[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 ↗

(On Diff #478393)

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 ↗

(On Diff #478393)

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

58 ↗

(On Diff #478393)

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

[davidtgoldblatt]

Per review comments.

[davidtgoldblatt]

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

58 ↗

(On Diff #478393)

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

Spurious newline.

2532

Spurious indent.

2599

Spurious newline

llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp

58 ↗

(On Diff #478393)

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

1 ↗

(On Diff #481492)

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

3 ↗

(On Diff #481492)

Data layout not necessary.

7 ↗

(On Diff #481492)

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

7 ↗

(On Diff #481492)

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

nit: double space

llvm/test/Analysis/BasicAA/separate_storage.ll

1

Please use update_test_checks.py to generate CHECK lines.

[nikic]

llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll

7 ↗

(On Diff #481492)

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/docs/LangRef.rst

 that these arguments must be available before and after (but not
 necessarily during) the execution of the callee.
 
 .. _assume_opbundles:
 
 Assume Operand Bundles
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Operand bundles on an :ref:`llvm.assume <int_assume>` allows representing
-assumptions that a :ref:`parameter attribute <paramattrs>` or a
+assumptions, such as that a :ref:`parameter attribute <paramattrs>` or a
 :ref:`function attribute <fnattrs>` holds for a certain value at a certain
 location. Operand bundles enable assumptions that are either hard or impossible
 to represent as a boolean argument of an :ref:`llvm.assume <int_assume>`.
 
 An assume operand bundle has the form:
 
 ::
 
+      "<tag>"([ <arguments>] ])
+
+In the case of function or parameter attributes, the operand bundle has the
+restricted form:
+
+::
+
       "<tag>"([ <holds for value> [, <attribute argument>] ])
 
 * The tag of the operand bundle is usually the name of attribute that can be
   assumed to hold. It can also be `ignore`, this tag doesn't contain any
   information and should be ignored.
 * The first argument if present is the value for which the attribute hold.
 * The second argument if present is an argument of the attribute.
 
 If there are no arguments the attribute is a property of the call location.
 

 
 If the operand bundle value violates any requirements on the attribute value,
 the behavior is undefined, unless one of the following exceptions applies:
 
 * ``"align"`` operand bundles may specify a non-power-of-two alignment
   (including a zero alignment). If this is the case, then the pointer value
   must be a null pointer, otherwise the behavior is undefined.
 
+In addition to allowing operand bundles encoding function and parameter
+attributes, an assume operand bundle my also encode a ``separate_storage``
+operand bundle. This has the form:
+
+.. code-block:: llvm
+
+    separate_storage(<val1>, <val2>)``
+
+This indicates that  no pointer :ref:`based <pointeraliasing>` on one of its
+arguments can alias any pointer based on the other.
+
 Even if the assumed property can be encoded as a boolean value, like
 ``nonnull``, using operand bundles to express the property can still have
 benefits:
 
 * Attributes that can be expressed via operand bundles are directly the
   property that the optimizer uses and cares about. Encoding attributes as
   operand bundles removes the need for an instruction sequence that represents
   the property (e.g., `icmp ne ptr %p, null` for `nonnull`) and for the
   optimizer to deduce the property from that instruction sequence.
 * Expressing the property using operand bundles makes it easy to identify the
   use of the value as a use in an :ref:`llvm.assume <int_assume>`. This then
   simplifies and improves heuristics, e.g., for use "use-sensitive"
   optimizations.
 
 .. _ob_preallocated:
 
 Preallocated Operand Bundles
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Preallocated operand bundles are characterized by the ``"preallocated"``
 operand bundle tag.  These operand bundles allow separation of the allocation
 of the call argument memory from the call site.  This is necessary to pass
 non-trivially copyable objects by value in a way that is compatible with MSVC

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
 
   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
                        const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
 
   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
                           const Value *V2, LocationSize V2Size,
                           AAQueryInfo &AAQI);
 
-  AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
-                         const Value *V2, LocationSize V2Size,
-                         AAQueryInfo &AAQI);
+  AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
+                         LocationSize V2Size, AAQueryInfo &AAQI,
+                         const Instruction *CtxI);
 
   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
                                   const Value *V2, LocationSize V2Size,
                                   AAQueryInfo &AAQI, const Value *O1,
                                   const Value *O2);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
 
 /// Enable analysis of recursive PHI nodes.
 static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden,
                                           cl::init(true));
 
+static cl::opt<bool> EnableSeparateStorageAnalysis("basic-aa-separate-storage",
+                                                   cl::Hidden, cl::init(false));
+
 /// SearchLimitReached / SearchTimes shows how often the limit of
 /// to decompose GEPs is reached. It will affect the precision
 /// of basic alias analysis.
 STATISTIC(SearchLimitReached, "Number of times the limit to "
                               "decompose GEPs is reached");
 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
 
 // The max limit of the search depth in DecomposeGEPExpression() and
static bool notDifferentParent(const Value *O1, const Value *O2) {
   const Function *F2 = getParent(O2);
 
   return !F1 || !F2 || F1 == F2;
 }
 #endif
 
 AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
                                  const MemoryLocation &LocB, AAQueryInfo &AAQI,
-                                 const Instruction *) {
+                                 const Instruction *CtxI) {
   assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
          "BasicAliasAnalysis doesn't support interprocedural queries.");
-  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI);
+  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI, CtxI);
 }
 
 /// 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.
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
 
   return Alias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
 AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                       const Value *V2, LocationSize V2Size,
-                                      AAQueryInfo &AAQI) {
+                                      AAQueryInfo &AAQI,
+                                      const Instruction *CtxI) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size.isZero() || V2Size.isZero())
     return AliasResult::NoAlias;
 
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCastsForAliasAnalysis();
   V2 = V2->stripPointerCastsForAliasAnalysis();
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   if ((isObjectSmallerThan(
           O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
           TLI, NullIsValidLocation)) ||
       (isObjectSmallerThan(
           O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL,
           TLI, NullIsValidLocation)))
     return AliasResult::NoAlias;
 
+  if (CtxI && EnableSeparateStorageAnalysis) {
+    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 *Hint1 = OBU.Inputs[0].get();
+          const Value *Hint2 = OBU.Inputs[1].get();
+          const Value *HintO1 = getUnderlyingObject(Hint1);
+          const Value *HintO2 = getUnderlyingObject(Hint2);
+
+          if (((O1 == HintO1 && O2 == HintO2) ||
+               (O1 == HintO2 && O2 == HintO1)) &&
+              isValidAssumeForContext(Assume, CtxI, DT))
+            return AliasResult::NoAlias;
+        }
+      }
+    }
+  }
+
   // If one the accesses may be before the accessed pointer, canonicalize this
   // by using unknown after-pointer sizes for both accesses. This is
   // equivalent, because regardless of which pointer is lower, one of them
   // will always came after the other, as long as the underlying objects aren't
   // disjoint. We do this so that the rest of BasicAA does not have to deal
   // with accesses before the base pointer, and to improve cache utilization by
   // merging equivalent states.
   if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) {

llvm/lib/IR/Verifier.cpp

if (auto *Const = dyn_cast<Constant>(V))
             "const x86_amx is not allowed in argument!");
   }
 
   switch (ID) {
   default:
     break;
   case Intrinsic::assume: {
     for (auto &Elem : Call.bundle_op_infos()) {
+      unsigned ArgCount = Elem.End - Elem.Begin;
+      // Separate storage assumptions are special insofar as they're the only
+      // operand bundles allowed on assumes that aren't parameter attributes.
+      if (Elem.Tag->getKey() == "separate_storage") {
+        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(Elem.Tag->getKey() == "ignore" ||
                 Attribute::isExistingAttribute(Elem.Tag->getKey()),
             "tags must be valid attribute names", Call);
       Attribute::AttrKind Kind =
           Attribute::getAttrKindFromName(Elem.Tag->getKey());
-      unsigned ArgCount = Elem.End - Elem.Begin;
       if (Kind == Attribute::Alignment) {
         Check(ArgCount <= 3 && ArgCount >= 2,
               "alignment assumptions should have 2 or 3 arguments", Call);
         Check(Call.getOperand(Elem.Begin)->getType()->isPointerTy(),
               "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)

llvm/test/Analysis/BasicAA/separate_storage.ll

+; RUN: opt < %s -passes='gvn' -basic-aa-separate-storage -S | FileCheck %s
+
+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/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
 }