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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ssa"
     9  	"cmd/compile/internal/ssa/block"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  )
    12  
    13  // We are looking for loops with following structure
    14  // (loop bodies may have control flow inside):
    15  //
    16  //              +--------------+
    17  //              |              |
    18  //              |  preheader   |
    19  //              |              |
    20  //              +-------+------+
    21  //                      |
    22  //                      |
    23  //              +-------v------+
    24  //              |              |
    25  //       +------>    header    |
    26  //       |      |              |
    27  //       |      +-------+------+
    28  //       |              |
    29  //       |              |
    30  //       |      +-------v------+
    31  //       |      |              |
    32  //       +------+  loop body   |
    33  //              |              |
    34  //              +--------------+
    35  //
    36  //
    37  // We consider all phis and memory operations as initial loop dependent set.
    38  // So loop independent values are all loop values,
    39  // minus transitive closure of initial loop dependent values.
    40  // We remove those values from their BBs and move them to preheader.
    41  
    42  func licm(f *ssa.Func) {
    43  	// See likelyadjust.go for details about loop info.
    44  	nest := ssa.Loopnestfor(f)
    45  	if len(nest.Loops) == 0 || nest.HasIrreducible {
    46  		return
    47  	}
    48  
    49  	uses := uses(f)
    50  	defer uses.free(f)
    51  
    52  	loopDependent := f.Cache.AllocBoolSlice(f.NumValues())
    53  	defer f.Cache.FreeBoolSlice(loopDependent)
    54  	queue := f.Cache.AllocValueSlice(f.NumValues())
    55  	defer f.Cache.FreeValueSlice(queue)
    56  	queue = queue[:0]
    57  
    58  	// Start with all values we can't move out of loops.
    59  	for _, b := range f.Blocks {
    60  		if loop := nest.B2L[b.ID]; loop == nil || !loop.IsInner {
    61  			// Values outside any loop we don't care about.
    62  			// Values not in a leaf loop we can't handle.
    63  			continue
    64  		}
    65  		for _, v := range b.Values {
    66  			if ssaop.OpcodeTable[v.Op].EarlyOk {
    67  				// Double check we didn't mark the wrong ops as earlyOk
    68  				if v.Type.IsMemory() || ssaop.OpcodeTable[v.Op].NilCheck || ssaop.OpcodeTable[v.Op].HasSideEffects || v.MemoryArg() != nil {
    69  					v.Fatalf("op %s has bad earlyOk mark", v.Op)
    70  				}
    71  				if !v.Type.IsPtr() {
    72  					// Note: can't move pointer arithmetic, as it may be guarded by conditionals
    73  					// and thus could materialize a bad pointer across a safepoint.
    74  
    75  					continue // Ok to lift out of loop.
    76  				}
    77  			}
    78  			if v.Op == ssaop.OpSelect0 || v.Op == ssaop.OpSelect1 {
    79  				// These ops can (and must) move with the op they are selecting from.
    80  				continue
    81  			}
    82  			loopDependent[v.ID] = true
    83  			queue = append(queue, v)
    84  		}
    85  	}
    86  
    87  	// If a value can't be moved out of a loop, neither can its users.
    88  	// The queue contains values which are loop dependent, but their users
    89  	// have not been marked as loop dependent yet.
    90  	for len(queue) > 0 {
    91  		v := queue[len(queue)-1]
    92  		queue = queue[:len(queue)-1]
    93  
    94  		for _, u := range uses.get(v) {
    95  			if loop := nest.B2L[u.Block.ID]; loop == nil || !loop.IsInner {
    96  				continue // see above
    97  			}
    98  			if loopDependent[u.ID] {
    99  				continue
   100  			}
   101  			loopDependent[u.ID] = true
   102  			queue = append(queue, u)
   103  		}
   104  	}
   105  
   106  	// Anything not marked as loop-dependent can be moved out of its loop.
   107  	for _, b := range f.Blocks {
   108  		loop := nest.B2L[b.ID]
   109  		if loop == nil || !loop.IsInner {
   110  			// loopDependent check is wrong for loops containing other loops,
   111  			// because then a value might have an argument computed inside
   112  			// a nested loop.
   113  			continue
   114  		}
   115  		if len(loop.Header.Preds) != 2 {
   116  			continue // is never true?
   117  		}
   118  		anyMoved := false
   119  		for i, v := range b.Values {
   120  			if loopDependent[v.ID] {
   121  				continue
   122  			}
   123  			// Figure out where to move loop-independent values.
   124  			h := loop.Header
   125  			var inIdx int
   126  			if int(h.Preds[0].B.ID) >= len(nest.B2L) || nest.B2L[h.Preds[0].B.ID] != loop {
   127  				inIdx = 0
   128  			} else {
   129  				inIdx = 1
   130  			}
   131  			dest := h.Preds[inIdx].B
   132  			if dest.Kind != block.BlockPlain {
   133  				outIdx := h.Preds[inIdx].I
   134  				// Introduce a new block between the loop
   135  				// header predecessor and the loop header itself.
   136  				mid := f.NewBlock(block.BlockPlain)
   137  				mid.Pos = dest.Pos
   138  				// Splice into graph.
   139  				mid.Preds = append(mid.Preds, ssa.Edge{B: dest, I: outIdx})
   140  				mid.Succs = append(mid.Succs, ssa.Edge{B: h, I: inIdx})
   141  				h.Preds[inIdx] = ssa.Edge{B: mid, I: 0}
   142  				dest.Succs[outIdx] = ssa.Edge{B: mid, I: 0}
   143  
   144  				dest = mid
   145  			}
   146  
   147  			b.Values[i] = nil
   148  			v.Block = dest
   149  			dest.Values = append(dest.Values, v)
   150  			anyMoved = true
   151  		}
   152  		if anyMoved {
   153  			// We just nil'd entries in b.Values above. Compact out the nils.
   154  			i := 0
   155  			for _, v := range b.Values {
   156  				if v == nil {
   157  					continue
   158  				}
   159  				b.Values[i] = v
   160  				i++
   161  			}
   162  			b.Values = b.Values[:i]
   163  		}
   164  	}
   165  }
   166
View as plain text