diff options
Diffstat (limited to 'src/cmd/compile/internal/ssa/looprotate.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/looprotate.go | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/looprotate.go b/src/cmd/compile/internal/ssa/looprotate.go new file mode 100644 index 0000000..2e5e421 --- /dev/null +++ b/src/cmd/compile/internal/ssa/looprotate.go @@ -0,0 +1,106 @@ +// 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 := make([]int, f.NumBlocks()) + 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 || p == b { + continue + } + 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 { // about to leave loop + break + } + after[p.ID] = append(after[p.ID], nextb) + b = nextb + } + + // 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 + for i, b := range f.Blocks { + if _, ok := move[b.ID]; ok { + continue + } + f.Blocks[j] = b + j++ + for _, a := range after[b.ID] { + if j > i { + f.Fatalf("head before tail in loop %s", b) + } + f.Blocks[j] = a + j++ + } + } + if j != len(f.Blocks) { + f.Fatalf("bad reordering in looprotate") + } +} |