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

josharian · 2017-03-24T17:20:22Z

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

The text was updated successfully, but these errors were encountered:

mdempsky · 2017-03-24T18:18:02Z

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 · 2017-03-24T18:21:24Z

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

mdempsky · 2017-03-24T18:21:50Z

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 · 2017-03-24T18:30:08Z

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 · 2017-03-24T18:31:45Z

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.

dr2chase · 2017-03-24T18:33:50Z

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 · 2017-03-24T18:46:03Z

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 · 2017-03-24T18:51:36Z

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 · 2017-03-24T18:53:09Z

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

josharian · 2017-03-24T18:55:13Z

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 · 2017-03-24T18:58:15Z

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

ALTree · 2017-03-26T19:28:10Z

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 · 2017-03-28T19:53:33Z

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 · 2017-03-28T20:00:29Z

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

ALTree · 2017-03-28T20:42:14Z

@josharian sure, will do.

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

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>

As of CL 39998, it is no longer necessary. Fixes golang#19699 Change-Id: Ie1c49c8468073c6ddeb96c03668705cf81d40c98

josharian added this to the Unplanned milestone Mar 24, 2017

josharian added the help wanted label Mar 24, 2017

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

josharian mentioned this issue Mar 24, 2017

cmd/compile: internal compiler error: cannot inline function containing closure #19705

Closed

josharian assigned josharian and unassigned josharian Mar 26, 2017

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

cmd/compile: remove haslabelgoto

44083a0

As of CL 39998, it is no longer necessary. Fixes golang#19699 Change-Id: Ie1c49c8468073c6ddeb96c03668705cf81d40c98

gopherbot closed this as completed in 7189a02 Apr 20, 2017

golang locked and limited conversation to collaborators Apr 20, 2018

gopherbot added the FrozenDueToAge label Apr 20, 2018

rsc unassigned josharian Jun 23, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017 •

edited

josharian commented Mar 24, 2017

josharian commented Mar 24, 2017

dr2chase commented Mar 24, 2017 •

edited

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

dr2chase commented Mar 24, 2017

ALTree commented Mar 26, 2017

josharian commented Mar 28, 2017

gopherbot commented Mar 28, 2017

ALTree commented Mar 28, 2017

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

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

Comments

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017 • edited

josharian commented Mar 24, 2017

josharian commented Mar 24, 2017

dr2chase commented Mar 24, 2017 • edited

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

mdempsky commented Mar 24, 2017

josharian commented Mar 24, 2017

dr2chase commented Mar 24, 2017

ALTree commented Mar 26, 2017

josharian commented Mar 28, 2017

gopherbot commented Mar 28, 2017

ALTree commented Mar 28, 2017

mdempsky commented Mar 24, 2017 •

edited

dr2chase commented Mar 24, 2017 •

edited