From 892c71a5bb72cfcce1f0e94e3a0fd314d4606977 Mon Sep 17 00:00:00 2001 From: Vitaly Buka Date: Wed, 27 May 2020 22:21:39 -0700 Subject: [PATCH] [StackSafety] Don't run datafow on allocas We need to process only parameters. Allocas access can be calculated afterwards. Also don't create fake function for aliases and just resolve them on initialization. --- llvm/lib/Analysis/StackSafetyAnalysis.cpp | 197 ++++++++++++--------- .../test/Analysis/StackSafetyAnalysis/ipa-alias.ll | 36 ---- 2 files changed, 117 insertions(+), 116 deletions(-) diff --git a/llvm/lib/Analysis/StackSafetyAnalysis.cpp b/llvm/lib/Analysis/StackSafetyAnalysis.cpp index e969639..cdb952b 100644 --- a/llvm/lib/Analysis/StackSafetyAnalysis.cpp +++ b/llvm/lib/Analysis/StackSafetyAnalysis.cpp @@ -137,31 +137,19 @@ ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) { return R; } -/// Describes uses of allocas and parameters inside of a single function. struct FunctionInfo { SmallVector Allocas; SmallVector Params; - const GlobalValue *GV = nullptr; // TODO: describe return value as depending on one or more of its arguments. // StackSafetyDataFlowAnalysis counter stored here for faster access. int UpdateCount = 0; - FunctionInfo() = default; - FunctionInfo(const Function *F) : GV(F){}; - explicit FunctionInfo(const GlobalAlias *A); - - bool IsDSOLocal() const { return GV->isDSOLocal(); }; - - bool IsInterposable() const { return GV->isInterposable(); }; - - StringRef getName() const { return GV->getName(); } - void print(raw_ostream &O, StringRef Name, const Function *F) const { // TODO: Consider different printout format after // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then. - O << " @" << Name << (IsDSOLocal() ? "" : " dso_preemptable") - << (IsInterposable() ? " interposable" : "") << "\n"; + O << " @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable") + << ((F && F->isInterposable()) ? " interposable" : "") << "\n"; O << " args uses:\n"; size_t Pos = 0; @@ -190,18 +178,6 @@ struct FunctionInfo { } }; -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); - UseInfo &US = Params.back(); - US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0))); - } -} - } // namespace struct StackSafetyInfo::InfoTy { @@ -404,7 +380,7 @@ bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr, UseInfo &US) { } FunctionInfo StackSafetyLocalAnalysis::run() { - FunctionInfo Info(&F); + FunctionInfo Info; assert(!F.isDeclaration() && "Can't run StackSafety on a function declaration"); @@ -433,15 +409,13 @@ class StackSafetyDataFlowAnalysis { using FunctionMap = std::map; FunctionMap Functions; + const ConstantRange UnknownRange; + // 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, FunctionInfo &FS); void updateOneNode(const GlobalValue *Callee) { @@ -456,25 +430,24 @@ class StackSafetyDataFlowAnalysis { void verifyFixedPoint(); #endif + uint32_t findPointerWidth() const { + for (auto &F : Functions) + for (auto &P : F.second.Params) + return P.Range.getBitWidth(); + return 1; + } + public: - StackSafetyDataFlowAnalysis( - Module &M, std::function FI); - GVToSSI run(); -}; + explicit StackSafetyDataFlowAnalysis(FunctionMap Functions) + : Functions(std::move(Functions)), + UnknownRange(ConstantRange::getFull(findPointerWidth())) {} -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. - 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, FunctionInfo(&A)); -} + const FunctionMap &run(); + + // FIXME: Accept offset. + ConstantRange getArgumentAccessRange(const GlobalValue *Callee, + unsigned ParamNo) const; +}; ConstantRange StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee, @@ -484,10 +457,6 @@ StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee, if (IT == Functions.end()) return UnknownRange; const 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].Range; @@ -517,8 +486,6 @@ void StackSafetyDataFlowAnalysis::updateOneNode(const GlobalValue *Callee, FunctionInfo &FS) { bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations; bool Changed = false; - for (auto &AS : FS.Allocas) - Changed |= updateOneUse(AS, UpdateToFullSet); for (auto &PS : FS.Params) Changed |= updateOneUse(PS, UpdateToFullSet); @@ -542,9 +509,6 @@ void StackSafetyDataFlowAnalysis::runDataFlow() { for (auto &F : Functions) { Callees.clear(); FunctionInfo &FS = F.second; - for (auto &AS : FS.Allocas) - for (auto &CS : AS.Calls) - Callees.push_back(CS.Callee); for (auto &PS : FS.Params) for (auto &CS : PS.Calls) Callees.push_back(CS.Callee); @@ -573,14 +537,11 @@ void StackSafetyDataFlowAnalysis::verifyFixedPoint() { } #endif -GVToSSI StackSafetyDataFlowAnalysis::run() { +const StackSafetyDataFlowAnalysis::FunctionMap & +StackSafetyDataFlowAnalysis::run() { runDataFlow(); LLVM_DEBUG(verifyFixedPoint()); - - GVToSSI SSI; - for (auto &F : Functions) - SSI.emplace(F.first, makeSSI(F.second)); - return SSI; + return Functions; } bool setStackSafetyMetadata(Module &M, const GVToSSI &SSGI) { @@ -608,6 +569,78 @@ bool setStackSafetyMetadata(Module &M, const GVToSSI &SSGI) { return Changed; } +const Function *FindCalleeInModule(const GlobalValue *GV) { + while (GV) { + if (GV->isInterposable() || !GV->isDSOLocal()) + return nullptr; + if (const Function *F = dyn_cast(GV)) + return F; + const GlobalAlias *A = dyn_cast(GV); + if (!A) + return nullptr; + GV = A->getBaseObject(); + if (GV == A) + return nullptr; + } + return nullptr; +} + +void ResolveAllCalls(UseInfo &Use) { + ConstantRange FullSet(Use.Range.getBitWidth(), true); + for (auto &C : Use.Calls) { + const Function *F = FindCalleeInModule(C.Callee); + if (F) { + C.Callee = F; + continue; + } + + return Use.updateRange(FullSet); + } +} + +void ResolveAllCalls(SmallVectorImpl &Values) { + for (auto &V : Values) + ResolveAllCalls(V); +} + +GVToSSI createGlobalStackSafetyInfo( + std::map Functions) { + GVToSSI SSI; + if (Functions.empty()) + return SSI; + + // FIXME: Simplify printing and remove copying here. + auto Copy = Functions; + + for (auto &FI : Copy) + ResolveAllCalls(FI.second.Params); + + StackSafetyDataFlowAnalysis SSDFA(std::move(Copy)); + + for (auto &F : SSDFA.run()) { + auto FI = F.second; + size_t Pos = 0; + for (auto &A : FI.Allocas) { + ResolveAllCalls(A); + for (auto &C : A.Calls) { + ConstantRange R = SSDFA.getArgumentAccessRange(C.Callee, C.ParamNo); + A.updateRange(R.add(C.Offset)); + } + // FIXME: This is needed only to preserve calls in print() results. + A.Calls = Functions[F.first].Allocas[Pos].Calls; + ++Pos; + } + Pos = 0; + for (auto &P : FI.Params) { + P.Calls = Functions[F.first].Params[Pos].Calls; + ++Pos; + } + SSI.emplace(F.first, makeSSI(std::move(FI))); + } + + return SSI; +} + } // end anonymous namespace StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default; @@ -636,10 +669,6 @@ void StackSafetyGlobalInfo::print(raw_ostream &O) const { O << "\n"; } } - for (auto &A : M.aliases()) { - SSGI.find(&A)->second.print(O, A); - O << "\n"; - } } LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); } @@ -689,11 +718,17 @@ StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) { FunctionAnalysisManager &FAM = AM.getResult(M).getManager(); - StackSafetyDataFlowAnalysis SSDFA( - M, [&FAM](Function &F) -> const FunctionInfo & { - return FAM.getResult(F).getInfo().Info; - }); - return SSDFA.run(); + // FIXME: Lookup Module Summary. + std::map Functions; + + for (auto &F : M.functions()) { + if (!F.isDeclaration()) { + auto FI = FAM.getResult(F).getInfo().Info; + Functions.emplace(&F, std::move(FI)); + } + } + + return createGlobalStackSafetyInfo(std::move(Functions)); } PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M, @@ -729,14 +764,16 @@ void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage( } bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { - StackSafetyDataFlowAnalysis SSDFA( - M, [this](Function &F) -> const FunctionInfo & { - return getAnalysis(F) - .getResult() - .getInfo() - .Info; - }); - SSGI = SSDFA.run(); + std::map Functions; + for (auto &F : M.functions()) { + if (!F.isDeclaration()) { + auto FI = + getAnalysis(F).getResult().getInfo().Info; + Functions.emplace(&F, std::move(FI)); + } + } + + SSGI = createGlobalStackSafetyInfo(std::move(Functions)); return SSGI.setMetadata(M); } diff --git a/llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll b/llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll index d77e7a6..cfb6528 100644 --- a/llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll +++ b/llvm/test/Analysis/StackSafetyAnalysis/ipa-alias.ll @@ -95,39 +95,3 @@ entry: ; 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: ]: -- 2.7.4