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

[Jeff Law <law@redhat.com>]

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

On 11/08/11 13:15, Paolo Bonzini wrote:
> On 11/08/2011 08:29 PM, Jeff Law wrote:
>>> Just to understand, what does this do with your optimization?
>>> 
>>> void f(void *p) { if (p) { puts("sell_soul_to_devil");
>>> puts("post_reload_rewrite"); }
>>> 
>>> *p = 2; }
>>> 
>>> ... f(NULL);
>>> 
>>> Does the program sell its soul to the devil before crashing?
>> 
>> If "f" is not inlined into its caller, then there's nothing for
>> the new pass to do.  There's no explicit NULL dereference and
>> there's no assignments to "p", so there's no PHI at the merge
>> point for P.
> 
> But is that just a limitation of the representation?  With
> assertions as in VRP you'd have
> 
> if (p_1) goto BB1 else goto BB2 BB1: ... goto BB3; BB2: p_2 =
> assert(p_1, p_1 == 0); goto BB3;
> 
> p_3 = phi (p_1<BB1>, p_2<BB2>); *p_3 = 2;
> 
> What would happen then?
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.

We would remove the edge bb0->bb2 and the control statement if (p_1)
....  That makes BB2 unreachable resulting in

BB0 goto BB1
BB1 ...
BB3 p_2 = phi (p_1)
    *p_2 = 2;

Which would then be optimized into

BB0: ...
     *p_1 = 2;

Which is exactly what I would expect the code to do with the knowledge
that passing 0 to f results in undefined behaviour.


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

iQEcBAEBAgAGBQJOuZAGAAoJEBRtltQi2kC7gkwIAJLBfsgICHOWKVBFTAv1U1Xx
8+gR3o70JJmoZY7wOv51ReUOU3Nxzj36f/HzY0SHgNBDu4gxo94HzFkUp1x5u1uw
NUwv802p3JKpIroi8Tonu42mEhIzWGTOIUCLdrxqc3fdPtEMQrC5ExjeKdt//x61
+/JVzz4pNO2ZeYLfATa8fZDLtz0vBhmXD+Ue+p71i0sqw0TfNs+DYvuneW7Bk0uy
TfNpaVRZp+xJgYukrNqZqXw7+O4OuqU5Y1X42CCoz8m6+Zxado1sOB6jeEQjyyqH
+Liewv0jas67velgycrNRG4O0ppoOUF8vVY26ofeWtV16otc9/Yuz6+iqGJOJgo=
=8mxV
-----END PGP SIGNATURE-----