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

Collapse All | Expand All

(-)tree-into-ssa.c (-12 / +23 lines)
Lines 407-452 set_current_def (tree var, tree def) Link Here
407
   to include global livein (i.e., it modifies the underlying bitmap
407
   to include global livein (i.e., it modifies the underlying bitmap
408
   for LIVEIN).  */
408
   for LIVEIN).  */
409
409
410
/*void
411
compute_global_livein (bitmap livein, bitmap def_blocks)*/
412
void compute_global_livein2 (bitmap, bitmap, int);
410
void
413
void
411
compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)
414
compute_global_livein2 (bitmap livein, bitmap def_blocks, int depth)
412
{
415
{
413
  basic_block bb, *worklist, *tos;
416
  basic_block bb;
414
  unsigned i;
417
  unsigned i;
415
  bitmap_iterator bi;
418
  bitmap_iterator bi;
419
  VEC (basic_block, heap) *worklist;
416
420
417
  tos = worklist
421
  /* Normally the work list size is bounded by the number of basic
418
    = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
422
     blocks in the largest loop.  We don't know this number, but we
423
     can be fairly sure that it will be relatively small.  */
424
  worklist = VEC_alloc (basic_block, heap, MAX (8, n_basic_blocks / 128));
419
425
420
  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
426
  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
421
    *tos++ = BASIC_BLOCK (i);
427
    VEC_safe_push (basic_block, heap, worklist, BASIC_BLOCK (i));
422
428
423
  /* Iterate until the worklist is empty.  */
429
  /* Iterate until the worklist is empty.  */
424
  while (tos != worklist)
430
  while (! VEC_empty (basic_block, worklist))
425
    {
431
    {
426
      edge e;
432
      edge e;
427
      edge_iterator ei;
433
      edge_iterator ei;
428
434
429
      /* Pull a block off the worklist.  */
435
      /* Pull a block off the worklist.  */
430
      bb = *--tos;
436
      bb = VEC_pop (basic_block, worklist);
437
438
      /* Make sure we have at least enough room in the work list
439
	 for all predecessors of this block.  */
440
      VEC_reserve (basic_block, heap, worklist, EDGE_COUNT (bb->preds));
431
441
432
      /* For each predecessor block.  */
442
      /* For each predecessor block.  */
433
      FOR_EACH_EDGE (e, ei, bb->preds)
443
      FOR_EACH_EDGE (e, ei, bb->preds)
434
	{
444
	{
435
	  basic_block pred = e->src;
445
	  basic_block pred = e->src;
436
	  int pred_index = pred->index;
446
	  int pred_index = pred->index;
447
	  if (pred->loop_depth >= depth)
448
	    continue;
437
449
438
	  /* None of this is necessary for the entry block.  */
450
	  /* None of this is necessary for the entry block.  */
439
	  if (pred != ENTRY_BLOCK_PTR
451
	  if (pred != ENTRY_BLOCK_PTR
440
	      && ! bitmap_bit_p (livein, pred_index)
452
	      && ! bitmap_bit_p (def_blocks, pred_index)
441
	      && ! bitmap_bit_p (def_blocks, pred_index))
453
	      && bitmap_set_bit (livein, pred_index))
442
	    {
454
	    {
443
	      *tos++ = pred;
455
	      VEC_quick_push (basic_block, worklist, pred);
444
	      bitmap_set_bit (livein, pred_index);
445
	    }
456
	    }
446
	}
457
	}
447
    }
458
    }
448
459
449
  free (worklist);
460
  VEC_free (basic_block, heap, worklist);
450
}
461
}
451
462
452
463
(-)tree-ssa-loop-manip.c (-17 / +47 lines)
Lines 27-32 along with GCC; see the file COPYING3. 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 149-159 add_exit_phis_edge (basic_block exit, tr Link Here
149
		      gimple_phi_result_ptr (phi));
150
		      gimple_phi_result_ptr (phi));
150
  FOR_EACH_EDGE (e, ei, exit->preds)
151
  FOR_EACH_EDGE (e, ei, exit->preds)
151
    add_phi_arg (phi, use, e, UNKNOWN_LOCATION);
152
    add_phi_arg (phi, use, e, UNKNOWN_LOCATION);
153
154
  if (dump_file && (dump_flags & TDF_DETAILS))
155
    {
156
      fprintf (dump_file, ";; Created LCSSA PHI: ");
157
      print_gimple_stmt (dump_file, phi, 0, dump_flags);
158
    }
152
}
159
}
153
160
154
/* Add exit phis for VAR that is used in LIVEIN.
161
/* Add exit phis for VAR that is used in LIVEIN.
155
   Exits of the loops are stored in EXITS.  */
162
   Exits of the loops are stored in EXITS.  */
156
163
void compute_global_livein2 (bitmap, bitmap, int);
157
static void
164
static void
158
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
165
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
159
{
166
{
Lines 162-181 add_exit_phis_var (tree var, bitmap live Link Here
162
  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
169
  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
163
  bitmap_iterator bi;
170
  bitmap_iterator bi;
164
171
165
  if (is_gimple_reg (var))
172
  gcc_checking_assert (is_gimple_reg (var));
166
    bitmap_clear_bit (livein, def_bb->index);
173
  bitmap_clear_bit (livein, def_bb->index);
167
  else
168
    bitmap_set_bit (livein, def_bb->index);
169
174
175
timevar_push (TV_GLOBAL_ALLOC);
170
  def = BITMAP_ALLOC (NULL);
176
  def = BITMAP_ALLOC (NULL);
171
  bitmap_set_bit (def, def_bb->index);
177
  bitmap_set_bit (def, def_bb->index);
172
  compute_global_livein (livein, def);
178
  compute_global_livein2(livein, def, def_bb->loop_depth);
173
  BITMAP_FREE (def);
179
  BITMAP_FREE (def);
180
timevar_pop (TV_GLOBAL_ALLOC);
174
181
175
  EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
182
  EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
176
    {
183
    {
177
      add_exit_phis_edge (BASIC_BLOCK (index), var);
184
      add_exit_phis_edge (BASIC_BLOCK (index), var);
178
    }
185
    }
186
187
  /* The LIVEIN bitmap can have grown really large, but we're not
188
     going to use it anymore.  So release all storage for it as
189
     early as possible, i.e. here.  */
190
  bitmap_clear (livein);
179
}
191
}
180
192
181
/* Add exit phis for the names marked in NAMES_TO_RENAME.
193
/* Add exit phis for the names marked in NAMES_TO_RENAME.
Lines 228-241 find_uses_to_rename_use (basic_block bb, Link Here
228
{
240
{
229
  unsigned ver;
241
  unsigned ver;
230
  basic_block def_bb;
242
  basic_block def_bb;
231
  struct loop *def_loop;
243
  struct loop *def_loop, *use_loop, *common_loop;
232
244
233
  if (TREE_CODE (use) != SSA_NAME)
245
  if (TREE_CODE (use) != SSA_NAME)
234
    return;
246
    return;
235
247
  gcc_checking_assert (is_gimple_reg (use));
236
  /* We don't need to keep virtual operands in loop-closed form.  */
237
  if (!is_gimple_reg (use))
238
    return;
239
248
240
  ver = SSA_NAME_VERSION (use);
249
  ver = SSA_NAME_VERSION (use);
241
  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
250
  def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
Lines 252-257 find_uses_to_rename_use (basic_block bb, Link Here
252
  if (flow_bb_inside_loop_p (def_loop, bb))
261
  if (flow_bb_inside_loop_p (def_loop, bb))
253
    return;
262
    return;
254
263
264
  /* If the def and the use are nested in a common outer loop, we don't
265
     want to look in the loop containing use.  Look for a loop at the
266
     same loop depth and mark the header.  */
267
  use_loop = bb->loop_father;
268
  common_loop = find_common_loop (def_loop, use_loop);
269
  if (common_loop && use_loop != common_loop)
270
    {
271
      while (loop_outer (use_loop) != common_loop)
272
        use_loop = loop_outer (use_loop);
273
      bb = use_loop->header;
274
    }
275
255
  if (!use_blocks[ver])
276
  if (!use_blocks[ver])
256
    use_blocks[ver] = BITMAP_ALLOC (NULL);
277
    use_blocks[ver] = BITMAP_ALLOC (NULL);
257
  bitmap_set_bit (use_blocks[ver], bb->index);
278
  bitmap_set_bit (use_blocks[ver], bb->index);
Lines 274-287 find_uses_to_rename_stmt (gimple stmt, b Link Here
274
  if (is_gimple_debug (stmt))
295
  if (is_gimple_debug (stmt))
275
    return;
296
    return;
276
297
277
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
298
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
278
    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
299
    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
279
}
300
}
280
301
281
/* Marks names that are used in BB and outside of the loop they are
302
/* Marks names that are used in BB and outside of the loop they are
282
   defined in for rewrite.  Records the set of blocks in that the ssa
303
   defined in for rewrite.  Records the set of blocks in that the ssa
283
   names are defined to USE_BLOCKS.  Record the SSA names that will
304
   names are defined to USE_BLOCKS.  Record the SSA names that will
284
   need exit PHIs in NEED_PHIS.  */
305
   need exit PHIs in NEED_PHIS.
306
   We don't need to keep virtual operands in loop-closed form.  */
285
307
286
static void
308
static void
287
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
309
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
Lines 292-299 find_uses_to_rename_bb (basic_block bb, Link Here
292
314
293
  FOR_EACH_EDGE (e, ei, bb->succs)
315
  FOR_EACH_EDGE (e, ei, bb->succs)
294
    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
316
    for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
295
      find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e),
317
      {
296
			       use_blocks, need_phis);
318
	gimple phi = gsi_stmt (bsi);
319
	if (is_gimple_reg (PHI_RESULT (phi)))
320
	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
321
				   use_blocks, need_phis);
322
      }
297
323
298
  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
324
  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
299
    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
325
    find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis);
Lines 397-402 rewrite_into_loop_closed_ssa (bitmap cha Link Here
397
  /* Fix up all the names found to be used outside their original
423
  /* Fix up all the names found to be used outside their original
398
     loops.  */
424
     loops.  */
399
  update_ssa (TODO_update_ssa);
425
  update_ssa (TODO_update_ssa);
426
timevar_push (TV_GLOBAL_ALLOC);
427
  verify_loop_closed_ssa (false);
428
timevar_pop (TV_GLOBAL_ALLOC);
400
}
429
}
401
430
402
/* Check invariants of the loop closed ssa form for the USE in BB.  */
431
/* Check invariants of the loop closed ssa form for the USE in BB.  */
Lines 407-413 check_loop_closed_ssa_use (basic_block b Link Here
407
  gimple def;
436
  gimple def;
408
  basic_block def_bb;
437
  basic_block def_bb;
409
438
410
  if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
439
  if (TREE_CODE (use) != SSA_NAME
440
      || ! is_gimple_reg (use))
411
    return;
441
    return;
412
442
413
  def = SSA_NAME_DEF_STMT (use);
443
  def = SSA_NAME_DEF_STMT (use);
Lines 427-433 check_loop_closed_ssa_stmt (basic_block Link Here
427
  if (is_gimple_debug (stmt))
457
  if (is_gimple_debug (stmt))
428
    return;
458
    return;
429
459
430
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
460
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
431
    check_loop_closed_ssa_use (bb, var);
461
    check_loop_closed_ssa_use (bb, var);
432
}
462
}
433
463

Return to bug 54146