gcc/tree-ssa-loop-im.c

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