| // Copyright 2017 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package ssa |
| |
| // loopRotate converts loops with a check-loop-condition-at-beginning |
| // to loops with a check-loop-condition-at-end. |
| // This helps loops avoid extra unnecessary jumps. |
| // |
| // loop: |
| // CMPQ ... |
| // JGE exit |
| // ... |
| // JMP loop |
| // exit: |
| // |
| // JMP entry |
| // loop: |
| // ... |
| // entry: |
| // CMPQ ... |
| // JLT loop |
| func loopRotate(f *Func) { |
| loopnest := f.loopnest() |
| if loopnest.hasIrreducible { |
| return |
| } |
| if len(loopnest.loops) == 0 { |
| return |
| } |
| |
| idToIdx := f.Cache.allocIntSlice(f.NumBlocks()) |
| defer f.Cache.freeIntSlice(idToIdx) |
| for i, b := range f.Blocks { |
| idToIdx[b.ID] = i |
| } |
| |
| // Set of blocks we're moving, by ID. |
| move := map[ID]struct{}{} |
| |
| // Map from block ID to the moving blocks that should |
| // come right after it. |
| after := map[ID][]*Block{} |
| |
| // Check each loop header and decide if we want to move it. |
| for _, loop := range loopnest.loops { |
| b := loop.header |
| var p *Block // b's in-loop predecessor |
| for _, e := range b.Preds { |
| if e.b.Kind != BlockPlain { |
| continue |
| } |
| if loopnest.b2l[e.b.ID] != loop { |
| continue |
| } |
| p = e.b |
| } |
| if p == nil { |
| continue |
| } |
| p.Hotness |= HotInitial |
| if f.IsPgoHot { |
| p.Hotness |= HotPgo |
| } |
| // blocks will be arranged so that p is ordered first, if it isn't already. |
| if p == b { // p is header, already first (and also, only block in the loop) |
| continue |
| } |
| p.Hotness |= HotNotFlowIn |
| |
| // the loop header b follows p |
| after[p.ID] = []*Block{b} |
| for { |
| nextIdx := idToIdx[b.ID] + 1 |
| if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?) |
| break |
| } |
| nextb := f.Blocks[nextIdx] |
| if nextb == p { // original loop predecessor is next |
| break |
| } |
| if loopnest.b2l[nextb.ID] == loop { |
| after[p.ID] = append(after[p.ID], nextb) |
| } |
| b = nextb |
| } |
| // Swap b and p so that we'll handle p before b when moving blocks. |
| f.Blocks[idToIdx[loop.header.ID]] = p |
| f.Blocks[idToIdx[p.ID]] = loop.header |
| idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID] |
| |
| // Place b after p. |
| for _, b := range after[p.ID] { |
| move[b.ID] = struct{}{} |
| } |
| } |
| |
| // Move blocks to their destinations in a single pass. |
| // We rely here on the fact that loop headers must come |
| // before the rest of the loop. And that relies on the |
| // fact that we only identify reducible loops. |
| j := 0 |
| // Some blocks that are not part of a loop may be placed |
| // between loop blocks. In order to avoid these blocks from |
| // being overwritten, use a temporary slice. |
| oldOrder := f.Cache.allocBlockSlice(len(f.Blocks)) |
| defer f.Cache.freeBlockSlice(oldOrder) |
| copy(oldOrder, f.Blocks) |
| for _, b := range oldOrder { |
| if _, ok := move[b.ID]; ok { |
| continue |
| } |
| f.Blocks[j] = b |
| j++ |
| for _, a := range after[b.ID] { |
| f.Blocks[j] = a |
| j++ |
| } |
| } |
| if j != len(oldOrder) { |
| f.Fatalf("bad reordering in looprotate") |
| } |
| } |