diff options
Diffstat (limited to 'include/llvm')
-rw-r--r-- | include/llvm/Constants.h | 42 | ||||
-rw-r--r-- | include/llvm/GlobalAlias.h | 15 | ||||
-rw-r--r-- | include/llvm/GlobalVariable.h | 35 | ||||
-rw-r--r-- | include/llvm/InstrTypes.h | 71 | ||||
-rw-r--r-- | include/llvm/Instruction.h | 1 | ||||
-rw-r--r-- | include/llvm/Instructions.h | 591 | ||||
-rw-r--r-- | include/llvm/OperandTraits.h | 163 | ||||
-rw-r--r-- | include/llvm/Use.h | 81 | ||||
-rw-r--r-- | include/llvm/User.h | 242 | ||||
-rw-r--r-- | include/llvm/Value.h | 7 |
10 files changed, 926 insertions, 322 deletions
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h index c69a381..a55c19a 100644 --- a/include/llvm/Constants.h +++ b/include/llvm/Constants.h @@ -22,6 +22,7 @@ #include "llvm/Constant.h" #include "llvm/Type.h" +#include "llvm/OperandTraits.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/APFloat.h" @@ -318,7 +319,6 @@ class ConstantArray : public Constant { ConstantArray(const ConstantArray &); // DO NOT IMPLEMENT protected: ConstantArray(const ArrayType *T, const std::vector<Constant*> &Val); - ~ConstantArray(); public: /// get() - Static factory methods - Return objects of the specified value static Constant *get(const ArrayType *T, const std::vector<Constant*> &); @@ -336,6 +336,9 @@ public: /// null termination. static Constant *get(const std::string &Initializer, bool AddNull = true); + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant); + /// getType - Specialize the getType() method to always return an ArrayType, /// which reduces the amount of casting needed in parts of the compiler. /// @@ -374,6 +377,11 @@ public: } }; +template <> +struct OperandTraits<ConstantArray> : VariadicOperandTraits<> { +}; + +DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantArray, Constant) //===----------------------------------------------------------------------===// // ConstantStruct - Constant Struct Declarations @@ -384,7 +392,6 @@ class ConstantStruct : public Constant { ConstantStruct(const ConstantStruct &); // DO NOT IMPLEMENT protected: ConstantStruct(const StructType *T, const std::vector<Constant*> &Val); - ~ConstantStruct(); public: /// get() - Static factory methods - Return objects of the specified value /// @@ -396,6 +403,9 @@ public: return get(std::vector<Constant*>(Vals, Vals+NumVals), Packed); } + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant); + /// getType() specialization - Reduce amount of casting... /// inline const StructType *getType() const { @@ -419,6 +429,12 @@ public: } }; +template <> +struct OperandTraits<ConstantStruct> : VariadicOperandTraits<> { +}; + +DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantStruct, Constant) + //===----------------------------------------------------------------------===// /// ConstantVector - Constant Vector Declarations /// @@ -428,7 +444,6 @@ class ConstantVector : public Constant { ConstantVector(const ConstantVector &); // DO NOT IMPLEMENT protected: ConstantVector(const VectorType *T, const std::vector<Constant*> &Val); - ~ConstantVector(); public: /// get() - Static factory methods - Return objects of the specified value static Constant *get(const VectorType *T, const std::vector<Constant*> &); @@ -438,6 +453,9 @@ public: return get(std::vector<Constant*>(Vals, Vals+NumVals)); } + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant); + /// getType - Specialize the getType() method to always return a VectorType, /// which reduces the amount of casting needed in parts of the compiler. /// @@ -475,6 +493,12 @@ public: } }; +template <> +struct OperandTraits<ConstantVector> : VariadicOperandTraits<> { +}; + +DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantVector, Constant) + //===----------------------------------------------------------------------===// /// ConstantPointerNull - a constant pointer value that points to null /// @@ -573,6 +597,9 @@ public: static Constant *getIntToPtr(Constant *C, const Type *Ty); static Constant *getBitCast (Constant *C, const Type *Ty); + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant); + // @brief Convenience function for getting one of the casting operations // using a CastOps opcode. static Constant *getCast( @@ -709,13 +736,13 @@ public: virtual void destroyConstant(); virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U); - /// Override methods to provide more type information... +/* /// Override methods to provide more type information... inline Constant *getOperand(unsigned i) { return cast<Constant>(User::getOperand(i)); } inline Constant *getOperand(unsigned i) const { return const_cast<Constant*>(cast<Constant>(User::getOperand(i))); - } + }*/ /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -725,6 +752,11 @@ public: } }; +template <> +struct OperandTraits<ConstantExpr> : VariadicOperandTraits<1> { +}; + +DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantExpr, Constant) //===----------------------------------------------------------------------===// /// UndefValue - 'undef' values are things that do not have specified contents. diff --git a/include/llvm/GlobalAlias.h b/include/llvm/GlobalAlias.h index b59537c..7c147eb 100644 --- a/include/llvm/GlobalAlias.h +++ b/include/llvm/GlobalAlias.h @@ -16,6 +16,7 @@ #define LLVM_GLOBAL_ALIAS_H #include "llvm/GlobalValue.h" +#include "llvm/OperandTraits.h" namespace llvm { @@ -42,17 +43,19 @@ class GlobalAlias : public GlobalValue { GlobalAlias *getPrev() { return Prev; } const GlobalAlias *getPrev() const { return Prev; } - Use Aliasee; public: - // allocate space for exactly zero operands + // allocate space for exactly one operand void *operator new(size_t s) { - return User::operator new(s, 0); + return User::operator new(s, 1); } /// GlobalAlias ctor - If a parent module is specified, the alias is /// automatically inserted into the end of the specified module's alias list. GlobalAlias(const Type *Ty, LinkageTypes Linkage, const std::string &Name = "", Constant* Aliasee = 0, Module *Parent = 0); + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + /// isDeclaration - Is this global variable lacking an initializer? If so, /// the global variable is defined in some other translation unit, and is thus /// only a declaration here. @@ -95,6 +98,12 @@ public: } }; +template <> +struct OperandTraits<GlobalAlias> : FixedNumOperandTraits<1> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GlobalAlias, Value) + } // End llvm namespace #endif diff --git a/include/llvm/GlobalVariable.h b/include/llvm/GlobalVariable.h index 8c6d803..5a42e78 100644 --- a/include/llvm/GlobalVariable.h +++ b/include/llvm/GlobalVariable.h @@ -21,6 +21,7 @@ #define LLVM_GLOBAL_VARIABLE_H #include "llvm/GlobalValue.h" +#include "llvm/OperandTraits.h" namespace llvm { @@ -44,26 +45,32 @@ class GlobalVariable : public GlobalValue { bool isConstantGlobal : 1; // Is this a global constant? bool isThreadLocalSymbol : 1; // Is this symbol "Thread Local"? - Use Initializer; public: - // allocate space for exactly zero operands + // allocate space for exactly one operand void *operator new(size_t s) { - return User::operator new(s, 0); + return User::operator new(s, 1); } /// GlobalVariable ctor - If a parent module is specified, the global is /// automatically inserted into the end of the specified modules global list. GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes Linkage, Constant *Initializer = 0, const std::string &Name = "", - Module *Parent = 0, bool ThreadLocal = false, + Module *Parent = 0, bool ThreadLocal = false, unsigned AddressSpace = 0); /// GlobalVariable ctor - This creates a global and inserts it before the /// specified other global. GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes Linkage, Constant *Initializer, const std::string &Name, - GlobalVariable *InsertBefore, bool ThreadLocal = false, + GlobalVariable *InsertBefore, bool ThreadLocal = false, unsigned AddressSpace = 0); - + + ~GlobalVariable() { + NumOperands = 1; // FIXME: needed by operator delete + } + + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + /// isDeclaration - Is this global variable lacking an initializer? If so, /// the global variable is defined in some other translation unit, and is thus /// only a declaration here. @@ -79,24 +86,24 @@ public: /// illegal to call this method if the global is external, because we cannot /// tell what the value is initialized to! /// - inline Constant *getInitializer() const { + inline /*const FIXME*/ Constant *getInitializer() const { assert(hasInitializer() && "GV doesn't have initializer!"); - return reinterpret_cast<Constant*>(Initializer.get()); + return static_cast<Constant*>(Op<0>().get()); } inline Constant *getInitializer() { assert(hasInitializer() && "GV doesn't have initializer!"); - return reinterpret_cast<Constant*>(Initializer.get()); + return static_cast<Constant*>(Op<0>().get()); } inline void setInitializer(Constant *CPV) { if (CPV == 0) { if (hasInitializer()) { - Initializer.set(0); + Op<0>().set(0); NumOperands = 0; } } else { if (!hasInitializer()) NumOperands = 1; - Initializer.set(CPV); + Op<0>().set(CPV); } } @@ -141,6 +148,12 @@ private: const GlobalVariable *getPrev() const { return Prev; } }; +template <> +struct OperandTraits<GlobalVariable> : OptionalOperandTraits<> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GlobalVariable, Value) + } // End llvm namespace #endif diff --git a/include/llvm/InstrTypes.h b/include/llvm/InstrTypes.h index f735602..a68b562 100644 --- a/include/llvm/InstrTypes.h +++ b/include/llvm/InstrTypes.h @@ -17,6 +17,7 @@ #define LLVM_INSTRUCTION_TYPES_H #include "llvm/Instruction.h" +#include "llvm/OperandTraits.h" namespace llvm { @@ -78,22 +79,22 @@ public: } }; + //===----------------------------------------------------------------------===// // UnaryInstruction Class //===----------------------------------------------------------------------===// class UnaryInstruction : public Instruction { void *operator new(size_t, unsigned); // Do not implement - Use Op; - // avoiding warning: 'this' : used in base member initializer list - UnaryInstruction* this_() { return this; } protected: - UnaryInstruction(const Type *Ty, unsigned iType, Value *V, Instruction *IB =0) - : Instruction(Ty, iType, &Op, 1, IB), Op(V, this_()) { + UnaryInstruction(const Type *Ty, unsigned iType, Value *V, Instruction *IB = 0) + : Instruction(Ty, iType, &Op<0>(), 1, IB) { + Op<0>() = V; } UnaryInstruction(const Type *Ty, unsigned iType, Value *V, BasicBlock *IAE) - : Instruction(Ty, iType, &Op, 1, IAE), Op(V, this_()) { + : Instruction(Ty, iType, &Op<0>(), 1, IAE) { + Op<0>() = V; } public: // allocate space for exactly one operand @@ -104,16 +105,8 @@ public: // Out of line virtual method, so the vtable, etc has a home. ~UnaryInstruction(); - // Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i == 0 && "getOperand() out of range!"); - return Op; - } - void setOperand(unsigned i, Value *Val) { - assert(i == 0 && "setOperand() out of range!"); - Op = Val; - } - unsigned getNumOperands() const { return 1; } + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const UnaryInstruction *) { return true; } @@ -130,13 +123,18 @@ public: } }; +template <> +struct OperandTraits<UnaryInstruction> : FixedNumOperandTraits<1> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(UnaryInstruction, Value) + //===----------------------------------------------------------------------===// // BinaryOperator Class //===----------------------------------------------------------------------===// class BinaryOperator : public Instruction { void *operator new(size_t, unsigned); // Do not implement - Use Ops[2]; protected: void init(BinaryOps iType); BinaryOperator(BinaryOps iType, Value *S1, Value *S2, const Type *Ty, @@ -150,15 +148,7 @@ public: } /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 2 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 2 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 2; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); /// create() - Construct a binary instruction, given the opcode and the two /// operands. Optionally (if InstBefore is specified) insert the instruction @@ -251,6 +241,12 @@ public: } }; +template <> +struct OperandTraits<BinaryOperator> : FixedNumOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BinaryOperator, Value) + //===----------------------------------------------------------------------===// // CastInst Class //===----------------------------------------------------------------------===// @@ -497,6 +493,7 @@ public: /// This class is the base class for the comparison instructions. /// @brief Abstract base class of comparison instructions. +// FIXME: why not derive from BinaryOperator? class CmpInst: public Instruction { void *operator new(size_t, unsigned); // DO NOT IMPLEMENT CmpInst(); // do not implement @@ -507,8 +504,6 @@ protected: CmpInst(Instruction::OtherOps op, unsigned short pred, Value *LHS, Value *RHS, const std::string &Name, BasicBlock *InsertAtEnd); - Use Ops[2]; // CmpInst instructions always have 2 operands, optimize - public: // allocate space for exactly two operands void *operator new(size_t s) { @@ -548,17 +543,7 @@ public: } /// @brief Provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 2 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 2 && "setOperand() out of range!"); - Ops[i] = Val; - } - - /// @brief CmpInst instructions always have 2 operands. - unsigned getNumOperands() const { return 2; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); /// This is just a convenience that dispatches to the subclasses. /// @brief Swap the operands and adjust predicate accordingly to retain @@ -598,6 +583,14 @@ public: } }; + +// FIXME: these are redundant if CmpInst < BinaryOperator +template <> +struct OperandTraits<CmpInst> : FixedNumOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CmpInst, Value) + } // End llvm namespace #endif diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h index 29ae5c3..40d8305 100644 --- a/include/llvm/Instruction.h +++ b/include/llvm/Instruction.h @@ -20,7 +20,6 @@ namespace llvm { struct AssemblyAnnotationWriter; -class BinaryOperator; template<typename ValueSubClass, typename ItemParentClass> class SymbolTableListTraits; diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h index f292a31..86bc3f5 100644 --- a/include/llvm/Instructions.h +++ b/include/llvm/Instructions.h @@ -21,10 +21,10 @@ #include "llvm/InstrTypes.h" #include "llvm/DerivedTypes.h" #include "llvm/ParameterAttributes.h" +#include "llvm/BasicBlock.h" namespace llvm { -class BasicBlock; class ConstantInt; class PointerType; class VectorType; @@ -288,11 +288,11 @@ public: /// class StoreInst : public Instruction { void *operator new(size_t, unsigned); // DO NOT IMPLEMENT - Use Ops[2]; - StoreInst(const StoreInst &SI) : Instruction(SI.getType(), Store, Ops, 2) { - Ops[0].init(SI.Ops[0], this); - Ops[1].init(SI.Ops[1], this); + StoreInst(const StoreInst &SI) : Instruction(SI.getType(), Store, + &Op<0>(), 2) { + Op<0>().init(SI.Op<0>(), this); + Op<1>().init(SI.Op<1>(), this); setVolatile(SI.isVolatile()); setAlignment(SI.getAlignment()); @@ -329,15 +329,7 @@ public: } /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 2 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 2 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 2; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); /// getAlignment - Return the alignment of the access that is being performed /// @@ -363,6 +355,11 @@ public: } }; +template <> +struct OperandTraits<StoreInst> : FixedNumOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(StoreInst, Value) //===----------------------------------------------------------------------===// // GetElementPtrInst Class @@ -380,14 +377,7 @@ static inline const Type *checkType(const Type *Ty) { /// access elements of arrays and structs /// class GetElementPtrInst : public Instruction { - GetElementPtrInst(const GetElementPtrInst &GEPI) - : Instruction(reinterpret_cast<const Type*>(GEPI.getType()), GetElementPtr, - 0, GEPI.getNumOperands()) { - Use *OL = OperandList = new Use[NumOperands]; - Use *GEPIOL = GEPI.OperandList; - for (unsigned i = 0, E = NumOperands; i != E; ++i) - OL[i].init(GEPIOL[i], this); - } + GetElementPtrInst(const GetElementPtrInst &GEPI); void init(Value *Ptr, Value* const *Idx, unsigned NumIdx); void init(Value *Ptr, Value *Idx); @@ -400,8 +390,9 @@ class GetElementPtrInst : public Instruction { unsigned NumIdx = static_cast<unsigned>(std::distance(IdxBegin, IdxEnd)); if (NumIdx > 0) { - // This requires that the itoerator points to contiguous memory. - init(Ptr, &*IdxBegin, NumIdx); + // This requires that the iterator points to contiguous memory. + init(Ptr, &*IdxBegin, NumIdx); // FIXME: for the general case + // we have to build an array here } else { init(Ptr, 0, NumIdx); @@ -446,34 +437,21 @@ class GetElementPtrInst : public Instruction { /// instruction, the second appends the new instruction to the specified /// BasicBlock. template<typename InputIterator> - GetElementPtrInst(Value *Ptr, InputIterator IdxBegin, - InputIterator IdxEnd, - const std::string &Name = "", - Instruction *InsertBefore = 0) - : Instruction(PointerType::get( - checkType(getIndexedType(Ptr->getType(), - IdxBegin, IdxEnd, true)), - cast<PointerType>(Ptr->getType())->getAddressSpace()), - GetElementPtr, 0, 0, InsertBefore) { - init(Ptr, IdxBegin, IdxEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + inline GetElementPtrInst(Value *Ptr, InputIterator IdxBegin, + InputIterator IdxEnd, + unsigned Values, + const std::string &Name, + Instruction *InsertBefore); template<typename InputIterator> - GetElementPtrInst(Value *Ptr, InputIterator IdxBegin, InputIterator IdxEnd, - const std::string &Name, BasicBlock *InsertAtEnd) - : Instruction(PointerType::get( - checkType(getIndexedType(Ptr->getType(), - IdxBegin, IdxEnd, true)), - cast<PointerType>(Ptr->getType())->getAddressSpace()), - GetElementPtr, 0, 0, InsertAtEnd) { - init(Ptr, IdxBegin, IdxEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + inline GetElementPtrInst(Value *Ptr, + InputIterator IdxBegin, InputIterator IdxEnd, + unsigned Values, + const std::string &Name, BasicBlock *InsertAtEnd); /// Constructors - These two constructors are convenience methods because one /// and two index getelementptr instructions are so common. - GetElementPtrInst(Value *Ptr, Value *Idx, - const std::string &Name = "", Instruction *InsertBefore = 0); + GetElementPtrInst(Value *Ptr, Value *Idx, const std::string &Name = "", + Instruction *InsertBefore = 0); GetElementPtrInst(Value *Ptr, Value *Idx, const std::string &Name, BasicBlock *InsertAtEnd); public: @@ -482,28 +460,40 @@ public: InputIterator IdxEnd, const std::string &Name = "", Instruction *InsertBefore = 0) { - return new(0/*FIXME*/) GetElementPtrInst(Ptr, IdxBegin, IdxEnd, Name, InsertBefore); + typename std::iterator_traits<InputIterator>::difference_type Values = + 1 + std::distance(IdxBegin, IdxEnd); + return new(Values) + GetElementPtrInst(Ptr, IdxBegin, IdxEnd, Values, Name, InsertBefore); } template<typename InputIterator> - static GetElementPtrInst *Create(Value *Ptr, InputIterator IdxBegin, InputIterator IdxEnd, - const std::string &Name, BasicBlock *InsertAtEnd) { - return new(0/*FIXME*/) GetElementPtrInst(Ptr, IdxBegin, IdxEnd, Name, InsertAtEnd); + static GetElementPtrInst *Create(Value *Ptr, + InputIterator IdxBegin, InputIterator IdxEnd, + const std::string &Name, + BasicBlock *InsertAtEnd) { + typename std::iterator_traits<InputIterator>::difference_type Values = + 1 + std::distance(IdxBegin, IdxEnd); + return new(Values) + GetElementPtrInst(Ptr, IdxBegin, IdxEnd, Values, Name, InsertAtEnd); } - /// Constructors - These two constructors are convenience methods because one - /// and two index getelementptr instructions are so common. + /// Constructors - These two creators are convenience methods because one + /// index getelementptr instructions are so common. static GetElementPtrInst *Create(Value *Ptr, Value *Idx, - const std::string &Name = "", Instruction *InsertBefore = 0) { - return new(2/*FIXME*/) GetElementPtrInst(Ptr, Idx, Name, InsertBefore); + const std::string &Name = "", + Instruction *InsertBefore = 0) { + return new(2) GetElementPtrInst(Ptr, Idx, Name, InsertBefore); } static GetElementPtrInst *Create(Value *Ptr, Value *Idx, - const std::string &Name, BasicBlock *InsertAtEnd) { - return new(2/*FIXME*/) GetElementPtrInst(Ptr, Idx, Name, InsertAtEnd); + const std::string &Name, + BasicBlock *InsertAtEnd) { + return new(2) GetElementPtrInst(Ptr, Idx, Name, InsertAtEnd); } - ~GetElementPtrInst(); virtual GetElementPtrInst *clone() const; + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + // getType - Overload to return most specific pointer type... const PointerType *getType() const { return reinterpret_cast<const PointerType*>(Instruction::getType()); @@ -570,6 +560,51 @@ public: } }; +template <> +struct OperandTraits<GetElementPtrInst> : VariadicOperandTraits<1> { +}; + +template<typename InputIterator> +GetElementPtrInst::GetElementPtrInst(Value *Ptr, + InputIterator IdxBegin, + InputIterator IdxEnd, + unsigned Values, + const std::string &Name, + Instruction *InsertBefore) + : Instruction(PointerType::get(checkType( + getIndexedType(Ptr->getType(), + IdxBegin, IdxEnd, true)), + cast<PointerType>(Ptr->getType()) + ->getAddressSpace()), + GetElementPtr, + OperandTraits<GetElementPtrInst>::op_end(this) - Values, + Values, InsertBefore) { + init(Ptr, IdxBegin, IdxEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} +template<typename InputIterator> +GetElementPtrInst::GetElementPtrInst(Value *Ptr, + InputIterator IdxBegin, + InputIterator IdxEnd, + unsigned Values, + const std::string &Name, + BasicBlock *InsertAtEnd) + : Instruction(PointerType::get(checkType( + getIndexedType(Ptr->getType(), + IdxBegin, IdxEnd, true)), + cast<PointerType>(Ptr->getType()) + ->getAddressSpace()), + GetElementPtr, + OperandTraits<GetElementPtrInst>::op_end(this) - Values, + Values, InsertAtEnd) { + init(Ptr, IdxBegin, IdxEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} + + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrInst, Value) + + //===----------------------------------------------------------------------===// // ICmpInst Class //===----------------------------------------------------------------------===// @@ -723,7 +758,7 @@ public: /// @brief Swap operands and adjust predicate. void swapOperands() { SubclassData = getSwappedPredicate(); - std::swap(Ops[0], Ops[1]); + std::swap(Op<0>(), Op<1>()); } virtual ICmpInst *clone() const; @@ -847,7 +882,7 @@ public: /// @brief Swap operands and adjust predicate. void swapOperands() { SubclassData = getSwappedPredicate(); - std::swap(Ops[0], Ops[1]); + std::swap(Op<0>(), Op<1>()); } virtual FCmpInst *clone() const; @@ -900,13 +935,7 @@ class CallInst : public Instruction { /// @brief Construct a CallInst from a range of arguments template<typename InputIterator> CallInst(Value *Func, InputIterator ArgBegin, InputIterator ArgEnd, - const std::string &Name = "", Instruction *InsertBefore = 0) - : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType()) - ->getElementType())->getReturnType(), - Instruction::Call, 0, 0, InsertBefore) { - init(Func, ArgBegin, ArgEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + const std::string &Name, Instruction *InsertBefore); /// Construct a CallInst given a range of arguments. InputIterator /// must be a random-access iterator pointing to contiguous storage @@ -915,35 +944,29 @@ class CallInst : public Instruction { /// incur runtime overhead. /// @brief Construct a CallInst from a range of arguments template<typename InputIterator> - CallInst(Value *Func, InputIterator ArgBegin, InputIterator ArgEnd, - const std::string &Name, BasicBlock *InsertAtEnd) - : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType()) - ->getElementType())->getReturnType(), - Instruction::Call, 0, 0, InsertAtEnd) { - init(Func, ArgBegin, ArgEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + inline CallInst(Value *Func, InputIterator ArgBegin, InputIterator ArgEnd, + const std::string &Name, BasicBlock *InsertAtEnd); - CallInst(Value *F, Value *Actual, const std::string& Name = "", - Instruction *InsertBefore = 0); + CallInst(Value *F, Value *Actual, const std::string& Name, + Instruction *InsertBefore); CallInst(Value *F, Value *Actual, const std::string& Name, BasicBlock *InsertAtEnd); - explicit CallInst(Value *F, const std::string &Name = "", - Instruction *InsertBefore = 0); + explicit CallInst(Value *F, const std::string &Name, + Instruction *InsertBefore); CallInst(Value *F, const std::string &Name, BasicBlock *InsertAtEnd); public: template<typename InputIterator> - static CallInst *Create(Value *Func, InputIterator ArgBegin, - InputIterator ArgEnd, + static CallInst *Create(Value *Func, + InputIterator ArgBegin, InputIterator ArgEnd, const std::string &Name = "", Instruction *InsertBefore = 0) { return new(ArgEnd - ArgBegin + 1) CallInst(Func, ArgBegin, ArgEnd, Name, InsertBefore); } template<typename InputIterator> - static CallInst *Create(Value *Func, InputIterator ArgBegin, - InputIterator ArgEnd, const std::string &Name, - BasicBlock *InsertAtEnd) { + static CallInst *Create(Value *Func, + InputIterator ArgBegin, InputIterator ArgEnd, + const std::string &Name, BasicBlock *InsertAtEnd) { return new(ArgEnd - ArgBegin + 1) CallInst(Func, ArgBegin, ArgEnd, Name, InsertAtEnd); } @@ -967,6 +990,9 @@ public: ~CallInst(); virtual CallInst *clone() const; + + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); bool isTailCall() const { return SubclassData & 1; } void setTailCall(bool isTailCall = true) { @@ -1050,6 +1076,36 @@ public: } }; +template <> +struct OperandTraits<CallInst> : VariadicOperandTraits<1> { +}; + +template<typename InputIterator> +CallInst::CallInst(Value *Func, InputIterator ArgBegin, InputIterator ArgEnd, + const std::string &Name, BasicBlock *InsertAtEnd) + : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType()) + ->getElementType())->getReturnType(), + Instruction::Call, + OperandTraits<CallInst>::op_end(this) - (ArgEnd - ArgBegin + 1), + ArgEnd - ArgBegin + 1, InsertAtEnd) { + init(Func, ArgBegin, ArgEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} + +template<typename InputIterator> +CallInst::CallInst(Value *Func, InputIterator ArgBegin, InputIterator ArgEnd, + const std::string &Name, Instruction *InsertBefore) + : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType()) + ->getElementType())->getReturnType(), + Instruction::Call, + OperandTraits<CallInst>::op_end(this) - (ArgEnd - ArgBegin + 1), + ArgEnd - ArgBegin + 1, InsertBefore) { + init(Func, ArgBegin, ArgEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CallInst, Value) + //===----------------------------------------------------------------------===// // SelectInst Class //===----------------------------------------------------------------------===// @@ -1057,27 +1113,27 @@ public: /// SelectInst - This class represents the LLVM 'select' instruction. /// class SelectInst : public Instruction { - Use Ops[3]; - void init(Value *C, Value *S1, Value *S2) { - Ops[0].init(C, this); - Ops[1].init(S1, this); - Ops[2].init(S2, this); + Op<0>() = C; + Op<1>() = S1; + Op<2>() = S2; } SelectInst(const SelectInst &SI) - : Instruction(SI.getType(), SI.getOpcode(), Ops, 3) { - init(SI.Ops[0], SI.Ops[1], SI.Ops[2]); + : Instruction(SI.getType(), SI.getOpcode(), &Op<0>(), 3) { + init(SI.Op<0>(), SI.Op<1>(), SI.Op<2>()); } - SelectInst(Value *C, Value *S1, Value *S2, const std::string &Name = "", - Instruction *InsertBefore = 0) - : Instruction(S1->getType(), Instruction::Select, Ops, 3, InsertBefore) { + SelectInst(Value *C, Value *S1, Value *S2, const std::string &Name, + Instruction *InsertBefore) + : Instruction(S1->getType(), Instruction::Select, + &Op<0>(), 3, InsertBefore) { init(C, S1, S2); setName(Name); } SelectInst(Value *C, Value *S1, Value *S2, const std::string &Name, BasicBlock *InsertAtEnd) - : Instruction(S1->getType(), Instruction::Select, Ops, 3, InsertAtEnd) { + : Instruction(S1->getType(), Instruction::Select, + &Op<0>(), 3, InsertAtEnd) { init(C, S1, S2); setName(Name); } @@ -1092,20 +1148,12 @@ public: return new(3) SelectInst(C, S1, S2, Name, InsertAtEnd); } - Value *getCondition() const { return Ops[0]; } - Value *getTrueValue() const { return Ops[1]; } - Value *getFalseValue() const { return Ops[2]; } + Value *getCondition() const { return Op<0>(); } + Value *getTrueValue() const { return Op<1>(); } + Value *getFalseValue() const { return Op<2>(); } /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 3 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 3 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 3; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); OtherOps getOpcode() const { return static_cast<OtherOps>(Instruction::getOpcode()); @@ -1123,6 +1171,12 @@ public: } }; +template <> +struct OperandTraits<SelectInst> : FixedNumOperandTraits<3> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectInst, Value) + //===----------------------------------------------------------------------===// // VAArgInst Class //===----------------------------------------------------------------------===// @@ -1165,17 +1219,16 @@ public: /// element from a VectorType value /// class ExtractElementInst : public Instruction { - Use Ops[2]; ExtractElementInst(const ExtractElementInst &EE) : - Instruction(EE.getType(), ExtractElement, Ops, 2) { - Ops[0].init(EE.Ops[0], this); - Ops[1].init(EE.Ops[1], this); + Instruction(EE.getType(), ExtractElement, &Op<0>(), 2) { + Op<0>().init(EE.Op<0>(), this); + Op<1>().init(EE.Op<1>(), this); } public: // allocate space for exactly two operands void *operator new(size_t s) { - return User::operator new(s, 2); // FIXME: unsigned Idx forms of constructor? + return User::operator new(s, 2); // FIXME: "unsigned Idx" forms of ctor? } ExtractElementInst(Value *Vec, Value *Idx, const std::string &Name = "", Instruction *InsertBefore = 0); @@ -1193,15 +1246,7 @@ public: virtual ExtractElementInst *clone() const; /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 2 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 2 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 2; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const ExtractElementInst *) { return true; } @@ -1213,6 +1258,12 @@ public: } }; +template <> +struct OperandTraits<ExtractElementInst> : FixedNumOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ExtractElementInst, Value) + //===----------------------------------------------------------------------===// // InsertElementInst Class //===----------------------------------------------------------------------===// @@ -1221,7 +1272,6 @@ public: /// element into a VectorType value /// class InsertElementInst : public Instruction { - Use Ops[3]; InsertElementInst(const InsertElementInst &IE); InsertElementInst(Value *Vec, Value *NewElt, Value *Idx, const std::string &Name = "",Instruction *InsertBefore = 0); @@ -1236,14 +1286,14 @@ public: return new(IE.getNumOperands()) InsertElementInst(IE); } static InsertElementInst *Create(Value *Vec, Value *NewElt, Value *Idx, - const std::string &Name = "",Instruction *InsertBefore = 0) { + const std::string &Name = "", + Instruction *InsertBefore = 0) { return new(3) InsertElementInst(Vec, NewElt, Idx, Name, InsertBefore); } static InsertElementInst *Create(Value *Vec, Value *NewElt, unsigned Idx, const std::string &Name = "", Instruction *InsertBefore = 0) { - return new(3/*FIXME*/) - InsertElementInst(Vec, NewElt, Idx, Name, InsertBefore); + return new(3) InsertElementInst(Vec, NewElt, Idx, Name, InsertBefore); } static InsertElementInst *Create(Value *Vec, Value *NewElt, Value *Idx, const std::string &Name, @@ -1253,8 +1303,7 @@ public: static InsertElementInst *Create(Value *Vec, Value *NewElt, unsigned Idx, const std::string &Name, BasicBlock *InsertAtEnd) { - return new(3/*FIXME*/) - InsertElementInst(Vec, NewElt, Idx, Name, InsertAtEnd); + return new(3) InsertElementInst(Vec, NewElt, Idx, Name, InsertAtEnd); } /// isValidOperands - Return true if an insertelement instruction can be @@ -1271,15 +1320,7 @@ public: } /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < 3 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 3 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 3; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const InsertElementInst *) { return true; } @@ -1291,6 +1332,12 @@ public: } }; +template <> +struct OperandTraits<InsertElementInst> : FixedNumOperandTraits<3> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementInst, Value) + //===----------------------------------------------------------------------===// // ShuffleVectorInst Class //===----------------------------------------------------------------------===// @@ -1299,7 +1346,6 @@ public: /// input vectors. /// class ShuffleVectorInst : public Instruction { - Use Ops[3]; ShuffleVectorInst(const ShuffleVectorInst &IE); public: // allocate space for exactly three operands @@ -1325,19 +1371,7 @@ public: } /// Transparently provide more efficient getOperand methods. - const Value *getOperand(unsigned i) const { - assert(i < 3 && "getOperand() out of range!"); - return Ops[i]; - } - Value *getOperand(unsigned i) { - assert(i < 3 && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < 3 && "setOperand() out of range!"); - Ops[i] = Val; - } - unsigned getNumOperands() const { return 3; } + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); /// getMaskValue - Return the index from the shuffle mask for the specified /// output result. This is either -1 if the element is undef or a number less @@ -1354,6 +1388,11 @@ public: } }; +template <> +struct OperandTraits<ShuffleVectorInst> : FixedNumOperandTraits<3> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ShuffleVectorInst, Value) //===----------------------------------------------------------------------===// // PHINode Class @@ -1406,6 +1445,9 @@ public: virtual PHINode *clone() const; + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + /// getNumIncomingValues - Return the number of incoming edges /// unsigned getNumIncomingValues() const { return getNumOperands()/2; } @@ -1427,10 +1469,10 @@ public: /// getIncomingBlock - Return incoming basic block number x /// BasicBlock *getIncomingBlock(unsigned i) const { - return reinterpret_cast<BasicBlock*>(getOperand(i*2+1)); + return static_cast<BasicBlock*>(getOperand(i*2+1)); } void setIncomingBlock(unsigned i, BasicBlock *BB) { - setOperand(i*2+1, reinterpret_cast<Value*>(BB)); + setOperand(i*2+1, BB); } unsigned getOperandNumForIncomingBlock(unsigned i) { return i*2+1; @@ -1449,7 +1491,7 @@ public: // Initialize some new operands. NumOperands = OpNo+2; OperandList[OpNo].init(V, this); - OperandList[OpNo+1].init(reinterpret_cast<Value*>(BB), this); + OperandList[OpNo+1].init(BB, this); } /// removeIncomingValue - Remove an incoming value. This is useful if a @@ -1462,7 +1504,7 @@ public: /// Value *removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty = true); - Value *removeIncomingValue(const BasicBlock *BB, bool DeletePHIIfEmpty =true){ + Value *removeIncomingValue(const BasicBlock *BB, bool DeletePHIIfEmpty=true) { int Idx = getBasicBlockIndex(BB); assert(Idx >= 0 && "Invalid basic block argument to remove!"); return removeIncomingValue(Idx, DeletePHIIfEmpty); @@ -1474,7 +1516,7 @@ public: int getBasicBlockIndex(const BasicBlock *BB) const { Use *OL = OperandList; for (unsigned i = 0, e = getNumOperands(); i != e; i += 2) - if (OL[i+1] == reinterpret_cast<const Value*>(BB)) return i/2; + if (OL[i+1].get() == BB) return i/2; return -1; } @@ -1499,6 +1541,13 @@ public: void resizeOperands(unsigned NumOperands); }; +template <> +struct OperandTraits<PHINode> : HungoffOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(PHINode, Value) + + //===----------------------------------------------------------------------===// // ReturnInst Class //===----------------------------------------------------------------------===// @@ -1508,7 +1557,6 @@ public: /// does not continue in this function any longer. /// class ReturnInst : public TerminatorInst { - Use RetVal; ReturnInst(const ReturnInst &RI); void init(Value * const* retVals, unsigned N); @@ -1517,20 +1565,19 @@ private: // ReturnInst() - 'ret void' instruction // ReturnInst( null) - 'ret void' instruction // ReturnInst(Value* X) - 'ret X' instruction - // ReturnInst( null, Inst *) - 'ret void' instruction, insert before I + // ReturnInst( null, Inst *I) - 'ret void' instruction, insert before I // ReturnInst(Value* X, Inst *I) - 'ret X' instruction, insert before I - // ReturnInst( null, BB *B) - 'ret void' instruction, insert @ end of BB - // ReturnInst(Value* X, BB *B) - 'ret X' instruction, insert @ end of BB + // ReturnInst( null, BB *B) - 'ret void' instruction, insert @ end of B + // ReturnInst(Value* X, BB *B) - 'ret X' instruction, insert @ end of B // ReturnInst(Value* X, N) - 'ret X,X+1...X+N-1' instruction - // ReturnInst(Value* X, N, Inst *) - 'ret X,X+1...X+N-1', insert before I - // ReturnInst(Value* X, N, BB *) - 'ret X,X+1...X+N-1', insert @ end of BB + // ReturnInst(Value* X, N, Inst *I) - 'ret X,X+1...X+N-1', insert before I + // ReturnInst(Value* X, N, BB *B) - 'ret X,X+1...X+N-1', insert @ end of B // // NOTE: If the Value* passed is of type void then the constructor behaves as // if it was passed NULL. explicit ReturnInst(Value *retVal = 0, Instruction *InsertBefore = 0); ReturnInst(Value *retVal, BasicBlock *InsertAtEnd); - ReturnInst(Value * const* retVals, unsigned N); - ReturnInst(Value * const* retVals, unsigned N, Instruction *InsertBefore); + ReturnInst(Value * const* retVals, unsigned N, Instruction *InsertBefore = 0); ReturnInst(Value * const* retVals, unsigned N, BasicBlock *InsertAtEnd); explicit ReturnInst(BasicBlock *InsertAtEnd); public: @@ -1540,11 +1587,8 @@ public: static ReturnInst* Create(Value *retVal, BasicBlock *InsertAtEnd) { return new(!!retVal) ReturnInst(retVal, InsertAtEnd); } - static ReturnInst* Create(Value * const* retVals, unsigned N) { - return new(N) ReturnInst(retVals, N); - } static ReturnInst* Create(Value * const* retVals, unsigned N, - Instruction *InsertBefore) { + Instruction *InsertBefore = 0) { return new(N) ReturnInst(retVals, N, InsertBefore); } static ReturnInst* Create(Value * const* retVals, unsigned N, @@ -1555,18 +1599,18 @@ public: return new(0) ReturnInst(InsertAtEnd); } virtual ~ReturnInst(); + inline void operator delete(void*); virtual ReturnInst *clone() const; - Value *getOperand(unsigned n = 0) const { - if (getNumOperands() > 1) - return TerminatorInst::getOperand(n); - else - return RetVal; - } + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + /// Convenience accessor Value *getReturnValue(unsigned n = 0) const { - return getOperand(n); + return n < getNumOperands() + ? getOperand(n) + : 0; } unsigned getNumSuccessors() const { return 0; } @@ -1585,6 +1629,18 @@ public: virtual void setSuccessorV(unsigned idx, BasicBlock *B); }; +template <> +struct OperandTraits<ReturnInst> : VariadicOperandTraits<> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ReturnInst, Value) +void ReturnInst::operator delete(void *it) { + ReturnInst* me(static_cast<ReturnInst*>(it)); + Use::zap(OperandTraits<ReturnInst>::op_begin(me), + OperandTraits<ReturnInst>::op_end(me), + true); +} + //===----------------------------------------------------------------------===// // BranchInst Class //===----------------------------------------------------------------------===// @@ -1596,7 +1652,6 @@ 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. - Use Ops[3]; BranchInst(const BranchInst &BI); void AssertOK(); // BranchInst constructors (where {B, T, F} are blocks, and C is a condition): @@ -1616,28 +1671,29 @@ public: static BranchInst *Create(BasicBlock *IfTrue, Instruction *InsertBefore = 0) { return new(1) BranchInst(IfTrue, InsertBefore); } - static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond, - Instruction *InsertBefore = 0) { + 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); } - static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond, - BasicBlock *InsertAtEnd) { + static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse, + Value *Cond, BasicBlock *InsertAtEnd) { return new(3) BranchInst(IfTrue, IfFalse, Cond, InsertAtEnd); } - /// Transparently provide more efficient getOperand methods. - Value *getOperand(unsigned i) const { - assert(i < getNumOperands() && "getOperand() out of range!"); - return Ops[i]; - } - void setOperand(unsigned i, Value *Val) { - assert(i < getNumOperands() && "setOperand() out of range!"); - Ops[i] = Val; + ~BranchInst() + { + if (NumOperands == 1) + { + NumOperands = (Use*)this - OperandList; + } } + /// Transparently provide more efficient getOperand methods. + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + virtual BranchInst *clone() const; bool isUnconditional() const { return getNumOperands() == 1; } @@ -1657,12 +1713,12 @@ public: // targeting the specified block. // FIXME: Eliminate this ugly method. void setUnconditionalDest(BasicBlock *Dest) { + Op<0>() = Dest; if (isConditional()) { // Convert this to an uncond branch. + Op<1>().set(0); + Op<2>().set(0); NumOperands = 1; - Ops[1].set(0); - Ops[2].set(0); } - setOperand(0, reinterpret_cast<Value*>(Dest)); } unsigned getNumSuccessors() const { return 1+isConditional(); } @@ -1674,7 +1730,7 @@ public: void setSuccessor(unsigned idx, BasicBlock *NewSucc) { assert(idx < getNumSuccessors() && "Successor # out of range for Branch!"); - setOperand(idx, reinterpret_cast<Value*>(NewSucc)); + setOperand(idx, NewSucc); } // Methods for support type inquiry through isa, cast, and dyn_cast: @@ -1691,6 +1747,15 @@ private: virtual void setSuccessorV(unsigned idx, BasicBlock *B); }; +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 +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value) + //===----------------------------------------------------------------------===// // SwitchInst Class //===----------------------------------------------------------------------===// @@ -1699,6 +1764,7 @@ private: /// SwitchInst - Multiway switch /// class SwitchInst : public TerminatorInst { + void *operator new(size_t, unsigned); // DO NOT IMPLEMENT unsigned ReservedSpace; // Operand[0] = Value to switch on // Operand[1] = Default basic block destination @@ -1707,6 +1773,10 @@ class SwitchInst : public TerminatorInst { SwitchInst(const SwitchInst &RI); void init(Value *Value, BasicBlock *Default, unsigned NumCases); void resizeOperands(unsigned No); + // allocate space for exactly zero operands + void *operator new(size_t s) { + return User::operator new(s, 0); + } /// SwitchInst ctor - Create a new switch instruction, specifying a value to /// switch on and a default destination. The number of additional cases can /// be specified here to make memory allocation more efficient. This @@ -1721,18 +1791,19 @@ class SwitchInst : public TerminatorInst { SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases, BasicBlock *InsertAtEnd); public: - static SwitchInst *Create(Value *Value, BasicBlock *Default, unsigned NumCases, - Instruction *InsertBefore = 0) { - return new(NumCases/*FIXME*/) - SwitchInst(Value, Default, NumCases, InsertBefore); + static SwitchInst *Create(Value *Value, BasicBlock *Default, + unsigned NumCases, Instruction *InsertBefore = 0) { + return new SwitchInst(Value, Default, NumCases, InsertBefore); } - static SwitchInst *Create(Value *Value, BasicBlock *Default, unsigned NumCases, - BasicBlock *InsertAtEnd) { - return new(NumCases/*FIXME*/) - SwitchInst(Value, Default, NumCases, InsertAtEnd); + static SwitchInst *Create(Value *Value, BasicBlock *Default, + unsigned NumCases, BasicBlock *InsertAtEnd) { + return new SwitchInst(Value, Default, NumCases, InsertAtEnd); } ~SwitchInst(); + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + // Accessor Methods for Switch stmt Value *getCondition() const { return getOperand(0); } void setCondition(Value *V) { setOperand(0, V); } @@ -1805,7 +1876,7 @@ public: } void setSuccessor(unsigned idx, BasicBlock *NewSucc) { assert(idx < getNumSuccessors() && "Successor # out of range for switch!"); - setOperand(idx*2+1, reinterpret_cast<Value*>(NewSucc)); + setOperand(idx*2+1, NewSucc); } // getSuccessorValue - Return the value associated with the specified @@ -1829,6 +1900,13 @@ private: virtual void setSuccessorV(unsigned idx, BasicBlock *B); }; +template <> +struct OperandTraits<SwitchInst> : HungoffOperandTraits<2> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SwitchInst, Value) + + //===----------------------------------------------------------------------===// // InvokeInst Class //===----------------------------------------------------------------------===// @@ -1866,15 +1944,10 @@ class InvokeInst : public TerminatorInst { /// /// @brief Construct an InvokeInst from a range of arguments template<typename InputIterator> - InvokeInst(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, - InputIterator ArgBegin, InputIterator ArgEnd, - const std::string &Name = "", Instruction *InsertBefore = 0) - : TerminatorInst(cast<FunctionType>(cast<PointerType>(Func->getType()) - ->getElementType())->getReturnType(), - Instruction::Invoke, 0, 0, InsertBefore) { - init(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + inline InvokeInst(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, + InputIterator ArgBegin, InputIterator ArgEnd, + unsigned Values, + const std::string &Name, Instruction *InsertBefore); /// Construct an InvokeInst given a range of arguments. /// InputIterator must be a random-access iterator pointing to @@ -1884,38 +1957,36 @@ class InvokeInst : public TerminatorInst { /// /// @brief Construct an InvokeInst from a range of arguments template<typename InputIterator> - InvokeInst(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, - InputIterator ArgBegin, InputIterator ArgEnd, - const std::string &Name, BasicBlock *InsertAtEnd) - : TerminatorInst(cast<FunctionType>(cast<PointerType>(Func->getType()) - ->getElementType())->getReturnType(), - Instruction::Invoke, 0, 0, InsertAtEnd) { - init(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, - typename std::iterator_traits<InputIterator>::iterator_category()); - } + inline InvokeInst(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, + InputIterator ArgBegin, InputIterator ArgEnd, + unsigned Values, + const std::string &Name, BasicBlock *InsertAtEnd); public: template<typename InputIterator> - static InvokeInst *Create(Value *Func, BasicBlock *IfNormal, - BasicBlock *IfException, + static InvokeInst *Create(Value *Func, + BasicBlock *IfNormal, BasicBlock *IfException, InputIterator ArgBegin, InputIterator ArgEnd, const std::string &Name = "", Instruction *InsertBefore = 0) { - return new(ArgEnd - ArgBegin + 3) - InvokeInst(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, InsertBefore); + unsigned Values(ArgEnd - ArgBegin + 3); + return new(Values) InvokeInst(Func, IfNormal, IfException, ArgBegin, ArgEnd, + Values, Name, InsertBefore); } template<typename InputIterator> - static InvokeInst *Create(Value *Func, BasicBlock *IfNormal, - BasicBlock *IfException, + static InvokeInst *Create(Value *Func, + BasicBlock *IfNormal, BasicBlock *IfException, InputIterator ArgBegin, InputIterator ArgEnd, const std::string &Name, BasicBlock *InsertAtEnd) { - return new(ArgEnd - ArgBegin + 3) - InvokeInst(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, InsertAtEnd); + unsigned Values(ArgEnd - ArgBegin + 3); + return new(Values) InvokeInst(Func, IfNormal, IfException, ArgBegin, ArgEnd, + Values, Name, InsertAtEnd); } - ~InvokeInst(); - virtual InvokeInst *clone() const; + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); + /// getCallingConv/setCallingConv - Get or set the calling convention of this /// function call. unsigned getCallingConv() const { return SubclassData; } @@ -1985,11 +2056,11 @@ public: return cast<BasicBlock>(getOperand(2)); } void setNormalDest(BasicBlock *B) { - setOperand(1, reinterpret_cast<Value*>(B)); + setOperand(1, B); } void setUnwindDest(BasicBlock *B) { - setOperand(2, reinterpret_cast<Value*>(B)); + setOperand(2, B); } BasicBlock *getSuccessor(unsigned i) const { @@ -1999,7 +2070,7 @@ public: void setSuccessor(unsigned idx, BasicBlock *NewSucc) { assert(idx < 2 && "Successor # out of range for invoke!"); - setOperand(idx+1, reinterpret_cast<Value*>(NewSucc)); + setOperand(idx+1, NewSucc); } unsigned getNumSuccessors() const { return 2; } @@ -2018,6 +2089,40 @@ private: virtual void setSuccessorV(unsigned idx, BasicBlock *B); }; +template <> +struct OperandTraits<InvokeInst> : VariadicOperandTraits<3> { +}; + +template<typename InputIterator> +InvokeInst::InvokeInst(Value *Func, + BasicBlock *IfNormal, BasicBlock *IfException, + InputIterator ArgBegin, InputIterator ArgEnd, + unsigned Values, + const std::string &Name, Instruction *InsertBefore) + : TerminatorInst(cast<FunctionType>(cast<PointerType>(Func->getType()) + ->getElementType())->getReturnType(), + Instruction::Invoke, + OperandTraits<InvokeInst>::op_end(this) - Values, + Values, InsertBefore) { + init(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} +template<typename InputIterator> +InvokeInst::InvokeInst(Value *Func, + BasicBlock *IfNormal, BasicBlock *IfException, + InputIterator ArgBegin, InputIterator ArgEnd, + unsigned Values, + const std::string &Name, BasicBlock *InsertAtEnd) + : TerminatorInst(cast<FunctionType>(cast<PointerType>(Func->getType()) + ->getElementType())->getReturnType(), + Instruction::Invoke, + OperandTraits<InvokeInst>::op_end(this) - Values, + Values, InsertAtEnd) { + init(Func, IfNormal, IfException, ArgBegin, ArgEnd, Name, + typename std::iterator_traits<InputIterator>::iterator_category()); +} + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InvokeInst, Value) //===----------------------------------------------------------------------===// // UnwindInst Class @@ -2572,11 +2677,10 @@ public: /// class GetResultInst : public /*FIXME: Unary*/Instruction { void *operator new(size_t, unsigned); // DO NOT IMPLEMENT - Use Aggr; unsigned Idx; GetResultInst(const GetResultInst &GRI) : - Instruction(GRI.getType(), Instruction::GetResult, &Aggr, 1) { - Aggr.init(GRI.Aggr, this); + Instruction(GRI.getType(), Instruction::GetResult, &Op<0>(), 1) { + Op<0>().init(GRI.Op<0>(), this); Idx = GRI.Idx; } @@ -2585,9 +2689,9 @@ public: void *operator new(size_t s) { return User::operator new(s, 1); } - explicit GetResultInst(Value *Aggr, unsigned index, - const std::string &Name = "", - Instruction *InsertBefore = 0); + GetResultInst(Value *Aggr, unsigned index, + const std::string &Name = "", + Instruction *InsertBefore = 0); /// isValidOperands - Return true if an getresult instruction can be /// formed with the specified operands. @@ -2607,7 +2711,8 @@ public: return Idx; } - unsigned getNumOperands() const { return 1; } + /// Provide fast operand accessors + DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const GetResultInst *) { return true; } @@ -2619,6 +2724,14 @@ public: } }; +// FIXME: these are redundant if GetResultInst < UnaryInstruction +template <> +struct OperandTraits<GetResultInst> : FixedNumOperandTraits<1> { +}; + +DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetResultInst, Value) + + } // End llvm namespace #endif diff --git a/include/llvm/OperandTraits.h b/include/llvm/OperandTraits.h new file mode 100644 index 0000000..3811927 --- /dev/null +++ b/include/llvm/OperandTraits.h @@ -0,0 +1,163 @@ +//===-- llvm/OperandTraits.h - OperandTraits class definition ---------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the traits classes that are handy for enforcing the correct +// layout of various User subclasses. It also provides the means for accessing +// the operands in the most efficient manner. +// + +#ifndef LLVM_OPERAND_TRAITS_H +#define LLVM_OPERAND_TRAITS_H + +#include "llvm/User.h" + +namespace llvm { + +//===----------------------------------------------------------------------===// +// FixedNumOperands Trait Class +//===----------------------------------------------------------------------===// + +template <unsigned ARITY> +struct FixedNumOperandTraits { + static Use *op_begin(User* U) { + return reinterpret_cast<Use*>(U) - ARITY; + } + static Use *op_end(User* U) { + return reinterpret_cast<Use*>(U); + } + static unsigned operands(const User*) { + return ARITY; + } + struct prefix { + Use Ops[ARITY]; + prefix(); // DO NOT IMPLEMENT + }; + template <class U> + struct Layout { + struct overlay : prefix, U { + overlay(); // DO NOT IMPLEMENT + }; + }; + static inline void *allocate(unsigned); // FIXME +}; + +//===----------------------------------------------------------------------===// +// OptionalOperands Trait Class +//===----------------------------------------------------------------------===// + +template <unsigned ARITY = 1> +struct OptionalOperandTraits : FixedNumOperandTraits<ARITY> { + static unsigned operands(const User *U) { + return U->getNumOperands(); + } +}; + +//===----------------------------------------------------------------------===// +// VariadicOperand Trait Class +//===----------------------------------------------------------------------===// + +template <unsigned MINARITY = 0> +struct VariadicOperandTraits { + static Use *op_begin(User* U) { + return reinterpret_cast<Use*>(U) - U->getNumOperands(); + } + static Use *op_end(User* U) { + return reinterpret_cast<Use*>(U); + } + static unsigned operands(const User *U) { + return U->getNumOperands(); + } + static inline void *allocate(unsigned); // FIXME +}; + +//===----------------------------------------------------------------------===// +// HungoffOperand Trait Class +//===----------------------------------------------------------------------===// + +template <unsigned MINARITY = 1> +struct HungoffOperandTraits { + static Use *op_begin(User* U) { + return U->OperandList; + } + static Use *op_end(User* U) { + return U->OperandList + U->getNumOperands(); + } + static unsigned operands(const User *U) { + return U->getNumOperands(); + } + static inline void *allocate(unsigned); // FIXME +}; + +/// Macro for generating in-class operand accessor declarations. +/// It should only be called in the public section of the interface. +/// +#define DECLARE_TRANSPARENT_OPERAND_ACCESSORS(VALUECLASS) \ + public: \ + inline VALUECLASS *getOperand(unsigned) const; \ + inline void setOperand(unsigned, VALUECLASS*); \ + protected: \ + template <unsigned> inline Use &Op(); \ + template <unsigned> inline const Use &Op() const; \ + public: \ + inline unsigned getNumOperands() const + +/// Macro for generating out-of-class operand accessor definitions +#define DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CLASS, VALUECLASS) \ +VALUECLASS *CLASS::getOperand(unsigned i_nocapture) const { \ + assert(i_nocapture < OperandTraits<CLASS>::operands(this) \ + && "getOperand() out of range!"); \ + return static_cast<VALUECLASS*>( \ + OperandTraits<CLASS>::op_begin(const_cast<CLASS*>(this))[i_nocapture]); \ +} \ +void CLASS::setOperand(unsigned i_nocapture, VALUECLASS *Val_nocapture) { \ + assert(i_nocapture < OperandTraits<CLASS>::operands(this) \ + && "setOperand() out of range!"); \ + OperandTraits<CLASS>::op_begin(this)[i_nocapture] = Val_nocapture; \ +} \ +unsigned CLASS::getNumOperands() const { \ + return OperandTraits<CLASS>::operands(this); \ +} \ +template <unsigned Idx_nocapture> Use &CLASS::Op() { \ + return OperandTraits<CLASS>::op_begin(this)[Idx_nocapture]; \ +} \ +template <unsigned Idx_nocapture> const Use &CLASS::Op() const { \ + return OperandTraits<CLASS>::op_begin( \ + const_cast<CLASS*>(this))[Idx_nocapture]; \ +} + + +/// Macro for generating out-of-class operand accessor +/// definitions with casted result +#define DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(CLASS, VALUECLASS) \ +VALUECLASS *CLASS::getOperand(unsigned i_nocapture) const { \ + assert(i_nocapture < OperandTraits<CLASS>::operands(this) \ + && "getOperand() out of range!"); \ + return cast<VALUECLASS>( \ + OperandTraits<CLASS>::op_begin(const_cast<CLASS*>(this))[i_nocapture]); \ +} \ +void CLASS::setOperand(unsigned i_nocapture, VALUECLASS *Val_nocapture) { \ + assert(i_nocapture < OperandTraits<CLASS>::operands(this) \ + && "setOperand() out of range!"); \ + OperandTraits<CLASS>::op_begin(this)[i_nocapture] = Val_nocapture; \ +} \ +unsigned CLASS::getNumOperands() const { \ + return OperandTraits<CLASS>::operands(this); \ +} \ +template <unsigned Idx_nocapture> Use &CLASS::Op() { \ + return OperandTraits<CLASS>::op_begin(this)[Idx_nocapture]; \ +} \ +template <unsigned Idx_nocapture> const Use &CLASS::Op() const { \ + return OperandTraits<CLASS>::op_begin( \ + const_cast<CLASS*>(this))[Idx_nocapture]; \ +} + + +} // End llvm namespace + +#endif diff --git a/include/llvm/Use.h b/include/llvm/Use.h index e050743..b4d4bda 100644 --- a/include/llvm/Use.h +++ b/include/llvm/Use.h @@ -26,6 +26,40 @@ class User; //===----------------------------------------------------------------------===// +// Generic Tagging Functions +//===----------------------------------------------------------------------===// + +/// Tag - generic tag type for (at least 32 bit) pointers +enum Tag { noTag, tagOne, tagTwo, tagThree }; + +/// addTag - insert tag bits into an (untagged) pointer +template <typename T, typename TAG> +inline T *addTag(const T *P, TAG Tag) { + return reinterpret_cast<T*>(ptrdiff_t(P) | Tag); +} + +/// stripTag - remove tag bits from a pointer, +/// making it dereferencable +template <ptrdiff_t MASK, typename T> +inline T *stripTag(const T *P) { + return reinterpret_cast<T*>(ptrdiff_t(P) & ~MASK); +} + +/// extractTag - extract tag bits from a pointer +template <typename TAG, TAG MASK, typename T> +inline TAG extractTag(const T *P) { + return TAG(ptrdiff_t(P) & MASK); +} + +/// transferTag - transfer tag bits from a pointer, +/// to an untagged pointer +template <ptrdiff_t MASK, typename T> +inline T *transferTag(const T *From, const T *To) { + return reinterpret_cast<T*>((ptrdiff_t(From) & MASK) | ptrdiff_t(To)); +} + + +//===----------------------------------------------------------------------===// // Use Class //===----------------------------------------------------------------------===// @@ -35,20 +69,36 @@ class Use { public: inline void init(Value *V, User *U); - Use(Value *V, User *U) { init(V, U); } - Use(const Use &U) { init(U.Val, U.U); } +private: + /// Allow std::swap some intimacy + template <typename U> friend void std::swap(U&, U&); + + /// Copy ctor - Only for std::swap + Use(const Use &U) { init(U.get(), 0); } + + /// Destructor - Only for zap() and std::swap inline ~Use() { - if (Val) removeFromList(); + if (get()) removeFromList(); } - /// Default ctor - This leaves the Use completely unitialized. The only thing + /// Default ctor - This leaves the Use completely uninitialized. The only thing /// that is valid to do with this use is to call the "init" method. - inline Use() : Val(0) {} + + inline Use() {} + enum PrevPtrTag { zeroDigitTag = noTag + , oneDigitTag = tagOne + , stopTag = tagTwo + , fullStopTag = tagThree }; + +public: operator Value*() const { return Val; } Value *get() const { return Val; } - User *getUser() const { return U; } + User *getUser() const; + const Use* getImpliedUser() const; + static Use *initTags(Use *Start, Use *Stop, ptrdiff_t Done = 0); + static void zap(Use *Start, const Use *Stop, bool del = false); inline void set(Value *Val); @@ -57,7 +107,7 @@ public: return RHS; } const Use &operator=(const Use &RHS) { - set(RHS.Val); + set(RHS.get()); return *this; } @@ -66,19 +116,22 @@ public: Use *getNext() const { return Next; } private: - Use *Next, **Prev; Value *Val; - User *U; + Use *Next, **Prev; + void setPrev(Use **NewPrev) { + Prev = transferTag<fullStopTag>(Prev, NewPrev); + } void addToList(Use **List) { Next = *List; - if (Next) Next->Prev = &Next; - Prev = List; + if (Next) Next->setPrev(&Next); + setPrev(List); *List = this; } void removeFromList() { - *Prev = Next; - if (Next) Next->Prev = Prev; + Use **StrippedPrev = stripTag<fullStopTag>(Prev); + *StrippedPrev = Next; + if (Next) Next->setPrev(StrippedPrev); } friend class Value; @@ -138,7 +191,7 @@ public: // Retrieve a reference to the current User UserTy *operator*() const { - assert(U && "Cannot increment end iterator!"); + assert(U && "Cannot dereference end iterator!"); return U->getUser(); } diff --git a/include/llvm/User.h b/include/llvm/User.h index d3e4f1e..1454779 100644 --- a/include/llvm/User.h +++ b/include/llvm/User.h @@ -23,15 +23,203 @@ namespace llvm { +/*============================================================================== + + + ----------------------------------------------------------------- + --- Interaction and relationship between User and Use objects --- + ----------------------------------------------------------------- + + +A subclass of User can choose between incorporating its Use objects +or refer to them out-of-line by means of a pointer. A mixed variant +(some Uses inline others hung off) is impractical and breaks the invariant +that the Use objects belonging to the same User form a contiguous array. + +We have 2 different layouts in the User (sub)classes: + +Layout a) +The Use object(s) are inside (resp. at fixed offset) of the User +object and there are a fixed number of them. + +Layout b) +The Use object(s) are referenced by a pointer to an +array from the User object and there may be a variable +number of them. + +Initially each layout will possess a direct pointer to the +start of the array of Uses. Though not mandatory for layout a), +we stick to this redundancy for the sake of simplicity. +The User object will also store the number of Use objects it +has. (Theoretically this information can also be calculated +given the scheme presented below.) + +Special forms of allocation operators (operator new) +will enforce the following memory layouts: + + +# Layout a) will be modelled by prepending the User object +# by the Use[] array. +# +# ...---.---.---.---.-------... +# | P | P | P | P | User +# '''---'---'---'---'-------''' + + +# Layout b) will be modelled by pointing at the Use[] array. +# +# .-------... +# | User +# '-------''' +# | +# v +# .---.---.---.---... +# | P | P | P | P | +# '---'---'---'---''' + + (In the above figures 'P' stands for the Use** that + is stored in each Use object in the member Use::Prev) + + +Since the Use objects will be deprived of the direct pointer to +their User objects, there must be a fast and exact method to +recover it. This is accomplished by the following scheme: + +A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the +start of the User object: + +00 --> binary digit 0 +01 --> binary digit 1 +10 --> stop and calc (s) +11 --> full stop (S) + +Given a Use*, all we have to do is to walk till we get +a stop and we either have a User immediately behind or +we have to walk to the next stop picking up digits +and calculating the offset: + +.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---------------- +| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*) +'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---------------- + |+15 |+10 |+6 |+3 |+1 + | | | | |__> + | | | |__________> + | | |______________________> + | |______________________________________> + |__________________________________________________________> + + +Only the significant number of bits need to be stored between the +stops, so that the worst case is 20 memory accesses when there are +1000 Use objects. + +The following literate Haskell fragment demonstrates the concept: + +> import Test.QuickCheck +> +> digits :: Int -> [Char] -> [Char] +> digits 0 acc = '0' : acc +> digits 1 acc = '1' : acc +> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc +> +> dist :: Int -> [Char] -> [Char] +> dist 0 [] = ['S'] +> dist 0 acc = acc +> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r +> dist n acc = dist (n - 1) $ dist 1 acc +> +> takeLast n ss = reverse $ take n $ reverse ss +> +> test = takeLast 40 $ dist 20 [] +> + +Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S" + +The reverse algorithm computes the +length of the string just by examining +a certain prefix: + +> pref :: [Char] -> Int +> pref "S" = 1 +> pref ('s':'1':rest) = decode 2 1 rest +> pref (_:rest) = 1 + pref rest +> +> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest +> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest +> decode walk acc _ = walk + acc +> + +Now, as expected, printing <pref test> gives 40. + +We can quickCheck this with following property: + +> testcase = dist 2000 [] +> testcaseLength = length testcase +> +> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr +> where arr = takeLast n testcase + +As expected <quickCheck identityProp> gives: + +*Main> quickCheck identityProp +OK, passed 100 tests. + +Let's be a bit more exhaustive: + +> +> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p +> + +And here is the result of <deepCheck identityProp>: + +*Main> deepCheck identityProp +OK, passed 500 tests. + + +To maintain the invariant that the 2 LSBits of each Use** in Use +never change after being set up, setters of Use::Prev must re-tag the +new Use** on every modification. Accordingly getters must strip the +tag bits. + +For layout b) instead of the User we will find a pointer (User* with LSBit set). +Following this pointer brings us to the User. A portable trick will ensure +that the first bytes of User (if interpreted as a pointer) will never have +the LSBit set. + +==============================================================================*/ + +/// OperandTraits - Compile-time customization of +/// operand-related allocators and accessors +/// for use of the User class +template <class> +struct OperandTraits; + +class User; + +/// OperandTraits<User> - specialization to User +template <> +struct OperandTraits<User> { + static inline Use *op_begin(User*); + static inline Use *op_end(User*); + static inline unsigned operands(const User*); + template <class U> + struct Layout { + typedef U overlay; + }; + static inline void *allocate(unsigned); +}; + class User : public Value { User(const User &); // Do not implement void *operator new(size_t); // Do not implement + template <unsigned> + friend struct HungoffOperandTraits; protected: /// OperandList - This is a pointer to the array of Users for this operand. /// For nodes of fixed arity (e.g. a binary operator) this array will live - /// embedded into the derived class. For nodes of variable arity - /// (e.g. ConstantArrays, CallInst, PHINodes, ReturnInst etc), this memory - /// will be dynamically allocated and should be destroyed by the classes + /// prefixed to the derived class. For nodes of resizable variable arity + /// (e.g. PHINodes, SwitchInst etc.), this memory will be dynamically + /// allocated and should be destroyed by the classes' /// virtual dtor. Use *OperandList; @@ -39,13 +227,43 @@ protected: /// unsigned NumOperands; - void *operator new(size_t s, size_t) { - return ::operator new(s); + void *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; } User(const Type *Ty, unsigned vty, Use *OpList, unsigned NumOps) : Value(Ty, vty), OperandList(OpList), NumOperands(NumOps) {} - + Use *allocHungoffUses(unsigned) const; + void dropHungoffUses(Use *U) { + if (OperandList == U) { + OperandList = 0; + NumOperands = 0; + } + Use::zap(U, U->getImpliedUser(), true); + } public: + ~User() { + Use::zap(OperandList, OperandList + NumOperands); + } + void 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); + } + template <unsigned Idx> Use &Op() { + return OperandTraits<User>::op_begin(this)[Idx]; + } + template <unsigned Idx> const Use &Op() const { + return OperandTraits<User>::op_begin(const_cast<User*>(this))[Idx]; + } Value *getOperand(unsigned i) const { assert(i < NumOperands && "getOperand() out of range!"); return OperandList[i]; @@ -93,6 +311,18 @@ public: } }; +inline Use *OperandTraits<User>::op_begin(User *U) { + return U->op_begin(); +} + +inline Use *OperandTraits<User>::op_end(User *U) { + return U->op_end(); +} + +inline unsigned OperandTraits<User>::operands(const User *U) { + return U->getNumOperands(); +} + template<> struct simplify_type<User::op_iterator> { typedef Value* SimpleType; diff --git a/include/llvm/Value.h b/include/llvm/Value.h index 2bcac08..2d6351d 100644 --- a/include/llvm/Value.h +++ b/include/llvm/Value.h @@ -232,10 +232,9 @@ inline std::ostream &operator<<(std::ostream &OS, const Value &V) { return OS; } -void Use::init(Value *v, User *user) { - Val = v; - U = user; - if (Val) Val->addUse(*this); +void Use::init(Value *V, User *user) { + Val = V; + if (V) V->addUse(*this); } void Use::set(Value *V) { |