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