CIRCT  19.0.0git
InsertMergeBlocks.cpp
Go to the documentation of this file.
1 //===- InsertMergeBlocks.cpp - Insert Merge Blocks --------------*- 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 #include "PassDetail.h"
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"
20 
21 using namespace mlir;
22 using namespace circt;
23 
24 /// Replaces the branching to oldDest of with an equivalent operation that
25 /// instead branches to newDest.
26 static LogicalResult changeBranchTarget(Block *block, Block *oldDest,
27  Block *newDest,
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());
35  return success();
36  })
37  .Case<cf::CondBranchOp>([&](auto condBr) {
38  auto cond = condBr.getCondition();
39 
40  Block *trueDest = condBr.getTrueDest();
41  Block *falseDest = condBr.getFalseDest();
42 
43  // Change to the correct destination.
44  if (trueDest == oldDest)
45  trueDest = newDest;
46 
47  if (falseDest == oldDest)
48  falseDest = newDest;
49 
50  rewriter.replaceOpWithNewOp<cf::CondBranchOp>(
51  condBr, cond, trueDest, condBr.getTrueOperands(), falseDest,
52  condBr.getFalseOperands());
53  return success();
54  })
55  .Default([&](Operation *op) {
56  return op->emitError("Unexpected terminator that cannot be handled.");
57  });
58 }
59 
60 /// Creates a new intermediate block that b1 and b2 branch to. The new block
61 /// branches to their common successor oldSucc.
62 static FailureOr<Block *> buildMergeBlock(Block *b1, Block *b2, Block *oldSucc,
63  ConversionPatternRewriter &rewriter) {
64  auto blockArgTypes = oldSucc->getArgumentTypes();
65  SmallVector<Location> argLocs(blockArgTypes.size(), rewriter.getUnknownLoc());
66 
67  Block *res = rewriter.createBlock(oldSucc, blockArgTypes, argLocs);
68  rewriter.create<cf::BranchOp>(rewriter.getUnknownLoc(), oldSucc,
69  res->getArguments());
70 
71  if (failed(changeBranchTarget(b1, oldSucc, res, rewriter)))
72  return failure();
73  if (failed(changeBranchTarget(b2, oldSucc, res, rewriter)))
74  return failure();
75 
76  return res;
77 }
78 
79 namespace {
80 /// A dual CFG that contracts cycles into single logical blocks.
81 struct DualGraph {
82  DualGraph(Region &r, CFGLoopInfo &loopInfo);
83 
84  size_t getNumPredecessors(Block *b) { return predCnts.lookup(b); }
85  void getPredecessors(Block *b, SmallVectorImpl<Block *> &res);
86 
87  size_t getNumSuccessors(Block *b) { return succMap.lookup(b).size(); }
88  ArrayRef<Block *> getSuccessors(Block *b) {
89  return succMap.find(b)->getSecond();
90  }
91 
92  // If the block is part of a contracted block, the header of the contracted
93  // block is returned. Otherwise, the block itself is returned.
94  Block *lookupDualBlock(Block *b);
95  DenseMap<Block *, size_t> getPredCountMapCopy() { return predCnts; }
96 
97 private:
98  CFGLoopInfo &loopInfo;
99 
100  DenseMap<Block *, SmallVector<Block *>> succMap;
101  DenseMap<Block *, size_t> predCnts;
102 };
103 } // namespace
104 
105 DualGraph::DualGraph(Region &r, CFGLoopInfo &loopInfo)
106  : loopInfo(loopInfo), succMap(), predCnts() {
107  for (Block &b : r) {
108  CFGLoop *loop = loopInfo.getLoopFor(&b);
109 
110  if (loop && loop->getHeader() != &b)
111  continue;
112 
113  // Create and get a new succ map entry for the current block.
114  SmallVector<Block *> &succs =
115  succMap.try_emplace(&b, SmallVector<Block *>()).first->getSecond();
116 
117  // NOTE: This assumes that there is only one exiting node, i.e., not
118  // two blocks from the same loop can be predecessors of one block.
119  unsigned predCnt = 0;
120  for (auto *pred : b.getPredecessors())
121  if (!loop || !loop->contains(pred))
122  predCnt++;
123 
124  if (loop && loop->getHeader() == &b)
125  loop->getExitBlocks(succs);
126  else
127  llvm::copy(b.getSuccessors(), std::back_inserter(succs));
128 
129  predCnts.try_emplace(&b, predCnt);
130  }
131 }
132 
133 Block *DualGraph::lookupDualBlock(Block *b) {
134  CFGLoop *loop = loopInfo.getLoopFor(b);
135  if (!loop)
136  return b;
137 
138  return loop->getHeader();
139 }
140 
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");
145 
146  for (auto *pred : b->getPredecessors()) {
147  if (loop && loop->contains(pred))
148  continue;
149 
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());
154  continue;
155  }
156  res.push_back(pred);
157  }
158 }
159 
160 namespace {
161 using BlockToBlockMap = DenseMap<Block *, Block *>;
162 /// A helper class to store the split block information gathered during analysis
163 /// of the CFG.
164 struct SplitInfo {
165  /// Points to the last split block that dominates the block.
166  BlockToBlockMap in;
167  /// Either points to the last split block or to itself, if the block itself is
168  /// a split block.
169  BlockToBlockMap out;
170 };
171 } // namespace
172 
173 /// Builds a binary merge block tree for the predecessors of currBlock.
174 static LogicalResult buildMergeBlocks(Block *currBlock, SplitInfo &splitInfo,
175  Block *predDom,
176  ConversionPatternRewriter &rewriter,
177  DualGraph &graph) {
178  SmallVector<Block *> preds;
179  llvm::copy(currBlock->getPredecessors(), std::back_inserter(preds));
180 
181  // Map from split blocks to blocks that descend from it.
182  DenseMap<Block *, Block *> predsToConsider;
183 
184  while (!preds.empty()) {
185  Block *pred = preds.pop_back_val();
186  Block *splitBlock = splitInfo.out.lookup(graph.lookupDualBlock(pred));
187  if (splitBlock == predDom)
188  // Needs no additional merge block, as this directly descends from the
189  // correct split block.
190  continue;
191 
192  if (predsToConsider.count(splitBlock) == 0) {
193  // No other block with the same split block was found yet, so just store
194  // it and wait for a match.
195  predsToConsider.try_emplace(splitBlock, pred);
196  continue;
197  }
198 
199  // Found a pair, so insert a new merge block for them.
200  Block *other = predsToConsider.lookup(splitBlock);
201  predsToConsider.erase(splitBlock);
202 
204  buildMergeBlock(pred, other, currBlock, rewriter);
205  if (failed(mergeBlock))
206  return failure();
207 
208  // Update info for the newly created block.
209  Block *splitIn = splitInfo.in.lookup(splitBlock);
210  splitInfo.in.try_emplace(*mergeBlock, splitIn);
211  // By construction, this block has only one successor, therefore, out == in.
212  splitInfo.out.try_emplace(*mergeBlock, splitIn);
213 
214  preds.push_back(*mergeBlock);
215  }
216  if (!predsToConsider.empty())
217  return currBlock->getParentOp()->emitError(
218  "irregular control flow is not yet supported");
219  return success();
220 }
221 
222 /// Checks preconditions of this transformation.
223 static LogicalResult preconditionCheck(Region &r, CFGLoopInfo &loopInfo) {
224  for (auto &info : loopInfo.getTopLevelLoops())
225  // Does only return a block if it is the only exit block.
226  if (!info->getExitBlock())
227  return r.getParentOp()->emitError(
228  "multiple exit blocks are not yet supported");
229 
230  return success();
231 }
232 
233 /// Insert additional blocks that serve as counterparts to the blocks that
234 /// diverged the control flow.
235 /// The resulting merge block tree is guaranteed to be a binary tree.
236 ///
237 /// This transformation does not affect any blocks that are part of a loop as it
238 /// treats a loop as one logical block.
239 /// Irregular control flow is not supported and results in a failed
240 /// transformation.
241 LogicalResult circt::insertMergeBlocks(Region &r,
242  ConversionPatternRewriter &rewriter) {
243  Block *entry = &r.front();
244  DominanceInfo domInfo(r.getParentOp());
245 
246  CFGLoopInfo loopInfo(domInfo.getDomTree(&r));
247  if (failed(preconditionCheck(r, loopInfo)))
248  return failure();
249 
250  // Traversing the graph in topological order can be simply done with a stack.
251  SmallVector<Block *> stack;
252  stack.push_back(entry);
253 
254  // Holds the graph that contains the relevant blocks. It for example contracts
255  // loops into one block to preserve a DAG structure.
256  DualGraph graph(r, loopInfo);
257 
258  // Counts the amount of predecessors remaining.
259  auto predsToVisit = graph.getPredCountMapCopy();
260 
261  SplitInfo splitInfo;
262 
263  while (!stack.empty()) {
264  Block *currBlock = stack.pop_back_val();
265 
266  Block *in = nullptr;
267  Block *out = nullptr;
268 
269  bool isMergeBlock = graph.getNumPredecessors(currBlock) > 1;
270  bool isSplitBlock = graph.getNumSuccessors(currBlock) > 1;
271 
272  SmallVector<Block *> preds;
273  graph.getPredecessors(currBlock, preds);
274 
275  if (isMergeBlock) {
276  Block *predDom = currBlock;
277  for (auto *pred : preds) {
278  predDom = domInfo.findNearestCommonDominator(predDom, pred);
279  }
280 
281  if (failed(
282  buildMergeBlocks(currBlock, splitInfo, predDom, rewriter, graph)))
283  return failure();
284 
285  // The sub-CFG created by the predDom (split block) and the current merge
286  // block can logically be treated like a single block, thus their "in"s
287  // are the same.
288  in = splitInfo.in.lookup(predDom);
289  } else if (!preds.empty()) {
290  Block *pred = preds.front();
291 
292  in = splitInfo.out.lookup(pred);
293  }
294 
295  if (isSplitBlock)
296  out = currBlock;
297  else
298  out = in;
299 
300  splitInfo.in.try_emplace(currBlock, in);
301  splitInfo.out.try_emplace(currBlock, out);
302 
303  for (auto *succ : graph.getSuccessors(currBlock)) {
304  auto it = predsToVisit.find(succ);
305  unsigned predsRemaining = --(it->getSecond());
306  // Pushing the block on the stack once all it's successors were visited
307  // ensures a topological traversal.
308  if (predsRemaining == 0)
309  stack.push_back(succ);
310  }
311  }
312 
313  return success();
314 }
315 
316 namespace {
317 
318 using PtrSet = SmallPtrSet<Operation *, 4>;
319 
320 struct FuncOpPattern : public OpConversionPattern<func::FuncOp> {
321 
322  FuncOpPattern(PtrSet &rewrittenFuncs, MLIRContext *ctx)
323  : OpConversionPattern(ctx), rewrittenFuncs(rewrittenFuncs) {}
324 
325  LogicalResult
326  matchAndRewrite(func::FuncOp op, OpAdaptor adaptor,
327  ConversionPatternRewriter &rewriter) const override {
328  rewriter.startOpModification(op);
329 
330  if (!op.isExternal())
331  if (failed(insertMergeBlocks(op.getRegion(), rewriter)))
332  return failure();
333 
334  rewriter.finalizeOpModification(op);
335  rewrittenFuncs.insert(op);
336 
337  return success();
338  }
339 
340 private:
341  PtrSet &rewrittenFuncs;
342 };
343 
344 struct InsertMergeBlocksPass
345  : public InsertMergeBlocksBase<InsertMergeBlocksPass> {
346 public:
347  void runOnOperation() override {
348  auto *ctx = &getContext();
349  RewritePatternSet patterns(ctx);
350  // Remembers traversed functions to only apply the conversion once.
351  PtrSet rewrittenFuncs;
352  patterns.add<FuncOpPattern>(rewrittenFuncs, ctx);
353 
354  ConversionTarget target(*ctx);
355  target.addDynamicallyLegalOp<func::FuncOp>(
356  [&](func::FuncOp func) { return rewrittenFuncs.contains(func); });
357  target.addLegalDialect<cf::ControlFlowDialect>();
358 
359  if (applyPartialConversion(getOperation(), target, std::move(patterns))
360  .failed())
361  signalPassFailure();
362  }
363 };
364 
365 } // namespace
366 
367 namespace circt {
368 std::unique_ptr<mlir::Pass> createInsertMergeBlocksPass() {
369  return std::make_unique<InsertMergeBlocksPass>();
370 }
371 } // namespace circt
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.
Definition: ExpandWhens.cpp:28
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...
Definition: DebugAnalysis.h:21
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.