Commit Graph

13876 Commits

Author SHA1 Message Date
Geoffrey White
77c983b99a Merge pull request #1070 from jbj/dataflow-defbyref-join-order
C++: Fix join order in def-by-reference data flow
2019-03-12 15:34:07 +00:00
Jonas Jensen
9758164dd6 Merge pull request #1083 from geoffw0/newdelete-perf2
CPP: Fix NewDelete.qll performance.
2019-03-12 16:08:46 +01:00
Max Schaefer
605f6bc6a6 Merge pull request #1082 from hvitved/merge-rc
Merge rc/1.20 into master
2019-03-12 13:49:12 +00:00
Geoffrey White
249f350cc8 Fix NewDelete.qll performance. 2019-03-12 11:32:24 +00:00
Tom Hvitved
c5450128be Merge branch 'rc/1.20' into merge-rc 2019-03-12 09:14:38 +01:00
Ziemowit Laski
75b4a6d6b3 [CPP-80] Provide kinder, gentler wording for messages (ClassesWithManyFields.{ql,qhelp}) 2019-03-11 16:16:05 -07:00
Jonas Jensen
6122cdb424 C++: Make FlowVar::toString not use Expr::toString
The `FlowVar::toString` predicate is purely a debugging aid, but
unfortunately it has to be `cached` because it's in a `cached` class.
Before this commit, it caused `Expr::toString` to be evaluated in full.
2019-03-11 11:40:49 +01:00
Jonas Jensen
ece122aca3 C++: Fix join order in def-by-reference data flow
The performance was adequate on most projects but degenerated on
https://github.com/Microsoft/Tocino.
2019-03-11 10:57:00 +01:00
Geoffrey White
0b21f4d59b CPP: Add an empty references section to the ReturnStackAllocatedMemory qhelp. 2019-03-08 23:21:47 +00:00
Jonas Jensen
a90e4a7bdf Merge pull request #1066 from xiemaisi/fix-qhelp-backticks
Fix qhelp backticks
2019-03-08 19:06:48 +01:00
Max Schaefer
a94f25e8fa C++: Fix erroneous backticks in query help. 2019-03-08 15:28:14 +00:00
Jonas Jensen
38310e0380 C++: Mention isGLValue in getResultType QLDoc 2019-03-08 11:46:35 +01:00
Robert Marsh
07bc9ca26c C++: fix whitespace 2019-03-07 13:14:58 -08:00
Robert Marsh
8a2a4678d8 C++: accept dataflow test change 2019-03-07 13:14:57 -08:00
Robert Marsh
ef836c39bb C++: respond to PR comments 2019-03-07 13:14:57 -08:00
Robert Marsh
17ad124c9e C++: remove VariableAddress from points_to test 2019-03-07 13:14:56 -08:00
Robert Marsh
7e30ce0c09 C++: add phi node support to escape analysis 2019-03-07 13:14:56 -08:00
Robert Marsh
97c11a5222 C++: points-to for argument-returning calls 2019-03-07 13:14:55 -08:00
Robert Marsh
878502f82e C++: remove duplicate logic 2019-03-07 13:14:52 -08:00
Jonas Jensen
794a8954cd C++: Simplify automaticVariableAddressEscapes
The `automaticVariableAddressEscapes` predicate got join-ordered badly
in its `unaliased_ssa` version. These are the tuple counts on Wireshark,
where one pipeline step is seen to have 716 million tuples:

```
[2019-03-02 11:29:41] (42s) Starting to evaluate predicate AliasAnalysis::automaticVariableAddressEscapes#2#f
[2019-03-02 11:30:06] (67s) Tuple counts:
                      353419    ~0%      {1} r1 = JOIN project#Instruction::VariableAddressInstruction#class#2#ff WITH AliasAnalysis::resultEscapesNonReturn#2#f ON project#Instruction::VariableAddressInstruction#class#2#ff.<0>=AliasAnalysis::resultEscapesNonReturn#2#f.<0> OUTPUT FIELDS {AliasAnalysis::resultEscapesNonReturn#2#f.<0>}
                      353419    ~0%      {2} r2 = JOIN r1 WITH IRConstruction::Cached::getInstructionEnclosingFunctionIR#ff@staged_ext ON r1.<0>=IRConstruction::Cached::getInstructionEnclosingFunctionIR#ff@staged_ext.<0> OUTPUT FIELDS {IRConstruction::Cached::getInstructionEnclosingFunctionIR#ff@staged_ext.<1>,r1.<0>}
                      353419    ~0%      {2} r3 = JOIN r2 WITH FunctionIR::FunctionIR::getFunction_dispred#3#ff ON r2.<0>=FunctionIR::FunctionIR::getFunction_dispred#3#ff.<0> OUTPUT FIELDS {FunctionIR::FunctionIR::getFunction_dispred#3#ff.<1>,r2.<1>}
                      716040298 ~0%      {2} r4 = JOIN r3 WITH IRVariable::IRVariable#class#3#ff_10#join_rhs ON r3.<0>=IRVariable::IRVariable#class#3#ff_10#join_rhs.<0> OUTPUT FIELDS {IRVariable::IRVariable#class#3#ff_10#join_rhs.<1>,r3.<1>}
                      4480139   ~0%      {2} r5 = JOIN r4 WITH IRVariable::IRAutomaticVariable#class#3#ff ON r4.<0>=IRVariable::IRAutomaticVariable#class#3#ff.<0> OUTPUT FIELDS {r4.<1>,r4.<0>}
                      66760     ~91%     {1} r6 = JOIN r5 WITH Instruction::VariableInstruction::getVariable_dispred#2#ff ON r5.<0>=Instruction::VariableInstruction::getVariable_dispred#2#ff.<0> AND r5.<1>=Instruction::VariableInstruction::getVariable_dispred#2#ff.<1> OUTPUT FIELDS {r5.<1>}
                                         return r6
[2019-03-02 11:30:06] (67s)  >>> Relation AliasAnalysis::automaticVariableAddressEscapes#2#f: 35531 rows using 0 MB
```

The predicate contained a cyclic join, which is always hard to optimize.
I couldn't see a reason to join the `FunctionIR`, so I removed that
part. The predicate is now fast, and there are no changes in the tests.
2019-03-07 13:14:51 -08:00
Robert Marsh
a72cd23d1d C++: fix escape test failures 2019-03-07 13:14:51 -08:00
Robert Marsh
09321ee062 C++: refactor escape analysis for performance 2019-03-07 13:14:51 -08:00
Robert Marsh
6f76c13385 C++: fix unused variable warning 2019-03-07 13:14:50 -08:00
Robert Marsh
726f38c802 C++: refactor alias analysis for performance 2019-03-07 13:14:50 -08:00
Robert Marsh
c70bd285de C++: assume arguments to virtual functions escape 2019-03-07 13:14:49 -08:00
Robert Marsh
2c94a8887d C++: test for virtual functions in escape analysis 2019-03-07 13:14:49 -08:00
Robert Marsh
6089172554 C++: escape analysis for this parameters 2019-03-07 13:14:49 -08:00
Robert Marsh
466e110338 C++: add new interprocedural escape analysis 2019-03-07 13:14:48 -08:00
Robert Marsh
bd39698528 C++: test changes for interproc escape analysis 2019-03-07 13:14:48 -08:00
Robert Marsh
0efb110512 C++: docs for AllocaInLoop 2019-03-06 09:35:17 -08:00
Jonas Jensen
57732ee6f9 Merge pull request #1008 from geoffw0/wprintf
CPP: Clean up and fix FormattingFunction, FormatLiteral
2019-03-06 15:08:29 +00:00
Geoffrey White
693937367d Merge pull request #1047 from jbj/dataflow-StmtExpr
C++: Data flow through StmtExpr
2019-03-06 10:33:12 +00:00
Geoffrey White
2bac7f1516 CPP: Deprecate old mechanisms FormattingFunction.isWideCharDefault and FormatLiteral.isWideCharDefault. 2019-03-06 10:23:46 +00:00
Geoffrey White
5b8a6c8335 CPP: Remove no longer used FormatLiteral.getEffectiveCharConversionChar. 2019-03-06 10:23:45 +00:00
Geoffrey White
e1447787e3 CPP: Remove dubious case from FormatLiteral.getMaxConvertedLength. 2019-03-06 10:23:45 +00:00
Geoffrey White
1b71accbfe CPP: Fix a bug in FormattingFunction.getDefaultCharType. 2019-03-06 10:23:45 +00:00
Geoffrey White
e59b3c28e4 CPP: Modernize FormatLiteral.getConversionType1b. 2019-03-06 10:23:45 +00:00
Geoffrey White
ac708a569e CPP: Clean up formatting in FormatLiteral.getEffectiveCharConversionChar somewhat. 2019-03-06 10:23:45 +00:00
Geoffrey White
9f9712047c CPP: Add a few more tests of '%c'. 2019-03-06 10:23:45 +00:00
Jonas Jensen
80b0765618 C++: Make IR DataFlow dispatch use non-IR version
This removes code duplication and ensures that the IR version also gets
the support for flow across link targets.
2019-03-06 10:08:14 +01:00
Jonas Jensen
10ce13d1e9 C++: Tests for cross-target dispatch 2019-03-06 10:08:13 +01:00
Jonas Jensen
14f1ecb456 C++: Data flow dispatch across link targets 2019-03-06 10:08:13 +01:00
Jonas Jensen
94699175a4 Merge pull request #1046 from xiemaisi/rc/1.20
Merge rc/1.20 into master
2019-03-06 07:49:15 +00:00
Jonas Jensen
6ef946c2b0 C++: Make IR TaintTracking available on LGTM
Because this new library is not used in a default query, it needs to be
imported here in order to be available in the LGTM query console.
2019-03-05 18:05:27 +01:00
Jonas Jensen
b3d935063f Merge pull request #815 from geoffw0/keyset
CPP: dbscheme annotations
2019-03-05 14:53:46 +00:00
Jonas Jensen
0a57767cc6 C++: Data flow through StmtExpr 2019-03-05 14:36:40 +01:00
Jonas Jensen
a2de057c26 C++: Test for StmtExpr data flow 2019-03-05 14:34:19 +01:00
Jonas Jensen
9d595aa5ea Merge pull request #1033 from geoffw0/newdelete-perf
CPP: NewDelete.qll performance
2019-03-05 12:52:59 +00:00
Jonas Jensen
d310338c9b C++: Implement dominanceFrontier with recursion
This implementation is borrowed from Java's QL library and offers a
great performance improvement. For example, on Wireshark the performance
goes from

    Dominance::bbDominates#ff ....... 40.3s
    SSAUtils::dominanceFrontier#ff .. 30s

to

    SSAUtils::dominanceFrontier#ff .. 418ms (executed 67 times)

The big performance problem before was the need to materialize
`bbDominates`, which is the reflexive-transitive "basic block dominates"
relation. It had 79 million rows on Wireshark.
2019-03-05 11:54:45 +01:00
Geoffrey White
4e1e3131ac CPP: Revert annotation on 'externalData'. 2019-03-05 10:22:33 +00:00