Improving the efficiency of the Loop Unswitching pass

[Abhilash]

Summary

{F2564183}The existing Loop Unswitching Pass generates an exponential number of loops with respect to the number of unswitched branches.
For any loop, the number of generated loops are n^2 where n is the number of unswitched branches.
The exponential nature of the transformation is an obstacle in generating better unswitched code.

Consider the following testcase:

1: for(int i=0;i<100;i++){
2: if (m)
3: a[i]*=2;
4: else if (n)
5: a[i]*=3;
6:
7: a[i]*=4;
8: }

m and n are loop invariants.

The existing algorithm generates 4 unswitched loops for the following cases:

1. Condition at line 2 is true and Condition at line 4 is true.
2. Condition at line 2 is true and Condition at line 4 is false.
3. Condition at line 2 is false and Condition at line 4 is true.
4. Condition at line 2 is false and Condition at line 4 is false.

However, due to the very nature of the else-if chain, there exists a control dependency between Conditions at line 2 and 4. When the Condition at line 2 is true, the Condition at line 4 is never taken and hence the outcome of the Condition at line 4 is irrelevant (don't care scenario), in this case.
This has not been accounted for, in the existing infrastructure. Currently, two similar loops are generated for cases 1 and 2 leading to redundancy and inefficiency.

It is sufficient, if we handle the following three cases:

1. Condition at line 2 is true.
2. Condition at line 2 is false and Condition at line 4 is true.
3. Condition at line 2 is false and Condition at line 4 is false.

One of the possible solutions, is to find the unreachable branches and eliminate them before unswitching.

The attached patch has the solution implemented in the Loop Unswitching Pass. The choice of this solution (among other possible solutions) is for the following reasons:

1. Eliminating unreachable branches so that many other branches are unswitched out of their enclosing loops (probably, better code).
2. Difficult to handle in the existing CFG Simplification Pass.

[mzolotukhin]

Hi,

Some initial comments, unrelated to the patch idea:

1. Please upload the patch with the full context (see http://llvm.org/docs/Phabricator.html).
2. Please run clang-format on it: some lines are too long.
3. Please add a testcase.

Thanks,
Michael

[weimingz]

lib/Transforms/Scalar/LoopUnswitch.cpp

624

already break in line 618?

[Abhilash]

The following changes have been incorporated in the updated diff:
As suggested by Michael Zolothukin:

1. Context added.
2. Clang-format has been applied.

As suggested by Weiming Zhao:

1. Removed the redundant conditional break on 'isUnreachable'.

[Abhilash]

This comment was removed by Abhilash.

[weimingz]

lib/Transforms/Scalar/LoopUnswitch.cpp

640

Does the True destination and False destination get swapped?

[mzolotukhin]

Hi,

Please find some comments inline. Also, you still need to add a test for this change.

Michael

lib/Transforms/Scalar/LoopUnswitch.cpp

625–629

Please use the same style for comments as in the rest of the file:

// Some branches ...
// ...
// ...

636

Maybe rewrite it as

if (!BI || !BI->isConditional())
  continue;
...

?

Then we can also continue if Cond is not a constant.

638

s/NULL/nullptr/

640

AFAIU, Succ is the unreachable successor. Probably, another name would work better here, because indeed, it's confusing.

659–660

I think this message would be confusing. We either need to provide more details (like why is it unreachable and under which conditions), or drop it completely.

[Abhilash]

Hi Michael Zolotukhin,

I have made the suggested changes and have added the testcase (earlier, I mistook about the testcase and attached my testcase with this revision).

Thanks,
Abhilash Bhandari

[mzolotukhin]

Hi Abhilash,

Thanks for working on this, please find some comments below.

Michael

lib/Transforms/Scalar/LoopUnswitch.cpp

632

Nit: we have a BI variable, and here we create BInst. Can we use a more descriptive name for one of them to help distinguishing them?

test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll

3

Please don't run entire -O3 pipeline in the test. It's slow and makes the test fragile (because passes in the pipeline change the input).

You can get IR just before loop-unswitching and use it as the test (and in the test run opt -loop-unswitch without -O3). To get full list of passes in O3 pipeline, you can run opt -O3 -debug-pass=Arguments.

Also, it's better to check what exactly what we get after loop-unswitching, not just look for a debug message. We use FileCheck tool for this, and annotate tests with special CHECK statements. The documentation is available here: http://llvm.org/docs/CommandGuide/FileCheck.html, and you can take a look at existing loop-unswitching tests if you need an example.

[anna]

Hi Abhilash,

I've added some comments mainly related to stylistic changes. Please have a look.

Thanks,
Anna

lib/Transforms/Scalar/LoopUnswitch.cpp

637–638

There's only formatting changes here right? Usually, in diff's it's better to avoid formatting changes not related to your code. I think this case is okay (since it's just a single one).

If you're using git, there's some script to clang-format *just your changes*. See git clang-format.

649–650

Isn't it enough to check if the basic block UnreachableSucc dominates I->getParent()?

656

I think this looks a bit confusing. isUnreachable is only set to true once inside the while loop, where we break from it. I think it maybe better to separate the while loop into another function/lambda such as bool isBranchUnreachable() and change all the breaks into return false. This way it is easier to read when you have more cases for unreachable branches.

test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll

4

Also, if there are any test cases that the current code will not catch, it will be good to add those. This will help future developers on what would be good cases to work on.

[Abhilash]

Hi Michael and Anna,

All the suggested changes have been incorporated.
The testcase now includes CHECK patterns.
The patterns to be checked are kept as minimal as possible.

Thanks,
Abhilash

[anna]

lib/Transforms/Scalar/LoopUnswitch.cpp

510

Prior diff question:
Isn't it enough to check if the basic block UnreachableSucc dominates I->getParent()?
i.e. `DT->dominates(UnreachableSucc, BB).
Is there something else subtle here, that I'm missing?
IIUC, the algorithm keeps traversing backwards to an immediate dominator of the current DomBB, and checks if it's an unreachable block.

512

Is this clang-formatted? I think single statements within if-conditions dont need braces.

[mzolotukhin]

Hi Abhilash,

Please find some stylistic comments from me as well.

Thanks,
Michael

lib/Transforms/Scalar/LoopUnswitch.cpp

488

Please rename this function, as the name is to generic now, and LLVM already uses term unreachable with another meaning. Here the block is rendered unreachable because we unswitched some conditional branches - we should somehow reflect that in the name (I don't have good suggestions though :) ).

512

I think clang-format doesn't remove such braces, but yep, we don't need them in this case.

test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll

3–4

Why do we need -sroa? Why can't we use its output?

Also, if we do check the actual contents of the function, there is no need in checking debug messages, and thus we can remove first RUN invocation and REQUIRES: asserts.

9–13

Some more recommendations about tests:

1. Run opt -instnamer on the test so that names like %7 are replaced with symbolic names. It makes it much easier to edit the test later if necessary (we need to preserve numeration if we don't use symbolic names).
2. Please add CHECK-LABEL: @b. That'll help to distinguish function bodies in case someone adds another function into this test.
3. It might be an overkill to check every instruction. It's usually enough to check key instructions in key blocks. E.g.:

; CHECK: bb1:
; CHECK-NOT br i1      ; Check that the branch is not conditional any more
; CHECK: br label %succ ; Check that we're unconditionally jumping to correct successor

And we don't need to check what's in between label bb1 and branch from the block. This way it's easier to understand what the test checks, and also the test becomes more robust to random change that can somehow change the bodies of the blocks.

[Abhilash]

Hi Anna and Michael Zolothukin,

I have renamed the function and reduced the CHECK patterns in the testcase.
I have tried to keep the CHECK patterns generic.
I have retained the CHECK patterns for only 3 loops (the number of loops that would be generated with this revision) and the corresponding phi nodes at the exit (join) nodes.

One help: Is there a way to make the phi-nodes (in the CHECK pattern) more generic?

Thanks,
Abhilash

[mzolotukhin]

Hi Abhilash,

The change looks good to me now, thank you! Regarding phis - I would probably just check how many operands the phi-instruction has, without explicit specifying the operands (if it doesn't make the regex much easier, then it's ok to keep it as you have it now I think). Thanks for your patience in going through so many iterations of review! :)

Michael

[anna]

Hi Abhilash, Michael,

One small suggestion inline from my side.

Thanks,
Anna

lib/Transforms/Scalar/LoopUnswitch.cpp

509

I was thinking of this signature in DominatorTree:
dominates(BasicBlock*, BasicBlock*).
So, the above changes to: DT->dominates(UnreachableSucc, BB).

For other such usages, take a look in LoopUnswitch::RewriteLoopBodyWithConditionConstant function.

if (Latch && DT->dominates(SISucc, Latch))

SISucc and Latch are both basic blocks.

For more clarification, check out Dominator class:
class DominatorTree : public DominatorTreeBase<BasicBlock>. The templatized NodeT is a basic block.

[Abhilash]

Hi Anna,

All this time, I have misunderstood your comment. Please find the changes incorporated.

Thanks,
Abhilash

[Abhilash]

In D26299#601308, @mzolotukhin wrote:

Hi Abhilash,

The change looks good to me now, thank you! Regarding phis - I would probably just check how many operands the phi-instruction has, without explicit specifying the operands (if it doesn't make the regex much easier, then it's ok to keep it as you have it now I think). Thanks for your patience in going through so many iterations of review! :)

Michael

Thank you Michael. It's a learning phase for me.

---

Abhilash

lib/Transforms/Scalar/LoopUnswitch.cpp

510

I have rectified this in the latest revision.

638

The nullptr initialization is no longer required and hence has been removed.

640

No. The code just identifies the unreachable successors.
After unswitching, some of the branch conditions may just be constants (True/false). If the condition is true, then the else (false) path is unreachable and otherwise.
All the branches that are unreachable (because of previous unswitching) should not be considered for further unswitching. The code filters out such unreachable conditions.

649–650

The change has been incorporated.

[anna]

great Abhilash, the changes look good to me. Thanks for taking this to completion :)

lib/Transforms/Scalar/LoopUnswitch.cpp

explicit LoopUnswitch(bool Os = false) :
       LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
       currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
       loopPreheader(nullptr) {
         initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
       }
 
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
     bool processCurrentLoop();
-
+    bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG.
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<AssumptionCacheTracker>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
       getLoopAnalysisUsage(AU);
     }
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   } while(redoLoop);
 
   // FIXME: Reconstruct dom info, because it is not preserved properly.
   if (Changed)
     DT->recalculate(*F);
   return Changed;
 }
 
+// Return true if the BasicBlock BB is unreachable from the loop header.
+// Return false, otherwise.
+bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
+  auto *Node = DT->getNode(BB)->getIDom();
+  BasicBlock *DomBB = Node->getBlock();
+  while (currentLoop->contains(DomBB)) {
+    BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator());
+
+    Node = DT->getNode(DomBB)->getIDom();
+    DomBB = Node->getBlock();
+
+    if (!BInst || !BInst->isConditional())
+      continue;
+
+    Value *Cond = BInst->getCondition();
+    if (!isa<ConstantInt>(Cond))
+      continue;
+
+    BasicBlock *UnreachableSucc =
+        Cond == ConstantInt::getTrue(Cond->getContext())
+            ? BInst->getSuccessor(1)
+            : BInst->getSuccessor(0);
+
+    if (DT->dominates(DT->getNode(UnreachableSucc), DT->getNode(BB)))
+      return true;
+  }
+  return false;
+}
+
 /// Do actual work and unswitch loop if possible and profitable.
 bool LoopUnswitch::processCurrentLoop() {
   bool Changed = false;
 
   initLoopData();
 
   // If LoopSimplify was unable to form a preheader, don't do any unswitching.
   if (!loopPreheader)
for (Loop::block_iterator I = currentLoop->block_begin(),
     // guaranteed to execute, to avoid creating a use-of-uninitialized-value
     // in the code that did not have one.
     // This is a workaround for the discrepancy between LLVM IR and MSan
     // semantics. See PR28054 for more details.
     if (SanitizeMemory &&
         !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
       continue;
 
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+      // Some branches may be rendered unreachable because of previous
+      // unswitching.
+      // Unswitch only those branches that are reachable.
+      if (isUnreachableDueToPreviousUnswitching(*I))
+        continue;
+ 
       // If this isn't branching on an invariant condition, we can't unswitch
       // it.
       if (BI->isConditional()) {
         // See if this, or some part of it, is loop invariant.  If so, we can
         // unswitch on it if we desire.
         Value *LoopCond = FindLIVLoopCondition(BI->getCondition(),
                                                currentLoop, Changed);
         if (LoopCond &&
             UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) {
           ++NumBranches;
           return true;
         }
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       Value *LoopCond = FindLIVLoopCondition(SI->getCondition(),
                                              currentLoop, Changed);
       unsigned NumCases = SI->getNumCases();
       if (LoopCond && NumCases) {
         // Find a value to unswitch on:
         // FIXME: this should chose the most expensive case!
         // FIXME: scan for a case with a non-critical edge?
         Constant *UnswitchVal = nullptr;
 
         // Do not process same value again and again.
         // At this point we have some cases already unswitched and
         // some not yet unswitched. Let's find the first not yet unswitched one.
         for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
              i != e; ++i) {
           Constant *UnswitchValCandidate = i.getCaseValue();
           if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
             UnswitchVal = UnswitchValCandidate;
             break;
           }
         }
 
         if (!UnswitchVal)
           continue;
 

test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll

+; RUN: opt -loop-unswitch -S - < %s | FileCheck %s
+
+;CHECK-LABEL: @b
+;CHECK: [[Loop1:for\.end.*]]:                              ; preds = %for.cond.us
+;CHECK-NEXT:  %[[PhiVar1:pdt.*]] = phi i32 [ %pdt.0.us, %for.cond.us ]
+;CHECK: [[Loop2:for\.end.*]]:                     ; preds = %for.cond.us1
+;CHECK-NEXT:  %[[PhiVar2:pdt.*]] = phi i32 [ %pdt.0.us2, %for.cond.us1 ]
+;CHECK: [[Loop3:for\.end.*]]:                        ; preds = %for.cond
+;CHECK-NEXT:  %[[PhiVar3:pdt.*]] = phi i32 [ %pdt.0, %for.cond ]
+;CHECK: [[Join1:for\.end.*]]:                                 ; preds = %[[Loop2]], %[[Loop3]]
+;CHECK-NEXT:  %[[PhiRes1:pdt.*]] = phi i32 [ %[[PhiVar3]], %[[Loop3]] ], [ %[[PhiVar2]], %[[Loop2]] ]
+;CHECK: for.end:                                          ; preds = %[[Loop1]], %[[Join1]]
+;CHECK-NEXT:  %[[PhiRes2:pdt.*]] = phi i32 [ %[[PhiRes1]], %[[Join1]] ], [ %[[PhiVar1]], %[[Loop1]] ]
+;CHECK-NEXT:  ret i32 %[[PhiRes2]]
+
+; Function Attrs: nounwind uwtable
+define i32 @b(i32 %x, i32 %y) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %pdt.0 = phi i32 [ 1, %entry ], [ %pdt.2, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 100
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tobool = icmp ne i32 %x, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  %mul = mul nsw i32 %pdt.0, 2
+  br label %if.end6
+
+if.else:                                          ; preds = %for.body
+  %tobool1 = icmp ne i32 %y, 0
+  br i1 %tobool1, label %if.then2, label %if.else4
+
+if.then2:                                         ; preds = %if.else
+  %mul3 = mul nsw i32 %pdt.0, 3
+  br label %if.end
+
+if.else4:                                         ; preds = %if.else
+  %mul5 = mul nsw i32 %pdt.0, 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else4, %if.then2
+  %pdt.1 = phi i32 [ %mul3, %if.then2 ], [ %mul5, %if.else4 ]
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.end, %if.then
+  %pdt.2 = phi i32 [ %mul, %if.then ], [ %pdt.1, %if.end ]
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end6
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %pdt.0
+}
+