looprotate.go

     1  // Copyright 2017 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  // loopRotate converts loops with a check-loop-condition-at-beginning
     8  // to loops with a check-loop-condition-at-end.
     9  // This helps loops avoid extra unnecessary jumps.
    10  //
    11  //	 loop:
    12  //	   CMPQ ...
    13  //	   JGE exit
    14  //	   ...
    15  //	   JMP loop
    16  //	 exit:
    17  //
    18  //	  JMP entry
    19  //	loop:
    20  //	  ...
    21  //	entry:
    22  //	  CMPQ ...
    23  //	  JLT loop
    24  func loopRotate(f *Func) {
    25  	loopnest := f.loopnest()
    26  	if loopnest.hasIrreducible {
    27  		return
    28  	}
    29  	if len(loopnest.loops) == 0 {
    30  		return
    31  	}
    32  
    33  	idToIdx := f.Cache.allocIntSlice(f.NumBlocks())
    34  	defer f.Cache.freeIntSlice(idToIdx)
    35  	for i, b := range f.Blocks {
    36  		idToIdx[b.ID] = i
    37  	}
    38  
    39  	// Set of blocks we're moving, by ID.
    40  	move := map[ID]struct{}{}
    41  
    42  	// Map from block ID to the moving blocks that should
    43  	// come right after it.
    44  	after := map[ID][]*Block{}
    45  
    46  	// Check each loop header and decide if we want to move it.
    47  	for _, loop := range loopnest.loops {
    48  		b := loop.header
    49  		var p *Block // b's in-loop predecessor
    50  		for _, e := range b.Preds {
    51  			if e.b.Kind != BlockPlain {
    52  				continue
    53  			}
    54  			if loopnest.b2l[e.b.ID] != loop {
    55  				continue
    56  			}
    57  			p = e.b
    58  		}
    59  		if p == nil {
    60  			continue
    61  		}
    62  		p.Hotness |= HotInitial
    63  		if f.IsPgoHot {
    64  			p.Hotness |= HotPgo
    65  		}
    66  		// blocks will be arranged so that p is ordered first, if it isn't already.
    67  		if p == b { // p is header, already first (and also, only block in the loop)
    68  			continue
    69  		}
    70  		p.Hotness |= HotNotFlowIn
    71  
    72  		// the loop header b follows p
    73  		after[p.ID] = []*Block{b}
    74  		for {
    75  			nextIdx := idToIdx[b.ID] + 1
    76  			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
    77  				break
    78  			}
    79  			nextb := f.Blocks[nextIdx]
    80  			if nextb == p { // original loop predecessor is next
    81  				break
    82  			}
    83  			if loopnest.b2l[nextb.ID] == loop {
    84  				after[p.ID] = append(after[p.ID], nextb)
    85  			}
    86  			b = nextb
    87  		}
    88  		// Swap b and p so that we'll handle p before b when moving blocks.
    89  		f.Blocks[idToIdx[loop.header.ID]] = p
    90  		f.Blocks[idToIdx[p.ID]] = loop.header
    91  		idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID]
    92  
    93  		// Place b after p.
    94  		for _, b := range after[p.ID] {
    95  			move[b.ID] = struct{}{}
    96  		}
    97  	}
    98  
    99  	// Move blocks to their destinations in a single pass.
   100  	// We rely here on the fact that loop headers must come
   101  	// before the rest of the loop.  And that relies on the
   102  	// fact that we only identify reducible loops.
   103  	j := 0
   104  	// Some blocks that are not part of a loop may be placed
   105  	// between loop blocks. In order to avoid these blocks from
   106  	// being overwritten, use a temporary slice.
   107  	oldOrder := f.Cache.allocBlockSlice(len(f.Blocks))
   108  	defer f.Cache.freeBlockSlice(oldOrder)
   109  	copy(oldOrder, f.Blocks)
   110  	for _, b := range oldOrder {
   111  		if _, ok := move[b.ID]; ok {
   112  			continue
   113  		}
   114  		f.Blocks[j] = b
   115  		j++
   116  		for _, a := range after[b.ID] {
   117  			f.Blocks[j] = a
   118  			j++
   119  		}
   120  	}
   121  	if j != len(oldOrder) {
   122  		f.Fatalf("bad reordering in looprotate")
   123  	}
   124  }
   125
View as plain text