C++/C#: Reuse some SSA def/use info from previous iteration #3340
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
We build SSA twice. The first iteration, "unaliased SSA", considers only those memory locations that are not aliased, do not have their address escape, and are always accessed in their entirety and as their underlying declared type. The second iteration, "aliased SSA", considers all memory locations. However, whatever defs and uses we computed for unaliased SSA are still valid for aliased SSA, because they never overlap with the aliased memory locations that aliased SSA adds into the mix. If we can reuse the unaliased SSA information directly, we can potentially save significant cost in building aliased SSA. With this change, the SSA configuration can specify which definitions can be reused from the previous iteration of the IR. Unaliased SSA does not reuse anything from Raw IR, but Aliased SSA reuses any definition of a variable that did not escape. In addition, Unaliased SSA tells Aliased SSA which variables were did not escape, so that Aliased SSA can skip all alias analysis for those variables. During SSA construction, instead of throwing away all Phi instructions and def/use information from the previous IR iteration, we reuse whatever we were told that we could. This is slightly complicated by the possibility of degenerate (single-operand) Phi instructions due to unreachable code being eliminated between iterations. If we would have wound up with a degenerate Phi instruction, we recurse to the definition of that Phi instruction's sole reachable input operand. See the new test cases for a couple examples. In aliased SSA's AliasConfiguration.qll, I stopped creating allocations for variables that were already modeled in unaliased SSA. This in turn prevents us from creating memory locations for those variables and their defs and uses, which is where we hope to reduce evaluation time. I also tweaked the getInstructionUniqueId() predicate to reuse the unique ID from the previous stage, which preserves ordering of Phi instructions in a block to minimize test output diffs. The points_to test had to be updated to no longer expect points-to analysis on unaliased SSA to report results that were already reported when running on raw IR. Finally, I added PhiInstruction.getInputOperand(). I'm surprised we didn't have it already.
jbj
reviewed
Apr 27, 2020
| exists(IREscapeAnalysisConfiguration config | | ||
| config.useSoundEscapeAnalysis() and resultEscapesNonReturn(allocation.getABaseInstruction()) | ||
| ) | ||
| resultEscapesNonReturn(allocation.getABaseInstruction()) |
There was a problem hiding this comment.
I don't understand why this predicate changed and whether the QLDoc on it is still accurate.
| /** | ||
| * Holds if the specified variable should be modeled in SSA form. For unaliased SSA, we only model a | ||
| * variable if its address never escapes and all reads and writes of that variable access the entire | ||
| * variable using the original type of the variable. | ||
| */ | ||
| private predicate isVariableModeled(Allocation var) { | ||
| not allocationEscapes(var) and | ||
| not treatAllocationAsEscaped(var) and |
There was a problem hiding this comment.
This change means (when unsound) we're now modelling some variables in unaliased SSA that were previously modelled in aliased SSA, right? Why?
| @@ -199,9 +258,25 @@ private module Cached { | |||
| ) | |||
| } | |||
|
|
|||
| /** | |||
| * Gets the new definition instruction for the operand of `instr` that flows from the block | |||
There was a problem hiding this comment.
Suggested change
| * Gets the new definition instruction for the operand of `instr` that flows from the block | |
| * Gets the new definition instruction for the phi operand of `instr` that flows from the block |
This would improve readability for me.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Leaving as a draft until I have performance numbers from a CPP-Differences job
This PR supercedes #3235. The necessary changes were extensive enough that it was too risky for
rc/1.24, so this PR is againstmaster.We build SSA twice. The first iteration, "unaliased SSA", considers only those memory locations that are not aliased, do not have their address escape, and are always accessed in their entirety and as their underlying declared type. The second iteration, "aliased SSA", considers all memory locations. However, whatever defs and uses we computed for unaliased SSA are still valid for aliased SSA, because they never overlap with the aliased memory locations that aliased SSA adds into the mix. If we can reuse the unaliased SSA information directly, we can potentially save significant cost in building aliased SSA.
With this change, the SSA configuration can specify which definitions can be reused from the previous iteration of the IR. Unaliased SSA does not reuse anything from Raw IR, but Aliased SSA reuses any definition of a variable that did not escape. In addition, Unaliased SSA tells Aliased SSA which variables were did not escape, so that Aliased SSA can skip all alias analysis for those variables.
During SSA construction, instead of throwing away all Phi instructions and def/use information from the previous IR iteration, we reuse whatever we were told that we could. This is slightly complicated by the possibility of degenerate (single-operand) Phi instructions due to unreachable code being eliminated between iterations. If we would have wound up with a degenerate Phi instruction, we recurse to the definition of that Phi instruction's sole reachable input operand. See the new test cases for a couple examples.
In aliased SSA's AliasConfiguration.qll, I stopped creating allocations for variables that were already modeled in unaliased SSA. This in turn prevents us from creating memory locations for those variables and their defs and uses, which is where we hope to reduce evaluation time.
I also tweaked the getInstructionUniqueId() predicate to reuse the unique ID from the previous stage, which preserves ordering of Phi instructions in a block to minimize test output diffs.
The points_to test had to be updated to no longer expect points-to analysis on unaliased SSA to report results that were already reported when running on raw IR.
Finally, I added PhiInstruction.getInputOperand(). I'm surprised we didn't have it already.