diff --git a/llvm/docs/LangRef.rst b/llvm/docs/LangRef.rst --- a/llvm/docs/LangRef.rst +++ b/llvm/docs/LangRef.rst @@ -2512,13 +2512,20 @@ ^^^^^^^^^^^^^^^^^^^^^^ Operand bundles on an :ref:`llvm.assume ` allows representing -assumptions that a :ref:`parameter attribute ` or a +assumptions, such as that a :ref:`parameter attribute ` or a :ref:`function attribute ` 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 `. An assume operand bundle has the form: +:: + + ""([ ] ]) + +In the case of function or parameter attributes, the operand bundle has the +restricted form: + :: ""([ [, ] ]) @@ -2564,6 +2571,17 @@ (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(, )`` + +This indicates that no pointer :ref:`based ` 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: diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h --- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h @@ -134,9 +134,9 @@ 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, diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -68,6 +68,9 @@ static cl::opt EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, cl::init(true)); +static cl::opt 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. @@ -824,10 +827,10 @@ 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 @@ -1415,7 +1418,8 @@ /// 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()) @@ -1499,6 +1503,31 @@ TLI, NullIsValidLocation))) return AliasResult::NoAlias; + if (CtxI && EnableSeparateStorageAnalysis) { + for (auto &AssumeVH : AC.assumptions()) { + if (!AssumeVH) + continue; + + AssumeInst *Assume = cast(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 diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp --- a/llvm/lib/IR/Verifier.cpp +++ b/llvm/lib/IR/Verifier.cpp @@ -4963,12 +4963,23 @@ 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); diff --git a/llvm/test/Analysis/BasicAA/separate_storage.ll b/llvm/test/Analysis/BasicAA/separate_storage.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/BasicAA/separate_storage.ll @@ -0,0 +1,179 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes='gvn' -basic-aa-separate-storage -S | FileCheck %s + +declare void @llvm.assume(i1) + +; Test basic queries. + +define i8 @simple_no(ptr %p1, ptr %p2) { +; CHECK-LABEL: @simple_no( +; CHECK-NEXT: entry: +; CHECK-NEXT: store i8 0, ptr [[P1:%.*]], align 1 +; CHECK-NEXT: store i8 1, ptr [[P2:%.*]], align 1 +; CHECK-NEXT: [[LOADOFSTORE:%.*]] = load i8, ptr [[P1]], align 1 +; CHECK-NEXT: ret i8 [[LOADOFSTORE]] +; +entry: + store i8 0, ptr %p1 + store i8 1, ptr %p2 + %loadofstore = load i8, ptr %p1 + ret i8 %loadofstore +} + +define i8 @simple_yes(ptr %p1, ptr %p2) { +; CHECK-LABEL: @simple_yes( +; CHECK-NEXT: entry: +; CHECK-NEXT: call void @llvm.assume(i1 true) [ "separate_storage"(ptr [[P1:%.*]], ptr [[P2:%.*]]) ] +; CHECK-NEXT: store i8 0, ptr [[P1]], align 1 +; CHECK-NEXT: store i8 1, ptr [[P2]], align 1 +; CHECK-NEXT: ret i8 0 +; +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 +} + +define i8 @ptr_to_ptr_no(ptr %pp) { +; CHECK-LABEL: @ptr_to_ptr_no( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[P_BASE:%.*]] = load ptr, ptr [[PP:%.*]], align 8 +; CHECK-NEXT: store i8 0, ptr [[P_BASE]], align 1 +; CHECK-NEXT: [[P_BASE2:%.*]] = load ptr, ptr [[PP]], align 8 +; CHECK-NEXT: [[LOADOFSTORE:%.*]] = load i8, ptr [[P_BASE2]], align 1 +; CHECK-NEXT: ret i8 [[LOADOFSTORE]] +; +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 +} + +define i8 @ptr_to_ptr_yes(ptr %pp) { +; CHECK-LABEL: @ptr_to_ptr_yes( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[P_BASE:%.*]] = load ptr, ptr [[PP:%.*]], align 8 +; CHECK-NEXT: call void @llvm.assume(i1 true) [ "separate_storage"(ptr [[P_BASE]], ptr [[PP]]) ] +; CHECK-NEXT: store i8 0, ptr [[P_BASE]], align 1 +; CHECK-NEXT: ret i8 0 +; +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. + +define i8 @flow_sensitive(ptr %p1, ptr %p2, i1 %cond) { +; CHECK-LABEL: @flow_sensitive( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[COND:%.*]], label [[TRUE_BRANCH:%.*]], label [[FALSE_BRANCH:%.*]] +; CHECK: true_branch: +; CHECK-NEXT: store i8 11, ptr [[P1:%.*]], align 1 +; CHECK-NEXT: store i8 22, ptr [[P2:%.*]], align 1 +; CHECK-NEXT: [[LOADOFSTORE_TRUE:%.*]] = load i8, ptr [[P1]], align 1 +; CHECK-NEXT: br label [[ENDIF:%.*]] +; CHECK: false_branch: +; CHECK-NEXT: call void @llvm.assume(i1 true) [ "separate_storage"(ptr [[P1]], ptr [[P2]]) ] +; CHECK-NEXT: store i8 33, ptr [[P1]], align 1 +; CHECK-NEXT: store i8 44, ptr [[P2]], align 1 +; CHECK-NEXT: br label [[ENDIF]] +; CHECK: endif: +; CHECK-NEXT: [[LOADOFSTORE:%.*]] = phi i8 [ [[LOADOFSTORE_TRUE]], [[TRUE_BRANCH]] ], [ 33, [[FALSE_BRANCH]] ] +; CHECK-NEXT: ret i8 [[LOADOFSTORE]] +; +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 +} + +define i8 @flow_sensitive_with_dominator(ptr %p1, ptr %p2, i1 %cond) { +; CHECK-LABEL: @flow_sensitive_with_dominator( +; CHECK-NEXT: entry: +; CHECK-NEXT: call void @llvm.assume(i1 true) [ "separate_storage"(ptr [[P1:%.*]], ptr [[P2:%.*]]) ] +; CHECK-NEXT: br i1 [[COND:%.*]], label [[TRUE_BRANCH:%.*]], label [[FALSE_BRANCH:%.*]] +; CHECK: true_branch: +; CHECK-NEXT: store i8 11, ptr [[P1]], align 1 +; CHECK-NEXT: store i8 22, ptr [[P2]], align 1 +; CHECK-NEXT: br label [[ENDIF:%.*]] +; CHECK: false_branch: +; CHECK-NEXT: store i8 33, ptr [[P1]], align 1 +; CHECK-NEXT: store i8 44, ptr [[P2]], align 1 +; CHECK-NEXT: br label [[ENDIF]] +; CHECK: endif: +; CHECK-NEXT: [[LOADOFSTORE:%.*]] = phi i8 [ 11, [[TRUE_BRANCH]] ], [ 33, [[FALSE_BRANCH]] ] +; CHECK-NEXT: ret i8 [[LOADOFSTORE]] +; +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. + +define i8 @offset_agnostic(ptr %p1, ptr %p2) { +; CHECK-LABEL: @offset_agnostic( +; CHECK-NEXT: [[ACCESS1:%.*]] = getelementptr inbounds i8, ptr [[P1:%.*]], i64 12 +; CHECK-NEXT: [[ACCESS2:%.*]] = getelementptr inbounds i8, ptr [[P2:%.*]], i64 34 +; CHECK-NEXT: [[HINT1:%.*]] = getelementptr inbounds i8, ptr [[P1]], i64 56 +; CHECK-NEXT: [[HINT2:%.*]] = getelementptr inbounds i8, ptr [[P2]], i64 78 +; CHECK-NEXT: call void @llvm.assume(i1 true) [ "separate_storage"(ptr [[HINT1]], ptr [[HINT2]]) ] +; CHECK-NEXT: store i8 0, ptr [[ACCESS1]], align 1 +; CHECK-NEXT: store i8 1, ptr [[ACCESS2]], align 1 +; CHECK-NEXT: ret i8 0 +; + %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 +} diff --git a/llvm/test/Verifier/assume-bundles.ll b/llvm/test/Verifier/assume-bundles.ll --- a/llvm/test/Verifier/assume-bundles.ll +++ b/llvm/test/Verifier/assume-bundles.ll @@ -24,5 +24,9 @@ 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 }