Source file src/pkg/cmd/compile/internal/gc/phi.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 gc
     6	
     7	import (
     8		"cmd/compile/internal/ssa"
     9		"cmd/compile/internal/types"
    10		"cmd/internal/src"
    11		"container/heap"
    12		"fmt"
    13	)
    14	
    15	// This file contains the algorithm to place phi nodes in a function.
    16	// For small functions, we use Braun, Buchwald, Hack, Leißa, Mallon, and Zwinkau.
    17	// https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
    18	// For large functions, we use Sreedhar & Gao: A Linear Time Algorithm for Placing Φ-Nodes.
    19	// http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.1979&rep=rep1&type=pdf
    20	
    21	const smallBlocks = 500
    22	
    23	const debugPhi = false
    24	
    25	// insertPhis finds all the places in the function where a phi is
    26	// necessary and inserts them.
    27	// Uses FwdRef ops to find all uses of variables, and s.defvars to find
    28	// all definitions.
    29	// Phi values are inserted, and all FwdRefs are changed to a Copy
    30	// of the appropriate phi or definition.
    31	// TODO: make this part of cmd/compile/internal/ssa somehow?
    32	func (s *state) insertPhis() {
    33		if len(s.f.Blocks) <= smallBlocks {
    34			sps := simplePhiState{s: s, f: s.f, defvars: s.defvars}
    35			sps.insertPhis()
    36			return
    37		}
    38		ps := phiState{s: s, f: s.f, defvars: s.defvars}
    39		ps.insertPhis()
    40	}
    41	
    42	type phiState struct {
    43		s       *state                 // SSA state
    44		f       *ssa.Func              // function to work on
    45		defvars []map[*Node]*ssa.Value // defined variables at end of each block
    46	
    47		varnum map[*Node]int32 // variable numbering
    48	
    49		// properties of the dominator tree
    50		idom  []*ssa.Block // dominator parents
    51		tree  []domBlock   // dominator child+sibling
    52		level []int32      // level in dominator tree (0 = root or unreachable, 1 = children of root, ...)
    53	
    54		// scratch locations
    55		priq   blockHeap    // priority queue of blocks, higher level (toward leaves) = higher priority
    56		q      []*ssa.Block // inner loop queue
    57		queued *sparseSet   // has been put in q
    58		hasPhi *sparseSet   // has a phi
    59		hasDef *sparseSet   // has a write of the variable we're processing
    60	
    61		// miscellaneous
    62		placeholder *ssa.Value // dummy value to use as a "not set yet" placeholder.
    63	}
    64	
    65	func (s *phiState) insertPhis() {
    66		if debugPhi {
    67			fmt.Println(s.f.String())
    68		}
    69	
    70		// Find all the variables for which we need to match up reads & writes.
    71		// This step prunes any basic-block-only variables from consideration.
    72		// Generate a numbering for these variables.
    73		s.varnum = map[*Node]int32{}
    74		var vars []*Node
    75		var vartypes []*types.Type
    76		for _, b := range s.f.Blocks {
    77			for _, v := range b.Values {
    78				if v.Op != ssa.OpFwdRef {
    79					continue
    80				}
    81				var_ := v.Aux.(*Node)
    82	
    83				// Optimization: look back 1 block for the definition.
    84				if len(b.Preds) == 1 {
    85					c := b.Preds[0].Block()
    86					if w := s.defvars[c.ID][var_]; w != nil {
    87						v.Op = ssa.OpCopy
    88						v.Aux = nil
    89						v.AddArg(w)
    90						continue
    91					}
    92				}
    93	
    94				if _, ok := s.varnum[var_]; ok {
    95					continue
    96				}
    97				s.varnum[var_] = int32(len(vartypes))
    98				if debugPhi {
    99					fmt.Printf("var%d = %v\n", len(vartypes), var_)
   100				}
   101				vars = append(vars, var_)
   102				vartypes = append(vartypes, v.Type)
   103			}
   104		}
   105	
   106		if len(vartypes) == 0 {
   107			return
   108		}
   109	
   110		// Find all definitions of the variables we need to process.
   111		// defs[n] contains all the blocks in which variable number n is assigned.
   112		defs := make([][]*ssa.Block, len(vartypes))
   113		for _, b := range s.f.Blocks {
   114			for var_ := range s.defvars[b.ID] { // TODO: encode defvars some other way (explicit ops)? make defvars[n] a slice instead of a map.
   115				if n, ok := s.varnum[var_]; ok {
   116					defs[n] = append(defs[n], b)
   117				}
   118			}
   119		}
   120	
   121		// Make dominator tree.
   122		s.idom = s.f.Idom()
   123		s.tree = make([]domBlock, s.f.NumBlocks())
   124		for _, b := range s.f.Blocks {
   125			p := s.idom[b.ID]
   126			if p != nil {
   127				s.tree[b.ID].sibling = s.tree[p.ID].firstChild
   128				s.tree[p.ID].firstChild = b
   129			}
   130		}
   131		// Compute levels in dominator tree.
   132		// With parent pointers we can do a depth-first walk without
   133		// any auxiliary storage.
   134		s.level = make([]int32, s.f.NumBlocks())
   135		b := s.f.Entry
   136	levels:
   137		for {
   138			if p := s.idom[b.ID]; p != nil {
   139				s.level[b.ID] = s.level[p.ID] + 1
   140				if debugPhi {
   141					fmt.Printf("level %s = %d\n", b, s.level[b.ID])
   142				}
   143			}
   144			if c := s.tree[b.ID].firstChild; c != nil {
   145				b = c
   146				continue
   147			}
   148			for {
   149				if c := s.tree[b.ID].sibling; c != nil {
   150					b = c
   151					continue levels
   152				}
   153				b = s.idom[b.ID]
   154				if b == nil {
   155					break levels
   156				}
   157			}
   158		}
   159	
   160		// Allocate scratch locations.
   161		s.priq.level = s.level
   162		s.q = make([]*ssa.Block, 0, s.f.NumBlocks())
   163		s.queued = newSparseSet(s.f.NumBlocks())
   164		s.hasPhi = newSparseSet(s.f.NumBlocks())
   165		s.hasDef = newSparseSet(s.f.NumBlocks())
   166		s.placeholder = s.s.entryNewValue0(ssa.OpUnknown, types.TypeInvalid)
   167	
   168		// Generate phi ops for each variable.
   169		for n := range vartypes {
   170			s.insertVarPhis(n, vars[n], defs[n], vartypes[n])
   171		}
   172	
   173		// Resolve FwdRefs to the correct write or phi.
   174		s.resolveFwdRefs()
   175	
   176		// Erase variable numbers stored in AuxInt fields of phi ops. They are no longer needed.
   177		for _, b := range s.f.Blocks {
   178			for _, v := range b.Values {
   179				if v.Op == ssa.OpPhi {
   180					v.AuxInt = 0
   181				}
   182			}
   183		}
   184	}
   185	
   186	func (s *phiState) insertVarPhis(n int, var_ *Node, defs []*ssa.Block, typ *types.Type) {
   187		priq := &s.priq
   188		q := s.q
   189		queued := s.queued
   190		queued.clear()
   191		hasPhi := s.hasPhi
   192		hasPhi.clear()
   193		hasDef := s.hasDef
   194		hasDef.clear()
   195	
   196		// Add defining blocks to priority queue.
   197		for _, b := range defs {
   198			priq.a = append(priq.a, b)
   199			hasDef.add(b.ID)
   200			if debugPhi {
   201				fmt.Printf("def of var%d in %s\n", n, b)
   202			}
   203		}
   204		heap.Init(priq)
   205	
   206		// Visit blocks defining variable n, from deepest to shallowest.
   207		for len(priq.a) > 0 {
   208			currentRoot := heap.Pop(priq).(*ssa.Block)
   209			if debugPhi {
   210				fmt.Printf("currentRoot %s\n", currentRoot)
   211			}
   212			// Walk subtree below definition.
   213			// Skip subtrees we've done in previous iterations.
   214			// Find edges exiting tree dominated by definition (the dominance frontier).
   215			// Insert phis at target blocks.
   216			if queued.contains(currentRoot.ID) {
   217				s.s.Fatalf("root already in queue")
   218			}
   219			q = append(q, currentRoot)
   220			queued.add(currentRoot.ID)
   221			for len(q) > 0 {
   222				b := q[len(q)-1]
   223				q = q[:len(q)-1]
   224				if debugPhi {
   225					fmt.Printf("  processing %s\n", b)
   226				}
   227	
   228				currentRootLevel := s.level[currentRoot.ID]
   229				for _, e := range b.Succs {
   230					c := e.Block()
   231					// TODO: if the variable is dead at c, skip it.
   232					if s.level[c.ID] > currentRootLevel {
   233						// a D-edge, or an edge whose target is in currentRoot's subtree.
   234						continue
   235					}
   236					if hasPhi.contains(c.ID) {
   237						continue
   238					}
   239					// Add a phi to block c for variable n.
   240					hasPhi.add(c.ID)
   241					v := c.NewValue0I(currentRoot.Pos, ssa.OpPhi, typ, int64(n)) // TODO: line number right?
   242					// Note: we store the variable number in the phi's AuxInt field. Used temporarily by phi building.
   243					s.s.addNamedValue(var_, v)
   244					for range c.Preds {
   245						v.AddArg(s.placeholder) // Actual args will be filled in by resolveFwdRefs.
   246					}
   247					if debugPhi {
   248						fmt.Printf("new phi for var%d in %s: %s\n", n, c, v)
   249					}
   250					if !hasDef.contains(c.ID) {
   251						// There's now a new definition of this variable in block c.
   252						// Add it to the priority queue to explore.
   253						heap.Push(priq, c)
   254						hasDef.add(c.ID)
   255					}
   256				}
   257	
   258				// Visit children if they have not been visited yet.
   259				for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
   260					if !queued.contains(c.ID) {
   261						q = append(q, c)
   262						queued.add(c.ID)
   263					}
   264				}
   265			}
   266		}
   267	}
   268	
   269	// resolveFwdRefs links all FwdRef uses up to their nearest dominating definition.
   270	func (s *phiState) resolveFwdRefs() {
   271		// Do a depth-first walk of the dominator tree, keeping track
   272		// of the most-recently-seen value for each variable.
   273	
   274		// Map from variable ID to SSA value at the current point of the walk.
   275		values := make([]*ssa.Value, len(s.varnum))
   276		for i := range values {
   277			values[i] = s.placeholder
   278		}
   279	
   280		// Stack of work to do.
   281		type stackEntry struct {
   282			b *ssa.Block // block to explore
   283	
   284			// variable/value pair to reinstate on exit
   285			n int32 // variable ID
   286			v *ssa.Value
   287	
   288			// Note: only one of b or n,v will be set.
   289		}
   290		var stk []stackEntry
   291	
   292		stk = append(stk, stackEntry{b: s.f.Entry})
   293		for len(stk) > 0 {
   294			work := stk[len(stk)-1]
   295			stk = stk[:len(stk)-1]
   296	
   297			b := work.b
   298			if b == nil {
   299				// On exit from a block, this case will undo any assignments done below.
   300				values[work.n] = work.v
   301				continue
   302			}
   303	
   304			// Process phis as new defs. They come before FwdRefs in this block.
   305			for _, v := range b.Values {
   306				if v.Op != ssa.OpPhi {
   307					continue
   308				}
   309				n := int32(v.AuxInt)
   310				// Remember the old assignment so we can undo it when we exit b.
   311				stk = append(stk, stackEntry{n: n, v: values[n]})
   312				// Record the new assignment.
   313				values[n] = v
   314			}
   315	
   316			// Replace a FwdRef op with the current incoming value for its variable.
   317			for _, v := range b.Values {
   318				if v.Op != ssa.OpFwdRef {
   319					continue
   320				}
   321				n := s.varnum[v.Aux.(*Node)]
   322				v.Op = ssa.OpCopy
   323				v.Aux = nil
   324				v.AddArg(values[n])
   325			}
   326	
   327			// Establish values for variables defined in b.
   328			for var_, v := range s.defvars[b.ID] {
   329				n, ok := s.varnum[var_]
   330				if !ok {
   331					// some variable not live across a basic block boundary.
   332					continue
   333				}
   334				// Remember the old assignment so we can undo it when we exit b.
   335				stk = append(stk, stackEntry{n: n, v: values[n]})
   336				// Record the new assignment.
   337				values[n] = v
   338			}
   339	
   340			// Replace phi args in successors with the current incoming value.
   341			for _, e := range b.Succs {
   342				c, i := e.Block(), e.Index()
   343				for j := len(c.Values) - 1; j >= 0; j-- {
   344					v := c.Values[j]
   345					if v.Op != ssa.OpPhi {
   346						break // All phis will be at the end of the block during phi building.
   347					}
   348					// Only set arguments that have been resolved.
   349					// For very wide CFGs, this significantly speeds up phi resolution.
   350					// See golang.org/issue/8225.
   351					if w := values[v.AuxInt]; w.Op != ssa.OpUnknown {
   352						v.SetArg(i, w)
   353					}
   354				}
   355			}
   356	
   357			// Walk children in dominator tree.
   358			for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
   359				stk = append(stk, stackEntry{b: c})
   360			}
   361		}
   362	}
   363	
   364	// domBlock contains extra per-block information to record the dominator tree.
   365	type domBlock struct {
   366		firstChild *ssa.Block // first child of block in dominator tree
   367		sibling    *ssa.Block // next child of parent in dominator tree
   368	}
   369	
   370	// A block heap is used as a priority queue to implement the PiggyBank
   371	// from Sreedhar and Gao.  That paper uses an array which is better
   372	// asymptotically but worse in the common case when the PiggyBank
   373	// holds a sparse set of blocks.
   374	type blockHeap struct {
   375		a     []*ssa.Block // block IDs in heap
   376		level []int32      // depth in dominator tree (static, used for determining priority)
   377	}
   378	
   379	func (h *blockHeap) Len() int      { return len(h.a) }
   380	func (h *blockHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }
   381	
   382	func (h *blockHeap) Push(x interface{}) {
   383		v := x.(*ssa.Block)
   384		h.a = append(h.a, v)
   385	}
   386	func (h *blockHeap) Pop() interface{} {
   387		old := h.a
   388		n := len(old)
   389		x := old[n-1]
   390		h.a = old[:n-1]
   391		return x
   392	}
   393	func (h *blockHeap) Less(i, j int) bool {
   394		return h.level[h.a[i].ID] > h.level[h.a[j].ID]
   395	}
   396	
   397	// TODO: stop walking the iterated domininance frontier when
   398	// the variable is dead. Maybe detect that by checking if the
   399	// node we're on is reverse dominated by all the reads?
   400	// Reverse dominated by the highest common successor of all the reads?
   401	
   402	// copy of ../ssa/sparseset.go
   403	// TODO: move this file to ../ssa, then use sparseSet there.
   404	type sparseSet struct {
   405		dense  []ssa.ID
   406		sparse []int32
   407	}
   408	
   409	// newSparseSet returns a sparseSet that can represent
   410	// integers between 0 and n-1
   411	func newSparseSet(n int) *sparseSet {
   412		return &sparseSet{dense: nil, sparse: make([]int32, n)}
   413	}
   414	
   415	func (s *sparseSet) contains(x ssa.ID) bool {
   416		i := s.sparse[x]
   417		return i < int32(len(s.dense)) && s.dense[i] == x
   418	}
   419	
   420	func (s *sparseSet) add(x ssa.ID) {
   421		i := s.sparse[x]
   422		if i < int32(len(s.dense)) && s.dense[i] == x {
   423			return
   424		}
   425		s.dense = append(s.dense, x)
   426		s.sparse[x] = int32(len(s.dense)) - 1
   427	}
   428	
   429	func (s *sparseSet) clear() {
   430		s.dense = s.dense[:0]
   431	}
   432	
   433	// Variant to use for small functions.
   434	type simplePhiState struct {
   435		s         *state                 // SSA state
   436		f         *ssa.Func              // function to work on
   437		fwdrefs   []*ssa.Value           // list of FwdRefs to be processed
   438		defvars   []map[*Node]*ssa.Value // defined variables at end of each block
   439		reachable []bool                 // which blocks are reachable
   440	}
   441	
   442	func (s *simplePhiState) insertPhis() {
   443		s.reachable = ssa.ReachableBlocks(s.f)
   444	
   445		// Find FwdRef ops.
   446		for _, b := range s.f.Blocks {
   447			for _, v := range b.Values {
   448				if v.Op != ssa.OpFwdRef {
   449					continue
   450				}
   451				s.fwdrefs = append(s.fwdrefs, v)
   452				var_ := v.Aux.(*Node)
   453				if _, ok := s.defvars[b.ID][var_]; !ok {
   454					s.defvars[b.ID][var_] = v // treat FwdDefs as definitions.
   455				}
   456			}
   457		}
   458	
   459		var args []*ssa.Value
   460	
   461	loop:
   462		for len(s.fwdrefs) > 0 {
   463			v := s.fwdrefs[len(s.fwdrefs)-1]
   464			s.fwdrefs = s.fwdrefs[:len(s.fwdrefs)-1]
   465			b := v.Block
   466			var_ := v.Aux.(*Node)
   467			if b == s.f.Entry {
   468				// No variable should be live at entry.
   469				s.s.Fatalf("Value live at entry. It shouldn't be. func %s, node %v, value %v", s.f.Name, var_, v)
   470			}
   471			if !s.reachable[b.ID] {
   472				// This block is dead.
   473				// It doesn't matter what we use here as long as it is well-formed.
   474				v.Op = ssa.OpUnknown
   475				v.Aux = nil
   476				continue
   477			}
   478			// Find variable value on each predecessor.
   479			args = args[:0]
   480			for _, e := range b.Preds {
   481				args = append(args, s.lookupVarOutgoing(e.Block(), v.Type, var_, v.Pos))
   482			}
   483	
   484			// Decide if we need a phi or not. We need a phi if there
   485			// are two different args (which are both not v).
   486			var w *ssa.Value
   487			for _, a := range args {
   488				if a == v {
   489					continue // self-reference
   490				}
   491				if a == w {
   492					continue // already have this witness
   493				}
   494				if w != nil {
   495					// two witnesses, need a phi value
   496					v.Op = ssa.OpPhi
   497					v.AddArgs(args...)
   498					v.Aux = nil
   499					continue loop
   500				}
   501				w = a // save witness
   502			}
   503			if w == nil {
   504				s.s.Fatalf("no witness for reachable phi %s", v)
   505			}
   506			// One witness. Make v a copy of w.
   507			v.Op = ssa.OpCopy
   508			v.Aux = nil
   509			v.AddArg(w)
   510		}
   511	}
   512	
   513	// lookupVarOutgoing finds the variable's value at the end of block b.
   514	func (s *simplePhiState) lookupVarOutgoing(b *ssa.Block, t *types.Type, var_ *Node, line src.XPos) *ssa.Value {
   515		for {
   516			if v := s.defvars[b.ID][var_]; v != nil {
   517				return v
   518			}
   519			// The variable is not defined by b and we haven't looked it up yet.
   520			// If b has exactly one predecessor, loop to look it up there.
   521			// Otherwise, give up and insert a new FwdRef and resolve it later.
   522			if len(b.Preds) != 1 {
   523				break
   524			}
   525			b = b.Preds[0].Block()
   526			if !s.reachable[b.ID] {
   527				// This is rare; it happens with oddly interleaved infinite loops in dead code.
   528				// See issue 19783.
   529				break
   530			}
   531		}
   532		// Generate a FwdRef for the variable and return that.
   533		v := b.NewValue0A(line, ssa.OpFwdRef, t, var_)
   534		s.defvars[b.ID][var_] = v
   535		s.s.addNamedValue(var_, v)
   536		s.fwdrefs = append(s.fwdrefs, v)
   537		return v
   538	}
   539	

View as plain text