Page MenuHomePhabricator

[BasicAA] Make alias GEP positive offset handling symmetric
ClosedPublic

Authored by nikic on Thu, Nov 12, 12:59 PM.

Details

Summary

aliasGEP() currently implements some special handling for the case where all variable offsets are positive, in which case the constant offset can be taken as the minimal offset. However, it does not perform the same handling for the all-negative case. This means that the alias-analysis result between two GEPs is asymmetric: If GEP1 - GEP2 is all-positive, then GEP2 - GEP1 is all-negative, and the first will result in NoAlias, while the second will result in MayAlias.

Apart from producing sub-optimal results for one order, this also violates our caching assumption. In particular, if BatchAA is used, the cached result depends on the order of the GEPs in the first query. This results in an inconsistency in BatchAA and AA results, which is how I noticed this issue.

Diff Detail

Event Timeline

nikic created this revision.Thu, Nov 12, 12:59 PM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Nov 12, 12:59 PM
nikic requested review of this revision.Thu, Nov 12, 12:59 PM
nikic added inline comments.Thu, Nov 12, 1:01 PM
llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
177

This assertion currently fails on Analysis/BasicAA/zext.ll.

Arguably this should be asserted in AA itself, but a) I'm not confident enough that this is the only asymmetry that exists right now and b) a more general assertion would have to be behind EXPENSIVE_CHECKS, so I figured this would be a good place to verify this initially.

jdoerfert added inline comments.Thu, Nov 12, 1:13 PM
llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
177

Can you add the reasoning as a TODO maybe?

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

Copy paste error?

nikic updated this revision to Diff 304953.Thu, Nov 12, 1:22 PM

Add TODO.

nikic marked an inline comment as done.Thu, Nov 12, 1:23 PM
nikic added inline comments.
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

Um, where? I'm not seeing it ^

jdoerfert added inline comments.Thu, Nov 12, 1:40 PM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

I think I was simply confused. Maybe today is not the day to finish this review (for me). I'll give it another shot tomorrow ;)

asbirlea accepted this revision.Thu, Nov 12, 5:06 PM

I wouldn't be surprised if there are other asymmetries, thank you for digging further here.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

I believe this is correct :-).

This revision is now accepted and ready to land.Thu, Nov 12, 5:06 PM
nikic added inline comments.Fri, Nov 13, 12:35 AM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

I think @jdoerfert was right, and there is a mistake here: This should be comparing against V1Size rather than V2Size.

// Non-negative case:
0 ... V2Size ... GEP1BaseOffset ... GEP1BaseOffset+V1Size
// Non-positive case:
GEP1BaseOffset ... GEP1BaseOffset+V1Size ... 0 ... V2Size

We need to check that V1Size fits between GEP1BaseOffset and 0, the V2Size access is above zero and not relevant.

I'll have to add a test where both access sizes are different.

asbirlea added inline comments.Fri, Nov 13, 12:51 AM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

Adding a test will be the best solution here, but here's where I went back and forth here and I ended up concluding the above is correct.

// Non-negative case:
0 ... V2 ... GEP1BasePoint
//       \____/<- V2 needs to fit here;
// All offsets are +,  and GEP1BaseOffset already had GEP2 subtracted.

// Non-positive case:
// Initializing like above: "AllNonPositive = GEP1BaseOffset.isNonPositive();", means:
GEP1BasePoint ... V2 ... 0
// All offsets are -, so it's still V2Size that needs to fit between V2 and GEP1BasePoint.

Initially I thought we need to fit V1Size, and in order to match the condition for non-negatives (and fit V2) you'd need to initialize AllNonPositive = GEP1BaseOffset.isNonNegative();
So you'd get:
V2 ... GEP1BasePoint ... 0
But the indices are negative as well.

Again, +1 on a test to clarify either way.

nikic updated this revision to Diff 305157.Fri, Nov 13, 8:13 AM

Use correct size, add test with different sizes.

nikic added inline comments.Fri, Nov 13, 8:16 AM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1451

I've now added a test that asserted with the previous code. The thing to keep in mind here is that while the GEP offset is negative, the access size still points in the positive direction. So for the negative case, what we need is that access 1 fits between the negative GEP1BaseOffset and zero, because zero is where the access 2 starts.

asbirlea accepted this revision.Mon, Nov 16, 5:32 PM

As talked offline, this lgtm.

This revision was automatically updated to reflect the committed changes.

Hello!

The following hits an assertion with this patch. If I run

opt -S -o - aa.ll -aa-eval

I get

opt: ../lib/Analysis/AliasAnalysisEvaluator.cpp:180: void llvm::AAEvaluator::runInternal(llvm::Function &, llvm::AAResults &): Assertion `AR == AA.alias(*I2, I2Size, *I1, I1Size) && "AA query not symmetric"' failed.

with aa.ll being

define void @dll(i32* %outputdata_p) {
entry:
  br label %while.body

while.body:                                       ; preds = %cond.end, %entry
  %outputdata_p.addr.042 = phi i32* [ %outputdata_p, %entry ], [ %incdec.ptr6, %cond.end ]
  br label %cond.end

cond.end:                                         ; preds = %while.body
  %incdec.ptr6 = getelementptr inbounds i32, i32* %outputdata_p.addr.042, i32 1
  br i1 undef, label %while.body, label %crit_edge44

crit_edge44:                                      ; preds = %cond.end
  %split45 = phi i32* [ %incdec.ptr6, %cond.end ]
  unreachable
}

@uabelho Thanks for the report! I have reverted the assert in https://github.com/llvm/llvm-project/commit/85ccdcaa502ee2c478f2d0ba2b1e217117b69032. We'll have to fix this asymmetric in phi-phi aliasing before re-enabling it.

@uabelho Thanks for the report! I have reverted the assert in https://github.com/llvm/llvm-project/commit/85ccdcaa502ee2c478f2d0ba2b1e217117b69032. We'll have to fix this asymmetric in phi-phi aliasing before re-enabling it.

Thanks!