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 | |
22 | namespace 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. |
28 | class CFGToSCFInterface { |
29 | public: |
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 ®ion) = 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. |
153 | FailureOr<bool> transformCFGToSCF(Region ®ion, CFGToSCFInterface &interface, |
154 | DominanceInfo &dominanceInfo); |
155 | |
156 | } // namespace mlir |
157 | |
158 | #endif // MLIR_TRANSFORMS_CFGTOSCF_H |
159 | |