[BFI] Use CallbackVH to notify BFI about deletion of basic blocks

[DaniilSuchkov]

Summary

With AssertingVHs instead of bare pointers in BlockFrequencyInfoImpl::Nodes (but without CallbackVHs) ~1/36 of all tests ran by make check fail (in my setup it's 1042 out of 36257). It means that there are users of BFI that delete basic blocks while keeping BFI. Some of those transformations add new basic blocks, so if a new basic block happens to be allocated at address where an already deleted block was and we don't explicitly set block frequency for that new block, BFI will report some non-default frequency for the block even though frequency for the block was never set. Inliner is an example of a transformation that adds and removes BBs while querying and updating BFI, however I can't provide a test case that would show non-deterministic inlining caused by this issue.

[asbirlea]

Just a quick comment, that IMO this is a great patch to have, even without an actual test showing the non-determinism.
We've seen issues like this with BFI between passes, and I tried to prevent using a cached BFI due to precisely the problem you describe.
I did not however handle the situation of BFI being invalidated by a pass and used by the same pass.
I'm sorry I don't have a good suggestion for your const_cast question.

The changes lgtm, but I'd let the other reviewers chime in too.

[fhahn]

Alternatively I think it would be reasonable to expect the passes claiming to preserve BFI to notify BFI about deleted/added blocks, like we do for many other analysis. Do you have any idea of how much effort that would take?

[davidxl]

Can you make BlockKeyT to be AssertingVH<const BasicBlock> to avoid the const castings?

[DaniilSuchkov]

In D75341#1898925, @davidxl wrote:

Can you make BlockKeyT to be AssertingVH<const BasicBlock> to avoid the const castings?

Sadly, ValueHandles don't work with non-const pointers.

[davidxl]

Do you mean it does not work well for const pointers? There are existing uses of AssertingVH<const BasicBlock> or AssertingVH<const Value>?

[DaniilSuchkov]

In D75341#1898807, @fhahn wrote:

Alternatively I think it would be reasonable to expect the passes claiming to preserve BFI to notify BFI about deleted/added blocks, like we do for many other analysis. Do you have any idea of how much effort that would take?

Yeah, I considered this option but I don't think it's any better.
First, even with that approach we'll still need AssertingVHs in order to verify that we didn't miss any updates, and given that most of ugly const_casts are required by AssertingVH, it's not much of an improvement.
UPD: First, given that const_casts aren't an issue, I don't see any benefits of manual updates.

Second, CallbackVHs "automatically" notify BFI about changes, so they solve this part of the issue once and for all, while with manual notifications it'll be a classic whack-a-mole kind of effort, we'll be fixing AssertingVH's crashes on regular basis (maybe not too often though).
Third, it requires considerable amount of pretty intrusive changes, even more than providing BFI with non-const Functions/BasicBlocks does.

[DaniilSuchkov]

In D75341#1899307, @davidxl wrote:

Do you mean it does not work well for const pointers? There are existing uses of AssertingVH<const BasicBlock> or AssertingVH<const Value>?

Actually you're right, thank you!
It didn't cross my mind that someone could've already included const_casts into AssertingVH itself, so that unlike other ValueHandles it accepts const pointers.

[DaniilSuchkov]

One thing I don't understand is why three out of four kinds of VHs perform the const_cast, not the ValueHandleBase. I think it's time to change that (and by doing so, allow CallbackVH accept const pointers too).
Given that three out of four VH kinds already perform const_cast inside, I think it makes sense to add one to CallbackVH too.

[DaniilSuchkov]

Got rid of all const_casts except one, which was moved into CallbackVH's constructor.

[davidxl]

This looks good, but it does have implications on memory consumption for BFI. To avoid that, gate the data structure change on #ifndef NDEBUG.

[DaniilSuchkov]

In D75341#1903988, @davidxl wrote:

This looks good, but it does have implications on memory consumption for BFI. To avoid that, gate the data structure change on #ifndef NDEBUG.

I understand that, but I don't think we can do anything about it. You see, AssertingVH already gates itself in a way that turns it into a pointer wrapper in Release configuration and BFICallbackVH is always required for correctness, since it updates BFI.
Or am I missing something?

[davidxl]

The value field of the NodesMap now becomes a pair unconditionally -- which is unnecessary for nonAsserting Build.

[DaniilSuchkov]

You mean we don't need to update BFI in non-asserting mode? It's not just for verification, it's required for correctness.

[davidxl]

I think we should explicitly fix the real problems that new blocks are not updated frequency information instead of just letting them get a known default value. Doing it later can make it harder to find those problems, right?

[DaniilSuchkov]

In D75341#1904797, @davidxl wrote:

I think we should explicitly fix the real problems that new blocks are not updated frequency information instead of just letting them get a known default value. Doing it later can make it harder to find those problems, right?

Cases when we don't properly set frequencies are inefficiencies, which are unfortunate, but they aren't critical, to catch them there is already a CheckBFIUnknownBlockQueries option. This patch, on the other hand, not about mere inefficiencies, it's about non-deterministic behavior of compiler, which is a pretty nasty thing, I find even possibility of this happening a real problem. What I here propose would protect us from such issues and it won't cover cases CheckBFIUnknownBlockQueries is made to detect, so it won't make finding such cases any harder.

[DaniilSuchkov]

Actually, this change will even help CheckBFIUnknownBlockQueries: since every missed update will result in a missing NodesMap entry, without exclusion of cases when new BB happens to be in the same address where some old BB was.

[davidxl]

lgtm

[hjyamauchi]

Sorry for not noticing this patch sooner. I think this helps bring some more sanity in the BFI staleness issue. LGTM.

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/BlockFrequency.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/ScaledNumber.h"
public:
   }
 };
 
 namespace bfi_detail {
 
 template <class BlockT> struct TypeMap {};
 template <> struct TypeMap<BasicBlock> {
   using BlockT = BasicBlock;
+  using BlockKeyT = AssertingVH<const BasicBlock>;
   using FunctionT = Function;
   using BranchProbabilityInfoT = BranchProbabilityInfo;
   using LoopT = Loop;
   using LoopInfoT = LoopInfo;
 };
 template <> struct TypeMap<MachineBasicBlock> {
   using BlockT = MachineBasicBlock;
+  using BlockKeyT = const MachineBasicBlock *;
   using FunctionT = MachineFunction;
   using BranchProbabilityInfoT = MachineBranchProbabilityInfo;
   using LoopT = MachineLoop;
   using LoopInfoT = MachineLoopInfo;
 };
 
 /// Get the name of a MachineBasicBlock.
 ///

 ///         used for computing loop scale) is the sum of all iterations.
 ///         (Running this until fixed point would "solve" the geometric
 ///         series by simulation.)
 template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase {
   // This is part of a workaround for a GCC 4.7 crash on lambdas.
   friend struct bfi_detail::BlockEdgesAdder<BT>;
 
   using BlockT = typename bfi_detail::TypeMap<BT>::BlockT;
+  using BlockKeyT = typename bfi_detail::TypeMap<BT>::BlockKeyT;
   using FunctionT = typename bfi_detail::TypeMap<BT>::FunctionT;
   using BranchProbabilityInfoT =
       typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT;
   using LoopT = typename bfi_detail::TypeMap<BT>::LoopT;
   using LoopInfoT = typename bfi_detail::TypeMap<BT>::LoopInfoT;
   using Successor = GraphTraits<const BlockT *>;
   using Predecessor = GraphTraits<Inverse<const BlockT *>>;
 
   const BranchProbabilityInfoT *BPI = nullptr;
   const LoopInfoT *LI = nullptr;
   const FunctionT *F = nullptr;
 
+  class BFICallbackVH;
+
   // All blocks in reverse postorder.
   std::vector<const BlockT *> RPOT;
-  DenseMap<const BlockT *, BlockNode> Nodes;
+  DenseMap<BlockKeyT, std::pair<BlockNode, BFICallbackVH>> Nodes;
 
   using rpot_iterator = typename std::vector<const BlockT *>::const_iterator;
 
   rpot_iterator rpot_begin() const { return RPOT.begin(); }
   rpot_iterator rpot_end() const { return RPOT.end(); }
 
   size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); }
 
   BlockNode getNode(const rpot_iterator &I) const {
     return BlockNode(getIndex(I));
   }
-  BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB); }
+
+  BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB).first; }
 
   const BlockT *getBlock(const BlockNode &Node) const {
     assert(Node.Index < RPOT.size());
     return RPOT[Node.Index];
   }
 
   /// Run (and save) a post-order traversal.
   ///
public:
   }
 
   bool isIrrLoopHeader(const BlockT *BB) {
     return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB));
   }
 
   void setBlockFreq(const BlockT *BB, uint64_t Freq);
 
+  void forgetBlock(const BlockT *BB) {
+    // We don't erase corresponding items from `Freqs`, `RPOT` and other to
+    // avoid invalidating indices. Doing so would have saved some memory, but
+    // it's not worth it.
+    Nodes.erase(BB);
+  }
+
   Scaled64 getFloatingBlockFreq(const BlockT *BB) const {
     return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB));
   }
 
   const BranchProbabilityInfoT &getBPI() const { return *BPI; }
 
   /// Print the frequencies for the current function.
   ///
public:
   using BlockFrequencyInfoImplBase::dump;
   using BlockFrequencyInfoImplBase::printBlockFreq;
 
   raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const {
     return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB));
   }
 };
 
+template <>
+class BlockFrequencyInfoImpl<BasicBlock>::BFICallbackVH : public CallbackVH {
+  BlockFrequencyInfoImpl *BFIImpl;
+
+public:
+  BFICallbackVH() = default;
+
+  BFICallbackVH(const BasicBlock *BB, BlockFrequencyInfoImpl *BFIImpl)
+    : CallbackVH(BB), BFIImpl(BFIImpl) {}
+
+  void deleted() override {
+    BFIImpl->forgetBlock(cast<BasicBlock>(getValPtr()));
+  }
+};
+
+/// Dummy implementation since MachineBasicBlocks aren't Values, so ValueHandles
+/// don't apply to them.
+template <>
+class BlockFrequencyInfoImpl<MachineBasicBlock>::BFICallbackVH {
+public:
+  BFICallbackVH() = default;
+  BFICallbackVH(const MachineBasicBlock *, BlockFrequencyInfoImpl *) {}
+};
+
 template <class BT>
 void BlockFrequencyInfoImpl<BT>::calculate(const FunctionT &F,
                                            const BranchProbabilityInfoT &BPI,
                                            const LoopInfoT &LI) {
   // Save the parameters.
   this->BPI = &BPI;
   this->LI = &LI;
   this->F = &F;

 void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, uint64_t Freq) {
   if (Nodes.count(BB))
     BlockFrequencyInfoImplBase::setBlockFreq(getNode(BB), Freq);
   else {
     // If BB is a newly added block after BFI is done, we need to create a new
     // BlockNode for it assigned with a new index. The index can be determined
     // by the size of Freqs.
     BlockNode NewNode(Freqs.size());
-    Nodes[BB] = NewNode;
+    Nodes[BB] = {NewNode, BFICallbackVH(BB, this)};
     Freqs.emplace_back();
     BlockFrequencyInfoImplBase::setBlockFreq(NewNode, Freq);
   }
 }
 
 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() {
   const BlockT *Entry = &F->front();
   RPOT.reserve(F->size());
   std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
   std::reverse(RPOT.begin(), RPOT.end());
 
   assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
          "More nodes in function than Block Frequency Info supports");
 
   LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
   for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
     BlockNode Node = getNode(I);
     LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node)
                       << "\n");
-    Nodes[*I] = Node;
+    Nodes[*I] = {Node, BFICallbackVH(*I, this)};
   }
 
   Working.reserve(RPOT.size());
   for (size_t Index = 0; Index < RPOT.size(); ++Index)
     Working.emplace_back(Index);
   Freqs.resize(RPOT.size());
 }
 

llvm/include/llvm/IR/ValueHandle.h

protected:
 
   void setValPtr(Value *P) {
     ValueHandleBase::operator=(P);
   }
 
 public:
   CallbackVH() : ValueHandleBase(Callback) {}
   CallbackVH(Value *P) : ValueHandleBase(Callback, P) {}
+  CallbackVH(const Value *P) : CallbackVH(const_cast<Value *>(P)) {}
 
   operator Value*() const {
     return getValPtr();
   }
 
   /// Callback for Value destruction.
   ///
   /// Called when this->getValPtr() is destroyed, inside ~Value(), so you