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