rv64: Skip extensions that registers already have
d09d682d1b771f6f60a1beaad93320d302aabc5835589325c5f2f87648463e3a
Narrow values have undefined high bits in IL, so instruction selection extended every word operand of a comparison and every array or slice index, usually with two instructions, even when the instruction that produced the value had already extended it. In loops these extensions cost more than the bounds checks. Selection now finds, for each register of a function, the widths whose sign and zero extension it holds, from the instructions it emits for the definition: word arithmetic sign-extends, narrow loads and extensions extend, comparisons give zero or one, and bitwise operations and copies combine their operands. Block parameters take what holds for every incoming argument, at a fixed point. Comparisons, divisors, indices and `zext`/`sext` skip extensions that these facts prove, and two zero-extended words are compared as they are. An array of at most 2^31 elements takes a sign-extended index directly, because the unsigned check rejects any index with its high bits set. Slices still zero-extend other indices, so longer slices keep every index. Word multiplication by 2, 4 or 8 uses `slliw`, so that it sign-extends like other word arithmetic. A word load now uses `lw`, like word arithmetic, unless an instruction can observe its high bits: a 64-bit operation, store, switch, call, return, or slice index, directly or through copies, block arguments and bitwise operations. Those loads keep `lwu`, so code that uses loaded words in 64-bit operations sees the same bits as before. The facts follow the emitted instructions, so they hold for any input RIL. The prog.* fixtures run 18.4% fewer instructions (geometric mean), 32.8% in total, than before the logical condition change. The compiler built by itself compiles its source in 11.5% fewer instructions, with identical output. Each analysis makes one full pass and then revisits only the instructions that depend on other registers. Assisted-by: Claude:opus-5.5
1 parent
adb500c3
lib/std/arch/rv64.rad
+1 -1
| 376 | 376 | // so the restore below reclaims no live storage. |
|
| 377 | 377 | let ralloc = try regalloc::allocate(func, &config, arena) catch { |
|
| 378 | 378 | restoreArena(arena, checkpoint); |
|
| 379 | 379 | throw Error::Allocation; |
|
| 380 | 380 | }; |
|
| 381 | - | try isel::selectFn(&mut generator.e, ralloc, func, layouts) catch error { |
|
| 381 | + | try isel::selectFn(&mut generator.e, ralloc, func, layouts, arena) catch error { |
|
| 382 | 382 | restoreArena(arena, checkpoint); |
|
| 383 | 383 | throw error; |
|
| 384 | 384 | }; |
|
| 385 | 385 | // Reclaim unused memory after instruction selection. |
|
| 386 | 386 | restoreArena(arena, checkpoint); |
lib/std/arch/rv64/isel.rad
+608 -37
| 26 | 26 | //! loadVal(rd, val) -> Reg |
|
| 27 | 27 | //! Force an [`il::Val`] into a specific register `rd`. Built on [`resolveVal`] + [`emitMv`]. |
|
| 28 | 28 | //! Used when the instruction requires the value in `rd` (e.g. `sub rd, rd, rs2`). |
|
| 29 | 29 | ||
| 30 | 30 | use std::mem; |
|
| 31 | + | use std::lang::alloc; |
|
| 31 | 32 | use std::lang::il; |
|
| 32 | 33 | use std::lang::gen; |
|
| 33 | 34 | use std::lang::gen::regalloc; |
|
| 34 | 35 | use std::lang::gen::labels; |
|
| 35 | 36 |
| 111 | 112 | /// Next synthetic block index for skip-branch targets. |
|
| 112 | 113 | nextSynthBlock: u32, |
|
| 113 | 114 | /// Bytes by which SP is lowered for the stack arguments of the call being |
|
| 114 | 115 | /// selected. Zero outside such a call. SP-relative frame offsets add it. |
|
| 115 | 116 | argAdjust: i32, |
|
| 117 | + | /// Known high bits of the register of each SSA value. |
|
| 118 | + | exts: *[Extension], |
|
| 119 | + | /// Whether an instruction can observe the high bits of each SSA value. |
|
| 120 | + | observed: *[bool], |
|
| 121 | + | } |
|
| 122 | + | ||
| 123 | + | ///////////////////////// |
|
| 124 | + | // Register Extensions // |
|
| 125 | + | ///////////////////////// |
|
| 126 | + | ||
| 127 | + | /// High bits of the register of an SSA value: the widths of 8, 16, 32 or 64 bits |
|
| 128 | + | /// that the register is the sign extension and the zero extension of. A width of |
|
| 129 | + | /// 64 says nothing. Narrow values have undefined high bits, so comparisons and |
|
| 130 | + | /// indices extend them, unless the instruction that [`selectInstr`] emits for the |
|
| 131 | + | /// definition of the value already did. |
|
| 132 | + | record Extension: Copy { |
|
| 133 | + | /// Width whose sign extension the register holds. |
|
| 134 | + | sign: u8, |
|
| 135 | + | /// Width whose zero extension the register holds. |
|
| 136 | + | zero: u8, |
|
| 137 | + | } |
|
| 138 | + | ||
| 139 | + | /// Extension of a register whose high bits are unknown. |
|
| 140 | + | constant UNKNOWN: Extension = Extension { sign: 64, zero: 64 }; |
|
| 141 | + | /// Extension of a register whose definition is not visited yet. It is where the |
|
| 142 | + | /// fixed point starts, and no register keeps it. |
|
| 143 | + | constant UNVISITED: Extension = Extension { sign: 0, zero: 0 }; |
|
| 144 | + | /// Extension of a register that holds zero or one. |
|
| 145 | + | constant BOOLEAN: Extension = Extension { sign: 8, zero: 8 }; |
|
| 146 | + | /// Extension of the result of an RV64 word instruction. |
|
| 147 | + | constant WORD: Extension = Extension { sign: 32, zero: 64 }; |
|
| 148 | + | /// Largest array length for which a passed bounds check proves that a |
|
| 149 | + | /// sign-extended word index equals its zero extension. A larger index has its |
|
| 150 | + | /// high bits set, so it fails the unsigned check. |
|
| 151 | + | constant MAX_SIGNED_INDEX_COUNT: u32 = 0x80000000; |
|
| 152 | + | ||
| 153 | + | /// Extension from the sign and zero widths. A register that is zero above a width |
|
| 154 | + | /// is also the sign extension of the next wider width. |
|
| 155 | + | fn extension(sign: u32, zero: u32) -> Extension { |
|
| 156 | + | let wider = zero * 2; |
|
| 157 | + | return Extension { sign: (sign if sign < wider else wider) as u8, zero: zero as u8 }; |
|
| 158 | + | } |
|
| 159 | + | ||
| 160 | + | /// Extension of an immediate. |
|
| 161 | + | fn immediateExtension(imm: i64) -> Extension { |
|
| 162 | + | let mut sign: u32 = 64; |
|
| 163 | + | if imm >= I8_MIN and imm <= I8_MAX { |
|
| 164 | + | set sign = 8; |
|
| 165 | + | } else if imm >= I16_MIN and imm <= I16_MAX { |
|
| 166 | + | set sign = 16; |
|
| 167 | + | } else if imm >= I32_MIN and imm <= I32_MAX { |
|
| 168 | + | set sign = 32; |
|
| 169 | + | } |
|
| 170 | + | let mut zero: u32 = 64; |
|
| 171 | + | if imm >= 0 and imm <= U8_MAX { |
|
| 172 | + | set zero = 8; |
|
| 173 | + | } else if imm >= 0 and imm <= U16_MAX { |
|
| 174 | + | set zero = 16; |
|
| 175 | + | } else if imm >= 0 and imm <= U32_MAX { |
|
| 176 | + | set zero = 32; |
|
| 177 | + | } |
|
| 178 | + | return extension(sign, zero); |
|
| 179 | + | } |
|
| 180 | + | ||
| 181 | + | /// Extension of the register that holds `val`. |
|
| 182 | + | fn valueExtension(exts: &[Extension], val: il::Val) -> Extension { |
|
| 183 | + | match val { |
|
| 184 | + | case il::Val::Reg(r) => return exts[r.n], |
|
| 185 | + | case il::Val::Imm(imm) => return immediateExtension(imm), |
|
| 186 | + | else => return UNKNOWN, |
|
| 187 | + | } |
|
| 188 | + | } |
|
| 189 | + | ||
| 190 | + | /// Extension that holds for both `a` and `b`. |
|
| 191 | + | fn meet(a: Extension, b: Extension) -> Extension { |
|
| 192 | + | return Extension { |
|
| 193 | + | sign: a.sign if a.sign > b.sign else b.sign, |
|
| 194 | + | zero: a.zero if a.zero > b.zero else b.zero, |
|
| 195 | + | }; |
|
| 196 | + | } |
|
| 197 | + | ||
| 198 | + | /// Whether a load of `typ` into `dst` sign-extends. A word whose high bits nothing |
|
| 199 | + | /// observes is sign-extended like word arithmetic, so that comparisons with it need |
|
| 200 | + | /// no extension. Other loads zero-extend. |
|
| 201 | + | fn signsWord(observed: &[bool], typ: il::Type, dst: il::Reg) -> bool { |
|
| 202 | + | return typ == il::Type::W32 and not observed[dst.n]; |
|
| 203 | + | } |
|
| 204 | + | ||
| 205 | + | /// Extension of a register that holds the sign or zero extension of `typ` bits, as |
|
| 206 | + | /// narrow loads and extensions leave it. |
|
| 207 | + | fn narrowExtension(typ: il::Type, signed: bool) -> Extension { |
|
| 208 | + | let width = il::typeSize(typ) * 8; |
|
| 209 | + | if width == 64 { |
|
| 210 | + | return UNKNOWN; |
|
| 211 | + | } |
|
| 212 | + | return extension(width, 64) if signed else extension(64, width); |
|
| 213 | + | } |
|
| 214 | + | ||
| 215 | + | /// Extension of the result of a binary operation, from the instructions that |
|
| 216 | + | /// [`selectInstr`] emits for it. |
|
| 217 | + | fn binOpExtension( |
|
| 218 | + | exts: &[Extension], op: il::BinOp, typ: il::Type, a: il::Val, b: il::Val |
|
| 219 | + | ) -> Extension { |
|
| 220 | + | let left = valueExtension(exts, a); |
|
| 221 | + | let right = valueExtension(exts, b); |
|
| 222 | + | match op { |
|
| 223 | + | // Bitwise operations act on each bit of the full registers. |
|
| 224 | + | case il::BinOp::And => { |
|
| 225 | + | let sign = left.sign if left.sign > right.sign else right.sign; |
|
| 226 | + | let zero = left.zero if left.zero < right.zero else right.zero; |
|
| 227 | + | return extension(sign as u32, zero as u32); |
|
| 228 | + | } |
|
| 229 | + | case il::BinOp::Or, il::BinOp::Xor => return meet(left, right), |
|
| 230 | + | case |
|
| 231 | + | il::BinOp::Eq, |
|
| 232 | + | il::BinOp::Ne, |
|
| 233 | + | il::BinOp::Slt, |
|
| 234 | + | il::BinOp::Ult, |
|
| 235 | + | il::BinOp::Sge, |
|
| 236 | + | il::BinOp::Uge => return BOOLEAN, |
|
| 237 | + | case il::BinOp::Mul => { |
|
| 238 | + | // Multiplication by zero or one is a move. |
|
| 239 | + | if b == il::Val::Imm(0) { |
|
| 240 | + | return immediateExtension(0); |
|
| 241 | + | } |
|
| 242 | + | if b == il::Val::Imm(1) { |
|
| 243 | + | return left; |
|
| 244 | + | } |
|
| 245 | + | } |
|
| 246 | + | else => {} |
|
| 247 | + | } |
|
| 248 | + | // The other arithmetic of words uses word instructions. |
|
| 249 | + | return WORD if typ == il::Type::W32 else UNKNOWN; |
|
| 250 | + | } |
|
| 251 | + | ||
| 252 | + | /// Position of an instruction in a function. |
|
| 253 | + | record Position: Copy { |
|
| 254 | + | /// Index of the block. |
|
| 255 | + | block: u32, |
|
| 256 | + | /// Index of the instruction in the block. |
|
| 257 | + | instr: u32, |
|
| 258 | + | } |
|
| 259 | + | ||
| 260 | + | /// Registers whose high bits an instruction can observe. |
|
| 261 | + | record Observed { |
|
| 262 | + | /// Whether the high bits of each register can be observed. |
|
| 263 | + | wide: *mut [bool], |
|
| 264 | + | /// Whether a register was marked since the flag was cleared. |
|
| 265 | + | changed: bool, |
|
| 266 | + | } |
|
| 267 | + | ||
| 268 | + | instance il::RegVisitor for Observed { |
|
| 269 | + | /// Mark the operand as observed. |
|
| 270 | + | fn (o: &mut Observed) visit(reg: il::Reg) { |
|
| 271 | + | mark(o, reg); |
|
| 272 | + | } |
|
| 273 | + | } |
|
| 274 | + | ||
| 275 | + | /// Mark `reg` as observed. |
|
| 276 | + | fn mark(o: &mut Observed, reg: il::Reg) { |
|
| 277 | + | if not o.wide[reg.n] { |
|
| 278 | + | set o.wide[reg.n] = true; |
|
| 279 | + | set o.changed = true; |
|
| 280 | + | } |
|
| 281 | + | } |
|
| 282 | + | ||
| 283 | + | /// Mark the register of `val`, if any, as observed. |
|
| 284 | + | fn observe(o: &mut Observed, val: il::Val) { |
|
| 285 | + | if let case il::Val::Reg(r) = val { |
|
| 286 | + | mark(o, r); |
|
| 287 | + | } |
|
| 288 | + | } |
|
| 289 | + | ||
| 290 | + | /// Mark the arguments that edge `args` passes to observed parameters of block |
|
| 291 | + | /// `target` of `func`. |
|
| 292 | + | fn observeArgs(o: &mut Observed, func: *il::Fn, target: u32, args: il::ArgRange) { |
|
| 293 | + | let params = func.blocks[target].params; |
|
| 294 | + | for val, i in il::argVals(func, args) { |
|
| 295 | + | if i < params.len and o.wide[params[i].value.n] { |
|
| 296 | + | observe(o, val); |
|
| 297 | + | } |
|
| 298 | + | } |
|
| 299 | + | } |
|
| 300 | + | ||
| 301 | + | /// Whether a binary operation of narrow values leaves the high bits of its operands |
|
| 302 | + | /// in its result. Words use word instructions, except for bitwise operations and the |
|
| 303 | + | /// move that multiplies by one. Comparisons extend their operands. |
|
| 304 | + | fn keepsHighBits(op: il::BinOp, typ: il::Type, b: il::Val) -> bool { |
|
| 305 | + | match op { |
|
| 306 | + | case |
|
| 307 | + | il::BinOp::Eq, |
|
| 308 | + | il::BinOp::Ne, |
|
| 309 | + | il::BinOp::Slt, |
|
| 310 | + | il::BinOp::Ult, |
|
| 311 | + | il::BinOp::Sge, |
|
| 312 | + | il::BinOp::Uge => return false, |
|
| 313 | + | case il::BinOp::And, il::BinOp::Or, il::BinOp::Xor => return true, |
|
| 314 | + | case il::BinOp::Mul => return typ <> il::Type::W32 or b == il::Val::Imm(1), |
|
| 315 | + | else => return typ <> il::Type::W32, |
|
| 316 | + | } |
|
| 317 | + | } |
|
| 318 | + | ||
| 319 | + | /// Mark the operands of `instr` whose high bits it observes. Returns whether that |
|
| 320 | + | /// depends on what is observed of its result or of the parameters of its targets. |
|
| 321 | + | fn observeOperands(o: &mut Observed, func: *il::Fn, instr: il::Instr) -> bool { |
|
| 322 | + | match instr { |
|
| 323 | + | case il::Instr::BinOp { op, typ, dst, a, b } => { |
|
| 324 | + | if typ == il::Type::W64 { |
|
| 325 | + | observe(o, a); |
|
| 326 | + | observe(o, b); |
|
| 327 | + | return false; |
|
| 328 | + | } |
|
| 329 | + | if not keepsHighBits(op, typ, b) { |
|
| 330 | + | return false; |
|
| 331 | + | } |
|
| 332 | + | if o.wide[dst.n] { |
|
| 333 | + | observe(o, a); |
|
| 334 | + | observe(o, b); |
|
| 335 | + | } |
|
| 336 | + | } |
|
| 337 | + | case il::Instr::UnOp { op, typ, dst, a } => { |
|
| 338 | + | if typ == il::Type::W64 { |
|
| 339 | + | observe(o, a); |
|
| 340 | + | return false; |
|
| 341 | + | } |
|
| 342 | + | if typ == il::Type::W32 and op <> il::UnOp::Not { |
|
| 343 | + | return false; |
|
| 344 | + | } |
|
| 345 | + | if o.wide[dst.n] { |
|
| 346 | + | observe(o, a); |
|
| 347 | + | } |
|
| 348 | + | } |
|
| 349 | + | case il::Instr::Copy { dst, val } => { |
|
| 350 | + | if o.wide[dst.n] { |
|
| 351 | + | observe(o, val); |
|
| 352 | + | } |
|
| 353 | + | } |
|
| 354 | + | case il::Instr::Zext { typ, val, .. } => { |
|
| 355 | + | if typ == il::Type::W64 { |
|
| 356 | + | observe(o, val); |
|
| 357 | + | } |
|
| 358 | + | return false; |
|
| 359 | + | } |
|
| 360 | + | case il::Instr::Sext { typ, val, .. } => { |
|
| 361 | + | if typ == il::Type::W64 { |
|
| 362 | + | observe(o, val); |
|
| 363 | + | } |
|
| 364 | + | return false; |
|
| 365 | + | } |
|
| 366 | + | case il::Instr::Load { src, .. } => { |
|
| 367 | + | mark(o, src); |
|
| 368 | + | return false; |
|
| 369 | + | } |
|
| 370 | + | case il::Instr::Sload { src, .. } => { |
|
| 371 | + | mark(o, src); |
|
| 372 | + | return false; |
|
| 373 | + | } |
|
| 374 | + | case il::Instr::Store { typ, src, dst, .. } => { |
|
| 375 | + | if typ == il::Type::W64 { |
|
| 376 | + | observe(o, src); |
|
| 377 | + | } |
|
| 378 | + | mark(o, dst); |
|
| 379 | + | return false; |
|
| 380 | + | } |
|
| 381 | + | case il::Instr::Field { src, .. } => { |
|
| 382 | + | mark(o, src); |
|
| 383 | + | return false; |
|
| 384 | + | } |
|
| 385 | + | case il::Instr::Elem { base, index, count, .. } => { |
|
| 386 | + | mark(o, base); |
|
| 387 | + | if count > MAX_SIGNED_INDEX_COUNT { |
|
| 388 | + | observe(o, index); |
|
| 389 | + | } |
|
| 390 | + | return false; |
|
| 391 | + | } |
|
| 392 | + | case il::Instr::SliceElem { slice, index, .. } => { |
|
| 393 | + | mark(o, slice); |
|
| 394 | + | observe(o, index); |
|
| 395 | + | return false; |
|
| 396 | + | } |
|
| 397 | + | case il::Instr::Call { func: callee, args, .. } => { |
|
| 398 | + | observe(o, callee); |
|
| 399 | + | for arg in il::argVals(func, args) { |
|
| 400 | + | observe(o, arg); |
|
| 401 | + | } |
|
| 402 | + | return false; |
|
| 403 | + | } |
|
| 404 | + | case il::Instr::Ret { val } => { |
|
| 405 | + | if let v = val { |
|
| 406 | + | observe(o, v); |
|
| 407 | + | } |
|
| 408 | + | return false; |
|
| 409 | + | } |
|
| 410 | + | case il::Instr::Jmp { target, args } => { |
|
| 411 | + | observeArgs(o, func, target, args); |
|
| 412 | + | return args.len > 0; |
|
| 413 | + | } |
|
| 414 | + | case il::Instr::Br { typ, a, b, thenTarget, thenArgs, elseTarget, elseArgs, .. } => { |
|
| 415 | + | if typ == il::Type::W64 { |
|
| 416 | + | observe(o, a); |
|
| 417 | + | observe(o, b); |
|
| 418 | + | } |
|
| 419 | + | observeArgs(o, func, thenTarget, thenArgs); |
|
| 420 | + | observeArgs(o, func, elseTarget, elseArgs); |
|
| 421 | + | return thenArgs.len > 0 or elseArgs.len > 0; |
|
| 422 | + | } |
|
| 423 | + | case il::Instr::Switch { val, defaultTarget, defaultArgs, cases } => { |
|
| 424 | + | observe(o, val); |
|
| 425 | + | observeArgs(o, func, defaultTarget, defaultArgs); |
|
| 426 | + | for c in il::switchCases(func, cases) { |
|
| 427 | + | observeArgs(o, func, c.target, c.args); |
|
| 428 | + | } |
|
| 429 | + | return true; |
|
| 430 | + | } |
|
| 431 | + | else => { |
|
| 432 | + | il::forEachReg(func, instr, o); |
|
| 433 | + | return false; |
|
| 434 | + | } |
|
| 435 | + | } |
|
| 436 | + | return true; |
|
| 437 | + | } |
|
| 438 | + | ||
| 439 | + | /// Find the registers whose high bits an instruction can observe: a 64-bit |
|
| 440 | + | /// operation, a switch, memory, a call, or a return. Slice indices and bounds are |
|
| 441 | + | /// zero-extended, so they observe the high bits too: a zero-extended word is used |
|
| 442 | + | /// as it is. Copies, block arguments and operations that keep high bits pass the |
|
| 443 | + | /// observation on to their operands. Comparisons, array indices, narrow stores and |
|
| 444 | + | /// extensions extend or ignore the high bits. Instructions not listed here observe |
|
| 445 | + | /// all their operands. |
|
| 446 | + | /// |
|
| 447 | + | /// A first pass visits every instruction, and later passes revisit those that pass |
|
| 448 | + | /// observations on, until none is added. Uses mostly follow definitions, so the |
|
| 449 | + | /// passes visit instructions backwards. |
|
| 450 | + | fn observedRegisters(func: *il::Fn, count: u32, arena: &mut alloc::Arena) -> *[bool] |
|
| 451 | + | throws (alloc::AllocError) |
|
| 452 | + | { |
|
| 453 | + | let mut wide: *mut [bool] = &mut []; |
|
| 454 | + | try wide.resize(count, false, arena); |
|
| 455 | + | let mut o = Observed { wide, changed: false }; |
|
| 456 | + | let mut revisit: *mut [Position] = &mut []; |
|
| 457 | + | let mut b = func.blocks.len; |
|
| 458 | + | while b > 0 { |
|
| 459 | + | set b -= 1; |
|
| 460 | + | let instrs = func.blocks[b].instrs; |
|
| 461 | + | let mut i = instrs.len; |
|
| 462 | + | while i > 0 { |
|
| 463 | + | set i -= 1; |
|
| 464 | + | if observeOperands(&mut o, func, instrs[i]) { |
|
| 465 | + | try revisit.append(Position { block: b, instr: i }, arena); |
|
| 466 | + | } |
|
| 467 | + | } |
|
| 468 | + | } |
|
| 469 | + | while o.changed { |
|
| 470 | + | set o.changed = false; |
|
| 471 | + | for k in 0..revisit.len { |
|
| 472 | + | let p = revisit[k]; |
|
| 473 | + | let _ = observeOperands(&mut o, func, func.blocks[p.block].instrs[p.instr]); |
|
| 474 | + | } |
|
| 475 | + | } |
|
| 476 | + | return &o.wide[..]; |
|
| 477 | + | } |
|
| 478 | + | ||
| 479 | + | /// Known extensions of the registers of a function. |
|
| 480 | + | record Extensions { |
|
| 481 | + | /// Extension of each register. |
|
| 482 | + | exts: *mut [Extension], |
|
| 483 | + | /// Whether an extension changed since the flag was cleared. |
|
| 484 | + | changed: bool, |
|
| 485 | + | } |
|
| 486 | + | ||
| 487 | + | /// Set the extension of `reg` to `ext`. |
|
| 488 | + | fn update(x: &mut Extensions, reg: il::Reg, ext: Extension) { |
|
| 489 | + | if ext <> x.exts[reg.n] { |
|
| 490 | + | set x.exts[reg.n] = ext; |
|
| 491 | + | set x.changed = true; |
|
| 492 | + | } |
|
| 493 | + | } |
|
| 494 | + | ||
| 495 | + | /// Weaken the extensions of the parameters of block `target` of `func` to hold for |
|
| 496 | + | /// the arguments `args`. |
|
| 497 | + | fn meetArgs(x: &mut Extensions, func: *il::Fn, target: u32, args: il::ArgRange) { |
|
| 498 | + | let params = func.blocks[target].params; |
|
| 499 | + | for val, i in il::argVals(func, args) { |
|
| 500 | + | if i < params.len { |
|
| 501 | + | let param = params[i].value; |
|
| 502 | + | update(x, param, meet(x.exts[param.n], valueExtension(&x.exts[..], val))); |
|
| 503 | + | } |
|
| 504 | + | } |
|
| 505 | + | } |
|
| 506 | + | ||
| 507 | + | /// Set the extension of the register that `instr` defines, and weaken those of the |
|
| 508 | + | /// parameters it passes arguments to. Returns whether that depends on the extensions |
|
| 509 | + | /// of other registers. |
|
| 510 | + | fn defineExtension(x: &mut Extensions, func: *il::Fn, observed: &[bool], instr: il::Instr) -> bool { |
|
| 511 | + | match instr { |
|
| 512 | + | case il::Instr::BinOp { op, typ, dst, a, b } => { |
|
| 513 | + | update(x, dst, binOpExtension(&x.exts[..], op, typ, a, b)); |
|
| 514 | + | match op { |
|
| 515 | + | case il::BinOp::And, il::BinOp::Or, il::BinOp::Xor => return true, |
|
| 516 | + | case il::BinOp::Mul => return b == il::Val::Imm(1), |
|
| 517 | + | else => return false, |
|
| 518 | + | } |
|
| 519 | + | } |
|
| 520 | + | case il::Instr::UnOp { op, typ, dst, a } => { |
|
| 521 | + | if op == il::UnOp::Not { |
|
| 522 | + | update(x, dst, Extension { sign: valueExtension(&x.exts[..], a).sign, zero: 64 }); |
|
| 523 | + | return true; |
|
| 524 | + | } |
|
| 525 | + | update(x, dst, WORD if typ == il::Type::W32 else UNKNOWN); |
|
| 526 | + | } |
|
| 527 | + | case il::Instr::Copy { dst, val } => { |
|
| 528 | + | update(x, dst, valueExtension(&x.exts[..], val)); |
|
| 529 | + | return true; |
|
| 530 | + | } |
|
| 531 | + | case il::Instr::Load { typ, dst, .. } => |
|
| 532 | + | update(x, dst, narrowExtension(typ, signsWord(observed, typ, dst))), |
|
| 533 | + | case il::Instr::Sload { typ, dst, .. } => update(x, dst, narrowExtension(typ, true)), |
|
| 534 | + | case il::Instr::Zext { typ, dst, .. } => update(x, dst, narrowExtension(typ, false)), |
|
| 535 | + | case il::Instr::Sext { typ, dst, .. } => update(x, dst, narrowExtension(typ, true)), |
|
| 536 | + | case il::Instr::Jmp { target, args } => { |
|
| 537 | + | meetArgs(x, func, target, args); |
|
| 538 | + | return args.len > 0; |
|
| 539 | + | } |
|
| 540 | + | case il::Instr::Br { thenTarget, thenArgs, elseTarget, elseArgs, .. } => { |
|
| 541 | + | meetArgs(x, func, thenTarget, thenArgs); |
|
| 542 | + | meetArgs(x, func, elseTarget, elseArgs); |
|
| 543 | + | return thenArgs.len > 0 or elseArgs.len > 0; |
|
| 544 | + | } |
|
| 545 | + | case il::Instr::Switch { defaultTarget, defaultArgs, cases, .. } => { |
|
| 546 | + | meetArgs(x, func, defaultTarget, defaultArgs); |
|
| 547 | + | for c in il::switchCases(func, cases) { |
|
| 548 | + | meetArgs(x, func, c.target, c.args); |
|
| 549 | + | } |
|
| 550 | + | return true; |
|
| 551 | + | } |
|
| 552 | + | else => { |
|
| 553 | + | if let dst = il::instrDst(instr) { |
|
| 554 | + | update(x, dst, UNKNOWN); |
|
| 555 | + | } |
|
| 556 | + | } |
|
| 557 | + | } |
|
| 558 | + | return false; |
|
| 559 | + | } |
|
| 560 | + | ||
| 561 | + | /// Find the extension of each of the `count` registers of `func`, from the |
|
| 562 | + | /// instructions that [`selectInstr`] emits for their definitions. Block parameters |
|
| 563 | + | /// hold the extension of the arguments of every incoming edge. Registers that other |
|
| 564 | + | /// instructions define have unknown high bits. |
|
| 565 | + | /// |
|
| 566 | + | /// Starting from unvisited registers, a first pass visits every instruction, and |
|
| 567 | + | /// later passes revisit those that depend on other registers, until no extension |
|
| 568 | + | /// changes. Every definition and edge then agrees with the extensions. |
|
| 569 | + | fn extensions( |
|
| 570 | + | func: *il::Fn, observed: &[bool], count: u32, arena: &mut alloc::Arena |
|
| 571 | + | ) -> *[Extension] throws (alloc::AllocError) { |
|
| 572 | + | let mut exts: *mut [Extension] = &mut []; |
|
| 573 | + | try exts.resize(count, UNVISITED, arena); |
|
| 574 | + | for param in func.params { |
|
| 575 | + | set exts[param.value.n] = UNKNOWN; |
|
| 576 | + | } |
|
| 577 | + | let mut x = Extensions { exts, changed: false }; |
|
| 578 | + | let mut revisit: *mut [Position] = &mut []; |
|
| 579 | + | for block, b in func.blocks { |
|
| 580 | + | for i in 0..block.instrs.len { |
|
| 581 | + | if defineExtension(&mut x, func, observed, block.instrs[i]) { |
|
| 582 | + | try revisit.append(Position { block: b, instr: i }, arena); |
|
| 583 | + | } |
|
| 584 | + | } |
|
| 585 | + | } |
|
| 586 | + | while x.changed { |
|
| 587 | + | set x.changed = false; |
|
| 588 | + | for k in 0..revisit.len { |
|
| 589 | + | let p = revisit[k]; |
|
| 590 | + | let _ = defineExtension(&mut x, func, observed, func.blocks[p.block].instrs[p.instr]); |
|
| 591 | + | } |
|
| 592 | + | } |
|
| 593 | + | return &x.exts[..]; |
|
| 594 | + | } |
|
| 595 | + | ||
| 596 | + | /// Whether the register of `val` holds the sign extension, or for `signed` false |
|
| 597 | + | /// the zero extension, of its low `typ` bits. |
|
| 598 | + | fn isExtended(s: &Selector, val: il::Val, typ: il::Type, signed: bool) -> bool { |
|
| 599 | + | if let case il::Val::Reg(r) = val { |
|
| 600 | + | let ext = s.exts[r.n]; |
|
| 601 | + | let width = ext.sign if signed else ext.zero; |
|
| 602 | + | return width as u32 <= il::typeSize(typ) * 8; |
|
| 603 | + | } |
|
| 604 | + | return isExtendedImm(val, typ, signed); |
|
| 116 | 605 | } |
|
| 117 | 606 | ||
| 118 | 607 | ///////////////////////// |
|
| 119 | 608 | // Register Allocation // |
|
| 120 | 609 | ///////////////////////// |
| 264 | 753 | let mut divisor = b; |
|
| 265 | 754 | if let case il::Val::Imm(imm) = b { |
|
| 266 | 755 | set divisor = il::Val::Imm(canonicalCmpImm(imm, typ, signed)); |
|
| 267 | 756 | } |
|
| 268 | 757 | let mut rs2 = try resolveVal(s, e, super::SCRATCH2, divisor); |
|
| 269 | - | if not isExtendedImm(divisor, typ, signed) { |
|
| 758 | + | if not isExtended(s, divisor, typ, signed) { |
|
| 270 | 759 | set rs2 = try cmpOperand(e, super::SCRATCH2, rs2, typ, signed); |
|
| 271 | 760 | } |
|
| 272 | 761 | let mut knownNonZero = false; |
|
| 273 | 762 | if let case il::Val::Imm(imm) = divisor { |
|
| 274 | 763 | set knownNonZero = imm <> 0; |
| 304 | 793 | if let case il::Val::Imm(imm) = val { |
|
| 305 | 794 | try emit::loadImm(e, rd, (imm as u64 & mem::U32_MAX as u64) as i64); |
|
| 306 | 795 | return; |
|
| 307 | 796 | } |
|
| 308 | 797 | let rs = try resolveVal(s, e, scratch, val); |
|
| 798 | + | if isExtended(s, val, il::Type::W32, false) { |
|
| 799 | + | try emitMv(s, e, rd, rs); |
|
| 800 | + | return; |
|
| 801 | + | } |
|
| 309 | 802 | try emit::emit(e, encode::slli(rd, rs, SHIFT_W32)); |
|
| 310 | 803 | try emit::emit(e, encode::srli(rd, rd, SHIFT_W32)); |
|
| 311 | 804 | } |
|
| 312 | 805 | ||
| 806 | + | /// Resolve the word `index` of a bounds check into a register. A register that holds |
|
| 807 | + | /// its zero extension, or for `signed` its sign extension, is used as it is. Other |
|
| 808 | + | /// indices are zero-extended into [`super::SCRATCH1`]. |
|
| 809 | + | fn resolveIndex(s: &mut Selector, e: &mut emit::Emitter, index: il::Val, signed: bool) -> gen::Reg |
|
| 810 | + | throws (super::Error) |
|
| 811 | + | { |
|
| 812 | + | if isExtended(s, index, il::Type::W32, false) |
|
| 813 | + | or (signed and isExtended(s, index, il::Type::W32, true)) |
|
| 814 | + | { |
|
| 815 | + | return try resolveVal(s, e, super::SCRATCH1, index); |
|
| 816 | + | } |
|
| 817 | + | try loadU32(s, e, super::SCRATCH1, super::SCRATCH1, index); |
|
| 818 | + | return super::SCRATCH1; |
|
| 819 | + | } |
|
| 820 | + | ||
| 313 | 821 | /// Trap with `ebreak` unless `a < b`, comparing unsigned. |
|
| 314 | 822 | fn emitTrapUnlessLtu(e: &mut emit::Emitter, a: gen::Reg, b: gen::Reg) throws (super::Error) { |
|
| 315 | 823 | try emit::emit(e, encode::bltu(a, b, super::INSTR_SIZE * 2)); |
|
| 316 | 824 | try emit::emit(e, encode::ebreak()); |
|
| 317 | 825 | } |
| 550 | 1058 | /// Select instructions for a function. |
|
| 551 | 1059 | export fn selectFn( |
|
| 552 | 1060 | e: &mut emit::Emitter, |
|
| 553 | 1061 | ralloc: regalloc::AllocResult, |
|
| 554 | 1062 | func: *il::Fn, |
|
| 555 | - | layouts: &[il::Layout] |
|
| 1063 | + | layouts: &[il::Layout], |
|
| 1064 | + | arena: &mut alloc::Arena |
|
| 556 | 1065 | ) throws (super::Error) { |
|
| 557 | 1066 | // Pre-scan the reserves to give them fixed frame slots. |
|
| 558 | 1067 | let reserved = try reserveSize(func, layouts); |
|
| 559 | 1068 | if reserved > I32_MAX as i32 - ralloc.spill.frameSize { |
|
| 560 | 1069 | throw super::Error::Capacity; |
| 569 | 1078 | ); |
|
| 570 | 1079 | // Record function name for printing. |
|
| 571 | 1080 | try emit::recordFunc(e, func.name); |
|
| 572 | 1081 | // Record function code offset for call patching. |
|
| 573 | 1082 | try emit::recordFuncOffset(e, func.name); |
|
| 1083 | + | // Find the high bits of registers, which do not depend on branch forms. |
|
| 1084 | + | let count = ralloc.assignments.len; |
|
| 1085 | + | let observed = try observedRegisters(func, count, arena) catch { |
|
| 1086 | + | throw super::Error::Allocation; |
|
| 1087 | + | }; |
|
| 1088 | + | let exts = try extensions(func, observed, count, arena) catch { |
|
| 1089 | + | throw super::Error::Allocation; |
|
| 1090 | + | }; |
|
| 574 | 1091 | // Conditional branches start in their short form. When one does not reach |
|
| 575 | 1092 | // its target, the body is emitted again with that branch in its long form. |
|
| 576 | 1093 | let start = emit::beginBody(e); |
|
| 577 | 1094 | loop { |
|
| 578 | - | try selectBody(e, ralloc, func, layouts, &frame); |
|
| 1095 | + | try selectBody(e, ralloc, exts, observed, func, layouts, &frame); |
|
| 579 | 1096 | // Patch local branches now that all blocks are emitted. |
|
| 580 | 1097 | if try emit::patchLocalBranches(e) { |
|
| 581 | 1098 | return; |
|
| 582 | 1099 | } |
|
| 583 | 1100 | emit::rewind(e, start); |
| 586 | 1103 | ||
| 587 | 1104 | /// Emit the prologue, the blocks, and the epilogue of a function. |
|
| 588 | 1105 | fn selectBody( |
|
| 589 | 1106 | e: &mut emit::Emitter, |
|
| 590 | 1107 | ralloc: regalloc::AllocResult, |
|
| 1108 | + | exts: *[Extension], |
|
| 1109 | + | observed: *[bool], |
|
| 591 | 1110 | func: *il::Fn, |
|
| 592 | 1111 | layouts: &[il::Layout], |
|
| 593 | 1112 | frame: &emit::Frame |
|
| 594 | 1113 | ) throws (super::Error) { |
|
| 595 | 1114 | // Reset block offsets for this function. |
| 601 | 1120 | reserveOffset: 0, |
|
| 602 | 1121 | pendingSpill: nil, |
|
| 603 | 1122 | instrIndex: 0, |
|
| 604 | 1123 | nextSynthBlock: func.blocks.len + 1, |
|
| 605 | 1124 | argAdjust: 0, |
|
| 1125 | + | exts, |
|
| 1126 | + | observed, |
|
| 606 | 1127 | }; |
|
| 607 | 1128 | // Emit prologue. |
|
| 608 | 1129 | try emit::emitPrologue(e, frame); |
|
| 609 | 1130 | ||
| 610 | 1131 | // Move function params from arg registers to assigned registers. |
| 693 | 1214 | ) throws (super::Error) { |
|
| 694 | 1215 | match instr { |
|
| 695 | 1216 | case il::Instr::BinOp { op, typ, dst, a, b } => { |
|
| 696 | 1217 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 697 | 1218 | let rs1 = try resolveVal(s, e, super::SCRATCH1, a); |
|
| 698 | - | try selectAluBinOp(s, e, op, typ, rd, rs1, b); |
|
| 1219 | + | try selectAluBinOp(s, e, op, typ, rd, rs1, a, b); |
|
| 699 | 1220 | } |
|
| 700 | 1221 | case il::Instr::UnOp { op, typ, dst, a } => { |
|
| 701 | 1222 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 702 | 1223 | let rs = try resolveVal(s, e, super::SCRATCH1, a); |
|
| 703 | 1224 | try selectAluUnOp(s, e, op, typ, rd, rs); |
|
| 704 | 1225 | } |
|
| 705 | 1226 | case il::Instr::Load { typ, dst, src, offset } => { |
|
| 706 | 1227 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 707 | 1228 | let base = try getSrcReg(s, e, src, super::SCRATCH2); |
|
| 708 | - | try emit::emitLoad(e, rd, base, offset, typ); |
|
| 1229 | + | if signsWord(s.observed, typ, dst) { |
|
| 1230 | + | try emit::emitSload(e, rd, base, offset, typ); |
|
| 1231 | + | } else { |
|
| 1232 | + | try emit::emitLoad(e, rd, base, offset, typ); |
|
| 1233 | + | } |
|
| 709 | 1234 | } |
|
| 710 | 1235 | case il::Instr::Sload { typ, dst, src, offset } => { |
|
| 711 | 1236 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 712 | 1237 | let base = try getSrcReg(s, e, src, super::SCRATCH2); |
|
| 713 | 1238 | try emit::emitSload(e, rd, base, offset, typ); |
| 761 | 1286 | try emit::emit(e, encode::ebreak()); |
|
| 762 | 1287 | } |
|
| 763 | 1288 | try emitAddOffset(e, rd, rbase, (k * size as u64) as i64); |
|
| 764 | 1289 | return; |
|
| 765 | 1290 | } |
|
| 766 | - | try loadU32(s, e, super::SCRATCH1, super::SCRATCH1, index); |
|
| 1291 | + | // A sign-extended index above the largest one fails the check, so the |
|
| 1292 | + | // check proves that it equals its zero extension. |
|
| 1293 | + | let ri = try resolveIndex(s, e, index, count <= MAX_SIGNED_INDEX_COUNT); |
|
| 767 | 1294 | try emit::loadImm(e, super::ADDR_SCRATCH, count as i64); |
|
| 768 | - | try emitTrapUnlessLtu(e, super::SCRATCH1, super::ADDR_SCRATCH); |
|
| 769 | - | try emitScale(e, super::ADDR_SCRATCH, super::SCRATCH1, size, super::SCRATCH3); |
|
| 770 | - | try emit::emit(e, encode::add(rd, rbase, super::ADDR_SCRATCH)); |
|
| 1295 | + | try emitTrapUnlessLtu(e, ri, super::ADDR_SCRATCH); |
|
| 1296 | + | if size == 1 { |
|
| 1297 | + | try emit::emit(e, encode::add(rd, rbase, ri)); |
|
| 1298 | + | } else { |
|
| 1299 | + | try emitScale(e, super::ADDR_SCRATCH, ri, size, super::SCRATCH3); |
|
| 1300 | + | try emit::emit(e, encode::add(rd, rbase, super::ADDR_SCRATCH)); |
|
| 1301 | + | } |
|
| 771 | 1302 | } |
|
| 772 | 1303 | case il::Instr::SliceElem { dst, slice, index, layout } => { |
|
| 773 | 1304 | let size = layouts[layout].size; |
|
| 774 | 1305 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 775 | 1306 | let rslice = try getSrcReg(s, e, slice, super::SCRATCH2); |
|
| 776 | - | try loadU32(s, e, super::SCRATCH1, super::SCRATCH1, index); |
|
| 1307 | + | // A slice can be longer than 2^31 elements, so only a zero-extended |
|
| 1308 | + | // index is used as it is. |
|
| 1309 | + | let ri = try resolveIndex(s, e, index, false); |
|
| 777 | 1310 | try emit::emitLoad(e, super::ADDR_SCRATCH, rslice, SLICE_LEN_OFFSET, il::Type::W32); |
|
| 778 | - | try emitTrapUnlessLtu(e, super::SCRATCH1, super::ADDR_SCRATCH); |
|
| 779 | - | try emitScale(e, super::SCRATCH1, super::SCRATCH1, size, super::SCRATCH3); |
|
| 1311 | + | try emitTrapUnlessLtu(e, ri, super::ADDR_SCRATCH); |
|
| 1312 | + | let mut offset = ri; |
|
| 1313 | + | if size <> 1 { |
|
| 1314 | + | try emitScale(e, super::SCRATCH1, ri, size, super::SCRATCH3); |
|
| 1315 | + | set offset = super::SCRATCH1; |
|
| 1316 | + | } |
|
| 780 | 1317 | try emit::emitLd(e, super::ADDR_SCRATCH, rslice, SLICE_PTR_OFFSET); |
|
| 781 | - | try emit::emit(e, encode::add(rd, super::ADDR_SCRATCH, super::SCRATCH1)); |
|
| 1318 | + | try emit::emit(e, encode::add(rd, super::ADDR_SCRATCH, offset)); |
|
| 782 | 1319 | } |
|
| 783 | 1320 | case il::Instr::SliceNew { dst, base, layout, count, start, end } => { |
|
| 784 | 1321 | let size = layouts[layout].size; |
|
| 785 | 1322 | // T6 holds the slot and T3 the start throughout. T5 holds the end, and then the |
|
| 786 | 1323 | // length. T4 holds a value only between operand resolutions, since resolving an |
| 920 | 1457 | } |
|
| 921 | 1458 | } |
|
| 922 | 1459 | case il::Instr::Zext { typ, dst, val } => { |
|
| 923 | 1460 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 924 | 1461 | let rs = try resolveVal(s, e, super::SCRATCH1, val); |
|
| 925 | - | try emitZext(e, rd, rs, typ); |
|
| 1462 | + | if isExtended(s, val, typ, false) { |
|
| 1463 | + | try emitMv(s, e, rd, rs); |
|
| 1464 | + | } else { |
|
| 1465 | + | try emitZext(e, rd, rs, typ); |
|
| 1466 | + | } |
|
| 926 | 1467 | } |
|
| 927 | 1468 | case il::Instr::Sext { typ, dst, val } => { |
|
| 928 | 1469 | let rd = getDstReg(s, dst, super::SCRATCH1); |
|
| 929 | 1470 | let rs = try resolveVal(s, e, super::SCRATCH1, val); |
|
| 930 | - | try emitSext(e, rd, rs, typ); |
|
| 1471 | + | if isExtended(s, val, typ, true) { |
|
| 1472 | + | try emitMv(s, e, rd, rs); |
|
| 1473 | + | } else { |
|
| 1474 | + | try emitSext(e, rd, rs, typ); |
|
| 1475 | + | } |
|
| 931 | 1476 | } |
|
| 932 | 1477 | case il::Instr::Ret { val } => { |
|
| 933 | 1478 | if let v = val { |
|
| 934 | 1479 | let rs = try resolveVal(s, e, super::SCRATCH1, v); |
|
| 935 | 1480 | try emitMv(s, e, super::A0, rs); |
| 970 | 1515 | // Skip extension for zero register. |
|
| 971 | 1516 | let mut signed = false; |
|
| 972 | 1517 | if let case il::CmpOp::Slt = op { |
|
| 973 | 1518 | set signed = true; |
|
| 974 | 1519 | } |
|
| 975 | - | let useSext = cmpUsesSext(typ, signed); |
|
| 976 | - | if not aIsZero and not isExtendedImm(a, typ, useSext) { |
|
| 1520 | + | let useSext = cmpUsesSext(s, typ, signed, a, b); |
|
| 1521 | + | if not aIsZero and not isExtended(s, a, typ, useSext) { |
|
| 977 | 1522 | set rs1 = try cmpOperand(e, super::SCRATCH1, rs1, typ, useSext); |
|
| 978 | 1523 | } |
|
| 979 | - | if not bIsZero and not isExtendedImm(b, typ, useSext) { |
|
| 1524 | + | if not bIsZero and not isExtended(s, b, typ, useSext) { |
|
| 980 | 1525 | set rs2 = try cmpOperand(e, super::SCRATCH2, rs2, typ, useSext); |
|
| 981 | 1526 | } |
|
| 982 | 1527 | // Block-argument moves must only execute on the taken path. |
|
| 983 | 1528 | // When `thenArgs` is non-empty, invert the branch so that the |
|
| 984 | 1529 | // then-moves land on the fall-through (taken) side. |
| 1147 | 1692 | try emit::emit(e, encode::fence()); |
|
| 1148 | 1693 | } |
|
| 1149 | 1694 | } |
|
| 1150 | 1695 | } |
|
| 1151 | 1696 | ||
| 1152 | - | /// Choose the cheapest canonical representation that preserves the comparison. |
|
| 1153 | - | /// RV64 word operations naturally sign-extend, and sign-extension preserves |
|
| 1154 | - | /// unsigned ordering when both operands have the same declared width. |
|
| 1155 | - | fn cmpUsesSext(typ: il::Type, signed: bool) -> bool { |
|
| 1156 | - | return signed or typ == il::Type::W32; |
|
| 1697 | + | /// Choose the cheapest canonical representation of `a` and `b` that preserves the |
|
| 1698 | + | /// comparison. RV64 word operations naturally sign-extend, and sign-extension |
|
| 1699 | + | /// preserves unsigned ordering when both operands have the same declared width. |
|
| 1700 | + | /// Words that are both zero-extended already are compared as they are. |
|
| 1701 | + | fn cmpUsesSext(s: &Selector, typ: il::Type, signed: bool, a: il::Val, b: il::Val) -> bool { |
|
| 1702 | + | if signed { |
|
| 1703 | + | return true; |
|
| 1704 | + | } |
|
| 1705 | + | if typ <> il::Type::W32 { |
|
| 1706 | + | return false; |
|
| 1707 | + | } |
|
| 1708 | + | return not isExtended(s, a, typ, false) or not isExtended(s, b, typ, false); |
|
| 1157 | 1709 | } |
|
| 1158 | 1710 | ||
| 1159 | 1711 | /// Extend a comparison operand to its selected canonical representation. |
|
| 1160 | 1712 | fn emitCmpExt( |
|
| 1161 | 1713 | e: &mut emit::Emitter, |
| 1250 | 1802 | e: &mut emit::Emitter, |
|
| 1251 | 1803 | op: il::BinOp, |
|
| 1252 | 1804 | typ: il::Type, |
|
| 1253 | 1805 | rd: gen::Reg, |
|
| 1254 | 1806 | rs1: gen::Reg, |
|
| 1807 | + | a: il::Val, |
|
| 1255 | 1808 | b: il::Val |
|
| 1256 | 1809 | ) throws (super::Error) { |
|
| 1257 | 1810 | match op { |
|
| 1258 | 1811 | case il::BinOp::Add => { |
|
| 1259 | 1812 | if typ == il::Type::W32 { |
| 1301 | 1854 | return; |
|
| 1302 | 1855 | } else if imm == 1 { |
|
| 1303 | 1856 | try emitMv(s, e, rd, rs1); |
|
| 1304 | 1857 | return; |
|
| 1305 | 1858 | } else if imm == 2 { |
|
| 1306 | - | try emit::emit(e, encode::slli(rd, rs1, 1)); |
|
| 1859 | + | try emitShiftLeft(e, typ, rd, rs1, 1); |
|
| 1307 | 1860 | return; |
|
| 1308 | 1861 | } else if imm == 4 { |
|
| 1309 | - | try emit::emit(e, encode::slli(rd, rs1, 2)); |
|
| 1862 | + | try emitShiftLeft(e, typ, rd, rs1, 2); |
|
| 1310 | 1863 | return; |
|
| 1311 | 1864 | } else if imm == 8 { |
|
| 1312 | - | try emit::emit(e, encode::slli(rd, rs1, 3)); |
|
| 1865 | + | try emitShiftLeft(e, typ, rd, rs1, 3); |
|
| 1313 | 1866 | return; |
|
| 1314 | 1867 | } |
|
| 1315 | 1868 | } |
|
| 1316 | 1869 | let rs2 = try resolveVal(s, e, super::SCRATCH2, b); |
|
| 1317 | 1870 | try emit::emit( |
| 1369 | 1922 | try selectShift(s, e, rd, rs1, b, ShiftOp::Sra, typ), |
|
| 1370 | 1923 | case il::BinOp::Ushr => |
|
| 1371 | 1924 | try selectShift(s, e, rd, rs1, b, ShiftOp::Srl, typ), |
|
| 1372 | 1925 | case il::BinOp::Eq, il::BinOp::Ne => { |
|
| 1373 | 1926 | let mut rs2 = try resolveVal(s, e, super::SCRATCH2, b); |
|
| 1374 | - | let useSext = cmpUsesSext(typ, false); |
|
| 1375 | - | let lhs = try cmpOperand(e, super::SCRATCH1, rs1, typ, useSext); |
|
| 1376 | - | if not isExtendedImm(b, typ, useSext) { |
|
| 1927 | + | let useSext = cmpUsesSext(s, typ, false, a, b); |
|
| 1928 | + | let mut lhs = rs1; |
|
| 1929 | + | if not isExtended(s, a, typ, useSext) { |
|
| 1930 | + | set lhs = try cmpOperand(e, super::SCRATCH1, rs1, typ, useSext); |
|
| 1931 | + | } |
|
| 1932 | + | if not isExtended(s, b, typ, useSext) { |
|
| 1377 | 1933 | set rs2 = try cmpOperand(e, super::SCRATCH2, rs2, typ, useSext); |
|
| 1378 | 1934 | } |
|
| 1379 | 1935 | try emit::emit(e, encode::xor(rd, lhs, rs2)); |
|
| 1380 | 1936 | if let case il::BinOp::Eq = op { |
|
| 1381 | 1937 | try emit::emit(e, encode::sltiu(rd, rd, 1)); |
|
| 1382 | 1938 | } else { |
|
| 1383 | 1939 | try emit::emit(e, encode::sltu(rd, super::ZERO, rd)); |
|
| 1384 | 1940 | } |
|
| 1385 | 1941 | } |
|
| 1386 | 1942 | case il::BinOp::Slt => |
|
| 1387 | - | try selectCmp(s, e, typ, rd, rs1, b, CmpOp::Slt), |
|
| 1943 | + | try selectCmp(s, e, typ, rd, rs1, a, b, CmpOp::Slt), |
|
| 1388 | 1944 | case il::BinOp::Ult => |
|
| 1389 | - | try selectCmp(s, e, typ, rd, rs1, b, CmpOp::Ult), |
|
| 1945 | + | try selectCmp(s, e, typ, rd, rs1, a, b, CmpOp::Ult), |
|
| 1390 | 1946 | case il::BinOp::Sge => |
|
| 1391 | - | try selectCmp(s, e, typ, rd, rs1, b, CmpOp::Sge), |
|
| 1947 | + | try selectCmp(s, e, typ, rd, rs1, a, b, CmpOp::Sge), |
|
| 1392 | 1948 | case il::BinOp::Uge => |
|
| 1393 | - | try selectCmp(s, e, typ, rd, rs1, b, CmpOp::Uge), |
|
| 1949 | + | try selectCmp(s, e, typ, rd, rs1, a, b, CmpOp::Uge), |
|
| 1950 | + | } |
|
| 1951 | + | } |
|
| 1952 | + | ||
| 1953 | + | /// Shift `rs` left by `shift` bits into `rd`, with a word instruction for words, so |
|
| 1954 | + | /// that the result is sign-extended. |
|
| 1955 | + | fn emitShiftLeft(e: &mut emit::Emitter, typ: il::Type, rd: gen::Reg, rs: gen::Reg, shift: i32) |
|
| 1956 | + | throws (super::Error) |
|
| 1957 | + | { |
|
| 1958 | + | if typ == il::Type::W32 { |
|
| 1959 | + | try emit::emit(e, encode::slliw(rd, rs, shift)); |
|
| 1960 | + | } else { |
|
| 1961 | + | try emit::emit(e, encode::slli(rd, rs, shift)); |
|
| 1394 | 1962 | } |
|
| 1395 | 1963 | } |
|
| 1396 | 1964 | ||
| 1397 | 1965 | /// Select a unary ALU operation. |
|
| 1398 | 1966 | fn selectAluUnOp( |
| 1728 | 2296 | s: &mut Selector, |
|
| 1729 | 2297 | e: &mut emit::Emitter, |
|
| 1730 | 2298 | typ: il::Type, |
|
| 1731 | 2299 | rd: gen::Reg, |
|
| 1732 | 2300 | source: gen::Reg, |
|
| 2301 | + | a: il::Val, |
|
| 1733 | 2302 | b: il::Val, |
|
| 1734 | 2303 | op: CmpOp |
|
| 1735 | 2304 | ) throws (super::Error) { |
|
| 1736 | 2305 | // `Sge` and `Uge` compute `Slt` and `Ult`, then invert the result. |
|
| 1737 | 2306 | let mut signed = false; |
| 1747 | 2316 | } |
|
| 1748 | 2317 | case CmpOp::Uge => { |
|
| 1749 | 2318 | set invert = true; |
|
| 1750 | 2319 | } |
|
| 1751 | 2320 | } |
|
| 1752 | - | let useSext = cmpUsesSext(typ, signed); |
|
| 1753 | - | let rs1 = try cmpOperand(e, super::SCRATCH1, source, typ, useSext); |
|
| 1754 | - | ||
| 2321 | + | let useSext = cmpUsesSext(s, typ, signed, a, b); |
|
| 2322 | + | let mut rs1 = source; |
|
| 2323 | + | if not isExtended(s, a, typ, useSext) { |
|
| 2324 | + | set rs1 = try cmpOperand(e, super::SCRATCH1, source, typ, useSext); |
|
| 2325 | + | } |
|
| 1755 | 2326 | // Canonicalizing the immediate can expose an immediate instruction even |
|
| 1756 | 2327 | // when the IL value used a different representation for the same width. |
|
| 1757 | 2328 | let mut rhs = b; |
|
| 1758 | 2329 | if let case il::Val::Imm(imm) = b { |
|
| 1759 | 2330 | let canonical = canonicalCmpImm(imm, typ, useSext); |
| 1770 | 2341 | } |
|
| 1771 | 2342 | return; |
|
| 1772 | 2343 | } |
|
| 1773 | 2344 | } |
|
| 1774 | 2345 | let mut rs2 = try resolveVal(s, e, super::SCRATCH2, rhs); |
|
| 1775 | - | if not isExtendedImm(rhs, typ, useSext) { |
|
| 2346 | + | if not isExtended(s, rhs, typ, useSext) { |
|
| 1776 | 2347 | set rs2 = try cmpOperand(e, super::SCRATCH2, rs2, typ, useSext); |
|
| 1777 | 2348 | } |
|
| 1778 | 2349 | if signed { |
|
| 1779 | 2350 | try emit::emit(e, encode::slt(rd, rs1, rs2)); |
|
| 1780 | 2351 | } else { |
lib/std/arch/rv64/tests.rad
+109 -0
| 642 | 642 | layout: 0, |
|
| 643 | 643 | }; |
|
| 644 | 644 | try testing::expect(selfMoves(try generateBody(&table[..], nil, &[element])) == 0); |
|
| 645 | 645 | } |
|
| 646 | 646 | ||
| 647 | + | /// Number of instructions in `code` that sign- or zero-extend a register from 32 bits: |
|
| 648 | + | /// `addiw` by zero, or `slli` by 32. |
|
| 649 | + | fn wordExtensions(code: *[u32]) -> u32 { |
|
| 650 | + | let mut count: u32 = 0; |
|
| 651 | + | for word in code { |
|
| 652 | + | let isAddiw = (word & 0x7f) == 0x1b and ((word >> 12) & 7) == 0 and (word >> 20) == 0; |
|
| 653 | + | let isSlli32 = (word & 0x7f) == 0x13 and ((word >> 12) & 7) == 1 and (word >> 20) == 32; |
|
| 654 | + | if isAddiw or isSlli32 { |
|
| 655 | + | set count += 1; |
|
| 656 | + | } |
|
| 657 | + | } |
|
| 658 | + | return count; |
|
| 659 | + | } |
|
| 660 | + | ||
| 661 | + | /// Shorthand for the register `%n`. |
|
| 662 | + | fn reg(n: u32) -> il::Val { |
|
| 663 | + | return il::Val::Reg(il::Reg { n }); |
|
| 664 | + | } |
|
| 665 | + | ||
| 666 | + | /// A comparison or index needs no extension of a register that its producer already |
|
| 667 | + | /// extended: 32-bit arithmetic sign-extends and an unsigned load zero-extends. `%0` |
|
| 668 | + | /// and `%1` are parameters with unknown high bits. |
|
| 669 | + | @test unsafe fn testKnownExtensions() throws (testing::TestError) { |
|
| 670 | + | let table = [il::Layout { size: 4, alignment: 4, slots: &[] }]; |
|
| 671 | + | let sum = il::Instr::BinOp { |
|
| 672 | + | op: il::BinOp::Add, typ: il::Type::W32, dst: il::Reg { n: 2 }, a: reg(0), b: il::Val::Imm(1) |
|
| 673 | + | }; |
|
| 674 | + | let loaded = il::Instr::Load { |
|
| 675 | + | typ: il::Type::W32, dst: il::Reg { n: 3 }, src: il::Reg { n: 1 }, offset: 0 |
|
| 676 | + | }; |
|
| 677 | + | // A signed comparison of a sum. |
|
| 678 | + | let less = il::Instr::BinOp { |
|
| 679 | + | op: il::BinOp::Slt, typ: il::Type::W32, dst: il::Reg { n: 4 }, a: reg(2), b: il::Val::Imm(5) |
|
| 680 | + | }; |
|
| 681 | + | try testing::expect(wordExtensions(try generateBody(&table[..], nil, &[sum, less])) == 0); |
|
| 682 | + | // An unsigned comparison of two loaded values. |
|
| 683 | + | let other = il::Instr::Load { |
|
| 684 | + | typ: il::Type::W32, dst: il::Reg { n: 4 }, src: il::Reg { n: 1 }, offset: 4 |
|
| 685 | + | }; |
|
| 686 | + | let below = il::Instr::BinOp { |
|
| 687 | + | op: il::BinOp::Ult, typ: il::Type::W32, dst: il::Reg { n: 5 }, a: reg(3), b: reg(4) |
|
| 688 | + | }; |
|
| 689 | + | try testing::expect( |
|
| 690 | + | wordExtensions(try generateBody(&table[..], nil, &[loaded, other, below])) == 0 |
|
| 691 | + | ); |
|
| 692 | + | // A loaded slice index, and a computed index of a fixed array. |
|
| 693 | + | let element = il::Instr::SliceElem { |
|
| 694 | + | dst: il::Reg { n: 4 }, slice: il::Reg { n: 0 }, index: reg(3), layout: 0 |
|
| 695 | + | }; |
|
| 696 | + | try testing::expect(wordExtensions(try generateBody(&table[..], nil, &[loaded, element])) == 0); |
|
| 697 | + | let fixed = il::Instr::Elem { |
|
| 698 | + | dst: il::Reg { n: 4 }, base: il::Reg { n: 1 }, index: reg(2), layout: 0, count: 4 |
|
| 699 | + | }; |
|
| 700 | + | try testing::expect(wordExtensions(try generateBody(&table[..], nil, &[sum, fixed])) == 0); |
|
| 701 | + | // A loaded value that a 64-bit operation also reads is zero-extended, and a |
|
| 702 | + | // computed one is sign-extended, so one is extended. |
|
| 703 | + | let mixed = il::Instr::BinOp { |
|
| 704 | + | op: il::BinOp::Eq, typ: il::Type::W32, dst: il::Reg { n: 4 }, a: reg(2), b: reg(3) |
|
| 705 | + | }; |
|
| 706 | + | let wide = il::Instr::BinOp { |
|
| 707 | + | op: il::BinOp::Add, typ: il::Type::W64, dst: il::Reg { n: 5 }, a: reg(1), b: reg(3) |
|
| 708 | + | }; |
|
| 709 | + | try testing::expect( |
|
| 710 | + | wordExtensions(try generateBody(&table[..], nil, &[sum, loaded, mixed, wide])) == 1 |
|
| 711 | + | ); |
|
| 712 | + | // A computed index of a slice is zero-extended, so that slices longer than 2^31 |
|
| 713 | + | // elements keep every index. |
|
| 714 | + | let computed = il::Instr::SliceElem { |
|
| 715 | + | dst: il::Reg { n: 4 }, slice: il::Reg { n: 1 }, index: reg(2), layout: 0 |
|
| 716 | + | }; |
|
| 717 | + | try testing::expect(wordExtensions(try generateBody(&table[..], nil, &[sum, computed])) == 1); |
|
| 718 | + | } |
|
| 719 | + | ||
| 720 | + | /// A loaded word whose high bits nothing observes is sign-extended like word |
|
| 721 | + | /// arithmetic, so comparing them needs no extension. A loaded word that a 64-bit |
|
| 722 | + | /// operation reads stays zero-extended. |
|
| 723 | + | @test unsafe fn testLoadedWordExtension() throws (testing::TestError) { |
|
| 724 | + | let table = [il::Layout { size: 4, alignment: 4, slots: &[] }]; |
|
| 725 | + | let sum = il::Instr::BinOp { |
|
| 726 | + | op: il::BinOp::Add, typ: il::Type::W32, dst: il::Reg { n: 2 }, a: reg(0), b: il::Val::Imm(1) |
|
| 727 | + | }; |
|
| 728 | + | let loaded = il::Instr::Load { |
|
| 729 | + | typ: il::Type::W32, dst: il::Reg { n: 3 }, src: il::Reg { n: 1 }, offset: 0 |
|
| 730 | + | }; |
|
| 731 | + | let mixed = il::Instr::BinOp { |
|
| 732 | + | op: il::BinOp::Ult, typ: il::Type::W32, dst: il::Reg { n: 4 }, a: reg(2), b: reg(3) |
|
| 733 | + | }; |
|
| 734 | + | let code = try generateBody(&table[..], nil, &[sum, loaded, mixed]); |
|
| 735 | + | try testing::expect(wordExtensions(code) == 0); |
|
| 736 | + | try testing::expect(loads(code, 2) == 1); |
|
| 737 | + | ||
| 738 | + | let wide = il::Instr::BinOp { |
|
| 739 | + | op: il::BinOp::Add, typ: il::Type::W64, dst: il::Reg { n: 5 }, a: reg(1), b: reg(3) |
|
| 740 | + | }; |
|
| 741 | + | let widened = try generateBody(&table[..], nil, &[sum, loaded, mixed, wide]); |
|
| 742 | + | try testing::expect(loads(widened, 6) == 1); |
|
| 743 | + | } |
|
| 744 | + | ||
| 745 | + | /// Number of loads with `funct3` in `code`: 2 for `lw` and 6 for `lwu`. |
|
| 746 | + | fn loads(code: *[u32], funct3: u32) -> u32 { |
|
| 747 | + | let mut count: u32 = 0; |
|
| 748 | + | for word in code { |
|
| 749 | + | if (word & 0x7f) == 0x03 and ((word >> 12) & 7) == funct3 { |
|
| 750 | + | set count += 1; |
|
| 751 | + | } |
|
| 752 | + | } |
|
| 753 | + | return count; |
|
| 754 | + | } |
|
| 755 | + | ||
| 647 | 756 | /// Helper to check encoding equals expected value. |
|
| 648 | 757 | fn expectEncoding(actual: u32, expected: u32) throws (testing::TestError) { |
|
| 649 | 758 | try testing::expect(actual == expected); |
|
| 650 | 759 | } |
|
| 651 | 760 |
test/tests/cmp.extension.rad
added
+107 -0
| 1 | + | //! returns: 0 |
|
| 2 | + | //! Comparisons and indices agree for narrow values whose registers hold |
|
| 3 | + | //! different high bits: loaded values are zero-extended and 32-bit |
|
| 4 | + | //! arithmetic results are sign-extended. |
|
| 5 | + | ||
| 6 | + | /// Return the sum of `a` and `b`, which wraps to 32 bits. |
|
| 7 | + | fn sum(a: u32, b: u32) -> u32 { |
|
| 8 | + | return a + b; |
|
| 9 | + | } |
|
| 10 | + | ||
| 11 | + | /// Compare loaded and computed unsigned values at and above 2^31. |
|
| 12 | + | fn unsignedValues(values: &[u32]) { |
|
| 13 | + | let top = values[0] + 1; |
|
| 14 | + | assert top == values[1]; |
|
| 15 | + | assert values[1] == top; |
|
| 16 | + | assert top > values[0]; |
|
| 17 | + | assert not (top < values[1]); |
|
| 18 | + | assert values[2] > top; |
|
| 19 | + | let doubled = values[0] * 2; |
|
| 20 | + | assert doubled == values[2] - 1; |
|
| 21 | + | let quadrupled = values[1] * 4; |
|
| 22 | + | assert quadrupled == 0; |
|
| 23 | + | let wrapped = sum(values[2], 1); |
|
| 24 | + | assert wrapped == 0; |
|
| 25 | + | assert values[2] / values[1] == 1; |
|
| 26 | + | assert values[2] % values[1] == 0x7fffffff; |
|
| 27 | + | let wide = values[1] as u64; |
|
| 28 | + | assert wide == 0x80000000; |
|
| 29 | + | assert wide + (values[2] as u64) == 0x17fffffff; |
|
| 30 | + | } |
|
| 31 | + | ||
| 32 | + | /// Compare loaded and computed signed values. |
|
| 33 | + | fn signedValues(values: &[i32]) { |
|
| 34 | + | let minus = values[0] - 1; |
|
| 35 | + | assert minus == values[1]; |
|
| 36 | + | assert minus < values[0]; |
|
| 37 | + | assert values[1] < 0; |
|
| 38 | + | assert values[2] < values[1]; |
|
| 39 | + | assert values[2] - 1 == 0x7fffffff; |
|
| 40 | + | assert (values[1] as u32) > 0x7fffffff; |
|
| 41 | + | } |
|
| 42 | + | ||
| 43 | + | /// Merge a loaded and a computed value through a block parameter. |
|
| 44 | + | fn merged(values: &[u32], loaded: bool) -> u32 { |
|
| 45 | + | let mut v = values[1]; |
|
| 46 | + | if not loaded { |
|
| 47 | + | set v = values[0] + 1; |
|
| 48 | + | } |
|
| 49 | + | if v == 0x80000000 { |
|
| 50 | + | return 1; |
|
| 51 | + | } |
|
| 52 | + | return 0; |
|
| 53 | + | } |
|
| 54 | + | ||
| 55 | + | /// Carry a value of each representation through a loop. |
|
| 56 | + | fn looped(values: &[u32]) -> u32 { |
|
| 57 | + | let mut a = values[1]; |
|
| 58 | + | let mut b = values[0]; |
|
| 59 | + | let mut n: u32 = 0; |
|
| 60 | + | while n < 3 { |
|
| 61 | + | if a == b { |
|
| 62 | + | return n; |
|
| 63 | + | } |
|
| 64 | + | set b += 1; |
|
| 65 | + | set n += 1; |
|
| 66 | + | } |
|
| 67 | + | return 99; |
|
| 68 | + | } |
|
| 69 | + | ||
| 70 | + | /// Index arrays and slices with loaded and computed indices. |
|
| 71 | + | fn indexed(table: &[u8], indices: &[u32]) -> u32 { |
|
| 72 | + | let fixed: [u8; 4] = [10, 20, 30, 40]; |
|
| 73 | + | let mut total: u32 = 0; |
|
| 74 | + | for i in indices { |
|
| 75 | + | let j = i + 1; |
|
| 76 | + | set total += fixed[i] as u32 + fixed[j - 1] as u32 + table[i] as u32 + table[j] as u32; |
|
| 77 | + | } |
|
| 78 | + | return total; |
|
| 79 | + | } |
|
| 80 | + | ||
| 81 | + | /// Compare loaded and computed small values. |
|
| 82 | + | fn smallValues(bytes: &[u8], halves: &[i16]) { |
|
| 83 | + | let b = bytes[0] + 1; |
|
| 84 | + | assert b == bytes[1]; |
|
| 85 | + | assert b > bytes[2]; |
|
| 86 | + | assert bytes[1] + 1 == bytes[2]; |
|
| 87 | + | let h = halves[0] - 1; |
|
| 88 | + | assert h == halves[1]; |
|
| 89 | + | assert h > halves[0]; |
|
| 90 | + | } |
|
| 91 | + | ||
| 92 | + | @default fn main() -> i32 { |
|
| 93 | + | let unsigned: [u32; 3] = [0x7fffffff, 0x80000000, 0xffffffff]; |
|
| 94 | + | unsignedValues(&unsigned[..]); |
|
| 95 | + | let signed: [i32; 3] = [0, -1, -2147483648]; |
|
| 96 | + | signedValues(&signed[..]); |
|
| 97 | + | assert merged(&unsigned[..], true) == 1; |
|
| 98 | + | assert merged(&unsigned[..], false) == 1; |
|
| 99 | + | assert looped(&unsigned[..]) == 1; |
|
| 100 | + | let table: [u8; 5] = [1, 2, 3, 4, 5]; |
|
| 101 | + | let indices: [u32; 2] = [0, 3]; |
|
| 102 | + | assert indexed(&table[..], &indices[..]) == 10 + 10 + 1 + 2 + 40 + 40 + 4 + 5; |
|
| 103 | + | let bytes: [u8; 3] = [254, 255, 0]; |
|
| 104 | + | let halves: [i16; 2] = [-32768, 32767]; |
|
| 105 | + | smallValues(&bytes[..], &halves[..]); |
|
| 106 | + | return 0; |
|
| 107 | + | } |