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_ADVANCEDLAYERSINK
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());
71 return op->hasTrait<OpTrait::ConstantLike>();
83 DenseSet<InstanceGraphNode *> visited;
84 for (
auto *root : instanceGraph) {
85 for (
auto *node :
llvm::post_order_ext(root, visited)) {
86 auto *op = node->getModule().getOperation();
93 bool effectful(Operation *op)
const {
96 if (
auto name = dyn_cast<FNamableOp>(op))
97 if (!name.hasDroppableName())
99 if (op->getNumRegions() != 0)
101 if (
auto instance = dyn_cast<InstanceOp>(op))
102 return effectfulModules.contains(instance.getModuleNameAttr().getAttr());
103 if (isa<FConnectLike, WireOp, RegResetOp, RegOp, MemOp, NodeOp>(op))
105 return !(mlir::isMemoryEffectFree(op) ||
106 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
107 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
112 void update(FModuleOp moduleOp) {
113 moduleOp.getBodyBlock()->walk([&](Operation *op) {
115 markEffectful(moduleOp);
116 return WalkResult::interrupt();
118 return WalkResult::advance();
123 void update(FModuleLike moduleOp) {
128 return markEffectful(moduleOp);
130 for (
auto annos : moduleOp.getPortAnnotations())
131 if (!cast<ArrayAttr>(annos).
empty())
132 return markEffectful(moduleOp);
134 auto *op = moduleOp.getOperation();
136 if (
auto m = dyn_cast<FModuleOp>(op))
139 if (
auto m = dyn_cast<FMemModuleOp>(op))
143 return markEffectful(moduleOp);
146 void update(Operation *op) {
147 if (
auto moduleOp = dyn_cast<FModuleLike>(op))
152 void markEffectful(FModuleLike moduleOp) {
153 effectfulModules.insert(moduleOp.getModuleNameAttr());
156 DenseSet<StringAttr> effectfulModules;
167 constexpr Demand() : Demand(nullptr) {}
168 constexpr Demand(Block *block) : block(block) {}
170 constexpr Demand merge(Demand other)
const {
171 if (block == other.block)
172 return Demand(block);
173 if (other.block ==
nullptr)
174 return Demand(block);
175 if (block ==
nullptr)
176 return Demand(other.block);
180 b = b->getParentOp()->getBlock();
185 bool mergeIn(Demand other) {
187 auto next = merge(other);
192 constexpr bool operator==(Demand rhs)
const {
return block == rhs.block; }
193 constexpr bool operator!=(Demand rhs)
const {
return block != rhs.block; }
194 constexpr operator bool()
const {
return block; }
202 return op && (isa<LayerBlockOp>(op) || isa<FModuleOp>(op));
223static Demand
clamp(Operation *op, Demand demand) {
227 auto *upper = op->getBlock();
228 assert(upper &&
"this should not be called on a top-level operation.");
233 for (
auto *i = demand.block; i != upper; i = i->getParentOp()->getBlock())
235 demand = i->getParentOp()->getBlock();
242 using WorkStack = std::vector<Operation *>;
244 DemandInfo(
const EffectInfo &, FModuleOp);
246 Demand getDemandFor(Operation *op)
const {
return table.lookup(op); }
252 void run(
const EffectInfo &, FModuleOp, WorkStack &);
256 void update(WorkStack &work, Operation *op, Demand demand) {
257 if (table[op].mergeIn(
clamp(op, demand)))
261 void update(WorkStack &work, Value value, Demand demand) {
262 if (
auto result = dyn_cast<OpResult>(value))
263 update(work, cast<OpResult>(value).getOwner(), demand);
266 void updateConnects(WorkStack &, Value, Demand);
267 void updateConnects(WorkStack &, Operation *, Demand);
269 llvm::DenseMap<Operation *, Demand> table;
273DemandInfo::DemandInfo(
const EffectInfo &effectInfo, FModuleOp moduleOp) {
275 Block *body = moduleOp.getBodyBlock();
276 ArrayRef<bool> dirs = moduleOp.getPortDirections();
277 for (
unsigned i = 0, e = moduleOp.getNumPorts(); i < e; ++i)
279 updateConnects(work, body->getArgument(i), moduleOp.getBodyBlock());
280 moduleOp.getBodyBlock()->walk([&](Operation *op) {
281 if (effectInfo.effectful(op))
282 update(work, op, op->getBlock());
284 run(effectInfo, moduleOp, work);
287void DemandInfo::run(
const EffectInfo &effectInfo, FModuleOp, WorkStack &work) {
288 while (!work.empty()) {
289 auto *op = work.back();
291 auto demand = getDemandFor(op);
292 for (
auto operand : op->getOperands())
293 update(work, operand, demand);
294 updateConnects(work, op, demand);
304void DemandInfo::updateConnects(WorkStack &work, Value value, Demand demand) {
305 struct StackElement {
307 Value::user_iterator it;
310 SmallVector<StackElement> stack;
311 stack.push_back({value, value.user_begin()});
312 while (!stack.empty()) {
313 auto &top = stack.back();
314 auto end = top.value.user_end();
320 auto *user = *(top.it++);
321 if (
auto connect = dyn_cast<FConnectLike>(user)) {
322 if (
connect.getDest() == top.value) {
323 update(work, connect, demand);
327 if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(user)) {
328 for (
auto result : user->getResults())
329 stack.push_back({result, result.user_begin()});
336void DemandInfo::updateConnects(WorkStack &work, Operation *op, Demand demand) {
337 if (isa<WireOp, RegResetOp, RegOp, MemOp, ObjectOp>(op)) {
338 for (
auto result : op->getResults())
339 updateConnects(work, result, demand);
340 }
else if (
auto inst = dyn_cast<InstanceOp>(op)) {
341 auto dirs = inst.getPortDirections();
342 for (
unsigned i = 0, e = inst->getNumResults(); i < e; ++i) {
344 updateConnects(work, inst.getResult(i), demand);
354class ModuleLayerSink {
356 static bool run(FModuleOp moduleOp,
const EffectInfo &effectInfo) {
357 return ModuleLayerSink(moduleOp, effectInfo)();
361 ModuleLayerSink(FModuleOp moduleOp,
const EffectInfo &effectInfo)
362 : moduleOp(moduleOp), effectInfo(effectInfo) {}
365 void moveLayersToBack(Operation *op);
366 void moveLayersToBack(Block *block);
368 void erase(Operation *op);
369 void sinkOpByCloning(Operation *op);
370 void sinkOpByMoving(Operation *op, Block *dest);
373 const EffectInfo &effectInfo;
374 bool changed =
false;
379void ModuleLayerSink::moveLayersToBack(Operation *op) {
380 for (
auto &r : op->getRegions())
381 for (auto &b : r.getBlocks())
382 moveLayersToBack(&b);
386void ModuleLayerSink::moveLayersToBack(Block *block) {
387 auto i = block->rbegin();
388 auto e = block->rend();
393 moveLayersToBack(op);
394 if (!isa<LayerBlockOp>(op))
407 moveLayersToBack(op);
408 if (isa<LayerBlockOp>(op)) {
418void ModuleLayerSink::erase(Operation *op) {
423void ModuleLayerSink::sinkOpByCloning(Operation *op) {
426 auto *src = op->getBlock();
427 DenseMap<Block *, Operation *> cache;
428 for (
unsigned i = 0, e = op->getNumResults(); i < e; ++i) {
429 for (
auto &use :
llvm::make_early_inc_range(op->getResult(i).getUses())) {
430 auto *dst = use.getOwner()->getBlock();
432 auto &clone = cache[dst];
434 clone = OpBuilder::atBlockBegin(dst).clone(*op);
435 use.set(clone->getResult(i));
442 if (isOpTriviallyDead(op))
446void ModuleLayerSink::sinkOpByMoving(Operation *op, Block *dst) {
447 if (dst != op->getBlock()) {
448 op->moveBefore(dst, dst->begin());
453bool ModuleLayerSink::operator()() {
454 moveLayersToBack(moduleOp.getBodyBlock());
455 DemandInfo demandInfo(effectInfo, moduleOp);
456 walkBwd(moduleOp.getBodyBlock(), [&](Operation *op) {
457 auto demand = demandInfo.getDemandFor(op);
461 return sinkOpByCloning(op);
462 sinkOpByMoving(op, demand.block);
474struct AdvancedLayerSinkPass final
475 :
public circt::firrtl::impl::AdvancedLayerSinkBase<AdvancedLayerSinkPass> {
476 void runOnOperation()
override;
480void AdvancedLayerSinkPass::runOnOperation() {
481 auto circuit = getOperation();
484 <<
"Circuit: '" << circuit.getName() <<
"'\n";);
485 auto &instanceGraph = getAnalysis<InstanceGraph>();
486 EffectInfo effectInfo(circuit, instanceGraph);
488 std::atomic<bool> changed(
false);
489 parallelForEach(&getContext(), circuit.getOps<FModuleOp>(),
490 [&](FModuleOp moduleOp) {
491 if (ModuleLayerSink::run(moduleOp, effectInfo))
496 markAllAnalysesPreserved();
498 markAnalysesPreserved<InstanceGraph>();
506 return std::make_unique<AdvancedLayerSinkPass>();
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)
assert(baseType &&"element must be base type")
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,...
std::unique_ptr< mlir::Pass > createAdvancedLayerSinkPass()
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)