[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.

1 files changed, 117 insertions, 80 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<UseInfo, 4> Allocas;
   SmallVector<UseInfo, 4> 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<FunctionType>(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<const GlobalValue *, FunctionInfo>;
 
   FunctionMap Functions;
+  const ConstantRange UnknownRange;
+
   // Callee-to-Caller multimap.
   DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers;
   SetVector<const GlobalValue *> 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<const FunctionInfo &(Function &)> FI);
-  GVToSSI run();
-};
+  explicit StackSafetyDataFlowAnalysis(FunctionMap Functions)
+      : Functions(std::move(Functions)),
+        UnknownRange(ConstantRange::getFull(findPointerWidth())) {}
 
-StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis(
-    Module &M, std::function<const FunctionInfo &(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<Function>(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<Function>(GV))
+      return F;
+    const GlobalAlias *A = dyn_cast<GlobalAlias>(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<UseInfo> &Values) {
+  for (auto &V : Values)
+    ResolveAllCalls(V);
+}
+
+GVToSSI createGlobalStackSafetyInfo(
+    std::map<const GlobalValue *, FunctionInfo> 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<FunctionAnalysisManagerModuleProxy>(M).getManager();
 
-  StackSafetyDataFlowAnalysis SSDFA(
-      M, [&FAM](Function &F) -> const FunctionInfo & {
-        return FAM.getResult<StackSafetyAnalysis>(F).getInfo().Info;
-      });
-  return SSDFA.run();
+  // FIXME: Lookup Module Summary.
+  std::map<const GlobalValue *, FunctionInfo> Functions;
+
+  for (auto &F : M.functions()) {
+    if (!F.isDeclaration()) {
+      auto FI = FAM.getResult<StackSafetyAnalysis>(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<StackSafetyInfoWrapperPass>(F)
-            .getResult()
-            .getInfo()
-            .Info;
-      });
-  SSGI = SSDFA.run();
+  std::map<const GlobalValue *, FunctionInfo> Functions;
+  for (auto &F : M.functions()) {
+    if (!F.isDeclaration()) {
+      auto FI =
+          getAnalysis<StackSafetyInfoWrapperPass>(F).getResult().getInfo().Info;
+      Functions.emplace(&F, std::move(FI));
+    }
+  }
+
+  SSGI = createGlobalStackSafetyInfo(std::move(Functions));
   return SSGI.setMetadata(M);
 }