Loading [MathJax]/extensions/tex2jax.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LongestPathAnalysis.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This analysis computes the longest combinational paths through a circuit
10// represented in the AIG (And-Inverter Graph) dialect. The key aspects are:
11//
12// - Each AIG and-inverter operation is considered to have a unit delay of 1
13// - The analysis traverses the circuit graph from inputs/registers to outputs
14// - It handles hierarchical designs by analyzing modules bottom-up
15// - Results include full path information with delays and debug points
16// - Caching is used extensively to improve performance on large designs
17//
18// The core algorithm works as follows:
19// 1. Build an instance graph of the full design hierarchy
20// 2. Analyze modules in post-order (children before parents)
21// 3. For each module:
22// - Trace paths from inputs and registers
23// - Propagate delays through logic and across module boundaries
24// - Record maximum delay and path info for each node
25// 4. Combine results across hierarchy to get full chip critical paths
26//
27// The analysis handles both closed paths (register-to-register) and open
28// paths (input-to-register, register-to-output) across the full hierarchy.
29//===----------------------------------------------------------------------===//
30
39#include "circt/Support/LLVM.h"
40#include "mlir/IR/BuiltinAttributes.h"
41#include "mlir/IR/BuiltinOps.h"
42#include "mlir/IR/Diagnostics.h"
43#include "mlir/IR/Operation.h"
44#include "mlir/IR/Threading.h"
45#include "mlir/IR/Value.h"
46#include "mlir/IR/Visitors.h"
47#include "mlir/Pass/AnalysisManager.h"
48#include "mlir/Support/FileUtilities.h"
49#include "mlir/Support/LLVM.h"
50#include "llvm/ADT//MapVector.h"
51#include "llvm/ADT/ArrayRef.h"
52#include "llvm/ADT/DenseMapInfoVariant.h"
53#include "llvm/ADT/EquivalenceClasses.h"
54#include "llvm/ADT/ImmutableList.h"
55#include "llvm/ADT/MapVector.h"
56#include "llvm/ADT/PostOrderIterator.h"
57#include "llvm/ADT/STLExtras.h"
58#include "llvm/ADT/SmallVector.h"
59#include "llvm/ADT/StringRef.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/LogicalResult.h"
63#include "llvm/Support/MathExtras.h"
64#include "llvm/Support/Mutex.h"
65#include "llvm/Support/raw_ostream.h"
66#include <condition_variable>
67#include <cstdint>
68#include <memory>
69#include <mutex>
70
71#define DEBUG_TYPE "aig-longest-path-analysis"
72using namespace circt;
73using namespace aig;
74
75static size_t getBitWidth(Value value) {
76 if (auto vecType = dyn_cast<seq::ClockType>(value.getType()))
77 return 1;
78 if (auto memory = dyn_cast<seq::FirMemType>(value.getType()))
79 return memory.getWidth();
80 return hw::getBitWidth(value.getType());
81}
82
83template <typename T, typename Key>
84static void
85deduplicatePathsImpl(SmallVectorImpl<T> &results, size_t startIndex,
86 llvm::function_ref<Key(const T &)> keyFn,
87 llvm::function_ref<int64_t(const T &)> delayFn) {
88 // Take only maximum for each path destination.
89 DenseMap<Key, size_t> saved;
90 for (auto [i, path] :
91 llvm::enumerate(ArrayRef(results).drop_front(startIndex))) {
92 auto &slot = saved[keyFn(path)];
93 if (slot == 0) {
94 slot = startIndex + i + 1;
95 continue;
96 }
97 if (delayFn(results[slot - 1]) < delayFn(path))
98 results[slot - 1] = path;
99 }
100
101 results.resize(saved.size() + startIndex);
102}
103
104static void deduplicatePaths(SmallVectorImpl<OpenPath> &results,
105 size_t startIndex = 0) {
106 deduplicatePathsImpl<OpenPath, Object>(
107 results, startIndex, [](const auto &path) { return path.fanIn; },
108 [](const auto &path) { return path.delay; });
109}
110
111static void deduplicatePaths(SmallVectorImpl<DataflowPath> &results,
112 size_t startIndex = 0) {
114 std::pair<DataflowPath::FanOutType, Object>>(
115 results, startIndex,
116 [](const DataflowPath &path) {
117 return std::pair(path.getFanOut(), path.getFanIn());
118 },
119 [](const DataflowPath &path) { return path.getDelay(); });
120}
121
122static llvm::ImmutableList<DebugPoint>
123mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
124 llvm::ImmutableList<DebugPoint> list,
125 llvm::function_ref<DebugPoint(DebugPoint)> fn) {
126 if (list.isEmpty())
127 return list;
128 auto &head = list.getHead();
129 return debugPointFactory->add(fn(head),
130 mapList(debugPointFactory, list.getTail(), fn));
131}
132
133static llvm::ImmutableList<DebugPoint>
134concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
135 llvm::ImmutableList<DebugPoint> lhs,
136 llvm::ImmutableList<DebugPoint> rhs) {
137 if (lhs.isEmpty())
138 return rhs;
139 return debugPointFactory->add(
140 lhs.getHead(), concatList(debugPointFactory, lhs.getTail(), rhs));
141}
142
143static StringAttr getNameImpl(Value value) {
144 if (auto arg = dyn_cast<BlockArgument>(value)) {
145 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
146 if (!op) {
147 // TODO: Handle other operations.
148 return StringAttr::get(value.getContext(), "<unknown-argument>");
149 }
150 return op.getArgName(arg.getArgNumber());
151 }
152 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
153 .Case<seq::CompRegOp, seq::FirRegOp>(
154 [](auto op) { return op.getNameAttr(); })
155 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
156 SmallString<16> str;
157 str += op.getInstanceName();
158 str += ".";
159 str += cast<StringAttr>(
160 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
161 return StringAttr::get(op.getContext(), str);
162 })
163 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
164 llvm::SmallString<16> str;
165 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
166 str += ".read_port";
167 return StringAttr::get(value.getContext(), str);
168 })
169 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
170 llvm::SmallString<16> str;
171 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
172 str += ".rw_port";
173 return StringAttr::get(value.getContext(), str);
174 })
175 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
176 llvm::SmallString<16> str;
177 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
178 str += ".write_port";
179 return StringAttr::get(value.getContext(), str);
180 })
181 .Default([&](auto op) {
182 if (auto name = op->template getAttrOfType<StringAttr>("sv.namehint"))
183 return name;
184 llvm::errs() << "Unknown op: " << *op << "\n";
185 return StringAttr::get(value.getContext(), "");
186 });
187}
188
189static void printObjectImpl(llvm::raw_ostream &os, const Object &object,
190 int64_t delay = -1,
191 llvm::ImmutableList<DebugPoint> history = {},
192 StringRef comment = "") {
193 std::string pathString;
194 llvm::raw_string_ostream osPath(pathString);
195 object.instancePath.print(osPath);
196 os << "Object(" << pathString << "." << getNameImpl(object.value).getValue()
197 << "[" << object.bitPos << "]";
198 if (delay != -1)
199 os << ", delay=" << delay;
200 if (!history.isEmpty()) {
201 os << ", history=[";
202 llvm::interleaveComma(history, os, [&](DebugPoint p) { p.print(os); });
203 os << "]";
204 }
205 if (!comment.empty())
206 os << ", comment=\"" << comment << "\"";
207 os << ")";
208}
209
210using namespace circt;
211using namespace aig;
212
213//===----------------------------------------------------------------------===//
214// Printing
215//===----------------------------------------------------------------------===//
216
217void OpenPath::print(llvm::raw_ostream &os) const {
219}
220
221void DebugPoint::print(llvm::raw_ostream &os) const {
222 printObjectImpl(os, object, delay, {}, comment);
223}
224
225void Object::print(llvm::raw_ostream &os) const { printObjectImpl(os, *this); }
226
227void DataflowPath::printFanOut(llvm::raw_ostream &os) {
228 if (auto *object = std::get_if<Object>(&fanOut)) {
229 object->print(os);
230 } else {
231 auto &[resultNumber, bitPos] =
232 *std::get_if<std::pair<size_t, size_t>>(&fanOut);
233 auto outputPortName = root.getOutputName(resultNumber);
234 os << "Object($root." << outputPortName << "[" << bitPos << "])";
235 }
236}
237
238void DataflowPath::print(llvm::raw_ostream &os) {
239 os << "root=" << root.getModuleName() << ", ";
240 os << "fanOut=";
241 printFanOut(os);
242 os << ", ";
243 os << "fanIn=";
244 path.print(os);
245}
246
247//===----------------------------------------------------------------------===//
248// OpenPath
249//===----------------------------------------------------------------------===//
250
256
259 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
261 fanIn.prependPaths(cache, path);
262 if (debugPointFactory)
263 this->history = mapList(debugPointFactory, this->history,
264 [&](DebugPoint p) -> DebugPoint {
265 p.object.prependPaths(cache, path);
266 return p;
267 });
268 return *this;
269}
270
271//===----------------------------------------------------------------------===//
272// DataflowPath
273//===----------------------------------------------------------------------===//
274
277 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
279 this->path.prependPaths(cache, debugPointFactory, path);
280 if (!path.empty()) {
281 auto root = path.top()->getParentOfType<hw::HWModuleOp>();
282 assert(root && "root is not a hw::HWModuleOp");
283 this->root = root;
284 }
285
286 // If the fanout is an object, prepend the path.
287 if (auto *object = std::get_if<Object>(&fanOut))
288 object->prependPaths(cache, path);
289
290 return *this;
291}
292
294 // If the fanout is an object, return the location of the object.
295 if (auto *object = std::get_if<Object>(&fanOut))
296 return object->value.getLoc();
297
298 // Return output port location.
299 return root.getOutputLoc(std::get<std::pair<size_t, size_t>>(fanOut).first);
300}
301
302class LocalVisitor;
303
304//===----------------------------------------------------------------------===//
305// Context
306//===----------------------------------------------------------------------===//
307/// This class provides a thread-safe interface to access the analysis results.
308
309class Context {
310public:
312 const LongestPathAnalysisOption &option)
313 : instanceGraph(instanceGraph), option(option) {}
314 void notifyStart(StringAttr name) {
315 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
316 running.insert(name);
317 llvm::dbgs() << "[Timing] " << name << " started. running=[";
318 for (auto &name : running)
319 llvm::dbgs() << name << " ";
320 llvm::dbgs() << "]\n";
321 }
322
323 void notifyEnd(StringAttr name) {
324 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
325 running.remove(name);
326
327 llvm::dbgs() << "[Timing] " << name << " finished. running=[";
328 for (auto &name : running)
329 llvm::dbgs() << name << " ";
330 llvm::dbgs() << "]\n";
331 }
332
333 // Lookup a local visitor for `name`.
334 const LocalVisitor *getLocalVisitor(StringAttr name) const;
335
336 // Lookup a local visitor for `name`, and wait until it's done.
337 const LocalVisitor *getAndWaitLocalVisitor(StringAttr name) const;
338
339 // A map from the module name to the local visitor.
340 llvm::MapVector<StringAttr, std::unique_ptr<LocalVisitor>> localVisitors;
341 // This is non-null only if `module` is a ModuleOp.
342 circt::igraph::InstanceGraph *instanceGraph = nullptr;
343
344 bool doTraceDebugPoints() const { return option.traceDebugPoints; }
345
346private:
347 llvm::sys::SmartMutex<true> mutex;
348 llvm::SetVector<StringAttr> running;
350};
351
352// -----------------------------------------------------------------------------
353// LocalVisitor
354// -----------------------------------------------------------------------------
355
357public:
358 LocalVisitor(hw::HWModuleOp module, Context *ctx);
359 LogicalResult initializeAndRun();
360 // Wait until the thread is done.
361 void waitUntilDone() const;
362
363 // Get the longest paths for the given value and bit position.
364 // If the result is not cached, compute it and cache it.
365 FailureOr<ArrayRef<OpenPath>> getOrComputeResults(Value value, size_t bitPos);
366
367 // Get the longest paths for the given value and bit position. This returns
368 // an empty array if not pre-computed.
369 ArrayRef<OpenPath> getResults(Value value, size_t bitPos) const;
370
371 // A map from the object to the maximum distance and history.
373 llvm::MapVector<Object,
374 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
375
376 void getClosedPaths(SmallVectorImpl<DataflowPath> &results) const;
377 void setTopLevel() { this->topLevel = true; }
378 bool isTopLevel() const { return topLevel; }
379 hw::HWModuleOp getHWModuleOp() const { return module; }
380
381 const auto &getFromInputPortToFanOut() const { return fromInputPortToFanOut; }
382 const auto &getFromOutputPortToFanIn() const { return fromOutputPortToFanIn; }
383 const auto &getFanOutResults() const { return fanOutResults; }
384
386 return instancePathCache.get();
387 }
388
389 llvm::ImmutableListFactory<DebugPoint> *getDebugPointFactory() const {
390 return debugPointFactory.get();
391 }
392
393private:
394 void putUnclosedResult(const Object &object, int64_t delay,
395 llvm::ImmutableList<DebugPoint> history,
396 ObjectToMaxDistance &objectToMaxDistance);
397
398 // A map from the input port to the farthest fanOut.
399 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
401
402 // A map from the output port to the farthest fanIn.
403 llvm::MapVector<std::tuple<size_t, size_t>, ObjectToMaxDistance>
405
406 LogicalResult initializeAndRun(hw::InstanceOp instance);
407 LogicalResult initializeAndRun(hw::OutputOp output);
408
409 // --------------------------------------------------------------------------
410 // Visitors
411 // --------------------------------------------------------------------------
412 LogicalResult visitValue(Value value, size_t bitPos,
413 SmallVectorImpl<OpenPath> &results);
414 // Module boundary.
415 LogicalResult visit(mlir::BlockArgument argument, size_t bitPos,
416 SmallVectorImpl<OpenPath> &results);
417 LogicalResult visit(hw::InstanceOp op, size_t bitPos, size_t resultNum,
418 SmallVectorImpl<OpenPath> &results);
419
420 // Data-movement ops.
421 LogicalResult visit(hw::WireOp op, size_t bitPos,
422 SmallVectorImpl<OpenPath> &results);
423 LogicalResult visit(comb::ConcatOp op, size_t bitPos,
424 SmallVectorImpl<OpenPath> &results);
425 LogicalResult visit(comb::ExtractOp op, size_t bitPos,
426 SmallVectorImpl<OpenPath> &results);
427 LogicalResult visit(comb::ReplicateOp op, size_t bitPos,
428 SmallVectorImpl<OpenPath> &results);
429 // Track equivalence classes for data movement ops
430 // Treat output as equivalent to input for pure data movement operations
431 llvm::EquivalenceClasses<std::pair<Value, size_t>> ec;
432 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>> ecMap;
433 std::pair<Value, size_t> findLeader(Value value, size_t bitpos) const {
434 return ec.getLeaderValue({value, bitpos});
435 }
436 LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to,
437 size_t toBitPos,
438 SmallVectorImpl<OpenPath> &results);
439
440 // Bit-logical ops.
441 LogicalResult visit(aig::AndInverterOp op, size_t bitPos,
442 SmallVectorImpl<OpenPath> &results);
443 LogicalResult visit(comb::AndOp op, size_t bitPos,
444 SmallVectorImpl<OpenPath> &results);
445 LogicalResult visit(comb::XorOp op, size_t bitPos,
446 SmallVectorImpl<OpenPath> &results);
447 LogicalResult visit(comb::OrOp op, size_t bitPos,
448 SmallVectorImpl<OpenPath> &results);
449 LogicalResult visit(comb::MuxOp op, size_t bitPos,
450 SmallVectorImpl<OpenPath> &results);
451 LogicalResult addLogicOp(Operation *op, size_t bitPos,
452 SmallVectorImpl<OpenPath> &results);
453
454 // Constants.
455 LogicalResult visit(hw::ConstantOp op, size_t bitPos,
456 SmallVectorImpl<OpenPath> &results) {
457 return success();
458 }
459
460 // Registers are fanIn.
461 LogicalResult visit(seq::FirRegOp op, size_t bitPos,
462 SmallVectorImpl<OpenPath> &results) {
463 return markFanIn(op, bitPos, results);
464 }
465
466 LogicalResult visit(seq::CompRegOp op, size_t bitPos,
467 SmallVectorImpl<OpenPath> &results) {
468 return markFanIn(op, bitPos, results);
469 }
470
471 LogicalResult visit(seq::FirMemReadOp op, size_t bitPos,
472 SmallVectorImpl<OpenPath> &results) {
473 return markFanIn(op, bitPos, results);
474 }
475
476 LogicalResult visit(seq::FirMemReadWriteOp op, size_t bitPos,
477 SmallVectorImpl<OpenPath> &results) {
478 return markFanIn(op, bitPos, results);
479 }
480
481 LogicalResult visitDefault(Operation *op, size_t bitPos,
482 SmallVectorImpl<OpenPath> &results);
483
484 // Helper functions.
485 LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay,
486 SmallVectorImpl<OpenPath> &results);
487 LogicalResult markFanIn(Value value, size_t bitPos,
488 SmallVectorImpl<OpenPath> &results);
489 LogicalResult markRegFanOut(Value fanOut, Value start, Value reset = {},
490 Value resetValue = {}, Value enable = {});
491
492 // The module we are visiting.
493 hw::HWModuleOp module;
495
496 // Thread-local data structures.
497 std::unique_ptr<circt::igraph::InstancePathCache> instancePathCache;
498 // TODO: Make debug points optional.
499 std::unique_ptr<llvm::ImmutableListFactory<DebugPoint>> debugPointFactory;
500
501 // A map from the value point to the longest paths.
502 DenseMap<std::pair<Value, size_t>, SmallVector<OpenPath>> cachedResults;
503
504 // A map from the object to the longest paths.
505 DenseMap<Object, SmallVector<OpenPath>> fanOutResults;
506
507 // This is set to true when the thread is done.
508 std::atomic_bool done;
509 mutable std::condition_variable cv;
510 mutable std::mutex mutex;
511
512 // A flag to indicate the module is top-level.
513 bool topLevel = false;
514};
515
517 : module(module), ctx(ctx) {
519 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
520 instancePathCache = ctx->instanceGraph
521 ? std::make_unique<circt::igraph::InstancePathCache>(
522 *ctx->instanceGraph)
523 : nullptr;
524 done = false;
525}
526
527ArrayRef<OpenPath> LocalVisitor::getResults(Value value, size_t bitPos) const {
528 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
529 auto leader = ec.findLeader(valueAndBitPos);
530 if (leader != ec.member_end()) {
531 if (*leader != valueAndBitPos) {
532 // If this is not the leader, then use the leader.
533 return getResults(leader->first, leader->second);
534 }
535 }
536
537 auto it = cachedResults.find(valueAndBitPos);
538 // If not found, then consider it to be a constant.
539 if (it == cachedResults.end())
540 return {};
541 return it->second;
542}
543
544void LocalVisitor::putUnclosedResult(const Object &object, int64_t delay,
545 llvm::ImmutableList<DebugPoint> history,
546 ObjectToMaxDistance &objectToMaxDistance) {
547 auto &slot = objectToMaxDistance[object];
548 if (slot.first >= delay && delay != 0)
549 return;
550 slot = {delay, history};
551}
552
554 // Wait for the thread to finish.
555 std::unique_lock<std::mutex> lock(mutex);
556 cv.wait(lock, [this] { return done.load(); });
557}
558
559LogicalResult LocalVisitor::markRegFanOut(Value fanOut, Value start,
560 Value reset, Value resetValue,
561 Value enable) {
562 auto bitWidth = getBitWidth(fanOut);
563 auto record = [&](size_t fanOutBitPos, Value value, size_t bitPos) {
564 auto result = getOrComputeResults(value, bitPos);
565 if (failed(result))
566 return failure();
567 for (auto &path : *result) {
568 if (auto blockArg = dyn_cast<BlockArgument>(path.fanIn.value)) {
569 // Not closed.
570 putUnclosedResult({{}, fanOut, fanOutBitPos}, path.delay, path.history,
571 fromInputPortToFanOut[{blockArg, path.fanIn.bitPos}]);
572 } else {
573 // If the fanIn is not a port, record to the results.
574 fanOutResults[{{}, fanOut, fanOutBitPos}].push_back(path);
575 }
576 }
577 return success();
578 };
579
580 // Get paths for each bit, and record them.
581 for (size_t i = 0, e = bitWidth; i < e; ++i) {
582 if (failed(record(i, start, i)))
583 return failure();
584 }
585
586 // Edge from a reg to reset/resetValue.
587 if (reset)
588 for (size_t i = 0, e = bitWidth; i < e; ++i) {
589 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
590 return failure();
591 }
592
593 // Edge from a reg to enable signal.
594 if (enable)
595 for (size_t i = 0, e = bitWidth; i < e; ++i) {
596 if (failed(record(i, enable, 0)))
597 return failure();
598 }
599
600 return success();
601}
602
603LogicalResult LocalVisitor::markEquivalent(Value from, size_t fromBitPos,
604 Value to, size_t toBitPos,
605 SmallVectorImpl<OpenPath> &results) {
606 auto leader = ec.getOrInsertLeaderValue({to, toBitPos});
607 (void)leader;
608 // Merge classes, and visit the leader.
609 auto newLeader = ec.unionSets({to, toBitPos}, {from, fromBitPos});
610 assert(leader == *newLeader);
611 return visitValue(to, toBitPos, results);
612}
613
614LogicalResult LocalVisitor::addEdge(Value to, size_t bitPos, int64_t delay,
615 SmallVectorImpl<OpenPath> &results) {
616 auto result = getOrComputeResults(to, bitPos);
617 if (failed(result))
618 return failure();
619 for (auto &path : *result) {
620 auto newPath = path;
621 newPath.delay += delay;
622 results.push_back(newPath);
623 }
624 return success();
625}
626
627LogicalResult LocalVisitor::visit(aig::AndInverterOp op, size_t bitPos,
628 SmallVectorImpl<OpenPath> &results) {
629 return addLogicOp(op, bitPos, results);
630}
631
632LogicalResult LocalVisitor::visit(comb::AndOp op, size_t bitPos,
633 SmallVectorImpl<OpenPath> &results) {
634 return addLogicOp(op, bitPos, results);
635}
636
637LogicalResult LocalVisitor::visit(comb::OrOp op, size_t bitPos,
638 SmallVectorImpl<OpenPath> &results) {
639 return addLogicOp(op, bitPos, results);
640}
641
642LogicalResult LocalVisitor::visit(comb::XorOp op, size_t bitPos,
643 SmallVectorImpl<OpenPath> &results) {
644 return addLogicOp(op, bitPos, results);
645}
646
647LogicalResult LocalVisitor::visit(comb::MuxOp op, size_t bitPos,
648 SmallVectorImpl<OpenPath> &results) {
649 // Add a cost of 1 for the mux.
650 if (failed(addEdge(op.getCond(), 0, 1, results)) ||
651 failed(addEdge(op.getTrueValue(), bitPos, 1, results)) ||
652 failed(addEdge(op.getFalseValue(), bitPos, 1, results)))
653 return failure();
654 deduplicatePaths(results);
655 return success();
656}
657
658LogicalResult LocalVisitor::visit(comb::ExtractOp op, size_t bitPos,
659 SmallVectorImpl<OpenPath> &results) {
660 assert(getBitWidth(op.getInput()) > bitPos + op.getLowBit());
661 auto result = markEquivalent(op, bitPos, op.getInput(),
662 bitPos + op.getLowBit(), results);
663 return result;
664}
665
666LogicalResult LocalVisitor::visit(comb::ReplicateOp op, size_t bitPos,
667 SmallVectorImpl<OpenPath> &results) {
668 return markEquivalent(op, bitPos, op.getInput(),
669 bitPos % getBitWidth(op.getInput()), results);
670}
671
672LogicalResult LocalVisitor::markFanIn(Value value, size_t bitPos,
673 SmallVectorImpl<OpenPath> &results) {
674 results.emplace_back(circt::igraph::InstancePath(), value, bitPos);
675 return success();
676}
677
678LogicalResult LocalVisitor::visit(hw::WireOp op, size_t bitPos,
679 SmallVectorImpl<OpenPath> &results) {
680 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
681}
682
683LogicalResult LocalVisitor::visit(hw::InstanceOp op, size_t bitPos,
684 size_t resultNum,
685 SmallVectorImpl<OpenPath> &results) {
686 auto moduleName = op.getReferencedModuleNameAttr();
687 auto value = op->getResult(resultNum);
688
689 // If an instance graph is not available, we treat instance results as a
690 // fanIn.
691 if (!ctx->instanceGraph)
692 return markFanIn(value, bitPos, results);
693
694 // If an instance graph is available, then we can look up the module.
695 auto *node = ctx->instanceGraph->lookup(moduleName);
696 assert(node && "module not found");
697
698 // Otherwise, if the module is not a HWModuleOp, then we should treat it as a
699 // fanIn.
700 if (!isa<hw::HWModuleOp>(node->getModule()))
701 return markFanIn(value, bitPos, results);
702
703 auto *localVisitor = ctx->getAndWaitLocalVisitor(moduleName);
704 auto *fanInIt = localVisitor->fromOutputPortToFanIn.find({resultNum, bitPos});
705
706 // It means output is constant, so it's ok.
707 if (fanInIt == localVisitor->fromOutputPortToFanIn.end())
708 return success();
709
710 const auto &fanIns = fanInIt->second;
711
712 for (auto &[fanInPoint, delayAndHistory] : fanIns) {
713 auto [delay, history] = delayAndHistory;
714 auto newPath =
715 instancePathCache->prependInstance(op, fanInPoint.instancePath);
716
717 // If the fanIn is not a block argument, record it directly.
718 auto arg = dyn_cast<BlockArgument>(fanInPoint.value);
719 if (!arg) {
720 // Update the history to have correct instance path.
721 auto newHistory = debugPointFactory->getEmptyList();
722 if (ctx->doTraceDebugPoints()) {
723 newHistory =
724 mapList(debugPointFactory.get(), history, [&](DebugPoint p) {
725 p.object.instancePath =
726 instancePathCache->prependInstance(op, p.object.instancePath);
727 return p;
728 });
729 newHistory = debugPointFactory->add(
730 DebugPoint({}, value, bitPos, delay, "output port"), newHistory);
731 }
732
733 results.emplace_back(newPath, fanInPoint.value, fanInPoint.bitPos, delay,
734 newHistory);
735 continue;
736 }
737
738 // Otherwise, we need to look up the instance operand.
739 auto result = getOrComputeResults(op->getOperand(arg.getArgNumber()),
740 fanInPoint.bitPos);
741 if (failed(result))
742 return failure();
743 for (auto path : *result) {
744 auto newHistory = debugPointFactory->getEmptyList();
745 if (ctx->doTraceDebugPoints()) {
746 // Update the history to have correct instance path.
747 newHistory =
748 mapList(debugPointFactory.get(), history, [&](DebugPoint p) {
749 p.object.instancePath =
750 instancePathCache->prependInstance(op, p.object.instancePath);
751 p.delay += path.delay;
752 return p;
753 });
754 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
755 "output port");
756 newHistory = debugPointFactory->add(debugPoint, newHistory);
757 }
758
759 path.delay += delay;
760 path.history =
761 concatList(debugPointFactory.get(), newHistory, path.history);
762 results.push_back(path);
763 }
764 }
765
766 return success();
767}
768
769LogicalResult LocalVisitor::visit(comb::ConcatOp op, size_t bitPos,
770 SmallVectorImpl<OpenPath> &results) {
771 // Find the exact bit pos in the concat.
772 size_t newBitPos = bitPos;
773 for (auto operand : llvm::reverse(op.getInputs())) {
774 auto size = getBitWidth(operand);
775 if (newBitPos >= size) {
776 newBitPos -= size;
777 continue;
778 }
779 return markEquivalent(op, bitPos, operand, newBitPos, results);
780 }
781
782 llvm::report_fatal_error("Should not reach here");
783 return failure();
784}
785
786LogicalResult LocalVisitor::addLogicOp(Operation *op, size_t bitPos,
787 SmallVectorImpl<OpenPath> &results) {
788 auto size = op->getNumOperands();
789 auto cost = llvm::Log2_64_Ceil(size);
790 // Create edges each operand with cost ceil(log(size)).
791 for (auto operand : op->getOperands())
792 if (failed(addEdge(operand, bitPos, cost, results)))
793 return failure();
794
795 deduplicatePaths(results);
796 return success();
797}
798
799LogicalResult LocalVisitor::visitDefault(Operation *op, size_t bitPos,
800 SmallVectorImpl<OpenPath> &results) {
801 return success();
802}
803
804LogicalResult LocalVisitor::visit(mlir::BlockArgument arg, size_t bitPos,
805 SmallVectorImpl<OpenPath> &results) {
806 assert(arg.getOwner() == module.getBodyBlock());
807
808 // Record a debug point.
809 auto newHistory = ctx->doTraceDebugPoints()
810 ? debugPointFactory->add(
811 DebugPoint({}, arg, bitPos, 0, "input port"), {})
812 : debugPointFactory->getEmptyList();
813 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
814 results.push_back(newPoint);
815 return success();
816}
817
818FailureOr<ArrayRef<OpenPath>> LocalVisitor::getOrComputeResults(Value value,
819 size_t bitPos) {
820 if (ec.contains({value, bitPos})) {
821 auto leader = ec.findLeader({value, bitPos});
822 // If this is not the leader, then use the leader.
823 if (*leader != std::pair(value, bitPos)) {
824 return getOrComputeResults(leader->first, leader->second);
825 }
826 }
827
828 auto it = cachedResults.find({value, bitPos});
829 if (it != cachedResults.end())
830 return ArrayRef<OpenPath>(it->second);
831
832 SmallVector<OpenPath> results;
833 if (failed(visitValue(value, bitPos, results)))
834 return {};
835
836 // Unique the results.
837 deduplicatePaths(results);
838 LLVM_DEBUG({
839 llvm::dbgs() << value << "[" << bitPos << "] "
840 << "Found " << results.size() << " paths\n";
841 llvm::dbgs() << "====Paths:\n";
842 for (auto &path : results) {
843 path.print(llvm::dbgs());
844 llvm::dbgs() << "\n";
845 }
846 llvm::dbgs() << "====\n";
847 });
848
849 auto insertedResult =
850 cachedResults.try_emplace({value, bitPos}, std::move(results));
851 assert(insertedResult.second);
852 return ArrayRef<OpenPath>(insertedResult.first->second);
853}
854
855LogicalResult LocalVisitor::visitValue(Value value, size_t bitPos,
856 SmallVectorImpl<OpenPath> &results) {
857 LLVM_DEBUG({
858 llvm::dbgs() << "Visiting: ";
859 llvm::dbgs() << " " << value << "[" << bitPos << "]\n";
860 });
861
862 if (auto blockArg = dyn_cast<mlir::BlockArgument>(value))
863 return visit(blockArg, bitPos, results);
864
865 auto *op = value.getDefiningOp();
866 auto result =
867 TypeSwitch<Operation *, LogicalResult>(op)
868 .Case<comb::ConcatOp, comb::ExtractOp, comb::ReplicateOp,
869 aig::AndInverterOp, comb::AndOp, comb::OrOp, comb::MuxOp,
871 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
872 [&](auto op) {
873 size_t idx = results.size();
874 auto result = visit(op, bitPos, results);
875 if (ctx->doTraceDebugPoints())
876 if (auto name = op->template getAttrOfType<StringAttr>(
877 "sv.namehint")) {
878
879 for (auto i = idx, e = results.size(); i < e; ++i) {
880 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
881 "namehint");
882 auto newHistory = debugPointFactory->add(
883 debugPoint, results[i].history);
884 results[i].history = newHistory;
885 }
886 }
887 return result;
888 })
889 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
890 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
891 results);
892 })
893 .Default([&](auto op) { return visitDefault(op, bitPos, results); });
894 return result;
895}
896
897LogicalResult LocalVisitor::initializeAndRun(hw::InstanceOp instance) {
898 const auto *childVisitor =
899 ctx->getAndWaitLocalVisitor(instance.getReferencedModuleNameAttr());
900 // If not found, the module is blackbox so skip it.
901 if (!childVisitor)
902 return success();
903
904 // Connect dataflow from instance input ports to fanout in the child.
905 for (const auto &[object, openPaths] :
906 childVisitor->getFromInputPortToFanOut()) {
907 auto [arg, argBitPos] = object;
908 for (auto [point, delayAndHistory] : openPaths) {
909 auto [instancePath, fanOut, fanOutBitPos] = point;
910 auto [delay, history] = delayAndHistory;
911 // Prepend the instance path.
913 auto newPath = instancePathCache->prependInstance(instance, instancePath);
914 auto computedResults = getOrComputeResults(
915 instance.getOperand(arg.getArgNumber()), argBitPos);
916 if (failed(computedResults))
917 return failure();
918
919 for (auto &result : *computedResults) {
920 auto newHistory = ctx->doTraceDebugPoints()
921 ? mapList(debugPointFactory.get(), history,
922 [&](DebugPoint p) {
923 // Update the instance path to prepend
924 // the current instance.
925 p.object.instancePath = newPath;
926 p.delay += result.delay;
927 return p;
928 })
929 : debugPointFactory->getEmptyList();
930 if (auto newPort = dyn_cast<BlockArgument>(result.fanIn.value)) {
932 {newPath, fanOut, fanOutBitPos}, result.delay + delay, newHistory,
933 fromInputPortToFanOut[{newPort, result.fanIn.bitPos}]);
934 } else {
935 fanOutResults[{newPath, fanOut, fanOutBitPos}].emplace_back(
936 newPath, result.fanIn.value, result.fanIn.bitPos,
937 result.delay + delay,
938 ctx->doTraceDebugPoints() ? concatList(debugPointFactory.get(),
939 newHistory, result.history)
940 : debugPointFactory->getEmptyList());
941 }
942 }
943 }
944 }
945
946 // Pre-compute the results for the instance output ports.
947 for (auto instance : instance->getResults()) {
948 for (size_t i = 0, e = getBitWidth(instance); i < e; ++i) {
949 auto computedResults = getOrComputeResults(instance, i);
950 if (failed(computedResults))
951 return failure();
952 }
953 }
954 return success();
955}
956
957LogicalResult LocalVisitor::initializeAndRun(hw::OutputOp output) {
958 for (OpOperand &operand : output->getOpOperands()) {
959 for (size_t i = 0, e = getBitWidth(operand.get()); i < e; ++i) {
960 auto &recordOutput =
961 fromOutputPortToFanIn[{operand.getOperandNumber(), i}];
962 auto computedResults = getOrComputeResults(operand.get(), i);
963 if (failed(computedResults))
964 return failure();
965 for (const auto &result : *computedResults) {
966 putUnclosedResult(result.fanIn, result.delay, result.history,
967 recordOutput);
968 }
969 }
970 }
971 return success();
972}
973
975 LLVM_DEBUG({ ctx->notifyStart(module.getModuleNameAttr()); });
976 // Initialize the results for the block arguments.
977 for (auto blockArgument : module.getBodyBlock()->getArguments())
978 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
979 (void)getOrComputeResults(blockArgument, i);
980
981 auto walkResult = module->walk([&](Operation *op) {
982 auto result =
983 mlir::TypeSwitch<Operation *, LogicalResult>(op)
984 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
985 return markRegFanOut(op, op.getNext(), op.getReset(),
986 op.getResetValue());
987 })
988 .Case<seq::CompRegOp>([&](auto op) {
989 return markRegFanOut(op, op.getInput(), op.getReset(),
990 op.getResetValue());
991 })
992 .Case<seq::FirMemWriteOp>([&](auto op) {
993 // TODO: Add address.
994 return markRegFanOut(op.getMemory(), op.getData(), {}, {},
995 op.getEnable());
996 })
997 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
998 // TODO: Add address.
999 return markRegFanOut(op.getMemory(), op.getWriteData(), {}, {},
1000 op.getEnable());
1001 })
1002 .Case<aig::AndInverterOp, comb::AndOp, comb::OrOp, comb::XorOp,
1003 comb::MuxOp>([&](auto op) {
1004 // NOTE: Visiting and-inverter is not necessary but
1005 // useful to reduce recursion depth.
1006 for (size_t i = 0, e = getBitWidth(op); i < e; ++i)
1007 if (failed(getOrComputeResults(op, i)))
1008 return failure();
1009 return success();
1010 })
1011 .Case<hw::InstanceOp, hw::OutputOp>(
1012 [&](auto op) { return initializeAndRun(op); })
1013 .Default([](auto op) { return success(); });
1014 if (failed(result))
1015 return WalkResult::interrupt();
1016 return WalkResult::advance();
1017 });
1018
1019 {
1020 std::lock_guard<std::mutex> lock(mutex);
1021 done.store(true);
1022 cv.notify_all();
1023 }
1024 LLVM_DEBUG({ ctx->notifyEnd(module.getModuleNameAttr()); });
1025 return failure(walkResult.wasInterrupted());
1026}
1027
1028//===----------------------------------------------------------------------===//
1029// Context
1030//===----------------------------------------------------------------------===//
1031
1032const LocalVisitor *Context::getLocalVisitor(StringAttr name) const {
1033 auto *it = localVisitors.find(name);
1034 if (it == localVisitors.end())
1035 return nullptr;
1036 return it->second.get();
1037}
1038
1039const LocalVisitor *Context::getAndWaitLocalVisitor(StringAttr name) const {
1040 auto *visitor = getLocalVisitor(name);
1041 if (!visitor)
1042 return nullptr;
1043 visitor->waitUntilDone();
1044 return visitor;
1045}
1046
1047//===----------------------------------------------------------------------===//
1048// LongestPathAnalysis::Impl
1049//===----------------------------------------------------------------------===//
1050
1052 Impl(Operation *module, mlir::AnalysisManager &am,
1053 const LongestPathAnalysisOption &option);
1054 LogicalResult initializeAndRun(mlir::ModuleOp module);
1055 LogicalResult initializeAndRun(hw::HWModuleOp module);
1056
1057 // See LongestPathAnalysis.
1058 bool isAnalysisAvailable(StringAttr moduleName) const;
1059 int64_t getAverageMaxDelay(Value value) const;
1060 int64_t getMaxDelay(Value value) const;
1061 LogicalResult
1062 getResults(Value value, size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1063 circt::igraph::InstancePathCache *instancePathCache = nullptr,
1064 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory =
1065 nullptr) const;
1066
1067 template <bool elaborate>
1068 LogicalResult getClosedPaths(StringAttr moduleName,
1069 SmallVectorImpl<DataflowPath> &results) const;
1071 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const;
1073 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const;
1074
1075 llvm::ArrayRef<hw::HWModuleOp> getTopModules() const { return topModules; }
1076
1077private:
1078 LogicalResult getResultsImpl(
1079 const Object &originalObject, Value value, size_t bitPos,
1080 SmallVectorImpl<DataflowPath> &results,
1081 circt::igraph::InstancePathCache *instancePathCache,
1082 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory) const;
1083
1085 SmallVector<hw::HWModuleOp> topModules;
1086};
1087
1089 Value value, size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1090 circt::igraph::InstancePathCache *instancePathCache,
1091 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory) const {
1092 return getResultsImpl(Object({}, value, bitPos), value, bitPos, results,
1093 instancePathCache, debugPointFactory);
1094}
1095
1097 const Object &originalObject, Value value, size_t bitPos,
1098 SmallVectorImpl<DataflowPath> &results,
1099 circt::igraph::InstancePathCache *instancePathCache,
1100 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory) const {
1101 auto parentHWModule =
1102 value.getParentRegion()->getParentOfType<hw::HWModuleOp>();
1103 if (!parentHWModule)
1104 return mlir::emitError(value.getLoc())
1105 << "query value is not in a HWModuleOp";
1106 auto *localVisitor = ctx.getLocalVisitor(parentHWModule.getModuleNameAttr());
1107 if (!localVisitor)
1108 return success();
1109
1110 size_t oldIndex = results.size();
1111 auto *node =
1112 ctx.instanceGraph
1113 ? ctx.instanceGraph->lookup(parentHWModule.getModuleNameAttr())
1114 : nullptr;
1115 LLVM_DEBUG({
1116 llvm::dbgs() << "Running " << parentHWModule.getModuleNameAttr() << " "
1117 << value << " " << bitPos << "\n";
1118 });
1119
1120 for (auto &path : localVisitor->getResults(value, bitPos)) {
1121 auto arg = dyn_cast<BlockArgument>(path.fanIn.value);
1122 if (!arg || localVisitor->isTopLevel()) {
1123 // If the value is not a block argument, then we are done.
1124 results.push_back({originalObject, path, parentHWModule});
1125 continue;
1126 }
1127
1128 auto newObject = originalObject;
1129 assert(node && "If an instance graph is not available, localVisitor must "
1130 "be a toplevel");
1131 for (auto *inst : node->uses()) {
1132 auto startIndex = results.size();
1133 if (instancePathCache)
1134 newObject.instancePath = instancePathCache->appendInstance(
1135 originalObject.instancePath, inst->getInstance());
1136
1137 auto result = getResultsImpl(
1138 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1139 path.fanIn.bitPos, results, instancePathCache, debugPointFactory);
1140 if (failed(result))
1141 return result;
1142 for (auto i = startIndex, e = results.size(); i < e; ++i)
1143 results[i].setDelay(results[i].getDelay() + path.delay);
1144 }
1145 }
1146
1147 deduplicatePaths(results, oldIndex);
1148 return success();
1149}
1150
1151template <bool elaborate>
1153 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1154 auto collectClosedPaths = [&](StringAttr name,
1155 igraph::InstanceGraphNode *top = nullptr) {
1156 if (!isAnalysisAvailable(name))
1157 return;
1158 auto *visitor = ctx.getLocalVisitor(name);
1159 for (auto &[point, state] : visitor->getFanOutResults())
1160 for (const auto &dataFlow : state) {
1161 if constexpr (elaborate) {
1162 // If elaborate, we need to prepend the path to the root.
1163 auto *instancePathCache = visitor->getInstancePathCache();
1164 auto topToRoot = instancePathCache->getRelativePaths(
1165 visitor->getHWModuleOp(), top);
1166 for (auto &instancePath : topToRoot) {
1167 results.emplace_back(point, dataFlow,
1168 top->getModule<hw::HWModuleOp>());
1169 results.back().prependPaths(*visitor->getInstancePathCache(),
1170 visitor->getDebugPointFactory(),
1171 instancePath);
1172 }
1173 } else {
1174 results.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1175 }
1176 }
1177 };
1178
1179 if (ctx.instanceGraph) {
1180 // Accumulate all closed results under the given module.
1181 auto *node = ctx.instanceGraph->lookup(moduleName);
1182 for (auto *child : llvm::post_order(node))
1183 collectClosedPaths(child->getModule().getModuleNameAttr(), node);
1184 } else {
1185 collectClosedPaths(moduleName);
1186 }
1187
1188 return success();
1189}
1190
1192 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1193 auto *visitor = ctx.getLocalVisitor(moduleName);
1194 if (!visitor)
1195 return failure();
1196
1197 for (auto &[key, value] : visitor->getFromInputPortToFanOut()) {
1198 auto [arg, argBitPos] = key;
1199 for (auto [point, delayAndHistory] : value) {
1200 auto [path, start, startBitPos] = point;
1201 auto [delay, history] = delayAndHistory;
1202 results.emplace_back(Object(path, start, startBitPos),
1203 OpenPath({}, arg, argBitPos, delay, history),
1204 visitor->getHWModuleOp());
1205 }
1206 }
1207
1208 return success();
1209}
1210
1212 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1213 auto *visitor = ctx.getLocalVisitor(moduleName);
1214 if (!visitor)
1215 return failure();
1216
1217 for (auto &[key, value] : visitor->getFromOutputPortToFanIn()) {
1218 auto [resultNum, bitPos] = key;
1219 for (auto [point, delayAndHistory] : value) {
1220 auto [path, start, startBitPos] = point;
1221 auto [delay, history] = delayAndHistory;
1222 results.emplace_back(std::make_pair(resultNum, bitPos),
1223 OpenPath(path, start, startBitPos, delay, history),
1224 visitor->getHWModuleOp());
1225 }
1226 }
1227
1228 return success();
1229}
1230
1231LongestPathAnalysis::Impl::Impl(Operation *moduleOp, mlir::AnalysisManager &am,
1232 const LongestPathAnalysisOption &option)
1233 : ctx(isa<mlir::ModuleOp>(moduleOp)
1234 ? &am.getAnalysis<igraph::InstanceGraph>()
1235 : nullptr,
1236 option) {
1237 if (auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1238 if (failed(initializeAndRun(module)))
1239 llvm::report_fatal_error("Failed to run longest path analysis");
1240 } else if (auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1241 if (failed(initializeAndRun(hwMod)))
1242 llvm::report_fatal_error("Failed to run longest path analysis");
1243 } else {
1244 llvm::report_fatal_error("Analysis scheduled on invalid operation");
1245 }
1246}
1247LogicalResult
1249 auto it =
1250 ctx.localVisitors.insert({module.getModuleNameAttr(),
1251 std::make_unique<LocalVisitor>(module, &ctx)});
1252 assert(it.second);
1253 it.first->second->setTopLevel();
1254 return it.first->second->initializeAndRun();
1255}
1256
1257LogicalResult
1259 auto topNameAttr =
1260 module->getAttrOfType<FlatSymbolRefAttr>(getTopModuleNameAttrName());
1261
1262 topModules.clear();
1263 llvm::SetVector<Operation *> visited;
1264 auto *instanceGraph = ctx.instanceGraph;
1265 if (topNameAttr) {
1266 auto *topNode = instanceGraph->lookup(topNameAttr.getAttr());
1267 if (!topNode || !topNode->getModule() ||
1268 !isa<hw::HWModuleOp>(topNode->getModule())) {
1269 module.emitError() << "top module not found in instance graph "
1270 << topNameAttr;
1271 return failure();
1272 }
1273 topModules.push_back(topNode->getModule<hw::HWModuleOp>());
1274 } else {
1275 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1276 if (failed(inferredResults))
1277 return inferredResults;
1278
1279 for (auto *node : *inferredResults) {
1280 if (auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1281 topModules.push_back(top);
1282 }
1283 }
1284
1285 SmallVector<igraph::InstanceGraphNode *> worklist;
1286 for (auto topNode : topModules)
1287 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1288 // Get a set of design modules that are reachable from the top nodes,
1289 // excluding bound instances.
1290 while (!worklist.empty()) {
1291 auto *node = worklist.pop_back_val();
1292 assert(node && "node should not be null");
1293 auto op = node->getModule();
1294 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1295 continue;
1296
1297 for (auto *child : *node) {
1298 auto childOp = child->getInstance();
1299 if (!childOp || childOp->hasAttr("doNotPrint"))
1300 continue;
1301
1302 worklist.push_back(child->getTarget());
1303 }
1304 }
1305
1306 // Initialize the local visitors if the module was visited, in the
1307 // post-order of the instance graph.
1308 for (auto module : topModules) {
1309 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1310 for (auto *node : llvm::post_order(topNode))
1311 if (node && node->getModule())
1312 if (auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1313 if (visited.contains(hwMod))
1314 ctx.localVisitors.insert(
1315 {hwMod.getModuleNameAttr(),
1316 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1317 }
1318
1319 ctx.localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1320 }
1321
1322 return mlir::failableParallelForEach(
1323 module.getContext(), ctx.localVisitors,
1324 [&](auto &it) { return it.second->initializeAndRun(); });
1325}
1326
1328 StringAttr moduleName) const {
1329 return ctx.localVisitors.find(moduleName) != ctx.localVisitors.end();
1330}
1331
1332// Return the average of the maximum delays across all bits of the given
1333// value, which is useful approximation for the delay of the value. For each
1334// bit position, finds all paths and takes the maximum delay. Then averages
1335// these maximum delays across all bits of the value.
1337 SmallVector<DataflowPath> results;
1338 size_t bitWidth = getBitWidth(value);
1339 if (bitWidth == 0)
1340 return 0;
1341 int64_t totalDelay = 0;
1342 for (size_t i = 0; i < bitWidth; ++i) {
1343 // Clear results from previous iteration.
1344 results.clear();
1345 auto result = getResults(value, i, results);
1346 if (failed(result))
1347 return 0;
1348
1349 int64_t maxDelay = 0;
1350 for (auto &path : results)
1351 maxDelay = std::max(maxDelay, path.getDelay());
1352 totalDelay += maxDelay;
1353 }
1354 return llvm::divideCeil(totalDelay, bitWidth);
1355}
1356
1357int64_t LongestPathAnalysis::Impl::getMaxDelay(Value value) const {
1358 SmallVector<DataflowPath> results;
1359 size_t bitWidth = getBitWidth(value);
1360 if (bitWidth == 0)
1361 return 0;
1362 int64_t maxDelay = 0;
1363 for (size_t i = 0; i < bitWidth; ++i) {
1364 // Clear results from previous iteration.
1365 results.clear();
1366 auto result = getResults(value, i, results);
1367 if (failed(result))
1368 return 0;
1369
1370 for (auto &path : results)
1371 maxDelay = std::max(maxDelay, path.getDelay());
1372 }
1373 return maxDelay;
1374}
1375
1376//===----------------------------------------------------------------------===//
1377// LongestPathAnalysis
1378//===----------------------------------------------------------------------===//
1379
1381
1383 Operation *moduleOp, mlir::AnalysisManager &am,
1384 const LongestPathAnalysisOption &option)
1385 : impl(new Impl(moduleOp, am, option)) {}
1386
1387bool LongestPathAnalysis::isAnalysisAvailable(StringAttr moduleName) const {
1388 return impl->isAnalysisAvailable(moduleName);
1389}
1390
1392 return impl->getAverageMaxDelay(value);
1393}
1394
1395int64_t LongestPathAnalysis::getMaxDelay(Value value) const {
1396 return impl->getMaxDelay(value);
1397}
1398
1399LogicalResult
1401 SmallVectorImpl<DataflowPath> &results,
1402 bool elaboratePaths) const {
1403 if (elaboratePaths)
1404 return impl->getClosedPaths<true>(moduleName, results);
1405 return impl->getClosedPaths<false>(moduleName, results);
1406}
1407
1409 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1410 return impl->getOpenPathsFromInputPortsToInternal(moduleName, results);
1411}
1412
1414 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1415 return impl->getOpenPathsFromInternalToOutputPorts(moduleName, results);
1416}
1417
1418LogicalResult
1420 SmallVectorImpl<DataflowPath> &results,
1421 bool elaboratePaths) const {
1422 if (failed(getClosedPaths(moduleName, results, elaboratePaths)))
1423 return failure();
1424 if (failed(getOpenPathsFromInputPortsToInternal(moduleName, results)))
1425 return failure();
1426 if (failed(getOpenPathsFromInternalToOutputPorts(moduleName, results)))
1427 return failure();
1428 return success();
1429}
1430
1431ArrayRef<hw::HWModuleOp> LongestPathAnalysis::getTopModules() const {
1432 return impl->getTopModules();
1433}
assert(baseType &&"element must be base type")
static void printObjectImpl(llvm::raw_ostream &os, const Object &object, int64_t delay=-1, llvm::ImmutableList< DebugPoint > history={}, StringRef comment="")
static void deduplicatePaths(SmallVectorImpl< OpenPath > &results, size_t startIndex=0)
static llvm::ImmutableList< DebugPoint > mapList(llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, llvm::ImmutableList< DebugPoint > list, llvm::function_ref< DebugPoint(DebugPoint)> fn)
static llvm::ImmutableList< DebugPoint > concatList(llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, llvm::ImmutableList< DebugPoint > lhs, llvm::ImmutableList< DebugPoint > rhs)
static void deduplicatePathsImpl(SmallVectorImpl< T > &results, size_t startIndex, llvm::function_ref< Key(const T &)> keyFn, llvm::function_ref< int64_t(const T &)> delayFn)
static StringAttr getNameImpl(Value value)
This class provides a thread-safe interface to access the analysis results.
circt::igraph::InstanceGraph * instanceGraph
const LocalVisitor * getLocalVisitor(StringAttr name) const
void notifyEnd(StringAttr name)
bool doTraceDebugPoints() const
const LongestPathAnalysisOption & option
llvm::sys::SmartMutex< true > mutex
llvm::MapVector< StringAttr, std::unique_ptr< LocalVisitor > > localVisitors
Context(igraph::InstanceGraph *instanceGraph, const LongestPathAnalysisOption &option)
llvm::SetVector< StringAttr > running
const LocalVisitor * getAndWaitLocalVisitor(StringAttr name) const
void notifyStart(StringAttr name)
hw::HWModuleOp getHWModuleOp() const
LogicalResult markRegFanOut(Value fanOut, Value start, Value reset={}, Value resetValue={}, Value enable={})
const auto & getFanOutResults() const
const auto & getFromInputPortToFanOut() const
LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay, SmallVectorImpl< OpenPath > &results)
LogicalResult visitValue(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
ArrayRef< OpenPath > getResults(Value value, size_t bitPos) const
LogicalResult addLogicOp(Operation *op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::unique_ptr< llvm::ImmutableListFactory< DebugPoint > > debugPointFactory
DenseMap< std::pair< Value, size_t >, std::pair< Value, size_t > > ecMap
LogicalResult visitDefault(Operation *op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
llvm::MapVector< Object, std::pair< int64_t, llvm::ImmutableList< DebugPoint > > > ObjectToMaxDistance
DenseMap< std::pair< Value, size_t >, SmallVector< OpenPath > > cachedResults
std::pair< Value, size_t > findLeader(Value value, size_t bitpos) const
llvm::ImmutableListFactory< DebugPoint > * getDebugPointFactory() const
LogicalResult visit(seq::FirMemReadOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to, size_t toBitPos, SmallVectorImpl< OpenPath > &results)
llvm::MapVector< std::pair< BlockArgument, size_t >, ObjectToMaxDistance > fromInputPortToFanOut
FailureOr< ArrayRef< OpenPath > > getOrComputeResults(Value value, size_t bitPos)
std::atomic_bool done
hw::HWModuleOp Context * ctx
DenseMap< Object, SmallVector< OpenPath > > fanOutResults
llvm::MapVector< std::tuple< size_t, size_t >, ObjectToMaxDistance > fromOutputPortToFanIn
LogicalResult visit(seq::CompRegOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markFanIn(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult visit(seq::FirRegOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult initializeAndRun()
void getClosedPaths(SmallVectorImpl< DataflowPath > &results) const
llvm::EquivalenceClasses< std::pair< Value, size_t > > ec
bool isTopLevel() const
LogicalResult visit(seq::FirMemReadWriteOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult visit(mlir::BlockArgument argument, size_t bitPos, SmallVectorImpl< OpenPath > &results)
const auto & getFromOutputPortToFanIn() const
LogicalResult visit(hw::ConstantOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::condition_variable cv
void putUnclosedResult(const Object &object, int64_t delay, llvm::ImmutableList< DebugPoint > history, ObjectToMaxDistance &objectToMaxDistance)
std::unique_ptr< circt::igraph::InstancePathCache > instancePathCache
circt::igraph::InstancePathCache * getInstancePathCache() const
LocalVisitor(hw::HWModuleOp module, Context *ctx)
void waitUntilDone() const
DataflowPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
void printFanOut(llvm::raw_ostream &os)
void print(llvm::raw_ostream &os)
LogicalResult getResults(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results) const
LogicalResult getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results, bool elaboratePaths=false) const
int64_t getMaxDelay(Value value) const
int64_t getAverageMaxDelay(Value value) const
LogicalResult getAllPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results, bool elaboratePaths=false) const
LongestPathAnalysis(Operation *moduleOp, mlir::AnalysisManager &am, const LongestPathAnalysisOption &option={})
LogicalResult getOpenPathsFromInternalToOutputPorts(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
bool isAnalysisAvailable(StringAttr moduleName) const
LogicalResult getOpenPathsFromInputPortsToInternal(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
HW-specific instance graph with a virtual entry node linking to all publicly visible modules.
This is a Node in the InstanceGraph.
This graph tracks modules and where they are instantiated.
InstanceGraphNode * lookup(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
An instance path composed of a series of instances.
Impl(int port)
Start a server on the given port. -1 means to let the OS pick a port.
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
Definition HWTypes.cpp:110
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
LogicalResult getOpenPathsFromInputPortsToInternal(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
LogicalResult getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
LogicalResult initializeAndRun(mlir::ModuleOp module)
bool isAnalysisAvailable(StringAttr moduleName) const
LogicalResult getResults(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results, circt::igraph::InstancePathCache *instancePathCache=nullptr, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory=nullptr) const
LogicalResult getOpenPathsFromInternalToOutputPorts(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
LogicalResult getResultsImpl(const Object &originalObject, Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results, circt::igraph::InstancePathCache *instancePathCache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory) const
void print(llvm::raw_ostream &os) const
circt::igraph::InstancePath instancePath
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
void print(llvm::raw_ostream &os) const
void print(llvm::raw_ostream &os) const
OpenPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
llvm::ImmutableList< DebugPoint > history
A data structure that caches and provides paths to module instances in the IR.
ArrayRef< InstancePath > getRelativePaths(ModuleOpInterface op, InstanceGraphNode *node)
InstancePath appendInstance(InstancePath path, InstanceOpInterface inst)
Append an instance to a path.
InstancePath concatPath(InstancePath path1, InstancePath path2)
Concatenate two paths.