• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 = &block;
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 &region, Region &limit,
147                             Optional<Location> noteLoc) {
148   assert(limit.isAncestor(&region) &&
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(&region);
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