diff options
Diffstat (limited to 'llvm/lib/Analysis')
69 files changed, 2210 insertions, 938 deletions
diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp index 55dd9a4cda083..1c7678a602d81 100644 --- a/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/llvm/lib/Analysis/AliasAnalysis.cpp @@ -44,6 +44,7 @@ #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/Casting.h" @@ -734,6 +735,15 @@ namespace { } // end anonymous namespace +ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) { + initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB) + : ImmutablePass(ID), CB(std::move(CB)) { + initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + char ExternalAAWrapperPass::ID = 0; INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis", @@ -836,6 +846,7 @@ void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addUsedIfAvailable<SCEVAAWrapperPass>(); AU.addUsedIfAvailable<CFLAndersAAWrapperPass>(); AU.addUsedIfAvailable<CFLSteensAAWrapperPass>(); + AU.addUsedIfAvailable<ExternalAAWrapperPass>(); } AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F, @@ -861,6 +872,9 @@ AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F, AAR.addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>()) AAR.addAAResult(WrapperPass->getResult()); + if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>()) + if (WrapperPass->CB) + WrapperPass->CB(P, F, AAR); return AAR; } @@ -904,4 +918,5 @@ void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) { AU.addUsedIfAvailable<GlobalsAAWrapperPass>(); AU.addUsedIfAvailable<CFLAndersAAWrapperPass>(); AU.addUsedIfAvailable<CFLSteensAAWrapperPass>(); + AU.addUsedIfAvailable<ExternalAAWrapperPass>(); } diff --git a/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp b/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp index e83703867e09a..2e44bbd3a8ca5 100644 --- a/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp +++ b/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp @@ -16,6 +16,7 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/AliasSetTracker.cpp b/llvm/lib/Analysis/AliasSetTracker.cpp index 79fbcd464c1b5..5cc5ab597ef90 100644 --- a/llvm/lib/Analysis/AliasSetTracker.cpp +++ b/llvm/lib/Analysis/AliasSetTracker.cpp @@ -27,6 +27,7 @@ #include "llvm/IR/Module.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/Casting.h" diff --git a/llvm/lib/Analysis/AssumptionCache.cpp b/llvm/lib/Analysis/AssumptionCache.cpp index 129944743c5ef..f4d4a5ac8f88c 100644 --- a/llvm/lib/Analysis/AssumptionCache.cpp +++ b/llvm/lib/Analysis/AssumptionCache.cpp @@ -23,6 +23,7 @@ #include "llvm/IR/Intrinsics.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index f3c30c258c19e..e852d663c6b4b 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -25,9 +25,9 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Analysis/PhiValues.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/Constant.h" @@ -49,6 +49,7 @@ #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -1481,7 +1482,8 @@ AliasResult BasicAAResult::aliasGEP( // give up if we can't determine conditions that hold for every cycle: const Value *V = DecompGEP1.VarIndices[i].V; - KnownBits Known = computeKnownBits(V, DL, 0, &AC, nullptr, DT); + KnownBits Known = + computeKnownBits(V, DL, 0, &AC, dyn_cast<Instruction>(GEP1), DT); bool SignKnownZero = Known.isNonNegative(); bool SignKnownOne = Known.isNegative(); @@ -2049,7 +2051,7 @@ BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { } BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { - initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); + initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); } char BasicAAWrapperPass::ID = 0; diff --git a/llvm/lib/Analysis/BlockFrequencyInfo.cpp b/llvm/lib/Analysis/BlockFrequencyInfo.cpp index de183bbde173d..544bd7757ae4a 100644 --- a/llvm/lib/Analysis/BlockFrequencyInfo.cpp +++ b/llvm/lib/Analysis/BlockFrequencyInfo.cpp @@ -20,6 +20,7 @@ #include "llvm/IR/CFG.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/GraphWriter.h" diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index a06ee096d54c2..ffba65b5ed5ee 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -16,6 +16,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" @@ -31,9 +32,11 @@ #include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <cassert> @@ -61,6 +64,12 @@ INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) +BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass() + : FunctionPass(ID) { + initializeBranchProbabilityInfoWrapperPassPass( + *PassRegistry::getPassRegistry()); +} + char BranchProbabilityInfoWrapperPass::ID = 0; // Weights are for internal use only. They are used by heuristics to help to @@ -138,69 +147,83 @@ static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1; /// instruction. This is essentially never taken. static const uint32_t IH_NONTAKEN_WEIGHT = 1; -/// Add \p BB to PostDominatedByUnreachable set if applicable. -void -BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) { - const Instruction *TI = BB->getTerminator(); - if (TI->getNumSuccessors() == 0) { - if (isa<UnreachableInst>(TI) || - // If this block is terminated by a call to - // @llvm.experimental.deoptimize then treat it like an unreachable since - // the @llvm.experimental.deoptimize call is expected to practically - // never execute. - BB->getTerminatingDeoptimizeCall()) - PostDominatedByUnreachable.insert(BB); - return; - } +static void UpdatePDTWorklist(const BasicBlock *BB, PostDominatorTree *PDT, + SmallVectorImpl<const BasicBlock *> &WorkList, + SmallPtrSetImpl<const BasicBlock *> &TargetSet) { + SmallVector<BasicBlock *, 8> Descendants; + SmallPtrSet<const BasicBlock *, 16> NewItems; + + PDT->getDescendants(const_cast<BasicBlock *>(BB), Descendants); + for (auto *BB : Descendants) + if (TargetSet.insert(BB).second) + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + if (!TargetSet.count(*PI)) + NewItems.insert(*PI); + WorkList.insert(WorkList.end(), NewItems.begin(), NewItems.end()); +} - // If the terminator is an InvokeInst, check only the normal destination block - // as the unwind edge of InvokeInst is also very unlikely taken. - if (auto *II = dyn_cast<InvokeInst>(TI)) { - if (PostDominatedByUnreachable.count(II->getNormalDest())) - PostDominatedByUnreachable.insert(BB); - return; +/// Compute a set of basic blocks that are post-dominated by unreachables. +void BranchProbabilityInfo::computePostDominatedByUnreachable( + const Function &F, PostDominatorTree *PDT) { + SmallVector<const BasicBlock *, 8> WorkList; + for (auto &BB : F) { + const Instruction *TI = BB.getTerminator(); + if (TI->getNumSuccessors() == 0) { + if (isa<UnreachableInst>(TI) || + // If this block is terminated by a call to + // @llvm.experimental.deoptimize then treat it like an unreachable + // since the @llvm.experimental.deoptimize call is expected to + // practically never execute. + BB.getTerminatingDeoptimizeCall()) + UpdatePDTWorklist(&BB, PDT, WorkList, PostDominatedByUnreachable); + } } - for (auto *I : successors(BB)) - // If any of successor is not post dominated then BB is also not. - if (!PostDominatedByUnreachable.count(I)) - return; - - PostDominatedByUnreachable.insert(BB); + while (!WorkList.empty()) { + const BasicBlock *BB = WorkList.pop_back_val(); + if (PostDominatedByUnreachable.count(BB)) + continue; + // If the terminator is an InvokeInst, check only the normal destination + // block as the unwind edge of InvokeInst is also very unlikely taken. + if (auto *II = dyn_cast<InvokeInst>(BB->getTerminator())) { + if (PostDominatedByUnreachable.count(II->getNormalDest())) + UpdatePDTWorklist(BB, PDT, WorkList, PostDominatedByUnreachable); + } + // If all the successors are unreachable, BB is unreachable as well. + else if (!successors(BB).empty() && + llvm::all_of(successors(BB), [this](const BasicBlock *Succ) { + return PostDominatedByUnreachable.count(Succ); + })) + UpdatePDTWorklist(BB, PDT, WorkList, PostDominatedByUnreachable); + } } -/// Add \p BB to PostDominatedByColdCall set if applicable. -void -BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) { - assert(!PostDominatedByColdCall.count(BB)); - const Instruction *TI = BB->getTerminator(); - if (TI->getNumSuccessors() == 0) - return; +/// compute a set of basic blocks that are post-dominated by ColdCalls. +void BranchProbabilityInfo::computePostDominatedByColdCall( + const Function &F, PostDominatorTree *PDT) { + SmallVector<const BasicBlock *, 8> WorkList; + for (auto &BB : F) + for (auto &I : BB) + if (const CallInst *CI = dyn_cast<CallInst>(&I)) + if (CI->hasFnAttr(Attribute::Cold)) + UpdatePDTWorklist(&BB, PDT, WorkList, PostDominatedByColdCall); - // If all of successor are post dominated then BB is also done. - if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) { - return PostDominatedByColdCall.count(SuccBB); - })) { - PostDominatedByColdCall.insert(BB); - return; - } + while (!WorkList.empty()) { + const BasicBlock *BB = WorkList.pop_back_val(); - // If the terminator is an InvokeInst, check only the normal destination - // block as the unwind edge of InvokeInst is also very unlikely taken. - if (auto *II = dyn_cast<InvokeInst>(TI)) - if (PostDominatedByColdCall.count(II->getNormalDest())) { - PostDominatedByColdCall.insert(BB); - return; + // If the terminator is an InvokeInst, check only the normal destination + // block as the unwind edge of InvokeInst is also very unlikely taken. + if (auto *II = dyn_cast<InvokeInst>(BB->getTerminator())) { + if (PostDominatedByColdCall.count(II->getNormalDest())) + UpdatePDTWorklist(BB, PDT, WorkList, PostDominatedByColdCall); } - - // Otherwise, if the block itself contains a cold function, add it to the - // set of blocks post-dominated by a cold call. - for (auto &I : *BB) - if (const CallInst *CI = dyn_cast<CallInst>(&I)) - if (CI->hasFnAttr(Attribute::Cold)) { - PostDominatedByColdCall.insert(BB); - return; - } + // If all of successor are post dominated then BB is also done. + else if (!successors(BB).empty() && + llvm::all_of(successors(BB), [this](const BasicBlock *Succ) { + return PostDominatedByColdCall.count(Succ); + })) + UpdatePDTWorklist(BB, PDT, WorkList, PostDominatedByColdCall); + } } /// Calculate edge weights for successors lead to unreachable. @@ -975,13 +998,16 @@ void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI, LLVM_DEBUG(dbgs() << "\n"); } + std::unique_ptr<PostDominatorTree> PDT = + std::make_unique<PostDominatorTree>(const_cast<Function &>(F)); + computePostDominatedByUnreachable(F, PDT.get()); + computePostDominatedByColdCall(F, PDT.get()); + // Walk the basic blocks in post-order so that we can build up state about // the successors of a block iteratively. for (auto BB : post_order(&F.getEntryBlock())) { LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); - updatePostDominatedByUnreachable(BB); - updatePostDominatedByColdCall(BB); // If there is no at least two successors, no sense to set probability. if (BB->getTerminator()->getNumSuccessors() < 2) continue; diff --git a/llvm/lib/Analysis/CFGPrinter.cpp b/llvm/lib/Analysis/CFGPrinter.cpp index 4f4103fefa253..88e7d3bdede1a 100644 --- a/llvm/lib/Analysis/CFGPrinter.cpp +++ b/llvm/lib/Analysis/CFGPrinter.cpp @@ -18,7 +18,9 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CFGPrinter.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/FileSystem.h" using namespace llvm; diff --git a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp index fd90bd1521d69..eb5c96e6eecaf 100644 --- a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp +++ b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -69,6 +69,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" diff --git a/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp b/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp index b87aa4065392c..85a8c3d2a00b0 100644 --- a/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp +++ b/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -46,6 +46,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" diff --git a/llvm/lib/Analysis/CallGraph.cpp b/llvm/lib/Analysis/CallGraph.cpp index 70aeb1a688ee0..8e8a50178518d 100644 --- a/llvm/lib/Analysis/CallGraph.cpp +++ b/llvm/lib/Analysis/CallGraph.cpp @@ -10,10 +10,11 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Config/llvm-config.h" -#include "llvm/IR/Module.h" #include "llvm/IR/Function.h" #include "llvm/IR/Intrinsics.h" +#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/CallPrinter.cpp b/llvm/lib/Analysis/CallPrinter.cpp index d24cbd104bf62..7246b73bfd4bf 100644 --- a/llvm/lib/Analysis/CallPrinter.cpp +++ b/llvm/lib/Analysis/CallPrinter.cpp @@ -16,6 +16,7 @@ #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DOTGraphTraitsPass.h" +#include "llvm/InitializePasses.h" using namespace llvm; diff --git a/llvm/lib/Analysis/ConstantFolding.cpp b/llvm/lib/Analysis/ConstantFolding.cpp index 8dbcf7034fdaf..b32924e6497a6 100644 --- a/llvm/lib/Analysis/ConstantFolding.cpp +++ b/llvm/lib/Analysis/ConstantFolding.cpp @@ -37,6 +37,8 @@ #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/IntrinsicsX86.h" #include "llvm/IR/Operator.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" @@ -764,8 +766,8 @@ Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, Constant *Op1, Constant *CastGEPIndices(Type *SrcElemTy, ArrayRef<Constant *> Ops, Type *ResultTy, Optional<unsigned> InRangeIndex, const DataLayout &DL, const TargetLibraryInfo *TLI) { - Type *IntPtrTy = DL.getIntPtrType(ResultTy); - Type *IntPtrScalarTy = IntPtrTy->getScalarType(); + Type *IntIdxTy = DL.getIndexType(ResultTy); + Type *IntIdxScalarTy = IntIdxTy->getScalarType(); bool Any = false; SmallVector<Constant*, 32> NewIdxs; @@ -773,11 +775,11 @@ Constant *CastGEPIndices(Type *SrcElemTy, ArrayRef<Constant *> Ops, if ((i == 1 || !isa<StructType>(GetElementPtrInst::getIndexedType( SrcElemTy, Ops.slice(1, i - 1)))) && - Ops[i]->getType()->getScalarType() != IntPtrScalarTy) { + Ops[i]->getType()->getScalarType() != IntIdxScalarTy) { Any = true; Type *NewType = Ops[i]->getType()->isVectorTy() - ? IntPtrTy - : IntPtrTy->getScalarType(); + ? IntIdxTy + : IntIdxScalarTy; NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i], true, NewType, @@ -837,7 +839,7 @@ Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP, if (!Ptr->getType()->isPointerTy()) return nullptr; - Type *IntPtrTy = DL.getIntPtrType(Ptr->getType()); + Type *IntIdxTy = DL.getIndexType(Ptr->getType()); // If this is a constant expr gep that is effectively computing an // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12' @@ -848,7 +850,7 @@ Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP, // "inttoptr (sub (ptrtoint Ptr), V)" if (Ops.size() == 2 && ResElemTy->isIntegerTy(8)) { auto *CE = dyn_cast<ConstantExpr>(Ops[1]); - assert((!CE || CE->getType() == IntPtrTy) && + assert((!CE || CE->getType() == IntIdxTy) && "CastGEPIndices didn't canonicalize index types!"); if (CE && CE->getOpcode() == Instruction::Sub && CE->getOperand(0)->isNullValue()) { @@ -863,7 +865,7 @@ Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP, return nullptr; } - unsigned BitWidth = DL.getTypeSizeInBits(IntPtrTy); + unsigned BitWidth = DL.getTypeSizeInBits(IntIdxTy); APInt Offset = APInt(BitWidth, DL.getIndexedOffsetInType( @@ -943,7 +945,7 @@ Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP, // The element size is 0. This may be [0 x Ty]*, so just use a zero // index for this level and proceed to the next level to see if it can // accommodate the offset. - NewIdxs.push_back(ConstantInt::get(IntPtrTy, 0)); + NewIdxs.push_back(ConstantInt::get(IntIdxTy, 0)); } else { // The element size is non-zero divide the offset by the element // size (rounding down), to compute the index at this level. @@ -952,7 +954,7 @@ Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP, if (Overflow) break; Offset -= NewIdx * ElemSize; - NewIdxs.push_back(ConstantInt::get(IntPtrTy, NewIdx)); + NewIdxs.push_back(ConstantInt::get(IntIdxTy, NewIdx)); } } else { auto *STy = cast<StructType>(Ty); diff --git a/llvm/lib/Analysis/CostModel.cpp b/llvm/lib/Analysis/CostModel.cpp index bf0cdbfd0c8b5..953da964c4352 100644 --- a/llvm/lib/Analysis/CostModel.cpp +++ b/llvm/lib/Analysis/CostModel.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Function.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp index b5c3c761ad98f..90ce13e6f6503 100644 --- a/llvm/lib/Analysis/DDG.cpp +++ b/llvm/lib/Analysis/DDG.cpp @@ -9,10 +9,17 @@ // The implementation for the data dependence graph. //===----------------------------------------------------------------------===// #include "llvm/Analysis/DDG.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopIterator.h" +#include "llvm/Support/CommandLine.h" using namespace llvm; +static cl::opt<bool> + CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore, + cl::desc("Create pi-block nodes.")); + #define DEBUG_TYPE "ddg" template class llvm::DGEdge<DDGNode, DDGEdge>; @@ -29,9 +36,16 @@ bool DDGNode::collectInstructions( InstructionListType &IList) const { assert(IList.empty() && "Expected the IList to be empty on entry."); if (isa<SimpleDDGNode>(this)) { - for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions()) + for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions()) if (Pred(I)) IList.push_back(I); + } else if (isa<PiBlockDDGNode>(this)) { + for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) { + assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported."); + SmallVector<Instruction *, 8> TmpIList; + PN->collectInstructions(Pred, TmpIList); + IList.insert(IList.end(), TmpIList.begin(), TmpIList.end()); + } } else llvm_unreachable("unimplemented type of node"); return !IList.empty(); @@ -46,11 +60,14 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) { case DDGNode::NodeKind::MultiInstruction: Out = "multi-instruction"; break; + case DDGNode::NodeKind::PiBlock: + Out = "pi-block"; + break; case DDGNode::NodeKind::Root: Out = "root"; break; case DDGNode::NodeKind::Unknown: - Out = "??"; + Out = "?? (error)"; break; } OS << Out; @@ -61,8 +78,15 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) { OS << "Node Address:" << &N << ":" << N.getKind() << "\n"; if (isa<SimpleDDGNode>(N)) { OS << " Instructions:\n"; - for (auto *I : cast<const SimpleDDGNode>(N).getInstructions()) + for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions()) OS.indent(2) << *I << "\n"; + } else if (isa<PiBlockDDGNode>(&N)) { + OS << "--- start of nodes in pi-block ---\n"; + auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes(); + unsigned Count = 0; + for (const DDGNode *N : Nodes) + OS << *N << (++Count == Nodes.size() ? "" : "\n"); + OS << "--- end of nodes in pi-block ---\n"; } else if (!isa<RootDDGNode>(N)) llvm_unreachable("unimplemented type of node"); @@ -99,6 +123,29 @@ SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N) SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); } //===--------------------------------------------------------------------===// +// PiBlockDDGNode implementation +//===--------------------------------------------------------------------===// + +PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List) + : DDGNode(NodeKind::PiBlock), NodeList(List) { + assert(!NodeList.empty() && "pi-block node constructed with an empty list."); +} + +PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N) + : DDGNode(N), NodeList(N.NodeList) { + assert(getKind() == NodeKind::PiBlock && !NodeList.empty() && + "constructing from invalid pi-block node."); +} + +PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N) + : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) { + assert(getKind() == NodeKind::PiBlock && !NodeList.empty() && + "constructing from invalid pi-block node."); +} + +PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); } + +//===--------------------------------------------------------------------===// // DDGEdge implementation //===--------------------------------------------------------------------===// @@ -115,7 +162,7 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) { Out = "rooted"; break; case DDGEdge::EdgeKind::Unknown: - Out = "??"; + Out = "?? (error)"; break; } OS << Out; @@ -134,19 +181,28 @@ using BasicBlockListType = SmallVector<BasicBlock *, 8>; DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D) : DependenceGraphInfo(F.getName().str(), D) { + // Put the basic blocks in program order for correct dependence + // directions. BasicBlockListType BBList; - for (auto &BB : F.getBasicBlockList()) - BBList.push_back(&BB); + for (auto &SCC : make_range(scc_begin(&F), scc_end(&F))) + for (BasicBlock * BB : SCC) + BBList.push_back(BB); + std::reverse(BBList.begin(), BBList.end()); DDGBuilder(*this, D, BBList).populate(); } -DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D) +DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI, + DependenceInfo &D) : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." + L.getHeader()->getName()) .str(), D) { + // Put the basic blocks in program order for correct dependence + // directions. + LoopBlocksDFS DFS(&L); + DFS.perform(&LI); BasicBlockListType BBList; - for (BasicBlock *BB : L.blocks()) + for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) BBList.push_back(BB); DDGBuilder(*this, D, BBList).populate(); } @@ -164,23 +220,47 @@ bool DataDependenceGraph::addNode(DDGNode &N) { return false; // In general, if the root node is already created and linked, it is not safe - // to add new nodes since they may be unreachable by the root. - // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an - // exception because they represent components that are already reachable by - // root. - assert(!Root && "Root node is already added. No more nodes can be added."); + // to add new nodes since they may be unreachable by the root. However, + // pi-block nodes need to be added after the root node is linked, and they are + // always reachable by the root, because they represent components that are + // already reachable by root. + auto *Pi = dyn_cast<PiBlockDDGNode>(&N); + assert((!Root || Pi) && + "Root node is already added. No more nodes can be added."); + if (isa<RootDDGNode>(N)) Root = &N; + if (Pi) + for (DDGNode *NI : Pi->getNodes()) + PiBlockMap.insert(std::make_pair(NI, Pi)); + return true; } +const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const { + if (PiBlockMap.find(&N) == PiBlockMap.end()) + return nullptr; + auto *Pi = PiBlockMap.find(&N)->second; + assert(PiBlockMap.find(Pi) == PiBlockMap.end() && + "Nested pi-blocks detected."); + return Pi; +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) { - for (auto *Node : G) - OS << *Node << "\n"; + for (DDGNode *Node : G) + // Avoid printing nodes that are part of a pi-block twice. They will get + // printed when the pi-block is printed. + if (!G.getPiBlock(*Node)) + OS << *Node << "\n"; + OS << "\n"; return OS; } +bool DDGBuilder::shouldCreatePiBlocks() const { + return CreatePiBlocks; +} + //===--------------------------------------------------------------------===// // DDG Analysis Passes //===--------------------------------------------------------------------===// @@ -190,7 +270,7 @@ DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR) { Function *F = L.getHeader()->getParent(); DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI); - return std::make_unique<DataDependenceGraph>(L, DI); + return std::make_unique<DataDependenceGraph>(L, AR.LI, DI); } AnalysisKey DDGAnalysis::Key; diff --git a/llvm/lib/Analysis/Delinearization.cpp b/llvm/lib/Analysis/Delinearization.cpp index c1043e446beb6..60cd1b5317d68 100644 --- a/llvm/lib/Analysis/Delinearization.cpp +++ b/llvm/lib/Analysis/Delinearization.cpp @@ -24,6 +24,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Type.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" diff --git a/llvm/lib/Analysis/DemandedBits.cpp b/llvm/lib/Analysis/DemandedBits.cpp index 01b8ff10d3559..aaee8c21f2891 100644 --- a/llvm/lib/Analysis/DemandedBits.cpp +++ b/llvm/lib/Analysis/DemandedBits.cpp @@ -40,6 +40,7 @@ #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 0038c9fb9ce42..9b38053c196b9 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -61,6 +61,7 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" @@ -141,6 +142,11 @@ INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", char DependenceAnalysisWrapperPass::ID = 0; +DependenceAnalysisWrapperPass::DependenceAnalysisWrapperPass() + : FunctionPass(ID) { + initializeDependenceAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); +} + FunctionPass *llvm::createDependenceAnalysisWrapperPass() { return new DependenceAnalysisWrapperPass(); } @@ -164,25 +170,25 @@ void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequiredTransitive<LoopInfoWrapperPass>(); } - // Used to test the dependence analyzer. -// Looks through the function, noting loads and stores. +// Looks through the function, noting instructions that may access memory. // Calls depends() on every possible pair and prints out the result. // Ignores all other instructions. static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) { auto *F = DA->getFunction(); for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE; ++SrcI) { - if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) { + if (SrcI->mayReadOrWriteMemory()) { for (inst_iterator DstI = SrcI, DstE = inst_end(F); DstI != DstE; ++DstI) { - if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) { - OS << "da analyze - "; + if (DstI->mayReadOrWriteMemory()) { + OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n"; + OS << " da analyze - "; if (auto D = DA->depends(&*SrcI, &*DstI, true)) { D->dump(OS); for (unsigned Level = 1; Level <= D->getLevels(); Level++) { if (D->isSplitable(Level)) { - OS << "da analyze - split level = " << Level; + OS << " da analyze - split level = " << Level; OS << ", iteration = " << *DA->getSplitIteration(*D, Level); OS << "!\n"; } @@ -876,14 +882,13 @@ void DependenceInfo::removeMatchingExtensions(Subscript *Pair) { } } - // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". -bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, - SmallBitVector &Loops) { - const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src); +bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest, + SmallBitVector &Loops, bool IsSrc) { + const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr); if (!AddRec) - return isLoopInvariant(Src, LoopNest); + return isLoopInvariant(Expr, LoopNest); const SCEV *Start = AddRec->getStart(); const SCEV *Step = AddRec->getStepRecurrence(*SE); const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); @@ -896,33 +901,25 @@ bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, } if (!isLoopInvariant(Step, LoopNest)) return false; - Loops.set(mapSrcLoop(AddRec->getLoop())); - return checkSrcSubscript(Start, LoopNest, Loops); + if (IsSrc) + Loops.set(mapSrcLoop(AddRec->getLoop())); + else + Loops.set(mapDstLoop(AddRec->getLoop())); + return checkSubscript(Start, LoopNest, Loops, IsSrc); } - +// Examine the scev and return true iff it's linear. +// Collect any loops mentioned in the set of "Loops". +bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, + SmallBitVector &Loops) { + return checkSubscript(Src, LoopNest, Loops, true); +} // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest, SmallBitVector &Loops) { - const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst); - if (!AddRec) - return isLoopInvariant(Dst, LoopNest); - const SCEV *Start = AddRec->getStart(); - const SCEV *Step = AddRec->getStepRecurrence(*SE); - const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); - if (!isa<SCEVCouldNotCompute>(UB)) { - if (SE->getTypeSizeInBits(Start->getType()) < - SE->getTypeSizeInBits(UB->getType())) { - if (!AddRec->getNoWrapFlags()) - return false; - } - } - if (!isLoopInvariant(Step, LoopNest)) - return false; - Loops.set(mapDstLoop(AddRec->getLoop())); - return checkDstSubscript(Start, LoopNest, Loops); + return checkSubscript(Dst, LoopNest, Loops, false); } @@ -3407,8 +3404,7 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst, if (Src == Dst) PossiblyLoopIndependent = false; - if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) || - (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory())) + if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory())) // if both instructions don't reference memory, there's no dependence return nullptr; @@ -3780,8 +3776,6 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst, return std::make_unique<FullDependence>(std::move(Result)); } - - //===----------------------------------------------------------------------===// // getSplitIteration - // Rather than spend rarely-used space recording the splitting iteration diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp index ed1d8351b2f03..e8a1a2fff9195 100644 --- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -10,6 +10,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DependenceGraphBuilder.h" +#include "llvm/ADT/EnumeratedArray.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DDG.h" @@ -22,6 +23,7 @@ STATISTIC(TotalGraphs, "Number of dependence graphs created."); STATISTIC(TotalDefUseEdges, "Number of def-use edges created."); STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created."); STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created."); +STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created."); STATISTIC(TotalConfusedEdges, "Number of confused memory dependencies between two nodes."); STATISTIC(TotalEdgeReversals, @@ -35,6 +37,15 @@ using InstructionListType = SmallVector<Instruction *, 2>; //===--------------------------------------------------------------------===// template <class G> +void AbstractDependenceGraphBuilder<G>::computeInstructionOrdinals() { + // The BBList is expected to be in program order. + size_t NextOrdinal = 1; + for (auto *BB : BBList) + for (auto &I : *BB) + InstOrdinalMap.insert(std::make_pair(&I, NextOrdinal++)); +} + +template <class G> void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() { ++TotalGraphs; assert(IMap.empty() && "Expected empty instruction map at start"); @@ -42,6 +53,7 @@ void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() { for (Instruction &I : *BB) { auto &NewNode = createFineGrainedNode(I); IMap.insert(std::make_pair(&I, &NewNode)); + NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I))); ++TotalFineGrainedNodes; } } @@ -74,6 +86,144 @@ void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() { } } +template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() { + if (!shouldCreatePiBlocks()) + return; + + LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n"); + + // The overall algorithm is as follows: + // 1. Identify SCCs and for each SCC create a pi-block node containing all + // the nodes in that SCC. + // 2. Identify incoming edges incident to the nodes inside of the SCC and + // reconnect them to the pi-block node. + // 3. Identify outgoing edges from the nodes inside of the SCC to nodes + // outside of it and reconnect them so that the edges are coming out of the + // SCC node instead. + + // Adding nodes as we iterate through the SCCs cause the SCC + // iterators to get invalidated. To prevent this invalidation, we first + // collect a list of nodes that are part of an SCC, and then iterate over + // those lists to create the pi-block nodes. Each element of the list is a + // list of nodes in an SCC. Note: trivial SCCs containing a single node are + // ignored. + SmallVector<NodeListType, 4> ListOfSCCs; + for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) { + if (SCC.size() > 1) + ListOfSCCs.emplace_back(SCC.begin(), SCC.end()); + } + + for (NodeListType &NL : ListOfSCCs) { + LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size() + << " nodes in it.\n"); + + // SCC iterator may put the nodes in an order that's different from the + // program order. To preserve original program order, we sort the list of + // nodes based on ordinal numbers computed earlier. + llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) { + return getOrdinal(*LHS) < getOrdinal(*RHS); + }); + + NodeType &PiNode = createPiBlock(NL); + ++TotalPiBlockNodes; + + // Build a set to speed up the lookup for edges whose targets + // are inside the SCC. + SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end()); + + // We have the set of nodes in the SCC. We go through the set of nodes + // that are outside of the SCC and look for edges that cross the two sets. + for (NodeType *N : Graph) { + + // Skip the SCC node and all the nodes inside of it. + if (*N == PiNode || NodesInSCC.count(N)) + continue; + + for (NodeType *SCCNode : NL) { + + enum Direction { + Incoming, // Incoming edges to the SCC + Outgoing, // Edges going ot of the SCC + DirectionCount // To make the enum usable as an array index. + }; + + // Use these flags to help us avoid creating redundant edges. If there + // are more than one edges from an outside node to inside nodes, we only + // keep one edge from that node to the pi-block node. Similarly, if + // there are more than one edges from inside nodes to an outside node, + // we only keep one edge from the pi-block node to the outside node. + // There is a flag defined for each direction (incoming vs outgoing) and + // for each type of edge supported, using a two-dimensional boolean + // array. + using EdgeKind = typename EdgeType::EdgeKind; + EnumeratedArray<bool, EdgeKind> EdgeAlreadyCreated[DirectionCount]{ + false, false}; + + auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst, + const EdgeKind K) { + switch (K) { + case EdgeKind::RegisterDefUse: + createDefUseEdge(Src, Dst); + break; + case EdgeKind::MemoryDependence: + createMemoryEdge(Src, Dst); + break; + case EdgeKind::Rooted: + createRootedEdge(Src, Dst); + break; + default: + llvm_unreachable("Unsupported type of edge."); + } + }; + + auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New, + const Direction Dir) { + if (!Src->hasEdgeTo(*Dst)) + return; + LLVM_DEBUG(dbgs() + << "reconnecting(" + << (Dir == Direction::Incoming ? "incoming)" : "outgoing)") + << ":\nSrc:" << *Src << "\nDst:" << *Dst + << "\nNew:" << *New << "\n"); + assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) && + "Invalid direction."); + + SmallVector<EdgeType *, 10> EL; + Src->findEdgesTo(*Dst, EL); + for (EdgeType *OldEdge : EL) { + EdgeKind Kind = OldEdge->getKind(); + if (!EdgeAlreadyCreated[Dir][Kind]) { + if (Dir == Direction::Incoming) { + createEdgeOfKind(*Src, *New, Kind); + LLVM_DEBUG(dbgs() << "created edge from Src to New.\n"); + } else if (Dir == Direction::Outgoing) { + createEdgeOfKind(*New, *Dst, Kind); + LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n"); + } + EdgeAlreadyCreated[Dir][Kind] = true; + } + Src->removeEdge(*OldEdge); + destroyEdge(*OldEdge); + LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n"); + } + }; + + // Process incoming edges incident to the pi-block node. + reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming); + + // Process edges that are coming out of the pi-block node. + reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing); + } + } + } + + // Ordinal maps are no longer needed. + InstOrdinalMap.clear(); + NodeOrdinalMap.clear(); + + LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n"); +} + template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() { for (NodeType *N : Graph) { InstructionListType SrcIList; @@ -224,5 +374,34 @@ void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() { } } +template <class G> +void AbstractDependenceGraphBuilder<G>::sortNodesTopologically() { + + // If we don't create pi-blocks, then we may not have a DAG. + if (!shouldCreatePiBlocks()) + return; + + SmallVector<NodeType *, 64> NodesInPO; + using NodeKind = typename NodeType::NodeKind; + for (NodeType *N : post_order(&Graph)) { + if (N->getKind() == NodeKind::PiBlock) { + // Put members of the pi-block right after the pi-block itself, for + // convenience. + const NodeListType &PiBlockMembers = getNodesInPiBlock(*N); + NodesInPO.insert(NodesInPO.end(), PiBlockMembers.begin(), + PiBlockMembers.end()); + } + NodesInPO.push_back(N); + } + + size_t OldSize = Graph.Nodes.size(); + Graph.Nodes.clear(); + for (NodeType *N : reverse(NodesInPO)) + Graph.Nodes.push_back(N); + if (Graph.Nodes.size() != OldSize) + assert(false && + "Expected the number of nodes to stay the same after the sort"); +} + template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>; template class llvm::DependenceGraphInfo<DDGNode>; diff --git a/llvm/lib/Analysis/DomPrinter.cpp b/llvm/lib/Analysis/DomPrinter.cpp index d9f43dd746efb..024a0fb499505 100644 --- a/llvm/lib/Analysis/DomPrinter.cpp +++ b/llvm/lib/Analysis/DomPrinter.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/DOTGraphTraitsPass.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/InitializePasses.h" using namespace llvm; diff --git a/llvm/lib/Analysis/DomTreeUpdater.cpp b/llvm/lib/Analysis/DomTreeUpdater.cpp index 49215889cfd60..b374334ea3716 100644 --- a/llvm/lib/Analysis/DomTreeUpdater.cpp +++ b/llvm/lib/Analysis/DomTreeUpdater.cpp @@ -233,7 +233,7 @@ void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) { return; if (Strategy == UpdateStrategy::Lazy) { - for (const auto U : Updates) + for (const auto &U : Updates) if (!isSelfDominance(U)) PendUpdates.push_back(U); @@ -253,7 +253,7 @@ void DomTreeUpdater::applyUpdatesPermissive( SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen; SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates; - for (const auto U : Updates) { + for (const auto &U : Updates) { auto Edge = std::make_pair(U.getFrom(), U.getTo()); // Because it is illegal to submit updates that have already been applied // and updates to an edge need to be strictly ordered, diff --git a/llvm/lib/Analysis/DominanceFrontier.cpp b/llvm/lib/Analysis/DominanceFrontier.cpp index f9a554acb7ea3..14e6965f12598 100644 --- a/llvm/lib/Analysis/DominanceFrontier.cpp +++ b/llvm/lib/Analysis/DominanceFrontier.cpp @@ -12,6 +12,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/GlobalsModRef.cpp b/llvm/lib/Analysis/GlobalsModRef.cpp index efdf9706ba3c3..4361e0dc9bbd5 100644 --- a/llvm/lib/Analysis/GlobalsModRef.cpp +++ b/llvm/lib/Analysis/GlobalsModRef.cpp @@ -25,6 +25,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" using namespace llvm; @@ -286,7 +287,7 @@ GlobalsAAResult::getFunctionInfo(const Function *F) { void GlobalsAAResult::AnalyzeGlobals(Module &M) { SmallPtrSet<Function *, 32> TrackedFunctions; for (Function &F : M) - if (F.hasLocalLinkage()) + if (F.hasLocalLinkage()) { if (!AnalyzeUsesOfPointer(&F)) { // Remember that we are tracking this global. NonAddressTakenGlobals.insert(&F); @@ -294,7 +295,9 @@ void GlobalsAAResult::AnalyzeGlobals(Module &M) { Handles.emplace_front(*this, &F); Handles.front().I = Handles.begin(); ++NumNonAddrTakenFunctions; - } + } else + UnknownFunctionsWithLocalLinkage = true; + } SmallPtrSet<Function *, 16> Readers, Writers; for (GlobalVariable &GV : M.globals()) @@ -526,9 +529,12 @@ void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) { FI.setMayReadAnyGlobal(); } else { FI.addModRefInfo(ModRefInfo::ModRef); - // Can't say anything useful unless it's an intrinsic - they don't - // read or write global variables of the kind considered here. - KnowNothing = !F->isIntrinsic(); + if (!F->onlyAccessesArgMemory()) + FI.setMayReadAnyGlobal(); + if (!F->isIntrinsic()) { + KnowNothing = true; + break; + } } continue; } @@ -927,7 +933,9 @@ ModRefInfo GlobalsAAResult::getModRefInfo(const CallBase *Call, // global we are tracking, return information if we have it. if (const GlobalValue *GV = dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL))) - if (GV->hasLocalLinkage()) + // If GV is internal to this IR and there is no function with local linkage + // that has had their address taken, keep looking for a tighter ModRefInfo. + if (GV->hasLocalLinkage() && !UnknownFunctionsWithLocalLinkage) if (const Function *F = Call->getCalledFunction()) if (NonAddressTakenGlobals.count(GV)) if (const FunctionInfo *FI = getFunctionInfo(F)) diff --git a/llvm/lib/Analysis/GuardUtils.cpp b/llvm/lib/Analysis/GuardUtils.cpp index cad92f6e56bb7..d482832798581 100644 --- a/llvm/lib/Analysis/GuardUtils.cpp +++ b/llvm/lib/Analysis/GuardUtils.cpp @@ -13,19 +13,25 @@ #include "llvm/IR/PatternMatch.h" using namespace llvm; +using namespace llvm::PatternMatch; bool llvm::isGuard(const User *U) { - using namespace llvm::PatternMatch; return match(U, m_Intrinsic<Intrinsic::experimental_guard>()); } +bool llvm::isWidenableBranch(const User *U) { + Value *Condition, *WidenableCondition; + BasicBlock *GuardedBB, *DeoptBB; + return parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB, + DeoptBB); +} + bool llvm::isGuardAsWidenableBranch(const User *U) { Value *Condition, *WidenableCondition; BasicBlock *GuardedBB, *DeoptBB; if (!parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB, DeoptBB)) return false; - using namespace llvm::PatternMatch; for (auto &Insn : *DeoptBB) { if (match(&Insn, m_Intrinsic<Intrinsic::experimental_deoptimize>())) return true; @@ -38,12 +44,63 @@ bool llvm::isGuardAsWidenableBranch(const User *U) { bool llvm::parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) { - using namespace llvm::PatternMatch; - if (!match(U, m_Br(m_And(m_Value(Condition), m_Value(WidenableCondition)), - IfTrueBB, IfFalseBB))) + + Use *C, *WC; + if (parseWidenableBranch(const_cast<User*>(U), C, WC, IfTrueBB, IfFalseBB)) { + if (C) + Condition = C->get(); + else + Condition = ConstantInt::getTrue(IfTrueBB->getContext()); + WidenableCondition = WC->get(); + return true; + } + return false; +} + +bool llvm::parseWidenableBranch(User *U, Use *&C,Use *&WC, + BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) { + + auto *BI = dyn_cast<BranchInst>(U); + if (!BI || !BI->isConditional()) + return false; + auto *Cond = BI->getCondition(); + if (!Cond->hasOneUse()) + return false; + + IfTrueBB = BI->getSuccessor(0); + IfFalseBB = BI->getSuccessor(1); + + if (match(Cond, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) { + WC = &BI->getOperandUse(0); + C = nullptr; + return true; + } + + // Check for two cases: + // 1) br (i1 (and A, WC())), label %IfTrue, label %IfFalse + // 2) br (i1 (and WC(), B)), label %IfTrue, label %IfFalse + // We do not check for more generalized and trees as we should canonicalize + // to the form above in instcombine. (TODO) + Value *A, *B; + if (!match(Cond, m_And(m_Value(A), m_Value(B)))) return false; - // TODO: At the moment, we only recognize the branch if the WC call in this - // specific position. We should generalize! - return match(WidenableCondition, - m_Intrinsic<Intrinsic::experimental_widenable_condition>()); + auto *And = dyn_cast<Instruction>(Cond); + if (!And) + // Could be a constexpr + return false; + + if (match(A, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) && + A->hasOneUse()) { + WC = &And->getOperandUse(0); + C = &And->getOperandUse(1); + return true; + } + + if (match(B, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) && + B->hasOneUse()) { + WC = &And->getOperandUse(1); + C = &And->getOperandUse(0); + return true; + } + return false; } diff --git a/llvm/lib/Analysis/IVDescriptors.cpp b/llvm/lib/Analysis/IVDescriptors.cpp index 6fb600114bc61..ac81cba836f89 100644 --- a/llvm/lib/Analysis/IVDescriptors.cpp +++ b/llvm/lib/Analysis/IVDescriptors.cpp @@ -22,7 +22,6 @@ #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" @@ -699,25 +698,48 @@ bool RecurrenceDescriptor::isFirstOrderRecurrence( // Ensure every user of the phi node is dominated by the previous value. // The dominance requirement ensures the loop vectorizer will not need to // vectorize the initial value prior to the first iteration of the loop. - // TODO: Consider extending this sinking to handle other kinds of instructions - // and expressions, beyond sinking a single cast past Previous. + // TODO: Consider extending this sinking to handle memory instructions and + // phis with multiple users. + + // Returns true, if all users of I are dominated by DominatedBy. + auto allUsesDominatedBy = [DT](Instruction *I, Instruction *DominatedBy) { + return all_of(I->uses(), [DT, DominatedBy](Use &U) { + return DT->dominates(DominatedBy, U); + }); + }; + if (Phi->hasOneUse()) { - auto *I = Phi->user_back(); - if (I->isCast() && (I->getParent() == Phi->getParent()) && I->hasOneUse() && - DT->dominates(Previous, I->user_back())) { - if (!DT->dominates(Previous, I)) // Otherwise we're good w/o sinking. - SinkAfter[I] = Previous; + Instruction *I = Phi->user_back(); + + // If the user of the PHI is also the incoming value, we potentially have a + // reduction and which cannot be handled by sinking. + if (Previous == I) + return false; + + // We cannot sink terminator instructions. + if (I->getParent()->getTerminator() == I) + return false; + + // Do not try to sink an instruction multiple times (if multiple operands + // are first order recurrences). + // TODO: We can support this case, by sinking the instruction after the + // 'deepest' previous instruction. + if (SinkAfter.find(I) != SinkAfter.end()) + return false; + + if (DT->dominates(Previous, I)) // We already are good w/o sinking. return true; - } - } - for (User *U : Phi->users()) - if (auto *I = dyn_cast<Instruction>(U)) { - if (!DT->dominates(Previous, I)) - return false; + // We can sink any instruction without side effects, as long as all users + // are dominated by the instruction we are sinking after. + if (I->getParent() == Phi->getParent() && !I->mayHaveSideEffects() && + allUsesDominatedBy(I, Previous)) { + SinkAfter[I] = Previous; + return true; } + } - return true; + return allUsesDominatedBy(Phi, Previous); } /// This function returns the identity element (or neutral element) for diff --git a/llvm/lib/Analysis/IVUsers.cpp b/llvm/lib/Analysis/IVUsers.cpp index 681a0cf7e9814..9432696b5a261 100644 --- a/llvm/lib/Analysis/IVUsers.cpp +++ b/llvm/lib/Analysis/IVUsers.cpp @@ -27,6 +27,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> diff --git a/llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp b/llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp index 68153de8219f5..dc4cbc371ef43 100644 --- a/llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp +++ b/llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp @@ -21,6 +21,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/ProfileData/InstrProf.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include <string> #include <utility> diff --git a/llvm/lib/Analysis/InlineCost.cpp b/llvm/lib/Analysis/InlineCost.cpp index 89811ec0e377a..de83a48aad16a 100644 --- a/llvm/lib/Analysis/InlineCost.cpp +++ b/llvm/lib/Analysis/InlineCost.cpp @@ -18,9 +18,9 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ProfileSummaryInfo.h" @@ -36,6 +36,7 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -50,7 +51,7 @@ static cl::opt<int> InlineThreshold( cl::desc("Control the amount of inlining to perform (default = 225)")); static cl::opt<int> HintThreshold( - "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore, + "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore, cl::desc("Threshold for inlining functions with inline hint")); static cl::opt<int> @@ -62,7 +63,7 @@ static cl::opt<int> // PGO before we actually hook up inliner with analysis passes such as BPI and // BFI. static cl::opt<int> ColdThreshold( - "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore, + "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore, cl::desc("Threshold for inlining functions with cold attribute")); static cl::opt<int> @@ -92,11 +93,13 @@ static cl::opt<bool> OptComputeFullInlineCost( "exceeds the threshold.")); namespace { - +class InlineCostCallAnalyzer; class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { typedef InstVisitor<CallAnalyzer, bool> Base; friend class InstVisitor<CallAnalyzer, bool>; +protected: + virtual ~CallAnalyzer() {} /// The TargetTransformInfo available for this compilation. const TargetTransformInfo &TTI; @@ -123,20 +126,86 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { /// easily cacheable. Instead, use the cover function paramHasAttr. CallBase &CandidateCall; - /// Tunable parameters that control the analysis. - const InlineParams &Params; + /// Extension points for handling callsite features. + /// Called after a basic block was analyzed. + virtual void onBlockAnalyzed(const BasicBlock *BB) {} - /// Upper bound for the inlining cost. Bonuses are being applied to account - /// for speculative "expected profit" of the inlining decision. - int Threshold; + /// Called at the end of the analysis of the callsite. Return the outcome of + /// the analysis, i.e. 'InlineResult(true)' if the inlining may happen, or + /// the reason it can't. + virtual InlineResult finalizeAnalysis() { return true; } - /// Inlining cost measured in abstract units, accounts for all the - /// instructions expected to be executed for a given function invocation. - /// Instructions that are statically proven to be dead based on call-site - /// arguments are not counted here. - int Cost = 0; + /// Called when we're about to start processing a basic block, and every time + /// we are done processing an instruction. Return true if there is no point in + /// continuing the analysis (e.g. we've determined already the call site is + /// too expensive to inline) + virtual bool shouldStop() { return false; } + + /// Called before the analysis of the callee body starts (with callsite + /// contexts propagated). It checks callsite-specific information. Return a + /// reason analysis can't continue if that's the case, or 'true' if it may + /// continue. + virtual InlineResult onAnalysisStart() { return true; } + + /// Called if the analysis engine decides SROA cannot be done for the given + /// alloca. + virtual void onDisableSROA(AllocaInst *Arg) {} + + /// Called the analysis engine determines load elimination won't happen. + virtual void onDisableLoadElimination() {} + + /// Called to account for a call. + virtual void onCallPenalty() {} + + /// Called to account for the expectation the inlining would result in a load + /// elimination. + virtual void onLoadEliminationOpportunity() {} - bool ComputeFullInlineCost; + /// Called to account for the cost of argument setup for the Call in the + /// callee's body (not the callsite currently under analysis). + virtual void onCallArgumentSetup(const CallBase &Call) {} + + /// Called to account for a load relative intrinsic. + virtual void onLoadRelativeIntrinsic() {} + + /// Called to account for a lowered call. + virtual void onLoweredCall(Function *F, CallBase &Call, bool IsIndirectCall) { + } + + /// Account for a jump table of given size. Return false to stop further + /// processing the switch instruction + virtual bool onJumpTable(unsigned JumpTableSize) { return true; } + + /// Account for a case cluster of given size. Return false to stop further + /// processing of the instruction. + virtual bool onCaseCluster(unsigned NumCaseCluster) { return true; } + + /// Called at the end of processing a switch instruction, with the given + /// number of case clusters. + virtual void onFinalizeSwitch(unsigned JumpTableSize, + unsigned NumCaseCluster) {} + + /// Called to account for any other instruction not specifically accounted + /// for. + virtual void onCommonInstructionSimplification() {} + + /// Start accounting potential benefits due to SROA for the given alloca. + virtual void onInitializeSROAArg(AllocaInst *Arg) {} + + /// Account SROA savings for the AllocaInst value. + virtual void onAggregateSROAUse(AllocaInst *V) {} + + bool handleSROA(Value *V, bool DoNotDisable) { + // Check for SROA candidates in comparisons. + if (auto *SROAArg = getSROAArgForValueOrNull(V)) { + if (DoNotDisable) { + onAggregateSROAUse(SROAArg); + return true; + } + disableSROAForArg(SROAArg); + } + return false; + } bool IsCallerRecursive = false; bool IsRecursiveCall = false; @@ -153,12 +222,6 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { unsigned NumInstructions = 0; unsigned NumVectorInstructions = 0; - /// Bonus to be applied when percentage of vector instructions in callee is - /// high (see more details in updateThreshold). - int VectorBonus = 0; - /// Bonus to be applied when the callee has only one reachable basic block. - int SingleBBBonus = 0; - /// While we walk the potentially-inlined instructions, we build up and /// maintain a mapping of simplified values specific to this callsite. The /// idea is to propagate any special information we have about arguments to @@ -170,12 +233,12 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { /// Keep track of the values which map back (through function arguments) to /// allocas on the caller stack which could be simplified through SROA. - DenseMap<Value *, Value *> SROAArgValues; + DenseMap<Value *, AllocaInst *> SROAArgValues; - /// The mapping of caller Alloca values to their accumulated cost savings. If - /// we have to disable SROA for one of the allocas, this tells us how much - /// cost must be added. - DenseMap<Value *, int> SROAArgCosts; + /// Keep track of Allocas for which we believe we may get SROA optimization. + /// We don't delete entries in SROAArgValue because we still want + /// isAllocaDerivedArg to function correctly. + DenseSet<AllocaInst *> EnabledSROAArgValues; /// Keep track of values which map to a pointer base and constant offset. DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs; @@ -192,17 +255,20 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { /// loads. bool EnableLoadElimination; SmallPtrSet<Value *, 16> LoadAddrSet; - int LoadEliminationCost = 0; + + AllocaInst *getSROAArgForValueOrNull(Value *V) const { + auto It = SROAArgValues.find(V); + if (It == SROAArgValues.end() || + EnabledSROAArgValues.count(It->second) == 0) + return nullptr; + return It->second; + } // Custom simplification helper routines. bool isAllocaDerivedArg(Value *V); - bool lookupSROAArgAndCost(Value *V, Value *&Arg, - DenseMap<Value *, int>::iterator &CostIt); - void disableSROA(DenseMap<Value *, int>::iterator CostIt); + void disableSROAForArg(AllocaInst *SROAArg); void disableSROA(Value *V); void findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB); - void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, - int InstructionCost); void disableLoadElimination(); bool isGEPFree(GetElementPtrInst &GEP); bool canFoldInboundsGEP(GetElementPtrInst &I); @@ -223,32 +289,13 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { /// inlined through this particular callsite. bool isKnownNonNullInCallee(Value *V); - /// Update Threshold based on callsite properties such as callee - /// attributes and callee hotness for PGO builds. The Callee is explicitly - /// passed to support analyzing indirect calls whose target is inferred by - /// analysis. - void updateThreshold(CallBase &Call, Function &Callee); - /// Return true if size growth is allowed when inlining the callee at \p Call. bool allowSizeGrowth(CallBase &Call); - /// Return true if \p Call is a cold callsite. - bool isColdCallSite(CallBase &Call, BlockFrequencyInfo *CallerBFI); - - /// Return a higher threshold if \p Call is a hot callsite. - Optional<int> getHotCallSiteThreshold(CallBase &Call, - BlockFrequencyInfo *CallerBFI); - // Custom analysis routines. InlineResult analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues); - /// Handle a capped 'int' increment for Cost. - void addCost(int64_t Inc, int64_t UpperBound = INT_MAX) { - assert(UpperBound > 0 && UpperBound <= INT_MAX && "invalid upper bound"); - Cost = (int)std::min(UpperBound, Cost + Inc); - } - // Disable several entry points to the visitor so we don't accidentally use // them by declaring but not defining them here. void visit(Module *); @@ -294,18 +341,12 @@ public: std::function<AssumptionCache &(Function &)> &GetAssumptionCache, Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI, ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE, - Function &Callee, CallBase &Call, const InlineParams &Params) + Function &Callee, CallBase &Call) : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI), PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE), - CandidateCall(Call), Params(Params), Threshold(Params.DefaultThreshold), - ComputeFullInlineCost(OptComputeFullInlineCost || - Params.ComputeFullInlineCost || ORE), - EnableLoadElimination(true) {} + CandidateCall(Call), EnableLoadElimination(true) {} - InlineResult analyzeCall(CallBase &Call); - - int getThreshold() { return Threshold; } - int getCost() { return Cost; } + InlineResult analyze(); // Keep a bunch of stats about the cost savings found so we can print them // out when debugging. @@ -315,12 +356,291 @@ public: unsigned NumConstantPtrCmps = 0; unsigned NumConstantPtrDiffs = 0; unsigned NumInstructionsSimplified = 0; + + void dump(); +}; + +/// FIXME: if it is necessary to derive from InlineCostCallAnalyzer, note +/// the FIXME in onLoweredCall, when instantiating an InlineCostCallAnalyzer +class InlineCostCallAnalyzer final : public CallAnalyzer { + const int CostUpperBound = INT_MAX - InlineConstants::InstrCost - 1; + const bool ComputeFullInlineCost; + int LoadEliminationCost = 0; + /// Bonus to be applied when percentage of vector instructions in callee is + /// high (see more details in updateThreshold). + int VectorBonus = 0; + /// Bonus to be applied when the callee has only one reachable basic block. + int SingleBBBonus = 0; + + /// Tunable parameters that control the analysis. + const InlineParams &Params; + + /// Upper bound for the inlining cost. Bonuses are being applied to account + /// for speculative "expected profit" of the inlining decision. + int Threshold = 0; + + /// Attempt to evaluate indirect calls to boost its inline cost. + const bool BoostIndirectCalls; + + /// Inlining cost measured in abstract units, accounts for all the + /// instructions expected to be executed for a given function invocation. + /// Instructions that are statically proven to be dead based on call-site + /// arguments are not counted here. + int Cost = 0; + + bool SingleBB = true; + unsigned SROACostSavings = 0; unsigned SROACostSavingsLost = 0; + /// The mapping of caller Alloca values to their accumulated cost savings. If + /// we have to disable SROA for one of the allocas, this tells us how much + /// cost must be added. + DenseMap<AllocaInst *, int> SROAArgCosts; + + /// Return true if \p Call is a cold callsite. + bool isColdCallSite(CallBase &Call, BlockFrequencyInfo *CallerBFI); + + /// Update Threshold based on callsite properties such as callee + /// attributes and callee hotness for PGO builds. The Callee is explicitly + /// passed to support analyzing indirect calls whose target is inferred by + /// analysis. + void updateThreshold(CallBase &Call, Function &Callee); + /// Return a higher threshold if \p Call is a hot callsite. + Optional<int> getHotCallSiteThreshold(CallBase &Call, + BlockFrequencyInfo *CallerBFI); + + /// Handle a capped 'int' increment for Cost. + void addCost(int64_t Inc, int64_t UpperBound = INT_MAX) { + assert(UpperBound > 0 && UpperBound <= INT_MAX && "invalid upper bound"); + Cost = (int)std::min(UpperBound, Cost + Inc); + } + + void onDisableSROA(AllocaInst *Arg) override { + auto CostIt = SROAArgCosts.find(Arg); + if (CostIt == SROAArgCosts.end()) + return; + addCost(CostIt->second); + SROACostSavings -= CostIt->second; + SROACostSavingsLost += CostIt->second; + SROAArgCosts.erase(CostIt); + } + + void onDisableLoadElimination() override { + addCost(LoadEliminationCost); + LoadEliminationCost = 0; + } + void onCallPenalty() override { addCost(InlineConstants::CallPenalty); } + void onCallArgumentSetup(const CallBase &Call) override { + // Pay the price of the argument setup. We account for the average 1 + // instruction per call argument setup here. + addCost(Call.arg_size() * InlineConstants::InstrCost); + } + void onLoadRelativeIntrinsic() override { + // This is normally lowered to 4 LLVM instructions. + addCost(3 * InlineConstants::InstrCost); + } + void onLoweredCall(Function *F, CallBase &Call, + bool IsIndirectCall) override { + // We account for the average 1 instruction per call argument setup here. + addCost(Call.arg_size() * InlineConstants::InstrCost); + + // If we have a constant that we are calling as a function, we can peer + // through it and see the function target. This happens not infrequently + // during devirtualization and so we want to give it a hefty bonus for + // inlining, but cap that bonus in the event that inlining wouldn't pan out. + // Pretend to inline the function, with a custom threshold. + if (IsIndirectCall && BoostIndirectCalls) { + auto IndirectCallParams = Params; + IndirectCallParams.DefaultThreshold = + InlineConstants::IndirectCallThreshold; + /// FIXME: if InlineCostCallAnalyzer is derived from, this may need + /// to instantiate the derived class. + InlineCostCallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, + Call, IndirectCallParams, false); + if (CA.analyze()) { + // We were able to inline the indirect call! Subtract the cost from the + // threshold to get the bonus we want to apply, but don't go below zero. + Cost -= std::max(0, CA.getThreshold() - CA.getCost()); + } + } else + // Otherwise simply add the cost for merely making the call. + addCost(InlineConstants::CallPenalty); + } + + void onFinalizeSwitch(unsigned JumpTableSize, + unsigned NumCaseCluster) override { + // If suitable for a jump table, consider the cost for the table size and + // branch to destination. + // Maximum valid cost increased in this function. + if (JumpTableSize) { + int64_t JTCost = (int64_t)JumpTableSize * InlineConstants::InstrCost + + 4 * InlineConstants::InstrCost; + + addCost(JTCost, (int64_t)CostUpperBound); + return; + } + // Considering forming a binary search, we should find the number of nodes + // which is same as the number of comparisons when lowered. For a given + // number of clusters, n, we can define a recursive function, f(n), to find + // the number of nodes in the tree. The recursion is : + // f(n) = 1 + f(n/2) + f (n - n/2), when n > 3, + // and f(n) = n, when n <= 3. + // This will lead a binary tree where the leaf should be either f(2) or f(3) + // when n > 3. So, the number of comparisons from leaves should be n, while + // the number of non-leaf should be : + // 2^(log2(n) - 1) - 1 + // = 2^log2(n) * 2^-1 - 1 + // = n / 2 - 1. + // Considering comparisons from leaf and non-leaf nodes, we can estimate the + // number of comparisons in a simple closed form : + // n + n / 2 - 1 = n * 3 / 2 - 1 + if (NumCaseCluster <= 3) { + // Suppose a comparison includes one compare and one conditional branch. + addCost(NumCaseCluster * 2 * InlineConstants::InstrCost); + return; + } + + int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1; + int64_t SwitchCost = + ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost; + + addCost(SwitchCost, (int64_t)CostUpperBound); + } + void onCommonInstructionSimplification() override { + addCost(InlineConstants::InstrCost); + } + + void onInitializeSROAArg(AllocaInst *Arg) override { + assert(Arg != nullptr && + "Should not initialize SROA costs for null value."); + SROAArgCosts[Arg] = 0; + EnabledSROAArgValues.insert(Arg); + } + + void onAggregateSROAUse(AllocaInst *SROAArg) override { + auto CostIt = SROAArgCosts.find(SROAArg); + assert(CostIt != SROAArgCosts.end() && + "expected this argument to have a cost"); + CostIt->second += InlineConstants::InstrCost; + SROACostSavings += InlineConstants::InstrCost; + } + + void onBlockAnalyzed(const BasicBlock *BB) override { + auto *TI = BB->getTerminator(); + // If we had any successors at this point, than post-inlining is likely to + // have them as well. Note that we assume any basic blocks which existed + // due to branches or switches which folded above will also fold after + // inlining. + if (SingleBB && TI->getNumSuccessors() > 1) { + // Take off the bonus we applied to the threshold. + Threshold -= SingleBBBonus; + SingleBB = false; + } + } + InlineResult finalizeAnalysis() override { + // Loops generally act a lot like calls in that they act like barriers to + // movement, require a certain amount of setup, etc. So when optimising for + // size, we penalise any call sites that perform loops. We do this after all + // other costs here, so will likely only be dealing with relatively small + // functions (and hence DT and LI will hopefully be cheap). + auto *Caller = CandidateCall.getFunction(); + if (Caller->hasMinSize()) { + DominatorTree DT(F); + LoopInfo LI(DT); + int NumLoops = 0; + for (Loop *L : LI) { + // Ignore loops that will not be executed + if (DeadBlocks.count(L->getHeader())) + continue; + NumLoops++; + } + addCost(NumLoops * InlineConstants::CallPenalty); + } + + // We applied the maximum possible vector bonus at the beginning. Now, + // subtract the excess bonus, if any, from the Threshold before + // comparing against Cost. + if (NumVectorInstructions <= NumInstructions / 10) + Threshold -= VectorBonus; + else if (NumVectorInstructions <= NumInstructions / 2) + Threshold -= VectorBonus / 2; + + return Cost < std::max(1, Threshold); + } + bool shouldStop() override { + // Bail out the moment we cross the threshold. This means we'll under-count + // the cost, but only when undercounting doesn't matter. + return Cost >= Threshold && !ComputeFullInlineCost; + } + + void onLoadEliminationOpportunity() override { + LoadEliminationCost += InlineConstants::InstrCost; + } + + InlineResult onAnalysisStart() override { + // Perform some tweaks to the cost and threshold based on the direct + // callsite information. + + // We want to more aggressively inline vector-dense kernels, so up the + // threshold, and we'll lower it if the % of vector instructions gets too + // low. Note that these bonuses are some what arbitrary and evolved over + // time by accident as much as because they are principled bonuses. + // + // FIXME: It would be nice to remove all such bonuses. At least it would be + // nice to base the bonus values on something more scientific. + assert(NumInstructions == 0); + assert(NumVectorInstructions == 0); + + // Update the threshold based on callsite properties + updateThreshold(CandidateCall, F); + + // While Threshold depends on commandline options that can take negative + // values, we want to enforce the invariant that the computed threshold and + // bonuses are non-negative. + assert(Threshold >= 0); + assert(SingleBBBonus >= 0); + assert(VectorBonus >= 0); + + // Speculatively apply all possible bonuses to Threshold. If cost exceeds + // this Threshold any time, and cost cannot decrease, we can stop processing + // the rest of the function body. + Threshold += (SingleBBBonus + VectorBonus); + + // Give out bonuses for the callsite, as the instructions setting them up + // will be gone after inlining. + addCost(-getCallsiteCost(this->CandidateCall, DL)); + + // If this function uses the coldcc calling convention, prefer not to inline + // it. + if (F.getCallingConv() == CallingConv::Cold) + Cost += InlineConstants::ColdccPenalty; + + // Check if we're done. This can happen due to bonuses and penalties. + if (Cost >= Threshold && !ComputeFullInlineCost) + return "high cost"; + + return true; + } + +public: + InlineCostCallAnalyzer( + const TargetTransformInfo &TTI, + std::function<AssumptionCache &(Function &)> &GetAssumptionCache, + Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI, + ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE, Function &Callee, + CallBase &Call, const InlineParams &Params, bool BoostIndirect = true) + : CallAnalyzer(TTI, GetAssumptionCache, GetBFI, PSI, ORE, Callee, Call), + ComputeFullInlineCost(OptComputeFullInlineCost || + Params.ComputeFullInlineCost || ORE), + Params(Params), Threshold(Params.DefaultThreshold), + BoostIndirectCalls(BoostIndirect) {} void dump(); -}; + virtual ~InlineCostCallAnalyzer() {} + int getThreshold() { return Threshold; } + int getCost() { return Cost; } +}; } // namespace /// Test whether the given value is an Alloca-derived function argument. @@ -328,55 +648,21 @@ bool CallAnalyzer::isAllocaDerivedArg(Value *V) { return SROAArgValues.count(V); } -/// Lookup the SROA-candidate argument and cost iterator which V maps to. -/// Returns false if V does not map to a SROA-candidate. -bool CallAnalyzer::lookupSROAArgAndCost( - Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) { - if (SROAArgValues.empty() || SROAArgCosts.empty()) - return false; - - DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V); - if (ArgIt == SROAArgValues.end()) - return false; - - Arg = ArgIt->second; - CostIt = SROAArgCosts.find(Arg); - return CostIt != SROAArgCosts.end(); -} - -/// Disable SROA for the candidate marked by this cost iterator. -/// -/// This marks the candidate as no longer viable for SROA, and adds the cost -/// savings associated with it back into the inline cost measurement. -void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) { - // If we're no longer able to perform SROA we need to undo its cost savings - // and prevent subsequent analysis. - addCost(CostIt->second); - SROACostSavings -= CostIt->second; - SROACostSavingsLost += CostIt->second; - SROAArgCosts.erase(CostIt); +void CallAnalyzer::disableSROAForArg(AllocaInst *SROAArg) { + onDisableSROA(SROAArg); + EnabledSROAArgValues.erase(SROAArg); disableLoadElimination(); } - /// If 'V' maps to a SROA candidate, disable SROA for it. void CallAnalyzer::disableSROA(Value *V) { - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(V, SROAArg, CostIt)) - disableSROA(CostIt); -} - -/// Accumulate the given cost for a particular SROA candidate. -void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, - int InstructionCost) { - CostIt->second += InstructionCost; - SROACostSavings += InstructionCost; + if (auto *SROAArg = getSROAArgForValueOrNull(V)) { + disableSROAForArg(SROAArg); + } } void CallAnalyzer::disableLoadElimination() { if (EnableLoadElimination) { - addCost(LoadEliminationCost); - LoadEliminationCost = 0; + onDisableLoadElimination(); EnableLoadElimination = false; } } @@ -422,9 +708,9 @@ bool CallAnalyzer::isGEPFree(GetElementPtrInst &GEP) { Operands.push_back(GEP.getOperand(0)); for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I) if (Constant *SimpleOp = SimplifiedValues.lookup(*I)) - Operands.push_back(SimpleOp); - else - Operands.push_back(*I); + Operands.push_back(SimpleOp); + else + Operands.push_back(*I); return TargetTransformInfo::TCC_Free == TTI.getUserCost(&GEP, Operands); } @@ -445,8 +731,8 @@ bool CallAnalyzer::visitAlloca(AllocaInst &I) { // Accumulate the allocated size. if (I.isStaticAlloca()) { Type *Ty = I.getAllocatedType(); - AllocatedSize = SaturatingAdd(DL.getTypeAllocSize(Ty).getFixedSize(), - AllocatedSize); + AllocatedSize = + SaturatingAdd(DL.getTypeAllocSize(Ty).getFixedSize(), AllocatedSize); } // We will happily inline static alloca instructions. @@ -548,9 +834,7 @@ bool CallAnalyzer::visitPHI(PHINode &I) { if (FirstBaseAndOffset.first) { ConstantOffsetPtrs[&I] = FirstBaseAndOffset; - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(FirstV, SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(FirstV)) SROAArgValues[&I] = SROAArg; } @@ -580,10 +864,7 @@ bool CallAnalyzer::canFoldInboundsGEP(GetElementPtrInst &I) { } bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - bool SROACandidate = - lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt); + auto *SROAArg = getSROAArgForValueOrNull(I.getPointerOperand()); // Lambda to check whether a GEP's indices are all constant. auto IsGEPOffsetConstant = [&](GetElementPtrInst &GEP) { @@ -594,7 +875,7 @@ bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { }; if ((I.isInBounds() && canFoldInboundsGEP(I)) || IsGEPOffsetConstant(I)) { - if (SROACandidate) + if (SROAArg) SROAArgValues[&I] = SROAArg; // Constant GEPs are modeled as free. @@ -602,8 +883,8 @@ bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { } // Variable GEPs will require math and will disable SROA. - if (SROACandidate) - disableSROA(CostIt); + if (SROAArg) + disableSROAForArg(SROAArg); return isGEPFree(I); } @@ -643,9 +924,7 @@ bool CallAnalyzer::visitBitCast(BitCastInst &I) { ConstantOffsetPtrs[&I] = BaseAndOffset; // Also look for SROA candidates here. - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(I.getOperand(0))) SROAArgValues[&I] = SROAArg; // Bitcasts are always zero cost. @@ -677,9 +956,7 @@ bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) { // and so we can just add the integer in here. The only places where SROA is // preserved either cannot fire on an integer, or won't in-and-of themselves // disable SROA (ext) w/o some later use that we would see and disable. - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(I.getOperand(0))) SROAArgValues[&I] = SROAArg; return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); @@ -703,9 +980,7 @@ bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { } // "Propagate" SROA here in the same manner as we do for ptrtoint above. - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(Op, SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(Op)) SROAArgValues[&I] = SROAArg; return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); @@ -732,7 +1007,7 @@ bool CallAnalyzer::visitCastInst(CastInst &I) { case Instruction::FPToUI: case Instruction::FPToSI: if (TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive) - addCost(InlineConstants::CallPenalty); + onCallPenalty(); break; default: break; @@ -805,8 +1080,8 @@ bool CallAnalyzer::allowSizeGrowth(CallBase &Call) { return true; } -bool CallAnalyzer::isColdCallSite(CallBase &Call, - BlockFrequencyInfo *CallerBFI) { +bool InlineCostCallAnalyzer::isColdCallSite(CallBase &Call, + BlockFrequencyInfo *CallerBFI) { // If global profile summary is available, then callsite's coldness is // determined based on that. if (PSI && PSI->hasProfileSummary()) @@ -829,8 +1104,8 @@ bool CallAnalyzer::isColdCallSite(CallBase &Call, } Optional<int> -CallAnalyzer::getHotCallSiteThreshold(CallBase &Call, - BlockFrequencyInfo *CallerBFI) { +InlineCostCallAnalyzer::getHotCallSiteThreshold(CallBase &Call, + BlockFrequencyInfo *CallerBFI) { // If global profile summary is available, then callsite's hotness is // determined based on that. @@ -857,7 +1132,7 @@ CallAnalyzer::getHotCallSiteThreshold(CallBase &Call, return None; } -void CallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) { +void InlineCostCallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) { // If no size growth is allowed for this inlining, set Threshold to 0. if (!allowSizeGrowth(Call)) { Threshold = 0; @@ -1019,19 +1294,7 @@ bool CallAnalyzer::visitCmpInst(CmpInst &I) { : ConstantInt::getFalse(I.getType()); return true; } - // Finally check for SROA candidates in comparisons. - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { - if (isa<ConstantPointerNull>(I.getOperand(1))) { - accumulateSROACost(CostIt, InlineConstants::InstrCost); - return true; - } - - disableSROA(CostIt); - } - - return false; + return handleSROA(I.getOperand(0), isa<ConstantPointerNull>(I.getOperand(1))); } bool CallAnalyzer::visitSub(BinaryOperator &I) { @@ -1072,8 +1335,8 @@ bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { Value *SimpleV = nullptr; if (auto FI = dyn_cast<FPMathOperator>(&I)) - SimpleV = SimplifyBinOp(I.getOpcode(), CLHS ? CLHS : LHS, - CRHS ? CRHS : RHS, FI->getFastMathFlags(), DL); + SimpleV = SimplifyBinOp(I.getOpcode(), CLHS ? CLHS : LHS, CRHS ? CRHS : RHS, + FI->getFastMathFlags(), DL); else SimpleV = SimplifyBinOp(I.getOpcode(), CLHS ? CLHS : LHS, CRHS ? CRHS : RHS, DL); @@ -1095,7 +1358,7 @@ bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { if (I.getType()->isFloatingPointTy() && TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive && !match(&I, m_FNeg(m_Value()))) - addCost(InlineConstants::CallPenalty); + onCallPenalty(); return false; } @@ -1106,9 +1369,8 @@ bool CallAnalyzer::visitFNeg(UnaryOperator &I) { if (!COp) COp = SimplifiedValues.lookup(Op); - Value *SimpleV = SimplifyFNegInst(COp ? COp : Op, - cast<FPMathOperator>(I).getFastMathFlags(), - DL); + Value *SimpleV = SimplifyFNegInst( + COp ? COp : Op, cast<FPMathOperator>(I).getFastMathFlags(), DL); if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) SimplifiedValues[&I] = C; @@ -1123,23 +1385,15 @@ bool CallAnalyzer::visitFNeg(UnaryOperator &I) { } bool CallAnalyzer::visitLoad(LoadInst &I) { - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) { - if (I.isSimple()) { - accumulateSROACost(CostIt, InlineConstants::InstrCost); - return true; - } - - disableSROA(CostIt); - } + if (handleSROA(I.getPointerOperand(), I.isSimple())) + return true; // If the data is already loaded from this address and hasn't been clobbered // by any stores or calls, this load is likely to be redundant and can be // eliminated. if (EnableLoadElimination && !LoadAddrSet.insert(I.getPointerOperand()).second && I.isUnordered()) { - LoadEliminationCost += InlineConstants::InstrCost; + onLoadEliminationOpportunity(); return true; } @@ -1147,16 +1401,8 @@ bool CallAnalyzer::visitLoad(LoadInst &I) { } bool CallAnalyzer::visitStore(StoreInst &I) { - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) { - if (I.isSimple()) { - accumulateSROACost(CostIt, InlineConstants::InstrCost); - return true; - } - - disableSROA(CostIt); - } + if (handleSROA(I.getPointerOperand(), I.isSimple())) + return true; // The store can potentially clobber loads and prevent repeated loads from // being eliminated. @@ -1238,97 +1484,69 @@ bool CallAnalyzer::visitCallBase(CallBase &Call) { if (isa<CallInst>(Call) && cast<CallInst>(Call).cannotDuplicate()) ContainsNoDuplicateCall = true; - if (Function *F = Call.getCalledFunction()) { - // When we have a concrete function, first try to simplify it directly. - if (simplifyCallSite(F, Call)) - return true; - - // Next check if it is an intrinsic we know about. - // FIXME: Lift this into part of the InstVisitor. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Call)) { - switch (II->getIntrinsicID()) { - default: - if (!Call.onlyReadsMemory() && !isAssumeLikeIntrinsic(II)) - disableLoadElimination(); - return Base::visitCallBase(Call); - - case Intrinsic::load_relative: - // This is normally lowered to 4 LLVM instructions. - addCost(3 * InlineConstants::InstrCost); - return false; - - case Intrinsic::memset: - case Intrinsic::memcpy: - case Intrinsic::memmove: + Value *Callee = Call.getCalledOperand(); + Function *F = dyn_cast_or_null<Function>(Callee); + bool IsIndirectCall = !F; + if (IsIndirectCall) { + // Check if this happens to be an indirect function call to a known function + // in this inline context. If not, we've done all we can. + F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee)); + if (!F) { + onCallArgumentSetup(Call); + + if (!Call.onlyReadsMemory()) disableLoadElimination(); - // SROA can usually chew through these intrinsics, but they aren't free. - return false; - case Intrinsic::icall_branch_funnel: - case Intrinsic::localescape: - HasUninlineableIntrinsic = true; - return false; - case Intrinsic::vastart: - InitsVargArgs = true; - return false; - } + return Base::visitCallBase(Call); } + } - if (F == Call.getFunction()) { - // This flag will fully abort the analysis, so don't bother with anything - // else. - IsRecursiveCall = true; - return false; - } + assert(F && "Expected a call to a known function"); - if (TTI.isLoweredToCall(F)) { - // We account for the average 1 instruction per call argument setup - // here. - addCost(Call.arg_size() * InlineConstants::InstrCost); + // When we have a concrete function, first try to simplify it directly. + if (simplifyCallSite(F, Call)) + return true; - // Everything other than inline ASM will also have a significant cost - // merely from making the call. - if (!isa<InlineAsm>(Call.getCalledValue())) - addCost(InlineConstants::CallPenalty); - } + // Next check if it is an intrinsic we know about. + // FIXME: Lift this into part of the InstVisitor. + if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Call)) { + switch (II->getIntrinsicID()) { + default: + if (!Call.onlyReadsMemory() && !isAssumeLikeIntrinsic(II)) + disableLoadElimination(); + return Base::visitCallBase(Call); + + case Intrinsic::load_relative: + onLoadRelativeIntrinsic(); + return false; - if (!Call.onlyReadsMemory()) + case Intrinsic::memset: + case Intrinsic::memcpy: + case Intrinsic::memmove: disableLoadElimination(); - return Base::visitCallBase(Call); + // SROA can usually chew through these intrinsics, but they aren't free. + return false; + case Intrinsic::icall_branch_funnel: + case Intrinsic::localescape: + HasUninlineableIntrinsic = true; + return false; + case Intrinsic::vastart: + InitsVargArgs = true; + return false; + } } - // Otherwise we're in a very special case -- an indirect function call. See - // if we can be particularly clever about this. - Value *Callee = Call.getCalledValue(); - - // First, pay the price of the argument setup. We account for the average - // 1 instruction per call argument setup here. - addCost(Call.arg_size() * InlineConstants::InstrCost); - - // Next, check if this happens to be an indirect function call to a known - // function in this inline context. If not, we've done all we can. - Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee)); - if (!F) { - if (!Call.onlyReadsMemory()) - disableLoadElimination(); - return Base::visitCallBase(Call); + if (F == Call.getFunction()) { + // This flag will fully abort the analysis, so don't bother with anything + // else. + IsRecursiveCall = true; + return false; } - // If we have a constant that we are calling as a function, we can peer - // through it and see the function target. This happens not infrequently - // during devirtualization and so we want to give it a hefty bonus for - // inlining, but cap that bonus in the event that inlining wouldn't pan - // out. Pretend to inline the function, with a custom threshold. - auto IndirectCallParams = Params; - IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold; - CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, Call, - IndirectCallParams); - if (CA.analyzeCall(Call)) { - // We were able to inline the indirect call! Subtract the cost from the - // threshold to get the bonus we want to apply, but don't go below zero. - Cost -= std::max(0, CA.getThreshold() - CA.getCost()); + if (TTI.isLoweredToCall(F)) { + onLoweredCall(F, Call, IsIndirectCall); } - if (!F->onlyReadsMemory()) + if (!(Call.onlyReadsMemory() || (IsIndirectCall && F->onlyReadsMemory()))) disableLoadElimination(); return Base::visitCallBase(Call); } @@ -1381,9 +1599,7 @@ bool CallAnalyzer::visitSelectInst(SelectInst &SI) { if (TrueBaseAndOffset == FalseBaseAndOffset && TrueBaseAndOffset.first) { ConstantOffsetPtrs[&SI] = TrueBaseAndOffset; - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(TrueVal, SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(TrueVal)) SROAArgValues[&SI] = SROAArg; return true; } @@ -1422,9 +1638,7 @@ bool CallAnalyzer::visitSelectInst(SelectInst &SI) { if (BaseAndOffset.first) { ConstantOffsetPtrs[&SI] = BaseAndOffset; - Value *SROAArg; - DenseMap<Value *, int>::iterator CostIt; - if (lookupSROAArgAndCost(SelectedV, SROAArg, CostIt)) + if (auto *SROAArg = getSROAArgForValueOrNull(SelectedV)) SROAArgValues[&SI] = SROAArg; } @@ -1452,49 +1666,12 @@ bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) { // inlining those. It will prevent inlining in cases where the optimization // does not (yet) fire. - // Maximum valid cost increased in this function. - int CostUpperBound = INT_MAX - InlineConstants::InstrCost - 1; - unsigned JumpTableSize = 0; + BlockFrequencyInfo *BFI = GetBFI ? &((*GetBFI)(F)) : nullptr; unsigned NumCaseCluster = - TTI.getEstimatedNumberOfCaseClusters(SI, JumpTableSize); + TTI.getEstimatedNumberOfCaseClusters(SI, JumpTableSize, PSI, BFI); - // If suitable for a jump table, consider the cost for the table size and - // branch to destination. - if (JumpTableSize) { - int64_t JTCost = (int64_t)JumpTableSize * InlineConstants::InstrCost + - 4 * InlineConstants::InstrCost; - - addCost(JTCost, (int64_t)CostUpperBound); - return false; - } - - // Considering forming a binary search, we should find the number of nodes - // which is same as the number of comparisons when lowered. For a given - // number of clusters, n, we can define a recursive function, f(n), to find - // the number of nodes in the tree. The recursion is : - // f(n) = 1 + f(n/2) + f (n - n/2), when n > 3, - // and f(n) = n, when n <= 3. - // This will lead a binary tree where the leaf should be either f(2) or f(3) - // when n > 3. So, the number of comparisons from leaves should be n, while - // the number of non-leaf should be : - // 2^(log2(n) - 1) - 1 - // = 2^log2(n) * 2^-1 - 1 - // = n / 2 - 1. - // Considering comparisons from leaf and non-leaf nodes, we can estimate the - // number of comparisons in a simple closed form : - // n + n / 2 - 1 = n * 3 / 2 - 1 - if (NumCaseCluster <= 3) { - // Suppose a comparison includes one compare and one conditional branch. - addCost(NumCaseCluster * 2 * InlineConstants::InstrCost); - return false; - } - - int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1; - int64_t SwitchCost = - ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost; - - addCost(SwitchCost, (int64_t)CostUpperBound); + onFinalizeSwitch(JumpTableSize, NumCaseCluster); return false; } @@ -1587,7 +1764,7 @@ CallAnalyzer::analyzeBlock(BasicBlock *BB, if (Base::visit(&*I)) ++NumInstructionsSimplified; else - addCost(InlineConstants::InstrCost); + onCommonInstructionSimplification(); using namespace ore; // If the visit this instruction detected an uninlinable pattern, abort. @@ -1632,9 +1809,7 @@ CallAnalyzer::analyzeBlock(BasicBlock *BB, return IR; } - // Check if we've passed the maximum possible threshold so we don't spin in - // huge basic blocks that will never inline. - if (Cost >= Threshold && !ComputeFullInlineCost) + if (shouldStop()) return false; } @@ -1676,8 +1851,8 @@ ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) { assert(V->getType()->isPointerTy() && "Unexpected operand type!"); } while (Visited.insert(V).second); - Type *IntPtrTy = DL.getIntPtrType(V->getContext(), AS); - return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset)); + Type *IdxPtrTy = DL.getIndexType(V->getType()); + return cast<ConstantInt>(ConstantInt::get(IdxPtrTy, Offset)); } /// Find dead blocks due to deleted CFG edges during inlining. @@ -1725,54 +1900,17 @@ void CallAnalyzer::findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB) { /// factors and heuristics. If this method returns false but the computed cost /// is below the computed threshold, then inlining was forcibly disabled by /// some artifact of the routine. -InlineResult CallAnalyzer::analyzeCall(CallBase &Call) { +InlineResult CallAnalyzer::analyze() { ++NumCallsAnalyzed; - // Perform some tweaks to the cost and threshold based on the direct - // callsite information. - - // We want to more aggressively inline vector-dense kernels, so up the - // threshold, and we'll lower it if the % of vector instructions gets too - // low. Note that these bonuses are some what arbitrary and evolved over time - // by accident as much as because they are principled bonuses. - // - // FIXME: It would be nice to remove all such bonuses. At least it would be - // nice to base the bonus values on something more scientific. - assert(NumInstructions == 0); - assert(NumVectorInstructions == 0); - - // Update the threshold based on callsite properties - updateThreshold(Call, F); - - // While Threshold depends on commandline options that can take negative - // values, we want to enforce the invariant that the computed threshold and - // bonuses are non-negative. - assert(Threshold >= 0); - assert(SingleBBBonus >= 0); - assert(VectorBonus >= 0); - - // Speculatively apply all possible bonuses to Threshold. If cost exceeds - // this Threshold any time, and cost cannot decrease, we can stop processing - // the rest of the function body. - Threshold += (SingleBBBonus + VectorBonus); - - // Give out bonuses for the callsite, as the instructions setting them up - // will be gone after inlining. - addCost(-getCallsiteCost(Call, DL)); - - // If this function uses the coldcc calling convention, prefer not to inline - // it. - if (F.getCallingConv() == CallingConv::Cold) - Cost += InlineConstants::ColdccPenalty; - - // Check if we're done. This can happen due to bonuses and penalties. - if (Cost >= Threshold && !ComputeFullInlineCost) - return "high cost"; + auto Result = onAnalysisStart(); + if (!Result) + return Result; if (F.empty()) return true; - Function *Caller = Call.getFunction(); + Function *Caller = CandidateCall.getFunction(); // Check if the caller function is recursive itself. for (User *U : Caller->users()) { CallBase *Call = dyn_cast<CallBase>(U); @@ -1784,10 +1922,10 @@ InlineResult CallAnalyzer::analyzeCall(CallBase &Call) { // Populate our simplified values by mapping from function arguments to call // arguments with known important simplifications. - auto CAI = Call.arg_begin(); + auto CAI = CandidateCall.arg_begin(); for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end(); FAI != FAE; ++FAI, ++CAI) { - assert(CAI != Call.arg_end()); + assert(CAI != CandidateCall.arg_end()); if (Constant *C = dyn_cast<Constant>(CAI)) SimplifiedValues[&*FAI] = C; @@ -1796,9 +1934,9 @@ InlineResult CallAnalyzer::analyzeCall(CallBase &Call) { ConstantOffsetPtrs[&*FAI] = std::make_pair(PtrArg, C->getValue()); // We can SROA any pointer arguments derived from alloca instructions. - if (isa<AllocaInst>(PtrArg)) { - SROAArgValues[&*FAI] = PtrArg; - SROAArgCosts[PtrArg] = 0; + if (auto *SROAArg = dyn_cast<AllocaInst>(PtrArg)) { + SROAArgValues[&*FAI] = SROAArg; + onInitializeSROAArg(SROAArg); } } } @@ -1824,12 +1962,10 @@ InlineResult CallAnalyzer::analyzeCall(CallBase &Call) { BBSetVector; BBSetVector BBWorklist; BBWorklist.insert(&F.getEntryBlock()); - bool SingleBB = true; + // Note that we *must not* cache the size, this loop grows the worklist. for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) { - // Bail out the moment we cross the threshold. This means we'll under-count - // the cost, but only when undercounting doesn't matter. - if (Cost >= Threshold && !ComputeFullInlineCost) + if (shouldStop()) break; BasicBlock *BB = BBWorklist[Idx]; @@ -1889,57 +2025,23 @@ InlineResult CallAnalyzer::analyzeCall(CallBase &Call) { ++TIdx) BBWorklist.insert(TI->getSuccessor(TIdx)); - // If we had any successors at this point, than post-inlining is likely to - // have them as well. Note that we assume any basic blocks which existed - // due to branches or switches which folded above will also fold after - // inlining. - if (SingleBB && TI->getNumSuccessors() > 1) { - // Take off the bonus we applied to the threshold. - Threshold -= SingleBBBonus; - SingleBB = false; - } + onBlockAnalyzed(BB); } - bool OnlyOneCallAndLocalLinkage = - F.hasLocalLinkage() && F.hasOneUse() && &F == Call.getCalledFunction(); + bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() && + &F == CandidateCall.getCalledFunction(); // If this is a noduplicate call, we can still inline as long as // inlining this would cause the removal of the caller (so the instruction // is not actually duplicated, just moved). if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall) return "noduplicate"; - // Loops generally act a lot like calls in that they act like barriers to - // movement, require a certain amount of setup, etc. So when optimising for - // size, we penalise any call sites that perform loops. We do this after all - // other costs here, so will likely only be dealing with relatively small - // functions (and hence DT and LI will hopefully be cheap). - if (Caller->hasMinSize()) { - DominatorTree DT(F); - LoopInfo LI(DT); - int NumLoops = 0; - for (Loop *L : LI) { - // Ignore loops that will not be executed - if (DeadBlocks.count(L->getHeader())) - continue; - NumLoops++; - } - addCost(NumLoops * InlineConstants::CallPenalty); - } - - // We applied the maximum possible vector bonus at the beginning. Now, - // subtract the excess bonus, if any, from the Threshold before - // comparing against Cost. - if (NumVectorInstructions <= NumInstructions / 10) - Threshold -= VectorBonus; - else if (NumVectorInstructions <= NumInstructions / 2) - Threshold -= VectorBonus/2; - - return Cost < std::max(1, Threshold); + return finalizeAnalysis(); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// Dump stats about this call's analysis. -LLVM_DUMP_METHOD void CallAnalyzer::dump() { +LLVM_DUMP_METHOD void InlineCostCallAnalyzer::dump() { #define DEBUG_PRINT_STAT(x) dbgs() << " " #x ": " << x << "\n" DEBUG_PRINT_STAT(NumConstantArgs); DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs); @@ -2073,9 +2175,9 @@ InlineCost llvm::getInlineCost( LLVM_DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() << "... (caller:" << Caller->getName() << ")\n"); - CallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, ORE, *Callee, - Call, Params); - InlineResult ShouldInline = CA.analyzeCall(Call); + InlineCostCallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, ORE, + *Callee, Call, Params); + InlineResult ShouldInline = CA.analyze(); LLVM_DEBUG(CA.dump()); @@ -2121,16 +2223,17 @@ InlineResult llvm::isInlineViable(Function &F) { switch (Call->getCalledFunction()->getIntrinsicID()) { default: break; - // Disallow inlining of @llvm.icall.branch.funnel because current - // backend can't separate call targets from call arguments. case llvm::Intrinsic::icall_branch_funnel: + // Disallow inlining of @llvm.icall.branch.funnel because current + // backend can't separate call targets from call arguments. return "disallowed inlining of @llvm.icall.branch.funnel"; - // Disallow inlining functions that call @llvm.localescape. Doing this - // correctly would require major changes to the inliner. case llvm::Intrinsic::localescape: + // Disallow inlining functions that call @llvm.localescape. Doing this + // correctly would require major changes to the inliner. return "disallowed inlining of @llvm.localescape"; - // Disallow inlining of functions that initialize VarArgs with va_start. case llvm::Intrinsic::vastart: + // Disallow inlining of functions that initialize VarArgs with + // va_start. return "contains VarArgs initialized with va_start"; } } @@ -2173,7 +2276,8 @@ InlineParams llvm::getInlineParams(int Threshold) { if (LocallyHotCallSiteThreshold.getNumOccurrences() > 0) Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold; - // Set the ColdCallSiteThreshold knob from the -inline-cold-callsite-threshold. + // Set the ColdCallSiteThreshold knob from the + // -inline-cold-callsite-threshold. Params.ColdCallSiteThreshold = ColdCallSiteThreshold; // Set the OptMinSizeThreshold and OptSizeThreshold params only if the diff --git a/llvm/lib/Analysis/InstCount.cpp b/llvm/lib/Analysis/InstCount.cpp index 943a99a5f46de..bb9c7b7eb11fe 100644 --- a/llvm/lib/Analysis/InstCount.cpp +++ b/llvm/lib/Analysis/InstCount.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstVisitor.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" diff --git a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp index 35190ce3e11a2..415797d6a3783 100644 --- a/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp +++ b/llvm/lib/Analysis/InstructionPrecedenceTracking.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/InstructionPrecedenceTracking.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/Support/CommandLine.h" using namespace llvm; diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index cb8987721700b..d7510c8991013 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -137,6 +137,71 @@ static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, CRHS == LHS; } +/// Simplify comparison with true or false branch of select: +/// %sel = select i1 %cond, i32 %tv, i32 %fv +/// %cmp = icmp sle i32 %sel, %rhs +/// Compose new comparison by substituting %sel with either %tv or %fv +/// and see if it simplifies. +static Value *simplifyCmpSelCase(CmpInst::Predicate Pred, Value *LHS, + Value *RHS, Value *Cond, + const SimplifyQuery &Q, unsigned MaxRecurse, + Constant *TrueOrFalse) { + Value *SimplifiedCmp = SimplifyCmpInst(Pred, LHS, RHS, Q, MaxRecurse); + if (SimplifiedCmp == Cond) { + // %cmp simplified to the select condition (%cond). + return TrueOrFalse; + } else if (!SimplifiedCmp && isSameCompare(Cond, Pred, LHS, RHS)) { + // It didn't simplify. However, if composed comparison is equivalent + // to the select condition (%cond) then we can replace it. + return TrueOrFalse; + } + return SimplifiedCmp; +} + +/// Simplify comparison with true branch of select +static Value *simplifyCmpSelTrueCase(CmpInst::Predicate Pred, Value *LHS, + Value *RHS, Value *Cond, + const SimplifyQuery &Q, + unsigned MaxRecurse) { + return simplifyCmpSelCase(Pred, LHS, RHS, Cond, Q, MaxRecurse, + getTrue(Cond->getType())); +} + +/// Simplify comparison with false branch of select +static Value *simplifyCmpSelFalseCase(CmpInst::Predicate Pred, Value *LHS, + Value *RHS, Value *Cond, + const SimplifyQuery &Q, + unsigned MaxRecurse) { + return simplifyCmpSelCase(Pred, LHS, RHS, Cond, Q, MaxRecurse, + getFalse(Cond->getType())); +} + +/// We know comparison with both branches of select can be simplified, but they +/// are not equal. This routine handles some logical simplifications. +static Value *handleOtherCmpSelSimplifications(Value *TCmp, Value *FCmp, + Value *Cond, + const SimplifyQuery &Q, + unsigned MaxRecurse) { + // If the false value simplified to false, then the result of the compare + // is equal to "Cond && TCmp". This also catches the case when the false + // value simplified to false and the true value to true, returning "Cond". + if (match(FCmp, m_Zero())) + if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) + return V; + // If the true value simplified to true, then the result of the compare + // is equal to "Cond || FCmp". + if (match(TCmp, m_One())) + if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) + return V; + // Finally, if the false value simplified to true and the true value to + // false, then the result of the compare is equal to "!Cond". + if (match(FCmp, m_One()) && match(TCmp, m_Zero())) + if (Value *V = SimplifyXorInst( + Cond, Constant::getAllOnesValue(Cond->getType()), Q, MaxRecurse)) + return V; + return nullptr; +} + /// Does the given value dominate the specified phi node? static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { Instruction *I = dyn_cast<Instruction>(V); @@ -398,6 +463,12 @@ static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS, /// In the case of a comparison with a select instruction, try to simplify the /// comparison by seeing whether both branches of the select result in the same /// value. Returns the common value if so, otherwise returns null. +/// For example, if we have: +/// %tmp = select i1 %cmp, i32 1, i32 2 +/// %cmp1 = icmp sle i32 %tmp, 3 +/// We can simplify %cmp1 to true, because both branches of select are +/// less than 3. We compose new comparison by substituting %tmp with both +/// branches of select and see if it can be simplified. static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q, unsigned MaxRecurse) { @@ -418,32 +489,14 @@ static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. // Does "cmp TV, RHS" simplify? - Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); - if (TCmp == Cond) { - // It not only simplified, it simplified to the select condition. Replace - // it with 'true'. - TCmp = getTrue(Cond->getType()); - } else if (!TCmp) { - // It didn't simplify. However if "cmp TV, RHS" is equal to the select - // condition then we can replace it with 'true'. Otherwise give up. - if (!isSameCompare(Cond, Pred, TV, RHS)) - return nullptr; - TCmp = getTrue(Cond->getType()); - } + Value *TCmp = simplifyCmpSelTrueCase(Pred, TV, RHS, Cond, Q, MaxRecurse); + if (!TCmp) + return nullptr; // Does "cmp FV, RHS" simplify? - Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); - if (FCmp == Cond) { - // It not only simplified, it simplified to the select condition. Replace - // it with 'false'. - FCmp = getFalse(Cond->getType()); - } else if (!FCmp) { - // It didn't simplify. However if "cmp FV, RHS" is equal to the select - // condition then we can replace it with 'false'. Otherwise give up. - if (!isSameCompare(Cond, Pred, FV, RHS)) - return nullptr; - FCmp = getFalse(Cond->getType()); - } + Value *FCmp = simplifyCmpSelFalseCase(Pred, FV, RHS, Cond, Q, MaxRecurse); + if (!FCmp) + return nullptr; // If both sides simplified to the same value, then use it as the result of // the original comparison. @@ -452,26 +505,8 @@ static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, // The remaining cases only make sense if the select condition has the same // type as the result of the comparison, so bail out if this is not so. - if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) - return nullptr; - // If the false value simplified to false, then the result of the compare - // is equal to "Cond && TCmp". This also catches the case when the false - // value simplified to false and the true value to true, returning "Cond". - if (match(FCmp, m_Zero())) - if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) - return V; - // If the true value simplified to true, then the result of the compare - // is equal to "Cond || FCmp". - if (match(TCmp, m_One())) - if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) - return V; - // Finally, if the false value simplified to true and the true value to - // false, then the result of the compare is equal to "!Cond". - if (match(FCmp, m_One()) && match(TCmp, m_Zero())) - if (Value *V = - SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), - Q, MaxRecurse)) - return V; + if (Cond->getType()->isVectorTy() == RHS->getType()->isVectorTy()) + return handleOtherCmpSelSimplifications(TCmp, FCmp, Cond, Q, MaxRecurse); return nullptr; } @@ -543,10 +578,16 @@ static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, // Evaluate the BinOp on the incoming phi values. Value *CommonValue = nullptr; - for (Value *Incoming : PI->incoming_values()) { + for (unsigned u = 0, e = PI->getNumIncomingValues(); u < e; ++u) { + Value *Incoming = PI->getIncomingValue(u); + Instruction *InTI = PI->getIncomingBlock(u)->getTerminator(); // If the incoming value is the phi node itself, it can safely be skipped. if (Incoming == PI) continue; - Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); + // Change the context instruction to the "edge" that flows into the phi. + // This is important because that is where incoming is actually "evaluated" + // even though it is used later somewhere else. + Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q.getWithInstruction(InTI), + MaxRecurse); // If the operation failed to simplify, or simplified to a different value // to previously, then give up. if (!V || (CommonValue && V != CommonValue)) @@ -656,16 +697,16 @@ static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V, bool AllowNonInbounds = false) { assert(V->getType()->isPtrOrPtrVectorTy()); - Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); - APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); + Type *IntIdxTy = DL.getIndexType(V->getType())->getScalarType(); + APInt Offset = APInt::getNullValue(IntIdxTy->getIntegerBitWidth()); V = V->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds); // As that strip may trace through `addrspacecast`, need to sext or trunc // the offset calculated. - IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType(); - Offset = Offset.sextOrTrunc(IntPtrTy->getIntegerBitWidth()); + IntIdxTy = DL.getIndexType(V->getType())->getScalarType(); + Offset = Offset.sextOrTrunc(IntIdxTy->getIntegerBitWidth()); - Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); + Constant *OffsetIntPtr = ConstantInt::get(IntIdxTy, Offset); if (V->getType()->isVectorTy()) return ConstantVector::getSplat(V->getType()->getVectorNumElements(), OffsetIntPtr); @@ -3903,18 +3944,21 @@ static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal, /// Try to simplify a select instruction when its condition operand is a /// floating-point comparison. -static Value *simplifySelectWithFCmp(Value *Cond, Value *T, Value *F) { +static Value *simplifySelectWithFCmp(Value *Cond, Value *T, Value *F, + const SimplifyQuery &Q) { FCmpInst::Predicate Pred; if (!match(Cond, m_FCmp(Pred, m_Specific(T), m_Specific(F))) && !match(Cond, m_FCmp(Pred, m_Specific(F), m_Specific(T)))) return nullptr; - // TODO: The transform may not be valid with -0.0. An incomplete way of - // testing for that possibility is to check if at least one operand is a - // non-zero constant. + // This transform is safe if we do not have (do not care about) -0.0 or if + // at least one operand is known to not be -0.0. Otherwise, the select can + // change the sign of a zero operand. + bool HasNoSignedZeros = Q.CxtI && isa<FPMathOperator>(Q.CxtI) && + Q.CxtI->hasNoSignedZeros(); const APFloat *C; - if ((match(T, m_APFloat(C)) && C->isNonZero()) || - (match(F, m_APFloat(C)) && C->isNonZero())) { + if (HasNoSignedZeros || (match(T, m_APFloat(C)) && C->isNonZero()) || + (match(F, m_APFloat(C)) && C->isNonZero())) { // (T == F) ? T : F --> F // (F == T) ? T : F --> F if (Pred == FCmpInst::FCMP_OEQ) @@ -3952,6 +3996,15 @@ static Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, return FalseVal; } + // select i1 Cond, i1 true, i1 false --> i1 Cond + assert(Cond->getType()->isIntOrIntVectorTy(1) && + "Select must have bool or bool vector condition"); + assert(TrueVal->getType() == FalseVal->getType() && + "Select must have same types for true/false ops"); + if (Cond->getType() == TrueVal->getType() && + match(TrueVal, m_One()) && match(FalseVal, m_ZeroInt())) + return Cond; + // select ?, X, X -> X if (TrueVal == FalseVal) return TrueVal; @@ -3965,7 +4018,7 @@ static Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, simplifySelectWithICmpCond(Cond, TrueVal, FalseVal, Q, MaxRecurse)) return V; - if (Value *V = simplifySelectWithFCmp(Cond, TrueVal, FalseVal)) + if (Value *V = simplifySelectWithFCmp(Cond, TrueVal, FalseVal, Q)) return V; if (Value *V = foldSelectWithBinaryOp(Cond, TrueVal, FalseVal)) @@ -4023,7 +4076,7 @@ static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops, // The following transforms are only safe if the ptrtoint cast // doesn't truncate the pointers. if (Ops[1]->getType()->getScalarSizeInBits() == - Q.DL.getIndexSizeInBits(AS)) { + Q.DL.getPointerSizeInBits(AS)) { auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * { if (match(P, m_Zero())) return Constant::getNullValue(GEPTy); @@ -4408,6 +4461,30 @@ static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, ShuffleVectorInst::commuteShuffleMask(Indices, InVecNumElts); } + // A splat of an inserted scalar constant becomes a vector constant: + // shuf (inselt ?, C, IndexC), undef, <IndexC, IndexC...> --> <C, C...> + // NOTE: We may have commuted above, so analyze the updated Indices, not the + // original mask constant. + Constant *C; + ConstantInt *IndexC; + if (match(Op0, m_InsertElement(m_Value(), m_Constant(C), + m_ConstantInt(IndexC)))) { + // Match a splat shuffle mask of the insert index allowing undef elements. + int InsertIndex = IndexC->getZExtValue(); + if (all_of(Indices, [InsertIndex](int MaskElt) { + return MaskElt == InsertIndex || MaskElt == -1; + })) { + assert(isa<UndefValue>(Op1) && "Expected undef operand 1 for splat"); + + // Shuffle mask undefs become undefined constant result elements. + SmallVector<Constant *, 16> VecC(MaskNumElts, C); + for (unsigned i = 0; i != MaskNumElts; ++i) + if (Indices[i] == -1) + VecC[i] = UndefValue::get(C->getType()); + return ConstantVector::get(VecC); + } + } + // A shuffle of a splat is always the splat itself. Legal if the shuffle's // value type is same as the input vectors' type. if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0)) @@ -5083,6 +5160,16 @@ static Value *simplifyBinaryIntrinsic(Function *F, Value *Op0, Value *Op1, return Op0; } break; + case Intrinsic::copysign: + // copysign X, X --> X + if (Op0 == Op1) + return Op0; + // copysign -X, X --> X + // copysign X, -X --> -X + if (match(Op0, m_FNeg(m_Specific(Op1))) || + match(Op1, m_FNeg(m_Specific(Op0)))) + return Op1; + break; case Intrinsic::maxnum: case Intrinsic::minnum: case Intrinsic::maximum: @@ -5232,6 +5319,19 @@ Value *llvm::SimplifyCall(CallBase *Call, const SimplifyQuery &Q) { return ConstantFoldCall(Call, F, ConstantArgs, Q.TLI); } +/// Given operands for a Freeze, see if we can fold the result. +static Value *SimplifyFreezeInst(Value *Op0) { + // Use a utility function defined in ValueTracking. + if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0)) + return Op0; + // We have room for improvement. + return nullptr; +} + +Value *llvm::SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) { + return ::SimplifyFreezeInst(Op0); +} + /// See if we can compute a simplified version of this instruction. /// If not, this returns null. @@ -5374,6 +5474,9 @@ Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &SQ, Result = SimplifyCall(cast<CallInst>(I), Q); break; } + case Instruction::Freeze: + Result = SimplifyFreezeInst(I->getOperand(0), Q); + break; #define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc: #include "llvm/IR/Instruction.def" #undef HANDLE_CAST_INST diff --git a/llvm/lib/Analysis/IntervalPartition.cpp b/llvm/lib/Analysis/IntervalPartition.cpp index d12db010db6aa..23ff4fd6f85e9 100644 --- a/llvm/lib/Analysis/IntervalPartition.cpp +++ b/llvm/lib/Analysis/IntervalPartition.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/IntervalPartition.h" #include "llvm/Analysis/Interval.h" #include "llvm/Analysis/IntervalIterator.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include <cassert> #include <utility> @@ -22,6 +23,10 @@ using namespace llvm; char IntervalPartition::ID = 0; +IntervalPartition::IntervalPartition() : FunctionPass(ID) { + initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); +} + INITIALIZE_PASS(IntervalPartition, "intervals", "Interval Partition Construction", true, true) diff --git a/llvm/lib/Analysis/LazyBlockFrequencyInfo.cpp b/llvm/lib/Analysis/LazyBlockFrequencyInfo.cpp index 4397585602841..6107cacb9533d 100644 --- a/llvm/lib/Analysis/LazyBlockFrequencyInfo.cpp +++ b/llvm/lib/Analysis/LazyBlockFrequencyInfo.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/LazyBranchProbabilityInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Dominators.h" +#include "llvm/InitializePasses.h" using namespace llvm; diff --git a/llvm/lib/Analysis/LazyBranchProbabilityInfo.cpp b/llvm/lib/Analysis/LazyBranchProbabilityInfo.cpp index e727de468a0d2..83698598e1563 100644 --- a/llvm/lib/Analysis/LazyBranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/LazyBranchProbabilityInfo.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/Dominators.h" +#include "llvm/InitializePasses.h" using namespace llvm; diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 96722f32e3550..bad2de9e5f5e0 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -19,8 +19,8 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ValueLattice.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/CFG.h" #include "llvm/IR/ConstantRange.h" @@ -33,6 +33,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/ValueHandle.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/Debug.h" #include "llvm/Support/FormattedStream.h" #include "llvm/Support/raw_ostream.h" @@ -47,6 +48,9 @@ using namespace PatternMatch; static const unsigned MaxProcessedPerValue = 500; char LazyValueInfoWrapperPass::ID = 0; +LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) { + initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry()); +} INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) @@ -432,6 +436,8 @@ namespace { BasicBlock *BB); bool solveBlockValueOverflowIntrinsic( ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB); + bool solveBlockValueSaturatingIntrinsic(ValueLatticeElement &BBLV, + SaturatingInst *SI, BasicBlock *BB); bool solveBlockValueIntrinsic(ValueLatticeElement &BBLV, IntrinsicInst *II, BasicBlock *BB); bool solveBlockValueExtractValue(ValueLatticeElement &BBLV, @@ -1090,8 +1096,22 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, return true; } - return solveBlockValueBinaryOpImpl(BBLV, BO, BB, - [BO](const ConstantRange &CR1, const ConstantRange &CR2) { + if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) { + unsigned NoWrapKind = 0; + if (OBO->hasNoUnsignedWrap()) + NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap; + if (OBO->hasNoSignedWrap()) + NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap; + + return solveBlockValueBinaryOpImpl( + BBLV, BO, BB, + [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind); + }); + } + + return solveBlockValueBinaryOpImpl( + BBLV, BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.binaryOp(BO->getOpcode(), CR2); }); } @@ -1104,37 +1124,46 @@ bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic( }); } -bool LazyValueInfoImpl::solveBlockValueIntrinsic( - ValueLatticeElement &BBLV, IntrinsicInst *II, BasicBlock *BB) { - switch (II->getIntrinsicID()) { +bool LazyValueInfoImpl::solveBlockValueSaturatingIntrinsic( + ValueLatticeElement &BBLV, SaturatingInst *SI, BasicBlock *BB) { + switch (SI->getIntrinsicID()) { case Intrinsic::uadd_sat: - return solveBlockValueBinaryOpImpl(BBLV, II, BB, - [](const ConstantRange &CR1, const ConstantRange &CR2) { + return solveBlockValueBinaryOpImpl( + BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.uadd_sat(CR2); }); case Intrinsic::usub_sat: - return solveBlockValueBinaryOpImpl(BBLV, II, BB, - [](const ConstantRange &CR1, const ConstantRange &CR2) { + return solveBlockValueBinaryOpImpl( + BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.usub_sat(CR2); }); case Intrinsic::sadd_sat: - return solveBlockValueBinaryOpImpl(BBLV, II, BB, - [](const ConstantRange &CR1, const ConstantRange &CR2) { + return solveBlockValueBinaryOpImpl( + BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.sadd_sat(CR2); }); case Intrinsic::ssub_sat: - return solveBlockValueBinaryOpImpl(BBLV, II, BB, - [](const ConstantRange &CR1, const ConstantRange &CR2) { + return solveBlockValueBinaryOpImpl( + BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.ssub_sat(CR2); }); default: - LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined (unknown intrinsic).\n"); - BBLV = ValueLatticeElement::getOverdefined(); - return true; + llvm_unreachable("All llvm.sat intrinsic are handled."); } } +bool LazyValueInfoImpl::solveBlockValueIntrinsic(ValueLatticeElement &BBLV, + IntrinsicInst *II, + BasicBlock *BB) { + if (auto *SI = dyn_cast<SaturatingInst>(II)) + return solveBlockValueSaturatingIntrinsic(BBLV, SI, BB); + + LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined (unknown intrinsic).\n"); + BBLV = ValueLatticeElement::getOverdefined(); + return true; +} + bool LazyValueInfoImpl::solveBlockValueExtractValue( ValueLatticeElement &BBLV, ExtractValueInst *EVI, BasicBlock *BB) { if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) diff --git a/llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp b/llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp index 7de9d2cbfddba..0f274429f11fd 100644 --- a/llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp +++ b/llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp @@ -64,10 +64,10 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/LegacyDivergenceAnalysis.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/DivergenceAnalysis.h" -#include "llvm/Analysis/LegacyDivergenceAnalysis.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -75,6 +75,8 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <vector> @@ -281,6 +283,9 @@ void DivergencePropagator::propagate() { // Register this pass. char LegacyDivergenceAnalysis::ID = 0; +LegacyDivergenceAnalysis::LegacyDivergenceAnalysis() : FunctionPass(ID) { + initializeLegacyDivergenceAnalysisPass(*PassRegistry::getPassRegistry()); +} INITIALIZE_PASS_BEGIN(LegacyDivergenceAnalysis, "divergence", "Legacy Divergence Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) diff --git a/llvm/lib/Analysis/Lint.cpp b/llvm/lib/Analysis/Lint.cpp index db18716c64cf8..ba945eb4318fc 100644 --- a/llvm/lib/Analysis/Lint.cpp +++ b/llvm/lib/Analysis/Lint.cpp @@ -66,6 +66,7 @@ #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" diff --git a/llvm/lib/Analysis/Loads.cpp b/llvm/lib/Analysis/Loads.cpp index 641e92eac781f..a7d07c0b61834 100644 --- a/llvm/lib/Analysis/Loads.cpp +++ b/llvm/lib/Analysis/Loads.cpp @@ -150,7 +150,7 @@ bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, // Require ABI alignment for loads without alignment specification const Align Alignment = DL.getValueOrABITypeAlignment(MA, Ty); - APInt AccessSize(DL.getIndexTypeSizeInBits(V->getType()), + APInt AccessSize(DL.getPointerTypeSizeInBits(V->getType()), DL.getTypeStoreSize(Ty)); return isDereferenceableAndAlignedPointer(V, Alignment, AccessSize, DL, CtxI, DT); @@ -383,10 +383,6 @@ Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy, MaxInstsToScan = ~0U; const DataLayout &DL = ScanBB->getModule()->getDataLayout(); - - // Try to get the store size for the type. - auto AccessSize = LocationSize::precise(DL.getTypeStoreSize(AccessTy)); - Value *StrippedPtr = Ptr->stripPointerCasts(); while (ScanFrom != ScanBB->begin()) { @@ -425,6 +421,9 @@ Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy, return LI; } + // Try to get the store size for the type. + auto AccessSize = LocationSize::precise(DL.getTypeStoreSize(AccessTy)); + if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); // If this is a store through Ptr, the value is available! diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp index 3d8f77675f3a2..26fa5112c29a7 100644 --- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -52,6 +52,7 @@ #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -2397,6 +2398,10 @@ void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const { PSE->print(OS, Depth); } +LoopAccessLegacyAnalysis::LoopAccessLegacyAnalysis() : FunctionPass(ID) { + initializeLoopAccessLegacyAnalysisPass(*PassRegistry::getPassRegistry()); +} + const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L) { auto &LAI = LoopAccessInfoMap[L]; diff --git a/llvm/lib/Analysis/LoopCacheAnalysis.cpp b/llvm/lib/Analysis/LoopCacheAnalysis.cpp index 10d2fe07884a0..25325ec1be025 100644 --- a/llvm/lib/Analysis/LoopCacheAnalysis.cpp +++ b/llvm/lib/Analysis/LoopCacheAnalysis.cpp @@ -29,6 +29,7 @@ #include "llvm/ADT/BreadthFirstIterator.h" #include "llvm/ADT/Sequence.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" using namespace llvm; @@ -283,6 +284,9 @@ CacheCostTy IndexedReference::computeRefCost(const Loop &L, const SCEV *ElemSize = Sizes.back(); const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize); const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS); + Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType()); + Stride = SE.getNoopOrSignExtend(Stride, WiderType); + TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType); const SCEV *Numerator = SE.getMulExpr(Stride, TripCount); RefCost = SE.getUDivExpr(Numerator, CacheLineSize); LLVM_DEBUG(dbgs().indent(4) @@ -313,7 +317,7 @@ bool IndexedReference::delinearize(const LoopInfo &LI) { const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst); const BasicBlock *BB = StoreOrLoadInst.getParent(); - for (Loop *L = LI.getLoopFor(BB); L != nullptr; L = L->getParentLoop()) { + if (Loop *L = LI.getLoopFor(BB)) { const SCEV *AccessFn = SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L); @@ -342,7 +346,7 @@ bool IndexedReference::delinearize(const LoopInfo &LI) { << "ERROR: failed to delinearize reference\n"); Subscripts.clear(); Sizes.clear(); - break; + return false; } const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize); @@ -453,7 +457,7 @@ CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, AliasAnalysis &AA, DependenceInfo &DI, Optional<unsigned> TRT) : Loops(Loops), TripCounts(), LoopCosts(), - TRT(TRT == None ? Optional<unsigned>(TemporalReuseThreshold) : TRT), + TRT((TRT == None) ? Optional<unsigned>(TemporalReuseThreshold) : TRT), LI(LI), SE(SE), TTI(TTI), AA(AA), DI(DI) { assert(!Loops.empty() && "Expecting a non-empty loop vector."); diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp index dbab5db7dbc2d..3dc29b40834c7 100644 --- a/llvm/lib/Analysis/LoopInfo.cpp +++ b/llvm/lib/Analysis/LoopInfo.cpp @@ -34,6 +34,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -105,7 +106,8 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, I->moveBefore(InsertPt); if (MSSAU) if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I)) - MSSAU->moveToPlace(MUD, InsertPt->getParent(), MemorySSA::End); + MSSAU->moveToPlace(MUD, InsertPt->getParent(), + MemorySSA::BeforeTerminator); // There is possibility of hoisting this instruction above some arbitrary // condition. Any metadata defined on it can be control dependent on this @@ -364,12 +366,11 @@ BranchInst *Loop::getLoopGuardBranch() const { return nullptr; BasicBlock *Preheader = getLoopPreheader(); - BasicBlock *Latch = getLoopLatch(); - assert(Preheader && Latch && + assert(Preheader && getLoopLatch() && "Expecting a loop with valid preheader and latch"); // Loop should be in rotate form. - if (!isLoopExiting(Latch)) + if (!isRotatedForm()) return nullptr; // Disallow loops with more than one unique exit block, as we do not verify @@ -1051,6 +1052,10 @@ MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context, // LoopInfo implementation // +LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) { + initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); +} + char LoopInfoWrapperPass::ID = 0; INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) diff --git a/llvm/lib/Analysis/LoopPass.cpp b/llvm/lib/Analysis/LoopPass.cpp index 4ab3798039d84..507f5f4428659 100644 --- a/llvm/lib/Analysis/LoopPass.cpp +++ b/llvm/lib/Analysis/LoopPass.cpp @@ -20,9 +20,10 @@ #include "llvm/IR/OptBisect.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/PassTimingInfo.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/Timer.h" #include "llvm/Support/TimeProfiler.h" +#include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -409,6 +410,10 @@ bool LoopPass::skipLoop(const Loop *L) const { return false; } +LCSSAVerificationPass::LCSSAVerificationPass() : FunctionPass(ID) { + initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry()); +} + char LCSSAVerificationPass::ID = 0; INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier", false, false) diff --git a/llvm/lib/Analysis/MemDepPrinter.cpp b/llvm/lib/Analysis/MemDepPrinter.cpp index 6e1bb50e88936..2c57e63251c66 100644 --- a/llvm/lib/Analysis/MemDepPrinter.cpp +++ b/llvm/lib/Analysis/MemDepPrinter.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; diff --git a/llvm/lib/Analysis/MemDerefPrinter.cpp b/llvm/lib/Analysis/MemDerefPrinter.cpp index 5cf516a538b55..5d824067df539 100644 --- a/llvm/lib/Analysis/MemDerefPrinter.cpp +++ b/llvm/lib/Analysis/MemDerefPrinter.cpp @@ -13,6 +13,7 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; diff --git a/llvm/lib/Analysis/MemoryBuiltins.cpp b/llvm/lib/Analysis/MemoryBuiltins.cpp index 172c86eb46466..427e6fd3ace24 100644 --- a/llvm/lib/Analysis/MemoryBuiltins.cpp +++ b/llvm/lib/Analysis/MemoryBuiltins.cpp @@ -544,6 +544,7 @@ Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize, Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second); Value *UseZero = Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second); + ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType); return Builder.CreateSelect(UseZero, ConstantInt::get(ResultType, 0), ResultSize); } @@ -576,7 +577,7 @@ ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL, } SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { - IntTyBits = DL.getPointerTypeSizeInBits(V->getType()); + IntTyBits = DL.getIndexTypeSizeInBits(V->getType()); Zero = APInt::getNullValue(IntTyBits); V = V->stripPointerCasts(); @@ -746,7 +747,7 @@ ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { SizeOffsetType PtrData = compute(GEP.getPointerOperand()); - APInt Offset(IntTyBits, 0); + APInt Offset(DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()), 0); if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset)) return unknown(); @@ -834,7 +835,7 @@ ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator( SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { // XXX - Are vectors of pointers possible here? - IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType())); + IntTy = cast<IntegerType>(DL.getIndexType(V->getType())); Zero = ConstantInt::get(IntTy, 0); SizeOffsetEvalType Result = compute_(V); @@ -938,12 +939,12 @@ SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { } Value *FirstArg = CS.getArgument(FnData->FstParam); - FirstArg = Builder.CreateZExt(FirstArg, IntTy); + FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy); if (FnData->SndParam < 0) return std::make_pair(FirstArg, Zero); Value *SecondArg = CS.getArgument(FnData->SndParam); - SecondArg = Builder.CreateZExt(SecondArg, IntTy); + SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy); Value *Size = Builder.CreateMul(FirstArg, SecondArg); return std::make_pair(Size, Zero); diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index 884587e020bb6..a97a56e258050 100644 --- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -47,6 +47,7 @@ #include "llvm/IR/Use.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/Casting.h" @@ -1493,7 +1494,7 @@ void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies( if (auto *I = dyn_cast<Instruction>(P.getPointer())) { auto toRemoveIt = ReverseNonLocalDefsCache.find(I); if (toRemoveIt != ReverseNonLocalDefsCache.end()) { - for (const auto &entry : toRemoveIt->second) + for (const auto *entry : toRemoveIt->second) NonLocalDefsCache.erase(entry); ReverseNonLocalDefsCache.erase(toRemoveIt); } diff --git a/llvm/lib/Analysis/MemoryLocation.cpp b/llvm/lib/Analysis/MemoryLocation.cpp index 163830eee797e..103cdea148e5e 100644 --- a/llvm/lib/Analysis/MemoryLocation.cpp +++ b/llvm/lib/Analysis/MemoryLocation.cpp @@ -12,6 +12,7 @@ #include "llvm/IR/DataLayout.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/IntrinsicsARM.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp index cfb8b7e7dcb55..bf8dc94bfbf94 100644 --- a/llvm/lib/Analysis/MemorySSA.cpp +++ b/llvm/lib/Analysis/MemorySSA.cpp @@ -38,6 +38,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Use.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/Casting.h" @@ -1229,6 +1230,7 @@ MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT) // safe because there are no CFG changes while building MemorySSA and can // significantly reduce the time spent by the compiler in AA, because we will // make queries about all the instructions in the Function. + assert(AA && "No alias analysis?"); BatchAAResults BatchAA(*AA); buildMemorySSA(BatchAA); // Intentionally leave AA to nullptr while building so we don't accidently @@ -1868,9 +1870,7 @@ LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); } #endif void MemorySSA::verifyMemorySSA() const { - verifyDefUses(F); - verifyDomination(F); - verifyOrdering(F); + verifyOrderingDominationAndDefUses(F); verifyDominationNumbers(F); verifyPrevDefInPhis(F); // Previously, the verification used to also verify that the clobberingAccess @@ -1957,10 +1957,14 @@ void MemorySSA::verifyDominationNumbers(const Function &F) const { #endif } -/// Verify that the order and existence of MemoryAccesses matches the +/// Verify ordering: the order and existence of MemoryAccesses matches the /// order and existence of memory affecting instructions. -void MemorySSA::verifyOrdering(Function &F) const { -#ifndef NDEBUG +/// Verify domination: each definition dominates all of its uses. +/// Verify def-uses: the immediate use information - walk all the memory +/// accesses and verifying that, for each use, it appears in the appropriate +/// def's use list +void MemorySSA::verifyOrderingDominationAndDefUses(Function &F) const { +#if !defined(NDEBUG) // Walk all the blocks, comparing what the lookups think and what the access // lists think, as well as the order in the blocks vs the order in the access // lists. @@ -1969,29 +1973,56 @@ void MemorySSA::verifyOrdering(Function &F) const { for (BasicBlock &B : F) { const AccessList *AL = getBlockAccesses(&B); const auto *DL = getBlockDefs(&B); - MemoryAccess *Phi = getMemoryAccess(&B); + MemoryPhi *Phi = getMemoryAccess(&B); if (Phi) { + // Verify ordering. ActualAccesses.push_back(Phi); ActualDefs.push_back(Phi); + // Verify domination + for (const Use &U : Phi->uses()) + assert(dominates(Phi, U) && "Memory PHI does not dominate it's uses"); +#if defined(EXPENSIVE_CHECKS) + // Verify def-uses. + assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance( + pred_begin(&B), pred_end(&B))) && + "Incomplete MemoryPhi Node"); + for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) { + verifyUseInDefs(Phi->getIncomingValue(I), Phi); + assert(find(predecessors(&B), Phi->getIncomingBlock(I)) != + pred_end(&B) && + "Incoming phi block not a block predecessor"); + } +#endif } for (Instruction &I : B) { - MemoryAccess *MA = getMemoryAccess(&I); + MemoryUseOrDef *MA = getMemoryAccess(&I); assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) && "We have memory affecting instructions " "in this block but they are not in the " "access list or defs list"); if (MA) { + // Verify ordering. ActualAccesses.push_back(MA); - if (isa<MemoryDef>(MA)) + if (MemoryAccess *MD = dyn_cast<MemoryDef>(MA)) { + // Verify ordering. ActualDefs.push_back(MA); + // Verify domination. + for (const Use &U : MD->uses()) + assert(dominates(MD, U) && + "Memory Def does not dominate it's uses"); + } +#if defined(EXPENSIVE_CHECKS) + // Verify def-uses. + verifyUseInDefs(MA->getDefiningAccess(), MA); +#endif } } // Either we hit the assert, really have no accesses, or we have both - // accesses and an access list. - // Same with defs. + // accesses and an access list. Same with defs. if (!AL && !DL) continue; + // Verify ordering. assert(AL->size() == ActualAccesses.size() && "We don't have the same number of accesses in the block as on the " "access list"); @@ -2022,28 +2053,6 @@ void MemorySSA::verifyOrdering(Function &F) const { #endif } -/// Verify the domination properties of MemorySSA by checking that each -/// definition dominates all of its uses. -void MemorySSA::verifyDomination(Function &F) const { -#ifndef NDEBUG - for (BasicBlock &B : F) { - // Phi nodes are attached to basic blocks - if (MemoryPhi *MP = getMemoryAccess(&B)) - for (const Use &U : MP->uses()) - assert(dominates(MP, U) && "Memory PHI does not dominate it's uses"); - - for (Instruction &I : B) { - MemoryAccess *MD = dyn_cast_or_null<MemoryDef>(getMemoryAccess(&I)); - if (!MD) - continue; - - for (const Use &U : MD->uses()) - assert(dominates(MD, U) && "Memory Def does not dominate it's uses"); - } - } -#endif -} - /// Verify the def-use lists in MemorySSA, by verifying that \p Use /// appears in the use list of \p Def. void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const { @@ -2058,34 +2067,6 @@ void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const { #endif } -/// Verify the immediate use information, by walking all the memory -/// accesses and verifying that, for each use, it appears in the -/// appropriate def's use list -void MemorySSA::verifyDefUses(Function &F) const { -#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS) - for (BasicBlock &B : F) { - // Phi nodes are attached to basic blocks - if (MemoryPhi *Phi = getMemoryAccess(&B)) { - assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance( - pred_begin(&B), pred_end(&B))) && - "Incomplete MemoryPhi Node"); - for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) { - verifyUseInDefs(Phi->getIncomingValue(I), Phi); - assert(find(predecessors(&B), Phi->getIncomingBlock(I)) != - pred_end(&B) && - "Incoming phi block not a block predecessor"); - } - } - - for (Instruction &I : B) { - if (MemoryUseOrDef *MA = getMemoryAccess(&I)) { - verifyUseInDefs(MA->getDefiningAccess(), MA); - } - } - } -#endif -} - /// Perform a local numbering on blocks so that instruction ordering can be /// determined in constant time. /// TODO: We currently just number in order. If we numbered by N, we could diff --git a/llvm/lib/Analysis/MemorySSAUpdater.cpp b/llvm/lib/Analysis/MemorySSAUpdater.cpp index f2d56b05d968e..473268982f2df 100644 --- a/llvm/lib/Analysis/MemorySSAUpdater.cpp +++ b/llvm/lib/Analysis/MemorySSAUpdater.cpp @@ -1159,7 +1159,13 @@ void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) { void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where) { - return moveTo(What, BB, Where); + if (Where != MemorySSA::InsertionPlace::BeforeTerminator) + return moveTo(What, BB, Where); + + if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator())) + return moveBefore(What, Where); + else + return moveTo(What, BB, MemorySSA::InsertionPlace::End); } // All accesses in To used to be in From. Move to end and update access lists. diff --git a/llvm/lib/Analysis/ModuleDebugInfoPrinter.cpp b/llvm/lib/Analysis/ModuleDebugInfoPrinter.cpp index 519242759824a..52b884fb88e06 100644 --- a/llvm/lib/Analysis/ModuleDebugInfoPrinter.cpp +++ b/llvm/lib/Analysis/ModuleDebugInfoPrinter.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/Passes.h" #include "llvm/IR/DebugInfo.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" diff --git a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp index 8232bf07cafc9..8a1206f49c21d 100644 --- a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp +++ b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -44,6 +44,7 @@ #include "llvm/IR/ModuleSummaryIndex.h" #include "llvm/IR/Use.h" #include "llvm/IR/User.h" +#include "llvm/InitializePasses.h" #include "llvm/Object/ModuleSymbolTable.h" #include "llvm/Object/SymbolicFile.h" #include "llvm/Pass.h" @@ -466,7 +467,8 @@ static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(), // FIXME: refactor this to use the same code that inliner is using. // Don't try to import functions with noinline attribute. - F.getAttributes().hasFnAttribute(Attribute::NoInline)}; + F.getAttributes().hasFnAttribute(Attribute::NoInline), + F.hasFnAttribute(Attribute::AlwaysInline)}; auto FuncSummary = std::make_unique<FunctionSummary>( Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs), CallGraphEdges.takeVector(), TypeTests.takeVector(), @@ -703,7 +705,8 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( F->hasFnAttribute(Attribute::ReadOnly), F->hasFnAttribute(Attribute::NoRecurse), F->returnDoesNotAlias(), - /* NoInline = */ false}, + /* NoInline = */ false, + F->hasFnAttribute(Attribute::AlwaysInline)}, /*EntryCount=*/0, ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{}, ArrayRef<GlobalValue::GUID>{}, @@ -817,7 +820,7 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( if (EC) report_fatal_error(Twine("Failed to open dot file ") + ModuleSummaryDotFile + ": " + EC.message() + "\n"); - Index.exportToDot(OSDot); + Index.exportToDot(OSDot, {}); } return Index; diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp index 44527773115d3..952c2cbfec4e0 100644 --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -12,12 +12,14 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/FormattedStream.h" #include "llvm/Support/raw_ostream.h" @@ -353,7 +355,25 @@ ModulePass *llvm::createMustBeExecutedContextPrinter() { } bool MustBeExecutedContextPrinter::runOnModule(Module &M) { - MustBeExecutedContextExplorer Explorer(true); + // We provide non-PM analysis here because the old PM doesn't like to query + // function passes from a module pass. + SmallVector<PostDominatorTree *, 8> PDTs; + SmallVector<DominatorTree *, 8> DTs; + SmallVector<LoopInfo *, 8> LIs; + + GetterTy<LoopInfo> LIGetter = [&](const Function &F) { + DominatorTree *DT = new DominatorTree(const_cast<Function &>(F)); + LoopInfo *LI = new LoopInfo(*DT); + DTs.push_back(DT); + LIs.push_back(LI); + return LI; + }; + GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) { + PostDominatorTree *PDT = new PostDominatorTree(const_cast<Function &>(F)); + PDTs.push_back(PDT); + return PDT; + }; + MustBeExecutedContextExplorer Explorer(true, LIGetter, PDTGetter); for (Function &F : M) { for (Instruction &I : instructions(F)) { dbgs() << "-- Explore context of: " << I << "\n"; @@ -363,6 +383,9 @@ bool MustBeExecutedContextPrinter::runOnModule(Module &M) { } } + DeleteContainerPointers(PDTs); + DeleteContainerPointers(LIs); + DeleteContainerPointers(DTs); return false; } @@ -443,6 +466,173 @@ bool MustExecutePrinter::runOnFunction(Function &F) { return false; } +/// Return true if \p L might be an endless loop. +static bool maybeEndlessLoop(const Loop &L) { + if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn)) + return false; + // TODO: Actually try to prove it is not. + // TODO: If maybeEndlessLoop is going to be expensive, cache it. + return true; +} + +static bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) { + if (!LI) + return false; + using RPOTraversal = ReversePostOrderTraversal<const Function *>; + RPOTraversal FuncRPOT(&F); + return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal, + const LoopInfo>(FuncRPOT, *LI); +} + +/// Lookup \p Key in \p Map and return the result, potentially after +/// initializing the optional through \p Fn(\p args). +template <typename K, typename V, typename FnTy, typename... ArgsTy> +static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map, + FnTy &&Fn, ArgsTy&&... args) { + Optional<V> &OptVal = Map[Key]; + if (!OptVal.hasValue()) + OptVal = Fn(std::forward<ArgsTy>(args)...); + return OptVal.getValue(); +} + +const BasicBlock * +MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) { + const LoopInfo *LI = LIGetter(*InitBB->getParent()); + const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent()); + + LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName() + << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : "")); + + const Function &F = *InitBB->getParent(); + const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr; + const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB; + bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) || + (L && !maybeEndlessLoop(*L))) && + F.doesNotThrow(); + LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "") + << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "") + << "\n"); + + // Determine the adjacent blocks in the given direction but exclude (self) + // loops under certain circumstances. + SmallVector<const BasicBlock *, 8> Worklist; + for (const BasicBlock *SuccBB : successors(InitBB)) { + bool IsLatch = SuccBB == HeaderBB; + // Loop latches are ignored in forward propagation if the loop cannot be + // endless and may not throw: control has to go somewhere. + if (!WillReturnAndNoThrow || !IsLatch) + Worklist.push_back(SuccBB); + } + LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n"); + + // If there are no other adjacent blocks, there is no join point. + if (Worklist.empty()) + return nullptr; + + // If there is one adjacent block, it is the join point. + if (Worklist.size() == 1) + return Worklist[0]; + + // Try to determine a join block through the help of the post-dominance + // tree. If no tree was provided, we perform simple pattern matching for one + // block conditionals and one block loops only. + const BasicBlock *JoinBB = nullptr; + if (PDT) + if (const auto *InitNode = PDT->getNode(InitBB)) + if (const auto *IDomNode = InitNode->getIDom()) + JoinBB = IDomNode->getBlock(); + + if (!JoinBB && Worklist.size() == 2) { + const BasicBlock *Succ0 = Worklist[0]; + const BasicBlock *Succ1 = Worklist[1]; + const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor(); + const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor(); + if (Succ0UniqueSucc == InitBB) { + // InitBB -> Succ0 -> InitBB + // InitBB -> Succ1 = JoinBB + JoinBB = Succ1; + } else if (Succ1UniqueSucc == InitBB) { + // InitBB -> Succ1 -> InitBB + // InitBB -> Succ0 = JoinBB + JoinBB = Succ0; + } else if (Succ0 == Succ1UniqueSucc) { + // InitBB -> Succ0 = JoinBB + // InitBB -> Succ1 -> Succ0 = JoinBB + JoinBB = Succ0; + } else if (Succ1 == Succ0UniqueSucc) { + // InitBB -> Succ0 -> Succ1 = JoinBB + // InitBB -> Succ1 = JoinBB + JoinBB = Succ1; + } else if (Succ0UniqueSucc == Succ1UniqueSucc) { + // InitBB -> Succ0 -> JoinBB + // InitBB -> Succ1 -> JoinBB + JoinBB = Succ0UniqueSucc; + } + } + + if (!JoinBB && L) + JoinBB = L->getUniqueExitBlock(); + + if (!JoinBB) + return nullptr; + + LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n"); + + // In forward direction we check if control will for sure reach JoinBB from + // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control + // are: infinite loops and instructions that do not necessarily transfer + // execution to their successor. To check for them we traverse the CFG from + // the adjacent blocks to the JoinBB, looking at all intermediate blocks. + + // If we know the function is "will-return" and "no-throw" there is no need + // for futher checks. + if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) { + + auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) { + return isGuaranteedToTransferExecutionToSuccessor(BB); + }; + + SmallPtrSet<const BasicBlock *, 16> Visited; + while (!Worklist.empty()) { + const BasicBlock *ToBB = Worklist.pop_back_val(); + if (ToBB == JoinBB) + continue; + + // Make sure all loops in-between are finite. + if (!Visited.insert(ToBB).second) { + if (!F.hasFnAttribute(Attribute::WillReturn)) { + if (!LI) + return nullptr; + + bool MayContainIrreducibleControl = getOrCreateCachedOptional( + &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI); + if (MayContainIrreducibleControl) + return nullptr; + + const Loop *L = LI->getLoopFor(ToBB); + if (L && maybeEndlessLoop(*L)) + return nullptr; + } + + continue; + } + + // Make sure the block has no instructions that could stop control + // transfer. + bool TransfersExecution = getOrCreateCachedOptional( + ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB); + if (!TransfersExecution) + return nullptr; + + for (const BasicBlock *AdjacentBB : successors(ToBB)) + Worklist.push_back(AdjacentBB); + } + } + + LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n"); + return JoinBB; +} + const Instruction * MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( MustBeExecutedIterator &It, const Instruction *PP) { @@ -490,6 +680,12 @@ MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( return &PP->getSuccessor(0)->front(); } + // Multiple successors mean we need to find the join point where control flow + // converges again. We use the findForwardJoinPoint helper function with + // information about the function and helper analyses, if available. + if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent())) + return &JoinBB->front(); + LLVM_DEBUG(dbgs() << "\tNo join point found\n"); return nullptr; } diff --git a/llvm/lib/Analysis/OptimizationRemarkEmitter.cpp b/llvm/lib/Analysis/OptimizationRemarkEmitter.cpp index 07a5619a35b90..44e6637f63377 100644 --- a/llvm/lib/Analysis/OptimizationRemarkEmitter.cpp +++ b/llvm/lib/Analysis/OptimizationRemarkEmitter.cpp @@ -18,6 +18,7 @@ #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/InitializePasses.h" using namespace llvm; diff --git a/llvm/lib/Analysis/PhiValues.cpp b/llvm/lib/Analysis/PhiValues.cpp index 49749bc44746d..198647dafbef9 100644 --- a/llvm/lib/Analysis/PhiValues.cpp +++ b/llvm/lib/Analysis/PhiValues.cpp @@ -10,6 +10,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/Instructions.h" +#include "llvm/InitializePasses.h" using namespace llvm; @@ -47,25 +48,28 @@ bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA, // we're ultimately interested in, and all of the reachable values, i.e. // including phis, as that makes invalidateValue easier. void PhiValues::processPhi(const PHINode *Phi, - SmallVector<const PHINode *, 8> &Stack) { + SmallVectorImpl<const PHINode *> &Stack) { // Initialize the phi with the next depth number. assert(DepthMap.lookup(Phi) == 0); assert(NextDepthNumber != UINT_MAX); - unsigned int DepthNumber = ++NextDepthNumber; - DepthMap[Phi] = DepthNumber; + unsigned int RootDepthNumber = ++NextDepthNumber; + DepthMap[Phi] = RootDepthNumber; // Recursively process the incoming phis of this phi. TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this)); for (Value *PhiOp : Phi->incoming_values()) { if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) { // Recurse if the phi has not yet been visited. - if (DepthMap.lookup(PhiPhiOp) == 0) + unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp); + if (OpDepthNumber == 0) { processPhi(PhiPhiOp, Stack); - assert(DepthMap.lookup(PhiPhiOp) != 0); + OpDepthNumber = DepthMap.lookup(PhiPhiOp); + assert(OpDepthNumber != 0); + } // If the phi did not become part of a component then this phi and that // phi are part of the same component, so adjust the depth number. - if (!ReachableMap.count(DepthMap[PhiPhiOp])) - DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]); + if (!ReachableMap.count(OpDepthNumber)) + DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber); } else { TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this)); } @@ -76,48 +80,59 @@ void PhiValues::processPhi(const PHINode *Phi, // If the depth number has not changed then we've finished collecting the phis // of a strongly connected component. - if (DepthMap[Phi] == DepthNumber) { + if (DepthMap[Phi] == RootDepthNumber) { // Collect the reachable values for this component. The phis of this - // component will be those on top of the depth stach with the same or + // component will be those on top of the depth stack with the same or // greater depth number. - ConstValueSet Reachable; - while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) { + ConstValueSet &Reachable = ReachableMap[RootDepthNumber]; + while (true) { const PHINode *ComponentPhi = Stack.pop_back_val(); Reachable.insert(ComponentPhi); - DepthMap[ComponentPhi] = DepthNumber; + for (Value *Op : ComponentPhi->incoming_values()) { if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) { // If this phi is not part of the same component then that component // is guaranteed to have been completed before this one. Therefore we // can just add its reachable values to the reachable values of this // component. - auto It = ReachableMap.find(DepthMap[PhiOp]); - if (It != ReachableMap.end()) - Reachable.insert(It->second.begin(), It->second.end()); - } else { + unsigned int OpDepthNumber = DepthMap[PhiOp]; + if (OpDepthNumber != RootDepthNumber) { + auto It = ReachableMap.find(OpDepthNumber); + if (It != ReachableMap.end()) + Reachable.insert(It->second.begin(), It->second.end()); + } + } else Reachable.insert(Op); - } } + + if (Stack.empty()) + break; + + unsigned int &ComponentDepthNumber = DepthMap[Stack.back()]; + if (ComponentDepthNumber < RootDepthNumber) + break; + + ComponentDepthNumber = RootDepthNumber; } - ReachableMap.insert({DepthNumber,Reachable}); // Filter out phis to get the non-phi reachable values. - ValueSet NonPhi; + ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber]; for (const Value *V : Reachable) if (!isa<PHINode>(V)) - NonPhi.insert(const_cast<Value*>(V)); - NonPhiReachableMap.insert({DepthNumber,NonPhi}); + NonPhi.insert(const_cast<Value *>(V)); } } const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) { - if (DepthMap.count(PN) == 0) { + unsigned int DepthNumber = DepthMap.lookup(PN); + if (DepthNumber == 0) { SmallVector<const PHINode *, 8> Stack; processPhi(PN, Stack); + DepthNumber = DepthMap.lookup(PN); assert(Stack.empty()); + assert(DepthNumber != 0); } - assert(DepthMap.lookup(PN) != 0); - return NonPhiReachableMap[DepthMap[PN]]; + return NonPhiReachableMap[DepthNumber]; } void PhiValues::invalidateValue(const Value *V) { diff --git a/llvm/lib/Analysis/PostDominators.cpp b/llvm/lib/Analysis/PostDominators.cpp index 4afe22bd5342a..f01d51504d7cd 100644 --- a/llvm/lib/Analysis/PostDominators.cpp +++ b/llvm/lib/Analysis/PostDominators.cpp @@ -12,7 +12,9 @@ #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/raw_ostream.h" @@ -32,6 +34,11 @@ static constexpr bool ExpensiveChecksEnabled = false; char PostDominatorTreeWrapperPass::ID = 0; +PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass() + : FunctionPass(ID) { + initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); +} + INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree", "Post-Dominator Tree Construction", true, true) @@ -44,6 +51,28 @@ bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA, PAC.preservedSet<CFGAnalyses>()); } +bool PostDominatorTree::dominates(const Instruction *I1, + const Instruction *I2) const { + assert(I1 && I2 && "Expecting valid I1 and I2"); + + const BasicBlock *BB1 = I1->getParent(); + const BasicBlock *BB2 = I2->getParent(); + + if (BB1 != BB2) + return Base::dominates(BB1, BB2); + + // PHINodes in a block are unordered. + if (isa<PHINode>(I1) && isa<PHINode>(I2)) + return false; + + // Loop through the basic block until we find I1 or I2. + BasicBlock::const_iterator I = BB1->begin(); + for (; &*I != I1 && &*I != I2; ++I) + /*empty*/; + + return &*I == I2; +} + bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) { DT.recalculate(F); return false; diff --git a/llvm/lib/Analysis/ProfileSummaryInfo.cpp b/llvm/lib/Analysis/ProfileSummaryInfo.cpp index b99b75715025b..911d39d9a2637 100644 --- a/llvm/lib/Analysis/ProfileSummaryInfo.cpp +++ b/llvm/lib/Analysis/ProfileSummaryInfo.cpp @@ -18,6 +18,8 @@ #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/ProfileSummary.h" +#include "llvm/InitializePasses.h" +#include "llvm/Support/CommandLine.h" using namespace llvm; // The following two parameters determine the threshold for a count to be diff --git a/llvm/lib/Analysis/RegionInfo.cpp b/llvm/lib/Analysis/RegionInfo.cpp index 8ba38adfb0d23..88629517d484b 100644 --- a/llvm/lib/Analysis/RegionInfo.cpp +++ b/llvm/lib/Analysis/RegionInfo.cpp @@ -10,6 +10,7 @@ #include "llvm/Analysis/RegionInfo.h" #include "llvm/ADT/Statistic.h" +#include "llvm/InitializePasses.h" #ifndef NDEBUG #include "llvm/Analysis/RegionPrinter.h" #endif diff --git a/llvm/lib/Analysis/RegionPrinter.cpp b/llvm/lib/Analysis/RegionPrinter.cpp index 5bdcb31fbe993..020ff85d1b989 100644 --- a/llvm/lib/Analysis/RegionPrinter.cpp +++ b/llvm/lib/Analysis/RegionPrinter.cpp @@ -16,6 +16,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/RegionIterator.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 5ce0a1adeaa0c..26a9a5ddf1ea7 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -112,6 +112,7 @@ #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/Verifier.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -220,6 +221,12 @@ static cl::opt<unsigned> cl::desc("Size of the expression which is considered huge"), cl::init(4096)); +static cl::opt<bool> +ClassifyExpressions("scalar-evolution-classify-expressions", + cl::Hidden, cl::init(true), + cl::desc("When printing analysis, include information on every instruction")); + + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -3488,7 +3495,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); // getSCEV(Base)->getType() has the same address space as Base->getType() // because SCEV::getType() preserves the address space. - Type *IntPtrTy = getEffectiveSCEVType(BaseExpr->getType()); + Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType()); // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP // instruction to its SCEV, because the Instruction may be guarded by control // flow and the no-overflow bits may not be valid for the expression in any @@ -3497,7 +3504,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap; - const SCEV *TotalOffset = getZero(IntPtrTy); + const SCEV *TotalOffset = getZero(IntIdxTy); // The array size is unimportant. The first thing we do on CurTy is getting // its element type. Type *CurTy = ArrayType::get(GEP->getSourceElementType(), 0); @@ -3507,7 +3514,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // For a struct, add the member offset. ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue(); unsigned FieldNo = Index->getZExtValue(); - const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo); + const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); // Add the field offset to the running total offset. TotalOffset = getAddExpr(TotalOffset, FieldOffset); @@ -3518,9 +3525,9 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // Update CurTy to its element type. CurTy = cast<SequentialType>(CurTy)->getElementType(); // For an array, add the element offset, explicitly scaled. - const SCEV *ElementSize = getSizeOfExpr(IntPtrTy, CurTy); + const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); // Getelementptr indices are signed. - IndexExpr = getTruncateOrSignExtend(IndexExpr, IntPtrTy); + IndexExpr = getTruncateOrSignExtend(IndexExpr, IntIdxTy); // Multiply the index by the element size to compute the element offset. const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap); @@ -3779,7 +3786,7 @@ uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { /// Return a type with the same bitwidth as the given type and which represents /// how SCEV will treat the given type, for which isSCEVable must return -/// true. For pointer types, this is the pointer-sized integer type. +/// true. For pointer types, this is the pointer index sized integer type. Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { assert(isSCEVable(Ty) && "Type is not SCEVable!"); @@ -3788,7 +3795,7 @@ Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { // The only other support type is pointer. assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!"); - return getDataLayout().getIntPtrType(Ty); + return getDataLayout().getIndexType(Ty); } Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const { @@ -4568,6 +4575,12 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { break; } + // Recognise intrinsic loop.decrement.reg, and as this has exactly the same + // semantics as a Sub, return a binary sub expression. + if (auto *II = dyn_cast<IntrinsicInst>(V)) + if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg) + return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1)); + return None; } @@ -5553,6 +5566,7 @@ ScalarEvolution::getRangeRef(const SCEV *S, unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); + using OBO = OverflowingBinaryOperator; // If the value has known zeros, the maximum value will have those known zeros // as well. @@ -5570,8 +5584,14 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); + unsigned WrapType = OBO::AnyWrap; + if (Add->hasNoSignedWrap()) + WrapType |= OBO::NoSignedWrap; + if (Add->hasNoUnsignedWrap()) + WrapType |= OBO::NoUnsignedWrap; for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + WrapType, RangeType); return setRange(Add, SignHint, ConservativeResult.intersectWith(X, RangeType)); } @@ -5647,29 +5667,38 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { // If there's no unsigned wrap, the value will never be less than its // initial value. - if (AddRec->hasNoUnsignedWrap()) - if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) - if (!C->getValue()->isZero()) - ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(C->getAPInt(), APInt(BitWidth, 0)), RangeType); - - // If there's no signed wrap, and all the operands have the same sign or - // zero, the value won't ever change sign. + if (AddRec->hasNoUnsignedWrap()) { + APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart()); + if (!UnsignedMinValue.isNullValue()) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(UnsignedMinValue, APInt(BitWidth, 0)), RangeType); + } + + // If there's no signed wrap, and all the operands except initial value have + // the same sign or zero, the value won't ever be: + // 1: smaller than initial value if operands are non negative, + // 2: bigger than initial value if operands are non positive. + // For both cases, value can not cross signed min/max boundary. if (AddRec->hasNoSignedWrap()) { bool AllNonNeg = true; bool AllNonPos = true; - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { - if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false; - if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false; + for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) { + if (!isKnownNonNegative(AddRec->getOperand(i))) + AllNonNeg = false; + if (!isKnownNonPositive(AddRec->getOperand(i))) + AllNonPos = false; } if (AllNonNeg) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt(BitWidth, 0), - APInt::getSignedMinValue(BitWidth)), RangeType); + ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()), + APInt::getSignedMinValue(BitWidth)), + RangeType); else if (AllNonPos) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt(BitWidth, 1)), RangeType); + ConstantRange::getNonEmpty( + APInt::getSignedMinValue(BitWidth), + getSignedRangeMax(AddRec->getStart()) + 1), + RangeType); } // TODO: non-affine addrec @@ -5710,14 +5739,26 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) { // For a SCEVUnknown, ask ValueTracking. KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT); - if (Known.One != ~Known.Zero + 1) - ConservativeResult = - ConservativeResult.intersectWith( - ConstantRange(Known.One, ~Known.Zero + 1), RangeType); + if (Known.getBitWidth() != BitWidth) + Known = Known.zextOrTrunc(BitWidth, true); + // If Known does not result in full-set, intersect with it. + if (Known.getMinValue() != Known.getMaxValue() + 1) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1), + RangeType); } else { assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED && "generalize as needed!"); unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT); + // If the pointer size is larger than the index size type, this can cause + // NS to be larger than BitWidth. So compensate for this. + if (U->getType()->isPointerTy()) { + unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType()); + int ptrIdxDiff = ptrSize - BitWidth; + if (ptrIdxDiff > 0 && ptrSize > BitWidth && NS > (unsigned)ptrIdxDiff) + NS -= ptrIdxDiff; + } + if (NS > 1) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), @@ -6599,12 +6640,16 @@ ScalarEvolution::getSmallConstantTripMultiple(const Loop *L, return (unsigned)Result->getZExtValue(); } -/// Get the expression for the number of loop iterations for which this loop is -/// guaranteed not to exit via ExitingBlock. Otherwise return -/// SCEVCouldNotCompute. const SCEV *ScalarEvolution::getExitCount(const Loop *L, - BasicBlock *ExitingBlock) { - return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + BasicBlock *ExitingBlock, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(ExitingBlock, this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } const SCEV * @@ -6613,14 +6658,15 @@ ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L, return getPredicatedBackedgeTakenInfo(L).getExact(L, this, &Preds); } -const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getExact(L, this); -} - -/// Similar to getBackedgeTakenCount, except return the least SCEV value that is -/// known never to be less than the actual backedge taken count. -const SCEV *ScalarEvolution::getConstantMaxBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getMax(this); +const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(L, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { @@ -6929,6 +6975,16 @@ ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock, return SE->getCouldNotCompute(); } +const SCEV * +ScalarEvolution::BackedgeTakenInfo::getMax(BasicBlock *ExitingBlock, + ScalarEvolution *SE) const { + for (auto &ENT : ExitNotTaken) + if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate()) + return ENT.MaxNotTaken; + + return SE->getCouldNotCompute(); +} + /// getMax - Get the max backedge taken count for the loop. const SCEV * ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { @@ -7020,13 +7076,15 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( BasicBlock *ExitBB = EEI.first; const ExitLimit &EL = EEI.second; if (EL.Predicates.empty()) - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, nullptr); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + nullptr); std::unique_ptr<SCEVUnionPredicate> Predicate(new SCEVUnionPredicate); for (auto *Pred : EL.Predicates) Predicate->add(Pred); - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + std::move(Predicate)); }); assert((isa<SCEVCouldNotCompute>(MaxCount) || isa<SCEVConstant>(MaxCount)) && "No point in having a non-constant max backedge taken count!"); @@ -7058,6 +7116,17 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L, // Do a union of all the predicates here. for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { BasicBlock *ExitBB = ExitingBlocks[i]; + + // We canonicalize untaken exits to br (constant), ignore them so that + // proving an exit untaken doesn't negatively impact our ability to reason + // about the loop as whole. + if (auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator())) + if (auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) { + bool ExitIfTrue = !L->contains(BI->getSuccessor(0)); + if ((ExitIfTrue && CI->isZero()) || (!ExitIfTrue && CI->isOne())) + continue; + } + ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates); assert((AllowPredicates || EL.Predicates.empty()) && @@ -7217,6 +7286,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "and i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isOne() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isOne() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -7265,6 +7339,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "or i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isZero() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isZero() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -10976,7 +11055,7 @@ struct SCEVCollectAddRecMultiplies { } else if (Unknown) { HasAddRec = true; } else { - bool ContainsAddRec; + bool ContainsAddRec = false; SCEVHasAddRec ContiansAddRec(ContainsAddRec); visitAll(Op, ContiansAddRec); HasAddRec |= ContainsAddRec; @@ -11544,77 +11623,79 @@ void ScalarEvolution::print(raw_ostream &OS) const { // const isn't dangerous. ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this); - OS << "Classifying expressions for: "; - F.printAsOperand(OS, /*PrintType=*/false); - OS << "\n"; - for (Instruction &I : instructions(F)) - if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { - OS << I << '\n'; - OS << " --> "; - const SCEV *SV = SE.getSCEV(&I); - SV->print(OS); - if (!isa<SCEVCouldNotCompute>(SV)) { - OS << " U: "; - SE.getUnsignedRange(SV).print(OS); - OS << " S: "; - SE.getSignedRange(SV).print(OS); - } - - const Loop *L = LI.getLoopFor(I.getParent()); - - const SCEV *AtUse = SE.getSCEVAtScope(SV, L); - if (AtUse != SV) { + if (ClassifyExpressions) { + OS << "Classifying expressions for: "; + F.printAsOperand(OS, /*PrintType=*/false); + OS << "\n"; + for (Instruction &I : instructions(F)) + if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { + OS << I << '\n'; OS << " --> "; - AtUse->print(OS); - if (!isa<SCEVCouldNotCompute>(AtUse)) { + const SCEV *SV = SE.getSCEV(&I); + SV->print(OS); + if (!isa<SCEVCouldNotCompute>(SV)) { OS << " U: "; - SE.getUnsignedRange(AtUse).print(OS); + SE.getUnsignedRange(SV).print(OS); OS << " S: "; - SE.getSignedRange(AtUse).print(OS); + SE.getSignedRange(SV).print(OS); } - } - if (L) { - OS << "\t\t" "Exits: "; - const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); - if (!SE.isLoopInvariant(ExitValue, L)) { - OS << "<<Unknown>>"; - } else { - OS << *ExitValue; + const Loop *L = LI.getLoopFor(I.getParent()); + + const SCEV *AtUse = SE.getSCEVAtScope(SV, L); + if (AtUse != SV) { + OS << " --> "; + AtUse->print(OS); + if (!isa<SCEVCouldNotCompute>(AtUse)) { + OS << " U: "; + SE.getUnsignedRange(AtUse).print(OS); + OS << " S: "; + SE.getSignedRange(AtUse).print(OS); + } } - bool First = true; - for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; + if (L) { + OS << "\t\t" "Exits: "; + const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); + if (!SE.isLoopInvariant(ExitValue, L)) { + OS << "<<Unknown>>"; } else { - OS << ", "; + OS << *ExitValue; } - Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); - } + bool First = true; + for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } - for (auto *InnerL : depth_first(L)) { - if (InnerL == L) - continue; - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; - } else { - OS << ", "; + Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); } - InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + for (auto *InnerL : depth_first(L)) { + if (InnerL == L) + continue; + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } + + InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + } + + OS << " }"; } - OS << " }"; + OS << "\n"; } - - OS << "\n"; - } + } OS << "Determining loop execution counts for: "; F.printAsOperand(OS, /*PrintType=*/false); @@ -11994,6 +12075,12 @@ ScalarEvolution ScalarEvolutionAnalysis::run(Function &F, } PreservedAnalyses +ScalarEvolutionVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { + AM.getResult<ScalarEvolutionAnalysis>(F).verify(); + return PreservedAnalyses::all(); +} + +PreservedAnalyses ScalarEvolutionPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { AM.getResult<ScalarEvolutionAnalysis>(F).print(OS); return PreservedAnalyses::all(); @@ -12462,7 +12549,7 @@ PredicatedScalarEvolution::PredicatedScalarEvolution( const PredicatedScalarEvolution &Init) : RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), Preds(Init.Preds), Generation(Init.Generation), BackedgeCount(Init.BackedgeCount) { - for (const auto &I : Init.FlagsMap) + for (auto I : Init.FlagsMap) FlagsMap.insert(I); } diff --git a/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp b/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp index 96da0a24cddd4..79640256f6955 100644 --- a/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp +++ b/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp @@ -19,6 +19,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/InitializePasses.h" using namespace llvm; AliasResult SCEVAAResult::alias(const MemoryLocation &LocA, diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp index bceec921188e2..dc5d02aa3a3cb 100644 --- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp @@ -414,7 +414,7 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, // without the other. SplitAddRecs(Ops, Ty, SE); - Type *IntPtrTy = DL.getIntPtrType(PTy); + Type *IntIdxTy = DL.getIndexType(PTy); // Descend down the pointer's type and attempt to convert the other // operands into GEP indices, at each level. The first index in a GEP @@ -426,7 +426,7 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, // array indexing. SmallVector<const SCEV *, 8> ScaledOps; if (ElTy->isSized()) { - const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy); + const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy); if (!ElSize->isZero()) { SmallVector<const SCEV *, 8> NewOps; for (const SCEV *Op : Ops) { diff --git a/llvm/lib/Analysis/ScopedNoAliasAA.cpp b/llvm/lib/Analysis/ScopedNoAliasAA.cpp index 094e4a3d5dc8d..8928678d6ab21 100644 --- a/llvm/lib/Analysis/ScopedNoAliasAA.cpp +++ b/llvm/lib/Analysis/ScopedNoAliasAA.cpp @@ -37,6 +37,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" diff --git a/llvm/lib/Analysis/StackSafetyAnalysis.cpp b/llvm/lib/Analysis/StackSafetyAnalysis.cpp index 1b36386989500..7f5bedabbd80b 100644 --- a/llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ b/llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -13,6 +13,8 @@ #include "llvm/IR/CallSite.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/InitializePasses.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; diff --git a/llvm/lib/Analysis/TargetLibraryInfo.cpp b/llvm/lib/Analysis/TargetLibraryInfo.cpp index 2309696980540..c7238db43aab6 100644 --- a/llvm/lib/Analysis/TargetLibraryInfo.cpp +++ b/llvm/lib/Analysis/TargetLibraryInfo.cpp @@ -13,6 +13,7 @@ #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/ADT/Triple.h" #include "llvm/IR/Constants.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" using namespace llvm; @@ -378,10 +379,8 @@ static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, case Triple::TvOS: case Triple::WatchOS: TLI.setUnavailable(LibFunc_exp10l); - if (!T.isWatchOS() && (T.isOSVersionLT(7, 0) || - (T.isOSVersionLT(9, 0) && - (T.getArch() == Triple::x86 || - T.getArch() == Triple::x86_64)))) { + if (!T.isWatchOS() && + (T.isOSVersionLT(7, 0) || (T.isOSVersionLT(9, 0) && T.isX86()))) { TLI.setUnavailable(LibFunc_exp10); TLI.setUnavailable(LibFunc_exp10f); } else { @@ -1587,22 +1586,12 @@ StringRef TargetLibraryInfoImpl::getScalarizedFunction(StringRef F, return I->ScalarFnName; } -TargetLibraryInfo TargetLibraryAnalysis::run(Function &F, +TargetLibraryInfo TargetLibraryAnalysis::run(const Function &F, FunctionAnalysisManager &) { - if (PresetInfoImpl) - return TargetLibraryInfo(*PresetInfoImpl); - - return TargetLibraryInfo( - lookupInfoImpl(Triple(F.getParent()->getTargetTriple()))); -} - -TargetLibraryInfoImpl &TargetLibraryAnalysis::lookupInfoImpl(const Triple &T) { - std::unique_ptr<TargetLibraryInfoImpl> &Impl = - Impls[T.normalize()]; - if (!Impl) - Impl.reset(new TargetLibraryInfoImpl(T)); - - return *Impl; + if (!BaselineInfoImpl) + BaselineInfoImpl = + TargetLibraryInfoImpl(Triple(F.getParent()->getTargetTriple())); + return TargetLibraryInfo(*BaselineInfoImpl, &F); } unsigned TargetLibraryInfoImpl::getWCharSize(const Module &M) const { @@ -1613,18 +1602,18 @@ unsigned TargetLibraryInfoImpl::getWCharSize(const Module &M) const { } TargetLibraryInfoWrapperPass::TargetLibraryInfoWrapperPass() - : ImmutablePass(ID), TLIImpl(), TLI(TLIImpl) { + : ImmutablePass(ID), TLA(TargetLibraryInfoImpl()) { initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry()); } TargetLibraryInfoWrapperPass::TargetLibraryInfoWrapperPass(const Triple &T) - : ImmutablePass(ID), TLIImpl(T), TLI(TLIImpl) { + : ImmutablePass(ID), TLA(TargetLibraryInfoImpl(T)) { initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry()); } TargetLibraryInfoWrapperPass::TargetLibraryInfoWrapperPass( const TargetLibraryInfoImpl &TLIImpl) - : ImmutablePass(ID), TLIImpl(TLIImpl), TLI(this->TLIImpl) { + : ImmutablePass(ID), TLA(TLIImpl) { initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry()); } @@ -1636,3 +1625,19 @@ INITIALIZE_PASS(TargetLibraryInfoWrapperPass, "targetlibinfo", char TargetLibraryInfoWrapperPass::ID = 0; void TargetLibraryInfoWrapperPass::anchor() {} + +unsigned TargetLibraryInfoImpl::getWidestVF(StringRef ScalarF) const { + ScalarF = sanitizeFunctionName(ScalarF); + if (ScalarF.empty()) + return 1; + + unsigned VF = 1; + std::vector<VecDesc>::const_iterator I = + llvm::lower_bound(VectorDescs, ScalarF, compareWithScalarFnName); + while (I != VectorDescs.end() && StringRef(I->ScalarFnName) == ScalarF) { + if (I->VectorizationFactor > VF) + VF = I->VectorizationFactor; + ++I; + } + return VF; +} diff --git a/llvm/lib/Analysis/TargetTransformInfo.cpp b/llvm/lib/Analysis/TargetTransformInfo.cpp index c9c294873ea60..f2c63f789d892 100644 --- a/llvm/lib/Analysis/TargetTransformInfo.cpp +++ b/llvm/lib/Analysis/TargetTransformInfo.cpp @@ -7,9 +7,11 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/TargetTransformInfoImpl.h" -#include "llvm/IR/CallSite.h" #include "llvm/IR/CFG.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" @@ -17,10 +19,9 @@ #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/LoopIterator.h" #include <utility> using namespace llvm; @@ -194,9 +195,10 @@ int TargetTransformInfo::getIntrinsicCost( } unsigned -TargetTransformInfo::getEstimatedNumberOfCaseClusters(const SwitchInst &SI, - unsigned &JTSize) const { - return TTIImpl->getEstimatedNumberOfCaseClusters(SI, JTSize); +TargetTransformInfo::getEstimatedNumberOfCaseClusters( + const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI, + BlockFrequencyInfo *BFI) const { + return TTIImpl->getEstimatedNumberOfCaseClusters(SI, JTSize, PSI, BFI); } int TargetTransformInfo::getUserCost(const User *U, @@ -242,6 +244,12 @@ bool TargetTransformInfo::isHardwareLoopProfitable( return TTIImpl->isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo); } +bool TargetTransformInfo::preferPredicateOverEpilogue(Loop *L, LoopInfo *LI, + ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *TLI, + DominatorTree *DT, const LoopAccessInfo *LAI) const { + return TTIImpl->preferPredicateOverEpilogue(L, LI, SE, AC, TLI, DT, LAI); +} + void TargetTransformInfo::getUnrollingPreferences( Loop *L, ScalarEvolution &SE, UnrollingPreferences &UP) const { return TTIImpl->getUnrollingPreferences(L, SE, UP); @@ -307,12 +315,14 @@ bool TargetTransformInfo::isLegalNTLoad(Type *DataType, Align Alignment) const { return TTIImpl->isLegalNTLoad(DataType, Alignment); } -bool TargetTransformInfo::isLegalMaskedGather(Type *DataType) const { - return TTIImpl->isLegalMaskedGather(DataType); +bool TargetTransformInfo::isLegalMaskedGather(Type *DataType, + MaybeAlign Alignment) const { + return TTIImpl->isLegalMaskedGather(DataType, Alignment); } -bool TargetTransformInfo::isLegalMaskedScatter(Type *DataType) const { - return TTIImpl->isLegalMaskedScatter(DataType); +bool TargetTransformInfo::isLegalMaskedScatter(Type *DataType, + MaybeAlign Alignment) const { + return TTIImpl->isLegalMaskedScatter(DataType, Alignment); } bool TargetTransformInfo::isLegalMaskedCompressStore(Type *DataType) const { @@ -454,16 +464,16 @@ int TargetTransformInfo::getIntImmCost(const APInt &Imm, Type *Ty) const { return Cost; } -int TargetTransformInfo::getIntImmCost(unsigned Opcode, unsigned Idx, - const APInt &Imm, Type *Ty) const { - int Cost = TTIImpl->getIntImmCost(Opcode, Idx, Imm, Ty); +int TargetTransformInfo::getIntImmCostInst(unsigned Opcode, unsigned Idx, + const APInt &Imm, Type *Ty) const { + int Cost = TTIImpl->getIntImmCostInst(Opcode, Idx, Imm, Ty); assert(Cost >= 0 && "TTI should not produce negative costs!"); return Cost; } -int TargetTransformInfo::getIntImmCost(Intrinsic::ID IID, unsigned Idx, - const APInt &Imm, Type *Ty) const { - int Cost = TTIImpl->getIntImmCost(IID, Idx, Imm, Ty); +int TargetTransformInfo::getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, + const APInt &Imm, Type *Ty) const { + int Cost = TTIImpl->getIntImmCostIntrin(IID, Idx, Imm, Ty); assert(Cost >= 0 && "TTI should not produce negative costs!"); return Cost; } @@ -584,10 +594,10 @@ TargetTransformInfo::getOperandInfo(Value *V, OperandValueProperties &OpProps) { int TargetTransformInfo::getArithmeticInstrCost( unsigned Opcode, Type *Ty, OperandValueKind Opd1Info, OperandValueKind Opd2Info, OperandValueProperties Opd1PropInfo, - OperandValueProperties Opd2PropInfo, - ArrayRef<const Value *> Args) const { - int Cost = TTIImpl->getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info, - Opd1PropInfo, Opd2PropInfo, Args); + OperandValueProperties Opd2PropInfo, ArrayRef<const Value *> Args, + const Instruction *CxtI) const { + int Cost = TTIImpl->getArithmeticInstrCost( + Opcode, Ty, Opd1Info, Opd2Info, Opd1PropInfo, Opd2PropInfo, Args, CxtI); assert(Cost >= 0 && "TTI should not produce negative costs!"); return Cost; } @@ -639,7 +649,7 @@ int TargetTransformInfo::getVectorInstrCost(unsigned Opcode, Type *Val, } int TargetTransformInfo::getMemoryOpCost(unsigned Opcode, Type *Src, - unsigned Alignment, + MaybeAlign Alignment, unsigned AddressSpace, const Instruction *I) const { assert ((I == nullptr || I->getOpcode() == Opcode) && @@ -1175,7 +1185,7 @@ int TargetTransformInfo::getInstructionThroughput(const Instruction *I) const { Op2VK = getOperandInfo(I->getOperand(1), Op2VP); SmallVector<const Value *, 2> Operands(I->operand_values()); return getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK, Op2VK, - Op1VP, Op2VP, Operands); + Op1VP, Op2VP, Operands, I); } case Instruction::FNeg: { TargetTransformInfo::OperandValueKind Op1VK, Op2VK; @@ -1185,7 +1195,7 @@ int TargetTransformInfo::getInstructionThroughput(const Instruction *I) const { Op2VP = OP_None; SmallVector<const Value *, 2> Operands(I->operand_values()); return getArithmeticInstrCost(I->getOpcode(), I->getType(), Op1VK, Op2VK, - Op1VP, Op2VP, Operands); + Op1VP, Op2VP, Operands, I); } case Instruction::Select: { const SelectInst *SI = cast<SelectInst>(I); @@ -1201,14 +1211,14 @@ int TargetTransformInfo::getInstructionThroughput(const Instruction *I) const { const StoreInst *SI = cast<StoreInst>(I); Type *ValTy = SI->getValueOperand()->getType(); return getMemoryOpCost(I->getOpcode(), ValTy, - SI->getAlignment(), - SI->getPointerAddressSpace(), I); + MaybeAlign(SI->getAlignment()), + SI->getPointerAddressSpace(), I); } case Instruction::Load: { const LoadInst *LI = cast<LoadInst>(I); return getMemoryOpCost(I->getOpcode(), I->getType(), - LI->getAlignment(), - LI->getPointerAddressSpace(), I); + MaybeAlign(LI->getAlignment()), + LI->getPointerAddressSpace(), I); } case Instruction::ZExt: case Instruction::SExt: diff --git a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp index 3b9040aa0f52a..da4520066b467 100644 --- a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -114,6 +114,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -520,23 +521,20 @@ static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) { } void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const { - if (Merge) + if (Merge) { N.TBAA = MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa)); - else - N.TBAA = getMetadata(LLVMContext::MD_tbaa); - - if (Merge) + N.TBAAStruct = nullptr; N.Scope = MDNode::getMostGenericAliasScope( N.Scope, getMetadata(LLVMContext::MD_alias_scope)); - else - N.Scope = getMetadata(LLVMContext::MD_alias_scope); - - if (Merge) N.NoAlias = MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias)); - else + } else { + N.TBAA = getMetadata(LLVMContext::MD_tbaa); + N.TBAAStruct = getMetadata(LLVMContext::MD_tbaa_struct); + N.Scope = getMetadata(LLVMContext::MD_alias_scope); N.NoAlias = getMetadata(LLVMContext::MD_noalias); + } } static const MDNode *createAccessTag(const MDNode *AccessType) { diff --git a/llvm/lib/Analysis/VFABIDemangling.cpp b/llvm/lib/Analysis/VFABIDemangling.cpp index 6fd8ae63f5f07..a331b95e818b2 100644 --- a/llvm/lib/Analysis/VFABIDemangling.cpp +++ b/llvm/lib/Analysis/VFABIDemangling.cpp @@ -6,6 +6,8 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallString.h" #include "llvm/Analysis/VectorUtils.h" using namespace llvm; @@ -26,16 +28,20 @@ ParseRet tryParseISA(StringRef &MangledName, VFISAKind &ISA) { if (MangledName.empty()) return ParseRet::Error; - ISA = StringSwitch<VFISAKind>(MangledName.take_front(1)) - .Case("n", VFISAKind::AdvancedSIMD) - .Case("s", VFISAKind::SVE) - .Case("b", VFISAKind::SSE) - .Case("c", VFISAKind::AVX) - .Case("d", VFISAKind::AVX2) - .Case("e", VFISAKind::AVX512) - .Default(VFISAKind::Unknown); - - MangledName = MangledName.drop_front(1); + if (MangledName.startswith(VFABI::_LLVM_)) { + MangledName = MangledName.drop_front(strlen(VFABI::_LLVM_)); + ISA = VFISAKind::LLVM; + } else { + ISA = StringSwitch<VFISAKind>(MangledName.take_front(1)) + .Case("n", VFISAKind::AdvancedSIMD) + .Case("s", VFISAKind::SVE) + .Case("b", VFISAKind::SSE) + .Case("c", VFISAKind::AVX) + .Case("d", VFISAKind::AVX2) + .Case("e", VFISAKind::AVX512) + .Default(VFISAKind::Unknown); + MangledName = MangledName.drop_front(1); + } return ParseRet::OK; } @@ -286,6 +292,7 @@ ParseRet tryParseAlign(StringRef &ParseString, Align &Alignment) { // Format of the ABI name: // _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)] Optional<VFInfo> VFABI::tryDemangleForVFABI(StringRef MangledName) { + const StringRef OriginalName = MangledName; // Assume there is no custom name <redirection>, and therefore the // vector name consists of // _ZGV<isa><mask><vlen><parameters>_<scalarname>. @@ -338,7 +345,7 @@ Optional<VFInfo> VFABI::tryDemangleForVFABI(StringRef MangledName) { } } while (ParamFound == ParseRet::OK); - // A valid MangledName mus have at least one valid entry in the + // A valid MangledName must have at least one valid entry in the // <parameters>. if (Parameters.empty()) return None; @@ -369,6 +376,11 @@ Optional<VFInfo> VFABI::tryDemangleForVFABI(StringRef MangledName) { return None; } + // LLVM internal mapping via the TargetLibraryInfo (TLI) must be + // redirected to an existing name. + if (ISA == VFISAKind::LLVM && VectorName == OriginalName) + return None; + // When <mask> is "M", we need to add a parameter that is used as // global predicate for the function. if (IsMasked) { @@ -390,8 +402,8 @@ Optional<VFInfo> VFABI::tryDemangleForVFABI(StringRef MangledName) { assert(Parameters.back().ParamKind == VFParamKind::GlobalPredicate && "The global predicate must be the last parameter"); - const VFShape Shape({VF, IsScalable, ISA, Parameters}); - return VFInfo({Shape, ScalarName, VectorName}); + const VFShape Shape({VF, IsScalable, Parameters}); + return VFInfo({Shape, ScalarName, VectorName, ISA}); } VFParamKind VFABI::getVFParamKindFromString(const StringRef Token) { diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index bbf3899918367..ad6765e2514b4 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -51,6 +51,8 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" +#include "llvm/IR/IntrinsicsAArch64.h" +#include "llvm/IR/IntrinsicsX86.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" @@ -88,7 +90,7 @@ static unsigned getBitWidth(Type *Ty, const DataLayout &DL) { if (unsigned BitWidth = Ty->getScalarSizeInBits()) return BitWidth; - return DL.getIndexTypeSizeInBits(Ty); + return DL.getPointerTypeSizeInBits(Ty); } namespace { @@ -564,17 +566,83 @@ bool llvm::isValidAssumeForContext(const Instruction *Inv, if (Inv == CxtI) return false; - // The context comes first, but they're both in the same block. Make sure - // there is nothing in between that might interrupt the control flow. - for (BasicBlock::const_iterator I = - std::next(BasicBlock::const_iterator(CxtI)), IE(Inv); - I != IE; ++I) + // The context comes first, but they're both in the same block. + // Make sure there is nothing in between that might interrupt + // the control flow, not even CxtI itself. + for (BasicBlock::const_iterator I(CxtI), IE(Inv); I != IE; ++I) if (!isGuaranteedToTransferExecutionToSuccessor(&*I)) return false; return !isEphemeralValueOf(Inv, CxtI); } +static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) { + // Use of assumptions is context-sensitive. If we don't have a context, we + // cannot use them! + if (!Q.AC || !Q.CxtI) + return false; + + // Note that the patterns below need to be kept in sync with the code + // in AssumptionCache::updateAffectedValues. + + auto CmpExcludesZero = [V](ICmpInst *Cmp) { + auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V))); + + Value *RHS; + CmpInst::Predicate Pred; + if (!match(Cmp, m_c_ICmp(Pred, m_V, m_Value(RHS)))) + return false; + // Canonicalize 'v' to be on the LHS of the comparison. + if (Cmp->getOperand(1) != RHS) + Pred = CmpInst::getSwappedPredicate(Pred); + + // assume(v u> y) -> assume(v != 0) + if (Pred == ICmpInst::ICMP_UGT) + return true; + + // assume(v != 0) + // We special-case this one to ensure that we handle `assume(v != null)`. + if (Pred == ICmpInst::ICMP_NE) + return match(RHS, m_Zero()); + + // All other predicates - rely on generic ConstantRange handling. + ConstantInt *CI; + if (!match(RHS, m_ConstantInt(CI))) + return false; + ConstantRange RHSRange(CI->getValue()); + ConstantRange TrueValues = + ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); + return !TrueValues.contains(APInt::getNullValue(CI->getBitWidth())); + }; + + for (auto &AssumeVH : Q.AC->assumptionsFor(V)) { + if (!AssumeVH) + continue; + CallInst *I = cast<CallInst>(AssumeVH); + assert(I->getFunction() == Q.CxtI->getFunction() && + "Got assumption for the wrong function!"); + if (Q.isExcluded(I)) + continue; + + // Warning: This loop can end up being somewhat performance sensitive. + // We're running this loop for once for each value queried resulting in a + // runtime of ~O(#assumes * #values). + + assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && + "must be an assume intrinsic"); + + Value *Arg = I->getArgOperand(0); + ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg); + if (!Cmp) + continue; + + if (CmpExcludesZero(Cmp) && isValidAssumeForContext(I, Q.CxtI, Q.DT)) + return true; + } + + return false; +} + static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, unsigned Depth, const Query &Q) { // Use of assumptions is context-sensitive. If we don't have a context, we @@ -915,7 +983,7 @@ static void computeKnownBitsFromShiftOperator( // If the shift amount could be greater than or equal to the bit-width of the // LHS, the value could be poison, but bail out because the check below is // expensive. TODO: Should we just carry on? - if ((~Known.Zero).uge(BitWidth)) { + if (Known.getMaxValue().uge(BitWidth)) { Known.resetAll(); return; } @@ -1135,7 +1203,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, // which fall through here. Type *ScalarTy = SrcTy->getScalarType(); SrcBitWidth = ScalarTy->isPointerTy() ? - Q.DL.getIndexTypeSizeInBits(ScalarTy) : + Q.DL.getPointerTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy); assert(SrcBitWidth && "SrcBitWidth can't be zero"); @@ -1353,6 +1421,8 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, for (unsigned i = 0; i != 2; ++i) { Value *L = P->getIncomingValue(i); Value *R = P->getIncomingValue(!i); + Instruction *RInst = P->getIncomingBlock(!i)->getTerminator(); + Instruction *LInst = P->getIncomingBlock(i)->getTerminator(); Operator *LU = dyn_cast<Operator>(L); if (!LU) continue; @@ -1374,13 +1444,22 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, L = LL; else continue; // Check for recurrence with L and R flipped. + + // Change the context instruction to the "edge" that flows into the + // phi. This is important because that is where the value is actually + // "evaluated" even though it is used later somewhere else. (see also + // D69571). + Query RecQ = Q; + // Ok, we have a PHI of the form L op= R. Check for low // zero bits. - computeKnownBits(R, Known2, Depth + 1, Q); + RecQ.CxtI = RInst; + computeKnownBits(R, Known2, Depth + 1, RecQ); // We need to take the minimum number of known bits KnownBits Known3(Known); - computeKnownBits(L, Known3, Depth + 1, Q); + RecQ.CxtI = LInst; + computeKnownBits(L, Known3, Depth + 1, RecQ); Known.Zero.setLowBits(std::min(Known2.countMinTrailingZeros(), Known3.countMinTrailingZeros())); @@ -1436,14 +1515,22 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, Known.Zero.setAllBits(); Known.One.setAllBits(); - for (Value *IncValue : P->incoming_values()) { + for (unsigned u = 0, e = P->getNumIncomingValues(); u < e; ++u) { + Value *IncValue = P->getIncomingValue(u); // Skip direct self references. if (IncValue == P) continue; + // Change the context instruction to the "edge" that flows into the + // phi. This is important because that is where the value is actually + // "evaluated" even though it is used later somewhere else. (see also + // D69571). + Query RecQ = Q; + RecQ.CxtI = P->getIncomingBlock(u)->getTerminator(); + Known2 = KnownBits(BitWidth); // Recurse, but cap the recursion to one level, because we don't // want to waste time spinning around in loops. - computeKnownBits(IncValue, Known2, MaxDepth - 1, Q); + computeKnownBits(IncValue, Known2, MaxDepth - 1, RecQ); Known.Zero &= Known2.Zero; Known.One &= Known2.One; // If all bits have been ruled out, there's no need to check @@ -1643,7 +1730,7 @@ void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, Type *ScalarTy = V->getType()->getScalarType(); unsigned ExpectedWidth = ScalarTy->isPointerTy() ? - Q.DL.getIndexTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy); + Q.DL.getPointerTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy); assert(ExpectedWidth == BitWidth && "V and Known should have same BitWidth"); (void)BitWidth; (void)ExpectedWidth; @@ -1902,8 +1989,8 @@ static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth, static bool isKnownNonNullFromDominatingCondition(const Value *V, const Instruction *CtxI, const DominatorTree *DT) { - assert(V->getType()->isPointerTy() && "V must be pointer type"); - assert(!isa<ConstantData>(V) && "Did not expect ConstantPointerNull"); + if (isa<Constant>(V)) + return false; if (!CtxI || !DT) return false; @@ -1924,6 +2011,15 @@ static bool isKnownNonNullFromDominatingCondition(const Value *V, Arg.hasNonNullAttr() && DT->dominates(CS.getInstruction(), CtxI)) return true; + // If the value is used as a load/store, then the pointer must be non null. + if (V == getLoadStorePointerOperand(U)) { + const Instruction *I = cast<Instruction>(U); + if (!NullPointerIsDefined(I->getFunction(), + V->getType()->getPointerAddressSpace()) && + DT->dominates(I, CtxI)) + return true; + } + // Consider only compare instructions uniquely controlling a branch CmpInst::Predicate Pred; if (!match(const_cast<User *>(U), @@ -2050,6 +2146,9 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) { } } + if (isKnownNonZeroFromAssume(V, Q)) + return true; + // Some of the tests below are recursive, so bail out if we hit the limit. if (Depth++ >= MaxDepth) return false; @@ -2078,12 +2177,11 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) { } } + if (isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT)) + return true; // Check for recursive pointer simplifications. if (V->getType()->isPointerTy()) { - if (isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT)) - return true; - // Look through bitcast operations, GEPs, and int2ptr instructions as they // do not alter the value, or at least not the nullness property of the // value, e.g., int2ptr is allowed to zero/sign extend the value. @@ -2380,7 +2478,7 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth, Type *ScalarTy = V->getType()->getScalarType(); unsigned TyBits = ScalarTy->isPointerTy() ? - Q.DL.getIndexTypeSizeInBits(ScalarTy) : + Q.DL.getPointerTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy); unsigned Tmp, Tmp2; @@ -3095,6 +3193,58 @@ bool llvm::SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI) { return cannotBeOrderedLessThanZeroImpl(V, TLI, true, 0); } +bool llvm::isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, + unsigned Depth) { + assert(V->getType()->isFPOrFPVectorTy() && "Querying for Inf on non-FP type"); + + // If we're told that infinities won't happen, assume they won't. + if (auto *FPMathOp = dyn_cast<FPMathOperator>(V)) + if (FPMathOp->hasNoInfs()) + return true; + + // Handle scalar constants. + if (auto *CFP = dyn_cast<ConstantFP>(V)) + return !CFP->isInfinity(); + + if (Depth == MaxDepth) + return false; + + if (auto *Inst = dyn_cast<Instruction>(V)) { + switch (Inst->getOpcode()) { + case Instruction::Select: { + return isKnownNeverInfinity(Inst->getOperand(1), TLI, Depth + 1) && + isKnownNeverInfinity(Inst->getOperand(2), TLI, Depth + 1); + } + case Instruction::UIToFP: + // If the input type fits into the floating type the result is finite. + return ilogb(APFloat::getLargest( + Inst->getType()->getScalarType()->getFltSemantics())) >= + (int)Inst->getOperand(0)->getType()->getScalarSizeInBits(); + default: + break; + } + } + + // Bail out for constant expressions, but try to handle vector constants. + if (!V->getType()->isVectorTy() || !isa<Constant>(V)) + return false; + + // For vectors, verify that each element is not infinity. + unsigned NumElts = V->getType()->getVectorNumElements(); + for (unsigned i = 0; i != NumElts; ++i) { + Constant *Elt = cast<Constant>(V)->getAggregateElement(i); + if (!Elt) + return false; + if (isa<UndefValue>(Elt)) + continue; + auto *CElt = dyn_cast<ConstantFP>(Elt); + if (!CElt || CElt->isInfinity()) + return false; + } + // All elements were confirmed non-infinity or undefined. + return true; +} + bool llvm::isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth) { assert(V->getType()->isFPOrFPVectorTy() && "Querying for NaN on non-FP type"); @@ -3114,13 +3264,26 @@ bool llvm::isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, if (auto *Inst = dyn_cast<Instruction>(V)) { switch (Inst->getOpcode()) { case Instruction::FAdd: - case Instruction::FMul: case Instruction::FSub: + // Adding positive and negative infinity produces NaN. + return isKnownNeverNaN(Inst->getOperand(0), TLI, Depth + 1) && + isKnownNeverNaN(Inst->getOperand(1), TLI, Depth + 1) && + (isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1) || + isKnownNeverInfinity(Inst->getOperand(1), TLI, Depth + 1)); + + case Instruction::FMul: + // Zero multiplied with infinity produces NaN. + // FIXME: If neither side can be zero fmul never produces NaN. + return isKnownNeverNaN(Inst->getOperand(0), TLI, Depth + 1) && + isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1) && + isKnownNeverNaN(Inst->getOperand(1), TLI, Depth + 1) && + isKnownNeverInfinity(Inst->getOperand(1), TLI, Depth + 1); + case Instruction::FDiv: - case Instruction::FRem: { - // TODO: Need isKnownNeverInfinity + case Instruction::FRem: + // FIXME: Only 0/0, Inf/Inf, Inf REM x and x REM 0 produce NaN. return false; - } + case Instruction::Select: { return isKnownNeverNaN(Inst->getOperand(1), TLI, Depth + 1) && isKnownNeverNaN(Inst->getOperand(2), TLI, Depth + 1); @@ -4222,6 +4385,20 @@ bool llvm::isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch); } +bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V) { + // If the value is a freeze instruction, then it can never + // be undef or poison. + if (isa<FreezeInst>(V)) + return true; + // TODO: Some instructions are guaranteed to return neither undef + // nor poison if their arguments are not poison/undef. + + // TODO: Deal with other Constant subclasses. + if (isa<ConstantInt>(V) || isa<GlobalVariable>(V)) + return true; + + return false; +} OverflowResult llvm::computeOverflowForSignedAdd(const AddOperator *Add, const DataLayout &DL, diff --git a/llvm/lib/Analysis/VectorUtils.cpp b/llvm/lib/Analysis/VectorUtils.cpp index 600f57ab9d716..c45ab941a1428 100644 --- a/llvm/lib/Analysis/VectorUtils.cpp +++ b/llvm/lib/Analysis/VectorUtils.cpp @@ -24,6 +24,7 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Value.h" +#include "llvm/Support/CommandLine.h" #define DEBUG_TYPE "vectorutils" @@ -1159,3 +1160,69 @@ void InterleaveGroup<Instruction>::addMetadata(Instruction *NewInst) const { propagateMetadata(NewInst, VL); } } + +void VFABI::getVectorVariantNames( + const CallInst &CI, SmallVectorImpl<std::string> &VariantMappings) { + const StringRef S = + CI.getAttribute(AttributeList::FunctionIndex, VFABI::MappingsAttrName) + .getValueAsString(); + if (S.empty()) + return; + + SmallVector<StringRef, 8> ListAttr; + S.split(ListAttr, ","); + + for (auto &S : SetVector<StringRef>(ListAttr.begin(), ListAttr.end())) { +#ifndef NDEBUG + Optional<VFInfo> Info = VFABI::tryDemangleForVFABI(S); + assert(Info.hasValue() && "Invalid name for a VFABI variant."); + assert(CI.getModule()->getFunction(Info.getValue().VectorName) && + "Vector function is missing."); +#endif + VariantMappings.push_back(S); + } +} + +bool VFShape::hasValidParameterList() const { + for (unsigned Pos = 0, NumParams = Parameters.size(); Pos < NumParams; + ++Pos) { + assert(Parameters[Pos].ParamPos == Pos && "Broken parameter list."); + + switch (Parameters[Pos].ParamKind) { + default: // Nothing to check. + break; + case VFParamKind::OMP_Linear: + case VFParamKind::OMP_LinearRef: + case VFParamKind::OMP_LinearVal: + case VFParamKind::OMP_LinearUVal: + // Compile time linear steps must be non-zero. + if (Parameters[Pos].LinearStepOrPos == 0) + return false; + break; + case VFParamKind::OMP_LinearPos: + case VFParamKind::OMP_LinearRefPos: + case VFParamKind::OMP_LinearValPos: + case VFParamKind::OMP_LinearUValPos: + // The runtime linear step must be referring to some other + // parameters in the signature. + if (Parameters[Pos].LinearStepOrPos >= int(NumParams)) + return false; + // The linear step parameter must be marked as uniform. + if (Parameters[Parameters[Pos].LinearStepOrPos].ParamKind != + VFParamKind::OMP_Uniform) + return false; + // The linear step parameter can't point at itself. + if (Parameters[Pos].LinearStepOrPos == int(Pos)) + return false; + break; + case VFParamKind::GlobalPredicate: + // The global predicate must be the unique. Can be placed anywhere in the + // signature. + for (unsigned NextPos = Pos + 1; NextPos < NumParams; ++NextPos) + if (Parameters[NextPos].ParamKind == VFParamKind::GlobalPredicate) + return false; + break; + } + } + return true; +} |