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