/* Allocation for dataflow support routines.
- Copyright (C) 1999-2016 Free Software Foundation, Inc.
+ Copyright (C) 1999-2021 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)
Artificial defs and uses occur both at the beginning and ends of blocks.
- For blocks that area at the destination of eh edges, the
+ For blocks that are at the destination of eh edges, the
artificial uses and defs occur at the beginning. The defs relate
to the registers specified in EH_RETURN_DATA_REGNO and the uses
- relate to the registers specified in ED_USES. Logically these
+ relate to the registers specified in EH_USES. Logically these
defs and uses should really occur along the eh edge, but there is
- no convenient way to do this. Artificial edges that occur at the
+ no convenient way to do this. Artificial defs that occur at the
beginning of the block have the DF_REF_AT_TOP flag set.
Artificial uses occur at the end of all blocks. These arise from
#include "backend.h"
#include "rtl.h"
#include "df.h"
+#include "memmodel.h"
#include "emit-rtl.h"
#include "cfganal.h"
#include "tree-pass.h"
Functions to create, destroy and manipulate an instance of df.
----------------------------------------------------------------------------*/
-struct df_d *df;
+class df_d *df;
/* Add PROBLEM (and any dependent problems) to the DF instance. */
void
-df_add_problem (struct df_problem *problem)
+df_add_problem (const struct df_problem *problem)
{
struct dataflow *dflow;
int i;
/* This block is called to change the focus from one subset
to another. */
int p;
- bitmap_head diff;
- bitmap_initialize (&diff, &df_bitmap_obstack);
- bitmap_and_compl (&diff, df->blocks_to_analyze, blocks);
+ auto_bitmap diff (&df_bitmap_obstack);
+ bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
for (p = 0; p < df->num_problems_defined; p++)
{
struct dataflow *dflow = df->problems_in_order[p];
bitmap_iterator bi;
unsigned int bb_index;
- EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
{
basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
if (bb)
}
}
}
-
- bitmap_clear (&diff);
}
else
{
void
df_remove_problem (struct dataflow *dflow)
{
- struct df_problem *problem;
+ const struct df_problem *problem;
int i;
if (!dflow)
rest_of_handle_df_initialize (void)
{
gcc_assert (!df);
- df = XCNEW (struct df_d);
+ df = XCNEW (class df_d);
df->changeable_flags = 0;
bitmap_obstack_initialize (&df_bitmap_obstack);
df_live_add_problem ();
df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
- df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
df->n_blocks = post_order_compute (df->postorder, true, true);
- df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
- gcc_assert (df->n_blocks == df->n_blocks_inverted);
+ 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);
}
free (df->postorder);
- free (df->postorder_inverted);
+ df->postorder_inverted.release ();
free (df->hard_regs_live_count);
free (df);
df = NULL;
The general data flow analysis engine.
----------------------------------------------------------------------------*/
-/* Return time BB when it was visited for last time. */
-#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
-
/* Helper function for df_worklist_dataflow.
Propagate the dataflow forward.
Given a BB_INDEX, do the dataflow propagation
unsigned *bbindex_to_postorder,
bitmap pending,
sbitmap considered,
- ptrdiff_t age)
+ vec<int> &last_change_age,
+ int age)
{
edge e;
edge_iterator ei;
if (EDGE_COUNT (bb->preds) > 0)
FOR_EACH_EDGE (e, ei, bb->preds)
{
- if (age <= BB_LAST_CHANGE_AGE (e->src)
+ if (bbindex_to_postorder[e->src->index] < last_change_age.length ()
+ && age <= last_change_age[bbindex_to_postorder[e->src->index]]
&& bitmap_bit_p (considered, e->src->index))
changed |= dataflow->problem->con_fun_n (e);
}
unsigned *bbindex_to_postorder,
bitmap pending,
sbitmap considered,
- ptrdiff_t age)
+ vec<int> &last_change_age,
+ int age)
{
edge e;
edge_iterator ei;
if (EDGE_COUNT (bb->succs) > 0)
FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (age <= BB_LAST_CHANGE_AGE (e->dest)
+ if (bbindex_to_postorder[e->dest->index] < last_change_age.length ()
+ && age <= last_change_age[bbindex_to_postorder[e->dest->index]]
&& bitmap_bit_p (considered, e->dest->index))
changed |= dataflow->problem->con_fun_n (e);
}
worklists (we are processing WORKLIST and storing new BBs to visit in
PENDING).
- As an optimization we maintain ages when BB was changed (stored in bb->aux)
- and when it was last visited (stored in last_visit_age). This avoids need
- to re-do confluence function for edges to basic blocks whose source
- did not change since destination was visited last time. */
+ As an optimization we maintain ages when BB was changed (stored in
+ last_change_age) and when it was last visited (stored in last_visit_age).
+ This avoids need to re-do confluence function for edges to basic blocks
+ whose source did not change since destination was visited last time. */
static void
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
int age = 0;
bool changed;
vec<int> last_visit_age = vNULL;
+ vec<int> last_change_age = vNULL;
int prev_age;
- basic_block bb;
- int i;
- last_visit_age.safe_grow_cleared (n_blocks);
+ last_visit_age.safe_grow_cleared (n_blocks, true);
+ last_change_age.safe_grow_cleared (n_blocks, true);
/* Double-queueing. Worklist is for the current iteration,
and pending is for the next. */
bitmap_clear_bit (pending, index);
bb_index = blocks_in_postorder[index];
- bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
prev_age = last_visit_age[index];
if (dir == DF_FORWARD)
changed = df_worklist_propagate_forward (dataflow, bb_index,
bbindex_to_postorder,
pending, considered,
+ last_change_age,
prev_age);
else
changed = df_worklist_propagate_backward (dataflow, bb_index,
bbindex_to_postorder,
pending, considered,
+ last_change_age,
prev_age);
last_visit_age[index] = ++age;
if (changed)
- bb->aux = (void *)(ptrdiff_t)age;
+ last_change_age[index] = age;
}
bitmap_clear (worklist);
}
- for (i = 0; i < n_blocks; i++)
- BASIC_BLOCK_FOR_FN (cfun, blocks_in_postorder[i])->aux = NULL;
BITMAP_FREE (worklist);
BITMAP_FREE (pending);
last_visit_age.release ();
+ last_change_age.release ();
/* Dump statistics. */
if (dump_file)
fprintf (dump_file, "df_worklist_dataflow_doublequeue:"
- "n_basic_blocks %d n_edges %d"
+ " n_basic_blocks %d n_edges %d"
" count %d (%5.2g)\n",
n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun),
- dcount, dcount / (float)n_basic_blocks_for_fn (cfun));
+ dcount, dcount / (double)n_basic_blocks_for_fn (cfun));
}
/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
int n_blocks)
{
bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
- sbitmap considered = sbitmap_alloc (last_basic_block_for_fn (cfun));
bitmap_iterator bi;
unsigned int *bbindex_to_postorder;
int i;
bbindex_to_postorder[i] = last_basic_block_for_fn (cfun);
/* Initialize the considered map. */
+ auto_sbitmap considered (last_basic_block_for_fn (cfun));
bitmap_clear (considered);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
{
blocks_in_postorder,
bbindex_to_postorder,
n_blocks);
- sbitmap_free (considered);
free (bbindex_to_postorder);
}
int i;
/* These should be the same. */
- gcc_assert (df->n_blocks == df->n_blocks_inverted);
+ 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. */
if (dflow->problem->dir == DF_FORWARD)
df_analyze_problem (dflow,
df->blocks_to_analyze,
- df->postorder_inverted,
- df->n_blocks_inverted);
+ df->postorder_inverted.address (),
+ df->postorder_inverted.length ());
else
df_analyze_problem (dflow,
df->blocks_to_analyze,
df_analyze (void)
{
bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
- int i;
free (df->postorder);
- free (df->postorder_inverted);
df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
- df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
df->n_blocks = post_order_compute (df->postorder, true, true);
- df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
+ df->postorder_inverted.truncate (0);
+ inverted_post_order_compute (&df->postorder_inverted);
- for (i = 0; i < df->n_blocks; i++)
+ for (int i = 0; i < df->n_blocks; i++)
bitmap_set_bit (current_all_blocks, df->postorder[i]);
if (flag_checking)
{
/* Verify that POSTORDER_INVERTED only contains blocks reachable from
the ENTRY block. */
- for (i = 0; i < df->n_blocks_inverted; i++)
+ for (unsigned int i = 0; i < df->postorder_inverted.length (); i++)
gcc_assert (bitmap_bit_p (current_all_blocks,
df->postorder_inverted[i]));
}
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);
- df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
- df->n_blocks_inverted,
+ unsigned int newlen = df_prune_to_subcfg (df->postorder_inverted.address (),
+ df->postorder_inverted.length (),
df->blocks_to_analyze);
+ df->postorder_inverted.truncate (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, struct loop *loop)
+loop_post_order_compute (int *post_order, class loop *loop)
{
edge_iterator *stack;
int sp;
int post_order_num = 0;
- bitmap visited;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = BITMAP_ALLOC (NULL);
+ auto_bitmap visited;
/* Push the first edge on to the stack. */
stack[sp++] = ei_start (loop_preheader_edge (loop)->src->succs);
}
free (stack);
- BITMAP_FREE (visited);
return post_order_num;
}
/* 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 int
-loop_inverted_post_order_compute (int *post_order, struct loop *loop)
+static void
+loop_inverted_post_order_compute (vec<int> *post_order, class loop *loop)
{
basic_block bb;
edge_iterator *stack;
int sp;
- int post_order_num = 0;
- bitmap visited;
+
+ post_order->reserve_exact (loop->num_nodes);
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = BITMAP_ALLOC (NULL);
+ auto_bitmap visited;
/* Put all latches into the initial work list. In theory we'd want
to start from loop exits but then we'd have the special case of
time, check its predecessors. */
stack[sp++] = ei_start (pred->preds);
else
- post_order[post_order_num++] = pred->index;
+ post_order->quick_push (pred->index);
}
else
{
if (flow_bb_inside_loop_p (loop, bb)
&& ei_one_before_end_p (ei))
- post_order[post_order_num++] = bb->index;
+ post_order->quick_push (bb->index);
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
}
free (stack);
- BITMAP_FREE (visited);
- return post_order_num;
}
/* Analyze dataflow info for the basic blocks contained in LOOP. */
void
-df_analyze_loop (struct loop *loop)
+df_analyze_loop (class loop *loop)
{
free (df->postorder);
- free (df->postorder_inverted);
df->postorder = XNEWVEC (int, loop->num_nodes);
- df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
+ df->postorder_inverted.truncate (0);
df->n_blocks = loop_post_order_compute (df->postorder, loop);
- df->n_blocks_inverted
- = loop_inverted_post_order_compute (df->postorder_inverted, loop);
+ loop_inverted_post_order_compute (&df->postorder_inverted, loop);
gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
- gcc_assert ((unsigned) df->n_blocks_inverted == loop->num_nodes);
+ gcc_assert (df->postorder_inverted.length () == 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);
- return df->n_blocks_inverted;
+ gcc_assert (df->postorder_inverted.length ());
+ return df->postorder_inverted.length ();
}
gcc_assert (df->postorder);
if (dir == DF_FORWARD)
{
- gcc_assert (df->postorder_inverted);
- return df->postorder_inverted;
+ gcc_assert (df->postorder_inverted.length ());
+ return df->postorder_inverted.address ();
}
gcc_assert (df->postorder);
return df->postorder;
int i, p;
basic_block bb;
void *problem_temps;
- bitmap_head tmp;
- bitmap_initialize (&tmp, &df_bitmap_obstack);
+ auto_bitmap tmp (&df_bitmap_obstack);
for (p = 0; p < df->num_problems_defined; p++)
{
struct dataflow *dflow = df->problems_in_order[p];
dflow problem. */
if (dflow->out_of_date_transfer_functions)
{
- bitmap_copy (&tmp, dflow->out_of_date_transfer_functions);
+ bitmap_copy (tmp, dflow->out_of_date_transfer_functions);
bitmap_clear (dflow->out_of_date_transfer_functions);
- if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
+ if (bitmap_bit_p (tmp, ENTRY_BLOCK))
bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK);
- if (bitmap_bit_p (&tmp, EXIT_BLOCK))
+ if (bitmap_bit_p (tmp, EXIT_BLOCK))
bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK);
i = NUM_FIXED_BLOCKS;
FOR_EACH_BB_FN (bb, cfun)
{
- if (bitmap_bit_p (&tmp, bb->index))
+ if (bitmap_bit_p (tmp, bb->index))
bitmap_set_bit (dflow->out_of_date_transfer_functions, i);
i++;
}
if (df->blocks_to_analyze)
{
- if (bitmap_bit_p (&tmp, ENTRY_BLOCK))
+ if (bitmap_bit_p (tmp, ENTRY_BLOCK))
bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK);
- if (bitmap_bit_p (&tmp, EXIT_BLOCK))
+ if (bitmap_bit_p (tmp, EXIT_BLOCK))
bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK);
- bitmap_copy (&tmp, df->blocks_to_analyze);
+ bitmap_copy (tmp, df->blocks_to_analyze);
bitmap_clear (df->blocks_to_analyze);
i = NUM_FIXED_BLOCKS;
FOR_EACH_BB_FN (bb, cfun)
{
- if (bitmap_bit_p (&tmp, bb->index))
+ if (bitmap_bit_p (tmp, bb->index))
bitmap_set_bit (df->blocks_to_analyze, i);
i++;
}
}
- bitmap_clear (&tmp);
-
i = NUM_FIXED_BLOCKS;
FOR_EACH_BB_FN (bb, cfun)
{
if (df_live)
df_live_verify_transfer_functions ();
#endif
+ df->changeable_flags &= ~DF_VERIFY_SCHEDULED;
}
#ifdef DF_DEBUG_CFG
This is part of making a debugging dump. */
void
-df_print_regset (FILE *file, bitmap r)
+df_print_regset (FILE *file, const_bitmap r)
{
unsigned int i;
bitmap_iterator bi;
debugging dump. */
void
-df_print_word_regset (FILE *file, bitmap r)
+df_print_word_regset (FILE *file, const_bitmap r)
{
unsigned int max_reg = max_reg_num ();
projects / thirdparty / gcc.git / blobdiff