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