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> makeIterableReverseIterator32 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 { makeIterableForwardDominanceIterator49 static Block &makeIterable(Block &range) { 50 return ForwardIterator::makeIterable(range); 51 } 52 makeIterableForwardDominanceIterator53 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(llvm::df_end(null), llvm::df_end(null)) 64 : llvm::depth_first(®ion.front()); 65 66 // Walk API expects Block references instead of pointers. 67 return llvm::make_pointee_range(it); 68 } 69 makeIterableForwardDominanceIterator70 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. makeIterableReverseDominanceIterator87 static constexpr auto makeIterable(Block &range) { 88 return llvm::reverse(ForwardIterator::makeIterable(range)); 89 } 90 makeIterableReverseDominanceIterator91 static constexpr auto makeIterable(Operation &range) { 92 return llvm::reverse(ForwardIterator::makeIterable(range)); 93 } 94 makeIterableReverseDominanceIterator95 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(llvm::po_end(null), llvm::po_end(null)) 106 : llvm::post_order(®ion.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 115