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