Lines Matching full:block
16 // entry and single exit block into structured control flow operations
25 // single exit block containing an instance of that return-like operation.
46 // entry block and a single latch containing the only back edge to the entry
47 // block and the only edge to an exit block outside the loop. Rerouting control
78 // bbM in the above is the multiplexer block, and any block previously branching
79 // to an entry block of the region are redirected to it. This includes any
80 // branches from within the region. Using a block argument, bbM then dispatches
81 // to the correct entry block of the region dependent on the predecessor.
83 // A similar transformation is done to create the latch block with the single
110 // single entry block is created using a multiplexer block as shown above.
113 // followed by the operations of the entry block of Region T.
129 /// Returns the mutable operand range used to transfer operands from `block` to
133 getMutableSuccessorOperands(Block *block, unsigned successorIndex) { in getMutableSuccessorOperands() argument
134 auto branchOpInterface = cast<BranchOpInterface>(block->getTerminator()); in getMutableSuccessorOperands()
140 /// Return the operand range used to transfer operands from `block` to its
142 static OperandRange getSuccessorOperands(Block *block, in getSuccessorOperands() argument
144 return getMutableSuccessorOperands(block, successorIndex); in getSuccessorOperands()
147 /// Appends all the block arguments from `other` to the block arguments of
148 /// `block`, copying their types and locations.
149 static void addBlockArgumentsFromOther(Block *block, Block *other) { in addBlockArgumentsFromOther() argument
151 block->addArgument(arg.getType(), arg.getLoc()); in addBlockArgumentsFromOther()
156 /// Class representing an edge in the CFG. Consists of a from-block, a successor
157 /// and corresponding successor operands passed to the block arguments of the
160 Block *fromBlock;
166 Edge(Block *fromBlock, unsigned int successorIndex) in Edge()
169 /// Returns the from-block.
170 Block *getFromBlock() const { return fromBlock; } in getFromBlock()
173 Block *getSuccessor() const { in getSuccessor()
178 /// from-block.
179 void setSuccessor(Block *block) const { in setSuccessor()
180 fromBlock->getTerminator()->setSuccessor(block, successorIndex); in setSuccessor()
183 /// Returns the arguments of this edge that are passed to the block arguments
189 /// Returns the arguments of this edge that are passed to the block arguments
200 /// All edges from a block outside the cycle to a block inside the cycle.
203 /// All edges from a block inside the cycle to a block outside the cycle.
205 /// All edges from a block inside the cycle to an entry block.
210 /// This class creates a new basic block and routes all inputs edges
211 /// to this basic block before branching to their original target.
217 /// the `entryBlocks`. This creates the multiplexer basic block with
218 /// appropriate block arguments after the first entry block. `extraArgs`
219 /// contains the types of possible extra block arguments passed to the
220 /// multiplexer block that are added to the successor operands of every
224 /// multiplexer block nor code dispatching from the multiplexer code
227 static EdgeMultiplexer create(Location loc, ArrayRef<Block *> entryBlocks, in create()
231 assert(!entryBlocks.empty() && "Require at least one entry block");
233 auto *multiplexerBlock = new Block;
236 // To implement the multiplexer block, we have to add the block arguments of
237 // every distinct successor block to the multiplexer block. When redirecting
238 // edges, block arguments designated for blocks that aren't branched to will
239 // be assigned the `getUndefValue`. The amount of block arguments and their
241 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;
242 for (Block *entryBlock : entryBlocks) {
265 /// Returns the created multiplexer block.
266 Block *getMultiplexerBlock() const { return multiplexerBlock; } in getMultiplexerBlock()
268 /// Redirects `edge` to branch to the multiplexer block before continuing to
280 // Extra arguments are always appended at the end of the block arguments.
292 // Original block arguments to the entry block.
311 // Otherwise undef values for any unused block arguments used by other
322 /// The builder's insertion point has to be in a block dominated by the
323 /// multiplexer block. All edges to the multiplexer block must have already
327 const SmallPtrSetImpl<Block *> &excluded = SmallPtrSet<Block *, 1>{}) {
333 SmallVector<Block *> caseDestinations;
352 Block *defaultDest = caseDestinations.pop_back_val();
363 /// Newly created multiplexer block.
364 Block *multiplexerBlock;
371 /// Mapping of the block arguments of an entry block to the corresponding
372 /// block arguments in the multiplexer block. Block arguments of an entry
373 /// block are simply appended ot the multiplexer block. This map simply
374 /// contains the offset to the range in the multiplexer block.
375 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;
376 /// Discriminator value used in the multiplexer block to dispatch to the
377 /// correct entry block. Null value if not required due to only having one
378 /// entry block.
381 EdgeMultiplexer(Block *multiplexerBlock, in EdgeMultiplexer()
384 llvm::SmallMapVector<Block *, unsigned, 4> &&entries, in EdgeMultiplexer() argument
419 /// Utility-class for transforming a region to only have one single block for
426 /// Transforms `returnLikeOp` to a branch to the only block in the
435 Block *exitBlock = iter->second; in combineExit()
437 exitBlock = new Block; in combineExit()
461 /// Mapping of return-like operation to block. All return-like operations
464 llvm::SmallDenseMap<Operation *, Block *, 4, ReturnLikeOpEquivalence>
472 /// Returns a range of all edges from `block` to each of its successors.
473 static auto successorEdges(Block *block) { in successorEdges() argument
474 return llvm::map_range(llvm::seq(block->getNumSuccessors()), in successorEdges()
475 [=](unsigned index) { return Edge(block, index); }); in successorEdges()
480 calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) { in calculateCycleEdges() argument
482 SmallPtrSet<Block *, 8> entryBlocks; in calculateCycleEdges()
486 for (Block *block : cycles) { in calculateCycleEdges()
487 for (auto pred = block->pred_begin(); pred != block->pred_end(); pred++) { in calculateCycleEdges()
492 entryBlocks.insert(block); in calculateCycleEdges()
495 for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) { in calculateCycleEdges()
499 result.exitEdges.emplace_back(block, succIndex); in calculateCycleEdges()
504 for (Block *block : cycles) { in calculateCycleEdges()
505 for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) { in calculateCycleEdges()
509 result.backEdges.emplace_back(block, succIndex); in calculateCycleEdges()
516 /// Creates a single entry block out of multiple entry edges using an edge
542 /// * The back edge originates from the same block as the exit edge.
544 /// Block containing both the single exit edge and the single back edge.
545 Block *latch;
548 /// Exit block which is the only successor of the loop.
549 Block *exitBlock;
554 /// exiting edge, originating from the same block.
564 // First create the multiplexer block, which will be our latch, for all back in createSingleExitingLatch()
566 // block which indicates whether the latch was reached from what was in createSingleExitingLatch()
567 // originally a back edge or an exit block. in createSingleExitingLatch()
569 SmallVector<Block *> successors; in createSingleExitingLatch()
580 // Create a separate exit block that comes right after the latch. in createSingleExitingLatch()
581 auto *exitBlock = new Block; in createSingleExitingLatch()
585 Block *loopHeader = backEdges.front().getSuccessor(); in createSingleExitingLatch()
599 // exit block otherwise. in createSingleExitingLatch()
620 SmallPtrSet<Block *, 1> excluded = {loopHeader}; in createSingleExitingLatch()
644 /// (1) The block arguments and successor operands of the exit block are equal
645 /// to the block arguments of the loop header and the successor operands
650 /// at the end of the block. Rather, the "loop iteration arguments" from the
658 transformToReduceLoop(Block *loopHeader, Block *exitBlock, in transformToReduceLoop()
659 const llvm::SmallSetVector<Block *, 4> &loopBlocks, in transformToReduceLoop() argument
662 Block *latch = exitBlock->getSinglePredecessor(); in transformToReduceLoop()
664 "Exit block must have only latch as predecessor at this point"); in transformToReduceLoop()
666 "Exit block mustn't have any block arguments at this point"); in transformToReduceLoop()
684 // Add all values used in the next iteration to the exit block. Replace in transformToReduceLoop()
685 // any uses that are outside the loop with the newly created exit block. in transformToReduceLoop()
694 // Loop below might add block arguments to the latch and loop header. in transformToReduceLoop()
695 // Save the block arguments prior to the loop to not process these. in transformToReduceLoop()
702 // outside the loop body, create a block argument on the exit block and loop in transformToReduceLoop()
703 // header and replace the outside uses with the exit block argument. in transformToReduceLoop()
704 // The loop header block argument is added to satisfy requirement (1) in the in transformToReduceLoop()
706 for (Block *loopBlock : loopBlocks) { in transformToReduceLoop()
709 // definitions within a block. in transformToReduceLoop()
710 llvm::SmallDenseMap<Block *, bool> dominanceCache; in transformToReduceLoop()
711 // Returns true if `loopBlock` dominates `block`. in transformToReduceLoop()
712 auto loopBlockDominates = [&](Block *block) { in transformToReduceLoop() argument
713 auto [iter, inserted] = dominanceCache.insert({block, false}); in transformToReduceLoop()
716 iter->second = dominanceInfo.dominates(loopBlock, block); in transformToReduceLoop()
724 // of the loop. If the block is part of the loop, then the value does in transformToReduceLoop()
726 Block *currBlock = use.getOwner()->getBlock(); in transformToReduceLoop()
732 // Block argument is only created the first time it is required. in transformToReduceLoop()
738 // `value` might be defined in a block that does not dominate `latch` in transformToReduceLoop()
739 // but previously dominated an exit block with a use. in transformToReduceLoop()
740 // In this case, add a block argument to the latch and go through all in transformToReduceLoop()
743 // The above is unnecessary if the value is a block argument of the in transformToReduceLoop()
747 llvm::any_of(latch->getPredecessors(), [&](Block *pred) { in transformToReduceLoop()
782 // New block arguments may have been added to the loop header. in transformToReduceLoop()
803 static FailureOr<SmallVector<Block *>> transformCyclesToSCFLoops( in transformCyclesToSCFLoops()
804 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue, in transformCyclesToSCFLoops()
807 SmallVector<Block *> newSubRegions; in transformCyclesToSCFLoops()
817 llvm::SmallSetVector<Block *, 4> cycleBlockSet(scc->begin(), scc->end()); in transformCyclesToSCFLoops()
821 Block *loopHeader = edges.entryEdges.front().getSuccessor(); in transformCyclesToSCFLoops()
822 // First turn the cycle into a loop by creating a single entry block if in transformCyclesToSCFLoops()
846 Block *latchBlock = loopProperties->latch; in transformCyclesToSCFLoops()
847 Block *exitBlock = loopProperties->exitBlock; in transformCyclesToSCFLoops()
855 // Create a block acting as replacement for the loop header and insert in transformCyclesToSCFLoops()
857 auto *newLoopParentBlock = new Block; in transformCyclesToSCFLoops()
863 // Make sure the loop header is the entry block. in transformCyclesToSCFLoops()
865 for (Block *block : cycleBlockSet) in transformCyclesToSCFLoops()
866 if (block != latchBlock && block != loopHeader) in transformCyclesToSCFLoops()
867 loopBody.push_back(blocks.remove(block)); in transformCyclesToSCFLoops()
868 // And the latch is the last block. in transformCyclesToSCFLoops()
890 // Merge the exit block right after the loop operation. in transformCyclesToSCFLoops()
900 /// and single-exit. This is done by simply creating an empty block if there
901 /// is more than one block with an edge to the continuation block. All blocks
902 /// with edges to the continuation are then redirected to this block. A region
903 /// terminator is later placed into the block.
905 ArrayRef<Block *> branchRegion, Block *continuation, in createSingleExitBranchRegion()
906 SmallVectorImpl<std::pair<Block *, SmallVector<Value>>> &createdEmptyBlocks, in createSingleExitBranchRegion() argument
908 Block *singleExitBlock = nullptr; in createSingleExitBranchRegion()
912 for (Block *block : branchRegion) { in createSingleExitBranchRegion()
913 for (Edge edge : successorEdges(block)) { in createSingleExitBranchRegion()
923 // single exit block and redirect the edges. in createSingleExitBranchRegion()
925 singleExitBlock = new Block; in createSingleExitBranchRegion()
935 conditionalRegion.push_back(parentBlockList.remove(block)); in createSingleExitBranchRegion()
942 /// Returns true if this block is an exit block of the region.
943 static bool isRegionExitBlock(Block *block) { in isRegionExitBlock() argument
944 return block->getNumSuccessors() == 0; in isRegionExitBlock()
948 /// into conditionally executed regions. Returns the entry block of the created
950 static FailureOr<SmallVector<Block *>> transformToStructuredCFBranches( in transformToStructuredCFBranches()
951 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue, in transformToStructuredCFBranches()
956 return SmallVector<Block *>{}; in transformToStructuredCFBranches()
960 Block *successor = regionEntry->getSuccessor(0); in transformToStructuredCFBranches()
969 return SmallVector<Block *>{regionEntry}; in transformToStructuredCFBranches()
976 SmallPtrSet<Block *, 8> notContinuation; in transformToStructuredCFBranches()
978 SmallVector<SmallVector<Block *>> successorBranchRegions( in transformToStructuredCFBranches()
983 // dominate the block it leads to. in transformToStructuredCFBranches()
1005 // single entry block has to be created. A structured control flow op in transformToStructuredCFBranches()
1018 // unable to create a single exit-block. We can nevertheless process all its in transformToStructuredCFBranches()
1024 // In this case we also create a single entry block like in 1) that also in transformToStructuredCFBranches()
1071 for (Block *block : branchRegion) { in transformToStructuredCFBranches()
1072 if (isRegionExitBlock(block)) { in transformToStructuredCFBranches()
1076 // block for all branch regions. in transformToStructuredCFBranches()
1078 for (auto iter = block->pred_begin(); iter != block->pred_end(); in transformToStructuredCFBranches()
1085 for (Edge edge : successorEdges(block)) { in transformToStructuredCFBranches()
1099 Block *continuation = llvm::find_singleton<Block>( in transformToStructuredCFBranches()
1103 // In case 3) or if not all continuation edges have the same entry block, in transformToStructuredCFBranches()
1104 // create a single entry block as continuation for all branch regions. in transformToStructuredCFBranches()
1112 // Trigger reprocess of case 3) after creating the single entry block. in transformToStructuredCFBranches()
1118 return SmallVector<Block *>{regionEntry}; in transformToStructuredCFBranches()
1121 SmallVector<Block *> newSubRegions; in transformToStructuredCFBranches()
1124 SmallVector<std::pair<Block *, SmallVector<Value>>> createdEmptyBlocks; in transformToStructuredCFBranches()
1132 // If no block is part of the branch region, we create a dummy block to in transformToStructuredCFBranches()
1135 new Block, llvm::to_vector(entryEdge.getSuccessorOperands())); in transformToStructuredCFBranches()
1143 // The entries of the branch regions may only have redundant block arguments in transformToStructuredCFBranches()
1145 Block *subRegionEntryBlock = &conditionalRegion.front(); in transformToStructuredCFBranches()
1168 for (auto &&[block, valueRange] : createdEmptyBlocks) { in transformToStructuredCFBranches()
1169 auto builder = OpBuilder::atBlockEnd(block); in transformToStructuredCFBranches()
1209 /// Transforms the region to only have a single block for every kind of
1218 for (Block &block : region.getBlocks()) { in createSingleExitBlocksForReturnLike()
1219 if (block.getNumSuccessors() != 0) in createSingleExitBlocksForReturnLike()
1221 exitCombiner.combineExit(block.getTerminator(), getSwitchValue); in createSingleExitBlocksForReturnLike()
1230 for (Block &block : region.getBlocks()) in checkTransformationPreconditions()
1231 if (block.hasNoPredecessors() && !block.isEntryBlock()) in checkTransformationPreconditions()
1232 return block.front().emitOpError( in checkTransformationPreconditions()
1240 // branch op interface. It is impossible to adjust their block arguments in checkTransformationPreconditions()
1260 // as it is currently not possible to pass them to any block arguments in checkTransformationPreconditions()
1323 SmallVector<Block *> workList = {®ion.front()}; in transformCFGToSCF()
1325 Block *current = workList.pop_back_val(); in transformCFGToSCF()
1329 FailureOr<SmallVector<Block *>> newRegions = in transformCFGToSCF()