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     case LSHIFT_EXPR:
 464     case RSHIFT_EXPR:
 465       cost += 20;
 466       break;
 467
 468     default:
 469       break;
 470     }
 471
 472   return cost;
 473 }
 474
 475 /* Determine the outermost loop to that it is possible to hoist a statement
 476    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 477    the outermost loop in that the value computed by STMT is invariant.
 478    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 479    we preserve the fact whether STMT is executed.  It also fills other related
 480    information to LIM_DATA (STMT).
 481
 482    The function returns false if STMT cannot be hoisted outside of the loop it
 483    is defined in, and true otherwise.  */
 484
 485 static bool
 486 determine_max_movement (tree stmt, bool must_preserve_exec)
 487 {
 488   basic_block bb = bb_for_stmt (stmt);
 489   struct loop *loop = bb->loop_father;
 490   struct loop *level;
 491   struct lim_aux_data *lim_data = LIM_DATA (stmt);
 492   tree val;
 493   ssa_op_iter iter;
 494
 495   if (must_preserve_exec)
 496     level = ALWAYS_EXECUTED_IN (bb);
 497   else
 498     level = superloop_at_depth (loop, 1);
 499   lim_data->max_loop = level;
 500
 501   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
 502     if (!add_dependency (val, lim_data, loop, true))
 503       return false;
 504
 505   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
 506     if (!add_dependency (val, lim_data, loop, false))
 507       return false;
 508
 509   lim_data->cost += stmt_cost (stmt);
 510
 511   return true;
 512 }
 513
 514 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
 515    and that one of the operands of this statement is computed by STMT.
 516    Ensure that STMT (together with all the statements that define its
 517    operands) is hoisted at least out of the loop LEVEL.  */
 518
 519 static void
 520 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
 521 {
 522   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
 523   struct depend *dep;
 524
 525   stmt_loop = find_common_loop (orig_loop, stmt_loop);
 526   if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
 527     stmt_loop = find_common_loop (stmt_loop,
 528                                   LIM_DATA (stmt)->tgt_loop->outer);
 529   if (flow_loop_nested_p (stmt_loop, level))
 530     return;
 531
 532   gcc_assert (LIM_DATA (stmt));
 533   gcc_assert (level == LIM_DATA (stmt)->max_loop
 534               || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
 535
 536   LIM_DATA (stmt)->tgt_loop = level;
 537   for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
 538     set_level (dep->stmt, orig_loop, level);
 539 }
 540
 541 /* Determines an outermost loop from that we want to hoist the statement STMT.
 542    For now we chose the outermost possible loop.  TODO -- use profiling
 543    information to set it more sanely.  */
 544
 545 static void
 546 set_profitable_level (tree stmt)
 547 {
 548   set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
 549 }
 550
 551 /* Returns true if STMT is not a pure call.  */
 552
 553 static bool
 554 nonpure_call_p (tree stmt)
 555 {
 556   tree call = get_call_expr_in (stmt);
 557
 558   if (!call)
 559     return false;
 560
 561   return TREE_SIDE_EFFECTS (call) != 0;
 562 }
 563
 564 /* Releases the memory occupied by DATA.  */
 565
 566 static void
 567 free_lim_aux_data (struct lim_aux_data *data)
 568 {
 569   struct depend *dep, *next;
 570
 571   for (dep = data->depends; dep; dep = next)
 572     {
 573       next = dep->next;
 574       free (dep);
 575     }
 576   free (data);
 577 }
 578
 579 /* Rewrite a/b to a*(1/b).  Return the invariant stmt to process.  */
 580
 581 static tree
 582 rewrite_reciprocal (block_stmt_iterator *bsi)
 583 {
 584   tree stmt, lhs, rhs, stmt1, stmt2, var, name, tmp;
 585
 586   stmt = bsi_stmt (*bsi);
 587   lhs = GENERIC_TREE_OPERAND (stmt, 0);
 588   rhs = GENERIC_TREE_OPERAND (stmt, 1);
 589
 590   /* stmt must be GIMPLE_MODIFY_STMT.  */
 591   var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
 592   add_referenced_var (var);
 593
 594   tmp = build2 (RDIV_EXPR, TREE_TYPE (rhs),
 595                 build_real (TREE_TYPE (rhs), dconst1),
 596                 TREE_OPERAND (rhs, 1));
 597   stmt1 = build_gimple_modify_stmt (var, tmp);
 598   name = make_ssa_name (var, stmt1);
 599   GIMPLE_STMT_OPERAND (stmt1, 0) = name;
 600   tmp = build2 (MULT_EXPR, TREE_TYPE (rhs),
 601                 name, TREE_OPERAND (rhs, 0));
 602   stmt2 = build_gimple_modify_stmt (lhs, tmp);
 603
 604   /* Replace division stmt with reciprocal and multiply stmts.
 605      The multiply stmt is not invariant, so update iterator
 606      and avoid rescanning.  */
 607   bsi_replace (bsi, stmt1, true);
 608   bsi_insert_after (bsi, stmt2, BSI_NEW_STMT);
 609   SSA_NAME_DEF_STMT (lhs) = stmt2;
 610
 611   /* Continue processing with invariant reciprocal statement.  */
 612   return stmt1;
 613 }
 614
 615 /* Check if the pattern at *BSI is a bittest of the form
 616    (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0.  */
 617
 618 static tree
 619 rewrite_bittest (block_stmt_iterator *bsi)
 620 {
 621   tree stmt, lhs, rhs, var, name, use_stmt, stmt1, stmt2, t;
 622   use_operand_p use;
 623
 624   stmt = bsi_stmt (*bsi);
 625   lhs = GENERIC_TREE_OPERAND (stmt, 0);
 626   rhs = GENERIC_TREE_OPERAND (stmt, 1);
 627
 628   /* Verify that the single use of lhs is a comparison against zero.  */
 629   if (TREE_CODE (lhs) != SSA_NAME
 630       || !single_imm_use (lhs, &use, &use_stmt)
 631       || TREE_CODE (use_stmt) != COND_EXPR)
 632     return stmt;
 633   t = COND_EXPR_COND (use_stmt);
 634   if (TREE_OPERAND (t, 0) != lhs
 635       || (TREE_CODE (t) != NE_EXPR
 636           && TREE_CODE (t) != EQ_EXPR)
 637       || !integer_zerop (TREE_OPERAND (t, 1)))
 638     return stmt;
 639
 640   /* Get at the operands of the shift.  The rhs is TMP1 & 1.  */
 641   stmt1 = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 642   if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
 643     return stmt;
 644
 645   /* There is a conversion inbetween possibly inserted by fold.  */
 646   t = GIMPLE_STMT_OPERAND (stmt1, 1);
 647   if (TREE_CODE (t) == NOP_EXPR
 648       || TREE_CODE (t) == CONVERT_EXPR)
 649     {
 650       t = TREE_OPERAND (t, 0);
 651       if (TREE_CODE (t) != SSA_NAME
 652           || !has_single_use (t))
 653         return stmt;
 654       stmt1 = SSA_NAME_DEF_STMT (t);
 655       if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
 656         return stmt;
 657       t = GIMPLE_STMT_OPERAND (stmt1, 1);
 658     }
 659
 660   /* Verify that B is loop invariant but A is not.  Verify that with
 661      all the stmt walking we are still in the same loop.  */
 662   if (TREE_CODE (t) == RSHIFT_EXPR
 663       && loop_containing_stmt (stmt1) == loop_containing_stmt (stmt)
 664       && outermost_invariant_loop_expr (TREE_OPERAND (t, 1),
 665                                         loop_containing_stmt (stmt1)) != NULL
 666       && outermost_invariant_loop_expr (TREE_OPERAND (t, 0),
 667                                         loop_containing_stmt (stmt1)) == NULL)
 668     {
 669       tree a = TREE_OPERAND (t, 0);
 670       tree b = TREE_OPERAND (t, 1);
 671
 672       /* 1 << B */
 673       var = create_tmp_var (TREE_TYPE (a), "shifttmp");
 674       add_referenced_var (var);
 675       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
 676                        build_int_cst (TREE_TYPE (a), 1), b);
 677       stmt1 = build_gimple_modify_stmt (var, t);
 678       name = make_ssa_name (var, stmt1);
 679       GIMPLE_STMT_OPERAND (stmt1, 0) = name;
 680
 681       /* A & (1 << B) */
 682       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
 683       stmt2 = build_gimple_modify_stmt (var, t);
 684       name = make_ssa_name (var, stmt2);
 685       GIMPLE_STMT_OPERAND (stmt2, 0) = name;
 686       SET_USE (use, name);
 687
 688       bsi_insert_before (bsi, stmt1, BSI_SAME_STMT);
 689       bsi_replace (bsi, stmt2, true);
 690
 691       return stmt1;
 692     }
 693
 694   return stmt;
 695 }
 696
 697
 698 /* Determine the outermost loops in that statements in basic block BB are
 699    invariant, and record them to the LIM_DATA associated with the statements.
 700    Callback for walk_dominator_tree.  */
 701
 702 static void
 703 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 704                               basic_block bb)
 705 {
 706   enum move_pos pos;
 707   block_stmt_iterator bsi;
 708   tree stmt, rhs;
 709   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
 710   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
 711
 712   if (!bb->loop_father->outer)
 713     return;
 714
 715   if (dump_file && (dump_flags & TDF_DETAILS))
 716     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 717              bb->index, bb->loop_father->num, bb->loop_father->depth);
 718
 719   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 720     {
 721       stmt = bsi_stmt (bsi);
 722
 723       pos = movement_possibility (stmt);
 724       if (pos == MOVE_IMPOSSIBLE)
 725         {
 726           if (nonpure_call_p (stmt))
 727             {
 728               maybe_never = true;
 729               outermost = NULL;
 730             }
 731           continue;
 732         }
 733
 734       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 735         {
 736           rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 737
 738           /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
 739              to be hoisted out of loop, saving expensive divide.  */
 740           if (pos == MOVE_POSSIBLE
 741               && TREE_CODE (rhs) == RDIV_EXPR
 742               && flag_unsafe_math_optimizations
 743               && !flag_trapping_math
 744               && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
 745                                                 loop_containing_stmt (stmt)) != NULL
 746               && outermost_invariant_loop_expr (rhs,
 747                                                 loop_containing_stmt (stmt)) == NULL)
 748             stmt = rewrite_reciprocal (&bsi);
 749
 750           /* If the shift count is invariant, convert (A >> B) & 1 to
 751              A & (1 << B) allowing the bit mask to be hoisted out of the loop
 752              saving an expensive shift.  */
 753           if (pos == MOVE_POSSIBLE
 754               && TREE_CODE (rhs) == BIT_AND_EXPR
 755               && integer_onep (TREE_OPERAND (rhs, 1))
 756               && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
 757               && has_single_use (TREE_OPERAND (rhs, 0)))
 758             stmt = rewrite_bittest (&bsi);
 759         }
 760
 761       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
 762       LIM_DATA (stmt)->always_executed_in = outermost;
 763
 764       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
 765         continue;
 766
 767       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
 768         {
 769           LIM_DATA (stmt)->max_loop = NULL;
 770           continue;
 771         }
 772
 773       if (dump_file && (dump_flags & TDF_DETAILS))
 774         {
 775           print_generic_stmt_indented (dump_file, stmt, 0, 2);
 776           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
 777                    LIM_DATA (stmt)->max_loop->depth,
 778                    LIM_DATA (stmt)->cost);
 779         }
 780
 781       if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
 782         set_profitable_level (stmt);
 783     }
 784 }
 785
 786 /* For each statement determines the outermost loop in that it is invariant,
 787    statements on whose motion it depends and the cost of the computation.
 788    This information is stored to the LIM_DATA structure associated with
 789    each statement.  */
 790
 791 static void
 792 determine_invariantness (void)
 793 {
 794   struct dom_walk_data walk_data;
 795
 796   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 797   walk_data.dom_direction = CDI_DOMINATORS;
 798   walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
 799
 800   init_walk_dominator_tree (&walk_data);
 801   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 802   fini_walk_dominator_tree (&walk_data);
 803 }
 804
 805 /* Hoist the statements in basic block BB out of the loops prescribed by
 806    data stored in LIM_DATA structures associated with each statement.  Callback
 807    for walk_dominator_tree.  */
 808
 809 static void
 810 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 811                         basic_block bb)
 812 {
 813   struct loop *level;
 814   block_stmt_iterator bsi;
 815   tree stmt;
 816   unsigned cost = 0;
 817
 818   if (!bb->loop_father->outer)
 819     return;
 820
 821   for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 822     {
 823       stmt = bsi_stmt (bsi);
 824
 825       if (!LIM_DATA (stmt))
 826         {
 827           bsi_next (&bsi);
 828           continue;
 829         }
 830
 831       cost = LIM_DATA (stmt)->cost;
 832       level = LIM_DATA (stmt)->tgt_loop;
 833       free_lim_aux_data (LIM_DATA (stmt));
 834       stmt_ann (stmt)->common.aux = NULL;
 835
 836       if (!level)
 837         {
 838           bsi_next (&bsi);
 839           continue;
 840         }
 841
 842       /* We do not really want to move conditionals out of the loop; we just
 843          placed it here to force its operands to be moved if necessary.  */
 844       if (TREE_CODE (stmt) == COND_EXPR)
 845         continue;
 846
 847       if (dump_file && (dump_flags & TDF_DETAILS))
 848         {
 849           fprintf (dump_file, "Moving statement\n");
 850           print_generic_stmt (dump_file, stmt, 0);
 851           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
 852                    cost, level->num);
 853         }
 854       bsi_insert_on_edge (loop_preheader_edge (level), stmt);
 855       bsi_remove (&bsi, false);
 856     }
 857 }
 858
 859 /* Hoist the statements out of the loops prescribed by data stored in
 860    LIM_DATA structures associated with each statement.*/
 861
 862 static void
 863 move_computations (void)
 864 {
 865   struct dom_walk_data walk_data;
 866
 867   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 868   walk_data.dom_direction = CDI_DOMINATORS;
 869   walk_data.before_dom_children_before_stmts = move_computations_stmt;
 870
 871   init_walk_dominator_tree (&walk_data);
 872   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 873   fini_walk_dominator_tree (&walk_data);
 874
 875   bsi_commit_edge_inserts ();
 876   if (need_ssa_update_p ())
 877     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 878 }
 879
 880 /* Checks whether the statement defining variable *INDEX can be hoisted
 881    out of the loop passed in DATA.  Callback for for_each_index.  */
 882
 883 static bool
 884 may_move_till (tree ref, tree *index, void *data)
 885 {
 886   struct loop *loop = data, *max_loop;
 887
 888   /* If REF is an array reference, check also that the step and the lower
 889      bound is invariant in LOOP.  */
 890   if (TREE_CODE (ref) == ARRAY_REF)
 891     {
 892       tree step = array_ref_element_size (ref);
 893       tree lbound = array_ref_low_bound (ref);
 894
 895       max_loop = outermost_invariant_loop_expr (step, loop);
 896       if (!max_loop)
 897         return false;
 898
 899       max_loop = outermost_invariant_loop_expr (lbound, loop);
 900       if (!max_loop)
 901         return false;
 902     }
 903
 904   max_loop = outermost_invariant_loop (*index, loop);
 905   if (!max_loop)
 906     return false;
 907
 908   return true;
 909 }
 910
 911 /* Forces statements defining (invariant) SSA names in expression EXPR to be
 912    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
 913
 914 static void
 915 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
 916 {
 917   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
 918   unsigned i, nops;
 919
 920   if (TREE_CODE (expr) == SSA_NAME)
 921     {
 922       tree stmt = SSA_NAME_DEF_STMT (expr);
 923       if (IS_EMPTY_STMT (stmt))
 924         return;
 925
 926       set_level (stmt, orig_loop, loop);
 927       return;
 928     }
 929
 930   if (class != tcc_unary
 931       && class != tcc_binary
 932       && class != tcc_expression
 933       && class != tcc_vl_exp
 934       && class != tcc_comparison)
 935     return;
 936
 937   nops = TREE_OPERAND_LENGTH (expr);
 938   for (i = 0; i < nops; i++)
 939     force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
 940 }
 941
 942 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 943    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
 944    for_each_index.  */
 945
 946 struct fmt_data
 947 {
 948   struct loop *loop;
 949   struct loop *orig_loop;
 950 };
 951
 952 static bool
 953 force_move_till (tree ref, tree *index, void *data)
 954 {
 955   tree stmt;
 956   struct fmt_data *fmt_data = data;
 957
 958   if (TREE_CODE (ref) == ARRAY_REF)
 959     {
 960       tree step = array_ref_element_size (ref);
 961       tree lbound = array_ref_low_bound (ref);
 962
 963       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
 964       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
 965     }
 966
 967   if (TREE_CODE (*index) != SSA_NAME)
 968     return true;
 969
 970   stmt = SSA_NAME_DEF_STMT (*index);
 971   if (IS_EMPTY_STMT (stmt))
 972     return true;
 973
 974   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
 975
 976   return true;
 977 }
 978
 979 /* Records memory reference location *REF to the list MEM_REFS.  The reference
 980    occurs in statement STMT.  */
 981
 982 static void
 983 record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref)
 984 {
 985   struct mem_ref_loc *aref = XNEW (struct mem_ref_loc);
 986
 987   aref->stmt = stmt;
 988   aref->ref = ref;
 989
 990   aref->next = *mem_refs;
 991   *mem_refs = aref;
 992 }
 993
 994 /* Releases list of memory reference locations MEM_REFS.  */
 995
 996 static void
 997 free_mem_ref_locs (struct mem_ref_loc *mem_refs)
 998 {
 999   struct mem_ref_loc *act;
1000
1001   while (mem_refs)
1002     {
1003       act = mem_refs;
1004       mem_refs = mem_refs->next;
1005       free (act);
1006     }
1007 }
1008
1009 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
1010
1011 static void
1012 rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs)
1013 {
1014   tree var;
1015   ssa_op_iter iter;
1016
1017   for (; mem_refs; mem_refs = mem_refs->next)
1018     {
1019       FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
1020         mark_sym_for_renaming (SSA_NAME_VAR (var));
1021
1022       *mem_refs->ref = tmp_var;
1023       update_stmt (mem_refs->stmt);
1024     }
1025 }
1026
1027 /* The name and the length of the currently generated variable
1028    for lsm.  */
1029 #define MAX_LSM_NAME_LENGTH 40
1030 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1031 static int lsm_tmp_name_length;
1032
1033 /* Adds S to lsm_tmp_name.  */
1034
1035 static void
1036 lsm_tmp_name_add (const char *s)
1037 {
1038   int l = strlen (s) + lsm_tmp_name_length;
1039   if (l > MAX_LSM_NAME_LENGTH)
1040     return;
1041
1042   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1043   lsm_tmp_name_length = l;
1044 }
1045
1046 /* Stores the name for temporary variable that replaces REF to
1047    lsm_tmp_name.  */
1048
1049 static void
1050 gen_lsm_tmp_name (tree ref)
1051 {
1052   const char *name;
1053
1054   switch (TREE_CODE (ref))
1055     {
1056     case MISALIGNED_INDIRECT_REF:
1057     case ALIGN_INDIRECT_REF:
1058     case INDIRECT_REF:
1059       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1060       lsm_tmp_name_add ("_");
1061       break;
1062
1063     case BIT_FIELD_REF:
1064     case VIEW_CONVERT_EXPR:
1065     case ARRAY_RANGE_REF:
1066       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1067       break;
1068
1069     case REALPART_EXPR:
1070       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1071       lsm_tmp_name_add ("_RE");
1072       break;
1073
1074     case IMAGPART_EXPR:
1075       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1076       lsm_tmp_name_add ("_IM");
1077       break;
1078
1079     case COMPONENT_REF:
1080       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1081       lsm_tmp_name_add ("_");
1082       name = get_name (TREE_OPERAND (ref, 1));
1083       if (!name)
1084         name = "F";
1085       lsm_tmp_name_add ("_");
1086       lsm_tmp_name_add (name);
1087
1088     case ARRAY_REF:
1089       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1090       lsm_tmp_name_add ("_I");
1091       break;
1092
1093     case SSA_NAME:
1094       ref = SSA_NAME_VAR (ref);
1095       /* Fallthru.  */
1096
1097     case VAR_DECL:
1098     case PARM_DECL:
1099       name = get_name (ref);
1100       if (!name)
1101         name = "D";
1102       lsm_tmp_name_add (name);
1103       break;
1104
1105     case STRING_CST:
1106       lsm_tmp_name_add ("S");
1107       break;
1108
1109     case RESULT_DECL:
1110       lsm_tmp_name_add ("R");
1111       break;
1112
1113     default:
1114       gcc_unreachable ();
1115     }
1116 }
1117
1118 /* Determines name for temporary variable that replaces REF.
1119    The name is accumulated into the lsm_tmp_name variable.  */
1120
1121 static char *
1122 get_lsm_tmp_name (tree ref)
1123 {
1124   lsm_tmp_name_length = 0;
1125   gen_lsm_tmp_name (ref);
1126   lsm_tmp_name_add ("_lsm");
1127   return lsm_tmp_name;
1128 }
1129
1130 /* Records request for store motion of memory reference REF from LOOP.
1131    MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1132    these references are rewritten by a new temporary variable.
1133    Exits from the LOOP are stored in EXITS.  The initialization of the
1134    temporary variable is put to the preheader of the loop, and assignments
1135    to the reference from the temporary variable are emitted to exits.  */
1136
1137 static void
1138 schedule_sm (struct loop *loop, VEC (edge, heap) *exits, tree ref,
1139              struct mem_ref_loc *mem_refs)
1140 {
1141   struct mem_ref_loc *aref;
1142   tree tmp_var;
1143   unsigned i;
1144   tree load, store;
1145   struct fmt_data fmt_data;
1146   edge ex;
1147
1148   if (dump_file && (dump_flags & TDF_DETAILS))
1149     {
1150       fprintf (dump_file, "Executing store motion of ");
1151       print_generic_expr (dump_file, ref, 0);
1152       fprintf (dump_file, " from loop %d\n", loop->num);
1153     }
1154
1155   tmp_var = make_rename_temp (TREE_TYPE (ref),
1156                               get_lsm_tmp_name (ref));
1157
1158   fmt_data.loop = loop;
1159   fmt_data.orig_loop = loop;
1160   for_each_index (&ref, force_move_till, &fmt_data);
1161
1162   rewrite_mem_refs (tmp_var, mem_refs);
1163   for (aref = mem_refs; aref; aref = aref->next)
1164     if (LIM_DATA (aref->stmt))
1165       LIM_DATA (aref->stmt)->sm_done = true;
1166
1167   /* Emit the load & stores.  */
1168   load = build_gimple_modify_stmt (tmp_var, ref);
1169   get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1170   LIM_DATA (load)->max_loop = loop;
1171   LIM_DATA (load)->tgt_loop = loop;
1172
1173   /* Put this into the latch, so that we are sure it will be processed after
1174      all dependencies.  */
1175   bsi_insert_on_edge (loop_latch_edge (loop), load);
1176
1177   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1178     {
1179       store = build_gimple_modify_stmt (unshare_expr (ref), tmp_var);
1180       bsi_insert_on_edge (ex, store);
1181     }
1182 }
1183
1184 /* Check whether memory reference REF can be hoisted out of the LOOP.  If this
1185    is true, prepare the statements that load the value of the memory reference
1186    to a temporary variable in the loop preheader, store it back on the loop
1187    exits, and replace all the references inside LOOP by this temporary variable.
1188    EXITS is the list of exits of LOOP.  CLOBBERED_VOPS is the bitmap of virtual
1189    operands that are clobbered by a call or accessed through multiple references
1190    in loop.  */
1191
1192 static void
1193 determine_lsm_ref (struct loop *loop, VEC (edge, heap) *exits,
1194                    bitmap clobbered_vops, struct mem_ref *ref)
1195 {
1196   struct mem_ref_loc *aref;
1197   struct loop *must_exec;
1198
1199   /* In case the memory is not stored to, there is nothing for SM to do.  */
1200   if (!ref->is_stored)
1201     return;
1202
1203   /* If the reference is aliased with any different ref, or killed by call
1204      in function, then fail.  */
1205   if (bitmap_intersect_p (ref->vops, clobbered_vops))
1206     return;
1207
1208   if (tree_could_trap_p (ref->mem))
1209     {
1210       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1211          of the statements in that it occurs is always executed when the loop
1212          is entered.  This way we know that by moving the load from the
1213          reference out of the loop we will not cause the error that would not
1214          occur otherwise.
1215
1216          TODO -- in fact we would like to check for anticipability of the
1217          reference, i.e. that on each path from loop entry to loop exit at
1218          least one of the statements containing the memory reference is
1219          executed.  */
1220
1221       for (aref = ref->locs; aref; aref = aref->next)
1222         {
1223           if (!LIM_DATA (aref->stmt))
1224             continue;
1225
1226           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1227           if (!must_exec)
1228             continue;
1229
1230           if (must_exec == loop
1231               || flow_loop_nested_p (must_exec, loop))
1232             break;
1233         }
1234
1235       if (!aref)
1236         return;
1237     }
1238
1239   schedule_sm (loop, exits, ref->mem, ref->locs);
1240 }
1241
1242 /* Hoists memory references MEM_REFS out of LOOP.  CLOBBERED_VOPS is the list
1243    of vops clobbered by call in loop or accessed by multiple memory references.
1244    EXITS is the list of exit edges of the LOOP.  */
1245
1246 static void
1247 hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
1248                          bitmap clobbered_vops, VEC (edge, heap) *exits)
1249 {
1250   struct mem_ref *ref;
1251
1252   for (ref = mem_refs; ref; ref = ref->next)
1253     determine_lsm_ref (loop, exits, clobbered_vops, ref);
1254 }
1255
1256 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
1257    for a store motion optimization (i.e. whether we can insert statement
1258    on its exits).  */
1259
1260 static bool
1261 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
1262                       VEC (edge, heap) *exits)
1263 {
1264   unsigned i;
1265   edge ex;
1266
1267   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1268     if (ex->flags & EDGE_ABNORMAL)
1269       return false;
1270
1271   return true;
1272 }
1273
1274 /* A hash function for struct mem_ref object OBJ.  */
1275
1276 static hashval_t
1277 memref_hash (const void *obj)
1278 {
1279   const struct mem_ref *mem = obj;
1280
1281   return mem->hash;
1282 }
1283
1284 /* An equality function for struct mem_ref object OBJ1 with
1285    memory reference OBJ2.  */
1286
1287 static int
1288 memref_eq (const void *obj1, const void *obj2)
1289 {
1290   const struct mem_ref *mem1 = obj1;
1291
1292   return operand_equal_p (mem1->mem, (tree) obj2, 0);
1293 }
1294
1295 /* Gathers memory references in statement STMT in LOOP, storing the
1296    information about them in MEM_REFS hash table.  Note vops accessed through
1297    unrecognized statements in CLOBBERED_VOPS.  The newly created references
1298    are also stored to MEM_REF_LIST.  */
1299
1300 static void
1301 gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs,
1302                       bitmap clobbered_vops, tree stmt,
1303                       struct mem_ref **mem_ref_list)
1304 {
1305   tree *lhs, *rhs, *mem = NULL;
1306   hashval_t hash;
1307   PTR *slot;
1308   struct mem_ref *ref = NULL;
1309   ssa_op_iter oi;
1310   tree vname;
1311   bool is_stored;
1312
1313   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1314     return;
1315
1316   /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns.  */
1317   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1318     goto fail;
1319
1320   lhs = &GIMPLE_STMT_OPERAND (stmt, 0);
1321   rhs = &GIMPLE_STMT_OPERAND (stmt, 1);
1322
1323   if (TREE_CODE (*lhs) == SSA_NAME)
1324     {
1325       if (!is_gimple_addressable (*rhs))
1326         goto fail;
1327
1328       mem = rhs;
1329       is_stored = false;
1330     }
1331   else if (TREE_CODE (*rhs) == SSA_NAME
1332            || is_gimple_min_invariant (*rhs))
1333     {
1334       mem = lhs;
1335       is_stored = true;
1336     }
1337   else
1338     goto fail;
1339
1340   /* If we cannot create an SSA name for the result, give up.  */
1341   if (!is_gimple_reg_type (TREE_TYPE (*mem))
1342       || TREE_THIS_VOLATILE (*mem))
1343     goto fail;
1344
1345   /* If we cannot move the reference out of the loop, fail.  */
1346   if (!for_each_index (mem, may_move_till, loop))
1347     goto fail;
1348
1349   hash = iterative_hash_expr (*mem, 0);
1350   slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT);
1351
1352   if (*slot)
1353     ref = *slot;
1354   else
1355     {
1356       ref = XNEW (struct mem_ref);
1357       ref->mem = *mem;
1358       ref->hash = hash;
1359       ref->locs = NULL;
1360       ref->is_stored = false;
1361       ref->vops = BITMAP_ALLOC (NULL);
1362       ref->next = *mem_ref_list;
1363       *mem_ref_list = ref;
1364       *slot = ref;
1365     }
1366   ref->is_stored |= is_stored;
1367
1368   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1369     bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1370   record_mem_ref_loc (&ref->locs, stmt, mem);
1371   return;
1372
1373 fail:
1374   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1375     bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname)));
1376 }
1377
1378 /* Gathers memory references in LOOP.  Notes vops accessed through unrecognized
1379    statements in CLOBBERED_VOPS.  The list of the references found by
1380    the function is returned.  */
1381
1382 static struct mem_ref *
1383 gather_mem_refs (struct loop *loop, bitmap clobbered_vops)
1384 {
1385   basic_block *body = get_loop_body (loop);
1386   block_stmt_iterator bsi;
1387   unsigned i;
1388   struct mem_ref *mem_ref_list = NULL;
1389   htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL);
1390
1391   for (i = 0; i < loop->num_nodes; i++)
1392     {
1393       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
1394         gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi),
1395                               &mem_ref_list);
1396     }
1397
1398   free (body);
1399
1400   htab_delete (mem_refs);
1401   return mem_ref_list;
1402 }
1403
1404 /* Finds the vops accessed by more than one of the memory references described
1405    in MEM_REFS and marks them in CLOBBERED_VOPS.  */
1406
1407 static void
1408 find_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops)
1409 {
1410   bitmap_head tmp, all_vops;
1411   struct mem_ref *ref;
1412
1413   bitmap_initialize (&tmp, &bitmap_default_obstack);
1414   bitmap_initialize (&all_vops, &bitmap_default_obstack);
1415
1416   for (ref = mem_refs; ref; ref = ref->next)
1417     {
1418       /* The vops that are already in all_vops are accessed by more than
1419          one memory reference.  */
1420       bitmap_and (&tmp, &all_vops, ref->vops);
1421       bitmap_ior_into (clobbered_vops, &tmp);
1422       bitmap_clear (&tmp);
1423
1424       bitmap_ior_into (&all_vops, ref->vops);
1425     }
1426
1427   bitmap_clear (&all_vops);
1428 }
1429
1430 /* Releases the memory occupied by REF.  */
1431
1432 static void
1433 free_mem_ref (struct mem_ref *ref)
1434 {
1435   free_mem_ref_locs (ref->locs);
1436   BITMAP_FREE (ref->vops);
1437   free (ref);
1438 }
1439
1440 /* Releases the memory occupied by REFS.  */
1441
1442 static void
1443 free_mem_refs (struct mem_ref *refs)
1444 {
1445   struct mem_ref *ref, *next;
1446
1447   for (ref = refs; ref; ref = next)
1448     {
1449       next = ref->next;
1450       free_mem_ref (ref);
1451     }
1452 }
1453
1454 /* Try to perform store motion for all memory references modified inside
1455    LOOP.  */
1456
1457 static void
1458 determine_lsm_loop (struct loop *loop)
1459 {
1460   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1461   bitmap clobbered_vops;
1462   struct mem_ref *mem_refs;
1463
1464   if (!loop_suitable_for_sm (loop, exits))
1465     {
1466       VEC_free (edge, heap, exits);
1467       return;
1468     }
1469
1470   /* Find the memory references in LOOP.  */
1471   clobbered_vops = BITMAP_ALLOC (NULL);
1472   mem_refs = gather_mem_refs (loop, clobbered_vops);
1473
1474   /* Find the vops that are used for more than one reference.  */
1475   find_more_ref_vops (mem_refs, clobbered_vops);
1476
1477   /* Hoist all suitable memory references.  */
1478   hoist_memory_references (loop, mem_refs, clobbered_vops, exits);
1479
1480   free_mem_refs (mem_refs);
1481   VEC_free (edge, heap, exits);
1482   BITMAP_FREE (clobbered_vops);
1483 }
1484
1485 /* Try to perform store motion for all memory references modified inside
1486    loops.  */
1487
1488 static void
1489 determine_lsm (void)
1490 {
1491   struct loop *loop;
1492   loop_iterator li;
1493
1494   /* Pass the loops from the outermost and perform the store motion as
1495      suitable.  */
1496
1497   FOR_EACH_LOOP (li, loop, 0)
1498     {
1499       determine_lsm_loop (loop);
1500     }
1501
1502   bsi_commit_edge_inserts ();
1503 }
1504
1505 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1506    for each such basic block bb records the outermost loop for that execution
1507    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1508    blocks that contain a nonpure call.  */
1509
1510 static void
1511 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1512 {
1513   basic_block bb = NULL, *bbs, last = NULL;
1514   unsigned i;
1515   edge e;
1516   struct loop *inn_loop = loop;
1517
1518   if (!loop->header->aux)
1519     {
1520       bbs = get_loop_body_in_dom_order (loop);
1521
1522       for (i = 0; i < loop->num_nodes; i++)
1523         {
1524           edge_iterator ei;
1525           bb = bbs[i];
1526
1527           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1528             last = bb;
1529
1530           if (TEST_BIT (contains_call, bb->index))
1531             break;
1532
1533           FOR_EACH_EDGE (e, ei, bb->succs)
1534             if (!flow_bb_inside_loop_p (loop, e->dest))
1535               break;
1536           if (e)
1537             break;
1538
1539           /* A loop might be infinite (TODO use simple loop analysis
1540              to disprove this if possible).  */
1541           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1542             break;
1543
1544           if (!flow_bb_inside_loop_p (inn_loop, bb))
1545             break;
1546
1547           if (bb->loop_father->header == bb)
1548             {
1549               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1550                 break;
1551
1552               /* In a loop that is always entered we may proceed anyway.
1553                  But record that we entered it and stop once we leave it.  */
1554               inn_loop = bb->loop_father;
1555             }
1556         }
1557
1558       while (1)
1559         {
1560           last->aux = loop;
1561           if (last == loop->header)
1562             break;
1563           last = get_immediate_dominator (CDI_DOMINATORS, last);
1564         }
1565
1566       free (bbs);
1567     }
1568
1569   for (loop = loop->inner; loop; loop = loop->next)
1570     fill_always_executed_in (loop, contains_call);
1571 }
1572
1573 /* Compute the global information needed by the loop invariant motion pass.  */
1574
1575 static void
1576 tree_ssa_lim_initialize (void)
1577 {
1578   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1579   block_stmt_iterator bsi;
1580   struct loop *loop;
1581   basic_block bb;
1582
1583   sbitmap_zero (contains_call);
1584   FOR_EACH_BB (bb)
1585     {
1586       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1587         {
1588           if (nonpure_call_p (bsi_stmt (bsi)))
1589             break;
1590         }
1591
1592       if (!bsi_end_p (bsi))
1593         SET_BIT (contains_call, bb->index);
1594     }
1595
1596   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
1597     fill_always_executed_in (loop, contains_call);
1598
1599   sbitmap_free (contains_call);
1600 }
1601
1602 /* Cleans up after the invariant motion pass.  */
1603
1604 static void
1605 tree_ssa_lim_finalize (void)
1606 {
1607   basic_block bb;
1608
1609   FOR_EACH_BB (bb)
1610     {
1611       bb->aux = NULL;
1612     }
1613 }
1614
1615 /* Moves invariants from loops.  Only "expensive" invariants are moved out --
1616    i.e. those that are likely to be win regardless of the register pressure.  */
1617
1618 void
1619 tree_ssa_lim (void)
1620 {
1621   tree_ssa_lim_initialize ();
1622
1623   /* For each statement determine the outermost loop in that it is
1624      invariant and cost for computing the invariant.  */
1625   determine_invariantness ();
1626
1627   /* For each memory reference determine whether it is possible to hoist it
1628      out of the loop.  Force the necessary invariants to be moved out of the
1629      loops as well.  */
1630   determine_lsm ();
1631
1632   /* Move the expressions that are expensive enough.  */
1633   move_computations ();
1634
1635   tree_ssa_lim_finalize ();
1636 }