Index: include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- include/llvm/Transforms/Scalar/JumpThreading.h +++ include/llvm/Transforms/Scalar/JumpThreading.h @@ -139,7 +139,11 @@ bool ProcessImpliedCondition(BasicBlock *BB); bool SimplifyPartiallyRedundantLoad(LoadInst *LI); + void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, + PHINode *SIUse, unsigned Idx); + bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); + bool TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB); bool TryToUnfoldSelectInCurrBB(BasicBlock *BB); bool ProcessGuards(BasicBlock *BB); Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -1171,6 +1171,9 @@ } } + if (SwitchInst *SI = dyn_cast(BB->getTerminator())) + TryToUnfoldSelect(SI, BB); + // Check for some cases that are worth simplifying. Right now we want to look // for loads that are used by a switch or by the condition for the branch. If // we see one, check to see if it's partially redundant. If so, insert a PHI @@ -2388,6 +2391,72 @@ return true; } +// Pred is a predecessor of BB with an unconditional branch to BB. SI is +// a Select instruction in Pred. BB has other predecessors and SI is used in +// a PHI node in BB. SI has no other use. +// A new basic block, NewBB, is created and SI is converted to compare and +// conditional branch. SI is erased from parent. +void JumpThreadingPass::UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, + SelectInst *SI, PHINode *SIUse, + unsigned Idx) { + // Expand the select. + // + // Pred -- + // | v + // | NewBB + // | | + // |----- + // v + // BB + BranchInst *PredTerm = dyn_cast(Pred->getTerminator()); + BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", + BB->getParent(), BB); + // Move the unconditional branch to NewBB. + PredTerm->removeFromParent(); + NewBB->getInstList().insert(NewBB->end(), PredTerm); + // Create a conditional branch and update PHI nodes. + BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); + SIUse->setIncomingValue(Idx, SI->getFalseValue()); + SIUse->addIncoming(SI->getTrueValue(), NewBB); + + // The select is now dead. + SI->eraseFromParent(); + DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB}, + {DominatorTree::Insert, Pred, NewBB}}); + + // Update any other PHI nodes in BB. + for (BasicBlock::iterator BI = BB->begin(); + PHINode *Phi = dyn_cast(BI); ++BI) + if (Phi != SIUse) + Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB); +} + +bool JumpThreadingPass::TryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB) { + PHINode *CondPHI = dyn_cast(SI->getCondition()); + + if (!CondPHI || CondPHI->getParent() != BB) + return false; + + for (unsigned I = 0, E = CondPHI->getNumIncomingValues(); I != E; ++I) { + BasicBlock *Pred = CondPHI->getIncomingBlock(I); + SelectInst *PredSI = dyn_cast(CondPHI->getIncomingValue(I)); + + // The second and third condition can be potentially relaxed. Currently + // the conditions help to simplify the code and allow us to reuse existing + // code, developed for TryToUnfoldSelect(CmpInst *, BasicBlock *) + if (!PredSI || PredSI->getParent() != Pred || !PredSI->hasOneUse()) + continue; + + BranchInst *PredTerm = dyn_cast(Pred->getTerminator()); + if (!PredTerm || !PredTerm->isUnconditional()) + continue; + + UnfoldSelectInstr(Pred, BB, PredSI, CondPHI, I); + return true; + } + return false; +} + /// TryToUnfoldSelect - Look for blocks of the form /// bb1: /// %a = select @@ -2438,34 +2507,7 @@ if ((LHSFolds != LazyValueInfo::Unknown || RHSFolds != LazyValueInfo::Unknown) && LHSFolds != RHSFolds) { - // Expand the select. - // - // Pred -- - // | v - // | NewBB - // | | - // |----- - // v - // BB - BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", - BB->getParent(), BB); - // Move the unconditional branch to NewBB. - PredTerm->removeFromParent(); - NewBB->getInstList().insert(NewBB->end(), PredTerm); - // Create a conditional branch and update PHI nodes. - BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); - CondLHS->setIncomingValue(I, SI->getFalseValue()); - CondLHS->addIncoming(SI->getTrueValue(), NewBB); - // The select is now dead. - SI->eraseFromParent(); - - DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB}, - {DominatorTree::Insert, Pred, NewBB}}); - // Update any other PHI nodes in BB. - for (BasicBlock::iterator BI = BB->begin(); - PHINode *Phi = dyn_cast(BI); ++BI) - if (Phi != CondLHS) - Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB); + UnfoldSelectInstr(Pred, BB, SI, CondLHS, I); return true; } } Index: test/Transforms/JumpThreading/select.ll =================================================================== --- test/Transforms/JumpThreading/select.ll +++ test/Transforms/JumpThreading/select.ll @@ -363,3 +363,81 @@ ; CHECK: br i1 %cmp13.i, label %.exit, label %cond.false.15.i ; CHECK: br label %.exit } + +; When a select has a constant operand in one branch, and it feeds a phi node +; and the phi node feeds a switch we unfold the select +define void @test_func(i32* nocapture readonly %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %n) local_unnamed_addr #0 { +entry: + br label %for.cond + +for.cond: ; preds = %sw.default, %entry + %i.0 = phi i32 [ 0, %entry ], [ %inc, %sw.default ] + %cmp = icmp slt i32 %i.0, %n + br i1 %cmp, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: ; preds = %for.cond + ret void + +for.body: ; preds = %for.cond + %0 = zext i32 %i.0 to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %0 + %1 = load i32, i32* %arrayidx, align 4 + %cmp1 = icmp eq i32 %1, 4 + br i1 %cmp1, label %land.lhs.true, label %if.end + +land.lhs.true: ; preds = %for.body + %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %0 + %2 = load i32, i32* %arrayidx3, align 4 + %arrayidx5 = getelementptr inbounds i32, i32* %c, i64 %0 + %3 = load i32, i32* %arrayidx5, align 4 + %cmp6 = icmp eq i32 %2, %3 + %spec.select = select i1 %cmp6, i32 2, i32 4 + br label %if.end + +if.end: ; preds = %land.lhs.true, %for.body + %local_var.0 = phi i32 [ %1, %for.body ], [ %spec.select, %land.lhs.true ] + switch i32 %local_var.0, label %sw.default [ + i32 2, label %sw.bb + i32 4, label %sw.bb7 + i32 5, label %sw.bb8 + i32 7, label %sw.bb9 + ] + +sw.bb: ; preds = %if.end + call void @foo() + br label %sw.bb7 + +sw.bb7: ; preds = %if.end, %sw.bb + call void @bar() + br label %sw.bb8 + +sw.bb8: ; preds = %if.end, %sw.bb7 + call void @baz() + br label %sw.bb9 + +sw.bb9: ; preds = %if.end, %sw.bb8 + call void @quux() + br label %sw.default + +sw.default: ; preds = %if.end, %sw.bb9 + call void @baz() + %inc = add nuw nsw i32 %i.0, 1 + br label %for.cond + +; CHECK-LABEL: @test_func( +; CHECK: [[REG:%[0-9]+]] = load +; CHECK-NOT: select +; CHECK: br i1 +; CHECK-NOT: select +; CHECK: br i1 {{.*}}, label [[DEST1:%.*]], label [[DEST2:%.*]] + +; The following line checks existence of a phi node, and makes sure +; it only has one incoming value. To do this, we check every '%'. Note +; that REG and REG2 each contain one '%;. There is another one in the +; beginning of the incoming block name. After that there should be no other '%'. + +; CHECK: [[REG2:%.*]] = phi i32 {{[^%]*}}[[REG]]{{[^%]*%[^%]*}} +; CHECK: switch i32 [[REG2]] +; CHECK: i32 2, label [[DEST1]] +; CHECK: i32 4, label [[DEST2]] +}