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