diff --git a/llvm/docs/LangRef.rst b/llvm/docs/LangRef.rst --- a/llvm/docs/LangRef.rst +++ b/llvm/docs/LangRef.rst @@ -1274,6 +1274,11 @@ function, returning a pointer to allocated storage disjoint from the storage for any other object accessible to the caller. +``separate_storage(, )`` + This attribute, in an :ref:`assume operand bundle `, + indicates that no pointer :ref:`based ` on one of its + arguments can alias any pointer based on the other. + .. _nocapture: ``nocapture`` 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/include/llvm/Bitcode/LLVMBitCodes.h b/llvm/include/llvm/Bitcode/LLVMBitCodes.h --- a/llvm/include/llvm/Bitcode/LLVMBitCodes.h +++ b/llvm/include/llvm/Bitcode/LLVMBitCodes.h @@ -708,6 +708,7 @@ ATTR_KIND_FNRETTHUNK_EXTERN = 84, ATTR_KIND_SKIP_PROFILE = 85, ATTR_KIND_MEMORY = 86, + ATTR_KIND_SEPARATE_STORAGE = 87, }; enum ComdatSelectionKindCodes { diff --git a/llvm/include/llvm/IR/Attributes.td b/llvm/include/llvm/IR/Attributes.td --- a/llvm/include/llvm/IR/Attributes.td +++ b/llvm/include/llvm/IR/Attributes.td @@ -178,6 +178,10 @@ /// 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]>; 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,15 +11,83 @@ //===----------------------------------------------------------------------===// #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 *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(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(F); + auto &DT = AM.getResult(F); + return SeparateStorageAAResult(AC, DT); } char SeparateStorageAAWrapperPass::ID = 0; @@ -36,10 +104,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/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -742,6 +742,8 @@ 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: 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 @@ -4977,6 +4977,15 @@ "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; diff --git a/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/llvm/lib/Transforms/Utils/CodeExtractor.cpp --- a/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -981,6 +981,7 @@ case Attribute::ReadNone: case Attribute::ReadOnly: case Attribute::Returned: + case Attribute::SeparateStorage: case Attribute::SExt: case Attribute::StructRet: case Attribute::SwiftError: 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 @@ -32,8 +32,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 }