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> saved;
92 llvm::enumerate(ArrayRef(results).drop_front(startIndex))) {
93 auto &slot = saved[keyFn(path)];
95 slot = startIndex + i + 1;
98 if (delayFn(results[slot - 1]) < delayFn(path))
99 results[slot - 1] = path;
102 results.resize(saved.size() + startIndex);
106 size_t startIndex = 0) {
107 deduplicatePathsImpl<OpenPath, Object>(
108 results, startIndex, [](
const auto &path) {
return path.fanIn; },
109 [](
const auto &path) {
return path.delay; });
113 size_t startIndex = 0) {
115 std::pair<DataflowPath::FanOutType, Object>>(
117 [](
const DataflowPath &path) {
118 return std::pair(path.getFanOut(), path.getFanIn());
120 [](
const DataflowPath &path) {
return path.getDelay(); });
123static llvm::ImmutableList<DebugPoint>
124mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
125 llvm::ImmutableList<DebugPoint> list,
126 llvm::function_ref<DebugPoint(DebugPoint)> fn) {
129 auto &head = list.getHead();
130 return debugPointFactory->add(fn(head),
131 mapList(debugPointFactory, list.getTail(), fn));
134static llvm::ImmutableList<DebugPoint>
135concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
136 llvm::ImmutableList<DebugPoint> lhs,
137 llvm::ImmutableList<DebugPoint> rhs) {
140 return debugPointFactory->add(
141 lhs.getHead(),
concatList(debugPointFactory, lhs.getTail(), rhs));
145 if (
auto arg = dyn_cast<BlockArgument>(value)) {
146 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
149 return StringAttr::get(value.getContext(),
"<unknown-argument>");
151 return op.getArgName(arg.getArgNumber());
153 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
155 [](
auto op) {
return op.getNameAttr(); })
156 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
158 str += op.getInstanceName();
160 str += cast<StringAttr>(
161 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
162 return StringAttr::get(op.getContext(), str);
164 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
165 llvm::SmallString<16> str;
166 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
168 return StringAttr::get(value.getContext(), str);
170 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
171 llvm::SmallString<16> str;
172 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
174 return StringAttr::get(value.getContext(), str);
176 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
177 llvm::SmallString<16> str;
178 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
179 str +=
".write_port";
180 return StringAttr::get(value.getContext(), str);
182 .Default([&](
auto op) {
183 if (
auto name = op->template getAttrOfType<StringAttr>(
"sv.namehint"))
185 llvm::errs() <<
"Unknown op: " << *op <<
"\n";
186 return StringAttr::get(value.getContext(),
"");
192 llvm::ImmutableList<DebugPoint> history = {},
193 StringRef comment =
"") {
194 std::string pathString;
195 llvm::raw_string_ostream osPath(pathString);
196 object.instancePath.print(osPath);
197 os <<
"Object(" << pathString <<
"." <<
getNameImpl(
object.value).getValue()
198 <<
"[" <<
object.bitPos <<
"]";
200 os <<
", delay=" << delay;
201 if (!history.isEmpty()) {
203 llvm::interleaveComma(history, os, [&](DebugPoint p) { p.print(os); });
206 if (!comment.empty())
207 os <<
", comment=\"" << comment <<
"\"";
211using namespace circt;
218void OpenPath::print(llvm::raw_ostream &os)
const {
222void DebugPoint::print(llvm::raw_ostream &os)
const {
228void DataflowPath::printFanOut(llvm::raw_ostream &os) {
229 if (
auto *
object = std::get_if<Object>(&fanOut)) {
232 auto &[resultNumber, bitPos] =
233 *std::get_if<std::pair<size_t, size_t>>(&fanOut);
234 auto outputPortName = root.getOutputName(resultNumber);
235 os <<
"Object($root." << outputPortName <<
"[" << bitPos <<
"])";
239void DataflowPath::print(llvm::raw_ostream &os) {
240 os <<
"root=" << root.getModuleName() <<
", ";
254 instancePath = cache.
concatPath(path, instancePath);
260 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
263 if (debugPointFactory)
264 this->history =
mapList(debugPointFactory, this->history,
278 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
280 this->path.prependPaths(cache, debugPointFactory, path);
283 assert(root &&
"root is not a hw::HWModuleOp");
288 if (
auto *
object = std::get_if<Object>(&fanOut))
289 object->prependPaths(cache, path);
294Location DataflowPath::getFanOutLoc() {
296 if (
auto *
object = std::get_if<Object>(&fanOut))
297 return object->value.getLoc();
300 return root.getOutputLoc(std::get<std::pair<size_t, size_t>>(fanOut).first);
308 llvm::json::Array result;
309 for (
auto op : path) {
310 llvm::json::Object obj;
311 obj[
"instance_name"] = op.getInstanceName();
312 obj[
"module_name"] = op.getReferencedModuleNames()[0];
313 result.push_back(std::move(obj));
319 return llvm::json::Object{
320 {
"instance_path",
toJSON(
object.instancePath)},
322 {
"bit_pos",
object.bitPos},
326static llvm::json::Value
toJSON(
const DataflowPath::FanOutType &path,
329 if (
auto *
object = std::get_if<circt::aig::Object>(&path))
332 auto &[resultNumber, bitPos] = *std::get_if<std::pair<size_t, size_t>>(&path);
333 return llvm::json::Object{
334 {
"instance_path", {}},
335 {
"name", root.getOutputName(resultNumber)},
340static llvm::json::Value
toJSON(
const DebugPoint &point) {
341 return llvm::json::Object{
342 {
"object",
toJSON(point.object)},
343 {
"delay", point.delay},
344 {
"comment", point.comment},
348static llvm::json::Value
toJSON(
const OpenPath &path) {
349 llvm::json::Array history;
350 for (
auto &point : path.history)
351 history.push_back(
toJSON(point));
352 return llvm::json::Object{{
"fan_in",
toJSON(path.fanIn)},
353 {
"delay", path.delay},
354 {
"history", std::move(history)}};
358 return llvm::json::Object{
361 {
"root", path.
getRoot().getModuleName()},
375 const LongestPathAnalysisOption &
option)
378 std::lock_guard<llvm::sys::SmartMutex<true>> lock(
mutex);
380 llvm::dbgs() <<
"[Timing] " << name <<
" started. running=[";
382 llvm::dbgs() << name <<
" ";
383 llvm::dbgs() <<
"]\n";
387 std::lock_guard<llvm::sys::SmartMutex<true>> lock(
mutex);
390 llvm::dbgs() <<
"[Timing] " << name <<
" finished. running=[";
392 llvm::dbgs() << name <<
" ";
393 llvm::dbgs() <<
"]\n";
432 ArrayRef<OpenPath>
getResults(Value value,
size_t bitPos)
const;
436 llvm::MapVector<Object,
437 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
458 llvm::ImmutableList<DebugPoint> history,
475 LogicalResult
visitValue(Value value,
size_t bitPos,
476 SmallVectorImpl<OpenPath> &results);
478 LogicalResult
visit(mlir::BlockArgument argument,
size_t bitPos,
479 SmallVectorImpl<OpenPath> &results);
480 LogicalResult
visit(hw::InstanceOp op,
size_t bitPos,
size_t resultNum,
481 SmallVectorImpl<OpenPath> &results);
484 LogicalResult
visit(hw::WireOp op,
size_t bitPos,
485 SmallVectorImpl<OpenPath> &results);
487 SmallVectorImpl<OpenPath> &results);
489 SmallVectorImpl<OpenPath> &results);
490 LogicalResult
visit(comb::ReplicateOp op,
size_t bitPos,
491 SmallVectorImpl<OpenPath> &results);
494 llvm::EquivalenceClasses<std::pair<Value, size_t>>
ec;
495 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>>
ecMap;
496 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
497 return ec.getLeaderValue({value, bitpos});
499 LogicalResult
markEquivalent(Value from,
size_t fromBitPos, Value to,
501 SmallVectorImpl<OpenPath> &results);
504 LogicalResult
visit(aig::AndInverterOp op,
size_t bitPos,
505 SmallVectorImpl<OpenPath> &results);
507 SmallVectorImpl<OpenPath> &results);
509 SmallVectorImpl<OpenPath> &results);
511 SmallVectorImpl<OpenPath> &results);
513 SmallVectorImpl<OpenPath> &results);
514 LogicalResult
addLogicOp(Operation *op,
size_t bitPos,
515 SmallVectorImpl<OpenPath> &results);
519 SmallVectorImpl<OpenPath> &results) {
524 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos,
525 SmallVectorImpl<OpenPath> &results) {
530 SmallVectorImpl<OpenPath> &results) {
534 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos,
535 SmallVectorImpl<OpenPath> &results) {
539 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos,
540 SmallVectorImpl<OpenPath> &results) {
544 LogicalResult
visitDefault(Operation *op,
size_t bitPos,
545 SmallVectorImpl<OpenPath> &results);
548 LogicalResult
addEdge(Value to,
size_t toBitPos, int64_t delay,
549 SmallVectorImpl<OpenPath> &results);
550 LogicalResult
markFanIn(Value value,
size_t bitPos,
551 SmallVectorImpl<OpenPath> &results);
552 LogicalResult
markRegFanOut(Value fanOut, Value start, Value reset = {},
553 Value resetValue = {}, Value enable = {});
572 mutable std::condition_variable
cv;
580 : module(module), ctx(ctx) {
582 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
584 ? std::make_unique<circt::igraph::InstancePathCache>(
591 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
592 auto leader =
ec.findLeader(valueAndBitPos);
593 if (leader !=
ec.member_end()) {
594 if (*leader != valueAndBitPos) {
596 return getResults(leader->first, leader->second);
608 llvm::ImmutableList<DebugPoint> history,
610 auto &slot = objectToMaxDistance[object];
611 if (slot.first >= delay && delay != 0)
613 slot = {delay, history};
618 std::unique_lock<std::mutex> lock(
mutex);
619 cv.wait(lock, [
this] {
return done.load(); });
623 Value reset, Value resetValue,
626 auto record = [&](
size_t fanOutBitPos, Value value,
size_t bitPos) {
630 for (
auto &path : *result) {
631 if (
auto blockArg = dyn_cast<BlockArgument>(path.fanIn.value)) {
644 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
645 if (failed(record(i, start, i)))
651 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
652 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
658 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
659 if (failed(record(i, enable, 0)))
667 Value to,
size_t toBitPos,
668 SmallVectorImpl<OpenPath> &results) {
669 auto leader =
ec.getOrInsertLeaderValue({to, toBitPos});
672 auto newLeader =
ec.unionSets({to, toBitPos}, {from, fromBitPos});
673 assert(leader == *newLeader);
678 SmallVectorImpl<OpenPath> &results) {
682 for (
auto &path : *result) {
684 newPath.delay += delay;
685 results.push_back(newPath);
691 SmallVectorImpl<OpenPath> &results) {
696 SmallVectorImpl<OpenPath> &results) {
701 SmallVectorImpl<OpenPath> &results) {
706 SmallVectorImpl<OpenPath> &results) {
711 SmallVectorImpl<OpenPath> &results) {
713 if (failed(
addEdge(op.getCond(), 0, 1, results)) ||
714 failed(
addEdge(op.getTrueValue(), bitPos, 1, results)) ||
715 failed(
addEdge(op.getFalseValue(), bitPos, 1, results)))
722 SmallVectorImpl<OpenPath> &results) {
725 bitPos + op.getLowBit(), results);
730 SmallVectorImpl<OpenPath> &results) {
736 SmallVectorImpl<OpenPath> &results) {
742 SmallVectorImpl<OpenPath> &results) {
743 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
748 SmallVectorImpl<OpenPath> &results) {
749 auto moduleName = op.getReferencedModuleNameAttr();
750 auto value = op->getResult(resultNum);
754 if (!
ctx->instanceGraph)
755 return markFanIn(value, bitPos, results);
758 auto *node =
ctx->instanceGraph->lookup(moduleName);
759 assert(node &&
"module not found");
763 if (!isa<hw::HWModuleOp>(node->getModule()))
764 return markFanIn(value, bitPos, results);
766 auto *localVisitor =
ctx->getAndWaitLocalVisitor(moduleName);
767 auto *fanInIt = localVisitor->fromOutputPortToFanIn.find({resultNum, bitPos});
770 if (fanInIt == localVisitor->fromOutputPortToFanIn.end())
773 const auto &fanIns = fanInIt->second;
775 for (
auto &[fanInPoint, delayAndHistory] : fanIns) {
776 auto [delay, history] = delayAndHistory;
781 auto arg = dyn_cast<BlockArgument>(fanInPoint.value);
785 if (
ctx->doTraceDebugPoints()) {
788 p.object.instancePath =
789 instancePathCache->prependInstance(op, p.object.instancePath);
793 DebugPoint({}, value, bitPos, delay,
"output port"), newHistory);
796 results.emplace_back(newPath, fanInPoint.value, fanInPoint.bitPos, delay,
806 for (
auto path : *result) {
808 if (
ctx->doTraceDebugPoints()) {
812 p.object.instancePath =
813 instancePathCache->prependInstance(op, p.object.instancePath);
814 p.delay += path.delay;
817 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
825 results.push_back(path);
833 SmallVectorImpl<OpenPath> &results) {
835 size_t newBitPos = bitPos;
836 for (
auto operand : llvm::reverse(op.getInputs())) {
838 if (newBitPos >= size) {
845 llvm::report_fatal_error(
"Should not reach here");
850 SmallVectorImpl<OpenPath> &results) {
851 auto size = op->getNumOperands();
852 auto cost = llvm::Log2_64_Ceil(size);
854 for (
auto operand : op->getOperands())
855 if (failed(
addEdge(operand, bitPos, cost, results)))
863 SmallVectorImpl<OpenPath> &results) {
868 SmallVectorImpl<OpenPath> &results) {
869 assert(arg.getOwner() == module.getBodyBlock());
872 auto newHistory =
ctx->doTraceDebugPoints()
874 DebugPoint({}, arg, bitPos, 0,
"input port"), {})
876 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
877 results.push_back(newPoint);
883 if (
ec.contains({value, bitPos})) {
884 auto leader =
ec.findLeader({value, bitPos});
886 if (*leader != std::pair(value, bitPos)) {
893 return ArrayRef<OpenPath>(it->second);
895 SmallVector<OpenPath> results;
896 if (failed(
visitValue(value, bitPos, results)))
902 llvm::dbgs() << value <<
"[" << bitPos <<
"] "
903 <<
"Found " << results.size() <<
" paths\n";
904 llvm::dbgs() <<
"====Paths:\n";
905 for (
auto &path : results) {
906 path.print(llvm::dbgs());
907 llvm::dbgs() <<
"\n";
909 llvm::dbgs() <<
"====\n";
912 auto insertedResult =
913 cachedResults.try_emplace({value, bitPos}, std::move(results));
914 assert(insertedResult.second);
915 return ArrayRef<OpenPath>(insertedResult.first->second);
919 SmallVectorImpl<OpenPath> &results) {
921 llvm::dbgs() <<
"Visiting: ";
922 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
925 if (
auto blockArg = dyn_cast<mlir::BlockArgument>(value))
926 return visit(blockArg, bitPos, results);
928 auto *op = value.getDefiningOp();
930 TypeSwitch<Operation *, LogicalResult>(op)
934 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
936 size_t idx = results.size();
937 auto result =
visit(op, bitPos, results);
938 if (
ctx->doTraceDebugPoints())
939 if (
auto name = op->template getAttrOfType<StringAttr>(
942 for (
auto i = idx, e = results.size(); i < e; ++i) {
943 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
946 debugPoint, results[i].history);
947 results[i].history = newHistory;
952 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
953 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
956 .Default([&](
auto op) {
return visitDefault(op, bitPos, results); });
961 const auto *childVisitor =
962 ctx->getAndWaitLocalVisitor(instance.getReferencedModuleNameAttr());
968 for (
const auto &[
object, openPaths] :
969 childVisitor->getFromInputPortToFanOut()) {
970 auto [arg, argBitPos] = object;
971 for (
auto [point, delayAndHistory] : openPaths) {
972 auto [instancePath, fanOut, fanOutBitPos] = point;
973 auto [delay, history] = delayAndHistory;
978 instance.getOperand(arg.getArgNumber()), argBitPos);
979 if (failed(computedResults))
982 for (
auto &result : *computedResults) {
983 auto newHistory =
ctx->doTraceDebugPoints()
988 p.object.instancePath = newPath;
989 p.delay += result.delay;
993 if (
auto newPort = dyn_cast<BlockArgument>(result.fanIn.value)) {
995 {newPath, fanOut, fanOutBitPos}, result.delay + delay, newHistory,
999 newPath, result.fanIn.value, result.fanIn.bitPos,
1000 result.delay + delay,
1002 newHistory, result.history)
1010 for (
auto instance : instance->getResults()) {
1011 for (
size_t i = 0, e =
getBitWidth(instance); i < e; ++i) {
1013 if (failed(computedResults))
1021 for (OpOperand &operand : output->getOpOperands()) {
1022 for (
size_t i = 0, e =
getBitWidth(operand.get()); i < e; ++i) {
1023 auto &recordOutput =
1026 if (failed(computedResults))
1028 for (
const auto &result : *computedResults) {
1038 LLVM_DEBUG({
ctx->notifyStart(module.getModuleNameAttr()); });
1040 for (
auto blockArgument :
module.getBodyBlock()->getArguments())
1041 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
1044 auto walkResult =
module->walk([&](Operation *op) {
1046 mlir::TypeSwitch<Operation *, LogicalResult>(op)
1047 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
1048 return markRegFanOut(op, op.getNext(), op.getReset(),
1049 op.getResetValue());
1051 .Case<seq::CompRegOp>([&](
auto op) {
1052 return markRegFanOut(op, op.getInput(), op.getReset(),
1053 op.getResetValue());
1055 .Case<seq::FirMemWriteOp>([&](
auto op) {
1057 return markRegFanOut(op.getMemory(), op.getData(), {}, {},
1060 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
1062 return markRegFanOut(op.getMemory(), op.getWriteData(), {}, {},
1069 for (
size_t i = 0, e =
getBitWidth(op); i < e; ++i)
1070 if (failed(getOrComputeResults(op, i)))
1074 .Case<hw::InstanceOp, hw::OutputOp>(
1075 [&](
auto op) {
return initializeAndRun(op); })
1076 .Default([](
auto op) {
return success(); });
1078 return WalkResult::interrupt();
1079 return WalkResult::advance();
1083 std::lock_guard<std::mutex> lock(mutex);
1087 LLVM_DEBUG({ ctx->
notifyEnd(module.getModuleNameAttr()); });
1088 return failure(walkResult.wasInterrupted());
1099 return it->second.get();
1106 visitor->waitUntilDone();
1115 Impl(Operation *module, mlir::AnalysisManager &am,
1116 const LongestPathAnalysisOption &option);
1125 getResults(Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1127 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory =
1130 template <
bool elaborate>
1132 SmallVectorImpl<DataflowPath> &results)
const;
1134 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1136 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1142 const Object &originalObject, Value value,
size_t bitPos,
1143 SmallVectorImpl<DataflowPath> &results,
1145 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const;
1152 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1154 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1155 return getResultsImpl(Object({}, value, bitPos), value, bitPos, results,
1156 instancePathCache, debugPointFactory);
1160 const Object &originalObject, Value value,
size_t bitPos,
1161 SmallVectorImpl<DataflowPath> &results,
1163 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1164 auto parentHWModule =
1166 if (!parentHWModule)
1167 return mlir::emitError(value.getLoc())
1168 <<
"query value is not in a HWModuleOp";
1169 auto *localVisitor = ctx.
getLocalVisitor(parentHWModule.getModuleNameAttr());
1173 size_t oldIndex = results.size();
1179 llvm::dbgs() <<
"Running " << parentHWModule.getModuleNameAttr() <<
" "
1180 << value <<
" " << bitPos <<
"\n";
1183 for (
auto &path : localVisitor->getResults(value, bitPos)) {
1184 auto arg = dyn_cast<BlockArgument>(path.fanIn.value);
1185 if (!arg || localVisitor->isTopLevel()) {
1187 results.push_back({originalObject, path, parentHWModule});
1191 auto newObject = originalObject;
1192 assert(node &&
"If an instance graph is not available, localVisitor must "
1194 for (
auto *inst : node->uses()) {
1195 auto startIndex = results.size();
1196 if (instancePathCache)
1198 originalObject.instancePath, inst->getInstance());
1200 auto result = getResultsImpl(
1201 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1202 path.fanIn.bitPos, results, instancePathCache, debugPointFactory);
1205 for (
auto i = startIndex, e = results.size(); i < e; ++i)
1206 results[i].setDelay(results[i].getDelay() + path.delay);
1214template <
bool elaborate>
1216 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1217 auto collectClosedPaths = [&](StringAttr name,
1219 if (!isAnalysisAvailable(name))
1222 for (
auto &[point, state] : visitor->getFanOutResults())
1223 for (
const auto &dataFlow : state) {
1224 if constexpr (elaborate) {
1228 visitor->getHWModuleOp(), top);
1229 for (
auto &instancePath : topToRoot) {
1230 results.emplace_back(point, dataFlow,
1232 results.back().prependPaths(*visitor->getInstancePathCache(),
1233 visitor->getDebugPointFactory(),
1237 results.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1245 for (
auto *child : llvm::post_order(node))
1246 collectClosedPaths(child->getModule().getModuleNameAttr(), node);
1248 collectClosedPaths(moduleName);
1255 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1260 for (
auto &[key, value] : visitor->getFromInputPortToFanOut()) {
1261 auto [arg, argBitPos] = key;
1262 for (
auto [point, delayAndHistory] : value) {
1263 auto [path, start, startBitPos] = point;
1264 auto [delay, history] = delayAndHistory;
1265 results.emplace_back(Object(path, start, startBitPos),
1266 OpenPath({}, arg, argBitPos, delay, history),
1267 visitor->getHWModuleOp());
1275 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1280 for (
auto &[key, value] : visitor->getFromOutputPortToFanIn()) {
1281 auto [resultNum, bitPos] = key;
1282 for (
auto [point, delayAndHistory] : value) {
1283 auto [path, start, startBitPos] = point;
1284 auto [delay, history] = delayAndHistory;
1285 results.emplace_back(std::make_pair(resultNum, bitPos),
1286 OpenPath(path, start, startBitPos, delay, history),
1287 visitor->getHWModuleOp());
1295 const LongestPathAnalysisOption &option)
1296 : ctx(isa<
mlir::ModuleOp>(moduleOp)
1300 if (
auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1302 llvm::report_fatal_error(
"Failed to run longest path analysis");
1303 }
else if (
auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1305 llvm::report_fatal_error(
"Failed to run longest path analysis");
1307 llvm::report_fatal_error(
"Analysis scheduled on invalid operation");
1314 std::make_unique<LocalVisitor>(module, &ctx)});
1316 it.first->second->setTopLevel();
1317 return it.first->second->initializeAndRun();
1323 module->getAttrOfType<FlatSymbolRefAttr>(getTopModuleNameAttrName());
1326 llvm::SetVector<Operation *> visited;
1329 auto *topNode = instanceGraph->
lookup(topNameAttr.getAttr());
1330 if (!topNode || !topNode->getModule() ||
1331 !isa<hw::HWModuleOp>(topNode->getModule())) {
1332 module.emitError() << "top module not found in instance graph "
1338 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1339 if (failed(inferredResults))
1340 return inferredResults;
1342 for (
auto *node : *inferredResults) {
1343 if (
auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1344 topModules.push_back(top);
1348 SmallVector<igraph::InstanceGraphNode *> worklist;
1349 for (
auto topNode : topModules)
1350 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1353 while (!worklist.empty()) {
1354 auto *node = worklist.pop_back_val();
1355 assert(node &&
"node should not be null");
1356 auto op = node->getModule();
1357 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1360 for (
auto *child : *node) {
1361 auto childOp = child->getInstance();
1362 if (!childOp || childOp->hasAttr(
"doNotPrint"))
1365 worklist.push_back(child->getTarget());
1371 for (
auto module : topModules) {
1372 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1373 for (
auto *node : llvm::post_order(topNode))
1374 if (node && node->getModule())
1375 if (
auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1376 if (visited.contains(hwMod))
1378 {hwMod.getModuleNameAttr(),
1379 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1382 ctx.
localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1385 return mlir::failableParallelForEach(
1387 [&](
auto &it) { return it.second->initializeAndRun(); });
1391 StringAttr moduleName)
const {
1400 SmallVector<DataflowPath> results;
1404 int64_t totalDelay = 0;
1405 for (
size_t i = 0; i < bitWidth; ++i) {
1408 auto result = getResults(value, i, results);
1412 int64_t maxDelay = 0;
1413 for (
auto &path : results)
1414 maxDelay = std::max(maxDelay, path.getDelay());
1415 totalDelay += maxDelay;
1417 return llvm::divideCeil(totalDelay, bitWidth);
1421 SmallVector<DataflowPath> results;
1425 int64_t maxDelay = 0;
1426 for (
size_t i = 0; i < bitWidth; ++i) {
1429 auto result = getResults(value, i, results);
1433 for (
auto &path : results)
1434 maxDelay = std::max(maxDelay, path.getDelay());
1443LongestPathAnalysis::~LongestPathAnalysis() {
delete impl; }
1445LongestPathAnalysis::LongestPathAnalysis(
1446 Operation *moduleOp, mlir::AnalysisManager &am,
1447 const LongestPathAnalysisOption &option)
1448 : impl(new
Impl(moduleOp, am, option)), ctx(moduleOp->getContext()) {}
1450bool LongestPathAnalysis::isAnalysisAvailable(StringAttr moduleName)
const {
1451 return impl->isAnalysisAvailable(moduleName);
1454int64_t LongestPathAnalysis::getAverageMaxDelay(Value value)
const {
1455 return impl->getAverageMaxDelay(value);
1458int64_t LongestPathAnalysis::getMaxDelay(Value value)
const {
1459 return impl->getMaxDelay(value);
1463LongestPathAnalysis::getClosedPaths(StringAttr moduleName,
1464 SmallVectorImpl<DataflowPath> &results,
1465 bool elaboratePaths)
const {
1467 return impl->getClosedPaths<
true>(moduleName, results);
1468 return impl->getClosedPaths<
false>(moduleName, results);
1471LogicalResult LongestPathAnalysis::getOpenPathsFromInputPortsToInternal(
1472 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1473 return impl->getOpenPathsFromInputPortsToInternal(moduleName, results);
1476LogicalResult LongestPathAnalysis::getOpenPathsFromInternalToOutputPorts(
1477 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1478 return impl->getOpenPathsFromInternalToOutputPorts(moduleName, results);
1482LongestPathAnalysis::getAllPaths(StringAttr moduleName,
1483 SmallVectorImpl<DataflowPath> &results,
1484 bool elaboratePaths)
const {
1485 if (failed(getClosedPaths(moduleName, results, elaboratePaths)))
1487 if (failed(getOpenPathsFromInputPortsToInternal(moduleName, results)))
1489 if (failed(getOpenPathsFromInternalToOutputPorts(moduleName, results)))
1494ArrayRef<hw::HWModuleOp> LongestPathAnalysis::getTopModules()
const {
1495 return impl->getTopModules();
1502void LongestPathCollection::sortInDescendingOrder() {
1508void LongestPathCollection::sortAndDropNonCriticalPathsPerFanOut() {
1509 sortInDescendingOrder();
1513 llvm::DenseSet<DataflowPath::FanOutType> seen;
1514 for (
size_t i = 0; i < paths.size(); ++i) {
1515 if (seen.insert(paths[i].getFanOut()).second)
1516 paths[seen.size() - 1] = std::move(paths[i]);
1518 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 llvm::json::Value toJSON(const circt::igraph::InstancePath &path)
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
const FanOutType & getFanOut() const
hw::HWModuleOp getRoot() const
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.
int64_t getAverageMaxDelay(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 getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
int64_t getMaxDelay(Value value) const
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
LogicalResult initializeAndRun(mlir::ModuleOp module)
LogicalResult getResults(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results, circt::igraph::InstancePathCache *instancePathCache=nullptr, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory=nullptr) const
LogicalResult getOpenPathsFromInputPortsToInternal(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
bool isAnalysisAvailable(StringAttr moduleName) const
LogicalResult getOpenPathsFromInternalToOutputPorts(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
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.