radiance · commit

Fix subword comparisons on RV64

6cdb32137429733911b794de54decf4d774712b7e49eebac4a8693ea1a404d28

RV64 ordered comparisons consumed subword values without
canonicalizing them to their declared width. Word operations can leave
`u32` values sign-extended to 64 bits, causing signed and unsigned
comparisons to inspect incorrect upper bits.

Normalize both operands with the appropriate sign or zero extension
before selecting ordered comparisons, and only use immediate forms for
canonical immediates.

Alexis Sellier committed 23 days ago 1 parent a6f4d48e

lib/std/arch/rv64/isel.rad +95 -49

            // For SLT: sign-extension needed (signed comparison).
            // For ULT: zero-extension needed (unsigned magnitude comparison).
            // For EQ/NE with W32: sign-extension is cheaper.
            // For EQ/NE with W8/W16: keep zero-extension.
            // Skip extension for zero register.
            // Determine extension mode: sign-extend for W32 or SLT,
            // zero-extend otherwise.
            let mut useSext: bool = undefined;
            let mut signed = false;
            if let case il::CmpOp::Slt = op {
                set useSext = true;
            } else {
                set useSext = typ == il::Type::W32;
                set signed = true;
            }
            if useSext {
                if not aIsZero and not isExtendedImm(a, typ, true) {
                    emitSext(s.e, rs1, rs1, typ);
                }
                if not bIsZero and not isExtendedImm(b, typ, true) {
                    emitSext(s.e, rs2, rs2, typ);
                }
            } else {
                if not aIsZero and not isExtendedImm(a, typ, false) {
                    emitZext(s.e, rs1, rs1, typ);
                }
                if not bIsZero and not isExtendedImm(b, typ, false) {
                    emitZext(s.e, rs2, rs2, typ);
                }
            let useSext = cmpUsesSext(typ, signed);
            if not aIsZero and not isExtendedImm(a, typ, useSext) {
                emitCmpExt(s.e, rs1, rs1, typ, useSext);
            }
            if not bIsZero and not isExtendedImm(b, typ, useSext) {
                emitCmpExt(s.e, rs2, rs2, typ, useSext);
            }
            // Block-argument moves must only execute on the taken path.
            // When `thenArgs` is non-empty, invert the branch so that the
            // then-moves land on the fall-through (taken) side.
            //

            emit::emit(s.e, encode::ebreak());
        },
    }
}

/// Choose the cheapest canonical representation that preserves the comparison.
/// RV64 word operations naturally sign-extend, and sign-extension preserves
/// unsigned ordering when both operands have the same declared width.
fn cmpUsesSext(typ: il::Type, signed: bool) -> bool {
    return signed or typ == il::Type::W32;
}

/// Extend a comparison operand to its selected canonical representation.
fn emitCmpExt(
    e: *mut emit::Emitter,
    rd: gen::Reg,
    rs: gen::Reg,
    typ: il::Type,
    useSext: bool
) {
    if useSext {
        emitSext(e, rd, rs, typ);
    } else {
        emitZext(e, rd, rs, typ);
    }
}

/// Truncate and extend an immediate exactly as its register operand would be.
fn canonicalCmpImm(imm: i64, typ: il::Type, useSext: bool) -> i64 {
    if useSext {
        match typ {
            case il::Type::W8 => return (imm as i8) as i64,
            case il::Type::W16 => return (imm as i16) as i64,
            case il::Type::W32 => return (imm as i32) as i64,
            case il::Type::W64 => return imm,
        }
    } else {
        match typ {
            case il::Type::W8 => return (imm as u8) as i64,
            case il::Type::W16 => return (imm as u16) as i64,
            case il::Type::W32 => return (imm as u32) as i64,
            case il::Type::W64 => return imm,
        }
    }
}

/// Check if a value is an immediate that's already correctly extended.
/// `loadImm` produces the exact 64-bit value; this checks whether that value
/// already matches what sign/zero-extension to the given type would produce.
fn isExtendedImm(val: il::Val, typ: il::Type, signed: bool) -> bool {
    if let case il::Val::Imm(imm) = val {

            selectShift(s, rd, rs1, b, ShiftOp::Sra, typ, super::SCRATCH2),
        case il::BinOp::Ushr =>
            selectShift(s, rd, rs1, b, ShiftOp::Srl, typ, super::SCRATCH2),
        case il::BinOp::Eq, il::BinOp::Ne => {
            let rs2 = resolveVal(s, super::SCRATCH2, b);
            // Canonicalize both operands to the declared width.
            if typ == il::Type::W32 {
                emitSext(s.e, rs1, rs1, typ);
                if not isExtendedImm(b, typ, true) {
                    emitSext(s.e, rs2, rs2, typ);
                }
            } else {
                emitZext(s.e, rs1, rs1, typ);
                if not isExtendedImm(b, typ, false) {
                    emitZext(s.e, rs2, rs2, typ);
                }
            let useSext = cmpUsesSext(typ, false);
            emitCmpExt(s.e, rs1, rs1, typ, useSext);
            if not isExtendedImm(b, typ, useSext) {
                emitCmpExt(s.e, rs2, rs2, typ, useSext);
            }
            emit::emit(s.e, encode::xor(rd, rs1, rs2));
            if let case il::BinOp::Eq = op {
                emit::emit(s.e, encode::sltiu(rd, rd, 1));
            } else {
                emit::emit(s.e, encode::sltu(rd, super::ZERO, rd));
            }
        }
        case il::BinOp::Slt =>
            selectCmp(s, rd, rs1, b, CmpOp::Slt, super::SCRATCH2),
            selectCmp(s, typ, rd, rs1, b, CmpOp::Slt, false, super::SCRATCH2),
        case il::BinOp::Ult =>
            selectCmp(s, rd, rs1, b, CmpOp::Ult, super::SCRATCH2),
        case il::BinOp::Sge, il::BinOp::Uge => {
            let rs2 = resolveVal(s, super::SCRATCH2, b);
            if let case il::BinOp::Sge = op {
                emit::emit(s.e, encode::slt(rd, rs1, rs2));
            } else {
                emit::emit(s.e, encode::sltu(rd, rs1, rs2));
            }
            emit::emit(s.e, encode::xori(rd, rd, 1));
        }
            selectCmp(s, typ, rd, rs1, b, CmpOp::Ult, false, super::SCRATCH2),
        case il::BinOp::Sge =>
            selectCmp(s, typ, rd, rs1, b, CmpOp::Slt, true, super::SCRATCH2),
        case il::BinOp::Uge =>
            selectCmp(s, typ, rd, rs1, b, CmpOp::Ult, true, super::SCRATCH2),
    }
}

/// Select a unary ALU operation.
fn selectAluUnOp(s: *mut Selector, op: il::UnOp, typ: il::Type, rd: gen::Reg, rs: gen::Reg) {

        }
    }
    emitParallelMoves(s, &dsts[..], args);
}

/// Select comparison with immediate optimization.
fn selectCmp(s: *mut Selector, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: CmpOp, scratch: gen::Reg) {
    // Try immediate optimization first.
/// Select a comparison with immediate optimization.
fn selectCmp(
    s: *mut Selector,
    typ: il::Type,
    rd: gen::Reg,
    rs1: gen::Reg,
    b: il::Val,
    op: CmpOp,
    invert: bool,
    scratch: gen::Reg
) {
    let mut signed = false;
    if let case CmpOp::Slt = op {
        set signed = true;
    }
    let useSext = cmpUsesSext(typ, signed);
    emitCmpExt(s.e, rs1, rs1, typ, useSext);

    // Canonicalizing the immediate can expose an immediate instruction even
    // when the IL value used a different representation for the same width.
    let mut rhs = b;
    if let case il::Val::Imm(imm) = b {
        if encode::isSmallImm64(imm) {
            let simm = imm as i32;
        let canonical = canonicalCmpImm(imm, typ, useSext);
        set rhs = il::Val::Imm(canonical);
        if encode::isSmallImm64(canonical) {
            let simm = canonical as i32;
            match op {
                case CmpOp::Slt => emit::emit(s.e, encode::slti(rd, rs1, simm)),
                case CmpOp::Ult => emit::emit(s.e, encode::sltiu(rd, rs1, simm)),
            }
            if invert {
                emit::emit(s.e, encode::xori(rd, rd, 1));
            }
            return;
        }
    }
    // Fallback: load into register.
    let rs2 = resolveVal(s, scratch, b);

    let rs2 = resolveVal(s, scratch, rhs);
    if not isExtendedImm(rhs, typ, useSext) {
        emitCmpExt(s.e, rs2, rs2, typ, useSext);
    }
    match op {
        case CmpOp::Slt => emit::emit(s.e, encode::slt(rd, rs1, rs2)),
        case CmpOp::Ult => emit::emit(s.e, encode::sltu(rd, rs1, rs2)),
    }
    if invert {
        emit::emit(s.e, encode::xori(rd, rd, 1));
    }
}

test/tests/rv64.u32.compare.rad added +84 -0

1	+	//! returns: 0
2	+	//! Ordered comparisons must canonicalize computed subword values, register
3	+	//! operands, and immediates to the representation selected for their width.
4	+
5	+	fn addU8(a: u8, b: u8) -> u8 {
6	+	return a + b;
7	+	}
8	+
9	+	fn addU16(a: u16, b: u16) -> u16 {
10	+	return a + b;
11	+	}
12	+
13	+	fn addU32(a: u32, b: u32) -> u32 {
14	+	return a + b;
15	+	}
16	+
17	+	fn addI8(a: i8, b: i8) -> i8 {
18	+	return a + b;
19	+	}
20	+
21	+	fn addI16(a: i16, b: i16) -> i16 {
22	+	return a + b;
23	+	}
24	+
25	+	fn addI32(a: i32, b: i32) -> i32 {
26	+	return a + b;
27	+	}
28	+
29	+	fn u8Expressions(value: u8, limit: u8) -> bool {
30	+	return value < 0xFF and value >= 0x80 and value < limit and limit >= value;
31	+	}
32	+
33	+	fn u16Expressions(value: u16, limit: u16) -> bool {
34	+	return value < 0xFFFF and value >= 0x8000 and value < limit and limit >= value;
35	+	}
36	+
37	+	fn u32Expressions(value: u32, limit: u32) -> bool {
38	+	return value < 0xFFFFFFFF and value >= 0x80000000
39	+	and value < limit and limit >= value;
40	+	}
41	+
42	+	fn i8Expressions(value: i8, limit: i8) -> bool {
43	+	return value < 0 and value >= -128 and value < limit and limit >= value;
44	+	}
45	+
46	+	fn i16Expressions(value: i16, limit: i16) -> bool {
47	+	return value < 0 and value >= -32768 and value < limit and limit >= value;
48	+	}
49	+
50	+	fn i32Expressions(value: i32, limit: i32) -> bool {
51	+	return value < 0 and value >= -2147483648
52	+	and value < limit and limit >= value;
53	+	}
54	+
55	+	fn u32Branches(value: u32, limit: u32) -> bool {
56	+	if value >= 0xFFFFFFFF {
57	+	return false;
58	+	}
59	+	if value < 0x80000000 {
60	+	return false;
61	+	}
62	+	if value < limit {
63	+	return true;
64	+	}
65	+	return false;
66	+	}
67	+
68	+	@default fn main() -> i32 {
69	+	let highU8 = addU8(0x7F, 1);
70	+	let highU16 = addU16(0x7FFF, 1);
71	+	let highU32 = addU32(0x7FFFFFFF, 1);
72	+	let minI8 = addI8(127, 1);
73	+	let minI16 = addI16(32767, 1);
74	+	let minI32 = addI32(2147483647, 1);
75	+
76	+	assert u8Expressions(highU8, 0xFE);
77	+	assert u16Expressions(highU16, 0xFFFE);
78	+	assert u32Expressions(highU32, 0xFFFFFFFE);
79	+	assert i8Expressions(minI8, -1);
80	+	assert i16Expressions(minI16, -1);
81	+	assert i32Expressions(minI32, -1);
82	+	assert u32Branches(highU32, 0xFFFFFFFE);
83	+	return 0;
84	+	}

615	615		// For SLT: sign-extension needed (signed comparison).
616	616		// For ULT: zero-extension needed (unsigned magnitude comparison).
617	617		// For EQ/NE with W32: sign-extension is cheaper.
618	618		// For EQ/NE with W8/W16: keep zero-extension.
619	619		// Skip extension for zero register.
620		-	// Determine extension mode: sign-extend for W32 or SLT,
621		-	// zero-extend otherwise.
622		-	let mut useSext: bool = undefined;
	620	+	let mut signed = false;
623	621		if let case il::CmpOp::Slt = op {
624		-	set useSext = true;
625		-	} else {
626		-	set useSext = typ == il::Type::W32;
	622	+	set signed = true;
627	623		}
628		-	if useSext {
629		-	if not aIsZero and not isExtendedImm(a, typ, true) {
630		-	emitSext(s.e, rs1, rs1, typ);
631		-	}
632		-	if not bIsZero and not isExtendedImm(b, typ, true) {
633		-	emitSext(s.e, rs2, rs2, typ);
634		-	}
635		-	} else {
636		-	if not aIsZero and not isExtendedImm(a, typ, false) {
637		-	emitZext(s.e, rs1, rs1, typ);
638		-	}
639		-	if not bIsZero and not isExtendedImm(b, typ, false) {
640		-	emitZext(s.e, rs2, rs2, typ);
641		-	}
	624	+	let useSext = cmpUsesSext(typ, signed);
	625	+	if not aIsZero and not isExtendedImm(a, typ, useSext) {
	626	+	emitCmpExt(s.e, rs1, rs1, typ, useSext);
	627	+	}
	628	+	if not bIsZero and not isExtendedImm(b, typ, useSext) {
	629	+	emitCmpExt(s.e, rs2, rs2, typ, useSext);
642	630		}
643	631		// Block-argument moves must only execute on the taken path.
644	632		// When `thenArgs` is non-empty, invert the branch so that the
645	633		// then-moves land on the fall-through (taken) side.
646	634		//

747	735		emit::emit(s.e, encode::ebreak());
748	736		},
749	737		}
750	738		}
751	739
	740	+	/// Choose the cheapest canonical representation that preserves the comparison.
	741	+	/// RV64 word operations naturally sign-extend, and sign-extension preserves
	742	+	/// unsigned ordering when both operands have the same declared width.
	743	+	fn cmpUsesSext(typ: il::Type, signed: bool) -> bool {
	744	+	return signed or typ == il::Type::W32;
	745	+	}
	746	+
	747	+	/// Extend a comparison operand to its selected canonical representation.
	748	+	fn emitCmpExt(
	749	+	e: *mut emit::Emitter,
	750	+	rd: gen::Reg,
	751	+	rs: gen::Reg,
	752	+	typ: il::Type,
	753	+	useSext: bool
	754	+	) {
	755	+	if useSext {
	756	+	emitSext(e, rd, rs, typ);
	757	+	} else {
	758	+	emitZext(e, rd, rs, typ);
	759	+	}
	760	+	}
	761	+
	762	+	/// Truncate and extend an immediate exactly as its register operand would be.
	763	+	fn canonicalCmpImm(imm: i64, typ: il::Type, useSext: bool) -> i64 {
	764	+	if useSext {
	765	+	match typ {
	766	+	case il::Type::W8 => return (imm as i8) as i64,
	767	+	case il::Type::W16 => return (imm as i16) as i64,
	768	+	case il::Type::W32 => return (imm as i32) as i64,
	769	+	case il::Type::W64 => return imm,
	770	+	}
	771	+	} else {
	772	+	match typ {
	773	+	case il::Type::W8 => return (imm as u8) as i64,
	774	+	case il::Type::W16 => return (imm as u16) as i64,
	775	+	case il::Type::W32 => return (imm as u32) as i64,
	776	+	case il::Type::W64 => return imm,
	777	+	}
	778	+	}
	779	+	}
	780	+
752	781		/// Check if a value is an immediate that's already correctly extended.
753	782		/// `loadImm` produces the exact 64-bit value; this checks whether that value
754	783		/// already matches what sign/zero-extension to the given type would produce.
755	784		fn isExtendedImm(val: il::Val, typ: il::Type, signed: bool) -> bool {
756	785		if let case il::Val::Imm(imm) = val {

889	918		selectShift(s, rd, rs1, b, ShiftOp::Sra, typ, super::SCRATCH2),
890	919		case il::BinOp::Ushr =>
891	920		selectShift(s, rd, rs1, b, ShiftOp::Srl, typ, super::SCRATCH2),
892	921		case il::BinOp::Eq, il::BinOp::Ne => {
893	922		let rs2 = resolveVal(s, super::SCRATCH2, b);
894		-	// Canonicalize both operands to the declared width.
895		-	if typ == il::Type::W32 {
896		-	emitSext(s.e, rs1, rs1, typ);
897		-	if not isExtendedImm(b, typ, true) {
898		-	emitSext(s.e, rs2, rs2, typ);
899		-	}
900		-	} else {
901		-	emitZext(s.e, rs1, rs1, typ);
902		-	if not isExtendedImm(b, typ, false) {
903		-	emitZext(s.e, rs2, rs2, typ);
904		-	}
	923	+	let useSext = cmpUsesSext(typ, false);
	924	+	emitCmpExt(s.e, rs1, rs1, typ, useSext);
	925	+	if not isExtendedImm(b, typ, useSext) {
	926	+	emitCmpExt(s.e, rs2, rs2, typ, useSext);
905	927		}
906	928		emit::emit(s.e, encode::xor(rd, rs1, rs2));
907	929		if let case il::BinOp::Eq = op {
908	930		emit::emit(s.e, encode::sltiu(rd, rd, 1));
909	931		} else {
910	932		emit::emit(s.e, encode::sltu(rd, super::ZERO, rd));
911	933		}
912	934		}
913	935		case il::BinOp::Slt =>
914		-	selectCmp(s, rd, rs1, b, CmpOp::Slt, super::SCRATCH2),
	936	+	selectCmp(s, typ, rd, rs1, b, CmpOp::Slt, false, super::SCRATCH2),
915	937		case il::BinOp::Ult =>
916		-	selectCmp(s, rd, rs1, b, CmpOp::Ult, super::SCRATCH2),
917		-	case il::BinOp::Sge, il::BinOp::Uge => {
918		-	let rs2 = resolveVal(s, super::SCRATCH2, b);
919		-	if let case il::BinOp::Sge = op {
920		-	emit::emit(s.e, encode::slt(rd, rs1, rs2));
921		-	} else {
922		-	emit::emit(s.e, encode::sltu(rd, rs1, rs2));
923		-	}
924		-	emit::emit(s.e, encode::xori(rd, rd, 1));
925		-	}
	938	+	selectCmp(s, typ, rd, rs1, b, CmpOp::Ult, false, super::SCRATCH2),
	939	+	case il::BinOp::Sge =>
	940	+	selectCmp(s, typ, rd, rs1, b, CmpOp::Slt, true, super::SCRATCH2),
	941	+	case il::BinOp::Uge =>
	942	+	selectCmp(s, typ, rd, rs1, b, CmpOp::Ult, true, super::SCRATCH2),
926	943		}
927	944		}
928	945
929	946		/// Select a unary ALU operation.
930	947		fn selectAluUnOp(s: *mut Selector, op: il::UnOp, typ: il::Type, rd: gen::Reg, rs: gen::Reg) {

1161	1178		}
1162	1179		}
1163	1180		emitParallelMoves(s, &dsts[..], args);
1164	1181		}
1165	1182
1166		-	/// Select comparison with immediate optimization.
1167		-	fn selectCmp(s: *mut Selector, rd: gen::Reg, rs1: gen::Reg, b: il::Val, op: CmpOp, scratch: gen::Reg) {
1168		-	// Try immediate optimization first.
	1183	+	/// Select a comparison with immediate optimization.
	1184	+	fn selectCmp(
	1185	+	s: *mut Selector,
	1186	+	typ: il::Type,
	1187	+	rd: gen::Reg,
	1188	+	rs1: gen::Reg,
	1189	+	b: il::Val,
	1190	+	op: CmpOp,
	1191	+	invert: bool,
	1192	+	scratch: gen::Reg
	1193	+	) {
	1194	+	let mut signed = false;
	1195	+	if let case CmpOp::Slt = op {
	1196	+	set signed = true;
	1197	+	}
	1198	+	let useSext = cmpUsesSext(typ, signed);
	1199	+	emitCmpExt(s.e, rs1, rs1, typ, useSext);
	1200	+
	1201	+	// Canonicalizing the immediate can expose an immediate instruction even
	1202	+	// when the IL value used a different representation for the same width.
	1203	+	let mut rhs = b;
1169	1204		if let case il::Val::Imm(imm) = b {
1170		-	if encode::isSmallImm64(imm) {
1171		-	let simm = imm as i32;
	1205	+	let canonical = canonicalCmpImm(imm, typ, useSext);
	1206	+	set rhs = il::Val::Imm(canonical);
	1207	+	if encode::isSmallImm64(canonical) {
	1208	+	let simm = canonical as i32;
1172	1209		match op {
1173	1210		case CmpOp::Slt => emit::emit(s.e, encode::slti(rd, rs1, simm)),
1174	1211		case CmpOp::Ult => emit::emit(s.e, encode::sltiu(rd, rs1, simm)),
1175	1212		}
	1213	+	if invert {
	1214	+	emit::emit(s.e, encode::xori(rd, rd, 1));
	1215	+	}
1176	1216		return;
1177	1217		}
1178	1218		}
1179		-	// Fallback: load into register.
1180		-	let rs2 = resolveVal(s, scratch, b);
	1219	+
	1220	+	let rs2 = resolveVal(s, scratch, rhs);
	1221	+	if not isExtendedImm(rhs, typ, useSext) {
	1222	+	emitCmpExt(s.e, rs2, rs2, typ, useSext);
	1223	+	}
1181	1224		match op {
1182	1225		case CmpOp::Slt => emit::emit(s.e, encode::slt(rd, rs1, rs2)),
1183	1226		case CmpOp::Ult => emit::emit(s.e, encode::sltu(rd, rs1, rs2)),
1184	1227		}
	1228	+	if invert {
	1229	+	emit::emit(s.e, encode::xori(rd, rd, 1));
	1230	+	}
1185	1231		}