Source file src/pkg/cmd/compile/internal/ssa/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	
    75		idom := f.Idom()
    76		po := f.postorder()
    77		// The ordering in the dominator tree matters; it's important that
    78		// the walk of the dominator tree also be a preorder (i.e., a node is
    79		// visited only after all its non-backedge predecessors have been visited).
    80		sdom := newSparseOrderedTree(f, idom, po)
    81	
    82		if f.pass.debug > 1 {
    83			fmt.Printf("before %s = %s\n", f.Name, sdom.treestructure(f.Entry))
    84		}
    85	
    86		tofixBackedges := []edgeMem{}
    87	
    88		for _, e := range backedges { // TODO: could filter here by calls in loops, if declared and inferred nosplit are recorded in export data.
    89			tofixBackedges = append(tofixBackedges, edgeMem{e, nil})
    90		}
    91	
    92		// It's possible that there is no memory state (no global/pointer loads/stores or calls)
    93		if lastMems[f.Entry.ID] == nil {
    94			lastMems[f.Entry.ID] = f.Entry.NewValue0(f.Entry.Pos, OpInitMem, types.TypeMem)
    95		}
    96	
    97		memDefsAtBlockEnds := make([]*Value, f.NumBlocks()) // For each block, the mem def seen at its bottom. Could be from earlier block.
    98	
    99		// Propagate last mem definitions forward through successor blocks.
   100		for i := len(po) - 1; i >= 0; i-- {
   101			b := po[i]
   102			mem := lastMems[b.ID]
   103			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.
   104				// loop because there might be backedges that haven't been visited yet.
   105				mem = memDefsAtBlockEnds[b.Preds[j].b.ID]
   106			}
   107			memDefsAtBlockEnds[b.ID] = mem
   108			if f.pass.debug > 2 {
   109				fmt.Printf("memDefsAtBlockEnds[%s] = %s\n", b, mem)
   110			}
   111		}
   112	
   113		// Maps from block to newly-inserted phi function in block.
   114		newmemphis := make(map[*Block]rewrite)
   115	
   116		// Insert phi functions as necessary for future changes to flow graph.
   117		for i, emc := range tofixBackedges {
   118			e := emc.e
   119			h := e.b
   120	
   121			// find the phi function for the memory input at "h", if there is one.
   122			var headerMemPhi *Value // look for header mem phi
   123	
   124			for _, v := range h.Values {
   125				if v.Op == OpPhi && v.Type.IsMemory() {
   126					headerMemPhi = v
   127				}
   128			}
   129	
   130			if headerMemPhi == nil {
   131				// if the header is nil, make a trivial phi from the dominator
   132				mem0 := memDefsAtBlockEnds[idom[h.ID].ID]
   133				headerMemPhi = newPhiFor(h, mem0)
   134				newmemphis[h] = rewrite{before: mem0, after: headerMemPhi}
   135				addDFphis(mem0, h, h, f, memDefsAtBlockEnds, newmemphis, sdom)
   136	
   137			}
   138			tofixBackedges[i].m = headerMemPhi
   139	
   140		}
   141		if f.pass.debug > 0 {
   142			for b, r := range newmemphis {
   143				fmt.Printf("before b=%s, rewrite=%s\n", b, r.String())
   144			}
   145		}
   146	
   147		// dfPhiTargets notes inputs to phis in dominance frontiers that should not
   148		// be rewritten as part of the dominated children of some outer rewrite.
   149		dfPhiTargets := make(map[rewriteTarget]bool)
   150	
   151		rewriteNewPhis(f.Entry, f.Entry, f, memDefsAtBlockEnds, newmemphis, dfPhiTargets, sdom)
   152	
   153		if f.pass.debug > 0 {
   154			for b, r := range newmemphis {
   155				fmt.Printf("after b=%s, rewrite=%s\n", b, r.String())
   156			}
   157		}
   158	
   159		// Apply collected rewrites.
   160		for _, r := range newmemphis {
   161			for _, rw := range r.rewrites {
   162				rw.v.SetArg(rw.i, r.after)
   163			}
   164		}
   165	
   166		// Rewrite backedges to include reschedule checks.
   167		for _, emc := range tofixBackedges {
   168			e := emc.e
   169			headerMemPhi := emc.m
   170			h := e.b
   171			i := e.i
   172			p := h.Preds[i]
   173			bb := p.b
   174			mem0 := headerMemPhi.Args[i]
   175			// bb e->p h,
   176			// Because we're going to insert a rare-call, make sure the
   177			// looping edge still looks likely.
   178			likely := BranchLikely
   179			if p.i != 0 {
   180				likely = BranchUnlikely
   181			}
   182			if bb.Kind != BlockPlain { // backedges can be unconditional. e.g., if x { something; continue }
   183				bb.Likely = likely
   184			}
   185	
   186			// rewrite edge to include reschedule check
   187			// existing edges:
   188			//
   189			// bb.Succs[p.i] == Edge{h, i}
   190			// h.Preds[i] == p == Edge{bb,p.i}
   191			//
   192			// new block(s):
   193			// test:
   194			//    if sp < g.limit { goto sched }
   195			//    goto join
   196			// sched:
   197			//    mem1 := call resched (mem0)
   198			//    goto join
   199			// join:
   200			//    mem2 := phi(mem0, mem1)
   201			//    goto h
   202			//
   203			// and correct arg i of headerMemPhi and headerCtrPhi
   204			//
   205			// EXCEPT: join block containing only phi functions is bad
   206			// for the register allocator.  Therefore, there is no
   207			// join, and branches targeting join must instead target
   208			// the header, and the other phi functions within header are
   209			// adjusted for the additional input.
   210	
   211			test := f.NewBlock(BlockIf)
   212			sched := f.NewBlock(BlockPlain)
   213	
   214			test.Pos = bb.Pos
   215			sched.Pos = bb.Pos
   216	
   217			// if sp < g.limit { goto sched }
   218			// goto header
   219	
   220			cfgtypes := &f.Config.Types
   221			pt := cfgtypes.Uintptr
   222			g := test.NewValue1(bb.Pos, OpGetG, pt, mem0)
   223			sp := test.NewValue0(bb.Pos, OpSP, pt)
   224			cmpOp := OpLess64U
   225			if pt.Size() == 4 {
   226				cmpOp = OpLess32U
   227			}
   228			limaddr := test.NewValue1I(bb.Pos, OpOffPtr, pt, 2*pt.Size(), g)
   229			lim := test.NewValue2(bb.Pos, OpLoad, pt, limaddr, mem0)
   230			cmp := test.NewValue2(bb.Pos, cmpOp, cfgtypes.Bool, sp, lim)
   231			test.SetControl(cmp)
   232	
   233			// if true, goto sched
   234			test.AddEdgeTo(sched)
   235	
   236			// if false, rewrite edge to header.
   237			// do NOT remove+add, because that will perturb all the other phi functions
   238			// as well as messing up other edges to the header.
   239			test.Succs = append(test.Succs, Edge{h, i})
   240			h.Preds[i] = Edge{test, 1}
   241			headerMemPhi.SetArg(i, mem0)
   242	
   243			test.Likely = BranchUnlikely
   244	
   245			// sched:
   246			//    mem1 := call resched (mem0)
   247			//    goto header
   248			resched := f.fe.Syslook("goschedguarded")
   249			mem1 := sched.NewValue1A(bb.Pos, OpStaticCall, types.TypeMem, resched, mem0)
   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 := make([]*Value, 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			lastMems[b.ID] = last
   451		}
   452		return lastMems
   453	}
   454	
   455	type backedgesState struct {
   456		b *Block
   457		i int
   458	}
   459	
   460	// backedges returns a slice of successor edges that are back
   461	// edges.  For reducible loops, edge.b is the header.
   462	func backedges(f *Func) []Edge {
   463		edges := []Edge{}
   464		mark := make([]markKind, f.NumBlocks())
   465		stack := []backedgesState{}
   466	
   467		mark[f.Entry.ID] = notExplored
   468		stack = append(stack, backedgesState{f.Entry, 0})
   469	
   470		for len(stack) > 0 {
   471			l := len(stack)
   472			x := stack[l-1]
   473			if x.i < len(x.b.Succs) {
   474				e := x.b.Succs[x.i]
   475				stack[l-1].i++
   476				s := e.b
   477				if mark[s.ID] == notFound {
   478					mark[s.ID] = notExplored
   479					stack = append(stack, backedgesState{s, 0})
   480				} else if mark[s.ID] == notExplored {
   481					edges = append(edges, e)
   482				}
   483			} else {
   484				mark[x.b.ID] = done
   485				stack = stack[0 : l-1]
   486			}
   487		}
   488		return edges
   489	}
   490	

View as plain text