From ae5a20a9177650525b40ed88c8326a398e6caa8a Mon Sep 17 00:00:00 2001 From: Gabor Greif Date: Thu, 12 Mar 2009 18:34:49 +0000 Subject: [PATCH] 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 --- include/llvm/Instructions.h | 35 +++++++++---------- include/llvm/Use.h | 2 ++ include/llvm/User.h | 4 ++- lib/VMCore/Instructions.cpp | 50 ++++++++++++++++++++------- lib/VMCore/Use.cpp | 67 +++++++++++++++++++++++++++++++++++++ lib/VMCore/Value.cpp | 18 ---------- 6 files changed, 125 insertions(+), 51 deletions(-) diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h index 535333a9f5d..4821155e46f 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(getOperand(i)); + return cast_or_null((&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 : 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 : VariadicOperandTraits<1> {}; DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value) diff --git a/include/llvm/Use.h b/include/llvm/Use.h index a2774c802ff..cde4366a5a0 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 1a88ce0cce8..69826c0d8cf 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 7f5d4615d18..fe30271f844 100644 --- a/lib/VMCore/Instructions.cpp +++ b/lib/VMCore/Instructions.cpp @@ -612,16 +612,16 @@ BranchInst::BranchInst(BasicBlock *IfTrue, Instruction *InsertBefore) OperandTraits::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::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::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::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::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 &PotentialPrefix(this[-1].Prev); + if (PotentialPrefix.getOpaqueValue()) + return 0; + + return reinterpret_cast((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 0c566a9cb70..b25415a3d14 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(Storage); + Use *End = Start + Us; + User *Obj = reinterpret_cast(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 TaggedPrefix; + void *Raw = ::operator new(s + sizeof(TaggedPrefix) + sizeof(Use) * Us); + TaggedPrefix *Pre = static_cast(Raw); + Pre->setFromOpaqueValue(0); + void *Storage = Pre + 1; // skip over prefix + Use *Start = static_cast(Storage); + Use *End = Start + Us; + User *Obj = reinterpret_cast(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(Usr); + Use *Storage = static_cast(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(Start->OperandList) & 1) { + ::operator delete(reinterpret_cast(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 ab7e0443c07..0aa2db44399 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(Storage); - Use *End = Start + Us; - User *Obj = reinterpret_cast(End); - Obj->OperandList = Start; - Obj->NumOperands = Us; - Use::initTags(Start, End); - return Obj; -} - -void User::operator delete(void *Usr) { - User *Start = static_cast(Usr); - Use *Storage = static_cast(Usr) - Start->NumOperands; - ::operator delete(Storage == Start->OperandList - ? Storage - : Usr); -} -- 2.34.1