C++: Speed up alias analysis #17062

MathiasVP · 2024-07-24T13:46:40Z

This PR fixes a performance problem that has always been present in the IR alias analysis, but which became much more likely to happen after merging #16139.

The problem

The core problem is here. The hasNonPhiDefinition predicate contains a useLocation column whose only restriction is that it overlaps with defLocation. So if many useLocations overlap with the defLocation this predicate becomes very large.

The reason this became a problem when we merged #16139 is that many more things started to escape the alias analysis, and thus many more things started to overlap.

The fix

This PR fixes the problem by identifying which memory locations will cause an explosion in hasNonPhiDefinition, and then removing those MemoryLocations from the universe of MemoryLocations. This speeds up alias analysis significantly on some projects, at the cost of not being able to properly resolve def-use information for these memory locations.

Test diff

Unfortunately, we need quite a large test to trigger the effect of this PR. So GitHub doesn't really want to show the diff on the .expected changes 😂 I've pasted the relevant diffs to https://www.diffchecker.com/VMt0M8HK/.

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/AliasedSSA.qll

geoffw0

Code changes LGTM.

DCA shows a performance improvement at the cost of three results. They look like good results at a glance. Assuming these are lost due to the changes (not wobble), is there anything we can do? Should the threshold (1024) be a little higher perhaps???

What do you make of the changes in CPP IR inconsistencies?

Also should this have a change note, since it can affect results?

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/AliasedSSA.qll

MathiasVP · 2024-07-25T09:21:23Z

Code changes LGTM.

DCA shows a performance improvement at the cost of three results. They look like good results at a glance. Assuming these are lost due to the changes (not wobble), is there anything we can do? Should the threshold (1024) be a little higher perhaps???

We could make the threshold higher, but I don't think it's really worth tuning this number too much since the choice was fairly arbitrary.

What do you make of the changes in CPP IR inconsistencies?

The changes to IR consistencies are all in the b_missingOperandType type column. This means that there are some operands for which operand.getType() no longer has a result. An operand gets its type from its defining instruction, and the reason we're getting more consistency errors here are because we're bailing out on trying to resolve all the def-use information in alias analysis when we think it will be too costly to compute this. So unfortunately, I think we have to live with these extra consistency errors.

It may be possible to silence the consistency errors arising from this PR by excluding "missing type information caused by bailing out of alias analysis" if we want.

It's a bit of a double edged sword, though: we'd obviously like to know about these since they are genuinely consistency problems. However, there's also a risk of drowning in "spurious" consistency errors so that we don't notice some new actual consistency errors.

I could go either way on this. What do you think?

Also should this have a change note, since it can affect results?

I can write one, sure. It's probably going to be something vague as:

Improvement the performance of the alias analysis of large function bodies. As a result, alerts that depend on alias analysis of large function bodies may no longer be found.

I think this phrasing sounds a little bit too alarming given that we're losing 3 alerts across thousands of alerts on ~30 projects. What do you think?

geoffw0 · 2024-07-25T09:44:11Z

I don't think it's really worth tuning this number too much since the choice was fairly arbitrary.

OK, I'm going to do a brief MRVA investigation to see if this is affecting many results elsewhere. My intuition is that it is worth tuning this number, but that may just be because I'm used to Swift DCA where results are sparse and any change in them can be considered a fairly strong signal - not really the case for CPP.

It may be possible to silence the consistency errors arising from this PR by excluding "missing type information caused by bailing out of alias analysis" if we want.
...
I could go either way on this. What do you think?

I don't feel strongly about this. Happy with the consistency errors being visible.

Improvement the performance of the alias analysis of large function bodies. As a result, alerts that depend on alias
analysis of large function bodies may no longer be found.

I think this phrasing sounds a little bit too alarming given that we're losing 3 alerts across thousands of alerts on ~30
projects. What do you think?

How about:

Improved performance of alias analysis of large function bodies. In rare cases, alerts
that depend on alias analysis of large function bodies may be affected.

MathiasVP · 2024-07-25T09:48:17Z

I don't think it's really worth tuning this number too much since the choice was fairly arbitrary.

OK, I'm going to do a brief MRVA investigation to see if this is affecting many results elsewhere. My intuition is that it is worth tuning this number, but that may just be because I'm used to Swift DCA where results are sparse and any change in them can be considered a fairly strong signal - not really the case for CPP.

That's fair. What I suggest doing is to evaluate the numberOfOverlappingUses predicate from SSAConstruction and see the distribution. I expect that 99% of them will be way lower than the 1024 threshold, and we then need to figure out how much above 1024 we need to go to not reintroduce the performance regression. For the nlohmann/json database I was investigating the highest numbers were ~4000. So we certainly don't want to go that far up.

It may be possible to silence the consistency errors arising from this PR by excluding "missing type information caused by bailing out of alias analysis" if we want.
...
I could go either way on this. What do you think?

I don't feel strongly about this. Happy with the consistency errors being visible.

👍

Improvement the performance of the alias analysis of large function bodies. As a result, alerts that depend on alias
analysis of large function bodies may no longer be found.

I think this phrasing sounds a little bit too alarming given that we're losing 3 alerts across thousands of alerts on ~30
projects. What do you think?

How about:
Improved performance of alias analysis of large function bodies. In rare cases, alerts
that depend on alias analysis of large function bodies may be affected.

I like that! I'll add such a change note.

cpp/ql/test/library-tests/ir/ir/ir.cpp

jketema

I'm happy with this, but @geoffw0 should approve too.

geoffw0

Investigation - Performance vs Results vs Threshold Value

We have three (closely related) lost results on DCA. I did some fairly arbitrary before + after query runs on the MRVA-100 to cast a wider net and found no further result changes, which is reassuring - though this wasn't quite the scale I was hoping for:

query	results prior to change*	results after change*, threshold = 1024
`cpp/bad-strncpy-size` (the one that was affected on DCA)	1	1
`cpp/double-free`	11	11
`cpp/suspicious-allocation-size`	6	6
`cpp/overrunning-write`	26	26
`cpp/no-space-for-terminator`	2	2
`cpp/uncontrolled-allocation-size`	558	558

* - total number of results on MRVA-100

Here's a breakdown of the range of numberOfOverlappingUses values we're seeing, next to the number of projects with a most overlapping memory location in that range. I think it's fair to say that 1024 is towards the lower end of thresholds we should consider, as quite a few projects are theoretically affected at this level:

largest numberOfOverlappingUses	MRVA-100 projects
< 512	49
512-1023	15
1024-2047	8
2048-4095	16
4096-8191	4
8192+	6

I selected google/libphonenumber as the project from the MRVA-100 with by far the most memory locations in the largest two buckets, and nlohmann/json as the project where we originally saw this issue. nlohmann/json has clusters of exactly 770, 1,105 and 2,715 overlaps - plus a few memory locations with up to 8,136 overlaps. I ran cpp/redundant-null-check-simple on them (a relatively simple query that computes alias analysis) with various overlap thresholds:

threshold	time on google/libphonenumber	time on nlohmann/json
512	(not run)	57s
1024	26s	63s
2048	27s	88s
2716	(not run)	136s
4096	27s	221s
8192	27s	364s
no threshold	27s	370s

Bringing all of that together, I would like to recommend (in line with my earlier intuition) a threshold higher than 1024 so that we don't risk affecting query results more often than necessary. 2048 or even 4096 would be nice. However the last experiment shows that 2048 is affecting performance just a little bit (with a risk of problems in more extreme projects), and 4096 is clearly not really acceptable.

So I think the safe option is 1024, the braver option is 2048, and I approve merging this PR with any value in the range 1024 - 2048 (which includes where we are now).

MathiasVP · 2024-07-26T09:01:41Z

Thanks for the detailed analysis @geoffw0 🚀 I share your view that we can probably raise this to slightly more than 1024. However, in order to unblock the customer I'd like to start off at 1024, and we can then ask them to try out a version with a slightly higher threshold. Alternatively, we can also make this an extensibly defined value (i.e., from a .yml file) in the future.

MathiasVP added 3 commits July 24, 2024 13:46

C++: Add a testcase with many def/use pairs in alias analysis.

28cff2e

C++: Speed up alias analysis.

b1bea31

C++: Accept test changes.

5e484e4

MathiasVP requested a review from a team as a code owner July 24, 2024 13:46

github-actions bot added the C++ label Jul 24, 2024

MathiasVP added the no-change-note-required This PR does not need a change note label Jul 24, 2024

github-advanced-security bot found potential problems Jul 24, 2024

View reviewed changes

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/AliasedSSA.qll Fixed Show resolved Hide resolved

C++: Expand the macro manually to work around an extractor bug.

4a34dc1

MathiasVP mentioned this pull request Jul 25, 2024

C++: Speed up alias analysis #17056

Closed

geoffw0 reviewed Jul 25, 2024

View reviewed changes

cpp/ql/lib/semmle/code/cpp/ir/implementation/aliased_ssa/internal/AliasedSSA.qll Show resolved Hide resolved

C++: Add change note.

34ad211

MathiasVP removed the no-change-note-required This PR does not need a change note label Jul 25, 2024

github-actions bot added the documentation label Jul 25, 2024

jketema reviewed Jul 25, 2024

View reviewed changes

cpp/ql/test/library-tests/ir/ir/ir.cpp Outdated Show resolved Hide resolved

MathiasVP added 2 commits July 25, 2024 12:11

C++: Move large function to its own file.

099c282

C++: Fix QLDoc.

087b0da

jketema approved these changes Jul 25, 2024

View reviewed changes

geoffw0 approved these changes Jul 25, 2024

View reviewed changes

MathiasVP merged commit c0263be into github:main Jul 26, 2024
16 checks passed

MathiasVP mentioned this pull request May 13, 2025

C++: Fix infinite range analysis loop on invalid SSA #19477

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

C++: Speed up alias analysis #17062

C++: Speed up alias analysis #17062

Uh oh!

MathiasVP commented Jul 24, 2024 •

edited

Loading

Uh oh!

Uh oh!

geoffw0 left a comment

Uh oh!

Uh oh!

MathiasVP commented Jul 25, 2024

Uh oh!

geoffw0 commented Jul 25, 2024

Uh oh!

MathiasVP commented Jul 25, 2024 •

edited

Loading

Uh oh!

Uh oh!

jketema left a comment

Uh oh!

geoffw0 left a comment

Uh oh!

MathiasVP commented Jul 26, 2024

Uh oh!

Uh oh!

Uh oh!

C++: Speed up alias analysis #17062

C++: Speed up alias analysis #17062

Uh oh!

Conversation

MathiasVP commented Jul 24, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

The problem

The fix

Test diff

Uh oh!

Uh oh!

geoffw0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

MathiasVP commented Jul 25, 2024

Uh oh!

geoffw0 commented Jul 25, 2024

Uh oh!

MathiasVP commented Jul 25, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

jketema left a comment

Choose a reason for hiding this comment

Uh oh!

geoffw0 left a comment

Choose a reason for hiding this comment

Uh oh!

MathiasVP commented Jul 26, 2024

Uh oh!

Uh oh!

Uh oh!

MathiasVP commented Jul 24, 2024 •

edited

Loading

MathiasVP commented Jul 25, 2024 •

edited

Loading