| // Derived from Inferno utils/6c/reg.c |
| // http://code.google.com/p/inferno-os/source/browse/utils/6c/reg.c |
| // |
| // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved. |
| // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net) |
| // Portions Copyright © 1997-1999 Vita Nuova Limited |
| // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) |
| // Portions Copyright © 2004,2006 Bruce Ellis |
| // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net) |
| // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others |
| // Portions Copyright © 2009 The Go Authors. All rights reserved. |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a copy |
| // of this software and associated documentation files (the "Software"), to deal |
| // in the Software without restriction, including without limitation the rights |
| // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| // copies of the Software, and to permit persons to whom the Software is |
| // furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| // THE SOFTWARE. |
| |
| package gc |
| |
| import ( |
| "cmd/internal/obj" |
| "fmt" |
| "sort" |
| "strings" |
| ) |
| |
| // "Portable" optimizations. |
| // Compiled separately for 5g, 6g, and 8g, so allowed to use gg.h, opt.h. |
| // Must code to the intersection of the three back ends. |
| |
| // Derived from Inferno utils/6c/gc.h |
| // http://code.google.com/p/inferno-os/source/browse/utils/6c/gc.h |
| // |
| // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved. |
| // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net) |
| // Portions Copyright © 1997-1999 Vita Nuova Limited |
| // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) |
| // Portions Copyright © 2004,2006 Bruce Ellis |
| // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net) |
| // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others |
| // Portions Copyright © 2009 The Go Authors. All rights reserved. |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a copy |
| // of this software and associated documentation files (the "Software"), to deal |
| // in the Software without restriction, including without limitation the rights |
| // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| // copies of the Software, and to permit persons to whom the Software is |
| // furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| // THE SOFTWARE. |
| |
| const ( |
| CLOAD = 5 |
| CREF = 5 |
| CINF = 1000 |
| LOOP = 3 |
| ) |
| |
| type Reg struct { |
| set Bits |
| use1 Bits |
| use2 Bits |
| refbehind Bits |
| refahead Bits |
| calbehind Bits |
| calahead Bits |
| regdiff Bits |
| act Bits |
| regu uint64 |
| } |
| |
| type Rgn struct { |
| enter *Flow |
| cost int16 |
| varno int16 |
| regno int16 |
| } |
| |
| var Z *Node |
| |
| // A Reg is a wrapper around a single Prog (one instruction) that holds |
| // register optimization information while the optimizer runs. |
| // r->prog is the instruction. |
| |
| var R *Reg |
| |
| const ( |
| NRGN = 600 |
| ) |
| |
| // A Rgn represents a single regopt variable over a region of code |
| // where a register could potentially be dedicated to that variable. |
| // The code encompassed by a Rgn is defined by the flow graph, |
| // starting at enter, flood-filling forward while varno is refahead |
| // and backward while varno is refbehind, and following branches. A |
| // single variable may be represented by multiple disjoint Rgns and |
| // each Rgn may choose a different register for that variable. |
| // Registers are allocated to regions greedily in order of descending |
| // cost. |
| |
| var zreg Reg |
| |
| var region [NRGN]Rgn |
| |
| var rgp *Rgn |
| |
| var nregion int |
| |
| var nvar int |
| |
| var regbits uint64 |
| |
| var externs Bits |
| |
| var params Bits |
| |
| var consts Bits |
| |
| var addrs Bits |
| |
| var ivar Bits |
| |
| var ovar Bits |
| |
| var change int |
| |
| var maxnr int32 |
| |
| type OptStats struct { |
| Ncvtreg int32 |
| Nspill int32 |
| Nreload int32 |
| Ndelmov int32 |
| Nvar int32 |
| Naddr int32 |
| } |
| |
| var Ostats OptStats |
| |
| /* |
| * reg.c |
| */ |
| |
| /* |
| * peep.c |
| void peep(Prog*); |
| void excise(Flow*); |
| int copyu(Prog*, Adr*, Adr*); |
| */ |
| |
| /* |
| * prog.c |
| |
| void proginfo(ProgInfo*, Prog*); |
| */ |
| // p is a call instruction. Does the call fail to return? |
| |
| var noreturn_symlist [10]*Sym |
| |
| func Noreturn(p *obj.Prog) bool { |
| if noreturn_symlist[0] == nil { |
| noreturn_symlist[0] = Pkglookup("panicindex", Runtimepkg) |
| noreturn_symlist[1] = Pkglookup("panicslice", Runtimepkg) |
| noreturn_symlist[2] = Pkglookup("throwinit", Runtimepkg) |
| noreturn_symlist[3] = Pkglookup("gopanic", Runtimepkg) |
| noreturn_symlist[4] = Pkglookup("panicwrap", Runtimepkg) |
| noreturn_symlist[5] = Pkglookup("throwreturn", Runtimepkg) |
| noreturn_symlist[6] = Pkglookup("selectgo", Runtimepkg) |
| noreturn_symlist[7] = Pkglookup("block", Runtimepkg) |
| } |
| |
| if p.To.Node == nil { |
| return false |
| } |
| s := ((p.To.Node).(*Node)).Sym |
| if s == nil { |
| return false |
| } |
| for i := 0; noreturn_symlist[i] != nil; i++ { |
| if s == noreturn_symlist[i] { |
| return true |
| } |
| } |
| return false |
| } |
| |
| // JMP chasing and removal. |
| // |
| // The code generator depends on being able to write out jump |
| // instructions that it can jump to now but fill in later. |
| // the linker will resolve them nicely, but they make the code |
| // longer and more difficult to follow during debugging. |
| // Remove them. |
| |
| /* what instruction does a JMP to p eventually land on? */ |
| func chasejmp(p *obj.Prog, jmploop *int) *obj.Prog { |
| n := 0 |
| for p != nil && p.As == obj.AJMP && p.To.Type == obj.TYPE_BRANCH { |
| n++ |
| if n > 10 { |
| *jmploop = 1 |
| break |
| } |
| |
| p = p.To.U.Branch |
| } |
| |
| return p |
| } |
| |
| /* |
| * reuse reg pointer for mark/sweep state. |
| * leave reg==nil at end because alive==nil. |
| */ |
| var alive interface{} = nil |
| var dead interface{} = 1 |
| |
| /* mark all code reachable from firstp as alive */ |
| func mark(firstp *obj.Prog) { |
| for p := firstp; p != nil; p = p.Link { |
| if p.Opt != dead { |
| break |
| } |
| p.Opt = alive |
| if p.As != obj.ACALL && p.To.Type == obj.TYPE_BRANCH && p.To.U.Branch != nil { |
| mark(p.To.U.Branch) |
| } |
| if p.As == obj.AJMP || p.As == obj.ARET || p.As == obj.AUNDEF { |
| break |
| } |
| } |
| } |
| |
| func fixjmp(firstp *obj.Prog) { |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("\nfixjmp\n") |
| } |
| |
| // pass 1: resolve jump to jump, mark all code as dead. |
| jmploop := 0 |
| |
| for p := firstp; p != nil; p = p.Link { |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("%v\n", p) |
| } |
| if p.As != obj.ACALL && p.To.Type == obj.TYPE_BRANCH && p.To.U.Branch != nil && p.To.U.Branch.As == obj.AJMP { |
| p.To.U.Branch = chasejmp(p.To.U.Branch, &jmploop) |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("->%v\n", p) |
| } |
| } |
| |
| p.Opt = dead |
| } |
| |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("\n") |
| } |
| |
| // pass 2: mark all reachable code alive |
| mark(firstp) |
| |
| // pass 3: delete dead code (mostly JMPs). |
| last := (*obj.Prog)(nil) |
| |
| for p := firstp; p != nil; p = p.Link { |
| if p.Opt == dead { |
| if p.Link == nil && p.As == obj.ARET && last != nil && last.As != obj.ARET { |
| // This is the final ARET, and the code so far doesn't have one. |
| // Let it stay. The register allocator assumes that all live code in |
| // the function can be traversed by starting at all the RET instructions |
| // and following predecessor links. If we remove the final RET, |
| // this assumption will not hold in the case of an infinite loop |
| // at the end of a function. |
| // Keep the RET but mark it dead for the liveness analysis. |
| p.Mode = 1 |
| } else { |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("del %v\n", p) |
| } |
| continue |
| } |
| } |
| |
| if last != nil { |
| last.Link = p |
| } |
| last = p |
| } |
| |
| last.Link = nil |
| |
| // pass 4: elide JMP to next instruction. |
| // only safe if there are no jumps to JMPs anymore. |
| if jmploop == 0 { |
| last := (*obj.Prog)(nil) |
| for p := firstp; p != nil; p = p.Link { |
| if p.As == obj.AJMP && p.To.Type == obj.TYPE_BRANCH && p.To.U.Branch == p.Link { |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("del %v\n", p) |
| } |
| continue |
| } |
| |
| if last != nil { |
| last.Link = p |
| } |
| last = p |
| } |
| |
| last.Link = nil |
| } |
| |
| if Debug['R'] != 0 && Debug['v'] != 0 { |
| fmt.Printf("\n") |
| for p := firstp; p != nil; p = p.Link { |
| fmt.Printf("%v\n", p) |
| } |
| fmt.Printf("\n") |
| } |
| } |
| |
| // Control flow analysis. The Flow structures hold predecessor and successor |
| // information as well as basic loop analysis. |
| // |
| // graph = flowstart(firstp, 0); |
| // ... use flow graph ... |
| // flowend(graph); // free graph |
| // |
| // Typical uses of the flow graph are to iterate over all the flow-relevant instructions: |
| // |
| // for(f = graph->start; f != nil; f = f->link) |
| // |
| // or, given an instruction f, to iterate over all the predecessors, which is |
| // f->p1 and this list: |
| // |
| // for(f2 = f->p2; f2 != nil; f2 = f2->p2link) |
| // |
| // The size argument to flowstart specifies an amount of zeroed memory |
| // to allocate in every f->data field, for use by the client. |
| // If size == 0, f->data will be nil. |
| |
| func Flowstart(firstp *obj.Prog, newData func() interface{}) *Graph { |
| var info ProgInfo |
| |
| // Count and mark instructions to annotate. |
| nf := 0 |
| |
| for p := firstp; p != nil; p = p.Link { |
| p.Opt = nil // should be already, but just in case |
| Thearch.Proginfo(&info, p) |
| if info.Flags&Skip != 0 { |
| continue |
| } |
| p.Opt = interface{}(1) |
| nf++ |
| } |
| |
| if nf == 0 { |
| return nil |
| } |
| |
| if nf >= 20000 { |
| // fatal("%S is too big (%d instructions)", curfn->nname->sym, nf); |
| return nil |
| } |
| |
| // Allocate annotations and assign to instructions. |
| graph := new(Graph) |
| ff := make([]Flow, nf) |
| start := &ff[0] |
| id := 0 |
| var last *Flow |
| for p := firstp; p != nil; p = p.Link { |
| if p.Opt == nil { |
| continue |
| } |
| f := &ff[0] |
| ff = ff[1:] |
| p.Opt = f |
| f.Prog = p |
| if last != nil { |
| last.Link = f |
| } |
| last = f |
| if newData != nil { |
| f.Data = newData() |
| } |
| f.Id = int32(id) |
| id++ |
| } |
| |
| // Fill in pred/succ information. |
| var f1 *Flow |
| var p *obj.Prog |
| for f := start; f != nil; f = f.Link { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| if info.Flags&Break == 0 { |
| f1 = f.Link |
| f.S1 = f1 |
| f1.P1 = f |
| } |
| |
| if p.To.Type == obj.TYPE_BRANCH { |
| if p.To.U.Branch == nil { |
| Fatal("pnil %v", p) |
| } |
| f1 = p.To.U.Branch.Opt.(*Flow) |
| if f1 == nil { |
| Fatal("fnil %v / %v", p, p.To.U.Branch) |
| } |
| if f1 == f { |
| //fatal("self loop %P", p); |
| continue |
| } |
| |
| f.S2 = f1 |
| f.P2link = f1.P2 |
| f1.P2 = f |
| } |
| } |
| |
| graph.Start = start |
| graph.Num = nf |
| return graph |
| } |
| |
| func Flowend(graph *Graph) { |
| for f := graph.Start; f != nil; f = f.Link { |
| f.Prog.Opt = nil |
| } |
| } |
| |
| /* |
| * find looping structure |
| * |
| * 1) find reverse postordering |
| * 2) find approximate dominators, |
| * the actual dominators if the flow graph is reducible |
| * otherwise, dominators plus some other non-dominators. |
| * See Matthew S. Hecht and Jeffrey D. Ullman, |
| * "Analysis of a Simple Algorithm for Global Data Flow Problems", |
| * Conf. Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts, |
| * Oct. 1-3, 1973, pp. 207-217. |
| * 3) find all nodes with a predecessor dominated by the current node. |
| * such a node is a loop head. |
| * recursively, all preds with a greater rpo number are in the loop |
| */ |
| func postorder(r *Flow, rpo2r []*Flow, n int32) int32 { |
| r.Rpo = 1 |
| r1 := r.S1 |
| if r1 != nil && r1.Rpo == 0 { |
| n = postorder(r1, rpo2r, n) |
| } |
| r1 = r.S2 |
| if r1 != nil && r1.Rpo == 0 { |
| n = postorder(r1, rpo2r, n) |
| } |
| rpo2r[n] = r |
| n++ |
| return n |
| } |
| |
| func rpolca(idom []int32, rpo1 int32, rpo2 int32) int32 { |
| if rpo1 == -1 { |
| return rpo2 |
| } |
| var t int32 |
| for rpo1 != rpo2 { |
| if rpo1 > rpo2 { |
| t = rpo2 |
| rpo2 = rpo1 |
| rpo1 = t |
| } |
| |
| for rpo1 < rpo2 { |
| t = idom[rpo2] |
| if t >= rpo2 { |
| Fatal("bad idom") |
| } |
| rpo2 = t |
| } |
| } |
| |
| return rpo1 |
| } |
| |
| func doms(idom []int32, r int32, s int32) bool { |
| for s > r { |
| s = idom[s] |
| } |
| return s == r |
| } |
| |
| func loophead(idom []int32, r *Flow) bool { |
| src := r.Rpo |
| if r.P1 != nil && doms(idom, src, r.P1.Rpo) { |
| return true |
| } |
| for r = r.P2; r != nil; r = r.P2link { |
| if doms(idom, src, r.Rpo) { |
| return true |
| } |
| } |
| return false |
| } |
| |
| func loopmark(rpo2r **Flow, head int32, r *Flow) { |
| if r.Rpo < head || r.Active == head { |
| return |
| } |
| r.Active = head |
| r.Loop += LOOP |
| if r.P1 != nil { |
| loopmark(rpo2r, head, r.P1) |
| } |
| for r = r.P2; r != nil; r = r.P2link { |
| loopmark(rpo2r, head, r) |
| } |
| } |
| |
| func flowrpo(g *Graph) { |
| g.Rpo = make([]*Flow, g.Num) |
| idom := make([]int32, g.Num) |
| |
| for r1 := g.Start; r1 != nil; r1 = r1.Link { |
| r1.Active = 0 |
| } |
| |
| rpo2r := g.Rpo |
| d := postorder(g.Start, rpo2r, 0) |
| nr := int32(g.Num) |
| if d > nr { |
| Fatal("too many reg nodes %d %d", d, nr) |
| } |
| nr = d |
| var r1 *Flow |
| for i := int32(0); i < nr/2; i++ { |
| r1 = rpo2r[i] |
| rpo2r[i] = rpo2r[nr-1-i] |
| rpo2r[nr-1-i] = r1 |
| } |
| |
| for i := int32(0); i < nr; i++ { |
| rpo2r[i].Rpo = i |
| } |
| |
| idom[0] = 0 |
| var me int32 |
| for i := int32(0); i < nr; i++ { |
| r1 = rpo2r[i] |
| me = r1.Rpo |
| d = -1 |
| |
| // rpo2r[r->rpo] == r protects against considering dead code, |
| // which has r->rpo == 0. |
| if r1.P1 != nil && rpo2r[r1.P1.Rpo] == r1.P1 && r1.P1.Rpo < me { |
| d = r1.P1.Rpo |
| } |
| for r1 = r1.P2; r1 != nil; r1 = r1.P2link { |
| if rpo2r[r1.Rpo] == r1 && r1.Rpo < me { |
| d = rpolca(idom, d, r1.Rpo) |
| } |
| } |
| idom[i] = d |
| } |
| |
| for i := int32(0); i < nr; i++ { |
| r1 = rpo2r[i] |
| r1.Loop++ |
| if r1.P2 != nil && loophead(idom, r1) { |
| loopmark(&rpo2r[0], i, r1) |
| } |
| } |
| |
| for r1 := g.Start; r1 != nil; r1 = r1.Link { |
| r1.Active = 0 |
| } |
| } |
| |
| func Uniqp(r *Flow) *Flow { |
| r1 := r.P1 |
| if r1 == nil { |
| r1 = r.P2 |
| if r1 == nil || r1.P2link != nil { |
| return nil |
| } |
| } else if r.P2 != nil { |
| return nil |
| } |
| return r1 |
| } |
| |
| func Uniqs(r *Flow) *Flow { |
| r1 := r.S1 |
| if r1 == nil { |
| r1 = r.S2 |
| if r1 == nil { |
| return nil |
| } |
| } else if r.S2 != nil { |
| return nil |
| } |
| return r1 |
| } |
| |
| // The compilers assume they can generate temporary variables |
| // as needed to preserve the right semantics or simplify code |
| // generation and the back end will still generate good code. |
| // This results in a large number of ephemeral temporary variables. |
| // Merge temps with non-overlapping lifetimes and equal types using the |
| // greedy algorithm in Poletto and Sarkar, "Linear Scan Register Allocation", |
| // ACM TOPLAS 1999. |
| |
| type TempVar struct { |
| node *Node |
| def *Flow |
| use *Flow |
| freelink *TempVar |
| merge *TempVar |
| start int64 |
| end int64 |
| addr uint8 |
| removed uint8 |
| } |
| |
| type startcmp []*TempVar |
| |
| func (x startcmp) Len() int { |
| return len(x) |
| } |
| |
| func (x startcmp) Swap(i, j int) { |
| x[i], x[j] = x[j], x[i] |
| } |
| |
| func (x startcmp) Less(i, j int) bool { |
| a := x[i] |
| b := x[j] |
| |
| if a.start < b.start { |
| return true |
| } |
| if a.start > b.start { |
| return false |
| } |
| |
| // Order what's left by id or symbol name, |
| // just so that sort is forced into a specific ordering, |
| // so that the result of the sort does not depend on |
| // the sort implementation. |
| if a.def != b.def { |
| return int(a.def.Id-b.def.Id) < 0 |
| } |
| if a.node != b.node { |
| return stringsCompare(a.node.Sym.Name, b.node.Sym.Name) < 0 |
| } |
| return false |
| } |
| |
| // Is n available for merging? |
| func canmerge(n *Node) bool { |
| return n.Class == PAUTO && strings.HasPrefix(n.Sym.Name, "autotmp") |
| } |
| |
| func mergetemp(firstp *obj.Prog) { |
| const ( |
| debugmerge = 1 |
| ) |
| |
| g := Flowstart(firstp, nil) |
| if g == nil { |
| return |
| } |
| |
| // Build list of all mergeable variables. |
| nvar := 0 |
| for l := Curfn.Dcl; l != nil; l = l.Next { |
| if canmerge(l.N) { |
| nvar++ |
| } |
| } |
| |
| var_ := make([]TempVar, nvar) |
| nvar = 0 |
| var n *Node |
| var v *TempVar |
| for l := Curfn.Dcl; l != nil; l = l.Next { |
| n = l.N |
| if canmerge(n) { |
| v = &var_[nvar] |
| nvar++ |
| n.Opt = v |
| v.node = n |
| } |
| } |
| |
| // Build list of uses. |
| // We assume that the earliest reference to a temporary is its definition. |
| // This is not true of variables in general but our temporaries are all |
| // single-use (that's why we have so many!). |
| var p *obj.Prog |
| var info ProgInfo |
| for f := g.Start; f != nil; f = f.Link { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| |
| if p.From.Node != nil && ((p.From.Node).(*Node)).Opt != nil && p.To.Node != nil && ((p.To.Node).(*Node)).Opt != nil { |
| Fatal("double node %v", p) |
| } |
| v = nil |
| n, _ = p.From.Node.(*Node) |
| if n != nil { |
| v, _ = n.Opt.(*TempVar) |
| } |
| if v == nil { |
| n, _ = p.To.Node.(*Node) |
| if n != nil { |
| v, _ = n.Opt.(*TempVar) |
| } |
| } |
| if v != nil { |
| if v.def == nil { |
| v.def = f |
| } |
| f.Data = v.use |
| v.use = f |
| if n == p.From.Node && (info.Flags&LeftAddr != 0) { |
| v.addr = 1 |
| } |
| } |
| } |
| |
| if debugmerge > 1 && Debug['v'] != 0 { |
| Dumpit("before", g.Start, 0) |
| } |
| |
| nkill := 0 |
| |
| // Special case. |
| var p1 *obj.Prog |
| var info1 ProgInfo |
| var f *Flow |
| for i := 0; i < len(var_); i++ { |
| v = &var_[i] |
| if v.addr != 0 { |
| continue |
| } |
| |
| // Used in only one instruction, which had better be a write. |
| f = v.use |
| if f != nil && f.Data.(*Flow) == nil { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| if p.To.Node == v.node && (info.Flags&RightWrite != 0) && info.Flags&RightRead == 0 { |
| p.As = obj.ANOP |
| p.To = obj.Addr{} |
| v.removed = 1 |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("drop write-only %v\n", Sconv(v.node.Sym, 0)) |
| } |
| } else { |
| Fatal("temp used and not set: %v", p) |
| } |
| nkill++ |
| continue |
| } |
| |
| // Written in one instruction, read in the next, otherwise unused, |
| // no jumps to the next instruction. Happens mainly in 386 compiler. |
| f = v.use |
| if f != nil && f.Link == f.Data.(*Flow) && (f.Data.(*Flow)).Data.(*Flow) == nil && Uniqp(f.Link) == f { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| p1 = f.Link.Prog |
| Thearch.Proginfo(&info1, p1) |
| const ( |
| SizeAny = SizeB | SizeW | SizeL | SizeQ | SizeF | SizeD |
| ) |
| if p.From.Node == v.node && p1.To.Node == v.node && (info.Flags&Move != 0) && (info.Flags|info1.Flags)&(LeftAddr|RightAddr) == 0 && info.Flags&SizeAny == info1.Flags&SizeAny { |
| p1.From = p.From |
| Thearch.Excise(f) |
| v.removed = 1 |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("drop immediate-use %v\n", Sconv(v.node.Sym, 0)) |
| } |
| } |
| |
| nkill++ |
| continue |
| } |
| } |
| |
| // Traverse live range of each variable to set start, end. |
| // Each flood uses a new value of gen so that we don't have |
| // to clear all the r->active words after each variable. |
| gen := int32(0) |
| |
| for i := 0; i < len(var_); i++ { |
| v = &var_[i] |
| gen++ |
| for f = v.use; f != nil; f = f.Data.(*Flow) { |
| mergewalk(v, f, uint32(gen)) |
| } |
| if v.addr != 0 { |
| gen++ |
| for f = v.use; f != nil; f = f.Data.(*Flow) { |
| varkillwalk(v, f, uint32(gen)) |
| } |
| } |
| } |
| |
| // Sort variables by start. |
| bystart := make([]*TempVar, len(var_)) |
| |
| for i := 0; i < len(var_); i++ { |
| bystart[i] = &var_[i] |
| } |
| sort.Sort(startcmp(bystart[:len(var_)])) |
| |
| // List of in-use variables, sorted by end, so that the ones that |
| // will last the longest are the earliest ones in the array. |
| // The tail inuse[nfree:] holds no-longer-used variables. |
| // In theory we should use a sorted tree so that insertions are |
| // guaranteed O(log n) and then the loop is guaranteed O(n log n). |
| // In practice, it doesn't really matter. |
| inuse := make([]*TempVar, len(var_)) |
| |
| ninuse := 0 |
| nfree := len(var_) |
| var t *Type |
| var v1 *TempVar |
| var j int |
| for i := 0; i < len(var_); i++ { |
| v = bystart[i] |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("consider %v: removed=%d\n", Nconv(v.node, obj.FmtSharp), v.removed) |
| } |
| |
| if v.removed != 0 { |
| continue |
| } |
| |
| // Expire no longer in use. |
| for ninuse > 0 && inuse[ninuse-1].end < v.start { |
| ninuse-- |
| v1 = inuse[ninuse] |
| nfree-- |
| inuse[nfree] = v1 |
| } |
| |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("consider %v: removed=%d nfree=%d nvar=%d\n", Nconv(v.node, obj.FmtSharp), v.removed, nfree, len(var_)) |
| } |
| |
| // Find old temp to reuse if possible. |
| t = v.node.Type |
| |
| for j = nfree; j < len(var_); j++ { |
| v1 = inuse[j] |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("consider %v: maybe %v: type=%v,%v addrtaken=%d,%d\n", Nconv(v.node, obj.FmtSharp), Nconv(v1.node, obj.FmtSharp), Tconv(t, 0), Tconv(v1.node.Type, 0), v.node.Addrtaken, v1.node.Addrtaken) |
| } |
| |
| // Require the types to match but also require the addrtaken bits to match. |
| // If a variable's address is taken, that disables registerization for the individual |
| // words of the variable (for example, the base,len,cap of a slice). |
| // We don't want to merge a non-addressed var with an addressed one and |
| // inhibit registerization of the former. |
| if Eqtype(t, v1.node.Type) && v.node.Addrtaken == v1.node.Addrtaken { |
| inuse[j] = inuse[nfree] |
| nfree++ |
| if v1.merge != nil { |
| v.merge = v1.merge |
| } else { |
| v.merge = v1 |
| } |
| nkill++ |
| break |
| } |
| } |
| |
| // Sort v into inuse. |
| j = ninuse |
| ninuse++ |
| |
| for j > 0 && inuse[j-1].end < v.end { |
| inuse[j] = inuse[j-1] |
| j-- |
| } |
| |
| inuse[j] = v |
| } |
| |
| if debugmerge > 0 && Debug['v'] != 0 { |
| fmt.Printf("%v [%d - %d]\n", Sconv(Curfn.Nname.Sym, 0), len(var_), nkill) |
| var v *TempVar |
| for i := 0; i < len(var_); i++ { |
| v = &var_[i] |
| fmt.Printf("var %v %v %d-%d", Nconv(v.node, obj.FmtSharp), Tconv(v.node.Type, 0), v.start, v.end) |
| if v.addr != 0 { |
| fmt.Printf(" addr=1") |
| } |
| if v.removed != 0 { |
| fmt.Printf(" dead=1") |
| } |
| if v.merge != nil { |
| fmt.Printf(" merge %v", Nconv(v.merge.node, obj.FmtSharp)) |
| } |
| if v.start == v.end && v.def != nil { |
| fmt.Printf(" %v", v.def.Prog) |
| } |
| fmt.Printf("\n") |
| } |
| |
| if debugmerge > 1 && Debug['v'] != 0 { |
| Dumpit("after", g.Start, 0) |
| } |
| } |
| |
| // Update node references to use merged temporaries. |
| for f := g.Start; f != nil; f = f.Link { |
| p = f.Prog |
| n, _ = p.From.Node.(*Node) |
| if n != nil { |
| v, _ = n.Opt.(*TempVar) |
| if v != nil && v.merge != nil { |
| p.From.Node = v.merge.node |
| } |
| } |
| n, _ = p.To.Node.(*Node) |
| if n != nil { |
| v, _ = n.Opt.(*TempVar) |
| if v != nil && v.merge != nil { |
| p.To.Node = v.merge.node |
| } |
| } |
| } |
| |
| // Delete merged nodes from declaration list. |
| var l *NodeList |
| for lp := &Curfn.Dcl; ; { |
| l = *lp |
| if l == nil { |
| break |
| } |
| |
| Curfn.Dcl.End = l |
| n = l.N |
| v, _ = n.Opt.(*TempVar) |
| if v != nil && (v.merge != nil || v.removed != 0) { |
| *lp = l.Next |
| continue |
| } |
| |
| lp = &l.Next |
| } |
| |
| // Clear aux structures. |
| for i := 0; i < len(var_); i++ { |
| var_[i].node.Opt = nil |
| } |
| |
| Flowend(g) |
| } |
| |
| func mergewalk(v *TempVar, f0 *Flow, gen uint32) { |
| var p *obj.Prog |
| var f1 *Flow |
| |
| for f1 = f0; f1 != nil; f1 = f1.P1 { |
| if uint32(f1.Active) == gen { |
| break |
| } |
| f1.Active = int32(gen) |
| p = f1.Prog |
| if v.end < p.Pc { |
| v.end = p.Pc |
| } |
| if f1 == v.def { |
| v.start = p.Pc |
| break |
| } |
| } |
| |
| var f2 *Flow |
| for f := f0; f != f1; f = f.P1 { |
| for f2 = f.P2; f2 != nil; f2 = f2.P2link { |
| mergewalk(v, f2, gen) |
| } |
| } |
| } |
| |
| func varkillwalk(v *TempVar, f0 *Flow, gen uint32) { |
| var p *obj.Prog |
| var f1 *Flow |
| |
| for f1 = f0; f1 != nil; f1 = f1.S1 { |
| if uint32(f1.Active) == gen { |
| break |
| } |
| f1.Active = int32(gen) |
| p = f1.Prog |
| if v.end < p.Pc { |
| v.end = p.Pc |
| } |
| if v.start > p.Pc { |
| v.start = p.Pc |
| } |
| if p.As == obj.ARET || (p.As == obj.AVARKILL && p.To.Node == v.node) { |
| break |
| } |
| } |
| |
| for f := f0; f != f1; f = f.S1 { |
| varkillwalk(v, f.S2, gen) |
| } |
| } |
| |
| // Eliminate redundant nil pointer checks. |
| // |
| // The code generation pass emits a CHECKNIL for every possibly nil pointer. |
| // This pass removes a CHECKNIL if every predecessor path has already |
| // checked this value for nil. |
| // |
| // Simple backwards flood from check to definition. |
| // Run prog loop backward from end of program to beginning to avoid quadratic |
| // behavior removing a run of checks. |
| // |
| // Assume that stack variables with address not taken can be loaded multiple times |
| // from memory without being rechecked. Other variables need to be checked on |
| // each load. |
| type NilVar struct { |
| } |
| |
| var killed int // f->data is either nil or &killed |
| |
| func nilopt(firstp *obj.Prog) { |
| g := Flowstart(firstp, nil) |
| if g == nil { |
| return |
| } |
| |
| if Debug_checknil > 1 { /* || strcmp(curfn->nname->sym->name, "f1") == 0 */ |
| Dumpit("nilopt", g.Start, 0) |
| } |
| |
| ncheck := 0 |
| nkill := 0 |
| var p *obj.Prog |
| for f := g.Start; f != nil; f = f.Link { |
| p = f.Prog |
| if p.As != obj.ACHECKNIL || !Thearch.Regtyp(&p.From) { |
| continue |
| } |
| ncheck++ |
| if Thearch.Stackaddr(&p.From) { |
| if Debug_checknil != 0 && p.Lineno > 1 { |
| Warnl(int(p.Lineno), "removed nil check of SP address") |
| } |
| f.Data = &killed |
| continue |
| } |
| |
| nilwalkfwd(f) |
| if f.Data != nil { |
| if Debug_checknil != 0 && p.Lineno > 1 { |
| Warnl(int(p.Lineno), "removed nil check before indirect") |
| } |
| continue |
| } |
| |
| nilwalkback(f) |
| if f.Data != nil { |
| if Debug_checknil != 0 && p.Lineno > 1 { |
| Warnl(int(p.Lineno), "removed repeated nil check") |
| } |
| continue |
| } |
| } |
| |
| for f := g.Start; f != nil; f = f.Link { |
| if f.Data != nil { |
| nkill++ |
| Thearch.Excise(f) |
| } |
| } |
| |
| Flowend(g) |
| |
| if Debug_checknil > 1 { |
| fmt.Printf("%v: removed %d of %d nil checks\n", Sconv(Curfn.Nname.Sym, 0), nkill, ncheck) |
| } |
| } |
| |
| func nilwalkback(fcheck *Flow) { |
| var p *obj.Prog |
| var info ProgInfo |
| |
| for f := fcheck; f != nil; f = Uniqp(f) { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| if (info.Flags&RightWrite != 0) && Thearch.Sameaddr(&p.To, &fcheck.Prog.From) { |
| // Found initialization of value we're checking for nil. |
| // without first finding the check, so this one is unchecked. |
| return |
| } |
| |
| if f != fcheck && p.As == obj.ACHECKNIL && Thearch.Sameaddr(&p.From, &fcheck.Prog.From) { |
| fcheck.Data = &killed |
| return |
| } |
| } |
| } |
| |
| // Here is a more complex version that scans backward across branches. |
| // It assumes fcheck->kill = 1 has been set on entry, and its job is to find a reason |
| // to keep the check (setting fcheck->kill = 0). |
| // It doesn't handle copying of aggregates as well as I would like, |
| // nor variables with their address taken, |
| // and it's too subtle to turn on this late in Go 1.2. Perhaps for Go 1.3. |
| /* |
| for(f1 = f0; f1 != nil; f1 = f1->p1) { |
| if(f1->active == gen) |
| break; |
| f1->active = gen; |
| p = f1->prog; |
| |
| // If same check, stop this loop but still check |
| // alternate predecessors up to this point. |
| if(f1 != fcheck && p->as == ACHECKNIL && thearch.sameaddr(&p->from, &fcheck->prog->from)) |
| break; |
| |
| thearch.proginfo(&info, p); |
| if((info.flags & RightWrite) && thearch.sameaddr(&p->to, &fcheck->prog->from)) { |
| // Found initialization of value we're checking for nil. |
| // without first finding the check, so this one is unchecked. |
| fcheck->kill = 0; |
| return; |
| } |
| |
| if(f1->p1 == nil && f1->p2 == nil) { |
| print("lost pred for %P\n", fcheck->prog); |
| for(f1=f0; f1!=nil; f1=f1->p1) { |
| thearch.proginfo(&info, f1->prog); |
| print("\t%P %d %d %D %D\n", r1->prog, info.flags&RightWrite, thearch.sameaddr(&f1->prog->to, &fcheck->prog->from), &f1->prog->to, &fcheck->prog->from); |
| } |
| fatal("lost pred trail"); |
| } |
| } |
| |
| for(f = f0; f != f1; f = f->p1) |
| for(f2 = f->p2; f2 != nil; f2 = f2->p2link) |
| nilwalkback(fcheck, f2, gen); |
| */ |
| func nilwalkfwd(fcheck *Flow) { |
| var p *obj.Prog |
| var info ProgInfo |
| |
| // If the path down from rcheck dereferences the address |
| // (possibly with a small offset) before writing to memory |
| // and before any subsequent checks, it's okay to wait for |
| // that implicit check. Only consider this basic block to |
| // avoid problems like: |
| // _ = *x // should panic |
| // for {} // no writes but infinite loop may be considered visible |
| last := (*Flow)(nil) |
| |
| for f := Uniqs(fcheck); f != nil; f = Uniqs(f) { |
| p = f.Prog |
| Thearch.Proginfo(&info, p) |
| |
| if (info.Flags&LeftRead != 0) && Thearch.Smallindir(&p.From, &fcheck.Prog.From) { |
| fcheck.Data = &killed |
| return |
| } |
| |
| if (info.Flags&(RightRead|RightWrite) != 0) && Thearch.Smallindir(&p.To, &fcheck.Prog.From) { |
| fcheck.Data = &killed |
| return |
| } |
| |
| // Stop if another nil check happens. |
| if p.As == obj.ACHECKNIL { |
| return |
| } |
| |
| // Stop if value is lost. |
| if (info.Flags&RightWrite != 0) && Thearch.Sameaddr(&p.To, &fcheck.Prog.From) { |
| return |
| } |
| |
| // Stop if memory write. |
| if (info.Flags&RightWrite != 0) && !Thearch.Regtyp(&p.To) { |
| return |
| } |
| |
| // Stop if we jump backward. |
| if last != nil && f.Id <= last.Id { |
| return |
| } |
| last = f |
| } |
| } |