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   if (any_marked_for_rewrite_p ())
 314     abort ();
 315
 316   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 317
 318   /* Find the uses outside loops.  */
 319   find_uses_to_rename (use_blocks);
 320
 321   /* Add the phi nodes on exits of the loops for the names we need to
 322      rewrite.  */
 323   names_to_rename = marked_ssa_names ();
 324   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 325
 326   for (i = 0; i < num_ssa_names; i++)
 327     BITMAP_XFREE (use_blocks[i]);
 328   free (use_blocks);
 329   BITMAP_XFREE (loop_exits);
 330   BITMAP_XFREE (names_to_rename);
 331
 332   /* Do the rewriting.  */
 333   rewrite_ssa_into_ssa ();
 334 }
 335
 336 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 337
 338 static void
 339 check_loop_closed_ssa_use (basic_block bb, tree use)
 340 {
 341   tree def;
 342   basic_block def_bb;
 343
 344   if (TREE_CODE (use) != SSA_NAME)
 345     return;
 346
 347   def = SSA_NAME_DEF_STMT (use);
 348   def_bb = bb_for_stmt (def);
 349   if (def_bb
 350       && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
 351     abort ();
 352 }
 353
 354 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 355
 356 static void
 357 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 358 {
 359   ssa_op_iter iter;
 360   tree var;
 361
 362   get_stmt_operands (stmt);
 363
 364   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 365     check_loop_closed_ssa_use (bb, var);
 366 }
 367
 368 /* Checks that invariants of the loop closed ssa form are preserved.  */
 369
 370 void
 371 verify_loop_closed_ssa (void)
 372 {
 373   basic_block bb;
 374   block_stmt_iterator bsi;
 375   tree phi;
 376   unsigned i;
 377
 378   verify_ssa ();
 379
 380   FOR_EACH_BB (bb)
 381     {
 382       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 383         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 384           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 385                                      PHI_ARG_DEF (phi, i));
 386
 387       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 388         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 389     }
 390 }
 391
 392 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
 393    preserve the loop closed ssa form.  */
 394
 395 void
 396 split_loop_exit_edge (edge exit)
 397 {
 398   basic_block dest = exit->dest;
 399   basic_block bb = loop_split_edge_with (exit, NULL);
 400   tree phi, new_phi, new_name;
 401   use_operand_p op_p;
 402
 403   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
 404     {
 405       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, bb->succ);
 406
 407       new_name = duplicate_ssa_name (USE_FROM_PTR (op_p), NULL);
 408       new_phi = create_phi_node (new_name, bb);
 409       SSA_NAME_DEF_STMT (new_name) = new_phi;
 410       add_phi_arg (&new_phi, USE_FROM_PTR (op_p), exit);
 411       SET_USE (op_p, new_name);
 412     }
 413 }
 414
 415 /* Insert statement STMT to the edge E and update the loop structures.
 416    Returns the newly created block (if any).  */
 417
 418 basic_block
 419 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
 420 {
 421   basic_block src, dest, new_bb;
 422   struct loop *loop_c;
 423
 424   src = e->src;
 425   dest = e->dest;
 426
 427   loop_c = find_common_loop (src->loop_father, dest->loop_father);
 428
 429   new_bb = bsi_insert_on_edge_immediate (e, stmt);
 430
 431   if (!new_bb)
 432     return NULL;
 433
 434   add_bb_to_loop (new_bb, loop_c);
 435   if (dest->loop_father->latch == src)
 436     dest->loop_father->latch = new_bb;
 437
 438   return new_bb;
 439 }
 440
 441 /* Returns the basic block in that statements should be emitted for induction
 442    variables incremented at the end of the LOOP.  */
 443
 444 basic_block
 445 ip_end_pos (struct loop *loop)
 446 {
 447   return loop->latch;
 448 }
 449
 450 /* Returns the basic block in that statements should be emitted for induction
 451    variables incremented just before exit condition of a LOOP.  */
 452
 453 basic_block
 454 ip_normal_pos (struct loop *loop)
 455 {
 456   tree last;
 457   basic_block bb;
 458   edge exit;
 459
 460   if (loop->latch->pred->pred_next)
 461     return NULL;
 462
 463   bb = loop->latch->pred->src;
 464   last = last_stmt (bb);
 465   if (TREE_CODE (last) != COND_EXPR)
 466     return NULL;
 467
 468   exit = bb->succ;
 469   if (exit->dest == loop->latch)
 470     exit = exit->succ_next;
 471
 472   if (flow_bb_inside_loop_p (loop, exit->dest))
 473     return NULL;
 474
 475   return bb;
 476 }
 477
 478 /* Stores the standard position for induction variable increment in LOOP
 479    (just before the exit condition if it is available and latch block is empty,
 480    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
 481    the increment should be inserted after *BSI.  */
 482
 483 void
 484 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
 485                                 bool *insert_after)
 486 {
 487   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
 488   tree last = last_stmt (latch);
 489
 490   if (!bb
 491       || (last && TREE_CODE (last) != LABEL_EXPR))
 492     {
 493       *bsi = bsi_last (latch);
 494       *insert_after = true;
 495     }
 496   else
 497     {
 498       *bsi = bsi_last (bb);
 499       *insert_after = false;
 500     }
 501 }