![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to reorg.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 reorg.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Perform instruction reorganizations for delay slot filling. 1.1.1.7 ! root 2: Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. ! 3: Contributed by Richard Kenner ([email protected]). 1.1 root 4: Hacked by Michael Tiemann ([email protected]). 5: 6: This file is part of GNU CC. 7: 8: GNU CC is free software; you can redistribute it and/or modify 9: it under the terms of the GNU General Public License as published by 10: the Free Software Foundation; either version 2, or (at your option) 11: any later version. 12: 13: GNU CC is distributed in the hope that it will be useful, 14: but WITHOUT ANY WARRANTY; without even the implied warranty of 15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16: GNU General Public License for more details. 17: 18: You should have received a copy of the GNU General Public License 19: along with GNU CC; see the file COPYING. If not, write to 20: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 21: 22: /* Instruction reorganization pass. 23: 24: This pass runs after register allocation and final jump 25: optimization. It should be the last pass to run before peephole. 26: It serves primarily to fill delay slots of insns, typically branch 27: and call insns. Other insns typically involve more complicated 1.1.1.3 root 28: interactions of data dependencies and resource constraints, and 1.1 root 29: are better handled by scheduling before register allocation (by the 30: function `schedule_insns'). 31: 32: The Branch Penalty is the number of extra cycles that are needed to 33: execute a branch insn. On an ideal machine, branches take a single 34: cycle, and the Branch Penalty is 0. Several RISC machines approach 35: branch delays differently: 36: 37: The MIPS and AMD 29000 have a single branch delay slot. Most insns 38: (except other branches) can be used to fill this slot. When the 39: slot is filled, two insns execute in two cycles, reducing the 40: branch penalty to zero. 41: 42: The Motorola 88000 conditionally exposes its branch delay slot, 43: so code is shorter when it is turned off, but will run faster 44: when useful insns are scheduled there. 45: 46: The IBM ROMP has two forms of branch and call insns, both with and 47: without a delay slot. Much like the 88k, insns not using the delay 48: slot can be shorted (2 bytes vs. 4 bytes), but will run slowed. 49: 50: The SPARC always has a branch delay slot, but its effects can be 51: annulled when the branch is not taken. This means that failing to 52: find other sources of insns, we can hoist an insn from the branch 53: target that would only be safe to execute knowing that the branch 54: is taken. 55: 1.1.1.5 root 56: The HP-PA always has a branch delay slot. For unconditional branches 57: its effects can be annulled when the branch is taken. The effects 58: of the delay slot in a conditional branch can be nullified for forward 59: taken branches, or for untaken backward branches. This means 60: we can hoist insns from the fall-through path for forward branches or 61: steal insns from the target of backward branches. 62: 1.1 root 63: Three techniques for filling delay slots have been implemented so far: 64: 65: (1) `fill_simple_delay_slots' is the simplest, most efficient way 66: to fill delay slots. This pass first looks for insns which come 67: from before the branch and which are safe to execute after the 68: branch. Then it searches after the insn requiring delay slots or, 69: in the case of a branch, for insns that are after the point at 70: which the branch merges into the fallthrough code, if such a point 71: exists. When such insns are found, the branch penalty decreases 72: and no code expansion takes place. 73: 74: (2) `fill_eager_delay_slots' is more complicated: it is used for 75: scheduling conditional jumps, or for scheduling jumps which cannot 76: be filled using (1). A machine need not have annulled jumps to use 77: this strategy, but it helps (by keeping more options open). 78: `fill_eager_delay_slots' tries to guess the direction the branch 79: will go; if it guesses right 100% of the time, it can reduce the 1.1.1.4 root 80: branch penalty as much as `fill_simple_delay_slots' does. If it 1.1 root 81: guesses wrong 100% of the time, it might as well schedule nops (or 82: on the m88k, unexpose the branch slot). When 83: `fill_eager_delay_slots' takes insns from the fall-through path of 84: the jump, usually there is no code expansion; when it takes insns 85: from the branch target, there is code expansion if it is not the 86: only way to reach that target. 87: 88: (3) `relax_delay_slots' uses a set of rules to simplify code that 89: has been reorganized by (1) and (2). It finds cases where 90: conditional test can be eliminated, jumps can be threaded, extra 91: insns can be eliminated, etc. It is the job of (1) and (2) to do a 92: good job of scheduling locally; `relax_delay_slots' takes care of 93: making the various individual schedules work well together. It is 94: especially tuned to handle the control flow interactions of branch 95: insns. It does nothing for insns with delay slots that do not 96: branch. 97: 98: On machines that use CC0, we are very conservative. We will not make 99: a copy of an insn involving CC0 since we want to maintain a 1-1 1.1.1.2 root 100: correspondence between the insn that sets and uses CC0. The insns are 1.1 root 101: allowed to be separated by placing an insn that sets CC0 (but not an insn 102: that uses CC0; we could do this, but it doesn't seem worthwhile) in a 103: delay slot. In that case, we point each insn at the other with REG_CC_USER 104: and REG_CC_SETTER notes. Note that these restrictions affect very few 105: machines because most RISC machines with delay slots will not use CC0 106: (the RT is the only known exception at this point). 107: 108: Not yet implemented: 109: 110: The Acorn Risc Machine can conditionally execute most insns, so 111: it is profitable to move single insns into a position to execute 112: based on the condition code of the previous insn. 113: 114: The HP-PA can conditionally nullify insns, providing a similar 115: effect to the ARM, differing mostly in which insn is "in charge". */ 116: 117: #include <stdio.h> 118: #include "config.h" 119: #include "rtl.h" 120: #include "insn-config.h" 121: #include "conditions.h" 122: #include "hard-reg-set.h" 123: #include "basic-block.h" 124: #include "regs.h" 125: #include "insn-flags.h" 126: #include "recog.h" 127: #include "flags.h" 128: #include "output.h" 129: #include "obstack.h" 1.1.1.4 root 130: #include "insn-attr.h" 131: 132: #ifdef DELAY_SLOTS 1.1 root 133: 134: #define obstack_chunk_alloc xmalloc 135: #define obstack_chunk_free free 136: 137: #ifndef ANNUL_IFTRUE_SLOTS 1.1.1.5 root 138: #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0 1.1 root 139: #endif 140: #ifndef ANNUL_IFFALSE_SLOTS 1.1.1.5 root 141: #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0 1.1 root 142: #endif 143: 144: /* Insns which have delay slots that have not yet been filled. */ 145: 146: static struct obstack unfilled_slots_obstack; 147: static rtx *unfilled_firstobj; 148: 149: /* Define macros to refer to the first and last slot containing unfilled 150: insns. These are used because the list may move and its address 151: should be recomputed at each use. */ 152: 153: #define unfilled_slots_base \ 154: ((rtx *) obstack_base (&unfilled_slots_obstack)) 155: 156: #define unfilled_slots_next \ 157: ((rtx *) obstack_next_free (&unfilled_slots_obstack)) 158: 159: /* This structure is used to indicate which hardware resources are set or 160: needed by insns so far. */ 161: 162: struct resources 163: { 164: char memory; /* Insn sets or needs a memory location. */ 165: char volatil; /* Insn sets or needs a volatile memory loc. */ 166: char cc; /* Insn sets or needs the condition codes. */ 167: HARD_REG_SET regs; /* Which registers are set or needed. */ 168: }; 169: 170: /* Macro to clear all resources. */ 171: #define CLEAR_RESOURCE(RES) \ 172: do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \ 173: CLEAR_HARD_REG_SET ((RES)->regs); } while (0) 174: 1.1.1.4 root 175: /* Indicates what resources are required at the beginning of the epilogue. */ 176: static struct resources start_of_epilogue_needs; 177: 1.1 root 178: /* Indicates what resources are required at function end. */ 179: static struct resources end_of_function_needs; 180: 181: /* Points to the label before the end of the function. */ 182: static rtx end_of_function_label; 183: 1.1.1.3 root 184: /* This structure is used to record liveness information at the targets or 1.1 root 185: fallthrough insns of branches. We will most likely need the information 186: at targets again, so save them in a hash table rather than recomputing them 187: each time. */ 188: 189: struct target_info 190: { 191: int uid; /* INSN_UID of target. */ 192: struct target_info *next; /* Next info for same hash bucket. */ 193: HARD_REG_SET live_regs; /* Registers live at target. */ 194: int block; /* Basic block number containing target. */ 195: int bb_tick; /* Generation count of basic block info. */ 196: }; 197: 198: #define TARGET_HASH_PRIME 257 199: 200: /* Define the hash table itself. */ 201: static struct target_info **target_hash_table; 202: 203: /* For each basic block, we maintain a generation number of its basic 204: block info, which is updated each time we move an insn from the 205: target of a jump. This is the generation number indexed by block 206: number. */ 207: 208: static int *bb_ticks; 209: 210: /* Mapping between INSN_UID's and position in the code since INSN_UID's do 211: not always monotonically increase. */ 212: static int *uid_to_ruid; 213: 214: /* Highest valid index in `uid_to_ruid'. */ 215: static int max_uid; 216: 1.1.1.5 root 217: static void mark_referenced_resources PROTO((rtx, struct resources *, int)); 218: static void mark_set_resources PROTO((rtx, struct resources *, int, int)); 219: static int stop_search_p PROTO((rtx, int)); 220: static int resource_conflicts_p PROTO((struct resources *, 221: struct resources *)); 222: static int insn_references_resource_p PROTO((rtx, struct resources *, int)); 223: static int insn_sets_resources_p PROTO((rtx, struct resources *, int)); 224: static rtx find_end_label PROTO((void)); 225: static rtx emit_delay_sequence PROTO((rtx, rtx, int, int)); 226: static rtx add_to_delay_list PROTO((rtx, rtx)); 227: static void delete_from_delay_slot PROTO((rtx)); 228: static void delete_scheduled_jump PROTO((rtx)); 229: static void note_delay_statistics PROTO((int, int)); 230: static rtx optimize_skip PROTO((rtx)); 231: static int get_jump_flags PROTO((rtx, rtx)); 232: static int rare_destination PROTO((rtx)); 233: static int mostly_true_jump PROTO((rtx, rtx)); 234: static rtx get_branch_condition PROTO((rtx, rtx)); 235: static int condition_dominates_p PROTO((rtx, rtx)); 236: static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx, 237: struct resources *, 238: struct resources *, 239: struct resources *, 240: int, int *, int *, rtx *)); 241: static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx, 242: struct resources *, 243: struct resources *, 244: struct resources *, 245: int, int *, int *)); 246: static void try_merge_delay_insns PROTO((rtx, rtx)); 1.1.1.7 ! root 247: static rtx redundant_insn_p PROTO((rtx, rtx, rtx)); 1.1.1.5 root 248: static int own_thread_p PROTO((rtx, rtx, int)); 249: static int find_basic_block PROTO((rtx)); 250: static void update_block PROTO((rtx, rtx)); 251: static int reorg_redirect_jump PROTO((rtx, rtx)); 252: static void update_reg_dead_notes PROTO((rtx, rtx)); 1.1.1.7 ! root 253: static void update_reg_unused_notes PROTO((rtx, rtx)); 1.1.1.5 root 254: static void update_live_status PROTO((rtx, rtx)); 255: static rtx next_insn_no_annul PROTO((rtx)); 256: static void mark_target_live_regs PROTO((rtx, struct resources *)); 257: static void fill_simple_delay_slots PROTO((rtx, int)); 258: static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int, 259: int, int, int, int *)); 260: static void fill_eager_delay_slots PROTO((rtx)); 261: static void relax_delay_slots PROTO((rtx)); 262: static void make_return_insns PROTO((rtx)); 1.1.1.7 ! root 263: static int redirect_with_delay_slots_safe_p PROTO ((rtx, rtx, rtx)); ! 264: static int redirect_with_delay_list_safe_p PROTO ((rtx, rtx, rtx)); 1.1 root 265: 266: /* Given X, some rtl, and RES, a pointer to a `struct resource', mark 267: which resources are references by the insn. If INCLUDE_CALLED_ROUTINE 268: is TRUE, resources used by the called routine will be included for 269: CALL_INSNs. */ 270: 271: static void 1.1.1.5 root 272: mark_referenced_resources (x, res, include_delayed_effects) 1.1 root 273: register rtx x; 274: register struct resources *res; 1.1.1.5 root 275: register int include_delayed_effects; 1.1 root 276: { 277: register enum rtx_code code = GET_CODE (x); 278: register int i, j; 279: register char *format_ptr; 280: 281: /* Handle leaf items for which we set resource flags. Also, special-case 282: CALL, SET and CLOBBER operators. */ 283: switch (code) 284: { 285: case CONST: 286: case CONST_INT: 287: case CONST_DOUBLE: 288: case PC: 289: case SYMBOL_REF: 290: case LABEL_REF: 291: return; 292: 293: case SUBREG: 294: if (GET_CODE (SUBREG_REG (x)) != REG) 295: mark_referenced_resources (SUBREG_REG (x), res, 0); 296: else 297: { 298: int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x); 299: int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x)); 300: for (i = regno; i < last_regno; i++) 301: SET_HARD_REG_BIT (res->regs, i); 302: } 303: return; 304: 305: case REG: 306: for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++) 307: SET_HARD_REG_BIT (res->regs, REGNO (x) + i); 308: return; 309: 310: case MEM: 311: /* If this memory shouldn't change, it really isn't referencing 312: memory. */ 313: if (! RTX_UNCHANGING_P (x)) 314: res->memory = 1; 315: res->volatil = MEM_VOLATILE_P (x); 316: 317: /* Mark registers used to access memory. */ 318: mark_referenced_resources (XEXP (x, 0), res, 0); 319: return; 320: 321: case CC0: 322: res->cc = 1; 323: return; 324: 325: case UNSPEC_VOLATILE: 326: case ASM_INPUT: 327: /* Traditional asm's are always volatile. */ 328: res->volatil = 1; 329: return; 330: 331: case ASM_OPERANDS: 332: res->volatil = MEM_VOLATILE_P (x); 333: 334: /* For all ASM_OPERANDS, we must traverse the vector of input operands. 335: We can not just fall through here since then we would be confused 336: by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 337: traditional asms unlike their normal usage. */ 338: 339: for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++) 340: mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0); 341: return; 342: 343: case CALL: 344: /* The first operand will be a (MEM (xxx)) but doesn't really reference 345: memory. The second operand may be referenced, though. */ 346: mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0); 347: mark_referenced_resources (XEXP (x, 1), res, 0); 348: return; 349: 350: case SET: 351: /* Usually, the first operand of SET is set, not referenced. But 352: registers used to access memory are referenced. SET_DEST is 353: also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */ 354: 355: mark_referenced_resources (SET_SRC (x), res, 0); 356: 357: x = SET_DEST (x); 358: if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT) 359: mark_referenced_resources (x, res, 0); 360: else if (GET_CODE (x) == SUBREG) 361: x = SUBREG_REG (x); 362: if (GET_CODE (x) == MEM) 363: mark_referenced_resources (XEXP (x, 0), res, 0); 364: return; 365: 366: case CLOBBER: 367: return; 368: 369: case CALL_INSN: 1.1.1.5 root 370: if (include_delayed_effects) 1.1 root 371: { 372: /* A CALL references memory, the frame pointer if it exists, the 373: stack pointer, any global registers and any registers given in 374: USE insns immediately in front of the CALL. 375: 376: However, we may have moved some of the parameter loading insns 377: into the delay slot of this CALL. If so, the USE's for them 378: don't count and should be skipped. */ 379: rtx insn = PREV_INSN (x); 380: rtx sequence = 0; 381: int seq_size = 0; 382: int i; 383: 384: /* If we are part of a delay slot sequence, point at the SEQUENCE. */ 385: if (NEXT_INSN (insn) != x) 386: { 387: sequence = PATTERN (NEXT_INSN (insn)); 388: seq_size = XVECLEN (sequence, 0); 389: if (GET_CODE (sequence) != SEQUENCE) 390: abort (); 391: } 392: 393: res->memory = 1; 394: SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM); 395: if (frame_pointer_needed) 1.1.1.6 root 396: { 397: SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM); 398: #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 399: SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM); 400: #endif 401: } 1.1 root 402: 403: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 404: if (global_regs[i]) 405: SET_HARD_REG_BIT (res->regs, i); 406: 1.1.1.7 ! root 407: { ! 408: rtx link; ! 409: ! 410: for (link = CALL_INSN_FUNCTION_USAGE (x); ! 411: link; ! 412: link = XEXP (link, 1)) ! 413: if (GET_CODE (XEXP (link, 0)) == USE) 1.1 root 414: { 1.1.1.7 ! root 415: for (i = 1; i < seq_size; i++) ! 416: { ! 417: rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i)); ! 418: if (GET_CODE (slot_pat) == SET ! 419: && rtx_equal_p (SET_DEST (slot_pat), ! 420: SET_DEST (XEXP (link, 0)))) ! 421: break; ! 422: } ! 423: if (i >= seq_size) ! 424: mark_referenced_resources (SET_DEST (XEXP (link, 0)), ! 425: res, 0); 1.1 root 426: } 1.1.1.7 ! root 427: } 1.1 root 428: } 429: 1.1.1.3 root 430: /* ... fall through to other INSN processing ... */ 1.1 root 431: 432: case INSN: 433: case JUMP_INSN: 1.1.1.5 root 434: 435: #ifdef INSN_REFERENCES_ARE_DELAYED 436: if (! include_delayed_effects 437: && INSN_REFERENCES_ARE_DELAYED (x)) 438: return; 439: #endif 440: 1.1 root 441: /* No special processing, just speed up. */ 1.1.1.5 root 442: mark_referenced_resources (PATTERN (x), res, include_delayed_effects); 1.1 root 443: return; 444: } 445: 446: /* Process each sub-expression and flag what it needs. */ 447: format_ptr = GET_RTX_FORMAT (code); 448: for (i = 0; i < GET_RTX_LENGTH (code); i++) 449: switch (*format_ptr++) 450: { 451: case 'e': 1.1.1.5 root 452: mark_referenced_resources (XEXP (x, i), res, include_delayed_effects); 1.1 root 453: break; 454: 455: case 'E': 456: for (j = 0; j < XVECLEN (x, i); j++) 457: mark_referenced_resources (XVECEXP (x, i, j), res, 1.1.1.5 root 458: include_delayed_effects); 1.1 root 459: break; 460: } 461: } 462: 1.1.1.4 root 463: /* Given X, a part of an insn, and a pointer to a `struct resource', RES, 464: indicate which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE 465: is nonzero, also mark resources potentially set by the called routine. 466: 467: If IN_DEST is nonzero, it means we are inside a SET. Otherwise, 468: objects are being referenced instead of set. 1.1 root 469: 470: We never mark the insn as modifying the condition code unless it explicitly 471: SETs CC0 even though this is not totally correct. The reason for this is 1.1.1.3 root 472: that we require a SET of CC0 to immediately precede the reference to CC0. 1.1 root 473: So if some other insn sets CC0 as a side-effect, we know it cannot affect 474: our computation and thus may be placed in a delay slot. */ 475: 476: static void 1.1.1.5 root 477: mark_set_resources (x, res, in_dest, include_delayed_effects) 1.1.1.4 root 478: register rtx x; 1.1 root 479: register struct resources *res; 1.1.1.4 root 480: int in_dest; 1.1.1.5 root 481: int include_delayed_effects; 1.1 root 482: { 1.1.1.4 root 483: register enum rtx_code code; 484: register int i, j; 485: register char *format_ptr; 1.1 root 486: 1.1.1.4 root 487: restart: 488: 489: code = GET_CODE (x); 490: 491: switch (code) 1.1 root 492: { 493: case NOTE: 494: case BARRIER: 495: case CODE_LABEL: 1.1.1.4 root 496: case USE: 497: case CONST_INT: 498: case CONST_DOUBLE: 499: case LABEL_REF: 500: case SYMBOL_REF: 501: case CONST: 502: case PC: 1.1 root 503: /* These don't set any resources. */ 504: return; 505: 1.1.1.4 root 506: case CC0: 507: if (in_dest) 508: res->cc = 1; 509: return; 510: 1.1 root 511: case CALL_INSN: 512: /* Called routine modifies the condition code, memory, any registers 513: that aren't saved across calls, global registers and anything 514: explicitly CLOBBERed immediately after the CALL_INSN. */ 515: 1.1.1.5 root 516: if (include_delayed_effects) 1.1 root 517: { 1.1.1.4 root 518: rtx next = NEXT_INSN (x); 1.1.1.6 root 519: rtx prev = PREV_INSN (x); 1.1.1.7 ! root 520: rtx link; 1.1 root 521: 522: res->cc = res->memory = 1; 523: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 524: if (call_used_regs[i] || global_regs[i]) 525: SET_HARD_REG_BIT (res->regs, i); 526: 1.1.1.6 root 527: /* If X is part of a delay slot sequence, then NEXT should be 528: the first insn after the sequence. */ 529: if (NEXT_INSN (prev) != x) 530: next = NEXT_INSN (NEXT_INSN (prev)); 531: 1.1.1.7 ! root 532: for (link = CALL_INSN_FUNCTION_USAGE (x); ! 533: link; link = XEXP (link, 1)) ! 534: if (GET_CODE (XEXP (link, 0)) == CLOBBER) ! 535: mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1, 0); 1.1.1.6 root 536: 537: /* Check for a NOTE_INSN_SETJMP. If it exists, then we must 538: assume that this call can clobber any register. */ 539: if (next && GET_CODE (next) == NOTE 540: && NOTE_LINE_NUMBER (next) == NOTE_INSN_SETJMP) 541: SET_HARD_REG_SET (res->regs); 1.1 root 542: } 543: 544: /* ... and also what it's RTL says it modifies, if anything. */ 545: 546: case JUMP_INSN: 547: case INSN: 548: 1.1.1.4 root 549: /* An insn consisting of just a CLOBBER (or USE) is just for flow 550: and doesn't actually do anything, so we ignore it. */ 1.1 root 551: 1.1.1.5 root 552: #ifdef INSN_SETS_ARE_DELAYED 553: if (! include_delayed_effects 554: && INSN_SETS_ARE_DELAYED (x)) 555: return; 556: #endif 557: 1.1.1.4 root 558: x = PATTERN (x); 559: if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER) 560: goto restart; 561: return; 562: 563: case SET: 564: /* If the source of a SET is a CALL, this is actually done by 565: the called routine. So only include it if we are to include the 566: effects of the calling routine. */ 567: 568: mark_set_resources (SET_DEST (x), res, 1.1.1.5 root 569: (include_delayed_effects 1.1.1.4 root 570: || GET_CODE (SET_SRC (x)) != CALL), 571: 0); 572: 573: mark_set_resources (SET_SRC (x), res, 0, 0); 574: return; 575: 576: case CLOBBER: 577: mark_set_resources (XEXP (x, 0), res, 1, 0); 578: return; 579: 580: case SEQUENCE: 581: for (i = 0; i < XVECLEN (x, 0); i++) 582: if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0)) 583: && INSN_FROM_TARGET_P (XVECEXP (x, 0, i)))) 584: mark_set_resources (XVECEXP (x, 0, i), res, 0, 1.1.1.5 root 585: include_delayed_effects); 1.1.1.4 root 586: return; 587: 588: case POST_INC: 589: case PRE_INC: 590: case POST_DEC: 591: case PRE_DEC: 592: mark_set_resources (XEXP (x, 0), res, 1, 0); 593: return; 594: 595: case ZERO_EXTRACT: 596: mark_set_resources (XEXP (x, 0), res, in_dest, 0); 597: mark_set_resources (XEXP (x, 1), res, 0, 0); 598: mark_set_resources (XEXP (x, 2), res, 0, 0); 599: return; 600: 601: case MEM: 602: if (in_dest) 603: { 604: res->memory = 1; 605: res->volatil = MEM_VOLATILE_P (x); 606: } 607: 608: mark_set_resources (XEXP (x, 0), res, 0, 0); 609: return; 610: 1.1.1.7 ! root 611: case SUBREG: ! 612: if (in_dest) ! 613: { ! 614: if (GET_CODE (SUBREG_REG (x)) != REG) ! 615: mark_set_resources (SUBREG_REG (x), res, ! 616: in_dest, include_delayed_effects); ! 617: else ! 618: { ! 619: int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x); ! 620: int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x)); ! 621: for (i = regno; i < last_regno; i++) ! 622: SET_HARD_REG_BIT (res->regs, i); ! 623: } ! 624: } ! 625: return; ! 626: 1.1.1.4 root 627: case REG: 628: if (in_dest) 629: for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++) 630: SET_HARD_REG_BIT (res->regs, REGNO (x) + i); 631: return; 1.1 root 632: } 1.1.1.4 root 633: 634: /* Process each sub-expression and flag what it needs. */ 635: format_ptr = GET_RTX_FORMAT (code); 636: for (i = 0; i < GET_RTX_LENGTH (code); i++) 637: switch (*format_ptr++) 638: { 639: case 'e': 1.1.1.5 root 640: mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects); 1.1.1.4 root 641: break; 642: 643: case 'E': 644: for (j = 0; j < XVECLEN (x, i); j++) 645: mark_set_resources (XVECEXP (x, i, j), res, in_dest, 1.1.1.5 root 646: include_delayed_effects); 1.1.1.4 root 647: break; 648: } 1.1 root 649: } 650: 651: /* Return TRUE if this insn should stop the search for insn to fill delay 652: slots. LABELS_P indicates that labels should terminate the search. 653: In all cases, jumps terminate the search. */ 654: 655: static int 656: stop_search_p (insn, labels_p) 657: rtx insn; 658: int labels_p; 659: { 660: if (insn == 0) 661: return 1; 662: 663: switch (GET_CODE (insn)) 664: { 665: case NOTE: 666: case CALL_INSN: 667: return 0; 668: 669: case CODE_LABEL: 670: return labels_p; 671: 672: case JUMP_INSN: 673: case BARRIER: 674: return 1; 675: 676: case INSN: 677: /* OK unless it contains a delay slot or is an `asm' insn of some type. 678: We don't know anything about these. */ 679: return (GET_CODE (PATTERN (insn)) == SEQUENCE 680: || GET_CODE (PATTERN (insn)) == ASM_INPUT 681: || asm_noperands (PATTERN (insn)) >= 0); 682: 683: default: 684: abort (); 685: } 686: } 687: 688: /* Return TRUE if any resources are marked in both RES1 and RES2 or if either 689: resource set contains a volatile memory reference. Otherwise, return FALSE. */ 690: 691: static int 692: resource_conflicts_p (res1, res2) 693: struct resources *res1, *res2; 694: { 695: if ((res1->cc && res2->cc) || (res1->memory && res2->memory) 696: || res1->volatil || res2->volatil) 697: return 1; 698: 699: #ifdef HARD_REG_SET 700: return (res1->regs & res2->regs) != HARD_CONST (0); 701: #else 702: { 703: int i; 704: 705: for (i = 0; i < HARD_REG_SET_LONGS; i++) 706: if ((res1->regs[i] & res2->regs[i]) != 0) 707: return 1; 708: return 0; 709: } 710: #endif 711: } 712: 713: /* Return TRUE if any resource marked in RES, a `struct resources', is 714: referenced by INSN. If INCLUDE_CALLED_ROUTINE is set, return if the called 715: routine is using those resources. 716: 717: We compute this by computing all the resources referenced by INSN and 718: seeing if this conflicts with RES. It might be faster to directly check 719: ourselves, and this is the way it used to work, but it means duplicating 720: a large block of complex code. */ 721: 722: static int 1.1.1.5 root 723: insn_references_resource_p (insn, res, include_delayed_effects) 1.1 root 724: register rtx insn; 725: register struct resources *res; 1.1.1.5 root 726: int include_delayed_effects; 1.1 root 727: { 728: struct resources insn_res; 729: 730: CLEAR_RESOURCE (&insn_res); 1.1.1.5 root 731: mark_referenced_resources (insn, &insn_res, include_delayed_effects); 1.1 root 732: return resource_conflicts_p (&insn_res, res); 733: } 734: 735: /* Return TRUE if INSN modifies resources that are marked in RES. 736: INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be 737: included. CC0 is only modified if it is explicitly set; see comments 738: in front of mark_set_resources for details. */ 739: 740: static int 1.1.1.5 root 741: insn_sets_resource_p (insn, res, include_delayed_effects) 1.1 root 742: register rtx insn; 743: register struct resources *res; 1.1.1.5 root 744: int include_delayed_effects; 1.1 root 745: { 746: struct resources insn_sets; 747: 748: CLEAR_RESOURCE (&insn_sets); 1.1.1.5 root 749: mark_set_resources (insn, &insn_sets, 0, include_delayed_effects); 1.1 root 750: return resource_conflicts_p (&insn_sets, res); 751: } 752: 753: /* Find a label at the end of the function or before a RETURN. If there is 754: none, make one. */ 755: 756: static rtx 757: find_end_label () 758: { 759: rtx insn; 760: 761: /* If we found one previously, return it. */ 762: if (end_of_function_label) 763: return end_of_function_label; 764: 765: /* Otherwise, see if there is a label at the end of the function. If there 766: is, it must be that RETURN insns aren't needed, so that is our return 767: label and we don't have to do anything else. */ 768: 769: insn = get_last_insn (); 770: while (GET_CODE (insn) == NOTE 771: || (GET_CODE (insn) == INSN 772: && (GET_CODE (PATTERN (insn)) == USE 773: || GET_CODE (PATTERN (insn)) == CLOBBER))) 774: insn = PREV_INSN (insn); 775: 1.1.1.6 root 776: /* When a target threads its epilogue we might already have a 777: suitable return insn. If so put a label before it for the 778: end_of_function_label. */ 779: if (GET_CODE (insn) == BARRIER 780: && GET_CODE (PREV_INSN (insn)) == JUMP_INSN 781: && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN) 782: { 783: rtx temp = PREV_INSN (PREV_INSN (insn)); 784: end_of_function_label = gen_label_rtx (); 785: LABEL_NUSES (end_of_function_label) = 0; 786: 787: /* Put the label before an USE insns that may proceed the RETURN insn. */ 788: while (GET_CODE (temp) == USE) 789: temp = PREV_INSN (temp); 790: 791: emit_label_after (end_of_function_label, temp); 792: } 793: 794: else if (GET_CODE (insn) == CODE_LABEL) 795: end_of_function_label = insn; 1.1 root 796: else 797: { 798: /* Otherwise, make a new label and emit a RETURN and BARRIER, 799: if needed. */ 800: end_of_function_label = gen_label_rtx (); 801: LABEL_NUSES (end_of_function_label) = 0; 802: emit_label (end_of_function_label); 803: #ifdef HAVE_return 804: if (HAVE_return) 805: { 1.1.1.5 root 806: /* The return we make may have delay slots too. */ 807: rtx insn = gen_return (); 808: insn = emit_jump_insn (insn); 1.1 root 809: emit_barrier (); 1.1.1.5 root 810: if (num_delay_slots (insn) > 0) 811: obstack_ptr_grow (&unfilled_slots_obstack, insn); 1.1 root 812: } 813: #endif 814: } 815: 816: /* Show one additional use for this label so it won't go away until 817: we are done. */ 818: ++LABEL_NUSES (end_of_function_label); 819: 820: return end_of_function_label; 821: } 822: 823: /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace 824: the pattern of INSN with the SEQUENCE. 825: 826: Chain the insns so that NEXT_INSN of each insn in the sequence points to 827: the next and NEXT_INSN of the last insn in the sequence points to 828: the first insn after the sequence. Similarly for PREV_INSN. This makes 829: it easier to scan all insns. 830: 831: Returns the SEQUENCE that replaces INSN. */ 832: 833: static rtx 834: emit_delay_sequence (insn, list, length, avail) 835: rtx insn; 836: rtx list; 837: int length; 838: int avail; 839: { 840: register int i = 1; 841: register rtx li; 842: int had_barrier = 0; 843: 844: /* Allocate the the rtvec to hold the insns and the SEQUENCE. */ 845: rtvec seqv = rtvec_alloc (length + 1); 846: rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv); 847: rtx seq_insn = make_insn_raw (seq); 848: rtx first = get_insns (); 849: rtx last = get_last_insn (); 850: 851: /* Make a copy of the insn having delay slots. */ 852: rtx delay_insn = copy_rtx (insn); 853: 854: /* If INSN is followed by a BARRIER, delete the BARRIER since it will only 855: confuse further processing. Update LAST in case it was the last insn. 856: We will put the BARRIER back in later. */ 857: if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER) 858: { 859: delete_insn (NEXT_INSN (insn)); 860: last = get_last_insn (); 861: had_barrier = 1; 862: } 863: 864: /* Splice our SEQUENCE into the insn stream where INSN used to be. */ 865: NEXT_INSN (seq_insn) = NEXT_INSN (insn); 866: PREV_INSN (seq_insn) = PREV_INSN (insn); 867: 868: if (insn == last) 869: set_new_first_and_last_insn (first, seq_insn); 870: else 871: PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn; 872: 873: if (insn == first) 874: set_new_first_and_last_insn (seq_insn, last); 875: else 876: NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn; 877: 878: /* Build our SEQUENCE and rebuild the insn chain. */ 879: XVECEXP (seq, 0, 0) = delay_insn; 880: INSN_DELETED_P (delay_insn) = 0; 881: PREV_INSN (delay_insn) = PREV_INSN (seq_insn); 882: 883: for (li = list; li; li = XEXP (li, 1), i++) 884: { 885: rtx tem = XEXP (li, 0); 886: rtx note; 887: 888: /* Show that this copy of the insn isn't deleted. */ 889: INSN_DELETED_P (tem) = 0; 890: 891: XVECEXP (seq, 0, i) = tem; 892: PREV_INSN (tem) = XVECEXP (seq, 0, i - 1); 893: NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem; 894: 895: /* Remove any REG_DEAD notes because we can't rely on them now 896: that the insn has been moved. */ 897: for (note = REG_NOTES (tem); note; note = XEXP (note, 1)) 898: if (REG_NOTE_KIND (note) == REG_DEAD) 899: XEXP (note, 0) = const0_rtx; 900: } 901: 902: NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn); 903: 904: /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the 905: last insn in that SEQUENCE to point to us. Similarly for the first 906: insn in the following insn if it is a SEQUENCE. */ 907: 908: if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN 909: && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE) 910: NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0, 911: XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1)) 912: = seq_insn; 913: 914: if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN 915: && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE) 916: PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn; 917: 918: /* If there used to be a BARRIER, put it back. */ 919: if (had_barrier) 920: emit_barrier_after (seq_insn); 921: 922: if (i != length + 1) 923: abort (); 924: 925: return seq_insn; 926: } 927: 928: /* Add INSN to DELAY_LIST and return the head of the new list. The list must 929: be in the order in which the insns are to be executed. */ 930: 931: static rtx 932: add_to_delay_list (insn, delay_list) 933: rtx insn; 934: rtx delay_list; 935: { 1.1.1.5 root 936: /* If we have an empty list, just make a new list element. If 937: INSN has it's block number recorded, clear it since we may 938: be moving the insn to a new block. */ 939: 1.1 root 940: if (delay_list == 0) 1.1.1.5 root 941: { 942: struct target_info *tinfo; 943: 944: for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME]; 945: tinfo; tinfo = tinfo->next) 946: if (tinfo->uid == INSN_UID (insn)) 947: break; 948: 949: if (tinfo) 950: tinfo->block = -1; 951: 952: return gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX); 953: } 1.1 root 954: 955: /* Otherwise this must be an INSN_LIST. Add INSN to the end of the 956: list. */ 957: XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1)); 958: 959: return delay_list; 960: } 961: 962: /* Delete INSN from the the delay slot of the insn that it is in. This may 963: produce an insn without anything in its delay slots. */ 964: 965: static void 966: delete_from_delay_slot (insn) 967: rtx insn; 968: { 969: rtx trial, seq_insn, seq, prev; 970: rtx delay_list = 0; 971: int i; 972: 973: /* We first must find the insn containing the SEQUENCE with INSN in its 974: delay slot. Do this by finding an insn, TRIAL, where 975: PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */ 976: 977: for (trial = insn; 978: PREV_INSN (NEXT_INSN (trial)) == trial; 979: trial = NEXT_INSN (trial)) 980: ; 981: 982: seq_insn = PREV_INSN (NEXT_INSN (trial)); 983: seq = PATTERN (seq_insn); 984: 985: /* Create a delay list consisting of all the insns other than the one 986: we are deleting (unless we were the only one). */ 987: if (XVECLEN (seq, 0) > 2) 988: for (i = 1; i < XVECLEN (seq, 0); i++) 989: if (XVECEXP (seq, 0, i) != insn) 990: delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list); 991: 992: /* Delete the old SEQUENCE, re-emit the insn that used to have the delay 993: list, and rebuild the delay list if non-empty. */ 994: prev = PREV_INSN (seq_insn); 995: trial = XVECEXP (seq, 0, 0); 996: delete_insn (seq_insn); 997: add_insn_after (trial, prev); 998: 999: if (GET_CODE (trial) == JUMP_INSN 1000: && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN)) 1001: emit_barrier_after (trial); 1002: 1003: /* If there are any delay insns, remit them. Otherwise clear the 1004: annul flag. */ 1005: if (delay_list) 1006: trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0); 1007: else 1008: INSN_ANNULLED_BRANCH_P (trial) = 0; 1009: 1010: INSN_FROM_TARGET_P (insn) = 0; 1011: 1012: /* Show we need to fill this insn again. */ 1013: obstack_ptr_grow (&unfilled_slots_obstack, trial); 1014: } 1015: 1016: /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down 1017: the insn that sets CC0 for it and delete it too. */ 1018: 1019: static void 1020: delete_scheduled_jump (insn) 1021: rtx insn; 1022: { 1023: /* Delete the insn that sets cc0 for us. On machines without cc0, we could 1024: delete the insn that sets the condition code, but it is hard to find it. 1025: Since this case is rare anyway, don't bother trying; there would likely 1026: be other insns that became dead anyway, which we wouldn't know to 1027: delete. */ 1028: 1029: #ifdef HAVE_cc0 1030: if (reg_mentioned_p (cc0_rtx, insn)) 1031: { 1.1.1.4 root 1032: rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX); 1.1 root 1033: 1034: /* If a reg-note was found, it points to an insn to set CC0. This 1035: insn is in the delay list of some other insn. So delete it from 1036: the delay list it was in. */ 1037: if (note) 1038: { 1.1.1.4 root 1039: if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX) 1.1 root 1040: && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1) 1041: delete_from_delay_slot (XEXP (note, 0)); 1042: } 1043: else 1044: { 1045: /* The insn setting CC0 is our previous insn, but it may be in 1046: a delay slot. It will be the last insn in the delay slot, if 1047: it is. */ 1048: rtx trial = previous_insn (insn); 1049: if (GET_CODE (trial) == NOTE) 1050: trial = prev_nonnote_insn (trial); 1051: if (sets_cc0_p (PATTERN (trial)) != 1 1052: || FIND_REG_INC_NOTE (trial, 0)) 1053: return; 1054: if (PREV_INSN (NEXT_INSN (trial)) == trial) 1055: delete_insn (trial); 1056: else 1057: delete_from_delay_slot (trial); 1058: } 1059: } 1060: #endif 1061: 1062: delete_insn (insn); 1063: } 1064: 1065: /* Counters for delay-slot filling. */ 1066: 1067: #define NUM_REORG_FUNCTIONS 2 1068: #define MAX_DELAY_HISTOGRAM 3 1069: #define MAX_REORG_PASSES 2 1070: 1071: static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES]; 1072: 1073: static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES]; 1074: 1075: static int reorg_pass_number; 1076: 1077: static void 1078: note_delay_statistics (slots_filled, index) 1079: int slots_filled, index; 1080: { 1081: num_insns_needing_delays[index][reorg_pass_number]++; 1082: if (slots_filled > MAX_DELAY_HISTOGRAM) 1083: slots_filled = MAX_DELAY_HISTOGRAM; 1084: num_filled_delays[index][slots_filled][reorg_pass_number]++; 1085: } 1086: 1087: #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 1088: 1089: /* Optimize the following cases: 1090: 1091: 1. When a conditional branch skips over only one instruction, 1092: use an annulling branch and put that insn in the delay slot. 1.1.1.3 root 1093: Use either a branch that annuls when the condition if true or 1094: invert the test with a branch that annuls when the condition is 1.1 root 1095: false. This saves insns, since otherwise we must copy an insn 1096: from the L1 target. 1097: 1098: (orig) (skip) (otherwise) 1099: Bcc.n L1 Bcc',a L1 Bcc,a L1' 1100: insn insn insn2 1101: L1: L1: L1: 1102: insn2 insn2 insn2 1103: insn3 insn3 L1': 1104: insn3 1105: 1106: 2. When a conditional branch skips over only one instruction, 1107: and after that, it unconditionally branches somewhere else, 1108: perform the similar optimization. This saves executing the 1109: second branch in the case where the inverted condition is true. 1110: 1111: Bcc.n L1 Bcc',a L2 1112: insn insn 1113: L1: L1: 1114: Bra L2 Bra L2 1115: 1116: INSN is a JUMP_INSN. 1117: 1118: This should be expanded to skip over N insns, where N is the number 1119: of delay slots required. */ 1120: 1121: static rtx 1122: optimize_skip (insn) 1123: register rtx insn; 1124: { 1125: register rtx trial = next_nonnote_insn (insn); 1126: rtx next_trial = next_active_insn (trial); 1127: rtx delay_list = 0; 1128: rtx target_label; 1.1.1.5 root 1129: int flags; 1130: 1131: flags = get_jump_flags (insn, JUMP_LABEL (insn)); 1.1 root 1132: 1133: if (trial == 0 1134: || GET_CODE (trial) != INSN 1135: || GET_CODE (PATTERN (trial)) == SEQUENCE 1136: || recog_memoized (trial) < 0 1.1.1.5 root 1137: || (! eligible_for_annul_false (insn, 0, trial, flags) 1138: && ! eligible_for_annul_true (insn, 0, trial, flags))) 1.1 root 1139: return 0; 1140: 1141: /* There are two cases where we are just executing one insn (we assume 1142: here that a branch requires only one insn; this should be generalized 1143: at some point): Where the branch goes around a single insn or where 1144: we have one insn followed by a branch to the same label we branch to. 1145: In both of these cases, inverting the jump and annulling the delay 1146: slot give the same effect in fewer insns. */ 1147: if ((next_trial == next_active_insn (JUMP_LABEL (insn))) 1148: || (next_trial != 0 1149: && GET_CODE (next_trial) == JUMP_INSN 1150: && JUMP_LABEL (insn) == JUMP_LABEL (next_trial) 1151: && (simplejump_p (next_trial) 1152: || GET_CODE (PATTERN (next_trial)) == RETURN))) 1153: { 1.1.1.5 root 1154: if (eligible_for_annul_false (insn, 0, trial, flags)) 1.1 root 1155: { 1156: if (invert_jump (insn, JUMP_LABEL (insn))) 1157: INSN_FROM_TARGET_P (trial) = 1; 1.1.1.5 root 1158: else if (! eligible_for_annul_true (insn, 0, trial, flags)) 1.1 root 1159: return 0; 1160: } 1161: 1.1.1.4 root 1162: delay_list = add_to_delay_list (trial, NULL_RTX); 1.1 root 1163: next_trial = next_active_insn (trial); 1164: update_block (trial, trial); 1165: delete_insn (trial); 1166: 1167: /* Also, if we are targeting an unconditional 1168: branch, thread our jump to the target of that branch. Don't 1169: change this into a RETURN here, because it may not accept what 1170: we have in the delay slot. We'll fix this up later. */ 1171: if (next_trial && GET_CODE (next_trial) == JUMP_INSN 1172: && (simplejump_p (next_trial) 1173: || GET_CODE (PATTERN (next_trial)) == RETURN)) 1174: { 1175: target_label = JUMP_LABEL (next_trial); 1176: if (target_label == 0) 1177: target_label = find_end_label (); 1.1.1.6 root 1178: 1179: /* Recompute the flags based on TARGET_LABEL since threading 1180: the jump to TARGET_LABEL may change the direction of the 1181: jump (which may change the circumstances in which the 1182: delay slot is nullified). */ 1183: flags = get_jump_flags (insn, target_label); 1184: if (eligible_for_annul_true (insn, 0, trial, flags)) 1185: reorg_redirect_jump (insn, target_label); 1.1 root 1186: } 1187: 1188: INSN_ANNULLED_BRANCH_P (insn) = 1; 1189: } 1190: 1191: return delay_list; 1192: } 1193: #endif 1194: 1.1.1.5 root 1195: 1196: /* Encode and return branch direction and prediction information for 1197: INSN assuming it will jump to LABEL. 1198: 1199: Non conditional branches return no direction information and 1200: are predicted as very likely taken. */ 1201: static int 1202: get_jump_flags (insn, label) 1203: rtx insn, label; 1204: { 1205: int flags; 1206: 1207: /* get_jump_flags can be passed any insn with delay slots, these may 1208: be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch 1209: direction information, and only if they are conditional jumps. 1210: 1211: If LABEL is zero, then there is no way to determine the branch 1212: direction. */ 1213: if (GET_CODE (insn) == JUMP_INSN 1.1.1.7 ! root 1214: && (condjump_p (insn) || condjump_in_parallel_p (insn)) 1.1.1.5 root 1215: && INSN_UID (insn) <= max_uid 1216: && label != 0 1217: && INSN_UID (label) <= max_uid) 1218: flags 1219: = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)]) 1220: ? ATTR_FLAG_forward : ATTR_FLAG_backward; 1221: /* No valid direction information. */ 1222: else 1223: flags = 0; 1224: 1225: /* If insn is a conditional branch call mostly_true_jump to get 1226: determine the branch prediction. 1227: 1228: Non conditional branches are predicted as very likely taken. */ 1229: if (GET_CODE (insn) == JUMP_INSN 1.1.1.7 ! root 1230: && (condjump_p (insn) || condjump_in_parallel_p (insn))) 1.1.1.5 root 1231: { 1232: int prediction; 1233: 1234: prediction = mostly_true_jump (insn, get_branch_condition (insn, label)); 1235: switch (prediction) 1236: { 1237: case 2: 1238: flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 1239: break; 1240: case 1: 1241: flags |= ATTR_FLAG_likely; 1242: break; 1243: case 0: 1244: flags |= ATTR_FLAG_unlikely; 1245: break; 1246: case -1: 1247: flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely); 1248: break; 1249: 1250: default: 1251: abort(); 1252: } 1253: } 1254: else 1255: flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely); 1256: 1257: return flags; 1258: } 1259: 1.1.1.6 root 1260: /* Return 1 if INSN is a destination that will be branched to rarely (the 1.1.1.5 root 1261: return point of a function); return 2 if DEST will be branched to very 1262: rarely (a call to a function that doesn't return). Otherwise, 1263: return 0. */ 1264: 1265: static int 1266: rare_destination (insn) 1267: rtx insn; 1268: { 1269: int jump_count = 0; 1.1.1.6 root 1270: rtx next; 1.1.1.5 root 1271: 1.1.1.6 root 1272: for (; insn; insn = next) 1.1.1.5 root 1273: { 1274: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE) 1275: insn = XVECEXP (PATTERN (insn), 0, 0); 1276: 1.1.1.6 root 1277: next = NEXT_INSN (insn); 1278: 1.1.1.5 root 1279: switch (GET_CODE (insn)) 1280: { 1281: case CODE_LABEL: 1282: return 0; 1283: case BARRIER: 1284: /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We 1285: don't scan past JUMP_INSNs, so any barrier we find here must 1286: have been after a CALL_INSN and hence mean the call doesn't 1287: return. */ 1288: return 2; 1289: case JUMP_INSN: 1290: if (GET_CODE (PATTERN (insn)) == RETURN) 1291: return 1; 1292: else if (simplejump_p (insn) 1293: && jump_count++ < 10) 1.1.1.6 root 1294: next = JUMP_LABEL (insn); 1.1.1.5 root 1295: else 1296: return 0; 1297: } 1298: } 1299: 1300: /* If we got here it means we hit the end of the function. So this 1301: is an unlikely destination. */ 1302: 1303: return 1; 1304: } 1305: 1.1 root 1306: /* Return truth value of the statement that this branch 1307: is mostly taken. If we think that the branch is extremely likely 1308: to be taken, we return 2. If the branch is slightly more likely to be 1.1.1.5 root 1309: taken, return 1. If the branch is slightly less likely to be taken, 1310: return 0 and if the branch is highly unlikely to be taken, return -1. 1.1 root 1311: 1312: CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */ 1313: 1314: static int 1315: mostly_true_jump (jump_insn, condition) 1316: rtx jump_insn, condition; 1317: { 1318: rtx target_label = JUMP_LABEL (jump_insn); 1319: rtx insn; 1.1.1.5 root 1320: int rare_dest = rare_destination (target_label); 1321: int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn)); 1.1 root 1322: 1.1.1.5 root 1323: /* If this is a branch outside a loop, it is highly unlikely. */ 1324: if (GET_CODE (PATTERN (jump_insn)) == SET 1325: && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE 1326: && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF 1327: && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1))) 1328: || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF 1329: && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2))))) 1330: return -1; 1331: 1332: if (target_label) 1333: { 1334: /* If this is the test of a loop, it is very likely true. We scan 1335: backwards from the target label. If we find a NOTE_INSN_LOOP_BEG 1336: before the next real insn, we assume the branch is to the top of 1337: the loop. */ 1338: for (insn = PREV_INSN (target_label); 1339: insn && GET_CODE (insn) == NOTE; 1340: insn = PREV_INSN (insn)) 1341: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1342: return 2; 1343: 1344: /* If this is a jump to the test of a loop, it is likely true. We scan 1345: forwards from the target label. If we find a NOTE_INSN_LOOP_VTOP 1346: before the next real insn, we assume the branch is to the loop branch 1347: test. */ 1348: for (insn = NEXT_INSN (target_label); 1349: insn && GET_CODE (insn) == NOTE; 1350: insn = PREV_INSN (insn)) 1351: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP) 1352: return 1; 1353: } 1354: 1355: /* Look at the relative rarities of the fallthough and destination. If 1356: they differ, we can predict the branch that way. */ 1357: 1358: switch (rare_fallthrough - rare_dest) 1359: { 1360: case -2: 1361: return -1; 1362: case -1: 1363: return 0; 1364: case 0: 1365: break; 1366: case 1: 1367: return 1; 1368: case 2: 1.1 root 1369: return 2; 1.1.1.5 root 1370: } 1.1 root 1371: 1372: /* If we couldn't figure out what this jump was, assume it won't be 1373: taken. This should be rare. */ 1374: if (condition == 0) 1375: return 0; 1376: 1377: /* EQ tests are usually false and NE tests are usually true. Also, 1378: most quantities are positive, so we can make the appropriate guesses 1379: about signed comparisons against zero. */ 1380: switch (GET_CODE (condition)) 1381: { 1382: case CONST_INT: 1383: /* Unconditional branch. */ 1384: return 1; 1385: case EQ: 1386: return 0; 1387: case NE: 1388: return 1; 1389: case LE: 1390: case LT: 1391: if (XEXP (condition, 1) == const0_rtx) 1392: return 0; 1393: break; 1394: case GE: 1395: case GT: 1396: if (XEXP (condition, 1) == const0_rtx) 1397: return 1; 1398: break; 1399: } 1400: 1401: /* Predict backward branches usually take, forward branches usually not. If 1402: we don't know whether this is forward or backward, assume the branch 1403: will be taken, since most are. */ 1.1.1.5 root 1404: return (target_label == 0 || INSN_UID (jump_insn) > max_uid 1405: || INSN_UID (target_label) > max_uid 1.1 root 1406: || (uid_to_ruid[INSN_UID (jump_insn)] 1407: > uid_to_ruid[INSN_UID (target_label)]));; 1408: } 1409: 1410: /* Return the condition under which INSN will branch to TARGET. If TARGET 1411: is zero, return the condition under which INSN will return. If INSN is 1412: an unconditional branch, return const_true_rtx. If INSN isn't a simple 1413: type of jump, or it doesn't go to TARGET, return 0. */ 1414: 1415: static rtx 1416: get_branch_condition (insn, target) 1417: rtx insn; 1418: rtx target; 1419: { 1420: rtx pat = PATTERN (insn); 1421: rtx src; 1422: 1.1.1.7 ! root 1423: if (condjump_in_parallel_p (insn)) ! 1424: pat = XVECEXP (pat, 0, 0); ! 1425: 1.1 root 1426: if (GET_CODE (pat) == RETURN) 1427: return target == 0 ? const_true_rtx : 0; 1428: 1429: else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx) 1430: return 0; 1431: 1432: src = SET_SRC (pat); 1433: if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target) 1434: return const_true_rtx; 1435: 1436: else if (GET_CODE (src) == IF_THEN_ELSE 1437: && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN) 1438: || (GET_CODE (XEXP (src, 1)) == LABEL_REF 1439: && XEXP (XEXP (src, 1), 0) == target)) 1440: && XEXP (src, 2) == pc_rtx) 1441: return XEXP (src, 0); 1442: 1443: else if (GET_CODE (src) == IF_THEN_ELSE 1444: && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN) 1445: || (GET_CODE (XEXP (src, 2)) == LABEL_REF 1446: && XEXP (XEXP (src, 2), 0) == target)) 1447: && XEXP (src, 1) == pc_rtx) 1448: return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))), 1449: GET_MODE (XEXP (src, 0)), 1450: XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1)); 1.1.1.4 root 1451: 1452: return 0; 1.1 root 1453: } 1454: 1455: /* Return non-zero if CONDITION is more strict than the condition of 1456: INSN, i.e., if INSN will always branch if CONDITION is true. */ 1457: 1458: static int 1459: condition_dominates_p (condition, insn) 1460: rtx condition; 1461: rtx insn; 1462: { 1463: rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn)); 1464: enum rtx_code code = GET_CODE (condition); 1465: enum rtx_code other_code; 1466: 1467: if (rtx_equal_p (condition, other_condition) 1468: || other_condition == const_true_rtx) 1469: return 1; 1470: 1471: else if (condition == const_true_rtx || other_condition == 0) 1472: return 0; 1473: 1474: other_code = GET_CODE (other_condition); 1475: if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2 1476: || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0)) 1477: || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1))) 1478: return 0; 1479: 1480: return comparison_dominates_p (code, other_code); 1481: } 1.1.1.6 root 1482: 1483: /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate 1484: any insns already in the delay slot of JUMP. */ 1485: 1486: static int 1487: redirect_with_delay_slots_safe_p (jump, newlabel, seq) 1488: rtx jump, newlabel, seq; 1489: { 1490: int flags, slots, i; 1491: rtx pat = PATTERN (seq); 1492: 1493: /* Make sure all the delay slots of this jump would still 1494: be valid after threading the jump. If they are still 1495: valid, then return non-zero. */ 1496: 1497: flags = get_jump_flags (jump, newlabel); 1498: for (i = 1; i < XVECLEN (pat, 0); i++) 1499: if (! ( 1500: #ifdef ANNUL_IFFALSE_SLOTS 1501: (INSN_ANNULLED_BRANCH_P (jump) 1502: && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 1503: ? eligible_for_annul_false (jump, i - 1, 1504: XVECEXP (pat, 0, i), flags) : 1505: #endif 1506: #ifdef ANNUL_IFTRUE_SLOTS 1507: (INSN_ANNULLED_BRANCH_P (jump) 1508: && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 1509: ? eligible_for_annul_true (jump, i - 1, 1510: XVECEXP (pat, 0, i), flags) : 1511: #endif 1512: eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags))) 1513: break; 1514: 1515: return (i == XVECLEN (pat, 0)); 1516: } 1517: 1.1.1.7 ! root 1518: /* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate ! 1519: any insns we wish to place in the delay slot of JUMP. */ ! 1520: ! 1521: static int ! 1522: redirect_with_delay_list_safe_p (jump, newlabel, delay_list) ! 1523: rtx jump, newlabel, delay_list; ! 1524: { ! 1525: int flags, i; ! 1526: rtx li; ! 1527: ! 1528: /* Make sure all the insns in DELAY_LIST would still be ! 1529: valid after threading the jump. If they are still ! 1530: valid, then return non-zero. */ ! 1531: ! 1532: flags = get_jump_flags (jump, newlabel); ! 1533: for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++) ! 1534: if (! ( ! 1535: #ifdef ANNUL_IFFALSE_SLOTS ! 1536: (INSN_ANNULLED_BRANCH_P (jump) ! 1537: && INSN_FROM_TARGET_P (XEXP (li, 0))) ! 1538: ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) : ! 1539: #endif ! 1540: #ifdef ANNUL_IFTRUE_SLOTS ! 1541: (INSN_ANNULLED_BRANCH_P (jump) ! 1542: && ! INSN_FROM_TARGET_P (XEXP (li, 0))) ! 1543: ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) : ! 1544: #endif ! 1545: eligible_for_delay (jump, i, XEXP (li, 0), flags))) ! 1546: break; ! 1547: ! 1548: return (li == NULL); ! 1549: } ! 1550: 1.1 root 1551: 1552: /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that 1553: the condition tested by INSN is CONDITION and the resources shown in 1554: OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns 1555: from SEQ's delay list, in addition to whatever insns it may execute 1556: (in DELAY_LIST). SETS and NEEDED are denote resources already set and 1557: needed while searching for delay slot insns. Return the concatenated 1558: delay list if possible, otherwise, return 0. 1559: 1560: SLOTS_TO_FILL is the total number of slots required by INSN, and 1561: PSLOTS_FILLED points to the number filled so far (also the number of 1562: insns in DELAY_LIST). It is updated with the number that have been 1563: filled from the SEQUENCE, if any. 1564: 1565: PANNUL_P points to a non-zero value if we already know that we need 1566: to annul INSN. If this routine determines that annulling is needed, 1567: it may set that value non-zero. 1568: 1569: PNEW_THREAD points to a location that is to receive the place at which 1570: execution should continue. */ 1571: 1572: static rtx 1573: steal_delay_list_from_target (insn, condition, seq, delay_list, 1574: sets, needed, other_needed, 1575: slots_to_fill, pslots_filled, pannul_p, 1576: pnew_thread) 1577: rtx insn, condition; 1578: rtx seq; 1579: rtx delay_list; 1580: struct resources *sets, *needed, *other_needed; 1581: int slots_to_fill; 1582: int *pslots_filled; 1583: int *pannul_p; 1584: rtx *pnew_thread; 1585: { 1586: rtx temp; 1587: int slots_remaining = slots_to_fill - *pslots_filled; 1588: int total_slots_filled = *pslots_filled; 1589: rtx new_delay_list = 0; 1590: int must_annul = *pannul_p; 1591: int i; 1592: 1593: /* We can't do anything if there are more delay slots in SEQ than we 1594: can handle, or if we don't know that it will be a taken branch. 1595: 1596: We know that it will be a taken branch if it is either an unconditional 1597: branch or a conditional branch with a stricter branch condition. */ 1598: 1599: if (XVECLEN (seq, 0) - 1 > slots_remaining 1600: || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))) 1601: return delay_list; 1602: 1603: for (i = 1; i < XVECLEN (seq, 0); i++) 1604: { 1605: rtx trial = XVECEXP (seq, 0, i); 1.1.1.5 root 1606: int flags; 1.1 root 1607: 1608: if (insn_references_resource_p (trial, sets, 0) 1609: || insn_sets_resource_p (trial, needed, 0) 1610: || insn_sets_resource_p (trial, sets, 0) 1611: #ifdef HAVE_cc0 1612: /* If TRIAL sets CC0, we can't copy it, so we can't steal this 1613: delay list. */ 1.1.1.4 root 1614: || find_reg_note (trial, REG_CC_USER, NULL_RTX) 1.1 root 1615: #endif 1616: /* If TRIAL is from the fallthrough code of an annulled branch insn 1617: in SEQ, we cannot use it. */ 1618: || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0)) 1619: && ! INSN_FROM_TARGET_P (trial))) 1620: return delay_list; 1621: 1622: /* If this insn was already done (usually in a previous delay slot), 1623: pretend we put it in our delay slot. */ 1624: if (redundant_insn_p (trial, insn, new_delay_list)) 1625: continue; 1626: 1.1.1.5 root 1627: /* We will end up re-vectoring this branch, so compute flags 1628: based on jumping to the new label. */ 1629: flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0))); 1630: 1.1 root 1631: if (! must_annul 1632: && ((condition == const_true_rtx 1633: || (! insn_sets_resource_p (trial, other_needed, 0) 1634: && ! may_trap_p (PATTERN (trial))))) 1.1.1.5 root 1635: ? eligible_for_delay (insn, total_slots_filled, trial, flags) 1.1 root 1636: : (must_annul = 1, 1.1.1.5 root 1637: eligible_for_annul_false (insn, total_slots_filled, trial, flags))) 1.1 root 1638: { 1639: temp = copy_rtx (trial); 1640: INSN_FROM_TARGET_P (temp) = 1; 1641: new_delay_list = add_to_delay_list (temp, new_delay_list); 1642: total_slots_filled++; 1643: 1644: if (--slots_remaining == 0) 1645: break; 1646: } 1647: else 1648: return delay_list; 1649: } 1650: 1651: /* Show the place to which we will be branching. */ 1652: *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0))); 1653: 1654: /* Add any new insns to the delay list and update the count of the 1655: number of slots filled. */ 1656: *pslots_filled = total_slots_filled; 1657: *pannul_p = must_annul; 1658: 1659: if (delay_list == 0) 1660: return new_delay_list; 1661: 1662: for (temp = new_delay_list; temp; temp = XEXP (temp, 1)) 1663: delay_list = add_to_delay_list (XEXP (temp, 0), delay_list); 1664: 1665: return delay_list; 1666: } 1667: 1668: /* Similar to steal_delay_list_from_target except that SEQ is on the 1669: fallthrough path of INSN. Here we only do something if the delay insn 1670: of SEQ is an unconditional branch. In that case we steal its delay slot 1671: for INSN since unconditional branches are much easier to fill. */ 1672: 1673: static rtx 1674: steal_delay_list_from_fallthrough (insn, condition, seq, 1675: delay_list, sets, needed, other_needed, 1676: slots_to_fill, pslots_filled, pannul_p) 1677: rtx insn, condition; 1678: rtx seq; 1679: rtx delay_list; 1680: struct resources *sets, *needed, *other_needed; 1681: int slots_to_fill; 1682: int *pslots_filled; 1683: int *pannul_p; 1684: { 1685: int i; 1.1.1.5 root 1686: int flags; 1687: 1688: flags = get_jump_flags (insn, JUMP_LABEL (insn)); 1.1 root 1689: 1690: /* We can't do anything if SEQ's delay insn isn't an 1691: unconditional branch. */ 1692: 1693: if (! simplejump_p (XVECEXP (seq, 0, 0)) 1694: && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN) 1695: return delay_list; 1696: 1697: for (i = 1; i < XVECLEN (seq, 0); i++) 1698: { 1699: rtx trial = XVECEXP (seq, 0, i); 1700: 1701: /* If TRIAL sets CC0, stealing it will move it too far from the use 1702: of CC0. */ 1703: if (insn_references_resource_p (trial, sets, 0) 1704: || insn_sets_resource_p (trial, needed, 0) 1705: || insn_sets_resource_p (trial, sets, 0) 1706: #ifdef HAVE_cc0 1707: || sets_cc0_p (PATTERN (trial)) 1708: #endif 1709: ) 1710: 1711: break; 1712: 1713: /* If this insn was already done, we don't need it. */ 1714: if (redundant_insn_p (trial, insn, delay_list)) 1715: { 1716: delete_from_delay_slot (trial); 1717: continue; 1718: } 1719: 1720: if (! *pannul_p 1721: && ((condition == const_true_rtx 1722: || (! insn_sets_resource_p (trial, other_needed, 0) 1723: && ! may_trap_p (PATTERN (trial))))) 1.1.1.5 root 1724: ? eligible_for_delay (insn, *pslots_filled, trial, flags) 1.1 root 1725: : (*pannul_p = 1, 1.1.1.5 root 1726: eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 1.1 root 1727: { 1728: delete_from_delay_slot (trial); 1729: delay_list = add_to_delay_list (trial, delay_list); 1730: 1731: if (++(*pslots_filled) == slots_to_fill) 1732: break; 1733: } 1734: else 1735: break; 1736: } 1737: 1738: return delay_list; 1739: } 1740: 1741: /* Try merging insns starting at THREAD which match exactly the insns in 1742: INSN's delay list. 1743: 1744: If all insns were matched and the insn was previously annulling, the 1745: annul bit will be cleared. 1746: 1747: For each insn that is merged, if the branch is or will be non-annulling, 1748: we delete the merged insn. */ 1749: 1750: static void 1751: try_merge_delay_insns (insn, thread) 1752: rtx insn, thread; 1753: { 1754: rtx trial, next_trial; 1755: rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0); 1756: int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn); 1757: int slot_number = 1; 1758: int num_slots = XVECLEN (PATTERN (insn), 0); 1759: rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1760: struct resources set, needed; 1761: rtx merged_insns = 0; 1762: int i; 1.1.1.5 root 1763: int flags; 1764: 1.1.1.6 root 1765: flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn)); 1.1 root 1766: 1767: CLEAR_RESOURCE (&needed); 1768: CLEAR_RESOURCE (&set); 1769: 1770: /* If this is not an annulling branch, take into account anything needed in 1771: NEXT_TO_MATCH. This prevents two increments from being incorrectly 1772: folded into one. If we are annulling, this would be the correct 1773: thing to do. (The alternative, looking at things set in NEXT_TO_MATCH 1774: will essentially disable this optimization. This method is somewhat of 1775: a kludge, but I don't see a better way.) */ 1776: if (! annul_p) 1777: mark_referenced_resources (next_to_match, &needed, 1); 1778: 1779: for (trial = thread; !stop_search_p (trial, 1); trial = next_trial) 1780: { 1781: rtx pat = PATTERN (trial); 1.1.1.7 ! root 1782: rtx oldtrial = trial; 1.1 root 1783: 1784: next_trial = next_nonnote_insn (trial); 1785: 1786: /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */ 1787: if (GET_CODE (trial) == INSN 1788: && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)) 1789: continue; 1790: 1791: if (GET_CODE (next_to_match) == GET_CODE (trial) 1792: #ifdef HAVE_cc0 1793: /* We can't share an insn that sets cc0. */ 1794: && ! sets_cc0_p (pat) 1795: #endif 1796: && ! insn_references_resource_p (trial, &set, 1) 1797: && ! insn_sets_resource_p (trial, &set, 1) 1798: && ! insn_sets_resource_p (trial, &needed, 1) 1799: && (trial = try_split (pat, trial, 0)) != 0 1.1.1.7 ! root 1800: /* Update next_trial, in case try_split succeeded. */ ! 1801: && (next_trial = next_nonnote_insn (trial)) ! 1802: /* Likewise THREAD. */ ! 1803: && (thread = oldtrial == thread ? trial : thread) 1.1 root 1804: && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial)) 1805: /* Have to test this condition if annul condition is different 1806: from (and less restrictive than) non-annulling one. */ 1.1.1.5 root 1807: && eligible_for_delay (delay_insn, slot_number - 1, trial, flags)) 1.1 root 1808: { 1809: 1810: if (! annul_p) 1811: { 1812: update_block (trial, thread); 1.1.1.7 ! root 1813: if (trial == thread) ! 1814: thread = next_active_insn (thread); ! 1815: 1.1 root 1816: delete_insn (trial); 1817: INSN_FROM_TARGET_P (next_to_match) = 0; 1818: } 1819: else 1820: merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns); 1821: 1822: if (++slot_number == num_slots) 1823: break; 1824: 1825: next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1826: if (! annul_p) 1827: mark_referenced_resources (next_to_match, &needed, 1); 1828: } 1829: 1.1.1.4 root 1830: mark_set_resources (trial, &set, 0, 1); 1.1 root 1831: mark_referenced_resources (trial, &needed, 1); 1832: } 1833: 1834: /* See if we stopped on a filled insn. If we did, try to see if its 1835: delay slots match. */ 1836: if (slot_number != num_slots 1837: && trial && GET_CODE (trial) == INSN 1838: && GET_CODE (PATTERN (trial)) == SEQUENCE 1839: && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0))) 1840: { 1841: rtx pat = PATTERN (trial); 1.1.1.7 ! root 1842: rtx filled_insn = XVECEXP (pat, 0, 0); ! 1843: ! 1844: /* Account for resources set/needed by the filled insn. */ ! 1845: mark_set_resources (filled_insn, &set, 0, 1); ! 1846: mark_referenced_resources (filled_insn, &needed, 1); 1.1 root 1847: 1848: for (i = 1; i < XVECLEN (pat, 0); i++) 1849: { 1850: rtx dtrial = XVECEXP (pat, 0, i); 1851: 1852: if (! insn_references_resource_p (dtrial, &set, 1) 1853: && ! insn_sets_resource_p (dtrial, &set, 1) 1854: && ! insn_sets_resource_p (dtrial, &needed, 1) 1855: #ifdef HAVE_cc0 1856: && ! sets_cc0_p (PATTERN (dtrial)) 1857: #endif 1858: && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial)) 1.1.1.5 root 1859: && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags)) 1.1 root 1860: { 1861: if (! annul_p) 1862: { 1863: update_block (dtrial, thread); 1864: delete_from_delay_slot (dtrial); 1865: INSN_FROM_TARGET_P (next_to_match) = 0; 1866: } 1867: else 1868: merged_insns = gen_rtx (INSN_LIST, SImode, dtrial, 1869: merged_insns); 1870: 1871: if (++slot_number == num_slots) 1872: break; 1873: 1874: next_to_match = XVECEXP (PATTERN (insn), 0, slot_number); 1875: } 1876: } 1877: } 1878: 1879: /* If all insns in the delay slot have been matched and we were previously 1880: annulling the branch, we need not any more. In that case delete all the 1881: merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn the 1882: the delay list so that we know that it isn't only being used at the 1883: target. */ 1.1.1.7 ! root 1884: if (slot_number == num_slots && annul_p) 1.1 root 1885: { 1886: for (; merged_insns; merged_insns = XEXP (merged_insns, 1)) 1887: { 1888: if (GET_MODE (merged_insns) == SImode) 1889: { 1890: update_block (XEXP (merged_insns, 0), thread); 1891: delete_from_delay_slot (XEXP (merged_insns, 0)); 1892: } 1893: else 1894: { 1895: update_block (XEXP (merged_insns, 0), thread); 1896: delete_insn (XEXP (merged_insns, 0)); 1897: } 1898: } 1899: 1900: INSN_ANNULLED_BRANCH_P (delay_insn) = 0; 1901: 1902: for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 1903: INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0; 1904: } 1905: } 1906: 1907: /* See if INSN is redundant with an insn in front of TARGET. Often this 1908: is called when INSN is a candidate for a delay slot of TARGET. 1909: DELAY_LIST are insns that will be placed in delay slots of TARGET in front 1910: of INSN. Often INSN will be redundant with an insn in a delay slot of 1911: some previous insn. This happens when we have a series of branches to the 1912: same label; in that case the first insn at the target might want to go 1913: into each of the delay slots. 1914: 1915: If we are not careful, this routine can take up a significant fraction 1916: of the total compilation time (4%), but only wins rarely. Hence we 1917: speed this routine up by making two passes. The first pass goes back 1918: until it hits a label and sees if it find an insn with an identical 1919: pattern. Only in this (relatively rare) event does it check for 1920: data conflicts. 1921: 1922: We do not split insns we encounter. This could cause us not to find a 1923: redundant insn, but the cost of splitting seems greater than the possible 1924: gain in rare cases. */ 1925: 1.1.1.7 ! root 1926: static rtx 1.1 root 1927: redundant_insn_p (insn, target, delay_list) 1928: rtx insn; 1929: rtx target; 1930: rtx delay_list; 1931: { 1932: rtx target_main = target; 1933: rtx ipat = PATTERN (insn); 1934: rtx trial, pat; 1935: struct resources needed, set; 1936: int i; 1937: 1938: /* Scan backwards looking for a match. */ 1939: for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial)) 1940: { 1941: if (GET_CODE (trial) == CODE_LABEL) 1942: return 0; 1943: 1.1.1.5 root 1944: if (GET_RTX_CLASS (GET_CODE (trial)) != 'i') 1.1 root 1945: continue; 1946: 1947: pat = PATTERN (trial); 1948: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 1949: continue; 1950: 1951: if (GET_CODE (pat) == SEQUENCE) 1952: { 1.1.1.5 root 1953: /* Stop for a CALL and its delay slots because it is difficult to 1954: track its resource needs correctly. */ 1.1 root 1955: if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN) 1956: return 0; 1957: 1.1.1.5 root 1958: /* Stop for an INSN or JUMP_INSN with delayed effects and its delay 1959: slots because it is difficult to track its resource needs 1960: correctly. */ 1961: 1962: #ifdef INSN_SETS_ARE_DELAYED 1963: if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1964: return 0; 1965: #endif 1966: 1967: #ifdef INSN_REFERENCES_ARE_DELAYED 1968: if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 1969: return 0; 1970: #endif 1971: 1972: /* See if any of the insns in the delay slot match, updating 1973: resource requirements as we go. */ 1.1 root 1974: for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 1975: if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn) 1976: && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat)) 1977: break; 1978: 1979: /* If found a match, exit this loop early. */ 1980: if (i > 0) 1981: break; 1982: } 1983: 1984: else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)) 1985: break; 1986: } 1987: 1988: /* If we didn't find an insn that matches, return 0. */ 1989: if (trial == 0) 1990: return 0; 1991: 1992: /* See what resources this insn sets and needs. If they overlap, or 1993: if this insn references CC0, it can't be redundant. */ 1994: 1995: CLEAR_RESOURCE (&needed); 1996: CLEAR_RESOURCE (&set); 1.1.1.4 root 1997: mark_set_resources (insn, &set, 0, 1); 1.1 root 1998: mark_referenced_resources (insn, &needed, 1); 1999: 2000: /* If TARGET is a SEQUENCE, get the main insn. */ 2001: if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE) 2002: target_main = XVECEXP (PATTERN (target), 0, 0); 2003: 2004: if (resource_conflicts_p (&needed, &set) 2005: #ifdef HAVE_cc0 2006: || reg_mentioned_p (cc0_rtx, ipat) 2007: #endif 2008: /* The insn requiring the delay may not set anything needed or set by 2009: INSN. */ 2010: || insn_sets_resource_p (target_main, &needed, 1) 2011: || insn_sets_resource_p (target_main, &set, 1)) 2012: return 0; 2013: 2014: /* Insns we pass may not set either NEEDED or SET, so merge them for 2015: simpler tests. */ 2016: needed.memory |= set.memory; 2017: IOR_HARD_REG_SET (needed.regs, set.regs); 2018: 2019: /* This insn isn't redundant if it conflicts with an insn that either is 2020: or will be in a delay slot of TARGET. */ 2021: 2022: while (delay_list) 2023: { 2024: if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1)) 2025: return 0; 2026: delay_list = XEXP (delay_list, 1); 2027: } 2028: 2029: if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE) 2030: for (i = 1; i < XVECLEN (PATTERN (target), 0); i++) 2031: if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1)) 2032: return 0; 2033: 2034: /* Scan backwards until we reach a label or an insn that uses something 2035: INSN sets or sets something insn uses or sets. */ 2036: 2037: for (trial = PREV_INSN (target); 2038: trial && GET_CODE (trial) != CODE_LABEL; 2039: trial = PREV_INSN (trial)) 2040: { 2041: if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN 2042: && GET_CODE (trial) != JUMP_INSN) 2043: continue; 2044: 2045: pat = PATTERN (trial); 2046: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2047: continue; 2048: 2049: if (GET_CODE (pat) == SEQUENCE) 2050: { 2051: /* If this is a CALL_INSN and its delay slots, it is hard to track 2052: the resource needs properly, so give up. */ 2053: if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN) 2054: return 0; 2055: 1.1.1.5 root 2056: /* If this this is an INSN or JUMP_INSN with delayed effects, it 2057: is hard to track the resource needs properly, so give up. */ 2058: 2059: #ifdef INSN_SETS_ARE_DELAYED 2060: if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0))) 2061: return 0; 2062: #endif 2063: 2064: #ifdef INSN_REFERENCES_ARE_DELAYED 2065: if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0))) 2066: return 0; 2067: #endif 2068: 1.1 root 2069: /* See if any of the insns in the delay slot match, updating 2070: resource requirements as we go. */ 2071: for (i = XVECLEN (pat, 0) - 1; i > 0; i--) 2072: { 2073: rtx candidate = XVECEXP (pat, 0, i); 2074: 2075: /* If an insn will be annulled if the branch is false, it isn't 2076: considered as a possible duplicate insn. */ 2077: if (rtx_equal_p (PATTERN (candidate), ipat) 2078: && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 2079: && INSN_FROM_TARGET_P (candidate))) 2080: { 2081: /* Show that this insn will be used in the sequel. */ 2082: INSN_FROM_TARGET_P (candidate) = 0; 1.1.1.7 ! root 2083: return candidate; 1.1 root 2084: } 2085: 2086: /* Unless this is an annulled insn from the target of a branch, 2087: we must stop if it sets anything needed or set by INSN. */ 2088: if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0)) 2089: || ! INSN_FROM_TARGET_P (candidate)) 2090: && insn_sets_resource_p (candidate, &needed, 1)) 2091: return 0; 2092: } 2093: 2094: 2095: /* If the insn requiring the delay slot conflicts with INSN, we 2096: must stop. */ 2097: if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1)) 2098: return 0; 2099: } 2100: else 2101: { 2102: /* See if TRIAL is the same as INSN. */ 2103: pat = PATTERN (trial); 2104: if (rtx_equal_p (pat, ipat)) 1.1.1.7 ! root 2105: return trial; 1.1 root 2106: 2107: /* Can't go any further if TRIAL conflicts with INSN. */ 2108: if (insn_sets_resource_p (trial, &needed, 1)) 2109: return 0; 2110: } 2111: } 2112: 2113: return 0; 2114: } 2115: 2116: /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero, 2117: it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH 2118: is non-zero, we are allowed to fall into this thread; otherwise, we are 2119: not. 2120: 2121: If LABEL is used more than one or we pass a label other than LABEL before 2122: finding an active insn, we do not own this thread. */ 2123: 2124: static int 2125: own_thread_p (thread, label, allow_fallthrough) 2126: rtx thread; 2127: rtx label; 2128: int allow_fallthrough; 2129: { 2130: rtx active_insn; 2131: rtx insn; 2132: 2133: /* We don't own the function end. */ 2134: if (thread == 0) 2135: return 0; 2136: 2137: /* Get the first active insn, or THREAD, if it is an active insn. */ 2138: active_insn = next_active_insn (PREV_INSN (thread)); 2139: 2140: for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn)) 2141: if (GET_CODE (insn) == CODE_LABEL 2142: && (insn != label || LABEL_NUSES (insn) != 1)) 2143: return 0; 2144: 2145: if (allow_fallthrough) 2146: return 1; 2147: 2148: /* Ensure that we reach a BARRIER before any insn or label. */ 2149: for (insn = prev_nonnote_insn (thread); 2150: insn == 0 || GET_CODE (insn) != BARRIER; 2151: insn = prev_nonnote_insn (insn)) 2152: if (insn == 0 2153: || GET_CODE (insn) == CODE_LABEL 2154: || (GET_CODE (insn) == INSN 2155: && GET_CODE (PATTERN (insn)) != USE 2156: && GET_CODE (PATTERN (insn)) != CLOBBER)) 2157: return 0; 2158: 2159: return 1; 2160: } 2161: 2162: /* Find the number of the basic block that starts closest to INSN. Return -1 2163: if we couldn't find such a basic block. */ 2164: 2165: static int 2166: find_basic_block (insn) 2167: rtx insn; 2168: { 2169: int i; 2170: 2171: /* Scan backwards to the previous BARRIER. Then see if we can find a 2172: label that starts a basic block. Return the basic block number. */ 2173: 2174: for (insn = prev_nonnote_insn (insn); 2175: insn && GET_CODE (insn) != BARRIER; 2176: insn = prev_nonnote_insn (insn)) 2177: ; 2178: 2179: /* The start of the function is basic block zero. */ 2180: if (insn == 0) 2181: return 0; 2182: 2183: /* See if any of the upcoming CODE_LABELs start a basic block. If we reach 2184: anything other than a CODE_LABEL or note, we can't find this code. */ 2185: for (insn = next_nonnote_insn (insn); 2186: insn && GET_CODE (insn) == CODE_LABEL; 2187: insn = next_nonnote_insn (insn)) 2188: { 2189: for (i = 0; i < n_basic_blocks; i++) 2190: if (insn == basic_block_head[i]) 2191: return i; 2192: } 2193: 2194: return -1; 2195: } 2196: 2197: /* Called when INSN is being moved from a location near the target of a jump. 1.1.1.2 root 2198: We leave a marker of the form (use (INSN)) immediately in front 1.1 root 2199: of WHERE for mark_target_live_regs. These markers will be deleted when 1.1.1.2 root 2200: reorg finishes. 2201: 2202: We used to try to update the live status of registers if WHERE is at 2203: the start of a basic block, but that can't work since we may remove a 2204: BARRIER in relax_delay_slots. */ 1.1 root 2205: 2206: static void 2207: update_block (insn, where) 2208: rtx insn; 2209: rtx where; 2210: { 1.1.1.2 root 2211: int b; 2212: 1.1 root 2213: /* Ignore if this was in a delay slot and it came from the target of 2214: a branch. */ 2215: if (INSN_FROM_TARGET_P (insn)) 2216: return; 2217: 1.1.1.2 root 2218: emit_insn_before (gen_rtx (USE, VOIDmode, insn), where); 1.1 root 2219: 2220: /* INSN might be making a value live in a block where it didn't use to 2221: be. So recompute liveness information for this block. */ 1.1.1.2 root 2222: 2223: b = find_basic_block (insn); 2224: if (b != -1) 2225: bb_ticks[b]++; 1.1 root 2226: } 1.1.1.5 root 2227: 2228: /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for 2229: the basic block containing the jump. */ 2230: 2231: static int 2232: reorg_redirect_jump (jump, nlabel) 2233: rtx jump; 2234: rtx nlabel; 2235: { 2236: int b = find_basic_block (jump); 2237: 2238: if (b != -1) 2239: bb_ticks[b]++; 2240: 2241: return redirect_jump (jump, nlabel); 2242: } 2243: 2244: /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN. 2245: We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes 2246: that reference values used in INSN. If we find one, then we move the 2247: REG_DEAD note to INSN. 2248: 2249: This is needed to handle the case where an later insn (after INSN) has a 2250: REG_DEAD note for a register used by INSN, and this later insn subsequently 2251: gets moved before a CODE_LABEL because it is a redundant insn. In this 2252: case, mark_target_live_regs may be confused into thinking the register 2253: is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */ 2254: 2255: static void 2256: update_reg_dead_notes (insn, delayed_insn) 2257: rtx insn, delayed_insn; 2258: { 2259: rtx p, link, next; 2260: 2261: for (p = next_nonnote_insn (insn); p != delayed_insn; 2262: p = next_nonnote_insn (p)) 2263: for (link = REG_NOTES (p); link; link = next) 2264: { 2265: next = XEXP (link, 1); 2266: 2267: if (REG_NOTE_KIND (link) != REG_DEAD 2268: || GET_CODE (XEXP (link, 0)) != REG) 2269: continue; 2270: 2271: if (reg_referenced_p (XEXP (link, 0), PATTERN (insn))) 2272: { 2273: /* Move the REG_DEAD note from P to INSN. */ 2274: remove_note (p, link); 2275: XEXP (link, 1) = REG_NOTES (insn); 2276: REG_NOTES (insn) = link; 2277: } 2278: } 2279: } 1.1.1.7 ! root 2280: ! 2281: /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN. ! 2282: ! 2283: This handles the case of udivmodXi4 instructions which optimize their ! 2284: output depending on whether any REG_UNUSED notes are present. ! 2285: we must make sure that INSN calculates as many results as REDUNDANT_INSN ! 2286: does. */ ! 2287: ! 2288: static void ! 2289: update_reg_unused_notes (insn, redundant_insn) ! 2290: rtx insn, redundant_insn; ! 2291: { ! 2292: rtx p, link, next; ! 2293: ! 2294: for (link = REG_NOTES (insn); link; link = next) ! 2295: { ! 2296: next = XEXP (link, 1); ! 2297: ! 2298: if (REG_NOTE_KIND (link) != REG_UNUSED ! 2299: || GET_CODE (XEXP (link, 0)) != REG) ! 2300: continue; ! 2301: ! 2302: if (! find_regno_note (redundant_insn, REG_UNUSED, ! 2303: REGNO (XEXP (link, 0)))) ! 2304: remove_note (insn, link); ! 2305: } ! 2306: } 1.1 root 2307: 2308: /* Marks registers possibly live at the current place being scanned by 2309: mark_target_live_regs. Used only by next two function. */ 2310: 2311: static HARD_REG_SET current_live_regs; 2312: 2313: /* Marks registers for which we have seen a REG_DEAD note but no assignment. 2314: Also only used by the next two functions. */ 2315: 2316: static HARD_REG_SET pending_dead_regs; 2317: 2318: /* Utility function called from mark_target_live_regs via note_stores. 2319: It deadens any CLOBBERed registers and livens any SET registers. */ 2320: 2321: static void 2322: update_live_status (dest, x) 2323: rtx dest; 2324: rtx x; 2325: { 2326: int first_regno, last_regno; 2327: int i; 2328: 2329: if (GET_CODE (dest) != REG 2330: && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG)) 2331: return; 2332: 2333: if (GET_CODE (dest) == SUBREG) 2334: first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest); 2335: else 2336: first_regno = REGNO (dest); 2337: 2338: last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest)); 2339: 2340: if (GET_CODE (x) == CLOBBER) 2341: for (i = first_regno; i < last_regno; i++) 2342: CLEAR_HARD_REG_BIT (current_live_regs, i); 2343: else 2344: for (i = first_regno; i < last_regno; i++) 2345: { 2346: SET_HARD_REG_BIT (current_live_regs, i); 2347: CLEAR_HARD_REG_BIT (pending_dead_regs, i); 2348: } 2349: } 2350: 2351: /* Similar to next_insn, but ignores insns in the delay slots of 2352: an annulled branch. */ 2353: 2354: static rtx 2355: next_insn_no_annul (insn) 2356: rtx insn; 2357: { 2358: if (insn) 2359: { 2360: /* If INSN is an annulled branch, skip any insns from the target 2361: of the branch. */ 2362: if (INSN_ANNULLED_BRANCH_P (insn) 2363: && NEXT_INSN (PREV_INSN (insn)) != insn) 2364: while (INSN_FROM_TARGET_P (NEXT_INSN (insn))) 2365: insn = NEXT_INSN (insn); 2366: 2367: insn = NEXT_INSN (insn); 2368: if (insn && GET_CODE (insn) == INSN 2369: && GET_CODE (PATTERN (insn)) == SEQUENCE) 2370: insn = XVECEXP (PATTERN (insn), 0, 0); 2371: } 2372: 2373: return insn; 2374: } 2375: 2376: /* Set the resources that are live at TARGET. 2377: 2378: If TARGET is zero, we refer to the end of the current function and can 2379: return our precomputed value. 2380: 2381: Otherwise, we try to find out what is live by consulting the basic block 2382: information. This is tricky, because we must consider the actions of 2383: reload and jump optimization, which occur after the basic block information 2384: has been computed. 2385: 2386: Accordingly, we proceed as follows:: 2387: 2388: We find the previous BARRIER and look at all immediately following labels 2389: (with no intervening active insns) to see if any of them start a basic 2390: block. If we hit the start of the function first, we use block 0. 2391: 2392: Once we have found a basic block and a corresponding first insns, we can 2393: accurately compute the live status from basic_block_live_regs and 2394: reg_renumber. (By starting at a label following a BARRIER, we are immune 2395: to actions taken by reload and jump.) Then we scan all insns between 2396: that point and our target. For each CLOBBER (or for call-clobbered regs 2397: when we pass a CALL_INSN), mark the appropriate registers are dead. For 2398: a SET, mark them as live. 2399: 2400: We have to be careful when using REG_DEAD notes because they are not 2401: updated by such things as find_equiv_reg. So keep track of registers 2402: marked as dead that haven't been assigned to, and mark them dead at the 2403: next CODE_LABEL since reload and jump won't propagate values across labels. 2404: 2405: If we cannot find the start of a basic block (should be a very rare 2406: case, if it can happen at all), mark everything as potentially live. 2407: 2408: Next, scan forward from TARGET looking for things set or clobbered 2409: before they are used. These are not live. 2410: 2411: Because we can be called many times on the same target, save our results 2412: in a hash table indexed by INSN_UID. */ 2413: 2414: static void 2415: mark_target_live_regs (target, res) 2416: rtx target; 2417: struct resources *res; 2418: { 2419: int b = -1; 2420: int i; 2421: struct target_info *tinfo; 2422: rtx insn, next; 2423: rtx jump_insn = 0; 1.1.1.4 root 2424: rtx jump_target; 1.1 root 2425: HARD_REG_SET scratch; 2426: struct resources set, needed; 2427: int jump_count = 0; 2428: 2429: /* Handle end of function. */ 2430: if (target == 0) 2431: { 2432: *res = end_of_function_needs; 2433: return; 2434: } 2435: 2436: /* We have to assume memory is needed, but the CC isn't. */ 2437: res->memory = 1; 2438: res->volatil = 0; 2439: res->cc = 0; 2440: 2441: /* See if we have computed this value already. */ 2442: for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME]; 2443: tinfo; tinfo = tinfo->next) 2444: if (tinfo->uid == INSN_UID (target)) 2445: break; 2446: 2447: /* Start by getting the basic block number. If we have saved information, 2448: we can get it from there unless the insn at the start of the basic block 2449: has been deleted. */ 2450: if (tinfo && tinfo->block != -1 2451: && ! INSN_DELETED_P (basic_block_head[tinfo->block])) 2452: b = tinfo->block; 2453: 2454: if (b == -1) 2455: b = find_basic_block (target); 2456: 2457: if (tinfo) 2458: { 2459: /* If the information is up-to-date, use it. Otherwise, we will 2460: update it below. */ 2461: if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b]) 2462: { 2463: COPY_HARD_REG_SET (res->regs, tinfo->live_regs); 2464: return; 2465: } 2466: } 2467: else 2468: { 2469: /* Allocate a place to put our results and chain it into the 2470: hash table. */ 2471: tinfo = (struct target_info *) oballoc (sizeof (struct target_info)); 2472: tinfo->uid = INSN_UID (target); 2473: tinfo->block = b; 2474: tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME]; 2475: target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo; 2476: } 2477: 2478: CLEAR_HARD_REG_SET (pending_dead_regs); 2479: 2480: /* If we found a basic block, get the live registers from it and update 2481: them with anything set or killed between its start and the insn before 2482: TARGET. Otherwise, we must assume everything is live. */ 2483: if (b != -1) 2484: { 2485: regset regs_live = basic_block_live_at_start[b]; 1.1.1.4 root 2486: int offset, j; 2487: REGSET_ELT_TYPE bit; 1.1 root 2488: int regno; 2489: rtx start_insn, stop_insn; 2490: 2491: /* Compute hard regs live at start of block -- this is the real hard regs 2492: marked live, plus live pseudo regs that have been renumbered to 2493: hard regs. */ 2494: 2495: #ifdef HARD_REG_SET 2496: current_live_regs = *regs_live; 2497: #else 2498: COPY_HARD_REG_SET (current_live_regs, regs_live); 2499: #endif 2500: 2501: for (offset = 0, i = 0; offset < regset_size; offset++) 2502: { 2503: if (regs_live[offset] == 0) 1.1.1.4 root 2504: i += REGSET_ELT_BITS; 1.1 root 2505: else 2506: for (bit = 1; bit && i < max_regno; bit <<= 1, i++) 2507: if ((regs_live[offset] & bit) 2508: && (regno = reg_renumber[i]) >= 0) 2509: for (j = regno; 2510: j < regno + HARD_REGNO_NREGS (regno, 2511: PSEUDO_REGNO_MODE (i)); 2512: j++) 2513: SET_HARD_REG_BIT (current_live_regs, j); 2514: } 2515: 2516: /* Get starting and ending insn, handling the case where each might 2517: be a SEQUENCE. */ 2518: start_insn = (b == 0 ? get_insns () : basic_block_head[b]); 2519: stop_insn = target; 2520: 2521: if (GET_CODE (start_insn) == INSN 2522: && GET_CODE (PATTERN (start_insn)) == SEQUENCE) 2523: start_insn = XVECEXP (PATTERN (start_insn), 0, 0); 2524: 2525: if (GET_CODE (stop_insn) == INSN 2526: && GET_CODE (PATTERN (stop_insn)) == SEQUENCE) 2527: stop_insn = next_insn (PREV_INSN (stop_insn)); 2528: 2529: for (insn = start_insn; insn != stop_insn; 2530: insn = next_insn_no_annul (insn)) 2531: { 2532: rtx link; 2533: rtx real_insn = insn; 2534: 2535: /* If this insn is from the target of a branch, it isn't going to 2536: be used in the sequel. If it is used in both cases, this 2537: test will not be true. */ 2538: if (INSN_FROM_TARGET_P (insn)) 2539: continue; 2540: 2541: /* If this insn is a USE made by update_block, we care about the 2542: underlying insn. */ 2543: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE 1.1.1.4 root 2544: && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i') 1.1 root 2545: real_insn = XEXP (PATTERN (insn), 0); 2546: 2547: if (GET_CODE (real_insn) == CALL_INSN) 2548: { 2549: /* CALL clobbers all call-used regs that aren't fixed except 2550: sp, ap, and fp. Do this before setting the result of the 2551: call live. */ 2552: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2553: if (call_used_regs[i] 2554: && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM 2555: && i != ARG_POINTER_REGNUM 1.1.1.6 root 2556: #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2557: && i != HARD_FRAME_POINTER_REGNUM 2558: #endif 1.1 root 2559: #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM 2560: && ! (i == ARG_POINTER_REGNUM && fixed_regs[i]) 2561: #endif 2562: #ifdef PIC_OFFSET_TABLE_REGNUM 2563: && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic) 2564: #endif 2565: ) 2566: CLEAR_HARD_REG_BIT (current_live_regs, i); 1.1.1.2 root 2567: 2568: /* A CALL_INSN sets any global register live, since it may 2569: have been modified by the call. */ 2570: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2571: if (global_regs[i]) 2572: SET_HARD_REG_BIT (current_live_regs, i); 1.1 root 2573: } 2574: 2575: /* Mark anything killed in an insn to be deadened at the next 2576: label. Ignore USE insns; the only REG_DEAD notes will be for 2577: parameters. But they might be early. A CALL_INSN will usually 2578: clobber registers used for parameters. It isn't worth bothering 2579: with the unlikely case when it won't. */ 2580: if ((GET_CODE (real_insn) == INSN 1.1.1.6 root 2581: && GET_CODE (PATTERN (real_insn)) != USE 2582: && GET_CODE (PATTERN (real_insn)) != CLOBBER) 1.1 root 2583: || GET_CODE (real_insn) == JUMP_INSN 2584: || GET_CODE (real_insn) == CALL_INSN) 2585: { 2586: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1)) 2587: if (REG_NOTE_KIND (link) == REG_DEAD 2588: && GET_CODE (XEXP (link, 0)) == REG 2589: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER) 2590: { 2591: int first_regno = REGNO (XEXP (link, 0)); 2592: int last_regno 2593: = (first_regno 2594: + HARD_REGNO_NREGS (first_regno, 2595: GET_MODE (XEXP (link, 0)))); 2596: 2597: for (i = first_regno; i < last_regno; i++) 2598: SET_HARD_REG_BIT (pending_dead_regs, i); 2599: } 2600: 2601: note_stores (PATTERN (real_insn), update_live_status); 2602: 2603: /* If any registers were unused after this insn, kill them. 2604: These notes will always be accurate. */ 2605: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1)) 2606: if (REG_NOTE_KIND (link) == REG_UNUSED 2607: && GET_CODE (XEXP (link, 0)) == REG 2608: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER) 2609: { 2610: int first_regno = REGNO (XEXP (link, 0)); 2611: int last_regno 2612: = (first_regno 2613: + HARD_REGNO_NREGS (first_regno, 2614: GET_MODE (XEXP (link, 0)))); 2615: 2616: for (i = first_regno; i < last_regno; i++) 2617: CLEAR_HARD_REG_BIT (current_live_regs, i); 2618: } 2619: } 2620: 1.1.1.4 root 2621: else if (GET_CODE (real_insn) == CODE_LABEL) 1.1 root 2622: { 2623: /* A label clobbers the pending dead registers since neither 2624: reload nor jump will propagate a value across a label. */ 2625: AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs); 2626: CLEAR_HARD_REG_SET (pending_dead_regs); 2627: } 1.1.1.4 root 2628: 2629: /* The beginning of the epilogue corresponds to the end of the 2630: RTL chain when there are no epilogue insns. Certain resources 2631: are implicitly required at that point. */ 2632: else if (GET_CODE (real_insn) == NOTE 2633: && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG) 2634: IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs); 1.1 root 2635: } 2636: 2637: COPY_HARD_REG_SET (res->regs, current_live_regs); 2638: tinfo->block = b; 2639: tinfo->bb_tick = bb_ticks[b]; 2640: } 2641: else 2642: /* We didn't find the start of a basic block. Assume everything 2643: in use. This should happen only extremely rarely. */ 2644: SET_HARD_REG_SET (res->regs); 2645: 2646: /* Now step forward from TARGET looking for registers that are set before 2647: they are used. These are dead. If we pass a label, any pending dead 2648: registers that weren't yet used can be made dead. Stop when we pass a 2649: conditional JUMP_INSN; follow the first few unconditional branches. */ 2650: 2651: CLEAR_RESOURCE (&set); 2652: CLEAR_RESOURCE (&needed); 2653: 2654: for (insn = target; insn; insn = next) 2655: { 1.1.1.4 root 2656: rtx this_jump_insn = insn; 1.1 root 2657: 2658: next = NEXT_INSN (insn); 2659: switch (GET_CODE (insn)) 2660: { 2661: case CODE_LABEL: 2662: AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs); 2663: AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs); 2664: CLEAR_HARD_REG_SET (pending_dead_regs); 2665: continue; 2666: 2667: case BARRIER: 2668: case NOTE: 2669: continue; 2670: 2671: case INSN: 1.1.1.4 root 2672: if (GET_CODE (PATTERN (insn)) == USE) 2673: { 2674: /* If INSN is a USE made by update_block, we care about the 2675: underlying insn. Any registers set by the underlying insn 2676: are live since the insn is being done somewhere else. */ 2677: if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i') 2678: mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1); 2679: 2680: /* All other USE insns are to be ignored. */ 2681: continue; 2682: } 2683: else if (GET_CODE (PATTERN (insn)) == CLOBBER) 1.1 root 2684: continue; 1.1.1.4 root 2685: else if (GET_CODE (PATTERN (insn)) == SEQUENCE) 2686: { 2687: /* An unconditional jump can be used to fill the delay slot 2688: of a call, so search for a JUMP_INSN in any position. */ 2689: for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++) 2690: { 2691: this_jump_insn = XVECEXP (PATTERN (insn), 0, i); 2692: if (GET_CODE (this_jump_insn) == JUMP_INSN) 2693: break; 2694: } 2695: } 1.1 root 2696: } 2697: 1.1.1.4 root 2698: if (GET_CODE (this_jump_insn) == JUMP_INSN) 1.1 root 2699: { 2700: if (jump_count++ < 10 1.1.1.4 root 2701: && (simplejump_p (this_jump_insn) 2702: || GET_CODE (PATTERN (this_jump_insn)) == RETURN)) 1.1 root 2703: { 1.1.1.4 root 2704: next = next_active_insn (JUMP_LABEL (this_jump_insn)); 1.1 root 2705: if (jump_insn == 0) 1.1.1.4 root 2706: { 2707: jump_insn = insn; 2708: jump_target = JUMP_LABEL (this_jump_insn); 2709: } 1.1 root 2710: } 2711: else 2712: break; 2713: } 2714: 2715: mark_referenced_resources (insn, &needed, 1); 1.1.1.4 root 2716: mark_set_resources (insn, &set, 0, 1); 1.1 root 2717: 2718: COPY_HARD_REG_SET (scratch, set.regs); 2719: AND_COMPL_HARD_REG_SET (scratch, needed.regs); 2720: AND_COMPL_HARD_REG_SET (res->regs, scratch); 2721: } 2722: 2723: /* If we hit an unconditional branch, we have another way of finding out 2724: what is live: we can see what is live at the branch target and include 2725: anything used but not set before the branch. The only things that are 1.1.1.2 root 2726: live are those that are live using the above test and the test below. 2727: 2728: Don't try this if we expired our jump count above, since that would 2729: mean there may be an infinite loop in the function being compiled. */ 2730: 2731: if (jump_insn && jump_count < 10) 1.1 root 2732: { 2733: struct resources new_resources; 2734: rtx stop_insn = next_active_insn (jump_insn); 2735: 2736: mark_target_live_regs (next_active_insn (jump_target), &new_resources); 2737: CLEAR_RESOURCE (&set); 2738: CLEAR_RESOURCE (&needed); 2739: 2740: /* Include JUMP_INSN in the needed registers. */ 2741: for (insn = target; insn != stop_insn; insn = next_active_insn (insn)) 2742: { 2743: mark_referenced_resources (insn, &needed, 1); 2744: 2745: COPY_HARD_REG_SET (scratch, needed.regs); 2746: AND_COMPL_HARD_REG_SET (scratch, set.regs); 2747: IOR_HARD_REG_SET (new_resources.regs, scratch); 2748: 1.1.1.4 root 2749: mark_set_resources (insn, &set, 0, 1); 1.1 root 2750: } 2751: 2752: AND_HARD_REG_SET (res->regs, new_resources.regs); 2753: } 2754: 2755: COPY_HARD_REG_SET (tinfo->live_regs, res->regs); 2756: } 2757: 2758: /* Scan a function looking for insns that need a delay slot and find insns to 2759: put into the delay slot. 2760: 2761: NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such 2762: as calls). We do these first since we don't want jump insns (that are 2763: easier to fill) to get the only insns that could be used for non-jump insns. 2764: When it is zero, only try to fill JUMP_INSNs. 2765: 2766: When slots are filled in this manner, the insns (including the 2767: delay_insn) are put together in a SEQUENCE rtx. In this fashion, 2768: it is possible to tell whether a delay slot has really been filled 2769: or not. `final' knows how to deal with this, by communicating 2770: through FINAL_SEQUENCE. */ 2771: 2772: static void 2773: fill_simple_delay_slots (first, non_jumps_p) 2774: rtx first; 1.1.1.5 root 2775: int non_jumps_p; 1.1 root 2776: { 2777: register rtx insn, pat, trial, next_trial; 1.1.1.4 root 2778: register int i, j; 1.1 root 2779: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 2780: struct resources needed, set; 2781: register int slots_to_fill, slots_filled; 2782: rtx delay_list; 2783: 2784: for (i = 0; i < num_unfilled_slots; i++) 2785: { 1.1.1.5 root 2786: int flags; 1.1 root 2787: /* Get the next insn to fill. If it has already had any slots assigned, 2788: we can't do anything with it. Maybe we'll improve this later. */ 2789: 2790: insn = unfilled_slots_base[i]; 2791: if (insn == 0 2792: || INSN_DELETED_P (insn) 2793: || (GET_CODE (insn) == INSN 2794: && GET_CODE (PATTERN (insn)) == SEQUENCE) 2795: || (GET_CODE (insn) == JUMP_INSN && non_jumps_p) 2796: || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p)) 2797: continue; 1.1.1.5 root 2798: 1.1.1.6 root 2799: if (GET_CODE (insn) == JUMP_INSN) 2800: flags = get_jump_flags (insn, JUMP_LABEL (insn)); 2801: else 2802: flags = get_jump_flags (insn, NULL_RTX); 1.1 root 2803: slots_to_fill = num_delay_slots (insn); 2804: if (slots_to_fill == 0) 2805: abort (); 2806: 2807: /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL 1.1.1.4 root 2808: says how many. After initialization, first try optimizing 2809: 2810: call _foo call _foo 2811: nop add %o7,.-L1,%o7 2812: b,a L1 2813: nop 2814: 2815: If this case applies, the delay slot of the call is filled with 2816: the unconditional jump. This is done first to avoid having the 2817: delay slot of the call filled in the backward scan. Also, since 2818: the unconditional jump is likely to also have a delay slot, that 1.1.1.6 root 2819: insn must exist when it is subsequently scanned. 2820: 2821: This is tried on each insn with delay slots as some machines 2822: have insns which perform calls, but are not represented as 2823: CALL_INSNs. */ 1.1.1.4 root 2824: 2825: slots_filled = 0; 2826: delay_list = 0; 2827: 1.1.1.6 root 2828: if ((trial = next_active_insn (insn)) 1.1.1.4 root 2829: && GET_CODE (trial) == JUMP_INSN 2830: && simplejump_p (trial) 1.1.1.5 root 2831: && eligible_for_delay (insn, slots_filled, trial, flags) 1.1.1.4 root 2832: && no_labels_between_p (insn, trial)) 2833: { 2834: slots_filled++; 2835: delay_list = add_to_delay_list (trial, delay_list); 2836: /* Remove the unconditional jump from consideration for delay slot 2837: filling and unthread it. */ 2838: if (unfilled_slots_base[i + 1] == trial) 2839: unfilled_slots_base[i + 1] = 0; 2840: { 2841: rtx next = NEXT_INSN (trial); 2842: rtx prev = PREV_INSN (trial); 2843: if (prev) 2844: NEXT_INSN (prev) = next; 2845: if (next) 2846: PREV_INSN (next) = prev; 2847: } 2848: } 2849: 2850: /* Now, scan backwards from the insn to search for a potential 2851: delay-slot candidate. Stop searching when a label or jump is hit. 2852: 1.1 root 2853: For each candidate, if it is to go into the delay slot (moved 2854: forward in execution sequence), it must not need or set any resources 2855: that were set by later insns and must not set any resources that 2856: are needed for those insns. 2857: 2858: The delay slot insn itself sets resources unless it is a call 2859: (in which case the called routine, not the insn itself, is doing 2860: the setting). */ 2861: 1.1.1.4 root 2862: if (slots_filled < slots_to_fill) 1.1 root 2863: { 1.1.1.4 root 2864: CLEAR_RESOURCE (&needed); 2865: CLEAR_RESOURCE (&set); 2866: mark_set_resources (insn, &set, 0, 0); 2867: mark_referenced_resources (insn, &needed, 0); 1.1 root 2868: 1.1.1.4 root 2869: for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1); 2870: trial = next_trial) 2871: { 2872: next_trial = prev_nonnote_insn (trial); 1.1 root 2873: 1.1.1.4 root 2874: /* This must be an INSN or CALL_INSN. */ 2875: pat = PATTERN (trial); 2876: 2877: /* USE and CLOBBER at this level was just for flow; ignore it. */ 2878: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 2879: continue; 1.1 root 2880: 1.1.1.4 root 2881: /* Check for resource conflict first, to avoid unnecessary 2882: splitting. */ 2883: if (! insn_references_resource_p (trial, &set, 1) 2884: && ! insn_sets_resource_p (trial, &set, 1) 2885: && ! insn_sets_resource_p (trial, &needed, 1) 1.1 root 2886: #ifdef HAVE_cc0 1.1.1.4 root 2887: /* Can't separate set of cc0 from its use. */ 2888: && ! (reg_mentioned_p (cc0_rtx, pat) 2889: && ! sets_cc0_p (cc0_rtx, pat)) 1.1 root 2890: #endif 1.1.1.4 root 2891: ) 1.1 root 2892: { 1.1.1.4 root 2893: trial = try_split (pat, trial, 1); 2894: next_trial = prev_nonnote_insn (trial); 1.1.1.5 root 2895: if (eligible_for_delay (insn, slots_filled, trial, flags)) 1.1.1.4 root 2896: { 2897: /* In this case, we are searching backward, so if we 2898: find insns to put on the delay list, we want 2899: to put them at the head, rather than the 2900: tail, of the list. */ 2901: 1.1.1.5 root 2902: update_reg_dead_notes (trial, insn); 1.1.1.4 root 2903: delay_list = gen_rtx (INSN_LIST, VOIDmode, 2904: trial, delay_list); 2905: update_block (trial, trial); 2906: delete_insn (trial); 2907: if (slots_to_fill == ++slots_filled) 2908: break; 2909: continue; 2910: } 1.1 root 2911: } 2912: 1.1.1.4 root 2913: mark_set_resources (trial, &set, 0, 1); 2914: mark_referenced_resources (trial, &needed, 1); 2915: } 1.1 root 2916: } 2917: 2918: /* If all needed slots haven't been filled, we come here. */ 2919: 2920: /* Try to optimize case of jumping around a single insn. */ 2921: #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS) 1.1.1.4 root 2922: if (slots_filled != slots_to_fill 2923: && delay_list == 0 1.1.1.7 ! root 2924: && GET_CODE (insn) == JUMP_INSN ! 2925: && (condjump_p (insn) || condjump_in_parallel_p (insn))) 1.1 root 2926: { 2927: delay_list = optimize_skip (insn); 2928: if (delay_list) 2929: slots_filled += 1; 2930: } 2931: #endif 2932: 2933: /* Try to get insns from beyond the insn needing the delay slot. 2934: These insns can neither set or reference resources set in insns being 2935: skipped, cannot set resources in the insn being skipped, and, if this 2936: is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the 2937: call might not return). 2938: 2939: If this is a conditional jump, see if it merges back to us early 2940: enough for us to pick up insns from the merge point. Don't do 2941: this if there is another branch to our label unless we pass all of 2942: them. 2943: 2944: Another similar merge is if we jump to the same place that a 2945: later unconditional jump branches to. In that case, we don't 2946: care about the number of uses of our label. */ 2947: 1.1.1.4 root 2948: if (slots_filled != slots_to_fill 2949: && (GET_CODE (insn) != JUMP_INSN 1.1.1.7 ! root 2950: || ((condjump_p (insn) || condjump_in_parallel_p (insn)) ! 2951: && ! simplejump_p (insn) 1.1.1.4 root 2952: && JUMP_LABEL (insn) != 0))) 1.1 root 2953: { 2954: rtx target = 0; 2955: int maybe_never = 0; 2956: int passed_label = 0; 2957: int target_uses; 2958: struct resources needed_at_jump; 2959: 2960: CLEAR_RESOURCE (&needed); 2961: CLEAR_RESOURCE (&set); 2962: 2963: if (GET_CODE (insn) == CALL_INSN) 2964: { 1.1.1.4 root 2965: mark_set_resources (insn, &set, 0, 1); 1.1 root 2966: mark_referenced_resources (insn, &needed, 1); 2967: maybe_never = 1; 2968: } 1.1.1.4 root 2969: else 1.1 root 2970: { 1.1.1.5 root 2971: mark_set_resources (insn, &set, 0, 1); 2972: mark_referenced_resources (insn, &needed, 1); 1.1.1.4 root 2973: if (GET_CODE (insn) == JUMP_INSN) 2974: { 2975: /* Get our target and show how many more uses we want to 2976: see before we hit the label. */ 2977: target = JUMP_LABEL (insn); 2978: target_uses = LABEL_NUSES (target) - 1; 2979: } 2980: 1.1 root 2981: } 2982: 2983: for (trial = next_nonnote_insn (insn); trial; trial = next_trial) 2984: { 2985: rtx pat, trial_delay; 2986: 2987: next_trial = next_nonnote_insn (trial); 2988: 2989: if (GET_CODE (trial) == CODE_LABEL) 2990: { 2991: passed_label = 1; 2992: 2993: /* If this is our target, see if we have seen all its uses. 2994: If so, indicate we have passed our target and ignore it. 2995: All other labels cause us to stop our search. */ 2996: if (trial == target && target_uses == 0) 2997: { 2998: target = 0; 2999: continue; 3000: } 3001: else 3002: break; 3003: } 3004: else if (GET_CODE (trial) == BARRIER) 3005: break; 3006: 3007: /* We must have an INSN, JUMP_INSN, or CALL_INSN. */ 3008: pat = PATTERN (trial); 3009: 3010: /* Stand-alone USE and CLOBBER are just for flow. */ 3011: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 3012: continue; 3013: 3014: /* If this already has filled delay slots, get the insn needing 3015: the delay slots. */ 3016: if (GET_CODE (pat) == SEQUENCE) 3017: trial_delay = XVECEXP (pat, 0, 0); 3018: else 3019: trial_delay = trial; 3020: 3021: /* If this is a jump insn to our target, indicate that we have 3022: seen another jump to it. If we aren't handling a conditional 3023: jump, stop our search. Otherwise, compute the needs at its 3024: target and add them to NEEDED. */ 3025: if (GET_CODE (trial_delay) == JUMP_INSN) 3026: { 3027: if (target == 0) 3028: break; 3029: else if (JUMP_LABEL (trial_delay) == target) 3030: target_uses--; 3031: else 3032: { 3033: mark_target_live_regs 3034: (next_active_insn (JUMP_LABEL (trial_delay)), 3035: &needed_at_jump); 3036: needed.memory |= needed_at_jump.memory; 3037: IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs); 3038: } 3039: } 3040: 3041: /* See if we have a resource problem before we try to 3042: split. */ 3043: if (target == 0 3044: && GET_CODE (pat) != SEQUENCE 3045: && ! insn_references_resource_p (trial, &set, 1) 3046: && ! insn_sets_resource_p (trial, &set, 1) 3047: && ! insn_sets_resource_p (trial, &needed, 1) 3048: #ifdef HAVE_cc0 3049: && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat)) 3050: #endif 3051: && ! (maybe_never && may_trap_p (pat)) 3052: && (trial = try_split (pat, trial, 0)) 1.1.1.5 root 3053: && eligible_for_delay (insn, slots_filled, trial, flags)) 1.1 root 3054: { 3055: next_trial = next_nonnote_insn (trial); 3056: delay_list = add_to_delay_list (trial, delay_list); 3057: 3058: #ifdef HAVE_cc0 3059: if (reg_mentioned_p (cc0_rtx, pat)) 3060: link_cc0_insns (trial); 3061: #endif 3062: 3063: if (passed_label) 3064: update_block (trial, trial); 3065: delete_insn (trial); 3066: if (slots_to_fill == ++slots_filled) 3067: break; 3068: continue; 3069: } 3070: 1.1.1.4 root 3071: mark_set_resources (trial, &set, 0, 1); 1.1 root 3072: mark_referenced_resources (trial, &needed, 1); 3073: 3074: /* Ensure we don't put insns between the setting of cc and the 3075: comparison by moving a setting of cc into an earlier delay 3076: slot since these insns could clobber the condition code. */ 3077: set.cc = 1; 3078: 3079: /* If this is a call or jump, we might not get here. */ 3080: if (GET_CODE (trial) == CALL_INSN 3081: || GET_CODE (trial) == JUMP_INSN) 3082: maybe_never = 1; 3083: } 3084: 3085: /* If there are slots left to fill and our search was stopped by an 3086: unconditional branch, try the insn at the branch target. We can 3087: redirect the branch if it works. */ 3088: if (slots_to_fill != slots_filled 3089: && trial 3090: && GET_CODE (trial) == JUMP_INSN 3091: && simplejump_p (trial) 3092: && (target == 0 || JUMP_LABEL (trial) == target) 3093: && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0 3094: && ! (GET_CODE (next_trial) == INSN 3095: && GET_CODE (PATTERN (next_trial)) == SEQUENCE) 3096: && ! insn_references_resource_p (next_trial, &set, 1) 3097: && ! insn_sets_resource_p (next_trial, &set, 1) 3098: && ! insn_sets_resource_p (next_trial, &needed, 1) 3099: #ifdef HAVE_cc0 1.1.1.4 root 3100: && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial)) 1.1 root 3101: #endif 3102: && ! (maybe_never && may_trap_p (PATTERN (next_trial))) 3103: && (next_trial = try_split (PATTERN (next_trial), next_trial, 0)) 1.1.1.5 root 3104: && eligible_for_delay (insn, slots_filled, next_trial, flags)) 1.1 root 3105: { 3106: rtx new_label = next_active_insn (next_trial); 3107: 3108: if (new_label != 0) 3109: new_label = get_label_before (new_label); 1.1.1.6 root 3110: else 3111: new_label = find_end_label (); 1.1 root 3112: 3113: delay_list 3114: = add_to_delay_list (copy_rtx (next_trial), delay_list); 3115: slots_filled++; 1.1.1.5 root 3116: reorg_redirect_jump (trial, new_label); 1.1 root 3117: 3118: /* If we merged because we both jumped to the same place, 3119: redirect the original insn also. */ 3120: if (target) 1.1.1.5 root 3121: reorg_redirect_jump (insn, new_label); 1.1 root 3122: } 3123: } 3124: 3125: if (delay_list) 3126: unfilled_slots_base[i] 3127: = emit_delay_sequence (insn, delay_list, 3128: slots_filled, slots_to_fill); 3129: 3130: if (slots_to_fill == slots_filled) 3131: unfilled_slots_base[i] = 0; 3132: 3133: note_delay_statistics (slots_filled, 0); 3134: } 3135: 3136: #ifdef DELAY_SLOTS_FOR_EPILOGUE 3137: /* See if the epilogue needs any delay slots. Try to fill them if so. 3138: The only thing we can do is scan backwards from the end of the 3139: function. If we did this in a previous pass, it is incorrect to do it 3140: again. */ 3141: if (current_function_epilogue_delay_list) 3142: return; 3143: 3144: slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE; 3145: if (slots_to_fill == 0) 3146: return; 3147: 3148: slots_filled = 0; 1.1.1.7 ! root 3149: needed = end_of_function_needs; 1.1 root 3150: CLEAR_RESOURCE (&set); 3151: 3152: for (trial = get_last_insn (); ! stop_search_p (trial, 1); 3153: trial = PREV_INSN (trial)) 3154: { 3155: if (GET_CODE (trial) == NOTE) 3156: continue; 3157: pat = PATTERN (trial); 3158: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 3159: continue; 3160: 3161: if (! insn_references_resource_p (trial, &set, 1) 3162: && ! insn_sets_resource_p (trial, &needed, 1) 3163: #ifdef HAVE_cc0 3164: /* Don't want to mess with cc0 here. */ 3165: && ! reg_mentioned_p (cc0_rtx, pat) 3166: #endif 3167: ) 3168: { 3169: trial = try_split (pat, trial, 1); 3170: if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled)) 3171: { 3172: /* Here as well we are searching backward, so put the 3173: insns we find on the head of the list. */ 3174: 3175: current_function_epilogue_delay_list 3176: = gen_rtx (INSN_LIST, VOIDmode, trial, 3177: current_function_epilogue_delay_list); 3178: mark_referenced_resources (trial, &end_of_function_needs, 1); 3179: update_block (trial, trial); 3180: delete_insn (trial); 3181: 3182: /* Clear deleted bit so final.c will output the insn. */ 3183: INSN_DELETED_P (trial) = 0; 3184: 3185: if (slots_to_fill == ++slots_filled) 3186: break; 3187: continue; 3188: } 3189: } 3190: 1.1.1.4 root 3191: mark_set_resources (trial, &set, 0, 1); 1.1 root 3192: mark_referenced_resources (trial, &needed, 1); 3193: } 3194: 3195: note_delay_statistics (slots_filled, 0); 3196: #endif 3197: } 3198: 3199: /* Try to find insns to place in delay slots. 3200: 3201: INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION 3202: or is an unconditional branch if CONDITION is const_true_rtx. 3203: *PSLOTS_FILLED is updated with the number of slots that we have filled. 3204: 3205: THREAD is a flow-of-control, either the insns to be executed if the 3206: branch is true or if the branch is false, THREAD_IF_TRUE says which. 3207: 3208: OPPOSITE_THREAD is the thread in the opposite direction. It is used 3209: to see if any potential delay slot insns set things needed there. 3210: 3211: LIKELY is non-zero if it is extremely likely that the branch will be 3212: taken and THREAD_IF_TRUE is set. This is used for the branch at the 3213: end of a loop back up to the top. 3214: 3215: OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the 3216: thread. I.e., it is the fallthrough code of our jump or the target of the 3217: jump when we are the only jump going there. 3218: 3219: If OWN_THREAD is false, it must be the "true" thread of a jump. In that 3220: case, we can only take insns from the head of the thread for our delay 3221: slot. We then adjust the jump to point after the insns we have taken. */ 3222: 3223: static rtx 3224: fill_slots_from_thread (insn, condition, thread, opposite_thread, likely, 3225: thread_if_true, own_thread, own_opposite_thread, 3226: slots_to_fill, pslots_filled) 3227: rtx insn; 3228: rtx condition; 3229: rtx thread, opposite_thread; 3230: int likely; 3231: int thread_if_true; 3232: int own_thread, own_opposite_thread; 3233: int slots_to_fill, *pslots_filled; 3234: { 1.1.1.2 root 3235: rtx new_thread; 1.1 root 3236: rtx delay_list = 0; 3237: struct resources opposite_needed, set, needed; 3238: rtx trial; 3239: int lose = 0; 3240: int must_annul = 0; 1.1.1.5 root 3241: int flags; 1.1 root 3242: 3243: /* Validate our arguments. */ 3244: if ((condition == const_true_rtx && ! thread_if_true) 3245: || (! own_thread && ! thread_if_true)) 3246: abort (); 3247: 1.1.1.5 root 3248: flags = get_jump_flags (insn, JUMP_LABEL (insn)); 3249: 1.1 root 3250: /* If our thread is the end of subroutine, we can't get any delay 3251: insns from that. */ 3252: if (thread == 0) 3253: return 0; 3254: 3255: /* If this is an unconditional branch, nothing is needed at the 3256: opposite thread. Otherwise, compute what is needed there. */ 3257: if (condition == const_true_rtx) 3258: CLEAR_RESOURCE (&opposite_needed); 3259: else 3260: mark_target_live_regs (opposite_thread, &opposite_needed); 3261: 1.1.1.2 root 3262: /* If the insn at THREAD can be split, do it here to avoid having to 3263: update THREAD and NEW_THREAD if it is done in the loop below. Also 3264: initialize NEW_THREAD. */ 3265: 3266: new_thread = thread = try_split (PATTERN (thread), thread, 0); 3267: 1.1 root 3268: /* Scan insns at THREAD. We are looking for an insn that can be removed 3269: from THREAD (it neither sets nor references resources that were set 3270: ahead of it and it doesn't set anything needs by the insns ahead of 3271: it) and that either can be placed in an annulling insn or aren't 3272: needed at OPPOSITE_THREAD. */ 3273: 3274: CLEAR_RESOURCE (&needed); 3275: CLEAR_RESOURCE (&set); 3276: 3277: /* If we do not own this thread, we must stop as soon as we find 3278: something that we can't put in a delay slot, since all we can do 3279: is branch into THREAD at a later point. Therefore, labels stop 3280: the search if this is not the `true' thread. */ 3281: 3282: for (trial = thread; 3283: ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread); 3284: trial = next_nonnote_insn (trial)) 3285: { 1.1.1.5 root 3286: rtx pat, old_trial; 1.1 root 3287: 3288: /* If we have passed a label, we no longer own this thread. */ 3289: if (GET_CODE (trial) == CODE_LABEL) 3290: { 3291: own_thread = 0; 3292: continue; 3293: } 3294: 3295: pat = PATTERN (trial); 3296: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER) 3297: continue; 3298: 3299: /* If TRIAL conflicts with the insns ahead of it, we lose. Also, 3300: don't separate or copy insns that set and use CC0. */ 3301: if (! insn_references_resource_p (trial, &set, 1) 3302: && ! insn_sets_resource_p (trial, &set, 1) 3303: && ! insn_sets_resource_p (trial, &needed, 1) 3304: #ifdef HAVE_cc0 3305: && ! (reg_mentioned_p (cc0_rtx, pat) 3306: && (! own_thread || ! sets_cc0_p (pat))) 3307: #endif 3308: ) 3309: { 1.1.1.7 ! root 3310: rtx prior_insn; ! 3311: 1.1 root 3312: /* If TRIAL is redundant with some insn before INSN, we don't 3313: actually need to add it to the delay list; we can merely pretend 3314: we did. */ 1.1.1.7 ! root 3315: if (prior_insn = redundant_insn_p (trial, insn, delay_list)) 1.1 root 3316: { 3317: if (own_thread) 3318: { 3319: update_block (trial, thread); 1.1.1.7 ! root 3320: if (trial == thread) ! 3321: { ! 3322: thread = next_active_insn (thread); ! 3323: if (new_thread == trial) ! 3324: new_thread = thread; ! 3325: } ! 3326: 1.1 root 3327: delete_insn (trial); 3328: } 3329: else 1.1.1.7 ! root 3330: { ! 3331: update_reg_unused_notes (prior_insn, trial); ! 3332: new_thread = next_active_insn (trial); ! 3333: } 1.1 root 3334: 3335: continue; 3336: } 3337: 3338: /* There are two ways we can win: If TRIAL doesn't set anything 3339: needed at the opposite thread and can't trap, or if it can 3340: go into an annulled delay slot. */ 3341: if (condition == const_true_rtx 3342: || (! insn_sets_resource_p (trial, &opposite_needed, 1) 3343: && ! may_trap_p (pat))) 3344: { 1.1.1.5 root 3345: old_trial = trial; 1.1 root 3346: trial = try_split (pat, trial, 0); 1.1.1.5 root 3347: if (new_thread == old_trial) 3348: new_thread = trial; 1.1.1.7 ! root 3349: if (thread == old_trial) ! 3350: thread = trial; 1.1 root 3351: pat = PATTERN (trial); 1.1.1.5 root 3352: if (eligible_for_delay (insn, *pslots_filled, trial, flags)) 1.1 root 3353: goto winner; 3354: } 3355: else if (0 3356: #ifdef ANNUL_IFTRUE_SLOTS 3357: || ! thread_if_true 3358: #endif 3359: #ifdef ANNUL_IFFALSE_SLOTS 3360: || thread_if_true 3361: #endif 3362: ) 3363: { 1.1.1.5 root 3364: old_trial = trial; 1.1 root 3365: trial = try_split (pat, trial, 0); 1.1.1.5 root 3366: if (new_thread == old_trial) 3367: new_thread = trial; 1.1 root 3368: pat = PATTERN (trial); 3369: if ((thread_if_true 1.1.1.5 root 3370: ? eligible_for_annul_false (insn, *pslots_filled, trial, flags) 3371: : eligible_for_annul_true (insn, *pslots_filled, trial, flags))) 1.1 root 3372: { 3373: rtx temp; 3374: 3375: must_annul = 1; 3376: winner: 3377: 3378: #ifdef HAVE_cc0 3379: if (reg_mentioned_p (cc0_rtx, pat)) 3380: link_cc0_insns (trial); 3381: #endif 3382: 3383: /* If we own this thread, delete the insn. If this is the 3384: destination of a branch, show that a basic block status 3385: may have been updated. In any case, mark the new 3386: starting point of this thread. */ 3387: if (own_thread) 3388: { 3389: update_block (trial, thread); 3390: delete_insn (trial); 3391: } 3392: else 3393: new_thread = next_active_insn (trial); 3394: 3395: temp = own_thread ? trial : copy_rtx (trial); 3396: if (thread_if_true) 3397: INSN_FROM_TARGET_P (temp) = 1; 3398: 3399: delay_list = add_to_delay_list (temp, delay_list); 3400: 3401: if (slots_to_fill == ++(*pslots_filled)) 3402: { 3403: /* Even though we have filled all the slots, we 3404: may be branching to a location that has a 3405: redundant insn. Skip any if so. */ 3406: while (new_thread && ! own_thread 3407: && ! insn_sets_resource_p (new_thread, &set, 1) 3408: && ! insn_sets_resource_p (new_thread, &needed, 1) 3409: && ! insn_references_resource_p (new_thread, 3410: &set, 1) 3411: && redundant_insn_p (new_thread, insn, 3412: delay_list)) 3413: new_thread = next_active_insn (new_thread); 3414: break; 3415: } 3416: 3417: continue; 3418: } 3419: } 3420: } 3421: 3422: /* This insn can't go into a delay slot. */ 3423: lose = 1; 1.1.1.4 root 3424: mark_set_resources (trial, &set, 0, 1); 1.1 root 3425: mark_referenced_resources (trial, &needed, 1); 3426: 3427: /* Ensure we don't put insns between the setting of cc and the comparison 3428: by moving a setting of cc into an earlier delay slot since these insns 3429: could clobber the condition code. */ 3430: set.cc = 1; 3431: 3432: /* If this insn is a register-register copy and the next insn has 3433: a use of our destination, change it to use our source. That way, 3434: it will become a candidate for our delay slot the next time 3435: through this loop. This case occurs commonly in loops that 3436: scan a list. 3437: 3438: We could check for more complex cases than those tested below, 3439: but it doesn't seem worth it. It might also be a good idea to try 1.1.1.2 root 3440: to swap the two insns. That might do better. 3441: 1.1.1.6 root 3442: We can't do this if the next insn modifies our destination, because 3443: that would make the replacement into the insn invalid. We also can't 3444: do this if it modifies our source, because it might be an earlyclobber 3445: operand. This latter test also prevents updating the contents of 3446: a PRE_INC. */ 1.1 root 3447: 3448: if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET 3449: && GET_CODE (SET_SRC (pat)) == REG 3450: && GET_CODE (SET_DEST (pat)) == REG) 3451: { 3452: rtx next = next_nonnote_insn (trial); 3453: 3454: if (next && GET_CODE (next) == INSN 1.1.1.2 root 3455: && GET_CODE (PATTERN (next)) != USE 3456: && ! reg_set_p (SET_DEST (pat), next) 1.1.1.6 root 3457: && ! reg_set_p (SET_SRC (pat), next) 1.1.1.2 root 3458: && reg_referenced_p (SET_DEST (pat), PATTERN (next))) 1.1 root 3459: validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next); 3460: } 3461: } 3462: 3463: /* If we stopped on a branch insn that has delay slots, see if we can 3464: steal some of the insns in those slots. */ 3465: if (trial && GET_CODE (trial) == INSN 3466: && GET_CODE (PATTERN (trial)) == SEQUENCE 3467: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN) 3468: { 3469: /* If this is the `true' thread, we will want to follow the jump, 3470: so we can only do this if we have taken everything up to here. */ 3471: if (thread_if_true && trial == new_thread) 3472: delay_list 3473: = steal_delay_list_from_target (insn, condition, PATTERN (trial), 3474: delay_list, &set, &needed, 3475: &opposite_needed, slots_to_fill, 3476: pslots_filled, &must_annul, 3477: &new_thread); 3478: else if (! thread_if_true) 3479: delay_list 3480: = steal_delay_list_from_fallthrough (insn, condition, 3481: PATTERN (trial), 3482: delay_list, &set, &needed, 3483: &opposite_needed, slots_to_fill, 3484: pslots_filled, &must_annul); 3485: } 3486: 3487: /* If we haven't found anything for this delay slot and it is very 3488: likely that the branch will be taken, see if the insn at our target 1.1.1.2 root 3489: increments or decrements a register with an increment that does not 3490: depend on the destination register. If so, try to place the opposite 1.1 root 3491: arithmetic insn after the jump insn and put the arithmetic insn in the 3492: delay slot. If we can't do this, return. */ 3493: if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN) 3494: { 3495: rtx pat = PATTERN (new_thread); 3496: rtx dest; 3497: rtx src; 3498: 1.1.1.2 root 3499: trial = new_thread; 1.1 root 3500: pat = PATTERN (trial); 3501: 3502: if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET 1.1.1.5 root 3503: || ! eligible_for_delay (insn, 0, trial, flags)) 1.1 root 3504: return 0; 3505: 3506: dest = SET_DEST (pat), src = SET_SRC (pat); 3507: if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS) 1.1.1.2 root 3508: && rtx_equal_p (XEXP (src, 0), dest) 3509: && ! reg_overlap_mentioned_p (dest, XEXP (src, 1))) 1.1 root 3510: { 3511: rtx other = XEXP (src, 1); 3512: rtx new_arith; 3513: rtx ninsn; 3514: 3515: /* If this is a constant adjustment, use the same code with 3516: the negated constant. Otherwise, reverse the sense of the 3517: arithmetic. */ 3518: if (GET_CODE (other) == CONST_INT) 3519: new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest, 3520: negate_rtx (GET_MODE (src), other)); 3521: else 3522: new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS, 3523: GET_MODE (src), dest, other); 3524: 3525: ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith), 3526: insn); 3527: 3528: if (recog_memoized (ninsn) < 0 3529: || (insn_extract (ninsn), 3530: ! constrain_operands (INSN_CODE (ninsn), 1))) 3531: { 3532: delete_insn (ninsn); 3533: return 0; 3534: } 3535: 3536: if (own_thread) 3537: { 3538: update_block (trial, thread); 3539: delete_insn (trial); 3540: } 3541: else 3542: new_thread = next_active_insn (trial); 3543: 3544: ninsn = own_thread ? trial : copy_rtx (trial); 3545: if (thread_if_true) 3546: INSN_FROM_TARGET_P (ninsn) = 1; 3547: 1.1.1.4 root 3548: delay_list = add_to_delay_list (ninsn, NULL_RTX); 1.1 root 3549: (*pslots_filled)++; 3550: } 3551: } 3552: 3553: if (delay_list && must_annul) 3554: INSN_ANNULLED_BRANCH_P (insn) = 1; 3555: 3556: /* If we are to branch into the middle of this thread, find an appropriate 3557: label or make a new one if none, and redirect INSN to it. If we hit the 3558: end of the function, use the end-of-function label. */ 3559: if (new_thread != thread) 3560: { 3561: rtx label; 3562: 3563: if (! thread_if_true) 3564: abort (); 3565: 3566: if (new_thread && GET_CODE (new_thread) == JUMP_INSN 3567: && (simplejump_p (new_thread) 1.1.1.7 ! root 3568: || GET_CODE (PATTERN (new_thread)) == RETURN) ! 3569: && redirect_with_delay_list_safe_p (insn, ! 3570: JUMP_LABEL (new_thread), ! 3571: delay_list)) 1.1.1.4 root 3572: new_thread = follow_jumps (JUMP_LABEL (new_thread)); 1.1 root 3573: 3574: if (new_thread == 0) 3575: label = find_end_label (); 3576: else if (GET_CODE (new_thread) == CODE_LABEL) 3577: label = new_thread; 3578: else 3579: label = get_label_before (new_thread); 3580: 1.1.1.5 root 3581: reorg_redirect_jump (insn, label); 1.1 root 3582: } 3583: 3584: return delay_list; 3585: } 3586: 3587: /* Make another attempt to find insns to place in delay slots. 3588: 3589: We previously looked for insns located in front of the delay insn 3590: and, for non-jump delay insns, located behind the delay insn. 3591: 3592: Here only try to schedule jump insns and try to move insns from either 3593: the target or the following insns into the delay slot. If annulling is 3594: supported, we will be likely to do this. Otherwise, we can do this only 3595: if safe. */ 3596: 3597: static void 3598: fill_eager_delay_slots (first) 3599: rtx first; 3600: { 3601: register rtx insn; 3602: register int i; 3603: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base; 3604: 3605: for (i = 0; i < num_unfilled_slots; i++) 3606: { 3607: rtx condition; 3608: rtx target_label, insn_at_target, fallthrough_insn; 3609: rtx delay_list = 0; 3610: int own_target; 3611: int own_fallthrough; 3612: int prediction, slots_to_fill, slots_filled; 3613: 3614: insn = unfilled_slots_base[i]; 3615: if (insn == 0 3616: || INSN_DELETED_P (insn) 3617: || GET_CODE (insn) != JUMP_INSN 1.1.1.7 ! root 3618: || ! (condjump_p (insn) || condjump_in_parallel_p (insn))) 1.1 root 3619: continue; 3620: 3621: slots_to_fill = num_delay_slots (insn); 3622: if (slots_to_fill == 0) 3623: abort (); 3624: 3625: slots_filled = 0; 3626: target_label = JUMP_LABEL (insn); 3627: condition = get_branch_condition (insn, target_label); 3628: 3629: if (condition == 0) 3630: continue; 3631: 3632: /* Get the next active fallthough and target insns and see if we own 3633: them. Then see whether the branch is likely true. We don't need 3634: to do a lot of this for unconditional branches. */ 3635: 3636: insn_at_target = next_active_insn (target_label); 3637: own_target = own_thread_p (target_label, target_label, 0); 3638: 3639: if (condition == const_true_rtx) 3640: { 3641: own_fallthrough = 0; 3642: fallthrough_insn = 0; 3643: prediction = 2; 3644: } 3645: else 3646: { 3647: fallthrough_insn = next_active_insn (insn); 1.1.1.4 root 3648: own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1); 1.1 root 3649: prediction = mostly_true_jump (insn, condition); 3650: } 3651: 3652: /* If this insn is expected to branch, first try to get insns from our 3653: target, then our fallthrough insns. If it is not, expected to branch, 3654: try the other order. */ 3655: 1.1.1.5 root 3656: if (prediction > 0) 1.1 root 3657: { 3658: delay_list 3659: = fill_slots_from_thread (insn, condition, insn_at_target, 3660: fallthrough_insn, prediction == 2, 1, 3661: own_target, own_fallthrough, 3662: slots_to_fill, &slots_filled); 3663: 3664: if (delay_list == 0 && own_fallthrough) 3665: { 3666: /* Even though we didn't find anything for delay slots, 3667: we might have found a redundant insn which we deleted 3668: from the thread that was filled. So we have to recompute 3669: the next insn at the target. */ 3670: target_label = JUMP_LABEL (insn); 3671: insn_at_target = next_active_insn (target_label); 3672: 3673: delay_list 3674: = fill_slots_from_thread (insn, condition, fallthrough_insn, 3675: insn_at_target, 0, 0, 3676: own_fallthrough, own_target, 3677: slots_to_fill, &slots_filled); 3678: } 3679: } 3680: else 3681: { 3682: if (own_fallthrough) 3683: delay_list 3684: = fill_slots_from_thread (insn, condition, fallthrough_insn, 3685: insn_at_target, 0, 0, 3686: own_fallthrough, own_target, 3687: slots_to_fill, &slots_filled); 3688: 3689: if (delay_list == 0) 3690: delay_list 3691: = fill_slots_from_thread (insn, condition, insn_at_target, 3692: next_active_insn (insn), 0, 1, 3693: own_target, own_fallthrough, 3694: slots_to_fill, &slots_filled); 3695: } 3696: 3697: if (delay_list) 3698: unfilled_slots_base[i] 3699: = emit_delay_sequence (insn, delay_list, 3700: slots_filled, slots_to_fill); 3701: 3702: if (slots_to_fill == slots_filled) 3703: unfilled_slots_base[i] = 0; 3704: 3705: note_delay_statistics (slots_filled, 1); 3706: } 3707: } 3708: 3709: /* Once we have tried two ways to fill a delay slot, make a pass over the 3710: code to try to improve the results and to do such things as more jump 3711: threading. */ 3712: 3713: static void 3714: relax_delay_slots (first) 3715: rtx first; 3716: { 3717: register rtx insn, next, pat; 3718: register rtx trial, delay_insn, target_label; 3719: 3720: /* Look at every JUMP_INSN and see if we can improve it. */ 3721: for (insn = first; insn; insn = next) 3722: { 3723: rtx other; 3724: 3725: next = next_active_insn (insn); 3726: 3727: /* If this is a jump insn, see if it now jumps to a jump, jumps to 3728: the next insn, or jumps to a label that is not the last of a 3729: group of consecutive labels. */ 3730: if (GET_CODE (insn) == JUMP_INSN 1.1.1.7 ! root 3731: && (condjump_p (insn) || condjump_in_parallel_p (insn)) 1.1 root 3732: && (target_label = JUMP_LABEL (insn)) != 0) 3733: { 1.1.1.4 root 3734: target_label = follow_jumps (target_label); 1.1 root 3735: target_label = prev_label (next_active_insn (target_label)); 3736: 1.1.1.3 root 3737: if (target_label == 0) 3738: target_label = find_end_label (); 3739: 1.1.1.7 ! root 3740: if (next_active_insn (target_label) == next ! 3741: && ! condjump_in_parallel_p (insn)) 1.1 root 3742: { 3743: delete_jump (insn); 3744: continue; 3745: } 3746: 3747: if (target_label != JUMP_LABEL (insn)) 1.1.1.5 root 3748: reorg_redirect_jump (insn, target_label); 1.1 root 3749: 3750: /* See if this jump branches around a unconditional jump. 3751: If so, invert this jump and point it to the target of the 3752: second jump. */ 3753: if (next && GET_CODE (next) == JUMP_INSN 3754: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 3755: && next_active_insn (target_label) == next_active_insn (next) 3756: && no_labels_between_p (insn, next)) 3757: { 3758: rtx label = JUMP_LABEL (next); 3759: 3760: /* Be careful how we do this to avoid deleting code or 3761: labels that are momentarily dead. See similar optimization 3762: in jump.c. 3763: 3764: We also need to ensure we properly handle the case when 3765: invert_jump fails. */ 3766: 3767: ++LABEL_NUSES (target_label); 3768: if (label) 3769: ++LABEL_NUSES (label); 3770: 3771: if (invert_jump (insn, label)) 3772: { 3773: delete_insn (next); 3774: next = insn; 3775: } 3776: 3777: if (label) 3778: --LABEL_NUSES (label); 3779: 3780: if (--LABEL_NUSES (target_label) == 0) 3781: delete_insn (target_label); 3782: 3783: continue; 3784: } 3785: } 3786: 3787: /* If this is an unconditional jump and the previous insn is a 3788: conditional jump, try reversing the condition of the previous 3789: insn and swapping our targets. The next pass might be able to 3790: fill the slots. 3791: 3792: Don't do this if we expect the conditional branch to be true, because 3793: we would then be making the more common case longer. */ 3794: 3795: if (GET_CODE (insn) == JUMP_INSN 3796: && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN) 3797: && (other = prev_active_insn (insn)) != 0 1.1.1.7 ! root 3798: && (condjump_p (other) || condjump_in_parallel_p (other)) 1.1 root 3799: && no_labels_between_p (other, insn) 1.1.1.5 root 3800: && 0 < mostly_true_jump (other, 3801: get_branch_condition (other, 3802: JUMP_LABEL (other)))) 1.1 root 3803: { 3804: rtx other_target = JUMP_LABEL (other); 1.1.1.5 root 3805: target_label = JUMP_LABEL (insn); 1.1 root 3806: 3807: /* Increment the count of OTHER_TARGET, so it doesn't get deleted 3808: as we move the label. */ 3809: if (other_target) 3810: ++LABEL_NUSES (other_target); 3811: 3812: if (invert_jump (other, target_label)) 1.1.1.5 root 3813: reorg_redirect_jump (insn, other_target); 1.1 root 3814: 3815: if (other_target) 3816: --LABEL_NUSES (other_target); 3817: } 3818: 3819: /* Now look only at cases where we have filled a delay slot. */ 3820: if (GET_CODE (insn) != INSN 3821: || GET_CODE (PATTERN (insn)) != SEQUENCE) 3822: continue; 3823: 3824: pat = PATTERN (insn); 3825: delay_insn = XVECEXP (pat, 0, 0); 3826: 3827: /* See if the first insn in the delay slot is redundant with some 3828: previous insn. Remove it from the delay slot if so; then set up 3829: to reprocess this insn. */ 3830: if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0)) 3831: { 3832: delete_from_delay_slot (XVECEXP (pat, 0, 1)); 3833: next = prev_active_insn (next); 3834: continue; 3835: } 3836: 3837: /* Now look only at the cases where we have a filled JUMP_INSN. */ 3838: if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN 1.1.1.7 ! root 3839: || ! (condjump_p (XVECEXP (PATTERN (insn), 0, 0)) ! 3840: || condjump_in_parallel_p (XVECEXP (PATTERN (insn), 0, 0)))) 1.1 root 3841: continue; 3842: 3843: target_label = JUMP_LABEL (delay_insn); 3844: 3845: if (target_label) 3846: { 3847: /* If this jump goes to another unconditional jump, thread it, but 3848: don't convert a jump into a RETURN here. */ 1.1.1.4 root 3849: trial = follow_jumps (target_label); 1.1 root 3850: trial = prev_label (next_active_insn (trial)); 3851: if (trial == 0 && target_label != 0) 3852: trial = find_end_label (); 3853: 1.1.1.6 root 3854: if (trial != target_label 3855: && redirect_with_delay_slots_safe_p (delay_insn, trial, insn)) 1.1 root 3856: { 1.1.1.5 root 3857: reorg_redirect_jump (delay_insn, trial); 1.1 root 3858: target_label = trial; 3859: } 3860: 3861: /* If the first insn at TARGET_LABEL is redundant with a previous 3862: insn, redirect the jump to the following insn process again. */ 3863: trial = next_active_insn (target_label); 3864: if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE 3865: && redundant_insn_p (trial, insn, 0)) 3866: { 3867: trial = next_active_insn (trial); 3868: if (trial == 0) 3869: target_label = find_end_label (); 3870: else 3871: target_label = get_label_before (trial); 1.1.1.5 root 3872: reorg_redirect_jump (delay_insn, target_label); 1.1 root 3873: next = insn; 3874: continue; 3875: } 3876: 3877: /* Similarly, if it is an unconditional jump with one insn in its 3878: delay list and that insn is redundant, thread the jump. */ 3879: if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE 3880: && XVECLEN (PATTERN (trial), 0) == 2 3881: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN 3882: && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0)) 3883: || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN) 3884: && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0)) 3885: { 3886: target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0)); 3887: if (target_label == 0) 3888: target_label = find_end_label (); 1.1.1.6 root 3889: 3890: if (redirect_with_delay_slots_safe_p (delay_insn, target_label, 3891: insn)) 3892: { 3893: reorg_redirect_jump (delay_insn, target_label); 3894: next = insn; 3895: continue; 3896: } 1.1 root 3897: } 3898: } 3899: 3900: if (! INSN_ANNULLED_BRANCH_P (delay_insn) 3901: && prev_active_insn (target_label) == insn 1.1.1.7 ! root 3902: && ! condjump_in_parallel_p (delay_insn) 1.1 root 3903: #ifdef HAVE_cc0 3904: /* If the last insn in the delay slot sets CC0 for some insn, 3905: various code assumes that it is in a delay slot. We could 3906: put it back where it belonged and delete the register notes, 1.1.1.3 root 3907: but it doesn't seem worthwhile in this uncommon case. */ 1.1 root 3908: && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1), 1.1.1.4 root 3909: REG_CC_USER, NULL_RTX) 1.1 root 3910: #endif 3911: ) 3912: { 1.1.1.3 root 3913: int i; 3914: 1.1 root 3915: /* All this insn does is execute its delay list and jump to the 3916: following insn. So delete the jump and just execute the delay 3917: list insns. 3918: 3919: We do this by deleting the INSN containing the SEQUENCE, then 3920: re-emitting the insns separately, and then deleting the jump. 3921: This allows the count of the jump target to be properly 3922: decremented. */ 3923: 1.1.1.3 root 3924: /* Clear the from target bit, since these insns are no longer 3925: in delay slots. */ 3926: for (i = 0; i < XVECLEN (pat, 0); i++) 3927: INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0; 3928: 1.1 root 3929: trial = PREV_INSN (insn); 3930: delete_insn (insn); 3931: emit_insn_after (pat, trial); 3932: delete_scheduled_jump (delay_insn); 3933: continue; 3934: } 3935: 1.1.1.5 root 3936: /* See if this is an unconditional jump around a single insn which is 3937: identical to the one in its delay slot. In this case, we can just 3938: delete the branch and the insn in its delay slot. */ 3939: if (next && GET_CODE (next) == INSN 3940: && prev_label (next_active_insn (next)) == target_label 3941: && simplejump_p (insn) 3942: && XVECLEN (pat, 0) == 2 3943: && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1)))) 3944: { 3945: delete_insn (insn); 3946: continue; 3947: } 3948: 1.1 root 3949: /* See if this jump (with its delay slots) branches around another 3950: jump (without delay slots). If so, invert this jump and point 3951: it to the target of the second jump. We cannot do this for 3952: annulled jumps, though. Again, don't convert a jump to a RETURN 3953: here. */ 3954: if (! INSN_ANNULLED_BRANCH_P (delay_insn) 3955: && next && GET_CODE (next) == JUMP_INSN 3956: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN) 3957: && next_active_insn (target_label) == next_active_insn (next) 3958: && no_labels_between_p (insn, next)) 3959: { 3960: rtx label = JUMP_LABEL (next); 3961: rtx old_label = JUMP_LABEL (delay_insn); 3962: 3963: if (label == 0) 3964: label = find_end_label (); 3965: 1.1.1.6 root 3966: if (redirect_with_delay_slots_safe_p (delay_insn, label, insn)) 1.1 root 3967: { 1.1.1.6 root 3968: /* Be careful how we do this to avoid deleting code or labels 3969: that are momentarily dead. See similar optimization in 3970: jump.c */ 3971: if (old_label) 3972: ++LABEL_NUSES (old_label); 1.1 root 3973: 1.1.1.6 root 3974: if (invert_jump (delay_insn, label)) 3975: { 1.1.1.7 ! root 3976: int i; ! 3977: ! 3978: /* Must update the INSN_FROM_TARGET_P bits now that ! 3979: the branch is reversed, so that mark_target_live_regs ! 3980: will handle the delay slot insn correctly. */ ! 3981: for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++) ! 3982: { ! 3983: rtx slot = XVECEXP (PATTERN (insn), 0, i); ! 3984: INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot); ! 3985: } ! 3986: 1.1.1.6 root 3987: delete_insn (next); 3988: next = insn; 3989: } 3990: 3991: if (old_label && --LABEL_NUSES (old_label) == 0) 3992: delete_insn (old_label); 3993: continue; 3994: } 1.1 root 3995: } 3996: 3997: /* If we own the thread opposite the way this insn branches, see if we 3998: can merge its delay slots with following insns. */ 3999: if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 4000: && own_thread_p (NEXT_INSN (insn), 0, 1)) 4001: try_merge_delay_insns (insn, next); 4002: else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1)) 4003: && own_thread_p (target_label, target_label, 0)) 4004: try_merge_delay_insns (insn, next_active_insn (target_label)); 4005: 4006: /* If we get here, we haven't deleted INSN. But we may have deleted 4007: NEXT, so recompute it. */ 4008: next = next_active_insn (insn); 4009: } 4010: } 4011: 4012: #ifdef HAVE_return 4013: 4014: /* Look for filled jumps to the end of function label. We can try to convert 4015: them into RETURN insns if the insns in the delay slot are valid for the 4016: RETURN as well. */ 4017: 4018: static void 4019: make_return_insns (first) 4020: rtx first; 4021: { 4022: rtx insn, jump_insn, pat; 4023: rtx real_return_label = end_of_function_label; 4024: int slots, i; 4025: 4026: /* See if there is a RETURN insn in the function other than the one we 4027: made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change 4028: into a RETURN to jump to it. */ 4029: for (insn = first; insn; insn = NEXT_INSN (insn)) 4030: if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN) 4031: { 4032: real_return_label = get_label_before (insn); 4033: break; 4034: } 4035: 4036: /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it 4037: was equal to END_OF_FUNCTION_LABEL. */ 4038: LABEL_NUSES (real_return_label)++; 4039: 4040: /* Clear the list of insns to fill so we can use it. */ 4041: obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 4042: 4043: for (insn = first; insn; insn = NEXT_INSN (insn)) 4044: { 1.1.1.5 root 4045: int flags; 4046: 1.1 root 4047: /* Only look at filled JUMP_INSNs that go to the end of function 4048: label. */ 4049: if (GET_CODE (insn) != INSN 4050: || GET_CODE (PATTERN (insn)) != SEQUENCE 4051: || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN 4052: || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label) 4053: continue; 4054: 4055: pat = PATTERN (insn); 4056: jump_insn = XVECEXP (pat, 0, 0); 4057: 1.1.1.7 ! root 4058: /* If we can't make the jump into a RETURN, try to redirect it to the best 1.1 root 4059: RETURN and go on to the next insn. */ 1.1.1.5 root 4060: if (! reorg_redirect_jump (jump_insn, NULL_RTX)) 1.1 root 4061: { 1.1.1.7 ! root 4062: /* Make sure redirecting the jump will not invalidate the delay ! 4063: slot insns. */ ! 4064: if (redirect_with_delay_slots_safe_p (jump_insn, ! 4065: real_return_label, ! 4066: insn)) ! 4067: reorg_redirect_jump (jump_insn, real_return_label); 1.1 root 4068: continue; 4069: } 4070: 4071: /* See if this RETURN can accept the insns current in its delay slot. 4072: It can if it has more or an equal number of slots and the contents 4073: of each is valid. */ 4074: 1.1.1.5 root 4075: flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn)); 1.1 root 4076: slots = num_delay_slots (jump_insn); 4077: if (slots >= XVECLEN (pat, 0) - 1) 4078: { 4079: for (i = 1; i < XVECLEN (pat, 0); i++) 4080: if (! ( 4081: #ifdef ANNUL_IFFALSE_SLOTS 4082: (INSN_ANNULLED_BRANCH_P (jump_insn) 4083: && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 4084: ? eligible_for_annul_false (jump_insn, i - 1, 1.1.1.5 root 4085: XVECEXP (pat, 0, i), flags) : 1.1 root 4086: #endif 4087: #ifdef ANNUL_IFTRUE_SLOTS 4088: (INSN_ANNULLED_BRANCH_P (jump_insn) 4089: && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i))) 4090: ? eligible_for_annul_true (jump_insn, i - 1, 1.1.1.5 root 4091: XVECEXP (pat, 0, i), flags) : 1.1 root 4092: #endif 1.1.1.5 root 4093: eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags))) 1.1 root 4094: break; 4095: } 4096: else 4097: i = 0; 4098: 4099: if (i == XVECLEN (pat, 0)) 4100: continue; 4101: 4102: /* We have to do something with this insn. If it is an unconditional 4103: RETURN, delete the SEQUENCE and output the individual insns, 4104: followed by the RETURN. Then set things up so we try to find 4105: insns for its delay slots, if it needs some. */ 4106: if (GET_CODE (PATTERN (jump_insn)) == RETURN) 4107: { 4108: rtx prev = PREV_INSN (insn); 4109: 4110: delete_insn (insn); 4111: for (i = 1; i < XVECLEN (pat, 0); i++) 4112: prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev); 4113: 4114: insn = emit_jump_insn_after (PATTERN (jump_insn), prev); 4115: emit_barrier_after (insn); 4116: 4117: if (slots) 4118: obstack_ptr_grow (&unfilled_slots_obstack, insn); 4119: } 4120: else 4121: /* It is probably more efficient to keep this with its current 4122: delay slot as a branch to a RETURN. */ 1.1.1.5 root 4123: reorg_redirect_jump (jump_insn, real_return_label); 1.1 root 4124: } 4125: 4126: /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any 4127: new delay slots we have created. */ 4128: if (--LABEL_NUSES (real_return_label) == 0) 4129: delete_insn (real_return_label); 4130: 4131: fill_simple_delay_slots (first, 1); 4132: fill_simple_delay_slots (first, 0); 4133: } 4134: #endif 4135: 4136: /* Try to find insns to place in delay slots. */ 4137: 4138: void 4139: dbr_schedule (first, file) 4140: rtx first; 4141: FILE *file; 4142: { 1.1.1.4 root 4143: rtx insn, next, epilogue_insn = 0; 1.1 root 4144: int i; 4145: #if 0 4146: int old_flag_no_peephole = flag_no_peephole; 4147: 4148: /* Execute `final' once in prescan mode to delete any insns that won't be 4149: used. Don't let final try to do any peephole optimization--it will 4150: ruin dataflow information for this pass. */ 4151: 4152: flag_no_peephole = 1; 4153: final (first, 0, NO_DEBUG, 1, 1); 4154: flag_no_peephole = old_flag_no_peephole; 4155: #endif 4156: 1.1.1.5 root 4157: /* If the current function has no insns other than the prologue and 4158: epilogue, then do not try to fill any delay slots. */ 4159: if (n_basic_blocks == 0) 4160: return; 4161: 1.1 root 4162: /* Find the highest INSN_UID and allocate and initialize our map from 4163: INSN_UID's to position in code. */ 4164: for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn)) 1.1.1.4 root 4165: { 4166: if (INSN_UID (insn) > max_uid) 4167: max_uid = INSN_UID (insn); 4168: if (GET_CODE (insn) == NOTE 4169: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG) 4170: epilogue_insn = insn; 4171: } 1.1 root 4172: 4173: uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *)); 4174: for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn)) 4175: uid_to_ruid[INSN_UID (insn)] = i; 4176: 4177: /* Initialize the list of insns that need filling. */ 4178: if (unfilled_firstobj == 0) 4179: { 4180: gcc_obstack_init (&unfilled_slots_obstack); 4181: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0); 4182: } 4183: 4184: for (insn = next_active_insn (first); insn; insn = next_active_insn (insn)) 4185: { 4186: rtx target; 4187: 4188: INSN_ANNULLED_BRANCH_P (insn) = 0; 4189: INSN_FROM_TARGET_P (insn) = 0; 4190: 4191: /* Skip vector tables. We can't get attributes for them. */ 4192: if (GET_CODE (insn) == JUMP_INSN 4193: && (GET_CODE (PATTERN (insn)) == ADDR_VEC 4194: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 4195: continue; 4196: 4197: if (num_delay_slots (insn) > 0) 4198: obstack_ptr_grow (&unfilled_slots_obstack, insn); 4199: 4200: /* Ensure all jumps go to the last of a set of consecutive labels. */ 1.1.1.7 ! root 4201: if (GET_CODE (insn) == JUMP_INSN ! 4202: && (condjump_p (insn) || condjump_in_parallel_p (insn)) 1.1 root 4203: && JUMP_LABEL (insn) != 0 4204: && ((target = prev_label (next_active_insn (JUMP_LABEL (insn)))) 4205: != JUMP_LABEL (insn))) 4206: redirect_jump (insn, target); 4207: } 4208: 4209: /* Indicate what resources are required to be valid at the end of the current 4210: function. The condition code never is and memory always is. If the 4211: frame pointer is needed, it is and so is the stack pointer unless 4212: EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the 1.1.1.3 root 4213: stack pointer is. Registers used to return the function value are 4214: needed. Registers holding global variables are needed. */ 1.1 root 4215: 4216: end_of_function_needs.cc = 0; 4217: end_of_function_needs.memory = 1; 4218: CLEAR_HARD_REG_SET (end_of_function_needs.regs); 4219: 4220: if (frame_pointer_needed) 4221: { 4222: SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM); 1.1.1.6 root 4223: #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 4224: SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM); 4225: #endif 1.1 root 4226: #ifdef EXIT_IGNORE_STACK 4227: if (! EXIT_IGNORE_STACK) 4228: #endif 4229: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM); 4230: } 4231: else 4232: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM); 4233: 4234: if (current_function_return_rtx != 0 4235: && GET_CODE (current_function_return_rtx) == REG) 4236: mark_referenced_resources (current_function_return_rtx, 1.1.1.5 root 4237: &end_of_function_needs, 1); 1.1 root 4238: 1.1.1.3 root 4239: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 4240: if (global_regs[i]) 4241: SET_HARD_REG_BIT (end_of_function_needs.regs, i); 4242: 1.1.1.4 root 4243: /* The registers required to be live at the end of the function are 4244: represented in the flow information as being dead just prior to 4245: reaching the end of the function. For example, the return of a value 4246: might be represented by a USE of the return register immediately 4247: followed by an unconditional jump to the return label where the 4248: return label is the end of the RTL chain. The end of the RTL chain 4249: is then taken to mean that the return register is live. 4250: 4251: This sequence is no longer maintained when epilogue instructions are 4252: added to the RTL chain. To reconstruct the original meaning, the 4253: start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the 4254: point where these registers become live (start_of_epilogue_needs). 4255: If epilogue instructions are present, the registers set by those 4256: instructions won't have been processed by flow. Thus, those 4257: registers are additionally required at the end of the RTL chain 4258: (end_of_function_needs). */ 4259: 4260: start_of_epilogue_needs = end_of_function_needs; 4261: 4262: while (epilogue_insn = next_nonnote_insn (epilogue_insn)) 1.1.1.5 root 4263: mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1); 1.1.1.4 root 4264: 1.1 root 4265: /* Show we haven't computed an end-of-function label yet. */ 4266: end_of_function_label = 0; 4267: 4268: /* Allocate and initialize the tables used by mark_target_live_regs. */ 4269: target_hash_table 4270: = (struct target_info **) alloca ((TARGET_HASH_PRIME 4271: * sizeof (struct target_info *))); 4272: bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *)); 4273: 4274: bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int)); 4275: bzero (bb_ticks, n_basic_blocks * sizeof (int)); 4276: 4277: /* Initialize the statistics for this function. */ 4278: bzero (num_insns_needing_delays, sizeof num_insns_needing_delays); 4279: bzero (num_filled_delays, sizeof num_filled_delays); 4280: 4281: /* Now do the delay slot filling. Try everything twice in case earlier 4282: changes make more slots fillable. */ 4283: 4284: for (reorg_pass_number = 0; 4285: reorg_pass_number < MAX_REORG_PASSES; 4286: reorg_pass_number++) 4287: { 4288: fill_simple_delay_slots (first, 1); 4289: fill_simple_delay_slots (first, 0); 4290: fill_eager_delay_slots (first); 4291: relax_delay_slots (first); 4292: } 4293: 4294: /* Delete any USE insns made by update_block; subsequent passes don't need 4295: them or know how to deal with them. */ 4296: for (insn = first; insn; insn = next) 4297: { 4298: next = NEXT_INSN (insn); 4299: 4300: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE 1.1.1.4 root 4301: && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i') 1.1 root 4302: next = delete_insn (insn); 4303: } 4304: 4305: /* If we made an end of function label, indicate that it is now 4306: safe to delete it by undoing our prior adjustment to LABEL_NUSES. 4307: If it is now unused, delete it. */ 4308: if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0) 4309: delete_insn (end_of_function_label); 4310: 4311: #ifdef HAVE_return 4312: if (HAVE_return && end_of_function_label != 0) 4313: make_return_insns (first); 4314: #endif 4315: 4316: obstack_free (&unfilled_slots_obstack, unfilled_firstobj); 4317: 4318: /* It is not clear why the line below is needed, but it does seem to be. */ 4319: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0); 4320: 1.1.1.4 root 4321: /* Reposition the prologue and epilogue notes in case we moved the 4322: prologue/epilogue insns. */ 4323: reposition_prologue_and_epilogue_notes (first); 4324: 1.1 root 4325: if (file) 4326: { 4327: register int i, j, need_comma; 4328: 4329: for (reorg_pass_number = 0; 4330: reorg_pass_number < MAX_REORG_PASSES; 4331: reorg_pass_number++) 4332: { 4333: fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1); 4334: for (i = 0; i < NUM_REORG_FUNCTIONS; i++) 4335: { 4336: need_comma = 0; 4337: fprintf (file, ";; Reorg function #%d\n", i); 4338: 4339: fprintf (file, ";; %d insns needing delay slots\n;; ", 4340: num_insns_needing_delays[i][reorg_pass_number]); 4341: 4342: for (j = 0; j < MAX_DELAY_HISTOGRAM; j++) 4343: if (num_filled_delays[i][j][reorg_pass_number]) 4344: { 4345: if (need_comma) 4346: fprintf (file, ", "); 4347: need_comma = 1; 4348: fprintf (file, "%d got %d delays", 4349: num_filled_delays[i][j][reorg_pass_number], j); 4350: } 4351: fprintf (file, "\n"); 4352: } 4353: } 4354: } 4355: } 4356: #endif /* DELAY_SLOTS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.