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);
116 bool keepOnlyMaxDelay,
bool isLocalScope) {
122 if (keepOnlyMaxDelay && isLocalScope) {
127 for (
auto &path : results) {
128 if (path.delay > maxDelay.delay)
134 if (maxDelay.delay >= 0)
135 results.push_back(maxDelay);
141 deduplicatePathsImpl<OpenPath, Object>(
142 results, 0, [](
const auto &path) {
return path.startPoint; },
143 [](
const auto &path) {
return path.delay; });
148 if (keepOnlyMaxDelay) {
150 size_t writeIndex = 0;
154 for (
size_t i = 0; i < results.size(); ++i) {
157 if (isa<BlockArgument>(results[i].getStartPoint().value)) {
160 results[writeIndex++] = results[i];
163 if (results[i].delay > maxDelay.delay)
164 maxDelay = results[i];
169 results.resize(writeIndex);
170 if (maxDelay.delay >= 0)
171 results.push_back(maxDelay);
176 size_t startIndex = 0) {
178 std::pair<DataflowPath::EndPointType, Object>>(
181 return std::pair(path.getEndPoint(), path.getStartPoint());
183 [](
const DataflowPath &path) {
return path.getDelay(); });
186static llvm::ImmutableList<DebugPoint>
187mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
188 llvm::ImmutableList<DebugPoint> list,
192 auto &head = list.getHead();
193 return debugPointFactory->add(fn(head),
194 mapList(debugPointFactory, list.getTail(), fn));
197static llvm::ImmutableList<DebugPoint>
198concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
199 llvm::ImmutableList<DebugPoint> lhs,
200 llvm::ImmutableList<DebugPoint> rhs) {
203 return debugPointFactory->add(
204 lhs.getHead(),
concatList(debugPointFactory, lhs.getTail(), rhs));
208 if (
auto arg = dyn_cast<BlockArgument>(value)) {
209 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
212 return StringAttr::get(value.getContext(),
"<unknown-argument>");
214 return op.getArgName(arg.getArgNumber());
216 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
218 [](
auto op) {
return op.getNameAttr(); })
219 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
221 str += op.getInstanceName();
223 str += cast<StringAttr>(
224 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
225 return StringAttr::get(op.getContext(), str);
227 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
228 llvm::SmallString<16> str;
229 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
231 return StringAttr::get(value.getContext(), str);
233 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
234 llvm::SmallString<16> str;
235 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
237 return StringAttr::get(value.getContext(), str);
239 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
240 llvm::SmallString<16> str;
241 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
242 str +=
".write_port";
243 return StringAttr::get(value.getContext(), str);
245 .Default([&](
auto op) {
246 if (
auto name = op->template getAttrOfType<StringAttr>(
"sv.namehint"))
248 llvm::errs() <<
"Unknown op: " << *op <<
"\n";
249 return StringAttr::get(value.getContext(),
"");
255 llvm::ImmutableList<DebugPoint> history = {},
256 StringRef comment =
"") {
257 std::string pathString;
258 llvm::raw_string_ostream osPath(pathString);
259 object.instancePath.print(osPath);
260 os <<
"Object(" << pathString <<
"." <<
object.getName().getValue() <<
"["
261 <<
object.bitPos <<
"]";
263 os <<
", delay=" << delay;
264 if (!history.isEmpty()) {
266 llvm::interleaveComma(history, os, [&](
DebugPoint p) { p.
print(os); });
269 if (!comment.empty())
270 os <<
", comment=\"" << comment <<
"\"";
276 int64_t maxDelay = 0;
277 for (
auto &path : paths)
278 maxDelay = std::max(maxDelay, path.getDelay());
282using namespace circt;
289void OpenPath::print(llvm::raw_ostream &os)
const {
293void DebugPoint::print(llvm::raw_ostream &os)
const {
302 if (
auto *
object = std::get_if<Object>(&endPoint)) {
305 auto &[module, resultNumber, bitPos] =
306 *std::get_if<DataflowPath::OutputPort>(&endPoint);
307 auto outputPortName =
root.getOutputName(resultNumber);
308 os <<
"Object($root." << outputPortName <<
"[" << bitPos <<
"])";
313 os <<
"root=" <<
root.getModuleName() <<
", ";
327 instancePath = cache.
concatPath(path, instancePath);
333 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
336 if (debugPointFactory)
337 this->history =
mapList(debugPointFactory, this->history,
351 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
353 this->path.prependPaths(cache, debugPointFactory, path);
356 assert(
root &&
"root is not a hw::HWModuleOp");
361 if (
auto *
object = std::get_if<Object>(&endPoint))
362 object->prependPaths(cache, path);
369 if (
auto *
object = std::get_if<Object>(&endPoint))
370 return object->value.getLoc();
373 auto &[module, resultNumber, bitPos] =
374 *std::get_if<DataflowPath::OutputPort>(&endPoint);
375 return module.getOutputLoc(resultNumber);
383 llvm::json::Array result;
384 for (
auto op : path) {
385 llvm::json::Object obj;
386 obj[
"instance_name"] = op.getInstanceName();
387 obj[
"module_name"] = op.getReferencedModuleNames()[0];
388 result.push_back(std::move(obj));
394 return llvm::json::Object{
395 {
"instance_path",
toJSON(
object.instancePath)},
396 {
"name",
object.getName().getValue()},
397 {
"bit_pos",
object.bitPos},
404 if (
auto *
object = std::get_if<circt::synth::Object>(&path))
407 auto &[module, resultNumber, bitPos] =
408 *std::get_if<DataflowPath::OutputPort>(&path);
409 return llvm::json::Object{
410 {
"instance_path", {}},
411 {
"name", root.getOutputName(resultNumber)},
417 return llvm::json::Object{
419 {
"delay", point.
delay},
424static llvm::json::Value
toJSON(
const OpenPath &path) {
425 llvm::json::Array history;
426 for (
auto &point : path.history)
427 history.push_back(
toJSON(point));
428 return llvm::json::Object{{
"start_point",
toJSON(path.startPoint)},
429 {
"delay", path.delay},
430 {
"history", std::move(history)}};
434 return llvm::json::Object{
437 {
"root", path.
getRoot().getModuleName()},
451 const LongestPathAnalysisOptions &option)
452 : instanceGraph(instanceGraph), option(option) {}
454 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
455 running.insert(name);
456 llvm::dbgs() <<
"[Timing] " << name <<
" started. running=[";
457 for (
auto &name : running)
458 llvm::dbgs() << name <<
" ";
459 llvm::dbgs() <<
"]\n";
463 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
464 running.remove(name);
466 llvm::dbgs() <<
"[Timing] " << name <<
" finished. running=[";
467 for (
auto &name : running)
468 llvm::dbgs() << name <<
" ";
469 llvm::dbgs() <<
"]\n";
473 const LocalVisitor *getLocalVisitor(StringAttr name)
const;
476 LocalVisitor *getLocalVisitorMutable(StringAttr name)
const;
520 : ctx(nullptr, LongestPathAnalysisOptions(false, true, false)), loc(loc) {
521 mlir::OpBuilder builder(loc->getContext());
522 moduleOp = builder.create<mlir::ModuleOp>(loc);
523 emptyName = StringAttr::get(loc->getContext(),
"");
528 LogicalResult initializePipeline();
534 LogicalResult analyzeOperation(
535 OpResult value,
size_t bitPos,
536 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results);
542 FailureOr<LocalVisitor *> getOrComputeLocalVisitor(Operation *op);
547 static mlir::FunctionType getFunctionTypeForOp(Operation *op);
551 llvm::DenseMap<std::pair<mlir::OperationName, mlir::FunctionType>,
552 std::unique_ptr<LocalVisitor>>
557 constexpr static StringRef pipelineStr =
558 "hw.module(hw-aggregate-to-comb,convert-comb-to-synth,cse,canonicalize)";
571 return mlir::FunctionType::get(op->getContext(), op->getOperandTypes(),
572 op->getResultTypes());
582 LogicalResult initializeAndRun();
584 void waitUntilDone()
const;
588 FailureOr<ArrayRef<OpenPath>> getOrComputePaths(Value value,
size_t bitPos);
592 ArrayRef<OpenPath> getCachedPaths(Value value,
size_t bitPos)
const;
597 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
605 return fromInputPortToEndPoint;
608 return fromOutputPortToStartPoint;
613 return instancePathCache.get();
617 return debugPointFactory.get();
621 void putUnclosedResult(
const Object &
object, int64_t delay,
622 llvm::ImmutableList<DebugPoint> history,
623 ObjectToMaxDistance &objectToMaxDistance);
626 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
633 LogicalResult initializeAndRun(hw::InstanceOp instance);
634 LogicalResult initializeAndRun(hw::OutputOp output);
639 LogicalResult visitValue(Value value,
size_t bitPos,
640 SmallVectorImpl<OpenPath> &results);
642 LogicalResult visit(mlir::BlockArgument argument,
size_t bitPos,
643 SmallVectorImpl<OpenPath> &results);
644 LogicalResult visit(hw::InstanceOp op,
size_t bitPos,
size_t resultNum,
645 SmallVectorImpl<OpenPath> &results);
648 LogicalResult visit(hw::WireOp op,
size_t bitPos,
649 SmallVectorImpl<OpenPath> &results);
651 SmallVectorImpl<OpenPath> &results);
653 SmallVectorImpl<OpenPath> &results);
654 LogicalResult visit(comb::ReplicateOp op,
size_t bitPos,
655 SmallVectorImpl<OpenPath> &results);
658 llvm::EquivalenceClasses<std::pair<Value, size_t>>
ec;
659 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>>
ecMap;
660 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
661 return ec.getLeaderValue({value, bitpos});
663 LogicalResult markEquivalent(Value from,
size_t fromBitPos, Value to,
665 SmallVectorImpl<OpenPath> &results);
668 LogicalResult visit(aig::AndInverterOp op,
size_t bitPos,
669 SmallVectorImpl<OpenPath> &results);
670 LogicalResult visit(mig::MajorityInverterOp op,
size_t bitPos,
671 SmallVectorImpl<OpenPath> &results);
673 SmallVectorImpl<OpenPath> &results);
675 SmallVectorImpl<OpenPath> &results);
676 LogicalResult visit(
comb::OrOp op,
size_t bitPos,
677 SmallVectorImpl<OpenPath> &results);
679 SmallVectorImpl<OpenPath> &results);
680 LogicalResult addLogicOp(Operation *op,
size_t bitPos,
681 SmallVectorImpl<OpenPath> &results);
682 LogicalResult visit(comb::TruthTableOp op,
size_t bitPos,
683 SmallVectorImpl<OpenPath> &results);
687 SmallVectorImpl<OpenPath> &results) {
692 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos,
693 SmallVectorImpl<OpenPath> &results) {
694 return markStartPoint(op, bitPos, results);
698 SmallVectorImpl<OpenPath> &results) {
699 return markStartPoint(op, bitPos, results);
702 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos,
703 SmallVectorImpl<OpenPath> &results) {
704 return markStartPoint(op, bitPos, results);
707 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos,
708 SmallVectorImpl<OpenPath> &results) {
709 return markStartPoint(op, bitPos, results);
712 LogicalResult visitDefault(OpResult result,
size_t bitPos,
713 SmallVectorImpl<OpenPath> &results);
716 LogicalResult addEdge(Value to,
size_t toBitPos, int64_t delay,
717 SmallVectorImpl<OpenPath> &results);
718 LogicalResult markStartPoint(Value value,
size_t bitPos,
719 SmallVectorImpl<OpenPath> &results);
720 LogicalResult markRegEndPoint(Value endPoint, Value start, Value reset = {},
721 Value resetValue = {}, Value enable = {});
743 mutable std::condition_variable
cv;
747 bool topLevel =
false;
751 : module(module), ctx(ctx) {
753 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
755 ? std::make_unique<circt::igraph::InstancePathCache>(
764 size_t bitPos)
const {
765 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
766 auto leader =
ec.findLeader(valueAndBitPos);
767 if (leader !=
ec.member_end()) {
768 if (*leader != valueAndBitPos) {
782 llvm::ImmutableList<DebugPoint> history,
784 auto &slot = objectToMaxDistance[object];
785 if (slot.first >= delay && delay != 0)
787 slot = {delay, history};
792 std::unique_lock<std::mutex> lock(
mutex);
793 cv.wait(lock, [
this] {
return done.load(); });
797 Value reset, Value resetValue,
800 auto record = [&](
size_t endPointBitPos, Value value,
size_t bitPos) {
804 for (
auto &path : *result) {
805 if (
auto blockArg = dyn_cast<BlockArgument>(path.startPoint.value)) {
808 {{}, endPoint, endPointBitPos}, path.delay, path.history,
819 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
820 if (failed(record(i, start, i)))
826 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
827 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
833 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
834 if (failed(record(i, enable, 0)))
842 Value to,
size_t toBitPos,
843 SmallVectorImpl<OpenPath> &results) {
844 [[maybe_unused]]
auto leader =
ec.getOrInsertLeaderValue({to, toBitPos});
846 [[maybe_unused]]
auto newLeader =
847 ec.unionSets({to, toBitPos}, {from, fromBitPos});
848 assert(leader == *newLeader);
853 SmallVectorImpl<OpenPath> &results) {
857 for (
auto &path : *result) {
859 newPath.delay += delay;
860 results.push_back(newPath);
866 SmallVectorImpl<OpenPath> &results) {
872 SmallVectorImpl<OpenPath> &results) {
875 size_t depth = op.getInputs().size() / 2;
876 for (
auto input : op.getInputs()) {
877 if (failed(
addEdge(input, bitPos, depth, results)))
884 SmallVectorImpl<OpenPath> &results) {
889 SmallVectorImpl<OpenPath> &results) {
894 SmallVectorImpl<OpenPath> &results) {
899 SmallVectorImpl<OpenPath> &results) {
901 if (failed(
addEdge(op.getCond(), 0, 1, results)) ||
902 failed(
addEdge(op.getTrueValue(), bitPos, 1, results)) ||
903 failed(
addEdge(op.getFalseValue(), bitPos, 1, results)))
910 SmallVectorImpl<OpenPath> &results) {
911 for (
auto input : op.getInputs()) {
912 if (failed(
addEdge(input, 0, 1, results)))
919 SmallVectorImpl<OpenPath> &results) {
922 bitPos + op.getLowBit(), results);
927 SmallVectorImpl<OpenPath> &results) {
933 SmallVectorImpl<OpenPath> &results) {
939 SmallVectorImpl<OpenPath> &results) {
940 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
945 SmallVectorImpl<OpenPath> &results) {
946 auto moduleName = op.getReferencedModuleNameAttr();
947 auto value = op->getResult(resultNum);
951 if (!
ctx->instanceGraph)
955 auto *node =
ctx->instanceGraph->lookup(moduleName);
956 assert(node &&
"module not found");
960 if (!isa<hw::HWModuleOp>(node->getModule()))
963 auto *localVisitor =
ctx->getLocalVisitorMutable(moduleName);
965 auto module = localVisitor->getHWModuleOp();
966 auto operand =
module.getBodyBlock()->getTerminator()->getOperand(resultNum);
967 auto result = localVisitor->getOrComputePaths(operand, bitPos);
971 for (
auto &path : *result) {
972 auto delay = path.delay;
973 auto history = path.history;
976 auto startPointPoint = path.startPoint;
978 auto arg = dyn_cast<BlockArgument>(startPointPoint.value);
982 if (
ctx->doTraceDebugPoints()) {
985 p.object.instancePath =
986 instancePathCache->prependInstance(op, p.object.instancePath);
990 DebugPoint({}, value, bitPos, delay,
"output port"), newHistory);
993 results.emplace_back(newPath, startPointPoint.value,
994 startPointPoint.bitPos, delay, newHistory);
1000 startPointPoint.bitPos);
1003 for (
auto path : *result) {
1005 if (
ctx->doTraceDebugPoints()) {
1009 p.object.instancePath =
1010 instancePathCache->prependInstance(op, p.object.instancePath);
1011 p.delay += path.delay;
1014 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
1019 path.
delay += delay;
1022 results.push_back(path);
1029 SmallVectorImpl<OpenPath> &results) {
1031 size_t newBitPos = bitPos;
1032 for (
auto operand : llvm::reverse(op.getInputs())) {
1034 if (newBitPos >= size) {
1041 llvm::report_fatal_error(
"Should not reach here");
1046 SmallVectorImpl<OpenPath> &results) {
1047 auto size = op->getNumOperands();
1048 auto cost = llvm::Log2_64_Ceil(size);
1050 for (
auto operand : op->getOperands())
1051 if (failed(
addEdge(operand, bitPos, cost, results)))
1058 SmallVectorImpl<OpenPath> &results) {
1059 if (!isa_and_nonnull<hw::HWDialect, comb::CombDialect>(
1060 value.getDefiningOp()->getDialect()))
1064 llvm::dbgs() <<
"Visiting default: ";
1065 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
1067 SmallVector<std::tuple<size_t, size_t, int64_t>> oracleResults;
1070 if (failed(paths)) {
1072 llvm::dbgs() <<
"Failed to get results for: " << value <<
"[" << bitPos
1077 auto *op = value.getDefiningOp();
1078 for (
auto [inputPortIndex, startPointBitPos, delay] : oracleResults) {
1080 llvm::dbgs() <<
"Adding edge: " << value <<
"[" << bitPos <<
"] -> "
1081 << op->getOperand(inputPortIndex) <<
"[" << startPointBitPos
1082 <<
"] with delay " << delay <<
"\n";
1084 if (failed(
addEdge(op->getOperand(inputPortIndex), startPointBitPos, delay,
1092 SmallVectorImpl<OpenPath> &results) {
1093 assert(arg.getOwner() == module.getBodyBlock());
1096 auto newHistory =
ctx->doTraceDebugPoints()
1098 DebugPoint({}, arg, bitPos, 0,
"input port"), {})
1100 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
1101 results.push_back(newPoint);
1107 if (
ec.contains({value, bitPos})) {
1108 auto leader =
ec.findLeader({value, bitPos});
1110 if (*leader != std::pair(value, bitPos)) {
1117 return ArrayRef<OpenPath>(it->second);
1119 SmallVector<OpenPath> results;
1120 if (failed(
visitValue(value, bitPos, results)))
1126 llvm::dbgs() << value <<
"[" << bitPos <<
"] "
1127 <<
"Found " << results.size() <<
" paths\n";
1128 llvm::dbgs() <<
"====Paths:\n";
1129 for (
auto &path : results) {
1130 path.print(llvm::dbgs());
1131 llvm::dbgs() <<
"\n";
1133 llvm::dbgs() <<
"====\n";
1136 auto insertedResult =
1137 cachedResults.try_emplace({value, bitPos}, std::move(results));
1138 assert(insertedResult.second);
1139 return ArrayRef<OpenPath>(insertedResult.first->second);
1143 SmallVectorImpl<OpenPath> &results) {
1145 llvm::dbgs() <<
"Visiting: ";
1146 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
1149 if (
auto blockArg = dyn_cast<mlir::BlockArgument>(value))
1150 return visit(blockArg, bitPos, results);
1152 auto *op = value.getDefiningOp();
1154 TypeSwitch<Operation *, LogicalResult>(op)
1156 aig::AndInverterOp, mig::MajorityInverterOp,
comb::AndOp,
1159 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
1161 size_t idx = results.size();
1162 auto result =
visit(op, bitPos, results);
1163 if (
ctx->doTraceDebugPoints())
1164 if (
auto name = op->template getAttrOfType<StringAttr>(
1167 for (
auto i = idx, e = results.size(); i < e; ++i) {
1168 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
1171 debugPoint, results[i].history);
1172 results[i].history = newHistory;
1177 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
1178 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
1181 .Default([&](
auto op) {
1182 return visitDefault(cast<OpResult>(value), bitPos, results);
1188 const auto *childVisitor =
1189 ctx->getLocalVisitorMutable(instance.getReferencedModuleNameAttr());
1195 for (
const auto &[
object, openPaths] :
1196 childVisitor->getFromInputPortToEndPoint()) {
1197 auto [arg, argBitPos] = object;
1198 for (
auto [point, delayAndHistory] : openPaths) {
1199 auto [instancePath, endPoint, endPointBitPos] = point;
1200 auto [delay, history] = delayAndHistory;
1204 auto computedResults =
1206 if (failed(computedResults))
1209 for (
auto &result : *computedResults) {
1210 auto newHistory =
ctx->doTraceDebugPoints()
1215 p.object.instancePath = newPath;
1216 p.delay += result.delay;
1220 if (
auto newPort = dyn_cast<BlockArgument>(result.startPoint.value)) {
1222 {newPath, endPoint, endPointBitPos}, result.delay + delay,
1227 newPath, result.startPoint.value, result.startPoint.bitPos,
1228 result.delay + delay,
1230 newHistory, result.history)
1238 for (
auto instance : instance->getResults()) {
1239 for (
size_t i = 0, e =
getBitWidth(instance); i < e; ++i) {
1241 if (failed(computedResults))
1249 for (OpOperand &operand : output->getOpOperands()) {
1250 for (
size_t i = 0, e =
getBitWidth(operand.get()); i < e; ++i) {
1251 auto &recordOutput =
1254 if (failed(computedResults))
1256 for (
const auto &result : *computedResults) {
1266 LLVM_DEBUG({
ctx->notifyStart(module.getModuleNameAttr()); });
1267 if (
ctx->doLazyComputation())
1271 for (
auto blockArgument :
module.getBodyBlock()->getArguments())
1272 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
1275 auto walkResult =
module->walk([&](Operation *op) {
1277 mlir::TypeSwitch<Operation *, LogicalResult>(op)
1278 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
1279 return markRegEndPoint(op, op.getNext(), op.getReset(),
1280 op.getResetValue());
1282 .Case<seq::CompRegOp>([&](
auto op) {
1283 return markRegEndPoint(op, op.getInput(), op.getReset(),
1284 op.getResetValue());
1286 .Case<seq::FirMemWriteOp>([&](
auto op) {
1288 return markRegEndPoint(op.getMemory(), op.getData(), {}, {},
1291 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
1293 return markRegEndPoint(op.getMemory(), op.getWriteData(), {}, {},
1300 for (
size_t i = 0, e =
getBitWidth(op); i < e; ++i)
1301 if (failed(getOrComputePaths(op, i)))
1305 .Case<hw::InstanceOp, hw::OutputOp>(
1306 [&](
auto op) {
return initializeAndRun(op); })
1307 .Default([](
auto op) {
return success(); });
1309 return WalkResult::interrupt();
1310 return WalkResult::advance();
1314 std::lock_guard<std::mutex> lock(mutex);
1318 LLVM_DEBUG({ ctx->
notifyEnd(module.getModuleNameAttr()); });
1319 return failure(walkResult.wasInterrupted());
1339 return it->second.get();
1346FailureOr<LocalVisitor *>
1349 auto opName = op->getName();
1351 auto key = std::make_pair(opName, functionType);
1352 auto it =
cache.find(key);
1353 if (it !=
cache.end())
1354 return it->second.get();
1356 SmallVector<hw::PortInfo> ports;
1358 auto getType = [&](Type type) -> Type {
1359 if (type.isInteger())
1361 auto bitWidth = hw::getBitWidth(type);
1364 return IntegerType::get(op->getContext(), bitWidth);
1372 portInfo.
type = type;
1373 ports.push_back(portInfo);
1377 for (
auto input : op->getOperands()) {
1378 auto type = getType(input.getType());
1381 addPort(type, hw::ModulePort::Direction::Input);
1385 SmallVector<Type> resultsTypes;
1386 for (Value result : op->getResults()) {
1387 auto type = getType(result.getType());
1390 addPort(type, hw::ModulePort::Direction::Output);
1391 resultsTypes.push_back(type);
1395 OpBuilder builder(op->getContext());
1396 builder.setInsertionPointToEnd(
moduleOp->getBody());
1399 auto moduleName = builder.getStringAttr(
"module_" + Twine(
cache.size()));
1404 builder.setInsertionPointToStart(hwModule.getBodyBlock());
1405 auto *cloned = builder.clone(*op);
1413 for (
auto arg : hwModule.getBodyBlock()->getArguments()) {
1415 auto idx = arg.getArgNumber();
1418 if (input.getType() != cloned->getOperand(idx).getType())
1420 op->getLoc(), cloned->getOperand(idx).getType(), input);
1422 cloned->setOperand(idx, input);
1427 SmallVector<Value> outputs;
1428 for (
auto result : cloned->getResults()) {
1429 auto idx = result.getResultNumber();
1432 if (result.getType() != resultsTypes[idx])
1435 .create<hw::BitcastOp>(op->getLoc(), resultsTypes[idx], result)
1438 outputs.push_back(result);
1441 hwModule.getBodyBlock()->getTerminator()->setOperands(outputs);
1445 return mlir::emitError(
loc)
1446 <<
"Failed to initialize pipeline, possibly passes used in the "
1447 "analysis are not registered";
1450 return mlir::emitError(
loc) <<
"Failed to run lowering pipeline";
1453 auto localVisitor = std::make_unique<LocalVisitor>(hwModule, &
ctx);
1454 if (failed(localVisitor->initializeAndRun()))
1458 auto [iterator, inserted] =
cache.insert({key, std::move(localVisitor)});
1459 assert(inserted &&
"Cache insertion must succeed for new key");
1460 return iterator->second.get();
1464 OpResult value,
size_t bitPos,
1465 SmallVectorImpl<std::tuple<size_t, size_t, int64_t>> &results) {
1466 auto *op = value.getDefiningOp();
1468 if (failed(localVisitorResult))
1471 auto *localVisitor = *localVisitorResult;
1475 localVisitor->getHWModuleOp().getBodyBlock()->getTerminator()->getOperand(
1476 value.getResultNumber());
1477 auto openPaths = localVisitor->getOrComputePaths(operand, bitPos);
1478 if (failed(openPaths))
1481 results.reserve(openPaths->size() + results.size());
1482 for (
auto &path : *openPaths) {
1485 BlockArgument blockArg = cast<BlockArgument>(path.startPoint.value);
1486 auto inputPortIndex = blockArg.getArgNumber();
1488 std::make_tuple(inputPortIndex, path.startPoint.bitPos, path.delay));
1495 passManager = std::make_unique<mlir::PassManager>(
loc->getContext());
1509 Impl(Operation *module, mlir::AnalysisManager &am,
1510 const LongestPathAnalysisOptions &option);
1524 SmallVectorImpl<DataflowPath> &results);
1529 template <
bool elaborate>
1532 SmallVectorImpl<DataflowPath> &results)
const;
1537 SmallVectorImpl<DataflowPath> &results)
const;
1543 SmallVectorImpl<DataflowPath> &results)
const;
1552 FailureOr<int64_t>
getMaxDelay(Value value, int64_t bitPos);
1564 SmallVectorImpl<DataflowPath> &results);
1573 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results) {
1578 const Object &originalObject, Value value,
size_t bitPos,
1579 SmallVectorImpl<DataflowPath> &results) {
1580 auto parentHWModule =
1582 if (!parentHWModule)
1583 return mlir::emitError(value.getLoc())
1584 <<
"query value is not in a HWModuleOp";
1585 auto *localVisitor =
1590 auto *instancePathCache = localVisitor->getInstancePathCache();
1591 size_t oldIndex = results.size();
1597 llvm::dbgs() <<
"Running " << parentHWModule.getModuleNameAttr() <<
" "
1598 << value <<
" " << bitPos <<
"\n";
1600 auto paths = localVisitor->getOrComputePaths(value, bitPos);
1604 for (
auto &path : *paths) {
1605 auto arg = dyn_cast<BlockArgument>(path.startPoint.value);
1606 if (!arg || localVisitor->isTopLevel()) {
1608 results.push_back({originalObject, path, parentHWModule});
1612 auto newObject = originalObject;
1613 assert(node &&
"If an instance graph is not available, localVisitor must "
1615 for (
auto *inst : node->uses()) {
1616 auto startIndex = results.size();
1617 if (instancePathCache)
1618 newObject.instancePath = instancePathCache->appendInstance(
1619 originalObject.instancePath, inst->getInstance());
1621 auto result = computeGlobalPaths(
1622 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1623 path.startPoint.bitPos, results);
1626 for (
auto i = startIndex, e = results.size(); i < e; ++i)
1627 results[i].setDelay(results[i].getDelay() + path.delay);
1635template <
bool elaborate>
1637 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1638 auto collectClosedPaths = [&](StringAttr name,
1639 SmallVectorImpl<DataflowPath> &localResults,
1641 if (!isAnalysisAvailable(name))
1644 for (
auto &[point, state] : visitor->getEndPointResults()) {
1645 for (
const auto &dataFlow : state) {
1646 if constexpr (elaborate) {
1650 visitor->getHWModuleOp(), top);
1651 for (
auto &instancePath : topToRoot) {
1652 localResults.emplace_back(point, dataFlow,
1654 localResults.back().prependPaths(*visitor->getInstancePathCache(),
1655 visitor->getDebugPointFactory(),
1659 localResults.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1668 llvm::MapVector<StringAttr, SmallVector<DataflowPath>> resultsMap;
1670 for (
auto *child : llvm::post_order(node))
1671 resultsMap[child->getModule().getModuleNameAttr()] = {};
1673 mlir::parallelForEach(
1674 node->getModule().getContext(), resultsMap,
1675 [&](
auto &it) { collectClosedPaths(it.first, it.second, node); });
1677 for (
auto &[name, localResults] : resultsMap)
1678 results.append(localResults.begin(), localResults.end());
1680 collectClosedPaths(moduleName, results);
1687 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1692 for (
auto &[key, value] : visitor->getFromInputPortToEndPoint()) {
1693 auto [arg, argBitPos] = key;
1694 for (
auto [point, delayAndHistory] : value) {
1695 auto [path, start, startBitPos] = point;
1696 auto [delay, history] = delayAndHistory;
1697 results.emplace_back(
Object(path, start, startBitPos),
1698 OpenPath({}, arg, argBitPos, delay, history),
1699 visitor->getHWModuleOp());
1707 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1712 for (
auto &[key, value] : visitor->getFromOutputPortToStartPoint()) {
1713 auto [resultNum, bitPos] = key;
1714 for (
auto [point, delayAndHistory] : value) {
1715 auto [path, start, startBitPos] = point;
1716 auto [delay, history] = delayAndHistory;
1717 results.emplace_back(
1718 std::make_tuple(visitor->getHWModuleOp(), resultNum, bitPos),
1719 OpenPath(path, start, startBitPos, delay, history),
1720 visitor->getHWModuleOp());
1728 const LongestPathAnalysisOptions &option)
1729 : ctx(isa<
mlir::ModuleOp>(moduleOp)
1733 if (
auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1735 llvm::report_fatal_error(
"Failed to run longest path analysis");
1736 }
else if (
auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1738 llvm::report_fatal_error(
"Failed to run longest path analysis");
1740 llvm::report_fatal_error(
"Analysis scheduled on invalid operation");
1748 std::make_unique<LocalVisitor>(module, &ctx)});
1750 it.first->second->setTopLevel();
1751 return it.first->second->initializeAndRun();
1758 llvm::SetVector<Operation *> visited;
1760 if (topNameAttr && topNameAttr.getValue() !=
"") {
1761 auto *topNode = instanceGraph->
lookupOrNull(topNameAttr);
1762 if (!topNode || !topNode->getModule() ||
1763 !isa<hw::HWModuleOp>(topNode->getModule())) {
1764 module.emitError() << "top module not found in instance graph "
1770 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1771 if (failed(inferredResults))
1772 return inferredResults;
1774 for (
auto *node : *inferredResults) {
1775 if (
auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1776 topModules.push_back(top);
1780 SmallVector<igraph::InstanceGraphNode *> worklist;
1781 for (
auto topNode : topModules)
1782 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1785 while (!worklist.empty()) {
1786 auto *node = worklist.pop_back_val();
1787 assert(node &&
"node should not be null");
1788 auto op = node->getModule();
1789 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1792 for (
auto *child : *node) {
1793 auto childOp = child->getInstance();
1794 if (!childOp || childOp->hasAttr(
"doNotPrint"))
1797 worklist.push_back(child->getTarget());
1803 for (
auto module : topModules) {
1804 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1805 for (
auto *node : llvm::post_order(topNode))
1806 if (node && node->getModule())
1807 if (
auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1808 if (visited.contains(hwMod))
1810 {hwMod.getModuleNameAttr(),
1811 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1814 ctx.
localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1817 return mlir::failableParallelForEach(
1819 [&](
auto &it) { return it.second->initializeAndRun(); });
1823 StringAttr moduleName)
const {
1831 SmallVector<DataflowPath> results;
1835 int64_t totalDelay = 0;
1836 for (
size_t i = 0; i < bitWidth; ++i) {
1839 auto result = computeGlobalPaths(value, i, results);
1844 totalDelay += maxDelay;
1846 return llvm::divideCeil(totalDelay, bitWidth);
1851 SmallVector<DataflowPath> results;
1852 auto collectAndFindMax = ([&](int64_t bitPos) -> FailureOr<int64_t> {
1854 auto result = computeGlobalPaths(value, bitPos, results);
1860 return collectAndFindMax(bitPos);
1866 int64_t maxDelay = 0;
1867 for (
size_t i = 0; i < bitWidth; ++i) {
1868 auto result = collectAndFindMax(i);
1871 maxDelay = std::max(maxDelay, *result);
1876FailureOr<ArrayRef<OpenPath>>
1878 auto parentHWModule =
1880 if (!parentHWModule)
1881 return mlir::emitError(value.getLoc())
1882 <<
"query value is not in a HWModuleOp";
1884 "In incremental mode, there should be only one local visitor");
1886 auto *localVisitor =
1889 return mlir::emitError(value.getLoc())
1890 <<
"the local visitor for the given value does not exist";
1898LongestPathAnalysis::~LongestPathAnalysis() {
delete impl; }
1900LongestPathAnalysis::LongestPathAnalysis(
1901 Operation *moduleOp, mlir::AnalysisManager &am,
1903 : impl(new
Impl(moduleOp, am, option)), ctx(moduleOp->getContext()) {
1905 llvm::dbgs() <<
"LongestPathAnalysis created\n";
1907 llvm::dbgs() <<
" - Collecting debug info\n";
1909 llvm::dbgs() <<
" - Lazy computation enabled\n";
1911 llvm::dbgs() <<
" - Keeping only max delay paths\n";
1916 return impl->isAnalysisAvailable(moduleName);
1920 return impl->getAverageMaxDelay(value);
1925 return impl->getMaxDelay(value, bitPos);
1930 SmallVectorImpl<DataflowPath> &results,
1931 bool elaboratePaths)
const {
1935 return impl->collectClosedPaths<
true>(moduleName, results);
1936 return impl->collectClosedPaths<
false>(moduleName, results);
1940 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1944 return impl->collectInputToInternalPaths(moduleName, results);
1948 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1952 return impl->collectInternalToOutputPaths(moduleName, results);
1957 SmallVectorImpl<DataflowPath> &results,
1958 bool elaboratePaths)
const {
1969 return impl->getTopModules();
1972FailureOr<ArrayRef<OpenPath>>
1977 return impl->computeLocalPaths(value, bitPos);
1981 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results) {
1983 return mlir::emitError(value.getLoc()) <<
"analysis has been invalidated";
1985 return impl->computeGlobalPaths(value, bitPos, results);
1993 Operation *op)
const {
1997 auto parentHWModule =
1999 if (!parentHWModule)
2001 auto *localVisitor =
2002 impl->ctx.getLocalVisitor(parentHWModule.getModuleNameAttr());
2008 return llvm::all_of(op->getResults(), [localVisitor](Value value) {
2009 for (int64_t i = 0, e = getBitWidth(value); i < e; ++i) {
2010 auto path = localVisitor->getCachedPaths(value, i);
2023 Operation *op, ValueRange replacement) {
2046 llvm::DenseSet<DataflowPath::EndPointType> seen;
2047 for (
size_t i = 0; i <
paths.size(); ++i) {
2048 if (seen.insert(
paths[i].getEndPoint()).second)
2049 paths[seen.size() - 1] = std::move(
paths[i]);
2051 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 llvm::ImmutableList< DebugPoint > mapList(llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, llvm::ImmutableList< DebugPoint > list, llvm::function_ref< DebugPoint(DebugPoint)> fn)
static llvm::ImmutableList< DebugPoint > concatList(llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, llvm::ImmutableList< DebugPoint > lhs, llvm::ImmutableList< DebugPoint > rhs)
static void filterPaths(SmallVectorImpl< OpenPath > &results, bool keepOnlyMaxDelay, bool isLocalScope)
static void deduplicatePathsImpl(SmallVectorImpl< T > &results, size_t startIndex, llvm::function_ref< Key(const T &)> keyFn, llvm::function_ref< int64_t(const T &)> delayFn)
static StringAttr getNameImpl(Value value)
static int64_t getMaxDelayInPaths(ArrayRef< T > paths)
This class provides a thread-safe interface to access the analysis results.
circt::igraph::InstanceGraph * instanceGraph
const LocalVisitor * getLocalVisitor(StringAttr name) const
void notifyEnd(StringAttr name)
bool doTraceDebugPoints() const
llvm::sys::SmartMutex< true > mutex
bool doKeepOnlyMaxDelayPaths() const
LongestPathAnalysisOptions option
llvm::MapVector< StringAttr, std::unique_ptr< LocalVisitor > > localVisitors
bool isRunningParallel() const
LocalVisitor * getLocalVisitorMutable(StringAttr name) const
StringAttr getTopModuleName() const
Context(igraph::InstanceGraph *instanceGraph, const LongestPathAnalysisOptions &option)
llvm::SetVector< StringAttr > running
bool isLocalScope() const
bool doLazyComputation() const
void notifyStart(StringAttr name)
hw::HWModuleOp getHWModuleOp() const
ArrayRef< OpenPath > getCachedPaths(Value value, size_t bitPos) const
LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay, SmallVectorImpl< OpenPath > &results)
LogicalResult visitValue(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult addLogicOp(Operation *op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::unique_ptr< llvm::ImmutableListFactory< DebugPoint > > debugPointFactory
DenseMap< std::pair< Value, size_t >, std::pair< Value, size_t > > ecMap
llvm::MapVector< Object, std::pair< int64_t, llvm::ImmutableList< DebugPoint > > > ObjectToMaxDistance
LogicalResult markRegEndPoint(Value endPoint, Value start, Value reset={}, Value resetValue={}, Value enable={})
DenseMap< std::pair< Value, size_t >, SmallVector< OpenPath > > cachedResults
std::pair< Value, size_t > findLeader(Value value, size_t bitpos) const
LogicalResult visitDefault(OpResult result, size_t bitPos, SmallVectorImpl< OpenPath > &results)
FailureOr< ArrayRef< OpenPath > > getOrComputePaths(Value value, size_t bitPos)
const auto & getFromInputPortToEndPoint() const
llvm::ImmutableListFactory< DebugPoint > * getDebugPointFactory() const
LogicalResult visit(seq::FirMemReadOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markStartPoint(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to, size_t toBitPos, SmallVectorImpl< OpenPath > &results)
const auto & getEndPointResults() const
llvm::MapVector< std::pair< BlockArgument, size_t >, ObjectToMaxDistance > fromInputPortToEndPoint
hw::HWModuleOp Context * ctx
llvm::MapVector< std::tuple< size_t, size_t >, ObjectToMaxDistance > fromOutputPortToStartPoint
LogicalResult visit(seq::CompRegOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
DenseMap< Object, SmallVector< OpenPath > > endPointResults
LogicalResult visit(seq::FirRegOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult initializeAndRun()
void getClosedPaths(SmallVectorImpl< DataflowPath > &results) const
llvm::EquivalenceClasses< std::pair< Value, size_t > > ec
LogicalResult visit(seq::FirMemReadWriteOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult visit(mlir::BlockArgument argument, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::unique_ptr< OperationAnalyzer > operationAnalyzer
LogicalResult visit(hw::ConstantOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::condition_variable cv
void putUnclosedResult(const Object &object, int64_t delay, llvm::ImmutableList< DebugPoint > history, ObjectToMaxDistance &objectToMaxDistance)
std::unique_ptr< circt::igraph::InstancePathCache > instancePathCache
circt::igraph::InstancePathCache * getInstancePathCache() const
LocalVisitor(hw::HWModuleOp module, Context *ctx)
const auto & getFromOutputPortToStartPoint() const
void waitUntilDone() const
std::unique_ptr< mlir::PassManager > passManager
static constexpr StringRef pipelineStr
mlir::OwningOpRef< mlir::ModuleOp > moduleOp
FailureOr< LocalVisitor * > getOrComputeLocalVisitor(Operation *op)
llvm::DenseMap< std::pair< mlir::OperationName, mlir::FunctionType >, std::unique_ptr< LocalVisitor > > cache
static mlir::FunctionType getFunctionTypeForOp(Operation *op)
LogicalResult analyzeOperation(OpResult value, size_t bitPos, SmallVectorImpl< std::tuple< size_t, size_t, int64_t > > &results)
LogicalResult initializePipeline()
OperationAnalyzer(Location loc)
HW-specific instance graph with a virtual entry node linking to all publicly visible modules.
This is a Node in the InstanceGraph.
This graph tracks modules and where they are instantiated.
InstanceGraphNode * lookupOrNull(StringAttr name)
Lookup an module by name.
InstanceGraphNode * lookup(ModuleOpInterface op)
Look up an InstanceGraphNode for a module.
An instance path composed of a series of instances.
InstanceOpInterface top() const
std::variant< Object, OutputPort > EndPointType
DataflowPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
const OpenPath & getPath() const
Location getEndPointLoc()
hw::HWModuleOp getRoot() const
void print(llvm::raw_ostream &os)
void printEndPoint(llvm::raw_ostream &os)
const EndPointType & getEndPoint() const
void notifyOperationModified(Operation *op) override
void notifyOperationReplaced(Operation *op, ValueRange replacement) override
void notifyOperationErased(Operation *op) override
bool isOperationValidToMutate(Operation *op) const
FailureOr< int64_t > getAverageMaxDelay(Value value)
LogicalResult computeGlobalPaths(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results)
LogicalResult getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results, bool elaboratePaths=false) const
FailureOr< int64_t > getMaxDelay(Value value, int64_t bitPos=-1)
FailureOr< ArrayRef< OpenPath > > computeLocalPaths(Value value, size_t bitPos)
LogicalResult getAllPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results, bool elaboratePaths=false) const
LogicalResult getOpenPathsFromInternalToOutputPorts(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
bool isAnalysisAvailable(StringAttr moduleName) const
LogicalResult getOpenPathsFromInputPortsToInternal(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
void merge(const LongestPathCollection &other)
llvm::SmallVector< DataflowPath, 64 > paths
void sortAndDropNonCriticalPathsPerEndPoint()
void sortInDescendingOrder()
Impl(int port)
Start a server on the given port. -1 means to let the OS pick a port.
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
llvm::json::Value toJSON(const circt::synth::DataflowPath &path)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Internal implementation for LongestPathAnalysis.
LogicalResult collectInternalToOutputPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect open paths from internal sequential sources to module output ports.
LogicalResult computeGlobalPaths(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results)
Compute hierarchical timing paths to (value, bitPos) and append to results.
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
Top modules inferred or specified for this analysis run.
FailureOr< ArrayRef< OpenPath > > computeLocalPaths(Value value, size_t bitPos)
Compute local open paths to (value, bitPos).
friend class IncrementalLongestPathAnalysis
FailureOr< int64_t > getMaxDelay(Value value, int64_t bitPos)
Return the max delay for a value.
LogicalResult collectClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect register-to-register (closed) paths within the module.
bool isAnalysisAvailable(StringAttr moduleName) const
Return true if we have a LocalVisitor for the given HW module.
LogicalResult initializeAndRun(mlir::ModuleOp module)
Initialize and run analysis for a full MLIR module (hierarchical).
FailureOr< int64_t > getAverageMaxDelay(Value value)
Return average of per-bit max delays for a value.
LogicalResult collectInputToInternalPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Collect open paths from module input ports to internal sequential sinks.
SmallVector< hw::HWModuleOp > topModules
Top-level HW modules that seed hierarchical analysis.
Context ctx
Analysis context.
This holds the name, type, direction of a module's ports.
A data structure that caches and provides paths to module instances in the IR.
ArrayRef< InstancePath > getRelativePaths(ModuleOpInterface op, InstanceGraphNode *node)
InstancePath concatPath(InstancePath path1, InstancePath path2)
Concatenate two paths.
void print(llvm::raw_ostream &os) const
Configuration options for the longest path analysis.
bool collectDebugInfo
Enable collection of debug points along timing paths.
bool lazyComputation
Enable lazy computation mode for on-demand analysis.
bool keepOnlyMaxDelayPaths
Keep only the maximum delay path per end point.
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
StringAttr getName() const
void print(llvm::raw_ostream &os) const
OpenPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)