[AA][Intrinsics] Add separate_storage assumptions.

[davidtgoldblatt]

Summary

This operand bundle on an assume informs alias analysis that the
arguments point to regions of memory that were allocated separately
(i.e. different heap allocations, different allocas, or different
globals).

As a safety measure, we leave the analysis flag-disabled by default.

[davidtgoldblatt]

Updating per review comments.

[lebedev.ri]

Missing langref changes.

[davidtgoldblatt]

Add langref change for separate_storage attribute.

[nikic]

llvm/include/llvm/IR/Attributes.td

183

It doesn't make sense to add an actual attribute for this. This would allow you to write something like define foo(ptr separate_storage %arg), and what is that supposed to mean?

We should allow separate_storage as an assume operand bundled only -- there's not fundamental reason why these bundled have to map onto attributes. That's just all we needed historically.

[nikic]

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

53

I don't think Loc without pointer is legal in this context. Should be fine to drop this check.

58

Hm, I wonder if we can use assumptionsFor() here?

[davidtgoldblatt]

Per review comments.

[davidtgoldblatt]

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

58

I think eventually we should be able to, but there's two things that make this tricky:

• I think the AssumptionCache assumes that the only value that matters for assumptionsFor is the first one (because of the param attribute background?), which would introduce a weird asymmetry in how we can use it.
• We care about the comparison after a getUnderlyingObject call, but the AssumptionCache doesn't trace through GEPs in findAffectedValues.

(plausibly other issues; I checked that naive attempts at assumptionsFor didn't work, but didn't dig as much into the why).

I think the right thing to do eventually is to rewrite the hints during InstCombine (which should fix issue 2 as well as just speeding things up), but figured it didn't make sense to add extra complication to the AssumptionCache to fix 1 until that was done.

[davidtgoldblatt]

Fix the LangRef changes -- left some junk lying around.

[nikic]

This looks basically fine to me. My one remaining concern here is compile-time impact. Adding a new SeparateStorageAliasAnalysis pass does add some overhead even if these assumptions are not used (the last two patches add about 0.2% overhead). I think we might be better off just folding this code into BasicAA at an appropriate place, which also saves a good bit of boilerplate.

llvm/docs/LangRef.rst

2514 ↗

(On Diff #481492)

Spurious newline.

2534 ↗

(On Diff #481492)

Spurious indent.

2602 ↗

(On Diff #481492)

Spurious newline

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

58

My thinking was that we add the underlying object as the affected value in the assumption cache, but your suggestion to strip that away in InstCombine does sound better.

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

2

I don't think you need to specify aa-pipeline here, it's in the default pipeline.

4

Data layout not necessary.

8

It would be preferable to make this an aa-eval test, to test AA directly, rather than a pass using it.

[davidtgoldblatt]

Movie logic into BasicAA.

[davidtgoldblatt]

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

8

This is a little hard in the aa-eval of today because of the flow-sensitivity; it can't just print out yes/no/maybe results for all pairs of pointers; it would have to do so out all program locations too. TBAA has a similar sort of issue, uses the same "use gvn to check effects rather than results" trick to get around it too.

The only aa-eval improvements I could think of were:

• Do the cubic-size "print AA result for every pair of pointers at every program location" output under a flag
• Have some sort of magic "print aa-eval results at this location" function

Both of which seemed like overkill, although I suppose the first is manageable so long as we make sure to keep any test cases sufficiently compact. WDYT?

[nikic]

LGTM

llvm/docs/LangRef.rst

2582 ↗

(On Diff #481769)

nit: double space

llvm/test/Analysis/BasicAA/separate_storage.ll

1 ↗

(On Diff #481769)

Please use update_test_checks.py to generate CHECK lines.

[nikic]

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

8

We could add a mode to print ModRef results rather than AliasResults (like we do for calls). But I think your current test is fine.

[davidtgoldblatt]

Fix langref nit, use update_test_checks.py.

[davidtgoldblatt]

Rebase, futz with parent diffs in arc for wenlei@.

[fhahn]

What's the plan for flipping the default for EnableSeparateStorageAnalysis?

llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h

 #ifndef LLVM_ANALYSIS_SEPARATESTORAGEALIASANALYSIS
 #define LLVM_ANALYSIS_SEPARATESTORAGEALIASANALYSIS
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
+class AssumptionCache;
+class DominatorTree;
+
 /// A simple AA result that uses calls to the separate storage intrinsics.
 class SeparateStorageAAResult : public AAResultBase {
 public:
-  bool invalidate(Function &, const PreservedAnalyses &,
-                  FunctionAnalysisManager::Invalidator &) {
-    return false;
-  }
+  SeparateStorageAAResult(AssumptionCache &AC, DominatorTree &DT);
+  bool invalidate(Function &Fn, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
+  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
+                    AAQueryInfo &AAQI, const Instruction *I);
+
+private:
+  AssumptionCache ∾
+  DominatorTree &DT;
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class SeparateStorageAA : public AnalysisInfoMixin<SeparateStorageAA> {
   friend AnalysisInfoMixin<SeparateStorageAA>;
 
   static AnalysisKey Key;
 

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum AttributeKindCodes {
   ATTR_KIND_NO_SANITIZE_BOUNDS = 79,
   ATTR_KIND_ALLOC_ALIGN = 80,
   ATTR_KIND_ALLOCATED_POINTER = 81,
   ATTR_KIND_ALLOC_KIND = 82,
   ATTR_KIND_PRESPLIT_COROUTINE = 83,
   ATTR_KIND_FNRETTHUNK_EXTERN = 84,
   ATTR_KIND_SKIP_PROFILE = 85,
   ATTR_KIND_MEMORY = 86,
+  ATTR_KIND_SEPARATE_STORAGE = 87,
 };
 
 enum ComdatSelectionKindCodes {
   COMDAT_SELECTION_KIND_ANY = 1,
   COMDAT_SELECTION_KIND_EXACT_MATCH = 2,
   COMDAT_SELECTION_KIND_LARGEST = 3,
   COMDAT_SELECTION_KIND_NO_DUPLICATES = 4,
   COMDAT_SELECTION_KIND_SAME_SIZE = 5,

llvm/include/llvm/IR/Attributes.td

 def NoSync : EnumAttr<"nosync", [FnAttr]>;
 
 /// Disable Indirect Branch Tracking.
 def NoCfCheck : EnumAttr<"nocf_check", [FnAttr]>;
 
 /// Function should not be instrumented.
 def NoProfile : EnumAttr<"noprofile", [FnAttr]>;
 
+/// As an operand bundle on an assume intrinsic, Indicates that its two pointer
+/// operands do not alias.
+def SeparateStorage : EnumAttr<"separate_storage", [ParamAttr]>;
+
 /// This function should not be instrumented but it is ok to inline profiled
 // functions into it.
 def SkipProfile : EnumAttr<"skipprofile", [FnAttr]>;
 
 /// Function doesn't unwind stack.
 def NoUnwind : EnumAttr<"nounwind", [FnAttr]>;
 
 /// No SanitizeBounds instrumentation.

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

 //===- SeparateStorageAliasAnalysis.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
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements the separate storage alias analysis pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/SeparateStorageAliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
+static cl::opt<bool> EnableSeparateStorageAA("enable-separate-storage-aa",
+                                             cl::Hidden, cl::init(false));
+
 AnalysisKey SeparateStorageAA::Key;
 
+SeparateStorageAAResult::SeparateStorageAAResult(AssumptionCache &AC,
+                                                 DominatorTree &DT)
+    : AC(AC), DT(DT) {}
+
+bool SeparateStorageAAResult::invalidate(
+    Function &Fn, const PreservedAnalyses &PA,
+    FunctionAnalysisManager::Invalidator &Inv) {
+  return Inv.invalidate<AssumptionAnalysis>(Fn, PA) ||
+         Inv.invalidate<DominatorTreeAnalysis>(Fn, PA);
+}
+
+AliasResult SeparateStorageAAResult::alias(const MemoryLocation &LocA,
+                                           const MemoryLocation &LocB,
+                                           AAQueryInfo &AAQI,
+                                           const Instruction *I) {
+  if (!EnableSeparateStorageAA)
+    return AliasResult::MayAlias;
+
+  if (!I)
+    return AliasResult::MayAlias;
+
+  const Value *PtrA = LocA.Ptr;
+  const Value *PtrB = LocB.Ptr;
+  if (!PtrA || !PtrB)
+    return AliasResult::MayAlias;
+
+  const Value *UnderlyingA = getUnderlyingObject(PtrA);
+  const Value *UnderlyingB = getUnderlyingObject(PtrB);
+
+  for (auto &AssumeVH : AC.assumptions()) {
+    if (!AssumeVH)
+      continue;
+
+    AssumeInst *Assume = cast<AssumeInst>(AssumeVH);
+
+    for (unsigned Idx = 0; Idx < Assume->getNumOperandBundles(); Idx++) {
+      OperandBundleUse OBU = Assume->getOperandBundleAt(Idx);
+      if (OBU.getTagName() == "separate_storage") {
+        assert(OBU.Inputs.size() == 2);
+        const Value *HintA = OBU.Inputs[0].get();
+        const Value *HintB = OBU.Inputs[1].get();
+        const Value *UnderlyingHintA = getUnderlyingObject(HintA);
+        const Value *UnderlyingHintB = getUnderlyingObject(HintB);
+
+        if (((UnderlyingA == UnderlyingHintA &&
+              UnderlyingB == UnderlyingHintB) ||
+             (UnderlyingA == UnderlyingHintB &&
+              UnderlyingB == UnderlyingHintA)) &&
+            isValidAssumeForContext(Assume, I, &DT))
+          return AliasResult::NoAlias;
+        break;
+      }
+    }
+  }
+  return AliasResult::MayAlias;
+}
+
 SeparateStorageAAResult SeparateStorageAA::run(Function &F,
                                                FunctionAnalysisManager &AM) {
-  return SeparateStorageAAResult();
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  return SeparateStorageAAResult(AC, DT);
 }
 
 char SeparateStorageAAWrapperPass::ID = 0;
 INITIALIZE_PASS(SeparateStorageAAWrapperPass, "separatestorage-aa",
                 "Separate Storage Alias Analysis", false, true)
 
 FunctionPass *llvm::createSeparateStorageAAWrapperPass() {
   return new SeparateStorageAAWrapperPass();
 }
 
 SeparateStorageAAWrapperPass::SeparateStorageAAWrapperPass()
     : FunctionPass(ID) {
   initializeSeparateStorageAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 bool SeparateStorageAAWrapperPass::runOnFunction(Function &F) {
-  Result.reset(new SeparateStorageAAResult());
+  auto &ACT = getAnalysis<AssumptionCacheTracker>();
+  auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
+
+  Result.reset(new SeparateStorageAAResult(ACT.getAssumptionCache(F),
+                                           DTWP.getDomTree()));
   return false;
 }
 
 void SeparateStorageAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
+  AU.addRequiredTransitive<AssumptionCacheTracker>();
+  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
 }

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
   case Attribute::ReadNone:
     return bitc::ATTR_KIND_READ_NONE;
   case Attribute::ReadOnly:
     return bitc::ATTR_KIND_READ_ONLY;
   case Attribute::Returned:
     return bitc::ATTR_KIND_RETURNED;
   case Attribute::ReturnsTwice:
     return bitc::ATTR_KIND_RETURNS_TWICE;
+  case Attribute::SeparateStorage:
+    return bitc::ATTR_KIND_SEPARATE_STORAGE;
   case Attribute::SExt:
     return bitc::ATTR_KIND_S_EXT;
   case Attribute::Speculatable:
     return bitc::ATTR_KIND_SPECULATABLE;
   case Attribute::StackAlignment:
     return bitc::ATTR_KIND_STACK_ALIGNMENT;
   case Attribute::StackProtect:
     return bitc::ATTR_KIND_STACK_PROTECT;

llvm/lib/IR/Verifier.cpp

for (auto &Elem : Call.bundle_op_infos()) {
               "first argument should be a pointer", Call);
         Check(Call.getOperand(Elem.Begin + 1)->getType()->isIntegerTy(),
               "second argument should be an integer", Call);
         if (ArgCount == 3)
           Check(Call.getOperand(Elem.Begin + 2)->getType()->isIntegerTy(),
                 "third argument should be an integer if present", Call);
         return;
       }
+      if (Kind == Attribute::SeparateStorage) {
+        Check(ArgCount == 2,
+              "separate_storage assumptions should have 2 arguments", Call);
+        Check(Call.getOperand(Elem.Begin)->getType()->isPointerTy() &&
+                  Call.getOperand(Elem.Begin + 1)->getType()->isPointerTy(),
+              "arguments to separate_storage assumptions should be pointers",
+              Call);
+        return;
+      }
       Check(ArgCount <= 2, "too many arguments", Call);
       if (Kind == Attribute::None)
         break;
       if (Attribute::isIntAttrKind(Kind)) {
         Check(ArgCount == 2, "this attribute should have 2 arguments", Call);
         Check(isa<ConstantInt>(Call.getOperand(Elem.Begin + 1)),
               "the second argument should be a constant integral value", Call);
       } else if (Attribute::canUseAsParamAttr(Kind)) {

llvm/lib/Transforms/Utils/CodeExtractor.cpp

if (Attr.isStringAttribute()) {
       case Attribute::NoAlias:
       case Attribute::NoCapture:
       case Attribute::NoUndef:
       case Attribute::NonNull:
       case Attribute::Preallocated:
       case Attribute::ReadNone:
       case Attribute::ReadOnly:
       case Attribute::Returned:
+      case Attribute::SeparateStorage:
       case Attribute::SExt:
       case Attribute::StructRet:
       case Attribute::SwiftError:
       case Attribute::SwiftSelf:
       case Attribute::SwiftAsync:
       case Attribute::ZExt:
       case Attribute::ImmArg:
       case Attribute::ByRef:

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

+; RUN: opt < %s -aa-pipeline=separatestorage-aa,basic-aa -gvn -enable-separate-storage-aa -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+declare void @llvm.assume(i1)
+
+; Test basic queries.
+
+; CHECK-LAEBL: @simple_no
+; CHECK: ret i8 %loadofstore
+define i8 @simple_no(ptr %p1, ptr %p2) {
+entry:
+  store i8 0, ptr %p1
+  store i8 1, ptr %p2
+  %loadofstore = load i8, ptr %p1
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @simple_yes
+; CHECK: ret i8 0
+define i8 @simple_yes(ptr %p1, ptr %p2) {
+entry:
+  call void @llvm.assume(i1 1) ["separate_storage"(ptr %p1, ptr %p2)]
+  store i8 0, ptr %p1
+  store i8 1, ptr %p2
+  %loadofstore = load i8, ptr %p1
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @ptr_to_ptr_no
+; CHECK: ret i8 %loadofstore
+define i8 @ptr_to_ptr_no(ptr %pp) {
+entry:
+  %p_base = load ptr, ptr %pp
+  store i8 0, ptr %p_base
+  %p_base2 = load ptr, ptr %pp
+  %loadofstore = load i8, ptr %p_base2
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @ptr_to_ptr_yes
+; CHECK: ret i8 0
+define i8 @ptr_to_ptr_yes(ptr %pp) {
+entry:
+  %p_base = load ptr, ptr %pp
+  call void @llvm.assume(i1 1) ["separate_storage"(ptr %p_base, ptr %pp)]
+  store i8 0, ptr %p_base
+  %p_base2 = load ptr, ptr %pp
+  %loadofstore = load i8, ptr %p_base2
+  ret i8 %loadofstore
+}
+
+; The analysis should only kick in if executed (or will be executed) at the
+; given program point.
+
+; CHECK-LABEL: @flow_sensitive
+; CHECK: %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ 33, %false_branch ]
+define i8 @flow_sensitive(ptr %p1, ptr %p2, i1 %cond) {
+entry:
+  br i1 %cond, label %true_branch, label %false_branch
+
+true_branch:
+  store i8 11, ptr %p1
+  store i8 22, ptr %p2
+  %loadofstore_true = load i8, ptr %p1
+  br label %endif
+
+false_branch:
+  call void @llvm.assume(i1 1) ["separate_storage"(ptr %p1, ptr %p2)]
+  store i8 33, ptr %p1
+  store i8 44, ptr %p2
+  %loadofstore_false = load i8, ptr %p1
+  br label %endif
+
+endif:
+  %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ %loadofstore_false, %false_branch ]
+  ret i8 %loadofstore
+}
+
+; CHECK-LABEL: @flow_sensitive_with_dominator
+; CHECK: %loadofstore = phi i8 [ 11, %true_branch ], [ 33, %false_branch ]
+define i8 @flow_sensitive_with_dominator(ptr %p1, ptr %p2, i1 %cond) {
+entry:
+  call void @llvm.assume(i1 1) ["separate_storage"(ptr %p1, ptr %p2)]
+  br i1 %cond, label %true_branch, label %false_branch
+
+true_branch:
+  store i8 11, ptr %p1
+  store i8 22, ptr %p2
+  %loadofstore_true = load i8, ptr %p1
+  br label %endif
+
+false_branch:
+  store i8 33, ptr %p1
+  store i8 44, ptr %p2
+  %loadofstore_false = load i8, ptr %p1
+  br label %endif
+
+endif:
+  %loadofstore = phi i8 [ %loadofstore_true, %true_branch ], [ %loadofstore_false, %false_branch ]
+  ret i8 %loadofstore
+}
+
+; Hints are relative to entire regions of storage, not particular pointers
+; inside them. We should know that the whole ranges are disjoint given hints at
+; offsets.
+
+; CHECK-LABEL: @offset_agnostic
+; CHECK: ret i8 0
+define i8 @offset_agnostic(ptr %p1, ptr %p2) {
+  %access1 = getelementptr inbounds i8, ptr %p1, i64 12
+  %access2 = getelementptr inbounds i8, ptr %p2, i64 34
+
+  %hint1 = getelementptr inbounds i8, ptr %p1, i64 56
+  %hint2 = getelementptr inbounds i8, ptr %p2, i64 78
+  call void @llvm.assume(i1 1) ["separate_storage"(ptr %hint1, ptr %hint2)]
+
+  store i8 0, ptr %access1
+  store i8 1, ptr %access2
+  %loadofstore = load i8, ptr %access1
+  ret i8 %loadofstore
+}

llvm/test/CodeGen/X86/opt-pipeline.ll

 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Pass Configuration
 ; CHECK-NEXT: Machine Module Information
 ; CHECK-NEXT: Target Transform Information
+; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
-; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT: Create Garbage Collector Module Metadata
 ; CHECK-NEXT: Machine Branch Probability Analysis
 ; CHECK-NEXT: Default Regalloc Eviction Advisor
 ; CHECK-NEXT: Default Regalloc Priority Advisor
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Expand large div/rem
 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:       Lower AMX intrinsics
 ; CHECK-NEXT:       Lower AMX type for load/store
 ; CHECK-NEXT:       Module Verifier
-; CHECK-NEXT:       Separate Storage Alias Analysis
 ; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Separate Storage Alias Analysis
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Canonicalize Freeze Instructions in Loops
 ; CHECK-NEXT:         Induction Variable Users
 ; CHECK-NEXT:         Loop Strength Reduction

llvm/test/Verifier/assume-bundles.ll

; CHECK: this attribute should have one argument
   call void @llvm.assume(i1 true) ["noalias"()]
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32 4)]
 ; CHECK: alignment assumptions should have 2 or 3 arguments
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32 4, i32 4)]
 ; CHECK: second argument should be an integer
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32* %P2)]
 ; CHECK: third argument should be an integer if present
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32* %P2)]
+; CHECK: separate_storage assumptions should have 2 arguments
+  call void @llvm.assume(i1 true) ["separate_storage"(i32* %P)]
+; CHECK: arguments to separate_storage assumptions should be pointers
+  call void @llvm.assume(i1 true) ["separate_storage"(i32* %P, i32 123)]
   ret void
 }