diff options
Diffstat (limited to 'lib/Transforms/Utils/SimplifyCFG.cpp')
| -rw-r--r-- | lib/Transforms/Utils/SimplifyCFG.cpp | 1741 |
1 files changed, 989 insertions, 752 deletions
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index e484b690597e9..0504646c304ef 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -11,7 +11,6 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetOperations.h" @@ -45,6 +44,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include <algorithm> #include <map> @@ -58,17 +58,18 @@ using namespace PatternMatch; // a select, so the "clamp" idiom (of a min followed by a max) will be caught. // To catch this, we need to fold a compare and a select, hence '2' being the // minimum reasonable default. -static cl::opt<unsigned> -PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), - cl::desc("Control the amount of phi node folding to perform (default = 2)")); +static cl::opt<unsigned> PHINodeFoldingThreshold( + "phi-node-folding-threshold", cl::Hidden, cl::init(2), + cl::desc( + "Control the amount of phi node folding to perform (default = 2)")); -static cl::opt<bool> -DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), - cl::desc("Duplicate return instructions into unconditional branches")); +static cl::opt<bool> DupRet( + "simplifycfg-dup-ret", cl::Hidden, cl::init(false), + cl::desc("Duplicate return instructions into unconditional branches")); static cl::opt<bool> -SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), - cl::desc("Sink common instructions down to the end block")); + SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), + cl::desc("Sink common instructions down to the end block")); static cl::opt<bool> HoistCondStores( "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), @@ -96,48 +97,54 @@ static cl::opt<unsigned> MaxSpeculationDepth( "speculatively executed instructions")); STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); -STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping"); -STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); -STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)"); +STATISTIC(NumLinearMaps, + "Number of switch instructions turned into linear mapping"); +STATISTIC(NumLookupTables, + "Number of switch instructions turned into lookup tables"); +STATISTIC( + NumLookupTablesHoles, + "Number of switch instructions turned into lookup tables (holes checked)"); STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares"); -STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); +STATISTIC(NumSinkCommons, + "Number of common instructions sunk down to the end block"); STATISTIC(NumSpeculations, "Number of speculative executed instructions"); namespace { - // The first field contains the value that the switch produces when a certain - // case group is selected, and the second field is a vector containing the - // cases composing the case group. - typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2> +// The first field contains the value that the switch produces when a certain +// case group is selected, and the second field is a vector containing the +// cases composing the case group. +typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2> SwitchCaseResultVectorTy; - // The first field contains the phi node that generates a result of the switch - // and the second field contains the value generated for a certain case in the - // switch for that PHI. - typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy; +// The first field contains the phi node that generates a result of the switch +// and the second field contains the value generated for a certain case in the +// switch for that PHI. +typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy; - /// ValueEqualityComparisonCase - Represents a case of a switch. - struct ValueEqualityComparisonCase { - ConstantInt *Value; - BasicBlock *Dest; +/// ValueEqualityComparisonCase - Represents a case of a switch. +struct ValueEqualityComparisonCase { + ConstantInt *Value; + BasicBlock *Dest; - ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) + ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) : Value(Value), Dest(Dest) {} - bool operator<(ValueEqualityComparisonCase RHS) const { - // Comparing pointers is ok as we only rely on the order for uniquing. - return Value < RHS.Value; - } + bool operator<(ValueEqualityComparisonCase RHS) const { + // Comparing pointers is ok as we only rely on the order for uniquing. + return Value < RHS.Value; + } - bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; } - }; + bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; } +}; class SimplifyCFGOpt { const TargetTransformInfo &TTI; const DataLayout &DL; unsigned BonusInstThreshold; AssumptionCache *AC; + SmallPtrSetImpl<BasicBlock *> *LoopHeaders; Value *isValueEqualityComparison(TerminatorInst *TI); - BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, - std::vector<ValueEqualityComparisonCase> &Cases); + BasicBlock *GetValueEqualityComparisonCases( + TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases); bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, BasicBlock *Pred, IRBuilder<> &Builder); @@ -152,13 +159,15 @@ class SimplifyCFGOpt { bool SimplifyUnreachable(UnreachableInst *UI); bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); bool SimplifyIndirectBr(IndirectBrInst *IBI); - bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder); - bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder); + bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder); + bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder); public: SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, - unsigned BonusInstThreshold, AssumptionCache *AC) - : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {} + unsigned BonusInstThreshold, AssumptionCache *AC, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders) + : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC), + LoopHeaders(LoopHeaders) {} bool run(BasicBlock *BB); }; } @@ -166,19 +175,19 @@ public: /// Return true if it is safe to merge these two /// terminator instructions together. static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { - if (SI1 == SI2) return false; // Can't merge with self! + if (SI1 == SI2) + return false; // Can't merge with self! // It is not safe to merge these two switch instructions if they have a common // successor, and if that successor has a PHI node, and if *that* PHI node has // conflicting incoming values from the two switch blocks. BasicBlock *SI1BB = SI1->getParent(); BasicBlock *SI2BB = SI2->getParent(); - SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); + SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); - for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) - if (SI1Succs.count(*I)) - for (BasicBlock::iterator BBI = (*I)->begin(); - isa<PHINode>(BBI); ++BBI) { + for (BasicBlock *Succ : successors(SI2BB)) + if (SI1Succs.count(Succ)) + for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { PHINode *PN = cast<PHINode>(BBI); if (PN->getIncomingValueForBlock(SI1BB) != PN->getIncomingValueForBlock(SI2BB)) @@ -191,11 +200,12 @@ static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { /// Return true if it is safe and profitable to merge these two terminator /// instructions together, where SI1 is an unconditional branch. PhiNodes will /// store all PHI nodes in common successors. -static bool isProfitableToFoldUnconditional(BranchInst *SI1, - BranchInst *SI2, - Instruction *Cond, - SmallVectorImpl<PHINode*> &PhiNodes) { - if (SI1 == SI2) return false; // Can't merge with self! +static bool +isProfitableToFoldUnconditional(BranchInst *SI1, BranchInst *SI2, + Instruction *Cond, + SmallVectorImpl<PHINode *> &PhiNodes) { + if (SI1 == SI2) + return false; // Can't merge with self! assert(SI1->isUnconditional() && SI2->isConditional()); // We fold the unconditional branch if we can easily update all PHI nodes in @@ -204,7 +214,8 @@ static bool isProfitableToFoldUnconditional(BranchInst *SI1, // 2> We have "Cond" as the incoming value for the unconditional branch; // 3> SI2->getCondition() and Cond have same operands. CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); - if (!Ci2) return false; + if (!Ci2) + return false; if (!(Cond->getOperand(0) == Ci2->getOperand(0) && Cond->getOperand(1) == Ci2->getOperand(1)) && !(Cond->getOperand(0) == Ci2->getOperand(1) && @@ -213,11 +224,10 @@ static bool isProfitableToFoldUnconditional(BranchInst *SI1, BasicBlock *SI1BB = SI1->getParent(); BasicBlock *SI2BB = SI2->getParent(); - SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); - for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) - if (SI1Succs.count(*I)) - for (BasicBlock::iterator BBI = (*I)->begin(); - isa<PHINode>(BBI); ++BBI) { + SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); + for (BasicBlock *Succ : successors(SI2BB)) + if (SI1Succs.count(Succ)) + for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) { PHINode *PN = cast<PHINode>(BBI); if (PN->getIncomingValueForBlock(SI1BB) != Cond || !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) @@ -233,11 +243,11 @@ static bool isProfitableToFoldUnconditional(BranchInst *SI1, /// of Succ. static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred) { - if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do + if (!isa<PHINode>(Succ->begin())) + return; // Quick exit if nothing to do PHINode *PN; - for (BasicBlock::iterator I = Succ->begin(); - (PN = dyn_cast<PHINode>(I)); ++I) + for (BasicBlock::iterator I = Succ->begin(); (PN = dyn_cast<PHINode>(I)); ++I) PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); } @@ -270,7 +280,7 @@ static unsigned ComputeSpeculationCost(const User *I, /// V plus its non-dominating operands. If that cost is greater than /// CostRemaining, false is returned and CostRemaining is undefined. static bool DominatesMergePoint(Value *V, BasicBlock *BB, - SmallPtrSetImpl<Instruction*> *AggressiveInsts, + SmallPtrSetImpl<Instruction *> *AggressiveInsts, unsigned &CostRemaining, const TargetTransformInfo &TTI, unsigned Depth = 0) { @@ -294,7 +304,8 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, // We don't want to allow weird loops that might have the "if condition" in // the bottom of this block. - if (PBB == BB) return false; + if (PBB == BB) + return false; // If this instruction is defined in a block that contains an unconditional // branch to BB, then it must be in the 'conditional' part of the "if @@ -305,10 +316,12 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, // If we aren't allowing aggressive promotion anymore, then don't consider // instructions in the 'if region'. - if (!AggressiveInsts) return false; + if (!AggressiveInsts) + return false; // If we have seen this instruction before, don't count it again. - if (AggressiveInsts->count(I)) return true; + if (AggressiveInsts->count(I)) + return true; // Okay, it looks like the instruction IS in the "condition". Check to // see if it's a cheap instruction to unconditionally compute, and if it @@ -366,8 +379,8 @@ static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) { if (CI->getType() == PtrTy) return CI; else - return cast<ConstantInt> - (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); + return cast<ConstantInt>( + ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); } return nullptr; } @@ -403,11 +416,11 @@ struct ConstantComparesGatherer { operator=(const ConstantComparesGatherer &) = delete; private: - /// Try to set the current value used for the comparison, it succeeds only if /// it wasn't set before or if the new value is the same as the old one bool setValueOnce(Value *NewVal) { - if(CompValue && CompValue != NewVal) return false; + if (CompValue && CompValue != NewVal) + return false; CompValue = NewVal; return (CompValue != nullptr); } @@ -424,35 +437,99 @@ private: ICmpInst *ICI; ConstantInt *C; if (!((ICI = dyn_cast<ICmpInst>(I)) && - (C = GetConstantInt(I->getOperand(1), DL)))) { + (C = GetConstantInt(I->getOperand(1), DL)))) { return false; } Value *RHSVal; - ConstantInt *RHSC; + const APInt *RHSC; // Pattern match a special case - // (x & ~2^x) == y --> x == y || x == y|2^x + // (x & ~2^z) == y --> x == y || x == y|2^z // This undoes a transformation done by instcombine to fuse 2 compares. - if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { + if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) { + + // It's a little bit hard to see why the following transformations are + // correct. Here is a CVC3 program to verify them for 64-bit values: + + /* + ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63); + x : BITVECTOR(64); + y : BITVECTOR(64); + z : BITVECTOR(64); + mask : BITVECTOR(64) = BVSHL(ONE, z); + QUERY( (y & ~mask = y) => + ((x & ~mask = y) <=> (x = y OR x = (y | mask))) + ); + QUERY( (y | mask = y) => + ((x | mask = y) <=> (x = y OR x = (y & ~mask))) + ); + */ + + // Please note that each pattern must be a dual implication (<--> or + // iff). One directional implication can create spurious matches. If the + // implication is only one-way, an unsatisfiable condition on the left + // side can imply a satisfiable condition on the right side. Dual + // implication ensures that satisfiable conditions are transformed to + // other satisfiable conditions and unsatisfiable conditions are + // transformed to other unsatisfiable conditions. + + // Here is a concrete example of a unsatisfiable condition on the left + // implying a satisfiable condition on the right: + // + // mask = (1 << z) + // (x & ~mask) == y --> (x == y || x == (y | mask)) + // + // Substituting y = 3, z = 0 yields: + // (x & -2) == 3 --> (x == 3 || x == 2) + + // Pattern match a special case: + /* + QUERY( (y & ~mask = y) => + ((x & ~mask = y) <=> (x = y OR x = (y | mask))) + ); + */ if (match(ICI->getOperand(0), - m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) { - APInt Not = ~RHSC->getValue(); - if (Not.isPowerOf2()) { + m_And(m_Value(RHSVal), m_APInt(RHSC)))) { + APInt Mask = ~*RHSC; + if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) { // If we already have a value for the switch, it has to match! - if(!setValueOnce(RHSVal)) + if (!setValueOnce(RHSVal)) + return false; + + Vals.push_back(C); + Vals.push_back( + ConstantInt::get(C->getContext(), + C->getValue() | Mask)); + UsedICmps++; + return true; + } + } + + // Pattern match a special case: + /* + QUERY( (y | mask = y) => + ((x | mask = y) <=> (x = y OR x = (y & ~mask))) + ); + */ + if (match(ICI->getOperand(0), + m_Or(m_Value(RHSVal), m_APInt(RHSC)))) { + APInt Mask = *RHSC; + if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) { + // If we already have a value for the switch, it has to match! + if (!setValueOnce(RHSVal)) return false; Vals.push_back(C); Vals.push_back(ConstantInt::get(C->getContext(), - C->getValue() | Not)); + C->getValue() & ~Mask)); UsedICmps++; return true; } } // If we already have a value for the switch, it has to match! - if(!setValueOnce(ICI->getOperand(0))) + if (!setValueOnce(ICI->getOperand(0))) return false; UsedICmps++; @@ -467,8 +544,8 @@ private: // Shift the range if the compare is fed by an add. This is the range // compare idiom as emitted by instcombine. Value *CandidateVal = I->getOperand(0); - if(match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)))) { - Span = Span.subtract(RHSC->getValue()); + if (match(I->getOperand(0), m_Add(m_Value(RHSVal), m_APInt(RHSC)))) { + Span = Span.subtract(*RHSC); CandidateVal = RHSVal; } @@ -484,7 +561,7 @@ private: } // If we already have a value for the switch, it has to match! - if(!setValueOnce(CandidateVal)) + if (!setValueOnce(CandidateVal)) return false; // Add all values from the range to the set @@ -493,7 +570,6 @@ private: UsedICmps++; return true; - } /// Given a potentially 'or'd or 'and'd together collection of icmp @@ -507,18 +583,22 @@ private: // Keep a stack (SmallVector for efficiency) for depth-first traversal SmallVector<Value *, 8> DFT; + SmallPtrSet<Value *, 8> Visited; // Initialize + Visited.insert(V); DFT.push_back(V); - while(!DFT.empty()) { + while (!DFT.empty()) { V = DFT.pop_back_val(); if (Instruction *I = dyn_cast<Instruction>(V)) { // If it is a || (or && depending on isEQ), process the operands. if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) { - DFT.push_back(I->getOperand(1)); - DFT.push_back(I->getOperand(0)); + if (Visited.insert(I->getOperand(1)).second) + DFT.push_back(I->getOperand(1)); + if (Visited.insert(I->getOperand(0)).second) + DFT.push_back(I->getOperand(0)); continue; } @@ -541,7 +621,6 @@ private: } } }; - } static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { @@ -556,7 +635,8 @@ static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { } TI->eraseFromParent(); - if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); + if (Cond) + RecursivelyDeleteTriviallyDeadInstructions(Cond); } /// Return true if the specified terminator checks @@ -566,8 +646,9 @@ Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { // Do not permit merging of large switch instructions into their // predecessors unless there is only one predecessor. - if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), - pred_end(SI->getParent())) <= 128) + if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), + pred_end(SI->getParent())) <= + 128) CV = SI->getCondition(); } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) if (BI->isConditional() && BI->getCondition()->hasOneUse()) @@ -589,46 +670,44 @@ Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { /// Given a value comparison instruction, /// decode all of the 'cases' that it represents and return the 'default' block. -BasicBlock *SimplifyCFGOpt:: -GetValueEqualityComparisonCases(TerminatorInst *TI, - std::vector<ValueEqualityComparisonCase> - &Cases) { +BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases( + TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases) { if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { Cases.reserve(SI->getNumCases()); - for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) - Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(), - i.getCaseSuccessor())); + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; + ++i) + Cases.push_back( + ValueEqualityComparisonCase(i.getCaseValue(), i.getCaseSuccessor())); return SI->getDefaultDest(); } BranchInst *BI = cast<BranchInst>(TI); ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); - Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1), - DL), - Succ)); + Cases.push_back(ValueEqualityComparisonCase( + GetConstantInt(ICI->getOperand(1), DL), Succ)); return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); } - /// Given a vector of bb/value pairs, remove any entries /// in the list that match the specified block. -static void EliminateBlockCases(BasicBlock *BB, - std::vector<ValueEqualityComparisonCase> &Cases) { +static void +EliminateBlockCases(BasicBlock *BB, + std::vector<ValueEqualityComparisonCase> &Cases) { Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end()); } /// Return true if there are any keys in C1 that exist in C2 as well. -static bool -ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, - std::vector<ValueEqualityComparisonCase > &C2) { +static bool ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, + std::vector<ValueEqualityComparisonCase> &C2) { std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2; // Make V1 be smaller than V2. if (V1->size() > V2->size()) std::swap(V1, V2); - if (V1->size() == 0) return false; + if (V1->size() == 0) + return false; if (V1->size() == 1) { // Just scan V2. ConstantInt *TheVal = (*V1)[0].Value; @@ -657,30 +736,30 @@ ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, /// also a value comparison with the same value, and if that comparison /// determines the outcome of this comparison. If so, simplify TI. This does a /// very limited form of jump threading. -bool SimplifyCFGOpt:: -SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, - BasicBlock *Pred, - IRBuilder<> &Builder) { +bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor( + TerminatorInst *TI, BasicBlock *Pred, IRBuilder<> &Builder) { Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); - if (!PredVal) return false; // Not a value comparison in predecessor. + if (!PredVal) + return false; // Not a value comparison in predecessor. Value *ThisVal = isValueEqualityComparison(TI); assert(ThisVal && "This isn't a value comparison!!"); - if (ThisVal != PredVal) return false; // Different predicates. + if (ThisVal != PredVal) + return false; // Different predicates. // TODO: Preserve branch weight metadata, similarly to how // FoldValueComparisonIntoPredecessors preserves it. // Find out information about when control will move from Pred to TI's block. std::vector<ValueEqualityComparisonCase> PredCases; - BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), - PredCases); - EliminateBlockCases(PredDef, PredCases); // Remove default from cases. + BasicBlock *PredDef = + GetValueEqualityComparisonCases(Pred->getTerminator(), PredCases); + EliminateBlockCases(PredDef, PredCases); // Remove default from cases. // Find information about how control leaves this block. std::vector<ValueEqualityComparisonCase> ThisCases; BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); - EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. + EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. // If TI's block is the default block from Pred's comparison, potentially // simplify TI based on this knowledge. @@ -697,13 +776,14 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, assert(ThisCases.size() == 1 && "Branch can only have one case!"); // Insert the new branch. Instruction *NI = Builder.CreateBr(ThisDef); - (void) NI; + (void)NI; // Remove PHI node entries for the dead edge. ThisCases[0].Dest->removePredecessor(TI->getParent()); DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); + << "Through successor TI: " << *TI << "Leaving: " << *NI + << "\n"); EraseTerminatorInstAndDCECond(TI); return true; @@ -711,7 +791,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, SwitchInst *SI = cast<SwitchInst>(TI); // Okay, TI has cases that are statically dead, prune them away. - SmallPtrSet<Constant*, 16> DeadCases; + SmallPtrSet<Constant *, 16> DeadCases; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) DeadCases.insert(PredCases[i].Value); @@ -732,7 +812,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, --i; if (DeadCases.count(i.getCaseValue())) { if (HasWeight) { - std::swap(Weights[i.getCaseIndex()+1], Weights.back()); + std::swap(Weights[i.getCaseIndex() + 1], Weights.back()); Weights.pop_back(); } i.getCaseSuccessor()->removePredecessor(TI->getParent()); @@ -741,8 +821,8 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, } if (HasWeight && Weights.size() >= 2) SI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getParent()->getContext()). - createBranchWeights(Weights)); + MDBuilder(SI->getParent()->getContext()) + .createBranchWeights(Weights)); DEBUG(dbgs() << "Leaving: " << *TI << "\n"); return true; @@ -755,7 +835,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].Dest == TIBB) { if (TIV) - return false; // Cannot handle multiple values coming to this block. + return false; // Cannot handle multiple values coming to this block. TIV = PredCases[i].Value; } assert(TIV && "No edge from pred to succ?"); @@ -770,53 +850,53 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, } // If not handled by any explicit cases, it is handled by the default case. - if (!TheRealDest) TheRealDest = ThisDef; + if (!TheRealDest) + TheRealDest = ThisDef; // Remove PHI node entries for dead edges. BasicBlock *CheckEdge = TheRealDest; - for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) - if (*SI != CheckEdge) - (*SI)->removePredecessor(TIBB); + for (BasicBlock *Succ : successors(TIBB)) + if (Succ != CheckEdge) + Succ->removePredecessor(TIBB); else CheckEdge = nullptr; // Insert the new branch. Instruction *NI = Builder.CreateBr(TheRealDest); - (void) NI; + (void)NI; DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); + << "Through successor TI: " << *TI << "Leaving: " << *NI + << "\n"); EraseTerminatorInstAndDCECond(TI); return true; } namespace { - /// This class implements a stable ordering of constant - /// integers that does not depend on their address. This is important for - /// applications that sort ConstantInt's to ensure uniqueness. - struct ConstantIntOrdering { - bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { - return LHS->getValue().ult(RHS->getValue()); - } - }; +/// This class implements a stable ordering of constant +/// integers that does not depend on their address. This is important for +/// applications that sort ConstantInt's to ensure uniqueness. +struct ConstantIntOrdering { + bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { + return LHS->getValue().ult(RHS->getValue()); + } +}; } 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()) + if (LHS == RHS) return 0; - return -1; + return LHS->getValue().ult(RHS->getValue()) ? 1 : -1; } -static inline bool HasBranchWeights(const Instruction* I) { +static inline bool HasBranchWeights(const Instruction *I) { MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof); if (ProfMD && ProfMD->getOperand(0)) - if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) + if (MDString *MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) return MDS->getString().equals("branch_weights"); return false; @@ -837,7 +917,7 @@ static void GetBranchWeights(TerminatorInst *TI, // If TI is a conditional eq, the default case is the false case, // and the corresponding branch-weight data is at index 2. We swap the // default weight to be the first entry. - if (BranchInst* BI = dyn_cast<BranchInst>(TI)) { + if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { assert(Weights.size() == 2); ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); if (ICI->getPredicate() == ICmpInst::ICMP_EQ) @@ -862,17 +942,17 @@ static void FitWeights(MutableArrayRef<uint64_t> Weights) { bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, IRBuilder<> &Builder) { BasicBlock *BB = TI->getParent(); - Value *CV = isValueEqualityComparison(TI); // CondVal + Value *CV = isValueEqualityComparison(TI); // CondVal assert(CV && "Not a comparison?"); bool Changed = false; - SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); + SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB)); while (!Preds.empty()) { BasicBlock *Pred = Preds.pop_back_val(); // See if the predecessor is a comparison with the same value. TerminatorInst *PTI = Pred->getTerminator(); - Value *PCV = isValueEqualityComparison(PTI); // PredCondVal + Value *PCV = isValueEqualityComparison(PTI); // PredCondVal if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { // Figure out which 'cases' to copy from SI to PSI. @@ -885,7 +965,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, // Based on whether the default edge from PTI goes to BB or not, fill in // PredCases and PredDefault with the new switch cases we would like to // build. - SmallVector<BasicBlock*, 8> NewSuccessors; + SmallVector<BasicBlock *, 8> NewSuccessors; // Update the branch weight metadata along the way SmallVector<uint64_t, 8> Weights; @@ -915,7 +995,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, if (PredDefault == BB) { // If this is the default destination from PTI, only the edges in TI // that don't occur in PTI, or that branch to BB will be activated. - std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; + std::set<ConstantInt *, ConstantIntOrdering> PTIHandled; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].Dest != BB) PTIHandled.insert(PredCases[i].Value); @@ -925,13 +1005,14 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, if (PredHasWeights || SuccHasWeights) { // Increase weight for the default case. - Weights[0] += Weights[i+1]; - std::swap(Weights[i+1], Weights.back()); + Weights[0] += Weights[i + 1]; + std::swap(Weights[i + 1], Weights.back()); Weights.pop_back(); } PredCases.pop_back(); - --i; --e; + --i; + --e; } // Reconstruct the new switch statement we will be building. @@ -952,8 +1033,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, // The default weight is at index 0, so weight for the ith case // should be at index i+1. Scale the cases from successor by // PredDefaultWeight (Weights[0]). - Weights.push_back(Weights[0] * SuccWeights[i+1]); - ValidTotalSuccWeight += SuccWeights[i+1]; + Weights.push_back(Weights[0] * SuccWeights[i + 1]); + ValidTotalSuccWeight += SuccWeights[i + 1]; } } @@ -969,21 +1050,22 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, // If this is not the default destination from PSI, only the edges // in SI that occur in PSI with a destination of BB will be // activated. - std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; - std::map<ConstantInt*, uint64_t> WeightsForHandled; + std::set<ConstantInt *, ConstantIntOrdering> PTIHandled; + std::map<ConstantInt *, uint64_t> WeightsForHandled; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].Dest == BB) { PTIHandled.insert(PredCases[i].Value); if (PredHasWeights || SuccHasWeights) { - WeightsForHandled[PredCases[i].Value] = Weights[i+1]; - std::swap(Weights[i+1], Weights.back()); + WeightsForHandled[PredCases[i].Value] = Weights[i + 1]; + std::swap(Weights[i + 1], Weights.back()); Weights.pop_back(); } std::swap(PredCases[i], PredCases.back()); PredCases.pop_back(); - --i; --e; + --i; + --e; } // Okay, now we know which constants were sent to BB from the @@ -995,17 +1077,16 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, Weights.push_back(WeightsForHandled[BBCases[i].Value]); PredCases.push_back(BBCases[i]); NewSuccessors.push_back(BBCases[i].Dest); - PTIHandled.erase(BBCases[i].Value);// This constant is taken care of + PTIHandled.erase( + BBCases[i].Value); // This constant is taken care of } // If there are any constants vectored to BB that TI doesn't handle, // they must go to the default destination of TI. - for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = - PTIHandled.begin(), - E = PTIHandled.end(); I != E; ++I) { + for (ConstantInt *I : PTIHandled) { if (PredHasWeights || SuccHasWeights) - Weights.push_back(WeightsForHandled[*I]); - PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault)); + Weights.push_back(WeightsForHandled[I]); + PredCases.push_back(ValueEqualityComparisonCase(I, BBDefault)); NewSuccessors.push_back(BBDefault); } } @@ -1024,8 +1105,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, } // Now that the successors are updated, create the new Switch instruction. - SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault, - PredCases.size()); + SwitchInst *NewSI = + Builder.CreateSwitch(CV, PredDefault, PredCases.size()); NewSI->setDebugLoc(PTI->getDebugLoc()); for (ValueEqualityComparisonCase &V : PredCases) NewSI->addCase(V.Value, V.Dest); @@ -1036,9 +1117,9 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); - NewSI->setMetadata(LLVMContext::MD_prof, - MDBuilder(BB->getContext()). - createBranchWeights(MDWeights)); + NewSI->setMetadata( + LLVMContext::MD_prof, + MDBuilder(BB->getContext()).createBranchWeights(MDWeights)); } EraseTerminatorInstAndDCECond(PTI); @@ -1052,8 +1133,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 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(), - "infloop", BB->getParent()); + InfLoopBlock = BasicBlock::Create(BB->getContext(), "infloop", + BB->getParent()); BranchInst::Create(InfLoopBlock, InfLoopBlock); } NewSI->setSuccessor(i, InfLoopBlock); @@ -1070,13 +1151,13 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, // can't hoist the invoke, as there is nowhere to put the select in this case. static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2) { - for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { + for (BasicBlock *Succ : successors(BB1)) { PHINode *PN; - for (BasicBlock::iterator BBI = SI->begin(); + for (BasicBlock::iterator BBI = Succ->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI) { Value *BB1V = PN->getIncomingValueForBlock(BB1); Value *BB2V = PN->getIncomingValueForBlock(BB2); - if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { + if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) { return false; } } @@ -1096,8 +1177,8 @@ static bool HoistThenElseCodeToIf(BranchInst *BI, // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As // such, we currently just scan for obviously identical instructions in an // identical order. - BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. - BasicBlock *BB2 = BI->getSuccessor(1); // The false destination + BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. + BasicBlock *BB2 = BI->getSuccessor(1); // The false destination BasicBlock::iterator BB1_Itr = BB1->begin(); BasicBlock::iterator BB2_Itr = BB2->begin(); @@ -1135,12 +1216,16 @@ static bool HoistThenElseCodeToIf(BranchInst *BI, if (!I2->use_empty()) I2->replaceAllUsesWith(I1); I1->intersectOptionalDataWith(I2); - unsigned KnownIDs[] = { - LLVMContext::MD_tbaa, LLVMContext::MD_range, - LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, - LLVMContext::MD_nonnull, LLVMContext::MD_invariant_group, - LLVMContext::MD_align, LLVMContext::MD_dereferenceable, - LLVMContext::MD_dereferenceable_or_null}; + unsigned KnownIDs[] = {LLVMContext::MD_tbaa, + LLVMContext::MD_range, + LLVMContext::MD_fpmath, + LLVMContext::MD_invariant_load, + LLVMContext::MD_nonnull, + LLVMContext::MD_invariant_group, + LLVMContext::MD_align, + LLVMContext::MD_dereferenceable, + LLVMContext::MD_dereferenceable_or_null, + LLVMContext::MD_mem_parallel_loop_access}; combineMetadata(I1, I2, KnownIDs); I2->eraseFromParent(); Changed = true; @@ -1165,9 +1250,9 @@ HoistTerminator: if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) return Changed; - for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { + for (BasicBlock *Succ : successors(BB1)) { PHINode *PN; - for (BasicBlock::iterator BBI = SI->begin(); + for (BasicBlock::iterator BBI = Succ->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI) { Value *BB1V = PN->getIncomingValueForBlock(BB1); Value *BB2V = PN->getIncomingValueForBlock(BB2); @@ -1178,7 +1263,7 @@ HoistTerminator: // eliminate undefined control flow then converting it to a select. if (passingValueIsAlwaysUndefined(BB1V, PN) || passingValueIsAlwaysUndefined(BB2V, PN)) - return Changed; + return Changed; if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) return Changed; @@ -1196,27 +1281,28 @@ HoistTerminator: NT->takeName(I1); } - IRBuilder<true, NoFolder> Builder(NT); + IRBuilder<NoFolder> Builder(NT); // Hoisting one of the terminators from our successor is a great thing. // Unfortunately, the successors of the if/else blocks may have PHI nodes in // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI // nodes, so we insert select instruction to compute the final result. - std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; - for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { + std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects; + for (BasicBlock *Succ : successors(BB1)) { PHINode *PN; - for (BasicBlock::iterator BBI = SI->begin(); + for (BasicBlock::iterator BBI = Succ->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI) { Value *BB1V = PN->getIncomingValueForBlock(BB1); Value *BB2V = PN->getIncomingValueForBlock(BB2); - if (BB1V == BB2V) continue; + if (BB1V == BB2V) + continue; // 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) - SI = cast<SelectInst> - (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, - BB1V->getName()+"."+BB2V->getName())); + SI = cast<SelectInst>( + Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, + BB1V->getName() + "." + BB2V->getName(), BI)); // Make the PHI node use the select for all incoming values for BB1/BB2 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) @@ -1226,8 +1312,8 @@ HoistTerminator: } // Update any PHI nodes in our new successors. - for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) - AddPredecessorToBlock(*SI, BIParent, BB1); + for (BasicBlock *Succ : successors(BB1)) + AddPredecessorToBlock(Succ, BIParent, BB1); EraseTerminatorInstAndDCECond(BI); return true; @@ -1280,10 +1366,12 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { RI2 = BB2->getInstList().rbegin(), RE2 = BB2->getInstList().rend(); // Skip debug info. - while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; + while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) + ++RI1; if (RI1 == RE1) return false; - while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; + while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) + ++RI2; if (RI2 == RE2) return false; // Skip the unconditional branches. @@ -1293,10 +1381,12 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { bool Changed = false; while (RI1 != RE1 && RI2 != RE2) { // Skip debug info. - while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; + while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) + ++RI1; if (RI1 == RE1) return Changed; - while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; + while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) + ++RI2; if (RI2 == RE2) return Changed; @@ -1305,22 +1395,19 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { // I1 and I2 should have a single use in the same PHI node, and they // perform the same operation. // Cannot move control-flow-involving, volatile loads, vaarg, etc. - if (isa<PHINode>(I1) || isa<PHINode>(I2) || - isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) || - I1->isEHPad() || I2->isEHPad() || + if (isa<PHINode>(I1) || isa<PHINode>(I2) || isa<TerminatorInst>(I1) || + isa<TerminatorInst>(I2) || I1->isEHPad() || I2->isEHPad() || isa<AllocaInst>(I1) || isa<AllocaInst>(I2) || I1->mayHaveSideEffects() || I2->mayHaveSideEffects() || I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() || - !I1->hasOneUse() || !I2->hasOneUse() || - !JointValueMap.count(InstPair)) + !I1->hasOneUse() || !I2->hasOneUse() || !JointValueMap.count(InstPair)) return Changed; // Check whether we should swap the operands of ICmpInst. // TODO: Add support of communativity. ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2); bool SwapOpnds = false; - if (ICmp1 && ICmp2 && - ICmp1->getOperand(0) != ICmp2->getOperand(0) && + if (ICmp1 && ICmp2 && ICmp1->getOperand(0) != ICmp2->getOperand(0) && ICmp1->getOperand(1) != ICmp2->getOperand(1) && (ICmp1->getOperand(0) == ICmp2->getOperand(1) || ICmp1->getOperand(1) == ICmp2->getOperand(0))) { @@ -1343,8 +1430,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { continue; // Early exit if we have more-than one pair of different operands or if // we need a PHI node to replace a constant. - if (Op1Idx != ~0U || - isa<Constant>(I1->getOperand(I)) || + if (Op1Idx != ~0U || isa<Constant>(I1->getOperand(I)) || isa<Constant>(I2->getOperand(I))) { // If we can't sink the instructions, undo the swapping. if (SwapOpnds) @@ -1379,7 +1465,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { // We need to update RE1 and RE2 if we are going to sink the first // instruction in the basic block down. - bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin()); + bool UpdateRE1 = (I1 == &BB1->front()), UpdateRE2 = (I2 == &BB2->front()); // Sink the instruction. BBEnd->getInstList().splice(FirstNonPhiInBBEnd->getIterator(), BB1->getInstList(), I1); @@ -1444,22 +1530,26 @@ static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, 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; + unsigned MaxNumInstToLookAt = 9; + for (Instruction &CurI : reverse(*BrBB)) { + if (!MaxNumInstToLookAt) + break; + // Skip debug info. + if (isa<DbgInfoIntrinsic>(CurI)) + continue; + --MaxNumInstToLookAt; // Could be calling an instruction that effects memory like free(). - if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI)) + if (CurI.mayHaveSideEffects() && !isa<StoreInst>(CurI)) return nullptr; - StoreInst *SI = dyn_cast<StoreInst>(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) + if (auto *SI = dyn_cast<StoreInst>(&CurI)) { + // Found the previous store make sure it stores to the same location. + if (SI->getPointerOperand() == StorePtr) + // Found the previous store, return its value operand. + return SI->getValueOperand(); return nullptr; // Unknown store. + } } return nullptr; @@ -1562,11 +1652,9 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // Do not hoist the instruction if any of its operands are defined but not // used in BB. The transformation will prevent the operand from // being sunk into the use block. - for (User::op_iterator i = I->op_begin(), e = I->op_end(); - i != e; ++i) { + for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { Instruction *OpI = dyn_cast<Instruction>(*i); - if (!OpI || OpI->getParent() != BB || - OpI->mayHaveSideEffects()) + if (!OpI || OpI->getParent() != BB || OpI->mayHaveSideEffects()) continue; // Not a candidate for sinking. ++SinkCandidateUseCounts[OpI]; @@ -1576,8 +1664,9 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // 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<Instruction *, unsigned, 4>::iterator I = - SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end(); + for (SmallDenseMap<Instruction *, unsigned, 4>::iterator + I = SinkCandidateUseCounts.begin(), + E = SinkCandidateUseCounts.end(); I != E; ++I) if (I->first->getNumUses() == I->second) { ++SpeculationCost; @@ -1613,8 +1702,8 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, return false; unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0; unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0; - unsigned MaxCost = 2 * PHINodeFoldingThreshold * - TargetTransformInfo::TCC_Basic; + unsigned MaxCost = + 2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic; if (OrigCost + ThenCost > MaxCost) return false; @@ -1637,19 +1726,19 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // Insert a select of the value of the speculated store. if (SpeculatedStoreValue) { - IRBuilder<true, NoFolder> Builder(BI); + IRBuilder<NoFolder> 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()); + Value *S = Builder.CreateSelect( + BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); SpeculatedStore->setOperand(0, S); } // Metadata can be dependent on the condition we are hoisting above. // Conservatively strip all metadata on the instruction. - for (auto &I: *ThenBB) + for (auto &I : *ThenBB) I.dropUnknownNonDebugMetadata(); // Hoist the instructions. @@ -1657,7 +1746,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, ThenBB->begin(), std::prev(ThenBB->end())); // Insert selects and rewrite the PHI operands. - IRBuilder<true, NoFolder> Builder(BI); + IRBuilder<NoFolder> Builder(BI); for (BasicBlock::iterator I = EndBB->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) { unsigned OrigI = PN->getBasicBlockIndex(BB); @@ -1675,8 +1764,8 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, Value *TrueV = ThenV, *FalseV = OrigV; if (Invert) std::swap(TrueV, FalseV); - Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV, - TrueV->getName() + "." + FalseV->getName()); + Value *V = Builder.CreateSelect( + BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); PN->setIncomingValue(OrigI, V); PN->setIncomingValue(ThenI, V); } @@ -1685,19 +1774,6 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, 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<CallInst>(I); - if (!CI) - continue; - if (CI->cannotDuplicate()) - return true; - } - return false; -} - /// Return true if we can thread a branch across this block. static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { BranchInst *BI = cast<BranchInst>(BB->getTerminator()); @@ -1706,14 +1782,16 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { if (isa<DbgInfoIntrinsic>(BBI)) continue; - if (Size > 10) return false; // Don't clone large BB's. + if (Size > 10) + return false; // Don't clone large BB's. ++Size; // We can only support instructions that do not define values that are // live outside of the current basic block. for (User *U : BBI->users()) { Instruction *UI = cast<Instruction>(U); - if (UI->getParent() != BB || isa<PHINode>(UI)) return false; + if (UI->getParent() != BB || isa<PHINode>(UI)) + return false; } // Looks ok, continue checking. @@ -1740,32 +1818,41 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) { } // Now we know that this block has multiple preds and two succs. - if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; + if (!BlockIsSimpleEnoughToThreadThrough(BB)) + return false; - if (HasNoDuplicateCall(BB)) return false; + // Can't fold blocks that contain noduplicate or convergent calls. + if (llvm::any_of(*BB, [](const Instruction &I) { + const CallInst *CI = dyn_cast<CallInst>(&I); + return CI && (CI->cannotDuplicate() || CI->isConvergent()); + })) + 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<ConstantInt>(PN->getIncomingValue(i)); - if (!CB || !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. BasicBlock *PredBB = PN->getIncomingBlock(i); BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); - if (RealDest == BB) continue; // Skip self loops. + if (RealDest == BB) + continue; // Skip self loops. // Skip if the predecessor's terminator is an indirect branch. - if (isa<IndirectBrInst>(PredBB->getTerminator())) continue; + if (isa<IndirectBrInst>(PredBB->getTerminator())) + continue; // The dest block might have PHI nodes, other predecessors and other // difficult cases. Instead of being smart about this, just insert a new // block that jumps to the destination block, effectively splitting // the edge we are about to create. - BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), - RealDest->getName()+".critedge", - RealDest->getParent(), RealDest); + BasicBlock *EdgeBB = + BasicBlock::Create(BB->getContext(), RealDest->getName() + ".critedge", + RealDest->getParent(), RealDest); BranchInst::Create(RealDest, EdgeBB); // Update PHI nodes. @@ -1775,7 +1862,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) { // instructions into EdgeBB. We know that there will be no uses of the // cloned instructions outside of EdgeBB. BasicBlock::iterator InsertPt = EdgeBB->begin(); - DenseMap<Value*, Value*> TranslateMap; // Track translated values. + DenseMap<Value *, Value *> TranslateMap; // Track translated values. for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { if (PHINode *PN = dyn_cast<PHINode>(BBI)) { TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); @@ -1783,26 +1870,31 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL) { } // Clone the instruction. Instruction *N = BBI->clone(); - if (BBI->hasName()) N->setName(BBI->getName()+".c"); + if (BBI->hasName()) + N->setName(BBI->getName() + ".c"); // Update operands due to translation. - for (User::op_iterator i = N->op_begin(), e = N->op_end(); - i != e; ++i) { - DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i); + for (User::op_iterator i = N->op_begin(), e = N->op_end(); i != e; ++i) { + DenseMap<Value *, Value *>::iterator PI = TranslateMap.find(*i); if (PI != TranslateMap.end()) *i = PI->second; } // Check for trivial simplification. if (Value *V = SimplifyInstruction(N, DL)) { - TranslateMap[&*BBI] = V; - delete N; // Instruction folded away, don't need actual inst + if (!BBI->use_empty()) + TranslateMap[&*BBI] = V; + if (!N->mayHaveSideEffects()) { + delete N; // Instruction folded away, don't need actual inst + N = nullptr; + } } else { - // Insert the new instruction into its new home. - EdgeBB->getInstList().insert(InsertPt, N); if (!BBI->use_empty()) TranslateMap[&*BBI] = N; } + // Insert the new instruction into its new home. + if (N) + EdgeBB->getInstList().insert(InsertPt, N); } // Loop over all of the edges from PredBB to BB, changing them to branch @@ -1852,7 +1944,7 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, // Loop over the PHI's seeing if we can promote them all to select // instructions. While we are at it, keep track of the instructions // that need to be moved to the dominating block. - SmallPtrSet<Instruction*, 4> AggressiveInsts; + SmallPtrSet<Instruction *, 4> AggressiveInsts; unsigned MaxCostVal0 = PHINodeFoldingThreshold, MaxCostVal1 = PHINodeFoldingThreshold; MaxCostVal0 *= TargetTransformInfo::TCC_Basic; @@ -1876,7 +1968,8 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, // 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<PHINode>(BB->begin()); - if (!PN) 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. @@ -1886,10 +1979,10 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, isa<BinaryOperator>(IfCond))) return false; - // If we all PHI nodes are promotable, check to make sure that all - // 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. + // If all PHI nodes are promotable, check to make sure that all 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 = nullptr; BasicBlock *IfBlock1 = PN->getIncomingBlock(0); BasicBlock *IfBlock2 = PN->getIncomingBlock(1); @@ -1897,11 +1990,12 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, IfBlock1 = nullptr; } else { DomBlock = *pred_begin(IfBlock1); - for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I) + for (BasicBlock::iterator I = IfBlock1->begin(); !isa<TerminatorInst>(I); + ++I) if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) { // This is not an aggressive instruction that we can promote. - // Because of this, we won't be able to get rid of the control - // flow, so the xform is not worth it. + // Because of this, we won't be able to get rid of the control flow, so + // the xform is not worth it. return false; } } @@ -1910,11 +2004,12 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, IfBlock2 = nullptr; } else { DomBlock = *pred_begin(IfBlock2); - for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I) + for (BasicBlock::iterator I = IfBlock2->begin(); !isa<TerminatorInst>(I); + ++I) if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) { // This is not an aggressive instruction that we can promote. - // Because of this, we won't be able to get rid of the control - // flow, so the xform is not worth it. + // Because of this, we won't be able to get rid of the control flow, so + // the xform is not worth it. return false; } } @@ -1925,7 +2020,7 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, // If we can still promote the PHI nodes after this gauntlet of tests, // do all of the PHI's now. Instruction *InsertPt = DomBlock->getTerminator(); - IRBuilder<true, NoFolder> Builder(InsertPt); + IRBuilder<NoFolder> Builder(InsertPt); // Move all 'aggressive' instructions, which are defined in the // conditional parts of the if's up to the dominating block. @@ -1940,13 +2035,12 @@ static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { // Change the PHI node into a select instruction. - Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); + Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); - SelectInst *NV = - cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, "")); - PN->replaceAllUsesWith(NV); - NV->takeName(PN); + Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt); + PN->replaceAllUsesWith(Sel); + Sel->takeName(PN); PN->eraseFromParent(); } @@ -2029,51 +2123,32 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI, } else if (isa<UndefValue>(TrueValue)) { TrueValue = FalseValue; } else { - TrueValue = Builder.CreateSelect(BrCond, TrueValue, - FalseValue, "retval"); + TrueValue = + Builder.CreateSelect(BrCond, TrueValue, FalseValue, "retval", BI); } } - Value *RI = !TrueValue ? - Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); + Value *RI = + !TrueValue ? Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); - (void) RI; + (void)RI; DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" << "\n " << *BI << "NewRet = " << *RI - << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); + << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: " << *FalseSucc); EraseTerminatorInstAndDCECond(BI); return true; } -/// Given a conditional BranchInstruction, retrieve the probabilities of the -/// branch taking each edge. Fills in the two APInt parameters and returns true, -/// or returns false if no or invalid metadata was found. -static bool ExtractBranchMetadata(BranchInst *BI, - uint64_t &ProbTrue, uint64_t &ProbFalse) { - assert(BI->isConditional() && - "Looking for probabilities on unconditional branch?"); - MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof); - if (!ProfileData || ProfileData->getNumOperands() != 3) return false; - ConstantInt *CITrue = - mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1)); - ConstantInt *CIFalse = - mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2)); - if (!CITrue || !CIFalse) return false; - ProbTrue = CITrue->getValue().getZExtValue(); - ProbFalse = CIFalse->getValue().getZExtValue(); - return true; -} - /// Return true if the given instruction is available /// in its predecessor block. If yes, the instruction will be removed. static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst)) return false; - for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) { - Instruction *PBI = &*I; + for (Instruction &I : *PB) { + Instruction *PBI = &I; // Check whether Inst and PBI generate the same value. if (Inst->isIdenticalTo(PBI)) { Inst->replaceAllUsesWith(PBI); @@ -2084,6 +2159,29 @@ static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { return false; } +/// Return true if either PBI or BI has branch weight available, and store +/// the weights in {Pred|Succ}{True|False}Weight. If one of PBI and BI does +/// not have branch weight, use 1:1 as its weight. +static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, + uint64_t &PredTrueWeight, + uint64_t &PredFalseWeight, + uint64_t &SuccTrueWeight, + uint64_t &SuccFalseWeight) { + bool PredHasWeights = + PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight); + bool SuccHasWeights = + BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight); + if (PredHasWeights || SuccHasWeights) { + if (!PredHasWeights) + PredTrueWeight = PredFalseWeight = 1; + if (!SuccHasWeights) + SuccTrueWeight = SuccFalseWeight = 1; + return true; + } else { + return false; + } +} + /// If this basic block is simple enough, and if a predecessor branches to us /// and one of our successors, fold the block into the predecessor and use /// logical operations to pick the right destination. @@ -2103,8 +2201,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { if (PBI->isConditional() && (BI->getSuccessor(0) == PBI->getSuccessor(0) || BI->getSuccessor(0) == PBI->getSuccessor(1))) { - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); - I != E; ) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { Instruction *Curr = &*I++; if (isa<CmpInst>(Curr)) { Cond = Curr; @@ -2122,13 +2219,14 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || Cond->getParent() != BB || !Cond->hasOneUse()) - return false; + return false; // Make sure the instruction after the condition is the cond branch. BasicBlock::iterator CondIt = ++Cond->getIterator(); // Ignore dbg intrinsics. - while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt; + while (isa<DbgInfoIntrinsic>(CondIt)) + ++CondIt; if (&*CondIt != BI) return false; @@ -2139,7 +2237,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // as "bonus instructions", and only allow this transformation when the // number of the bonus instructions does not exceed a certain threshold. unsigned NumBonusInsts = 0; - for (auto I = BB->begin(); Cond != I; ++I) { + for (auto I = BB->begin(); Cond != &*I; ++I) { // Ignore dbg intrinsics. if (isa<DbgInfoIntrinsic>(I)) continue; @@ -2168,7 +2266,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { return false; // Finally, don't infinitely unroll conditional loops. - BasicBlock *TrueDest = BI->getSuccessor(0); + BasicBlock *TrueDest = BI->getSuccessor(0); BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; if (TrueDest == BB || FalseDest == BB) return false; @@ -2180,10 +2278,9 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // Check that we have two conditional branches. If there is a PHI node in // the common successor, verify that the same value flows in from both // blocks. - SmallVector<PHINode*, 4> PHIs; + SmallVector<PHINode *, 4> PHIs; if (!PBI || PBI->isUnconditional() || - (BI->isConditional() && - !SafeToMergeTerminators(BI, PBI)) || + (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) || (!BI->isConditional() && !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs))) continue; @@ -2193,16 +2290,19 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { bool InvertPredCond = false; if (BI->isConditional()) { - if (PBI->getSuccessor(0) == TrueDest) + if (PBI->getSuccessor(0) == TrueDest) { Opc = Instruction::Or; - else if (PBI->getSuccessor(1) == FalseDest) + } else if (PBI->getSuccessor(1) == FalseDest) { Opc = Instruction::And; - else if (PBI->getSuccessor(0) == FalseDest) - Opc = Instruction::And, InvertPredCond = true; - else if (PBI->getSuccessor(1) == TrueDest) - Opc = Instruction::Or, InvertPredCond = true; - else + } else if (PBI->getSuccessor(0) == FalseDest) { + Opc = Instruction::And; + InvertPredCond = true; + } else if (PBI->getSuccessor(1) == TrueDest) { + Opc = Instruction::Or; + InvertPredCond = true; + } else { continue; + } } else { if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) continue; @@ -2219,8 +2319,8 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { CmpInst *CI = cast<CmpInst>(NewCond); CI->setPredicate(CI->getInversePredicate()); } else { - NewCond = Builder.CreateNot(NewCond, - PBI->getCondition()->getName()+".not"); + NewCond = + Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not"); } PBI->setCondition(NewCond); @@ -2234,12 +2334,12 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // We already make sure Cond is the last instruction before BI. Therefore, // all instructions before Cond other than DbgInfoIntrinsic are bonus // instructions. - for (auto BonusInst = BB->begin(); Cond != BonusInst; ++BonusInst) { + for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) { if (isa<DbgInfoIntrinsic>(BonusInst)) continue; Instruction *NewBonusInst = BonusInst->clone(); RemapInstruction(NewBonusInst, VMap, - RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); + RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); VMap[&*BonusInst] = NewBonusInst; // If we moved a load, we cannot any longer claim any knowledge about @@ -2258,49 +2358,49 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // two conditions together. Instruction *New = Cond->clone(); RemapInstruction(New, VMap, - RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); + RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); PredBlock->getInstList().insert(PBI->getIterator(), New); New->takeName(Cond); Cond->setName(New->getName() + ".old"); if (BI->isConditional()) { - Instruction *NewCond = - cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(), - New, "or.cond")); + Instruction *NewCond = cast<Instruction>( + Builder.CreateBinOp(Opc, PBI->getCondition(), New, "or.cond")); PBI->setCondition(NewCond); uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; - bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, - PredFalseWeight); - bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, - SuccFalseWeight); + bool HasWeights = + extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight, + SuccTrueWeight, SuccFalseWeight); SmallVector<uint64_t, 8> NewWeights; if (PBI->getSuccessor(0) == BB) { - if (PredHasWeights && SuccHasWeights) { + if (HasWeights) { // PBI: br i1 %x, BB, FalseDest // BI: br i1 %y, TrueDest, FalseDest - //TrueWeight is TrueWeight for PBI * TrueWeight for BI. + // TrueWeight is TrueWeight for PBI * TrueWeight for BI. NewWeights.push_back(PredTrueWeight * SuccTrueWeight); - //FalseWeight is FalseWeight for PBI * TotalWeight for BI + + // FalseWeight is FalseWeight for PBI * TotalWeight for BI + // TrueWeight for PBI * FalseWeight for BI. // We assume that total weights of a BranchInst can fit into 32 bits. // Therefore, we will not have overflow using 64-bit arithmetic. - NewWeights.push_back(PredFalseWeight * (SuccFalseWeight + - SuccTrueWeight) + PredTrueWeight * SuccFalseWeight); + NewWeights.push_back(PredFalseWeight * + (SuccFalseWeight + SuccTrueWeight) + + PredTrueWeight * SuccFalseWeight); } AddPredecessorToBlock(TrueDest, PredBlock, BB); PBI->setSuccessor(0, TrueDest); } if (PBI->getSuccessor(1) == BB) { - if (PredHasWeights && SuccHasWeights) { + if (HasWeights) { // PBI: br i1 %x, TrueDest, BB // BI: br i1 %y, TrueDest, FalseDest - //TrueWeight is TrueWeight for PBI * TotalWeight for BI + + // TrueWeight is TrueWeight for PBI * TotalWeight for BI + // FalseWeight for PBI * TrueWeight for BI. - NewWeights.push_back(PredTrueWeight * (SuccFalseWeight + - SuccTrueWeight) + PredFalseWeight * SuccTrueWeight); - //FalseWeight is FalseWeight for PBI * FalseWeight for BI. + NewWeights.push_back(PredTrueWeight * + (SuccFalseWeight + SuccTrueWeight) + + PredFalseWeight * SuccTrueWeight); + // FalseWeight is FalseWeight for PBI * FalseWeight for BI. NewWeights.push_back(PredFalseWeight * SuccFalseWeight); } AddPredecessorToBlock(FalseDest, PredBlock, BB); @@ -2310,51 +2410,42 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // Halve the weights if any of them cannot fit in an uint32_t FitWeights(NewWeights); - SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end()); - PBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(BI->getContext()). - createBranchWeights(MDWeights)); + SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(), + NewWeights.end()); + PBI->setMetadata( + LLVMContext::MD_prof, + MDBuilder(BI->getContext()).createBranchWeights(MDWeights)); } else 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<ConstantInt>( - PHIs[i]->getIncomingValueForBlock(PBI->getParent())); + PHIs[i]->getIncomingValueForBlock(PBI->getParent())); assert(PBI_C->getType()->isIntegerTy(1)); 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) // is false: !PBI_Cond and BI_Value - Instruction *NotCond = - cast<Instruction>(Builder.CreateNot(PBI->getCondition(), - "not.cond")); - MergedCond = - cast<Instruction>(Builder.CreateBinOp(Instruction::And, - NotCond, New, - "and.cond")); + Instruction *NotCond = cast<Instruction>( + Builder.CreateNot(PBI->getCondition(), "not.cond")); + MergedCond = cast<Instruction>( + Builder.CreateBinOp(Instruction::And, NotCond, New, "and.cond")); if (PBI_C->isOne()) - MergedCond = - cast<Instruction>(Builder.CreateBinOp(Instruction::Or, - PBI->getCondition(), MergedCond, - "or.cond")); + MergedCond = cast<Instruction>(Builder.CreateBinOp( + Instruction::Or, PBI->getCondition(), MergedCond, "or.cond")); } else { // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C) // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond) // is false: PBI_Cond and BI_Value - MergedCond = - cast<Instruction>(Builder.CreateBinOp(Instruction::And, - PBI->getCondition(), New, - "and.cond")); + MergedCond = cast<Instruction>(Builder.CreateBinOp( + Instruction::And, PBI->getCondition(), New, "and.cond")); if (PBI_C->isOne()) { - Instruction *NotCond = - cast<Instruction>(Builder.CreateNot(PBI->getCondition(), - "not.cond")); - MergedCond = - cast<Instruction>(Builder.CreateBinOp(Instruction::Or, - NotCond, MergedCond, - "or.cond")); + Instruction *NotCond = cast<Instruction>( + Builder.CreateNot(PBI->getCondition(), "not.cond")); + MergedCond = cast<Instruction>(Builder.CreateBinOp( + Instruction::Or, NotCond, MergedCond, "or.cond")); } } // Update PHI Node. @@ -2371,9 +2462,9 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { // could replace PBI's branch probabilities with BI's. // Copy any debug value intrinsics into the end of PredBlock. - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - if (isa<DbgInfoIntrinsic>(*I)) - I->clone()->insertBefore(PBI); + for (Instruction &I : *BB) + if (isa<DbgInfoIntrinsic>(I)) + I.clone()->insertBefore(PBI); return true; } @@ -2417,7 +2508,7 @@ static Value *ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, // where OtherBB is the single other predecessor of BB's only successor. PHINode *PHI = nullptr; BasicBlock *Succ = BB->getSingleSuccessor(); - + for (auto I = Succ->begin(); isa<PHINode>(I); ++I) if (cast<PHINode>(I)->getIncomingValueForBlock(BB) == V) { PHI = cast<PHINode>(I); @@ -2443,8 +2534,8 @@ static Value *ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, PHI->addIncoming(V, BB); for (BasicBlock *PredBB : predecessors(Succ)) if (PredBB != BB) - PHI->addIncoming(AlternativeV ? AlternativeV : UndefValue::get(V->getType()), - PredBB); + PHI->addIncoming( + AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB); return PHI; } @@ -2481,10 +2572,9 @@ static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, return N <= PHINodeFoldingThreshold; }; - if (!MergeCondStoresAggressively && (!IsWorthwhile(PTB) || - !IsWorthwhile(PFB) || - !IsWorthwhile(QTB) || - !IsWorthwhile(QFB))) + if (!MergeCondStoresAggressively && + (!IsWorthwhile(PTB) || !IsWorthwhile(PFB) || !IsWorthwhile(QTB) || + !IsWorthwhile(QFB))) return false; // For every pointer, there must be exactly two stores, one coming from @@ -2561,7 +2651,7 @@ static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, QStore->eraseFromParent(); PStore->eraseFromParent(); - + return true; } @@ -2593,7 +2683,7 @@ static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { // We model triangles as a type of diamond with a nullptr "true" block. // Triangles are canonicalized so that the fallthrough edge is represented by // a true condition, as in the diagram above. - // + // BasicBlock *PTB = PBI->getSuccessor(0); BasicBlock *PFB = PBI->getSuccessor(1); BasicBlock *QTB = QBI->getSuccessor(0); @@ -2622,8 +2712,7 @@ static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { // the post-dominating block, and the non-fallthroughs must only have one // predecessor. auto HasOnePredAndOneSucc = [](BasicBlock *BB, BasicBlock *P, BasicBlock *S) { - return BB->getSinglePredecessor() == P && - BB->getSingleSuccessor() == S; + return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S; }; if (!PostBB || !HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) || @@ -2637,7 +2726,7 @@ static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { // OK, this is a sequence of two diamonds or triangles. // Check if there are stores in PTB or PFB that are repeated in QTB or QFB. - SmallPtrSet<Value *,4> PStoreAddresses, QStoreAddresses; + SmallPtrSet<Value *, 4> PStoreAddresses, QStoreAddresses; for (auto *BB : {PTB, PFB}) { if (!BB) continue; @@ -2652,7 +2741,7 @@ static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { if (StoreInst *SI = dyn_cast<StoreInst>(&I)) QStoreAddresses.insert(SI->getPointerOperand()); } - + set_intersect(PStoreAddresses, QStoreAddresses); // set_intersect mutates PStoreAddresses in place. Rename it here to make it // clear what it contains. @@ -2684,9 +2773,9 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, if (BB->getSinglePredecessor()) { // Turn this into a branch on constant. bool CondIsTrue = PBI->getSuccessor(0) == BB; - BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), - CondIsTrue)); - return true; // Nuke the branch on constant. + BI->setCondition( + ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue)); + return true; // Nuke the branch on constant. } // Otherwise, if there are multiple predecessors, insert a PHI that merges @@ -2702,13 +2791,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // Any predecessor where the condition is not computable we keep symbolic. for (pred_iterator PI = PB; PI != PE; ++PI) { BasicBlock *P = *PI; - if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && - PBI != BI && PBI->isConditional() && - PBI->getCondition() == BI->getCondition() && + if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && PBI != BI && + PBI->isConditional() && PBI->getCondition() == BI->getCondition() && PBI->getSuccessor(0) != PBI->getSuccessor(1)) { bool CondIsTrue = PBI->getSuccessor(0) == BB; - NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), - CondIsTrue), P); + NewPN->addIncoming( + ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue), + P); } else { NewPN->addIncoming(BI->getCondition(), P); } @@ -2723,19 +2812,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, if (CE->canTrap()) return false; - // If BI is reached from the true path of PBI and PBI's condition implies - // BI's condition, we know the direction of the BI branch. - if (PBI->getSuccessor(0) == BI->getParent() && - isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL) && - PBI->getSuccessor(0) != PBI->getSuccessor(1) && - BB->getSinglePredecessor()) { - // Turn this into a branch on constant. - auto *OldCond = BI->getCondition(); - BI->setCondition(ConstantInt::getTrue(BB->getContext())); - RecursivelyDeleteTriviallyDeadInstructions(OldCond); - return true; // Nuke the branch on constant. - } - // If both branches are conditional and both contain stores to the same // address, remove the stores from the conditionals and create a conditional // merged store at the end. @@ -2753,16 +2829,21 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, return false; int PBIOp, BIOp; - if (PBI->getSuccessor(0) == BI->getSuccessor(0)) - PBIOp = BIOp = 0; - else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) - PBIOp = 0, BIOp = 1; - else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) - PBIOp = 1, BIOp = 0; - else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) - PBIOp = BIOp = 1; - else + if (PBI->getSuccessor(0) == BI->getSuccessor(0)) { + PBIOp = 0; + BIOp = 0; + } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) { + PBIOp = 0; + BIOp = 1; + } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) { + PBIOp = 1; + BIOp = 0; + } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) { + PBIOp = 1; + BIOp = 1; + } else { return false; + } // Check to make sure that the other destination of this branch // isn't BB itself. If so, this is an infinite loop that will @@ -2780,8 +2861,8 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); unsigned NumPhis = 0; - for (BasicBlock::iterator II = CommonDest->begin(); - isa<PHINode>(II); ++II, ++NumPhis) { + for (BasicBlock::iterator II = CommonDest->begin(); isa<PHINode>(II); + ++II, ++NumPhis) { if (NumPhis > 2) // Disable this xform. return false; @@ -2804,7 +2885,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() << "AND: " << *BI->getParent()); - // If OtherDest *is* BB, then BB is a basic block with a single conditional // branch in it, where one edge (OtherDest) goes back to itself but the other // exits. We don't *know* that the program avoids the infinite loop @@ -2815,8 +2895,8 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, if (OtherDest == BB) { // Insert it at the end of the function, because it's either code, // or it won't matter if it's hot. :) - BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), - "infloop", BB->getParent()); + BasicBlock *InfLoopBlock = + BasicBlock::Create(BB->getContext(), "infloop", BB->getParent()); BranchInst::Create(InfLoopBlock, InfLoopBlock); OtherDest = InfLoopBlock; } @@ -2828,13 +2908,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // Make sure we get to CommonDest on True&True directions. Value *PBICond = PBI->getCondition(); - IRBuilder<true, NoFolder> Builder(PBI); + IRBuilder<NoFolder> Builder(PBI); if (PBIOp) - PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not"); + PBICond = Builder.CreateNot(PBICond, PBICond->getName() + ".not"); Value *BICond = BI->getCondition(); if (BIOp) - BICond = Builder.CreateNot(BICond, BICond->getName()+".not"); + BICond = Builder.CreateNot(BICond, BICond->getName() + ".not"); // Merge the conditions. Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge"); @@ -2846,15 +2926,15 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // Update branch weight for PBI. uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; - bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, - PredFalseWeight); - bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, - SuccFalseWeight); - if (PredHasWeights && SuccHasWeights) { - uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; - uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight; - uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; - uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; + uint64_t PredCommon, PredOther, SuccCommon, SuccOther; + bool HasWeights = + extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight, + SuccTrueWeight, SuccFalseWeight); + if (HasWeights) { + PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; + PredOther = PBIOp ? PredTrueWeight : PredFalseWeight; + SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; + SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; // The weight to CommonDest should be PredCommon * SuccTotal + // PredOther * SuccCommon. // The weight to OtherDest should be PredOther * SuccOther. @@ -2885,9 +2965,29 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, Value *PBIV = PN->getIncomingValue(PBBIdx); if (BIV != PBIV) { // Insert a select in PBI to pick the right value. - Value *NV = cast<SelectInst> - (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux")); + SelectInst *NV = cast<SelectInst>( + Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux")); PN->setIncomingValue(PBBIdx, NV); + // Although the select has the same condition as PBI, the original branch + // weights for PBI do not apply to the new select because the select's + // 'logical' edges are incoming edges of the phi that is eliminated, not + // the outgoing edges of PBI. + if (HasWeights) { + uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; + uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight; + uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; + uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; + // The weight to PredCommonDest should be PredCommon * SuccTotal. + // The weight to PredOtherDest should be PredOther * SuccCommon. + uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther), + PredOther * SuccCommon}; + + FitWeights(NewWeights); + + NV->setMetadata(LLVMContext::MD_prof, + MDBuilder(BI->getContext()) + .createBranchWeights(NewWeights[0], NewWeights[1])); + } } } @@ -2907,7 +3007,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, BasicBlock *TrueBB, BasicBlock *FalseBB, uint32_t TrueWeight, - uint32_t FalseWeight){ + uint32_t FalseWeight) { // Remove any superfluous successor edges from the CFG. // First, figure out which successors to preserve. // If TrueBB and FalseBB are equal, only try to preserve one copy of that @@ -2942,8 +3042,8 @@ static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB); if (TrueWeight != FalseWeight) NewBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(OldTerm->getContext()). - createBranchWeights(TrueWeight, FalseWeight)); + MDBuilder(OldTerm->getContext()) + .createBranchWeights(TrueWeight, FalseWeight)); } } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { // Neither of the selected blocks were successors, so this @@ -2988,16 +3088,16 @@ static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { if (HasWeights) { GetBranchWeights(SI, Weights); if (Weights.size() == 1 + SI->getNumCases()) { - TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal). - getSuccessorIndex()]; - FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal). - getSuccessorIndex()]; + TrueWeight = + (uint32_t)Weights[SI->findCaseValue(TrueVal).getSuccessorIndex()]; + FalseWeight = + (uint32_t)Weights[SI->findCaseValue(FalseVal).getSuccessorIndex()]; } } // Perform the actual simplification. - return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, - TrueWeight, FalseWeight); + return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight, + FalseWeight); } // Replaces @@ -3017,8 +3117,8 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { BasicBlock *FalseBB = FBA->getBasicBlock(); // Perform the actual simplification. - return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, - 0, 0); + return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 0, + 0); } /// This is called when we find an icmp instruction @@ -3046,7 +3146,8 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( // If the block has any PHIs in it or the icmp has multiple uses, it is too // complex. - if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false; + if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) + return false; Value *V = ICI->getOperand(0); ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); @@ -3055,7 +3156,8 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( // '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 || !isa<SwitchInst>(Pred->getTerminator())) return false; + if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) + return false; SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); if (SI->getCondition() != V) @@ -3104,7 +3206,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( // If the icmp is a SETEQ, then the default dest gets false, the new edge gets // true in the PHI. Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); - Constant *NewCst = ConstantInt::getFalse(BB->getContext()); + Constant *NewCst = ConstantInt::getFalse(BB->getContext()); if (ICI->getPredicate() == ICmpInst::ICMP_EQ) std::swap(DefaultCst, NewCst); @@ -3116,21 +3218,21 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( // Okay, the switch goes to this block on a default value. Add an edge from // the switch to the merge point on the compared value. - BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", - BB->getParent(), BB); + BasicBlock *NewBB = + BasicBlock::Create(BB->getContext(), "switch.edge", BB->getParent(), BB); SmallVector<uint64_t, 8> Weights; bool HasWeights = HasBranchWeights(SI); if (HasWeights) { GetBranchWeights(SI, Weights); if (Weights.size() == 1 + SI->getNumCases()) { // Split weight for default case to case for "Cst". - Weights[0] = (Weights[0]+1) >> 1; + Weights[0] = (Weights[0] + 1) >> 1; Weights.push_back(Weights[0]); SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); - SI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getContext()). - createBranchWeights(MDWeights)); + SI->setMetadata( + LLVMContext::MD_prof, + MDBuilder(SI->getContext()).createBranchWeights(MDWeights)); } } SI->addCase(Cst, NewBB); @@ -3149,7 +3251,8 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, const DataLayout &DL) { Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); - if (!Cond) 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 @@ -3158,13 +3261,14 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, // Try to gather values from a chain of and/or to be turned into a switch ConstantComparesGatherer ConstantCompare(Cond, DL); // Unpack the result - SmallVectorImpl<ConstantInt*> &Values = ConstantCompare.Vals; + SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals; Value *CompVal = ConstantCompare.CompValue; unsigned UsedICmps = ConstantCompare.UsedICmps; Value *ExtraCase = ConstantCompare.Extra; // If we didn't have a multiply compared value, fail. - if (!CompVal) return false; + if (!CompVal) + return false; // Avoid turning single icmps into a switch. if (UsedICmps <= 1) @@ -3179,20 +3283,23 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, // If Extra was used, we require at least two switch values to do the // transformation. A switch with one value is just a conditional branch. - if (ExtraCase && Values.size() < 2) return false; + if (ExtraCase && Values.size() < 2) + return false; // TODO: Preserve branch weight metadata, similarly to how // FoldValueComparisonIntoPredecessors preserves it. // Figure out which block is which destination. BasicBlock *DefaultBB = BI->getSuccessor(1); - BasicBlock *EdgeBB = BI->getSuccessor(0); - if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); + BasicBlock *EdgeBB = BI->getSuccessor(0); + if (!TrueWhenEqual) + std::swap(DefaultBB, EdgeBB); BasicBlock *BB = BI->getParent(); DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() - << " cases into SWITCH. BB is:\n" << *BB); + << " cases into SWITCH. BB is:\n" + << *BB); // If there are any extra values that couldn't be folded into the switch // then we evaluate them with an explicit branch first. Split the block @@ -3216,7 +3323,7 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, AddPredecessorToBlock(EdgeBB, BB, NewBB); DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase - << "\nEXTRABB = " << *BB); + << "\nEXTRABB = " << *BB); BB = NewBB; } @@ -3237,11 +3344,10 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder, // We added edges from PI to the EdgeBB. As such, if there were any // PHI nodes in EdgeBB, they need entries to be added corresponding to // the number of edges added. - for (BasicBlock::iterator BBI = EdgeBB->begin(); - isa<PHINode>(BBI); ++BBI) { + for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) { PHINode *PN = cast<PHINode>(BBI); Value *InVal = PN->getIncomingValueForBlock(BB); - for (unsigned i = 0, e = Values.size()-1; i != e; ++i) + for (unsigned i = 0, e = Values.size() - 1; i != e; ++i) PN->addIncoming(InVal, BB); } @@ -3270,7 +3376,7 @@ bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { // Check that there are no other instructions except for debug intrinsics // between the phi of landing pads (RI->getValue()) and resume instruction. BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(), - E = RI->getIterator(); + E = RI->getIterator(); while (++I != E) if (!isa<DbgInfoIntrinsic>(I)) return false; @@ -3279,8 +3385,8 @@ bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { auto *PhiLPInst = cast<PHINode>(RI->getValue()); // Check incoming blocks to see if any of them are trivial. - for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); - Idx != End; Idx++) { + for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End; + Idx++) { auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx); auto *IncomingValue = PhiLPInst->getIncomingValue(Idx); @@ -3289,8 +3395,7 @@ bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { if (IncomingBB->getUniqueSuccessor() != BB) continue; - auto *LandingPad = - dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI()); + auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI()); // Not the landing pad that caused the control to branch here. if (IncomingValue != LandingPad) continue; @@ -3310,7 +3415,8 @@ bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { } // If no trivial unwind blocks, don't do any simplifications. - if (TrivialUnwindBlocks.empty()) return false; + if (TrivialUnwindBlocks.empty()) + return false; // Turn all invokes that unwind here into calls. for (auto *TrivialBB : TrivialUnwindBlocks) { @@ -3346,8 +3452,8 @@ bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) { bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) { BasicBlock *BB = RI->getParent(); LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); - assert (RI->getValue() == LPInst && - "Resume must unwind the exception that caused control to here"); + assert(RI->getValue() == LPInst && + "Resume must unwind the exception that caused control to here"); // Check that there are no other instructions except for debug intrinsics. BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator(); @@ -3363,10 +3469,12 @@ bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) { // The landingpad is now unreachable. Zap it. BB->eraseFromParent(); + if (LoopHeaders) + LoopHeaders->erase(BB); return true; } -bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { +static bool removeEmptyCleanup(CleanupReturnInst *RI) { // If this is a trivial cleanup pad that executes no instructions, it can be // eliminated. If the cleanup pad continues to the caller, any predecessor // that is an EH pad will be updated to continue to the caller and any @@ -3381,12 +3489,29 @@ bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { // This isn't an empty cleanup. return false; - // Check that there are no other instructions except for debug intrinsics. + // We cannot kill the pad if it has multiple uses. This typically arises + // from unreachable basic blocks. + if (!CPInst->hasOneUse()) + return false; + + // Check that there are no other instructions except for benign intrinsics. BasicBlock::iterator I = CPInst->getIterator(), E = RI->getIterator(); - while (++I != E) - if (!isa<DbgInfoIntrinsic>(I)) + while (++I != E) { + auto *II = dyn_cast<IntrinsicInst>(I); + if (!II) return false; + Intrinsic::ID IntrinsicID = II->getIntrinsicID(); + switch (IntrinsicID) { + case Intrinsic::dbg_declare: + case Intrinsic::dbg_value: + case Intrinsic::lifetime_end: + break; + default: + return false; + } + } + // If the cleanup return we are simplifying unwinds to the caller, this will // set UnwindDest to nullptr. BasicBlock *UnwindDest = RI->getUnwindDest(); @@ -3430,7 +3555,7 @@ bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { // removing, we need to merge that PHI node's incoming values into // DestPN. for (unsigned SrcIdx = 0, SrcE = SrcPN->getNumIncomingValues(); - SrcIdx != SrcE; ++SrcIdx) { + SrcIdx != SrcE; ++SrcIdx) { DestPN->addIncoming(SrcPN->getIncomingValue(SrcIdx), SrcPN->getIncomingBlock(SrcIdx)); } @@ -3484,13 +3609,63 @@ bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { return true; } +// Try to merge two cleanuppads together. +static bool mergeCleanupPad(CleanupReturnInst *RI) { + // Skip any cleanuprets which unwind to caller, there is nothing to merge + // with. + BasicBlock *UnwindDest = RI->getUnwindDest(); + if (!UnwindDest) + return false; + + // This cleanupret isn't the only predecessor of this cleanuppad, it wouldn't + // be safe to merge without code duplication. + if (UnwindDest->getSinglePredecessor() != RI->getParent()) + return false; + + // Verify that our cleanuppad's unwind destination is another cleanuppad. + auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->front()); + if (!SuccessorCleanupPad) + return false; + + CleanupPadInst *PredecessorCleanupPad = RI->getCleanupPad(); + // Replace any uses of the successor cleanupad with the predecessor pad + // The only cleanuppad uses should be this cleanupret, it's cleanupret and + // funclet bundle operands. + SuccessorCleanupPad->replaceAllUsesWith(PredecessorCleanupPad); + // Remove the old cleanuppad. + SuccessorCleanupPad->eraseFromParent(); + // Now, we simply replace the cleanupret with a branch to the unwind + // destination. + BranchInst::Create(UnwindDest, RI->getParent()); + RI->eraseFromParent(); + + return true; +} + +bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) { + // It is possible to transiantly have an undef cleanuppad operand because we + // have deleted some, but not all, dead blocks. + // Eventually, this block will be deleted. + if (isa<UndefValue>(RI->getOperand(0))) + return false; + + if (mergeCleanupPad(RI)) + return true; + + if (removeEmptyCleanup(RI)) + return true; + + return false; +} + bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { BasicBlock *BB = RI->getParent(); - if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; + if (!BB->getFirstNonPHIOrDbg()->isTerminator()) + return false; // Find predecessors that end with branches. - SmallVector<BasicBlock*, 8> UncondBranchPreds; - SmallVector<BranchInst*, 8> CondBranchPreds; + SmallVector<BasicBlock *, 8> UncondBranchPreds; + SmallVector<BranchInst *, 8> CondBranchPreds; for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { BasicBlock *P = *PI; TerminatorInst *PTI = P->getTerminator(); @@ -3507,14 +3682,17 @@ bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { while (!UncondBranchPreds.empty()) { BasicBlock *Pred = UncondBranchPreds.pop_back_val(); DEBUG(dbgs() << "FOLDING: " << *BB - << "INTO UNCOND BRANCH PRED: " << *Pred); + << "INTO UNCOND BRANCH PRED: " << *Pred); (void)FoldReturnIntoUncondBranch(RI, BB, Pred); } // If we eliminated all predecessors of the block, delete the block now. - if (pred_empty(BB)) + if (pred_empty(BB)) { // We know there are no successors, so just nuke the block. BB->eraseFromParent(); + if (LoopHeaders) + LoopHeaders->erase(BB); + } return true; } @@ -3547,7 +3725,8 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { // Do not delete instructions that can have side effects which might cause // the unreachable to not be reachable; specifically, calls and volatile // operations may have this effect. - if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; + if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) + break; if (BBI->mayHaveSideEffects()) { if (auto *SI = dyn_cast<StoreInst>(BBI)) { @@ -3589,9 +3768,10 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { // If the unreachable instruction is the first in the block, take a gander // at all of the predecessors of this instruction, and simplify them. - if (&BB->front() != UI) return Changed; + if (&BB->front() != UI) + return Changed; - SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); + SmallVector<BasicBlock *, 8> Preds(pred_begin(BB), pred_end(BB)); for (unsigned i = 0, e = Preds.size(); i != e; ++i) { TerminatorInst *TI = Preds[i]->getTerminator(); IRBuilder<> Builder(TI); @@ -3613,12 +3793,13 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { } } } else if (auto *SI = dyn_cast<SwitchInst>(TI)) { - for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); - i != e; ++i) + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; + ++i) if (i.getCaseSuccessor() == BB) { BB->removePredecessor(SI->getParent()); SI->removeCase(i); - --i; --e; + --i; + --e; Changed = true; } } else if (auto *II = dyn_cast<InvokeInst>(TI)) { @@ -3667,10 +3848,11 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { } // If this block is now dead, remove it. - if (pred_empty(BB) && - BB != &BB->getParent()->getEntryBlock()) { + if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) { // We know there are no successors, so just nuke the block. BB->eraseFromParent(); + if (LoopHeaders) + LoopHeaders->erase(BB); return true; } @@ -3699,25 +3881,28 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { // Partition the cases into two sets with different destinations. BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr; BasicBlock *DestB = nullptr; - SmallVector <ConstantInt *, 16> CasesA; - SmallVector <ConstantInt *, 16> CasesB; + SmallVector<ConstantInt *, 16> CasesA; + SmallVector<ConstantInt *, 16> CasesB; for (SwitchInst::CaseIt I : SI->cases()) { BasicBlock *Dest = I.getCaseSuccessor(); - if (!DestA) DestA = Dest; + if (!DestA) + DestA = Dest; if (Dest == DestA) { CasesA.push_back(I.getCaseValue()); continue; } - if (!DestB) DestB = Dest; + if (!DestB) + DestB = Dest; if (Dest == DestB) { CasesB.push_back(I.getCaseValue()); continue; } - return false; // More than two destinations. + return false; // More than two destinations. } - assert(DestA && DestB && "Single-destination switch should have been folded."); + assert(DestA && DestB && + "Single-destination switch should have been folded."); assert(DestA != DestB); assert(DestB != SI->getDefaultDest()); assert(!CasesB.empty() && "There must be non-default cases."); @@ -3741,7 +3926,8 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { // Start building the compare and branch. Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back()); - Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size()); + Constant *NumCases = + ConstantInt::get(Offset->getType(), ContiguousCases->size()); Value *Sub = SI->getCondition(); if (!Offset->isNullValue()) @@ -3773,21 +3959,24 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { FalseWeight /= 2; } NewBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getContext()).createBranchWeights( - (uint32_t)TrueWeight, (uint32_t)FalseWeight)); + MDBuilder(SI->getContext()) + .createBranchWeights((uint32_t)TrueWeight, + (uint32_t)FalseWeight)); } } // Prune obsolete incoming values off the successors' PHI nodes. for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) { unsigned PreviousEdges = ContiguousCases->size(); - if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges; + if (ContiguousDest == SI->getDefaultDest()) + ++PreviousEdges; for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); } for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) { unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size(); - if (OtherDest == SI->getDefaultDest()) ++PreviousEdges; + if (OtherDest == SI->getDefaultDest()) + ++PreviousEdges; for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I) cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); } @@ -3807,32 +3996,38 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, APInt KnownZero(Bits, 0), KnownOne(Bits, 0); computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AC, SI); + // We can also eliminate cases by determining that their values are outside of + // the limited range of the condition based on how many significant (non-sign) + // bits are in the condition value. + unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1; + unsigned MaxSignificantBitsInCond = Bits - ExtraSignBits; + // Gather dead cases. - SmallVector<ConstantInt*, 8> DeadCases; - for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { - if ((I.getCaseValue()->getValue() & KnownZero) != 0 || - (I.getCaseValue()->getValue() & KnownOne) != KnownOne) { - DeadCases.push_back(I.getCaseValue()); - DEBUG(dbgs() << "SimplifyCFG: switch case '" - << I.getCaseValue() << "' is dead.\n"); + SmallVector<ConstantInt *, 8> DeadCases; + for (auto &Case : SI->cases()) { + APInt CaseVal = Case.getCaseValue()->getValue(); + if ((CaseVal & KnownZero) != 0 || (CaseVal & KnownOne) != KnownOne || + (CaseVal.getMinSignedBits() > MaxSignificantBitsInCond)) { + DeadCases.push_back(Case.getCaseValue()); + DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal << " is dead.\n"); } } - // If we can prove that the cases must cover all possible values, the - // default destination becomes dead and we can remove it. If we know some + // If we can prove that the cases must cover all possible values, the + // default destination becomes dead and we can remove it. If we know some // of the bits in the value, we can use that to more precisely compute the // number of possible unique case values. bool HasDefault = - !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); - const unsigned NumUnknownBits = Bits - - (KnownZero.Or(KnownOne)).countPopulation(); + !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()); + const unsigned NumUnknownBits = + Bits - (KnownZero.Or(KnownOne)).countPopulation(); assert(NumUnknownBits <= Bits); if (HasDefault && DeadCases.empty() && - NumUnknownBits < 64 /* avoid overflow */ && + NumUnknownBits < 64 /* avoid overflow */ && SI->getNumCases() == (1ULL << NumUnknownBits)) { DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n"); - BasicBlock *NewDefault = SplitBlockPredecessors(SI->getDefaultDest(), - SI->getParent(), ""); + BasicBlock *NewDefault = + SplitBlockPredecessors(SI->getDefaultDest(), SI->getParent(), ""); SI->setDefaultDest(&*NewDefault); SplitBlock(&*NewDefault, &NewDefault->front()); auto *OldTI = NewDefault->getTerminator(); @@ -3849,12 +4044,12 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, } // Remove dead cases from the switch. - for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) { - SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]); + for (ConstantInt *DeadCase : DeadCases) { + SwitchInst::CaseIt Case = SI->findCaseValue(DeadCase); assert(Case != SI->case_default() && "Case was not found. Probably mistake in DeadCases forming."); if (HasWeight) { - std::swap(Weights[Case.getCaseIndex()+1], Weights.back()); + std::swap(Weights[Case.getCaseIndex() + 1], Weights.back()); Weights.pop_back(); } @@ -3865,8 +4060,8 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, if (HasWeight && Weights.size() >= 2) { SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); SI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getParent()->getContext()). - createBranchWeights(MDWeights)); + MDBuilder(SI->getParent()->getContext()) + .createBranchWeights(MDWeights)); } return !DeadCases.empty(); @@ -3878,8 +4073,7 @@ static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, /// block and see if the incoming value is equal to CaseValue. If so, return /// the phi node, and set PhiIndex to BB's index in the phi node. static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, - BasicBlock *BB, - int *PhiIndex) { + BasicBlock *BB, int *PhiIndex) { if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) return nullptr; // BB must be empty to be a candidate for simplification. if (!BB->getSinglePredecessor()) @@ -3897,7 +4091,8 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, assert(Idx >= 0 && "PHI has no entry for predecessor?"); Value *InValue = PHI->getIncomingValue(Idx); - if (InValue != CaseValue) continue; + if (InValue != CaseValue) + continue; *PhiIndex = Idx; return PHI; @@ -3911,17 +4106,19 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, /// blocks of the switch can be folded away. /// Returns true if a change is made. static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { - typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; + typedef DenseMap<PHINode *, SmallVector<int, 4>> ForwardingNodesMap; ForwardingNodesMap ForwardingNodes; - for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { + for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; + ++I) { ConstantInt *CaseValue = I.getCaseValue(); BasicBlock *CaseDest = I.getCaseSuccessor(); int PhiIndex; - PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, - &PhiIndex); - if (!PHI) continue; + PHINode *PHI = + FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIndex); + if (!PHI) + continue; ForwardingNodes[PHI].push_back(PhiIndex); } @@ -3929,11 +4126,13 @@ static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { bool Changed = false; for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), - E = ForwardingNodes.end(); I != E; ++I) { + E = ForwardingNodes.end(); + I != E; ++I) { PHINode *Phi = I->first; SmallVectorImpl<int> &Indexes = I->second; - if (Indexes.size() < 2) continue; + if (Indexes.size() < 2) + continue; for (size_t I = 0, E = Indexes.size(); I != E; ++I) Phi->setIncomingValue(Indexes[I], SI->getCondition()); @@ -3954,17 +4153,16 @@ static bool ValidLookupTableConstant(Constant *C) { if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) return CE->isGEPWithNoNotionalOverIndexing(); - return isa<ConstantFP>(C) || - isa<ConstantInt>(C) || - isa<ConstantPointerNull>(C) || - isa<GlobalValue>(C) || - isa<UndefValue>(C); + return isa<ConstantFP>(C) || isa<ConstantInt>(C) || + isa<ConstantPointerNull>(C) || isa<GlobalValue>(C) || + isa<UndefValue>(C); } /// If V is a Constant, return it. Otherwise, try to look up /// its constant value in ConstantPool, returning 0 if it's not there. -static Constant *LookupConstant(Value *V, - const SmallDenseMap<Value*, Constant*>& ConstantPool) { +static Constant * +LookupConstant(Value *V, + const SmallDenseMap<Value *, Constant *> &ConstantPool) { if (Constant *C = dyn_cast<Constant>(V)) return C; return ConstantPool.lookup(V); @@ -4001,7 +4199,7 @@ ConstantFold(Instruction *I, const DataLayout &DL, COps[1], DL); } - return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL); + return ConstantFoldInstOperands(I, COps, DL); } /// Try to determine the resulting constant values in phi nodes @@ -4018,7 +4216,7 @@ GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, // If CaseDest is empty except for some side-effect free instructions through // which we can constant-propagate the CaseVal, continue to its successor. - SmallDenseMap<Value*, Constant*> ConstantPool; + SmallDenseMap<Value *, Constant *> ConstantPool; ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal)); for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E; ++I) { @@ -4068,8 +4266,8 @@ GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, if (Idx == -1) continue; - Constant *ConstVal = LookupConstant(PHI->getIncomingValue(Idx), - ConstantPool); + Constant *ConstVal = + LookupConstant(PHI->getIncomingValue(Idx), ConstantPool); if (!ConstVal) return false; @@ -4086,16 +4284,16 @@ GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, // Helper function used to add CaseVal to the list of cases that generate // Result. static void MapCaseToResult(ConstantInt *CaseVal, - SwitchCaseResultVectorTy &UniqueResults, - Constant *Result) { + SwitchCaseResultVectorTy &UniqueResults, + Constant *Result) { for (auto &I : UniqueResults) { if (I.first == Result) { I.second.push_back(CaseVal); return; } } - UniqueResults.push_back(std::make_pair(Result, - SmallVector<ConstantInt*, 4>(1, CaseVal))); + UniqueResults.push_back( + std::make_pair(Result, SmallVector<ConstantInt *, 4>(1, CaseVal))); } // Helper function that initializes a map containing @@ -4137,7 +4335,7 @@ static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, DefaultResult = DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr; if ((!DefaultResult && - !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()))) + !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()))) return false; return true; @@ -4154,12 +4352,11 @@ static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI, // default: // return 4; // } -static Value * -ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, - Constant *DefaultResult, Value *Condition, - IRBuilder<> &Builder) { +static Value *ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, + Constant *DefaultResult, Value *Condition, + IRBuilder<> &Builder) { assert(ResultVector.size() == 2 && - "We should have exactly two unique results at this point"); + "We should have exactly two unique results at this point"); // If we are selecting between only two cases transform into a simple // select or a two-way select if default is possible. if (ResultVector[0].second.size() == 1 && @@ -4177,8 +4374,8 @@ ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector, } Value *const ValueCompare = Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp"); - return Builder.CreateSelect(ValueCompare, ResultVector[0].first, SelectValue, - "switch.select"); + return Builder.CreateSelect(ValueCompare, ResultVector[0].first, + SelectValue, "switch.select"); } return nullptr; @@ -4227,9 +4424,8 @@ static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, assert(PHI != nullptr && "PHI for value select not found"); Builder.SetInsertPoint(SI); - Value *SelectValue = ConvertTwoCaseSwitch( - UniqueResults, - DefaultResult, Cond, Builder); + Value *SelectValue = + ConvertTwoCaseSwitch(UniqueResults, DefaultResult, Cond, Builder); if (SelectValue) { RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder); return true; @@ -4239,62 +4435,62 @@ static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, } namespace { - /// This class represents a lookup table that can be used to replace a switch. - class SwitchLookupTable { - public: - /// Create a lookup table to use as a switch replacement with the contents - /// of Values, using DefaultValue to fill any holes in the table. - SwitchLookupTable( - Module &M, uint64_t TableSize, ConstantInt *Offset, - const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, - Constant *DefaultValue, const DataLayout &DL); - - /// Build instructions with Builder to retrieve the value at - /// the position given by Index in the lookup table. - Value *BuildLookup(Value *Index, IRBuilder<> &Builder); - - /// Return true if a table with TableSize elements of - /// type ElementType would fit in a target-legal register. - static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize, - Type *ElementType); - - private: - // Depending on the contents of the table, it can be represented in - // different ways. - enum { - // For tables where each element contains the same value, we just have to - // store that single value and return it for each lookup. - SingleValueKind, - - // For tables where there is a linear relationship between table index - // and values. We calculate the result with a simple multiplication - // and addition instead of a table lookup. - LinearMapKind, - - // For small tables with integer elements, we can pack them into a bitmap - // that fits into a target-legal register. Values are retrieved by - // shift and mask operations. - BitMapKind, - - // The table is stored as an array of values. Values are retrieved by load - // instructions from the table. - ArrayKind - } Kind; - - // For SingleValueKind, this is the single value. - Constant *SingleValue; - - // For BitMapKind, this is the bitmap. - ConstantInt *BitMap; - IntegerType *BitMapElementTy; - - // For LinearMapKind, these are the constants used to derive the value. - ConstantInt *LinearOffset; - ConstantInt *LinearMultiplier; - - // For ArrayKind, this is the array. - GlobalVariable *Array; - }; +/// This class represents a lookup table that can be used to replace a switch. +class SwitchLookupTable { +public: + /// Create a lookup table to use as a switch replacement with the contents + /// of Values, using DefaultValue to fill any holes in the table. + SwitchLookupTable( + Module &M, uint64_t TableSize, ConstantInt *Offset, + const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, + Constant *DefaultValue, const DataLayout &DL); + + /// Build instructions with Builder to retrieve the value at + /// the position given by Index in the lookup table. + Value *BuildLookup(Value *Index, IRBuilder<> &Builder); + + /// Return true if a table with TableSize elements of + /// type ElementType would fit in a target-legal register. + static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize, + Type *ElementType); + +private: + // Depending on the contents of the table, it can be represented in + // different ways. + enum { + // For tables where each element contains the same value, we just have to + // store that single value and return it for each lookup. + SingleValueKind, + + // For tables where there is a linear relationship between table index + // and values. We calculate the result with a simple multiplication + // and addition instead of a table lookup. + LinearMapKind, + + // For small tables with integer elements, we can pack them into a bitmap + // that fits into a target-legal register. Values are retrieved by + // shift and mask operations. + BitMapKind, + + // The table is stored as an array of values. Values are retrieved by load + // instructions from the table. + ArrayKind + } Kind; + + // For SingleValueKind, this is the single value. + Constant *SingleValue; + + // For BitMapKind, this is the bitmap. + ConstantInt *BitMap; + IntegerType *BitMapElementTy; + + // For LinearMapKind, these are the constants used to derive the value. + ConstantInt *LinearOffset; + ConstantInt *LinearMultiplier; + + // For ArrayKind, this is the array. + GlobalVariable *Array; +}; } SwitchLookupTable::SwitchLookupTable( @@ -4312,14 +4508,13 @@ SwitchLookupTable::SwitchLookupTable( Type *ValueType = Values.begin()->second->getType(); // Build up the table contents. - SmallVector<Constant*, 64> TableContents(TableSize); + SmallVector<Constant *, 64> 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() == ValueType); - uint64_t Idx = (CaseVal->getValue() - Offset->getValue()) - .getLimitedValue(); + uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); TableContents[Idx] = CaseRes; if (CaseRes != SingleValue) @@ -4407,65 +4602,62 @@ SwitchLookupTable::SwitchLookupTable( ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); - Array = new GlobalVariable(M, ArrayTy, /*constant=*/ true, - GlobalVariable::PrivateLinkage, - Initializer, + Array = new GlobalVariable(M, ArrayTy, /*constant=*/true, + GlobalVariable::PrivateLinkage, Initializer, "switch.table"); - Array->setUnnamedAddr(true); + Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); Kind = ArrayKind; } Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { switch (Kind) { - case SingleValueKind: - return SingleValue; - case LinearMapKind: { - // Derive the result value from the input value. - Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), - false, "switch.idx.cast"); - if (!LinearMultiplier->isOne()) - Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult"); - if (!LinearOffset->isZero()) - Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset"); - return Result; - } - case BitMapKind: { - // Type of the bitmap (e.g. i59). - IntegerType *MapTy = BitMap->getType(); - - // Cast Index to the same type as the bitmap. - // Note: The Index is <= the number of elements in the table, so - // truncating it to the width of the bitmask is safe. - Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast"); - - // Multiply the shift amount by the element width. - ShiftAmt = Builder.CreateMul(ShiftAmt, - ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), - "switch.shiftamt"); - - // Shift down. - Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt, - "switch.downshift"); - // Mask off. - return Builder.CreateTrunc(DownShifted, BitMapElementTy, - "switch.masked"); - } - case ArrayKind: { - // Make sure the table index will not overflow when treated as signed. - IntegerType *IT = cast<IntegerType>(Index->getType()); - uint64_t TableSize = Array->getInitializer()->getType() - ->getArrayNumElements(); - if (TableSize > (1ULL << (IT->getBitWidth() - 1))) - Index = Builder.CreateZExt(Index, - IntegerType::get(IT->getContext(), - IT->getBitWidth() + 1), - "switch.tableidx.zext"); - - Value *GEPIndices[] = { Builder.getInt32(0), Index }; - Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, - GEPIndices, "switch.gep"); - return Builder.CreateLoad(GEP, "switch.load"); - } + case SingleValueKind: + return SingleValue; + case LinearMapKind: { + // Derive the result value from the input value. + Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), + false, "switch.idx.cast"); + if (!LinearMultiplier->isOne()) + Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult"); + if (!LinearOffset->isZero()) + Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset"); + return Result; + } + case BitMapKind: { + // Type of the bitmap (e.g. i59). + IntegerType *MapTy = BitMap->getType(); + + // Cast Index to the same type as the bitmap. + // Note: The Index is <= the number of elements in the table, so + // truncating it to the width of the bitmask is safe. + Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast"); + + // Multiply the shift amount by the element width. + ShiftAmt = Builder.CreateMul( + ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), + "switch.shiftamt"); + + // Shift down. + Value *DownShifted = + Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift"); + // Mask off. + return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked"); + } + case ArrayKind: { + // Make sure the table index will not overflow when treated as signed. + IntegerType *IT = cast<IntegerType>(Index->getType()); + uint64_t TableSize = + Array->getInitializer()->getType()->getArrayNumElements(); + if (TableSize > (1ULL << (IT->getBitWidth() - 1))) + Index = Builder.CreateZExt( + Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1), + "switch.tableidx.zext"); + + Value *GEPIndices[] = {Builder.getInt32(0), Index}; + Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, + GEPIndices, "switch.gep"); + return Builder.CreateLoad(GEP, "switch.load"); + } } llvm_unreachable("Unknown lookup table kind!"); } @@ -4480,7 +4672,7 @@ bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL, // are <= 15, we could try to narrow the type. // Avoid overflow, fitsInLegalInteger uses unsigned int for the width. - if (TableSize >= UINT_MAX/IT->getBitWidth()) + if (TableSize >= UINT_MAX / IT->getBitWidth()) return false; return DL.fitsInLegalInteger(TableSize * IT->getBitWidth()); } @@ -4503,8 +4695,9 @@ ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); // Saturate this flag to false. - AllTablesFitInRegister = AllTablesFitInRegister && - SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty); + 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 @@ -4547,9 +4740,10 @@ ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, /// ... /// \endcode /// Jump threading will then eliminate the second if(cond). -static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, - BranchInst *RangeCheckBranch, Constant *DefaultValue, - const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values) { +static void reuseTableCompare( + User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, + Constant *DefaultValue, + const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) { ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser); if (!CmpInst) @@ -4578,13 +4772,13 @@ static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, // compare result. for (auto ValuePair : Values) { Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(), - ValuePair.second, CmpOp1, true); + ValuePair.second, CmpOp1, true); if (!CaseConst || CaseConst == DefaultConst) return; assert((CaseConst == TrueConst || CaseConst == FalseConst) && "Expect true or false as compare result."); } - + // Check if the branch instruction dominates the phi node. It's a simple // dominance check, but sufficient for our needs. // Although this check is invariant in the calling loops, it's better to do it @@ -4602,9 +4796,9 @@ static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, ++NumTableCmpReuses; } else { // The compare yields the same result, just inverted. We can replace it. - Value *InvertedTableCmp = BinaryOperator::CreateXor(RangeCmp, - ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp", - RangeCheckBranch); + Value *InvertedTableCmp = BinaryOperator::CreateXor( + RangeCmp, ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp", + RangeCheckBranch); CmpInst->replaceAllUsesWith(InvertedTableCmp); ++NumTableCmpReuses; } @@ -4629,7 +4823,8 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // GEP needs a runtime relocation in PIC code. We should just build one big // string and lookup indices into that. - // Ignore switches with less than three cases. Lookup tables will not make them + // 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; @@ -4642,11 +4837,11 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, ConstantInt *MaxCaseVal = CI.getCaseValue(); BasicBlock *CommonDest = nullptr; - typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy; - SmallDenseMap<PHINode*, ResultListTy> ResultLists; - SmallDenseMap<PHINode*, Constant*> DefaultResults; - SmallDenseMap<PHINode*, Type*> ResultTypes; - SmallVector<PHINode*, 4> PHIs; + typedef SmallVector<std::pair<ConstantInt *, Constant *>, 4> ResultListTy; + SmallDenseMap<PHINode *, ResultListTy> ResultLists; + SmallDenseMap<PHINode *, Constant *> DefaultResults; + SmallDenseMap<PHINode *, Type *> ResultTypes; + SmallVector<PHINode *, 4> PHIs; for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { ConstantInt *CaseVal = CI.getCaseValue(); @@ -4656,7 +4851,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, MaxCaseVal = CaseVal; // Resulting value at phi nodes for this case value. - typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy; + typedef SmallVector<std::pair<PHINode *, Constant *>, 4> ResultsTy; ResultsTy Results; if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest, Results, DL)) @@ -4684,14 +4879,14 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // If the table has holes, we need a constant result for the default case // or a bitmask that fits in a register. - SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList; + SmallVector<std::pair<PHINode *, Constant *>, 4> DefaultResultsList; bool 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). + if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). return false; if (!DL.fitsInLegalInteger(TableSize)) return false; @@ -4708,15 +4903,13 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // Create the BB that does the lookups. Module &Mod = *CommonDest->getParent()->getParent(); - BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(), - "switch.lookup", - CommonDest->getParent(), - CommonDest); + BasicBlock *LookupBB = BasicBlock::Create( + Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest); // Compute the table index value. Builder.SetInsertPoint(SI); - Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, - "switch.tableidx"); + Value *TableIndex = + Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx"); // Compute the maximum table size representable by the integer type we are // switching upon. @@ -4739,9 +4932,10 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // Note: We call removeProdecessor later since we need to be able to get the // PHI value for the default case in case we're using a bit mask. } else { - Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( - MinCaseVal->getType(), TableSize)); - RangeCheckBranch = Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); + Value *Cmp = Builder.CreateICmpULT( + TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize)); + RangeCheckBranch = + Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); } // Populate the BB that does the lookups. @@ -4753,10 +4947,8 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // and we create a new LookupBB. BasicBlock *MaskBB = LookupBB; MaskBB->setName("switch.hole_check"); - LookupBB = BasicBlock::Create(Mod.getContext(), - "switch.lookup", - CommonDest->getParent(), - CommonDest); + LookupBB = BasicBlock::Create(Mod.getContext(), "switch.lookup", + CommonDest->getParent(), CommonDest); // Make the mask's bitwidth at least 8bit and a power-of-2 to avoid // unnecessary illegal types. @@ -4766,8 +4958,8 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // Build bitmask; fill in a 1 bit for every case. 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(); + uint64_t Idx = (ResultList[I].first->getValue() - MinCaseVal->getValue()) + .getLimitedValue(); MaskInt |= One << Idx; } ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt); @@ -4776,13 +4968,11 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // 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"); + 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); @@ -4905,7 +5095,8 @@ bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) { Dest->removePredecessor(BB); IBI->removeDestination(i); - --i; --e; + --i; + --e; Changed = true; } } @@ -4968,27 +5159,28 @@ static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, LandingPadInst *LPad2 = dyn_cast<LandingPadInst>(I); if (!LPad2 || !LPad2->isIdenticalTo(LPad)) continue; - for (++I; isa<DbgInfoIntrinsic>(I); ++I) {} + for (++I; isa<DbgInfoIntrinsic>(I); ++I) { + } BranchInst *BI2 = dyn_cast<BranchInst>(I); if (!BI2 || !BI2->isIdenticalTo(BI)) continue; - // We've found an identical block. Update our predeccessors to take that + // We've found an identical block. Update our predecessors to take that // path instead and make ourselves dead. SmallSet<BasicBlock *, 16> Preds; Preds.insert(pred_begin(BB), pred_end(BB)); for (BasicBlock *Pred : Preds) { InvokeInst *II = cast<InvokeInst>(Pred->getTerminator()); - assert(II->getNormalDest() != BB && - II->getUnwindDest() == BB && "unexpected successor"); + assert(II->getNormalDest() != BB && II->getUnwindDest() == BB && + "unexpected successor"); II->setUnwindDest(OtherPred); } // The debug info in OtherPred doesn't cover the merged control flow that // used to go through BB. We need to delete it or update it. - for (auto I = OtherPred->begin(), E = OtherPred->end(); - I != E;) { - Instruction &Inst = *I; I++; + for (auto I = OtherPred->begin(), E = OtherPred->end(); I != E;) { + Instruction &Inst = *I; + I++; if (isa<DbgInfoIntrinsic>(Inst)) Inst.eraseFromParent(); } @@ -5007,15 +5199,22 @@ static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, return false; } -bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ +bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, + IRBuilder<> &Builder) { BasicBlock *BB = BI->getParent(); if (SinkCommon && SinkThenElseCodeToEnd(BI)) return true; // If the Terminator is the only non-phi instruction, simplify the block. + // if LoopHeader is provided, check if the block is a loop header + // (This is for early invocations before loop simplify and vectorization + // to keep canonical loop forms for nested loops. + // These blocks can be eliminated when the pass is invoked later + // in the back-end.) BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && + (!LoopHeaders || !LoopHeaders->count(BB)) && TryToSimplifyUncondBranchFromEmptyBlock(BB)) return true; @@ -5034,9 +5233,9 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ // See if we can merge an empty landing pad block with another which is // equivalent. if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) { - for (++I; isa<DbgInfoIntrinsic>(I); ++I) {} - if (I->isTerminator() && - TryToMergeLandingPad(LPad, BI, BB)) + for (++I; isa<DbgInfoIntrinsic>(I); ++I) { + } + if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB)) return true; } @@ -5081,7 +5280,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (&*I == BI) { if (FoldValueComparisonIntoPredecessors(BI, Builder)) return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; - } else if (&*I == cast<Instruction>(BI->getCondition())){ + } else if (&*I == cast<Instruction>(BI->getCondition())) { ++I; // Ignore dbg intrinsics. while (isa<DbgInfoIntrinsic>(I)) @@ -5095,6 +5294,30 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (SimplifyBranchOnICmpChain(BI, Builder, DL)) return true; + // If this basic block has a single dominating predecessor block and the + // dominating block's condition implies BI's condition, we know the direction + // of the BI branch. + if (BasicBlock *Dom = BB->getSinglePredecessor()) { + auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator()); + if (PBI && PBI->isConditional() && + PBI->getSuccessor(0) != PBI->getSuccessor(1) && + (PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB)) { + bool CondIsFalse = PBI->getSuccessor(1) == BB; + Optional<bool> Implication = isImpliedCondition( + PBI->getCondition(), BI->getCondition(), DL, CondIsFalse); + if (Implication) { + // Turn this into a branch on constant. + auto *OldCond = BI->getCondition(); + ConstantInt *CI = *Implication + ? ConstantInt::getTrue(BB->getContext()) + : ConstantInt::getFalse(BB->getContext()); + BI->setCondition(CI); + RecursivelyDeleteTriviallyDeadInstructions(OldCond); + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | 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. @@ -5149,7 +5372,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (PBI != BI && PBI->isConditional()) if (mergeConditionalStores(PBI, BI)) return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; - + return false; } @@ -5162,7 +5385,7 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { if (I->use_empty()) return false; - if (C->isNullValue()) { + if (C->isNullValue() || isa<UndefValue>(C)) { // Only look at the first use, avoid hurting compile time with long uselists User *Use = *I->user_begin(); @@ -5189,7 +5412,12 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { // Store to null is undefined. if (StoreInst *SI = dyn_cast<StoreInst>(Use)) if (!SI->isVolatile()) - return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; + return SI->getPointerAddressSpace() == 0 && + SI->getPointerOperand() == I; + + // A call to null is undefined. + if (auto CS = CallSite(Use)) + return CS.getCalledValue() == I; } return false; } @@ -5210,8 +5438,8 @@ static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { if (BI->isUnconditional()) Builder.CreateUnreachable(); else - Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : - BI->getSuccessor(0)); + Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) + : BI->getSuccessor(0)); BI->eraseFromParent(); return true; } @@ -5229,8 +5457,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { // Remove basic blocks that have no predecessors (except the entry block)... // or that just have themself as a predecessor. These are unreachable. - if ((pred_empty(BB) && - BB != &BB->getParent()->getEntryBlock()) || + if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) || BB->getSinglePredecessor() == BB) { DEBUG(dbgs() << "Removing BB: \n" << *BB); DeleteDeadBlock(BB); @@ -5265,25 +5492,33 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { Builder.SetInsertPoint(BB->getTerminator()); if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { if (BI->isUnconditional()) { - if (SimplifyUncondBranch(BI, Builder)) return true; + if (SimplifyUncondBranch(BI, Builder)) + return true; } else { - if (SimplifyCondBranch(BI, Builder)) return true; + if (SimplifyCondBranch(BI, Builder)) + return true; } } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { - if (SimplifyReturn(RI, Builder)) return true; + if (SimplifyReturn(RI, Builder)) + return true; } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { - if (SimplifyResume(RI, Builder)) return true; + if (SimplifyResume(RI, Builder)) + return true; } else if (CleanupReturnInst *RI = - dyn_cast<CleanupReturnInst>(BB->getTerminator())) { - if (SimplifyCleanupReturn(RI)) return true; + dyn_cast<CleanupReturnInst>(BB->getTerminator())) { + if (SimplifyCleanupReturn(RI)) + return true; } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { - if (SimplifySwitch(SI, Builder)) return true; + if (SimplifySwitch(SI, Builder)) + return true; } else if (UnreachableInst *UI = - dyn_cast<UnreachableInst>(BB->getTerminator())) { - if (SimplifyUnreachable(UI)) return true; + dyn_cast<UnreachableInst>(BB->getTerminator())) { + if (SimplifyUnreachable(UI)) + return true; } else if (IndirectBrInst *IBI = - dyn_cast<IndirectBrInst>(BB->getTerminator())) { - if (SimplifyIndirectBr(IBI)) return true; + dyn_cast<IndirectBrInst>(BB->getTerminator())) { + if (SimplifyIndirectBr(IBI)) + return true; } return Changed; @@ -5295,7 +5530,9 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { /// of the CFG. It returns true if a modification was made. /// bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC) { + unsigned BonusInstThreshold, AssumptionCache *AC, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders) { return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), - BonusInstThreshold, AC).run(BB); + BonusInstThreshold, AC, LoopHeaders) + .run(BB); } |