1 //===- GetElementPtrTypeIterator.h ------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements an iterator for walking through the types indexed by 10 // getelementptr instructions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_IR_GETELEMENTPTRTYPEITERATOR_H 15 #define LLVM_IR_GETELEMENTPTRTYPEITERATOR_H 16 17 #include "llvm/ADT/ArrayRef.h" 18 #include "llvm/ADT/PointerUnion.h" 19 #include "llvm/IR/DataLayout.h" 20 #include "llvm/IR/DerivedTypes.h" 21 #include "llvm/IR/Operator.h" 22 #include "llvm/IR/User.h" 23 #include "llvm/Support/Casting.h" 24 #include <cstddef> 25 #include <cstdint> 26 #include <iterator> 27 28 namespace llvm { 29 30 template <typename ItTy = User::const_op_iterator> 31 class generic_gep_type_iterator { 32 33 ItTy OpIt; 34 // We use two different mechanisms to store the type a GEP index applies to. 35 // In some cases, we need to know the outer aggregate type the index is 36 // applied within, e.g. a struct. In such cases, we store the aggregate type 37 // in the iterator, and derive the element type on the fly. 38 // 39 // However, this is not always possible, because for the outermost index there 40 // is no containing type. In such cases, or if the containing type is not 41 // relevant, e.g. for arrays, the element type is stored as Type* in CurTy. 42 // 43 // If CurTy contains a Type* value, this does not imply anything about the 44 // type itself, because it is the element type and not the outer type. 45 // In particular, Type* can be a struct type. 46 // 47 // Consider this example: 48 // 49 // %my.struct = type { i32, [ 4 x float ] } 50 // [...] 51 // %gep = getelementptr %my.struct, ptr %ptr, i32 10, i32 1, 32 3 52 // 53 // Iterating over the indices of this GEP, CurTy will contain the following 54 // values: 55 // * i32 10: The outer index always operates on the GEP value type. 56 // CurTy contains a Type* pointing at `%my.struct`. 57 // * i32 1: This index is within a struct. 58 // CurTy contains a StructType* pointing at `%my.struct`. 59 // * i32 3: This index is within an array. We reuse the "flat" indexing 60 // for arrays which is also used in the top level GEP index. 61 // CurTy contains a Type* pointing at `float`. 62 // 63 // Vectors are handled separately because the layout of vectors is different 64 // for overaligned elements: Vectors are always bit-packed, whereas arrays 65 // respect ABI alignment of the elements. 66 PointerUnion<StructType *, VectorType *, Type *> CurTy; 67 68 generic_gep_type_iterator() = default; 69 70 public: 71 using iterator_category = std::forward_iterator_tag; 72 using value_type = Type *; 73 using difference_type = std::ptrdiff_t; 74 using pointer = value_type *; 75 using reference = value_type &; 76 77 static generic_gep_type_iterator begin(Type *Ty, ItTy It) { 78 generic_gep_type_iterator I; 79 I.CurTy = Ty; 80 I.OpIt = It; 81 return I; 82 } 83 84 static generic_gep_type_iterator end(ItTy It) { 85 generic_gep_type_iterator I; 86 I.OpIt = It; 87 return I; 88 } 89 90 bool operator==(const generic_gep_type_iterator &x) const { 91 return OpIt == x.OpIt; 92 } 93 94 bool operator!=(const generic_gep_type_iterator &x) const { 95 return !operator==(x); 96 } 97 98 // FIXME: Make this the iterator's operator*() after the 4.0 release. 99 // operator*() had a different meaning in earlier releases, so we're 100 // temporarily not giving this iterator an operator*() to avoid a subtle 101 // semantics break. 102 Type *getIndexedType() const { 103 if (auto *T = dyn_cast_if_present<Type *>(CurTy)) 104 return T; 105 if (auto *VT = dyn_cast_if_present<VectorType *>(CurTy)) 106 return VT->getElementType(); 107 return cast<StructType *>(CurTy)->getTypeAtIndex(getOperand()); 108 } 109 110 Value *getOperand() const { return const_cast<Value *>(&**OpIt); } 111 112 generic_gep_type_iterator &operator++() { // Preincrement 113 Type *Ty = getIndexedType(); 114 if (auto *ATy = dyn_cast<ArrayType>(Ty)) 115 CurTy = ATy->getElementType(); 116 else if (auto *VTy = dyn_cast<VectorType>(Ty)) 117 CurTy = VTy; 118 else 119 CurTy = dyn_cast<StructType>(Ty); 120 ++OpIt; 121 return *this; 122 } 123 124 generic_gep_type_iterator operator++(int) { // Postincrement 125 generic_gep_type_iterator tmp = *this; 126 ++*this; 127 return tmp; 128 } 129 130 // All of the below API is for querying properties of the "outer type", i.e. 131 // the type that contains the indexed type. Most of the time this is just 132 // the type that was visited immediately prior to the indexed type, but for 133 // the first element this is an unbounded array of the GEP's source element 134 // type, for which there is no clearly corresponding IR type (we've 135 // historically used a pointer type as the outer type in this case, but 136 // pointers will soon lose their element type). 137 // 138 // FIXME: Most current users of this class are just interested in byte 139 // offsets (a few need to know whether the outer type is a struct because 140 // they are trying to replace a constant with a variable, which is only 141 // legal for arrays, e.g. canReplaceOperandWithVariable in SimplifyCFG.cpp); 142 // we should provide a more minimal API here that exposes not much more than 143 // that. 144 145 bool isStruct() const { return isa<StructType *>(CurTy); } 146 bool isVector() const { return isa<VectorType *>(CurTy); } 147 bool isSequential() const { return !isStruct(); } 148 149 // For sequential GEP indices (all except those into structs), the index value 150 // can be translated into a byte offset by multiplying with an element stride. 151 // This function returns this stride, which both depends on the element type, 152 // and the containing aggregate type, as vectors always tightly bit-pack their 153 // elements. 154 TypeSize getSequentialElementStride(const DataLayout &DL) const { 155 assert(isSequential()); 156 Type *ElemTy = getIndexedType(); 157 if (isVector()) { 158 assert(DL.typeSizeEqualsStoreSize(ElemTy) && "Not byte-addressable"); 159 return DL.getTypeStoreSize(ElemTy); 160 } 161 return DL.getTypeAllocSize(ElemTy); 162 } 163 164 StructType *getStructType() const { return cast<StructType *>(CurTy); } 165 166 StructType *getStructTypeOrNull() const { 167 return dyn_cast_if_present<StructType *>(CurTy); 168 } 169 }; 170 171 using gep_type_iterator = generic_gep_type_iterator<>; 172 173 inline gep_type_iterator gep_type_begin(const User *GEP) { 174 auto *GEPOp = cast<GEPOperator>(GEP); 175 return gep_type_iterator::begin( 176 GEPOp->getSourceElementType(), 177 GEP->op_begin() + 1); 178 } 179 180 inline gep_type_iterator gep_type_end(const User *GEP) { 181 return gep_type_iterator::end(GEP->op_end()); 182 } 183 184 inline gep_type_iterator gep_type_begin(const User &GEP) { 185 auto &GEPOp = cast<GEPOperator>(GEP); 186 return gep_type_iterator::begin( 187 GEPOp.getSourceElementType(), 188 GEP.op_begin() + 1); 189 } 190 191 inline gep_type_iterator gep_type_end(const User &GEP) { 192 return gep_type_iterator::end(GEP.op_end()); 193 } 194 195 template<typename T> 196 inline generic_gep_type_iterator<const T *> 197 gep_type_begin(Type *Op0, ArrayRef<T> A) { 198 return generic_gep_type_iterator<const T *>::begin(Op0, A.begin()); 199 } 200 201 template<typename T> 202 inline generic_gep_type_iterator<const T *> 203 gep_type_end(Type * /*Op0*/, ArrayRef<T> A) { 204 return generic_gep_type_iterator<const T *>::end(A.end()); 205 } 206 207 } // end namespace llvm 208 209 #endif // LLVM_IR_GETELEMENTPTRTYPEITERATOR_H 210