home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / gcc-2.3.3-src.lha / GNU / src / amiga / gcc-2.3.3 / global.c < prev    next >
C/C++ Source or Header  |  1994-02-06  |  53KB  |  1,657 lines
  1. /* Allocate registers for pseudo-registers that span basic blocks.
  2.    Copyright (C) 1987, 1988, 1991 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include <stdio.h>
  22. #include "config.h"
  23. #include "rtl.h"
  24. #include "flags.h"
  25. #include "basic-block.h"
  26. #include "hard-reg-set.h"
  27. #include "regs.h"
  28. #include "insn-config.h"
  29. #include "output.h"
  30.  
  31. /* This pass of the compiler performs global register allocation.
  32.    It assigns hard register numbers to all the pseudo registers
  33.    that were not handled in local_alloc.  Assignments are recorded
  34.    in the vector reg_renumber, not by changing the rtl code.
  35.    (Such changes are made by final).  The entry point is
  36.    the function global_alloc.
  37.  
  38.    After allocation is complete, the reload pass is run as a subroutine
  39.    of this pass, so that when a pseudo reg loses its hard reg due to
  40.    spilling it is possible to make a second attempt to find a hard
  41.    reg for it.  The reload pass is independent in other respects
  42.    and it is run even when stupid register allocation is in use.
  43.  
  44.    1. count the pseudo-registers still needing allocation
  45.    and assign allocation-numbers (allocnos) to them.
  46.    Set up tables reg_allocno and allocno_reg to map 
  47.    reg numbers to allocnos and vice versa.
  48.    max_allocno gets the number of allocnos in use.
  49.  
  50.    2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
  51.    Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
  52.    for conflicts between allocnos and explicit hard register use
  53.    (which includes use of pseudo-registers allocated by local_alloc).
  54.  
  55.    3. for each basic block
  56.     walk forward through the block, recording which
  57.     unallocated registers and which hardware registers are live.
  58.     Build the conflict matrix between the unallocated registers
  59.     and another of unallocated registers versus hardware registers.
  60.     Also record the preferred hardware registers
  61.     for each unallocated one.
  62.  
  63.    4. Sort a table of the allocnos into order of
  64.    desirability of the variables.
  65.  
  66.    5. Allocate the variables in that order; each if possible into
  67.    a preferred register, else into another register.  */
  68.  
  69. /* Number of pseudo-registers still requiring allocation
  70.    (not allocated by local_allocate).  */
  71.  
  72. static int max_allocno;
  73.  
  74. /* Indexed by (pseudo) reg number, gives the allocno, or -1
  75.    for pseudo registers already allocated by local_allocate.  */
  76.  
  77. static int *reg_allocno;
  78.  
  79. /* Indexed by allocno, gives the reg number.  */
  80.  
  81. static int *allocno_reg;
  82.  
  83. /* A vector of the integers from 0 to max_allocno-1,
  84.    sorted in the order of first-to-be-allocated first.  */
  85.  
  86. static int *allocno_order;
  87.  
  88. /* Indexed by an allocno, gives the number of consecutive
  89.    hard registers needed by that pseudo reg.  */
  90.  
  91. static int *allocno_size;
  92.  
  93. /* Indexed by (pseudo) reg number, gives the number of another
  94.    lower-numbered pseudo reg which can share a hard reg with this pseudo
  95.    *even if the two pseudos would otherwise appear to conflict*.  */
  96.  
  97. static int *reg_may_share;
  98.  
  99. /* Define the number of bits in each element of `conflicts' and what
  100.    type that element has.  We use the largest integer format on the
  101.    host machine.  */
  102.  
  103. #define INT_BITS HOST_BITS_PER_WIDE_INT
  104. #define INT_TYPE HOST_WIDE_INT
  105.  
  106. /* max_allocno by max_allocno array of bits,
  107.    recording whether two allocno's conflict (can't go in the same
  108.    hardware register).
  109.  
  110.    `conflicts' is not symmetric; a conflict between allocno's i and j
  111.    is recorded either in element i,j or in element j,i.  */
  112.  
  113. static INT_TYPE *conflicts;
  114.  
  115. /* Number of ints require to hold max_allocno bits.
  116.    This is the length of a row in `conflicts'.  */
  117.  
  118. static int allocno_row_words;
  119.  
  120. /* Two macros to test or store 1 in an element of `conflicts'.  */
  121.  
  122. #define CONFLICTP(I, J) \
  123.  (conflicts[(I) * allocno_row_words + (J) / INT_BITS]    \
  124.   & ((INT_TYPE) 1 << ((J) % INT_BITS)))
  125.  
  126. #define SET_CONFLICT(I, J) \
  127.  (conflicts[(I) * allocno_row_words + (J) / INT_BITS]    \
  128.   |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
  129.  
  130. /* Set of hard regs currently live (during scan of all insns).  */
  131.  
  132. static HARD_REG_SET hard_regs_live;
  133.  
  134. /* Indexed by N, set of hard regs conflicting with allocno N.  */
  135.  
  136. static HARD_REG_SET *hard_reg_conflicts;
  137.  
  138. /* Indexed by N, set of hard regs preferred by allocno N.
  139.    This is used to make allocnos go into regs that are copied to or from them,
  140.    when possible, to reduce register shuffling.  */
  141.  
  142. static HARD_REG_SET *hard_reg_preferences;
  143.  
  144. /* Similar, but just counts register preferences made in simple copy
  145.    operations, rather than arithmetic.  These are given priority because
  146.    we can always eliminate an insn by using these, but using a register
  147.    in the above list won't always eliminate an insn.  */
  148.  
  149. static HARD_REG_SET *hard_reg_copy_preferences;
  150.  
  151. /* Similar to hard_reg_preferences, but includes bits for subsequent
  152.    registers when an allocno is multi-word.  The above variable is used for
  153.    allocation while this is used to build reg_someone_prefers, below.  */
  154.  
  155. static HARD_REG_SET *hard_reg_full_preferences;
  156.  
  157. /* Indexed by N, set of hard registers that some later allocno has a
  158.    preference for.  */
  159.  
  160. static HARD_REG_SET *regs_someone_prefers;
  161.  
  162. /* Set of registers that global-alloc isn't supposed to use.  */
  163.  
  164. static HARD_REG_SET no_global_alloc_regs;
  165.  
  166. /* Set of registers used so far.  */
  167.  
  168. static HARD_REG_SET regs_used_so_far;
  169.  
  170. /* Number of calls crossed by each allocno.  */
  171.  
  172. static int *allocno_calls_crossed;
  173.  
  174. /* Number of refs (weighted) to each allocno.  */
  175.  
  176. static int *allocno_n_refs;
  177.  
  178. /* Guess at live length of each allocno.
  179.    This is actually the max of the live lengths of the regs.  */
  180.  
  181. static int *allocno_live_length;
  182.  
  183. /* Number of refs (weighted) to each hard reg, as used by local alloc.
  184.    It is zero for a reg that contains global pseudos or is explicitly used.  */
  185.  
  186. static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
  187.  
  188. /* Guess at live length of each hard reg, as used by local alloc.
  189.    This is actually the sum of the live lengths of the specific regs.  */
  190.  
  191. static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
  192.  
  193. /* Test a bit in TABLE, a vector of HARD_REG_SETs,
  194.    for vector element I, and hard register number J.  */
  195.  
  196. #define REGBITP(TABLE, I, J)     TEST_HARD_REG_BIT (TABLE[I], J)
  197.  
  198. /* Set to 1 a bit in a vector of HARD_REG_SETs.  Works like REGBITP.  */
  199.  
  200. #define SET_REGBIT(TABLE, I, J)  SET_HARD_REG_BIT (TABLE[I], J)
  201.  
  202. /* Bit mask for allocnos live at current point in the scan.  */
  203.  
  204. static INT_TYPE *allocnos_live;
  205.  
  206. /* Test, set or clear bit number I in allocnos_live,
  207.    a bit vector indexed by allocno.  */
  208.  
  209. #define ALLOCNO_LIVE_P(I) \
  210.   (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
  211.  
  212. #define SET_ALLOCNO_LIVE(I) \
  213.   (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
  214.  
  215. #define CLEAR_ALLOCNO_LIVE(I) \
  216.   (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
  217.  
  218. /* This is turned off because it doesn't work right for DImode.
  219.    (And it is only used for DImode, so the other cases are worthless.)
  220.    The problem is that it isn't true that there is NO possibility of conflict;
  221.    only that there is no conflict if the two pseudos get the exact same regs.
  222.    If they were allocated with a partial overlap, there would be a conflict.
  223.    We can't safely turn off the conflict unless we have another way to
  224.    prevent the partial overlap.
  225.  
  226.    Idea: change hard_reg_conflicts so that instead of recording which
  227.    hard regs the allocno may not overlap, it records where the allocno
  228.    may not start.  Change both where it is used and where