On Wed, Dec 13, 2017 at 10:30 PM, David Malcolm <dmalc...@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;
?
> }
>
> /* 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.
Ok with those changes.
Richard.
> 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);
> @@ -2331,10 +2344,11 @@ find_taken_edge_cond_expr (basic_block bb, tree val)
>
> /* 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. */
> + NULL if any edge may be taken.
> + If VAL is NULL_TREE, then the current value of the index is used. */
>
> static edge
> -find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
> +find_taken_edge_switch_expr (const gswitch *switch_stmt, basic_block bb,
> tree val)
> {
> basic_block dest_bb;
> @@ -2343,10 +2357,15 @@ 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);
> @@ -2360,7 +2379,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
>
