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 header file defines a generic `transformCFGToSCF` function that can be
10// used to lift any dialect operations implementing control flow graph
11// operations to any dialect implementing structured control flow operations.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef MLIR_TRANSFORMS_CFGTOSCF_H
16#define MLIR_TRANSFORMS_CFGTOSCF_H
17
18#include "mlir/IR/Builders.h"
19#include "mlir/IR/Dominance.h"
20#include "mlir/IR/Operation.h"
21
22namespace mlir {
23
24/// Interface that should be implemented by any caller of `transformCFGToSCF`.
25/// The transformation requires the caller to 1) create switch-like control
26/// flow operations for intermediate transformations and 2) to create
27/// the desired structured control flow ops.
28class CFGToSCFInterface {
29public:
30 virtual ~CFGToSCFInterface() = default;
31
32 /// Creates a structured control flow operation branching to one of `regions`.
33 /// It replaces `controlFlowCondOp` and must have `resultTypes` as results.
34 /// `regions` contains the list of branch regions corresponding to each
35 /// successor of `controlFlowCondOp`. Their bodies must simply be taken and
36 /// left as is.
37 /// Returns failure if incapable of converting the control flow graph
38 /// operation.
39 virtual FailureOr<Operation *> createStructuredBranchRegionOp(
40 OpBuilder &builder, Operation *controlFlowCondOp, TypeRange resultTypes,
41 MutableArrayRef<Region> regions) = 0;
42
43 /// Creates a return-like terminator for a branch region of the op returned
44 /// by `createStructuredBranchRegionOp`. `branchRegionOp` is the operation
45 /// returned by `createStructuredBranchRegionOp`.
46 /// `replacedControlFlowOp` is the control flow op being replaced by the
47 /// terminator or nullptr if the terminator is not replacing any existing
48 /// control flow op. `results` are the values that should be returned by the
49 /// branch region.
50 virtual LogicalResult createStructuredBranchRegionTerminatorOp(
51 Location loc, OpBuilder &builder, Operation *branchRegionOp,
52 Operation *replacedControlFlowOp, ValueRange results) = 0;
53
54 /// Creates a structured control flow operation representing a do-while loop.
55 /// The do-while loop is expected to have the exact same result types as the
56 /// types of the iteration values.
57 /// `loopBody` is the body of the loop. The implementation of this
58 /// function must create a suitable terminator op at the end of the last block
59 /// in `loopBody` which continues the loop if `condition` is 1 and exits the
60 /// loop if 0. `loopValuesNextIter` are the values that have to be passed as
61 /// the iteration values for the next iteration if continuing, or the result
62 /// of the loop if exiting.
63 /// `condition` is guaranteed to be of the same type as values returned by
64 /// `getCFGSwitchValue` with either 0 or 1 as value.
65 ///
66 /// `loopValuesInit` are the values used to initialize the iteration
67 /// values of the loop.
68 /// Returns failure if incapable of creating a loop op.
69 virtual FailureOr<Operation *> createStructuredDoWhileLoopOp(
70 OpBuilder &builder, Operation *replacedOp, ValueRange loopValuesInit,
71 Value condition, ValueRange loopValuesNextIter, Region &&loopBody) = 0;
72
73 /// Creates a constant operation with a result representing `value` that is
74 /// suitable as flag for `createCFGSwitchOp`.
75 virtual Value getCFGSwitchValue(Location loc, OpBuilder &builder,
76 unsigned value) = 0;
77
78 /// Creates a switch CFG branch operation branching to one of
79 /// `caseDestinations` or `defaultDest`. This is used by the transformation
80 /// for intermediate transformations before lifting to structured control
81 /// flow. The switch op branches based on `flag` which is guaranteed to be of
82 /// the same type as values returned by `getCFGSwitchValue`. The insertion
83 /// block of the builder is guaranteed to have its predecessors already set
84 /// to create an equivalent CFG after this operation.
85 /// Note: `caseValues` and other related ranges may be empty to represent an
86 /// unconditional branch.
87 virtual void createCFGSwitchOp(Location loc, OpBuilder &builder, Value flag,
88 ArrayRef<unsigned> caseValues,
89 BlockRange caseDestinations,
90 ArrayRef<ValueRange> caseArguments,
91 Block *defaultDest,
92 ValueRange defaultArgs) = 0;
93
94 /// Creates a constant operation returning an undefined instance of `type`.
95 /// This is required by the transformation as the lifting process might create
96 /// control-flow paths where an SSA-value is undefined.
97 virtual Value getUndefValue(Location loc, OpBuilder &builder, Type type) = 0;
98
99 /// Creates a return-like terminator indicating unreachable.
100 /// This is required when the transformation encounters a statically known
101 /// infinite loop. Since structured control flow ops are not terminators,
102 /// after lifting an infinite loop, a terminator has to be placed after to
103 /// possibly satisfy the terminator requirement of the region originally
104 /// passed to `transformCFGToSCF`.
105 ///
106 /// `region` is guaranteed to be the region originally passed to
107 /// `transformCFGToSCF` and the op is guaranteed to always be an op in a block
108 /// directly nested under `region` after the transformation.
109 ///
110 /// Returns failure if incapable of creating an unreachable terminator.
111 virtual FailureOr<Operation *>
112 createUnreachableTerminator(Location loc, OpBuilder &builder,
113 Region &region) = 0;
114
115 /// Helper function to create an unconditional branch using
116 /// `createCFGSwitchOp`.
117 void createSingleDestinationBranch(Location loc, OpBuilder &builder,
118 Value dummyFlag, Block *destination,
119 ValueRange arguments) {
120 createCFGSwitchOp(loc, builder, flag: dummyFlag, caseValues: {}, caseDestinations: {}, caseArguments: {}, defaultDest: destination,
121 defaultArgs: arguments);
122 }
123
124 /// Helper function to create a conditional branch using
125 /// `createCFGSwitchOp`.
126 void createConditionalBranch(Location loc, OpBuilder &builder,
127 Value condition, Block *trueDest,
128 ValueRange trueArgs, Block *falseDest,
129 ValueRange falseArgs) {
130 createCFGSwitchOp(loc, builder, flag: condition, caseValues: {0}, caseDestinations: {falseDest}, caseArguments: {falseArgs},
131 defaultDest: trueDest, defaultArgs: trueArgs);
132 }
133};
134
135/// Transformation lifting any dialect implementing control flow graph
136/// operations to a dialect implementing structured control flow operations.
137/// `region` is the region that should be transformed.
138/// The implementation of `interface` is responsible for the conversion of the
139/// control flow operations to the structured control flow operations.
140///
141/// If the region contains only a single kind of return-like operation, all
142/// control flow graph operations will be converted successfully.
143/// Otherwise a single control flow graph operation branching to one block
144/// per return-like operation kind remains.
145///
146/// The transformation currently requires that all control flow graph operations
147/// have no side effects, implement the BranchOpInterface and does not have any
148/// operation produced successor operands.
149/// Returns failure if any of the preconditions are violated or if any of the
150/// methods of `interface` failed. The IR is left in an unspecified state.
151///
152/// Otherwise, returns true or false if any changes to the IR have been made.
153FailureOr<bool> transformCFGToSCF(Region &region, CFGToSCFInterface &interface,
154 DominanceInfo &dominanceInfo);
155
156} // namespace mlir
157
158#endif // MLIR_TRANSFORMS_CFGTOSCF_H
159

source code of mlir/include/mlir/Transforms/CFGToSCF.h