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