ΒΆOptional<llvm::APInt> SolveQuadraticEquationWrap(
    llvm::APInt A,
    llvm::APInt B,
    llvm::APInt C,
    unsigned int RangeWidth)

Description

Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g. 32 for i32). This function finds the smallest number n, such that (a) n >= 0 and q(n) = 0, or (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all integers, belong to two different intervals [Rk, Rk+R), where R = 2^BW, and k is an integer. The idea here is to find when q(n) "overflows" 2^BW, while at the same time "allowing" subtraction. In unsigned modulo arithmetic a subtraction (treated as addition of negated numbers) would always count as an overflow, but here we want to allow values to decrease and increase as long as they are within the same interval. Specifically, adding of two negative numbers should not cause an overflow (as long as the magnitude does not exceed the bit width). On the other hand, given a positive number, adding a negative number to it can give a negative result, which would cause the value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is treated as a special case of an overflow. This function returns None if after finding k that minimizes the positive solution to q(n) = kR, both solutions are contained between two consecutive integers. There are cases where q(n) > T, and q(n+1) < T (assuming evaluation in arithmetic modulo 2^BW, and treating the values as signed) by the virtue of *signed* overflow. This function will *not* find such an n, however it may find a value of n satisfying the inequalities due to an *unsigned* overflow (if the values are treated as unsigned). To find a solution for a signed overflow, treat it as a problem of finding an unsigned overflow with a range with of BW-1. The returned value may have a different bit width from the input coefficients.

Declared at: llvm/include/llvm/ADT/APInt.h:2266

Parameters

llvm::APInt A
llvm::APInt B
llvm::APInt C
unsigned int RangeWidth