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 := make([]int, f.NumBlocks())
    34  	for i, b := range f.Blocks {
    35  		idToIdx[b.ID] = i
    36  	}
    37  
    38  	// Set of blocks we're moving, by ID.
    39  	move := map[ID]struct{}{}
    40  
    41  	// Map from block ID to the moving blocks that should
    42  	// come right after it.
    43  	after := map[ID][]*Block{}
    44  
    45  	// Check each loop header and decide if we want to move it.
    46  	for _, loop := range loopnest.loops {
    47  		b := loop.header
    48  		var p *Block // b's in-loop predecessor
    49  		for _, e := range b.Preds {
    50  			if e.b.Kind != BlockPlain {
    51  				continue
    52  			}
    53  			if loopnest.b2l[e.b.ID] != loop {
    54  				continue
    55  			}
    56  			p = e.b
    57  		}
    58  		if p == nil || p == b {
    59  			continue
    60  		}
    61  		after[p.ID] = []*Block{b}
    62  		for {
    63  			nextIdx := idToIdx[b.ID] + 1
    64  			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
    65  				break
    66  			}
    67  			nextb := f.Blocks[nextIdx]
    68  			if nextb == p { // original loop predecessor is next
    69  				break
    70  			}
    71  			if loopnest.b2l[nextb.ID] == loop {
    72  				after[p.ID] = append(after[p.ID], nextb)
    73  			}
    74  			b = nextb
    75  		}
    76  		// Swap b and p so that we'll handle p before b when moving blocks.
    77  		f.Blocks[idToIdx[loop.header.ID]] = p
    78  		f.Blocks[idToIdx[p.ID]] = loop.header
    79  		idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID]
    80  
    81  		// Place b after p.
    82  		for _, b := range after[p.ID] {
    83  			move[b.ID] = struct{}{}
    84  		}
    85  	}
    86  
    87  	// Move blocks to their destinations in a single pass.
    88  	// We rely here on the fact that loop headers must come
    89  	// before the rest of the loop.  And that relies on the
    90  	// fact that we only identify reducible loops.
    91  	j := 0
    92  	// Some blocks that are not part of a loop may be placed
    93  	// between loop blocks. In order to avoid these blocks from
    94  	// being overwritten, use a temporary slice.
    95  	newOrder := make([]*Block, 0, f.NumBlocks())
    96  	for _, b := range f.Blocks {
    97  		if _, ok := move[b.ID]; ok {
    98  			continue
    99  		}
   100  		newOrder = append(newOrder, b)
   101  		j++
   102  		for _, a := range after[b.ID] {
   103  			newOrder = append(newOrder, a)
   104  			j++
   105  		}
   106  	}
   107  	if j != len(f.Blocks) {
   108  		f.Fatalf("bad reordering in looprotate")
   109  	}
   110  	f.Blocks = newOrder
   111  }
   112
View as plain text