Page MenuHomePhabricator

[LoopFusion] Move instructions from FC1.Preheader to FC0.Preheader when proven safe.
ClosedPublic

Authored by Whitney on Dec 22 2019, 4:58 PM.

Details

Summary

Currently LoopFusion give up when the second loop nest preheader is
not empty. For example:

for (int i = 0; i < 100; ++i) {}
x+=1;
for (int i = 0; i < 100; ++i) {}

The above example should be safe to fuse.
This PR moves instructions in FC1 preheader (e.g. x+=1; ) to
FC0 preheader, which then LoopFusion is able to fuse them.

Diff Detail

Event Timeline

Whitney created this revision.Dec 22 2019, 4:58 PM
Whitney updated this revision to Diff 235241.Dec 24 2019, 5:08 PM

Added a new test case.

Some minor comments only.

llvm/lib/Transforms/Scalar/LoopFuse.cpp
89–91

unsafe preheader is probably not the best term. Maybe spell it out: non-empty preheader with instructions that cannot be moved?

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
421

while (FromBB.size() > 1) might be easier, with *I = FromBB.front().

Why do you take the DT, PDT, DI? I would not or just them to assert(isSafe..)

llvm/test/Transforms/LoopFusion/diagnostics_missed.ll
219

Delete the attributes please.

llvm/test/Transforms/LoopFusion/simple.ll
335

Maybe make it more realistic by adding an argument %x and 1, as your commit message example shows. We can then also have a negative test where you replace 1 with %i from the first loop.

Whitney updated this revision to Diff 235290.Dec 25 2019, 10:33 AM
Whitney marked 5 inline comments as done.

Addressed review comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
421

Forgot to add the isSafeToMoveBefore check, there is no need to check for this use case, but this utility can be use by user that didn't check beforehand.

jdoerfert accepted this revision.Dec 25 2019, 3:13 PM

One more minor comment below, otherwise LGTM.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
421

Fair.

With the while loop and front, you don't need the terminator check anymore.
For any non-broken IR this will work fine without.

This revision is now accepted and ready to land.Dec 25 2019, 3:13 PM
Whitney updated this revision to Diff 235302.Dec 25 2019, 4:00 PM

Address review comment.

Whitney marked an inline comment as done.Dec 25 2019, 4:00 PM
This revision was automatically updated to reflect the committed changes.