Provide a method for generating deterministic IDs for pointers allocated in BumpPtrAllocator

[george.karpenkov]

Summary

There are many "dumping" actions available from the compiler: Clang dumps AST, Clang static analyzer dumps generated nodes in the "exploded graph" it generates.

However, in many of those dumps raw pointer values are printed for the objects of interest, which can considerably complicate debugging due to those values being non-reproducible.
This patch adds a method for converting a pointer generated through an allocator to a deterministic (up to an architecture) long, which can make the debugging experience much more pleasant.
(E.g. compare hunting for a value "0xa9273f732" which changes every run to hunting for "23432").

Discussion started at http://lists.llvm.org/pipermail/cfe-dev/2018-August/059178.html

Code in collaboration with @NoQ

[aprantl]

llvm/include/llvm/Support/Allocator.h

292

clang-format?

295

return {Idx, P - S};

[aprantl]

Just for consideration: The raw pointers in dumps are sometimes useful while in a debugger session, because you can cast a pointer and dump the object in the debugger.

[NoQ]

In D51393#1217644, @aprantl wrote:

Just for consideration: The raw pointers in dumps are sometimes useful while in a debugger session, because you can cast a pointer and dump the object in the debugger.

Yup, i use that as well from time to time, so i guess we can either dump both or make a flag.

llvm/include/llvm/Support/Allocator.h

290

I'd much rather have the first element signed, because it's the only one that can actually carry "negative" values. Maybe just let's do two int64_ts or intptr_ts?

295

And, well, let's make integral casts explicit here.

[george.karpenkov]

In fact, generating a single "long" seems even better.

[NoQ]

In D51393#1218544, @george.karpenkov wrote:

In fact, generating a single "long" seems even better.

ptrdiff_t seems to express what we're trying to say pretty accurately.

[NoQ]

llvm/include/llvm/Support/Allocator.h

304

We should start with -1 because otherwise the first standard-slab object and the first custom-slab object would both have id 0.

[xbolva00]

llvm/include/llvm/Support/Allocator.h

295

for (size_t Idx = 0, e = Slabs.size(); Idx < e; Idx++) {

[george.karpenkov]

More casts.

[NoQ]

I'm happy with the code.

llvm/include/llvm/Support/Allocator.h

298

Two spaces here.

llvm/include/llvm/Support/Allocator.h

 /// type. These overloads are typically provided by a base class template \c
 /// AllocatorBase.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_ALLOCATOR_H
 #define LLVM_SUPPORT_ALLOCATOR_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MemAlloc.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
void Deallocate(const void *Ptr, size_t Size) {
     __asan_poison_memory_region(Ptr, Size);
   }
 
   // Pull in base class overloads.
   using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
 
   size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }
 
+  /// \return An index uniquely and reproducibly identifying
+  /// an input pointer \p Ptr in the given allocator.
+  /// The returned value is negative iff the object is inside a custom-size
+  /// slab.
+  /// Returns an empty optional if the pointer is not found in the allocator.
+  llvm::Optional<int64_t> identifyObject(const void *Ptr) {
+    const char *P = static_cast<const char *>(Ptr);
+    int64_t InSlabIdx = 0;
+    for (size_t Idx = 0, E = Slabs.size(); Idx < E; Idx++) {
+      const char *S = static_cast<const char *>(Slabs[Idx]);
+      if (P >= S && P < S + computeSlabSize(Idx))
+        return InSlabIdx +  static_cast<int64_t>(P - S);
+      InSlabIdx += static_cast<int64_t>(computeSlabSize(Idx));
+    }
+
+    // Use negative index to denote custom sized slabs.
+    int64_t InCustomSizedSlabIdx = -1;
+    for (size_t Idx = 0, E = CustomSizedSlabs.size(); Idx < E; Idx++) {
+      const char *S = static_cast<const char *>(CustomSizedSlabs[Idx].first);
+      size_t Size = CustomSizedSlabs[Idx].second;
+      if (P >= S && P < S + Size)
+        return InCustomSizedSlabIdx - static_cast<int64_t>(P - S);
+      InCustomSizedSlabIdx -= static_cast<int64_t>(Size);
+    }
+    return None;
+  }
+
   size_t getTotalMemory() const {
     size_t TotalMemory = 0;
     for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I)
       TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I));
     for (auto &PtrAndSize : CustomSizedSlabs)
       TotalMemory += PtrAndSize.second;
     return TotalMemory;
   }