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