Page MenuHomePhabricator

Analyze recursive PHI nodes in BasicAA
ClosedPublic

Authored by tobiasvk on Jun 10 2015, 3:27 PM.

Details

Summary

This patch allows phi nodes like

%x = phi [ %incptr, ... ] [ %var, ... ]
%incptr = getelementptr %x, 1

to be analyzed by BasicAliasAnalysis.

In aliasPHI, we can detect incoming values that are recursive GEPs with a
constant offset. Instead of trying to analyze a recursive GEP (and failing),
we now ignore it and instead set the size of the memory referenced by
the PHINode to UnknownSize. This represents all the possible memory
locations the pointer represented by the PHINode could be advanced to
by the GEP.

For now, this new behavior is turned off by default to allow debugging of
performance degradations seen with SPEC/x86 and Hexagon benchmarks.
The flag -basicaa-recphi turns it on.

Diff Detail

Event Timeline

tobiasvk updated this revision to Diff 27467.Jun 10 2015, 3:27 PM
tobiasvk retitled this revision from to Analyze recursive PHI nodes in BasicAA.
tobiasvk updated this object.
tobiasvk edited the test plan for this revision. (Show Details)
tobiasvk added a subscriber: Unknown Object (MLST).
sanjoy added a subscriber: sanjoy.Jun 10 2015, 3:50 PM

As far as I can tell, running opt -basicaa -scev-aa (without your change) gets this. Can you please check?

Hi Daniel, Hal,

I've evaluated the patch on the SPEC CPU2006 C/C++ benchmarks. Here are
the results.

  1. How many aliasPHI queries on recursive PHI nodes are there and what

are their results?

NoAlias 81317/10.6% (before) 118549/18.1% (after)
MayAlias 685637/89.4% (before) 534856/81.4% (after)
PartialAlias 0/ 0.0% (before) 3325/ 0.5% (after)
Total 766954 (before) 656730 (after)

As you can see, the share of NoAlias results for these queries goes up
noticeably. What's also interesting is that there is a 14.4% reduction
in total queries on recursive PHI nodes with the patch.

  1. What is the average number of incoming values on recursive PHI nodes?

There were 2 incoming values (one recursive, one 'real' value) in all
but 102 (0.013%) of aliasPHI queries on recursive PHI nodes before the
patch. With the patch, there were 103 queries with more than 2 incoming
values. So two incoming values is indeed the common case.

  1. What is the compile time impact of the change?

I ran the SPEC2006 build 5 times, discarding the numbers for the first
build to warm up the fs cache. Without the patch, the average build
time over the remaining four builds is 5023.913s. With the patch, it is
5023.713s. Pretty much unchanged.

  1. What is the impact of the change on the execution time of the

benchmarks?

This is with the ref data set, average of three runs.

(Speedup, higher is better)
400.perlbench 0.991404586
401.bzip2 0.999081718
403.gcc 1.006213196
429.mcf 0.990988836
445.gobmk 0.994521527
456.hmmer 0.996110677
458.sjeng 0.993703064
462.libquantum 1.014540594
464.h264ref 0.996489267
471.omnetpp 0.986799815
473.astar 0.987321483
483.xalancbmk 0.985122405
433.milc 1.023695308
444.namd 0.998587195
447.dealII 0.999585507
450.soplex 1.001369759
453.povray 0.978606911
470.lbm 1.018186381
482.sphinx3 0.998224144
Average 0.997923809

Not a huge change here although the numbers tend to be more on the side
of a slowdown. This is interesting - you'd think that better alias
analysis shouldn't have that effect. Any idea what could be causing
this? The numbers are from a real machine though so I'd expect
something like 1-2% noise, so it could be just that.

I hope this answers some of your questions!

Tobias

tobiasvk updated this revision to Diff 28372.Jun 24 2015, 11:15 AM

Add a flag to guard this change and leave it off by default for now.

tobiasvk updated this revision to Diff 28373.Jun 24 2015, 11:17 AM

Remove spurious extra directories that ended up in the patch.

Hi Hal, Daniel,

I'm a tad concerned about the use of undef in this change. If I
understand the change correctly, it looks like you're using undef as
"any arbitrary value that the compiler cannot reason about" when it
really is "any arbitrary value of the compiler's choice".

For instance, if you're trying to check if "PN = PHI(GEP(PN, 1), V)"
aliases with "GEP(V, 1)" (the correct result here is MayAlias) then
you'll return NoAlias if "V NoAlias GEP(V, 1)" && "V NoAlias GEP(V,
undef)". The first clause is true today, and depending on how
aggressive -basicaa becomes about exploiting undef, the second clause
may be taken to be true as well (today it is false). e.g. -basicaa
today will return NoAlias for (X, undef) for any X; and "X NoAlias
(GEP(V, undef))" is a very similar concept.

hfinkel accepted this revision.Jul 8 2015, 10:02 PM
hfinkel edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Jul 8 2015, 10:02 PM

Sanjoy, thanks for clarifying the semantics of undef. I can see how my code would break if aliasGEP ever started to exploit those semantics. I have been thinking of what else could be used to represent "any arbitrary value that the compiler cannot reason about"... I suppose we could create another temporary, like a load from undef? Pushing logic to special-case those temporary GEP values directly into aliasGEP may be another option but it seems a little intrusive to me.

Sanjoy, thanks for clarifying the semantics of undef. I can see how my code would break if aliasGEP ever started to exploit those semantics. I have been thinking of what else could be used to represent "any arbitrary value that the compiler cannot reason about"... I suppose we could create another temporary, like a load from undef? Pushing logic to special-case those temporary GEP values directly into aliasGEP may be another option but it seems a little intrusive to me.

Ah, and on this point, please make sure you add comments in the code about this, both where the undef is created, but also in aliasGEP.

tobiasvk updated this revision to Diff 29448.Jul 10 2015, 9:07 AM
tobiasvk edited edge metadata.

Change patch to use a load of undef, instead of just an undef, as the index for
the temporary GEP. This should make it safe even if aliasGEP ever gets smarter
about undefs.

Change patch to use a load of undef, instead of just an undef, as the index for
the temporary GEP. This should make it safe even if aliasGEP ever gets smarter
about undefs.

Should we add some kind of '@llvm.unknown_value' intrinsic for this purpose?

Sanjoy, thanks for clarifying the semantics of undef. I can see how my code would break if aliasGEP ever started to exploit those semantics. I have been thinking of what else could be used to represent "any arbitrary value that the compiler cannot reason about"... I suppose we could create another temporary, like a load from undef? Pushing logic to special-case those temporary GEP values directly into aliasGEP may be another option but it seems a little intrusive to me.

Sorry I did not respond to this earlier, for some reason I did not see the phabricator email.

I don't think load from undef is okay -- load from undef is undefined behavior, which is even worse than undef.

If I were you, I'd restructure BasicAliasAnalysis::aliasCheck to not take an llvm::Value but an llvm::Value + a constant offset, and the offset data type would have two extra values other than constant integers -- Unknown and Any (for your use case, you only need Unknown). Then you can ask do an alias check against gep(V, unknown) without creating a temporary instruction.

tobiasvk updated this revision to Diff 29720.Jul 14 2015, 3:10 PM

Update patch to no longer create temporary instructions

Sanjoy - actually I think we can achieve the same effect by passing
MemoryLocation::UnknownSize for the size in the aliasCheck queries that
aliasPHI makes for recursive PHI nodes. See patch.

sanjoy accepted this revision.Jul 15 2015, 11:59 AM
sanjoy added a reviewer: sanjoy.

I'm not a 100% comfortable signing off on changes to BasicAliasAnalysis, but given that this change looks good to Hal and you've fixed the undef issue I think this is okay to check in.

tobiasvk updated this object.Jul 15 2015, 12:30 PM
tobiasvk edited edge metadata.
tobiasvk set the repository for this revision to rL LLVM.
tobiasvk closed this revision.Jul 15 2015, 12:32 PM