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