CIRCT 22.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
40#include "circt/Support/LLVM.h"
41#include "mlir/IR/BuiltinAttributes.h"
42#include "mlir/IR/BuiltinOps.h"
43#include "mlir/IR/Diagnostics.h"
44#include "mlir/IR/Operation.h"
45#include "mlir/IR/Threading.h"
46#include "mlir/IR/Value.h"
47#include "mlir/IR/Visitors.h"
48#include "mlir/Pass/AnalysisManager.h"
49#include "mlir/Pass/PassManager.h"
50#include "mlir/Pass/PassRegistry.h"
51#include "mlir/Support/FileUtilities.h"
52#include "mlir/Support/LLVM.h"
53#include "llvm/ADT//MapVector.h"
54#include "llvm/ADT/ArrayRef.h"
55#include "llvm/ADT/DenseMapInfoVariant.h"
56#include "llvm/ADT/EquivalenceClasses.h"
57#include "llvm/ADT/ImmutableList.h"
58#include "llvm/ADT/MapVector.h"
59#include "llvm/ADT/PostOrderIterator.h"
60#include "llvm/ADT/STLExtras.h"
61#include "llvm/ADT/SmallVector.h"
62#include "llvm/ADT/StringRef.h"
63#include "llvm/Support/Debug.h"
64#include "llvm/Support/ErrorHandling.h"
65#include "llvm/Support/JSON.h"
66#include "llvm/Support/LogicalResult.h"
67#include "llvm/Support/MathExtras.h"
68#include "llvm/Support/Mutex.h"
69#include "llvm/Support/raw_ostream.h"
70#include <condition_variable>
71#include <cstddef>
72#include <cstdint>
73#include <memory>
74#include <mutex>
75
76#define DEBUG_TYPE "aig-longest-path-analysis"
77using namespace circt;
78using namespace synth;
79
80static size_t getBitWidth(Value value) {
81 if (auto vecType = dyn_cast<seq::ClockType>(value.getType()))
82 return 1;
83 if (auto memory = dyn_cast<seq::FirMemType>(value.getType()))
84 return memory.getWidth();
85 return hw::getBitWidth(value.getType());
86}
87
88template <typename T, typename Key>
89static void
90deduplicatePathsImpl(SmallVectorImpl<T> &results, size_t startIndex,
91 llvm::function_ref<Key(const T &)> keyFn,
92 llvm::function_ref<int64_t(const T &)> delayFn) {
93 // Take only maximum for each path destination.
94 DenseMap<Key, size_t> keyToIndex;
95 for (size_t i = startIndex; i < results.size(); ++i) {
96 auto &path = results[i];
97 auto key = keyFn(path);
98 auto delay = delayFn(path);
99 auto it = keyToIndex.find(key);
100 if (it == keyToIndex.end()) {
101 // Insert a new entry.
102 size_t newIndex = keyToIndex.size() + startIndex;
103 keyToIndex[key] = newIndex;
104 results[newIndex] = std::move(results[i]);
105 continue;
106 }
107 if (delay > delayFn(results[it->second]))
108 results[it->second] = std::move(results[i]);
109 }
110
111 results.resize(keyToIndex.size() + startIndex);
112}
113
114// Filter and optimize OpenPaths based on analysis configuration.
115static void filterPaths(SmallVectorImpl<OpenPath> &results,
116 bool keepOnlyMaxDelay, bool isLocalScope) {
117 if (results.empty())
118 return;
119
120 // Fast path for local scope with max-delay filtering:
121 // Simply find and keep only the single longest delay path
122 if (keepOnlyMaxDelay && isLocalScope) {
123 OpenPath maxDelay;
124 maxDelay.delay = -1; // Initialize to invalid delay
125
126 // Find the path with maximum delay
127 for (auto &path : results) {
128 if (path.delay > maxDelay.delay)
129 maxDelay = path;
130 }
131
132 // Replace all paths with just the maximum delay path
133 results.clear();
134 if (maxDelay.delay >= 0) // Only add if we found a valid path
135 results.push_back(maxDelay);
136 return;
137 }
138
139 // Remove paths with identical start point, keeping only the longest delay
140 // path for each unique points.
141 deduplicatePathsImpl<OpenPath, Object>(
142 results, 0, [](const auto &path) { return path.startPoint; },
143 [](const auto &path) { return path.delay; });
144
145 // Global scope max-delay filtering:
146 // Keep all module input ports (BlockArguments) but only the single
147 // longest internal path to preserve boundary information
148 if (keepOnlyMaxDelay) {
149 assert(!isLocalScope);
150 size_t writeIndex = 0;
151 OpenPath maxDelay;
152 maxDelay.delay = -1; // Initialize to invalid delay
153
154 for (size_t i = 0; i < results.size(); ++i) {
155 // Preserve all module input port paths (BlockArguments) since the input
156 // port might be the critical path.
157 if (isa<BlockArgument>(results[i].getStartPoint().value)) {
158 // Keep all module input port paths, as inputs themselves may be
159 // critical
160 results[writeIndex++] = results[i];
161 } else {
162 // For internal paths, track only the maximum delay path
163 if (results[i].delay > maxDelay.delay)
164 maxDelay = results[i];
165 }
166 }
167
168 // Resize to remove processed internal paths, then add the max delay path
169 results.resize(writeIndex);
170 if (maxDelay.delay >= 0) // Only add if we found a valid internal path
171 results.push_back(maxDelay);
172 }
173}
174
175static void filterPaths(SmallVectorImpl<DataflowPath> &results,
176 size_t startIndex = 0) {
178 std::pair<DataflowPath::EndPointType, Object>>(
179 results, startIndex,
180 [](const DataflowPath &path) {
181 return std::pair(path.getEndPoint(), path.getStartPoint());
182 },
183 [](const DataflowPath &path) { return path.getDelay(); });
184}
185
186static llvm::ImmutableList<DebugPoint>
187mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
188 llvm::ImmutableList<DebugPoint> list,
189 llvm::function_ref<DebugPoint(DebugPoint)> fn) {
190 if (list.isEmpty())
191 return list;
192 auto &head = list.getHead();
193 return debugPointFactory->add(fn(head),
194 mapList(debugPointFactory, list.getTail(), fn));
195}
196
197static llvm::ImmutableList<DebugPoint>
198concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
199 llvm::ImmutableList<DebugPoint> lhs,
200 llvm::ImmutableList<DebugPoint> rhs) {
201 if (lhs.isEmpty())
202 return rhs;
203 return debugPointFactory->add(
204 lhs.getHead(), concatList(debugPointFactory, lhs.getTail(), rhs));
205}
206
207static StringAttr getNameImpl(Value value) {
208 if (auto arg = dyn_cast<BlockArgument>(value)) {
209 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
210 if (!op) {
211 // TODO: Handle other operations.
212 return StringAttr::get(value.getContext(), "<unknown-argument>");
213 }
214 return op.getArgName(arg.getArgNumber());
215 }
216 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
217 .Case<seq::CompRegOp, seq::FirRegOp>(
218 [](auto op) { return op.getNameAttr(); })
219 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
220 SmallString<16> str;
221 str += op.getInstanceName();
222 str += ".";
223 str += cast<StringAttr>(
224 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
225 return StringAttr::get(op.getContext(), str);
226 })
227 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
228 llvm::SmallString<16> str;
229 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
230 str += ".read_port";
231 return StringAttr::get(value.getContext(), str);
232 })
233 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
234 llvm::SmallString<16> str;
235 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
236 str += ".rw_port";
237 return StringAttr::get(value.getContext(), str);
238 })
239 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
240 llvm::SmallString<16> str;
241 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
242 str += ".write_port";
243 return StringAttr::get(value.getContext(), str);
244 })
245 .Default([&](auto op) {
246 if (auto name = op->template getAttrOfType<StringAttr>("sv.namehint"))
247 return name;
248 llvm::errs() << "Unknown op: " << *op << "\n";
249 return StringAttr::get(value.getContext(), "");
250 });
251}
252
253static void printObjectImpl(llvm::raw_ostream &os, const Object &object,
254 int64_t delay = -1,
255 llvm::ImmutableList<DebugPoint> history = {},
256 StringRef comment = "") {
257 std::string pathString;
258 llvm::raw_string_ostream osPath(pathString);
259 object.instancePath.print(osPath);
260 os << "Object(" << pathString << "." << object.getName().getValue() << "["
261 << object.bitPos << "]";
262 if (delay != -1)
263 os << ", delay=" << delay;
264 if (!history.isEmpty()) {
265 os << ", history=[";
266 llvm::interleaveComma(history, os, [&](DebugPoint p) { p.print(os); });
267 os << "]";
268 }
269 if (!comment.empty())
270 os << ", comment=\"" << comment << "\"";
271 os << ")";
272}
273
274template <typename T>
275static int64_t getMaxDelayInPaths(ArrayRef<T> paths) {
276 int64_t maxDelay = 0;
277 for (auto &path : paths)
278 maxDelay = std::max(maxDelay, path.getDelay());
279 return maxDelay;
280}
281
282using namespace circt;
283using namespace aig;
284
285//===----------------------------------------------------------------------===//
286// Printing
287//===----------------------------------------------------------------------===//
288
289void OpenPath::print(llvm::raw_ostream &os) const {
290 printObjectImpl(os, startPoint, delay, history);
291}
292
293void DebugPoint::print(llvm::raw_ostream &os) const {
294 printObjectImpl(os, object, delay, {}, comment);
295}
296
297void Object::print(llvm::raw_ostream &os) const { printObjectImpl(os, *this); }
298
299StringAttr Object::getName() const { return getNameImpl(value); }
300
301void DataflowPath::printEndPoint(llvm::raw_ostream &os) {
302 if (auto *object = std::get_if<Object>(&endPoint)) {
303 object->print(os);
304 } else {
305 auto &[module, resultNumber, bitPos] =
306 *std::get_if<DataflowPath::OutputPort>(&endPoint);
307 auto outputPortName = root.getOutputName(resultNumber);
308 os << "Object($root." << outputPortName << "[" << bitPos << "])";
309 }
310}
311
312void DataflowPath::print(llvm::raw_ostream &os) {
313 os << "root=" << root.getModuleName() << ", ";
314 os << "endPoint=";
315 printEndPoint(os);
316 os << ", ";
317 os << "startPoint=";
318 path.print(os);
319}
320
321//===----------------------------------------------------------------------===//
322// OpenPath
323//===----------------------------------------------------------------------===//
324
327 instancePath = cache.concatPath(path, instancePath);
328 return *this;
329}
330
333 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
335 startPoint.prependPaths(cache, path);
336 if (debugPointFactory)
337 this->history = mapList(debugPointFactory, this->history,
338 [&](DebugPoint p) -> DebugPoint {
339 p.object.prependPaths(cache, path);
340 return p;
341 });
342 return *this;
343}
344
345//===----------------------------------------------------------------------===//
346// DataflowPath
347//===----------------------------------------------------------------------===//
348
351 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
353 this->path.prependPaths(cache, debugPointFactory, path);
354 if (!path.empty()) {
355 auto root = path.top()->getParentOfType<hw::HWModuleOp>();
356 assert(root && "root is not a hw::HWModuleOp");
357 this->root = root;
358 }
359
360 // If the end point is an object, prepend the path.
361 if (auto *object = std::get_if<Object>(&endPoint))
362 object->prependPaths(cache, path);
363
364 return *this;
365}
366
368 // If the end point is an object, return the location of the object.
369 if (auto *object = std::get_if<Object>(&endPoint))
370 return object->value.getLoc();
371
372 // Return output port location.
373 auto &[module, resultNumber, bitPos] =
374 *std::get_if<DataflowPath::OutputPort>(&endPoint);
375 return module.getOutputLoc(resultNumber);
376}
377
378//===----------------------------------------------------------------------===//
379// JSON serialization
380//===----------------------------------------------------------------------===//
381
382static llvm::json::Value toJSON(const circt::igraph::InstancePath &path) {
383 llvm::json::Array result;
384 for (auto op : path) {
385 llvm::json::Object obj;
386 obj["instance_name"] = op.getInstanceName();
387 obj["module_name"] = op.getReferencedModuleNames()[0];
388 result.push_back(std::move(obj));
389 }
390 return result;
391}
392
393static llvm::json::Value toJSON(const circt::synth::Object &object) {
394 return llvm::json::Object{
395 {"instance_path", toJSON(object.instancePath)},
396 {"name", object.getName().getValue()},
397 {"bit_pos", object.bitPos},
398 };
399}
400
401static llvm::json::Value toJSON(const DataflowPath::EndPointType &path,
402 hw::HWModuleOp root) {
403 using namespace llvm::json;
404 if (auto *object = std::get_if<circt::synth::Object>(&path))
405 return toJSON(*object);
406
407 auto &[module, resultNumber, bitPos] =
408 *std::get_if<DataflowPath::OutputPort>(&path);
409 return llvm::json::Object{
410 {"instance_path", {}}, // Instance path is empty for output ports.
411 {"name", root.getOutputName(resultNumber)},
412 {"bit_pos", bitPos},
413 };
414}
415
416static llvm::json::Value toJSON(const DebugPoint &point) {
417 return llvm::json::Object{
418 {"object", toJSON(point.object)},
419 {"delay", point.delay},
420 {"comment", point.comment},
421 };
422}
423
424static llvm::json::Value toJSON(const OpenPath &path) {
425 llvm::json::Array history;
426 for (auto &point : path.history)
427 history.push_back(toJSON(point));
428 return llvm::json::Object{{"start_point", toJSON(path.startPoint)},
429 {"delay", path.delay},
430 {"history", std::move(history)}};
431}
432
433llvm::json::Value circt::synth::toJSON(const DataflowPath &path) {
434 return llvm::json::Object{
435 {"end_point", ::toJSON(path.getEndPoint(), path.getRoot())},
436 {"path", ::toJSON(path.getPath())},
437 {"root", path.getRoot().getModuleName()},
438 };
439}
440
441class LocalVisitor;
442
443//===----------------------------------------------------------------------===//
444// Context
445//===----------------------------------------------------------------------===//
446/// This class provides a thread-safe interface to access the analysis results.
447
448class Context {
449public:
451 const LongestPathAnalysisOptions &option)
452 : instanceGraph(instanceGraph), option(option) {}
453 void notifyStart(StringAttr name) {
454 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
455 running.insert(name);
456 llvm::dbgs() << "[Timing] " << name << " started. running=[";
457 for (auto &name : running)
458 llvm::dbgs() << name << " ";
459 llvm::dbgs() << "]\n";
460 }
461
462 void notifyEnd(StringAttr name) {
463 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
464 running.remove(name);
465
466 llvm::dbgs() << "[Timing] " << name << " finished. running=[";
467 for (auto &name : running)
468 llvm::dbgs() << name << " ";
469 llvm::dbgs() << "]\n";
470 }
471
472 // Lookup a local visitor for `name`.
473 const LocalVisitor *getLocalVisitor(StringAttr name) const;
474
475 // Lookup a mutable local visitor for `name`.
476 LocalVisitor *getLocalVisitorMutable(StringAttr name) const;
477
478 // A map from the module name to the local visitor.
479 llvm::MapVector<StringAttr, std::unique_ptr<LocalVisitor>> localVisitors;
480
481 // This is non-null only if `module` is a ModuleOp.
482 circt::igraph::InstanceGraph *instanceGraph = nullptr;
483
484 bool doTraceDebugPoints() const { return option.collectDebugInfo; }
485 bool doLazyComputation() const { return option.lazyComputation; }
486 bool doKeepOnlyMaxDelayPaths() const { return option.keepOnlyMaxDelayPaths; }
487 bool isLocalScope() const { return instanceGraph == nullptr; }
488 StringAttr getTopModuleName() const { return option.topModuleName; }
489
490private:
491 bool isRunningParallel() const { return !doLazyComputation(); }
492 llvm::sys::SmartMutex<true> mutex;
493 llvm::SetVector<StringAttr> running;
494 LongestPathAnalysisOptions option;
495};
496
497//===----------------------------------------------------------------------===//
498// OperationAnalyzer
499//===----------------------------------------------------------------------===//
500
501// OperationAnalyzer handles timing analysis for individual operations that
502// haven't been converted to AIG yet. It creates isolated modules for each
503// unique operation type/signature combination, runs the conversion pipeline
504// (HW -> Comb -> AIG), and analyzes the resulting AIG representation.
505//
506// This is used as a fallback when the main analysis encounters operations
507// that don't have direct AIG equivalents. The analyzer:
508// 1. Creates a wrapper HW module for the operation
509// 2. Runs the standard conversion pipeline to lower it to AIG
510// 3. Analyzes the resulting AIG to compute timing paths
511// 4. Caches results based on operation name and function signature
513public:
514 // Constructor creates a new analyzer with an empty module for building
515 // temporary operation wrappers.
516 // The analyzer needs its own Context separate from the main analysis
517 // to avoid using onlyMaxDelay mode, as we require precise input
518 // dependency information for accurate delay propagation
519 OperationAnalyzer(Location loc)
520 : ctx(nullptr, LongestPathAnalysisOptions(false, true, false)), loc(loc) {
521 mlir::OpBuilder builder(loc->getContext());
522 moduleOp = builder.create<mlir::ModuleOp>(loc);
523 emptyName = StringAttr::get(loc->getContext(), "");
524 }
525
526 // Initialize the pass pipeline used to lower operations to AIG.
527 // This sets up the standard conversion sequence: HW -> Comb -> AIG -> cleanup
528 LogicalResult initializePipeline();
529
530 // Analyze timing paths for a specific operation result and bit position.
531 // Creates a wrapper module if needed, runs conversion, and returns timing
532 // information as input dependencies.
533 // Results are tuples of (input operand index, bit position in operand, delay)
534 LogicalResult analyzeOperation(
535 OpResult value, size_t bitPos,
536 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results);
537
538private:
539 // Get or create a LocalVisitor for analyzing the given operation.
540 // Uses caching based on operation name and function signature to avoid
541 // recomputing analysis for identical operations.
542 FailureOr<LocalVisitor *> getOrComputeLocalVisitor(Operation *op);
543
544 // Extract the function signature (input/output types) from an operation.
545 // This is used as part of the cache key to distinguish operations with
546 // different type signatures.
547 static mlir::FunctionType getFunctionTypeForOp(Operation *op);
548
549 // Cache mapping (operation_name, function_type) -> analyzed LocalVisitor
550 // This avoids recomputing analysis for operations with identical signatures
551 llvm::DenseMap<std::pair<mlir::OperationName, mlir::FunctionType>,
552 std::unique_ptr<LocalVisitor>>
554
555 // Standard conversion pipeline: HW -> Comb -> AIG -> cleanup passes
556 // This pipeline is applied to wrapper modules to prepare them for analysis
557 constexpr static StringRef pipelineStr =
558 "hw.module(hw-aggregate-to-comb,convert-comb-to-synth,cse,canonicalize)";
559 std::unique_ptr<mlir::PassManager> passManager;
560
561 // Temporary module used to hold wrapper modules during analysis
562 // Each operation gets its own wrapper module created inside this parent
564
565 Context ctx; // Analysis context and configuration
566 Location loc; // Source location for error reporting
567 StringAttr emptyName;
568};
569
570mlir::FunctionType OperationAnalyzer::getFunctionTypeForOp(Operation *op) {
571 return mlir::FunctionType::get(op->getContext(), op->getOperandTypes(),
572 op->getResultTypes());
573}
574
575// -----------------------------------------------------------------------------
576// LocalVisitor
577// -----------------------------------------------------------------------------
578
580public:
581 LocalVisitor(hw::HWModuleOp module, Context *ctx);
582 LogicalResult initializeAndRun();
583 // Wait until the thread is done.
584 void waitUntilDone() const;
585
586 // Get the longest paths for the given value and bit position.
587 // If the result is not cached, compute it and cache it.
588 FailureOr<ArrayRef<OpenPath>> getOrComputePaths(Value value, size_t bitPos);
589
590 // Get the longest paths for the given value and bit position. This returns
591 // an empty array if not pre-computed.
592 ArrayRef<OpenPath> getCachedPaths(Value value, size_t bitPos) const;
593
594 // A map from the object to the maximum distance and history.
596 llvm::MapVector<Object,
597 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
598
599 void getClosedPaths(SmallVectorImpl<DataflowPath> &results) const;
600 void setTopLevel() { this->topLevel = true; }
601 bool isTopLevel() const { return topLevel; }
602 hw::HWModuleOp getHWModuleOp() const { return module; }
603
604 const auto &getFromInputPortToEndPoint() const {
605 return fromInputPortToEndPoint;
606 }
607 const auto &getFromOutputPortToStartPoint() const {
608 return fromOutputPortToStartPoint;
609 }
610 const auto &getEndPointResults() const { return endPointResults; }
611
613 return instancePathCache.get();
614 }
615
616 llvm::ImmutableListFactory<DebugPoint> *getDebugPointFactory() const {
617 return debugPointFactory.get();
618 }
619
620private:
621 void putUnclosedResult(const Object &object, int64_t delay,
622 llvm::ImmutableList<DebugPoint> history,
623 ObjectToMaxDistance &objectToMaxDistance);
624
625 // A map from the input port to the farthest end point.
626 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
628
629 // A map from the output port to the farthest start point.
630 llvm::MapVector<std::tuple<size_t, size_t>, ObjectToMaxDistance>
632
633 LogicalResult initializeAndRun(hw::InstanceOp instance);
634 LogicalResult initializeAndRun(hw::OutputOp output);
635
636 // --------------------------------------------------------------------------
637 // Visitors
638 // --------------------------------------------------------------------------
639 LogicalResult visitValue(Value value, size_t bitPos,
640 SmallVectorImpl<OpenPath> &results);
641 // Module boundary.
642 LogicalResult visit(mlir::BlockArgument argument, size_t bitPos,
643 SmallVectorImpl<OpenPath> &results);
644 LogicalResult visit(hw::InstanceOp op, size_t bitPos, size_t resultNum,
645 SmallVectorImpl<OpenPath> &results);
646
647 // Data-movement ops.
648 LogicalResult visit(hw::WireOp op, size_t bitPos,
649 SmallVectorImpl<OpenPath> &results);
650 LogicalResult visit(comb::ConcatOp op, size_t bitPos,
651 SmallVectorImpl<OpenPath> &results);
652 LogicalResult visit(comb::ExtractOp op, size_t bitPos,
653 SmallVectorImpl<OpenPath> &results);
654 LogicalResult visit(comb::ReplicateOp op, size_t bitPos,
655 SmallVectorImpl<OpenPath> &results);
656 // Track equivalence classes for data movement ops
657 // Treat output as equivalent to input for pure data movement operations
658 llvm::EquivalenceClasses<std::pair<Value, size_t>> ec;
659 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>> ecMap;
660 std::pair<Value, size_t> findLeader(Value value, size_t bitpos) const {
661 return ec.getLeaderValue({value, bitpos});
662 }
663 LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to,
664 size_t toBitPos,
665 SmallVectorImpl<OpenPath> &results);
666
667 // Bit-logical ops.
668 LogicalResult visit(aig::AndInverterOp op, size_t bitPos,
669 SmallVectorImpl<OpenPath> &results);
670 LogicalResult visit(mig::MajorityInverterOp op, size_t bitPos,
671 SmallVectorImpl<OpenPath> &results);
672 LogicalResult visit(comb::AndOp op, size_t bitPos,
673 SmallVectorImpl<OpenPath> &results);
674 LogicalResult visit(comb::XorOp op, size_t bitPos,
675 SmallVectorImpl<OpenPath> &results);
676 LogicalResult visit(comb::OrOp op, size_t bitPos,
677 SmallVectorImpl<OpenPath> &results);
678 LogicalResult visit(comb::MuxOp op, size_t bitPos,
679 SmallVectorImpl<OpenPath> &results);
680 LogicalResult addLogicOp(Operation *op, size_t bitPos,
681 SmallVectorImpl<OpenPath> &results);
682 LogicalResult visit(comb::TruthTableOp op, size_t bitPos,
683 SmallVectorImpl<OpenPath> &results);
684
685 // Constants.
686 LogicalResult visit(hw::ConstantOp op, size_t bitPos,
687 SmallVectorImpl<OpenPath> &results) {
688 return success();
689 }
690
691 // Registers are start point.
692 LogicalResult visit(seq::FirRegOp op, size_t bitPos,
693 SmallVectorImpl<OpenPath> &results) {
694 return markStartPoint(op, bitPos, results);
695 }
696
697 LogicalResult visit(seq::CompRegOp op, size_t bitPos,
698 SmallVectorImpl<OpenPath> &results) {
699 return markStartPoint(op, bitPos, results);
700 }
701
702 LogicalResult visit(seq::FirMemReadOp op, size_t bitPos,
703 SmallVectorImpl<OpenPath> &results) {
704 return markStartPoint(op, bitPos, results);
705 }
706
707 LogicalResult visit(seq::FirMemReadWriteOp op, size_t bitPos,
708 SmallVectorImpl<OpenPath> &results) {
709 return markStartPoint(op, bitPos, results);
710 }
711
712 LogicalResult visitDefault(OpResult result, size_t bitPos,
713 SmallVectorImpl<OpenPath> &results);
714
715 // Helper functions.
716 LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay,
717 SmallVectorImpl<OpenPath> &results);
718 LogicalResult markStartPoint(Value value, size_t bitPos,
719 SmallVectorImpl<OpenPath> &results);
720 LogicalResult markRegEndPoint(Value endPoint, Value start, Value reset = {},
721 Value resetValue = {}, Value enable = {});
722
723 // The module we are visiting.
724 hw::HWModuleOp module;
726
727 // Thread-local data structures.
728 std::unique_ptr<circt::igraph::InstancePathCache> instancePathCache;
729 // TODO: Make debug points optional.
730 std::unique_ptr<llvm::ImmutableListFactory<DebugPoint>> debugPointFactory;
731
732 // A map from the value point to the longest paths.
733 DenseMap<std::pair<Value, size_t>, SmallVector<OpenPath>> cachedResults;
734
735 // A map from the object to the longest paths.
736 DenseMap<Object, SmallVector<OpenPath>> endPointResults;
737
738 // The operation analyzer for comb/hw operations remaining in the circuit.
739 std::unique_ptr<OperationAnalyzer> operationAnalyzer;
740
741 // This is set to true when the thread is done.
742 std::atomic_bool done;
743 mutable std::condition_variable cv;
744 mutable std::mutex mutex;
745
746 // A flag to indicate the module is top-level.
747 bool topLevel = false;
748};
749
751 : module(module), ctx(ctx) {
753 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
754 instancePathCache = ctx->instanceGraph
755 ? std::make_unique<circt::igraph::InstancePathCache>(
756 *ctx->instanceGraph)
757 : nullptr;
758 operationAnalyzer = std::make_unique<OperationAnalyzer>(module->getLoc());
759
760 done = false;
761}
762
763ArrayRef<OpenPath> LocalVisitor::getCachedPaths(Value value,
764 size_t bitPos) const {
765 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
766 auto leader = ec.findLeader(valueAndBitPos);
767 if (leader != ec.member_end()) {
768 if (*leader != valueAndBitPos) {
769 // If this is not the leader, then use the leader.
770 return getCachedPaths(leader->first, leader->second);
771 }
772 }
773
774 auto it = cachedResults.find(valueAndBitPos);
775 // If not found, then consider it to be a constant.
776 if (it == cachedResults.end())
777 return {};
778 return it->second;
779}
780
781void LocalVisitor::putUnclosedResult(const Object &object, int64_t delay,
782 llvm::ImmutableList<DebugPoint> history,
783 ObjectToMaxDistance &objectToMaxDistance) {
784 auto &slot = objectToMaxDistance[object];
785 if (slot.first >= delay && delay != 0)
786 return;
787 slot = {delay, history};
788}
789
791 // Wait for the thread to finish.
792 std::unique_lock<std::mutex> lock(mutex);
793 cv.wait(lock, [this] { return done.load(); });
794}
795
796LogicalResult LocalVisitor::markRegEndPoint(Value endPoint, Value start,
797 Value reset, Value resetValue,
798 Value enable) {
799 auto bitWidth = getBitWidth(endPoint);
800 auto record = [&](size_t endPointBitPos, Value value, size_t bitPos) {
801 auto result = getOrComputePaths(value, bitPos);
802 if (failed(result))
803 return failure();
804 for (auto &path : *result) {
805 if (auto blockArg = dyn_cast<BlockArgument>(path.startPoint.value)) {
806 // Not closed.
808 {{}, endPoint, endPointBitPos}, path.delay, path.history,
809 fromInputPortToEndPoint[{blockArg, path.startPoint.bitPos}]);
810 } else {
811 // If the start point is not a port, record to the results.
812 endPointResults[{{}, endPoint, endPointBitPos}].push_back(path);
813 }
814 }
815 return success();
816 };
817
818 // Get paths for each bit, and record them.
819 for (size_t i = 0, e = bitWidth; i < e; ++i) {
820 if (failed(record(i, start, i)))
821 return failure();
822 }
823
824 // Edge from a reg to reset/resetValue.
825 if (reset)
826 for (size_t i = 0, e = bitWidth; i < e; ++i) {
827 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
828 return failure();
829 }
830
831 // Edge from a reg to enable signal.
832 if (enable)
833 for (size_t i = 0, e = bitWidth; i < e; ++i) {
834 if (failed(record(i, enable, 0)))
835 return failure();
836 }
837
838 return success();
839}
840
841LogicalResult LocalVisitor::markEquivalent(Value from, size_t fromBitPos,
842 Value to, size_t toBitPos,
843 SmallVectorImpl<OpenPath> &results) {
844 [[maybe_unused]] auto leader = ec.getOrInsertLeaderValue({to, toBitPos});
845 // Merge classes, and visit the leader.
846 [[maybe_unused]] auto newLeader =
847 ec.unionSets({to, toBitPos}, {from, fromBitPos});
848 assert(leader == *newLeader);
849 return visitValue(to, toBitPos, results);
850}
851
852LogicalResult LocalVisitor::addEdge(Value to, size_t bitPos, int64_t delay,
853 SmallVectorImpl<OpenPath> &results) {
854 auto result = getOrComputePaths(to, bitPos);
855 if (failed(result))
856 return failure();
857 for (auto &path : *result) {
858 auto newPath = path;
859 newPath.delay += delay;
860 results.push_back(newPath);
861 }
862 return success();
863}
864
865LogicalResult LocalVisitor::visit(aig::AndInverterOp op, size_t bitPos,
866 SmallVectorImpl<OpenPath> &results) {
867
868 return addLogicOp(op, bitPos, results);
869}
870
871LogicalResult LocalVisitor::visit(mig::MajorityInverterOp op, size_t bitPos,
872 SmallVectorImpl<OpenPath> &results) {
873 // Use a 3-input majority inverter as the basic unit.
874 // An n-input majority inverter requires n/2 stages of 3-input gates.
875 size_t depth = op.getInputs().size() / 2;
876 for (auto input : op.getInputs()) {
877 if (failed(addEdge(input, bitPos, depth, results)))
878 return failure();
879 }
880 return success();
881}
882
883LogicalResult LocalVisitor::visit(comb::AndOp op, size_t bitPos,
884 SmallVectorImpl<OpenPath> &results) {
885 return addLogicOp(op, bitPos, results);
886}
887
888LogicalResult LocalVisitor::visit(comb::OrOp op, size_t bitPos,
889 SmallVectorImpl<OpenPath> &results) {
890 return addLogicOp(op, bitPos, results);
891}
892
893LogicalResult LocalVisitor::visit(comb::XorOp op, size_t bitPos,
894 SmallVectorImpl<OpenPath> &results) {
895 return addLogicOp(op, bitPos, results);
896}
897
898LogicalResult LocalVisitor::visit(comb::MuxOp op, size_t bitPos,
899 SmallVectorImpl<OpenPath> &results) {
900 // Add a cost of 1 for the mux.
901 if (failed(addEdge(op.getCond(), 0, 1, results)) ||
902 failed(addEdge(op.getTrueValue(), bitPos, 1, results)) ||
903 failed(addEdge(op.getFalseValue(), bitPos, 1, results)))
904 return failure();
905 filterPaths(results, ctx->doKeepOnlyMaxDelayPaths(), ctx->isLocalScope());
906 return success();
907}
908
909LogicalResult LocalVisitor::visit(comb::TruthTableOp op, size_t bitPos,
910 SmallVectorImpl<OpenPath> &results) {
911 for (auto input : op.getInputs()) {
912 if (failed(addEdge(input, 0, 1, results)))
913 return failure();
914 }
915 return success();
916}
917
918LogicalResult LocalVisitor::visit(comb::ExtractOp op, size_t bitPos,
919 SmallVectorImpl<OpenPath> &results) {
920 assert(getBitWidth(op.getInput()) > bitPos + op.getLowBit());
921 auto result = markEquivalent(op, bitPos, op.getInput(),
922 bitPos + op.getLowBit(), results);
923 return result;
924}
925
926LogicalResult LocalVisitor::visit(comb::ReplicateOp op, size_t bitPos,
927 SmallVectorImpl<OpenPath> &results) {
928 return markEquivalent(op, bitPos, op.getInput(),
929 bitPos % getBitWidth(op.getInput()), results);
930}
931
932LogicalResult LocalVisitor::markStartPoint(Value value, size_t bitPos,
933 SmallVectorImpl<OpenPath> &results) {
934 results.emplace_back(circt::igraph::InstancePath(), value, bitPos);
935 return success();
936}
937
938LogicalResult LocalVisitor::visit(hw::WireOp op, size_t bitPos,
939 SmallVectorImpl<OpenPath> &results) {
940 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
941}
942
943LogicalResult LocalVisitor::visit(hw::InstanceOp op, size_t bitPos,
944 size_t resultNum,
945 SmallVectorImpl<OpenPath> &results) {
946 auto moduleName = op.getReferencedModuleNameAttr();
947 auto value = op->getResult(resultNum);
948
949 // If an instance graph is not available, we treat instance results as a
950 // start point.
951 if (!ctx->instanceGraph)
952 return markStartPoint(value, bitPos, results);
953
954 // If an instance graph is available, then we can look up the module.
955 auto *node = ctx->instanceGraph->lookup(moduleName);
956 assert(node && "module not found");
957
958 // Otherwise, if the module is not a HWModuleOp, then we should treat it as a
959 // start point.
960 if (!isa<hw::HWModuleOp>(node->getModule()))
961 return markStartPoint(value, bitPos, results);
962
963 auto *localVisitor = ctx->getLocalVisitorMutable(moduleName);
964
965 auto module = localVisitor->getHWModuleOp();
966 auto operand = module.getBodyBlock()->getTerminator()->getOperand(resultNum);
967 auto result = localVisitor->getOrComputePaths(operand, bitPos);
968 if (failed(result))
969 return failure();
970
971 for (auto &path : *result) {
972 auto delay = path.delay;
973 auto history = path.history;
974 auto newPath =
975 instancePathCache->prependInstance(op, path.startPoint.instancePath);
976 auto startPointPoint = path.startPoint;
977 // If the start point is not a block argument, record it directly.
978 auto arg = dyn_cast<BlockArgument>(startPointPoint.value);
979 if (!arg) {
980 // Update the history to have correct instance path.
981 auto newHistory = debugPointFactory->getEmptyList();
982 if (ctx->doTraceDebugPoints()) {
983 newHistory =
984 mapList(debugPointFactory.get(), history, [&](DebugPoint p) {
985 p.object.instancePath =
986 instancePathCache->prependInstance(op, p.object.instancePath);
987 return p;
988 });
989 newHistory = debugPointFactory->add(
990 DebugPoint({}, value, bitPos, delay, "output port"), newHistory);
991 }
992
993 results.emplace_back(newPath, startPointPoint.value,
994 startPointPoint.bitPos, delay, newHistory);
995 continue;
996 }
997
998 // Otherwise, we need to look up the instance operand.
999 auto result = getOrComputePaths(op->getOperand(arg.getArgNumber()),
1000 startPointPoint.bitPos);
1001 if (failed(result))
1002 return failure();
1003 for (auto path : *result) {
1004 auto newHistory = debugPointFactory->getEmptyList();
1005 if (ctx->doTraceDebugPoints()) {
1006 // Update the history to have correct instance path.
1007 newHistory =
1008 mapList(debugPointFactory.get(), history, [&](DebugPoint p) {
1009 p.object.instancePath =
1010 instancePathCache->prependInstance(op, p.object.instancePath);
1011 p.delay += path.delay;
1012 return p;
1013 });
1014 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
1015 "output port");
1016 newHistory = debugPointFactory->add(debugPoint, newHistory);
1017 }
1018
1019 path.delay += delay;
1020 path.history =
1021 concatList(debugPointFactory.get(), newHistory, path.history);
1022 results.push_back(path);
1023 }
1024 }
1025 return success();
1026}
1027
1028LogicalResult LocalVisitor::visit(comb::ConcatOp op, size_t bitPos,
1029 SmallVectorImpl<OpenPath> &results) {
1030 // Find the exact bit pos in the concat.
1031 size_t newBitPos = bitPos;
1032 for (auto operand : llvm::reverse(op.getInputs())) {
1033 auto size = getBitWidth(operand);
1034 if (newBitPos >= size) {
1035 newBitPos -= size;
1036 continue;
1037 }
1038 return markEquivalent(op, bitPos, operand, newBitPos, results);
1039 }
1040
1041 llvm::report_fatal_error("Should not reach here");
1042 return failure();
1043}
1044
1045LogicalResult LocalVisitor::addLogicOp(Operation *op, size_t bitPos,
1046 SmallVectorImpl<OpenPath> &results) {
1047 auto size = op->getNumOperands();
1048 auto cost = llvm::Log2_64_Ceil(size);
1049 // Create edges each operand with cost ceil(log(size)).
1050 for (auto operand : op->getOperands())
1051 if (failed(addEdge(operand, bitPos, cost, results)))
1052 return failure();
1053 filterPaths(results, ctx->doKeepOnlyMaxDelayPaths(), ctx->isLocalScope());
1054 return success();
1055}
1056
1057LogicalResult LocalVisitor::visitDefault(OpResult value, size_t bitPos,
1058 SmallVectorImpl<OpenPath> &results) {
1059 if (!isa_and_nonnull<hw::HWDialect, comb::CombDialect>(
1060 value.getDefiningOp()->getDialect()))
1061 return success();
1062 // Query it to an operation analyzer.
1063 LLVM_DEBUG({
1064 llvm::dbgs() << "Visiting default: ";
1065 llvm::dbgs() << " " << value << "[" << bitPos << "]\n";
1066 });
1067 SmallVector<std::tuple<size_t, size_t, int64_t>> oracleResults;
1068 auto paths =
1069 operationAnalyzer->analyzeOperation(value, bitPos, oracleResults);
1070 if (failed(paths)) {
1071 LLVM_DEBUG({
1072 llvm::dbgs() << "Failed to get results for: " << value << "[" << bitPos
1073 << "]\n";
1074 });
1075 return success();
1076 }
1077 auto *op = value.getDefiningOp();
1078 for (auto [inputPortIndex, startPointBitPos, delay] : oracleResults) {
1079 LLVM_DEBUG({
1080 llvm::dbgs() << "Adding edge: " << value << "[" << bitPos << "] -> "
1081 << op->getOperand(inputPortIndex) << "[" << startPointBitPos
1082 << "] with delay " << delay << "\n";
1083 });
1084 if (failed(addEdge(op->getOperand(inputPortIndex), startPointBitPos, delay,
1085 results)))
1086 return failure();
1087 }
1088 return success();
1089}
1090
1091LogicalResult LocalVisitor::visit(mlir::BlockArgument arg, size_t bitPos,
1092 SmallVectorImpl<OpenPath> &results) {
1093 assert(arg.getOwner() == module.getBodyBlock());
1094
1095 // Record a debug point.
1096 auto newHistory = ctx->doTraceDebugPoints()
1097 ? debugPointFactory->add(
1098 DebugPoint({}, arg, bitPos, 0, "input port"), {})
1099 : debugPointFactory->getEmptyList();
1100 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
1101 results.push_back(newPoint);
1102 return success();
1103}
1104
1105FailureOr<ArrayRef<OpenPath>> LocalVisitor::getOrComputePaths(Value value,
1106 size_t bitPos) {
1107 if (ec.contains({value, bitPos})) {
1108 auto leader = ec.findLeader({value, bitPos});
1109 // If this is not the leader, then use the leader.
1110 if (*leader != std::pair(value, bitPos)) {
1111 return getOrComputePaths(leader->first, leader->second);
1112 }
1113 }
1114
1115 auto it = cachedResults.find({value, bitPos});
1116 if (it != cachedResults.end())
1117 return ArrayRef<OpenPath>(it->second);
1118
1119 SmallVector<OpenPath> results;
1120 if (failed(visitValue(value, bitPos, results)))
1121 return {};
1122
1123 // Unique the results.
1124 filterPaths(results, ctx->doKeepOnlyMaxDelayPaths(), ctx->isLocalScope());
1125 LLVM_DEBUG({
1126 llvm::dbgs() << value << "[" << bitPos << "] "
1127 << "Found " << results.size() << " paths\n";
1128 llvm::dbgs() << "====Paths:\n";
1129 for (auto &path : results) {
1130 path.print(llvm::dbgs());
1131 llvm::dbgs() << "\n";
1132 }
1133 llvm::dbgs() << "====\n";
1134 });
1135
1136 auto insertedResult =
1137 cachedResults.try_emplace({value, bitPos}, std::move(results));
1138 assert(insertedResult.second);
1139 return ArrayRef<OpenPath>(insertedResult.first->second);
1140}
1141
1142LogicalResult LocalVisitor::visitValue(Value value, size_t bitPos,
1143 SmallVectorImpl<OpenPath> &results) {
1144 LLVM_DEBUG({
1145 llvm::dbgs() << "Visiting: ";
1146 llvm::dbgs() << " " << value << "[" << bitPos << "]\n";
1147 });
1148
1149 if (auto blockArg = dyn_cast<mlir::BlockArgument>(value))
1150 return visit(blockArg, bitPos, results);
1151
1152 auto *op = value.getDefiningOp();
1153 auto result =
1154 TypeSwitch<Operation *, LogicalResult>(op)
1155 .Case<comb::ConcatOp, comb::ExtractOp, comb::ReplicateOp,
1156 aig::AndInverterOp, mig::MajorityInverterOp, comb::AndOp,
1157 comb::OrOp, comb::MuxOp, comb::XorOp, comb::TruthTableOp,
1158 seq::FirRegOp, seq::CompRegOp, hw::ConstantOp,
1159 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
1160 [&](auto op) {
1161 size_t idx = results.size();
1162 auto result = visit(op, bitPos, results);
1163 if (ctx->doTraceDebugPoints())
1164 if (auto name = op->template getAttrOfType<StringAttr>(
1165 "sv.namehint")) {
1166
1167 for (auto i = idx, e = results.size(); i < e; ++i) {
1168 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
1169 "namehint");
1170 auto newHistory = debugPointFactory->add(
1171 debugPoint, results[i].history);
1172 results[i].history = newHistory;
1173 }
1174 }
1175 return result;
1176 })
1177 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
1178 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
1179 results);
1180 })
1181 .Default([&](auto op) {
1182 return visitDefault(cast<OpResult>(value), bitPos, results);
1183 });
1184 return result;
1185}
1186
1187LogicalResult LocalVisitor::initializeAndRun(hw::InstanceOp instance) {
1188 const auto *childVisitor =
1189 ctx->getLocalVisitorMutable(instance.getReferencedModuleNameAttr());
1190 // If not found, the module is blackbox so skip it.
1191 if (!childVisitor)
1192 return success();
1193
1194 // Connect dataflow from instance input ports to end point in the child.
1195 for (const auto &[object, openPaths] :
1196 childVisitor->getFromInputPortToEndPoint()) {
1197 auto [arg, argBitPos] = object;
1198 for (auto [point, delayAndHistory] : openPaths) {
1199 auto [instancePath, endPoint, endPointBitPos] = point;
1200 auto [delay, history] = delayAndHistory;
1201 // Prepend the instance path.
1203 auto newPath = instancePathCache->prependInstance(instance, instancePath);
1204 auto computedResults =
1205 getOrComputePaths(instance.getOperand(arg.getArgNumber()), argBitPos);
1206 if (failed(computedResults))
1207 return failure();
1208
1209 for (auto &result : *computedResults) {
1210 auto newHistory = ctx->doTraceDebugPoints()
1211 ? mapList(debugPointFactory.get(), history,
1212 [&](DebugPoint p) {
1213 // Update the instance path to
1214 // prepend the current instance.
1215 p.object.instancePath = newPath;
1216 p.delay += result.delay;
1217 return p;
1218 })
1219 : debugPointFactory->getEmptyList();
1220 if (auto newPort = dyn_cast<BlockArgument>(result.startPoint.value)) {
1222 {newPath, endPoint, endPointBitPos}, result.delay + delay,
1223 newHistory,
1224 fromInputPortToEndPoint[{newPort, result.startPoint.bitPos}]);
1225 } else {
1226 endPointResults[{newPath, endPoint, endPointBitPos}].emplace_back(
1227 newPath, result.startPoint.value, result.startPoint.bitPos,
1228 result.delay + delay,
1229 ctx->doTraceDebugPoints() ? concatList(debugPointFactory.get(),
1230 newHistory, result.history)
1231 : debugPointFactory->getEmptyList());
1232 }
1233 }
1234 }
1235 }
1236
1237 // Pre-compute the results for the instance output ports.
1238 for (auto instance : instance->getResults()) {
1239 for (size_t i = 0, e = getBitWidth(instance); i < e; ++i) {
1240 auto computedResults = getOrComputePaths(instance, i);
1241 if (failed(computedResults))
1242 return failure();
1243 }
1244 }
1245 return success();
1246}
1247
1248LogicalResult LocalVisitor::initializeAndRun(hw::OutputOp output) {
1249 for (OpOperand &operand : output->getOpOperands()) {
1250 for (size_t i = 0, e = getBitWidth(operand.get()); i < e; ++i) {
1251 auto &recordOutput =
1252 fromOutputPortToStartPoint[{operand.getOperandNumber(), i}];
1253 auto computedResults = getOrComputePaths(operand.get(), i);
1254 if (failed(computedResults))
1255 return failure();
1256 for (const auto &result : *computedResults) {
1257 putUnclosedResult(result.startPoint, result.delay, result.history,
1258 recordOutput);
1259 }
1260 }
1261 }
1262 return success();
1263}
1264
1266 LLVM_DEBUG({ ctx->notifyStart(module.getModuleNameAttr()); });
1267 if (ctx->doLazyComputation())
1268 return success();
1269
1270 // Initialize the results for the block arguments.
1271 for (auto blockArgument : module.getBodyBlock()->getArguments())
1272 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
1273 (void)getOrComputePaths(blockArgument, i);
1274
1275 auto walkResult = module->walk([&](Operation *op) {
1276 auto result =
1277 mlir::TypeSwitch<Operation *, LogicalResult>(op)
1278 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
1279 return markRegEndPoint(op, op.getNext(), op.getReset(),
1280 op.getResetValue());
1281 })
1282 .Case<seq::CompRegOp>([&](auto op) {
1283 return markRegEndPoint(op, op.getInput(), op.getReset(),
1284 op.getResetValue());
1285 })
1286 .Case<seq::FirMemWriteOp>([&](auto op) {
1287 // TODO: Add address.
1288 return markRegEndPoint(op.getMemory(), op.getData(), {}, {},
1289 op.getEnable());
1290 })
1291 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
1292 // TODO: Add address.
1293 return markRegEndPoint(op.getMemory(), op.getWriteData(), {}, {},
1294 op.getEnable());
1295 })
1296 .Case<aig::AndInverterOp, comb::AndOp, comb::OrOp, comb::XorOp,
1297 comb::MuxOp>([&](auto op) {
1298 // NOTE: Visiting and-inverter is not necessary but
1299 // useful to reduce recursion depth.
1300 for (size_t i = 0, e = getBitWidth(op); i < e; ++i)
1301 if (failed(getOrComputePaths(op, i)))
1302 return failure();
1303 return success();
1304 })
1305 .Case<hw::InstanceOp, hw::OutputOp>(
1306 [&](auto op) { return initializeAndRun(op); })
1307 .Default([](auto op) { return success(); });
1308 if (failed(result))
1309 return WalkResult::interrupt();
1310 return WalkResult::advance();
1311 });
1312
1313 {
1314 std::lock_guard<std::mutex> lock(mutex);
1315 done.store(true);
1316 cv.notify_all();
1317 }
1318 LLVM_DEBUG({ ctx->notifyEnd(module.getModuleNameAttr()); });
1319 return failure(walkResult.wasInterrupted());
1320}
1321
1322//===----------------------------------------------------------------------===//
1323// Context
1324//===----------------------------------------------------------------------===//
1325
1326const LocalVisitor *Context::getLocalVisitor(StringAttr name) const {
1327 return getLocalVisitorMutable(name);
1328}
1329
1331 auto *it = localVisitors.find(name);
1332 if (it == localVisitors.end())
1333 return nullptr;
1334
1335 if (isRunningParallel())
1336 it->second->waitUntilDone();
1337
1338 // NOTE: Don't call waitUntilDone here.
1339 return it->second.get();
1340}
1341
1342// ===----------------------------------------------------------------------===//
1343// OperationAnalyzer
1344// ===----------------------------------------------------------------------===//
1345
1346FailureOr<LocalVisitor *>
1348 // Check cache first.
1349 auto opName = op->getName();
1350 auto functionType = getFunctionTypeForOp(op);
1351 auto key = std::make_pair(opName, functionType);
1352 auto it = cache.find(key);
1353 if (it != cache.end())
1354 return it->second.get();
1355
1356 SmallVector<hw::PortInfo> ports;
1357 // Helper to convert types into integer types.
1358 auto getType = [&](Type type) -> Type {
1359 if (type.isInteger())
1360 return type;
1361 auto bitWidth = hw::getBitWidth(type);
1362 if (bitWidth < 0)
1363 return Type(); // Unsupported type
1364 return IntegerType::get(op->getContext(), bitWidth);
1365 };
1366
1367 // Helper to add a port to the module definition
1368 auto addPort = [&](Type type, hw::ModulePort::Direction dir) {
1369 hw::PortInfo portInfo;
1370 portInfo.dir = dir;
1371 portInfo.name = emptyName;
1372 portInfo.type = type;
1373 ports.push_back(portInfo);
1374 };
1375
1376 // Create input ports for each operand
1377 for (auto input : op->getOperands()) {
1378 auto type = getType(input.getType());
1379 if (!type)
1380 return failure(); // Unsupported operand type
1381 addPort(type, hw::ModulePort::Direction::Input);
1382 }
1383
1384 // Create output ports for each result.
1385 SmallVector<Type> resultsTypes;
1386 for (Value result : op->getResults()) {
1387 auto type = getType(result.getType());
1388 if (!type)
1389 return failure(); // Unsupported result type
1390 addPort(type, hw::ModulePort::Direction::Output);
1391 resultsTypes.push_back(type);
1392 }
1393
1394 // Build the wrapper HW module
1395 OpBuilder builder(op->getContext());
1396 builder.setInsertionPointToEnd(moduleOp->getBody());
1397
1398 // Generate unique module name.
1399 auto moduleName = builder.getStringAttr("module_" + Twine(cache.size()));
1400 hw::HWModuleOp hwModule =
1401 builder.create<hw::HWModuleOp>(op->getLoc(), moduleName, ports);
1402
1403 // Clone the operation inside the wrapper module
1404 builder.setInsertionPointToStart(hwModule.getBodyBlock());
1405 auto *cloned = builder.clone(*op);
1406
1407 // Connect module inputs to cloned operation operands
1408 // Handle type mismatches with bitcast operations
1409 // Type mismatches can occur when the original operation uses non-integer
1410 // types (e.g., structs, arrays) that get converted to integer types for the
1411 // wrapper module ports. Since we use the same bit width via
1412 // hw::getBitWidth(), bitcast is safe for bit-compatible types.
1413 for (auto arg : hwModule.getBodyBlock()->getArguments()) {
1414 Value input = arg;
1415 auto idx = arg.getArgNumber();
1416
1417 // Insert bitcast if input port type differs from operand type
1418 if (input.getType() != cloned->getOperand(idx).getType())
1419 input = builder.create<hw::BitcastOp>(
1420 op->getLoc(), cloned->getOperand(idx).getType(), input);
1421
1422 cloned->setOperand(idx, input);
1423 }
1424
1425 // Connect cloned operation results to module outputs
1426 // Handle type mismatches with bitcast operations
1427 SmallVector<Value> outputs;
1428 for (auto result : cloned->getResults()) {
1429 auto idx = result.getResultNumber();
1430
1431 // Insert bitcast if result type differs from output port type
1432 if (result.getType() != resultsTypes[idx])
1433 result =
1434 builder
1435 .create<hw::BitcastOp>(op->getLoc(), resultsTypes[idx], result)
1436 ->getResult(0);
1437
1438 outputs.push_back(result);
1439 }
1440
1441 hwModule.getBodyBlock()->getTerminator()->setOperands(outputs);
1442
1443 // Run conversion pipeline (HW -> Comb -> AIG -> cleanup)
1444 if (!passManager && failed(initializePipeline()))
1445 return mlir::emitError(loc)
1446 << "Failed to initialize pipeline, possibly passes used in the "
1447 "analysis are not registered";
1448
1449 if (failed(passManager->run(moduleOp->getOperation())))
1450 return mlir::emitError(loc) << "Failed to run lowering pipeline";
1451
1452 // Create LocalVisitor to analyze the converted AIG module
1453 auto localVisitor = std::make_unique<LocalVisitor>(hwModule, &ctx);
1454 if (failed(localVisitor->initializeAndRun()))
1455 return failure();
1456
1457 // Cache the result and return
1458 auto [iterator, inserted] = cache.insert({key, std::move(localVisitor)});
1459 assert(inserted && "Cache insertion must succeed for new key");
1460 return iterator->second.get();
1461}
1462
1464 OpResult value, size_t bitPos,
1465 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results) {
1466 auto *op = value.getDefiningOp();
1467 auto localVisitorResult = getOrComputeLocalVisitor(op);
1468 if (failed(localVisitorResult))
1469 return failure();
1470
1471 auto *localVisitor = *localVisitorResult;
1472
1473 // Get output.
1474 Value operand =
1475 localVisitor->getHWModuleOp().getBodyBlock()->getTerminator()->getOperand(
1476 value.getResultNumber());
1477 auto openPaths = localVisitor->getOrComputePaths(operand, bitPos);
1478 if (failed(openPaths))
1479 return failure();
1480
1481 results.reserve(openPaths->size() + results.size());
1482 for (auto &path : *openPaths) {
1483 // end point is always a block argument since there is no other value that
1484 // could be a start point.
1485 BlockArgument blockArg = cast<BlockArgument>(path.startPoint.value);
1486 auto inputPortIndex = blockArg.getArgNumber();
1487 results.push_back(
1488 std::make_tuple(inputPortIndex, path.startPoint.bitPos, path.delay));
1489 }
1490
1491 return success();
1492}
1493
1495 passManager = std::make_unique<mlir::PassManager>(loc->getContext());
1496 return parsePassPipeline(pipelineStr, *passManager);
1497}
1498
1499//===----------------------------------------------------------------------===//
1500// LongestPathAnalysis::Impl
1501//===----------------------------------------------------------------------===//
1502
1503/// Internal implementation for LongestPathAnalysis.
1504///
1505/// This class owns per-module LocalVisitors, orchestrates initialization over
1506/// the instance graph, and provides the concrete implementations for the
1507/// public LongestPathAnalysis API.
1509 Impl(Operation *module, mlir::AnalysisManager &am,
1510 const LongestPathAnalysisOptions &option);
1511
1512 /// Initialize and run analysis for a full MLIR module (hierarchical).
1513 LogicalResult initializeAndRun(mlir::ModuleOp module);
1514
1515 /// Initialize and run analysis for a single HW module (local scope).
1516 LogicalResult initializeAndRun(hw::HWModuleOp module);
1517
1518 /// Return true if we have a LocalVisitor for the given HW module.
1519 bool isAnalysisAvailable(StringAttr moduleName) const;
1520
1521 /// Compute hierarchical timing paths to (value, bitPos) and append to
1522 /// results.
1523 LogicalResult computeGlobalPaths(Value value, size_t bitPos,
1524 SmallVectorImpl<DataflowPath> &results);
1525
1526 /// Collect register-to-register (closed) paths within the module. When
1527 /// 'elaborate' is true, paths are elaborated with instance paths from
1528 /// `moduleName`.
1529 template <bool elaborate>
1530 LogicalResult
1531 collectClosedPaths(StringAttr moduleName,
1532 SmallVectorImpl<DataflowPath> &results) const;
1533
1534 /// Collect open paths from module input ports to internal sequential sinks.
1535 LogicalResult
1536 collectInputToInternalPaths(StringAttr moduleName,
1537 SmallVectorImpl<DataflowPath> &results) const;
1538
1539 /// Collect open paths from internal sequential sources to module output
1540 /// ports.
1541 LogicalResult
1542 collectInternalToOutputPaths(StringAttr moduleName,
1543 SmallVectorImpl<DataflowPath> &results) const;
1544
1545 /// Top modules inferred or specified for this analysis run.
1546 llvm::ArrayRef<hw::HWModuleOp> getTopModules() const { return topModules; }
1547
1548 /// Return average of per-bit max delays for a value.
1549 FailureOr<int64_t> getAverageMaxDelay(Value value);
1550
1551 /// Return the max delay for a value.
1552 FailureOr<int64_t> getMaxDelay(Value value, int64_t bitPos);
1553
1554 /// Compute local open paths to (value, bitPos).
1555 FailureOr<ArrayRef<OpenPath>> computeLocalPaths(Value value, size_t bitPos);
1556
1557protected:
1559
1560private:
1561 /// Recursive helper for computeGlobalPaths.
1562 LogicalResult computeGlobalPaths(const Object &originalObject, Value value,
1563 size_t bitPos,
1564 SmallVectorImpl<DataflowPath> &results);
1565
1566 /// Analysis context.
1568 /// Top-level HW modules that seed hierarchical analysis.
1569 SmallVector<hw::HWModuleOp> topModules;
1570};
1571
1573 Value value, size_t bitPos, SmallVectorImpl<DataflowPath> &results) {
1574 return computeGlobalPaths(Object({}, value, bitPos), value, bitPos, results);
1575}
1576
1578 const Object &originalObject, Value value, size_t bitPos,
1579 SmallVectorImpl<DataflowPath> &results) {
1580 auto parentHWModule =
1581 value.getParentRegion()->getParentOfType<hw::HWModuleOp>();
1582 if (!parentHWModule)
1583 return mlir::emitError(value.getLoc())
1584 << "query value is not in a HWModuleOp";
1585 auto *localVisitor =
1586 ctx.getLocalVisitorMutable(parentHWModule.getModuleNameAttr());
1587 if (!localVisitor)
1588 return success();
1589
1590 auto *instancePathCache = localVisitor->getInstancePathCache();
1591 size_t oldIndex = results.size();
1592 auto *node =
1593 ctx.instanceGraph
1594 ? ctx.instanceGraph->lookup(parentHWModule.getModuleNameAttr())
1595 : nullptr;
1596 LLVM_DEBUG({
1597 llvm::dbgs() << "Running " << parentHWModule.getModuleNameAttr() << " "
1598 << value << " " << bitPos << "\n";
1599 });
1600 auto paths = localVisitor->getOrComputePaths(value, bitPos);
1601 if (failed(paths))
1602 return failure();
1603
1604 for (auto &path : *paths) {
1605 auto arg = dyn_cast<BlockArgument>(path.startPoint.value);
1606 if (!arg || localVisitor->isTopLevel()) {
1607 // If the value is not a block argument, then we are done.
1608 results.push_back({originalObject, path, parentHWModule});
1609 continue;
1610 }
1611
1612 auto newObject = originalObject;
1613 assert(node && "If an instance graph is not available, localVisitor must "
1614 "be a toplevel");
1615 for (auto *inst : node->uses()) {
1616 auto startIndex = results.size();
1617 if (instancePathCache)
1618 newObject.instancePath = instancePathCache->appendInstance(
1619 originalObject.instancePath, inst->getInstance());
1620
1621 auto result = computeGlobalPaths(
1622 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1623 path.startPoint.bitPos, results);
1624 if (failed(result))
1625 return result;
1626 for (auto i = startIndex, e = results.size(); i < e; ++i)
1627 results[i].setDelay(results[i].getDelay() + path.delay);
1628 }
1629 }
1630
1631 filterPaths(results, oldIndex);
1632 return success();
1633}
1634
1635template <bool elaborate>
1637 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1638 auto collectClosedPaths = [&](StringAttr name,
1639 SmallVectorImpl<DataflowPath> &localResults,
1640 igraph::InstanceGraphNode *top = nullptr) {
1641 if (!isAnalysisAvailable(name))
1642 return;
1643 auto *visitor = ctx.getLocalVisitorMutable(name);
1644 for (auto &[point, state] : visitor->getEndPointResults()) {
1645 for (const auto &dataFlow : state) {
1646 if constexpr (elaborate) {
1647 // If elaborate, we need to prepend the path to the root.
1648 auto *instancePathCache = visitor->getInstancePathCache();
1649 auto topToRoot = instancePathCache->getRelativePaths(
1650 visitor->getHWModuleOp(), top);
1651 for (auto &instancePath : topToRoot) {
1652 localResults.emplace_back(point, dataFlow,
1653 top->getModule<hw::HWModuleOp>());
1654 localResults.back().prependPaths(*visitor->getInstancePathCache(),
1655 visitor->getDebugPointFactory(),
1656 instancePath);
1657 }
1658 } else {
1659 localResults.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1660 }
1661 }
1662 }
1663 };
1664
1665 if (ctx.instanceGraph) {
1666 // Accumulate all closed results under the given module.
1667 auto *node = ctx.instanceGraph->lookup(moduleName);
1668 llvm::MapVector<StringAttr, SmallVector<DataflowPath>> resultsMap;
1669 // Prepare the results map for parallel processing.
1670 for (auto *child : llvm::post_order(node))
1671 resultsMap[child->getModule().getModuleNameAttr()] = {};
1672
1673 mlir::parallelForEach(
1674 node->getModule().getContext(), resultsMap,
1675 [&](auto &it) { collectClosedPaths(it.first, it.second, node); });
1676
1677 for (auto &[name, localResults] : resultsMap)
1678 results.append(localResults.begin(), localResults.end());
1679 } else {
1680 collectClosedPaths(moduleName, results);
1681 }
1682
1683 return success();
1684}
1685
1687 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1688 auto *visitor = ctx.getLocalVisitor(moduleName);
1689 if (!visitor)
1690 return failure();
1691
1692 for (auto &[key, value] : visitor->getFromInputPortToEndPoint()) {
1693 auto [arg, argBitPos] = key;
1694 for (auto [point, delayAndHistory] : value) {
1695 auto [path, start, startBitPos] = point;
1696 auto [delay, history] = delayAndHistory;
1697 results.emplace_back(Object(path, start, startBitPos),
1698 OpenPath({}, arg, argBitPos, delay, history),
1699 visitor->getHWModuleOp());
1700 }
1701 }
1702
1703 return success();
1704}
1705
1707 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1708 auto *visitor = ctx.getLocalVisitor(moduleName);
1709 if (!visitor)
1710 return failure();
1711
1712 for (auto &[key, value] : visitor->getFromOutputPortToStartPoint()) {
1713 auto [resultNum, bitPos] = key;
1714 for (auto [point, delayAndHistory] : value) {
1715 auto [path, start, startBitPos] = point;
1716 auto [delay, history] = delayAndHistory;
1717 results.emplace_back(
1718 std::make_tuple(visitor->getHWModuleOp(), resultNum, bitPos),
1719 OpenPath(path, start, startBitPos, delay, history),
1720 visitor->getHWModuleOp());
1721 }
1722 }
1723
1724 return success();
1725}
1726
1727LongestPathAnalysis::Impl::Impl(Operation *moduleOp, mlir::AnalysisManager &am,
1728 const LongestPathAnalysisOptions &option)
1729 : ctx(isa<mlir::ModuleOp>(moduleOp)
1730 ? &am.getAnalysis<igraph::InstanceGraph>()
1731 : nullptr,
1732 option) {
1733 if (auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1734 if (failed(initializeAndRun(module)))
1735 llvm::report_fatal_error("Failed to run longest path analysis");
1736 } else if (auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1737 if (failed(initializeAndRun(hwMod)))
1738 llvm::report_fatal_error("Failed to run longest path analysis");
1739 } else {
1740 llvm::report_fatal_error("Analysis scheduled on invalid operation");
1741 }
1742}
1743
1744LogicalResult
1746 auto it =
1747 ctx.localVisitors.insert({module.getModuleNameAttr(),
1748 std::make_unique<LocalVisitor>(module, &ctx)});
1749 assert(it.second);
1750 it.first->second->setTopLevel();
1751 return it.first->second->initializeAndRun();
1752}
1753
1754LogicalResult
1756 auto topNameAttr = ctx.getTopModuleName();
1757 topModules.clear();
1758 llvm::SetVector<Operation *> visited;
1759 auto *instanceGraph = ctx.instanceGraph;
1760 if (topNameAttr && topNameAttr.getValue() != "") {
1761 auto *topNode = instanceGraph->lookupOrNull(topNameAttr);
1762 if (!topNode || !topNode->getModule() ||
1763 !isa<hw::HWModuleOp>(topNode->getModule())) {
1764 module.emitError() << "top module not found in instance graph "
1765 << topNameAttr;
1766 return failure();
1767 }
1768 topModules.push_back(topNode->getModule<hw::HWModuleOp>());
1769 } else {
1770 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1771 if (failed(inferredResults))
1772 return inferredResults;
1773
1774 for (auto *node : *inferredResults) {
1775 if (auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1776 topModules.push_back(top);
1777 }
1778 }
1779
1780 SmallVector<igraph::InstanceGraphNode *> worklist;
1781 for (auto topNode : topModules)
1782 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1783 // Get a set of design modules that are reachable from the top nodes,
1784 // excluding bound instances.
1785 while (!worklist.empty()) {
1786 auto *node = worklist.pop_back_val();
1787 assert(node && "node should not be null");
1788 auto op = node->getModule();
1789 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1790 continue;
1791
1792 for (auto *child : *node) {
1793 auto childOp = child->getInstance();
1794 if (!childOp || childOp->hasAttr("doNotPrint"))
1795 continue;
1796
1797 worklist.push_back(child->getTarget());
1798 }
1799 }
1800
1801 // Initialize the local visitors if the module was visited, in the
1802 // post-order of the instance graph.
1803 for (auto module : topModules) {
1804 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1805 for (auto *node : llvm::post_order(topNode))
1806 if (node && node->getModule())
1807 if (auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1808 if (visited.contains(hwMod))
1809 ctx.localVisitors.insert(
1810 {hwMod.getModuleNameAttr(),
1811 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1812 }
1813
1814 ctx.localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1815 }
1816
1817 return mlir::failableParallelForEach(
1818 module.getContext(), ctx.localVisitors,
1819 [&](auto &it) { return it.second->initializeAndRun(); });
1820}
1821
1823 StringAttr moduleName) const {
1824 return ctx.localVisitors.find(moduleName) != ctx.localVisitors.end();
1825}
1826// Return the average of the maximum delays across all bits of the given
1827// value, which is useful approximation for the delay of the value. For each
1828// bit position, finds all paths and takes the maximum delay. Then averages
1829// these maximum delays across all bits of the value.
1830FailureOr<int64_t> LongestPathAnalysis::Impl::getAverageMaxDelay(Value value) {
1831 SmallVector<DataflowPath> results;
1832 size_t bitWidth = getBitWidth(value);
1833 if (bitWidth == 0)
1834 return 0;
1835 int64_t totalDelay = 0;
1836 for (size_t i = 0; i < bitWidth; ++i) {
1837 // Clear results from previous iteration.
1838 results.clear();
1839 auto result = computeGlobalPaths(value, i, results);
1840 if (failed(result))
1841 return failure();
1842
1843 int64_t maxDelay = getMaxDelayInPaths(ArrayRef<DataflowPath>(results));
1844 totalDelay += maxDelay;
1845 }
1846 return llvm::divideCeil(totalDelay, bitWidth);
1847}
1848
1849FailureOr<int64_t> LongestPathAnalysis::Impl::getMaxDelay(Value value,
1850 int64_t bitPos) {
1851 SmallVector<DataflowPath> results;
1852 auto collectAndFindMax = ([&](int64_t bitPos) -> FailureOr<int64_t> {
1853 results.clear();
1854 auto result = computeGlobalPaths(value, bitPos, results);
1855 if (failed(result))
1856 return failure();
1857 return getMaxDelayInPaths(ArrayRef<DataflowPath>(results));
1858 });
1859 if (bitPos >= 0)
1860 return collectAndFindMax(bitPos);
1861
1862 size_t bitWidth = getBitWidth(value);
1863 if (bitWidth == 0)
1864 return 0;
1865
1866 int64_t maxDelay = 0;
1867 for (size_t i = 0; i < bitWidth; ++i) {
1868 auto result = collectAndFindMax(i);
1869 if (failed(result))
1870 return failure();
1871 maxDelay = std::max(maxDelay, *result);
1872 }
1873 return maxDelay;
1874}
1875
1876FailureOr<ArrayRef<OpenPath>>
1878 auto parentHWModule =
1879 value.getParentRegion()->getParentOfType<hw::HWModuleOp>();
1880 if (!parentHWModule)
1881 return mlir::emitError(value.getLoc())
1882 << "query value is not in a HWModuleOp";
1883 assert(ctx.localVisitors.size() == 1 &&
1884 "In incremental mode, there should be only one local visitor");
1885
1886 auto *localVisitor =
1887 ctx.getLocalVisitorMutable(parentHWModule.getModuleNameAttr());
1888 if (!localVisitor)
1889 return mlir::emitError(value.getLoc())
1890 << "the local visitor for the given value does not exist";
1891 return localVisitor->getOrComputePaths(value, bitPos);
1892}
1893
1894//===----------------------------------------------------------------------===//
1895// LongestPathAnalysis
1896//===----------------------------------------------------------------------===//
1897
1898LongestPathAnalysis::~LongestPathAnalysis() { delete impl; }
1899
1900LongestPathAnalysis::LongestPathAnalysis(
1901 Operation *moduleOp, mlir::AnalysisManager &am,
1902 const LongestPathAnalysisOptions &option)
1903 : impl(new Impl(moduleOp, am, option)), ctx(moduleOp->getContext()) {
1904 LLVM_DEBUG({
1905 llvm::dbgs() << "LongestPathAnalysis created\n";
1906 if (option.collectDebugInfo)
1907 llvm::dbgs() << " - Collecting debug info\n";
1908 if (option.lazyComputation)
1909 llvm::dbgs() << " - Lazy computation enabled\n";
1910 if (option.keepOnlyMaxDelayPaths)
1911 llvm::dbgs() << " - Keeping only max delay paths\n";
1912 });
1913}
1914
1915bool LongestPathAnalysis::isAnalysisAvailable(StringAttr moduleName) const {
1916 return impl->isAnalysisAvailable(moduleName);
1917}
1918
1919FailureOr<int64_t> LongestPathAnalysis::getAverageMaxDelay(Value value) {
1920 return impl->getAverageMaxDelay(value);
1921}
1922
1923FailureOr<int64_t> LongestPathAnalysis::getMaxDelay(Value value,
1924 int64_t bitPos) {
1925 return impl->getMaxDelay(value, bitPos);
1926}
1927
1928LogicalResult
1930 SmallVectorImpl<DataflowPath> &results,
1931 bool elaboratePaths) const {
1932 if (!isAnalysisValid)
1933 return failure();
1934 if (elaboratePaths)
1935 return impl->collectClosedPaths<true>(moduleName, results);
1936 return impl->collectClosedPaths<false>(moduleName, results);
1937}
1938
1940 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1941 if (!isAnalysisValid)
1942 return failure();
1943
1944 return impl->collectInputToInternalPaths(moduleName, results);
1945}
1946
1948 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const {
1949 if (!isAnalysisValid)
1950 return failure();
1951
1952 return impl->collectInternalToOutputPaths(moduleName, results);
1953}
1954
1955LogicalResult
1957 SmallVectorImpl<DataflowPath> &results,
1958 bool elaboratePaths) const {
1959 if (failed(getClosedPaths(moduleName, results, elaboratePaths)))
1960 return failure();
1961 if (failed(getOpenPathsFromInputPortsToInternal(moduleName, results)))
1962 return failure();
1963 if (failed(getOpenPathsFromInternalToOutputPorts(moduleName, results)))
1964 return failure();
1965 return success();
1966}
1967
1968ArrayRef<hw::HWModuleOp> LongestPathAnalysis::getTopModules() const {
1969 return impl->getTopModules();
1970}
1971
1972FailureOr<ArrayRef<OpenPath>>
1973LongestPathAnalysis::computeLocalPaths(Value value, size_t bitPos) {
1974 if (!isAnalysisValid)
1975 return failure();
1976
1977 return impl->computeLocalPaths(value, bitPos);
1978}
1979
1981 Value value, size_t bitPos, SmallVectorImpl<DataflowPath> &results) {
1982 if (!isAnalysisValid)
1983 return mlir::emitError(value.getLoc()) << "analysis has been invalidated";
1984
1985 return impl->computeGlobalPaths(value, bitPos, results);
1986}
1987
1988//===----------------------------------------------------------------------===//
1989// IncrementalLongestPathAnalysis
1990//===----------------------------------------------------------------------===//
1991
1993 Operation *op) const {
1994 if (!isAnalysisValid)
1995 return false;
1996
1997 auto parentHWModule =
1998 op->getParentRegion()->getParentOfType<hw::HWModuleOp>();
1999 if (!parentHWModule)
2000 return true;
2001 auto *localVisitor =
2002 impl->ctx.getLocalVisitor(parentHWModule.getModuleNameAttr());
2003 if (!localVisitor)
2004 return true;
2005
2006 // If all results of the operation have no paths, then it is safe to mutate
2007 // the operation.
2008 return llvm::all_of(op->getResults(), [localVisitor](Value value) {
2009 for (int64_t i = 0, e = getBitWidth(value); i < e; ++i) {
2010 auto path = localVisitor->getCachedPaths(value, i);
2011 if (!path.empty())
2012 return false;
2013 }
2014 return true;
2015 });
2016}
2017
2023 Operation *op, ValueRange replacement) {
2025}
2026
2030
2031// ===----------------------------------------------------------------------===//
2032// LongestPathCollection
2033// ===----------------------------------------------------------------------===//
2034
2036 llvm::stable_sort(paths, [](const DataflowPath &a, const DataflowPath &b) {
2037 return a.getDelay() > b.getDelay();
2038 });
2039}
2040
2043 // Deduplicate paths by end-point, keeping only the worst-case delay per
2044 // end-point. This gives us the critical delay for each end-point in the
2045 // design
2046 llvm::DenseSet<DataflowPath::EndPointType> seen;
2047 for (size_t i = 0; i < paths.size(); ++i) {
2048 if (seen.insert(paths[i].getEndPoint()).second)
2049 paths[seen.size() - 1] = std::move(paths[i]);
2050 }
2051 paths.resize(seen.size());
2052}
2053
2055 paths.append(other.paths.begin(), other.paths.end());
2057}
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 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 filterPaths(SmallVectorImpl< OpenPath > &results, bool keepOnlyMaxDelay, bool isLocalScope)
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 int64_t getMaxDelayInPaths(ArrayRef< T > paths)
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
llvm::sys::SmartMutex< true > mutex
bool doKeepOnlyMaxDelayPaths() const
LongestPathAnalysisOptions option
llvm::MapVector< StringAttr, std::unique_ptr< LocalVisitor > > localVisitors
bool isRunningParallel() const
LocalVisitor * getLocalVisitorMutable(StringAttr name) const
StringAttr getTopModuleName() const
Context(igraph::InstanceGraph *instanceGraph, const LongestPathAnalysisOptions &option)
llvm::SetVector< StringAttr > running
bool isLocalScope() const
bool doLazyComputation() const
void notifyStart(StringAttr name)
hw::HWModuleOp getHWModuleOp() const
ArrayRef< OpenPath > getCachedPaths(Value value, size_t bitPos) const
LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay, SmallVectorImpl< OpenPath > &results)
LogicalResult visitValue(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
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
llvm::MapVector< Object, std::pair< int64_t, llvm::ImmutableList< DebugPoint > > > ObjectToMaxDistance
LogicalResult markRegEndPoint(Value endPoint, Value start, Value reset={}, Value resetValue={}, Value enable={})
DenseMap< std::pair< Value, size_t >, SmallVector< OpenPath > > cachedResults
std::pair< Value, size_t > findLeader(Value value, size_t bitpos) const
LogicalResult visitDefault(OpResult result, size_t bitPos, SmallVectorImpl< OpenPath > &results)
FailureOr< ArrayRef< OpenPath > > getOrComputePaths(Value value, size_t bitPos)
const auto & getFromInputPortToEndPoint() const
llvm::ImmutableListFactory< DebugPoint > * getDebugPointFactory() const
LogicalResult visit(seq::FirMemReadOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markStartPoint(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to, size_t toBitPos, SmallVectorImpl< OpenPath > &results)
const auto & getEndPointResults() const
llvm::MapVector< std::pair< BlockArgument, size_t >, ObjectToMaxDistance > fromInputPortToEndPoint
std::atomic_bool done
hw::HWModuleOp Context * ctx
llvm::MapVector< std::tuple< size_t, size_t >, ObjectToMaxDistance > fromOutputPortToStartPoint
LogicalResult visit(seq::CompRegOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
DenseMap< Object, SmallVector< OpenPath > > endPointResults
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)
std::unique_ptr< OperationAnalyzer > operationAnalyzer
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)
const auto & getFromOutputPortToStartPoint() const
void waitUntilDone() const
std::unique_ptr< mlir::PassManager > passManager
static constexpr StringRef pipelineStr
mlir::OwningOpRef< mlir::ModuleOp > moduleOp
FailureOr< LocalVisitor * > getOrComputeLocalVisitor(Operation *op)
llvm::DenseMap< std::pair< mlir::OperationName, mlir::FunctionType >, std::unique_ptr< LocalVisitor > > cache
static mlir::FunctionType getFunctionTypeForOp(Operation *op)
LogicalResult analyzeOperation(OpResult value, size_t bitPos, SmallVectorImpl< std::tuple< size_t, size_t, int64_t > > &results)
LogicalResult initializePipeline()
OperationAnalyzer(Location loc)
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 * lookupOrNull(StringAttr name)
Lookup an module by name.
InstanceGraphNode * lookup(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
An instance path composed of a series of instances.
InstanceOpInterface top() const
std::variant< Object, OutputPort > EndPointType
DataflowPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
const OpenPath & getPath() const
hw::HWModuleOp getRoot() const
void print(llvm::raw_ostream &os)
void printEndPoint(llvm::raw_ostream &os)
const EndPointType & getEndPoint() const
void notifyOperationReplaced(Operation *op, ValueRange replacement) override
FailureOr< int64_t > getAverageMaxDelay(Value value)
LogicalResult computeGlobalPaths(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results)
LogicalResult getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results, bool elaboratePaths=false) const
FailureOr< int64_t > getMaxDelay(Value value, int64_t bitPos=-1)
FailureOr< ArrayRef< OpenPath > > computeLocalPaths(Value value, size_t bitPos)
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
void merge(const LongestPathCollection &other)
llvm::SmallVector< DataflowPath, 64 > paths
Impl(int port)
Start a server on the given port. -1 means to let the OS pick a port.
str root(self)
Definition synth.py:152
Object object
Definition synth.py:102
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
Definition HWTypes.cpp:110
llvm::json::Value toJSON(const circt::synth::DataflowPath &path)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition synth.py:1
Internal implementation for LongestPathAnalysis.
LogicalResult collectInternalToOutputPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect open paths from internal sequential sources to module output ports.
LogicalResult computeGlobalPaths(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results)
Compute hierarchical timing paths to (value, bitPos) and append to results.
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
Top modules inferred or specified for this analysis run.
FailureOr< ArrayRef< OpenPath > > computeLocalPaths(Value value, size_t bitPos)
Compute local open paths to (value, bitPos).
FailureOr< int64_t > getMaxDelay(Value value, int64_t bitPos)
Return the max delay for a value.
LogicalResult collectClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect register-to-register (closed) paths within the module.
bool isAnalysisAvailable(StringAttr moduleName) const
Return true if we have a LocalVisitor for the given HW module.
LogicalResult initializeAndRun(mlir::ModuleOp module)
Initialize and run analysis for a full MLIR module (hierarchical).
FailureOr< int64_t > getAverageMaxDelay(Value value)
Return average of per-bit max delays for a value.
LogicalResult collectInputToInternalPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect open paths from module input ports to internal sequential sinks.
SmallVector< hw::HWModuleOp > topModules
Top-level HW modules that seed hierarchical analysis.
mlir::Type type
Definition HWTypes.h:31
mlir::StringAttr name
Definition HWTypes.h:30
This holds the name, type, direction of a module's ports.
A data structure that caches and provides paths to module instances in the IR.
ArrayRef< InstancePath > getRelativePaths(ModuleOpInterface op, InstanceGraphNode *node)
InstancePath concatPath(InstancePath path1, InstancePath path2)
Concatenate two paths.
void print(llvm::raw_ostream &os) const
Configuration options for the longest path analysis.
bool collectDebugInfo
Enable collection of debug points along timing paths.
bool lazyComputation
Enable lazy computation mode for on-demand analysis.
bool keepOnlyMaxDelayPaths
Keep only the maximum delay path per end point.
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)