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

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