Page MenuHomePhabricator

[InstCombine] icmp eq/ne (gep inbounds P, Idx..), null -> icmp eq/ne P, null
ClosedPublic

Authored by reames on Thu, Aug 22, 10:58 AM.

Details

Summary

This generalizes the isGEPKnownNonNull rule from ValueTracking to apply when we do not know if the base is non-null, and thus need to replace one condition with another.

This is an alternative, much more aggressive, approach to the same problem as https://reviews.llvm.org/D64533.

The core notion is that since an inbounds GEP can only form null if the base pointer is null and the offset is zero. However, if the offset is non-zero, the the "inbounds" marker makes the result poison. Thus, we're free to ignore the case where the offset is non-zero. Similarly, there's no case under which a non-null base can result in a null result without generating poison.

Reviewers - I'd appreciate careful review of the reasoning here. It's subtle, and I found several bugs in early versions of this patch. I'm not at all certain there aren't some left.

Diff Detail

Repository
rL LLVM

Event Timeline

reames created this revision.Thu, Aug 22, 10:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Aug 22, 10:58 AM
reames updated this revision to Diff 216674.Thu, Aug 22, 11:05 AM

Fix a typo in one of the tests and add clarifying comments.

reames retitled this revision from [InstCombine] icmp eq/ne (gep P, Idx..), null -> icmp eq/ne P, null to [InstCombine] icmp eq/ne (gep inbounds P, Idx..), null -> icmp eq/ne P, null.Thu, Aug 22, 11:10 AM
jdoerfert added inline comments.Thu, Aug 22, 1:12 PM
lib/Transforms/InstCombine/InstCombineCompares.cpp
882 ↗(On Diff #216674)

Side note: This should probably be RHS->stripPointerCastsSameRepresentation() as we below argue about nullness of values and address spaces.

915 ↗(On Diff #216674)

I drew up the following table to convince myself this is valid given the restrictions checked in the conditional above: inbounds, rhs = zero, null is not valid.

base/offsetzeronot zero
zerob = zeropoison
not zerobnot zero or poison
nikic added a comment.Thu, Aug 22, 1:31 PM

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

Here it could cause problems, different other places we actually accumulate the index and decide based on the value, e.g., Offset != 0, which should avoid the problem.
Long story short, I guess we need another check in the if condition here.

reames planned changes to this revision.Thu, Aug 22, 4:46 PM

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

I'm happy to add another bailout. To be honest, the exact semantics of unsized types are not all clear to me.

reames updated this revision to Diff 216764.Thu, Aug 22, 8:39 PM

When I went to add the suggested size-0 type bailout, I realized the existing code was correct for this case. I added tests and a comment to show this.

When I went to add the suggested size-0 type bailout, I realized the existing code was correct for this case. I added tests and a comment to show this.

The comment is helpful, thanks!

I'm good with this but I'm also tired. Let's wait for others to voice their opinion or at least till I can take another look with fresh eyes.

nikic accepted this revision.Fri, Aug 23, 12:33 AM

LGTM

lib/Transforms/InstCombine/InstCombineCompares.cpp
911 ↗(On Diff #216764)

I'd suggest changing Index -> Offset in these comments.

test/Transforms/InstCombine/gep-inbounds-null.ll
36 ↗(On Diff #216764)

Should be eq?

This revision is now accepted and ready to land.Fri, Aug 23, 12:33 AM
xbolva00 added inline comments.
lib/Transforms/InstCombine/InstCombineCompares.cpp
907 ↗(On Diff #216764)

Four?

xbolva00 added inline comments.Fri, Aug 23, 8:29 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
900 ↗(On Diff #216764)

isa<ConstantPointerNull>(...)

This revision was automatically updated to reflect the committed changes.

I noticed a bug in what got committed, and fixed that in rL369795.

reames marked 4 inline comments as done.Fri, Aug 23, 11:48 AM

A vector extension of this is now posted for review: https://reviews.llvm.org/D66671

lib/Transforms/InstCombine/InstCombineCompares.cpp
900 ↗(On Diff #216764)

Left as is for the vector patch now posted.

Thanks for taking the time doing this! Now the compile times for glew are back to more tolerable levels (down to 1 minute in my case, from 6 minutes before), despite the excessive unrolling.