Go: Improve bad join order in guardingCall by owen-mc · Pull Request #18831 · github/codeql

owen-mc · 2025-02-21T10:44:12Z

Old code:

guardingFunction(g, f, inp, outp, p) and
c = f.getACall() and
nd = inp.getNode(c) and
localFlow(pragma[only_bind_out](outp.getNode(c)), resNode)

Old join order (note that FunctionOutput.getExitNode comes from ``outp.getNode`, which is just a wrapper for it):

Pipeline standard for DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb@dfedaw8n was evaluated in 2 iterations totaling 7ms (delta sizes total: 4).
             6   ~0%    {5} r1 = SCAN `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingFunction/5#1f27d9d8#fffbf#prev_delta` OUTPUT In.3, In.0, In.1, In.2, In.4
        722106   ~6%    {7}    | JOIN WITH `FunctionInputsAndOutputs::FunctionOutput.getExitNode/1#dispred#4c5ce77c` ON FIRST 1 OUTPUT Lhs.2, Rhs.1, Lhs.1, Lhs.3, Lhs.0, Lhs.4, Rhs.2
            19   ~0%    {7}    | JOIN WITH `Scopes::Function.getACall/0#ab99e5da` ON FIRST 2 OUTPUT Lhs.3, Lhs.1, Lhs.2, Lhs.0, Lhs.4, Lhs.5, Lhs.6
            19   ~0%    {8}    | JOIN WITH `FunctionInputsAndOutputs::FunctionInput.getNode/1#dispred#bca71294` ON FIRST 2 OUTPUT Lhs.6, Lhs.2, Lhs.3, Lhs.0, Lhs.4, Lhs.5, Lhs.1, Rhs.2
                    
             4   ~0%    {8} r2 = JOIN r1 WITH `project#Properties::Property.checkOn/3#dispred#43ad13f2` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.0
                    
            14   ~0%    {8} r3 = JOIN r1 WITH `#DataFlowUtil::localFlowStep/2#edbc0f9aPlus` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7
             0   ~0%    {8}    | JOIN WITH `project#Properties::Property.checkOn/3#dispred#43ad13f2` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.0
                    
             4   ~0%    {8} r4 = r2 UNION r3
             4   ~0%    {8}    | AND NOT `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb#prev`(FIRST 8)
                        return r4

It is finding the exit node corresponding to inp of all calls c, and only afterwards restricting c to be a call to f. This doesn't seem to be taking a long time, but it seems worth fixing the join order in case it takes a long time on some other database.

New code:

guardingFunction(g, f, inp, outp, p) and
c = pragma[only_bind_into](f).getACall() and
nd = inp.getNode(c) and
localFlow(outp.getNode(c), resNode)

New join order:

Pipeline standard for DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb@fc684wgo was evaluated in 2 iterations totaling 0ms (delta sizes total: 4).
         6   ~0%    {5} r1 = SCAN `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingFunction/5#1f27d9d8#fffbf#prev_delta` OUTPUT In.1, In.0, In.2, In.3, In.4
        19   ~0%    {6}    | JOIN WITH `Scopes::Function.getACall/0#ab99e5da` ON FIRST 1 OUTPUT Lhs.3, Rhs.1, Lhs.0, Lhs.1, Lhs.2, Lhs.4
        19   ~0%    {7}    | JOIN WITH `FunctionInputsAndOutputs::FunctionOutput.getExitNode/1#dispred#4c5ce77c` ON FIRST 2 OUTPUT Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.5, Rhs.2
        19   ~0%    {8}    | JOIN WITH `FunctionInputsAndOutputs::FunctionInput.getNode/1#dispred#bca71294` ON FIRST 2 OUTPUT Lhs.6, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.4, Lhs.5, Rhs.2
                
         4   ~0%    {8} r2 = JOIN r1 WITH `#DataFlowUtil::localFlowStep/2#edbc0f9aPlus#sinkBound#3` ON FIRST 1 OUTPUT Lhs.3, Lhs.2, Lhs.4, Lhs.5, Lhs.6, Lhs.1, Lhs.7, Lhs.0
                
         0   ~0%    {8} r3 = JOIN r1 WITH `#DataFlowUtil::localFlowStep/2#edbc0f9aPlus#bounded` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7
         0   ~0%    {8}    | JOIN WITH `#DataFlowUtil::localFlowStep/2#edbc0f9aPlus#sinkBound#3` ON FIRST 1 OUTPUT Lhs.3, Lhs.2, Lhs.4, Lhs.5, Lhs.6, Lhs.1, Lhs.7, Lhs.0
                
         4   ~0%    {8} r4 = r2 UNION r3
         4   ~0%    {8}    | AND NOT `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb#prev`(FIRST 8)
                    return r4

Copilot

Copilot reviewed 1 out of 1 changed files in this pull request and generated no comments.

Tip: Copilot code review supports C#, Go, Java, JavaScript, Markdown, Python, Ruby and TypeScript, with more languages coming soon. Learn more

aschackmull · 2025-02-21T12:04:32Z

This seems very brittle and even though the result works as intended, I don't see much reason for that - I'm actually somewhat confused about why this even works - it seems that the added pragma ought to prohibit the good order. It would seem safer to use inline_late on both inp.getNode(c) and outp.getNode(c) with bindingsets requiring both the qualifier and the call to be present, as that should ensure that they're joined ON FIRST 2 as seen in the good join-order.

smowton · 2025-02-21T14:46:05Z

I'm also confused about why that binding hint doesn't actually cue it to go the other way around, via the output/input first and only then getting to a call node.

I note that the old order shows Property.checkOn magic'd in from the use-site, whereas the new one doesn't. I don't know off-hand if the magic is a good thing or not here.

owen-mc · 2025-02-21T16:48:14Z

My intention was to make it evaluate c = f.getACall() first, since I think it has some info about f (in the recursive case at least). My thinking was that it would then be okay to evaluate outp.getNode(c) as there are fewer call nodes. I may well have messed it up though, and accidentally perturbed the order to something better. I'll have another go when I next have time.

smowton

I made a quick check to convince myself I wasn't going nuts, and surrounding any of f and c with bind-in or bind-out annotations has no effect. I would expect some to serve as a cue to go inp -> c -> f or f -> c -> inp, but apparently not. Since the annotations don't seem to be doing anything, I suggest simply dropping them.

smowton · 2025-02-21T17:20:28Z

  ) {
    guardingFunction(g, f, inp, outp, p) and
-    c = f.getACall() and
+    c = pragma[only_bind_into](f).getACall() and


Suggested change

c = pragma[only_bind_into](f).getACall() and

c = f.getACall() and

owen-mc · 2025-02-22T08:48:37Z

New RA looks good:

Pipeline standard for DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb@10408wls was evaluated in 2 iterations totaling 0ms (delta sizes total: 4).
         6   ~0%    {5} r1 = SCAN `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingFunction/5#1f27d9d8#fffbf#prev_delta` OUTPUT In.1, In.0, In.2, In.3, In.4
        19   ~0%    {6}    | JOIN WITH `Scopes::Function.getACall/0#ab99e5da` ON FIRST 1 OUTPUT Lhs.3, Rhs.1, Lhs.1, Lhs.0, Lhs.2, Lhs.4
        19   ~0%    {7}    | JOIN WITH `FunctionInputsAndOutputs::FunctionOutput.getExitNode/1#dispred#4c5ce77c` ON FIRST 2 OUTPUT Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.5, Rhs.2
        19   ~0%    {8}    | JOIN WITH `FunctionInputsAndOutputs::FunctionInput.getNode/1#dispred#bca71294` ON FIRST 2 OUTPUT Lhs.6, Lhs.2, Lhs.3, Lhs.0, Lhs.4, Lhs.5, Lhs.1, Rhs.2
                
         4   ~0%    {8} r2 = JOIN r1 WITH `project#Properties::Property.checkOn/3#dispred#43ad13f2` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.0
                
        14   ~0%    {8} r3 = JOIN r1 WITH `#DataFlowUtil::localFlowStep/2#edbc0f9aPlus` ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7
         0   ~0%    {8}    | JOIN WITH `project#Properties::Property.checkOn/3#dispred#43ad13f2` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.4, Lhs.5, Lhs.6, Lhs.7, Lhs.0
                
         4   ~0%    {8} r4 = r2 UNION r3
         4   ~0%    {8}    | AND NOT `DataFlowUtil::BarrierGuard<WrappedErrorAlwaysNil::nilTestGuard>::guardingCall/8#aa0defc4#fffffffb#prev`(FIRST 8)
                    return r4

DCA looks good.

Thought: should the actual member predicate FunctionOutput.getExitNode be inline_late? If we don't know the call then we'll get lots of results. If we don't know which FunctionOutput it is we'll also get quite a few extra. I guess I should try it and run DCA. Edit: I did that and the DCA results were awful, so I'll abandon that idea.

aschackmull

LGTM. This makes the join-order very clear and stable.

Improve bad join order

50d1bc6

Copilot AI review requested due to automatic review settings February 21, 2025 10:44

owen-mc requested a review from a team as a code owner February 21, 2025 10:44

Copilot AI reviewed Feb 21, 2025

View reviewed changes

github-actions Bot added the Go label Feb 21, 2025

owen-mc added the no-change-note-required This PR does not need a change note label Feb 21, 2025

owen-mc requested a review from smowton February 21, 2025 10:44

smowton reviewed Feb 21, 2025

View reviewed changes

Address review comments

d9d909a

aschackmull approved these changes Feb 24, 2025

View reviewed changes

owen-mc merged commit 0d994c1 into github:main Feb 24, 2025

owen-mc deleted the go/join-order-fix-2 branch February 24, 2025 22:16

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Go: Improve bad join order in guardingCall#18831

Go: Improve bad join order in guardingCall#18831
owen-mc merged 2 commits into
github:mainfrom
owen-mc:go/join-order-fix-2

owen-mc commented Feb 21, 2025

Uh oh!

Copilot AI left a comment

Uh oh!

aschackmull commented Feb 21, 2025

Uh oh!

smowton commented Feb 21, 2025

Uh oh!

owen-mc commented Feb 21, 2025

Uh oh!

smowton left a comment

Uh oh!

smowton Feb 21, 2025

Uh oh!

owen-mc commented Feb 22, 2025 •

edited

Loading

Uh oh!

aschackmull left a comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

	c = pragma[only_bind_into](f).getACall() and
	c = f.getACall() and

Conversation

owen-mc commented Feb 21, 2025

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Uh oh!

aschackmull commented Feb 21, 2025

Uh oh!

smowton commented Feb 21, 2025

Uh oh!

owen-mc commented Feb 21, 2025

Uh oh!

smowton left a comment

Choose a reason for hiding this comment

Uh oh!

smowton Feb 21, 2025

Choose a reason for hiding this comment

Uh oh!

owen-mc commented Feb 22, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aschackmull left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

owen-mc commented Feb 22, 2025 •

edited

Loading