1 // Copyright 2019 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 // fuseIntegerComparisons optimizes inequalities such as '1 <= x && x < 5', 8 // which can be optimized to 'unsigned(x-1) < 4'. 9 // 10 // Look for branch structure like: 11 // 12 // p 13 // |\ 14 // | b 15 // |/ \ 16 // s0 s1 17 // 18 // In our example, p has control '1 <= x', b has control 'x < 5', 19 // and s0 and s1 are the if and else results of the comparison. 20 // 21 // This will be optimized into: 22 // 23 // p 24 // \ 25 // b 26 // / \ 27 // s0 s1 28 // 29 // where b has the combined control value 'unsigned(x-1) < 4'. 30 // Later passes will then fuse p and b. 31 func fuseIntegerComparisons(b *Block) bool { 32 if len(b.Preds) != 1 { 33 return false 34 } 35 p := b.Preds[0].Block() 36 if b.Kind != BlockIf || p.Kind != BlockIf { 37 return false 38 } 39 40 // Don't merge control values if b is likely to be bypassed anyway. 41 if p.Likely == BranchLikely && p.Succs[0].Block() != b { 42 return false 43 } 44 if p.Likely == BranchUnlikely && p.Succs[1].Block() != b { 45 return false 46 } 47 48 // Check if the control values combine to make an integer inequality that 49 // can be further optimized later. 50 bc := b.Controls[0] 51 pc := p.Controls[0] 52 if !areMergeableInequalities(bc, pc) { 53 return false 54 } 55 56 // If the first (true) successors match then we have a disjunction (||). 57 // If the second (false) successors match then we have a conjunction (&&). 58 for i, op := range [2]Op{OpOrB, OpAndB} { 59 if p.Succs[i].Block() != b.Succs[i].Block() { 60 continue 61 } 62 63 // TODO(mundaym): should we also check the cost of executing b? 64 // Currently we might speculatively execute b even if b contains 65 // a lot of instructions. We could just check that len(b.Values) 66 // is lower than a fixed amount. Bear in mind however that the 67 // other optimization passes might yet reduce the cost of b 68 // significantly so we shouldn't be overly conservative. 69 if !canSpeculativelyExecute(b) { 70 return false 71 } 72 73 // Logically combine the control values for p and b. 74 v := b.NewValue0(bc.Pos, op, bc.Type) 75 v.AddArg(pc) 76 v.AddArg(bc) 77 78 // Set the combined control value as the control value for b. 79 b.SetControl(v) 80 81 // Modify p so that it jumps directly to b. 82 p.removeEdge(i) 83 p.Kind = BlockPlain 84 p.Likely = BranchUnknown 85 p.ResetControls() 86 87 return true 88 } 89 90 // TODO: could negate condition(s) to merge controls. 91 return false 92 } 93 94 // getConstIntArgIndex returns the index of the first argument that is a 95 // constant integer or -1 if no such argument exists. 96 func getConstIntArgIndex(v *Value) int { 97 for i, a := range v.Args { 98 switch a.Op { 99 case OpConst8, OpConst16, OpConst32, OpConst64: 100 return i 101 } 102 } 103 return -1 104 } 105 106 // isSignedInequality reports whether op represents the inequality < or ≤ 107 // in the signed domain. 108 func isSignedInequality(v *Value) bool { 109 switch v.Op { 110 case OpLess64, OpLess32, OpLess16, OpLess8, 111 OpLeq64, OpLeq32, OpLeq16, OpLeq8: 112 return true 113 } 114 return false 115 } 116 117 // isUnsignedInequality reports whether op represents the inequality < or ≤ 118 // in the unsigned domain. 119 func isUnsignedInequality(v *Value) bool { 120 switch v.Op { 121 case OpLess64U, OpLess32U, OpLess16U, OpLess8U, 122 OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U: 123 return true 124 } 125 return false 126 } 127 128 func areMergeableInequalities(x, y *Value) bool { 129 // We need both inequalities to be either in the signed or unsigned domain. 130 // TODO(mundaym): it would also be good to merge when we have an Eq op that 131 // could be transformed into a Less/Leq. For example in the unsigned 132 // domain 'x == 0 || 3 < x' is equivalent to 'x <= 0 || 3 < x' 133 inequalityChecks := [...]func(*Value) bool{ 134 isSignedInequality, 135 isUnsignedInequality, 136 } 137 for _, f := range inequalityChecks { 138 if !f(x) || !f(y) { 139 continue 140 } 141 142 // Check that both inequalities are comparisons with constants. 143 xi := getConstIntArgIndex(x) 144 if xi < 0 { 145 return false 146 } 147 yi := getConstIntArgIndex(y) 148 if yi < 0 { 149 return false 150 } 151 152 // Check that the non-constant arguments to the inequalities 153 // are the same. 154 return x.Args[xi^1] == y.Args[yi^1] 155 } 156 return false 157 } 158