[Bug] [Arith] ConstIntBound excludes zero for a wrapping uint32 left shift

Đang mở
  • Có gì không ổn?
#20,886 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
3/5
Thời gian dự kiến
1-2 ngày
Mức phù hợp với người mới
42/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
cpp, python
Lĩnh vực
compilers

Hướng nghiên cứu

The unsound bound comes from InfAwareLeftShift as called in src/arith/const_int_bound.cc around lines 497-508, which ignores the uint32 result width. Start by running the repro script with an LLVM-enabled build, then check how the shift bound is computed for unsigned dtypes. Done means the analyzer's bound for uint32(2) << i with i in [0, 32) includes 0, and the existing arith tests still pass.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

needs-triage type: bug
Expected behavior

For i in [0, 32), the constant integer bound of uint32(2) << uint32(i) should include zero. At i = 31, the uint32 result wraps modulo 2**32 and is exactly zero. All shift counts are smaller than the 32-bit operand width.

This uses the default analyzer context without allow_uint_as_index or any opt-in no-overflow assumption. A conservative bound covering the uint32 range would be acceptable.

Actual behavior

Analyzer.const_int_bound returns [2, 4294967296], whose lower bound excludes the valid result zero.

The script below also compiles and executes the same expression for all 32 shift counts on LLVM, verifies every output against a Python modulo-2**32 reference, and then shows the contradictory inferred bound:

inferred bound: 2 4294967296
actual uint32(2) << 31: 0
AssertionError: inferred bound [2, 4294967296] excludes 0

The assertion is a check in the reproduction script; TVM returns the incorrect bound without raising an error. The generated kernel returns the expected uint32 results. The demonstrated defect is the unsound bound, rather than an observed uint32 code-generation error.

This exact script reproduced in three fresh Python processes. Controls limiting uint32 shifts to [0, 31), or widening the operand to uint64 while retaining [0, 32), avoid wraparound and give bounds consistent with the computed values.

In the tested source snapshot, src/arith/const_int_bound.cc:497-508 passes the operand bounds to InfAwareLeftShift. That helper accounts for the int64 computation limit but does not account for the uint32 result width. This appears to explain the omitted wraparound value.

Environment
  • Apache TVM 0.26.dev0+source.8f328e8 (source snapshot)
  • Ubuntu 22.04.5, Linux 6.8.0-52-generic, x86-64
  • Python 3.11.16
  • LLVM 15.0.7, target llvm

The analyzer example requires no GPU; the compiled LLVM kernel verifies the concrete counterexample.

Steps to reproduce

Save as repro.py and run python repro.py in a TVM build with LLVM enabled:

import numpy as np
import tvm
from tvm import tirx
from tvm.script import ir as I, tirx as T

i = tirx.Var("i", "int32")
analyzer = tvm.arith.Analyzer()
analyzer.bind(i, tvm.ir.Range(0, 32))
expr = tirx.shift_left(tirx.const(2, "uint32"), tirx.Cast("uint32", i))
bound = analyzer.const_int_bound(expr)
print("inferred bound:", bound.min_value, bound.max_value, flush=True)

@I.ir_module
class Module:
    @T.prim_func(s_tir=True)
    def main(out: T.Buffer((32,), "uint32")):
        for j in range(32):
            out[j] = T.shift_left(T.uint32(2), T.Cast("uint32", j))

executable = tvm.compile(Module, target="llvm")
out = tvm.runtime.empty((32,), "uint32", tvm.cpu())
executable["main"](out)
actual = out.numpy()
expected = np.array([(2 << j) & 0xffffffff for j in range(32)], dtype="uint32")
np.testing.assert_array_equal(actual, expected)
value = int(actual[31])
print("actual uint32(2) << 31:", value, flush=True)
assert bound.min_value <= value <= bound.max_value, (
    f"inferred bound [{bound.min_value}, {bound.max_value}] excludes {value}"
)
Triage
  • needs-triage
  • type: bug
Ngôn ngữ chính
Python
Star
13.9k
Fork
4k
Merge trung bình
7 giờ 59 phút
Pull request đã merge (30 ngày)
159

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của apache/tvm

Tất cả issue của apache/tvm

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.