This is an archive of the discontinued LLVM Phabricator instance.

[CGP] Allow cycles during Phi traversal in OptimizaMemoryInst
ClosedPublic

Authored by skatkov on Jul 12 2017, 2:11 AM.

Details

Summary

Allowing cycles in Phi traversal increases the scope of optimize memory instruction
in case we are in loop.

The added test shows an example of enabling optimization inside a loop.

Diff Detail

Repository
rL LLVM

Event Timeline

skatkov created this revision.Jul 12 2017, 2:11 AM
efriedma added inline comments.Jul 12 2017, 12:33 PM
lib/CodeGen/CodeGenPrepare.cpp
4285 ↗(On Diff #106153)

When you're looking through a PHI node, equality can be deceptive; induction variables are the "same", but can have a different value. (We got into trouble with BasicAA doing that recently.) I'd like to see a comment explaining why this particular version of the algorithm is correct.

Hmmm, it is strange but it appeared not to be sent :( Re-sending.

lib/CodeGen/CodeGenPrepare.cpp
4285 ↗(On Diff #106153)

Hi Eli, thank you for the good question. My current understanding as is follows. We are traversing through all paths from address up by use->def chain and finally found that ptr is computed as arithmetic expression of the form BaseGv + Base + Scale * Index + Offset, where Offset and Scale are constants while BaseGV, Base and Index are exact the same instructions.

As soon as all these are the same and we traversed by all paths these instruction dominates our ptr and our memory instruction. Instruction cannot change its value on the paths its dominates and our found expression will produce the same value on the path from definition of these instruction till our load and actually further. So we can safely add the computation of ptr right before our load.

Please correct me if I'm wrong or missed anything.

efriedma added inline comments.Jul 17 2017, 12:41 PM
lib/CodeGen/CodeGenPrepare.cpp
4285 ↗(On Diff #106153)

That looks right.

Please add that explanation as a comment in the code.

skatkov updated this revision to Diff 107023.Jul 18 2017, 12:33 AM

Please take a look.

efriedma accepted this revision.Jul 18 2017, 11:09 AM

LGTM.

lib/CodeGen/CodeGenPrepare.cpp
4281 ↗(On Diff #107023)

"the" is unnecessary.

This revision is now accepted and ready to land.Jul 18 2017, 11:09 AM
This revision was automatically updated to reflect the committed changes.