diff options
Diffstat (limited to 'gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp')
| -rw-r--r-- | gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 618 |
1 files changed, 332 insertions, 286 deletions
diff --git a/gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 8784b970214..7c195788e41 100644 --- a/gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/gnu/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -22,12 +22,14 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/CallSite.h" @@ -35,8 +37,8 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" -#include "llvm/IR/DebugInfo.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" #include "llvm/IR/GlobalValue.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" @@ -53,6 +55,7 @@ #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" @@ -73,6 +76,7 @@ #include <iterator> #include <map> #include <set> +#include <tuple> #include <utility> #include <vector> @@ -141,12 +145,13 @@ 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> - SwitchCaseResultVectorTy; +using SwitchCaseResultVectorTy = + SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>; + // 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; +using SwitchCaseResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>; /// ValueEqualityComparisonCase - Represents a case of a switch. struct ValueEqualityComparisonCase { @@ -167,11 +172,9 @@ struct ValueEqualityComparisonCase { class SimplifyCFGOpt { const TargetTransformInfo &TTI; const DataLayout &DL; - unsigned BonusInstThreshold; - AssumptionCache *AC; SmallPtrSetImpl<BasicBlock *> *LoopHeaders; - // See comments in SimplifyCFGOpt::SimplifySwitch. - bool LateSimplifyCFG; + const SimplifyCFGOptions &Options; + Value *isValueEqualityComparison(TerminatorInst *TI); BasicBlock *GetValueEqualityComparisonCases( TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases); @@ -194,11 +197,9 @@ class SimplifyCFGOpt { public: SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, - unsigned BonusInstThreshold, AssumptionCache *AC, SmallPtrSetImpl<BasicBlock *> *LoopHeaders, - bool LateSimplifyCFG) - : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC), - LoopHeaders(LoopHeaders), LateSimplifyCFG(LateSimplifyCFG) {} + const SimplifyCFGOptions &Opts) + : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {} bool run(BasicBlock *BB); }; @@ -282,12 +283,8 @@ isProfitableToFoldUnconditional(BranchInst *SI1, BranchInst *SI2, /// of Succ. static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred) { - 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) - PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); + for (PHINode &PN : Succ->phis()) + PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred); } /// Compute an abstract "cost" of speculating the given instruction, @@ -438,18 +435,24 @@ namespace { /// fail. struct ConstantComparesGatherer { const DataLayout &DL; - Value *CompValue; /// Value found for the switch comparison - Value *Extra; /// Extra clause to be checked before the switch - SmallVector<ConstantInt *, 8> Vals; /// Set of integers to match in switch - unsigned UsedICmps; /// Number of comparisons matched in the and/or chain + + /// Value found for the switch comparison + Value *CompValue = nullptr; + + /// Extra clause to be checked before the switch + Value *Extra = nullptr; + + /// Set of integers to match in switch + SmallVector<ConstantInt *, 8> Vals; + + /// Number of comparisons matched in the and/or chain + unsigned UsedICmps = 0; /// Construct and compute the result for the comparison instruction Cond - ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) - : DL(DL), CompValue(nullptr), Extra(nullptr), UsedICmps(0) { + ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) : DL(DL) { gather(Cond); } - /// Prevent copy ConstantComparesGatherer(const ConstantComparesGatherer &) = delete; ConstantComparesGatherer & operator=(const ConstantComparesGatherer &) = delete; @@ -487,7 +490,6 @@ private: // (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)) { - // 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: @@ -770,6 +772,31 @@ static bool ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, return false; } +// Set branch weights on SwitchInst. This sets the metadata if there is at +// least one non-zero weight. +static void setBranchWeights(SwitchInst *SI, ArrayRef<uint32_t> Weights) { + // Check that there is at least one non-zero weight. Otherwise, pass + // nullptr to setMetadata which will erase the existing metadata. + MDNode *N = nullptr; + if (llvm::any_of(Weights, [](uint32_t W) { return W != 0; })) + N = MDBuilder(SI->getParent()->getContext()).createBranchWeights(Weights); + SI->setMetadata(LLVMContext::MD_prof, N); +} + +// Similar to the above, but for branch and select instructions that take +// exactly 2 weights. +static void setBranchWeights(Instruction *I, uint32_t TrueWeight, + uint32_t FalseWeight) { + assert(isa<BranchInst>(I) || isa<SelectInst>(I)); + // Check that there is at least one non-zero weight. Otherwise, pass + // nullptr to setMetadata which will erase the existing metadata. + MDNode *N = nullptr; + if (TrueWeight || FalseWeight) + N = MDBuilder(I->getParent()->getContext()) + .createBranchWeights(TrueWeight, FalseWeight); + I->setMetadata(LLVMContext::MD_prof, N); +} + /// If TI is known to be a terminator instruction and its block is known to /// only have a single predecessor block, check to see if that predecessor is /// also a value comparison with the same value, and if that comparison @@ -859,9 +886,7 @@ bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor( } } if (HasWeight && Weights.size() >= 2) - SI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getParent()->getContext()) - .createBranchWeights(Weights)); + setBranchWeights(SI, Weights); DEBUG(dbgs() << "Leaving: " << *TI << "\n"); return true; @@ -1166,9 +1191,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); - NewSI->setMetadata( - LLVMContext::MD_prof, - MDBuilder(BB->getContext()).createBranchWeights(MDWeights)); + setBranchWeights(NewSI, MDWeights); } EraseTerminatorInstAndDCECond(PTI); @@ -1201,11 +1224,9 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2) { for (BasicBlock *Succ : successors(BB1)) { - PHINode *PN; - for (BasicBlock::iterator BBI = Succ->begin(); - (PN = dyn_cast<PHINode>(BBI)); ++BBI) { - Value *BB1V = PN->getIncomingValueForBlock(BB1); - Value *BB2V = PN->getIncomingValueForBlock(BB2); + for (const PHINode &PN : Succ->phis()) { + Value *BB1V = PN.getIncomingValueForBlock(BB1); + Value *BB2V = PN.getIncomingValueForBlock(BB2); if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) { return false; } @@ -1255,6 +1276,17 @@ static bool HoistThenElseCodeToIf(BranchInst *BI, if (isa<TerminatorInst>(I1)) goto HoistTerminator; + // If we're going to hoist a call, make sure that the two instructions we're + // commoning/hoisting are both marked with musttail, or neither of them is + // marked as such. Otherwise, we might end up in a situation where we hoist + // from a block where the terminator is a `ret` to a block where the terminator + // is a `br`, and `musttail` calls expect to be followed by a return. + auto *C1 = dyn_cast<CallInst>(I1); + auto *C2 = dyn_cast<CallInst>(I2); + if (C1 && C2) + if (C1->isMustTailCall() != C2->isMustTailCall()) + return Changed; + if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2)) return Changed; @@ -1279,9 +1311,7 @@ static bool HoistThenElseCodeToIf(BranchInst *BI, // I1 and I2 are being combined into a single instruction. Its debug // location is the merged locations of the original instructions. - if (!isa<CallInst>(I1)) - I1->setDebugLoc( - DILocation::getMergedLocation(I1->getDebugLoc(), I2->getDebugLoc())); + I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc()); I2->eraseFromParent(); Changed = true; @@ -1307,18 +1337,16 @@ HoistTerminator: return Changed; for (BasicBlock *Succ : successors(BB1)) { - PHINode *PN; - for (BasicBlock::iterator BBI = Succ->begin(); - (PN = dyn_cast<PHINode>(BBI)); ++BBI) { - Value *BB1V = PN->getIncomingValueForBlock(BB1); - Value *BB2V = PN->getIncomingValueForBlock(BB2); + for (PHINode &PN : Succ->phis()) { + Value *BB1V = PN.getIncomingValueForBlock(BB1); + Value *BB2V = PN.getIncomingValueForBlock(BB2); if (BB1V == BB2V) continue; // Check for passingValueIsAlwaysUndefined here because we would rather // eliminate undefined control flow then converting it to a select. - if (passingValueIsAlwaysUndefined(BB1V, PN) || - passingValueIsAlwaysUndefined(BB2V, PN)) + if (passingValueIsAlwaysUndefined(BB1V, &PN) || + passingValueIsAlwaysUndefined(BB2V, &PN)) return Changed; if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) @@ -1344,11 +1372,9 @@ HoistTerminator: // nodes, so we insert select instruction to compute the final result. std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects; for (BasicBlock *Succ : successors(BB1)) { - PHINode *PN; - for (BasicBlock::iterator BBI = Succ->begin(); - (PN = dyn_cast<PHINode>(BBI)); ++BBI) { - Value *BB1V = PN->getIncomingValueForBlock(BB1); - Value *BB2V = PN->getIncomingValueForBlock(BB2); + for (PHINode &PN : Succ->phis()) { + Value *BB1V = PN.getIncomingValueForBlock(BB1); + Value *BB2V = PN.getIncomingValueForBlock(BB2); if (BB1V == BB2V) continue; @@ -1361,9 +1387,9 @@ HoistTerminator: 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) - if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) - PN->setIncomingValue(i, SI); + for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) + if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2) + PN.setIncomingValue(i, SI); } } @@ -1535,20 +1561,20 @@ static bool sinkLastInstruction(ArrayRef<BasicBlock*> Blocks) { I0->getOperandUse(O).set(NewOperands[O]); I0->moveBefore(&*BBEnd->getFirstInsertionPt()); - // The debug location for the "common" instruction is the merged locations of - // all the commoned instructions. We start with the original location of the - // "common" instruction and iteratively merge each location in the loop below. - const DILocation *Loc = I0->getDebugLoc(); - // Update metadata and IR flags, and merge debug locations. for (auto *I : Insts) if (I != I0) { - Loc = DILocation::getMergedLocation(Loc, I->getDebugLoc()); + // The debug location for the "common" instruction is the merged locations + // of all the commoned instructions. We start with the original location + // of the "common" instruction and iteratively merge each location in the + // loop below. + // This is an N-way merge, which will be inefficient if I0 is a CallInst. + // However, as N-way merge for CallInst is rare, so we use simplified API + // instead of using complex API for N-way merge. + I0->applyMergedLocation(I0->getDebugLoc(), I->getDebugLoc()); combineMetadataForCSE(I0, I); I0->andIRFlags(I); } - if (!isa<CallInst>(I0)) - I0->setDebugLoc(Loc); if (!isa<StoreInst>(I0)) { // canSinkLastInstruction checked that all instructions were used by @@ -1582,9 +1608,9 @@ namespace { ArrayRef<BasicBlock*> Blocks; SmallVector<Instruction*,4> Insts; bool Fail; + public: - LockstepReverseIterator(ArrayRef<BasicBlock*> Blocks) : - Blocks(Blocks) { + LockstepReverseIterator(ArrayRef<BasicBlock*> Blocks) : Blocks(Blocks) { reset(); } @@ -1608,7 +1634,7 @@ namespace { return !Fail; } - void operator -- () { + void operator--() { if (Fail) return; for (auto *&Inst : Insts) { @@ -1629,14 +1655,11 @@ namespace { } // end anonymous namespace -/// Given an unconditional branch that goes to BBEnd, -/// check whether BBEnd has only two predecessors and the other predecessor -/// ends with an unconditional branch. If it is true, sink any common code -/// in the two predecessors to BBEnd. -static bool SinkThenElseCodeToEnd(BranchInst *BI1) { - assert(BI1->isUnconditional()); - BasicBlock *BBEnd = BI1->getSuccessor(0); - +/// Check whether BB's predecessors end with unconditional branches. If it is +/// true, sink any common code from the predecessors to BB. +/// We also allow one predecessor to end with conditional branch (but no more +/// than one). +static bool SinkCommonCodeFromPredecessors(BasicBlock *BB) { // We support two situations: // (1) all incoming arcs are unconditional // (2) one incoming arc is conditional @@ -1680,7 +1703,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { // SmallVector<BasicBlock*,4> UnconditionalPreds; Instruction *Cond = nullptr; - for (auto *B : predecessors(BBEnd)) { + for (auto *B : predecessors(BB)) { auto *T = B->getTerminator(); if (isa<BranchInst>(T) && cast<BranchInst>(T)->isUnconditional()) UnconditionalPreds.push_back(B); @@ -1748,8 +1771,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) { DEBUG(dbgs() << "SINK: Splitting edge\n"); // We have a conditional edge and we're going to sink some instructions. // Insert a new block postdominating all blocks we're going to sink from. - if (!SplitBlockPredecessors(BI1->getSuccessor(0), UnconditionalPreds, - ".sink.split")) + if (!SplitBlockPredecessors(BB, UnconditionalPreds, ".sink.split")) // Edges couldn't be split. return false; Changed = true; @@ -1916,6 +1938,8 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // - All of their uses are in CondBB. SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts; + SmallVector<Instruction *, 4> SpeculatedDbgIntrinsics; + unsigned SpeculationCost = 0; Value *SpeculatedStoreValue = nullptr; StoreInst *SpeculatedStore = nullptr; @@ -1924,8 +1948,10 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, BBI != BBE; ++BBI) { Instruction *I = &*BBI; // Skip debug info. - if (isa<DbgInfoIntrinsic>(I)) + if (isa<DbgInfoIntrinsic>(I)) { + SpeculatedDbgIntrinsics.push_back(I); continue; + } // Only speculatively execute a single instruction (not counting the // terminator) for now. @@ -1974,10 +2000,9 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // Check that the PHI nodes can be converted to selects. bool HaveRewritablePHIs = false; - for (BasicBlock::iterator I = EndBB->begin(); - PHINode *PN = dyn_cast<PHINode>(I); ++I) { - Value *OrigV = PN->getIncomingValueForBlock(BB); - Value *ThenV = PN->getIncomingValueForBlock(ThenBB); + for (PHINode &PN : EndBB->phis()) { + Value *OrigV = PN.getIncomingValueForBlock(BB); + Value *ThenV = PN.getIncomingValueForBlock(ThenBB); // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf. // Skip PHIs which are trivial. @@ -1985,8 +2010,8 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, continue; // Don't convert to selects if we could remove undefined behavior instead. - if (passingValueIsAlwaysUndefined(OrigV, PN) || - passingValueIsAlwaysUndefined(ThenV, PN)) + if (passingValueIsAlwaysUndefined(OrigV, &PN) || + passingValueIsAlwaysUndefined(ThenV, &PN)) return false; HaveRewritablePHIs = true; @@ -2030,11 +2055,10 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, if (Invert) std::swap(TrueV, FalseV); Value *S = Builder.CreateSelect( - BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); + BrCond, TrueV, FalseV, "spec.store.select", BI); SpeculatedStore->setOperand(0, S); - SpeculatedStore->setDebugLoc( - DILocation::getMergedLocation( - BI->getDebugLoc(), SpeculatedStore->getDebugLoc())); + SpeculatedStore->applyMergedLocation(BI->getDebugLoc(), + SpeculatedStore->getDebugLoc()); } // Metadata can be dependent on the condition we are hoisting above. @@ -2048,12 +2072,11 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, // Insert selects and rewrite the PHI operands. IRBuilder<NoFolder> Builder(BI); - for (BasicBlock::iterator I = EndBB->begin(); - PHINode *PN = dyn_cast<PHINode>(I); ++I) { - unsigned OrigI = PN->getBasicBlockIndex(BB); - unsigned ThenI = PN->getBasicBlockIndex(ThenBB); - Value *OrigV = PN->getIncomingValue(OrigI); - Value *ThenV = PN->getIncomingValue(ThenI); + for (PHINode &PN : EndBB->phis()) { + unsigned OrigI = PN.getBasicBlockIndex(BB); + unsigned ThenI = PN.getBasicBlockIndex(ThenBB); + Value *OrigV = PN.getIncomingValue(OrigI); + Value *ThenV = PN.getIncomingValue(ThenI); // Skip PHIs which are trivial. if (OrigV == ThenV) @@ -2066,11 +2089,17 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB, if (Invert) std::swap(TrueV, FalseV); Value *V = Builder.CreateSelect( - BrCond, TrueV, FalseV, TrueV->getName() + "." + FalseV->getName(), BI); - PN->setIncomingValue(OrigI, V); - PN->setIncomingValue(ThenI, V); + BrCond, TrueV, FalseV, "spec.select", BI); + PN.setIncomingValue(OrigI, V); + PN.setIncomingValue(ThenI, V); } + // Remove speculated dbg intrinsics. + // FIXME: Is it possible to do this in a more elegant way? Moving/merging the + // dbg value for the different flows and inserting it after the select. + for (Instruction *I : SpeculatedDbgIntrinsics) + I->eraseFromParent(); + ++NumSpeculations; return true; } @@ -2507,7 +2536,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { else { // For unconditional branch, check for a simple CFG pattern, where // BB has a single predecessor and BB's successor is also its predecessor's - // successor. If such pattern exisits, check for CSE between BB and its + // successor. If such pattern exists, check for CSE between BB and its // predecessor. if (BasicBlock *PB = BB->getSinglePredecessor()) if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) @@ -2725,9 +2754,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(), NewWeights.end()); - PBI->setMetadata( - LLVMContext::MD_prof, - MDBuilder(BI->getContext()).createBranchWeights(MDWeights)); + setBranchWeights(PBI, MDWeights[0], MDWeights[1]); } else PBI->setMetadata(LLVMContext::MD_prof, nullptr); } else { @@ -2860,7 +2887,8 @@ static Value *ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, - bool InvertPCond, bool InvertQCond) { + bool InvertPCond, bool InvertQCond, + const DataLayout &DL) { auto IsaBitcastOfPointerType = [](const Instruction &I) { return Operator::getOpcode(&I) == Instruction::BitCast && I.getType()->isPointerTy(); @@ -2887,7 +2915,9 @@ static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, else return false; } - return N <= PHINodeFoldingThreshold; + // The store we want to merge is counted in N, so add 1 to make sure + // we're counting the instructions that would be left. + return N <= (PHINodeFoldingThreshold + 1); }; if (!MergeCondStoresAggressively && @@ -2966,6 +2996,29 @@ static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, PStore->getAAMetadata(AAMD, /*Merge=*/false); PStore->getAAMetadata(AAMD, /*Merge=*/true); SI->setAAMetadata(AAMD); + unsigned PAlignment = PStore->getAlignment(); + unsigned QAlignment = QStore->getAlignment(); + unsigned TypeAlignment = + DL.getABITypeAlignment(SI->getValueOperand()->getType()); + unsigned MinAlignment; + unsigned MaxAlignment; + std::tie(MinAlignment, MaxAlignment) = std::minmax(PAlignment, QAlignment); + // Choose the minimum alignment. If we could prove both stores execute, we + // could use biggest one. In this case, though, we only know that one of the + // stores executes. And we don't know it's safe to take the alignment from a + // store that doesn't execute. + if (MinAlignment != 0) { + // Choose the minimum of all non-zero alignments. + SI->setAlignment(MinAlignment); + } else if (MaxAlignment != 0) { + // Choose the minimal alignment between the non-zero alignment and the ABI + // default alignment for the type of the stored value. + SI->setAlignment(std::min(MaxAlignment, TypeAlignment)); + } else { + // If both alignments are zero, use ABI default alignment for the type of + // the stored value. + SI->setAlignment(TypeAlignment); + } QStore->eraseFromParent(); PStore->eraseFromParent(); @@ -2973,7 +3026,8 @@ static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, return true; } -static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { +static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, + const DataLayout &DL) { // The intention here is to find diamonds or triangles (see below) where each // conditional block contains a store to the same address. Both of these // stores are conditional, so they can't be unconditionally sunk. But it may @@ -3001,7 +3055,6 @@ 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); @@ -3076,7 +3129,7 @@ static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) { bool Changed = false; for (auto *Address : CommonAddresses) Changed |= mergeConditionalStoreToAddress( - PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond); + PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL); return Changed; } @@ -3141,7 +3194,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // 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. - if (MergeCondStores && mergeConditionalStores(PBI, BI)) + if (MergeCondStores && mergeConditionalStores(PBI, BI, DL)) return true; // If this is a conditional branch in an empty block, and if any @@ -3270,9 +3323,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // Halve the weights if any of them cannot fit in an uint32_t FitWeights(NewWeights); - PBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(BI->getContext()) - .createBranchWeights(NewWeights[0], NewWeights[1])); + setBranchWeights(PBI, NewWeights[0], NewWeights[1]); } // OtherDest may have phi nodes. If so, add an entry from PBI's @@ -3283,17 +3334,15 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, // it. If it has PHIs though, the PHIs may have different // entries for BB and PBI's BB. If so, insert a select to make // them agree. - PHINode *PN; - for (BasicBlock::iterator II = CommonDest->begin(); - (PN = dyn_cast<PHINode>(II)); ++II) { - Value *BIV = PN->getIncomingValueForBlock(BB); - unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); - Value *PBIV = PN->getIncomingValue(PBBIdx); + for (PHINode &PN : CommonDest->phis()) { + Value *BIV = PN.getIncomingValueForBlock(BB); + unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent()); + Value *PBIV = PN.getIncomingValue(PBBIdx); if (BIV != PBIV) { // Insert a select in PBI to pick the right value. SelectInst *NV = cast<SelectInst>( Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux")); - PN->setIncomingValue(PBBIdx, NV); + 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 @@ -3310,9 +3359,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, FitWeights(NewWeights); - NV->setMetadata(LLVMContext::MD_prof, - MDBuilder(BI->getContext()) - .createBranchWeights(NewWeights[0], NewWeights[1])); + setBranchWeights(NV, NewWeights[0], NewWeights[1]); } } } @@ -3367,9 +3414,7 @@ static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, // Create a conditional branch sharing the condition of the select. BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB); if (TrueWeight != FalseWeight) - NewBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(OldTerm->getContext()) - .createBranchWeights(TrueWeight, FalseWeight)); + setBranchWeights(NewBI, TrueWeight, FalseWeight); } } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { // Neither of the selected blocks were successors, so this @@ -3464,10 +3509,9 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { /// /// We prefer to split the edge to 'end' so that there is a true/false entry to /// the PHI, merging the third icmp into the switch. -static bool TryToSimplifyUncondBranchWithICmpInIt( +static bool tryToSimplifyUncondBranchWithICmpInIt( ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL, - const TargetTransformInfo &TTI, unsigned BonusInstThreshold, - AssumptionCache *AC) { + const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options) { BasicBlock *BB = ICI->getParent(); // If the block has any PHIs in it or the icmp has multiple uses, it is too @@ -3502,7 +3546,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( ICI->eraseFromParent(); } // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } // Ok, the block is reachable from the default dest. If the constant we're @@ -3518,7 +3562,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } // The use of the icmp has to be in the 'end' block, by the only PHI node in @@ -3556,9 +3600,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( Weights.push_back(Weights[0]); SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); - SI->setMetadata( - LLVMContext::MD_prof, - MDBuilder(SI->getContext()).createBranchWeights(MDWeights)); + setBranchWeights(SI, MDWeights); } } SI->addCase(Cst, NewBB); @@ -4285,10 +4327,7 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { TrueWeight /= 2; FalseWeight /= 2; } - NewBI->setMetadata(LLVMContext::MD_prof, - MDBuilder(SI->getContext()) - .createBranchWeights((uint32_t)TrueWeight, - (uint32_t)FalseWeight)); + setBranchWeights(NewBI, TrueWeight, FalseWeight); } } @@ -4316,7 +4355,7 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { /// Compute masked bits for the condition of a switch /// and use it to remove dead cases. -static bool EliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, +static bool eliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC, const DataLayout &DL) { Value *Cond = SI->getCondition(); unsigned Bits = Cond->getType()->getIntegerBitWidth(); @@ -4385,9 +4424,7 @@ 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)); + setBranchWeights(SI, MDWeights); } return !DeadCases.empty(); @@ -4411,17 +4448,16 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *Succ = Branch->getSuccessor(0); - BasicBlock::iterator I = Succ->begin(); - while (PHINode *PHI = dyn_cast<PHINode>(I++)) { - int Idx = PHI->getBasicBlockIndex(BB); + for (PHINode &PHI : Succ->phis()) { + int Idx = PHI.getBasicBlockIndex(BB); assert(Idx >= 0 && "PHI has no entry for predecessor?"); - Value *InValue = PHI->getIncomingValue(Idx); + Value *InValue = PHI.getIncomingValue(Idx); if (InValue != CaseValue) continue; *PhiIndex = Idx; - return PHI; + return &PHI; } return nullptr; @@ -4429,38 +4465,56 @@ static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, /// Try to forward the condition of a switch instruction to a phi node /// dominated by the switch, if that would mean that some of the destination -/// blocks of the switch can be folded away. -/// Returns true if a change is made. +/// blocks of the switch can be folded away. Return true if a change is made. static bool ForwardSwitchConditionToPHI(SwitchInst *SI) { - typedef DenseMap<PHINode *, SmallVector<int, 4>> ForwardingNodesMap; - ForwardingNodesMap ForwardingNodes; + using ForwardingNodesMap = DenseMap<PHINode *, SmallVector<int, 4>>; - for (auto Case : SI->cases()) { + ForwardingNodesMap ForwardingNodes; + BasicBlock *SwitchBlock = SI->getParent(); + bool Changed = false; + for (auto &Case : SI->cases()) { ConstantInt *CaseValue = Case.getCaseValue(); BasicBlock *CaseDest = Case.getCaseSuccessor(); - int PhiIndex; - PHINode *PHI = - FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIndex); - if (!PHI) - continue; + // Replace phi operands in successor blocks that are using the constant case + // value rather than the switch condition variable: + // switchbb: + // switch i32 %x, label %default [ + // i32 17, label %succ + // ... + // succ: + // %r = phi i32 ... [ 17, %switchbb ] ... + // --> + // %r = phi i32 ... [ %x, %switchbb ] ... + + for (PHINode &Phi : CaseDest->phis()) { + // This only works if there is exactly 1 incoming edge from the switch to + // a phi. If there is >1, that means multiple cases of the switch map to 1 + // value in the phi, and that phi value is not the switch condition. Thus, + // this transform would not make sense (the phi would be invalid because + // a phi can't have different incoming values from the same block). + int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock); + if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue && + count(Phi.blocks(), SwitchBlock) == 1) { + Phi.setIncomingValue(SwitchBBIdx, SI->getCondition()); + Changed = true; + } + } - ForwardingNodes[PHI].push_back(PhiIndex); + // Collect phi nodes that are indirectly using this switch's case constants. + int PhiIdx; + if (auto *Phi = FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIdx)) + ForwardingNodes[Phi].push_back(PhiIdx); } - bool Changed = false; - - for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), - E = ForwardingNodes.end(); - I != E; ++I) { - PHINode *Phi = I->first; - SmallVectorImpl<int> &Indexes = I->second; - + for (auto &ForwardingNode : ForwardingNodes) { + PHINode *Phi = ForwardingNode.first; + SmallVectorImpl<int> &Indexes = ForwardingNode.second; if (Indexes.size() < 2) continue; - for (size_t I = 0, E = Indexes.size(); I != E; ++I) - Phi->setIncomingValue(Indexes[I], SI->getCondition()); + for (int Index : Indexes) + Phi->setIncomingValue(Index, SI->getCondition()); Changed = true; } @@ -4595,14 +4649,13 @@ GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, return false; // Get the values for this case from phi nodes in the destination block. - BasicBlock::iterator I = (*CommonDest)->begin(); - while (PHINode *PHI = dyn_cast<PHINode>(I++)) { - int Idx = PHI->getBasicBlockIndex(Pred); + for (PHINode &PHI : (*CommonDest)->phis()) { + int Idx = PHI.getBasicBlockIndex(Pred); if (Idx == -1) continue; Constant *ConstVal = - LookupConstant(PHI->getIncomingValue(Idx), ConstantPool); + LookupConstant(PHI.getIncomingValue(Idx), ConstantPool); if (!ConstVal) return false; @@ -4610,7 +4663,7 @@ GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, if (!ValidLookupTableConstant(ConstVal, TTI)) return false; - Res.push_back(std::make_pair(PHI, ConstVal)); + Res.push_back(std::make_pair(&PHI, ConstVal)); } return Res.size() > 0; @@ -4743,8 +4796,8 @@ static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI, /// If the switch is only used to initialize one or more /// phi nodes in a common successor block with only two different /// constant values, replace the switch with select. -static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, - AssumptionCache *AC, const DataLayout &DL, +static bool switchToSelect(SwitchInst *SI, IRBuilder<> &Builder, + const DataLayout &DL, const TargetTransformInfo &TTI) { Value *const Cond = SI->getCondition(); PHINode *PHI = nullptr; @@ -4816,18 +4869,18 @@ private: } Kind; // For SingleValueKind, this is the single value. - Constant *SingleValue; + Constant *SingleValue = nullptr; // For BitMapKind, this is the bitmap. - ConstantInt *BitMap; - IntegerType *BitMapElementTy; + ConstantInt *BitMap = nullptr; + IntegerType *BitMapElementTy = nullptr; // For LinearMapKind, these are the constants used to derive the value. - ConstantInt *LinearOffset; - ConstantInt *LinearMultiplier; + ConstantInt *LinearOffset = nullptr; + ConstantInt *LinearMultiplier = nullptr; // For ArrayKind, this is the array. - GlobalVariable *Array; + GlobalVariable *Array = nullptr; }; } // end anonymous namespace @@ -4835,9 +4888,7 @@ private: SwitchLookupTable::SwitchLookupTable( Module &M, uint64_t TableSize, ConstantInt *Offset, const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values, - Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) - : SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr), - LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) { + Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) { assert(Values.size() && "Can't build lookup table without values!"); assert(TableSize >= Values.size() && "Can't fit values in table!"); @@ -5083,7 +5134,6 @@ 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) return; @@ -5112,7 +5162,7 @@ static void reuseTableCompare( for (auto ValuePair : Values) { Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(), ValuePair.second, CmpOp1, true); - if (!CaseConst || CaseConst == DefaultConst) + if (!CaseConst || CaseConst == DefaultConst || isa<UndefValue>(CaseConst)) return; assert((CaseConst == TrueConst || CaseConst == FalseConst) && "Expect true or false as compare result."); @@ -5151,8 +5201,11 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, const TargetTransformInfo &TTI) { assert(SI->getNumCases() > 1 && "Degenerate switch?"); - // Only build lookup table when we have a target that supports it. - if (!TTI.shouldBuildLookupTables()) + Function *Fn = SI->getParent()->getParent(); + // Only build lookup table when we have a target that supports it or the + // attribute is not set. + if (!TTI.shouldBuildLookupTables() || + (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true")) return false; // FIXME: If the switch is too sparse for a lookup table, perhaps we could @@ -5163,8 +5216,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // string and lookup indices into that. // Ignore switches with less than three cases. Lookup tables will not make - // them - // faster, so we don't analyze them. + // them faster, so we don't analyze them. if (SI->getNumCases() < 3) return false; @@ -5176,8 +5228,10 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, ConstantInt *MaxCaseVal = CI->getCaseValue(); BasicBlock *CommonDest = nullptr; - typedef SmallVector<std::pair<ConstantInt *, Constant *>, 4> ResultListTy; + + using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>; SmallDenseMap<PHINode *, ResultListTy> ResultLists; + SmallDenseMap<PHINode *, Constant *> DefaultResults; SmallDenseMap<PHINode *, Type *> ResultTypes; SmallVector<PHINode *, 4> PHIs; @@ -5190,7 +5244,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; + using ResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>; ResultsTy Results; if (!GetCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest, Results, DL, TTI)) @@ -5248,8 +5302,12 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // Compute the table index value. Builder.SetInsertPoint(SI); - Value *TableIndex = - Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx"); + Value *TableIndex; + if (MinCaseVal->isNullValue()) + TableIndex = SI->getCondition(); + else + TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, + "switch.tableidx"); // Compute the maximum table size representable by the integer type we are // switching upon. @@ -5282,15 +5340,14 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, Builder.SetInsertPoint(LookupBB); if (NeedMask) { - // Before doing the lookup we do the hole check. - // The LookupBB is therefore re-purposed to do the hole check - // and we create a new LookupBB. + // Before doing the lookup, we do the hole check. The LookupBB is therefore + // re-purposed to do the hole check, and we create a new LookupBB. BasicBlock *MaskBB = LookupBB; MaskBB->setName("switch.hole_check"); LookupBB = BasicBlock::Create(Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest); - // Make the mask's bitwidth at least 8bit and a power-of-2 to avoid + // Make the mask's bitwidth at least 8-bit and a power-of-2 to avoid // unnecessary illegal types. uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL)); APInt MaskInt(TableSizePowOf2, 0); @@ -5320,7 +5377,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, } if (!DefaultIsReachable || GeneratingCoveredLookupTable) { - // We cached PHINodes in PHIs, to avoid accessing deleted PHINodes later, + // We cached PHINodes in PHIs. To avoid accessing deleted PHINodes later, // do not delete PHINodes here. SI->getDefaultDest()->removePredecessor(SI->getParent(), /*DontDeleteUselessPHIs=*/true); @@ -5333,7 +5390,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, // If using a bitmask, use any value to fill the lookup table holes. Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI]; - StringRef FuncName = SI->getParent()->getParent()->getName(); + StringRef FuncName = Fn->getName(); SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL, FuncName); @@ -5391,14 +5448,14 @@ static bool isSwitchDense(ArrayRef<int64_t> Values) { return NumCases * 100 >= Range * MinDensity; } -// Try and transform a switch that has "holes" in it to a contiguous sequence -// of cases. -// -// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be -// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}. -// -// This converts a sparse switch into a dense switch which allows better -// lowering and could also allow transforming into a lookup table. +/// Try to transform a switch that has "holes" in it to a contiguous sequence +/// of cases. +/// +/// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be +/// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}. +/// +/// This converts a sparse switch into a dense switch which allows better +/// lowering and could also allow transforming into a lookup table. static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI) { @@ -5427,7 +5484,7 @@ static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, // First, transform the values such that they start at zero and ascend. int64_t Base = Values[0]; for (auto &V : Values) - V -= Base; + V -= (uint64_t)(Base); // Now we have signed numbers that have been shifted so that, given enough // precision, there are no negative values. Since the rest of the transform @@ -5492,12 +5549,12 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { // see if that predecessor totally determines the outcome of this switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; Value *Cond = SI->getCondition(); if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) if (SimplifySwitchOnSelect(SI, Select)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; // If the block only contains the switch, see if we can fold the block // away into any preds. @@ -5507,33 +5564,34 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { ++BBI; if (SI == &*BBI) if (FoldValueComparisonIntoPredecessors(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; // Remove unreachable cases. - if (EliminateDeadSwitchCases(SI, AC, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (eliminateDeadSwitchCases(SI, Options.AC, DL)) + return simplifyCFG(BB, TTI, Options) | true; - if (SwitchToSelect(SI, Builder, AC, DL, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (switchToSelect(SI, Builder, DL, TTI)) + return simplifyCFG(BB, TTI, Options) | true; - if (ForwardSwitchConditionToPHI(SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI)) + return simplifyCFG(BB, TTI, Options) | true; - // The conversion from switch to lookup tables results in difficult - // to analyze code and makes pruning branches much harder. - // This is a problem of the switch expression itself can still be - // restricted as a result of inlining or CVP. There only apply this - // transformation during late steps of the optimisation chain. - if (LateSimplifyCFG && SwitchToLookupTable(SI, Builder, DL, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + // The conversion from switch to lookup tables results in difficult-to-analyze + // code and makes pruning branches much harder. This is a problem if the + // switch expression itself can still be restricted as a result of inlining or + // CVP. Therefore, only apply this transformation during late stages of the + // optimisation pipeline. + if (Options.ConvertSwitchToLookupTable && + SwitchToLookupTable(SI, Builder, DL, TTI)) + return simplifyCFG(BB, TTI, Options) | true; if (ReduceSwitchRange(SI, Builder, DL, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; return false; } @@ -5571,7 +5629,7 @@ bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { if (SimplifyIndirectBrOnSelect(IBI, SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } return Changed; } @@ -5613,8 +5671,8 @@ 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; @@ -5658,39 +5716,35 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, BasicBlock *BB = BI->getParent(); BasicBlock *Succ = BI->getSuccessor(0); - 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 or its successor is a loop - // header (This is for early invocations before loop simplify and + // If LoopHeader is provided, check if the block or its successor 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.) bool NeedCanonicalLoop = - !LateSimplifyCFG && + Options.NeedCanonicalLoop && (LoopHeaders && (LoopHeaders->count(BB) || LoopHeaders->count(Succ))); BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && !NeedCanonicalLoop && TryToSimplifyUncondBranchFromEmptyBlock(BB)) return true; - // If the only instruction in the block is a seteq/setne comparison - // against a constant, try to simplify the block. + // If the only instruction in the block is a seteq/setne comparison against a + // constant, try to simplify the block. if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { for (++I; isa<DbgInfoIntrinsic>(I); ++I) ; if (I->isTerminator() && - TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, - BonusInstThreshold, AC)) + tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, Options)) return true; } // 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) { - } + for (++I; isa<DbgInfoIntrinsic>(I); ++I) + ; if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB)) return true; } @@ -5699,8 +5753,8 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, // branches to us and our successor, fold the comparison into the // predecessor and use logical operations to update the incoming value // for PHI nodes in common successor. - if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold)) + return simplifyCFG(BB, TTI, Options) | true; return false; } @@ -5725,7 +5779,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { // switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; // This block must be empty, except for the setcond inst, if it exists. // Ignore dbg intrinsics. @@ -5735,14 +5789,14 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { ++I; if (&*I == BI) { if (FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } else if (&*I == cast<Instruction>(BI->getCondition())) { ++I; // Ignore dbg intrinsics. while (isa<DbgInfoIntrinsic>(I)) ++I; if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } } @@ -5758,9 +5812,9 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (PBI && PBI->isConditional() && PBI->getSuccessor(0) != PBI->getSuccessor(1)) { assert(PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB); - bool CondIsFalse = PBI->getSuccessor(1) == BB; + bool CondIsTrue = PBI->getSuccessor(0) == BB; Optional<bool> Implication = isImpliedCondition( - PBI->getCondition(), BI->getCondition(), DL, CondIsFalse); + PBI->getCondition(), BI->getCondition(), DL, CondIsTrue); if (Implication) { // Turn this into a branch on constant. auto *OldCond = BI->getCondition(); @@ -5769,7 +5823,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { : ConstantInt::getFalse(BB->getContext()); BI->setCondition(CI); RecursivelyDeleteTriviallyDeadInstructions(OldCond); - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } } } @@ -5777,8 +5831,8 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { // If this basic block is ONLY a compare and a branch, and if a predecessor // branches to us and one of our successors, fold the comparison into the // predecessor and use logical operations to pick the right destination. - if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (FoldBranchToCommonDest(BI, Options.BonusInstThreshold)) + return simplifyCFG(BB, TTI, Options) | true; // We have a conditional branch to two blocks that are only reachable // from BI. We know that the condbr dominates the two blocks, so see if @@ -5787,7 +5841,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (BI->getSuccessor(0)->getSinglePredecessor()) { if (BI->getSuccessor(1)->getSinglePredecessor()) { if (HoistThenElseCodeToIf(BI, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } else { // If Successor #1 has multiple preds, we may be able to conditionally // execute Successor #0 if it branches to Successor #1. @@ -5795,7 +5849,7 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (Succ0TI->getNumSuccessors() == 1 && Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } } else if (BI->getSuccessor(1)->getSinglePredecessor()) { // If Successor #0 has multiple preds, we may be able to conditionally @@ -5804,30 +5858,30 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { if (Succ1TI->getNumSuccessors() == 1 && Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; } // If this is a branch on a phi node in the current block, thread control // through this block if any PHI node entries are constants. if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) if (PN->getParent() == BI->getParent()) - if (FoldCondBranchOnPHI(BI, DL, AC)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (FoldCondBranchOnPHI(BI, DL, Options.AC)) + return simplifyCFG(BB, TTI, Options) | true; // Scan predecessor blocks for conditional branches. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) if (PBI != BI && PBI->isConditional()) if (SimplifyCondBranchToCondBranch(PBI, BI, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return simplifyCFG(BB, TTI, Options) | true; // Look for diamond patterns. if (MergeCondStores) if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB)) if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator())) if (PBI != BI && PBI->isConditional()) - if (mergeConditionalStores(PBI, BI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + if (mergeConditionalStores(PBI, BI, DL)) + return simplifyCFG(BB, TTI, Options) | true; return false; } @@ -5884,14 +5938,13 @@ static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { /// If BB has an incoming value that will always trigger undefined behavior /// (eg. null pointer dereference), remove the branch leading here. static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { - for (BasicBlock::iterator i = BB->begin(); - PHINode *PHI = dyn_cast<PHINode>(i); ++i) - for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) - if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { - TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); + for (PHINode &PHI : BB->phis()) + for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) + if (passingValueIsAlwaysUndefined(PHI.getIncomingValue(i), &PHI)) { + TerminatorInst *T = PHI.getIncomingBlock(i)->getTerminator(); IRBuilder<> Builder(T); if (BranchInst *BI = dyn_cast<BranchInst>(T)) { - BB->removePredecessor(PHI->getIncomingBlock(i)); + BB->removePredecessor(PHI.getIncomingBlock(i)); // Turn uncoditional branches into unreachables and remove the dead // destination from conditional branches. if (BI->isUnconditional()) @@ -5936,20 +5989,22 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { // Merge basic blocks into their predecessor if there is only one distinct // pred, and if there is only one distinct successor of the predecessor, and // if there are no PHI nodes. - // if (MergeBlockIntoPredecessor(BB)) return true; + if (SinkCommon && Options.SinkCommonInsts) + Changed |= SinkCommonCodeFromPredecessors(BB); + IRBuilder<> Builder(BB); // If there is a trivial two-entry PHI node in this basic block, and we can // eliminate it, do so now. - if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) + if (auto *PN = dyn_cast<PHINode>(BB->begin())) if (PN->getNumIncomingValues() == 2) Changed |= FoldTwoEntryPHINode(PN, TTI, DL); Builder.SetInsertPoint(BB->getTerminator()); - if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { + if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator())) { if (BI->isUnconditional()) { if (SimplifyUncondBranch(BI, Builder)) return true; @@ -5957,25 +6012,22 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { if (SimplifyCondBranch(BI, Builder)) return true; } - } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { + } else if (auto *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { if (SimplifyReturn(RI, Builder)) return true; - } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { + } else if (auto *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { if (SimplifyResume(RI, Builder)) return true; - } else if (CleanupReturnInst *RI = - dyn_cast<CleanupReturnInst>(BB->getTerminator())) { + } else if (auto *RI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) { if (SimplifyCleanupReturn(RI)) return true; - } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { + } else if (auto *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { if (SimplifySwitch(SI, Builder)) return true; - } else if (UnreachableInst *UI = - dyn_cast<UnreachableInst>(BB->getTerminator())) { + } else if (auto *UI = dyn_cast<UnreachableInst>(BB->getTerminator())) { if (SimplifyUnreachable(UI)) return true; - } else if (IndirectBrInst *IBI = - dyn_cast<IndirectBrInst>(BB->getTerminator())) { + } else if (auto *IBI = dyn_cast<IndirectBrInst>(BB->getTerminator())) { if (SimplifyIndirectBr(IBI)) return true; } @@ -5983,16 +6035,10 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { return Changed; } -/// This function is used to do simplification of a CFG. -/// For example, it adjusts branches to branches to eliminate the extra hop, -/// eliminates unreachable basic blocks, and does other "peephole" optimization -/// of the CFG. It returns true if a modification was made. -/// -bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC, - SmallPtrSetImpl<BasicBlock *> *LoopHeaders, - bool LateSimplifyCFG) { - return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), - BonusInstThreshold, AC, LoopHeaders, LateSimplifyCFG) +bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, + const SimplifyCFGOptions &Options, + SmallPtrSetImpl<BasicBlock *> *LoopHeaders) { + return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders, + Options) .run(BB); } |