Analyze recursive PHI nodes in BasicAA

[tobiasvk]

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.

[sanjoy]

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

[tobiasvk]

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.

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

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

4. 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]

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

[tobiasvk]

Remove spurious extra directories that ended up in the patch.

[tobiasvk]

Hi Hal, Daniel,

[sanjoy]

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]

LGTM.

[tobiasvk_caf]

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.

[hfinkel]

In D10368#201839, @tobiasvk_caf wrote:

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]

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.

[hfinkel]

In D10368#202772, @tobiasvk wrote:

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]

In D10368#201839, @tobiasvk_caf wrote:

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]

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]

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.

lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 using namespace llvm;
 
+/// Enable analysis of recursive PHI nodes.
+static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi",
+                                          cl::Hidden, cl::init(false));
+
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
 // The max limit of the search depth in DecomposeGEPExpression() and
 // GetUnderlyingObject(), both functions need to use the same search
if (PN2->getParent() == PN->getParent()) {
       if (Alias != NoAlias)
         AliasCache[Locs] = OrigAliasResult;
 
       return Alias;
     }
 
   SmallPtrSet<Value*, 4> UniqueSrc;
   SmallVector<Value*, 4> V1Srcs;
+  bool isRecursive = false;
   for (Value *PV1 : PN->incoming_values()) {
     if (isa<PHINode>(PV1))
       // If any of the source itself is a PHI, return MayAlias conservatively
       // to avoid compile time explosion. The worst possible case is if both
       // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
       // and 'n' are the number of PHI sources.
       return MayAlias;
+
+    if (EnableRecPhiAnalysis)
+      if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
+        // Check whether the incoming value is a GEP that advances the pointer
+        // result of this PHI node (e.g. in a loop). If this is the case, we
+        // would recurse and always get a MayAlias. Handle this case specially
+        // below.
+        if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
+            isa<ConstantInt>(PV1GEP->idx_begin())) {
+          isRecursive = true;
+          continue;
+        }
+      }
+
     if (UniqueSrc.insert(PV1).second)
       V1Srcs.push_back(PV1);
   }
 
+  // If this PHI node is recursive, set the size of the accessed memory to
+  // unknown to represent all the possible values the GEP could advance the
+  // pointer to.
+  if (isRecursive)
+    PNSize = MemoryLocation::UnknownSize;
+
   AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo,
                                  V1Srcs[0], PNSize, PNAAInfo);
+
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == MayAlias)
     return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {

test/Analysis/BasicAA/phi-loop.ll

+; RUN: opt < %s -basicaa -basicaa-recphi=1 -gvn -S | FileCheck %s
+;
+; Check that section->word_ofs doesn't get reloaded in every iteration of the
+; for loop.
+;
+; Code:
+;
+; typedef struct {
+;   unsigned num_words;
+;   unsigned word_ofs;
+;   const unsigned *data;
+; } section_t;
+; 
+; 
+; void test2(const section_t * restrict section, unsigned * restrict dst) {;
+;   while (section->data != NULL) {
+;     const unsigned *src = section->data;
+;     for (unsigned i=0; i < section->num_words; ++i) {
+;       dst[section->word_ofs + i] = src[i];
+;     }   
+; 
+;     ++section;
+;   }
+; }
+; 
+
+; CHECK-LABEL: for.body:
+; CHECK-NOT: load i32, i32* %word_ofs
+
+%struct.section_t = type { i32, i32, i32* }
+
+define void @test2(%struct.section_t* noalias nocapture readonly %section, i32* noalias nocapture %dst) {
+entry:
+  %data13 = getelementptr inbounds %struct.section_t, %struct.section_t* %section, i32 0, i32 2
+  %0 = load i32*, i32** %data13, align 4
+  %cmp14 = icmp eq i32* %0, null
+  br i1 %cmp14, label %while.end, label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %entry, %for.end
+  %1 = phi i32* [ %6, %for.end ], [ %0, %entry ]
+  %section.addr.015 = phi %struct.section_t* [ %incdec.ptr, %for.end ], [ %section, %entry ]
+  %num_words = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 0, i32 0
+  %2 = load i32, i32* %num_words, align 4
+  %cmp211 = icmp eq i32 %2, 0
+  br i1 %cmp211, label %for.end, label %for.body.lr.ph
+
+for.body.lr.ph:                                   ; preds = %for.cond.preheader
+  %word_ofs = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 0, i32 1
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %arrayidx.phi = phi i32* [ %1, %for.body.lr.ph ], [ %arrayidx.inc, %for.body ]
+  %i.012 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %3 = load i32, i32* %arrayidx.phi, align 4
+  %4 = load i32, i32* %word_ofs, align 4
+  %add = add i32 %4, %i.012
+  %arrayidx3 = getelementptr inbounds i32, i32* %dst, i32 %add
+  store i32 %3, i32* %arrayidx3, align 4
+  %inc = add i32 %i.012, 1
+  %5 = load i32, i32* %num_words, align 4
+  %cmp2 = icmp ult i32 %inc, %5
+  %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1
+  br i1 %cmp2, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %for.cond.preheader
+  %incdec.ptr = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 1
+  %data = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 1, i32 2
+  %6 = load i32*, i32** %data, align 4
+  %cmp = icmp eq i32* %6, null
+  br i1 %cmp, label %while.end, label %for.cond.preheader
+
+while.end:                                        ; preds = %for.end, %entry
+  ret void
+}
+