google / google/xls

type_inference_v2 is not aware that the 'too large shift' is impossible

Open
#2,440 0 comments 0 reactions 0 assignees View on GitHub
dslx dslx:TIv2
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

**Describe the bug**
#![feature(type_inference_v2)] is erroneously flagging code that worked as intended under v1. This is in stdlib/fixed_point.x

I think this bug is [related to this.](https://github.com/google/xls/issues/2425)

**To Reproduce**
Steps to reproduce the behavior:
1. enable #![feature(type_inference_v2)] at the top of stdlib/fixed_point.x
2. build any dslx_library that depends on fixed_point.x (or just build fixed_point.x)
3. See error

**Expected behavior**
The file should build without errors.

**Explanation**
consider this block in fixed_point.x
```
pub fn round_ne_bits_discarded

(a: FixedPoint) -> FixedPoint {
if NUM_BITS_ROUNDED == u32:0 {
// no rounding needed, but we have to make DSLX happy about unifying the types
// (otherwise we'd just return `a`)
make_fixed_point(a.significand as sN[NB_R])
} else {
// keeps the least significant retained bit
let lsb_bit_mask = uN[NB_A]:1 << NUM_BITS_ROUNDED;

const_assert!(NUM_BITS_ROUNDED > 0); // I added this for debugging

// the index of the bit that is equal to half of the result's ULP
let halfway_idx = NUM_BITS_ROUNDED as uN[NB_A] - uN[NB_A]:1;

// keeps the half-ULP bit
let halfway_bit_mask = uN[NB_A]:1 << halfway_idx;
```

Note that we have two cases, NUM_BITS_ROUNDED=0 and NUM_BITS_ROUNDED!=0 (i.e., the `else` case). Logically, only one of these cases 'exists' for a specific instantiation of the function.

What you'll see without the `const_assert!(NUM_BITS_ROUNDED > 0)` that I added is
```
0341: let halfway_bit_mask = uN[NB_A]:1 << halfway_idx;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^---------^ TypeInferenceError: uN[9] Shifting a 9-bit value (`uN[9]`) by a constexpr shift of 511 exceeds its bit width.
```
I didn't dig in, but presumably there's a unit test that instantiates this function with NUM_BITS_ROUNDED=0 and NB_A=9

I added the const assert and now I see
```
0337: const_assert!(NUM_BITS_ROUNDED > 0);
~~~~~~~~~~~~~~^----------------------------------^ TypeInferenceError: const_assert! failure: `NUM_BITS_ROUNDED > 0`
```
so clearly, type inference is looking inside the else case, even though NUM_BITS_ROUNDED=0, and creating an overshift error for code that "doesn't exist". Instead, it thinks NUM_BITS_ROUNDED is 0, so then (0-1) underflows to 511, which is a too-large shift amount.

Ideally, type inference would be able to understand that this function is being instantiated with NUM_BITS_ROUNDED=0, and thus the `else` case is impossible and overshift errors and the like that are in the else case should not be flagged.

I think the overshift error is good and should be kept, but in a logically impossible case like this, there should be no error. And I think the fact that this is parametric is important and relevant (which is why I linked the other bug). On the other hand, code like this is always nonsensical and thus should be flagged as bad:
```
let x: u32;
if 1 < 0 {
x << 42
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.