#endif
#endif
+/* This is the maximum number of times we process any given block if the
+ latest loop depth count is smaller than this number. Only used for the
+ failure strategy to avoid infinite loops in calculate_global_regs_live. */
+#define MAX_LIVENESS_ROUNDS 20
+
/* Nonzero if the second flow pass has completed. */
int flow2_completed;
/* Regset of regs live when calls to `setjmp'-like functions happen. */
/* ??? Does this exist only for the setjmp-clobbered warning message? */
-regset regs_live_at_setjmp;
+static regset regs_live_at_setjmp;
/* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
that have to go in the same hard reg.
(remember, we are walking backward). This can be computed as current
pbi->insn_num - reg_deaths[regno].
At the end of processing each basic block, the remaining live registers
- are inspected and liferanges are increased same way so liverange of global
+ are inspected and live ranges are increased same way so liverange of global
registers are computed correctly.
The array is maintained clear for dead registers, so it can be safely reused
sbitmap_zero (update_life_blocks);
FOR_EACH_BB (bb)
{
- if (extent == UPDATE_LIFE_LOCAL)
+ if (bb->flags & BB_DIRTY)
{
- if (bb->flags & BB_DIRTY)
- {
- SET_BIT (update_life_blocks, bb->index);
- n++;
- }
- }
- else
- {
- /* ??? Bootstrap with -march=pentium4 fails to terminate
- with only a partial life update. */
SET_BIT (update_life_blocks, bb->index);
- if (bb->flags & BB_DIRTY)
- n++;
+ n++;
}
}
void
delete_dead_jumptables (void)
{
- rtx insn, next;
- for (insn = get_insns (); insn; insn = next)
+ basic_block bb;
+
+ /* A dead jump table does not belong to any basic block. Scan insns
+ between two adjacent basic blocks. */
+ FOR_EACH_BB (bb)
{
- next = NEXT_INSN (insn);
- if (LABEL_P (insn)
- && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
- && JUMP_P (next)
- && (GET_CODE (PATTERN (next)) == ADDR_VEC
- || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ rtx insn, next;
+
+ for (insn = NEXT_INSN (BB_END (bb));
+ insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
+ insn = next)
{
- if (dump_file)
- fprintf (dump_file, "Dead jumptable %i removed\n", INSN_UID (insn));
- delete_insn (NEXT_INSN (insn));
- delete_insn (insn);
- next = NEXT_INSN (next);
+ next = NEXT_INSN (insn);
+ if (LABEL_P (insn)
+ && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
+ && JUMP_P (next)
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ {
+ rtx label = insn, jump = next;
+
+ if (dump_file)
+ fprintf (dump_file, "Dead jumptable %i removed\n",
+ INSN_UID (insn));
+
+ next = NEXT_INSN (next);
+ delete_insn (jump);
+ delete_insn (label);
+ }
}
}
}
{
basic_block *queue, *qhead, *qtail, *qend, bb;
regset tmp, new_live_at_end, invalidated_by_call;
+ regset registers_made_dead;
+ bool failure_strategy_required = false;
+ int *block_accesses;
/* The registers that are modified within this in block. */
regset *local_sets;
tmp = ALLOC_REG_SET (®_obstack);
new_live_at_end = ALLOC_REG_SET (®_obstack);
invalidated_by_call = ALLOC_REG_SET (®_obstack);
+ registers_made_dead = ALLOC_REG_SET (®_obstack);
/* Inconveniently, this is only readily available in hard reg set form. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
}
}
+ block_accesses = xcalloc (last_basic_block, sizeof (int));
+
/* We clean aux when we remove the initially-enqueued bbs, but we
don't enqueue ENTRY and EXIT initially, so clean them upfront and
unconditionally. */
from GLOBAL_LIVE_AT_START. In the former case, the register
could go away only if it disappeared from GLOBAL_LIVE_AT_START
for one of the successor blocks. By induction, that cannot
- occur. */
+ occur.
+
+ ??? This reasoning doesn't work if we start from non-empty initial
+ GLOBAL_LIVE_AT_START sets. And there are actually two problems:
+ 1) Updating may not terminate (endless oscillation).
+ 2) Even if it does (and it usually does), the resulting information
+ may be inaccurate. Consider for example the following case:
+
+ a = ...;
+ while (...) {...} -- 'a' not mentioned at all
+ ... = a;
+
+ If the use of 'a' is deleted between two calculations of liveness
+ information and the initial sets are not cleared, the information
+ about a's liveness will get stuck inside the loop and the set will
+ appear not to be dead.
+
+ We do not attempt to solve 2) -- the information is conservatively
+ correct (i.e. we never claim that something live is dead) and the
+ amount of optimization opportunities missed due to this problem is
+ not significant.
+
+ 1) is more serious. In order to fix it, we monitor the number of times
+ each block is processed. Once one of the blocks has been processed more
+ times than the maximum number of rounds, we use the following strategy:
+ When a register disappears from one of the sets, we add it to a MAKE_DEAD
+ set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and
+ add the blocks with changed sets into the queue. Thus we are guaranteed
+ to terminate (the worst case corresponds to all registers in MADE_DEAD,
+ in which case the original reasoning above is valid), but in general we
+ only fix up a few offending registers.
+
+ The maximum number of rounds for computing liveness is the largest of
+ MAX_LIVENESS_ROUNDS and the latest loop depth count for this function. */
+
while (qhead != qtail)
{
int rescan, changed;
qhead = queue;
bb->aux = NULL;
+ /* Should we start using the failure strategy? */
+ if (bb != ENTRY_BLOCK_PTR)
+ {
+ int max_liveness_rounds =
+ MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth);
+
+ block_accesses[bb->index]++;
+ if (block_accesses[bb->index] > max_liveness_rounds)
+ failure_strategy_required = true;
+ }
+
/* Begin by propagating live_at_start from the successor blocks. */
CLEAR_REG_SET (new_live_at_end);
if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
continue;
+ if (failure_strategy_required)
+ {
+ /* Get the list of registers that were removed from the
+ bb->global_live_at_start set. */
+ bitmap_and_compl (tmp, bb->global_live_at_start,
+ new_live_at_end);
+ if (!bitmap_empty_p (tmp))
+ {
+ bool pbb_changed;
+ basic_block pbb;
+
+ /* It should not happen that one of registers we have
+ removed last time is disappears again before any other
+ register does. */
+ pbb_changed = bitmap_ior_into (registers_made_dead, tmp);
+ gcc_assert (pbb_changed);
+
+ /* Now remove the registers from all sets. */
+ FOR_EACH_BB (pbb)
+ {
+ pbb_changed = false;
+
+ pbb_changed
+ |= bitmap_and_compl_into (pbb->global_live_at_start,
+ registers_made_dead);
+ pbb_changed
+ |= bitmap_and_compl_into (pbb->global_live_at_end,
+ registers_made_dead);
+ if (!pbb_changed)
+ continue;
+
+ /* Note the (possible) change. */
+ if (blocks_out)
+ SET_BIT (blocks_out, pbb->index);
+
+ /* Makes sure to really rescan the block. */
+ if (local_sets[pbb->index - (INVALID_BLOCK + 1)])
+ {
+ FREE_REG_SET (local_sets[pbb->index - (INVALID_BLOCK + 1)]);
+ FREE_REG_SET (cond_local_sets[pbb->index - (INVALID_BLOCK + 1)]);
+ local_sets[pbb->index - (INVALID_BLOCK + 1)] = 0;
+ }
+
+ /* Add it to the queue. */
+ if (pbb->aux == NULL)
+ {
+ *qtail++ = pbb;
+ if (qtail == qend)
+ qtail = queue;
+ pbb->aux = pbb;
+ }
+ }
+ continue;
+ }
+ } /* end of failure_strategy_required */
+
COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
}
FREE_REG_SET (tmp);
FREE_REG_SET (new_live_at_end);
FREE_REG_SET (invalidated_by_call);
+ FREE_REG_SET (registers_made_dead);
if (blocks_out)
{
}
}
+ free (block_accesses);
free (queue);
free (cond_local_sets);
free (local_sets);
else
pbi->reg_next_use = NULL;
- pbi->new_set = BITMAP_XMALLOC ();
+ pbi->new_set = BITMAP_ALLOC (NULL);
#ifdef HAVE_conditional_execution
pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
free_reg_cond_life_info);
- pbi->reg_cond_reg = BITMAP_XMALLOC ();
+ pbi->reg_cond_reg = BITMAP_ALLOC (NULL);
/* If this block ends in a conditional branch, for each register
live from one side of the branch and not the other, record the
/* Identify the successor blocks. */
bb_true = EDGE_SUCC (bb, 0)->dest;
- if (EDGE_COUNT (bb->succs) > 1)
+ if (!single_succ_p (bb))
{
bb_false = EDGE_SUCC (bb, 1)->dest;
(TREE_TYPE (current_function_decl))))
&& (flags & PROP_SCAN_DEAD_STORES)
&& (EDGE_COUNT (bb->succs) == 0
- || (EDGE_COUNT (bb->succs) == 1
- && EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
+ || (single_succ_p (bb)
+ && single_succ (bb) == EXIT_BLOCK_PTR
&& ! current_function_calls_eh_return)))
{
rtx insn, set;
{
free_EXPR_LIST_list (&pbi->mem_set_list);
- BITMAP_XFREE (pbi->new_set);
+ BITMAP_FREE (pbi->new_set);
#ifdef HAVE_conditional_execution
splay_tree_delete (pbi->reg_cond_dead);
- BITMAP_XFREE (pbi->reg_cond_reg);
+ BITMAP_FREE (pbi->reg_cond_reg);
#endif
if (pbi->flags & PROP_REG_INFO)
register allocators to prioritize pseudos for allocation to hard regs.
More accurate reference counts generally lead to better register allocation.
- F is the first insn to be scanned.
-
- LOOP_STEP denotes how much loop_depth should be incremented per
- loop nesting level in order to increase the ref count more for
- references in a loop.
-
It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
possibly other information which is used by the register allocators. */
void
-recompute_reg_usage (rtx f ATTRIBUTE_UNUSED, int loop_step ATTRIBUTE_UNUSED)
+recompute_reg_usage (void)
{
allocate_reg_life_data ();
/* distribute_notes in combiner fails to convert some of the REG_UNUSED notes
OSDN Git Service
