gcc/tree-ssa-loop-manip.c

   1 /* High-level loop manipulation functions.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "tree-pass.h"
  37 #include "cfglayout.h"
  38 #include "tree-scalar-evolution.h"
  39
  40 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
  41    It is expected that neither BASE nor STEP are shared with other expressions
  42    (unless the sharing rules allow this).  Use VAR as a base var_decl for it
  43    (if NULL, a new temporary will be created).  The increment will occur at
  44    INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and
  45    AFTER can be computed using standard_iv_increment_position.  The ssa versions
  46    of the variable before and after increment will be stored in VAR_BEFORE and
  47    VAR_AFTER (unless they are NULL).  */
  48
  49 void
  50 create_iv (tree base, tree step, tree var, struct loop *loop,
  51            block_stmt_iterator *incr_pos, bool after,
  52            tree *var_before, tree *var_after)
  53 {
  54   tree stmt, initial, step1, stmts;
  55   tree vb, va;
  56   enum tree_code incr_op = PLUS_EXPR;
  57   edge pe = loop_preheader_edge (loop);
  58
  59   if (!var)
  60     {
  61       var = create_tmp_var (TREE_TYPE (base), "ivtmp");
  62       add_referenced_tmp_var (var);
  63     }
  64
  65   vb = make_ssa_name (var, NULL_TREE);
  66   if (var_before)
  67     *var_before = vb;
  68   va = make_ssa_name (var, NULL_TREE);
  69   if (var_after)
  70     *var_after = va;
  71
  72   /* For easier readability of the created code, produce MINUS_EXPRs
  73      when suitable.  */
  74   if (TREE_CODE (step) == INTEGER_CST)
  75     {
  76       if (TYPE_UNSIGNED (TREE_TYPE (step)))
  77         {
  78           step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
  79           if (tree_int_cst_lt (step1, step))
  80             {
  81               incr_op = MINUS_EXPR;
  82               step = step1;
  83             }
  84         }
  85       else
  86         {
  87           if (!tree_expr_nonnegative_p (step)
  88               && may_negate_without_overflow_p (step))
  89             {
  90               incr_op = MINUS_EXPR;
  91               step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
  92             }
  93         }
  94     }
  95
  96   /* Gimplify the step if necessary.  We put the computations in front of the
  97      loop (i.e. the step should be loop invariant).  */
  98   step = force_gimple_operand (step, &stmts, true, var);
  99   if (stmts)
 100     bsi_insert_on_edge_immediate_loop (pe, stmts);
 101
 102   stmt = build2 (MODIFY_EXPR, void_type_node, va,
 103                  build2 (incr_op, TREE_TYPE (base),
 104                          vb, step));
 105   SSA_NAME_DEF_STMT (va) = stmt;
 106   if (after)
 107     bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
 108   else
 109     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
 110
 111   initial = force_gimple_operand (base, &stmts, true, var);
 112   if (stmts)
 113     bsi_insert_on_edge_immediate_loop (pe, stmts);
 114
 115   stmt = create_phi_node (vb, loop->header);
 116   SSA_NAME_DEF_STMT (vb) = stmt;
 117   add_phi_arg (stmt, initial, loop_preheader_edge (loop));
 118   add_phi_arg (stmt, va, loop_latch_edge (loop));
 119 }
 120
 121 /* Add exit phis for the USE on EXIT.  */
 122
 123 static void
 124 add_exit_phis_edge (basic_block exit, tree use)
 125 {
 126   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
 127   basic_block def_bb = bb_for_stmt (def_stmt);
 128   struct loop *def_loop;
 129   edge e;
 130   edge_iterator ei;
 131
 132   /* Check that some of the edges entering the EXIT block exits a loop in
 133      that USE is defined.  */
 134   FOR_EACH_EDGE (e, ei, exit->preds)
 135     {
 136       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
 137       if (!flow_bb_inside_loop_p (def_loop, e->dest))
 138         break;
 139     }
 140
 141   if (!e)
 142     return;
 143
 144   phi = create_phi_node (use, exit);
 145   create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
 146   FOR_EACH_EDGE (e, ei, exit->preds)
 147     add_phi_arg (phi, use, e);
 148 }
 149
 150 /* Add exit phis for VAR that is used in LIVEIN.
 151    Exits of the loops are stored in EXITS.  */
 152
 153 static void
 154 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
 155 {
 156   bitmap def;
 157   unsigned index;
 158   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 159   bitmap_iterator bi;
 160
 161   if (is_gimple_reg (var))
 162     bitmap_clear_bit (livein, def_bb->index);
 163   else
 164     bitmap_set_bit (livein, def_bb->index);
 165
 166   def = BITMAP_ALLOC (NULL);
 167   bitmap_set_bit (def, def_bb->index);
 168   compute_global_livein (livein, def);
 169   BITMAP_FREE (def);
 170
 171   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
 172     {
 173       add_exit_phis_edge (BASIC_BLOCK (index), var);
 174     }
 175 }
 176
 177 /* Add exit phis for the names marked in NAMES_TO_RENAME.
 178    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
 179    names are used are stored in USE_BLOCKS.  */
 180
 181 static void
 182 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
 183 {
 184   unsigned i;
 185   bitmap_iterator bi;
 186
 187   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
 188     {
 189       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 190     }
 191 }
 192
 193 /* Returns a bitmap of all loop exit edge targets.  */
 194
 195 static bitmap
 196 get_loops_exits (void)
 197 {
 198   bitmap exits = BITMAP_ALLOC (NULL);
 199   basic_block bb;
 200   edge e;
 201   edge_iterator ei;
 202
 203   FOR_EACH_BB (bb)
 204     {
 205       FOR_EACH_EDGE (e, ei, bb->preds)
 206         if (e->src != ENTRY_BLOCK_PTR
 207             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 208           {
 209             bitmap_set_bit (exits, bb->index);
 210             break;
 211           }
 212     }
 213
 214   return exits;
 215 }
 216
 217 /* For USE in BB, if it is used outside of the loop it is defined in,
 218    mark it for rewrite.  Record basic block BB where it is used
 219    to USE_BLOCKS.  Record the ssa name index to NEED_PHIS bitmap.  */
 220
 221 static void
 222 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
 223                          bitmap need_phis)
 224 {
 225   unsigned ver;
 226   basic_block def_bb;
 227   struct loop *def_loop;
 228
 229   if (TREE_CODE (use) != SSA_NAME)
 230     return;
 231
 232   /* We don't need to keep virtual operands in loop-closed form.  */
 233   if (!is_gimple_reg (use))
 234     return;
 235
 236   ver = SSA_NAME_VERSION (use);
 237   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 238   if (!def_bb)
 239     return;
 240   def_loop = def_bb->loop_father;
 241
 242   /* If the definition is not inside loop, it is not interesting.  */
 243   if (!def_loop->outer)
 244     return;
 245
 246   if (!use_blocks[ver])
 247     use_blocks[ver] = BITMAP_ALLOC (NULL);
 248   bitmap_set_bit (use_blocks[ver], bb->index);
 249
 250   bitmap_set_bit (need_phis, ver);
 251 }
 252
 253 /* For uses in STMT, mark names that are used outside of the loop they are
 254    defined to rewrite.  Record the set of blocks in that the ssa
 255    names are defined to USE_BLOCKS and the ssa names themselves to
 256    NEED_PHIS.  */
 257
 258 static void
 259 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
 260 {
 261   ssa_op_iter iter;
 262   tree var;
 263   basic_block bb = bb_for_stmt (stmt);
 264
 265   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 266     find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 267 }
 268
 269 /* Marks names that are used in BB and outside of the loop they are
 270    defined in for rewrite.  Records the set of blocks in that the ssa
 271    names are defined to USE_BLOCKS.  Record the SSA names that will
 272    need exit PHIs in NEED_PHIS.  */
 273
 274 static void
 275 find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
 276 {
 277   block_stmt_iterator bsi;
 278   edge e;
 279   edge_iterator ei;
 280   tree phi;
 281
 282   FOR_EACH_EDGE (e, ei, bb->succs)
 283     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 284       find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
 285                                use_blocks, need_phis);
 286
 287   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 288     find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
 289 }
 290
 291 /* Marks names that are used outside of the loop they are defined in
 292    for rewrite.  Records the set of blocks in that the ssa
 293    names are defined to USE_BLOCKS.  If CHANGED_BBS is not NULL,
 294    scan only blocks in this set.  */
 295
 296 static void
 297 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
 298 {
 299   basic_block bb;
 300   unsigned index;
 301   bitmap_iterator bi;
 302
 303   if (changed_bbs && !bitmap_empty_p (changed_bbs))
 304     {
 305       EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
 306         {
 307           find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
 308         }
 309     }
 310   else
 311     {
 312       FOR_EACH_BB (bb)
 313         {
 314           find_uses_to_rename_bb (bb, use_blocks, need_phis);
 315         }
 316     }
 317 }
 318
 319 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 320    phi nodes to ensure that no variable is used outside the loop it is
 321    defined in.
 322
 323    This strengthening of the basic ssa form has several advantages:
 324
 325    1) Updating it during unrolling/peeling/versioning is trivial, since
 326       we do not need to care about the uses outside of the loop.
 327    2) The behavior of all uses of an induction variable is the same.
 328       Without this, you need to distinguish the case when the variable
 329       is used outside of the loop it is defined in, for example
 330
 331       for (i = 0; i < 100; i++)
 332         {
 333           for (j = 0; j < 100; j++)
 334             {
 335               k = i + j;
 336               use1 (k);
 337             }
 338           use2 (k);
 339         }
 340
 341       Looking from the outer loop with the normal SSA form, the first use of k
 342       is not well-behaved, while the second one is an induction variable with
 343       base 99 and step 1.
 344
 345       If CHANGED_BBS is not NULL, we look for uses outside loops only in
 346       the basic blocks in this set.
 347
 348       UPDATE_FLAG is used in the call to update_ssa.  See
 349       TODO_update_ssa* for documentation.  */
 350
 351 void
 352 rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 353 {
 354   bitmap loop_exits = get_loops_exits ();
 355   bitmap *use_blocks;
 356   unsigned i, old_num_ssa_names;
 357   bitmap names_to_rename = BITMAP_ALLOC (NULL);
 358
 359   /* If the pass has caused the SSA form to be out-of-date, update it
 360      now.  */
 361   update_ssa (update_flag);
 362
 363   old_num_ssa_names = num_ssa_names;
 364   use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap));
 365
 366   /* Find the uses outside loops.  */
 367   find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
 368
 369   /* Add the PHI nodes on exits of the loops for the names we need to
 370      rewrite.  */
 371   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 372
 373   for (i = 0; i < old_num_ssa_names; i++)
 374     BITMAP_FREE (use_blocks[i]);
 375   free (use_blocks);
 376   BITMAP_FREE (loop_exits);
 377   BITMAP_FREE (names_to_rename);
 378
 379   /* Fix up all the names found to be used outside their original
 380      loops.  */
 381   update_ssa (TODO_update_ssa);
 382 }
 383
 384 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 385
 386 static void
 387 check_loop_closed_ssa_use (basic_block bb, tree use)
 388 {
 389   tree def;
 390   basic_block def_bb;
 391
 392   if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
 393     return;
 394
 395   def = SSA_NAME_DEF_STMT (use);
 396   def_bb = bb_for_stmt (def);
 397   gcc_assert (!def_bb
 398               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 399 }
 400
 401 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 402
 403 static void
 404 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 405 {
 406   ssa_op_iter iter;
 407   tree var;
 408
 409   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 410     check_loop_closed_ssa_use (bb, var);
 411 }
 412
 413 /* Checks that invariants of the loop closed ssa form are preserved.  */
 414
 415 void
 416 verify_loop_closed_ssa (void)
 417 {
 418   basic_block bb;
 419   block_stmt_iterator bsi;
 420   tree phi;
 421   unsigned i;
 422
 423   if (current_loops == NULL)
 424     return;
 425
 426   verify_ssa (false);
 427
 428   FOR_EACH_BB (bb)
 429     {
 430       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 431         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 432           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 433                                      PHI_ARG_DEF (phi, i));
 434
 435       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 436         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 437     }
 438 }
 439
 440 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 441    preserve the loop closed ssa form.  */
 442
 443 void
 444 split_loop_exit_edge (edge exit)
 445 {
 446   basic_block dest = exit->dest;
 447   basic_block bb = loop_split_edge_with (exit, NULL);
 448   tree phi, new_phi, new_name, name;
 449   use_operand_p op_p;
 450
 451   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
 452     {
 453       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
 454
 455       name = USE_FROM_PTR (op_p);
 456
 457       /* If the argument of the phi node is a constant, we do not need
 458          to keep it inside loop.  */
 459       if (TREE_CODE (name) != SSA_NAME)
 460         continue;
 461
 462       /* Otherwise create an auxiliary phi node that will copy the value
 463          of the ssa name out of the loop.  */
 464       new_name = duplicate_ssa_name (name, NULL);
 465       new_phi = create_phi_node (new_name, bb);
 466       SSA_NAME_DEF_STMT (new_name) = new_phi;
 467       add_phi_arg (new_phi, name, exit);
 468       SET_USE (op_p, new_name);
 469     }
 470 }
 471
 472 /* Insert statement STMT to the edge E and update the loop structures.
 473    Returns the newly created block (if any).  */
 474
 475 basic_block
 476 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
 477 {
 478   basic_block src, dest, new_bb;
 479   struct loop *loop_c;
 480
 481   src = e->src;
 482   dest = e->dest;
 483
 484   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 485
 486   new_bb = bsi_insert_on_edge_immediate (e, stmt);
 487
 488   if (!new_bb)
 489     return NULL;
 490
 491   add_bb_to_loop (new_bb, loop_c);
 492   if (dest->loop_father->latch == src)
 493     dest->loop_father->latch = new_bb;
 494
 495   return new_bb;
 496 }
 497
 498 /* Returns the basic block in that statements should be emitted for induction
 499    variables incremented at the end of the LOOP.  */
 500
 501 basic_block
 502 ip_end_pos (struct loop *loop)
 503 {
 504   return loop->latch;
 505 }
 506
 507 /* Returns the basic block in that statements should be emitted for induction
 508    variables incremented just before exit condition of a LOOP.  */
 509
 510 basic_block
 511 ip_normal_pos (struct loop *loop)
 512 {
 513   tree last;
 514   basic_block bb;
 515   edge exit;
 516
 517   if (!single_pred_p (loop->latch))
 518     return NULL;
 519
 520   bb = single_pred (loop->latch);
 521   last = last_stmt (bb);
 522   if (TREE_CODE (last) != COND_EXPR)
 523     return NULL;
 524
 525   exit = EDGE_SUCC (bb, 0);
 526   if (exit->dest == loop->latch)
 527     exit = EDGE_SUCC (bb, 1);
 528
 529   if (flow_bb_inside_loop_p (loop, exit->dest))
 530     return NULL;
 531
 532   return bb;
 533 }
 534
 535 /* Stores the standard position for induction variable increment in LOOP
 536    (just before the exit condition if it is available and latch block is empty,
 537    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 538    the increment should be inserted after *BSI.  */
 539
 540 void
 541 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 542                                 bool *insert_after)
 543 {
 544   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 545   tree last = last_stmt (latch);
 546
 547   if (!bb
 548       || (last && TREE_CODE (last) != LABEL_EXPR))
 549     {
 550       *bsi = bsi_last (latch);
 551       *insert_after = true;
 552     }
 553   else
 554     {
 555       *bsi = bsi_last (bb);
 556       *insert_after = false;
 557     }
 558 }
 559
 560 /* Copies phi node arguments for duplicated blocks.  The index of the first
 561    duplicated block is FIRST_NEW_BLOCK.  */
 562
 563 static void
 564 copy_phi_node_args (unsigned first_new_block)
 565 {
 566   unsigned i;
 567
 568   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 569     BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
 570
 571   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 572     add_phi_args_after_copy_bb (BASIC_BLOCK (i));
 573
 574   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
 575     BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
 576 }
 577
 578
 579 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
 580    updates the PHI nodes at start of the copied region.  In order to
 581    achieve this, only loops whose exits all lead to the same location
 582    are handled.
 583
 584    Notice that we do not completely update the SSA web after
 585    duplication.  The caller is responsible for calling update_ssa
 586    after the loop has been duplicated.  */
 587
 588 bool
 589 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 590                                     struct loops *loops,
 591                                     unsigned int ndupl, sbitmap wont_exit,
 592                                     edge orig, edge *to_remove,
 593                                     unsigned int *n_to_remove, int flags)
 594 {
 595   unsigned first_new_block;
 596
 597   if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
 598     return false;
 599   if (!(loops->state & LOOPS_HAVE_PREHEADERS))
 600     return false;
 601
 602 #ifdef ENABLE_CHECKING
 603   verify_loop_closed_ssa ();
 604 #endif
 605
 606   first_new_block = last_basic_block;
 607   if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
 608                                       orig, to_remove, n_to_remove, flags))
 609     return false;
 610
 611   /* Readd the removed phi args for e.  */
 612   flush_pending_stmts (e);
 613
 614   /* Copy the phi node arguments.  */
 615   copy_phi_node_args (first_new_block);
 616
 617   scev_reset ();
 618
 619   return true;
 620 }