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