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.

llvm-svn: 66815

1 files changed, 38 insertions, 12 deletions

diff --git a/llvm/lib/VMCore/Instructions.cpp b/llvm/lib/VMCore/Instructions.cpp
index 7f5d4615d18..fe30271f844 100644
--- a/llvm/lib/VMCore/Instructions.cpp
+++ b/llvm/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 {