gcc/tree-ssa-loop-im.c

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