llvm dev - Apr 2015 - [LLVMdev] [RFC][Float2Int] Converting (fcmp Pred, x * F, y) to (ICmp ...)

Hi,

 

I'm trying expand the Float2Int pass in order to make it able to optimize

expressions like f * x  > y, where x and y are integers (we'll assume
unsigned for

simplicity) and f is a floating point constant. The optimization would
convert

the expression to something like:

 

  (a * x)/b > y

 

where a and b are integers guessed by the compiler (currently using
continued

fractions, but some other method could also be used). The exact expression

would depend on the comparison type and on the type of input integers.

 

Note that dividing by an integer constant should be a cheap operation

compared to FP multiplication and comparison as this would get lowered to a

multiply+subtract+shift sequence (and should certainly be true on cores with
no

FP unit)

 

The change will add some machinery to Float2Int in order to be able to

match certain known patterns. All patterns will have exactly representable

inputs and outputs. In this case, the FCMP will have two inputs, x and y and

one output (the result of the comparison). This allows us to use the
existing

Float2Int infrastructure to track the integer length that would be required

for the conversion.

 

The main difficulty I can see with this is validating the transformation.
Ideally

the property that we want to prove for the guessed integers a and b would be

that (a*x)/b == round_to_zero(f * to_float(x)), for every integer x in a
given

range. The problem with this is that we would need to come up with a
reasonably

quick method of proving this.

 

My best guess (still need to work out the exact details) would be that we
only

need to check the first and last b numbers of the range. A hand-wavy
argument

for this would be that since errors increase on the extremities of the
range, so if

an error appears anywhere it must also appear  at the edges of the range.

I still need to prove this. If there are any floating-point experts that can
help

with this, I would greatly appreciate it.

 

Any other comments about the overall merits of the idea and the approach are

of course also welcome!

 

Thanks,

Silviu

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/dbf6769e/attachment.html>

> On Apr 29, 2015, at 10:06 AM, Silviu Baranga <Silviu.Baranga at
arm.com> wrote:
> 
> Note that dividing by an integer constant should be a cheap operation
> compared to FP multiplication and comparison as this would get lowered to a
> multiply+subtract+shift sequence (and should certainly be true on cores
with no
> FP unit)
>  
This is not true on the targets I care about. The integer division (which, even
with the division by constant expansion to multiplies with magic constants)
would be significantly more expensive.

-Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/b474877f/attachment.html>

> On Apr 29, 2015, at 2:33 PM, Matt Arsenault <arsenm2 at gmail.com>
wrote:
> 
>> On Apr 29, 2015, at 10:06 AM, Silviu Baranga <Silviu.Baranga at
arm.com <mailto:Silviu.Baranga at arm.com>> wrote:
>> 
>> Note that dividing by an integer constant should be a cheap operation
>> compared to FP multiplication and comparison as this would get lowered
to a
>> multiply+subtract+shift sequence (and should certainly be true on cores
with no
>> FP unit)
>>  
> 
> This is not true on the targets I care about. The integer division (which,
even with the division by constant expansion to multiplies with magic constants)
would be significantly more expensive.
What targets *does* this benefit?  Soft-float targets and Cortex-A8?

Anyway, both integer and floating-point multiplication and division are
monotonic, so it suffices to check the two values of x that bracket y/f.

– Steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150429/bbf3325e/attachment.html>