IR: Change PointerType to derive from Type rather than SequentialType.

[pcc]

Summary

As proposed on llvm-dev:
http://lists.llvm.org/pipermail/llvm-dev/2016-October/106640.html

This is for a couple of reasons:

• Values of type PointerType are unlike the other SequentialTypes (arrays and vectors) in that they do not hold values of the element type. By moving PointerType we can unify certain aspects of how the other SequentialTypes are handled.
• PointerType will have no place in the SequentialType hierarchy once pointee types are removed, so this is a necessary step towards removing pointee types.

Depends on D26594

[dblaikie]

llvm/include/llvm/IR/DerivedTypes.h

316

Might be best to save the refactoring here for a separate patch - make things a bit easier to follow (ie: which bit makes PointerType not a SequentialType, and then which things are improvements now that all SequentialTypes have numElements, etc).

Maybe. Open to debate/discussion/disagreement for sure.

460–463

This should make it much easier for me to test how the typeless pointer work is progressing (previously I had to do a dynamic check in SequentialType::getElementType (assert(!isa<PointerType>) basically). Handy :)

[pcc]

Split out the getNumElements() change

[pcc]

llvm/include/llvm/IR/DerivedTypes.h

316

Seems reasonable enough. Done: : D27122

[dblaikie]

Looks generally good - I just don't understand how some of the changes are valid. Would be helpful to know.

llvm/lib/IR/ConstantFold.cpp

2208–2212

Is there a guarantee that it's never really a pointer type here?

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

178

This looks like it changes the behavior of the code.

Previously the code returned here if type was a PointerType - now it doesn't return, but continues into the rest of the function.

Is this just because type was never really a PointerType? (perhaps you could add an assert to that effect)

llvm/lib/Transforms/Scalar/SROA.cpp

3215–3219

This also appears to change the behavior - if Ty is a PointerType this code previously returned, now it skips this block and continues. Is this correct? Because Ty is never a PointerType here (add an assert?), or because the following code doesn't do anything if it is? (maybe still worth an early return defensively - oh, I see, after this block it returns if non-struct, so that's pretty obvious & maybe doesn't need anything extra)

[pcc]

llvm/lib/IR/ConstantFold.cpp

2208–2212

The purpose of this loop is to look through a notional GEP's element types. Earlier we initialized Ty to PointeeTy which, at the only call site [0], is the notional GEP's source element type. Because the source element type cannot be a pointer, and the same goes for later element types, having a pointer type here is impossible and this was dead code before.

[0] http://llvm-cs.pcc.me.uk/lib/IR/Constants.cpp#1906

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

178

Now that PointerTypes are no longer CompositeTypes, the return happens on line 175 above.

llvm/lib/Transforms/Scalar/SROA.cpp

3215–3219

Yes, I think the existing code is sufficient.

[pcc]

llvm/lib/IR/ConstantFold.cpp

2208–2212

Correction: the loop only looks at indexable element types. Of course the source element type could be a pointer (or any other type) if the GEP has only one operand, and the target element type may be non-indexable regardless of the number of operands. But this loop has (operands-1) iterations (see line 2189 above), which means that we never look at the target element type.

[dblaikie]

Looks like Phab might not've sent email - anyway, signed off on this. Carry on :)

llvm/docs/ProgrammersManual.rst

``IntegerType``
   ``IntegerType::MAX_INT_BITS`` (~8 million) can be represented.
 
   * ``static const IntegerType* get(unsigned NumBits)``: get an integer
     type of a specific bit width.
 
   * ``unsigned getBitWidth() const``: Get the bit width of an integer type.
 
 ``SequentialType``
-  This is subclassed by ArrayType, PointerType and VectorType.
+  This is subclassed by ArrayType and VectorType.
 
   * ``const Type * getElementType() const``: Returns the type of each
     of the elements in the sequential type.
 
 ``ArrayType``
   This is a subclass of SequentialType and defines the interface for array
   types.
 
   * ``unsigned getNumElements() const``: Returns the number of elements
     in the array.
 
 ``PointerType``
-  Subclass of SequentialType for pointer types.
+  Subclass of Type for pointer types.
 
 ``VectorType``
   Subclass of SequentialType for vector types.  A vector type is similar to an
   ArrayType but is distinguished because it is a first class type whereas
   ArrayType is not.  Vector types are used for vector operations and are usually
   small vectors of an integer or floating point type.
 
 ``StructType``

llvm/include/llvm/IR/DerivedTypes.h

 Type *Type::getFunctionParamType(unsigned i) const {
   return cast<FunctionType>(this)->getParamType(i);
 }
 
 unsigned Type::getFunctionNumParams() const {
   return cast<FunctionType>(this)->getNumParams();
 }
 
-/// Common super class of ArrayType, StructType, PointerType and VectorType.
+/// Common super class of ArrayType, StructType and VectorType.
 class CompositeType : public Type {
 protected:
   explicit CompositeType(LLVMContext &C, TypeID tid) : Type(C, tid) {}
 
 public:
   /// Given an index value into the type, return the type of the element.
   Type *getTypeAtIndex(const Value *V) const;
   Type *getTypeAtIndex(unsigned Idx) const;
   bool indexValid(const Value *V) const;
   bool indexValid(unsigned Idx) const;
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const Type *T) {
     return T->getTypeID() == ArrayTyID ||
            T->getTypeID() == StructTyID ||
-           T->getTypeID() == PointerTyID ||
            T->getTypeID() == VectorTyID;
   }
 };
 
 /// Class to represent struct types. There are two different kinds of struct
 /// types: Literal structs and Identified structs.
 ///
 /// Literal struct types (e.g. { i32, i32 }) are uniqued structurally, and must

 unsigned Type::getStructNumElements() const {
   return cast<StructType>(this)->getNumElements();
 }
 
 Type *Type::getStructElementType(unsigned N) const {
   return cast<StructType>(this)->getElementType(N);
 }
 
-/// This is the superclass of the array, pointer and vector type classes.
-/// All of these represent "arrays" in memory. The array type represents a
-/// specifically sized array, pointer types are unsized/unknown size arrays,
-/// vector types represent specifically sized arrays that allow for use of SIMD
-/// instructions. SequentialType holds the common features of all, which stem
-/// from the fact that all three lay their components out in memory identically.
+/// This is the superclass of the array and vector type classes. Both of these
+/// represent "arrays" in memory. The array type represents a specifically sized
+/// array, and the vector type represents a specifically sized array that allows
+/// for use of SIMD instructions. SequentialType holds the common features of
+/// both, which stem from the fact that both lay their components out in memory
+/// identically.
 class SequentialType : public CompositeType {
   Type *ContainedType;               ///< Storage for the single contained type.
   SequentialType(const SequentialType &) = delete;
   const SequentialType &operator=(const SequentialType &) = delete;
 
 protected:
   SequentialType(TypeID TID, Type *ElType)
     : CompositeType(ElType->getContext(), TID), ContainedType(ElType) {
     ContainedTys = &ContainedType;
     NumContainedTys = 1;
   }
 
 public:
   Type *getElementType() const { return getSequentialElementType(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const Type *T) {
     return T->getTypeID() == ArrayTyID ||
-           T->getTypeID() == PointerTyID ||
            T->getTypeID() == VectorTyID;
   }
 };
 
 /// Class to represent array types.
 class ArrayType : public SequentialType {
   uint64_t NumElements;
 
public:
   }
 };
 
 unsigned Type::getVectorNumElements() const {
   return cast<VectorType>(this)->getNumElements();
 }
 
 /// Class to represent pointers.
-class PointerType : public SequentialType {
+class PointerType : public Type {
   PointerType(const PointerType &) = delete;
   const PointerType &operator=(const PointerType &) = delete;
   explicit PointerType(Type *ElType, unsigned AddrSpace);
 
+  Type *PointeeTy;
+
 public:
   /// This constructs a pointer to an object of the specified type in a numbered
   /// address space.
   static PointerType *get(Type *ElementType, unsigned AddressSpace);
 
   /// This constructs a pointer to an object of the specified type in the
   /// generic address space (address space zero).
   static PointerType *getUnqual(Type *ElementType) {
     return PointerType::get(ElementType, 0);
   }
 
+  Type *getElementType() const {
+    return PointeeTy;
+  }
+
   /// Return true if the specified type is valid as a element type.
   static bool isValidElementType(Type *ElemTy);
 
   /// Return true if we can load or store from a pointer to this type.
   static bool isLoadableOrStorableType(Type *ElemTy);
 
   /// Return the address space of the Pointer type.
   inline unsigned getAddressSpace() const { return getSubclassData(); }

llvm/include/llvm/IR/Instructions.h

GetElementPtrInst *GEP =
         Create(PointeeType, Ptr, IdxList, NameStr, InsertAtEnd);
     GEP->setIsInBounds(true);
     return GEP;
   }
 
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
-  // getType - Overload to return most specific sequential type.
-  SequentialType *getType() const {
-    return cast<SequentialType>(Instruction::getType());
-  }
-
   Type *getSourceElementType() const { return SourceElementType; }
 
   void setSourceElementType(Type *Ty) { SourceElementType = Ty; }
   void setResultElementType(Type *Ty) { ResultElementType = Ty; }
 
   Type *getResultElementType() const {
     assert(ResultElementType ==
            cast<PointerType>(getType()->getScalarType())->getElementType());

llvm/include/llvm/IR/Type.h

protected:
   /// A pointer to the array of Types contained by this Type. For example, this
   /// includes the arguments of a function type, the elements of a structure,
   /// the pointee of a pointer, the element type of an array, etc. This pointer
   /// may be 0 for types that don't contain other types (Integer, Double,
   /// Float).
   Type * const *ContainedTys;
 
   static bool isSequentialType(TypeID TyID) {
-    return TyID == ArrayTyID || TyID == PointerTyID || TyID == VectorTyID;
+    return TyID == ArrayTyID || TyID == VectorTyID;
   }
 
 public:
   /// Print the current type.
   /// Omit the type details if \p NoDetails == true.
   /// E.g., let %st = type { i32, i16 }
   /// When \p NoDetails is true, we only print %st.
   /// Put differently, \p NoDetails prints the type as if

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getGEPExpr(GEPOperator *GEP,
   // instruction to its SCEV, because the Instruction may be guarded by control
   // flow and the no-overflow bits may not be valid for the expression in any
   // context. This can be fixed similarly to how these flags are handled for
   // adds.
   SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW
                                              : SCEV::FlagAnyWrap;
 
   const SCEV *TotalOffset = getZero(IntPtrTy);
-  // The address space is unimportant. The first thing we do on CurTy is getting
+  // The array size is unimportant. The first thing we do on CurTy is getting
   // its element type.
-  Type *CurTy = PointerType::getUnqual(GEP->getSourceElementType());
+  Type *CurTy = ArrayType::get(GEP->getSourceElementType(), 0);
   for (const SCEV *IndexExpr : IndexExprs) {
     // Compute the (potentially symbolic) offset in bytes for this index.
     if (StructType *STy = dyn_cast<StructType>(CurTy)) {
       // For a struct, add the member offset.
       ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue();
       unsigned FieldNo = Index->getZExtValue();
       const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo);
 

llvm/lib/IR/ConstantFold.cpp

if (PointerType *DPTy = dyn_cast<PointerType>(DestTy))
         Type *ElTy = PTy->getElementType();
         while (ElTy != DPTy->getElementType()) {
           if (StructType *STy = dyn_cast<StructType>(ElTy)) {
             if (STy->getNumElements() == 0) break;
             ElTy = STy->getElementType(0);
             IdxList.push_back(Zero);
           } else if (SequentialType *STy =
                      dyn_cast<SequentialType>(ElTy)) {
-            if (ElTy->isPointerTy()) break;  // Can't index into pointers!
             ElTy = STy->getElementType();
             IdxList.push_back(Zero);
           } else {
             break;
           }
         }
 
         if (ElTy == DPTy->getElementType())
if (InRangeIndex && i == *InRangeIndex + 1) {
       // the wrong element.
       continue;
     }
     if (isa<StructType>(Ty)) {
       // The verify makes sure that GEPs into a struct are in range.
       continue;
     }
     auto *STy = cast<SequentialType>(Ty);
-    if (isa<PointerType>(STy)) {
-      // We don't know if it's in range or not.
-      Unknown = true;
-      continue;
-    }
     if (isa<VectorType>(STy)) {
       // There can be awkward padding in after a non-power of two vector.
       Unknown = true;
       continue;
     }
     if (isIndexInRangeOfArrayType(isa<ArrayType>(STy)
                                       ? cast<ArrayType>(STy)->getNumElements()
                                       : cast<VectorType>(STy)->getNumElements(),
                                   CI))
       // It's in range, skip to the next index.
       continue;
-    if (!isa<SequentialType>(Prev)) {
+    if (isa<StructType>(Prev)) {
       // It's out of range, but the prior dimension is a struct
       // so we can't do anything about it.
       Unknown = true;
       continue;
     }
     if (CI->getSExtValue() < 0) {
       // It's out of range and negative, don't try to factor it.
       Unknown = true;

llvm/lib/IR/Core.cpp

 LLVMTypeRef LLVMPointerType(LLVMTypeRef ElementType, unsigned AddressSpace) {
   return wrap(PointerType::get(unwrap(ElementType), AddressSpace));
 }
 
 LLVMTypeRef LLVMVectorType(LLVMTypeRef ElementType, unsigned ElementCount) {
   return wrap(VectorType::get(unwrap(ElementType), ElementCount));
 }
 
-LLVMTypeRef LLVMGetElementType(LLVMTypeRef Ty) {
-  return wrap(unwrap<SequentialType>(Ty)->getElementType());
+LLVMTypeRef LLVMGetElementType(LLVMTypeRef WrappedTy) {
+  auto *Ty = unwrap<Type>(WrappedTy);
+  if (auto *PTy = dyn_cast<PointerType>(Ty))
+    return wrap(PTy->getElementType());
+  return wrap(cast<SequentialType>(Ty)->getElementType());
 }
 
 unsigned LLVMGetArrayLength(LLVMTypeRef ArrayTy) {
   return unwrap<ArrayType>(ArrayTy)->getNumElements();
 }
 
 unsigned LLVMGetPointerAddressSpace(LLVMTypeRef PointerTy) {
   return unwrap<PointerType>(PointerTy)->getAddressSpace();

llvm/lib/IR/Type.cpp

PointerType *PointerType::get(Type *EltTy, unsigned AddressSpace) {
 
   if (!Entry)
     Entry = new (CImpl->TypeAllocator) PointerType(EltTy, AddressSpace);
   return Entry;
 }
 
 
 PointerType::PointerType(Type *E, unsigned AddrSpace)
-  : SequentialType(PointerTyID, E) {
+  : Type(E->getContext(), PointerTyID), PointeeTy(E) {
+  ContainedTys = &PointeeTy;
+  NumContainedTys = 1;
   setSubclassData(AddrSpace);
 }
 
 PointerType *Type::getPointerTo(unsigned addrs) const {
   return PointerType::get(const_cast<Type*>(this), addrs);
 }
 
 bool PointerType::isValidElementType(Type *ElemTy) {
   return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
          !ElemTy->isMetadataTy() && !ElemTy->isTokenTy();
 }
 
 bool PointerType::isLoadableOrStorableType(Type *ElemTy) {
   return isValidElementType(ElemTy) && !ElemTy->isFunctionTy();
 }

llvm/lib/Target/Hexagon/HexagonCommonGEP.cpp

GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
       else
         Parent = N->Parent;
     }
     friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
   };
 
 
   Type *next_type(Type *Ty, Value *Idx) {
+    if (auto *PTy = dyn_cast<PointerType>(Ty))
+      return PTy->getElementType();
     // Advance the type.
     if (!Ty->isStructTy()) {
       Type *NexTy = cast<SequentialType>(Ty)->getElementType();
       return NexTy;
     }
     // Otherwise it is a struct type.
     ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
     assert(CI && "Struct type with non-constant index");

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

static bool isDenselyPacked(Type *type, const DataLayout &DL) {
   // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
   if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
     return false;
 
   if (!isa<CompositeType>(type))
     return true;
 
   // For homogenous sequential types, check for padding within members.
   if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
-    return isa<PointerType>(seqTy) ||
-           isDenselyPacked(seqTy->getElementType(), DL);
+    return isDenselyPacked(seqTy->getElementType(), DL);
 
   // Check for padding within and between elements of a struct.
   StructType *StructTy = cast<StructType>(type);
   const StructLayout *Layout = DL.getStructLayout(StructTy);
   uint64_t StartPos = 0;
   for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
     Type *ElTy = StructTy->getElementType(i);
     if (!isDenselyPacked(ElTy, DL))
for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
             for (unsigned long II : ArgIndex.second) {
               // Use i32 to index structs, and i64 for others (pointers/arrays).
               // This satisfies GEP constraints.
               Type *IdxTy = (ElTy->isStructTy() ?
                     Type::getInt32Ty(F->getContext()) : 
                     Type::getInt64Ty(F->getContext()));
               Ops.push_back(ConstantInt::get(IdxTy, II));
               // Keep track of the type we're currently indexing.
+              if (auto *ElPTy = dyn_cast<PointerType>(ElTy))
+                ElTy = ElPTy->getElementType();
+              else
                 ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(II);
             }
             // And create a GEP to extract those indices.
             V = GetElementPtrInst::Create(ArgIndex.first, V, Ops,
                                           V->getName() + ".idx", Call);
             Ops.clear();
           }
           // Since we're replacing a load make sure we take the alignment
           // of the previous load.

llvm/lib/Transforms/Scalar/SROA.cpp

 static Type *getTypePartition(const DataLayout &DL, Type *Ty, uint64_t Offset,
                               uint64_t Size) {
   if (Offset == 0 && DL.getTypeAllocSize(Ty) == Size)
     return stripAggregateTypeWrapping(DL, Ty);
   if (Offset > DL.getTypeAllocSize(Ty) ||
       (DL.getTypeAllocSize(Ty) - Offset) < Size)
     return nullptr;
 
   if (SequentialType *SeqTy = dyn_cast<SequentialType>(Ty)) {
-    // We can't partition pointers...
-    if (SeqTy->isPointerTy())
-      return nullptr;
-
     Type *ElementTy = SeqTy->getElementType();
     uint64_t ElementSize = DL.getTypeAllocSize(ElementTy);
     uint64_t NumSkippedElements = Offset / ElementSize;
     if (ArrayType *ArrTy = dyn_cast<ArrayType>(SeqTy)) {
       if (NumSkippedElements >= ArrTy->getNumElements())
         return nullptr;
     } else if (VectorType *VecTy = dyn_cast<VectorType>(SeqTy)) {
       if (NumSkippedElements >= VecTy->getNumElements())