Improve jump threading #1 of N

[Jeff Law <law at redhat dot com>]

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

I've been doing some research into improving certain aspects of our
warnings, particularly removing false positives from the warnings which
require dataflow information.  I think it's reasonably well known that
many of the false positives occur due to unexecutable edges remaining in
the CFG.

Long term I think we're going to need a more structured approach to path
isolation and I'm still pondering exactly what that might look like.

In the mean time one thing is clear the current jump threading is quite
important for eliminating many of the unexecutable edges in the CFG.
Furthermore, the cases I'm looking at require us capture more of the
secondary effects of jump threading.

Let's consider this CFG (from a routine in cfgexpand.c)


           A
          / \
         B   C
         |  / \
         | D   E
         | |  / \
         | | F   G
          \| |
            \|
             H
            / \
           I   J
          / \
         L   M
         |  / \
         | N   O
         | |  / \
         | | P   Q
          \| |
            \|
             R


As it turns out some blocks have the same condition (A,I), (C,M), (E,O).
 But because of the merge block H, no threading is possible.  I've got
patches which let us copy H into B, D & F.  That exposes the jump
threads B->L, D->M and F->M.  Unfortunately, we need another iteration
of jump threading to then thread D->N and F->O and then another
iteration to thread F->P with the net result looking something like this:


           A
          / \
        BH'L C
         |  / \
         |DH'N E
         | |  / \
         | |FH'P G
          \| |
            \|
             R



I don't think anyone is going to argue for a return to the iterated DOM
approach we had in the past.  Luckily we can often pick up the secondary
effects by looking deeper into the CFG when we do find a threading
opportunity.  ie, when we discover D->I->M, go ahead and look at M and
see if we can thread through it to N or O and so-on.

That turns out to be relatively easy and cheap if we restrict the form
of M so that we don't need to create a duplicate of M (which ties back
to our long term need for a more structured approach to path isolation).

The attached patch allows us to capture some of these secondary effects
by looking at the destination of a threadable jump to see if it is yet
another conditional with a statically computable destination.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  Trivial
testcase included :-)  OK for trunk?


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

iQEcBAEBAgAGBQJNjMM7AAoJEBRtltQi2kC7mtAH/2yC58nNaW1ZZP6OQFztNTHo
nyRAIjS7NxT8Sal84cRwfaAgND74VesVUs8EgYY9G7brHWihBWYqZ8gRjRp2VJqA
EM9IIScKgYqM5/2+41Iy2yGY3yMksOpVPX3LZfCHWKW0PIycpmHnLglGUSU33rbr
8EtVbv3PuXn6OnqYqA5onCmLiI4YRapLnF+iNvH3r5DI4EJKPweLPBygye/aDI+F
DCZl9zCKfdrKvvkA81o1+f2CQPC9507w2B1MZBM3uXRJGETrLTNKiyIDyciq2OG+
SR2e72co/zbUTU1HQlpkL5nCEl4xn8fYmZQlaZjp3OypkY86vI5YnStjPKjnc2w=
=z6nn
-----END PGP SIGNATURE-----

Attachment: patch
Description: Text document