diff options
Diffstat (limited to 'lib/Transforms/Utils')
21 files changed, 163 insertions, 193 deletions
diff --git a/lib/Transforms/Utils/ASanStackFrameLayout.cpp b/lib/Transforms/Utils/ASanStackFrameLayout.cpp index 03c3a80170a3..72cdfa464a3b 100644 --- a/lib/Transforms/Utils/ASanStackFrameLayout.cpp +++ b/lib/Transforms/Utils/ASanStackFrameLayout.cpp @@ -107,4 +107,4 @@ ComputeASanStackFrameLayout(SmallVectorImpl<ASanStackVariableDescription> &Vars, assert(Layout->FrameSize / Granularity == Layout->ShadowBytes.size()); } -} // llvm namespace +} // namespace llvm diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index f3c801348a62..798376e95543 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -486,11 +486,12 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, } // Create new basic block, insert right before the original block. - BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, - BB->getParent(), BB); + BasicBlock *NewBB = BasicBlock::Create( + BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB); // The new block unconditionally branches to the old block. BranchInst *BI = BranchInst::Create(BB, NewBB); + BI->setDebugLoc(BB->getFirstNonPHI()->getDebugLoc()); // Move the edges from Preds to point to NewBB instead of BB. for (unsigned i = 0, e = Preds.size(); i != e; ++i) { @@ -553,6 +554,7 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, // The new block unconditionally branches to the old block. BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); + BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); // Move the edges from Preds to point to NewBB1 instead of OrigBB. for (unsigned i = 0, e = Preds.size(); i != e; ++i) { @@ -593,6 +595,7 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, // The new block unconditionally branches to the old block. BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); + BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); // Move the remaining edges from OrigBB to point to NewBB2. for (SmallVectorImpl<BasicBlock*>::iterator diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 7e83c9eeceb7..362cd9bbee7b 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -60,7 +60,7 @@ namespace { AU.addPreservedID(LoopSimplifyID); } }; -} +} // namespace char BreakCriticalEdges::ID = 0; INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", diff --git a/lib/Transforms/Utils/BypassSlowDivision.cpp b/lib/Transforms/Utils/BypassSlowDivision.cpp index f2d5e0745035..0771b29b24fd 100644 --- a/lib/Transforms/Utils/BypassSlowDivision.cpp +++ b/lib/Transforms/Utils/BypassSlowDivision.cpp @@ -42,7 +42,7 @@ namespace { DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder) : Quotient(InQuotient), Remainder(InRemainder) {} }; -} +} // namespace namespace llvm { template<> @@ -69,7 +69,7 @@ namespace llvm { }; typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy; -} +} // namespace llvm // insertFastDiv - Substitutes the div/rem instruction with code that checks the // value of the operands and uses a shorter-faster div/rem instruction when diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp index 4f8d1dfbe5df..e623445b284b 100644 --- a/lib/Transforms/Utils/CloneFunction.cpp +++ b/lib/Transforms/Utils/CloneFunction.cpp @@ -289,7 +289,7 @@ namespace { BasicBlock::const_iterator StartingInst, std::vector<const BasicBlock*> &ToClone); }; -} +} // namespace /// The specified block is found to be reachable, clone it and /// anything that it can reach. diff --git a/lib/Transforms/Utils/CtorUtils.cpp b/lib/Transforms/Utils/CtorUtils.cpp index dc95089cd2ca..4bbded8dc998 100644 --- a/lib/Transforms/Utils/CtorUtils.cpp +++ b/lib/Transforms/Utils/CtorUtils.cpp @@ -162,4 +162,4 @@ bool optimizeGlobalCtorsList(Module &M, return true; } -} // End llvm namespace +} // namespace llvm diff --git a/lib/Transforms/Utils/FlattenCFG.cpp b/lib/Transforms/Utils/FlattenCFG.cpp index 4eb3e3dd17d2..40a48c067907 100644 --- a/lib/Transforms/Utils/FlattenCFG.cpp +++ b/lib/Transforms/Utils/FlattenCFG.cpp @@ -46,7 +46,7 @@ public: FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {} bool run(BasicBlock *BB); }; -} +} // namespace /// If \param [in] BB has more than one predecessor that is a conditional /// branch, attempt to use parallel and/or for the branch condition. \returns diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp index ddeaff06d3c8..ea84e7c302d1 100644 --- a/lib/Transforms/Utils/InlineFunction.cpp +++ b/lib/Transforms/Utils/InlineFunction.cpp @@ -121,7 +121,7 @@ namespace { } } }; -} +} // namespace /// Get or create a target for the branch from ResumeInsts. BasicBlock *InvokeInliningInfo::getInnerResumeDest() { @@ -949,35 +949,23 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI, } // Get the personality function from the callee if it contains a landing pad. - Value *CalleePersonality = nullptr; - for (Function::const_iterator I = CalledFunc->begin(), E = CalledFunc->end(); - I != E; ++I) - if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) { - const BasicBlock *BB = II->getUnwindDest(); - const LandingPadInst *LP = BB->getLandingPadInst(); - CalleePersonality = LP->getPersonalityFn(); - break; - } + Constant *CalledPersonality = + CalledFunc->hasPersonalityFn() ? CalledFunc->getPersonalityFn() : nullptr; // Find the personality function used by the landing pads of the caller. If it // exists, then check to see that it matches the personality function used in // the callee. - if (CalleePersonality) { - for (Function::const_iterator I = Caller->begin(), E = Caller->end(); - I != E; ++I) - if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) { - const BasicBlock *BB = II->getUnwindDest(); - const LandingPadInst *LP = BB->getLandingPadInst(); - - // If the personality functions match, then we can perform the - // inlining. Otherwise, we can't inline. - // TODO: This isn't 100% true. Some personality functions are proper - // supersets of others and can be used in place of the other. - if (LP->getPersonalityFn() != CalleePersonality) - return false; - - break; - } + Constant *CallerPersonality = + Caller->hasPersonalityFn() ? Caller->getPersonalityFn() : nullptr; + if (CalledPersonality) { + if (!CallerPersonality) + Caller->setPersonalityFn(CalledPersonality); + // If the personality functions match, then we can perform the + // inlining. Otherwise, we can't inline. + // TODO: This isn't 100% true. Some personality functions are proper + // supersets of others and can be used in place of the other. + else if (CalledPersonality != CallerPersonality) + return false; } // Get an iterator to the last basic block in the function, which will have diff --git a/lib/Transforms/Utils/InstructionNamer.cpp b/lib/Transforms/Utils/InstructionNamer.cpp index da890a297005..c9bec9a9fa79 100644 --- a/lib/Transforms/Utils/InstructionNamer.cpp +++ b/lib/Transforms/Utils/InstructionNamer.cpp @@ -50,7 +50,7 @@ namespace { }; char InstNamer::ID = 0; -} +} // namespace INITIALIZE_PASS(InstNamer, "instnamer", "Assign names to anonymous instructions", false, false) diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index 9d40b6989d6e..fcc79864219e 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -300,7 +300,7 @@ struct LCSSA : public FunctionPass { AU.addPreserved<ScalarEvolution>(); } }; -} +} // namespace char LCSSA::ID = 0; INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 70c77b06d62e..56085579b61c 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -14,6 +14,8 @@ #include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" @@ -828,64 +830,45 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { /// orders them so it usually won't matter. /// bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { - bool Changed = false; - // This implementation doesn't currently consider undef operands // specially. Theoretically, two phis which are identical except for // one having an undef where the other doesn't could be collapsed. - // Map from PHI hash values to PHI nodes. If multiple PHIs have - // the same hash value, the element is the first PHI in the - // linked list in CollisionMap. - DenseMap<uintptr_t, PHINode *> HashMap; + struct PHIDenseMapInfo { + static PHINode *getEmptyKey() { + return DenseMapInfo<PHINode *>::getEmptyKey(); + } + static PHINode *getTombstoneKey() { + return DenseMapInfo<PHINode *>::getTombstoneKey(); + } + static unsigned getHashValue(PHINode *PN) { + // Compute a hash value on the operands. Instcombine will likely have + // sorted them, which helps expose duplicates, but we have to check all + // the operands to be safe in case instcombine hasn't run. + return static_cast<unsigned>(hash_combine( + hash_combine_range(PN->value_op_begin(), PN->value_op_end()), + hash_combine_range(PN->block_begin(), PN->block_end()))); + } + static bool isEqual(PHINode *LHS, PHINode *RHS) { + if (LHS == getEmptyKey() || LHS == getTombstoneKey() || + RHS == getEmptyKey() || RHS == getTombstoneKey()) + return LHS == RHS; + return LHS->isIdenticalTo(RHS); + } + }; - // Maintain linked lists of PHI nodes with common hash values. - DenseMap<PHINode *, PHINode *> CollisionMap; + // Set of unique PHINodes. + DenseSet<PHINode *, PHIDenseMapInfo> PHISet; // Examine each PHI. - for (BasicBlock::iterator I = BB->begin(); - PHINode *PN = dyn_cast<PHINode>(I++); ) { - // Compute a hash value on the operands. Instcombine will likely have sorted - // them, which helps expose duplicates, but we have to check all the - // operands to be safe in case instcombine hasn't run. - uintptr_t Hash = 0; - // This hash algorithm is quite weak as hash functions go, but it seems - // to do a good enough job for this particular purpose, and is very quick. - for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { - Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); - Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); - } - for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); - I != E; ++I) { - Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); - Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); - } - // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. - Hash >>= 1; - // If we've never seen this hash value before, it's a unique PHI. - std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = - HashMap.insert(std::make_pair(Hash, PN)); - if (Pair.second) continue; - // Otherwise it's either a duplicate or a hash collision. - for (PHINode *OtherPN = Pair.first->second; ; ) { - if (OtherPN->isIdenticalTo(PN)) { - // A duplicate. Replace this PHI with its duplicate. - PN->replaceAllUsesWith(OtherPN); - PN->eraseFromParent(); - Changed = true; - break; - } - // A non-duplicate hash collision. - DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); - if (I == CollisionMap.end()) { - // Set this PHI to be the head of the linked list of colliding PHIs. - PHINode *Old = Pair.first->second; - Pair.first->second = PN; - CollisionMap[PN] = Old; - break; - } - // Proceed to the next PHI in the list. - OtherPN = I->second; + bool Changed = false; + for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) { + auto Inserted = PHISet.insert(PN); + if (!Inserted.second) { + // A duplicate. Replace this PHI with its duplicate. + PN->replaceAllUsesWith(*Inserted.first); + PN->eraseFromParent(); + Changed = true; } } @@ -1173,10 +1156,11 @@ static void changeToCall(InvokeInst *II) { II->eraseFromParent(); } -static bool markAliveBlocks(BasicBlock *BB, +static bool markAliveBlocks(Function &F, SmallPtrSetImpl<BasicBlock*> &Reachable) { SmallVector<BasicBlock*, 128> Worklist; + BasicBlock *BB = F.begin(); Worklist.push_back(BB); Reachable.insert(BB); bool Changed = false; @@ -1247,7 +1231,7 @@ static bool markAliveBlocks(BasicBlock *BB, if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { changeToUnreachable(II, true); Changed = true; - } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(II)) { + } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. BranchInst::Create(II->getNormalDest(), II); @@ -1272,7 +1256,7 @@ static bool markAliveBlocks(BasicBlock *BB, /// otherwise. bool llvm::removeUnreachableBlocks(Function &F) { SmallPtrSet<BasicBlock*, 128> Reachable; - bool Changed = markAliveBlocks(F.begin(), Reachable); + bool Changed = markAliveBlocks(F, Reachable); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 90dfabaeb356..8b0afa69d974 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -144,8 +144,6 @@ BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", AA, DT, LI, PreserveLCSSA); - PreheaderBB->getTerminator()->setDebugLoc( - Header->getFirstNonPHI()->getDebugLoc()); DEBUG(dbgs() << "LoopSimplify: Creating pre-header " << PreheaderBB->getName() << "\n"); @@ -778,7 +776,7 @@ namespace { /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. void verifyAnalysis() const override; }; -} +} // namespace char LoopSimplify::ID = 0; INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", diff --git a/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/lib/Transforms/Utils/LoopUnrollRuntime.cpp index d1774dfa10d9..919b45d3c7b1 100644 --- a/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ b/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -113,6 +113,7 @@ static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, // Create a branch around the orignal loop, which is taken if there are no // iterations remaining to be executed after running the prologue. Instruction *InsertPt = PrologEnd->getTerminator(); + IRBuilder<> B(InsertPt); assert(Count != 0 && "nonsensical Count!"); @@ -120,9 +121,8 @@ static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, // (since Count is a power of 2). This means %xtraiter is (BECount + 1) and // and all of the iterations of this loop were executed by the prologue. Note // that if BECount <u (Count - 1) then (BECount + 1) cannot unsigned-overflow. - Instruction *BrLoopExit = - new ICmpInst(InsertPt, ICmpInst::ICMP_ULT, BECount, - ConstantInt::get(BECount->getType(), Count - 1)); + Value *BrLoopExit = + B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1)); BasicBlock *Exit = L->getUniqueExitBlock(); assert(Exit && "Loop must have a single exit block only"); // Split the exit to maintain loop canonicalization guarantees @@ -130,7 +130,7 @@ static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", AA, DT, LI, P->mustPreserveAnalysisID(LCSSAID)); // Add the branch to the exit block (around the unrolled loop) - BranchInst::Create(Exit, NewPH, BrLoopExit, InsertPt); + B.CreateCondBr(BrLoopExit, Exit, NewPH); InsertPt->eraseFromParent(); } @@ -184,23 +184,22 @@ static void CloneLoopBlocks(Loop *L, Value *NewIter, const bool UnrollProlog, VMap.erase((*BB)->getTerminator()); BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]); BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator()); + IRBuilder<> Builder(LatchBR); if (UnrollProlog) { - LatchBR->eraseFromParent(); - BranchInst::Create(InsertBot, NewBB); + Builder.CreateBr(InsertBot); } else { PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2, "prol.iter", FirstLoopBB->getFirstNonPHI()); - IRBuilder<> Builder(LatchBR); Value *IdxSub = Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1), NewIdx->getName() + ".sub"); Value *IdxCmp = Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp"); - BranchInst::Create(FirstLoopBB, InsertBot, IdxCmp, NewBB); + Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot); NewIdx->addIncoming(NewIter, InsertTop); NewIdx->addIncoming(IdxSub, NewBB); - LatchBR->eraseFromParent(); } + LatchBR->eraseFromParent(); } } @@ -370,7 +369,7 @@ bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, // Branch to either the extra iterations or the cloned/unrolled loop // We will fix up the true branch label when adding loop body copies - BranchInst::Create(PEnd, PEnd, BranchVal, PreHeaderBR); + B.CreateCondBr(BranchVal, PEnd, PEnd); assert(PreHeaderBR->isUnconditional() && PreHeaderBR->getSuccessor(0) == PEnd && "CFG edges in Preheader are not correct"); diff --git a/lib/Transforms/Utils/LoopUtils.cpp b/lib/Transforms/Utils/LoopUtils.cpp index 5f25e6b2cb6f..5cbde94a98ed 100644 --- a/lib/Transforms/Utils/LoopUtils.cpp +++ b/lib/Transforms/Utils/LoopUtils.cpp @@ -26,17 +26,17 @@ using namespace llvm::PatternMatch; #define DEBUG_TYPE "loop-utils" -bool ReductionDescriptor::areAllUsesIn(Instruction *I, - SmallPtrSetImpl<Instruction *> &Set) { +bool RecurrenceDescriptor::areAllUsesIn(Instruction *I, + SmallPtrSetImpl<Instruction *> &Set) { for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) if (!Set.count(dyn_cast<Instruction>(*Use))) return false; return true; } -bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, - Loop *TheLoop, bool HasFunNoNaNAttr, - ReductionDescriptor &RedDes) { +bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind, + Loop *TheLoop, bool HasFunNoNaNAttr, + RecurrenceDescriptor &RedDes) { if (Phi->getNumIncomingValues() != 2) return false; @@ -66,7 +66,7 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, // the number of instruction we saw from the recognized min/max pattern, // to make sure we only see exactly the two instructions. unsigned NumCmpSelectPatternInst = 0; - ReductionInstDesc ReduxDesc(false, nullptr); + InstDesc ReduxDesc(false, nullptr); SmallPtrSet<Instruction *, 8> VisitedInsts; SmallVector<Instruction *, 8> Worklist; @@ -111,8 +111,8 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, return false; // Any reduction instruction must be of one of the allowed kinds. - ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); - if (!ReduxDesc.isReduction()) + ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); + if (!ReduxDesc.isRecurrence()) return false; // A reduction operation must only have one use of the reduction value. @@ -164,7 +164,7 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, // Process instructions only once (termination). Each reduction cycle // value must only be used once, except by phi nodes and min/max // reductions which are represented as a cmp followed by a select. - ReductionInstDesc IgnoredVal(false, nullptr); + InstDesc IgnoredVal(false, nullptr); if (VisitedInsts.insert(UI).second) { if (isa<PHINode>(UI)) PHIs.push_back(UI); @@ -173,7 +173,7 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, } else if (!isa<PHINode>(UI) && ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) && !isa<SelectInst>(UI)) || - !isMinMaxSelectCmpPattern(UI, IgnoredVal).isReduction())) + !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence())) return false; // Remember that we completed the cycle. @@ -197,11 +197,11 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, // only have a single instruction with out-of-loop users. // The ExitInstruction(Instruction which is allowed to have out-of-loop users) - // is saved as part of the ReductionDescriptor. + // is saved as part of the RecurrenceDescriptor. // Save the description of this reduction variable. - ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, - ReduxDesc.getMinMaxKind()); + RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, + ReduxDesc.getMinMaxKind()); RedDes = RD; @@ -210,9 +210,8 @@ bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction /// pattern corresponding to a min(X, Y) or max(X, Y). -ReductionInstDesc -ReductionDescriptor::isMinMaxSelectCmpPattern(Instruction *I, - ReductionInstDesc &Prev) { +RecurrenceDescriptor::InstDesc +RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) { assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) && "Expect a select instruction"); @@ -223,84 +222,83 @@ ReductionDescriptor::isMinMaxSelectCmpPattern(Instruction *I, // select. if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) { if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin()))) - return ReductionInstDesc(false, I); - return ReductionInstDesc(Select, Prev.getMinMaxKind()); + return InstDesc(false, I); + return InstDesc(Select, Prev.getMinMaxKind()); } // Only handle single use cases for now. if (!(Select = dyn_cast<SelectInst>(I))) - return ReductionInstDesc(false, I); + return InstDesc(false, I); if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) && !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0)))) - return ReductionInstDesc(false, I); + return InstDesc(false, I); if (!Cmp->hasOneUse()) - return ReductionInstDesc(false, I); + return InstDesc(false, I); Value *CmpLeft; Value *CmpRight; // Look for a min/max pattern. if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMin); + return InstDesc(Select, MRK_UIntMin); else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMax); + return InstDesc(Select, MRK_UIntMax); else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMax); + return InstDesc(Select, MRK_SIntMax); else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMin); + return InstDesc(Select, MRK_SIntMin); else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); + return InstDesc(Select, MRK_FloatMin); else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); + return InstDesc(Select, MRK_FloatMax); else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); + return InstDesc(Select, MRK_FloatMin); else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); + return InstDesc(Select, MRK_FloatMax); - return ReductionInstDesc(false, I); + return InstDesc(false, I); } -ReductionInstDesc ReductionDescriptor::isReductionInstr(Instruction *I, - ReductionKind Kind, - ReductionInstDesc &Prev, - bool HasFunNoNaNAttr) { +RecurrenceDescriptor::InstDesc +RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, + InstDesc &Prev, bool HasFunNoNaNAttr) { bool FP = I->getType()->isFloatingPointTy(); bool FastMath = FP && I->hasUnsafeAlgebra(); switch (I->getOpcode()) { default: - return ReductionInstDesc(false, I); + return InstDesc(false, I); case Instruction::PHI: if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax)) - return ReductionInstDesc(false, I); - return ReductionInstDesc(I, Prev.getMinMaxKind()); + return InstDesc(false, I); + return InstDesc(I, Prev.getMinMaxKind()); case Instruction::Sub: case Instruction::Add: - return ReductionInstDesc(Kind == RK_IntegerAdd, I); + return InstDesc(Kind == RK_IntegerAdd, I); case Instruction::Mul: - return ReductionInstDesc(Kind == RK_IntegerMult, I); + return InstDesc(Kind == RK_IntegerMult, I); case Instruction::And: - return ReductionInstDesc(Kind == RK_IntegerAnd, I); + return InstDesc(Kind == RK_IntegerAnd, I); case Instruction::Or: - return ReductionInstDesc(Kind == RK_IntegerOr, I); + return InstDesc(Kind == RK_IntegerOr, I); case Instruction::Xor: - return ReductionInstDesc(Kind == RK_IntegerXor, I); + return InstDesc(Kind == RK_IntegerXor, I); case Instruction::FMul: - return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I); + return InstDesc(Kind == RK_FloatMult && FastMath, I); case Instruction::FSub: case Instruction::FAdd: - return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I); + return InstDesc(Kind == RK_FloatAdd && FastMath, I); case Instruction::FCmp: case Instruction::ICmp: case Instruction::Select: if (Kind != RK_IntegerMinMax && (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) - return ReductionInstDesc(false, I); + return InstDesc(false, I); return isMinMaxSelectCmpPattern(I, Prev); } } -bool ReductionDescriptor::hasMultipleUsesOf( +bool RecurrenceDescriptor::hasMultipleUsesOf( Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) { unsigned NumUses = 0; for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; @@ -313,8 +311,8 @@ bool ReductionDescriptor::hasMultipleUsesOf( return false; } -bool ReductionDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, - ReductionDescriptor &RedDes) { +bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, + RecurrenceDescriptor &RedDes) { bool HasFunNoNaNAttr = false; BasicBlock *Header = TheLoop->getHeader(); @@ -366,7 +364,8 @@ bool ReductionDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, /// This function returns the identity element (or neutral element) for /// the operation K. -Constant *ReductionDescriptor::getReductionIdentity(ReductionKind K, Type *Tp) { +Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K, + Type *Tp) { switch (K) { case RK_IntegerXor: case RK_IntegerAdd: @@ -386,12 +385,12 @@ Constant *ReductionDescriptor::getReductionIdentity(ReductionKind K, Type *Tp) { // Adding zero to a number does not change it. return ConstantFP::get(Tp, 0.0L); default: - llvm_unreachable("Unknown reduction kind"); + llvm_unreachable("Unknown recurrence kind"); } } -/// This function translates the reduction kind to an LLVM binary operator. -unsigned ReductionDescriptor::getReductionBinOp(ReductionKind Kind) { +/// This function translates the recurrence kind to an LLVM binary operator. +unsigned RecurrenceDescriptor::getRecurrenceBinOp(RecurrenceKind Kind) { switch (Kind) { case RK_IntegerAdd: return Instruction::Add; @@ -412,41 +411,39 @@ unsigned ReductionDescriptor::getReductionBinOp(ReductionKind Kind) { case RK_FloatMinMax: return Instruction::FCmp; default: - llvm_unreachable("Unknown reduction operation"); + llvm_unreachable("Unknown recurrence operation"); } } -Value * -ReductionDescriptor::createMinMaxOp(IRBuilder<> &Builder, - ReductionInstDesc::MinMaxReductionKind RK, - Value *Left, Value *Right) { +Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder, + MinMaxRecurrenceKind RK, + Value *Left, Value *Right) { CmpInst::Predicate P = CmpInst::ICMP_NE; switch (RK) { default: - llvm_unreachable("Unknown min/max reduction kind"); - case ReductionInstDesc::MRK_UIntMin: + llvm_unreachable("Unknown min/max recurrence kind"); + case MRK_UIntMin: P = CmpInst::ICMP_ULT; break; - case ReductionInstDesc::MRK_UIntMax: + case MRK_UIntMax: P = CmpInst::ICMP_UGT; break; - case ReductionInstDesc::MRK_SIntMin: + case MRK_SIntMin: P = CmpInst::ICMP_SLT; break; - case ReductionInstDesc::MRK_SIntMax: + case MRK_SIntMax: P = CmpInst::ICMP_SGT; break; - case ReductionInstDesc::MRK_FloatMin: + case MRK_FloatMin: P = CmpInst::FCMP_OLT; break; - case ReductionInstDesc::MRK_FloatMax: + case MRK_FloatMax: P = CmpInst::FCMP_OGT; break; } Value *Cmp; - if (RK == ReductionInstDesc::MRK_FloatMin || - RK == ReductionInstDesc::MRK_FloatMax) + if (RK == MRK_FloatMin || RK == MRK_FloatMax) Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); else Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp index e0e0e9009495..c1b0645c7cbc 100644 --- a/lib/Transforms/Utils/LowerSwitch.cpp +++ b/lib/Transforms/Utils/LowerSwitch.cpp @@ -101,7 +101,7 @@ namespace { return CI1->getValue().slt(CI2->getValue()); } }; -} +} // namespace char LowerSwitch::ID = 0; INITIALIZE_PASS(LowerSwitch, "lowerswitch", @@ -364,9 +364,9 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { std::sort(Cases.begin(), Cases.end(), CaseCmp()); // Merge case into clusters - if (Cases.size()>=2) - for (CaseItr I = Cases.begin(), J = std::next(Cases.begin()); - J != Cases.end();) { + if (Cases.size() >= 2) { + CaseItr I = Cases.begin(); + for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) { int64_t nextValue = J->Low->getSExtValue(); int64_t currentValue = I->High->getSExtValue(); BasicBlock* nextBB = J->BB; @@ -374,13 +374,16 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { // If the two neighboring cases go to the same destination, merge them // into a single case. - if ((nextValue-currentValue==1) && (currentBB == nextBB)) { + assert(nextValue > currentValue && "Cases should be strictly ascending"); + if ((nextValue == currentValue + 1) && (currentBB == nextBB)) { I->High = J->High; - J = Cases.erase(J); - } else { - I = J++; + // FIXME: Combine branch weights. + } else if (++I != J) { + *I = *J; } } + Cases.erase(std::next(I), Cases.end()); + } for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { if (I->Low != I->High) @@ -476,12 +479,10 @@ void LowerSwitch::processSwitchInst(SwitchInst *SI) { // cases. assert(MaxPop > 0 && PopSucc); Default = PopSucc; - for (CaseItr I = Cases.begin(); I != Cases.end();) { - if (I->BB == PopSucc) - I = Cases.erase(I); - else - ++I; - } + Cases.erase(std::remove_if( + Cases.begin(), Cases.end(), + [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }), + Cases.end()); // If there are no cases left, just branch. if (Cases.empty()) { diff --git a/lib/Transforms/Utils/MetaRenamer.cpp b/lib/Transforms/Utils/MetaRenamer.cpp index 395a46bad97b..46dd65e9def6 100644 --- a/lib/Transforms/Utils/MetaRenamer.cpp +++ b/lib/Transforms/Utils/MetaRenamer.cpp @@ -131,7 +131,7 @@ namespace { return true; } }; -} +} // namespace char MetaRenamer::ID = 0; INITIALIZE_PASS(MetaRenamer, "metarenamer", diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index 88b39dd7f664..c09889875805 100644 --- a/lib/Transforms/Utils/SSAUpdater.cpp +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -303,7 +303,7 @@ public: } }; -} // End llvm namespace +} // namespace llvm /// Check to see if AvailableVals has an entry for the specified BB and if so, /// return it. If not, construct SSA form by first calculating the required diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 60ac271bceb7..3d7ab0fd65a9 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -136,7 +136,7 @@ public: : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {} bool run(BasicBlock *BB); }; -} +} // namespace /// SafeToMergeTerminators - Return true if it is safe to merge these two /// terminator instructions together. @@ -502,7 +502,7 @@ private: } }; -} +} // namespace static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { Instruction *Cond = nullptr; @@ -3717,7 +3717,7 @@ namespace { // For ArrayKind, this is the array. GlobalVariable *Array; }; -} +} // namespace SwitchLookupTable::SwitchLookupTable( Module &M, uint64_t TableSize, ConstantInt *Offset, @@ -4058,7 +4058,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, return false; // Figure out the corresponding result for each case value and phi node in the - // common destination, as well as the the min and max case values. + // common destination, as well as the min and max case values. assert(SI->case_begin() != SI->case_end()); SwitchInst::CaseIt CI = SI->case_begin(); ConstantInt *MinCaseVal = CI.getCaseValue(); diff --git a/lib/Transforms/Utils/SimplifyIndVar.cpp b/lib/Transforms/Utils/SimplifyIndVar.cpp index ab30aa17c76b..68986ac0894f 100644 --- a/lib/Transforms/Utils/SimplifyIndVar.cpp +++ b/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -77,7 +77,7 @@ namespace { Instruction *splitOverflowIntrinsic(Instruction *IVUser, const DominatorTree *DT); }; -} +} // namespace /// Fold an IV operand into its use. This removes increments of an /// aligned IV when used by a instruction that ignores the low bits. diff --git a/lib/Transforms/Utils/SimplifyInstructions.cpp b/lib/Transforms/Utils/SimplifyInstructions.cpp index c499c87b1f0b..0a583a5af27a 100644 --- a/lib/Transforms/Utils/SimplifyInstructions.cpp +++ b/lib/Transforms/Utils/SimplifyInstructions.cpp @@ -100,7 +100,7 @@ namespace { return Changed; } }; -} +} // namespace char InstSimplifier::ID = 0; INITIALIZE_PASS_BEGIN(InstSimplifier, "instsimplify", diff --git a/lib/Transforms/Utils/SymbolRewriter.cpp b/lib/Transforms/Utils/SymbolRewriter.cpp index a2a54da8590c..4cc278fe7278 100644 --- a/lib/Transforms/Utils/SymbolRewriter.cpp +++ b/lib/Transforms/Utils/SymbolRewriter.cpp @@ -538,7 +538,7 @@ void RewriteSymbols::loadAndParseMapFiles() { for (const auto &MapFile : MapFiles) parser.parse(MapFile, &Descriptors); } -} +} // namespace INITIALIZE_PASS(RewriteSymbols, "rewrite-symbols", "Rewrite Symbols", false, false) |