Index: llvm/lib/Analysis/StackSafetyAnalysis.cpp =================================================================== --- llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -10,7 +10,6 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/StackSafetyAnalysis.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/InstIterator.h" @@ -21,6 +20,9 @@ #define DEBUG_TYPE "stack-safety" +static cl::opt StackSafetyMaxIterations("stack-safety-max-iterations", + cl::init(20), cl::Hidden); + namespace { /// Rewrite an SCEV expression for a memory access address to an expression that @@ -150,9 +152,14 @@ SmallVector Params; // TODO: describe return value as depending on one or more of its arguments. + // StackSafetyDataFlowAnalysis counter stored here for faster access. + int UpdateCount = 0; + FunctionInfo(const StackSafetyInfo &SSI) : FunctionInfo(*SSI.Info) {} explicit FunctionInfo(const Function *F) : GV(F){}; + // Creates FunctionInfo that forwards all the parameters to the aliasee. + explicit FunctionInfo(const GlobalAlias *A); FunctionInfo(FunctionInfo &&) = default; @@ -163,6 +170,8 @@ StringRef getName() const { return GV->getName(); } void print(raw_ostream &O) const { + // TODO: Consider different printout format after + // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then. O << " @" << getName() << (IsDSOLocal() ? "" : " dso_preemptable") << (IsInterposable() ? " interposable" : "") << "\n"; O << " args uses:\n"; @@ -177,6 +186,18 @@ FunctionInfo(const FunctionInfo &) = default; }; +StackSafetyInfo::FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) { + unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits(); + const GlobalObject *Aliasee = A->getBaseObject(); + const FunctionType *Type = cast(Aliasee->getValueType()); + // 'Forward' all parameters to this alias to the aliasee + for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) { + Params.emplace_back(PointerSize, nullptr); + UseInfo &US = Params.back().Use; + US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0))); + } +} + namespace { class StackSafetyLocalAnalysis { @@ -373,8 +394,172 @@ return StackSafetyInfo(std::move(Info)); } +class StackSafetyDataFlowAnalysis { + using FunctionMap = + std::map; + + FunctionMap Functions; + // Callee-to-Caller multimap. + DenseMap> Callers; + SetVector WorkList; + + unsigned PointerSize = 0; + const ConstantRange UnknownRange; + + ConstantRange getArgumentAccessRange(const GlobalValue *Callee, + unsigned ParamNo) const; + bool updateOneUse(UseInfo &US, bool UpdateToFullSet); + void updateOneNode(const GlobalValue *Callee, + StackSafetyInfo::FunctionInfo &FS); + void updateOneNode(const GlobalValue *Callee) { + updateOneNode(Callee, Functions.find(Callee)->second); + } + void updateAllNodes() { + for (auto &F : Functions) + updateOneNode(F.first, F.second); + } + void runDataFlow(); + void verifyFixedPoint(); + +public: + StackSafetyDataFlowAnalysis( + Module &M, std::function FI); + StackSafetyGlobalInfo run(); +}; + +StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis( + Module &M, std::function FI) + : PointerSize(M.getDataLayout().getPointerSizeInBits()), + UnknownRange(PointerSize, true) { + // Without ThinLTO, run the local analysis for every function in the TU and + // then run the DFA and annotate allocas + for (auto &F : M.functions()) + if (!F.isDeclaration()) + Functions.emplace(&F, FI(F)); + for (auto &A : M.aliases()) + if (isa(A.getBaseObject())) + Functions.emplace(&A, &A); +} + +ConstantRange +StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee, + unsigned ParamNo) const { + auto IT = Functions.find(Callee); + // Unknown callee (outside of LTO domain or an indirect call). + if (IT == Functions.end()) + return UnknownRange; + const StackSafetyInfo::FunctionInfo &FS = IT->second; + // The definition of this symbol may not be the definition in this linkage + // unit. + if (!FS.IsDSOLocal() || FS.IsInterposable()) + return UnknownRange; + if (ParamNo >= FS.Params.size()) // possibly vararg + return UnknownRange; + return FS.Params[ParamNo].Use.Range; +} + +bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US, + bool UpdateToFullSet) { + bool Changed = false; + for (auto &CS : US.Calls) { + assert(!CS.Range.isEmptySet() && + "Param range can't be empty-set, invalid access range"); + + ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo); + CalleeRange = CalleeRange.add(CS.Offset); + if (!US.Range.contains(CalleeRange)) { + Changed = true; + if (UpdateToFullSet) + US.Range = UnknownRange; + else + US.Range = US.Range.unionWith(CalleeRange); + } + } + return Changed; +} + +void StackSafetyDataFlowAnalysis::updateOneNode( + const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) { + bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations; + bool Changed = false; + for (auto &AS : FS.Allocas) + Changed |= updateOneUse(AS.Use, UpdateToFullSet); + for (auto &PS : FS.Params) + Changed |= updateOneUse(PS.Use, UpdateToFullSet); + + if (Changed) { + LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount + << (UpdateToFullSet ? ", full-set" : "") << "] " + << FS.getName() << "\n"); + // Callers of this function may need updating. + for (auto &CallerID : Callers[Callee]) + WorkList.insert(CallerID); + + ++FS.UpdateCount; + } +} + +void StackSafetyDataFlowAnalysis::runDataFlow() { + Callers.clear(); + WorkList.clear(); + + SmallVector Callees; + for (auto &F : Functions) { + Callees.clear(); + StackSafetyInfo::FunctionInfo &FS = F.second; + for (auto &AS : FS.Allocas) + for (auto &CS : AS.Use.Calls) + Callees.push_back(CS.Callee); + for (auto &PS : FS.Params) + for (auto &CS : PS.Use.Calls) + Callees.push_back(CS.Callee); + + llvm::sort(Callees); + Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end()); + + for (auto &Callee : Callees) + Callers[Callee].push_back(F.first); + } + + updateAllNodes(); + + while (!WorkList.empty()) { + const GlobalValue *Callee = WorkList.back(); + WorkList.pop_back(); + updateOneNode(Callee); + } +} + +void StackSafetyDataFlowAnalysis::verifyFixedPoint() { + WorkList.clear(); + updateAllNodes(); + assert(WorkList.empty()); +} + +StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() { + runDataFlow(); + LLVM_DEBUG(verifyFixedPoint()); + + StackSafetyGlobalInfo SSI; + for (auto &F : Functions) + SSI.emplace(F.first, std::move(F.second)); + return SSI; +} + void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) { - O << "Not Implemented\n"; + size_t Count = 0; + for (auto &F : M.functions()) + if (!F.isDeclaration()) { + SSI.find(&F)->second.print(O); + O << "\n"; + ++Count; + } + for (auto &A : M.aliases()) { + SSI.find(&A)->second.print(O); + O << "\n"; + ++Count; + } + assert(Count == SSI.size() && "Unexpected functions in the result"); } } // end anonymous namespace @@ -431,7 +616,14 @@ StackSafetyGlobalInfo StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) { - return {}; + FunctionAnalysisManager &FAM = + AM.getResult(M).getManager(); + + StackSafetyDataFlowAnalysis SSDFA( + M, [&FAM](Function &F) -> const StackSafetyInfo & { + return FAM.getResult(F); + }); + return SSDFA.run(); } PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M, @@ -459,7 +651,14 @@ AU.addRequired(); } -bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { return false; } +bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { + StackSafetyDataFlowAnalysis SSDFA( + M, [this](Function &F) -> const StackSafetyInfo & { + return getAnalysis(F).getResult(); + }); + SSI = SSDFA.run(); + return false; +} static const char LocalPassArg[] = "stack-safety-local"; static const char LocalPassName[] = "Stack Safety Local Analysis"; Index: llvm/test/Analysis/StackSafetyAnalysis/Inputs/ipa-alias.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/StackSafetyAnalysis/Inputs/ipa-alias.ll @@ -0,0 +1,18 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +@InterposableAliasWrite1 = linkonce dso_local alias void(i8*), void(i8*)* @Write1 + +@PreemptableAliasWrite1 = dso_preemptable alias void(i8*), void(i8*)* @Write1 +@AliasToPreemptableAliasWrite1 = dso_local alias void(i8*), void(i8*)* @PreemptableAliasWrite1 + +@AliasWrite1 = dso_local alias void(i8*), void(i8*)* @Write1 + +@BitcastAliasWrite1 = dso_local alias void(i32*), bitcast (void(i8*)* @Write1 to void(i32*)*) +@AliasToBitcastAliasWrite1 = dso_local alias void(i8*), bitcast (void(i32*)* @BitcastAliasWrite1 to void(i8*)*) + +define dso_local void @Write1(i8* %p) { +entry: + store i8 0, i8* %p, align 1 + ret void +} Index: llvm/test/Analysis/StackSafetyAnalysis/Inputs/ipa.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/StackSafetyAnalysis/Inputs/ipa.ll @@ -0,0 +1,118 @@ +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define dso_local void @Write1(i8* %p) { +entry: + store i8 0, i8* %p, align 1 + ret void +} + +define dso_local void @Write4(i8* %p) { +entry: + %0 = bitcast i8* %p to i32* + store i32 0, i32* %0, align 1 + ret void +} + +define dso_local void @Write4_2(i8* %p, i8* %q) { +entry: + %0 = bitcast i8* %p to i32* + store i32 0, i32* %0, align 1 + %1 = bitcast i8* %q to i32* + store i32 0, i32* %1, align 1 + ret void +} + +define dso_local void @Write8(i8* %p) { +entry: + %0 = bitcast i8* %p to i64* + store i64 0, i64* %0, align 1 + ret void +} + +define dso_local i8* @WriteAndReturn8(i8* %p) { +entry: + store i8 0, i8* %p, align 1 + ret i8* %p +} + +declare dso_local void @ExternalCall(i8* %p) + +define dso_preemptable void @PreemptableWrite1(i8* %p) { +entry: + store i8 0, i8* %p, align 1 + ret void +} + +define linkonce dso_local void @InterposableWrite1(i8* %p) { +entry: + store i8 0, i8* %p, align 1 + ret void +} + +define dso_local i8* @ReturnDependent(i8* %p) { +entry: + %p2 = getelementptr i8, i8* %p, i64 2 + ret i8* %p2 +} + +; access range [2, 6) +define dso_local void @Rec0(i8* %p) { +entry: + %p1 = getelementptr i8, i8* %p, i64 2 + call void @Write4(i8* %p1) + ret void +} + +; access range [3, 7) +define dso_local void @Rec1(i8* %p) { +entry: + %p1 = getelementptr i8, i8* %p, i64 1 + call void @Rec0(i8* %p1) + ret void +} + +; access range [-2, 2) +define dso_local void @Rec2(i8* %p) { +entry: + %p1 = getelementptr i8, i8* %p, i64 -5 + call void @Rec1(i8* %p1) + ret void +} + +; Recursive function that passes %acc unchanged => access range [0, 4). +define dso_local void @RecursiveNoOffset(i32* %p, i32 %size, i32* %acc) { +entry: + %cmp = icmp eq i32 %size, 0 + br i1 %cmp, label %return, label %if.end + +if.end: + %0 = load i32, i32* %p, align 4 + %1 = load i32, i32* %acc, align 4 + %add = add nsw i32 %1, %0 + store i32 %add, i32* %acc, align 4 + %add.ptr = getelementptr inbounds i32, i32* %p, i64 1 + %sub = add nsw i32 %size, -1 + tail call void @RecursiveNoOffset(i32* %add.ptr, i32 %sub, i32* %acc) + ret void + +return: + ret void +} + +; Recursive function that advances %acc on each iteration => access range unlimited. +define dso_local void @RecursiveWithOffset(i32 %size, i32* %acc) { +entry: + %cmp = icmp eq i32 %size, 0 + br i1 %cmp, label %return, label %if.end + +if.end: + store i32 0, i32* %acc, align 4 + %acc2 = getelementptr inbounds i32, i32* %acc, i64 1 + %sub = add nsw i32 %size, -1 + tail call void @RecursiveWithOffset(i32 %sub, i32* %acc2) + ret void + +return: + ret void +} Index: llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll @@ -0,0 +1,133 @@ +; Test IPA over a single combined file +; RUN: llvm-as %s -o %t0.bc +; RUN: llvm-as %S/Inputs/ipa-alias.ll -o %t1.bc +; RUN: llvm-link %t0.bc %t1.bc -o %t.combined.bc +; RUN: opt -S -analyze -stack-safety-local %t.combined.bc | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -passes="print" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -analyze -stack-safety %t.combined.bc | FileCheck %s --check-prefixes=CHECK,GLOBAL +; RUN: opt -S -passes="print-stack-safety" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare void @PreemptableAliasWrite1(i8* %p) +declare void @AliasToPreemptableAliasWrite1(i8* %p) + +declare void @InterposableAliasWrite1(i8* %p) +; Aliases to interposable aliases are not allowed + +declare void @AliasWrite1(i8* %p) + +declare void @BitcastAliasWrite1(i32* %p) +declare void @AliasToBitcastAliasWrite1(i8* %p) + +; Call to dso_preemptable alias to a dso_local aliasee +define void @PreemptableAliasCall() { +; CHECK-LABEL: @PreemptableAliasCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x1[1]: empty-set, @PreemptableAliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x1[1]: full-set, @PreemptableAliasWrite1(arg0, [0,1)){{$}} +; LOCAL-NEXT: x2[1]: empty-set, @AliasToPreemptableAliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x2[1]: [0,1), @AliasToPreemptableAliasWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x1 = alloca i8 + call void @PreemptableAliasWrite1(i8* %x1) + + %x2 = alloca i8 +; Alias to a preemptable alias is not preemptable + call void @AliasToPreemptableAliasWrite1(i8* %x2) + ret void +} + +; Call to an interposable alias to a non-interposable aliasee +define void @InterposableAliasCall() { +; CHECK-LABEL: @InterposableAliasCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[1]: empty-set, @InterposableAliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[1]: full-set, @InterposableAliasWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i8 +; ThinLTO can resolve the prevailing implementation for interposable definitions. + call void @InterposableAliasWrite1(i8* %x) + ret void +} + +; Call to a dso_local/non-interposable alias/aliasee +define void @AliasCall() { +; CHECK-LABEL: @AliasCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[1]: empty-set, @AliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[1]: [0,1), @AliasWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i8 + call void @AliasWrite1(i8* %x) + ret void +} + +; Call to a bitcasted dso_local/non-interposable alias/aliasee +define void @BitcastAliasCall() { +; CHECK-LABEL: @BitcastAliasCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x1[4]: empty-set, @BitcastAliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x1[4]: [0,1), @BitcastAliasWrite1(arg0, [0,1)){{$}} +; LOCAL-NEXT: x2[1]: empty-set, @AliasToBitcastAliasWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x2[1]: [0,1), @AliasToBitcastAliasWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x1 = alloca i32 + call void @BitcastAliasWrite1(i32* %x1) + %x2 = alloca i8 + call void @AliasToBitcastAliasWrite1(i8* %x2) + ret void +} + +; The rest is from Inputs/ipa-alias.ll + +; CHECK-LABEL: @Write1{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,1){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; GLOBAL-LABEL: @InterposableAliasWrite1 interposable{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: + +; GLOBAL-LABEL: @PreemptableAliasWrite1 dso_preemptable{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: + +; GLOBAL-LABEL: @AliasToPreemptableAliasWrite1{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: + +; GLOBAL-LABEL: @AliasWrite1{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: + +; GLOBAL-LABEL: @BitcastAliasWrite1{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: + +; GLOBAL-LABEL: @AliasToBitcastAliasWrite1{{$}} +; GLOBAL-NEXT: args uses: +; GLOBAL-NEXT: []: [0,1), @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: allocas uses: +; GLOBAL-NOT: ]: Index: llvm/test/Analysis/StackSafetyAnalysis/ipa.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/StackSafetyAnalysis/ipa.ll @@ -0,0 +1,448 @@ +; RUN: llvm-as %s -o %t0.bc +; RUN: llvm-as %S/Inputs/ipa.ll -o %t1.bc +; RUN: llvm-link -disable-lazy-loading %t0.bc %t1.bc -o %t.combined.bc +; RUN: opt -S -analyze -stack-safety-local %t.combined.bc | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -passes="print" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -analyze -stack-safety %t.combined.bc | FileCheck %s --check-prefixes=CHECK,GLOBAL +; RUN: opt -S -passes="print-stack-safety" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare void @Write1(i8* %p) +declare void @Write4(i8* %p) +declare void @Write4_2(i8* %p, i8* %q) +declare void @Write8(i8* %p) +declare dso_local i8* @WriteAndReturn8(i8* %p) +declare dso_local void @ExternalCall(i8* %p) +declare void @PreemptableWrite1(i8* %p) +declare void @InterposableWrite1(i8* %p) +declare i8* @ReturnDependent(i8* %p) +declare void @Rec2(i8* %p) +declare void @RecursiveNoOffset(i32* %p, i32 %size, i32* %acc) +declare void @RecursiveWithOffset(i32 %size, i32* %acc) + +; Basic out-of-bounds. +define void @f1() { +; CHECK-LABEL: @f1 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @Write8(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: [0,8), @Write8(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @Write8(i8* %x1) + ret void +} + +; Basic in-bounds. +define void @f2() { +; CHECK-LABEL: @f2 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @Write1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: [0,1), @Write1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @Write1(i8* %x1) + ret void +} + +; Another basic in-bounds. +define void @f3() { +; CHECK-LABEL: @f3 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @Write4(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: [0,4), @Write4(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @Write4(i8* %x1) + ret void +} + +; In-bounds with offset. +define void @f4() { +; CHECK-LABEL: @f4 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @Write1(arg0, [1,2)){{$}} +; GLOBAL-NEXT: x[4]: [1,2), @Write1(arg0, [1,2)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 1 + call void @Write1(i8* %x2) + ret void +} + +; Out-of-bounds with offset. +define void @f5() { +; CHECK-LABEL: @f5 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: empty-set, @Write4(arg0, [1,2)){{$}} +; GLOBAL-NEXT: [1,5), @Write4(arg0, [1,2)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 1 + call void @Write4(i8* %x2) + ret void +} + +; External call. +define void @f6() { +; CHECK-LABEL: @f6 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @ExternalCall(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: full-set, @ExternalCall(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @ExternalCall(i8* %x1) + ret void +} + +; Call to dso_preemptable function +define void @PreemptableCall() { +; CHECK-LABEL: @PreemptableCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @PreemptableWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: full-set, @PreemptableWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @PreemptableWrite1(i8* %x1) + ret void +} + +; Call to function with interposable linkage +define void @InterposableCall() { +; CHECK-LABEL: @InterposableCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @InterposableWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: full-set, @InterposableWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @InterposableWrite1(i8* %x1) + ret void +} + +; Call to function with private linkage +define void @PrivateCall() { +; CHECK-LABEL: @PrivateCall dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @PrivateWrite1(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: [0,1), @PrivateWrite1(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + call void @PrivateWrite1(i8* %x1) + ret void +} + +define private void @PrivateWrite1(i8* %p) { +; CHECK-LABEL: @PrivateWrite1{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,1){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: +entry: + store i8 0, i8* %p, align 1 + ret void +} + +; Caller returns a dependent value. +; FIXME: alloca considered unsafe even if the return value is unused. +define void @f7() { +; CHECK-LABEL: @f7 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[4]: empty-set, @ReturnDependent(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[4]: full-set, @ReturnDependent(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i32, align 4 + %x1 = bitcast i32* %x to i8* + %x2 = call i8* @ReturnDependent(i8* %x1) + ret void +} + +define void @f8left() { +; CHECK-LABEL: @f8left dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [2,3)){{$}} +; GLOBAL-NEXT: x[8]: [0,4), @Rec2(arg0, [2,3)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 2 +; 2 + [-2, 2) = [0, 4) => OK + call void @Rec2(i8* %x2) + ret void +} + +define void @f8right() { +; CHECK-LABEL: @f8right dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [6,7)){{$}} +; GLOBAL-NEXT: x[8]: [4,8), @Rec2(arg0, [6,7)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 6 +; 6 + [-2, 2) = [4, 8) => OK + call void @Rec2(i8* %x2) + ret void +} + +define void @f8oobleft() { +; CHECK-LABEL: @f8oobleft dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [1,2)){{$}} +; GLOBAL-NEXT: x[8]: [-1,3), @Rec2(arg0, [1,2)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 1 +; 1 + [-2, 2) = [-1, 3) => NOT OK + call void @Rec2(i8* %x2) + ret void +} + +define void @f8oobright() { +; CHECK-LABEL: @f8oobright dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [7,8)){{$}} +; GLOBAL-NEXT: x[8]: [5,9), @Rec2(arg0, [7,8)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 7 +; 7 + [-2, 2) = [5, 9) => NOT OK + call void @Rec2(i8* %x2) + ret void +} + +define void @TwoArguments() { +; CHECK-LABEL: @TwoArguments dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [0,1)), @Write4_2(arg0, [4,5)){{$}} +; GLOBAL-NEXT: x[8]: [0,8), @Write4_2(arg1, [0,1)), @Write4_2(arg0, [4,5)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 4 + call void @Write4_2(i8* %x2, i8* %x1) + ret void +} + +define void @TwoArgumentsOOBOne() { +; CHECK-LABEL: @TwoArgumentsOOBOne dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [0,1)), @Write4_2(arg0, [5,6)){{$}} +; GLOBAL-NEXT: x[8]: [0,9), @Write4_2(arg1, [0,1)), @Write4_2(arg0, [5,6)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x1 = bitcast i64* %x to i8* + %x2 = getelementptr i8, i8* %x1, i64 5 + call void @Write4_2(i8* %x2, i8* %x1) + ret void +} + +define void @TwoArgumentsOOBOther() { +; CHECK-LABEL: @TwoArgumentsOOBOther dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [4,5)){{$}} +; GLOBAL-NEXT: x[8]: [-1,8), @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [4,5)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x0 = bitcast i64* %x to i8* + %x1 = getelementptr i8, i8* %x0, i64 -1 + %x2 = getelementptr i8, i8* %x0, i64 4 + call void @Write4_2(i8* %x2, i8* %x1) + ret void +} + +define void @TwoArgumentsOOBBoth() { +; CHECK-LABEL: @TwoArgumentsOOBBoth dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [5,6)){{$}} +; GLOBAL-NEXT: x[8]: [-1,9), @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [5,6)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i64, align 4 + %x0 = bitcast i64* %x to i8* + %x1 = getelementptr i8, i8* %x0, i64 -1 + %x2 = getelementptr i8, i8* %x0, i64 5 + call void @Write4_2(i8* %x2, i8* %x1) + ret void +} + +define i32 @TestRecursiveNoOffset(i32* %p, i32 %size) { +; CHECK-LABEL: @TestRecursiveNoOffset dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: p[]: empty-set, @RecursiveNoOffset(arg0, [0,1)){{$}} +; GLOBAL-NEXT: p[]: full-set, @RecursiveNoOffset(arg0, [0,1)){{$}} +; CHECK-NEXT: size[]: empty-set, @RecursiveNoOffset(arg1, [0,1)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NEXT: sum[4]: [0,4), @RecursiveNoOffset(arg2, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %sum = alloca i32, align 4 + %0 = bitcast i32* %sum to i8* + store i32 0, i32* %sum, align 4 + call void @RecursiveNoOffset(i32* %p, i32 %size, i32* %sum) + %1 = load i32, i32* %sum, align 4 + ret i32 %1 +} + +define void @TestRecursiveWithOffset(i32 %size) { +; CHECK-LABEL: @TestRecursiveWithOffset dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: size[]: empty-set, @RecursiveWithOffset(arg0, [0,1)){{$}} +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: sum[64]: empty-set, @RecursiveWithOffset(arg1, [0,1)){{$}} +; GLOBAL-NEXT: sum[64]: full-set, @RecursiveWithOffset(arg1, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %sum = alloca i32, i64 16, align 4 + call void @RecursiveWithOffset(i32 %size, i32* %sum) + ret void +} + +; FIXME: IPA should detect that access is safe +define void @TestUpdateArg() { +; CHECK-LABEL: @TestUpdateArg dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[16]: empty-set, @WriteAndReturn8(arg0, [0,1)){{$}} +; GLOBAL-NEXT: x[16]: full-set, @WriteAndReturn8(arg0, [0,1)){{$}} +; CHECK-NOT: ]: +entry: + %x = alloca i8, i64 16, align 4 + %0 = call i8* @WriteAndReturn8(i8* %x) + ret void +} + +; The rest is from Inputs/ipa.ll + +; CHECK-LABEL: @Write1{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,1){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Write4{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,4){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Write4_2{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,4){{$}} +; CHECK-NEXT: q[]: [0,4){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Write8{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,8){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @WriteAndReturn8{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: full-set{{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @PreemptableWrite1 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,1){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @InterposableWrite1 interposable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: [0,1){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @ReturnDependent{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: p[]: full-set{{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Rec0{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: p[]: empty-set, @Write4(arg0, [2,3)){{$}} +; GLOBAL-NEXT: p[]: [2,6), @Write4(arg0, [2,3)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Rec1{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: p[]: empty-set, @Rec0(arg0, [1,2)){{$}} +; GLOBAL-NEXT: p[]: [3,7), @Rec0(arg0, [1,2)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @Rec2{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: p[]: empty-set, @Rec1(arg0, [-5,-4)){{$}} +; GLOBAL-NEXT: p[]: [-2,2), @Rec1(arg0, [-5,-4)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @RecursiveNoOffset{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: p[]: [0,4), @RecursiveNoOffset(arg0, [4,5)){{$}} +; GLOBAL-NEXT: p[]: full-set, @RecursiveNoOffset(arg0, [4,5)){{$}} +; CHECK-NEXT: size[]: empty-set, @RecursiveNoOffset(arg1, [4294967295,4294967296)){{$}} +; CHECK-NEXT: acc[]: [0,4), @RecursiveNoOffset(arg2, [0,1)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + +; CHECK-LABEL: @RecursiveWithOffset{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: size[]: empty-set, @RecursiveWithOffset(arg0, [4294967295,4294967296)){{$}} +; LOCAL-NEXT: acc[]: [0,4), @RecursiveWithOffset(arg1, [4,5)){{$}} +; GLOBAL-NEXT: acc[]: full-set, @RecursiveWithOffset(arg1, [4,5)){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: Index: llvm/test/Analysis/StackSafetyAnalysis/local.ll =================================================================== --- llvm/test/Analysis/StackSafetyAnalysis/local.ll +++ llvm/test/Analysis/StackSafetyAnalysis/local.ll @@ -1,9 +1,7 @@ -; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s -; RUN: opt -S -passes="print" -disable-output < %s 2>&1 | FileCheck %s -; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefix=GLOBAL -; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=GLOBAL - -; GLOBAL: Not Implemented +; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -passes="print" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefixes=CHECK,GLOBAL +; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @@ -147,7 +145,8 @@ ; CHECK-LABEL: @DirectCall dso_preemptable{{$}} ; CHECK-NEXT: args uses: ; CHECK-NEXT: allocas uses: -; CHECK-NEXT: x[8]: empty-set, @Foo(arg0, [2,3)){{$}} +; LOCAL-NEXT: x[8]: empty-set, @Foo(arg0, [2,3)){{$}} +; GLOBAL-NEXT: x[8]: full-set, @Foo(arg0, [2,3)){{$}} ; CHECK-NOT: ]: entry: %x = alloca i64, align 4 Index: llvm/test/Analysis/StackSafetyAnalysis/memintrin.ll =================================================================== --- llvm/test/Analysis/StackSafetyAnalysis/memintrin.ll +++ llvm/test/Analysis/StackSafetyAnalysis/memintrin.ll @@ -1,5 +1,7 @@ ; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s ; RUN: opt -S -passes="print" -disable-output < %s 2>&1 | FileCheck %s +; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s +; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" Index: llvm/test/Analysis/StackSafetyAnalysis/scev-udiv.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/StackSafetyAnalysis/scev-udiv.ll @@ -0,0 +1,65 @@ +; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -passes="print" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL +; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefixes=CHECK,GLOBAL +; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL + +; Regression test that exercises a case when a AllocaOffsetRewritten SCEV +; could return an empty-set range. This could occur with udiv SCEVs where the +; RHS was re-written to 0. + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare void @ExternalFn(i64) + +define void @Test1() { +; CHECK-LABEL: @Test1 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[1]: empty-set, @Divide1(arg0, full-set){{$}} +; GLOBAL-NEXT: x[1]: full-set, @Divide1(arg0, full-set){{$}} +; CHECK-NOT: ]: + %x = alloca i8 + %int = ptrtoint i8* %x to i64 + call void @Divide1(i64 %int) + ret void +} + +define dso_local void @Divide1(i64 %arg) { +; CHECK-LABEL: @Divide1{{$}} +; CHECK-NEXT: args uses: +; LOCAL-NEXT: arg[]: empty-set, @ExternalFn(arg0, full-set){{$}} +; GLOBAL-NEXT: arg[]: full-set, @ExternalFn(arg0, full-set){{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + %quotient = udiv i64 undef, %arg + call void @ExternalFn(i64 %quotient) + unreachable +} + +define void @Test2(i64 %arg) { +; CHECK-LABEL: @Test2 dso_preemptable{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: arg[]: empty-set{{$}} +; CHECK-NEXT: allocas uses: +; LOCAL-NEXT: x[1]: empty-set, @Divide2(arg0, full-set){{$}} +; GLOBAL-NEXT: x[1]: full-set, @Divide2(arg0, full-set){{$}} +; CHECK-NOT: ]: + %x = alloca i8 + %int = ptrtoint i8* %x to i64 + call void @Divide2(i64 %int) + ret void +} + +define dso_local void @Divide2(i64 %arg) { +; CHECK-LABEL: @Divide2{{$}} +; CHECK-NEXT: args uses: +; CHECK-NEXT: arg[]: full-set{{$}} +; CHECK-NEXT: allocas uses: +; CHECK-NOT: ]: + %x = inttoptr i64 %arg to i8* + %quotient = udiv i64 undef, %arg + %arrayidx = getelementptr i8, i8* %x, i64 %quotient + load i8, i8* %arrayidx + unreachable +}