Index: include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- include/llvm/Analysis/BasicAliasAnalysis.h +++ include/llvm/Analysis/BasicAliasAnalysis.h @@ -40,21 +40,23 @@ friend AAResultBase; const DataLayout &DL; + InvariantInfo &InvInfo; AssumptionCache &AC; DominatorTree *DT; LoopInfo *LI; public: BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI, - AssumptionCache &AC, DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr) - : AAResultBase(TLI), DL(DL), AC(AC), DT(DT), LI(LI) {} + AssumptionCache &AC, InvariantInfo &InvInfo, + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr) + : AAResultBase(TLI), DL(DL), InvInfo(InvInfo), AC(AC), DT(DT), LI(LI) {} BasicAAResult(const BasicAAResult &Arg) - : AAResultBase(Arg), DL(Arg.DL), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI) {} + : AAResultBase(Arg), DL(Arg.DL), InvInfo(Arg.InvInfo), AC(Arg.AC), + DT(Arg.DT), LI(Arg.LI) {} BasicAAResult(BasicAAResult &&Arg) - : AAResultBase(std::move(Arg)), DL(Arg.DL), AC(Arg.AC), DT(Arg.DT), - LI(Arg.LI) {} + : AAResultBase(std::move(Arg)), DL(Arg.DL), InvInfo(Arg.InvInfo), + AC(Arg.AC), DT(Arg.DT), LI(Arg.LI) {} /// Handle invalidation events from the new pass manager. /// Index: include/llvm/IR/InvariantInfo.h =================================================================== --- /dev/null +++ include/llvm/IR/InvariantInfo.h @@ -0,0 +1,80 @@ +//===-------- llvm/InvariantInfo.h - invariant_start/end info ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines properties for handling invariant_start/end instructions +// for purposes of load elimination. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_INVARIANTINFO_H +#define LLVM_IR_INVARIANTINFO_H + +#include "llvm/ADT/DenseMap.h" + +namespace llvm { +class Value; +class DataLayout; +class IntrinsicInst; + +/// PreservedInvariantInfo -- A data structure to mark and access processed +/// invariant intrinsic calls. +class InvariantInfo { + + /// \brief A mapping of each 'writeonce' allocated memory (via a + /// GlobalVariable or AllocaInst instance) to its matching intrisic_start + /// call. This is to be used by GVN, InstCombine, GlobalOpt and BasicAA + /// to process invariant intrinsics for purposes of eliminating redundant + /// load instructions. + DenseMap InvariantMarkers; + +public: + + /// \brief Access the 'InvariantMarkers' mapping to extract invariant_start + /// instruction that is associated with the given Address. + IntrinsicInst *GetStartInstruction(const Value *Addr) const; + + /// \brief Add an entry to the 'InvariantMarkers' mapping. + void SetStartInstruction(Value *Addr, IntrinsicInst *IStart); +}; + +/// PreservedInvariantInfo -- Information processed from invariant intrinsics, +/// for a given query instruction. +struct PreservedInvariantInfo { + IntrinsicInst *II; + Value *LoadedAddr; + InvariantInfo &InvInfo; + PreservedInvariantInfo(Value *Query, const DataLayout &DL, + InvariantInfo &InvInfo); +}; + +/// PreserveInvariantInfo -- An RAII object to save and restore information +/// from processed invariant intrinsics. +class PreserveInvariantInfo { + PreservedInvariantInfo Preserved; + void CheckPreservedInfo() const; + + public: + PreserveInvariantInfo(PreservedInvariantInfo Info); + ~PreserveInvariantInfo(); +}; + +/// \brief Process invariant_start/end intrinsics: Mark addresses as "within +/// an invariant range" specified by the given intrinsic call. +bool processInvariantIntrinsic(IntrinsicInst *II, InvariantInfo &InvInfo); + +/// \brief Handle invariant_start/end intrinsics when scanning intructions +/// backward to either find available loads or look for pointer dependencies +/// from a given query instruction, based on preserved invariant info. +bool BackwardScanInvariantIntrinsic(const IntrinsicInst *II, + const PreservedInvariantInfo &Preserved, + InvariantInfo &InvInfo); + +} // End llvm namespace + +#endif Index: include/llvm/IR/Module.h =================================================================== --- include/llvm/IR/Module.h +++ include/llvm/IR/Module.h @@ -21,6 +21,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/InvariantInfo.h" #include "llvm/IR/Metadata.h" #include "llvm/Support/CBindingWrapping.h" #include "llvm/Support/CodeGen.h" @@ -173,6 +174,7 @@ ///< Format: (arch)(sub)-(vendor)-(sys0-(abi) void *NamedMDSymTab; ///< NamedMDNode names. DataLayout DL; ///< DataLayout associated with the module + InvariantInfo InvInfo; ///< Processed invariant intrinsics info. friend class Constant; @@ -209,6 +211,9 @@ /// Get the data layout for the module's target platform. const DataLayout &getDataLayout() const; + /// \brief Get info about invariant intrinsics processed in this module. + InvariantInfo &getInvariantInfo() { return InvInfo; } + /// Get the target triple which is a string describing the target host. /// @returns a string containing the target triple. const std::string &getTargetTriple() const { return TargetTriple; } Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -488,12 +488,15 @@ if (OrLocal && isa(V)) continue; + if (const AllocaInst *AI = dyn_cast(V)) + if (InvInfo.GetStartInstruction(AI)) continue; + // A global constant counts as local memory for our purposes. if (const GlobalVariable *GV = dyn_cast(V)) { // Note: this doesn't require GV to be "ODR" because it isn't legal for a // global to be marked constant in some modules and non-constant in // others. GV may even be a declaration, not a definition. - if (!GV->isConstant()) { + if (!GV->isConstant() && !InvInfo.GetStartInstruction(GV)) { Visited.clear(); return AAResultBase::pointsToConstantMemory(Loc, OrLocal); } @@ -670,6 +673,12 @@ return Alias; } +static bool isInvariantIntrinsic(ImmutableCallSite CS) { + const IntrinsicInst *II = dyn_cast(CS.getInstruction()); + return II && (II->getIntrinsicID() == Intrinsic::invariant_start || + II->getIntrinsicID() == Intrinsic::invariant_end); +} + /// Checks to see if the specified callsite can clobber the specified memory /// object. /// @@ -731,6 +740,9 @@ if (isAssumeIntrinsic(CS)) return MRI_NoModRef; + // Invariant intrinsics follow the same pattern as assume intrinsic. + if (isInvariantIntrinsic(CS)) return MRI_NoModRef; + // The AAResultBase base class has some smarts, lets use them. return AAResultBase::getModRefInfo(CS, Loc); } @@ -743,6 +755,10 @@ if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2)) return MRI_NoModRef; + // Invariant intrinsics follow the same pattern as assume intrinsic. + if (isInvariantIntrinsic(CS1) || isInvariantIntrinsic(CS2)) + return MRI_NoModRef; + // The AAResultBase base class has some smarts, lets use them. return AAResultBase::getModRefInfo(CS1, CS2); } @@ -1528,6 +1544,7 @@ return BasicAAResult(F.getParent()->getDataLayout(), AM->getResult(F), AM->getResult(F), + F.getParent()->getInvariantInfo(), AM->getCachedResult(F), AM->getCachedResult(F)); } @@ -1554,6 +1571,7 @@ Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(), ACT.getAssumptionCache(F), + F.getParent()->getInvariantInfo(), DTWP ? &DTWP->getDomTree() : nullptr, LIWP ? &LIWP->getLoopInfo() : nullptr)); @@ -1570,5 +1588,6 @@ return BasicAAResult( F.getParent()->getDataLayout(), P.getAnalysis().getTLI(), - P.getAnalysis().getAssumptionCache(F)); + P.getAnalysis().getAssumptionCache(F), + F.getParent()->getInvariantInfo()); } Index: lib/IR/CMakeLists.txt =================================================================== --- lib/IR/CMakeLists.txt +++ lib/IR/CMakeLists.txt @@ -26,6 +26,7 @@ Instruction.cpp Instructions.cpp IntrinsicInst.cpp + InvariantInfo.cpp LLVMContext.cpp LLVMContextImpl.cpp LegacyPassManager.cpp Index: lib/IR/InvariantInfo.cpp =================================================================== --- /dev/null +++ lib/IR/InvariantInfo.cpp @@ -0,0 +1,143 @@ +//===---------- InvariantInfo.cpp - invariant_start/end info ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines properties for handling invariant_start/end instructions +// for purposes of load elimination. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/InvariantInfo.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Instructions.h" +using namespace llvm; + +IntrinsicInst *InvariantInfo::GetStartInstruction(const Value *Addr) const { + if (!Addr) return nullptr; + + // Only global variables and alloca instructions are marked. + if (!isa(Addr) && !isa(Addr)) return nullptr; + + // constant globals are also not marked. + if (const GlobalVariable *GV = dyn_cast(Addr)) { + if (GV->isConstant()) return nullptr; + } + + // Retrieve the value from the markers map. + auto EntryIter = InvariantMarkers.find(const_cast(Addr)); + if (EntryIter != InvariantMarkers.end()) return EntryIter->second; + return nullptr; +} + +void InvariantInfo::SetStartInstruction(Value *Addr, IntrinsicInst *IStart) { + if (!Addr) return; + + // Only mark either global variables or alloca instructions. + if (!isa(Addr) && !isa(Addr)) return; + + assert((!IStart || IStart->getIntrinsicID() == Intrinsic::invariant_start) && + "Given intrinsic instruction is not invariant_start"); + if (IStart && isa(Addr)) + assert(IStart->getParent() == cast(Addr)->getParent() && + "Invariant_start calls on a given alloca instruction must have" + "the same parent the alloca instruction."); + + // Erase the current entry to ensure that the new value is inserted into + // the markers map. + InvariantMarkers.erase(Addr); + + // Actually insert the value into the map. This operation must be successful. + // Note: A request to insert a nullptr value is a request to erase the entry. + // So, do not insert nullptr values. + if (IStart) { + bool Inserted = InvariantMarkers.insert(std::make_pair(Addr, IStart)).second; + assert(Inserted && "Setting new marker failed."); + } +} + +void llvm::PreserveInvariantInfo::CheckPreservedInfo() const { + assert(Preserved.II->getIntrinsicID() == Intrinsic::invariant_start && + "Preserved instruction must be an invariant_start intrinsic"); + assert(Preserved.LoadedAddr && + "Can't preserve an intrinsic instruction for no load."); +} + +PreserveInvariantInfo::PreserveInvariantInfo(PreservedInvariantInfo Info) + : Preserved(Info) { + if (Preserved.II) CheckPreservedInfo(); +} + +PreserveInvariantInfo::~PreserveInvariantInfo() { + if (Preserved.II) + Preserved.InvInfo.SetStartInstruction(Preserved.LoadedAddr, Preserved.II); +} + +/// Before scanning instructions backward from a given query instruction, +/// preserve information processed from invariant intrinsics, if the query is +/// is a load from writeonce memory. +llvm::PreservedInvariantInfo::PreservedInvariantInfo(Value *QueryInst, + const DataLayout &DL, + InvariantInfo &InvInfo) +: II(nullptr), LoadedAddr(nullptr), InvInfo(InvInfo) { + if (LoadInst *LI = dyn_cast_or_null(QueryInst)) { + Value *Addr = GetUnderlyingObject(LI->getPointerOperand(), DL); + if (IntrinsicInst *QueryII = InvInfo.GetStartInstruction(Addr)) { + II = QueryII; + LoadedAddr = Addr; + } + } +} + +/// If the given intrinsic instruction is an invariant_start, then mark its +/// corresponding address as "written" 'writeonce', and thus treatable as not +/// pointing to constant memory. If the intrinsic instruction is an +/// invariant_end instead, then mark the address as no longer "written" +/// and thus writeable again (i.e. no longer pointing to constant memory). +bool llvm::processInvariantIntrinsic(IntrinsicInst *II, + InvariantInfo &InvInfo) { + assert(II && "Can't mark a null instruction."); + + if (II->getIntrinsicID() == Intrinsic::invariant_start) { + llvm::Value *Addr = II->getArgOperand(1)->stripPointerCasts(); + InvInfo.SetStartInstruction(Addr, II); + return true; + } else if (II->getIntrinsicID() == Intrinsic::invariant_end) { + llvm::Value *Addr = II->getArgOperand(2)->stripPointerCasts(); + if (InvInfo.GetStartInstruction(Addr)) + InvInfo.SetStartInstruction(Addr, nullptr); + return true; + } + return false; +} + +/// If the query is a load that is within an invariant_start/end pair, and +/// if we encounter its associated invariant_start instruction, then start +/// treating the memory location that it loads from as not pointing to +/// constant memory. +/// +/// This function returns true if the given instrinsic instruction is an +/// invariant_start/end. +bool llvm::BackwardScanInvariantIntrinsic(const IntrinsicInst *II, + const PreservedInvariantInfo &Preserved, + InvariantInfo &InvInfo) { + if (II->getIntrinsicID() == Intrinsic::invariant_start) { + if (II == Preserved.II) + InvInfo.SetStartInstruction(Preserved.LoadedAddr, nullptr); + return true; + } else if (II->getIntrinsicID() == Intrinsic::invariant_end) { + llvm::Value *IStart = II->getArgOperand(0)->stripPointerCasts(); + assert(Preserved.II != dyn_cast(IStart) && + "This invariant_end's start instruction could not match the " + "preserved invariant_start, if preserved."); + return true; + } + return false; +} Index: unittests/Analysis/AliasAnalysisTest.cpp =================================================================== --- unittests/Analysis/AliasAnalysisTest.cpp +++ unittests/Analysis/AliasAnalysisTest.cpp @@ -39,7 +39,8 @@ // Build the various AA results and register them. AC.reset(new AssumptionCache(F)); - BAR.reset(new BasicAAResult(M.getDataLayout(), TLI, *AC)); + BAR.reset(new BasicAAResult(M.getDataLayout(), TLI, *AC, + M.getInvariantInfo())); AAR->addAAResult(*BAR); return *AAR;