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   use_optype uses;
 240   vuse_optype vuses;
 241   v_may_def_optype v_may_defs;
 242   stmt_ann_t ann;
 243   unsigned i;
 244   basic_block bb = bb_for_stmt (stmt);
 245
 246   get_stmt_operands (stmt);
 247   ann = stmt_ann (stmt);
 248
 249   uses = USE_OPS (ann);
 250   for (i = 0; i < NUM_USES (uses); i++)
 251     find_uses_to_rename_use (bb, USE_OP (uses, i), use_blocks);
 252
 253   vuses = VUSE_OPS (ann);
 254   for (i = 0; i < NUM_VUSES (vuses); i++)
 255     find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks);
 256
 257   v_may_defs = V_MAY_DEF_OPS (ann);
 258   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 259     find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks);
 260 }
 261
 262 /* Marks names that are used outside of the loop they are defined in
 263    for rewrite.  Records the set of blocks in that the ssa
 264    names are defined to USE_BLOCKS.  */
 265
 266 static void
 267 find_uses_to_rename (bitmap *use_blocks)
 268 {
 269   basic_block bb;
 270   block_stmt_iterator bsi;
 271   tree phi;
 272   unsigned i;
 273
 274   FOR_EACH_BB (bb)
 275     {
 276       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 277         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 278           find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
 279                                    PHI_ARG_DEF (phi, i), use_blocks);
 280
 281       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 282         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 283     }
 284 }
 285
 286 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 287    phi nodes to ensure that no variable is used outside the loop it is
 288    defined in.
 289
 290    This strengthening of the basic ssa form has several advantages:
 291
 292    1) Updating it during unrolling/peeling/versioning is trivial, since
 293       we do not need to care about the uses outside of the loop.
 294    2) The behavior of all uses of an induction variable is the same.
 295       Without this, you need to distinguish the case when the variable
 296       is used outside of the loop it is defined in, for example
 297
 298       for (i = 0; i < 100; i++)
 299         {
 300           for (j = 0; j < 100; j++)
 301             {
 302               k = i + j;
 303               use1 (k);
 304             }
 305           use2 (k);
 306         }
 307
 308       Looking from the outer loop with the normal SSA form, the first use of k
 309       is not well-behaved, while the second one is an induction variable with
 310       base 99 and step 1.  */
 311
 312 void
 313 rewrite_into_loop_closed_ssa (void)
 314 {
 315   bitmap loop_exits = get_loops_exits ();
 316   bitmap *use_blocks;
 317   unsigned i;
 318   bitmap names_to_rename;
 319
 320   if (any_marked_for_rewrite_p ())
 321     abort ();
 322
 323   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 324
 325   /* Find the uses outside loops.  */
 326   find_uses_to_rename (use_blocks);
 327
 328   /* Add the phi nodes on exits of the loops for the names we need to
 329      rewrite.  */
 330   names_to_rename = marked_ssa_names ();
 331   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 332
 333   for (i = 0; i < num_ssa_names; i++)
 334     BITMAP_XFREE (use_blocks[i]);
 335   free (use_blocks);
 336   BITMAP_XFREE (loop_exits);
 337   BITMAP_XFREE (names_to_rename);
 338
 339   /* Do the rewriting.  */
 340   rewrite_ssa_into_ssa ();
 341 }
 342
 343 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 344
 345 static void
 346 check_loop_closed_ssa_use (basic_block bb, tree use)
 347 {
 348   tree def;
 349   basic_block def_bb;
 350
 351   if (TREE_CODE (use) != SSA_NAME)
 352     return;
 353
 354   def = SSA_NAME_DEF_STMT (use);
 355   def_bb = bb_for_stmt (def);
 356   if (def_bb
 357       && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
 358     abort ();
 359 }
 360
 361 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 362
 363 static void
 364 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 365 {
 366   use_optype uses;
 367   vuse_optype vuses;
 368   v_may_def_optype v_may_defs;
 369   stmt_ann_t ann;
 370   unsigned i;
 371
 372   get_stmt_operands (stmt);
 373   ann = stmt_ann (stmt);
 374
 375   uses = USE_OPS (ann);
 376   for (i = 0; i < NUM_USES (uses); i++)
 377     check_loop_closed_ssa_use (bb, USE_OP (uses, i));
 378
 379   vuses = VUSE_OPS (ann);
 380   for (i = 0; i < NUM_VUSES (vuses); i++)
 381     check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
 382
 383   v_may_defs = V_MAY_DEF_OPS (ann);
 384   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 385     check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
 386 }
 387
 388 /* Checks that invariants of the loop closed ssa form are preserved.  */
 389
 390 void
 391 verify_loop_closed_ssa (void)
 392 {
 393   basic_block bb;
 394   block_stmt_iterator bsi;
 395   tree phi;
 396   unsigned i;
 397
 398   verify_ssa ();
 399
 400   FOR_EACH_BB (bb)
 401     {
 402       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 403         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 404           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 405                                      PHI_ARG_DEF (phi, i));
 406
 407       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 408         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 409     }
 410 }