CIRCT  19.0.0git
EarlyCodeMotionPass.cpp
Go to the documentation of this file.
1 //===- EarlyCodeMotionPass.cpp - Implement Early Code Motion Pass ---------===//
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 // Implement pass to move allowed instructions as far up in the CFG as possible.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "TemporalRegions.h"
16 #include "circt/Support/LLVM.h"
17 #include "mlir/IR/Dominance.h"
18 #include "mlir/Pass/Pass.h"
19 
20 namespace circt {
21 namespace llhd {
22 #define GEN_PASS_DEF_EARLYCODEMOTION
23 #include "circt/Dialect/LLHD/Transforms/Passes.h.inc"
24 } // namespace llhd
25 } // namespace circt
26 
27 using namespace circt;
28 namespace {
29 struct EarlyCodeMotionPass
30  : public circt::llhd::impl::EarlyCodeMotionBase<EarlyCodeMotionPass> {
31  void runOnOperation() override;
32 };
33 } // namespace
34 
35 /// Calculate intersection of two vectors, returns a new vector
36 static SmallVector<Block *, 8> intersection(SmallVectorImpl<Block *> &v1,
37  SmallVectorImpl<Block *> &v2) {
38  SmallVector<Block *, 8> res;
39  std::sort(v1.begin(), v1.end());
40  std::sort(v2.begin(), v2.end());
41 
42  std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
43  std::back_inserter(res));
44  return res;
45 }
46 
47 void EarlyCodeMotionPass::runOnOperation() {
48  llhd::ProcOp proc = getOperation();
50  mlir::DominanceInfo dom(proc);
51 
52  DenseMap<Block *, unsigned> entryDistance;
53  SmallPtrSet<Block *, 32> workDone;
54  SmallPtrSet<Block *, 32> workPending;
55 
56  Block &entryBlock = proc.getBody().front();
57  workPending.insert(&entryBlock);
58  entryDistance.insert(std::make_pair(&entryBlock, 0));
59 
60  while (!workPending.empty()) {
61  Block *block = *workPending.begin();
62  workPending.erase(block);
63  workDone.insert(block);
64 
65  for (auto iter = block->getOperations().begin();
66  iter != block->getOperations().end(); ++iter) {
67  Operation &op = *iter;
68  if (!isa<llhd::PrbOp>(op) && !isa<llhd::SigOp>(op) &&
69  (!mlir::isMemoryEffectFree(&op) ||
70  op.hasTrait<OpTrait::IsTerminator>()))
71  continue;
72 
73  SmallVector<Block *, 8> validPlacements;
74  // Initialize validPlacements to all blocks in the process
75  for (Block &b : proc.getBlocks())
76  validPlacements.push_back(&b);
77 
78  // Delete all blocks in validPlacements that are not common to all
79  // operands
80  for (Value operand : op.getOperands()) {
81  SmallVector<Block *, 8> dominationSet;
82  Block *instBlock = nullptr;
83  if (BlockArgument arg = dyn_cast<BlockArgument>(operand)) {
84  instBlock = arg.getParentBlock();
85  } else {
86  instBlock = operand.getDefiningOp()->getBlock();
87  }
88 
89  for (Block &b : proc.getBlocks()) {
90  if (dom.dominates(instBlock, &b))
91  dominationSet.push_back(&b);
92  }
93  validPlacements = intersection(dominationSet, validPlacements);
94  }
95 
96  // The probe instruction has to stay in the same temporal region
97  if (isa<llhd::PrbOp>(op)) {
98  SmallVector<Block *, 8> blocksInTR =
99  trAnalysis.getBlocksInTR(trAnalysis.getBlockTR(block));
100  validPlacements = intersection(validPlacements, blocksInTR);
101  }
102 
103  if (validPlacements.empty())
104  continue;
105 
106  // Move the instruction to the block which is the closest to the entry
107  // block (and valid)
108  unsigned minBBdist = -1;
109  Block *minBB = nullptr;
110  for (Block *b : validPlacements) {
111  if (!entryDistance.count(b))
112  continue;
113  if (entryDistance[b] < minBBdist) {
114  minBBdist = entryDistance[b];
115  minBB = b;
116  }
117  }
118 
119  if (!minBB || minBB == op.getBlock())
120  continue;
121 
122  auto prev = std::prev(iter);
123  op.moveBefore(minBB->getTerminator());
124  iter = prev;
125  }
126 
127  // Add successors of this block
128  for (Block *succ : block->getSuccessors()) {
129  if (!workDone.count(succ)) {
130  workPending.insert(succ);
131  assert(entryDistance.count(block) &&
132  "ECM: block has to be present in entryDistance map");
133  unsigned nextDist = entryDistance[block] + 1;
134  entryDistance.insert(std::make_pair(succ, nextDist));
135  }
136  }
137  }
138 }
139 
140 std::unique_ptr<OperationPass<llhd::ProcOp>>
142  return std::make_unique<EarlyCodeMotionPass>();
143 }
assert(baseType &&"element must be base type")
static SmallVector< Block *, 8 > intersection(SmallVectorImpl< Block * > &v1, SmallVectorImpl< Block * > &v2)
Calculate intersection of two vectors, returns a new vector.
std::unique_ptr< OperationPass< ProcOp > > createEarlyCodeMotionPass()
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
SmallVector< Block *, 8 > getBlocksInTR(int)