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.  ORIG_LOOP is the loop in that EXPR is used.  */
 714
 715 static void
 716 force_move_till_expr (tree expr, struct loop *orig_loop, 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, orig_loop, 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), orig_loop, loop);
 740 }
 741
 742 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 743    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
 744    for_each_index.  */
 745
 746 struct fmt_data
 747 {
 748   struct loop *loop;
 749   struct loop *orig_loop;
 750 };
 751
 752 static bool
 753 force_move_till (tree ref, tree *index, void *data)
 754 {
 755   tree stmt;
 756   struct fmt_data *fmt_data = data;
 757
 758   if (TREE_CODE (ref) == ARRAY_REF)
 759     {
 760       tree step = array_ref_element_size (ref);
 761       tree lbound = array_ref_low_bound (ref);
 762
 763       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
 764       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
 765     }
 766
 767   if (TREE_CODE (*index) != SSA_NAME)
 768     return true;
 769
 770   stmt = SSA_NAME_DEF_STMT (*index);
 771   if (IS_EMPTY_STMT (stmt))
 772     return true;
 773
 774   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
 775
 776   return true;
 777 }
 778
 779 /* Records memory reference *REF (that occurs in statement STMT)
 780    to the list MEM_REFS.  */
 781
 782 static void
 783 record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
 784 {
 785   struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
 786
 787   aref->stmt = stmt;
 788   aref->ref = ref;
 789
 790   aref->next = *mem_refs;
 791   *mem_refs = aref;
 792 }
 793
 794 /* Releases list of memory references MEM_REFS.  */
 795
 796 static void
 797 free_mem_refs (struct mem_ref *mem_refs)
 798 {
 799   struct mem_ref *act;
 800
 801   while (mem_refs)
 802     {
 803       act = mem_refs;
 804       mem_refs = mem_refs->next;
 805       free (act);
 806     }
 807 }
 808
 809 /* If VAR is defined in LOOP and the statement it is defined in does not belong
 810    to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
 811    to the set SEEN.  */
 812
 813 static void
 814 maybe_queue_var (tree var, struct loop *loop,
 815                  sbitmap seen, tree *queue, unsigned *in_queue)
 816 {
 817   tree stmt = SSA_NAME_DEF_STMT (var);
 818   basic_block def_bb = bb_for_stmt (stmt);
 819
 820   if (!def_bb
 821       || !flow_bb_inside_loop_p (loop, def_bb)
 822       || TEST_BIT (seen, stmt_ann (stmt)->uid))
 823     return;
 824
 825   SET_BIT (seen, stmt_ann (stmt)->uid);
 826   queue[(*in_queue)++] = stmt;
 827 }
 828
 829 /* Determine whether all memory references inside the LOOP that correspond
 830    to virtual ssa names defined in statement STMT are equal.
 831    If so, store the list of the references to MEM_REFS, and return one
 832    of them.  Otherwise store NULL to MEM_REFS and return NULL_TREE.  */
 833
 834 static tree
 835 single_reachable_address (struct loop *loop, tree stmt,
 836                           struct mem_ref **mem_refs)
 837 {
 838   tree *queue = xmalloc (sizeof (tree) * max_uid);
 839   sbitmap seen = sbitmap_alloc (max_uid);
 840   tree common_ref = NULL, *aref;
 841   unsigned in_queue = 1;
 842   dataflow_t df;
 843   unsigned i, n;
 844   v_may_def_optype v_may_defs;
 845   vuse_optype vuses;
 846
 847   sbitmap_zero (seen);
 848
 849   *mem_refs = NULL;
 850
 851   queue[0] = stmt;
 852   SET_BIT (seen, stmt_ann (stmt)->uid);
 853
 854   while (in_queue)
 855     {
 856       stmt = queue[--in_queue];
 857
 858       if (LIM_DATA (stmt)
 859           && LIM_DATA (stmt)->sm_done)
 860         goto fail;
 861
 862       switch (TREE_CODE (stmt))
 863         {
 864         case MODIFY_EXPR:
 865           aref = &TREE_OPERAND (stmt, 0);
 866           if (is_gimple_reg (*aref)
 867               || !is_gimple_lvalue (*aref))
 868             aref = &TREE_OPERAND (stmt, 1);
 869           if (is_gimple_reg (*aref)
 870               || !is_gimple_lvalue (*aref)
 871               || (common_ref && !operand_equal_p (*aref, common_ref, 0)))
 872             goto fail;
 873           common_ref = *aref;
 874
 875           record_mem_ref (mem_refs, stmt, aref);
 876
 877           /* Traverse also definitions of the VUSES (there may be other
 878              distinct from the one we used to get to this statement).  */
 879           v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
 880           for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 881             maybe_queue_var (V_MAY_DEF_OP (v_may_defs, i), loop,
 882                              seen, queue, &in_queue);
 883
 884           vuses = STMT_VUSE_OPS (stmt);
 885           for (i = 0; i < NUM_VUSES (vuses); i++)
 886             maybe_queue_var (VUSE_OP (vuses, i), loop,
 887                              seen, queue, &in_queue);
 888           break;
 889
 890         case PHI_NODE:
 891           for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
 892             maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
 893                              seen, queue, &in_queue);
 894           break;
 895
 896         default:
 897           goto fail;
 898         }
 899
 900       /* Find uses of virtual names.  */
 901       df = get_immediate_uses (stmt);
 902       n = num_immediate_uses (df);
 903
 904       for (i = 0; i < n; i++)
 905         {
 906           stmt = immediate_use (df, i);
 907
 908           if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
 909             continue;
 910
 911           if (TEST_BIT (seen, stmt_ann (stmt)->uid))
 912             continue;
 913           SET_BIT (seen, stmt_ann (stmt)->uid);
 914
 915           queue[in_queue++] = stmt;
 916         }
 917     }
 918
 919   free (queue);
 920   sbitmap_free (seen);
 921
 922   return common_ref;
 923
 924 fail:
 925   free_mem_refs (*mem_refs);
 926   *mem_refs = NULL;
 927   free (queue);
 928   sbitmap_free (seen);
 929
 930   return NULL;
 931 }
 932
 933 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
 934
 935 static void
 936 rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
 937 {
 938   v_may_def_optype v_may_defs;
 939   v_must_def_optype v_must_defs;
 940   vuse_optype vuses;
 941   unsigned i;
 942   tree var;
 943
 944   for (; mem_refs; mem_refs = mem_refs->next)
 945     {
 946       v_may_defs = STMT_V_MAY_DEF_OPS (mem_refs->stmt);
 947       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 948         {
 949           var = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i));
 950           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 951         }
 952
 953       v_must_defs = STMT_V_MUST_DEF_OPS (mem_refs->stmt);
 954       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 955         {
 956           var = SSA_NAME_VAR (V_MUST_DEF_OP (v_must_defs, i));
 957           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 958         }
 959
 960       vuses = STMT_VUSE_OPS (mem_refs->stmt);
 961       for (i = 0; i < NUM_VUSES (vuses); i++)
 962         {
 963           var = SSA_NAME_VAR (VUSE_OP (vuses, i));
 964           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 965         }
 966
 967       *mem_refs->ref = tmp_var;
 968       modify_stmt (mem_refs->stmt);
 969     }
 970 }
 971
 972 /* Records request for store motion of memory reference REF from LOOP.
 973    MEM_REFS is the list of occurences of the reference REF inside LOOP;
 974    these references are rewritten by a new temporary variable.
 975    Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
 976    The initialization of the temporary variable is put to the preheader
 977    of the loop, and assignments to the reference from the temporary variable
 978    are emitted to exits.  */
 979
 980 static void
 981 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
 982              struct mem_ref *mem_refs)
 983 {
 984   struct mem_ref *aref;
 985   tree tmp_var;
 986   unsigned i;
 987   tree load, store;
 988   struct fmt_data fmt_data;
 989
 990   tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
 991
 992   fmt_data.loop = loop;
 993   fmt_data.orig_loop = loop;
 994   for_each_index (&ref, force_move_till, &fmt_data);
 995
 996   rewrite_mem_refs (tmp_var, mem_refs);
 997   for (aref = mem_refs; aref; aref = aref->next)
 998     if (LIM_DATA (aref->stmt))
 999       LIM_DATA (aref->stmt)->sm_done = true;
1000
1001   /* Emit the load & stores.  */
1002   load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
1003   modify_stmt (load);
1004   stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1005   LIM_DATA (load)->max_loop = loop;
1006   LIM_DATA (load)->tgt_loop = loop;
1007
1008   /* Put this into the latch, so that we are sure it will be processed after
1009      all dependencies.  */
1010   bsi_insert_on_edge (loop_latch_edge (loop), load);
1011
1012   for (i = 0; i < n_exits; i++)
1013     {
1014       store = build (MODIFY_EXPR, void_type_node,
1015                      unshare_expr (ref), tmp_var);
1016       bsi_insert_on_edge (exits[i], store);
1017     }
1018 }
1019
1020 /* Determine whether all memory references inside LOOP corresponding to the
1021    virtual ssa name REG are equal to each other, and whether the address of
1022    this common reference can be hoisted outside of the loop.  If this is true,
1023    prepare the statements that load the value of the memory reference to a
1024    temporary variable in the loop preheader, store it back on the loop exits,
1025    and replace all the references inside LOOP by this temporary variable.
1026    LOOP has N_EXITS stored in EXITS.  */
1027
1028 static void
1029 determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
1030 {
1031   tree ref;
1032   struct mem_ref *mem_refs, *aref;
1033   struct loop *must_exec;
1034
1035   if (is_gimple_reg (reg))
1036     return;
1037
1038   ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs);
1039   if (!ref)
1040     return;
1041
1042   if (!for_each_index (&ref, may_move_till, loop))
1043     {
1044       free_mem_refs (mem_refs);
1045       return;
1046     }
1047
1048   if (tree_could_trap_p (ref))
1049     {
1050       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1051          of the statements in that it occurs is always executed when the loop
1052          is entered.  This way we know that by moving the load from the
1053          reference out of the loop we will not cause the error that would not
1054          occur otherwise.
1055
1056          TODO -- in fact we would like to check for anticipability of the
1057          reference, i.e. that on each path from loop entry to loop exit at
1058          least one of the statements containing the memory reference is
1059          executed.  */
1060
1061       for (aref = mem_refs; aref; aref = aref->next)
1062         {
1063           if (!LIM_DATA (aref->stmt))
1064             continue;
1065
1066           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1067           if (!must_exec)
1068             continue;
1069
1070           if (must_exec == loop
1071               || flow_loop_nested_p (must_exec, loop))
1072             break;
1073         }
1074
1075       if (!aref)
1076         {
1077           free_mem_refs (mem_refs);
1078           return;
1079         }
1080     }
1081
1082   schedule_sm (loop, exits, n_exits, ref, mem_refs);
1083   free_mem_refs (mem_refs);
1084 }
1085
1086 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1087    for a store motion optimization (i.e. whether we can insert statement
1088    on its exits).  */
1089
1090 static bool
1091 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1092                       unsigned n_exits)
1093 {
1094   unsigned i;
1095
1096   for (i = 0; i < n_exits; i++)
1097     if (exits[i]->flags & EDGE_ABNORMAL)
1098       return false;
1099
1100   return true;
1101 }
1102
1103 /* Try to perform store motion for all memory references modified inside
1104    LOOP.  */
1105
1106 static void
1107 determine_lsm_loop (struct loop *loop)
1108 {
1109   tree phi;
1110   unsigned n_exits;
1111   edge *exits = get_loop_exit_edges (loop, &n_exits);
1112
1113   if (!loop_suitable_for_sm (loop, exits, n_exits))
1114     {
1115       free (exits);
1116       return;
1117     }
1118
1119   for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
1120     determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
1121
1122   free (exits);
1123 }
1124
1125 /* Try to perform store motion for all memory references modified inside
1126    any of LOOPS.  */
1127
1128 static void
1129 determine_lsm (struct loops *loops)
1130 {
1131   struct loop *loop;
1132   basic_block bb;
1133
1134   /* Create a UID for each statement in the function.  Ordering of the
1135      UIDs is not important for this pass.  */
1136   max_uid = 0;
1137   FOR_EACH_BB (bb)
1138     {
1139       block_stmt_iterator bsi;
1140       tree phi;
1141
1142       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1143         stmt_ann (bsi_stmt (bsi))->uid = max_uid++;
1144
1145       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1146         stmt_ann (phi)->uid = max_uid++;
1147     }
1148
1149   compute_immediate_uses (TDFA_USE_VOPS, NULL);
1150
1151   /* Pass the loops from the outermost.  For each virtual operand loop phi node
1152      check whether all the references inside the loop correspond to a single
1153      address, and if so, move them.  */
1154
1155   loop = loops->tree_root->inner;
1156   while (1)
1157     {
1158       determine_lsm_loop (loop);
1159
1160       if (loop->inner)
1161         {
1162           loop = loop->inner;
1163           continue;
1164         }
1165       while (!loop->next)
1166         {
1167           loop = loop->outer;
1168           if (loop == loops->tree_root)
1169             {
1170               free_df ();
1171               loop_commit_inserts ();
1172               return;
1173             }
1174         }
1175       loop = loop->next;
1176     }
1177 }
1178
1179 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1180    for each such basic block bb records the outermost loop for that execution
1181    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1182    blocks that contain a nonpure call.  */
1183
1184 static void
1185 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1186 {
1187   basic_block bb = NULL, *bbs, last = NULL;
1188   unsigned i;
1189   edge e;
1190   struct loop *inn_loop = loop;
1191
1192   if (!loop->header->aux)
1193     {
1194       bbs = get_loop_body_in_dom_order (loop);
1195
1196       for (i = 0; i < loop->num_nodes; i++)
1197         {
1198           bb = bbs[i];
1199
1200           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1201             last = bb;
1202
1203           if (TEST_BIT (contains_call, bb->index))
1204             break;
1205
1206           for (e = bb->succ; e; e = e->succ_next)
1207             if (!flow_bb_inside_loop_p (loop, e->dest))
1208               break;
1209           if (e)
1210             break;
1211
1212           /* A loop might be infinite (TODO use simple loop analysis
1213              to disprove this if possible).  */
1214           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1215             break;
1216
1217           if (!flow_bb_inside_loop_p (inn_loop, bb))
1218             break;
1219
1220           if (bb->loop_father->header == bb)
1221             {
1222               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1223                 break;
1224
1225               /* In a loop that is always entered we may proceed anyway.
1226                  But record that we entered it and stop once we leave it.  */
1227               inn_loop = bb->loop_father;
1228             }
1229         }
1230
1231       while (1)
1232         {
1233           last->aux = loop;
1234           if (last == loop->header)
1235             break;
1236           last = get_immediate_dominator (CDI_DOMINATORS, last);
1237         }
1238
1239       free (bbs);
1240     }
1241
1242   for (loop = loop->inner; loop; loop = loop->next)
1243     fill_always_executed_in (loop, contains_call);
1244 }
1245
1246 /* Compute the global information needed by the loop invariant motion pass.
1247    LOOPS is the loop tree.  */
1248
1249 static void
1250 tree_ssa_lim_initialize (struct loops *loops)
1251 {
1252   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1253   block_stmt_iterator bsi;
1254   struct loop *loop;
1255   basic_block bb;
1256
1257   sbitmap_zero (contains_call);
1258   FOR_EACH_BB (bb)
1259     {
1260       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1261         {
1262           if (nonpure_call_p (bsi_stmt (bsi)))
1263             break;
1264         }
1265
1266       if (!bsi_end_p (bsi))
1267         SET_BIT (contains_call, bb->index);
1268     }
1269
1270   for (loop = loops->tree_root->inner; loop; loop = loop->next)
1271     fill_always_executed_in (loop, contains_call);
1272
1273   sbitmap_free (contains_call);
1274 }
1275
1276 /* Cleans up after the invariant motion pass.  */
1277
1278 static void
1279 tree_ssa_lim_finalize (void)
1280 {
1281   basic_block bb;
1282
1283   FOR_EACH_BB (bb)
1284     {
1285       bb->aux = NULL;
1286     }
1287 }
1288
1289 /* Moves invariants from LOOPS.  Only "expensive" invariants are moved out --
1290    i.e. those that are likely to be win regardless of the register pressure.  */
1291
1292 void
1293 tree_ssa_lim (struct loops *loops)
1294 {
1295   tree_ssa_lim_initialize (loops);
1296
1297   /* For each statement determine the outermost loop in that it is
1298      invariant and cost for computing the invariant.  */
1299   determine_invariantness ();
1300
1301   /* For each memory reference determine whether it is possible to hoist it
1302      out of the loop.  Force the necessary invariants to be moved out of the
1303      loops as well.  */
1304   determine_lsm (loops);
1305
1306   /* Move the expressions that are expensive enough.  */
1307   move_computations ();
1308
1309   tree_ssa_lim_finalize ();
1310 }