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

未关闭
  • 哪里不对？
#20,886 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

还没有人认领这个 Issue。

评估

难度
3/5
预计耗时
1-2 天
新手友好度
42/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
cpp, python
领域
compilers

调研方向

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.

由索引模型根据 Issue 内容生成。

描述

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
主要语言
Python
星标
13.9k
派生
4k
平均合并
7 小时 59 分钟
30 天内合并 PR
159

环境准备

这个项目没有提供开发容器、Dockerfile 或贡献指南，环境需要你自己搭建：先看它的 README，通用步骤见我们的新手贡献指南。

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

apache/tvm 的其他 Issue

查看 apache/tvm 的全部 Issue

相似的 Issue

更多 Python Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。