| // 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 |
| |
| // branchelim tries to eliminate branches by |
| // generating CondSelect instructions. |
| // |
| // Search for basic blocks that look like |
| // |
| // bb0 bb0 |
| // | \ / \ |
| // | bb1 or bb1 bb2 <- trivial if/else blocks |
| // | / \ / |
| // bb2 bb3 |
| // |
| // where the intermediate blocks are mostly empty (with no side-effects); |
| // rewrite Phis in the postdominator as CondSelects. |
| func branchelim(f *Func) { |
| // FIXME: add support for lowering CondSelects on more architectures |
| switch f.Config.arch { |
| case "arm64", "amd64": |
| // implemented |
| default: |
| return |
| } |
| |
| change := true |
| for change { |
| change = false |
| for _, b := range f.Blocks { |
| change = elimIf(f, b) || elimIfElse(f, b) || change |
| } |
| } |
| } |
| |
| func canCondSelect(v *Value, arch string) bool { |
| // For now, stick to simple scalars that fit in registers |
| switch { |
| case v.Type.Size() > v.Block.Func.Config.RegSize: |
| return false |
| case v.Type.IsPtrShaped(): |
| return true |
| case v.Type.IsInteger(): |
| if arch == "amd64" && v.Type.Size() < 2 { |
| // amd64 doesn't support CMOV with byte registers |
| return false |
| } |
| return true |
| default: |
| return false |
| } |
| } |
| |
| func elimIf(f *Func, dom *Block) bool { |
| // See if dom is an If with one arm that |
| // is trivial and succeeded by the other |
| // successor of dom. |
| if dom.Kind != BlockIf || dom.Likely != BranchUnknown { |
| return false |
| } |
| var simple, post *Block |
| for i := range dom.Succs { |
| bb, other := dom.Succs[i].Block(), dom.Succs[i^1].Block() |
| if isLeafPlain(bb) && bb.Succs[0].Block() == other { |
| simple = bb |
| post = other |
| break |
| } |
| } |
| if simple == nil || len(post.Preds) != 2 || post == dom { |
| return false |
| } |
| |
| // We've found our diamond CFG of blocks. |
| // Now decide if fusing 'simple' into dom+post |
| // looks profitable. |
| |
| // Check that there are Phis, and that all of them |
| // can be safely rewritten to CondSelect. |
| hasphis := false |
| for _, v := range post.Values { |
| if v.Op == OpPhi { |
| hasphis = true |
| if !canCondSelect(v, f.Config.arch) { |
| return false |
| } |
| } |
| } |
| if !hasphis { |
| return false |
| } |
| |
| // Pick some upper bound for the number of instructions |
| // we'd be willing to execute just to generate a dead |
| // argument to CondSelect. In the worst case, this is |
| // the number of useless instructions executed. |
| const maxfuseinsts = 2 |
| |
| if len(simple.Values) > maxfuseinsts || !allTrivial(simple) { |
| return false |
| } |
| |
| // Replace Phi instructions in b with CondSelect instructions |
| swap := (post.Preds[0].Block() == dom) != (dom.Succs[0].Block() == post) |
| for _, v := range post.Values { |
| if v.Op != OpPhi { |
| continue |
| } |
| v.Op = OpCondSelect |
| if swap { |
| v.Args[0], v.Args[1] = v.Args[1], v.Args[0] |
| } |
| v.AddArg(dom.Control) |
| } |
| |
| // Put all of the instructions into 'dom' |
| // and update the CFG appropriately. |
| dom.Kind = post.Kind |
| dom.SetControl(post.Control) |
| dom.Aux = post.Aux |
| dom.Succs = append(dom.Succs[:0], post.Succs...) |
| for i := range dom.Succs { |
| e := dom.Succs[i] |
| e.b.Preds[e.i].b = dom |
| } |
| |
| for i := range simple.Values { |
| simple.Values[i].Block = dom |
| } |
| for i := range post.Values { |
| post.Values[i].Block = dom |
| } |
| dom.Values = append(dom.Values, simple.Values...) |
| dom.Values = append(dom.Values, post.Values...) |
| |
| // Trash 'post' and 'simple' |
| clobberBlock(post) |
| clobberBlock(simple) |
| |
| f.invalidateCFG() |
| return true |
| } |
| |
| // is this a BlockPlain with one predecessor? |
| func isLeafPlain(b *Block) bool { |
| return b.Kind == BlockPlain && len(b.Preds) == 1 |
| } |
| |
| func clobberBlock(b *Block) { |
| b.Values = nil |
| b.Preds = nil |
| b.Succs = nil |
| b.Aux = nil |
| b.SetControl(nil) |
| b.Likely = BranchUnknown |
| b.Kind = BlockInvalid |
| } |
| |
| func elimIfElse(f *Func, b *Block) bool { |
| // See if 'b' ends in an if/else: it should |
| // have two successors, both of which are BlockPlain |
| // and succeeded by the same block. |
| if b.Kind != BlockIf || b.Likely != BranchUnknown { |
| return false |
| } |
| yes, no := b.Succs[0].Block(), b.Succs[1].Block() |
| if !isLeafPlain(yes) || len(yes.Values) > 1 || !allTrivial(yes) { |
| return false |
| } |
| if !isLeafPlain(no) || len(no.Values) > 1 || !allTrivial(no) { |
| return false |
| } |
| if b.Succs[0].Block().Succs[0].Block() != b.Succs[1].Block().Succs[0].Block() { |
| return false |
| } |
| // block that postdominates the if/else |
| post := b.Succs[0].Block().Succs[0].Block() |
| if len(post.Preds) != 2 || post == b { |
| return false |
| } |
| hasphis := false |
| for _, v := range post.Values { |
| if v.Op == OpPhi { |
| hasphis = true |
| if !canCondSelect(v, f.Config.arch) { |
| return false |
| } |
| } |
| } |
| if !hasphis { |
| return false |
| } |
| |
| // Don't generate CondSelects if branch is cheaper. |
| if !shouldElimIfElse(no, yes, post, f.Config.arch) { |
| return false |
| } |
| |
| // now we're committed: rewrite each Phi as a CondSelect |
| swap := post.Preds[0].Block() != b.Succs[0].Block() |
| for _, v := range post.Values { |
| if v.Op != OpPhi { |
| continue |
| } |
| v.Op = OpCondSelect |
| if swap { |
| v.Args[0], v.Args[1] = v.Args[1], v.Args[0] |
| } |
| v.AddArg(b.Control) |
| } |
| |
| // Move the contents of all of these |
| // blocks into 'b' and update CFG edges accordingly |
| b.Kind = post.Kind |
| b.SetControl(post.Control) |
| b.Aux = post.Aux |
| b.Succs = append(b.Succs[:0], post.Succs...) |
| for i := range b.Succs { |
| e := b.Succs[i] |
| e.b.Preds[e.i].b = b |
| } |
| for i := range post.Values { |
| post.Values[i].Block = b |
| } |
| for i := range yes.Values { |
| yes.Values[i].Block = b |
| } |
| for i := range no.Values { |
| no.Values[i].Block = b |
| } |
| b.Values = append(b.Values, yes.Values...) |
| b.Values = append(b.Values, no.Values...) |
| b.Values = append(b.Values, post.Values...) |
| |
| // trash post, yes, and no |
| clobberBlock(yes) |
| clobberBlock(no) |
| clobberBlock(post) |
| |
| f.invalidateCFG() |
| return true |
| } |
| |
| // shouldElimIfElse reports whether estimated cost of eliminating branch |
| // is lower than threshold. |
| func shouldElimIfElse(no, yes, post *Block, arch string) bool { |
| switch arch { |
| default: |
| return true |
| case "amd64": |
| const maxcost = 2 |
| phi := 0 |
| other := 0 |
| for _, v := range post.Values { |
| if v.Op == OpPhi { |
| // Each phi results in CondSelect, which lowers into CMOV, |
| // CMOV has latency >1 on most CPUs. |
| phi++ |
| } |
| for _, x := range v.Args { |
| if x.Block == no || x.Block == yes { |
| other++ |
| } |
| } |
| } |
| cost := phi * 1 |
| if phi > 1 { |
| // If we have more than 1 phi and some values in post have args |
| // in yes or no blocks, we may have to recalucalte condition, because |
| // those args may clobber flags. For now assume that all operations clobber flags. |
| cost += other * 1 |
| } |
| return cost < maxcost |
| } |
| } |
| |
| func allTrivial(b *Block) bool { |
| // don't fuse memory ops, Phi ops, divides (can panic), |
| // or anything else with side-effects |
| for _, v := range b.Values { |
| if v.Op == OpPhi || isDivMod(v.Op) || v.Type.IsMemory() || |
| v.MemoryArg() != nil || opcodeTable[v.Op].hasSideEffects { |
| return false |
| } |
| } |
| return true |
| } |
| |
| func isDivMod(op Op) bool { |
| switch op { |
| case OpDiv8, OpDiv8u, OpDiv16, OpDiv16u, |
| OpDiv32, OpDiv32u, OpDiv64, OpDiv64u, OpDiv128u, |
| OpDiv32F, OpDiv64F, |
| OpMod8, OpMod8u, OpMod16, OpMod16u, |
| OpMod32, OpMod32u, OpMod64, OpMod64u: |
| return true |
| default: |
| return false |
| } |
| } |
