Update BFI when handling inlined landing / eh pad

[hhb]

Summary

When handling inlined landing / eh pad, we may split a block. But we didn't copy BFI to the new block.

This leads to non-deterministic behavior.
In some cases, BlockFrequencyInfoImplBase::getBlockFreq can detect this unknown block and return 0.
In other rare cases, the BasicBlock* happens to be an address used before, an old frequency value will be returned.

This error can be easily detected if -check-bfi-unknown-block-queries is enabled.

https://bugs.llvm.org/show_bug.cgi?id=45789

[hhb]

Rebase

[hhb]

Don't output block name when a node is invalid: it is almost certainly fail.

[hhb]

Revert to last version

[mtrofin]

Shouldn't this happen as part of BasicBlock::splitBasicBlock? Or probably BasicBlockUtils.cpp (llvm::SplitBlock).

There should also probably be a call to BlockFrequencyInfoImpl::forgetBlock that we're missing somewhere, that triggers this in the first place.

This is a good find, and I think we should identify the places that introduce fragility (i.e. deletions of BBs without telling BFI to forget - there seems to have been a design about this, BFICallbackVH, can't seem to find uses of it though)

[hhb]

In D80510#2065193, @mtrofin wrote:

Shouldn't this happen as part of BasicBlock::splitBasicBlock? Or probably BasicBlockUtils.cpp (llvm::SplitBlock).

There should also probably be a call to BlockFrequencyInfoImpl::forgetBlock that we're missing somewhere, that triggers this in the first place.

This is a good find, and I think we should identify the places that introduce fragility (i.e. deletions of BBs without telling BFI to forget - there seems to have been a design about this, BFICallbackVH, can't seem to find uses of it though)

I do want to put this into splitBasicBlock and other related functions. But it seems too intrusive. Consider the situation that all analysis passes adding a parameter to splitBasicBlock...

There are probably many places where forgetBlock is missing. Given that forgetBlock is not even exposed through BlockFrequencyInfo.

But yes this fix is not reliable. All places where a new block is added, need to also update BFI. There's no way to guarantee that.

A couple of ways to fix:

1. Remove BFI "defaults to 0" behavior. This way if a new block is not added to BFI, compiler will likely crash and we will notice. But many other places depends on default 0 and difficult to change.
2. Make sure removed blocks are also removed from BFI. We may need some event mechanism. I'll check BFICallbackVH.
3. Use some other identifier that will not be reused, instead of pointer. It will be a huge change.
4. Add a unit test and enable -check-bfi-unknown-block-queries for it. This is probably the only viable way to go...

[mtrofin]

In D80510#2067235, @hhb wrote:

In D80510#2065193, @mtrofin wrote:

Shouldn't this happen as part of BasicBlock::splitBasicBlock? Or probably BasicBlockUtils.cpp (llvm::SplitBlock).

There should also probably be a call to BlockFrequencyInfoImpl::forgetBlock that we're missing somewhere, that triggers this in the first place.

This is a good find, and I think we should identify the places that introduce fragility (i.e. deletions of BBs without telling BFI to forget - there seems to have been a design about this, BFICallbackVH, can't seem to find uses of it though)

I do want to put this into splitBasicBlock and other related functions. But it seems too intrusive. Consider the situation that all analysis passes adding a parameter to splitBasicBlock...

There are probably many places where forgetBlock is missing. Given that forgetBlock is not even exposed through BlockFrequencyInfo.

But yes this fix is not reliable. All places where a new block is added, need to also update BFI. There's no way to guarantee that.

A couple of ways to fix:

1. Remove BFI "defaults to 0" behavior. This way if a new block is not added to BFI, compiler will likely crash and we will notice. But many other places depends on default 0 and difficult to change.
2. Make sure removed blocks are also removed from BFI. We may need some event mechanism. I'll check BFICallbackVH.
3. Use some other identifier that will not be reused, instead of pointer. It will be a huge change.
4. Add a unit test and enable -check-bfi-unknown-block-queries for it. This is probably the only viable way to go...

I believe point 2 is critically important, and points 1 or 4 are "nice to have": we need to remove the source of non-determinism due to BB pointers being used as keys, and not removed. If a map has a key value "p1" from a BB1, and BB1 is deleted, it is possible, and non-deterministic, that a BB2 be allocated at p, and this would appear as a known BB. -check-bfi-unknown-block-queries would only help with the resulting BB from a split not having BFI data.

[hhb]

D75341 and comments there seem highly related.

[hhb]

In D80510#2067446, @hhb wrote:

D75341 and comments there seem highly related.

Actually that change supposes to fix this kind of non-deterministic. Not sure why it does not work as intended.

We may still want to copy BFI when split BBs. But other concerns should have been solved by CallbackVH...

[mtrofin]

In D80510#2067484, @hhb wrote:

In D80510#2067446, @hhb wrote:

D75341 and comments there seem highly related.

Actually that change supposes to fix this kind of non-deterministic. Not sure why it does not work as intended.

We may still want to copy BFI when split BBs. But other concerns should have been solved by CallbackVH...

Huh.. added davidxl for more background, too, he remembered something along the lines of this non-determinism being addressed somehow (probably via the CallbackVH)

[hhb]

In D80510#2067572, @mtrofin wrote:

In D80510#2067484, @hhb wrote:

In D80510#2067446, @hhb wrote:

D75341 and comments there seem highly related.

Actually that change supposes to fix this kind of non-deterministic. Not sure why it does not work as intended.

We may still want to copy BFI when split BBs. But other concerns should have been solved by CallbackVH...

Huh.. added davidxl for more background, too, he remembered something along the lines of this non-determinism being addressed somehow (probably via the CallbackVH)

Aha it is simply because BFICallbackVH is new enough to not include in Android tree (that's what I test against). I will try again with latest llvm.

[davidxl]

the related fix is https://reviews.llvm.org/D75341 which will turn non-determinstic behavior into 'returning default unknown' which helps -check-bfi-unknown-block-queries to find the issue.

[hhb]

In D80510#2067617, @hhb wrote:

In D80510#2067572, @mtrofin wrote:

In D80510#2067484, @hhb wrote:

In D80510#2067446, @hhb wrote:

D75341 and comments there seem highly related.

Actually that change supposes to fix this kind of non-deterministic. Not sure why it does not work as intended.

We may still want to copy BFI when split BBs. But other concerns should have been solved by CallbackVH...

Huh.. added davidxl for more background, too, he remembered something along the lines of this non-determinism being addressed somehow (probably via the CallbackVH)

Aha it is simply because BFICallbackVH is new enough to not include in Android tree (that's what I test against). I will try again with latest llvm.

D75341 did fix the issue. Then this change is kind of optional. I'll close the bug.

[davidxl]

The direction of the patch is still valid. The patch I mentioned only fixes the non-deterministicness of the problem -- the resulting profile data is still fully updated -- though for landing pad, the default frequency seems ok.

llvm/lib/Transforms/Utils/InlineFunction.cpp

class LandingPadInliningInfo {
     BasicBlock *InnerResumeDest = nullptr;
 
     /// LandingPadInst associated with the invoke.
     LandingPadInst *CallerLPad = nullptr;
 
     /// PHI for EH values from landingpad insts.
     PHINode *InnerEHValuesPHI = nullptr;
 
+    BlockFrequencyInfo *BFI;
+
     SmallVector<Value*, 8> UnwindDestPHIValues;
 
   public:
-    LandingPadInliningInfo(InvokeInst *II)
-        : OuterResumeDest(II->getUnwindDest()) {
+    LandingPadInliningInfo(InvokeInst *II, BlockFrequencyInfo *BFI)
+        : OuterResumeDest(II->getUnwindDest()), BFI(BFI) {
       // If there are PHI nodes in the unwind destination block, we need to keep
       // track of which values came into them from the invoke before removing
       // the edge from this block.
       BasicBlock *InvokeBB = II->getParent();
       BasicBlock::iterator I = OuterResumeDest->begin();
       for (; isa<PHINode>(I); ++I) {
         // Save the value to use for this edge.
         PHINode *PHI = cast<PHINode>(I);

 BasicBlock *LandingPadInliningInfo::getInnerResumeDest() {
   if (InnerResumeDest) return InnerResumeDest;
 
   // Split the landing pad.
   BasicBlock::iterator SplitPoint = ++CallerLPad->getIterator();
   InnerResumeDest =
     OuterResumeDest->splitBasicBlock(SplitPoint,
                                      OuterResumeDest->getName() + ".body");
+  // Copy OuterResumeDest's block frequency to InnerResumeDest
+  if (BFI)
+    BFI->setBlockFreq(InnerResumeDest,
+                      BFI->getBlockFreq(OuterResumeDest).getFrequency());
 
   // The number of incoming edges we expect to the inner landing pad.
   const unsigned PHICapacity = 2;
 
   // Create corresponding new PHIs for all the PHIs in the outer landing pad.
   Instruction *InsertPoint = &InnerResumeDest->front();
   BasicBlock::iterator I = OuterResumeDest->begin();
   for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) {

 }
 
 /// When we inline a basic block into an invoke,
 /// we have to turn all of the calls that can throw into invokes.
 /// This function analyze BB to see if there are any calls, and if so,
 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
 /// nodes in that block with the values specified in InvokeDestPHIValues.
 static BasicBlock *HandleCallsInBlockInlinedThroughInvoke(
-    BasicBlock *BB, BasicBlock *UnwindEdge,
+    BasicBlock *BB, BasicBlock *UnwindEdge, BlockFrequencyInfo *BFI,
     UnwindDestMemoTy *FuncletUnwindMap = nullptr) {
   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
     Instruction *I = &*BBI++;
 
     // We only need to check for function calls: inlined invoke
     // instructions require no special handling.
     CallInst *CI = dyn_cast<CallInst>(I);
 
#ifndef NDEBUG
       else
         MemoKey = FuncletPad;
       assert(FuncletUnwindMap->count(MemoKey) &&
              (*FuncletUnwindMap)[MemoKey] == UnwindDestToken &&
              "must get memoized to avoid confusing later searches");
 #endif // NDEBUG
     }
 
-    changeToInvokeAndSplitBasicBlock(CI, UnwindEdge);
+    BasicBlock *Split = changeToInvokeAndSplitBasicBlock(CI, UnwindEdge);
+    // Copy BB's block frequency to Split
+    if (BFI)
+      BFI->setBlockFreq(Split, BFI->getBlockFreq(BB).getFrequency());
     return BB;
   }
   return nullptr;
 }
 
 /// If we inlined an invoke site, we need to convert calls
 /// in the body of the inlined function into invokes.
 ///
 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
 /// block of the inlined code (the last block is the end of the function),
 /// and InlineCodeInfo is information about the code that got inlined.
 static void HandleInlinedLandingPad(InvokeInst *II, BasicBlock *FirstNewBlock,
+                                    BlockFrequencyInfo *BFI,
                                     ClonedCodeInfo &InlinedCodeInfo) {
   BasicBlock *InvokeDest = II->getUnwindDest();
 
   Function *Caller = FirstNewBlock->getParent();
 
   // The inlined code is currently at the end of the function, scan from the
   // start of the inlined code to its end, checking for stuff we need to
   // rewrite.
-  LandingPadInliningInfo Invoke(II);
+  LandingPadInliningInfo Invoke(II, BFI);
 
   // Get all of the inlined landing pad instructions.
   SmallPtrSet<LandingPadInst*, 16> InlinedLPads;
   for (Function::iterator I = FirstNewBlock->getIterator(), E = Caller->end();
        I != E; ++I)
     if (InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator()))
       InlinedLPads.insert(II->getLandingPadInst());
 
   // Append the clauses from the outer landing pad instruction into the inlined
   // landing pad instructions.
   LandingPadInst *OuterLPad = Invoke.getLandingPadInst();
   for (LandingPadInst *InlinedLPad : InlinedLPads) {
     unsigned OuterNum = OuterLPad->getNumClauses();
     InlinedLPad->reserveClauses(OuterNum);
     for (unsigned OuterIdx = 0; OuterIdx != OuterNum; ++OuterIdx)
       InlinedLPad->addClause(OuterLPad->getClause(OuterIdx));
     if (OuterLPad->isCleanup())
       InlinedLPad->setCleanup(true);
   }
 
   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
        BB != E; ++BB) {
     if (InlinedCodeInfo.ContainsCalls)
       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
-              &*BB, Invoke.getOuterResumeDest()))
+              &*BB, Invoke.getOuterResumeDest(), BFI))
         // Update any PHI nodes in the exceptional block to indicate that there
         // is now a new entry in them.
         Invoke.addIncomingPHIValuesFor(NewBB);
 
     // Forward any resumes that are remaining here.
     if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator()))
       Invoke.forwardResume(RI, InlinedLPads);
   }
 
   // Now that everything is happy, we have one final detail.  The PHI nodes in
   // the exception destination block still have entries due to the original
   // invoke instruction. Eliminate these entries (which might even delete the
   // PHI node) now.
   InvokeDest->removePredecessor(II->getParent());
 }
 
 /// If we inlined an invoke site, we need to convert calls
 /// in the body of the inlined function into invokes.
 ///
 /// II is the invoke instruction being inlined.  FirstNewBlock is the first
 /// block of the inlined code (the last block is the end of the function),
 /// and InlineCodeInfo is information about the code that got inlined.
 static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
+                               BlockFrequencyInfo *BFI,
                                ClonedCodeInfo &InlinedCodeInfo) {
   BasicBlock *UnwindDest = II->getUnwindDest();
   Function *Caller = FirstNewBlock->getParent();
 
   assert(UnwindDest->getFirstNonPHI()->isEHPad() && "unexpected BasicBlock!");
 
   // If there are PHI nodes in the unwind destination block, we need to keep
   // track of which values came into them from the invoke before removing the
for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
     }
   }
 
   if (InlinedCodeInfo.ContainsCalls)
     for (Function::iterator BB = FirstNewBlock->getIterator(),
                             E = Caller->end();
          BB != E; ++BB)
       if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
-              &*BB, UnwindDest, &FuncletUnwindMap))
+              &*BB, UnwindDest, BFI, &FuncletUnwindMap))
         // Update any PHI nodes in the exceptional block to indicate that there
         // is now a new entry in them.
         UpdatePHINodes(NewBB);
 
   // Now that everything is happy, we have one final detail.  The PHI nodes in
   // the exception destination block still have entries due to the original
   // invoke instruction. Eliminate these entries (which might even delete the
   // PHI node) now.
llvm::InlineResult llvm::InlineFunction(CallBase &CB, InlineFunctionInfo &IFI,
   // If we are inlining for an invoke instruction, we must make sure to rewrite
   // any call instructions into invoke instructions.  This is sensitive to which
   // funclet pads were top-level in the inlinee, so must be done before
   // rewriting the "parent pad" links.
   if (auto *II = dyn_cast<InvokeInst>(&CB)) {
     BasicBlock *UnwindDest = II->getUnwindDest();
     Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
     if (isa<LandingPadInst>(FirstNonPHI)) {
-      HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo);
+      HandleInlinedLandingPad(II, &*FirstNewBlock, IFI.CallerBFI,
+                              InlinedFunctionInfo);
     } else {
-      HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo);
+      HandleInlinedEHPad(II, &*FirstNewBlock, IFI.CallerBFI,
+                         InlinedFunctionInfo);
     }
   }
 
   // Update the lexical scopes of the new funclets and callsites.
   // Anything that had 'none' as its parent is now nested inside the callsite's
   // EHPad.
 
   if (CallSiteEHPad) {