gcc/tree-ssa-loop-im.c

   1 /* Loop invariant motion.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "domwalk.h"
  37 #include "params.h"
  38 #include "tree-pass.h"
  39 #include "flags.h"
  40
  41 /* A type for the list of statements that have to be moved in order to be able
  42    to hoist an invariant computation.  */
  43
  44 struct depend
  45 {
  46   tree stmt;
  47   struct depend *next;
  48 };
  49
  50 /* The auxiliary data kept for each statement.  */
  51
  52 struct lim_aux_data
  53 {
  54   struct loop *max_loop;        /* The outermost loop in that the statement
  55                                    is invariant.  */
  56
  57   struct loop *tgt_loop;        /* The loop out of that we want to move the
  58                                    invariant.  */
  59
  60   struct loop *always_executed_in;
  61                                 /* The outermost loop for that we are sure
  62                                    the statement is executed if the loop
  63                                    is entered.  */
  64
  65   bool sm_done;                 /* True iff the store motion for a memory
  66                                    reference in the statement has already
  67                                    been executed.  */
  68
  69   unsigned cost;                /* Cost of the computation performed by the
  70                                    statement.  */
  71
  72   struct depend *depends;       /* List of statements that must be also hoisted
  73                                    out of the loop when this statement is
  74                                    hoisted; i.e. those that define the operands
  75                                    of the statement and are inside of the
  76                                    MAX_LOOP loop.  */
  77 };
  78
  79 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
  80                         ? NULL \
  81                         : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
  82
  83 /* Description of a memory reference for store motion.  */
  84
  85 struct mem_ref
  86 {
  87   tree *ref;                    /* The reference itself.  */
  88   tree stmt;                    /* The statement in that it occurs.  */
  89   struct mem_ref *next;         /* Next use in the chain.  */
  90 };
  91
  92 /* Minimum cost of an expensive expression.  */
  93 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
  94
  95 /* The outermost loop for that execution of the header guarantees that the
  96    block will be executed.  */
  97 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
  98
  99 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 100                                    nodes are assigned using the versions of
 101                                    ssa names they define.  */
 102
 103 /* Returns uid of statement STMT.  */
 104
 105 static unsigned
 106 get_stmt_uid (tree stmt)
 107 {
 108   if (TREE_CODE (stmt) == PHI_NODE)
 109     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 110
 111   return stmt_ann (stmt)->uid;
 112 }
 113
 114 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 115    kinds situations handled; in each of these cases, the memory reference
 116    and DATA are passed to the callback:
 117
 118    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 119    pass the pointer to the index to the callback.
 120
 121    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 122    pointer to addr to the callback.
 123
 124    If the callback returns false, the whole search stops and false is returned.
 125    Otherwise the function returns true after traversing through the whole
 126    reference *ADDR_P.  */
 127
 128 bool
 129 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 130 {
 131   tree *nxt;
 132
 133   for (; ; addr_p = nxt)
 134     {
 135       switch (TREE_CODE (*addr_p))
 136         {
 137         case SSA_NAME:
 138           return cbck (*addr_p, addr_p, data);
 139
 140         case MISALIGNED_INDIRECT_REF:
 141         case ALIGN_INDIRECT_REF:
 142         case INDIRECT_REF:
 143           nxt = &TREE_OPERAND (*addr_p, 0);
 144           return cbck (*addr_p, nxt, data);
 145
 146         case BIT_FIELD_REF:
 147         case COMPONENT_REF:
 148         case VIEW_CONVERT_EXPR:
 149         case ARRAY_RANGE_REF:
 150         case REALPART_EXPR:
 151         case IMAGPART_EXPR:
 152           nxt = &TREE_OPERAND (*addr_p, 0);
 153           break;
 154
 155         case ARRAY_REF:
 156           nxt = &TREE_OPERAND (*addr_p, 0);
 157           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 158             return false;
 159           break;
 160
 161         case VAR_DECL:
 162         case PARM_DECL:
 163         case STRING_CST:
 164         case RESULT_DECL:
 165           return true;
 166
 167         default:
 168           gcc_unreachable ();
 169         }
 170     }
 171 }
 172
 173 /* If it is possible to hoist the statement STMT unconditionally,
 174    returns MOVE_POSSIBLE.
 175    If it is possible to hoist the statement STMT, but we must avoid making
 176    it executed if it would not be executed in the original program (e.g.
 177    because it may trap), return MOVE_PRESERVE_EXECUTION.
 178    Otherwise return MOVE_IMPOSSIBLE.  */
 179
 180 enum move_pos
 181 movement_possibility (tree stmt)
 182 {
 183   tree lhs, rhs;
 184
 185   if (flag_unswitch_loops
 186       && TREE_CODE (stmt) == COND_EXPR)
 187     {
 188       /* If we perform unswitching, force the operands of the invariant
 189          condition to be moved out of the loop.  */
 190       get_stmt_operands (stmt);
 191
 192       return MOVE_POSSIBLE;
 193     }
 194
 195   if (TREE_CODE (stmt) != MODIFY_EXPR)
 196     return MOVE_IMPOSSIBLE;
 197
 198   if (stmt_ends_bb_p (stmt))
 199     return MOVE_IMPOSSIBLE;
 200
 201   get_stmt_operands (stmt);
 202
 203   if (stmt_ann (stmt)->has_volatile_ops)
 204     return MOVE_IMPOSSIBLE;
 205
 206   lhs = TREE_OPERAND (stmt, 0);
 207   if (TREE_CODE (lhs) == SSA_NAME
 208       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 209     return MOVE_IMPOSSIBLE;
 210
 211   rhs = TREE_OPERAND (stmt, 1);
 212
 213   if (TREE_SIDE_EFFECTS (rhs))
 214     return MOVE_IMPOSSIBLE;
 215
 216   if (TREE_CODE (lhs) != SSA_NAME
 217       || tree_could_trap_p (rhs))
 218     return MOVE_PRESERVE_EXECUTION;
 219
 220   return MOVE_POSSIBLE;
 221 }
 222
 223 /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
 224    loop to that we could move the expression using DEF if it did not have
 225    other operands, i.e. the outermost loop enclosing LOOP in that the value
 226    of DEF is invariant.  */
 227
 228 static struct loop *
 229 outermost_invariant_loop (tree def, struct loop *loop)
 230 {
 231   tree def_stmt;
 232   basic_block def_bb;
 233   struct loop *max_loop;
 234
 235   if (TREE_CODE (def) != SSA_NAME)
 236     return superloop_at_depth (loop, 1);
 237
 238   def_stmt = SSA_NAME_DEF_STMT (def);
 239   def_bb = bb_for_stmt (def_stmt);
 240   if (!def_bb)
 241     return superloop_at_depth (loop, 1);
 242
 243   max_loop = find_common_loop (loop, def_bb->loop_father);
 244
 245   if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
 246     max_loop = find_common_loop (max_loop,
 247                                  LIM_DATA (def_stmt)->max_loop->outer);
 248   if (max_loop == loop)
 249     return NULL;
 250   max_loop = superloop_at_depth (loop, max_loop->depth + 1);
 251
 252   return max_loop;
 253 }
 254
 255 /* Returns the outermost superloop of LOOP in that the expression EXPR is
 256    invariant.  */
 257
 258 static struct loop *
 259 outermost_invariant_loop_expr (tree expr, struct loop *loop)
 260 {
 261   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
 262   unsigned i, nops;
 263   struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
 264
 265   if (TREE_CODE (expr) == SSA_NAME
 266       || TREE_CODE (expr) == INTEGER_CST
 267       || is_gimple_min_invariant (expr))
 268     return outermost_invariant_loop (expr, loop);
 269
 270   if (class != tcc_unary
 271       && class != tcc_binary
 272       && class != tcc_expression
 273       && class != tcc_comparison)
 274     return NULL;
 275
 276   nops = first_rtl_op (TREE_CODE (expr));
 277   for (i = 0; i < nops; i++)
 278     {
 279       aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
 280       if (!aloop)
 281         return NULL;
 282
 283       if (flow_loop_nested_p (max_loop, aloop))
 284         max_loop = aloop;
 285     }
 286
 287   return max_loop;
 288 }
 289
 290 /* DATA is a structure containing information associated with a statement
 291    inside LOOP.  DEF is one of the operands of this statement.
 292
 293    Find the outermost loop enclosing LOOP in that value of DEF is invariant
 294    and record this in DATA->max_loop field.  If DEF itself is defined inside
 295    this loop as well (i.e. we need to hoist it out of the loop if we want
 296    to hoist the statement represented by DATA), record the statement in that
 297    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
 298    add the cost of the computation of DEF to the DATA->cost.
 299
 300    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
 301
 302 static bool
 303 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
 304                 bool add_cost)
 305 {
 306   tree def_stmt = SSA_NAME_DEF_STMT (def);
 307   basic_block def_bb = bb_for_stmt (def_stmt);
 308   struct loop *max_loop;
 309   struct depend *dep;
 310
 311   if (!def_bb)
 312     return true;
 313
 314   max_loop = outermost_invariant_loop (def, loop);
 315   if (!max_loop)
 316     return false;
 317
 318   if (flow_loop_nested_p (data->max_loop, max_loop))
 319     data->max_loop = max_loop;
 320
 321   if (!LIM_DATA (def_stmt))
 322     return true;
 323
 324   if (add_cost
 325       /* Only add the cost if the statement defining DEF is inside LOOP,
 326          i.e. if it is likely that by moving the invariants dependent
 327          on it, we will be able to avoid creating a new register for
 328          it (since it will be only used in these dependent invariants).  */
 329       && def_bb->loop_father == loop)
 330     data->cost += LIM_DATA (def_stmt)->cost;
 331
 332   dep = xmalloc (sizeof (struct depend));
 333   dep->stmt = def_stmt;
 334   dep->next = data->depends;
 335   data->depends = dep;
 336
 337   return true;
 338 }
 339
 340 /* Returns an estimate for a cost of statement STMT.  TODO -- the values here
 341    are just ad-hoc constants.  The estimates should be based on target-specific
 342    values.  */
 343
 344 static unsigned
 345 stmt_cost (tree stmt)
 346 {
 347   tree lhs, rhs;
 348   unsigned cost = 1;
 349
 350   /* Always try to create possibilities for unswitching.  */
 351   if (TREE_CODE (stmt) == COND_EXPR)
 352     return LIM_EXPENSIVE;
 353
 354   lhs = TREE_OPERAND (stmt, 0);
 355   rhs = TREE_OPERAND (stmt, 1);
 356
 357   /* Hoisting memory references out should almost surely be a win.  */
 358   if (!is_gimple_variable (lhs))
 359     cost += 20;
 360   if (is_gimple_addressable (rhs) && !is_gimple_variable (rhs))
 361     cost += 20;
 362
 363   switch (TREE_CODE (rhs))
 364     {
 365     case CALL_EXPR:
 366       /* We should be hoisting calls if possible.  */
 367
 368       /* Unless the call is a builtin_constant_p; this always folds to a
 369          constant, so moving it is useless.  */
 370       rhs = get_callee_fndecl (rhs);
 371       if (DECL_BUILT_IN (rhs)
 372           && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
 373         return 0;
 374
 375       cost += 20;
 376       break;
 377
 378     case MULT_EXPR:
 379     case TRUNC_DIV_EXPR:
 380     case CEIL_DIV_EXPR:
 381     case FLOOR_DIV_EXPR:
 382     case ROUND_DIV_EXPR:
 383     case EXACT_DIV_EXPR:
 384     case CEIL_MOD_EXPR:
 385     case FLOOR_MOD_EXPR:
 386     case ROUND_MOD_EXPR:
 387     case TRUNC_MOD_EXPR:
 388       /* Division and multiplication are usually expensive.  */
 389       cost += 20;
 390       break;
 391
 392     default:
 393       break;
 394     }
 395
 396   return cost;
 397 }
 398
 399 /* Determine the outermost loop to that it is possible to hoist a statement
 400    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 401    the outermost loop in that the value computed by STMT is invariant.
 402    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 403    we preserve the fact whether STMT is executed.  It also fills other related
 404    information to LIM_DATA (STMT).
 405
 406    The function returns false if STMT cannot be hoisted outside of the loop it
 407    is defined in, and true otherwise.  */
 408
 409 static bool
 410 determine_max_movement (tree stmt, bool must_preserve_exec)
 411 {
 412   basic_block bb = bb_for_stmt (stmt);
 413   struct loop *loop = bb->loop_father;
 414   struct loop *level;
 415   struct lim_aux_data *lim_data = LIM_DATA (stmt);
 416   tree val;
 417   ssa_op_iter iter;
 418
 419   if (must_preserve_exec)
 420     level = ALWAYS_EXECUTED_IN (bb);
 421   else
 422     level = superloop_at_depth (loop, 1);
 423   lim_data->max_loop = level;
 424
 425   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
 426     if (!add_dependency (val, lim_data, loop, true))
 427       return false;
 428
 429   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
 430     if (!add_dependency (val, lim_data, loop, false))
 431       return false;
 432
 433   lim_data->cost += stmt_cost (stmt);
 434
 435   return true;
 436 }
 437
 438 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
 439    and that one of the operands of this statement is computed by STMT.
 440    Ensure that STMT (together with all the statements that define its
 441    operands) is hoisted at least out of the loop LEVEL.  */
 442
 443 static void
 444 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
 445 {
 446   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
 447   struct depend *dep;
 448
 449   stmt_loop = find_common_loop (orig_loop, stmt_loop);
 450   if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
 451     stmt_loop = find_common_loop (stmt_loop,
 452                                   LIM_DATA (stmt)->tgt_loop->outer);
 453   if (flow_loop_nested_p (stmt_loop, level))
 454     return;
 455
 456   gcc_assert (LIM_DATA (stmt));
 457   gcc_assert (level == LIM_DATA (stmt)->max_loop
 458               || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
 459
 460   LIM_DATA (stmt)->tgt_loop = level;
 461   for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
 462     set_level (dep->stmt, orig_loop, level);
 463 }
 464
 465 /* Determines an outermost loop from that we want to hoist the statement STMT.
 466    For now we chose the outermost possible loop.  TODO -- use profiling
 467    information to set it more sanely.  */
 468
 469 static void
 470 set_profitable_level (tree stmt)
 471 {
 472   set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
 473 }
 474
 475 /* Returns true if STMT is not a pure call.  */
 476
 477 static bool
 478 nonpure_call_p (tree stmt)
 479 {
 480   tree call = get_call_expr_in (stmt);
 481
 482   if (!call)
 483     return false;
 484
 485   return TREE_SIDE_EFFECTS (call) != 0;
 486 }
 487
 488 /* Releases the memory occupied by DATA.  */
 489
 490 static void
 491 free_lim_aux_data (struct lim_aux_data *data)
 492 {
 493   struct depend *dep, *next;
 494
 495   for (dep = data->depends; dep; dep = next)
 496     {
 497       next = dep->next;
 498       free (dep);
 499     }
 500   free (data);
 501 }
 502
 503 /* Determine the outermost loops in that statements in basic block BB are
 504    invariant, and record them to the LIM_DATA associated with the statements.
 505    Callback for walk_dominator_tree.  */
 506
 507 static void
 508 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 509                               basic_block bb)
 510 {
 511   enum move_pos pos;
 512   block_stmt_iterator bsi;
 513   tree stmt;
 514   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
 515   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
 516
 517   if (!bb->loop_father->outer)
 518     return;
 519
 520   if (dump_file && (dump_flags & TDF_DETAILS))
 521     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 522              bb->index, bb->loop_father->num, bb->loop_father->depth);
 523
 524   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 525     {
 526       stmt = bsi_stmt (bsi);
 527
 528       pos = movement_possibility (stmt);
 529       if (pos == MOVE_IMPOSSIBLE)
 530         {
 531           if (nonpure_call_p (stmt))
 532             {
 533               maybe_never = true;
 534               outermost = NULL;
 535             }
 536           continue;
 537         }
 538
 539       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
 540       LIM_DATA (stmt)->always_executed_in = outermost;
 541
 542       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
 543         continue;
 544
 545       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
 546         {
 547           LIM_DATA (stmt)->max_loop = NULL;
 548           continue;
 549         }
 550
 551       if (dump_file && (dump_flags & TDF_DETAILS))
 552         {
 553           print_generic_stmt_indented (dump_file, stmt, 0, 2);
 554           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
 555                    LIM_DATA (stmt)->max_loop->depth,
 556                    LIM_DATA (stmt)->cost);
 557         }
 558
 559       if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
 560         set_profitable_level (stmt);
 561     }
 562 }
 563
 564 /* For each statement determines the outermost loop in that it is invariant,
 565    statements on whose motion it depends and the cost of the computation.
 566    This information is stored to the LIM_DATA structure associated with
 567    each statement.  */
 568
 569 static void
 570 determine_invariantness (void)
 571 {
 572   struct dom_walk_data walk_data;
 573
 574   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 575   walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
 576
 577   init_walk_dominator_tree (&walk_data);
 578   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 579   fini_walk_dominator_tree (&walk_data);
 580 }
 581
 582 /* Commits edge insertions and updates loop structures.  */
 583
 584 void
 585 loop_commit_inserts (void)
 586 {
 587   unsigned old_last_basic_block, i;
 588   basic_block bb;
 589
 590   old_last_basic_block = last_basic_block;
 591   bsi_commit_edge_inserts (NULL);
 592   for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
 593     {
 594       bb = BASIC_BLOCK (i);
 595       add_bb_to_loop (bb,
 596                       find_common_loop (bb->succ->dest->loop_father,
 597                                         bb->pred->src->loop_father));
 598     }
 599 }
 600
 601 /* Hoist the statements in basic block BB out of the loops prescribed by
 602    data stored in LIM_DATA structures associated with each statement.  Callback
 603    for walk_dominator_tree.  */
 604
 605 static void
 606 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 607                         basic_block bb)
 608 {
 609   struct loop *level;
 610   block_stmt_iterator bsi;
 611   tree stmt;
 612   unsigned cost = 0;
 613
 614   if (!bb->loop_father->outer)
 615     return;
 616
 617   for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 618     {
 619       stmt = bsi_stmt (bsi);
 620
 621       if (!LIM_DATA (stmt))
 622         {
 623           bsi_next (&bsi);
 624           continue;
 625         }
 626
 627       cost = LIM_DATA (stmt)->cost;
 628       level = LIM_DATA (stmt)->tgt_loop;
 629       free_lim_aux_data (LIM_DATA (stmt));
 630       stmt_ann (stmt)->common.aux = NULL;
 631
 632       if (!level)
 633         {
 634           bsi_next (&bsi);
 635           continue;
 636         }
 637
 638       /* We do not really want to move conditionals out of the loop; we just
 639          placed it here to force its operands to be moved if necessary.  */
 640       if (TREE_CODE (stmt) == COND_EXPR)
 641         continue;
 642
 643       if (dump_file && (dump_flags & TDF_DETAILS))
 644         {
 645           fprintf (dump_file, "Moving statement\n");
 646           print_generic_stmt (dump_file, stmt, 0);
 647           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
 648                    cost, level->num);
 649         }
 650       bsi_insert_on_edge (loop_preheader_edge (level), stmt);
 651       bsi_remove (&bsi);
 652     }
 653 }
 654
 655 /* Hoist the statements out of the loops prescribed by data stored in
 656    LIM_DATA structures associated with each statement.*/
 657
 658 static void
 659 move_computations (void)
 660 {
 661   struct dom_walk_data walk_data;
 662
 663   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 664   walk_data.before_dom_children_before_stmts = move_computations_stmt;
 665
 666   init_walk_dominator_tree (&walk_data);
 667   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 668   fini_walk_dominator_tree (&walk_data);
 669
 670   loop_commit_inserts ();
 671   rewrite_into_ssa (false);
 672   if (bitmap_first_set_bit (vars_to_rename) >= 0)
 673     {
 674       /* The rewrite of ssa names may cause violation of loop closed ssa
 675          form invariants.  TODO -- avoid these rewrites completely.
 676          Information in virtual phi nodes is sufficient for it.  */
 677       rewrite_into_loop_closed_ssa ();
 678     }
 679   bitmap_clear (vars_to_rename);
 680 }
 681
 682 /* Checks whether the statement defining variable *INDEX can be hoisted
 683    out of the loop passed in DATA.  Callback for for_each_index.  */
 684
 685 static bool
 686 may_move_till (tree ref, tree *index, void *data)
 687 {
 688   struct loop *loop = data, *max_loop;
 689
 690   /* If REF is an array reference, check also that the step and the lower
 691      bound is invariant in LOOP.  */
 692   if (TREE_CODE (ref) == ARRAY_REF)
 693     {
 694       tree step = array_ref_element_size (ref);
 695       tree lbound = array_ref_low_bound (ref);
 696
 697       max_loop = outermost_invariant_loop_expr (step, loop);
 698       if (!max_loop)
 699         return false;
 700
 701       max_loop = outermost_invariant_loop_expr (lbound, loop);
 702       if (!max_loop)
 703         return false;
 704     }
 705
 706   max_loop = outermost_invariant_loop (*index, loop);
 707   if (!max_loop)
 708     return false;
 709
 710   return true;
 711 }
 712
 713 /* Forces statements defining (invariant) SSA names in expression EXPR to be
 714    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
 715
 716 static void
 717 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
 718 {
 719   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
 720   unsigned i, nops;
 721
 722   if (TREE_CODE (expr) == SSA_NAME)
 723     {
 724       tree stmt = SSA_NAME_DEF_STMT (expr);
 725       if (IS_EMPTY_STMT (stmt))
 726         return;
 727
 728       set_level (stmt, orig_loop, loop);
 729       return;
 730     }
 731
 732   if (class != tcc_unary
 733       && class != tcc_binary
 734       && class != tcc_expression
 735       && class != tcc_comparison)
 736     return;
 737
 738   nops = first_rtl_op (TREE_CODE (expr));
 739   for (i = 0; i < nops; i++)
 740     force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
 741 }
 742
 743 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 744    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
 745    for_each_index.  */
 746
 747 struct fmt_data
 748 {
 749   struct loop *loop;
 750   struct loop *orig_loop;
 751 };
 752
 753 static bool
 754 force_move_till (tree ref, tree *index, void *data)
 755 {
 756   tree stmt;
 757   struct fmt_data *fmt_data = data;
 758
 759   if (TREE_CODE (ref) == ARRAY_REF)
 760     {
 761       tree step = array_ref_element_size (ref);
 762       tree lbound = array_ref_low_bound (ref);
 763
 764       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
 765       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
 766     }
 767
 768   if (TREE_CODE (*index) != SSA_NAME)
 769     return true;
 770
 771   stmt = SSA_NAME_DEF_STMT (*index);
 772   if (IS_EMPTY_STMT (stmt))
 773     return true;
 774
 775   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
 776
 777   return true;
 778 }
 779
 780 /* Records memory reference *REF (that occurs in statement STMT)
 781    to the list MEM_REFS.  */
 782
 783 static void
 784 record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
 785 {
 786   struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
 787
 788   aref->stmt = stmt;
 789   aref->ref = ref;
 790
 791   aref->next = *mem_refs;
 792   *mem_refs = aref;
 793 }
 794
 795 /* Releases list of memory references MEM_REFS.  */
 796
 797 static void
 798 free_mem_refs (struct mem_ref *mem_refs)
 799 {
 800   struct mem_ref *act;
 801
 802   while (mem_refs)
 803     {
 804       act = mem_refs;
 805       mem_refs = mem_refs->next;
 806       free (act);
 807     }
 808 }
 809
 810 /* If VAR is defined in LOOP and the statement it is defined in does not belong
 811    to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
 812    to the set SEEN.  */
 813
 814 static void
 815 maybe_queue_var (tree var, struct loop *loop,
 816                  sbitmap seen, tree *queue, unsigned *in_queue)
 817 {
 818   tree stmt = SSA_NAME_DEF_STMT (var);
 819   basic_block def_bb = bb_for_stmt (stmt);
 820
 821   if (!def_bb
 822       || !flow_bb_inside_loop_p (loop, def_bb)
 823       || TEST_BIT (seen, get_stmt_uid (stmt)))
 824     return;
 825
 826   SET_BIT (seen, get_stmt_uid (stmt));
 827   queue[(*in_queue)++] = stmt;
 828 }
 829
 830 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
 831    Otherwise return true if the memory reference *OP is equal to COMMON_REF.
 832    Record the reference OP to list MEM_REFS.  STMT is the statement in that
 833    the reference occurs.  */
 834
 835 struct sra_data
 836 {
 837   struct mem_ref **mem_refs;
 838   tree common_ref;
 839   tree stmt;
 840 };
 841
 842 static bool
 843 fem_single_reachable_address (tree *op, void *data)
 844 {
 845   struct sra_data *sra_data = data;
 846
 847   if (sra_data->common_ref
 848       && !operand_equal_p (*op, sra_data->common_ref, 0))
 849     return false;
 850   sra_data->common_ref = *op;
 851
 852   record_mem_ref (sra_data->mem_refs, sra_data->stmt, op);
 853   return true;
 854 }
 855
 856 /* Runs CALLBACK for each operand of STMT that is a memory reference.  DATA
 857    is passed to the CALLBACK as well.  The traversal stops if CALLBACK
 858    returns false, for_each_memref then returns false as well.  Otherwise
 859    for_each_memref returns true.  */
 860
 861 static bool
 862 for_each_memref (tree stmt, bool (*callback)(tree *, void *), void *data)
 863 {
 864   tree *op;
 865
 866   if (TREE_CODE (stmt) == RETURN_EXPR)
 867     stmt = TREE_OPERAND (stmt, 1);
 868
 869   if (TREE_CODE (stmt) == MODIFY_EXPR)
 870     {
 871       op = &TREE_OPERAND (stmt, 0);
 872       if (TREE_CODE (*op) != SSA_NAME
 873           && !callback (op, data))
 874         return false;
 875
 876       op = &TREE_OPERAND (stmt, 1);
 877       if (TREE_CODE (*op) != SSA_NAME
 878           && is_gimple_lvalue (*op)
 879           && !callback (op, data))
 880         return false;
 881
 882       stmt = TREE_OPERAND (stmt, 1);
 883     }
 884
 885   if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
 886     stmt = TREE_OPERAND (stmt, 0);
 887
 888   if (TREE_CODE (stmt) == CALL_EXPR)
 889     {
 890       tree args;
 891
 892       for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
 893         {
 894           op = &TREE_VALUE (args);
 895
 896           if (TREE_CODE (*op) != SSA_NAME
 897               && is_gimple_lvalue (*op)
 898               && !callback (op, data))
 899             return false;
 900         }
 901     }
 902
 903   return true;
 904 }
 905
 906 /* Determine whether all memory references inside the LOOP that correspond
 907    to virtual ssa names defined in statement STMT are equal.
 908    If so, store the list of the references to MEM_REFS, and return one
 909    of them.  Otherwise store NULL to MEM_REFS and return NULL_TREE.
 910    *SEEN_CALL_STMT is set to true if the virtual operands suggest
 911    that the reference might be clobbered by a call inside the LOOP.  */
 912
 913 static tree
 914 single_reachable_address (struct loop *loop, tree stmt,
 915                           struct mem_ref **mem_refs,
 916                           bool *seen_call_stmt)
 917 {
 918   unsigned max_uid = max_stmt_uid + num_ssa_names;
 919   tree *queue = xmalloc (sizeof (tree) * max_uid);
 920   sbitmap seen = sbitmap_alloc (max_uid);
 921   unsigned in_queue = 1;
 922   dataflow_t df;
 923   unsigned i, n;
 924   struct sra_data sra_data;
 925   tree call;
 926   tree val;
 927   ssa_op_iter iter;
 928
 929   sbitmap_zero (seen);
 930
 931   *mem_refs = NULL;
 932   sra_data.mem_refs = mem_refs;
 933   sra_data.common_ref = NULL_TREE;
 934
 935   queue[0] = stmt;
 936   SET_BIT (seen, get_stmt_uid (stmt));
 937   *seen_call_stmt = false;
 938
 939   while (in_queue)
 940     {
 941       stmt = queue[--in_queue];
 942       sra_data.stmt = stmt;
 943
 944       if (LIM_DATA (stmt)
 945           && LIM_DATA (stmt)->sm_done)
 946         goto fail;
 947
 948       switch (TREE_CODE (stmt))
 949         {
 950         case MODIFY_EXPR:
 951         case CALL_EXPR:
 952         case RETURN_EXPR:
 953           if (!for_each_memref (stmt, fem_single_reachable_address,
 954                                 &sra_data))
 955             goto fail;
 956
 957           /* If this is a function that may depend on the memory location,
 958              record the fact.  We cannot directly refuse call clobbered
 959              operands here, since sra_data.common_ref did not have
 960              to be set yet.  */
 961           call = get_call_expr_in (stmt);
 962           if (call
 963               && !(call_expr_flags (call) & ECF_CONST))
 964             *seen_call_stmt = true;
 965
 966           /* Traverse also definitions of the VUSES (there may be other
 967              distinct from the one we used to get to this statement).  */
 968           FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
 969             maybe_queue_var (val, loop, seen, queue, &in_queue);
 970
 971           break;
 972
 973         case PHI_NODE:
 974           for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
 975             maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
 976                              seen, queue, &in_queue);
 977           break;
 978
 979         default:
 980           goto fail;
 981         }
 982
 983       /* Find uses of virtual names.  */
 984       df = get_immediate_uses (stmt);
 985       n = num_immediate_uses (df);
 986
 987       for (i = 0; i < n; i++)
 988         {
 989           stmt = immediate_use (df, i);
 990
 991           if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
 992             continue;
 993
 994           if (TEST_BIT (seen, get_stmt_uid (stmt)))
 995             continue;
 996           SET_BIT (seen, get_stmt_uid (stmt));
 997
 998           queue[in_queue++] = stmt;
 999         }
1000     }
1001
1002   free (queue);
1003   sbitmap_free (seen);
1004
1005   return sra_data.common_ref;
1006
1007 fail:
1008   free_mem_refs (*mem_refs);
1009   *mem_refs = NULL;
1010   free (queue);
1011   sbitmap_free (seen);
1012
1013   return NULL;
1014 }
1015
1016 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
1017
1018 static void
1019 rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
1020 {
1021   tree var;
1022   ssa_op_iter iter;
1023
1024   for (; mem_refs; mem_refs = mem_refs->next)
1025     {
1026       FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter,
1027                                  (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE))
1028         {
1029           var = SSA_NAME_VAR (var);
1030           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1031         }
1032
1033       *mem_refs->ref = tmp_var;
1034       modify_stmt (mem_refs->stmt);
1035     }
1036 }
1037
1038 /* Records request for store motion of memory reference REF from LOOP.
1039    MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1040    these references are rewritten by a new temporary variable.
1041    Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1042    The initialization of the temporary variable is put to the preheader
1043    of the loop, and assignments to the reference from the temporary variable
1044    are emitted to exits.  */
1045
1046 static void
1047 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
1048              struct mem_ref *mem_refs)
1049 {
1050   struct mem_ref *aref;
1051   tree tmp_var;
1052   unsigned i;
1053   tree load, store;
1054   struct fmt_data fmt_data;
1055
1056   if (dump_file && (dump_flags & TDF_DETAILS))
1057     {
1058       fprintf (dump_file, "Executing store motion of ");
1059       print_generic_expr (dump_file, ref, 0);
1060       fprintf (dump_file, " from loop %d\n", loop->num);
1061     }
1062
1063   tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
1064
1065   fmt_data.loop = loop;
1066   fmt_data.orig_loop = loop;
1067   for_each_index (&ref, force_move_till, &fmt_data);
1068
1069   rewrite_mem_refs (tmp_var, mem_refs);
1070   for (aref = mem_refs; aref; aref = aref->next)
1071     if (LIM_DATA (aref->stmt))
1072       LIM_DATA (aref->stmt)->sm_done = true;
1073
1074   /* Emit the load & stores.  */
1075   load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
1076   get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1077   LIM_DATA (load)->max_loop = loop;
1078   LIM_DATA (load)->tgt_loop = loop;
1079
1080   /* Put this into the latch, so that we are sure it will be processed after
1081      all dependencies.  */
1082   bsi_insert_on_edge (loop_latch_edge (loop), load);
1083
1084   for (i = 0; i < n_exits; i++)
1085     {
1086       store = build (MODIFY_EXPR, void_type_node,
1087                      unshare_expr (ref), tmp_var);
1088       bsi_insert_on_edge (exits[i], store);
1089     }
1090 }
1091
1092 /* Returns true if REF may be clobbered by calls.  */
1093
1094 static bool
1095 is_call_clobbered_ref (tree ref)
1096 {
1097   tree base;
1098
1099   base = get_base_address (ref);
1100   if (!base)
1101     return true;
1102
1103   if (DECL_P (base))
1104     return is_call_clobbered (base);
1105
1106   if (TREE_CODE (base) == INDIRECT_REF
1107       || TREE_CODE (base) == ALIGN_INDIRECT_REF
1108       || TREE_CODE (base) == MISALIGNED_INDIRECT_REF)
1109     {
1110       /* Check whether the alias tags associated with the pointer
1111          are call clobbered.  */
1112       tree ptr = TREE_OPERAND (base, 0);
1113       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1114       tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
1115       tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
1116
1117       if ((nmt && is_call_clobbered (nmt))
1118           || (tmt && is_call_clobbered (tmt)))
1119         return true;
1120
1121       return false;
1122     }
1123
1124   gcc_unreachable ();
1125 }
1126
1127 /* Determine whether all memory references inside LOOP corresponding to the
1128    virtual ssa name REG are equal to each other, and whether the address of
1129    this common reference can be hoisted outside of the loop.  If this is true,
1130    prepare the statements that load the value of the memory reference to a
1131    temporary variable in the loop preheader, store it back on the loop exits,
1132    and replace all the references inside LOOP by this temporary variable.
1133    LOOP has N_EXITS stored in EXITS.  */
1134
1135 static void
1136 determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
1137 {
1138   tree ref;
1139   struct mem_ref *mem_refs, *aref;
1140   struct loop *must_exec;
1141   bool sees_call;
1142
1143   if (is_gimple_reg (reg))
1144     return;
1145
1146   ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs,
1147                                   &sees_call);
1148   if (!ref)
1149     return;
1150
1151   /* If we cannot create a ssa name for the result, give up.  */
1152   if (!is_gimple_reg_type (TREE_TYPE (ref))
1153       || TREE_THIS_VOLATILE (ref))
1154     goto fail;
1155
1156   /* If there is a call that may use the location, give up as well.  */
1157   if (sees_call
1158       && is_call_clobbered_ref (ref))
1159     goto fail;
1160
1161   if (!for_each_index (&ref, may_move_till, loop))
1162     goto fail;
1163
1164   if (tree_could_trap_p (ref))
1165     {
1166       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1167          of the statements in that it occurs is always executed when the loop
1168          is entered.  This way we know that by moving the load from the
1169          reference out of the loop we will not cause the error that would not
1170          occur otherwise.
1171
1172          TODO -- in fact we would like to check for anticipability of the
1173          reference, i.e. that on each path from loop entry to loop exit at
1174          least one of the statements containing the memory reference is
1175          executed.  */
1176
1177       for (aref = mem_refs; aref; aref = aref->next)
1178         {
1179           if (!LIM_DATA (aref->stmt))
1180             continue;
1181
1182           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1183           if (!must_exec)
1184             continue;
1185
1186           if (must_exec == loop
1187               || flow_loop_nested_p (must_exec, loop))
1188             break;
1189         }
1190
1191       if (!aref)
1192         goto fail;
1193     }
1194
1195   schedule_sm (loop, exits, n_exits, ref, mem_refs);
1196
1197 fail: ;
1198   free_mem_refs (mem_refs);
1199 }
1200
1201 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1202    for a store motion optimization (i.e. whether we can insert statement
1203    on its exits).  */
1204
1205 static bool
1206 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1207                       unsigned n_exits)
1208 {
1209   unsigned i;
1210
1211   for (i = 0; i < n_exits; i++)
1212     if (exits[i]->flags & EDGE_ABNORMAL)
1213       return false;
1214
1215   return true;
1216 }
1217
1218 /* Try to perform store motion for all memory references modified inside
1219    LOOP.  */
1220
1221 static void
1222 determine_lsm_loop (struct loop *loop)
1223 {
1224   tree phi;
1225   unsigned n_exits;
1226   edge *exits = get_loop_exit_edges (loop, &n_exits);
1227
1228   if (!loop_suitable_for_sm (loop, exits, n_exits))
1229     {
1230       free (exits);
1231       return;
1232     }
1233
1234   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
1235     determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
1236
1237   free (exits);
1238 }
1239
1240 /* Try to perform store motion for all memory references modified inside
1241    any of LOOPS.  */
1242
1243 static void
1244 determine_lsm (struct loops *loops)
1245 {
1246   struct loop *loop;
1247   basic_block bb;
1248
1249   /* Create a UID for each statement in the function.  Ordering of the
1250      UIDs is not important for this pass.  */
1251   max_stmt_uid = 0;
1252   FOR_EACH_BB (bb)
1253     {
1254       block_stmt_iterator bsi;
1255
1256       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1257         stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
1258     }
1259
1260   compute_immediate_uses (TDFA_USE_VOPS, NULL);
1261
1262   /* Pass the loops from the outermost.  For each virtual operand loop phi node
1263      check whether all the references inside the loop correspond to a single
1264      address, and if so, move them.  */
1265
1266   loop = loops->tree_root->inner;
1267   while (1)
1268     {
1269       determine_lsm_loop (loop);
1270
1271       if (loop->inner)
1272         {
1273           loop = loop->inner;
1274           continue;
1275         }
1276       while (!loop->next)
1277         {
1278           loop = loop->outer;
1279           if (loop == loops->tree_root)
1280             {
1281               free_df ();
1282               loop_commit_inserts ();
1283               return;
1284             }
1285         }
1286       loop = loop->next;
1287     }
1288 }
1289
1290 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1291    for each such basic block bb records the outermost loop for that execution
1292    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1293    blocks that contain a nonpure call.  */
1294
1295 static void
1296 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1297 {
1298   basic_block bb = NULL, *bbs, last = NULL;
1299   unsigned i;
1300   edge e;
1301   struct loop *inn_loop = loop;
1302
1303   if (!loop->header->aux)
1304     {
1305       bbs = get_loop_body_in_dom_order (loop);
1306
1307       for (i = 0; i < loop->num_nodes; i++)
1308         {
1309           bb = bbs[i];
1310
1311           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1312             last = bb;
1313
1314           if (TEST_BIT (contains_call, bb->index))
1315             break;
1316
1317           for (e = bb->succ; e; e = e->succ_next)
1318             if (!flow_bb_inside_loop_p (loop, e->dest))
1319               break;
1320           if (e)
1321             break;
1322
1323           /* A loop might be infinite (TODO use simple loop analysis
1324              to disprove this if possible).  */
1325           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1326             break;
1327
1328           if (!flow_bb_inside_loop_p (inn_loop, bb))
1329             break;
1330
1331           if (bb->loop_father->header == bb)
1332             {
1333               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1334                 break;
1335
1336               /* In a loop that is always entered we may proceed anyway.
1337                  But record that we entered it and stop once we leave it.  */
1338               inn_loop = bb->loop_father;
1339             }
1340         }
1341
1342       while (1)
1343         {
1344           last->aux = loop;
1345           if (last == loop->header)
1346             break;
1347           last = get_immediate_dominator (CDI_DOMINATORS, last);
1348         }
1349
1350       free (bbs);
1351     }
1352
1353   for (loop = loop->inner; loop; loop = loop->next)
1354     fill_always_executed_in (loop, contains_call);
1355 }
1356
1357 /* Compute the global information needed by the loop invariant motion pass.
1358    LOOPS is the loop tree.  */
1359
1360 static void
1361 tree_ssa_lim_initialize (struct loops *loops)
1362 {
1363   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1364   block_stmt_iterator bsi;
1365   struct loop *loop;
1366   basic_block bb;
1367
1368   sbitmap_zero (contains_call);
1369   FOR_EACH_BB (bb)
1370     {
1371       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1372         {
1373           if (nonpure_call_p (bsi_stmt (bsi)))
1374             break;
1375         }
1376
1377       if (!bsi_end_p (bsi))
1378         SET_BIT (contains_call, bb->index);
1379     }
1380
1381   for (loop = loops->tree_root->inner; loop; loop = loop->next)
1382     fill_always_executed_in (loop, contains_call);
1383
1384   sbitmap_free (contains_call);
1385 }
1386
1387 /* Cleans up after the invariant motion pass.  */
1388
1389 static void
1390 tree_ssa_lim_finalize (void)
1391 {
1392   basic_block bb;
1393
1394   FOR_EACH_BB (bb)
1395     {
1396       bb->aux = NULL;
1397     }
1398 }
1399
1400 /* Moves invariants from LOOPS.  Only "expensive" invariants are moved out --
1401    i.e. those that are likely to be win regardless of the register pressure.  */
1402
1403 void
1404 tree_ssa_lim (struct loops *loops)
1405 {
1406   tree_ssa_lim_initialize (loops);
1407
1408   /* For each statement determine the outermost loop in that it is
1409      invariant and cost for computing the invariant.  */
1410   determine_invariantness ();
1411
1412   /* For each memory reference determine whether it is possible to hoist it
1413      out of the loop.  Force the necessary invariants to be moved out of the
1414      loops as well.  */
1415   determine_lsm (loops);
1416
1417   /* Move the expressions that are expensive enough.  */
1418   move_computations ();
1419
1420   tree_ssa_lim_finalize ();
1421 }