Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -459,8 +459,6 @@ AC)) return false; - // Trivial unswitch condition can only occur at loop header basic block because - // that condition needs to control whether or not the loop does anything at all. // Try trivial unswitch first before loop over other basic blocks in the loop. if (TryTrivialLoopUnswitch(Changed)) { return true; @@ -743,31 +741,73 @@ ++NumTrivial; } -/// TryTrivialLoopUnswitch - Check if loop header block's terminator is a trivial -/// unswitch condition: that is, the condition controls whether or not the loop -/// does anything at all (which means it can only occur in loop header). If it is -/// a trivial condition, unswitching produces no code duplications (equivalently, -/// it produces a simpler loop and a new empty loop, which gets deleted). Therefore -/// always unswitch trivial condition. +/// TryTrivialLoopUnswitch - Check if the first non-constant condition from the loop +/// header is a trivial unswitch condition: that is, a condition controls whether +/// or not the loop does anything at all. If it is a trivial condition, unswitching +/// produces no code duplications (equivalently, it produces a simpler loop and a new +/// empty loop, which gets deleted). Therefore always unswitch trivial condition. /// bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { - BasicBlock *Header = currentLoop->getHeader(); - TerminatorInst *HeaderTerm = Header->getTerminator(); - LLVMContext &Context = Header->getContext(); - - // 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 (BasicBlock::iterator I :*Header) - if (I->mayHaveSideEffects()) + BasicBlock *CurrentBB = currentLoop->getHeader(); + TerminatorInst *CurrentTerm = CurrentBB->getTerminator(); + LLVMContext &Context = CurrentBB->getContext(); + + // If loop header has only one reachable successor (currently via an + // unconditional branch or constant foldable conditional branch, but + // should also consider adding constant foldable switch instruction in + // future), we should keep looking for trivial condition candidates in + // the successor as well. Because in theory these successors could be + // fused to loop header block. The reason to not constant fold + // conditions and merge blocks in LoopUnswitch pass is that it could + // potentially break LoopPassManager's invariants. Folding dead branches + // could either eliminate the current loop or make other loops unreachable. + // LCSSA form might also not be preserved after deleting branches. The + // following code keeps traversing loop header's successors until it finds + // the trivial condition candidate (condition that is not a constant). + // Since unswitching generates branches with constant conditions, this + // scenario could be very common in practice. + SmallSet Visited; + + while (true) { + // If we exit loop or reach a previous visited block, then + // we can not reach any trivial condition candidates (unfoldable + // branch instructions or switch instructions) and no unswitch + // can happen. Exit and return false. + if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second) return false; + // 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 (BasicBlock::iterator I : *CurrentBB) + if (I->mayHaveSideEffects()) + return false; + + // FIXME: add check for constant foldable switch instructions. + if (BranchInst *BI = dyn_cast(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 { + 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(HeaderTerm)) { + if (BranchInst *BI = dyn_cast(CurrentTerm)) { // If this isn't branching on an invariant condition, we can't unswitch it. if (!BI->isConditional()) return false; @@ -797,10 +837,10 @@ if (!LoopExitBB || isa(LoopExitBB->begin())) return false; // Can't handle this. - UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, HeaderTerm); + UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, CurrentTerm); ++NumBranches; return true; - } else if (SwitchInst *SI = dyn_cast(HeaderTerm)) { + } else if (SwitchInst *SI = dyn_cast(CurrentTerm)) { // If this isn't switching on an invariant condition, we can't unswitch it. Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop, Changed); Index: test/Transforms/LoopUnswitch/infinite-loop.ll =================================================================== --- test/Transforms/LoopUnswitch/infinite-loop.ll +++ test/Transforms/LoopUnswitch/infinite-loop.ll @@ -9,23 +9,23 @@ ; It can trivially unswitch on the false cas of condition %a though. ; STATS: 2 loop-unswitch - Number of branches unswitched -; STATS: 1 loop-unswitch - Number of unswitches that are trivial +; STATS: 2 loop-unswitch - Number of unswitches that are trivial ; CHECK-LABEL: @func_16( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 %a, label %entry.split, label %abort0.split ; CHECK: entry.split: -; CHECK-NEXT: br i1 %b, label %cond.end.us, label %abort1 +; CHECK-NEXT: br i1 %b, label %cond.end, label %abort1.split -; CHECK: cond.end.us: -; CHECK-NEXT: br label %cond.end.us +; CHECK: cond.end: +; CHECK-NEXT: br label %cond.end ; CHECK: abort0.split: ; CHECK-NEXT: call void @end0() [[NOR_NUW:#[0-9]+]] ; CHECK-NEXT: unreachable -; CHECK: abort1: +; CHECK: abort1.split: ; CHECK-NEXT: call void @end1() [[NOR_NUW]] ; CHECK-NEXT: unreachable Index: test/Transforms/LoopUnswitch/trivial-unswitch.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnswitch/trivial-unswitch.ll @@ -0,0 +1,47 @@ +; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -verify-loop-info -S < %s 2>&1 | FileCheck %s + +; This test contains two trivial unswitch condition in one loop. +; LoopUnswitch pass should be able to unswitch the second one +; after unswitching the first one. + + +; 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 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: %var_val = load i32, i32* %var +; CHECK: br i1 true, label %do_something, label %loop_exit + +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 \ No newline at end of file