Source file src/pkg/cmd/compile/internal/ssa/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 { // 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