[ValueTracking] Allow getUnderlyingPointer to look through inttoptr/ptrtoint round trip casts #146432
Conversation
…trtoint round trip casts
|
@llvm/pr-subscribers-llvm-analysis Author: Drew Kersnar (dakersnar) ChangesIt has been established in past discussions that optimizing away a round trip ptrtoint -> inttoptr cast in something like InstCombine is not correct (https://www.ralfj.de/blog/2020/12/14/provenance.html, #33896). However, is it possibly correct to strip this round trip when recursing through Full diff: https://github.com/llvm/llvm-project/pull/146432.diff 2 Files Affected:
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index e576f4899810a..837c6a6caa4b2 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -6661,6 +6661,10 @@ const Value *llvm::getUnderlyingObject(const Value *V, unsigned MaxLookup) {
if (!NewV->getType()->isPointerTy())
return V;
V = NewV;
+ } else if (Operator::getOpcode(V) == Instruction::IntToPtr &&
+ Operator::getOpcode(cast<Operator>(V)->getOperand(0)) ==
+ Instruction::PtrToInt) {
+ V = cast<Operator>(cast<Operator>(V)->getOperand(0))->getOperand(0);
} else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
if (GA->isInterposable())
return V;
diff --git a/llvm/unittests/Analysis/ValueTrackingTest.cpp b/llvm/unittests/Analysis/ValueTrackingTest.cpp
index 129052fbe08b8..b40f38d464ed9 100644
--- a/llvm/unittests/Analysis/ValueTrackingTest.cpp
+++ b/llvm/unittests/Analysis/ValueTrackingTest.cpp
@@ -3350,6 +3350,18 @@ TEST_F(ValueTrackingTest, ComputeConstantRange) {
}
}
+TEST_F(ValueTrackingTest, GetUnderlyingObject) {
+ parseAssembly(R"(
+ @globalmem = external global i8
+ define void @test() {
+ %A = getelementptr i8, ptr @globalmem, i64 0
+ %A2 = getelementptr i8, ptr inttoptr (i32 ptrtoint (ptr @globalmem to i32) to ptr), i64 0
+ ret void
+ }
+ )");
+ EXPECT_EQ(getUnderlyingObject(A), getUnderlyingObject(A2));
+}
+
struct FindAllocaForValueTestParams {
const char *IR;
bool AnyOffsetResult;
|
| removeRoundTripCasts(O1); | ||
| removeRoundTripCasts(O2); |
There was a problem hiding this comment.
@nikic I'm wondering if a less general change could be considered correct. It sounds like the change in getUnderlyingObject would not be correct for every user, but for this specific user of getUnderlyingObject, could it be correct to strip away this pattern as this pseudocode would do?
The reason this would be useful would be because it could open up an easy NoAlias result.
Lets say we have the following instruction A, that we are comparing to instruction B in BasicAliasAnalysis. Each have a different underlying global value, but A's pointer is wrapped in the round trip cast.
%A= getelementptr i8, ptr inttoptr (i32 ptrtoint (ptr @globalmem to i32) to ptr), i64 0
%B = getelementptr i8, ptr @globalmem_2, i64 0
On line 1619 of this file, isIdentifiedObject is called on each underlying object. If we do not traverse through the inttoptr/ptrtoint round trip we do not identify the underlying object as a global value, and thus are not able to prove NoAlias with that check.
Is it possible this traversal is correct in this specific case, or is it the same problem as the more general optimizations?
There was a problem hiding this comment.
It's the same problem as in the general case. You can't look through inttoptr/ptrtoint cast in any code that does provenance-based reasoning, which BasicAA does (e.g. via isIdentifiedObject).
It is possible to look through these casts, but you can only reason about the address of the pointer after you do. This means that in your example, we would not be able to prove these are NoAlias because the underlying object is different -- but we could prove that the accessed address ranges must be disjoint.
It's possible, but this would need substantial changes to BasicAA and the AA API.
There was a problem hiding this comment.
Thanks for the explanation, that makes sense to me. Closing this PR. Appreciate the time!
|
@nikic It seems that a caching-based CaptureTracking analysis would also solve the issue I'm exploring, which is referenced in a TODO here: . I saw that you recently did some work in this area, out of curiosity, do you happen to know whether that specific TODO is being tracked/discussed anywhere? Do you have a rough idea of its feasibility/difficulty? I was going to start scoping out the idea but wanted to see if anyone else had already explored this. I would imagine the biggest difficulty would be the lifetime of the cache would have to be the lifetime of an instance of the AliasAnalysis class in order to be useful. Which might mean CaptureTracking.cpp would need to be redesigned. But these are very initial thoughts. |
|
@dakersnar CaptureTracking queries made by AA are already cached (see CaptureAnalysis), but the duration of that caching can be short. If BatchAAResults is not used, it will be "cached" only during one AA query. We do use BatchAA in many of the most expensive areas nowadays... How many uses do you need to explore for your case? |
|
It's around 1100 uses. The AA calls are coming from the LoadStoreVectorizer, and yes, in this case the cache would need to persist across different AA queries. Let me see if I can adjust the LoadStoreVectorizer to take advantage of this feature. |
|
Wow, using the BatchAAResults feature in the LoadStoreVectorizer indeed solves the problem. I'll open another MR that makes that change, but do you happen to see any potential downsides to introducing that feature to the LSV? I think it's a particularly good use case for it because there are a ton of Alias Analysis calls that all happen before any IR changes are made, so it would be safe to use BatchAA across those calls. Is that reasoning correct? |
|
Yes, using BatchAA is always safe if IR is not modified. Using it in LSV should be fine. Though I don't really get how just using BatchAA fixes your problem. |
|
It fixes the problem because it would also be paired with an increase in the MaxUsesToExplore in CaptureTracking.cpp. Speaking of which, now that this cache exists, should we consider increasing that default limit, as the TODO suggests? Or is that TODO referring to a different type of cache? Perhaps we could have two separate limits, one that is higher and only to be used if the caller is using the Batched version of Alias Analysis? |
It has been established in past discussions that optimizing away a round trip ptrtoint -> inttoptr cast in something like InstCombine is not correct (https://www.ralfj.de/blog/2020/12/14/provenance.html, #33896). However, is it possibly correct to strip this round trip when recursing through
getUnderlyingObject? This would improve alias analysis.