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/LogicalResult.h"
63#include "llvm/Support/MathExtras.h"
64#include "llvm/Support/Mutex.h"
65#include "llvm/Support/raw_ostream.h"
66#include <condition_variable>
71#define DEBUG_TYPE "aig-longest-path-analysis"
76 if (
auto vecType = dyn_cast<seq::ClockType>(value.getType()))
78 if (
auto memory = dyn_cast<seq::FirMemType>(value.getType()))
79 return memory.getWidth();
80 return hw::getBitWidth(value.getType());
83template <
typename T,
typename Key>
86 llvm::function_ref<Key(
const T &)> keyFn,
87 llvm::function_ref<int64_t(
const T &)> delayFn) {
89 DenseMap<Key, size_t> saved;
91 llvm::enumerate(ArrayRef(results).drop_front(startIndex))) {
92 auto &slot = saved[keyFn(path)];
94 slot = startIndex + i + 1;
97 if (delayFn(results[slot - 1]) < delayFn(path))
98 results[slot - 1] = path;
101 results.resize(saved.size() + startIndex);
105 size_t startIndex = 0) {
106 deduplicatePathsImpl<OpenPath, Object>(
107 results, startIndex, [](
const auto &path) {
return path.fanIn; },
108 [](
const auto &path) {
return path.delay; });
112 size_t startIndex = 0) {
114 std::pair<DataflowPath::FanOutType, Object>>(
117 return std::pair(path.getFanOut(), path.getFanIn());
119 [](
const DataflowPath &path) {
return path.getDelay(); });
122static llvm::ImmutableList<DebugPoint>
123mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
124 llvm::ImmutableList<DebugPoint> list,
128 auto &head = list.getHead();
129 return debugPointFactory->add(fn(head),
130 mapList(debugPointFactory, list.getTail(), fn));
123mapList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory, {
…}
133static llvm::ImmutableList<DebugPoint>
134concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
135 llvm::ImmutableList<DebugPoint> lhs,
136 llvm::ImmutableList<DebugPoint> rhs) {
139 return debugPointFactory->add(
140 lhs.getHead(),
concatList(debugPointFactory, lhs.getTail(), rhs));
134concatList(llvm::ImmutableListFactory<DebugPoint> *debugPointFactory, {
…}
144 if (
auto arg = dyn_cast<BlockArgument>(value)) {
145 auto op = dyn_cast<hw::HWModuleOp>(arg.getParentBlock()->getParentOp());
148 return StringAttr::get(value.getContext(),
"<unknown-argument>");
150 return op.getArgName(arg.getArgNumber());
152 return TypeSwitch<Operation *, StringAttr>(value.getDefiningOp())
154 [](
auto op) {
return op.getNameAttr(); })
155 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
157 str += op.getInstanceName();
159 str += cast<StringAttr>(
160 op.getResultNamesAttr()[cast<OpResult>(value).getResultNumber()]);
161 return StringAttr::get(op.getContext(), str);
163 .Case<seq::FirMemReadOp>([&](seq::FirMemReadOp op) {
164 llvm::SmallString<16> str;
165 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
167 return StringAttr::get(value.getContext(), str);
169 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
170 llvm::SmallString<16> str;
171 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
173 return StringAttr::get(value.getContext(), str);
175 .Case<seq::FirMemOp>([&](seq::FirMemOp op) {
176 llvm::SmallString<16> str;
177 str += op.getMemory().getDefiningOp<seq::FirMemOp>().getNameAttr();
178 str +=
".write_port";
179 return StringAttr::get(value.getContext(), str);
181 .Default([&](
auto op) {
182 if (
auto name = op->template getAttrOfType<StringAttr>(
"sv.namehint"))
184 llvm::errs() <<
"Unknown op: " << *op <<
"\n";
185 return StringAttr::get(value.getContext(),
"");
191 llvm::ImmutableList<DebugPoint> history = {},
192 StringRef comment =
"") {
193 std::string pathString;
194 llvm::raw_string_ostream osPath(pathString);
195 object.instancePath.print(osPath);
196 os <<
"Object(" << pathString <<
"." <<
getNameImpl(
object.value).getValue()
197 <<
"[" <<
object.bitPos <<
"]";
199 os <<
", delay=" << delay;
200 if (!history.isEmpty()) {
202 llvm::interleaveComma(history, os, [&](
DebugPoint p) { p.
print(os); });
205 if (!comment.empty())
206 os <<
", comment=\"" << comment <<
"\"";
210using namespace circt;
228 if (
auto *
object = std::get_if<Object>(&
fanOut)) {
231 auto &[resultNumber, bitPos] =
232 *std::get_if<std::pair<size_t, size_t>>(&
fanOut);
233 auto outputPortName =
root.getOutputName(resultNumber);
234 os <<
"Object($root." << outputPortName <<
"[" << bitPos <<
"])";
239 os <<
"root=" <<
root.getModuleName() <<
", ";
259 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
262 if (debugPointFactory)
277 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
279 this->path.prependPaths(cache, debugPointFactory,
path);
282 assert(
root &&
"root is not a hw::HWModuleOp");
287 if (
auto *
object = std::get_if<Object>(&
fanOut))
288 object->prependPaths(cache,
path);
295 if (
auto *
object = std::get_if<Object>(&
fanOut))
296 return object->value.getLoc();
299 return root.getOutputLoc(std::get<std::pair<size_t, size_t>>(
fanOut).first);
313 : instanceGraph(instanceGraph), option(option) {}
315 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
316 running.insert(name);
317 llvm::dbgs() <<
"[Timing] " << name <<
" started. running=[";
318 for (
auto &name : running)
319 llvm::dbgs() << name <<
" ";
320 llvm::dbgs() <<
"]\n";
324 std::lock_guard<llvm::sys::SmartMutex<true>> lock(mutex);
325 running.remove(name);
327 llvm::dbgs() <<
"[Timing] " << name <<
" finished. running=[";
328 for (
auto &name : running)
329 llvm::dbgs() << name <<
" ";
330 llvm::dbgs() <<
"]\n";
334 const LocalVisitor *getLocalVisitor(StringAttr name)
const;
337 const LocalVisitor *getAndWaitLocalVisitor(StringAttr name)
const;
359 LogicalResult initializeAndRun();
361 void waitUntilDone()
const;
365 FailureOr<ArrayRef<OpenPath>> getOrComputeResults(Value value,
size_t bitPos);
369 ArrayRef<OpenPath> getResults(Value value,
size_t bitPos)
const;
374 std::pair<int64_t, llvm::ImmutableList<DebugPoint>>>;
386 return instancePathCache.get();
390 return debugPointFactory.get();
394 void putUnclosedResult(
const Object &
object, int64_t delay,
395 llvm::ImmutableList<DebugPoint> history,
396 ObjectToMaxDistance &objectToMaxDistance);
399 llvm::MapVector<std::pair<BlockArgument, size_t>, ObjectToMaxDistance>
406 LogicalResult initializeAndRun(hw::InstanceOp instance);
407 LogicalResult initializeAndRun(hw::OutputOp output);
412 LogicalResult visitValue(Value value,
size_t bitPos,
413 SmallVectorImpl<OpenPath> &results);
415 LogicalResult visit(mlir::BlockArgument argument,
size_t bitPos,
416 SmallVectorImpl<OpenPath> &results);
417 LogicalResult visit(hw::InstanceOp op,
size_t bitPos,
size_t resultNum,
418 SmallVectorImpl<OpenPath> &results);
421 LogicalResult visit(hw::WireOp op,
size_t bitPos,
422 SmallVectorImpl<OpenPath> &results);
424 SmallVectorImpl<OpenPath> &results);
426 SmallVectorImpl<OpenPath> &results);
427 LogicalResult visit(comb::ReplicateOp op,
size_t bitPos,
428 SmallVectorImpl<OpenPath> &results);
431 llvm::EquivalenceClasses<std::pair<Value, size_t>>
ec;
432 DenseMap<std::pair<Value, size_t>, std::pair<Value, size_t>>
ecMap;
433 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
434 return ec.getLeaderValue({value, bitpos});
433 std::pair<Value, size_t>
findLeader(Value value,
size_t bitpos)
const {
…}
436 LogicalResult markEquivalent(Value from,
size_t fromBitPos, Value to,
438 SmallVectorImpl<OpenPath> &results);
441 LogicalResult visit(aig::AndInverterOp op,
size_t bitPos,
442 SmallVectorImpl<OpenPath> &results);
444 SmallVectorImpl<OpenPath> &results);
446 SmallVectorImpl<OpenPath> &results);
447 LogicalResult visit(
comb::OrOp op,
size_t bitPos,
448 SmallVectorImpl<OpenPath> &results);
450 SmallVectorImpl<OpenPath> &results);
451 LogicalResult addLogicOp(Operation *op,
size_t bitPos,
452 SmallVectorImpl<OpenPath> &results);
456 SmallVectorImpl<OpenPath> &results) {
461 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos,
462 SmallVectorImpl<OpenPath> &results) {
463 return markFanIn(op, bitPos, results);
461 LogicalResult
visit(seq::FirRegOp op,
size_t bitPos, {
…}
467 SmallVectorImpl<OpenPath> &results) {
468 return markFanIn(op, bitPos, results);
471 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos,
472 SmallVectorImpl<OpenPath> &results) {
473 return markFanIn(op, bitPos, results);
471 LogicalResult
visit(seq::FirMemReadOp op,
size_t bitPos, {
…}
476 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos,
477 SmallVectorImpl<OpenPath> &results) {
478 return markFanIn(op, bitPos, results);
476 LogicalResult
visit(seq::FirMemReadWriteOp op,
size_t bitPos, {
…}
481 LogicalResult visitDefault(Operation *op,
size_t bitPos,
482 SmallVectorImpl<OpenPath> &results);
485 LogicalResult addEdge(Value to,
size_t toBitPos, int64_t delay,
486 SmallVectorImpl<OpenPath> &results);
487 LogicalResult markFanIn(Value value,
size_t bitPos,
488 SmallVectorImpl<OpenPath> &results);
489 LogicalResult markRegFanOut(Value fanOut, Value start, Value reset = {},
490 Value resetValue = {}, Value enable = {});
509 mutable std::condition_variable
cv;
513 bool topLevel =
false;
517 : module(module), ctx(ctx) {
519 std::make_unique<llvm::ImmutableListFactory<DebugPoint>>();
521 ? std::make_unique<circt::igraph::InstancePathCache>(
528 std::pair<Value, size_t> valueAndBitPos(value, bitPos);
529 auto leader =
ec.findLeader(valueAndBitPos);
530 if (leader !=
ec.member_end()) {
531 if (*leader != valueAndBitPos) {
533 return getResults(leader->first, leader->second);
545 llvm::ImmutableList<DebugPoint> history,
547 auto &slot = objectToMaxDistance[object];
548 if (slot.first >= delay && delay != 0)
550 slot = {delay, history};
555 std::unique_lock<std::mutex> lock(
mutex);
556 cv.wait(lock, [
this] {
return done.load(); });
560 Value reset, Value resetValue,
563 auto record = [&](
size_t fanOutBitPos, Value value,
size_t bitPos) {
567 for (
auto &path : *result) {
568 if (
auto blockArg = dyn_cast<BlockArgument>(path.fanIn.value)) {
581 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
582 if (failed(record(i, start, i)))
588 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
589 if (failed(record(i, reset, 0)) || failed(record(i, resetValue, i)))
595 for (
size_t i = 0, e = bitWidth; i < e; ++i) {
596 if (failed(record(i, enable, 0)))
604 Value to,
size_t toBitPos,
605 SmallVectorImpl<OpenPath> &results) {
606 auto leader =
ec.getOrInsertLeaderValue({to, toBitPos});
609 auto newLeader =
ec.unionSets({to, toBitPos}, {from, fromBitPos});
610 assert(leader == *newLeader);
615 SmallVectorImpl<OpenPath> &results) {
619 for (
auto &path : *result) {
621 newPath.delay += delay;
622 results.push_back(newPath);
628 SmallVectorImpl<OpenPath> &results) {
633 SmallVectorImpl<OpenPath> &results) {
638 SmallVectorImpl<OpenPath> &results) {
643 SmallVectorImpl<OpenPath> &results) {
648 SmallVectorImpl<OpenPath> &results) {
650 if (failed(
addEdge(op.getCond(), 0, 1, results)) ||
651 failed(
addEdge(op.getTrueValue(), bitPos, 1, results)) ||
652 failed(
addEdge(op.getFalseValue(), bitPos, 1, results)))
659 SmallVectorImpl<OpenPath> &results) {
662 bitPos + op.getLowBit(), results);
667 SmallVectorImpl<OpenPath> &results) {
673 SmallVectorImpl<OpenPath> &results) {
679 SmallVectorImpl<OpenPath> &results) {
680 return markEquivalent(op, bitPos, op.getInput(), bitPos, results);
685 SmallVectorImpl<OpenPath> &results) {
686 auto moduleName = op.getReferencedModuleNameAttr();
687 auto value = op->getResult(resultNum);
691 if (!
ctx->instanceGraph)
692 return markFanIn(value, bitPos, results);
695 auto *node =
ctx->instanceGraph->lookup(moduleName);
696 assert(node &&
"module not found");
700 if (!isa<hw::HWModuleOp>(node->getModule()))
701 return markFanIn(value, bitPos, results);
703 auto *localVisitor =
ctx->getAndWaitLocalVisitor(moduleName);
704 auto *fanInIt = localVisitor->fromOutputPortToFanIn.find({resultNum, bitPos});
707 if (fanInIt == localVisitor->fromOutputPortToFanIn.end())
710 const auto &fanIns = fanInIt->second;
712 for (
auto &[fanInPoint, delayAndHistory] : fanIns) {
713 auto [delay, history] = delayAndHistory;
718 auto arg = dyn_cast<BlockArgument>(fanInPoint.value);
722 if (
ctx->doTraceDebugPoints()) {
725 p.object.instancePath =
726 instancePathCache->prependInstance(op, p.object.instancePath);
730 DebugPoint({}, value, bitPos, delay,
"output port"), newHistory);
733 results.emplace_back(newPath, fanInPoint.value, fanInPoint.bitPos, delay,
743 for (
auto path : *result) {
745 if (
ctx->doTraceDebugPoints()) {
749 p.object.instancePath =
750 instancePathCache->prependInstance(op, p.object.instancePath);
751 p.delay += path.delay;
754 DebugPoint debugPoint({}, value, bitPos, delay + path.delay,
762 results.push_back(path);
770 SmallVectorImpl<OpenPath> &results) {
772 size_t newBitPos = bitPos;
773 for (
auto operand : llvm::reverse(op.getInputs())) {
775 if (newBitPos >= size) {
782 llvm::report_fatal_error(
"Should not reach here");
787 SmallVectorImpl<OpenPath> &results) {
788 auto size = op->getNumOperands();
789 auto cost = llvm::Log2_64_Ceil(size);
791 for (
auto operand : op->getOperands())
792 if (failed(
addEdge(operand, bitPos, cost, results)))
800 SmallVectorImpl<OpenPath> &results) {
805 SmallVectorImpl<OpenPath> &results) {
806 assert(arg.getOwner() == module.getBodyBlock());
809 auto newHistory =
ctx->doTraceDebugPoints()
811 DebugPoint({}, arg, bitPos, 0,
"input port"), {})
813 OpenPath newPoint({}, arg, bitPos, 0, newHistory);
814 results.push_back(newPoint);
820 if (
ec.contains({value, bitPos})) {
821 auto leader =
ec.findLeader({value, bitPos});
823 if (*leader != std::pair(value, bitPos)) {
830 return ArrayRef<OpenPath>(it->second);
832 SmallVector<OpenPath> results;
833 if (failed(
visitValue(value, bitPos, results)))
839 llvm::dbgs() << value <<
"[" << bitPos <<
"] "
840 <<
"Found " << results.size() <<
" paths\n";
841 llvm::dbgs() <<
"====Paths:\n";
842 for (
auto &path : results) {
843 path.print(llvm::dbgs());
844 llvm::dbgs() <<
"\n";
846 llvm::dbgs() <<
"====\n";
849 auto insertedResult =
850 cachedResults.try_emplace({value, bitPos}, std::move(results));
851 assert(insertedResult.second);
852 return ArrayRef<OpenPath>(insertedResult.first->second);
856 SmallVectorImpl<OpenPath> &results) {
858 llvm::dbgs() <<
"Visiting: ";
859 llvm::dbgs() <<
" " << value <<
"[" << bitPos <<
"]\n";
862 if (
auto blockArg = dyn_cast<mlir::BlockArgument>(value))
863 return visit(blockArg, bitPos, results);
865 auto *op = value.getDefiningOp();
867 TypeSwitch<Operation *, LogicalResult>(op)
871 seq::FirMemReadOp, seq::FirMemReadWriteOp, hw::WireOp>(
873 size_t idx = results.size();
874 auto result =
visit(op, bitPos, results);
875 if (
ctx->doTraceDebugPoints())
876 if (
auto name = op->template getAttrOfType<StringAttr>(
879 for (
auto i = idx, e = results.size(); i < e; ++i) {
880 DebugPoint debugPoint({}, value, bitPos, results[i].delay,
883 debugPoint, results[i].history);
884 results[i].history = newHistory;
889 .Case<hw::InstanceOp>([&](hw::InstanceOp op) {
890 return visit(op, bitPos, cast<OpResult>(value).getResultNumber(),
893 .Default([&](
auto op) {
return visitDefault(op, bitPos, results); });
898 const auto *childVisitor =
899 ctx->getAndWaitLocalVisitor(instance.getReferencedModuleNameAttr());
905 for (
const auto &[
object, openPaths] :
906 childVisitor->getFromInputPortToFanOut()) {
907 auto [arg, argBitPos] = object;
908 for (
auto [point, delayAndHistory] : openPaths) {
909 auto [instancePath, fanOut, fanOutBitPos] = point;
910 auto [delay, history] = delayAndHistory;
915 instance.getOperand(arg.getArgNumber()), argBitPos);
916 if (failed(computedResults))
919 for (
auto &result : *computedResults) {
920 auto newHistory =
ctx->doTraceDebugPoints()
925 p.object.instancePath = newPath;
926 p.delay += result.delay;
930 if (
auto newPort = dyn_cast<BlockArgument>(result.fanIn.value)) {
932 {newPath, fanOut, fanOutBitPos}, result.delay + delay, newHistory,
936 newPath, result.fanIn.value, result.fanIn.bitPos,
937 result.delay + delay,
939 newHistory, result.history)
947 for (
auto instance : instance->getResults()) {
948 for (
size_t i = 0, e =
getBitWidth(instance); i < e; ++i) {
950 if (failed(computedResults))
958 for (OpOperand &operand : output->getOpOperands()) {
959 for (
size_t i = 0, e =
getBitWidth(operand.get()); i < e; ++i) {
963 if (failed(computedResults))
965 for (
const auto &result : *computedResults) {
975 LLVM_DEBUG({
ctx->notifyStart(module.getModuleNameAttr()); });
977 for (
auto blockArgument :
module.getBodyBlock()->getArguments())
978 for (size_t i = 0, e = getBitWidth(blockArgument); i < e; ++i)
981 auto walkResult =
module->walk([&](Operation *op) {
983 mlir::TypeSwitch<Operation *, LogicalResult>(op)
984 .Case<seq::FirRegOp>([&](seq::FirRegOp op) {
985 return markRegFanOut(op, op.getNext(), op.getReset(),
988 .Case<seq::CompRegOp>([&](
auto op) {
989 return markRegFanOut(op, op.getInput(), op.getReset(),
992 .Case<seq::FirMemWriteOp>([&](
auto op) {
994 return markRegFanOut(op.getMemory(), op.getData(), {}, {},
997 .Case<seq::FirMemReadWriteOp>([&](seq::FirMemReadWriteOp op) {
999 return markRegFanOut(op.getMemory(), op.getWriteData(), {}, {},
1006 for (
size_t i = 0, e =
getBitWidth(op); i < e; ++i)
1007 if (failed(getOrComputeResults(op, i)))
1011 .Case<hw::InstanceOp, hw::OutputOp>(
1012 [&](
auto op) {
return initializeAndRun(op); })
1013 .Default([](
auto op) {
return success(); });
1015 return WalkResult::interrupt();
1016 return WalkResult::advance();
1020 std::lock_guard<std::mutex> lock(mutex);
1024 LLVM_DEBUG({ ctx->
notifyEnd(module.getModuleNameAttr()); });
1025 return failure(walkResult.wasInterrupted());
1036 return it->second.get();
1043 visitor->waitUntilDone();
1052 Impl(Operation *module, mlir::AnalysisManager &am,
1062 getResults(Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1064 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory =
1067 template <
bool elaborate>
1069 SmallVectorImpl<DataflowPath> &results)
const;
1071 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1073 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const;
1079 const Object &originalObject, Value value,
size_t bitPos,
1080 SmallVectorImpl<DataflowPath> &results,
1082 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const;
1089 Value value,
size_t bitPos, SmallVectorImpl<DataflowPath> &results,
1091 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1093 instancePathCache, debugPointFactory);
1097 const Object &originalObject, Value value,
size_t bitPos,
1098 SmallVectorImpl<DataflowPath> &results,
1100 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory)
const {
1101 auto parentHWModule =
1103 if (!parentHWModule)
1104 return mlir::emitError(value.getLoc())
1105 <<
"query value is not in a HWModuleOp";
1106 auto *localVisitor = ctx.
getLocalVisitor(parentHWModule.getModuleNameAttr());
1110 size_t oldIndex = results.size();
1116 llvm::dbgs() <<
"Running " << parentHWModule.getModuleNameAttr() <<
" "
1117 << value <<
" " << bitPos <<
"\n";
1120 for (
auto &path : localVisitor->getResults(value, bitPos)) {
1121 auto arg = dyn_cast<BlockArgument>(path.fanIn.value);
1122 if (!arg || localVisitor->isTopLevel()) {
1124 results.push_back({originalObject, path, parentHWModule});
1128 auto newObject = originalObject;
1129 assert(node &&
"If an instance graph is not available, localVisitor must "
1131 for (
auto *inst : node->uses()) {
1132 auto startIndex = results.size();
1133 if (instancePathCache)
1137 auto result = getResultsImpl(
1138 newObject, inst->getInstance()->getOperand(arg.getArgNumber()),
1139 path.fanIn.bitPos, results, instancePathCache, debugPointFactory);
1142 for (
auto i = startIndex, e = results.size(); i < e; ++i)
1143 results[i].setDelay(results[i].getDelay() + path.delay);
1151template <
bool elaborate>
1153 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1154 auto collectClosedPaths = [&](StringAttr name,
1159 for (
auto &[point, state] : visitor->getFanOutResults())
1160 for (
const auto &dataFlow : state) {
1161 if constexpr (elaborate) {
1165 visitor->getHWModuleOp(), top);
1166 for (
auto &instancePath : topToRoot) {
1167 results.emplace_back(point, dataFlow,
1169 results.back().prependPaths(*visitor->getInstancePathCache(),
1170 visitor->getDebugPointFactory(),
1174 results.emplace_back(point, dataFlow, visitor->getHWModuleOp());
1182 for (
auto *child : llvm::post_order(node))
1183 collectClosedPaths(child->getModule().getModuleNameAttr(), node);
1185 collectClosedPaths(moduleName);
1192 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1197 for (
auto &[key, value] : visitor->getFromInputPortToFanOut()) {
1198 auto [arg, argBitPos] = key;
1199 for (
auto [point, delayAndHistory] : value) {
1200 auto [path, start, startBitPos] = point;
1201 auto [delay, history] = delayAndHistory;
1202 results.emplace_back(
Object(path, start, startBitPos),
1203 OpenPath({}, arg, argBitPos, delay, history),
1204 visitor->getHWModuleOp());
1212 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1217 for (
auto &[key, value] : visitor->getFromOutputPortToFanIn()) {
1218 auto [resultNum, bitPos] = key;
1219 for (
auto [point, delayAndHistory] : value) {
1220 auto [path, start, startBitPos] = point;
1221 auto [delay, history] = delayAndHistory;
1222 results.emplace_back(std::make_pair(resultNum, bitPos),
1223 OpenPath(path, start, startBitPos, delay, history),
1224 visitor->getHWModuleOp());
1233 : ctx(isa<
mlir::ModuleOp>(moduleOp)
1237 if (
auto module = dyn_cast<mlir::ModuleOp>(moduleOp)) {
1239 llvm::report_fatal_error(
"Failed to run longest path analysis");
1240 }
else if (
auto hwMod = dyn_cast<hw::HWModuleOp>(moduleOp)) {
1242 llvm::report_fatal_error(
"Failed to run longest path analysis");
1244 llvm::report_fatal_error(
"Analysis scheduled on invalid operation");
1251 std::make_unique<LocalVisitor>(module, &ctx)});
1253 it.first->second->setTopLevel();
1254 return it.first->second->initializeAndRun();
1260 module->getAttrOfType<FlatSymbolRefAttr>(getTopModuleNameAttrName());
1263 llvm::SetVector<Operation *> visited;
1266 auto *topNode = instanceGraph->
lookup(topNameAttr.getAttr());
1267 if (!topNode || !topNode->getModule() ||
1268 !isa<hw::HWModuleOp>(topNode->getModule())) {
1269 module.emitError() << "top module not found in instance graph "
1275 auto inferredResults = instanceGraph->getInferredTopLevelNodes();
1276 if (failed(inferredResults))
1277 return inferredResults;
1279 for (
auto *node : *inferredResults) {
1280 if (
auto top = dyn_cast<hw::HWModuleOp>(*node->getModule()))
1281 topModules.push_back(top);
1285 SmallVector<igraph::InstanceGraphNode *> worklist;
1286 for (
auto topNode : topModules)
1287 worklist.push_back(instanceGraph->lookup(topNode.getModuleNameAttr()));
1290 while (!worklist.empty()) {
1291 auto *node = worklist.pop_back_val();
1292 assert(node &&
"node should not be null");
1293 auto op = node->getModule();
1294 if (!isa_and_nonnull<hw::HWModuleOp>(op) || !visited.insert(op))
1297 for (
auto *child : *node) {
1298 auto childOp = child->getInstance();
1299 if (!childOp || childOp->hasAttr(
"doNotPrint"))
1302 worklist.push_back(child->getTarget());
1308 for (
auto module : topModules) {
1309 auto *topNode = instanceGraph->lookup(module.getModuleNameAttr());
1310 for (
auto *node : llvm::post_order(topNode))
1311 if (node && node->getModule())
1312 if (
auto hwMod = dyn_cast<hw::HWModuleOp>(*node->getModule())) {
1313 if (visited.contains(hwMod))
1315 {hwMod.getModuleNameAttr(),
1316 std::make_unique<LocalVisitor>(hwMod, &ctx)});
1319 ctx.
localVisitors[topNode->getModule().getModuleNameAttr()]->setTopLevel();
1322 return mlir::failableParallelForEach(
1324 [&](
auto &it) { return it.second->initializeAndRun(); });
1328 StringAttr moduleName)
const {
1337 SmallVector<DataflowPath> results;
1341 int64_t totalDelay = 0;
1342 for (
size_t i = 0; i < bitWidth; ++i) {
1349 int64_t maxDelay = 0;
1350 for (
auto &path : results)
1351 maxDelay = std::max(maxDelay, path.getDelay());
1352 totalDelay += maxDelay;
1354 return llvm::divideCeil(totalDelay, bitWidth);
1358 SmallVector<DataflowPath> results;
1362 int64_t maxDelay = 0;
1363 for (
size_t i = 0; i < bitWidth; ++i) {
1370 for (
auto &path : results)
1371 maxDelay = std::max(maxDelay, path.getDelay());
1383 Operation *moduleOp, mlir::AnalysisManager &am,
1385 :
impl(new
Impl(moduleOp, am, option)) {}
1401 SmallVectorImpl<DataflowPath> &results,
1402 bool elaboratePaths)
const {
1409 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1414 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results)
const {
1420 SmallVectorImpl<DataflowPath> &results,
1421 bool elaboratePaths)
const {
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
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)
LogicalResult getResults(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results) 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
LongestPathAnalysis(Operation *moduleOp, mlir::AnalysisManager &am, const LongestPathAnalysisOption &option={})
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
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.
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
llvm::ArrayRef< hw::HWModuleOp > getTopModules() const
LogicalResult getOpenPathsFromInputPortsToInternal(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
LogicalResult getClosedPaths(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
SmallVector< hw::HWModuleOp > topModules
LogicalResult initializeAndRun(mlir::ModuleOp module)
bool isAnalysisAvailable(StringAttr moduleName) const
LogicalResult getResults(Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results, circt::igraph::InstancePathCache *instancePathCache=nullptr, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory=nullptr) const
int64_t getAverageMaxDelay(Value value) const
LogicalResult getOpenPathsFromInternalToOutputPorts(StringAttr moduleName, SmallVectorImpl< DataflowPath > &results) const
LogicalResult getResultsImpl(const Object &originalObject, Value value, size_t bitPos, SmallVectorImpl< DataflowPath > &results, circt::igraph::InstancePathCache *instancePathCache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory) const
int64_t getMaxDelay(Value value) const
void print(llvm::raw_ostream &os) const
circt::igraph::InstancePath instancePath
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
void print(llvm::raw_ostream &os) const
void print(llvm::raw_ostream &os) const
OpenPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
llvm::ImmutableList< DebugPoint > history
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.