compiler: Select instructions through checked operand borrows
b7b60331d6f6ae46bb58cf07d2fe8b9685de109bdede07684f59bb63f8ae301c
1 parent
997083ce
lib/std/arch/rv64/emit.rad
+1 -1
| 508 | 508 | /// |
|
| 509 | 509 | /// Called after each function. |
|
| 510 | 510 | /// |
|
| 511 | 511 | /// Uses two-instruction sequences: short branches use `branch` and `nop`, |
|
| 512 | 512 | /// long branches use inverted branch and `jal` or `auipc` and `jalr`. |
|
| 513 | - | export unsafe fn patchLocalBranches(e: &mut Emitter) { |
|
| 513 | + | export fn patchLocalBranches(e: &mut Emitter) { |
|
| 514 | 514 | if e.error <> nil { |
|
| 515 | 515 | return; |
|
| 516 | 516 | } |
|
| 517 | 517 | for i in 0..e.pendingBranchesLen { |
|
| 518 | 518 | let p = e.pendingBranches[i]; |
lib/std/arch/rv64/isel.rad
+24 -25
| 105 | 105 | ///////////////////////// |
|
| 106 | 106 | // Register Allocation // |
|
| 107 | 107 | ///////////////////////// |
|
| 108 | 108 | ||
| 109 | 109 | /// Get the physical register for an already-allocated SSA register. |
|
| 110 | - | unsafe fn getReg 'scratch 'selection (s: &Selector 'scratch 'selection, ssa: il::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 110 | + | fn getReg 'scratch 'selection (s: &Selector 'scratch 'selection, ssa: il::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 111 | 111 | let phys = s.ralloc.assignments[ssa.n] else { |
|
| 112 | 112 | panic "getReg: spilled register has no physical assignment"; |
|
| 113 | 113 | }; |
|
| 114 | 114 | return phys; |
|
| 115 | 115 | } |
| 134 | 134 | ||
| 135 | 135 | /// Get the destination register for an SSA register. |
|
| 136 | 136 | /// If the register is spilled, records a pending spill and returns the scratch |
|
| 137 | 137 | /// register. The pending spill is auto-committed by [`selectBlock`] after each |
|
| 138 | 138 | /// instruction. If not spilled, returns the physical register. |
|
| 139 | - | unsafe fn getDstReg 'scratch 'selection (s: &mut Selector 'scratch 'selection, ssa: il::Reg, scratch: gen::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 139 | + | fn getDstReg 'scratch 'selection (s: &mut Selector 'scratch 'selection, ssa: il::Reg, scratch: gen::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 140 | 140 | if let _ = regalloc::spill::spillSlot(&s.ralloc.spill, ssa) { |
|
| 141 | 141 | set s.pendingSpill = PendingSpill { ssa, rd: scratch }; |
|
| 142 | 142 | return scratch; |
|
| 143 | 143 | } |
|
| 144 | 144 | return getReg(s, ssa); |
|
| 145 | 145 | } |
|
| 146 | 146 | ||
| 147 | 147 | /// Get the source register for an SSA register. |
|
| 148 | 148 | /// If the register is spilled, loads the value from the spill slot into the |
|
| 149 | 149 | /// scratch register and returns it. Otherwise returns the physical register. |
|
| 150 | - | unsafe fn getSrcReg 'scratch 'selection (s: &mut Selector 'scratch 'selection, ssa: il::Reg, scratch: gen::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 150 | + | fn getSrcReg 'scratch 'selection (s: &mut Selector 'scratch 'selection, ssa: il::Reg, scratch: gen::Reg) -> gen::Reg where 'scratch: 'selection { |
|
| 151 | 151 | if let slot = regalloc::spill::spillSlot(&s.ralloc.spill, ssa) { |
|
| 152 | 152 | emit::emitLd(s.e, scratch, spillBase(s), spillOffset(s, slot)); |
|
| 153 | 153 | return scratch; |
|
| 154 | 154 | } |
|
| 155 | 155 | return getReg(s, ssa); |
|
| 156 | 156 | } |
|
| 157 | 157 | ||
| 158 | 158 | /// Resolve an IL value to the physical register holding it. |
|
| 159 | 159 | /// For non-spilled register values, returns the physical register directly. |
|
| 160 | 160 | /// For immediates, symbols, and spilled registers, materializes into `scratch`. |
|
| 161 | - | unsafe fn resolveVal 'scratch 'selection (s: &mut Selector 'scratch 'selection, scratch: gen::Reg, val: il::Val) -> gen::Reg where 'scratch: 'selection { |
|
| 161 | + | fn resolveVal 'scratch 'selection (s: &mut Selector 'scratch 'selection, scratch: gen::Reg, val: il::Val) -> gen::Reg where 'scratch: 'selection { |
|
| 162 | 162 | match val { |
|
| 163 | 163 | case il::Val::Reg(r) => { |
|
| 164 | 164 | return getSrcReg(s, r, scratch); |
|
| 165 | 165 | }, |
|
| 166 | 166 | case il::Val::Imm(imm) => { |
| 184 | 184 | } |
|
| 185 | 185 | } |
|
| 186 | 186 | ||
| 187 | 187 | /// Load an IL value into a specific physical register. |
|
| 188 | 188 | /// Like [`resolveVal`], but ensures the value ends up in `rd`. |
|
| 189 | - | unsafe fn loadVal 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, val: il::Val) -> gen::Reg where 'scratch: 'selection { |
|
| 189 | + | fn loadVal 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, val: il::Val) -> gen::Reg where 'scratch: 'selection { |
|
| 190 | 190 | let rs = resolveVal(s, rd, val); |
|
| 191 | 191 | emitMv(s, rd, rs); |
|
| 192 | 192 | return rd; |
|
| 193 | 193 | } |
|
| 194 | 194 | ||
| 195 | 195 | /// Emit a move instruction if source and destination differ. |
|
| 196 | - | unsafe fn emitMv 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs: gen::Reg) where 'scratch: 'selection { |
|
| 196 | + | fn emitMv 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs: gen::Reg) where 'scratch: 'selection { |
|
| 197 | 197 | if *rd <> *rs { |
|
| 198 | 198 | emit::emit(s.e, encode::mv(rd, rs)); |
|
| 199 | 199 | } |
|
| 200 | 200 | } |
|
| 201 | 201 |
| 233 | 233 | } |
|
| 234 | 234 | } |
|
| 235 | 235 | ||
| 236 | 236 | /// Resolve a divisor in its declared width, trap if it becomes zero, and |
|
| 237 | 237 | /// return the canonicalized register. |
|
| 238 | - | unsafe fn resolveAndTrapIfZero 'scratch 'selection ( |
|
| 238 | + | fn resolveAndTrapIfZero 'scratch 'selection ( |
|
| 239 | 239 | s: &mut Selector 'scratch 'selection, |
|
| 240 | 240 | b: il::Val, |
|
| 241 | 241 | typ: il::Type, |
|
| 242 | 242 | signed: bool |
|
| 243 | 243 | ) -> gen::Reg where 'scratch: 'selection { |
| 538 | 538 | emit::emitReturn(s.e, frame); |
|
| 539 | 539 | } |
|
| 540 | 540 | }, |
|
| 541 | 541 | case il::Instr::Jmp { target, args } => { |
|
| 542 | 542 | // Move arguments to target block's parameter registers. |
|
| 543 | - | emitBlockArgs(s, func, target, args); |
|
| 543 | + | emitBlockArgs(s, func.blocks[target].params, args); |
|
| 544 | 544 | // Skip branch if target is the next block (fallthrough). |
|
| 545 | 545 | if target <> blockIdx + 1 { |
|
| 546 | 546 | emit::recordBranch(s.e, target, emit::BranchKind::Jump); |
|
| 547 | 547 | } |
|
| 548 | 548 | }, |
| 585 | 585 | // execution fall through. |
|
| 586 | 586 | if thenArgs.len > 0 and elseArgs.len > 0 { |
|
| 587 | 587 | panic "selectInstr: both `then` and `else` have block arguments"; |
|
| 588 | 588 | } else if thenArgs.len > 0 { |
|
| 589 | 589 | emit::recordBranch(s.e, elseTarget, emit::BranchKind::InvertedCond { op, rs1, rs2 }); |
|
| 590 | - | emitBlockArgs(s, func, thenTarget, thenArgs); |
|
| 590 | + | emitBlockArgs(s, func.blocks[thenTarget].params, thenArgs); |
|
| 591 | 591 | // Skip trailing jump if then is the next block (fallthrough). |
|
| 592 | 592 | if thenTarget <> blockIdx + 1 { |
|
| 593 | 593 | emit::recordBranch(s.e, thenTarget, emit::BranchKind::Jump); |
|
| 594 | 594 | } |
|
| 595 | 595 | } else if thenTarget == blockIdx + 1 and elseArgs.len == 0 { |
|
| 596 | 596 | // Then is the next block and no else args: invert the |
|
| 597 | 597 | // condition to branch to else and fall through to then. |
|
| 598 | 598 | emit::recordBranch(s.e, elseTarget, emit::BranchKind::InvertedCond { op, rs1, rs2 }); |
|
| 599 | 599 | } else { |
|
| 600 | 600 | emit::recordBranch(s.e, thenTarget, emit::BranchKind::Cond { op, rs1, rs2 }); |
|
| 601 | - | emitBlockArgs(s, func, elseTarget, elseArgs); |
|
| 601 | + | emitBlockArgs(s, func.blocks[elseTarget].params, elseArgs); |
|
| 602 | 602 | // Skip trailing jump if else is the next block (fallthrough). |
|
| 603 | 603 | if elseTarget <> blockIdx + 1 { |
|
| 604 | 604 | emit::recordBranch(s.e, elseTarget, emit::BranchKind::Jump); |
|
| 605 | 605 | } |
|
| 606 | 606 | } |
| 617 | 617 | set s.nextSynthBlock = skip + 1; |
|
| 618 | 618 | ||
| 619 | 619 | emit::recordBranch(s.e, skip, emit::BranchKind::InvertedCond { |
|
| 620 | 620 | op: il::CmpOp::Eq, rs1, rs2: super::SCRATCH2, |
|
| 621 | 621 | }); |
|
| 622 | - | emitBlockArgs(s, func, c.target, c.args); |
|
| 622 | + | emitBlockArgs(s, func.blocks[c.target].params, c.args); |
|
| 623 | 623 | emit::recordBranch(s.e, c.target, emit::BranchKind::Jump); |
|
| 624 | 624 | emit::recordBlock(s.e, skip); |
|
| 625 | 625 | } else { |
|
| 626 | 626 | emit::recordBranch(s.e, c.target, emit::BranchKind::Cond { |
|
| 627 | 627 | op: il::CmpOp::Eq, rs1, rs2: super::SCRATCH2, |
|
| 628 | 628 | }); |
|
| 629 | 629 | } |
|
| 630 | 630 | } |
|
| 631 | 631 | // Fall through to default. |
|
| 632 | - | emitBlockArgs(s, func, defaultTarget, defaultArgs); |
|
| 632 | + | emitBlockArgs(s, func.blocks[defaultTarget].params, defaultArgs); |
|
| 633 | 633 | emit::recordBranch(s.e, defaultTarget, emit::BranchKind::Jump); |
|
| 634 | 634 | }, |
|
| 635 | 635 | case il::Instr::Unreachable => { |
|
| 636 | 636 | emit::emit(s.e, encode::ebreak()); |
|
| 637 | 637 | }, |
| 788 | 788 | return false; |
|
| 789 | 789 | } |
|
| 790 | 790 | ||
| 791 | 791 | /// Select a binary ALU operation, dispatching to the appropriate |
|
| 792 | 792 | /// instruction pattern based on the operation kind and type. |
|
| 793 | - | unsafe fn selectAluBinOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, op: il::BinOp, typ: il::Type, rd: gen::Reg, rs1: gen::Reg, b: il::Val) where 'scratch: 'selection { |
|
| 793 | + | fn selectAluBinOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, op: il::BinOp, typ: il::Type, rd: gen::Reg, rs1: gen::Reg, b: il::Val) where 'scratch: 'selection { |
|
| 794 | 794 | match op { |
|
| 795 | 795 | case il::BinOp::Add => { |
|
| 796 | 796 | if typ == il::Type::W32 { |
|
| 797 | 797 | // Inline W32 ADD with immediate optimization. |
|
| 798 | 798 | if let case il::Val::Imm(imm) = b { |
| 916 | 916 | selectCmp(s, typ, rd, rs1, b, CmpOp::Ult, true, super::SCRATCH2), |
|
| 917 | 917 | } |
|
| 918 | 918 | } |
|
| 919 | 919 | ||
| 920 | 920 | /// Select a unary ALU operation. |
|
| 921 | - | unsafe fn selectAluUnOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, op: il::UnOp, typ: il::Type, rd: gen::Reg, rs: gen::Reg) where 'scratch: 'selection { |
|
| 921 | + | fn selectAluUnOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, op: il::UnOp, typ: il::Type, rd: gen::Reg, rs: gen::Reg) where 'scratch: 'selection { |
|
| 922 | 922 | match op { |
|
| 923 | 923 | case il::UnOp::Neg => { |
|
| 924 | 924 | if typ == il::Type::W32 { |
|
| 925 | 925 | emit::emit(s.e, encode::subw(rd, super::ZERO, rs)); |
|
| 926 | 926 | } else { |
| 931 | 931 | emit::emit(s.e, encode::not_(rd, rs)), |
|
| 932 | 932 | } |
|
| 933 | 933 | } |
|
| 934 | 934 | ||
| 935 | 935 | /// Select binary operation with immediate optimization. |
|
| 936 | - | unsafe fn selectBinOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: BinOp, scratch: gen::Reg) where 'scratch: 'selection { |
|
| 936 | + | fn selectBinOp 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: BinOp, scratch: gen::Reg) where 'scratch: 'selection { |
|
| 937 | 937 | // Try immediate optimization first. |
|
| 938 | 938 | if let case il::Val::Imm(imm) = b { |
|
| 939 | 939 | if encode::isSmallImm64(imm) { |
|
| 940 | 940 | let simm = imm as i32; |
|
| 941 | 941 | match op { |
| 958 | 958 | } |
|
| 959 | 959 | ||
| 960 | 960 | /// Select shift operation with immediate optimization. |
|
| 961 | 961 | /// For 32-bit operations, uses the `*w` variants that operate on the lower 32 bits |
|
| 962 | 962 | /// and sign-extend the result. |
|
| 963 | - | unsafe fn selectShift 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: ShiftOp, typ: il::Type, scratch: gen::Reg) where 'scratch: 'selection { |
|
| 963 | + | fn selectShift 'scratch 'selection (s: &mut Selector 'scratch 'selection, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: ShiftOp, typ: il::Type, scratch: gen::Reg) where 'scratch: 'selection { |
|
| 964 | 964 | let isW32: bool = typ == il::Type::W32; |
|
| 965 | 965 | ||
| 966 | 966 | // Try immediate optimization first. |
|
| 967 | 967 | if let case il::Val::Imm(shamt) = b { |
|
| 968 | 968 | // Keep immediate forms only for encodable shift amounts. |
| 1011 | 1011 | /// 1. Identifies "ready" moves. |
|
| 1012 | 1012 | /// 2. Executes ready moves. |
|
| 1013 | 1013 | /// 3. Breaks cycles using scratch register. |
|
| 1014 | 1014 | /// |
|
| 1015 | 1015 | /// Entries with `ZERO` destination are skipped, as they are handled by caller. |
|
| 1016 | - | unsafe fn emitParallelMoves 'scratch 'selection (s: &mut Selector 'scratch 'selection, dsts: &[gen::Reg], args: &[il::Val]) where 'scratch: 'selection { |
|
| 1016 | + | fn emitParallelMoves 'scratch 'selection (s: &mut Selector 'scratch 'selection, dsts: &[gen::Reg], args: &[il::Val]) where 'scratch: 'selection { |
|
| 1017 | 1017 | let n: u32 = args.len; |
|
| 1018 | 1018 | if n == 0 { |
|
| 1019 | 1019 | return; |
|
| 1020 | 1020 | } |
|
| 1021 | 1021 | if n > MAX_BLOCK_ARGS { |
| 1125 | 1125 | /// Emit moves from block arguments to target block's parameter registers. |
|
| 1126 | 1126 | /// |
|
| 1127 | 1127 | /// Handles spilled destinations directly, then delegates to [`emitParallelMoves`] |
|
| 1128 | 1128 | /// for the remaining register-to-register parallel move resolution. Edges that |
|
| 1129 | 1129 | /// would overwrite an unconsumed spill source are unsupported. |
|
| 1130 | - | unsafe fn emitBlockArgs 'scratch 'selection (s: &mut Selector 'scratch 'selection, func: &il::Fn, target: u32, args: &[il::Val]) where 'scratch: 'selection { |
|
| 1130 | + | fn emitBlockArgs 'scratch 'selection (s: &mut Selector 'scratch 'selection, params: &[il::Param], args: &[il::Val]) where 'scratch: 'selection { |
|
| 1131 | 1131 | if args.len == 0 { |
|
| 1132 | 1132 | return; |
|
| 1133 | 1133 | } |
|
| 1134 | - | let block = &func.blocks[target]; |
|
| 1135 | - | assert args.len == block.params.len, "emitBlockArgs: argument/parameter count mismatch"; |
|
| 1134 | + | assert args.len == params.len, "emitBlockArgs: argument/parameter count mismatch"; |
|
| 1136 | 1135 | if args.len > MAX_BLOCK_ARGS { |
|
| 1137 | 1136 | set s.e.error = super::Error::Capacity; |
|
| 1138 | 1137 | return; |
|
| 1139 | 1138 | } |
|
| 1140 | 1139 | ||
| 1141 | 1140 | // The parallel-move resolver only handles register destinations. Keep eager |
|
| 1142 | 1141 | // stores for independent spill slots, but reject dependencies that would |
|
| 1143 | 1142 | // require stack staging rather than silently miscompiling them. |
|
| 1144 | 1143 | for arg, i in args { |
|
| 1145 | - | if let dstSlot = regalloc::spill::spillSlot(&s.ralloc.spill, block.params[i].value) { |
|
| 1144 | + | if let dstSlot = regalloc::spill::spillSlot(&s.ralloc.spill, params[i].value) { |
|
| 1146 | 1145 | let mut changesSlot = true; |
|
| 1147 | 1146 | if let case il::Val::Reg(src) = arg { |
|
| 1148 | 1147 | if let srcSlot = regalloc::spill::spillSlot(&s.ralloc.spill, src) { |
|
| 1149 | 1148 | if srcSlot == dstSlot { |
|
| 1150 | 1149 | set changesSlot = false; |
| 1155 | 1154 | for source, j in args { |
|
| 1156 | 1155 | if let case il::Val::Reg(src) = source { |
|
| 1157 | 1156 | if let sourceSlot = regalloc::spill::spillSlot(&s.ralloc.spill, src) { |
|
| 1158 | 1157 | if sourceSlot == dstSlot { |
|
| 1159 | 1158 | if let sourceDstSlot = regalloc::spill::spillSlot( |
|
| 1160 | - | &s.ralloc.spill, block.params[j].value |
|
| 1159 | + | &s.ralloc.spill, params[j].value |
|
| 1161 | 1160 | ) { |
|
| 1162 | 1161 | assert sourceDstSlot == dstSlot or j < i, |
|
| 1163 | 1162 | "emitBlockArgs: overlapping spilled block arguments are unsupported"; |
|
| 1164 | 1163 | } else { |
|
| 1165 | 1164 | panic "emitBlockArgs: overlapping spilled block arguments are unsupported"; |
| 1175 | 1174 | // Destination registers for each arg. |
|
| 1176 | 1175 | // Zero means the destination is spilled or skipped. |
|
| 1177 | 1176 | let mut dsts: [gen::Reg; MAX_BLOCK_ARGS] = [super::ZERO; MAX_BLOCK_ARGS]; |
|
| 1178 | 1177 | ||
| 1179 | 1178 | for arg, i in args { |
|
| 1180 | - | let param = block.params[i].value; |
|
| 1179 | + | let param = params[i].value; |
|
| 1181 | 1180 | ||
| 1182 | 1181 | // Spilled destinations: store directly to spill slot. |
|
| 1183 | 1182 | // These don't participate in the parallel move algorithm. |
|
| 1184 | 1183 | if let slot = regalloc::spill::spillSlot(&s.ralloc.spill, param) { |
|
| 1185 | 1184 | if let case il::Val::Undef = arg { |
| 1194 | 1193 | } |
|
| 1195 | 1194 | emitParallelMoves(s, &dsts[..], args); |
|
| 1196 | 1195 | } |
|
| 1197 | 1196 | ||
| 1198 | 1197 | /// Select a comparison with immediate optimization. |
|
| 1199 | - | unsafe fn selectCmp 'scratch 'selection ( |
|
| 1198 | + | fn selectCmp 'scratch 'selection ( |
|
| 1200 | 1199 | s: &mut Selector 'scratch 'selection, |
|
| 1201 | 1200 | typ: il::Type, |
|
| 1202 | 1201 | rd: gen::Reg, |
|
| 1203 | 1202 | rs1: gen::Reg, |
|
| 1204 | 1203 | b: il::Val, |
| 1244 | 1243 | emit::emit(s.e, encode::xori(rd, rd, 1)); |
|
| 1245 | 1244 | } |
|
| 1246 | 1245 | } |
|
| 1247 | 1246 | ||
| 1248 | 1247 | /// Resolve one live Device access before an ordered user-mode register instruction. |
|
| 1249 | - | unsafe fn deviceAddress 'scratch 'selection ( |
|
| 1248 | + | fn deviceAddress 'scratch 'selection ( |
|
| 1250 | 1249 | s: &mut Selector 'scratch 'selection, |
|
| 1251 | 1250 | typ: il::Type, |
|
| 1252 | 1251 | handle: il::Val, |
|
| 1253 | 1252 | offset: il::Val, |
|
| 1254 | 1253 | value: il::Val, |