1 //===- Block.h - MLIR Block Class -------------------------------*- 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 // This file defines the Block class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef MLIR_IR_BLOCK_H 14 #define MLIR_IR_BLOCK_H 15 16 #include "mlir/IR/BlockSupport.h" 17 #include "mlir/IR/Visitors.h" 18 19 namespace llvm { 20 class BitVector; 21 } // end namespace llvm 22 23 namespace mlir { 24 class TypeRange; 25 template <typename ValueRangeT> 26 class ValueTypeRange; 27 28 /// `Block` represents an ordered list of `Operation`s. 29 class Block : public IRObjectWithUseList<BlockOperand>, 30 public llvm::ilist_node_with_parent<Block, Region> { 31 public: Block()32 explicit Block() {} 33 ~Block(); 34 clear()35 void clear() { 36 // Drop all references from within this block. 37 dropAllReferences(); 38 39 // Clear operations in the reverse order so that uses are destroyed 40 // before their defs. 41 while (!empty()) 42 operations.pop_back(); 43 } 44 45 /// Provide a 'getParent' method for ilist_node_with_parent methods. 46 /// We mark it as a const function because ilist_node_with_parent specifically 47 /// requires a 'getParent() const' method. Once ilist_node removes this 48 /// constraint, we should drop the const to fit the rest of the MLIR const 49 /// model. 50 Region *getParent() const; 51 52 /// Returns the closest surrounding operation that contains this block. 53 Operation *getParentOp(); 54 55 /// Return if this block is the entry block in the parent region. 56 bool isEntryBlock(); 57 58 /// Insert this block (which must not already be in a region) right before 59 /// the specified block. 60 void insertBefore(Block *block); 61 62 /// Unlink this block from its current region and insert it right before the 63 /// specific block. 64 void moveBefore(Block *block); 65 66 /// Unlink this Block from its parent region and delete it. 67 void erase(); 68 69 //===--------------------------------------------------------------------===// 70 // Block argument management 71 //===--------------------------------------------------------------------===// 72 73 // This is the list of arguments to the block. 74 using BlockArgListType = MutableArrayRef<BlockArgument>; 75 getArguments()76 BlockArgListType getArguments() { return arguments; } 77 78 /// Return a range containing the types of the arguments for this block. 79 ValueTypeRange<BlockArgListType> getArgumentTypes(); 80 81 using args_iterator = BlockArgListType::iterator; 82 using reverse_args_iterator = BlockArgListType::reverse_iterator; args_begin()83 args_iterator args_begin() { return getArguments().begin(); } args_end()84 args_iterator args_end() { return getArguments().end(); } args_rbegin()85 reverse_args_iterator args_rbegin() { return getArguments().rbegin(); } args_rend()86 reverse_args_iterator args_rend() { return getArguments().rend(); } 87 args_empty()88 bool args_empty() { return arguments.empty(); } 89 90 /// Add one value to the argument list. 91 BlockArgument addArgument(Type type, Optional<Location> loc = {}); 92 93 /// Insert one value to the position in the argument list indicated by the 94 /// given iterator. The existing arguments are shifted. The block is expected 95 /// not to have predecessors. 96 BlockArgument insertArgument(args_iterator it, Type type, 97 Optional<Location> loc = {}); 98 99 /// Add one argument to the argument list for each type specified in the list. 100 iterator_range<args_iterator> addArguments(TypeRange types, 101 ArrayRef<Location> locs = {}); 102 103 /// Add one value to the argument list at the specified position. 104 BlockArgument insertArgument(unsigned index, Type type, 105 Optional<Location> loc = {}); 106 107 /// Erase the argument at 'index' and remove it from the argument list. 108 void eraseArgument(unsigned index); 109 /// Erases the arguments listed in `argIndices` and removes them from the 110 /// argument list. 111 /// `argIndices` is allowed to have duplicates and can be in any order. 112 void eraseArguments(ArrayRef<unsigned> argIndices); 113 /// Erases the arguments that have their corresponding bit set in 114 /// `eraseIndices` and removes them from the argument list. 115 void eraseArguments(const llvm::BitVector &eraseIndices); 116 /// Erases arguments using the given predicate. If the predicate returns true, 117 /// that argument is erased. 118 void eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn); 119 getNumArguments()120 unsigned getNumArguments() { return arguments.size(); } getArgument(unsigned i)121 BlockArgument getArgument(unsigned i) { return arguments[i]; } 122 123 //===--------------------------------------------------------------------===// 124 // Operation list management 125 //===--------------------------------------------------------------------===// 126 127 /// This is the list of operations in the block. 128 using OpListType = llvm::iplist<Operation>; getOperations()129 OpListType &getOperations() { return operations; } 130 131 // Iteration over the operations in the block. 132 using iterator = OpListType::iterator; 133 using reverse_iterator = OpListType::reverse_iterator; 134 begin()135 iterator begin() { return operations.begin(); } end()136 iterator end() { return operations.end(); } rbegin()137 reverse_iterator rbegin() { return operations.rbegin(); } rend()138 reverse_iterator rend() { return operations.rend(); } 139 empty()140 bool empty() { return operations.empty(); } push_back(Operation * op)141 void push_back(Operation *op) { operations.push_back(op); } push_front(Operation * op)142 void push_front(Operation *op) { operations.push_front(op); } 143 back()144 Operation &back() { return operations.back(); } front()145 Operation &front() { return operations.front(); } 146 147 /// Returns 'op' if 'op' lies in this block, or otherwise finds the 148 /// ancestor operation of 'op' that lies in this block. Returns nullptr if 149 /// the latter fails. 150 /// TODO: This is very specific functionality that should live somewhere else, 151 /// probably in Dominance.cpp. 152 Operation *findAncestorOpInBlock(Operation &op); 153 154 /// This drops all operand uses from operations within this block, which is 155 /// an essential step in breaking cyclic dependences between references when 156 /// they are to be deleted. 157 void dropAllReferences(); 158 159 /// This drops all uses of values defined in this block or in the blocks of 160 /// nested regions wherever the uses are located. 161 void dropAllDefinedValueUses(); 162 163 /// Returns true if the ordering of the child operations is valid, false 164 /// otherwise. 165 bool isOpOrderValid(); 166 167 /// Invalidates the current ordering of operations. 168 void invalidateOpOrder(); 169 170 /// Verifies the current ordering of child operations matches the 171 /// validOpOrder flag. Returns false if the order is valid, true otherwise. 172 bool verifyOpOrder(); 173 174 /// Recomputes the ordering of child operations within the block. 175 void recomputeOpOrder(); 176 177 /// This class provides iteration over the held operations of a block for a 178 /// specific operation type. 179 template <typename OpT> 180 using op_iterator = detail::op_iterator<OpT, iterator>; 181 182 /// Return an iterator range over the operations within this block that are of 183 /// 'OpT'. 184 template <typename OpT> getOps()185 iterator_range<op_iterator<OpT>> getOps() { 186 auto endIt = end(); 187 return {detail::op_filter_iterator<OpT, iterator>(begin(), endIt), 188 detail::op_filter_iterator<OpT, iterator>(endIt, endIt)}; 189 } 190 template <typename OpT> op_begin()191 op_iterator<OpT> op_begin() { 192 return detail::op_filter_iterator<OpT, iterator>(begin(), end()); 193 } 194 template <typename OpT> op_end()195 op_iterator<OpT> op_end() { 196 return detail::op_filter_iterator<OpT, iterator>(end(), end()); 197 } 198 199 /// Return an iterator range over the operation within this block excluding 200 /// the terminator operation at the end. without_terminator()201 iterator_range<iterator> without_terminator() { 202 if (begin() == end()) 203 return {begin(), end()}; 204 auto endIt = --end(); 205 return {begin(), endIt}; 206 } 207 208 //===--------------------------------------------------------------------===// 209 // Terminator management 210 //===--------------------------------------------------------------------===// 211 212 /// Get the terminator operation of this block. This function asserts that 213 /// the block has a valid terminator operation. 214 Operation *getTerminator(); 215 216 //===--------------------------------------------------------------------===// 217 // Predecessors and successors. 218 //===--------------------------------------------------------------------===// 219 220 // Predecessor iteration. 221 using pred_iterator = PredecessorIterator; pred_begin()222 pred_iterator pred_begin() { 223 return pred_iterator((BlockOperand *)getFirstUse()); 224 } pred_end()225 pred_iterator pred_end() { return pred_iterator(nullptr); } getPredecessors()226 iterator_range<pred_iterator> getPredecessors() { 227 return {pred_begin(), pred_end()}; 228 } 229 230 /// Return true if this block has no predecessors. hasNoPredecessors()231 bool hasNoPredecessors() { return pred_begin() == pred_end(); } 232 233 /// Returns true if this blocks has no successors. hasNoSuccessors()234 bool hasNoSuccessors() { return succ_begin() == succ_end(); } 235 236 /// If this block has exactly one predecessor, return it. Otherwise, return 237 /// null. 238 /// 239 /// Note that if a block has duplicate predecessors from a single block (e.g. 240 /// if you have a conditional branch with the same block as the true/false 241 /// destinations) is not considered to be a single predecessor. 242 Block *getSinglePredecessor(); 243 244 /// If this block has a unique predecessor, i.e., all incoming edges originate 245 /// from one block, return it. Otherwise, return null. 246 Block *getUniquePredecessor(); 247 248 // Indexed successor access. 249 unsigned getNumSuccessors(); 250 Block *getSuccessor(unsigned i); 251 252 // Successor iteration. 253 using succ_iterator = SuccessorRange::iterator; succ_begin()254 succ_iterator succ_begin() { return getSuccessors().begin(); } succ_end()255 succ_iterator succ_end() { return getSuccessors().end(); } getSuccessors()256 SuccessorRange getSuccessors() { return SuccessorRange(this); } 257 258 //===--------------------------------------------------------------------===// 259 // Operation Walkers 260 //===--------------------------------------------------------------------===// 261 262 /// Walk the operations in this block. The callback method is called for each 263 /// nested region, block or operation, depending on the callback provided. 264 /// Regions, blocks and operations at the same nesting level are visited in 265 /// lexicographical order. The walk order for enclosing regions, blocks and 266 /// operations with respect to their nested ones is specified by 'Order' 267 /// (post-order by default). A callback on a block or operation is allowed to 268 /// erase that block or operation if either: 269 /// * the walk is in post-order, or 270 /// * the walk is in pre-order and the walk is skipped after the erasure. 271 /// See Operation::walk for more details. 272 template <WalkOrder Order = WalkOrder::PostOrder, typename FnT, 273 typename RetT = detail::walkResultType<FnT>> walk(FnT && callback)274 RetT walk(FnT &&callback) { 275 return walk<Order>(begin(), end(), std::forward<FnT>(callback)); 276 } 277 278 /// Walk the operations in the specified [begin, end) range of this block. The 279 /// callback method is called for each nested region, block or operation, 280 /// depending on the callback provided. Regions, blocks and operations at the 281 /// same nesting level are visited in lexicographical order. The walk order 282 /// for enclosing regions, blocks and operations with respect to their nested 283 /// ones is specified by 'Order' (post-order by default). This method is 284 /// invoked for void-returning callbacks. A callback on a block or operation 285 /// is allowed to erase that block or operation only if the walk is in 286 /// post-order. See non-void method for pre-order erasure. 287 /// See Operation::walk for more details. 288 template <WalkOrder Order = WalkOrder::PostOrder, typename FnT, 289 typename RetT = detail::walkResultType<FnT>> 290 typename std::enable_if<std::is_same<RetT, void>::value, RetT>::type walk(Block::iterator begin,Block::iterator end,FnT && callback)291 walk(Block::iterator begin, Block::iterator end, FnT &&callback) { 292 for (auto &op : llvm::make_early_inc_range(llvm::make_range(begin, end))) 293 detail::walk<Order>(&op, callback); 294 } 295 296 /// Walk the operations in the specified [begin, end) range of this block. The 297 /// callback method is called for each nested region, block or operation, 298 /// depending on the callback provided. Regions, blocks and operations at the 299 /// same nesting level are visited in lexicographical order. The walk order 300 /// for enclosing regions, blocks and operations with respect to their nested 301 /// ones is specified by 'Order' (post-order by default). This method is 302 /// invoked for skippable or interruptible callbacks. A callback on a block or 303 /// operation is allowed to erase that block or operation if either: 304 /// * the walk is in post-order, or 305 /// * the walk is in pre-order and the walk is skipped after the erasure. 306 /// See Operation::walk for more details. 307 template <WalkOrder Order = WalkOrder::PostOrder, typename FnT, 308 typename RetT = detail::walkResultType<FnT>> 309 typename std::enable_if<std::is_same<RetT, WalkResult>::value, RetT>::type walk(Block::iterator begin,Block::iterator end,FnT && callback)310 walk(Block::iterator begin, Block::iterator end, FnT &&callback) { 311 for (auto &op : llvm::make_early_inc_range(llvm::make_range(begin, end))) 312 if (detail::walk<Order>(&op, callback).wasInterrupted()) 313 return WalkResult::interrupt(); 314 return WalkResult::advance(); 315 } 316 317 //===--------------------------------------------------------------------===// 318 // Other 319 //===--------------------------------------------------------------------===// 320 321 /// Split the block into two blocks before the specified operation or 322 /// iterator. 323 /// 324 /// Note that all operations BEFORE the specified iterator stay as part of 325 /// the original basic block, and the rest of the operations in the original 326 /// block are moved to the new block, including the old terminator. The 327 /// original block is left without a terminator. 328 /// 329 /// The newly formed Block is returned, and the specified iterator is 330 /// invalidated. 331 Block *splitBlock(iterator splitBefore); splitBlock(Operation * splitBeforeOp)332 Block *splitBlock(Operation *splitBeforeOp) { 333 return splitBlock(iterator(splitBeforeOp)); 334 } 335 336 /// Returns pointer to member of operation list. getSublistAccess(Operation *)337 static OpListType Block::*getSublistAccess(Operation *) { 338 return &Block::operations; 339 } 340 341 void print(raw_ostream &os); 342 void print(raw_ostream &os, AsmState &state); 343 void dump(); 344 345 /// Print out the name of the block without printing its body. 346 /// NOTE: The printType argument is ignored. We keep it for compatibility 347 /// with LLVM dominator machinery that expects it to exist. 348 void printAsOperand(raw_ostream &os, bool printType = true); 349 void printAsOperand(raw_ostream &os, AsmState &state); 350 351 private: 352 /// Pair of the parent object that owns this block and a bit that signifies if 353 /// the operations within this block have a valid ordering. 354 llvm::PointerIntPair<Region *, /*IntBits=*/1, bool> parentValidOpOrderPair; 355 356 /// This is the list of operations in the block. 357 OpListType operations; 358 359 /// This is the list of arguments to the block. 360 std::vector<BlockArgument> arguments; 361 362 Block(Block &) = delete; 363 void operator=(Block &) = delete; 364 365 friend struct llvm::ilist_traits<Block>; 366 }; 367 } // end namespace mlir 368 369 #endif // MLIR_IR_BLOCK_H 370