From 9683f181746c2312c8828c79b6e25a07fb441d57 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Fri, 19 Jun 2009 04:56:29 +0000 Subject: Teach jump threading to look at comparisons between phi nodes and non-constants. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@73755 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/JumpThreading.cpp | 73 ++++++++++++++++++++++----------- 1 file changed, 48 insertions(+), 25 deletions(-) (limited to 'lib/Transforms') diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index c0ca2df..ed84ec1 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -76,7 +76,7 @@ namespace { bool ProcessBlock(BasicBlock *BB); bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB, unsigned JumpThreadCost); - BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal); + BasicBlock *FactorCommonPHIPreds(PHINode *PN, Value *Val); bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); @@ -163,10 +163,10 @@ void JumpThreading::FindLoopHeaders(Function &F) { /// This is important for things like "phi i1 [true, true, false, true, x]" /// where we only need to clone the block for the true blocks once. /// -BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Constant *CstVal) { +BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Value *Val) { SmallVector CommonPreds; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingValue(i) == CstVal) + if (PN->getIncomingValue(i) == Val) CommonPreds.push_back(PN->getIncomingBlock(i)); if (CommonPreds.size() == 1) @@ -346,13 +346,19 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { CondInst->getOpcode() == Instruction::And)) return true; - // If we have "br (phi != 42)" and the phi node has any constant values as - // operands, we can thread through this block. - if (CmpInst *CondCmp = dyn_cast(CondInst)) - if (isa(CondCmp->getOperand(0)) && - isa(CondCmp->getOperand(1)) && - ProcessBranchOnCompare(CondCmp, BB)) - return true; + if (CmpInst *CondCmp = dyn_cast(CondInst)) { + if (isa(CondCmp->getOperand(0))) { + // If we have "br (phi != 42)" and the phi node has any constant values + // as operands, we can thread through this block. + // + // If we have "br (cmp phi, x)" and the phi node contains x such that the + // comparison uniquely identifies the branch target, we can thread + // through this block. + + if (ProcessBranchOnCompare(CondCmp, BB)) + return true; + } + } // 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 @@ -770,12 +776,30 @@ bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB, return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost); } +/// GetResultOfComparison - Given an icmp/fcmp predicate and the left and right +/// hand sides of the compare instruction, try to determine the result. If the +/// result can not be determined, a null pointer is returned. +static Constant *GetResultOfComparison(CmpInst::Predicate pred, + Value *LHS, Value *RHS) { + if (Constant *CLHS = dyn_cast(LHS)) + if (Constant *CRHS = dyn_cast(RHS)) + return ConstantExpr::getCompare(pred, CLHS, CRHS); + + if (LHS == RHS) + if (isa(LHS->getType()) || isa(LHS->getType())) + return ICmpInst::isTrueWhenEqual(pred) ? + ConstantInt::getTrue() : ConstantInt::getFalse(); + + return 0; +} + /// ProcessBranchOnCompare - We found a branch on a comparison between a phi -/// node and a constant. If the PHI node contains any constants as inputs, we -/// can fold the compare for that edge and thread through it. +/// node and a value. If we can identify when the comparison is true between +/// the phi inputs and the value, we can fold the compare for that edge and +/// thread through it. bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { PHINode *PN = cast(Cmp->getOperand(0)); - Constant *RHS = cast(Cmp->getOperand(1)); + Value *RHS = Cmp->getOperand(1); // If the phi isn't in the current block, an incoming edge to this block // doesn't control the destination. @@ -784,18 +808,17 @@ bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { // We can do this simplification if any comparisons fold to true or false. // See if any do. - Constant *PredCst = 0; + Value *PredVal = 0; bool TrueDirection = false; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - PredCst = dyn_cast(PN->getIncomingValue(i)); - if (PredCst == 0) continue; + PredVal = PN->getIncomingValue(i); + + Constant *Res = GetResultOfComparison(Cmp->getPredicate(), PredVal, RHS); + if (!Res) { + PredVal = 0; + continue; + } - Constant *Res; - if (ICmpInst *ICI = dyn_cast(Cmp)) - Res = ConstantExpr::getICmp(ICI->getPredicate(), PredCst, RHS); - else - Res = ConstantExpr::getFCmp(cast(Cmp)->getPredicate(), - PredCst, RHS); // If this folded to a constant expr, we can't do anything. if (ConstantInt *ResC = dyn_cast(Res)) { TrueDirection = ResC->getZExtValue(); @@ -808,11 +831,11 @@ bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { } // Otherwise, we can't fold this input. - PredCst = 0; + PredVal = 0; } // If no match, bail out. - if (PredCst == 0) + if (PredVal == 0) return false; // See if the cost of duplicating this block is low enough. @@ -825,7 +848,7 @@ bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) { // If so, we can actually do this threading. Merge any common predecessors // that will act the same. - BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredCst); + BasicBlock *PredBB = FactorCommonPHIPreds(PN, PredVal); // Next, get our successor. BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection); -- cgit v1.1