From ffbf209a7c733ef519abbe9a5c47a8b1c73814af Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Mon, 20 Jul 2015 13:00:28 -0700 Subject: [dev.ssa] test: gofmt {goto,label,label1}.go Change-Id: I971d0c93632e39aad4e2ba1862f085df820baf8b Reviewed-on: https://go-review.googlesource.com/12431 Reviewed-by: Brad Fitzpatrick --- test/goto.go | 72 +++++++++++++++++++++++++++++----------------------------- test/label.go | 3 +-- test/label1.go | 1 - 3 files changed, 37 insertions(+), 39 deletions(-) (limited to 'test') diff --git a/test/goto.go b/test/goto.go index ca477b3d0c..2daaa950af 100644 --- a/test/goto.go +++ b/test/goto.go @@ -40,7 +40,7 @@ L: // goto across declaration not okay func _() { goto L // ERROR "goto L jumps over declaration of x at LINE+1|goto jumps over declaration" - x := 1 // GCCGO_ERROR "defined here" + x := 1 // GCCGO_ERROR "defined here" _ = x L: } @@ -62,7 +62,7 @@ func _() { x := 1 _ = x } - x := 1 // GCCGO_ERROR "defined here" + x := 1 // GCCGO_ERROR "defined here" _ = x L: } @@ -78,7 +78,7 @@ L: // error shows first offending variable func _() { goto L // ERROR "goto L jumps over declaration of x at LINE+1|goto jumps over declaration" - x := 1 // GCCGO_ERROR "defined here" + x := 1 // GCCGO_ERROR "defined here" _ = x y := 1 _ = y @@ -88,7 +88,7 @@ L: // goto not okay even if code path is dead func _() { goto L // ERROR "goto L jumps over declaration of x at LINE+1|goto jumps over declaration" - x := 1 // GCCGO_ERROR "defined here" + x := 1 // GCCGO_ERROR "defined here" _ = x y := 1 _ = y @@ -115,14 +115,14 @@ L: // goto into inner block not okay func _() { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - { // GCCGO_ERROR "block starts here" + { // GCCGO_ERROR "block starts here" L: } } // goto backward into inner block still not okay func _() { - { // GCCGO_ERROR "block starts here" + { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" @@ -133,7 +133,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" { { - { // GCCGO_ERROR "block starts here" + { // GCCGO_ERROR "block starts here" L: } } @@ -145,7 +145,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+3|goto jumps into block" x := 1 _ = x - { // GCCGO_ERROR "block starts here" + { // GCCGO_ERROR "block starts here" L: } } @@ -179,15 +179,15 @@ L: } func _() { - goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - if true { // GCCGO_ERROR "block starts here" + goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" + if true { // GCCGO_ERROR "block starts here" L: } } func _() { - goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - if true { // GCCGO_ERROR "block starts here" + goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" + if true { // GCCGO_ERROR "block starts here" L: } else { } @@ -196,13 +196,13 @@ func _() { func _() { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" if true { - } else { // GCCGO_ERROR "block starts here" + } else { // GCCGO_ERROR "block starts here" L: } } func _() { - if false { // GCCGO_ERROR "block starts here" + if false { // GCCGO_ERROR "block starts here" L: } else { goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" @@ -212,7 +212,7 @@ func _() { func _() { if true { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - } else { // GCCGO_ERROR "block starts here" + } else { // GCCGO_ERROR "block starts here" L: } } @@ -220,7 +220,7 @@ func _() { func _() { if true { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - } else if false { // GCCGO_ERROR "block starts here" + } else if false { // GCCGO_ERROR "block starts here" L: } } @@ -228,7 +228,7 @@ func _() { func _() { if true { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" - } else if false { // GCCGO_ERROR "block starts here" + } else if false { // GCCGO_ERROR "block starts here" L: } else { } @@ -243,7 +243,7 @@ func _() { if true { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" } else if false { - } else { // GCCGO_ERROR "block starts here" + } else { // GCCGO_ERROR "block starts here" L: } } @@ -287,14 +287,14 @@ func _() { } func _() { - for { // GCCGO_ERROR "block starts here" + for { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for { // GCCGO_ERROR "block starts here" + for { // GCCGO_ERROR "block starts here" goto L L1: } @@ -303,42 +303,42 @@ L: } func _() { - for i < n { // GCCGO_ERROR "block starts here" + for i < n { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for i = 0; i < n; i++ { // GCCGO_ERROR "block starts here" + for i = 0; i < n; i++ { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for i = range x { // GCCGO_ERROR "block starts here" + for i = range x { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for i = range c { // GCCGO_ERROR "block starts here" + for i = range c { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for i = range m { // GCCGO_ERROR "block starts here" + for i = range m { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" } func _() { - for i = range s { // GCCGO_ERROR "block starts here" + for i = range s { // GCCGO_ERROR "block starts here" L: } goto L // ERROR "goto L jumps into block starting at LINE-3|goto jumps into block" @@ -398,7 +398,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" switch i { case 0: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } @@ -406,7 +406,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" switch i { case 0: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" ; default: } @@ -417,7 +417,7 @@ func _() { switch i { case 0: default: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } @@ -426,14 +426,14 @@ func _() { default: goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" case 0: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } func _() { switch i { case 0: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" ; default: goto L // ERROR "goto L jumps into block starting at LINE-4|goto jumps into block" @@ -495,7 +495,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+2|goto jumps into block" select { case c <- 1: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } @@ -503,7 +503,7 @@ func _() { goto L // ERROR "goto L jumps into block starting at LINE+2|goto jumps into block" select { case c <- 1: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" ; default: } @@ -514,7 +514,7 @@ func _() { select { case <-c: default: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } @@ -523,14 +523,14 @@ func _() { default: goto L // ERROR "goto L jumps into block starting at LINE+1|goto jumps into block" case <-c: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" } } func _() { select { case <-c: - L: // GCCGO_ERROR "block starts here" + L: // GCCGO_ERROR "block starts here" ; default: goto L // ERROR "goto L jumps into block starting at LINE-4|goto jumps into block" diff --git a/test/label.go b/test/label.go index b30c27ec44..a1811c2d68 100644 --- a/test/label.go +++ b/test/label.go @@ -17,8 +17,7 @@ L1: // ERROR "label .*L1.* defined and not used" for { } L2: // ERROR "label .*L2.* defined and not used" - select { - } + select {} L3: // ERROR "label .*L3.* defined and not used" switch { } diff --git a/test/label1.go b/test/label1.go index f923a18820..bc8fea6f6a 100644 --- a/test/label1.go +++ b/test/label1.go @@ -4,7 +4,6 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. - // Verify that erroneous labels are caught by the compiler. // This set is caught by pass 2. That's why this file is label1.go. // Does not compile. -- cgit v1.3 From 61aa0953e542eb047f22905f84c7d627a35b8607 Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Mon, 20 Jul 2015 15:39:14 -0700 Subject: [dev.ssa] cmd/compile: implement control flow handling Add label and goto checks and improve test coverage. Implement OSWITCH and OSELECT. Implement OBREAK and OCONTINUE. Allow generation of code in dead blocks. Change-Id: Ibebb7c98b4b2344f46d38db7c9dce058c56beaac Reviewed-on: https://go-review.googlesource.com/12445 Reviewed-by: Keith Randall --- src/cmd/compile/internal/gc/gen.go | 2 + src/cmd/compile/internal/gc/ssa.go | 316 ++++++++++++++++++++-- src/cmd/compile/internal/gc/ssa_test.go | 17 +- src/cmd/compile/internal/gc/testdata/break_ssa.go | 255 +++++++++++++++++ src/cmd/compile/internal/ssa/compile.go | 1 + test/label.go | 4 + test/label1.go | 31 ++- 7 files changed, 590 insertions(+), 36 deletions(-) create mode 100644 src/cmd/compile/internal/gc/testdata/break_ssa.go (limited to 'test') diff --git a/src/cmd/compile/internal/gc/gen.go b/src/cmd/compile/internal/gc/gen.go index 764895f15d..6390818e16 100644 --- a/src/cmd/compile/internal/gc/gen.go +++ b/src/cmd/compile/internal/gc/gen.go @@ -141,6 +141,8 @@ func newlab(n *Node) *Label { return lab } +// There is a copy of checkgoto in the new SSA backend. +// Please keep them in sync. func checkgoto(from *Node, to *Node) { if from.Sym == to.Sym { return diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index a77e788a1c..96756b11d0 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -62,7 +62,8 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // Allocate starting values s.vars = map[*Node]*ssa.Value{} - s.labels = map[string]*ssa.Block{} + s.labels = map[string]*ssaLabel{} + s.labeledNodes = map[*Node]*ssaLabel{} s.startmem = s.entryNewValue0(ssa.OpArg, ssa.TypeMem) s.sp = s.entryNewValue0(ssa.OpSP, s.config.Uintptr) // TODO: use generic pointer type (unsafe.Pointer?) instead s.sb = s.entryNewValue0(ssa.OpSB, s.config.Uintptr) @@ -105,6 +106,31 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { s.exit.Control = s.mem() s.endBlock() + // Check that we used all labels + for name, lab := range s.labels { + if !lab.used() && !lab.reported { + yyerrorl(int(lab.defNode.Lineno), "label %v defined and not used", name) + lab.reported = true + } + if lab.used() && !lab.defined() && !lab.reported { + yyerrorl(int(lab.useNode.Lineno), "label %v not defined", name) + lab.reported = true + } + } + + // Check any forward gotos. Non-forward gotos have already been checked. + for _, n := range s.fwdGotos { + lab := s.labels[n.Left.Sym.Name] + // If the label is undefined, we have already have printed an error. + if lab.defined() { + s.checkgoto(n, lab.defNode) + } + } + + if nerrors > 0 { + return nil, false + } + // Link up variable uses to variable definitions s.linkForwardReferences() @@ -132,8 +158,16 @@ type state struct { // exit block that "return" jumps to (and panics jump to) exit *ssa.Block - // the target block for each label in f - labels map[string]*ssa.Block + // labels and labeled control flow nodes (OFOR, OSWITCH, OSELECT) in f + labels map[string]*ssaLabel + labeledNodes map[*Node]*ssaLabel + + // gotos that jump forward; required for deferred checkgoto calls + fwdGotos []*Node + + // unlabeled break and continue statement tracking + breakTo *ssa.Block // current target for plain break statement + continueTo *ssa.Block // current target for plain continue statement // current location where we're interpreting the AST curBlock *ssa.Block @@ -157,6 +191,34 @@ type state struct { line []int32 } +type ssaLabel struct { + target *ssa.Block // block identified by this label + breakTarget *ssa.Block // block to break to in control flow node identified by this label + continueTarget *ssa.Block // block to continue to in control flow node identified by this label + defNode *Node // label definition Node (OLABEL) + // Label use Node (OGOTO, OBREAK, OCONTINUE). + // Used only for error detection and reporting. + // There might be multiple uses, but we only need to track one. + useNode *Node + reported bool // reported indicates whether an error has already been reported for this label +} + +// defined reports whether the label has a definition (OLABEL node). +func (l *ssaLabel) defined() bool { return l.defNode != nil } + +// used reports whether the label has a use (OGOTO, OBREAK, or OCONTINUE node). +func (l *ssaLabel) used() bool { return l.useNode != nil } + +// label returns the label associated with sym, creating it if necessary. +func (s *state) label(sym *Sym) *ssaLabel { + lab := s.labels[sym.Name] + if lab == nil { + lab = new(ssaLabel) + s.labels[sym.Name] = lab + } + return lab +} + func (s *state) Logf(msg string, args ...interface{}) { s.config.Logf(msg, args...) } func (s *state) Fatalf(msg string, args ...interface{}) { s.config.Fatalf(msg, args...) } func (s *state) Unimplementedf(msg string, args ...interface{}) { s.config.Unimplementedf(msg, args...) } @@ -206,6 +268,10 @@ func (s *state) peekLine() int32 { return s.line[len(s.line)-1] } +func (s *state) Error(msg string, args ...interface{}) { + yyerrorl(int(s.peekLine()), msg, args...) +} + // newValue0 adds a new value with no arguments to the current block. func (s *state) newValue0(op ssa.Op, t ssa.Type) *ssa.Value { return s.curBlock.NewValue0(s.peekLine(), op, t) @@ -293,6 +359,16 @@ func (s *state) stmt(n *Node) { s.pushLine(n.Lineno) defer s.popLine() + // If s.curBlock is nil, then we're about to generate dead code. + // We can't just short-circuit here, though, + // because we check labels and gotos as part of SSA generation. + // Provide a block for the dead code so that we don't have + // to add special cases everywhere else. + if s.curBlock == nil { + dead := s.f.NewBlock(ssa.BlockPlain) + s.startBlock(dead) + } + s.stmtList(n.Ninit) switch n.Op { @@ -325,32 +401,61 @@ func (s *state) stmt(n *Node) { } s.assign(OAS, n.Left.Name.Heapaddr, palloc) - case OLABEL, OGOTO: - if n.Op == OLABEL && isblanksym(n.Left.Sym) { + case OLABEL: + sym := n.Left.Sym + + if isblanksym(sym) { // Empty identifier is valid but useless. // See issues 11589, 11593. return } - // get block at label, or make one - t := s.labels[n.Left.Sym.Name] - if t == nil { - t = s.f.NewBlock(ssa.BlockPlain) - s.labels[n.Left.Sym.Name] = t + + lab := s.label(sym) + + // Associate label with its control flow node, if any + if ctl := n.Name.Defn; ctl != nil { + switch ctl.Op { + case OFOR, OSWITCH, OSELECT: + s.labeledNodes[ctl] = lab + } } - // go to that label (we pretend "label:" is preceded by "goto label") - if b := s.endBlock(); b != nil { - addEdge(b, t) + + if !lab.defined() { + lab.defNode = n + } else { + s.Error("label %v already defined at %v", sym, Ctxt.Line(int(lab.defNode.Lineno))) + lab.reported = true + } + // The label might already have a target block via a goto. + if lab.target == nil { + lab.target = s.f.NewBlock(ssa.BlockPlain) } - if n.Op == OLABEL { - // next we work on the label's target block - s.startBlock(t) + // go to that label (we pretend "label:" is preceded by "goto label") + b := s.endBlock() + addEdge(b, lab.target) + s.startBlock(lab.target) + + case OGOTO: + sym := n.Left.Sym + + lab := s.label(sym) + if lab.target == nil { + lab.target = s.f.NewBlock(ssa.BlockPlain) + } + if !lab.used() { + lab.useNode = n } - if n.Op == OGOTO && s.curBlock == nil { - s.Unimplementedf("goto at start of function; see test/goto.go") - panic("stop compiling here, on pain of infinite loops") + + if lab.defined() { + s.checkgoto(n, lab.defNode) + } else { + s.fwdGotos = append(s.fwdGotos, n) } + b := s.endBlock() + addEdge(b, lab.target) + case OAS, OASWB: s.assign(n.Op, n.Left, n.Right) @@ -396,6 +501,58 @@ func (s *state) stmt(n *Node) { b := s.endBlock() addEdge(b, s.exit) + case OCONTINUE, OBREAK: + var op string + var to *ssa.Block + switch n.Op { + case OCONTINUE: + op = "continue" + to = s.continueTo + case OBREAK: + op = "break" + to = s.breakTo + } + if n.Left == nil { + // plain break/continue + if to == nil { + s.Error("%s is not in a loop", op) + return + } + // nothing to do; "to" is already the correct target + } else { + // labeled break/continue; look up the target + sym := n.Left.Sym + lab := s.label(sym) + if !lab.used() { + lab.useNode = n.Left + } + if !lab.defined() { + s.Error("%s label not defined: %v", op, sym) + lab.reported = true + return + } + switch n.Op { + case OCONTINUE: + to = lab.continueTarget + case OBREAK: + to = lab.breakTarget + } + if to == nil { + // Valid label but not usable with a break/continue here, e.g.: + // for { + // continue abc + // } + // abc: + // for {} + s.Error("invalid %s label %v", op, sym) + lab.reported = true + return + } + } + + b := s.endBlock() + addEdge(b, to) + case OFOR: // OFOR: for Ninit; Left; Right { Nbody } bCond := s.f.NewBlock(ssa.BlockPlain) @@ -422,9 +579,31 @@ func (s *state) stmt(n *Node) { addEdge(b, bBody) addEdge(b, bEnd) + // set up for continue/break in body + prevContinue := s.continueTo + prevBreak := s.breakTo + s.continueTo = bIncr + s.breakTo = bEnd + lab := s.labeledNodes[n] + if lab != nil { + // labeled for loop + lab.continueTarget = bIncr + lab.breakTarget = bEnd + } + // generate body s.startBlock(bBody) s.stmtList(n.Nbody) + + // tear down continue/break + s.continueTo = prevContinue + s.breakTo = prevBreak + if lab != nil { + lab.continueTarget = nil + lab.breakTarget = nil + } + + // done with body, goto incr if b := s.endBlock(); b != nil { addEdge(b, bIncr) } @@ -439,6 +618,32 @@ func (s *state) stmt(n *Node) { } s.startBlock(bEnd) + case OSWITCH, OSELECT: + // These have been mostly rewritten by the front end into their Nbody fields. + // Our main task is to correctly hook up any break statements. + bEnd := s.f.NewBlock(ssa.BlockPlain) + + prevBreak := s.breakTo + s.breakTo = bEnd + lab := s.labeledNodes[n] + if lab != nil { + // labeled + lab.breakTarget = bEnd + } + + // generate body code + s.stmtList(n.Nbody) + + s.breakTo = prevBreak + if lab != nil { + lab.breakTarget = nil + } + + if b := s.endBlock(); b != nil { + addEdge(b, bEnd) + } + s.startBlock(bEnd) + case OVARKILL: // TODO(khr): ??? anything to do here? Only for addrtaken variables? // Maybe just link it in the store chain? @@ -924,14 +1129,66 @@ func (s *state) boundsCheck(idx, len *ssa.Value) { s.startBlock(bNext) } +// checkgoto checks that a goto from from to to does not +// jump into a block or jump over variable declarations. +// It is a copy of checkgoto in the pre-SSA backend, +// modified only for line number handling. +// TODO: document how this works and why it is designed the way it is. +func (s *state) checkgoto(from *Node, to *Node) { + if from.Sym == to.Sym { + return + } + + nf := 0 + for fs := from.Sym; fs != nil; fs = fs.Link { + nf++ + } + nt := 0 + for fs := to.Sym; fs != nil; fs = fs.Link { + nt++ + } + fs := from.Sym + for ; nf > nt; nf-- { + fs = fs.Link + } + if fs != to.Sym { + // decide what to complain about. + // prefer to complain about 'into block' over declarations, + // so scan backward to find most recent block or else dcl. + var block *Sym + + var dcl *Sym + ts := to.Sym + for ; nt > nf; nt-- { + if ts.Pkg == nil { + block = ts + } else { + dcl = ts + } + ts = ts.Link + } + + for ts != fs { + if ts.Pkg == nil { + block = ts + } else { + dcl = ts + } + ts = ts.Link + fs = fs.Link + } + + lno := int(from.Left.Lineno) + if block != nil { + yyerrorl(lno, "goto %v jumps into block starting at %v", from.Left.Sym, Ctxt.Line(int(block.Lastlineno))) + } else { + yyerrorl(lno, "goto %v jumps over declaration of %v at %v", from.Left.Sym, dcl, Ctxt.Line(int(dcl.Lastlineno))) + } + } +} + // variable returns the value of a variable at the current location. func (s *state) variable(name *Node, t ssa.Type) *ssa.Value { - if s.curBlock == nil { - // Unimplemented instead of Fatal because fixedbugs/bug303.go - // demonstrates a case in which this appears to happen legitimately. - // TODO: decide on the correct behavior here. - s.Unimplementedf("nil curblock adding variable %v (%v)", name, t) - } v := s.vars[name] if v == nil { // TODO: get type? Take Sym as arg? @@ -989,8 +1246,13 @@ func (s *state) lookupVarIncoming(b *ssa.Block, t ssa.Type, name *Node) *ssa.Val vals = append(vals, s.lookupVarOutgoing(p, t, name)) } if len(vals) == 0 { - s.Unimplementedf("TODO: Handle fixedbugs/bug076.go") - return nil + // This block is dead; we have no predecessors and we're not the entry block. + // It doesn't matter what we use here as long as it is well-formed, + // so use the default/zero value. + if name == &memvar { + return s.startmem + } + return s.zeroVal(name.Type) } v0 := vals[0] for i := 1; i < len(vals); i++ { diff --git a/src/cmd/compile/internal/gc/ssa_test.go b/src/cmd/compile/internal/gc/ssa_test.go index fbbba6d9cb..4354d020f2 100644 --- a/src/cmd/compile/internal/gc/ssa_test.go +++ b/src/cmd/compile/internal/gc/ssa_test.go @@ -8,23 +8,24 @@ import ( "bytes" "internal/testenv" "os/exec" + "path/filepath" "runtime" "strings" "testing" ) -// Tests OANDAND and OOROR expressions and short circuiting. -// TODO: move these tests elsewhere? perhaps teach test/run.go how to run them -// with a new action verb. -func TestShortCircuit(t *testing.T) { +// TODO: move all these tests elsewhere? +// Perhaps teach test/run.go how to run them with a new action verb. +func runTest(t *testing.T, filename string) { if runtime.GOARCH != "amd64" { t.Skipf("skipping SSA tests on %s for now", runtime.GOARCH) } testenv.MustHaveGoBuild(t) var stdout, stderr bytes.Buffer - cmd := exec.Command("go", "run", "testdata/short_ssa.go") + cmd := exec.Command("go", "run", filepath.Join("testdata", filename)) cmd.Stdout = &stdout cmd.Stderr = &stderr + // TODO: set GOGC=off until we have stackmaps if err := cmd.Run(); err != nil { t.Fatalf("Failed: %v:\nOut: %s\nStderr: %s\n", err, &stdout, &stderr) } @@ -35,3 +36,9 @@ func TestShortCircuit(t *testing.T) { t.Errorf("Unimplemented message found in stderr:\n%s", s) } } + +// TestShortCircuit tests OANDAND and OOROR expressions and short circuiting. +func TestShortCircuit(t *testing.T) { runTest(t, "short_ssa.go") } + +// TestBreakContinue tests that continue and break statements do what they say. +func TestBreakContinue(t *testing.T) { runTest(t, "break_ssa.go") } diff --git a/src/cmd/compile/internal/gc/testdata/break_ssa.go b/src/cmd/compile/internal/gc/testdata/break_ssa.go new file mode 100644 index 0000000000..855ef70049 --- /dev/null +++ b/src/cmd/compile/internal/gc/testdata/break_ssa.go @@ -0,0 +1,255 @@ +// run + +// Copyright 2015 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Tests continue and break. + +package main + +func continuePlain_ssa() int { + var n int + for i := 0; i < 10; i++ { + if i == 6 { + continue + } + n = i + } + return n +} + +func continueLabeled_ssa() int { + var n int +Next: + for i := 0; i < 10; i++ { + if i == 6 { + continue Next + } + n = i + } + return n +} + +func continuePlainInner_ssa() int { + var n int + for j := 0; j < 30; j += 10 { + for i := 0; i < 10; i++ { + if i == 6 { + continue + } + n = i + } + n += j + } + return n +} + +func continueLabeledInner_ssa() int { + var n int + for j := 0; j < 30; j += 10 { + Next: + for i := 0; i < 10; i++ { + if i == 6 { + continue Next + } + n = i + } + n += j + } + return n +} + +func continueLabeledOuter_ssa() int { + var n int +Next: + for j := 0; j < 30; j += 10 { + for i := 0; i < 10; i++ { + if i == 6 { + continue Next + } + n = i + } + n += j + } + return n +} + +func breakPlain_ssa() int { + var n int + for i := 0; i < 10; i++ { + if i == 6 { + break + } + n = i + } + return n +} + +func breakLabeled_ssa() int { + var n int +Next: + for i := 0; i < 10; i++ { + if i == 6 { + break Next + } + n = i + } + return n +} + +func breakPlainInner_ssa() int { + var n int + for j := 0; j < 30; j += 10 { + for i := 0; i < 10; i++ { + if i == 6 { + break + } + n = i + } + n += j + } + return n +} + +func breakLabeledInner_ssa() int { + var n int + for j := 0; j < 30; j += 10 { + Next: + for i := 0; i < 10; i++ { + if i == 6 { + break Next + } + n = i + } + n += j + } + return n +} + +func breakLabeledOuter_ssa() int { + var n int +Next: + for j := 0; j < 30; j += 10 { + for i := 0; i < 10; i++ { + if i == 6 { + break Next + } + n = i + } + n += j + } + return n +} + +var g, h int // globals to ensure optimizations don't collapse our switch statements + +func switchPlain_ssa() int { + var n int + switch g { + case 0: + n = 1 + break + n = 2 + } + return n +} + +func switchLabeled_ssa() int { + var n int +Done: + switch g { + case 0: + n = 1 + break Done + n = 2 + } + return n +} + +func switchPlainInner_ssa() int { + var n int + switch g { + case 0: + n = 1 + switch h { + case 0: + n += 10 + break + } + n = 2 + } + return n +} + +func switchLabeledInner_ssa() int { + var n int + switch g { + case 0: + n = 1 + Done: + switch h { + case 0: + n += 10 + break Done + } + n = 2 + } + return n +} + +func switchLabeledOuter_ssa() int { + var n int +Done: + switch g { + case 0: + n = 1 + switch h { + case 0: + n += 10 + break Done + } + n = 2 + } + return n +} + +func main() { + tests := [...]struct { + name string + fn func() int + want int + }{ + {"continuePlain_ssa", continuePlain_ssa, 9}, + {"continueLabeled_ssa", continueLabeled_ssa, 9}, + {"continuePlainInner_ssa", continuePlainInner_ssa, 29}, + {"continueLabeledInner_ssa", continueLabeledInner_ssa, 29}, + {"continueLabeledOuter_ssa", continueLabeledOuter_ssa, 5}, + + {"breakPlain_ssa", breakPlain_ssa, 5}, + {"breakLabeled_ssa", breakLabeled_ssa, 5}, + {"breakPlainInner_ssa", breakPlainInner_ssa, 25}, + {"breakLabeledInner_ssa", breakLabeledInner_ssa, 25}, + {"breakLabeledOuter_ssa", breakLabeledOuter_ssa, 5}, + + {"switchPlain_ssa", switchPlain_ssa, 1}, + {"switchLabeled_ssa", switchLabeled_ssa, 1}, + {"switchPlainInner_ssa", switchPlainInner_ssa, 2}, + {"switchLabeledInner_ssa", switchLabeledInner_ssa, 2}, + {"switchLabeledOuter_ssa", switchLabeledOuter_ssa, 11}, + + // no select tests; they're identical to switch + } + + var failed bool + for _, test := range tests { + if got := test.fn(); test.fn() != test.want { + print(test.name, "()=", got, ", want ", test.want, "\n") + failed = true + } + } + + if failed { + panic("failed") + } +} diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 4a6c2a9404..7a7b9926ed 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -50,6 +50,7 @@ type pass struct { var passes = [...]pass{ {"phielim", phielim}, {"copyelim", copyelim}, + {"early deadcode", deadcode}, // remove generated dead code to avoid doing pointless work during opt {"opt", opt}, {"opt deadcode", deadcode}, // remove any blocks orphaned during opt {"generic cse", cse}, diff --git a/test/label.go b/test/label.go index a1811c2d68..c3c0c27edd 100644 --- a/test/label.go +++ b/test/label.go @@ -58,4 +58,8 @@ L10: default: break L10 } + + goto L10 + + goto go2 // ERROR "label go2 not defined" } diff --git a/test/label1.go b/test/label1.go index bc8fea6f6a..937b5cb900 100644 --- a/test/label1.go +++ b/test/label1.go @@ -31,11 +31,17 @@ L2: break L2 } if x == 1 { - continue L2 // ERROR "invalid continue label .*L2" + continue L2 // ERROR "invalid continue label .*L2|continue is not in a loop" } goto L2 } + for { + if x == 1 { + continue L2 // ERROR "invalid continue label .*L2" + } + } + L3: switch { case x > 10: @@ -43,7 +49,7 @@ L3: break L3 } if x == 12 { - continue L3 // ERROR "invalid continue label .*L3" + continue L3 // ERROR "invalid continue label .*L3|continue is not in a loop" } goto L3 } @@ -54,7 +60,7 @@ L4: break L4 // ERROR "invalid break label .*L4" } if x == 14 { - continue L4 // ERROR "invalid continue label .*L4" + continue L4 // ERROR "invalid continue label .*L4|continue is not in a loop" } if x == 15 { goto L4 @@ -67,7 +73,7 @@ L5: break L5 // ERROR "invalid break label .*L5" } if x == 17 { - continue L5 // ERROR "invalid continue label .*L5" + continue L5 // ERROR "invalid continue label .*L5|continue is not in a loop" } if x == 18 { goto L5 @@ -84,4 +90,21 @@ L5: goto L1 } } + + continue // ERROR "continue is not in a loop" + for { + continue on // ERROR "continue label not defined: on" + } + + break // ERROR "break is not in a loop" + for { + break dance // ERROR "break label not defined: dance" + } + + for { + switch x { + case 1: + continue + } + } } -- cgit v1.3 From 186cf1b9ba1358344b8ce6f2fb4a62302b98ba90 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Fri, 28 Aug 2015 16:45:17 -0700 Subject: [dev.ssa] cmd/compile/internal/ssa: handle dead code a different way Instead of trying to delete dead code as soon as we find it, just mark it as dead using a PlainAndDead block kind. The deadcode pass will do the real removal. This way is somewhat more efficient because we don't need to mess with successor and predecessor lists of all the dead blocks. Fixes #12347 Change-Id: Ia42d6b5f9cdb3215a51737b3eb117c00bd439b13 Reviewed-on: https://go-review.googlesource.com/14033 Reviewed-by: Josh Bleecher Snyder --- src/cmd/compile/internal/ssa/check.go | 7 + src/cmd/compile/internal/ssa/deadcode.go | 186 +++++++++++++------------ src/cmd/compile/internal/ssa/gen/generic.rules | 6 +- src/cmd/compile/internal/ssa/gen/genericOps.go | 2 +- src/cmd/compile/internal/ssa/gen/rulegen.go | 5 +- src/cmd/compile/internal/ssa/nilcheck.go | 8 +- src/cmd/compile/internal/ssa/opGen.go | 2 + src/cmd/compile/internal/ssa/rewritegeneric.go | 49 +++---- test/fixedbugs/issue12347.go | 16 +++ 9 files changed, 154 insertions(+), 127 deletions(-) create mode 100644 test/fixedbugs/issue12347.go (limited to 'test') diff --git a/src/cmd/compile/internal/ssa/check.go b/src/cmd/compile/internal/ssa/check.go index ad9222f3e2..0c2bc4c7f1 100644 --- a/src/cmd/compile/internal/ssa/check.go +++ b/src/cmd/compile/internal/ssa/check.go @@ -99,6 +99,13 @@ func checkFunc(f *Func) { if !b.Control.Type.IsMemory() { f.Fatalf("call block %s has non-memory control value %s", b, b.Control.LongString()) } + case BlockFirst: + if len(b.Succs) != 2 { + f.Fatalf("plain/dead block %s len(Succs)==%d, want 2", b, len(b.Succs)) + } + if b.Control != nil { + f.Fatalf("plain/dead block %s has a control value", b) + } } if len(b.Succs) > 2 && b.Likely != BranchUnknown { f.Fatalf("likeliness prediction %d for block %s with %d successors: %s", b.Likely, b, len(b.Succs)) diff --git a/src/cmd/compile/internal/ssa/deadcode.go b/src/cmd/compile/internal/ssa/deadcode.go index 5ff082baff..be25eddb47 100644 --- a/src/cmd/compile/internal/ssa/deadcode.go +++ b/src/cmd/compile/internal/ssa/deadcode.go @@ -29,7 +29,11 @@ func findlive(f *Func) (reachable []bool, live []bool) { b := p[len(p)-1] p = p[:len(p)-1] // Mark successors as reachable - for _, c := range b.Succs { + s := b.Succs + if b.Kind == BlockFirst { + s = s[:1] + } + for _, c := range s { if !reachable[c.ID] { reachable[c.ID] = true p = append(p, c) // push @@ -103,6 +107,37 @@ func deadcode(f *Func) { b.Values = b.Values[:i] } + // Get rid of edges from dead to live code. + for _, b := range f.Blocks { + if reachable[b.ID] { + continue + } + for _, c := range b.Succs { + if reachable[c.ID] { + c.removePred(b) + } + } + } + + // Get rid of dead edges from live code. + for _, b := range f.Blocks { + if !reachable[b.ID] { + continue + } + if b.Kind != BlockFirst { + continue + } + c := b.Succs[1] + b.Succs[1] = nil + b.Succs = b.Succs[:1] + b.Kind = BlockPlain + + if reachable[c.ID] { + // Note: c must be reachable through some other edge. + c.removePred(b) + } + } + // Remove unreachable blocks. Return dead block ids to allocator. i := 0 for _, b := range f.Blocks { @@ -113,11 +148,10 @@ func deadcode(f *Func) { if len(b.Values) > 0 { b.Fatalf("live values in unreachable block %v: %v", b, b.Values) } - s := b.Succs + b.Preds = nil b.Succs = nil - for _, c := range s { - f.removePredecessor(b, c) - } + b.Control = nil + b.Kind = BlockDead f.bid.put(b.ID) } } @@ -132,94 +166,68 @@ func deadcode(f *Func) { // TODO: save dead Values and Blocks for reuse? Or should we just let GC handle it? } -// There was an edge b->c. c has been removed from b's successors. -// Fix up c to handle that fact. -func (f *Func) removePredecessor(b, c *Block) { - work := [][2]*Block{{b, c}} - - for len(work) > 0 { - b, c := work[0][0], work[0][1] - work = work[1:] - - // Find index of b in c's predecessor list - // TODO: This could conceivably cause O(n^2) work. Imagine a very - // wide phi in (for example) the return block. If we determine that - // lots of panics won't happen, we remove each edge at a cost of O(n) each. - var i int - found := false - for j, p := range c.Preds { - if p == b { - i = j - found = true - break - } - } - if !found { - f.Fatalf("can't find predecessor %v of %v\n", b, c) +// removePred removes the predecessor p from b's predecessor list. +func (b *Block) removePred(p *Block) { + var i int + found := false + for j, q := range b.Preds { + if q == p { + i = j + found = true + break } + } + // TODO: the above loop could make the deadcode pass take quadratic time + if !found { + b.Fatalf("can't find predecessor %v of %v\n", p, b) + } - n := len(c.Preds) - 1 - c.Preds[i] = c.Preds[n] - c.Preds[n] = nil // aid GC - c.Preds = c.Preds[:n] + n := len(b.Preds) - 1 + b.Preds[i] = b.Preds[n] + b.Preds[n] = nil // aid GC + b.Preds = b.Preds[:n] - // rewrite phi ops to match the new predecessor list - for _, v := range c.Values { - if v.Op != OpPhi { - continue - } - v.Args[i] = v.Args[n] - v.Args[n] = nil // aid GC - v.Args = v.Args[:n] - if n == 1 { - v.Op = OpCopy - // Note: this is trickier than it looks. Replacing - // a Phi with a Copy can in general cause problems because - // Phi and Copy don't have exactly the same semantics. - // Phi arguments always come from a predecessor block, - // whereas copies don't. This matters in loops like: - // 1: x = (Phi y) - // y = (Add x 1) - // goto 1 - // If we replace Phi->Copy, we get - // 1: x = (Copy y) - // y = (Add x 1) - // goto 1 - // (Phi y) refers to the *previous* value of y, whereas - // (Copy y) refers to the *current* value of y. - // The modified code has a cycle and the scheduler - // will barf on it. - // - // Fortunately, this situation can only happen for dead - // code loops. So although the value graph is transiently - // bad, we'll throw away the bad part by the end of - // the next deadcode phase. - // Proof: If we have a potential bad cycle, we have a - // situation like this: - // x = (Phi z) - // y = (op1 x ...) - // z = (op2 y ...) - // Where opX are not Phi ops. But such a situation - // implies a cycle in the dominator graph. In the - // example, x.Block dominates y.Block, y.Block dominates - // z.Block, and z.Block dominates x.Block (treating - // "dominates" as reflexive). Cycles in the dominator - // graph can only happen in an unreachable cycle. - } + // rewrite phi ops to match the new predecessor list + for _, v := range b.Values { + if v.Op != OpPhi { + continue } - if n == 0 { - // c is now dead--recycle its values - for _, v := range c.Values { - f.vid.put(v.ID) - } - c.Values = nil - // Also kill any successors of c now, to spare later processing. - for _, succ := range c.Succs { - work = append(work, [2]*Block{c, succ}) - } - c.Succs = nil - c.Kind = BlockDead - c.Control = nil + v.Args[i] = v.Args[n] + v.Args[n] = nil // aid GC + v.Args = v.Args[:n] + if n == 1 { + v.Op = OpCopy + // Note: this is trickier than it looks. Replacing + // a Phi with a Copy can in general cause problems because + // Phi and Copy don't have exactly the same semantics. + // Phi arguments always come from a predecessor block, + // whereas copies don't. This matters in loops like: + // 1: x = (Phi y) + // y = (Add x 1) + // goto 1 + // If we replace Phi->Copy, we get + // 1: x = (Copy y) + // y = (Add x 1) + // goto 1 + // (Phi y) refers to the *previous* value of y, whereas + // (Copy y) refers to the *current* value of y. + // The modified code has a cycle and the scheduler + // will barf on it. + // + // Fortunately, this situation can only happen for dead + // code loops. We know the code we're working with is + // not dead, so we're ok. + // Proof: If we have a potential bad cycle, we have a + // situation like this: + // x = (Phi z) + // y = (op1 x ...) + // z = (op2 y ...) + // Where opX are not Phi ops. But such a situation + // implies a cycle in the dominator graph. In the + // example, x.Block dominates y.Block, y.Block dominates + // z.Block, and z.Block dominates x.Block (treating + // "dominates" as reflexive). Cycles in the dominator + // graph can only happen in an unreachable cycle. } } } diff --git a/src/cmd/compile/internal/ssa/gen/generic.rules b/src/cmd/compile/internal/ssa/gen/generic.rules index f77b31501d..5d870ab1cc 100644 --- a/src/cmd/compile/internal/ssa/gen/generic.rules +++ b/src/cmd/compile/internal/ssa/gen/generic.rules @@ -174,8 +174,8 @@ // big-object moves (TODO: remove?) (Store [size] dst (Load src mem) mem) && size > config.IntSize -> (Move [size] dst src mem) -(If (IsNonNil (GetG)) yes no) -> (Plain nil yes) +(If (IsNonNil (GetG)) yes no) -> (First nil yes no) (If (Not cond) yes no) -> (If cond no yes) -(If (ConstBool {c}) yes no) && c.(bool) -> (Plain nil yes) -(If (ConstBool {c}) yes no) && !c.(bool) -> (Plain nil no) +(If (ConstBool {c}) yes no) && c.(bool) -> (First nil yes no) +(If (ConstBool {c}) yes no) && !c.(bool) -> (First nil no yes) diff --git a/src/cmd/compile/internal/ssa/gen/genericOps.go b/src/cmd/compile/internal/ssa/gen/genericOps.go index 62d34e74bb..2e3be0c0ce 100644 --- a/src/cmd/compile/internal/ssa/gen/genericOps.go +++ b/src/cmd/compile/internal/ssa/gen/genericOps.go @@ -373,7 +373,7 @@ var genericBlocks = []blockData{ {name: "Plain"}, // a single successor {name: "If"}, // 2 successors, if control goto Succs[0] else goto Succs[1] {name: "Call"}, // 2 successors, normal return and panic - // TODO(khr): BlockPanic for the built-in panic call, has 1 edge to the exit block + {name: "First"}, // 2 successors, always takes the first one (second is dead) } func init() { diff --git a/src/cmd/compile/internal/ssa/gen/rulegen.go b/src/cmd/compile/internal/ssa/gen/rulegen.go index 057e68601b..e5c61952f1 100644 --- a/src/cmd/compile/internal/ssa/gen/rulegen.go +++ b/src/cmd/compile/internal/ssa/gen/rulegen.go @@ -236,7 +236,7 @@ func genRules(arch arch) { t := split(result[1 : len(result)-1]) // remove parens, then split newsuccs := t[2:] - // Check if newsuccs is a subset of succs. + // Check if newsuccs is the same set as succs. m := map[string]bool{} for _, succ := range succs { if m[succ] { @@ -250,6 +250,9 @@ func genRules(arch arch) { } delete(m, succ) } + if len(m) != 0 { + log.Fatalf("unmatched successors %v in %s", m, rule) + } // Modify predecessor lists for no-longer-reachable blocks for succ := range m { diff --git a/src/cmd/compile/internal/ssa/nilcheck.go b/src/cmd/compile/internal/ssa/nilcheck.go index 4833ac472d..80b9e668d3 100644 --- a/src/cmd/compile/internal/ssa/nilcheck.go +++ b/src/cmd/compile/internal/ssa/nilcheck.go @@ -83,10 +83,8 @@ func nilcheckelim(f *Func) { // Eliminate the nil check. // The deadcode pass will remove vestigial values, // and the fuse pass will join this block with its successor. - node.block.Kind = BlockPlain + node.block.Kind = BlockFirst node.block.Control = nil - f.removePredecessor(node.block, node.block.Succs[1]) - node.block.Succs = node.block.Succs[:1] } else { // new nilcheck so add a ClearPtr node to clear the // ptr from the map of nil checks once we traverse @@ -173,10 +171,8 @@ func nilcheckelim0(f *Func) { // Eliminate the nil check. // The deadcode pass will remove vestigial values, // and the fuse pass will join this block with its successor. - b.Kind = BlockPlain + b.Kind = BlockFirst b.Control = nil - f.removePredecessor(b, b.Succs[1]) - b.Succs = b.Succs[:1] } } } diff --git a/src/cmd/compile/internal/ssa/opGen.go b/src/cmd/compile/internal/ssa/opGen.go index 15689b2a85..51a998e352 100644 --- a/src/cmd/compile/internal/ssa/opGen.go +++ b/src/cmd/compile/internal/ssa/opGen.go @@ -27,6 +27,7 @@ const ( BlockPlain BlockIf BlockCall + BlockFirst ) var blockString = [...]string{ @@ -52,6 +53,7 @@ var blockString = [...]string{ BlockPlain: "Plain", BlockIf: "If", BlockCall: "Call", + BlockFirst: "First", } func (k BlockKind) String() string { return blockString[k] } diff --git a/src/cmd/compile/internal/ssa/rewritegeneric.go b/src/cmd/compile/internal/ssa/rewritegeneric.go index b14ed9c21e..3ec41181cc 100644 --- a/src/cmd/compile/internal/ssa/rewritegeneric.go +++ b/src/cmd/compile/internal/ssa/rewritegeneric.go @@ -1574,27 +1574,25 @@ func rewriteBlockgeneric(b *Block) bool { case BlockIf: // match: (If (IsNonNil (GetG)) yes no) // cond: - // result: (Plain nil yes) + // result: (First nil yes no) { v := b.Control if v.Op != OpIsNonNil { - goto end0f2bb0111a86be0436b44210dbd83a90 + goto endafdc4e2525f9933ab0ae7effc3559597 } if v.Args[0].Op != OpGetG { - goto end0f2bb0111a86be0436b44210dbd83a90 + goto endafdc4e2525f9933ab0ae7effc3559597 } yes := b.Succs[0] no := b.Succs[1] - b.Func.removePredecessor(b, no) - b.Kind = BlockPlain + b.Kind = BlockFirst b.Control = nil - b.Succs = b.Succs[:1] b.Succs[0] = yes - b.Likely = BranchUnknown + b.Succs[1] = no return true } - goto end0f2bb0111a86be0436b44210dbd83a90 - end0f2bb0111a86be0436b44210dbd83a90: + goto endafdc4e2525f9933ab0ae7effc3559597 + endafdc4e2525f9933ab0ae7effc3559597: ; // match: (If (Not cond) yes no) // cond: @@ -1619,53 +1617,50 @@ func rewriteBlockgeneric(b *Block) bool { ; // match: (If (ConstBool {c}) yes no) // cond: c.(bool) - // result: (Plain nil yes) + // result: (First nil yes no) { v := b.Control if v.Op != OpConstBool { - goto end9ff0273f9b1657f4afc287562ca889f0 + goto end7a20763049489cdb40bb1eaa57d113d8 } c := v.Aux yes := b.Succs[0] no := b.Succs[1] if !(c.(bool)) { - goto end9ff0273f9b1657f4afc287562ca889f0 + goto end7a20763049489cdb40bb1eaa57d113d8 } - b.Func.removePredecessor(b, no) - b.Kind = BlockPlain + b.Kind = BlockFirst b.Control = nil - b.Succs = b.Succs[:1] b.Succs[0] = yes - b.Likely = BranchUnknown + b.Succs[1] = no return true } - goto end9ff0273f9b1657f4afc287562ca889f0 - end9ff0273f9b1657f4afc287562ca889f0: + goto end7a20763049489cdb40bb1eaa57d113d8 + end7a20763049489cdb40bb1eaa57d113d8: ; // match: (If (ConstBool {c}) yes no) // cond: !c.(bool) - // result: (Plain nil no) + // result: (First nil no yes) { v := b.Control if v.Op != OpConstBool { - goto endf401a4553c3c7c6bed64801da7bba076 + goto end3ecbf5b2cc1f0a08444d8ab1871a829c } c := v.Aux yes := b.Succs[0] no := b.Succs[1] if !(!c.(bool)) { - goto endf401a4553c3c7c6bed64801da7bba076 + goto end3ecbf5b2cc1f0a08444d8ab1871a829c } - b.Func.removePredecessor(b, yes) - b.Kind = BlockPlain + b.Kind = BlockFirst b.Control = nil - b.Succs = b.Succs[:1] b.Succs[0] = no - b.Likely = BranchUnknown + b.Succs[1] = yes + b.Likely *= -1 return true } - goto endf401a4553c3c7c6bed64801da7bba076 - endf401a4553c3c7c6bed64801da7bba076: + goto end3ecbf5b2cc1f0a08444d8ab1871a829c + end3ecbf5b2cc1f0a08444d8ab1871a829c: } return false } diff --git a/test/fixedbugs/issue12347.go b/test/fixedbugs/issue12347.go new file mode 100644 index 0000000000..4bbe09c3e8 --- /dev/null +++ b/test/fixedbugs/issue12347.go @@ -0,0 +1,16 @@ +// compile + +// Copyright 2015 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package p + +func f_ssa(x int, p *int) { + if false { + y := x + 5 + for { + *p = y + } + } +} -- cgit v1.3 From 1fc52b61f24c210514d4b14e9cc2f8e0aa3f3d9b Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Sun, 6 Sep 2015 19:39:07 -0700 Subject: [dev.ssa] test: use SSA codegen for runnable tests Now that the standard library tests are all passing, add the test directory tests. These contain a number of edge case tests that are of particular interest for compilers. Some kinds of tests are not well-suited for a new backend, such as errorcheck tests. To start, use SSA only for run and runoutput. There are three failing tests now. Just mark them as such for now, so that we can prevent regressions. This code will all be unwound once SSA codegen matures and becomes the default. Change-Id: Ic51e6d0cc1cd48ef1e2fe2c9a743bf0cce275200 Reviewed-on: https://go-review.googlesource.com/14344 Reviewed-by: Keith Randall Run-TryBot: Josh Bleecher Snyder TryBot-Result: Gobot Gobot --- test/run.go | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'test') diff --git a/test/run.go b/test/run.go index 6e1cde9390..f2618e027b 100644 --- a/test/run.go +++ b/test/run.go @@ -493,6 +493,7 @@ func (t *test) run() { } useTmp := true + ssaMain := false runcmd := func(args ...string) ([]byte, error) { cmd := exec.Command(args[0], args[1:]...) var buf bytes.Buffer @@ -501,6 +502,11 @@ func (t *test) run() { if useTmp { cmd.Dir = t.tempDir cmd.Env = envForDir(cmd.Dir) + } else { + cmd.Env = os.Environ() + } + if ssaMain && os.Getenv("GOARCH") == "amd64" { + cmd.Env = append(cmd.Env, "GOSSAPKG=main") } err := cmd.Run() if err != nil { @@ -631,6 +637,12 @@ func (t *test) run() { case "run": useTmp = false + switch t.gofile { + case "bug434.go", "recover.go", "recover1.go", "issue4066.go": + // TODO fix these failures + default: + ssaMain = true + } out, err := runcmd(append([]string{"go", "run", t.goFileName()}, args...)...) if err != nil { t.err = err @@ -656,6 +668,7 @@ func (t *test) run() { t.err = fmt.Errorf("write tempfile:%s", err) return } + ssaMain = true out, err = runcmd("go", "run", tfile) if err != nil { t.err = err -- cgit v1.3 From fd8c71be865386b5545571c9ff3b5c604809e133 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Tue, 8 Sep 2015 21:37:37 -0700 Subject: [dev.ssa] cmd/compile/internal/ssa: eval defer args before setting argsize and func Evaluating args can overwrite arg area, so we can't write argsize and func until args are evaluated. Fixes test/recover.go, test/recover1.go, and test/fixedbugs/issue4066.go Change-Id: I862e4934ccdb8661431bcc3e1e93817ea834ea3f Reviewed-on: https://go-review.googlesource.com/14405 Reviewed-by: David Chase --- src/cmd/compile/internal/gc/ssa.go | 8 ++++---- test/run.go | 4 ++-- 2 files changed, 6 insertions(+), 6 deletions(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index 9791967677..e3a71a9f3f 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -741,6 +741,10 @@ func (s *state) stmt(n *Node) { s.Unimplementedf("defer/go of %s", opnames[call.Op]) } + // Run all argument assignments. The arg slots have already + // been offset by 2*widthptr. + s.stmtList(call.List) + // Write argsize and closure (args to Newproc/Deferproc) argsize := s.constInt32(Types[TUINT32], int32(fn.Type.Argwid)) s.vars[&memvar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, 4, s.sp, argsize, s.mem()) @@ -748,10 +752,6 @@ func (s *state) stmt(n *Node) { addr := s.entryNewValue1I(ssa.OpOffPtr, Ptrto(Types[TUINTPTR]), int64(Widthptr), s.sp) s.vars[&memvar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, int64(Widthptr), addr, closure, s.mem()) - // Run all argument assignments. The arg slots have already - // been offset by 2*widthptr. - s.stmtList(call.List) - // Call deferproc or newproc bNext := s.f.NewBlock(ssa.BlockPlain) var op ssa.Op diff --git a/test/run.go b/test/run.go index f2618e027b..1f9b905ea3 100644 --- a/test/run.go +++ b/test/run.go @@ -638,8 +638,8 @@ func (t *test) run() { case "run": useTmp = false switch t.gofile { - case "bug434.go", "recover.go", "recover1.go", "issue4066.go": - // TODO fix these failures + case "bug434.go": + // TODO fix this failure default: ssaMain = true } -- cgit v1.3 From adba6c4fdf8c9d2078a88a016924e80fd23cb39c Mon Sep 17 00:00:00 2001 From: Todd Neal Date: Tue, 8 Sep 2015 07:50:25 -0400 Subject: [dev.ssa] cmd/compile/internal/ssa: treat -0.0 literal as 0.0 This matches existing behavior, see issue #2196 Change-Id: Ifa9359b7c821115389f337a57de355c5ec23be8f Reviewed-on: https://go-review.googlesource.com/14261 Reviewed-by: Keith Randall --- src/cmd/compile/internal/gc/ssa.go | 16 ++++++++++------ test/run.go | 8 +------- 2 files changed, 11 insertions(+), 13 deletions(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index 9d87f38ea1..386420f26b 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -1254,9 +1254,11 @@ func (s *state) expr(n *Node) *ssa.Value { f := n.Val().U.(*Mpflt) switch n.Type.Size() { case 4: - return s.constFloat32(n.Type, mpgetflt32(f)) + // -0.0 literals need to be treated as if they were 0.0, adding 0.0 here + // accomplishes this while not affecting other values. + return s.constFloat32(n.Type, mpgetflt32(f)+0.0) case 8: - return s.constFloat64(n.Type, mpgetflt(f)) + return s.constFloat64(n.Type, mpgetflt(f)+0.0) default: s.Fatalf("bad float size %d", n.Type.Size()) return nil @@ -1269,16 +1271,18 @@ func (s *state) expr(n *Node) *ssa.Value { case 8: { pt := Types[TFLOAT32] + // -0.0 literals need to be treated as if they were 0.0, adding 0.0 here + // accomplishes this while not affecting other values. return s.newValue2(ssa.OpComplexMake, n.Type, - s.constFloat32(pt, mpgetflt32(r)), - s.constFloat32(pt, mpgetflt32(i))) + s.constFloat32(pt, mpgetflt32(r)+0.0), + s.constFloat32(pt, mpgetflt32(i)+0.0)) } case 16: { pt := Types[TFLOAT64] return s.newValue2(ssa.OpComplexMake, n.Type, - s.constFloat64(pt, mpgetflt(r)), - s.constFloat64(pt, mpgetflt(i))) + s.constFloat64(pt, mpgetflt(r)+0.0), + s.constFloat64(pt, mpgetflt(i)+0.0)) } default: s.Fatalf("bad float size %d", n.Type.Size()) diff --git a/test/run.go b/test/run.go index 1f9b905ea3..de2044704c 100644 --- a/test/run.go +++ b/test/run.go @@ -636,13 +636,7 @@ func (t *test) run() { } case "run": - useTmp = false - switch t.gofile { - case "bug434.go": - // TODO fix this failure - default: - ssaMain = true - } + ssaMain = true out, err := runcmd(append([]string{"go", "run", t.goFileName()}, args...)...) if err != nil { t.err = err -- cgit v1.3 From 545c9662031330ea3f92c51986d8ef1c29684bcb Mon Sep 17 00:00:00 2001 From: Todd Neal Date: Wed, 9 Sep 2015 20:39:31 -0400 Subject: [dev.ssa] test: fix build Add line that was inadvertently removed. Change-Id: I99ebc1041e984e408ae5825836c28b9891d6043b Reviewed-on: https://go-review.googlesource.com/14470 Run-TryBot: Todd Neal Reviewed-by: Keith Randall --- test/run.go | 1 + 1 file changed, 1 insertion(+) (limited to 'test') diff --git a/test/run.go b/test/run.go index de2044704c..57b386de99 100644 --- a/test/run.go +++ b/test/run.go @@ -636,6 +636,7 @@ func (t *test) run() { } case "run": + useTmp = false ssaMain = true out, err := runcmd(append([]string{"go", "run", t.goFileName()}, args...)...) if err != nil { -- cgit v1.3 From e3869a6b65bb0f95dac7eca3d86055160b12589f Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Mon, 7 Sep 2015 23:18:02 -0700 Subject: [dev.ssa] cmd/compile/internal/ssa: implement write barriers For now, we only use typedmemmove. This can be optimized in future CLs. Also add a feature to help with binary searching bad compilations. Together with GOSSAPKG, GOSSAHASH specifies the last few binary digits of the hash of function names that should be compiled. So GOSSAHASH=0110 means compile only those functions whose last 4 bits of hash are 0110. By adding digits to the front we can binary search for the function whose SSA-generated code is causing a test to fail. Change-Id: I5a8b6b70c6f034f59e5753965234cd42ea36d524 Reviewed-on: https://go-review.googlesource.com/14530 Reviewed-by: Keith Randall --- src/cmd/compile/internal/gc/builtin.go | 1 + src/cmd/compile/internal/gc/builtin/runtime.go | 1 + src/cmd/compile/internal/gc/ssa.go | 62 ++++++++++++++++++++++++-- src/cmd/compile/internal/gc/ssa_test.go | 1 - src/cmd/dist/test.go | 7 +-- src/cmd/internal/obj/stack.go | 2 +- src/runtime/mbarrier.go | 8 ++++ src/runtime/stack2.go | 4 +- test/nosplit.go | 4 +- 9 files changed, 76 insertions(+), 14 deletions(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/builtin.go b/src/cmd/compile/internal/gc/builtin.go index f09dd5690f..0e5fe2ab60 100644 --- a/src/cmd/compile/internal/gc/builtin.go +++ b/src/cmd/compile/internal/gc/builtin.go @@ -118,6 +118,7 @@ const runtimeimport = "" + "func @\"\".writebarrierfat1110 (@\"\".dst·1 *any, _ uintptr, @\"\".src·3 any)\n" + "func @\"\".writebarrierfat1111 (@\"\".dst·1 *any, _ uintptr, @\"\".src·3 any)\n" + "func @\"\".typedmemmove (@\"\".typ·1 *byte, @\"\".dst·2 *any, @\"\".src·3 *any)\n" + + "func @\"\".typedmemmove_nostore (@\"\".typ·1 *byte, @\"\".dst·2 *any)\n" + "func @\"\".typedslicecopy (@\"\".typ·2 *byte, @\"\".dst·3 any, @\"\".src·4 any) (? int)\n" + "func @\"\".selectnbsend (@\"\".chanType·2 *byte, @\"\".hchan·3 chan<- any, @\"\".elem·4 *any) (? bool)\n" + "func @\"\".selectnbrecv (@\"\".chanType·2 *byte, @\"\".elem·3 *any, @\"\".hchan·4 <-chan any) (? bool)\n" + diff --git a/src/cmd/compile/internal/gc/builtin/runtime.go b/src/cmd/compile/internal/gc/builtin/runtime.go index 6210f10cdf..f8487de45b 100644 --- a/src/cmd/compile/internal/gc/builtin/runtime.go +++ b/src/cmd/compile/internal/gc/builtin/runtime.go @@ -147,6 +147,7 @@ func writebarrierfat1111(dst *any, _ uintptr, src any) // *byte is really *runtime.Type func typedmemmove(typ *byte, dst *any, src *any) +func typedmemmove_nostore(typ *byte, dst *any) func typedslicecopy(typ *byte, dst any, src any) int func selectnbsend(chanType *byte, hchan chan<- any, elem *any) bool diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index 738685b044..e6a5627abf 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -6,6 +6,7 @@ package gc import ( "bytes" + "crypto/sha1" "fmt" "html" "math" @@ -162,7 +163,28 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // TODO: enable codegen more broadly once the codegen stabilizes // and runtime support is in (gc maps, write barriers, etc.) - return s.f, usessa || localpkg.Name == os.Getenv("GOSSAPKG") + if usessa { + return s.f, true + } + if localpkg.Name != os.Getenv("GOSSAPKG") { + return s.f, false + } + if os.Getenv("GOSSAHASH") == "" { + // Use everything in the package + return s.f, true + } + // Check the hash of the name against a partial input hash. + // We use this feature to do a binary search within a package to + // find a function that is incorrectly compiled. + hstr := "" + for _, b := range sha1.Sum([]byte(name)) { + hstr += fmt.Sprintf("%08b", b) + } + if strings.HasSuffix(hstr, os.Getenv("GOSSAHASH")) { + fmt.Println("GOSSAHASH triggered %s\n", name) + return s.f, true + } + return s.f, false } type state struct { @@ -744,6 +766,7 @@ func (s *state) stmt(n *Node) { fn := call.Left if call.Op != OCALLFUNC { s.Unimplementedf("defer/go of %s", opnames[call.Op]) + return } // Run all argument assignments. The arg slots have already @@ -1852,8 +1875,6 @@ func (s *state) assign(left *Node, right *ssa.Value, wb bool) { if left.Op == ONAME && isblank(left) { return } - // TODO: do write barrier - // if wb t := left.Type dowidth(t) if right == nil { @@ -1880,6 +1901,41 @@ func (s *state) assign(left *Node, right *ssa.Value, wb bool) { s.vars[&memvar] = s.newValue1A(ssa.OpVarDef, ssa.TypeMem, left, s.mem()) } s.vars[&memvar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, t.Size(), addr, right, s.mem()) + if wb { + // if writeBarrierEnabled { + // typedmemmove_nostore(t, &l) + // } + bThen := s.f.NewBlock(ssa.BlockPlain) + bNext := s.f.NewBlock(ssa.BlockPlain) + + aux := &ssa.ExternSymbol{Types[TBOOL], syslook("writeBarrierEnabled", 0).Sym} + flagaddr := s.newValue1A(ssa.OpAddr, Ptrto(Types[TBOOL]), aux, s.sb) + flag := s.newValue2(ssa.OpLoad, Types[TBOOL], flagaddr, s.mem()) + b := s.endBlock() + b.Kind = ssa.BlockIf + b.Likely = ssa.BranchUnlikely + b.Control = flag + b.AddEdgeTo(bThen) + b.AddEdgeTo(bNext) + + s.startBlock(bThen) + // NOTE: there must be no GC suspension points between the write above + // (the OpStore) and this call to typedmemmove_nostore. + // TODO: writebarrierptr_nostore if just one pointer word (or a few?) + taddr := s.newValue1A(ssa.OpAddr, Types[TUINTPTR], &ssa.ExternSymbol{Types[TUINTPTR], typenamesym(left.Type)}, s.sb) + s.vars[&memvar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, int64(Widthptr), s.sp, taddr, s.mem()) + spplus8 := s.newValue1I(ssa.OpOffPtr, Types[TUINTPTR], int64(Widthptr), s.sp) + s.vars[&memvar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, int64(Widthptr), spplus8, addr, s.mem()) + call := s.newValue1A(ssa.OpStaticCall, ssa.TypeMem, syslook("typedmemmove_nostore", 0).Sym, s.mem()) + call.AuxInt = int64(2 * Widthptr) + s.vars[&memvar] = call + c := s.endBlock() + c.Kind = ssa.BlockCall + c.Control = call + c.AddEdgeTo(bNext) + + s.startBlock(bNext) + } } // zeroVal returns the zero value for type t. diff --git a/src/cmd/compile/internal/gc/ssa_test.go b/src/cmd/compile/internal/gc/ssa_test.go index 74415fd560..b3ab09d914 100644 --- a/src/cmd/compile/internal/gc/ssa_test.go +++ b/src/cmd/compile/internal/gc/ssa_test.go @@ -31,7 +31,6 @@ func doTest(t *testing.T, filename string, kind string) { cmd := exec.Command("go", kind, filepath.Join("testdata", filename)) cmd.Stdout = &stdout cmd.Stderr = &stderr - // TODO: set GOGC=off until we have stackmaps if err := cmd.Run(); err != nil { t.Fatalf("Failed: %v:\nOut: %s\nStderr: %s\n", err, &stdout, &stderr) } diff --git a/src/cmd/dist/test.go b/src/cmd/dist/test.go index d80547ed1c..5f8afd0cb3 100644 --- a/src/cmd/dist/test.go +++ b/src/cmd/dist/test.go @@ -277,11 +277,6 @@ func (t *tester) registerStdTest(pkg string) { // TODO: Remove when SSA codegen is used by default. func (t *tester) registerSSATest(pkg string) { - switch pkg { - // known failures due to GOGC=off - case "runtime", "runtime/pprof", "runtime/trace", "sync": - return - } t.tests = append(t.tests, distTest{ name: "go_test_ssa:" + pkg, heading: "Testing packages with SSA codegen.", @@ -297,7 +292,7 @@ func (t *tester) registerSSATest(pkg string) { } args = append(args, pkg) cmd := exec.Command("go", args...) - cmd.Env = mergeEnvLists([]string{"GOSSAPKG=" + path.Base(pkg), "GOGC=off"}, os.Environ()) + cmd.Env = mergeEnvLists([]string{"GOSSAPKG=" + path.Base(pkg)}, os.Environ()) cmd.Stdout = os.Stdout cmd.Stderr = os.Stderr return cmd.Run() diff --git a/src/cmd/internal/obj/stack.go b/src/cmd/internal/obj/stack.go index 87698b3eeb..b1630b55fc 100644 --- a/src/cmd/internal/obj/stack.go +++ b/src/cmd/internal/obj/stack.go @@ -41,7 +41,7 @@ const ( STACKSYSTEM = 0 StackSystem = STACKSYSTEM StackBig = 4096 - StackGuard = 640*stackGuardMultiplier + StackSystem + StackGuard = 960*stackGuardMultiplier + StackSystem StackSmall = 128 StackLimit = StackGuard - StackSystem - StackSmall ) diff --git a/src/runtime/mbarrier.go b/src/runtime/mbarrier.go index 0dbe1ffc9d..c94e44f142 100644 --- a/src/runtime/mbarrier.go +++ b/src/runtime/mbarrier.go @@ -185,6 +185,14 @@ func typedmemmove(typ *_type, dst, src unsafe.Pointer) { heapBitsBulkBarrier(uintptr(dst), typ.size) } +//go:nosplit +func typedmemmove_nostore(typ *_type, dst unsafe.Pointer) { + if typ.kind&kindNoPointers != 0 { + return + } + heapBitsBulkBarrier(uintptr(dst), typ.size) +} + //go:linkname reflect_typedmemmove reflect.typedmemmove func reflect_typedmemmove(typ *_type, dst, src unsafe.Pointer) { typedmemmove(typ, dst, src) diff --git a/src/runtime/stack2.go b/src/runtime/stack2.go index 5ec8d8d060..02b82ebe13 100644 --- a/src/runtime/stack2.go +++ b/src/runtime/stack2.go @@ -54,6 +54,8 @@ The linkers explore all possible call traces involving non-splitting functions to make sure that this limit cannot be violated. */ +// Constants here match those in cmd/internal/obj/stack.go. + const ( // StackSystem is a number of additional bytes to add // to each stack below the usual guard area for OS-specific @@ -84,7 +86,7 @@ const ( // The stack guard is a pointer this many bytes above the // bottom of the stack. - _StackGuard = 640*stackGuardMultiplier + _StackSystem + _StackGuard = 960*stackGuardMultiplier + _StackSystem // After a stack split check the SP is allowed to be this // many bytes below the stack guard. This saves an instruction diff --git a/test/nosplit.go b/test/nosplit.go index e5c2a9f30e..e7c00f5783 100644 --- a/test/nosplit.go +++ b/test/nosplit.go @@ -285,12 +285,12 @@ TestCases: // Instead of rewriting the test cases above, adjust // the first stack frame to use up the extra bytes. if i == 0 { - size += 512 - 128 + size += 832 - 128 // Noopt builds have a larger stackguard. // See ../cmd/dist/buildruntime.go:stackGuardMultiplier for _, s := range strings.Split(os.Getenv("GO_GCFLAGS"), " ") { if s == "-N" { - size += 640 + size += 960 } } } -- cgit v1.3 From d29e92be523efd8270c0e7ca0eaa6afa86bbedca Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Sat, 19 Sep 2015 12:01:39 -0700 Subject: [dev.ssa] cmd/compile: Use varkill only for non-SSAable vars For variables which get SSA'd, SSA keeps track of all the def/kill. It is only for on-stack variables that we need them. This reduces stack frame sizes significantly because often the only use of a variable was a varkill, and without that last use the variable doesn't get allocated in the frame at all. Fixes #12602 Change-Id: I3f00a768aa5ddd8d7772f375b25f846086a3e689 Reviewed-on: https://go-review.googlesource.com/14758 Reviewed-by: Brad Fitzpatrick --- src/cmd/compile/internal/gc/ssa.go | 4 +++- src/cmd/internal/obj/stack.go | 2 +- src/runtime/stack2.go | 2 +- test/nosplit.go | 4 ++-- 4 files changed, 7 insertions(+), 5 deletions(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index 8e0f0dcc9b..6cb5c571c2 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -794,7 +794,9 @@ func (s *state) stmt(n *Node) { // We only care about liveness info at call sites, so putting the // varkill in the store chain is enough to keep it correctly ordered // with respect to call ops. - s.vars[&memVar] = s.newValue1A(ssa.OpVarKill, ssa.TypeMem, n.Left, s.mem()) + if !canSSA(n.Left) { + s.vars[&memVar] = s.newValue1A(ssa.OpVarKill, ssa.TypeMem, n.Left, s.mem()) + } case OCHECKNIL: p := s.expr(n.Left) diff --git a/src/cmd/internal/obj/stack.go b/src/cmd/internal/obj/stack.go index b1630b55fc..87698b3eeb 100644 --- a/src/cmd/internal/obj/stack.go +++ b/src/cmd/internal/obj/stack.go @@ -41,7 +41,7 @@ const ( STACKSYSTEM = 0 StackSystem = STACKSYSTEM StackBig = 4096 - StackGuard = 960*stackGuardMultiplier + StackSystem + StackGuard = 640*stackGuardMultiplier + StackSystem StackSmall = 128 StackLimit = StackGuard - StackSystem - StackSmall ) diff --git a/src/runtime/stack2.go b/src/runtime/stack2.go index 02b82ebe13..59d4ef694d 100644 --- a/src/runtime/stack2.go +++ b/src/runtime/stack2.go @@ -86,7 +86,7 @@ const ( // The stack guard is a pointer this many bytes above the // bottom of the stack. - _StackGuard = 960*stackGuardMultiplier + _StackSystem + _StackGuard = 640*stackGuardMultiplier + _StackSystem // After a stack split check the SP is allowed to be this // many bytes below the stack guard. This saves an instruction diff --git a/test/nosplit.go b/test/nosplit.go index e7c00f5783..e5c2a9f30e 100644 --- a/test/nosplit.go +++ b/test/nosplit.go @@ -285,12 +285,12 @@ TestCases: // Instead of rewriting the test cases above, adjust // the first stack frame to use up the extra bytes. if i == 0 { - size += 832 - 128 + size += 512 - 128 // Noopt builds have a larger stackguard. // See ../cmd/dist/buildruntime.go:stackGuardMultiplier for _, s := range strings.Split(os.Getenv("GO_GCFLAGS"), " ") { if s == "-N" { - size += 960 + size += 640 } } } -- cgit v1.3 From e99dd520665000dfeb848fb4ecd381314b8fe61b Mon Sep 17 00:00:00 2001 From: David Chase Date: Mon, 19 Oct 2015 11:36:07 -0400 Subject: [dev.ssa] cmd/compile: enhance SSA filtering, add OpConvert Modified GOSSA{HASH.PKG} environment variable filters to make it easier to make/run with all SSA for testing. Disable attempts at SSA for architectures that are not amd64 (avoid spurious errors/unimplementeds.) Removed easy out for unimplemented features. Add convert op for proper liveness in presence of uintptr to/from unsafe.Pointer conversions. Tweaked stack sizes to get a pass on windows; 1024 instead 768, was observed to pass at least once. Change-Id: Ida3800afcda67d529e3b1cf48ca4a3f0fa48b2c5 Reviewed-on: https://go-review.googlesource.com/16201 Reviewed-by: Keith Randall Run-TryBot: David Chase --- src/cmd/compile/internal/gc/pgen.go | 4 +- src/cmd/compile/internal/gc/ssa.go | 85 +++++++++++++++++--------- src/cmd/compile/internal/ssa/gen/AMD64.rules | 3 + src/cmd/compile/internal/ssa/gen/genericOps.go | 5 +- src/cmd/compile/internal/ssa/opGen.go | 5 ++ src/cmd/compile/internal/ssa/rewriteAMD64.go | 18 ++++++ src/cmd/compile/internal/ssa/tighten.go | 8 ++- src/cmd/dist/test.go | 5 -- src/cmd/internal/obj/stack.go | 2 +- src/cmd/internal/obj/util.go | 3 + src/runtime/stack.go | 2 +- test/nosplit.go | 8 ++- 12 files changed, 105 insertions(+), 43 deletions(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/pgen.go b/src/cmd/compile/internal/gc/pgen.go index a5010a31b4..b3ba2fbb46 100644 --- a/src/cmd/compile/internal/gc/pgen.go +++ b/src/cmd/compile/internal/gc/pgen.go @@ -414,7 +414,9 @@ func compile(fn *Node) { // Build an SSA backend function. // TODO: get rid of usessa. - ssafn, usessa = buildssa(Curfn) + if Thearch.Thestring == "amd64" { + ssafn, usessa = buildssa(Curfn) + } continpc = nil breakpc = nil diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index 64391b0fca..8939f14136 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -24,8 +24,32 @@ import ( // it will never return nil, and the bool can be removed. func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { name := fn.Func.Nname.Sym.Name + gossahash := os.Getenv("GOSSAHASH") usessa = strings.HasSuffix(name, "_ssa") || strings.Contains(name, "_ssa.") || name == os.Getenv("GOSSAFUNC") + // Environment variable control of SSA CG + // 1. IF GOSSAFUNC == current function name THEN + // compile this function with SSA and log output to ssa.html + + // 2. IF GOSSAHASH == "y" or "Y" THEN + // compile this function (and everything else) with SSA + + // 3. IF GOSSAHASH == "" THEN + // IF GOSSAPKG == current package name THEN + // compile this function (and everything in this package) with SSA + // ELSE + // use the old back end for this function. + // This is for compatibility with existing test harness and should go away. + + // 4. IF GOSSAHASH is a suffix of the binary-rendered SHA1 hash of the function name THEN + // compile this function with SSA + // ELSE + // compile this function with the old back end. + + // Plan is for 3 to be remove, and the 2) dependence on GOSSAHASH changes + // from "y"/"Y" to empty -- then SSA is default, and is disabled by setting + // GOSSAHASH to a value that is neither 0 nor 1 (e.g., "N" or "X") + if usessa { fmt.Println("generating SSA for", name) dumplist("buildssa-enter", fn.Func.Enter) @@ -58,17 +82,6 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { } }() - // If SSA support for the function is incomplete, - // assume that any panics are due to violated - // invariants. Swallow them silently. - defer func() { - if err := recover(); err != nil { - if !e.unimplemented { - panic(err) - } - } - }() - // We construct SSA using an algorithm similar to // Brau, Buchwald, Hack, Leißa, Mallon, and Zwinkau // http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf @@ -167,27 +180,17 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // Main call to ssa package to compile function ssa.Compile(s.f) - // Calculate stats about what percentage of functions SSA handles. - if false { - fmt.Printf("SSA implemented: %t\n", !e.unimplemented) - } - - if e.unimplemented { - return nil, false - } - - // TODO: enable codegen more broadly once the codegen stabilizes - // and runtime support is in (gc maps, write barriers, etc.) - if usessa { + if usessa || gossahash == "y" || gossahash == "Y" { return s.f, true } - if localpkg.Name != os.Getenv("GOSSAPKG") { - return s.f, false - } - if os.Getenv("GOSSAHASH") == "" { + if gossahash == "" { + if localpkg.Name != os.Getenv("GOSSAPKG") { + return s.f, false + } // Use everything in the package return s.f, true } + // Check the hash of the name against a partial input hash. // We use this feature to do a binary search within a package to // find a function that is incorrectly compiled. @@ -195,10 +198,26 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { for _, b := range sha1.Sum([]byte(name)) { hstr += fmt.Sprintf("%08b", b) } - if strings.HasSuffix(hstr, os.Getenv("GOSSAHASH")) { + + if strings.HasSuffix(hstr, gossahash) { fmt.Printf("GOSSAHASH triggered %s\n", name) return s.f, true } + + // Iteratively try additional hashes to allow tests for multi-point + // failure. + for i := 0; true; i++ { + ev := fmt.Sprintf("GOSSAHASH%d", i) + evv := os.Getenv(ev) + if evv == "" { + break + } + if strings.HasSuffix(hstr, evv) { + fmt.Printf("%s triggered %s\n", ev, name) + return s.f, true + } + } + return s.f, false } @@ -1353,6 +1372,15 @@ func (s *state) expr(n *Node) *ssa.Value { // Assume everything will work out, so set up our return value. // Anything interesting that happens from here is a fatal. x := s.expr(n.Left) + + // Special case for not confusing GC and liveness. + // We don't want pointers accidentally classified + // as not-pointers or vice-versa because of copy + // elision. + if to.IsPtr() != from.IsPtr() { + return s.newValue1(ssa.OpConvert, to, x) + } + v := s.newValue1(ssa.OpCopy, to, x) // ensure that v has the right type // CONVNOP closure @@ -1364,6 +1392,7 @@ func (s *state) expr(n *Node) *ssa.Value { if from.Etype == to.Etype { return v } + // unsafe.Pointer <--> *T if to.Etype == TUNSAFEPTR && from.IsPtr() || from.Etype == TUNSAFEPTR && to.IsPtr() { return v diff --git a/src/cmd/compile/internal/ssa/gen/AMD64.rules b/src/cmd/compile/internal/ssa/gen/AMD64.rules index dd50dd2d27..abe103571d 100644 --- a/src/cmd/compile/internal/ssa/gen/AMD64.rules +++ b/src/cmd/compile/internal/ssa/gen/AMD64.rules @@ -281,6 +281,9 @@ (Store [2] ptr val mem) -> (MOVWstore ptr val mem) (Store [1] ptr val mem) -> (MOVBstore ptr val mem) +// We want this to stick out so the to/from ptr conversion is obvious +(Convert x) -> (LEAQ x) + // checks (IsNonNil p) -> (SETNE (TESTQ p p)) (IsInBounds idx len) -> (SETB (CMPQ idx len)) diff --git a/src/cmd/compile/internal/ssa/gen/genericOps.go b/src/cmd/compile/internal/ssa/gen/genericOps.go index 5881596441..8a8837c0e9 100644 --- a/src/cmd/compile/internal/ssa/gen/genericOps.go +++ b/src/cmd/compile/internal/ssa/gen/genericOps.go @@ -237,8 +237,9 @@ var genericOps = []opData{ {name: "Sqrt"}, // sqrt(arg0), float64 only // Data movement - {name: "Phi"}, // select an argument based on which predecessor block we came from - {name: "Copy"}, // output = arg0 + {name: "Phi"}, // select an argument based on which predecessor block we came from + {name: "Copy"}, // output = arg0 + {name: "Convert"}, // output = arg0 -- a copy that converts to/from a pointer // constants. Constant values are stored in the aux field. // booleans have a bool aux field, strings have a string aux diff --git a/src/cmd/compile/internal/ssa/opGen.go b/src/cmd/compile/internal/ssa/opGen.go index d86dce354b..4c191807ba 100644 --- a/src/cmd/compile/internal/ssa/opGen.go +++ b/src/cmd/compile/internal/ssa/opGen.go @@ -455,6 +455,7 @@ const ( OpSqrt OpPhi OpCopy + OpConvert OpConstBool OpConstString OpConstNil @@ -3866,6 +3867,10 @@ var opcodeTable = [...]opInfo{ name: "Copy", generic: true, }, + { + name: "Convert", + generic: true, + }, { name: "ConstBool", generic: true, diff --git a/src/cmd/compile/internal/ssa/rewriteAMD64.go b/src/cmd/compile/internal/ssa/rewriteAMD64.go index 2fd9a08d5b..3fe272c204 100644 --- a/src/cmd/compile/internal/ssa/rewriteAMD64.go +++ b/src/cmd/compile/internal/ssa/rewriteAMD64.go @@ -1670,6 +1670,24 @@ func rewriteValueAMD64(v *Value, config *Config) bool { goto endc395c0a53eeccf597e225a07b53047d1 endc395c0a53eeccf597e225a07b53047d1: ; + case OpConvert: + // match: (Convert x) + // cond: + // result: (LEAQ x) + { + t := v.Type + x := v.Args[0] + v.Op = OpAMD64LEAQ + v.AuxInt = 0 + v.Aux = nil + v.resetArgs() + v.Type = t + v.AddArg(x) + return true + } + goto end1cac40a6074914d6ae3d4aa039a625ed + end1cac40a6074914d6ae3d4aa039a625ed: + ; case OpCvt32Fto32: // match: (Cvt32Fto32 x) // cond: diff --git a/src/cmd/compile/internal/ssa/tighten.go b/src/cmd/compile/internal/ssa/tighten.go index 1da5071a2a..4fa26d2d18 100644 --- a/src/cmd/compile/internal/ssa/tighten.go +++ b/src/cmd/compile/internal/ssa/tighten.go @@ -54,8 +54,12 @@ func tighten(f *Func) { for _, b := range f.Blocks { for i := 0; i < len(b.Values); i++ { v := b.Values[i] - if v.Op == OpPhi || v.Op == OpGetClosurePtr { - // GetClosurePtr must stay in entry block + if v.Op == OpPhi || v.Op == OpGetClosurePtr || v.Op == OpConvert { + // GetClosurePtr must stay in entry block. + // OpConvert must not float over call sites. + // TODO do we instead need a dependence edge of some sort for OpConvert? + // Would memory do the trick, or do we need something else that relates + // to safe point operations? continue } if len(v.Args) > 0 && v.Args[len(v.Args)-1].Type.IsMemory() { diff --git a/src/cmd/dist/test.go b/src/cmd/dist/test.go index c92109afa5..be6cdb5c0b 100644 --- a/src/cmd/dist/test.go +++ b/src/cmd/dist/test.go @@ -278,11 +278,6 @@ func (t *tester) registerStdTest(pkg string) { // TODO: Remove when SSA codegen is used by default. func (t *tester) registerSSATest(pkg string) { - switch pkg { - // known failures - case "runtime": - return - } t.tests = append(t.tests, distTest{ name: "go_test_ssa:" + pkg, heading: "Testing packages with SSA codegen.", diff --git a/src/cmd/internal/obj/stack.go b/src/cmd/internal/obj/stack.go index 87698b3eeb..1ca673285a 100644 --- a/src/cmd/internal/obj/stack.go +++ b/src/cmd/internal/obj/stack.go @@ -41,7 +41,7 @@ const ( STACKSYSTEM = 0 StackSystem = STACKSYSTEM StackBig = 4096 - StackGuard = 640*stackGuardMultiplier + StackSystem + StackGuard = 1024*stackGuardMultiplier + StackSystem StackSmall = 128 StackLimit = StackGuard - StackSystem - StackSmall ) diff --git a/src/cmd/internal/obj/util.go b/src/cmd/internal/obj/util.go index 73d33666e2..a71d69edfc 100644 --- a/src/cmd/internal/obj/util.go +++ b/src/cmd/internal/obj/util.go @@ -385,6 +385,9 @@ func Dconv(p *Prog, a *Addr) string { if a.Index != REG_NONE { str += fmt.Sprintf("(%v*%d)", Rconv(int(a.Index)), int(a.Scale)) } + if p.As == ATYPE && a.Gotype != nil { + str += fmt.Sprintf("%s", a.Gotype.Name) + } case TYPE_CONST: if a.Reg != 0 { diff --git a/src/runtime/stack.go b/src/runtime/stack.go index 1809a4d9ac..128278ebdc 100644 --- a/src/runtime/stack.go +++ b/src/runtime/stack.go @@ -86,7 +86,7 @@ const ( // The stack guard is a pointer this many bytes above the // bottom of the stack. - _StackGuard = 640*stackGuardMultiplier + _StackSystem + _StackGuard = 1024*stackGuardMultiplier + _StackSystem // After a stack split check the SP is allowed to be this // many bytes below the stack guard. This saves an instruction diff --git a/test/nosplit.go b/test/nosplit.go index e5c2a9f30e..70e8fced86 100644 --- a/test/nosplit.go +++ b/test/nosplit.go @@ -9,6 +9,7 @@ package main import ( "bytes" + "cmd/internal/obj" "fmt" "io/ioutil" "log" @@ -285,12 +286,13 @@ TestCases: // Instead of rewriting the test cases above, adjust // the first stack frame to use up the extra bytes. if i == 0 { - size += 512 - 128 + size += (obj.StackGuard - 128) - 128 // Noopt builds have a larger stackguard. - // See ../cmd/dist/buildruntime.go:stackGuardMultiplier + // See ../src/cmd/dist/buildruntime.go:stackGuardMultiplier + // This increase is included in obj.StackGuard for _, s := range strings.Split(os.Getenv("GO_GCFLAGS"), " ") { if s == "-N" { - size += 640 + size += obj.StackGuard } } } -- cgit v1.3 From 729abfa35ca19a3ec9bd11a8c25eecac5eba6cc9 Mon Sep 17 00:00:00 2001 From: David Chase Date: Mon, 26 Oct 2015 17:34:06 -0400 Subject: [dev.ssa] cmd/compile: default compile+test with SSA Some tests disabled, some bifurcated into _ssa and not, with appropriate logging added to compiler. "tests/live.go" in particular needs attention. SSA-specific testing removed, since it's all SSA now. Added "-run_skips" option to tests/run.go to simplify checking whether a test still fails (or how it fails) on a skipped platform. The compiler now compiles with SSA by default. If you don't want SSA, specify GOSSAHASH=n (or N) as an environment variable. Function names ending in "_ssa" are always SSA-compiled. GOSSAFUNC=fname retains its "SSA for fname, log to ssa.html" GOSSAPKG=pkg only has an effect when GOSSAHASH=n GOSSAHASH=10101 etc retains its name-hash-matching behavior for purposes of debugging. See #13068 Change-Id: I8217bfeb34173533eaeb391b5f6935483c7d6b43 Reviewed-on: https://go-review.googlesource.com/16299 Reviewed-by: Keith Randall Run-TryBot: David Chase --- src/cmd/compile/internal/gc/ssa.go | 48 +++++-- src/cmd/compile/internal/ssa/config.go | 14 +- src/cmd/compile/internal/ssa/export_test.go | 8 +- src/cmd/compile/internal/ssa/nilcheck.go | 7 + src/cmd/dist/test.go | 34 ----- test/live.go | 1 + test/live2.go | 1 + test/nilcheck.go | 99 +++++++------- test/nilcheck_ssa.go | 187 +++++++++++++++++++++++++++ test/nilptr3.go | 2 +- test/nilptr3_ssa.go | 194 ++++++++++++++++++++++++++++ test/run.go | 7 + test/sliceopt.go | 1 + 13 files changed, 500 insertions(+), 103 deletions(-) create mode 100644 test/nilcheck_ssa.go create mode 100644 test/nilptr3_ssa.go (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index b96661d15e..521e6d7ffa 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -34,10 +34,10 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // 1. IF GOSSAFUNC == current function name THEN // compile this function with SSA and log output to ssa.html - // 2. IF GOSSAHASH == "y" or "Y" THEN + // 2. IF GOSSAHASH == "" THEN // compile this function (and everything else) with SSA - // 3. IF GOSSAHASH == "" THEN + // 3. IF GOSSAHASH == "n" or "N" // IF GOSSAPKG == current package name THEN // compile this function (and everything in this package) with SSA // ELSE @@ -49,9 +49,10 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // ELSE // compile this function with the old back end. - // Plan is for 3 to be remove, and the 2) dependence on GOSSAHASH changes - // from "y"/"Y" to empty -- then SSA is default, and is disabled by setting - // GOSSAHASH to a value that is neither 0 nor 1 (e.g., "N" or "X") + // Plan is for 3 to be removed when the tests are revised. + // SSA is now default, and is disabled by setting + // GOSSAHASH to n or N, or selectively with strings of + // 0 and 1. if usessa { fmt.Println("generating SSA for", name) @@ -183,10 +184,11 @@ func buildssa(fn *Node) (ssafn *ssa.Func, usessa bool) { // Main call to ssa package to compile function ssa.Compile(s.f) - if usessa || gossahash == "y" || gossahash == "Y" { + // gossahash = "y" is historical/symmetric-with-"n" -- i.e., not really needed. + if usessa || gossahash == "" || gossahash == "y" || gossahash == "Y" { return s.f, true } - if gossahash == "" { + if gossahash == "n" || gossahash == "N" { if localpkg.Name != os.Getenv("GOSSAPKG") { return s.f, false } @@ -298,9 +300,11 @@ func (s *state) label(sym *Sym) *ssaLabel { return lab } -func (s *state) Logf(msg string, args ...interface{}) { s.config.Logf(msg, args...) } -func (s *state) Fatalf(msg string, args ...interface{}) { s.config.Fatalf(msg, args...) } -func (s *state) Unimplementedf(msg string, args ...interface{}) { s.config.Unimplementedf(msg, args...) } +func (s *state) Logf(msg string, args ...interface{}) { s.config.Logf(msg, args...) } +func (s *state) Fatalf(msg string, args ...interface{}) { s.config.Fatalf(msg, args...) } +func (s *state) Unimplementedf(msg string, args ...interface{}) { s.config.Unimplementedf(msg, args...) } +func (s *state) Warnl(line int, msg string, args ...interface{}) { s.config.Warnl(line, msg, args...) } +func (s *state) Debug_checknil() bool { return s.config.Debug_checknil() } var ( // dummy node for the memory variable @@ -1997,7 +2001,7 @@ func (s *state) expr(n *Node) *ssa.Value { if haspointers(et) { // TODO: just one write barrier call for all of these writes? // TODO: maybe just one writeBarrierEnabled check? - s.insertWB(et, addr) + s.insertWB(et, addr, n.Lineno) } } @@ -2044,7 +2048,7 @@ func (s *state) assign(left *Node, right *ssa.Value, wb bool) { } s.vars[&memVar] = s.newValue3I(ssa.OpStore, ssa.TypeMem, t.Size(), addr, right, s.mem()) if wb { - s.insertWB(left.Type, addr) + s.insertWB(left.Type, addr, left.Lineno) } } @@ -2566,7 +2570,7 @@ func (s *state) rtcall(fn *Node, returns bool, results []*Type, args ...*ssa.Val // been stored at location p. Tell the runtime about this write. // Note: there must be no GC suspension points between the write and // the call that this function inserts. -func (s *state) insertWB(t *Type, p *ssa.Value) { +func (s *state) insertWB(t *Type, p *ssa.Value, line int32) { // if writeBarrierEnabled { // typedmemmove_nostore(&t, p) // } @@ -2586,6 +2590,10 @@ func (s *state) insertWB(t *Type, p *ssa.Value) { taddr := s.newValue1A(ssa.OpAddr, Types[TUINTPTR], &ssa.ExternSymbol{Types[TUINTPTR], typenamesym(t)}, s.sb) s.rtcall(typedmemmove_nostore, true, nil, taddr, p) + if Debug_wb > 0 { + Warnl(int(line), "write barrier") + } + b.AddEdgeTo(s.curBlock) } @@ -2985,6 +2993,10 @@ func (s *state) dottype(n *Node, commaok bool) (res, resok *ssa.Value) { Fatalf("dottype needs a direct iface type %s", n.Type) } + if Debug_typeassert > 0 { + Warnl(int(n.Lineno), "type assertion inlined") + } + // TODO: If we have a nonempty interface and its itab field is nil, // then this test is redundant and ifaceType should just branch directly to bFail. cond := s.newValue2(ssa.OpEqPtr, Types[TBOOL], typ, target) @@ -4523,6 +4535,16 @@ func (e *ssaExport) Unimplementedf(msg string, args ...interface{}) { e.unimplemented = true } +// Warnl reports a "warning", which is usually flag-triggered +// logging output for the benefit of tests. +func (e *ssaExport) Warnl(line int, fmt_ string, args ...interface{}) { + Warnl(line, fmt_, args...) +} + +func (e *ssaExport) Debug_checknil() bool { + return Debug_checknil != 0 +} + func (n *Node) Typ() ssa.Type { return n.Type } diff --git a/src/cmd/compile/internal/ssa/config.go b/src/cmd/compile/internal/ssa/config.go index cfba10bc24..014c960267 100644 --- a/src/cmd/compile/internal/ssa/config.go +++ b/src/cmd/compile/internal/ssa/config.go @@ -49,6 +49,12 @@ type Logger interface { // Unimplemented reports that the function cannot be compiled. // It will be removed once SSA work is complete. Unimplementedf(msg string, args ...interface{}) + + // Warnl writes compiler messages in the form expected by "errorcheck" tests + Warnl(line int, fmt_ string, args ...interface{}) + + // Fowards the Debug_checknil flag from gc + Debug_checknil() bool } type Frontend interface { @@ -100,9 +106,11 @@ func (c *Config) NewFunc() *Func { return &Func{Config: c, NamedValues: map[GCNode][]*Value{}} } -func (c *Config) Logf(msg string, args ...interface{}) { c.fe.Logf(msg, args...) } -func (c *Config) Fatalf(msg string, args ...interface{}) { c.fe.Fatalf(msg, args...) } -func (c *Config) Unimplementedf(msg string, args ...interface{}) { c.fe.Unimplementedf(msg, args...) } +func (c *Config) Logf(msg string, args ...interface{}) { c.fe.Logf(msg, args...) } +func (c *Config) Fatalf(msg string, args ...interface{}) { c.fe.Fatalf(msg, args...) } +func (c *Config) Unimplementedf(msg string, args ...interface{}) { c.fe.Unimplementedf(msg, args...) } +func (c *Config) Warnl(line int, msg string, args ...interface{}) { c.fe.Warnl(line, msg, args...) } +func (c *Config) Debug_checknil() bool { return c.fe.Debug_checknil() } // TODO(khr): do we really need a separate Config, or can we just // store all its fields inside a Func? diff --git a/src/cmd/compile/internal/ssa/export_test.go b/src/cmd/compile/internal/ssa/export_test.go index d0ba7b1c09..c37db75803 100644 --- a/src/cmd/compile/internal/ssa/export_test.go +++ b/src/cmd/compile/internal/ssa/export_test.go @@ -32,9 +32,11 @@ func (DummyFrontend) Auto(t Type) GCNode { return nil } -func (d DummyFrontend) Logf(msg string, args ...interface{}) { d.t.Logf(msg, args...) } -func (d DummyFrontend) Fatalf(msg string, args ...interface{}) { d.t.Fatalf(msg, args...) } -func (d DummyFrontend) Unimplementedf(msg string, args ...interface{}) { d.t.Fatalf(msg, args...) } +func (d DummyFrontend) Logf(msg string, args ...interface{}) { d.t.Logf(msg, args...) } +func (d DummyFrontend) Fatalf(msg string, args ...interface{}) { d.t.Fatalf(msg, args...) } +func (d DummyFrontend) Unimplementedf(msg string, args ...interface{}) { d.t.Fatalf(msg, args...) } +func (d DummyFrontend) Warnl(line int, msg string, args ...interface{}) { d.t.Logf(msg, args...) } +func (d DummyFrontend) Debug_checknil() bool { return false } func (d DummyFrontend) TypeBool() Type { return TypeBool } func (d DummyFrontend) TypeInt8() Type { return TypeInt8 } diff --git a/src/cmd/compile/internal/ssa/nilcheck.go b/src/cmd/compile/internal/ssa/nilcheck.go index 5b012a8551..f8caa7b042 100644 --- a/src/cmd/compile/internal/ssa/nilcheck.go +++ b/src/cmd/compile/internal/ssa/nilcheck.go @@ -88,6 +88,13 @@ func nilcheckelim(f *Func) { // Eliminate the nil check. // The deadcode pass will remove vestigial values, // and the fuse pass will join this block with its successor. + + // Logging in the style of the former compiler -- and omit line 1, + // which is usually in generated code. + if f.Config.Debug_checknil() && int(node.block.Control.Line) > 1 { + f.Config.Warnl(int(node.block.Control.Line), "removed nil check") + } + switch node.block.Kind { case BlockIf: node.block.Kind = BlockFirst diff --git a/src/cmd/dist/test.go b/src/cmd/dist/test.go index be6cdb5c0b..0afe4c6060 100644 --- a/src/cmd/dist/test.go +++ b/src/cmd/dist/test.go @@ -13,7 +13,6 @@ import ( "log" "os" "os/exec" - "path" "path/filepath" "regexp" "strconv" @@ -276,31 +275,6 @@ func (t *tester) registerStdTest(pkg string) { }) } -// TODO: Remove when SSA codegen is used by default. -func (t *tester) registerSSATest(pkg string) { - t.tests = append(t.tests, distTest{ - name: "go_test_ssa:" + pkg, - heading: "Testing packages with SSA codegen.", - fn: func() error { - args := []string{ - "test", - "-short", - t.timeout(180 * 3), // SSA generates slower code right now - "-gcflags=" + os.Getenv("GO_GCFLAGS"), - } - if t.race { - args = append(args, "-race") - } - args = append(args, pkg) - cmd := exec.Command("go", args...) - cmd.Env = mergeEnvLists([]string{"GOSSAPKG=" + path.Base(pkg)}, os.Environ()) - cmd.Stdout = os.Stdout - cmd.Stderr = os.Stderr - return cmd.Run() - }, - }) -} - func (t *tester) registerRaceBenchTest(pkg string) { testName := "go_test_bench:" + pkg if t.runRx == nil || t.runRx.MatchString(testName) { @@ -344,9 +318,6 @@ func (t *tester) registerTests() { if strings.HasPrefix(name, "go_test_bench:") { t.registerRaceBenchTest(strings.TrimPrefix(name, "go_test_bench:")) } - if t.goarch == "amd64" && strings.HasPrefix(name, "go_test_ssa:") { - t.registerSSATest(strings.TrimPrefix(name, "go_test_ssa:")) - } } } else { // Use a format string to only list packages and commands that have tests. @@ -363,11 +334,6 @@ func (t *tester) registerTests() { for _, pkg := range pkgs { t.registerStdTest(pkg) } - if t.goarch == "amd64" { - for _, pkg := range pkgs { - t.registerSSATest(pkg) - } - } if t.race { for _, pkg := range pkgs { t.registerRaceBenchTest(pkg) diff --git a/test/live.go b/test/live.go index ae982f4957..c54f091d1b 100644 --- a/test/live.go +++ b/test/live.go @@ -1,3 +1,4 @@ +// +build !amd64 // errorcheck -0 -l -live -wb=0 // Copyright 2014 The Go Authors. All rights reserved. diff --git a/test/live2.go b/test/live2.go index 7474756157..430f9feb7e 100644 --- a/test/live2.go +++ b/test/live2.go @@ -1,3 +1,4 @@ +// +build !amd64 // errorcheck -0 -live -wb=0 // Copyright 2014 The Go Authors. All rights reserved. diff --git a/test/nilcheck.go b/test/nilcheck.go index 99c3c5fdb6..173fcb33a6 100644 --- a/test/nilcheck.go +++ b/test/nilcheck.go @@ -1,3 +1,4 @@ +// +build !amd64 // errorcheck -0 -N -d=nil // Copyright 2013 The Go Authors. All rights reserved. @@ -17,7 +18,7 @@ type Struct struct { type BigStruct struct { X int Y float64 - A [1<<20]int + A [1 << 20]int Z string } @@ -29,86 +30,86 @@ type Empty1 struct { } var ( - intp *int - arrayp *[10]int - array0p *[0]int - bigarrayp *[1<<26]int - structp *Struct + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 26]int + structp *Struct bigstructp *BigStruct - emptyp *Empty - empty1p *Empty1 + emptyp *Empty + empty1p *Empty1 ) func f1() { - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" _ = *array0p // ERROR "nil check" _ = *array0p // ERROR "nil check" - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" _ = *structp // ERROR "nil check" - _ = *emptyp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" + _ = *emptyp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" } func f2() { var ( - intp *int - arrayp *[10]int - array0p *[0]int - bigarrayp *[1<<20]int - structp *Struct + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 20]int + structp *Struct bigstructp *BigStruct - emptyp *Empty - empty1p *Empty1 + emptyp *Empty + empty1p *Empty1 ) - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *array0p // ERROR "nil check" - _ = *array0p // ERROR "nil check" - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *structp // ERROR "nil check" - _ = *emptyp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *bigarrayp // ERROR "nil check" + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *array0p // ERROR "nil check" + _ = *array0p // ERROR "nil check" + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *structp // ERROR "nil check" + _ = *emptyp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *bigarrayp // ERROR "nil check" _ = *bigstructp // ERROR "nil check" - _ = *empty1p // ERROR "nil check" + _ = *empty1p // ERROR "nil check" } func fx10k() *[10000]int -var b bool +var b bool func f3(x *[10000]int) { // Using a huge type and huge offsets so the compiler // does not expect the memory hardware to fault. _ = x[9999] // ERROR "nil check" - + for { if x[9999] != 0 { // ERROR "nil check" break } } - - x = fx10k() + + x = fx10k() _ = x[9999] // ERROR "nil check" if b { _ = x[9999] // ERROR "nil check" } else { _ = x[9999] // ERROR "nil check" - } + } _ = x[9999] // ERROR "nil check" - x = fx10k() + x = fx10k() if b { _ = x[9999] // ERROR "nil check" } else { _ = x[9999] // ERROR "nil check" - } + } _ = x[9999] // ERROR "nil check" - + fx10k() // This one is a bit redundant, if we figured out that // x wasn't going to change across the function call. @@ -138,7 +139,7 @@ func f3b() { _ = &x[9] // ERROR "nil check" } -func fx10() *[10]int +func fx10() *[10]int func f4(x *[10]int) { // Most of these have no checks because a real memory reference follows, @@ -146,33 +147,33 @@ func f4(x *[10]int) { // in the first unmapped page of memory. _ = x[9] // ERROR "nil check" - + for { if x[9] != 0 { // ERROR "nil check" break } } - - x = fx10() + + x = fx10() _ = x[9] // ERROR "nil check" if b { _ = x[9] // ERROR "nil check" } else { _ = x[9] // ERROR "nil check" - } + } _ = x[9] // ERROR "nil check" - x = fx10() + x = fx10() if b { _ = x[9] // ERROR "nil check" } else { _ = &x[9] // ERROR "nil check" - } + } _ = x[9] // ERROR "nil check" - + fx10() _ = x[9] // ERROR "nil check" - + x = fx10() y := fx10() _ = &x[9] // ERROR "nil check" diff --git a/test/nilcheck_ssa.go b/test/nilcheck_ssa.go new file mode 100644 index 0000000000..a20cfd8ae6 --- /dev/null +++ b/test/nilcheck_ssa.go @@ -0,0 +1,187 @@ +// +build amd64 +// errorcheck -0 -N -d=nil + +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Test that nil checks are inserted. +// Optimization is disabled, so redundant checks are not removed. + +package p + +type Struct struct { + X int + Y float64 +} + +type BigStruct struct { + X int + Y float64 + A [1 << 20]int + Z string +} + +type Empty struct { +} + +type Empty1 struct { + Empty +} + +var ( + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 26]int + structp *Struct + bigstructp *BigStruct + emptyp *Empty + empty1p *Empty1 +) + +func f1() { + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *array0p // ERROR "nil check" + _ = *array0p // ERROR "nil check" + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *structp // ERROR "nil check" + _ = *emptyp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" +} + +func f2() { + var ( + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 20]int + structp *Struct + bigstructp *BigStruct + emptyp *Empty + empty1p *Empty1 + ) + + _ = *intp // ERROR "nil check" + _ = *arrayp // ERROR "nil check" + _ = *array0p // ERROR "nil check" + _ = *array0p // ERROR "removed nil check" + _ = *intp // ERROR "removed nil check" + _ = *arrayp // ERROR "removed nil check" + _ = *structp // ERROR "nil check" + _ = *emptyp // ERROR "nil check" + _ = *arrayp // ERROR "removed nil check" + _ = *bigarrayp // ERROR "nil check" + _ = *bigstructp // ERROR "nil check" + _ = *empty1p // ERROR "nil check" +} + +func fx10k() *[10000]int + +var b bool + +func f3(x *[10000]int) { + // Using a huge type and huge offsets so the compiler + // does not expect the memory hardware to fault. + _ = x[9999] // ERROR "nil check" + + for { + if x[9999] != 0 { // ERROR "removed nil check" + break + } + } + + x = fx10k() + _ = x[9999] // ERROR "nil check" + if b { + _ = x[9999] // ERROR "removed nil check" + } else { + _ = x[9999] // ERROR "removed nil check" + } + _ = x[9999] // ERROR "removed nil check" + + x = fx10k() + if b { + _ = x[9999] // ERROR "nil check" + } else { + _ = x[9999] // ERROR "nil check" + } + _ = x[9999] // ERROR "nil check" + + fx10k() + // SSA nilcheck removal works across calls. + _ = x[9999] // ERROR "removed nil check" +} + +func f3a() { + x := fx10k() + y := fx10k() + z := fx10k() + _ = &x[9] // ERROR "nil check" + y = z + _ = &x[9] // ERROR "removed nil check" + x = y + _ = &x[9] // ERROR "nil check" +} + +func f3b() { + x := fx10k() + y := fx10k() + _ = &x[9] // ERROR "nil check" + y = x + _ = &x[9] // ERROR "removed nil check" + x = y + _ = &x[9] // ERROR "removed nil check" +} + +func fx10() *[10]int + +func f4(x *[10]int) { + // Most of these have no checks because a real memory reference follows, + // and the offset is small enough that if x is nil, the address will still be + // in the first unmapped page of memory. + + _ = x[9] // ERROR "nil check" + + for { + if x[9] != 0 { // ERROR "removed nil check" + break + } + } + + x = fx10() + _ = x[9] // ERROR "nil check" + if b { + _ = x[9] // ERROR "removed nil check" + } else { + _ = x[9] // ERROR "removed nil check" + } + _ = x[9] // ERROR "removed nil check" + + x = fx10() + if b { + _ = x[9] // ERROR "nil check" + } else { + _ = &x[9] // ERROR "nil check" + } + _ = x[9] // ERROR "nil check" + + fx10() + _ = x[9] // ERROR "removed nil check" + + x = fx10() + y := fx10() + _ = &x[9] // ERROR "nil check" + y = x + _ = &x[9] // ERROR "removed nil check" + x = y + _ = &x[9] // ERROR "removed nil check" +} + +func f5(m map[string]struct{}) bool { + // Existence-only map lookups should not generate a nil check + _, ok := m[""] + return ok +} diff --git a/test/nilptr3.go b/test/nilptr3.go index 607c6fb984..33045207b2 100644 --- a/test/nilptr3.go +++ b/test/nilptr3.go @@ -1,7 +1,7 @@ // errorcheck -0 -d=nil // Fails on ppc64x because of incomplete optimization. // See issues 9058. -// +build !ppc64,!ppc64le +// +build !ppc64,!ppc64le,!amd64 // Copyright 2013 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style diff --git a/test/nilptr3_ssa.go b/test/nilptr3_ssa.go new file mode 100644 index 0000000000..9824ce1cc0 --- /dev/null +++ b/test/nilptr3_ssa.go @@ -0,0 +1,194 @@ +// errorcheck -0 -d=nil +// Fails on ppc64x because of incomplete optimization. +// See issues 9058. +// +build !ppc64,!ppc64le,amd64 + +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Test that nil checks are removed. +// Optimization is enabled. + +package p + +type Struct struct { + X int + Y float64 +} + +type BigStruct struct { + X int + Y float64 + A [1 << 20]int + Z string +} + +type Empty struct { +} + +type Empty1 struct { + Empty +} + +var ( + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 26]int + structp *Struct + bigstructp *BigStruct + emptyp *Empty + empty1p *Empty1 +) + +func f1() { + _ = *intp // ERROR "generated nil check" + + // This one should be removed but the block copy needs + // to be turned into its own pseudo-op in order to see + // the indirect. + _ = *arrayp // ERROR "generated nil check" + + // 0-byte indirect doesn't suffice. + // we don't registerize globals, so there are no removed.* nil checks. + _ = *array0p // ERROR "generated nil check" + _ = *array0p // ERROR "removed nil check" + + _ = *intp // ERROR "removed nil check" + _ = *arrayp // ERROR "removed nil check" + _ = *structp // ERROR "generated nil check" + _ = *emptyp // ERROR "generated nil check" + _ = *arrayp // ERROR "removed nil check" +} + +func f2() { + var ( + intp *int + arrayp *[10]int + array0p *[0]int + bigarrayp *[1 << 20]int + structp *Struct + bigstructp *BigStruct + emptyp *Empty + empty1p *Empty1 + ) + + _ = *intp // ERROR "generated nil check" + _ = *arrayp // ERROR "generated nil check" + _ = *array0p // ERROR "generated nil check" + _ = *array0p // ERROR "removed.* nil check" + _ = *intp // ERROR "removed.* nil check" + _ = *arrayp // ERROR "removed.* nil check" + _ = *structp // ERROR "generated nil check" + _ = *emptyp // ERROR "generated nil check" + _ = *arrayp // ERROR "removed.* nil check" + _ = *bigarrayp // ERROR "generated nil check" ARM removed nil check before indirect!! + _ = *bigstructp // ERROR "generated nil check" + _ = *empty1p // ERROR "generated nil check" +} + +func fx10k() *[10000]int + +var b bool + +func f3(x *[10000]int) { + // Using a huge type and huge offsets so the compiler + // does not expect the memory hardware to fault. + _ = x[9999] // ERROR "generated nil check" + + for { + if x[9999] != 0 { // ERROR "removed nil check" + break + } + } + + x = fx10k() + _ = x[9999] // ERROR "generated nil check" + if b { + _ = x[9999] // ERROR "removed.* nil check" + } else { + _ = x[9999] // ERROR "removed.* nil check" + } + _ = x[9999] // ERROR "removed nil check" + + x = fx10k() + if b { + _ = x[9999] // ERROR "generated nil check" + } else { + _ = x[9999] // ERROR "generated nil check" + } + _ = x[9999] // ERROR "generated nil check" + + fx10k() + // This one is a bit redundant, if we figured out that + // x wasn't going to change across the function call. + // But it's a little complex to do and in practice doesn't + // matter enough. + _ = x[9999] // ERROR "removed nil check" +} + +func f3a() { + x := fx10k() + y := fx10k() + z := fx10k() + _ = &x[9] // ERROR "generated nil check" + y = z + _ = &x[9] // ERROR "removed.* nil check" + x = y + _ = &x[9] // ERROR "generated nil check" +} + +func f3b() { + x := fx10k() + y := fx10k() + _ = &x[9] // ERROR "generated nil check" + y = x + _ = &x[9] // ERROR "removed.* nil check" + x = y + _ = &x[9] // ERROR "removed.* nil check" +} + +func fx10() *[10]int + +func f4(x *[10]int) { + // Most of these have no checks because a real memory reference follows, + // and the offset is small enough that if x is nil, the address will still be + // in the first unmapped page of memory. + + _ = x[9] // ERROR "generated nil check" // bug would like to remove before indirect + + for { + if x[9] != 0 { // ERROR "removed nil check" + break + } + } + + x = fx10() + _ = x[9] // ERROR "generated nil check" // bug would like to remove before indirect + if b { + _ = x[9] // ERROR "removed nil check" + } else { + _ = x[9] // ERROR "removed nil check" + } + _ = x[9] // ERROR "removed nil check" + + x = fx10() + if b { + _ = x[9] // ERROR "generated nil check" // bug would like to remove before indirect + } else { + _ = &x[9] // ERROR "generated nil check" + } + _ = x[9] // ERROR "generated nil check" // bug would like to remove before indirect + + fx10() + _ = x[9] // ERROR "removed nil check" + + x = fx10() + y := fx10() + _ = &x[9] // ERROR "generated nil check" + y = x + _ = &x[9] // ERROR "removed[a-z ]* nil check" + x = y + _ = &x[9] // ERROR "removed[a-z ]* nil check" +} diff --git a/test/run.go b/test/run.go index 57b386de99..425db6ed4e 100644 --- a/test/run.go +++ b/test/run.go @@ -37,6 +37,7 @@ var ( numParallel = flag.Int("n", runtime.NumCPU(), "number of parallel tests to run") summary = flag.Bool("summary", false, "show summary of results") showSkips = flag.Bool("show_skips", false, "show skipped tests") + runSkips = flag.Bool("run_skips", false, "run skipped tests (ignore skip and build tags)") updateErrors = flag.Bool("update_errors", false, "update error messages in test file based on compiler output") runoutputLimit = flag.Int("l", defaultRunOutputLimit(), "number of parallel runoutput tests to run") @@ -328,6 +329,9 @@ type context struct { // shouldTest looks for build tags in a source file and returns // whether the file should be used according to the tags. func shouldTest(src string, goos, goarch string) (ok bool, whyNot string) { + if *runSkips { + return true, "" + } for _, line := range strings.Split(src, "\n") { line = strings.TrimSpace(line) if strings.HasPrefix(line, "//") { @@ -470,6 +474,9 @@ func (t *test) run() { args = args[1:] } case "skip": + if *runSkips { + break + } t.action = "skip" return default: diff --git a/test/sliceopt.go b/test/sliceopt.go index c9d089f7d2..90ec75086e 100644 --- a/test/sliceopt.go +++ b/test/sliceopt.go @@ -1,3 +1,4 @@ +// +build !amd64 // errorcheck -0 -d=append,slice // Copyright 2015 The Go Authors. All rights reserved. -- cgit v1.3 From 3c26c0db3923451f1340e10524e985597da5bba2 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Thu, 21 Jan 2016 13:27:01 -0800 Subject: [dev.ssa] cmd/compile: short-circuit empty blocks Empty blocks are introduced to remove critical edges. After regalloc, we can remove any of the added blocks that are still empty. Change-Id: I0b40e95ac3a6cc1e632a479443479532b6c5ccd9 Reviewed-on: https://go-review.googlesource.com/18833 TryBot-Result: Gobot Gobot Reviewed-by: David Chase --- src/cmd/compile/internal/gc/ssa.go | 15 ++++++++++++- src/cmd/compile/internal/ssa/TODO | 1 - src/cmd/compile/internal/ssa/check.go | 11 ++++++---- src/cmd/compile/internal/ssa/compile.go | 5 ++++- src/cmd/compile/internal/ssa/trim.go | 37 +++++++++++++++++++++++++++++++++ test/nilptr3_ssa.go | 2 +- 6 files changed, 63 insertions(+), 8 deletions(-) create mode 100644 src/cmd/compile/internal/ssa/trim.go (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index b57958a24d..9dd5859735 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -4183,23 +4183,36 @@ func (s *genState) genValue(v *ssa.Value) { case ssa.OpAMD64LoweredNilCheck: // Optimization - if the subsequent block has a load or store // at the same address, we don't need to issue this instruction. + mem := v.Args[1] for _, w := range v.Block.Succs[0].Values { + if w.Op == ssa.OpPhi { + if w.Type.IsMemory() { + mem = w + } + continue + } if len(w.Args) == 0 || !w.Args[len(w.Args)-1].Type.IsMemory() { // w doesn't use a store - can't be a memory op. continue } - if w.Args[len(w.Args)-1] != v.Args[1] { + if w.Args[len(w.Args)-1] != mem { v.Fatalf("wrong store after nilcheck v=%s w=%s", v, w) } switch w.Op { case ssa.OpAMD64MOVQload, ssa.OpAMD64MOVLload, ssa.OpAMD64MOVWload, ssa.OpAMD64MOVBload, ssa.OpAMD64MOVQstore, ssa.OpAMD64MOVLstore, ssa.OpAMD64MOVWstore, ssa.OpAMD64MOVBstore: if w.Args[0] == v.Args[0] && w.Aux == nil && w.AuxInt >= 0 && w.AuxInt < minZeroPage { + if Debug_checknil != 0 && int(v.Line) > 1 { + Warnl(int(v.Line), "removed nil check") + } return } case ssa.OpAMD64MOVQstoreconst, ssa.OpAMD64MOVLstoreconst, ssa.OpAMD64MOVWstoreconst, ssa.OpAMD64MOVBstoreconst: off := ssa.StoreConst(v.AuxInt).Off() if w.Args[0] == v.Args[0] && w.Aux == nil && off >= 0 && off < minZeroPage { + if Debug_checknil != 0 && int(v.Line) > 1 { + Warnl(int(v.Line), "removed nil check") + } return } } diff --git a/src/cmd/compile/internal/ssa/TODO b/src/cmd/compile/internal/ssa/TODO index 403f98cf40..2f7973c5a3 100644 --- a/src/cmd/compile/internal/ssa/TODO +++ b/src/cmd/compile/internal/ssa/TODO @@ -42,7 +42,6 @@ Optimizations (better compiled code) (all instructions, really) - combine LEAQs - store followed by load to same address -- short circuit blocks which are just a jump (undo critical edge processing when no instructions are put in it by regalloc) - (CMPconst [0] (AND x y)) -> (TEST x y) - more (LOAD (ADDQ )) -> LOADIDX - CMPL/SETEQ/TESTB/JEQ -> CMPL/JEQ diff --git a/src/cmd/compile/internal/ssa/check.go b/src/cmd/compile/internal/ssa/check.go index ca3bbfe494..b74371008c 100644 --- a/src/cmd/compile/internal/ssa/check.go +++ b/src/cmd/compile/internal/ssa/check.go @@ -18,10 +18,12 @@ func checkFunc(f *Func) { f.Fatalf("%s.Func=%s, want %s", b, b.Func.Name, f.Name) } - for i, c := range b.Succs { - for j, d := range b.Succs { - if i != j && c == d { - f.Fatalf("%s.Succs has duplicate block %s", b, c) + if f.RegAlloc == nil { + for i, c := range b.Succs { + for j, d := range b.Succs { + if i != j && c == d { + f.Fatalf("%s.Succs has duplicate block %s", b, c) + } } } } @@ -34,6 +36,7 @@ func checkFunc(f *Func) { // all successors are distinct. They will need to be distinct // anyway for register allocation (duplicate successors implies // the existence of critical edges). + // After regalloc we can allow non-distinct predecessors. for _, p := range b.Preds { var found bool diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 64c1412f9d..7a515f898c 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -105,7 +105,8 @@ var passes = [...]pass{ {"layout", layout}, // schedule blocks {"schedule", schedule}, // schedule values {"flagalloc", flagalloc}, // allocate flags register - {"regalloc", regalloc}, + {"regalloc", regalloc}, // allocate int & float registers + {"trim", trim}, // remove empty blocks } // Double-check phase ordering constraints. @@ -148,6 +149,8 @@ var passOrder = [...]constraint{ {"schedule", "flagalloc"}, // regalloc needs flags to be allocated first. {"flagalloc", "regalloc"}, + // trim needs regalloc to be done first. + {"regalloc", "trim"}, } func init() { diff --git a/src/cmd/compile/internal/ssa/trim.go b/src/cmd/compile/internal/ssa/trim.go new file mode 100644 index 0000000000..594d2aa372 --- /dev/null +++ b/src/cmd/compile/internal/ssa/trim.go @@ -0,0 +1,37 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ssa + +// trim removes blocks with no code in them. +// These blocks were inserted to remove critical edges. +func trim(f *Func) { + i := 0 + for _, b := range f.Blocks { + if b.Kind != BlockPlain || len(b.Values) != 0 || len(b.Preds) != 1 { + f.Blocks[i] = b + i++ + continue + } + // TODO: handle len(b.Preds)>1 case. + + // Splice b out of the graph. + pred := b.Preds[0] + succ := b.Succs[0] + for j, s := range pred.Succs { + if s == b { + pred.Succs[j] = succ + } + } + for j, p := range succ.Preds { + if p == b { + succ.Preds[j] = pred + } + } + } + for j := i; j < len(f.Blocks); j++ { + f.Blocks[j] = nil + } + f.Blocks = f.Blocks[:i] +} diff --git a/test/nilptr3_ssa.go b/test/nilptr3_ssa.go index 9824ce1cc0..d324076114 100644 --- a/test/nilptr3_ssa.go +++ b/test/nilptr3_ssa.go @@ -156,7 +156,7 @@ func f4(x *[10]int) { // and the offset is small enough that if x is nil, the address will still be // in the first unmapped page of memory. - _ = x[9] // ERROR "generated nil check" // bug would like to remove before indirect + _ = x[9] // ERROR "removed nil check" for { if x[9] != 0 { // ERROR "removed nil check" -- cgit v1.3 From 6a96a2fe5a95375e2f8cccca6d848728fef0e09f Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Wed, 27 Jan 2016 16:47:23 -0800 Subject: [dev.ssa] cmd/compile: make cse faster It is one of the slowest compiler phases right now, and we run two of them. Instead of using a map to make the initial partition, use a sort. It is much less memory intensive. Do a few optimizations to avoid work for size-1 equivalence classes. Implement -N. Change-Id: I1d2d85d3771abc918db4dd7cc30b0b2d854b15e1 Reviewed-on: https://go-review.googlesource.com/19024 Reviewed-by: David Chase --- src/cmd/compile/internal/gc/ssa.go | 2 +- src/cmd/compile/internal/ssa/compile.go | 58 ++++---- src/cmd/compile/internal/ssa/config.go | 4 +- src/cmd/compile/internal/ssa/cse.go | 200 ++++++++++++++++++++------ src/cmd/compile/internal/ssa/dom_test.go | 2 +- src/cmd/compile/internal/ssa/export_test.go | 2 +- src/cmd/compile/internal/ssa/nilcheck_test.go | 20 +-- src/cmd/compile/internal/ssa/regalloc.go | 6 + test/nilcheck.go | 1 - test/nilcheck_ssa.go | 187 ------------------------ 10 files changed, 206 insertions(+), 276 deletions(-) delete mode 100644 test/nilcheck_ssa.go (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index de00fe9651..203de6421c 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -121,7 +121,7 @@ func buildssa(fn *Node) *ssa.Func { var e ssaExport e.log = printssa - s.config = ssa.NewConfig(Thearch.Thestring, &e, Ctxt) + s.config = ssa.NewConfig(Thearch.Thestring, &e, Ctxt, Debug['N'] == 0) s.f = s.config.NewFunc() s.f.Name = name s.exitCode = fn.Func.Exit diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 7a515f898c..048f189ffe 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -40,6 +40,9 @@ func Compile(f *Func) { checkFunc(f) const logMemStats = false for _, p := range passes { + if !f.Config.optimize && !p.required { + continue + } phaseName = p.name f.Logf(" pass %s begin\n", p.name) // TODO: capture logging during this pass, add it to the HTML @@ -75,38 +78,39 @@ func Compile(f *Func) { } type pass struct { - name string - fn func(*Func) + name string + fn func(*Func) + required bool } // list of passes for the compiler var passes = [...]pass{ // TODO: combine phielim and copyelim into a single pass? - {"early phielim", phielim}, - {"early copyelim", copyelim}, - {"early deadcode", deadcode}, // remove generated dead code to avoid doing pointless work during opt - {"decompose", decompose}, - {"opt", opt}, - {"opt deadcode", deadcode}, // remove any blocks orphaned during opt - {"generic cse", cse}, - {"nilcheckelim", nilcheckelim}, - {"generic deadcode", deadcode}, - {"fuse", fuse}, - {"dse", dse}, - {"tighten", tighten}, // move values closer to their uses - {"lower", lower}, - {"lowered cse", cse}, - {"lowered deadcode", deadcode}, - {"checkLower", checkLower}, - {"late phielim", phielim}, - {"late copyelim", copyelim}, - {"late deadcode", deadcode}, - {"critical", critical}, // remove critical edges - {"layout", layout}, // schedule blocks - {"schedule", schedule}, // schedule values - {"flagalloc", flagalloc}, // allocate flags register - {"regalloc", regalloc}, // allocate int & float registers - {"trim", trim}, // remove empty blocks + {"early phielim", phielim, false}, + {"early copyelim", copyelim, false}, + {"early deadcode", deadcode, false}, // remove generated dead code to avoid doing pointless work during opt + {"decompose", decompose, true}, + {"opt", opt, true}, // TODO: split required rules and optimizing rules + {"opt deadcode", deadcode, false}, // remove any blocks orphaned during opt + {"generic cse", cse, false}, + {"nilcheckelim", nilcheckelim, false}, + {"generic deadcode", deadcode, false}, + {"fuse", fuse, false}, + {"dse", dse, false}, + {"tighten", tighten, false}, // move values closer to their uses + {"lower", lower, true}, + {"lowered cse", cse, false}, + {"lowered deadcode", deadcode, true}, + {"checkLower", checkLower, true}, + {"late phielim", phielim, false}, + {"late copyelim", copyelim, false}, + {"late deadcode", deadcode, false}, + {"critical", critical, true}, // remove critical edges + {"layout", layout, true}, // schedule blocks + {"schedule", schedule, true}, // schedule values + {"flagalloc", flagalloc, true}, // allocate flags register + {"regalloc", regalloc, true}, // allocate int & float registers + stack slots + {"trim", trim, false}, // remove empty blocks } // Double-check phase ordering constraints. diff --git a/src/cmd/compile/internal/ssa/config.go b/src/cmd/compile/internal/ssa/config.go index fb0d886b88..7325873a15 100644 --- a/src/cmd/compile/internal/ssa/config.go +++ b/src/cmd/compile/internal/ssa/config.go @@ -15,6 +15,7 @@ type Config struct { fe Frontend // callbacks into compiler frontend HTML *HTMLWriter // html writer, for debugging ctxt *obj.Link // Generic arch information + optimize bool // Do optimization // TODO: more stuff. Compiler flags of interest, ... } @@ -80,7 +81,7 @@ type GCNode interface { } // NewConfig returns a new configuration object for the given architecture. -func NewConfig(arch string, fe Frontend, ctxt *obj.Link) *Config { +func NewConfig(arch string, fe Frontend, ctxt *obj.Link, optimize bool) *Config { c := &Config{arch: arch, fe: fe} switch arch { case "amd64": @@ -97,6 +98,7 @@ func NewConfig(arch string, fe Frontend, ctxt *obj.Link) *Config { fe.Unimplementedf(0, "arch %s not implemented", arch) } c.ctxt = ctxt + c.optimize = optimize return c } diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go index 58c52f23e6..7603e17ecf 100644 --- a/src/cmd/compile/internal/ssa/cse.go +++ b/src/cmd/compile/internal/ssa/cse.go @@ -25,56 +25,29 @@ func cse(f *Func) { // It starts with a coarse partition and iteratively refines it // until it reaches a fixed point. - // Make initial partition based on opcode, type-name, aux, auxint, nargs, phi-block, and the ops of v's first args - type key struct { - op Op - typ string - aux interface{} - auxint int64 - nargs int - block ID // block id for phi vars, -1 otherwise - arg0op Op // v.Args[0].Op if len(v.Args) > 0, OpInvalid otherwise - arg1op Op // v.Args[1].Op if len(v.Args) > 1, OpInvalid otherwise - } - m := map[key]eqclass{} + // Make initial coarse partitions by using a subset of the conditions above. + a := make([]*Value, 0, f.NumValues()) for _, b := range f.Blocks { for _, v := range b.Values { - bid := ID(-1) - if v.Op == OpPhi { - bid = b.ID + if v.Type.IsMemory() { + continue // memory values can never cse } - arg0op := OpInvalid - if len(v.Args) > 0 { - arg0op = v.Args[0].Op - } - arg1op := OpInvalid - if len(v.Args) > 1 { - arg1op = v.Args[1].Op - } - - // This assumes that floats are stored in AuxInt - // instead of Aux. If not, then we need to use the - // float bits as part of the key, otherwise since 0.0 == -0.0 - // this would incorrectly treat 0.0 and -0.0 as identical values - k := key{v.Op, v.Type.String(), v.Aux, v.AuxInt, len(v.Args), bid, arg0op, arg1op} - m[k] = append(m[k], v) + a = append(a, v) } } - - // A partition is a set of disjoint eqclasses. - var partition []eqclass - for _, v := range m { - partition = append(partition, v) - } - // TODO: Sort partition here for perfect reproducibility? - // Sort by what? Partition size? - // (Could that improve efficiency by discovering splits earlier?) + partition := partitionValues(a) // map from value id back to eqclass id - valueEqClass := make([]int, f.NumValues()) + valueEqClass := make([]ID, f.NumValues()) + for _, b := range f.Blocks { + for _, v := range b.Values { + // Use negative equivalence class #s for unique values. + valueEqClass[v.ID] = -v.ID + } + } for i, e := range partition { for _, v := range e { - valueEqClass[v.ID] = i + valueEqClass[v.ID] = ID(i) } } @@ -104,7 +77,7 @@ func cse(f *Func) { // move it to the end and shrink e. e[j], e[len(e)-1] = e[len(e)-1], e[j] e = e[:len(e)-1] - valueEqClass[w.ID] = len(partition) + valueEqClass[w.ID] = ID(len(partition)) changed = true continue eqloop } @@ -131,7 +104,6 @@ func cse(f *Func) { // if v and w are in the same equivalence class and v dominates w. rewrite := make([]*Value, f.NumValues()) for _, e := range partition { - sort.Sort(e) // ensure deterministic ordering for len(e) > 1 { // Find a maximal dominant element in e v := e[0] @@ -197,7 +169,141 @@ func dom(b, c *Block, idom []*Block) bool { // final equivalence classes. type eqclass []*Value -// Sort an equivalence class by value ID. -func (e eqclass) Len() int { return len(e) } -func (e eqclass) Swap(i, j int) { e[i], e[j] = e[j], e[i] } -func (e eqclass) Less(i, j int) bool { return e[i].ID < e[j].ID } +// partitionValues partitions the values into equivalence classes +// based on having all the following features match: +// - opcode +// - type +// - auxint +// - aux +// - nargs +// - block # if a phi op +// - first two arg's opcodes +// partitionValues returns a list of equivalence classes, each +// being a sorted by ID list of *Values. The eqclass slices are +// backed by the same storage as the input slice. +// Equivalence classes of size 1 are ignored. +func partitionValues(a []*Value) []eqclass { + typNames := map[Type]string{} + auxIDs := map[interface{}]int32{} + sort.Sort(sortvalues{a, typNames, auxIDs}) + + var partition []eqclass + for len(a) > 0 { + v := a[0] + j := 1 + for ; j < len(a); j++ { + w := a[j] + if v.Op != w.Op || + v.AuxInt != w.AuxInt || + len(v.Args) != len(w.Args) || + v.Op == OpPhi && v.Block != w.Block || + v.Aux != w.Aux || + len(v.Args) >= 1 && v.Args[0].Op != w.Args[0].Op || + len(v.Args) >= 2 && v.Args[1].Op != w.Args[1].Op || + typNames[v.Type] != typNames[w.Type] { + break + } + } + if j > 1 { + partition = append(partition, a[:j]) + } + a = a[j:] + } + + return partition +} + +// Sort values to make the initial partition. +type sortvalues struct { + a []*Value // array of values + typNames map[Type]string // type -> type ID map + auxIDs map[interface{}]int32 // aux -> aux ID map +} + +func (sv sortvalues) Len() int { return len(sv.a) } +func (sv sortvalues) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] } +func (sv sortvalues) Less(i, j int) bool { + v := sv.a[i] + w := sv.a[j] + if v.Op != w.Op { + return v.Op < w.Op + } + if v.AuxInt != w.AuxInt { + return v.AuxInt < w.AuxInt + } + if v.Aux == nil && w.Aux != nil { // cheap aux check - expensive one below. + return true + } + if v.Aux != nil && w.Aux == nil { + return false + } + if len(v.Args) != len(w.Args) { + return len(v.Args) < len(w.Args) + } + if v.Op == OpPhi && v.Block.ID != w.Block.ID { + return v.Block.ID < w.Block.ID + } + if len(v.Args) >= 1 { + x := v.Args[0].Op + y := w.Args[0].Op + if x != y { + return x < y + } + if len(v.Args) >= 2 { + x = v.Args[1].Op + y = w.Args[1].Op + if x != y { + return x < y + } + } + } + + // Sort by type. Types are just interfaces, so we can't compare + // them with < directly. Instead, map types to their names and + // sort on that. + if v.Type != w.Type { + x := sv.typNames[v.Type] + if x == "" { + x = v.Type.String() + sv.typNames[v.Type] = x + } + y := sv.typNames[w.Type] + if y == "" { + y = w.Type.String() + sv.typNames[w.Type] = y + } + if x != y { + return x < y + } + } + + // Same deal for aux fields. + if v.Aux != w.Aux { + x := sv.auxIDs[v.Aux] + if x == 0 { + x = int32(len(sv.auxIDs)) + 1 + sv.auxIDs[v.Aux] = x + } + y := sv.auxIDs[w.Aux] + if y == 0 { + y = int32(len(sv.auxIDs)) + 1 + sv.auxIDs[w.Aux] = y + } + if x != y { + return x < y + } + } + + // TODO(khr): is the above really ok to do? We're building + // the aux->auxID map online as sort is asking about it. If + // sort has some internal randomness, then the numbering might + // change from run to run. That will make the ordering of + // partitions random. It won't break the compiler but may + // make it nondeterministic. We could fix this by computing + // the aux->auxID map ahead of time, but the hope is here that + // we won't need to compute the mapping for many aux fields + // because the values they are in are otherwise unique. + + // Sort by value ID last to keep the sort result deterministic. + return v.ID < w.ID +} diff --git a/src/cmd/compile/internal/ssa/dom_test.go b/src/cmd/compile/internal/ssa/dom_test.go index 84e0093799..7174f10e4d 100644 --- a/src/cmd/compile/internal/ssa/dom_test.go +++ b/src/cmd/compile/internal/ssa/dom_test.go @@ -160,7 +160,7 @@ func genMaxPredValue(size int) []bloc { var domBenchRes []*Block func benchmarkDominators(b *testing.B, size int, bg blockGen) { - c := NewConfig("amd64", DummyFrontend{b}, nil) + c := NewConfig("amd64", DummyFrontend{b}, nil, true) fun := Fun(c, "entry", bg(size)...) CheckFunc(fun.f) diff --git a/src/cmd/compile/internal/ssa/export_test.go b/src/cmd/compile/internal/ssa/export_test.go index badafadd70..962dc52a5f 100644 --- a/src/cmd/compile/internal/ssa/export_test.go +++ b/src/cmd/compile/internal/ssa/export_test.go @@ -16,7 +16,7 @@ var Deadcode = deadcode func testConfig(t *testing.T) *Config { testCtxt := &obj.Link{} - return NewConfig("amd64", DummyFrontend{t}, testCtxt) + return NewConfig("amd64", DummyFrontend{t}, testCtxt, true) } // DummyFrontend is a test-only frontend. diff --git a/src/cmd/compile/internal/ssa/nilcheck_test.go b/src/cmd/compile/internal/ssa/nilcheck_test.go index d4a55c0855..c4aff58d76 100644 --- a/src/cmd/compile/internal/ssa/nilcheck_test.go +++ b/src/cmd/compile/internal/ssa/nilcheck_test.go @@ -40,7 +40,7 @@ func benchmarkNilCheckDeep(b *testing.B, depth int) { Bloc("exit", Exit("mem")), ) - c := NewConfig("amd64", DummyFrontend{b}, nil) + c := NewConfig("amd64", DummyFrontend{b}, nil, true) fun := Fun(c, "entry", blocs...) CheckFunc(fun.f) @@ -64,7 +64,7 @@ func isNilCheck(b *Block) bool { // TestNilcheckSimple verifies that a second repeated nilcheck is removed. func TestNilcheckSimple(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -101,7 +101,7 @@ func TestNilcheckSimple(t *testing.T) { // on the order of the dominees. func TestNilcheckDomOrder(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -137,7 +137,7 @@ func TestNilcheckDomOrder(t *testing.T) { // TestNilcheckAddr verifies that nilchecks of OpAddr constructed values are removed. func TestNilcheckAddr(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -170,7 +170,7 @@ func TestNilcheckAddr(t *testing.T) { // TestNilcheckAddPtr verifies that nilchecks of OpAddPtr constructed values are removed. func TestNilcheckAddPtr(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -204,7 +204,7 @@ func TestNilcheckAddPtr(t *testing.T) { // non-nil are removed. func TestNilcheckPhi(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -248,7 +248,7 @@ func TestNilcheckPhi(t *testing.T) { // are removed, but checks of different pointers are not. func TestNilcheckKeepRemove(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -296,7 +296,7 @@ func TestNilcheckKeepRemove(t *testing.T) { // block are *not* removed. func TestNilcheckInFalseBranch(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -347,7 +347,7 @@ func TestNilcheckInFalseBranch(t *testing.T) { // wil remove the generated nil check. func TestNilcheckUser(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), @@ -386,7 +386,7 @@ func TestNilcheckUser(t *testing.T) { // TestNilcheckBug reproduces a bug in nilcheckelim found by compiling math/big func TestNilcheckBug(t *testing.T) { ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing - c := NewConfig("amd64", DummyFrontend{t}, nil) + c := NewConfig("amd64", DummyFrontend{t}, nil, true) fun := Fun(c, "entry", Bloc("entry", Valu("mem", OpInitMem, TypeMem, 0, ".mem"), diff --git a/src/cmd/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go index 7cbd30311f..9238999074 100644 --- a/src/cmd/compile/internal/ssa/regalloc.go +++ b/src/cmd/compile/internal/ssa/regalloc.go @@ -316,6 +316,12 @@ func (s *regAllocState) assignReg(r register, v *Value, c *Value) { fmt.Printf("assignReg %s %s/%s\n", registers[r].Name(), v, c) } if s.regs[r].v != nil { + if v.Op == OpSB && !v.Block.Func.Config.optimize { + // Rewrite rules may introduce multiple OpSB, and with + // -N they don't get CSEd. Ignore the extra assignments. + s.f.setHome(c, ®isters[r]) + return + } s.f.Fatalf("tried to assign register %d to %s/%s but it is already used by %s", r, v, c, s.regs[r].v) } diff --git a/test/nilcheck.go b/test/nilcheck.go index 173fcb33a6..ab28b33d41 100644 --- a/test/nilcheck.go +++ b/test/nilcheck.go @@ -1,4 +1,3 @@ -// +build !amd64 // errorcheck -0 -N -d=nil // Copyright 2013 The Go Authors. All rights reserved. diff --git a/test/nilcheck_ssa.go b/test/nilcheck_ssa.go deleted file mode 100644 index a20cfd8ae6..0000000000 --- a/test/nilcheck_ssa.go +++ /dev/null @@ -1,187 +0,0 @@ -// +build amd64 -// errorcheck -0 -N -d=nil - -// Copyright 2013 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Test that nil checks are inserted. -// Optimization is disabled, so redundant checks are not removed. - -package p - -type Struct struct { - X int - Y float64 -} - -type BigStruct struct { - X int - Y float64 - A [1 << 20]int - Z string -} - -type Empty struct { -} - -type Empty1 struct { - Empty -} - -var ( - intp *int - arrayp *[10]int - array0p *[0]int - bigarrayp *[1 << 26]int - structp *Struct - bigstructp *BigStruct - emptyp *Empty - empty1p *Empty1 -) - -func f1() { - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *array0p // ERROR "nil check" - _ = *array0p // ERROR "nil check" - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *structp // ERROR "nil check" - _ = *emptyp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" -} - -func f2() { - var ( - intp *int - arrayp *[10]int - array0p *[0]int - bigarrayp *[1 << 20]int - structp *Struct - bigstructp *BigStruct - emptyp *Empty - empty1p *Empty1 - ) - - _ = *intp // ERROR "nil check" - _ = *arrayp // ERROR "nil check" - _ = *array0p // ERROR "nil check" - _ = *array0p // ERROR "removed nil check" - _ = *intp // ERROR "removed nil check" - _ = *arrayp // ERROR "removed nil check" - _ = *structp // ERROR "nil check" - _ = *emptyp // ERROR "nil check" - _ = *arrayp // ERROR "removed nil check" - _ = *bigarrayp // ERROR "nil check" - _ = *bigstructp // ERROR "nil check" - _ = *empty1p // ERROR "nil check" -} - -func fx10k() *[10000]int - -var b bool - -func f3(x *[10000]int) { - // Using a huge type and huge offsets so the compiler - // does not expect the memory hardware to fault. - _ = x[9999] // ERROR "nil check" - - for { - if x[9999] != 0 { // ERROR "removed nil check" - break - } - } - - x = fx10k() - _ = x[9999] // ERROR "nil check" - if b { - _ = x[9999] // ERROR "removed nil check" - } else { - _ = x[9999] // ERROR "removed nil check" - } - _ = x[9999] // ERROR "removed nil check" - - x = fx10k() - if b { - _ = x[9999] // ERROR "nil check" - } else { - _ = x[9999] // ERROR "nil check" - } - _ = x[9999] // ERROR "nil check" - - fx10k() - // SSA nilcheck removal works across calls. - _ = x[9999] // ERROR "removed nil check" -} - -func f3a() { - x := fx10k() - y := fx10k() - z := fx10k() - _ = &x[9] // ERROR "nil check" - y = z - _ = &x[9] // ERROR "removed nil check" - x = y - _ = &x[9] // ERROR "nil check" -} - -func f3b() { - x := fx10k() - y := fx10k() - _ = &x[9] // ERROR "nil check" - y = x - _ = &x[9] // ERROR "removed nil check" - x = y - _ = &x[9] // ERROR "removed nil check" -} - -func fx10() *[10]int - -func f4(x *[10]int) { - // Most of these have no checks because a real memory reference follows, - // and the offset is small enough that if x is nil, the address will still be - // in the first unmapped page of memory. - - _ = x[9] // ERROR "nil check" - - for { - if x[9] != 0 { // ERROR "removed nil check" - break - } - } - - x = fx10() - _ = x[9] // ERROR "nil check" - if b { - _ = x[9] // ERROR "removed nil check" - } else { - _ = x[9] // ERROR "removed nil check" - } - _ = x[9] // ERROR "removed nil check" - - x = fx10() - if b { - _ = x[9] // ERROR "nil check" - } else { - _ = &x[9] // ERROR "nil check" - } - _ = x[9] // ERROR "nil check" - - fx10() - _ = x[9] // ERROR "removed nil check" - - x = fx10() - y := fx10() - _ = &x[9] // ERROR "nil check" - y = x - _ = &x[9] // ERROR "removed nil check" - x = y - _ = &x[9] // ERROR "removed nil check" -} - -func f5(m map[string]struct{}) bool { - // Existence-only map lookups should not generate a nil check - _, ok := m[""] - return ok -} -- cgit v1.3 From d3f15ff6bc353d94b7249f33bb030ee1f7ee887e Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Thu, 25 Feb 2016 11:40:51 -0800 Subject: [dev.ssa] cmd/compile: shrink stack guard Our stack frame sizes look pretty good now. Lower the stack guard from 1024 to 720. Tip is currently using 720. We could go lower (to 640 at least) except PPC doesn't like that. Change-Id: Ie5f96c0e822435638223f1e8a2bd1a1eed68e6aa Reviewed-on: https://go-review.googlesource.com/19922 Run-TryBot: Keith Randall TryBot-Result: Gobot Gobot Reviewed-by: David Chase --- src/cmd/internal/obj/stack.go | 2 +- src/runtime/stack.go | 2 +- test/nosplit.go | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'test') diff --git a/src/cmd/internal/obj/stack.go b/src/cmd/internal/obj/stack.go index 1a2ee12291..80f6c6c164 100644 --- a/src/cmd/internal/obj/stack.go +++ b/src/cmd/internal/obj/stack.go @@ -11,7 +11,7 @@ const ( STACKSYSTEM = 0 StackSystem = STACKSYSTEM StackBig = 4096 - StackGuard = 1024*stackGuardMultiplier + StackSystem + StackGuard = 720*stackGuardMultiplier + StackSystem StackSmall = 128 StackLimit = StackGuard - StackSystem - StackSmall ) diff --git a/src/runtime/stack.go b/src/runtime/stack.go index ba1a1bb143..81059965d9 100644 --- a/src/runtime/stack.go +++ b/src/runtime/stack.go @@ -90,7 +90,7 @@ const ( // The stack guard is a pointer this many bytes above the // bottom of the stack. - _StackGuard = 1024*sys.StackGuardMultiplier + _StackSystem + _StackGuard = 720*sys.StackGuardMultiplier + _StackSystem // After a stack split check the SP is allowed to be this // many bytes below the stack guard. This saves an instruction diff --git a/test/nosplit.go b/test/nosplit.go index 2bf7077808..082fc3b0e6 100644 --- a/test/nosplit.go +++ b/test/nosplit.go @@ -302,13 +302,13 @@ TestCases: // Instead of rewriting the test cases above, adjust // the first stack frame to use up the extra bytes. if i == 0 { - size += (1024 - 128) - 128 + size += (720 - 128) - 128 // Noopt builds have a larger stackguard. // See ../src/cmd/dist/buildruntime.go:stackGuardMultiplier // This increase is included in obj.StackGuard for _, s := range strings.Split(os.Getenv("GO_GCFLAGS"), " ") { if s == "-N" { - size += 1024 + size += 720 } } } -- cgit v1.3 From 4a346e7489038a0913f590da98a12f6e660b683a Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Thu, 25 Feb 2016 13:45:22 -0800 Subject: [dev.ssa] cmd/compile: get rid of nil checks before float loads/stores Just like we do for integer loads/stores. Update #14511 Change-Id: Ic6ca6b54301438a5701ea5fb0be755451cb24d45 Reviewed-on: https://go-review.googlesource.com/19923 Reviewed-by: Josh Bleecher Snyder Run-TryBot: Keith Randall --- src/cmd/compile/internal/gc/ssa.go | 9 ++++++++- test/nilptr3.go | 18 ++++++++++++++++++ test/nilptr3_ssa.go | 15 +++++++++++++++ 3 files changed, 41 insertions(+), 1 deletion(-) (limited to 'test') diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index a463f9dfc5..a64bdd07bd 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -4588,7 +4588,9 @@ func (s *genState) genValue(v *ssa.Value) { case ssa.OpAMD64MOVQload, ssa.OpAMD64MOVLload, ssa.OpAMD64MOVWload, ssa.OpAMD64MOVBload, ssa.OpAMD64MOVQstore, ssa.OpAMD64MOVLstore, ssa.OpAMD64MOVWstore, ssa.OpAMD64MOVBstore, ssa.OpAMD64MOVBQSXload, ssa.OpAMD64MOVBQZXload, ssa.OpAMD64MOVWQSXload, - ssa.OpAMD64MOVWQZXload, ssa.OpAMD64MOVLQSXload, ssa.OpAMD64MOVLQZXload: + ssa.OpAMD64MOVWQZXload, ssa.OpAMD64MOVLQSXload, ssa.OpAMD64MOVLQZXload, + ssa.OpAMD64MOVSSload, ssa.OpAMD64MOVSDload, ssa.OpAMD64MOVOload, + ssa.OpAMD64MOVSSstore, ssa.OpAMD64MOVSDstore, ssa.OpAMD64MOVOstore: if w.Args[0] == v.Args[0] && w.Aux == nil && w.AuxInt >= 0 && w.AuxInt < minZeroPage { if Debug_checknil != 0 && int(v.Line) > 1 { Warnl(int(v.Line), "removed nil check") @@ -4605,6 +4607,11 @@ func (s *genState) genValue(v *ssa.Value) { } } if w.Type.IsMemory() { + if w.Op == ssa.OpVarDef || w.Op == ssa.OpVarKill || w.Op == ssa.OpVarLive { + // these ops are OK + mem = w + continue + } // We can't delay the nil check past the next store. break } diff --git a/test/nilptr3.go b/test/nilptr3.go index 1ba774d839..258547733c 100644 --- a/test/nilptr3.go +++ b/test/nilptr3.go @@ -193,3 +193,21 @@ func f4(x *[10]int) { x = y _ = &x[9] // ERROR "removed repeated nil check" } + +func f5(p *float32, q *float64, r *float32, s *float64) float64 { + x := float64(*p) // ERROR "removed nil check" + y := *q // ERROR "removed nil check" + *r = 7 // ERROR "removed nil check" + *s = 9 // ERROR "removed nil check" + return x + y +} + +type T [29]byte + +func f6(p, q *T) { + x := *p // ERROR "generated nil check" + // On ARM, the nil check on this store gets removed. On other archs, + // it doesn't. Makes this hard to test. SSA will always remove it. + //*q = x + _ = x +} diff --git a/test/nilptr3_ssa.go b/test/nilptr3_ssa.go index d324076114..ba60a64602 100644 --- a/test/nilptr3_ssa.go +++ b/test/nilptr3_ssa.go @@ -192,3 +192,18 @@ func f4(x *[10]int) { x = y _ = &x[9] // ERROR "removed[a-z ]* nil check" } + +func f5(p *float32, q *float64, r *float32, s *float64) float64 { + x := float64(*p) // ERROR "removed nil check" + y := *q // ERROR "removed nil check" + *r = 7 // ERROR "removed nil check" + *s = 9 // ERROR "removed nil check" + return x + y +} + +type T [29]byte + +func f6(p, q *T) { + x := *p // ERROR "removed nil check" + *q = x // ERROR "removed nil check" +} -- cgit v1.3 From b462744e7088bd899ff14170146e31db5edd867e Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Fri, 26 Feb 2016 11:01:14 -0800 Subject: [dev.ssa] test: remove extra tests from non-SSA builds non-SSA backends are all over the map as to whether nil checks get removed or not. amd64, 386, 386/387, arm are all subtly different. Remove these extra checks for now, they are in nilptr3_ssa.go so they won't get lost. Change-Id: I2e0051f488fb2cb7278c6fdd44cb9d68b5778345 Reviewed-on: https://go-review.googlesource.com/19961 Reviewed-by: Brad Fitzpatrick --- test/nilptr3.go | 18 ------------------ 1 file changed, 18 deletions(-) (limited to 'test') diff --git a/test/nilptr3.go b/test/nilptr3.go index 258547733c..1ba774d839 100644 --- a/test/nilptr3.go +++ b/test/nilptr3.go @@ -193,21 +193,3 @@ func f4(x *[10]int) { x = y _ = &x[9] // ERROR "removed repeated nil check" } - -func f5(p *float32, q *float64, r *float32, s *float64) float64 { - x := float64(*p) // ERROR "removed nil check" - y := *q // ERROR "removed nil check" - *r = 7 // ERROR "removed nil check" - *s = 9 // ERROR "removed nil check" - return x + y -} - -type T [29]byte - -func f6(p, q *T) { - x := *p // ERROR "generated nil check" - // On ARM, the nil check on this store gets removed. On other archs, - // it doesn't. Makes this hard to test. SSA will always remove it. - //*q = x - _ = x -} -- cgit v1.3 From bdea1d58cfc55a5156c8df392cfc3133589389db Mon Sep 17 00:00:00 2001 From: Alexandru Moșoi Date: Fri, 19 Feb 2016 12:14:42 +0100 Subject: [dev.ssa] cmd/compile/internal/ssa: remove proven redundant controls. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * It does very simple bounds checking elimination. E.g. removes the second check in for i := range a { a[i]++; a[i++]; } * Improves on the following redundant expression: return a6 || (a6 || (a6 || a4)) || (a6 || (a4 || a6 || (false || a6))) * Linear in the number of block edges. I patched in CL 12960 that does bounds, nil and constant propagation to make sure this CL is not just redundant. Size of pkg/tool/linux_amd64/* (excluding compile which is affected by this change): With IsInBounds and IsSliceInBounds -this -12960 92285080 +this -12960 91947416 -this +12960 91978976 +this +12960 91923088 Gain is ~110% of 12960. Without IsInBounds and IsSliceInBounds (older run) -this -12960 95515512 +this -12960 95492536 -this +12960 95216920 +this +12960 95204440 Shaves 22k on its own. * Can we handle IsInBounds better with this? In for i := range a { a[i]++; } the bounds checking at a[i] is not eliminated. Change-Id: I98957427399145fb33693173fd4d5a8d71c7cc20 Reviewed-on: https://go-review.googlesource.com/19710 Reviewed-by: David Chase Reviewed-by: Keith Randall Run-TryBot: Alexandru Moșoi TryBot-Result: Gobot Gobot --- src/cmd/compile/internal/ssa/compile.go | 5 + src/cmd/compile/internal/ssa/prove.go | 359 ++++++++++++++++++++++++++++++++ test/prove.go | 207 ++++++++++++++++++ 3 files changed, 571 insertions(+) create mode 100644 src/cmd/compile/internal/ssa/prove.go create mode 100644 test/prove.go (limited to 'test') diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 23dab9e273..5e68ea004e 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -165,6 +165,7 @@ var passes = [...]pass{ {name: "opt deadcode", fn: deadcode}, // remove any blocks orphaned during opt {name: "generic cse", fn: cse}, {name: "nilcheckelim", fn: nilcheckelim}, + {name: "prove", fn: prove}, {name: "generic deadcode", fn: deadcode}, {name: "fuse", fn: fuse}, {name: "dse", fn: dse}, @@ -193,6 +194,10 @@ type constraint struct { } var passOrder = [...]constraint{ + // prove reliese on common-subexpression elimination for maximum benefits. + {"generic cse", "prove"}, + // deadcode after prove to eliminate all new dead blocks. + {"prove", "generic deadcode"}, // common-subexpression before dead-store elim, so that we recognize // when two address expressions are the same. {"generic cse", "dse"}, diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go new file mode 100644 index 0000000000..f0f4649896 --- /dev/null +++ b/src/cmd/compile/internal/ssa/prove.go @@ -0,0 +1,359 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ssa + +// rangeMask represents the possible relations between a pair of variables. +type rangeMask uint + +const ( + lt rangeMask = 1 << iota + eq + gt +) + +// typeMask represents the universe of a variable pair in which +// a set of relations is known. +// For example, information learned for unsigned pairs cannot +// be transfered to signed pairs because the same bit representation +// can mean something else. +type typeMask uint + +const ( + signed typeMask = 1 << iota + unsigned + pointer +) + +type typeRange struct { + t typeMask + r rangeMask +} + +type control struct { + tm typeMask + a0, a1 ID +} + +var ( + reverseBits = [...]rangeMask{0, 4, 2, 6, 1, 5, 3, 7} + + // maps what we learn when the positive branch is taken. + // For example: + // OpLess8: {signed, lt}, + // v1 = (OpLess8 v2 v3). + // If v1 branch is taken than we learn that the rangeMaks + // can be at most lt. + typeRangeTable = map[Op]typeRange{ + OpEq8: {signed | unsigned, eq}, + OpEq16: {signed | unsigned, eq}, + OpEq32: {signed | unsigned, eq}, + OpEq64: {signed | unsigned, eq}, + OpEqPtr: {pointer, eq}, + + OpNeq8: {signed | unsigned, lt | gt}, + OpNeq16: {signed | unsigned, lt | gt}, + OpNeq32: {signed | unsigned, lt | gt}, + OpNeq64: {signed | unsigned, lt | gt}, + OpNeqPtr: {pointer, lt | gt}, + + OpLess8: {signed, lt}, + OpLess8U: {unsigned, lt}, + OpLess16: {signed, lt}, + OpLess16U: {unsigned, lt}, + OpLess32: {signed, lt}, + OpLess32U: {unsigned, lt}, + OpLess64: {signed, lt}, + OpLess64U: {unsigned, lt}, + + OpLeq8: {signed, lt | eq}, + OpLeq8U: {unsigned, lt | eq}, + OpLeq16: {signed, lt | eq}, + OpLeq16U: {unsigned, lt | eq}, + OpLeq32: {signed, lt | eq}, + OpLeq32U: {unsigned, lt | eq}, + OpLeq64: {signed, lt | eq}, + OpLeq64U: {unsigned, lt | eq}, + + OpGeq8: {signed, eq | gt}, + OpGeq8U: {unsigned, eq | gt}, + OpGeq16: {signed, eq | gt}, + OpGeq16U: {unsigned, eq | gt}, + OpGeq32: {signed, eq | gt}, + OpGeq32U: {unsigned, eq | gt}, + OpGeq64: {signed, eq | gt}, + OpGeq64U: {unsigned, eq | gt}, + + OpGreater8: {signed, gt}, + OpGreater8U: {unsigned, gt}, + OpGreater16: {signed, gt}, + OpGreater16U: {unsigned, gt}, + OpGreater32: {signed, gt}, + OpGreater32U: {unsigned, gt}, + OpGreater64: {signed, gt}, + OpGreater64U: {unsigned, gt}, + + // TODO: OpIsInBounds actually test 0 <= a < b. This means + // that the positive branch learns signed/LT and unsigned/LT + // but the negative branch only learns unsigned/GE. + OpIsInBounds: {unsigned, lt}, + OpIsSliceInBounds: {unsigned, lt | eq}, + } +) + +// prove removes redundant BlockIf controls that can be inferred in a straight line. +// +// By far, the most common redundant control are generated by bounds checking. +// For example for the code: +// +// a[i] = 4 +// foo(a[i]) +// +// The compiler will generate the following code: +// +// if i >= len(a) { +// panic("not in bounds") +// } +// a[i] = 4 +// if i >= len(a) { +// panic("not in bounds") +// } +// foo(a[i]) +// +// The second comparison i >= len(a) is clearly redundant because if the +// else branch of the first comparison is executed, we already know that i < len(a). +// The code for the second panic can be removed. +func prove(f *Func) { + idom := dominators(f) + sdom := newSparseTree(f, idom) + domTree := make([][]*Block, f.NumBlocks()) + + // Create a block ID -> [dominees] mapping + for _, b := range f.Blocks { + if dom := idom[b.ID]; dom != nil { + domTree[dom.ID] = append(domTree[dom.ID], b) + } + } + + // current node state + type walkState int + const ( + descend walkState = iota + simplify + ) + // work maintains the DFS stack. + type bp struct { + block *Block // current handled block + state walkState // what's to do + saved []typeRange // save previous map entries modified by node + } + work := make([]bp, 0, 256) + work = append(work, bp{ + block: f.Entry, + state: descend, + }) + + // mask keep tracks of restrictions for each pair of values in + // the dominators for the current node. + // Invariant: a0.ID <= a1.ID + // For example {unsigned, a0, a1} -> eq|gt means that from + // predecessors we know that a0 must be greater or equal to + // a1. + mask := make(map[control]rangeMask) + + // DFS on the dominator tree. + for len(work) > 0 { + node := work[len(work)-1] + work = work[:len(work)-1] + + switch node.state { + case descend: + parent := idom[node.block.ID] + tr := getRestrict(sdom, parent, node.block) + saved := updateRestrictions(mask, parent, tr) + + work = append(work, bp{ + block: node.block, + state: simplify, + saved: saved, + }) + + for _, s := range domTree[node.block.ID] { + work = append(work, bp{ + block: s, + state: descend, + }) + } + + case simplify: + simplifyBlock(mask, node.block) + restoreRestrictions(mask, idom[node.block.ID], node.saved) + } + } +} + +// getRestrict returns the range restrictions added by p +// when reaching b. p is the immediate dominator or b. +func getRestrict(sdom sparseTree, p *Block, b *Block) typeRange { + if p == nil || p.Kind != BlockIf { + return typeRange{} + } + tr, has := typeRangeTable[p.Control.Op] + if !has { + return typeRange{} + } + // If p and p.Succs[0] are dominators it means that every path + // from entry to b passes through p and p.Succs[0]. We care that + // no path from entry to b passes through p.Succs[1]. If p.Succs[0] + // has one predecessor then (apart from the degenerate case), + // there is no path from entry that can reach b through p.Succs[1]. + // TODO: how about p->yes->b->yes, i.e. a loop in yes. + if sdom.isAncestorEq(p.Succs[0], b) && len(p.Succs[0].Preds) == 1 { + return tr + } else if sdom.isAncestorEq(p.Succs[1], b) && len(p.Succs[1].Preds) == 1 { + tr.r = (lt | eq | gt) ^ tr.r + return tr + } + return typeRange{} +} + +// updateRestrictions updates restrictions from the previous block (p) based on tr. +// normally tr was calculated with getRestrict. +func updateRestrictions(mask map[control]rangeMask, p *Block, tr typeRange) []typeRange { + if tr.t == 0 { + return nil + } + + // p modifies the restrictions for (a0, a1). + // save and return the previous state. + a0 := p.Control.Args[0] + a1 := p.Control.Args[1] + if a0.ID > a1.ID { + tr.r = reverseBits[tr.r] + a0, a1 = a1, a0 + } + + saved := make([]typeRange, 0, 2) + for t := typeMask(1); t <= tr.t; t <<= 1 { + if t&tr.t == 0 { + continue + } + + i := control{t, a0.ID, a1.ID} + oldRange, ok := mask[i] + if !ok { + if a1 != a0 { + oldRange = lt | eq | gt + } else { // sometimes happens after cse + oldRange = eq + } + } + // if i was not already in the map we save the full range + // so that when we restore it we properly keep track of it. + saved = append(saved, typeRange{t, oldRange}) + // mask[i] contains the possible relations between a0 and a1. + // When we branched from parent we learned that the possible + // relations cannot be more than tr.r. We compute the new set of + // relations as the intersection betwee the old and the new set. + mask[i] = oldRange & tr.r + } + return saved +} + +func restoreRestrictions(mask map[control]rangeMask, p *Block, saved []typeRange) { + if p == nil || p.Kind != BlockIf || len(saved) == 0 { + return + } + + a0 := p.Control.Args[0].ID + a1 := p.Control.Args[1].ID + if a0 > a1 { + a0, a1 = a1, a0 + } + + for _, tr := range saved { + i := control{tr.t, a0, a1} + if tr.r != lt|eq|gt { + mask[i] = tr.r + } else { + delete(mask, i) + } + } +} + +// simplifyBlock simplifies block known the restrictions in mask. +func simplifyBlock(mask map[control]rangeMask, b *Block) { + if b.Kind != BlockIf { + return + } + + tr, has := typeRangeTable[b.Control.Op] + if !has { + return + } + + succ := -1 + a0 := b.Control.Args[0].ID + a1 := b.Control.Args[1].ID + if a0 > a1 { + tr.r = reverseBits[tr.r] + a0, a1 = a1, a0 + } + + for t := typeMask(1); t <= tr.t; t <<= 1 { + if t&tr.t == 0 { + continue + } + + // tr.r represents in which case the positive branch is taken. + // m.r represents which cases are possible because of previous relations. + // If the set of possible relations m.r is included in the set of relations + // need to take the positive branch (or negative) then that branch will + // always be taken. + // For shortcut, if m.r == 0 then this block is dead code. + i := control{t, a0, a1} + m := mask[i] + if m != 0 && tr.r&m == m { + if b.Func.pass.debug > 0 { + b.Func.Config.Warnl(int(b.Line), "Proved %s", b.Control.Op) + } + b.Logf("proved positive branch of %s, block %s in %s\n", b.Control, b, b.Func.Name) + succ = 0 + break + } + if m != 0 && ((lt|eq|gt)^tr.r)&m == m { + if b.Func.pass.debug > 0 { + b.Func.Config.Warnl(int(b.Line), "Disproved %s", b.Control.Op) + } + b.Logf("proved negative branch of %s, block %s in %s\n", b.Control, b, b.Func.Name) + succ = 1 + break + } + } + + if succ == -1 { + // HACK: If the first argument of IsInBounds or IsSliceInBounds + // is a constant and we already know that constant is smaller (or equal) + // to the upper bound than this is proven. Most useful in cases such as: + // if len(a) <= 1 { return } + // do something with a[1] + c := b.Control + if (c.Op == OpIsInBounds || c.Op == OpIsSliceInBounds) && + c.Args[0].Op == OpConst64 && c.Args[0].AuxInt >= 0 { + m := mask[control{signed, a0, a1}] + if m != 0 && tr.r&m == m { + if b.Func.pass.debug > 0 { + b.Func.Config.Warnl(int(b.Line), "Proved constant %s", c.Op) + } + succ = 0 + } + } + } + + if succ != -1 { + b.Kind = BlockFirst + b.Control = nil + b.Succs[0], b.Succs[1] = b.Succs[succ], b.Succs[1-succ] + } +} diff --git a/test/prove.go b/test/prove.go new file mode 100644 index 0000000000..0f5b8ce87f --- /dev/null +++ b/test/prove.go @@ -0,0 +1,207 @@ +// +build amd64 +// errorcheck -0 -d=ssa/prove/debug=3 + +package main + +func f0(a []int) int { + a[0] = 1 + a[0] = 1 // ERROR "Proved IsInBounds$" + a[6] = 1 + a[6] = 1 // ERROR "Proved IsInBounds$" + a[5] = 1 + a[5] = 1 // ERROR "Proved IsInBounds$" + return 13 +} + +func f1(a []int) int { + if len(a) <= 5 { + return 18 + } + a[0] = 1 + a[0] = 1 // ERROR "Proved IsInBounds$" + a[6] = 1 + a[6] = 1 // ERROR "Proved IsInBounds$" + a[5] = 1 // ERROR "Proved constant IsInBounds$" + a[5] = 1 // ERROR "Proved IsInBounds$" + return 26 +} + +func f2(a []int) int { + for i := range a { + a[i] = i + a[i] = i // ERROR "Proved IsInBounds$" + } + return 34 +} + +func f3(a []uint) int { + for i := uint(0); i < uint(len(a)); i++ { + a[i] = i // ERROR "Proved IsInBounds$" + } + return 41 +} + +func f4a(a, b, c int) int { + if a < b { + if a == b { // ERROR "Disproved Eq64$" + return 47 + } + if a > b { // ERROR "Disproved Greater64$" + return 50 + } + if a < b { // ERROR "Proved Less64$" + return 53 + } + if a == b { // ERROR "Disproved Eq64$" + return 56 + } + if a > b { + return 59 + } + return 61 + } + return 63 +} + +func f4b(a, b, c int) int { + if a <= b { + if a >= b { + if a == b { // ERROR "Proved Eq64$" + return 70 + } + return 75 + } + return 77 + } + return 79 +} + +func f4c(a, b, c int) int { + if a <= b { + if a >= b { + if a != b { // ERROR "Disproved Neq64$" + return 73 + } + return 75 + } + return 77 + } + return 79 +} + +func f4d(a, b, c int) int { + if a < b { + if a < c { + if a < b { // ERROR "Proved Less64$" + if a < c { // ERROR "Proved Less64$" + return 87 + } + return 89 + } + return 91 + } + return 93 + } + return 95 +} + +func f4e(a, b, c int) int { + if a < b { + if b > a { // ERROR "Proved Greater64$" + return 101 + } + return 103 + } + return 105 +} + +func f4f(a, b, c int) int { + if a <= b { + if b > a { + if b == a { // ERROR "Disproved Eq64$" + return 112 + } + return 114 + } + if b >= a { // ERROR "Proved Geq64$" + if b == a { // ERROR "Proved Eq64$" + return 118 + } + return 120 + } + return 122 + } + return 124 +} + +func f5(a, b uint) int { + if a == b { + if a <= b { // ERROR "Proved Leq64U$" + return 130 + } + return 132 + } + return 134 +} + +// These comparisons are compile time constants. +func f6a(a uint8) int { + if a < a { // ERROR "Disproved Less8U$" + return 140 + } + return 151 +} + +func f6b(a uint8) int { + if a < a { // ERROR "Disproved Less8U$" + return 140 + } + return 151 +} + +func f6x(a uint8) int { + if a > a { // ERROR "Disproved Greater8U$" + return 143 + } + return 151 +} + +func f6d(a uint8) int { + if a <= a { // ERROR "Proved Leq8U$" + return 146 + } + return 151 +} + +func f6e(a uint8) int { + if a >= a { // ERROR "Proved Geq8U$" + return 149 + } + return 151 +} + +func f7(a []int, b int) int { + if b < len(a) { + a[b] = 3 + if b < len(a) { // ERROR "Proved Less64$" + a[b] = 5 // ERROR "Proved IsInBounds$" + } + } + return 161 +} + +func f8(a, b uint) int { + if a == b { + return 166 + } + if a > b { + return 169 + } + if a < b { // ERROR "Proved Less64U$" + return 172 + } + return 174 +} + +func main() { +} -- cgit v1.3 From e197f467d51318305439610d44af0e20dae7062f Mon Sep 17 00:00:00 2001 From: Alexandru Moșoi Date: Mon, 29 Feb 2016 19:29:04 +0100 Subject: [dev.ssa] cmd/compile/internal/ssa: simplify boolean phis MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * Decreases the generated code slightly. * Similar to phiopt pass from gcc, except it only handles booleans. Handling Eq/Neq had no impact on the generated code. name old time/op new time/op delta Template 453ms ± 4% 451ms ± 4% ~ (p=0.468 n=24+24) GoTypes 1.55s ± 1% 1.55s ± 2% ~ (p=0.287 n=24+25) Compiler 6.53s ± 2% 6.56s ± 1% +0.46% (p=0.050 n=23+23) MakeBash 45.8s ± 2% 45.7s ± 2% ~ (p=0.866 n=24+25) name old text-bytes new text-bytes delta HelloSize 676k ± 0% 676k ± 0% ~ (all samples are equal) CmdGoSize 8.07M ± 0% 8.07M ± 0% -0.03% (p=0.000 n=25+25) Change-Id: Ia62477b7554127958a14cb27f85849b095d63663 Reviewed-on: https://go-review.googlesource.com/20090 Reviewed-by: Keith Randall Run-TryBot: Alexandru Moșoi TryBot-Result: Gobot Gobot --- src/cmd/compile/internal/ssa/compile.go | 1 + src/cmd/compile/internal/ssa/phiopt.go | 86 +++++++++++++++++++++++++++++++++ test/phiopt.go | 43 +++++++++++++++++ 3 files changed, 130 insertions(+) create mode 100644 src/cmd/compile/internal/ssa/phiopt.go create mode 100644 test/phiopt.go (limited to 'test') diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 5e68ea004e..2780e5bcfc 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -164,6 +164,7 @@ var passes = [...]pass{ {name: "zero arg cse", fn: zcse, required: true}, // required to merge OpSB values {name: "opt deadcode", fn: deadcode}, // remove any blocks orphaned during opt {name: "generic cse", fn: cse}, + {name: "phiopt", fn: phiopt}, {name: "nilcheckelim", fn: nilcheckelim}, {name: "prove", fn: prove}, {name: "generic deadcode", fn: deadcode}, diff --git a/src/cmd/compile/internal/ssa/phiopt.go b/src/cmd/compile/internal/ssa/phiopt.go new file mode 100644 index 0000000000..fb17727242 --- /dev/null +++ b/src/cmd/compile/internal/ssa/phiopt.go @@ -0,0 +1,86 @@ +package ssa + +// phiopt eliminates boolean Phis based on the previous if. +// +// Main use case is to transform: +// x := false +// if b { +// x = true +// } +// into x = b. +// +// In SSA code this appears as +// +// b0 +// If b -> b1 b2 +// b1 +// Plain -> b2 +// b2 +// x = (OpPhi (ConstBool [true]) (ConstBool [false])) +// +// In this case we can replace x with a copy of b. +func phiopt(f *Func) { + for _, b := range f.Blocks { + if len(b.Preds) != 2 || len(b.Values) == 0 { + continue + } + + pb0, b0 := b, b.Preds[0] + for b0.Kind != BlockIf && len(b0.Preds) == 1 { + pb0, b0 = b0, b0.Preds[0] + } + if b0.Kind != BlockIf { + continue + } + pb1, b1 := b, b.Preds[1] + for b1.Kind != BlockIf && len(b1.Preds) == 1 { + pb1, b1 = b1, b1.Preds[0] + } + if b1 != b0 { + continue + } + // b0 is the if block giving the boolean value. + + var reverse bool + if b0.Succs[0] == pb0 && b0.Succs[1] == pb1 { + reverse = false + } else if b0.Succs[0] == pb1 && b0.Succs[1] == pb0 { + reverse = true + } else { + b.Fatalf("invalid predecessors\n") + } + + for _, v := range b.Values { + if v.Op != OpPhi || !v.Type.IsBoolean() || v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool { + continue + } + + ok, isCopy := false, false + if v.Args[0].AuxInt == 1 && v.Args[1].AuxInt == 0 { + ok, isCopy = true, !reverse + } else if v.Args[0].AuxInt == 0 && v.Args[1].AuxInt == 1 { + ok, isCopy = true, reverse + } + + // (Phi (ConstBool [x]) (ConstBool [x])) is already handled by opt / phielim. + + if ok && isCopy { + if f.pass.debug > 0 { + f.Config.Warnl(int(b.Line), "converted OpPhi to OpCopy") + } + v.reset(OpCopy) + v.AddArg(b0.Control) + continue + } + if ok && !isCopy { + if f.pass.debug > 0 { + f.Config.Warnl(int(b.Line), "converted OpPhi to OpNot") + } + v.reset(OpNot) + v.AddArg(b0.Control) + continue + } + } + } + +} diff --git a/test/phiopt.go b/test/phiopt.go new file mode 100644 index 0000000000..9b9b701124 --- /dev/null +++ b/test/phiopt.go @@ -0,0 +1,43 @@ +// +build amd64 +// errorcheck -0 -d=ssa/phiopt/debug=3 + +package main + +func f0(a bool) bool { + x := false + if a { + x = true + } else { + x = false + } + return x // ERROR "converted OpPhi to OpCopy$" +} + +func f1(a bool) bool { + x := false + if a { + x = false + } else { + x = true + } + return x // ERROR "converted OpPhi to OpNot$" +} + +func f2(a, b int) bool { + x := true + if a == b { + x = false + } + return x // ERROR "converted OpPhi to OpNot$" +} + +func f3(a, b int) bool { + x := false + if a == b { + x = true + } + return x // ERROR "converted OpPhi to OpCopy$" +} + +func main() { +} -- cgit v1.3 From 6b3462c784df961f22eea0c39490b38093086b83 Mon Sep 17 00:00:00 2001 From: David Chase Date: Sat, 27 Feb 2016 11:54:52 -0500 Subject: [dev.ssa] cmd/compile: adjust branch likeliness for calls/loops Static branch predictions (which guide block ordering) are adjusted based on: loop/not-loop (favor looping) abnormal-exit/not (avoid panic) call/not-call (avoid call) ret/default (treat returns as rare) This appears to make no difference in performance of real code, meaning the compiler itself. The earlier version of this has been stripped down to help make the cost of this only-aesthetic-on-Intel phase be as cheap as possible (we probably want information about inner loops for improving register allocation, but because register allocation follows close behind this pass, conceivably the information could be reused -- so we might do this anyway just to normalize output). For a ./make.bash that takes 200 user seconds, about .75 second is reported in likelyadjust (summing nanoseconds reported with -d=ssa/likelyadjust/time ). Upstream predictions are respected. Includes test, limited to build on amd64 only. Did several iterations on the debugging output to allow some rough checks on behavior. Debug=1 logging notes agree/disagree with earlier passes, allowing analysis like the following: Run on make.bash: GO_GCFLAGS=-d=ssa/likelyadjust/debug \ ./make.bash >& lkly5.log grep 'ranch prediction' lkly5.log | wc -l 78242 // 78k predictions grep 'ranch predi' lkly5.log | egrep -v 'agrees with' | wc -l 29633 // 29k NEW predictions grep 'disagrees' lkly5.log | wc -l 444 // contradicted 444 times grep '< exit' lkly5.log | wc -l 10212 // 10k exit predictions grep '< exit' lkly5.log | egrep 'disagrees' | wc -l 5 // 5 contradicted by previous prediction grep '< exit' lkly5.log | egrep -v 'agrees' | wc -l 702 // 702-5 redundant with previous prediction grep '< call' lkly5.log | egrep -v 'agrees' | wc -l 16699 // 16k new call predictions grep 'stay in loop' lkly5.log | egrep -v 'agrees' | wc -l 3951 // 4k new "remain in loop" predictions Fixes #11451. Change-Id: Iafb0504f7030d304ef4b6dc1aba9a5789151a593 Reviewed-on: https://go-review.googlesource.com/19995 Run-TryBot: David Chase Reviewed-by: Keith Randall --- src/cmd/compile/internal/ssa/TODO | 3 +- src/cmd/compile/internal/ssa/compile.go | 3 +- src/cmd/compile/internal/ssa/likelyadjust.go | 300 +++++++++++++++++++++++++++ test/opt_branchlikely.go | 85 ++++++++ 4 files changed, 388 insertions(+), 3 deletions(-) create mode 100755 src/cmd/compile/internal/ssa/likelyadjust.go create mode 100644 test/opt_branchlikely.go (limited to 'test') diff --git a/src/cmd/compile/internal/ssa/TODO b/src/cmd/compile/internal/ssa/TODO index 4e39d1e9c3..a457e67101 100644 --- a/src/cmd/compile/internal/ssa/TODO +++ b/src/cmd/compile/internal/ssa/TODO @@ -24,7 +24,7 @@ Optimizations (better compiled code) - Figure out how to make PARAMOUT variables ssa-able. They need to get spilled automatically at end-of-function somehow. - If strings are being passed around without being interpreted (ptr - and len feilds being accessed) pass them in xmm registers? + and len fields being accessed) pass them in xmm registers? Same for interfaces? - OpArrayIndex should take its index in AuxInt, not a full value. - remove FLAGS from REP instruction clobbers @@ -32,7 +32,6 @@ Optimizations (better compiled code) Note that this is challenging for ops that generate flags because flagalloc wants to move those instructions around for flag regeneration. -- In forms like if ... { call } else { no call }, mark the call branch as unlikely. - Non-constant rotate detection. - Do 0 <= x && x < n with one unsigned compare - nil-check removal in indexed load/store case: diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 2780e5bcfc..f68819c3c2 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -178,7 +178,8 @@ var passes = [...]pass{ {name: "late phielim", fn: phielim}, {name: "late copyelim", fn: copyelim}, {name: "late deadcode", fn: deadcode}, - {name: "critical", fn: critical, required: true}, // remove critical edges + {name: "critical", fn: critical, required: true}, // remove critical edges + {name: "likelyadjust", fn: likelyadjust}, {name: "layout", fn: layout, required: true}, // schedule blocks {name: "schedule", fn: schedule, required: true}, // schedule values {name: "flagalloc", fn: flagalloc, required: true}, // allocate flags register diff --git a/src/cmd/compile/internal/ssa/likelyadjust.go b/src/cmd/compile/internal/ssa/likelyadjust.go new file mode 100755 index 0000000000..6ce8705272 --- /dev/null +++ b/src/cmd/compile/internal/ssa/likelyadjust.go @@ -0,0 +1,300 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ssa + +import ( + "fmt" +) + +type loop struct { + header *Block // The header node of this (reducible) loop + outer *loop // loop containing this loop + // Next two fields not currently used, but cheap to maintain, + // and aid in computation of inner-ness and list of blocks. + nBlocks int32 // Number of blocks in this loop but not within inner loops + isInner bool // True if never discovered to contain a loop +} + +// outerinner records that outer contains inner +func (sdom sparseTree) outerinner(outer, inner *loop) { + oldouter := inner.outer + if oldouter == nil || sdom.isAncestorEq(oldouter.header, outer.header) { + inner.outer = outer + outer.isInner = false + } +} + +type loopnest struct { + f *Func + b2l []*loop + po []*Block + sdom sparseTree + loops []*loop +} + +func min8(a, b int8) int8 { + if a < b { + return a + } + return b +} + +func max8(a, b int8) int8 { + if a > b { + return a + } + return b +} + +const ( + blDEFAULT = 0 + blMin = blDEFAULT + blCALL = 1 + blRET = 2 + blEXIT = 3 +) + +var bllikelies [4]string = [4]string{"default", "call", "ret", "exit"} + +func describePredictionAgrees(b *Block, prediction BranchPrediction) string { + s := "" + if prediction == b.Likely { + s = " (agrees with previous)" + } else if b.Likely != BranchUnknown { + s = " (disagrees with previous, ignored)" + } + return s +} + +func describeBranchPrediction(f *Func, b *Block, likely, not int8, prediction BranchPrediction) { + f.Config.Warnl(int(b.Line), "Branch prediction rule %s < %s%s", + bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction)) +} + +func likelyadjust(f *Func) { + // The values assigned to certain and local only matter + // in their rank order. 0 is default, more positive + // is less likely. It's possible to assign a negative + // unlikeliness (though not currently the case). + certain := make([]int8, f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit + local := make([]int8, f.NumBlocks()) // for our immediate predecessors. + + nest := loopnestfor(f) + po := nest.po + b2l := nest.b2l + + for _, b := range po { + switch b.Kind { + case BlockExit: + // Very unlikely. + local[b.ID] = blEXIT + certain[b.ID] = blEXIT + + // Ret, it depends. + case BlockRet, BlockRetJmp: + local[b.ID] = blRET + certain[b.ID] = blRET + + // Calls. TODO not all calls are equal, names give useful clues. + // Any name-based heuristics are only relative to other calls, + // and less influential than inferences from loop structure. + case BlockCall: + local[b.ID] = blCALL + certain[b.ID] = max8(blCALL, certain[b.Succs[0].ID]) + + default: + if len(b.Succs) == 1 { + certain[b.ID] = certain[b.Succs[0].ID] + } else if len(b.Succs) == 2 { + // If successor is an unvisited backedge, it's in loop and we don't care. + // Its default unlikely is also zero which is consistent with favoring loop edges. + // Notice that this can act like a "reset" on unlikeliness at loops; the + // default "everything returns" unlikeliness is erased by min with the + // backedge likeliness; however a loop with calls on every path will be + // tagged with call cost. Net effect is that loop entry is favored. + b0 := b.Succs[0].ID + b1 := b.Succs[1].ID + certain[b.ID] = min8(certain[b0], certain[b1]) + + l := b2l[b.ID] + l0 := b2l[b0] + l1 := b2l[b1] + + prediction := b.Likely + // Weak loop heuristic -- both source and at least one dest are in loops, + // and there is a difference in the destinations. + // TODO what is best arrangement for nested loops? + if l != nil && l0 != l1 { + noprediction := false + switch { + // prefer not to exit loops + case l1 == nil: + prediction = BranchLikely + case l0 == nil: + prediction = BranchUnlikely + + // prefer to stay in loop, not exit to outer. + case l == l0: + prediction = BranchLikely + case l == l1: + prediction = BranchUnlikely + default: + noprediction = true + } + if f.pass.debug > 0 && !noprediction { + f.Config.Warnl(int(b.Line), "Branch prediction rule stay in loop%s", + describePredictionAgrees(b, prediction)) + } + + } else { + // Lacking loop structure, fall back on heuristics. + if certain[b1] > certain[b0] { + prediction = BranchLikely + if f.pass.debug > 0 { + describeBranchPrediction(f, b, certain[b0], certain[b1], prediction) + } + } else if certain[b0] > certain[b1] { + prediction = BranchUnlikely + if f.pass.debug > 0 { + describeBranchPrediction(f, b, certain[b1], certain[b0], prediction) + } + } else if local[b1] > local[b0] { + prediction = BranchLikely + if f.pass.debug > 0 { + describeBranchPrediction(f, b, local[b0], local[b1], prediction) + } + } else if local[b0] > local[b1] { + prediction = BranchUnlikely + if f.pass.debug > 0 { + describeBranchPrediction(f, b, local[b1], local[b0], prediction) + } + } + } + if b.Likely != prediction { + if b.Likely == BranchUnknown { + b.Likely = prediction + } + } + } + } + if f.pass.debug > 2 { + f.Config.Warnl(int(b.Line), "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin]) + } + + } +} + +func (l *loop) String() string { + return fmt.Sprintf("hdr:%s", l.header) +} + +func (l *loop) LongString() string { + i := "" + o := "" + if l.isInner { + i = ", INNER" + } + if l.outer != nil { + o = ", o=" + l.outer.header.String() + } + return fmt.Sprintf("hdr:%s%s%s", l.header, i, o) +} + +// nearestOuterLoop returns the outer loop of loop most nearly +// containing block b; the header must dominate b. loop itself +// is assumed to not be that loop. For acceptable performance, +// we're relying on loop nests to not be terribly deep. +func (l *loop) nearestOuterLoop(sdom sparseTree, b *Block) *loop { + var o *loop + for o = l.outer; o != nil && !sdom.isAncestorEq(o.header, b); o = o.outer { + } + return o +} + +func loopnestfor(f *Func) *loopnest { + po := postorder(f) + dom := dominators(f) + sdom := newSparseTree(f, dom) + b2l := make([]*loop, f.NumBlocks()) + loops := make([]*loop, 0) + + // Reducible-loop-nest-finding. + for _, b := range po { + if f.pass.debug > 3 { + fmt.Printf("loop finding (0) at %s\n", b) + } + + var innermost *loop // innermost header reachable from this block + + // IF any successor s of b is in a loop headed by h + // AND h dominates b + // THEN b is in the loop headed by h. + // + // Choose the first/innermost such h. + // + // IF s itself dominates b, the s is a loop header; + // and there may be more than one such s. + // Since there's at most 2 successors, the inner/outer ordering + // between them can be established with simple comparisons. + for _, bb := range b.Succs { + l := b2l[bb.ID] + + if sdom.isAncestorEq(bb, b) { // Found a loop header + if l == nil { + l = &loop{header: bb, isInner: true} + loops = append(loops, l) + b2l[bb.ID] = l + } + } else { // Perhaps a loop header is inherited. + // is there any loop containing our successor whose + // header dominates b? + if l != nil && !sdom.isAncestorEq(l.header, b) { + l = l.nearestOuterLoop(sdom, b) + } + } + + if l == nil || innermost == l { + continue + } + + if innermost == nil { + innermost = l + continue + } + + if sdom.isAncestor(innermost.header, l.header) { + sdom.outerinner(innermost, l) + innermost = l + } else if sdom.isAncestor(l.header, innermost.header) { + sdom.outerinner(l, innermost) + } + } + + if innermost != nil { + b2l[b.ID] = innermost + innermost.nBlocks++ + } + } + if f.pass.debug > 1 && len(loops) > 0 { + fmt.Printf("Loops in %s:\n", f.Name) + for _, l := range loops { + fmt.Printf("%s, b=", l.LongString()) + for _, b := range f.Blocks { + if b2l[b.ID] == l { + fmt.Printf(" %s", b) + } + } + fmt.Print("\n") + } + fmt.Printf("Nonloop blocks in %s:", f.Name) + for _, b := range f.Blocks { + if b2l[b.ID] == nil { + fmt.Printf(" %s", b) + } + } + fmt.Print("\n") + } + return &loopnest{f, b2l, po, sdom, loops} +} diff --git a/test/opt_branchlikely.go b/test/opt_branchlikely.go new file mode 100644 index 0000000000..99e914654f --- /dev/null +++ b/test/opt_branchlikely.go @@ -0,0 +1,85 @@ +// +build amd64 +// errorcheck -0 -d=ssa/likelyadjust/debug=1 + +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Test that branches have some prediction properties. +package foo + +func f(x, y, z int) int { + a := 0 + for i := 0; i < x; i++ { // ERROR "Branch prediction rule stay in loop" + for j := 0; j < y; j++ { // ERROR "Branch prediction rule stay in loop" + a += j + } + for k := 0; k < z; k++ { // ERROR "Branch prediction rule stay in loop" + a -= x + y + z + } + } + return a +} + +func g(x, y, z int) int { + a := 0 + if y == 0 { // ERROR "Branch prediction rule default < call" + y = g(y, z, x) + } else { + y++ + } + if y == x { // ERROR "Branch prediction rule default < call" + y = g(y, z, x) + } else { + } + if y == 2 { // ERROR "Branch prediction rule default < call" + z++ + } else { + y = g(z, x, y) + } + if y+z == 3 { // ERROR "Branch prediction rule call < exit" + println("ha ha") + } else { + panic("help help help") + } + if x != 0 { // ERROR "Branch prediction rule default < ret" + for i := 0; i < x; i++ { // ERROR "Branch prediction rule stay in loop" + if x == 4 { // ERROR "Branch prediction rule stay in loop" + return a + } + for j := 0; j < y; j++ { // ERROR "Branch prediction rule stay in loop" + for k := 0; k < z; k++ { // ERROR "Branch prediction rule stay in loop" + a -= j * i + } + a += j + } + } + } + return a +} + +func h(x, y, z int) int { + a := 0 + for i := 0; i < x; i++ { // ERROR "Branch prediction rule stay in loop" + for j := 0; j < y; j++ { // ERROR "Branch prediction rule stay in loop" + a += j + if i == j { // ERROR "Branch prediction rule stay in loop" + break + } + a *= j + } + for k := 0; k < z; k++ { // ERROR "Branch prediction rule stay in loop" + a -= k + if i == k { + continue + } + a *= k + } + } + if a > 0 { // ERROR "Branch prediction rule default < call" + a = g(x, y, z) + } else { + a = -a + } + return a +} -- cgit v1.3