diff options
Diffstat (limited to 'lib/Analysis')
| -rw-r--r-- | lib/Analysis/AliasAnalysis.cpp | 95 | ||||
| -rw-r--r-- | lib/Analysis/AliasAnalysisEvaluator.cpp | 61 | ||||
| -rw-r--r-- | lib/Analysis/BasicAliasAnalysis.cpp | 13 | ||||
| -rw-r--r-- | lib/Analysis/CFGPrinter.cpp | 8 | ||||
| -rw-r--r-- | lib/Analysis/GlobalsModRef.cpp | 21 | ||||
| -rw-r--r-- | lib/Analysis/InlineCost.cpp | 95 | ||||
| -rw-r--r-- | lib/Analysis/LoopAccessAnalysis.cpp | 71 | ||||
| -rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 23 | ||||
| -rw-r--r-- | lib/Analysis/MemorySSA.cpp | 39 | ||||
| -rw-r--r-- | lib/Analysis/ModuleSummaryAnalysis.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/ProfileSummaryInfo.cpp | 60 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 1 | ||||
| -rw-r--r-- | lib/Analysis/TargetTransformInfo.cpp | 4 | ||||
| -rw-r--r-- | lib/Analysis/TypeBasedAliasAnalysis.cpp | 23 |
14 files changed, 297 insertions, 219 deletions
diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index dd2db1e5b27bc..55df667141788 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -133,9 +133,9 @@ ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) { } ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) { - // We may have two calls + // We may have two calls. if (auto CS = ImmutableCallSite(I)) { - // Check if the two calls modify the same memory + // Check if the two calls modify the same memory. return getModRefInfo(CS, Call); } else if (I->isFenceLike()) { // If this is a fence, just return ModRef. @@ -179,6 +179,7 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS, if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) { bool DoesAlias = false; + bool IsMustAlias = true; ModRefInfo AllArgsMask = ModRefInfo::NoModRef; if (doesAccessArgPointees(MRB)) { for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) { @@ -193,6 +194,8 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS, DoesAlias = true; AllArgsMask = unionModRef(AllArgsMask, ArgMask); } + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= (ArgAlias == MustAlias); } } // Return NoModRef if no alias found with any argument. @@ -200,6 +203,8 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS, return ModRefInfo::NoModRef; // Logical & between other AA analyses and argument analysis. Result = intersectModRef(Result, AllArgsMask); + // If only MustAlias found above, set Must bit. + Result = IsMustAlias ? setMust(Result) : clearMust(Result); } // If Loc is a constant memory location, the call definitely could not @@ -251,6 +256,7 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1, if (onlyAccessesArgPointees(CS2B)) { ModRefInfo R = ModRefInfo::NoModRef; if (doesAccessArgPointees(CS2B)) { + bool IsMustAlias = true; for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { const Value *Arg = *I; if (!Arg->getType()->isPointerTy()) @@ -274,10 +280,19 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1, ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc); ArgMask = intersectModRef(ArgMask, ModRefCS1); + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= isMustSet(ModRefCS1); + R = intersectModRef(unionModRef(R, ArgMask), Result); - if (R == Result) + if (R == Result) { + // On early exit, not all args were checked, cannot set Must. + if (I + 1 != E) + IsMustAlias = false; break; + } } + // If Alias found and only MustAlias found above, set Must bit. + R = IsMustAlias ? setMust(R) : clearMust(R); } return R; } @@ -287,6 +302,7 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1, if (onlyAccessesArgPointees(CS1B)) { ModRefInfo R = ModRefInfo::NoModRef; if (doesAccessArgPointees(CS1B)) { + bool IsMustAlias = true; for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { const Value *Arg = *I; if (!Arg->getType()->isPointerTy()) @@ -303,9 +319,18 @@ ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1, (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2))) R = intersectModRef(unionModRef(R, ArgModRefCS1), Result); - if (R == Result) + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= isMustSet(ModRefCS2); + + if (R == Result) { + // On early exit, not all args were checked, cannot set Must. + if (I + 1 != E) + IsMustAlias = false; break; + } } + // If Alias found and only MustAlias found above, set Must bit. + R = IsMustAlias ? setMust(R) : clearMust(R); } return R; } @@ -353,9 +378,13 @@ ModRefInfo AAResults::getModRefInfo(const LoadInst *L, // If the load address doesn't alias the given address, it doesn't read // or write the specified memory. - if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc)) - return ModRefInfo::NoModRef; - + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(L), Loc); + if (AR == NoAlias) + return ModRefInfo::NoModRef; + if (AR == MustAlias) + return ModRefInfo::MustRef; + } // Otherwise, a load just reads. return ModRefInfo::Ref; } @@ -367,15 +396,20 @@ ModRefInfo AAResults::getModRefInfo(const StoreInst *S, return ModRefInfo::ModRef; if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(S), Loc); // If the store address cannot alias the pointer in question, then the // specified memory cannot be modified by the store. - if (!alias(MemoryLocation::get(S), Loc)) + if (AR == NoAlias) return ModRefInfo::NoModRef; // If the pointer is a pointer to constant memory, then it could not have // been modified by this store. if (pointsToConstantMemory(Loc)) return ModRefInfo::NoModRef; + + // If the store address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustMod; } // Otherwise, a store just writes. @@ -393,15 +427,20 @@ ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Lo ModRefInfo AAResults::getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc) { if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(V), Loc); // If the va_arg address cannot alias the pointer in question, then the // specified memory cannot be accessed by the va_arg. - if (!alias(MemoryLocation::get(V), Loc)) + if (AR == NoAlias) return ModRefInfo::NoModRef; // If the pointer is a pointer to constant memory, then it could not have // been modified by this va_arg. if (pointsToConstantMemory(Loc)) return ModRefInfo::NoModRef; + + // If the va_arg aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; } // Otherwise, a va_arg reads and writes. @@ -440,9 +479,17 @@ ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX, if (isStrongerThanMonotonic(CX->getSuccessOrdering())) return ModRefInfo::ModRef; - // If the cmpxchg address does not alias the location, it does not access it. - if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc)) - return ModRefInfo::NoModRef; + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(CX), Loc); + // If the cmpxchg address does not alias the location, it does not access + // it. + if (AR == NoAlias) + return ModRefInfo::NoModRef; + + // If the cmpxchg address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; + } return ModRefInfo::ModRef; } @@ -453,9 +500,17 @@ ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW, if (isStrongerThanMonotonic(RMW->getOrdering())) return ModRefInfo::ModRef; - // If the atomicrmw address does not alias the location, it does not access it. - if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc)) - return ModRefInfo::NoModRef; + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(RMW), Loc); + // If the atomicrmw address does not alias the location, it does not access + // it. + if (AR == NoAlias) + return ModRefInfo::NoModRef; + + // If the atomicrmw address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; + } return ModRefInfo::ModRef; } @@ -493,6 +548,8 @@ ModRefInfo AAResults::callCapturesBefore(const Instruction *I, unsigned ArgNo = 0; ModRefInfo R = ModRefInfo::NoModRef; + bool MustAlias = true; + // Set flag only if no May found and all operands processed. for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end(); CI != CE; ++CI, ++ArgNo) { // Only look at the no-capture or byval pointer arguments. If this @@ -503,11 +560,14 @@ ModRefInfo AAResults::callCapturesBefore(const Instruction *I, ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo))) continue; + AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object)); // If this is a no-capture pointer argument, see if we can tell that it // is impossible to alias the pointer we're checking. If not, we have to // assume that the call could touch the pointer, even though it doesn't // escape. - if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object))) + if (AR != MustAlias) + MustAlias = false; + if (AR == NoAlias) continue; if (CS.doesNotAccessMemory(ArgNo)) continue; @@ -515,9 +575,10 @@ ModRefInfo AAResults::callCapturesBefore(const Instruction *I, R = ModRefInfo::Ref; continue; } + // Not returning MustModRef since we have not seen all the arguments. return ModRefInfo::ModRef; } - return R; + return MustAlias ? setMust(R) : clearMust(R); } /// canBasicBlockModify - Return true if it is possible for execution of the diff --git a/lib/Analysis/AliasAnalysisEvaluator.cpp b/lib/Analysis/AliasAnalysisEvaluator.cpp index 423acf739f58d..f737cecc43d14 100644 --- a/lib/Analysis/AliasAnalysisEvaluator.cpp +++ b/lib/Analysis/AliasAnalysisEvaluator.cpp @@ -31,9 +31,13 @@ static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden); static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden); -static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden); +static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); +static cl::opt<bool> PrintMust("print-must", cl::ReallyHidden); +static cl::opt<bool> PrintMustRef("print-mustref", cl::ReallyHidden); +static cl::opt<bool> PrintMustMod("print-mustmod", cl::ReallyHidden); +static cl::opt<bool> PrintMustModRef("print-mustmodref", cl::ReallyHidden); static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden); @@ -262,6 +266,25 @@ void AAEvaluator::runInternal(Function &F, AAResults &AA) { F.getParent()); ++ModRefCount; break; + case ModRefInfo::Must: + PrintModRefResults("Must", PrintMust, I, Pointer, F.getParent()); + ++MustCount; + break; + case ModRefInfo::MustMod: + PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, I, Pointer, + F.getParent()); + ++MustModCount; + break; + case ModRefInfo::MustRef: + PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, I, Pointer, + F.getParent()); + ++MustRefCount; + break; + case ModRefInfo::MustModRef: + PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, I, + Pointer, F.getParent()); + ++MustModRefCount; + break; } } } @@ -288,6 +311,25 @@ void AAEvaluator::runInternal(Function &F, AAResults &AA) { PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); ++ModRefCount; break; + case ModRefInfo::Must: + PrintModRefResults("Must", PrintMust, *C, *D, F.getParent()); + ++MustCount; + break; + case ModRefInfo::MustMod: + PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, *C, *D, + F.getParent()); + ++MustModCount; + break; + case ModRefInfo::MustRef: + PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, *C, *D, + F.getParent()); + ++MustRefCount; + break; + case ModRefInfo::MustModRef: + PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, *C, *D, + F.getParent()); + ++MustModRefCount; + break; } } } @@ -325,7 +367,8 @@ AAEvaluator::~AAEvaluator() { } // Display the summary for mod/ref analysis - int64_t ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount; + int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount + + MustCount + MustRefCount + MustModCount + MustModRefCount; if (ModRefSum == 0) { errs() << " Alias Analysis Mod/Ref Evaluator Summary: no " "mod/ref!\n"; @@ -339,10 +382,22 @@ AAEvaluator::~AAEvaluator() { PrintPercent(RefCount, ModRefSum); errs() << " " << ModRefCount << " mod & ref responses "; PrintPercent(ModRefCount, ModRefSum); + errs() << " " << MustCount << " must responses "; + PrintPercent(MustCount, ModRefSum); + errs() << " " << MustModCount << " must mod responses "; + PrintPercent(MustModCount, ModRefSum); + errs() << " " << MustRefCount << " must ref responses "; + PrintPercent(MustRefCount, ModRefSum); + errs() << " " << MustModRefCount << " must mod & ref responses "; + PrintPercent(MustModRefCount, ModRefSum); errs() << " Alias Analysis Evaluator Mod/Ref Summary: " << NoModRefCount * 100 / ModRefSum << "%/" << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum - << "%/" << ModRefCount * 100 / ModRefSum << "%\n"; + << "%/" << ModRefCount * 100 / ModRefSum << "%/" + << MustCount * 100 / ModRefSum << "%/" + << MustRefCount * 100 / ModRefSum << "%/" + << MustModCount * 100 / ModRefSum << "%/" + << MustModRefCount * 100 / ModRefSum << "%\n"; } } diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 81b9f842249e1..537813b6b752f 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -781,6 +781,7 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS, // Optimistically assume that call doesn't touch Object and check this // assumption in the following loop. ModRefInfo Result = ModRefInfo::NoModRef; + bool IsMustAlias = true; unsigned OperandNo = 0; for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end(); @@ -802,7 +803,8 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS, // is impossible to alias the pointer we're checking. AliasResult AR = getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object)); - + if (AR != MustAlias) + IsMustAlias = false; // Operand doesnt alias 'Object', continue looking for other aliases if (AR == NoAlias) continue; @@ -818,13 +820,20 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS, continue; } // This operand aliases 'Object' and call reads and writes into it. + // Setting ModRef will not yield an early return below, MustAlias is not + // used further. Result = ModRefInfo::ModRef; break; } + // No operand aliases, reset Must bit. Add below if at least one aliases + // and all aliases found are MustAlias. + if (isNoModRef(Result)) + IsMustAlias = false; + // Early return if we improved mod ref information if (!isModAndRefSet(Result)) - return Result; + return IsMustAlias ? setMust(Result) : clearMust(Result); } // If the CallSite is to malloc or calloc, we can assume that it doesn't diff --git a/lib/Analysis/CFGPrinter.cpp b/lib/Analysis/CFGPrinter.cpp index a85af6c9c93f0..fb261755e5d1d 100644 --- a/lib/Analysis/CFGPrinter.cpp +++ b/lib/Analysis/CFGPrinter.cpp @@ -82,7 +82,7 @@ PreservedAnalyses CFGOnlyViewerPass::run(Function &F, return PreservedAnalyses::all(); } -static void writeCFGToDotFile(Function &F) { +static void writeCFGToDotFile(Function &F, bool CFGOnly = false) { std::string Filename = ("cfg." + F.getName() + ".dot").str(); errs() << "Writing '" << Filename << "'..."; @@ -90,7 +90,7 @@ static void writeCFGToDotFile(Function &F) { raw_fd_ostream File(Filename, EC, sys::fs::F_Text); if (!EC) - WriteGraph(File, (const Function*)&F); + WriteGraph(File, (const Function*)&F, CFGOnly); else errs() << " error opening file for writing!"; errs() << "\n"; @@ -134,7 +134,7 @@ namespace { } bool runOnFunction(Function &F) override { - writeCFGToDotFile(F); + writeCFGToDotFile(F, /*CFGOnly=*/true); return false; } void print(raw_ostream &OS, const Module* = nullptr) const override {} @@ -152,7 +152,7 @@ INITIALIZE_PASS(CFGOnlyPrinterLegacyPass, "dot-cfg-only", PreservedAnalyses CFGOnlyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { - writeCFGToDotFile(F); + writeCFGToDotFile(F, /*CFGOnly=*/true); return PreservedAnalyses::all(); } diff --git a/lib/Analysis/GlobalsModRef.cpp b/lib/Analysis/GlobalsModRef.cpp index 23109c67e5c3c..daee93267f56d 100644 --- a/lib/Analysis/GlobalsModRef.cpp +++ b/lib/Analysis/GlobalsModRef.cpp @@ -85,12 +85,17 @@ class GlobalsAAResult::FunctionInfo { /// The bit that flags that this function may read any global. This is /// chosen to mix together with ModRefInfo bits. /// FIXME: This assumes ModRefInfo lattice will remain 4 bits! + /// It overlaps with ModRefInfo::Must bit! + /// FunctionInfo.getModRefInfo() masks out everything except ModRef so + /// this remains correct, but the Must info is lost. enum { MayReadAnyGlobal = 4 }; /// Checks to document the invariants of the bit packing here. - static_assert((MayReadAnyGlobal & static_cast<int>(ModRefInfo::ModRef)) == 0, + static_assert((MayReadAnyGlobal & static_cast<int>(ModRefInfo::MustModRef)) == + 0, "ModRef and the MayReadAnyGlobal flag bits overlap."); - static_assert(((MayReadAnyGlobal | static_cast<int>(ModRefInfo::ModRef)) >> + static_assert(((MayReadAnyGlobal | + static_cast<int>(ModRefInfo::MustModRef)) >> AlignedMapPointerTraits::NumLowBitsAvailable) == 0, "Insufficient low bits to store our flag and ModRef info."); @@ -125,14 +130,22 @@ public: return *this; } + /// This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return + /// the corresponding ModRefInfo. It must align in functionality with + /// clearMust(). + ModRefInfo globalClearMayReadAnyGlobal(int I) const { + return ModRefInfo((I & static_cast<int>(ModRefInfo::ModRef)) | + static_cast<int>(ModRefInfo::NoModRef)); + } + /// Returns the \c ModRefInfo info for this function. ModRefInfo getModRefInfo() const { - return ModRefInfo(Info.getInt() & static_cast<int>(ModRefInfo::ModRef)); + return globalClearMayReadAnyGlobal(Info.getInt()); } /// Adds new \c ModRefInfo for this function to its state. void addModRefInfo(ModRefInfo NewMRI) { - Info.setInt(Info.getInt() | static_cast<int>(NewMRI)); + Info.setInt(Info.getInt() | static_cast<int>(setMust(NewMRI))); } /// Returns whether this function may read any global variable, and we don't diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp index fba96c8976a69..b0cb29203a5a4 100644 --- a/lib/Analysis/InlineCost.cpp +++ b/lib/Analysis/InlineCost.cpp @@ -249,8 +249,6 @@ class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { bool visitCastInst(CastInst &I); bool visitUnaryInstruction(UnaryInstruction &I); bool visitCmpInst(CmpInst &I); - bool visitAnd(BinaryOperator &I); - bool visitOr(BinaryOperator &I); bool visitSub(BinaryOperator &I); bool visitBinaryOperator(BinaryOperator &I); bool visitLoad(LoadInst &I); @@ -363,6 +361,7 @@ void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, void CallAnalyzer::disableLoadElimination() { if (EnableLoadElimination) { Cost += LoadEliminationCost; + LoadEliminationCost = 0; EnableLoadElimination = false; } } @@ -700,6 +699,22 @@ bool CallAnalyzer::visitCastInst(CastInst &I) { // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere. disableSROA(I.getOperand(0)); + // If this is a floating-point cast, and the target says this operation + // is expensive, this may eventually become a library call. Treat the cost + // as such. + switch (I.getOpcode()) { + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::FPToUI: + case Instruction::FPToSI: + if (TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive) + Cost += InlineConstants::CallPenalty; + default: + break; + } + return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); } @@ -1004,34 +1019,6 @@ bool CallAnalyzer::visitCmpInst(CmpInst &I) { return false; } -bool CallAnalyzer::visitOr(BinaryOperator &I) { - // This is necessary because the generic simplify instruction only works if - // both operands are constants. - for (unsigned i = 0; i < 2; ++i) { - if (ConstantInt *C = dyn_cast_or_null<ConstantInt>( - SimplifiedValues.lookup(I.getOperand(i)))) - if (C->isAllOnesValue()) { - SimplifiedValues[&I] = C; - return true; - } - } - return Base::visitOr(I); -} - -bool CallAnalyzer::visitAnd(BinaryOperator &I) { - // This is necessary because the generic simplify instruction only works if - // both operands are constants. - for (unsigned i = 0; i < 2; ++i) { - if (ConstantInt *C = dyn_cast_or_null<ConstantInt>( - SimplifiedValues.lookup(I.getOperand(i)))) - if (C->isZero()) { - SimplifiedValues[&I] = C; - return true; - } - } - return Base::visitAnd(I); -} - bool CallAnalyzer::visitSub(BinaryOperator &I) { // Try to handle a special case: we can fold computing the difference of two // constant-related pointers. @@ -1061,23 +1048,38 @@ bool CallAnalyzer::visitSub(BinaryOperator &I) { bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); - auto Evaluate = [&](SmallVectorImpl<Constant *> &COps) { - Value *SimpleV = nullptr; - if (auto FI = dyn_cast<FPMathOperator>(&I)) - SimpleV = SimplifyFPBinOp(I.getOpcode(), COps[0], COps[1], - FI->getFastMathFlags(), DL); - else - SimpleV = SimplifyBinOp(I.getOpcode(), COps[0], COps[1], DL); - return dyn_cast_or_null<Constant>(SimpleV); - }; + Constant *CLHS = dyn_cast<Constant>(LHS); + if (!CLHS) + CLHS = SimplifiedValues.lookup(LHS); + Constant *CRHS = dyn_cast<Constant>(RHS); + if (!CRHS) + CRHS = SimplifiedValues.lookup(RHS); + + Value *SimpleV = nullptr; + if (auto FI = dyn_cast<FPMathOperator>(&I)) + SimpleV = SimplifyFPBinOp(I.getOpcode(), CLHS ? CLHS : LHS, + CRHS ? CRHS : RHS, FI->getFastMathFlags(), DL); + else + SimpleV = + SimplifyBinOp(I.getOpcode(), CLHS ? CLHS : LHS, CRHS ? CRHS : RHS, DL); - if (simplifyInstruction(I, Evaluate)) + if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) + SimplifiedValues[&I] = C; + + if (SimpleV) return true; // Disable any SROA on arguments to arbitrary, unsimplified binary operators. disableSROA(LHS); disableSROA(RHS); + // If the instruction is floating point, and the target says this operation + // is expensive, this may eventually become a library call. Treat the cost + // as such. + if (I.getType()->isFloatingPointTy() && + TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive) + Cost += InlineConstants::CallPenalty; + return false; } @@ -1097,7 +1099,7 @@ bool CallAnalyzer::visitLoad(LoadInst &I) { // by any stores or calls, this load is likely to be redundant and can be // eliminated. if (EnableLoadElimination && - !LoadAddrSet.insert(I.getPointerOperand()).second) { + !LoadAddrSet.insert(I.getPointerOperand()).second && I.isUnordered()) { LoadEliminationCost += InlineConstants::InstrCost; return true; } @@ -1547,17 +1549,6 @@ bool CallAnalyzer::analyzeBlock(BasicBlock *BB, if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy()) ++NumVectorInstructions; - // If the instruction is floating point, and the target says this operation - // is expensive or the function has the "use-soft-float" attribute, this may - // eventually become a library call. Treat the cost as such. - if (I->getType()->isFloatingPointTy()) { - // If the function has the "use-soft-float" attribute, mark it as - // expensive. - if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive || - (F.getFnAttribute("use-soft-float").getValueAsString() == "true")) - Cost += InlineConstants::CallPenalty; - } - // If the instruction simplified to a constant, there is no cost to this // instruction. Visit the instructions using our InstVisitor to account for // all of the per-instruction logic. The visit tree returns true if we diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp index ed8e5e8cc489f..e141d6c58b65f 100644 --- a/lib/Analysis/LoopAccessAnalysis.cpp +++ b/lib/Analysis/LoopAccessAnalysis.cpp @@ -1107,77 +1107,6 @@ static unsigned getAddressSpaceOperand(Value *I) { return -1; } -// TODO:This API can be improved by using the permutation of given width as the -// accesses are entered into the map. -bool llvm::sortLoadAccesses(ArrayRef<Value *> VL, const DataLayout &DL, - ScalarEvolution &SE, - SmallVectorImpl<Value *> &Sorted, - SmallVectorImpl<unsigned> *Mask) { - SmallVector<std::pair<int64_t, Value *>, 4> OffValPairs; - OffValPairs.reserve(VL.size()); - Sorted.reserve(VL.size()); - - // Walk over the pointers, and map each of them to an offset relative to - // first pointer in the array. - Value *Ptr0 = getPointerOperand(VL[0]); - const SCEV *Scev0 = SE.getSCEV(Ptr0); - Value *Obj0 = GetUnderlyingObject(Ptr0, DL); - PointerType *PtrTy = dyn_cast<PointerType>(Ptr0->getType()); - uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType()); - - for (auto *Val : VL) { - // The only kind of access we care about here is load. - if (!isa<LoadInst>(Val)) - return false; - - Value *Ptr = getPointerOperand(Val); - assert(Ptr && "Expected value to have a pointer operand."); - // If a pointer refers to a different underlying object, bail - the - // pointers are by definition incomparable. - Value *CurrObj = GetUnderlyingObject(Ptr, DL); - if (CurrObj != Obj0) - return false; - - const SCEVConstant *Diff = - dyn_cast<SCEVConstant>(SE.getMinusSCEV(SE.getSCEV(Ptr), Scev0)); - // The pointers may not have a constant offset from each other, or SCEV - // may just not be smart enough to figure out they do. Regardless, - // there's nothing we can do. - if (!Diff || static_cast<unsigned>(Diff->getAPInt().abs().getSExtValue()) > - (VL.size() - 1) * Size) - return false; - - OffValPairs.emplace_back(Diff->getAPInt().getSExtValue(), Val); - } - SmallVector<unsigned, 4> UseOrder(VL.size()); - for (unsigned i = 0; i < VL.size(); i++) { - UseOrder[i] = i; - } - - // Sort the memory accesses and keep the order of their uses in UseOrder. - std::sort(UseOrder.begin(), UseOrder.end(), - [&OffValPairs](unsigned Left, unsigned Right) { - return OffValPairs[Left].first < OffValPairs[Right].first; - }); - - for (unsigned i = 0; i < VL.size(); i++) - Sorted.emplace_back(OffValPairs[UseOrder[i]].second); - - // Sort UseOrder to compute the Mask. - if (Mask) { - Mask->reserve(VL.size()); - for (unsigned i = 0; i < VL.size(); i++) - Mask->emplace_back(i); - std::sort(Mask->begin(), Mask->end(), - [&UseOrder](unsigned Left, unsigned Right) { - return UseOrder[Left] < UseOrder[Right]; - }); - } - - return true; -} - - /// Returns true if the memory operations \p A and \p B are consecutive. bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType) { diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index a6c590126c2f8..bb7bf967994c3 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -647,6 +647,7 @@ MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom( // Ok, this store might clobber the query pointer. Check to see if it is // a must alias: in this case, we want to return this as a def. + // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above. MemoryLocation StoreLoc = MemoryLocation::get(SI); // If we found a pointer, check if it could be the same as our pointer. @@ -690,7 +691,7 @@ MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom( // If necessary, perform additional analysis. if (isModAndRefSet(MR)) MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB); - switch (MR) { + switch (clearMust(MR)) { case ModRefInfo::NoModRef: // If the call has no effect on the queried pointer, just ignore it. continue; @@ -919,6 +920,14 @@ void MemoryDependenceResults::getNonLocalPointerDependency( Instruction *QueryInst, SmallVectorImpl<NonLocalDepResult> &Result) { const MemoryLocation Loc = MemoryLocation::get(QueryInst); bool isLoad = isa<LoadInst>(QueryInst); + return getNonLocalPointerDependencyFrom(QueryInst, Loc, isLoad, Result); +} + +void MemoryDependenceResults::getNonLocalPointerDependencyFrom( + Instruction *QueryInst, + const MemoryLocation &Loc, + bool isLoad, + SmallVectorImpl<NonLocalDepResult> &Result) { BasicBlock *FromBB = QueryInst->getParent(); assert(FromBB); @@ -1118,21 +1127,15 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB( // If we already have a cache entry for this CacheKey, we may need to do some // work to reconcile the cache entry and the current query. if (!Pair.second) { - if (CacheInfo->Size < Loc.Size) { - // The query's Size is greater than the cached one. Throw out the - // cached data and proceed with the query at the greater size. + if (CacheInfo->Size != Loc.Size) { + // The query's Size differs from the cached one. Throw out the + // cached data and proceed with the query at the new size. CacheInfo->Pair = BBSkipFirstBlockPair(); CacheInfo->Size = Loc.Size; for (auto &Entry : CacheInfo->NonLocalDeps) if (Instruction *Inst = Entry.getResult().getInst()) RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); CacheInfo->NonLocalDeps.clear(); - } else if (CacheInfo->Size > Loc.Size) { - // This query's Size is less than the cached one. Conservatively restart - // the query using the greater size. - return getNonLocalPointerDepFromBB( - QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, - StartBB, Result, Visited, SkipFirstBlock); } // If the query's AATags are inconsistent with the cached one, diff --git a/lib/Analysis/MemorySSA.cpp b/lib/Analysis/MemorySSA.cpp index 8fe190e8bcf80..6e9368c49d659 100644 --- a/lib/Analysis/MemorySSA.cpp +++ b/lib/Analysis/MemorySSA.cpp @@ -192,8 +192,6 @@ template <> struct DenseMapInfo<MemoryLocOrCall> { } }; -enum class Reorderability { Always, IfNoAlias, Never }; - } // end namespace llvm /// This does one-way checks to see if Use could theoretically be hoisted above @@ -202,22 +200,16 @@ enum class Reorderability { Always, IfNoAlias, Never }; /// This assumes that, for the purposes of MemorySSA, Use comes directly after /// MayClobber, with no potentially clobbering operations in between them. /// (Where potentially clobbering ops are memory barriers, aliased stores, etc.) -static Reorderability getLoadReorderability(const LoadInst *Use, - const LoadInst *MayClobber) { +static bool areLoadsReorderable(const LoadInst *Use, + const LoadInst *MayClobber) { bool VolatileUse = Use->isVolatile(); bool VolatileClobber = MayClobber->isVolatile(); // Volatile operations may never be reordered with other volatile operations. if (VolatileUse && VolatileClobber) - return Reorderability::Never; - - // The lang ref allows reordering of volatile and non-volatile operations. - // Whether an aliasing nonvolatile load and volatile load can be reordered, - // though, is ambiguous. Because it may not be best to exploit this ambiguity, - // we only allow volatile/non-volatile reordering if the volatile and - // non-volatile operations don't alias. - Reorderability Result = VolatileUse || VolatileClobber - ? Reorderability::IfNoAlias - : Reorderability::Always; + return false; + // Otherwise, volatile doesn't matter here. From the language reference: + // 'optimizers may change the order of volatile operations relative to + // non-volatile operations.'" // If a load is seq_cst, it cannot be moved above other loads. If its ordering // is weaker, it can be moved above other loads. We just need to be sure that @@ -229,9 +221,7 @@ static Reorderability getLoadReorderability(const LoadInst *Use, bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent; bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(), AtomicOrdering::Acquire); - if (SeqCstUse || MayClobberIsAcquire) - return Reorderability::Never; - return Result; + return !(SeqCstUse || MayClobberIsAcquire); } static bool instructionClobbersQuery(MemoryDef *MD, @@ -265,18 +255,9 @@ static bool instructionClobbersQuery(MemoryDef *MD, return isModOrRefSet(I); } - if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) { - if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) { - switch (getLoadReorderability(UseLoad, DefLoad)) { - case Reorderability::Always: - return false; - case Reorderability::Never: - return true; - case Reorderability::IfNoAlias: - return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad)); - } - } - } + if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) + if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) + return !areLoadsReorderable(UseLoad, DefLoad); return isModSet(AA.getModRefInfo(DefInst, UseLoc)); } diff --git a/lib/Analysis/ModuleSummaryAnalysis.cpp b/lib/Analysis/ModuleSummaryAnalysis.cpp index d54fb700200d4..10badd89a4a85 100644 --- a/lib/Analysis/ModuleSummaryAnalysis.cpp +++ b/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -454,7 +454,7 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( std::unique_ptr<BlockFrequencyInfo> BFIPtr; if (GetBFICallback) BFI = GetBFICallback(F); - else if (F.getEntryCount().hasValue()) { + else if (F.hasProfileData()) { LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; BranchProbabilityInfo BPI{F, LI}; BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); diff --git a/lib/Analysis/ProfileSummaryInfo.cpp b/lib/Analysis/ProfileSummaryInfo.cpp index 671744f93fb8f..347d093b0f61f 100644 --- a/lib/Analysis/ProfileSummaryInfo.cpp +++ b/lib/Analysis/ProfileSummaryInfo.cpp @@ -115,42 +115,62 @@ bool ProfileSummaryInfo::isFunctionEntryHot(const Function *F) { return FunctionCount && isHotCount(FunctionCount.getValue()); } -/// Returns true if the function's entry or total call edge count is hot. +/// Returns true if the function contains hot code. This can include a hot +/// function entry count, hot basic block, or (in the case of Sample PGO) +/// hot total call edge count. /// If it returns false, it either means it is not hot or it is unknown -/// whether it is hot or not (for example, no profile data is available). -bool ProfileSummaryInfo::isFunctionHotInCallGraph(const Function *F) { +/// (for example, no profile data is available). +bool ProfileSummaryInfo::isFunctionHotInCallGraph(const Function *F, + BlockFrequencyInfo &BFI) { if (!F || !computeSummary()) return false; if (auto FunctionCount = F->getEntryCount()) if (isHotCount(FunctionCount.getValue())) return true; - uint64_t TotalCallCount = 0; + if (hasSampleProfile()) { + uint64_t TotalCallCount = 0; + for (const auto &BB : *F) + for (const auto &I : BB) + if (isa<CallInst>(I) || isa<InvokeInst>(I)) + if (auto CallCount = getProfileCount(&I, nullptr)) + TotalCallCount += CallCount.getValue(); + if (isHotCount(TotalCallCount)) + return true; + } for (const auto &BB : *F) - for (const auto &I : BB) - if (isa<CallInst>(I) || isa<InvokeInst>(I)) - if (auto CallCount = getProfileCount(&I, nullptr)) - TotalCallCount += CallCount.getValue(); - return isHotCount(TotalCallCount); + if (isHotBB(&BB, &BFI)) + return true; + return false; } -/// Returns true if the function's entry and total call edge count is cold. +/// Returns true if the function only contains cold code. This means that +/// the function entry and blocks are all cold, and (in the case of Sample PGO) +/// the total call edge count is cold. /// If it returns false, it either means it is not cold or it is unknown -/// whether it is cold or not (for example, no profile data is available). -bool ProfileSummaryInfo::isFunctionColdInCallGraph(const Function *F) { +/// (for example, no profile data is available). +bool ProfileSummaryInfo::isFunctionColdInCallGraph(const Function *F, + BlockFrequencyInfo &BFI) { if (!F || !computeSummary()) return false; if (auto FunctionCount = F->getEntryCount()) if (!isColdCount(FunctionCount.getValue())) return false; - - uint64_t TotalCallCount = 0; + + if (hasSampleProfile()) { + uint64_t TotalCallCount = 0; + for (const auto &BB : *F) + for (const auto &I : BB) + if (isa<CallInst>(I) || isa<InvokeInst>(I)) + if (auto CallCount = getProfileCount(&I, nullptr)) + TotalCallCount += CallCount.getValue(); + if (!isColdCount(TotalCallCount)) + return false; + } for (const auto &BB : *F) - for (const auto &I : BB) - if (isa<CallInst>(I) || isa<InvokeInst>(I)) - if (auto CallCount = getProfileCount(&I, nullptr)) - TotalCallCount += CallCount.getValue(); - return isColdCount(TotalCallCount); + if (!isColdBB(&BB, &BFI)) + return false; + return true; } /// Returns true if the function's entry is a cold. If it returns false, it @@ -231,7 +251,7 @@ bool ProfileSummaryInfo::isColdCallSite(const CallSite &CS, // If there is no profile for the caller, and we know the profile is // accurate, we consider the callsite as cold. return (hasSampleProfile() && - (CS.getCaller()->getEntryCount() || ProfileSampleAccurate || + (CS.getCaller()->hasProfileData() || ProfileSampleAccurate || CS.getCaller()->hasFnAttribute("profile-sample-accurate"))); } diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 0b8604187121f..2a8088dc44528 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4368,6 +4368,7 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { default: break; } + break; } default: diff --git a/lib/Analysis/TargetTransformInfo.cpp b/lib/Analysis/TargetTransformInfo.cpp index b744cae51ed7b..c9e9c6d1a419c 100644 --- a/lib/Analysis/TargetTransformInfo.cpp +++ b/lib/Analysis/TargetTransformInfo.cpp @@ -314,6 +314,10 @@ int TargetTransformInfo::getIntImmCost(Intrinsic::ID IID, unsigned Idx, return Cost; } +bool TargetTransformInfo::isOutOfOrder() const { + return TTIImpl->isOutOfOrder(); +} + unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const { return TTIImpl->getNumberOfRegisters(Vector); } diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp index c9ed026a1e335..173db399b9d60 100644 --- a/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -544,21 +544,32 @@ static bool matchAccessTags(const MDNode *A, const MDNode *B, TBAAStructTagNode TagA(A), TagB(B); const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(), TagB.getAccessType()); - if (GenericTag) - *GenericTag = createAccessTag(CommonType); // TODO: We need to check if AccessType of TagA encloses AccessType of // TagB to support aggregate AccessType. If yes, return true. // Climb the type DAG from base type of A to see if we reach base type of B. uint64_t OffsetA; - if (findAccessType(TagA, TagB.getBaseType(), OffsetA)) - return OffsetA == TagB.getOffset(); + if (findAccessType(TagA, TagB.getBaseType(), OffsetA)) { + bool SameMemberAccess = OffsetA == TagB.getOffset(); + if (GenericTag) + *GenericTag = SameMemberAccess ? TagB.getNode() : + createAccessTag(CommonType); + return SameMemberAccess; + } // Climb the type DAG from base type of B to see if we reach base type of A. uint64_t OffsetB; - if (findAccessType(TagB, TagA.getBaseType(), OffsetB)) - return OffsetB == TagA.getOffset(); + if (findAccessType(TagB, TagA.getBaseType(), OffsetB)) { + bool SameMemberAccess = OffsetB == TagA.getOffset(); + if (GenericTag) + *GenericTag = SameMemberAccess ? TagA.getNode() : + createAccessTag(CommonType); + return SameMemberAccess; + } + + if (GenericTag) + *GenericTag = createAccessTag(CommonType); // If the final access types have different roots, they're part of different // potentially unrelated type systems, so we must be conservative. |