[StackLifetime] More efficient loop for LivenessType::Must

[vitalybuka]

Summary

CFG with cycles may requires additional passes of "while (Changed)"
iteration if to propagate data back from latter blocks to earlier blocks,
ordered according to depth_fist.

OR logic, used for ::May, converge to stable state faster then AND logic
use for ::Must.

Though the better solution is to switch to some some form of queue, but
having that this one is good enough, I will consider to do that later.

We can switch ::Must to OR logic if we calculate "may be dead" instead
of direct "must be alive" and then convert values to match existing
interface.

Additionally it fixes correctness in "@cycle" test.

[fmayer]

llvm/lib/Analysis/StackLifetime.cpp

200–201

if you wanted to micro-optimize, you could put the BlockInfo.LiveIn |= BitsIn in this condition, and make the one below an else if.

217–218

these comments are a bit confusing. it says "set by lifetime start" then uses BlockInfo.End.

[vitalybuka]

llvm/lib/Analysis/StackLifetime.cpp

200–201

I'll keep as-is for simplicity. This apply only to the entry.

217–218

I'll move to the next line in the next snapshot.

[vitalybuka]

comment

[vitalybuka]

another comment

[fmayer]

llvm/lib/Analysis/StackLifetime.cpp

222

nit for consistency with above.

[vitalybuka]

comments

llvm/lib/Analysis/StackLifetime.cpp

for (const BasicBlock *BB : depth_first(&F)) {
     }
 
     BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size());
   }
 }
 
 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;
-        }
       }
 
+      // 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;
       }
 
       // Compute LiveOut by subtracting out lifetimes that end in this
       // block, then adding in lifetimes that begin in this block.  If
       // we have both BEGIN and END markers in the same basic block
       // then we know that the BEGIN marker comes after the END,
       // because we already handle the case where the BEGIN comes
       // before the END when collecting the markers (and building the
       // BEGIN/END vectors).
+      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)) {
         Changed = true;
         BlockInfo.LiveOut |= BitsIn;
       }
     }
   } // 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() {
   for (auto IT : BlockLiveness) {
     const BasicBlock *BB = IT.getFirst();
     BlockLifetimeInfo &BlockInfo = IT.getSecond();
     unsigned BBStart, BBEnd;
     std::tie(BBStart, BBEnd) = BlockInstRange[BB];

llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll

; CHECK-NEXT: Alive: <x>
 
   br i1 %a, label %if.then, label %if.end
 ; CHECK: br i1 %a, label %if.then, label %if.end
 ; CHECK-NEXT: Alive: <x>
 
 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
 }
 
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
 declare void @llvm.lifetime.start.p0i32(i64, i32* nocapture)
 declare void @llvm.lifetime.end.p0i32(i64, i32* nocapture)
 declare void @capture8(i8*)
 declare void @capture32(i32*)
 declare void @capture64(i64*)
 declare void @capture100x32([100 x i32]*)