1169689Skan/* Loop invariant motion. 2169689Skan Copyright (C) 2003, 2004, 2005 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#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "rtl.h" 27169689Skan#include "tm_p.h" 28169689Skan#include "hard-reg-set.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "output.h" 31169689Skan#include "diagnostic.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-dump.h" 34169689Skan#include "timevar.h" 35169689Skan#include "cfgloop.h" 36169689Skan#include "domwalk.h" 37169689Skan#include "params.h" 38169689Skan#include "tree-pass.h" 39169689Skan#include "flags.h" 40169689Skan#include "real.h" 41169689Skan#include "hashtab.h" 42169689Skan 43169689Skan/* TODO: Support for predicated code motion. I.e. 44169689Skan 45169689Skan while (1) 46169689Skan { 47169689Skan if (cond) 48169689Skan { 49169689Skan a = inv; 50169689Skan something; 51169689Skan } 52169689Skan } 53169689Skan 54169689Skan Where COND and INV are is invariants, but evaluating INV may trap or be 55169689Skan invalid from some other reason if !COND. This may be transformed to 56169689Skan 57169689Skan if (cond) 58169689Skan a = inv; 59169689Skan while (1) 60169689Skan { 61169689Skan if (cond) 62169689Skan something; 63169689Skan } */ 64169689Skan 65169689Skan/* A type for the list of statements that have to be moved in order to be able 66169689Skan to hoist an invariant computation. */ 67169689Skan 68169689Skanstruct depend 69169689Skan{ 70169689Skan tree stmt; 71169689Skan struct depend *next; 72169689Skan}; 73169689Skan 74169689Skan/* The auxiliary data kept for each statement. */ 75169689Skan 76169689Skanstruct lim_aux_data 77169689Skan{ 78169689Skan struct loop *max_loop; /* The outermost loop in that the statement 79169689Skan is invariant. */ 80169689Skan 81169689Skan struct loop *tgt_loop; /* The loop out of that we want to move the 82169689Skan invariant. */ 83169689Skan 84169689Skan struct loop *always_executed_in; 85169689Skan /* The outermost loop for that we are sure 86169689Skan the statement is executed if the loop 87169689Skan is entered. */ 88169689Skan 89169689Skan bool sm_done; /* True iff the store motion for a memory 90169689Skan reference in the statement has already 91169689Skan been executed. */ 92169689Skan 93169689Skan unsigned cost; /* Cost of the computation performed by the 94169689Skan statement. */ 95169689Skan 96169689Skan struct depend *depends; /* List of statements that must be also hoisted 97169689Skan out of the loop when this statement is 98169689Skan hoisted; i.e. those that define the operands 99169689Skan of the statement and are inside of the 100169689Skan MAX_LOOP loop. */ 101169689Skan}; 102169689Skan 103169689Skan#define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \ 104169689Skan ? NULL \ 105169689Skan : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux)) 106169689Skan 107169689Skan/* Description of a memory reference location for store motion. */ 108169689Skan 109169689Skanstruct mem_ref_loc 110169689Skan{ 111169689Skan tree *ref; /* The reference itself. */ 112169689Skan tree stmt; /* The statement in that it occurs. */ 113169689Skan struct mem_ref_loc *next; /* Next use in the chain. */ 114169689Skan}; 115169689Skan 116169689Skan/* Description of a memory reference for store motion. */ 117169689Skan 118169689Skanstruct mem_ref 119169689Skan{ 120169689Skan tree mem; /* The memory itself. */ 121169689Skan hashval_t hash; /* Its hash value. */ 122169689Skan bool is_stored; /* True if there is a store to the location 123169689Skan in the loop. */ 124169689Skan struct mem_ref_loc *locs; /* The locations where it is found. */ 125169689Skan bitmap vops; /* Vops corresponding to this memory 126169689Skan location. */ 127169689Skan struct mem_ref *next; /* Next memory reference in the list. 128169689Skan Memory references are stored in a hash 129169689Skan table, but the hash function depends 130169689Skan on values of pointers. Thus we cannot use 131169689Skan htab_traverse, since then we would get 132169689Skan miscompares during bootstrap (although the 133169689Skan produced code would be correct). */ 134169689Skan}; 135169689Skan 136169689Skan/* Minimum cost of an expensive expression. */ 137169689Skan#define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE)) 138169689Skan 139169689Skan/* The outermost loop for that execution of the header guarantees that the 140169689Skan block will be executed. */ 141169689Skan#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux) 142169689Skan 143169689Skan/* Calls CBCK for each index in memory reference ADDR_P. There are two 144169689Skan kinds situations handled; in each of these cases, the memory reference 145169689Skan and DATA are passed to the callback: 146169689Skan 147169689Skan Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also 148169689Skan pass the pointer to the index to the callback. 149169689Skan 150169689Skan Pointer dereference: INDIRECT_REF (addr). In this case we also pass the 151169689Skan pointer to addr to the callback. 152169689Skan 153169689Skan If the callback returns false, the whole search stops and false is returned. 154169689Skan Otherwise the function returns true after traversing through the whole 155169689Skan reference *ADDR_P. */ 156169689Skan 157169689Skanbool 158169689Skanfor_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) 159169689Skan{ 160169689Skan tree *nxt, *idx; 161169689Skan 162169689Skan for (; ; addr_p = nxt) 163169689Skan { 164169689Skan switch (TREE_CODE (*addr_p)) 165169689Skan { 166169689Skan case SSA_NAME: 167169689Skan return cbck (*addr_p, addr_p, data); 168169689Skan 169169689Skan case MISALIGNED_INDIRECT_REF: 170169689Skan case ALIGN_INDIRECT_REF: 171169689Skan case INDIRECT_REF: 172169689Skan nxt = &TREE_OPERAND (*addr_p, 0); 173169689Skan return cbck (*addr_p, nxt, data); 174169689Skan 175169689Skan case BIT_FIELD_REF: 176169689Skan case VIEW_CONVERT_EXPR: 177169689Skan case REALPART_EXPR: 178169689Skan case IMAGPART_EXPR: 179169689Skan nxt = &TREE_OPERAND (*addr_p, 0); 180169689Skan break; 181169689Skan 182169689Skan case COMPONENT_REF: 183169689Skan /* If the component has varying offset, it behaves like index 184169689Skan as well. */ 185169689Skan idx = &TREE_OPERAND (*addr_p, 2); 186169689Skan if (*idx 187169689Skan && !cbck (*addr_p, idx, data)) 188169689Skan return false; 189169689Skan 190169689Skan nxt = &TREE_OPERAND (*addr_p, 0); 191169689Skan break; 192169689Skan 193169689Skan case ARRAY_REF: 194169689Skan case ARRAY_RANGE_REF: 195169689Skan nxt = &TREE_OPERAND (*addr_p, 0); 196169689Skan if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) 197169689Skan return false; 198169689Skan break; 199169689Skan 200169689Skan case VAR_DECL: 201169689Skan case PARM_DECL: 202169689Skan case STRING_CST: 203169689Skan case RESULT_DECL: 204169689Skan case VECTOR_CST: 205169689Skan case COMPLEX_CST: 206169689Skan case INTEGER_CST: 207169689Skan case REAL_CST: 208169689Skan return true; 209169689Skan 210169689Skan case TARGET_MEM_REF: 211169689Skan idx = &TMR_BASE (*addr_p); 212169689Skan if (*idx 213169689Skan && !cbck (*addr_p, idx, data)) 214169689Skan return false; 215169689Skan idx = &TMR_INDEX (*addr_p); 216169689Skan if (*idx 217169689Skan && !cbck (*addr_p, idx, data)) 218169689Skan return false; 219169689Skan return true; 220169689Skan 221169689Skan default: 222169689Skan gcc_unreachable (); 223169689Skan } 224169689Skan } 225169689Skan} 226169689Skan 227169689Skan/* If it is possible to hoist the statement STMT unconditionally, 228169689Skan returns MOVE_POSSIBLE. 229169689Skan If it is possible to hoist the statement STMT, but we must avoid making 230169689Skan it executed if it would not be executed in the original program (e.g. 231169689Skan because it may trap), return MOVE_PRESERVE_EXECUTION. 232169689Skan Otherwise return MOVE_IMPOSSIBLE. */ 233169689Skan 234169689Skanenum move_pos 235169689Skanmovement_possibility (tree stmt) 236169689Skan{ 237169689Skan tree lhs, rhs; 238169689Skan 239169689Skan if (flag_unswitch_loops 240169689Skan && TREE_CODE (stmt) == COND_EXPR) 241169689Skan { 242169689Skan /* If we perform unswitching, force the operands of the invariant 243169689Skan condition to be moved out of the loop. */ 244169689Skan return MOVE_POSSIBLE; 245169689Skan } 246169689Skan 247169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 248169689Skan return MOVE_IMPOSSIBLE; 249169689Skan 250169689Skan if (stmt_ends_bb_p (stmt)) 251169689Skan return MOVE_IMPOSSIBLE; 252169689Skan 253169689Skan if (stmt_ann (stmt)->has_volatile_ops) 254169689Skan return MOVE_IMPOSSIBLE; 255169689Skan 256169689Skan lhs = TREE_OPERAND (stmt, 0); 257169689Skan if (TREE_CODE (lhs) == SSA_NAME 258169689Skan && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 259169689Skan return MOVE_IMPOSSIBLE; 260169689Skan 261169689Skan rhs = TREE_OPERAND (stmt, 1); 262169689Skan 263169689Skan if (TREE_SIDE_EFFECTS (rhs)) 264169689Skan return MOVE_IMPOSSIBLE; 265169689Skan 266169689Skan if (TREE_CODE (lhs) != SSA_NAME 267169689Skan || tree_could_trap_p (rhs)) 268169689Skan return MOVE_PRESERVE_EXECUTION; 269169689Skan 270169689Skan if (get_call_expr_in (stmt)) 271169689Skan { 272169689Skan /* While pure or const call is guaranteed to have no side effects, we 273169689Skan cannot move it arbitrarily. Consider code like 274169689Skan 275169689Skan char *s = something (); 276169689Skan 277169689Skan while (1) 278169689Skan { 279169689Skan if (s) 280169689Skan t = strlen (s); 281169689Skan else 282169689Skan t = 0; 283169689Skan } 284169689Skan 285169689Skan Here the strlen call cannot be moved out of the loop, even though 286169689Skan s is invariant. In addition to possibly creating a call with 287169689Skan invalid arguments, moving out a function call that is not executed 288169689Skan may cause performance regressions in case the call is costly and 289169689Skan not executed at all. */ 290169689Skan return MOVE_PRESERVE_EXECUTION; 291169689Skan } 292169689Skan return MOVE_POSSIBLE; 293169689Skan} 294169689Skan 295169689Skan/* Suppose that operand DEF is used inside the LOOP. Returns the outermost 296169689Skan loop to that we could move the expression using DEF if it did not have 297169689Skan other operands, i.e. the outermost loop enclosing LOOP in that the value 298169689Skan of DEF is invariant. */ 299169689Skan 300169689Skanstatic struct loop * 301169689Skanoutermost_invariant_loop (tree def, struct loop *loop) 302169689Skan{ 303169689Skan tree def_stmt; 304169689Skan basic_block def_bb; 305169689Skan struct loop *max_loop; 306169689Skan 307169689Skan if (TREE_CODE (def) != SSA_NAME) 308169689Skan return superloop_at_depth (loop, 1); 309169689Skan 310169689Skan def_stmt = SSA_NAME_DEF_STMT (def); 311169689Skan def_bb = bb_for_stmt (def_stmt); 312169689Skan if (!def_bb) 313169689Skan return superloop_at_depth (loop, 1); 314169689Skan 315169689Skan max_loop = find_common_loop (loop, def_bb->loop_father); 316169689Skan 317169689Skan if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop) 318169689Skan max_loop = find_common_loop (max_loop, 319169689Skan LIM_DATA (def_stmt)->max_loop->outer); 320169689Skan if (max_loop == loop) 321169689Skan return NULL; 322169689Skan max_loop = superloop_at_depth (loop, max_loop->depth + 1); 323169689Skan 324169689Skan return max_loop; 325169689Skan} 326169689Skan 327169689Skan/* Returns the outermost superloop of LOOP in that the expression EXPR is 328169689Skan invariant. */ 329169689Skan 330169689Skanstatic struct loop * 331169689Skanoutermost_invariant_loop_expr (tree expr, struct loop *loop) 332169689Skan{ 333169689Skan enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr)); 334169689Skan unsigned i, nops; 335169689Skan struct loop *max_loop = superloop_at_depth (loop, 1), *aloop; 336169689Skan 337169689Skan if (TREE_CODE (expr) == SSA_NAME 338169689Skan || TREE_CODE (expr) == INTEGER_CST 339169689Skan || is_gimple_min_invariant (expr)) 340169689Skan return outermost_invariant_loop (expr, loop); 341169689Skan 342169689Skan if (class != tcc_unary 343169689Skan && class != tcc_binary 344169689Skan && class != tcc_expression 345169689Skan && class != tcc_comparison) 346169689Skan return NULL; 347169689Skan 348169689Skan nops = TREE_CODE_LENGTH (TREE_CODE (expr)); 349169689Skan for (i = 0; i < nops; i++) 350169689Skan { 351169689Skan aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop); 352169689Skan if (!aloop) 353169689Skan return NULL; 354169689Skan 355169689Skan if (flow_loop_nested_p (max_loop, aloop)) 356169689Skan max_loop = aloop; 357169689Skan } 358169689Skan 359169689Skan return max_loop; 360169689Skan} 361169689Skan 362169689Skan/* DATA is a structure containing information associated with a statement 363169689Skan inside LOOP. DEF is one of the operands of this statement. 364169689Skan 365169689Skan Find the outermost loop enclosing LOOP in that value of DEF is invariant 366169689Skan and record this in DATA->max_loop field. If DEF itself is defined inside 367169689Skan this loop as well (i.e. we need to hoist it out of the loop if we want 368169689Skan to hoist the statement represented by DATA), record the statement in that 369169689Skan DEF is defined to the DATA->depends list. Additionally if ADD_COST is true, 370169689Skan add the cost of the computation of DEF to the DATA->cost. 371169689Skan 372169689Skan If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */ 373169689Skan 374169689Skanstatic bool 375169689Skanadd_dependency (tree def, struct lim_aux_data *data, struct loop *loop, 376169689Skan bool add_cost) 377169689Skan{ 378169689Skan tree def_stmt = SSA_NAME_DEF_STMT (def); 379169689Skan basic_block def_bb = bb_for_stmt (def_stmt); 380169689Skan struct loop *max_loop; 381169689Skan struct depend *dep; 382169689Skan 383169689Skan if (!def_bb) 384169689Skan return true; 385169689Skan 386169689Skan max_loop = outermost_invariant_loop (def, loop); 387169689Skan if (!max_loop) 388169689Skan return false; 389169689Skan 390169689Skan if (flow_loop_nested_p (data->max_loop, max_loop)) 391169689Skan data->max_loop = max_loop; 392169689Skan 393169689Skan if (!LIM_DATA (def_stmt)) 394169689Skan return true; 395169689Skan 396169689Skan if (add_cost 397169689Skan /* Only add the cost if the statement defining DEF is inside LOOP, 398169689Skan i.e. if it is likely that by moving the invariants dependent 399169689Skan on it, we will be able to avoid creating a new register for 400169689Skan it (since it will be only used in these dependent invariants). */ 401169689Skan && def_bb->loop_father == loop) 402169689Skan data->cost += LIM_DATA (def_stmt)->cost; 403169689Skan 404169689Skan dep = XNEW (struct depend); 405169689Skan dep->stmt = def_stmt; 406169689Skan dep->next = data->depends; 407169689Skan data->depends = dep; 408169689Skan 409169689Skan return true; 410169689Skan} 411169689Skan 412169689Skan/* Returns an estimate for a cost of statement STMT. TODO -- the values here 413169689Skan are just ad-hoc constants. The estimates should be based on target-specific 414169689Skan values. */ 415169689Skan 416169689Skanstatic unsigned 417169689Skanstmt_cost (tree stmt) 418169689Skan{ 419169689Skan tree rhs; 420169689Skan unsigned cost = 1; 421169689Skan 422169689Skan /* Always try to create possibilities for unswitching. */ 423169689Skan if (TREE_CODE (stmt) == COND_EXPR) 424169689Skan return LIM_EXPENSIVE; 425169689Skan 426169689Skan rhs = TREE_OPERAND (stmt, 1); 427169689Skan 428169689Skan /* Hoisting memory references out should almost surely be a win. */ 429169689Skan if (stmt_references_memory_p (stmt)) 430169689Skan cost += 20; 431169689Skan 432169689Skan switch (TREE_CODE (rhs)) 433169689Skan { 434169689Skan case CALL_EXPR: 435169689Skan /* We should be hoisting calls if possible. */ 436169689Skan 437169689Skan /* Unless the call is a builtin_constant_p; this always folds to a 438169689Skan constant, so moving it is useless. */ 439169689Skan rhs = get_callee_fndecl (rhs); 440169689Skan if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL 441169689Skan && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P) 442169689Skan return 0; 443169689Skan 444169689Skan cost += 20; 445169689Skan break; 446169689Skan 447169689Skan case MULT_EXPR: 448169689Skan case TRUNC_DIV_EXPR: 449169689Skan case CEIL_DIV_EXPR: 450169689Skan case FLOOR_DIV_EXPR: 451169689Skan case ROUND_DIV_EXPR: 452169689Skan case EXACT_DIV_EXPR: 453169689Skan case CEIL_MOD_EXPR: 454169689Skan case FLOOR_MOD_EXPR: 455169689Skan case ROUND_MOD_EXPR: 456169689Skan case TRUNC_MOD_EXPR: 457169689Skan case RDIV_EXPR: 458169689Skan /* Division and multiplication are usually expensive. */ 459169689Skan cost += 20; 460169689Skan break; 461169689Skan 462169689Skan default: 463169689Skan break; 464169689Skan } 465169689Skan 466169689Skan return cost; 467169689Skan} 468169689Skan 469169689Skan/* Determine the outermost loop to that it is possible to hoist a statement 470169689Skan STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine 471169689Skan the outermost loop in that the value computed by STMT is invariant. 472169689Skan If MUST_PRESERVE_EXEC is true, additionally choose such a loop that 473169689Skan we preserve the fact whether STMT is executed. It also fills other related 474169689Skan information to LIM_DATA (STMT). 475169689Skan 476169689Skan The function returns false if STMT cannot be hoisted outside of the loop it 477169689Skan is defined in, and true otherwise. */ 478169689Skan 479169689Skanstatic bool 480169689Skandetermine_max_movement (tree stmt, bool must_preserve_exec) 481169689Skan{ 482169689Skan basic_block bb = bb_for_stmt (stmt); 483169689Skan struct loop *loop = bb->loop_father; 484169689Skan struct loop *level; 485169689Skan struct lim_aux_data *lim_data = LIM_DATA (stmt); 486169689Skan tree val; 487169689Skan ssa_op_iter iter; 488169689Skan 489169689Skan if (must_preserve_exec) 490169689Skan level = ALWAYS_EXECUTED_IN (bb); 491169689Skan else 492169689Skan level = superloop_at_depth (loop, 1); 493169689Skan lim_data->max_loop = level; 494169689Skan 495169689Skan FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE) 496169689Skan if (!add_dependency (val, lim_data, loop, true)) 497169689Skan return false; 498169689Skan 499169689Skan FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 500169689Skan if (!add_dependency (val, lim_data, loop, false)) 501169689Skan return false; 502169689Skan 503169689Skan lim_data->cost += stmt_cost (stmt); 504169689Skan 505169689Skan return true; 506169689Skan} 507169689Skan 508169689Skan/* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL, 509169689Skan and that one of the operands of this statement is computed by STMT. 510169689Skan Ensure that STMT (together with all the statements that define its 511169689Skan operands) is hoisted at least out of the loop LEVEL. */ 512169689Skan 513169689Skanstatic void 514169689Skanset_level (tree stmt, struct loop *orig_loop, struct loop *level) 515169689Skan{ 516169689Skan struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father; 517169689Skan struct depend *dep; 518169689Skan 519169689Skan stmt_loop = find_common_loop (orig_loop, stmt_loop); 520169689Skan if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop) 521169689Skan stmt_loop = find_common_loop (stmt_loop, 522169689Skan LIM_DATA (stmt)->tgt_loop->outer); 523169689Skan if (flow_loop_nested_p (stmt_loop, level)) 524169689Skan return; 525169689Skan 526169689Skan gcc_assert (LIM_DATA (stmt)); 527169689Skan gcc_assert (level == LIM_DATA (stmt)->max_loop 528169689Skan || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level)); 529169689Skan 530169689Skan LIM_DATA (stmt)->tgt_loop = level; 531169689Skan for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next) 532169689Skan set_level (dep->stmt, orig_loop, level); 533169689Skan} 534169689Skan 535169689Skan/* Determines an outermost loop from that we want to hoist the statement STMT. 536169689Skan For now we chose the outermost possible loop. TODO -- use profiling 537169689Skan information to set it more sanely. */ 538169689Skan 539169689Skanstatic void 540169689Skanset_profitable_level (tree stmt) 541169689Skan{ 542169689Skan set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop); 543169689Skan} 544169689Skan 545169689Skan/* Returns true if STMT is not a pure call. */ 546169689Skan 547169689Skanstatic bool 548169689Skannonpure_call_p (tree stmt) 549169689Skan{ 550169689Skan tree call = get_call_expr_in (stmt); 551169689Skan 552169689Skan if (!call) 553169689Skan return false; 554169689Skan 555169689Skan return TREE_SIDE_EFFECTS (call) != 0; 556169689Skan} 557169689Skan 558169689Skan/* Releases the memory occupied by DATA. */ 559169689Skan 560169689Skanstatic void 561169689Skanfree_lim_aux_data (struct lim_aux_data *data) 562169689Skan{ 563169689Skan struct depend *dep, *next; 564169689Skan 565169689Skan for (dep = data->depends; dep; dep = next) 566169689Skan { 567169689Skan next = dep->next; 568169689Skan free (dep); 569169689Skan } 570169689Skan free (data); 571169689Skan} 572169689Skan 573169689Skan/* Determine the outermost loops in that statements in basic block BB are 574169689Skan invariant, and record them to the LIM_DATA associated with the statements. 575169689Skan Callback for walk_dominator_tree. */ 576169689Skan 577169689Skanstatic void 578169689Skandetermine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, 579169689Skan basic_block bb) 580169689Skan{ 581169689Skan enum move_pos pos; 582169689Skan block_stmt_iterator bsi; 583169689Skan tree stmt, rhs; 584169689Skan bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL; 585169689Skan struct loop *outermost = ALWAYS_EXECUTED_IN (bb); 586169689Skan 587169689Skan if (!bb->loop_father->outer) 588169689Skan return; 589169689Skan 590169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 591169689Skan fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n", 592169689Skan bb->index, bb->loop_father->num, bb->loop_father->depth); 593169689Skan 594169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 595169689Skan { 596169689Skan stmt = bsi_stmt (bsi); 597169689Skan 598169689Skan pos = movement_possibility (stmt); 599169689Skan if (pos == MOVE_IMPOSSIBLE) 600169689Skan { 601169689Skan if (nonpure_call_p (stmt)) 602169689Skan { 603169689Skan maybe_never = true; 604169689Skan outermost = NULL; 605169689Skan } 606169689Skan continue; 607169689Skan } 608169689Skan 609169689Skan /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal 610169689Skan to be hoisted out of loop, saving expensive divide. */ 611169689Skan if (pos == MOVE_POSSIBLE 612169689Skan && (rhs = TREE_OPERAND (stmt, 1)) != NULL 613169689Skan && TREE_CODE (rhs) == RDIV_EXPR 614169689Skan && flag_unsafe_math_optimizations 615169689Skan && !flag_trapping_math 616169689Skan && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1), 617169689Skan loop_containing_stmt (stmt)) != NULL 618169689Skan && outermost_invariant_loop_expr (rhs, 619169689Skan loop_containing_stmt (stmt)) == NULL) 620169689Skan { 621169689Skan tree lhs, stmt1, stmt2, var, name; 622169689Skan 623169689Skan lhs = TREE_OPERAND (stmt, 0); 624169689Skan 625169689Skan /* stmt must be MODIFY_EXPR. */ 626169689Skan var = create_tmp_var (TREE_TYPE (rhs), "reciptmp"); 627169689Skan add_referenced_var (var); 628169689Skan 629169689Skan stmt1 = build2 (MODIFY_EXPR, void_type_node, var, 630169689Skan build2 (RDIV_EXPR, TREE_TYPE (rhs), 631169689Skan build_real (TREE_TYPE (rhs), dconst1), 632169689Skan TREE_OPERAND (rhs, 1))); 633169689Skan name = make_ssa_name (var, stmt1); 634169689Skan TREE_OPERAND (stmt1, 0) = name; 635169689Skan stmt2 = build2 (MODIFY_EXPR, void_type_node, lhs, 636169689Skan build2 (MULT_EXPR, TREE_TYPE (rhs), 637169689Skan name, TREE_OPERAND (rhs, 0))); 638169689Skan 639169689Skan /* Replace division stmt with reciprocal and multiply stmts. 640169689Skan The multiply stmt is not invariant, so update iterator 641169689Skan and avoid rescanning. */ 642169689Skan bsi_replace (&bsi, stmt1, true); 643169689Skan bsi_insert_after (&bsi, stmt2, BSI_NEW_STMT); 644169689Skan SSA_NAME_DEF_STMT (lhs) = stmt2; 645169689Skan 646169689Skan /* Continue processing with invariant reciprocal statement. */ 647169689Skan stmt = stmt1; 648169689Skan } 649169689Skan 650169689Skan stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); 651169689Skan LIM_DATA (stmt)->always_executed_in = outermost; 652169689Skan 653169689Skan if (maybe_never && pos == MOVE_PRESERVE_EXECUTION) 654169689Skan continue; 655169689Skan 656169689Skan if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION)) 657169689Skan { 658169689Skan LIM_DATA (stmt)->max_loop = NULL; 659169689Skan continue; 660169689Skan } 661169689Skan 662169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 663169689Skan { 664169689Skan print_generic_stmt_indented (dump_file, stmt, 0, 2); 665169689Skan fprintf (dump_file, " invariant up to level %d, cost %d.\n\n", 666169689Skan LIM_DATA (stmt)->max_loop->depth, 667169689Skan LIM_DATA (stmt)->cost); 668169689Skan } 669169689Skan 670169689Skan if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE) 671169689Skan set_profitable_level (stmt); 672169689Skan } 673169689Skan} 674169689Skan 675169689Skan/* For each statement determines the outermost loop in that it is invariant, 676169689Skan statements on whose motion it depends and the cost of the computation. 677169689Skan This information is stored to the LIM_DATA structure associated with 678169689Skan each statement. */ 679169689Skan 680169689Skanstatic void 681169689Skandetermine_invariantness (void) 682169689Skan{ 683169689Skan struct dom_walk_data walk_data; 684169689Skan 685169689Skan memset (&walk_data, 0, sizeof (struct dom_walk_data)); 686169689Skan walk_data.before_dom_children_before_stmts = determine_invariantness_stmt; 687169689Skan 688169689Skan init_walk_dominator_tree (&walk_data); 689169689Skan walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 690169689Skan fini_walk_dominator_tree (&walk_data); 691169689Skan} 692169689Skan 693169689Skan/* Commits edge insertions and updates loop structures. */ 694169689Skan 695169689Skanvoid 696169689Skanloop_commit_inserts (void) 697169689Skan{ 698169689Skan unsigned old_last_basic_block, i; 699169689Skan basic_block bb; 700169689Skan 701169689Skan old_last_basic_block = last_basic_block; 702169689Skan bsi_commit_edge_inserts (); 703169689Skan for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++) 704169689Skan { 705169689Skan bb = BASIC_BLOCK (i); 706169689Skan add_bb_to_loop (bb, 707169689Skan find_common_loop (single_pred (bb)->loop_father, 708169689Skan single_succ (bb)->loop_father)); 709169689Skan } 710169689Skan} 711169689Skan 712169689Skan/* Hoist the statements in basic block BB out of the loops prescribed by 713169689Skan data stored in LIM_DATA structures associated with each statement. Callback 714169689Skan for walk_dominator_tree. */ 715169689Skan 716169689Skanstatic void 717169689Skanmove_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, 718169689Skan basic_block bb) 719169689Skan{ 720169689Skan struct loop *level; 721169689Skan block_stmt_iterator bsi; 722169689Skan tree stmt; 723169689Skan unsigned cost = 0; 724169689Skan 725169689Skan if (!bb->loop_father->outer) 726169689Skan return; 727169689Skan 728169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 729169689Skan { 730169689Skan stmt = bsi_stmt (bsi); 731169689Skan 732169689Skan if (!LIM_DATA (stmt)) 733169689Skan { 734169689Skan bsi_next (&bsi); 735169689Skan continue; 736169689Skan } 737169689Skan 738169689Skan cost = LIM_DATA (stmt)->cost; 739169689Skan level = LIM_DATA (stmt)->tgt_loop; 740169689Skan free_lim_aux_data (LIM_DATA (stmt)); 741169689Skan stmt_ann (stmt)->common.aux = NULL; 742169689Skan 743169689Skan if (!level) 744169689Skan { 745169689Skan bsi_next (&bsi); 746169689Skan continue; 747169689Skan } 748169689Skan 749169689Skan /* We do not really want to move conditionals out of the loop; we just 750169689Skan placed it here to force its operands to be moved if necessary. */ 751169689Skan if (TREE_CODE (stmt) == COND_EXPR) 752169689Skan continue; 753169689Skan 754169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 755169689Skan { 756169689Skan fprintf (dump_file, "Moving statement\n"); 757169689Skan print_generic_stmt (dump_file, stmt, 0); 758169689Skan fprintf (dump_file, "(cost %u) out of loop %d.\n\n", 759169689Skan cost, level->num); 760169689Skan } 761169689Skan bsi_insert_on_edge (loop_preheader_edge (level), stmt); 762169689Skan bsi_remove (&bsi, false); 763169689Skan } 764169689Skan} 765169689Skan 766169689Skan/* Hoist the statements out of the loops prescribed by data stored in 767169689Skan LIM_DATA structures associated with each statement.*/ 768169689Skan 769169689Skanstatic void 770169689Skanmove_computations (void) 771169689Skan{ 772169689Skan struct dom_walk_data walk_data; 773169689Skan 774169689Skan memset (&walk_data, 0, sizeof (struct dom_walk_data)); 775169689Skan walk_data.before_dom_children_before_stmts = move_computations_stmt; 776169689Skan 777169689Skan init_walk_dominator_tree (&walk_data); 778169689Skan walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 779169689Skan fini_walk_dominator_tree (&walk_data); 780169689Skan 781169689Skan loop_commit_inserts (); 782169689Skan if (need_ssa_update_p ()) 783169689Skan rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 784169689Skan} 785169689Skan 786169689Skan/* Checks whether the statement defining variable *INDEX can be hoisted 787169689Skan out of the loop passed in DATA. Callback for for_each_index. */ 788169689Skan 789169689Skanstatic bool 790169689Skanmay_move_till (tree ref, tree *index, void *data) 791169689Skan{ 792169689Skan struct loop *loop = data, *max_loop; 793169689Skan 794169689Skan /* If REF is an array reference, check also that the step and the lower 795169689Skan bound is invariant in LOOP. */ 796169689Skan if (TREE_CODE (ref) == ARRAY_REF) 797169689Skan { 798169689Skan tree step = array_ref_element_size (ref); 799169689Skan tree lbound = array_ref_low_bound (ref); 800169689Skan 801169689Skan max_loop = outermost_invariant_loop_expr (step, loop); 802169689Skan if (!max_loop) 803169689Skan return false; 804169689Skan 805169689Skan max_loop = outermost_invariant_loop_expr (lbound, loop); 806169689Skan if (!max_loop) 807169689Skan return false; 808169689Skan } 809169689Skan 810169689Skan max_loop = outermost_invariant_loop (*index, loop); 811169689Skan if (!max_loop) 812169689Skan return false; 813169689Skan 814169689Skan return true; 815169689Skan} 816169689Skan 817169689Skan/* Forces statements defining (invariant) SSA names in expression EXPR to be 818169689Skan moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */ 819169689Skan 820169689Skanstatic void 821169689Skanforce_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop) 822169689Skan{ 823169689Skan enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr)); 824169689Skan unsigned i, nops; 825169689Skan 826169689Skan if (TREE_CODE (expr) == SSA_NAME) 827169689Skan { 828169689Skan tree stmt = SSA_NAME_DEF_STMT (expr); 829169689Skan if (IS_EMPTY_STMT (stmt)) 830169689Skan return; 831169689Skan 832169689Skan set_level (stmt, orig_loop, loop); 833169689Skan return; 834169689Skan } 835169689Skan 836169689Skan if (class != tcc_unary 837169689Skan && class != tcc_binary 838169689Skan && class != tcc_expression 839169689Skan && class != tcc_comparison) 840169689Skan return; 841169689Skan 842169689Skan nops = TREE_CODE_LENGTH (TREE_CODE (expr)); 843169689Skan for (i = 0; i < nops; i++) 844169689Skan force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop); 845169689Skan} 846169689Skan 847169689Skan/* Forces statement defining invariants in REF (and *INDEX) to be moved out of 848169689Skan the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for 849169689Skan for_each_index. */ 850169689Skan 851169689Skanstruct fmt_data 852169689Skan{ 853169689Skan struct loop *loop; 854169689Skan struct loop *orig_loop; 855169689Skan}; 856169689Skan 857169689Skanstatic bool 858169689Skanforce_move_till (tree ref, tree *index, void *data) 859169689Skan{ 860169689Skan tree stmt; 861169689Skan struct fmt_data *fmt_data = data; 862169689Skan 863169689Skan if (TREE_CODE (ref) == ARRAY_REF) 864169689Skan { 865169689Skan tree step = array_ref_element_size (ref); 866169689Skan tree lbound = array_ref_low_bound (ref); 867169689Skan 868169689Skan force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop); 869169689Skan force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop); 870169689Skan } 871169689Skan 872169689Skan if (TREE_CODE (*index) != SSA_NAME) 873169689Skan return true; 874169689Skan 875169689Skan stmt = SSA_NAME_DEF_STMT (*index); 876169689Skan if (IS_EMPTY_STMT (stmt)) 877169689Skan return true; 878169689Skan 879169689Skan set_level (stmt, fmt_data->orig_loop, fmt_data->loop); 880169689Skan 881169689Skan return true; 882169689Skan} 883169689Skan 884169689Skan/* Records memory reference location *REF to the list MEM_REFS. The reference 885169689Skan occurs in statement STMT. */ 886169689Skan 887169689Skanstatic void 888169689Skanrecord_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref) 889169689Skan{ 890169689Skan struct mem_ref_loc *aref = XNEW (struct mem_ref_loc); 891169689Skan 892169689Skan aref->stmt = stmt; 893169689Skan aref->ref = ref; 894169689Skan 895169689Skan aref->next = *mem_refs; 896169689Skan *mem_refs = aref; 897169689Skan} 898169689Skan 899169689Skan/* Releases list of memory reference locations MEM_REFS. */ 900169689Skan 901169689Skanstatic void 902169689Skanfree_mem_ref_locs (struct mem_ref_loc *mem_refs) 903169689Skan{ 904169689Skan struct mem_ref_loc *act; 905169689Skan 906169689Skan while (mem_refs) 907169689Skan { 908169689Skan act = mem_refs; 909169689Skan mem_refs = mem_refs->next; 910169689Skan free (act); 911169689Skan } 912169689Skan} 913169689Skan 914169689Skan/* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */ 915169689Skan 916169689Skanstatic void 917169689Skanrewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs) 918169689Skan{ 919169689Skan tree var; 920169689Skan ssa_op_iter iter; 921169689Skan 922169689Skan for (; mem_refs; mem_refs = mem_refs->next) 923169689Skan { 924169689Skan FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS) 925169689Skan mark_sym_for_renaming (SSA_NAME_VAR (var)); 926169689Skan 927169689Skan *mem_refs->ref = tmp_var; 928169689Skan update_stmt (mem_refs->stmt); 929169689Skan } 930169689Skan} 931169689Skan 932169689Skan/* The name and the length of the currently generated variable 933169689Skan for lsm. */ 934169689Skan#define MAX_LSM_NAME_LENGTH 40 935169689Skanstatic char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1]; 936169689Skanstatic int lsm_tmp_name_length; 937169689Skan 938169689Skan/* Adds S to lsm_tmp_name. */ 939169689Skan 940169689Skanstatic void 941169689Skanlsm_tmp_name_add (const char *s) 942169689Skan{ 943169689Skan int l = strlen (s) + lsm_tmp_name_length; 944169689Skan if (l > MAX_LSM_NAME_LENGTH) 945169689Skan return; 946169689Skan 947169689Skan strcpy (lsm_tmp_name + lsm_tmp_name_length, s); 948169689Skan lsm_tmp_name_length = l; 949169689Skan} 950169689Skan 951169689Skan/* Stores the name for temporary variable that replaces REF to 952169689Skan lsm_tmp_name. */ 953169689Skan 954169689Skanstatic void 955169689Skangen_lsm_tmp_name (tree ref) 956169689Skan{ 957169689Skan const char *name; 958169689Skan 959169689Skan switch (TREE_CODE (ref)) 960169689Skan { 961169689Skan case MISALIGNED_INDIRECT_REF: 962169689Skan case ALIGN_INDIRECT_REF: 963169689Skan case INDIRECT_REF: 964169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 965169689Skan lsm_tmp_name_add ("_"); 966169689Skan break; 967169689Skan 968169689Skan case BIT_FIELD_REF: 969169689Skan case VIEW_CONVERT_EXPR: 970169689Skan case ARRAY_RANGE_REF: 971169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 972169689Skan break; 973169689Skan 974169689Skan case REALPART_EXPR: 975169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 976169689Skan lsm_tmp_name_add ("_RE"); 977169689Skan break; 978169689Skan 979169689Skan case IMAGPART_EXPR: 980169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 981169689Skan lsm_tmp_name_add ("_IM"); 982169689Skan break; 983169689Skan 984169689Skan case COMPONENT_REF: 985169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 986169689Skan lsm_tmp_name_add ("_"); 987169689Skan name = get_name (TREE_OPERAND (ref, 1)); 988169689Skan if (!name) 989169689Skan name = "F"; 990169689Skan lsm_tmp_name_add ("_"); 991169689Skan lsm_tmp_name_add (name); 992169689Skan 993169689Skan case ARRAY_REF: 994169689Skan gen_lsm_tmp_name (TREE_OPERAND (ref, 0)); 995169689Skan lsm_tmp_name_add ("_I"); 996169689Skan break; 997169689Skan 998169689Skan case SSA_NAME: 999169689Skan ref = SSA_NAME_VAR (ref); 1000169689Skan /* Fallthru. */ 1001169689Skan 1002169689Skan case VAR_DECL: 1003169689Skan case PARM_DECL: 1004169689Skan name = get_name (ref); 1005169689Skan if (!name) 1006169689Skan name = "D"; 1007169689Skan lsm_tmp_name_add (name); 1008169689Skan break; 1009169689Skan 1010169689Skan case STRING_CST: 1011169689Skan lsm_tmp_name_add ("S"); 1012169689Skan break; 1013169689Skan 1014169689Skan case RESULT_DECL: 1015169689Skan lsm_tmp_name_add ("R"); 1016169689Skan break; 1017169689Skan 1018169689Skan default: 1019169689Skan gcc_unreachable (); 1020169689Skan } 1021169689Skan} 1022169689Skan 1023169689Skan/* Determines name for temporary variable that replaces REF. 1024169689Skan The name is accumulated into the lsm_tmp_name variable. */ 1025169689Skan 1026169689Skanstatic char * 1027169689Skanget_lsm_tmp_name (tree ref) 1028169689Skan{ 1029169689Skan lsm_tmp_name_length = 0; 1030169689Skan gen_lsm_tmp_name (ref); 1031169689Skan lsm_tmp_name_add ("_lsm"); 1032169689Skan return lsm_tmp_name; 1033169689Skan} 1034169689Skan 1035169689Skan/* Records request for store motion of memory reference REF from LOOP. 1036169689Skan MEM_REFS is the list of occurrences of the reference REF inside LOOP; 1037169689Skan these references are rewritten by a new temporary variable. 1038169689Skan Exits from the LOOP are stored in EXITS, there are N_EXITS of them. 1039169689Skan The initialization of the temporary variable is put to the preheader 1040169689Skan of the loop, and assignments to the reference from the temporary variable 1041169689Skan are emitted to exits. */ 1042169689Skan 1043169689Skanstatic void 1044169689Skanschedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref, 1045169689Skan struct mem_ref_loc *mem_refs) 1046169689Skan{ 1047169689Skan struct mem_ref_loc *aref; 1048169689Skan tree tmp_var; 1049169689Skan unsigned i; 1050169689Skan tree load, store; 1051169689Skan struct fmt_data fmt_data; 1052169689Skan 1053169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1054169689Skan { 1055169689Skan fprintf (dump_file, "Executing store motion of "); 1056169689Skan print_generic_expr (dump_file, ref, 0); 1057169689Skan fprintf (dump_file, " from loop %d\n", loop->num); 1058169689Skan } 1059169689Skan 1060169689Skan tmp_var = make_rename_temp (TREE_TYPE (ref), 1061169689Skan get_lsm_tmp_name (ref)); 1062169689Skan 1063169689Skan fmt_data.loop = loop; 1064169689Skan fmt_data.orig_loop = loop; 1065169689Skan for_each_index (&ref, force_move_till, &fmt_data); 1066169689Skan 1067169689Skan rewrite_mem_refs (tmp_var, mem_refs); 1068169689Skan for (aref = mem_refs; aref; aref = aref->next) 1069169689Skan if (LIM_DATA (aref->stmt)) 1070169689Skan LIM_DATA (aref->stmt)->sm_done = true; 1071169689Skan 1072169689Skan /* Emit the load & stores. */ 1073169689Skan load = build2 (MODIFY_EXPR, void_type_node, tmp_var, ref); 1074169689Skan get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); 1075169689Skan LIM_DATA (load)->max_loop = loop; 1076169689Skan LIM_DATA (load)->tgt_loop = loop; 1077169689Skan 1078169689Skan /* Put this into the latch, so that we are sure it will be processed after 1079169689Skan all dependencies. */ 1080169689Skan bsi_insert_on_edge (loop_latch_edge (loop), load); 1081169689Skan 1082169689Skan for (i = 0; i < n_exits; i++) 1083169689Skan { 1084169689Skan store = build2 (MODIFY_EXPR, void_type_node, 1085169689Skan unshare_expr (ref), tmp_var); 1086169689Skan bsi_insert_on_edge (exits[i], store); 1087169689Skan } 1088169689Skan} 1089169689Skan 1090169689Skan/* Check whether memory reference REF can be hoisted out of the LOOP. If this 1091169689Skan is true, prepare the statements that load the value of the memory reference 1092169689Skan to a temporary variable in the loop preheader, store it back on the loop 1093169689Skan exits, and replace all the references inside LOOP by this temporary variable. 1094169689Skan LOOP has N_EXITS stored in EXITS. CLOBBERED_VOPS is the bitmap of virtual 1095169689Skan operands that are clobbered by a call or accessed through multiple references 1096169689Skan in loop. */ 1097169689Skan 1098169689Skanstatic void 1099169689Skandetermine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits, 1100169689Skan bitmap clobbered_vops, struct mem_ref *ref) 1101169689Skan{ 1102169689Skan struct mem_ref_loc *aref; 1103169689Skan struct loop *must_exec; 1104169689Skan 1105169689Skan /* In case the memory is not stored to, there is nothing for SM to do. */ 1106169689Skan if (!ref->is_stored) 1107169689Skan return; 1108169689Skan 1109169689Skan /* If the reference is aliased with any different ref, or killed by call 1110169689Skan in function, then fail. */ 1111169689Skan if (bitmap_intersect_p (ref->vops, clobbered_vops)) 1112169689Skan return; 1113169689Skan 1114169689Skan if (tree_could_trap_p (ref->mem)) 1115169689Skan { 1116169689Skan /* If the memory access is unsafe (i.e. it might trap), ensure that some 1117169689Skan of the statements in that it occurs is always executed when the loop 1118169689Skan is entered. This way we know that by moving the load from the 1119169689Skan reference out of the loop we will not cause the error that would not 1120169689Skan occur otherwise. 1121169689Skan 1122169689Skan TODO -- in fact we would like to check for anticipability of the 1123169689Skan reference, i.e. that on each path from loop entry to loop exit at 1124169689Skan least one of the statements containing the memory reference is 1125169689Skan executed. */ 1126169689Skan 1127169689Skan for (aref = ref->locs; aref; aref = aref->next) 1128169689Skan { 1129169689Skan if (!LIM_DATA (aref->stmt)) 1130169689Skan continue; 1131169689Skan 1132169689Skan must_exec = LIM_DATA (aref->stmt)->always_executed_in; 1133169689Skan if (!must_exec) 1134169689Skan continue; 1135169689Skan 1136169689Skan if (must_exec == loop 1137169689Skan || flow_loop_nested_p (must_exec, loop)) 1138169689Skan break; 1139169689Skan } 1140169689Skan 1141169689Skan if (!aref) 1142169689Skan return; 1143169689Skan } 1144169689Skan 1145169689Skan schedule_sm (loop, exits, n_exits, ref->mem, ref->locs); 1146169689Skan} 1147169689Skan 1148169689Skan/* Hoists memory references MEM_REFS out of LOOP. CLOBBERED_VOPS is the list 1149169689Skan of vops clobbered by call in loop or accessed by multiple memory references. 1150169689Skan EXITS is the list of N_EXITS exit edges of the LOOP. */ 1151169689Skan 1152169689Skanstatic void 1153169689Skanhoist_memory_references (struct loop *loop, struct mem_ref *mem_refs, 1154169689Skan bitmap clobbered_vops, edge *exits, unsigned n_exits) 1155169689Skan{ 1156169689Skan struct mem_ref *ref; 1157169689Skan 1158169689Skan for (ref = mem_refs; ref; ref = ref->next) 1159169689Skan determine_lsm_ref (loop, exits, n_exits, clobbered_vops, ref); 1160169689Skan} 1161169689Skan 1162169689Skan/* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable 1163169689Skan for a store motion optimization (i.e. whether we can insert statement 1164169689Skan on its exits). */ 1165169689Skan 1166169689Skanstatic bool 1167169689Skanloop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits, 1168169689Skan unsigned n_exits) 1169169689Skan{ 1170169689Skan unsigned i; 1171169689Skan 1172169689Skan for (i = 0; i < n_exits; i++) 1173169689Skan if (exits[i]->flags & EDGE_ABNORMAL) 1174169689Skan return false; 1175169689Skan 1176169689Skan return true; 1177169689Skan} 1178169689Skan 1179169689Skan/* A hash function for struct mem_ref object OBJ. */ 1180169689Skan 1181169689Skanstatic hashval_t 1182169689Skanmemref_hash (const void *obj) 1183169689Skan{ 1184169689Skan const struct mem_ref *mem = obj; 1185169689Skan 1186169689Skan return mem->hash; 1187169689Skan} 1188169689Skan 1189169689Skan/* An equality function for struct mem_ref object OBJ1 with 1190169689Skan memory reference OBJ2. */ 1191169689Skan 1192169689Skanstatic int 1193169689Skanmemref_eq (const void *obj1, const void *obj2) 1194169689Skan{ 1195169689Skan const struct mem_ref *mem1 = obj1; 1196169689Skan 1197169689Skan return operand_equal_p (mem1->mem, (tree) obj2, 0); 1198169689Skan} 1199169689Skan 1200169689Skan/* Gathers memory references in statement STMT in LOOP, storing the 1201169689Skan information about them in MEM_REFS hash table. Note vops accessed through 1202169689Skan unrecognized statements in CLOBBERED_VOPS. The newly created references 1203169689Skan are also stored to MEM_REF_LIST. */ 1204169689Skan 1205169689Skanstatic void 1206169689Skangather_mem_refs_stmt (struct loop *loop, htab_t mem_refs, 1207169689Skan bitmap clobbered_vops, tree stmt, 1208169689Skan struct mem_ref **mem_ref_list) 1209169689Skan{ 1210169689Skan tree *lhs, *rhs, *mem = NULL; 1211169689Skan hashval_t hash; 1212169689Skan PTR *slot; 1213169689Skan struct mem_ref *ref = NULL; 1214169689Skan ssa_op_iter oi; 1215169689Skan tree vname; 1216169689Skan bool is_stored; 1217169689Skan 1218169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 1219169689Skan return; 1220169689Skan 1221169689Skan /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */ 1222169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1223169689Skan goto fail; 1224169689Skan 1225169689Skan lhs = &TREE_OPERAND (stmt, 0); 1226169689Skan rhs = &TREE_OPERAND (stmt, 1); 1227169689Skan 1228169689Skan if (TREE_CODE (*lhs) == SSA_NAME) 1229169689Skan { 1230169689Skan if (!is_gimple_addressable (*rhs)) 1231169689Skan goto fail; 1232169689Skan 1233169689Skan mem = rhs; 1234169689Skan is_stored = false; 1235169689Skan } 1236169689Skan else if (TREE_CODE (*rhs) == SSA_NAME 1237169689Skan || is_gimple_min_invariant (*rhs)) 1238169689Skan { 1239169689Skan mem = lhs; 1240169689Skan is_stored = true; 1241169689Skan } 1242169689Skan else 1243169689Skan goto fail; 1244169689Skan 1245169689Skan /* If we cannot create an SSA name for the result, give up. */ 1246169689Skan if (!is_gimple_reg_type (TREE_TYPE (*mem)) 1247169689Skan || TREE_THIS_VOLATILE (*mem)) 1248169689Skan goto fail; 1249169689Skan 1250169689Skan /* If we cannot move the reference out of the loop, fail. */ 1251169689Skan if (!for_each_index (mem, may_move_till, loop)) 1252169689Skan goto fail; 1253169689Skan 1254169689Skan hash = iterative_hash_expr (*mem, 0); 1255169689Skan slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT); 1256169689Skan 1257169689Skan if (*slot) 1258169689Skan ref = *slot; 1259169689Skan else 1260169689Skan { 1261169689Skan ref = XNEW (struct mem_ref); 1262169689Skan ref->mem = *mem; 1263169689Skan ref->hash = hash; 1264169689Skan ref->locs = NULL; 1265169689Skan ref->is_stored = false; 1266169689Skan ref->vops = BITMAP_ALLOC (NULL); 1267169689Skan ref->next = *mem_ref_list; 1268169689Skan *mem_ref_list = ref; 1269169689Skan *slot = ref; 1270169689Skan } 1271169689Skan ref->is_stored |= is_stored; 1272169689Skan 1273169689Skan FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, 1274169689Skan SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1275169689Skan bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname))); 1276169689Skan record_mem_ref_loc (&ref->locs, stmt, mem); 1277169689Skan return; 1278169689Skan 1279169689Skanfail: 1280169689Skan FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, 1281169689Skan SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 1282169689Skan bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname))); 1283169689Skan} 1284169689Skan 1285169689Skan/* Gathers memory references in LOOP. Notes vops accessed through unrecognized 1286169689Skan statements in CLOBBERED_VOPS. The list of the references found by 1287169689Skan the function is returned. */ 1288169689Skan 1289169689Skanstatic struct mem_ref * 1290169689Skangather_mem_refs (struct loop *loop, bitmap clobbered_vops) 1291169689Skan{ 1292169689Skan basic_block *body = get_loop_body (loop); 1293169689Skan block_stmt_iterator bsi; 1294169689Skan unsigned i; 1295169689Skan struct mem_ref *mem_ref_list = NULL; 1296169689Skan htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL); 1297169689Skan 1298169689Skan for (i = 0; i < loop->num_nodes; i++) 1299169689Skan { 1300169689Skan for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 1301169689Skan gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi), 1302169689Skan &mem_ref_list); 1303169689Skan } 1304169689Skan 1305169689Skan free (body); 1306169689Skan 1307169689Skan htab_delete (mem_refs); 1308169689Skan return mem_ref_list; 1309169689Skan} 1310169689Skan 1311169689Skan/* Finds the vops accessed by more than one of the memory references described 1312169689Skan in MEM_REFS and marks them in CLOBBERED_VOPS. */ 1313169689Skan 1314169689Skanstatic void 1315169689Skanfind_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops) 1316169689Skan{ 1317169689Skan bitmap_head tmp, all_vops; 1318169689Skan struct mem_ref *ref; 1319169689Skan 1320169689Skan bitmap_initialize (&tmp, &bitmap_default_obstack); 1321169689Skan bitmap_initialize (&all_vops, &bitmap_default_obstack); 1322169689Skan 1323169689Skan for (ref = mem_refs; ref; ref = ref->next) 1324169689Skan { 1325169689Skan /* The vops that are already in all_vops are accessed by more than 1326169689Skan one memory reference. */ 1327169689Skan bitmap_and (&tmp, &all_vops, ref->vops); 1328169689Skan bitmap_ior_into (clobbered_vops, &tmp); 1329169689Skan bitmap_clear (&tmp); 1330169689Skan 1331169689Skan bitmap_ior_into (&all_vops, ref->vops); 1332169689Skan } 1333169689Skan 1334169689Skan bitmap_clear (&all_vops); 1335169689Skan} 1336169689Skan 1337169689Skan/* Releases the memory occupied by REF. */ 1338169689Skan 1339169689Skanstatic void 1340169689Skanfree_mem_ref (struct mem_ref *ref) 1341169689Skan{ 1342169689Skan free_mem_ref_locs (ref->locs); 1343169689Skan BITMAP_FREE (ref->vops); 1344169689Skan free (ref); 1345169689Skan} 1346169689Skan 1347169689Skan/* Releases the memory occupied by REFS. */ 1348169689Skan 1349169689Skanstatic void 1350169689Skanfree_mem_refs (struct mem_ref *refs) 1351169689Skan{ 1352169689Skan struct mem_ref *ref, *next; 1353169689Skan 1354169689Skan for (ref = refs; ref; ref = next) 1355169689Skan { 1356169689Skan next = ref->next; 1357169689Skan free_mem_ref (ref); 1358169689Skan } 1359169689Skan} 1360169689Skan 1361169689Skan/* Try to perform store motion for all memory references modified inside 1362169689Skan LOOP. */ 1363169689Skan 1364169689Skanstatic void 1365169689Skandetermine_lsm_loop (struct loop *loop) 1366169689Skan{ 1367169689Skan unsigned n_exits; 1368169689Skan edge *exits = get_loop_exit_edges (loop, &n_exits); 1369169689Skan bitmap clobbered_vops; 1370169689Skan struct mem_ref *mem_refs; 1371169689Skan 1372169689Skan if (!loop_suitable_for_sm (loop, exits, n_exits)) 1373169689Skan { 1374169689Skan free (exits); 1375169689Skan return; 1376169689Skan } 1377169689Skan 1378169689Skan /* Find the memory references in LOOP. */ 1379169689Skan clobbered_vops = BITMAP_ALLOC (NULL); 1380169689Skan mem_refs = gather_mem_refs (loop, clobbered_vops); 1381169689Skan 1382169689Skan /* Find the vops that are used for more than one reference. */ 1383169689Skan find_more_ref_vops (mem_refs, clobbered_vops); 1384169689Skan 1385169689Skan /* Hoist all suitable memory references. */ 1386169689Skan hoist_memory_references (loop, mem_refs, clobbered_vops, exits, n_exits); 1387169689Skan 1388169689Skan free_mem_refs (mem_refs); 1389169689Skan free (exits); 1390169689Skan BITMAP_FREE (clobbered_vops); 1391169689Skan} 1392169689Skan 1393169689Skan/* Try to perform store motion for all memory references modified inside 1394169689Skan any of LOOPS. */ 1395169689Skan 1396169689Skanstatic void 1397169689Skandetermine_lsm (struct loops *loops) 1398169689Skan{ 1399169689Skan struct loop *loop; 1400169689Skan 1401169689Skan if (!loops->tree_root->inner) 1402169689Skan return; 1403169689Skan 1404169689Skan /* Pass the loops from the outermost and perform the store motion as 1405169689Skan suitable. */ 1406169689Skan 1407169689Skan loop = loops->tree_root->inner; 1408169689Skan while (1) 1409169689Skan { 1410169689Skan determine_lsm_loop (loop); 1411169689Skan 1412169689Skan if (loop->inner) 1413169689Skan { 1414169689Skan loop = loop->inner; 1415169689Skan continue; 1416169689Skan } 1417169689Skan while (!loop->next) 1418169689Skan { 1419169689Skan loop = loop->outer; 1420169689Skan if (loop == loops->tree_root) 1421169689Skan { 1422169689Skan loop_commit_inserts (); 1423169689Skan return; 1424169689Skan } 1425169689Skan } 1426169689Skan loop = loop->next; 1427169689Skan } 1428169689Skan} 1429169689Skan 1430169689Skan/* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e. 1431169689Skan for each such basic block bb records the outermost loop for that execution 1432169689Skan of its header implies execution of bb. CONTAINS_CALL is the bitmap of 1433169689Skan blocks that contain a nonpure call. */ 1434169689Skan 1435169689Skanstatic void 1436169689Skanfill_always_executed_in (struct loop *loop, sbitmap contains_call) 1437169689Skan{ 1438169689Skan basic_block bb = NULL, *bbs, last = NULL; 1439169689Skan unsigned i; 1440169689Skan edge e; 1441169689Skan struct loop *inn_loop = loop; 1442169689Skan 1443169689Skan if (!loop->header->aux) 1444169689Skan { 1445169689Skan bbs = get_loop_body_in_dom_order (loop); 1446169689Skan 1447169689Skan for (i = 0; i < loop->num_nodes; i++) 1448169689Skan { 1449169689Skan edge_iterator ei; 1450169689Skan bb = bbs[i]; 1451169689Skan 1452169689Skan if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1453169689Skan last = bb; 1454169689Skan 1455169689Skan if (TEST_BIT (contains_call, bb->index)) 1456169689Skan break; 1457169689Skan 1458169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1459169689Skan if (!flow_bb_inside_loop_p (loop, e->dest)) 1460169689Skan break; 1461169689Skan if (e) 1462169689Skan break; 1463169689Skan 1464169689Skan /* A loop might be infinite (TODO use simple loop analysis 1465169689Skan to disprove this if possible). */ 1466169689Skan if (bb->flags & BB_IRREDUCIBLE_LOOP) 1467169689Skan break; 1468169689Skan 1469169689Skan if (!flow_bb_inside_loop_p (inn_loop, bb)) 1470169689Skan break; 1471169689Skan 1472169689Skan if (bb->loop_father->header == bb) 1473169689Skan { 1474169689Skan if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1475169689Skan break; 1476169689Skan 1477169689Skan /* In a loop that is always entered we may proceed anyway. 1478169689Skan But record that we entered it and stop once we leave it. */ 1479169689Skan inn_loop = bb->loop_father; 1480169689Skan } 1481169689Skan } 1482169689Skan 1483169689Skan while (1) 1484169689Skan { 1485169689Skan last->aux = loop; 1486169689Skan if (last == loop->header) 1487169689Skan break; 1488169689Skan last = get_immediate_dominator (CDI_DOMINATORS, last); 1489169689Skan } 1490169689Skan 1491169689Skan free (bbs); 1492169689Skan } 1493169689Skan 1494169689Skan for (loop = loop->inner; loop; loop = loop->next) 1495169689Skan fill_always_executed_in (loop, contains_call); 1496169689Skan} 1497169689Skan 1498169689Skan/* Compute the global information needed by the loop invariant motion pass. 1499169689Skan LOOPS is the loop tree. */ 1500169689Skan 1501169689Skanstatic void 1502169689Skantree_ssa_lim_initialize (struct loops *loops) 1503169689Skan{ 1504169689Skan sbitmap contains_call = sbitmap_alloc (last_basic_block); 1505169689Skan block_stmt_iterator bsi; 1506169689Skan struct loop *loop; 1507169689Skan basic_block bb; 1508169689Skan 1509169689Skan sbitmap_zero (contains_call); 1510169689Skan FOR_EACH_BB (bb) 1511169689Skan { 1512169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1513169689Skan { 1514169689Skan if (nonpure_call_p (bsi_stmt (bsi))) 1515169689Skan break; 1516169689Skan } 1517169689Skan 1518169689Skan if (!bsi_end_p (bsi)) 1519169689Skan SET_BIT (contains_call, bb->index); 1520169689Skan } 1521169689Skan 1522169689Skan for (loop = loops->tree_root->inner; loop; loop = loop->next) 1523169689Skan fill_always_executed_in (loop, contains_call); 1524169689Skan 1525169689Skan sbitmap_free (contains_call); 1526169689Skan} 1527169689Skan 1528169689Skan/* Cleans up after the invariant motion pass. */ 1529169689Skan 1530169689Skanstatic void 1531169689Skantree_ssa_lim_finalize (void) 1532169689Skan{ 1533169689Skan basic_block bb; 1534169689Skan 1535169689Skan FOR_EACH_BB (bb) 1536169689Skan { 1537169689Skan bb->aux = NULL; 1538169689Skan } 1539169689Skan} 1540169689Skan 1541169689Skan/* Moves invariants from LOOPS. Only "expensive" invariants are moved out -- 1542169689Skan i.e. those that are likely to be win regardless of the register pressure. */ 1543169689Skan 1544169689Skanvoid 1545169689Skantree_ssa_lim (struct loops *loops) 1546169689Skan{ 1547169689Skan tree_ssa_lim_initialize (loops); 1548169689Skan 1549169689Skan /* For each statement determine the outermost loop in that it is 1550169689Skan invariant and cost for computing the invariant. */ 1551169689Skan determine_invariantness (); 1552169689Skan 1553169689Skan /* For each memory reference determine whether it is possible to hoist it 1554169689Skan out of the loop. Force the necessary invariants to be moved out of the 1555169689Skan loops as well. */ 1556169689Skan determine_lsm (loops); 1557169689Skan 1558169689Skan /* Move the expressions that are expensive enough. */ 1559169689Skan move_computations (); 1560169689Skan 1561169689Skan tree_ssa_lim_finalize (); 1562169689Skan} 1563