[committed] v3: vrp_prop: Use dom_walker for -Warray-bounds (PR tree-optimization/83312)
David Malcolm
dmalcolm@redhat.com
Thu Dec 14 17:24:00 GMT 2017
On Thu, 2017-12-14 at 11:53 +0100, Richard Biener wrote:
> On Wed, Dec 13, 2017 at 10:30 PM, David Malcolm <dmalcolm@redhat.com>
> wrote:
> > On Wed, 2017-12-13 at 10:47 -0700, Jeff Law wrote:
> > > On 12/13/2017 09:24 AM, Richard Biener wrote:
> > > > >
> > > > > Alternately we could to the dom_walker ctor that an initial
> > > > > state
> > > > > of
> > > > > EDGE_EXECUTABLE is already set.
> > > >
> > > > I'm quite sure that wouldn't help for VRP.
> > >
> > > Not sure why. But it's not worth digging deep into.
> > >
> > > I do think the current structure could still fail to pick up some
> > > secondary cases where blocks become unreachable as a result of
> > > both
> > > not
> > > needing to visit during the lattice propagation step and the
> > > substitution step. But I'd expect this to be rare.
> > >
> > > > I think David's approach is fine just we don't need any other
> > > > API
> > > > to get at a known executable outgoing edge. We can improve the
> > > > existing one or just add the trivial folding required.
> > >
> > > I think Michael's suggestion to pass in NULL for the value and
> > > allow
> > > find_edge to try and determine the value makes the most sense
> > > here.
> > >
> > > Jeff
> >
> > Michael: thanks for the hint about find_taken_edge; I assumed that
> > such
> > a "find the relevant out-edge" function would already exist; but I
> > didn't find it (I'm relatively unfamiliar with this part of the
> > code).
> >
> > Here's an updated version of the patch, which eliminates the stuff
> > I
> > added to gimple.h/gimple.c changes in favor of using
> > find_taken_edge (bb, NULL_TREE),
> > generalizing it to work with arbitrary bbs, so that the dom_walker
> > vfunc can simply use:
> > return find_taken_edge (bb, NULL_TREE);
> > without having to check e.g. for there being a last stmt (ENTRY
> > and EXIT), or having to check that it is indeed a control statement
> > (is there a requirement at this point of the IR that we don't just
> > fall off the last statment through an out-edge?)
> >
> > I handled var == NULL_TREE for GIMPLE_COND and GIMPLE_SWITCH,
> > but not for computed goto (find_taken_edge already handles that by
> > bailing out).
> >
> > I also made some things "const" whilst I was touching it.
> >
> > Successfully bootstrapped®rtested on x86_64-pc-linux-gnu.
> >
> > OK for trunk?
> >
> > gcc/ChangeLog:
> > PR tree-optimization/83312
> > * domwalk.h (dom_walker::dom_walker): Fix typo in comment.
> > * tree-cfg.c (find_taken_edge): Update to handle NULL_TREE
> > for
> > "val" param, and to cope with arbitrary basic blocks.
> > (find_taken_edge_cond_expr): Add "cond_stmt" param and use
> > it to
> > handle NULL_TREE for "val".
> > (find_taken_edge_switch_expr): Make "switch_stmt" param
> > const.
> > Handle NULL_TREE for "val".
> > (find_case_label_for_value): Make "switch_stmt" param
> > const.
> > * tree-vrp.c (class check_array_bounds_dom_walker): New
> > subclass
> > of dom_walker.
> > (vrp_prop::check_all_array_refs): Reimplement as...
> > (check_array_bounds_dom_walker::before_dom_children):
> > ...this new
> > vfunc. Replace linear search through BB block list,
> > excluding
> > those with non-executable in-edges via dominator walk.
> >
> > gcc/testsuite/ChangeLog:
> > PR tree-optimization/83312
> > * gcc.dg/pr83312.c: New test case.
> > ---
> > gcc/domwalk.h | 2 +-
> > gcc/testsuite/gcc.dg/pr83312.c | 30 +++++++++++++++++
> > gcc/tree-cfg.c | 59 +++++++++++++++++++++---------
> > --
> > gcc/tree-vrp.c | 76 ++++++++++++++++++++++++++--
> > --------------
> > 4 files changed, 117 insertions(+), 50 deletions(-)
> > create mode 100644 gcc/testsuite/gcc.dg/pr83312.c
> >
> > diff --git a/gcc/domwalk.h b/gcc/domwalk.h
> > index 6ac93eb..c7e3450 100644
> > --- a/gcc/domwalk.h
> > +++ b/gcc/domwalk.h
> > @@ -32,7 +32,7 @@ class dom_walker
> > public:
> > static const edge STOP;
> >
> > - /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can
> > discover
> > + /* Use SKIP_UNREACHABLE_BLOCKS = true when your client can
> > discover
> > that some edges are not executable.
> >
> > If a client can discover that a COND, SWITCH or GOTO has a
> > static
> > diff --git a/gcc/testsuite/gcc.dg/pr83312.c
> > b/gcc/testsuite/gcc.dg/pr83312.c
> > new file mode 100644
> > index 0000000..2eb241d
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/pr83312.c
> > @@ -0,0 +1,30 @@
> > +/* { dg-options "-O2 -Warray-bounds" } */
> > +
> > +struct ptlrpcd_ctl {
> > + char pc_name[20];
> > +};
> > +struct ptlrpcd {
> > + struct ptlrpcd_ctl pd_threads[6];
> > +};
> > +struct ptlrpcd *ptlrpcd_init_pd;
> > +static void ptlrpcd_ctl_init(struct ptlrpcd_ctl *pc, int index) {
> > + if (index < 0)
> > + __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name),
> > "ptlrpcd_rcv");
> > + else
> > + __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name),
> > "ptlrpcd_%d", index);
> > +}
> > +int ptlrpcd_init_ncpts;
> > +static int ptlrpcd_init(int nthreads) {
> > + int j;
> > + if (ptlrpcd_init_ncpts) {
> > + ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[0], -1);
> > + for (j = 1; j < nthreads; j++)
> > + ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[j], j);
> > + }
> > + return 0;
> > +}
> > +int ptlrpcd_init_groupsize;
> > +void ptlrpcd_addref(void) {
> > + ptlrpcd_init(ptlrpcd_init_groupsize);
> > +}
> > +
> > diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
> > index 4d09b2c..7ecc5c8 100644
> > --- a/gcc/tree-cfg.c
> > +++ b/gcc/tree-cfg.c
> > @@ -170,9 +170,9 @@ static void gimple_merge_blocks (basic_block,
> > basic_block);
> > static bool gimple_can_merge_blocks_p (basic_block, basic_block);
> > static void remove_bb (basic_block);
> > static edge find_taken_edge_computed_goto (basic_block, tree);
> > -static edge find_taken_edge_cond_expr (basic_block, tree);
> > -static edge find_taken_edge_switch_expr (gswitch *, basic_block,
> > tree);
> > -static tree find_case_label_for_value (gswitch *, tree);
> > +static edge find_taken_edge_cond_expr (const gcond *, basic_block,
> > tree);
> > +static edge find_taken_edge_switch_expr (const gswitch *,
> > basic_block, tree);
> > +static tree find_case_label_for_value (const gswitch *, tree);
> > static void lower_phi_internal_fn ();
> >
> > void
> > @@ -2254,9 +2254,10 @@ remove_bb (basic_block bb)
> > }
> >
> >
> > -/* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR,
> > and a
> > - predicate VAL, return the edge that will be taken out of the
> > block.
> > - If VAL does not match a unique edge, NULL is returned. */
> > +/* Given a basic block BB and a predicate VAL for use in the final
> > statement
> > + of the block, return the edge that will be taken out of the
> > block.
> > + If VAL does not match a unique edge, NULL is returned.
> > + If VAL is NULL_TREE, then the current value of the predicate is
> > used. */
> >
> > edge
> > find_taken_edge (basic_block bb, tree val)
> > @@ -2265,10 +2266,12 @@ find_taken_edge (basic_block bb, tree val)
> >
> > stmt = last_stmt (bb);
> >
> > - gcc_assert (is_ctrl_stmt (stmt));
> > + /* Handle ENTRY and EXIT. */
> > + if (!stmt)
> > + return NULL;
> >
> > if (gimple_code (stmt) == GIMPLE_COND)
> > - return find_taken_edge_cond_expr (bb, val);
> > + return find_taken_edge_cond_expr (as_a <gcond *> (stmt), bb,
> > val);
> >
> > if (gimple_code (stmt) == GIMPLE_SWITCH)
> > return find_taken_edge_switch_expr (as_a <gswitch *> (stmt),
> > bb, val);
> > @@ -2285,10 +2288,10 @@ find_taken_edge (basic_block bb, tree val)
> > && (TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) ==
> > LABEL_EXPR)
> > && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
> > return find_taken_edge_computed_goto (bb, TREE_OPERAND
> > (val, 0));
> > - return NULL;
> > }
> >
> > - gcc_unreachable ();
> > + /* Unable to find a unique edge. */
> > + return NULL;
>
> Not sure if important but if you want to handle arbitrary BBs then
> surely
> a single successor edge (a fallthru) would qualify? I think your
> updated
> comment doesn't reflect that passing a BB without a "predicate" is a
> valid input.
> So...
>
> return single_succ_p (bb) ? single_succ_edge (bb) : NULL;
>
> ?
This isn't needed for the "dom_walker with skip_unreachable_blocks"
case in the patch, since dom_walker::walk merely uses this result to
clear the EDGE_EXECUTABLE flag from the other edges, and there won't
be any.
That said, if find_taken_edge is to support arbitrary BBs it seems
like the thing to do, and the test is cheap, so I added it.
> > }
> >
> > /* Given a constant value VAL and the entry block BB to a
> > GOTO_EXPR
> > @@ -2313,15 +2316,25 @@ find_taken_edge_computed_goto (basic_block
> > bb, tree val)
> >
> > /* Given a constant value VAL and the entry block BB to a
> > COND_EXPR
> > statement, determine which of the two edges will be taken out
> > of the
> > - block. Return NULL if either edge may be taken. */
> > + block. Return NULL if either edge may be taken.
> > + If VAL is NULL_TREE, then the current value of the predicate is
> > used. */
> >
> > static edge
> > -find_taken_edge_cond_expr (basic_block bb, tree val)
> > +find_taken_edge_cond_expr (const gcond *cond_stmt, basic_block bb,
> > tree val)
> > {
>
> here and below the BB argument is somewhat redundant given the stmt
> has a reference to it via gimple_bb (). Let's remove it.
Done.
> Ok with those changes.
>
> Richard.
[...]
For reference, here's what I committed to trunk (as r255649, after
successfully bootstrap®rtest on x86_64-pc-linux-gnu).
gcc/ChangeLog:
PR tree-optimization/83312
* domwalk.h (dom_walker::dom_walker): Fix typo in comment.
* tree-cfg.c (find_taken_edge): Update to handle NULL_TREE for
"val" param, and to cope with arbitrary basic blocks.
(find_taken_edge_cond_expr): Add "cond_stmt" param and use it to
handle NULL_TREE for "val", dropping "bb" param.
(find_taken_edge_switch_expr): Make "switch_stmt" param const and
drop "bb" param. Handle NULL_TREE for "val".
(find_case_label_for_value): Make "switch_stmt" param const.
* tree-vrp.c (class check_array_bounds_dom_walker): New subclass
of dom_walker.
(vrp_prop::check_all_array_refs): Reimplement as...
(check_array_bounds_dom_walker::before_dom_children): ...this new
vfunc. Replace linear search through BB block list, excluding
those with non-executable in-edges via dominator walk.
gcc/testsuite/ChangeLog:
PR tree-optimization/83312
* gcc.dg/pr83312.c: New test case.
---
gcc/domwalk.h | 2 +-
gcc/testsuite/gcc.dg/pr83312.c | 30 ++++++++++++++++
gcc/tree-cfg.c | 79 +++++++++++++++++++++++++++---------------
gcc/tree-vrp.c | 76 ++++++++++++++++++++++++----------------
4 files changed, 129 insertions(+), 58 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr83312.c
diff --git a/gcc/domwalk.h b/gcc/domwalk.h
index 6ac93eb..c7e3450 100644
--- a/gcc/domwalk.h
+++ b/gcc/domwalk.h
@@ -32,7 +32,7 @@ class dom_walker
public:
static const edge STOP;
- /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover
+ /* Use SKIP_UNREACHABLE_BLOCKS = true when your client can discover
that some edges are not executable.
If a client can discover that a COND, SWITCH or GOTO has a static
diff --git a/gcc/testsuite/gcc.dg/pr83312.c b/gcc/testsuite/gcc.dg/pr83312.c
new file mode 100644
index 0000000..2eb241d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr83312.c
@@ -0,0 +1,30 @@
+/* { dg-options "-O2 -Warray-bounds" } */
+
+struct ptlrpcd_ctl {
+ char pc_name[20];
+};
+struct ptlrpcd {
+ struct ptlrpcd_ctl pd_threads[6];
+};
+struct ptlrpcd *ptlrpcd_init_pd;
+static void ptlrpcd_ctl_init(struct ptlrpcd_ctl *pc, int index) {
+ if (index < 0)
+ __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name), "ptlrpcd_rcv");
+ else
+ __builtin_snprintf(pc->pc_name, sizeof(pc->pc_name), "ptlrpcd_%d", index);
+}
+int ptlrpcd_init_ncpts;
+static int ptlrpcd_init(int nthreads) {
+ int j;
+ if (ptlrpcd_init_ncpts) {
+ ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[0], -1);
+ for (j = 1; j < nthreads; j++)
+ ptlrpcd_ctl_init(&ptlrpcd_init_pd->pd_threads[j], j);
+ }
+ return 0;
+}
+int ptlrpcd_init_groupsize;
+void ptlrpcd_addref(void) {
+ ptlrpcd_init(ptlrpcd_init_groupsize);
+}
+
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 4d09b2c..c1a73d1 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -170,9 +170,9 @@ static void gimple_merge_blocks (basic_block, basic_block);
static bool gimple_can_merge_blocks_p (basic_block, basic_block);
static void remove_bb (basic_block);
static edge find_taken_edge_computed_goto (basic_block, tree);
-static edge find_taken_edge_cond_expr (basic_block, tree);
-static edge find_taken_edge_switch_expr (gswitch *, basic_block, tree);
-static tree find_case_label_for_value (gswitch *, tree);
+static edge find_taken_edge_cond_expr (const gcond *, tree);
+static edge find_taken_edge_switch_expr (const gswitch *, tree);
+static tree find_case_label_for_value (const gswitch *, tree);
static void lower_phi_internal_fn ();
void
@@ -2254,9 +2254,12 @@ remove_bb (basic_block bb)
}
-/* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
- predicate VAL, return the edge that will be taken out of the block.
- If VAL does not match a unique edge, NULL is returned. */
+/* Given a basic block BB and a value VAL for use in the final statement
+ of the block (if a GIMPLE_COND, GIMPLE_SWITCH, or computed goto), return
+ the edge that will be taken out of the block.
+ If VAL is NULL_TREE, then the current value of the final statement's
+ predicate or index is used.
+ If the value does not match a unique edge, NULL is returned. */
edge
find_taken_edge (basic_block bb, tree val)
@@ -2265,13 +2268,15 @@ find_taken_edge (basic_block bb, tree val)
stmt = last_stmt (bb);
- gcc_assert (is_ctrl_stmt (stmt));
+ /* Handle ENTRY and EXIT. */
+ if (!stmt)
+ return NULL;
if (gimple_code (stmt) == GIMPLE_COND)
- return find_taken_edge_cond_expr (bb, val);
+ return find_taken_edge_cond_expr (as_a <gcond *> (stmt), val);
if (gimple_code (stmt) == GIMPLE_SWITCH)
- return find_taken_edge_switch_expr (as_a <gswitch *> (stmt), bb, val);
+ return find_taken_edge_switch_expr (as_a <gswitch *> (stmt), val);
if (computed_goto_p (stmt))
{
@@ -2285,10 +2290,10 @@ find_taken_edge (basic_block bb, tree val)
&& (TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
&& TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
- return NULL;
}
- gcc_unreachable ();
+ /* Otherwise we only know the taken successor edge if it's unique. */
+ return single_succ_p (bb) ? single_succ_edge (bb) : NULL;
}
/* Given a constant value VAL and the entry block BB to a GOTO_EXPR
@@ -2311,31 +2316,44 @@ find_taken_edge_computed_goto (basic_block bb, tree val)
return e;
}
-/* Given a constant value VAL and the entry block BB to a COND_EXPR
- statement, determine which of the two edges will be taken out of the
- block. Return NULL if either edge may be taken. */
+/* Given COND_STMT and a constant value VAL for use as the predicate,
+ determine which of the two edges will be taken out of
+ the statement's block. Return NULL if either edge may be taken.
+ If VAL is NULL_TREE, then the current value of COND_STMT's predicate
+ is used. */
static edge
-find_taken_edge_cond_expr (basic_block bb, tree val)
+find_taken_edge_cond_expr (const gcond *cond_stmt, tree val)
{
edge true_edge, false_edge;
- if (val == NULL
- || TREE_CODE (val) != INTEGER_CST)
+ if (val == NULL_TREE)
+ {
+ /* Use the current value of the predicate. */
+ if (gimple_cond_true_p (cond_stmt))
+ val = integer_one_node;
+ else if (gimple_cond_false_p (cond_stmt))
+ val = integer_zero_node;
+ else
+ return NULL;
+ }
+ else if (TREE_CODE (val) != INTEGER_CST)
return NULL;
- extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+ extract_true_false_edges_from_block (gimple_bb (cond_stmt),
+ &true_edge, &false_edge);
return (integer_zerop (val) ? false_edge : true_edge);
}
-/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
- statement, determine which edge will be taken out of the block. Return
- NULL if any edge may be taken. */
+/* Given SWITCH_STMT and an INTEGER_CST VAL for use as the index, determine
+ which edge will be taken out of the statement's block. Return NULL if any
+ edge may be taken.
+ If VAL is NULL_TREE, then the current value of SWITCH_STMT's index
+ is used. */
static edge
-find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
- tree val)
+find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val)
{
basic_block dest_bb;
edge e;
@@ -2343,13 +2361,18 @@ find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
if (gimple_switch_num_labels (switch_stmt) == 1)
taken_case = gimple_switch_default_label (switch_stmt);
- else if (! val || TREE_CODE (val) != INTEGER_CST)
- return NULL;
else
- taken_case = find_case_label_for_value (switch_stmt, val);
+ {
+ if (val == NULL_TREE)
+ val = gimple_switch_index (switch_stmt);
+ if (TREE_CODE (val) != INTEGER_CST)
+ return NULL;
+ else
+ taken_case = find_case_label_for_value (switch_stmt, val);
+ }
dest_bb = label_to_block (CASE_LABEL (taken_case));
- e = find_edge (bb, dest_bb);
+ e = find_edge (gimple_bb (switch_stmt), dest_bb);
gcc_assert (e);
return e;
}
@@ -2360,7 +2383,7 @@ find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
sorted: We can do a binary search for a case matching VAL. */
static tree
-find_case_label_for_value (gswitch *switch_stmt, tree val)
+find_case_label_for_value (const gswitch *switch_stmt, tree val)
{
size_t low, high, n = gimple_switch_num_labels (switch_stmt);
tree default_case = gimple_switch_default_label (switch_stmt);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index a86b382..fe778b0 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5000,44 +5000,62 @@ check_array_bounds (tree *tp, int *walk_subtree, void *data)
return NULL_TREE;
}
-/* Walk over all statements of all reachable BBs and call check_array_bounds
- on them. */
+/* A dom_walker subclass for use by vrp_prop::check_all_array_refs,
+ to walk over all statements of all reachable BBs and call
+ check_array_bounds on them. */
-void
-vrp_prop::check_all_array_refs ()
+class check_array_bounds_dom_walker : public dom_walker
{
- basic_block bb;
- gimple_stmt_iterator si;
+ public:
+ check_array_bounds_dom_walker (vrp_prop *prop)
+ : dom_walker (CDI_DOMINATORS, true), m_prop (prop) {}
+ ~check_array_bounds_dom_walker () {}
- FOR_EACH_BB_FN (bb, cfun)
- {
- edge_iterator ei;
- edge e;
- bool executable = false;
+ edge before_dom_children (basic_block) FINAL OVERRIDE;
- /* Skip blocks that were found to be unreachable. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- executable |= !!(e->flags & EDGE_EXECUTABLE);
- if (!executable)
- continue;
+ private:
+ vrp_prop *m_prop;
+};
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- {
- gimple *stmt = gsi_stmt (si);
- struct walk_stmt_info wi;
- if (!gimple_has_location (stmt)
- || is_gimple_debug (stmt))
- continue;
+/* Implementation of dom_walker::before_dom_children.
- memset (&wi, 0, sizeof (wi));
+ Walk over all statements of BB and call check_array_bounds on them,
+ and determine if there's a unique successor edge. */
- wi.info = this;
+edge
+check_array_bounds_dom_walker::before_dom_children (basic_block bb)
+{
+ gimple_stmt_iterator si;
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ gimple *stmt = gsi_stmt (si);
+ struct walk_stmt_info wi;
+ if (!gimple_has_location (stmt)
+ || is_gimple_debug (stmt))
+ continue;
- walk_gimple_op (gsi_stmt (si),
- check_array_bounds,
- &wi);
- }
+ memset (&wi, 0, sizeof (wi));
+
+ wi.info = m_prop;
+
+ walk_gimple_op (stmt, check_array_bounds, &wi);
}
+
+ /* Determine if there's a unique successor edge, and if so, return
+ that back to dom_walker, ensuring that we don't visit blocks that
+ became unreachable during the VRP propagation
+ (PR tree-optimization/83312). */
+ return find_taken_edge (bb, NULL_TREE);
+}
+
+/* Walk over all statements of all reachable BBs and call check_array_bounds
+ on them. */
+
+void
+vrp_prop::check_all_array_refs ()
+{
+ check_array_bounds_dom_walker w (this);
+ w.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
}
/* Return true if all imm uses of VAR are either in STMT, or
--
1.8.5.3
More information about the Gcc-patches
mailing list