licm.go

     1  // Copyright 2016 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  // We are looking for loops with following structure
     8  // (loop bodies may have control flow inside):
     9  //
    10  //              +--------------+
    11  //              |              |
    12  //              |  preheader   |
    13  //              |              |
    14  //              +-------+------+
    15  //                      |
    16  //                      |
    17  //              +-------v------+
    18  //              |              |
    19  //       +------>    header    |
    20  //       |      |              |
    21  //       |      +-------+------+
    22  //       |              |
    23  //       |              |
    24  //       |      +-------v------+
    25  //       |      |              |
    26  //       +------+  loop body   |
    27  //              |              |
    28  //              +--------------+
    29  //
    30  //
    31  // We consider all phis and memory operations as initial loop dependent set.
    32  // So loop independent values are all loop values,
    33  // minus transitive closure of initial loop dependent values.
    34  // We remove those values from their BBs and move them to preheader.
    35  
    36  func licm(f *Func) {
    37  	// See likelyadjust.go for details about loop info.
    38  	nest := loopnestfor(f)
    39  	if len(nest.loops) == 0 || nest.hasIrreducible {
    40  		return
    41  	}
    42  
    43  	uses := uses(f)
    44  	defer uses.free(f)
    45  
    46  	loopDependent := f.Cache.allocBoolSlice(f.NumValues())
    47  	defer f.Cache.freeBoolSlice(loopDependent)
    48  	queue := f.Cache.allocValueSlice(f.NumValues())
    49  	defer f.Cache.freeValueSlice(queue)
    50  	queue = queue[:0]
    51  
    52  	// Start with all values we can't move out of loops.
    53  	for _, b := range f.Blocks {
    54  		if loop := nest.b2l[b.ID]; loop == nil || !loop.isInner {
    55  			// Values outside any loop we don't care about.
    56  			// Values not in a leaf loop we can't handle.
    57  			continue
    58  		}
    59  		for _, v := range b.Values {
    60  			loopDep := false
    61  			if v.Op == OpPhi {
    62  				loopDep = true
    63  			} else if v.Type.IsMemory() {
    64  				// We can't move state-modifying code.
    65  				// (TODO: but maybe this is handled by memory Phis anyway?)
    66  				loopDep = true
    67  			} else if v.Type.IsFlags() || v.Type.IsTuple() && (v.Type.FieldType(0).IsFlags() || v.Type.FieldType(1).IsFlags()) {
    68  				// This is not required for correctness. It is just to
    69  				// keep the live range of flag values low.
    70  				loopDep = true
    71  			} else if opcodeTable[v.Op].nilCheck {
    72  				// NilCheck in case loop executes 0 times. (It has a memory arg anyway?)
    73  				loopDep = true
    74  			} else if opcodeTable[v.Op].hasSideEffects {
    75  				// Operations with side effects cannot be moved.
    76  				// (This includes divides that might fault, see issue 78892.)
    77  				loopDep = true
    78  			} else if v.MemoryArg() != nil {
    79  				// Because the state of memory might be different at the loop start. (Also handled by Phi?)
    80  				loopDep = true
    81  			} else if v.Type.IsPtr() {
    82  				// Can't move pointer arithmetic, as it may be guarded by conditionals
    83  				// and this could materialize a bad pointer across a safepoint.
    84  				loopDep = true
    85  			}
    86  			if loopDep {
    87  				loopDependent[v.ID] = true
    88  				queue = append(queue, v)
    89  			}
    90  		}
    91  	}
    92  
    93  	// If a value can't be moved out of a loop, neither can its users.
    94  	// The queue contains values which are loop dependent, but their users
    95  	// have not been marked as loop dependent yet.
    96  	for len(queue) > 0 {
    97  		v := queue[len(queue)-1]
    98  		queue = queue[:len(queue)-1]
    99  
   100  		for _, u := range uses.get(v) {
   101  			if loop := nest.b2l[u.Block.ID]; loop == nil || !loop.isInner {
   102  				continue // see above
   103  			}
   104  			if loopDependent[u.ID] {
   105  				continue
   106  			}
   107  			loopDependent[u.ID] = true
   108  			queue = append(queue, u)
   109  		}
   110  	}
   111  
   112  	// Anything not marked as loop-dependent can be moved out of its loop.
   113  	for _, b := range f.Blocks {
   114  		loop := nest.b2l[b.ID]
   115  		if loop == nil || !loop.isInner {
   116  			// loopDependent check is wrong for loops containing other loops,
   117  			// because then a value might have an argument computed inside
   118  			// a nested loop.
   119  			continue
   120  		}
   121  		if len(loop.header.Preds) != 2 {
   122  			continue // is never true?
   123  		}
   124  		anyMoved := false
   125  		for i, v := range b.Values {
   126  			if loopDependent[v.ID] {
   127  				continue
   128  			}
   129  			// Figure out where to move loop-independent values.
   130  			h := loop.header
   131  			var inIdx int
   132  			if int(h.Preds[0].b.ID) >= len(nest.b2l) || nest.b2l[h.Preds[0].b.ID] != loop {
   133  				inIdx = 0
   134  			} else {
   135  				inIdx = 1
   136  			}
   137  			dest := h.Preds[inIdx].b
   138  			if dest.Kind != BlockPlain {
   139  				outIdx := h.Preds[inIdx].i
   140  				// Introduce a new block between the loop
   141  				// header predecessor and the loop header itself.
   142  				mid := f.NewBlock(BlockPlain)
   143  				mid.Pos = dest.Pos
   144  				// Splice into graph.
   145  				mid.Preds = append(mid.Preds, Edge{dest, outIdx})
   146  				mid.Succs = append(mid.Succs, Edge{h, inIdx})
   147  				h.Preds[inIdx] = Edge{mid, 0}
   148  				dest.Succs[outIdx] = Edge{mid, 0}
   149  
   150  				dest = mid
   151  			}
   152  
   153  			b.Values[i] = nil
   154  			v.Block = dest
   155  			dest.Values = append(dest.Values, v)
   156  			anyMoved = true
   157  		}
   158  		if anyMoved {
   159  			// We just nil'd entries in b.Values above. Compact out the nils.
   160  			i := 0
   161  			for _, v := range b.Values {
   162  				if v == nil {
   163  					continue
   164  				}
   165  				b.Values[i] = v
   166  				i++
   167  			}
   168  			b.Values = b.Values[:i]
   169  		}
   170  	}
   171  }
   172
View as plain text