1 // Copyright 2016 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 // A copy of the code in ../gc/subr.go. 8 // We can't use it directly because it would generate 9 // an import cycle. TODO: move to a common support package. 10 11 // argument passing to/from 12 // smagic and umagic 13 type magic struct { 14 W int // input for both - width 15 S int // output for both - shift 16 Bad int // output for both - unexpected failure 17 18 // magic multiplier for signed literal divisors 19 Sd int64 // input - literal divisor 20 Sm int64 // output - multiplier 21 22 // magic multiplier for unsigned literal divisors 23 Ud uint64 // input - literal divisor 24 Um uint64 // output - multiplier 25 Ua int // output - adder 26 } 27 28 // magic number for signed division 29 // see hacker's delight chapter 10 30 func smagic(m *magic) { 31 var mask uint64 32 33 m.Bad = 0 34 switch m.W { 35 default: 36 m.Bad = 1 37 return 38 39 case 8: 40 mask = 0xff 41 42 case 16: 43 mask = 0xffff 44 45 case 32: 46 mask = 0xffffffff 47 48 case 64: 49 mask = 0xffffffffffffffff 50 } 51 52 two31 := mask ^ (mask >> 1) 53 54 p := m.W - 1 55 ad := uint64(m.Sd) 56 if m.Sd < 0 { 57 ad = -uint64(m.Sd) 58 } 59 60 // bad denominators 61 if ad == 0 || ad == 1 || ad == two31 { 62 m.Bad = 1 63 return 64 } 65 66 t := two31 67 ad &= mask 68 69 anc := t - 1 - t%ad 70 anc &= mask 71 72 q1 := two31 / anc 73 r1 := two31 - q1*anc 74 q1 &= mask 75 r1 &= mask 76 77 q2 := two31 / ad 78 r2 := two31 - q2*ad 79 q2 &= mask 80 r2 &= mask 81 82 var delta uint64 83 for { 84 p++ 85 q1 <<= 1 86 r1 <<= 1 87 q1 &= mask 88 r1 &= mask 89 if r1 >= anc { 90 q1++ 91 r1 -= anc 92 q1 &= mask 93 r1 &= mask 94 } 95 96 q2 <<= 1 97 r2 <<= 1 98 q2 &= mask 99 r2 &= mask 100 if r2 >= ad { 101 q2++ 102 r2 -= ad 103 q2 &= mask 104 r2 &= mask 105 } 106 107 delta = ad - r2 108 delta &= mask 109 if q1 < delta || (q1 == delta && r1 == 0) { 110 continue 111 } 112 113 break 114 } 115 116 m.Sm = int64(q2 + 1) 117 if uint64(m.Sm)&two31 != 0 { 118 m.Sm |= ^int64(mask) 119 } 120 m.S = p - m.W 121 } 122 123 // magic number for unsigned division 124 // see hacker's delight chapter 10 125 func umagic(m *magic) { 126 var mask uint64 127 128 m.Bad = 0 129 m.Ua = 0 130 131 switch m.W { 132 default: 133 m.Bad = 1 134 return 135 136 case 8: 137 mask = 0xff 138 139 case 16: 140 mask = 0xffff 141 142 case 32: 143 mask = 0xffffffff 144 145 case 64: 146 mask = 0xffffffffffffffff 147 } 148 149 two31 := mask ^ (mask >> 1) 150 151 m.Ud &= mask 152 if m.Ud == 0 || m.Ud == two31 { 153 m.Bad = 1 154 return 155 } 156 157 nc := mask - (-m.Ud&mask)%m.Ud 158 p := m.W - 1 159 160 q1 := two31 / nc 161 r1 := two31 - q1*nc 162 q1 &= mask 163 r1 &= mask 164 165 q2 := (two31 - 1) / m.Ud 166 r2 := (two31 - 1) - q2*m.Ud 167 q2 &= mask 168 r2 &= mask 169 170 var delta uint64 171 for { 172 p++ 173 if r1 >= nc-r1 { 174 q1 <<= 1 175 q1++ 176 r1 <<= 1 177 r1 -= nc 178 } else { 179 q1 <<= 1 180 r1 <<= 1 181 } 182 183 q1 &= mask 184 r1 &= mask 185 if r2+1 >= m.Ud-r2 { 186 if q2 >= two31-1 { 187 m.Ua = 1 188 } 189 190 q2 <<= 1 191 q2++ 192 r2 <<= 1 193 r2++ 194 r2 -= m.Ud 195 } else { 196 if q2 >= two31 { 197 m.Ua = 1 198 } 199 200 q2 <<= 1 201 r2 <<= 1 202 r2++ 203 } 204 205 q2 &= mask 206 r2 &= mask 207 208 delta = m.Ud - 1 - r2 209 delta &= mask 210 211 if p < m.W+m.W { 212 if q1 < delta || (q1 == delta && r1 == 0) { 213 continue 214 } 215 } 216 217 break 218 } 219 220 m.Um = q2 + 1 221 m.S = p - m.W 222 } 223 224 // adaptors for use by rewrite rules 225 func smagic64ok(d int64) bool { 226 m := magic{W: 64, Sd: d} 227 smagic(&m) 228 return m.Bad == 0 229 } 230 func smagic64m(d int64) int64 { 231 m := magic{W: 64, Sd: d} 232 smagic(&m) 233 return m.Sm 234 } 235 func smagic64s(d int64) int64 { 236 m := magic{W: 64, Sd: d} 237 smagic(&m) 238 return int64(m.S) 239 } 240 241 func umagic64ok(d int64) bool { 242 m := magic{W: 64, Ud: uint64(d)} 243 umagic(&m) 244 return m.Bad == 0 245 } 246 func umagic64m(d int64) int64 { 247 m := magic{W: 64, Ud: uint64(d)} 248 umagic(&m) 249 return int64(m.Um) 250 } 251 func umagic64s(d int64) int64 { 252 m := magic{W: 64, Ud: uint64(d)} 253 umagic(&m) 254 return int64(m.S) 255 } 256 func umagic64a(d int64) bool { 257 m := magic{W: 64, Ud: uint64(d)} 258 umagic(&m) 259 return m.Ua != 0 260 } 261
