hernanponcedeleon
Backwards reaching definitions
This PR decouples an interface for Dependency and UseDefAnalysis, and adds an alternative implementation for it, BackwardsReachingDefinitionsAnalysis (BRDA). It takes into account, that readers on uninitialized registers are unlikely, while final writers are frequent, although rarely useful. This means, that the propagated data is smaller in BRDA, than in the existing forward-directed implementations.
The more noteworthy feature is, that I wrote it to support loops. This means that it, as well as the dependent alias analysis could potentially be done before unrolling.
UseDefAnalysis also supported loops. But I guess your new analysis might be more efficient?
Yes, it should have the capabilities of both implementations and be more efficient.
Also, why do you use BranchEquivalence rather than ExecutionAnalysis? I think the latter is more correct because it also considers that instructions may fail to execute.
@hernanponcedeleon Do you remember on which benchmark UseDefAnalysis ran out of memory? I think you had some huge benchmarks where this was a problem. If so, it would be interesting to test this new analysis for efficiency.
Also, why do you use BranchEquivalence rather than ExecutionAnalysis? I think the latter is more correct because it also considers that instructions may fail to execute.
Because the cfImpliesExec condition is only needed in the over approximation (the 'may' relation). BranchEquivalence on the other hand, more precisely the areMutuallyExclusive relation, is only needed in the under approximation (the 'conditionally-must' relation). Since the later is optional, BE is not mandatory.
By the way, using the analysis has the side effect, that final register encodings are omitted, if the register is not used by the spec. This could be a small issue fixed.
Also, why do you use BranchEquivalence rather than ExecutionAnalysis? I think the latter is more correct because it also considers that instructions may fail to execute.
Because the
cfImpliesExeccondition is only needed in the over approximation (the 'may' relation).BranchEquivalenceon the other hand, more precisely theareMutuallyExclusiverelation, is only needed in the under approximation (the 'conditionally-must' relation). Since the later is optional, BE is not mandatory.
I'm not sure I understand. It seems you could just use ExecutionAnalysis.areMutuallyExclusive in your code to both simplify it and be more accurate (in theory). Conceptually, when analysing dataflow you care about executed instructions rather than instructions in the control-flow.
It likely won't make a practical difference in your use-case, because the ExecutionAnalysis is based only on control-flow but I don't see why your analysis should be aware of that and "optimize" for it.
@hernanponcedeleon Do you remember on which benchmark
UseDefAnalysisran out of memory? I think you had some huge benchmarks where this was a problem. If so, it would be interesting to test this new analysis for efficiency.
I don't really remember which benchmark that was. But I can try this in some of our larger ones.
This means, that the propagated data is smaller in BRDA, than in the existing forward-directed implementations.
Which part of our pipelines are (positively) affected by this? E.g., does the alias analysis potentially becomes more precise? Do we get smaller mayset in idd?
I think this statement is not about precision but just about memory consumption. The forward-directed implementation kept information about (last) register writes even if those registers were never going to get used again.
Which part of our pipelines are (positively) affected by this? E.g., does the alias analysis potentially becomes more precise? Do we get smaller mayset in idd?
Compared to UseDefAnalysis and Dependency, the results of BRDA for any RegReader should be exactly the same. So, any dependent analysis should be relatively unaffected, up until the encoder. idd stays the same. With propagated data, I just meant the internal updates of BRDA and Dependency. At best, there could be side effects on BRDA's querying performance, based on the data layout I chose, i.e. the time it needs to fetch a list of writers.
Since UseDefAnalysis and Dependency are unused now, I probably should add the following options, before merging.
-
program.processing.loopBounds.useDefAnalysis= {FORWARD,BACKWARD} -
program.analysis.reachingDefinitions= {FORWARD,BACKWARD}
If the analysis work fine, I don't think we need to keep around the unused options.
Keeping two implementations of the analysis might be good: if we encounter any example where one is too slow, we can try another (similar to what happened with the alias analysis and wsq.c).
However, keeping options for each single pass making use of the analysis seems too fine-grained without much clear benefit. I would rather always use forward or always us backwards.
Anything that needs to be done here? I have not checked the algorithmic details, but given that all tests pass it is likely working as intended.
Unless I missed something, not all comments were fixed. From the top of my head:
- we still have fine grained options that I don't like
- some of the preconditions / checks need to be streamlined
I think all my comments have been solved. Unless @ThomasHaas has some more comments, I'll merge