Loading [MathJax]/extensions/tex2jax.js
CIRCT 22.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LongestPathAnalysis.h
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the longest path analysis for the AIG dialect.
10// The analysis computes the maximum delay through combinational paths in a
11// circuit where each AIG and-inverter operation is considered to have a unit
12// delay. It handles module hierarchies and provides detailed path information
13// including sources, sinks, delays, and debug points.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef CIRCT_ANALYSIS_AIG_ANALYSIS_H
18#define CIRCT_ANALYSIS_AIG_ANALYSIS_H
19
22#include "circt/Support/LLVM.h"
23#include "mlir/IR/BuiltinOps.h"
24#include "mlir/IR/MLIRContext.h"
25#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/ImmutableList.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/Support/JSON.h"
29#include <variant>
30
31namespace mlir {
32class AnalysisManager;
33} // namespace mlir
34namespace circt {
35namespace igraph {
36class InstanceGraph;
37} // namespace igraph
38namespace aig {
39
40// A class represents an object in the dataflow graph.
41// An Object identifies a specific bit of a value at a specific instance path.
42struct Object {
45 Object() = default;
46
47 bool operator==(const Object &other) const {
48 return instancePath == other.instancePath && value == other.value &&
49 bitPos == other.bitPos;
50 }
51
52 void print(llvm::raw_ostream &os) const;
55
56 StringAttr getName() const;
57
59 Value value;
60 size_t bitPos;
61};
62
63// A debug point represents a point in the dataflow graph which carries delay
64// and optional comment. Debug points are used to track the history of a path
65// and provide context for debugging.
66struct DebugPoint {
67 DebugPoint(circt::igraph::InstancePath path, Value value, size_t bitPos,
68 int64_t delay = 0, StringRef comment = "")
69 : object(path, value, bitPos), delay(delay), comment(comment) {}
70
71 // Trait for ImmutableList.
72 void Profile(llvm::FoldingSetNodeID &ID) const {
73 for (auto &inst : object.instancePath) {
74 ID.AddPointer(inst.getAsOpaquePointer());
75 }
76 ID.AddPointer(object.value.getAsOpaquePointer());
77 ID.AddInteger(object.bitPos);
78 ID.AddInteger(delay);
79 }
80
81 void print(llvm::raw_ostream &os) const;
82
84 int64_t delay;
85 StringRef comment;
86};
87
88// An OpenPath represents a path from a fan-in with an associated
89// delay and history of debug points.
90struct OpenPath {
91 OpenPath(circt::igraph::InstancePath path, Value value, size_t bitPos,
92 int64_t delay = 0, llvm::ImmutableList<DebugPoint> history = {})
93 : fanIn(path, value, bitPos), delay(delay), history(history) {}
94 OpenPath() = default;
95
96 const Object &getFanIn() const { return fanIn; }
97 int64_t getDelay() const { return delay; }
98 const llvm::ImmutableList<DebugPoint> &getHistory() const { return history; }
99
100 void print(llvm::raw_ostream &os) const;
101 OpenPath &
103 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
105
107 int64_t delay;
108 // History of debug points represented by linked lists.
109 // The head of the list is the farthest point from the fanIn.
110 llvm::ImmutableList<DebugPoint> history;
111};
112
113// A DataflowPath represents a complete timing path from a fanout to a fanin
114// with associated delay information. This is the primary result type for
115// longest path analysis, containing both endpoints and path history.
117public:
118 // FanOut can be either an internal circuit object or a module output port
119 // This flexibility allows representing both closed paths
120 // (register-to-register) and open paths (register-to-output) in a unified way
121 using OutputPort = std::tuple<hw::HWModuleOp, size_t, size_t>;
122 using FanOutType = std::variant<Object, OutputPort>;
123
124 // Constructor for paths with Object fanout (internal circuit nodes)
127
128 // Constructor for paths with port fanout (module output ports)
131
132 DataflowPath() = default;
133
134 int64_t getDelay() const { return path.delay; }
135 const Object &getFanIn() const { return path.fanIn; }
136 const FanOutType &getFanOut() const { return fanOut; }
137 const Object &getFanOutAsObject() const { return std::get<Object>(fanOut); }
139 return std::get<OutputPort>(fanOut);
140 }
141 hw::HWModuleOp getRoot() const { return root; }
142 const llvm::ImmutableList<DebugPoint> &getHistory() const {
143 return path.history;
144 }
145 const OpenPath &getPath() const { return path; }
146
147 // Get source location for the fanout point (for diagnostics)
148 Location getFanOutLoc();
149
150 void setDelay(int64_t delay) { path.delay = delay; }
151
152 void print(llvm::raw_ostream &os);
153 void printFanOut(llvm::raw_ostream &os);
154
155 // Path elaboration for hierarchical analysis
156 // Prepends instance path information to create full hierarchical paths
159 llvm::ImmutableListFactory<DebugPoint> *debugPointFactory,
161
162private:
163 FanOutType fanOut; // Either Object or (port_index, bit_index)
164 OpenPath path; // The actual timing path with history
165 hw::HWModuleOp root; // Root module for this path
166};
167
168// JSON serialization for DataflowPath
169llvm::json::Value toJSON(const circt::aig::DataflowPath &path);
170
171// Options for the longest path analysis.
175
176// This analysis finds the longest paths in the dataflow graph across modules.
177// Also be aware of the lifetime of the analysis, the results would be
178// invalid if the IR is modified. Currently there is no way to efficiently
179// update the analysis results, so it's recommended to only use this analysis
180// once on a design, and store the results in a separate data structure which
181// users can manage the lifetime.
183public:
184 // Entry points for analysis.
185 LongestPathAnalysis(Operation *moduleOp, mlir::AnalysisManager &am,
186 const LongestPathAnalysisOption &option = {});
188
189 // Return all longest paths to each Fanin for the given value and bit
190 // position.
191 LogicalResult getResults(Value value, size_t bitPos,
192 SmallVectorImpl<DataflowPath> &results) const;
193
194 // Return the maximum delay to the given value for all bit positions.
195 int64_t getMaxDelay(Value value) const;
196
197 // Return the average of the maximum delays across all bits of the given
198 // value, which is useful approximation for the delay of the value. For each
199 // bit position, finds all paths and takes the maximum delay. Then averages
200 // these maximum delays across all bits of the value.
201 int64_t getAverageMaxDelay(Value value) const;
202
203 // Return paths that are closed under the given module. Closed paths are
204 // typically register-to-register paths. A closed path is a path that starts
205 // and ends at sequential elements (registers/flip-flops), forming a complete
206 // timing path through combinational logic. The path may cross module
207 // boundaries but both endpoints are sequential elements, not ports.
208 LogicalResult getClosedPaths(StringAttr moduleName,
209 SmallVectorImpl<DataflowPath> &results,
210 bool elaboratePaths = false) const;
211
212 // Return input-to-internal timing paths for the given module.
213 // These are open paths from module input ports to internal sequential
214 // elements (registers/flip-flops).
216 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const;
217
218 // Return internal-to-output timing paths for the given module.
219 // These are open paths from internal sequential elements to module output
220 // ports.
222 StringAttr moduleName, SmallVectorImpl<DataflowPath> &results) const;
223
224 // Get all timing paths in the given module including both closed and open
225 // paths. This is a convenience method that combines results from
226 // getClosedPaths, getOpenPathsFromInputPortsToInternal, and
227 // getOpenPathsFromInternalToOutputPorts. If elaboratedPaths is true, paths
228 // include full hierarchical instance information.
229 LogicalResult getAllPaths(StringAttr moduleName,
230 SmallVectorImpl<DataflowPath> &results,
231 bool elaboratePaths = false) const;
232
233 // Return true if the analysis is available for the given module.
234 bool isAnalysisAvailable(StringAttr moduleName) const;
235
236 // Return the top nodes that were used for the analysis.
237 llvm::ArrayRef<hw::HWModuleOp> getTopModules() const;
238
239 // This is the name of the attribute that can be attached to the module
240 // to specify the top module for the analysis. This is optional, if not
241 // specified, the analysis will infer the top module from the instance graph.
242 // However it's recommended to specify it, as the entire module tends to
243 // contain testbench or verification modules, which may have expensive paths
244 // that are not of interest.
245 static StringRef getTopModuleNameAttrName() {
246 return "aig.longest-path-analysis-top";
247 }
248
249 MLIRContext *getContext() const { return ctx; }
250
251private:
252 struct Impl;
254
255 mlir::MLIRContext *ctx;
256};
257
258// A wrapper class for the longest path analysis that also traces debug points.
259// This is necessary for analysis manager to cache the analysis results.
261public:
262 LongestPathAnalysisWithTrace(Operation *moduleOp, mlir::AnalysisManager &am)
263 : LongestPathAnalysis(moduleOp, am, {true}) {}
264};
265
266// A collection of longest paths. The data structure owns the paths, and used
267// for computing statistics and CAPI.
269public:
270 LongestPathCollection(MLIRContext *ctx) : ctx(ctx){};
271 const DataflowPath &getPath(unsigned index) const { return paths[index]; }
272 MLIRContext *getContext() const { return ctx; }
273 llvm::SmallVector<DataflowPath, 64> paths;
274
275 // Sort the paths by delay in descending order.
277
278 // Sort and drop all paths except the longest path per fanout point.
280
281private:
282 MLIRContext *ctx;
283};
284
285} // namespace aig
286} // namespace circt
287
288namespace llvm {
289// Provide DenseMapInfo for Object.
290template <>
293 std::tuple<circt::igraph::InstancePath, mlir::Value, size_t>>;
296 auto [path, value, bitPos] = Info::getEmptyKey();
297 return Object(path, value, bitPos);
298 }
299
301 auto [path, value, bitPos] = Info::getTombstoneKey();
302 return Object(path, value, bitPos);
303 }
304 static llvm::hash_code getHashValue(Object object) {
305 return Info::getHashValue(
306 {object.instancePath, object.value, object.bitPos});
307 }
308 static bool isEqual(const Object &a, const Object &b) {
309 return Info::isEqual({a.instancePath, a.value, a.bitPos},
310 {b.instancePath, b.value, b.bitPos});
311 }
312};
313} // namespace llvm
314
315#endif // CIRCT_ANALYSIS_AIG_ANALYSIS_H
const OpenPath & getPath() const
std::tuple< hw::HWModuleOp, size_t, size_t > OutputPort
const OutputPort & getFanOutAsPort() const
const llvm::ImmutableList< DebugPoint > & getHistory() const
const Object & getFanOutAsObject() const
std::variant< Object, OutputPort > FanOutType
const FanOutType & getFanOut() const
DataflowPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
DataflowPath(OutputPort fanOut, OpenPath fanIn, hw::HWModuleOp root)
const Object & getFanIn() const
DataflowPath(Object fanOut, OpenPath fanIn, hw::HWModuleOp root)
void printFanOut(llvm::raw_ostream &os)
void print(llvm::raw_ostream &os)
hw::HWModuleOp getRoot() const
LongestPathAnalysisWithTrace(Operation *moduleOp, mlir::AnalysisManager &am)
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
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
const DataflowPath & getPath(unsigned index) const
llvm::SmallVector< DataflowPath, 64 > paths
This graph tracks modules and where they are instantiated.
An instance path composed of a series of instances.
Definition aig.py:1
llvm::json::Value toJSON(const circt::aig::DataflowPath &path)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
void Profile(llvm::FoldingSetNodeID &ID) const
DebugPoint(circt::igraph::InstancePath path, Value value, size_t bitPos, int64_t delay=0, StringRef comment="")
void print(llvm::raw_ostream &os) const
circt::igraph::InstancePath instancePath
Object & prependPaths(circt::igraph::InstancePathCache &cache, circt::igraph::InstancePath path)
StringAttr getName() const
bool operator==(const Object &other) const
void print(llvm::raw_ostream &os) const
Object(circt::igraph::InstancePath path, Value value, size_t bitPos)
const Object & getFanIn() const
void print(llvm::raw_ostream &os) const
OpenPath(circt::igraph::InstancePath path, Value value, size_t bitPos, int64_t delay=0, llvm::ImmutableList< DebugPoint > history={})
OpenPath & prependPaths(circt::igraph::InstancePathCache &cache, llvm::ImmutableListFactory< DebugPoint > *debugPointFactory, circt::igraph::InstancePath path)
llvm::ImmutableList< DebugPoint > history
const llvm::ImmutableList< DebugPoint > & getHistory() const
A data structure that caches and provides paths to module instances in the IR.
static llvm::hash_code getHashValue(Object object)
static bool isEqual(const Object &a, const Object &b)