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