This is an archive of the discontinued LLVM Phabricator instance.

[NaryReassoc] reassociate GEP for CSE
ClosedPublic

Authored by jingyue on May 15 2015, 3:46 PM.

Details

Summary

x = &a[i];
y = &a[i + j];

>

y = x + j;

along with some refactoring work such as extracting method
findClosestMatchingDominator.

Depends on D9786 which provides the ScalarEvolution::getGEPExpr interface.

Diff Detail

Event Timeline

jingyue updated this revision to Diff 25900.May 15 2015, 3:46 PM
jingyue retitled this revision from to [NaryReassoc] reassociate GEP for CSE.
jingyue updated this object.
jingyue edited the test plan for this revision. (Show Details)
jingyue added reviewers: broune, meheff.
jingyue added a subscriber: Unknown Object (MLST).
jingyue updated this revision to Diff 25984.May 18 2015, 10:48 AM

Following D9786, adjust the usage of getGEPExpr.

broune added inline comments.May 18 2015, 12:47 PM
lib/Transforms/Scalar/NaryReassociate.cpp
130

sss -> ss in reasssociates.

217

It's unclear to me what reassociable means here. Certainly other operations than add and GEPs can be reassociated in certain cases and I'd imagine that one can usually construct some example where that opens up further optimization opportunities. This seems more like a whitelist of instructions that nary reassociate knows how to deal with?

230–231

in the depth-first order -> in depth-first order
makes sure -> ensures that

You state more specifically that the traversal is in pre-order in another comment, and I think that that is necessary - it's not enough for the order to be depth-first. So this comment could also say pre-order.

236–237

Previously, the comment about SCEVable was helpful as it was not so clear that that was what isVectorTy was about. I think it's clear that isSCEVable checks if the type is SCEVable, so then the comment could be removed.

239

This could be moved into the previous if as

if (!SE->isSCEVable(I->getType()) || !isPotentiallyNaryReassociable(I)) {
243–244

Is this explaining why it is that we are not using the old I from above? If so, I'd say that it's not just because of tryReassociate, it's more because we called replaceAllUsesWith and then RecursivelyDeleteTriviallyDeadInstructions above. I'm not sure it requires a comment to explain that we then can't use the old I.

260

What's the motivation behind doing it this way instead of returning null here and then not needing isPotentiallyNaryReassociable?

337

I was wondering about the case where the index is unsigned so that hasNoUnsignedWrap would be relevant, but it looks like GEP always has signed indices. Is that how it works?

342

I think that one of these comments should say LHS + RHS.

453–470

"in the pre-order" -> "in pre-order" or perhaps "Because we do a pre-order traversal of the dominator tree"

jingyue added inline comments.May 19 2015, 3:50 PM
lib/Transforms/Scalar/NaryReassociate.cpp
130

Nice caaatch :)

217

Yes, you are right. It simply whitelists the instruction types we currently handle. Updated the comments accordingly.

230–231

Done.

239

Done.

243–244

It's tempting to put this statement before the "if tryReassociate" block. I was protecting code against that.

260

If !isPotentiallyNaryReassociable, we don't need to add I to SeenExprs. I could merge SeenExprs[SE->getSCEV(I)].push_back(I) to tryReassociate; then tryReassociate should probably be renamed to tryReassociateAndAddCandidate?

337

If the indexed is unsigned in the source code, then IR either zero-extends it (which we currently ignore) to pointer size or treats it as signed if it's already pointer size.

342

Done.

453–470

Done.

jingyue updated this revision to Diff 26102.May 19 2015, 3:51 PM

Bjarke's comments

broune added inline comments.May 19 2015, 5:52 PM
lib/Transforms/Scalar/NaryReassociate.cpp
260

I'm fine with it as it is now. Merging it into tryReassociate seems fine too.

402

Suppose that RHS is 64 bits and pointers are 32 bits (or if RHS is >64 bits), do we then need CreateSExtOrTrunc here instead of CreateSExt?

jingyue updated this revision to Diff 26119.May 19 2015, 9:04 PM

Yes, that's problematic. Fixed and added a test. Thank you!

broune accepted this revision.May 20 2015, 10:49 PM
broune edited edge metadata.
This revision is now accepted and ready to land.May 20 2015, 10:49 PM
jingyue closed this revision.May 21 2015, 4:21 PM