17 #include "mlir/IR/Dominance.h"
19 using namespace circt;
22 struct EarlyCodeMotionPass
23 :
public llhd::EarlyCodeMotionBase<EarlyCodeMotionPass> {
24 void runOnOperation()
override;
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());
35 std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
36 std::back_inserter(res));
40 void EarlyCodeMotionPass::runOnOperation() {
41 llhd::ProcOp proc = getOperation();
43 mlir::DominanceInfo dom(proc);
45 DenseMap<Block *, unsigned> entryDistance;
46 SmallPtrSet<Block *, 32> workDone;
47 SmallPtrSet<Block *, 32> workPending;
49 Block &entryBlock = proc.getBody().front();
50 workPending.insert(&entryBlock);
51 entryDistance.insert(std::make_pair(&entryBlock, 0));
53 while (!workPending.empty()) {
54 Block *block = *workPending.begin();
55 workPending.erase(block);
56 workDone.insert(block);
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>()))
66 SmallVector<Block *, 8> validPlacements;
68 for (Block &b : proc.getBlocks())
69 validPlacements.push_back(&b);
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();
79 instBlock = operand.getDefiningOp()->getBlock();
82 for (Block &b : proc.getBlocks()) {
83 if (dom.dominates(instBlock, &b))
84 dominationSet.push_back(&b);
86 validPlacements =
intersection(dominationSet, validPlacements);
90 if (isa<llhd::PrbOp>(op)) {
91 SmallVector<Block *, 8> blocksInTR =
93 validPlacements =
intersection(validPlacements, blocksInTR);
96 if (validPlacements.empty())
101 unsigned minBBdist = -1;
102 Block *minBB =
nullptr;
103 for (Block *b : validPlacements) {
104 if (!entryDistance.count(b))
106 if (entryDistance[b] < minBBdist) {
107 minBBdist = entryDistance[b];
112 if (!minBB || minBB == op.getBlock())
115 auto prev = std::prev(iter);
116 op.moveBefore(minBB->getTerminator());
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));
133 std::unique_ptr<OperationPass<llhd::ProcOp>>
135 return std::make_unique<EarlyCodeMotionPass>();
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...
SmallVector< Block *, 8 > getBlocksInTR(int)