← Back to board

PR Detail

#206927
ValueTracking: Improve frexp known range from dominating conditions
ValueTracking

Description

Try to restrict the known range of the exponent result of llvm.frexp
based on dominating conditions. Identify comparisons that imply the
incoming value cannot introduce an overflow in a downstream ldexp
use. This pattern appears in the implementation of some complex math
functions and allows finite only math to prune out more edge case
paths.

One attributor test for ldexp regresses due to the switch from
computeKnownBits to computeConstantRange. computeConstantRange
does not try to handle non-splat vector constants for the binary
operators.

As a side effect, this also improves knowing that ldexp can't
introduce overflow for the 0 case.

Commit Versions & Reviews

Commit #1reviewinga2984d809con based1eae28e79
Buggy1 bug (1 patch-specific)292s · 1,327,946 tok · 17 rounds
View agent trace →

Analysis & Findings

Bug Triggering Analysis

The patch infers the exponent range of llvm.frexp from a dominating fabs(x) <= 1.0 condition by using ilogb(1.0) == 0 as the maximum exponent. This is off by one for nonzero finite inputs: frexp(1.0) returns mantissa 0.5 and exponent 1. The reduced test makes this observable with icmp sle i32 %e, 0. InstCombine transforms the guarded block to ret i1 true, but Alive2 produces the counterexample x = 1.0, where the original returns false.

Alive2 verification result:

  • Command: alive-tv -passes=instcombine
  • Result: incorrect transformation
  • Counterexample: %x = 1.0f
  • Source: %e = 1, %r = false
  • Target: true

Fix Weakness Analysis

The weakness is in computeKnownExponentRangeFromContext: it treats ilogb(K) as an inclusive upper bound for the frexp exponent when the path implies fabs(x) <= K. For finite nonzero values, frexp's exponent is ilogb(x) + 1, so inclusive/equality predicates at the boundary are unsound. The same issue likely affects oeq/ueq and non-power-of-two constants such as 0.75, and zero requires special handling because ilogb(0.0) returns an error sentinel while frexp(0.0) returns exponent 0.

Bugs (1)

BUG #1Patch-specific
Original IR
define i1 @bug_ole_one_exp_le0(float nofpclass(nan inf) %x) {
entry:
  %abs = call float @llvm.fabs.f32(float %x)
  %c = fcmp ole float %abs, 1.0
  br i1 %c, label %small, label %large
small:
  %fx = call { float, i32 } @llvm.frexp.f32.i32(float %x)
  %e = extractvalue { float, i32 } %fx, 1
  %r = icmp sle i32 %e, 0
  ret i1 %r
large:
  ret i1 false
}
declare float @llvm.fabs.f32(float) #0
declare { float, i32 } @llvm.frexp.f32.i32(float) #0
attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
Transformed IR
; ModuleID = '/data/tmp/tmp0upfw8ci/orig.ll'
source_filename = "/data/tmp/tmp0upfw8ci/orig.ll"

define i1 @bug_ole_one_exp_le0(float nofpclass(nan inf) %x) {
entry:
  %abs = call float @llvm.fabs.f32(float %x)
  %c = fcmp ugt float %abs, 1.000000e+00
  br i1 %c, label %large, label %small

small:                                            ; preds = %entry
  ret i1 true

large:                                            ; preds = %entry
  ret i1 false
}

; Function Attrs: nocallback nocreateundeforpoison nofree nosync nounwind speculatable willreturn memory(none)
declare float @llvm.fabs.f32(float) #0

; Function Attrs: nocallback nocreateundeforpoison nofree nosync nounwind speculatable willreturn memory(none)
declare { float, i32 } @llvm.frexp.f32.i32(float) #0

attributes #0 = { nocallback nocreateundeforpoison nofree nosync nounwind speculatable willreturn memory(none) }
Output Log
----------------------------------------
define i1 @bug_ole_one_exp_le0(float nofpclass(519) %x) {
entry:
  %abs = fabs float nofpclass(519) %x
  %c = fcmp ole float %abs, 1e+00
  br i1 %c, label %small, label %large

large:
  ret i1 0

small:
  %fx = frexp float nofpclass(519) %x
  %e = extractvalue {float, i32} %fx, 1
  %r = icmp sle i32 %e, 0
  ret i1 %r
}
=>
define i1 @bug_ole_one_exp_le0(float nofpclass(519) %x) {
entry:
  %abs = fabs float nofpclass(519) %x
  %c = fcmp ugt float %abs, 1e+00
  br i1 %c, label %large, label %small

small:
  ret i1 1

large:
  ret i1 0
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
float nofpclass(519) %x = #x3f800000 (1e+00)

Source:
float %abs = #x3f800000 (1e+00)
i1 %c = #x1 (1)
  >> Jump to %small
{float, i32} %fx = { #x3f000000 (5e-01), #x00000001 (1) }
i32 %e = #x00000001 (1)
i1 %r = #x0 (0)

Target:
float %abs = #x3f800000 (1e+00)
i1 %c = #x0 (0)
  >> Jump to %small
Source value: #x0 (0)
Target value: #x1 (1)

Summary:
  0 correct transformations
  1 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

Test Strategies

1Inclusive one off-by-one overflow guard
Target
Mutate an existing frexp_fcmp_ole_1 / frexp_fcmp_ogt_1 false-edge test so the ldexp source can be the largest finite float/double and the result is guarded by `fcmp oeq +inf` or an `is_fpclass(inf)` path.
Rationale
The new context range uses ilogb(K) as the inclusive maximum frexp exponent for fabs(x) <= K. For nonzero finite x, frexp exponent is ilogb(x)+1. Thus fabs(x) <= 1.0 permits x=1.0 with exponent 1, but the analysis records max 0.
Expected Issue
The optimizer may prove the frexp exponent is <= 0 and remove an ldexp overflow check, but at x = 1.0 frexp returns exponent 1, so ldexp(max_finite, 1) can overflow to +inf and the removed check was semantically observable.
2Non-power-of-two bound off-by-one
Target
Mutate the dominating compare constant from 1.0 to 0.75 (or hex f0x3F400000) and add an integer comparison/select on the extracted frexp exponent, such as `select (icmp slt %exp, 0) ...`.
Rationale
For a non-power-of-two K in (0.5, 1), ilogb(K) is -1, but values in [0.5,K] have frexp exponent 0. The patch accepts any finite K <= 1.0, not just strict comparisons against powers of two where ilogb(K) is a valid upper bound.
Expected Issue
Integer users of the exponent may be folded incorrectly, e.g. `icmp sle i32 %exp, -1` or `icmp slt i32 %exp, 0` may become true under a dominating `fabs(x) <= 0.75`, although x=0.75 gives frexp exponent 0.
3Zero limit pathological range
Target
Mutate the compare limit to `0.0` with a no-NaN/non-inf source and use the extracted exponent in an `icmp` (for example `icmp slt %exp, -1000000`) or downstream ldexp classification.
Rationale
`ilogb(0.0)` returns APFloat::IEK_Zero (INT_MIN+1), but frexp(0.0) returns exponent 0. Under `fabs(x) <= 0.0` or `fabs(x) == 0.0`, the patch sets the adjusted max to IEK_Zero rather than 0, making max less than the normal minimum exponent and potentially wrapping when converted to ConstantRange.
Expected Issue
The analysis may create a nonsensical or wrapped ConstantRange for the exponent, possibly leading to wrong folds of comparisons against very negative values, or assertions in debug builds around ConstantRange construction/use.
4OEQ/UEQ exact-bound exponent
Target
Mutate an existing `fcmp ole/ule` case to `fcmp oeq float fabs(x), 1.0` (and separately `0.5` or `0.75`) on the true edge, then test either `ldexp(max_finite, %exp)` overflow or an `icmp sle %exp, 0` fold.
Rationale
The patch groups `oeq`/`ueq` with less-or-equal predicates. Equality to a finite nonzero magnitude gives a precise frexp exponent of ilogb(K)+1, not ilogb(K). With `nofpclass(nan inf)` on the source, unordered complications are removed and the off-by-one becomes directly observable.
Expected Issue
Equality cases may be optimized as if the exponent is <= ilogb(K), but when fabs(x) == K and K is nonzero, the exponent is ilogb(K)+1; this can miscompile both integer exponent tests and ldexp overflow pruning.
5Narrow frexp exponent type wrapping
Target
Mutate `known-range-frexp-exp.ll` or the dominating-condition test to declare/use `@llvm.frexp.f32.i8` (and possibly i1/i2), extract the exponent, and feed it to signed `icmp` or `llvm.ldexp.f32.i8` under a dominating `fabs(x) < 1.0` condition.
Rationale
The frexp exponent range for float is roughly [-149,128], which does not fit in i8 and certainly not in i1/i2. The patch constructs `APInt(BitWidth, MinExp, isSigned=true)` and `APInt(BitWidth, MaxExp+1, isSigned=true)`, so narrow result types can wrap the mathematical bounds. Existing tests cover i16/i128 but not too-narrow types.
Expected Issue
For small integer exponent result types, min/max APInt construction may truncate the real float exponent bounds, producing wrapped or overly precise ConstantRanges and incorrect signed comparisons or known-fp-class deductions.