11 #include "mlir/Analysis/CFGLoopInfo.h"
12 #include "mlir/Conversion/LLVMCommon/ConversionTarget.h"
13 #include "mlir/Conversion/LLVMCommon/Pattern.h"
14 #include "mlir/Dialect/ControlFlow/IR/ControlFlow.h"
15 #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
16 #include "mlir/Dialect/Func/IR/FuncOps.h"
17 #include "mlir/IR/Dominance.h"
18 #include "mlir/Transforms/DialectConversion.h"
19 #include "llvm/ADT/TypeSwitch.h"
22 using namespace circt;
28 ConversionPatternRewriter &rewriter) {
29 rewriter.setInsertionPointToEnd(block);
30 auto term = block->getTerminator();
31 return llvm::TypeSwitch<Operation *, LogicalResult>(term)
32 .Case<cf::BranchOp>([&](
auto branchOp) {
33 rewriter.replaceOpWithNewOp<cf::BranchOp>(branchOp, newDest,
34 branchOp->getOperands());
37 .Case<cf::CondBranchOp>([&](
auto condBr) {
38 auto cond = condBr.getCondition();
40 Block *trueDest = condBr.getTrueDest();
41 Block *falseDest = condBr.getFalseDest();
44 if (trueDest == oldDest)
47 if (falseDest == oldDest)
50 rewriter.replaceOpWithNewOp<cf::CondBranchOp>(
51 condBr, cond, trueDest, condBr.getTrueOperands(), falseDest,
52 condBr.getFalseOperands());
55 .Default([&](Operation *op) {
56 return op->emitError(
"Unexpected terminator that cannot be handled.");
63 ConversionPatternRewriter &rewriter) {
64 auto blockArgTypes = oldSucc->getArgumentTypes();
65 SmallVector<Location> argLocs(blockArgTypes.size(), rewriter.getUnknownLoc());
67 Block *res = rewriter.createBlock(oldSucc, blockArgTypes, argLocs);
68 rewriter.create<cf::BranchOp>(rewriter.getUnknownLoc(), oldSucc,
82 DualGraph(Region &r, CFGLoopInfo &loopInfo);
84 size_t getNumPredecessors(Block *b) {
return predCnts.lookup(b); }
85 void getPredecessors(Block *b, SmallVectorImpl<Block *> &res);
87 size_t getNumSuccessors(Block *b) {
return succMap.lookup(b).size(); }
88 ArrayRef<Block *> getSuccessors(Block *b) {
89 return succMap.find(b)->getSecond();
94 Block *lookupDualBlock(Block *b);
95 DenseMap<Block *, size_t> getPredCountMapCopy() {
return predCnts; }
98 CFGLoopInfo &loopInfo;
100 DenseMap<Block *, SmallVector<Block *>> succMap;
101 DenseMap<Block *, size_t> predCnts;
105 DualGraph::DualGraph(Region &r, CFGLoopInfo &loopInfo)
106 : loopInfo(loopInfo), succMap(), predCnts() {
108 CFGLoop *loop = loopInfo.getLoopFor(&b);
110 if (loop && loop->getHeader() != &b)
114 SmallVector<Block *> &succs =
115 succMap.try_emplace(&b, SmallVector<Block *>()).first->getSecond();
119 unsigned predCnt = 0;
120 for (
auto *pred : b.getPredecessors())
121 if (!loop || !loop->contains(pred))
124 if (loop && loop->getHeader() == &b)
125 loop->getExitBlocks(succs);
127 llvm::copy(b.getSuccessors(), std::back_inserter(succs));
129 predCnts.try_emplace(&b, predCnt);
133 Block *DualGraph::lookupDualBlock(Block *b) {
134 CFGLoop *loop = loopInfo.getLoopFor(b);
138 return loop->getHeader();
141 void DualGraph::getPredecessors(Block *b, SmallVectorImpl<Block *> &res) {
142 CFGLoop *loop = loopInfo.getLoopFor(b);
143 assert((!loop || loop->getHeader() == b) &&
144 "can only get predecessors of blocks in the graph");
146 for (
auto *pred : b->getPredecessors()) {
147 if (loop && loop->contains(pred))
150 if (CFGLoop *predLoop = loopInfo.getLoopFor(pred)) {
151 assert(predLoop->getExitBlock() &&
152 "multiple exit blocks are not yet supported");
153 res.push_back(predLoop->getHeader());
161 using BlockToBlockMap = DenseMap<Block *, Block *>;
176 ConversionPatternRewriter &rewriter,
178 SmallVector<Block *> preds;
179 llvm::copy(currBlock->getPredecessors(), std::back_inserter(preds));
182 DenseMap<Block *, Block *> predsToConsider;
184 while (!preds.empty()) {
185 Block *pred = preds.pop_back_val();
186 Block *splitBlock = splitInfo.out.lookup(graph.lookupDualBlock(pred));
187 if (splitBlock == predDom)
192 if (predsToConsider.count(splitBlock) == 0) {
195 predsToConsider.try_emplace(splitBlock, pred);
200 Block *other = predsToConsider.lookup(splitBlock);
201 predsToConsider.erase(splitBlock);
209 Block *splitIn = splitInfo.in.lookup(splitBlock);
210 splitInfo.in.try_emplace(*
mergeBlock, splitIn);
212 splitInfo.out.try_emplace(*
mergeBlock, splitIn);
216 if (!predsToConsider.empty())
217 return currBlock->getParentOp()->emitError(
218 "irregular control flow is not yet supported");
224 for (
auto &info : loopInfo.getTopLevelLoops())
226 if (!info->getExitBlock())
227 return r.getParentOp()->emitError(
228 "multiple exit blocks are not yet supported");
242 ConversionPatternRewriter &rewriter) {
243 Block *entry = &r.front();
244 DominanceInfo domInfo(r.getParentOp());
246 CFGLoopInfo loopInfo(domInfo.getDomTree(&r));
251 SmallVector<Block *> stack;
252 stack.push_back(entry);
256 DualGraph graph(r, loopInfo);
259 auto predsToVisit = graph.getPredCountMapCopy();
263 while (!stack.empty()) {
264 Block *currBlock = stack.pop_back_val();
267 Block *out =
nullptr;
269 bool isMergeBlock = graph.getNumPredecessors(currBlock) > 1;
270 bool isSplitBlock = graph.getNumSuccessors(currBlock) > 1;
272 SmallVector<Block *> preds;
273 graph.getPredecessors(currBlock, preds);
276 Block *predDom = currBlock;
277 for (
auto *pred : preds) {
278 predDom = domInfo.findNearestCommonDominator(predDom, pred);
288 in = splitInfo.in.lookup(predDom);
289 }
else if (!preds.empty()) {
290 Block *pred = preds.front();
292 in = splitInfo.out.lookup(pred);
300 splitInfo.in.try_emplace(currBlock, in);
301 splitInfo.out.try_emplace(currBlock, out);
303 for (
auto *succ : graph.getSuccessors(currBlock)) {
304 auto it = predsToVisit.find(succ);
305 unsigned predsRemaining = --(it->getSecond());
308 if (predsRemaining == 0)
309 stack.push_back(succ);
318 using PtrSet = SmallPtrSet<Operation *, 4>;
322 FuncOpPattern(PtrSet &rewrittenFuncs, MLIRContext *ctx)
326 matchAndRewrite(func::FuncOp op, OpAdaptor adaptor,
327 ConversionPatternRewriter &rewriter)
const override {
328 rewriter.startRootUpdate(op);
330 if (!op.isExternal())
334 rewriter.finalizeRootUpdate(op);
335 rewrittenFuncs.insert(op);
341 PtrSet &rewrittenFuncs;
344 struct InsertMergeBlocksPass
345 :
public InsertMergeBlocksBase<InsertMergeBlocksPass> {
347 void runOnOperation()
override {
348 auto *ctx = &getContext();
351 PtrSet rewrittenFuncs;
352 patterns.add<FuncOpPattern>(rewrittenFuncs, ctx);
354 ConversionTarget target(*ctx);
355 target.addDynamicallyLegalOp<func::FuncOp>(
356 [&](func::FuncOp func) {
return rewrittenFuncs.contains(func); });
357 target.addLegalDialect<cf::ControlFlowDialect>();
359 if (applyPartialConversion(getOperation(), target, std::move(
patterns))
369 return std::make_unique<InsertMergeBlocksPass>();
assert(baseType &&"element must be base type")
static void mergeBlock(Block &destination, Block::iterator insertPoint, Block &source)
Move all operations from a source block in to a destination block.
static LogicalResult changeBranchTarget(Block *block, Block *oldDest, Block *newDest, ConversionPatternRewriter &rewriter)
Replaces the branching to oldDest of with an equivalent operation that instead branches to newDest.
static LogicalResult preconditionCheck(Region &r, CFGLoopInfo &loopInfo)
Checks preconditions of this transformation.
static LogicalResult buildMergeBlocks(Block *currBlock, SplitInfo &splitInfo, Block *predDom, ConversionPatternRewriter &rewriter, DualGraph &graph)
Builds a binary merge block tree for the predecessors of currBlock.
static FailureOr< Block * > buildMergeBlock(Block *b1, Block *b2, Block *oldSucc, ConversionPatternRewriter &rewriter)
Creates a new intermediate block that b1 and b2 branch to.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
std::unique_ptr< mlir::Pass > createInsertMergeBlocksPass()
mlir::LogicalResult insertMergeBlocks(mlir::Region &r, mlir::ConversionPatternRewriter &rewriter)
Insert additional blocks that serve as counterparts to the blocks that diverged the control flow.