Constant fold switch inst when looking for trivial conditions to unswitch on.

[trentxintong]

Summary

Constant fold switch inst when looking for trivial conditions to unswitch on.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

922

Is this likely to actually do anything in practice...? Most passes (including LoopUnswitch itself) will constant-fold newly generated code.

928

Checking for a Constant isn't good enough here: you need a ConstantInt.

[trentxintong]

lib/Transforms/Scalar/LoopUnswitch.cpp

922

I agree that the constants probably have been folded at this point. The only constants remaining are likely to be the ones generated by unswitching (Even those ones are likely to be folded away by SimplifyCode in LoopUnswitch) or maybe we have some pass ordering problems.

I am fine dropping the ConstantFoldInstruction, as this does add some compilation time to the pass.

928

Yes, this has to be a constant int of abitrary width.

[trentxintong]

Address comments.

[trentxintong]

After thinking about it. I decided to drop the constant-folding as they are not trivially cheap.
Especially at this point, they have probably been folded away, the ones remaining probably can
not be folded anyways.

[trentxintong]

Friendly ping.

[trentxintong]

@efriedma Does this look OK now ? Thanks.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

931

Can you use SwitchInst::findCaseValue rather than an explicit loop?

[trentxintong]

Address comments.

[efriedma]

LGTM.

[trentxintong]

@efriedma Thanks for the review!

lib/Transforms/Scalar/LoopUnswitch.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
while (true) {
 
     // Check if this loop will execute any side-effecting instructions (e.g.
     // stores, calls, volatile loads) in the part of the loop that the code
     // *would* execute. Check the header first.
     for (Instruction &I : *CurrentBB)
       if (I.mayHaveSideEffects())
         return false;
 
-    // FIXME: add check for constant foldable switch instructions.
     if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
       if (BI->isUnconditional()) {
         CurrentBB = BI->getSuccessor(0);
       } else if (BI->getCondition() == ConstantInt::getTrue(Context)) {
         CurrentBB = BI->getSuccessor(0);
       } else if (BI->getCondition() == ConstantInt::getFalse(Context)) {
         CurrentBB = BI->getSuccessor(1);
       } else {
         // Found a trivial condition candidate: non-foldable conditional branch.
         break;
       }
-    } else {
+    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
+      // Either the Cond is a constant or we try to fold it into a constant.
+      Value *Cond = SI->getCondition();
+      if (!isa<Constant>(Cond)) {
+        Instruction *I = dyn_cast<Instruction>(Cond);
+        if (!I)
+          break;
+        const DataLayout &DL = I->getModule()->getDataLayout();
+        if (Constant *Fold = ConstantFoldInstruction(I, DL))
+          Cond = Fold;
+        else 
+          break;
+      }
+      // At this point, the switched value is a constant int.
+      assert(isa<ConstantInt>(Cond) && "Switched value must be a constant");
+      bool FoundDest = false;
+      for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
+           i != e; ++i) {
+        // The case value should have the same type as the switched value.
+        assert(i.getCaseValue()->getType() == Cond->getType() &&
+               "Switched value has different types as the case value");
+        if (Cond == i.getCaseValue()) {
+          CurrentBB = i.getCaseSuccessor();
+          FoundDest = true;
+          break;
+        }
+      }
+      // The default case is taken.
+      if (!FoundDest)
+        CurrentBB = SI->getDefaultDest();
+    } else { 
+      // We do not understand this terminator instructions.
       break;
     }
 
     CurrentTerm = CurrentBB->getTerminator();
   }
 
   // CondVal is the condition that controls the trivial condition.
   // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.

test/Transforms/LoopUnswitch/trivial-unswitch.ll

 do_something:
   call void @some_func() noreturn nounwind
   br label %loop_begin
 
 loop_exit:
   ret i32 0
 }
 
-declare void @some_func() noreturn
+
+; We should not trivially unswitch on the SwitchInst. Instead, we
+; should be able to figure out that the switch can be folded into
+; a unconditional branch to %continue. Then we unswitch on the br
+; inst in %continue.
+;
+; CHECK: define i32 @test2(
+
+; This is an indication that the SwitchInst is unswitched upon,
+; i.e. an ICmpInst is generated by the EmitPreheaderBranchOnCondition
+; on the unswitched case value which leads to a trivial loop exit.
+;
+; CHECK-NOT: icmp
+; CHECK:  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge
+
+; CHECK:  ..split_crit_edge:                                ; preds = %0
+; CHECK:    br label %.split
+
+; CHECK:  .split:                                           ; preds = %..split_crit_edge
+; CHECK:    br label %loop_begin
+
+; CHECK:  loop_begin:                                       ; preds = %do_something, %.split
+; CHECK:    switch i32
+
+; CHECK:  continue:                                         ; preds = %loop_begin
+; CHECK:    %var_val = load i32, i32* %var
+; CHECK:    br i1 true, label %do_something, label %loop_exit
+
+define i32 @test2(i32* %var, i1 %cond1) {
+  %sub = sub i32 6, 5 
+  br label %loop_begin
+
+loop_begin:  
+  switch i32 %sub, label %continue [
+    i32 0, label %loop_exit
+    i32 1, label %continue
+  ]
+
+continue:
+  %var_val = load i32, i32* %var
+  br i1 %cond1, label %do_something, label %loop_exit
+
+do_something:
+  call void @some_func() noreturn nounwind
+  br label %loop_begin
+
+loop_exit:
+  ret i32 0
+}
+
+declare void @some_func() noreturn