[NFC] Remove waymarking because it improves performances

[Tyker]

Summary

This patch remove waymarking and replaces it with storing a pointer to the User in the Use.
here are the results on the measurements for the CTMark tests of the test suite.

Metric: instructions_count

Program                                                      baseline      patched       diff 
 test-suite :: CTMark/ClamAV/clamscan.test                    72557942065   71733653521  -1.1%
 test-suite :: CTMark/sqlite3/sqlite3.test                    76281422939   75484840636  -1.0%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test  51364676366   50862185614  -1.0%
 test-suite :: CTMark/SPASS/SPASS.test                        60476106505   59908437767  -0.9%
 test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test              112578442329  111725050856 -0.8%
 test-suite :: CTMark/mafft/pairlocalalign.test               50846133013   50473644539  -0.7%
 test-suite :: CTMark/kimwitu++/kc.test                       54692641250   54349070299  -0.6%
 test-suite :: CTMark/7zip/7zip-benchmark.test                182216614747  181216091230 -0.5%
 test-suite :: CTMark/Bullet/bullet.test                      123459210616  122905866767 -0.4%
 Geomean difference                                                                      -0.8%

Metric: peak_memory_use

Program                                                      baseline  patched   diff 
 test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test              326864    338524    3.6%
 test-suite :: CTMark/sqlite3/sqlite3.test                    216412    221240    2.2%
 test-suite :: CTMark/7zip/7zip-benchmark.test                11808284  12022604  1.8%
 test-suite :: CTMark/Bullet/bullet.test                      6831752   6945988   1.7%
 test-suite :: CTMark/SPASS/SPASS.test                        2682552   2721820   1.5%
 test-suite :: CTMark/ClamAV/clamscan.test                    5037256   5107936   1.4%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test  2752728   2790768   1.4%
 test-suite :: CTMark/mafft/pairlocalalign.test               1517676   1537244   1.3%
 test-suite :: CTMark/kimwitu++/kc.test                       1090748   1103448   1.2%
 Geomean difference                                                               1.8%

Metric: compile_time

Program                                                      baseline patched diff 
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test  14.71    14.38  -2.2%
 test-suite :: CTMark/sqlite3/sqlite3.test                    23.18    22.73  -2.0%
 test-suite :: CTMark/7zip/7zip-benchmark.test                57.96    56.99  -1.7%
 test-suite :: CTMark/ClamAV/clamscan.test                    20.75    20.49  -1.2%
 test-suite :: CTMark/kimwitu++/kc.test                       18.35    18.15  -1.1%
 test-suite :: CTMark/SPASS/SPASS.test                        18.72    18.57  -0.8%
 test-suite :: CTMark/mafft/pairlocalalign.test               14.09    14.00  -0.6%
 test-suite :: CTMark/Bullet/bullet.test                      37.38    37.19  -0.5%
 test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test              33.81    33.76  -0.2%
 Geomean difference                                                           -1.1%

i believe that it is worth trading +1.8% peak memory use for -1.1% compile time.
also this patch removes waymarking which simplifies the Use and User classes.

[lebedev.ri]

Why did instructions_count metric change?

[Tyker]

In D77144#1952618, @lebedev.ri wrote:

Why did instructions_count metric change?

the instructions_count metric is the number of instruction the compiler executed when building the code not the number of instruction in the resulting binary.
i added it because it is usually close to compile time but has less noise.

[nikic]

I also ran the numbers, results are pretty similar to what you're seeing: instructions, max-rss.

I suspect that we might not be seeing the whole picture here though. I couldn't find the original discussion on this, but https://github.com/ggreif/EuroLLVM-Waymarking mentions that at the time it was introduced, waymarking was a 2.5% compile-time regression, but saved 12% memory on some large C++ workloads. We're clearly not seeing anything close to a 12% memory regression here, but it's not clear whether that's because memory usage characteristics in LLVM changed significantly over the last 12 years (which doesn't seem unplausible), or whether waymarking needs heavier workloads to really shine.

[lattner]

Huh, interesting. I think that taking this could make a lot of sense, I like the simplicity and performance benefits. Could you please start a discussion about it on llvm-dev?

@ekatz and @rriddle it would be good for you two to be aware of this.

[ekatz]

Let me shed a little light on the Waymarking algorithm:

It all began with @ggreif, in 2008.
He proposed the the Waymarking as a solution in LLVM Data Structures, and Putting Use on Diet.

As a solution, he opened a branch called use-diet in the LLVM SVN repository, which was merged in rL50943 : rGf6caff66a1bf.

According to the his blog, in http://heisenbug.blogspot.com/2008/05/merged.html; I quote:
"... the SPEC benchmark 447.dealII had a 13% reduced memory footprint ..."
and
"... observed slight speedup on kimwitu++ benchmark's compilation time."

In addition, according to @lattner's response in https://lists.llvm.org/pipermail/llvm-dev/2008-April/014151.html, the Waymarking seems to go up to even 15% improvement in memory usage.

Regarding the removal of the Waymarking, don't get me wrong, I am all in for its simplicity, and performance improvements, but I'm afraid more investigation needs to be done.
Please try to test using the benchmarks mentioned above, and maybe even larger workloads (like the linux kernel, if you can; and I know, at least it part, if not in full, the AOSP is using clang).

[foad]

I like this. It's a bit sad that waymarking isn't paying for itself, but if it's not then it should definitely go.

llvm/include/llvm/IR/Use.h

71

Maybe name the argument Parent instead of U? Does it actually need a default of nullptr?

llvm/lib/IR/User.cpp

46–47

Comment needs updating :-)

[foad]

In D77144#1953469, @nikic wrote:

[...] at the time it was introduced, waymarking was a 2.5% compile-time regression, but saved 12% memory on some large C++ workloads. We're clearly not seeing anything close to a 12% memory regression here, but it's not clear whether that's because memory usage characteristics in LLVM changed significantly over the last 12 years (which doesn't seem unplausible) [...]

Can we easily collect statistics on how much memory is allocated for what kind of objects? E.g. how much of the peak usage is Uses, how much is Instructions, how much is BasicBlocks and so on?

[Tyker]

In D77144#1954171, @ekatz wrote:

Let me shed a little light on the Waymarking algorithm:

thanks for the insight

According to the his blog, in http://heisenbug.blogspot.com/2008/05/merged.html; I quote:
"... the SPEC benchmark 447.dealII had a 13% reduced memory footprint ..."

i don't have access to SPEC since it isn't open source.

and
"... observed slight speedup on kimwitu++ benchmark's compilation time."

from my an nikic's measurement this is not true anymore.

Regarding the removal of the Waymarking, don't get me wrong, I am all in for its simplicity, and performance improvements, but I'm afraid more investigation needs to be done.
Please try to test using the benchmarks mentioned above, and maybe even larger workloads (like the linux kernel, if you can; and I know, at least it part, if not in full, the AOSP is using clang).

i ran a build of clang while tracking max memory use of every translation units (2687).
the highest max memory use difference i saw was +7.27% on llvm/lib/DebugInfo/CodeView/EnumTables.cpp.
but it is a outlier since the the second highest was at +1.80% and there are 7 other TU above 1.5%
the average over all TU was a +0.25%.
i didn't measure compile-time during this build because it measuring it accurately would have taken a very long time.

In D77144#1956725, @foad wrote:

In D77144#1953469, @nikic wrote:

[...] at the time it was introduced, waymarking was a 2.5% compile-time regression, but saved 12% memory on some large C++ workloads. We're clearly not seeing anything close to a 12% memory regression here, but it's not clear whether that's because memory usage characteristics in LLVM changed significantly over the last 12 years (which doesn't seem unplausible) [...]

Can we easily collect statistics on how much memory is allocated for what kind of objects? E.g. how much of the peak usage is Uses, how much is Instructions, how much is BasicBlocks and so on?

since allocation of Use is grouped with the User (and all derived classes of User) i don't think a tool could figure it out.
we could easily instrument manually every allocation of a Use to see the difference in allocation size but this wouldn't give us the difference at its peak.

[Tyker]

fixed comments

[ekatz]

"llvm/docs/ProgrammersManual.rst" needs to be updated as well.

[Tyker]

adapt ProgrammersManual
remove some waymarking specific comments.

[Tyker]

ping

[lattner]

Sorry, I thought this was approved on llvm-dev. Looks good, thank you for simplifying the compiler!

llvm/include/llvm/Analysis/MemorySSA.h

public:
   }
 
   // Block iterator interface. This provides access to the list of incoming
   // basic blocks, which parallels the list of incoming values.
   using block_iterator = BasicBlock **;
   using const_block_iterator = BasicBlock *const *;
 
   block_iterator block_begin() {
-    auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace);
-    return reinterpret_cast<block_iterator>(Ref + 1);
+    return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
   }
 
   const_block_iterator block_begin() const {
-    const auto *Ref =
-        reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace);
-    return reinterpret_cast<const_block_iterator>(Ref + 1);
+    return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
   }
 
   block_iterator block_end() { return block_begin() + getNumOperands(); }
 
   const_block_iterator block_end() const {
     return block_begin() + getNumOperands();
   }
 

llvm/include/llvm/IR/Instructions.h

public:
 
   // Block iterator interface. This provides access to the list of incoming
   // basic blocks, which parallels the list of incoming values.
 
   using block_iterator = BasicBlock **;
   using const_block_iterator = BasicBlock * const *;
 
   block_iterator block_begin() {
-    Use::UserRef *ref =
-      reinterpret_cast<Use::UserRef*>(op_begin() + ReservedSpace);
-    return reinterpret_cast<block_iterator>(ref + 1);
+    return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
   }
 
   const_block_iterator block_begin() const {
-    const Use::UserRef *ref =
-      reinterpret_cast<const Use::UserRef*>(op_begin() + ReservedSpace);
-    return reinterpret_cast<const_block_iterator>(ref + 1);
+    return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
   }
 
   block_iterator block_end() {
     return block_begin() + getNumOperands();
   }
 
   const_block_iterator block_end() const {
     return block_begin() + getNumOperands();

llvm/include/llvm/IR/Use.h

 class Use {
 public:
   Use(const Use &U) = delete;
 
   /// Provide a fast substitute to std::swap<Use>
   /// that also works with less standard-compliant compilers
   void swap(Use &RHS);
 
-  /// Pointer traits for the UserRef PointerIntPair. This ensures we always
-  /// use the LSB regardless of pointer alignment on different targets.
-  struct UserRefPointerTraits {
-    static inline void *getAsVoidPointer(User *P) { return P; }
-
-    static inline User *getFromVoidPointer(void *P) {
-      return (User *)P;
-    }
-
-    static constexpr int NumLowBitsAvailable = 1;
-  };
-
-  // A type for the word following an array of hung-off Uses in memory, which is
-  // a pointer back to their User with the bottom bit set.
-  using UserRef = PointerIntPair<User *, 1, unsigned, UserRefPointerTraits>;
-
-  /// Pointer traits for the Prev PointerIntPair. This ensures we always use
-  /// the two LSBs regardless of pointer alignment on different targets.
-  struct PrevPointerTraits {
-    static inline void *getAsVoidPointer(Use **P) { return P; }
-
-    static inline Use **getFromVoidPointer(void *P) {
-      return (Use **)P;
-    }
-
-    static constexpr int NumLowBitsAvailable = 2;
-  };
-
 private:
   /// Destructor - Only for zap()
   ~Use() {
     if (Val)
       removeFromList();
   }
 
-  enum PrevPtrTag { zeroDigitTag, oneDigitTag, stopTag, fullStopTag };
-
   /// Constructor
-  Use(PrevPtrTag tag) { Prev.setInt(tag); }
+  Use(User *U = nullptr) : Parent(U) {}
 
 public:
   friend class Value;
+  friend class User;
 
   operator Value *() const { return Val; }
   Value *get() const { return Val; }
 
   /// Returns the User that contains this Use.
   ///
   /// For an instruction operand, for example, this will return the
   /// instruction.
-  User *getUser() const LLVM_READONLY;
+  User *getUser() const { return Parent; };
 
   inline void set(Value *Val);
 
   inline Value *operator=(Value *RHS);
   inline const Use &operator=(const Use &RHS);
 
   Value *operator->() { return Val; }
   const Value *operator->() const { return Val; }
 
   Use *getNext() const { return Next; }
 
   /// Return the operand # of this use in its User.
   unsigned getOperandNo() const;
 
-  /// Initializes the waymarking tags on an array of Uses.
-  ///
-  /// This sets up the array of Uses such that getUser() can find the User from
-  /// any of those Uses.
-  static Use *initTags(Use *Start, Use *Stop);
-
   /// Destroys Use operands when the number of operands of
   /// a User changes.
   static void zap(Use *Start, const Use *Stop, bool del = false);
 
 private:
-  const Use *getImpliedUser() const LLVM_READONLY;
 
   Value *Val = nullptr;
   Use *Next = nullptr;
-  PointerIntPair<Use **, 2, PrevPtrTag, PrevPointerTraits> Prev;
+  Use **Prev = nullptr;
+  User *Parent = nullptr;
 
-  void setPrev(Use **NewPrev) { Prev.setPointer(NewPrev); }
+  void setPrev(Use **NewPrev) { Prev = NewPrev; }
 
   void addToList(Use **List) {
     Next = *List;
     if (Next)
       Next->setPrev(&Next);
     setPrev(List);
     *List = this;
   }
 
   void removeFromList() {
-    Use **StrippedPrev = Prev.getPointer();
+    Use **StrippedPrev = Prev;
     *StrippedPrev = Next;
     if (Next)
       Next->setPrev(StrippedPrev);
   }
 };
 
 /// Allow clients to treat uses just like values when using
 /// casting operators.

llvm/lib/IR/Use.cpp

void Use::swap(Use &RHS) {
   if (OldVal) {
     RHS.Val = OldVal;
     RHS.Val->addUse(RHS);
   } else {
     RHS.Val = nullptr;
   }
 }
 
-User *Use::getUser() const {
-  const Use *End = getImpliedUser();
-  const UserRef *ref = reinterpret_cast<const UserRef *>(End);
-  return ref->getInt() ? ref->getPointer()
-                       : reinterpret_cast<User *>(const_cast<Use *>(End));
-}
-
 unsigned Use::getOperandNo() const {
   return this - getUser()->op_begin();
 }
 
-// Sets up the waymarking algorithm's tags for a series of Uses. See the
-// algorithm details here:
-//
-//   http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
-//
-Use *Use::initTags(Use *const Start, Use *Stop) {
-  ptrdiff_t Done = 0;
-  while (Done < 20) {
-    if (Start == Stop--)
-      return Start;
-    static const PrevPtrTag tags[20] = {
-        fullStopTag,  oneDigitTag,  stopTag,      oneDigitTag, oneDigitTag,
-        stopTag,      zeroDigitTag, oneDigitTag,  oneDigitTag, stopTag,
-        zeroDigitTag, oneDigitTag,  zeroDigitTag, oneDigitTag, stopTag,
-        oneDigitTag,  oneDigitTag,  oneDigitTag,  oneDigitTag, stopTag};
-    new (Stop) Use(tags[Done++]);
-  }
-
-  ptrdiff_t Count = Done;
-  while (Start != Stop) {
-    --Stop;
-    if (!Count) {
-      new (Stop) Use(stopTag);
-      ++Done;
-      Count = Done;
-    } else {
-      new (Stop) Use(PrevPtrTag(Count & 1));
-      Count >>= 1;
-      ++Done;
-    }
-  }
-
-  return Start;
-}
-
 void Use::zap(Use *Start, const Use *Stop, bool del) {
   while (Start != Stop)
     (--Stop)->~Use();
   if (del)
     ::operator delete(Start);
 }
 
-const Use *Use::getImpliedUser() const {
-  const Use *Current = this;
-
-  while (true) {
-    unsigned Tag = (Current++)->Prev.getInt();
-    switch (Tag) {
-    case zeroDigitTag:
-    case oneDigitTag:
-      continue;
-
-    case stopTag: {
-      ++Current;
-      ptrdiff_t Offset = 1;
-      while (true) {
-        unsigned Tag = Current->Prev.getInt();
-        switch (Tag) {
-        case zeroDigitTag:
-        case oneDigitTag:
-          ++Current;
-          Offset = (Offset << 1) + Tag;
-          continue;
-        default:
-          return Current + Offset;
-        }
-      }
-    }
-
-    case fullStopTag:
-      return Current;
-    }
-  }
-}
-
 } // End llvm namespace

llvm/lib/IR/User.cpp

 
 //===----------------------------------------------------------------------===//
 //                         User allocHungoffUses Implementation
 //===----------------------------------------------------------------------===//
 
 void User::allocHungoffUses(unsigned N, bool IsPhi) {
   assert(HasHungOffUses && "alloc must have hung off uses");
 
-  static_assert(alignof(Use) >= alignof(Use::UserRef),
-                "Alignment is insufficient for 'hung-off-uses' pieces");
-  static_assert(alignof(Use::UserRef) >= alignof(BasicBlock *),
+  static_assert(alignof(Use) >= alignof(BasicBlock *),
                 "Alignment is insufficient for 'hung-off-uses' pieces");
 
   // Allocate the array of Uses, followed by a pointer (with bottom bit set) to
   // the User.
-  size_t size = N * sizeof(Use) + sizeof(Use::UserRef);
+  size_t size = N * sizeof(Use);
   if (IsPhi)
     size += N * sizeof(BasicBlock *);
   Use *Begin = static_cast<Use*>(::operator new(size));
   Use *End = Begin + N;
-  (void) new(End) Use::UserRef(const_cast<User*>(this), 1);
-  setOperandList(Use::initTags(Begin, End));
+  setOperandList(Begin);
+  for (; Begin != End; Begin++)
+    new (Begin) Use(this);
 }
 
 void User::growHungoffUses(unsigned NewNumUses, bool IsPhi) {
   assert(HasHungOffUses && "realloc must have hung off uses");
 
   unsigned OldNumUses = getNumOperands();
 
   // We don't support shrinking the number of uses.  We wouldn't have enough
   // space to copy the old uses in to the new space.
   assert(NewNumUses > OldNumUses && "realloc must grow num uses");
 
   Use *OldOps = getOperandList();
   allocHungoffUses(NewNumUses, IsPhi);
   Use *NewOps = getOperandList();
 
   // Now copy from the old operands list to the new one.
   std::copy(OldOps, OldOps + OldNumUses, NewOps);
 
   // If this is a Phi, then we need to copy the BB pointers too.
   if (IsPhi) {
-    auto *OldPtr =
-        reinterpret_cast<char *>(OldOps + OldNumUses) + sizeof(Use::UserRef);
-    auto *NewPtr =
-        reinterpret_cast<char *>(NewOps + NewNumUses) + sizeof(Use::UserRef);
+    auto *OldPtr = reinterpret_cast<char *>(OldOps + OldNumUses);
+    auto *NewPtr = reinterpret_cast<char *>(NewOps + NewNumUses);
     std::copy(OldPtr, OldPtr + (OldNumUses * sizeof(BasicBlock *)), NewPtr);
   }
   Use::zap(OldOps, OldOps + OldNumUses, true);
 }
 
 
 // This is a private struct used by `User` to track the co-allocated descriptor
 // section.
void *User::allocateFixedOperandUser(size_t Size, unsigned Us,
   uint8_t *Storage = static_cast<uint8_t *>(
       ::operator new(Size + sizeof(Use) * Us + DescBytesToAllocate));
   Use *Start = reinterpret_cast<Use *>(Storage + DescBytesToAllocate);
   Use *End = Start + Us;
   User *Obj = reinterpret_cast<User*>(End);
   Obj->NumUserOperands = Us;
   Obj->HasHungOffUses = false;
   Obj->HasDescriptor = DescBytes != 0;
-  Use::initTags(Start, End);
+  for (; Start != End; Start++)
+    new (Start) Use(Obj);
 
   if (DescBytes != 0) {
     auto *DescInfo = reinterpret_cast<DescriptorInfo *>(Storage + DescBytes);
     DescInfo->SizeInBytes = DescBytes;
   }
 
   return Obj;
 }

llvm/unittests/IR/CMakeLists.txt

add_llvm_unittest(IRTests
   UseTest.cpp
   UserTest.cpp
   ValueHandleTest.cpp
   ValueMapTest.cpp
   ValueTest.cpp
   VectorTypesTest.cpp
   VerifierTest.cpp
   VPIntrinsicTest.cpp
-  WaymarkTest.cpp
   )
 
 target_link_libraries(IRTests PRIVATE LLVMTestingSupport)

llvm/unittests/IR/WaymarkTest.cpp

-//===- llvm/unittest/IR/WaymarkTest.cpp - getUser() unit tests ------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-// we perform white-box tests
-//
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
-#include "gtest/gtest.h"
-#include <algorithm>
-
-namespace llvm {
-namespace {
-
-TEST(WaymarkTest, NativeArray) {
-  LLVMContext Context;
-  static uint8_t tail[22] = "s02s33s30y2y0s1x0syxS";
-  Value * values[22];
-  std::transform(tail, tail + 22, values, [&](char c) {
-    return ConstantInt::get(Type::getInt8Ty(Context), c);
-  });
-  FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), true);
-  std::unique_ptr<Function> F(
-      Function::Create(FT, GlobalValue::ExternalLinkage));
-  const CallInst *A = CallInst::Create(F.get(), makeArrayRef(values));
-  ASSERT_NE(A, (const CallInst*)nullptr);
-  ASSERT_EQ(1U + 22, A->getNumOperands());
-  const Use *U = &A->getOperandUse(0);
-  const Use *Ue = &A->getOperandUse(22);
-  for (; U != Ue; ++U)
-  {
-    EXPECT_EQ(A, U->getUser());
-  }
-  delete A;
-}
-
-TEST(WaymarkTest, TwoBit) {
-  Use* many = (Use*)calloc(sizeof(Use), 8212 + 1);
-  ASSERT_TRUE(many);
-  Use::initTags(many, many + 8212);
-  for (Use *U = many, *Ue = many + 8212 - 1; U != Ue; ++U)
-  {
-    EXPECT_EQ(reinterpret_cast<User *>(Ue + 1), U->getUser());
-  }
-  free(many);
-}
-
-}  // end anonymous namespace
-}  // end namespace llvm