Source file src/pkg/cmd/compile/internal/ssa/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, 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