diff options
Diffstat (limited to 'lib/Transforms/InstCombine/InstructionCombining.cpp')
| -rw-r--r-- | lib/Transforms/InstCombine/InstructionCombining.cpp | 572 |
1 files changed, 304 insertions, 268 deletions
diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index e4a4fef..88fcd53 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -33,18 +33,20 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" -#include "InstCombine.h" +#include "llvm/Transforms/InstCombine/InstCombine.h" +#include "InstCombineInternal.h" #include "llvm-c/Initialization.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringSwitch.h" -#include "llvm/Analysis/AssumptionTracker.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LibCallSemantics.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" #include "llvm/IR/DataLayout.h" @@ -55,7 +57,7 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/Target/TargetLibraryInfo.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" #include <algorithm> #include <climits> @@ -72,30 +74,6 @@ STATISTIC(NumExpand, "Number of expansions"); STATISTIC(NumFactor , "Number of factorizations"); STATISTIC(NumReassoc , "Number of reassociations"); -// Initialization Routines -void llvm::initializeInstCombine(PassRegistry &Registry) { - initializeInstCombinerPass(Registry); -} - -void LLVMInitializeInstCombine(LLVMPassRegistryRef R) { - initializeInstCombine(*unwrap(R)); -} - -char InstCombiner::ID = 0; -INITIALIZE_PASS_BEGIN(InstCombiner, "instcombine", - "Combine redundant instructions", false, false) -INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) -INITIALIZE_PASS_END(InstCombiner, "instcombine", - "Combine redundant instructions", false, false) - -void InstCombiner::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired<AssumptionTracker>(); - AU.addRequired<TargetLibraryInfo>(); -} - - Value *InstCombiner::EmitGEPOffset(User *GEP) { return llvm::EmitGEPOffset(Builder, *getDataLayout(), GEP); } @@ -796,8 +774,7 @@ Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) { // If the incoming non-constant value is in I's block, we will remove one // instruction, but insert another equivalent one, leading to infinite // instcombine. - if (isPotentiallyReachable(I.getParent(), NonConstBB, DT, - getAnalysisIfAvailable<LoopInfo>())) + if (isPotentiallyReachable(I.getParent(), NonConstBB, DT, LI)) return nullptr; } @@ -1316,7 +1293,7 @@ Value *InstCombiner::SimplifyVectorOp(BinaryOperator &Inst) { Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end()); - if (Value *V = SimplifyGEPInst(Ops, DL, TLI, DT, AT)) + if (Value *V = SimplifyGEPInst(Ops, DL, TLI, DT, AC)) return ReplaceInstUsesWith(GEP, V); Value *PtrOp = GEP.getOperand(0); @@ -1414,8 +1391,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (DI == -1) { // All the GEPs feeding the PHI are identical. Clone one down into our // BB so that it can be merged with the current GEP. - GEP.getParent()->getInstList().insert(GEP.getParent()->getFirstNonPHI(), - NewGEP); + GEP.getParent()->getInstList().insert( + GEP.getParent()->getFirstInsertionPt(), NewGEP); } else { // All the GEPs feeding the PHI differ at a single offset. Clone a GEP // into the current block so it can be merged, and create a new PHI to @@ -1431,8 +1408,8 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) { PN->getIncomingBlock(I)); NewGEP->setOperand(DI, NewPN); - GEP.getParent()->getInstList().insert(GEP.getParent()->getFirstNonPHI(), - NewGEP); + GEP.getParent()->getInstList().insert( + GEP.getParent()->getFirstInsertionPt(), NewGEP); NewGEP->setOperand(DI, NewPN); } @@ -2092,7 +2069,10 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { // the largest legal integer type. We need to be conservative here since // x86 generates redundant zero-extenstion instructions if the operand is // truncated to i8 or i16. - if (BitWidth > NewWidth && NewWidth >= DL->getLargestLegalIntTypeSize()) { + bool TruncCond = false; + if (DL && BitWidth > NewWidth && + NewWidth >= DL->getLargestLegalIntTypeSize()) { + TruncCond = true; IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth); Builder->SetInsertPoint(&SI); Value *NewCond = Builder->CreateTrunc(SI.getCondition(), Ty, "trunc"); @@ -2111,8 +2091,12 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) { ConstantInt* CaseVal = i.getCaseValue(); - Constant* NewCaseVal = ConstantExpr::getSub(cast<Constant>(CaseVal), - AddRHS); + Constant *LHS = CaseVal; + if (TruncCond) + LHS = LeadingKnownZeros + ? ConstantExpr::getZExt(CaseVal, Cond->getType()) + : ConstantExpr::getSExt(CaseVal, Cond->getType()); + Constant* NewCaseVal = ConstantExpr::getSub(LHS, AddRHS); assert(isa<ConstantInt>(NewCaseVal) && "Result of expression should be constant"); i.setValue(cast<ConstantInt>(NewCaseVal)); @@ -2122,7 +2106,8 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { return &SI; } } - return nullptr; + + return TruncCond ? &SI : nullptr; } Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { @@ -2275,41 +2260,27 @@ Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) { return nullptr; } -enum Personality_Type { - Unknown_Personality, - GNU_Ada_Personality, - GNU_CXX_Personality, - GNU_ObjC_Personality -}; - -/// RecognizePersonality - See if the given exception handling personality -/// function is one that we understand. If so, return a description of it; -/// otherwise return Unknown_Personality. -static Personality_Type RecognizePersonality(Value *Pers) { - Function *F = dyn_cast<Function>(Pers->stripPointerCasts()); - if (!F) - return Unknown_Personality; - return StringSwitch<Personality_Type>(F->getName()) - .Case("__gnat_eh_personality", GNU_Ada_Personality) - .Case("__gxx_personality_v0", GNU_CXX_Personality) - .Case("__objc_personality_v0", GNU_ObjC_Personality) - .Default(Unknown_Personality); -} - /// isCatchAll - Return 'true' if the given typeinfo will match anything. -static bool isCatchAll(Personality_Type Personality, Constant *TypeInfo) { +static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) { switch (Personality) { - case Unknown_Personality: + case EHPersonality::GNU_C: + // The GCC C EH personality only exists to support cleanups, so it's not + // clear what the semantics of catch clauses are. return false; - case GNU_Ada_Personality: + case EHPersonality::Unknown: + return false; + case EHPersonality::GNU_Ada: // While __gnat_all_others_value will match any Ada exception, it doesn't // match foreign exceptions (or didn't, before gcc-4.7). return false; - case GNU_CXX_Personality: - case GNU_ObjC_Personality: + case EHPersonality::GNU_CXX: + case EHPersonality::GNU_ObjC: + case EHPersonality::MSVC_X86SEH: + case EHPersonality::MSVC_Win64SEH: + case EHPersonality::MSVC_CXX: return TypeInfo->isNullValue(); } - llvm_unreachable("Unknown personality!"); + llvm_unreachable("invalid enum"); } static bool shorter_filter(const Value *LHS, const Value *RHS) { @@ -2323,7 +2294,7 @@ Instruction *InstCombiner::visitLandingPadInst(LandingPadInst &LI) { // The logic here should be correct for any real-world personality function. // However if that turns out not to be true, the offending logic can always // be conditioned on the personality function, like the catch-all logic is. - Personality_Type Personality = RecognizePersonality(LI.getPersonalityFn()); + EHPersonality Personality = classifyEHPersonality(LI.getPersonalityFn()); // Simplify the list of clauses, eg by removing repeated catch clauses // (these are often created by inlining). @@ -2614,9 +2585,6 @@ Instruction *InstCombiner::visitLandingPadInst(LandingPadInst &LI) { return nullptr; } - - - /// TryToSinkInstruction - Try to move the specified instruction from its /// current block into the beginning of DestBlock, which can only happen if it's /// safe to move the instruction past all of the instructions between it and the @@ -2649,6 +2617,135 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { return true; } +bool InstCombiner::run() { + while (!Worklist.isEmpty()) { + Instruction *I = Worklist.RemoveOne(); + if (I == nullptr) continue; // skip null values. + + // Check to see if we can DCE the instruction. + if (isInstructionTriviallyDead(I, TLI)) { + DEBUG(dbgs() << "IC: DCE: " << *I << '\n'); + EraseInstFromFunction(*I); + ++NumDeadInst; + MadeIRChange = true; + continue; + } + + // Instruction isn't dead, see if we can constant propagate it. + if (!I->use_empty() && isa<Constant>(I->getOperand(0))) + if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) { + DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I << '\n'); + + // Add operands to the worklist. + ReplaceInstUsesWith(*I, C); + ++NumConstProp; + EraseInstFromFunction(*I); + MadeIRChange = true; + continue; + } + + // See if we can trivially sink this instruction to a successor basic block. + if (I->hasOneUse()) { + BasicBlock *BB = I->getParent(); + Instruction *UserInst = cast<Instruction>(*I->user_begin()); + BasicBlock *UserParent; + + // Get the block the use occurs in. + if (PHINode *PN = dyn_cast<PHINode>(UserInst)) + UserParent = PN->getIncomingBlock(*I->use_begin()); + else + UserParent = UserInst->getParent(); + + if (UserParent != BB) { + bool UserIsSuccessor = false; + // See if the user is one of our successors. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) + if (*SI == UserParent) { + UserIsSuccessor = true; + break; + } + + // If the user is one of our immediate successors, and if that successor + // only has us as a predecessors (we'd have to split the critical edge + // otherwise), we can keep going. + if (UserIsSuccessor && UserParent->getSinglePredecessor()) { + // Okay, the CFG is simple enough, try to sink this instruction. + if (TryToSinkInstruction(I, UserParent)) { + MadeIRChange = true; + // We'll add uses of the sunk instruction below, but since sinking + // can expose opportunities for it's *operands* add them to the + // worklist + for (Use &U : I->operands()) + if (Instruction *OpI = dyn_cast<Instruction>(U.get())) + Worklist.Add(OpI); + } + } + } + } + + // Now that we have an instruction, try combining it to simplify it. + Builder->SetInsertPoint(I->getParent(), I); + Builder->SetCurrentDebugLocation(I->getDebugLoc()); + +#ifndef NDEBUG + std::string OrigI; +#endif + DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str();); + DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n'); + + if (Instruction *Result = visit(*I)) { + ++NumCombined; + // Should we replace the old instruction with a new one? + if (Result != I) { + DEBUG(dbgs() << "IC: Old = " << *I << '\n' + << " New = " << *Result << '\n'); + + if (!I->getDebugLoc().isUnknown()) + Result->setDebugLoc(I->getDebugLoc()); + // Everything uses the new instruction now. + I->replaceAllUsesWith(Result); + + // Move the name to the new instruction first. + Result->takeName(I); + + // Push the new instruction and any users onto the worklist. + Worklist.Add(Result); + Worklist.AddUsersToWorkList(*Result); + + // Insert the new instruction into the basic block... + BasicBlock *InstParent = I->getParent(); + BasicBlock::iterator InsertPos = I; + + // If we replace a PHI with something that isn't a PHI, fix up the + // insertion point. + if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos)) + InsertPos = InstParent->getFirstInsertionPt(); + + InstParent->getInstList().insert(InsertPos, Result); + + EraseInstFromFunction(*I); + } else { +#ifndef NDEBUG + DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n' + << " New = " << *I << '\n'); +#endif + + // If the instruction was modified, it's possible that it is now dead. + // if so, remove it. + if (isInstructionTriviallyDead(I, TLI)) { + EraseInstFromFunction(*I); + } else { + Worklist.Add(I); + Worklist.AddUsersToWorkList(*I); + } + } + MadeIRChange = true; + } + } + + Worklist.Zap(); + return MadeIRChange; +} /// AddReachableCodeToWorklist - Walk the function in depth-first order, adding /// all reachable code to the worklist. @@ -2661,7 +2758,7 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { /// static bool AddReachableCodeToWorklist(BasicBlock *BB, SmallPtrSetImpl<BasicBlock*> &Visited, - InstCombiner &IC, + InstCombineWorklist &ICWorklist, const DataLayout *DL, const TargetLibraryInfo *TLI) { bool MadeIRChange = false; @@ -2759,244 +2856,183 @@ static bool AddReachableCodeToWorklist(BasicBlock *BB, // of the function down. This jives well with the way that it adds all uses // of instructions to the worklist after doing a transformation, thus avoiding // some N^2 behavior in pathological cases. - IC.Worklist.AddInitialGroup(&InstrsForInstCombineWorklist[0], - InstrsForInstCombineWorklist.size()); + ICWorklist.AddInitialGroup(&InstrsForInstCombineWorklist[0], + InstrsForInstCombineWorklist.size()); return MadeIRChange; } -bool InstCombiner::DoOneIteration(Function &F, unsigned Iteration) { - MadeIRChange = false; - - DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " - << F.getName() << "\n"); - - { - // Do a depth-first traversal of the function, populate the worklist with - // the reachable instructions. Ignore blocks that are not reachable. Keep - // track of which blocks we visit. - SmallPtrSet<BasicBlock*, 64> Visited; - MadeIRChange |= AddReachableCodeToWorklist(F.begin(), Visited, *this, DL, - TLI); - - // Do a quick scan over the function. If we find any blocks that are - // unreachable, remove any instructions inside of them. This prevents - // the instcombine code from having to deal with some bad special cases. - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { - if (Visited.count(BB)) continue; - - // Delete the instructions backwards, as it has a reduced likelihood of - // having to update as many def-use and use-def chains. - Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. - while (EndInst != BB->begin()) { - // Delete the next to last instruction. - BasicBlock::iterator I = EndInst; - Instruction *Inst = --I; - if (!Inst->use_empty()) - Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); - if (isa<LandingPadInst>(Inst)) { - EndInst = Inst; - continue; - } - if (!isa<DbgInfoIntrinsic>(Inst)) { - ++NumDeadInst; - MadeIRChange = true; - } - Inst->eraseFromParent(); - } - } - } - - while (!Worklist.isEmpty()) { - Instruction *I = Worklist.RemoveOne(); - if (I == nullptr) continue; // skip null values. +/// \brief Populate the IC worklist from a function, and prune any dead basic +/// blocks discovered in the process. +/// +/// This also does basic constant propagation and other forward fixing to make +/// the combiner itself run much faster. +static bool prepareICWorklistFromFunction(Function &F, const DataLayout *DL, + TargetLibraryInfo *TLI, + InstCombineWorklist &ICWorklist) { + bool MadeIRChange = false; - // Check to see if we can DCE the instruction. - if (isInstructionTriviallyDead(I, TLI)) { - DEBUG(dbgs() << "IC: DCE: " << *I << '\n'); - EraseInstFromFunction(*I); - ++NumDeadInst; - MadeIRChange = true; + // Do a depth-first traversal of the function, populate the worklist with + // the reachable instructions. Ignore blocks that are not reachable. Keep + // track of which blocks we visit. + SmallPtrSet<BasicBlock *, 64> Visited; + MadeIRChange |= + AddReachableCodeToWorklist(F.begin(), Visited, ICWorklist, DL, TLI); + + // Do a quick scan over the function. If we find any blocks that are + // unreachable, remove any instructions inside of them. This prevents + // the instcombine code from having to deal with some bad special cases. + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { + if (Visited.count(BB)) continue; - } - // Instruction isn't dead, see if we can constant propagate it. - if (!I->use_empty() && isa<Constant>(I->getOperand(0))) - if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) { - DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I << '\n'); - - // Add operands to the worklist. - ReplaceInstUsesWith(*I, C); - ++NumConstProp; - EraseInstFromFunction(*I); - MadeIRChange = true; + // Delete the instructions backwards, as it has a reduced likelihood of + // having to update as many def-use and use-def chains. + Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. + while (EndInst != BB->begin()) { + // Delete the next to last instruction. + BasicBlock::iterator I = EndInst; + Instruction *Inst = --I; + if (!Inst->use_empty()) + Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); + if (isa<LandingPadInst>(Inst)) { + EndInst = Inst; continue; } - - // See if we can trivially sink this instruction to a successor basic block. - if (I->hasOneUse()) { - BasicBlock *BB = I->getParent(); - Instruction *UserInst = cast<Instruction>(*I->user_begin()); - BasicBlock *UserParent; - - // Get the block the use occurs in. - if (PHINode *PN = dyn_cast<PHINode>(UserInst)) - UserParent = PN->getIncomingBlock(*I->use_begin()); - else - UserParent = UserInst->getParent(); - - if (UserParent != BB) { - bool UserIsSuccessor = false; - // See if the user is one of our successors. - for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) - if (*SI == UserParent) { - UserIsSuccessor = true; - break; - } - - // If the user is one of our immediate successors, and if that successor - // only has us as a predecessors (we'd have to split the critical edge - // otherwise), we can keep going. - if (UserIsSuccessor && UserParent->getSinglePredecessor()) { - // Okay, the CFG is simple enough, try to sink this instruction. - if (TryToSinkInstruction(I, UserParent)) { - MadeIRChange = true; - // We'll add uses of the sunk instruction below, but since sinking - // can expose opportunities for it's *operands* add them to the - // worklist - for (Use &U : I->operands()) - if (Instruction *OpI = dyn_cast<Instruction>(U.get())) - Worklist.Add(OpI); - } - } + if (!isa<DbgInfoIntrinsic>(Inst)) { + ++NumDeadInst; + MadeIRChange = true; } + Inst->eraseFromParent(); } + } - // Now that we have an instruction, try combining it to simplify it. - Builder->SetInsertPoint(I->getParent(), I); - Builder->SetCurrentDebugLocation(I->getDebugLoc()); + return MadeIRChange; +} -#ifndef NDEBUG - std::string OrigI; -#endif - DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str();); - DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n'); +static bool combineInstructionsOverFunction( + Function &F, InstCombineWorklist &Worklist, AssumptionCache &AC, + TargetLibraryInfo &TLI, DominatorTree &DT, const DataLayout *DL = nullptr, + LoopInfo *LI = nullptr) { + // Minimizing size? + bool MinimizeSize = F.hasFnAttribute(Attribute::MinSize); - if (Instruction *Result = visit(*I)) { - ++NumCombined; - // Should we replace the old instruction with a new one? - if (Result != I) { - DEBUG(dbgs() << "IC: Old = " << *I << '\n' - << " New = " << *Result << '\n'); + /// Builder - This is an IRBuilder that automatically inserts new + /// instructions into the worklist when they are created. + IRBuilder<true, TargetFolder, InstCombineIRInserter> Builder( + F.getContext(), TargetFolder(DL), InstCombineIRInserter(Worklist, &AC)); - if (!I->getDebugLoc().isUnknown()) - Result->setDebugLoc(I->getDebugLoc()); - // Everything uses the new instruction now. - I->replaceAllUsesWith(Result); + // Lower dbg.declare intrinsics otherwise their value may be clobbered + // by instcombiner. + bool DbgDeclaresChanged = LowerDbgDeclare(F); - // Move the name to the new instruction first. - Result->takeName(I); + // Iterate while there is work to do. + int Iteration = 0; + for (;;) { + ++Iteration; + DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " + << F.getName() << "\n"); - // Push the new instruction and any users onto the worklist. - Worklist.Add(Result); - Worklist.AddUsersToWorkList(*Result); + bool Changed = false; + if (prepareICWorklistFromFunction(F, DL, &TLI, Worklist)) + Changed = true; - // Insert the new instruction into the basic block... - BasicBlock *InstParent = I->getParent(); - BasicBlock::iterator InsertPos = I; + InstCombiner IC(Worklist, &Builder, MinimizeSize, &AC, &TLI, &DT, DL, LI); + if (IC.run()) + Changed = true; - // If we replace a PHI with something that isn't a PHI, fix up the - // insertion point. - if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos)) - InsertPos = InstParent->getFirstInsertionPt(); + if (!Changed) + break; + } - InstParent->getInstList().insert(InsertPos, Result); + return DbgDeclaresChanged || Iteration > 1; +} - EraseInstFromFunction(*I); - } else { -#ifndef NDEBUG - DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n' - << " New = " << *I << '\n'); -#endif +PreservedAnalyses InstCombinePass::run(Function &F, + AnalysisManager<Function> *AM) { + auto *DL = F.getParent()->getDataLayout(); - // If the instruction was modified, it's possible that it is now dead. - // if so, remove it. - if (isInstructionTriviallyDead(I, TLI)) { - EraseInstFromFunction(*I); - } else { - Worklist.Add(I); - Worklist.AddUsersToWorkList(*I); - } - } - MadeIRChange = true; - } - } + auto &AC = AM->getResult<AssumptionAnalysis>(F); + auto &DT = AM->getResult<DominatorTreeAnalysis>(F); + auto &TLI = AM->getResult<TargetLibraryAnalysis>(F); - Worklist.Zap(); - return MadeIRChange; + auto *LI = AM->getCachedResult<LoopAnalysis>(F); + + if (!combineInstructionsOverFunction(F, Worklist, AC, TLI, DT, DL, LI)) + // No changes, all analyses are preserved. + return PreservedAnalyses::all(); + + // Mark all the analyses that instcombine updates as preserved. + // FIXME: Need a way to preserve CFG analyses here! + PreservedAnalyses PA; + PA.preserve<DominatorTreeAnalysis>(); + return PA; } namespace { -class InstCombinerLibCallSimplifier final : public LibCallSimplifier { - InstCombiner *IC; +/// \brief The legacy pass manager's instcombine pass. +/// +/// This is a basic whole-function wrapper around the instcombine utility. It +/// will try to combine all instructions in the function. +class InstructionCombiningPass : public FunctionPass { + InstCombineWorklist Worklist; + public: - InstCombinerLibCallSimplifier(const DataLayout *DL, - const TargetLibraryInfo *TLI, - InstCombiner *IC) - : LibCallSimplifier(DL, TLI) { - this->IC = IC; - } + static char ID; // Pass identification, replacement for typeid - /// replaceAllUsesWith - override so that instruction replacement - /// can be defined in terms of the instruction combiner framework. - void replaceAllUsesWith(Instruction *I, Value *With) const override { - IC->ReplaceInstUsesWith(*I, With); + InstructionCombiningPass() : FunctionPass(ID) { + initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry()); } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; }; } -bool InstCombiner::runOnFunction(Function &F) { +void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired<AssumptionCacheTracker>(); + AU.addRequired<TargetLibraryInfoWrapperPass>(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addPreserved<DominatorTreeWrapperPass>(); +} + +bool InstructionCombiningPass::runOnFunction(Function &F) { if (skipOptnoneFunction(F)) return false; - AT = &getAnalysis<AssumptionTracker>(); - DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); - DL = DLP ? &DLP->getDataLayout() : nullptr; - TLI = &getAnalysis<TargetLibraryInfo>(); + // Required analyses. + auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); + auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); - DominatorTreeWrapperPass *DTWP = - getAnalysisIfAvailable<DominatorTreeWrapperPass>(); - DT = DTWP ? &DTWP->getDomTree() : nullptr; - - // Minimizing size? - MinimizeSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, - Attribute::MinSize); - - /// Builder - This is an IRBuilder that automatically inserts new - /// instructions into the worklist when they are created. - IRBuilder<true, TargetFolder, InstCombineIRInserter> - TheBuilder(F.getContext(), TargetFolder(DL), - InstCombineIRInserter(Worklist, AT)); - Builder = &TheBuilder; + // Optional analyses. + auto *DLP = getAnalysisIfAvailable<DataLayoutPass>(); + auto *DL = DLP ? &DLP->getDataLayout() : nullptr; + auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); + auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; - InstCombinerLibCallSimplifier TheSimplifier(DL, TLI, this); - Simplifier = &TheSimplifier; + return combineInstructionsOverFunction(F, Worklist, AC, TLI, DT, DL, LI); +} - bool EverMadeChange = false; +char InstructionCombiningPass::ID = 0; +INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine", + "Combine redundant instructions", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine", + "Combine redundant instructions", false, false) - // Lower dbg.declare intrinsics otherwise their value may be clobbered - // by instcombiner. - EverMadeChange = LowerDbgDeclare(F); - - // Iterate while there is work to do. - unsigned Iteration = 0; - while (DoOneIteration(F, Iteration++)) - EverMadeChange = true; +// Initialization Routines +void llvm::initializeInstCombine(PassRegistry &Registry) { + initializeInstructionCombiningPassPass(Registry); +} - Builder = nullptr; - return EverMadeChange; +void LLVMInitializeInstCombine(LLVMPassRegistryRef R) { + initializeInstructionCombiningPassPass(*unwrap(R)); } FunctionPass *llvm::createInstructionCombiningPass() { - return new InstCombiner(); + return new InstructionCombiningPass(); } |