flagalloc.go

     1  // Copyright 2015 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  	"cmd/compile/internal/ssa"
     9  	"cmd/compile/internal/ssa/block"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  )
    12  
    13  // flagalloc allocates the flag register among all the flag-generating
    14  // instructions. Flag values are recomputed if they need to be
    15  // spilled/restored.
    16  func flagalloc(f *ssa.Func) {
    17  	// Compute the in-register flag value we want at the end of
    18  	// each block. This is basically a best-effort live variable
    19  	// analysis, so it can be much simpler than a full analysis.
    20  	end := f.Cache.AllocValueSlice(f.NumBlocks())
    21  	defer f.Cache.FreeValueSlice(end)
    22  	po := f.Postorder()
    23  	for n := 0; n < 2; n++ {
    24  		for _, b := range po {
    25  			// Walk values backwards to figure out what flag
    26  			// value we want in the flag register at the start
    27  			// of the block.
    28  			var flag *ssa.Value
    29  			for _, c := range b.ControlValues() {
    30  				if c.Type.IsFlags() {
    31  					if flag != nil {
    32  						panic("cannot have multiple controls using flags")
    33  					}
    34  					flag = c
    35  				}
    36  			}
    37  			if flag == nil {
    38  				flag = end[b.ID]
    39  			}
    40  			for j := len(b.Values) - 1; j >= 0; j-- {
    41  				v := b.Values[j]
    42  				if v == flag {
    43  					flag = nil
    44  				}
    45  				if v.ClobbersFlags() {
    46  					flag = nil
    47  				}
    48  				for _, a := range v.Args {
    49  					if a.Type.IsFlags() {
    50  						flag = a
    51  					}
    52  				}
    53  			}
    54  			if flag != nil {
    55  				for _, e := range b.Preds {
    56  					p := e.B
    57  					end[p.ID] = flag
    58  				}
    59  			}
    60  		}
    61  	}
    62  
    63  	// For blocks which have a flags control value, that's the only value
    64  	// we can leave in the flags register at the end of the block. (There
    65  	// is no place to put a flag regeneration instruction.)
    66  	for _, b := range f.Blocks {
    67  		if b.Kind == block.BlockDefer {
    68  			// Defer blocks internally use/clobber the flags value.
    69  			end[b.ID] = nil
    70  			continue
    71  		}
    72  		for _, v := range b.ControlValues() {
    73  			if v.Type.IsFlags() && end[b.ID] != v {
    74  				end[b.ID] = nil
    75  			}
    76  		}
    77  	}
    78  
    79  	// Compute which flags values will need to be spilled.
    80  	spill := map[ssa.ID]bool{}
    81  	for _, b := range f.Blocks {
    82  		var flag *ssa.Value
    83  		if len(b.Preds) > 0 {
    84  			flag = end[b.Preds[0].B.ID]
    85  		}
    86  		for _, v := range b.Values {
    87  			for _, a := range v.Args {
    88  				if !a.Type.IsFlags() {
    89  					continue
    90  				}
    91  				if a == flag {
    92  					continue
    93  				}
    94  				// a will need to be restored here.
    95  				spill[a.ID] = true
    96  				flag = a
    97  			}
    98  			if v.ClobbersFlags() {
    99  				flag = nil
   100  			}
   101  			if v.Type.IsFlags() {
   102  				flag = v
   103  			}
   104  		}
   105  		for _, v := range b.ControlValues() {
   106  			if v != flag && v.Type.IsFlags() {
   107  				spill[v.ID] = true
   108  			}
   109  		}
   110  		if v := end[b.ID]; v != nil && v != flag {
   111  			spill[v.ID] = true
   112  		}
   113  	}
   114  
   115  	// Add flag spill and recomputation where they are needed.
   116  	var remove []*ssa.Value // values that should be checked for possible removal
   117  	var oldSched []*ssa.Value
   118  	for _, b := range f.Blocks {
   119  		oldSched = append(oldSched[:0], b.Values...)
   120  		b.Values = b.Values[:0]
   121  		// The current live flag value (the pre-flagalloc copy).
   122  		var flag *ssa.Value
   123  		if len(b.Preds) > 0 {
   124  			flag = end[b.Preds[0].B.ID]
   125  			// Note: the following condition depends on the lack of critical edges.
   126  			for _, e := range b.Preds[1:] {
   127  				p := e.B
   128  				if end[p.ID] != flag {
   129  					f.Fatalf("live flag in %s's predecessors not consistent", b)
   130  				}
   131  			}
   132  		}
   133  		for _, v := range oldSched {
   134  			if v.Op == ssaop.OpPhi && v.Type.IsFlags() {
   135  				f.Fatalf("phi of flags not supported: %s", v.LongString())
   136  			}
   137  
   138  			// If v will be spilled, and v uses memory, then we must split it
   139  			// into a load + a flag generator.
   140  			if spill[v.ID] && v.MemoryArg() != nil {
   141  				remove = append(remove, v)
   142  				if !f.Config.SplitLoad(v) {
   143  					f.Fatalf("can't split flag generator: %s", v.LongString())
   144  				}
   145  			}
   146  
   147  			// Make sure any flag arg of v is in the flags register.
   148  			// If not, recompute it.
   149  			for i, a := range v.Args {
   150  				if !a.Type.IsFlags() {
   151  					continue
   152  				}
   153  				if a == flag {
   154  					continue
   155  				}
   156  				// Recalculate a
   157  				c := copyFlags(a, b)
   158  				// Update v.
   159  				v.SetArg(i, c)
   160  				// Remember the most-recently computed flag value.
   161  				flag = a
   162  			}
   163  			// Issue v.
   164  			b.Values = append(b.Values, v)
   165  			if v.ClobbersFlags() {
   166  				flag = nil
   167  			}
   168  			if v.Type.IsFlags() {
   169  				flag = v
   170  			}
   171  		}
   172  		for i, v := range b.ControlValues() {
   173  			if v != flag && v.Type.IsFlags() {
   174  				// Recalculate control value.
   175  				remove = append(remove, v)
   176  				c := copyFlags(v, b)
   177  				b.ReplaceControl(i, c)
   178  				flag = v
   179  			}
   180  		}
   181  		if v := end[b.ID]; v != nil && v != flag {
   182  			// Need to reissue flag generator for use by
   183  			// subsequent blocks.
   184  			remove = append(remove, v)
   185  			copyFlags(v, b)
   186  			// Note: this flag generator is not properly linked up
   187  			// with the flag users. This breaks the SSA representation.
   188  			// We could fix up the users with another pass, but for now
   189  			// we'll just leave it. (Regalloc has the same issue for
   190  			// standard regs, and it runs next.)
   191  			// For this reason, take care not to add this flag
   192  			// generator to the remove list.
   193  		}
   194  	}
   195  
   196  	// Save live flag state for later.
   197  	for _, b := range f.Blocks {
   198  		b.FlagsLiveAtEnd = end[b.ID] != nil
   199  	}
   200  
   201  	// Remove any now-dead values.
   202  	// The number of values to remove is likely small,
   203  	// and removing them requires processing all values in a block,
   204  	// so minimize the number of blocks that we touch.
   205  
   206  	// Shrink remove to contain only dead values, and clobber those dead values.
   207  	for i := 0; i < len(remove); i++ {
   208  		v := remove[i]
   209  		if v.Uses == 0 {
   210  			v.Reset(ssaop.OpInvalid)
   211  			continue
   212  		}
   213  		// Remove v.
   214  		last := len(remove) - 1
   215  		remove[i] = remove[last]
   216  		remove[last] = nil
   217  		remove = remove[:last]
   218  		i-- // reprocess value at i
   219  	}
   220  
   221  	if len(remove) == 0 {
   222  		return
   223  	}
   224  
   225  	removeBlocks := f.NewSparseSet(f.NumBlocks())
   226  	defer f.RetSparseSet(removeBlocks)
   227  	for _, v := range remove {
   228  		removeBlocks.Add(v.Block.ID)
   229  	}
   230  
   231  	// Process affected blocks, preserving value order.
   232  	for _, b := range f.Blocks {
   233  		if !removeBlocks.Contains(b.ID) {
   234  			continue
   235  		}
   236  		i := 0
   237  		for j := 0; j < len(b.Values); j++ {
   238  			v := b.Values[j]
   239  			if v.Op == ssaop.OpInvalid {
   240  				continue
   241  			}
   242  			b.Values[i] = v
   243  			i++
   244  		}
   245  		b.TruncateValues(i)
   246  	}
   247  }
   248  
   249  // copyFlags copies v (flag generator) into b, returns the copy.
   250  // If v's arg is also flags, copy recursively.
   251  func copyFlags(v *ssa.Value, b *ssa.Block) *ssa.Value {
   252  	flagsArgs := make(map[int]*ssa.Value)
   253  	for i, a := range v.Args {
   254  		if a.Type.IsFlags() || a.Type.IsTuple() {
   255  			flagsArgs[i] = copyFlags(a, b)
   256  		}
   257  	}
   258  	c := v.CopyInto(b)
   259  	for i, a := range flagsArgs {
   260  		c.SetArg(i, a)
   261  	}
   262  	return c
   263  }
   264
View as plain text