Skip to content

Data flow: Use precise call contexts in flowFwd()#3838

Merged
aschackmull merged 4 commits into
github:mainfrom
hvitved:dataflow/flow-fwd-ctx
Aug 18, 2020
Merged

Data flow: Use precise call contexts in flowFwd()#3838
aschackmull merged 4 commits into
github:mainfrom
hvitved:dataflow/flow-fwd-ctx

Conversation

@hvitved

@hvitved hvitved commented Jun 29, 2020 •
edited
Loading

Copy link
Copy Markdown
Contributor

This is the second step towards increasing the access path restriction for C# from 3 to 5, as for other languages.

The C# project https://github.com/mono/mono includes a rather involved visitor pattern, where call contexts such as this can drastically reduce dispatch. However, we currently only apply call contexts in the last pathStep calculation, which means that we get a blow-up in the access paths reachable by flowFwd, when increasing the access path restriction. This PR therefore adds call contexts also to flowFwd, to avoid the blow-up.

Differences jobs:

@hvitved hvitved force-pushed the dataflow/flow-fwd-ctx branch 3 times, most recently from 0075a9e to e59e183 Compare July 2, 2020 07:45
@hvitved hvitved mentioned this pull request Jul 2, 2020
Merged
@hvitved hvitved marked this pull request as ready for review July 3, 2020 06:42
@hvitved hvitved requested review from a team as code owners July 3, 2020 06:42
@jbj

jbj commented Jul 7, 2020

Copy link
Copy Markdown
Contributor

I note that there are no performance or results changes in the CPP-Differences test.

@jbj jbj removed the request for review from a team July 7, 2020 13:57
@hvitved hvitved force-pushed the dataflow/flow-fwd-ctx branch from e59e183 to 1bc660a Compare July 29, 2020 07:29
@hvitved

hvitved commented Jul 29, 2020 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Rebased and updated differences jobs in the PR description.

@hvitved hvitved requested a review from a team as a code owner July 29, 2020 07:45
@hvitved hvitved force-pushed the dataflow/flow-fwd-ctx branch from c4a35a5 to e518cba Compare August 14, 2020 14:12
@hvitved

hvitved commented Aug 14, 2020

Copy link
Copy Markdown
Contributor Author

Rebased.

Here are some tuple counts for mono using this benchmark (the definition for fwd4t uses boolean instead of CallContext for the before numbers):

  fwd1 nc1 fwd2 nc2 ff1 fb1 ff2 fb2 f fwd3 nc3 fwd3t nc3t ccfwd cc fwd4 nc4 fwd4t nc4t pn
Before 3163944 1830102 928649 110442 32513 24077 11395 1448 1159 39147 23209 67287 23658 1004 77 22099 22041 22248 22106 28586
After 3163944 1830102 928649 110442 32513 24077 11395 1448 1159 39147 23209 67287 23658 1004 77 22041 21967 23001 22032 28565
Increase 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 3% 0% 0%

And here are some tuple counts for JDK using this benchmark (again, the definition for fwd4t uses boolean instead of CallContext for the before numbers):

  fwd1 nc1 fwd2 nc2 ff1 fb1 ff2 fb2 f fwd3 nc3 fwd3t nc3t ccfwd cc fwd4 nc4 fwd4t nc4t pn
Before 2604206 1555243 920416 565520 30417 22434 14298 8872 7884 208534 127783 976581 346054 11750 3955 119389 115219 379812 346083 315048
After 2604206 1555243 920416 565520 30417 22434 14298 8872 7884 208534 127783 976581 346054 11750 3955 113281 108944 403062 322831 313277
Increase 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% -5% -5% 6% -7% -1%

@adityasharad adityasharad changed the base branch from master to main August 14, 2020 18:34
aschackmull
aschackmull reviewed Aug 17, 2020
View reviewed changes

@aschackmull aschackmull left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Some inline suggestions; otherwise LGTM.

Comment thread cpp/ql/src/semmle/code/cpp/dataflow/internal/DataFlowImpl.qll Outdated
Comment thread cpp/ql/src/semmle/code/cpp/dataflow/internal/DataFlowImpl.qll Outdated
Comment thread cpp/ql/src/semmle/code/cpp/dataflow/internal/DataFlowImplCommon.qll
}

class CallContextAny extends CallContext, TAnyCallContext {
abstract class CallContextNoCall extends CallContext { }

@aschackmull aschackmull Aug 17, 2020

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Couldn't we define this simply with a charpred of not this instanceof CallContextCall instead of an abstract class? I think that would be slightly clearer.

@hvitved hvitved Aug 17, 2020

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

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

CallContext is itself abstract, so that doesn't work nicely.

Comment thread cpp/ql/src/semmle/code/cpp/dataflow/internal/DataFlowImpl.qll
@aschackmull aschackmull merged commit f75f5ab into github:main Aug 18, 2020
@hvitved hvitved deleted the dataflow/flow-fwd-ctx branch August 18, 2020 11:32
@hvitved hvitved mentioned this pull request Aug 19, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@aschackmull aschackmull aschackmull approved these changes

Assignees

@aschackmull aschackmull

Labels

C# C++ Java

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@hvitved @jbj @aschackmull