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"
33 using namespace circt;
34 using namespace firrtl;
48 void 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());
75 DenseSet<InstanceGraphNode *> visited;
76 for (
auto *root : instanceGraph) {
77 for (
auto *node : llvm::post_order_ext(root, visited)) {
78 auto *op = node->getModule().getOperation();
85 bool effectful(Operation *op)
const {
88 if (
auto name = dyn_cast<FNamableOp>(op))
89 if (!name.hasDroppableName())
91 if (op->getNumRegions() != 0)
93 if (
auto instance = dyn_cast<InstanceOp>(op))
94 return effectfulModules.contains(instance.getModuleNameAttr().getAttr());
95 if (isa<FConnectLike, WireOp, RegResetOp, RegOp, MemOp, NodeOp>(op))
97 return !(mlir::isMemoryEffectFree(op) ||
98 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
99 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
104 void update(FModuleOp moduleOp) {
105 moduleOp.getBodyBlock()->walk([&](Operation *op) {
107 markEffectful(moduleOp);
108 return WalkResult::interrupt();
110 return WalkResult::advance();
115 void update(FModuleLike moduleOp) {
120 return markEffectful(moduleOp);
122 for (
auto annos : moduleOp.getPortAnnotations())
123 if (!cast<ArrayAttr>(annos).
empty())
124 return markEffectful(moduleOp);
126 auto *op = moduleOp.getOperation();
128 if (
auto m = dyn_cast<FModuleOp>(op))
131 if (
auto m = dyn_cast<FMemModuleOp>(op))
135 return markEffectful(moduleOp);
138 void update(Operation *op) {
139 if (
auto moduleOp = dyn_cast<FModuleLike>(op))
144 void markEffectful(FModuleLike moduleOp) {
145 effectfulModules.insert(moduleOp.getModuleNameAttr());
148 DenseSet<StringAttr> effectfulModules;
159 constexpr Demand() : Demand(nullptr) {}
160 constexpr Demand(Block *block) : block(block) {}
162 constexpr Demand merge(Demand other)
const {
163 if (block == other.block)
164 return Demand(block);
165 if (other.block ==
nullptr)
166 return Demand(block);
167 if (block ==
nullptr)
168 return Demand(other.block);
172 b = b->getParentOp()->getBlock();
177 bool mergeIn(Demand other) {
179 auto next = merge(other);
184 constexpr
bool operator==(Demand rhs)
const {
return block == rhs.block; }
185 constexpr
bool operator!=(Demand rhs)
const {
return block != rhs.block; }
186 constexpr
operator bool()
const {
return block; }
194 return op && (isa<LayerBlockOp>(op) || isa<FModuleOp>(op));
215 static Demand
clamp(Operation *op, Demand demand) {
219 auto *upper = op->getBlock();
220 assert(upper &&
"this should not be called on a top-level operation.");
225 for (
auto *i = demand.block; i != upper; i = i->getParentOp()->getBlock())
227 demand = i->getParentOp()->getBlock();
234 using WorkStack = std::vector<Operation *>;
236 DemandInfo(
const EffectInfo &, FModuleOp);
238 Demand getDemandFor(Operation *op)
const {
return table.lookup(op); }
244 void run(
const EffectInfo &, FModuleOp, WorkStack &);
248 void update(WorkStack &work, Operation *op, Demand demand) {
249 if (table[op].mergeIn(
clamp(op, demand)))
253 void update(WorkStack &work, Value value, Demand demand) {
254 if (
auto result = dyn_cast<OpResult>(value))
255 update(work, cast<OpResult>(value).getOwner(), demand);
258 void updateConnects(WorkStack &, Value, Demand);
259 void updateConnects(WorkStack &, Operation *, Demand);
261 llvm::DenseMap<Operation *, Demand> table;
265 DemandInfo::DemandInfo(
const EffectInfo &effectInfo, FModuleOp moduleOp) {
267 Block *body = moduleOp.getBodyBlock();
268 ArrayRef<bool> dirs = moduleOp.getPortDirections();
269 for (
unsigned i = 0, e = moduleOp.getNumPorts(); i < e; ++i)
271 updateConnects(work, body->getArgument(i), moduleOp.getBodyBlock());
272 moduleOp.getBodyBlock()->walk([&](Operation *op) {
273 if (effectInfo.effectful(op))
274 update(work, op, op->getBlock());
276 run(effectInfo, moduleOp, work);
279 void DemandInfo::run(
const EffectInfo &effectInfo, FModuleOp, WorkStack &work) {
280 while (!work.empty()) {
281 auto *op = work.back();
283 auto demand = getDemandFor(op);
284 for (
auto operand : op->getOperands())
285 update(work, operand, demand);
286 updateConnects(work, op, demand);
296 void DemandInfo::updateConnects(WorkStack &work, Value value, Demand demand) {
297 struct StackElement {
299 Value::user_iterator it;
302 SmallVector<StackElement> stack;
303 stack.push_back({value, value.user_begin()});
304 while (!stack.empty()) {
305 auto &top = stack.back();
306 auto end = top.value.user_end();
312 auto *user = *(top.it++);
313 if (
auto connect = dyn_cast<FConnectLike>(user)) {
314 if (
connect.getDest() == top.value) {
319 if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(user)) {
320 for (
auto result : user->getResults())
321 stack.push_back({result, result.user_begin()});
328 void DemandInfo::updateConnects(WorkStack &work, Operation *op, Demand demand) {
329 if (isa<WireOp, RegResetOp, RegOp, MemOp, ObjectOp>(op)) {
330 for (
auto result : op->getResults())
331 updateConnects(work, result, demand);
332 }
else if (
auto inst = dyn_cast<InstanceOp>(op)) {
333 auto dirs = inst.getPortDirections();
334 for (
unsigned i = 0, e = inst->getNumResults(); i < e; ++i) {
336 updateConnects(work, inst.getResult(i), demand);
346 class ModuleLayerSink {
348 static bool run(FModuleOp moduleOp,
const EffectInfo &effectInfo) {
349 return ModuleLayerSink(moduleOp, effectInfo)();
353 ModuleLayerSink(FModuleOp moduleOp,
const EffectInfo &effectInfo)
354 : moduleOp(moduleOp), effectInfo(effectInfo) {}
357 void moveLayersToBack(Operation *op);
358 void moveLayersToBack(Block *block);
361 const EffectInfo &effectInfo;
362 bool changed =
false;
367 void ModuleLayerSink::moveLayersToBack(Operation *op) {
368 for (
auto &r : op->getRegions())
369 for (
auto &b : r.getBlocks())
370 moveLayersToBack(&b);
374 void ModuleLayerSink::moveLayersToBack(Block *block) {
375 auto i = block->rbegin();
376 auto e = block->rend();
381 moveLayersToBack(op);
382 if (!isa<LayerBlockOp>(op))
395 moveLayersToBack(op);
396 if (isa<LayerBlockOp>(op)) {
406 bool ModuleLayerSink::operator()() {
407 moveLayersToBack(moduleOp.getBodyBlock());
408 DemandInfo demandInfo(effectInfo, moduleOp);
409 walkBwd(moduleOp.getBodyBlock(), [&](Operation *op) {
410 auto demand = demandInfo.getDemandFor(op);
417 if (demand == op->getBlock())
420 op->moveBefore(demand.block, demand.block->begin());
433 struct AdvancedLayerSinkPass final
434 :
public circt::firrtl::impl::AdvancedLayerSinkBase<AdvancedLayerSinkPass> {
435 void runOnOperation()
override;
439 void AdvancedLayerSinkPass::runOnOperation() {
440 auto circuit = getOperation();
443 <<
"Circuit: '" << circuit.getName() <<
"'\n";);
444 auto &instanceGraph = getAnalysis<InstanceGraph>();
445 EffectInfo effectInfo(circuit, instanceGraph);
447 std::atomic<bool> changed(
false);
448 parallelForEach(&getContext(), circuit.getOps<FModuleOp>(),
449 [&](FModuleOp moduleOp) {
450 if (ModuleLayerSink::run(moduleOp, effectInfo))
455 markAllAnalysesPreserved();
457 markAnalysesPreserved<InstanceGraph>();
465 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")
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.
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()
ArrayAttr getAnnotationsIfPresent(Operation *op)
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)