From 8975aa6ea8172963d6532caa8ed2a6f6e0074a02 Mon Sep 17 00:00:00 2001 From: Daniil Suchkov Date: Thu, 5 Mar 2020 18:32:50 +0700 Subject: [PATCH] [BFI] Use CallbackVH to notify BFI about deletion of basic blocks With AssertingVHs instead of bare pointers in BlockFrequencyInfoImpl::Nodes (but without CallbackVHs) ~1/36 of all tests ran by make check fail. 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. With this patch, thanks to updates via CallbackVH, BFI won't keep stale pointers in its Nodes map. This is a resubmission of 408349a25d0f5a012003f84c95b49bcc7782fa70 with fixed MSVC compilation errors. Reviewers: davidxl, yamauchi, asbirlea, fhahn, fedor.sergeev Reviewed-By: asbirlea, davidxl Tags: #llvm Differential Revision: https://reviews.llvm.org/D75341 --- .../include/llvm/Analysis/BlockFrequencyInfoImpl.h | 48 ++++++++++++++++++++-- llvm/include/llvm/IR/ValueHandle.h | 1 + 2 files changed, 45 insertions(+), 4 deletions(-) diff --git a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 4d80591..2a81306 100644 --- a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -24,6 +24,7 @@ #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" @@ -547,6 +548,7 @@ namespace bfi_detail { template struct TypeMap {}; template <> struct TypeMap { using BlockT = BasicBlock; + using BlockKeyT = AssertingVH; using FunctionT = Function; using BranchProbabilityInfoT = BranchProbabilityInfo; using LoopT = Loop; @@ -554,6 +556,7 @@ template <> struct TypeMap { }; template <> struct TypeMap { using BlockT = MachineBasicBlock; + using BlockKeyT = const MachineBasicBlock *; using FunctionT = MachineFunction; using BranchProbabilityInfoT = MachineBranchProbabilityInfo; using LoopT = MachineLoop; @@ -845,6 +848,7 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { friend struct bfi_detail::BlockEdgesAdder; using BlockT = typename bfi_detail::TypeMap::BlockT; + using BlockKeyT = typename bfi_detail::TypeMap::BlockKeyT; using FunctionT = typename bfi_detail::TypeMap::FunctionT; using BranchProbabilityInfoT = typename bfi_detail::TypeMap::BranchProbabilityInfoT; @@ -857,9 +861,11 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { const LoopInfoT *LI = nullptr; const FunctionT *F = nullptr; + class BFICallbackVH; + // All blocks in reverse postorder. std::vector RPOT; - DenseMap Nodes; + DenseMap> Nodes; using rpot_iterator = typename std::vector::const_iterator; @@ -871,7 +877,8 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { 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()); @@ -992,6 +999,13 @@ public: 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)); } @@ -1019,6 +1033,32 @@ public: } }; +template <> +class BlockFrequencyInfoImpl::BFICallbackVH : public CallbackVH { + BlockFrequencyInfoImpl *BFIImpl; + +public: + BFICallbackVH() = default; + + BFICallbackVH(const BasicBlock *BB, + BlockFrequencyInfoImpl *BFIImpl) + : CallbackVH(BB), BFIImpl(BFIImpl) {} + + void deleted() override { + BFIImpl->forgetBlock(cast(getValPtr())); + } +}; + +/// Dummy implementation since MachineBasicBlocks aren't Values, so ValueHandles +/// don't apply to them. +template <> +class BlockFrequencyInfoImpl::BFICallbackVH { +public: + BFICallbackVH() = default; + BFICallbackVH(const MachineBasicBlock *, + BlockFrequencyInfoImpl *) {} +}; + template void BlockFrequencyInfoImpl::calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, @@ -1066,7 +1106,7 @@ void BlockFrequencyInfoImpl::setBlockFreq(const BlockT *BB, uint64_t Freq) { // 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); } @@ -1086,7 +1126,7 @@ template void BlockFrequencyInfoImpl::initializeRPOT() { 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()); diff --git a/llvm/include/llvm/IR/ValueHandle.h b/llvm/include/llvm/IR/ValueHandle.h index a21d017..81438c6 100644 --- a/llvm/include/llvm/IR/ValueHandle.h +++ b/llvm/include/llvm/IR/ValueHandle.h @@ -414,6 +414,7 @@ protected: public: CallbackVH() : ValueHandleBase(Callback) {} CallbackVH(Value *P) : ValueHandleBase(Callback, P) {} + CallbackVH(const Value *P) : CallbackVH(const_cast(P)) {} operator Value*() const { return getValPtr(); -- 2.7.4