Simplify conditional branch on constant condition and remove unreachable blocks in LoopUnswitch.

[trentxintong]

Summary

we can turn the branch with const condition into a unconditional branch.

With this transformation, we can then run a dead block deletion algorithm to remove
unreachable blocks in the loop.

This is useful as the next time we unswitch this loop, we will have fewer
blocks to duplicate and fewer instructions to remap, etc.

This should also give us a better idea of the real unswitch cost of the
loop (even though we still cant use this information right now).

Additionally, its good for us to clean up as soon as possible in loop unswitch,
otherwise we duplicate a lot of dead code which need to be cleaned up by
later passes, this is suboptimal as this leads to more compilation time.

Note: I have not fixed all the LIT tests yet. There are quite a number of them to FIX.
I will upload again again once I fix them. Would like for people to take a look first
while I work on fixing the tests.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

1374

See the comment near the beginning of LoopUnswitch::TryTrivialLoopUnswitch for a description of all the state you aren't updating correctly.

Also, I think you meant "isa<ConstantInt>(BI->getCondition())".

[trentxintong]

lib/Transforms/Scalar/LoopUnswitch.cpp

1374

Thanks @efriedma. In llvm, a change in CFG like this, do we usually expect to update the dominator tree dynamic/manually or we are ok with DT->recalculate.

[efriedma]

lib/Transforms/Scalar/LoopUnswitch.cpp

1374

LoopUnswitch already calls DT->recalculate... but only once loop, and only if we unswitched that loop. In theory, doing it that way is O(N^2) in the number of loops in the function (since DT->recalculate scans the whole function), so it's something we should fix at some point, it doesn't seem to cause issues in practice. If you want to call it more frequently than that, it could lead to problems.

[davidxl]

Do you see missed optimizations without the on-the-fly CFG cleanup or is it just for compile time improvement? Do you have data on the impact of compile time with this patch?

lib/Transforms/Scalar/LoopUnswitch.cpp

private:
 
     void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                         BasicBlock *TrueDest,
                                         BasicBlock *FalseDest,
                                         Instruction *InsertPt,
                                         TerminatorInst *TI);
 
     void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
+    // Remove all the unreachable blocks in the loop, such that they do not
+    // get duplicated the next time the loop is unswitched.
+    void RemoveUnreachableBlocksInLoop(Loop *L);
   };
 }
 
 // Analyze loop. Check its size, calculate is it possible to unswitch
 // it. Returns true if we can unswitch this loop.
 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
                                 AssumptionCache *AC) {
 
for (User *U : LIC->users()) {
         continue;
       Worklist.push_back(UI);
     }
 
     for (Instruction *UI : Worklist)
       UI->replaceUsesOfWith(LIC, Replacement);
 
     SimplifyCode(Worklist, L);
+    RemoveUnreachableBlocksInLoop(L);
     return;
   }
 
   // Otherwise, we don't know the precise value of LIC, but we do know that it
   // is certainly NOT "Val".  As such, simplify any uses in the loop that we
   // can.  This case occurs when we unswitch switch statements.
   for (User *U : LIC->users()) {
     Instruction *UI = dyn_cast<Instruction>(U);
for (User *U : LIC->users()) {
     // Tell the domtree about the new block. We don't fully update the
     // domtree here -- instead we force it to do a full recomputation
     // after the pass is complete -- but we do need to inform it of
     // new blocks.
     DT->addNewBlock(Abort, NewSISucc);
   }
 
   SimplifyCode(Worklist, L);
+  RemoveUnreachableBlocksInLoop(L);
 }
 
 /// Now that we have simplified some instructions in the loop, walk over it and
 /// constant prop, dce, and fold control flow where possible. Note that this is
 /// effectively a very simple loop-structure-aware optimizer. During processing
 /// of this loop, L could very well be deleted, so it must not be used.
 ///
 /// FIXME: When the loop optimizer is more mature, separate this out to a new
while (!Worklist.empty()) {
     if (Value *V = SimplifyInstruction(I, DL))
       if (LI->replacementPreservesLCSSAForm(I, V)) {
         ReplaceUsesOfWith(I, V, Worklist, L, LPM);
         continue;
       }
 
     // Special case hacks that appear commonly in unswitched code.
     if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
+      // Try to simplify conditional branches to unconditional branches.
+      if (BI->isConditional() && isa<Constant>(BI->getCondition())) {
+        BranchInst *NBI = BranchInst::Create(BI->getCondition() ==
+                                             ConstantInt::getTrue(BI->getContext()) ?
+                                             BI->getSuccessor(0) :
+                                             BI->getSuccessor(1), BI);
+        RemoveFromWorklist(BI, Worklist);
+        BI->eraseFromParent();
+        Worklist.push_back(NBI);
+      }
       if (BI->isUnconditional()) {
         // If BI's parent is the only pred of the successor, fold the two blocks
         // together.
         BasicBlock *Pred = BI->getParent();
         BasicBlock *Succ = BI->getSuccessor(0);
         BasicBlock *SinglePred = Succ->getSinglePredecessor();
         if (!SinglePred) continue;  // Nothing to do.
         assert(SinglePred == Pred && "CFG broken");
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
         ++NumSimplify;
         continue;
       }
 
       continue;
     }
   }
 }
+
+void LoopUnswitch::RemoveUnreachableBlocksInLoop(Loop *L) {
+  // Run a simple dead block elimination algorithm which assumes every
+  // block except the header is initially dead.
+  SmallVector<BasicBlock *, 8> Worklist;
+  SmallPtrSet<BasicBlock *, 8> DeadBlocks(L->block_begin(), L->block_end());
+
+  // No blocks (other than the header) in this loop shall have predecessors
+  // that are not in the loop, as this is not valid for natural loops. This can
+  // can occur if the blocks are unreachable. Hopefully LoopSimplify has
+  // deleted them. Its still OK if they exist.
+  DeadBlocks.erase(L->getHeader());
+  Worklist.push_back(L->getHeader());
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.back();
+    Worklist.pop_back();
+    for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
+      if (!DeadBlocks.count(*I))
+        continue;
+      // This block becomes alive.
+      DeadBlocks.erase(*I);
+      Worklist.push_back(*I);
+    }
+  }
+
+  // Remove the blocks that are unreachable in the loop.
+  for (BasicBlock *BB : DeadBlocks) {
+     LI->removeBlock(BB);
+     LPM->deleteSimpleAnalysisValue(BB, L);
+     BB->eraseFromParent();
+  }
+}

test/Transforms/LoopUnswitch/trivial-unswitch.ll

 ; CHECK:    br i1 %cond2, label %.split..split.split_crit_edge, label %.split.loop_exit.split1_crit_edge
 
 ; CHECK:  .split..split.split_crit_edge:                    ; preds = %.split
 ; CHECK:    br label %.split.split
 
 ; CHECK:  .split.split:                                     ; preds = %.split..split.split_crit_edge
 ; CHECK:    br label %loop_begin
 
-; CHECK:  loop_begin:                                       ; preds = %do_something, %.split.split
-; CHECK:    br i1 true, label %continue, label %loop_exit
-
-; CHECK:  continue:                                         ; preds = %loop_begin
+; CHECK:  loop_begin:                                       ; preds = %loop_begin, %.split.split
 ; CHECK:    %var_val = load i32, i32* %var
-; CHECK:    br i1 true, label %do_something, label %loop_exit
+; CHECK:    call void @some_func() #1
+; CHECK:    br label %loop_begin
 
 define i32 @test(i32* %var, i1 %cond1, i1 %cond2) {
   br label %loop_begin
 
 loop_begin:  
   br i1 %cond1, label %continue, label %loop_exit  ; first trivial condition
 
 continue:
   %var_val = load i32, i32* %var
   br i1 %cond2, label %do_something, label %loop_exit  ; second trivial condition  
 
 do_something:
   call void @some_func() noreturn nounwind
   br label %loop_begin
 
 loop_exit:
   ret i32 0
 }
 
-declare void @some_func() noreturn
+declare void @some_func() noreturn