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 *>(Val: CurTy)) |
104 | return T; |
105 | if (auto *VT = dyn_cast_if_present<VectorType *>(Val: CurTy)) |
106 | return VT->getElementType(); |
107 | return cast<StructType *>(Val: 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>(Val: Ty)) |
115 | CurTy = ATy->getElementType(); |
116 | else if (auto *VTy = dyn_cast<VectorType>(Val: Ty)) |
117 | CurTy = VTy; |
118 | else |
119 | CurTy = dyn_cast<StructType>(Val: 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 *>(Val: CurTy); } |
146 | bool isVector() const { return isa<VectorType *>(Val: 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(Ty: ElemTy); |
160 | } |
161 | return DL.getTypeAllocSize(Ty: ElemTy); |
162 | } |
163 | |
164 | StructType *getStructType() const { return cast<StructType *>(Val: CurTy); } |
165 | |
166 | StructType *getStructTypeOrNull() const { |
167 | return dyn_cast_if_present<StructType *>(Val: 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>(Val: GEP); |
175 | return gep_type_iterator::begin( |
176 | Ty: GEPOp->getSourceElementType(), |
177 | It: GEP->op_begin() + 1); |
178 | } |
179 | |
180 | inline gep_type_iterator gep_type_end(const User *GEP) { |
181 | return gep_type_iterator::end(It: GEP->op_end()); |
182 | } |
183 | |
184 | inline gep_type_iterator gep_type_begin(const User &GEP) { |
185 | auto &GEPOp = cast<GEPOperator>(Val: GEP); |
186 | return gep_type_iterator::begin( |
187 | Ty: GEPOp.getSourceElementType(), |
188 | It: GEP.op_begin() + 1); |
189 | } |
190 | |
191 | inline gep_type_iterator gep_type_end(const User &GEP) { |
192 | return gep_type_iterator::end(It: 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 | |