Sitelet https://web.archive.org/web/20260605032452/https://github.com/github/codeql/pull/12184
Skip to content

C++: Better discrimination for union Contents#12184

Merged
MathiasVP merged 1 commit into
github:mathiasvp/replace-ast-with-ir-use-usedataflowfrom
MathiasVP:discriminate-union-contents
Feb 14, 2023
Merged

C++: Better discrimination for union Contents#12184
MathiasVP merged 1 commit into
github:mathiasvp/replace-ast-with-ir-use-usedataflowfrom
MathiasVP:discriminate-union-contents

Conversation

@MathiasVP
Copy link
Copy Markdown
Contributor

@MathiasVP MathiasVP commented Feb 14, 2023 •

This PR fixes a performance problem on the use-use flow branch.

One of the things the dataflow library computes is the possible set of tails for an access path that starts with a specific Content. We have modelled a read of (or write to) a union using a Content branch defined by the union type itself (so that you can write to one union member and read it off another).

The problem is that this makes the set of tails for a union Content the a lot larger than the set of tails for a specific Field (since there's just 1 Content value per union in the database).

Performance-wise the best fix would be to model unions as we model regular struct fields (as this would increase the discrimination factor by creating a Content branch for each field in the union instead of 1 Content branch for each union in the database). However, this would prevent a write to one union field to flow to another union read of a different field. This pattern occurs quite frequently (especially in C projects where it's not actually undefined behavior).

Instead, this PR adds another column to the union Content branch that specifies "the size of the field that's currently active in the union". This means there are more union Content branches in the database (so that the set of tail access paths is spread out more across those Contents), while still ensuring that we get dataflow in examples like:

union A {
  int x;
  unsigned char buffer[sizeof(int)];
};

void test() {
  A a;
  a.x = source();
  sink(a.buffer);
}

Locally, this gives me a large speedup for the Nelson project.

@MathiasVP MathiasVP requested a review from a team as a code owner February 14, 2023 13:41
@github-actions github-actions Bot added the C++ label Feb 14, 2023
@MathiasVP MathiasVP added the no-change-note-required This PR does not need a change note label Feb 14, 2023
Copy link
Copy Markdown
Contributor

@jketema jketema left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM if DCA is happy.

@MathiasVP MathiasVP merged commit c11218f into github:mathiasvp/replace-ast-with-ir-use-usedataflow Feb 14, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

C++ no-change-note-required This PR does not need a change note

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants