[ASan] Workaround for a performance problem in StackSafetyAnalysis pass.

[kstoimenov]

Summary

There is a performance problem in StackLifetime::calculateLocalLiveness when a function has a lot of allocas. The stack-safety-max-allocas flag prevents this algorithm from being invoked for such functions.

[vitalybuka]

llvm/test/Instrumentation/AddressSanitizer/asan-stack-safety.ll

3 ↗

(On Diff #463348)

don't break lines, line len is not enforced in tests

7 ↗

(On Diff #463348)

you are fixing StackSafetyAnalysis.cpp, so the test must be in those tests

[vitalybuka]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

62

int is enough

[kstoimenov]

Addressed comments.

llvm/lib/Analysis/StackSafetyAnalysis.cpp

62

Yeah, but it produces a warning when I compare it with .size().

llvm/test/Instrumentation/AddressSanitizer/asan-stack-safety.ll

3 ↗

(On Diff #463348)

I prefer that for readability.

[vitalybuka]

llvm/test/Analysis/StackSafetyAnalysis/stack-safety-max-allocas.ll

1

not needed?

3

broken lines hard to read when you have many of them, all RUNs looks the same them
long lines not nice in some editors, but very convenient to compare RUNs

so I prefer long RUN line exactly for readability

3

instead of asan please directly use the pass: -passes="print-stack-safety"

example local.ll

4

can you do at least =1 and have one function with 1 and one function with 2 allocas

[vitalybuka]

llvm/test/Analysis/StackSafetyAnalysis/stack-safety-max-allocas.ll

3

it changes function local part, so please check -passes="print<stack-safety-local>"as well

[vitalybuka]

I guess I understand the problem. Algorithm is O(A*B*B) for ::Must case, where A-num allocas, B is num of basic blocks. But it should be O(A*B) as of ::May case.
ll try to create a patch.

If we do a limiter, it should be by B.

llvm/lib/Analysis/StackSafetyAnalysis.cpp

STATISTIC(NumCombinedParamAccessesAfter,
           "Number of total param accesses after generateParamAccessSummary.");
 STATISTIC(NumCombinedDataFlowNodes,
           "Number of total nodes in combined index for dataflow processing.");
 STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.");
 STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.");
 STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.");
 
 
+static cl::opt<size_t> StackSafetyMaxAllocas("stack-safety-max-allocas",
+                                             cl::init(250), cl::Hidden);
+
 static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
                                              cl::init(20), cl::Hidden);
 
 static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),
                                       cl::Hidden);
 
 static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),
                                     cl::Hidden);
FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
   FunctionInfo<GlobalValue> Info;
   assert(!F.isDeclaration() &&
          "Can't run StackSafety on a function declaration");
 
   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
 
   SmallVector<AllocaInst *, 64> Allocas;
   for (auto &I : instructions(F))
-    if (auto *AI = dyn_cast<AllocaInst>(&I))
+    if (auto *AI = dyn_cast<AllocaInst>(&I)) {
       Allocas.push_back(AI);
+      // Skip stack safety analysis if there are too many allocas.
+      if (Allocas.size() > StackSafetyMaxAllocas) {
+        LLVM_DEBUG(dbgs() << "\n[StackSafety] skipped\n");
+        return Info;
+      }
+    }
+
   StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);
   SL.run();
 
   for (auto *AI : Allocas) {
     auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
     analyzeAllUses(AI, UI, SL);
   }
 

llvm/test/Analysis/StackSafetyAnalysis/stack-safety-max-allocas.ll

+; REQUIRES: x86-registered-target
+
+; RUN: opt < %s -S -asan-instrumentation-with-call-threshold=0 -passes='asan-pipeline' -asan-use-stack-safety=1 \
+; RUN:   -stack-safety-max-allocas=0 -o - | FileCheck %s --check-prefixes=ALLOCAS
+
+; ALLOCAS-LABEL: define i32 @f
+define i32 @f() sanitize_address {
+  %buf = alloca [10 x i8], align 1
+  ; ALLOCAS: call i64 @__asan_stack_malloc
+  %arrayidx = getelementptr inbounds [10 x i8], [10 x i8]* %buf, i64 0, i64 0
+  %1 = load i8, i8* %arrayidx, align 1
+  ret i32 0
+}