Index: include/llvm/Analysis/FunctionAttrsAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/FunctionAttrsAnalysis.h @@ -0,0 +1,41 @@ +//===-- FunctionAttrs.h - Compute function attrs --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// Provides analysis for computing function attributes +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_FUNCTIONATTRSANALYSIS_H +#define LLVM_ANALYSIS_FUNCTIONATTRSANALYSIS_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/AliasAnalysis.h" + +namespace llvm { + +class AAResults; + +/// The three kinds of memory access relevant to 'readonly' and +/// 'readnone' attributes. +enum MemoryAccessKind { MAK_ReadNone = 0, MAK_ReadOnly = 1, MAK_MayWrite = 2 }; + +typedef SmallSetVector SCCNodeSet; + +/// Returns the memory access properties of this copy of the function. +MemoryAccessKind computeFunctionBodyMemoryAccess( + const Function &F, AAResults &AAR, + DenseMap *CSModRefMap = nullptr); + +MemoryAccessKind +checkFunctionMemoryAccess(const Function &F, bool ThisBody, AAResults &AAR, + const SCCNodeSet &SCCNodes, + DenseMap *CSModRefMap); +} // namespace llvm + +#endif // LLVM_ANALYSIS_FUNCTIONATTRSANALYSIS_H Index: include/llvm/Analysis/ModuleSummaryAnalysis.h =================================================================== --- include/llvm/Analysis/ModuleSummaryAnalysis.h +++ include/llvm/Analysis/ModuleSummaryAnalysis.h @@ -26,6 +26,7 @@ class Function; class Module; class ProfileSummaryInfo; +class AAResults; /// Direct function to compute a \c ModuleSummaryIndex from a given module. /// @@ -36,7 +37,8 @@ ModuleSummaryIndex buildModuleSummaryIndex( const Module &M, std::function GetBFICallback, - ProfileSummaryInfo *PSI); + ProfileSummaryInfo *PSI, + std::function GetAARCallback = nullptr); /// Analysis pass to provide the ModuleSummaryIndex object. class ModuleSummaryIndexAnalysis Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -55,6 +55,8 @@ Critical = 4 }; HotnessType Hotness = HotnessType::Unknown; + enum class ModRefType : uint8_t { ReadNone = 0, ReadOnly = 1, MayWrite = 2 }; + ModRefType ModRef = ModRefType::ReadNone; CalleeInfo() = default; explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {} @@ -62,6 +64,10 @@ void updateHotness(const HotnessType OtherHotness) { Hotness = std::max(Hotness, OtherHotness); } + + void updateModRef(const ModRefType OtherModRef) { + ModRef = std::max(ModRef, OtherModRef); + } }; class GlobalValueSummary; @@ -290,8 +296,8 @@ /// Function attribute flags. Used to track if a function accesses memory, /// recurses or aliases. struct FFlags { - unsigned ReadNone : 1; - unsigned ReadOnly : 1; + unsigned ReadNone : 1; // TODO: change to ReadNoneIgnoringCalls + unsigned ReadOnly : 1; // TODO: change to ReadOnlyIgnoringCalls unsigned NoRecurse : 1; unsigned ReturnDoesNotAlias : 1; }; Index: include/llvm/Transforms/IPO/FunctionAttrs.h =================================================================== --- include/llvm/Transforms/IPO/FunctionAttrs.h +++ include/llvm/Transforms/IPO/FunctionAttrs.h @@ -20,19 +20,6 @@ namespace llvm { -class AAResults; - -/// The three kinds of memory access relevant to 'readonly' and -/// 'readnone' attributes. -enum MemoryAccessKind { - MAK_ReadNone = 0, - MAK_ReadOnly = 1, - MAK_MayWrite = 2 -}; - -/// Returns the memory access properties of this copy of the function. -MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR); - /// Computes function attributes in post-order over the call graph. /// /// By operating in post-order, this pass computes precise attributes for Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -29,6 +29,7 @@ DomPrinter.cpp DominanceFrontier.cpp EHPersonalities.cpp + FunctionAttrsAnalysis.cpp GlobalsModRef.cpp IVUsers.cpp IndirectCallPromotionAnalysis.cpp Index: lib/Analysis/FunctionAttrsAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/FunctionAttrsAnalysis.cpp @@ -0,0 +1,165 @@ +//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file implements interprocedural passes which walk the +/// call-graph deducing and/or propagating function attributes. +/// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/FunctionAttrsAnalysis.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/InstIterator.h" +using namespace llvm; + +/// Returns the memory access attribute for function F using AAR for AA results, +/// where SCCNodes is the current SCC. +/// +/// If ThisBody is true, this function may examine the function body and will +/// return a result pertaining to this copy of the function. If it is false, the +/// result will be based only on AA results for the function declaration; it +/// will be assumed that some other (perhaps less optimized) version of the +/// function may be selected at link time. +MemoryAccessKind llvm::checkFunctionMemoryAccess( + const Function &F, bool ThisBody, AAResults &AAR, + const SCCNodeSet &SCCNodes, + DenseMap *CSModRefMap) { + FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); + if (MRB == FMRB_DoesNotAccessMemory) + // Already perfect! + return MAK_ReadNone; + + if (!ThisBody) { + if (AliasAnalysis::onlyReadsMemory(MRB)) + return MAK_ReadOnly; + + // Conservatively assume it writes to memory. + return MAK_MayWrite; + } + + // Scan the function body for instructions that may read or write memory. + bool ReadsMemory = false; + for (auto II = inst_begin(F), E = inst_end(F); II != E; ++II) { + const Instruction *I = &*II; + + // Some instructions can be ignored even if they read or write memory. + // Detect these now, skipping to the next instruction if one is found. + ImmutableCallSite CS(cast(I)); + if (CS) { + // Ignore calls to functions in the same SCC, as long as the call sites + // don't have operand bundles. Calls with operand bundles are allowed to + // have memory effects not described by the memory effects of the call + // target. + if (!CS.hasOperandBundles() && CS.getCalledFunction() && + SCCNodes.count(const_cast(CS.getCalledFunction()))) + continue; + + ModRefInfo *SaveModRef = nullptr; + if (!CS.hasOperandBundles() && CS.getCalledFunction() && CSModRefMap) { + auto Result = + CSModRefMap->try_emplace(CS.getCalledFunction(), MRI_NoModRef); + SaveModRef = &Result.first->second; + } + + FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); + + // If the call doesn't access memory, we're done. + if (!(MRB & MRI_ModRef)) + continue; + + if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) { + // The call could access any memory. If that includes writes, give up. + if (MRB & MRI_Mod) { + if (SaveModRef) + (*SaveModRef) = MRI_Mod; + else + return MAK_MayWrite; + } + // If it reads, note it. + else if (MRB & MRI_Ref) { + if (SaveModRef && *SaveModRef == MRI_NoModRef) + (*SaveModRef) = MRI_Ref; + else + ReadsMemory = true; + } + continue; + } + + // Check whether all pointer arguments point to local memory, and + // ignore calls that only access local memory. + for (auto CI = CS.arg_begin(), CE = CS.arg_end(); CI != CE; ++CI) { + Value *Arg = *CI; + if (!Arg->getType()->isPtrOrPtrVectorTy()) + continue; + + AAMDNodes AAInfo; + I->getAAMetadata(AAInfo); + MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); + + // Skip accesses to local or constant memory as they don't impact the + // externally visible mod/ref behavior. + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; + + if (MRB & MRI_Mod) { + if (SaveModRef) + (*SaveModRef) = MRI_Mod; + else + // Writes non-local memory. Give up. + return MAK_MayWrite; + } else if (MRB & MRI_Ref) { + if (SaveModRef && *SaveModRef == MRI_NoModRef) + (*SaveModRef) = MRI_Ref; + else + // Ok, it reads non-local memory. + ReadsMemory = true; + } + } + continue; + } else if (const LoadInst *LI = dyn_cast(I)) { + // Ignore non-volatile loads from local memory. (Atomic is okay here.) + if (!LI->isVolatile()) { + MemoryLocation Loc = MemoryLocation::get(LI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; + } + } else if (const StoreInst *SI = dyn_cast(I)) { + // Ignore non-volatile stores to local memory. (Atomic is okay here.) + if (!SI->isVolatile()) { + MemoryLocation Loc = MemoryLocation::get(SI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; + } + } else if (const VAArgInst *VI = dyn_cast(I)) { + // Ignore vaargs on local memory. + MemoryLocation Loc = MemoryLocation::get(VI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; + } + + // Any remaining instructions need to be taken seriously! Check if they + // read or write memory. + if (I->mayWriteToMemory()) + // Writes memory. Just give up. + return MAK_MayWrite; + + // If this instruction may read memory, remember that. + ReadsMemory |= I->mayReadFromMemory(); + } + + return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; +} + +MemoryAccessKind llvm::computeFunctionBodyMemoryAccess( + const Function &F, AAResults &AAR, + DenseMap *CSModRefMap) { + return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {}, CSModRefMap); +} Index: lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- lib/Analysis/ModuleSummaryAnalysis.cpp +++ lib/Analysis/ModuleSummaryAnalysis.cpp @@ -21,8 +21,10 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/FunctionAttrsAnalysis.h" #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ProfileSummaryInfo.h" @@ -195,11 +197,12 @@ } } -static void -computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, - const Function &F, BlockFrequencyInfo *BFI, - ProfileSummaryInfo *PSI, bool HasLocalsInUsed, - DenseSet &CantBePromoted) { +static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, + const Function &F, BlockFrequencyInfo *BFI, + ProfileSummaryInfo *PSI, + bool HasLocalsInUsed, + DenseSet &CantBePromoted, + AAResults *AAR) { // Summary not currently supported for anonymous functions, they should // have been named. assert(F.hasName()); @@ -216,6 +219,18 @@ TypeCheckedLoadConstVCalls; ICallPromotionAnalysis ICallAnalysis; + DenseMap CSModRefMap; + bool ReadNone, ReadOnly; + if (AAR) { + auto MAK = computeFunctionBodyMemoryAccess(F, *AAR, &CSModRefMap); + ReadNone = MAK == MAK_ReadNone; + ReadOnly = MAK == MAK_ReadOnly; + errs() << "MemAccess for " << F.getName() << " is " << ReadNone << " " + << ReadOnly << "\n"; + } else { + ReadNone = F.hasFnAttribute(Attribute::ReadNone); + ReadOnly = F.hasFnAttribute(Attribute::ReadOnly); + } bool HasInlineAsmMaybeReferencingInternal = false; SmallPtrSet Visited; for (const BasicBlock &BB : F) @@ -267,6 +282,20 @@ CallGraphEdges[Index.getOrInsertValueInfo( cast(CalledValue))] .updateHotness(Hotness); + auto I = CSModRefMap.find(CalledFunction); + if (I != CSModRefMap.end()) { + ModRefInfo MRI = I->second; + CalleeInfo::ModRefType ModRef = CalleeInfo::ModRefType::ReadNone; + if (MRI & MRI_Mod) + ModRef = CalleeInfo::ModRefType::MayWrite; + else if (MRI & MRI_Ref) + ModRef = CalleeInfo::ModRefType::ReadOnly; + errs() << "ModRef for CalledFunction " << CalledFunction->getName() + << " = " << (int)ModRef << "\n"; + CallGraphEdges[Index.getOrInsertValueInfo( + cast(CalledValue))] + .updateModRef(ModRef); + } } else { // Skip inline assembly calls. if (CI && CI->isInlineAsm()) @@ -301,8 +330,8 @@ GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport, /* Live = */ false); FunctionSummary::FFlags FunFlags{ - F.hasFnAttribute(Attribute::ReadNone), - F.hasFnAttribute(Attribute::ReadOnly), + ReadNone, + ReadOnly, F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(), }; @@ -359,7 +388,8 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( const Module &M, std::function GetBFICallback, - ProfileSummaryInfo *PSI) { + ProfileSummaryInfo *PSI, + std::function GetAARCallback) { assert(PSI); ModuleSummaryIndex Index; @@ -398,9 +428,10 @@ BFIPtr = llvm::make_unique(F, BPI, LI); BFI = BFIPtr.get(); } + AAResults *AAR = GetAARCallback ? GetAARCallback(F) : nullptr; computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(), - CantBePromoted); + CantBePromoted, AAR); } // Compute summaries for all variables defined in module, and save in the @@ -534,7 +565,10 @@ return &FAM.getResult( *const_cast(&F)); }, - &PSI); + &PSI, + [&FAM](const Function &F) { + return &FAM.getResult(*const_cast(&F)); + }); } char ModuleSummaryIndexWrapperPass::ID = 0; @@ -543,6 +577,7 @@ "Module Summary Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", "Module Summary Analysis", false, true) @@ -564,7 +599,12 @@ *const_cast(&F)) .getBFI()); }, - &PSI); + &PSI, + [this](const Function &F) { + return &( + this->getAnalysis(*const_cast(&F)) + .getAAResults()); + }); return false; } @@ -577,4 +617,5 @@ AU.setPreservesAll(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); } Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/FunctionAttrsAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/GlobalVariable.h" @@ -56,130 +57,6 @@ cl::desc("Try to propagate nonnull argument attributes from callsites to " "caller functions.")); -namespace { -typedef SmallSetVector SCCNodeSet; -} - -/// Returns the memory access attribute for function F using AAR for AA results, -/// where SCCNodes is the current SCC. -/// -/// If ThisBody is true, this function may examine the function body and will -/// return a result pertaining to this copy of the function. If it is false, the -/// result will be based only on AA results for the function declaration; it -/// will be assumed that some other (perhaps less optimized) version of the -/// function may be selected at link time. -static MemoryAccessKind checkFunctionMemoryAccess(Function &F, bool ThisBody, - AAResults &AAR, - const SCCNodeSet &SCCNodes) { - FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); - if (MRB == FMRB_DoesNotAccessMemory) - // Already perfect! - return MAK_ReadNone; - - if (!ThisBody) { - if (AliasAnalysis::onlyReadsMemory(MRB)) - return MAK_ReadOnly; - - // Conservatively assume it writes to memory. - return MAK_MayWrite; - } - - // Scan the function body for instructions that may read or write memory. - bool ReadsMemory = false; - for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { - Instruction *I = &*II; - - // Some instructions can be ignored even if they read or write memory. - // Detect these now, skipping to the next instruction if one is found. - CallSite CS(cast(I)); - if (CS) { - // Ignore calls to functions in the same SCC, as long as the call sites - // don't have operand bundles. Calls with operand bundles are allowed to - // have memory effects not described by the memory effects of the call - // target. - if (!CS.hasOperandBundles() && CS.getCalledFunction() && - SCCNodes.count(CS.getCalledFunction())) - continue; - FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); - - // If the call doesn't access memory, we're done. - if (!(MRB & MRI_ModRef)) - continue; - - if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) { - // The call could access any memory. If that includes writes, give up. - if (MRB & MRI_Mod) - return MAK_MayWrite; - // If it reads, note it. - if (MRB & MRI_Ref) - ReadsMemory = true; - continue; - } - - // Check whether all pointer arguments point to local memory, and - // ignore calls that only access local memory. - for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); - CI != CE; ++CI) { - Value *Arg = *CI; - if (!Arg->getType()->isPtrOrPtrVectorTy()) - continue; - - AAMDNodes AAInfo; - I->getAAMetadata(AAInfo); - MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); - - // Skip accesses to local or constant memory as they don't impact the - // externally visible mod/ref behavior. - if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) - continue; - - if (MRB & MRI_Mod) - // Writes non-local memory. Give up. - return MAK_MayWrite; - if (MRB & MRI_Ref) - // Ok, it reads non-local memory. - ReadsMemory = true; - } - continue; - } else if (LoadInst *LI = dyn_cast(I)) { - // Ignore non-volatile loads from local memory. (Atomic is okay here.) - if (!LI->isVolatile()) { - MemoryLocation Loc = MemoryLocation::get(LI); - if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) - continue; - } - } else if (StoreInst *SI = dyn_cast(I)) { - // Ignore non-volatile stores to local memory. (Atomic is okay here.) - if (!SI->isVolatile()) { - MemoryLocation Loc = MemoryLocation::get(SI); - if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) - continue; - } - } else if (VAArgInst *VI = dyn_cast(I)) { - // Ignore vaargs on local memory. - MemoryLocation Loc = MemoryLocation::get(VI); - if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) - continue; - } - - // Any remaining instructions need to be taken seriously! Check if they - // read or write memory. - if (I->mayWriteToMemory()) - // Writes memory. Just give up. - return MAK_MayWrite; - - // If this instruction may read memory, remember that. - ReadsMemory |= I->mayReadFromMemory(); - } - - return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; -} - -MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F, - AAResults &AAR) { - return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {}); -} - /// Deduce readonly/readnone attributes for the SCC. template static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) { @@ -193,8 +70,8 @@ // Non-exact function definitions may not be selected at link time, and an // alternative version that writes to memory may be selected. See the // comment on GlobalValue::isDefinitionExact for more details. - switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(), - AAR, SCCNodes)) { + switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, + SCCNodes, nullptr)) { case MAK_MayWrite: return false; case MAK_ReadOnly: Index: lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp =================================================================== --- lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp +++ lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp @@ -9,6 +9,7 @@ #include "llvm/Transforms/IPO/ThinLTOBitcodeWriter.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/FunctionAttrsAnalysis.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/TypeMetadataUtils.h" @@ -23,7 +24,6 @@ #include "llvm/Support/ScopedPrinter.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/IPO.h" -#include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/ModuleUtils.h" using namespace llvm; Index: lib/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- lib/Transforms/IPO/WholeProgramDevirt.cpp +++ lib/Transforms/IPO/WholeProgramDevirt.cpp @@ -51,6 +51,7 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/FunctionAttrsAnalysis.h" #include "llvm/Analysis/TypeMetadataUtils.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" @@ -79,7 +80,6 @@ #include "llvm/Support/FileSystem.h" #include "llvm/Support/MathExtras.h" #include "llvm/Transforms/IPO.h" -#include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/Utils/Evaluator.h" #include #include