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 poison values for any unused block arguments used by other
310 // entry blocks.
311 newSuccOperands[index] = getPoisonValue(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 poison values of a given type.
367 function_ref<Value(Type)> getPoisonValue;
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)> getPoisonValue,
382 llvm::SmallMapVector<Block *, unsigned, 4> &&entries,
383 Value dispatchFlag)
384 : multiplexerBlock(multiplexerBlock), getSwitchValue(getSwitchValue),
385 getPoisonValue(getPoisonValue), 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 return OperationEquivalence::isEquivalentTo(
408 lhs: const_cast<Operation *>(lhs), rhs: const_cast<Operation *>(rhs),
409 checkEquivalent: OperationEquivalence::ignoreValueEquivalence, markEquivalent: nullptr,
410 flags: OperationEquivalence::IgnoreLocations);
411 }
412};
413
414/// Utility-class for transforming a region to only have one single block for
415/// every return-like operation.
416class ReturnLikeExitCombiner {
417public:
418 ReturnLikeExitCombiner(Region &topLevelRegion, CFGToSCFInterface &interface)
419 : topLevelRegion(topLevelRegion), interface(interface) {}
420
421 /// Transforms `returnLikeOp` to a branch to the only block in the
422 /// region with an instance of `returnLikeOp`s kind.
423 void combineExit(Operation *returnLikeOp,
424 function_ref<Value(unsigned)> getSwitchValue,
425 function_ref<Value(Type)> getUndefValue) {
426 auto existing = returnLikeToCombinedExit.find(Val: returnLikeOp);
427 if (existing != returnLikeToCombinedExit.end() &&
428 existing->first == returnLikeOp)
429 return;
430
431 // If `returnLikeOp` is an unreachable terminator and an exit block of
432 // another return-like operation already exists, it is turned into a branch
433 // to that exit block with poison operands instead of getting an exit
434 // block of its own.
435 if (interface.isUnreachableTerminator(op: returnLikeOp) &&
436 !orderedExitBlocks.empty()) {
437 Block *exitBlock = orderedExitBlocks.front();
438 auto builder = OpBuilder::atBlockTerminator(block: returnLikeOp->getBlock());
439 interface.createSingleDestinationBranch(
440 loc: returnLikeOp->getLoc(), builder, dummyFlag: getSwitchValue(0), destination: exitBlock,
441 arguments: llvm::map_to_vector(C: exitBlock->getArgumentTypes(), F&: getUndefValue));
442 returnLikeOp->erase();
443 return;
444 }
445
446 auto [iter, inserted] = returnLikeToCombinedExit.try_emplace(Key: returnLikeOp);
447
448 Block *exitBlock = iter->second;
449 if (inserted) {
450 exitBlock = new Block;
451 iter->second = exitBlock;
452 orderedExitBlocks.push_back(Elt: exitBlock);
453 topLevelRegion.push_back(block: exitBlock);
454 exitBlock->addArguments(
455 types: returnLikeOp->getOperandTypes(),
456 locs: SmallVector<Location>(returnLikeOp->getNumOperands(),
457 returnLikeOp->getLoc()));
458 }
459
460 auto builder = OpBuilder::atBlockTerminator(block: returnLikeOp->getBlock());
461 interface.createSingleDestinationBranch(loc: returnLikeOp->getLoc(), builder,
462 dummyFlag: getSwitchValue(0), destination: exitBlock,
463 arguments: returnLikeOp->getOperands());
464
465 if (!inserted) {
466 returnLikeOp->erase();
467 return;
468 }
469
470 returnLikeOp->moveBefore(block: exitBlock, iterator: exitBlock->end());
471 returnLikeOp->setOperands(exitBlock->getArguments());
472 }
473
474private:
475 /// Mapping of return-like operation to block. All return-like operations
476 /// of the same kind with the same attributes, properties and types are seen
477 /// as equivalent. First occurrence seen is kept in the map.
478 llvm::SmallDenseMap<Operation *, Block *, 4, ReturnLikeOpEquivalence>
479 returnLikeToCombinedExit;
480 /// All exit blocks in the order they were created.
481 SmallVector<Block *, 4> orderedExitBlocks;
482 Region &topLevelRegion;
483 CFGToSCFInterface &interface;
484};
485
486} // namespace
487
488/// Returns a range of all edges from `block` to each of its successors.
489static auto successorEdges(Block *block) {
490 return llvm::map_range(C: llvm::seq(Size: block->getNumSuccessors()),
491 F: [=](unsigned index) { return Edge(block, index); });
492}
493
494/// Calculates entry, exit and back edges of the given cycle.
495static CycleEdges
496calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) {
497 CycleEdges result;
498 SmallPtrSet<Block *, 8> entryBlocks;
499
500 // First identify all exit and entry edges by checking whether any successors
501 // or predecessors are from outside the cycles.
502 for (Block *block : cycles) {
503 for (auto pred = block->pred_begin(); pred != block->pred_end(); pred++) {
504 if (cycles.contains(key: *pred))
505 continue;
506
507 result.entryEdges.emplace_back(Args: *pred, Args: pred.getSuccessorIndex());
508 entryBlocks.insert(Ptr: block);
509 }
510
511 for (auto &&[succIndex, succ] : llvm::enumerate(First: block->getSuccessors())) {
512 if (cycles.contains(key: succ))
513 continue;
514
515 result.exitEdges.emplace_back(Args&: block, Args&: succIndex);
516 }
517 }
518
519 // With the entry blocks identified, find all the back edges.
520 for (Block *block : cycles) {
521 for (auto &&[succIndex, succ] : llvm::enumerate(First: block->getSuccessors())) {
522 if (!entryBlocks.contains(Ptr: succ))
523 continue;
524
525 result.backEdges.emplace_back(Args&: block, Args&: succIndex);
526 }
527 }
528
529 return result;
530}
531
532/// Creates a single entry block out of multiple entry edges using an edge
533/// multiplexer and returns it.
534static EdgeMultiplexer
535createSingleEntryBlock(Location loc, ArrayRef<Edge> entryEdges,
536 function_ref<Value(unsigned)> getSwitchValue,
537 function_ref<Value(Type)> getUndefValue,
538 CFGToSCFInterface &interface) {
539 auto result = EdgeMultiplexer::create(
540 loc, entryBlocks: llvm::map_to_vector(C&: entryEdges, F: std::mem_fn(pm: &Edge::getSuccessor)),
541 getSwitchValue, getUndefValue);
542
543 // Redirect the edges prior to creating the switch op.
544 // We guarantee that predecessors are up to date.
545 for (Edge edge : entryEdges)
546 result.redirectEdge(edge);
547
548 auto builder = OpBuilder::atBlockBegin(block: result.getMultiplexerBlock());
549 result.createSwitch(loc, builder, interface);
550
551 return result;
552}
553
554namespace {
555/// Special loop properties of a structured loop.
556/// A structured loop is a loop satisfying all of the following:
557/// * Has at most one entry, one exit and one back edge.
558/// * The back edge originates from the same block as the exit edge.
559struct StructuredLoopProperties {
560 /// Block containing both the single exit edge and the single back edge.
561 Block *latch;
562 /// Loop condition of type equal to a value returned by `getSwitchValue`.
563 Value condition;
564 /// Exit block which is the only successor of the loop.
565 Block *exitBlock;
566};
567} // namespace
568
569/// Transforms a loop into a structured loop with only a single back edge and
570/// exiting edge, originating from the same block.
571static FailureOr<StructuredLoopProperties> createSingleExitingLatch(
572 Location loc, ArrayRef<Edge> backEdges, ArrayRef<Edge> exitEdges,
573 function_ref<Value(unsigned)> getSwitchValue,
574 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
575 ReturnLikeExitCombiner &exitCombiner) {
576 assert(llvm::all_equal(
577 llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor))) &&
578 "All repetition edges must lead to the single loop header");
579
580 // First create the multiplexer block, which will be our latch, for all back
581 // edges and exit edges. We pass an additional argument to the multiplexer
582 // block which indicates whether the latch was reached from what was
583 // originally a back edge or an exit block.
584 // This is later used to branch using the new only back edge.
585 SmallVector<Block *> successors;
586 llvm::append_range(
587 C&: successors, R: llvm::map_range(C&: backEdges, F: std::mem_fn(pm: &Edge::getSuccessor)));
588 llvm::append_range(
589 C&: successors, R: llvm::map_range(C&: exitEdges, F: std::mem_fn(pm: &Edge::getSuccessor)));
590 auto multiplexer =
591 EdgeMultiplexer::create(loc, entryBlocks: successors, getSwitchValue, getUndefValue,
592 /*extraArgs=*/getSwitchValue(0).getType());
593
594 auto *latchBlock = multiplexer.getMultiplexerBlock();
595
596 // Create a separate exit block that comes right after the latch.
597 auto *exitBlock = new Block;
598 exitBlock->insertAfter(block: latchBlock);
599
600 // Since this is a loop, all back edges point to the same loop header.
601 Block *loopHeader = backEdges.front().getSuccessor();
602
603 // Redirect the edges prior to creating the switch op.
604 // We guarantee that predecessors are up to date.
605
606 // Redirecting back edges with `shouldRepeat` as 1.
607 for (Edge backEdge : backEdges)
608 multiplexer.redirectEdge(edge: backEdge, /*extraArgs=*/getSwitchValue(1));
609
610 // Redirecting exits edges with `shouldRepeat` as 0.
611 for (Edge exitEdge : exitEdges)
612 multiplexer.redirectEdge(edge: exitEdge, /*extraArgs=*/getSwitchValue(0));
613
614 // Create the new only back edge to the loop header. Branch to the
615 // exit block otherwise.
616 Value shouldRepeat = latchBlock->getArguments().back();
617 {
618 auto builder = OpBuilder::atBlockBegin(block: latchBlock);
619 interface.createConditionalBranch(
620 loc, builder, condition: shouldRepeat, trueDest: loopHeader,
621 trueArgs: latchBlock->getArguments().take_front(N: loopHeader->getNumArguments()),
622 /*falseDest=*/exitBlock,
623 /*falseArgs=*/{});
624 }
625
626 {
627 auto builder = OpBuilder::atBlockBegin(block: exitBlock);
628 if (!exitEdges.empty()) {
629 // Create the switch dispatching to what were originally the multiple exit
630 // blocks. The loop header has to explicitly be excluded in the below
631 // switch as we would otherwise be creating a new loop again. All back
632 // edges leading to the loop header have already been handled in the
633 // switch above. The remaining edges can only jump to blocks outside the
634 // loop.
635
636 SmallPtrSet<Block *, 1> excluded = {loopHeader};
637 multiplexer.createSwitch(loc, builder, interface, excluded);
638 } else {
639 // A loop without an exit edge is a statically known infinite loop.
640 // Since structured control flow ops are not terminator ops, the caller
641 // has to create a fitting return-like unreachable terminator operation.
642 FailureOr<Operation *> terminator = interface.createUnreachableTerminator(
643 loc, builder, region&: *latchBlock->getParent());
644 if (failed(Result: terminator))
645 return failure();
646 // Transform the just created transform operation in the case that an
647 // occurrence of it existed in input IR.
648 exitCombiner.combineExit(returnLikeOp: *terminator, getSwitchValue, getUndefValue);
649 }
650 }
651
652 return StructuredLoopProperties{.latch: latchBlock, /*condition=*/shouldRepeat,
653 .exitBlock: exitBlock};
654}
655
656/// Transforms a structured loop into a loop in reduce form.
657///
658/// Reduce form is defined as a structured loop where:
659/// (0) No values defined within the loop body are used outside the loop body.
660/// (1) The block arguments and successor operands of the exit block are equal
661/// to the block arguments of the loop header and the successor operands
662/// of the back edge.
663///
664/// This is required for many structured control flow ops as they tend
665/// to not have separate "loop result arguments" and "loop iteration arguments"
666/// at the end of the block. Rather, the "loop iteration arguments" from the
667/// last iteration are the result of the loop.
668///
669/// Note that the requirement of (0) is shared with LCSSA form in LLVM. However,
670/// due to this being a structured loop instead of a general loop, we do not
671/// require complicated dominance algorithms nor SSA updating making this
672/// implementation easier than creating a generic LCSSA transformation pass.
673static SmallVector<Value>
674transformToReduceLoop(Block *loopHeader, Block *exitBlock,
675 const llvm::SmallSetVector<Block *, 4> &loopBlocks,
676 function_ref<Value(Type)> getUndefValue,
677 DominanceInfo &dominanceInfo) {
678 Block *latch = exitBlock->getSinglePredecessor();
679 assert(latch &&
680 "Exit block must have only latch as predecessor at this point");
681 assert(exitBlock->getNumArguments() == 0 &&
682 "Exit block mustn't have any block arguments at this point");
683
684 unsigned loopHeaderIndex = 0;
685 unsigned exitBlockIndex = 1;
686 if (latch->getSuccessor(i: loopHeaderIndex) != loopHeader)
687 std::swap(a&: loopHeaderIndex, b&: exitBlockIndex);
688
689 assert(latch->getSuccessor(loopHeaderIndex) == loopHeader);
690 assert(latch->getSuccessor(exitBlockIndex) == exitBlock);
691
692 MutableOperandRange exitBlockSuccessorOperands =
693 getMutableSuccessorOperands(block: latch, successorIndex: exitBlockIndex);
694 // Save the values as a vector, not a `MutableOperandRange` as the latter gets
695 // invalidated when mutating the operands through a different
696 // `MutableOperandRange` of the same operation.
697 SmallVector<Value> loopHeaderSuccessorOperands =
698 llvm::to_vector(Range: getSuccessorOperands(block: latch, successorIndex: loopHeaderIndex));
699
700 // Add all values used in the next iteration to the exit block. Replace
701 // any uses that are outside the loop with the newly created exit block.
702 for (Value arg : loopHeaderSuccessorOperands) {
703 BlockArgument exitArg = exitBlock->addArgument(type: arg.getType(), loc: arg.getLoc());
704 exitBlockSuccessorOperands.append(values: arg);
705 arg.replaceUsesWithIf(newValue: exitArg, shouldReplace: [&](OpOperand &use) {
706 return !loopBlocks.contains(key: use.getOwner()->getBlock());
707 });
708 }
709
710 // Loop below might add block arguments to the latch and loop header.
711 // Save the block arguments prior to the loop to not process these.
712 SmallVector<BlockArgument> latchBlockArgumentsPrior =
713 llvm::to_vector(Range: latch->getArguments());
714 SmallVector<BlockArgument> loopHeaderArgumentsPrior =
715 llvm::to_vector(Range: loopHeader->getArguments());
716
717 // Go over all values defined within the loop body. If any of them are used
718 // outside the loop body, create a block argument on the exit block and loop
719 // header and replace the outside uses with the exit block argument.
720 // The loop header block argument is added to satisfy requirement (1) in the
721 // reduce form condition.
722 for (Block *loopBlock : loopBlocks) {
723 // Cache dominance queries for loopBlock.
724 // There are likely to be many duplicate queries as there can be many value
725 // definitions within a block.
726 llvm::SmallDenseMap<Block *, bool> dominanceCache;
727 // Returns true if `loopBlock` dominates `block`.
728 auto loopBlockDominates = [&](Block *block) {
729 auto [iter, inserted] = dominanceCache.try_emplace(Key: block);
730 if (!inserted)
731 return iter->second;
732 iter->second = dominanceInfo.dominates(a: loopBlock, b: block);
733 return iter->second;
734 };
735
736 auto checkValue = [&](Value value) {
737 Value blockArgument;
738 for (OpOperand &use : llvm::make_early_inc_range(Range: value.getUses())) {
739 // Go through all the parent blocks and find the one part of the region
740 // of the loop. If the block is part of the loop, then the value does
741 // not escape the loop through this use.
742 Block *currBlock = use.getOwner()->getBlock();
743 while (currBlock && currBlock->getParent() != loopHeader->getParent())
744 currBlock = currBlock->getParentOp()->getBlock();
745 if (loopBlocks.contains(key: currBlock))
746 continue;
747
748 // Block argument is only created the first time it is required.
749 if (!blockArgument) {
750 blockArgument =
751 exitBlock->addArgument(type: value.getType(), loc: value.getLoc());
752 loopHeader->addArgument(type: value.getType(), loc: value.getLoc());
753
754 // `value` might be defined in a block that does not dominate `latch`
755 // but previously dominated an exit block with a use.
756 // In this case, add a block argument to the latch and go through all
757 // predecessors. If the value dominates the predecessor, pass the
758 // value as a successor operand, otherwise pass poison.
759 // The above is unnecessary if the value is a block argument of the
760 // latch or if `value` dominates all predecessors.
761 Value argument = value;
762 if (value.getParentBlock() != latch &&
763 llvm::any_of(Range: latch->getPredecessors(), P: [&](Block *pred) {
764 return !loopBlockDominates(pred);
765 })) {
766 argument = latch->addArgument(type: value.getType(), loc: value.getLoc());
767 for (auto iter = latch->pred_begin(); iter != latch->pred_end();
768 ++iter) {
769 Value succOperand = value;
770 if (!loopBlockDominates(*iter))
771 succOperand = getUndefValue(value.getType());
772
773 getMutableSuccessorOperands(block: *iter, successorIndex: iter.getSuccessorIndex())
774 .append(values: succOperand);
775 }
776 }
777
778 loopHeaderSuccessorOperands.push_back(Elt: argument);
779 for (Edge edge : successorEdges(block: latch))
780 edge.getMutableSuccessorOperands().append(values: argument);
781 }
782
783 use.set(blockArgument);
784 }
785 };
786
787 if (loopBlock == latch)
788 llvm::for_each(Range&: latchBlockArgumentsPrior, F: checkValue);
789 else if (loopBlock == loopHeader)
790 llvm::for_each(Range&: loopHeaderArgumentsPrior, F: checkValue);
791 else
792 llvm::for_each(Range: loopBlock->getArguments(), F: checkValue);
793
794 for (Operation &op : *loopBlock)
795 llvm::for_each(Range: op.getResults(), F: checkValue);
796 }
797
798 // New block arguments may have been added to the loop header.
799 // Adjust the entry edges to pass poison values to these.
800 for (auto iter = loopHeader->pred_begin(); iter != loopHeader->pred_end();
801 ++iter) {
802 // Latch successor arguments have already been handled.
803 if (*iter == latch)
804 continue;
805
806 MutableOperandRange succOps =
807 getMutableSuccessorOperands(block: *iter, successorIndex: iter.getSuccessorIndex());
808 succOps.append(values: llvm::map_to_vector(
809 C: loopHeader->getArguments().drop_front(N: succOps.size()),
810 F: [&](BlockArgument arg) { return getUndefValue(arg.getType()); }));
811 }
812
813 return loopHeaderSuccessorOperands;
814}
815
816/// Transforms all outer-most cycles in the region with the region entry
817/// `regionEntry` into structured loops. Returns the entry blocks of any newly
818/// created regions potentially requiring further transformations.
819static FailureOr<SmallVector<Block *>> transformCyclesToSCFLoops(
820 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,
821 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
822 DominanceInfo &dominanceInfo, ReturnLikeExitCombiner &exitCombiner) {
823 SmallVector<Block *> newSubRegions;
824 auto scc = llvm::scc_begin(G: regionEntry);
825 while (!scc.isAtEnd()) {
826 if (!scc.hasCycle()) {
827 ++scc;
828 continue;
829 }
830
831 // Save the set and increment the SCC iterator early to avoid our
832 // modifications breaking the SCC iterator.
833 llvm::SmallSetVector<Block *, 4> cycleBlockSet(scc->begin(), scc->end());
834 ++scc;
835
836 CycleEdges edges = calculateCycleEdges(cycles: cycleBlockSet);
837 Block *loopHeader = edges.entryEdges.front().getSuccessor();
838 // First turn the cycle into a loop by creating a single entry block if
839 // needed.
840 if (edges.entryEdges.size() > 1) {
841 SmallVector<Edge> edgesToEntryBlocks;
842 llvm::append_range(C&: edgesToEntryBlocks, R&: edges.entryEdges);
843 llvm::append_range(C&: edgesToEntryBlocks, R&: edges.backEdges);
844
845 EdgeMultiplexer multiplexer = createSingleEntryBlock(
846 loc: loopHeader->getTerminator()->getLoc(), entryEdges: edgesToEntryBlocks,
847 getSwitchValue, getUndefValue, interface);
848
849 loopHeader = multiplexer.getMultiplexerBlock();
850 }
851 cycleBlockSet.insert(X: loopHeader);
852
853 // Then turn it into a structured loop by creating a single latch.
854 FailureOr<StructuredLoopProperties> loopProperties =
855 createSingleExitingLatch(
856 loc: edges.backEdges.front().getFromBlock()->getTerminator()->getLoc(),
857 backEdges: edges.backEdges, exitEdges: edges.exitEdges, getSwitchValue, getUndefValue,
858 interface, exitCombiner);
859 if (failed(Result: loopProperties))
860 return failure();
861
862 Block *latchBlock = loopProperties->latch;
863 Block *exitBlock = loopProperties->exitBlock;
864 cycleBlockSet.insert(X: latchBlock);
865 cycleBlockSet.insert(X: loopHeader);
866
867 // Finally, turn it into reduce form.
868 SmallVector<Value> iterationValues = transformToReduceLoop(
869 loopHeader, exitBlock, loopBlocks: cycleBlockSet, getUndefValue, dominanceInfo);
870
871 // Create a block acting as replacement for the loop header and insert
872 // the structured loop into it.
873 auto *newLoopParentBlock = new Block;
874 newLoopParentBlock->insertBefore(block: loopHeader);
875 addBlockArgumentsFromOther(block: newLoopParentBlock, other: loopHeader);
876
877 Region::BlockListType &blocks = regionEntry->getParent()->getBlocks();
878 Region loopBody;
879 // Make sure the loop header is the entry block.
880 loopBody.push_back(block: blocks.remove(IT: loopHeader));
881 for (Block *block : cycleBlockSet)
882 if (block != latchBlock && block != loopHeader)
883 loopBody.push_back(block: blocks.remove(IT: block));
884 // And the latch is the last block.
885 loopBody.push_back(block: blocks.remove(IT: latchBlock));
886
887 Operation *oldTerminator = latchBlock->getTerminator();
888 oldTerminator->remove();
889
890 auto builder = OpBuilder::atBlockBegin(block: newLoopParentBlock);
891 FailureOr<Operation *> structuredLoopOp =
892 interface.createStructuredDoWhileLoopOp(
893 builder, replacedOp: oldTerminator, loopValuesInit: newLoopParentBlock->getArguments(),
894 condition: loopProperties->condition, loopValuesNextIter: iterationValues, loopBody: std::move(loopBody));
895 if (failed(Result: structuredLoopOp))
896 return failure();
897 oldTerminator->erase();
898
899 newSubRegions.push_back(Elt: loopHeader);
900
901 for (auto &&[oldValue, newValue] : llvm::zip(
902 t: exitBlock->getArguments(), u: (*structuredLoopOp)->getResults()))
903 oldValue.replaceAllUsesWith(newValue);
904
905 loopHeader->replaceAllUsesWith(newValue&: newLoopParentBlock);
906 // Merge the exit block right after the loop operation.
907 newLoopParentBlock->getOperations().splice(where: newLoopParentBlock->end(),
908 L2&: exitBlock->getOperations());
909 exitBlock->erase();
910 }
911 return newSubRegions;
912}
913
914/// Makes sure the branch region only has a single exit. This is required by the
915/// recursive part of the algorithm, as it expects the CFG to be single-entry
916/// and single-exit. This is done by simply creating an empty block if there
917/// is more than one block with an edge to the continuation block. All blocks
918/// with edges to the continuation are then redirected to this block. A region
919/// terminator is later placed into the block.
920static void createSingleExitBranchRegion(
921 ArrayRef<Block *> branchRegion, Block *continuation,
922 SmallVectorImpl<std::pair<Block *, SmallVector<Value>>> &createdEmptyBlocks,
923 Region &conditionalRegion) {
924 Block *singleExitBlock = nullptr;
925 std::optional<Edge> previousEdgeToContinuation;
926 Region::BlockListType &parentBlockList =
927 branchRegion.front()->getParent()->getBlocks();
928 for (Block *block : branchRegion) {
929 for (Edge edge : successorEdges(block)) {
930 if (edge.getSuccessor() != continuation)
931 continue;
932
933 if (!previousEdgeToContinuation) {
934 previousEdgeToContinuation = edge;
935 continue;
936 }
937
938 // If this is not the first edge to the continuation we create the
939 // single exit block and redirect the edges.
940 if (!singleExitBlock) {
941 singleExitBlock = new Block;
942 addBlockArgumentsFromOther(block: singleExitBlock, other: continuation);
943 previousEdgeToContinuation->setSuccessor(singleExitBlock);
944 createdEmptyBlocks.emplace_back(Args&: singleExitBlock,
945 Args: singleExitBlock->getArguments());
946 }
947
948 edge.setSuccessor(singleExitBlock);
949 }
950
951 conditionalRegion.push_back(block: parentBlockList.remove(IT: block));
952 }
953
954 if (singleExitBlock)
955 conditionalRegion.push_back(block: singleExitBlock);
956}
957
958/// Returns true if this block is an exit block of the region.
959static bool isRegionExitBlock(Block *block) {
960 return block->getNumSuccessors() == 0;
961}
962
963/// Transforms the first occurrence of conditional control flow in `regionEntry`
964/// into conditionally executed regions. Returns the entry block of the created
965/// regions and the region after the conditional control flow.
966static FailureOr<SmallVector<Block *>> transformToStructuredCFBranches(
967 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,
968 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,
969 DominanceInfo &dominanceInfo) {
970 // Trivial region.
971 if (regionEntry->getNumSuccessors() == 0)
972 return SmallVector<Block *>{};
973
974 if (regionEntry->getNumSuccessors() == 1) {
975 // Single successor we can just splice together.
976 Block *successor = regionEntry->getSuccessor(i: 0);
977 for (auto &&[oldValue, newValue] : llvm::zip(
978 t: successor->getArguments(), u: getSuccessorOperands(block: regionEntry, successorIndex: 0)))
979 oldValue.replaceAllUsesWith(newValue);
980 regionEntry->getTerminator()->erase();
981
982 regionEntry->getOperations().splice(where: regionEntry->end(),
983 L2&: successor->getOperations());
984 successor->erase();
985 return SmallVector<Block *>{regionEntry};
986 }
987
988 // Split the CFG into "#numSuccessor + 1" regions.
989 // For every edge to a successor, the blocks it solely dominates are
990 // determined and become the region following that edge.
991 // The last region is the continuation that follows the branch regions.
992 SmallPtrSet<Block *, 8> notContinuation;
993 notContinuation.insert(Ptr: regionEntry);
994 SmallVector<SmallVector<Block *>> successorBranchRegions(
995 regionEntry->getNumSuccessors());
996 for (auto &&[blockList, succ] :
997 llvm::zip(t&: successorBranchRegions, u: regionEntry->getSuccessors())) {
998 // If the region entry is not the only predecessor, then the edge does not
999 // dominate the block it leads to.
1000 if (succ->getSinglePredecessor() != regionEntry)
1001 continue;
1002
1003 // Otherwise get all blocks it dominates in DFS/pre-order.
1004 DominanceInfoNode *node = dominanceInfo.getNode(a: succ);
1005 for (DominanceInfoNode *curr : llvm::depth_first(G: node)) {
1006 blockList.push_back(Elt: curr->getBlock());
1007 notContinuation.insert(Ptr: curr->getBlock());
1008 }
1009 }
1010
1011 // Finds all relevant edges and checks the shape of the control flow graph at
1012 // this point.
1013 // Branch regions may either:
1014 // * Be post-dominated by the continuation
1015 // * Be post-dominated by a return-like op
1016 // * Dominate a return-like op and have an edge to the continuation.
1017 //
1018 // The control flow graph may then be one of three cases:
1019 // 1) All branch regions are post-dominated by the continuation. This is the
1020 // usual case. If there are multiple entry blocks into the continuation a
1021 // single entry block has to be created. A structured control flow op
1022 // can then be created from the branch regions.
1023 //
1024 // 2) No branch region has an edge to a continuation:
1025 // +-----+
1026 // +-----+ bb0 +----+
1027 // v +-----+ v
1028 // Region 1 +-+--+ ... +-+--+ Region n
1029 // |ret1| |ret2|
1030 // +----+ +----+
1031 //
1032 // This can only occur if every region ends with a different kind of
1033 // return-like op. In that case the control flow operation must stay as we are
1034 // unable to create a single exit-block. We can nevertheless process all its
1035 // successors as they single-entry, single-exit regions.
1036 //
1037 // 3) Only some branch regions are post-dominated by the continuation.
1038 // The other branch regions may either be post-dominated by a return-like op
1039 // or lead to either the continuation or return-like op.
1040 // In this case we also create a single entry block like in 1) that also
1041 // includes all edges to the return-like op:
1042 // +-----+
1043 // +-----+ bb0 +----+
1044 // v +-----+ v
1045 // Region 1 +-+-+ ... +-+-+ Region n
1046 // +---+ +---+
1047 // +---+ |... ...
1048 // |ret|<-+ | |
1049 // +---+ | +---+ |
1050 // +---->++ ++<---+
1051 // | |
1052 // ++ ++ Region T
1053 // +---+
1054 // This transforms to:
1055 // +-----+
1056 // +-----+ bb0 +----+
1057 // v +-----+ v
1058 // Region 1 +-+-+ ... +-+-+ Region n
1059 // +---+ +---+
1060 // ... +-----+ ...
1061 // +---->+ bbM +<---+
1062 // +-----+
1063 // +-----+ |
1064 // | v
1065 // +---+ | +---+
1066 // |ret+<---+ ++ ++
1067 // +---+ | |
1068 // ++ ++ Region T
1069 // +---+
1070 //
1071 // bb0 to bbM is now a single-entry, single-exit region that applies to case
1072 // 1). The control flow op at the end of bbM will trigger case 2.
1073 SmallVector<Edge> continuationEdges;
1074 bool continuationPostDominatesAllRegions = true;
1075 bool noSuccessorHasContinuationEdge = true;
1076 for (auto &&[entryEdge, branchRegion] :
1077 llvm::zip(t: successorEdges(block: regionEntry), u&: successorBranchRegions)) {
1078
1079 // If the branch region is empty then the branch target itself is part of
1080 // the continuation.
1081 if (branchRegion.empty()) {
1082 continuationEdges.push_back(Elt: entryEdge);
1083 noSuccessorHasContinuationEdge = false;
1084 continue;
1085 }
1086
1087 for (Block *block : branchRegion) {
1088 if (isRegionExitBlock(block)) {
1089 // If a return-like op is part of the branch region then the
1090 // continuation no longer post-dominates the branch region.
1091 // Add all its incoming edges to edge list to create the single-exit
1092 // block for all branch regions.
1093 continuationPostDominatesAllRegions = false;
1094 for (auto iter = block->pred_begin(); iter != block->pred_end();
1095 ++iter) {
1096 continuationEdges.emplace_back(Args: *iter, Args: iter.getSuccessorIndex());
1097 }
1098 continue;
1099 }
1100
1101 for (Edge edge : successorEdges(block)) {
1102 if (notContinuation.contains(Ptr: edge.getSuccessor()))
1103 continue;
1104
1105 continuationEdges.push_back(Elt: edge);
1106 noSuccessorHasContinuationEdge = false;
1107 }
1108 }
1109 }
1110
1111 // case 2) Keep the control flow op but process its successors further.
1112 if (noSuccessorHasContinuationEdge)
1113 return llvm::to_vector(Range: regionEntry->getSuccessors());
1114
1115 Block *continuation = llvm::find_singleton<Block>(
1116 Range&: continuationEdges, P: [](Edge edge, bool) { return edge.getSuccessor(); },
1117 /*AllowRepeats=*/true);
1118
1119 // In case 3) or if not all continuation edges have the same entry block,
1120 // create a single entry block as continuation for all branch regions.
1121 if (!continuation || !continuationPostDominatesAllRegions) {
1122 EdgeMultiplexer multiplexer = createSingleEntryBlock(
1123 loc: continuationEdges.front().getFromBlock()->getTerminator()->getLoc(),
1124 entryEdges: continuationEdges, getSwitchValue, getUndefValue, interface);
1125 continuation = multiplexer.getMultiplexerBlock();
1126 }
1127
1128 // Trigger reprocess of case 3) after creating the single entry block.
1129 if (!continuationPostDominatesAllRegions) {
1130 // Unlike in the general case, we are explicitly revisiting the same region
1131 // entry again after having changed its control flow edges and dominance.
1132 // We have to therefore explicitly invalidate the dominance tree.
1133 dominanceInfo.invalidate(region: regionEntry->getParent());
1134 return SmallVector<Block *>{regionEntry};
1135 }
1136
1137 SmallVector<Block *> newSubRegions;
1138
1139 // Empty blocks with the values they return to the parent op.
1140 SmallVector<std::pair<Block *, SmallVector<Value>>> createdEmptyBlocks;
1141
1142 // Create the branch regions.
1143 std::vector<Region> conditionalRegions(successorBranchRegions.size());
1144 for (auto &&[branchRegion, entryEdge, conditionalRegion] :
1145 llvm::zip(t&: successorBranchRegions, u: successorEdges(block: regionEntry),
1146 args&: conditionalRegions)) {
1147 if (branchRegion.empty()) {
1148 // If no block is part of the branch region, we create a dummy block to
1149 // place the region terminator into.
1150 createdEmptyBlocks.emplace_back(
1151 Args: new Block, Args: llvm::to_vector(Range: entryEdge.getSuccessorOperands()));
1152 conditionalRegion.push_back(block: createdEmptyBlocks.back().first);
1153 continue;
1154 }
1155
1156 createSingleExitBranchRegion(branchRegion, continuation, createdEmptyBlocks,
1157 conditionalRegion);
1158
1159 // The entries of the branch regions may only have redundant block arguments
1160 // since the edge to the branch region is always dominating.
1161 Block *subRegionEntryBlock = &conditionalRegion.front();
1162 for (auto &&[oldValue, newValue] :
1163 llvm::zip(t: subRegionEntryBlock->getArguments(),
1164 u: entryEdge.getSuccessorOperands()))
1165 oldValue.replaceAllUsesWith(newValue);
1166
1167 subRegionEntryBlock->eraseArguments(start: 0,
1168 num: subRegionEntryBlock->getNumArguments());
1169 newSubRegions.push_back(Elt: subRegionEntryBlock);
1170 }
1171
1172 Operation *structuredCondOp;
1173 {
1174 auto opBuilder = OpBuilder::atBlockTerminator(block: regionEntry);
1175 FailureOr<Operation *> result = interface.createStructuredBranchRegionOp(
1176 builder&: opBuilder, controlFlowCondOp: regionEntry->getTerminator(),
1177 resultTypes: continuation->getArgumentTypes(), regions: conditionalRegions);
1178 if (failed(Result: result)) {
1179 // Blocks were moved from the parent region into conditionalRegions before
1180 // calling createStructuredBranchRegionOp. On failure, move them back to
1181 // avoid use-after-free crashes: the moved blocks may still be referenced
1182 // as successors by blocks remaining in the parent region, so destroying
1183 // conditionalRegions with live uses would trigger an assertion.
1184 // This patching does not undo the change, it barely makes it so that the
1185 // pass can gracefully fail instead of crashing.
1186 Region *parentRegion = regionEntry->getParent();
1187 for (Region &conditionalRegion : conditionalRegions)
1188 parentRegion->getBlocks().splice(where: parentRegion->getBlocks().end(),
1189 L2&: conditionalRegion.getBlocks());
1190 return failure();
1191 }
1192 structuredCondOp = *result;
1193 regionEntry->getTerminator()->erase();
1194 }
1195
1196 for (auto &&[block, valueRange] : createdEmptyBlocks) {
1197 auto builder = OpBuilder::atBlockEnd(block);
1198 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(
1199 loc: structuredCondOp->getLoc(), builder, branchRegionOp: structuredCondOp, replacedControlFlowOp: nullptr,
1200 results: valueRange);
1201 if (failed(Result: result))
1202 return failure();
1203 }
1204
1205 // Any leftover users of the continuation must be from unconditional branches
1206 // in a branch region. There can only be at most one per branch region as
1207 // all branch regions have been made single-entry single-exit above.
1208 // Replace them with the region terminator.
1209 for (Operation *user : llvm::make_early_inc_range(Range: continuation->getUsers())) {
1210 assert(user->getNumSuccessors() == 1);
1211 auto builder = OpBuilder::atBlockTerminator(block: user->getBlock());
1212 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(
1213 loc: user->getLoc(), builder, branchRegionOp: structuredCondOp, replacedControlFlowOp: user,
1214 results: getMutableSuccessorOperands(block: user->getBlock(), successorIndex: 0).getAsOperandRange());
1215 if (failed(Result: result))
1216 return failure();
1217 user->erase();
1218 }
1219
1220 for (auto &&[oldValue, newValue] :
1221 llvm::zip(t: continuation->getArguments(), u: structuredCondOp->getResults()))
1222 oldValue.replaceAllUsesWith(newValue);
1223
1224 // Splice together the continuations operations with the region entry.
1225 regionEntry->getOperations().splice(where: regionEntry->end(),
1226 L2&: continuation->getOperations());
1227
1228 continuation->erase();
1229
1230 // After splicing the continuation, the region has to be reprocessed as it has
1231 // new successors.
1232 newSubRegions.push_back(Elt: regionEntry);
1233
1234 return newSubRegions;
1235}
1236
1237/// Transforms the region to only have a single block for every kind of
1238/// return-like operation that all previous occurrences of the return-like op
1239/// branch to. If the region only contains a single kind of return-like
1240/// operation, it creates a single-entry and single-exit region.
1241static ReturnLikeExitCombiner createSingleExitBlocksForReturnLike(
1242 Region &region, function_ref<Value(unsigned)> getSwitchValue,
1243 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface) {
1244 ReturnLikeExitCombiner exitCombiner(region, interface);
1245
1246 // Combine the exits of all non-unreachable return-like operations first so
1247 // that unreachable terminators can be merged into their exit blocks,
1248 // regardless of the order in which they appear in the region.
1249 for (Block &block : region.getBlocks()) {
1250 if (block.getNumSuccessors() != 0 ||
1251 interface.isUnreachableTerminator(op: block.getTerminator()))
1252 continue;
1253 exitCombiner.combineExit(returnLikeOp: block.getTerminator(), getSwitchValue,
1254 getUndefValue);
1255 }
1256 for (Block &block : region.getBlocks()) {
1257 if (block.getNumSuccessors() != 0 ||
1258 !interface.isUnreachableTerminator(op: block.getTerminator()))
1259 continue;
1260 exitCombiner.combineExit(returnLikeOp: block.getTerminator(), getSwitchValue,
1261 getUndefValue);
1262 }
1263
1264 return exitCombiner;
1265}
1266
1267/// Checks all preconditions of the transformation prior to any transformations.
1268/// Returns failure if any precondition is violated.
1269static LogicalResult
1270checkTransformationPreconditions(Region &region, CFGToSCFInterface &interface) {
1271 llvm::df_iterator_default_set<Block *, 16> reachable;
1272 // Find all blocks reachable from the entry.
1273 for (Block *block : depth_first_ext(G: &region.front(), S&: reachable))
1274 (void)block;
1275
1276 for (Block &block : region.getBlocks())
1277 if (!reachable.contains(Ptr: &block))
1278 return block.front().emitOpError(
1279 message: "transformation does not support unreachable blocks");
1280
1281 WalkResult result = region.walk(callback: [](Operation *operation) {
1282 if (operation->getNumSuccessors() == 0)
1283 return WalkResult::advance();
1284
1285 // This transformation requires all ops with successors to implement the
1286 // branch op interface. It is impossible to adjust their block arguments
1287 // otherwise.
1288 auto branchOpInterface = dyn_cast<BranchOpInterface>(Val: operation);
1289 if (!branchOpInterface) {
1290 operation->emitOpError(message: "transformation does not support terminators with "
1291 "successors not implementing BranchOpInterface");
1292 return WalkResult::interrupt();
1293 }
1294 // Branch operations must have no side effects. Replacing them would not be
1295 // valid otherwise.
1296 if (!isMemoryEffectFree(op: branchOpInterface)) {
1297 branchOpInterface->emitOpError(
1298 message: "transformation does not support terminators with side effects");
1299 return WalkResult::interrupt();
1300 }
1301
1302 for (unsigned index : llvm::seq(Size: operation->getNumSuccessors())) {
1303 SuccessorOperands succOps = branchOpInterface.getSuccessorOperands(index);
1304
1305 // We cannot support operations with operation-produced successor operands
1306 // as it is currently not possible to pass them to any block arguments
1307 // other than the first. This breaks creating multiplexer blocks and would
1308 // likely need special handling elsewhere too.
1309 if (succOps.getProducedOperandCount() == 0)
1310 continue;
1311
1312 branchOpInterface->emitOpError(message: "transformation does not support "
1313 "operations with operation-produced "
1314 "successor operands");
1315 return WalkResult::interrupt();
1316 }
1317 return WalkResult::advance();
1318 });
1319 if (result.wasInterrupted())
1320 return failure();
1321
1322 // Verify all multi-successor terminators are convertible before touching IR.
1323 for (Block &block : region.getBlocks()) {
1324 if (block.getNumSuccessors() <= 1)
1325 continue;
1326 Operation *terminator = block.getTerminator();
1327 if (!interface.canConvertMultiSuccessorBranchOp(op: terminator)) {
1328 terminator->emitOpError(
1329 message: "cannot convert unknown control flow op to structured control flow");
1330 return failure();
1331 }
1332 }
1333 return success();
1334}
1335
1336FailureOr<bool> mlir::transformCFGToSCF(Region &region,
1337 CFGToSCFInterface &interface,
1338 DominanceInfo &dominanceInfo) {
1339 if (region.empty() || region.hasOneBlock())
1340 return false;
1341
1342 if (failed(Result: checkTransformationPreconditions(region, interface)))
1343 return failure();
1344
1345 DenseMap<Type, Value> typedUndefCache;
1346 auto getUndefValue = [&](Type type) {
1347 auto [iter, inserted] = typedUndefCache.try_emplace(Key: type);
1348 if (!inserted)
1349 return iter->second;
1350
1351 auto constantBuilder = OpBuilder::atBlockBegin(block: &region.front());
1352
1353 iter->second =
1354 interface.getUndefValue(loc: region.getLoc(), builder&: constantBuilder, type);
1355 return iter->second;
1356 };
1357
1358 // The transformation only creates all values in the range of 0 to
1359 // max(#numSuccessors). Therefore using a vector instead of a map.
1360 SmallVector<Value> switchValueCache;
1361 auto getSwitchValue = [&](unsigned value) {
1362 if (value < switchValueCache.size())
1363 if (switchValueCache[value])
1364 return switchValueCache[value];
1365
1366 auto constantBuilder = OpBuilder::atBlockBegin(block: &region.front());
1367
1368 switchValueCache.resize(
1369 N: std::max<size_t>(a: switchValueCache.size(), b: value + 1));
1370
1371 switchValueCache[value] =
1372 interface.getCFGSwitchValue(loc: region.getLoc(), builder&: constantBuilder, value);
1373 return switchValueCache[value];
1374 };
1375
1376 ReturnLikeExitCombiner exitCombiner = createSingleExitBlocksForReturnLike(
1377 region, getSwitchValue, getUndefValue, interface);
1378
1379 // Invalidate any dominance tree on the region as the exit combiner has
1380 // added new blocks and edges.
1381 dominanceInfo.invalidate(region: &region);
1382
1383 SmallVector<Block *> workList = {&region.front()};
1384 while (!workList.empty()) {
1385 Block *current = workList.pop_back_val();
1386
1387 // Turn all top-level cycles in the CFG to structured control flow first.
1388 // After this transformation, the remaining CFG ops form a DAG.
1389 FailureOr<SmallVector<Block *>> newRegions =
1390 transformCyclesToSCFLoops(regionEntry: current, getSwitchValue, getUndefValue,
1391 interface, dominanceInfo, exitCombiner);
1392 if (failed(Result: newRegions))
1393 return failure();
1394
1395 // Add the newly created subregions to the worklist. These are the
1396 // bodies of the loops.
1397 llvm::append_range(C&: workList, R&: *newRegions);
1398 // Invalidate the dominance tree as blocks have been moved, created and
1399 // added during the cycle to structured loop transformation.
1400 if (!newRegions->empty())
1401 dominanceInfo.invalidate(region: current->getParent());
1402
1403 newRegions = transformToStructuredCFBranches(
1404 regionEntry: current, getSwitchValue, getUndefValue, interface, dominanceInfo);
1405 if (failed(Result: newRegions))
1406 return failure();
1407 // Invalidating the dominance tree is generally not required by the
1408 // transformation above as the new region entries correspond to unaffected
1409 // subtrees in the dominator tree. Only its parent nodes have changed but
1410 // won't be visited again.
1411 llvm::append_range(C&: workList, R&: *newRegions);
1412 }
1413
1414 return true;
1415}
1416