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

921

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

927

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

[trentxintong]

lib/Transforms/Scalar/LoopUnswitch.cpp

921

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.

927

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

930

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

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)) {
+      // At this point, any constant-foldable instructions should have probably
+      // been folded.
+      ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
+      if (!Cond)
+        break;
+      // Find the target block we are definitely going to.
+      CurrentBB = SI->findCaseValue(Cond).getCaseSuccessor();
+    } else { 
+      // We do not understand these 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.
   Constant *CondVal = nullptr;
   BasicBlock *LoopExitBB = nullptr;
 
   if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) {
     // If this isn't branching on an invariant condition, we can't unswitch it.
     if (!BI->isConditional())
       return false;
 

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 will not be able trivially unswitch on the SwitchInst, as its input
+; is a constant. However, since its a constant 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 loop has been unswitched on %cond1.
+; 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) {
+  br label %loop_begin
+
+loop_begin:  
+  switch i32 1, 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