/* Allocation for dataflow support routines.
- Copyright (C) 1999-2022 Free Software Foundation, Inc.
+ Copyright (C) 1999-2024 Free Software Foundation, Inc.
Originally contributed by Michael P. Hayes
(m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
if (optimize > 1)
df_live_add_problem ();
- df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
- df->n_blocks = post_order_compute (df->postorder, true, true);
- inverted_post_order_compute (&df->postorder_inverted);
- gcc_assert ((unsigned) df->n_blocks == df->postorder_inverted.length ());
-
df->hard_regs_live_count = XCNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
df_hard_reg_init ();
{}
/* opt_pass methods: */
- virtual bool gate (function *) { return optimize > 0; }
- virtual unsigned int execute (function *)
+ bool gate (function *) final override { return optimize > 0; }
+ unsigned int execute (function *) final override
{
return rest_of_handle_df_initialize ();
}
{}
/* opt_pass methods: */
- virtual bool gate (function *) { return optimize == 0; }
- virtual unsigned int execute (function *)
+ bool gate (function *) final override { return optimize == 0; }
+ unsigned int execute (function *) final override
{
return rest_of_handle_df_initialize ();
}
}
free (df->postorder);
- df->postorder_inverted.release ();
+ free (df->postorder_inverted);
free (df->hard_regs_live_count);
free (df);
df = NULL;
{}
/* opt_pass methods: */
- virtual unsigned int execute (function *)
+ unsigned int execute (function *) final override
{
return rest_of_handle_df_finish ();
}
/* Helper function for df_worklist_dataflow.
Propagate the dataflow forward.
Given a BB_INDEX, do the dataflow propagation
- and set bits on for successors in PENDING
+ and set bits on for successors in PENDING for earlier
+ and WORKLIST for later in bbindex_to_postorder
if the out set of the dataflow has changed.
AGE specify time when BB was visited last time.
static bool
df_worklist_propagate_forward (struct dataflow *dataflow,
- unsigned bb_index,
- unsigned *bbindex_to_postorder,
- bitmap pending,
- sbitmap considered,
+ unsigned bb_index,
+ unsigned *bbindex_to_postorder,
+ bitmap worklist,
+ bitmap pending,
+ sbitmap considered,
vec<int> &last_change_age,
int age)
{
unsigned ob_index = e->dest->index;
if (bitmap_bit_p (considered, ob_index))
- bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ {
+ if (bbindex_to_postorder[bb_index]
+ < bbindex_to_postorder[ob_index])
+ bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
+ else
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
}
return true;
}
static bool
df_worklist_propagate_backward (struct dataflow *dataflow,
- unsigned bb_index,
- unsigned *bbindex_to_postorder,
- bitmap pending,
- sbitmap considered,
+ unsigned bb_index,
+ unsigned *bbindex_to_postorder,
+ bitmap worklist,
+ bitmap pending,
+ sbitmap considered,
vec<int> &last_change_age,
int age)
{
unsigned ob_index = e->src->index;
if (bitmap_bit_p (considered, ob_index))
- bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ {
+ if (bbindex_to_postorder[bb_index]
+ < bbindex_to_postorder[ob_index])
+ bitmap_set_bit (worklist, bbindex_to_postorder[ob_index]);
+ else
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
}
return true;
}
and pending is for the next. */
while (!bitmap_empty_p (pending))
{
- bitmap_iterator bi;
- unsigned int index;
-
std::swap (pending, worklist);
- EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
+ do
{
+ unsigned index = bitmap_clear_first_set_bit (worklist);
+
unsigned bb_index;
dcount++;
- bitmap_clear_bit (pending, index);
bb_index = blocks_in_postorder[index];
prev_age = last_visit_age[index];
if (dir == DF_FORWARD)
changed = df_worklist_propagate_forward (dataflow, bb_index,
bbindex_to_postorder,
- pending, considered,
+ worklist, pending,
+ considered,
last_change_age,
prev_age);
else
changed = df_worklist_propagate_backward (dataflow, bb_index,
bbindex_to_postorder,
- pending, considered,
+ worklist, pending,
+ considered,
last_change_age,
prev_age);
last_visit_age[index] = ++age;
if (changed)
last_change_age[index] = age;
}
- bitmap_clear (worklist);
+ while (!bitmap_empty_p (worklist));
}
BITMAP_FREE (worklist);
{
int i;
- /* These should be the same. */
- gcc_assert ((unsigned) df->n_blocks == df->postorder_inverted.length ());
-
/* We need to do this before the df_verify_all because this is
not kept incrementally up to date. */
df_compute_regs_ever_live (false);
if (dflow->problem->dir == DF_FORWARD)
df_analyze_problem (dflow,
df->blocks_to_analyze,
- df->postorder_inverted.address (),
- df->postorder_inverted.length ());
+ df->postorder_inverted,
+ df->n_blocks);
else
df_analyze_problem (dflow,
df->blocks_to_analyze,
bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
free (df->postorder);
- df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
- df->n_blocks = post_order_compute (df->postorder, true, true);
- df->postorder_inverted.truncate (0);
- inverted_post_order_compute (&df->postorder_inverted);
+ free (df->postorder_inverted);
+ /* For DF_FORWARD use a RPO on the forward graph. Since we want to
+ have unreachable blocks deleted use post_order_compute and reverse
+ the order. */
+ df->postorder_inverted = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ df->n_blocks = post_order_compute (df->postorder_inverted, true, true);
+ for (int i = 0; i < df->n_blocks / 2; ++i)
+ std::swap (df->postorder_inverted[i],
+ df->postorder_inverted[df->n_blocks - 1 - i]);
+ /* For DF_BACKWARD use a RPO on the reverse graph. */
+ df->postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int n = inverted_rev_post_order_compute (cfun, df->postorder);
+ gcc_assert (n == df->n_blocks);
for (int i = 0; i < df->n_blocks; i++)
bitmap_set_bit (current_all_blocks, df->postorder[i]);
{
/* Verify that POSTORDER_INVERTED only contains blocks reachable from
the ENTRY block. */
- for (unsigned int i = 0; i < df->postorder_inverted.length (); i++)
+ for (int i = 0; i < df->n_blocks; i++)
gcc_assert (bitmap_bit_p (current_all_blocks,
df->postorder_inverted[i]));
}
if (df->analyze_subset)
{
bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
- df->n_blocks = df_prune_to_subcfg (df->postorder,
- df->n_blocks, df->blocks_to_analyze);
- unsigned int newlen = df_prune_to_subcfg (df->postorder_inverted.address (),
- df->postorder_inverted.length (),
- df->blocks_to_analyze);
- df->postorder_inverted.truncate (newlen);
+ unsigned int newlen = df_prune_to_subcfg (df->postorder, df->n_blocks,
+ df->blocks_to_analyze);
+ df_prune_to_subcfg (df->postorder_inverted, df->n_blocks,
+ df->blocks_to_analyze);
+ df->n_blocks = newlen;
BITMAP_FREE (current_all_blocks);
}
else
Returns the number of blocks which is always loop->num_nodes. */
static int
-loop_post_order_compute (int *post_order, class loop *loop)
+loop_rev_post_order_compute (int *post_order, class loop *loop)
{
edge_iterator *stack;
int sp;
- int post_order_num = 0;
+ int post_order_num = loop->num_nodes - 1;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
time, check its successors. */
stack[sp++] = ei_start (dest->succs);
else
- post_order[post_order_num++] = dest->index;
+ post_order[post_order_num--] = dest->index;
}
else
{
if (ei_one_before_end_p (ei)
&& src != loop_preheader_edge (loop)->src)
- post_order[post_order_num++] = src->index;
+ post_order[post_order_num--] = src->index;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
free (stack);
- return post_order_num;
+ return loop->num_nodes;
}
/* Compute the reverse top sort order of the inverted sub-CFG specified
by LOOP. Returns the number of blocks which is always loop->num_nodes. */
-static void
-loop_inverted_post_order_compute (vec<int> *post_order, class loop *loop)
+static int
+loop_inverted_rev_post_order_compute (int *post_order, class loop *loop)
{
basic_block bb;
edge_iterator *stack;
int sp;
-
- post_order->reserve_exact (loop->num_nodes);
+ int post_order_num = loop->num_nodes - 1;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
time, check its predecessors. */
stack[sp++] = ei_start (pred->preds);
else
- post_order->quick_push (pred->index);
+ post_order[post_order_num--] = pred->index;
}
else
{
if (flow_bb_inside_loop_p (loop, bb)
&& ei_one_before_end_p (ei))
- post_order->quick_push (bb->index);
+ post_order[post_order_num--] = bb->index;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
}
free (stack);
+ return loop->num_nodes;
}
df_analyze_loop (class loop *loop)
{
free (df->postorder);
+ free (df->postorder_inverted);
df->postorder = XNEWVEC (int, loop->num_nodes);
- df->postorder_inverted.truncate (0);
- df->n_blocks = loop_post_order_compute (df->postorder, loop);
- loop_inverted_post_order_compute (&df->postorder_inverted, loop);
+ df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
+ df->n_blocks = loop_rev_post_order_compute (df->postorder_inverted, loop);
+ int n = loop_inverted_rev_post_order_compute (df->postorder, loop);
gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
- gcc_assert (df->postorder_inverted.length () == loop->num_nodes);
+ gcc_assert ((unsigned) n == loop->num_nodes);
bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack);
for (int i = 0; i < df->n_blocks; ++i)
if (dir == DF_FORWARD)
{
- gcc_assert (df->postorder_inverted.length ());
- return df->postorder_inverted.length ();
+ gcc_assert (df->postorder_inverted);
+ return df->n_blocks;
}
gcc_assert (df->postorder);
if (dir == DF_FORWARD)
{
- gcc_assert (df->postorder_inverted.length ());
- return df->postorder_inverted.address ();
+ gcc_assert (df->postorder_inverted);
+ return df->postorder_inverted;
}
gcc_assert (df->postorder);
return df->postorder;
return df_find_use (insn, reg) != NULL;
}
+/* If REG has a single definition, return its known value, otherwise return
+ null. */
+
+rtx
+df_find_single_def_src (rtx reg)
+{
+ rtx src = NULL_RTX;
+
+ /* Don't look through unbounded number of single definition REG copies,
+ there might be loops for sources with uninitialized variables. */
+ for (int cnt = 0; cnt < 128; cnt++)
+ {
+ df_ref adef = DF_REG_DEF_CHAIN (REGNO (reg));
+ if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
+ || DF_REF_IS_ARTIFICIAL (adef)
+ || (DF_REF_FLAGS (adef)
+ & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
+ return NULL_RTX;
+
+ rtx set = single_set (DF_REF_INSN (adef));
+ if (set == NULL || !rtx_equal_p (SET_DEST (set), reg))
+ return NULL_RTX;
+
+ rtx note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
+ if (note && function_invariant_p (XEXP (note, 0)))
+ return XEXP (note, 0);
+ src = SET_SRC (set);
+
+ if (REG_P (src))
+ {
+ reg = src;
+ continue;
+ }
+ break;
+ }
+ if (!function_invariant_p (src))
+ return NULL_RTX;
+
+ return src;
+}
+
\f
/*----------------------------------------------------------------------------
Debugging and printing functions.
projects / thirdparty / gcc.git / blobdiff