![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to local-alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to local-alloc.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Allocate registers within a basic block, for GNU compiler. 1.1.1.6 ! root 2: Copyright (C) 1987, 1988, 1991, 1993 Free Software Foundation, Inc. 1.1 root 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: /* Allocation of hard register numbers to pseudo registers is done in 22: two passes. In this pass we consider only regs that are born and 23: die once within one basic block. We do this one basic block at a 24: time. Then the next pass allocates the registers that remain. 25: Two passes are used because this pass uses methods that work only 26: on linear code, but that do a better job than the general methods 27: used in global_alloc, and more quickly too. 28: 29: The assignments made are recorded in the vector reg_renumber 30: whose space is allocated here. The rtl code itself is not altered. 31: 32: We assign each instruction in the basic block a number 33: which is its order from the beginning of the block. 34: Then we can represent the lifetime of a pseudo register with 35: a pair of numbers, and check for conflicts easily. 36: We can record the availability of hard registers with a 37: HARD_REG_SET for each instruction. The HARD_REG_SET 38: contains 0 or 1 for each hard reg. 39: 40: To avoid register shuffling, we tie registers together when one 41: dies by being copied into another, or dies in an instruction that 42: does arithmetic to produce another. The tied registers are 43: allocated as one. Registers with different reg class preferences 44: can never be tied unless the class preferred by one is a subclass 45: of the one preferred by the other. 46: 47: Tying is represented with "quantity numbers". 48: A non-tied register is given a new quantity number. 49: Tied registers have the same quantity number. 50: 51: We have provision to exempt registers, even when they are contained 52: within the block, that can be tied to others that are not contained in it. 53: This is so that global_alloc could process them both and tie them then. 54: But this is currently disabled since tying in global_alloc is not 55: yet implemented. */ 56: 57: #include <stdio.h> 58: #include "config.h" 59: #include "rtl.h" 60: #include "flags.h" 61: #include "basic-block.h" 62: #include "regs.h" 63: #include "hard-reg-set.h" 64: #include "insn-config.h" 65: #include "recog.h" 66: #include "output.h" 67: 1.1.1.5 root 68: /* Pseudos allocated here cannot be reallocated by global.c if the hard 69: register is used as a spill register. So we don't allocate such pseudos 70: here if their preferred class is likely to be used by spills. 71: 72: On most machines, the appropriate test is if the class has one 73: register, so we default to that. */ 74: 75: #ifndef CLASS_LIKELY_SPILLED_P 76: #define CLASS_LIKELY_SPILLED_P(CLASS) (reg_class_size[(int) (CLASS)] == 1) 77: #endif 78: 1.1 root 79: /* Next quantity number available for allocation. */ 80: 81: static int next_qty; 82: 83: /* In all the following vectors indexed by quantity number. */ 84: 85: /* Element Q is the hard reg number chosen for quantity Q, 86: or -1 if none was found. */ 87: 88: static short *qty_phys_reg; 89: 90: /* We maintain two hard register sets that indicate suggested hard registers 91: for each quantity. The first, qty_phys_copy_sugg, contains hard registers 92: that are tied to the quantity by a simple copy. The second contains all 93: hard registers that are tied to the quantity via an arithmetic operation. 94: 95: The former register set is given priority for allocation. This tends to 96: eliminate copy insns. */ 97: 98: /* Element Q is a set of hard registers that are suggested for quantity Q by 99: copy insns. */ 100: 101: static HARD_REG_SET *qty_phys_copy_sugg; 102: 103: /* Element Q is a set of hard registers that are suggested for quantity Q by 104: arithmetic insns. */ 105: 106: static HARD_REG_SET *qty_phys_sugg; 107: 108: /* Element Q is non-zero if there is a suggested register in 109: qty_phys_copy_sugg. */ 110: 111: static char *qty_phys_has_copy_sugg; 112: 113: /* Element Q is non-zero if there is a suggested register in qty_phys_sugg. */ 114: 115: static char *qty_phys_has_sugg; 116: 117: /* Element Q is the number of refs to quantity Q. */ 118: 1.1.1.5 root 119: static int *qty_n_refs; 1.1 root 120: 121: /* Element Q is a reg class contained in (smaller than) the 122: preferred classes of all the pseudo regs that are tied in quantity Q. 123: This is the preferred class for allocating that quantity. */ 124: 125: static enum reg_class *qty_min_class; 126: 127: /* Insn number (counting from head of basic block) 128: where quantity Q was born. -1 if birth has not been recorded. */ 129: 130: static int *qty_birth; 131: 132: /* Insn number (counting from head of basic block) 133: where quantity Q died. Due to the way tying is done, 134: and the fact that we consider in this pass only regs that die but once, 135: a quantity can die only once. Each quantity's life span 136: is a set of consecutive insns. -1 if death has not been recorded. */ 137: 138: static int *qty_death; 139: 140: /* Number of words needed to hold the data in quantity Q. 141: This depends on its machine mode. It is used for these purposes: 142: 1. It is used in computing the relative importances of qtys, 143: which determines the order in which we look for regs for them. 144: 2. It is used in rules that prevent tying several registers of 145: different sizes in a way that is geometrically impossible 146: (see combine_regs). */ 147: 148: static int *qty_size; 149: 150: /* This holds the mode of the registers that are tied to qty Q, 151: or VOIDmode if registers with differing modes are tied together. */ 152: 153: static enum machine_mode *qty_mode; 154: 155: /* Number of times a reg tied to qty Q lives across a CALL_INSN. */ 156: 157: static int *qty_n_calls_crossed; 158: 1.1.1.4 root 159: /* Register class within which we allocate qty Q if we can't get 160: its preferred class. */ 1.1 root 161: 1.1.1.4 root 162: static enum reg_class *qty_alternate_class; 1.1 root 163: 164: /* Element Q is the SCRATCH expression for which this quantity is being 165: allocated or 0 if this quantity is allocating registers. */ 166: 167: static rtx *qty_scratch_rtx; 168: 169: /* Element Q is the register number of one pseudo register whose 170: reg_qty value is Q, or -1 is this quantity is for a SCRATCH. This 171: register should be the head of the chain maintained in reg_next_in_qty. */ 172: 1.1.1.5 root 173: static int *qty_first_reg; 1.1 root 174: 175: /* If (REG N) has been assigned a quantity number, is a register number 176: of another register assigned the same quantity number, or -1 for the 177: end of the chain. qty_first_reg point to the head of this chain. */ 178: 1.1.1.5 root 179: static int *reg_next_in_qty; 1.1 root 180: 181: /* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg 182: if it is >= 0, 183: of -1 if this register cannot be allocated by local-alloc, 184: or -2 if not known yet. 185: 186: Note that if we see a use or death of pseudo register N with 187: reg_qty[N] == -2, register N must be local to the current block. If 188: it were used in more than one block, we would have reg_qty[N] == -1. 189: This relies on the fact that if reg_basic_block[N] is >= 0, register N 190: will not appear in any other block. We save a considerable number of 191: tests by exploiting this. 192: 193: If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not 194: be referenced. */ 195: 196: static int *reg_qty; 197: 198: /* The offset (in words) of register N within its quantity. 199: This can be nonzero if register N is SImode, and has been tied 200: to a subreg of a DImode register. */ 201: 202: static char *reg_offset; 203: 204: /* Vector of substitutions of register numbers, 205: used to map pseudo regs into hardware regs. 206: This is set up as a result of register allocation. 207: Element N is the hard reg assigned to pseudo reg N, 208: or is -1 if no hard reg was assigned. 209: If N is a hard reg number, element N is N. */ 210: 211: short *reg_renumber; 212: 213: /* Set of hard registers live at the current point in the scan 214: of the instructions in a basic block. */ 215: 216: static HARD_REG_SET regs_live; 217: 218: /* Each set of hard registers indicates registers live at a particular 219: point in the basic block. For N even, regs_live_at[N] says which 220: hard registers are needed *after* insn N/2 (i.e., they may not 221: conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1. 222: 223: If an object is to conflict with the inputs of insn J but not the 224: outputs of insn J + 1, we say it is born at index J*2 - 1. Similarly, 225: if it is to conflict with the outputs of insn J but not the inputs of 226: insn J + 1, it is said to die at index J*2 + 1. */ 227: 228: static HARD_REG_SET *regs_live_at; 229: 1.1.1.6 ! root 230: int *scratch_block; ! 231: rtx *scratch_list; ! 232: int scratch_list_length; ! 233: static int scratch_index; ! 234: 1.1 root 235: /* Communicate local vars `insn_number' and `insn' 236: from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'. */ 237: static int this_insn_number; 238: static rtx this_insn; 239: 240: static void block_alloc (); 241: static void update_equiv_regs (); 242: static int no_conflict_p (); 243: static int combine_regs (); 244: static void wipe_dead_reg (); 245: static int find_free_reg (); 246: static void reg_is_born (); 247: static void reg_is_set (); 248: static void mark_life (); 249: static void post_mark_life (); 250: static int qty_compare (); 251: static int qty_compare_1 (); 252: static int reg_meets_class_p (); 253: static void update_qty_class (); 254: static int requires_inout_p (); 255: 256: /* Allocate a new quantity (new within current basic block) 257: for register number REGNO which is born at index BIRTH 258: within the block. MODE and SIZE are info on reg REGNO. */ 259: 260: static void 261: alloc_qty (regno, mode, size, birth) 262: int regno; 263: enum machine_mode mode; 264: int size, birth; 265: { 266: register int qty = next_qty++; 267: 268: reg_qty[regno] = qty; 269: reg_offset[regno] = 0; 270: reg_next_in_qty[regno] = -1; 271: 272: qty_first_reg[qty] = regno; 273: qty_size[qty] = size; 274: qty_mode[qty] = mode; 275: qty_birth[qty] = birth; 276: qty_n_calls_crossed[qty] = reg_n_calls_crossed[regno]; 277: qty_min_class[qty] = reg_preferred_class (regno); 1.1.1.4 root 278: qty_alternate_class[qty] = reg_alternate_class (regno); 1.1 root 279: qty_n_refs[qty] = reg_n_refs[regno]; 280: } 281: 282: /* Similar to `alloc_qty', but allocates a quantity for a SCRATCH rtx 283: used as operand N in INSN. We assume here that the SCRATCH is used in 284: a CLOBBER. */ 285: 286: static void 287: alloc_qty_for_scratch (scratch, n, insn, insn_code_num, insn_number) 288: rtx scratch; 289: int n; 290: rtx insn; 291: int insn_code_num, insn_number; 292: { 293: register int qty; 294: enum reg_class class; 295: char *p, c; 296: int i; 297: 1.1.1.4 root 298: #ifdef REGISTER_CONSTRAINTS 1.1 root 299: /* If we haven't yet computed which alternative will be used, do so now. 300: Then set P to the constraints for that alternative. */ 301: if (which_alternative == -1) 302: if (! constrain_operands (insn_code_num, 0)) 303: return; 304: 305: for (p = insn_operand_constraint[insn_code_num][n], i = 0; 306: *p && i < which_alternative; p++) 307: if (*p == ',') 308: i++; 309: 310: /* Compute the class required for this SCRATCH. If we don't need a 311: register, the class will remain NO_REGS. If we guessed the alternative 312: number incorrectly, reload will fix things up for us. */ 313: 314: class = NO_REGS; 315: while ((c = *p++) != '\0' && c != ',') 316: switch (c) 317: { 318: case '=': case '+': case '?': 319: case '#': case '&': case '!': 320: case '*': case '%': 321: case '0': case '1': case '2': case '3': case '4': 322: case 'm': case '<': case '>': case 'V': case 'o': 323: case 'E': case 'F': case 'G': case 'H': 324: case 's': case 'i': case 'n': 325: case 'I': case 'J': case 'K': case 'L': 326: case 'M': case 'N': case 'O': case 'P': 327: #ifdef EXTRA_CONSTRAINT 328: case 'Q': case 'R': case 'S': case 'T': case 'U': 329: #endif 330: case 'p': 331: /* These don't say anything we care about. */ 332: break; 333: 334: case 'X': 335: /* We don't need to allocate this SCRATCH. */ 336: return; 337: 338: case 'g': case 'r': 339: class = reg_class_subunion[(int) class][(int) GENERAL_REGS]; 340: break; 341: 342: default: 343: class 344: = reg_class_subunion[(int) class][(int) REG_CLASS_FROM_LETTER (c)]; 345: break; 346: } 347: 1.1.1.6 ! root 348: if (class == NO_REGS) 1.1 root 349: return; 350: 1.1.1.4 root 351: #else /* REGISTER_CONSTRAINTS */ 352: 353: class = GENERAL_REGS; 354: #endif 355: 356: 1.1 root 357: qty = next_qty++; 358: 359: qty_first_reg[qty] = -1; 360: qty_scratch_rtx[qty] = scratch; 361: qty_size[qty] = GET_MODE_SIZE (GET_MODE (scratch)); 362: qty_mode[qty] = GET_MODE (scratch); 363: qty_birth[qty] = 2 * insn_number - 1; 364: qty_death[qty] = 2 * insn_number + 1; 365: qty_n_calls_crossed[qty] = 0; 366: qty_min_class[qty] = class; 1.1.1.4 root 367: qty_alternate_class[qty] = NO_REGS; 1.1 root 368: qty_n_refs[qty] = 1; 369: } 370: 371: /* Main entry point of this file. */ 372: 373: void 374: local_alloc () 375: { 376: register int b, i; 377: int max_qty; 378: 379: /* Leaf functions and non-leaf functions have different needs. 380: If defined, let the machine say what kind of ordering we 381: should use. */ 382: #ifdef ORDER_REGS_FOR_LOCAL_ALLOC 383: ORDER_REGS_FOR_LOCAL_ALLOC; 384: #endif 385: 386: /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected 387: registers. */ 388: update_equiv_regs (); 389: 390: /* This sets the maximum number of quantities we can have. Quantity 1.1.1.2 root 391: numbers start at zero and we can have one for each pseudo plus the 1.1.1.3 root 392: number of SCRATCHes in the largest block, in the worst case. */ 1.1 root 393: max_qty = (max_regno - FIRST_PSEUDO_REGISTER) + max_scratch; 394: 395: /* Allocate vectors of temporary data. 396: See the declarations of these variables, above, 397: for what they mean. */ 398: 1.1.1.6 ! root 399: /* There can be up to MAX_SCRATCH * N_BASIC_BLOCKS SCRATCHes to allocate. ! 400: Instead of allocating this much memory from now until the end of ! 401: reload, only allocate space for MAX_QTY SCRATCHes. If there are more ! 402: reload will allocate them. */ ! 403: ! 404: scratch_list_length = max_qty; ! 405: scratch_list = (rtx *) xmalloc (scratch_list_length * sizeof (rtx)); ! 406: bzero (scratch_list, scratch_list_length * sizeof (rtx)); ! 407: scratch_block = (int *) xmalloc (scratch_list_length * sizeof (int)); ! 408: bzero (scratch_block, scratch_list_length * sizeof (int)); ! 409: scratch_index = 0; ! 410: 1.1 root 411: qty_phys_reg = (short *) alloca (max_qty * sizeof (short)); 412: qty_phys_copy_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET)); 413: qty_phys_has_copy_sugg = (char *) alloca (max_qty * sizeof (char)); 414: qty_phys_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET)); 415: qty_phys_has_sugg = (char *) alloca (max_qty * sizeof (char)); 416: qty_birth = (int *) alloca (max_qty * sizeof (int)); 417: qty_death = (int *) alloca (max_qty * sizeof (int)); 418: qty_scratch_rtx = (rtx *) alloca (max_qty * sizeof (rtx)); 1.1.1.5 root 419: qty_first_reg = (int *) alloca (max_qty * sizeof (int)); 1.1 root 420: qty_size = (int *) alloca (max_qty * sizeof (int)); 421: qty_mode = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode)); 422: qty_n_calls_crossed = (int *) alloca (max_qty * sizeof (int)); 423: qty_min_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class)); 1.1.1.4 root 424: qty_alternate_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class)); 1.1.1.5 root 425: qty_n_refs = (int *) alloca (max_qty * sizeof (int)); 1.1 root 426: 427: reg_qty = (int *) alloca (max_regno * sizeof (int)); 428: reg_offset = (char *) alloca (max_regno * sizeof (char)); 1.1.1.5 root 429: reg_next_in_qty = (int *) alloca (max_regno * sizeof (int)); 1.1 root 430: 431: reg_renumber = (short *) oballoc (max_regno * sizeof (short)); 432: for (i = 0; i < max_regno; i++) 433: reg_renumber[i] = -1; 434: 435: /* Determine which pseudo-registers can be allocated by local-alloc. 436: In general, these are the registers used only in a single block and 437: which only die once. However, if a register's preferred class has only 1.1.1.5 root 438: a few entries, don't allocate this register here unless it is preferred 1.1 root 439: or nothing since retry_global_alloc won't be able to move it to 440: GENERAL_REGS if a reload register of this class is needed. 441: 442: We need not be concerned with which block actually uses the register 443: since we will never see it outside that block. */ 444: 445: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 446: { 447: if (reg_basic_block[i] >= 0 && reg_n_deaths[i] == 1 1.1.1.4 root 448: && (reg_alternate_class (i) == NO_REGS 1.1.1.5 root 449: || ! CLASS_LIKELY_SPILLED_P (reg_preferred_class (i)))) 1.1 root 450: reg_qty[i] = -2; 451: else 452: reg_qty[i] = -1; 453: } 454: 455: /* Force loop below to initialize entire quantity array. */ 456: next_qty = max_qty; 457: 458: /* Allocate each block's local registers, block by block. */ 459: 460: for (b = 0; b < n_basic_blocks; b++) 461: { 462: /* NEXT_QTY indicates which elements of the `qty_...' 463: vectors might need to be initialized because they were used 464: for the previous block; it is set to the entire array before 465: block 0. Initialize those, with explicit loop if there are few, 466: else with bzero and bcopy. Do not initialize vectors that are 467: explicit set by `alloc_qty'. */ 468: 469: if (next_qty < 6) 470: { 471: for (i = 0; i < next_qty; i++) 472: { 473: qty_scratch_rtx[i] = 0; 474: CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]); 475: qty_phys_has_copy_sugg[i] = 0; 476: CLEAR_HARD_REG_SET (qty_phys_sugg[i]); 477: qty_phys_has_sugg[i] = 0; 478: } 479: } 480: else 481: { 482: #define CLEAR(vector) \ 483: bzero ((vector), (sizeof (*(vector))) * next_qty); 484: 485: CLEAR (qty_scratch_rtx); 486: CLEAR (qty_phys_copy_sugg); 487: CLEAR (qty_phys_has_copy_sugg); 488: CLEAR (qty_phys_sugg); 489: CLEAR (qty_phys_has_sugg); 490: } 491: 492: next_qty = 0; 493: 494: block_alloc (b); 495: #ifdef USE_C_ALLOCA 496: alloca (0); 497: #endif 498: } 499: } 500: 501: /* Depth of loops we are in while in update_equiv_regs. */ 502: static int loop_depth; 503: 504: /* Used for communication between the following two functions: contains 505: a MEM that we wish to ensure remains unchanged. */ 506: static rtx equiv_mem; 507: 508: /* Set nonzero if EQUIV_MEM is modified. */ 509: static int equiv_mem_modified; 510: 511: /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified. 512: Called via note_stores. */ 513: 514: static void 515: validate_equiv_mem_from_store (dest, set) 516: rtx dest; 517: rtx set; 518: { 519: if ((GET_CODE (dest) == REG 520: && reg_overlap_mentioned_p (dest, equiv_mem)) 521: || (GET_CODE (dest) == MEM 522: && true_dependence (dest, equiv_mem))) 523: equiv_mem_modified = 1; 524: } 525: 526: /* Verify that no store between START and the death of REG invalidates 527: MEMREF. MEMREF is invalidated by modifying a register used in MEMREF, 528: by storing into an overlapping memory location, or with a non-const 529: CALL_INSN. 530: 531: Return 1 if MEMREF remains valid. */ 532: 533: static int 534: validate_equiv_mem (start, reg, memref) 535: rtx start; 536: rtx reg; 537: rtx memref; 538: { 539: rtx insn; 540: rtx note; 541: 542: equiv_mem = memref; 543: equiv_mem_modified = 0; 544: 545: /* If the memory reference has side effects or is volatile, it isn't a 546: valid equivalence. */ 547: if (side_effects_p (memref)) 548: return 0; 549: 550: for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn)) 551: { 552: if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') 553: continue; 554: 555: if (find_reg_note (insn, REG_DEAD, reg)) 556: return 1; 557: 558: if (GET_CODE (insn) == CALL_INSN && ! RTX_UNCHANGING_P (memref) 559: && ! CONST_CALL_P (insn)) 560: return 0; 561: 562: note_stores (PATTERN (insn), validate_equiv_mem_from_store); 563: 564: /* If a register mentioned in MEMREF is modified via an 565: auto-increment, we lose the equivalence. Do the same if one 566: dies; although we could extend the life, it doesn't seem worth 567: the trouble. */ 568: 569: for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 570: if ((REG_NOTE_KIND (note) == REG_INC 571: || REG_NOTE_KIND (note) == REG_DEAD) 572: && GET_CODE (XEXP (note, 0)) == REG 573: && reg_overlap_mentioned_p (XEXP (note, 0), memref)) 574: return 0; 575: } 576: 577: return 0; 578: } 579: 580: /* TRUE if X references a memory location that would be affected by a store 581: to MEMREF. */ 582: 583: static int 584: memref_referenced_p (memref, x) 585: rtx x; 586: rtx memref; 587: { 588: int i, j; 589: char *fmt; 590: enum rtx_code code = GET_CODE (x); 591: 592: switch (code) 593: { 594: case REG: 595: case CONST_INT: 596: case CONST: 597: case LABEL_REF: 598: case SYMBOL_REF: 599: case CONST_DOUBLE: 600: case PC: 601: case CC0: 602: case HIGH: 603: case LO_SUM: 604: return 0; 605: 606: case MEM: 607: if (true_dependence (memref, x)) 608: return 1; 609: break; 610: 611: case SET: 612: /* If we are setting a MEM, it doesn't count (its address does), but any 613: other SET_DEST that has a MEM in it is referencing the MEM. */ 614: if (GET_CODE (SET_DEST (x)) == MEM) 615: { 616: if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0))) 617: return 1; 618: } 619: else if (memref_referenced_p (memref, SET_DEST (x))) 620: return 1; 621: 622: return memref_referenced_p (memref, SET_SRC (x)); 623: } 624: 625: fmt = GET_RTX_FORMAT (code); 626: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 627: switch (fmt[i]) 628: { 629: case 'e': 630: if (memref_referenced_p (memref, XEXP (x, i))) 631: return 1; 632: break; 633: case 'E': 634: for (j = XVECLEN (x, i) - 1; j >= 0; j--) 635: if (memref_referenced_p (memref, XVECEXP (x, i, j))) 636: return 1; 637: break; 638: } 639: 640: return 0; 641: } 642: 643: /* TRUE if some insn in the range (START, END] references a memory location 644: that would be affected by a store to MEMREF. */ 645: 646: static int 647: memref_used_between_p (memref, start, end) 648: rtx memref; 649: rtx start; 650: rtx end; 651: { 652: rtx insn; 653: 654: for (insn = NEXT_INSN (start); insn != NEXT_INSN (end); 655: insn = NEXT_INSN (insn)) 656: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' 657: && memref_referenced_p (memref, PATTERN (insn))) 658: return 1; 659: 660: return 0; 661: } 662: 663: /* INSN is a copy from SRC to DEST, both registers, and SRC does not die 664: in INSN. 665: 666: Search forward to see if SRC dies before either it or DEST is modified, 667: but don't scan past the end of a basic block. If so, we can replace SRC 668: with DEST and let SRC die in INSN. 669: 670: This will reduce the number of registers live in that range and may enable 671: DEST to be tied to SRC, thus often saving one register in addition to a 672: register-register copy. */ 673: 674: static void 1.1.1.2 root 675: optimize_reg_copy_1 (insn, dest, src) 1.1 root 676: rtx insn; 677: rtx dest; 678: rtx src; 679: { 680: rtx p, q; 681: rtx note; 682: rtx dest_death = 0; 683: int sregno = REGNO (src); 684: int dregno = REGNO (dest); 685: 686: if (sregno == dregno 687: #ifdef SMALL_REGISTER_CLASSES 688: /* We don't want to mess with hard regs if register classes are small. */ 689: || sregno < FIRST_PSEUDO_REGISTER || dregno < FIRST_PSEUDO_REGISTER 690: #endif 691: /* We don't see all updates to SP if they are in an auto-inc memory 692: reference, so we must disallow this optimization on them. */ 693: || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM) 694: return; 695: 696: for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 697: { 698: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN 699: || (GET_CODE (p) == NOTE 700: && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG 701: || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END))) 702: break; 703: 704: if (GET_RTX_CLASS (GET_CODE (p)) != 'i') 705: continue; 706: 707: if (reg_set_p (src, p) || reg_set_p (dest, p) 708: /* Don't change a USE of a register. */ 709: || (GET_CODE (PATTERN (p)) == USE 710: && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0)))) 711: break; 712: 1.1.1.4 root 713: /* See if all of SRC dies in P. This test is slightly more 714: conservative than it needs to be. */ 715: if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0 716: && GET_MODE (XEXP (note, 0)) == GET_MODE (src)) 1.1 root 717: { 718: int failed = 0; 719: int length = 0; 1.1.1.4 root 720: int d_length = 0; 1.1 root 721: int n_calls = 0; 1.1.1.4 root 722: int d_n_calls = 0; 723: 1.1 root 724: /* We can do the optimization. Scan forward from INSN again, 725: replacing regs as we go. Set FAILED if a replacement can't 726: be done. In that case, we can't move the death note for SRC. 727: This should be rare. */ 728: 729: /* Set to stop at next insn. */ 730: for (q = next_real_insn (insn); 731: q != next_real_insn (p); 732: q = next_real_insn (q)) 733: { 1.1.1.4 root 734: if (reg_overlap_mentioned_p (src, PATTERN (q))) 1.1 root 735: { 1.1.1.4 root 736: /* If SRC is a hard register, we might miss some 737: overlapping registers with validate_replace_rtx, 738: so we would have to undo it. We can't if DEST is 739: present in the insn, so fail in that combination 740: of cases. */ 741: if (sregno < FIRST_PSEUDO_REGISTER 742: && reg_mentioned_p (dest, PATTERN (q))) 743: failed = 1; 744: 745: /* Replace all uses and make sure that the register 746: isn't still present. */ 747: else if (validate_replace_rtx (src, dest, q) 748: && (sregno >= FIRST_PSEUDO_REGISTER 749: || ! reg_overlap_mentioned_p (src, 750: PATTERN (q)))) 1.1 root 751: { 752: /* We assume that a register is used exactly once per 753: insn in the updates below. If this is not correct, 754: no great harm is done. */ 755: if (sregno >= FIRST_PSEUDO_REGISTER) 756: reg_n_refs[sregno] -= loop_depth; 757: if (dregno >= FIRST_PSEUDO_REGISTER) 758: reg_n_refs[dregno] += loop_depth; 759: } 760: else 1.1.1.4 root 761: { 762: validate_replace_rtx (dest, src, q); 763: failed = 1; 764: } 1.1 root 765: } 766: 767: /* Count the insns and CALL_INSNs passed. If we passed the 768: death note of DEST, show increased live length. */ 769: length++; 770: if (dest_death) 1.1.1.4 root 771: d_length++; 1.1 root 772: 773: if (GET_CODE (q) == CALL_INSN) 774: { 775: n_calls++; 776: if (dest_death) 1.1.1.4 root 777: d_n_calls++; 1.1 root 778: } 779: 780: /* If DEST dies here, remove the death note and save it for 1.1.1.4 root 781: later. Make sure ALL of DEST dies here; again, this is 782: overly conservative. */ 1.1 root 783: if (dest_death == 0 1.1.1.4 root 784: && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0 785: && GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest)) 1.1 root 786: remove_note (q, dest_death); 787: } 788: 789: if (! failed) 790: { 791: if (sregno >= FIRST_PSEUDO_REGISTER) 792: { 793: reg_live_length[sregno] -= length; 794: reg_n_calls_crossed[sregno] -= n_calls; 795: } 796: 1.1.1.4 root 797: if (dregno >= FIRST_PSEUDO_REGISTER) 798: { 799: reg_live_length[dregno] += d_length; 800: reg_n_calls_crossed[dregno] += d_n_calls; 801: } 802: 1.1 root 803: /* Move death note of SRC from P to INSN. */ 804: remove_note (p, note); 805: XEXP (note, 1) = REG_NOTES (insn); 806: REG_NOTES (insn) = note; 807: } 808: 809: /* Put death note of DEST on P if we saw it die. */ 810: if (dest_death) 811: { 812: XEXP (dest_death, 1) = REG_NOTES (p); 813: REG_NOTES (p) = dest_death; 814: } 815: 816: return; 817: } 1.1.1.4 root 818: 819: /* If SRC is a hard register which is set or killed in some other 820: way, we can't do this optimization. */ 821: else if (sregno < FIRST_PSEUDO_REGISTER 822: && dead_or_set_p (p, src)) 823: break; 1.1 root 824: } 825: } 1.1.1.2 root 826: 827: /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have 828: a sequence of insns that modify DEST followed by an insn that sets 829: SRC to DEST in which DEST dies, with no prior modification of DEST. 830: (There is no need to check if the insns in between actually modify 831: DEST. We should not have cases where DEST is not modified, but 832: the optimization is safe if no such modification is detected.) 833: In that case, we can replace all uses of DEST, starting with INSN and 834: ending with the set of SRC to DEST, with SRC. We do not do this 835: optimization if a CALL_INSN is crossed unless SRC already crosses a 836: call. 837: 838: It is assumed that DEST and SRC are pseudos; it is too complicated to do 839: this for hard registers since the substitutions we may make might fail. */ 840: 841: static void 842: optimize_reg_copy_2 (insn, dest, src) 843: rtx insn; 844: rtx dest; 845: rtx src; 846: { 847: rtx p, q; 848: rtx set; 849: int sregno = REGNO (src); 850: int dregno = REGNO (dest); 851: 852: for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 853: { 854: if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN 855: || (GET_CODE (p) == NOTE 856: && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG 857: || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END))) 858: break; 859: 860: if (GET_RTX_CLASS (GET_CODE (p)) != 'i') 861: continue; 862: 863: set = single_set (p); 864: if (set && SET_SRC (set) == dest && SET_DEST (set) == src 865: && find_reg_note (p, REG_DEAD, dest)) 866: { 867: /* We can do the optimization. Scan forward from INSN again, 868: replacing regs as we go. */ 869: 870: /* Set to stop at next insn. */ 871: for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q)) 872: if (GET_RTX_CLASS (GET_CODE (q)) == 'i') 873: { 874: if (reg_mentioned_p (dest, PATTERN (q))) 875: { 876: PATTERN (q) = replace_rtx (PATTERN (q), dest, src); 877: 878: /* We assume that a register is used exactly once per 879: insn in the updates below. If this is not correct, 880: no great harm is done. */ 1.1.1.4 root 881: reg_n_refs[dregno] -= loop_depth; 882: reg_n_refs[sregno] += loop_depth; 1.1.1.2 root 883: } 884: 885: 886: if (GET_CODE (q) == CALL_INSN) 887: { 888: reg_n_calls_crossed[dregno]--; 889: reg_n_calls_crossed[sregno]++; 890: } 891: } 892: 893: remove_note (p, find_reg_note (p, REG_DEAD, dest)); 894: reg_n_deaths[dregno]--; 895: remove_note (insn, find_reg_note (insn, REG_DEAD, src)); 896: reg_n_deaths[sregno]--; 897: return; 898: } 899: 900: if (reg_set_p (src, p) 901: || (GET_CODE (p) == CALL_INSN && reg_n_calls_crossed[sregno] == 0)) 902: break; 903: } 904: } 1.1 root 905: 906: /* Find registers that are equivalent to a single value throughout the 907: compilation (either because they can be referenced in memory or are set once 908: from a single constant). Lower their priority for a register. 909: 910: If such a register is only referenced once, try substituting its value 911: into the using insn. If it succeeds, we can eliminate the register 912: completely. */ 913: 914: static void 915: update_equiv_regs () 916: { 917: rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *)); 918: rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *)); 919: rtx insn; 920: 921: bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *)); 922: bzero (reg_equiv_replacement, max_regno * sizeof (rtx *)); 923: 924: init_alias_analysis (); 925: 926: loop_depth = 1; 927: 928: /* Scan the insns and find which registers have equivalences. Do this 929: in a separate scan of the insns because (due to -fcse-follow-jumps) 930: a register can be set below its use. */ 931: for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 932: { 933: rtx note; 934: rtx set = single_set (insn); 935: rtx dest; 936: int regno; 937: 938: if (GET_CODE (insn) == NOTE) 939: { 940: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 941: loop_depth++; 942: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 943: loop_depth--; 944: } 945: 946: /* If this insn contains more (or less) than a single SET, ignore it. */ 947: if (set == 0) 948: continue; 949: 950: dest = SET_DEST (set); 951: 952: /* If this sets a MEM to the contents of a REG that is only used 953: in a single basic block, see if the register is always equivalent 954: to that memory location and if moving the store from INSN to the 955: insn that set REG is safe. If so, put a REG_EQUIV note on the 956: initializing insn. */ 957: 958: if (GET_CODE (dest) == MEM && GET_CODE (SET_SRC (set)) == REG 959: && (regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER 960: && reg_basic_block[regno] >= 0 961: && reg_equiv_init_insn[regno] != 0 962: && validate_equiv_mem (reg_equiv_init_insn[regno], SET_SRC (set), 963: dest) 964: && ! memref_used_between_p (SET_DEST (set), 965: reg_equiv_init_insn[regno], insn)) 966: REG_NOTES (reg_equiv_init_insn[regno]) 967: = gen_rtx (EXPR_LIST, REG_EQUIV, dest, 968: REG_NOTES (reg_equiv_init_insn[regno])); 969: 970: /* If this is a register-register copy where SRC is not dead, see if we 971: can optimize it. */ 972: if (flag_expensive_optimizations && GET_CODE (dest) == REG 973: && GET_CODE (SET_SRC (set)) == REG 974: && ! find_reg_note (insn, REG_DEAD, SET_SRC (set))) 1.1.1.2 root 975: optimize_reg_copy_1 (insn, dest, SET_SRC (set)); 976: 977: /* Similarly for a pseudo-pseudo copy when SRC is dead. */ 978: else if (flag_expensive_optimizations && GET_CODE (dest) == REG 979: && REGNO (dest) >= FIRST_PSEUDO_REGISTER 980: && GET_CODE (SET_SRC (set)) == REG 981: && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER 982: && find_reg_note (insn, REG_DEAD, SET_SRC (set))) 983: optimize_reg_copy_2 (insn, dest, SET_SRC (set)); 1.1 root 984: 985: /* Otherwise, we only handle the case of a pseudo register being set 986: once. */ 987: if (GET_CODE (dest) != REG 988: || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER 989: || reg_n_sets[regno] != 1) 990: continue; 991: 1.1.1.4 root 992: note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 1.1 root 993: 994: /* Record this insn as initializing this register. */ 995: reg_equiv_init_insn[regno] = insn; 996: 997: /* If this register is known to be equal to a constant, record that 998: it is always equivalent to the constant. */ 999: if (note && CONSTANT_P (XEXP (note, 0))) 1000: PUT_MODE (note, (enum machine_mode) REG_EQUIV); 1001: 1002: /* If this insn introduces a "constant" register, decrease the priority 1003: of that register. Record this insn if the register is only used once 1004: more and the equivalence value is the same as our source. 1005: 1006: The latter condition is checked for two reasons: First, it is an 1007: indication that it may be more efficient to actually emit the insn 1008: as written (if no registers are available, reload will substitute 1009: the equivalence). Secondly, it avoids problems with any registers 1010: dying in this insn whose death notes would be missed. 1011: 1012: If we don't have a REG_EQUIV note, see if this insn is loading 1013: a register used only in one basic block from a MEM. If so, and the 1014: MEM remains unchanged for the life of the register, add a REG_EQUIV 1015: note. */ 1016: 1.1.1.4 root 1017: note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 1.1 root 1018: 1019: if (note == 0 && reg_basic_block[regno] >= 0 1020: && GET_CODE (SET_SRC (set)) == MEM 1021: && validate_equiv_mem (insn, dest, SET_SRC (set))) 1022: REG_NOTES (insn) = note = gen_rtx (EXPR_LIST, REG_EQUIV, SET_SRC (set), 1023: REG_NOTES (insn)); 1024: 1025: /* Don't mess with things live during setjmp. */ 1026: if (note && reg_live_length[regno] >= 0) 1027: { 1028: int regno = REGNO (dest); 1029: 1030: /* Note that the statement below does not affect the priority 1031: in local-alloc! */ 1032: reg_live_length[regno] *= 2; 1033: 1034: /* If the register is referenced exactly twice, meaning it is set 1035: once and used once, indicate that the reference may be replaced 1036: by the equivalence we computed above. If the register is only 1037: used in one basic block, this can't succeed or combine would 1038: have done it. 1039: 1040: It would be nice to use "loop_depth * 2" in the compare 1041: below. Unfortunately, LOOP_DEPTH need not be constant within 1042: a basic block so this would be too complicated. 1043: 1044: This case normally occurs when a parameter is read from memory 1045: and then used exactly once, not in a loop. */ 1046: 1047: if (reg_n_refs[regno] == 2 1048: && reg_basic_block[regno] < 0 1049: && rtx_equal_p (XEXP (note, 0), SET_SRC (set))) 1050: reg_equiv_replacement[regno] = SET_SRC (set); 1051: } 1052: } 1053: 1054: /* Now scan all regs killed in an insn to see if any of them are registers 1055: only used that once. If so, see if we can replace the reference with 1056: the equivalent from. If we can, delete the initializing reference 1057: and this register will go away. */ 1058: for (insn = next_active_insn (get_insns ()); 1059: insn; 1060: insn = next_active_insn (insn)) 1061: { 1062: rtx link; 1063: 1064: for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1065: if (REG_NOTE_KIND (link) == REG_DEAD 1066: /* Make sure this insn still refers to the register. */ 1067: && reg_mentioned_p (XEXP (link, 0), PATTERN (insn))) 1068: { 1069: int regno = REGNO (XEXP (link, 0)); 1070: 1071: if (reg_equiv_replacement[regno] 1072: && validate_replace_rtx (regno_reg_rtx[regno], 1073: reg_equiv_replacement[regno], insn)) 1074: { 1075: rtx equiv_insn = reg_equiv_init_insn[regno]; 1076: 1077: remove_death (regno, insn); 1078: reg_n_refs[regno] = 0; 1079: PUT_CODE (equiv_insn, NOTE); 1080: NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED; 1081: NOTE_SOURCE_FILE (equiv_insn) = 0; 1082: } 1083: } 1084: } 1085: } 1086: 1087: /* Allocate hard regs to the pseudo regs used only within block number B. 1088: Only the pseudos that die but once can be handled. */ 1089: 1090: static void 1091: block_alloc (b) 1092: int b; 1093: { 1094: register int i, q; 1095: register rtx insn; 1096: rtx note; 1097: int insn_number = 0; 1098: int insn_count = 0; 1099: int max_uid = get_max_uid (); 1.1.1.5 root 1100: int *qty_order; 1.1 root 1101: int no_conflict_combined_regno = -1; 1.1.1.6 ! root 1102: /* Counter to prevent allocating more SCRATCHes than can be stored ! 1103: in SCRATCH_LIST. */ ! 1104: int scratches_allocated = scratch_index; 1.1 root 1105: 1106: /* Count the instructions in the basic block. */ 1107: 1108: insn = basic_block_end[b]; 1109: while (1) 1110: { 1111: if (GET_CODE (insn) != NOTE) 1112: if (++insn_count > max_uid) 1113: abort (); 1114: if (insn == basic_block_head[b]) 1115: break; 1116: insn = PREV_INSN (insn); 1117: } 1118: 1119: /* +2 to leave room for a post_mark_life at the last insn and for 1120: the birth of a CLOBBER in the first insn. */ 1121: regs_live_at = (HARD_REG_SET *) alloca ((2 * insn_count + 2) 1122: * sizeof (HARD_REG_SET)); 1123: bzero (regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET)); 1124: 1125: /* Initialize table of hardware registers currently live. */ 1126: 1127: #ifdef HARD_REG_SET 1128: regs_live = *basic_block_live_at_start[b]; 1129: #else 1130: COPY_HARD_REG_SET (regs_live, basic_block_live_at_start[b]); 1131: #endif 1132: 1133: /* This loop scans the instructions of the basic block 1134: and assigns quantities to registers. 1135: It computes which registers to tie. */ 1136: 1137: insn = basic_block_head[b]; 1138: while (1) 1139: { 1140: register rtx body = PATTERN (insn); 1141: 1142: if (GET_CODE (insn) != NOTE) 1143: insn_number++; 1144: 1145: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') 1146: { 1147: register rtx link, set; 1148: register int win = 0; 1149: register rtx r0, r1; 1150: int combined_regno = -1; 1151: int i; 1152: int insn_code_number = recog_memoized (insn); 1153: 1154: this_insn_number = insn_number; 1155: this_insn = insn; 1156: 1157: if (insn_code_number >= 0) 1158: insn_extract (insn); 1159: which_alternative = -1; 1160: 1161: /* Is this insn suitable for tying two registers? 1162: If so, try doing that. 1163: Suitable insns are those with at least two operands and where 1164: operand 0 is an output that is a register that is not 1165: earlyclobber. 1.1.1.5 root 1166: 1167: We can tie operand 0 with some operand that dies in this insn. 1168: First look for operands that are required to be in the same 1169: register as operand 0. If we find such, only try tying that 1170: operand or one that can be put into that operand if the 1171: operation is commutative. If we don't find an operand 1172: that is required to be in the same register as operand 0, 1173: we can tie with any operand. 1174: 1.1 root 1175: Subregs in place of regs are also ok. 1176: 1177: If tying is done, WIN is set nonzero. */ 1178: 1179: if (insn_code_number >= 0 1.1.1.4 root 1180: #ifdef REGISTER_CONSTRAINTS 1.1 root 1181: && insn_n_operands[insn_code_number] > 1 1182: && insn_operand_constraint[insn_code_number][0][0] == '=' 1.1.1.4 root 1183: && insn_operand_constraint[insn_code_number][0][1] != '&' 1184: #else 1185: && GET_CODE (PATTERN (insn)) == SET 1186: && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0]) 1187: #endif 1188: ) 1.1 root 1189: { 1.1.1.4 root 1190: #ifdef REGISTER_CONSTRAINTS 1.1.1.5 root 1191: int must_match_0 = -1; 1192: 1193: 1194: for (i = 1; i < insn_n_operands[insn_code_number]; i++) 1195: if (requires_inout_p 1196: (insn_operand_constraint[insn_code_number][i])) 1197: must_match_0 = i; 1.1.1.4 root 1198: #endif 1.1 root 1199: 1.1.1.5 root 1200: r0 = recog_operand[0]; 1201: for (i = 1; i < insn_n_operands[insn_code_number]; i++) 1.1 root 1202: { 1.1.1.4 root 1203: #ifdef REGISTER_CONSTRAINTS 1.1.1.5 root 1204: /* Skip this operand if we found an operand that 1205: must match operand 0 and this operand isn't it 1206: and can't be made to be it by commutativity. */ 1207: 1208: if (must_match_0 >= 0 && i != must_match_0 1209: && ! (i == must_match_0 + 1 1210: && insn_operand_constraint[insn_code_number][i-1][0] == '%') 1211: && ! (i == must_match_0 - 1 1212: && insn_operand_constraint[insn_code_number][i][0] == '%')) 1213: continue; 1.1.1.4 root 1214: #endif 1.1 root 1215: 1.1.1.5 root 1216: r1 = recog_operand[i]; 1.1 root 1217: 1.1.1.5 root 1218: /* If the operand is an address, find a register in it. 1219: There may be more than one register, but we only try one 1220: of them. */ 1221: if ( 1.1.1.4 root 1222: #ifdef REGISTER_CONSTRAINTS 1.1.1.5 root 1223: insn_operand_constraint[insn_code_number][i][0] == 'p' 1.1.1.4 root 1224: #else 1.1.1.5 root 1225: insn_operand_address_p[insn_code_number][i] 1226: #endif 1227: ) 1228: while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT) 1229: r1 = XEXP (r1, 0); 1230: 1231: if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG) 1232: { 1233: /* We have two priorities for hard register preferences. 1234: If we have a move insn or an insn whose first input 1235: can only be in the same register as the output, give 1236: priority to an equivalence found from that insn. */ 1237: int may_save_copy 1238: = ((SET_DEST (body) == r0 && SET_SRC (body) == r1) 1239: #ifdef REGISTER_CONSTRAINTS 1240: || (r1 == recog_operand[i] && must_match_0 >= 0) 1.1.1.4 root 1241: #endif 1.1.1.5 root 1242: ); 1243: 1244: if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG) 1245: win = combine_regs (r1, r0, may_save_copy, 1246: insn_number, insn, 0); 1247: } 1.1 root 1248: } 1249: } 1250: 1251: /* Recognize an insn sequence with an ultimate result 1252: which can safely overlap one of the inputs. 1253: The sequence begins with a CLOBBER of its result, 1254: and ends with an insn that copies the result to itself 1255: and has a REG_EQUAL note for an equivalent formula. 1256: That note indicates what the inputs are. 1257: The result and the input can overlap if each insn in 1258: the sequence either doesn't mention the input 1259: or has a REG_NO_CONFLICT note to inhibit the conflict. 1260: 1261: We do the combining test at the CLOBBER so that the 1262: destination register won't have had a quantity number 1263: assigned, since that would prevent combining. */ 1264: 1265: if (GET_CODE (PATTERN (insn)) == CLOBBER 1266: && (r0 = XEXP (PATTERN (insn), 0), 1267: GET_CODE (r0) == REG) 1.1.1.4 root 1268: && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 1.1.1.5 root 1269: && XEXP (link, 0) != 0 1.1 root 1270: && GET_CODE (XEXP (link, 0)) == INSN 1271: && (set = single_set (XEXP (link, 0))) != 0 1272: && SET_DEST (set) == r0 && SET_SRC (set) == r0 1.1.1.4 root 1273: && (note = find_reg_note (XEXP (link, 0), REG_EQUAL, 1274: NULL_RTX)) != 0) 1.1 root 1275: { 1276: if (r1 = XEXP (note, 0), GET_CODE (r1) == REG 1277: /* Check that we have such a sequence. */ 1278: && no_conflict_p (insn, r0, r1)) 1279: win = combine_regs (r1, r0, 1, insn_number, insn, 1); 1280: else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e' 1281: && (r1 = XEXP (XEXP (note, 0), 0), 1282: GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG) 1283: && no_conflict_p (insn, r0, r1)) 1284: win = combine_regs (r1, r0, 0, insn_number, insn, 1); 1285: 1286: /* Here we care if the operation to be computed is 1287: commutative. */ 1288: else if ((GET_CODE (XEXP (note, 0)) == EQ 1289: || GET_CODE (XEXP (note, 0)) == NE 1290: || GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c') 1291: && (r1 = XEXP (XEXP (note, 0), 1), 1292: (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)) 1293: && no_conflict_p (insn, r0, r1)) 1294: win = combine_regs (r1, r0, 0, insn_number, insn, 1); 1295: 1296: /* If we did combine something, show the register number 1297: in question so that we know to ignore its death. */ 1298: if (win) 1299: no_conflict_combined_regno = REGNO (r1); 1300: } 1301: 1302: /* If registers were just tied, set COMBINED_REGNO 1303: to the number of the register used in this insn 1304: that was tied to the register set in this insn. 1305: This register's qty should not be "killed". */ 1306: 1307: if (win) 1308: { 1309: while (GET_CODE (r1) == SUBREG) 1310: r1 = SUBREG_REG (r1); 1311: combined_regno = REGNO (r1); 1312: } 1313: 1314: /* Mark the death of everything that dies in this instruction, 1315: except for anything that was just combined. */ 1316: 1317: for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1318: if (REG_NOTE_KIND (link) == REG_DEAD 1319: && GET_CODE (XEXP (link, 0)) == REG 1320: && combined_regno != REGNO (XEXP (link, 0)) 1321: && (no_conflict_combined_regno != REGNO (XEXP (link, 0)) 1322: || ! find_reg_note (insn, REG_NO_CONFLICT, XEXP (link, 0)))) 1323: wipe_dead_reg (XEXP (link, 0), 0); 1324: 1325: /* Allocate qty numbers for all registers local to this block 1326: that are born (set) in this instruction. 1327: A pseudo that already has a qty is not changed. */ 1328: 1329: note_stores (PATTERN (insn), reg_is_set); 1330: 1331: /* If anything is set in this insn and then unused, mark it as dying 1332: after this insn, so it will conflict with our outputs. This 1333: can't match with something that combined, and it doesn't matter 1334: if it did. Do this after the calls to reg_is_set since these 1335: die after, not during, the current insn. */ 1336: 1337: for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 1338: if (REG_NOTE_KIND (link) == REG_UNUSED 1339: && GET_CODE (XEXP (link, 0)) == REG) 1340: wipe_dead_reg (XEXP (link, 0), 1); 1341: 1.1.1.6 ! root 1342: /* Allocate quantities for any SCRATCH operands of this insn. */ 1.1 root 1343: 1344: if (insn_code_number >= 0) 1345: for (i = 0; i < insn_n_operands[insn_code_number]; i++) 1.1.1.6 ! root 1346: if (GET_CODE (recog_operand[i]) == SCRATCH ! 1347: && scratches_allocated++ < scratch_list_length) 1.1 root 1348: alloc_qty_for_scratch (recog_operand[i], i, insn, 1349: insn_code_number, insn_number); 1350: 1351: /* If this is an insn that has a REG_RETVAL note pointing at a 1352: CLOBBER insn, we have reached the end of a REG_NO_CONFLICT 1353: block, so clear any register number that combined within it. */ 1.1.1.4 root 1354: if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0 1.1 root 1355: && GET_CODE (XEXP (note, 0)) == INSN 1356: && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER) 1357: no_conflict_combined_regno = -1; 1358: } 1359: 1360: /* Set the registers live after INSN_NUMBER. Note that we never 1361: record the registers live before the block's first insn, since no 1362: pseudos we care about are live before that insn. */ 1363: 1364: IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live); 1365: IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live); 1366: 1367: if (insn == basic_block_end[b]) 1368: break; 1369: 1370: insn = NEXT_INSN (insn); 1371: } 1372: 1373: /* Now every register that is local to this basic block 1374: should have been given a quantity, or else -1 meaning ignore it. 1375: Every quantity should have a known birth and death. 1376: 1377: Order the qtys so we assign them registers in order of 1378: decreasing length of life. Normally call qsort, but if we 1379: have only a very small number of quantities, sort them ourselves. */ 1380: 1.1.1.5 root 1381: qty_order = (int *) alloca (next_qty * sizeof (int)); 1.1 root 1382: for (i = 0; i < next_qty; i++) 1383: qty_order[i] = i; 1384: 1385: #define EXCHANGE(I1, I2) \ 1386: { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; } 1387: 1388: switch (next_qty) 1389: { 1390: case 3: 1391: /* Make qty_order[2] be the one to allocate last. */ 1392: if (qty_compare (0, 1) > 0) 1393: EXCHANGE (0, 1); 1394: if (qty_compare (1, 2) > 0) 1395: EXCHANGE (2, 1); 1396: 1397: /* ... Fall through ... */ 1398: case 2: 1399: /* Put the best one to allocate in qty_order[0]. */ 1400: if (qty_compare (0, 1) > 0) 1401: EXCHANGE (0, 1); 1402: 1403: /* ... Fall through ... */ 1404: 1405: case 1: 1406: case 0: 1407: /* Nothing to do here. */ 1408: break; 1409: 1410: default: 1.1.1.5 root 1411: qsort (qty_order, next_qty, sizeof (int), qty_compare_1); 1.1 root 1412: } 1413: 1414: /* Try to put each quantity in a suggested physical register, if it has one. 1415: This may cause registers to be allocated that otherwise wouldn't be, but 1416: this seems acceptable in local allocation (unlike global allocation). */ 1417: for (i = 0; i < next_qty; i++) 1418: { 1419: q = qty_order[i]; 1420: if (qty_phys_has_sugg[q] || qty_phys_has_copy_sugg[q]) 1421: qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q, 1422: 0, 1, qty_birth[q], qty_death[q]); 1423: else 1424: qty_phys_reg[q] = -1; 1425: } 1426: 1427: /* Now for each qty that is not a hardware register, 1428: look for a hardware register to put it in. 1429: First try the register class that is cheapest for this qty, 1430: if there is more than one class. */ 1431: 1432: for (i = 0; i < next_qty; i++) 1433: { 1434: q = qty_order[i]; 1435: if (qty_phys_reg[q] < 0) 1436: { 1437: if (N_REG_CLASSES > 1) 1438: { 1439: qty_phys_reg[q] = find_free_reg (qty_min_class[q], 1440: qty_mode[q], q, 0, 0, 1441: qty_birth[q], qty_death[q]); 1442: if (qty_phys_reg[q] >= 0) 1443: continue; 1444: } 1445: 1.1.1.4 root 1446: if (qty_alternate_class[q] != NO_REGS) 1447: qty_phys_reg[q] = find_free_reg (qty_alternate_class[q], 1.1 root 1448: qty_mode[q], q, 0, 0, 1449: qty_birth[q], qty_death[q]); 1450: } 1451: } 1452: 1453: /* Now propagate the register assignments 1454: to the pseudo regs belonging to the qtys. */ 1455: 1456: for (q = 0; q < next_qty; q++) 1457: if (qty_phys_reg[q] >= 0) 1458: { 1459: for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i]) 1460: reg_renumber[i] = qty_phys_reg[q] + reg_offset[i]; 1461: if (qty_scratch_rtx[q]) 1462: { 1.1.1.6 ! root 1463: if (GET_CODE (qty_scratch_rtx[q]) == REG) ! 1464: abort (); 1.1 root 1465: PUT_CODE (qty_scratch_rtx[q], REG); 1466: REGNO (qty_scratch_rtx[q]) = qty_phys_reg[q]; 1467: 1.1.1.6 ! root 1468: scratch_block[scratch_index] = b; ! 1469: scratch_list[scratch_index++] = qty_scratch_rtx[q]; 1.1 root 1470: 1471: /* Must clear the USED field, because it will have been set by 1472: copy_rtx_if_shared, but the leaf_register code expects that 1473: it is zero in all REG rtx. copy_rtx_if_shared does not set the 1474: used bit for REGs, but does for SCRATCHes. */ 1475: qty_scratch_rtx[q]->used = 0; 1476: } 1477: } 1478: } 1479: 1480: /* Compare two quantities' priority for getting real registers. 1481: We give shorter-lived quantities higher priority. 1.1.1.3 root 1482: Quantities with more references are also preferred, as are quantities that 1483: require multiple registers. This is the identical prioritization as 1.1 root 1484: done by global-alloc. 1485: 1486: We used to give preference to registers with *longer* lives, but using 1487: the same algorithm in both local- and global-alloc can speed up execution 1488: of some programs by as much as a factor of three! */ 1489: 1490: static int 1491: qty_compare (q1, q2) 1492: int q1, q2; 1493: { 1494: /* Note that the quotient will never be bigger than 1495: the value of floor_log2 times the maximum number of 1496: times a register can occur in one insn (surely less than 100). 1497: Multiplying this by 10000 can't overflow. */ 1498: register int pri1 1499: = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1]) 1500: / ((qty_death[q1] - qty_birth[q1]) * qty_size[q1])) 1501: * 10000); 1502: register int pri2 1503: = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2]) 1504: / ((qty_death[q2] - qty_birth[q2]) * qty_size[q2])) 1505: * 10000); 1506: return pri2 - pri1; 1507: } 1508: 1509: static int 1510: qty_compare_1 (q1, q2) 1.1.1.5 root 1511: int *q1, *q2; 1.1 root 1512: { 1513: register int tem; 1514: 1515: /* Note that the quotient will never be bigger than 1516: the value of floor_log2 times the maximum number of 1517: times a register can occur in one insn (surely less than 100). 1518: Multiplying this by 10000 can't overflow. */ 1519: register int pri1 1520: = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1]) 1521: / ((qty_death[*q1] - qty_birth[*q1]) * qty_size[*q1])) 1522: * 10000); 1523: register int pri2 1524: = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2]) 1525: / ((qty_death[*q2] - qty_birth[*q2]) * qty_size[*q2])) 1526: * 10000); 1527: 1528: tem = pri2 - pri1; 1529: if (tem != 0) return tem; 1530: /* If qtys are equally good, sort by qty number, 1531: so that the results of qsort leave nothing to chance. */ 1532: return *q1 - *q2; 1533: } 1534: 1535: /* Attempt to combine the two registers (rtx's) USEDREG and SETREG. 1536: Returns 1 if have done so, or 0 if cannot. 1537: 1538: Combining registers means marking them as having the same quantity 1539: and adjusting the offsets within the quantity if either of 1540: them is a SUBREG). 1541: 1542: We don't actually combine a hard reg with a pseudo; instead 1543: we just record the hard reg as the suggestion for the pseudo's quantity. 1544: If we really combined them, we could lose if the pseudo lives 1545: across an insn that clobbers the hard reg (eg, movstr). 1546: 1547: ALREADY_DEAD is non-zero if USEDREG is known to be dead even though 1548: there is no REG_DEAD note on INSN. This occurs during the processing 1549: of REG_NO_CONFLICT blocks. 1550: 1551: MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to 1552: SETREG or if the input and output must share a register. 1553: In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG. 1554: 1555: There are elaborate checks for the validity of combining. */ 1556: 1557: 1558: static int 1559: combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead) 1560: rtx usedreg, setreg; 1561: int may_save_copy; 1562: int insn_number; 1563: rtx insn; 1564: int already_dead; 1565: { 1566: register int ureg, sreg; 1567: register int offset = 0; 1568: int usize, ssize; 1569: register int sqty; 1570: 1571: /* Determine the numbers and sizes of registers being used. If a subreg 1.1.1.3 root 1572: is present that does not change the entire register, don't consider 1.1 root 1573: this a copy insn. */ 1574: 1575: while (GET_CODE (usedreg) == SUBREG) 1576: { 1577: if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD) 1578: may_save_copy = 0; 1579: offset += SUBREG_WORD (usedreg); 1580: usedreg = SUBREG_REG (usedreg); 1581: } 1582: if (GET_CODE (usedreg) != REG) 1583: return 0; 1584: ureg = REGNO (usedreg); 1585: usize = REG_SIZE (usedreg); 1586: 1587: while (GET_CODE (setreg) == SUBREG) 1588: { 1589: if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD) 1590: may_save_copy = 0; 1591: offset -= SUBREG_WORD (setreg); 1592: setreg = SUBREG_REG (setreg); 1593: } 1594: if (GET_CODE (setreg) != REG) 1595: return 0; 1596: sreg = REGNO (setreg); 1597: ssize = REG_SIZE (setreg); 1598: 1599: /* If UREG is a pseudo-register that hasn't already been assigned a 1600: quantity number, it means that it is not local to this block or dies 1601: more than once. In either event, we can't do anything with it. */ 1602: if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0) 1603: /* Do not combine registers unless one fits within the other. */ 1604: || (offset > 0 && usize + offset > ssize) 1605: || (offset < 0 && usize + offset < ssize) 1606: /* Do not combine with a smaller already-assigned object 1607: if that smaller object is already combined with something bigger. */ 1608: || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER 1609: && usize < qty_size[reg_qty[ureg]]) 1610: /* Can't combine if SREG is not a register we can allocate. */ 1611: || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1) 1612: /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note. 1613: These have already been taken care of. This probably wouldn't 1614: combine anyway, but don't take any chances. */ 1615: || (ureg >= FIRST_PSEUDO_REGISTER 1616: && find_reg_note (insn, REG_NO_CONFLICT, usedreg)) 1617: /* Don't tie something to itself. In most cases it would make no 1618: difference, but it would screw up if the reg being tied to itself 1619: also dies in this insn. */ 1620: || ureg == sreg 1621: /* Don't try to connect two different hardware registers. */ 1622: || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER) 1623: /* Don't connect two different machine modes if they have different 1624: implications as to which registers may be used. */ 1625: || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))) 1626: return 0; 1627: 1628: /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in 1629: qty_phys_sugg for the pseudo instead of tying them. 1630: 1631: Return "failure" so that the lifespan of UREG is terminated here; 1632: that way the two lifespans will be disjoint and nothing will prevent 1633: the pseudo reg from being given this hard reg. */ 1634: 1635: if (ureg < FIRST_PSEUDO_REGISTER) 1636: { 1637: /* Allocate a quantity number so we have a place to put our 1638: suggestions. */ 1639: if (reg_qty[sreg] == -2) 1640: reg_is_born (setreg, 2 * insn_number); 1641: 1642: if (reg_qty[sreg] >= 0) 1643: { 1644: if (may_save_copy) 1645: { 1646: SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg); 1647: qty_phys_has_copy_sugg[reg_qty[sreg]] = 1; 1648: } 1649: else 1650: { 1651: SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg); 1652: qty_phys_has_sugg[reg_qty[sreg]] = 1; 1653: } 1654: } 1655: return 0; 1656: } 1657: 1658: /* Similarly for SREG a hard register and UREG a pseudo register. */ 1659: 1660: if (sreg < FIRST_PSEUDO_REGISTER) 1661: { 1662: if (may_save_copy) 1663: { 1664: SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg); 1665: qty_phys_has_copy_sugg[reg_qty[ureg]] = 1; 1666: } 1667: else 1668: { 1669: SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg); 1670: qty_phys_has_sugg[reg_qty[ureg]] = 1; 1671: } 1672: return 0; 1673: } 1674: 1675: /* At this point we know that SREG and UREG are both pseudos. 1676: Do nothing if SREG already has a quantity or is a register that we 1677: don't allocate. */ 1678: if (reg_qty[sreg] >= -1 1679: /* If we are not going to let any regs live across calls, 1680: don't tie a call-crossing reg to a non-call-crossing reg. */ 1681: || (current_function_has_nonlocal_label 1682: && ((reg_n_calls_crossed[ureg] > 0) 1683: != (reg_n_calls_crossed[sreg] > 0)))) 1684: return 0; 1685: 1686: /* We don't already know about SREG, so tie it to UREG 1687: if this is the last use of UREG, provided the classes they want 1688: are compatible. */ 1689: 1690: if ((already_dead || find_regno_note (insn, REG_DEAD, ureg)) 1691: && reg_meets_class_p (sreg, qty_min_class[reg_qty[ureg]])) 1692: { 1693: /* Add SREG to UREG's quantity. */ 1694: sqty = reg_qty[ureg]; 1695: reg_qty[sreg] = sqty; 1696: reg_offset[sreg] = reg_offset[ureg] + offset; 1697: reg_next_in_qty[sreg] = qty_first_reg[sqty]; 1698: qty_first_reg[sqty] = sreg; 1699: 1700: /* If SREG's reg class is smaller, set qty_min_class[SQTY]. */ 1701: update_qty_class (sqty, sreg); 1702: 1703: /* Update info about quantity SQTY. */ 1704: qty_n_calls_crossed[sqty] += reg_n_calls_crossed[sreg]; 1705: qty_n_refs[sqty] += reg_n_refs[sreg]; 1706: if (usize < ssize) 1707: { 1708: register int i; 1709: 1710: for (i = qty_first_reg[sqty]; i >= 0; i = reg_next_in_qty[i]) 1711: reg_offset[i] -= offset; 1712: 1713: qty_size[sqty] = ssize; 1714: qty_mode[sqty] = GET_MODE (setreg); 1715: } 1716: } 1717: else 1718: return 0; 1719: 1720: return 1; 1721: } 1722: 1723: /* Return 1 if the preferred class of REG allows it to be tied 1724: to a quantity or register whose class is CLASS. 1725: True if REG's reg class either contains or is contained in CLASS. */ 1726: 1727: static int 1728: reg_meets_class_p (reg, class) 1729: int reg; 1730: enum reg_class class; 1731: { 1732: register enum reg_class rclass = reg_preferred_class (reg); 1733: return (reg_class_subset_p (rclass, class) 1734: || reg_class_subset_p (class, rclass)); 1735: } 1736: 1737: /* Return 1 if the two specified classes have registers in common. 1738: If CALL_SAVED, then consider only call-saved registers. */ 1739: 1740: static int 1741: reg_classes_overlap_p (c1, c2, call_saved) 1742: register enum reg_class c1; 1743: register enum reg_class c2; 1744: int call_saved; 1745: { 1746: HARD_REG_SET c; 1747: int i; 1748: 1749: COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]); 1750: AND_HARD_REG_SET (c, reg_class_contents[(int) c2]); 1751: 1752: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1753: if (TEST_HARD_REG_BIT (c, i) 1754: && (! call_saved || ! call_used_regs[i])) 1755: return 1; 1756: 1757: return 0; 1758: } 1759: 1760: /* Update the class of QTY assuming that REG is being tied to it. */ 1761: 1762: static void 1763: update_qty_class (qty, reg) 1764: int qty; 1765: int reg; 1766: { 1767: enum reg_class rclass = reg_preferred_class (reg); 1768: if (reg_class_subset_p (rclass, qty_min_class[qty])) 1769: qty_min_class[qty] = rclass; 1.1.1.4 root 1770: 1771: rclass = reg_alternate_class (reg); 1772: if (reg_class_subset_p (rclass, qty_alternate_class[qty])) 1773: qty_alternate_class[qty] = rclass; 1.1 root 1774: } 1775: 1776: /* Handle something which alters the value of an rtx REG. 1777: 1778: REG is whatever is set or clobbered. SETTER is the rtx that 1779: is modifying the register. 1780: 1781: If it is not really a register, we do nothing. 1782: The file-global variables `this_insn' and `this_insn_number' 1783: carry info from `block_alloc'. */ 1784: 1785: static void 1786: reg_is_set (reg, setter) 1787: rtx reg; 1788: rtx setter; 1789: { 1790: /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of 1791: a hard register. These may actually not exist any more. */ 1792: 1793: if (GET_CODE (reg) != SUBREG 1794: && GET_CODE (reg) != REG) 1795: return; 1796: 1797: /* Mark this register as being born. If it is used in a CLOBBER, mark 1798: it as being born halfway between the previous insn and this insn so that 1799: it conflicts with our inputs but not the outputs of the previous insn. */ 1800: 1801: reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER)); 1802: } 1803: 1804: /* Handle beginning of the life of register REG. 1805: BIRTH is the index at which this is happening. */ 1806: 1807: static void 1808: reg_is_born (reg, birth) 1809: rtx reg; 1810: int birth; 1811: { 1812: register int regno; 1813: 1814: if (GET_CODE (reg) == SUBREG) 1815: regno = REGNO (SUBREG_REG (reg)) + SUBREG_WORD (reg); 1816: else 1817: regno = REGNO (reg); 1818: 1819: if (regno < FIRST_PSEUDO_REGISTER) 1820: { 1821: mark_life (regno, GET_MODE (reg), 1); 1822: 1823: /* If the register was to have been born earlier that the present 1824: insn, mark it as live where it is actually born. */ 1825: if (birth < 2 * this_insn_number) 1826: post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number); 1827: } 1828: else 1829: { 1830: if (reg_qty[regno] == -2) 1831: alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth); 1832: 1833: /* If this register has a quantity number, show that it isn't dead. */ 1834: if (reg_qty[regno] >= 0) 1835: qty_death[reg_qty[regno]] = -1; 1836: } 1837: } 1838: 1839: /* Record the death of REG in the current insn. If OUTPUT_P is non-zero, 1840: REG is an output that is dying (i.e., it is never used), otherwise it 1.1.1.2 root 1841: is an input (the normal case). 1842: If OUTPUT_P is 1, then we extend the life past the end of this insn. */ 1.1 root 1843: 1844: static void 1845: wipe_dead_reg (reg, output_p) 1846: register rtx reg; 1847: int output_p; 1848: { 1849: register int regno = REGNO (reg); 1850: 1.1.1.2 root 1851: /* If this insn has multiple results, 1852: and the dead reg is used in one of the results, 1853: extend its life to after this insn, 1854: so it won't get allocated together with any other result of this insn. */ 1855: if (GET_CODE (PATTERN (this_insn)) == PARALLEL 1856: && !single_set (this_insn)) 1857: { 1858: int i; 1859: for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--) 1860: { 1861: rtx set = XVECEXP (PATTERN (this_insn), 0, i); 1862: if (GET_CODE (set) == SET 1863: && GET_CODE (SET_DEST (set)) != REG 1864: && !rtx_equal_p (reg, SET_DEST (set)) 1865: && reg_overlap_mentioned_p (reg, SET_DEST (set))) 1866: output_p = 1; 1867: } 1868: } 1869: 1.1 root 1870: if (regno < FIRST_PSEUDO_REGISTER) 1871: { 1872: mark_life (regno, GET_MODE (reg), 0); 1873: 1874: /* If a hard register is dying as an output, mark it as in use at 1875: the beginning of this insn (the above statement would cause this 1876: not to happen). */ 1877: if (output_p) 1878: post_mark_life (regno, GET_MODE (reg), 1, 1879: 2 * this_insn_number, 2 * this_insn_number+ 1); 1880: } 1881: 1882: else if (reg_qty[regno] >= 0) 1883: qty_death[reg_qty[regno]] = 2 * this_insn_number + output_p; 1884: } 1885: 1886: /* Find a block of SIZE words of hard regs in reg_class CLASS 1887: that can hold something of machine-mode MODE 1888: (but actually we test only the first of the block for holding MODE) 1889: and still free between insn BORN_INDEX and insn DEAD_INDEX, 1890: and return the number of the first of them. 1891: Return -1 if such a block cannot be found. 1892: If QTY crosses calls, insist on a register preserved by calls, 1893: unless ACCEPT_CALL_CLOBBERED is nonzero. 1894: 1895: If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested 1896: register is available. If not, return -1. */ 1897: 1898: static int 1899: find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested, 1900: born_index, dead_index) 1901: enum reg_class class; 1902: enum machine_mode mode; 1903: int accept_call_clobbered; 1904: int just_try_suggested; 1905: int qty; 1906: int born_index, dead_index; 1907: { 1908: register int i, ins; 1909: #ifdef HARD_REG_SET 1910: register /* Declare it register if it's a scalar. */ 1911: #endif 1912: HARD_REG_SET used, first_used; 1913: #ifdef ELIMINABLE_REGS 1914: static struct {int from, to; } eliminables[] = ELIMINABLE_REGS; 1915: #endif 1916: 1917: /* Validate our parameters. */ 1918: if (born_index < 0 || born_index > dead_index) 1919: abort (); 1920: 1921: /* Don't let a pseudo live in a reg across a function call 1922: if we might get a nonlocal goto. */ 1923: if (current_function_has_nonlocal_label 1924: && qty_n_calls_crossed[qty] > 0) 1925: return -1; 1926: 1927: if (accept_call_clobbered) 1928: COPY_HARD_REG_SET (used, call_fixed_reg_set); 1929: else if (qty_n_calls_crossed[qty] == 0) 1930: COPY_HARD_REG_SET (used, fixed_reg_set); 1931: else 1932: COPY_HARD_REG_SET (used, call_used_reg_set); 1933: 1934: for (ins = born_index; ins < dead_index; ins++) 1935: IOR_HARD_REG_SET (used, regs_live_at[ins]); 1936: 1937: IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); 1938: 1939: /* Don't use the frame pointer reg in local-alloc even if 1940: we may omit the frame pointer, because if we do that and then we 1941: need a frame pointer, reload won't know how to move the pseudo 1942: to another hard reg. It can move only regs made by global-alloc. 1943: 1944: This is true of any register that can be eliminated. */ 1945: #ifdef ELIMINABLE_REGS 1946: for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++) 1947: SET_HARD_REG_BIT (used, eliminables[i].from); 1.1.1.6 ! root 1948: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM ! 1949: /* If FRAME_POINTER_REGNUM is not a real register, then protect the one ! 1950: that it might be eliminated into. */ ! 1951: SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM); ! 1952: #endif 1.1 root 1953: #else 1954: SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); 1955: #endif 1956: 1957: /* Normally, the registers that can be used for the first register in 1958: a multi-register quantity are the same as those that can be used for 1959: subsequent registers. However, if just trying suggested registers, 1960: restrict our consideration to them. If there are copy-suggested 1961: register, try them. Otherwise, try the arithmetic-suggested 1962: registers. */ 1963: COPY_HARD_REG_SET (first_used, used); 1964: 1965: if (just_try_suggested) 1966: { 1967: if (qty_phys_has_copy_sugg[qty]) 1968: IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]); 1969: else 1970: IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]); 1971: } 1972: 1973: /* If all registers are excluded, we can't do anything. */ 1974: GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail); 1975: 1976: /* If at least one would be suitable, test each hard reg. */ 1977: 1978: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1979: { 1980: #ifdef REG_ALLOC_ORDER 1981: int regno = reg_alloc_order[i]; 1982: #else 1983: int regno = i; 1984: #endif 1985: if (! TEST_HARD_REG_BIT (first_used, regno) 1986: && HARD_REGNO_MODE_OK (regno, mode)) 1987: { 1988: register int j; 1989: register int size1 = HARD_REGNO_NREGS (regno, mode); 1990: for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); 1991: if (j == size1) 1992: { 1993: /* Mark that this register is in use between its birth and death 1994: insns. */ 1995: post_mark_life (regno, mode, 1, born_index, dead_index); 1996: return regno; 1997: } 1998: #ifndef REG_ALLOC_ORDER 1999: i += j; /* Skip starting points we know will lose */ 2000: #endif 2001: } 2002: } 2003: 2004: fail: 2005: 2006: /* If we are just trying suggested register, we have just tried copy- 2007: suggested registers, and there are arithmetic-suggested registers, 2008: try them. */ 2009: 2010: /* If it would be profitable to allocate a call-clobbered register 2011: and save and restore it around calls, do that. */ 2012: if (just_try_suggested && qty_phys_has_copy_sugg[qty] 2013: && qty_phys_has_sugg[qty]) 2014: { 2015: /* Don't try the copy-suggested regs again. */ 2016: qty_phys_has_copy_sugg[qty] = 0; 2017: return find_free_reg (class, mode, qty, accept_call_clobbered, 1, 2018: born_index, dead_index); 2019: } 2020: 1.1.1.5 root 2021: /* We need not check to see if the current function has nonlocal 2022: labels because we don't put any pseudos that are live over calls in 2023: registers in that case. */ 2024: 1.1 root 2025: if (! accept_call_clobbered 2026: && flag_caller_saves 2027: && ! just_try_suggested 2028: && qty_n_calls_crossed[qty] != 0 2029: && CALLER_SAVE_PROFITABLE (qty_n_refs[qty], qty_n_calls_crossed[qty])) 2030: { 2031: i = find_free_reg (class, mode, qty, 1, 0, born_index, dead_index); 2032: if (i >= 0) 2033: caller_save_needed = 1; 2034: return i; 2035: } 2036: return -1; 2037: } 2038: 2039: /* Mark that REGNO with machine-mode MODE is live starting from the current 2040: insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE 2041: is zero). */ 2042: 2043: static void 2044: mark_life (regno, mode, life) 2045: register int regno; 2046: enum machine_mode mode; 2047: int life; 2048: { 2049: register int j = HARD_REGNO_NREGS (regno, mode); 2050: if (life) 2051: while (--j >= 0) 2052: SET_HARD_REG_BIT (regs_live, regno + j); 2053: else 2054: while (--j >= 0) 2055: CLEAR_HARD_REG_BIT (regs_live, regno + j); 2056: } 2057: 2058: /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE 2059: is non-zero) or dead (if LIFE is zero) from insn number BIRTH (inclusive) 2060: to insn number DEATH (exclusive). */ 2061: 2062: static void 2063: post_mark_life (regno, mode, life, birth, death) 2064: register int regno, life, birth; 2065: enum machine_mode mode; 2066: int death; 2067: { 2068: register int j = HARD_REGNO_NREGS (regno, mode); 2069: #ifdef HARD_REG_SET 2070: register /* Declare it register if it's a scalar. */ 2071: #endif 2072: HARD_REG_SET this_reg; 2073: 2074: CLEAR_HARD_REG_SET (this_reg); 2075: while (--j >= 0) 2076: SET_HARD_REG_BIT (this_reg, regno + j); 2077: 2078: if (life) 2079: while (birth < death) 2080: { 2081: IOR_HARD_REG_SET (regs_live_at[birth], this_reg); 2082: birth++; 2083: } 2084: else 2085: while (birth < death) 2086: { 2087: AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg); 2088: birth++; 2089: } 2090: } 2091: 2092: /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0 2093: is the register being clobbered, and R1 is a register being used in 2094: the equivalent expression. 2095: 2096: If R1 dies in the block and has a REG_NO_CONFLICT note on every insn 2097: in which it is used, return 1. 2098: 2099: Otherwise, return 0. */ 2100: 2101: static int 2102: no_conflict_p (insn, r0, r1) 2103: rtx insn, r0, r1; 2104: { 2105: int ok = 0; 1.1.1.4 root 2106: rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 1.1 root 2107: rtx p, last; 2108: 2109: /* If R1 is a hard register, return 0 since we handle this case 2110: when we scan the insns that actually use it. */ 2111: 2112: if (note == 0 2113: || (GET_CODE (r1) == REG && REGNO (r1) < FIRST_PSEUDO_REGISTER) 2114: || (GET_CODE (r1) == SUBREG && GET_CODE (SUBREG_REG (r1)) == REG 2115: && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER)) 2116: return 0; 2117: 2118: last = XEXP (note, 0); 2119: 2120: for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p)) 2121: if (GET_RTX_CLASS (GET_CODE (p)) == 'i') 2122: { 2123: if (find_reg_note (p, REG_DEAD, r1)) 2124: ok = 1; 2125: 2126: if (reg_mentioned_p (r1, PATTERN (p)) 2127: && ! find_reg_note (p, REG_NO_CONFLICT, r1)) 2128: return 0; 2129: } 2130: 2131: return ok; 2132: } 2133: 1.1.1.4 root 2134: #ifdef REGISTER_CONSTRAINTS 2135: 1.1 root 2136: /* Return 1 if the constraint string P indicates that the a the operand 2137: must be equal to operand 0 and that no register is acceptable. */ 2138: 2139: static int 2140: requires_inout_p (p) 2141: char *p; 2142: { 2143: char c; 2144: int found_zero = 0; 2145: 2146: while (c = *p++) 2147: switch (c) 2148: { 2149: case '0': 2150: found_zero = 1; 2151: break; 2152: 2153: case '=': case '+': case '?': 2154: case '#': case '&': case '!': 2155: case '*': case '%': case ',': 2156: case '1': case '2': case '3': case '4': 2157: case 'm': case '<': case '>': case 'V': case 'o': 2158: case 'E': case 'F': case 'G': case 'H': 2159: case 's': case 'i': case 'n': 2160: case 'I': case 'J': case 'K': case 'L': 2161: case 'M': case 'N': case 'O': case 'P': 2162: #ifdef EXTRA_CONSTRAINT 2163: case 'Q': case 'R': case 'S': case 'T': case 'U': 2164: #endif 2165: case 'X': 2166: /* These don't say anything we care about. */ 2167: break; 2168: 2169: case 'p': 2170: case 'g': case 'r': 2171: default: 2172: /* These mean a register is allowed. Fail if so. */ 2173: return 0; 2174: } 2175: 2176: return found_zero; 2177: } 1.1.1.4 root 2178: #endif /* REGISTER_CONSTRAINTS */ 1.1 root 2179: 2180: void 2181: dump_local_alloc (file) 2182: FILE *file; 2183: { 2184: register int i; 2185: for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 2186: if (reg_renumber[i] != -1) 2187: fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]); 2188: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.