Page MenuHomePhabricator

[LoopUnswitch] Do not freeze condition if hoisted branch is guaranteed to be reachable
Needs ReviewPublic

Authored by aqjune on Jan 23 2017, 4:00 AM.

Details

Summary

If the branch is hoisted to the loop header, and we know that it was originally
reachable, then no freeze instruction is needed since we are not introducing
a new branch in the dynamic control-flow.

For example:

while (D) {
  I1
  I2
  if (C) { A }
  else   { B }
}

If we know that I1 and I2 always transfer execution to the successor, then we
know that branch on C is reachable if D is true at least once.
Therefore, transforming the code above to the following is correct:

if (D) {
  if (C) {
    do { I1 I2 A } while (D)
  } else {
    do { I1 I2 B } while (D)
  }
}

Diff Detail

Event Timeline

aqjune created this revision.Jan 23 2017, 4:00 AM
nlopes edited the summary of this revision. (Show Details)Jan 23 2017, 4:01 AM
nlopes added a subscriber: nlopes.Jan 24 2017, 1:08 AM
regehr added a subscriber: regehr.Jan 28 2017, 10:04 PM
efriedma added inline comments.
lib/Transforms/Scalar/LoopUnswitch.cpp
722

Maybe we should be a little more aggressive here? LoopUnswitch::TryTrivialLoopUnswitch has a branch-following loop which special-cases conditional branches with a constant condition.

Can we compute this once for the whole loop, rather than iterating over the whole loop for each basic block?

aqjune added inline comments.Feb 1 2017, 12:07 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
722

@efriedma Hello. I couldn't understand your comment. Do you mean we can cache the necessity of freeze when LoopUnswitch::TryTrivialLoopUnswitch is called (which is called at line 545), and then reuse the cached info here?

efriedma added inline comments.Feb 1 2017, 10:18 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
722

The two paragraphs are sort of separate issues: you should share the branch-following code, and you should compute this property outside of the loop. I don't think you can reuse the result from TryTrivialLoopUnswitch because it isn't computing the same property.

aqjune updated this revision to Diff 86826.Feb 2 2017, 8:53 AM
  • Compute reachable terminators in advance so it does not traverse same basic block multiple times
  • Let branchs with constant condition be treated well
aqjune added inline comments.Feb 2 2017, 8:58 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
722

@efriedma I lifted out the loop to line 610 so it calculates reachable terminators in advance. Also I added code snippet which deals with constant branch condition.

(I don't feel comfortable approving changes to loop-unswitch, so someone else should probably look over this.)

lib/Transforms/Scalar/LoopUnswitch.cpp
708

Refactor the identical "find the next successor" code into a helper?

filcab added a subscriber: filcab.Feb 3 2017, 6:50 AM
filcab added inline comments.
lib/Transforms/Scalar/LoopUnswitch.cpp
679

break;
No need to keep going if we're just going to break the outer loop.

735

This comment seems to make more sense in line 681 (which already has a similar comment), since that's where you decide if you need to freeze the condition (and set NeedFreeze).

1058

(2) I guess :-)

1080

Minor nit: Maybe this instead of if + |=?
NeedFreeze = NeedFreeze || !isGuaranteedToTransferExecutionToSuccessor(&I);

aqjune added inline comments.Feb 3 2017, 7:43 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
708

@efriedma What do you mean by a helper?

aqjune updated this revision to Diff 86965.Feb 3 2017, 8:11 AM
  • Add FindNextSuccessorBlock
  • Minor modifications
aqjune marked 3 inline comments as done.Feb 3 2017, 8:13 AM

What do you mean by a helper?

Exactly what you did by adding FindNextSuccessorBlock.

aqjune updated this revision to Diff 106928.Jul 17 2017, 1:15 PM

Rebased to svn commit 308173