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
