40#include "mlir/IR/BuiltinAttributes.h"
41#include "mlir/IR/BuiltinOps.h"
42#include "mlir/IR/Diagnostics.h"
43#include "mlir/IR/Operation.h"
44#include "mlir/IR/Threading.h"
45#include "mlir/IR/Value.h"
46#include "mlir/IR/Visitors.h"
47#include "mlir/Pass/AnalysisManager.h"
48#include "mlir/Support/FileUtilities.h"
49#include "mlir/Support/LLVM.h"
50#include "llvm/ADT//MapVector.h"
51#include "llvm/ADT/ArrayRef.h"
52#include "llvm/ADT/DenseMapInfoVariant.h"
53#include "llvm/ADT/EquivalenceClasses.h"
54#include "llvm/ADT/ImmutableList.h"
55#include "llvm/ADT/MapVector.h"
56#include "llvm/ADT/PostOrderIterator.h"
57#include "llvm/ADT/STLExtras.h"
58#include "llvm/ADT/SmallVector.h"
59#include "llvm/ADT/StringRef.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/JSON.h"
63#include "llvm/Support/LogicalResult.h"
64#include "llvm/Support/MathExtras.h"
65#include "llvm/Support/Mutex.h"
66#include "llvm/Support/raw_ostream.h"
67#include <condition_variable>
72#define DEBUG_TYPE "aig-longest-path-analysis"
77 if (
auto vecType = dyn_cast<seq::ClockType>(value.getType()))
79 if (
auto memory = dyn_cast<seq::FirMemType>(value.getType()))
80 return memory.getWidth();
81 return hw::getBitWidth(value.getType());
84template <
typename T,
typename Key>
87 llvm::function_ref<Key(
const T &)> keyFn,
88 llvm::function_ref<int64_t(
const T &)> delayFn) {
90 DenseMap<Key, size_t> keyToIndex;
91 for (
size_t i = startIndex; i < results.size(); ++i) {
92 auto &path = results[i];
93 auto key = keyFn(path);
94 auto delay = delayFn(path);
95 auto it = keyToIndex.find(key);
96 if (it == keyToIndex.end()) {
98 size_t newIndex = keyToIndex.size() + startIndex;
99 keyToIndex[key] = newIndex;
100 results[newIndex] = std::move(results[i]);
103 if (delay > delayFn(results[it->second]))
104 results[it->second] = std::move(results[i]);
107 results.resize(keyToIndex.size() + startIndex);
111 size_t startIndex = 0) {
112 deduplicatePathsImpl<OpenPath, Object>(
113 results, startIndex, [](
const auto &path) {
return path.fanIn; },
114 [](
const auto &path) {
return path.delay; });
118 size_t startIndex = 0) {
120 std::pair<DataflowPath::FanOutType, Object>>(
123 return std::pair(path.getFanOut(), path.getFanIn());
125 [](
const DataflowPath &path) {
return path.getDelay(); });
128static llvm::ImmutableList<DebugPoint>
129mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
130 llvm::ImmutableList<DebugPoint> list,
134 auto &head = list.getHead();
135 return debugPointFactory->add(fn(head),
136 mapList(debugPointFactory, list.getTail(), fn));
129mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory, {
…}
139static llvm::ImmutableList<DebugPoint>
140concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
141 llvm::ImmutableList<DebugPoint> lhs,
142 llvm::ImmutableList<DebugPoint> rhs) {
145 return debugPointFactory->add(
146 lhs.getHead(),
concatList(debugPointFactory, lhs.getTail(), rhs));
140concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory, {
…}
150 if (
auto arg = dyn_cast<BlockArgument>(value)) {
151 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
154 return StringAttr::get(value.getContext(),
"<unknown-argument>");
156 return op.getArgName(arg.getArgNumber());
158 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
160 [](
auto op) {
return op.getNameAttr(); })
161 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
163 str += op.getInstanceName();
165 str += cast<StringAttr>(
166 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
167 return StringAttr::get(op.getContext(), str);
169 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
170 llvm::SmallString<16> str;
171 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
173 return StringAttr::get(value.getContext(), str);
175 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
176 llvm::SmallString<16> str;
177 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
179 return StringAttr::get(value.getContext(), str);
181 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
182 llvm::SmallString<16> str;
183 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
184 str +=
".write_port";
185 return StringAttr::get(value.getContext(), str);
187 .Default([&](
auto op) {
188 if (
auto name = op->template getAttrOfType<StringAttr>(
"sv.namehint"))
190 llvm::errs() <<
"Unknown op: " << *op <<
"\n";
191 return StringAttr::get(value.getContext(),
"");
197 llvm::ImmutableList<DebugPoint> history = {},
198 StringRef comment =
"") {
199 std::string pathString;
200 llvm::raw_string_ostream osPath(pathString);
201 object.instancePath.print(osPath);
202 os <<
"Object(" << pathString <<
"." <<
getNameImpl(
object.value).getValue()
203 <<
"[" <<
object.bitPos <<
"]";
205 os <<
", delay=" << delay;
206 if (!history.isEmpty()) {
208 llvm::interleaveComma(history, os, [&](
DebugPoint p) { p.print(os); });
211 if (!comment.empty())
212 os <<
", comment=\"" << comment <<
"\"";
216using namespace circt;
223void OpenPath::print(llvm::raw_ostream &os)
const {
223void OpenPath::print(llvm::raw_ostream &os)
const {
…}
234 if (
auto *
object = std::get_if<Object>(&fanOut)) {
237 auto &[resultNumber, bitPos] =
238 *std::get_if<std::pair<size_t, size_t>>(&fanOut);
239 auto outputPortName =
root.getOutputName(resultNumber);
240 os <<
"Object($root." << outputPortName <<
"[" << bitPos <<
"])";
245 os <<
"root=" <<
root.getModuleName() <<
", ";
259 instancePath = cache.
concatPath(path, instancePath);
265 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
268 if (debugPointFactory)
283 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
285 this->path.prependPaths(cache, debugPointFactory,
path);
288 assert(
root &&
"root is not a hw::HWModuleOp");
293 if (
auto *
object = std::get_if<Object>(&fanOut))
294 object->prependPaths(cache,
path);
301 if (
auto *
object = std::get_if<Object>(&fanOut))
302 return object->value.getLoc();
305 return root.getOutputLoc(std::get<std::pair<size_t, size_t>>(fanOut).first);
313 llvm::json::Array result;
314 for (
auto op : path) {
315 llvm::json::Object obj;
316 obj[
"instance_name"] = op.getInstanceName();
317 obj[
"module_name"] = op.getReferencedModuleNames()[0];
318 result.push_back(std::move(obj));
324 return llvm::json::Object{
325 {
"instance_path",
toJSON(
object.instancePath)},
327 {
"bit_pos",
object.bitPos},
334 if (
auto *
object = std::get_if<circt::aig::Object>(&path))
337 auto &[resultNumber, bitPos] = *std::get_if<std::pair<size_t, size_t>>(&path);
338 return llvm::json::Object{
339 {
"instance_path", {}},
340 {
"name", root.getOutputName(resultNumber)},
346 return llvm::json::Object{
348 {
"delay", point.
delay},
354 llvm::json::Array history;
355 for (
auto &point : path.
history)
356 history.push_back(
toJSON(point));
357 return llvm::json::Object{{
"fan_in",
toJSON(path.fanIn)},
358 {
"delay", path.
delay},
359 {
"history", std::move(history)}};
363 return llvm::json::Object{
366 {
"root", path.
getRoot().getModuleName()},
380 const LongestPathAnalysisOption &option)
381 : instanceGraph(instanceGraph), option(option) {}
383 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
384 running.insert(name);
385 llvm::dbgs() <<
"[Timing] " << name <<
" started. running=[";
386 for (
auto &name : running)
387 llvm::dbgs() << name <<
" ";
388 llvm::dbgs() <<
"]\n";
392 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
393 running.remove(name);
395 llvm::dbgs() <<
"[Timing] " << name <<
" finished. running=[";
396 for (
auto &name : running)
397 llvm::dbgs() << name <<
" ";
398 llvm::dbgs() <<
"]\n";
402 const LocalVisitor *getLocalVisitor(StringAttr name)
const;
405 const LocalVisitor *getAndWaitLocalVisitor(StringAttr name)
const;
427 LogicalResult initializeAndRun();
429 void waitUntilDone()
const;
433 FailureOr<ArrayRef<OpenPath>> getOrComputeResults(Value value,
size_t bitPos);
437 ArrayRef<OpenPath> getResults(Value value,
size_t bitPos)
const;
442 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
454 return instancePathCache.get();
458 return debugPointFactory.get();
462 void putUnclosedResult(
const Object &
object, int64_t delay,
463 llvm::ImmutableList<DebugPoint> history,
464 ObjectToMaxDistance &objectToMaxDistance);
467 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
474 LogicalResult initializeAndRun(hw::InstanceOp instance);
475 LogicalResult initializeAndRun(hw::OutputOp output);
480 LogicalResult visitValue(Value value,
size_t bitPos,
481 SmallVectorImpl<OpenPath> &results);
483 LogicalResult visit(mlir::BlockArgument argument,
size_t bitPos,
484 SmallVectorImpl<OpenPath> &results);
485 LogicalResult visit(hw::InstanceOp op,
size_t bitPos,
size_t resultNum,
486 SmallVectorImpl<OpenPath> &results);
489 LogicalResult visit(hw::WireOp op,
size_t bitPos,
490 SmallVectorImpl<OpenPath> &results);
492 SmallVectorImpl<OpenPath> &results);
494 SmallVectorImpl<OpenPath> &results);
495 LogicalResult visit(comb::ReplicateOp op,
size_t bitPos,
496 SmallVectorImpl<OpenPath> &results);
499 llvm::EquivalenceClasses<std::pair<Value, size_t>>
ec;
500 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>>
ecMap;
501 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
502 return ec.getLeaderValue({value, bitpos});
501 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
…}
504 LogicalResult markEquivalent(Value from,
size_t fromBitPos, Value to,
506 SmallVectorImpl<OpenPath> &results);
509 LogicalResult visit(aig::AndInverterOp op,
size_t bitPos,
510 SmallVectorImpl<OpenPath> &results);
512 SmallVectorImpl<OpenPath> &results);
514 SmallVectorImpl<OpenPath> &results);
515 LogicalResult visit(
comb::OrOp op,
size_t bitPos,
516 SmallVectorImpl<OpenPath> &results);
518 SmallVectorImpl<OpenPath> &results);
519 LogicalResult addLogicOp(Operation *op,
size_t bitPos,
520 SmallVectorImpl<OpenPath> &results);
524 SmallVectorImpl<OpenPath> &results) {
529 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos,
530 SmallVectorImpl<OpenPath> &results) {
531 return markFanIn(op, bitPos, results);
529 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos, {
…}
535 SmallVectorImpl<OpenPath> &results) {
536 return markFanIn(op, bitPos, results);
539 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos,
540 SmallVectorImpl<OpenPath> &results) {
541 return markFanIn(op, bitPos, results);
539 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos, {
…}
544 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos,
545 SmallVectorImpl<OpenPath> &results) {
546 return markFanIn(op, bitPos, results);
544 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos, {
…}
549 LogicalResult visitDefault(Operation *op,
size_t bitPos,
550 SmallVectorImpl<OpenPath> &results);
553 LogicalResult addEdge(Value to,
size_t toBitPos, int64_t delay,
554 SmallVectorImpl<OpenPath> &results);
555 LogicalResult markFanIn(Value value,
size_t bitPos,
556 SmallVectorImpl<OpenPath> &results);
557 LogicalResult markRegFanOut(Value fanOut, Value start, Value reset = {},
558 Value resetValue = {}, Value enable = {});
577 mutable std::condition_variable
cv;
581 bool topLevel =
false;
585 : module(module), ctx(ctx) {
587 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
589 ? std::make_unique<circt::igraph::InstancePathCache>(
596 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
597 auto leader =
ec.findLeader(valueAndBitPos);
598 if (leader !=
ec.member_end()) {
599 if (*leader != valueAndBitPos) {
601 return getResults(leader->first, leader->second);
613 llvm::ImmutableList<DebugPoint> history,
615 auto &slot = objectToMaxDistance[object];
616 if (slot.first >= delay && delay != 0)
618 slot = {delay, history};
623 std::unique_lock<std::mutex> lock(
mutex);
624 cv.wait(lock, [
this] {
return done.load(); });
628 Value reset, Value resetValue,
631 auto record = [&](
size_t fanOutBitPos, Value value,
size_t bitPos) {
635 for (
auto &path : *result) {
636 if (
auto blockArg = dyn_cast<BlockArgument>(path.fanIn.value)) {
649 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
650 if (failed(record(i, start, i)))
656 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
657 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
663 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
664 if (failed(record(i, enable, 0)))
672 Value to,
size_t toBitPos,
673 SmallVectorImpl<OpenPath> &results) {
674 auto leader =
ec.getOrInsertLeaderValue({to, toBitPos});
677 auto newLeader =
ec.unionSets({to, toBitPos}, {from, fromBitPos});
678 assert(leader == *newLeader);
683 SmallVectorImpl<OpenPath> &results) {
687 for (
auto &path : *result) {
689 newPath.delay += delay;
690 results.push_back(newPath);
696 SmallVectorImpl<OpenPath> &results) {
701 SmallVectorImpl<OpenPath> &results) {
706 SmallVectorImpl<OpenPath> &results) {
711 SmallVectorImpl<OpenPath> &results) {
716 SmallVectorImpl<OpenPath> &results) {
718 if (failed(
addEdge(op.getCond(), 0, 1, results)) ||
719 failed(
addEdge(op.getTrueValue(), bitPos, 1, results)) ||
720 failed(
addEdge(op.getFalseValue(), bitPos, 1, results)))
727 SmallVectorImpl<OpenPath> &results) {
730 bitPos + op.getLowBit(), results);
735 SmallVectorImpl<OpenPath> &results) {
741 SmallVectorImpl<OpenPath> &results) {
747 SmallVectorImpl<OpenPath> &results) {
748 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
753 SmallVectorImpl<OpenPath> &results) {
754 auto moduleName = op.getReferencedModuleNameAttr();
755 auto value = op->getResult(resultNum);
759 if (!
ctx->instanceGraph)
760 return markFanIn(value, bitPos, results);
763 auto *node =
ctx->instanceGraph->lookup(moduleName);
764 assert(node &&
"module not found");
768 if (!isa<hw::HWModuleOp>(node->getModule()))
769 return markFanIn(value, bitPos, results);
771 auto *localVisitor =
ctx->getAndWaitLocalVisitor(moduleName);
772 auto *fanInIt = localVisitor->fromOutputPortToFanIn.find({resultNum, bitPos});
775 if (fanInIt == localVisitor->fromOutputPortToFanIn.end())
778 const auto &fanIns = fanInIt->second;
780 for (
auto &[fanInPoint, delayAndHistory] : fanIns) {
781 auto [delay, history] = delayAndHistory;
786 auto arg = dyn_cast<BlockArgument>(fanInPoint.value);
790 if (
ctx->doTraceDebugPoints()) {
793 p.object.instancePath =
794 instancePathCache->prependInstance(op, p.object.instancePath);
798 DebugPoint({}, value, bitPos, delay,
"output port"), newHistory);
801 results.emplace_back(newPath, fanInPoint.value, fanInPoint.bitPos, delay,
811 for (
auto path : *result) {
813 if (
ctx->doTraceDebugPoints()) {
817 p.object.instancePath =
818 instancePathCache->prependInstance(op, p.object.instancePath);
819 p.delay += path.delay;
822 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
830 results.push_back(path);
838 SmallVectorImpl<OpenPath> &results) {
840 size_t newBitPos = bitPos;
841 for (
auto operand : llvm::reverse(op.getInputs())) {
843 if (newBitPos >= size) {
850 llvm::report_fatal_error(
"Should not reach here");
855 SmallVectorImpl<OpenPath> &results) {
856 auto size = op->getNumOperands();
857 auto cost = llvm::Log2_64_Ceil(size);
859 for (
auto operand : op->getOperands())
860 if (failed(
addEdge(operand, bitPos, cost, results)))
868 SmallVectorImpl<OpenPath> &results) {
873 SmallVectorImpl<OpenPath> &results) {
874 assert(arg.getOwner() == module.getBodyBlock());
877 auto newHistory =
ctx->doTraceDebugPoints()
879 DebugPoint({}, arg, bitPos, 0,
"input port"), {})
881 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
882 results.push_back(newPoint);
888 if (
ec.contains({value, bitPos})) {
889 auto leader =
ec.findLeader({value, bitPos});
891 if (*leader != std::pair(value, bitPos)) {
898 return ArrayRef<OpenPath>(it->second);
900 SmallVector<OpenPath> results;
901 if (failed(
visitValue(value, bitPos, results)))
907 llvm::dbgs() << value <<
"[" << bitPos <<
"] "
908 <<
"Found " << results.size() <<
" paths\n";
909 llvm::dbgs() <<
"====Paths:\n";
910 for (
auto &path : results) {
911 path.print(llvm::dbgs());
912 llvm::dbgs() <<
"\n";
914 llvm::dbgs() <<
"====\n";
917 auto insertedResult =
918 cachedResults.try_emplace({value, bitPos}, std::move(results));
919 assert(insertedResult.second);
920 return ArrayRef<OpenPath>(insertedResult.first->second);
924 SmallVectorImpl<OpenPath> &results) {
926 llvm::dbgs() <<
"Visiting: ";
927 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
930 if (
auto blockArg = dyn_cast<mlir::BlockArgument>(value))
931 return visit(blockArg, bitPos, results);
933 auto *op = value.getDefiningOp();
935 TypeSwitch<Operation *, LogicalResult>(op)
939 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
941 size_t idx = results.size();
942 auto result =
visit(op, bitPos, results);
943 if (
ctx->doTraceDebugPoints())
944 if (
auto name = op->template getAttrOfType<StringAttr>(
947 for (
auto i = idx, e = results.size(); i < e; ++i) {
948 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
951 debugPoint, results[i].history);
952 results[i].history = newHistory;
957 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
958 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
961 .Default([&](
auto op) {
return visitDefault(op, bitPos, results); });
966 const auto *childVisitor =
967 ctx->getAndWaitLocalVisitor(instance.getReferencedModuleNameAttr());
973 for (
const auto &[
object, openPaths] :
974 childVisitor->getFromInputPortToFanOut()) {
975 auto [arg, argBitPos] = object;
976 for (
auto [point, delayAndHistory] : openPaths) {
977 auto [instancePath, fanOut, fanOutBitPos] = point;
978 auto [delay, history] = delayAndHistory;
983 instance.getOperand(arg.getArgNumber()), argBitPos);
984 if (failed(computedResults))
987 for (
auto &result : *computedResults) {
988 auto newHistory =
ctx->doTraceDebugPoints()
993 p.object.instancePath = newPath;
994 p.delay += result.delay;
998 if (
auto newPort = dyn_cast<BlockArgument>(result.fanIn.value)) {
1000 {newPath, fanOut, fanOutBitPos}, result.delay + delay, newHistory,
1003 fanOutResults[{newPath, fanOut, fanOutBitPos}].emplace_back(
1004 newPath, result.fanIn.value, result.fanIn.bitPos,
1005 result.delay + delay,
1007 newHistory, result.history)
1015 for (
auto instance : instance->getResults()) {
1016 for (
size_t i = 0, e =
getBitWidth(instance); i < e; ++i) {
1018 if (failed(computedResults))
1026 for (OpOperand &operand : output->getOpOperands()) {
1027 for (
size_t i = 0, e =
getBitWidth(operand.get()); i < e; ++i) {
1028 auto &recordOutput =
1031 if (failed(computedResults))
1033 for (
const auto &result : *computedResults) {
1043 LLVM_DEBUG({
ctx->notifyStart(module.getModuleNameAttr()); });
1045 for (
auto blockArgument :
module.getBodyBlock()->getArguments())
1046 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
1049 auto walkResult =
module->walk([&](Operation *op) {
1051 mlir::TypeSwitch<Operation *, LogicalResult>(op)
1052 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
1053 return markRegFanOut(op, op.getNext(), op.getReset(),
1054 op.getResetValue());
1056 .Case<seq::CompRegOp>([&](
auto op) {
1057 return markRegFanOut(op, op.getInput(), op.getReset(),
1058 op.getResetValue());
1060 .Case<seq::FirMemWriteOp>([&](
auto op) {
1062 return markRegFanOut(op.getMemory(), op.getData(), {}, {},
1065 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
1067 return markRegFanOut(op.getMemory(), op.getWriteData(), {}, {},
1074 for (
size_t i = 0, e =
getBitWidth(op); i < e; ++i)
1075 if (failed(getOrComputeResults(op, i)))
1079 .Case<hw::InstanceOp, hw::OutputOp>(
1080 [&](
auto op) {
return initializeAndRun(op); })
1081 .Default([](
auto op) {
return success(); });
1083 return WalkResult::interrupt();
1084 return WalkResult::advance();
1088 std::lock_guard<std::mutex> lock(mutex);
1092 LLVM_DEBUG({ ctx->
notifyEnd(module.getModuleNameAttr()); });
1093 return failure(walkResult.wasInterrupted());
1104 return it->second.get();
1111 visitor->waitUntilDone();
1120 Impl(Operation *module, mlir::AnalysisManager &am,
1121 const LongestPathAnalysisOption &option);
1130 getResults(Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1132 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory =
1135 template <
bool elaborate>
1137 SmallVectorImpl<DataflowPath> &results)
const;
1139 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1141 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1147 const Object &originalObject, Value value,
size_t bitPos,
1148 SmallVectorImpl<DataflowPath> &results,
1150 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const;
1157 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1159 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1161 instancePathCache, debugPointFactory);
1165 const Object &originalObject, Value value,
size_t bitPos,
1166 SmallVectorImpl<DataflowPath> &results,
1168 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1169 auto parentHWModule =
1171 if (!parentHWModule)
1172 return mlir::emitError(value.getLoc())
1173 <<
"query value is not in a HWModuleOp";
1174 auto *localVisitor = ctx.
getLocalVisitor(parentHWModule.getModuleNameAttr());
1178 size_t oldIndex = results.size();
1184 llvm::dbgs() <<
"Running " << parentHWModule.getModuleNameAttr() <<
" "
1185 << value <<
" " << bitPos <<
"\n";
1188 for (
auto &path : localVisitor->getResults(value, bitPos)) {
1189 auto arg = dyn_cast<BlockArgument>(path.fanIn.value);
1190 if (!arg || localVisitor->isTopLevel()) {
1192 results.push_back({originalObject, path, parentHWModule});
1196 auto newObject = originalObject;
1197 assert(node &&
"If an instance graph is not available, localVisitor must "
1199 for (
auto *inst : node->uses()) {
1200 auto startIndex = results.size();
1201 if (instancePathCache)
1203 originalObject.instancePath, inst->getInstance());
1205 auto result = getResultsImpl(
1206 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1207 path.fanIn.bitPos, results, instancePathCache, debugPointFactory);
1210 for (
auto i = startIndex, e = results.size(); i < e; ++i)
1211 results[i].setDelay(results[i].getDelay() + path.delay);
1219template <
bool elaborate>
1221 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1222 auto collectClosedPaths = [&](StringAttr name,
1224 if (!isAnalysisAvailable(name))
1227 for (
auto &[point, state] : visitor->getFanOutResults())
1228 for (
const auto &dataFlow : state) {
1229 if constexpr (elaborate) {
1233 visitor->getHWModuleOp(), top);
1234 for (
auto &instancePath : topToRoot) {
1235 results.emplace_back(point, dataFlow,
1237 results.back().prependPaths(*visitor->getInstancePathCache(),
1238 visitor->getDebugPointFactory(),
1242 results.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1250 for (
auto *child : llvm::post_order(node))
1251 collectClosedPaths(child->getModule().getModuleNameAttr(), node);
1253 collectClosedPaths(moduleName);
1260 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1265 for (
auto &[key, value] : visitor->getFromInputPortToFanOut()) {
1266 auto [arg, argBitPos] = key;
1267 for (
auto [point, delayAndHistory] : value) {
1268 auto [path, start, startBitPos] = point;
1269 auto [delay, history] = delayAndHistory;
1270 results.emplace_back(
Object(path, start, startBitPos),
1271 OpenPath({}, arg, argBitPos, delay, history),
1272 visitor->getHWModuleOp());
1280 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1285 for (
auto &[key, value] : visitor->getFromOutputPortToFanIn()) {
1286 auto [resultNum, bitPos] = key;
1287 for (
auto [point, delayAndHistory] : value) {
1288 auto [path, start, startBitPos] = point;
1289 auto [delay, history] = delayAndHistory;
1290 results.emplace_back(std::make_pair(resultNum, bitPos),
1291 OpenPath(path, start, startBitPos, delay, history),
1292 visitor->getHWModuleOp());
1300 const LongestPathAnalysisOption &option)
1301 : ctx(isa<
mlir::ModuleOp>(moduleOp)
1305 if (
auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1307 llvm::report_fatal_error(
"Failed to run longest path analysis");
1308 }
else if (
auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1310 llvm::report_fatal_error(
"Failed to run longest path analysis");
1312 llvm::report_fatal_error(
"Analysis scheduled on invalid operation");
1319 std::make_unique<LocalVisitor>(module, &ctx)});
1321 it.first->second->setTopLevel();
1322 return it.first->second->initializeAndRun();
1328 module->getAttrOfType<FlatSymbolRefAttr>(getTopModuleNameAttrName());
1331 llvm::SetVector<Operation *> visited;
1334 auto *topNode = instanceGraph->
lookup(topNameAttr.getAttr());
1335 if (!topNode || !topNode->getModule() ||
1336 !isa<hw::HWModuleOp>(topNode->getModule())) {
1337 module.emitError() << "top module not found in instance graph "
1343 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1344 if (failed(inferredResults))
1345 return inferredResults;
1347 for (
auto *node : *inferredResults) {
1348 if (
auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1349 topModules.push_back(top);
1353 SmallVector<igraph::InstanceGraphNode *> worklist;
1354 for (
auto topNode : topModules)
1355 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1358 while (!worklist.empty()) {
1359 auto *node = worklist.pop_back_val();
1360 assert(node &&
"node should not be null");
1361 auto op = node->getModule();
1362 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1365 for (
auto *child : *node) {
1366 auto childOp = child->getInstance();
1367 if (!childOp || childOp->hasAttr(
"doNotPrint"))
1370 worklist.push_back(child->getTarget());
1376 for (
auto module : topModules) {
1377 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1378 for (
auto *node : llvm::post_order(topNode))
1379 if (node && node->getModule())
1380 if (
auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1381 if (visited.contains(hwMod))
1383 {hwMod.getModuleNameAttr(),
1384 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1387 ctx.
localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1390 return mlir::failableParallelForEach(
1392 [&](
auto &it) { return it.second->initializeAndRun(); });
1396 StringAttr moduleName)
const {
1405 SmallVector<DataflowPath> results;
1409 int64_t totalDelay = 0;
1410 for (
size_t i = 0; i < bitWidth; ++i) {
1413 auto result = getResults(value, i, results);
1417 int64_t maxDelay = 0;
1418 for (
auto &path : results)
1419 maxDelay = std::max(maxDelay, path.getDelay());
1420 totalDelay += maxDelay;
1422 return llvm::divideCeil(totalDelay, bitWidth);
1426 SmallVector<DataflowPath> results;
1430 int64_t maxDelay = 0;
1431 for (
size_t i = 0; i < bitWidth; ++i) {
1434 auto result = getResults(value, i, results);
1438 for (
auto &path : results)
1439 maxDelay = std::max(maxDelay, path.getDelay());
1448LongestPathAnalysis::~LongestPathAnalysis() {
delete impl; }
1450LongestPathAnalysis::LongestPathAnalysis(
1451 Operation *moduleOp, mlir::AnalysisManager &am,
1453 : impl(new
Impl(moduleOp, am, option)), ctx(moduleOp->getContext()) {}
1450LongestPathAnalysis::LongestPathAnalysis( {
…}
1456 return impl->isAnalysisAvailable(moduleName);
1460 return impl->getAverageMaxDelay(value);
1464 return impl->getMaxDelay(value);
1469 SmallVectorImpl<DataflowPath> &results,
1470 bool elaboratePaths)
const {
1472 return impl->getClosedPaths<
true>(moduleName, results);
1473 return impl->getClosedPaths<
false>(moduleName, results);
1477 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1478 return impl->getOpenPathsFromInputPortsToInternal(moduleName, results);
1482 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1483 return impl->getOpenPathsFromInternalToOutputPorts(moduleName, results);
1488 SmallVectorImpl<DataflowPath> &results,
1489 bool elaboratePaths)
const {
1500 return impl->getTopModules();
1518 llvm::DenseSet<DataflowPath::FanOutType> seen;
1519 for (
size_t i = 0; i <
paths.size(); ++i) {
1520 if (seen.insert(
paths[i].getFanOut()).second)
1521 paths[seen.size() - 1] = std::move(
paths[i]);
1523 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)
This class provides a thread-safe interface to access the analysis results.
circt::igraph::InstanceGraph * instanceGraph
const LocalVisitor * getLocalVisitor(StringAttr name) const
void notifyEnd(StringAttr name)
bool doTraceDebugPoints() const
const LongestPathAnalysisOption & option
llvm::sys::SmartMutex< true > mutex
llvm::MapVector< StringAttr, std::unique_ptr< LocalVisitor > > localVisitors
Context(igraph::InstanceGraph *instanceGraph, const LongestPathAnalysisOption &option)
llvm::SetVector< StringAttr > running
const LocalVisitor * getAndWaitLocalVisitor(StringAttr name) const
void notifyStart(StringAttr name)
hw::HWModuleOp getHWModuleOp() const
LogicalResult markRegFanOut(Value fanOut, Value start, Value reset={}, Value resetValue={}, Value enable={})
const auto & getFanOutResults() const
const auto & getFromInputPortToFanOut() const
LogicalResult addEdge(Value to, size_t toBitPos, int64_t delay, SmallVectorImpl< OpenPath > &results)
LogicalResult visitValue(Value value, size_t bitPos, SmallVectorImpl< OpenPath > &results)
ArrayRef< OpenPath > getResults(Value value, size_t bitPos) const
LogicalResult addLogicOp(Operation *op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::unique_ptr< llvm::ImmutableListFactory< DebugPoint > > debugPointFactory
DenseMap< std::pair< Value, size_t >, std::pair< Value, size_t > > ecMap
LogicalResult visitDefault(Operation *op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
llvm::MapVector< Object, std::pair< int64_t, llvm::ImmutableList< DebugPoint > > > ObjectToMaxDistance
DenseMap< std::pair< Value, size_t >, SmallVector< OpenPath > > cachedResults
std::pair< Value, size_t > findLeader(Value value, size_t bitpos) const
llvm::ImmutableListFactory< DebugPoint > * getDebugPointFactory() const
LogicalResult visit(seq::FirMemReadOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
LogicalResult markEquivalent(Value from, size_t fromBitPos, Value to, size_t toBitPos, SmallVectorImpl< OpenPath > &results)
llvm::MapVector< std::pair< BlockArgument, size_t >, ObjectToMaxDistance > fromInputPortToFanOut
FailureOr< ArrayRef< OpenPath > > getOrComputeResults(Value value, size_t bitPos)
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
LogicalResult visit(hw::ConstantOp op, size_t bitPos, SmallVectorImpl< OpenPath > &results)
std::condition_variable cv
void putUnclosedResult(const Object &object, int64_t delay, llvm::ImmutableList< DebugPoint > history, ObjectToMaxDistance &objectToMaxDistance)
std::unique_ptr< circt::igraph::InstancePathCache > instancePathCache
circt::igraph::InstancePathCache * getInstancePathCache() const
LocalVisitor(hw::HWModuleOp module, Context *ctx)
void waitUntilDone() const
const OpenPath & getPath() const
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
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.
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.
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
void print(llvm::raw_ostream &os) const
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
void print(llvm::raw_ostream &os) const
OpenPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
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.