On 01/05/2018 01:59 PM, Aldy Hernandez wrote:
> This fixes the code that verifies that none of the uninitialized paths
> reaching a PHI are actually taken (uninit_uses_cannot_happen).
>
> As discussed in the PR, this is done by fixing the predicate analysis in
> tree-ssa-uninit.c so that the set of predicates reaching the use of a
> PHI take into the entire path from the entry block. Previously we were
> starting at the immediate dominator of the PHI (for some obscure reason,
> or brain fart on my part).
>
> Fixing the predicate analysis to go all the way back to ENTRY, uncovers
> some latent limitations in compute_control_dep_chain(). I've fixed
> those as well.
>
> Note, I don't know why we were excluding basic blocks with a small (< 2)
> number of successors, but the exclusion was keeping us from looking at
> the ENTRY block. If this was by design, I can special case the ENTRY
> block. Similarly, convert_control_dep_chain_into_preds() was ignoring
> basic blocks with no instructions. This was making us skip the ENTRY
> block, which is just an empty forwarder block. Again, if this was by
> design, I can just special case the ENTRY block.
It's almost certainly the case they're ignored because a block with a
single successor never controls whether or not we execute some other
block in the CFG. A block with a single successor always transfers
control to that successor.
But the existence of a block with a single successor shouldn't stop
building the control dependence chain. We should just proceed into that
single successor and continue to build the control dependency chain.
>
> Finally, I've split up the dumping routine into member functions so we
> can get finer grained debugging help.
>
> Tested on x86-64 Linux.
>
> OK for trunk?
>
> curr.patch
>
>
> gcc/
>
> PR middle-end/81897
> * tree-ssa-uninit.c (compute_control_dep_chain): Do not bail on
> basic blocks with a small number of successors.
> (convert_control_dep_chain_into_preds): Special case the entry
> block.
> (dump_predicates): Split apart into...
> (dump_pred_chain): ...here...
> (dump_pred_info): ...and here.
> (can_one_predicate_be_invalidated_p): Add debugging printfs.
> (can_chain_union_be_invalidated_p): Return TRUE if any predicate
> was invalidated.
> (uninit_uses_cannot_happen): Avoid unnecessary if
> convert_control_dep_chain_into_preds yielded nothing.
So given that we regressed last time we poked around in here, I'm
looking this much deeper. For reference 78566 and 61409 were the bugs
we looked at last cycle.
> diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
> index 6930a243deb..58590a7763b 100644
> --- a/gcc/tree-ssa-uninit.c
> +++ b/gcc/tree-ssa-uninit.c
> @@ -543,9 +543,6 @@ compute_control_dep_chain (basic_block bb, basic_block
> dep_bb,
> bool found_cd_chain = false;
> size_t cur_chain_len = 0;
>
> - if (EDGE_COUNT (bb->succs) < 2)
> - return false;
So the worry here would be a block with no successors, but I think the
right thing will happen in this case.
> @@ -671,11 +668,9 @@ convert_control_dep_chain_into_preds (vec<edge>
> *dep_chains,
> e = one_cd_chain[j];
> guard_bb = e->src;
> gsi = gsi_last_bb (guard_bb);
> + /* Ignore empty BBs as they're basically forwarder blocks. */
> if (gsi_end_p (gsi))
> - {
> - has_valid_pred = false;
> - break;
> - }
> + continue;
> cond_stmt = gsi_stmt (gsi);
> if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
> /* Ignore EH edge. Can add assertion on the other edge's flag. */
ISTM that you want to use empty_block_p (bb) && single_succ_p (bb) to
detect the forwarder block. Otherwise ISTM that labels and debug
statements would affect the uninit analysis.
> @@ -2287,14 +2308,17 @@ can_chain_union_be_invalidated_p (pred_chain_union
> uninit_pred,
> {
> if (uninit_pred.is_empty ())
> return false;
> + if (dump_file && dump_flags & TDF_DETAILS)
> + dump_predicates (NULL, uninit_pred,
> + "Testing if anything here can be invalidated: ");
> for (size_t i = 0; i < uninit_pred.length (); ++i)
> {
> pred_chain c = uninit_pred[i];
> for (size_t j = 0; j < c.length (); ++j)
> - if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
> - return false;
> + if (can_one_predicate_be_invalidated_p (c[j], use_guard))
> + return true;
> }
> - return true;
> + return false;
> }
This seems close, but not quite right.
We want to prove (in the most general form) that for all paths from
ENTRY to the PHI which result in the PHI taking on an uninitialized
value that there is no viable path from the PHI to any use of the PHI
result.
We prune that search space by only allowing a single path from the PHI
to uses of the PHI. So we just have to prove that for all paths from
ENTRY to the PHI where the PHI takes on an uninitialized value the
single path from the PHI to the use is not viable.
USE_GUARD is the predicate chain for that one and only one path from the
PHI to the use of the PHI.
UNINIT_PRED is a vector of predicate chains for the uninitialized PHI
arguments. One predicate chain per uninitialized PHI argument (C in the
loop).
Thus we have to iterate over each predicate chain in UNINIT_PRED and
verify that it can be invalidated by USE_GUARD. If any predicate chain
in UNINIT_PRED can not be invalidated by USE_GUARD, then the chain union
can not be invalidated.
So we walk a given chain from UNINIT_PRED, C. If we are unable to
invalidate any predicates in C we must return false. If we are able to
invalidate a predicate in C, then we go to the next chain within
UNINIT_PRED and try to invalidate it. If we are successful in
invalidating all the chains in UNINIT_PRED, then and only then can we
return true.
So I think this ought to look like:
for (size_t i = 0; i < uninit_pred.length (); ++i)
{
pred_chain c = uninit_pred[i];
size_t j;
for (j = 0; j < c.length (); ++j)
if (can_one_predicate_be_invalidated_p (c[j], use_guard))
break;
/* If we were unable to invalidate any predicate in C, then there
is a viable path from entry to the PHI where the PHI takes
an uninitialized value and continues to a use of the PHI. */
if (j == c.length ())
return false;
}
/* We were able to invalidate each chain within UNINIT_PRED. */
return true;
Thoughts?
Jeff
