[IR] Add per-function numbers to basic blocks (#101052)

Every basic block that is linked into a function now has a unique
number, which can be queried using getNumber(). Numbers are densely
allocated, but not re-assigned on block removal for stability. Block
numbers are intended to be fairly stable and only be updated when
removing a several basic blocks to make sure the numbering doesn't
become too sparse.

To reduce holes in the numbering, renumberBlocks() can be called to
re-assign numbers in block order.

Additionally, getMaxBlockNumber() returns a value larger than the
largest block number, intended to pre-allocate/resize vectors.

Furthermore, this introduces the concept of a "block number epoch" --
an integer that changes after every renumbering. This is useful for
identifying use of block numbers after renumbering: on initialization,
the current epoch is stored, and on all subsequent accesses, equality
with the current epoch can be asserted.

I added a validate method to catch cases where something goes wrong,
even if I can't really imagine how invalid numbers can occur. But I
think it's better to be safe and rule out this potential source of bugs
when more things depend on the numbering.

Previous discussion in:
https://discourse.llvm.org/t/rfc-add-auxiliary-field-for-per-pass-custom-data-to-basicblock/80229

1 files changed, 24 insertions, 0 deletions

diff --git a/llvm/lib/IR/Function.cpp b/llvm/lib/IR/Function.cpp
index 9b0dd5f..69520fd 100644
--- a/llvm/lib/IR/Function.cpp
+++ b/llvm/lib/IR/Function.cpp
@@ -13,6 +13,7 @@
 #include "llvm/IR/Function.h"
 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
@@ -85,6 +86,27 @@ static cl::opt<int> NonGlobalValueMaxNameSize(
 
 extern cl::opt<bool> UseNewDbgInfoFormat;
 
+void Function::renumberBlocks() {
+  validateBlockNumbers();
+
+  NextBlockNum = 0;
+  for (auto &BB : *this)
+    BB.Number = NextBlockNum++;
+  BlockNumEpoch++;
+}
+
+void Function::validateBlockNumbers() const {
+#ifndef NDEBUG
+  BitVector Numbers(NextBlockNum);
+  for (const auto &BB : *this) {
+    unsigned Num = BB.getNumber();
+    assert(Num < NextBlockNum && "out of range block number");
+    assert(!Numbers[Num] && "duplicate block numbers");
+    Numbers.set(Num);
+  }
+#endif
+}
+
 void Function::convertToNewDbgValues() {
   IsNewDbgInfoFormat = true;
   for (auto &BB : *this) {
@@ -509,6 +531,8 @@ Function::Function(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace,
 }
 
 Function::~Function() {
+  validateBlockNumbers();
+
   dropAllReferences();    // After this it is safe to delete instructions.
 
   // Delete all of the method arguments and unlink from symbol table...