MLIR  19.0.0git
CFGToSCF.h
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 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.
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.
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.
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.
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 *>
113  Region &region) = 0;
114 
115  /// Helper function to create an unconditional branch using
116  /// `createCFGSwitchOp`.
118  Value dummyFlag, Block *destination,
119  ValueRange arguments) {
120  createCFGSwitchOp(loc, builder, dummyFlag, {}, {}, {}, destination,
121  arguments);
122  }
123 
124  /// Helper function to create a conditional branch using
125  /// `createCFGSwitchOp`.
127  Value condition, Block *trueDest,
128  ValueRange trueArgs, Block *falseDest,
129  ValueRange falseArgs) {
130  createCFGSwitchOp(loc, builder, condition, {0}, {falseDest}, {falseArgs},
131  trueDest, 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 &region, CFGToSCFInterface &interface,
154  DominanceInfo &dominanceInfo);
155 
156 } // namespace mlir
157 
158 #endif // MLIR_TRANSFORMS_CFGTOSCF_H
This class provides an abstraction over the different types of ranges over Blocks.
Definition: BlockSupport.h:106
Block represents an ordered list of Operations.
Definition: Block.h:30
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...
virtual ~CFGToSCFInterface()=default
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:63
This class helps build Operations.
Definition: Builders.h:209
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class provides an abstraction over the various different ranges of value types.
Definition: TypeRange.h:36
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:378
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Include the generated interface declarations.
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:1277
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26