1 //===- Region.cpp - MLIR Region Class -------------------------------------===//
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 #include "mlir/IR/Region.h"
10 #include "mlir/IR/BlockAndValueMapping.h"
11 #include "mlir/IR/Operation.h"
12 using namespace mlir;
13
Region(Operation * container)14 Region::Region(Operation *container) : container(container) {}
15
~Region()16 Region::~Region() {
17 // Operations may have cyclic references, which need to be dropped before we
18 // can start deleting them.
19 dropAllReferences();
20 }
21
22 /// Return the context this region is inserted in. The region must have a valid
23 /// parent container.
getContext()24 MLIRContext *Region::getContext() {
25 assert(container && "region is not attached to a container");
26 return container->getContext();
27 }
28
29 /// Return a location for this region. This is the location attached to the
30 /// parent container. The region must have a valid parent container.
getLoc()31 Location Region::getLoc() {
32 assert(container && "region is not attached to a container");
33 return container->getLoc();
34 }
35
36 /// Return a range containing the types of the arguments for this region.
getArgumentTypes()37 auto Region::getArgumentTypes() -> ValueTypeRange<BlockArgListType> {
38 return ValueTypeRange<BlockArgListType>(getArguments());
39 }
40
41 /// Add one argument to the argument list for each type specified in the list.
addArguments(TypeRange types)42 iterator_range<Region::args_iterator> Region::addArguments(TypeRange types) {
43 return front().addArguments(types);
44 }
45
getParentRegion()46 Region *Region::getParentRegion() {
47 assert(container && "region is not attached to a container");
48 return container->getParentRegion();
49 }
50
getParentOp()51 Operation *Region::getParentOp() { return container; }
52
isProperAncestor(Region * other)53 bool Region::isProperAncestor(Region *other) {
54 if (this == other)
55 return false;
56
57 while ((other = other->getParentRegion())) {
58 if (this == other)
59 return true;
60 }
61 return false;
62 }
63
64 /// Return the number of this region in the parent operation.
getRegionNumber()65 unsigned Region::getRegionNumber() {
66 // Regions are always stored consecutively, so use pointer subtraction to
67 // figure out what number this is.
68 return this - &getParentOp()->getRegions()[0];
69 }
70
71 /// Clone the internal blocks from this region into `dest`. Any
72 /// cloned blocks are appended to the back of dest.
cloneInto(Region * dest,BlockAndValueMapping & mapper)73 void Region::cloneInto(Region *dest, BlockAndValueMapping &mapper) {
74 assert(dest && "expected valid region to clone into");
75 cloneInto(dest, dest->end(), mapper);
76 }
77
78 /// Clone this region into 'dest' before the given position in 'dest'.
cloneInto(Region * dest,Region::iterator destPos,BlockAndValueMapping & mapper)79 void Region::cloneInto(Region *dest, Region::iterator destPos,
80 BlockAndValueMapping &mapper) {
81 assert(dest && "expected valid region to clone into");
82 assert(this != dest && "cannot clone region into itself");
83
84 // If the list is empty there is nothing to clone.
85 if (empty())
86 return;
87
88 for (Block &block : *this) {
89 Block *newBlock = new Block();
90 mapper.map(&block, newBlock);
91
92 // Clone the block arguments. The user might be deleting arguments to the
93 // block by specifying them in the mapper. If so, we don't add the
94 // argument to the cloned block.
95 for (auto arg : block.getArguments())
96 if (!mapper.contains(arg))
97 mapper.map(arg, newBlock->addArgument(arg.getType()));
98
99 // Clone and remap the operations within this block.
100 for (auto &op : block)
101 newBlock->push_back(op.clone(mapper));
102
103 dest->getBlocks().insert(destPos, newBlock);
104 }
105
106 // Now that each of the blocks have been cloned, go through and remap the
107 // operands of each of the operations.
108 auto remapOperands = [&](Operation *op) {
109 for (auto &operand : op->getOpOperands())
110 if (auto mappedOp = mapper.lookupOrNull(operand.get()))
111 operand.set(mappedOp);
112 for (auto &succOp : op->getBlockOperands())
113 if (auto *mappedOp = mapper.lookupOrNull(succOp.get()))
114 succOp.set(mappedOp);
115 };
116
117 for (iterator it(mapper.lookup(&front())); it != destPos; ++it)
118 it->walk(remapOperands);
119 }
120
121 /// Returns 'block' if 'block' lies in this region, or otherwise finds the
122 /// ancestor of 'block' that lies in this region. Returns nullptr if the latter
123 /// fails.
findAncestorBlockInRegion(Block & block)124 Block *Region::findAncestorBlockInRegion(Block &block) {
125 auto currBlock = █
126 while (currBlock->getParent() != this) {
127 Operation *parentOp = currBlock->getParentOp();
128 if (!parentOp || !parentOp->getBlock())
129 return nullptr;
130 currBlock = parentOp->getBlock();
131 }
132 return currBlock;
133 }
134
dropAllReferences()135 void Region::dropAllReferences() {
136 for (Block &b : *this)
137 b.dropAllReferences();
138 }
139
140 /// Check if there are any values used by operations in `region` defined
141 /// outside its ancestor region `limit`. That is, given `A{B{C{}}}` with region
142 /// `C` and limit `B`, the values defined in `B` can be used but the values
143 /// defined in `A` cannot. Emit errors if `noteLoc` is provided; this location
144 /// is used to point to the operation containing the region, the actual error is
145 /// reported at the operation with an offending use.
isIsolatedAbove(Region & region,Region & limit,Optional<Location> noteLoc)146 static bool isIsolatedAbove(Region ®ion, Region &limit,
147 Optional<Location> noteLoc) {
148 assert(limit.isAncestor(®ion) &&
149 "expected isolation limit to be an ancestor of the given region");
150
151 // List of regions to analyze. Each region is processed independently, with
152 // respect to the common `limit` region, so we can look at them in any order.
153 // Therefore, use a simple vector and push/pop back the current region.
154 SmallVector<Region *, 8> pendingRegions;
155 pendingRegions.push_back(®ion);
156
157 // Traverse all operations in the region.
158 while (!pendingRegions.empty()) {
159 for (Operation &op : pendingRegions.pop_back_val()->getOps()) {
160 for (Value operand : op.getOperands()) {
161 // operand should be non-null here if the IR is well-formed. But
162 // we don't assert here as this function is called from the verifier
163 // and so could be called on invalid IR.
164 if (!operand) {
165 if (noteLoc)
166 op.emitOpError("block's operand not defined").attachNote(noteLoc);
167 return false;
168 }
169
170 // Check that any value that is used by an operation is defined in the
171 // same region as either an operation result or a block argument.
172 if (operand.getParentRegion()->isProperAncestor(&limit)) {
173 if (noteLoc) {
174 op.emitOpError("using value defined outside the region")
175 .attachNote(noteLoc)
176 << "required by region isolation constraints";
177 }
178 return false;
179 }
180 }
181 // Schedule any regions the operations contain for further checking.
182 pendingRegions.reserve(pendingRegions.size() + op.getNumRegions());
183 for (Region &subRegion : op.getRegions())
184 pendingRegions.push_back(&subRegion);
185 }
186 }
187 return true;
188 }
189
isIsolatedFromAbove(Optional<Location> noteLoc)190 bool Region::isIsolatedFromAbove(Optional<Location> noteLoc) {
191 return isIsolatedAbove(*this, *this, noteLoc);
192 }
193
getParentRegion()194 Region *llvm::ilist_traits<::mlir::Block>::getParentRegion() {
195 size_t Offset(
196 size_t(&((Region *)nullptr->*Region::getSublistAccess(nullptr))));
197 iplist<Block> *Anchor(static_cast<iplist<Block> *>(this));
198 return reinterpret_cast<Region *>(reinterpret_cast<char *>(Anchor) - Offset);
199 }
200
201 /// This is a trait method invoked when a basic block is added to a region.
202 /// We keep the region pointer up to date.
addNodeToList(Block * block)203 void llvm::ilist_traits<::mlir::Block>::addNodeToList(Block *block) {
204 assert(!block->getParent() && "already in a region!");
205 block->parentValidOpOrderPair.setPointer(getParentRegion());
206 }
207
208 /// This is a trait method invoked when an operation is removed from a
209 /// region. We keep the region pointer up to date.
removeNodeFromList(Block * block)210 void llvm::ilist_traits<::mlir::Block>::removeNodeFromList(Block *block) {
211 assert(block->getParent() && "not already in a region!");
212 block->parentValidOpOrderPair.setPointer(nullptr);
213 }
214
215 /// This is a trait method invoked when an operation is moved from one block
216 /// to another. We keep the block pointer up to date.
transferNodesFromList(ilist_traits<Block> & otherList,block_iterator first,block_iterator last)217 void llvm::ilist_traits<::mlir::Block>::transferNodesFromList(
218 ilist_traits<Block> &otherList, block_iterator first, block_iterator last) {
219 // If we are transferring operations within the same function, the parent
220 // pointer doesn't need to be updated.
221 auto *curParent = getParentRegion();
222 if (curParent == otherList.getParentRegion())
223 return;
224
225 // Update the 'parent' member of each Block.
226 for (; first != last; ++first)
227 first->parentValidOpOrderPair.setPointer(curParent);
228 }
229
230 //===----------------------------------------------------------------------===//
231 // Region::OpIterator
232 //===----------------------------------------------------------------------===//
233
OpIterator(Region * region,bool end)234 Region::OpIterator::OpIterator(Region *region, bool end)
235 : region(region), block(end ? region->end() : region->begin()) {
236 if (!region->empty())
237 skipOverBlocksWithNoOps();
238 }
239
operator ++()240 Region::OpIterator &Region::OpIterator::operator++() {
241 // We increment over operations, if we reach the last use then move to next
242 // block.
243 if (operation != block->end())
244 ++operation;
245 if (operation == block->end()) {
246 ++block;
247 skipOverBlocksWithNoOps();
248 }
249 return *this;
250 }
251
skipOverBlocksWithNoOps()252 void Region::OpIterator::skipOverBlocksWithNoOps() {
253 while (block != region->end() && block->empty())
254 ++block;
255
256 // If we are at the last block, then set the operation to first operation of
257 // next block (sentinel value used for end).
258 if (block == region->end())
259 operation = {};
260 else
261 operation = block->begin();
262 }
263
264 //===----------------------------------------------------------------------===//
265 // RegionRange
266 //===----------------------------------------------------------------------===//
267
RegionRange(MutableArrayRef<Region> regions)268 RegionRange::RegionRange(MutableArrayRef<Region> regions)
269 : RegionRange(regions.data(), regions.size()) {}
RegionRange(ArrayRef<std::unique_ptr<Region>> regions)270 RegionRange::RegionRange(ArrayRef<std::unique_ptr<Region>> regions)
271 : RegionRange(regions.data(), regions.size()) {}
272
273 /// See `llvm::detail::indexed_accessor_range_base` for details.
offset_base(const OwnerT & owner,ptrdiff_t index)274 RegionRange::OwnerT RegionRange::offset_base(const OwnerT &owner,
275 ptrdiff_t index) {
276 if (auto *operand = owner.dyn_cast<const std::unique_ptr<Region> *>())
277 return operand + index;
278 return &owner.get<Region *>()[index];
279 }
280 /// See `llvm::detail::indexed_accessor_range_base` for details.
dereference_iterator(const OwnerT & owner,ptrdiff_t index)281 Region *RegionRange::dereference_iterator(const OwnerT &owner,
282 ptrdiff_t index) {
283 if (auto *operand = owner.dyn_cast<const std::unique_ptr<Region> *>())
284 return operand[index].get();
285 return &owner.get<Region *>()[index];
286 }
287