1169689Skan/* RTL-level loop invariant motion. 2169689Skan Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan/* This implements the loop invariant motion pass. It is very simple 22169689Skan (no calls, libcalls, etc.). This should be sufficient to cleanup things 23169689Skan like address arithmetics -- other more complicated invariants should be 24169689Skan eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c. 25169689Skan 26169689Skan We proceed loop by loop -- it is simpler than trying to handle things 27169689Skan globally and should not lose much. First we inspect all sets inside loop 28169689Skan and create a dependency graph on insns (saying "to move this insn, you must 29169689Skan also move the following insns"). 30169689Skan 31169689Skan We then need to determine what to move. We estimate the number of registers 32169689Skan used and move as many invariants as possible while we still have enough free 33169689Skan registers. We prefer the expensive invariants. 34169689Skan 35169689Skan Then we move the selected invariants out of the loop, creating a new 36169689Skan temporaries for them if necessary. */ 37169689Skan 38169689Skan#include "config.h" 39169689Skan#include "system.h" 40169689Skan#include "coretypes.h" 41169689Skan#include "tm.h" 42169689Skan#include "rtl.h" 43169689Skan#include "tm_p.h" 44169689Skan#include "hard-reg-set.h" 45169689Skan#include "obstack.h" 46169689Skan#include "basic-block.h" 47169689Skan#include "cfgloop.h" 48169689Skan#include "expr.h" 49169689Skan#include "recog.h" 50169689Skan#include "output.h" 51169689Skan#include "function.h" 52169689Skan#include "flags.h" 53169689Skan#include "df.h" 54169689Skan#include "hashtab.h" 55169689Skan#include "except.h" 56169689Skan 57169689Skan/* The data stored for the loop. */ 58169689Skan 59169689Skanstruct loop_data 60169689Skan{ 61169689Skan struct loop *outermost_exit; /* The outermost exit of the loop. */ 62169689Skan bool has_call; /* True if the loop contains a call. */ 63169689Skan}; 64169689Skan 65169689Skan#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux) 66169689Skan 67169689Skan/* The description of an use. */ 68169689Skan 69169689Skanstruct use 70169689Skan{ 71169689Skan rtx *pos; /* Position of the use. */ 72169689Skan rtx insn; /* The insn in that the use occurs. */ 73169689Skan 74169689Skan struct use *next; /* Next use in the list. */ 75169689Skan}; 76169689Skan 77169689Skan/* The description of a def. */ 78169689Skan 79169689Skanstruct def 80169689Skan{ 81169689Skan struct use *uses; /* The list of uses that are uniquely reached 82169689Skan by it. */ 83169689Skan unsigned n_uses; /* Number of such uses. */ 84169689Skan unsigned invno; /* The corresponding invariant. */ 85169689Skan}; 86169689Skan 87169689Skan/* The data stored for each invariant. */ 88169689Skan 89169689Skanstruct invariant 90169689Skan{ 91169689Skan /* The number of the invariant. */ 92169689Skan unsigned invno; 93169689Skan 94169689Skan /* The number of the invariant with the same value. */ 95169689Skan unsigned eqto; 96169689Skan 97169689Skan /* If we moved the invariant out of the loop, the register that contains its 98169689Skan value. */ 99169689Skan rtx reg; 100169689Skan 101169689Skan /* The definition of the invariant. */ 102169689Skan struct def *def; 103169689Skan 104169689Skan /* The insn in that it is defined. */ 105169689Skan rtx insn; 106169689Skan 107169689Skan /* Whether it is always executed. */ 108169689Skan bool always_executed; 109169689Skan 110169689Skan /* Whether to move the invariant. */ 111169689Skan bool move; 112169689Skan 113169689Skan /* Cost of the invariant. */ 114169689Skan unsigned cost; 115169689Skan 116169689Skan /* The invariants it depends on. */ 117169689Skan bitmap depends_on; 118169689Skan 119169689Skan /* Used for detecting already visited invariants during determining 120169689Skan costs of movements. */ 121169689Skan unsigned stamp; 122169689Skan}; 123169689Skan 124169689Skan/* Entry for hash table of invariant expressions. */ 125169689Skan 126169689Skanstruct invariant_expr_entry 127169689Skan{ 128169689Skan /* The invariant. */ 129169689Skan struct invariant *inv; 130169689Skan 131169689Skan /* Its value. */ 132169689Skan rtx expr; 133169689Skan 134169689Skan /* Its mode. */ 135169689Skan enum machine_mode mode; 136169689Skan 137169689Skan /* Its hash. */ 138169689Skan hashval_t hash; 139169689Skan}; 140169689Skan 141169689Skan/* The actual stamp for marking already visited invariants during determining 142169689Skan costs of movements. */ 143169689Skan 144169689Skanstatic unsigned actual_stamp; 145169689Skan 146169689Skantypedef struct invariant *invariant_p; 147169689Skan 148169689SkanDEF_VEC_P(invariant_p); 149169689SkanDEF_VEC_ALLOC_P(invariant_p, heap); 150169689Skan 151169689Skan/* The invariants. */ 152169689Skan 153169689Skanstatic VEC(invariant_p,heap) *invariants; 154169689Skan 155169689Skan/* The dataflow object. */ 156169689Skan 157169689Skanstatic struct df *df = NULL; 158169689Skan 159169689Skan/* Test for possibility of invariantness of X. */ 160169689Skan 161169689Skanstatic bool 162169689Skancheck_maybe_invariant (rtx x) 163169689Skan{ 164169689Skan enum rtx_code code = GET_CODE (x); 165169689Skan int i, j; 166169689Skan const char *fmt; 167169689Skan 168169689Skan switch (code) 169169689Skan { 170169689Skan case CONST_INT: 171169689Skan case CONST_DOUBLE: 172169689Skan case SYMBOL_REF: 173169689Skan case CONST: 174169689Skan case LABEL_REF: 175169689Skan return true; 176169689Skan 177169689Skan case PC: 178169689Skan case CC0: 179169689Skan case UNSPEC_VOLATILE: 180169689Skan case CALL: 181169689Skan return false; 182169689Skan 183169689Skan case REG: 184169689Skan return true; 185169689Skan 186169689Skan case MEM: 187169689Skan /* Load/store motion is done elsewhere. ??? Perhaps also add it here? 188169689Skan It should not be hard, and might be faster than "elsewhere". */ 189169689Skan 190169689Skan /* Just handle the most trivial case where we load from an unchanging 191169689Skan location (most importantly, pic tables). */ 192169689Skan if (MEM_READONLY_P (x)) 193169689Skan break; 194169689Skan 195169689Skan return false; 196169689Skan 197169689Skan case ASM_OPERANDS: 198169689Skan /* Don't mess with insns declared volatile. */ 199169689Skan if (MEM_VOLATILE_P (x)) 200169689Skan return false; 201169689Skan break; 202169689Skan 203169689Skan default: 204169689Skan break; 205169689Skan } 206169689Skan 207169689Skan fmt = GET_RTX_FORMAT (code); 208169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 209169689Skan { 210169689Skan if (fmt[i] == 'e') 211169689Skan { 212169689Skan if (!check_maybe_invariant (XEXP (x, i))) 213169689Skan return false; 214169689Skan } 215169689Skan else if (fmt[i] == 'E') 216169689Skan { 217169689Skan for (j = 0; j < XVECLEN (x, i); j++) 218169689Skan if (!check_maybe_invariant (XVECEXP (x, i, j))) 219169689Skan return false; 220169689Skan } 221169689Skan } 222169689Skan 223169689Skan return true; 224169689Skan} 225169689Skan 226169689Skan/* Returns the invariant definition for USE, or NULL if USE is not 227169689Skan invariant. */ 228169689Skan 229169689Skanstatic struct invariant * 230169689Skaninvariant_for_use (struct df_ref *use) 231169689Skan{ 232169689Skan struct df_link *defs; 233169689Skan struct df_ref *def; 234169689Skan basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb; 235169689Skan 236169689Skan if (use->flags & DF_REF_READ_WRITE) 237169689Skan return NULL; 238169689Skan 239169689Skan defs = DF_REF_CHAIN (use); 240169689Skan if (!defs || defs->next) 241169689Skan return NULL; 242169689Skan def = defs->ref; 243169689Skan if (!DF_REF_DATA (def)) 244169689Skan return NULL; 245169689Skan 246169689Skan def_bb = DF_REF_BB (def); 247169689Skan if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 248169689Skan return NULL; 249169689Skan return DF_REF_DATA (def); 250169689Skan} 251169689Skan 252169689Skan/* Computes hash value for invariant expression X in INSN. */ 253169689Skan 254169689Skanstatic hashval_t 255169689Skanhash_invariant_expr_1 (rtx insn, rtx x) 256169689Skan{ 257169689Skan enum rtx_code code = GET_CODE (x); 258169689Skan int i, j; 259169689Skan const char *fmt; 260169689Skan hashval_t val = code; 261169689Skan int do_not_record_p; 262169689Skan struct df_ref *use; 263169689Skan struct invariant *inv; 264169689Skan 265169689Skan switch (code) 266169689Skan { 267169689Skan case CONST_INT: 268169689Skan case CONST_DOUBLE: 269169689Skan case SYMBOL_REF: 270169689Skan case CONST: 271169689Skan case LABEL_REF: 272169689Skan return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 273169689Skan 274169689Skan case REG: 275169689Skan use = df_find_use (df, insn, x); 276169689Skan if (!use) 277169689Skan return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 278169689Skan inv = invariant_for_use (use); 279169689Skan if (!inv) 280169689Skan return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false); 281169689Skan 282169689Skan gcc_assert (inv->eqto != ~0u); 283169689Skan return inv->eqto; 284169689Skan 285169689Skan default: 286169689Skan break; 287169689Skan } 288169689Skan 289169689Skan fmt = GET_RTX_FORMAT (code); 290169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 291169689Skan { 292169689Skan if (fmt[i] == 'e') 293169689Skan val ^= hash_invariant_expr_1 (insn, XEXP (x, i)); 294169689Skan else if (fmt[i] == 'E') 295169689Skan { 296169689Skan for (j = 0; j < XVECLEN (x, i); j++) 297169689Skan val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j)); 298169689Skan } 299169689Skan else if (fmt[i] == 'i' || fmt[i] == 'n') 300169689Skan val ^= XINT (x, i); 301169689Skan } 302169689Skan 303169689Skan return val; 304169689Skan} 305169689Skan 306169689Skan/* Returns true if the invariant expressions E1 and E2 used in insns INSN1 307169689Skan and INSN2 have always the same value. */ 308169689Skan 309169689Skanstatic bool 310169689Skaninvariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2) 311169689Skan{ 312169689Skan enum rtx_code code = GET_CODE (e1); 313169689Skan int i, j; 314169689Skan const char *fmt; 315169689Skan struct df_ref *use1, *use2; 316169689Skan struct invariant *inv1 = NULL, *inv2 = NULL; 317169689Skan rtx sub1, sub2; 318169689Skan 319169689Skan /* If mode of only one of the operands is VOIDmode, it is not equivalent to 320169689Skan the other one. If both are VOIDmode, we rely on the caller of this 321169689Skan function to verify that their modes are the same. */ 322169689Skan if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2)) 323169689Skan return false; 324169689Skan 325169689Skan switch (code) 326169689Skan { 327169689Skan case CONST_INT: 328169689Skan case CONST_DOUBLE: 329169689Skan case SYMBOL_REF: 330169689Skan case CONST: 331169689Skan case LABEL_REF: 332169689Skan return rtx_equal_p (e1, e2); 333169689Skan 334169689Skan case REG: 335169689Skan use1 = df_find_use (df, insn1, e1); 336169689Skan use2 = df_find_use (df, insn2, e2); 337169689Skan if (use1) 338169689Skan inv1 = invariant_for_use (use1); 339169689Skan if (use2) 340169689Skan inv2 = invariant_for_use (use2); 341169689Skan 342169689Skan if (!inv1 && !inv2) 343169689Skan return rtx_equal_p (e1, e2); 344169689Skan 345169689Skan if (!inv1 || !inv2) 346169689Skan return false; 347169689Skan 348169689Skan gcc_assert (inv1->eqto != ~0u); 349169689Skan gcc_assert (inv2->eqto != ~0u); 350169689Skan return inv1->eqto == inv2->eqto; 351169689Skan 352169689Skan default: 353169689Skan break; 354169689Skan } 355169689Skan 356169689Skan fmt = GET_RTX_FORMAT (code); 357169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 358169689Skan { 359169689Skan if (fmt[i] == 'e') 360169689Skan { 361169689Skan sub1 = XEXP (e1, i); 362169689Skan sub2 = XEXP (e2, i); 363169689Skan 364169689Skan if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 365169689Skan return false; 366169689Skan } 367169689Skan 368169689Skan else if (fmt[i] == 'E') 369169689Skan { 370169689Skan if (XVECLEN (e1, i) != XVECLEN (e2, i)) 371169689Skan return false; 372169689Skan 373169689Skan for (j = 0; j < XVECLEN (e1, i); j++) 374169689Skan { 375169689Skan sub1 = XVECEXP (e1, i, j); 376169689Skan sub2 = XVECEXP (e2, i, j); 377169689Skan 378169689Skan if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2)) 379169689Skan return false; 380169689Skan } 381169689Skan } 382169689Skan else if (fmt[i] == 'i' || fmt[i] == 'n') 383169689Skan { 384169689Skan if (XINT (e1, i) != XINT (e2, i)) 385169689Skan return false; 386169689Skan } 387169689Skan /* Unhandled type of subexpression, we fail conservatively. */ 388169689Skan else 389169689Skan return false; 390169689Skan } 391169689Skan 392169689Skan return true; 393169689Skan} 394169689Skan 395169689Skan/* Returns hash value for invariant expression entry E. */ 396169689Skan 397169689Skanstatic hashval_t 398169689Skanhash_invariant_expr (const void *e) 399169689Skan{ 400169689Skan const struct invariant_expr_entry *entry = e; 401169689Skan 402169689Skan return entry->hash; 403169689Skan} 404169689Skan 405169689Skan/* Compares invariant expression entries E1 and E2. */ 406169689Skan 407169689Skanstatic int 408169689Skaneq_invariant_expr (const void *e1, const void *e2) 409169689Skan{ 410169689Skan const struct invariant_expr_entry *entry1 = e1; 411169689Skan const struct invariant_expr_entry *entry2 = e2; 412169689Skan 413169689Skan if (entry1->mode != entry2->mode) 414169689Skan return 0; 415169689Skan 416169689Skan return invariant_expr_equal_p (entry1->inv->insn, entry1->expr, 417169689Skan entry2->inv->insn, entry2->expr); 418169689Skan} 419169689Skan 420169689Skan/* Checks whether invariant with value EXPR in machine mode MODE is 421169689Skan recorded in EQ. If this is the case, return the invariant. Otherwise 422169689Skan insert INV to the table for this expression and return INV. */ 423169689Skan 424169689Skanstatic struct invariant * 425169689Skanfind_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode, 426169689Skan struct invariant *inv) 427169689Skan{ 428169689Skan hashval_t hash = hash_invariant_expr_1 (inv->insn, expr); 429169689Skan struct invariant_expr_entry *entry; 430169689Skan struct invariant_expr_entry pentry; 431169689Skan PTR *slot; 432169689Skan 433169689Skan pentry.expr = expr; 434169689Skan pentry.inv = inv; 435169689Skan pentry.mode = mode; 436169689Skan slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT); 437169689Skan entry = *slot; 438169689Skan 439169689Skan if (entry) 440169689Skan return entry->inv; 441169689Skan 442169689Skan entry = XNEW (struct invariant_expr_entry); 443169689Skan entry->inv = inv; 444169689Skan entry->expr = expr; 445169689Skan entry->mode = mode; 446169689Skan entry->hash = hash; 447169689Skan *slot = entry; 448169689Skan 449169689Skan return inv; 450169689Skan} 451169689Skan 452169689Skan/* Finds invariants identical to INV and records the equivalence. EQ is the 453169689Skan hash table of the invariants. */ 454169689Skan 455169689Skanstatic void 456169689Skanfind_identical_invariants (htab_t eq, struct invariant *inv) 457169689Skan{ 458169689Skan unsigned depno; 459169689Skan bitmap_iterator bi; 460169689Skan struct invariant *dep; 461169689Skan rtx expr, set; 462169689Skan enum machine_mode mode; 463169689Skan 464169689Skan if (inv->eqto != ~0u) 465169689Skan return; 466169689Skan 467169689Skan EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 468169689Skan { 469169689Skan dep = VEC_index (invariant_p, invariants, depno); 470169689Skan find_identical_invariants (eq, dep); 471169689Skan } 472169689Skan 473169689Skan set = single_set (inv->insn); 474169689Skan expr = SET_SRC (set); 475169689Skan mode = GET_MODE (expr); 476169689Skan if (mode == VOIDmode) 477169689Skan mode = GET_MODE (SET_DEST (set)); 478169689Skan inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno; 479169689Skan 480169689Skan if (dump_file && inv->eqto != inv->invno) 481169689Skan fprintf (dump_file, 482169689Skan "Invariant %d is equivalent to invariant %d.\n", 483169689Skan inv->invno, inv->eqto); 484169689Skan} 485169689Skan 486169689Skan/* Find invariants with the same value and record the equivalences. */ 487169689Skan 488169689Skanstatic void 489169689Skanmerge_identical_invariants (void) 490169689Skan{ 491169689Skan unsigned i; 492169689Skan struct invariant *inv; 493169689Skan htab_t eq = htab_create (VEC_length (invariant_p, invariants), 494169689Skan hash_invariant_expr, eq_invariant_expr, free); 495169689Skan 496169689Skan for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 497169689Skan find_identical_invariants (eq, inv); 498169689Skan 499169689Skan htab_delete (eq); 500169689Skan} 501169689Skan 502169689Skan/* Determines the basic blocks inside LOOP that are always executed and 503169689Skan stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of 504169689Skan basic blocks that may either exit the loop, or contain the call that 505169689Skan does not have to return. BODY is body of the loop obtained by 506169689Skan get_loop_body_in_dom_order. */ 507169689Skan 508169689Skanstatic void 509169689Skancompute_always_reached (struct loop *loop, basic_block *body, 510169689Skan bitmap may_exit, bitmap always_reached) 511169689Skan{ 512169689Skan unsigned i; 513169689Skan 514169689Skan for (i = 0; i < loop->num_nodes; i++) 515169689Skan { 516169689Skan if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i])) 517169689Skan bitmap_set_bit (always_reached, i); 518169689Skan 519169689Skan if (bitmap_bit_p (may_exit, i)) 520169689Skan return; 521169689Skan } 522169689Skan} 523169689Skan 524169689Skan/* Finds exits out of the LOOP with body BODY. Marks blocks in that we may 525169689Skan exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT 526169689Skan additionally mark blocks that may exit due to a call. */ 527169689Skan 528169689Skanstatic void 529169689Skanfind_exits (struct loop *loop, basic_block *body, 530169689Skan bitmap may_exit, bitmap has_exit) 531169689Skan{ 532169689Skan unsigned i; 533169689Skan edge_iterator ei; 534169689Skan edge e; 535169689Skan struct loop *outermost_exit = loop, *aexit; 536169689Skan bool has_call = false; 537169689Skan rtx insn; 538169689Skan 539169689Skan for (i = 0; i < loop->num_nodes; i++) 540169689Skan { 541169689Skan if (body[i]->loop_father == loop) 542169689Skan { 543169689Skan FOR_BB_INSNS (body[i], insn) 544169689Skan { 545169689Skan if (CALL_P (insn) 546169689Skan && !CONST_OR_PURE_CALL_P (insn)) 547169689Skan { 548169689Skan has_call = true; 549169689Skan bitmap_set_bit (may_exit, i); 550169689Skan break; 551169689Skan } 552169689Skan } 553169689Skan 554169689Skan FOR_EACH_EDGE (e, ei, body[i]->succs) 555169689Skan { 556169689Skan if (flow_bb_inside_loop_p (loop, e->dest)) 557169689Skan continue; 558169689Skan 559169689Skan bitmap_set_bit (may_exit, i); 560169689Skan bitmap_set_bit (has_exit, i); 561169689Skan outermost_exit = find_common_loop (outermost_exit, 562169689Skan e->dest->loop_father); 563169689Skan } 564169689Skan continue; 565169689Skan } 566169689Skan 567169689Skan /* Use the data stored for the subloop to decide whether we may exit 568169689Skan through it. It is sufficient to do this for header of the loop, 569169689Skan as other basic blocks inside it must be dominated by it. */ 570169689Skan if (body[i]->loop_father->header != body[i]) 571169689Skan continue; 572169689Skan 573169689Skan if (LOOP_DATA (body[i]->loop_father)->has_call) 574169689Skan { 575169689Skan has_call = true; 576169689Skan bitmap_set_bit (may_exit, i); 577169689Skan } 578169689Skan aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit; 579169689Skan if (aexit != loop) 580169689Skan { 581169689Skan bitmap_set_bit (may_exit, i); 582169689Skan bitmap_set_bit (has_exit, i); 583169689Skan 584169689Skan if (flow_loop_nested_p (aexit, outermost_exit)) 585169689Skan outermost_exit = aexit; 586169689Skan } 587169689Skan } 588169689Skan 589169689Skan loop->aux = xcalloc (1, sizeof (struct loop_data)); 590169689Skan LOOP_DATA (loop)->outermost_exit = outermost_exit; 591169689Skan LOOP_DATA (loop)->has_call = has_call; 592169689Skan} 593169689Skan 594169689Skan/* Check whether we may assign a value to X from a register. */ 595169689Skan 596169689Skanstatic bool 597169689Skanmay_assign_reg_p (rtx x) 598169689Skan{ 599169689Skan return (GET_MODE (x) != VOIDmode 600169689Skan && GET_MODE (x) != BLKmode 601169689Skan && can_copy_p (GET_MODE (x)) 602169689Skan && (!REG_P (x) 603169689Skan || !HARD_REGISTER_P (x) 604169689Skan || REGNO_REG_CLASS (REGNO (x)) != NO_REGS)); 605169689Skan} 606169689Skan 607169689Skan/* Finds definitions that may correspond to invariants in LOOP with body 608169689Skan BODY. */ 609169689Skan 610169689Skanstatic void 611169689Skanfind_defs (struct loop *loop, basic_block *body) 612169689Skan{ 613169689Skan unsigned i; 614169689Skan bitmap blocks = BITMAP_ALLOC (NULL); 615169689Skan 616169689Skan for (i = 0; i < loop->num_nodes; i++) 617169689Skan bitmap_set_bit (blocks, body[i]->index); 618169689Skan 619169689Skan df_set_blocks (df, blocks); 620169689Skan df_analyze (df); 621169689Skan BITMAP_FREE (blocks); 622169689Skan} 623169689Skan 624169689Skan/* Creates a new invariant for definition DEF in INSN, depending on invariants 625169689Skan in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed, 626169689Skan unless the program ends due to a function call. The newly created invariant 627169689Skan is returned. */ 628169689Skan 629169689Skanstatic struct invariant * 630169689Skancreate_new_invariant (struct def *def, rtx insn, bitmap depends_on, 631169689Skan bool always_executed) 632169689Skan{ 633169689Skan struct invariant *inv = XNEW (struct invariant); 634169689Skan rtx set = single_set (insn); 635169689Skan 636169689Skan inv->def = def; 637169689Skan inv->always_executed = always_executed; 638169689Skan inv->depends_on = depends_on; 639169689Skan 640169689Skan /* If the set is simple, usually by moving it we move the whole store out of 641169689Skan the loop. Otherwise we save only cost of the computation. */ 642169689Skan if (def) 643169689Skan inv->cost = rtx_cost (set, SET); 644169689Skan else 645169689Skan inv->cost = rtx_cost (SET_SRC (set), SET); 646169689Skan 647169689Skan inv->move = false; 648169689Skan inv->reg = NULL_RTX; 649169689Skan inv->stamp = 0; 650169689Skan inv->insn = insn; 651169689Skan 652169689Skan inv->invno = VEC_length (invariant_p, invariants); 653169689Skan inv->eqto = ~0u; 654169689Skan if (def) 655169689Skan def->invno = inv->invno; 656169689Skan VEC_safe_push (invariant_p, heap, invariants, inv); 657169689Skan 658169689Skan if (dump_file) 659169689Skan { 660169689Skan fprintf (dump_file, 661169689Skan "Set in insn %d is invariant (%d), cost %d, depends on ", 662169689Skan INSN_UID (insn), inv->invno, inv->cost); 663169689Skan dump_bitmap (dump_file, inv->depends_on); 664169689Skan } 665169689Skan 666169689Skan return inv; 667169689Skan} 668169689Skan 669169689Skan/* Record USE at DEF. */ 670169689Skan 671169689Skanstatic void 672169689Skanrecord_use (struct def *def, rtx *use, rtx insn) 673169689Skan{ 674169689Skan struct use *u = XNEW (struct use); 675169689Skan 676169689Skan if (GET_CODE (*use) == SUBREG) 677169689Skan use = &SUBREG_REG (*use); 678169689Skan gcc_assert (REG_P (*use)); 679169689Skan 680169689Skan u->pos = use; 681169689Skan u->insn = insn; 682169689Skan u->next = def->uses; 683169689Skan def->uses = u; 684169689Skan def->n_uses++; 685169689Skan} 686169689Skan 687169689Skan/* Finds the invariants INSN depends on and store them to the DEPENDS_ON 688169689Skan bitmap. Returns true if all dependencies of INSN are known to be 689169689Skan loop invariants, false otherwise. */ 690169689Skan 691169689Skanstatic bool 692169689Skancheck_dependencies (rtx insn, bitmap depends_on) 693169689Skan{ 694169689Skan struct df_link *defs; 695169689Skan struct df_ref *use, *def; 696169689Skan basic_block bb = BLOCK_FOR_INSN (insn), def_bb; 697169689Skan struct def *def_data; 698169689Skan struct invariant *inv; 699169689Skan 700169689Skan for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref) 701169689Skan { 702169689Skan if (use->flags & DF_REF_READ_WRITE) 703169689Skan return false; 704169689Skan 705169689Skan defs = DF_REF_CHAIN (use); 706169689Skan if (!defs) 707169689Skan continue; 708169689Skan 709169689Skan if (defs->next) 710169689Skan return false; 711169689Skan 712169689Skan def = defs->ref; 713169689Skan inv = DF_REF_DATA (def); 714169689Skan if (!inv) 715169689Skan return false; 716169689Skan 717169689Skan def_data = inv->def; 718169689Skan gcc_assert (def_data != NULL); 719169689Skan 720169689Skan def_bb = DF_REF_BB (def); 721169689Skan /* Note that in case bb == def_bb, we know that the definition dominates 722169689Skan insn, because def has DF_REF_DATA defined and we process the insns 723169689Skan in the basic block bb sequentially. */ 724169689Skan if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 725169689Skan return false; 726169689Skan 727169689Skan bitmap_set_bit (depends_on, def_data->invno); 728169689Skan } 729169689Skan 730169689Skan return true; 731169689Skan} 732169689Skan 733169689Skan/* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always 734169689Skan executed. ALWAYS_EXECUTED is true if the insn is always executed, 735169689Skan unless the program ends due to a function call. */ 736169689Skan 737169689Skanstatic void 738169689Skanfind_invariant_insn (rtx insn, bool always_reached, bool always_executed) 739169689Skan{ 740169689Skan struct df_ref *ref; 741169689Skan struct def *def; 742169689Skan bitmap depends_on; 743169689Skan rtx set, dest; 744169689Skan bool simple = true; 745169689Skan struct invariant *inv; 746169689Skan 747169689Skan /* Until we get rid of LIBCALLS. */ 748169689Skan if (find_reg_note (insn, REG_RETVAL, NULL_RTX) 749169689Skan || find_reg_note (insn, REG_LIBCALL, NULL_RTX) 750169689Skan || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX)) 751169689Skan return; 752169689Skan 753169689Skan#ifdef HAVE_cc0 754169689Skan /* We can't move a CC0 setter without the user. */ 755169689Skan if (sets_cc0_p (insn)) 756169689Skan return; 757169689Skan#endif 758169689Skan 759169689Skan set = single_set (insn); 760169689Skan if (!set) 761169689Skan return; 762169689Skan dest = SET_DEST (set); 763169689Skan 764169689Skan if (!REG_P (dest) 765169689Skan || HARD_REGISTER_P (dest)) 766169689Skan simple = false; 767169689Skan 768169689Skan if (!may_assign_reg_p (SET_DEST (set)) 769169689Skan || !check_maybe_invariant (SET_SRC (set))) 770169689Skan return; 771169689Skan 772169689Skan /* If the insn can throw exception, we cannot move it at all without changing 773169689Skan cfg. */ 774169689Skan if (can_throw_internal (insn)) 775169689Skan return; 776169689Skan 777169689Skan /* We cannot make trapping insn executed, unless it was executed before. */ 778169689Skan if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached) 779169689Skan return; 780169689Skan 781169689Skan depends_on = BITMAP_ALLOC (NULL); 782169689Skan if (!check_dependencies (insn, depends_on)) 783169689Skan { 784169689Skan BITMAP_FREE (depends_on); 785169689Skan return; 786169689Skan } 787169689Skan 788169689Skan if (simple) 789169689Skan def = XCNEW (struct def); 790169689Skan else 791169689Skan def = NULL; 792169689Skan 793169689Skan inv = create_new_invariant (def, insn, depends_on, always_executed); 794169689Skan 795169689Skan if (simple) 796169689Skan { 797169689Skan ref = df_find_def (df, insn, dest); 798169689Skan DF_REF_DATA (ref) = inv; 799169689Skan } 800169689Skan} 801169689Skan 802169689Skan/* Record registers used in INSN that have a unique invariant definition. */ 803169689Skan 804169689Skanstatic void 805169689Skanrecord_uses (rtx insn) 806169689Skan{ 807169689Skan struct df_ref *use; 808169689Skan struct invariant *inv; 809169689Skan 810169689Skan for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref) 811169689Skan { 812169689Skan inv = invariant_for_use (use); 813169689Skan if (inv) 814169689Skan record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use)); 815169689Skan } 816169689Skan} 817169689Skan 818169689Skan/* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always 819169689Skan executed. ALWAYS_EXECUTED is true if the insn is always executed, 820169689Skan unless the program ends due to a function call. */ 821169689Skan 822169689Skanstatic void 823169689Skanfind_invariants_insn (rtx insn, bool always_reached, bool always_executed) 824169689Skan{ 825169689Skan find_invariant_insn (insn, always_reached, always_executed); 826169689Skan record_uses (insn); 827169689Skan} 828169689Skan 829169689Skan/* Finds invariants in basic block BB. ALWAYS_REACHED is true if the 830169689Skan basic block is always executed. ALWAYS_EXECUTED is true if the basic 831169689Skan block is always executed, unless the program ends due to a function 832169689Skan call. */ 833169689Skan 834169689Skanstatic void 835169689Skanfind_invariants_bb (basic_block bb, bool always_reached, bool always_executed) 836169689Skan{ 837169689Skan rtx insn; 838169689Skan 839169689Skan FOR_BB_INSNS (bb, insn) 840169689Skan { 841169689Skan if (!INSN_P (insn)) 842169689Skan continue; 843169689Skan 844169689Skan find_invariants_insn (insn, always_reached, always_executed); 845169689Skan 846169689Skan if (always_reached 847169689Skan && CALL_P (insn) 848169689Skan && !CONST_OR_PURE_CALL_P (insn)) 849169689Skan always_reached = false; 850169689Skan } 851169689Skan} 852169689Skan 853169689Skan/* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of 854169689Skan basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the 855169689Skan bitmap of basic blocks in BODY that are always executed unless the program 856169689Skan ends due to a function call. */ 857169689Skan 858169689Skanstatic void 859169689Skanfind_invariants_body (struct loop *loop, basic_block *body, 860169689Skan bitmap always_reached, bitmap always_executed) 861169689Skan{ 862169689Skan unsigned i; 863169689Skan 864169689Skan for (i = 0; i < loop->num_nodes; i++) 865169689Skan find_invariants_bb (body[i], 866169689Skan bitmap_bit_p (always_reached, i), 867169689Skan bitmap_bit_p (always_executed, i)); 868169689Skan} 869169689Skan 870169689Skan/* Finds invariants in LOOP. */ 871169689Skan 872169689Skanstatic void 873169689Skanfind_invariants (struct loop *loop) 874169689Skan{ 875169689Skan bitmap may_exit = BITMAP_ALLOC (NULL); 876169689Skan bitmap always_reached = BITMAP_ALLOC (NULL); 877169689Skan bitmap has_exit = BITMAP_ALLOC (NULL); 878169689Skan bitmap always_executed = BITMAP_ALLOC (NULL); 879169689Skan basic_block *body = get_loop_body_in_dom_order (loop); 880169689Skan 881169689Skan find_exits (loop, body, may_exit, has_exit); 882169689Skan compute_always_reached (loop, body, may_exit, always_reached); 883169689Skan compute_always_reached (loop, body, has_exit, always_executed); 884169689Skan 885169689Skan find_defs (loop, body); 886169689Skan find_invariants_body (loop, body, always_reached, always_executed); 887169689Skan merge_identical_invariants (); 888169689Skan 889169689Skan BITMAP_FREE (always_reached); 890169689Skan BITMAP_FREE (always_executed); 891169689Skan BITMAP_FREE (may_exit); 892169689Skan BITMAP_FREE (has_exit); 893169689Skan free (body); 894169689Skan} 895169689Skan 896169689Skan/* Frees a list of uses USE. */ 897169689Skan 898169689Skanstatic void 899169689Skanfree_use_list (struct use *use) 900169689Skan{ 901169689Skan struct use *next; 902169689Skan 903169689Skan for (; use; use = next) 904169689Skan { 905169689Skan next = use->next; 906169689Skan free (use); 907169689Skan } 908169689Skan} 909169689Skan 910169689Skan/* Calculates cost and number of registers needed for moving invariant INV 911169689Skan out of the loop and stores them to *COST and *REGS_NEEDED. */ 912169689Skan 913169689Skanstatic void 914169689Skanget_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed) 915169689Skan{ 916169689Skan int acomp_cost; 917169689Skan unsigned aregs_needed; 918169689Skan unsigned depno; 919169689Skan struct invariant *dep; 920169689Skan bitmap_iterator bi; 921169689Skan 922169689Skan /* Find the representative of the class of the equivalent invariants. */ 923169689Skan inv = VEC_index (invariant_p, invariants, inv->eqto); 924169689Skan 925169689Skan *comp_cost = 0; 926169689Skan *regs_needed = 0; 927169689Skan if (inv->move 928169689Skan || inv->stamp == actual_stamp) 929169689Skan return; 930169689Skan inv->stamp = actual_stamp; 931169689Skan 932169689Skan (*regs_needed)++; 933169689Skan (*comp_cost) += inv->cost; 934169689Skan 935169689Skan#ifdef STACK_REGS 936169689Skan { 937169689Skan /* Hoisting constant pool constants into stack regs may cost more than 938169689Skan just single register. On x87, the balance is affected both by the 939169689Skan small number of FP registers, and by its register stack organization, 940169689Skan that forces us to add compensation code in and around the loop to 941169689Skan shuffle the operands to the top of stack before use, and pop them 942169689Skan from the stack after the loop finishes. 943169689Skan 944169689Skan To model this effect, we increase the number of registers needed for 945169689Skan stack registers by two: one register push, and one register pop. 946169689Skan This usually has the effect that FP constant loads from the constant 947169689Skan pool are not moved out of the loop. 948169689Skan 949169689Skan Note that this also means that dependent invariants can not be moved. 950169689Skan However, the primary purpose of this pass is to move loop invariant 951169689Skan address arithmetic out of loops, and address arithmetic that depends 952169689Skan on floating point constants is unlikely to ever occur. */ 953169689Skan rtx set = single_set (inv->insn); 954169689Skan if (set 955169689Skan && IS_STACK_MODE (GET_MODE (SET_SRC (set))) 956169689Skan && constant_pool_constant_p (SET_SRC (set))) 957169689Skan (*regs_needed) += 2; 958169689Skan } 959169689Skan#endif 960169689Skan 961169689Skan EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi) 962169689Skan { 963169689Skan dep = VEC_index (invariant_p, invariants, depno); 964169689Skan 965169689Skan get_inv_cost (dep, &acomp_cost, &aregs_needed); 966169689Skan 967169689Skan if (aregs_needed 968169689Skan /* We need to check always_executed, since if the original value of 969169689Skan the invariant may be preserved, we may need to keep it in a 970169689Skan separate register. TODO check whether the register has an 971169689Skan use outside of the loop. */ 972169689Skan && dep->always_executed 973169689Skan && !dep->def->uses->next) 974169689Skan { 975169689Skan /* If this is a single use, after moving the dependency we will not 976169689Skan need a new register. */ 977169689Skan aregs_needed--; 978169689Skan } 979169689Skan 980169689Skan (*regs_needed) += aregs_needed; 981169689Skan (*comp_cost) += acomp_cost; 982169689Skan } 983169689Skan} 984169689Skan 985169689Skan/* Calculates gain for eliminating invariant INV. REGS_USED is the number 986169689Skan of registers used in the loop, N_INV_USES is the number of uses of 987169689Skan invariants, NEW_REGS is the number of new variables already added due to 988169689Skan the invariant motion. The number of registers needed for it is stored in 989169689Skan *REGS_NEEDED. */ 990169689Skan 991169689Skanstatic int 992169689Skangain_for_invariant (struct invariant *inv, unsigned *regs_needed, 993169689Skan unsigned new_regs, unsigned regs_used, unsigned n_inv_uses) 994169689Skan{ 995169689Skan int comp_cost, size_cost; 996169689Skan 997169689Skan get_inv_cost (inv, &comp_cost, regs_needed); 998169689Skan actual_stamp++; 999169689Skan 1000169689Skan size_cost = (global_cost_for_size (new_regs + *regs_needed, 1001169689Skan regs_used, n_inv_uses) 1002169689Skan - global_cost_for_size (new_regs, regs_used, n_inv_uses)); 1003169689Skan 1004169689Skan return comp_cost - size_cost; 1005169689Skan} 1006169689Skan 1007169689Skan/* Finds invariant with best gain for moving. Returns the gain, stores 1008169689Skan the invariant in *BEST and number of registers needed for it to 1009169689Skan *REGS_NEEDED. REGS_USED is the number of registers used in 1010169689Skan the loop, N_INV_USES is the number of uses of invariants. NEW_REGS 1011169689Skan is the number of new variables already added due to invariant motion. */ 1012169689Skan 1013169689Skanstatic int 1014169689Skanbest_gain_for_invariant (struct invariant **best, unsigned *regs_needed, 1015169689Skan unsigned new_regs, unsigned regs_used, 1016169689Skan unsigned n_inv_uses) 1017169689Skan{ 1018169689Skan struct invariant *inv; 1019169689Skan int gain = 0, again; 1020169689Skan unsigned aregs_needed, invno; 1021169689Skan 1022169689Skan for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++) 1023169689Skan { 1024169689Skan if (inv->move) 1025169689Skan continue; 1026169689Skan 1027169689Skan /* Only consider the "representatives" of equivalent invariants. */ 1028169689Skan if (inv->eqto != inv->invno) 1029169689Skan continue; 1030169689Skan 1031169689Skan again = gain_for_invariant (inv, &aregs_needed, 1032169689Skan new_regs, regs_used, n_inv_uses); 1033169689Skan if (again > gain) 1034169689Skan { 1035169689Skan gain = again; 1036169689Skan *best = inv; 1037169689Skan *regs_needed = aregs_needed; 1038169689Skan } 1039169689Skan } 1040169689Skan 1041169689Skan return gain; 1042169689Skan} 1043169689Skan 1044169689Skan/* Marks invariant INVNO and all its dependencies for moving. */ 1045169689Skan 1046169689Skanstatic void 1047169689Skanset_move_mark (unsigned invno) 1048169689Skan{ 1049169689Skan struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1050169689Skan bitmap_iterator bi; 1051169689Skan 1052169689Skan /* Find the representative of the class of the equivalent invariants. */ 1053169689Skan inv = VEC_index (invariant_p, invariants, inv->eqto); 1054169689Skan 1055169689Skan if (inv->move) 1056169689Skan return; 1057169689Skan inv->move = true; 1058169689Skan 1059169689Skan if (dump_file) 1060169689Skan fprintf (dump_file, "Decided to move invariant %d\n", invno); 1061169689Skan 1062169689Skan EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi) 1063169689Skan { 1064169689Skan set_move_mark (invno); 1065169689Skan } 1066169689Skan} 1067169689Skan 1068169689Skan/* Determines which invariants to move. */ 1069169689Skan 1070169689Skanstatic void 1071169689Skanfind_invariants_to_move (void) 1072169689Skan{ 1073169689Skan unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs; 1074169689Skan struct invariant *inv = NULL; 1075169689Skan unsigned int n_regs = DF_REG_SIZE (df); 1076169689Skan 1077169689Skan if (!VEC_length (invariant_p, invariants)) 1078169689Skan return; 1079169689Skan 1080169689Skan /* Now something slightly more involved. First estimate the number of used 1081169689Skan registers. */ 1082169689Skan n_inv_uses = 0; 1083169689Skan 1084169689Skan /* We do not really do a good job in this estimation; put some initial bound 1085169689Skan here to stand for induction variables etc. that we do not detect. */ 1086169689Skan regs_used = 2; 1087169689Skan 1088169689Skan for (i = 0; i < n_regs; i++) 1089169689Skan { 1090169689Skan if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i)) 1091169689Skan { 1092169689Skan /* This is a value that is used but not changed inside loop. */ 1093169689Skan regs_used++; 1094169689Skan } 1095169689Skan } 1096169689Skan 1097169689Skan for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1098169689Skan { 1099169689Skan if (inv->def) 1100169689Skan n_inv_uses += inv->def->n_uses; 1101169689Skan } 1102169689Skan 1103169689Skan new_regs = 0; 1104169689Skan while (best_gain_for_invariant (&inv, ®s_needed, 1105169689Skan new_regs, regs_used, n_inv_uses) > 0) 1106169689Skan { 1107169689Skan set_move_mark (inv->invno); 1108169689Skan new_regs += regs_needed; 1109169689Skan } 1110169689Skan} 1111169689Skan 1112169689Skan/* Returns true if all insns in SEQ are valid. */ 1113169689Skan 1114169689Skanstatic bool 1115169689Skanseq_insns_valid_p (rtx seq) 1116169689Skan{ 1117169689Skan rtx x; 1118169689Skan 1119169689Skan for (x = seq; x; x = NEXT_INSN (x)) 1120169689Skan if (insn_invalid_p (x)) 1121169689Skan return false; 1122169689Skan 1123169689Skan return true; 1124169689Skan} 1125169689Skan 1126169689Skan/* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false 1127169689Skan otherwise. */ 1128169689Skan 1129169689Skanstatic bool 1130169689Skanmove_invariant_reg (struct loop *loop, unsigned invno) 1131169689Skan{ 1132169689Skan struct invariant *inv = VEC_index (invariant_p, invariants, invno); 1133169689Skan struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto); 1134169689Skan unsigned i; 1135169689Skan basic_block preheader = loop_preheader_edge (loop)->src; 1136169689Skan rtx reg, set, dest, seq, op; 1137169689Skan struct use *use; 1138169689Skan bitmap_iterator bi; 1139169689Skan 1140169689Skan if (inv->reg) 1141169689Skan return true; 1142169689Skan if (!repr->move) 1143169689Skan return false; 1144169689Skan 1145169689Skan /* If this is a representative of the class of equivalent invariants, 1146169689Skan really move the invariant. Otherwise just replace its use with 1147169689Skan the register used for the representative. */ 1148169689Skan if (inv == repr) 1149169689Skan { 1150169689Skan if (inv->depends_on) 1151169689Skan { 1152169689Skan EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi) 1153169689Skan { 1154169689Skan if (!move_invariant_reg (loop, i)) 1155169689Skan goto fail; 1156169689Skan } 1157169689Skan } 1158169689Skan 1159169689Skan /* Move the set out of the loop. If the set is always executed (we could 1160169689Skan omit this condition if we know that the register is unused outside of the 1161169689Skan loop, but it does not seem worth finding out) and it has no uses that 1162169689Skan would not be dominated by it, we may just move it (TODO). Otherwise we 1163169689Skan need to create a temporary register. */ 1164169689Skan set = single_set (inv->insn); 1165169689Skan dest = SET_DEST (set); 1166169689Skan reg = gen_reg_rtx (GET_MODE (dest)); 1167169689Skan 1168169689Skan /* If the SET_DEST of the invariant insn is a pseudo, we can just move 1169169689Skan the insn out of the loop. Otherwise, we have to use gen_move_insn 1170169689Skan to let emit_move_insn produce a valid instruction stream. */ 1171169689Skan if (REG_P (dest) && !HARD_REGISTER_P (dest)) 1172169689Skan { 1173169689Skan emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1174169689Skan SET_DEST (set) = reg; 1175169689Skan reorder_insns (inv->insn, inv->insn, BB_END (preheader)); 1176169689Skan } 1177169689Skan else 1178169689Skan { 1179169689Skan start_sequence (); 1180169689Skan op = force_operand (SET_SRC (set), reg); 1181169689Skan if (!op) 1182169689Skan { 1183169689Skan end_sequence (); 1184169689Skan goto fail; 1185169689Skan } 1186169689Skan if (op != reg) 1187169689Skan emit_move_insn (reg, op); 1188169689Skan seq = get_insns (); 1189169689Skan end_sequence (); 1190169689Skan 1191169689Skan if (!seq_insns_valid_p (seq)) 1192169689Skan goto fail; 1193169689Skan emit_insn_after (seq, BB_END (preheader)); 1194169689Skan 1195169689Skan emit_insn_after (gen_move_insn (dest, reg), inv->insn); 1196169689Skan delete_insn (inv->insn); 1197169689Skan } 1198169689Skan } 1199169689Skan else 1200169689Skan { 1201169689Skan if (!move_invariant_reg (loop, repr->invno)) 1202169689Skan goto fail; 1203169689Skan reg = repr->reg; 1204169689Skan set = single_set (inv->insn); 1205169689Skan emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn); 1206169689Skan delete_insn (inv->insn); 1207169689Skan } 1208169689Skan 1209169689Skan inv->reg = reg; 1210169689Skan 1211169689Skan /* Replace the uses we know to be dominated. It saves work for copy 1212169689Skan propagation, and also it is necessary so that dependent invariants 1213169689Skan are computed right. */ 1214169689Skan if (inv->def) 1215169689Skan { 1216169689Skan for (use = inv->def->uses; use; use = use->next) 1217169689Skan *use->pos = reg; 1218169689Skan } 1219169689Skan 1220169689Skan return true; 1221169689Skan 1222169689Skanfail: 1223169689Skan /* If we failed, clear move flag, so that we do not try to move inv 1224169689Skan again. */ 1225169689Skan if (dump_file) 1226169689Skan fprintf (dump_file, "Failed to move invariant %d\n", invno); 1227169689Skan inv->move = false; 1228169689Skan inv->reg = NULL_RTX; 1229169689Skan return false; 1230169689Skan} 1231169689Skan 1232169689Skan/* Move selected invariant out of the LOOP. Newly created regs are marked 1233169689Skan in TEMPORARY_REGS. */ 1234169689Skan 1235169689Skanstatic void 1236169689Skanmove_invariants (struct loop *loop) 1237169689Skan{ 1238169689Skan struct invariant *inv; 1239169689Skan unsigned i; 1240169689Skan 1241169689Skan for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1242169689Skan move_invariant_reg (loop, i); 1243169689Skan} 1244169689Skan 1245169689Skan/* Initializes invariant motion data. */ 1246169689Skan 1247169689Skanstatic void 1248169689Skaninit_inv_motion_data (void) 1249169689Skan{ 1250169689Skan actual_stamp = 1; 1251169689Skan 1252169689Skan invariants = VEC_alloc (invariant_p, heap, 100); 1253169689Skan} 1254169689Skan 1255169689Skan/* Frees the data allocated by invariant motion. */ 1256169689Skan 1257169689Skanstatic void 1258169689Skanfree_inv_motion_data (void) 1259169689Skan{ 1260169689Skan unsigned i; 1261169689Skan struct def *def; 1262169689Skan struct invariant *inv; 1263169689Skan 1264169689Skan for (i = 0; i < DF_DEFS_SIZE (df); i++) 1265169689Skan { 1266169689Skan struct df_ref * ref = DF_DEFS_GET (df, i); 1267169689Skan if (!ref) 1268169689Skan continue; 1269169689Skan 1270169689Skan inv = DF_REF_DATA (ref); 1271169689Skan if (!inv) 1272169689Skan continue; 1273169689Skan 1274169689Skan def = inv->def; 1275169689Skan gcc_assert (def != NULL); 1276169689Skan 1277169689Skan free_use_list (def->uses); 1278169689Skan free (def); 1279169689Skan DF_REF_DATA (ref) = NULL; 1280169689Skan } 1281169689Skan 1282169689Skan for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++) 1283169689Skan { 1284169689Skan BITMAP_FREE (inv->depends_on); 1285169689Skan free (inv); 1286169689Skan } 1287169689Skan VEC_free (invariant_p, heap, invariants); 1288169689Skan} 1289169689Skan 1290169689Skan/* Move the invariants out of the LOOP. */ 1291169689Skan 1292169689Skanstatic void 1293169689Skanmove_single_loop_invariants (struct loop *loop) 1294169689Skan{ 1295169689Skan init_inv_motion_data (); 1296169689Skan 1297169689Skan find_invariants (loop); 1298169689Skan find_invariants_to_move (); 1299169689Skan move_invariants (loop); 1300169689Skan 1301169689Skan free_inv_motion_data (); 1302169689Skan} 1303169689Skan 1304169689Skan/* Releases the auxiliary data for LOOP. */ 1305169689Skan 1306169689Skanstatic void 1307169689Skanfree_loop_data (struct loop *loop) 1308169689Skan{ 1309169689Skan struct loop_data *data = LOOP_DATA (loop); 1310169689Skan 1311169689Skan free (data); 1312169689Skan loop->aux = NULL; 1313169689Skan} 1314169689Skan 1315169689Skan/* Move the invariants out of the LOOPS. */ 1316169689Skan 1317169689Skanvoid 1318169689Skanmove_loop_invariants (struct loops *loops) 1319169689Skan{ 1320169689Skan struct loop *loop; 1321169689Skan unsigned i; 1322169689Skan 1323169689Skan df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES); 1324169689Skan df_chain_add_problem (df, DF_UD_CHAIN); 1325169689Skan 1326169689Skan /* Process the loops, innermost first. */ 1327169689Skan loop = loops->tree_root; 1328169689Skan while (loop->inner) 1329169689Skan loop = loop->inner; 1330169689Skan 1331169689Skan while (loop != loops->tree_root) 1332169689Skan { 1333169689Skan move_single_loop_invariants (loop); 1334169689Skan 1335169689Skan if (loop->next) 1336169689Skan { 1337169689Skan loop = loop->next; 1338169689Skan while (loop->inner) 1339169689Skan loop = loop->inner; 1340169689Skan } 1341169689Skan else 1342169689Skan loop = loop->outer; 1343169689Skan } 1344169689Skan 1345169689Skan for (i = 1; i < loops->num; i++) 1346169689Skan if (loops->parray[i]) 1347169689Skan free_loop_data (loops->parray[i]); 1348169689Skan 1349169689Skan df_finish (df); 1350169689Skan df = NULL; 1351169689Skan 1352169689Skan#ifdef ENABLE_CHECKING 1353169689Skan verify_flow_info (); 1354169689Skan#endif 1355169689Skan} 1356