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 /* Add exit phis for the USE on EXIT.  */
  41
  42 static void
  43 add_exit_phis_edge (basic_block exit, tree use)
  44 {
  45   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
  46   basic_block def_bb = bb_for_stmt (def_stmt);
  47   struct loop *def_loop;
  48   edge e;
  49
  50   /* Check that some of the edges entering the EXIT block exits a loop in
  51      that USE is defined.  */
  52   for (e = exit->pred; e; e = e->pred_next)
  53     {
  54       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
  55       if (!flow_bb_inside_loop_p (def_loop, e->dest))
  56         break;
  57     }
  58
  59   if (!e)
  60     return;
  61
  62   phi = create_phi_node (use, exit);
  63
  64   for (e = exit->pred; e; e = e->pred_next)
  65     add_phi_arg (&phi, use, e);
  66
  67   SSA_NAME_DEF_STMT (use) = def_stmt;
  68 }
  69
  70 /* Add exit phis for VAR that is used in LIVEIN.
  71    Exits of the loops are stored in EXITS.  */
  72
  73 static void
  74 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
  75 {
  76   bitmap def;
  77   int index;
  78   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
  79
  80   bitmap_clear_bit (livein, def_bb->index);
  81
  82   def = BITMAP_XMALLOC ();
  83   bitmap_set_bit (def, def_bb->index);
  84   compute_global_livein (livein, def);
  85   BITMAP_XFREE (def);
  86
  87   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
  88                             add_exit_phis_edge (BASIC_BLOCK (index), var));
  89 }
  90
  91 /* Add exit phis for the names marked in NAMES_TO_RENAME.
  92    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
  93    names are used are stored in USE_BLOCKS.  */
  94
  95 static void
  96 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
  97 {
  98   unsigned i;
  99
 100   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
 101     {
 102       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
 103     });
 104 }
 105
 106 /* Returns a bitmap of all loop exit edge targets.  */
 107
 108 static bitmap
 109 get_loops_exits (void)
 110 {
 111   bitmap exits = BITMAP_XMALLOC ();
 112   basic_block bb;
 113   edge e;
 114
 115   FOR_EACH_BB (bb)
 116     {
 117       for (e = bb->pred; e; e = e->pred_next)
 118         if (e->src != ENTRY_BLOCK_PTR
 119             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
 120           {
 121             bitmap_set_bit (exits, bb->index);
 122             break;
 123           }
 124     }
 125
 126   return exits;
 127 }
 128
 129 /* For USE in BB, if it is used outside of the loop it is defined in,
 130    mark it for rewrite.  Record basic block BB where it is used
 131    to USE_BLOCKS.  */
 132
 133 static void
 134 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
 135 {
 136   unsigned ver;
 137   basic_block def_bb;
 138   struct loop *def_loop;
 139
 140   if (TREE_CODE (use) != SSA_NAME)
 141     return;
 142
 143   ver = SSA_NAME_VERSION (use);
 144   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
 145   if (!def_bb)
 146     return;
 147   def_loop = def_bb->loop_father;
 148
 149   /* If the definition is not inside loop, it is not interesting.  */
 150   if (!def_loop->outer)
 151     return;
 152
 153   if (!use_blocks[ver])
 154     use_blocks[ver] = BITMAP_XMALLOC ();
 155   bitmap_set_bit (use_blocks[ver], bb->index);
 156
 157   if (!flow_bb_inside_loop_p (def_loop, bb))
 158     mark_for_rewrite (use);
 159 }
 160
 161 /* For uses in STMT, mark names that are used outside of the loop they are
 162    defined to rewrite.  Record the set of blocks in that the ssa
 163    names are defined to USE_BLOCKS.  */
 164
 165 static void
 166 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
 167 {
 168   use_optype uses;
 169   vuse_optype vuses;
 170   v_may_def_optype v_may_defs;
 171   stmt_ann_t ann;
 172   unsigned i;
 173   basic_block bb = bb_for_stmt (stmt);
 174
 175   get_stmt_operands (stmt);
 176   ann = stmt_ann (stmt);
 177
 178   uses = USE_OPS (ann);
 179   for (i = 0; i < NUM_USES (uses); i++)
 180     find_uses_to_rename_use (bb, USE_OP (uses, i), use_blocks);
 181
 182   vuses = VUSE_OPS (ann);
 183   for (i = 0; i < NUM_VUSES (vuses); i++)
 184     find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks);
 185
 186   v_may_defs = V_MAY_DEF_OPS (ann);
 187   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 188     find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks);
 189 }
 190
 191 /* Marks names that are used outside of the loop they are defined in
 192    for rewrite.  Records the set of blocks in that the ssa
 193    names are defined to USE_BLOCKS.  */
 194
 195 static void
 196 find_uses_to_rename (bitmap *use_blocks)
 197 {
 198   basic_block bb;
 199   block_stmt_iterator bsi;
 200   tree phi;
 201   unsigned i;
 202
 203   FOR_EACH_BB (bb)
 204     {
 205       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 206         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 207           find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
 208                                    PHI_ARG_DEF (phi, i), use_blocks);
 209
 210       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 211         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
 212     }
 213 }
 214
 215 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
 216    phi nodes to ensure that no variable is used outside the loop it is
 217    defined in.
 218
 219    This strengthening of the basic ssa form has several advantages:
 220
 221    1) Updating it during unrolling/peeling/versioning is trivial, since
 222       we do not need to care about the uses outside of the loop.
 223    2) The behavior of all uses of an induction variable is the same.
 224       Without this, you need to distinguish the case when the variable
 225       is used outside of the loop it is defined in, for example
 226
 227       for (i = 0; i < 100; i++)
 228         {
 229           for (j = 0; j < 100; j++)
 230             {
 231               k = i + j;
 232               use1 (k);
 233             }
 234           use2 (k);
 235         }
 236
 237       Looking from the outer loop with the normal SSA form, the first use of k
 238       is not well-behaved, while the second one is an induction variable with
 239       base 99 and step 1.  */
 240
 241 void
 242 rewrite_into_loop_closed_ssa (void)
 243 {
 244   bitmap loop_exits = get_loops_exits ();
 245   bitmap *use_blocks;
 246   unsigned i;
 247   bitmap names_to_rename;
 248
 249   if (any_marked_for_rewrite_p ())
 250     abort ();
 251
 252   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
 253
 254   /* Find the uses outside loops.  */
 255   find_uses_to_rename (use_blocks);
 256
 257   /* Add the phi nodes on exits of the loops for the names we need to
 258      rewrite.  */
 259   names_to_rename = marked_ssa_names ();
 260   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 261
 262   for (i = 0; i < num_ssa_names; i++)
 263     BITMAP_XFREE (use_blocks[i]);
 264   free (use_blocks);
 265   BITMAP_XFREE (loop_exits);
 266   BITMAP_XFREE (names_to_rename);
 267
 268   /* Do the rewriting.  */
 269   rewrite_ssa_into_ssa ();
 270 }
 271
 272 /* Check invariants of the loop closed ssa form for the USE in BB.  */
 273
 274 static void
 275 check_loop_closed_ssa_use (basic_block bb, tree use)
 276 {
 277   tree def;
 278   basic_block def_bb;
 279
 280   if (TREE_CODE (use) != SSA_NAME)
 281     return;
 282
 283   def = SSA_NAME_DEF_STMT (use);
 284   def_bb = bb_for_stmt (def);
 285   if (def_bb
 286       && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
 287     abort ();
 288 }
 289
 290 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
 291
 292 static void
 293 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
 294 {
 295   use_optype uses;
 296   vuse_optype vuses;
 297   v_may_def_optype v_may_defs;
 298   stmt_ann_t ann;
 299   unsigned i;
 300
 301   get_stmt_operands (stmt);
 302   ann = stmt_ann (stmt);
 303
 304   uses = USE_OPS (ann);
 305   for (i = 0; i < NUM_USES (uses); i++)
 306     check_loop_closed_ssa_use (bb, USE_OP (uses, i));
 307
 308   vuses = VUSE_OPS (ann);
 309   for (i = 0; i < NUM_VUSES (vuses); i++)
 310     check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
 311
 312   v_may_defs = V_MAY_DEF_OPS (ann);
 313   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 314     check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
 315 }
 316
 317 /* Checks that invariants of the loop closed ssa form are preserved.  */
 318
 319 void
 320 verify_loop_closed_ssa (void)
 321 {
 322   basic_block bb;
 323   block_stmt_iterator bsi;
 324   tree phi;
 325   unsigned i;
 326
 327   verify_ssa ();
 328
 329   FOR_EACH_BB (bb)
 330     {
 331       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 332         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 333           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
 334                                      PHI_ARG_DEF (phi, i));
 335
 336       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 337         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
 338     }
 339 }