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`. createSingleDestinationBranch(Location loc,OpBuilder & builder,Value dummyFlag,Block * destination,ValueRange arguments)117 void createSingleDestinationBranch(Location loc, OpBuilder &builder, 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`. createConditionalBranch(Location loc,OpBuilder & builder,Value condition,Block * trueDest,ValueRange trueArgs,Block * falseDest,ValueRange falseArgs)126 void createConditionalBranch(Location loc, OpBuilder &builder, 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 ®ion, CFGToSCFInterface &interface, 154 DominanceInfo &dominanceInfo); 155 156 } // namespace mlir 157 158 #endif // MLIR_TRANSFORMS_CFGTOSCF_H 159