1//===- CFGToSCF.h - Control Flow Graph to Structured Control Flow *- 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 code is an implementation of:
10// Helge Bahmann, Nico Reissmann, Magnus Jahre, and Jan Christian Meyer. 2015.
11// Perfect Reconstructability of Control Flow from Demand Dependence Graphs. ACM
12// Trans. Archit. Code Optim. 11, 4, Article 66 (January 2015), 25 pages.
13// https://doi.org/10.1145/2693261
14//
15// It defines an algorithm to translate any control flow graph with a single
16// entry and single exit block into structured control flow operations
17// consisting of regions of do-while loops and operations conditionally
18// dispatching to one out of multiple regions before continuing after the
19// operation. This includes control flow graphs containing irreducible
20// control flow.
21//
22// The implementation here additionally supports the transformation on
23// regions with multiple exit blocks. This is implemented by first
24// transforming all occurrences of return-like operations to branch to a
25// single exit block containing an instance of that return-like operation.
26// If there are multiple kinds of return-like operations, multiple exit
27// blocks are created. In that case the transformation leaves behind a
28// conditional control flow graph operation that dispatches to the given regions
29// terminating with different kinds of return-like operations each.
30//
31// If the function only contains a single kind of return-like operations,
32// it is guaranteed that all control flow graph ops will be lifted to structured
33// control flow, and that no more control flow graph ops remain after the
34// operation.
35//
36// The algorithm to lift CFGs consists of two transformations applied after each
37// other on any single-entry, single-exit region:
38// 1) Lifting cycles to structured control flow loops
39// 2) Lifting conditional branches to structured control flow branches
40// These are then applied recursively on any new single-entry single-exit
41// regions created by the transformation until no more CFG operations remain.
42//
43// The first part of cycle lifting is to detect any cycles in the CFG.
44// This is done using an algorithm for iterating over SCCs. Every SCC
45// representing a cycle is then transformed into a structured loop with a single
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
48// flow to create single entry and exit blocks is achieved via a multiplexer
49// construct that can be visualized as follows:
50// +-----+ +-----+ +-----+
51// | bb0 | | bb1 |...| bbN |
52// +--+--+ +--+--+ +-+---+
53// | | |
54// | v |
55// | +------+ |
56// | ++ ++<----+
57// | | Region |
58// +>| |<----+
59// ++ ++ |
60// +------+------+
61//
62// The above transforms to:
63// +-----+ +-----+ +-----+
64// | bb0 | | bb1 |...| bbN |
65// +-----+ +--|--+ ++----+
66// | v |
67// +->+-----+<---+
68// | bbM |<-------+
69// +---+-+ |
70// +---+ | +----+ |
71// | v | |
72// | +------+ | |
73// | ++ ++<-+ |
74// +->| Region | |
75// ++ ++ |
76// +------+-------+
77//
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.
82//
83// A similar transformation is done to create the latch block with the single
84// back edge and loop exit edge.
85//
86// The above form has the advantage that bbM now acts as the loop header
87// of the loop body. After the transformation on the latch, this results in a
88// structured loop that can then be lifted to structured control flow. The
89// conditional branches created in bbM are later lifted to conditional
90// branches.
91//
92// Lifting conditional branches is done by analyzing the *first* conditional
93// branch encountered in the entry region. The algorithm then identifies
94// all blocks that are dominated by a specific control flow edge and
95// the region where control flow continues:
96// +-----+
97// +-----+ bb0 +----+
98// v +-----+ v
99// Region 1 +-+-+ ... +-+-+ Region n
100// +---+ +---+
101// ... ...
102// | |
103// | +---+ |
104// +---->++ ++<---+
105// | |
106// ++ ++ Region T
107// +---+
108// Every region following bb0 consists of 0 or more blocks that eventually
109// branch to Region T. If there are multiple entry blocks into Region T, a
110// single entry block is created using a multiplexer block as shown above.
111// Region 1 to Region n are then lifted together with the conditional control
112// flow operation terminating bb0 into a structured conditional operation
113// followed by the operations of the entry block of Region T.
114//===----------------------------------------------------------------------===//
115
116#include "mlir/Transforms/CFGToSCF.h"
117
118#include "mlir/Interfaces/ControlFlowInterfaces.h"
119#include "mlir/Interfaces/SideEffectInterfaces.h"
120#include "llvm/ADT/DepthFirstIterator.h"
121#include "llvm/ADT/MapVector.h"
122#include "llvm/ADT/SCCIterator.h"
123#include "llvm/ADT/SetVector.h"
124
125using namespace mlir;
126
127/// Returns the mutable operand range used to transfer operands from `block` to
128/// its successor with the given index. The returned range being mutable allows
129/// us to modify the operands being transferred.
130static MutableOperandRange
131getMutableSuccessorOperands(Block *block, unsigned successorIndex) {
132 auto branchOpInterface = cast<BranchOpInterface>(Val: block->getTerminator());
133 SuccessorOperands succOps =
134 branchOpInterface.getSuccessorOperands(index: successorIndex);
135 return succOps.getMutableForwardedOperands();
136}
137
138/// Return the operand range used to transfer operands from `block` to its
139/// successor with the given index.
140static OperandRange getSuccessorOperands(Block *block,
141 unsigned successorIndex) {
142 return getMutableSuccessorOperands(block, successorIndex);
143}
144
145/// Appends all the block arguments from `other` to the block arguments of
146/// `block`, copying their types and locations.
147static void addBlockArgumentsFromOther(Block *block, Block *other) {
148 for (BlockArgument arg : other->getArguments())
149 block->addArgument(type: arg.getType(), loc: arg.getLoc());
150}
151
152namespace {
153
154/// Class representing an edge in the CFG. Consists of a from-block, a successor
155/// and corresponding successor operands passed to the block arguments of the
156/// successor.
157class Edge {
158 Block *fromBlock;
159 unsigned successorIndex;
160
161public:
162 /// Constructs a new edge from `fromBlock` to the successor corresponding to
163 /// `successorIndex`.
164 Edge(Block *fromBlock, unsigned int successorIndex)
165 : fromBlock(fromBlock), successorIndex(successorIndex) {}
166
167 /// Returns the from-block.
168 Block *getFromBlock() const { return fromBlock; }
169
170 /// Returns the successor of the edge.
171 Block *getSuccessor() const {
172 return fromBlock->getSuccessor(i: successorIndex);
173 }
174
175 /// Sets the successor of the edge, adjusting the terminator in the
176 /// from-block.
177 void setSuccessor(Block *block) const {
178 fromBlock->getTerminator()->setSuccessor(block, index: successorIndex);
179 }
180
181 /// Returns the arguments of this edge that are passed to the block arguments
182 /// of the successor.
183 MutableOperandRange getMutableSuccessorOperands() const {
184 return ::getMutableSuccessorOperands(block: fromBlock, successorIndex);
185 }
186
187 /// Returns the arguments of this edge that are passed to the block arguments
188 /// of the successor.
189 OperandRange getSuccessorOperands() const {
190 return ::getSuccessorOperands(block: fromBlock, successorIndex);
191 }
192};
193
194/// Structure containing the entry, exit and back edges of a cycle. A cycle is a
195/// generalization of a loop that may have multiple entry edges. See also
196/// https://llvm.org/docs/CycleTerminology.html.
197struct CycleEdges {
198 /// All edges from a block outside the cycle to a block inside the cycle.
199 /// The targets of these edges are entry blocks.
200 SmallVector<Edge> entryEdges;
201 /// All edges from a block inside the cycle to a block outside the cycle.
202 SmallVector<Edge> exitEdges;
203 /// All edges from a block inside the cycle to an entry block.
204 SmallVector<Edge> backEdges;
205};
206
207/// Class used to orchestrate creation of so-called edge multiplexers.
208/// This class creates a new basic block and routes all inputs edges
209/// to this basic block before branching to their original target.
210/// The purpose of this transformation is to create single-entry,
211/// single-exit regions.
212class EdgeMultiplexer {
213public:
214 /// Creates a new edge multiplexer capable of redirecting all edges to one of
215 /// the `entryBlocks`. This creates the multiplexer basic block with
216 /// appropriate block arguments after the first entry block. `extraArgs`
217 /// contains the types of possible extra block arguments passed to the
218 /// multiplexer block that are added to the successor operands of every
219 /// outgoing edge.
220 ///
221 /// NOTE: This does not yet redirect edges to branch to the
222 /// multiplexer block nor code dispatching from the multiplexer code
223 /// to the original successors.
224 /// See `redirectEdge` and `createSwitch`.
225 static EdgeMultiplexer create(Location loc, ArrayRef<Block *> entryBlocks,
226 function_ref<Value(unsigned)> getSwitchValue,
227 function_ref<Value(Type)> getUndefValue,
228 TypeRange extraArgs = {}) {
229 assert(!entryBlocks.empty() && "Require at least one entry block");
230
231 auto *multiplexerBlock = new Block;
232 multiplexerBlock->insertAfter(block: entryBlocks.front());
233
234 // To implement the multiplexer block, we have to add the block arguments of
235 // every distinct successor block to the multiplexer block. When redirecting
236 // edges, block arguments designated for blocks that aren't branched to will
237 // be assigned the `getUndefValue`. The amount of block arguments and their
238 // offset is saved in the map for `redirectEdge` to transform the edges.
239 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;
240 for (Block *entryBlock : entryBlocks) {
241 auto [iter, inserted] = blockArgMapping.insert(
242 KV: {entryBlock, multiplexerBlock->getNumArguments()});
243 if (inserted)
244 addBlockArgumentsFromOther(block: multiplexerBlock, other: entryBlock);
245 }
246
247 // If we have more than one successor, we have to additionally add a
248 // discriminator value, denoting which successor to jump to.
249 // When redirecting edges, an appropriate value will be passed using
250 // `getSwitchValue`.
251 Value discriminator;
252 if (blockArgMapping.size() > 1)
253 discriminator =
254 multiplexerBlock->addArgument(type: getSwitchValue(0).getType(), loc);
255
256 multiplexerBlock->addArguments(
257 types: extraArgs, locs: SmallVector<Location>(extraArgs.size(), loc));
258
259 return EdgeMultiplexer(multiplexerBlock, getSwitchValue, getUndefValue,
260 std::move(blockArgMapping), discriminator);
261 }
262
263 /// Returns the created multiplexer block.
264 Block *getMultiplexerBlock() const { return multiplexerBlock; }
265
266 /// Redirects `edge` to branch to the multiplexer block before continuing to
267 /// its original target. The edges successor must have originally been part
268 /// of the entry blocks array passed to the `create` function. `extraArgs`
269 /// must be used to pass along any additional values corresponding to
270 /// `extraArgs` in `create`.
271 void redirectEdge(Edge edge, ValueRange extraArgs = {}) const {
272 const auto *result = blockArgMapping.find(Key: edge.getSuccessor());
273 assert(result != blockArgMapping.end() &&
274 "Edge was not originally passed to `create` method.");
275
276 MutableOperandRange successorOperands = edge.getMutableSuccessorOperands();
277
278 // Extra arguments are always appended at the end of the block arguments.
279 unsigned extraArgsBeginIndex =
280 multiplexerBlock->getNumArguments() - extraArgs.size();
281 // If a discriminator exists, it is right before the extra arguments.
282 std::optional<unsigned> discriminatorIndex =
283 discriminator ? extraArgsBeginIndex - 1 : std::optional<unsigned>{};
284
285 SmallVector<Value> newSuccOperands(multiplexerBlock->getNumArguments());
286 for (BlockArgument argument : multiplexerBlock->getArguments()) {
287 unsigned index = argument.getArgNumber();
288 if (index >= result->second &&
289 index < result->second + edge.getSuccessor()->getNumArguments()) {
290 // Original block arguments to the entry block.
291 newSuccOperands[index] =
292 successorOperands[index - result->second].get();
293 continue;
294 }
295
296 // Discriminator value if it exists.
297 if (index == discriminatorIndex) {
298 newSuccOperands[index] =
299 getSwitchValue(result - blockArgMapping.begin());
300 continue;
301 }
302
303 // Followed by the extra arguments.
304 if (index >= extraArgsBeginIndex) {
305 newSuccOperands[index] = extraArgs[index - extraArgsBeginIndex];
306 continue;
307 }
308
309 // Otherwise undef values for any unused block arguments used by other
310 // entry blocks.
311 newSuccOperands[index] = getUndefValue(argument.getType());
312 }
313
314 edge.setSuccessor(multiplexerBlock);
315 successorOperands.assign(values: newSuccOperands);
316 }
317
318 /// Creates a switch op using `builder` which dispatches to the original
319 /// successors of the edges passed to `create` minus the ones in `excluded`.
320 /// The builder's insertion point has to be in a block dominated by the
321 /// multiplexer block. All edges to the multiplexer block must have already
322 /// been redirected using `redirectEdge`.
323 void createSwitch(
324 Location loc, OpBuilder &builder, CFGToSCFInterface &interface,
325 const SmallPtrSetImpl<Block *> &excluded = SmallPtrSet<Block *, 1>{}) {
326 // We create the switch by creating a case for all entries and then
327 // splitting of the last entry as a default case.
328
329 SmallVector<ValueRange> caseArguments;
330 SmallVector<unsigned> caseValues;
331 SmallVector<Block *> caseDestinations;
332 for (auto &&[index, pair] : llvm::enumerate(First&: blockArgMapping)) {
333 auto &&[succ, offset] = pair;
334 if (excluded.contains(Ptr: succ))
335 continue;
336
337 caseValues.push_back(Elt: index);
338 caseArguments.push_back(Elt: multiplexerBlock->getArguments().slice(
339 N: offset, M: succ->getNumArguments()));
340 caseDestinations.push_back(Elt: succ);
341 }
342
343 // If we don't have a discriminator due to only having one entry we have to
344 // create a dummy flag for the switch.
345 Value realDiscriminator = discriminator;
346 if (!realDiscriminator || caseArguments.size() == 1)
347 realDiscriminator = getSwitchValue(0);
348
349 caseValues.pop_back();
350 Block *defaultDest = caseDestinations.pop_back_val();
351 ValueRange defaultArgs = caseArguments.pop_back_val();
352
353 assert(!builder.getInsertionBlock()->hasNoPredecessors() &&
354 "Edges need to be redirected prior to creating switch.");
355 interface.createCFGSwitchOp(loc, builder, flag: realDiscriminator, caseValues,
356 caseDestinations, caseArguments, defaultDest,
357 defaultArgs);
358 }
359
360private:
361 /// Newly created multiplexer block.
362 Block *multiplexerBlock;
363 /// Callback used to create a constant suitable as flag for
364 /// the interfaces `createCFGSwitchOp`.
365 function_ref<Value(unsigned)> getSwitchValue;
366 /// Callback used to create undefined values of a given type.
367 function_ref<Value(Type)> getUndefValue;
368
369 /// Mapping of the block arguments of an entry block to the corresponding
370 /// block arguments in the multiplexer block. Block arguments of an entry
371 /// block are simply appended ot the multiplexer block. This map simply
372 /// contains the offset to the range in the multiplexer block.
373 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;
374 /// Discriminator value used in the multiplexer block to dispatch to the
375 /// correct entry block. Null value if not required due to only having one
376 /// entry block.
377 Value discriminator;
378
379 EdgeMultiplexer(Block *multiplexerBlock,
380 function_ref<Value(unsigned)> getSwitchValue,
381 function_ref<Value(Type)> getUndefValue,
382 llvm::SmallMapVector<Block *, unsigned, 4> &&entries,
383 Value dispatchFlag)
384 : multiplexerBlock(multiplexerBlock), getSwitchValue(getSwitchValue),
385 getUndefValue(getUndefValue), blockArgMapping(std::move(entries)),
386 discriminator(dispatchFlag) {}
387};
388
389/// Alternative implementation of DenseMapInfo<Operation*> using the operation
390/// equivalence infrastructure to check whether two 'return-like' operations are
391/// equivalent in the context of this transformation. This means that both
392/// operations are of the same kind, have the same amount of operands and types
393/// and the same attributes and properties. The operands themselves don't have
394/// to be equivalent.
395struct ReturnLikeOpEquivalence : public llvm::DenseMapInfo<Operation *> {
396 static unsigned getHashValue(const Operation *opC) {
397 return OperationEquivalence::computeHash(
398 op: const_cast<Operation *>(opC),
399 /*hashOperands=*/OperationEquivalence::ignoreHashValue,
400 /*hashResults=*/OperationEquivalence::ignoreHashValue,
401 flags: OperationEquivalence::IgnoreLocations);
402 }
403
404 static bool isEqual(const Operation *lhs, const Operation *rhs) {
405 if (lhs == rhs)
406 return true;
407 if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||
408 rhs == getTombstoneKey() || rhs == getEmptyKey())
409 return false;
410 return OperationEquivalence::isEquivalentTo(
411 lhs: const_cast<Operation *>(lhs), rhs: const_cast<Operation *>(rhs),
412 checkEquivalent: OperationEquivalence::ignoreValueEquivalence, markEquivalent: nullptr,
413 flags: OperationEquivalence::IgnoreLocations);
414 }
415};
416
417/// Utility-class for transforming a region to only have one single block for
418/// every return-like operation.
419class ReturnLikeExitCombiner {
420public:
421 ReturnLikeExitCombiner(Region &topLevelRegion, CFGToSCFInterface &interface)
422 : topLevelRegion(topLevelRegion), interface(interface) {}
423
424 /// Transforms `returnLikeOp` to a branch to the only block in the
425 /// region with an instance of `returnLikeOp`s kind.
426 void combineExit(Operation *returnLikeOp,
427 function_ref<Value(unsigned)> getSwitchValue) {
428 auto [iter, inserted] = returnLikeToCombinedExit.try_emplace(Key: returnLikeOp);
429 if (!inserted && iter->first == returnLikeOp)
430 return;
431
432 Block *exitBlock = iter->second;
433 if (inserted) {
434 exitBlock = new Block;
435 iter->second = exitBlock;
436 topLevelRegion.push_back(block: exitBlock);
437 exitBlock->addArguments(
438 types: returnLikeOp->getOperandTypes(),
439 locs: SmallVector<Location>(returnLikeOp->getNumOperands(),
440 returnLikeOp->getLoc()));
441 }
442
443 auto builder = OpBuilder::atBlockTerminator(block: returnLikeOp->getBlock());
444 interface.createSingleDestinationBranch(loc: returnLikeOp->getLoc(), builder,
445 dummyFlag: getSwitchValue(0), destination: exitBlock,
446 arguments: returnLikeOp->getOperands());
447
448 if (!inserted) {
449 returnLikeOp->erase();
450 return;
451 }
452
453 returnLikeOp->moveBefore(block: exitBlock, iterator: exitBlock->end());
454 returnLikeOp->setOperands(exitBlock->getArguments());
455 }
456
457private:
458 /// Mapping of return-like operation to block. All return-like operations
459 /// of the same kind with the same attributes, properties and types are seen
460 /// as equivalent. First occurrence seen is kept in the map.
461 llvm::SmallDenseMap<Operation *, Block *, 4, ReturnLikeOpEquivalence>
462 returnLikeToCombinedExit;
463 Region &topLevelRegion;
464 CFGToSCFInterface &interface;
465};
466
467} // namespace
468
469/// Returns a range of all edges from `block` to each of its successors.
470static auto successorEdges(Block *block) {
471 return llvm::map_range(C: llvm::seq(Size: block->getNumSuccessors()),
472 F: [=](unsigned index) { return Edge(block, index); });
473}
474
475/// Calculates entry, exit and back edges of the given cycle.
476static CycleEdges
477calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) {
478 CycleEdges result;
479 SmallPtrSet<Block *, 8> entryBlocks;
480
481 // First identify all exit and entry edges by checking whether any successors
482 // or predecessors are from outside the cycles.
483 for (Block *block : cycles) {
484 for (auto pred = block->pred_begin(); pred != block->pred_end(); pred++) {
485 if (cycles.contains(key: *pred))
486 continue;
487
488 result.entryEdges.emplace_back(Args: *pred, Args: pred.getSuccessorIndex());
489 entryBlocks.insert(Ptr: block);
490 }
491
492 for (auto &&[succIndex, succ] : llvm::enumerate(First: block->getSuccessors())) {
493 if (cycles.contains(key: succ))
494 continue;
495
496 result.exitEdges.emplace_back(Args&: block, Args&: succIndex);
497 }
498 }
499
500 // With the entry blocks identified, find all the back edges.
501 for (Block *block : cycles) {
502 for (auto &&[succIndex, succ] : llvm::enumerate(First: block->getSuccessors())) {
503 if (!entryBlocks.contains(Ptr: succ))
504 continue;
505
506 result.backEdges.emplace_back(Args&: block, Args&: succIndex);
507 }
508 }
509
510 return result;
511}
512
513/// Creates a single entry block out of multiple entry edges using an edge
514/// multiplexer and returns it.
515static EdgeMultiplexer
516createSingleEntryBlock(Location loc, ArrayRef<Edge> entryEdges,
517 function_ref<Value(unsigned)> getSwitchValue,
518 function_ref<Value(Type)> getUndefValue,
519 CFGToSCFInterface &interface) {
520 auto result = EdgeMultiplexer::create(
521 loc, entryBlocks: llvm::map_to_vector(C&: entryEdges, F: std::mem_fn(pm: &Edge::getSuccessor)),
522 getSwitchValue, getUndefValue);
523
524 // Redirect the edges prior to creating the switch op.
525 // We guarantee that predecessors are up to date.
526 for (Edge edge : entryEdges)
527 result.redirectEdge(edge);
528
529 auto builder = OpBuilder::atBlockBegin(block: result.getMultiplexerBlock());
530 result.createSwitch(loc, builder, interface);
531
532 return result;
533}
534
535namespace {
536/// Special loop properties of a structured loop.
537/// A structured loop is a loop satisfying all of the following:
538/// * Has at most one entry, one exit and one back edge.
539/// * The back edge originates from the same block as the exit edge.
540struct StructuredLoopProperties {
541 /// Block containing both the single exit edge and the single back edge.
542 Block *latch;
543 /// Loop condition of type equal to a value returned by `getSwitchValue`.
544 Value condition;
545 /// Exit block which is the only successor of the loop.
546 Block *exitBlock;
547};
548} // namespace
549
550/// Transforms a loop into a structured loop with only a single back edge and
551/// exiting edge, originating from the same block.
552static FailureOr<StructuredLoopProperties> createSingleExitingLatch(
553 Location loc, ArrayRef<Edge> backEdges, ArrayRef<Edge> exitEdges,
554 function_ref<Value(unsigned)> getSwitchValue,
555 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
556 ReturnLikeExitCombiner &exitCombiner) {
557 assert(llvm::all_equal(
558 llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor))) &&
559 "All repetition edges must lead to the single loop header");
560
561 // First create the multiplexer block, which will be our latch, for all back
562 // edges and exit edges. We pass an additional argument to the multiplexer
563 // block which indicates whether the latch was reached from what was
564 // originally a back edge or an exit block.
565 // This is later used to branch using the new only back edge.
566 SmallVector<Block *> successors;
567 llvm::append_range(
568 C&: successors, R: llvm::map_range(C&: backEdges, F: std::mem_fn(pm: &Edge::getSuccessor)));
569 llvm::append_range(
570 C&: successors, R: llvm::map_range(C&: exitEdges, F: std::mem_fn(pm: &Edge::getSuccessor)));
571 auto multiplexer =
572 EdgeMultiplexer::create(loc, entryBlocks: successors, getSwitchValue, getUndefValue,
573 /*extraArgs=*/getSwitchValue(0).getType());
574
575 auto *latchBlock = multiplexer.getMultiplexerBlock();
576
577 // Create a separate exit block that comes right after the latch.
578 auto *exitBlock = new Block;
579 exitBlock->insertAfter(block: latchBlock);
580
581 // Since this is a loop, all back edges point to the same loop header.
582 Block *loopHeader = backEdges.front().getSuccessor();
583
584 // Redirect the edges prior to creating the switch op.
585 // We guarantee that predecessors are up to date.
586
587 // Redirecting back edges with `shouldRepeat` as 1.
588 for (Edge backEdge : backEdges)
589 multiplexer.redirectEdge(edge: backEdge, /*extraArgs=*/getSwitchValue(1));
590
591 // Redirecting exits edges with `shouldRepeat` as 0.
592 for (Edge exitEdge : exitEdges)
593 multiplexer.redirectEdge(edge: exitEdge, /*extraArgs=*/getSwitchValue(0));
594
595 // Create the new only back edge to the loop header. Branch to the
596 // exit block otherwise.
597 Value shouldRepeat = latchBlock->getArguments().back();
598 {
599 auto builder = OpBuilder::atBlockBegin(block: latchBlock);
600 interface.createConditionalBranch(
601 loc, builder, condition: shouldRepeat, trueDest: loopHeader,
602 trueArgs: latchBlock->getArguments().take_front(N: loopHeader->getNumArguments()),
603 /*falseDest=*/exitBlock,
604 /*falseArgs=*/{});
605 }
606
607 {
608 auto builder = OpBuilder::atBlockBegin(block: exitBlock);
609 if (!exitEdges.empty()) {
610 // Create the switch dispatching to what were originally the multiple exit
611 // blocks. The loop header has to explicitly be excluded in the below
612 // switch as we would otherwise be creating a new loop again. All back
613 // edges leading to the loop header have already been handled in the
614 // switch above. The remaining edges can only jump to blocks outside the
615 // loop.
616
617 SmallPtrSet<Block *, 1> excluded = {loopHeader};
618 multiplexer.createSwitch(loc, builder, interface, excluded);
619 } else {
620 // A loop without an exit edge is a statically known infinite loop.
621 // Since structured control flow ops are not terminator ops, the caller
622 // has to create a fitting return-like unreachable terminator operation.
623 FailureOr<Operation *> terminator = interface.createUnreachableTerminator(
624 loc, builder, region&: *latchBlock->getParent());
625 if (failed(Result: terminator))
626 return failure();
627 // Transform the just created transform operation in the case that an
628 // occurrence of it existed in input IR.
629 exitCombiner.combineExit(returnLikeOp: *terminator, getSwitchValue);
630 }
631 }
632
633 return StructuredLoopProperties{.latch: latchBlock, /*condition=*/shouldRepeat,
634 .exitBlock: exitBlock};
635}
636
637/// Transforms a structured loop into a loop in reduce form.
638///
639/// Reduce form is defined as a structured loop where:
640/// (0) No values defined within the loop body are used outside the loop body.
641/// (1) The block arguments and successor operands of the exit block are equal
642/// to the block arguments of the loop header and the successor operands
643/// of the back edge.
644///
645/// This is required for many structured control flow ops as they tend
646/// to not have separate "loop result arguments" and "loop iteration arguments"
647/// at the end of the block. Rather, the "loop iteration arguments" from the
648/// last iteration are the result of the loop.
649///
650/// Note that the requirement of (0) is shared with LCSSA form in LLVM. However,
651/// due to this being a structured loop instead of a general loop, we do not
652/// require complicated dominance algorithms nor SSA updating making this
653/// implementation easier than creating a generic LCSSA transformation pass.
654static SmallVector<Value>
655transformToReduceLoop(Block *loopHeader, Block *exitBlock,
656 const llvm::SmallSetVector<Block *, 4> &loopBlocks,
657 function_ref<Value(Type)> getUndefValue,
658 DominanceInfo &dominanceInfo) {
659 Block *latch = exitBlock->getSinglePredecessor();
660 assert(latch &&
661 "Exit block must have only latch as predecessor at this point");
662 assert(exitBlock->getNumArguments() == 0 &&
663 "Exit block mustn't have any block arguments at this point");
664
665 unsigned loopHeaderIndex = 0;
666 unsigned exitBlockIndex = 1;
667 if (latch->getSuccessor(i: loopHeaderIndex) != loopHeader)
668 std::swap(a&: loopHeaderIndex, b&: exitBlockIndex);
669
670 assert(latch->getSuccessor(loopHeaderIndex) == loopHeader);
671 assert(latch->getSuccessor(exitBlockIndex) == exitBlock);
672
673 MutableOperandRange exitBlockSuccessorOperands =
674 getMutableSuccessorOperands(block: latch, successorIndex: exitBlockIndex);
675 // Save the values as a vector, not a `MutableOperandRange` as the latter gets
676 // invalidated when mutating the operands through a different
677 // `MutableOperandRange` of the same operation.
678 SmallVector<Value> loopHeaderSuccessorOperands =
679 llvm::to_vector(Range: getSuccessorOperands(block: latch, successorIndex: loopHeaderIndex));
680
681 // Add all values used in the next iteration to the exit block. Replace
682 // any uses that are outside the loop with the newly created exit block.
683 for (Value arg : loopHeaderSuccessorOperands) {
684 BlockArgument exitArg = exitBlock->addArgument(type: arg.getType(), loc: arg.getLoc());
685 exitBlockSuccessorOperands.append(values: arg);
686 arg.replaceUsesWithIf(newValue: exitArg, shouldReplace: [&](OpOperand &use) {
687 return !loopBlocks.contains(key: use.getOwner()->getBlock());
688 });
689 }
690
691 // Loop below might add block arguments to the latch and loop header.
692 // Save the block arguments prior to the loop to not process these.
693 SmallVector<BlockArgument> latchBlockArgumentsPrior =
694 llvm::to_vector(Range: latch->getArguments());
695 SmallVector<BlockArgument> loopHeaderArgumentsPrior =
696 llvm::to_vector(Range: loopHeader->getArguments());
697
698 // Go over all values defined within the loop body. If any of them are used
699 // outside the loop body, create a block argument on the exit block and loop
700 // header and replace the outside uses with the exit block argument.
701 // The loop header block argument is added to satisfy requirement (1) in the
702 // reduce form condition.
703 for (Block *loopBlock : loopBlocks) {
704 // Cache dominance queries for loopBlock.
705 // There are likely to be many duplicate queries as there can be many value
706 // definitions within a block.
707 llvm::SmallDenseMap<Block *, bool> dominanceCache;
708 // Returns true if `loopBlock` dominates `block`.
709 auto loopBlockDominates = [&](Block *block) {
710 auto [iter, inserted] = dominanceCache.try_emplace(Key: block);
711 if (!inserted)
712 return iter->second;
713 iter->second = dominanceInfo.dominates(a: loopBlock, b: block);
714 return iter->second;
715 };
716
717 auto checkValue = [&](Value value) {
718 Value blockArgument;
719 for (OpOperand &use : llvm::make_early_inc_range(Range: value.getUses())) {
720 // Go through all the parent blocks and find the one part of the region
721 // of the loop. If the block is part of the loop, then the value does
722 // not escape the loop through this use.
723 Block *currBlock = use.getOwner()->getBlock();
724 while (currBlock && currBlock->getParent() != loopHeader->getParent())
725 currBlock = currBlock->getParentOp()->getBlock();
726 if (loopBlocks.contains(key: currBlock))
727 continue;
728
729 // Block argument is only created the first time it is required.
730 if (!blockArgument) {
731 blockArgument =
732 exitBlock->addArgument(type: value.getType(), loc: value.getLoc());
733 loopHeader->addArgument(type: value.getType(), loc: value.getLoc());
734
735 // `value` might be defined in a block that does not dominate `latch`
736 // but previously dominated an exit block with a use.
737 // In this case, add a block argument to the latch and go through all
738 // predecessors. If the value dominates the predecessor, pass the
739 // value as a successor operand, otherwise pass undef.
740 // The above is unnecessary if the value is a block argument of the
741 // latch or if `value` dominates all predecessors.
742 Value argument = value;
743 if (value.getParentBlock() != latch &&
744 llvm::any_of(Range: latch->getPredecessors(), P: [&](Block *pred) {
745 return !loopBlockDominates(pred);
746 })) {
747 argument = latch->addArgument(type: value.getType(), loc: value.getLoc());
748 for (auto iter = latch->pred_begin(); iter != latch->pred_end();
749 ++iter) {
750 Value succOperand = value;
751 if (!loopBlockDominates(*iter))
752 succOperand = getUndefValue(value.getType());
753
754 getMutableSuccessorOperands(block: *iter, successorIndex: iter.getSuccessorIndex())
755 .append(values: succOperand);
756 }
757 }
758
759 loopHeaderSuccessorOperands.push_back(Elt: argument);
760 for (Edge edge : successorEdges(block: latch))
761 edge.getMutableSuccessorOperands().append(values: argument);
762 }
763
764 use.set(blockArgument);
765 }
766 };
767
768 if (loopBlock == latch)
769 llvm::for_each(Range&: latchBlockArgumentsPrior, F: checkValue);
770 else if (loopBlock == loopHeader)
771 llvm::for_each(Range&: loopHeaderArgumentsPrior, F: checkValue);
772 else
773 llvm::for_each(Range: loopBlock->getArguments(), F: checkValue);
774
775 for (Operation &op : *loopBlock)
776 llvm::for_each(Range: op.getResults(), F: checkValue);
777 }
778
779 // New block arguments may have been added to the loop header.
780 // Adjust the entry edges to pass undef values to these.
781 for (auto iter = loopHeader->pred_begin(); iter != loopHeader->pred_end();
782 ++iter) {
783 // Latch successor arguments have already been handled.
784 if (*iter == latch)
785 continue;
786
787 MutableOperandRange succOps =
788 getMutableSuccessorOperands(block: *iter, successorIndex: iter.getSuccessorIndex());
789 succOps.append(values: llvm::map_to_vector(
790 C: loopHeader->getArguments().drop_front(N: succOps.size()),
791 F: [&](BlockArgument arg) { return getUndefValue(arg.getType()); }));
792 }
793
794 return loopHeaderSuccessorOperands;
795}
796
797/// Transforms all outer-most cycles in the region with the region entry
798/// `regionEntry` into structured loops. Returns the entry blocks of any newly
799/// created regions potentially requiring further transformations.
800static FailureOr<SmallVector<Block *>> transformCyclesToSCFLoops(
801 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,
802 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
803 DominanceInfo &dominanceInfo, ReturnLikeExitCombiner &exitCombiner) {
804 SmallVector<Block *> newSubRegions;
805 auto scc = llvm::scc_begin(G: regionEntry);
806 while (!scc.isAtEnd()) {
807 if (!scc.hasCycle()) {
808 ++scc;
809 continue;
810 }
811
812 // Save the set and increment the SCC iterator early to avoid our
813 // modifications breaking the SCC iterator.
814 llvm::SmallSetVector<Block *, 4> cycleBlockSet(scc->begin(), scc->end());
815 ++scc;
816
817 CycleEdges edges = calculateCycleEdges(cycles: cycleBlockSet);
818 Block *loopHeader = edges.entryEdges.front().getSuccessor();
819 // First turn the cycle into a loop by creating a single entry block if
820 // needed.
821 if (edges.entryEdges.size() > 1) {
822 SmallVector<Edge> edgesToEntryBlocks;
823 llvm::append_range(C&: edgesToEntryBlocks, R&: edges.entryEdges);
824 llvm::append_range(C&: edgesToEntryBlocks, R&: edges.backEdges);
825
826 EdgeMultiplexer multiplexer = createSingleEntryBlock(
827 loc: loopHeader->getTerminator()->getLoc(), entryEdges: edgesToEntryBlocks,
828 getSwitchValue, getUndefValue, interface);
829
830 loopHeader = multiplexer.getMultiplexerBlock();
831 }
832 cycleBlockSet.insert(X: loopHeader);
833
834 // Then turn it into a structured loop by creating a single latch.
835 FailureOr<StructuredLoopProperties> loopProperties =
836 createSingleExitingLatch(
837 loc: edges.backEdges.front().getFromBlock()->getTerminator()->getLoc(),
838 backEdges: edges.backEdges, exitEdges: edges.exitEdges, getSwitchValue, getUndefValue,
839 interface, exitCombiner);
840 if (failed(Result: loopProperties))
841 return failure();
842
843 Block *latchBlock = loopProperties->latch;
844 Block *exitBlock = loopProperties->exitBlock;
845 cycleBlockSet.insert(X: latchBlock);
846 cycleBlockSet.insert(X: loopHeader);
847
848 // Finally, turn it into reduce form.
849 SmallVector<Value> iterationValues = transformToReduceLoop(
850 loopHeader, exitBlock, loopBlocks: cycleBlockSet, getUndefValue, dominanceInfo);
851
852 // Create a block acting as replacement for the loop header and insert
853 // the structured loop into it.
854 auto *newLoopParentBlock = new Block;
855 newLoopParentBlock->insertBefore(block: loopHeader);
856 addBlockArgumentsFromOther(block: newLoopParentBlock, other: loopHeader);
857
858 Region::BlockListType &blocks = regionEntry->getParent()->getBlocks();
859 Region loopBody;
860 // Make sure the loop header is the entry block.
861 loopBody.push_back(block: blocks.remove(IT: loopHeader));
862 for (Block *block : cycleBlockSet)
863 if (block != latchBlock && block != loopHeader)
864 loopBody.push_back(block: blocks.remove(IT: block));
865 // And the latch is the last block.
866 loopBody.push_back(block: blocks.remove(IT: latchBlock));
867
868 Operation *oldTerminator = latchBlock->getTerminator();
869 oldTerminator->remove();
870
871 auto builder = OpBuilder::atBlockBegin(block: newLoopParentBlock);
872 FailureOr<Operation *> structuredLoopOp =
873 interface.createStructuredDoWhileLoopOp(
874 builder, replacedOp: oldTerminator, loopValuesInit: newLoopParentBlock->getArguments(),
875 condition: loopProperties->condition, loopValuesNextIter: iterationValues, loopBody: std::move(loopBody));
876 if (failed(Result: structuredLoopOp))
877 return failure();
878 oldTerminator->erase();
879
880 newSubRegions.push_back(Elt: loopHeader);
881
882 for (auto &&[oldValue, newValue] : llvm::zip(
883 t: exitBlock->getArguments(), u: (*structuredLoopOp)->getResults()))
884 oldValue.replaceAllUsesWith(newValue);
885
886 loopHeader->replaceAllUsesWith(newValue&: newLoopParentBlock);
887 // Merge the exit block right after the loop operation.
888 newLoopParentBlock->getOperations().splice(where: newLoopParentBlock->end(),
889 L2&: exitBlock->getOperations());
890 exitBlock->erase();
891 }
892 return newSubRegions;
893}
894
895/// Makes sure the branch region only has a single exit. This is required by the
896/// recursive part of the algorithm, as it expects the CFG to be single-entry
897/// and single-exit. This is done by simply creating an empty block if there
898/// is more than one block with an edge to the continuation block. All blocks
899/// with edges to the continuation are then redirected to this block. A region
900/// terminator is later placed into the block.
901static void createSingleExitBranchRegion(
902 ArrayRef<Block *> branchRegion, Block *continuation,
903 SmallVectorImpl<std::pair<Block *, SmallVector<Value>>> &createdEmptyBlocks,
904 Region &conditionalRegion) {
905 Block *singleExitBlock = nullptr;
906 std::optional<Edge> previousEdgeToContinuation;
907 Region::BlockListType &parentBlockList =
908 branchRegion.front()->getParent()->getBlocks();
909 for (Block *block : branchRegion) {
910 for (Edge edge : successorEdges(block)) {
911 if (edge.getSuccessor() != continuation)
912 continue;
913
914 if (!previousEdgeToContinuation) {
915 previousEdgeToContinuation = edge;
916 continue;
917 }
918
919 // If this is not the first edge to the continuation we create the
920 // single exit block and redirect the edges.
921 if (!singleExitBlock) {
922 singleExitBlock = new Block;
923 addBlockArgumentsFromOther(block: singleExitBlock, other: continuation);
924 previousEdgeToContinuation->setSuccessor(singleExitBlock);
925 createdEmptyBlocks.emplace_back(Args&: singleExitBlock,
926 Args: singleExitBlock->getArguments());
927 }
928
929 edge.setSuccessor(singleExitBlock);
930 }
931
932 conditionalRegion.push_back(block: parentBlockList.remove(IT: block));
933 }
934
935 if (singleExitBlock)
936 conditionalRegion.push_back(block: singleExitBlock);
937}
938
939/// Returns true if this block is an exit block of the region.
940static bool isRegionExitBlock(Block *block) {
941 return block->getNumSuccessors() == 0;
942}
943
944/// Transforms the first occurrence of conditional control flow in `regionEntry`
945/// into conditionally executed regions. Returns the entry block of the created
946/// regions and the region after the conditional control flow.
947static FailureOr<SmallVector<Block *>> transformToStructuredCFBranches(
948 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,
949 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
950 DominanceInfo &dominanceInfo) {
951 // Trivial region.
952 if (regionEntry->getNumSuccessors() == 0)
953 return SmallVector<Block *>{};
954
955 if (regionEntry->getNumSuccessors() == 1) {
956 // Single successor we can just splice together.
957 Block *successor = regionEntry->getSuccessor(i: 0);
958 for (auto &&[oldValue, newValue] : llvm::zip(
959 t: successor->getArguments(), u: getSuccessorOperands(block: regionEntry, successorIndex: 0)))
960 oldValue.replaceAllUsesWith(newValue);
961 regionEntry->getTerminator()->erase();
962
963 regionEntry->getOperations().splice(where: regionEntry->end(),
964 L2&: successor->getOperations());
965 successor->erase();
966 return SmallVector<Block *>{regionEntry};
967 }
968
969 // Split the CFG into "#numSuccessor + 1" regions.
970 // For every edge to a successor, the blocks it solely dominates are
971 // determined and become the region following that edge.
972 // The last region is the continuation that follows the branch regions.
973 SmallPtrSet<Block *, 8> notContinuation;
974 notContinuation.insert(Ptr: regionEntry);
975 SmallVector<SmallVector<Block *>> successorBranchRegions(
976 regionEntry->getNumSuccessors());
977 for (auto &&[blockList, succ] :
978 llvm::zip(t&: successorBranchRegions, u: regionEntry->getSuccessors())) {
979 // If the region entry is not the only predecessor, then the edge does not
980 // dominate the block it leads to.
981 if (succ->getSinglePredecessor() != regionEntry)
982 continue;
983
984 // Otherwise get all blocks it dominates in DFS/pre-order.
985 DominanceInfoNode *node = dominanceInfo.getNode(a: succ);
986 for (DominanceInfoNode *curr : llvm::depth_first(G: node)) {
987 blockList.push_back(Elt: curr->getBlock());
988 notContinuation.insert(Ptr: curr->getBlock());
989 }
990 }
991
992 // Finds all relevant edges and checks the shape of the control flow graph at
993 // this point.
994 // Branch regions may either:
995 // * Be post-dominated by the continuation
996 // * Be post-dominated by a return-like op
997 // * Dominate a return-like op and have an edge to the continuation.
998 //
999 // The control flow graph may then be one of three cases:
1000 // 1) All branch regions are post-dominated by the continuation. This is the
1001 // usual case. If there are multiple entry blocks into the continuation a
1002 // single entry block has to be created. A structured control flow op
1003 // can then be created from the branch regions.
1004 //
1005 // 2) No branch region has an edge to a continuation:
1006 // +-----+
1007 // +-----+ bb0 +----+
1008 // v +-----+ v
1009 // Region 1 +-+--+ ... +-+--+ Region n
1010 // |ret1| |ret2|
1011 // +----+ +----+
1012 //
1013 // This can only occur if every region ends with a different kind of
1014 // return-like op. In that case the control flow operation must stay as we are
1015 // unable to create a single exit-block. We can nevertheless process all its
1016 // successors as they single-entry, single-exit regions.
1017 //
1018 // 3) Only some branch regions are post-dominated by the continuation.
1019 // The other branch regions may either be post-dominated by a return-like op
1020 // or lead to either the continuation or return-like op.
1021 // In this case we also create a single entry block like in 1) that also
1022 // includes all edges to the return-like op:
1023 // +-----+
1024 // +-----+ bb0 +----+
1025 // v +-----+ v
1026 // Region 1 +-+-+ ... +-+-+ Region n
1027 // +---+ +---+
1028 // +---+ |... ...
1029 // |ret|<-+ | |
1030 // +---+ | +---+ |
1031 // +---->++ ++<---+
1032 // | |
1033 // ++ ++ Region T
1034 // +---+
1035 // This transforms to:
1036 // +-----+
1037 // +-----+ bb0 +----+
1038 // v +-----+ v
1039 // Region 1 +-+-+ ... +-+-+ Region n
1040 // +---+ +---+
1041 // ... +-----+ ...
1042 // +---->+ bbM +<---+
1043 // +-----+
1044 // +-----+ |
1045 // | v
1046 // +---+ | +---+
1047 // |ret+<---+ ++ ++
1048 // +---+ | |
1049 // ++ ++ Region T
1050 // +---+
1051 //
1052 // bb0 to bbM is now a single-entry, single-exit region that applies to case
1053 // 1). The control flow op at the end of bbM will trigger case 2.
1054 SmallVector<Edge> continuationEdges;
1055 bool continuationPostDominatesAllRegions = true;
1056 bool noSuccessorHasContinuationEdge = true;
1057 for (auto &&[entryEdge, branchRegion] :
1058 llvm::zip(t: successorEdges(block: regionEntry), u&: successorBranchRegions)) {
1059
1060 // If the branch region is empty then the branch target itself is part of
1061 // the continuation.
1062 if (branchRegion.empty()) {
1063 continuationEdges.push_back(Elt: entryEdge);
1064 noSuccessorHasContinuationEdge = false;
1065 continue;
1066 }
1067
1068 for (Block *block : branchRegion) {
1069 if (isRegionExitBlock(block)) {
1070 // If a return-like op is part of the branch region then the
1071 // continuation no longer post-dominates the branch region.
1072 // Add all its incoming edges to edge list to create the single-exit
1073 // block for all branch regions.
1074 continuationPostDominatesAllRegions = false;
1075 for (auto iter = block->pred_begin(); iter != block->pred_end();
1076 ++iter) {
1077 continuationEdges.emplace_back(Args: *iter, Args: iter.getSuccessorIndex());
1078 }
1079 continue;
1080 }
1081
1082 for (Edge edge : successorEdges(block)) {
1083 if (notContinuation.contains(Ptr: edge.getSuccessor()))
1084 continue;
1085
1086 continuationEdges.push_back(Elt: edge);
1087 noSuccessorHasContinuationEdge = false;
1088 }
1089 }
1090 }
1091
1092 // case 2) Keep the control flow op but process its successors further.
1093 if (noSuccessorHasContinuationEdge)
1094 return llvm::to_vector(Range: regionEntry->getSuccessors());
1095
1096 Block *continuation = llvm::find_singleton<Block>(
1097 Range&: continuationEdges, P: [](Edge edge, bool) { return edge.getSuccessor(); },
1098 /*AllowRepeats=*/true);
1099
1100 // In case 3) or if not all continuation edges have the same entry block,
1101 // create a single entry block as continuation for all branch regions.
1102 if (!continuation || !continuationPostDominatesAllRegions) {
1103 EdgeMultiplexer multiplexer = createSingleEntryBlock(
1104 loc: continuationEdges.front().getFromBlock()->getTerminator()->getLoc(),
1105 entryEdges: continuationEdges, getSwitchValue, getUndefValue, interface);
1106 continuation = multiplexer.getMultiplexerBlock();
1107 }
1108
1109 // Trigger reprocess of case 3) after creating the single entry block.
1110 if (!continuationPostDominatesAllRegions) {
1111 // Unlike in the general case, we are explicitly revisiting the same region
1112 // entry again after having changed its control flow edges and dominance.
1113 // We have to therefore explicitly invalidate the dominance tree.
1114 dominanceInfo.invalidate(region: regionEntry->getParent());
1115 return SmallVector<Block *>{regionEntry};
1116 }
1117
1118 SmallVector<Block *> newSubRegions;
1119
1120 // Empty blocks with the values they return to the parent op.
1121 SmallVector<std::pair<Block *, SmallVector<Value>>> createdEmptyBlocks;
1122
1123 // Create the branch regions.
1124 std::vector<Region> conditionalRegions(successorBranchRegions.size());
1125 for (auto &&[branchRegion, entryEdge, conditionalRegion] :
1126 llvm::zip(t&: successorBranchRegions, u: successorEdges(block: regionEntry),
1127 args&: conditionalRegions)) {
1128 if (branchRegion.empty()) {
1129 // If no block is part of the branch region, we create a dummy block to
1130 // place the region terminator into.
1131 createdEmptyBlocks.emplace_back(
1132 Args: new Block, Args: llvm::to_vector(Range: entryEdge.getSuccessorOperands()));
1133 conditionalRegion.push_back(block: createdEmptyBlocks.back().first);
1134 continue;
1135 }
1136
1137 createSingleExitBranchRegion(branchRegion, continuation, createdEmptyBlocks,
1138 conditionalRegion);
1139
1140 // The entries of the branch regions may only have redundant block arguments
1141 // since the edge to the branch region is always dominating.
1142 Block *subRegionEntryBlock = &conditionalRegion.front();
1143 for (auto &&[oldValue, newValue] :
1144 llvm::zip(t: subRegionEntryBlock->getArguments(),
1145 u: entryEdge.getSuccessorOperands()))
1146 oldValue.replaceAllUsesWith(newValue);
1147
1148 subRegionEntryBlock->eraseArguments(start: 0,
1149 num: subRegionEntryBlock->getNumArguments());
1150 newSubRegions.push_back(Elt: subRegionEntryBlock);
1151 }
1152
1153 Operation *structuredCondOp;
1154 {
1155 auto opBuilder = OpBuilder::atBlockTerminator(block: regionEntry);
1156 FailureOr<Operation *> result = interface.createStructuredBranchRegionOp(
1157 builder&: opBuilder, controlFlowCondOp: regionEntry->getTerminator(),
1158 resultTypes: continuation->getArgumentTypes(), regions: conditionalRegions);
1159 if (failed(Result: result))
1160 return failure();
1161 structuredCondOp = *result;
1162 regionEntry->getTerminator()->erase();
1163 }
1164
1165 for (auto &&[block, valueRange] : createdEmptyBlocks) {
1166 auto builder = OpBuilder::atBlockEnd(block);
1167 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(
1168 loc: structuredCondOp->getLoc(), builder, branchRegionOp: structuredCondOp, replacedControlFlowOp: nullptr,
1169 results: valueRange);
1170 if (failed(Result: result))
1171 return failure();
1172 }
1173
1174 // Any leftover users of the continuation must be from unconditional branches
1175 // in a branch region. There can only be at most one per branch region as
1176 // all branch regions have been made single-entry single-exit above.
1177 // Replace them with the region terminator.
1178 for (Operation *user : llvm::make_early_inc_range(Range: continuation->getUsers())) {
1179 assert(user->getNumSuccessors() == 1);
1180 auto builder = OpBuilder::atBlockTerminator(block: user->getBlock());
1181 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(
1182 loc: user->getLoc(), builder, branchRegionOp: structuredCondOp, replacedControlFlowOp: user,
1183 results: getMutableSuccessorOperands(block: user->getBlock(), successorIndex: 0).getAsOperandRange());
1184 if (failed(Result: result))
1185 return failure();
1186 user->erase();
1187 }
1188
1189 for (auto &&[oldValue, newValue] :
1190 llvm::zip(t: continuation->getArguments(), u: structuredCondOp->getResults()))
1191 oldValue.replaceAllUsesWith(newValue);
1192
1193 // Splice together the continuations operations with the region entry.
1194 regionEntry->getOperations().splice(where: regionEntry->end(),
1195 L2&: continuation->getOperations());
1196
1197 continuation->erase();
1198
1199 // After splicing the continuation, the region has to be reprocessed as it has
1200 // new successors.
1201 newSubRegions.push_back(Elt: regionEntry);
1202
1203 return newSubRegions;
1204}
1205
1206/// Transforms the region to only have a single block for every kind of
1207/// return-like operation that all previous occurrences of the return-like op
1208/// branch to. If the region only contains a single kind of return-like
1209/// operation, it creates a single-entry and single-exit region.
1210static ReturnLikeExitCombiner createSingleExitBlocksForReturnLike(
1211 Region &region, function_ref<Value(unsigned)> getSwitchValue,
1212 CFGToSCFInterface &interface) {
1213 ReturnLikeExitCombiner exitCombiner(region, interface);
1214
1215 for (Block &block : region.getBlocks()) {
1216 if (block.getNumSuccessors() != 0)
1217 continue;
1218 exitCombiner.combineExit(returnLikeOp: block.getTerminator(), getSwitchValue);
1219 }
1220
1221 return exitCombiner;
1222}
1223
1224/// Checks all preconditions of the transformation prior to any transformations.
1225/// Returns failure if any precondition is violated.
1226static LogicalResult checkTransformationPreconditions(Region &region) {
1227 for (Block &block : region.getBlocks())
1228 if (block.hasNoPredecessors() && !block.isEntryBlock())
1229 return block.front().emitOpError(
1230 message: "transformation does not support unreachable blocks");
1231
1232 WalkResult result = region.walk(callback: [](Operation *operation) {
1233 if (operation->getNumSuccessors() == 0)
1234 return WalkResult::advance();
1235
1236 // This transformation requires all ops with successors to implement the
1237 // branch op interface. It is impossible to adjust their block arguments
1238 // otherwise.
1239 auto branchOpInterface = dyn_cast<BranchOpInterface>(Val: operation);
1240 if (!branchOpInterface) {
1241 operation->emitOpError(message: "transformation does not support terminators with "
1242 "successors not implementing BranchOpInterface");
1243 return WalkResult::interrupt();
1244 }
1245 // Branch operations must have no side effects. Replacing them would not be
1246 // valid otherwise.
1247 if (!isMemoryEffectFree(op: branchOpInterface)) {
1248 branchOpInterface->emitOpError(
1249 message: "transformation does not support terminators with side effects");
1250 return WalkResult::interrupt();
1251 }
1252
1253 for (unsigned index : llvm::seq(Size: operation->getNumSuccessors())) {
1254 SuccessorOperands succOps = branchOpInterface.getSuccessorOperands(index);
1255
1256 // We cannot support operations with operation-produced successor operands
1257 // as it is currently not possible to pass them to any block arguments
1258 // other than the first. This breaks creating multiplexer blocks and would
1259 // likely need special handling elsewhere too.
1260 if (succOps.getProducedOperandCount() == 0)
1261 continue;
1262
1263 branchOpInterface->emitOpError(message: "transformation does not support "
1264 "operations with operation-produced "
1265 "successor operands");
1266 return WalkResult::interrupt();
1267 }
1268 return WalkResult::advance();
1269 });
1270 return failure(IsFailure: result.wasInterrupted());
1271}
1272
1273FailureOr<bool> mlir::transformCFGToSCF(Region &region,
1274 CFGToSCFInterface &interface,
1275 DominanceInfo &dominanceInfo) {
1276 if (region.empty() || region.hasOneBlock())
1277 return false;
1278
1279 if (failed(Result: checkTransformationPreconditions(region)))
1280 return failure();
1281
1282 DenseMap<Type, Value> typedUndefCache;
1283 auto getUndefValue = [&](Type type) {
1284 auto [iter, inserted] = typedUndefCache.try_emplace(Key: type);
1285 if (!inserted)
1286 return iter->second;
1287
1288 auto constantBuilder = OpBuilder::atBlockBegin(block: &region.front());
1289
1290 iter->second =
1291 interface.getUndefValue(loc: region.getLoc(), builder&: constantBuilder, type);
1292 return iter->second;
1293 };
1294
1295 // The transformation only creates all values in the range of 0 to
1296 // max(#numSuccessors). Therefore using a vector instead of a map.
1297 SmallVector<Value> switchValueCache;
1298 auto getSwitchValue = [&](unsigned value) {
1299 if (value < switchValueCache.size())
1300 if (switchValueCache[value])
1301 return switchValueCache[value];
1302
1303 auto constantBuilder = OpBuilder::atBlockBegin(block: &region.front());
1304
1305 switchValueCache.resize(
1306 N: std::max<size_t>(a: switchValueCache.size(), b: value + 1));
1307
1308 switchValueCache[value] =
1309 interface.getCFGSwitchValue(loc: region.getLoc(), builder&: constantBuilder, value);
1310 return switchValueCache[value];
1311 };
1312
1313 ReturnLikeExitCombiner exitCombiner =
1314 createSingleExitBlocksForReturnLike(region, getSwitchValue, interface);
1315
1316 // Invalidate any dominance tree on the region as the exit combiner has
1317 // added new blocks and edges.
1318 dominanceInfo.invalidate(region: &region);
1319
1320 SmallVector<Block *> workList = {&region.front()};
1321 while (!workList.empty()) {
1322 Block *current = workList.pop_back_val();
1323
1324 // Turn all top-level cycles in the CFG to structured control flow first.
1325 // After this transformation, the remaining CFG ops form a DAG.
1326 FailureOr<SmallVector<Block *>> newRegions =
1327 transformCyclesToSCFLoops(regionEntry: current, getSwitchValue, getUndefValue,
1328 interface, dominanceInfo, exitCombiner);
1329 if (failed(Result: newRegions))
1330 return failure();
1331
1332 // Add the newly created subregions to the worklist. These are the
1333 // bodies of the loops.
1334 llvm::append_range(C&: workList, R&: *newRegions);
1335 // Invalidate the dominance tree as blocks have been moved, created and
1336 // added during the cycle to structured loop transformation.
1337 if (!newRegions->empty())
1338 dominanceInfo.invalidate(region: current->getParent());
1339
1340 newRegions = transformToStructuredCFBranches(
1341 regionEntry: current, getSwitchValue, getUndefValue, interface, dominanceInfo);
1342 if (failed(Result: newRegions))
1343 return failure();
1344 // Invalidating the dominance tree is generally not required by the
1345 // transformation above as the new region entries correspond to unaffected
1346 // subtrees in the dominator tree. Only its parent nodes have changed but
1347 // won't be visited again.
1348 llvm::append_range(C&: workList, R&: *newRegions);
1349 }
1350
1351 return true;
1352}
1353

source code of mlir/lib/Transforms/Utils/CFGToSCF.cpp