[AA] Add the notion of target-specific alias analyses.

[jlebar]

Summary

This allows the TTI to specify an alias analysis specifically for its
target.

Example usage (in MyTargetTTI.cpp):

class MyTargetAAresult : public AAResultBase<MyTargetAAResult> { ... };

class MyTargetAAResultProvider : public AAResultProvider {
  MyTargetAAResult Result;
public:
  void addAAResult(AAResults &AAR) override {
    // AAR only keeps a reference to Result; we have to keep it alive.
    AAR.addResult(Result);
  }
};

std::unique_ptr<AAResultProvider>
MyTargetTTI::getAAResultProvider(const Function *) {
  return make_unique<MyTargetAAResultProvider>();
}

A simpler API (that doesn't end up working) would be to have a different
function on TTI:

TargetTransformInfo::addAAResult(const Function *, AAResults &)

This would also more closely mirror how external AAs work.

The problem with this is that AAResults::addAAResult takes a reference
to the result it's given, so that object must be stored somewhere. With
the external AA framework, the external target is expected to register a
pass and store its AAResult in that pass. But that doesn't work for our
purposes; we have no way to get the TTI to register a pass (nor do I
think that's desirable).

So instead, we essentially have the TTI return a closure which stores
the AAResult and provides access to it via
AAResultProvider::addAAResult. We use a custom class rather than
std::function for this closure because std::functions must be copyable,
but it's natural for this closure to capture non-copyable objects.

[hfinkel]

It seems somewhat unfortunate to have both ExternalAAWrapperPass and TargetSpecificAAWrapperPass. It also seems unfortunate that we can only ever have one external AA provider. What if we let ExternalAAWrapperPass contain an array of callbacks and let the target add to that array?

[jlebar]

In D24441#551627, @hfinkel wrote:

It seems somewhat unfortunate to have both ExternalAAWrapperPass and TargetSpecificAAWrapperPass. It also seems unfortunate that we can only ever have one external AA provider. What if we let ExternalAAWrapperPass contain an array of callbacks and let the target add to that array?

That seems simple enough. We'd need to change the external wrapper pass to use AAResultsProvider (a raw callback isn't going to work for a target-specific pass, see the commit message), but if anything I think that will be a simplification for clients of the external thing.

[chandlerc]

While we don't have any way for TTI to register a pass, we do have a way for the *target* to register a pass.

In D24441#551638, @jlebar wrote:

In D24441#551627, @hfinkel wrote:

It seems somewhat unfortunate to have both ExternalAAWrapperPass and TargetSpecificAAWrapperPass. It also seems unfortunate that we can only ever have one external AA provider. What if we let ExternalAAWrapperPass contain an array of callbacks and let the target add to that array?

That seems simple enough. We'd need to change the external wrapper pass to use AAResultsProvider (a raw callback isn't going to work for a target-specific pass, see the commit message), but if anything I think that will be a simplification for clients of the external thing.

I think instead, the target *can* actually add a separate pass to provide the AA results, and then you should be able to use the external AA hooks already present. Let me find the place where you can do this from the target.

[jlebar]

I think instead, the target *can* actually add a separate pass to provide the AA results, and then you should be able to use the external AA hooks already present.

...with a modification to support running more than one, I presume?

I'm fine with that (if you can show me how this is supposed to work), although personally I think having to register a pass just to store this data seems...kind of weird? Maybe there is a good reason to do it that way as opposed to with the explicit callback objects as in the commit message here.

[jlebar]

In case anyone is watching this, I'm currently waiting for Chandler to put together a promised Correct Way of doing this that will work with the new pass manager.

llvm/include/llvm/Analysis/AliasAnalysis.h

 ///
 /// The callback provided here will be used each time we prepare an AAResults
 /// object, and will receive a reference to the function wrapper pass, the
 /// function, and the AAResults object to populate. This should be used when
 /// setting up a custom pass pipeline to inject a hook into the AA results.
 ImmutablePass *createExternalAAWrapperPass(
     std::function<void(Pass &, Function &, AAResults &)> Callback);
 
+/// A wrapper pass that lets TargetTransformInfo inject its own target-specific
+/// alias analysis.
+///
+/// When this pass is enabled, creation of the AA chain invokes
+/// TargetTransformInfo::getAAResultProvider(). If the result is not null, we
+/// use the provider to add an AA result to the chain.
+ImmutablePass *createTargetSpecificAAWrapperPass();
+
 /// A helper for the legacy pass manager to create a \c AAResults
 /// object populated to the best of our ability for a particular function when
 /// inside of a \c ModulePass or a \c CallGraphSCCPass.
 ///
 /// If a \c ModulePass or a \c CallGraphSCCPass calls \p
 /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
 /// getAnalysisUsage.
 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
 
 /// A helper for the legacy pass manager to populate \p AU to add uses to make
 /// sure the analyses required by \p createLegacyPMAAResults are available.
 void getAAResultsAnalysisUsage(AnalysisUsage &AU);
 
 } // End llvm namespace
 
 #endif

llvm/include/llvm/Analysis/TargetTransformInfo.h

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/DataTypes.h"
 #include <functional>
 
 namespace llvm {
 
+class AAResults;
 class Function;
 class GlobalValue;
 class Loop;
 class Type;
 class User;
 class Value;
 
 /// \brief Information about a load/store intrinsic defined by the target.
public:
   Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
                                            Type *ExpectedType) const;
 
   /// \returns True if the two functions have compatible attributes for inlining
   /// purposes.
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const;
 
+  /// AAResultProvider is a proxy class that lets you implement target-specific
+  /// alias analyses:
+  ///
+  ///   class MyTargetAAresult : public AAResultBase<MyTargetAAResult> { ... };
+  ///
+  ///   class MyTargetAAResultProvider : public AAResultProvider {
+  ///     MyTargetAAResult Result;
+  ///   public:
+  ///     void addAAResult(AAResults &AAR) override {
+  ///       // AAR only keeps a reference to Result; we have to keep it alive.
+  ///       AAR.addResult(Result);
+  ///     }
+  ///   };
+  ///
+  ///   std::unique_ptr<AAResultProvider>
+  ///   MyTargetTTI::getAAResultProvider(const Function *) {
+  ///     return make_unique<MyTargetAAResultProvider>();
+  ///   }
+  ///
+  /// (Essentially, AAResultProvider is a closure object that stores an object
+  /// derived from AAResultBase.  We don't use std::function because it's
+  /// natural for these objects to be move-only and/or contain non-copyable
+  /// members, and std::functions must be copyable.)
+  class AAResultProvider {
+  public:
+    virtual ~AAResultProvider() {}
+    virtual void addAAResult(AAResults &AAR) = 0;
+  };
+
+  /// \returns nullptr or an AAResultProvider which the alias analysis machinery
+  /// can use to inject a target-specific alias analysis into the AA chain.
+  std::unique_ptr<AAResultProvider>
+  getAAResultProvider(const Function *F) const;
+
   /// @}
 
 private:
   /// \brief The abstract base class used to type erase specific TTI
   /// implementations.
   class Concept;
 
   /// \brief The template model for the base class which wraps a concrete
public:
   virtual int getAddressComputationCost(Type *Ty, bool IsComplex) = 0;
   virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) = 0;
   virtual bool getTgtMemIntrinsic(IntrinsicInst *Inst,
                                   MemIntrinsicInfo &Info) = 0;
   virtual Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
                                                    Type *ExpectedType) = 0;
   virtual bool areInlineCompatible(const Function *Caller,
                                    const Function *Callee) const = 0;
+  virtual std::unique_ptr<AAResultProvider>
+  getAAResultProvider(const Function *F) = 0;
 };
 
 template <typename T>
 class TargetTransformInfo::Model final : public TargetTransformInfo::Concept {
   T Impl;
 
 public:
   Model(T Impl) : Impl(std::move(Impl)) {}
public:
   Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
                                            Type *ExpectedType) override {
     return Impl.getOrCreateResultFromMemIntrinsic(Inst, ExpectedType);
   }
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const override {
     return Impl.areInlineCompatible(Caller, Callee);
   }
+  std::unique_ptr<AAResultProvider>
+  getAAResultProvider(const Function *F) override {
+    return Impl.getAAResultProvider(F);
+  }
 };
 
 template <typename T>
 TargetTransformInfo::TargetTransformInfo(T Impl)
     : TTIImpl(new Model<T>(Impl)) {}
 
 /// \brief Analysis pass providing the \c TargetTransformInfo.
 ///

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const {
     return (Caller->getFnAttribute("target-cpu") ==
             Callee->getFnAttribute("target-cpu")) &&
            (Caller->getFnAttribute("target-features") ==
             Callee->getFnAttribute("target-features"));
   }
+
+  std::unique_ptr<TargetTransformInfo::AAResultProvider>
+  getAAResultProvider(const Function *F) const {
+    return nullptr;
+  }
 };
 
 /// \brief CRTP base class for use as a mix-in that aids implementing
 /// a TargetTransformInfo-compatible class.
 template <typename T>
 class TargetTransformInfoImplCRTPBase : public TargetTransformInfoImplBase {
 private:
   typedef TargetTransformInfoImplBase BaseT;

llvm/include/llvm/InitializePasses.h

 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripNonDebugSymbolsPass(PassRegistry&);
 void initializeStripSymbolsPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
 void initializeTailCallElimPass(PassRegistry&);
 void initializeTailDuplicatePassPass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry &);
 void initializeTargetPassConfigPass(PassRegistry&);
+void initializeTargetSpecificAAWrapperPassPass(PassRegistry &);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry &);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesPass(PassRegistry&);
 void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);

llvm/lib/Analysis/AliasAnalysis.cpp

 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"

 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
                 false, true)
 
 ImmutablePass *
 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
   return new ExternalAAWrapperPass(std::move(Callback));
 }
 
+namespace {
+/// Wrapper pass for target-specific alias analyses.  Stores the TTI's
+/// AAResultProvider, which owns the AAResult.
+class TargetSpecificAAWrapperPass : public ImmutablePass {
+  std::unique_ptr<TargetTransformInfo::AAResultProvider> Provider;
+
+public:
+  static char ID;
+
+  TargetSpecificAAWrapperPass() : ImmutablePass(ID) {
+    initializeTargetSpecificAAWrapperPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
+  }
+
+  void reset() { Provider.reset(); }
+
+  void addAAResult(const Function &F, AAResults &AAR) {
+    assert(!Provider && "Provider should have been cleared first.");
+    // Try to get an AAResultProvider for this function from our TTI.
+    if ((Provider = getAnalysis<TargetTransformInfoWrapperPass>()
+                        .getTTI(F)
+                        .getAAResultProvider(&F)))
+      Provider->addAAResult(AAR);
+  }
+};
+} // anonymous namespace
+
+char TargetSpecificAAWrapperPass::ID = 0;
+INITIALIZE_PASS_BEGIN(TargetSpecificAAWrapperPass, "target-specific-aa",
+                      "Target-specific Alias Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_END(TargetSpecificAAWrapperPass, "target-specific-aa",
+                    "Target-specific Alias Analysis", false, true)
+
+ImmutablePass *llvm::createTargetSpecificAAWrapperPass() {
+  return new TargetSpecificAAWrapperPass();
+}
+
 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 char AAResultsWrapperPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
                       "Function Alias Analysis Results", false, true)
 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetSpecificAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
                     "Function Alias Analysis Results", false, true)
 
 FunctionPass *llvm::createAAResultsWrapperPass() {
   return new AAResultsWrapperPass();
 }
 
 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
 ///
 /// This is the legacy pass manager's interface to the new-style AA results
 /// aggregation object. Because this is somewhat shoe-horned into the legacy
 /// pass manager, we hard code all the specific alias analyses available into
 /// it. While the particular set enabled is configured via commandline flags,
 /// adding a new alias analysis to LLVM will require adding support for it to
 /// this list.
 bool AAResultsWrapperPass::runOnFunction(Function &F) {
+  // First, clear the target-specific AA's AAResultProvider, which may have a
+  // reference to AAR.
+  if (auto *WrapperPass = getAnalysisIfAvailable<TargetSpecificAAWrapperPass>())
+    WrapperPass->reset();
+
   // NB! This *must* be reset before adding new AA results to the new
   // AAResults object because in the legacy pass manager, each instance
   // of these will refer to the *same* immutable analyses, registering and
   // unregistering themselves with them. We need to carefully tear down the
   // previous object first, in this case replacing it with an empty one, before
   // registering new results.
   AAR.reset(
       new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
bool AAResultsWrapperPass::runOnFunction(Function &F) {
   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = getAnalysisIfAvailable<TargetSpecificAAWrapperPass>())
+    WrapperPass->addAAResult(F, *AAR);
 
   // If available, run an external AA providing callback over the results as
   // well.
   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
     if (WrapperPass->CB)
       WrapperPass->CB(*this, F, *AAR);
 
   // Analyses don't mutate the IR, so return false.

llvm/lib/Analysis/TargetTransformInfo.cpp

Value *TargetTransformInfo::getOrCreateResultFromMemIntrinsic(
   return TTIImpl->getOrCreateResultFromMemIntrinsic(Inst, ExpectedType);
 }
 
 bool TargetTransformInfo::areInlineCompatible(const Function *Caller,
                                               const Function *Callee) const {
   return TTIImpl->areInlineCompatible(Caller, Callee);
 }
 
+std::unique_ptr<TargetTransformInfo::AAResultProvider>
+TargetTransformInfo::getAAResultProvider(const Function *F) const {
+  return TTIImpl->getAAResultProvider(F);
+}
+
 TargetTransformInfo::Concept::~Concept() {}
 
 TargetIRAnalysis::TargetIRAnalysis() : TTICallback(&getDefaultTTI) {}
 
 TargetIRAnalysis::TargetIRAnalysis(
     std::function<Result(const Function &)> TTICallback)
     : TTICallback(std::move(TTICallback)) {}
 

llvm/lib/CodeGen/TargetPassConfig.cpp

 void TargetPassConfig::addVerifyPass(const std::string &Banner) {
   if (VerifyMachineCode)
     PM->add(createMachineVerifierPass(Banner));
 }
 
 /// Add common target configurable passes that perform LLVM IR to IR transforms
 /// following machine independent optimization.
 void TargetPassConfig::addIRPasses() {
+  addPass(createTargetSpecificAAWrapperPass());
+
   switch (UseCFLAA) {
   case CFLAAType::Steensgaard:
     addPass(createCFLSteensAAWrapperPass());
     break;
   case CFLAAType::Andersen:
     addPass(createCFLAndersAAWrapperPass());
     break;
   case CFLAAType::Both:

llvm/lib/Target/NVPTX/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS NVPTX.td)
 
 
 tablegen(LLVM NVPTXGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM NVPTXGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM NVPTXGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM NVPTXGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM NVPTXGenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(NVPTXCommonTableGen)
 
 set(NVPTXCodeGen_sources
+  NVPTXAliasAnalysis.cpp
   NVPTXAllocaHoisting.cpp
   NVPTXAsmPrinter.cpp
   NVPTXAssignValidGlobalNames.cpp
   NVPTXFavorNonGenericAddrSpaces.cpp
   NVPTXFrameLowering.cpp
   NVPTXGenericToNVVM.cpp
   NVPTXISelDAGToDAG.cpp
   NVPTXISelLowering.cpp

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

if ((*GlobalExtensions)[i].first == ETy)
       (*GlobalExtensions)[i].second(*this, PM);
   for (unsigned i = 0, e = Extensions.size(); i != e; ++i)
     if (Extensions[i].first == ETy)
       Extensions[i].second(*this, PM);
 }
 
 void PassManagerBuilder::addInitialAliasAnalysisPasses(
     legacy::PassManagerBase &PM) const {
+  PM.add(createTargetSpecificAAWrapperPass());
   switch (UseCFLAA) {
   case CFLAAType::Steensgaard:
     PM.add(createCFLSteensAAWrapperPass());
     break;
   case CFLAAType::Andersen:
     PM.add(createCFLAndersAAWrapperPass());
     break;
   case CFLAAType::Both: