[NVPTX] Implement NVPTX AliasAnalysis

[asavonic]

Summary

NVPTXAliasAnalysis extends the default AA to take pointer address spaces
into account. The analysis assumes that pointers in different address
spaces do not alias, unless one of them is generic (flat) address
space.

The patch also implements pointsToConstantMemory (via getModRefInfoMask)
to expose semantic of the constant address space to the optimizer
as discussed in D112466.

[tra]

LGTM in general.

@asbirlea : Could you take a look and check if we've got all the right pieces for the pass for both new and old PM, please?

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Nit. I'd rephrase it a bit and put alias() call closer to the condition check.

if (getAliasResult(AS1, AS2) != AliasResult::NoAlias) 
    return AAResultBase::alias(Loc1, Loc2, AAQI);
return  AliasResult::NoAlias;

Maybe, even fold it into a single return (...== NoAlias) ? NoAlias : alias();

72

Kernel parameters are also read-only: https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#state-spaces

[asavonic]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Done.

72

Thanks! Added param space to the check and updated LIT tests.

[tra]

@nikic -- we could use your input here. The patch looks OK to me, but I'm not particularly familiar with AA machinery in general and could use a second opinion.

[tschuett]

Could that be a more general solution? You ask the target if address spaces A and B could alias?

[nikic]

Looks fine from a cursory look. To double check, this property also holds up in the presence of addrspacecasts? Note that AA will skip past those, so if you compare ptr addrspace(1) %x and addrspacecast (ptr addrspace(5) %y to ptr addrspace(1)), this will perform a comparison of ptr addrspace(1) %x and ptr addrspace(5) %y. I assume that the addrspacecast would just be considered illegal in the relevant cases?

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Can't you just return getAliasResult(AS1, AS2) here? Calling AAResultBase methods is not necessary, it'll always return MayAlias (there are some confusing comments about this in other AA implemementations, but chaining of AA providers happens at a different level nowadays).

84

Shouldn't be necessary, as the BasicAA implementation already covers this.

[asavonic]

• Rebased
• Removed calls to AAResultBase and the extra check for GV->isConstant.

[asavonic]

This took a while, I'm sorry for not following up earlier.

In D124787#3614613, @nikic wrote:

Looks fine from a cursory look. To double check, this property also holds up in the presence of addrspacecasts? Note that AA will skip past those, so if you compare ptr addrspace(1) %x and addrspacecast (ptr addrspace(5) %y to ptr addrspace(1)), this will perform a comparison of ptr addrspace(1) %x and ptr addrspace(5) %y. I assume that the addrspacecast would just be considered illegal in the relevant cases?

Yes, pointers in different address spaces do not alias unless at least one of them is in generic (flat) address space. Address space casts can only cast from/to generic address space, otherwise they are invalid.

Note that AA will skip past those

This might be an opportunity to improve the analysis. When we skip addrspacecasts from two pointers, we may end up with pointers in generic address space, and the result is always MayAlias. We can get better results from original pointers if they are in different address spaces (e.g. local and global AS never alias).

In D124787#3613322, @tschuett wrote:

Could that be a more general solution? You ask the target if address spaces A and B could alias?

We can add a simple check to TTI, and integrate it to BasicAA, but I think the current interface is simple enough already. Having access to MemoryLocation can be important: we can traverse a chain of address space casts and make a better AA decision (see AMDGPU AA for example). Also, pointsToConstantMemory check is done via AA anyway, so we have to implement a target-specific AA to customize it.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

65

Right, thank you!

84

Right, it is handled in BasicAA.

[asavonic]

• Rebased.
• Replaced pointsToConstantMemory with getModRefInfoMask due to the API change.
• Removed DataLayout variable that was unused.

[asavonic]

@nikic, @tra, please let me know if any other changes are needed.

[tra]

LGTM in general for LLVM as it is now. But...

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Looks like recently PTX grew ability to convert .param to generic AS:
https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#data-movement-and-conversion-instructions-cvta

AFAICT, when that happens, the address *may* be converted into a global pointer:
https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#generic-addressing says:

The Kernel Function Parameters (.param) window is contained within the .global window.

So, technically, a global pointer *may* alias with a param pointer on some GPUs via ASC(param->generic->global).

The good news is that we don't have cvta.param implemented yet, so as things stand, there's no aliasing between param and global, but that will likely change in the future. We may want to either conservatively make them "mayAlias" from now on, or keep them as "NoAlias" for now with a TODO to make sure we update it when we get to implement cvta.param in lib/Target/NVPTX/NVPTXIntrinsics.td

[asavonic]

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Hmm.. this is unfortunate. If param is a subset of global, then it also cannot be treated as constant memory. I'll update alias and getModRefInfoMask functions to handle this.

[asavonic]

• param pointers may alias global pointers.
• added more test cases for param.

[tra]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

62

param->generic is not implemented yet, so this is overly conservative.

Do we have any way to check whether ASC(param->generic) is available? If we do, we could use it to determine if we should return MayAlias or NoAlias.

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

.param AS is a bit special when it comes to constantness.

Param space should not ever be used in the user-provided IR. As far as the user IR is concerned, byval arguments live in generic AS and are writeable.

In order to make sure byval arguments are never written to, as required by PTX, we make a local copy, if one needs to store to it. From that point of view, AS should also consider param space as writable, even though we'll never generate actual writes to it and redirect them to a local copy.

[asavonic]

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

83

Ok, to summarize:

1. NVPTXLowerArgs does not allow any writes or pointer copies of param pointers by redirecting them to a local copy.

2. cvta.param (PTX 7.7+ and SM_70+) is not implemented, and therefore we have no way to cast it to generic and avoid the redirect (1).

So while both these implementation details are true, param pointers point to "constant" memory (there are no writes to it), and do not alias with anything except for other param pointers.

I guess we can put a TODO explaining this for now. Once NVPTXLowerArgs is changed to support cvta.param we'll have to re-evaluate this.

[asavonic]

• Rolled back changes for param address space: treat it as constant memory until cvta.param is supported.
• Changed tests to use opaque pointers.

[asavonic]

@tra, can you please check if it is OK to merge this patch?

[tra]

Still LGTM with a couple of nits.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

CtxI does not seem to be used. Do we need it?

91

IMO, the code would be more readable w/o the variable. Just do if (isConstOrParam(Loc.Ptr->getType()->getPointerAddressSpace())) directly here and below.

Having the variable makes me, as a reader, ask -- "what was the variable set to before?", "what else is this variable used for?" and that's just a distraction here.

[asavonic]

• Fixed code style issues.

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

It is a new parameter from D136512. We do not currently use it, so I guess it is better to drop it to avoid warnings.

91

Makes sense. Done.

[tra]

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

73

So, the intent is to match the signature of AAResultBase::alias()?
OK. I was thinking of getting rid of the argument altogether, but it looks like it's needed, after all.

llvm/lib/Target/NVPTX/CMakeLists.txt

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

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.h

+//===-------------------- NVPTXAliasAnalysis.h ------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This is the NVPTX address space based alias analysis pass.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_NVPTX_NVPTXALIASANALYSIS_H
+#define LLVM_LIB_TARGET_NVPTX_NVPTXALIASANALYSIS_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+
+namespace llvm {
+
+class MemoryLocation;
+
+class NVPTXAAResult : public AAResultBase {
+public:
+  NVPTXAAResult() {}
+  NVPTXAAResult(NVPTXAAResult &&Arg) : AAResultBase(std::move(Arg)) {}
+
+  /// Handle invalidation events from the new pass manager.
+  ///
+  /// By definition, this result is stateless and so remains valid.
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &Inv) {
+    return false;
+  }
+
+  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
+                    AAQueryInfo &AAQI, const Instruction *CtxI = nullptr);
+
+  ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
+                               bool IgnoreLocals);
+};
+
+/// Analysis pass providing a never-invalidated alias analysis result.
+class NVPTXAA : public AnalysisInfoMixin<NVPTXAA> {
+  friend AnalysisInfoMixin<NVPTXAA>;
+
+  static AnalysisKey Key;
+
+public:
+  using Result = NVPTXAAResult;
+
+  NVPTXAAResult run(Function &F, AnalysisManager<Function> &AM) {
+    return NVPTXAAResult();
+  }
+};
+
+/// Legacy wrapper pass to provide the NVPTXAAResult object.
+class NVPTXAAWrapperPass : public ImmutablePass {
+  std::unique_ptr<NVPTXAAResult> Result;
+
+public:
+  static char ID;
+
+  NVPTXAAWrapperPass();
+
+  NVPTXAAResult &getResult() { return *Result; }
+  const NVPTXAAResult &getResult() const { return *Result; }
+
+  bool doInitialization(Module &M) override {
+    Result.reset(new NVPTXAAResult());
+    return false;
+  }
+
+  bool doFinalization(Module &M) override {
+    Result.reset();
+    return false;
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+// Wrapper around ExternalAAWrapperPass so that the default
+// constructor gets the callback.
+class NVPTXExternalAAWrapper : public ExternalAAWrapperPass {
+public:
+  static char ID;
+
+  NVPTXExternalAAWrapper()
+      : ExternalAAWrapperPass([](Pass &P, Function &, AAResults &AAR) {
+          if (auto *WrapperPass =
+                  P.getAnalysisIfAvailable<NVPTXAAWrapperPass>())
+            AAR.addAAResult(WrapperPass->getResult());
+        }) {}
+};
+
+ImmutablePass *createNVPTXAAWrapperPass();
+void initializeNVPTXAAWrapperPassPass(PassRegistry &);
+ImmutablePass *createNVPTXExternalAAWrapperPass();
+void initializeNVPTXExternalAAWrapperPass(PassRegistry &);
+
+} // end namespace llvm
+
+#endif // LLVM_LIB_TARGET_NVPTX_NVPTXALIASANALYSIS_H

llvm/lib/Target/NVPTX/NVPTXAliasAnalysis.cpp

+//===--------------------- NVPTXAliasAnalysis.cpp--------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This is the NVPTX address space based alias analysis pass.
+//===----------------------------------------------------------------------===//
+
+#include "NVPTXAliasAnalysis.h"
+#include "MCTargetDesc/NVPTXBaseInfo.h"
+#include "NVPTX.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/CallingConv.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "NVPTX-aa"
+
+AnalysisKey NVPTXAA::Key;
+
+char NVPTXAAWrapperPass::ID = 0;
+char NVPTXExternalAAWrapper::ID = 0;
+
+INITIALIZE_PASS(NVPTXAAWrapperPass, "nvptx-aa",
+                "NVPTX Address space based Alias Analysis", false, true)
+
+INITIALIZE_PASS(NVPTXExternalAAWrapper, "nvptx-aa-wrapper",
+                "NVPTX Address space based Alias Analysis Wrapper", false, true)
+
+ImmutablePass *llvm::createNVPTXAAWrapperPass() {
+  return new NVPTXAAWrapperPass();
+}
+
+ImmutablePass *llvm::createNVPTXExternalAAWrapperPass() {
+  return new NVPTXExternalAAWrapper();
+}
+
+NVPTXAAWrapperPass::NVPTXAAWrapperPass() : ImmutablePass(ID) {
+  initializeNVPTXAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+void NVPTXAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+static AliasResult::Kind getAliasResult(unsigned AS1, unsigned AS2) {
+  if ((AS1 == ADDRESS_SPACE_GENERIC) || (AS2 == ADDRESS_SPACE_GENERIC))
+    return AliasResult::MayAlias;
+
+  // PTX s6.4.1.1. Generic Addressing:
+  // A generic address maps to global memory unless it falls within
+  // the window for const, local, or shared memory. The Kernel
+  // Function Parameters (.param) window is contained within the
+  // .global window.
+  //
+  // Therefore a global pointer may alias with a param pointer on some
+  // GPUs via addrspacecast(param->generic->global) when cvta.param
+  // instruction is used (PTX 7.7+ and SM_70+).
+  //
+  // TODO: cvta.param is not yet supported. We need to change aliasing
+  // rules once it is added.
+
+  return (AS1 == AS2 ? AliasResult::MayAlias : AliasResult::NoAlias);
+}
+
+AliasResult NVPTXAAResult::alias(const MemoryLocation &Loc1,
+                                 const MemoryLocation &Loc2, AAQueryInfo &AAQI,
+                                 const Instruction *) {
+  unsigned AS1 = Loc1.Ptr->getType()->getPointerAddressSpace();
+  unsigned AS2 = Loc2.Ptr->getType()->getPointerAddressSpace();
+
+  return getAliasResult(AS1, AS2);
+}
+
+// TODO: .param address space may be writable in presence of cvta.param, but
+// this instruction is currently not supported. NVPTXLowerArgs also does not
+// allow any writes to .param pointers.
+static bool isConstOrParam(unsigned AS) {
+  return AS == AddressSpace::ADDRESS_SPACE_CONST ||
+         AS == AddressSpace::ADDRESS_SPACE_PARAM;
+}
+
+ModRefInfo NVPTXAAResult::getModRefInfoMask(const MemoryLocation &Loc,
+                                            AAQueryInfo &AAQI,
+                                            bool IgnoreLocals) {
+  if (isConstOrParam(Loc.Ptr->getType()->getPointerAddressSpace()))
+    return ModRefInfo::NoModRef;
+
+  const Value *Base = getUnderlyingObject(Loc.Ptr);
+  if (isConstOrParam(Base->getType()->getPointerAddressSpace()))
+    return ModRefInfo::NoModRef;
+
+  return AAResultBase::getModRefInfoMask(Loc, AAQI, IgnoreLocals);
+}

llvm/lib/Target/NVPTX/NVPTXTargetMachine.h

public:
   TargetLoweringObjectFile *getObjFileLowering() const override {
     return TLOF.get();
   }
 
   MachineFunctionInfo *
   createMachineFunctionInfo(BumpPtrAllocator &Allocator, const Function &F,
                             const TargetSubtargetInfo *STI) const override;
 
+  void registerDefaultAliasAnalyses(AAManager &AAM) override;
+
   void registerPassBuilderCallbacks(PassBuilder &PB) override;
 
   TargetTransformInfo getTargetTransformInfo(const Function &F) const override;
 
   bool isMachineVerifierClean() const override {
     return false;
   }
 

llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp

 //===-- NVPTXTargetMachine.cpp - Define TargetMachine for NVPTX -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Top-level implementation for the NVPTX target.
 //
 //===----------------------------------------------------------------------===//
 
 #include "NVPTXTargetMachine.h"
 #include "NVPTX.h"
+#include "NVPTXAliasAnalysis.h"
 #include "NVPTXAllocaHoisting.h"
 #include "NVPTXAtomicLower.h"
 #include "NVPTXLowerAggrCopies.h"
 #include "NVPTXMachineFunctionInfo.h"
 #include "NVPTXTargetObjectFile.h"
 #include "NVPTXTargetTransformInfo.h"
 #include "TargetInfo/NVPTXTargetInfo.h"
 #include "llvm/ADT/STLExtras.h"

 void initializeNVPTXAssignValidGlobalNamesPass(PassRegistry&);
 void initializeNVPTXAtomicLowerPass(PassRegistry &);
 void initializeNVPTXLowerAggrCopiesPass(PassRegistry &);
 void initializeNVPTXLowerAllocaPass(PassRegistry &);
 void initializeNVPTXLowerArgsPass(PassRegistry &);
 void initializeNVPTXProxyRegErasurePass(PassRegistry &);
 void initializeNVVMIntrRangePass(PassRegistry &);
 void initializeNVVMReflectPass(PassRegistry &);
+void initializeNVPTXAAWrapperPassPass(PassRegistry &);
+void initializeNVPTXExternalAAWrapperPass(PassRegistry &);
 
 } // end namespace llvm
 
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeNVPTXTarget() {
   // Register the target.
   RegisterTargetMachine<NVPTXTargetMachine32> X(getTheNVPTXTarget32());
   RegisterTargetMachine<NVPTXTargetMachine64> Y(getTheNVPTXTarget64());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   // FIXME: This pass is really intended to be invoked during IR optimization,
   // but it's very NVPTX-specific.
   initializeNVVMReflectPass(PR);
   initializeNVVMIntrRangePass(PR);
   initializeGenericToNVVMPass(PR);
   initializeNVPTXAllocaHoistingPass(PR);
   initializeNVPTXAssignValidGlobalNamesPass(PR);
   initializeNVPTXAtomicLowerPass(PR);
   initializeNVPTXLowerArgsPass(PR);
   initializeNVPTXLowerAllocaPass(PR);
   initializeNVPTXLowerAggrCopiesPass(PR);
   initializeNVPTXProxyRegErasurePass(PR);
   initializeNVPTXDAGToDAGISelPass(PR);
+  initializeNVPTXAAWrapperPassPass(PR);
+  initializeNVPTXExternalAAWrapperPass(PR);
 }
 
 static std::string computeDataLayout(bool is64Bit, bool UseShortPointers) {
   std::string Ret = "e";
 
   if (!is64Bit)
     Ret += "-p:32:32";
   else if (UseShortPointers)

 
 MachineFunctionInfo *NVPTXTargetMachine::createMachineFunctionInfo(
     BumpPtrAllocator &Allocator, const Function &F,
     const TargetSubtargetInfo *STI) const {
   return NVPTXMachineFunctionInfo::create<NVPTXMachineFunctionInfo>(Allocator,
                                                                     F, STI);
 }
 
+void NVPTXTargetMachine::registerDefaultAliasAnalyses(AAManager &AAM) {
+  AAM.registerFunctionAnalysis<NVPTXAA>();
+}
+
 void NVPTXTargetMachine::registerPassBuilderCallbacks(PassBuilder &PB) {
   PB.registerPipelineParsingCallback(
       [](StringRef PassName, FunctionPassManager &PM,
          ArrayRef<PassBuilder::PipelineElement>) {
         if (PassName == "nvvm-reflect") {
           PM.addPass(NVVMReflectPass());
           return true;
         }
         if (PassName == "nvvm-intr-range") {
           PM.addPass(NVVMIntrRangePass());
           return true;
         }
         return false;
       });
 
+  PB.registerAnalysisRegistrationCallback([](FunctionAnalysisManager &FAM) {
+    FAM.registerPass([&] { return NVPTXAA(); });
+  });
+
+  PB.registerParseAACallback([](StringRef AAName, AAManager &AAM) {
+    if (AAName == "nvptx-aa") {
+      AAM.registerFunctionAnalysis<NVPTXAA>();
+      return true;
+    }
+    return false;
+  });
+
   PB.registerPipelineStartEPCallback(
       [this](ModulePassManager &PM, OptimizationLevel Level) {
         FunctionPassManager FPM;
         FPM.addPass(NVVMReflectPass(Subtarget.getSmVersion()));
         // FIXME: NVVMIntrRangePass is causing numerical discrepancies,
         // investigate and re-enable.
         // FPM.addPass(NVVMIntrRangePass(Subtarget.getSmVersion()));
         PM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
void NVPTXPassConfig::addIRPasses() {
   disablePass(&StackMapLivenessID);
   disablePass(&LiveDebugValuesID);
   disablePass(&PostRAMachineSinkingID);
   disablePass(&PostRASchedulerID);
   disablePass(&FuncletLayoutID);
   disablePass(&PatchableFunctionID);
   disablePass(&ShrinkWrapID);
 
+  addPass(createNVPTXAAWrapperPass());
+  addPass(createExternalAAWrapperPass([](Pass &P, Function &, AAResults &AAR) {
+    if (auto *WrapperPass = P.getAnalysisIfAvailable<NVPTXAAWrapperPass>())
+      AAR.addAAResult(WrapperPass->getResult());
+  }));
+
   // NVVMReflectPass is added in addEarlyAsPossiblePasses, so hopefully running
   // it here does nothing.  But since we need it for correctness when lowering
   // to NVPTX, run it here too, in case whoever built our pass pipeline didn't
   // call addEarlyAsPossiblePasses.
   const NVPTXSubtarget &ST = *getTM<NVPTXTargetMachine>().getSubtargetImpl();
   addPass(createNVVMReflectPass(ST.getSmVersion()));
 
   if (getOptLevel() != CodeGenOpt::None)

llvm/test/CodeGen/NVPTX/nvptx-aa.ll

+; RUN: opt -passes=aa-eval -aa-pipeline=nvptx-aa -print-all-alias-modref-info < %s -S 2>&1 \
+; RUN:   | FileCheck %s --check-prefixes CHECK-ALIAS
+;
+; RUN: opt -aa-pipeline=nvptx-aa -passes=licm < %s -S | FileCheck %s --check-prefixes CHECK-AA-CONST
+; RUN: opt -aa-pipeline=basic-aa -passes=licm < %s -S | FileCheck %s --check-prefixes CHECK-NOAA-CONST
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+target triple = "nvptx64-nvidia-cuda"
+
+; CHECK-ALIAS-LABEL: Function: test
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(1)* %global
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(3)* %shared
+; CHECK-ALIAS: NoAlias:  i8 addrspace(1)* %global, i8 addrspace(3)* %shared
+; CHECK-ALIAS: MayAlias: i8 addrspace(4)* %const, i8* %gen
+; CHECK-ALIAS: NoAlias:  i8 addrspace(4)* %const, i8 addrspace(1)* %global
+; CHECK-ALIAS: NoAlias:  i8 addrspace(4)* %const, i8 addrspace(3)* %shared
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(5)* %local
+; CHECK-ALIAS: NoAlias:  i8 addrspace(1)* %global, i8 addrspace(5)* %local
+; CHECK-ALIAS: NoAlias:  i8 addrspace(5)* %local, i8 addrspace(3)* %shared
+; CHECK-ALIAS: NoAlias:  i8 addrspace(4)* %const, i8 addrspace(5)* %local
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(101)* %param
+; CHECK-ALIAS: NoAlias:  i8 addrspace(1)* %global, i8 addrspace(101)* %param
+; CHECK-ALIAS: NoAlias:  i8 addrspace(101)* %param, i8 addrspace(3)* %shared
+; CHECK-ALIAS: NoAlias:  i8 addrspace(4)* %const, i8 addrspace(101)* %param
+; CHECK-ALIAS: NoAlias:  i8 addrspace(5)* %local, i8 addrspace(101)* %param
+
+define i8 @test_alias(ptr %gen, ptr addrspace(1) %global, ptr addrspace(3) %shared, ptr addrspace(4) %const, ptr addrspace(5) %local) {
+  %param = addrspacecast ptr %gen to ptr addrspace(101)
+  %v1 = load i8, ptr %gen
+  %v2 = load i8, ptr addrspace(1) %global
+  %v3 = load i8, ptr addrspace(3) %shared
+  %v4 = load i8, ptr addrspace(4) %const
+  %v5 = load i8, ptr addrspace(5) %local
+  %v6 = load i8, ptr addrspace(101) %param
+  %res1 = add i8 %v1, %v2
+  %res2 = add i8 %res1, %v3
+  %res3 = add i8 %res2, %v4
+  %res4 = add i8 %res3, %v5
+  %res5 = add i8 %res4, %v6
+  ret i8 %res5
+}
+
+; CHECK-ALIAS-LABEL: Function: test_const
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(1)* %global
+; CHECK-ALIAS: NoAlias:  i8 addrspace(4)* %const, i8 addrspace(1)* %global
+; CHECK-ALIAS: MayAlias: i8 addrspace(4)* %const, i8* %gen
+;
+define i8 @test_const(ptr %gen, ptr addrspace(1) %global, ptr addrspace(4) %const) {
+;
+; Even though %gen and %const may alias and there is a store to %gen,
+; LICM should be able to hoist %load_const because it is known to be
+; constant (AA::pointsToConstantMemory()).
+;
+; CHECK-AA-CONST-LABEL: @test_const
+; CHECK-AA-CONST-LABEL: entry
+; CHECK-AA-CONST: %[[LOAD_CONST:.+]] = load i8, ptr addrspace(4)
+; CHECK-AA-CONST-LABEL: loop
+; CHECK-AA-CONST: add {{.*}}%[[LOAD_CONST]]
+;
+; Without NVPTX AA the load is left in the loop because we assume that
+; it may be clobbered by the store.
+;
+; CHECK-NOAA-CONST-LABEL: @test_const
+; CHECK-NOAA-CONST-LABEL: loop
+; CHECK-NOAA-CONST: %[[LOAD_CONST:.+]] = load i8, ptr addrspace(4)
+; CHECK-NOAA-CONST: add {{.*}}%[[LOAD_CONST]]
+entry:
+  br label %loop
+loop:
+  %v = phi i8 [0, %entry], [%v2, %loop]
+  %load_global = load i8, ptr addrspace(1) %global
+  store i8 %load_global, ptr %gen
+  %load_const = load i8, ptr addrspace(4) %const
+  %v2 = add i8 %v, %load_const
+  %cond = icmp eq i8 %load_const, 0
+  br i1 %cond, label %done, label %loop
+done:
+  ret i8 %v2
+}
+
+; Same as @test_const above, but for param space.
+;
+; CHECK-ALIAS-LABEL: Function: test_param
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(1)* %global
+; CHECK-ALIAS: NoAlias:  i8 addrspace(1)* %global, i8 addrspace(101)* %param
+; CHECK-ALIAS: MayAlias: i8* %gen, i8 addrspace(101)* %param
+;
+define i8 @test_param(ptr %gen, ptr addrspace(1) %global, ptr %param_gen) {
+;
+; CHECK-AA-CONST-LABEL: @test_param
+; CHECK-AA-CONST-LABEL: entry
+; CHECK-AA-CONST: %[[LOAD_PARAM:.+]] = load i8, ptr addrspace(101)
+; CHECK-AA-CONST-LABEL: loop
+; CHECK-AA-CONST: add {{.*}}%[[LOAD_PARAM]]
+;
+; CHECK-NOAA-CONST-LABEL: @test_param
+; CHECK-NOAA-CONST-LABEL: loop
+; CHECK-NOAA-CONST: %[[LOAD_PARAM:.+]] = load i8, ptr addrspace(101)
+; CHECK-NOAA-CONST: add {{.*}}%[[LOAD_PARAM]]
+entry:
+  %param = addrspacecast ptr %param_gen to ptr addrspace(101)
+  br label %loop
+loop:
+  %v = phi i8 [0, %entry], [%v2, %loop]
+  %load_global = load i8, ptr addrspace(1) %global
+  store i8 %load_global, ptr %gen
+  %load_const = load i8, ptr addrspace(101) %param
+  %v2 = add i8 %v, %load_const
+  %cond = icmp eq i8 %load_const, 0
+  br i1 %cond, label %done, label %loop
+done:
+  ret i8 %v2
+}