This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Special case the problematic (gep inbounds p, iv == nullptr) problem (pr42357)
AbandonedPublic

Authored by reames on Jul 10 2019, 2:46 PM.

Details

Summary

LFTR and SCEV interact badly on the following test case:

%gep = getelementptr inbounds i8, i8* %base, i64 %iv
%cnd1 = icmp ne i8* null, %gep
br i1 %cnd1, label %latch, label %exit

SCEV will happily compute an exit count for this, but does so disregarding the inbounds annotation. As a result, we end up with a integer comparison of the following form:

%cnd1 = icmp ne i64 %iv, -1 * (ptrtoint(p))
br i1 %cnd1, label %latch, label %exit

Once we've done that, we delete the GEP, and loose the inbounds fact. At that point, we're stuck.

As somewhat of a hack, this patch implements a special case rule to discharge the null check before LFTR has a chance transform it. I don't really like this solution, but after a fair amount of thought, I can't come up with anything better which isn't either a) just as much of a special case, or b) a huge amount of complexity.

(For context, the reported compile time regression happens purely because we end with a loop which "more analyzeable" after LFTR (11 occurrences), and other transforms go to town. We never discharged the check at all - in either form -, and in the faster case just left the loops unoptimized. This special case appears to address the slowdown on this example.)

Diff Detail

Event Timeline

reames created this revision.Jul 10 2019, 2:46 PM
grandinj added inline comments.
lib/Transforms/Utils/SimplifyIndVar.cpp
195

looses->loses

198

loose->lose

nikic added inline comments.Jul 13 2019, 1:40 PM
lib/Transforms/Utils/SimplifyIndVar.cpp
206

GEP->getType()->isPointerTy() should always be true for a single-index GEP ... right?

220

I believe we also need to check for a pointer to a zero-sized type here, in which case we might have null + 0*Idx == null even if the index is non-zero.

reames marked 2 inline comments as done.Jul 17 2019, 12:18 PM
reames added inline comments.
lib/Transforms/Utils/SimplifyIndVar.cpp
206

Nope. The following is valid:
%vec_gep = gep i8, i8* %scalar_base, <2 x i64> zeroinitializer

(That's equivalent to a broadcast.)

220

Just to make sure I'm following you, you concern is a zero-sized *index type* right? If so, no, that's disallowed by the verifier.

nikic added inline comments.Jul 17 2019, 1:08 PM
lib/Transforms/Utils/SimplifyIndVar.cpp
206

Oh right, thanks.

220

I'm not sure what the right terminology is, but I mean something like getelementptr {}, {}* %p, i32 %idx, which is legal and evaluates to {}* %p.

I somehow have a bad feeling about this pattern matching "hack".

After looking at some of the test cases only, couldn't we rewrite null comparisons against a gep inbounds altogether in a more generic way?

I mean something like this, assuming null is not a valid pointer:

%c = icmp eq, null, gep inbounds %p %idx
%d = icmp ne, null, gep inbounds %p %idx

will become

%c0 = icmp eq, ptrtoint(%p), 0
%c1 = icmp eq,         %idx, 0
%c = and %c0, %c1
%d = xor %c, 1

Now, %c0 is loop invariant and %c1 is false for all but one iteration (in the common case of a counting loops).
In addition, if we can show %p != null we know %c0 is false which makes %c false as well and %d true.

Maybe I made a mistake but if the above logic holds, I would prefer a solution like that in one or two steps, that is perform the transformation either way and then check if %p is nonnull or only do it if we know %p is nonnull (maybe in inst-combine)?

lib/Transforms/Utils/SimplifyIndVar.cpp
219

I am confused by this comment, especially the negative part.

Without thinking about it too much I would have said somehting like this:

// With inbounds, 'g = p + NonZero' implies both g and p are valid pointers. Assuming null is not a valid pointer in this function, see NullPointerIsDefined above, we know g and p are both non-null. Note, this does not hold if the offset is zero.
220

assuming you meant the inbounds case and this is legal, which I can imagine it is, we might have missed this special case in other places as well.

reames planned changes to this revision.Jul 30 2019, 11:26 AM

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

fhahn added a subscriber: fhahn.Aug 18 2019, 7:13 AM

See https://reviews.llvm.org/D66608 for an alternate approach in InstCombine as suggested in review here.

See https://reviews.llvm.org/D66608 for an alternate approach in InstCombine as suggested in review here.

FWIW, I like the D66608 approach way better.

reames abandoned this revision.Aug 23 2019, 11:08 AM

Alternate change landed, so patch abandoned.

FWIW, I like the D66608 approach way better.

For the record, it was the discussion on the PoisonChecking review which made me realize the alternate approach was possible. Particularly the comments about the out of bounds base immediately triggering poison for an inbounds GEP. Without that, the alternate approach didn't seem feasible. So thanks!