looprotate.go

Documentation: cmd/compile/internal/ssa

     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 || p == b {
    60  			continue
    61  		}
    62  		after[p.ID] = []*Block{b}
    63  		for {
    64  			nextIdx := idToIdx[b.ID] + 1
    65  			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
    66  				break
    67  			}
    68  			nextb := f.Blocks[nextIdx]
    69  			if nextb == p { // original loop predecessor is next
    70  				break
    71  			}
    72  			if loopnest.b2l[nextb.ID] == loop {
    73  				after[p.ID] = append(after[p.ID], nextb)
    74  			}
    75  			b = nextb
    76  		}
    77  		// Swap b and p so that we'll handle p before b when moving blocks.
    78  		f.Blocks[idToIdx[loop.header.ID]] = p
    79  		f.Blocks[idToIdx[p.ID]] = loop.header
    80  		idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID]
    81  
    82  		// Place b after p.
    83  		for _, b := range after[p.ID] {
    84  			move[b.ID] = struct{}{}
    85  		}
    86  	}
    87  
    88  	// Move blocks to their destinations in a single pass.
    89  	// We rely here on the fact that loop headers must come
    90  	// before the rest of the loop.  And that relies on the
    91  	// fact that we only identify reducible loops.
    92  	j := 0
    93  	// Some blocks that are not part of a loop may be placed
    94  	// between loop blocks. In order to avoid these blocks from
    95  	// being overwritten, use a temporary slice.
    96  	oldOrder := f.Cache.allocBlockSlice(len(f.Blocks))
    97  	defer f.Cache.freeBlockSlice(oldOrder)
    98  	copy(oldOrder, f.Blocks)
    99  	for _, b := range oldOrder {
   100  		if _, ok := move[b.ID]; ok {
   101  			continue
   102  		}
   103  		f.Blocks[j] = b
   104  		j++
   105  		for _, a := range after[b.ID] {
   106  			f.Blocks[j] = a
   107  			j++
   108  		}
   109  	}
   110  	if j != len(oldOrder) {
   111  		f.Fatalf("bad reordering in looprotate")
   112  	}
   113  }
   114
View as plain text