1//===- InstIterator.h - Classes for inst iteration --------------*- 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 contains definitions of two iterators for iterating over the
10// instructions in a function.  This is effectively a wrapper around a two level
11// iterator that can probably be genericized later.
12//
13// Note that this iterator gets invalidated any time that basic blocks or
14// instructions are moved around.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_IR_INSTITERATOR_H
19#define LLVM_IR_INSTITERATOR_H
20
21#include "llvm/ADT/iterator_range.h"
22#include "llvm/IR/BasicBlock.h"
23#include "llvm/IR/Function.h"
24#include "llvm/IR/SymbolTableListTraits.h"
25#include <iterator>
26
27namespace llvm {
28
29// This class implements inst_begin() & inst_end() for
30// inst_iterator and const_inst_iterator's.
31//
32template <class BB_t, class BB_i_t, class BI_t, class II_t> class InstIterator {
33  using BBty = BB_t;
34  using BBIty = BB_i_t;
35  using BIty = BI_t;
36  using IIty = II_t;
37  BB_t *BBs; // BasicBlocksType
38  BB_i_t BB; // BasicBlocksType::iterator
39  BI_t BI;   // BasicBlock::iterator
40
41public:
42  using iterator_category = std::bidirectional_iterator_tag;
43  using value_type = IIty;
44  using difference_type = signed;
45  using pointer = IIty *;
46  using reference = IIty &;
47
48  // Default constructor
49  InstIterator() = default;
50
51  // Copy constructor...
52  template<typename A, typename B, typename C, typename D>
53  InstIterator(const InstIterator<A,B,C,D> &II)
54    : BBs(II.BBs), BB(II.BB), BI(II.BI) {}
55
56  template<typename A, typename B, typename C, typename D>
57  InstIterator(InstIterator<A,B,C,D> &II)
58    : BBs(II.BBs), BB(II.BB), BI(II.BI) {}
59
60  template<class M> InstIterator(M &m)
61    : BBs(&m.getBasicBlockList()), BB(BBs->begin()) {    // begin ctor
62    if (BB != BBs->end()) {
63      BI = BB->begin();
64      advanceToNextBB();
65    }
66  }
67
68  template<class M> InstIterator(M &m, bool)
69    : BBs(&m.getBasicBlockList()), BB(BBs->end()) {    // end ctor
70  }
71
72  // Accessors to get at the underlying iterators...
73  inline BBIty &getBasicBlockIterator()  { return BB; }
74  inline BIty  &getInstructionIterator() { return BI; }
75
76  inline reference operator*()  const { return *BI; }
77  inline pointer operator->() const { return &operator*(); }
78
79  inline bool operator==(const InstIterator &y) const {
80    return BB == y.BB && (BB == BBs->end() || BI == y.BI);
81  }
82  inline bool operator!=(const InstIterator& y) const {
83    return !operator==(y);
84  }
85
86  InstIterator& operator++() {
87    ++BI;
88    advanceToNextBB();
89    return *this;
90  }
91  inline InstIterator operator++(int) {
92    InstIterator tmp = *this; ++*this; return tmp;
93  }
94
95  InstIterator& operator--() {
96    while (BB == BBs->end() || BI == BB->begin()) {
97      --BB;
98      BI = BB->end();
99    }
100    --BI;
101    return *this;
102  }
103  inline InstIterator operator--(int) {
104    InstIterator tmp = *this; --*this; return tmp;
105  }
106
107  inline bool atEnd() const { return BB == BBs->end(); }
108
109private:
110  inline void advanceToNextBB() {
111    // The only way that the II could be broken is if it is now pointing to
112    // the end() of the current BasicBlock and there are successor BBs.
113    while (BI == BB->end()) {
114      ++BB;
115      if (BB == BBs->end()) break;
116      BI = BB->begin();
117    }
118  }
119};
120
121using inst_iterator =
122    InstIterator<SymbolTableList<BasicBlock>, Function::iterator,
123                 BasicBlock::iterator, Instruction>;
124using const_inst_iterator =
125    InstIterator<const SymbolTableList<BasicBlock>,
126                 Function::const_iterator, BasicBlock::const_iterator,
127                 const Instruction>;
128using inst_range = iterator_range<inst_iterator>;
129using const_inst_range = iterator_range<const_inst_iterator>;
130
131inline inst_iterator inst_begin(Function *F) { return inst_iterator(*F); }
132inline inst_iterator inst_end(Function *F)   { return inst_iterator(*F, true); }
133inline inst_range instructions(Function *F) {
134  return inst_range(inst_begin(F), inst_end(F));
135}
136inline const_inst_iterator inst_begin(const Function *F) {
137  return const_inst_iterator(*F);
138}
139inline const_inst_iterator inst_end(const Function *F) {
140  return const_inst_iterator(*F, true);
141}
142inline const_inst_range instructions(const Function *F) {
143  return const_inst_range(inst_begin(F), inst_end(F));
144}
145inline inst_iterator inst_begin(Function &F) { return inst_iterator(F); }
146inline inst_iterator inst_end(Function &F)   { return inst_iterator(F, true); }
147inline inst_range instructions(Function &F) {
148  return inst_range(inst_begin(F), inst_end(F));
149}
150inline const_inst_iterator inst_begin(const Function &F) {
151  return const_inst_iterator(F);
152}
153inline const_inst_iterator inst_end(const Function &F) {
154  return const_inst_iterator(F, true);
155}
156inline const_inst_range instructions(const Function &F) {
157  return const_inst_range(inst_begin(F), inst_end(F));
158}
159
160} // end namespace llvm
161
162#endif // LLVM_IR_INSTITERATOR_H
163