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>
76#define DEBUG_TYPE "aig-longest-path-analysis"
81 if (
auto vecType = dyn_cast<seq::ClockType>(value.getType()))
83 if (
auto memory = dyn_cast<seq::FirMemType>(value.getType()))
84 return memory.getWidth();
85 return hw::getBitWidth(value.getType());
88template <
typename T,
typename Key>
91 llvm::function_ref<Key(
const T &)> keyFn,
92 llvm::function_ref<int64_t(
const T &)> delayFn) {
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()) {
102 size_t newIndex = keyToIndex.size() + startIndex;
103 keyToIndex[key] = newIndex;
104 results[newIndex] = std::move(results[i]);
107 if (delay > delayFn(results[it->second]))
108 results[it->second] = std::move(results[i]);
111 results.resize(keyToIndex.size() + startIndex);
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; });
122 size_t startIndex = 0) {
124 std::pair<DataflowPath::FanOutType, Object>>(
127 return std::pair(path.getFanOut(), path.getFanIn());
129 [](
const DataflowPath &path) {
return path.getDelay(); });
132static llvm::ImmutableList<DebugPoint>
133mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
134 llvm::ImmutableList<DebugPoint> list,
138 auto &head = list.getHead();
139 return debugPointFactory->add(fn(head),
140 mapList(debugPointFactory, list.getTail(), fn));
143static llvm::ImmutableList<DebugPoint>
144concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
145 llvm::ImmutableList<DebugPoint> lhs,
146 llvm::ImmutableList<DebugPoint> rhs) {
149 return debugPointFactory->add(
150 lhs.getHead(),
concatList(debugPointFactory, lhs.getTail(), rhs));
154 if (
auto arg = dyn_cast<BlockArgument>(value)) {
155 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
158 return StringAttr::get(value.getContext(),
"<unknown-argument>");
160 return op.getArgName(arg.getArgNumber());
162 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
164 [](
auto op) {
return op.getNameAttr(); })
165 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
167 str += op.getInstanceName();
169 str += cast<StringAttr>(
170 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
171 return StringAttr::get(op.getContext(), str);
173 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
174 llvm::SmallString<16> str;
175 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
177 return StringAttr::get(value.getContext(), str);
179 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
180 llvm::SmallString<16> str;
181 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
183 return StringAttr::get(value.getContext(), str);
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);
191 .Default([&](
auto op) {
192 if (
auto name = op->template getAttrOfType<StringAttr>(
"sv.namehint"))
194 llvm::errs() <<
"Unknown op: " << *op <<
"\n";
195 return StringAttr::get(value.getContext(),
"");
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 <<
"]";
209 os <<
", delay=" << delay;
210 if (!history.isEmpty()) {
212 llvm::interleaveComma(history, os, [&](
DebugPoint p) { p.print(os); });
215 if (!comment.empty())
216 os <<
", comment=\"" << comment <<
"\"";
222 int64_t maxDelay = 0;
223 for (
auto &path : paths)
224 maxDelay = std::max(maxDelay, path.getDelay());
228using namespace circt;
235void OpenPath::print(llvm::raw_ostream &os)
const {
239void DebugPoint::print(llvm::raw_ostream &os)
const {
248 if (
auto *
object = std::get_if<Object>(&fanOut)) {
251 auto &[module, resultNumber, bitPos] =
252 *std::get_if<DataflowPath::OutputPort>(&fanOut);
253 auto outputPortName =
root.getOutputName(resultNumber);
254 os <<
"Object($root." << outputPortName <<
"[" << bitPos <<
"])";
259 os <<
"root=" <<
root.getModuleName() <<
", ";
273 instancePath = cache.
concatPath(path, instancePath);
279 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
282 if (debugPointFactory)
283 this->history =
mapList(debugPointFactory, this->history,
297 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
299 this->path.prependPaths(cache, debugPointFactory, path);
302 assert(
root &&
"root is not a hw::HWModuleOp");
307 if (
auto *
object = std::get_if<Object>(&fanOut))
308 object->prependPaths(cache, path);
315 if (
auto *
object = std::get_if<Object>(&fanOut))
316 return object->value.getLoc();
319 auto &[module, resultNumber, bitPos] =
320 *std::get_if<DataflowPath::OutputPort>(&fanOut);
321 return module.getOutputLoc(resultNumber);
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));
340 return llvm::json::Object{
341 {
"instance_path",
toJSON(
object.instancePath)},
342 {
"name",
object.getName().getValue()},
343 {
"bit_pos",
object.bitPos},
350 if (
auto *
object = std::get_if<circt::aig::Object>(&path))
353 auto &[module, resultNumber, bitPos] =
354 *std::get_if<DataflowPath::OutputPort>(&path);
355 return llvm::json::Object{
356 {
"instance_path", {}},
357 {
"name", root.getOutputName(resultNumber)},
363 return llvm::json::Object{
365 {
"delay", point.
delay},
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)}};
380 return llvm::json::Object{
383 {
"root", path.
getRoot().getModuleName()},
397 const LongestPathAnalysisOption &option)
398 : instanceGraph(instanceGraph), option(option) {}
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";
409 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
410 running.remove(name);
412 llvm::dbgs() <<
"[Timing] " << name <<
" finished. running=[";
413 for (
auto &name : running)
414 llvm::dbgs() << name <<
" ";
415 llvm::dbgs() <<
"]\n";
419 const LocalVisitor *getLocalVisitor(StringAttr name)
const;
422 const LocalVisitor *getAndWaitLocalVisitor(StringAttr name)
const;
425 LocalVisitor *getLocalVisitorMutable(StringAttr name)
const;
461 mlir::OpBuilder builder(loc->getContext());
462 moduleOp = builder.create<mlir::ModuleOp>(loc);
463 emptyName = StringAttr::get(loc->getContext(),
"");
468 LogicalResult initializePipeline();
475 getResults(OpResult value,
size_t bitPos,
476 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results);
482 FailureOr<LocalVisitor *> getOrComputeLocalVisitor(Operation *op);
487 static mlir::FunctionType getFunctionTypeForOp(Operation *op);
496 llvm::DenseMap<std::pair<mlir::OperationName, mlir::FunctionType>,
497 std::unique_ptr<LocalVisitor>>
502 constexpr static StringRef pipelineStr =
503 "hw.module(hw-aggregate-to-comb,convert-comb-to-aig,cse,canonicalize)";
516 return mlir::FunctionType::get(op->getContext(), op->getOperandTypes(),
517 op->getResultTypes());
527 LogicalResult initializeAndRun();
529 void waitUntilDone()
const;
533 FailureOr<ArrayRef<OpenPath>> getOrComputeResults(Value value,
size_t bitPos);
537 ArrayRef<OpenPath> getResults(Value value,
size_t bitPos)
const;
542 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
554 return instancePathCache.get();
558 return debugPointFactory.get();
562 void putUnclosedResult(
const Object &
object, int64_t delay,
563 llvm::ImmutableList<DebugPoint> history,
564 ObjectToMaxDistance &objectToMaxDistance);
567 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
574 LogicalResult initializeAndRun(hw::InstanceOp instance);
575 LogicalResult initializeAndRun(hw::OutputOp output);
580 LogicalResult visitValue(Value value,
size_t bitPos,
581 SmallVectorImpl<OpenPath> &results);
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);
589 LogicalResult visit(hw::WireOp op,
size_t bitPos,
590 SmallVectorImpl<OpenPath> &results);
592 SmallVectorImpl<OpenPath> &results);
594 SmallVectorImpl<OpenPath> &results);
595 LogicalResult visit(comb::ReplicateOp op,
size_t bitPos,
596 SmallVectorImpl<OpenPath> &results);
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});
604 LogicalResult markEquivalent(Value from,
size_t fromBitPos, Value to,
606 SmallVectorImpl<OpenPath> &results);
609 LogicalResult visit(aig::AndInverterOp op,
size_t bitPos,
610 SmallVectorImpl<OpenPath> &results);
612 SmallVectorImpl<OpenPath> &results);
614 SmallVectorImpl<OpenPath> &results);
615 LogicalResult visit(
comb::OrOp op,
size_t bitPos,
616 SmallVectorImpl<OpenPath> &results);
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);
626 SmallVectorImpl<OpenPath> &results) {
631 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos,
632 SmallVectorImpl<OpenPath> &results) {
633 return markFanIn(op, bitPos, results);
637 SmallVectorImpl<OpenPath> &results) {
638 return markFanIn(op, bitPos, results);
641 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos,
642 SmallVectorImpl<OpenPath> &results) {
643 return markFanIn(op, bitPos, results);
646 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos,
647 SmallVectorImpl<OpenPath> &results) {
648 return markFanIn(op, bitPos, results);
651 LogicalResult visitDefault(OpResult result,
size_t bitPos,
652 SmallVectorImpl<OpenPath> &results);
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 = {});
682 mutable std::condition_variable
cv;
686 bool topLevel =
false;
690 : module(module), ctx(ctx) {
692 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
694 ? std::make_unique<circt::igraph::InstancePathCache>(
698 std::make_unique<OperationAnalyzer>(
ctx, module->getLoc());
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) {
709 return getResults(leader->first, leader->second);
721 llvm::ImmutableList<DebugPoint> history,
723 auto &slot = objectToMaxDistance[object];
724 if (slot.first >= delay && delay != 0)
726 slot = {delay, history};
731 std::unique_lock<std::mutex> lock(
mutex);
732 cv.wait(lock, [
this] {
return done.load(); });
736 Value reset, Value resetValue,
739 auto record = [&](
size_t fanOutBitPos, Value value,
size_t bitPos) {
743 for (
auto &path : *result) {
744 if (
auto blockArg = dyn_cast<BlockArgument>(path.fanIn.value)) {
757 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
758 if (failed(record(i, start, i)))
764 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
765 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
771 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
772 if (failed(record(i, enable, 0)))
780 Value to,
size_t toBitPos,
781 SmallVectorImpl<OpenPath> &results) {
782 [[maybe_unused]]
auto leader =
ec.getOrInsertLeaderValue({to, toBitPos});
784 [[maybe_unused]]
auto newLeader =
785 ec.unionSets({to, toBitPos}, {from, fromBitPos});
786 assert(leader == *newLeader);
791 SmallVectorImpl<OpenPath> &results) {
795 for (
auto &path : *result) {
797 newPath.delay += delay;
798 results.push_back(newPath);
804 SmallVectorImpl<OpenPath> &results) {
809 SmallVectorImpl<OpenPath> &results) {
814 SmallVectorImpl<OpenPath> &results) {
819 SmallVectorImpl<OpenPath> &results) {
824 SmallVectorImpl<OpenPath> &results) {
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)))
835 SmallVectorImpl<OpenPath> &results) {
836 for (
auto input : op.getInputs()) {
837 if (failed(
addEdge(input, 0, 1, results)))
845 SmallVectorImpl<OpenPath> &results) {
848 bitPos + op.getLowBit(), results);
853 SmallVectorImpl<OpenPath> &results) {
859 SmallVectorImpl<OpenPath> &results) {
865 SmallVectorImpl<OpenPath> &results) {
866 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
871 SmallVectorImpl<OpenPath> &results) {
872 auto moduleName = op.getReferencedModuleNameAttr();
873 auto value = op->getResult(resultNum);
877 if (!
ctx->instanceGraph)
878 return markFanIn(value, bitPos, results);
881 auto *node =
ctx->instanceGraph->lookup(moduleName);
882 assert(node &&
"module not found");
886 if (!isa<hw::HWModuleOp>(node->getModule()))
887 return markFanIn(value, bitPos, results);
889 auto *localVisitor =
ctx->getAndWaitLocalVisitor(moduleName);
890 auto *fanInIt = localVisitor->fromOutputPortToFanIn.find({resultNum, bitPos});
893 if (fanInIt == localVisitor->fromOutputPortToFanIn.end())
896 const auto &fanIns = fanInIt->second;
898 for (
auto &[fanInPoint, delayAndHistory] : fanIns) {
899 auto [delay, history] = delayAndHistory;
904 auto arg = dyn_cast<BlockArgument>(fanInPoint.value);
908 if (
ctx->doTraceDebugPoints()) {
911 p.object.instancePath =
912 instancePathCache->prependInstance(op, p.object.instancePath);
916 DebugPoint({}, value, bitPos, delay,
"output port"), newHistory);
919 results.emplace_back(newPath, fanInPoint.value, fanInPoint.bitPos, delay,
929 for (
auto path : *result) {
931 if (
ctx->doTraceDebugPoints()) {
935 p.object.instancePath =
936 instancePathCache->prependInstance(op, p.object.instancePath);
937 p.delay += path.delay;
940 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
948 results.push_back(path);
956 SmallVectorImpl<OpenPath> &results) {
958 size_t newBitPos = bitPos;
959 for (
auto operand : llvm::reverse(op.getInputs())) {
961 if (newBitPos >= size) {
968 llvm::report_fatal_error(
"Should not reach here");
973 SmallVectorImpl<OpenPath> &results) {
974 auto size = op->getNumOperands();
975 auto cost = llvm::Log2_64_Ceil(size);
977 for (
auto operand : op->getOperands())
978 if (failed(
addEdge(operand, bitPos, cost, results)))
986 SmallVectorImpl<OpenPath> &results) {
987 if (!isa_and_nonnull<hw::HWDialect, comb::CombDialect>(
988 value.getDefiningOp()->getDialect()))
992 llvm::dbgs() <<
"Visiting default: ";
993 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
995 SmallVector<std::tuple<size_t, size_t, int64_t>> oracleResults;
999 llvm::dbgs() <<
"Failed to get results for: " << value <<
"[" << bitPos
1004 auto *op = value.getDefiningOp();
1005 for (
auto [inputPortIndex, fanInBitPos, delay] : oracleResults) {
1007 llvm::dbgs() <<
"Adding edge: " << value <<
"[" << bitPos <<
"] -> "
1008 << op->getOperand(inputPortIndex) <<
"[" << fanInBitPos
1009 <<
"] with delay " << delay <<
"\n";
1011 if (failed(
addEdge(op->getOperand(inputPortIndex), fanInBitPos, delay,
1019 SmallVectorImpl<OpenPath> &results) {
1020 assert(arg.getOwner() == module.getBodyBlock());
1023 auto newHistory =
ctx->doTraceDebugPoints()
1025 DebugPoint({}, arg, bitPos, 0,
"input port"), {})
1027 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
1028 results.push_back(newPoint);
1034 if (
ec.contains({value, bitPos})) {
1035 auto leader =
ec.findLeader({value, bitPos});
1037 if (*leader != std::pair(value, bitPos)) {
1044 return ArrayRef<OpenPath>(it->second);
1046 SmallVector<OpenPath> results;
1047 if (failed(
visitValue(value, bitPos, results)))
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";
1060 llvm::dbgs() <<
"====\n";
1063 auto insertedResult =
1064 cachedResults.try_emplace({value, bitPos}, std::move(results));
1065 assert(insertedResult.second);
1066 return ArrayRef<OpenPath>(insertedResult.first->second);
1070 SmallVectorImpl<OpenPath> &results) {
1072 llvm::dbgs() <<
"Visiting: ";
1073 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
1076 if (
auto blockArg = dyn_cast<mlir::BlockArgument>(value))
1077 return visit(blockArg, bitPos, results);
1079 auto *op = value.getDefiningOp();
1081 TypeSwitch<Operation *, LogicalResult>(op)
1086 hw::WireOp>([&](
auto op) {
1087 size_t idx = results.size();
1088 auto result =
visit(op, bitPos, results);
1089 if (
ctx->doTraceDebugPoints())
1091 op->template getAttrOfType<StringAttr>(
"sv.namehint")) {
1093 for (
auto i = idx, e = results.size(); i < e; ++i) {
1094 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
1098 results[i].history = newHistory;
1103 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
1104 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
1107 .Default([&](
auto op) {
1108 return visitDefault(cast<OpResult>(value), bitPos, results);
1114 const auto *childVisitor =
1115 ctx->getAndWaitLocalVisitor(instance.getReferencedModuleNameAttr());
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;
1131 instance.getOperand(arg.getArgNumber()), argBitPos);
1132 if (failed(computedResults))
1135 for (
auto &result : *computedResults) {
1136 auto newHistory =
ctx->doTraceDebugPoints()
1141 p.object.instancePath = newPath;
1142 p.delay += result.delay;
1146 if (
auto newPort = dyn_cast<BlockArgument>(result.fanIn.value)) {
1148 {newPath, fanOut, fanOutBitPos}, result.delay + delay, newHistory,
1151 fanOutResults[{newPath, fanOut, fanOutBitPos}].emplace_back(
1152 newPath, result.fanIn.value, result.fanIn.bitPos,
1153 result.delay + delay,
1155 newHistory, result.history)
1163 for (
auto instance : instance->getResults()) {
1164 for (
size_t i = 0, e =
getBitWidth(instance); i < e; ++i) {
1166 if (failed(computedResults))
1174 for (OpOperand &operand : output->getOpOperands()) {
1175 for (
size_t i = 0, e =
getBitWidth(operand.get()); i < e; ++i) {
1176 auto &recordOutput =
1179 if (failed(computedResults))
1181 for (
const auto &result : *computedResults) {
1191 LLVM_DEBUG({
ctx->notifyStart(module.getModuleNameAttr()); });
1192 if (
ctx->doIncremental())
1196 for (
auto blockArgument :
module.getBodyBlock()->getArguments())
1197 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
1200 auto walkResult =
module->walk([&](Operation *op) {
1202 mlir::TypeSwitch<Operation *, LogicalResult>(op)
1203 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
1204 return markRegFanOut(op, op.getNext(), op.getReset(),
1205 op.getResetValue());
1207 .Case<seq::CompRegOp>([&](
auto op) {
1208 return markRegFanOut(op, op.getInput(), op.getReset(),
1209 op.getResetValue());
1211 .Case<seq::FirMemWriteOp>([&](
auto op) {
1213 return markRegFanOut(op.getMemory(), op.getData(), {}, {},
1216 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
1218 return markRegFanOut(op.getMemory(), op.getWriteData(), {}, {},
1225 for (
size_t i = 0, e =
getBitWidth(op); i < e; ++i)
1226 if (failed(getOrComputeResults(op, i)))
1230 .Case<hw::InstanceOp, hw::OutputOp>(
1231 [&](
auto op) {
return initializeAndRun(op); })
1232 .Default([](
auto op) {
return success(); });
1234 return WalkResult::interrupt();
1235 return WalkResult::advance();
1239 std::lock_guard<std::mutex> lock(mutex);
1243 LLVM_DEBUG({ ctx->
notifyEnd(module.getModuleNameAttr()); });
1244 return failure(walkResult.wasInterrupted());
1255 return it->second.get();
1262 visitor->waitUntilDone();
1272 return it->second.get();
1279FailureOr<LocalVisitor *>
1282 auto opName = op->getName();
1284 auto key = std::make_pair(opName, functionType);
1285 auto it =
cache.find(key);
1286 if (it !=
cache.end())
1287 return it->second.get();
1289 SmallVector<hw::PortInfo> ports;
1291 auto getType = [&](Type type) -> Type {
1292 if (type.isInteger())
1294 auto bitWidth = hw::getBitWidth(type);
1297 return IntegerType::get(op->getContext(), bitWidth);
1305 portInfo.
type = type;
1306 ports.push_back(portInfo);
1310 for (
auto input : op->getOperands()) {
1311 auto type = getType(input.getType());
1314 addPort(type, hw::ModulePort::Direction::Input);
1318 SmallVector<Type> resultsTypes;
1319 for (Value result : op->getResults()) {
1320 auto type = getType(result.getType());
1323 addPort(type, hw::ModulePort::Direction::Output);
1324 resultsTypes.push_back(type);
1328 OpBuilder builder(op->getContext());
1329 builder.setInsertionPointToEnd(
moduleOp->getBody());
1332 auto moduleName = builder.getStringAttr(
"module_" + Twine(
cache.size()));
1337 builder.setInsertionPointToStart(hwModule.getBodyBlock());
1338 auto *cloned = builder.clone(*op);
1346 for (
auto arg : hwModule.getBodyBlock()->getArguments()) {
1348 auto idx = arg.getArgNumber();
1351 if (input.getType() != cloned->getOperand(idx).getType())
1353 op->getLoc(), cloned->getOperand(idx).getType(), input);
1355 cloned->setOperand(idx, input);
1360 SmallVector<Value> outputs;
1361 for (
auto result : cloned->getResults()) {
1362 auto idx = result.getResultNumber();
1365 if (result.getType() != resultsTypes[idx])
1368 .create<hw::BitcastOp>(op->getLoc(), resultsTypes[idx], result)
1371 outputs.push_back(result);
1374 hwModule.getBodyBlock()->getTerminator()->setOperands(outputs);
1378 return mlir::emitError(
loc)
1379 <<
"Failed to initialize pipeline, possibly passes used in the "
1380 "analysis are not registered";
1383 return mlir::emitError(
loc) <<
"Failed to run lowering pipeline";
1386 auto localVisitor = std::make_unique<LocalVisitor>(hwModule,
ctx);
1387 if (failed(localVisitor->initializeAndRun()))
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();
1397 OpResult value,
size_t bitPos,
1398 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results) {
1399 auto *op = value.getDefiningOp();
1401 if (failed(localVisitorResult))
1404 auto *localVisitor = *localVisitorResult;
1408 localVisitor->getHWModuleOp().getBodyBlock()->getTerminator()->getOperand(
1409 value.getResultNumber());
1410 auto openPaths = localVisitor->getOrComputeResults(operand, bitPos);
1411 if (failed(openPaths))
1414 results.reserve(openPaths->size() + results.size());
1415 for (
auto &path : *openPaths) {
1418 BlockArgument blockArg = cast<BlockArgument>(path.fanIn.value);
1419 auto inputPortIndex = blockArg.getArgNumber();
1421 std::make_tuple(inputPortIndex, path.fanIn.bitPos, path.delay));
1428 passManager = std::make_unique<mlir::PassManager>(
loc->getContext());
1437 Impl(Operation *module, mlir::AnalysisManager &am,
1438 const LongestPathAnalysisOption &option);
1447 getResults(Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1449 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory =
1452 template <
bool elaborate>
1454 SmallVectorImpl<DataflowPath> &results)
const;
1456 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1458 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1471 const Object &originalObject, Value value,
size_t bitPos,
1472 SmallVectorImpl<DataflowPath> &results,
1474 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const;
1481 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1483 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1485 instancePathCache, debugPointFactory);
1489 const Object &originalObject, Value value,
size_t bitPos,
1490 SmallVectorImpl<DataflowPath> &results,
1492 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1493 auto parentHWModule =
1495 if (!parentHWModule)
1496 return mlir::emitError(value.getLoc())
1497 <<
"query value is not in a HWModuleOp";
1498 auto *localVisitor = ctx.
getLocalVisitor(parentHWModule.getModuleNameAttr());
1502 size_t oldIndex = results.size();
1508 llvm::dbgs() <<
"Running " << parentHWModule.getModuleNameAttr() <<
" "
1509 << value <<
" " << bitPos <<
"\n";
1512 for (
auto &path : localVisitor->getResults(value, bitPos)) {
1513 auto arg = dyn_cast<BlockArgument>(path.fanIn.value);
1514 if (!arg || localVisitor->isTopLevel()) {
1516 results.push_back({originalObject, path, parentHWModule});
1520 auto newObject = originalObject;
1521 assert(node &&
"If an instance graph is not available, localVisitor must "
1523 for (
auto *inst : node->uses()) {
1524 auto startIndex = results.size();
1525 if (instancePathCache)
1527 originalObject.instancePath, inst->getInstance());
1529 auto result = getResultsImpl(
1530 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1531 path.fanIn.bitPos, results, instancePathCache, debugPointFactory);
1534 for (
auto i = startIndex, e = results.size(); i < e; ++i)
1535 results[i].setDelay(results[i].getDelay() + path.delay);
1543template <
bool elaborate>
1545 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1546 auto collectClosedPaths = [&](StringAttr name,
1548 if (!isAnalysisAvailable(name))
1551 for (
auto &[point, state] : visitor->getFanOutResults())
1552 for (
const auto &dataFlow : state) {
1553 if constexpr (elaborate) {
1557 visitor->getHWModuleOp(), top);
1558 for (
auto &instancePath : topToRoot) {
1559 results.emplace_back(point, dataFlow,
1561 results.back().prependPaths(*visitor->getInstancePathCache(),
1562 visitor->getDebugPointFactory(),
1566 results.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1574 for (
auto *child : llvm::post_order(node))
1575 collectClosedPaths(child->getModule().getModuleNameAttr(), node);
1577 collectClosedPaths(moduleName);
1584 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
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());
1604 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
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());
1625 const LongestPathAnalysisOption &option)
1626 : ctx(isa<
mlir::ModuleOp>(moduleOp)
1630 if (
auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1632 llvm::report_fatal_error(
"Failed to run longest path analysis");
1633 }
else if (
auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1635 llvm::report_fatal_error(
"Failed to run longest path analysis");
1637 llvm::report_fatal_error(
"Analysis scheduled on invalid operation");
1645 std::make_unique<LocalVisitor>(module, &ctx)});
1647 it.first->second->setTopLevel();
1648 return it.first->second->initializeAndRun();
1654 module->getAttrOfType<FlatSymbolRefAttr>(getTopModuleNameAttrName());
1657 llvm::SetVector<Operation *> visited;
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 "
1669 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1670 if (failed(inferredResults))
1671 return inferredResults;
1673 for (
auto *node : *inferredResults) {
1674 if (
auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1675 topModules.push_back(top);
1679 SmallVector<igraph::InstanceGraphNode *> worklist;
1680 for (
auto topNode : topModules)
1681 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
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))
1691 for (
auto *child : *node) {
1692 auto childOp = child->getInstance();
1693 if (!childOp || childOp->hasAttr(
"doNotPrint"))
1696 worklist.push_back(child->getTarget());
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))
1709 {hwMod.getModuleNameAttr(),
1710 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1713 ctx.
localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1716 return mlir::failableParallelForEach(
1718 [&](
auto &it) { return it.second->initializeAndRun(); });
1722 StringAttr moduleName)
const {
1731 SmallVector<DataflowPath> results;
1735 int64_t totalDelay = 0;
1736 for (
size_t i = 0; i < bitWidth; ++i) {
1739 auto result = getResults(value, i, results);
1744 totalDelay += maxDelay;
1746 return llvm::divideCeil(totalDelay, bitWidth);
1750 SmallVector<DataflowPath> results;
1754 int64_t maxDelay = 0;
1755 for (
size_t i = 0; i < bitWidth; ++i) {
1758 auto result = getResults(value, i, results);
1768FailureOr<ArrayRef<OpenPath>>
1770 if (!doIncremental())
1771 return mlir::emitError(value.getLoc())
1772 <<
"getOrComputeMaxDelay is only available in incremental mode";
1774 return mlir::emitError(value.getLoc())
1775 <<
"inceremental mode is not supported for global analysis";
1776 auto parentHWModule =
1778 if (!parentHWModule)
1779 return mlir::emitError(value.getLoc())
1780 <<
"query value is not in a HWModuleOp";
1782 "In incremental mode, there should be only one local visitor");
1784 auto *localVisitor =
1787 return mlir::emitError(value.getLoc())
1788 <<
"the local visitor for the given value does not exist";
1797LongestPathAnalysis::~LongestPathAnalysis() {
delete impl; }
1799LongestPathAnalysis::LongestPathAnalysis(
1800 Operation *moduleOp, mlir::AnalysisManager &am,
1802 : impl(new
Impl(moduleOp, am, option)), ctx(moduleOp->getContext()) {
1804 llvm::dbgs() <<
"LongestPathAnalysis created\n";
1806 llvm::dbgs() <<
" - Tracing debug points\n";
1808 llvm::dbgs() <<
" - Incremental analysis enabled\n";
1813 return impl->isAnalysisAvailable(moduleName);
1817 return impl->getAverageMaxDelay(value);
1821 return impl->getMaxDelay(value);
1826 SmallVectorImpl<DataflowPath> &results,
1827 bool elaboratePaths)
const {
1829 return impl->getClosedPaths<
true>(moduleName, results);
1830 return impl->getClosedPaths<
false>(moduleName, results);
1834 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1835 return impl->getOpenPathsFromInputPortsToInternal(moduleName, results);
1839 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1840 return impl->getOpenPathsFromInternalToOutputPorts(moduleName, results);
1845 SmallVectorImpl<DataflowPath> &results,
1846 bool elaboratePaths)
const {
1857 return impl->getTopModules();
1864FailureOr<ArrayRef<OpenPath>>
1869 return impl->getOrComputePaths(value, bitPos);
1876 return mlir::emitError(value.getLoc()) <<
"analysis has been invalidated";
1878 auto result =
impl->getOrComputePaths(value, bitPos);
1885 Operation *op)
const {
1889 auto parentHWModule =
1891 if (!parentHWModule)
1893 auto *localVisitor =
1894 impl->ctx.getLocalVisitor(parentHWModule.getModuleNameAttr());
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);
1915 Operation *op, ValueRange replacement) {
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]);
1943 paths.resize(seen.size());
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)
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
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()
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 notifyOperationModified(Operation *op) override
void notifyOperationReplaced(Operation *op, ValueRange replacement) override
void notifyOperationErased(Operation *op) override
FailureOr< ArrayRef< OpenPath > > getOrComputePaths(Value value, size_t bitPos)
bool isOperationValidToMutate(Operation *op) const
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
void sortAndDropNonCriticalPathsPerFanOut()
void sortInDescendingOrder()
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.
llvm::json::Value toJSON(const circt::aig::DataflowPath &path)
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
FailureOr< ArrayRef< OpenPath > > getOrComputePaths(Value value, size_t bitPos)
bool doIncremental() const
bool isAnalysisAvailable(StringAttr moduleName) const
int64_t getAverageMaxDelay(Value value) const
friend class IncrementalLongestPathAnalysis
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)
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.