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