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
26namespace mlir {
27/// This iterator enumerates elements in "reverse" order. It is a wrapper around
28/// llvm::reverse.
29struct 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.
47template <bool NoGraphRegions = false>
48struct ForwardDominanceIterator {
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(x: llvm::df_end(G: null), y: llvm::df_end(G: null))
64 : llvm::depth_first(G: &region.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.
84template <bool NoGraphRegions = false>
85struct 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 &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(x: llvm::po_end(G: null), y: llvm::po_end(G: null))
106 : llvm::post_order(G: &region.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

source code of mlir/include/mlir/IR/Iterators.h