[FunctionPropertiesAnalysis] Generalize support for unreachable

[mtrofin]

Summary

Generalized support for subgraphs that get rendered unreachable, for
both call and invoke cases.

[kazu]

LGTM modulo cosmetic changes. Your new algorithm looks pretty robust to me. Thanks!

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

156–160

An instruction can never be CallInst and InvokeInst at the same time because InvokeInst and CallInst are siblings derived from CallBase. Yo could shave one line with:

if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
  const auto *UnwindDest = II->getUnwindDest();
  Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest));
}

230–246

Could we avoid the negated name for clarity? We can shorten the variable name and remove one line.

if (I >= IncludeSuccessorsMark)
  Reinclude.insert(succ_begin(BB), succ_end(BB));

233

May I suggest an empty line immediately after the loop? We are starting a new code block here.

[mtrofin]

feedback

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

OS << "Printing analysis results of CFA for function "
      << "\n";
   AM.getResult<FunctionPropertiesAnalysis>(F).print(OS);
   return PreservedAnalyses::all();
 }
 
 FunctionPropertiesUpdater::FunctionPropertiesUpdater(
     FunctionPropertiesInfo &FPI, const CallBase &CB)
     : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
-
+  assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
   // For BBs that are likely to change, we subtract from feature totals their
   // contribution. Some features, like max loop counts or depths, are left
   // invalid, as they will be updated post-inlining.
   SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
   // The CB BB will change - it'll either be split or the callee's body (single
   // BB) will be pasted in.
   LikelyToChangeBBs.insert(&CallSiteBB);
 
   // The caller's entry BB may change due to new alloca instructions.
   LikelyToChangeBBs.insert(&*Caller.begin());
 
   // The successors may become unreachable in the case of `invoke` inlining.
   // We track successors separately, too, because they form a boundary, together
   // with the CB BB ('Entry') between which the inlined callee will be pasted.
   Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB));
 
+  // Inlining only handles invoke and calls. If this is an invoke, and inlining
+  // it pulls another invoke, the original landing pad may get split, so as to
+  // share its content with other potential users. So the edge up to which we
+  // need to invalidate and then re-account BB data is the successors of the
+  // current landing pad. We can leave the current lp, too - if it doesn't get
+  // split, then it will be the place traversal stops. Either way, the
+  // discounted BBs will be checked if reachable and re-added.
+  if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
+    const auto *UnwindDest = II->getUnwindDest();
+    Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest));
+  }
+
   // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
   // We are only interested in BBs the graph moves past the callsite BB to
   // define the frontier past which we don't want to re-process BBs. Including
   // the callsite BB in this case would prematurely stop the traversal in
   // finish().
   Successors.erase(&CallSiteBB);
 
   for (const auto *BB : Successors)
     LikelyToChangeBBs.insert(BB);
 
   // Commit the change. While some of the BBs accounted for above may play dual
   // role - e.g. caller's entry BB may be the same as the callsite BB - set
   // insertion semantics make sure we account them once. This needs to be
   // followed in `finish`, too.
   for (const auto *BB : LikelyToChangeBBs)
     FPI.updateForBB(*BB, -1);
 }
 
 void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
-  SetVector<const BasicBlock *> Worklist;
-
-  if (&CallSiteBB != &*Caller.begin()) {
-    FPI.reIncludeBB(*Caller.begin());
-    Worklist.insert(&*Caller.begin());
-  }
-
   // Update feature values from the BBs that were copied from the callee, or
   // might have been modified because of inlining. The latter have been
   // subtracted in the FunctionPropertiesUpdater ctor.
   // There could be successors that were reached before but now are only
   // reachable from elsewhere in the CFG.
-  // Suppose the following diamond CFG (lines are arrows pointing down):
+  // One example is the following diamond CFG (lines are arrows pointing down):
   //    A
   //  /   \
   // B     C
+  // |     |
+  // |     D
+  // |     |
+  // |     E
   //  \   /
-  //    D
+  //    F
   // There's a call site in C that is inlined. Upon doing that, it turns out
   // it expands to
   //   call void @llvm.trap()
   //   unreachable
-  // D isn't reachable from C anymore, but we did discount it when we set up
+  // F isn't reachable from C anymore, but we did discount it when we set up
   // FunctionPropertiesUpdater, so we need to re-include it here.
-
+  // At the same time, D and E were reachable before, but now are not anymore,
+  // so we need to leave D out (we discounted it at setup), and explicitly
+  // remove E.
+  SetVector<const BasicBlock *> Reinclude;
+  SetVector<const BasicBlock *> Unreachable;
   const auto &DT =
       FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));
-  for (const auto *Succ : Successors)
-    if (DT.isReachableFromEntry(Succ) && Worklist.insert(Succ))
-      FPI.reIncludeBB(*Succ);
 
-  auto I = Worklist.size();
-  bool CSInsertion = Worklist.insert(&CallSiteBB);
+  if (&CallSiteBB != &*Caller.begin())
+    Reinclude.insert(&*Caller.begin());
+
+  // Distribute the successors to the 2 buckets.
+  for (const auto *Succ : Successors)
+    if (DT.isReachableFromEntry(Succ))
+      Reinclude.insert(Succ);
+    else
+      Unreachable.insert(Succ);
+
+  // For reinclusion, we want to stop at the reachable successors, who are at
+  // the beginning of the worklist; but, starting from the callsite bb and
+  // ending at those successors, we also want to perform a traversal.
+  // IncludeSuccessorsMark is the index after which we include successors.
+  const auto IncludeSuccessorsMark = Reinclude.size();
+  bool CSInsertion = Reinclude.insert(&CallSiteBB);
   (void)CSInsertion;
   assert(CSInsertion);
-  for (; I < Worklist.size(); ++I) {
-    const auto *BB = Worklist[I];
+  for (size_t I = 0; I < Reinclude.size(); ++I) {
+    const auto *BB = Reinclude[I];
     FPI.reIncludeBB(*BB);
-    for (const auto *Succ : successors(BB))
-      Worklist.insert(Succ);
+    if (I >= IncludeSuccessorsMark)
+      Reinclude.insert(succ_begin(BB), succ_end(BB));
+  }
+
+  // For exclusion, we don't need to exclude the set of BBs that were successors
+  // before and are now unreachable, because we already did that at setup. For
+  // the rest, as long as a successor is unreachable, we want to explicitly
+  // exclude it.
+  const auto AlreadyExcludedMark = Unreachable.size();
+  for (size_t I = 0; I < Unreachable.size(); ++I) {
+    const auto *U = Unreachable[I];
+    if (I >= AlreadyExcludedMark)
+      FPI.updateForBB(*U, -1);
+    for (const auto *Succ : successors(U))
+      if (!DT.isReachableFromEntry(Succ))
+        Unreachable.insert(Succ);
   }
 
   const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
   FPI.updateAggregateStats(Caller, LI);
   assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, FAM));
 }

llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp

entry:
   br i1 true, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   %conv2 = sext i32 %value to i64
   br label %cond.end
 
 cond.false:                                       ; preds = %entry
   %call3 = call noundef i64 @f2()
+  br label %extra
+
+extra:
+  br label %extra2
+
+extra2:
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i64 [ %conv2, %cond.true ], [ %call3, %cond.false ]
+  %cond = phi i64 [ %conv2, %cond.true ], [ %call3, %extra ]
   ret i64 %cond
 }
 
 define i64 @f2() {
 entry:
   tail call void @llvm.trap()
   unreachable
 }
 
 declare void @llvm.trap()
 )IR");
 
   Function *F1 = M->getFunction("f1");
   CallBase *CB = findCall(*F1);
   EXPECT_NE(CB, nullptr);
 
   FunctionPropertiesInfo ExpectedInitial;
-  ExpectedInitial.BasicBlockCount = 4;
-  ExpectedInitial.TotalInstructionCount = 7;
+  ExpectedInitial.BasicBlockCount = 6;
+  ExpectedInitial.TotalInstructionCount = 9;
   ExpectedInitial.BlocksReachedFromConditionalInstruction = 2;
   ExpectedInitial.Uses = 1;
   ExpectedInitial.DirectCallsToDefinedFunctions = 1;
   
   FunctionPropertiesInfo ExpectedFinal = ExpectedInitial;
   ExpectedFinal.BasicBlockCount = 4;
   ExpectedFinal.DirectCallsToDefinedFunctions = 0;
   ExpectedFinal.TotalInstructionCount = 7;
 
   auto FPI = buildFPI(*F1);
   EXPECT_EQ(FPI, ExpectedInitial);
 
   FunctionPropertiesUpdater FPU(FPI, *CB);
   InlineFunctionInfo IFI;
   auto IR = llvm::InlineFunction(*CB, IFI);
   EXPECT_TRUE(IR.isSuccess());
   invalidate(*F1);
   FPU.finish(FAM);
   EXPECT_EQ(FPI, ExpectedFinal);
 }
 
+TEST_F(FunctionPropertiesAnalysisTest, InvokeSkipLP) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = makeLLVMModule(C,
+                                             R"IR(
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+define i64 @f1(i32 noundef %value) {
+entry:
+  invoke fastcc void @f2() to label %cont unwind label %lpad
+cont:
+  ret i64 1
+lpad:
+  %lp = landingpad i32 cleanup
+  br label %ehcleanup
+ehcleanup:
+  resume i32 0
+}
+define void @f2() {
+  invoke noundef void @f3() to label %exit unwind label %lpad
+exit:
+  ret void
+lpad:
+  %lp = landingpad i32 cleanup
+  resume i32 %lp
+}
+declare void @f3()
+)IR");
+
+  // The outcome of inlining will be that lpad becomes unreachable. The landing
+  // pad of the invoke inherited from f2 will land on a new bb which will branch
+  // to a bb containing the body of lpad.
+  Function *F1 = M->getFunction("f1");
+  CallBase *CB = findCall(*F1);
+  EXPECT_NE(CB, nullptr);
+
+  FunctionPropertiesInfo ExpectedInitial;
+  ExpectedInitial.BasicBlockCount = 4;
+  ExpectedInitial.TotalInstructionCount = 5;
+  ExpectedInitial.BlocksReachedFromConditionalInstruction = 0;
+  ExpectedInitial.Uses = 1;
+  ExpectedInitial.DirectCallsToDefinedFunctions = 1;
+
+  FunctionPropertiesInfo ExpectedFinal = ExpectedInitial;
+  ExpectedFinal.BasicBlockCount = 6;
+  ExpectedFinal.DirectCallsToDefinedFunctions = 0;
+  ExpectedFinal.TotalInstructionCount = 8;
+
+  auto FPI = buildFPI(*F1);
+  EXPECT_EQ(FPI, ExpectedInitial);
+
+  FunctionPropertiesUpdater FPU(FPI, *CB);
+  InlineFunctionInfo IFI;
+  auto IR = llvm::InlineFunction(*CB, IFI);
+  EXPECT_TRUE(IR.isSuccess());
+  invalidate(*F1);
+  FPU.finish(FAM);
+  EXPECT_EQ(FPI, ExpectedFinal);
+}
 } // end anonymous namespace