gcc/tree-ssa-loop-manip.c

   1 /* High-level loop manipulation functions.
   2    Copyright (C) 2004 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 "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).  The ssa versions
  45    of the variable before and after increment will be stored in VAR_BEFORE and
  46    VAR_AFTER (unless they are NULL).  */
  47
  48 void
  49 create_iv (tree base, tree step, tree var, struct loop *loop,
  50            block_stmt_iterator *incr_pos, bool after,
  51            tree *var_before, tree *var_after)
  52 {
  53   tree stmt, initial, step1, stmts;
  54   tree vb, va;
  55   enum tree_code incr_op = PLUS_EXPR;
  56
  57   if (!var)
  58     {
  59       var = create_tmp_var (TREE_TYPE (base), "ivtmp");
  60       add_referenced_tmp_var (var);
  61     }
  62
  63   vb = make_ssa_name (var, NULL_TREE);
  64   if (var_before)
  65     *var_before = vb;
  66   va = make_ssa_name (var, NULL_TREE);
  67   if (var_after)
  68     *var_after = va;
  69
  70   /* For easier readability of the created code, produce MINUS_EXPRs
  71      when suitable.  */
  72   if (TREE_CODE (step) == INTEGER_CST)
  73     {
  74       if (TYPE_UNSIGNED (TREE_TYPE (step)))
  75         {
  76           step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
  77           if (tree_int_cst_lt (step1, step))
  78             {
  79               incr_op = MINUS_EXPR;
  80               step = step1;
  81             }
  82         }
  83       else
  84         {
  85           if (!tree_expr_nonnegative_p (step)
  86               && may_negate_without_overflow_p (step))
  87             {
  88               incr_op = MINUS_EXPR;
  89               step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
  90             }
  91         }
  92     }
  93
  94   stmt = build2 (MODIFY_EXPR, void_type_node, va,
  95                  build2 (incr_op, TREE_TYPE (base),
  96                          vb, step));
  97   SSA_NAME_DEF_STMT (va) = stmt;
  98   if (after)
  99     bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
 100   else
 101     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
 102
 103   initial = force_gimple_operand (base, &stmts, true, var);
 104   if (stmts)
 105     {
 106       edge pe = loop_preheader_edge (loop);
 107
 108       bsi_insert_on_edge_immediate_loop (pe, stmts);
 109     }
 110
 111   stmt = create_phi_node (vb, loop->header);
 112   SSA_NAME_DEF_STMT (vb) = stmt;
 113   add_phi_arg (&stmt, initial, loop_preheader_edge (loop));
 114   add_phi_arg (&stmt, va, loop_latch_edge (loop));
 115 }
 116
 117 /* Add exit phis for the USE on EXIT.  */
 118
 119 static void
 120 add_exit_phis_edge (basic_block exit, tree use)
 121 {
 122   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
 123   basic_block def_bb = bb_for_stmt (def_stmt);
 124   struct loop *def_loop;
 125   edge e;
 126
 127   /* Check that some of the edges entering the EXIT block exits a loop in
 128      that USE is defined.  */
 129   for (e = exit->pred; e; e = e->pred_next)
 130     {
 131       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
 132       if (!flow_bb_inside_loop_p (def_loop, e->dest))
 133         break;
 134     }
 135
 136   if (!e)
 137     return;
 138
 139   phi = create_phi_node (use, exit);
 140
 141   for (e = exit->pred; e; e = e->pred_next)
 142     add_phi_arg (&phi, use, e);
 143
 144   SSA_NAME_DEF_STMT (use) = def_stmt;
 145 }
 146
 147 /* Add exit phis for VAR that is used in LIVEIN.
 148    Exits of the loops are stored in EXITS.  */
 149
 150 static void
 151 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
 152 {
 153   bitmap def;
 154   int index;
 155   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 156
 157   bitmap_clear_bit (livein, def_bb->index);
 158
 159   def = BITMAP_XMALLOC ();
 160   bitmap_set_bit (def, def_bb->index);
 161   compute_global_livein (livein, def);
 162   BITMAP_XFREE (def);
 163
 164   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
 165                             add_exit_phis_edge (BASIC_BLOCK (index), var));
 166 }
 167
 168 /* Add exit phis for the names marked in NAMES_TO_RENAME.
 169    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
 170    names are used are stored in USE_BLOCKS.  */
 171
 172 static void
 173 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
 174 {
 175   unsigned i;
 176
 177   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
 178     {
 179       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 180     });
 181 }
 182
 183 /* Returns a bitmap of all loop exit edge targets.  */
 184
 185 static bitmap
 186 get_loops_exits (void)
 187 {
 188   bitmap exits = BITMAP_XMALLOC ();
 189   basic_block bb;
 190   edge e;
 191
 192   FOR_EACH_BB (bb)
 193     {
 194       for (e = bb->pred; e; e = e->pred_next)
 195         if (e->src != ENTRY_BLOCK_PTR
 196             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 197           {
 198             bitmap_set_bit (exits, bb->index);
 199             break;
 200           }
 201     }
 202
 203   return exits;
 204 }
 205
 206 /* For USE in BB, if it is used outside of the loop it is defined in,
 207    mark it for rewrite.  Record basic block BB where it is used
 208    to USE_BLOCKS.  */
 209
 210 static void
 211 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
 212 {
 213   unsigned ver;
 214   basic_block def_bb;
 215   struct loop *def_loop;
 216
 217   if (TREE_CODE (use) != SSA_NAME)
 218     return;
 219
 220   ver = SSA_NAME_VERSION (use);
 221   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 222   if (!def_bb)
 223     return;
 224   def_loop = def_bb->loop_father;
 225
 226   /* If the definition is not inside loop, it is not interesting.  */
 227   if (!def_loop->outer)
 228     return;
 229
 230   if (!use_blocks[ver])
 231     use_blocks[ver] = BITMAP_XMALLOC ();
 232   bitmap_set_bit (use_blocks[ver], bb->index);
 233
 234   if (!flow_bb_inside_loop_p (def_loop, bb))
 235     mark_for_rewrite (use);
 236 }
 237
 238 /* For uses in STMT, mark names that are used outside of the loop they are
 239    defined to rewrite.  Record the set of blocks in that the ssa
 240    names are defined to USE_BLOCKS.  */
 241
 242 static void
 243 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
 244 {
 245   ssa_op_iter iter;
 246   tree var;
 247   basic_block bb = bb_for_stmt (stmt);
 248
 249   get_stmt_operands (stmt);
 250
 251   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 252     find_uses_to_rename_use (bb, var, use_blocks);
 253 }
 254
 255 /* Marks names that are used outside of the loop they are defined in
 256    for rewrite.  Records the set of blocks in that the ssa
 257    names are defined to USE_BLOCKS.  */
 258
 259 static void
 260 find_uses_to_rename (bitmap *use_blocks)
 261 {
 262   basic_block bb;
 263   block_stmt_iterator bsi;
 264   tree phi;
 265   unsigned i;
 266
 267   FOR_EACH_BB (bb)
 268     {
 269       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 270         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 271           find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
 272                                    PHI_ARG_DEF (phi, i), use_blocks);
 273
 274       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 275         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 276     }
 277 }
 278
 279 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 280    phi nodes to ensure that no variable is used outside the loop it is
 281    defined in.
 282
 283    This strengthening of the basic ssa form has several advantages:
 284
 285    1) Updating it during unrolling/peeling/versioning is trivial, since
 286       we do not need to care about the uses outside of the loop.
 287    2) The behavior of all uses of an induction variable is the same.
 288       Without this, you need to distinguish the case when the variable
 289       is used outside of the loop it is defined in, for example
 290
 291       for (i = 0; i < 100; i++)
 292         {
 293           for (j = 0; j < 100; j++)
 294             {
 295               k = i + j;
 296               use1 (k);
 297             }
 298           use2 (k);
 299         }
 300
 301       Looking from the outer loop with the normal SSA form, the first use of k
 302       is not well-behaved, while the second one is an induction variable with
 303       base 99 and step 1.  */
 304
 305 void
 306 rewrite_into_loop_closed_ssa (void)
 307 {
 308   bitmap loop_exits = get_loops_exits ();
 309   bitmap *use_blocks;
 310   unsigned i;
 311   bitmap names_to_rename;
 312
 313   gcc_assert (!any_marked_for_rewrite_p ());
 314
 315   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 316
 317   /* Find the uses outside loops.  */
 318   find_uses_to_rename (use_blocks);
 319
 320   /* Add the phi nodes on exits of the loops for the names we need to
 321      rewrite.  */
 322   names_to_rename = marked_ssa_names ();
 323   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 324
 325   for (i = 0; i < num_ssa_names; i++)
 326     BITMAP_XFREE (use_blocks[i]);
 327   free (use_blocks);
 328   BITMAP_XFREE (loop_exits);
 329   BITMAP_XFREE (names_to_rename);
 330
 331   /* Do the rewriting.  */
 332   rewrite_ssa_into_ssa ();
 333 }
 334
 335 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 336
 337 static void
 338 check_loop_closed_ssa_use (basic_block bb, tree use)
 339 {
 340   tree def;
 341   basic_block def_bb;
 342
 343   if (TREE_CODE (use) != SSA_NAME)
 344     return;
 345
 346   def = SSA_NAME_DEF_STMT (use);
 347   def_bb = bb_for_stmt (def);
 348   gcc_assert (!def_bb
 349               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 350 }
 351
 352 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 353
 354 static void
 355 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 356 {
 357   ssa_op_iter iter;
 358   tree var;
 359
 360   get_stmt_operands (stmt);
 361
 362   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 363     check_loop_closed_ssa_use (bb, var);
 364 }
 365
 366 /* Checks that invariants of the loop closed ssa form are preserved.  */
 367
 368 void
 369 verify_loop_closed_ssa (void)
 370 {
 371   basic_block bb;
 372   block_stmt_iterator bsi;
 373   tree phi;
 374   unsigned i;
 375
 376   verify_ssa ();
 377
 378   FOR_EACH_BB (bb)
 379     {
 380       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 381         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 382           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 383                                      PHI_ARG_DEF (phi, i));
 384
 385       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 386         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 387     }
 388 }
 389
 390 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 391    preserve the loop closed ssa form.  */
 392
 393 void
 394 split_loop_exit_edge (edge exit)
 395 {
 396   basic_block dest = exit->dest;
 397   basic_block bb = loop_split_edge_with (exit, NULL);
 398   tree phi, new_phi, new_name, name;
 399   use_operand_p op_p;
 400
 401   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
 402     {
 403       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ);
 404
 405       name = USE_FROM_PTR (op_p);
 406
 407       /* If the argument of the phi node is a constant, we do not need
 408          to keep it inside loop.  */
 409       if (TREE_CODE (name) != SSA_NAME)
 410         continue;
 411
 412       /* Otherwise create an auxiliary phi node that will copy the value
 413          of the ssa name out of the loop.  */
 414       new_name = duplicate_ssa_name (name, NULL);
 415       new_phi = create_phi_node (new_name, bb);
 416       SSA_NAME_DEF_STMT (new_name) = new_phi;
 417       add_phi_arg (&new_phi, name, exit);
 418       SET_USE (op_p, new_name);
 419     }
 420 }
 421
 422 /* Insert statement STMT to the edge E and update the loop structures.
 423    Returns the newly created block (if any).  */
 424
 425 basic_block
 426 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
 427 {
 428   basic_block src, dest, new_bb;
 429   struct loop *loop_c;
 430
 431   src = e->src;
 432   dest = e->dest;
 433
 434   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 435
 436   new_bb = bsi_insert_on_edge_immediate (e, stmt);
 437
 438   if (!new_bb)
 439     return NULL;
 440
 441   add_bb_to_loop (new_bb, loop_c);
 442   if (dest->loop_father->latch == src)
 443     dest->loop_father->latch = new_bb;
 444
 445   return new_bb;
 446 }
 447
 448 /* Returns the basic block in that statements should be emitted for induction
 449    variables incremented at the end of the LOOP.  */
 450
 451 basic_block
 452 ip_end_pos (struct loop *loop)
 453 {
 454   return loop->latch;
 455 }
 456
 457 /* Returns the basic block in that statements should be emitted for induction
 458    variables incremented just before exit condition of a LOOP.  */
 459
 460 basic_block
 461 ip_normal_pos (struct loop *loop)
 462 {
 463   tree last;
 464   basic_block bb;
 465   edge exit;
 466
 467   if (loop->latch->pred->pred_next)
 468     return NULL;
 469
 470   bb = loop->latch->pred->src;
 471   last = last_stmt (bb);
 472   if (TREE_CODE (last) != COND_EXPR)
 473     return NULL;
 474
 475   exit = bb->succ;
 476   if (exit->dest == loop->latch)
 477     exit = exit->succ_next;
 478
 479   if (flow_bb_inside_loop_p (loop, exit->dest))
 480     return NULL;
 481
 482   return bb;
 483 }
 484
 485 /* Stores the standard position for induction variable increment in LOOP
 486    (just before the exit condition if it is available and latch block is empty,
 487    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 488    the increment should be inserted after *BSI.  */
 489
 490 void
 491 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 492                                 bool *insert_after)
 493 {
 494   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 495   tree last = last_stmt (latch);
 496
 497   if (!bb
 498       || (last && TREE_CODE (last) != LABEL_EXPR))
 499     {
 500       *bsi = bsi_last (latch);
 501       *insert_after = true;
 502     }
 503   else
 504     {
 505       *bsi = bsi_last (bb);
 506       *insert_after = false;
 507     }
 508 }