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/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; +}