loopreschedchecks.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssacompile
     6  
     7  import (
     8  	"fmt"
     9  
    10  	"cmd/compile/internal/ssa"
    11  	"cmd/compile/internal/ssa/block"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/compile/internal/types"
    14  )
    15  
    16  // an edgeMem records a backedge, together with the memory
    17  // phi functions at the target of the backedge that must
    18  // be updated when a rescheduling check replaces the backedge.
    19  type edgeMem struct {
    20  	e ssa.Edge
    21  	m *ssa.Value // phi for memory at dest of e
    22  }
    23  
    24  // a rewriteTarget is a value-argindex pair indicating
    25  // where a rewrite is applied.  Note that this is for values,
    26  // not for block controls, because block controls are not targets
    27  // for the rewrites performed in inserting rescheduling checks.
    28  type rewriteTarget struct {
    29  	v *ssa.Value
    30  	i int
    31  }
    32  
    33  type rewrite struct {
    34  	before, after *ssa.Value      // before is the expected value before rewrite, after is the new value installed.
    35  	rewrites      []rewriteTarget // all the targets for this rewrite.
    36  }
    37  
    38  func (r *rewrite) String() string {
    39  	s := "\n\tbefore=" + r.before.String() + ", after=" + r.after.String()
    40  	for _, rw := range r.rewrites {
    41  		s += ", (i=" + fmt.Sprint(rw.i) + ", v=" + rw.v.LongString() + ")"
    42  	}
    43  	s += "\n"
    44  	return s
    45  }
    46  
    47  // insertLoopReschedChecks inserts rescheduling checks on loop backedges.
    48  func insertLoopReschedChecks(f *ssa.Func) {
    49  	// TODO: when split information is recorded in export data, insert checks only on backedges that can be reached on a split-call-free path.
    50  
    51  	// Loop reschedule checks compare the stack pointer with
    52  	// the per-g stack bound.  If the pointer appears invalid,
    53  	// that means a reschedule check is needed.
    54  	//
    55  	// Steps:
    56  	// 1. locate backedges.
    57  	// 2. Record memory definitions at block end so that
    58  	//    the SSA graph for mem can be properly modified.
    59  	// 3. Ensure that phi functions that will-be-needed for mem
    60  	//    are present in the graph, initially with trivial inputs.
    61  	// 4. Record all to-be-modified uses of mem;
    62  	//    apply modifications (split into two steps to simplify and
    63  	//    avoided nagging order-dependencies).
    64  	// 5. Rewrite backedges to include reschedule check,
    65  	//    and modify destination phi function appropriately with new
    66  	//    definitions for mem.
    67  
    68  	if f.NoSplit { // nosplit functions don't reschedule.
    69  		return
    70  	}
    71  
    72  	backedges := backedges(f)
    73  	if len(backedges) == 0 { // no backedges means no rescheduling checks.
    74  		return
    75  	}
    76  
    77  	lastMems := findLastMems(f)
    78  	defer f.Cache.FreeValueSlice(lastMems)
    79  
    80  	idom := f.Idom()
    81  	po := f.Postorder()
    82  	sdom := f.Sdom()
    83  
    84  	if f.Pass.Debug > 1 {
    85  		fmt.Printf("before %s = %s\n", f.Name, sdom.Treestructure(f.Entry))
    86  	}
    87  
    88  	tofixBackedges := []edgeMem{}
    89  
    90  	for _, e := range backedges { // TODO: could filter here by calls in loops, if declared and inferred nosplit are recorded in export data.
    91  		tofixBackedges = append(tofixBackedges, edgeMem{e, nil})
    92  	}
    93  
    94  	// It's possible that there is no memory state (no global/pointer loads/stores or calls)
    95  	if lastMems[f.Entry.ID] == nil {
    96  		lastMems[f.Entry.ID] = f.Entry.NewValue0(f.Entry.Pos, ssaop.OpInitMem, types.TypeMem)
    97  	}
    98  
    99  	memDefsAtBlockEnds := f.Cache.AllocValueSlice(f.NumBlocks()) // For each block, the mem def seen at its bottom. Could be from earlier block.
   100  	defer f.Cache.FreeValueSlice(memDefsAtBlockEnds)
   101  
   102  	// Propagate last mem definitions forward through successor blocks.
   103  	for i := len(po) - 1; i >= 0; i-- {
   104  		b := po[i]
   105  		mem := lastMems[b.ID]
   106  		for j := 0; mem == nil; j++ { // if there's no def, then there's no phi, so the visible mem is identical in all predecessors.
   107  			// loop because there might be backedges that haven't been visited yet.
   108  			mem = memDefsAtBlockEnds[b.Preds[j].B.ID]
   109  		}
   110  		memDefsAtBlockEnds[b.ID] = mem
   111  		if f.Pass.Debug > 2 {
   112  			fmt.Printf("memDefsAtBlockEnds[%s] = %s\n", b, mem)
   113  		}
   114  	}
   115  
   116  	// Maps from block to newly-inserted phi function in block.
   117  	newmemphis := make(map[*ssa.Block]rewrite)
   118  
   119  	// Insert phi functions as necessary for future changes to flow graph.
   120  	for i, emc := range tofixBackedges {
   121  		e := emc.e
   122  		h := e.B
   123  
   124  		// find the phi function for the memory input at "h", if there is one.
   125  		var headerMemPhi *ssa.Value // look for header mem phi
   126  
   127  		for _, v := range h.Values {
   128  			if v.Op == ssaop.OpPhi && v.Type.IsMemory() {
   129  				headerMemPhi = v
   130  			}
   131  		}
   132  
   133  		if headerMemPhi == nil {
   134  			// if the header is nil, make a trivial phi from the dominator
   135  			mem0 := memDefsAtBlockEnds[idom[h.ID].ID]
   136  			headerMemPhi = newPhiFor(h, mem0)
   137  			newmemphis[h] = rewrite{before: mem0, after: headerMemPhi}
   138  			addDFphis(mem0, h, h, f, memDefsAtBlockEnds, newmemphis, sdom)
   139  
   140  		}
   141  		tofixBackedges[i].m = headerMemPhi
   142  
   143  	}
   144  	if f.Pass.Debug > 0 {
   145  		for b, r := range newmemphis {
   146  			fmt.Printf("before b=%s, rewrite=%s\n", b, r.String())
   147  		}
   148  	}
   149  
   150  	// dfPhiTargets notes inputs to phis in dominance frontiers that should not
   151  	// be rewritten as part of the dominated children of some outer rewrite.
   152  	dfPhiTargets := make(map[rewriteTarget]bool)
   153  
   154  	rewriteNewPhis(f.Entry, f.Entry, f, memDefsAtBlockEnds, newmemphis, dfPhiTargets, sdom)
   155  
   156  	if f.Pass.Debug > 0 {
   157  		for b, r := range newmemphis {
   158  			fmt.Printf("after b=%s, rewrite=%s\n", b, r.String())
   159  		}
   160  	}
   161  
   162  	// Apply collected rewrites.
   163  	for _, r := range newmemphis {
   164  		for _, rw := range r.rewrites {
   165  			rw.v.SetArg(rw.i, r.after)
   166  		}
   167  	}
   168  
   169  	// Rewrite backedges to include reschedule checks.
   170  	for _, emc := range tofixBackedges {
   171  		e := emc.e
   172  		headerMemPhi := emc.m
   173  		h := e.B
   174  		i := e.I
   175  		p := h.Preds[i]
   176  		bb := p.B
   177  		mem0 := headerMemPhi.Args[i]
   178  		// bb e->p h,
   179  		// Because we're going to insert a rare-call, make sure the
   180  		// looping edge still looks likely.
   181  		likely := ssa.BranchLikely
   182  		if p.I != 0 {
   183  			likely = ssa.BranchUnlikely
   184  		}
   185  		if bb.Kind != block.BlockPlain { // backedges can be unconditional. e.g., if x { something; continue }
   186  			bb.Likely = likely
   187  		}
   188  
   189  		// rewrite edge to include reschedule check
   190  		// existing edges:
   191  		//
   192  		// bb.Succs[p.i] == Edge{h, i}
   193  		// h.Preds[i] == p == Edge{bb,p.i}
   194  		//
   195  		// new block(s):
   196  		// test:
   197  		//    if sp < g.limit { goto sched }
   198  		//    goto join
   199  		// sched:
   200  		//    mem1 := call resched (mem0)
   201  		//    goto join
   202  		// join:
   203  		//    mem2 := phi(mem0, mem1)
   204  		//    goto h
   205  		//
   206  		// and correct arg i of headerMemPhi and headerCtrPhi
   207  		//
   208  		// EXCEPT: join block containing only phi functions is bad
   209  		// for the register allocator.  Therefore, there is no
   210  		// join, and branches targeting join must instead target
   211  		// the header, and the other phi functions within header are
   212  		// adjusted for the additional input.
   213  
   214  		test := f.NewBlock(block.BlockIf)
   215  		sched := f.NewBlock(block.BlockPlain)
   216  
   217  		test.Pos = bb.Pos
   218  		sched.Pos = bb.Pos
   219  
   220  		// if sp < g.limit { goto sched }
   221  		// goto header
   222  
   223  		cfgtypes := &f.Config.Types
   224  		pt := cfgtypes.Uintptr
   225  		g := test.NewValue1(bb.Pos, ssaop.OpGetG, pt, mem0)
   226  		sp := test.NewValue0(bb.Pos, ssaop.OpSP, pt)
   227  		cmpOp := ssaop.OpLess64U
   228  		if pt.Size() == 4 {
   229  			cmpOp = ssaop.OpLess32U
   230  		}
   231  		limaddr := test.NewValue1I(bb.Pos, ssaop.OpOffPtr, pt, 2*pt.Size(), g)
   232  		lim := test.NewValue2(bb.Pos, ssaop.OpLoad, pt, limaddr, mem0)
   233  		cmp := test.NewValue2(bb.Pos, cmpOp, cfgtypes.Bool, sp, lim)
   234  		test.SetControl(cmp)
   235  
   236  		// if true, goto sched
   237  		test.AddEdgeTo(sched)
   238  
   239  		// if false, rewrite edge to header.
   240  		// do NOT remove+add, because that will perturb all the other phi functions
   241  		// as well as messing up other edges to the header.
   242  		test.Succs = append(test.Succs, ssa.Edge{B: h, I: i})
   243  		h.Preds[i] = ssa.Edge{B: test, I: 1}
   244  		headerMemPhi.SetArg(i, mem0)
   245  
   246  		test.Likely = ssa.BranchUnlikely
   247  
   248  		// sched:
   249  		//    mem1 := call resched (mem0)
   250  		//    goto header
   251  		resched := f.Fe.Syslook("goschedguarded")
   252  		call := sched.NewValue1A(bb.Pos, ssaop.OpStaticCall, types.TypeResultMem, ssa.StaticAuxCall(resched, bb.Func.ABIDefault.ABIAnalyzeTypes(nil, nil)), mem0)
   253  		mem1 := sched.NewValue1I(bb.Pos, ssaop.OpSelectN, types.TypeMem, 0, call)
   254  		sched.AddEdgeTo(h)
   255  		headerMemPhi.AddArg(mem1)
   256  
   257  		bb.Succs[p.I] = ssa.Edge{B: test, I: 0}
   258  		test.Preds = append(test.Preds, ssa.Edge{B: bb, I: p.I})
   259  
   260  		// Must correct all the other phi functions in the header for new incoming edge.
   261  		// Except for mem phis, it will be the same value seen on the original
   262  		// backedge at index i.
   263  		for _, v := range h.Values {
   264  			if v.Op == ssaop.OpPhi && v != headerMemPhi {
   265  				v.AddArg(v.Args[i])
   266  			}
   267  		}
   268  	}
   269  
   270  	f.InvalidateCFG()
   271  
   272  	if f.Pass.Debug > 1 {
   273  		sdom = ssa.NewSparseTree(f, f.Idom())
   274  		fmt.Printf("after %s = %s\n", f.Name, sdom.Treestructure(f.Entry))
   275  	}
   276  }
   277  
   278  // newPhiFor inserts a new Phi function into b,
   279  // with all inputs set to v.
   280  func newPhiFor(b *ssa.Block, v *ssa.Value) *ssa.Value {
   281  	phiV := b.NewValue0(b.Pos, ssaop.OpPhi, v.Type)
   282  
   283  	for range b.Preds {
   284  		phiV.AddArg(v)
   285  	}
   286  	return phiV
   287  }
   288  
   289  // rewriteNewPhis updates newphis[h] to record all places where the new phi function inserted
   290  // in block h will replace a previous definition.  Block b is the block currently being processed;
   291  // if b has its own phi definition then it takes the place of h.
   292  // defsForUses provides information about other definitions of the variable that are present
   293  // (and if nil, indicates that the variable is no longer live)
   294  // sdom must yield a preorder of the flow graph if recursively walked, root-to-children.
   295  // The result of newSparseOrderedTree with order supplied by a dfs-postorder satisfies this
   296  // requirement.
   297  func rewriteNewPhis(h, b *ssa.Block, f *ssa.Func, defsForUses []*ssa.Value, newphis map[*ssa.Block]rewrite, dfPhiTargets map[rewriteTarget]bool, sdom ssa.SparseTree) {
   298  	// If b is a block with a new phi, then a new rewrite applies below it in the dominator tree.
   299  	if _, ok := newphis[b]; ok {
   300  		h = b
   301  	}
   302  	change := newphis[h]
   303  	x := change.before
   304  	y := change.after
   305  
   306  	// Apply rewrites to this block
   307  	if x != nil { // don't waste time on the common case of no definition.
   308  		p := &change.rewrites
   309  		for _, v := range b.Values {
   310  			if v == y { // don't rewrite self -- phi inputs are handled below.
   311  				continue
   312  			}
   313  			for i, w := range v.Args {
   314  				if w != x {
   315  					continue
   316  				}
   317  				tgt := rewriteTarget{v, i}
   318  
   319  				// It's possible dominated control flow will rewrite this instead.
   320  				// Visiting in preorder (a property of how sdom was constructed)
   321  				// ensures that these are seen in the proper order.
   322  				if dfPhiTargets[tgt] {
   323  					continue
   324  				}
   325  				*p = append(*p, tgt)
   326  				if f.Pass.Debug > 1 {
   327  					fmt.Printf("added block target for h=%v, b=%v, x=%v, y=%v, tgt.v=%s, tgt.i=%d\n",
   328  						h, b, x, y, v, i)
   329  				}
   330  			}
   331  		}
   332  
   333  		// Rewrite appropriate inputs of phis reached in successors
   334  		// in dominance frontier, self, and dominated.
   335  		// If the variable def reaching uses in b is itself defined in b, then the new phi function
   336  		// does not reach the successors of b.  (This assumes a bit about the structure of the
   337  		// phi use-def graph, but it's true for memory.)
   338  		if dfu := defsForUses[b.ID]; dfu != nil && dfu.Block != b {
   339  			for _, e := range b.Succs {
   340  				s := e.B
   341  
   342  				for _, v := range s.Values {
   343  					if v.Op == ssaop.OpPhi && v.Args[e.I] == x {
   344  						tgt := rewriteTarget{v, e.I}
   345  						*p = append(*p, tgt)
   346  						dfPhiTargets[tgt] = true
   347  						if f.Pass.Debug > 1 {
   348  							fmt.Printf("added phi target for h=%v, b=%v, s=%v, x=%v, y=%v, tgt.v=%s, tgt.i=%d\n",
   349  								h, b, s, x, y, v.LongString(), e.I)
   350  						}
   351  						break
   352  					}
   353  				}
   354  			}
   355  		}
   356  		newphis[h] = change
   357  	}
   358  
   359  	for c := sdom[b.ID].Child; c != nil; c = sdom[c.ID].Sibling {
   360  		rewriteNewPhis(h, c, f, defsForUses, newphis, dfPhiTargets, sdom) // TODO: convert to explicit stack from recursion.
   361  	}
   362  }
   363  
   364  // addDFphis creates new trivial phis that are necessary to correctly reflect (within SSA)
   365  // a new definition for variable "x" inserted at h (usually but not necessarily a phi).
   366  // These new phis can only occur at the dominance frontier of h; block s is in the dominance
   367  // frontier of h if h does not strictly dominate s and if s is a successor of a block b where
   368  // either b = h or h strictly dominates b.
   369  // These newly created phis are themselves new definitions that may require addition of their
   370  // own trivial phi functions in their own dominance frontier, and this is handled recursively.
   371  func addDFphis(x *ssa.Value, h, b *ssa.Block, f *ssa.Func, defForUses []*ssa.Value, newphis map[*ssa.Block]rewrite, sdom ssa.SparseTree) {
   372  	oldv := defForUses[b.ID]
   373  	if oldv != x { // either a new definition replacing x, or nil if it is proven that there are no uses reachable from b
   374  		return
   375  	}
   376  	idom := f.Idom()
   377  outer:
   378  	for _, e := range b.Succs {
   379  		s := e.B
   380  		// check phi functions in the dominance frontier
   381  		if sdom.IsAncestor(h, s) {
   382  			continue // h dominates s, successor of b, therefore s is not in the frontier.
   383  		}
   384  		if _, ok := newphis[s]; ok {
   385  			continue // successor s of b already has a new phi function, so there is no need to add another.
   386  		}
   387  		if x != nil {
   388  			for _, v := range s.Values {
   389  				if v.Op == ssaop.OpPhi && v.Args[e.I] == x {
   390  					continue outer // successor s of b has an old phi function, so there is no need to add another.
   391  				}
   392  			}
   393  		}
   394  
   395  		old := defForUses[idom[s.ID].ID] // new phi function is correct-but-redundant, combining value "old" on all inputs.
   396  		headerPhi := newPhiFor(s, old)
   397  		// the new phi will replace "old" in block s and all blocks dominated by s.
   398  		newphis[s] = rewrite{before: old, after: headerPhi} // record new phi, to have inputs labeled "old" rewritten to "headerPhi"
   399  		addDFphis(old, s, s, f, defForUses, newphis, sdom)  // the new definition may also create new phi functions.
   400  	}
   401  	for c := sdom[b.ID].Child; c != nil; c = sdom[c.ID].Sibling {
   402  		addDFphis(x, h, c, f, defForUses, newphis, sdom) // TODO: convert to explicit stack from recursion.
   403  	}
   404  }
   405  
   406  // findLastMems maps block ids to last memory-output op in a block, if any.
   407  func findLastMems(f *ssa.Func) []*ssa.Value {
   408  
   409  	var stores []*ssa.Value
   410  	lastMems := f.Cache.AllocValueSlice(f.NumBlocks())
   411  	storeUse := f.NewSparseSet(f.NumValues())
   412  	defer f.RetSparseSet(storeUse)
   413  	for _, b := range f.Blocks {
   414  		// Find all the stores in this block. Categorize their uses:
   415  		//  storeUse contains stores which are used by a subsequent store.
   416  		storeUse.Clear()
   417  		stores = stores[:0]
   418  		var memPhi *ssa.Value
   419  		for _, v := range b.Values {
   420  			if v.Op == ssaop.OpPhi {
   421  				if v.Type.IsMemory() {
   422  					memPhi = v
   423  				}
   424  				continue
   425  			}
   426  			if v.Type.IsMemory() {
   427  				stores = append(stores, v)
   428  				for _, a := range v.Args {
   429  					if a.Block == b && a.Type.IsMemory() {
   430  						storeUse.Add(a.ID)
   431  					}
   432  				}
   433  			}
   434  		}
   435  		if len(stores) == 0 {
   436  			lastMems[b.ID] = memPhi
   437  			continue
   438  		}
   439  
   440  		// find last store in the block
   441  		var last *ssa.Value
   442  		for _, v := range stores {
   443  			if storeUse.Contains(v.ID) {
   444  				continue
   445  			}
   446  			if last != nil {
   447  				b.Fatalf("two final stores - simultaneous live stores %s %s", last, v)
   448  			}
   449  			last = v
   450  		}
   451  		if last == nil {
   452  			b.Fatalf("no last store found - cycle?")
   453  		}
   454  
   455  		// If this is a tuple containing a mem, select just
   456  		// the mem. This will generate ops we don't need, but
   457  		// it's the easiest thing to do.
   458  		if last.Type.IsTuple() {
   459  			last = b.NewValue1(last.Pos, ssaop.OpSelect1, types.TypeMem, last)
   460  		} else if last.Type.IsResults() {
   461  			last = b.NewValue1I(last.Pos, ssaop.OpSelectN, types.TypeMem, int64(last.Type.NumFields()-1), last)
   462  		}
   463  
   464  		lastMems[b.ID] = last
   465  	}
   466  	return lastMems
   467  }
   468  
   469  // mark values
   470  type markKind uint8
   471  
   472  const (
   473  	notFound    markKind = iota // block has not been discovered yet
   474  	notExplored                 // discovered and in queue, outedges not processed yet
   475  	explored                    // discovered and in queue, outedges processed
   476  	done                        // all done, in output ordering
   477  )
   478  
   479  type backedgesState struct {
   480  	b *ssa.Block
   481  	i int
   482  }
   483  
   484  // backedges returns a slice of successor edges that are back
   485  // edges.  For reducible loops, edge.b is the header.
   486  func backedges(f *ssa.Func) []ssa.Edge {
   487  	edges := []ssa.Edge{}
   488  	mark := make([]markKind, f.NumBlocks())
   489  	stack := []backedgesState{}
   490  
   491  	mark[f.Entry.ID] = notExplored
   492  	stack = append(stack, backedgesState{f.Entry, 0})
   493  
   494  	for len(stack) > 0 {
   495  		l := len(stack)
   496  		x := stack[l-1]
   497  		if x.i < len(x.b.Succs) {
   498  			e := x.b.Succs[x.i]
   499  			stack[l-1].i++
   500  			s := e.B
   501  			if mark[s.ID] == notFound {
   502  				mark[s.ID] = notExplored
   503  				stack = append(stack, backedgesState{s, 0})
   504  			} else if mark[s.ID] == notExplored {
   505  				edges = append(edges, e)
   506  			}
   507  		} else {
   508  			mark[x.b.ID] = done
   509  			stack = stack[0 : l-1]
   510  		}
   511  	}
   512  	return edges
   513  }
   514
View as plain text