[asan] Avoid lifetime analysis for allocas with can be in ambiguous state

Summary:
C allows to jump over variables declaration so lifetime.start can be
avoid before variable usage. To avoid false-positives on such rare cases
we detect them and remove from lifetime analysis.

PR27453
PR28267

Reviewers: eugenis

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D24321

llvm-svn: 280880

1 files changed, 74 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp
index dfdcd1122da..94a81c0005a 100644
--- a/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp
+++ b/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp
@@ -833,6 +833,76 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
                      Instruction *ThenTerm, Value *ValueIfFalse);
 };
 
+// Performs depth-first search on the control flow graph of block and checks if
+// we can get into the same block with different lifetime state.
+class AllocaLifetimeChecker {
+  // Contains values of the last lifetime intrinsics in the block.
+  // true: llvm.lifetime.start, false: llvm.lifetime.end
+  DenseMap<const BasicBlock *, bool> Markers;
+  // Contains the lifetime state we detected doing depth-first search on the
+  // control flow graph. We expect all future hits will have the same value.
+  // true: llvm.lifetime.start, false: llvm.lifetime.end
+  DenseMap<const BasicBlock *, bool> InboundState;
+  bool Processed = false;
+  bool CollisionDetected = false;
+
+  bool FindCollision(const std::pair<const BasicBlock *, bool> &BlockState) {
+    auto Ins = InboundState.insert(BlockState);
+    if (!Ins.second) {
+      // Already there. Return collision if they are different.
+      return BlockState.second != Ins.first->second;
+    }
+
+    // Use marker for successors if block contains any.
+    auto M = Markers.find(BlockState.first);
+    bool NewState = (M != Markers.end() ? M->second : BlockState.second);
+    for (const BasicBlock *SB : successors(BlockState.first))
+      if (FindCollision({SB, NewState}))
+        return true;
+
+    return false;
+  }
+
+public:
+  // Assume that markers of the same block will be added in the same order as
+  // the order of corresponding intrinsics, so in the end we will keep only
+  // value of the last intrinsic.
+  void AddMarker(const BasicBlock *BB, bool start) {
+    assert(!Processed);
+    Markers[BB] = start;
+  }
+
+  bool HasAmbiguousLifetime() {
+    if (!Processed) {
+      Processed = true;
+      const Function *F = Markers.begin()->first->getParent();
+      CollisionDetected = FindCollision({&F->getEntryBlock(), false});
+    }
+    return CollisionDetected;
+  }
+};
+
+// Removes allocas for which exists at least one block simultaneously
+// reachable in both states: allocas is inside the scope, and alloca is outside
+// of the scope. We don't have enough information to validate access to such
+// variable, so we just remove such allocas from lifetime analysis.
+// This is workaround for PR28267.
+void removeAllocasWithAmbiguousLifetime(
+    SmallVectorImpl<FunctionStackPoisoner::AllocaPoisonCall> &PoisonCallVec) {
+  DenseMap<const AllocaInst *, AllocaLifetimeChecker> Checkers;
+  for (const auto &APC : PoisonCallVec)
+    Checkers[APC.AI].AddMarker(APC.InsBefore->getParent(), !APC.DoPoison);
+
+  auto IsAmbiguous =
+      [&Checkers](const FunctionStackPoisoner::AllocaPoisonCall &APC) {
+        return Checkers[APC.AI].HasAmbiguousLifetime();
+      };
+
+  PoisonCallVec.erase(
+      std::remove_if(PoisonCallVec.begin(), PoisonCallVec.end(), IsAmbiguous),
+      PoisonCallVec.end());
+}
+
 } // anonymous namespace
 
 char AddressSanitizer::ID = 0;
@@ -2110,6 +2180,8 @@ void FunctionStackPoisoner::processDynamicAllocas() {
     return;
   }
 
+  removeAllocasWithAmbiguousLifetime(DynamicAllocaPoisonCallVec);
+
   // Insert poison calls for lifetime intrinsics for dynamic allocas.
   for (const auto &APC : DynamicAllocaPoisonCallVec) {
     assert(APC.InsBefore);
@@ -2137,6 +2209,8 @@ void FunctionStackPoisoner::processStaticAllocas() {
     return;
   }
 
+  removeAllocasWithAmbiguousLifetime(StaticAllocaPoisonCallVec);
+
   int StackMallocIdx = -1;
   DebugLoc EntryDebugLocation;
   if (auto SP = F.getSubprogram())