FunctionPropertiesAnalysis: handle callsite BBs that loose edges

[mtrofin]

Summary

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):

   A
 /   \
B     C
 \   /
   D

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
FunctionPropertiesUpdater, so we need to re-include it here.

The patch also updates loop accounting to use LoopInfo rather than traverse BBs.

[kazu]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

195

I may be being paranoid here, but is pred_empty(Succ) a correct condition here?

If Succ doesn't have any incoming edge, we can certainly disregard it. Now, if Succ has at least one incoming edge, could we have a corner case like this?

• SuccA has no incoming edge after inlining, and
• SuccB has an incoming edge from SuccA after inlining with no other incoming edge.

In this case, neither SuccA nor SuccB is reachable from the entry basic block, but your algorithm would end up re-including SuccB.

If we know for sure that this kind of thing never happens, I wonder if we can put an assert somewhere. For example, each successor has exactly one incoming edge prior to inlining because of exception semantics or something, we may be able to assert that as we populate Successors.

[mtrofin]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

195

Good point - thanks - and we should be probably just using the dominator tree to see if a BB is reachable from the entry point. I need D127467 landed first, as this fix then depends on that.

[mtrofin]

updated to use domtree instead of counting preds

[kazu]

LGTM with some cosmetic suggestions. Thanks!

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

75

llvm::append_range(Worklist, LI);

81–82

llvm::append_range(Worklist, L->getSubLoops());

196–201

Could we simplify this a little bit like so?

for (const auto *Succ : Successors)
  if (DT.isReachableFromEntry(Succ) && ReIncluded.insert(Succ).second)
    FPI.reIncludeBB(*Succ);

We could use a SetVector as a uniquified work list and prime it with Successors as sentinels, thereby eliminating the two if statements in the while loop above like so:

SetVector<const BasicBlock *> Worklist;

if (&CallSiteBB != &*Caller.begin()) {
  FPI.reIncludeBB(*Caller.begin());
  Worklist.insert(&*Caller.begin());
}

for (const auto *Succ : Successors)
  if (DT.isReachableFromEntry(Succ) && Worklist.insert(Succ))
    FPI.reIncludeBB(*Succ);

unsigned InitialPos = Worklist.size();
Worklist.insert(&CallSiteBB);
for (unsigned I = InitialPos; I != Worklist.size(); I++) {
  const auto *BB = Worklist[I];
  FPI.reIncludeBB(*BB);
  for (const auto *Succ : successors(BB))
    Worklist.insert(Succ);
}

I hear that you have a follow-up patch. Take this suggestion only if it's compatible with your upcoming changes, of course.

[mtrofin]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

196–201

Thanks, this looks neat!

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

 
 void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
                                                   const LoopInfo &LI) {
 
   Uses = getUses(F);
   TopLevelLoopCount = llvm::size(LI);
 }
 
 FunctionPropertiesInfo
 FunctionPropertiesInfo::getFunctionPropertiesInfo(const Function &F,
                                                   const LoopInfo &LI) {
 
   FunctionPropertiesInfo FPI;
   for (const auto &BB : F)
     if (!pred_empty(&BB) || BB.isEntryBlock())
       FPI.reIncludeBB(BB, LI);
   FPI.updateAggregateStats(F, LI);
   return FPI;
 }
 
 void FunctionPropertiesInfo::print(raw_ostream &OS) const {
   OS << "BasicBlockCount: " << BasicBlockCount << "\n"
      << "BlocksReachedFromConditionalInstruction: "
      << BlocksReachedFromConditionalInstruction << "\n"
while (!Worklist.empty()) {
     Worklist.pop_front();
     if (!ReIncluded.insert(BB).second)
       continue;
     FPI.reIncludeBB(*BB, LI);
     if (!Successors.contains(BB))
       for (const auto *Succ : successors(BB))
         Worklist.push_back(Succ);
   }
+
+  // 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):
+  //    A
+  //  /   \ 
+  // B     C
+  //  \   /
+  //    D
+  // 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
+  // FunctionPropertiesUpdater, so we need to re-include it here.
+  for (const auto *Succ : Successors) {
+    if (!ReIncluded.contains(Succ) && !pred_empty(Succ)) {
+      FPI.reIncludeBB(*Succ, LI);
+      ReIncluded.insert(Succ);
+    }
+  }
   FPI.updateAggregateStats(Caller, LI);
   assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, LI));
 }

llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp

)IR");
   FunctionPropertiesUpdater FPU(FPI, *CB);
   InlineFunctionInfo IFI;
   auto IR = llvm::InlineFunction(*CB, IFI);
   EXPECT_TRUE(IR.isSuccess());
   FPU.finish(*LI);
   EXPECT_EQ(FPI, ExpectedFinal);
 }
 
+TEST_F(FunctionPropertiesAnalysisTest, Unreachable) {
+  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:
+  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 %cond.end
+
+cond.end:                                         ; preds = %cond.false, %cond.true
+  %cond = phi i64 [ %conv2, %cond.true ], [ %call3, %cond.false ]
+  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.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());
+  FPU.finish(*LI);
+  EXPECT_EQ(FPI, ExpectedFinal);
+}
+
 } // end anonymous namespace