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