Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Data flow: Earlier call-context based dispatch filtering #13983

Open
wants to merge 3 commits into
base: main
Choose a base branch
from
Open

Data flow: Earlier call-context based dispatch filtering #13983

wants to merge 3 commits into from
+216 −107

Conversation

hvitved
Copy link
Contributor

@hvitved hvitved commented Aug 16, 2023 •
edited

#11725 reveals the following bad join-orders when calculating flow in

Evaluated relational algebra for predicate DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#47c9f12a::Global#StoredXSSQuery#5ea303cf::StoredXss::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowIn#11#fffffffffff@a0f95zb8 on iteration 108 running pipeline standard with tuple counts:
           1918   ~0%    {9} r1 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#47c9f12a::Global#StoredXSSQuery#5ea303cf::StoredXss::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta OUTPUT In.0, In.8, In.1, In.2, In.3, In.4, In.5, In.6, In.7
        7780921   ~0%    {11} r2 = JOIN r1 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#47c9f12a::Global#StoredXSSQuery#5ea303cf::StoredXss::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::flowIntoCallApa#5#fffff_14023#join_rhs ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.1, Rhs.2, Rhs.3, Rhs.4
                         {11} r3 = SELECT r2 ON In.10 = false AND In.6 = false OR In.10 != false
        7779113   ~0%    {11} r4 = SCAN r3 OUTPUT In.9, In.0, In.1, In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.9
        7779113   ~0%    {11} r5 = JOIN r4 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#47c9f12a::Global#StoredXSSQuery#5ea303cf::StoredXss::Config#::C#::NodeEx::getEnclosingCallable0#ff ON FIRST 1 OUTPUT Lhs.2, Lhs.1, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10, Rhs.1
                     
            257   ~9%    {11} r6 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSomeCall#f ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
             29   ~2%    {11} r7 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
            286  ~10%    {11} r8 = r6 UNION r7
                     
              1   ~0%    {11} r9 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TReturn#fff_2#join_rhs ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
        7778826   ~0%    {12} r10 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSpecificCall#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.8, Rhs.1, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9, Lhs.10
                         {12} r11 = r10 AND NOT project#DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::reducedViableImplInCallContext#3#2(Lhs.0, Lhs.1)
             46   ~0%    {12} r12 = SCAN r11 OUTPUT In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.9, In.0, In.10, In.11, In.1
                     
             46   ~0%    {11} r13 = SCAN r12 OUTPUT In.8, In.10, In.0, In.1, In.2, In.3, In.4, In.5, In.6, In.7, In.9
                     
        7778826   ~5%    {12} r14 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSpecificCall#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.8, Rhs.1, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
            142   ~1%    {12} r15 = JOIN r14 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::prunedViableImplInCallContext#2#fff ON FIRST 3 OUTPUT Lhs.0, Lhs.1, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10, Lhs.11, Lhs.2
                     
            142   ~0%    {11} r16 = JOIN r15 WITH project#DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::reducedViableImplInCallContext#3#2 ON FIRST 2 OUTPUT Lhs.0, Lhs.11, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10
                     
            188   ~0%    {11} r17 = r13 UNION r16
            189   ~0%    {11} r18 = r9 UNION r17
            475   ~1%    {11} r19 = r8 UNION r18
                         {11} r20 = r19 AND NOT DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::recordDataFlowCallSiteDispatch#2#ff(Lhs.0, Lhs.1)
            405   ~0%    {11} r21 = SCAN r20 OUTPUT In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.9, In.0, In.10, In.1
            405   ~0%    {11} r22 = JOIN r21 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSomeCall#f CARTESIAN PRODUCT OUTPUT Lhs.8, Lhs.9, Lhs.0, Lhs.1, Rhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7
                     
            257   ~9%    {11} r23 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSomeCall#f ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
             29   ~2%    {11} r24 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
            286  ~10%    {11} r25 = r23 UNION r24
                     
              1   ~0%    {11} r26 = JOIN r5 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TReturn#fff_2#join_rhs ON FIRST 1 OUTPUT Lhs.8, Lhs.10, Lhs.1, Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.9
                     
             46   ~0%    {11} r27 = SCAN r12 OUTPUT In.8, In.10, In.0, In.1, In.2, In.3, In.4, In.5, In.6, In.7, In.9
                     
            142   ~0%    {11} r28 = JOIN r15 WITH project#DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::reducedViableImplInCallContext#3#2 ON FIRST 2 OUTPUT Lhs.0, Lhs.11, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10
                     
            188   ~0%    {11} r29 = r27 UNION r28
            189   ~0%    {11} r30 = r26 UNION r29
            475   ~1%    {11} r31 = r25 UNION r30
             70   ~0%    {10} r32 = JOIN r31 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::recordDataFlowCallSiteDispatch#2#ff ON FIRST 2 OUTPUT Lhs.0, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10
             70   ~0%    {11} r33 = JOIN r32 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TSpecificCall#ff ON FIRST 1 OUTPUT Lhs.0, Lhs.9, Lhs.1, Lhs.2, Rhs.1, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8
                     
            475   ~0%    {11} r34 = r22 UNION r33
            475   ~0%    {11} r35 = r34 AND NOT DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#TaintTracking#47c9f12a::Global#StoredXSSQuery#5ea303cf::StoredXss::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowIn#11#fffffffffff#prev(Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10)
                         return r35

and flow out

Evaluated relational algebra for predicate DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow0#9#fffffffff@f99a4wn4 on iteration 27 running pipeline standard with tuple counts:
            4432    ~0%    {9} r1 = JOIN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::localFlowStepNodeCand1#2#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8
                       
             357    ~1%    {7} r2 = JOIN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowStore#11#fffffffffff#prev_delta WITH _DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac38__#join_rhs#1 CARTESIAN PRODUCT OUTPUT Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10
             353    ~0%    {8} r3 = JOIN r2 WITH num#Unit#54592529::TMkUnit#f CARTESIAN PRODUCT OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.0, Rhs.0
             353    ~0%    {9} r4 = SCAN r3 OUTPUT In.0, In.1, In.2, In.3, In.4, In.5, In.6, true, In.7
                       
              25    ~0%    {6} r5 = JOIN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowConsCand#5#fffff#prev_delta WITH num#Unit#54592529::TMkUnit#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Rhs.0, Lhs.3, Lhs.4
             208  ~106%    {9} r6 = JOIN r5 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff#prev ON FIRST 3 OUTPUT Rhs.4, Rhs.5, Rhs.6, Rhs.7, Rhs.8, Rhs.9, Lhs.4, Lhs.5, Lhs.3
                       
             561   ~23%    {9} r7 = r4 UNION r6
            4993    ~0%    {9} r8 = r1 UNION r7
                       
           10992    ~4%    {10} r9 = JOIN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowRead#10#ffffffffff#prev_delta WITH num#Unit#54592529::TMkUnit#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Rhs.0, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9
            1247   ~69%    {9} r10 = JOIN r9 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowConsCand#5#fffff#prev ON FIRST 3 OUTPUT Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Rhs.3, Rhs.4, Lhs.3
                       
            7493    ~0%    {8} r11 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta OUTPUT In.7, In.0, In.1, In.2, In.3, In.4, In.5, In.8
            1343    ~6%    {7} r12 = JOIN r11 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage2Param::ApNil#f ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7
               0    ~0%    {7} r13 = JOIN r12 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::additionalLocalFlowStepNodeCand1#2#ff ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Rhs.1
               0    ~0%    {8} r14 = JOIN r13 WITH num#Unit#54592529::TMkUnit#f CARTESIAN PRODUCT OUTPUT Lhs.6, Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Rhs.0, Lhs.5
               0    ~0%    {9} r15 = SCAN r14 OUTPUT In.0, In.1, In.2, In.3, In.4, In.5, In.6, false, In.7
                       
            7493   ~27%    {4} r16 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta OUTPUT In.7, In.0, In.1, In.8
            1338    ~5%    {7} r17 = JOIN r16 WITH _DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::T__#join_rhs ON FIRST 1 OUTPUT Lhs.1, Rhs.1, Rhs.2, Rhs.3, Rhs.4, Lhs.2, Lhs.3
               0    ~0%    {7} r18 = JOIN r17 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::additionalJumpStep#2#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6
               0    ~0%    {8} r19 = JOIN r18 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::getNodeTyp#1#ff ON FIRST 1 OUTPUT Lhs.0, Lhs.5, Lhs.2, Lhs.4, Lhs.3, Lhs.1, Rhs.1, Lhs.6
               0    ~0%    {9} r20 = SCAN r19 OUTPUT In.0, In.1, In.2, In.3, In.4, In.5, In.6, false, In.7
                       
               0    ~0%    {9} r21 = r15 UNION r20
            1247   ~69%    {9} r22 = r10 UNION r21
            6240   ~10%    {9} r23 = r8 UNION r22
                       
                           {12} r24 = SELECT DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowThrough#12#ffffffffffff#prev_delta ON In.9 = In.11
              18    ~0%    {12} r25 = SCAN r24 OUTPUT In.0, In.3, In.10, In.9, In.9, In.1, In.2, In.4, In.5, In.6, In.7, In.8
              18    ~0%    {10} r26 = JOIN r25 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::flowThroughOutOfCall#7#fffffff_0125634#join_rhs ON FIRST 5 OUTPUT Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.10, Lhs.11, Lhs.3, Rhs.5, Rhs.6
                       
                           {10} r27 = SELECT r26 ON In.9 != false
               7   ~16%    {9} r28 = SCAN r27 OUTPUT In.8, In.1, In.0, In.2, In.3, In.4, In.5, In.6, In.7
                       
              70   ~31%    {6} r29 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowIn#11#fffffffffff#prev_delta OUTPUT In.1, In.10, In.2, In.4, In.8, In.9
                           {6} r30 = r29 AND NOT DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage1::parameterMayFlowThrough#2#ff(Lhs.0, Lhs.1)
              26    ~0%    {6} r31 = SCAN r30 OUTPUT In.0, In.2, In.3, In.4, In.5, In.1
              26    ~3%    {7} r32 = JOIN r31 WITH num#Option#8eb11f23::Option#Unit#54592529::Unit#::TNone#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Rhs.0
              26    ~0%    {8} r33 = JOIN r32 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TParamNodeNone#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Rhs.0
              26    ~0%    {9} r34 = JOIN r33 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TBooleanNone#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.7, Lhs.6, Rhs.0, Lhs.3, Lhs.4, Lhs.5
                       
            7493   ~15%    {6} r35 = JOIN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f CARTESIAN PRODUCT OUTPUT Lhs.0, Rhs.0, Lhs.1, Lhs.6, Lhs.7, Lhs.8
               0    ~0%    {6} r36 = JOIN r35 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::jumpStepEx#2#ff ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Rhs.1
               0    ~0%    {7} r37 = JOIN r36 WITH num#Option#8eb11f23::Option#Unit#54592529::Unit#::TNone#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Rhs.0
               0    ~0%    {8} r38 = JOIN r37 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TParamNodeNone#f CARTESIAN PRODUCT OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Rhs.0
               0    ~0%    {9} r39 = JOIN r38 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TBooleanNone#f CARTESIAN PRODUCT OUTPUT Lhs.5, Lhs.1, Lhs.0, Lhs.7, Lhs.6, Rhs.0, Lhs.2, Lhs.3, Lhs.4
                       
              26    ~0%    {9} r40 = r34 UNION r39
              33    ~2%    {9} r41 = r28 UNION r40
                       
                           {10} r42 = SELECT r26 ON In.9 = false
              11    ~0%    {9} r43 = SCAN r42 OUTPUT In.6, In.0, In.1, In.2, In.3, In.4, In.5, In.7, In.8
               0    ~0%    {9} r44 = JOIN r43 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage2Param::ApNil#f ON FIRST 1 OUTPUT Lhs.8, Lhs.2, Lhs.1, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.0, Lhs.7
                       
              70   ~31%    {6} r45 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlowIn#11#fffffffffff#prev_delta OUTPUT In.1, In.10, In.2, In.4, In.8, In.9
              27    ~0%    {6} r46 = JOIN r45 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage1::parameterMayFlowThrough#2#ff ON FIRST 2 OUTPUT Lhs.4, Lhs.0, Lhs.2, Lhs.3, Lhs.5, Lhs.1
              27    ~0%    {7} r47 = JOIN r46 WITH num#Option#8eb11f23::Option#Unit#54592529::Unit#::TSome#ff ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.4, Lhs.5, Rhs.1
              27    ~0%    {8} r48 = JOIN r47 WITH num#DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::TNodeNormal#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1, Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6
              27    ~0%    {8} r49 = JOIN r48 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TParamNodeSome#ff ON FIRST 1 OUTPUT Lhs.5, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.6, Lhs.7, Rhs.1
              27    ~0%    {9} r50 = JOIN r49 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage2Param::apSome#1#ff ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.7, Lhs.6, Rhs.1, Lhs.4, Lhs.0, Lhs.5
                       
              27    ~0%    {9} r51 = r44 UNION r50
                       
            7493    ~7%    {10} r52 = SCAN DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow#9#fffffffff#prev_delta OUTPUT In.0, In.0, In.1, In.2, In.3, In.4, In.5, In.6, In.7, In.8
            7493    ~3%    {10} r53 = JOIN r52 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::NodeEx::getEnclosingCallable0#ff ON FIRST 1 OUTPUT Lhs.1, Lhs.9, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Rhs.1
        91338434    ~0%    {12} r54 = JOIN r53 WITH project#DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::flowOutOfCallApa#6#ffffff_14023#join_rhs ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.1, Lhs.9, Rhs.2, Rhs.3, Rhs.4
                       
                           {12} r55 = SELECT r54 ON In.11 != false
        86500516    ~0%    {11} r56 = SCAN r55 OUTPUT In.1, In.0, In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.9, In.10
                       
             506    ~0%    {10} r57 = JOIN r56 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f ON FIRST 1 OUTPUT Lhs.8, Lhs.9, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.10
                       
        86496662    ~0%    {12} r58 = JOIN r56 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TReturn#fff_201#join_rhs ON FIRST 1 OUTPUT Rhs.2, Lhs.9, Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.10
            1193    ~0%    {11} r59 = JOIN r58 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::prunedViableImplInCallContextReverse#2#fff ON FIRST 3 OUTPUT Lhs.0, Lhs.10, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.1, Lhs.11
                       
            1193    ~4%    {10} r60 = JOIN r59 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::callEnclosingCallable#2#ff ON FIRST 2 OUTPUT Lhs.1, Lhs.9, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.10
                       
                           {12} r61 = SELECT r54 ON In.11 = false
         4837918    ~0%    {11} r62 = SCAN r61 OUTPUT In.1, In.0, In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.9, In.10
                       
               0    ~0%    {10} r63 = JOIN r62 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f ON FIRST 1 OUTPUT Lhs.6, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.7, Lhs.8, Lhs.9, Lhs.10
                       
         4837914    ~3%    {12} r64 = JOIN r62 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TReturn#fff_201#join_rhs ON FIRST 1 OUTPUT Rhs.2, Lhs.9, Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.10
               2    ~0%    {11} r65 = JOIN r64 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::prunedViableImplInCallContextReverse#2#fff ON FIRST 3 OUTPUT Lhs.0, Lhs.10, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9, Lhs.1, Lhs.11
               2    ~0%    {10} r66 = JOIN r65 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::callEnclosingCallable#2#ff ON FIRST 2 OUTPUT Lhs.7, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.8, Lhs.1, Lhs.9, Lhs.10
                       
               2    ~0%    {10} r67 = r63 UNION r66
                       
               0    ~0%    {10} r68 = JOIN r67 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage2Param::ApNil#f ON FIRST 1 OUTPUT Lhs.7, Lhs.8, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.0, Lhs.6, Lhs.9
                       
            1193    ~4%    {10} r69 = r60 UNION r68
            1699    ~2%    {10} r70 = r57 UNION r69
                           {10} r71 = r70 AND NOT DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::reducedViableImplInReturn#2#ff(Lhs.0, Lhs.1)
            1236    ~1%    {10} r72 = SCAN r71 OUTPUT In.2, In.3, In.4, In.5, In.6, In.7, In.8, In.0, In.1, In.9
            1236    ~0%    {9} r73 = JOIN r72 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f CARTESIAN PRODUCT OUTPUT Lhs.9, Lhs.0, Rhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6
                       
             506    ~0%    {10} r74 = JOIN r56 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TAnyCallContext#f ON FIRST 1 OUTPUT Lhs.8, Lhs.9, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.10
                       
            1193    ~4%    {10} r75 = JOIN r59 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::callEnclosingCallable#2#ff ON FIRST 2 OUTPUT Lhs.1, Lhs.9, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.10
                       
               0    ~0%    {10} r76 = JOIN r67 WITH DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::Stage2Param::ApNil#f ON FIRST 1 OUTPUT Lhs.7, Lhs.8, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.0, Lhs.6, Lhs.9
                       
            1193    ~4%    {10} r77 = r75 UNION r76
            1699    ~2%    {10} r78 = r74 UNION r77
             463    ~1%    {10} r79 = JOIN r78 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::DispatchWithCallContext::reducedViableImplInReturn#2#ff ON FIRST 2 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8, Lhs.9
             463    ~3%    {9} r80 = JOIN r79 WITH DataFlowImplCommon#f7de413b::MakeImplCommon#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Cached::TReturn#fff ON FIRST 2 OUTPUT Lhs.9, Lhs.2, Rhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8
                       
            1699    ~0%    {9} r81 = r73 UNION r80
            1726    ~0%    {9} r82 = r51 UNION r81
            1759    ~0%    {9} r83 = r41 UNION r82
            7999    ~9%    {9} r84 = r23 UNION r83
            6288    ~3%    {9} r85 = r84 AND NOT DataFlowImpl#248dabc3::MakeImpl#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Impl#DataFlow#167ac380::DataFlowMake#DataFlowImplSpecific#21008cd7::RubyDataFlow#::Global#XSS#e59174e9::OrmTracking::Config#::C#::MkStage#Stage1#::Stage#Stage2Param#::fwdFlow0#9#fffffffff#prev(Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.8)
                           return r85

The bad join-orders happen because we first join with the full dispatch relation, only to afterwards filter away impossible call targets based on call contexts. This PR reorders the joins so we immediately filter away impossible call targets, when possible.

@hvitved hvitved force-pushed the dataflow/reduced-dispatch-early-join branch from 919931a to 570654d Compare August 16, 2023 18:57
@hvitved hvitved added the no-change-note-required This PR does not need a change note label Aug 16, 2023
@hvitved hvitved marked this pull request as ready for review August 16, 2023 19:00
aschackmull
aschackmull reviewed Aug 17, 2023
View reviewed changes
shared/dataflow/codeql/dataflow/internal/DataFlowImplCommon.qll
@@ -778,9 +780,13 @@ module MakeImplCommon<InputSig Lang> {
* `ctx`.
Copy link
Contributor

Choose a reason for hiding this comment

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

This qldoc needs an update - it's no longer correct now that you've shuffled the columns around.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

I thought it was still correct; what would you suggest updating it to?

Copy link
Contributor

Choose a reason for hiding this comment

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

The call is no longer in the context ctx. It used to be that the return chain was from result to call and then further to ctx, so the return context was the result-to-call edge. Now that edge is the CallContextReturn ctx, the result is the callable in which ctx makes sense, and call is where we can return to (the prior ctx).
So keeping the DataFlowCallable as the result is going to make the qldoc phrasing awkward, since that's not really the "result" - rather, it is the call that's the "result". I.e. "Holds if result-to-call is a viable return edge in the context ctx."

@hvitved hvitved requested review from a team as code owners August 17, 2023 18:50
@hvitved hvitved requested review from a team as code owners August 17, 2023 18:50
@hvitved hvitved force-pushed the dataflow/reduced-dispatch-early-join branch 2 times, most recently from 066ec79 to 4d951d8 Compare August 18, 2023 04:37
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@aschackmull aschackmull aschackmull left review comments

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
no-change-note-required This PR does not need a change note
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
2 participants
@hvitved @aschackmull