Page MenuHomePhabricator

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

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



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) {
  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.

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

@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

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

@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.)


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.

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


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).


(2) I guess :-)


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

aqjune added inline comments.Feb 3 2017, 7:43 AM

@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

reames requested changes to this revision.Nov 8 2019, 7:41 AM
reames added inline comments.

Please see Analysis/MustExecute.h. We already have a tested implementation of this, please use it. It looks like you probably want ICFLoopSafetyInfo

This revision now requires changes to proceed.Nov 8 2019, 7:41 AM
jdoerfert added inline comments.

You can also use MustBeExecutedContextExplorer (with or without LI, DT, PDT).