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   edge_iterator ei;
 127
 128   /* Check that some of the edges entering the EXIT block exits a loop in
 129      that USE is defined.  */
 130   FOR_EACH_EDGE (e, ei, exit->preds)
 131     {
 132       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
 133       if (!flow_bb_inside_loop_p (def_loop, e->dest))
 134         break;
 135     }
 136
 137   if (!e)
 138     return;
 139
 140   phi = create_phi_node (use, exit);
 141
 142   FOR_EACH_EDGE (e, ei, exit->preds)
 143     add_phi_arg (&phi, use, e);
 144
 145   SSA_NAME_DEF_STMT (use) = def_stmt;
 146 }
 147
 148 /* Add exit phis for VAR that is used in LIVEIN.
 149    Exits of the loops are stored in EXITS.  */
 150
 151 static void
 152 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
 153 {
 154   bitmap def;
 155   int index;
 156   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
 157
 158   bitmap_clear_bit (livein, def_bb->index);
 159
 160   def = BITMAP_XMALLOC ();
 161   bitmap_set_bit (def, def_bb->index);
 162   compute_global_livein (livein, def);
 163   BITMAP_XFREE (def);
 164
 165   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
 166                             add_exit_phis_edge (BASIC_BLOCK (index), var));
 167 }
 168
 169 /* Add exit phis for the names marked in NAMES_TO_RENAME.
 170    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
 171    names are used are stored in USE_BLOCKS.  */
 172
 173 static void
 174 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
 175 {
 176   unsigned i;
 177
 178   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
 179     {
 180       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 181     });
 182 }
 183
 184 /* Returns a bitmap of all loop exit edge targets.  */
 185
 186 static bitmap
 187 get_loops_exits (void)
 188 {
 189   bitmap exits = BITMAP_XMALLOC ();
 190   basic_block bb;
 191   edge e;
 192   edge_iterator ei;
 193
 194   FOR_EACH_BB (bb)
 195     {
 196       FOR_EACH_EDGE (e, ei, bb->preds)
 197         if (e->src != ENTRY_BLOCK_PTR
 198             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 199           {
 200             bitmap_set_bit (exits, bb->index);
 201             break;
 202           }
 203     }
 204
 205   return exits;
 206 }
 207
 208 /* For USE in BB, if it is used outside of the loop it is defined in,
 209    mark it for rewrite.  Record basic block BB where it is used
 210    to USE_BLOCKS.  */
 211
 212 static void
 213 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
 214 {
 215   unsigned ver;
 216   basic_block def_bb;
 217   struct loop *def_loop;
 218
 219   if (TREE_CODE (use) != SSA_NAME)
 220     return;
 221
 222   ver = SSA_NAME_VERSION (use);
 223   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 224   if (!def_bb)
 225     return;
 226   def_loop = def_bb->loop_father;
 227
 228   /* If the definition is not inside loop, it is not interesting.  */
 229   if (!def_loop->outer)
 230     return;
 231
 232   if (!use_blocks[ver])
 233     use_blocks[ver] = BITMAP_XMALLOC ();
 234   bitmap_set_bit (use_blocks[ver], bb->index);
 235
 236   if (!flow_bb_inside_loop_p (def_loop, bb))
 237     mark_for_rewrite (use);
 238 }
 239
 240 /* For uses in STMT, mark names that are used outside of the loop they are
 241    defined to rewrite.  Record the set of blocks in that the ssa
 242    names are defined to USE_BLOCKS.  */
 243
 244 static void
 245 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
 246 {
 247   ssa_op_iter iter;
 248   tree var;
 249   basic_block bb = bb_for_stmt (stmt);
 250
 251   get_stmt_operands (stmt);
 252
 253   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
 254     find_uses_to_rename_use (bb, var, use_blocks);
 255 }
 256
 257 /* Marks names that are used outside of the loop they are defined in
 258    for rewrite.  Records the set of blocks in that the ssa
 259    names are defined to USE_BLOCKS.  */
 260
 261 static void
 262 find_uses_to_rename (bitmap *use_blocks)
 263 {
 264   basic_block bb;
 265   block_stmt_iterator bsi;
 266   tree phi;
 267   unsigned i;
 268
 269   FOR_EACH_BB (bb)
 270     {
 271       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 272         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 273           find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
 274                                    PHI_ARG_DEF (phi, i), use_blocks);
 275
 276       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 277         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 278     }
 279 }
 280
 281 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 282    phi nodes to ensure that no variable is used outside the loop it is
 283    defined in.
 284
 285    This strengthening of the basic ssa form has several advantages:
 286
 287    1) Updating it during unrolling/peeling/versioning is trivial, since
 288       we do not need to care about the uses outside of the loop.
 289    2) The behavior of all uses of an induction variable is the same.
 290       Without this, you need to distinguish the case when the variable
 291       is used outside of the loop it is defined in, for example
 292
 293       for (i = 0; i < 100; i++)
 294         {
 295           for (j = 0; j < 100; j++)
 296             {
 297               k = i + j;
 298               use1 (k);
 299             }
 300           use2 (k);
 301         }
 302
 303       Looking from the outer loop with the normal SSA form, the first use of k
 304       is not well-behaved, while the second one is an induction variable with
 305       base 99 and step 1.  */
 306
 307 void
 308 rewrite_into_loop_closed_ssa (void)
 309 {
 310   bitmap loop_exits = get_loops_exits ();
 311   bitmap *use_blocks;
 312   unsigned i;
 313   bitmap names_to_rename;
 314
 315   gcc_assert (!any_marked_for_rewrite_p ());
 316
 317   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 318
 319   /* Find the uses outside loops.  */
 320   find_uses_to_rename (use_blocks);
 321
 322   /* Add the phi nodes on exits of the loops for the names we need to
 323      rewrite.  */
 324   names_to_rename = marked_ssa_names ();
 325   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 326
 327   for (i = 0; i < num_ssa_names; i++)
 328     BITMAP_XFREE (use_blocks[i]);
 329   free (use_blocks);
 330   BITMAP_XFREE (loop_exits);
 331   BITMAP_XFREE (names_to_rename);
 332
 333   /* Do the rewriting.  */
 334   rewrite_ssa_into_ssa ();
 335 }
 336
 337 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 338
 339 static void
 340 check_loop_closed_ssa_use (basic_block bb, tree use)
 341 {
 342   tree def;
 343   basic_block def_bb;
 344
 345   if (TREE_CODE (use) != SSA_NAME)
 346     return;
 347
 348   def = SSA_NAME_DEF_STMT (use);
 349   def_bb = bb_for_stmt (def);
 350   gcc_assert (!def_bb
 351               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
 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, EDGE_SUCC (bb, 0));
 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 (EDGE_COUNT (loop->latch->preds) > 1)
 461     return NULL;
 462
 463   bb = EDGE_PRED (loop->latch, 0)->src;
 464   last = last_stmt (bb);
 465   if (TREE_CODE (last) != COND_EXPR)
 466     return NULL;
 467
 468   exit = EDGE_SUCC (bb, 0);
 469   if (exit->dest == loop->latch)
 470     exit = EDGE_SUCC (bb, 1);
 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 }