X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyCFG.cpp;h=bfc7f4ace73a91f829b0058369d069437b53a1f2;hb=c0adfbb49d674dc04f39536151f05cc6a5e9e5fb;hp=6c34eed13d6d68e1c479b82086d012208633b4d5;hpb=6eac2ba4de0b293a627e20f5ef44d696f410b9dc;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 6c34eed13d6..bfc7f4ace73 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -11,41 +11,45 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "simplifycfg" #include "llvm/Transforms/Utils/Local.h" -#include "llvm/Constants.h" -#include "llvm/DataLayout.h" -#include "llvm/DerivedTypes.h" -#include "llvm/GlobalVariable.h" -#include "llvm/IRBuilder.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/LLVMContext.h" -#include "llvm/MDBuilder.h" -#include "llvm/Metadata.h" -#include "llvm/Module.h" -#include "llvm/Operator.h" -#include "llvm/Type.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Support/CFG.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/ConstantRange.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/MDBuilder.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/NoFolder.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/IR/Type.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/ConstantRange.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/NoFolder.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/TargetTransformInfo.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include -#include #include +#include using namespace llvm; +using namespace PatternMatch; + +#define DEBUG_TYPE "simplifycfg" static cl::opt PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1), @@ -59,8 +63,13 @@ static cl::opt SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block")); +static cl::opt HoistCondStores( + "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), + cl::desc("Hoist conditional stores if an unconditional store precedes")); + STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); +STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)"); STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); STATISTIC(NumSpeculations, "Number of speculative executed instructions"); @@ -82,9 +91,8 @@ namespace { }; class SimplifyCFGOpt { - const DataLayout *const TD; - const TargetTransformInfo *const TTI; - + const TargetTransformInfo &TTI; + const DataLayout *const DL; Value *isValueEqualityComparison(TerminatorInst *TI); BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, std::vector &Cases); @@ -103,8 +111,8 @@ class SimplifyCFGOpt { bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder); public: - SimplifyCFGOpt(const DataLayout *td, const TargetTransformInfo *tti) - : TD(td), TTI(tti) {} + SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout *DL) + : TTI(TTI), DL(DL) {} bool run(BasicBlock *BB); }; } @@ -190,94 +198,7 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); } - -/// GetIfCondition - Given a basic block (BB) with two predecessors (and at -/// least one PHI node in it), check to see if the merge at this block is due -/// to an "if condition". If so, return the boolean condition that determines -/// which entry into BB will be taken. Also, return by references the block -/// that will be entered from if the condition is true, and the block that will -/// be entered if the condition is false. -/// -/// This does no checking to see if the true/false blocks have large or unsavory -/// instructions in them. -static Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, - BasicBlock *&IfFalse) { - PHINode *SomePHI = cast(BB->begin()); - assert(SomePHI->getNumIncomingValues() == 2 && - "Function can only handle blocks with 2 predecessors!"); - BasicBlock *Pred1 = SomePHI->getIncomingBlock(0); - BasicBlock *Pred2 = SomePHI->getIncomingBlock(1); - - // We can only handle branches. Other control flow will be lowered to - // branches if possible anyway. - BranchInst *Pred1Br = dyn_cast(Pred1->getTerminator()); - BranchInst *Pred2Br = dyn_cast(Pred2->getTerminator()); - if (Pred1Br == 0 || Pred2Br == 0) - return 0; - - // Eliminate code duplication by ensuring that Pred1Br is conditional if - // either are. - if (Pred2Br->isConditional()) { - // If both branches are conditional, we don't have an "if statement". In - // reality, we could transform this case, but since the condition will be - // required anyway, we stand no chance of eliminating it, so the xform is - // probably not profitable. - if (Pred1Br->isConditional()) - return 0; - - std::swap(Pred1, Pred2); - std::swap(Pred1Br, Pred2Br); - } - - if (Pred1Br->isConditional()) { - // The only thing we have to watch out for here is to make sure that Pred2 - // doesn't have incoming edges from other blocks. If it does, the condition - // doesn't dominate BB. - if (Pred2->getSinglePredecessor() == 0) - return 0; - - // If we found a conditional branch predecessor, make sure that it branches - // to BB and Pred2Br. If it doesn't, this isn't an "if statement". - if (Pred1Br->getSuccessor(0) == BB && - Pred1Br->getSuccessor(1) == Pred2) { - IfTrue = Pred1; - IfFalse = Pred2; - } else if (Pred1Br->getSuccessor(0) == Pred2 && - Pred1Br->getSuccessor(1) == BB) { - IfTrue = Pred2; - IfFalse = Pred1; - } else { - // We know that one arm of the conditional goes to BB, so the other must - // go somewhere unrelated, and this must not be an "if statement". - return 0; - } - - return Pred1Br->getCondition(); - } - - // Ok, if we got here, both predecessors end with an unconditional branch to - // BB. Don't panic! If both blocks only have a single (identical) - // predecessor, and THAT is a conditional branch, then we're all ok! - BasicBlock *CommonPred = Pred1->getSinglePredecessor(); - if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor()) - return 0; - - // Otherwise, if this is a conditional branch, then we can use it! - BranchInst *BI = dyn_cast(CommonPred->getTerminator()); - if (BI == 0) return 0; - - assert(BI->isConditional() && "Two successors but not conditional?"); - if (BI->getSuccessor(0) == Pred1) { - IfTrue = Pred1; - IfFalse = Pred2; - } else { - IfTrue = Pred2; - IfFalse = Pred1; - } - return BI->getCondition(); -} - -/// ComputeSpeculuationCost - Compute an abstract "cost" of speculating the +/// ComputeSpeculationCost - Compute an abstract "cost" of speculating the /// given instruction, which is assumed to be safe to speculate. 1 means /// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive. static unsigned ComputeSpeculationCost(const User *I) { @@ -292,6 +213,7 @@ static unsigned ComputeSpeculationCost(const User *I) { if (!cast(I)->hasAllConstantIndices()) return UINT_MAX; return 1; + case Instruction::ExtractValue: case Instruction::Load: case Instruction::Add: case Instruction::Sub: @@ -352,12 +274,12 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, // branch to BB, then it must be in the 'conditional' part of the "if // statement". If not, it definitely dominates the region. BranchInst *BI = dyn_cast(PBB->getTerminator()); - if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB) + if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB) return true; // If we aren't allowing aggressive promotion anymore, then don't consider // instructions in the 'if region'. - if (AggressiveInsts == 0) return false; + if (!AggressiveInsts) return false; // If we have seen this instruction before, don't count it again. if (AggressiveInsts->count(I)) return true; @@ -387,15 +309,15 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, /// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr /// and PointerNullValue. Return NULL if value is not a constant int. -static ConstantInt *GetConstantInt(Value *V, const DataLayout *TD) { +static ConstantInt *GetConstantInt(Value *V, const DataLayout *DL) { // Normal constant int. ConstantInt *CI = dyn_cast(V); - if (CI || !TD || !isa(V) || !V->getType()->isPointerTy()) + if (CI || !DL || !isa(V) || !V->getType()->isPointerTy()) return CI; // This is some kind of pointer constant. Turn it into a pointer-sized // ConstantInt if possible. - IntegerType *PtrTy = cast(TD->getIntPtrType(V->getType())); + IntegerType *PtrTy = cast(DL->getIntPtrType(V->getType())); // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). if (isa(V)) @@ -412,7 +334,7 @@ static ConstantInt *GetConstantInt(Value *V, const DataLayout *TD) { return cast (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); } - return 0; + return nullptr; } /// GatherConstantCompares - Given a potentially 'or'd or 'and'd together @@ -421,14 +343,31 @@ static ConstantInt *GetConstantInt(Value *V, const DataLayout *TD) { /// Values vector. static Value * GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, - const DataLayout *TD, bool isEQ, unsigned &UsedICmps) { + const DataLayout *DL, bool isEQ, unsigned &UsedICmps) { Instruction *I = dyn_cast(V); - if (I == 0) return 0; + if (!I) return nullptr; // If this is an icmp against a constant, handle this as one of the cases. if (ICmpInst *ICI = dyn_cast(I)) { - if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { + if (ConstantInt *C = GetConstantInt(I->getOperand(1), DL)) { + Value *RHSVal; + ConstantInt *RHSC; + if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { + // (x & ~2^x) == y --> x == y || x == y|2^x + // This undoes a transformation done by instcombine to fuse 2 compares. + if (match(ICI->getOperand(0), + m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) { + APInt Not = ~RHSC->getValue(); + if (Not.isPowerOf2()) { + Vals.push_back(C); + Vals.push_back( + ConstantInt::get(C->getContext(), C->getValue() | Not)); + UsedICmps++; + return RHSVal; + } + } + UsedICmps++; Vals.push_back(C); return I->getOperand(0); @@ -439,6 +378,13 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, ConstantRange Span = ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); + // Shift the range if the compare is fed by an add. This is the range + // compare idiom as emitted by instcombine. + bool hasAdd = + match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC))); + if (hasAdd) + Span = Span.subtract(RHSC->getValue()); + // If this is an and/!= check then we want to optimize "x ugt 2" into // x != 0 && x != 1. if (!isEQ) @@ -446,27 +392,27 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, // If there are a ton of values, we don't want to make a ginormous switch. if (Span.getSetSize().ugt(8) || Span.isEmptySet()) - return 0; + return nullptr; for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); UsedICmps++; - return I->getOperand(0); + return hasAdd ? RHSVal : I->getOperand(0); } - return 0; + return nullptr; } // Otherwise, we can only handle an | or &, depending on isEQ. if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And)) - return 0; + return nullptr; unsigned NumValsBeforeLHS = Vals.size(); unsigned UsedICmpsBeforeLHS = UsedICmps; - if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, + if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, DL, isEQ, UsedICmps)) { unsigned NumVals = Vals.size(); unsigned UsedICmpsBeforeRHS = UsedICmps; - if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, + if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL, isEQ, UsedICmps)) { if (LHS == RHS) return LHS; @@ -476,33 +422,33 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, // set it and return success. - if (Extra == 0 || Extra == I->getOperand(1)) { + if (Extra == nullptr || Extra == I->getOperand(1)) { Extra = I->getOperand(1); return LHS; } Vals.resize(NumValsBeforeLHS); UsedICmps = UsedICmpsBeforeLHS; - return 0; + return nullptr; } // If the LHS can't be folded in, but Extra is available and RHS can, try to // use LHS as Extra. - if (Extra == 0 || Extra == I->getOperand(0)) { + if (Extra == nullptr || Extra == I->getOperand(0)) { Value *OldExtra = Extra; Extra = I->getOperand(0); - if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, + if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL, isEQ, UsedICmps)) return RHS; assert(Vals.size() == NumValsBeforeLHS); Extra = OldExtra; } - return 0; + return nullptr; } static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { - Instruction *Cond = 0; + Instruction *Cond = nullptr; if (SwitchInst *SI = dyn_cast(TI)) { Cond = dyn_cast(SI->getCondition()); } else if (BranchInst *BI = dyn_cast(TI)) { @@ -519,7 +465,7 @@ static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { /// isValueEqualityComparison - Return true if the specified terminator checks /// to see if a value is equal to constant integer value. Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { - Value *CV = 0; + Value *CV = nullptr; if (SwitchInst *SI = dyn_cast(TI)) { // Do not permit merging of large switch instructions into their // predecessors unless there is only one predecessor. @@ -529,15 +475,17 @@ Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { } else if (BranchInst *BI = dyn_cast(TI)) if (BI->isConditional() && BI->getCondition()->hasOneUse()) if (ICmpInst *ICI = dyn_cast(BI->getCondition())) - if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || - ICI->getPredicate() == ICmpInst::ICMP_NE) && - GetConstantInt(ICI->getOperand(1), TD)) + if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL)) CV = ICI->getOperand(0); // Unwrap any lossless ptrtoint cast. - if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) - if (PtrToIntInst *PTII = dyn_cast(CV)) - CV = PTII->getOperand(0); + if (DL && CV) { + if (PtrToIntInst *PTII = dyn_cast(CV)) { + Value *Ptr = PTII->getPointerOperand(); + if (PTII->getType() == DL->getIntPtrType(Ptr->getType())) + CV = Ptr; + } + } return CV; } @@ -559,7 +507,7 @@ GetValueEqualityComparisonCases(TerminatorInst *TI, ICmpInst *ICI = cast(BI->getCondition()); BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1), - TD), + DL), Succ)); return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); } @@ -707,11 +655,11 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, // Otherwise, TI's block must correspond to some matched value. Find out // which value (or set of values) this is. - ConstantInt *TIV = 0; + ConstantInt *TIV = nullptr; BasicBlock *TIBB = TI->getParent(); for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].Dest == TIBB) { - if (TIV != 0) + if (TIV) return false; // Cannot handle multiple values coming to this block. TIV = PredCases[i].Value; } @@ -719,7 +667,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, // Okay, we found the one constant that our value can be if we get into TI's // BB. Find out which successor will unconditionally be branched to. - BasicBlock *TheRealDest = 0; + BasicBlock *TheRealDest = nullptr; for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) if (ThisCases[i].Value == TIV) { TheRealDest = ThisCases[i].Dest; @@ -727,7 +675,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, } // If not handled by any explicit cases, it is handled by the default case. - if (TheRealDest == 0) TheRealDest = ThisDef; + if (!TheRealDest) TheRealDest = ThisDef; // Remove PHI node entries for dead edges. BasicBlock *CheckEdge = TheRealDest; @@ -735,7 +683,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, if (*SI != CheckEdge) (*SI)->removePredecessor(TIBB); else - CheckEdge = 0; + CheckEdge = nullptr; // Insert the new branch. Instruction *NI = Builder.CreateBr(TheRealDest); @@ -759,9 +707,10 @@ namespace { }; } -static int ConstantIntSortPredicate(const void *P1, const void *P2) { - const ConstantInt *LHS = *(const ConstantInt*const*)P1; - const ConstantInt *RHS = *(const ConstantInt*const*)P2; +static int ConstantIntSortPredicate(ConstantInt *const *P1, + ConstantInt *const *P2) { + const ConstantInt *LHS = *P1; + const ConstantInt *RHS = *P2; if (LHS->getValue().ult(RHS->getValue())) return 1; if (LHS->getValue() == RHS->getValue()) @@ -786,8 +735,7 @@ static void GetBranchWeights(TerminatorInst *TI, MDNode* MD = TI->getMetadata(LLVMContext::MD_prof); assert(MD); for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { - ConstantInt* CI = dyn_cast(MD->getOperand(i)); - assert(CI); + ConstantInt *CI = cast(MD->getOperand(i)); Weights.push_back(CI->getValue().getZExtValue()); } @@ -802,21 +750,14 @@ static void GetBranchWeights(TerminatorInst *TI, } } -/// Sees if any of the weights are too big for a uint32_t, and halves all the -/// weights if any are. +/// Keep halving the weights until all can fit in uint32_t. static void FitWeights(MutableArrayRef Weights) { - bool Halve = false; - for (unsigned i = 0; i < Weights.size(); ++i) - if (Weights[i] > UINT_MAX) { - Halve = true; - break; - } - - if (! Halve) - return; - - for (unsigned i = 0; i < Weights.size(); ++i) - Weights[i] /= 2; + uint64_t Max = *std::max_element(Weights.begin(), Weights.end()); + if (Max > UINT_MAX) { + unsigned Offset = 32 - countLeadingZeros(Max); + for (uint64_t &I : Weights) + I >>= Offset; + } } /// FoldValueComparisonIntoPredecessors - The specified terminator is a value @@ -983,8 +924,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, Builder.SetInsertPoint(PTI); // Convert pointer to int before we switch. if (CV->getType()->isPointerTy()) { - assert(TD && "Cannot switch on pointer without DataLayout"); - CV = Builder.CreatePtrToInt(CV, TD->getIntPtrType(CV->getContext()), + assert(DL && "Cannot switch on pointer without DataLayout"); + CV = Builder.CreatePtrToInt(CV, DL->getIntPtrType(CV->getType()), "magicptr"); } @@ -1011,10 +952,10 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, // Okay, last check. If BB is still a successor of PSI, then we must // have an infinite loop case. If so, add an infinitely looping block // to handle the case to preserve the behavior of the code. - BasicBlock *InfLoopBlock = 0; + BasicBlock *InfLoopBlock = nullptr; for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) if (NewSI->getSuccessor(i) == BB) { - if (InfLoopBlock == 0) { + if (!InfLoopBlock) { // Insert it at the end of the function, because it's either code, // or it won't matter if it's hot. :) InfLoopBlock = BasicBlock::Create(BB->getContext(), @@ -1079,9 +1020,9 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { (isa(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) return false; - // If we get here, we can hoist at least one instruction. BasicBlock *BIParent = BI->getParent(); + bool Changed = false; do { // If we are hoisting the terminator instruction, don't move one (making a // broken BB), instead clone it, and remove BI. @@ -1096,6 +1037,7 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { I2->replaceAllUsesWith(I1); I1->intersectOptionalDataWith(I2); I2->eraseFromParent(); + Changed = true; I1 = BB1_Itr++; I2 = BB2_Itr++; @@ -1115,7 +1057,23 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { HoistTerminator: // It may not be possible to hoist an invoke. if (isa(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) - return true; + return Changed; + + for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { + PHINode *PN; + for (BasicBlock::iterator BBI = SI->begin(); + (PN = dyn_cast(BBI)); ++BBI) { + Value *BB1V = PN->getIncomingValueForBlock(BB1); + Value *BB2V = PN->getIncomingValueForBlock(BB2); + if (BB1V == BB2V) + continue; + + if (isa(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) + return Changed; + if (isa(BB2V) && !isSafeToSpeculativelyExecute(BB2V)) + return Changed; + } + } // Okay, it is safe to hoist the terminator. Instruction *NT = I1->clone(); @@ -1143,7 +1101,7 @@ HoistTerminator: // These values do not agree. Insert a select instruction before NT // that determines the right value. SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; - if (SI == 0) + if (!SI) SI = cast (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, BB1V->getName()+"."+BB2V->getName())); @@ -1188,7 +1146,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { // Gather the PHI nodes in BBEnd. std::map > MapValueFromBB1ToBB2; - Instruction *FirstNonPhiInBBEnd = 0; + Instruction *FirstNonPhiInBBEnd = nullptr; for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) { if (PHINode *PN = dyn_cast(I)) { @@ -1266,7 +1224,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { // The operands should be either the same or they need to be generated // with a PHI node after sinking. We only handle the case where there is // a single pair of different operands. - Value *DifferentOp1 = 0, *DifferentOp2 = 0; + Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr; unsigned Op1Idx = 0; for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) { if (I1->getOperand(I) == I2->getOperand(I)) @@ -1332,155 +1290,286 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { return Changed; } -/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 -/// and an BB2 and the only successor of BB1 is BB2, hoist simple code -/// (for now, restricted to a single instruction that's side effect free) from -/// the BB1 into the branch block to speculatively execute it. +/// \brief Determine if we can hoist sink a sole store instruction out of a +/// conditional block. +/// +/// We are looking for code like the following: +/// BrBB: +/// store i32 %add, i32* %arrayidx2 +/// ... // No other stores or function calls (we could be calling a memory +/// ... // function). +/// %cmp = icmp ult %x, %y +/// br i1 %cmp, label %EndBB, label %ThenBB +/// ThenBB: +/// store i32 %add5, i32* %arrayidx2 +/// br label EndBB +/// EndBB: +/// ... +/// We are going to transform this into: +/// BrBB: +/// store i32 %add, i32* %arrayidx2 +/// ... // +/// %cmp = icmp ult %x, %y +/// %add.add5 = select i1 %cmp, i32 %add, %add5 +/// store i32 %add.add5, i32* %arrayidx2 +/// ... +/// +/// \return The pointer to the value of the previous store if the store can be +/// hoisted into the predecessor block. 0 otherwise. +static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, + BasicBlock *StoreBB, BasicBlock *EndBB) { + StoreInst *StoreToHoist = dyn_cast(I); + if (!StoreToHoist) + return nullptr; + + // Volatile or atomic. + if (!StoreToHoist->isSimple()) + return nullptr; + + Value *StorePtr = StoreToHoist->getPointerOperand(); + + // Look for a store to the same pointer in BrBB. + unsigned MaxNumInstToLookAt = 10; + for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), + RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) { + Instruction *CurI = &*RI; + + // Could be calling an instruction that effects memory like free(). + if (CurI->mayHaveSideEffects() && !isa(CurI)) + return nullptr; + + StoreInst *SI = dyn_cast(CurI); + // Found the previous store make sure it stores to the same location. + if (SI && SI->getPointerOperand() == StorePtr) + // Found the previous store, return its value operand. + return SI->getValueOperand(); + else if (SI) + return nullptr; // Unknown store. + } + + return nullptr; +} + +/// \brief Speculate a conditional basic block flattening the CFG. +/// +/// Note that this is a very risky transform currently. Speculating +/// instructions like this is most often not desirable. Instead, there is an MI +/// pass which can do it with full awareness of the resource constraints. +/// However, some cases are "obvious" and we should do directly. An example of +/// this is speculating a single, reasonably cheap instruction. /// -/// Turn -/// BB: -/// %t1 = icmp -/// br i1 %t1, label %BB1, label %BB2 -/// BB1: -/// %t3 = add %t2, c +/// There is only one distinct advantage to flattening the CFG at the IR level: +/// it makes very common but simplistic optimizations such as are common in +/// instcombine and the DAG combiner more powerful by removing CFG edges and +/// modeling their effects with easier to reason about SSA value graphs. +/// +/// +/// An illustration of this transform is turning this IR: +/// \code +/// BB: +/// %cmp = icmp ult %x, %y +/// br i1 %cmp, label %EndBB, label %ThenBB +/// ThenBB: +/// %sub = sub %x, %y /// br label BB2 -/// BB2: -/// => -/// BB: -/// %t1 = icmp -/// %t4 = add %t2, c -/// %t3 = select i1 %t1, %t2, %t3 -static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { - // Only speculatively execution a single instruction (not counting the - // terminator) for now. - Instruction *HInst = NULL; - Instruction *Term = BB1->getTerminator(); - for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); +/// EndBB: +/// %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ] +/// ... +/// \endcode +/// +/// Into this IR: +/// \code +/// BB: +/// %cmp = icmp ult %x, %y +/// %sub = sub %x, %y +/// %cond = select i1 %cmp, 0, %sub +/// ... +/// \endcode +/// +/// \returns true if the conditional block is removed. +static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB) { + // Be conservative for now. FP select instruction can often be expensive. + Value *BrCond = BI->getCondition(); + if (isa(BrCond)) + return false; + + BasicBlock *BB = BI->getParent(); + BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0); + + // If ThenBB is actually on the false edge of the conditional branch, remember + // to swap the select operands later. + bool Invert = false; + if (ThenBB != BI->getSuccessor(0)) { + assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?"); + Invert = true; + } + assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block"); + + // Keep a count of how many times instructions are used within CondBB when + // they are candidates for sinking into CondBB. Specifically: + // - They are defined in BB, and + // - They have no side effects, and + // - All of their uses are in CondBB. + SmallDenseMap SinkCandidateUseCounts; + + unsigned SpeculationCost = 0; + Value *SpeculatedStoreValue = nullptr; + StoreInst *SpeculatedStore = nullptr; + for (BasicBlock::iterator BBI = ThenBB->begin(), + BBE = std::prev(ThenBB->end()); BBI != BBE; ++BBI) { Instruction *I = BBI; // Skip debug info. - if (isa(I)) continue; - if (I == Term) break; + if (isa(I)) + continue; - if (HInst) + // Only speculatively execution a single instruction (not counting the + // terminator) for now. + ++SpeculationCost; + if (SpeculationCost > 1) return false; - HInst = I; - } - - BasicBlock *BIParent = BI->getParent(); - // Check the instruction to be hoisted, if there is one. - if (HInst) { // Don't hoist the instruction if it's unsafe or expensive. - if (!isSafeToSpeculativelyExecute(HInst)) + if (!isSafeToSpeculativelyExecute(I) && + !(HoistCondStores && + (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB, + EndBB)))) return false; - if (ComputeSpeculationCost(HInst) > PHINodeFoldingThreshold) + if (!SpeculatedStoreValue && + ComputeSpeculationCost(I) > PHINodeFoldingThreshold) return false; + // Store the store speculation candidate. + if (SpeculatedStoreValue) + SpeculatedStore = cast(I); + // Do not hoist the instruction if any of its operands are defined but not - // used in this BB. The transformation will prevent the operand from + // used in BB. The transformation will prevent the operand from // being sunk into the use block. - for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); + for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { Instruction *OpI = dyn_cast(*i); - if (OpI && OpI->getParent() == BIParent && - !OpI->mayHaveSideEffects() && - !OpI->isUsedInBasicBlock(BIParent)) - return false; + if (!OpI || OpI->getParent() != BB || + OpI->mayHaveSideEffects()) + continue; // Not a candidate for sinking. + + ++SinkCandidateUseCounts[OpI]; } } - // Be conservative for now. FP select instruction can often be expensive. - Value *BrCond = BI->getCondition(); - if (isa(BrCond)) - return false; - - // If BB1 is actually on the false edge of the conditional branch, remember - // to swap the select operands later. - bool Invert = false; - if (BB1 != BI->getSuccessor(0)) { - assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); - Invert = true; - } + // Consider any sink candidates which are only used in CondBB as costs for + // speculation. Note, while we iterate over a DenseMap here, we are summing + // and so iteration order isn't significant. + for (SmallDenseMap::iterator I = + SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end(); + I != E; ++I) + if (I->first->getNumUses() == I->second) { + ++SpeculationCost; + if (SpeculationCost > 1) + return false; + } - // Collect interesting PHIs, and scan for hazards. - SmallSetVector, 4> PHIs; - BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); - for (BasicBlock::iterator I = BB2->begin(); + // Check that the PHI nodes can be converted to selects. + bool HaveRewritablePHIs = false; + for (BasicBlock::iterator I = EndBB->begin(); PHINode *PN = dyn_cast(I); ++I) { - Value *BB1V = PN->getIncomingValueForBlock(BB1); - Value *BIParentV = PN->getIncomingValueForBlock(BIParent); + Value *OrigV = PN->getIncomingValueForBlock(BB); + Value *ThenV = PN->getIncomingValueForBlock(ThenBB); + // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf. // Skip PHIs which are trivial. - if (BB1V == BIParentV) + if (ThenV == OrigV) continue; - // Check for safety. - if (ConstantExpr *CE = dyn_cast(BB1V)) { - // An unfolded ConstantExpr could end up getting expanded into - // Instructions. Don't speculate this and another instruction at - // the same time. - if (HInst) - return false; - if (!isSafeToSpeculativelyExecute(CE)) - return false; - if (ComputeSpeculationCost(CE) > PHINodeFoldingThreshold) - return false; - } + HaveRewritablePHIs = true; + ConstantExpr *OrigCE = dyn_cast(OrigV); + ConstantExpr *ThenCE = dyn_cast(ThenV); + if (!OrigCE && !ThenCE) + continue; // Known safe and cheap. + + if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) || + (OrigCE && !isSafeToSpeculativelyExecute(OrigCE))) + return false; + unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE) : 0; + unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE) : 0; + if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold) + return false; - // Ok, we may insert a select for this PHI. - PHIs.insert(std::make_pair(BB1V, BIParentV)); + // Account for the cost of an unfolded ConstantExpr which could end up + // getting expanded into Instructions. + // FIXME: This doesn't account for how many operations are combined in the + // constant expression. + ++SpeculationCost; + if (SpeculationCost > 1) + return false; } // If there are no PHIs to process, bail early. This helps ensure idempotence // as well. - if (PHIs.empty()) + if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue)) return false; // If we get here, we can hoist the instruction and if-convert. - DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *BB1 << "\n";); + DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";); - // Hoist the instruction. - if (HInst) - BIParent->getInstList().splice(BI, BB1->getInstList(), HInst); + // Insert a select of the value of the speculated store. + if (SpeculatedStoreValue) { + IRBuilder Builder(BI); + Value *TrueV = SpeculatedStore->getValueOperand(); + Value *FalseV = SpeculatedStoreValue; + if (Invert) + std::swap(TrueV, FalseV); + Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() + + "." + FalseV->getName()); + SpeculatedStore->setOperand(0, S); + } + + // Hoist the instructions. + BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(), + std::prev(ThenBB->end())); // Insert selects and rewrite the PHI operands. IRBuilder Builder(BI); - for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { - Value *TrueV = PHIs[i].first; - Value *FalseV = PHIs[i].second; + for (BasicBlock::iterator I = EndBB->begin(); + PHINode *PN = dyn_cast(I); ++I) { + unsigned OrigI = PN->getBasicBlockIndex(BB); + unsigned ThenI = PN->getBasicBlockIndex(ThenBB); + Value *OrigV = PN->getIncomingValue(OrigI); + Value *ThenV = PN->getIncomingValue(ThenI); + + // Skip PHIs which are trivial. + if (OrigV == ThenV) + continue; // Create a select whose true value is the speculatively executed value and - // false value is the previously determined FalseV. - SelectInst *SI; + // false value is the preexisting value. Swap them if the branch + // destinations were inverted. + Value *TrueV = ThenV, *FalseV = OrigV; if (Invert) - SI = cast - (Builder.CreateSelect(BrCond, FalseV, TrueV, - FalseV->getName() + "." + TrueV->getName())); - else - SI = cast - (Builder.CreateSelect(BrCond, TrueV, FalseV, - TrueV->getName() + "." + FalseV->getName())); - - // Make the PHI node use the select for all incoming values for "then" and - // "if" blocks. - for (BasicBlock::iterator I = BB2->begin(); - PHINode *PN = dyn_cast(I); ++I) { - unsigned BB1I = PN->getBasicBlockIndex(BB1); - unsigned BIParentI = PN->getBasicBlockIndex(BIParent); - Value *BB1V = PN->getIncomingValue(BB1I); - Value *BIParentV = PN->getIncomingValue(BIParentI); - if (TrueV == BB1V && FalseV == BIParentV) { - PN->setIncomingValue(BB1I, SI); - PN->setIncomingValue(BIParentI, SI); - } - } + std::swap(TrueV, FalseV); + Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV, + TrueV->getName() + "." + FalseV->getName()); + PN->setIncomingValue(OrigI, V); + PN->setIncomingValue(ThenI, V); } ++NumSpeculations; return true; } +/// \returns True if this block contains a CallInst with the NoDuplicate +/// attribute. +static bool HasNoDuplicateCall(const BasicBlock *BB) { + for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + const CallInst *CI = dyn_cast(I); + if (!CI) + continue; + if (CI->cannotDuplicate()) + return true; + } + return false; +} + /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch /// across this block. static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { @@ -1495,10 +1584,9 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { // We can only support instructions that do not define values that are // live outside of the current basic block. - for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); - UI != E; ++UI) { - Instruction *U = cast(*UI); - if (U->getParent() != BB || isa(U)) return false; + for (User *U : BBI->users()) { + Instruction *UI = cast(U); + if (UI->getParent() != BB || isa(UI)) return false; } // Looks ok, continue checking. @@ -1511,7 +1599,7 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { /// that is defined in the same block as the branch and if any PHI entries are /// constants, thread edges corresponding to that entry to be branches to their /// ultimate destination. -static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { +static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *DL) { BasicBlock *BB = BI->getParent(); PHINode *PN = dyn_cast(BI->getCondition()); // NOTE: we currently cannot transform this case if the PHI node is used @@ -1528,11 +1616,13 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { // Now we know that this block has multiple preds and two succs. if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; + if (HasNoDuplicateCall(BB)) return false; + // Okay, this is a simple enough basic block. See if any phi values are // constants. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { ConstantInt *CB = dyn_cast(PN->getIncomingValue(i)); - if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue; + if (!CB || !CB->getType()->isIntegerTy(1)) continue; // Okay, we now know that all edges from PredBB should be revectored to // branch to RealDest. @@ -1578,7 +1668,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { } // Check for trivial simplification. - if (Value *V = SimplifyInstruction(N, TD)) { + if (Value *V = SimplifyInstruction(N, DL)) { TranslateMap[BBI] = V; delete N; // Instruction folded away, don't need actual inst } else { @@ -1599,7 +1689,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { } // Recurse, simplifying any other constants. - return FoldCondBranchOnPHI(BI, TD) | true; + return FoldCondBranchOnPHI(BI, DL) | true; } return false; @@ -1607,7 +1697,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry /// PHI node, see if we can eliminate it. -static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { +static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *DL) { // Ok, this is a two entry PHI node. Check to see if this is a simple "if // statement", which has a very simple dominance structure. Basically, we // are trying to find the condition that is being branched on, which @@ -1641,7 +1731,7 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { for (BasicBlock::iterator II = BB->begin(); isa(II);) { PHINode *PN = cast(II++); - if (Value *V = SimplifyInstruction(PN, TD)) { + if (Value *V = SimplifyInstruction(PN, DL)) { PN->replaceAllUsesWith(V); PN->eraseFromParent(); continue; @@ -1657,7 +1747,7 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { // If we folded the first phi, PN dangles at this point. Refresh it. If // we ran out of PHIs then we simplified them all. PN = dyn_cast(BB->begin()); - if (PN == 0) return true; + if (!PN) return true; // Don't fold i1 branches on PHIs which contain binary operators. These can // often be turned into switches and other things. @@ -1671,11 +1761,11 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { // instructions in the predecessor blocks can be promoted as well. If // not, we won't be able to get rid of the control flow, so it's not // worth promoting to select instructions. - BasicBlock *DomBlock = 0; + BasicBlock *DomBlock = nullptr; BasicBlock *IfBlock1 = PN->getIncomingBlock(0); BasicBlock *IfBlock2 = PN->getIncomingBlock(1); if (cast(IfBlock1->getTerminator())->isConditional()) { - IfBlock1 = 0; + IfBlock1 = nullptr; } else { DomBlock = *pred_begin(IfBlock1); for (BasicBlock::iterator I = IfBlock1->begin();!isa(I);++I) @@ -1688,7 +1778,7 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { } if (cast(IfBlock2->getTerminator())->isConditional()) { - IfBlock2 = 0; + IfBlock2 = nullptr; } else { DomBlock = *pred_begin(IfBlock2); for (BasicBlock::iterator I = IfBlock2->begin();!isa(I);++I) @@ -1871,7 +1961,7 @@ static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { bool llvm::FoldBranchToCommonDest(BranchInst *BI) { BasicBlock *BB = BI->getParent(); - Instruction *Cond = 0; + Instruction *Cond = nullptr; if (BI->isConditional()) Cond = dyn_cast(BI->getCondition()); else { @@ -1897,12 +1987,12 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { } } - if (Cond == 0) + if (!Cond) return false; } - if (Cond == 0 || (!isa(Cond) && !isa(Cond)) || - Cond->getParent() != BB || !Cond->hasOneUse()) + if (!Cond || (!isa(Cond) && !isa(Cond)) || + Cond->getParent() != BB || !Cond->hasOneUse()) return false; // Only allow this if the condition is a simple instruction that can be @@ -1917,9 +2007,9 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // that feeds the branch. We later ensure that any values that _it_ uses // were also live in the predecessor, so that we don't unnecessarily create // register pressure or inhibit out-of-order execution. - Instruction *BonusInst = 0; + Instruction *BonusInst = nullptr; if (&*FrontIt != Cond && - FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond && + FrontIt->hasOneUse() && FrontIt->user_back() == Cond && isSafeToSpeculativelyExecute(FrontIt)) { BonusInst = &*FrontIt; ++FrontIt; @@ -1952,7 +2042,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // Finally, don't infinitely unroll conditional loops. BasicBlock *TrueDest = BI->getSuccessor(0); - BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : 0; + BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; if (TrueDest == BB || FalseDest == BB) return false; @@ -1964,7 +2054,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // the common successor, verify that the same value flows in from both // blocks. SmallVector PHIs; - if (PBI == 0 || PBI->isUnconditional() || + if (!PBI || PBI->isUnconditional() || (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) || (!BI->isConditional() && @@ -1994,14 +2084,19 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // Ensure that any values used in the bonus instruction are also used // by the terminator of the predecessor. This means that those values // must already have been resolved, so we won't be inhibiting the - // out-of-order core by speculating them earlier. - if (BonusInst) { + // out-of-order core by speculating them earlier. We also allow + // instructions that are used by the terminator's condition because it + // exposes more merging opportunities. + bool UsedByBranch = (BonusInst && BonusInst->hasOneUse() && + BonusInst->user_back() == Cond); + + if (BonusInst && !UsedByBranch) { // Collect the values used by the bonus inst SmallPtrSet UsedValues; for (Instruction::op_iterator OI = BonusInst->op_begin(), OE = BonusInst->op_end(); OI != OE; ++OI) { Value *V = *OI; - if (!isa(V)) + if (!isa(V) && !isa(V)) UsedValues.insert(V); } @@ -2049,9 +2144,17 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { } // If we have a bonus inst, clone it into the predecessor block. - Instruction *NewBonus = 0; + Instruction *NewBonus = nullptr; if (BonusInst) { NewBonus = BonusInst->clone(); + + // If we moved a load, we cannot any longer claim any knowledge about + // its potential value. The previous information might have been valid + // only given the branch precondition. + // For an analogous reason, we must also drop all the metadata whose + // semantics we don't understand. + NewBonus->dropUnknownMetadata(LLVMContext::MD_dbg); + PredBlock->getInstList().insert(PBI, NewBonus); NewBonus->takeName(BonusInst); BonusInst->setName(BonusInst->getName()+".old"); @@ -2117,14 +2220,14 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { MDBuilder(BI->getContext()). createBranchWeights(MDWeights)); } else - PBI->setMetadata(LLVMContext::MD_prof, NULL); + PBI->setMetadata(LLVMContext::MD_prof, nullptr); } else { // Update PHI nodes in the common successors. for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { ConstantInt *PBI_C = cast( PHIs[i]->getIncomingValueForBlock(PBI->getParent())); assert(PBI_C->getType()->isIntegerTy(1)); - Instruction *MergedCond = 0; + Instruction *MergedCond = nullptr; if (PBI->getSuccessor(0) == TrueDest) { // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value) // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value) @@ -2397,16 +2500,16 @@ static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, // If TrueBB and FalseBB are equal, only try to preserve one copy of that // successor. BasicBlock *KeepEdge1 = TrueBB; - BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; + BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr; // Then remove the rest. for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { BasicBlock *Succ = OldTerm->getSuccessor(I); // Make sure only to keep exactly one copy of each edge. if (Succ == KeepEdge1) - KeepEdge1 = 0; + KeepEdge1 = nullptr; else if (Succ == KeepEdge2) - KeepEdge2 = 0; + KeepEdge2 = nullptr; else Succ->removePredecessor(OldTerm->getParent()); } @@ -2415,7 +2518,7 @@ static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); // Insert an appropriate new terminator. - if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { + if (!KeepEdge1 && !KeepEdge2) { if (TrueBB == FalseBB) // We were only looking for one successor, and it was present. // Create an unconditional branch to it. @@ -2437,7 +2540,7 @@ static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, // One of the selected values was a successor, but the other wasn't. // Insert an unconditional branch to the one that was found; // the edge to the one that wasn't must be unreachable. - if (KeepEdge1 == 0) + if (!KeepEdge1) // Only TrueBB was found. Builder.CreateBr(TrueBB); else @@ -2522,9 +2625,9 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { /// /// We prefer to split the edge to 'end' so that there is a true/false entry to /// the PHI, merging the third icmp into the switch. -static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, - const DataLayout *TD, - IRBuilder<> &Builder) { +static bool TryToSimplifyUncondBranchWithICmpInIt( + ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI, + const DataLayout *DL) { BasicBlock *BB = ICI->getParent(); // If the block has any PHIs in it or the icmp has multiple uses, it is too @@ -2538,7 +2641,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, // 'V' and this block is the default case for the switch. In this case we can // fold the compared value into the switch to simplify things. BasicBlock *Pred = BB->getSinglePredecessor(); - if (Pred == 0 || !isa(Pred->getTerminator())) return false; + if (!Pred || !isa(Pred->getTerminator())) return false; SwitchInst *SI = cast(Pred->getTerminator()); if (SI->getCondition() != V) @@ -2552,12 +2655,12 @@ static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, assert(VVal && "Should have a unique destination value"); ICI->setOperand(0, VVal); - if (Value *V = SimplifyInstruction(ICI, TD)) { + if (Value *V = SimplifyInstruction(ICI, DL)) { ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); } // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } // Ok, the block is reachable from the default dest. If the constant we're @@ -2573,14 +2676,14 @@ static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } // The use of the icmp has to be in the 'end' block, by the only PHI node in // the block. BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); - PHINode *PHIUse = dyn_cast(ICI->use_back()); - if (PHIUse == 0 || PHIUse != &SuccBlock->front() || + PHINode *PHIUse = dyn_cast(ICI->user_back()); + if (PHIUse == nullptr || PHIUse != &SuccBlock->front() || isa(++BasicBlock::iterator(PHIUse))) return false; @@ -2629,32 +2732,32 @@ static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, /// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. /// Check to see if it is branching on an or/and chain of icmp instructions, and /// fold it into a switch instruction if so. -static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *TD, +static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *DL, IRBuilder<> &Builder) { Instruction *Cond = dyn_cast(BI->getCondition()); - if (Cond == 0) return false; + if (!Cond) return false; // Change br (X == 0 | X == 1), T, F into a switch instruction. // If this is a bunch of seteq's or'd together, or if it's a bunch of // 'setne's and'ed together, collect them. - Value *CompVal = 0; + Value *CompVal = nullptr; std::vector Values; bool TrueWhenEqual = true; - Value *ExtraCase = 0; + Value *ExtraCase = nullptr; unsigned UsedICmps = 0; if (Cond->getOpcode() == Instruction::Or) { - CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true, + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, true, UsedICmps); } else if (Cond->getOpcode() == Instruction::And) { - CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false, + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, false, UsedICmps); TrueWhenEqual = false; } // If we didn't have a multiply compared value, fail. - if (CompVal == 0) return false; + if (!CompVal) return false; // Avoid turning single icmps into a switch. if (UsedICmps <= 1) @@ -2710,9 +2813,9 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *TD, Builder.SetInsertPoint(BI); // Convert pointer to int before we switch. if (CompVal->getType()->isPointerTy()) { - assert(TD && "Cannot switch on pointer without DataLayout"); + assert(DL && "Cannot switch on pointer without DataLayout"); CompVal = Builder.CreatePtrToInt(CompVal, - TD->getIntPtrType(CompVal->getContext()), + DL->getIntPtrType(CompVal->getType()), "magicptr"); } @@ -2758,9 +2861,20 @@ bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { return false; // Turn all invokes that unwind here into calls and delete the basic block. + bool InvokeRequiresTableEntry = false; + bool Changed = false; for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { InvokeInst *II = cast((*PI++)->getTerminator()); + + if (II->hasFnAttr(Attribute::UWTable)) { + // Don't remove an `invoke' instruction if the ABI requires an entry into + // the table. + InvokeRequiresTableEntry = true; + continue; + } + SmallVector Args(II->op_begin(), II->op_end() - 3); + // Insert a call instruction before the invoke. CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); Call->takeName(II); @@ -2780,11 +2894,14 @@ bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { // Finally, delete the invoke instruction! II->eraseFromParent(); + Changed = true; } - // The landingpad is now unreachable. Zap it. - BB->eraseFromParent(); - return true; + if (!InvokeRequiresTableEntry) + // The landingpad is now unreachable. Zap it. + BB->eraseFromParent(); + + return Changed; } bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { @@ -2935,7 +3052,7 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { // Find the most popular block. unsigned MaxPop = 0; unsigned MaxIndex = 0; - BasicBlock *MaxBlock = 0; + BasicBlock *MaxBlock = nullptr; for (std::map >::iterator I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { if (I->second.first > MaxPop || @@ -3028,7 +3145,12 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { Value *Sub = SI->getCondition(); if (!Offset->isNullValue()) Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off"); - Value *Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); + Value *Cmp; + // If NumCases overflowed, then all possible values jump to the successor. + if (NumCases->isNullValue() && SI->getNumCases() != 0) + Cmp = ConstantInt::getTrue(SI->getContext()); + else + Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); BranchInst *NewBI = Builder.CreateCondBr( Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest()); @@ -3066,7 +3188,7 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { /// and use it to remove dead cases. static bool EliminateDeadSwitchCases(SwitchInst *SI) { Value *Cond = SI->getCondition(); - unsigned Bits = cast(Cond->getType())->getBitWidth(); + unsigned Bits = Cond->getType()->getIntegerBitWidth(); APInt KnownZero(Bits, 0), KnownOne(Bits, 0); ComputeMaskedBits(Cond, KnownZero, KnownOne); @@ -3102,7 +3224,7 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI) { Case.getCaseSuccessor()->removePredecessor(SI->getParent()); SI->removeCase(Case); } - if (HasWeight) { + if (HasWeight && Weights.size() >= 2) { SmallVector MDWeights(Weights.begin(), Weights.end()); SI->setMetadata(LLVMContext::MD_prof, MDBuilder(SI->getParent()->getContext()). @@ -3121,13 +3243,13 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex) { if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) - return NULL; // BB must be empty to be a candidate for simplification. + return nullptr; // BB must be empty to be a candidate for simplification. if (!BB->getSinglePredecessor()) - return NULL; // BB must be dominated by the switch. + return nullptr; // BB must be dominated by the switch. BranchInst *Branch = dyn_cast(BB->getTerminator()); if (!Branch || !Branch->isUnconditional()) - return NULL; // Terminator must be unconditional branch. + return nullptr; // Terminator must be unconditional branch. BasicBlock *Succ = Branch->getSuccessor(0); @@ -3143,7 +3265,7 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, return PHI; } - return NULL; + return nullptr; } /// ForwardSwitchConditionToPHI - Try to forward the condition of a switch @@ -3171,7 +3293,7 @@ static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), E = ForwardingNodes.end(); I != E; ++I) { PHINode *Phi = I->first; - SmallVector &Indexes = I->second; + SmallVectorImpl &Indexes = I->second; if (Indexes.size() < 2) continue; @@ -3209,58 +3331,47 @@ static Constant *LookupConstant(Value *V, /// simple instructions such as binary operations where both operands are /// constant or can be replaced by constants from the ConstantPool. Returns the /// resulting constant on success, 0 otherwise. -static Constant *ConstantFold(Instruction *I, - const SmallDenseMap& ConstantPool) { - if (BinaryOperator *BO = dyn_cast(I)) { - Constant *A = LookupConstant(BO->getOperand(0), ConstantPool); - if (!A) - return 0; - Constant *B = LookupConstant(BO->getOperand(1), ConstantPool); - if (!B) - return 0; - return ConstantExpr::get(BO->getOpcode(), A, B); - } - - if (CmpInst *Cmp = dyn_cast(I)) { - Constant *A = LookupConstant(I->getOperand(0), ConstantPool); - if (!A) - return 0; - Constant *B = LookupConstant(I->getOperand(1), ConstantPool); - if (!B) - return 0; - return ConstantExpr::getCompare(Cmp->getPredicate(), A, B); - } - +static Constant * +ConstantFold(Instruction *I, + const SmallDenseMap &ConstantPool, + const DataLayout *DL) { if (SelectInst *Select = dyn_cast(I)) { Constant *A = LookupConstant(Select->getCondition(), ConstantPool); if (!A) - return 0; + return nullptr; if (A->isAllOnesValue()) return LookupConstant(Select->getTrueValue(), ConstantPool); if (A->isNullValue()) return LookupConstant(Select->getFalseValue(), ConstantPool); - return 0; + return nullptr; } - if (CastInst *Cast = dyn_cast(I)) { - Constant *A = LookupConstant(I->getOperand(0), ConstantPool); - if (!A) - return 0; - return ConstantExpr::getCast(Cast->getOpcode(), A, Cast->getDestTy()); + SmallVector COps; + for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) { + if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool)) + COps.push_back(A); + else + return nullptr; } - return 0; + if (CmpInst *Cmp = dyn_cast(I)) + return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0], + COps[1], DL); + + return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL); } /// GetCaseResults - Try to determine the resulting constant values in phi nodes /// at the common destination basic block, *CommonDest, for one of the case /// destionations CaseDest corresponding to value CaseVal (0 for the default /// case), of a switch instruction SI. -static bool GetCaseResults(SwitchInst *SI, - ConstantInt *CaseVal, - BasicBlock *CaseDest, - BasicBlock **CommonDest, - SmallVector, 4> &Res) { +static bool +GetCaseResults(SwitchInst *SI, + ConstantInt *CaseVal, + BasicBlock *CaseDest, + BasicBlock **CommonDest, + SmallVectorImpl > &Res, + const DataLayout *DL) { // The block from which we enter the common destination. BasicBlock *Pred = SI->getParent(); @@ -3279,7 +3390,7 @@ static bool GetCaseResults(SwitchInst *SI, } else if (isa(I)) { // Skip debug intrinsic. continue; - } else if (Constant *C = ConstantFold(I, ConstantPool)) { + } else if (Constant *C = ConstantFold(I, ConstantPool, DL)) { // Instruction is side-effect free and constant. ConstantPool.insert(std::make_pair(I, C)); } else { @@ -3319,7 +3430,7 @@ static bool GetCaseResults(SwitchInst *SI, Res.push_back(std::make_pair(PHI, ConstVal)); } - return true; + return Res.size() > 0; } namespace { @@ -3333,9 +3444,9 @@ namespace { SwitchLookupTable(Module &M, uint64_t TableSize, ConstantInt *Offset, - const SmallVector, 4>& Values, + const SmallVectorImpl >& Values, Constant *DefaultValue, - const DataLayout *TD); + const DataLayout *DL); /// BuildLookup - Build instructions with Builder to retrieve the value at /// the position given by Index in the lookup table. @@ -3343,7 +3454,7 @@ namespace { /// WouldFitInRegister - Return true if a table with TableSize elements of /// type ElementType would fit in a target-legal register. - static bool WouldFitInRegister(const DataLayout *TD, + static bool WouldFitInRegister(const DataLayout *DL, uint64_t TableSize, const Type *ElementType); @@ -3380,39 +3491,45 @@ namespace { SwitchLookupTable::SwitchLookupTable(Module &M, uint64_t TableSize, ConstantInt *Offset, - const SmallVector, 4>& Values, + const SmallVectorImpl >& Values, Constant *DefaultValue, - const DataLayout *TD) { + const DataLayout *DL) + : SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr), + Array(nullptr) { assert(Values.size() && "Can't build lookup table without values!"); assert(TableSize >= Values.size() && "Can't fit values in table!"); // If all values in the table are equal, this is that value. SingleValue = Values.begin()->second; + Type *ValueType = Values.begin()->second->getType(); + // Build up the table contents. SmallVector TableContents(TableSize); for (size_t I = 0, E = Values.size(); I != E; ++I) { ConstantInt *CaseVal = Values[I].first; Constant *CaseRes = Values[I].second; - assert(CaseRes->getType() == DefaultValue->getType()); + assert(CaseRes->getType() == ValueType); uint64_t Idx = (CaseVal->getValue() - Offset->getValue()) .getLimitedValue(); TableContents[Idx] = CaseRes; if (CaseRes != SingleValue) - SingleValue = 0; + SingleValue = nullptr; } // Fill in any holes in the table with the default result. if (Values.size() < TableSize) { + assert(DefaultValue && "Need a default value to fill the lookup table holes."); + assert(DefaultValue->getType() == ValueType); for (uint64_t I = 0; I < TableSize; ++I) { if (!TableContents[I]) TableContents[I] = DefaultValue; } if (DefaultValue != SingleValue) - SingleValue = 0; + SingleValue = nullptr; } // If each element in the table contains the same value, we only need to store @@ -3423,8 +3540,8 @@ SwitchLookupTable::SwitchLookupTable(Module &M, } // If the type is integer and the table fits in a register, build a bitmap. - if (WouldFitInRegister(TD, TableSize, DefaultValue->getType())) { - IntegerType *IT = cast(DefaultValue->getType()); + if (WouldFitInRegister(DL, TableSize, ValueType)) { + IntegerType *IT = cast(ValueType); APInt TableInt(TableSize * IT->getBitWidth(), 0); for (uint64_t I = TableSize; I > 0; --I) { TableInt <<= IT->getBitWidth(); @@ -3442,7 +3559,7 @@ SwitchLookupTable::SwitchLookupTable(Module &M, } // Store the table in an array. - ArrayType *ArrayTy = ArrayType::get(DefaultValue->getType(), TableSize); + ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); Array = new GlobalVariable(M, ArrayTy, /*constant=*/ true, @@ -3488,10 +3605,10 @@ Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { llvm_unreachable("Unknown lookup table kind!"); } -bool SwitchLookupTable::WouldFitInRegister(const DataLayout *TD, +bool SwitchLookupTable::WouldFitInRegister(const DataLayout *DL, uint64_t TableSize, const Type *ElementType) { - if (!TD) + if (!DL) return false; const IntegerType *IT = dyn_cast(ElementType); if (!IT) @@ -3502,31 +3619,52 @@ bool SwitchLookupTable::WouldFitInRegister(const DataLayout *TD, // Avoid overflow, fitsInLegalInteger uses unsigned int for the width. if (TableSize >= UINT_MAX/IT->getBitWidth()) return false; - return TD->fitsInLegalInteger(TableSize * IT->getBitWidth()); + return DL->fitsInLegalInteger(TableSize * IT->getBitWidth()); } /// ShouldBuildLookupTable - Determine whether a lookup table should be built -/// for this switch, based on the number of caes, size of the table and the +/// for this switch, based on the number of cases, size of the table and the /// types of the results. static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, - const DataLayout *TD, + const TargetTransformInfo &TTI, + const DataLayout *DL, const SmallDenseMap& ResultTypes) { - // The table density should be at least 40%. This is the same criterion as for - // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. - // FIXME: Find the best cut-off. if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) return false; // TableSize overflowed, or mul below might overflow. - if (SI->getNumCases() * 10 >= TableSize * 4) - return true; - // If each table would fit in a register, we should build it anyway. + bool AllTablesFitInRegister = true; + bool HasIllegalType = false; for (SmallDenseMap::const_iterator I = ResultTypes.begin(), E = ResultTypes.end(); I != E; ++I) { - if (!SwitchLookupTable::WouldFitInRegister(TD, TableSize, I->second)) - return false; + Type *Ty = I->second; + + // Saturate this flag to true. + HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); + + // Saturate this flag to false. + AllTablesFitInRegister = AllTablesFitInRegister && + SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty); + + // If both flags saturate, we're done. NOTE: This *only* works with + // saturating flags, and all flags have to saturate first due to the + // non-deterministic behavior of iterating over a dense map. + if (HasIllegalType && !AllTablesFitInRegister) + break; } - return true; + + // If each table would fit in a register, we should build it anyway. + if (AllTablesFitInRegister) + return true; + + // Don't build a table that doesn't fit in-register if it has illegal types. + if (HasIllegalType) + return false; + + // The table density should be at least 40%. This is the same criterion as for + // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. + // FIXME: Find the best cut-off. + return SI->getNumCases() * 10 >= TableSize * 4; } /// SwitchToLookupTable - If the switch is only used to initialize one or more @@ -3534,13 +3672,12 @@ static bool ShouldBuildLookupTable(SwitchInst *SI, /// replace the switch with lookup tables. static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, - const DataLayout* TD, - const TargetTransformInfo *TTI) { + const TargetTransformInfo &TTI, + const DataLayout* DL) { assert(SI->getNumCases() > 1 && "Degenerate switch?"); // Only build lookup table when we have a target that supports it. - if (!TTI || !TTI->getScalarTargetTransformInfo() || - !TTI->getScalarTargetTransformInfo()->shouldBuildLookupTables()) + if (!TTI.shouldBuildLookupTables()) return false; // FIXME: If the switch is too sparse for a lookup table, perhaps we could @@ -3550,11 +3687,9 @@ static bool SwitchToLookupTable(SwitchInst *SI, // GEP needs a runtime relocation in PIC code. We should just build one big // string and lookup indices into that. - // Ignore the switch if the number of cases is too small. - // This is similar to the check when building jump tables in - // SelectionDAGBuilder::handleJTSwitchCase. - // FIXME: Determine the best cut-off. - if (SI->getNumCases() < 4) + // Ignore switches with less than three cases. Lookup tables will not make them + // faster, so we don't analyze them. + if (SI->getNumCases() < 3) return false; // Figure out the corresponding result for each case value and phi node in the @@ -3564,7 +3699,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, ConstantInt *MinCaseVal = CI.getCaseValue(); ConstantInt *MaxCaseVal = CI.getCaseValue(); - BasicBlock *CommonDest = 0; + BasicBlock *CommonDest = nullptr; typedef SmallVector, 4> ResultListTy; SmallDenseMap ResultLists; SmallDenseMap DefaultResults; @@ -3582,7 +3717,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, typedef SmallVector, 4> ResultsTy; ResultsTy Results; if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest, - Results)) + Results, DL)) return false; // Append the result from this case to the list for each phi. @@ -3593,21 +3728,41 @@ static bool SwitchToLookupTable(SwitchInst *SI, } } - // Get the resulting values for the default case. + // Keep track of the result types. + for (size_t I = 0, E = PHIs.size(); I != E; ++I) { + PHINode *PHI = PHIs[I]; + ResultTypes[PHI] = ResultLists[PHI][0].second->getType(); + } + + uint64_t NumResults = ResultLists[PHIs[0]].size(); + APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); + uint64_t TableSize = RangeSpread.getLimitedValue() + 1; + bool TableHasHoles = (NumResults < TableSize); + + // If the table has holes, we need a constant result for the default case + // or a bitmask that fits in a register. SmallVector, 4> DefaultResultsList; - if (!GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest, - DefaultResultsList)) - return false; + bool HasDefaultResults = false; + if (TableHasHoles) { + HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(), + &CommonDest, DefaultResultsList, DL); + } + bool NeedMask = (TableHasHoles && !HasDefaultResults); + if (NeedMask) { + // As an extra penalty for the validity test we require more cases. + if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). + return false; + if (!(DL && DL->fitsInLegalInteger(TableSize))) + return false; + } + for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) { PHINode *PHI = DefaultResultsList[I].first; Constant *Result = DefaultResultsList[I].second; DefaultResults[PHI] = Result; - ResultTypes[PHI] = Result->getType(); } - APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); - uint64_t TableSize = RangeSpread.getLimitedValue() + 1; - if (!ShouldBuildLookupTable(SI, TableSize, TD, ResultTypes)) + if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes)) return false; // Create the BB that does the lookups. @@ -3617,30 +3772,90 @@ static bool SwitchToLookupTable(SwitchInst *SI, CommonDest->getParent(), CommonDest); - // Check whether the condition value is within the case range, and branch to - // the new BB. + // Compute the table index value. Builder.SetInsertPoint(SI); Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx"); - Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( - MinCaseVal->getType(), TableSize)); - Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); + + // Compute the maximum table size representable by the integer type we are + // switching upon. + unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); + uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize; + assert(MaxTableSize >= TableSize && + "It is impossible for a switch to have more entries than the max " + "representable value of its input integer type's size."); + + // If we have a fully covered lookup table, unconditionally branch to the + // lookup table BB. Otherwise, check if the condition value is within the case + // range. If it is so, branch to the new BB. Otherwise branch to SI's default + // destination. + const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize; + if (GeneratingCoveredLookupTable) { + Builder.CreateBr(LookupBB); + SI->getDefaultDest()->removePredecessor(SI->getParent()); + } else { + Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( + MinCaseVal->getType(), TableSize)); + Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); + } // Populate the BB that does the lookups. Builder.SetInsertPoint(LookupBB); + + if (NeedMask) { + // Before doing the lookup we do the hole check. + // The LookupBB is therefore re-purposed to do the hole check + // and we create a new LookupBB. + BasicBlock *MaskBB = LookupBB; + MaskBB->setName("switch.hole_check"); + LookupBB = BasicBlock::Create(Mod.getContext(), + "switch.lookup", + CommonDest->getParent(), + CommonDest); + + // Build bitmask; fill in a 1 bit for every case. + APInt MaskInt(TableSize, 0); + APInt One(TableSize, 1); + const ResultListTy &ResultList = ResultLists[PHIs[0]]; + for (size_t I = 0, E = ResultList.size(); I != E; ++I) { + uint64_t Idx = (ResultList[I].first->getValue() - + MinCaseVal->getValue()).getLimitedValue(); + MaskInt |= One << Idx; + } + ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt); + + // Get the TableIndex'th bit of the bitmask. + // If this bit is 0 (meaning hole) jump to the default destination, + // else continue with table lookup. + IntegerType *MapTy = TableMask->getType(); + Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy, + "switch.maskindex"); + Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, + "switch.shifted"); + Value *LoBit = Builder.CreateTrunc(Shifted, + Type::getInt1Ty(Mod.getContext()), + "switch.lobit"); + Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest()); + + Builder.SetInsertPoint(LookupBB); + AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent()); + } + bool ReturnedEarly = false; for (size_t I = 0, E = PHIs.size(); I != E; ++I) { PHINode *PHI = PHIs[I]; + // If using a bitmask, use any value to fill the lookup table holes. + Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI]; SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI], - DefaultResults[PHI], TD); + DV, DL); Value *Result = Table.BuildLookup(TableIndex, Builder); // If the result is used to return immediately from the function, we want to // do that right here. - if (PHI->hasOneUse() && isa(*PHI->use_begin()) && - *PHI->use_begin() == CommonDest->getFirstNonPHIOrDbg()) { + if (PHI->hasOneUse() && isa(*PHI->user_begin()) && + PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) { Builder.CreateRet(Result); ReturnedEarly = true; break; @@ -3653,14 +3868,18 @@ static bool SwitchToLookupTable(SwitchInst *SI, Builder.CreateBr(CommonDest); // Remove the switch. - for (unsigned i = 0; i < SI->getNumSuccessors(); ++i) { + for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { BasicBlock *Succ = SI->getSuccessor(i); - if (Succ == SI->getDefaultDest()) continue; + + if (Succ == SI->getDefaultDest()) + continue; Succ->removePredecessor(SI->getParent()); } SI->eraseFromParent(); ++NumLookupTables; + if (NeedMask) + ++NumLookupTablesHoles; return true; } @@ -3672,12 +3891,12 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { // see if that predecessor totally determines the outcome of this switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; Value *Cond = SI->getCondition(); if (SelectInst *Select = dyn_cast(Cond)) if (SimplifySwitchOnSelect(SI, Select)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; // If the block only contains the switch, see if we can fold the block // away into any preds. @@ -3687,22 +3906,22 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { ++BBI; if (SI == &*BBI) if (FoldValueComparisonIntoPredecessors(SI, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; // Remove unreachable cases. if (EliminateDeadSwitchCases(SI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; if (ForwardSwitchConditionToPHI(SI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; - if (SwitchToLookupTable(SI, Builder, TD, TTI)) - return SimplifyCFG(BB) | true; + if (SwitchToLookupTable(SI, Builder, TTI, DL)) + return SimplifyCFG(BB, TTI, DL) | true; return false; } @@ -3739,7 +3958,7 @@ bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { if (SelectInst *SI = dyn_cast(IBI->getAddress())) { if (SimplifyIndirectBrOnSelect(IBI, SI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } return Changed; } @@ -3763,7 +3982,7 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ for (++I; isa(I); ++I) ; if (I->isTerminator() && - TryToSimplifyUncondBranchWithICmpInIt(ICI, TD, Builder)) + TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI, DL)) return true; } @@ -3772,7 +3991,7 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ // predecessor and use logical operations to update the incoming value // for PHI nodes in common successor. if (FoldBranchToCommonDest(BI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; return false; } @@ -3787,7 +4006,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { // switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; // This block must be empty, except for the setcond inst, if it exists. // Ignore dbg intrinsics. @@ -3797,35 +4016,35 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { ++I; if (&*I == BI) { if (FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } else if (&*I == cast(BI->getCondition())){ ++I; // Ignore dbg intrinsics. while (isa(I)) ++I; if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } } // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. - if (SimplifyBranchOnICmpChain(BI, TD, Builder)) + if (SimplifyBranchOnICmpChain(BI, DL, Builder)) return true; // If this basic block is ONLY a compare and a branch, and if a predecessor // branches to us and one of our successors, fold the comparison into the // predecessor and use logical operations to pick the right destination. if (FoldBranchToCommonDest(BI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; // We have a conditional branch to two blocks that are only reachable // from BI. We know that the condbr dominates the two blocks, so see if // there is any identical code in the "then" and "else" blocks. If so, we // can hoist it up to the branching block. - if (BI->getSuccessor(0)->getSinglePredecessor() != 0) { - if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { + if (BI->getSuccessor(0)->getSinglePredecessor()) { + if (BI->getSuccessor(1)->getSinglePredecessor()) { if (HoistThenElseCodeToIf(BI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } else { // If Successor #1 has multiple preds, we may be able to conditionally // execute Successor #0 if it branches to successor #1. @@ -3833,31 +4052,31 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (Succ0TI->getNumSuccessors() == 1 && Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0))) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } - } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { + } else if (BI->getSuccessor(1)->getSinglePredecessor()) { // If Successor #0 has multiple preds, we may be able to conditionally // execute Successor #1 if it branches to successor #0. TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); if (Succ1TI->getNumSuccessors() == 1 && Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1))) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; } // If this is a branch on a phi node in the current block, thread control // through this block if any PHI node entries are constants. if (PHINode *PN = dyn_cast(BI->getCondition())) if (PN->getParent() == BI->getParent()) - if (FoldCondBranchOnPHI(BI, TD)) - return SimplifyCFG(BB) | true; + if (FoldCondBranchOnPHI(BI, DL)) + return SimplifyCFG(BB, TTI, DL) | true; // Scan predecessor blocks for conditional branches. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) if (BranchInst *PBI = dyn_cast((*PI)->getTerminator())) if (PBI != BI && PBI->isConditional()) if (SimplifyCondBranchToCondBranch(PBI, BI)) - return SimplifyCFG(BB) | true; + return SimplifyCFG(BB, TTI, DL) | true; return false; } @@ -3873,7 +4092,7 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { if (C->isNullValue()) { // Only look at the first use, avoid hurting compile time with long uselists - User *Use = *I->use_begin(); + User *Use = *I->user_begin(); // Now make sure that there are no instructions in between that can alter // control flow (eg. calls) @@ -3892,11 +4111,13 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { // Load from null is undefined. if (LoadInst *LI = dyn_cast(Use)) - return LI->getPointerAddressSpace() == 0; + if (!LI->isVolatile()) + return LI->getPointerAddressSpace() == 0; // Store to null is undefined. if (StoreInst *SI = dyn_cast(Use)) - return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; + if (!SI->isVolatile()) + return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; } return false; } @@ -3967,7 +4188,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { // eliminate it, do so now. if (PHINode *PN = dyn_cast(BB->begin())) if (PN->getNumIncomingValues() == 2) - Changed |= FoldTwoEntryPHINode(PN, TD); + Changed |= FoldTwoEntryPHINode(PN, DL); Builder.SetInsertPoint(BB->getTerminator()); if (BranchInst *BI = dyn_cast(BB->getTerminator())) { @@ -3998,7 +4219,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { /// eliminates unreachable basic blocks, and does other "peephole" optimization /// of the CFG. It returns true if a modification was made. /// -bool llvm::SimplifyCFG(BasicBlock *BB, const DataLayout *TD, - const TargetTransformInfo *TTI) { - return SimplifyCFGOpt(TD, TTI).run(BB); +bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, + const DataLayout *DL) { + return SimplifyCFGOpt(TTI, DL).run(BB); }