For sufficiently large and complex designs, a substantial performance penalty was paid for constructing Combinational.ssa due to the search algorithm for potential SSA drivers. The algorithm had to search backwards from inputs to Conditionals for potential SSA drivers. This was especially expensive when using the Pipeline abstraction, since that chained multiple Combinational.ssas together.
This PR changes the algorithm to search outwards from SSA drivers to cache signals that are driven by it. This trades the performance glass jaws:
originally, if you had much logic defined before a Combinational.ssa, you could pay a performance penalty proportional to the size of that logic
now, if you have a substantial amount of unrelated logic connected to an SSA driver (at the time of Combinational.ssa construction, you could pay a performance penalty proportional to the size of that logic.
The latter glass jaw should be substantially smaller, less likely, and less frequent.
This PR also adds a benchmark which demonstrates a large performance improvement in a somewhat good example of common use cases.
Related Issue(s)
N/A
Testing
Existing tests cover functionality, new benchmark covers performance
Backwards-compatibility
Is this a breaking change that will not be backwards-compatible? If yes, how so?
No
Documentation
Does the change require any updates to documentation? If so, where? Are they included?
Description & Motivation
For sufficiently large and complex designs, a substantial performance penalty was paid for constructing
Combinational.ssadue to the search algorithm for potential SSA drivers. The algorithm had to search backwards from inputs toConditionals for potential SSA drivers. This was especially expensive when using thePipelineabstraction, since that chained multipleCombinational.ssas together.This PR changes the algorithm to search outwards from SSA drivers to cache signals that are driven by it. This trades the performance glass jaws:
Combinational.ssa, you could pay a performance penalty proportional to the size of that logicCombinational.ssaconstruction, you could pay a performance penalty proportional to the size of that logic.The latter glass jaw should be substantially smaller, less likely, and less frequent.
This PR also adds a benchmark which demonstrates a large performance improvement in a somewhat good example of common use cases.
Related Issue(s)
N/A
Testing
Existing tests cover functionality, new benchmark covers performance
Backwards-compatibility
No
Documentation
No