17 #include "mlir/IR/Dominance.h"
18 #include "mlir/IR/Iterators.h"
19 #include "mlir/IR/Threading.h"
20 #include "mlir/Interfaces/ControlFlowInterfaces.h"
21 #include "mlir/Interfaces/SideEffectInterfaces.h"
22 #include "mlir/Pass/Pass.h"
23 #include "mlir/Transforms/ControlFlowSinkUtils.h"
25 #define DEBUG_TYPE "firrtl-layer-sink"
29 #define GEN_PASS_DEF_ADVANCEDLAYERSINK
30 #include "circt/Dialect/FIRRTL/Passes.h.inc"
34 using namespace circt;
35 using namespace firrtl;
49 void walkBwd(
Block *block, T &&f) {
51 llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
52 for (
auto ®ion : op.getRegions())
53 for (
auto &block : region.getBlocks())
64 return block->getParent()->isProperAncestor(other->getParent());
76 DenseSet<InstanceGraphNode *> visited;
77 for (
auto *root : instanceGraph) {
78 for (
auto *node : llvm::post_order_ext(root, visited)) {
79 auto *op = node->getModule().getOperation();
86 bool effectful(Operation *op)
const {
89 if (
auto name = dyn_cast<FNamableOp>(op))
90 if (!name.hasDroppableName())
92 if (op->getNumRegions() != 0)
94 if (
auto instance = dyn_cast<InstanceOp>(op))
95 return effectfulModules.contains(instance.getModuleNameAttr().getAttr());
96 if (isa<FConnectLike, WireOp, RegResetOp, RegOp, MemOp, NodeOp>(op))
98 return !(mlir::isMemoryEffectFree(op) ||
99 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
100 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
105 void update(FModuleOp moduleOp) {
106 moduleOp.getBodyBlock()->walk([&](Operation *op) {
108 markEffectful(moduleOp);
109 return WalkResult::interrupt();
111 return WalkResult::advance();
115 void update(FModuleLike moduleOp) {
117 return markEffectful(moduleOp);
118 auto *op = moduleOp.getOperation();
120 if (
auto m = dyn_cast<FModuleOp>(op))
123 if (
auto m = dyn_cast<FMemModuleOp>(op))
127 return markEffectful(moduleOp);
130 void update(Operation *op) {
131 if (
auto moduleOp = dyn_cast<FModuleLike>(op))
136 void markEffectful(FModuleLike moduleOp) {
137 effectfulModules.insert(moduleOp.getModuleNameAttr());
140 DenseSet<StringAttr> effectfulModules;
151 constexpr Demand() : Demand(nullptr) {}
152 constexpr Demand(Block *block) : block(block) {}
154 constexpr Demand merge(Demand other)
const {
155 if (block == other.block)
156 return Demand(block);
157 if (other.block ==
nullptr)
158 return Demand(block);
159 if (block ==
nullptr)
160 return Demand(other.block);
164 b = b->getParentOp()->getBlock();
169 bool mergeIn(Demand other) {
171 auto next = merge(other);
176 constexpr
bool operator==(Demand rhs)
const {
return block == rhs.block; }
177 constexpr
bool operator!=(Demand rhs)
const {
return block != rhs.block; }
178 constexpr
operator bool()
const {
return block; }
186 return op && (isa<LayerBlockOp>(op) || isa<FModuleOp>(op));
207 static Demand
clamp(Operation *op, Demand demand) {
211 auto *upper = op->getBlock();
212 assert(upper &&
"this should not be called on a top-level operation.");
217 for (
auto *i = demand.block; i != upper; i = i->getParentOp()->getBlock())
219 demand = i->getParentOp()->getBlock();
226 using WorkStack = std::vector<Operation *>;
228 DemandInfo(
const EffectInfo &, FModuleOp);
230 Demand getDemandFor(Operation *op)
const {
return table.lookup(op); }
236 void run(
const EffectInfo &, FModuleOp, WorkStack &);
240 void update(WorkStack &work, Operation *op, Demand demand) {
241 if (table[op].mergeIn(
clamp(op, demand)))
245 void update(WorkStack &work, Value value, Demand demand) {
246 if (
auto result = dyn_cast<OpResult>(value))
247 update(work, cast<OpResult>(value).getOwner(), demand);
250 void updateConnects(WorkStack &, Value, Demand);
251 void updateConnects(WorkStack &, Operation *, Demand);
253 llvm::DenseMap<Operation *, Demand> table;
257 DemandInfo::DemandInfo(
const EffectInfo &effectInfo, FModuleOp moduleOp) {
259 Block *body = moduleOp.getBodyBlock();
260 ArrayRef<bool> dirs = moduleOp.getPortDirections();
261 for (
unsigned i = 0, e = moduleOp.getNumPorts(); i < e; ++i)
263 updateConnects(work, body->getArgument(i), moduleOp.getBodyBlock());
264 moduleOp.getBodyBlock()->walk([&](Operation *op) {
265 if (effectInfo.effectful(op))
266 update(work, op, op->getBlock());
268 run(effectInfo, moduleOp, work);
271 void DemandInfo::run(
const EffectInfo &effectInfo, FModuleOp, WorkStack &work) {
272 while (!work.empty()) {
273 auto *op = work.back();
275 auto demand = getDemandFor(op);
276 for (
auto operand : op->getOperands())
277 update(work, operand, demand);
278 updateConnects(work, op, demand);
288 void DemandInfo::updateConnects(WorkStack &work, Value value, Demand demand) {
289 struct StackElement {
291 Value::user_iterator it;
294 SmallVector<StackElement> stack;
295 stack.push_back({value, value.user_begin()});
296 while (!stack.empty()) {
297 auto &top = stack.back();
298 auto end = top.value.user_end();
304 auto *user = *(top.it++);
305 if (
auto connect = dyn_cast<FConnectLike>(user)) {
306 if (
connect.getDest() == top.value) {
311 if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(user)) {
312 for (
auto result : user->getResults())
313 stack.push_back({result, result.user_begin()});
320 void DemandInfo::updateConnects(WorkStack &work, Operation *op, Demand demand) {
321 if (isa<WireOp, RegResetOp, RegOp, MemOp, ObjectOp>(op)) {
322 for (
auto result : op->getResults())
323 updateConnects(work, result, demand);
324 }
else if (
auto inst = dyn_cast<InstanceOp>(op)) {
325 auto dirs = inst.getPortDirections();
326 for (
unsigned i = 0, e = inst->getNumResults(); i < e; ++i) {
328 updateConnects(work, inst.getResult(i), demand);
338 class ModuleLayerSink {
340 static bool run(FModuleOp moduleOp,
const EffectInfo &effectInfo) {
341 return ModuleLayerSink(moduleOp, effectInfo)();
345 ModuleLayerSink(FModuleOp moduleOp,
const EffectInfo &effectInfo)
346 : moduleOp(moduleOp), effectInfo(effectInfo) {}
349 void moveLayersToBack(Operation *op);
350 void moveLayersToBack(Block *block);
353 const EffectInfo &effectInfo;
354 bool changed =
false;
359 void ModuleLayerSink::moveLayersToBack(Operation *op) {
360 for (
auto &r : op->getRegions())
361 for (
auto &b : r.getBlocks())
362 moveLayersToBack(&b);
366 void ModuleLayerSink::moveLayersToBack(Block *block) {
367 auto i = block->rbegin();
368 auto e = block->rend();
373 moveLayersToBack(op);
374 if (!isa<LayerBlockOp>(op))
387 moveLayersToBack(op);
388 if (isa<LayerBlockOp>(op)) {
398 bool ModuleLayerSink::operator()() {
399 moveLayersToBack(moduleOp.getBodyBlock());
400 DemandInfo demandInfo(effectInfo, moduleOp);
401 walkBwd(moduleOp.getBodyBlock(), [&](Operation *op) {
402 auto demand = demandInfo.getDemandFor(op);
409 if (demand == op->getBlock())
412 op->moveBefore(demand.block, demand.block->begin());
425 struct AdvancedLayerSinkPass final
426 :
public circt::firrtl::impl::AdvancedLayerSinkBase<AdvancedLayerSinkPass> {
427 void runOnOperation()
override;
431 void AdvancedLayerSinkPass::runOnOperation() {
432 auto circuit = getOperation();
435 <<
"Circuit: '" << circuit.getName() <<
"'\n";);
436 auto &instanceGraph = getAnalysis<InstanceGraph>();
437 EffectInfo effectInfo(circuit, instanceGraph);
439 std::atomic<bool> changed(
false);
440 parallelForEach(&getContext(), circuit.getOps<FModuleOp>(),
441 [&](FModuleOp moduleOp) {
442 if (ModuleLayerSink::run(moduleOp, effectInfo))
447 markAllAnalysesPreserved();
449 markAnalysesPreserved<InstanceGraph>();
457 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.
assert(baseType &&"element must be base type")
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.
def 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()
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
bool operator==(uint64_t a, const FVInt &b)
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)