llvm dev - Jan 2009 - [LLVMdev] Loop elimination with floating point counter.

FWIW, I believe icc -O3 turns on the equivalent of -ffast-math by default.
I could be misremembering which compilers do this though :)
This flag allows you to make all kinds of nice simplfiying assumptions
about floating point.

On Thu, Jan 8, 2009 at 7:45 PM, Owen Anderson <resistor at mac.com>
wrote:
> I assume it checks that the end condition and the increment can both
> be represented precisely with integer types.
>
> --Owen
>
> On Jan 8, 2009, at 9:49 AM, Martin Geisse wrote:
>
>> Isn't "simplifying" the loop index to an integer also
dependent on
>> precision issues? The following loop is infinite:
>>
>> for (float i=0.0; i<...; i+=1.0) {}
>>
>> where ... is a large "integral" float literal, e.g. 2^40. At
some
>> point, adding 1.0 to the loop index would not cause any changes
>> because of precision issues. However, if the float type is replaced
>> by some sufficiently large integer type, the loop terminates.
>>
>> The necessary reasoning may be simpler though.
>>
>> Greetings,
>> Martin Geisse
>>
>> On Jan 8, 2009, at 6:34 PM, Owen Anderson wrote:
>>
>>> It's because with 1.0f, the loop index is simplified into an
integer.
>>> With 1.2f, it isn't.  The loop deletion pass is dependent on
the loop
>>> analyses being able to determine that the loop is finite, which
they
>>> don't attempt to do for loops with floating point indices.
>>> Attempting
>>> to do so would require additional reasoning about floating point
>>> precision issues.
>>>
>>> --Owen
>>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Thanks for many comments.

The loop with finite fp values(which could be representable in IEEE754
fp format) such like,

void
foo() {
    float i;

    for (i = 0.0f; i < 1000.0f; i += 1.2f) {
    }
}

could reach the end condition under any fp rounding mode,
and eliminating the loop has no side effects.
(for example, floating point control register does not change because
the increment does not cause the overflow)

Thus I believe the loop as shown above could be removed safely.


FYI, gcc -O3 turns fp loop counter into integer, but gcc does not
optimize further(eliminate the loop).

$ gcc -O3 floop.c

_foo:
	pushl	%ebp
	movl	$834, %eax
	movl	%esp, %ebp
	.align 4,0x90
L2:
	decl	%eax
	jne	L2

--
Syoyo

On Fri, Jan 9, 2009 at 1:11 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> FWIW, I believe icc -O3 turns on the equivalent of -ffast-math by default.
> I could be misremembering which compilers do this though :)
> This flag allows you to make all kinds of nice simplfiying assumptions
> about floating point.
>
> On Thu, Jan 8, 2009 at 7:45 PM, Owen Anderson <resistor at mac.com>
wrote:
>> I assume it checks that the end condition and the increment can both
>> be represented precisely with integer types.
>>
>> --Owen
>>
>> On Jan 8, 2009, at 9:49 AM, Martin Geisse wrote:
>>
>>> Isn't "simplifying" the loop index to an integer also
dependent on
>>> precision issues? The following loop is infinite:
>>>
>>> for (float i=0.0; i<...; i+=1.0) {}
>>>
>>> where ... is a large "integral" float literal, e.g. 2^40.
At some
>>> point, adding 1.0 to the loop index would not cause any changes
>>> because of precision issues. However, if the float type is replaced
>>> by some sufficiently large integer type, the loop terminates.
>>>
>>> The necessary reasoning may be simpler though.
>>>
>>> Greetings,
>>> Martin Geisse
>>>
>>> On Jan 8, 2009, at 6:34 PM, Owen Anderson wrote:
>>>
>>>> It's because with 1.0f, the loop index is simplified into
an integer.
>>>> With 1.2f, it isn't.  The loop deletion pass is dependent
on the loop
>>>> analyses being able to determine that the loop is finite, which
they
>>>> don't attempt to do for loops with floating point indices.
>>>> Attempting
>>>> to do so would require additional reasoning about floating
point
>>>> precision issues.
>>>>
>>>> --Owen
>>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

On Jan 14, 2009, at 5:11 AM, Syoyo Fujita wrote:
> Thanks for many comments.
>
> The loop with finite fp values(which could be representable in IEEE754
> fp format) such like,
Sure, LLVM could definitely do this.  If you're interested, I'd  
suggest starting by extending the existing code that we have to do  
this.  The existing code just handles increments by unit constants, so  
it doesn't trigger with 1.2.

-Chris