Commit Graph

2596 Commits

Author SHA1 Message Date
Anders Schack-Mulligen
9140cbefc0 Dataflow: Sync. 2023-04-27 14:55:23 +02:00
Robert Marsh
3f8638643e C++: respond to PR comments 2023-04-26 14:56:10 -04:00
Mathias Vorreiter Pedersen
6bfdbef697 C++: Fix implicit 'this'. 2023-04-26 18:06:44 +01:00
Mathias Vorreiter Pedersen
b18e096f7f C++: Fix missing result for 'getFunction' and accept test changes. 2023-04-26 18:01:39 +01:00
Mathias Vorreiter Pedersen
60aab206b0 C++: Join on two columns instead of one.
Before:
```
Evaluated non-recursive predicate TranslatedElement#ea057665::TranslatedElement::getInstructionVariable#1#dispred#fff@146210id in 201548ms (size: 3469729).
Evaluated relational algebra for predicate TranslatedElement#ea057665::TranslatedElement::getInstructionVariable#1#dispred#fff@146210id with tuple counts:
  ...
     1812768   ~3%    {3} r65 = JOIN num#InstructionTag#c9183db3::OnlyInstructionTag#f WITH TranslatedExpr#043317a1::TranslatedNonFieldVariableAccess#ff CARTESIAN PRODUCT OUTPUT Rhs.1, Lhs.0, Rhs.0
     1812767   ~0%    {4} r66 = JOIN r65 WITH Access#8878f617::Access::getTarget#0#dispred#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.0
  3996407117   ~3%    {5} r67 = JOIN r66 WITH TranslatedElement#ea057665::getIRUserVariable#2#fff_102#join_rhs ON FIRST 1 OUTPUT Lhs.3, Rhs.1, Lhs.1, Lhs.2, Rhs.2
     1815194   ~0%    {3} r68 = JOIN r67 WITH TranslatedExpr#043317a1::getEnclosingDeclaration#1#ff ON FIRST 2 OUTPUT Lhs.3, Lhs.2, Lhs.4
  ...
```

After:
```
Evaluated non-recursive predicate TranslatedExpr#043317a1::accessHasEnclosingDeclarationAndVariable#3#fff@665ccb8o in 865ms (size: 2769549).
Evaluated relational algebra for predicate TranslatedExpr#043317a1::accessHasEnclosingDeclarationAndVariable#3#fff@665ccb8o with tuple counts:
        2769549  ~1%    {3} r1 = JOIN Access#8878f617::Access::getTarget#0#dispred#ff WITH TranslatedExpr#043317a1::getEnclosingDeclaration#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0
                        return r1
...
Evaluated non-recursive predicate TranslatedElement#ea057665::TranslatedElement::getInstructionVariable#1#dispred#fff@7d4d33to in 805ms (size: 3469729).
Evaluated relational algebra for predicate TranslatedElement#ea057665::TranslatedElement::getInstructionVariable#1#dispred#fff@7d4d33to with tuple counts:
  ...
  1963209   ~0%    {2} r34 = JOIN TranslatedElement#ea057665::getIRUserVariable#2#fff WITH TranslatedExpr#043317a1::accessHasEnclosingDeclarationAndVariable#3#fff ON FIRST 2 OUTPUT Rhs.2, Lhs.2
  1815194   ~2%    {2} r35 = JOIN r34 WITH TranslatedExpr#043317a1::TranslatedNonFieldVariableAccess#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.1, Rhs.1
  1815194   ~0%    {3} r36 = JOIN r35 WITH num#InstructionTag#c9183db3::OnlyInstructionTag#f CARTESIAN PRODUCT OUTPUT Lhs.1, Rhs.0, Lhs.0
  ...
```
2023-04-26 16:32:43 +01:00
Anders Schack-Mulligen
d681671356 Dataflow: Sync. 2023-04-26 14:45:07 +02:00
Mathias Vorreiter Pedersen
648c08bcd9 C++: Fix enclosing functions for static locals. 2023-04-25 17:51:04 +01:00
Mathias Vorreiter Pedersen
d14ee931e1 C++: IR translation for non-runtime-initialized static local variables. 2023-04-25 17:51:04 +01:00
Michael Nebel
656d8d2451 Sync files. 2023-04-20 11:29:51 +02:00
Robert Marsh
3c2b4e8456 C++: AST-based wrapper for new range analysis 2023-04-18 15:52:43 -04:00
Mathias Vorreiter Pedersen
6e5f09f7bb C++: Ignore more instructions in dataflow. 2023-04-18 13:32:24 +01:00
Mathias Vorreiter Pedersen
bb8c3de6b2 Merge pull request #12599 from rdmarsh2/rdmarsh2/range-analysis-overflow
C++: add overflow detection to new range analysis
2023-04-17 20:18:44 +01:00
Mathias Vorreiter Pedersen
2a14479bf3 C++: Autoformat. 2023-04-17 09:34:44 +01:00
Mathias Vorreiter Pedersen
a87e67d89d C++: Fix join orders.
Before:

```
Tuple counts for RangeAnalysisStage#38d7ce80::RangeStage#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisImpl#edd69a76::ConstantBounds#FloatDelta#0eab55d1::FloatOverflow#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::potentiallyOverflowingExpr#2#ff/2@36ed7auu after 42.1s:
    365        ~0%     {2} r1 = JOIN num#SemanticOpcode#e6f455a5::TNegate#f WITH SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs ON FIRST 1 OUTPUT false, Rhs.1 'expr'

    0          ~0%     {2} r2 = JOIN num#SemanticOpcode#e6f455a5::TSubOne#f WITH SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs ON FIRST 1 OUTPUT false, Rhs.1 'expr'

    365        ~0%     {2} r3 = r1 UNION r2

    0          ~0%     {2} r4 = JOIN num#SemanticOpcode#e6f455a5::TAddOne#f WITH project#SemanticExpr#91573b9a::SemKnownExpr#class#fff_10#join_rhs ON FIRST 1 OUTPUT true, Rhs.1 'expr'

    2          ~0%     {2} r5 = JOIN m#RangeAnalysisStage#38d7ce80::RangeStage#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisImpl#edd69a76::ConstantBounds#FloatDelta#0eab55d1::FloatOverflow#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::boundedPhiInp1#6#ffbfff WITH num#SemanticOpcode#e6f455a5::TMul#f CARTESIAN PRODUCT OUTPUT Rhs.0, Lhs.0 'positively'
    22026      ~0%     {2} r6 = JOIN r5 WITH SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs ON FIRST 1 OUTPUT Lhs.1 'positively', Rhs.1 'expr'

    2          ~0%     {2} r7 = JOIN m#RangeAnalysisStage#38d7ce80::RangeStage#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisImpl#edd69a76::ConstantBounds#FloatDelta#0eab55d1::FloatOverflow#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::boundedPhiInp1#6#ffbfff WITH num#SemanticOpcode#e6f455a5::TShiftLeft#f CARTESIAN PRODUCT OUTPUT Rhs.0, Lhs.0 'positively'
    1978       ~0%     {2} r8 = JOIN r7 WITH SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs ON FIRST 1 OUTPUT Lhs.1 'positively', Rhs.1 'expr'

    24004      ~0%     {2} r9 = r6 UNION r8
    24004      ~0%     {2} r10 = r4 UNION r9
    24369      ~0%     {2} r11 = r3 UNION r10

    2726       ~1%     {2} r12 = JOIN project#SemanticExpr#91573b9a::SemDivExpr#fffff WITH project#SemanticExpr#91573b9a::SemKnownExpr#class#fff#2 ON FIRST 1 OUTPUT Rhs.1, Lhs.0 'expr'
    1900       ~2%     {2} r13 = JOIN r12 WITH SemanticType#3725723c::SemFloatingPointType#ff ON FIRST 1 OUTPUT false, Lhs.1 'expr'

    4500       ~0%     {1} r14 = JOIN SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs WITH num#SemanticOpcode#e6f455a5::TAdd#f ON FIRST 1 OUTPUT Lhs.1 'expr'

    0          ~0%     {1} r15 = JOIN SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs WITH num#SemanticOpcode#e6f455a5::TPointerAdd#f ON FIRST 1 OUTPUT Lhs.1 'expr'

    4500       ~0%     {1} r16 = r14 UNION r15
    4000       ~0%     {2} r17 = JOIN r16 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff#2 ON FIRST 1 OUTPUT Rhs.1, Lhs.0 'expr'
    7000       ~0%     {2} r18 = JOIN r17 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1 'expr'

    1264       ~0%     {2} r19 = JOIN r18 WITH num#Sign#2ecc774b::TNeg#f ON FIRST 1 OUTPUT Lhs.0, Lhs.1 'expr'
    188324151  ~0%     {2} r20 = JOIN r19 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.1 'expr', Rhs.1
    1000       ~0%     {2} r21 = JOIN r20 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff ON FIRST 2 OUTPUT false, Lhs.0 'expr'

    2900       ~0%     {2} r22 = r13 UNION r21

    3259       ~2%     {2} r23 = JOIN r18 WITH num#Sign#2ecc774b::TPos#f ON FIRST 1 OUTPUT Lhs.0, Lhs.1 'expr'
    1521124720 ~0%     {2} r24 = JOIN r23 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.1 'expr', Rhs.1
    3000       ~2%     {2} r25 = JOIN r24 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff ON FIRST 2 OUTPUT true, Lhs.0 'expr'
```
(I stopped evaluation midway.)

After:

```ql
Evaluated relational algebra for predicate RangeAnalysisStage#38d7ce80::RangeStage#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisImpl#edd69a76::ConstantBounds#FloatDelta#0eab55d1::FloatOverflow#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::potentiallyOverflowingExpr#2#ff@dc3a0712 with tuple counts:
  26269   ~2%    {2} r1 = _SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs_m#RangeAnalysisStage#38d7ce80::R__#shared UNION _SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs_SemanticType#3725723c::SemFloati__#shared

  26269   ~2%    {2} r2 = _num#SemanticOpcode#e6f455a5::TAddOne#f_project#SemanticExpr#91573b9a::SemKnownExpr#class#fff_10#joi__#shared UNION r1

  41333   ~1%    {2} r3 = JOIN _SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs_num#SemanticOpcode#e6f455a5::TAd__#shared WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1

  5806   ~2%    {2} r4 = JOIN r3 WITH num#Sign#2ecc774b::TNeg#f ON FIRST 1 OUTPUT Lhs.1, Lhs.0
  5806   ~1%    {3} r5 = JOIN r4 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff#2 ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0
  3612   ~0%    {2} r6 = JOIN r5 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 2 OUTPUT false, Lhs.2

  18476   ~1%    {2} r7 = JOIN r3 WITH num#Sign#2ecc774b::TPos#f ON FIRST 1 OUTPUT Lhs.1, Lhs.0
  18476   ~1%    {3} r8 = JOIN r7 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff#2 ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.0
  18444   ~2%    {2} r9 = JOIN r8 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 2 OUTPUT true, Lhs.2

  22056   ~0%    {2} r10 = r6 UNION r9

  24137   ~2%    {2} r11 = JOIN _SemanticExpr#91573b9a::SemExpr::getOpcode#0#dispred#fb_10#join_rhs_num#SemanticOpcode#e6f455a5::TPo__#shared WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1

  16966   ~2%    {1} r12 = JOIN r11 WITH num#Sign#2ecc774b::TPos#f ON FIRST 1 OUTPUT Lhs.1
  16966   ~4%    {2} r13 = JOIN r12 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff ON FIRST 1 OUTPUT Rhs.1, Lhs.0
  24917   ~1%    {2} r14 = JOIN r13 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1
  2781   ~0%    {2} r15 = JOIN r14 WITH num#Sign#2ecc774b::TNeg#f ON FIRST 1 OUTPUT false, Lhs.1

  2817   ~0%    {1} r16 = JOIN r11 WITH num#Sign#2ecc774b::TNeg#f ON FIRST 1 OUTPUT Lhs.1
  2817   ~0%    {2} r17 = JOIN r16 WITH project#SemanticExpr#91573b9a::SemBinaryExpr#fffff ON FIRST 1 OUTPUT Rhs.1, Lhs.0
  6922   ~0%    {2} r18 = JOIN r17 WITH SignAnalysisCommon#4b1623af::SignAnalysis#FloatDelta#0eab55d1::FloatDelta#RangeUtils#6da26777::RangeUtil#FloatDelta#0eab55d1::FloatDelta#RangeAnalysisConstantSpecific#878f81e8::CppLangImplConstant##::semExprSign#1#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1
  2765   ~1%    {2} r19 = JOIN r18 WITH num#Sign#2ecc774b::TPos#f ON FIRST 1 OUTPUT true, Lhs.1

  5546   ~0%    {2} r20 = r15 UNION r19
  27602   ~0%    {2} r21 = r10 UNION r20
  53871   ~0%    {2} r22 = r2 UNION r21
                  return r22
```
2023-04-17 09:28:31 +01:00
Mathias Vorreiter Pedersen
7eee589304 Merge pull request #12569 from andersfugmann/andersfugmann/use_after_free
C++: Implement use-after-free and double-free queries using the new IR use-use dataflow
2023-04-17 08:01:58 +01:00
Geoffrey White
ba982e2f85 Merge pull request #12752 from gsingh93/buffer-access-array-expr
C++: Consider ArrayExpr with non-constant size expressions as a BufferAccess
2023-04-14 15:31:20 +01:00
Robert Marsh
fddbffee6f C++: autoformat 2023-04-13 11:13:27 -04:00
Robert Marsh
316cb95547 C++: respond to overflow PR comments 2023-04-13 10:03:55 -04:00
Chris Smowton
7eefa43f5a Rename and document viableArgParamSpecific to make clear it is a temporary hook. 2023-04-12 14:33:46 +01:00
Chris Smowton
4d8ca3d759 Add dataflow callback to filter out receiver argument flow to Golang interface dispatch candidates.
Other langauges stub the callback.
2023-04-12 14:19:06 +01:00
Mathias Vorreiter Pedersen
ab70f5722e C++: More QLDoc. 2023-04-12 11:22:31 +01:00
Mathias Vorreiter Pedersen
d65bb3b232 C++: Make basic block information available from dataflow nodes. 2023-04-11 13:52:26 +01:00
Robert Marsh
915c969efe Merge branch 'main' into rdmarsh2/range-analysis-overflow 2023-04-05 16:19:55 -04:00
Mathias Vorreiter Pedersen
7a32299f34 C++: Oops. Forgot to replace one use of a deprecated predicate. 2023-04-04 15:30:02 +01:00
Mathias Vorreiter Pedersen
f2197e67f5 C++: Deprecate single-parameter 'getFieldExpr' and 'getElementExpr'. 2023-04-04 15:14:27 +01:00
Mathias Vorreiter Pedersen
f28cf25ba2 Merge pull request #12755 from MathiasVP/aggregate-initialization-ir
C++: IR generation for repeated initializers
2023-04-04 15:04:55 +01:00
Mathias Vorreiter Pedersen
6c26ad7c2d C++: Expand QLDoc. 2023-04-04 14:02:31 +01:00
Mathias Vorreiter Pedersen
86fd2d5309 Merge pull request #12747 from MathiasVP/promote-new-range-analysis-out-of-experimental
C++: Promote IR-based range-analysis library out of experimental
2023-04-04 11:17:48 +01:00
Mathias Vorreiter Pedersen
52682e2ccb C++: Replace the word 'repetition' with 'position' to properly reflect the semantics of the dbscheme. 2023-04-04 11:02:55 +01:00
Mathias Vorreiter Pedersen
6dd6488437 C++: Introduce 'getAnElementExpr' and 'getAnExpr'. 2023-04-04 10:12:25 +01:00
Mathias Vorreiter Pedersen
bef0a159c0 C++: IR generation for repeated initializers. 2023-04-04 10:08:32 +01:00
Gulshan Singh
56dc2a4d4e C++: Consider ArrayExpr with non-constant size expressions as BufferAccesses 2023-04-03 23:11:14 -07:00
Alexandre Boulgakov
0aa39c0ca0 Merge pull request #12712 from github/sashabu/repeated-initializers
C++: Support repeated initializers in dbscheme.
2023-04-03 14:46:17 +01:00
Mathias Vorreiter Pedersen
e8800a6dba C++: Move the new range-analysis library out of experimental and into an 'internal' directory. 2023-04-03 13:53:43 +01:00
Mathias Vorreiter Pedersen
6638df1578 C++: Sync identical files. 2023-03-31 18:25:34 +01:00
Mathias Vorreiter Pedersen
0b33d26852 C++: Speed up non-linear recursion in GVN. 2023-03-31 18:25:19 +01:00
Alexandre Boulgakov
d0a77a8433 C++: Support repeated initializers in dbscheme. 2023-03-31 17:53:12 +01:00
Mathias Vorreiter Pedersen
62bc8074ba Merge pull request #12626 from gsingh93/buffer-access-size-expr
C++: Add getSizeExpr and getSizeMult predicates to BufferAccess
2023-03-30 10:49:12 +01:00
Mathias Vorreiter Pedersen
6275a015a4 Merge pull request #12708 from MathiasVP/dont-break-ir-cfg-on-vla
C++: Don't produce partial CFGs when using VLAs
2023-03-30 09:16:10 +01:00
Gulshan Singh
abec99badb C++: Add getSizeExpr and getSizeMult predicates to BufferAccess 2023-03-29 08:26:00 -07:00
Mathias Vorreiter Pedersen
3bd193f721 C++: Fix Code Scanning errors. 2023-03-29 14:02:34 +01:00
Mathias Vorreiter Pedersen
fb6e45b6f4 C++: Emit a NoOp during CFG construction for VLAs. 2023-03-29 13:58:39 +01:00
Jeroen Ketema
0acca2ba76 Merge pull request #12687 from jketema/unit-2
Make imports of `codeql.util.Unit` private
2023-03-29 13:07:12 +02:00
Jeroen Ketema
3b8ad087eb Make imports of codeql.util.Unit private 2023-03-28 14:14:13 +02:00
Anders Schack-Mulligen
d406b051fc Dataflow: Remove accidentally exposed predicates. 2023-03-28 10:04:21 +02:00
Jeroen Ketema
977f15f8a4 Merge pull request #12649 from jketema/unit
Replace all definitions of `Unit` by `import codeql.util.Unit`
2023-03-27 08:49:50 +02:00
Anders Schack-Mulligen
6db8c8b19f Merge pull request #12656 from aschackmull/dataflow/qldoc
Dataflow: Minor qldoc fix
2023-03-24 14:57:39 +01:00
Anders Schack-Mulligen
85511ba19d Dataflow: Sync 2023-03-24 12:42:06 +01:00
Jeroen Ketema
a87a9438c7 Replace all definitions of Unit by import codeql.util.Unit 2023-03-24 10:39:34 +01:00
Jeroen Ketema
8b5393661b C++: Address review comments 2023-03-24 10:34:10 +01:00