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" |
19 | #include "mlir/IR/RegionGraphTraits.h" |
20 | #include "mlir/IR/RegionKindInterface.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. |
29 | struct ReverseIterator { |
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> |
48 | struct ForwardDominanceIterator { |
49 | static Block &makeIterable(Block &range) { |
50 | return ForwardIterator::makeIterable(range); |
51 | } |
52 | |
53 | static auto makeIterable(Region ®ion) { |
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(x: llvm::df_end(G: null), y: llvm::df_end(G: null)) |
64 | : llvm::depth_first(G: ®ion.front()); |
65 | |
66 | // Walk API expects Block references instead of pointers. |
67 | return llvm::make_pointee_range(Range&: it); |
68 | } |
69 | |
70 | static MutableArrayRef<Region> makeIterable(Operation &range) { |
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> |
85 | struct ReverseDominanceIterator { |
86 | // llvm::reverse uses RangeT::rbegin and RangeT::rend. |
87 | static constexpr auto makeIterable(Block &range) { |
88 | return llvm::reverse(C&: ForwardIterator::makeIterable(range)); |
89 | } |
90 | |
91 | static constexpr auto makeIterable(Operation &range) { |
92 | return llvm::reverse(C: ForwardIterator::makeIterable(range)); |
93 | } |
94 | |
95 | static auto makeIterable(Region ®ion) { |
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(x: llvm::po_end(G: null), y: llvm::po_end(G: null)) |
106 | : llvm::post_order(G: ®ion.front()); |
107 | |
108 | // Walk API expects Block references instead of pointers. |
109 | return llvm::make_pointee_range(Range&: it); |
110 | } |
111 | }; |
112 | } // namespace mlir |
113 | |
114 | #endif // MLIR_IR_ITERATORS_H |
115 | |