tighten.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/base"
     9  	"cmd/compile/internal/ssa"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  )
    12  
    13  // tighten moves Values closer to the Blocks in which they are used.
    14  // This can reduce the amount of register spilling required,
    15  // if it doesn't also create more live values.
    16  // A Value can be moved to any block that
    17  // dominates all blocks in which it is used.
    18  func tighten(f *ssa.Func) {
    19  	if base.Flag.N != 0 && len(f.Blocks) < 10000 {
    20  		// Skip the optimization in -N mode, except for huge functions.
    21  		// Too many values live across blocks can cause pathological
    22  		// behavior in the register allocator (see issue 52180).
    23  		return
    24  	}
    25  
    26  	canMove := f.Cache.AllocBoolSlice(f.NumValues())
    27  	defer f.Cache.FreeBoolSlice(canMove)
    28  
    29  	// Compute the memory states of each block.
    30  	startMem := f.Cache.AllocValueSlice(f.NumBlocks())
    31  	defer f.Cache.FreeValueSlice(startMem)
    32  	endMem := f.Cache.AllocValueSlice(f.NumBlocks())
    33  	defer f.Cache.FreeValueSlice(endMem)
    34  	distinctArgs := f.NewSparseSet(f.NumValues())
    35  	defer f.RetSparseSet(distinctArgs)
    36  	memState(f, startMem, endMem)
    37  
    38  	for _, b := range f.Blocks {
    39  		for _, v := range b.Values {
    40  			if v.Op.IsLoweredGetClosurePtr() {
    41  				// Must stay in the entry block.
    42  				continue
    43  			}
    44  			switch v.Op {
    45  			case ssaop.OpPhi, ssaop.OpArg, ssaop.OpArgIntReg, ssaop.OpArgFloatReg, ssaop.OpSelect0, ssaop.OpSelect1, ssaop.OpSelectN:
    46  				// Phis need to stay in their block.
    47  				// Arg must stay in the entry block.
    48  				// Tuple selectors must stay with the tuple generator.
    49  				// SelectN is typically, ultimately, a register.
    50  				continue
    51  			}
    52  			if ssaop.OpcodeTable[v.Op].NilCheck {
    53  				// Nil checks need to stay in their block. See issue 72860.
    54  				continue
    55  			}
    56  			// Count distinct arguments which will need a register.
    57  			distinctArgs.Clear()
    58  
    59  			for _, a := range v.Args {
    60  				// SP and SB are special registers and have no effect on
    61  				// the allocation of general-purpose registers.
    62  				if a.NeedRegister() && a.Op != ssaop.OpSB && a.Op != ssaop.OpSP {
    63  					distinctArgs.Add(a.ID)
    64  				}
    65  			}
    66  
    67  			if distinctArgs.Size() >= 2 && !v.Type.IsFlags() {
    68  				// Don't move values with more than one input, as that may
    69  				// increase register pressure.
    70  				// We make an exception for flags, as we want flag generators
    71  				// moved next to uses (because we only have 1 flag register).
    72  				continue
    73  			}
    74  			canMove[v.ID] = true
    75  		}
    76  	}
    77  
    78  	// Build data structure for fast least-common-ancestor queries.
    79  	lca := makeLCArange(f)
    80  
    81  	// For each moveable value, record the block that dominates all uses found so far.
    82  	target := f.Cache.AllocBlockSlice(f.NumValues())
    83  	defer f.Cache.FreeBlockSlice(target)
    84  
    85  	// Grab loop information.
    86  	// We use this to make sure we don't tighten a value into a (deeper) loop.
    87  	idom := f.Idom()
    88  	loops := f.Loopnest()
    89  
    90  	changed := true
    91  	for changed {
    92  		changed = false
    93  
    94  		// Reset target
    95  		clear(target)
    96  
    97  		// Compute target locations (for moveable values only).
    98  		// target location = the least common ancestor of all uses in the dominator tree.
    99  		for _, b := range f.Blocks {
   100  			for _, v := range b.Values {
   101  				for i, a := range v.Args {
   102  					if !canMove[a.ID] {
   103  						continue
   104  					}
   105  					use := b
   106  					if v.Op == ssaop.OpPhi {
   107  						use = b.Preds[i].B
   108  					}
   109  					if target[a.ID] == nil {
   110  						target[a.ID] = use
   111  					} else {
   112  						target[a.ID] = lca.find(target[a.ID], use)
   113  					}
   114  				}
   115  			}
   116  			for _, c := range b.ControlValues() {
   117  				if !canMove[c.ID] {
   118  					continue
   119  				}
   120  				if target[c.ID] == nil {
   121  					target[c.ID] = b
   122  				} else {
   123  					target[c.ID] = lca.find(target[c.ID], b)
   124  				}
   125  			}
   126  		}
   127  
   128  		// If the target location is inside a loop,
   129  		// move the target location up to just before the loop head.
   130  		if !loops.HasIrreducible {
   131  			// Loop info might not be correct for irreducible loops. See issue 75569.
   132  			for _, b := range f.Blocks {
   133  				origloop := loops.B2L[b.ID]
   134  				for _, v := range b.Values {
   135  					t := target[v.ID]
   136  					if t == nil {
   137  						continue
   138  					}
   139  					targetloop := loops.B2L[t.ID]
   140  					for targetloop != nil && (origloop == nil || targetloop.Depth > origloop.Depth) {
   141  						t = idom[targetloop.Header.ID]
   142  						target[v.ID] = t
   143  						targetloop = loops.B2L[t.ID]
   144  					}
   145  				}
   146  			}
   147  		}
   148  
   149  		// Move values to target locations.
   150  		for _, b := range f.Blocks {
   151  			for i := 0; i < len(b.Values); i++ {
   152  				v := b.Values[i]
   153  				t := target[v.ID]
   154  				if t == nil || t == b {
   155  					// v is not moveable, or is already in correct place.
   156  					continue
   157  				}
   158  				if mem := v.MemoryArg(); mem != nil {
   159  					if startMem[t.ID] != mem {
   160  						// We can't move a value with a memory arg unless the target block
   161  						// has that memory arg as its starting memory.
   162  						continue
   163  					}
   164  				}
   165  				if f.Pass.Debug > 0 {
   166  					b.Func.Warnl(v.Pos, "%v is moved", v.Op)
   167  				}
   168  				// Move v to the block which dominates its uses.
   169  				t.Values = append(t.Values, v)
   170  				v.Block = t
   171  				last := len(b.Values) - 1
   172  				b.Values[i] = b.Values[last]
   173  				b.Values[last] = nil
   174  				b.Values = b.Values[:last]
   175  				changed = true
   176  				i--
   177  			}
   178  		}
   179  	}
   180  }
   181  
   182  // phiTighten moves constants closer to phi users.
   183  // This pass avoids having lots of constants live for lots of the program.
   184  // See issue 16407.
   185  func phiTighten(f *ssa.Func) {
   186  	for _, b := range f.Blocks {
   187  		for _, v := range b.Values {
   188  			if v.Op != ssaop.OpPhi {
   189  				continue
   190  			}
   191  			for i, a := range v.Args {
   192  				if !a.Rematerializeable() {
   193  					continue // not a constant we can move around
   194  				}
   195  				if a.Block == b.Preds[i].B {
   196  					continue // already in the right place
   197  				}
   198  				// Make a copy of a, put in predecessor block.
   199  				v.SetArg(i, a.CopyInto(b.Preds[i].B))
   200  			}
   201  		}
   202  	}
   203  }
   204  
   205  // memState computes the memory state at the beginning and end of each block of
   206  // the function. The memory state is represented by a value of mem type.
   207  // The returned result is stored in startMem and endMem, and endMem is nil for
   208  // blocks with no successors (Exit,Ret,RetJmp blocks). This algorithm is not
   209  // suitable for infinite loop blocks that do not contain any mem operations.
   210  // For example:
   211  // b1:
   212  //
   213  //	(some values)
   214  //
   215  // plain -> b2
   216  // b2: <- b1 b2
   217  // Plain -> b2
   218  //
   219  // Algorithm introduction:
   220  //  1. The start memory state of a block is InitMem, a Phi node of type mem or
   221  //     an incoming memory value.
   222  //  2. The start memory state of a block is consistent with the end memory state
   223  //     of its parent nodes. If the start memory state of a block is a Phi value,
   224  //     then the end memory state of its parent nodes is consistent with the
   225  //     corresponding argument value of the Phi node.
   226  //  3. The algorithm first obtains the memory state of some blocks in the tree
   227  //     in the first step. Then floods the known memory state to other nodes in
   228  //     the second step.
   229  func memState(f *ssa.Func, startMem, endMem []*ssa.Value) {
   230  	// This slice contains the set of blocks that have had their startMem set but this
   231  	// startMem value has not yet been propagated to the endMem of its predecessors
   232  	changed := make([]*ssa.Block, 0)
   233  	// First step, init the memory state of some blocks.
   234  	for _, b := range f.Blocks {
   235  		for _, v := range b.Values {
   236  			var mem *ssa.Value
   237  			if v.Op == ssaop.OpPhi {
   238  				if v.Type.IsMemory() {
   239  					mem = v
   240  				}
   241  			} else if v.Op == ssaop.OpInitMem {
   242  				mem = v // This is actually not needed.
   243  			} else if a := v.MemoryArg(); a != nil && a.Block != b {
   244  				// The only incoming memory value doesn't belong to this block.
   245  				mem = a
   246  			}
   247  			if mem != nil {
   248  				if old := startMem[b.ID]; old != nil {
   249  					if old == mem {
   250  						continue
   251  					}
   252  					f.Fatalf("func %s, startMem[%v] has different values, old %v, new %v", f.Name, b, old, mem)
   253  				}
   254  				startMem[b.ID] = mem
   255  				changed = append(changed, b)
   256  			}
   257  		}
   258  	}
   259  
   260  	// Second step, floods the known memory state of some blocks to others.
   261  	for len(changed) != 0 {
   262  		top := changed[0]
   263  		changed = changed[1:]
   264  		mem := startMem[top.ID]
   265  		for i, p := range top.Preds {
   266  			pb := p.B
   267  			if endMem[pb.ID] != nil {
   268  				continue
   269  			}
   270  			if mem.Op == ssaop.OpPhi && mem.Block == top {
   271  				endMem[pb.ID] = mem.Args[i]
   272  			} else {
   273  				endMem[pb.ID] = mem
   274  			}
   275  			if startMem[pb.ID] == nil {
   276  				startMem[pb.ID] = endMem[pb.ID]
   277  				changed = append(changed, pb)
   278  			}
   279  		}
   280  	}
   281  }
   282
View as plain text