[NaryReassoc] reassociate GEP for CSE

[jingyue]

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.

[jingyue]

Following D9786, adjust the usage of getGEPExpr.

[broune]

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]

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]

Bjarke's comments

[broune]

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]

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