Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -210,7 +210,7 @@ bool runOnLoop(Loop *L, LPPassManager &LPM) override; bool processCurrentLoop(); - + bool isUnreachable(BasicBlock *); /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG. /// @@ -483,6 +483,37 @@ return Changed; } +// Return true if the BasicBlock BB is unreachable from the loop header. +// Return false, otherwise. +bool LoopUnswitch::isUnreachable(BasicBlock *BB) { + auto *Node = DT->getNode(BB)->getIDom(); + BasicBlock *DomBB = Node->getBlock(); + while (currentLoop->contains(DomBB)) { + BranchInst *BInst = dyn_cast(DomBB->getTerminator()); + + Node = DT->getNode(DomBB)->getIDom(); + DomBB = Node->getBlock(); + + if (!BInst || !BInst->isConditional()) + continue; + + Value *Cond = BInst->getCondition(); + if (!isa(Cond)) + continue; + + BasicBlock *UnreachableSucc = + Cond == ConstantInt::getTrue(Cond->getContext()) + ? BInst->getSuccessor(1) + : BInst->getSuccessor(0); + + BasicBlockEdge UnreachableEdge(BInst->getParent(), UnreachableSucc); + if (DT->dominates(UnreachableEdge, BB)) { + return true; + } + } + return false; +} + /// Do actual work and unswitch loop if possible and profitable. bool LoopUnswitch::processCurrentLoop() { bool Changed = false; @@ -593,6 +624,12 @@ continue; if (BranchInst *BI = dyn_cast(TI)) { + // Some branches may be rendered unreachable because of previous + // unswitching. + // Unswitch only those branches that are reachable. + if (isUnreachable(*I)) + continue; + // If this isn't branching on an invariant condition, we can't unswitch // it. if (BI->isConditional()) { Index: test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll @@ -0,0 +1,98 @@ +; REQUIRES: asserts +; RUN: opt -sroa -loop-unswitch -stats -disable-output -info-output-file - < %s | FileCheck --check-prefix=STATS %s +; RUN: opt -sroa -loop-unswitch -S < %s | FileCheck %s + +; STATS: 2 loop-unswitch - Number of branches unswitched + + +; CHECK: for.cond.us: ; preds = %for.inc.us, %entry.split.us +; CHECK-NEXT: %pdt.0.us = phi i32 [ 1, %entry.split.us ], [ %pdt.2.us, %for.inc.us ] +; CHECK-NEXT: %i.0.us = phi i32 [ 0, %entry.split.us ], [ %inc.us, %for.inc.us ] +; CHECK-NEXT: %cmp.us = icmp slt i32 %i.0.us, 100 +; CHECK-NEXT: br i1 %cmp.us, label %for.body.us, label %for.end.us-lcssa.us +; CHECK: for.end.us-lcssa.us: ; preds = %for.cond.us +; CHECK-NEXT: %pdt.0.lcssa.ph.us = phi i32 [ %pdt.0.us, %for.cond.us ] +; CHECK-NEXT: br label %for.end +; CHECK: for.cond.us5: ; preds = %for.inc.us21, %entry.split.split.us +; CHECK-NEXT: %pdt.0.us6 = phi i32 [ 1, %entry.split.split.us ], [ %pdt.2.us20, %for.inc.us21 ] +; CHECK-NEXT: %i.0.us7 = phi i32 [ 0, %entry.split.split.us ], [ %inc.us22, %for.inc.us21 ] +; CHECK-NEXT: %cmp.us8 = icmp slt i32 %i.0.us7, 100 +; CHECK-NEXT: br i1 %cmp.us8, label %for.body.us9, label %for.end.us-lcssa.us-lcssa.us +; CHECK: for.end.us-lcssa.us-lcssa.us: ; preds = %for.cond.us5 +; CHECK-NEXT: %pdt.0.lcssa.ph.ph.us = phi i32 [ %pdt.0.us6, %for.cond.us5 ] +; CHECK-NEXT: br label %for.end.us-lcssa +; CHECK: for.cond: ; preds = %for.inc, %entry.split.split +; CHECK-NEXT: %pdt.0 = phi i32 [ 1, %entry.split.split ], [ %pdt.2, %for.inc ] +; CHECK-NEXT: %i.0 = phi i32 [ 0, %entry.split.split ], [ %inc, %for.inc ] +; CHECK-NEXT: %cmp = icmp slt i32 %i.0, 100 +; CHECK-NEXT: br i1 %cmp, label %for.body, label %for.end.us-lcssa.us-lcssa +; CHECK: for.end.us-lcssa: ; preds = %for.end.us-lcssa.us-lcssa.us, %for.end.us-lcssa.us-lcssa +; CHECK-NEXT: %pdt.0.lcssa.ph = phi i32 [ %pdt.0.lcssa.ph.ph, %for.end.us-lcssa.us-lcssa ], [ %pdt.0.lcssa.ph.ph.us, %for.end.us-lcssa.us-lcssa.us ] +; CHECK-NEXT: br label %for.end +; CHECK: for.end: ; preds = %for.end.us-lcssa.us, %for.end.us-lcssa +; CHECK-NEXT: %pdt.0.lcssa = phi i32 [ %pdt.0.lcssa.ph, %for.end.us-lcssa ], [ %pdt.0.lcssa.ph.us, %for.end.us-lcssa.us ] +; CHECK-NEXT: ret i32 %pdt.0.lcssa + +; Function Attrs: nounwind uwtable +define i32 @b(i32 %x, i32 %y) #0 { +entry: + %x.addr = alloca i32, align 4 + %y.addr = alloca i32, align 4 + %pdt = alloca i32, align 4 + %i = alloca i32, align 4 + store i32 %x, i32* %x.addr, align 4 + store i32 %y, i32* %y.addr, align 4 + store i32 1, i32* %pdt, align 4 + store i32 0, i32* %i, align 4 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %0 = load i32, i32* %i, align 4 + %cmp = icmp slt i32 %0, 100 + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %1 = load i32, i32* %x.addr, align 4 + %tobool = icmp ne i32 %1, 0 + br i1 %tobool, label %if.then, label %if.else + +if.then: ; preds = %for.body + %2 = load i32, i32* %pdt, align 4 + %mul = mul nsw i32 %2, 2 + store i32 %mul, i32* %pdt, align 4 + br label %if.end6 + +if.else: ; preds = %for.body + %3 = load i32, i32* %y.addr, align 4 + %tobool1 = icmp ne i32 %3, 0 + br i1 %tobool1, label %if.then2, label %if.else4 + +if.then2: ; preds = %if.else + %4 = load i32, i32* %pdt, align 4 + %mul3 = mul nsw i32 %4, 3 + store i32 %mul3, i32* %pdt, align 4 + br label %if.end + +if.else4: ; preds = %if.else + %5 = load i32, i32* %pdt, align 4 + %mul5 = mul nsw i32 %5, 4 + store i32 %mul5, i32* %pdt, align 4 + br label %if.end + +if.end: ; preds = %if.else4, %if.then2 + br label %if.end6 + +if.end6: ; preds = %if.end, %if.then + br label %for.inc + +for.inc: ; preds = %if.end6 + %6 = load i32, i32* %i, align 4 + %inc = add nsw i32 %6, 1 + store i32 %inc, i32* %i, align 4 + br label %for.cond + +for.end: ; preds = %for.cond + %7 = load i32, i32* %pdt, align 4 + ret i32 %7 +} +