Here is another change I'd like to suggest to the BasicAliasAnalysis.
LLVM fails to remove the dead store in the following code:
%t = type { i32 }
define void @f(%t* noalias nocapture %stuff ) {
%p = getelementptr inbounds %t* %stuff, i32 0, i32 0
store i32 1, i32* %p; <-- This store is dead
%x = load i32* inttoptr (i32 12345 to i32*)
store i32 %x, i32* %p
ret void
}
when run through
./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -
The problem is that the alias analysis is unsure about whether %p and 12345 may alias. But since %p is derived from %stuff, which has the noalias attribute, and 12345 is a constant and therefore cannot be derived from %stuff, they cannot alias.
I'm attaching a patch which implements this. Please comment on whether this is sane, and if my code is the right way of doing it.
/ Hans
BasicAliasAnalysis.patch (1.12 KB)
Here is another change I'd like to suggest to the BasicAliasAnalysis.
LLVM fails to remove the dead store in the following code:
%t = type { i32 }
define void @f(%t* noalias nocapture %stuff ) {
%p = getelementptr inbounds %t* %stuff, i32 0, i32 0
store i32 1, i32* %p; <-- This store is dead
%x = load i32* inttoptr (i32 12345 to i32*)
store i32 %x, i32* %p
ret void
}
when run through
./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -
The problem is that the alias analysis is unsure about whether %p and 12345 may alias. But since %p is derived from %stuff, which has the noalias attribute, and 12345 is a constant and therefore cannot be derived from %stuff, they cannot alias.
This sounds right. And actually, it's not limited to noalias;
isIdentifiedObject objects don't alias inttoptr-casted integer
literals either. I have a few comments on the patch below.
I'm attaching a patch which implements this. Please comment on whether this is sane, and if my code is the right way of doing it.
/ Hans
Index: lib/Analysis/BasicAliasAnalysis.cpp
--- lib/Analysis/BasicAliasAnalysis.cpp (revision 86023)
+++ lib/Analysis/BasicAliasAnalysis.cpp (working copy)
@@ -643,6 +643,23 @@
if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType()))
return NoAlias; // Scalars cannot alias each other
+ // Constant ptr cannot alias with a noalias attribute
+ if (isa<Constant>(V1) && isa<PointerType>(V2->getType())) {
+ while (const GEPOperator *g = dyn_cast<GEPOperator>(V2))
+ V2 = g->getOperand(0);
+
+ if (const Argument *A = dyn_cast<Argument>(V2))
+ if (A->hasNoAliasAttr())
+ return NoAlias;
+ } else if (isa<Constant>(V2) && isa<PointerType>(V1->getType())) {
+ while (const GEPOperator *g = dyn_cast<GEPOperator>(V1))
+ V1 = g->getOperand(0);
+
+ if (const Argument *A = dyn_cast<Argument>(V1))
+ if (A->hasNoAliasAttr())
+ return NoAlias;
+ }
The GEP logic here is effectively doing (a subset of) what
getUnderlyingObject does. It would be better to move these checks
below the getUnderlyingObject calls just below so that they can
use the results from those calls instead.
And instead of checking for a no-alias argument, this code could
use isIdentifiedObject instead, following my comment above.
Dan
Dan Gohman wrote:
Here is another change I'd like to suggest to the BasicAliasAnalysis.
LLVM fails to remove the dead store in the following code:
%t = type { i32 }
define void @f(%t* noalias nocapture %stuff ) {
%p = getelementptr inbounds %t* %stuff, i32 0, i32 0
store i32 1, i32* %p; <-- This store is dead
%x = load i32* inttoptr (i32 12345 to i32*)
store i32 %x, i32* %p
ret void
}
when run through
./llvm-as -o - test2.ll | ./opt -O3 -o - | ./llvm-dis -o -
The problem is that the alias analysis is unsure about whether %p and 12345 may alias. But since %p is derived from %stuff, which has the noalias attribute, and 12345 is a constant and therefore cannot be derived from %stuff, they cannot alias.
This sounds right. And actually, it's not limited to noalias;
isIdentifiedObject objects don't alias inttoptr-casted integer
literals either. I have a few comments on the patch below.
I'm attaching a patch which implements this. Please comment on whether this is sane, and if my code is the right way of doing it.
/ Hans
Index: lib/Analysis/BasicAliasAnalysis.cpp
--- lib/Analysis/BasicAliasAnalysis.cpp (revision 86023)
+++ lib/Analysis/BasicAliasAnalysis.cpp (working copy)
@@ -643,6 +643,23 @@
if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType()))
return NoAlias; // Scalars cannot alias each other
+ // Constant ptr cannot alias with a noalias attribute
+ if (isa<Constant>(V1) && isa<PointerType>(V2->getType())) {
+ while (const GEPOperator *g = dyn_cast<GEPOperator>(V2))
+ V2 = g->getOperand(0);
+
+ if (const Argument *A = dyn_cast<Argument>(V2))
+ if (A->hasNoAliasAttr())
+ return NoAlias;
+ } else if (isa<Constant>(V2) && isa<PointerType>(V1->getType())) {
+ while (const GEPOperator *g = dyn_cast<GEPOperator>(V1))
+ V1 = g->getOperand(0);
+
+ if (const Argument *A = dyn_cast<Argument>(V1))
+ if (A->hasNoAliasAttr())
+ return NoAlias;
+ }
The GEP logic here is effectively doing (a subset of) what
getUnderlyingObject does. It would be better to move these checks
below the getUnderlyingObject calls just below so that they can
use the results from those calls instead.
And instead of checking for a no-alias argument, this code could
use isIdentifiedObject instead, following my comment above.
Thank you for the input, this certainly made things nicer. I have attached a patch that does this together with a test case.
/ Hans
BasicAliasAnalysis.patch (2.13 KB)
After discussing with Nick Lewycky in the IRC channel, here comes a less aggressive patch.
We were worried that a constant pointer could alias with a GlobalValue.
Also, if one pointer could be a GlobalValue and the other a GlobalAlias with the GlobalValue as aliasee.
However, I was not able to produce a test where this happens wihout the getUnderlyingObject() returning the same value.
It would be nice if someone could produce such a test case, or dismiss the possibility of this happening.
Anyway, saying that a Constant does not alias with a non-const isIdentifiedObject object seems safe.
/ Hans
Hans Wennborg wrote:
BasicAliasAnalysis2.patch (1.95 KB)
After discussing with Nick Lewycky in the IRC channel, here comes a less aggressive patch.
We were worried that a constant pointer could alias with a GlobalValue.
It can. You can have a GetElementPtr ConstantExpr which aliases a
GlobalValue, for example. What problem does this cause though?
Also, if one pointer could be a GlobalValue and the other a GlobalAlias with the GlobalValue as aliasee.
However, I was not able to produce a test where this happens wihout the getUnderlyingObject() returning the same value.
AliasAnalysis::isIdentifiedObject knows that GlobalAlias and ConstantExpr
values are not "identified objects", so I don't see the trouble here. Also,
getUnderlyingObject() knows how to look through (non-weak) GlobalAliases.
Dan
Hello Hans,
This patch looks fine. I've now talked with Nick on IRC and I've gone
re-read your previous patch and found what I was confused about.
Your original email talked about inttoptr-casted integer constants,
and I missed that the patch itself was using isa<Constant> instead,
which covers a lot of other kinds of things.
So while it's true that constants don't alias non-constant identified
objects and your new patch is fine, it's also true that the special
case of inttoptr-casted constant ints don't alias *any* identified
objects, in case you're interested in that too.
Dan
Hans Wennborg wrote:
After discussing with Nick Lewycky in the IRC channel, here comes a less aggressive patch.
We were worried that a constant pointer could alias with a GlobalValue.
Also, if one pointer could be a GlobalValue and the other a GlobalAlias with the GlobalValue as aliasee.
However, I was not able to produce a test where this happens wihout the getUnderlyingObject() returning the same value.
It would be nice if someone could produce such a test case, or dismiss the possibility of this happening.
My bad, it seems that while I wasn't looking, someone taught getUnderlyingObject to look through GlobalAliases and return what they point to!
However the previous patch was wrong given code like:
@gv = global i32 0
define void @test() {
store i16 1, i16* inttoptr(i64 add(i64 ptrtoint(i32* @gv to i64), i64 1) to i16*) ; ; Not dead
store i32 2, i32* @gv
ret void
}
Anyway, saying that a Constant does not alias with a non-const isIdentifiedObject object seems safe.
Yup!
Please remove the tailing ; on the lines where they aren't needed in your tests. Besides that, your patch looks great! Thanks!
Nick
Attaching patch with unnecessary trailing ; removed from test case.
Thank you both for helping to straighten this out, and sorry about the confusion.
Hans
Nick Lewycky wrote:
BasicAliasAnalysis3.patch (1.95 KB)