View | Details | Return to bug 54146 | Differences between
and this patch

Collapse All | Expand All

(-)tree-flow.h (-1 lines)
Lines 521-527 tree create_new_def_for (tree, gimple, def_operand Link Here
521
bool need_ssa_update_p (struct function *);
521
bool need_ssa_update_p (struct function *);
522
bool name_registered_for_update_p (tree);
522
bool name_registered_for_update_p (tree);
523
void release_ssa_name_after_update_ssa (tree);
523
void release_ssa_name_after_update_ssa (tree);
524
void compute_global_livein (bitmap, bitmap);
525
void mark_virtual_operands_for_renaming (struct function *);
524
void mark_virtual_operands_for_renaming (struct function *);
526
tree get_current_def (tree);
525
tree get_current_def (tree);
527
void set_current_def (tree, tree);
526
void set_current_def (tree, tree);
(-)tree-into-ssa.c (-57 lines)
Lines 404-466 set_current_def (tree var, tree def) Link Here
404
  get_common_info (var)->current_def = def;
404
  get_common_info (var)->current_def = def;
405
}
405
}
406
406
407
408
/* Compute global livein information given the set of blocks where
409
   an object is locally live at the start of the block (LIVEIN)
410
   and the set of blocks where the object is defined (DEF_BLOCKS).
411
412
   Note: This routine augments the existing local livein information
413
   to include global livein (i.e., it modifies the underlying bitmap
414
   for LIVEIN).  */
415
416
void
417
compute_global_livein (bitmap livein, bitmap def_blocks)
418
{
419
  unsigned i;
420
  bitmap_iterator bi;
421
  VEC (basic_block, heap) *worklist;
422
423
  /* Normally the work list size is bounded by the number of basic
424
     blocks in the largest loop.  We don't know this number, but we
425
     can be fairly sure that it will be relatively small.  */
426
  worklist = VEC_alloc (basic_block, heap, MAX (8, n_basic_blocks / 128));
427
428
  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
429
    VEC_safe_push (basic_block, heap, worklist, BASIC_BLOCK (i));
430
431
  /* Iterate until the worklist is empty.  */
432
  while (! VEC_empty (basic_block, worklist))
433
    {
434
      edge e;
435
      edge_iterator ei;
436
437
      /* Pull a block off the worklist.  */
438
      basic_block bb = VEC_pop (basic_block, worklist);
439
440
      /* Make sure we have at least enough room in the work list
441
	 for all predecessors of this block.  */
442
      VEC_reserve (basic_block, heap, worklist, EDGE_COUNT (bb->preds));
443
444
      /* For each predecessor block.  */
445
      FOR_EACH_EDGE (e, ei, bb->preds)
446
	{
447
	  basic_block pred = e->src;
448
	  int pred_index = pred->index;
449
450
	  /* None of this is necessary for the entry block.  */
451
	  if (pred != ENTRY_BLOCK_PTR
452
	      && ! bitmap_bit_p (def_blocks, pred_index)
453
	      && bitmap_set_bit (livein, pred_index))
454
	    {
455
	      VEC_quick_push (basic_block, worklist, pred);
456
	    }
457
	}
458
    }
459
460
  VEC_free (basic_block, heap, worklist);
461
}
462
463
464
/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
407
/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
465
   all statements in basic block BB.  */
408
   all statements in basic block BB.  */
466
409
(-)tree-ssa-loop-manip.c (-51 / +185 lines)
Lines 27-32 along with GCC; see the file COPYING3. If not see Link Here
27
#include "basic-block.h"
27
#include "basic-block.h"
28
#include "tree-flow.h"
28
#include "tree-flow.h"
29
#include "dumpfile.h"
29
#include "dumpfile.h"
30
#include "gimple-pretty-print.h"
30
#include "cfgloop.h"
31
#include "cfgloop.h"
31
#include "tree-pass.h"	/* ??? for TODO_update_ssa but this isn't a pass.  */
32
#include "tree-pass.h"	/* ??? for TODO_update_ssa but this isn't a pass.  */
32
#include "tree-scalar-evolution.h"
33
#include "tree-scalar-evolution.h"
Lines 129-190 create_iv (tree base, tree step, tree var, struct Link Here
129
  add_phi_arg (stmt, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
130
  add_phi_arg (stmt, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
130
}
131
}
131
132
132
/* Add exit phis for the USE on EXIT.  */
133
/* Return the outermost superloop LOOP of USE_LOOP that is a superloop of
134
   both DEF_LOOP and USE_LOOP.  */
133
135
136
static inline struct loop *
137
find_sibling_superloop (struct loop *use_loop, struct loop *def_loop)
138
{
139
  unsigned ud = loop_depth (use_loop);
140
  unsigned dd = loop_depth (def_loop);
141
  gcc_assert (ud > 0 && dd > 0);
142
  if (ud > dd)
143
    use_loop = superloop_at_depth (use_loop, dd);
144
  if (ud < dd)
145
    def_loop = superloop_at_depth (def_loop, ud);
146
  while (loop_outer (use_loop) != loop_outer (def_loop))
147
    {
148
      use_loop = loop_outer (use_loop);
149
      def_loop = loop_outer (def_loop);
150
      gcc_assert (use_loop && def_loop);
151
    }
152
  return use_loop;
153
}
154
155
/* DEF_BB is a basic block containing a DEF that needs rewriting into
156
   loop-closed SSA form.  USE_BLOCKS is the set of basic blocks containing
157
   uses of DEF that "escape" from the loop that DEF_BB is (i.e. blocks in
158
   USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
159
   ALL_EXITS is the per-loop set of all basic blocks that exit loop.
160
161
   Compute the subset of LOOP_EXITS in exit the loop containing DEF_BB, and
162
   all its loop fathers, in which DEF is live.  This set is returned in
163
   the bitmap LIVE_EXITS.
164
165
   Instead of computing the complete livein set of the def, we use the loop
166
   nesting tree as a form of poor man's structure analysis.  This greatly
167
   speeds up the analysis, which is important because this function may be
168
   called on all SSA names that need rewriting, one at a time.  */
169
134
static void
170
static void
135
add_exit_phis_edge (basic_block exit, tree use)
171
compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
172
			 bitmap *loop_exits, basic_block def_bb)
136
{
173
{
137
  gimple phi, def_stmt = SSA_NAME_DEF_STMT (use);
174
  unsigned i;
138
  basic_block def_bb = gimple_bb (def_stmt);
175
  bitmap_iterator bi;
139
  struct loop *def_loop;
176
  VEC (basic_block, heap) *worklist;
177
  struct loop *def_loop = def_bb->loop_father;
178
  unsigned def_loop_depth = loop_depth (def_loop);
179
  bitmap def_loop_exits;
180
181
  /* Normally the work list size is bounded by the number of basic
182
     blocks in the largest loop.  We don't know this number, but we
183
     can be fairly sure that it will be relatively small.  */
184
  worklist = VEC_alloc (basic_block, heap, MAX (8, n_basic_blocks / 128));
185
186
  EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
187
    {
188
      basic_block use_bb = BASIC_BLOCK (i);
189
      struct loop *use_loop = use_bb->loop_father;
190
      gcc_checking_assert (def_loop != use_loop
191
			   && ! flow_loop_nested_p (def_loop, use_loop));
192
      if (! flow_loop_nested_p (use_loop, def_loop))
193
	use_bb = find_sibling_superloop (use_loop, def_loop)->header;
194
      if (bitmap_set_bit (live_exits, use_bb->index))
195
	VEC_safe_push (basic_block, heap, worklist, use_bb);
196
    }
197
198
  /* Iterate until the worklist is empty.  */
199
  while (! VEC_empty (basic_block, worklist))
200
    {
201
      edge e;
202
      edge_iterator ei;
203
204
      /* Pull a block off the worklist.  */
205
      basic_block bb = VEC_pop (basic_block, worklist);
206
207
      /* Make sure we have at least enough room in the work list
208
	 for all predecessors of this block.  */
209
      VEC_reserve (basic_block, heap, worklist, EDGE_COUNT (bb->preds));
210
211
      /* For each predecessor block.  */
212
      FOR_EACH_EDGE (e, ei, bb->preds)
213
	{
214
	  basic_block pred = e->src;
215
	  struct loop *pred_loop = pred->loop_father;
216
	  unsigned pred_loop_depth = loop_depth (pred_loop);
217
	  bool pred_visited;
218
219
	  /* We should have met DEF_BB along the way.  */
220
	  gcc_assert (pred != ENTRY_BLOCK_PTR);
221
222
	  if (pred_loop_depth >= def_loop_depth)
223
	    {
224
	      if (pred_loop_depth > def_loop_depth)
225
		pred_loop = superloop_at_depth (pred_loop, def_loop_depth);
226
	      /* If we've reached DEF_LOOP, our train ends here.  */
227
	      if (pred_loop == def_loop)
228
		continue;
229
	    }
230
	  else if (! flow_loop_nested_p (pred_loop, def_loop))
231
	    pred = find_sibling_superloop (pred_loop, def_loop)->header;
232
233
	  /* Add PRED to the LIVEIN set.  PRED_VISITED is true if
234
	     we had already added PRED to LIVEIN before.  */
235
	  pred_visited = !bitmap_set_bit (live_exits, pred->index);
236
237
	  /* If we have visited PRED before, don't add it to the worklist.
238
	     If BB dominates PRED, then we're probably looking at a loop.
239
	     We're only interested in looking up in the dominance tree
240
	     because DEF_BB dominates all the uses.  */
241
	  if (pred_visited || dominated_by_p (CDI_DOMINATORS, pred, bb))
242
	    continue;
243
244
	  VEC_quick_push (basic_block, worklist, pred);
245
	}
246
    }
247
  VEC_free (basic_block, heap, worklist);
248
249
  def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
250
  for (struct loop *loop = def_loop;
251
       loop != current_loops->tree_root;
252
       loop = loop_outer (loop))
253
    bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
254
  bitmap_and_into (live_exits, def_loop_exits);
255
  BITMAP_FREE (def_loop_exits);
256
}
257
258
/* Add a loop-closing PHI for VAR in basic block EXIT.  */
259
260
static void
261
add_exit_phi (basic_block exit, tree var)
262
{
263
  gimple phi;
140
  edge e;
264
  edge e;
141
  edge_iterator ei;
265
  edge_iterator ei;
142
266
143
  /* Check that some of the edges entering the EXIT block exits a loop in
267
#ifdef ENABLE_CHECKING
144
     that USE is defined.  */
268
  /* Check that at least one of the edges entering the EXIT block exits
269
     the loop, or a superloop of that loop, that VAR is defined in.  */
270
  gimple def_stmt = SSA_NAME_DEF_STMT (var);
271
  basic_block def_bb = gimple_bb (def_stmt);
145
  FOR_EACH_EDGE (e, ei, exit->preds)
272
  FOR_EACH_EDGE (e, ei, exit->preds)
146
    {
273
    {
147
      def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
274
      struct loop *aloop = find_common_loop (def_bb->loop_father,
148
      if (!flow_bb_inside_loop_p (def_loop, e->dest))
275
					     e->src->loop_father);
276
      if (!flow_bb_inside_loop_p (aloop, e->dest))
149
	break;
277
	break;
150
    }
278
    }
151
279
152
  if (!e)
280
  gcc_checking_assert (e);
153
    return;
281
#endif
154
282
155
  phi = create_phi_node (NULL_TREE, exit);
283
  phi = create_phi_node (NULL_TREE, exit);
156
  create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
284
  create_new_def_for (var, phi, gimple_phi_result_ptr (phi));
157
  FOR_EACH_EDGE (e, ei, exit->preds)
285
  FOR_EACH_EDGE (e, ei, exit->preds)
158
    add_phi_arg (phi, use, e, UNKNOWN_LOCATION);
286
    add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
287
288
  if (dump_file && (dump_flags & TDF_DETAILS))
289
    {
290
      fprintf (dump_file, ";; Created LCSSA PHI: ");
291
      print_gimple_stmt (dump_file, phi, 0, dump_flags);
292
    }
159
}
293
}
160
294
161
/* Add exit phis for VAR that is used in LIVEIN.
295
/* Add exit phis for VAR that is used in LIVEIN.
162
   Exits of the loops are stored in EXITS.  */
296
   Exits of the loops are stored in LOOP_EXITS.  */
163
297
164
static void
298
static void
165
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
299
add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
166
{
300
{
167
  bitmap def;
168
  unsigned index;
301
  unsigned index;
302
  bitmap_iterator bi;
169
  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
303
  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
170
  bitmap_iterator bi;
304
  bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
171
305
172
  gcc_checking_assert (! virtual_operand_p (var));
306
  gcc_checking_assert (! virtual_operand_p (var));
173
  bitmap_clear_bit (livein, def_bb->index);
307
  gcc_assert (! bitmap_bit_p (use_blocks, def_bb->index));
174
308
175
  def = BITMAP_ALLOC (&loop_renamer_obstack);
309
  compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
176
  bitmap_set_bit (def, def_bb->index);
177
  compute_global_livein (livein, def);
178
  BITMAP_FREE (def);
179
310
180
  EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
311
  EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
181
    {
312
    {
182
      add_exit_phis_edge (BASIC_BLOCK (index), var);
313
      add_exit_phi (BASIC_BLOCK (index), var);
183
    }
314
    }
184
315
185
  /* Free the livein bitmap.  We'll not be needing it anymore, and
316
  BITMAP_FREE (live_exits);
186
     it may have grown quite large.  No reason to hold on to it.  */
187
  bitmap_clear (livein);
188
}
317
}
189
318
190
/* Add exit phis for the names marked in NAMES_TO_RENAME.
319
/* Add exit phis for the names marked in NAMES_TO_RENAME.
Lines 192-198 static void Link Here
192
   names are used are stored in USE_BLOCKS.  */
321
   names are used are stored in USE_BLOCKS.  */
193
322
194
static void
323
static void
195
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
324
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
196
{
325
{
197
  unsigned i;
326
  unsigned i;
198
  bitmap_iterator bi;
327
  bitmap_iterator bi;
Lines 203-230 static void Link Here
203
    }
332
    }
204
}
333
}
205
334
206
/* Returns a bitmap of all loop exit edge targets.  */
335
/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets.  */
207
336
208
static bitmap
337
static void
209
get_loops_exits (void)
338
get_loops_exits (bitmap *loop_exits)
210
{
339
{
211
  bitmap exits = BITMAP_ALLOC (&loop_renamer_obstack);
340
  loop_iterator li;
212
  basic_block bb;
341
  struct loop *loop;
342
  unsigned j;
213
  edge e;
343
  edge e;
214
  edge_iterator ei;
215
344
216
  FOR_EACH_BB (bb)
345
  FOR_EACH_LOOP (li, loop, 0)
217
    {
346
    {
218
      FOR_EACH_EDGE (e, ei, bb->preds)
347
      VEC(edge, heap) *exit_edges = get_loop_exit_edges (loop);
219
	if (e->src != ENTRY_BLOCK_PTR
348
      loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
220
	    && !flow_bb_inside_loop_p (e->src->loop_father, bb))
349
      FOR_EACH_VEC_ELT (edge, exit_edges, j, e)
221
	  {
350
        bitmap_set_bit (loop_exits[loop->num], e->dest->index);
222
	    bitmap_set_bit (exits, bb->index);
351
      VEC_free (edge, heap, exit_edges);
223
	    break;
224
	  }
225
    }
352
    }
226
227
  return exits;
228
}
353
}
229
354
230
/* For USE in BB, if it is used outside of the loop it is defined in,
355
/* For USE in BB, if it is used outside of the loop it is defined in,
Lines 301-308 find_uses_to_rename_bb (basic_block bb, bitmap *us Link Here
301
426
302
  FOR_EACH_EDGE (e, ei, bb->succs)
427
  FOR_EACH_EDGE (e, ei, bb->succs)
303
    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
428
    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
304
      find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e),
429
      {
305
			       use_blocks, need_phis);
430
        gimple phi = gsi_stmt (bsi);
431
	if (! virtual_operand_p (gimple_phi_result (phi)))
432
	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
433
				   use_blocks, need_phis);
434
      }
306
435
307
  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
436
  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
308
    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
437
    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
Lines 372-378 find_uses_to_rename (bitmap changed_bbs, bitmap *u Link Here
372
void
501
void
373
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
502
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
374
{
503
{
375
  bitmap loop_exits;
504
  bitmap *loop_exits;
376
  bitmap *use_blocks;
505
  bitmap *use_blocks;
377
  bitmap names_to_rename;
506
  bitmap names_to_rename;
378
507
Lines 380-393 rewrite_into_loop_closed_ssa (bitmap changed_bbs, Link Here
380
  if (number_of_loops () <= 1)
509
  if (number_of_loops () <= 1)
381
    return;
510
    return;
382
511
512
  /* If the pass has caused the SSA form to be out-of-date, update it
513
     now.  */
514
  update_ssa (update_flag);
515
383
  bitmap_obstack_initialize (&loop_renamer_obstack);
516
  bitmap_obstack_initialize (&loop_renamer_obstack);
384
517
385
  loop_exits = get_loops_exits ();
386
  names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack);
518
  names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack);
387
519
388
  /* If the pass has caused the SSA form to be out-of-date, update it
520
  /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
389
     now.  */
521
     that are the destination of an edge exiting loop number I.  */
390
  update_ssa (update_flag);
522
  loop_exits = XNEWVEC (bitmap, number_of_loops ());
523
  get_loops_exits (loop_exits);
391
524
392
  /* Uses of names to rename.  We don't have to initialize this array,
525
  /* Uses of names to rename.  We don't have to initialize this array,
393
     because we know that we will only have entries for the SSA names
526
     because we know that we will only have entries for the SSA names
Lines 403-408 rewrite_into_loop_closed_ssa (bitmap changed_bbs, Link Here
403
536
404
  bitmap_obstack_release (&loop_renamer_obstack);
537
  bitmap_obstack_release (&loop_renamer_obstack);
405
  free (use_blocks);
538
  free (use_blocks);
539
  free (loop_exits);
406
540
407
  /* Fix up all the names found to be used outside their original
541
  /* Fix up all the names found to be used outside their original
408
     loops.  */
542
     loops.  */

Return to bug 54146