[BFI][CGP] Add limited support for detecting missed BFI updates and fix one in CodeGenPrepare.

[hjyamauchi]

Summary

This helps detect some missed BFI updates during CodeGenPrepare.

This is debug build only and disabled behind a flag.

Fix a missed update in CodeGenPrepare::dupRetToEnableTailCallOpts().

[lebedev.ri]

There's already -verify, -verify-dom-info, etc.
I wonder if this should follow similar pattern?

[davidxl]

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

1467

If there is no mismatch detected at this point, the following check is redundant.

llvm/lib/CodeGen/CodeGenPrepare.cpp

2221

Add assert that BB's frequency >= TailCallBB's freq?

[hjyamauchi]

Address comment.

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

1467

If there's a valid block in the Other BFI that's not in this BFI, this code is useful, as the comparison goes both ways?

llvm/lib/CodeGen/CodeGenPrepare.cpp

2221

Added one only under this check mode as I think the assert outside this BFI update check mode would be too strong at this point. Note that BlockFrequency avoids an underflow.

BlockFrequency &BlockFrequency::operator-=(BlockFrequency Freq) {
  // If underflow, set frequency to 0.
  if (Frequency <= Freq.Frequency)
    Frequency = 0;
  else
    Frequency -= Freq.Frequency;
  return *this;
}

[davidxl]

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

1467

There are two cases:

1. when the NumberOfValidNodes is different
2. when the NumberOfValidNodes is the same.

For the first case, the mismatch will be caught earlier. For the second case, in order to be 'mismatched', there must be a validNode in *this not in Other. Otherwise, Other will be a superset of *this, and it will become case #1. THis means the case 2 will also be caught in the previous loop.

[hjyamauchi]

Address comment.

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

1467

Done.

[davidxl]

llvm/lib/CodeGen/CodeGenPrepare.cpp

233

is it useful to extend the verification to earlier passes in the future?

[lebedev.ri]

In D77417#1960407, @lebedev.ri wrote:

There's already -verify, -verify-dom-info, etc.
I wonder if this should follow similar pattern?

[hjyamauchi]

In D77417#1980363, @lebedev.ri wrote:

In D77417#1960407, @lebedev.ri wrote:

There's already -verify, -verify-dom-info, etc.
I wonder if this should follow similar pattern?

The flag name was renamed from "check" to "verify".

llvm/lib/CodeGen/CodeGenPrepare.cpp

233

It would be (but it's not easy though.)

[lebedev.ri]

In D77417#1980889, @yamauchi wrote:

In D77417#1980363, @lebedev.ri wrote:

In D77417#1960407, @lebedev.ri wrote:

There's already -verify, -verify-dom-info, etc.
I wonder if this should follow similar pattern?

The flag name was renamed from "check" to "verify".

Hmm, maybe i should be more verbose.
My question is, we already have some sudo-passes (-verify, -verify-dom-info)
that can be run after any pass, that verify that internal invariants still hold
at the time they are run. I may be wrong, but it seems like
this is adding a similar consistency check, but it is hardcoded to one particular
position of the pipeline - before CGP. So i'm wondering if i'm misreading that,
and if not whether it should be generalized so that BFI consistency can be checked
after any pass of choice.

[hjyamauchi]

Noting that the "updatedness" of BFI *during a pass* is currently only on a best effort basis, what this patch is intended to provide is to have a way to check how well BFI is updated during CGP. It's sort of a middle ground between teaching CGP to preserve BFI (which is hard) and having no way to assess how well it can preserve BFI. Because its updatedness could still have performance consequences.

As I see it, this is a bit different from -verify/-verify-dom-info in that unlike -verify, it cannot be a separate pass as it needs to look at the state of BFI right before it gets erased at the end of CGP (as CGP isn't declared to preserve BFI), and unlike -verify-dom-info, Pass:verifyAnalysis isn't a good place to check it in as Pass:verifyAnalysis is called on preserved analyses only. Though we might be able to extend the pass manager interface to have a place for it (maybe checkNotPreservedAnalysis?) if it's really a good idea. I'm not sure if it's mature enough at this point to be generalized.

[davidxl]

lgtm

llvm/include/llvm/Analysis/BlockFrequencyInfo.h

 //===- BlockFrequencyInfo.h - Block Frequency Analysis ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
public:
 
   // Convenience method that attempts to look up the frequency associated with
   // BB and print it to OS.
   raw_ostream &printBlockFreq(raw_ostream &OS, const BasicBlock *BB) const;
 
   uint64_t getEntryFreq() const;
   void releaseMemory();
   void print(raw_ostream &OS) const;
+
+  // Compare to the other BFI and verify they match.
+  void verifyMatch(BlockFrequencyInfo &Other) const;
 };
 
 /// Analysis pass which computes \c BlockFrequencyInfo.
 class BlockFrequencyAnalysis
     : public AnalysisInfoMixin<BlockFrequencyAnalysis> {
   friend AnalysisInfoMixin<BlockFrequencyAnalysis>;
 
   static AnalysisKey Key;

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

 //==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
public:
   raw_ostream &print(raw_ostream &OS) const override;
 
   using BlockFrequencyInfoImplBase::dump;
   using BlockFrequencyInfoImplBase::printBlockFreq;
 
   raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const {
     return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB));
   }
+
+  void verifyMatch(BlockFrequencyInfoImpl<BT> &Other) const;
 };
 
 namespace bfi_detail {
 
 template <class BFIImplT>
 class BFICallbackVH<BasicBlock, BFIImplT> : public CallbackVH {
   BFIImplT *BFIImpl;
 
for (const BlockT &BB : *F) {
     OS << "\n";
   }
 
   // Add an extra newline for readability.
   OS << "\n";
   return OS;
 }
 
+template <class BT>
+void BlockFrequencyInfoImpl<BT>::verifyMatch(
+    BlockFrequencyInfoImpl<BT> &Other) const {
+  bool Match = true;
+  DenseMap<const BlockT *, BlockNode> ValidNodes;
+  DenseMap<const BlockT *, BlockNode> OtherValidNodes;
+  for (auto &Entry : Nodes) {
+    const BlockT *BB = Entry.first;
+    if (BB) {
+      ValidNodes[BB] = Entry.second.first;
+    }
+  }
+  for (auto &Entry : Other.Nodes) {
+    const BlockT *BB = Entry.first;
+    if (BB) {
+      OtherValidNodes[BB] = Entry.second.first;
+    }
+  }
+  unsigned NumValidNodes = ValidNodes.size();
+  unsigned NumOtherValidNodes = OtherValidNodes.size();
+  if (NumValidNodes != NumOtherValidNodes) {
+    Match = false;
+    dbgs() << "Number of blocks mismatch: " << NumValidNodes << " vs "
+           << NumOtherValidNodes << "\n";
+  } else {
+    for (auto &Entry : ValidNodes) {
+      const BlockT *BB = Entry.first;
+      BlockNode Node = Entry.second;
+      if (OtherValidNodes.count(BB)) {
+        BlockNode OtherNode = OtherValidNodes[BB];
+        auto Freq = Freqs[Node.Index];
+        auto OtherFreq = Other.Freqs[OtherNode.Index];
+        if (Freq.Integer != OtherFreq.Integer) {
+          Match = false;
+          dbgs() << "Freq mismatch: " << bfi_detail::getBlockName(BB) << " "
+                 << Freq.Integer << " vs " << OtherFreq.Integer << "\n";
+        }
+      } else {
+        Match = false;
+        dbgs() << "Block " << bfi_detail::getBlockName(BB) << " index "
+               << Node.Index << " does not exist in Other.\n";
+      }
+    }
+    // Look for a valid node in OtherValidNodes that's not in ValidNodes.
+    for (auto &Entry : OtherValidNodes) {
+      const BlockT *OtherBB = Entry.first;
+      BlockNode OtherNode = Entry.second;
+      if (!ValidNodes.count(OtherBB)) {
+        Match = false;
+        dbgs() << "Block " << bfi_detail::getBlockName(OtherBB) << " index "
+               << OtherNode.Index << " does not exist in this.\n";
+      }
+    }
+  }
+  if (!Match) {
+    dbgs() << "This\n";
+    print(dbgs());
+    dbgs() << "Other\n";
+    Other.print(dbgs());
+  }
+  assert(Match && "BFI mismatch");
+}
+
 // Graph trait base class for block frequency information graph
 // viewer.
 
 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count };
 
 template <class BlockFrequencyInfoT, class BranchProbabilityInfoT>
 struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits {
   using GTraits = GraphTraits<BlockFrequencyInfoT *>;

llvm/lib/Analysis/BlockFrequencyInfo.cpp

 //===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 
 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
 
 void BlockFrequencyInfo::print(raw_ostream &OS) const {
   if (BFI)
     BFI->print(OS);
 }
 
+void BlockFrequencyInfo::verifyMatch(BlockFrequencyInfo &Other) const {
+  if (BFI)
+    BFI->verifyMatch(*Other.BFI);
+}
+
 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
                       "Block Frequency Analysis", true, true)
 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
                     "Block Frequency Analysis", true, true)
 
 char BlockFrequencyInfoWrapperPass::ID = 0;

llvm/lib/CodeGen/CodeGenPrepare.cpp

 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
static cl::opt<bool>
     EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden,
                          cl::init(true),
                          cl::desc("Enable splitting large offset of GEP."));
 
 static cl::opt<bool> EnableICMP_EQToICMP_ST(
     "cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false),
     cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
 
+static cl::opt<bool>
+    VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false),
+                     cl::desc("Enable BFI update verification for "
+                              "CodeGenPrepare."));
+
 namespace {
 
 enum ExtType {
   ZeroExtension,   // Zero extension has been seen.
   SignExtension,   // Sign extension has been seen.
   BothExtension    // This extension type is used if we saw sext after
                    // ZeroExtension had been set, or if we saw zext after
                    // SignExtension had been set. It makes the type
private:
 
     bool tryToSinkFreeOperands(Instruction *I);
     bool replaceMathCmpWithIntrinsic(BinaryOperator *BO, Value *Arg0,
                                      Value *Arg1, CmpInst *Cmp,
                                      Intrinsic::ID IID);
     bool optimizeCmp(CmpInst *Cmp, bool &ModifiedDT);
     bool combineToUSubWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
     bool combineToUAddWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
+    void verifyBFIUpdates(Function &F);
   };
 
 } // end anonymous namespace
 
 char CodeGenPrepare::ID = 0;
 
 INITIALIZE_PASS_BEGIN(CodeGenPrepare, DEBUG_TYPE,
                       "Optimize for code generation", false, false)
if (!DisableGCOpts) {
     for (auto &I : Statepoints)
       EverMadeChange |= simplifyOffsetableRelocate(*I);
   }
 
   // Do this last to clean up use-before-def scenarios introduced by other
   // preparatory transforms.
   EverMadeChange |= placeDbgValues(F);
 
+#ifndef NDEBUG
+  if (VerifyBFIUpdates)
+    verifyBFIUpdates(F);
+#endif
+
   return EverMadeChange;
 }
 
+// Verify BFI has been updated correctly by recomputing BFI and comparing them.
+void CodeGenPrepare::verifyBFIUpdates(Function &F) {
+  DominatorTree NewDT(F);
+  LoopInfo NewLI(NewDT);
+  BranchProbabilityInfo NewBPI(F, NewLI, TLInfo);
+  BlockFrequencyInfo NewBFI(F, NewBPI, NewLI);
+  NewBFI.verifyMatch(*BFI);
+}
+
 /// Merge basic blocks which are connected by a single edge, where one of the
 /// basic blocks has a single successor pointing to the other basic block,
 /// which has a single predecessor.
 bool CodeGenPrepare::eliminateFallThrough(Function &F) {
   bool Changed = false;
   // Scan all of the blocks in the function, except for the entry block.
   // Use a temporary array to avoid iterator being invalidated when
   // deleting blocks.
for (auto const &TailCallBB : TailCallBBs) {
     // Make sure the call instruction is followed by an unconditional branch to
     // the return block.
     BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
       continue;
 
     // Duplicate the return into TailCallBB.
     (void)FoldReturnIntoUncondBranch(RetI, BB, TailCallBB);
+    assert(!VerifyBFIUpdates ||
+           BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
+    BFI->setBlockFreq(
+        BB,
+        (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)).getFrequency());
     ModifiedDT = Changed = true;
     ++NumRetsDup;
   }
 
   // If we eliminated all predecessors of the block, delete the block now.
   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
     BB->eraseFromParent();
 

llvm/test/CodeGen/AArch64/aarch64-tbz.ll

 ; RUN: llc -verify-machineinstrs -mtriple=aarch64-linux-gnueabi < %s | FileCheck %s
+; RUN: llc -verify-machineinstrs -mtriple=aarch64-linux-gnueabi -cgp-verify-bfi-updates=true < %s | FileCheck %s
 
 ; CHECK-LABEL: test1
 ; CHECK: tbz {{w[0-9]}}, #3, {{.LBB0_3}}
 ; CHECK: tbz w[[REG1:[0-9]+]], #2, {{.LBB0_3}}
 ; CHECK-NOT: and [[REG2:x[0-9]+]], x[[REG1]], #0x4
 ; CHECK-NOT: cbz [[REG2]], {{.LBB0_3}}
 
 ; CHECK: b