...
Run Format

Source file src/cmd/compile/internal/ssa/flagalloc.go

Documentation: cmd/compile/internal/ssa

     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  // When breaking up a combined load-compare to separated load and compare operations,
     8  // opLoad specifies the load operation, and opCmp specifies the compare operation.
     9  type typeCmdLoadMap struct {
    10  	opLoad Op
    11  	opCmp  Op
    12  }
    13  
    14  var opCmpLoadMap = map[Op]typeCmdLoadMap{
    15  	OpAMD64CMPQload:      {OpAMD64MOVQload, OpAMD64CMPQ},
    16  	OpAMD64CMPLload:      {OpAMD64MOVLload, OpAMD64CMPL},
    17  	OpAMD64CMPWload:      {OpAMD64MOVWload, OpAMD64CMPW},
    18  	OpAMD64CMPBload:      {OpAMD64MOVBload, OpAMD64CMPB},
    19  	Op386CMPLload:        {Op386MOVLload, Op386CMPL},
    20  	Op386CMPWload:        {Op386MOVWload, Op386CMPW},
    21  	Op386CMPBload:        {Op386MOVBload, Op386CMPB},
    22  	OpAMD64CMPQconstload: {OpAMD64MOVQload, OpAMD64CMPQconst},
    23  	OpAMD64CMPLconstload: {OpAMD64MOVLload, OpAMD64CMPLconst},
    24  	OpAMD64CMPWconstload: {OpAMD64MOVWload, OpAMD64CMPWconst},
    25  	OpAMD64CMPBconstload: {OpAMD64MOVBload, OpAMD64CMPBconst},
    26  	Op386CMPLconstload:   {Op386MOVLload, Op386CMPLconst},
    27  	Op386CMPWconstload:   {Op386MOVWload, Op386CMPWconst},
    28  	Op386CMPBconstload:   {Op386MOVBload, Op386CMPBconst},
    29  }
    30  
    31  // flagalloc allocates the flag register among all the flag-generating
    32  // instructions. Flag values are recomputed if they need to be
    33  // spilled/restored.
    34  func flagalloc(f *Func) {
    35  	// Compute the in-register flag value we want at the end of
    36  	// each block. This is basically a best-effort live variable
    37  	// analysis, so it can be much simpler than a full analysis.
    38  	end := make([]*Value, f.NumBlocks())
    39  	po := f.postorder()
    40  	for n := 0; n < 2; n++ {
    41  		for _, b := range po {
    42  			// Walk values backwards to figure out what flag
    43  			// value we want in the flag register at the start
    44  			// of the block.
    45  			flag := end[b.ID]
    46  			if b.Control != nil && b.Control.Type.IsFlags() {
    47  				flag = b.Control
    48  			}
    49  			for j := len(b.Values) - 1; j >= 0; j-- {
    50  				v := b.Values[j]
    51  				if v == flag {
    52  					flag = nil
    53  				}
    54  				if v.clobbersFlags() {
    55  					flag = nil
    56  				}
    57  				for _, a := range v.Args {
    58  					if a.Type.IsFlags() {
    59  						flag = a
    60  					}
    61  				}
    62  			}
    63  			if flag != nil {
    64  				for _, e := range b.Preds {
    65  					p := e.b
    66  					end[p.ID] = flag
    67  				}
    68  			}
    69  		}
    70  	}
    71  
    72  	// For blocks which have a flags control value, that's the only value
    73  	// we can leave in the flags register at the end of the block. (There
    74  	// is no place to put a flag regeneration instruction.)
    75  	for _, b := range f.Blocks {
    76  		v := b.Control
    77  		if v != nil && v.Type.IsFlags() && end[b.ID] != v {
    78  			end[b.ID] = nil
    79  		}
    80  		if b.Kind == BlockDefer {
    81  			// Defer blocks internally use/clobber the flags value.
    82  			end[b.ID] = nil
    83  		}
    84  	}
    85  
    86  	// Compute which flags values will need to be spilled.
    87  	spill := map[ID]bool{}
    88  	for _, b := range f.Blocks {
    89  		var flag *Value
    90  		if len(b.Preds) > 0 {
    91  			flag = end[b.Preds[0].b.ID]
    92  		}
    93  		for _, v := range b.Values {
    94  			for _, a := range v.Args {
    95  				if !a.Type.IsFlags() {
    96  					continue
    97  				}
    98  				if a == flag {
    99  					continue
   100  				}
   101  				// a will need to be restored here.
   102  				spill[a.ID] = true
   103  				flag = a
   104  			}
   105  			if v.clobbersFlags() {
   106  				flag = nil
   107  			}
   108  			if v.Type.IsFlags() {
   109  				flag = v
   110  			}
   111  		}
   112  		if v := b.Control; v != nil && v != flag && v.Type.IsFlags() {
   113  			spill[v.ID] = true
   114  		}
   115  		if v := end[b.ID]; v != nil && v != flag {
   116  			spill[v.ID] = true
   117  		}
   118  	}
   119  
   120  	// Add flag spill and recomputation where they are needed.
   121  	// TODO: Remove original instructions if they are never used.
   122  	var oldSched []*Value
   123  	for _, b := range f.Blocks {
   124  		oldSched = append(oldSched[:0], b.Values...)
   125  		b.Values = b.Values[:0]
   126  		// The current live flag value (the pre-flagalloc copy).
   127  		var flag *Value
   128  		if len(b.Preds) > 0 {
   129  			flag = end[b.Preds[0].b.ID]
   130  			// Note: the following condition depends on the lack of critical edges.
   131  			for _, e := range b.Preds[1:] {
   132  				p := e.b
   133  				if end[p.ID] != flag {
   134  					f.Fatalf("live flag in %s's predecessors not consistent", b)
   135  				}
   136  			}
   137  		}
   138  		for _, v := range oldSched {
   139  			if v.Op == OpPhi && v.Type.IsFlags() {
   140  				f.Fatalf("phi of flags not supported: %s", v.LongString())
   141  			}
   142  
   143  			// If v will be spilled, and v uses memory, then we must split it
   144  			// into a load + a flag generator.
   145  			// TODO: figure out how to do this without arch-dependent code.
   146  			if spill[v.ID] && v.MemoryArg() != nil {
   147  				switch v.Op {
   148  				case OpAMD64CMPQload:
   149  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt64, v.AuxInt, v.Aux, v.Args[0], v.Args[2])
   150  					v.Op = opCmpLoadMap[v.Op].opCmp
   151  					v.AuxInt = 0
   152  					v.Aux = nil
   153  					v.SetArgs2(load, v.Args[1])
   154  				case OpAMD64CMPLload, Op386CMPLload:
   155  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt32, v.AuxInt, v.Aux, v.Args[0], v.Args[2])
   156  					v.Op = opCmpLoadMap[v.Op].opCmp
   157  					v.AuxInt = 0
   158  					v.Aux = nil
   159  					v.SetArgs2(load, v.Args[1])
   160  				case OpAMD64CMPWload, Op386CMPWload:
   161  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt16, v.AuxInt, v.Aux, v.Args[0], v.Args[2])
   162  					v.Op = opCmpLoadMap[v.Op].opCmp
   163  					v.AuxInt = 0
   164  					v.Aux = nil
   165  					v.SetArgs2(load, v.Args[1])
   166  				case OpAMD64CMPBload, Op386CMPBload:
   167  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt8, v.AuxInt, v.Aux, v.Args[0], v.Args[2])
   168  					v.Op = opCmpLoadMap[v.Op].opCmp
   169  					v.AuxInt = 0
   170  					v.Aux = nil
   171  					v.SetArgs2(load, v.Args[1])
   172  
   173  				case OpAMD64CMPQconstload:
   174  					vo := v.AuxValAndOff()
   175  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt64, vo.Off(), v.Aux, v.Args[0], v.Args[1])
   176  					v.Op = opCmpLoadMap[v.Op].opCmp
   177  					v.AuxInt = vo.Val()
   178  					v.Aux = nil
   179  					v.SetArgs1(load)
   180  				case OpAMD64CMPLconstload, Op386CMPLconstload:
   181  					vo := v.AuxValAndOff()
   182  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt32, vo.Off(), v.Aux, v.Args[0], v.Args[1])
   183  					v.Op = opCmpLoadMap[v.Op].opCmp
   184  					v.AuxInt = vo.Val()
   185  					v.Aux = nil
   186  					v.SetArgs1(load)
   187  				case OpAMD64CMPWconstload, Op386CMPWconstload:
   188  					vo := v.AuxValAndOff()
   189  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt16, vo.Off(), v.Aux, v.Args[0], v.Args[1])
   190  					v.Op = opCmpLoadMap[v.Op].opCmp
   191  					v.AuxInt = vo.Val()
   192  					v.Aux = nil
   193  					v.SetArgs1(load)
   194  				case OpAMD64CMPBconstload, Op386CMPBconstload:
   195  					vo := v.AuxValAndOff()
   196  					load := b.NewValue2IA(v.Pos, opCmpLoadMap[v.Op].opLoad, f.Config.Types.UInt8, vo.Off(), v.Aux, v.Args[0], v.Args[1])
   197  					v.Op = opCmpLoadMap[v.Op].opCmp
   198  					v.AuxInt = vo.Val()
   199  					v.Aux = nil
   200  					v.SetArgs1(load)
   201  
   202  				default:
   203  					f.Fatalf("can't split flag generator: %s", v.LongString())
   204  				}
   205  
   206  			}
   207  
   208  			// Make sure any flag arg of v is in the flags register.
   209  			// If not, recompute it.
   210  			for i, a := range v.Args {
   211  				if !a.Type.IsFlags() {
   212  					continue
   213  				}
   214  				if a == flag {
   215  					continue
   216  				}
   217  				// Recalculate a
   218  				c := copyFlags(a, b)
   219  				// Update v.
   220  				v.SetArg(i, c)
   221  				// Remember the most-recently computed flag value.
   222  				flag = a
   223  			}
   224  			// Issue v.
   225  			b.Values = append(b.Values, v)
   226  			if v.clobbersFlags() {
   227  				flag = nil
   228  			}
   229  			if v.Type.IsFlags() {
   230  				flag = v
   231  			}
   232  		}
   233  		if v := b.Control; v != nil && v != flag && v.Type.IsFlags() {
   234  			// Recalculate control value.
   235  			c := copyFlags(v, b)
   236  			b.SetControl(c)
   237  			flag = v
   238  		}
   239  		if v := end[b.ID]; v != nil && v != flag {
   240  			// Need to reissue flag generator for use by
   241  			// subsequent blocks.
   242  			copyFlags(v, b)
   243  			// Note: this flag generator is not properly linked up
   244  			// with the flag users. This breaks the SSA representation.
   245  			// We could fix up the users with another pass, but for now
   246  			// we'll just leave it.  (Regalloc has the same issue for
   247  			// standard regs, and it runs next.)
   248  		}
   249  	}
   250  
   251  	// Save live flag state for later.
   252  	for _, b := range f.Blocks {
   253  		b.FlagsLiveAtEnd = end[b.ID] != nil
   254  	}
   255  }
   256  
   257  func (v *Value) clobbersFlags() bool {
   258  	if opcodeTable[v.Op].clobberFlags {
   259  		return true
   260  	}
   261  	if v.Type.IsTuple() && (v.Type.FieldType(0).IsFlags() || v.Type.FieldType(1).IsFlags()) {
   262  		// This case handles the possibility where a flag value is generated but never used.
   263  		// In that case, there's no corresponding Select to overwrite the flags value,
   264  		// so we must consider flags clobbered by the tuple-generating instruction.
   265  		return true
   266  	}
   267  	return false
   268  }
   269  
   270  // copyFlags copies v (flag generator) into b, returns the copy.
   271  // If v's arg is also flags, copy recursively.
   272  func copyFlags(v *Value, b *Block) *Value {
   273  	flagsArgs := make(map[int]*Value)
   274  	for i, a := range v.Args {
   275  		if a.Type.IsFlags() || a.Type.IsTuple() {
   276  			flagsArgs[i] = copyFlags(a, b)
   277  		}
   278  	}
   279  	c := v.copyInto(b)
   280  	for i, a := range flagsArgs {
   281  		c.SetArg(i, a)
   282  	}
   283  	return c
   284  }
   285  

View as plain text