17#include "mlir/IR/Dominance.h"
18#include "mlir/IR/Threading.h"
19#include "mlir/Interfaces/SideEffectInterfaces.h"
20#include "mlir/Pass/Pass.h"
21#include "mlir/Transforms/ControlFlowSinkUtils.h"
22#include "llvm/ADT/PostOrderIterator.h"
24#define DEBUG_TYPE "firrtl-layer-sink"
28#define GEN_PASS_DEF_LAYERSINK
29#include "circt/Dialect/FIRRTL/Passes.h.inc"
34using namespace firrtl;
48void walkBwd(
Block *block, T &&f) {
50 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
51 for (
auto ®ion : op.getRegions())
52 for (
auto &block : region.getBlocks())
63 return block->getParent()->isProperAncestor(other->getParent());
72 if (op->hasTrait<OpTrait::ConstantLike>())
76 if (isa<RefSendOp, RefResolveOp, RefCastOp, RefSubOp>(op))
91 DenseSet<InstanceGraphNode *> visited;
92 for (
auto *root : instanceGraph) {
93 for (
auto *node :
llvm::post_order_ext(root, visited)) {
94 auto *op = node->getModule().getOperation();
101 bool effectful(Operation *op)
const {
104 if (
auto name = dyn_cast<FNamableOp>(op))
105 if (!name.hasDroppableName())
107 if (op->getNumRegions() != 0)
109 if (
auto instance = dyn_cast<InstanceOp>(op))
110 return effectfulModules.contains(instance.getModuleNameAttr().getAttr());
111 if (isa<FConnectLike, WireOp, RegResetOp, RegOp, MemOp, NodeOp>(op))
113 return !(mlir::isMemoryEffectFree(op) ||
114 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
115 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
120 void update(FModuleOp moduleOp) {
121 moduleOp.getBodyBlock()->walk([&](Operation *op) {
123 markEffectful(moduleOp);
124 return WalkResult::interrupt();
126 return WalkResult::advance();
131 void update(FModuleLike moduleOp) {
136 return markEffectful(moduleOp);
138 for (
auto annos : moduleOp.getPortAnnotations())
139 if (!cast<ArrayAttr>(annos).
empty())
140 return markEffectful(moduleOp);
142 auto *op = moduleOp.getOperation();
144 if (
auto m = dyn_cast<FModuleOp>(op))
147 if (
auto m = dyn_cast<FMemModuleOp>(op))
151 return markEffectful(moduleOp);
154 void update(Operation *op) {
155 if (
auto moduleOp = dyn_cast<FModuleLike>(op))
160 void markEffectful(FModuleLike moduleOp) {
161 effectfulModules.insert(moduleOp.getModuleNameAttr());
164 DenseSet<StringAttr> effectfulModules;
175 constexpr Demand() : Demand(nullptr) {}
176 constexpr Demand(Block *block) : block(block) {}
178 constexpr Demand merge(Demand other)
const {
179 if (block == other.block)
180 return Demand(block);
181 if (other.block ==
nullptr)
182 return Demand(block);
183 if (block ==
nullptr)
184 return Demand(other.block);
188 b = b->getParentOp()->getBlock();
193 bool mergeIn(Demand other) {
195 auto next = merge(other);
200 constexpr bool operator==(Demand rhs)
const {
return block == rhs.block; }
201 constexpr bool operator!=(Demand rhs)
const {
return block != rhs.block; }
202 constexpr operator bool()
const {
return block; }
210 return op && (isa<LayerBlockOp>(op) || isa<FModuleOp>(op));
231static Demand
clamp(Operation *op, Demand demand) {
235 auto *upper = op->getBlock();
236 assert(upper &&
"this should not be called on a top-level operation.");
241 for (
auto *i = demand.block; i != upper; i = i->getParentOp()->getBlock())
243 demand = i->getParentOp()->getBlock();
231static Demand
clamp(Operation *op, Demand demand) {
…}
250 using WorkStack = std::vector<Operation *>;
252 DemandInfo(
const EffectInfo &, FModuleOp);
254 Demand getDemandFor(Operation *op)
const {
return table.lookup(op); }
260 void run(
const EffectInfo &, FModuleOp, WorkStack &);
264 void update(WorkStack &work, Operation *op, Demand demand) {
265 if (table[op].mergeIn(
clamp(op, demand)))
269 void update(WorkStack &work, Value value, Demand demand) {
270 if (
auto result = dyn_cast<OpResult>(value))
271 update(work, cast<OpResult>(value).getOwner(), demand);
274 void updateConnects(WorkStack &, Value, Demand);
275 void updateConnects(WorkStack &, Operation *, Demand);
277 llvm::DenseMap<Operation *, Demand> table;
281DemandInfo::DemandInfo(
const EffectInfo &effectInfo, FModuleOp moduleOp) {
283 Block *body = moduleOp.getBodyBlock();
284 ArrayRef<bool> dirs = moduleOp.getPortDirections();
285 for (
unsigned i = 0, e = moduleOp.getNumPorts(); i < e; ++i)
287 updateConnects(work, body->getArgument(i), moduleOp.getBodyBlock());
288 moduleOp.getBodyBlock()->walk([&](Operation *op) {
289 if (effectInfo.effectful(op))
290 update(work, op, op->getBlock());
292 run(effectInfo, moduleOp, work);
295void DemandInfo::run(
const EffectInfo &effectInfo, FModuleOp, WorkStack &work) {
296 while (!work.empty()) {
297 auto *op = work.back();
299 auto demand = getDemandFor(op);
300 for (
auto operand : op->getOperands())
301 update(work, operand, demand);
302 updateConnects(work, op, demand);
312void DemandInfo::updateConnects(WorkStack &work, Value value, Demand demand) {
313 struct StackElement {
315 Value::user_iterator it;
318 SmallVector<StackElement> stack;
319 stack.push_back({value, value.user_begin()});
320 while (!stack.empty()) {
321 auto &top = stack.back();
322 auto end = top.value.user_end();
328 auto *user = *(top.it++);
329 if (
auto connect = dyn_cast<FConnectLike>(user)) {
330 if (
connect.getDest() == top.value) {
331 update(work, connect, demand);
335 if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(user)) {
336 for (
auto result : user->getResults())
337 stack.push_back({result, result.user_begin()});
344void DemandInfo::updateConnects(WorkStack &work, Operation *op, Demand demand) {
345 if (isa<WireOp, RegResetOp, RegOp, MemOp, ObjectOp>(op)) {
346 for (
auto result : op->getResults())
347 updateConnects(work, result, demand);
348 }
else if (
auto inst = dyn_cast<InstanceOp>(op)) {
349 auto dirs = inst.getPortDirections();
350 for (
unsigned i = 0, e = inst->getNumResults(); i < e; ++i) {
352 updateConnects(work, inst.getResult(i), demand);
362class ModuleLayerSink {
364 static bool run(FModuleOp moduleOp,
const EffectInfo &effectInfo) {
365 return ModuleLayerSink(moduleOp, effectInfo)();
369 ModuleLayerSink(FModuleOp moduleOp,
const EffectInfo &effectInfo)
370 : moduleOp(moduleOp), effectInfo(effectInfo) {}
373 void moveLayersToBack(Operation *op);
374 void moveLayersToBack(Block *block);
376 void erase(Operation *op);
377 void sinkOpByCloning(Operation *op);
378 void sinkOpByMoving(Operation *op, Block *dest);
381 const EffectInfo &effectInfo;
382 bool changed =
false;
387void ModuleLayerSink::moveLayersToBack(Operation *op) {
388 for (
auto &r : op->getRegions())
389 for (auto &b : r.getBlocks())
390 moveLayersToBack(&b);
394void ModuleLayerSink::moveLayersToBack(Block *block) {
395 auto i = block->rbegin();
396 auto e = block->rend();
401 moveLayersToBack(op);
402 if (!isa<LayerBlockOp>(op))
415 moveLayersToBack(op);
416 if (isa<LayerBlockOp>(op)) {
426void ModuleLayerSink::erase(Operation *op) {
431void ModuleLayerSink::sinkOpByCloning(Operation *op) {
434 auto *src = op->getBlock();
435 DenseMap<Block *, Operation *> cache;
436 for (
unsigned i = 0, e = op->getNumResults(); i < e; ++i) {
437 for (
auto &use :
llvm::make_early_inc_range(op->getResult(i).getUses())) {
438 auto *dst = use.getOwner()->getBlock();
440 auto &clone = cache[dst];
442 clone = OpBuilder::atBlockBegin(dst).clone(*op);
443 use.set(clone->getResult(i));
450 if (isOpTriviallyDead(op))
454void ModuleLayerSink::sinkOpByMoving(Operation *op, Block *dst) {
455 if (dst != op->getBlock()) {
456 op->moveBefore(dst, dst->begin());
461bool ModuleLayerSink::operator()() {
462 moveLayersToBack(moduleOp.getBodyBlock());
463 DemandInfo demandInfo(effectInfo, moduleOp);
464 walkBwd(moduleOp.getBodyBlock(), [&](Operation *op) {
465 auto demand = demandInfo.getDemandFor(op);
469 return sinkOpByCloning(op);
470 sinkOpByMoving(op, demand.block);
482struct LayerSinkPass final
483 :
public circt::firrtl::impl::LayerSinkBase<LayerSinkPass> {
484 void runOnOperation()
override;
488void LayerSinkPass::runOnOperation() {
489 auto circuit = getOperation();
492 <<
"Circuit: '" << circuit.getName() <<
"'\n";);
493 auto &instanceGraph = getAnalysis<InstanceGraph>();
494 EffectInfo effectInfo(circuit, instanceGraph);
496 std::atomic<bool> changed(
false);
497 parallelForEach(&getContext(), circuit.getOps<FModuleOp>(),
498 [&](FModuleOp moduleOp) {
499 if (ModuleLayerSink::run(moduleOp, effectInfo))
504 markAllAnalysesPreserved();
506 markAnalysesPreserved<InstanceGraph>();
assert(baseType &&"element must be base type")
static bool isBarrier(Operation *op)
True if we are prevented from sinking operations into the regions of the op.
static Demand clamp(Operation *op, Demand demand)
Adjust the demand based on the location of the op being demanded.
static bool isAncestor(Block *block, Block *other)
static bool isValidDest(Operation *op)
True if this operation is a good site to sink operations.
static bool cloneable(Operation *op)
static InstancePath empty
This class provides a read-only projection over the MLIR attributes that represent a set of annotatio...
This graph tracks modules and where they are instantiated.
connect(destination, source)
static Direction get(bool isOutput)
Return an output direction if isOutput is true, otherwise return an input direction.
bool hasDontTouch(Value value)
Check whether a block argument ("port") or the operation defining a value has a DontTouch annotation,...
ArrayAttr getAnnotationsIfPresent(Operation *op)
static bool operator==(const ModulePort &a, const ModulePort &b)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
bool operator!=(uint64_t a, const FVInt &b)
llvm::raw_ostream & debugPassHeader(const mlir::Pass *pass, int width=80)
Write a boilerplate header for a pass to the debug stream.
int run(Type[Generator] generator=CppGenerator, cmdline_args=sys.argv)