Re: RFA: New pass to delete unexecutable paths in the CFG

[Jeff Law <law at redhat dot com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/09/11 01:09, Paolo Bonzini wrote:
> On 11/08/2011 09:24 PM, Jeff Law wrote:
>> We don't have access to those assertions as they're removed well
>> prior to this pass running.  However, if we did, or if we had
>> redundant PHIs in the stream which were propagated we'd be
>> presented with something like
>> 
>> BB0  if (p_1) goto BB1 else goto BB2
>> 
>> BB1: ... goto BB3 BB2: BB3: p_2 = phi (p_1 (BB1), 0(BB2)) *p_2 =
>> 2;
>> 
>> 
>> We'd recognize that the edge bb2->bb3 is unexecutable as doing
>> so leads to a NULL pointer dereference.  Since the edge bb2->bb3
>> is not a critical edge, we know that bb2 as a whole is
>> unexecutable.  bb2 is control dependent on the edge bb0->bb2.
> 
> (Side note regarding critical edges: have you tried splitting them 
> before your pass?)
No.  The pass really came about at the last minute when I realized I
could take the warning work (which was not ready), twiddle it slightly
and get an optimization.

Critical edges don't really inhibit this optimizer.  They allow us to
trivially distinguish between the case where the whole block is
unexecutable vs just one of its outgoing edges being unexecutable.

If we were to split the critical edge, we would ultimately get the
same results in the end.

> 
> Ok, so that's exactly what I was thinking about.  In this case the 
> optimization is obviously allowed by the C standard; you have
> 
> if (p) something; *p = 0;
> 
> and the "*p = 0" has been in some sense translated to
> 
> if (!p) something; *p = 0;
> 
> which is only different on undefined paths.  But I'm not sure that
> more complicated cases, where there are other instructions between
> the "if" and "*p = 0", would also be allowed by the C standard.
> For example, I think a function call in the "else" branch, or
> between the PHI and the dereference should prevent the
> optimization, because the function call might never return for what
> we know.  Probably a volatile asm too.  Does your patch do that?
> (Testcases! :)).
My patch totally ignores the other code on the unexecutable path.  So
we can miss externally visible side effects, if we were to somehow get
on the unexecutable path.  But that's the whole point, in a conforming
program we can't ever get on the unexecutable path.



> In general, this is quite different from all other existing GCC 
> optimizations based on undefined behavior.  Whenever you trigger 
> undefined behavior, right now the effects do not extend *before*
> the undefined operation.  The proposed pass would change that, so
> that its effects are a bit more surprising when debugging.  If your
> bug is that you forgot a "return;" in the else branch, you surely
> wouldn't expect the compiler to swallow the entire branch.
> Unfortunately debugging at -O0 is not always an option.
Most certainly, it's controversial.  I'm still debating with myself
over whether or not this is a wise direction to take.

As I've mentioned elsewhere, this is something that fell into my lap
as I was working on a closely related warning.  The warning is, to me
at least, ultimately far more interesting than the optimization.
Triggering the warning tells us to look at the code for a few things.

  1. Truly incorrect code which leads to a NULL pointer dereference.
  2. Correct, but inefficient source, like we've seen for VEC_BASE.
  3. Missed optimizations, again like we've seen for VEC_BASE

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOur4eAAoJEBRtltQi2kC7t+MH/R2asrStW6dOOEOxuQWmKLIR
uYGkknGsv36KJOD+rnzulv3iNZW2ubYvYNBCkJAJn6/PjRDvV9T9/82ZHY9m2+Cb
SvWFOnP/gU8yEzksiS5fRB6rRzYOXUMX1/nXqmMDAfprRg9vYOBo34zQU93KonMT
k2GBtXSD5vFXX3VL6ffGSnQk9i59A0eSPMs+0q6n3pGztd9AjvgPkJAMDP3qep9m
jgCM0x+5gQwGzGCIVF65JqowAoqOaT3ZIGRajTvOZSa7N5gc+fvI3Czizb6lFr6R
Xls4Q/G3M2T5uXENvAN6SiN0Sv24WTEWxIoyKS0X1KTSC78gyG2QVAMFaYwRj6A=
=DOjd
-----END PGP SIGNATURE-----