gcc/tree-ssa-loop-im.c

   1 /* Loop invariant motion.
   2    Copyright (C) 2003 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "domwalk.h"
  37 #include "params.h"
  38 #include "tree-pass.h"
  39 #include "flags.h"
  40
  41 /* A type for the list of statements that have to be moved in order to be able
  42    to hoist an invariant computation.  */
  43
  44 struct depend
  45 {
  46   tree stmt;
  47   struct depend *next;
  48 };
  49
  50 /* The possibilities of statement movement.  */
  51
  52 enum move_pos
  53 {
  54   MOVE_IMPOSSIBLE,              /* No movement -- side effect expression.  */
  55   MOVE_PRESERVE_EXECUTION,      /* Must not cause the non-executed statement
  56                                    become executed -- memory accesses, ... */
  57   MOVE_POSSIBLE                 /* Unlimited movement.  */
  58 };
  59
  60 /* The auxiliary data kept for each statement.  */
  61
  62 struct lim_aux_data
  63 {
  64   struct loop *max_loop;        /* The outermost loop in that the statement
  65                                    is invariant.  */
  66
  67   struct loop *tgt_loop;        /* The loop out of that we want to move the
  68                                    invariant.  */
  69
  70   struct loop *always_executed_in;
  71                                 /* The outermost loop for that we are sure
  72                                    the statement is executed if the loop
  73                                    is entered.  */
  74
  75   bool sm_done;                 /* True iff the store motion for a memory
  76                                    reference in the statement has already
  77                                    been executed.  */
  78
  79   unsigned cost;                /* Cost of the computation performed by the
  80                                    statement.  */
  81
  82   struct depend *depends;       /* List of statements that must be also hoisted
  83                                    out of the loop when this statement is
  84                                    hoisted; i.e. those that define the operands
  85                                    of the statement and are inside of the
  86                                    MAX_LOOP loop.  */
  87 };
  88
  89 #define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
  90
  91 /* Description of a memory reference for store motion.  */
  92
  93 struct mem_ref
  94 {
  95   tree *ref;                    /* The reference itself.  */
  96   tree stmt;                    /* The statement in that it occurs.  */
  97   struct mem_ref *next;         /* Next use in the chain.  */
  98 };
  99
 100 /* Minimum cost of an expensive expression.  */
 101 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
 102
 103 /* The outermost loop for that execution of the header guarantees that the
 104    block will be executed.  */
 105 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
 106
 107 /* Maximum uid in the statement in the function.  */
 108
 109 static unsigned max_uid;
 110
 111 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
 112    kinds situations handled; in each of these cases, the memory reference
 113    and DATA are passed to the callback:
 114
 115    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
 116    pass the pointer to the index to the callback.
 117
 118    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
 119    pointer to addr to the callback.
 120
 121    If the callback returns false, the whole search stops and false is returned.
 122    Otherwise the function returns true after traversing through the whole
 123    reference *ADDR_P.  */
 124
 125 bool
 126 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
 127 {
 128   tree *nxt;
 129
 130   for (; ; addr_p = nxt)
 131     {
 132       switch (TREE_CODE (*addr_p))
 133         {
 134         case SSA_NAME:
 135           return cbck (*addr_p, addr_p, data);
 136
 137         case INDIRECT_REF:
 138           nxt = &TREE_OPERAND (*addr_p, 0);
 139           return cbck (*addr_p, nxt, data);
 140
 141         case BIT_FIELD_REF:
 142         case COMPONENT_REF:
 143         case VIEW_CONVERT_EXPR:
 144         case ARRAY_RANGE_REF:
 145           nxt = &TREE_OPERAND (*addr_p, 0);
 146           break;
 147
 148         case ARRAY_REF:
 149           nxt = &TREE_OPERAND (*addr_p, 0);
 150           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
 151             return false;
 152           break;
 153
 154         case VAR_DECL:
 155         case PARM_DECL:
 156         case STRING_CST:
 157         case RESULT_DECL:
 158           return true;
 159
 160         default:
 161           abort ();
 162         }
 163     }
 164 }
 165
 166 /* If it is possible to hoist the statement STMT unconditionally,
 167    returns MOVE_POSSIBLE.
 168    If it is possible to hoist the statement STMT, but we must avoid making
 169    it executed if it would not be executed in the original program (e.g.
 170    because it may trap), return MOVE_PRESERVE_EXECUTION.
 171    Otherwise return MOVE_IMPOSSIBLE.  */
 172
 173 static enum move_pos
 174 movement_possibility (tree stmt)
 175 {
 176   tree lhs, rhs;
 177
 178   if (flag_unswitch_loops
 179       && TREE_CODE (stmt) == COND_EXPR)
 180     {
 181       /* If we perform unswitching, force the operands of the invariant
 182          condition to be moved out of the loop.  */
 183       get_stmt_operands (stmt);
 184
 185       return MOVE_POSSIBLE;
 186     }
 187
 188   if (TREE_CODE (stmt) != MODIFY_EXPR)
 189     return MOVE_IMPOSSIBLE;
 190
 191   if (stmt_ends_bb_p (stmt))
 192     return MOVE_IMPOSSIBLE;
 193
 194   get_stmt_operands (stmt);
 195
 196   if (stmt_ann (stmt)->has_volatile_ops)
 197     return MOVE_IMPOSSIBLE;
 198
 199   lhs = TREE_OPERAND (stmt, 0);
 200   if (TREE_CODE (lhs) == SSA_NAME
 201       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 202     return MOVE_IMPOSSIBLE;
 203
 204   rhs = TREE_OPERAND (stmt, 1);
 205
 206   if (TREE_SIDE_EFFECTS (rhs))
 207     return MOVE_IMPOSSIBLE;
 208
 209   if (TREE_CODE (lhs) != SSA_NAME
 210       || tree_could_trap_p (rhs))
 211     return MOVE_PRESERVE_EXECUTION;
 212
 213   return MOVE_POSSIBLE;
 214 }
 215
 216 /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
 217    loop to that we could move the expresion using DEF if it did not have
 218    other operands, i.e. the outermost loop enclosing LOOP in that the value
 219    of DEF is invariant.  */
 220
 221 static struct loop *
 222 outermost_invariant_loop (tree def, struct loop *loop)
 223 {
 224   tree def_stmt;
 225   basic_block def_bb;
 226   struct loop *max_loop;
 227
 228   if (TREE_CODE (def) != SSA_NAME)
 229     return superloop_at_depth (loop, 1);
 230
 231   def_stmt = SSA_NAME_DEF_STMT (def);
 232   def_bb = bb_for_stmt (def_stmt);
 233   if (!def_bb)
 234     return superloop_at_depth (loop, 1);
 235
 236   max_loop = find_common_loop (loop, def_bb->loop_father);
 237
 238   if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
 239     max_loop = find_common_loop (max_loop,
 240                                  LIM_DATA (def_stmt)->max_loop->outer);
 241   if (max_loop == loop)
 242     return NULL;
 243   max_loop = superloop_at_depth (loop, max_loop->depth + 1);
 244
 245   return max_loop;
 246 }
 247
 248 /* Returns the outermost superloop of LOOP in that the expression EXPR is
 249    invariant.  */
 250
 251 static struct loop *
 252 outermost_invariant_loop_expr (tree expr, struct loop *loop)
 253 {
 254   char class = TREE_CODE_CLASS (TREE_CODE (expr));
 255   unsigned i, nops;
 256   struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
 257
 258   if (TREE_CODE (expr) == SSA_NAME
 259       || TREE_CODE (expr) == INTEGER_CST
 260       || is_gimple_min_invariant (expr))
 261     return outermost_invariant_loop (expr, loop);
 262
 263   if (class != '1'
 264       && class != '2'
 265       && class != 'e'
 266       && class != '<')
 267     return NULL;
 268
 269   nops = first_rtl_op (TREE_CODE (expr));
 270   for (i = 0; i < nops; i++)
 271     {
 272       aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
 273       if (!aloop)
 274         return NULL;
 275
 276       if (flow_loop_nested_p (max_loop, aloop))
 277         max_loop = aloop;
 278     }
 279
 280   return max_loop;
 281 }
 282
 283 /* DATA is a structure containing information associated with a statement
 284    inside LOOP.  DEF is one of the operands of this statement.
 285
 286    Find the outermost loop enclosing LOOP in that value of DEF is invariant
 287    and record this in DATA->max_loop field.  If DEF itself is defined inside
 288    this loop as well (i.e. we need to hoist it out of the loop if we want
 289    to hoist the statement represented by DATA), record the statement in that
 290    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
 291    add the cost of the computation of DEF to the DATA->cost.
 292
 293    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
 294
 295 static bool
 296 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
 297                 bool add_cost)
 298 {
 299   tree def_stmt = SSA_NAME_DEF_STMT (def);
 300   basic_block def_bb = bb_for_stmt (def_stmt);
 301   struct loop *max_loop;
 302   struct depend *dep;
 303
 304   if (!def_bb)
 305     return true;
 306
 307   max_loop = outermost_invariant_loop (def, loop);
 308   if (!max_loop)
 309     return false;
 310
 311   if (flow_loop_nested_p (data->max_loop, max_loop))
 312     data->max_loop = max_loop;
 313
 314   if (!LIM_DATA (def_stmt))
 315     return true;
 316
 317   if (add_cost
 318       /* Only add the cost if the statement defining DEF is inside LOOP,
 319          i.e. if it is likely that by moving the invariants dependent
 320          on it, we will be able to avoid creating a new register for
 321          it (since it will be only used in these dependent invariants).  */
 322       && def_bb->loop_father == loop)
 323     data->cost += LIM_DATA (def_stmt)->cost;
 324
 325   dep = xmalloc (sizeof (struct depend));
 326   dep->stmt = def_stmt;
 327   dep->next = data->depends;
 328   data->depends = dep;
 329
 330   return true;
 331 }
 332
 333 /* Returns an estimate for a cost of statement STMT.  TODO -- the values here
 334    are just ad-hoc constants.  The estimates should be based on target-specific
 335    values.  */
 336
 337 static unsigned
 338 stmt_cost (tree stmt)
 339 {
 340   tree lhs, rhs;
 341   unsigned cost = 1;
 342
 343   /* Always try to create possibilities for unswitching.  */
 344   if (TREE_CODE (stmt) == COND_EXPR)
 345     return LIM_EXPENSIVE;
 346
 347   lhs = TREE_OPERAND (stmt, 0);
 348   rhs = TREE_OPERAND (stmt, 1);
 349
 350   /* Hoisting memory references out should almost surely be a win.  */
 351   if (!is_gimple_variable (lhs))
 352     cost += 20;
 353   if (is_gimple_addressable (rhs) && !is_gimple_variable (rhs))
 354     cost += 20;
 355
 356   switch (TREE_CODE (rhs))
 357     {
 358     case CALL_EXPR:
 359       /* We should be hoisting calls if possible.  */
 360
 361       /* Unless the call is a builtin_constant_p; this always folds to a
 362          constant, so moving it is useless.  */
 363       rhs = get_callee_fndecl (rhs);
 364       if (DECL_BUILT_IN (rhs)
 365           && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
 366         return 0;
 367
 368       cost += 20;
 369       break;
 370
 371     case MULT_EXPR:
 372     case TRUNC_DIV_EXPR:
 373     case CEIL_DIV_EXPR:
 374     case FLOOR_DIV_EXPR:
 375     case ROUND_DIV_EXPR:
 376     case EXACT_DIV_EXPR:
 377     case CEIL_MOD_EXPR:
 378     case FLOOR_MOD_EXPR:
 379     case ROUND_MOD_EXPR:
 380     case TRUNC_MOD_EXPR:
 381       /* Division and multiplication are usually expensive.  */
 382       cost += 20;
 383       break;
 384
 385     default:
 386       break;
 387     }
 388
 389   return cost;
 390 }
 391
 392 /* Determine the outermost loop to that it is possible to hoist a statement
 393    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 394    the outermost loop in that the value computed by STMT is invariant.
 395    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 396    we preserve the fact whether STMT is executed.  It also fills other related
 397    information to LIM_DATA (STMT).
 398
 399    The function returns false if STMT cannot be hoisted outside of the loop it
 400    is defined in, and true otherwise.  */
 401
 402 static bool
 403 determine_max_movement (tree stmt, bool must_preserve_exec)
 404 {
 405   basic_block bb = bb_for_stmt (stmt);
 406   struct loop *loop = bb->loop_father;
 407   struct loop *level;
 408   struct lim_aux_data *lim_data = LIM_DATA (stmt);
 409   use_optype uses;
 410   vuse_optype vuses;
 411   v_may_def_optype v_may_defs;
 412   stmt_ann_t ann = stmt_ann (stmt);
 413   unsigned i;
 414
 415   if (must_preserve_exec)
 416     level = ALWAYS_EXECUTED_IN (bb);
 417   else
 418     level = superloop_at_depth (loop, 1);
 419   lim_data->max_loop = level;
 420
 421   uses = USE_OPS (ann);
 422   for (i = 0; i < NUM_USES (uses); i++)
 423     if (!add_dependency (USE_OP (uses, i), lim_data, loop, true))
 424       return false;
 425
 426   vuses = VUSE_OPS (ann);
 427   for (i = 0; i < NUM_VUSES (vuses); i++)
 428     if (!add_dependency (VUSE_OP (vuses, i), lim_data, loop, false))
 429       return false;
 430
 431   v_may_defs = V_MAY_DEF_OPS (ann);
 432   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 433     if (!add_dependency (V_MAY_DEF_OP (v_may_defs, i), lim_data, loop, false))
 434       return false;
 435
 436   lim_data->cost += stmt_cost (stmt);
 437
 438   return true;
 439 }
 440
 441 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
 442    and that one of the operands of this statement is computed by STMT.
 443    Ensure that STMT (together with all the statements that define its
 444    operands) is hoisted at least out of the loop LEVEL.  */
 445
 446 static void
 447 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
 448 {
 449   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
 450   struct depend *dep;
 451
 452   stmt_loop = find_common_loop (orig_loop, stmt_loop);
 453   if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
 454     stmt_loop = find_common_loop (stmt_loop,
 455                                   LIM_DATA (stmt)->tgt_loop->outer);
 456   if (flow_loop_nested_p (stmt_loop, level))
 457     return;
 458
 459   if (!LIM_DATA (stmt))
 460     abort ();
 461
 462   if (level != LIM_DATA (stmt)->max_loop
 463       && !flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level))
 464     abort ();
 465
 466   LIM_DATA (stmt)->tgt_loop = level;
 467   for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
 468     set_level (dep->stmt, orig_loop, level);
 469 }
 470
 471 /* Determines an outermost loop from that we want to hoist the statement STMT.
 472    For now we chose the outermost possible loop.  TODO -- use profiling
 473    information to set it more sanely.  */
 474
 475 static void
 476 set_profitable_level (tree stmt)
 477 {
 478   set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
 479 }
 480
 481 /* Returns true if STMT is not a pure call.  */
 482
 483 static bool
 484 nonpure_call_p (tree stmt)
 485 {
 486   tree call = get_call_expr_in (stmt);
 487
 488   if (!call)
 489     return false;
 490
 491   return TREE_SIDE_EFFECTS (call) != 0;
 492 }
 493
 494 /* Releases the memory occupied by DATA.  */
 495
 496 static void
 497 free_lim_aux_data (struct lim_aux_data *data)
 498 {
 499   struct depend *dep, *next;
 500
 501   for (dep = data->depends; dep; dep = next)
 502     {
 503       next = dep->next;
 504       free (dep);
 505     }
 506   free (data);
 507 }
 508
 509 /* Determine the outermost loops in that statements in basic block BB are
 510    invariant, and record them to the LIM_DATA associated with the statements.
 511    Callback for walk_dominator_tree.  */
 512
 513 static void
 514 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 515                               basic_block bb)
 516 {
 517   enum move_pos pos;
 518   block_stmt_iterator bsi;
 519   tree stmt;
 520   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
 521   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
 522
 523   if (!bb->loop_father->outer)
 524     return;
 525
 526   if (dump_file && (dump_flags & TDF_DETAILS))
 527     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 528              bb->index, bb->loop_father->num, bb->loop_father->depth);
 529
 530   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 531     {
 532       stmt = bsi_stmt (bsi);
 533
 534       pos = movement_possibility (stmt);
 535       if (pos == MOVE_IMPOSSIBLE)
 536         {
 537           if (nonpure_call_p (stmt))
 538             {
 539               maybe_never = true;
 540               outermost = NULL;
 541             }
 542           continue;
 543         }
 544
 545       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
 546       LIM_DATA (stmt)->always_executed_in = outermost;
 547
 548       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
 549         continue;
 550
 551       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
 552         {
 553           LIM_DATA (stmt)->max_loop = NULL;
 554           continue;
 555         }
 556
 557       if (dump_file && (dump_flags & TDF_DETAILS))
 558         {
 559           print_generic_stmt_indented (dump_file, stmt, 0, 2);
 560           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
 561                    LIM_DATA (stmt)->max_loop->depth,
 562                    LIM_DATA (stmt)->cost);
 563         }
 564
 565       if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
 566         set_profitable_level (stmt);
 567     }
 568 }
 569
 570 /* For each statement determines the outermost loop in that it is invariant,
 571    statements on whose motion it depends and the cost of the computation.
 572    This information is stored to the LIM_DATA structure associated with
 573    each statement.  */
 574
 575 static void
 576 determine_invariantness (void)
 577 {
 578   struct dom_walk_data walk_data;
 579
 580   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 581   walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
 582
 583   init_walk_dominator_tree (&walk_data);
 584   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 585   fini_walk_dominator_tree (&walk_data);
 586 }
 587
 588 /* Commits edge insertions and updates loop structures.  */
 589
 590 void
 591 loop_commit_inserts (void)
 592 {
 593   unsigned old_last_basic_block, i;
 594   basic_block bb;
 595
 596   old_last_basic_block = last_basic_block;
 597   bsi_commit_edge_inserts (NULL);
 598   for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
 599     {
 600       bb = BASIC_BLOCK (i);
 601       add_bb_to_loop (bb,
 602                       find_common_loop (bb->succ->dest->loop_father,
 603                                         bb->pred->src->loop_father));
 604     }
 605 }
 606
 607 /* Hoist the statements in basic block BB out of the loops prescribed by
 608    data stored in LIM_DATA structres associated with each statement.  Callback
 609    for walk_dominator_tree.  */
 610
 611 static void
 612 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 613                         basic_block bb)
 614 {
 615   struct loop *level;
 616   block_stmt_iterator bsi;
 617   tree stmt;
 618   unsigned cost = 0;
 619
 620   if (!bb->loop_father->outer)
 621     return;
 622
 623   for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 624     {
 625       stmt = bsi_stmt (bsi);
 626
 627       if (!LIM_DATA (stmt))
 628         {
 629           bsi_next (&bsi);
 630           continue;
 631         }
 632
 633       cost = LIM_DATA (stmt)->cost;
 634       level = LIM_DATA (stmt)->tgt_loop;
 635       free_lim_aux_data (LIM_DATA (stmt));
 636       stmt_ann (stmt)->common.aux = NULL;
 637
 638       if (!level)
 639         {
 640           bsi_next (&bsi);
 641           continue;
 642         }
 643
 644       /* We do not really want to move conditionals out of the loop; we just
 645          placed it here to force its operands to be moved if necessary.  */
 646       if (TREE_CODE (stmt) == COND_EXPR)
 647         continue;
 648
 649       if (dump_file && (dump_flags & TDF_DETAILS))
 650         {
 651           fprintf (dump_file, "Moving statement\n");
 652           print_generic_stmt (dump_file, stmt, 0);
 653           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
 654                    cost, level->num);
 655         }
 656       bsi_insert_on_edge (loop_preheader_edge (level), stmt);
 657       bsi_remove (&bsi);
 658     }
 659 }
 660
 661 /* Hoist the statements out of the loops prescribed by data stored in
 662    LIM_DATA structres associated with each statement.*/
 663
 664 static void
 665 move_computations (void)
 666 {
 667   struct dom_walk_data walk_data;
 668
 669   memset (&walk_data, 0, sizeof (struct dom_walk_data));
 670   walk_data.before_dom_children_before_stmts = move_computations_stmt;
 671
 672   init_walk_dominator_tree (&walk_data);
 673   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 674   fini_walk_dominator_tree (&walk_data);
 675
 676   loop_commit_inserts ();
 677   rewrite_into_ssa (false);
 678   bitmap_clear (vars_to_rename);
 679 }
 680
 681 /* Checks whether the statement defining variable *INDEX can be hoisted
 682    out of the loop passed in DATA.  Callback for for_each_index.  */
 683
 684 static bool
 685 may_move_till (tree ref, tree *index, void *data)
 686 {
 687   struct loop *loop = data, *max_loop;
 688
 689   /* If REF is an array reference, check also that the step and the lower
 690      bound is invariant in LOOP.  */
 691   if (TREE_CODE (ref) == ARRAY_REF)
 692     {
 693       tree step = array_ref_element_size (ref);
 694       tree lbound = array_ref_low_bound (ref);
 695
 696       max_loop = outermost_invariant_loop_expr (step, loop);
 697       if (!max_loop)
 698         return false;
 699
 700       max_loop = outermost_invariant_loop_expr (lbound, loop);
 701       if (!max_loop)
 702         return false;
 703     }
 704
 705   max_loop = outermost_invariant_loop (*index, loop);
 706   if (!max_loop)
 707     return false;
 708
 709   return true;
 710 }
 711
 712 /* Forces statements definining (invariant) SSA names in expression EXPR to be
 713    moved out of the LOOP.  */
 714
 715 static void
 716 force_move_till_expr (tree expr, struct loop *loop)
 717 {
 718   char class = TREE_CODE_CLASS (TREE_CODE (expr));
 719   unsigned i, nops;
 720
 721   if (TREE_CODE (expr) == SSA_NAME)
 722     {
 723       tree stmt = SSA_NAME_DEF_STMT (expr);
 724       if (IS_EMPTY_STMT (stmt))
 725         return;
 726
 727       set_level (stmt, bb_for_stmt (stmt)->loop_father, loop);
 728       return;
 729     }
 730
 731   if (class != '1'
 732       && class != '2'
 733       && class != 'e'
 734       && class != '<')
 735     return;
 736
 737   nops = first_rtl_op (TREE_CODE (expr));
 738   for (i = 0; i < nops; i++)
 739     force_move_till_expr (TREE_OPERAND (expr, i), loop);
 740 }
 741
 742 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 743    the loop passed in DATA.  Callback for for_each_index.  */
 744
 745 static bool
 746 force_move_till (tree ref, tree *index, void *data)
 747 {
 748   tree stmt;
 749
 750   if (TREE_CODE (ref) == ARRAY_REF)
 751     {
 752       tree step = array_ref_element_size (ref);
 753       tree lbound = array_ref_low_bound (ref);
 754
 755       force_move_till_expr (step, data);
 756       force_move_till_expr (lbound, data);
 757     }
 758
 759   if (TREE_CODE (*index) != SSA_NAME)
 760     return true;
 761
 762   stmt = SSA_NAME_DEF_STMT (*index);
 763   if (IS_EMPTY_STMT (stmt))
 764     return true;
 765
 766   set_level (stmt, bb_for_stmt (stmt)->loop_father, data);
 767
 768   return true;
 769 }
 770
 771 /* Records memory reference *REF (that occurs in statement STMT)
 772    to the list MEM_REFS.  */
 773
 774 static void
 775 record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
 776 {
 777   struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
 778
 779   aref->stmt = stmt;
 780   aref->ref = ref;
 781
 782   aref->next = *mem_refs;
 783   *mem_refs = aref;
 784 }
 785
 786 /* Releases list of memory references MEM_REFS.  */
 787
 788 static void
 789 free_mem_refs (struct mem_ref *mem_refs)
 790 {
 791   struct mem_ref *act;
 792
 793   while (mem_refs)
 794     {
 795       act = mem_refs;
 796       mem_refs = mem_refs->next;
 797       free (act);
 798     }
 799 }
 800
 801 /* If VAR is defined in LOOP and the statement it is defined in does not belong
 802    to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
 803    to the set SEEN.  */
 804
 805 static void
 806 maybe_queue_var (tree var, struct loop *loop,
 807                  sbitmap seen, tree *queue, unsigned *in_queue)
 808 {
 809   tree stmt = SSA_NAME_DEF_STMT (var);
 810   basic_block def_bb = bb_for_stmt (stmt);
 811
 812   if (!def_bb
 813       || !flow_bb_inside_loop_p (loop, def_bb)
 814       || TEST_BIT (seen, stmt_ann (stmt)->uid))
 815     return;
 816
 817   SET_BIT (seen, stmt_ann (stmt)->uid);
 818   queue[(*in_queue)++] = stmt;
 819 }
 820
 821 /* Determine whether all memory references inside the LOOP that correspond
 822    to virtual ssa names defined in statement STMT are equal.
 823    If so, store the list of the references to MEM_REFS, and return one
 824    of them.  Otherwise store NULL to MEM_REFS and return NULL_TREE.  */
 825
 826 static tree
 827 single_reachable_address (struct loop *loop, tree stmt,
 828                           struct mem_ref **mem_refs)
 829 {
 830   tree *queue = xmalloc (sizeof (tree) * max_uid);
 831   sbitmap seen = sbitmap_alloc (max_uid);
 832   tree common_ref = NULL, *aref;
 833   unsigned in_queue = 1;
 834   dataflow_t df;
 835   unsigned i, n;
 836   v_may_def_optype v_may_defs;
 837   vuse_optype vuses;
 838
 839   sbitmap_zero (seen);
 840
 841   *mem_refs = NULL;
 842
 843   queue[0] = stmt;
 844   SET_BIT (seen, stmt_ann (stmt)->uid);
 845
 846   while (in_queue)
 847     {
 848       stmt = queue[--in_queue];
 849
 850       if (LIM_DATA (stmt)
 851           && LIM_DATA (stmt)->sm_done)
 852         goto fail;
 853
 854       switch (TREE_CODE (stmt))
 855         {
 856         case MODIFY_EXPR:
 857           aref = &TREE_OPERAND (stmt, 0);
 858           if (is_gimple_reg (*aref)
 859               || !is_gimple_lvalue (*aref))
 860             aref = &TREE_OPERAND (stmt, 1);
 861           if (is_gimple_reg (*aref)
 862               || !is_gimple_lvalue (*aref)
 863               || (common_ref && !operand_equal_p (*aref, common_ref, 0)))
 864             goto fail;
 865           common_ref = *aref;
 866
 867           record_mem_ref (mem_refs, stmt, aref);
 868
 869           /* Traverse also definitions of the VUSES (there may be other
 870              distinct from the one we used to get to this statement).  */
 871           v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
 872           for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 873             maybe_queue_var (V_MAY_DEF_OP (v_may_defs, i), loop,
 874                              seen, queue, &in_queue);
 875
 876           vuses = STMT_VUSE_OPS (stmt);
 877           for (i = 0; i < NUM_VUSES (vuses); i++)
 878             maybe_queue_var (VUSE_OP (vuses, i), loop,
 879                              seen, queue, &in_queue);
 880           break;
 881
 882         case PHI_NODE:
 883           for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
 884             maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
 885                              seen, queue, &in_queue);
 886           break;
 887
 888         default:
 889           goto fail;
 890         }
 891
 892       /* Find uses of virtual names.  */
 893       df = get_immediate_uses (stmt);
 894       n = num_immediate_uses (df);
 895
 896       for (i = 0; i < n; i++)
 897         {
 898           stmt = immediate_use (df, i);
 899
 900           if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
 901             continue;
 902
 903           if (TEST_BIT (seen, stmt_ann (stmt)->uid))
 904             continue;
 905           SET_BIT (seen, stmt_ann (stmt)->uid);
 906
 907           queue[in_queue++] = stmt;
 908         }
 909     }
 910
 911   free (queue);
 912   sbitmap_free (seen);
 913
 914   return common_ref;
 915
 916 fail:
 917   free_mem_refs (*mem_refs);
 918   *mem_refs = NULL;
 919   free (queue);
 920   sbitmap_free (seen);
 921
 922   return NULL;
 923 }
 924
 925 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
 926
 927 static void
 928 rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
 929 {
 930   v_may_def_optype v_may_defs;
 931   v_must_def_optype v_must_defs;
 932   vuse_optype vuses;
 933   unsigned i;
 934   tree var;
 935
 936   for (; mem_refs; mem_refs = mem_refs->next)
 937     {
 938       v_may_defs = STMT_V_MAY_DEF_OPS (mem_refs->stmt);
 939       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 940         {
 941           var = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
 942           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 943         }
 944
 945       v_must_defs = STMT_V_MUST_DEF_OPS (mem_refs->stmt);
 946       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 947         {
 948           var = SSA_NAME_VAR (V_MUST_DEF_OP (v_must_defs, i));
 949           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 950         }
 951
 952       vuses = STMT_VUSE_OPS (mem_refs->stmt);
 953       for (i = 0; i < NUM_VUSES (vuses); i++)
 954         {
 955           var = SSA_NAME_VAR (VUSE_OP (vuses, i));
 956           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 957         }
 958
 959       *mem_refs->ref = tmp_var;
 960       modify_stmt (mem_refs->stmt);
 961     }
 962 }
 963
 964 /* Records request for store motion of memory reference REF from LOOP.
 965    MEM_REFS is the list of occurences of the reference REF inside LOOP;
 966    these references are rewritten by a new temporary variable.
 967    Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
 968    The initialization of the temporary variable is put to the preheader
 969    of the loop, and assignments to the reference from the temporary variable
 970    are emitted to exits.  */
 971
 972 static void
 973 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
 974              struct mem_ref *mem_refs)
 975 {
 976   struct mem_ref *aref;
 977   tree tmp_var;
 978   unsigned i;
 979   tree load, store;
 980
 981   tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
 982
 983   for_each_index (&ref, force_move_till, loop);
 984
 985   rewrite_mem_refs (tmp_var, mem_refs);
 986   for (aref = mem_refs; aref; aref = aref->next)
 987     if (LIM_DATA (aref->stmt))
 988       LIM_DATA (aref->stmt)->sm_done = true;
 989
 990   /* Emit the load & stores.  */
 991   load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
 992   modify_stmt (load);
 993   stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
 994   LIM_DATA (load)->max_loop = loop;
 995   LIM_DATA (load)->tgt_loop = loop;
 996
 997   /* Put this into the latch, so that we are sure it will be processed after
 998      all dependencies.  */
 999   bsi_insert_on_edge (loop_latch_edge (loop), load);
1000
1001   for (i = 0; i < n_exits; i++)
1002     {
1003       store = build (MODIFY_EXPR, void_type_node,
1004                      unshare_expr (ref), tmp_var);
1005       bsi_insert_on_edge (exits[i], store);
1006     }
1007 }
1008
1009 /* Determine whether all memory references inside LOOP corresponding to the
1010    virtual ssa name REG are equal to each other, and whether the address of
1011    this common reference can be hoisted outside of the loop.  If this is true,
1012    prepare the statements that load the value of the memory reference to a
1013    temporary variable in the loop preheader, store it back on the loop exits,
1014    and replace all the references inside LOOP by this temporary variable.
1015    LOOP has N_EXITS stored in EXITS.  */
1016
1017 static void
1018 determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
1019 {
1020   tree ref;
1021   struct mem_ref *mem_refs, *aref;
1022   struct loop *must_exec;
1023
1024   if (is_gimple_reg (reg))
1025     return;
1026
1027   ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs);
1028   if (!ref)
1029     return;
1030
1031   if (!for_each_index (&ref, may_move_till, loop))
1032     {
1033       free_mem_refs (mem_refs);
1034       return;
1035     }
1036
1037   if (tree_could_trap_p (ref))
1038     {
1039       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1040          of the statements in that it occurs is always executed when the loop
1041          is entered.  This way we know that by moving the load from the
1042          reference out of the loop we will not cause the error that would not
1043          occur otherwise.
1044
1045          TODO -- in fact we would like to check for anticipability of the
1046          reference, i.e. that on each path from loop entry to loop exit at
1047          least one of the statements containing the memory reference is
1048          executed.  */
1049
1050       for (aref = mem_refs; aref; aref = aref->next)
1051         {
1052           if (!LIM_DATA (aref->stmt))
1053             continue;
1054
1055           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1056           if (!must_exec)
1057             continue;
1058
1059           if (must_exec == loop
1060               || flow_loop_nested_p (must_exec, loop))
1061             break;
1062         }
1063
1064       if (!aref)
1065         {
1066           free_mem_refs (mem_refs);
1067           return;
1068         }
1069     }
1070
1071   schedule_sm (loop, exits, n_exits, ref, mem_refs);
1072   free_mem_refs (mem_refs);
1073 }
1074
1075 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1076    for a store motion optimization (i.e. whether we can insert statement
1077    on its exits).  */
1078
1079 static bool
1080 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1081                       unsigned n_exits)
1082 {
1083   unsigned i;
1084
1085   for (i = 0; i < n_exits; i++)
1086     if (exits[i]->flags & EDGE_ABNORMAL)
1087       return false;
1088
1089   return true;
1090 }
1091
1092 /* Try to perform store motion for all memory references modified inside
1093    LOOP.  */
1094
1095 static void
1096 determine_lsm_loop (struct loop *loop)
1097 {
1098   tree phi;
1099   unsigned n_exits;
1100   edge *exits = get_loop_exit_edges (loop, &n_exits);
1101
1102   if (!loop_suitable_for_sm (loop, exits, n_exits))
1103     {
1104       free (exits);
1105       return;
1106     }
1107
1108   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
1109     determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
1110
1111   free (exits);
1112 }
1113
1114 /* Try to perform store motion for all memory references modified inside
1115    any of LOOPS.  */
1116
1117 static void
1118 determine_lsm (struct loops *loops)
1119 {
1120   struct loop *loop;
1121   basic_block bb;
1122
1123   /* Create a UID for each statement in the function.  Ordering of the
1124      UIDs is not important for this pass.  */
1125   max_uid = 0;
1126   FOR_EACH_BB (bb)
1127     {
1128       block_stmt_iterator bsi;
1129       tree phi;
1130
1131       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1132         stmt_ann (bsi_stmt (bsi))->uid = max_uid++;
1133
1134       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1135         stmt_ann (phi)->uid = max_uid++;
1136     }
1137
1138   compute_immediate_uses (TDFA_USE_VOPS, NULL);
1139
1140   /* Pass the loops from the outermost.  For each virtual operand loop phi node
1141      check whether all the references inside the loop correspond to a single
1142      address, and if so, move them.  */
1143
1144   loop = loops->tree_root->inner;
1145   while (1)
1146     {
1147       determine_lsm_loop (loop);
1148
1149       if (loop->inner)
1150         {
1151           loop = loop->inner;
1152           continue;
1153         }
1154       while (!loop->next)
1155         {
1156           loop = loop->outer;
1157           if (loop == loops->tree_root)
1158             {
1159               free_df ();
1160               loop_commit_inserts ();
1161               return;
1162             }
1163         }
1164       loop = loop->next;
1165     }
1166 }
1167
1168 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1169    for each such basic block bb records the outermost loop for that execution
1170    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1171    blocks that contain a nonpure call.  */
1172
1173 static void
1174 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1175 {
1176   basic_block bb = NULL, *bbs, last = NULL;
1177   unsigned i;
1178   edge e;
1179   struct loop *inn_loop = loop;
1180
1181   if (!loop->header->aux)
1182     {
1183       bbs = get_loop_body_in_dom_order (loop);
1184
1185       for (i = 0; i < loop->num_nodes; i++)
1186         {
1187           bb = bbs[i];
1188
1189           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1190             last = bb;
1191
1192           if (TEST_BIT (contains_call, bb->index))
1193             break;
1194
1195           for (e = bb->succ; e; e = e->succ_next)
1196             if (!flow_bb_inside_loop_p (loop, e->dest))
1197               break;
1198           if (e)
1199             break;
1200
1201           /* A loop might be infinite (TODO use simple loop analysis
1202              to disprove this if possible).  */
1203           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1204             break;
1205
1206           if (!flow_bb_inside_loop_p (inn_loop, bb))
1207             break;
1208
1209           if (bb->loop_father->header == bb)
1210             {
1211               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1212                 break;
1213
1214               /* In a loop that is always entered we may proceed anyway.
1215                  But record that we entered it and stop once we leave it.  */
1216               inn_loop = bb->loop_father;
1217             }
1218         }
1219
1220       while (1)
1221         {
1222           last->aux = loop;
1223           if (last == loop->header)
1224             break;
1225           last = get_immediate_dominator (CDI_DOMINATORS, last);
1226         }
1227
1228       free (bbs);
1229     }
1230
1231   for (loop = loop->inner; loop; loop = loop->next)
1232     fill_always_executed_in (loop, contains_call);
1233 }
1234
1235 /* Compute the global information needed by the loop invariant motion pass.
1236    LOOPS is the loop tree.  */
1237
1238 static void
1239 tree_ssa_lim_initialize (struct loops *loops)
1240 {
1241   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1242   block_stmt_iterator bsi;
1243   struct loop *loop;
1244   basic_block bb;
1245
1246   sbitmap_zero (contains_call);
1247   FOR_EACH_BB (bb)
1248     {
1249       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1250         {
1251           if (nonpure_call_p (bsi_stmt (bsi)))
1252             break;
1253         }
1254
1255       if (!bsi_end_p (bsi))
1256         SET_BIT (contains_call, bb->index);
1257     }
1258
1259   for (loop = loops->tree_root->inner; loop; loop = loop->next)
1260     fill_always_executed_in (loop, contains_call);
1261
1262   sbitmap_free (contains_call);
1263 }
1264
1265 /* Cleans up after the invariant motion pass.  */
1266
1267 static void
1268 tree_ssa_lim_finalize (void)
1269 {
1270   basic_block bb;
1271
1272   FOR_EACH_BB (bb)
1273     {
1274       bb->aux = NULL;
1275     }
1276 }
1277
1278 /* Moves invariants from LOOPS.  Only "expensive" invariants are moved out --
1279    i.e. those that are likely to be win regardless of the register pressure.  */
1280
1281 void
1282 tree_ssa_lim (struct loops *loops)
1283 {
1284   tree_ssa_lim_initialize (loops);
1285
1286   /* For each statement determine the outermost loop in that it is
1287      invariant and cost for computing the invariant.  */
1288   determine_invariantness ();
1289
1290   /* For each memory reference determine whether it is possible to hoist it
1291      out of the loop.  Force the necessary invariants to be moved out of the
1292      loops as well.  */
1293   determine_lsm (loops);
1294
1295   /* Move the expressions that are expensive enough.  */
1296   move_computations ();
1297
1298   tree_ssa_lim_finalize ();
1299 }