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/DerivedTypes.h"
20 #include "llvm/IR/Operator.h"
21 #include "llvm/IR/User.h"
22 #include "llvm/Support/Casting.h"
23 #include <cassert>
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     : public std::iterator<std::forward_iterator_tag, Type *, ptrdiff_t> {
33     using super = std::iterator<std::forward_iterator_tag, Type *, ptrdiff_t>;
34 
35     ItTy OpIt;
36     PointerUnion<StructType *, Type *> CurTy;
37     enum : uint64_t { Unbounded = -1ull };
38     uint64_t NumElements = Unbounded;
39 
40     generic_gep_type_iterator() = default;
41 
42   public:
43     static generic_gep_type_iterator begin(Type *Ty, ItTy It) {
44       generic_gep_type_iterator I;
45       I.CurTy = Ty;
46       I.OpIt = It;
47       return I;
48     }
49 
50     static generic_gep_type_iterator end(ItTy It) {
51       generic_gep_type_iterator I;
52       I.OpIt = It;
53       return I;
54     }
55 
56     bool operator==(const generic_gep_type_iterator& x) const {
57       return OpIt == x.OpIt;
58     }
59 
60     bool operator!=(const generic_gep_type_iterator& x) const {
61       return !operator==(x);
62     }
63 
64     // FIXME: Make this the iterator's operator*() after the 4.0 release.
65     // operator*() had a different meaning in earlier releases, so we're
66     // temporarily not giving this iterator an operator*() to avoid a subtle
67     // semantics break.
68     Type *getIndexedType() const {
69       if (auto *T = CurTy.dyn_cast<Type *>())
70         return T;
71       return CurTy.get<StructType *>()->getTypeAtIndex(getOperand());
72     }
73 
74     Value *getOperand() const { return const_cast<Value *>(&**OpIt); }
75 
76     generic_gep_type_iterator& operator++() {   // Preincrement
77       Type *Ty = getIndexedType();
78       if (auto *ATy = dyn_cast<ArrayType>(Ty)) {
79         CurTy = ATy->getElementType();
80         NumElements = ATy->getNumElements();
81       } else if (auto *VTy = dyn_cast<VectorType>(Ty)) {
82         CurTy = VTy->getElementType();
83         if (isa<ScalableVectorType>(VTy))
84           NumElements = Unbounded;
85         else
86           NumElements = cast<FixedVectorType>(VTy)->getNumElements();
87       } else
88         CurTy = dyn_cast<StructType>(Ty);
89       ++OpIt;
90       return *this;
91     }
92 
93     generic_gep_type_iterator operator++(int) { // Postincrement
94       generic_gep_type_iterator tmp = *this; ++*this; return tmp;
95     }
96 
97     // All of the below API is for querying properties of the "outer type", i.e.
98     // the type that contains the indexed type. Most of the time this is just
99     // the type that was visited immediately prior to the indexed type, but for
100     // the first element this is an unbounded array of the GEP's source element
101     // type, for which there is no clearly corresponding IR type (we've
102     // historically used a pointer type as the outer type in this case, but
103     // pointers will soon lose their element type).
104     //
105     // FIXME: Most current users of this class are just interested in byte
106     // offsets (a few need to know whether the outer type is a struct because
107     // they are trying to replace a constant with a variable, which is only
108     // legal for arrays, e.g. canReplaceOperandWithVariable in SimplifyCFG.cpp);
109     // we should provide a more minimal API here that exposes not much more than
110     // that.
111 
112     bool isStruct() const { return CurTy.is<StructType *>(); }
113     bool isSequential() const { return CurTy.is<Type *>(); }
114 
115     StructType *getStructType() const { return CurTy.get<StructType *>(); }
116 
117     StructType *getStructTypeOrNull() const {
118       return CurTy.dyn_cast<StructType *>();
119     }
120 
121     bool isBoundedSequential() const {
122       return isSequential() && NumElements != Unbounded;
123     }
124 
125     uint64_t getSequentialNumElements() const {
126       assert(isBoundedSequential());
127       return NumElements;
128     }
129   };
130 
131   using gep_type_iterator = generic_gep_type_iterator<>;
132 
133   inline gep_type_iterator gep_type_begin(const User *GEP) {
134     auto *GEPOp = cast<GEPOperator>(GEP);
135     return gep_type_iterator::begin(
136         GEPOp->getSourceElementType(),
137         GEP->op_begin() + 1);
138   }
139 
140   inline gep_type_iterator gep_type_end(const User *GEP) {
141     return gep_type_iterator::end(GEP->op_end());
142   }
143 
144   inline gep_type_iterator gep_type_begin(const User &GEP) {
145     auto &GEPOp = cast<GEPOperator>(GEP);
146     return gep_type_iterator::begin(
147         GEPOp.getSourceElementType(),
148         GEP.op_begin() + 1);
149   }
150 
151   inline gep_type_iterator gep_type_end(const User &GEP) {
152     return gep_type_iterator::end(GEP.op_end());
153   }
154 
155   template<typename T>
156   inline generic_gep_type_iterator<const T *>
157   gep_type_begin(Type *Op0, ArrayRef<T> A) {
158     return generic_gep_type_iterator<const T *>::begin(Op0, A.begin());
159   }
160 
161   template<typename T>
162   inline generic_gep_type_iterator<const T *>
163   gep_type_end(Type * /*Op0*/, ArrayRef<T> A) {
164     return generic_gep_type_iterator<const T *>::end(A.end());
165   }
166 
167 } // end namespace llvm
168 
169 #endif // LLVM_IR_GETELEMENTPTRTYPEITERATOR_H
170