Express and handle specific info about the processing of invariant intrinsics

[lvoufo]

Summary

Add an 'InvariantInfo' property to the 'Module' data structure, and use the property to extend basic AA's assessment that a given memory location is to be treated as constant memory.

The 'InvariantInfo' field in 'Module' will be used to collect information meaningful for load elimination while processing invariant intrinsics calls.

This patch is a break-down of (corrected) D13606.

[lvoufo]

I split this up into D14008 and D14009. I hope that this does not cause too much of an inconvenience. Please let me know...
--L

[sanjoy]

include/llvm/IR/InvariantInfo.h

28

Please add some high level comments describing how this is supposed to be used.

29

Please add some comments on how you deal with passes RAUW'ing or erasing values.

56

Please document these functions.

[lvoufo]

include/llvm/IR/InvariantInfo.h

56

Do you mean in addition to the documentation of its implementation in lib/IR/InvariantInfo.cpp ?

[sanjoy]

include/llvm/IR/InvariantInfo.h

56

Never mind, I just saw the docs in the implementation file. :)

The doxygen comments are typically put in the header.

[lvoufo]

include/llvm/IR/InvariantInfo.h

28

Ok.

29

Ok.

56

No problem. I just figured it would be more legible to have the detailed documentation right next to the implementation. I can add some high-level comments on the prototypes too if it help.

[nlewycky]

include/llvm/IR/InvariantInfo.h

21–23

Alphabetize.

25–27

One side says "PreservedInvariantInfo" the other side says "InvariantInfo". Just remove the class name from the comment, that style is pre-style guide.

Also, "a data structure to mark and access processed invariant intrinsic calls"? I don't think that tells me what it does or what it's for. Is it a cache of invariant intrinsics that pertain to a given Value?

29

"writeonce" is not defined anywhere?

30

Typo in "intrisic_start"

46

Remove struct name from comment.

58

Hold on, you have one struct PreservedInvariantInfo and one class PreserveInvariantInfo? Please rename one of them.

include/llvm/IR/Module.h

177

A Module has a 1:1 correlation with the .ll and the .bc. This shouldn't go there, probably it should be an analysis hanging off the side like AssumptionCache is.

lib/Analysis/BasicAliasAnalysis.cpp

499

This seems like a really bad interface. The Pass which sets up the InvInfo has to decide whether to add or not add an invariant intrinsic based on which instruction the caller of pointsToConstantMemory is going to be reasoning about. pointsToConstantMemory could be called by a utility used by the pass, and referring to a point in the program before (or after) the call to invariant.start/end.

lib/IR/InvariantInfo.cpp

1

Remove the "-*- C++ -*-" part, that's only for .h files.

include/llvm/Analysis/BasicAliasAnalysis.h

 /// analysis. It implements the AA query interface in an entirely stateless
 /// manner. As one consequence, it is never invalidated. While it does retain
 /// some storage, that is used as an optimization and not to preserve
 /// information from query to query.
 class BasicAAResult : public AAResultBase<BasicAAResult> {
   friend AAResultBase<BasicAAResult>;
 
   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.
   ///
   /// By definition, this result is stateless and so remains valid.
   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
 

include/llvm/IR/InvariantInfo.h

+//===-------- 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<Value *, IntrinsicInst *> 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

include/llvm/IR/Module.h

 #define LLVM_IR_MODULE_H
 
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Comdat.h"
 #include "llvm/IR/DataLayout.h"
 #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"
 #include "llvm/Support/DataTypes.h"
 #include <system_error>
 
 namespace llvm {
 class FunctionType;
private:
   ComdatSymTabType ComdatSymTab;  ///< Symbol table for COMDATs
   std::unique_ptr<GVMaterializer>
   Materializer;                   ///< Used to materialize GlobalValues
   std::string ModuleID;           ///< Human readable identifier for the module
   std::string TargetTriple;       ///< Platform target triple Module compiled on
                                   ///< 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;
 
 /// @}
 /// @name Constructors
 /// @{
 public:
   /// The Module constructor. Note that there is no default constructor. You
/// @{
   /// equivalent to getDataLayout()->getStringRepresentation().
   const std::string &getDataLayoutStr() const {
     return DL.getStringRepresentation();
   }
 
   /// 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; }
 
   /// Get the global data context.
   /// @returns LLVMContext - a container for LLVM's global information
   LLVMContext &getContext() const { return Context; }
 

lib/Analysis/BasicAliasAnalysis.cpp

if (!Visited.insert(V).second) {
       Visited.clear();
       return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
     }
 
     // An alloca instruction defines local memory.
     if (OrLocal && isa<AllocaInst>(V))
       continue;
 
+    if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
+      if (InvInfo.GetStartInstruction(AI)) continue;
+
     // A global constant counts as local memory for our purposes.
     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(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);
       }
       continue;
     }
 
     // If both select values point to local memory, then so does the select.
     if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
   // shrink_and_clear so it quickly returns to the inline capacity of the
   // SmallDenseMap if it ever grows larger.
   // FIXME: This should really be shrink_to_inline_capacity_and_clear().
   AliasCache.shrink_and_clear();
   VisitedPhiBBs.clear();
   return Alias;
 }
 
+static bool isInvariantIntrinsic(ImmutableCallSite CS) {
+  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(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.
 ///
 /// Since we only look at local properties of this function, we really can't
 /// say much about this query.  We do, however, use simple "address taken"
 /// analysis on local objects.
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
                                         const MemoryLocation &Loc) {
ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
   }
 
   // While the assume intrinsic is marked as arbitrarily writing so that
   // proper control dependencies will be maintained, it never aliases any
   // particular memory location.
   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);
 }
 
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
                                         ImmutableCallSite CS2) {
   // While the assume intrinsic is marked as arbitrarily writing so that
   // proper control dependencies will be maintained, it never aliases any
   // particular memory location.
   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);
 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                             uint64_t V1Size,

 //===----------------------------------------------------------------------===//
 
 char BasicAA::PassID;
 
 BasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) {
   return BasicAAResult(F.getParent()->getDataLayout(),
                        AM->getResult<TargetLibraryAnalysis>(F),
                        AM->getResult<AssumptionAnalysis>(F),
+                       F.getParent()->getInvariantInfo(),
                        AM->getCachedResult<DominatorTreeAnalysis>(F),
                        AM->getCachedResult<LoopAnalysis>(F));
 }
 
 char BasicAAWrapperPass::ID = 0;
 void BasicAAWrapperPass::anchor() {}
 
 INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",

 bool BasicAAWrapperPass::runOnFunction(Function &F) {
   auto &ACT = getAnalysis<AssumptionCacheTracker>();
   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
   auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
 
   Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
                                  ACT.getAssumptionCache(F),
+                                 F.getParent()->getInvariantInfo(),
                                  DTWP ? &DTWP->getDomTree() : nullptr,
                                  LIWP ? &LIWP->getLoopInfo() : nullptr));
 
   return false;
 }
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
 
 BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
   return BasicAAResult(
       F.getParent()->getDataLayout(),
       P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
-      P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
+      P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
+      F.getParent()->getInvariantInfo());
 }

lib/IR/CMakeLists.txt

add_llvm_library(LLVMCore
   GVMaterializer.cpp
   Globals.cpp
   IRBuilder.cpp
   IRPrintingPasses.cpp
   InlineAsm.cpp
   Instruction.cpp
   Instructions.cpp
   IntrinsicInst.cpp
+  InvariantInfo.cpp
   LLVMContext.cpp
   LLVMContextImpl.cpp
   LegacyPassManager.cpp
   MDBuilder.cpp
   Mangler.cpp
   Metadata.cpp
   MetadataTracking.cpp
   Module.cpp

lib/IR/InvariantInfo.cpp

+//===---------- 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<GlobalVariable>(Addr) && !isa<AllocaInst>(Addr)) return nullptr;
+
+  // constant globals are also not marked.
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
+    if (GV->isConstant()) return nullptr;
+  }
+
+  // Retrieve the value from the markers map.
+  auto EntryIter = InvariantMarkers.find(const_cast<Value *>(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<GlobalVariable>(Addr) && !isa<AllocaInst>(Addr)) return;
+
+  assert((!IStart || IStart->getIntrinsicID() == Intrinsic::invariant_start) &&
+         "Given intrinsic instruction is not invariant_start");
+  if (IStart && isa<AllocaInst>(Addr))
+    assert(IStart->getParent() == cast<AllocaInst>(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<LoadInst>(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<IntrinsicInst>(IStart) &&
+           "This invariant_end's start instruction could not match the "
+           "preserved invariant_start, if preserved.");
+    return true;
+  }
+  return false;
+}

unittests/Analysis/AliasAnalysisTest.cpp

protected:
   AliasAnalysisTest() : M("AliasAnalysisTest", C), TLI(TLII) {}
 
   AAResults &getAAResults(Function &F) {
     // Reset the Function AA results first to clear out any references.
     AAR.reset(new AAResults());
 
     // 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;
   }
 };
 
 TEST_F(AliasAnalysisTest, getModRefInfo) {
   // Setup function.