...
Run Format

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

View as plain text