This is an archive of the discontinued LLVM Phabricator instance.

[LoopSimplify] Update LCSSA after separating nested loops.
ClosedPublic

Authored by mzolotukhin on Jun 23 2016, 3:15 PM.

Details

Summary

Usually LCSSA survives this transformation, but in some cases (see
attached test) it doesn't: values from the original loop after
separating might be used from the outer loop. Before the transformation
it was the same loop, so LCSSA phis were not required.

We might move this logic, along with the logic for updating LoopInfo, to
BasicBlockUtils (routine SplitBlockPredecessors), but I now see this
pretty independent on the fix in question.

This fixes PR28272.

Diff Detail

Event Timeline

mzolotukhin retitled this revision from to [LoopSimplify] Update LCSSA after separating nested loops..
mzolotukhin updated this object.
mzolotukhin added reviewers: sanjoy, hfinkel, chandlerc.
mzolotukhin added a subscriber: llvm-commits.
chandlerc added inline comments.Jun 27 2016, 1:27 PM
lib/Transforms/Utils/LoopSimplify.cpp
343–345

Is it possible to track these when putting the instructions into this set? Maybe its just not worth it because its just the PHI nodes...

346

8? That seems like lots? Maybe not though

360–365

It's a bit odd to use this linear search for a unique dominating exit block... I wonder, is there some implicit guarantee that makes it make more sense? Do we instead want to perhaps build up a map from incoming BB of the outer PHI to dominating exit BB?

sanjoy added inline comments.Jun 27 2016, 2:03 PM
lib/Transforms/Utils/LoopSimplify.cpp
353

s/V/I/

370

What if you have

loop:
  %iv = phi [ 0, %entry ] [ %iv, (%loop, %left, %right)],  [ %iv.inc, %outer ]
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %loop

then the separated loop structure will be

outer_header:
  %iv = [ 0, %entry ] , [ %iv.inc, %outer ]
  br loop

loop:
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %loop

Now %iv.inc is live out of the inner loop and none of the inner loop
exits (%left, %right) dominate %outer.

sanjoy added inline comments.Jun 28 2016, 5:34 PM
lib/Transforms/Utils/LoopSimplify.cpp
370

Nit: the latter code snippet should be

outer_header:
  %iv = [ 0, %entry ] , [ %iv.inc, %outer ]
  br loop

loop:
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %outer_header

Hi Sanjoy, Chandler,

Thanks for taking a look!
And thanks for the example, Sanjoy, I need to think over it. Probably, we'll need to insert phis if IncomingBB is reachable from the exit block (and then somehow find a merging point to insert another phi), or something like this.

Michael

mzolotukhin updated this revision to Diff 62891.Jul 6 2016, 9:41 AM
  • Use SSAUpdate to properly rewrite values.
  • Break edges to exit-blocks after separating loop nest if the exit block has a pred from outside the loop.
  • Add Sanjoy's test.
sanjoy requested changes to this revision.Jul 13 2016, 3:17 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Transforms/Utils/LoopSimplify.cpp
349

Why not use predecessors ?

Actually, why not:

if (any_of(predecessors(ExitBlock), [](BasicBlock *BB) {
  return !L->contains(BB);
    }) {
rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
}
367

Why do you need to separately create a SmallSetVector here?

373

NewBB is the header of the new loop, right? (if so, a naming change
would be nice). Then I'm not sure if scanning NewBB for LCSSA
violations is sufficient -- what if we have:

loop:
  %iv = phi [ 0, %entry ] [ %iv, (%loop, %left, %right)],  [ %z, %outer ]
  switch(condition), %left, %right, %loop

left:
  %x = def()
  br condition, %outer_l, %loop

outer_l:
  br outer

right:
  %y = def()
  br condition, %outer_r, %loop

outer_r:
  br outer

outer:
  %z = phi(%x, %y)
  br %loop

then the separated structure would be

outer_l:
  %iv = phi [ 0, %entry ], [ %z, outer ]
  br loop

loop:
  switch(condition), %left, %right, %loop

left:
  %x = def()
  br condition, %outer_l, %loop

outer_l:
  br outer

right:
  %y = def()
  br condition, %outer, %loop

outer_r:
  br outer

outer:
  %z = phi(%x, %y)  ;; this PHI needs to be edited as well
  br %loop
387

When is this true?

392

s/the exit block/an exit block/
s/the phi-node/an LCSSA phi node/

This revision now requires changes to proceed.Jul 13 2016, 3:17 PM
mzolotukhin edited edge metadata.
  • Modify test to catch more corner cases including a case mentioned by Sanjoy. Also, add an assert.
  • Make processInstruction from LCSSA.cpp externally available.
  • Use formLCSSAForInstruction routine instead of doing it manually.
  • Use any_of when rewriting loop exit blocks.
mzolotukhin edited edge metadata.
  • We don't need to include SSAUpdated any more.

Hi Sanjoy,

Thanks for review! You're right that we need to look not only at NewBB but in other blocks that happen to be outside the inner loop as well. I updated the test to check this case as well.

Also, I decided to make processInstruction from LCSSA externally available, since it greatly simplifies the patch. I'll submit the corresponding patch for a separate review (we'll need to iron out the API we want to have there), but I'll keep it here as well just to show you the complete picture.

Thanks,
Michael

sanjoy accepted this revision.Jul 15 2016, 12:57 AM
sanjoy edited edge metadata.

lgtm with nits

lib/Transforms/Utils/LoopSimplify.cpp
330

Can't this just be a SmallVector ?

379

How about avoiding repeated calls to formLCSSAForInstruction on the same instruction using a set?

Given that you'll now send in a worklist of instructions anyway, maybe just unique that worklist before sending it in?

592

I was asking to use any_of instead of the loop you added. :)

If you want to clean this up also, that's fine too of course. :)

This revision is now accepted and ready to land.Jul 15 2016, 12:57 AM
This revision was automatically updated to reflect the committed changes.

Thanks for reviewing, Sanjoy!

I committed this in r275891 with your remarks addressed.

Michael

lib/Transforms/Utils/LoopSimplify.cpp
330

Indeed it can. Fixed!

379

Fixed.

592

Oops, wrong spot:)