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: Avoid unnecessary non-linear recursion in fwdFlowIn #15157

Open
wants to merge 1 commit into
base: main
Choose a base branch
from
Open

Data flow: Avoid unnecessary non-linear recursion in fwdFlowIn #15157

wants to merge 1 commit into from
+60 −18

Conversation

hvitved
Copy link
Contributor

@hvitved hvitved commented Dec 19, 2023 •
edited

Non-linear recursion is only needed when type flow is enabled, so this PR makes sure that we don't do unnecessary non-linear recursion in those pruning stages where type flow is disabled.

Example DIL before 
noinline
nomagic
incremental
`DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIn/6#e7e669eb`(
  /* DataFlowImpl::MakeImpl<DataFlowImplSpecific::RubyDataFlow>::Impl<DataFlow::DataFlowMake<DataFlowImplSpecific::RubyDataFlow>::Global<HttpClient::HttpClientDisablesCertificateValidationConfig>::C>::ParamNodeEx */ `DataFlowImpl#248dabc3::MakeImpl<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Impl<DataFlow#167ac380::DataFlowMake<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Global<HttpClient#d717370f::HttpClientDisablesCertificateValidationConfig>::C>::TNodeEx` p,
  /* Unit::Unit */ Unit#54592529::TUnit apa,
  /* Unit::Unit */ Unit#54592529::TUnit state,
  /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::CallContextCall */ `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext` innercc,
  /* Unit::Unit */ Unit#54592529::TUnit t, /* Boolean::Boolean */ boolean ap
)
{
  [base_case] false()
  [recursive_case]
  (
    exists(boolean allowsFieldFlow |
      exists(
        /* DataFlowImpl::MakeImpl<DataFlowImplSpecific::RubyDataFlow>::Impl<DataFlow::DataFlowMake<DataFlowImplSpecific::RubyDataFlow>::Global<HttpClient::HttpClientDisablesCertificateValidationConfig>::C>::ArgNodeEx */ `DataFlowImpl#248dabc3::MakeImpl<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Impl<DataFlow#167ac380::DataFlowMake<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Global<HttpClient#d717370f::HttpClientDisablesCertificateValidationConfig>::C>::TNodeEx` arg,
        /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::CallContext */ `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext` dummyField1,
        boolean dummyField
       |
        exists(
          /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::BooleanOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TBooleanOption` _,
          /* Option::Option<Unit::Unit>::Option */ dontcare `Option#8eb11f23::Option<Unit#54592529::Unit>::TOption` _1,
          /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::ParamNodeOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TParamNodeOption` _2
         |
          delta previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIntoArg/10#dbbd8af8`(arg,
            state, dummyField1, _2, _1, _, t, ap, apa, dummyField)
        ) and
        exists(
          /* DataFlowDispatch::DataFlowCallable */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCallable _,
          /* DataFlowDispatch::DataFlowCall */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCall _1
         |
          previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::fwdFlowInValidEdge/9#af336f0f`(_1,
            arg, dummyField1, _, p, innercc, apa, allowsFieldFlow, dummyField)
        )
      ) and
      (
        (allowsFieldFlow = false and ap = false)
        or
        not(allowsFieldFlow = false)
      )
    )
    or
    exists(boolean allowsFieldFlow |
      exists(
        /* DataFlowImpl::MakeImpl<DataFlowImplSpecific::RubyDataFlow>::Impl<DataFlow::DataFlowMake<DataFlowImplSpecific::RubyDataFlow>::Global<HttpClient::HttpClientDisablesCertificateValidationConfig>::C>::ArgNodeEx */ `DataFlowImpl#248dabc3::MakeImpl<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Impl<DataFlow#167ac380::DataFlowMake<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Global<HttpClient#d717370f::HttpClientDisablesCertificateValidationConfig>::C>::TNodeEx` arg,
        /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::CallContext */ `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext` dummyField1,
        boolean dummyField
       |
        exists(
          /* DataFlowDispatch::DataFlowCallable */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCallable _,
          /* DataFlowDispatch::DataFlowCall */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCall _1
         |
          delta previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::fwdFlowInValidEdge/9#af336f0f`(_1,
            arg, dummyField1, _, p, innercc, apa, allowsFieldFlow, dummyField)
        ) and
        exists(
          /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::BooleanOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TBooleanOption` _,
          /* Option::Option<Unit::Unit>::Option */ dontcare `Option#8eb11f23::Option<Unit#54592529::Unit>::TOption` _1,
          /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::ParamNodeOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TParamNodeOption` _2
         |
          previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIntoArg/10#dbbd8af8`(arg,
            state, dummyField1, _2, _1, _, t, ap, apa, dummyField)
        )
      ) and
      (
        (ap = false and allowsFieldFlow = false)
        or
        not(allowsFieldFlow = false)
      )
    )
  ) and
  not(
    previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIn/6#e7e669eb`(p,
      apa, state, innercc, t, ap)
  )
}
Example DIL after 
noinline
nomagic
incremental
`DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIn/6#e7e669eb`(
  /* DataFlowImpl::MakeImpl<DataFlowImplSpecific::RubyDataFlow>::Impl<DataFlow::DataFlowMake<DataFlowImplSpecific::RubyDataFlow>::Global<HttpClient::HttpClientDisablesCertificateValidationConfig>::C>::ParamNodeEx */ `DataFlowImpl#248dabc3::MakeImpl<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Impl<DataFlow#167ac380::DataFlowMake<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Global<HttpClient#d717370f::HttpClientDisablesCertificateValidationConfig>::C>::TNodeEx` p,
  /* Unit::Unit */ Unit#54592529::TUnit apa,
  /* Unit::Unit */ Unit#54592529::TUnit state,
  /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::CallContextCall */ `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext` innercc,
  /* Unit::Unit */ Unit#54592529::TUnit t, /* Boolean::Boolean */ boolean ap
)
{
  [base_case] false()
  [recursive_case]
  exists(boolean allowsFieldFlow, boolean emptyAp |
    exists(
      /* DataFlowDispatch::DataFlowCall */ DataFlowDispatch#36b84300::Cached::TDataFlowCall dummyField2,
      /* DataFlowDispatch::DataFlowCallable */ DataFlowDispatch#36b84300::Cached::TDataFlowCallable dummyField1,
      /* DataFlowImpl::MakeImpl<DataFlowImplSpecific::RubyDataFlow>::Impl<DataFlow::DataFlowMake<DataFlowImplSpecific::RubyDataFlow>::Global<HttpClient::HttpClientDisablesCertificateValidationConfig>::C>::ArgNodeEx */ `DataFlowImpl#248dabc3::MakeImpl<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Impl<DataFlow#167ac380::DataFlowMake<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Global<HttpClient#d717370f::HttpClientDisablesCertificateValidationConfig>::C>::TNodeEx` arg
     |
      exists(boolean dummyField |
        exists(
          /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::CallContext */ `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext` dummyField3
         |
          exists(
            /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::BooleanOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TBooleanOption` _,
            /* Option::Option<Unit::Unit>::Option */ dontcare `Option#8eb11f23::Option<Unit#54592529::Unit>::TOption` _1,
            /* DataFlowImplCommon::MakeImplCommon<DataFlowImplSpecific::RubyDataFlow>::ParamNodeOption */ dontcare `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TParamNodeOption` _2
           |
            delta previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIntoArg/11#9c3d5d05`(arg,
              state, dummyField3, _2, _1, _, t, ap, emptyAp, apa, dummyField)
          ) and
          (
            (
              DataFlowImplCommon::CallContextCall#class#d7d23011(dummyField3) and
              `project#DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::callEdgeArgParamRestricted/6#e11f7cc7`(dummyField2,
                arg) and
              `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::viableImplCallContextReducedRestricted/2#ae6fa78a`(dummyField2,
                dummyField3, dummyField1) and
              `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::fwdFlowInValidEdgeTypeFlowDisabled/4#475ef90b`(dummyField2,
                dummyField1, innercc, dummyField)
            )
            or
            (
              `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TCallContext`(dummyField3) and
              `project#DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::callEdgeArgParamRestricted/6#e11f7cc7`(dummyField2,
                arg) and
              DataFlowDispatch#36b84300::Cached::TDataFlowCall(dummyField2) and
              (
                exists(
                  /* DataFlowDispatch::DataFlowCall */ DataFlowDispatch#36b84300::Cached::TDataFlowCall outer
                 |
                  `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TSpecificCall`(outer,
                    dummyField3) and
                  not(
                    `project#DataFlowImplCommon::Cached::DispatchWithCallContext::reducedViableImplInCallContext/3#1d75019d`(dummyField2,
                      outer)
                  )
                )
                or
                `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TSomeCall`(dummyField3)
                or
                `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TAnyCallContext`(dummyField3)
                or
                exists(
                  /* DataFlowDispatch::DataFlowCallable */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCallable _,
                  /* DataFlowDispatch::DataFlowCall */ dontcare DataFlowDispatch#36b84300::Cached::TDataFlowCall _1
                 |
                  `DataFlowImplCommon#f7de413b::MakeImplCommon<DataFlowImplSpecific#21008cd7::RubyDataFlow>::Cached::TReturn`(_,
                    _1, dummyField3)
                )
              ) and
              `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::fwdFlowInValidEdgeTypeFlowDisabled/4#475ef90b`(dummyField2,
                dummyField1, innercc, dummyField)
            )
          )
        ) and
        `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::fwdFlowInValidEdgeTypeFlowDisabled/4#475ef90b`(dummyField2,
          dummyField1, innercc, dummyField)
      ) and
      `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::FwdFlowIn<FwdFlowInNoRestriction>::callEdgeArgParamRestricted/6#e11f7cc7`(dummyField2,
        dummyField1, arg, p, allowsFieldFlow, apa)
    ) and
    not(
      previous rec `DataFlowImpl::Impl<HttpClient::HttpClientDisablesCertificateValidationFlow::C>::Stage2::fwdFlowIn/6#e7e669eb`(p,
        apa, state, innercc, t, ap)
    ) and
    (
      (allowsFieldFlow = false and emptyAp = true)
      or
      not(allowsFieldFlow = false)
    )
  )
}

@hvitved hvitved added the no-change-note-required This PR does not need a change note label Dec 19, 2023
@hvitved hvitved force-pushed the dataflow/fwd-flow-in-non-linear-rec branch 2 times, most recently from 41b7e3f to 057b486 Compare December 19, 2023 20:01
@hvitved hvitved force-pushed the dataflow/fwd-flow-in-non-linear-rec branch 2 times, most recently from 0e093bd to 5be4fe1 Compare December 19, 2023 20:03
@github-actions github-actions bot removed the Python label Dec 19, 2023
@hvitved hvitved marked this pull request as ready for review December 19, 2023 20:03
aschackmull
aschackmull approved these changes Jan 5, 2024
View reviewed changes
Copy link
Contributor

@aschackmull aschackmull left a comment

Choose a reason for hiding this comment

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

I haven't looked at all the dca results (they're linked prior to a couple of force-pushes - are they still sufficiently representative of the code change?), but provided that dca is fine then the code change LGTM.

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
No one assigned
Labels
DataFlow Library 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