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