C++: Improve AliasedSSA performance

[geoffw0]

trafficstars

Improve AliasedSSA performance, in particular on projects where it's been found to perform poorly (such as AcademySoftwareFoundation/openexr).

Draft PR. The change I propose here definitely speeds up analysis on the target project, but is (in theory) behaviour changing and I'm not at all sure it's correct. @MathiasVP I think you're easily the most knowledgeable person to discuss this area of code. Once we're settled on a change, there may be some other improvements to follow up, and it will need wider testing.

[geoffw0]

... I've tried and so far failed to write a test exposing the behaviour of getExtentOverlap in this case.

I have confirmed how it performs locally with a small range of projects and dataflow queries:

AcademySoftwareFoundation/openexr, cpp/path-injection, before: 84 results, 3,081 seconds
AcademySoftwareFoundation/openexr, cpp/path-injection, after: 84 results, 77 seconds
Sphereserver/Source-X, cpp/sql-injection, before: 0 results, 37 seconds
Sphereserver/Source-X, cpp/sql-injection, after: 0 results, 38 seconds
WebKit-JavaScriptCore, cpp/type-confusion, before: 443 results, 516 seconds
WebKit-JavaScriptCore, cpp/type-confusion, after: 443 results, 512 seconds

I've also started a DCA run as further verification.

[MathiasVP]

I have confirmed how it performs locally with a small range of projects and dataflow queries:

Dataflow doesn't use the IR ssa analysis. So I'm not surprised you're not seeing any differences 😂

If you want to find a query thst exercises the changes here, you can pick a query that uses the MustFlow library

[geoffw0]

If you want to find a query thst exercises the changes here, you can pick a query that uses the MustFlow library

That can't be right, there's a large reproducible speedup of cpp/path-injection on AcademySoftwareFoundation/openexr. Here it is again:

AcademySoftwareFoundation/openexr, cpp/path-injection, after: 84 results, 76 seconds
AcademySoftwareFoundation/openexr, cpp/path-injection, before: 84 results, 3266 seconds

(this time running the 'after' version first; no meaningful change on the two other projects I tried it on though)

---

The DCA run showed nothing of interest.

[MathiasVP]

That's because the alias analysis/the IR-based ssa is cached as part of IR construction. So it's running as one big stage. But that doesn't mean that those predicates have any influence on dataflow/taint-tracking 🙂

Dataflow and taint-tracking totally ignore all operands and instruction that are considered by alis analysis.

[geoffw0]

I've just pushed two commits adding a (direct) test and then showing the difference this change makes. I'm much less experienced with the alias analysis logic than you are, but I would say that the MustExactlyOverlap results we lose were wrong - just because something escapes just not mean it must overlap something else that escapes. On the flip side, the MayPartiallyOverlap results were probably correct (and I'm not exactly sure why we lose them yet). Do you agree?

[geoffw0]

On the flip side, the MayPartiallyOverlap results were probably correct (and I'm not exactly sure why we lose them yet).

It's caused by the additional logic in getOverlap, transforming certain outputs of getExtentOverlap from MustTotallyOverlap / MustExactlyOverlap to MayPartiallyOverlap. I can repair it (and make all of them MayPartiallyOverlap), but I'm fairly sure that will reintroduce the performance issue (and that may be worse than the missing data). I'll wait for your advice now.

[geoffw0]

@MathiasVP I'm waiting for your opinion about the test I added in the last two commits. I'm keen to get this performance issue solved but I'm struggling with lack of knowledge of the internals of this library.

[MathiasVP]

Sorry! I missed the very last part of your sentence so I totally missed that you were waiting on me for this. Yeah, this change is clearly behavior changing, and I think we should find the "right" instead of introducing faulty logic.

As I wrote in my comment above, I think there is already something fishy going on. I will take a look and get back to you!

[geoffw0]

I just had a look for the same problem on a couple more projects we've had performance troubles with lately (Miseryset/Android-ImageMagick7 and Sphereserver/Source-X) that we suspected might be related - but the change makes no difference (and there are signs those projects may have been improved by other changes). So there is in fact only one project known to be affected by this issue - AcademySoftwareFoundation/openexr.

Honestly I'm looking to finish with this work very soon. It's taken up way more of my brain space over the last few weeks than it deserves, and it has no relation to any of my actual priorities at the moment. I'm willing to:

• (a) call this an imperfect improvement, merge as-is.
• (b) abandon and close it (in practice, probably merge the new test, but not the alias analysis code change).
• (c) work on a better solution, but only with a clear understanding of what this would look like.

What are your thoughts?

[geoffw0]

@dbartol are you able to reply to the last point in the thread?

One way or another, I am going to be done with this issue next week.

[geoffw0]

I've just switched this to @dbartol's suggestion:

use = def and
result instanceof MustExactlyOverlap

• performance is still very much improved (though a newer database doesn't match the numbers I posted earlier; AcademySoftwareFoundation/openexr, cpp/path-injection, before: I aborted after 10m; after: 48s)
• the test does in fact reveal a bit about what's going on here; we lose the a / b conflation on test lines 184 and 446 (as with my solution), we also lose overlaps between things like *p and ?*p in quite a lot of places, i.e. between may and non-may accesses. I've no idea what the consequences of this are.

If it looks good I'll do a fresh DCA run.

[dbartol]

we also lose overlaps between things like *p and ?*p in quite a lot of places

@geoffw0 can you point me to an example of this?

[geoffw0]

we also lose overlaps between things like *p and ?*p in quite a lot of places

@geoffw0 can you point me to an example of this?

Look at the aliased_ssa_overlap.expected changes in https://github.com/github/codeql/pull/17225/commits/4a131dd8f133424b5c7521ae5d76a32c3cfdf60c . The query is just reporting the results of getOverlap. For example the first change, on 13:

-| ssa.cpp:13:23:13:23 | *p | ssa.cpp:13:23:13:23 | ?*p | MustTotallyOverlap |
 | ssa.cpp:13:23:13:23 | *p[0..4)<int> | ssa.cpp:13:23:13:23 | *p | MayPartiallyOverlap |
 | ssa.cpp:13:23:13:23 | *p[0..4)<int> | ssa.cpp:13:23:13:23 | *p[0..4)<int> | MustExactlyOverlap |
 | ssa.cpp:13:23:13:23 | *p[0..4)<int> | ssa.cpp:13:23:13:23 | ?*p | MayPartiallyOverlap |
 | ssa.cpp:13:23:13:23 | *p[4..8)<int> | ssa.cpp:13:23:13:23 | *p | MayPartiallyOverlap |
 | ssa.cpp:13:23:13:23 | *p[4..8)<int> | ssa.cpp:13:23:13:23 | *p[4..8)<int> | MustExactlyOverlap |
 | ssa.cpp:13:23:13:23 | *p[4..8)<int> | ssa.cpp:13:23:13:23 | ?*p | MayPartiallyOverlap |
-| ssa.cpp:13:23:13:23 | ?*p | ssa.cpp:13:23:13:23 | *p | MayPartiallyOverlap |

corresponds with this C++ code:

int ChiPhiNode(Point* p, bool which1, bool which2) { // line 13
  if (which1) {
    p->x++;
  }
  else {
    p->y++;
  }

  if (which2) {
    p->x++;
  }
  else {
    p->y++;
  }

  return p->x + p->y;
}

[geoffw0]

@dbartol how do you feel about the *p and ?*p overlap changes revealed by the test?

(at this point I'd be happy to just undo the changes if we're not comfortable with them - leaving just the new test cases and an issue in a backlog somewhere)

[geoffw0]

Merged in recent main, fixed formatting, started new DCA run.

Update: DCA run successful, no alert changes, analysis time about the same overall.

[geoffw0]

@dbartol any thoughts on my answer to your question above?

[dbartol]

@geoffw0 Ah, I forgot that there will be two EntireAllocationMemoryLocations for a given allocation: a "may" access and a "must" access. Here's a branch that adds the correct fix and restores the test expectations.

[geoffw0]

I've added your commit. I'm happy with it. ✨

cpp/path-injection on AcademySoftwareFoundation/openexr now takes 224s :+1:

@jketema perhaps we could have an opinion from someone currently on the CPP team, then we can merge this?

[jketema]

@jketema perhaps we could have an opinion from someone currently on the CPP team, then we can merge this?

I don't really have an opinion, and forming one at this point would likely take an excessive amount of time, as this is code I have never looked at or touched. If DCA is happy with @dbartol 's last changes and if @MathiasVP thinks this looks ok, I'm happy for us to merge this.

[jketema]

Thanks for the review. Merged in the latest main and running some DCA on this now.

[jketema]

DCA looks good, merging.