This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Improve jump threading #1 of N


On Fri, Mar 25, 2011 at 5:30 PM, Jeff Law <law@redhat.com> wrote:
> -----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?

Looks good to me apart from not using gsi_start_nondebug_bb in
thread_around_empty_block.

Thanks,
Richard.

>
> -----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-----
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]