This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Look through PHIs, GEPs, IntToPtrs and PtrToInts to expose more constants when comparing GEPs
ClosedPublic

Authored by sbaranga on Dec 2 2015, 3:38 AM.

Details

Summary

When comparing two GEP instructions which have the same base pointer
and one of them has a constant index, it is possible to only compare
indices, transforming it to a compare with a constant. This removes
one use for the GEP instruction with the constant index, can reduce
register pressure and can sometimes lead to removing the comparisson
entirely.

InstCombine was already doing this when comparing two GEPs if the
base pointers were the same. However, in the case where we have
complex pointer arithmetic (GEPs applied to GEPs, PHIs of GEPs,
conversions to or from integers, etc) the value of the original
base pointer will be hidden to the optimizer and this transformation
will be disabled.

This change detects when the two sides of the comparison can be
expressed as GEPs with the same base pointer, even if they don't
appear as such in the IR. The transformation will convert all the
pointer arithmetic to arithmetic done on indices and all the
relevant uses of GEPs to GEPs with a common base pointer. The
GEP comparison will be converted to a comparison done on indices.

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 41607.Dec 2 2015, 3:38 AM
sbaranga retitled this revision from to [InstCombine] Look through PHIs, GEPs, IntToPtrs and PtrToInts to expose more constants when comparing GEPs.
sbaranga updated this object.
sbaranga added a reviewer: majnemer.
sbaranga added subscribers: llvm-commits, aadg, jmolloy.
majnemer edited edge metadata.Dec 2 2015, 8:16 AM

Please try to name your functions like transformToIndexedCompare instead of TransformToIndexedCompare.

lib/Transforms/InstCombine/InstCombineCompares.cpp
708

Please use auto * here.

835

If you are not using the result of dyn_cast, use isa instead.

861–863

The caller of GetAsConstantIndexedAddress passes in a GEPOperator but you are casting it to an Instruction. How have you ensured that the GEPOperator is an GetElementPtrInst instead of a ConstantExpr ?

Also, Value has a getContext member.

881

Please use auto *CI here.

881–894

Can you use isNoopCast here? Should simplify things.

888

Ditto.

903

Shouldn't this function be static ?

sbaranga updated this revision to Diff 41745.Dec 3 2015, 5:51 AM
sbaranga edited edge metadata.

Address the review comments so far.

sbaranga marked 6 inline comments as done.Dec 3 2015, 6:02 AM

Thanks for the review! The new version should fix all the issues pointed out.

-Silviu

lib/Transforms/InstCombine/InstCombineCompares.cpp
861–863

Thanks for the catch, this was indeed an issue. Not doing the cast in the first place should fix this.

jmolloy requested changes to this revision.Dec 9 2015, 3:07 AM
jmolloy added a reviewer: jmolloy.

Hi Silviu,

I've reviewed the first half of the patch and have a bunch of comments.

Cheers,

James

lib/Transforms/InstCombine/InstCombineCompares.cpp
604

Do you really expect 100 items in the worklist?

614

Why aren't you inserting V into Explored here, and just incrementing a counter instead of checking Explored.size() above?

624

It looks like you're checking the *next item to be inserted into the worklist* here; I think it'd be easier to just always insert into the worklist and check each item as it's removed from the worklist up above, like GetUnderlyingObjects does.

630

This and the previous block can be merged together.

644

These ifs can be merged.

654

Don't understand this comment?

667

Can't we insert the GEP after the transformed instruction instead of before the PHI?

691

I can't parse this comment :(

701

This would be better written as

I = &*std::next(I->getIterator());
712

We should assert this.

731

ValueToValueMapTy might help here.

761

It seems a bit strange to do all this work again. You've already explored before; if you'd have just kept the explore order you'd be able to iterate over Explored here without creating it afresh.

This revision now requires changes to proceed.Dec 9 2015, 3:07 AM

Hi James,

Thanks for having a look. I've added some replies inline. I should have a new version of this patch that addresses your comments out soon.

Thanks,
Silviu

lib/Transforms/InstCombine/InstCombineCompares.cpp
604

Not frequently, but it is possible. Probably the limit wouldn't be ever reached in practice, but we still need to have it. In my experience if we can't do the transformation we usually bail out early, so it shouldn't be a very big problem.

I can do compile time measurements if you think this would be a problem.

624

My intention was to limit the memory usage of the work list to |V| (you would get |E| if you checked when removing from the worklist). However, it doesn't seem that bad either way.

761

Good idea, thanks! It would technically need to be the reverse order, but that shouldn't be a problem.

hfinkel added inline comments.
lib/Transforms/InstCombine/InstCombineCompares.cpp
920

For the particular ICmpInst you've creating here, is this ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) or OFFSET1 cmp OFFSET2? Given that rewriteAsOffsetGEP returns a GEP that uses PtrBase as its base address, it looks like for former. I see no reason it should not be the latter, however.

I think this would be clearer if you used the same names in your comments as you did names for the local variables.

sbaranga added inline comments.Dec 11 2015, 6:00 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
667

Theoretically if you have

p0 = phi(x0, x1, ..)
p1 = phi(p0, ..)

you could insert GEPs before x0, x1, etc, and get:
BB1:

y0 = gep(base, x0)

BB2:

y1 = gep(base x1)

BB3:

p0 = phi(y0, y1)
p1 = phi(p0, ..)

However you end up inserting a lot of geps using this strategy. It's not clear to me that this is a good thing.
So we could also handle this case, but I don't think it's worth it.

731

I could use it, but I'm not sure how it would help.

920

Hi Hal,

Should be the latter (in rewriteAsOffsetGEP NewInsts maps the geps to offsets). Maybe rewriteGEPAsOffset would be a better name for that function.

Thanks,
Silviu

sbaranga updated this revision to Diff 42523.Dec 11 2015, 7:48 AM
sbaranga edited edge metadata.

Merged the traversal algorithms for the from canRewriteAsOffsetGEP and rewriteAsOffsetGEP.
Now the order in recorded in rewriteAsOffsetGEP.

Performed several other small changes requested during review.

hfinkel added inline comments.Dec 11 2015, 8:53 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
904

Still don't find this clear. It seems to me that:

std::tie(PtrBase, Index) = GetAsConstantIndexedAddress(GEPLHS, DL);

returns PtrBase and Index such that GEP(PtrBase, Index) == GEPLHS. And then:

RewriteGEPAsOffset(RHS, PtrBase)

returns GEP(PtrBase, Something) == RHS. And then we compare:

Index icmp GEP(PtrBase, Something)

which must be wrong. What am I missing?

sbaranga added inline comments.Dec 11 2015, 9:03 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
904

RewriteGEPAsOffset returns the offset, not the GEP.

hfinkel added inline comments.Dec 11 2015, 9:07 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
904

Ah, I understand now. The GEP it builds is not returned, but is for use by other users of the original GEP being replaced.

sbaranga added inline comments.Dec 11 2015, 9:09 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
904

Yes, that is correct. Would there be any better way to express this?

hfinkel added inline comments.Dec 11 2015, 9:16 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
904

Probably not. The code in RewriteGEPAsOffset does say that the GEP is being generated for external users. I did not read it with sufficient care.

I think however, it is worth nothing in a comment here that RHS is being replaced by a rewritten GEP and the GEP's Index operand it being returned. Otherwise, the fact that RHS is no longer valid after the function call is not obvious.

jmolloy requested changes to this revision.Dec 14 2015, 1:15 AM
jmolloy edited edge metadata.

Please try to name your functions like transformToIndexedCompare instead of TransformToIndexedCompare.

Please do update your function names to begin with a lower case letter as David asked.

lib/Transforms/InstCombine/InstCombineCompares.cpp
604

OK, but the smallvector value should be optimized for the frequent case. Something like 16 would be more appropriate?

630

You should move the comment inside of the if, so it makes sense.

678
for (auto &Use : Val->uses())  ?
804

Isn't this a ptrtoint?

850

possibility

This revision now requires changes to proceed.Dec 14 2015, 1:15 AM
sbaranga added inline comments.Dec 14 2015, 3:05 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
678

This is strange, Value seems to not have a uses() method.

804

The implementation creates a ptrtoint or inttoptr depending on the second argument (Start-getType() here). We know that Start is a pointer since it is produced by a GEP, so this will create a inttoptr.

904

Thanks, I'll add a comment.

sbaranga updated this revision to Diff 42699.Dec 14 2015, 3:13 AM
sbaranga edited edge metadata.

Change the names of the functions (back) to lower case.
Use a smaller default size for the traversal SmallVector (changed to 16).

jmolloy added inline comments.Dec 14 2015, 3:19 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
678

It does! :)

804

Ah OK, My bad misreading this.

sbaranga updated this revision to Diff 42700.Dec 14 2015, 3:34 AM
sbaranga edited edge metadata.

Changed loops to use the range for syntax.

sbaranga added inline comments.Dec 14 2015, 3:36 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
678

Yes, it does, I don't know how I missed it.

Hi Silviu,

This now LGTM. Please wait for Hal to give the OK too.

Cheers,

James

Optimistic Christmas Season Ping: Hal, did you have any more comments on this or were you happy?

jmolloy accepted this revision.Jan 6 2016, 5:24 AM
jmolloy edited edge metadata.

Hi,

Actually, I think this looks good enough to me that I can approve.

James

This revision is now accepted and ready to land.Jan 6 2016, 5:24 AM
sbaranga closed this revision.Jan 7 2016, 6:59 AM

Thanks, committed in r257064.

-Silviu