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

cmd/compile: do more aggressive rewrites during constant evaluation #19699

Closed
josharian opened this issue Mar 24, 2017 · 15 comments

Comments

Projects
None yet
5 participants
@josharian
Copy link
Contributor

commented Mar 24, 2017

CL 37499 taught the inliner to ignore dead code when inlining. There's a similar CL for escape analysis. And then CL 38601 did the same thing for the exporter. Three is too many--and all three would have to be remembered if, for example, we checked for for false { ... } as well as if false { ... }.

Instead, when we constant evaluate an OIF Node's n.Left to a constant bool, we should update the OIF's parent statement list.

Statement list before:

OIF n.Ninit; n.Left { n.Nbody } else { n.Rlist }

And after:

n.Ninit; _ = n.Left; n.Rlist or n.Nbody as appropriate

Then we can unwind all the other changes.

This might be tricky, since we might not have convenient access to the parent statement list to update it. (Related, kinda: #17108.)

cc @griesemer

@josharian josharian added this to the Unplanned milestone Mar 24, 2017

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 24, 2017

One option is to rewrite the OIF Node into an OBLOCK Node, like how evconst works.

Alternatively, since we're doing constant folding in typecheck anyway, we can probably just return the new OBLOCK Node and the caller will update references appropriately.

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 24, 2017

Good call. Seems pretty approachable for someone with low to moderate compiler experience, so added HelpWanted.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 24, 2017

A caveat of either approach though is we need to be careful about goto/label handling. This needs to remain valid:

label:
if false { goto label }

and this needs to remain invalid:

if false { unused: goto invalid }
var x int
invalid:
@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 24, 2017

Such things are rare enough that it's probably ok to just inhibit dead code elimination if labels or gotos are present inside the relevant blocks.

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 24, 2017

It's also entirely possible that (valid) labels/gotos inside apparently dead code like that is currently mishandled by the compiler. Moving to 1.9.

@josharian josharian modified the milestones: Go1.9, Unplanned Mar 24, 2017

@dr2chase

This comment has been minimized.

Copy link
Contributor

commented Mar 24, 2017

My solution to this annoying problem when I rewrote for-range loops for backedge rescheduling was to add another node with the same AST shape as the one transformed, but slightly different semantics. I.e., OIF, OIF_FALSE (== if(false)), OIF_TRUE (== if(true)). I suspect that this is ugly, but the other approaches I tried for dealing with label checking were uglier.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 24, 2017

We could potentially do goto validating in the frontend during type checking. Any gotos/labels introduced during order/walk would not get validated though.

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 24, 2017

Any gotos/labels introduced during order/walk would not get validated though.

That's ok.

We could potentially do goto validating in the frontend during type checking.

It's not just validation. I'm also worried about valid things like:

  i := 0
  if false {
    mutate:
       i++
  }
  if i == 0 {
    goto mutate
  }
  println(i)

If we constant-eliminate the if false block early on, we'll get the wrong answer. I think the easiest answer is to simply ignore such blocks. They're rare, and ignoring them won't impact correctness. I'm not sure whether that works for @dr2chase's case, though.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 24, 2017

That code's not valid: you can't goto into a block.

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 24, 2017

Oh right. That's C. :) Hurrah! Yes, early validation of labels/gotos sounds good, then. If we introduce bad labels/gotos in order/walk, that's our problem.

@dr2chase

This comment has been minimized.

Copy link
Contributor

commented Mar 24, 2017

Early validation is better. I thought it was beyond the scope of my change, and also risked running into the front-end cleanup.

@ALTree

This comment has been minimized.

Copy link
Member

commented Mar 26, 2017

For reference, I just hit mdempsky's caveat about labels while fuzzing the compiler.

After CL 38601 (cmd/compile: don't export dead code in inlineable fuctions) the following code does not compile any more:

package a

func F() {
l1:
	if false {
		goto l1
	}
}
package main

import "a"

func main() {
	a.F()
}

says:

# main
./0.go:6:5: label l1·1 defined and not used

@josharian josharian assigned josharian and unassigned josharian Mar 26, 2017

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Mar 28, 2017

CL 38773 covers some of this. It punts when labels or gotos are present, but in a way that shouldn't break anything, just generate less-optimized code. There is a known issue around handling checking for terminating statements that I'm unsure how best to handle. Suggestions welcome.

@ALTree any chance you could run your gosmith setup with that CL patched in for a bit? It seems very effective at finding related issues.

@gopherbot

This comment has been minimized.

Copy link

commented Mar 28, 2017

CL https://golang.org/cl/38773 mentions this issue.

@ALTree

This comment has been minimized.

Copy link
Member

commented Mar 28, 2017

@josharian sure, will do.

josharian added a commit to josharian/go that referenced this issue Apr 11, 2017

cmd/compile: eliminate dead code in if statements after typechecking
This is a more thorough and cleaner fix
than doing dead code elimination separately
during inlining, escape analysis, and export.

Unfortunately, it does add another full walk of the AST.
The performance impact is very small, but not non-zero.

If a label or goto is present in the dead code, it is not eliminated.
This restriction can be removed once label/goto checking occurs
much earlier in the compiler. In practice, it probably doesn't
matter much.

Updates golang#19699
Fixes golang#19705

name       old alloc/op      new alloc/op      delta
Template        39.2MB ± 0%       39.3MB ± 0%  +0.28%  (p=0.008 n=5+5)
Unicode         29.8MB ± 0%       29.8MB ± 0%    ~     (p=1.000 n=5+5)
GoTypes          113MB ± 0%        113MB ± 0%  -0.55%  (p=0.008 n=5+5)
SSA             1.25GB ± 0%       1.25GB ± 0%  +0.02%  (p=0.008 n=5+5)
Flate           25.3MB ± 0%       25.3MB ± 0%  -0.24%  (p=0.032 n=5+5)
GoParser        31.7MB ± 0%       31.8MB ± 0%  +0.31%  (p=0.008 n=5+5)
Reflect         78.2MB ± 0%       78.3MB ± 0%    ~     (p=0.421 n=5+5)
Tar             26.6MB ± 0%       26.7MB ± 0%  +0.21%  (p=0.008 n=5+5)
XML             42.2MB ± 0%       42.2MB ± 0%    ~     (p=0.056 n=5+5)

name       old allocs/op     new allocs/op     delta
Template          385k ± 0%         387k ± 0%  +0.51%  (p=0.016 n=5+5)
Unicode           321k ± 0%         321k ± 0%    ~     (p=1.000 n=5+5)
GoTypes          1.14M ± 0%        1.14M ± 0%    ~     (p=1.000 n=5+5)
SSA              9.71M ± 0%        9.72M ± 0%  +0.10%  (p=0.008 n=5+5)
Flate             234k ± 1%         234k ± 1%    ~     (p=0.690 n=5+5)
GoParser          315k ± 0%         317k ± 0%  +0.71%  (p=0.008 n=5+5)
Reflect           980k ± 0%         983k ± 0%  +0.30%  (p=0.032 n=5+5)
Tar               251k ± 0%         252k ± 0%  +0.55%  (p=0.016 n=5+5)
XML               392k ± 0%         393k ± 0%  +0.30%  (p=0.008 n=5+5)

Change-Id: Ia10ff4bbf5c6eae782582cc9cbc9785494d4fb83

gopherbot pushed a commit that referenced this issue Apr 18, 2017

cmd/compile: eliminate dead code in if statements after typechecking
This is a more thorough and cleaner fix
than doing dead code elimination separately
during inlining, escape analysis, and export.

Unfortunately, it does add another full walk of the AST.
The performance impact is very small, but not non-zero.

If a label or goto is present in the dead code, it is not eliminated.
This restriction can be removed once label/goto checking occurs
much earlier in the compiler. In practice, it probably doesn't
matter much.

Updates #19699
Fixes #19705

name       old alloc/op      new alloc/op      delta
Template        39.2MB ± 0%       39.3MB ± 0%  +0.28%  (p=0.008 n=5+5)
Unicode         29.8MB ± 0%       29.8MB ± 0%    ~     (p=1.000 n=5+5)
GoTypes          113MB ± 0%        113MB ± 0%  -0.55%  (p=0.008 n=5+5)
SSA             1.25GB ± 0%       1.25GB ± 0%  +0.02%  (p=0.008 n=5+5)
Flate           25.3MB ± 0%       25.3MB ± 0%  -0.24%  (p=0.032 n=5+5)
GoParser        31.7MB ± 0%       31.8MB ± 0%  +0.31%  (p=0.008 n=5+5)
Reflect         78.2MB ± 0%       78.3MB ± 0%    ~     (p=0.421 n=5+5)
Tar             26.6MB ± 0%       26.7MB ± 0%  +0.21%  (p=0.008 n=5+5)
XML             42.2MB ± 0%       42.2MB ± 0%    ~     (p=0.056 n=5+5)

name       old allocs/op     new allocs/op     delta
Template          385k ± 0%         387k ± 0%  +0.51%  (p=0.016 n=5+5)
Unicode           321k ± 0%         321k ± 0%    ~     (p=1.000 n=5+5)
GoTypes          1.14M ± 0%        1.14M ± 0%    ~     (p=1.000 n=5+5)
SSA              9.71M ± 0%        9.72M ± 0%  +0.10%  (p=0.008 n=5+5)
Flate             234k ± 1%         234k ± 1%    ~     (p=0.690 n=5+5)
GoParser          315k ± 0%         317k ± 0%  +0.71%  (p=0.008 n=5+5)
Reflect           980k ± 0%         983k ± 0%  +0.30%  (p=0.032 n=5+5)
Tar               251k ± 0%         252k ± 0%  +0.55%  (p=0.016 n=5+5)
XML               392k ± 0%         393k ± 0%  +0.30%  (p=0.008 n=5+5)

Change-Id: Ia10ff4bbf5c6eae782582cc9cbc9785494d4fb83
Reviewed-on: https://go-review.googlesource.com/38773
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

josharian added a commit to josharian/go that referenced this issue Apr 19, 2017

cmd/compile: remove haslabelgoto
As of CL 39998, it is no longer necessary.

Fixes golang#19699

Change-Id: Ie1c49c8468073c6ddeb96c03668705cf81d40c98

@gopherbot gopherbot closed this in 7189a02 Apr 20, 2017

@golang golang locked and limited conversation to collaborators Apr 20, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.