Rearrange operands of the BranchInst, to be able to

access each with a fixed negative index from op_end().

This has two important implications:
- getUser() will work faster, because there are less iterations
  for the waymarking algorithm to perform. This is important
  when running various analyses that want to determine callers
  of basic blocks.
- getSuccessor() now runs faster, because the indirection via OperandList
  is not necessary: Uses corresponding to the successors are at fixed
  offset to "this".

The price we pay is the slightly more complicated logic in the operator
User::delete, as it has to pick up the information whether it has to free
the memory of an original unconditional BranchInst or a BranchInst that
was originally conditional, but has been shortened to unconditional.
I was not able to come up with a nicer solution to this problem. (And
rest assured, I tried *a lot*).

Similar reorderings will follow for InvokeInst and CallInst. After that
some optimizations to pred_iterator and CallSite will fall out naturally.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@66815 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 125 insertions, 51 deletions

diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h
index 535333a9f5..4821155e46 100644
--- a/include/llvm/Instructions.h
+++ b/include/llvm/Instructions.h
@@ -2117,8 +2117,9 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ReturnInst, Value)
 ///
 class BranchInst : public TerminatorInst {
   /// Ops list - Branches are strange.  The operands are ordered:
-  ///  TrueDest, FalseDest, Cond.  This makes some accessors faster because
-  /// they don't have to check for cond/uncond branchness.
+  ///  [Cond, FalseDest,] TrueDest.  This makes some accessors faster because
+  /// they don't have to check for cond/uncond branchness. These are mostly
+  /// accessed relative from op_end().
   BranchInst(const BranchInst &BI);
   void AssertOK();
   // BranchInst constructors (where {B, T, F} are blocks, and C is a condition):
@@ -2136,24 +2137,21 @@ class BranchInst : public TerminatorInst {
              BasicBlock *InsertAtEnd);
 public:
   static BranchInst *Create(BasicBlock *IfTrue, Instruction *InsertBefore = 0) {
-    return new(1) BranchInst(IfTrue, InsertBefore);
+    return new(1, true) BranchInst(IfTrue, InsertBefore);
   }
   static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse,
                             Value *Cond, Instruction *InsertBefore = 0) {
     return new(3) BranchInst(IfTrue, IfFalse, Cond, InsertBefore);
   }
   static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *InsertAtEnd) {
-    return new(1) BranchInst(IfTrue, InsertAtEnd);
+    return new(1, true) BranchInst(IfTrue, InsertAtEnd);
   }
   static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse,
                             Value *Cond, BasicBlock *InsertAtEnd) {
     return new(3) BranchInst(IfTrue, IfFalse, Cond, InsertAtEnd);
   }
 
-  ~BranchInst() {
-    if (NumOperands == 1)
-      NumOperands = (unsigned)((Use*)this - OperandList);
-  }
+  ~BranchInst();
 
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
@@ -2165,23 +2163,24 @@ public:
 
   Value *getCondition() const {
     assert(isConditional() && "Cannot get condition of an uncond branch!");
-    return getOperand(2);
+    return Op<-3>();
   }
 
   void setCondition(Value *V) {
     assert(isConditional() && "Cannot set condition of unconditional branch!");
-    setOperand(2, V);
+    Op<-3>() = V;
   }
 
   // setUnconditionalDest - Change the current branch to an unconditional branch
   // targeting the specified block.
   // FIXME: Eliminate this ugly method.
   void setUnconditionalDest(BasicBlock *Dest) {
-    Op<0>() = Dest;
+    Op<-1>() = Dest;
     if (isConditional()) {  // Convert this to an uncond branch.
-      Op<1>().set(0);
-      Op<2>().set(0);
+      Op<-2>() = 0;
+      Op<-3>() = 0;
       NumOperands = 1;
+      OperandList = op_begin();
     }
   }
 
@@ -2189,12 +2188,12 @@ public:
 
   BasicBlock *getSuccessor(unsigned i) const {
     assert(i < getNumSuccessors() && "Successor # out of range for Branch!");
-    return cast_or_null<BasicBlock>(getOperand(i));
+    return cast_or_null<BasicBlock>((&Op<-1>() - i)->get());
   }
 
   void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
     assert(idx < getNumSuccessors() && "Successor # out of range for Branch!");
-    setOperand(idx, NewSucc);
+    *(&Op<-1>() - idx) = NewSucc;
   }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -2212,11 +2211,7 @@ private:
 };
 
 template <>
-struct OperandTraits<BranchInst> : HungoffOperandTraits<> {
-  // we need to access operands via OperandList, since
-  // the NumOperands may change from 3 to 1
-  static inline void *allocate(unsigned); // FIXME
-};
+struct OperandTraits<BranchInst> : VariadicOperandTraits<1> {};
 
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value)
 
diff --git a/include/llvm/Use.h b/include/llvm/Use.h
index a2774c802f..cde4366a5a 100644
--- a/include/llvm/Use.h
+++ b/include/llvm/Use.h
@@ -92,6 +92,8 @@ public:
   /// a User changes.
   static void zap(Use *Start, const Use *Stop, bool del = false);
 
+  /// getPrefix - Return deletable pointer if appropriate
+  Use *getPrefix();
 private:
   const Use* getImpliedUser() const;
   static Use *initTags(Use *Start, Use *Stop, ptrdiff_t Done = 0);
diff --git a/include/llvm/User.h b/include/llvm/User.h
index 1a88ce0cce..69826c0d8c 100644
--- a/include/llvm/User.h
+++ b/include/llvm/User.h
@@ -62,6 +62,7 @@ protected:
   unsigned NumOperands;
 
   void *operator new(size_t s, unsigned Us);
+  void *operator new(size_t s, unsigned Us, bool Prefix);
   User(const Type *ty, unsigned vty, Use *OpList, unsigned NumOps)
     : Value(ty, vty), OperandList(OpList), NumOperands(NumOps) {}
   Use *allocHungoffUses(unsigned) const;
@@ -74,7 +75,8 @@ protected:
   }
 public:
   ~User() {
-    Use::zap(OperandList, OperandList + NumOperands);
+    if ((intptr_t(OperandList) & 1) == 0)
+      Use::zap(OperandList, OperandList + NumOperands);
   }
   /// operator delete - free memory allocated for User and Use objects
   void operator delete(void *Usr);
diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 7f5d4615d1..fe30271f84 100644
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -612,16 +612,16 @@ BranchInst::BranchInst(BasicBlock *IfTrue, Instruction *InsertBefore)
                    OperandTraits<BranchInst>::op_end(this) - 1,
                    1, InsertBefore) {
   assert(IfTrue != 0 && "Branch destination may not be null!");
-  Op<0>() = IfTrue;
+  Op<-1>() = IfTrue;
 }
 BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
                        Instruction *InsertBefore)
   : TerminatorInst(Type::VoidTy, Instruction::Br,
                    OperandTraits<BranchInst>::op_end(this) - 3,
                    3, InsertBefore) {
-  Op<0>() = IfTrue;
-  Op<1>() = IfFalse;
-  Op<2>() = Cond;
+  Op<-1>() = IfTrue;
+  Op<-2>() = IfFalse;
+  Op<-3>() = Cond;
 #ifndef NDEBUG
   AssertOK();
 #endif
@@ -632,7 +632,7 @@ BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *InsertAtEnd)
                    OperandTraits<BranchInst>::op_end(this) - 1,
                    1, InsertAtEnd) {
   assert(IfTrue != 0 && "Branch destination may not be null!");
-  Op<0>() = IfTrue;
+  Op<-1>() = IfTrue;
 }
 
 BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
@@ -640,9 +640,9 @@ BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
   : TerminatorInst(Type::VoidTy, Instruction::Br,
                    OperandTraits<BranchInst>::op_end(this) - 3,
                    3, InsertAtEnd) {
-  Op<0>() = IfTrue;
-  Op<1>() = IfFalse;
-  Op<2>() = Cond;
+  Op<-1>() = IfTrue;
+  Op<-2>() = IfFalse;
+  Op<-3>() = Cond;
 #ifndef NDEBUG
   AssertOK();
 #endif
@@ -653,14 +653,39 @@ BranchInst::BranchInst(const BranchInst &BI) :
   TerminatorInst(Type::VoidTy, Instruction::Br,
                  OperandTraits<BranchInst>::op_end(this) - BI.getNumOperands(),
                  BI.getNumOperands()) {
-  OperandList[0] = BI.getOperand(0);
+  Op<-1>() = BI.Op<-1>();
   if (BI.getNumOperands() != 1) {
     assert(BI.getNumOperands() == 3 && "BR can have 1 or 3 operands!");
-    OperandList[1] = BI.getOperand(1);
-    OperandList[2] = BI.getOperand(2);
+    Op<-3>() = BI.Op<-3>();
+    Op<-2>() = BI.Op<-2>();
   }
 }
 
+
+Use* Use::getPrefix() {
+  PointerIntPair<Use**, 2, PrevPtrTag> &PotentialPrefix(this[-1].Prev);
+  if (PotentialPrefix.getOpaqueValue())
+    return 0;
+
+  return reinterpret_cast<Use*>((char*)&PotentialPrefix + 1);
+}
+
+BranchInst::~BranchInst() {
+  if (NumOperands == 1) {
+    if (Use *Prefix = OperandList->getPrefix()) {
+      Op<-1>() = 0;
+      //
+      // mark OperandList to have a special value for scrutiny
+      // by baseclass destructors and operator delete
+      OperandList = Prefix;
+    } else {
+      NumOperands = 3;
+      OperandList = op_begin();
+    }
+  }
+}
+
+
 BasicBlock *BranchInst::getSuccessorV(unsigned idx) const {
   return getSuccessor(idx);
 }
@@ -2927,7 +2952,8 @@ ReturnInst *ReturnInst::clone() const {
   return new(getNumOperands()) ReturnInst(*this);
 }
 BranchInst *BranchInst::clone() const {
-  return new(getNumOperands()) BranchInst(*this);
+  unsigned Ops(getNumOperands());
+  return new(Ops, Ops == 1) BranchInst(*this);
 }
 SwitchInst *SwitchInst::clone() const { return new SwitchInst(*this); }
 InvokeInst *InvokeInst::clone() const {
diff --git a/lib/VMCore/Use.cpp b/lib/VMCore/Use.cpp
index 0c566a9cb7..b25415a3d1 100644
--- a/lib/VMCore/Use.cpp
+++ b/lib/VMCore/Use.cpp
@@ -163,4 +163,71 @@ Use *User::allocHungoffUses(unsigned N) const {
   return Use::initTags(Begin, End);
 }
 
+//===----------------------------------------------------------------------===//
+//                         User operator new Implementations
+//===----------------------------------------------------------------------===//
+
+void *User::operator new(size_t s, unsigned Us) {
+  void *Storage = ::operator new(s + sizeof(Use) * Us);
+  Use *Start = static_cast<Use*>(Storage);
+  Use *End = Start + Us;
+  User *Obj = reinterpret_cast<User*>(End);
+  Obj->OperandList = Start;
+  Obj->NumOperands = Us;
+  Use::initTags(Start, End);
+  return Obj;
+}
+
+/// Prefixed allocation - just before the first Use, allocate a NULL pointer.
+/// The destructor can detect its presence and readjust the OperandList
+/// for deletition.
+///
+void *User::operator new(size_t s, unsigned Us, bool Prefix) {
+  // currently prefixed allocation only admissible for
+  // unconditional branch instructions
+  if (!Prefix)
+    return operator new(s, Us);
+
+  assert(Us == 1 && "Other than one Use allocated?");
+  typedef PointerIntPair<void*, 2, Use::PrevPtrTag> TaggedPrefix;
+  void *Raw = ::operator new(s + sizeof(TaggedPrefix) + sizeof(Use) * Us);
+  TaggedPrefix *Pre = static_cast<TaggedPrefix*>(Raw);
+  Pre->setFromOpaqueValue(0);
+  void *Storage = Pre + 1; // skip over prefix
+  Use *Start = static_cast<Use*>(Storage);
+  Use *End = Start + Us;
+  User *Obj = reinterpret_cast<User*>(End);
+  Obj->OperandList = Start;
+  Obj->NumOperands = Us;
+  Use::initTags(Start, End);
+  return Obj;
+}
+
+//===----------------------------------------------------------------------===//
+//                         User operator delete Implementation
+//===----------------------------------------------------------------------===//
+
+void User::operator delete(void *Usr) {
+  User *Start = static_cast<User*>(Usr);
+  Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
+  //
+  // look for a variadic User
+  if (Storage == Start->OperandList) {
+    ::operator delete(Storage);
+    return;
+  }
+  //
+  // check for the flag whether the destructor has detected a prefixed
+  // allocation, in which case we remove the flag and delete starting
+  // at OperandList
+  if (reinterpret_cast<intptr_t>(Start->OperandList) & 1) {
+    ::operator delete(reinterpret_cast<char*>(Start->OperandList) - 1);
+    return;
+  }
+  //
+  // in all other cases just delete the nullary User (covers hung-off
+  // uses also
+  ::operator delete(Usr);
+}
+
 } // End llvm namespace
diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index ab7e0443c0..0aa2db4439 100644
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -406,21 +406,3 @@ void User::replaceUsesOfWith(Value *From, Value *To) {
     }
 }
 
-void *User::operator new(size_t s, unsigned Us) {
-  void *Storage = ::operator new(s + sizeof(Use) * Us);
-  Use *Start = static_cast<Use*>(Storage);
-  Use *End = Start + Us;
-  User *Obj = reinterpret_cast<User*>(End);
-  Obj->OperandList = Start;
-  Obj->NumOperands = Us;
-  Use::initTags(Start, End);
-  return Obj;
-}
-
-void User::operator delete(void *Usr) {
-  User *Start = static_cast<User*>(Usr);
-  Use *Storage = static_cast<Use*>(Usr) - Start->NumOperands;
-  ::operator delete(Storage == Start->OperandList
-                    ? Storage
-                    : Usr);
-}