diff --git a/llvm/lib/Analysis/StackLifetime.cpp b/llvm/lib/Analysis/StackLifetime.cpp
--- a/llvm/lib/Analysis/StackLifetime.cpp
+++ b/llvm/lib/Analysis/StackLifetime.cpp
@@ -174,32 +174,32 @@
 
 void StackLifetime::calculateLocalLiveness() {
   bool Changed = true;
+
+  // LiveIn, LiveOut and BitsIn have a different meaning deppends on type.
+  // ::Maybe true bits represent "may be alive" allocas, ::Must true bits
+  // represent "may be dead". After the loop we will convert ::Must bits from
+  // "may be dead" to "must be alive".
   while (Changed) {
+    // TODO: Consider switching to worklist instead of traversing entire graph.
     Changed = false;
 
     for (const BasicBlock *BB : depth_first(&F)) {
       BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
 
-      // Compute LiveIn by unioning together the LiveOut sets of all preds.
+      // Compute BitsIn by unioning together the LiveOut sets of all preds.
       BitVector BitsIn;
       for (const auto *PredBB : predecessors(BB)) {
         LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
         // If a predecessor is unreachable, ignore it.
         if (I == BlockLiveness.end())
           continue;
-        switch (Type) {
-        case LivenessType::May:
-          BitsIn |= I->second.LiveOut;
-          break;
-        case LivenessType::Must:
-          if (BitsIn.empty())
-            BitsIn = I->second.LiveOut;
-          else
-            BitsIn &= I->second.LiveOut;
-          break;
-        }
+        BitsIn |= I->second.LiveOut;
       }
 
+      // Everything is "may be dead" for entry without predecessors.
+      if (Type == LivenessType::Must && BitsIn.empty())
+        BitsIn.resize(NumAllocas, true);
+
       // Update block LiveIn set, noting whether it has changed.
       if (BitsIn.test(BlockInfo.LiveIn)) {
         BlockInfo.LiveIn |= BitsIn;
@@ -212,8 +212,18 @@
       // because we already handle the case where the BEGIN comes
       // before the END when collecting the markers (and building the
       // BEGIN/END vectors).
-      BitsIn.reset(BlockInfo.End);
-      BitsIn |= BlockInfo.Begin;
+      switch (Type) {
+      case LivenessType::May:
+        BitsIn.reset(BlockInfo.End);
+        // "may be alive" is set by lifetime start.
+        BitsIn |= BlockInfo.Begin;
+        break;
+      case LivenessType::Must:
+        BitsIn.reset(BlockInfo.Begin);
+        // "may be dead" is set by lifetime end.
+        BitsIn |= BlockInfo.End;
+        break;
+      }
 
       // Update block LiveOut set, noting whether it has changed.
       if (BitsIn.test(BlockInfo.LiveOut)) {
@@ -222,6 +232,14 @@
       }
     }
   } // while changed.
+
+  if (Type == LivenessType::Must) {
+    // Convert from "may be dead" to "must be alive".
+    for (auto &[BB, BlockInfo] : BlockLiveness) {
+      BlockInfo.LiveIn.flip();
+      BlockInfo.LiveOut.flip();
+    }
+  }
 }
 
 void StackLifetime::calculateLiveIntervals() {
diff --git a/llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll b/llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll
--- a/llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll
+++ b/llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll
@@ -1070,22 +1070,19 @@
 if.then:
 ; CHECK: if.then:
 ; MAY-NEXT: Alive: <x y>
-; MUST-NEXT: Alive: <>
+; MUST-NEXT: Alive: <x>
   call void @llvm.lifetime.start.p0i8(i64 1, i8* %y)
 ; CHECK: call void @llvm.lifetime.start.p0i8(i64 1, i8* %y)
-; MAY-NEXT: Alive: <x y>
-; MUST-NEXT: Alive: <y>
-; FIXME: Alive: <x y> is expected above.
+; CHECK-NEXT: Alive: <x y>
 
   br i1 %a, label %if.then, label %if.end
 ; CHECK: br i1 %a, label %if.then, label %if.end
-; MAY-NEXT: Alive: <x y>
-; MUST-NEXT: Alive: <y>
+; CHECK-NEXT: Alive: <x y>
 
 if.end:
 ; CHECK: if.end:
 ; MAY-NEXT: Alive: <x y>
-; MUST-NEXT: Alive: <>
+; MUST-NEXT: Alive: <x>
 
   ret void
 }