Loading [MathJax]/extensions/tex2jax.js
CIRCT 22.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
aig.py
Go to the documentation of this file.
1# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
2# See https://llvm.org/LICENSE.txt for license information.
3# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
4
5from . import aig, hw
6from ._aig_ops_gen import *
7from .._mlir_libs._circt._aig import _LongestPathAnalysis, _LongestPathCollection, _LongestPathDataflowPath, _LongestPathHistory, _LongestPathObject
8
9from dataclasses import dataclass
10from typing import Any, Dict, List, Union
11
12# ============================================================================
13# Core Data Structures for AIG Path Analysis
14# ============================================================================
15
16
17@dataclass
19 """
20 Represents a single element in a hierarchical instance path.
21 In hardware design, modules are instantiated hierarchically. This class
22 represents one level in that hierarchy, containing both the module type
23 and the specific instance name.
24 Attributes:
25 instance_name: The name of this specific instance
26 module_name: The type/name of the module being instantiated
27 """
28 _instance: hw.InstanceOp
29
30 def __init__(self, instance: hw.InstanceOp):
31 self._instance_instance = instance
32
33 @property
34 def instance_name(self) -> str:
35 return self._instance_instance.attributes["instanceName"].value
36
37 @property
38 def module_name(self) -> str:
39 return self._instance_instance.attributes["moduleName"].value
40
41
42@dataclass
43class Object:
44 """
45 Represents a signal or port object in the dataflow graph.
46 This class encapsulates a specific signal within the hardware hierarchy,
47 including its location in the instance hierarchy, signal name, and bit position
48 for multi-bit signals.
49 Attributes:
50 instance_path: Hierarchical path to the module containing this object
51 name: The signal/port name within the module
52 bit_pos: Bit position for multi-bit signals (0 for single-bit)
53 """
54
55 _object: _LongestPathObject
56
57 # TODO: Associate with an MLIR value/op
58
59 def __str__(self) -> str:
60 """
61 Generate a human-readable string representation of this object.
62 Format: "module1:instance1/module2:instance2 signal_name[bit_pos]"
63 """
64 path = "/".join(f"{elem.module_name}:{elem.instance_name}"
66 return f"{path} {self.name}[{self.bit_pos}]"
67
68 def __repr__(self) -> str:
69 return f"Object({self.instance_path}, {self.name}, {self.bit_pos})"
70
71 @property
72 def instance_path(self) -> List[Instance]:
73 """Get the hierarchical instance path to this object."""
74 operations = self._object.instance_path
75
76 return [Instance(op) for op in operations]
77
78 @property
79 def name(self) -> str:
80 """Get the name of this signal/port."""
81 return self._object.name
82
83 @property
84 def bit_pos(self) -> int:
85 """Get the bit position for multi-bit signals."""
86 return self._object.bit_pos
87
88
89@dataclass
91 """
92 Represents a debug point in the timing path history.
93 Debug points are intermediate points along a timing path that provide
94 insight into the delay accumulation and signal propagation through
95 the circuit. Each point captures the state at a specific location.
96 Attributes:
97 object: The signal/object at this debug point
98 delay: Accumulated delay up to this point (in timing units)
99 comment: Optional descriptive comment about this point
100 """
101
102 object: Object
103 delay: int
104 comment: str
105
106 @classmethod
107 def from_dict(cls, data: Dict[str, Any]) -> "DebugPoint":
108 """Create a DebugPoint from a dictionary representation."""
109 return cls(
110 object=Object.from_dict(data["object"]),
111 delay=data["delay"],
112 comment=data["comment"],
113 )
114
115
116@dataclass
118 """
119 Represents a complete dataflow path from fan-out to fan-in.
120 A dataflow path captures the complete timing path through a circuit,
121 from an output point (fan-out) back to an input point (fan-in), including
122 all intermediate debug points and the total delay.
123 Attributes:
124 fan_out: The output signal/object where this path ends
125 path: The OpenPath containing the detailed path information
126 root: The root module name for this analysis
127 """
128
129 _path: _LongestPathDataflowPath
130
131 @property
132 def delay(self) -> int:
133 """Get the total delay of this path in timing units."""
134 return self._path.delay
135
136 @property
137 def fan_in(self) -> Object:
138 """Get the input signal/object where this path begins."""
139 return Object(self._path.fan_in)
140
141 @property
142 def fan_out(self) -> Object:
143 """Get the output signal/object where this path ends."""
144 return Object(self._path.fan_out)
145
146 @property
147 def history(self) -> List[DebugPoint]:
148 """Get the history of debug points along this path."""
149 return [i for i in LongestPathHistory(self._path.history)]
150
151 @property
152 def root(self) -> str:
153 """Get the root module name for this analysis."""
154 return self._path.root.attributes["sym_name"].value
155
156 # ========================================================================
157 # Visualization and Analysis Methods
158 # ========================================================================
159
160 def to_flamegraph(self) -> str:
161 """
162 Convert this path to FlameGraph format for visualization.
163 FlameGraphs are a visualization technique that shows call stacks or
164 in this case, timing paths through the circuit hierarchy. Each line
165 represents a segment of the path with its associated delay.
166 The format is: "hierarchy_path delay_increment"
167 where hierarchy_path uses semicolons to separate hierarchy levels.
168 Returns:
169 String in FlameGraph format showing the timing path progression
170 """
171 trace = []
172 prefix = f"top:{self.root}"
173
174 # Build hierarchy strings for start and end points
175 fan_in_hierarchy = self._build_hierarchy_string(self.fan_in, prefix)
176 fan_out_hierarchy = self._build_hierarchy_string(self.fan_out, prefix)
177
178 # Track current position and delay for incremental output
179 current_hierarchy = fan_in_hierarchy
180 current_delay = 0
181
182 # Process debug history points in reverse order (from input to output)
183 for debug_point in self.history[::-1]:
184 history_hierarchy = self._build_hierarchy_string(debug_point.object,
185 prefix)
186 if history_hierarchy:
187 # Add segment from current position to this debug point
188 delay_increment = debug_point.delay - current_delay
189 trace.append(f"{current_hierarchy} {delay_increment}")
190
191 # Update current position
192 current_hierarchy = history_hierarchy
193 current_delay = debug_point.delay
194
195 # Add final segment to fan-out if there's remaining delay
196 if current_delay != self.delay:
197 final_delay = self.delay - current_delay
198 trace.append(f"{fan_out_hierarchy} {final_delay}")
199
200 return "\n".join(trace)
201
202 def _build_hierarchy_string(self, obj: Object, prefix: str = "") -> str:
203 """
204 Build a hierarchical string representation of an Object for FlameGraph format.
205 This method constructs a semicolon-separated hierarchy string that represents
206 the full path from the top-level module down to the specific signal. This
207 format is compatible with FlameGraph visualization tools.
208 Args:
209 obj: Object to represent in the hierarchy
210 prefix: Top-level prefix (typically "top:module_name")
211 Returns:
212 Hierarchical string in format: "top:root;module1:inst1;module2:inst2;signal[bit]"
213 """
214 parts = [prefix]
215
216 # Add each level of the instance hierarchy
217 for elem in obj.instance_path:
218 parts.append(f"{elem.instance_name}:{elem.module_name}")
219
220 # Add the signal name with bit position if applicable
221 signal_part = obj.name
222 signal_part += f"[{obj.bit_pos}]"
223 parts.append(signal_part)
224
225 return ";".join(parts)
226
227
228# ============================================================================
229# Analysis Collection Classes
230# ============================================================================
231
232
234 """
235 A collection of timing paths sorted by delay (longest first).
236 This class provides a Python wrapper around the C++ LongestPathCollection,
237 offering convenient access to timing paths with caching for performance.
238 The paths are pre-sorted by delay in descending order.
239 Attributes:
240 collection: The underlying C++ collection object
241 length: Number of paths in the collection
242 """
243
244 def __init__(self, collection):
245 """
246 Initialize the collection wrapper.
247 Args:
248 collection: The underlying C++ LongestPathCollection object
249 """
250 self.collection = collection
251 self.length = self.collection.get_size()
252
253 # ========================================================================
254 # Collection Interface Methods
255 # ========================================================================
256
257 def __len__(self) -> int:
258 """Get the number of paths in the collection."""
259 return self.length
260
262 self, index: Union[slice,
263 int]) -> Union[DataflowPath, List[DataflowPath]]:
264 """
265 Get a specific path from the collection by index.
266 Supports both integer and slice indexing. Integer indices can be negative.
267
268 Args:
269 index: Integer index or slice object to access paths
270
271 Returns:
272 DataflowPath or list of DataflowPaths for slice access
273
274 Raises:
275 IndexError: If index is out of range
276 """
277 if isinstance(index, slice):
278 return [self[i] for i in range(*index.indices(len(self)))]
279
280 # Handle negative indexing
281 if index < 0:
282 index += self.length
283 if index < 0 or index >= self.length:
284 raise IndexError("Index out of range")
285
286 return DataflowPath(self.collection.get_path(index))
287
288 # ========================================================================
289 # Analysis and Query Methods
290 # ========================================================================
291
292 @property
293 def longest_path(self) -> DataflowPath:
294 """Get the path with the maximum delay (first element since sorted)."""
295 return self[0]
296
297 def get_by_delay_ratio(self, ratio: float) -> DataflowPath:
298 """
299 Get the path at the specified position in the delay-sorted collection.
300 Since paths are sorted by delay in descending order, higher ratios
301 correspond to paths with higher delays (closer to the critical path).
302 Args:
303 ratio: Position ratio between 0.0 and 1.0
304 (e.g., 1.0 = longest delay path, 0.0 = shortest delay path,
305 0.95 = path among the top 5% slowest paths)
306 Returns:
307 DataflowPath at the specified position ratio
308 """
309 assert ratio >= 0.0 and ratio <= 1.0, "Ratio must be between 0.0 and 1.0"
310 index = int(len(self) * (1 - ratio))
311 return self[index]
312
313 def print_summary(self) -> None:
314 """Print a statistical summary of path delays in the collection."""
315 print(f"Total paths: {len(self)}")
316 print(f"Max delay: {self.longest_path.delay}")
317 print(f"Min delay: {self[-1].delay}")
318 print(f"50th percentile delay: {self.get_by_delay_ratio(0.5).delay}")
319 print(f"90th percentile delay: {self.get_by_delay_ratio(0.9).delay}")
320 print(f"95th percentile delay: {self.get_by_delay_ratio(0.95).delay}")
321 print(f"99th percentile delay: {self.get_by_delay_ratio(0.99).delay}")
322 print(f"99.9th percentile delay: {self.get_by_delay_ratio(0.999).delay}")
323
324
325# ============================================================================
326# Main Analysis Interface
327# ============================================================================
328
329
331 """
332 Main interface for performing longest path analysis on AIG circuits.
333 This class provides a Python wrapper around the C++ LongestPathAnalysis,
334 enabling timing analysis of AIG (And-Inverter Graph) circuits. It can
335 identify critical timing paths and provide detailed path information.
336 Attributes:
337 analysis: The underlying C++ analysis object
338 """
339
340 def __init__(self, module, trace_debug_points: bool = True):
341 """
342 Initialize the longest path analysis for a given module.
343 Args:
344 module: The MLIR module to analyze
345 trace_debug_points: Whether to include debug points in the analysis.
346 The debug points provide additional information about the path,
347 but increase the analysis time and memory usage.
348 """
349 self.analysis = aig._LongestPathAnalysis(module, trace_debug_points)
350
352 module_name: str,
353 elaborate_paths: bool = True) -> LongestPathCollection:
354 """
355 Perform longest path analysis and return all timing paths.
356 This method analyzes the specified module and returns a collection
357 of all timing paths, sorted by delay in descending order.
358 Args:
359 module_name: Name of the module to analyze
360 Returns:
361 LongestPathCollection containing all paths sorted by delay
362 """
364 self.analysis.get_all_paths(module_name, elaborate_paths))
365
366
367@dataclass
369 """
370 Represents the history of a timing path, including intermediate debug points.
371 This class provides a Python wrapper around the C++ LongestPathHistory,
372 enabling iteration over the path's history and access to debug points.
373 Attributes:
374 history: The underlying C++ history object
375 """
376 history: _LongestPathHistory
377
378 def __iter__(self):
379 """Iterate over the debug points in the history."""
380 while not self.historyhistory.empty:
381 object, delay, comment = self.historyhistory.head
382 yield DebugPoint(Object(object), delay, comment)
static void print(TypedAttr val, llvm::raw_ostream &os)
Object fan_in(self)
Definition aig.py:137
int delay(self)
Definition aig.py:132
str root(self)
Definition aig.py:152
Object fan_out(self)
Definition aig.py:142
str _build_hierarchy_string(self, Object obj, str prefix="")
Definition aig.py:202
str to_flamegraph(self)
Definition aig.py:160
List[DebugPoint] history(self)
Definition aig.py:147
_LongestPathDataflowPath _path
Definition aig.py:129
"DebugPoint" from_dict(cls, Dict[str, Any] data)
Definition aig.py:107
__init__(self, hw.InstanceOp instance)
Definition aig.py:30
str instance_name(self)
Definition aig.py:34
hw _instance
Definition aig.py:28
str module_name(self)
Definition aig.py:38
LongestPathCollection get_all_paths(self, str module_name, bool elaborate_paths=True)
Definition aig.py:353
__init__(self, module, bool trace_debug_points=True)
Definition aig.py:340
None print_summary(self)
Definition aig.py:313
__init__(self, collection)
Definition aig.py:244
Union[DataflowPath, List[DataflowPath]] __getitem__(self, Union[slice, int] index)
Definition aig.py:263
DataflowPath longest_path(self)
Definition aig.py:293
DataflowPath get_by_delay_ratio(self, float ratio)
Definition aig.py:297
_LongestPathHistory history
Definition aig.py:376
str __str__(self)
Definition aig.py:59
instance_path
Definition aig.py:65
int bit_pos(self)
Definition aig.py:84
_LongestPathObject _object
Definition aig.py:55
str __repr__(self)
Definition aig.py:68
str name(self)
Definition aig.py:79
List[Instance] instance_path(self)
Definition aig.py:72