Source file src/cmd/compile/internal/ssa/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 := 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 { // about to leave loop
    72  				break
    73  			}
    74  			after[p.ID] = append(after[p.ID], nextb)
    75  			b = nextb
    76  		}
    77  
    78  		// Place b after p.
    79  		for _, b := range after[p.ID] {
    80  			move[b.ID] = struct{}{}
    81  		}
    82  	}
    83  
    84  	// Move blocks to their destinations in a single pass.
    85  	// We rely here on the fact that loop headers must come
    86  	// before the rest of the loop.  And that relies on the
    87  	// fact that we only identify reducible loops.
    88  	j := 0
    89  	for i, b := range f.Blocks {
    90  		if _, ok := move[b.ID]; ok {
    91  			continue
    92  		}
    93  		f.Blocks[j] = b
    94  		j++
    95  		for _, a := range after[b.ID] {
    96  			if j > i {
    97  				f.Fatalf("head before tail in loop %s", b)
    98  			}
    99  			f.Blocks[j] = a
   100  			j++
   101  		}
   102  	}
   103  	if j != len(f.Blocks) {
   104  		f.Fatalf("bad reordering in looprotate")
   105  	}
   106  }
   107  

View as plain text