C++: Reduce size of edges and nodes in cpp/upcast-array-pointer-arithmetic
#11330
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
geoffw0
reviewed
Nov 18, 2022
| exists(PointerAddExpr pae | pae.getAnOperand() = node.asExpr()) or | ||
| exists(ArrayExpr ae | ae.getArrayBase() = node.asExpr()) | ||
| ) and | ||
| getFullyConvertedType(node).getName() = state |
There was a problem hiding this comment.
So we're saying that the sink has to have the same (fully converted, unspecified) type as the source. Why does this help performance? Why does it not affect results?
There was a problem hiding this comment.
Exactly. Let me answer each question separately:
Why does it not affect results?
Because the query is already requiring that the type of the source and the sink is equivalent. To see this, notice that the body of the select is:
cfg.hasFlowPath(pragma[only_bind_into](source), pragma[only_bind_into](sink)) and
hasFullyConvertedType(source, t) and
hasFullyConvertedType(sink, t)Why does this help performance?
Consider what would happen without this PR:
- We would find all the sources
- We would find all the sinks
- We compute all the flows between sources and sinks
- After computing all these flows, the body of the
selectclause restricts the alerts to only those where the source type is equivalent to the sink type.
This is what we see in:
[2022-11-18 13:50:58] Evaluated non-recursive predicate #select#cpe#1235#ffff@f7d935aq in 2ms (size: 10).
Evaluated relational algebra for predicate #select#cpe#1235#ffff@f7d935aq with tuple counts:
9754 ~0% {4} r1 = SCAN DataFlowImpl#9021cc4c::Configuration::hasFlowPath#2#dispred#fff OUTPUT In.1, In.2, In.2, In.1
9754 ~2% {5} r2 = JOIN r1 WITH CastArrayPointerArithmetic#b621a59c::hasFullyConvertedType#2#ff ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.0, Lhs.2, Lhs.3
10 ~0% {4} r3 = JOIN r2 WITH CastArrayPointerArithmetic#b621a59c::hasFullyConvertedType#2#ff ON FIRST 2 OUTPUT Lhs.0, Lhs.2, Lhs.3, Lhs.4
return r3There are 9754 pairs of sources and sinks, but only 10 of those end up being reported because their types match.
Now, consider what happens with this PR:
- We would find all the sources (as before)
- We would find all the sinks (as before)
- We compute all the flows between sources and sinks (as before). But now there's only a flow between a source and a sink when they have the same (string representation) of their type. This means there are far fewer paths.
- After computing these flows, the body of the
selectclause restricts the alerts to only those where the source type is equivalent to the sink type (as before).
The important part is step 3. We see the effect of the PR in the evaluation of the select body:
[2022-11-18 14:41:49] Evaluated non-recursive predicate #select#cpe#1235#ffff@d790a1nc in 0ms (size: 10).
Evaluated relational algebra for predicate #select#cpe#1235#ffff@d790a1nc with tuple counts:
10 ~0% {4} r1 = SCAN DataFlowImpl#9021cc4c::Configuration::hasFlowPath#2#dispred#fff OUTPUT In.1, In.2, In.2, In.1
10 ~0% {5} r2 = JOIN r1 WITH CastArrayPointerArithmetic#b621a59c::hasFullyConvertedType#2#ff ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Lhs.0, Lhs.2, Lhs.3
10 ~0% {4} r3 = JOIN r2 WITH CastArrayPointerArithmetic#b621a59c::hasFullyConvertedType#2#ff ON FIRST 2 OUTPUT Lhs.0, Lhs.2, Lhs.3, Lhs.4
return r3|
DCA confirms that we can now analyze openjdk on the use-use flow feature branch without OOM'ing |
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.
This predicate was generating very large
nodesandedgesrelations on openjdk:These are the relations the CLI uses to generate the final paths.
After these have been computed, the body of the
selectwas used to prune out the paths that are okay (by checking that the types match):To improve this situation, this PR (ab)uses flow states to ensure that only the right sinks are matched up with the right source. This results in way smaller
edgesandnodes:and since the types now match, the final
selectends up like:Note that we still need the final type check in the body of the
selectsince I don't think thattype1.getName() = type2.getName()implies thattype1 = type2.