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