diff --git a/llvm/docs/LangRef.rst b/llvm/docs/LangRef.rst --- a/llvm/docs/LangRef.rst +++ b/llvm/docs/LangRef.rst @@ -2511,17 +2511,27 @@ Assume Operand Bundles ^^^^^^^^^^^^^^^^^^^^^^ + 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: + :: ""([ [, ] ]) + * 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 @@ -2564,6 +2574,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: @@ -2578,6 +2599,7 @@ simplifies and improves heuristics, e.g., for use "use-sensitive" optimizations. + .. _ob_preallocated: Preallocated Operand Bundles diff --git a/llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h b/llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h --- a/llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/SeparateStorageAliasAnalysis.h @@ -19,13 +19,21 @@ #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 &AC; + DominatorTree &DT; }; /// Analysis pass providing a never-invalidated alias analysis result. diff --git a/llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp b/llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp --- a/llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp +++ b/llvm/lib/Analysis/SeparateStorageAliasAnalysis.cpp @@ -11,20 +11,88 @@ //===----------------------------------------------------------------------===// #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 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(Fn, PA) || + Inv.invalidate(Fn, PA); +} + +AliasResult SeparateStorageAAResult::alias(const MemoryLocation &LocA, + const MemoryLocation &LocB, + AAQueryInfo &AAQI, + const Instruction *CtxI) { + if (!EnableSeparateStorageAA) + return AliasResult::MayAlias; + + if (!CtxI) + return AliasResult::MayAlias; + + const Value *PtrA = LocA.Ptr; + const Value *PtrB = LocB.Ptr; + + const Value *UnderlyingA = getUnderlyingObject(PtrA); + const Value *UnderlyingB = getUnderlyingObject(PtrB); + + 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 *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, CtxI, &DT)) + return AliasResult::NoAlias; + break; + } + } + } + return AliasResult::MayAlias; +} + SeparateStorageAAResult SeparateStorageAA::run(Function &F, FunctionAnalysisManager &AM) { - return SeparateStorageAAResult(); + auto &AC = AM.getResult(F); + auto &DT = AM.getResult(F); + return SeparateStorageAAResult(AC, DT); } char SeparateStorageAAWrapperPass::ID = 0; INITIALIZE_PASS_BEGIN(SeparateStorageAAWrapperPass, "separatestorage-aa", "Separate Storage Alias Analysis", true, true) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(SeparateStorageAAWrapperPass, "separatestorage-aa", "Separate Storage Alias Analysis", true, true) @@ -38,10 +106,16 @@ } bool SeparateStorageAAWrapperPass::runOnFunction(Function &F) { - Result.reset(new SeparateStorageAAResult()); + auto &ACT = getAnalysis(); + auto &DTWP = getAnalysis(); + + Result.reset(new SeparateStorageAAResult(ACT.getAssumptionCache(F), + DTWP.getDomTree())); return false; } void SeparateStorageAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); } 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/SeparateStorageAliasAnalysis/alias_test.ll b/llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/SeparateStorageAliasAnalysis/alias_test.ll @@ -0,0 +1,122 @@ +; 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 +} diff --git a/llvm/test/CodeGen/RISCV/O3-pipeline.ll b/llvm/test/CodeGen/RISCV/O3-pipeline.ll --- a/llvm/test/CodeGen/RISCV/O3-pipeline.ll +++ b/llvm/test/CodeGen/RISCV/O3-pipeline.ll @@ -12,9 +12,9 @@ ; 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 diff --git a/llvm/test/CodeGen/X86/opt-pipeline.ll b/llvm/test/CodeGen/X86/opt-pipeline.ll --- a/llvm/test/CodeGen/X86/opt-pipeline.ll +++ b/llvm/test/CodeGen/X86/opt-pipeline.ll @@ -16,9 +16,9 @@ ; 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 @@ -33,8 +33,8 @@ ; CHECK-NEXT: Lower AMX intrinsics ; CHECK-NEXT: Lower AMX type for load/store ; CHECK-NEXT: Module Verifier +; CHECK-NEXT: Dominator Tree Construction ; CHECK-NEXT: Separate Storage Alias Analysis -; CHECK-NEXT: Dominator Tree Construction ; CHECK-NEXT: Basic Alias Analysis (stateless AA impl) ; CHECK-NEXT: Natural Loop Information ; CHECK-NEXT: Canonicalize natural loops 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 }