1 // SPDX-License-Identifier: LGPL-2.1-or-later
3 * Copyright (C) 2022 Paul Cercueil <paul@crapouillou.net>
7 #include "disassembler.h"
8 #include "lightrec-private.h"
13 static u32 get_min_value(const struct constprop_data *d)
15 /* Min value: all sign bits to 1, all unknown bits but MSB to 0 */
16 return (d->value & d->known) | d->sign | (~d->known & BIT(31));
19 static u32 get_max_value(const struct constprop_data *d)
21 /* Max value: all sign bits to 0, all unknown bits to 1 */
22 return ((d->value & d->known) | ~d->known) & ~d->sign;
25 static u32 lightrec_same_sign(const struct constprop_data *d1,
26 const struct constprop_data *d2)
28 u32 min1, min2, max1, max2, a, b, c, d;
30 min1 = get_min_value(d1);
31 max1 = get_max_value(d1);
32 min2 = get_min_value(d2);
33 max2 = get_max_value(d2);
40 return ((a & b & c & d) | (~a & ~b & ~c & ~d)) & BIT(31);
43 static u32 lightrec_get_sign_mask(const struct constprop_data *d)
50 imm = (d->value & BIT(31)) ? d->value : ~d->value;
51 imm = ~(imm & d->known);
53 imm = 32 - clz32(imm);
55 return imm < 32 ? GENMASK(31, imm) : 0;
58 static void lightrec_propagate_addi(u32 rs, u32 rd,
59 const struct constprop_data *d,
60 struct constprop_data *v)
62 u32 end, bit, sum, min, mask, imm, value;
63 struct constprop_data result = {
70 /* clear unknown bits to ease processing */
71 v[rs].value &= v[rs].known;
72 value = d->value & d->known;
74 mask = ~(lightrec_get_sign_mask(d) & lightrec_get_sign_mask(&v[rs]));
75 end = mask ? 32 - clz32(mask) : 0;
77 for (bit = 0; bit < 32; bit++) {
78 if (v[rs].known & d->known & BIT(bit)) {
79 /* the bits are known - compute the resulting bit and
81 sum = ((u32)carry << bit) + (v[rs].value & BIT(bit))
85 result.value |= BIT(bit);
87 result.value &= ~BIT(bit);
89 result.known |= BIT(bit);
90 result.sign &= ~BIT(bit);
91 carry = sum & BIT(bit + 1);
96 /* We're past the last significant bits of the values
97 * (extra sign bits excepted).
98 * The destination register will be sign-extended
99 * starting from here (if no carry) or from the next
101 * If the source registers are not sign-extended and we
102 * have no carry, the algorithm is done here. */
104 if ((v[rs].sign | d->sign) & BIT(bit)) {
105 mask = GENMASK(31, bit);
107 if (lightrec_same_sign(&v[rs], d)) {
108 /* Theorical minimum and maximum values
109 * have the same sign; therefore the
110 * sign bits are known. */
111 min = get_min_value(&v[rs])
113 result.value = (min & mask)
114 | (result.value & ~mask);
115 result.known |= mask << carry;
118 /* min/max have different signs. */
119 result.sign = mask << 1;
120 result.known &= ~mask;
124 /* Past end bit, no carry; we're done here. */
129 result.known &= ~BIT(bit);
130 result.sign &= ~BIT(bit);
132 /* Found an unknown bit in one of the registers.
133 * If the carry and the bit in the other register are both zero,
134 * we can continue the algorithm. */
135 if (!carry && (((d->known & ~value)
136 | (v[rs].known & ~v[rs].value)) & BIT(bit)))
139 /* We have an unknown bit in one of the source registers, and we
140 * may generate a carry: there's nothing to do. Everything from
141 * this bit till the next known 0 bit or sign bit will be marked
142 * as unknown. The algorithm can then restart at the following
145 imm = (v[rs].known & d->known & ~v[rs].value & ~value)
146 | v[rs].sign | d->sign;
148 imm &= GENMASK(31, bit);
149 imm = imm ? ctz32(imm) : 31;
150 mask = GENMASK(imm, bit);
151 result.known &= ~mask;
152 result.sign &= ~mask;
161 static void lightrec_propagate_sub(u32 rs, u32 rt, u32 rd,
162 struct constprop_data *v)
164 struct constprop_data d = {
165 .value = ~v[rt].value,
166 .known = v[rt].known,
171 /* Negate the known Rt value, then propagate as a regular ADD. */
173 for (bit = 0; bit < 32; bit++) {
174 if (!(d.known & BIT(bit))) {
175 /* Unknown bit - mark bits unknown up to the next known 0 */
177 imm = (d.known & ~d.value) | d.sign;
178 imm &= GENMASK(31, bit);
179 imm = imm ? ctz32(imm) : 31;
180 mask = GENMASK(imm, bit);
186 if (!(d.value & BIT(bit))) {
187 /* Bit is 0: we can set our carry, and the algorithm is done. */
192 /* Bit is 1 - set to 0 and continue algorithm */
193 d.value &= ~BIT(bit);
196 lightrec_propagate_addi(rs, rd, &d, v);
199 static void lightrec_propagate_slt(u32 rs, u32 rd, bool is_signed,
200 const struct constprop_data *d,
201 struct constprop_data *v)
205 if (is_signed && (v[rs].known & d->known
206 & (v[rs].value ^ d->value) & BIT(31))) {
207 /* If doing a signed comparison and the two bits 31 are known
208 * to be opposite, we can deduce the value. */
209 v[rd].value = v[rs].value >> 31;
210 v[rd].known = 0xffffffff;
215 for (bit = 32; bit > 0; bit--) {
216 if (!(v[rs].known & d->known & BIT(bit - 1))) {
217 /* One bit is unknown and we cannot figure out which
218 * value is smaller. We still know that the upper 31
221 v[rd].known = 0xfffffffe;
226 /* The two bits are equal - continue to the next bit. */
227 if (~(v[rs].value ^ d->value) & BIT(bit - 1))
230 /* The two bits aren't equal; we can therefore deduce which
231 * value is smaller. */
232 v[rd].value = !(v[rs].value & BIT(bit - 1));
233 v[rd].known = 0xffffffff;
239 /* rs == rt and all bits are known */
241 v[rd].known = 0xffffffff;
246 void lightrec_consts_propagate(const struct block *block,
248 struct constprop_data *v)
250 const struct opcode *list = block->opcode_list;
257 /* Register $zero is always, well, zero */
260 v[0].known = 0xffffffff;
262 if (op_flag_sync(list[idx].flags)) {
263 memset(&v[1], 0, sizeof(*v) * 31);
267 flags = list[idx - 1].flags;
269 if (idx > 1 && !op_flag_sync(flags)) {
270 if (op_flag_no_ds(flags))
277 /* After a BNE $zero + delay slot, we know that the
278 * branch wasn't taken, and therefore the other register
283 v[c.i.rt].known = 0xffffffff;
284 } else if (c.i.rt == 0) {
287 v[c.i.rs].known = 0xffffffff;
291 v[c.i.rs].value &= ~BIT(31);
292 v[c.i.rs].known |= BIT(31);
295 /* TODO: handle non-zero? */
300 case OP_REGIMM_BLTZAL:
301 v[c.i.rs].value &= ~BIT(31);
302 v[c.i.rs].known |= BIT(31);
305 case OP_REGIMM_BGEZAL:
306 v[c.i.rs].value |= BIT(31);
307 v[c.i.rs].known |= BIT(31);
308 /* TODO: handle non-zero? */
323 v[c.r.rd].value = v[c.r.rt].value << c.r.imm;
324 v[c.r.rd].known = (v[c.r.rt].known << c.r.imm)
325 | (BIT(c.r.imm) - 1);
326 v[c.r.rd].sign = v[c.r.rt].sign << c.r.imm;
330 v[c.r.rd].value = v[c.r.rt].value >> c.r.imm;
331 v[c.r.rd].known = (v[c.r.rt].known >> c.r.imm)
332 | ((BIT(c.r.imm) - 1) << (32 - c.r.imm));
333 v[c.r.rd].sign = c.r.imm ? 0 : v[c.r.rt].sign;
337 v[c.r.rd].value = (s32)v[c.r.rt].value >> c.r.imm;
338 v[c.r.rd].sign = (s32)(v[c.r.rt].sign
339 | (~v[c.r.rt].known & 0x80000000)) >> c.r.imm;
340 v[c.r.rd].known = (s32)v[c.r.rt].known >> c.r.imm;
343 case OP_SPECIAL_SLLV:
344 if ((v[c.r.rs].known & 0x1f) == 0x1f) {
345 imm = v[c.r.rs].value & 0x1f;
346 v[c.r.rd].value = v[c.r.rt].value << imm;
347 v[c.r.rd].known = (v[c.r.rt].known << imm)
349 v[c.r.rd].sign = v[c.r.rt].sign << imm;
356 case OP_SPECIAL_SRLV:
357 if ((v[c.r.rs].known & 0x1f) == 0x1f) {
358 imm = v[c.r.rs].value & 0x1f;
359 v[c.r.rd].value = v[c.r.rt].value >> imm;
360 v[c.r.rd].known = (v[c.r.rt].known >> imm)
361 | ((BIT(imm) - 1) << (32 - imm));
370 case OP_SPECIAL_SRAV:
371 if ((v[c.r.rs].known & 0x1f) == 0x1f) {
372 imm = v[c.r.rs].value & 0x1f;
373 v[c.r.rd].value = (s32)v[c.r.rt].value >> imm;
374 v[c.r.rd].sign = (s32)(v[c.r.rt].sign
375 | (~v[c.r.rt].known & 0x80000000)) >> imm;
376 v[c.r.rd].known = (s32)v[c.r.rt].known >> imm;
384 case OP_SPECIAL_ADDU:
385 if (is_known_zero(v, c.r.rs))
386 v[c.r.rd] = v[c.r.rt];
387 else if (is_known_zero(v, c.r.rt))
388 v[c.r.rd] = v[c.r.rs];
390 lightrec_propagate_addi(c.r.rs, c.r.rd, &v[c.r.rt], v);
394 case OP_SPECIAL_SUBU:
395 if (c.r.rs == c.r.rt) {
397 v[c.r.rd].known = 0xffffffff;
400 lightrec_propagate_sub(c.r.rs, c.r.rt, c.r.rd, v);
405 v[c.r.rd].known = (v[c.r.rt].known & v[c.r.rs].known)
406 | (~v[c.r.rt].value & v[c.r.rt].known)
407 | (~v[c.r.rs].value & v[c.r.rs].known);
408 v[c.r.rd].value = v[c.r.rt].value & v[c.r.rs].value & v[c.r.rd].known;
409 v[c.r.rd].sign = v[c.r.rt].sign & v[c.r.rs].sign;
413 v[c.r.rd].known = (v[c.r.rt].known & v[c.r.rs].known)
414 | (v[c.r.rt].value & v[c.r.rt].known)
415 | (v[c.r.rs].value & v[c.r.rs].known);
416 v[c.r.rd].value = (v[c.r.rt].value | v[c.r.rs].value) & v[c.r.rd].known;
417 v[c.r.rd].sign = v[c.r.rt].sign & v[c.r.rs].sign;
421 v[c.r.rd].value = v[c.r.rt].value ^ v[c.r.rs].value;
422 v[c.r.rd].known = v[c.r.rt].known & v[c.r.rs].known;
423 v[c.r.rd].sign = v[c.r.rt].sign & v[c.r.rs].sign;
427 v[c.r.rd].known = (v[c.r.rt].known & v[c.r.rs].known)
428 | (v[c.r.rt].value & v[c.r.rt].known)
429 | (v[c.r.rs].value & v[c.r.rs].known);
430 v[c.r.rd].value = ~(v[c.r.rt].value | v[c.r.rs].value) & v[c.r.rd].known;
431 v[c.r.rd].sign = v[c.r.rt].sign & v[c.r.rs].sign;
435 case OP_SPECIAL_SLTU:
436 lightrec_propagate_slt(c.r.rs, c.r.rd,
437 c.r.op == OP_SPECIAL_SLT,
441 case OP_SPECIAL_MULT:
442 case OP_SPECIAL_MULTU:
444 case OP_SPECIAL_DIVU:
445 if (OPT_FLAG_MULT_DIV && c.r.rd) {
449 if (OPT_FLAG_MULT_DIV && c.r.imm) {
450 v[c.r.imm].known = 0;
455 case OP_SPECIAL_MFLO:
456 case OP_SPECIAL_MFHI:
461 case OP_SPECIAL_JALR:
462 v[c.r.rd].known = 0xffffffff;
464 v[c.r.rd].value = block->pc + ((idx + 2) << 2);
474 if (OPT_FLAG_MULT_DIV && c.r.rd) {
476 v[c.r.rd].value = v[c.r.rs].value << c.r.op;
477 v[c.r.rd].known = (v[c.r.rs].known << c.r.op)
479 v[c.r.rd].sign = v[c.r.rs].sign << c.r.op;
482 v[c.r.rd].known = 0xffffffff;
487 if (OPT_FLAG_MULT_DIV && c.r.imm) {
489 v[c.r.imm].value = v[c.r.rs].value << (c.r.op - 32);
490 v[c.r.imm].known = (v[c.r.rs].known << (c.r.op - 32))
491 | (BIT(c.r.op - 32) - 1);
492 v[c.r.imm].sign = v[c.r.rs].sign << (c.r.op - 32);
493 } else if (c.i.op == OP_META_MULT2) {
494 v[c.r.imm].value = (s32)v[c.r.rs].value >> (32 - c.r.op);
495 v[c.r.imm].known = (s32)v[c.r.rs].known >> (32 - c.r.op);
496 v[c.r.imm].sign = (s32)v[c.r.rs].sign >> (32 - c.r.op);
498 v[c.r.imm].value = v[c.r.rs].value >> (32 - c.r.op);
499 v[c.r.imm].known = v[c.r.rs].known >> (32 - c.r.op);
500 v[c.r.imm].sign = v[c.r.rs].sign >> (32 - c.r.op);
511 struct constprop_data d = {
512 .value = (s32)(s16)c.i.imm,
517 lightrec_propagate_addi(c.i.rs, c.i.rt, &d, v);
519 /* immediate is zero - that's just a register copy. */
520 v[c.i.rt] = v[c.i.rs];
527 struct constprop_data d = {
528 .value = (s32)(s16)c.i.imm,
533 lightrec_propagate_slt(c.i.rs, c.i.rt,
534 c.i.op == OP_SLTI, &d, v);
539 v[c.i.rt].value = v[c.i.rs].value & c.i.imm;
540 v[c.i.rt].known = v[c.i.rs].known | ~c.i.imm;
545 v[c.i.rt].value = v[c.i.rs].value | c.i.imm;
546 v[c.i.rt].known = v[c.i.rs].known | c.i.imm;
547 v[c.i.rt].sign = (v[c.i.rs].sign & 0xffff) ? 0xffff0000 : v[c.i.rs].sign;
551 v[c.i.rt].value = v[c.i.rs].value ^ c.i.imm;
552 v[c.i.rt].known = v[c.i.rs].known;
553 v[c.i.rt].sign = (v[c.i.rs].sign & 0xffff) ? 0xffff0000 : v[c.i.rs].sign;
557 v[c.i.rt].value = c.i.imm << 16;
558 v[c.i.rt].known = 0xffffffff;
575 if (c.r.op == OP_CP2_BASIC) {
577 case OP_CP2_BASIC_MFC2:
588 v[c.r.rt].sign = 0xffff8000;
595 /* Unsigned 16-bit */
597 v[c.r.rt].known = 0xffff0000;
607 case OP_CP2_BASIC_CFC2:
618 v[c.r.rt].sign = 0xffff8000;
632 v[c.i.rt].sign = 0xffffff80;
636 v[c.i.rt].sign = 0xffff8000;
640 v[c.i.rt].known = 0xffffff00;
645 v[c.i.rt].known = 0xffff0000;
650 /* LWL/LWR don't write the full register if the address is
651 * unaligned, so we only need to know the low 2 bits */
652 if (v[c.i.rs].known & 0x3) {
653 imm = (v[c.i.rs].value & 0x3) * 8;
655 if (c.i.op == OP_LWL) {
656 imm = BIT(24 - imm) - 1;
657 v[c.i.rt].sign &= ~imm;
659 imm = imm ? GENMASK(31, 32 - imm) : 0;
662 v[c.i.rt].known &= imm;
674 v[c.m.rd] = v[c.m.rs];
678 v[c.m.rd].value = (s32)(s8)v[c.m.rs].value;
679 if (v[c.m.rs].known & BIT(7)) {
680 v[c.m.rd].known = v[c.m.rs].known | 0xffffff00;
683 v[c.m.rd].known = v[c.m.rs].known & 0x7f;
684 v[c.m.rd].sign = 0xffffff80;
689 v[c.m.rd].value = (s32)(s16)v[c.m.rs].value;
690 if (v[c.m.rs].known & BIT(15)) {
691 v[c.m.rd].known = v[c.m.rs].known | 0xffff0000;
694 v[c.m.rd].known = v[c.m.rs].known & 0x7fff;
695 v[c.m.rd].sign = 0xffff8000;
700 v[c.m.rd].known = v[c.m.rs].known;
701 v[c.m.rd].value = ~v[c.m.rs].value;
702 v[c.m.rd].sign = v[c.m.rs].sign;
709 v[31].known = 0xffffffff;
711 v[31].value = block->pc + ((idx + 2) << 2);
718 /* Reset register 0 which may have been used as a target */
721 v[0].known = 0xffffffff;
725 lightrec_get_constprop_map(const struct lightrec_state *state,
726 const struct constprop_data *v, u8 reg, s16 imm)
728 const struct lightrec_mem_map *map;
732 min = get_min_value(&v[reg]) + imm;
733 max = get_max_value(&v[reg]) + imm;
735 /* Handle the case where max + imm overflows */
736 if ((min & 0xe0000000) != (max & 0xe0000000))
737 return PSX_MAP_UNKNOWN;
739 pr_debug("Min: "X32_FMT" max: "X32_FMT" Known: "X32_FMT" Sign: "X32_FMT"\n",
740 min, max, v[reg].known, v[reg].sign);
745 for (i = 0; i < state->nb_maps; i++) {
746 map = &state->maps[i];
748 if (min >= map->pc && min < map->pc + map->length
749 && max >= map->pc && max < map->pc + map->length)
750 return (enum psx_map) i;
753 return PSX_MAP_UNKNOWN;