tree-ssa-loop-im.c revision 169689
1249259Sdim/* Loop invariant motion. 2249259Sdim Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3249259Sdim 4249259SdimThis file is part of GCC. 5249259Sdim 6249259SdimGCC is free software; you can redistribute it and/or modify it 7249259Sdimunder the terms of the GNU General Public License as published by the 8249259SdimFree Software Foundation; either version 2, or (at your option) any 9249259Sdimlater version. 10249259Sdim 11249259SdimGCC is distributed in the hope that it will be useful, but WITHOUT 12249259SdimANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13249259SdimFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14249259Sdimfor more details. 15249259Sdim 16249259SdimYou should have received a copy of the GNU General Public License 17249259Sdimalong with GCC; see the file COPYING. If not, write to the Free 18249259SdimSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19249259Sdim02110-1301, USA. */ 20249259Sdim 21249259Sdim#include "config.h" 22249259Sdim#include "system.h" 23249259Sdim#include "coretypes.h" 24249259Sdim#include "tm.h" 25249259Sdim#include "tree.h" 26249259Sdim#include "rtl.h" 27249259Sdim#include "tm_p.h" 28249259Sdim#include "hard-reg-set.h" 29249259Sdim#include "basic-block.h" 30249259Sdim#include "output.h" 31249259Sdim#include "diagnostic.h" 32249259Sdim#include "tree-flow.h" 33249259Sdim#include "tree-dump.h" 34249259Sdim#include "timevar.h" 35249259Sdim#include "cfgloop.h" 36249259Sdim#include "domwalk.h" 37249259Sdim#include "params.h" 38249259Sdim#include "tree-pass.h" 39249259Sdim#include "flags.h" 40249259Sdim#include "real.h" 41249259Sdim#include "hashtab.h" 42249259Sdim 43249259Sdim/* TODO: Support for predicated code motion. I.e. 44249259Sdim 45249259Sdim while (1) 46249259Sdim { 47249259Sdim if (cond) 48249259Sdim { 49249259Sdim a = inv; 50249259Sdim something; 51249259Sdim } 52249259Sdim } 53249259Sdim 54249259Sdim Where COND and INV are is invariants, but evaluating INV may trap or be 55249259Sdim invalid from some other reason if !COND. This may be transformed to 56249259Sdim 57249259Sdim if (cond) 58249259Sdim a = inv; 59249259Sdim while (1) 60249259Sdim { 61249259Sdim if (cond) 62249259Sdim something; 63249259Sdim } */ 64249259Sdim 65249259Sdim/* A type for the list of statements that have to be moved in order to be able 66249259Sdim to hoist an invariant computation. */ 67249259Sdim 68249259Sdimstruct depend 69249259Sdim{ 70249259Sdim tree stmt; 71249259Sdim struct depend *next; 72249259Sdim}; 73249259Sdim 74249259Sdim/* The auxiliary data kept for each statement. */ 75249259Sdim 76249259Sdimstruct lim_aux_data 77249259Sdim{ 78249259Sdim struct loop *max_loop; /* The outermost loop in that the statement 79249259Sdim is invariant. */ 80249259Sdim 81249259Sdim struct loop *tgt_loop; /* The loop out of that we want to move the 82249259Sdim invariant. */ 83249259Sdim 84249259Sdim struct loop *always_executed_in; 85249259Sdim /* The outermost loop for that we are sure 86249259Sdim the statement is executed if the loop 87249259Sdim is entered. */ 88249259Sdim 89249259Sdim bool sm_done; /* True iff the store motion for a memory 90249259Sdim reference in the statement has already 91249259Sdim been executed. */ 92249259Sdim 93249259Sdim unsigned cost; /* Cost of the computation performed by the 94249259Sdim statement. */ 95249259Sdim 96249259Sdim struct depend *depends; /* List of statements that must be also hoisted 97249259Sdim out of the loop when this statement is 98249259Sdim hoisted; i.e. those that define the operands 99249259Sdim of the statement and are inside of the 100249259Sdim MAX_LOOP loop. */ 101249259Sdim}; 102249259Sdim 103249259Sdim#define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \ 104249259Sdim ? NULL \ 105249259Sdim : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux)) 106249259Sdim 107249259Sdim/* Description of a memory reference location for store motion. */ 108249259Sdim 109249259Sdimstruct mem_ref_loc 110249259Sdim{ 111249259Sdim tree *ref; /* The reference itself. */ 112249259Sdim tree stmt; /* The statement in that it occurs. */ 113249259Sdim struct mem_ref_loc *next; /* Next use in the chain. */ 114249259Sdim}; 115249259Sdim 116249259Sdim/* Description of a memory reference for store motion. */ 117249259Sdim 118249259Sdimstruct mem_ref 119249259Sdim{ 120249259Sdim tree mem; /* The memory itself. */ 121249259Sdim hashval_t hash; /* Its hash value. */ 122249259Sdim bool is_stored; /* True if there is a store to the location 123249259Sdim in the loop. */ 124249259Sdim struct mem_ref_loc *locs; /* The locations where it is found. */ 125249259Sdim bitmap vops; /* Vops corresponding to this memory 126249259Sdim location. */ 127249259Sdim struct mem_ref *next; /* Next memory reference in the list. 128249259Sdim Memory references are stored in a hash 129249259Sdim table, but the hash function depends 130249259Sdim on values of pointers. Thus we cannot use 131249259Sdim htab_traverse, since then we would get 132249259Sdim miscompares during bootstrap (although the 133249259Sdim produced code would be correct). */ 134249259Sdim}; 135249259Sdim 136249259Sdim/* Minimum cost of an expensive expression. */ 137249259Sdim#define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE)) 138249259Sdim 139249259Sdim/* The outermost loop for that execution of the header guarantees that the 140249259Sdim block will be executed. */ 141249259Sdim#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux) 142249259Sdim 143249259Sdim/* Calls CBCK for each index in memory reference ADDR_P. There are two 144249259Sdim kinds situations handled; in each of these cases, the memory reference 145249259Sdim and DATA are passed to the callback: 146249259Sdim 147249259Sdim Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also 148249259Sdim pass the pointer to the index to the callback. 149249259Sdim 150249259Sdim Pointer dereference: INDIRECT_REF (addr). In this case we also pass the 151249259Sdim pointer to addr to the callback. 152249259Sdim 153249259Sdim If the callback returns false, the whole search stops and false is returned. 154249259Sdim Otherwise the function returns true after traversing through the whole 155249259Sdim reference *ADDR_P. */ 156249259Sdim 157249259Sdimbool 158249259Sdimfor_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) 159249259Sdim{ 160249259Sdim tree *nxt, *idx; 161249259Sdim 162249259Sdim for (; ; addr_p = nxt) 163249259Sdim { 164249259Sdim switch (TREE_CODE (*addr_p)) 165249259Sdim { 166249259Sdim case SSA_NAME: 167249259Sdim return cbck (*addr_p, addr_p, data); 168249259Sdim 169249259Sdim case MISALIGNED_INDIRECT_REF: 170249259Sdim case ALIGN_INDIRECT_REF: 171249259Sdim case INDIRECT_REF: 172249259Sdim nxt = &TREE_OPERAND (*addr_p, 0); 173249259Sdim return cbck (*addr_p, nxt, data); 174249259Sdim 175249259Sdim case BIT_FIELD_REF: 176249259Sdim case VIEW_CONVERT_EXPR: 177249259Sdim case REALPART_EXPR: 178249259Sdim case IMAGPART_EXPR: 179249259Sdim nxt = &TREE_OPERAND (*addr_p, 0); 180249259Sdim break; 181249259Sdim 182249259Sdim case COMPONENT_REF: 183249259Sdim /* If the component has varying offset, it behaves like index 184249259Sdim as well. */ 185249259Sdim idx = &TREE_OPERAND (*addr_p, 2); 186249259Sdim if (*idx 187249259Sdim && !cbck (*addr_p, idx, data)) 188249259Sdim return false; 189249259Sdim 190249259Sdim nxt = &TREE_OPERAND (*addr_p, 0); 191249259Sdim break; 192249259Sdim 193249259Sdim case ARRAY_REF: 194249259Sdim case ARRAY_RANGE_REF: 195249259Sdim nxt = &TREE_OPERAND (*addr_p, 0); 196249259Sdim if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) 197249259Sdim return false; 198249259Sdim break; 199249259Sdim 200249259Sdim case VAR_DECL: 201249259Sdim case PARM_DECL: 202249259Sdim case STRING_CST: 203249259Sdim case RESULT_DECL: 204249259Sdim case VECTOR_CST: 205249259Sdim case COMPLEX_CST: 206249259Sdim case INTEGER_CST: 207249259Sdim case REAL_CST: 208249259Sdim return true; 209249259Sdim 210249259Sdim case TARGET_MEM_REF: 211249259Sdim idx = &TMR_BASE (*addr_p); 212249259Sdim if (*idx 213249259Sdim && !cbck (*addr_p, idx, data)) 214249259Sdim return false; 215249259Sdim idx = &TMR_INDEX (*addr_p); 216249259Sdim if (*idx 217249259Sdim && !cbck (*addr_p, idx, data)) 218249259Sdim return false; 219249259Sdim return true; 220249259Sdim 221249259Sdim default: 222249259Sdim gcc_unreachable (); 223249259Sdim } 224249259Sdim } 225249259Sdim} 226249259Sdim 227249259Sdim/* If it is possible to hoist the statement STMT unconditionally, 228249259Sdim returns MOVE_POSSIBLE. 229249259Sdim If it is possible to hoist the statement STMT, but we must avoid making 230249259Sdim it executed if it would not be executed in the original program (e.g. 231249259Sdim because it may trap), return MOVE_PRESERVE_EXECUTION. 232249259Sdim Otherwise return MOVE_IMPOSSIBLE. */ 233249259Sdim 234249259Sdimenum move_pos 235249259Sdimmovement_possibility (tree stmt) 236249259Sdim{ 237249259Sdim tree lhs, rhs; 238249259Sdim 239249259Sdim if (flag_unswitch_loops 240249259Sdim && TREE_CODE (stmt) == COND_EXPR) 241249259Sdim { 242249259Sdim /* If we perform unswitching, force the operands of the invariant 243249259Sdim condition to be moved out of the loop. */ 244249259Sdim return MOVE_POSSIBLE; 245249259Sdim } 246249259Sdim 247249259Sdim if (TREE_CODE (stmt) != MODIFY_EXPR) 248249259Sdim return MOVE_IMPOSSIBLE; 249249259Sdim 250249259Sdim if (stmt_ends_bb_p (stmt)) 251249259Sdim return MOVE_IMPOSSIBLE; 252249259Sdim 253249259Sdim if (stmt_ann (stmt)->has_volatile_ops) 254249259Sdim return MOVE_IMPOSSIBLE; 255249259Sdim 256249259Sdim lhs = TREE_OPERAND (stmt, 0); 257249259Sdim if (TREE_CODE (lhs) == SSA_NAME 258249259Sdim && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 259249259Sdim return MOVE_IMPOSSIBLE; 260249259Sdim 261249259Sdim rhs = TREE_OPERAND (stmt, 1); 262249259Sdim 263249259Sdim if (TREE_SIDE_EFFECTS (rhs)) 264249259Sdim return MOVE_IMPOSSIBLE; 265249259Sdim 266249259Sdim if (TREE_CODE (lhs) != SSA_NAME 267249259Sdim || tree_could_trap_p (rhs)) 268249259Sdim return MOVE_PRESERVE_EXECUTION; 269249259Sdim 270249259Sdim if (get_call_expr_in (stmt)) 271249259Sdim { 272249259Sdim /* While pure or const call is guaranteed to have no side effects, we 273249259Sdim cannot move it arbitrarily. Consider code like 274249259Sdim 275249259Sdim char *s = something (); 276249259Sdim 277249259Sdim while (1) 278249259Sdim { 279249259Sdim if (s) 280249259Sdim t = strlen (s); 281249259Sdim else 282249259Sdim t = 0; 283249259Sdim } 284249259Sdim 285249259Sdim Here the strlen call cannot be moved out of the loop, even though 286249259Sdim s is invariant. In addition to possibly creating a call with 287249259Sdim invalid arguments, moving out a function call that is not executed 288249259Sdim may cause performance regressions in case the call is costly and 289249259Sdim not executed at all. */ 290249259Sdim return MOVE_PRESERVE_EXECUTION; 291249259Sdim } 292249259Sdim return MOVE_POSSIBLE; 293249259Sdim} 294249259Sdim 295249259Sdim/* Suppose that operand DEF is used inside the LOOP. Returns the outermost 296249259Sdim loop to that we could move the expression using DEF if it did not have 297249259Sdim other operands, i.e. the outermost loop enclosing LOOP in that the value 298249259Sdim of DEF is invariant. */ 299249259Sdim 300249259Sdimstatic struct loop * 301249259Sdimoutermost_invariant_loop (tree def, struct loop *loop) 302249259Sdim{ 303249259Sdim tree def_stmt; 304249259Sdim basic_block def_bb; 305249259Sdim struct loop *max_loop; 306249259Sdim 307249259Sdim if (TREE_CODE (def) != SSA_NAME) 308249259Sdim return superloop_at_depth (loop, 1); 309249259Sdim 310249259Sdim def_stmt = SSA_NAME_DEF_STMT (def); 311249259Sdim def_bb = bb_for_stmt (def_stmt); 312249259Sdim if (!def_bb) 313249259Sdim return superloop_at_depth (loop, 1); 314249259Sdim 315249259Sdim max_loop = find_common_loop (loop, def_bb->loop_father); 316249259Sdim 317249259Sdim if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop) 318249259Sdim max_loop = find_common_loop (max_loop, 319249259Sdim LIM_DATA (def_stmt)->max_loop->outer); 320249259Sdim if (max_loop == loop) 321249259Sdim return NULL; 322249259Sdim max_loop = superloop_at_depth (loop, max_loop->depth + 1); 323249259Sdim 324249259Sdim return max_loop; 325249259Sdim} 326249259Sdim 327249259Sdim/* Returns the outermost superloop of LOOP in that the expression EXPR is 328249259Sdim invariant. */ 329249259Sdim 330249259Sdimstatic struct loop * 331249259Sdimoutermost_invariant_loop_expr (tree expr, struct loop *loop) 332249259Sdim{ 333249259Sdim enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr)); 334249259Sdim unsigned i, nops; 335249259Sdim struct loop *max_loop = superloop_at_depth (loop, 1), *aloop; 336249259Sdim 337249259Sdim if (TREE_CODE (expr) == SSA_NAME 338249259Sdim || TREE_CODE (expr) == INTEGER_CST 339249259Sdim || is_gimple_min_invariant (expr)) 340249259Sdim return outermost_invariant_loop (expr, loop); 341249259Sdim 342249259Sdim if (class != tcc_unary 343249259Sdim && class != tcc_binary 344249259Sdim && class != tcc_expression 345249259Sdim && class != tcc_comparison) 346249259Sdim return NULL; 347249259Sdim 348249259Sdim nops = TREE_CODE_LENGTH (TREE_CODE (expr)); 349249259Sdim for (i = 0; i < nops; i++) 350249259Sdim { 351249259Sdim aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop); 352249259Sdim if (!aloop) 353249259Sdim return NULL; 354249259Sdim 355249259Sdim if (flow_loop_nested_p (max_loop, aloop)) 356249259Sdim max_loop = aloop; 357249259Sdim } 358249259Sdim 359249259Sdim return max_loop; 360249259Sdim} 361249259Sdim 362249259Sdim/* DATA is a structure containing information associated with a statement 363249259Sdim inside LOOP. DEF is one of the operands of this statement. 364249259Sdim 365249259Sdim Find the outermost loop enclosing LOOP in that value of DEF is invariant 366249259Sdim and record this in DATA->max_loop field. If DEF itself is defined inside 367249259Sdim this loop as well (i.e. we need to hoist it out of the loop if we want 368249259Sdim to hoist the statement represented by DATA), record the statement in that 369249259Sdim DEF is defined to the DATA->depends list. Additionally if ADD_COST is true, 370249259Sdim add the cost of the computation of DEF to the DATA->cost. 371249259Sdim 372249259Sdim If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */ 373249259Sdim 374249259Sdimstatic bool 375249259Sdimadd_dependency (tree def, struct lim_aux_data *data, struct loop *loop, 376249259Sdim bool add_cost) 377249259Sdim{ 378249259Sdim tree def_stmt = SSA_NAME_DEF_STMT (def); 379249259Sdim basic_block def_bb = bb_for_stmt (def_stmt); 380249259Sdim struct loop *max_loop; 381249259Sdim struct depend *dep; 382249259Sdim 383249259Sdim if (!def_bb) 384249259Sdim return true; 385249259Sdim 386249259Sdim max_loop = outermost_invariant_loop (def, loop); 387249259Sdim if (!max_loop) 388249259Sdim return false; 389249259Sdim 390249259Sdim if (flow_loop_nested_p (data->max_loop, max_loop)) 391249259Sdim data->max_loop = max_loop; 392249259Sdim 393249259Sdim if (!LIM_DATA (def_stmt)) 394249259Sdim return true; 395249259Sdim 396249259Sdim if (add_cost 397249259Sdim /* Only add the cost if the statement defining DEF is inside LOOP, 398249259Sdim i.e. if it is likely that by moving the invariants dependent 399249259Sdim on it, we will be able to avoid creating a new register for 400249259Sdim it (since it will be only used in these dependent invariants). */ 401249259Sdim && def_bb->loop_father == loop) 402249259Sdim data->cost += LIM_DATA (def_stmt)->cost; 403249259Sdim 404249259Sdim dep = XNEW (struct depend); 405249259Sdim dep->stmt = def_stmt; 406249259Sdim dep->next = data->depends; 407249259Sdim data->depends = dep; 408249259Sdim 409249259Sdim return true; 410249259Sdim} 411249259Sdim 412249259Sdim/* Returns an estimate for a cost of statement STMT. TODO -- the values here 413249259Sdim are just ad-hoc constants. The estimates should be based on target-specific 414249259Sdim values. */ 415249259Sdim 416249259Sdimstatic unsigned 417249259Sdimstmt_cost (tree stmt) 418249259Sdim{ 419249259Sdim tree rhs; 420249259Sdim unsigned cost = 1; 421249259Sdim 422249259Sdim /* Always try to create possibilities for unswitching. */ 423249259Sdim if (TREE_CODE (stmt) == COND_EXPR) 424249259Sdim return LIM_EXPENSIVE; 425249259Sdim 426249259Sdim rhs = TREE_OPERAND (stmt, 1); 427249259Sdim 428249259Sdim /* Hoisting memory references out should almost surely be a win. */ 429249259Sdim if (stmt_references_memory_p (stmt)) 430249259Sdim cost += 20; 431249259Sdim 432249259Sdim switch (TREE_CODE (rhs)) 433249259Sdim { 434249259Sdim case CALL_EXPR: 435249259Sdim /* We should be hoisting calls if possible. */ 436249259Sdim 437249259Sdim /* Unless the call is a builtin_constant_p; this always folds to a 438249259Sdim constant, so moving it is useless. */ 439249259Sdim rhs = get_callee_fndecl (rhs); 440249259Sdim if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL 441249259Sdim && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P) 442249259Sdim return 0; 443249259Sdim 444249259Sdim cost += 20; 445249259Sdim break; 446249259Sdim 447249259Sdim case MULT_EXPR: 448249259Sdim case TRUNC_DIV_EXPR: 449249259Sdim case CEIL_DIV_EXPR: 450249259Sdim case FLOOR_DIV_EXPR: 451249259Sdim case ROUND_DIV_EXPR: 452249259Sdim case EXACT_DIV_EXPR: 453249259Sdim case CEIL_MOD_EXPR: 454249259Sdim case FLOOR_MOD_EXPR: 455249259Sdim case ROUND_MOD_EXPR: 456249259Sdim case TRUNC_MOD_EXPR: 457249259Sdim case RDIV_EXPR: 458249259Sdim /* Division and multiplication are usually expensive. */ 459249259Sdim cost += 20; 460249259Sdim break; 461249259Sdim 462249259Sdim default: 463249259Sdim break; 464249259Sdim } 465249259Sdim 466249259Sdim return cost; 467249259Sdim} 468249259Sdim 469249259Sdim/* Determine the outermost loop to that it is possible to hoist a statement 470249259Sdim STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine 471249259Sdim the outermost loop in that the value computed by STMT is invariant. 472249259Sdim If MUST_PRESERVE_EXEC is true, additionally choose such a loop that 473249259Sdim we preserve the fact whether STMT is executed. It also fills other related 474249259Sdim information to LIM_DATA (STMT). 475249259Sdim 476249259Sdim The function returns false if STMT cannot be hoisted outside of the loop it 477249259Sdim is defined in, and true otherwise. */ 478249259Sdim 479static bool 480determine_max_movement (tree stmt, bool must_preserve_exec) 481{ 482 basic_block bb = bb_for_stmt (stmt); 483 struct loop *loop = bb->loop_father; 484 struct loop *level; 485 struct lim_aux_data *lim_data = LIM_DATA (stmt); 486 tree val; 487 ssa_op_iter iter; 488 489 if (must_preserve_exec) 490 level = ALWAYS_EXECUTED_IN (bb); 491 else 492 level = superloop_at_depth (loop, 1); 493 lim_data->max_loop = level; 494 495 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE) 496 if (!add_dependency (val, lim_data, loop, true)) 497 return false; 498 499 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 500 if (!add_dependency (val, lim_data, loop, false)) 501 return false; 502 503 lim_data->cost += stmt_cost (stmt); 504 505 return true; 506} 507 508/* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL, 509 and that one of the operands of this statement is computed by STMT. 510 Ensure that STMT (together with all the statements that define its 511 operands) is hoisted at least out of the loop LEVEL. */ 512 513static void 514set_level (tree stmt, struct loop *orig_loop, struct loop *level) 515{ 516 struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father; 517 struct depend *dep; 518 519 stmt_loop = find_common_loop (orig_loop, stmt_loop); 520 if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop) 521 stmt_loop = find_common_loop (stmt_loop, 522 LIM_DATA (stmt)->tgt_loop->outer); 523 if (flow_loop_nested_p (stmt_loop, level)) 524 return; 525 526 gcc_assert (LIM_DATA (stmt)); 527 gcc_assert (level == LIM_DATA (stmt)->max_loop 528 || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level)); 529 530 LIM_DATA (stmt)->tgt_loop = level; 531 for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next) 532 set_level (dep->stmt, orig_loop, level); 533} 534 535/* Determines an outermost loop from that we want to hoist the statement STMT. 536 For now we chose the outermost possible loop. TODO -- use profiling 537 information to set it more sanely. */ 538 539static void 540set_profitable_level (tree stmt) 541{ 542 set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop); 543} 544 545/* Returns true if STMT is not a pure call. */ 546 547static bool 548nonpure_call_p (tree stmt) 549{ 550 tree call = get_call_expr_in (stmt); 551 552 if (!call) 553 return false; 554 555 return TREE_SIDE_EFFECTS (call) != 0; 556} 557 558/* Releases the memory occupied by DATA. */ 559 560static void 561free_lim_aux_data (struct lim_aux_data *data) 562{ 563 struct depend *dep, *next; 564 565 for (dep = data->depends; dep; dep = next) 566 { 567 next = dep->next; 568 free (dep); 569 } 570 free (data); 571} 572 573/* Determine the outermost loops in that statements in basic block BB are 574 invariant, and record them to the LIM_DATA associated with the statements. 575 Callback for walk_dominator_tree. */ 576 577static void 578determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, 579 basic_block bb) 580{ 581 enum move_pos pos; 582 block_stmt_iterator bsi; 583 tree stmt, rhs; 584 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL; 585 struct loop *outermost = ALWAYS_EXECUTED_IN (bb); 586 587 if (!bb->loop_father->outer) 588 return; 589 590 if (dump_file && (dump_flags & TDF_DETAILS)) 591 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n", 592 bb->index, bb->loop_father->num, bb->loop_father->depth); 593 594 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 595 { 596 stmt = bsi_stmt (bsi); 597 598 pos = movement_possibility (stmt); 599 if (pos == MOVE_IMPOSSIBLE) 600 { 601 if (nonpure_call_p (stmt)) 602 { 603 maybe_never = true; 604 outermost = NULL; 605 } 606 continue; 607 } 608 609 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal 610 to be hoisted out of loop, saving expensive divide. */ 611 if (pos == MOVE_POSSIBLE 612 && (rhs = TREE_OPERAND (stmt, 1)) != NULL 613 && TREE_CODE (rhs) == RDIV_EXPR 614 && flag_unsafe_math_optimizations 615 && !flag_trapping_math 616 && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1), 617 loop_containing_stmt (stmt)) != NULL 618 && outermost_invariant_loop_expr (rhs, 619 loop_containing_stmt (stmt)) == NULL) 620 { 621 tree lhs, stmt1, stmt2, var, name; 622 623 lhs = TREE_OPERAND (stmt, 0); 624 625 /* stmt must be MODIFY_EXPR. */ 626 var = create_tmp_var (TREE_TYPE (rhs), "reciptmp"); 627 add_referenced_var (var); 628 629 stmt1 = build2 (MODIFY_EXPR, void_type_node, var, 630 build2 (RDIV_EXPR, TREE_TYPE (rhs), 631 build_real (TREE_TYPE (rhs), dconst1), 632 TREE_OPERAND (rhs, 1))); 633 name = make_ssa_name (var, stmt1); 634 TREE_OPERAND (stmt1, 0) = name; 635 stmt2 = build2 (MODIFY_EXPR, void_type_node, lhs, 636 build2 (MULT_EXPR, TREE_TYPE (rhs), 637 name, TREE_OPERAND (rhs, 0))); 638 639 /* Replace division stmt with reciprocal and multiply stmts. 640 The multiply stmt is not invariant, so update iterator 641 and avoid rescanning. */ 642 bsi_replace (&bsi, stmt1, true); 643 bsi_insert_after (&bsi, stmt2, BSI_NEW_STMT); 644 SSA_NAME_DEF_STMT (lhs) = stmt2; 645 646 /* Continue processing with invariant reciprocal statement. */ 647 stmt = stmt1; 648 } 649 650 stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); 651 LIM_DATA (stmt)->always_executed_in = outermost; 652 653 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION) 654 continue; 655 656 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION)) 657 { 658 LIM_DATA (stmt)->max_loop = NULL; 659 continue; 660 } 661 662 if (dump_file && (dump_flags & TDF_DETAILS)) 663 { 664 print_generic_stmt_indented (dump_file, stmt, 0, 2); 665 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n", 666 LIM_DATA (stmt)->max_loop->depth, 667 LIM_DATA (stmt)->cost); 668 } 669 670 if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE) 671 set_profitable_level (stmt); 672 } 673} 674 675/* For each statement determines the outermost loop in that it is invariant, 676 statements on whose motion it depends and the cost of the computation. 677 This information is stored to the LIM_DATA structure associated with 678 each statement. */ 679 680static void 681determine_invariantness (void) 682{ 683 struct dom_walk_data walk_data; 684 685 memset (&walk_data, 0, sizeof (struct dom_walk_data)); 686 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt; 687 688 init_walk_dominator_tree (&walk_data); 689 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 690 fini_walk_dominator_tree (&walk_data); 691} 692 693/* Commits edge insertions and updates loop structures. */ 694 695void 696loop_commit_inserts (void) 697{ 698 unsigned old_last_basic_block, i; 699 basic_block bb; 700 701 old_last_basic_block = last_basic_block; 702 bsi_commit_edge_inserts (); 703 for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++) 704 { 705 bb = BASIC_BLOCK (i); 706 add_bb_to_loop (bb, 707 find_common_loop (single_pred (bb)->loop_father, 708 single_succ (bb)->loop_father)); 709 } 710} 711 712/* Hoist the statements in basic block BB out of the loops prescribed by 713 data stored in LIM_DATA structures associated with each statement. Callback 714 for walk_dominator_tree. */ 715 716static void 717move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, 718 basic_block bb) 719{ 720 struct loop *level; 721 block_stmt_iterator bsi; 722 tree stmt; 723 unsigned cost = 0; 724 725 if (!bb->loop_father->outer) 726 return; 727 728 for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 729 { 730 stmt = bsi_stmt (bsi); 731 732 if (!LIM_DATA (stmt)) 733 { 734 bsi_next (&bsi); 735 continue; 736 } 737 738 cost = LIM_DATA (stmt)->cost; 739 level = LIM_DATA (stmt)->tgt_loop; 740 free_lim_aux_data (LIM_DATA (stmt)); 741 stmt_ann (stmt)->common.aux = NULL; 742 743 if (!level) 744 { 745 bsi_next (&bsi); 746 continue; 747 } 748 749 /* We do not really want to move conditionals out of the loop; we just 750 placed it here to force its operands to be moved if necessary. */ 751 if (TREE_CODE (stmt) == COND_EXPR) 752 continue; 753 754 if (dump_file && (dump_flags & TDF_DETAILS)) 755 { 756 fprintf (dump_file, "Moving statement\n"); 757 print_generic_stmt (dump_file, stmt, 0); 758 fprintf (dump_file, "(cost %u) out of loop %d.\n\n", 759 cost, level->num); 760 } 761 bsi_insert_on_edge (loop_preheader_edge (level), stmt); 762 bsi_remove (&bsi, false); 763 } 764} 765 766/* Hoist the statements out of the loops prescribed by data stored in 767 LIM_DATA structures associated with each statement.*/ 768 769static void 770move_computations (void) 771{ 772 struct dom_walk_data walk_data; 773 774 memset (&walk_data, 0, sizeof (struct dom_walk_data)); 775 walk_data.before_dom_children_before_stmts = move_computations_stmt; 776 777 init_walk_dominator_tree (&walk_data); 778 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 779 fini_walk_dominator_tree (&walk_data); 780 781 loop_commit_inserts (); 782 if (need_ssa_update_p ()) 783 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 784} 785 786/* Checks whether the statement defining variable *INDEX can be hoisted 787 out of the loop passed in DATA. Callback for for_each_index. */ 788 789static bool 790may_move_till (tree ref, tree *index, void *data) 791{ 792 struct loop *loop = data, *max_loop; 793 794 /* If REF is an array reference, check also that the step and the lower 795 bound is invariant in LOOP. */ 796 if (TREE_CODE (ref) == ARRAY_REF) 797 { 798 tree step = array_ref_element_size (ref); 799 tree lbound = array_ref_low_bound (ref); 800 801 max_loop = outermost_invariant_loop_expr (step, loop); 802 if (!max_loop) 803 return false; 804 805 max_loop = outermost_invariant_loop_expr (lbound, loop); 806 if (!max_loop) 807 return false; 808 } 809 810 max_loop = outermost_invariant_loop (*index, loop); 811 if (!max_loop) 812 return false; 813 814 return true; 815} 816 817/* Forces statements defining (invariant) SSA names in expression EXPR to be 818 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */ 819 820static void 821force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop) 822{ 823 enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr)); 824 unsigned i, nops; 825 826 if (TREE_CODE (expr) == SSA_NAME) 827 { 828 tree stmt = SSA_NAME_DEF_STMT (expr); 829 if (IS_EMPTY_STMT (stmt)) 830 return; 831 832 set_level (stmt, orig_loop, loop); 833 return; 834 } 835 836 if (class != tcc_unary 837 && class != tcc_binary 838 && class != tcc_expression 839 && class != tcc_comparison) 840 return; 841 842 nops = TREE_CODE_LENGTH (TREE_CODE (expr)); 843 for (i = 0; i < nops; i++) 844 force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop); 845} 846 847/* Forces statement defining invariants in REF (and *INDEX) to be moved out of 848 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for 849 for_each_index. */ 850 851struct fmt_data 852{ 853 struct loop *loop; 854 struct loop *orig_loop; 855}; 856 857static bool 858force_move_till (tree ref, tree *index, void *data) 859{ 860 tree stmt; 861 struct fmt_data *fmt_data = data; 862 863 if (TREE_CODE (ref) == ARRAY_REF) 864 { 865 tree step = array_ref_element_size (ref); 866 tree lbound = array_ref_low_bound (ref); 867 868 force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop); 869 force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop); 870 } 871 872 if (TREE_CODE (*index) != SSA_NAME) 873 return true; 874 875 stmt = SSA_NAME_DEF_STMT (*index); 876 if (IS_EMPTY_STMT (stmt)) 877 return true; 878 879 set_level (stmt, fmt_data->orig_loop, fmt_data->loop); 880 881 return true; 882} 883 884/* Records memory reference location *REF to the list MEM_REFS. The reference 885 occurs in statement STMT. */ 886 887static void 888record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref) 889{ 890 struct mem_ref_loc *aref = XNEW (struct mem_ref_loc); 891 892 aref->stmt = stmt; 893 aref->ref = ref; 894 895 aref->next = *mem_refs; 896 *mem_refs = aref; 897} 898 899/* Releases list of memory reference locations MEM_REFS. */ 900 901static void 902free_mem_ref_locs (struct mem_ref_loc *mem_refs) 903{ 904 struct mem_ref_loc *act; 905 906 while (mem_refs) 907 { 908 act = mem_refs; 909 mem_refs = mem_refs->next; 910 free (act); 911 } 912} 913 914/* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */ 915 916static void 917rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs) 918{ 919 tree var; 920 ssa_op_iter iter; 921 922 for (; mem_refs; mem_refs = mem_refs->next) 923 { 924 FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS) 925 mark_sym_for_renaming (SSA_NAME_VAR (var)); 926 927 *mem_refs->ref = tmp_var; 928 update_stmt (mem_refs->stmt); 929 } 930} 931 932/* The name and the length of the currently generated variable 933 for lsm. */ 934#define MAX_LSM_NAME_LENGTH 40 935static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1]; 936static int lsm_tmp_name_length; 937 938/* Adds S to lsm_tmp_name. */ 939 940static void 941lsm_tmp_name_add (const char *s) 942{ 943 int l = strlen (s) + lsm_tmp_name_length; 944 if (l > MAX_LSM_NAME_LENGTH) 945 return; 946 947 strcpy (lsm_tmp_name + lsm_tmp_name_length, s); 948 lsm_tmp_name_length = l; 949} 950 951/* Stores the name for temporary variable that replaces REF to 952 lsm_tmp_name. */ 953 954static void 955gen_lsm_tmp_name (tree ref) 956{ 957 const char *name; 958 959 switch (TREE_CODE (ref)) 960 { 961 case MISALIGNED_INDIRECT_REF: 962 case ALIGN_INDIRECT_REF: 963 case INDIRECT_REF: 964 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 965 lsm_tmp_name_add ("_"); 966 break; 967 968 case BIT_FIELD_REF: 969 case VIEW_CONVERT_EXPR: 970 case ARRAY_RANGE_REF: 971 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 972 break; 973 974 case REALPART_EXPR: 975 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 976 lsm_tmp_name_add ("_RE"); 977 break; 978 979 case IMAGPART_EXPR: 980 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 981 lsm_tmp_name_add ("_IM"); 982 break; 983 984 case COMPONENT_REF: 985 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 986 lsm_tmp_name_add ("_"); 987 name = get_name (TREE_OPERAND (ref, 1)); 988 if (!name) 989 name = "F"; 990 lsm_tmp_name_add ("_"); 991 lsm_tmp_name_add (name); 992 993 case ARRAY_REF: 994 gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 995 lsm_tmp_name_add ("_I"); 996 break; 997 998 case SSA_NAME: 999 ref = SSA_NAME_VAR (ref); 1000 /* Fallthru. */ 1001 1002 case VAR_DECL: 1003 case PARM_DECL: 1004 name = get_name (ref); 1005 if (!name) 1006 name = "D"; 1007 lsm_tmp_name_add (name); 1008 break; 1009 1010 case STRING_CST: 1011 lsm_tmp_name_add ("S"); 1012 break; 1013 1014 case RESULT_DECL: 1015 lsm_tmp_name_add ("R"); 1016 break; 1017 1018 default: 1019 gcc_unreachable (); 1020 } 1021} 1022 1023/* Determines name for temporary variable that replaces REF. 1024 The name is accumulated into the lsm_tmp_name variable. */ 1025 1026static char * 1027get_lsm_tmp_name (tree ref) 1028{ 1029 lsm_tmp_name_length = 0; 1030 gen_lsm_tmp_name (ref); 1031 lsm_tmp_name_add ("_lsm"); 1032 return lsm_tmp_name; 1033} 1034 1035/* Records request for store motion of memory reference REF from LOOP. 1036 MEM_REFS is the list of occurrences of the reference REF inside LOOP; 1037 these references are rewritten by a new temporary variable. 1038 Exits from the LOOP are stored in EXITS, there are N_EXITS of them. 1039 The initialization of the temporary variable is put to the preheader 1040 of the loop, and assignments to the reference from the temporary variable 1041 are emitted to exits. */ 1042 1043static void 1044schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref, 1045 struct mem_ref_loc *mem_refs) 1046{ 1047 struct mem_ref_loc *aref; 1048 tree tmp_var; 1049 unsigned i; 1050 tree load, store; 1051 struct fmt_data fmt_data; 1052 1053 if (dump_file && (dump_flags & TDF_DETAILS)) 1054 { 1055 fprintf (dump_file, "Executing store motion of "); 1056 print_generic_expr (dump_file, ref, 0); 1057 fprintf (dump_file, " from loop %d\n", loop->num); 1058 } 1059 1060 tmp_var = make_rename_temp (TREE_TYPE (ref), 1061 get_lsm_tmp_name (ref)); 1062 1063 fmt_data.loop = loop; 1064 fmt_data.orig_loop = loop; 1065 for_each_index (&ref, force_move_till, &fmt_data); 1066 1067 rewrite_mem_refs (tmp_var, mem_refs); 1068 for (aref = mem_refs; aref; aref = aref->next) 1069 if (LIM_DATA (aref->stmt)) 1070 LIM_DATA (aref->stmt)->sm_done = true; 1071 1072 /* Emit the load & stores. */ 1073 load = build2 (MODIFY_EXPR, void_type_node, tmp_var, ref); 1074 get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); 1075 LIM_DATA (load)->max_loop = loop; 1076 LIM_DATA (load)->tgt_loop = loop; 1077 1078 /* Put this into the latch, so that we are sure it will be processed after 1079 all dependencies. */ 1080 bsi_insert_on_edge (loop_latch_edge (loop), load); 1081 1082 for (i = 0; i < n_exits; i++) 1083 { 1084 store = build2 (MODIFY_EXPR, void_type_node, 1085 unshare_expr (ref), tmp_var); 1086 bsi_insert_on_edge (exits[i], store); 1087 } 1088} 1089 1090/* Check whether memory reference REF can be hoisted out of the LOOP. If this 1091 is true, prepare the statements that load the value of the memory reference 1092 to a temporary variable in the loop preheader, store it back on the loop 1093 exits, and replace all the references inside LOOP by this temporary variable. 1094 LOOP has N_EXITS stored in EXITS. CLOBBERED_VOPS is the bitmap of virtual 1095 operands that are clobbered by a call or accessed through multiple references 1096 in loop. */ 1097 1098static void 1099determine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits, 1100 bitmap clobbered_vops, struct mem_ref *ref) 1101{ 1102 struct mem_ref_loc *aref; 1103 struct loop *must_exec; 1104 1105 /* In case the memory is not stored to, there is nothing for SM to do. */ 1106 if (!ref->is_stored) 1107 return; 1108 1109 /* If the reference is aliased with any different ref, or killed by call 1110 in function, then fail. */ 1111 if (bitmap_intersect_p (ref->vops, clobbered_vops)) 1112 return; 1113 1114 if (tree_could_trap_p (ref->mem)) 1115 { 1116 /* If the memory access is unsafe (i.e. it might trap), ensure that some 1117 of the statements in that it occurs is always executed when the loop 1118 is entered. This way we know that by moving the load from the 1119 reference out of the loop we will not cause the error that would not 1120 occur otherwise. 1121 1122 TODO -- in fact we would like to check for anticipability of the 1123 reference, i.e. that on each path from loop entry to loop exit at 1124 least one of the statements containing the memory reference is 1125 executed. */ 1126 1127 for (aref = ref->locs; aref; aref = aref->next) 1128 { 1129 if (!LIM_DATA (aref->stmt)) 1130 continue; 1131 1132 must_exec = LIM_DATA (aref->stmt)->always_executed_in; 1133 if (!must_exec) 1134 continue; 1135 1136 if (must_exec == loop 1137 || flow_loop_nested_p (must_exec, loop)) 1138 break; 1139 } 1140 1141 if (!aref) 1142 return; 1143 } 1144 1145 schedule_sm (loop, exits, n_exits, ref->mem, ref->locs); 1146} 1147 1148/* Hoists memory references MEM_REFS out of LOOP. CLOBBERED_VOPS is the list 1149 of vops clobbered by call in loop or accessed by multiple memory references. 1150 EXITS is the list of N_EXITS exit edges of the LOOP. */ 1151 1152static void 1153hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs, 1154 bitmap clobbered_vops, edge *exits, unsigned n_exits) 1155{ 1156 struct mem_ref *ref; 1157 1158 for (ref = mem_refs; ref; ref = ref->next) 1159 determine_lsm_ref (loop, exits, n_exits, clobbered_vops, ref); 1160} 1161 1162/* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable 1163 for a store motion optimization (i.e. whether we can insert statement 1164 on its exits). */ 1165 1166static bool 1167loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits, 1168 unsigned n_exits) 1169{ 1170 unsigned i; 1171 1172 for (i = 0; i < n_exits; i++) 1173 if (exits[i]->flags & EDGE_ABNORMAL) 1174 return false; 1175 1176 return true; 1177} 1178 1179/* A hash function for struct mem_ref object OBJ. */ 1180 1181static hashval_t 1182memref_hash (const void *obj) 1183{ 1184 const struct mem_ref *mem = obj; 1185 1186 return mem->hash; 1187} 1188 1189/* An equality function for struct mem_ref object OBJ1 with 1190 memory reference OBJ2. */ 1191 1192static int 1193memref_eq (const void *obj1, const void *obj2) 1194{ 1195 const struct mem_ref *mem1 = obj1; 1196 1197 return operand_equal_p (mem1->mem, (tree) obj2, 0); 1198} 1199 1200/* Gathers memory references in statement STMT in LOOP, storing the 1201 information about them in MEM_REFS hash table. Note vops accessed through 1202 unrecognized statements in CLOBBERED_VOPS. The newly created references 1203 are also stored to MEM_REF_LIST. */ 1204 1205static void 1206gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs, 1207 bitmap clobbered_vops, tree stmt, 1208 struct mem_ref **mem_ref_list) 1209{ 1210 tree *lhs, *rhs, *mem = NULL; 1211 hashval_t hash; 1212 PTR *slot; 1213 struct mem_ref *ref = NULL; 1214 ssa_op_iter oi; 1215 tree vname; 1216 bool is_stored; 1217 1218 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 1219 return; 1220 1221 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */ 1222 if (TREE_CODE (stmt) != MODIFY_EXPR) 1223 goto fail; 1224 1225 lhs = &TREE_OPERAND (stmt, 0); 1226 rhs = &TREE_OPERAND (stmt, 1); 1227 1228 if (TREE_CODE (*lhs) == SSA_NAME) 1229 { 1230 if (!is_gimple_addressable (*rhs)) 1231 goto fail; 1232 1233 mem = rhs; 1234 is_stored = false; 1235 } 1236 else if (TREE_CODE (*rhs) == SSA_NAME 1237 || is_gimple_min_invariant (*rhs)) 1238 { 1239 mem = lhs; 1240 is_stored = true; 1241 } 1242 else 1243 goto fail; 1244 1245 /* If we cannot create an SSA name for the result, give up. */ 1246 if (!is_gimple_reg_type (TREE_TYPE (*mem)) 1247 || TREE_THIS_VOLATILE (*mem)) 1248 goto fail; 1249 1250 /* If we cannot move the reference out of the loop, fail. */ 1251 if (!for_each_index (mem, may_move_till, loop)) 1252 goto fail; 1253 1254 hash = iterative_hash_expr (*mem, 0); 1255 slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT); 1256 1257 if (*slot) 1258 ref = *slot; 1259 else 1260 { 1261 ref = XNEW (struct mem_ref); 1262 ref->mem = *mem; 1263 ref->hash = hash; 1264 ref->locs = NULL; 1265 ref->is_stored = false; 1266 ref->vops = BITMAP_ALLOC (NULL); 1267 ref->next = *mem_ref_list; 1268 *mem_ref_list = ref; 1269 *slot = ref; 1270 } 1271 ref->is_stored |= is_stored; 1272 1273 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, 1274 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1275 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname))); 1276 record_mem_ref_loc (&ref->locs, stmt, mem); 1277 return; 1278 1279fail: 1280 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, 1281 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1282 bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname))); 1283} 1284 1285/* Gathers memory references in LOOP. Notes vops accessed through unrecognized 1286 statements in CLOBBERED_VOPS. The list of the references found by 1287 the function is returned. */ 1288 1289static struct mem_ref * 1290gather_mem_refs (struct loop *loop, bitmap clobbered_vops) 1291{ 1292 basic_block *body = get_loop_body (loop); 1293 block_stmt_iterator bsi; 1294 unsigned i; 1295 struct mem_ref *mem_ref_list = NULL; 1296 htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL); 1297 1298 for (i = 0; i < loop->num_nodes; i++) 1299 { 1300 for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 1301 gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi), 1302 &mem_ref_list); 1303 } 1304 1305 free (body); 1306 1307 htab_delete (mem_refs); 1308 return mem_ref_list; 1309} 1310 1311/* Finds the vops accessed by more than one of the memory references described 1312 in MEM_REFS and marks them in CLOBBERED_VOPS. */ 1313 1314static void 1315find_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops) 1316{ 1317 bitmap_head tmp, all_vops; 1318 struct mem_ref *ref; 1319 1320 bitmap_initialize (&tmp, &bitmap_default_obstack); 1321 bitmap_initialize (&all_vops, &bitmap_default_obstack); 1322 1323 for (ref = mem_refs; ref; ref = ref->next) 1324 { 1325 /* The vops that are already in all_vops are accessed by more than 1326 one memory reference. */ 1327 bitmap_and (&tmp, &all_vops, ref->vops); 1328 bitmap_ior_into (clobbered_vops, &tmp); 1329 bitmap_clear (&tmp); 1330 1331 bitmap_ior_into (&all_vops, ref->vops); 1332 } 1333 1334 bitmap_clear (&all_vops); 1335} 1336 1337/* Releases the memory occupied by REF. */ 1338 1339static void 1340free_mem_ref (struct mem_ref *ref) 1341{ 1342 free_mem_ref_locs (ref->locs); 1343 BITMAP_FREE (ref->vops); 1344 free (ref); 1345} 1346 1347/* Releases the memory occupied by REFS. */ 1348 1349static void 1350free_mem_refs (struct mem_ref *refs) 1351{ 1352 struct mem_ref *ref, *next; 1353 1354 for (ref = refs; ref; ref = next) 1355 { 1356 next = ref->next; 1357 free_mem_ref (ref); 1358 } 1359} 1360 1361/* Try to perform store motion for all memory references modified inside 1362 LOOP. */ 1363 1364static void 1365determine_lsm_loop (struct loop *loop) 1366{ 1367 unsigned n_exits; 1368 edge *exits = get_loop_exit_edges (loop, &n_exits); 1369 bitmap clobbered_vops; 1370 struct mem_ref *mem_refs; 1371 1372 if (!loop_suitable_for_sm (loop, exits, n_exits)) 1373 { 1374 free (exits); 1375 return; 1376 } 1377 1378 /* Find the memory references in LOOP. */ 1379 clobbered_vops = BITMAP_ALLOC (NULL); 1380 mem_refs = gather_mem_refs (loop, clobbered_vops); 1381 1382 /* Find the vops that are used for more than one reference. */ 1383 find_more_ref_vops (mem_refs, clobbered_vops); 1384 1385 /* Hoist all suitable memory references. */ 1386 hoist_memory_references (loop, mem_refs, clobbered_vops, exits, n_exits); 1387 1388 free_mem_refs (mem_refs); 1389 free (exits); 1390 BITMAP_FREE (clobbered_vops); 1391} 1392 1393/* Try to perform store motion for all memory references modified inside 1394 any of LOOPS. */ 1395 1396static void 1397determine_lsm (struct loops *loops) 1398{ 1399 struct loop *loop; 1400 1401 if (!loops->tree_root->inner) 1402 return; 1403 1404 /* Pass the loops from the outermost and perform the store motion as 1405 suitable. */ 1406 1407 loop = loops->tree_root->inner; 1408 while (1) 1409 { 1410 determine_lsm_loop (loop); 1411 1412 if (loop->inner) 1413 { 1414 loop = loop->inner; 1415 continue; 1416 } 1417 while (!loop->next) 1418 { 1419 loop = loop->outer; 1420 if (loop == loops->tree_root) 1421 { 1422 loop_commit_inserts (); 1423 return; 1424 } 1425 } 1426 loop = loop->next; 1427 } 1428} 1429 1430/* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e. 1431 for each such basic block bb records the outermost loop for that execution 1432 of its header implies execution of bb. CONTAINS_CALL is the bitmap of 1433 blocks that contain a nonpure call. */ 1434 1435static void 1436fill_always_executed_in (struct loop *loop, sbitmap contains_call) 1437{ 1438 basic_block bb = NULL, *bbs, last = NULL; 1439 unsigned i; 1440 edge e; 1441 struct loop *inn_loop = loop; 1442 1443 if (!loop->header->aux) 1444 { 1445 bbs = get_loop_body_in_dom_order (loop); 1446 1447 for (i = 0; i < loop->num_nodes; i++) 1448 { 1449 edge_iterator ei; 1450 bb = bbs[i]; 1451 1452 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1453 last = bb; 1454 1455 if (TEST_BIT (contains_call, bb->index)) 1456 break; 1457 1458 FOR_EACH_EDGE (e, ei, bb->succs) 1459 if (!flow_bb_inside_loop_p (loop, e->dest)) 1460 break; 1461 if (e) 1462 break; 1463 1464 /* A loop might be infinite (TODO use simple loop analysis 1465 to disprove this if possible). */ 1466 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1467 break; 1468 1469 if (!flow_bb_inside_loop_p (inn_loop, bb)) 1470 break; 1471 1472 if (bb->loop_father->header == bb) 1473 { 1474 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1475 break; 1476 1477 /* In a loop that is always entered we may proceed anyway. 1478 But record that we entered it and stop once we leave it. */ 1479 inn_loop = bb->loop_father; 1480 } 1481 } 1482 1483 while (1) 1484 { 1485 last->aux = loop; 1486 if (last == loop->header) 1487 break; 1488 last = get_immediate_dominator (CDI_DOMINATORS, last); 1489 } 1490 1491 free (bbs); 1492 } 1493 1494 for (loop = loop->inner; loop; loop = loop->next) 1495 fill_always_executed_in (loop, contains_call); 1496} 1497 1498/* Compute the global information needed by the loop invariant motion pass. 1499 LOOPS is the loop tree. */ 1500 1501static void 1502tree_ssa_lim_initialize (struct loops *loops) 1503{ 1504 sbitmap contains_call = sbitmap_alloc (last_basic_block); 1505 block_stmt_iterator bsi; 1506 struct loop *loop; 1507 basic_block bb; 1508 1509 sbitmap_zero (contains_call); 1510 FOR_EACH_BB (bb) 1511 { 1512 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1513 { 1514 if (nonpure_call_p (bsi_stmt (bsi))) 1515 break; 1516 } 1517 1518 if (!bsi_end_p (bsi)) 1519 SET_BIT (contains_call, bb->index); 1520 } 1521 1522 for (loop = loops->tree_root->inner; loop; loop = loop->next) 1523 fill_always_executed_in (loop, contains_call); 1524 1525 sbitmap_free (contains_call); 1526} 1527 1528/* Cleans up after the invariant motion pass. */ 1529 1530static void 1531tree_ssa_lim_finalize (void) 1532{ 1533 basic_block bb; 1534 1535 FOR_EACH_BB (bb) 1536 { 1537 bb->aux = NULL; 1538 } 1539} 1540 1541/* Moves invariants from LOOPS. Only "expensive" invariants are moved out -- 1542 i.e. those that are likely to be win regardless of the register pressure. */ 1543 1544void 1545tree_ssa_lim (struct loops *loops) 1546{ 1547 tree_ssa_lim_initialize (loops); 1548 1549 /* For each statement determine the outermost loop in that it is 1550 invariant and cost for computing the invariant. */ 1551 determine_invariantness (); 1552 1553 /* For each memory reference determine whether it is possible to hoist it 1554 out of the loop. Force the necessary invariants to be moved out of the 1555 loops as well. */ 1556 determine_lsm (loops); 1557 1558 /* Move the expressions that are expensive enough. */ 1559 move_computations (); 1560 1561 tree_ssa_lim_finalize (); 1562} 1563