1 //===- LegalizeForExport.cpp - Prepare for translation to LLVM IR ---------===//
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 "mlir/Dialect/LLVMIR/Transforms/LegalizeForExport.h"
10 #include "PassDetail.h"
11 #include "mlir/Dialect/LLVMIR/LLVMDialect.h"
12 #include "mlir/IR/Block.h"
13 #include "mlir/IR/Builders.h"
14 #include "mlir/IR/BuiltinOps.h"
15 
16 using namespace mlir;
17 
18 /// If the given block has the same successor with different arguments,
19 /// introduce dummy successor blocks so that all successors of the given block
20 /// are different.
21 static void ensureDistinctSuccessors(Block &bb) {
22   // Early exit if the block cannot have successors.
23   if (bb.empty() || !bb.back().mightHaveTrait<OpTrait::IsTerminator>())
24     return;
25 
26   auto *terminator = bb.getTerminator();
27 
28   // Find repeated successors with arguments.
29   llvm::SmallDenseMap<Block *, SmallVector<int, 4>> successorPositions;
30   for (int i = 0, e = terminator->getNumSuccessors(); i < e; ++i) {
31     Block *successor = terminator->getSuccessor(i);
32     // Blocks with no arguments are safe even if they appear multiple times
33     // because they don't need PHI nodes.
34     if (successor->getNumArguments() == 0)
35       continue;
36     successorPositions[successor].push_back(i);
37   }
38 
39   // If a successor appears for the second or more time in the terminator,
40   // create a new dummy block that unconditionally branches to the original
41   // destination, and retarget the terminator to branch to this new block.
42   // There is no need to pass arguments to the dummy block because it will be
43   // dominated by the original block and can therefore use any values defined in
44   // the original block.
45   OpBuilder builder(terminator->getContext());
46   for (const auto &successor : successorPositions) {
47     // Start from the second occurrence of a block in the successor list.
48     for (int position : llvm::drop_begin(successor.second, 1)) {
49       Block *dummyBlock = builder.createBlock(bb.getParent());
50       terminator->setSuccessor(dummyBlock, position);
51       for (BlockArgument arg : successor.first->getArguments())
52         dummyBlock->addArgument(arg.getType(), arg.getLoc());
53       builder.create<LLVM::BrOp>(terminator->getLoc(),
54                                  dummyBlock->getArguments(), successor.first);
55     }
56   }
57 }
58 
59 void mlir::LLVM::ensureDistinctSuccessors(Operation *op) {
60   op->walk([](Operation *nested) {
61     for (Region &region : llvm::make_early_inc_range(nested->getRegions())) {
62       for (Block &block : llvm::make_early_inc_range(region)) {
63         ::ensureDistinctSuccessors(block);
64       }
65     }
66   });
67 }
68 
69 namespace {
70 struct LegalizeForExportPass
71     : public LLVMLegalizeForExportBase<LegalizeForExportPass> {
72   void runOnOperation() override {
73     LLVM::ensureDistinctSuccessors(getOperation());
74   }
75 };
76 } // namespace
77 
78 std::unique_ptr<Pass> LLVM::createLegalizeForExportPass() {
79   return std::make_unique<LegalizeForExportPass>();
80 }
81