[StackSafety] Skip ambiguous lifetime analysis

[vitalybuka]

Summary

If we can't identify alloca used in lifetime marker we
need to assume to worst case scenario.

[t.p.northover]

llvm/include/llvm/Analysis/StackLifetime.h

124

Missing 'n' in "unknown"

llvm/lib/Analysis/StackLifetime.cpp

301

Doesn't this case need the loop below? It looks like it's undoing all the extra default initialization caused by the resize.

Actually, I'd be inclined to reword the whole thing in terms of resizing with the default and separately setting NumAllocas - 1 if that is the correct reading.

[eugenis]

llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll

781–836

Is this a tab character?

[vitalybuka]

fixed typo

[vitalybuka]

llvm/lib/Analysis/StackLifetime.cpp

301

Loop below sets Full range for uninteresting allocas, however with HasUnknowLifetimeStartOrEnd we can't be sure which are uninteresting,
Other than that I am not sure what are you asking.

llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll

781–836

no

[eugenis]

llvm/lib/Analysis/StackLifetime.cpp

301

I think Vitaly's right, if we see a lifetime that can't be traced back to an alloca, we have no way of knowing which allocas are "not interesting" and must handle all of them conservatively.

[eugenis]

LGTM

[ChuanqiXu]

llvm/lib/Analysis/StackLifetime.cpp

78

Maybe we can't use findAllocaForValue to find alloca for lifetime marker. Here I find a pattern:

a = alloca struct ...
b = getelementptr from a
lifetime start (b)
/// ...
lifetime end (b)

And the code here would treat the lifetime span of b, which is part of a, as the whole lifetime of a. But the lifetime span of other component of a may not be the same with the lifetime span of b. I think it may cause mismatch.

[vitalybuka]

llvm/lib/Analysis/StackLifetime.cpp

78

Is this theoretical or something produces such patterns?
I guess we will need to fallback to HasUnknownLifetimeStartOrEnd if life does not cover entire alloca.

[ChuanqiXu]

llvm/lib/Analysis/StackLifetime.cpp

78

I don't find theoretical who produces this pattern. I find such pattern by using StackLifetime in practice. The pattern seems like related to Coroutine Elision which would put one Coroutine Frame structure into another Coroutine Frame. But I don't sure if there is any other situation where would produce similar patterns.
My local fix for this problem is:
replace

const AllocaInst *AI = llvm::findAllocaForValue(II->getArgOperand(1));

into

auto *OpInst = dyn_cast<Instruction>(II->getOperand(1));
auto *AI = dyn_cast<AllocaInst>(OpInst->stripPointerCasts());

which would fallback to HasUnknownLifetimeStartOrEnd if lifetime marker doesn't cover entire alloca as you say.

[vitalybuka]

D86672

llvm/include/llvm/Analysis/StackLifetime.h

struct Marker {
     unsigned AllocaNo;
     bool IsStart;
   };
 
   /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
   DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>
       BBMarkers;
 
+  bool HasUnknownLifetimeStartOrEnd = false;
+
   void dumpAllocas() const;
   void dumpBlockLiveness() const;
   void dumpLiveRanges() const;
 
   void collectMarkers();
   void calculateLocalLiveness();
   void calculateLiveIntervals();
 

llvm/lib/Analysis/StackLifetime.cpp

 //===- StackLifetime.cpp - Alloca Lifetime Analysis -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/StackLifetime.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
auto It = std::upper_bound(Instructions.begin() + ItBB->getSecond().first + 1,
                              [](const Instruction *L, const Instruction *R) {
                                return L->comesBefore(R);
                              });
   --It;
   unsigned InstNum = It - Instructions.begin();
   return getLiveRange(AI).test(InstNum);
 }
 
-static bool readMarker(const Instruction *I, bool *IsStart) {
-  if (!I->isLifetimeStartOrEnd())
-    return false;
-
-  auto *II = cast<IntrinsicInst>(I);
-  *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
-  return true;
-}
-
 void StackLifetime::collectMarkers() {
   InterestingAllocas.resize(NumAllocas);
   DenseMap<const BasicBlock *, SmallDenseMap<const IntrinsicInst *, Marker>>
       BBMarkerSet;
 
   // Compute the set of start/end markers per basic block.
-  for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
-    const AllocaInst *AI = Allocas[AllocaNo];
-    SmallVector<const Instruction *, 8> WorkList;
-    WorkList.push_back(AI);
-    while (!WorkList.empty()) {
-      const Instruction *I = WorkList.pop_back_val();
-      for (const User *U : I->users()) {
-        if (auto *BI = dyn_cast<BitCastInst>(U)) {
-          WorkList.push_back(BI);
-          continue;
-        }
-        auto *UI = dyn_cast<IntrinsicInst>(U);
-        if (!UI)
-          continue;
-        bool IsStart;
-        if (!readMarker(UI, &IsStart))
-          continue;
-        if (IsStart)
-          InterestingAllocas.set(AllocaNo);
-        BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
-      }
+  for (const BasicBlock *BB : depth_first(&F)) {
+    for (const Instruction &I : *BB) {
+      const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
+      if (!II || !II->isLifetimeStartOrEnd())
+      const AllocaInst *AI = llvm::findAllocaForValue(II->getArgOperand(1));
+      if (!AI) {
+        HasUnknownLifetimeStartOrEnd = true;
+      }
+      bool IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
+      unsigned AllocaNo = AllocaNumbering[AI];
+      BBMarkerSet[BB][II] = {AllocaNo, IsStart};
     }
   }
 
   // Compute instruction numbering. Only the following instructions are
   // considered:
   // * Basic block entries
   // * Lifetime markers
   // For each basic block, compute
StackLifetime::StackLifetime(const Function &F,
 
   for (unsigned I = 0; I < NumAllocas; ++I)
     AllocaNumbering[Allocas[I]] = I;
 
   collectMarkers();
 }
 
 void StackLifetime::run() {
+  if (HasUnknownLifetimeStartOrEnd) {
+    // There is marker which we can't assign to a specific alloca, so we
+    // fallback to the most conservative results for the type.
+    switch (Type) {
+    case LivenessType::May:
+      LiveRanges.resize(NumAllocas, getFullLiveRange());
+      break;
+    case LivenessType::Must:
+      LiveRanges.resize(NumAllocas, LiveRange(Instructions.size()));
+      break;
+    }
+    return;
+  }
+
   LiveRanges.resize(NumAllocas, LiveRange(Instructions.size()));
   for (unsigned I = 0; I < NumAllocas; ++I)
     if (!InterestingAllocas.test(I))
       LiveRanges[I] = getFullLiveRange();
 
   calculateLocalLiveness();
   LLVM_DEBUG(dumpBlockLiveness());
   calculateLiveIntervals();

llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll

 ; CHECK: br label %if.end
 ; CHECK-NEXT: Alive: <x y>
 
 if.end:
 ; CHECK: if.end:
 ; MAY-NEXT: Alive: <x y>
 ; MUST-NEXT: Alive: <y>
 
   ret void
 }
 
 define void @unreachable() {
 ; CHECK-LABEL: define void @unreachable
 entry:
 ; CHECK: entry:
 ; CHECK-NEXT: Alive: <>
   %x = alloca i8, align 4
; CHECK-NOT: Alive:
   br label %end
 ; CHECK: br label %end
 ; CHECK-NOT: Alive:
 
 end:
 ; CHECK: end:
 ; CHECK-NEXT: Alive: <x y>
 
   ret void
 }
 
+define void @non_alloca(i8* %p) {
+; CHECK-LABEL: define void @non_alloca
+entry:
+; CHECK: entry:
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+  %x = alloca i8, align 4
+  %y = alloca i8, align 4
+
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %p)
+; CHECK: call void @llvm.lifetime.start.p0i8(i64 4, i8* %p)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %x)
+; CHECK: call void @llvm.lifetime.start.p0i8(i64 4, i8* %x)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %p)
+; CHECK: call void @llvm.lifetime.end.p0i8(i64 4, i8* %p)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  ret void
+}
+
+define void @select_alloca(i1 %v) {
+; CHECK-LABEL: define void @select_alloca
+entry:
+; CHECK: entry:
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+  %x = alloca i8, align 4
+  %y = alloca i8, align 4
+  %cxcy = select i1 %v, i8* %x, i8* %y
+
+  call void @llvm.lifetime.start.p0i8(i64 1, i8* %cxcy)
+; CHECK: call void @llvm.lifetime.start.p0i8(i64 1, i8* %cxcy)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  call void @llvm.lifetime.start.p0i8(i64 1, i8* %x)
+; CHECK: call void @llvm.lifetime.start.p0i8(i64 1, i8* %x)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  call void @llvm.lifetime.end.p0i8(i64 1, i8* %x)
+; CHECK: call void @llvm.lifetime.end.p0i8(i64 1, i8* %x)
+; MAY-NEXT: Alive: <x y>
+; MUST-NEXT: Alive: <>
+
+  ret void
+}
+
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
 declare void @capture8(i8*)
 declare void @capture32(i32*)
 declare void @capture64(i64*)
 declare void @capture100x32([100 x i32]*)

llvm/test/CodeGen/AArch64/stack-tagging.ll

 ; CHECK-LABEL: define void @UnrecognizedLifetime(
 ; CHECK: call i8* @llvm.aarch64.irg.sp(i64 0)
 ; CHECK: alloca { i32, [12 x i8] }, align 16
 ; CHECK: call { i32, [12 x i8] }* @llvm.aarch64.tagp
 ; CHECK: call void @llvm.aarch64.settag(
 ; CHECK: alloca { i32, [12 x i8] }, align 16
 ; CHECK: call { i32, [12 x i8] }* @llvm.aarch64.tagp
 ; CHECK: call void @llvm.aarch64.settag(
-; SSI: alloca i32, align 4
-; NOSSI: alloca { i32, [12 x i8] }, align 16
-; NOSSI: call { i32, [12 x i8] }* @llvm.aarch64.tagp
-; NOSSI: call void @llvm.aarch64.settag(
+; CHECK: alloca { i32, [12 x i8] }, align 16
+; CHECK: call { i32, [12 x i8] }* @llvm.aarch64.tagp
+; CHECK: call void @llvm.aarch64.settag(
 ; CHECK: store i32
 ; CHECK: call void @noUse32(i32*
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: call void @noUse32(i32*
 ; CHECK: call void @llvm.aarch64.settag(
 ; CHECK: call void @llvm.aarch64.settag(
-; NOSSI: call void @llvm.aarch64.settag(
+; CHECK: call void @llvm.aarch64.settag(
 ; CHECK: ret void
 
-!0 = !{}
+!0 = !{}