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
28namespace llvm {
29
30template <typename ItTy = User::const_op_iterator>
31class 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
70public:
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

source code of llvm/include/llvm/IR/GetElementPtrTypeIterator.h