gcc/tree-ssa-loop-im.c

   1 /* Loop invariant motion.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, 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 #include "real.h"
  41 #include "hashtab.h"
  42
  43 /* TODO:  Support for predicated code motion.  I.e.
  44
  45    while (1)
  46      {
  47        if (cond)
  48          {
  49            a = inv;
  50            something;
  51          }
  52      }
  53
  54    Where COND and INV are is invariants, but evaluating INV may trap or be
  55    invalid from some other reason if !COND.  This may be transformed to
  56
  57    if (cond)
  58      a = inv;
  59    while (1)
  60      {
  61        if (cond)
  62          something;
  63      }  */
  64
  65 /* A type for the list of statements that have to be moved in order to be able
  66    to hoist an invariant computation.  */
  67
  68 struct depend
  69 {
  70   tree stmt;
  71   struct depend *next;
  72 };
  73
  74 /* The auxiliary data kept for each statement.  */
  75
  76 struct lim_aux_data
  77 {
  78   struct loop *max_loop;        /* The outermost loop in that the statement
  79                                    is invariant.  */
  80
  81   struct loop *tgt_loop;        /* The loop out of that we want to move the
  82                                    invariant.  */
  83
  84   struct loop *always_executed_in;
  85                                 /* The outermost loop for that we are sure
  86                                    the statement is executed if the loop
  87                                    is entered.  */
  88
  89   bool sm_done;                 /* True iff the store motion for a memory
  90                                    reference in the statement has already
  91                                    been executed.  */
  92
  93   unsigned cost;                /* Cost of the computation performed by the
  94                                    statement.  */
  95
  96   struct depend *depends;       /* List of statements that must be also hoisted
  97                                    out of the loop when this statement is
  98                                    hoisted; i.e. those that define the operands
  99                                    of the statement and are inside of the
 100                                    MAX_LOOP loop.  */
 101 };
 102
 103 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
 104                         ? NULL \
 105                         : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
 106
 107 /* Description of a memory reference location for store motion.  */
 108
 109 struct mem_ref_loc
 110 {
 111   tree *ref;                    /* The reference itself.  */
 112   tree stmt;                    /* The statement in that it occurs.  */
 113   struct mem_ref_loc *next;     /* Next use in the chain.  */
 114 };
 115
 116 /* Description of a memory reference for store motion.  */
 117
 118 struct mem_ref
 119 {
 120   tree mem;                     /* The memory itself.  */
 121   hashval_t hash;               /* Its hash value.  */
 122   bool is_stored;               /* True if there is a store to the location
 123                                    in the loop.  */
 124   struct mem_ref_loc *locs;     /* The locations where it is found.  */
 125   bitmap vops;                  /* Vops corresponding to this memory
 126                                    location.  */
 127   struct mem_ref *next;         /* Next memory reference in the list.
 128                                    Memory references are stored in a hash
 129                                    table, but the hash function depends
 130                                    on values of pointers. Thus we cannot use
 131                                    htab_traverse, since then we would get
 132                                    miscompares during bootstrap (although the
 133                                    produced code would be correct).  */
 134 };
 135
 136 /* Minimum cost of an expensive expression.  */
 137 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
 138
 139 /* The outermost loop for that execution of the header guarantees that the
 140    block will be executed.  */
 141 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
 142
 143 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 144    kinds situations handled; in each of these cases, the memory reference
 145    and DATA are passed to the callback:
 146
 147    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 148    pass the pointer to the index to the callback.
 149
 150    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 151    pointer to addr to the callback.
 152
 153    If the callback returns false, the whole search stops and false is returned.
 154    Otherwise the function returns true after traversing through the whole
 155    reference *ADDR_P.  */
 156
 157 bool
 158 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 159 {
 160   tree *nxt, *idx;
 161
 162   for (; ; addr_p = nxt)
 163     {
 164       switch (TREE_CODE (*addr_p))
 165         {
 166         case SSA_NAME:
 167           return cbck (*addr_p, addr_p, data);
 168
 169         case MISALIGNED_INDIRECT_REF:
 170         case ALIGN_INDIRECT_REF:
 171         case INDIRECT_REF:
 172           nxt = &TREE_OPERAND (*addr_p, 0);
 173           return cbck (*addr_p, nxt, data);
 174
 175         case BIT_FIELD_REF:
 176         case VIEW_CONVERT_EXPR:
 177         case REALPART_EXPR:
 178         case IMAGPART_EXPR:
 179           nxt = &TREE_OPERAND (*addr_p, 0);
 180           break;
 181
 182         case COMPONENT_REF:
 183           /* If the component has varying offset, it behaves like index
 184              as well.  */
 185           idx = &TREE_OPERAND (*addr_p, 2);
 186           if (*idx
 187               && !cbck (*addr_p, idx, data))
 188             return false;
 189
 190           nxt = &TREE_OPERAND (*addr_p, 0);
 191           break;
 192
 193         case ARRAY_REF:
 194         case ARRAY_RANGE_REF:
 195           nxt = &TREE_OPERAND (*addr_p, 0);
 196           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 197             return false;
 198           break;
 199
 200         case VAR_DECL:
 201         case PARM_DECL:
 202         case STRING_CST:
 203         case RESULT_DECL:
 204         case VECTOR_CST:
 205         case COMPLEX_CST:
 206         case INTEGER_CST:
 207         case REAL_CST:
 208           return true;
 209
 210         case TARGET_MEM_REF:
 211           idx = &TMR_BASE (*addr_p);
 212           if (*idx
 213               && !cbck (*addr_p, idx, data))
 214             return false;
 215           idx = &TMR_INDEX (*addr_p);
 216           if (*idx
 217               && !cbck (*addr_p, idx, data))
 218             return false;
 219           return true;
 220
 221         default:
 222           gcc_unreachable ();
 223         }
 224     }
 225 }
 226
 227 /* If it is possible to hoist the statement STMT unconditionally,
 228    returns MOVE_POSSIBLE.
 229    If it is possible to hoist the statement STMT, but we must avoid making
 230    it executed if it would not be executed in the original program (e.g.
 231    because it may trap), return MOVE_PRESERVE_EXECUTION.
 232    Otherwise return MOVE_IMPOSSIBLE.  */
 233
 234 enum move_pos
 235 movement_possibility (tree stmt)
 236 {
 237   tree lhs, rhs;
 238
 239   if (flag_unswitch_loops
 240       && TREE_CODE (stmt) == COND_EXPR)
 241     {
 242       /* If we perform unswitching, force the operands of the invariant
 243          condition to be moved out of the loop.  */
 244       return MOVE_POSSIBLE;
 245     }
 246
 247   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 248     return MOVE_IMPOSSIBLE;
 249
 250   if (stmt_ends_bb_p (stmt))
 251     return MOVE_IMPOSSIBLE;
 252
 253   if (stmt_ann (stmt)->has_volatile_ops)
 254     return MOVE_IMPOSSIBLE;
 255
 256   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 257   if (TREE_CODE (lhs) == SSA_NAME
 258       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 259     return MOVE_IMPOSSIBLE;
 260
 261   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 262
 263   if (TREE_SIDE_EFFECTS (rhs))
 264     return MOVE_IMPOSSIBLE;
 265
 266   if (TREE_CODE (lhs) != SSA_NAME
 267       || tree_could_trap_p (rhs))
 268     return MOVE_PRESERVE_EXECUTION;
 269
 270   if (get_call_expr_in (stmt))
 271     {
 272       /* While pure or const call is guaranteed to have no side effects, we
 273          cannot move it arbitrarily.  Consider code like
 274
 275          char *s = something ();
 276
 277          while (1)
 278            {
 279              if (s)
 280                t = strlen (s);
 281              else
 282                t = 0;
 283            }
 284
 285          Here the strlen call cannot be moved out of the loop, even though
 286          s is invariant.  In addition to possibly creating a call with
 287          invalid arguments, moving out a function call that is not executed
 288          may cause performance regressions in case the call is costly and
 289          not executed at all.  */
 290       return MOVE_PRESERVE_EXECUTION;
 291     }
 292   return MOVE_POSSIBLE;
 293 }
 294
 295 /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
 296    loop to that we could move the expression using DEF if it did not have
 297    other operands, i.e. the outermost loop enclosing LOOP in that the value
 298    of DEF is invariant.  */
 299
 300 static struct loop *
 301 outermost_invariant_loop (tree def, struct loop *loop)
 302 {
 303   tree def_stmt;
 304   basic_block def_bb;
 305   struct loop *max_loop;
 306
 307   if (TREE_CODE (def) != SSA_NAME)
 308     return superloop_at_depth (loop, 1);
 309
 310   def_stmt = SSA_NAME_DEF_STMT (def);
 311   def_bb = bb_for_stmt (def_stmt);
 312   if (!def_bb)
 313     return superloop_at_depth (loop, 1);
 314
 315   max_loop = find_common_loop (loop, def_bb->loop_father);
 316
 317   if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
 318     max_loop = find_common_loop (max_loop,
 319                                  LIM_DATA (def_stmt)->max_loop->outer);
 320   if (max_loop == loop)
 321     return NULL;
 322   max_loop = superloop_at_depth (loop, max_loop->depth + 1);
 323
 324   return max_loop;
 325 }
 326
 327 /* Returns the outermost superloop of LOOP in that the expression EXPR is
 328    invariant.  */
 329
 330 static struct loop *
 331 outermost_invariant_loop_expr (tree expr, struct loop *loop)
 332 {
 333   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
 334   unsigned i, nops;
 335   struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
 336
 337   if (TREE_CODE (expr) == SSA_NAME
 338       || TREE_CODE (expr) == INTEGER_CST
 339       || is_gimple_min_invariant (expr))
 340     return outermost_invariant_loop (expr, loop);
 341
 342   if (class != tcc_unary
 343       && class != tcc_binary
 344       && class != tcc_expression
 345       && class != tcc_vl_exp
 346       && class != tcc_comparison)
 347     return NULL;
 348
 349   nops = TREE_OPERAND_LENGTH (expr);
 350   for (i = 0; i < nops; i++)
 351     {
 352       aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
 353       if (!aloop)
 354         return NULL;
 355
 356       if (flow_loop_nested_p (max_loop, aloop))
 357         max_loop = aloop;
 358     }
 359
 360   return max_loop;
 361 }
 362
 363 /* DATA is a structure containing information associated with a statement
 364    inside LOOP.  DEF is one of the operands of this statement.
 365
 366    Find the outermost loop enclosing LOOP in that value of DEF is invariant
 367    and record this in DATA->max_loop field.  If DEF itself is defined inside
 368    this loop as well (i.e. we need to hoist it out of the loop if we want
 369    to hoist the statement represented by DATA), record the statement in that
 370    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
 371    add the cost of the computation of DEF to the DATA->cost.
 372
 373    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
 374
 375 static bool
 376 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
 377                 bool add_cost)
 378 {
 379   tree def_stmt = SSA_NAME_DEF_STMT (def);
 380   basic_block def_bb = bb_for_stmt (def_stmt);
 381   struct loop *max_loop;
 382   struct depend *dep;
 383
 384   if (!def_bb)
 385     return true;
 386
 387   max_loop = outermost_invariant_loop (def, loop);
 388   if (!max_loop)
 389     return false;
 390
 391   if (flow_loop_nested_p (data->max_loop, max_loop))
 392     data->max_loop = max_loop;
 393
 394   if (!LIM_DATA (def_stmt))
 395     return true;
 396
 397   if (add_cost
 398       /* Only add the cost if the statement defining DEF is inside LOOP,
 399          i.e. if it is likely that by moving the invariants dependent
 400          on it, we will be able to avoid creating a new register for
 401          it (since it will be only used in these dependent invariants).  */
 402       && def_bb->loop_father == loop)
 403     data->cost += LIM_DATA (def_stmt)->cost;
 404
 405   dep = XNEW (struct depend);
 406   dep->stmt = def_stmt;
 407   dep->next = data->depends;
 408   data->depends = dep;
 409
 410   return true;
 411 }
 412
 413 /* Returns an estimate for a cost of statement STMT.  TODO -- the values here
 414    are just ad-hoc constants.  The estimates should be based on target-specific
 415    values.  */
 416
 417 static unsigned
 418 stmt_cost (tree stmt)
 419 {
 420   tree rhs;
 421   unsigned cost = 1;
 422
 423   /* Always try to create possibilities for unswitching.  */
 424   if (TREE_CODE (stmt) == COND_EXPR)
 425     return LIM_EXPENSIVE;
 426
 427   rhs = GENERIC_TREE_OPERAND (stmt, 1);
 428
 429   /* Hoisting memory references out should almost surely be a win.  */
 430   if (stmt_references_memory_p (stmt))
 431     cost += 20;
 432
 433   switch (TREE_CODE (rhs))
 434     {
 435     case CALL_EXPR:
 436       /* We should be hoisting calls if possible.  */
 437
 438       /* Unless the call is a builtin_constant_p; this always folds to a
 439          constant, so moving it is useless.  */
 440       rhs = get_callee_fndecl (rhs);
 441       if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
 442           && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
 443         return 0;
 444
 445       cost += 20;
 446       break;
 447
 448     case MULT_EXPR:
 449     case TRUNC_DIV_EXPR:
 450     case CEIL_DIV_EXPR:
 451     case FLOOR_DIV_EXPR:
 452     case ROUND_DIV_EXPR:
 453     case EXACT_DIV_EXPR:
 454     case CEIL_MOD_EXPR:
 455     case FLOOR_MOD_EXPR:
 456     case ROUND_MOD_EXPR:
 457     case TRUNC_MOD_EXPR:
 458     case RDIV_EXPR:
 459       /* Division and multiplication are usually expensive.  */
 460       cost += 20;
 461       break;
 462
 463     default:
 464       break;
 465     }
 466
 467   return cost;
 468 }
 469
 470 /* Determine the outermost loop to that it is possible to hoist a statement
 471    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 472    the outermost loop in that the value computed by STMT is invariant.
 473    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 474    we preserve the fact whether STMT is executed.  It also fills other related
 475    information to LIM_DATA (STMT).
 476
 477    The function returns false if STMT cannot be hoisted outside of the loop it
 478    is defined in, and true otherwise.  */
 479
 480 static bool
 481 determine_max_movement (tree stmt, bool must_preserve_exec)
 482 {
 483   basic_block bb = bb_for_stmt (stmt);
 484   struct loop *loop = bb->loop_father;
 485   struct loop *level;
 486   struct lim_aux_data *lim_data = LIM_DATA (stmt);
 487   tree val;
 488   ssa_op_iter iter;
 489
 490   if (must_preserve_exec)
 491     level = ALWAYS_EXECUTED_IN (bb);
 492   else
 493     level = superloop_at_depth (loop, 1);
 494   lim_data->max_loop = level;
 495
 496   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
 497     if (!add_dependency (val, lim_data, loop, true))
 498       return false;
 499
 500   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
 501     if (!add_dependency (val, lim_data, loop, false))
 502       return false;
 503
 504   lim_data->cost += stmt_cost (stmt);
 505
 506   return true;
 507 }
 508
 509 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
 510    and that one of the operands of this statement is computed by STMT.
 511    Ensure that STMT (together with all the statements that define its
 512    operands) is hoisted at least out of the loop LEVEL.  */
 513
 514 static void
 515 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
 516 {
 517   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
 518   struct depend *dep;
 519
 520   stmt_loop = find_common_loop (orig_loop, stmt_loop);
 521   if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
 522     stmt_loop = find_common_loop (stmt_loop,
 523                                   LIM_DATA (stmt)->tgt_loop->outer);
 524   if (flow_loop_nested_p (stmt_loop, level))
 525     return;
 526
 527   gcc_assert (LIM_DATA (stmt));
 528   gcc_assert (level == LIM_DATA (stmt)->max_loop
 529               || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
 530
 531   LIM_DATA (stmt)->tgt_loop = level;
 532   for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
 533     set_level (dep->stmt, orig_loop, level);
 534 }
 535
 536 /* Determines an outermost loop from that we want to hoist the statement STMT.
 537    For now we chose the outermost possible loop.  TODO -- use profiling
 538    information to set it more sanely.  */
 539
 540 static void
 541 set_profitable_level (tree stmt)
 542 {
 543   set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
 544 }
 545
 546 /* Returns true if STMT is not a pure call.  */
 547
 548 static bool
 549 nonpure_call_p (tree stmt)
 550 {
 551   tree call = get_call_expr_in (stmt);
 552
 553   if (!call)
 554     return false;
 555
 556   return TREE_SIDE_EFFECTS (call) != 0;
 557 }
 558
 559 /* Releases the memory occupied by DATA.  */
 560
 561 static void
 562 free_lim_aux_data (struct lim_aux_data *data)
 563 {
 564   struct depend *dep, *next;
 565
 566   for (dep = data->depends; dep; dep = next)
 567     {
 568       next = dep->next;
 569       free (dep);
 570     }
 571   free (data);
 572 }
 573
 574 /* Determine the outermost loops in that statements in basic block BB are
 575    invariant, and record them to the LIM_DATA associated with the statements.
 576    Callback for walk_dominator_tree.  */
 577
 578 static void
 579 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 580                               basic_block bb)
 581 {
 582   enum move_pos pos;
 583   block_stmt_iterator bsi;
 584   tree stmt, rhs;
 585   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
 586   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
 587
 588   if (!bb->loop_father->outer)
 589     return;
 590
 591   if (dump_file && (dump_flags & TDF_DETAILS))
 592     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 593              bb->index, bb->loop_father->num, bb->loop_father->depth);
 594
 595   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 596     {
 597       stmt = bsi_stmt (bsi);
 598
 599       pos = movement_possibility (stmt);
 600       if (pos == MOVE_IMPOSSIBLE)
 601         {
 602           if (nonpure_call_p (stmt))
 603             {
 604               maybe_never = true;
 605               outermost = NULL;
 606             }
 607           continue;
 608         }
 609
 610       /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
 611          to be hoisted out of loop, saving expensive divide.  */
 612       if (pos == MOVE_POSSIBLE
 613           && (rhs = GENERIC_TREE_OPERAND (stmt, 1)) != NULL
 614           && TREE_CODE (rhs) == RDIV_EXPR
 615           && flag_unsafe_math_optimizations
 616           && !flag_trapping_math
 617           && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
 618                                             loop_containing_stmt (stmt)) != NULL
 619           && outermost_invariant_loop_expr (rhs,
 620                                             loop_containing_stmt (stmt)) == NULL)
 621         {
 622           tree lhs, stmt1, stmt2, var, name, tmp;
 623
 624           lhs = GENERIC_TREE_OPERAND (stmt, 0);
 625
 626           /* stmt must be GIMPLE_MODIFY_STMT.  */
 627           var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
 628           add_referenced_var (var);
 629
 630           tmp = build2 (RDIV_EXPR, TREE_TYPE (rhs),
 631                         build_real (TREE_TYPE (rhs), dconst1),
 632                         TREE_OPERAND (rhs, 1));
 633           stmt1 = build_gimple_modify_stmt (var, tmp);
 634           name = make_ssa_name (var, stmt1);
 635           GIMPLE_STMT_OPERAND (stmt1, 0) = name;
 636           tmp = build2 (MULT_EXPR, TREE_TYPE (rhs),
 637                         name, TREE_OPERAND (rhs, 0));
 638           stmt2 = build_gimple_modify_stmt (lhs, tmp);
 639
 640           /* Replace division stmt with reciprocal and multiply stmts.
 641              The multiply stmt is not invariant, so update iterator
 642              and avoid rescanning.  */
 643           bsi_replace (&bsi, stmt1, true);
 644           bsi_insert_after (&bsi, stmt2, BSI_NEW_STMT);
 645           SSA_NAME_DEF_STMT (lhs) = stmt2;
 646
 647           /* Continue processing with invariant reciprocal statement.  */
 648           stmt = stmt1;
 649         }
 650
 651       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
 652       LIM_DATA (stmt)->always_executed_in = outermost;
 653
 654       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
 655         continue;
 656
 657       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
 658         {
 659           LIM_DATA (stmt)->max_loop = NULL;
 660           continue;
 661         }
 662
 663       if (dump_file && (dump_flags & TDF_DETAILS))
 664         {
 665           print_generic_stmt_indented (dump_file, stmt, 0, 2);
 666           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
 667                    LIM_DATA (stmt)->max_loop->depth,
 668                    LIM_DATA (stmt)->cost);
 669         }
 670
 671       if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
 672         set_profitable_level (stmt);
 673     }
 674 }
 675
 676 /* For each statement determines the outermost loop in that it is invariant,
 677    statements on whose motion it depends and the cost of the computation.
 678    This information is stored to the LIM_DATA structure associated with
 679    each statement.  */
 680
 681 static void
 682 determine_invariantness (void)
 683 {
 684   struct dom_walk_data walk_data;
 685
 686   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 687   walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
 688
 689   init_walk_dominator_tree (&walk_data);
 690   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 691   fini_walk_dominator_tree (&walk_data);
 692 }
 693
 694 /* Hoist the statements in basic block BB out of the loops prescribed by
 695    data stored in LIM_DATA structures associated with each statement.  Callback
 696    for walk_dominator_tree.  */
 697
 698 static void
 699 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 700                         basic_block bb)
 701 {
 702   struct loop *level;
 703   block_stmt_iterator bsi;
 704   tree stmt;
 705   unsigned cost = 0;
 706
 707   if (!bb->loop_father->outer)
 708     return;
 709
 710   for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 711     {
 712       stmt = bsi_stmt (bsi);
 713
 714       if (!LIM_DATA (stmt))
 715         {
 716           bsi_next (&bsi);
 717           continue;
 718         }
 719
 720       cost = LIM_DATA (stmt)->cost;
 721       level = LIM_DATA (stmt)->tgt_loop;
 722       free_lim_aux_data (LIM_DATA (stmt));
 723       stmt_ann (stmt)->common.aux = NULL;
 724
 725       if (!level)
 726         {
 727           bsi_next (&bsi);
 728           continue;
 729         }
 730
 731       /* We do not really want to move conditionals out of the loop; we just
 732          placed it here to force its operands to be moved if necessary.  */
 733       if (TREE_CODE (stmt) == COND_EXPR)
 734         continue;
 735
 736       if (dump_file && (dump_flags & TDF_DETAILS))
 737         {
 738           fprintf (dump_file, "Moving statement\n");
 739           print_generic_stmt (dump_file, stmt, 0);
 740           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
 741                    cost, level->num);
 742         }
 743       bsi_insert_on_edge (loop_preheader_edge (level), stmt);
 744       bsi_remove (&bsi, false);
 745     }
 746 }
 747
 748 /* Hoist the statements out of the loops prescribed by data stored in
 749    LIM_DATA structures associated with each statement.*/
 750
 751 static void
 752 move_computations (void)
 753 {
 754   struct dom_walk_data walk_data;
 755
 756   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 757   walk_data.before_dom_children_before_stmts = move_computations_stmt;
 758
 759   init_walk_dominator_tree (&walk_data);
 760   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 761   fini_walk_dominator_tree (&walk_data);
 762
 763   bsi_commit_edge_inserts ();
 764   if (need_ssa_update_p ())
 765     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 766 }
 767
 768 /* Checks whether the statement defining variable *INDEX can be hoisted
 769    out of the loop passed in DATA.  Callback for for_each_index.  */
 770
 771 static bool
 772 may_move_till (tree ref, tree *index, void *data)
 773 {
 774   struct loop *loop = data, *max_loop;
 775
 776   /* If REF is an array reference, check also that the step and the lower
 777      bound is invariant in LOOP.  */
 778   if (TREE_CODE (ref) == ARRAY_REF)
 779     {
 780       tree step = array_ref_element_size (ref);
 781       tree lbound = array_ref_low_bound (ref);
 782
 783       max_loop = outermost_invariant_loop_expr (step, loop);
 784       if (!max_loop)
 785         return false;
 786
 787       max_loop = outermost_invariant_loop_expr (lbound, loop);
 788       if (!max_loop)
 789         return false;
 790     }
 791
 792   max_loop = outermost_invariant_loop (*index, loop);
 793   if (!max_loop)
 794     return false;
 795
 796   return true;
 797 }
 798
 799 /* Forces statements defining (invariant) SSA names in expression EXPR to be
 800    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
 801
 802 static void
 803 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
 804 {
 805   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
 806   unsigned i, nops;
 807
 808   if (TREE_CODE (expr) == SSA_NAME)
 809     {
 810       tree stmt = SSA_NAME_DEF_STMT (expr);
 811       if (IS_EMPTY_STMT (stmt))
 812         return;
 813
 814       set_level (stmt, orig_loop, loop);
 815       return;
 816     }
 817
 818   if (class != tcc_unary
 819       && class != tcc_binary
 820       && class != tcc_expression
 821       && class != tcc_vl_exp
 822       && class != tcc_comparison)
 823     return;
 824
 825   nops = TREE_OPERAND_LENGTH (expr);
 826   for (i = 0; i < nops; i++)
 827     force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
 828 }
 829
 830 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 831    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
 832    for_each_index.  */
 833
 834 struct fmt_data
 835 {
 836   struct loop *loop;
 837   struct loop *orig_loop;
 838 };
 839
 840 static bool
 841 force_move_till (tree ref, tree *index, void *data)
 842 {
 843   tree stmt;
 844   struct fmt_data *fmt_data = data;
 845
 846   if (TREE_CODE (ref) == ARRAY_REF)
 847     {
 848       tree step = array_ref_element_size (ref);
 849       tree lbound = array_ref_low_bound (ref);
 850
 851       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
 852       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
 853     }
 854
 855   if (TREE_CODE (*index) != SSA_NAME)
 856     return true;
 857
 858   stmt = SSA_NAME_DEF_STMT (*index);
 859   if (IS_EMPTY_STMT (stmt))
 860     return true;
 861
 862   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
 863
 864   return true;
 865 }
 866
 867 /* Records memory reference location *REF to the list MEM_REFS.  The reference
 868    occurs in statement STMT.  */
 869
 870 static void
 871 record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref)
 872 {
 873   struct mem_ref_loc *aref = XNEW (struct mem_ref_loc);
 874
 875   aref->stmt = stmt;
 876   aref->ref = ref;
 877
 878   aref->next = *mem_refs;
 879   *mem_refs = aref;
 880 }
 881
 882 /* Releases list of memory reference locations MEM_REFS.  */
 883
 884 static void
 885 free_mem_ref_locs (struct mem_ref_loc *mem_refs)
 886 {
 887   struct mem_ref_loc *act;
 888
 889   while (mem_refs)
 890     {
 891       act = mem_refs;
 892       mem_refs = mem_refs->next;
 893       free (act);
 894     }
 895 }
 896
 897 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
 898
 899 static void
 900 rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs)
 901 {
 902   tree var;
 903   ssa_op_iter iter;
 904
 905   for (; mem_refs; mem_refs = mem_refs->next)
 906     {
 907       FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
 908         mark_sym_for_renaming (SSA_NAME_VAR (var));
 909
 910       *mem_refs->ref = tmp_var;
 911       update_stmt (mem_refs->stmt);
 912     }
 913 }
 914
 915 /* The name and the length of the currently generated variable
 916    for lsm.  */
 917 #define MAX_LSM_NAME_LENGTH 40
 918 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
 919 static int lsm_tmp_name_length;
 920
 921 /* Adds S to lsm_tmp_name.  */
 922
 923 static void
 924 lsm_tmp_name_add (const char *s)
 925 {
 926   int l = strlen (s) + lsm_tmp_name_length;
 927   if (l > MAX_LSM_NAME_LENGTH)
 928     return;
 929
 930   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
 931   lsm_tmp_name_length = l;
 932 }
 933
 934 /* Stores the name for temporary variable that replaces REF to
 935    lsm_tmp_name.  */
 936
 937 static void
 938 gen_lsm_tmp_name (tree ref)
 939 {
 940   const char *name;
 941
 942   switch (TREE_CODE (ref))
 943     {
 944     case MISALIGNED_INDIRECT_REF:
 945     case ALIGN_INDIRECT_REF:
 946     case INDIRECT_REF:
 947       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 948       lsm_tmp_name_add ("_");
 949       break;
 950
 951     case BIT_FIELD_REF:
 952     case VIEW_CONVERT_EXPR:
 953     case ARRAY_RANGE_REF:
 954       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 955       break;
 956
 957     case REALPART_EXPR:
 958       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 959       lsm_tmp_name_add ("_RE");
 960       break;
 961
 962     case IMAGPART_EXPR:
 963       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 964       lsm_tmp_name_add ("_IM");
 965       break;
 966
 967     case COMPONENT_REF:
 968       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 969       lsm_tmp_name_add ("_");
 970       name = get_name (TREE_OPERAND (ref, 1));
 971       if (!name)
 972         name = "F";
 973       lsm_tmp_name_add ("_");
 974       lsm_tmp_name_add (name);
 975
 976     case ARRAY_REF:
 977       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 978       lsm_tmp_name_add ("_I");
 979       break;
 980
 981     case SSA_NAME:
 982       ref = SSA_NAME_VAR (ref);
 983       /* Fallthru.  */
 984
 985     case VAR_DECL:
 986     case PARM_DECL:
 987       name = get_name (ref);
 988       if (!name)
 989         name = "D";
 990       lsm_tmp_name_add (name);
 991       break;
 992
 993     case STRING_CST:
 994       lsm_tmp_name_add ("S");
 995       break;
 996
 997     case RESULT_DECL:
 998       lsm_tmp_name_add ("R");
 999       break;
1000
1001     default:
1002       gcc_unreachable ();
1003     }
1004 }
1005
1006 /* Determines name for temporary variable that replaces REF.
1007    The name is accumulated into the lsm_tmp_name variable.  */
1008
1009 static char *
1010 get_lsm_tmp_name (tree ref)
1011 {
1012   lsm_tmp_name_length = 0;
1013   gen_lsm_tmp_name (ref);
1014   lsm_tmp_name_add ("_lsm");
1015   return lsm_tmp_name;
1016 }
1017
1018 /* Records request for store motion of memory reference REF from LOOP.
1019    MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1020    these references are rewritten by a new temporary variable.
1021    Exits from the LOOP are stored in EXITS.  The initialization of the
1022    temporary variable is put to the preheader of the loop, and assignments
1023    to the reference from the temporary variable are emitted to exits.  */
1024
1025 static void
1026 schedule_sm (struct loop *loop, VEC (edge, heap) *exits, tree ref,
1027              struct mem_ref_loc *mem_refs)
1028 {
1029   struct mem_ref_loc *aref;
1030   tree tmp_var;
1031   unsigned i;
1032   tree load, store;
1033   struct fmt_data fmt_data;
1034   edge ex;
1035
1036   if (dump_file && (dump_flags & TDF_DETAILS))
1037     {
1038       fprintf (dump_file, "Executing store motion of ");
1039       print_generic_expr (dump_file, ref, 0);
1040       fprintf (dump_file, " from loop %d\n", loop->num);
1041     }
1042
1043   tmp_var = make_rename_temp (TREE_TYPE (ref),
1044                               get_lsm_tmp_name (ref));
1045
1046   fmt_data.loop = loop;
1047   fmt_data.orig_loop = loop;
1048   for_each_index (&ref, force_move_till, &fmt_data);
1049
1050   rewrite_mem_refs (tmp_var, mem_refs);
1051   for (aref = mem_refs; aref; aref = aref->next)
1052     if (LIM_DATA (aref->stmt))
1053       LIM_DATA (aref->stmt)->sm_done = true;
1054
1055   /* Emit the load & stores.  */
1056   load = build_gimple_modify_stmt (tmp_var, ref);
1057   get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1058   LIM_DATA (load)->max_loop = loop;
1059   LIM_DATA (load)->tgt_loop = loop;
1060
1061   /* Put this into the latch, so that we are sure it will be processed after
1062      all dependencies.  */
1063   bsi_insert_on_edge (loop_latch_edge (loop), load);
1064
1065   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1066     {
1067       store = build_gimple_modify_stmt (unshare_expr (ref), tmp_var);
1068       bsi_insert_on_edge (ex, store);
1069     }
1070 }
1071
1072 /* Check whether memory reference REF can be hoisted out of the LOOP.  If this
1073    is true, prepare the statements that load the value of the memory reference
1074    to a temporary variable in the loop preheader, store it back on the loop
1075    exits, and replace all the references inside LOOP by this temporary variable.
1076    EXITS is the list of exits of LOOP.  CLOBBERED_VOPS is the bitmap of virtual
1077    operands that are clobbered by a call or accessed through multiple references
1078    in loop.  */
1079
1080 static void
1081 determine_lsm_ref (struct loop *loop, VEC (edge, heap) *exits,
1082                    bitmap clobbered_vops, struct mem_ref *ref)
1083 {
1084   struct mem_ref_loc *aref;
1085   struct loop *must_exec;
1086
1087   /* In case the memory is not stored to, there is nothing for SM to do.  */
1088   if (!ref->is_stored)
1089     return;
1090
1091   /* If the reference is aliased with any different ref, or killed by call
1092      in function, then fail.  */
1093   if (bitmap_intersect_p (ref->vops, clobbered_vops))
1094     return;
1095
1096   if (tree_could_trap_p (ref->mem))
1097     {
1098       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1099          of the statements in that it occurs is always executed when the loop
1100          is entered.  This way we know that by moving the load from the
1101          reference out of the loop we will not cause the error that would not
1102          occur otherwise.
1103
1104          TODO -- in fact we would like to check for anticipability of the
1105          reference, i.e. that on each path from loop entry to loop exit at
1106          least one of the statements containing the memory reference is
1107          executed.  */
1108
1109       for (aref = ref->locs; aref; aref = aref->next)
1110         {
1111           if (!LIM_DATA (aref->stmt))
1112             continue;
1113
1114           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1115           if (!must_exec)
1116             continue;
1117
1118           if (must_exec == loop
1119               || flow_loop_nested_p (must_exec, loop))
1120             break;
1121         }
1122
1123       if (!aref)
1124         return;
1125     }
1126
1127   schedule_sm (loop, exits, ref->mem, ref->locs);
1128 }
1129
1130 /* Hoists memory references MEM_REFS out of LOOP.  CLOBBERED_VOPS is the list
1131    of vops clobbered by call in loop or accessed by multiple memory references.
1132    EXITS is the list of exit edges of the LOOP.  */
1133
1134 static void
1135 hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
1136                          bitmap clobbered_vops, VEC (edge, heap) *exits)
1137 {
1138   struct mem_ref *ref;
1139
1140   for (ref = mem_refs; ref; ref = ref->next)
1141     determine_lsm_ref (loop, exits, clobbered_vops, ref);
1142 }
1143
1144 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
1145    for a store motion optimization (i.e. whether we can insert statement
1146    on its exits).  */
1147
1148 static bool
1149 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
1150                       VEC (edge, heap) *exits)
1151 {
1152   unsigned i;
1153   edge ex;
1154
1155   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1156     if (ex->flags & EDGE_ABNORMAL)
1157       return false;
1158
1159   return true;
1160 }
1161
1162 /* A hash function for struct mem_ref object OBJ.  */
1163
1164 static hashval_t
1165 memref_hash (const void *obj)
1166 {
1167   const struct mem_ref *mem = obj;
1168
1169   return mem->hash;
1170 }
1171
1172 /* An equality function for struct mem_ref object OBJ1 with
1173    memory reference OBJ2.  */
1174
1175 static int
1176 memref_eq (const void *obj1, const void *obj2)
1177 {
1178   const struct mem_ref *mem1 = obj1;
1179
1180   return operand_equal_p (mem1->mem, (tree) obj2, 0);
1181 }
1182
1183 /* Gathers memory references in statement STMT in LOOP, storing the
1184    information about them in MEM_REFS hash table.  Note vops accessed through
1185    unrecognized statements in CLOBBERED_VOPS.  The newly created references
1186    are also stored to MEM_REF_LIST.  */
1187
1188 static void
1189 gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs,
1190                       bitmap clobbered_vops, tree stmt,
1191                       struct mem_ref **mem_ref_list)
1192 {
1193   tree *lhs, *rhs, *mem = NULL;
1194   hashval_t hash;
1195   PTR *slot;
1196   struct mem_ref *ref = NULL;
1197   ssa_op_iter oi;
1198   tree vname;
1199   bool is_stored;
1200
1201   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1202     return;
1203
1204   /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns.  */
1205   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1206     goto fail;
1207
1208   lhs = &GIMPLE_STMT_OPERAND (stmt, 0);
1209   rhs = &GIMPLE_STMT_OPERAND (stmt, 1);
1210
1211   if (TREE_CODE (*lhs) == SSA_NAME)
1212     {
1213       if (!is_gimple_addressable (*rhs))
1214         goto fail;
1215
1216       mem = rhs;
1217       is_stored = false;
1218     }
1219   else if (TREE_CODE (*rhs) == SSA_NAME
1220            || is_gimple_min_invariant (*rhs))
1221     {
1222       mem = lhs;
1223       is_stored = true;
1224     }
1225   else
1226     goto fail;
1227
1228   /* If we cannot create an SSA name for the result, give up.  */
1229   if (!is_gimple_reg_type (TREE_TYPE (*mem))
1230       || TREE_THIS_VOLATILE (*mem))
1231     goto fail;
1232
1233   /* If we cannot move the reference out of the loop, fail.  */
1234   if (!for_each_index (mem, may_move_till, loop))
1235     goto fail;
1236
1237   hash = iterative_hash_expr (*mem, 0);
1238   slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT);
1239
1240   if (*slot)
1241     ref = *slot;
1242   else
1243     {
1244       ref = XNEW (struct mem_ref);
1245       ref->mem = *mem;
1246       ref->hash = hash;
1247       ref->locs = NULL;
1248       ref->is_stored = false;
1249       ref->vops = BITMAP_ALLOC (NULL);
1250       ref->next = *mem_ref_list;
1251       *mem_ref_list = ref;
1252       *slot = ref;
1253     }
1254   ref->is_stored |= is_stored;
1255
1256   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1257     bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1258   record_mem_ref_loc (&ref->locs, stmt, mem);
1259   return;
1260
1261 fail:
1262   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1263     bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname)));
1264 }
1265
1266 /* Gathers memory references in LOOP.  Notes vops accessed through unrecognized
1267    statements in CLOBBERED_VOPS.  The list of the references found by
1268    the function is returned.  */
1269
1270 static struct mem_ref *
1271 gather_mem_refs (struct loop *loop, bitmap clobbered_vops)
1272 {
1273   basic_block *body = get_loop_body (loop);
1274   block_stmt_iterator bsi;
1275   unsigned i;
1276   struct mem_ref *mem_ref_list = NULL;
1277   htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL);
1278
1279   for (i = 0; i < loop->num_nodes; i++)
1280     {
1281       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
1282         gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi),
1283                               &mem_ref_list);
1284     }
1285
1286   free (body);
1287
1288   htab_delete (mem_refs);
1289   return mem_ref_list;
1290 }
1291
1292 /* Finds the vops accessed by more than one of the memory references described
1293    in MEM_REFS and marks them in CLOBBERED_VOPS.  */
1294
1295 static void
1296 find_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops)
1297 {
1298   bitmap_head tmp, all_vops;
1299   struct mem_ref *ref;
1300
1301   bitmap_initialize (&tmp, &bitmap_default_obstack);
1302   bitmap_initialize (&all_vops, &bitmap_default_obstack);
1303
1304   for (ref = mem_refs; ref; ref = ref->next)
1305     {
1306       /* The vops that are already in all_vops are accessed by more than
1307          one memory reference.  */
1308       bitmap_and (&tmp, &all_vops, ref->vops);
1309       bitmap_ior_into (clobbered_vops, &tmp);
1310       bitmap_clear (&tmp);
1311
1312       bitmap_ior_into (&all_vops, ref->vops);
1313     }
1314
1315   bitmap_clear (&all_vops);
1316 }
1317
1318 /* Releases the memory occupied by REF.  */
1319
1320 static void
1321 free_mem_ref (struct mem_ref *ref)
1322 {
1323   free_mem_ref_locs (ref->locs);
1324   BITMAP_FREE (ref->vops);
1325   free (ref);
1326 }
1327
1328 /* Releases the memory occupied by REFS.  */
1329
1330 static void
1331 free_mem_refs (struct mem_ref *refs)
1332 {
1333   struct mem_ref *ref, *next;
1334
1335   for (ref = refs; ref; ref = next)
1336     {
1337       next = ref->next;
1338       free_mem_ref (ref);
1339     }
1340 }
1341
1342 /* Try to perform store motion for all memory references modified inside
1343    LOOP.  */
1344
1345 static void
1346 determine_lsm_loop (struct loop *loop)
1347 {
1348   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1349   bitmap clobbered_vops;
1350   struct mem_ref *mem_refs;
1351
1352   if (!loop_suitable_for_sm (loop, exits))
1353     {
1354       VEC_free (edge, heap, exits);
1355       return;
1356     }
1357
1358   /* Find the memory references in LOOP.  */
1359   clobbered_vops = BITMAP_ALLOC (NULL);
1360   mem_refs = gather_mem_refs (loop, clobbered_vops);
1361
1362   /* Find the vops that are used for more than one reference.  */
1363   find_more_ref_vops (mem_refs, clobbered_vops);
1364
1365   /* Hoist all suitable memory references.  */
1366   hoist_memory_references (loop, mem_refs, clobbered_vops, exits);
1367
1368   free_mem_refs (mem_refs);
1369   VEC_free (edge, heap, exits);
1370   BITMAP_FREE (clobbered_vops);
1371 }
1372
1373 /* Try to perform store motion for all memory references modified inside
1374    loops.  */
1375
1376 static void
1377 determine_lsm (void)
1378 {
1379   struct loop *loop;
1380   loop_iterator li;
1381
1382   /* Pass the loops from the outermost and perform the store motion as
1383      suitable.  */
1384
1385   FOR_EACH_LOOP (li, loop, 0)
1386     {
1387       determine_lsm_loop (loop);
1388     }
1389
1390   bsi_commit_edge_inserts ();
1391 }
1392
1393 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1394    for each such basic block bb records the outermost loop for that execution
1395    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1396    blocks that contain a nonpure call.  */
1397
1398 static void
1399 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1400 {
1401   basic_block bb = NULL, *bbs, last = NULL;
1402   unsigned i;
1403   edge e;
1404   struct loop *inn_loop = loop;
1405
1406   if (!loop->header->aux)
1407     {
1408       bbs = get_loop_body_in_dom_order (loop);
1409
1410       for (i = 0; i < loop->num_nodes; i++)
1411         {
1412           edge_iterator ei;
1413           bb = bbs[i];
1414
1415           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1416             last = bb;
1417
1418           if (TEST_BIT (contains_call, bb->index))
1419             break;
1420
1421           FOR_EACH_EDGE (e, ei, bb->succs)
1422             if (!flow_bb_inside_loop_p (loop, e->dest))
1423               break;
1424           if (e)
1425             break;
1426
1427           /* A loop might be infinite (TODO use simple loop analysis
1428              to disprove this if possible).  */
1429           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1430             break;
1431
1432           if (!flow_bb_inside_loop_p (inn_loop, bb))
1433             break;
1434
1435           if (bb->loop_father->header == bb)
1436             {
1437               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1438                 break;
1439
1440               /* In a loop that is always entered we may proceed anyway.
1441                  But record that we entered it and stop once we leave it.  */
1442               inn_loop = bb->loop_father;
1443             }
1444         }
1445
1446       while (1)
1447         {
1448           last->aux = loop;
1449           if (last == loop->header)
1450             break;
1451           last = get_immediate_dominator (CDI_DOMINATORS, last);
1452         }
1453
1454       free (bbs);
1455     }
1456
1457   for (loop = loop->inner; loop; loop = loop->next)
1458     fill_always_executed_in (loop, contains_call);
1459 }
1460
1461 /* Compute the global information needed by the loop invariant motion pass.  */
1462
1463 static void
1464 tree_ssa_lim_initialize (void)
1465 {
1466   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1467   block_stmt_iterator bsi;
1468   struct loop *loop;
1469   basic_block bb;
1470
1471   sbitmap_zero (contains_call);
1472   FOR_EACH_BB (bb)
1473     {
1474       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1475         {
1476           if (nonpure_call_p (bsi_stmt (bsi)))
1477             break;
1478         }
1479
1480       if (!bsi_end_p (bsi))
1481         SET_BIT (contains_call, bb->index);
1482     }
1483
1484   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
1485     fill_always_executed_in (loop, contains_call);
1486
1487   sbitmap_free (contains_call);
1488 }
1489
1490 /* Cleans up after the invariant motion pass.  */
1491
1492 static void
1493 tree_ssa_lim_finalize (void)
1494 {
1495   basic_block bb;
1496
1497   FOR_EACH_BB (bb)
1498     {
1499       bb->aux = NULL;
1500     }
1501 }
1502
1503 /* Moves invariants from loops.  Only "expensive" invariants are moved out --
1504    i.e. those that are likely to be win regardless of the register pressure.  */
1505
1506 void
1507 tree_ssa_lim (void)
1508 {
1509   tree_ssa_lim_initialize ();
1510
1511   /* For each statement determine the outermost loop in that it is
1512      invariant and cost for computing the invariant.  */
1513   determine_invariantness ();
1514
1515   /* For each memory reference determine whether it is possible to hoist it
1516      out of the loop.  Force the necessary invariants to be moved out of the
1517      loops as well.  */
1518   determine_lsm ();
1519
1520   /* Move the expressions that are expensive enough.  */
1521   move_computations ();
1522
1523   tree_ssa_lim_finalize ();
1524 }