Home | History | Annotate | Download | only in 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 			switch v.Op {
     17 			case OpPhi, OpGetClosurePtr, OpArg, OpSelect0, OpSelect1:
     18 				// Phis need to stay in their block.
     19 				// GetClosurePtr & Arg must stay in the entry block.
     20 				// Tuple selectors must stay with the tuple generator.
     21 				continue
     22 			}
     23 			if len(v.Args) > 0 && v.Args[len(v.Args)-1].Type.IsMemory() {
     24 				// We can't move values which have a memory arg - it might
     25 				// make two memory values live across a block boundary.
     26 				continue
     27 			}
     28 			// Count arguments which will need a register.
     29 			narg := 0
     30 			for _, a := range v.Args {
     31 				switch a.Op {
     32 				case OpConst8, OpConst16, OpConst32, OpConst64, OpAddr:
     33 					// Probably foldable into v, don't count as an argument needing a register.
     34 					// TODO: move tighten to a machine-dependent phase and use v.rematerializeable()?
     35 				default:
     36 					narg++
     37 				}
     38 			}
     39 			if narg >= 2 && !v.Type.IsBoolean() {
     40 				// Don't move values with more than one input, as that may
     41 				// increase register pressure.
     42 				// We make an exception for boolean-typed values, as they will
     43 				// likely be converted to flags, and 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 			if c := b.Control; c != nil {
     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