MLIR  19.0.0git
Iterators.h
Go to the documentation of this file.
1 //===- Iterators.h - IR iterators for IR visitors ---------------*- 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 // The iterators defined in this file can be used together with IR visitors.
10 // Note: These iterators cannot be defined in Visitors.h because that would
11 // introduce a cyclic header dependency due to Operation.h.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef MLIR_IR_ITERATORS_H
16 #define MLIR_IR_ITERATORS_H
17 
18 #include "mlir/IR/Operation.h"
21 #include "mlir/Support/LLVM.h"
22 
23 #include "llvm/ADT/DepthFirstIterator.h"
24 #include "llvm/ADT/PostOrderIterator.h"
25 
26 namespace mlir {
27 /// This iterator enumerates elements in "reverse" order. It is a wrapper around
28 /// llvm::reverse.
30  // llvm::reverse uses RangeT::rbegin and RangeT::rend.
31  template <typename RangeT>
32  static constexpr auto makeIterable(RangeT &&range) {
33  return llvm::reverse(
34  ForwardIterator::makeIterable(std::forward<RangeT>(range)));
35  }
36 };
37 
38 /// This iterator enumerates elements according to their dominance relationship.
39 /// Operations and regions are enumerated in "forward" order. Blocks are
40 /// enumerated according to their successor relationship. Unreachable blocks are
41 /// not enumerated. Blocks may not be erased during the traversal.
42 ///
43 /// Note: If `NoGraphRegions` is set to "true", this iterator asserts that each
44 /// visited region has SSA dominance. In either case, the ops in such regions
45 /// are visited in forward order, but for regions without SSA dominance this
46 /// does not guarantee that defining ops are visited before their users.
47 template <bool NoGraphRegions = false>
49  static Block &makeIterable(Block &range) {
50  return ForwardIterator::makeIterable(range);
51  }
52 
53  static auto makeIterable(Region &region) {
54  if (NoGraphRegions) {
55  // Only regions with SSA dominance are allowed.
56  assert(mayHaveSSADominance(region) && "graph regions are not allowed");
57  }
58 
59  // Create DFS iterator. Blocks are enumerated according to their successor
60  // relationship.
61  Block *null = nullptr;
62  auto it = region.empty()
63  ? llvm::make_range(llvm::df_end(null), llvm::df_end(null))
64  : llvm::depth_first(&region.front());
65 
66  // Walk API expects Block references instead of pointers.
67  return llvm::make_pointee_range(it);
68  }
69 
71  return ForwardIterator::makeIterable(range);
72  }
73 };
74 
75 /// This iterator enumerates elements according to their reverse dominance
76 /// relationship. Operations and regions are enumerated in "reverse" order.
77 /// Blocks are enumerated according to their successor relationship, but
78 /// post-order. I.e., a block is visited after its successors have been visited.
79 /// Cycles in the block graph are broken in an unspecified way. Unreachable
80 /// blocks are not enumerated. Blocks may not be erased during the traversal.
81 ///
82 /// Note: If `NoGraphRegions` is set to "true", this iterator asserts that each
83 /// visited region has SSA dominance.
84 template <bool NoGraphRegions = false>
86  // llvm::reverse uses RangeT::rbegin and RangeT::rend.
87  static constexpr auto makeIterable(Block &range) {
88  return llvm::reverse(ForwardIterator::makeIterable(range));
89  }
90 
91  static constexpr auto makeIterable(Operation &range) {
92  return llvm::reverse(ForwardIterator::makeIterable(range));
93  }
94 
95  static auto makeIterable(Region &region) {
96  if (NoGraphRegions) {
97  // Only regions with SSA dominance are allowed.
98  assert(mayHaveSSADominance(region) && "graph regions are not allowed");
99  }
100 
101  // Create post-order iterator. Blocks are enumerated according to their
102  // successor relationship.
103  Block *null = nullptr;
104  auto it = region.empty()
105  ? llvm::make_range(llvm::po_end(null), llvm::po_end(null))
106  : llvm::post_order(&region.front());
107 
108  // Walk API expects Block references instead of pointers.
109  return llvm::make_pointee_range(it);
110  }
111 };
112 } // namespace mlir
113 
114 #endif // MLIR_IR_ITERATORS_H
Block represents an ordered list of Operations.
Definition: Block.h:31
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
bool empty()
Definition: Region.h:60
Block & front()
Definition: Region.h:65
Include the generated interface declarations.
bool mayHaveSSADominance(Region &region)
Return "true" if the given region may have SSA dominance.
This iterator enumerates elements according to their dominance relationship.
Definition: Iterators.h:48
static auto makeIterable(Region &region)
Definition: Iterators.h:53
static Block & makeIterable(Block &range)
Definition: Iterators.h:49
static MutableArrayRef< Region > makeIterable(Operation &range)
Definition: Iterators.h:70
static MutableArrayRef< Region > makeIterable(Operation &range)
Make operations iterable: return the list of regions.
Definition: Visitors.cpp:17
This iterator enumerates elements according to their reverse dominance relationship.
Definition: Iterators.h:85
static constexpr auto makeIterable(Block &range)
Definition: Iterators.h:87
static auto makeIterable(Region &region)
Definition: Iterators.h:95
static constexpr auto makeIterable(Operation &range)
Definition: Iterators.h:91
This iterator enumerates elements in "reverse" order.
Definition: Iterators.h:29
static constexpr auto makeIterable(RangeT &&range)
Definition: Iterators.h:32