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 ssa
     6  
     7  // tighten moves Values closer to the Blocks in which they are used.
     8  // This can reduce the amount of register spilling required,
     9  // if it doesn't also create more live values.
    10  // A Value can be moved to any block that
    11  // dominates all blocks in which it is used.
    12  func tighten(f *Func) {
    13  	canMove := make([]bool, f.NumValues())
    14  	for _, b := range f.Blocks {
    15  		for _, v := range b.Values {
    16  			if v.Op.isLoweredGetClosurePtr() {
    17  				// Must stay in the entry block.
    18  				continue
    19  			}
    20  			switch v.Op {
    21  			case OpPhi, OpArg, OpArgIntReg, OpArgFloatReg, OpSelect0, OpSelect1, OpSelectN:
    22  				// Phis need to stay in their block.
    23  				// Arg must stay in the entry block.
    24  				// Tuple selectors must stay with the tuple generator.
    25  				// SelectN is typically, ultimately, a register.
    26  				continue
    27  			}
    28  			if v.MemoryArg() != nil {
    29  				// We can't move values which have a memory arg - it might
    30  				// make two memory values live across a block boundary.
    31  				continue
    32  			}
    33  			// Count arguments which will need a register.
    34  			narg := 0
    35  			for _, a := range v.Args {
    36  				if !a.rematerializeable() {
    37  					narg++
    38  				}
    39  			}
    40  			if narg >= 2 && !v.Type.IsFlags() {
    41  				// Don't move values with more than one input, as that may
    42  				// increase register pressure.
    43  				// We make an exception for flags, as we want flag generators
    44  				// moved next to uses (because we only have 1 flag register).
    45  				continue
    46  			}
    47  			canMove[v.ID] = true
    48  		}
    49  	}
    50  
    51  	// Build data structure for fast least-common-ancestor queries.
    52  	lca := makeLCArange(f)
    53  
    54  	// For each moveable value, record the block that dominates all uses found so far.
    55  	target := make([]*Block, f.NumValues())
    56  
    57  	// Grab loop information.
    58  	// We use this to make sure we don't tighten a value into a (deeper) loop.
    59  	idom := f.Idom()
    60  	loops := f.loopnest()
    61  	loops.calculateDepths()
    62  
    63  	changed := true
    64  	for changed {
    65  		changed = false
    66  
    67  		// Reset target
    68  		for i := range target {
    69  			target[i] = nil
    70  		}
    71  
    72  		// Compute target locations (for moveable values only).
    73  		// target location = the least common ancestor of all uses in the dominator tree.
    74  		for _, b := range f.Blocks {
    75  			for _, v := range b.Values {
    76  				for i, a := range v.Args {
    77  					if !canMove[a.ID] {
    78  						continue
    79  					}
    80  					use := b
    81  					if v.Op == OpPhi {
    82  						use = b.Preds[i].b
    83  					}
    84  					if target[a.ID] == nil {
    85  						target[a.ID] = use
    86  					} else {
    87  						target[a.ID] = lca.find(target[a.ID], use)
    88  					}
    89  				}
    90  			}
    91  			for _, c := range b.ControlValues() {
    92  				if !canMove[c.ID] {
    93  					continue
    94  				}
    95  				if target[c.ID] == nil {
    96  					target[c.ID] = b
    97  				} else {
    98  					target[c.ID] = lca.find(target[c.ID], b)
    99  				}
   100  			}
   101  		}
   102  
   103  		// If the target location is inside a loop,
   104  		// move the target location up to just before the loop head.
   105  		for _, b := range f.Blocks {
   106  			origloop := loops.b2l[b.ID]
   107  			for _, v := range b.Values {
   108  				t := target[v.ID]
   109  				if t == nil {
   110  					continue
   111  				}
   112  				targetloop := loops.b2l[t.ID]
   113  				for targetloop != nil && (origloop == nil || targetloop.depth > origloop.depth) {
   114  					t = idom[targetloop.header.ID]
   115  					target[v.ID] = t
   116  					targetloop = loops.b2l[t.ID]
   117  				}
   118  			}
   119  		}
   120  
   121  		// Move values to target locations.
   122  		for _, b := range f.Blocks {
   123  			for i := 0; i < len(b.Values); i++ {
   124  				v := b.Values[i]
   125  				t := target[v.ID]
   126  				if t == nil || t == b {
   127  					// v is not moveable, or is already in correct place.
   128  					continue
   129  				}
   130  				// Move v to the block which dominates its uses.
   131  				t.Values = append(t.Values, v)
   132  				v.Block = t
   133  				last := len(b.Values) - 1
   134  				b.Values[i] = b.Values[last]
   135  				b.Values[last] = nil
   136  				b.Values = b.Values[:last]
   137  				changed = true
   138  				i--
   139  			}
   140  		}
   141  	}
   142  }
   143  
   144  // phiTighten moves constants closer to phi users.
   145  // This pass avoids having lots of constants live for lots of the program.
   146  // See issue 16407.
   147  func phiTighten(f *Func) {
   148  	for _, b := range f.Blocks {
   149  		for _, v := range b.Values {
   150  			if v.Op != OpPhi {
   151  				continue
   152  			}
   153  			for i, a := range v.Args {
   154  				if !a.rematerializeable() {
   155  					continue // not a constant we can move around
   156  				}
   157  				if a.Block == b.Preds[i].b {
   158  					continue // already in the right place
   159  				}
   160  				// Make a copy of a, put in predecessor block.
   161  				v.SetArg(i, a.copyInto(b.Preds[i].b))
   162  			}
   163  		}
   164  	}
   165  }
   166
View as plain text