[FIX] Avoid creating BFI when emitting remarks for dead functions

[weiwang]

Summary

Dead function has its body stripped away, and can cause various
analyses to panic. Also it does not make sense to apply analyses on
such function.

[weiwang]

To reproduce:

1. create test file main.cpp

int bar() {
  return 2;
}

int foo() {
  return 1;
}

int main() {
  foo();
  return 0;
}

2. compile with clang: -fuse-ld=lld -O3 -flto=full -Wl,--opt-remarks-with-hotness -o test main.cpp

If clang has assertion enabled, it would hit the following assertion at ilist_iterator.h:138:

Assertion `!NodePtr->isKnownSentinel()' failed

otherwise, the behavior is undefined.

It is triggered at the point where ORE is created to emit dead functions LTO.cpp:801.

[wenlei]

I'm guessing these are not the only passes that will choke with empty/dead functions. If this is because ORE is being used for a special case, then we might want to fix the special case on the user side.

If we want passes to absorb such empty functions, then there needs to be consistency for all passes. I don't think passes need to absorb such cases though, as this is really a "limbo state" of functions when being removed (a normal empty function should still have entry block and ret instruction).

[MaskRay]

Test?

llvm/include/llvm/Support/GenericDomTreeConstruction.h

530

llvm-project currently requires C++14. C++17 extensions can't be used. (As an exception, if init-statement is allowed)

[fhahn]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

1137

Are empty functions valid IR? Don't they have to have at least a single BB. And each BB needs at least a terminator?

[weiwang]

In D84715#2177627, @wenlei wrote:

I'm guessing these are not the only passes that will choke with empty/dead functions. If this is because ORE is being used for a special case, then we might want to fix the special case on the user side.

If we want passes to absorb such empty functions, then there needs to be consistency for all passes. I don't think passes need to absorb such cases though, as this is really a "limbo state" of functions when being removed (a normal empty function should still have entry block and ret instruction).

Agree. The proposed checks are only placed along the particular call path that leads to the failure. If we are going cover all the analyses/passes, the overall effort could be substantial.

If the big assumption is that there shouldn't be an empty body function to deal with, we can probably change how ORE is created at the beginning. Instead of creating a heavy-weight version of ORE (with all dependent analyses invoked), using the light-weight version OptimizationRemarkEmitter ORE(F, nullptr) at LTO.cpp:801.

llvm/lib/Analysis/BranchProbabilityInfo.cpp

1137

This is a special case where function is marked dead and its body is completed strip away. AFAIK, it only happens before LTO backend, so analysis/pass in pass pipeline won't see such function.

[weiwang]

add test case

[hoyFB]

In D84715#2179099, @weiwang wrote:

In D84715#2177627, @wenlei wrote:

I'm guessing these are not the only passes that will choke with empty/dead functions. If this is because ORE is being used for a special case, then we might want to fix the special case on the user side.

If we want passes to absorb such empty functions, then there needs to be consistency for all passes. I don't think passes need to absorb such cases though, as this is really a "limbo state" of functions when being removed (a normal empty function should still have entry block and ret instruction).

Agree. The proposed checks are only placed along the particular call path that leads to the failure. If we are going cover all the analyses/passes, the overall effort could be substantial.

If the big assumption is that there shouldn't be an empty body function to deal with, we can probably change how ORE is created at the beginning. Instead of creating a heavy-weight version of ORE (with all dependent analyses invoked), using the light-weight version OptimizationRemarkEmitter ORE(F, nullptr) at LTO.cpp:801.

Can we bail out for dead/empty functions right there before launching ORE on them?

[wenlei]

In D84715#2186299, @hoyFB wrote:

In D84715#2179099, @weiwang wrote:

In D84715#2177627, @wenlei wrote:

I'm guessing these are not the only passes that will choke with empty/dead functions. If this is because ORE is being used for a special case, then we might want to fix the special case on the user side.

If we want passes to absorb such empty functions, then there needs to be consistency for all passes. I don't think passes need to absorb such cases though, as this is really a "limbo state" of functions when being removed (a normal empty function should still have entry block and ret instruction).

Agree. The proposed checks are only placed along the particular call path that leads to the failure. If we are going cover all the analyses/passes, the overall effort could be substantial.

If the big assumption is that there shouldn't be an empty body function to deal with, we can probably change how ORE is created at the beginning. Instead of creating a heavy-weight version of ORE (with all dependent analyses invoked), using the light-weight version OptimizationRemarkEmitter ORE(F, nullptr) at LTO.cpp:801.

Can we bail out for dead/empty functions right there before launching ORE on them?

I think the error path involved here was specifically for emitting remarks about dead functions. So bailout for that case effectively means removing ORE there. With that, something like OptimizationRemarkEmitter ORE(F, nullptr) for that path seem to make sense.

[weiwang]

Instead of adding checks for all passes/analyses, use light-weight ORE to emit remarks for dead functions.

[MaskRay]

LG. Would be wise waiting for a second opinion

llvm/test/LTO/Resolution/X86/dead-strip-fulllto.ll

4

Add a comment about --pass-remarks-with-hotness

[wenlei]

LTGM too. Thanks for the fix!

[xazax.hun]

Thanks! Sorry for not noticing this earlier. The fix looks good to me and indeed the original intention was to report dead functions with ORE.

[weiwang]

add comment on test case.

llvm/include/llvm/Analysis/LoopInfoImpl.h

 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
 ///
 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
 /// insertions per block.
 template <class BlockT, class LoopT>
 void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
   // Postorder traversal of the dominator tree.
   const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
+  if (!DomRoot)
+    return;
+
   for (auto DomNode : post_order(DomRoot)) {
 
     BlockT *Header = DomNode->getBlock();
     SmallVector<BlockT *, 4> Backedges;
 
     // Check each predecessor of the potential loop header.
     for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
       // If Header dominates predBB, this is a new loop. Collect the backedges.

llvm/include/llvm/Support/GenericDomTreeConstruction.h

 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTree.h"
 #include <queue>
 
 #define DEBUG_TYPE "dom-tree-builder"
 
 namespace llvm {
 namespace DomTreeBuilder {
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     unsigned Num = 1;
     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
   }
 
   static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     auto *Parent = DT.Parent;
     DT.reset();
     DT.Parent = Parent;
+
+    if constexpr (std::is_same<
+                      Function *,
+                      typename std::remove_const<
+                          typename DomTreeT::ParentPtr>::type>::value) {
+      if (auto *F = dyn_cast<Function>(DT.Parent))
+        if (F->empty())
+          return;
+    }
+
     SemiNCAInfo SNCA(nullptr);  // Since we are rebuilding the whole tree,
                                 // there's no point doing it incrementally.
 
     // Step #0: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
     DT.Roots = FindRoots(DT, nullptr);
     SNCA.doFullDFSWalk(DT, AlwaysDescend);
 

llvm/lib/Analysis/BlockFrequencyInfo.cpp

bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
   auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 void BlockFrequencyInfo::calculate(const Function &F,
                                    const BranchProbabilityInfo &BPI,
                                    const LoopInfo &LI) {
+  if (F.empty())
+    return;
+
   if (!BFI)
     BFI.reset(new ImplType);
   BFI->calculate(F, BPI, LI);
   if (ViewBlockFreqPropagationDAG != GVDT_None &&
       (ViewBlockFreqFuncName.empty() ||
        F.getName().equals(ViewBlockFreqFuncName))) {
     view();
   }

llvm/lib/Analysis/BranchProbabilityInfo.cpp

void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
   }
 }
 
 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
                                       const TargetLibraryInfo *TLI,
                                       PostDominatorTree *PDT) {
   LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
                     << " ----\n\n");
+  if (F.empty())
+    return;
+
   LastF = &F; // Store the last function we ran on for printing.
   assert(PostDominatedByUnreachable.empty());
   assert(PostDominatedByColdCall.empty());
 
   SccI = std::make_unique<SccInfo>(F);
 
   std::unique_ptr<PostDominatorTree> PDTPtr;
 

llvm/test/LTO/Resolution/X86/dead-strip-fulllto.ll

 ; RUN: opt -module-summary -o %t %s
 ; RUN: opt -module-summary -o %t2 %S/Inputs/dead-strip-fulllto.ll
 
-; RUN: llvm-lto2 run --pass-remarks-output=%t4.yaml --pass-remarks-filter=. \
+; RUN: llvm-lto2 run --pass-remarks-output=%t4.yaml --pass-remarks-filter=. --pass-remarks-with-hotness \
 ; RUN:               %t -r %t,main,px -r %t,live1, -r %t,live2,p -r %t,dead2,p \
 ; RUN:               %t2 -r %t2,live1,p -r %t2,live2, -r %t2,dead1,p -r %t2,dead2, -r %t2,odr, \
 ; RUN:               -save-temps -o %t3
 
 ; RUN: cat %t4.yaml | FileCheck %s -check-prefix=REMARK
 ; RUN: llvm-nm %t3.0 | FileCheck --check-prefix=FULL %s
 ; RUN: llvm-nm %t3.1 | FileCheck --check-prefix=THIN %s