![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to global-alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / gcc|
Return to global-alloc.c CVS log | Up to [Research Unix] / researchv10dc / cmd / gcc |
1.1 ! root 1: /* Allocate registers for pseudo-registers that span basic blocks. ! 2: Copyright (C) 1987, 1988 Free Software Foundation, Inc. ! 3: ! 4: This file is part of GNU CC. ! 5: ! 6: GNU CC is distributed in the hope that it will be useful, ! 7: but WITHOUT ANY WARRANTY. No author or distributor ! 8: accepts responsibility to anyone for the consequences of using it ! 9: or for whether it serves any particular purpose or works at all, ! 10: unless he says so in writing. Refer to the GNU CC General Public ! 11: License for full details. ! 12: ! 13: Everyone is granted permission to copy, modify and redistribute ! 14: GNU CC, but only under the conditions described in the ! 15: GNU CC General Public License. A copy of this license is ! 16: supposed to have been given to you along with GNU CC so you ! 17: can know your rights and responsibilities. It should be in a ! 18: file named COPYING. Among other things, the copyright notice ! 19: and this notice must be preserved on all copies. */ ! 20: ! 21: ! 22: #include <stdio.h> ! 23: #include "config.h" ! 24: #include "rtl.h" ! 25: #include "flags.h" ! 26: #include "basic-block.h" ! 27: #include "hard-reg-set.h" ! 28: #include "regs.h" ! 29: #include "insn-config.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: Someday 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: an 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 allocno, gives number of preferred hard reg, or -1 if none. */ ! 94: ! 95: static int *allocno_preferred_reg; ! 96: ! 97: /* max_allocno by max_allocno array of bits, ! 98: recording whether two allocno's conflict (can't go in the same ! 99: hardware register). ! 100: ! 101: `conflicts' is not symmetric; a conflict between allocno's i and j ! 102: is recorded either in element i,j or in element j,i. */ ! 103: ! 104: static int *conflicts; ! 105: ! 106: /* Number of ints require to hold max_allocno bits. ! 107: This is the length of a row in `conflicts'. */ ! 108: ! 109: static int allocno_row_words; ! 110: ! 111: /* Two macros to test or store 1 in an element of `conflicts'. */ ! 112: ! 113: #define CONFLICTP(I, J) \ ! 114: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ ! 115: & (1 << ((J) % INT_BITS))) ! 116: ! 117: #define SET_CONFLICT(I, J) \ ! 118: (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ ! 119: |= (1 << ((J) % INT_BITS))) ! 120: ! 121: /* Set of hard regs currently live (during scan of all insns). */ ! 122: ! 123: static HARD_REG_SET hard_regs_live; ! 124: ! 125: /* Indexed by N, set of hard regs conflicting with allocno N. */ ! 126: ! 127: static HARD_REG_SET *hard_reg_conflicts; ! 128: ! 129: #if 0 ! 130: /* Indexed by N, set of hard regs preferred by allocno N. ! 131: This was intended to be used to make allocnos go into regs ! 132: that they are loaded from, when possible, to reduce register shuffling. */ ! 133: ! 134: static HARD_REG_SET *hard_reg_preferences; ! 135: #endif ! 136: ! 137: /* Test a bit in TABLE, a vector of HARD_REG_SETs, ! 138: for vector element I, and hard register number J. */ ! 139: ! 140: #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J) ! 141: ! 142: /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */ ! 143: ! 144: #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J) ! 145: ! 146: /* Bit mask for allocnos live at current point in the scan. */ ! 147: ! 148: static int *allocnos_live; ! 149: ! 150: #define INT_BITS HOST_BITS_PER_INT ! 151: ! 152: /* Test, set or clear bit number I in allocnos_live, ! 153: a bit vector indexed by allocno. */ ! 154: ! 155: #define ALLOCNO_LIVE_P(I) \ ! 156: (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS))) ! 157: ! 158: #define SET_ALLOCNO_LIVE(I) \ ! 159: (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS))) ! 160: ! 161: #define CLEAR_ALLOCNO_LIVE(I) \ ! 162: (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS))) ! 163: ! 164: static int allocno_compare (); ! 165: static void mark_reg_store (); ! 166: static void mark_reg_live_nc (); ! 167: static void mark_reg_death (); ! 168: static void dump_conflicts (); ! 169: static void find_reg (); ! 170: static void global_conflicts (); ! 171: static void record_conflicts (); ! 172: ! 173: ! 174: /* Tables describing and classifying the hardware registers. */ ! 175: ! 176: /* Perform allocation of pseudo-registers not allocated by local_alloc. ! 177: FILE is a file to output debugging information on, ! 178: or zero if such output is not desired. */ ! 179: ! 180: void ! 181: global_alloc (file) ! 182: FILE *file; ! 183: { ! 184: register int i; ! 185: ! 186: max_allocno = 0; ! 187: ! 188: /* Establish mappings from register number to allocation number ! 189: and vice versa. In the process, count the allocnos. */ ! 190: ! 191: reg_allocno = (int *) alloca (max_regno * sizeof (int)); ! 192: ! 193: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 194: reg_allocno[i] = -1; ! 195: ! 196: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) ! 197: /* Note that reg_live_length[i] < 0 indicates a "constant" reg ! 198: that we are supposed to refrain from putting in a hard reg. ! 199: -2 means do make an allocno but don't allocate it. */ ! 200: if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1) ! 201: { ! 202: reg_allocno[i] = max_allocno++; ! 203: if (reg_live_length[i] == 0) ! 204: abort (); ! 205: } ! 206: else ! 207: reg_allocno[i] = -1; ! 208: ! 209: allocno_reg = (int *) alloca (max_allocno * sizeof (int)); ! 210: allocno_size = (int *) alloca (max_allocno * sizeof (int)); ! 211: allocno_preferred_reg = (int *) alloca (max_allocno * sizeof (int)); ! 212: bzero (allocno_size, max_allocno * sizeof (int)); ! 213: ! 214: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) ! 215: if (reg_allocno[i] >= 0) ! 216: { ! 217: allocno_reg[reg_allocno[i]] = i; ! 218: allocno_size[reg_allocno[i]] = PSEUDO_REGNO_SIZE (i); ! 219: allocno_preferred_reg[reg_allocno[i]] = -1; ! 220: } ! 221: ! 222: /* Allocate the space for the conflict tables. */ ! 223: ! 224: hard_reg_conflicts = (HARD_REG_SET *) ! 225: alloca (max_allocno * sizeof (HARD_REG_SET)); ! 226: bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET)); ! 227: ! 228: #if 0 ! 229: hard_reg_preferences = (HARD_REG_SET *) ! 230: alloca (max_allocno * sizeof (HARD_REG_SET)); ! 231: bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET)); ! 232: #endif ! 233: ! 234: allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS; ! 235: ! 236: conflicts = (int *) ! 237: alloca (max_allocno * allocno_row_words * sizeof (int)); ! 238: bzero (conflicts, max_allocno * allocno_row_words * sizeof (int)); ! 239: ! 240: allocnos_live = (int *) alloca (allocno_row_words * sizeof (int)); ! 241: ! 242: /* If there is work to be done (at least one reg to allocate), ! 243: perform global conflict analysis and allocate the regs. */ ! 244: ! 245: if (max_allocno > 0) ! 246: { ! 247: /* Scan all the insns and compute the conflicts among allocnos ! 248: and between allocnos and hard regs. */ ! 249: ! 250: global_conflicts (); ! 251: ! 252: /* Determine the order to allocate the remaining pseudo registers. */ ! 253: ! 254: allocno_order = (int *) alloca (max_allocno * sizeof (int)); ! 255: for (i = 0; i < max_allocno; i++) ! 256: allocno_order[i] = i; ! 257: ! 258: /* Default the size to 1, since allocno_compare uses it to divide by. */ ! 259: ! 260: for (i = 0; i < max_allocno; i++) ! 261: if (allocno_size[i] == 0) ! 262: allocno_size[i] = 1; ! 263: ! 264: qsort (allocno_order, max_allocno, sizeof (int), allocno_compare); ! 265: ! 266: if (file) ! 267: dump_conflicts (file); ! 268: ! 269: /* Try allocating them, one by one, in that order, ! 270: except for parameters marked with reg_live_length[regno] == -2. */ ! 271: ! 272: for (i = 0; i < max_allocno; i++) ! 273: if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0) ! 274: { ! 275: /* If we have a preferred hard register, try that first. */ ! 276: if (allocno_preferred_reg[allocno_order[i]] >= 0) ! 277: { ! 278: find_reg (allocno_order[i], 0, 0, ! 279: allocno_preferred_reg[allocno_order[i]]); ! 280: if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) ! 281: continue; ! 282: } ! 283: /* If we have more than one register class, ! 284: first try allocating in the class that is cheapest ! 285: for this pseudo-reg. If that fails, try any reg. */ ! 286: if (N_REG_CLASSES > 1) ! 287: { ! 288: find_reg (allocno_order[i], 0, 0, -1); ! 289: if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) ! 290: continue; ! 291: } ! 292: if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]])) ! 293: find_reg (allocno_order[i], 0, 1, -1); ! 294: } ! 295: } ! 296: ! 297: /* Do the reloads now while the allocno data still exist, so that we can ! 298: try to assign new hard regs to any pseudo regs that are spilled. */ ! 299: ! 300: if (n_basic_blocks > 0) ! 301: reload (basic_block_head[0], 1, file); ! 302: } ! 303: ! 304: /* Sort predicate for ordering the allocnos. ! 305: Returns -1 (1) if *v1 should be allocated before (after) *v2. */ ! 306: ! 307: static int ! 308: allocno_compare (v1, v2) ! 309: int *v1, *v2; ! 310: { ! 311: register int r1 = allocno_reg[*v1]; ! 312: register int r2 = allocno_reg[*v2]; ! 313: register double v ! 314: = ((double) (floor_log2 (reg_n_refs[r1]) * reg_n_refs[r1]) ! 315: / (reg_live_length[r1] * allocno_size[*v1])) ! 316: - ((double) (floor_log2 (reg_n_refs[r2]) * reg_n_refs[r2]) ! 317: / (reg_live_length[r2] * allocno_size[*v2])); ! 318: if (v < 0) ! 319: return 1; ! 320: if (v > 0) ! 321: return -1; ! 322: return 0; ! 323: } ! 324: ! 325: /* Scan the rtl code and record all conflicts in the conflict matrices. */ ! 326: ! 327: static void ! 328: global_conflicts () ! 329: { ! 330: register int b, i; ! 331: register rtx insn; ! 332: short *block_start_allocnos; ! 333: ! 334: block_start_allocnos = (short *) alloca (max_allocno * sizeof (short)); ! 335: ! 336: for (b = 0; b < n_basic_blocks; b++) ! 337: { ! 338: bzero (allocnos_live, allocno_row_words * sizeof (int)); ! 339: ! 340: /* Initialize table of registers currently live ! 341: to the state at the beginning of this basic block. ! 342: This also marks the conflicts among them. ! 343: ! 344: For pseudo-regs, there is only one bit for each one ! 345: no matter how many hard regs it occupies. ! 346: This is ok; we know the size from PSEUDO_REGNO_SIZE. ! 347: For explicit hard regs, we cannot know the size that way ! 348: since one hard reg can be used with various sizes. ! 349: Therefore, we must require that all the hard regs ! 350: implicitly live as part of a multi-word hard reg ! 351: are explicitly marked in basic_block_live_at_start. */ ! 352: ! 353: { ! 354: register int offset, bit; ! 355: register regset old = basic_block_live_at_start[b]; ! 356: int ax = 0; ! 357: ! 358: #ifdef HARD_REG_SET ! 359: hard_regs_live = old[0]; ! 360: #else ! 361: COPY_HARD_REG_SET (hard_regs_live, old); ! 362: #endif ! 363: for (offset = 0, i = 0; offset < regset_size; offset++) ! 364: if (old[offset] == 0) ! 365: i += HOST_BITS_PER_INT; ! 366: else ! 367: for (bit = 1; bit; bit <<= 1, i++) ! 368: { ! 369: if (i >= max_regno) ! 370: break; ! 371: if (old[offset] & bit) ! 372: { ! 373: register int a = reg_allocno[i]; ! 374: if (a >= 0) ! 375: { ! 376: SET_ALLOCNO_LIVE (a); ! 377: block_start_allocnos[ax++] = a; ! 378: } ! 379: else if ((a = reg_renumber[i]) >= 0) ! 380: mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i)); ! 381: } ! 382: } ! 383: ! 384: /* Record that each allocno now live conflicts with each other ! 385: allocno now live, and with each hard reg now live. */ ! 386: ! 387: record_conflicts (block_start_allocnos, ax); ! 388: } ! 389: ! 390: insn = basic_block_head[b]; ! 391: ! 392: /* Scan the code of this basic block, noting which allocnos ! 393: and hard regs are born or die. When one is born, ! 394: record a conflict with all others currently live. */ ! 395: ! 396: while (1) ! 397: { ! 398: register RTX_CODE code = GET_CODE (insn); ! 399: register rtx link; ! 400: rtx regs_set[MAX_SETS_PER_INSN + MAX_CLOBBERS_PER_INSN]; ! 401: int n_regs_set = 0; ! 402: ! 403: if (code == INSN || code == CALL_INSN || code == JUMP_INSN) ! 404: { ! 405: /* Mark any registers dead after INSN as dead now. */ ! 406: ! 407: for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) ! 408: if (REG_NOTE_KIND (link) == REG_DEAD) ! 409: mark_reg_death (XEXP (link, 0)); ! 410: ! 411: /* Mark any registers set in INSN as live, ! 412: and mark them as conflicting with all other live regs. */ ! 413: ! 414: if ((GET_CODE (PATTERN (insn)) == SET ! 415: || GET_CODE (PATTERN (insn)) == CLOBBER) ! 416: && GET_CODE (SET_DEST (PATTERN (insn))) == REG) ! 417: { ! 418: register rtx z = SET_DEST (PATTERN (insn)); ! 419: regs_set[n_regs_set++] = z; ! 420: mark_reg_store (z); ! 421: } ! 422: if ((GET_CODE (PATTERN (insn)) == SET ! 423: || GET_CODE (PATTERN (insn)) == CLOBBER) ! 424: && GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG) ! 425: { ! 426: register rtx z = SUBREG_REG (SET_DEST (PATTERN (insn))); ! 427: if (GET_CODE (z) == REG) ! 428: { ! 429: regs_set[n_regs_set++] = z; ! 430: mark_reg_store (z); ! 431: } ! 432: } ! 433: else if (GET_CODE (PATTERN (insn)) == PARALLEL) ! 434: { ! 435: register rtx y = PATTERN (insn); ! 436: for (i = XVECLEN (y, 0) - 1; ! 437: i >= 0; i--) ! 438: if (GET_CODE (XVECEXP (y, 0, i)) == SET ! 439: || GET_CODE (XVECEXP (y, 0, i)) == CLOBBER) ! 440: { ! 441: rtx z = SET_DEST (XVECEXP (y, 0, i)); ! 442: if (GET_CODE (z) == REG) ! 443: { ! 444: regs_set[n_regs_set++] = z; ! 445: mark_reg_store (z); ! 446: } ! 447: if (GET_CODE (z) == SUBREG ! 448: && GET_CODE (SUBREG_REG (z)) == REG) ! 449: { ! 450: regs_set[n_regs_set++] = SUBREG_REG (z); ! 451: mark_reg_store (SUBREG_REG (z)); ! 452: } ! 453: } ! 454: } ! 455: ! 456: /* Mark any registers both set and dead after INSN as dead. ! 457: This is not redundant! ! 458: A register may be set and killed in the same insn. ! 459: It is necessary to mark them as live, above, to get ! 460: the right conflicts within the insn. */ ! 461: ! 462: while (n_regs_set > 0) ! 463: if (find_regno_note (insn, REG_DEAD, REGNO (regs_set[--n_regs_set]))) ! 464: mark_reg_death (regs_set[n_regs_set]); ! 465: ! 466: /* Likewise for regs set by incrementation. */ ! 467: ! 468: for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) ! 469: if (REG_NOTE_KIND (link) == REG_INC ! 470: && find_regno_note (insn, REG_DEAD, REGNO (XEXP (link, 0)))) ! 471: mark_reg_death (XEXP (link, 0)); ! 472: } ! 473: ! 474: if (insn == basic_block_end[b]) ! 475: break; ! 476: insn = NEXT_INSN (insn); ! 477: } ! 478: } ! 479: } ! 480: ! 481: /* Assign a hard register to ALLOCNO; look for one that is the beginning ! 482: of a long enough stretch of hard regs none of which conflicts with ALLOCNO. ! 483: If PREFREG is >= 0, try that hard reg first. ! 484: ! 485: If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg. ! 486: Otherwise ignore that preferred class. ! 487: ! 488: If we find one, record it in reg_renumber. ! 489: If not, do nothing. */ ! 490: ! 491: static void ! 492: find_reg (allocno, losers, all_regs_p, prefreg) ! 493: int allocno; ! 494: register short *losers; ! 495: int all_regs_p; ! 496: int prefreg; ! 497: { ! 498: register int i; ! 499: #ifdef HARD_REG_SET ! 500: register /* Declare it register if it's a scalar. */ ! 501: #endif ! 502: HARD_REG_SET used; ! 503: ! 504: enum reg_class class ! 505: = all_regs_p ? GENERAL_REGS : reg_preferred_class (allocno_reg[allocno]); ! 506: enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]); ! 507: ! 508: COPY_HARD_REG_SET (used, ! 509: (reg_crosses_call[allocno_reg[allocno]] ! 510: ? call_used_reg_set : fixed_reg_set)); ! 511: ! 512: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); ! 513: IOR_HARD_REG_SET (used, hard_reg_conflicts[allocno]); ! 514: if (frame_pointer_needed) ! 515: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); ! 516: ! 517: /* If a preferred register was specified, try it first. */ ! 518: ! 519: i = -1; ! 520: if (prefreg >= 0) ! 521: if (! TEST_HARD_REG_BIT (used, prefreg) ! 522: && (losers == 0 || losers[prefreg] < 0) ! 523: && HARD_REGNO_MODE_OK (prefreg, mode)) ! 524: { ! 525: register int j; ! 526: register int lim = prefreg + HARD_REGNO_NREGS (prefreg, mode); ! 527: for (j = prefreg + 1; ! 528: (j < lim ! 529: && ! TEST_HARD_REG_BIT (used, j) ! 530: && (losers == 0 || losers[j] < 0)); ! 531: j++); ! 532: if (j == lim) ! 533: i = prefreg; ! 534: } ! 535: ! 536: /* Otherwise try each hard reg to see if it fits. */ ! 537: ! 538: if (i < 0) ! 539: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 540: if (! TEST_HARD_REG_BIT (used, i) ! 541: && (losers == 0 || losers[i] < 0) ! 542: && HARD_REGNO_MODE_OK (i, mode)) ! 543: { ! 544: register int j; ! 545: register int lim = i + HARD_REGNO_NREGS (i, mode); ! 546: for (j = i + 1; ! 547: (j < lim ! 548: && ! TEST_HARD_REG_BIT (used, j) ! 549: && (losers == 0 || losers[j] < 0)); ! 550: j++); ! 551: if (j == lim) ! 552: break; ! 553: i = j; /* Skip starting points we know will lose */ ! 554: } ! 555: ! 556: /* Did we find a register? */ ! 557: ! 558: if (i < FIRST_PSEUDO_REGISTER) ! 559: { ! 560: register int lim, j; ! 561: HARD_REG_SET this_reg; ! 562: ! 563: /* Yes. Record it as the hard register of this pseudo-reg. */ ! 564: reg_renumber[allocno_reg[allocno]] = i; ! 565: /* For each other pseudo-reg conflicting with this one, ! 566: mark it as conflicting with the hard regs this one occupies. */ ! 567: CLEAR_HARD_REG_SET (this_reg); ! 568: lim = i + HARD_REGNO_NREGS (i, mode); ! 569: for (j = i; j < lim; j++) ! 570: SET_HARD_REG_BIT (this_reg, j); ! 571: lim = allocno; ! 572: for (j = 0; j < max_allocno; j++) ! 573: if (CONFLICTP (lim, j) || CONFLICTP (j, lim)) ! 574: { ! 575: IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg); ! 576: } ! 577: } ! 578: } ! 579: ! 580: /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in. ! 581: Perhaps it had previously seemed not worth a hard reg, ! 582: or perhaps its old hard reg has been commandeered for reloads. ! 583: FORBIDDEN_REGS is a vector that indicates certain hard regs ! 584: that may not be used, even if they do not appear to be allocated. ! 585: A nonnegative element means the corresponding hard reg is forbidden. ! 586: If FORBIDDEN_REGS is zero, no regs are forbidden. */ ! 587: ! 588: void ! 589: retry_global_alloc (regno, forbidden_regs) ! 590: int regno; ! 591: short *forbidden_regs; ! 592: { ! 593: int allocno = reg_allocno[regno]; ! 594: if (allocno >= 0) ! 595: { ! 596: /* If we have more than one register class, ! 597: first try allocating in the class that is cheapest ! 598: for this pseudo-reg. If that fails, try any reg. */ ! 599: if (N_REG_CLASSES > 1) ! 600: find_reg (allocno, forbidden_regs, 0, -1); ! 601: if (reg_renumber[regno] < 0 ! 602: && !reg_preferred_or_nothing (regno)) ! 603: find_reg (allocno, forbidden_regs, 1, -1); ! 604: } ! 605: } ! 606: ! 607: /* Called from reload pass to see if current function's pseudo regs ! 608: require a frame pointer to be allocated and set up. ! 609: ! 610: Return 1 if so, 0 otherwise. ! 611: We may alter the hard-reg allocation of the pseudo regs ! 612: in order to make the frame pointer unnecessary. ! 613: However, if the value is 1, nothing has been altered. ! 614: ! 615: Args grant access to some tables used in reload1.c. ! 616: See there for info on them. */ ! 617: ! 618: int ! 619: check_frame_pointer_required (reg_equiv_constant, reg_equiv_mem) ! 620: rtx *reg_equiv_constant, *reg_equiv_mem; ! 621: { ! 622: register int i; ! 623: HARD_REG_SET *old_hard_reg_conflicts; ! 624: short *old_reg_renumber; ! 625: char old_regs_ever_live[FIRST_PSEUDO_REGISTER]; ! 626: ! 627: /* If any pseudo reg has no hard reg and no equivalent, ! 628: we must have a frame pointer. */ ! 629: ! 630: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) ! 631: if (reg_renumber[i] < 0 && reg_equiv_mem[i] == 0 ! 632: && reg_equiv_constant[i] == 0 && reg_n_refs[i] > 0) ! 633: return 1; ! 634: ! 635: /* If we might not need a frame pointer, ! 636: try finding a hard reg for any pseudo that has a memory equivalent. ! 637: That is because the memory equivalent probably refers to a frame ! 638: pointer. */ ! 639: ! 640: old_reg_renumber = (short *) alloca (max_regno * sizeof (short)); ! 641: old_hard_reg_conflicts = (HARD_REG_SET *) ! 642: alloca (max_allocno * sizeof (HARD_REG_SET)); ! 643: ! 644: bcopy (reg_renumber, old_reg_renumber, max_regno * sizeof (short)); ! 645: bcopy (hard_reg_conflicts, old_hard_reg_conflicts, ! 646: max_allocno * sizeof (HARD_REG_SET)); ! 647: bcopy (regs_ever_live, old_regs_ever_live, sizeof regs_ever_live); ! 648: ! 649: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) ! 650: if (reg_renumber[i] < 0 && reg_equiv_mem[i] != 0) ! 651: { ! 652: retry_global_alloc (i, 0); ! 653: /* If we can't find a hard reg for ALL of them, ! 654: or if a previously unneeded hard reg is used that requires saving, ! 655: we fail: set all those pseudos back as they were. */ ! 656: if (reg_renumber[i] < 0 ! 657: || (! old_regs_ever_live[reg_renumber[i]] ! 658: && ! call_used_regs[reg_renumber[i]])) ! 659: { ! 660: bcopy (old_reg_renumber, reg_renumber, ! 661: max_regno * sizeof (short)); ! 662: bcopy (old_hard_reg_conflicts, hard_reg_conflicts, ! 663: max_allocno * sizeof (HARD_REG_SET)); ! 664: bcopy (old_regs_ever_live, regs_ever_live, sizeof regs_ever_live); ! 665: return 1; ! 666: } ! 667: mark_home_live (i); ! 668: } ! 669: ! 670: return 0; ! 671: } ! 672: ! 673: /* Record a conflict between register REGNO ! 674: and everything currently live. ! 675: REGNO must not be a pseudo reg that was allocated ! 676: by local_alloc; such numbers must be translated through ! 677: reg_renumber before calling here. */ ! 678: ! 679: static void ! 680: record_one_conflict (regno) ! 681: int regno; ! 682: { ! 683: register int j; ! 684: ! 685: if (regno < FIRST_PSEUDO_REGISTER) ! 686: /* When a hard register becomes live, ! 687: record conflicts with live pseudo regs. */ ! 688: for (j = 0; j < max_allocno; j++) ! 689: { ! 690: if (ALLOCNO_LIVE_P (j)) ! 691: SET_HARD_REG_BIT (hard_reg_conflicts[j], regno); ! 692: } ! 693: else ! 694: /* When a pseudo-register becomes live, ! 695: record conflicts first with hard regs, ! 696: then with other pseudo regs. */ ! 697: { ! 698: register int ialloc = reg_allocno[regno]; ! 699: register int ialloc_prod = ialloc * allocno_row_words; ! 700: IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live); ! 701: for (j = allocno_row_words - 1; j >= 0; j--) ! 702: conflicts[ialloc_prod + j] |= allocnos_live[j]; ! 703: } ! 704: } ! 705: ! 706: /* Record all allocnos currently live as conflicting ! 707: with each other and with all hard regs currently live. ! 708: ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that ! 709: are currently live. Their bits are also flagged in allocnos_live. */ ! 710: ! 711: static void ! 712: record_conflicts (allocno_vec, len) ! 713: register short *allocno_vec; ! 714: register int len; ! 715: { ! 716: register int allocno; ! 717: register int j; ! 718: register int ialloc_prod; ! 719: ! 720: while (--len >= 0) ! 721: { ! 722: allocno = allocno_vec[len]; ! 723: ialloc_prod = allocno * allocno_row_words; ! 724: IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live); ! 725: for (j = allocno_row_words - 1; j >= 0; j--) ! 726: conflicts[ialloc_prod + j] |= allocnos_live[j]; ! 727: } ! 728: } ! 729: ! 730: /* Handle the case where REG is set by the insn being scanned, ! 731: during the forward scan to accumulate conflicts. ! 732: Store a 1 in regs_live or allocnos_live for this register, record how many ! 733: consecutive hardware registers it actually needs, ! 734: and record a conflict with all other registers already live. ! 735: ! 736: Note that even if REG does not remain alive after this insn, ! 737: we must mark it here as live, to ensure a conflict between ! 738: REG and any other regs set in this insn that really do live. ! 739: This is because those other regs could be considered after this. */ ! 740: ! 741: static void ! 742: mark_reg_store (reg) ! 743: rtx reg; ! 744: { ! 745: register int regno = REGNO (reg); ! 746: ! 747: if (reg_renumber[regno] >= 0) ! 748: regno = reg_renumber[regno]; ! 749: ! 750: /* Either this is one of the max_allocno pseudo regs not allocated, ! 751: or it is or has a hardware reg. First handle the pseudo-regs. */ ! 752: if (regno >= FIRST_PSEUDO_REGISTER) ! 753: { ! 754: if (reg_allocno[regno] >= 0) ! 755: { ! 756: SET_ALLOCNO_LIVE (reg_allocno[regno]); ! 757: record_one_conflict (regno); ! 758: } ! 759: } ! 760: /* Handle hardware regs (and pseudos allocated to hard regs). */ ! 761: else if (! fixed_regs[regno]) ! 762: { ! 763: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); ! 764: while (regno < last) ! 765: { ! 766: record_one_conflict (regno); ! 767: SET_HARD_REG_BIT (hard_regs_live, regno); ! 768: regno++; ! 769: } ! 770: } ! 771: } ! 772: ! 773: /* Mark REG as being dead (following the insn being scanned now). ! 774: Store a 0 in regs_live or allocnos_live for this register. */ ! 775: ! 776: static void ! 777: mark_reg_death (reg) ! 778: rtx reg; ! 779: { ! 780: register int regno = REGNO (reg); ! 781: ! 782: /* For pseudo reg, see if it has been assigned a hardware reg. */ ! 783: if (reg_renumber[regno] >= 0) ! 784: regno = reg_renumber[regno]; ! 785: ! 786: /* Either this is one of the max_allocno pseudo regs not allocated, ! 787: or it is a hardware reg. First handle the pseudo-regs. */ ! 788: if (regno >= FIRST_PSEUDO_REGISTER) ! 789: { ! 790: if (reg_allocno[regno] >= 0) ! 791: CLEAR_ALLOCNO_LIVE (reg_allocno[regno]); ! 792: } ! 793: /* Handle hardware regs (and pseudos allocated to hard regs). */ ! 794: else if (! fixed_regs[regno]) ! 795: { ! 796: /* Pseudo regs already assigned hardware regs are treated ! 797: almost the same as explicit hardware regs. */ ! 798: register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); ! 799: while (regno < last) ! 800: { ! 801: CLEAR_HARD_REG_BIT (hard_regs_live, regno); ! 802: regno++; ! 803: } ! 804: } ! 805: } ! 806: ! 807: /* Mark hard reg REGNO as currently live, assuming machine mode MODE ! 808: for the value stored in it. MODE determines how many consecutive ! 809: registers are actually in use. Do not record conflicts; ! 810: it is assumed that the caller will do that. */ ! 811: ! 812: static void ! 813: mark_reg_live_nc (regno, mode) ! 814: register int regno; ! 815: enum machine_mode mode; ! 816: { ! 817: register int last = regno + HARD_REGNO_NREGS (regno, mode); ! 818: while (regno < last) ! 819: { ! 820: SET_HARD_REG_BIT (hard_regs_live, regno); ! 821: regno++; ! 822: } ! 823: } ! 824: ! 825: /* Print debugging trace information if -greg switch is given, ! 826: showing the information on which the allocation decisions are based. */ ! 827: ! 828: static void ! 829: dump_conflicts (file) ! 830: FILE *file; ! 831: { ! 832: register int i; ! 833: fprintf (file, ";; %d regs to allocate:", max_allocno); ! 834: for (i = 0; i < max_allocno; i++) ! 835: { ! 836: fprintf (file, " %d", allocno_reg[allocno_order[i]]); ! 837: if (allocno_size[allocno_order[i]] != 1) ! 838: fprintf (file, " (%d)", allocno_size[allocno_order[i]]); ! 839: } ! 840: fprintf (file, "\n"); ! 841: ! 842: for (i = 0; i < max_allocno; i++) ! 843: { ! 844: register int j; ! 845: fprintf (file, ";; %d conflicts:", allocno_reg[i], ! 846: reg_renumber[allocno_reg[i]]); ! 847: for (j = 0; j < max_allocno; j++) ! 848: if (CONFLICTP (i, j) || CONFLICTP (j, i)) ! 849: fprintf (file, " %d", allocno_reg[j]); ! 850: for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) ! 851: if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j)) ! 852: fprintf (file, " %d", j); ! 853: fprintf (file, "\n"); ! 854: } ! 855: fprintf (file, "\n"); ! 856: } ! 857: ! 858: void ! 859: dump_global_regs (file) ! 860: FILE *file; ! 861: { ! 862: register int i; ! 863: ! 864: fprintf (file, ";; Register dispositions:"); ! 865: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) ! 866: { ! 867: if (reg_renumber[i] >= 0) ! 868: fprintf (file, " %d in %d ", i, reg_renumber[i]); ! 869: } ! 870: ! 871: fprintf (file, "\n\n;; Hard regs used: "); ! 872: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) ! 873: if (regs_ever_live[i]) ! 874: fprintf (file, " %d", i); ! 875: fprintf (file, "\n\n"); ! 876: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.