Re: [gfortran] Exponentiation by integral exponents

Re: [gfortran] Exponentiation by integral exponents

[Tobias Schlüter]

[ forwarding to gcc@gcc.gnu.org so more knowledgeable people can comment 
on the point I make in the last paragraph ]

Feng Wang wrote:
> Hi, Tobi, Paul, etc
>   I missed the discussion because of my poor modem. But I have implemented this
> and the patch is under test. IMHO, we have to implement the algorithm described
> by Knuth in the FE. BUILT_IN_POW only deals with Real type. How about complex
> type? There are also many problems to consider when an integer is raised to an
> negative integer. The result is just 0, -1, or 1. So it is not correct to
> convert integer to real. 

This is a good point that I hadn't thought about.

> I think we should also implement the runtime library
> function powi. When a value is raised to an varible integer, we just call the
> library function. The value may be of integer type, real type or complex type.

Yeah, I thought so as well. I was already looking for an implementation.

> I have done these and in a few days I will give the patch. I didn't port Andy's
> implementation. Andy's vertion only deal with exponent under 100 and don't
> consider (integer ** negative integer). The main algorithm in my implementation
> is from builtins.c and can deal with an arbitrary integer exponent. The
> algorithm in powi library function is from libf77.

If your patch is finished I agree that we should go with your patch, as 
mine is far from finished. I chose to port Andy's implementation as this 
was my first step in GCC trees, and I didn't want to do something from 
scratch :-)

I don't necessarily agree that this should be handled in the FE, though. 
There might be other languages that have an "integral exponent" idiom, 
so a language independent solution might be preferable.

- Tobi

Are BUILT_IN_POWII and BUILT_IN_POWCI necessary? (RE: Exponentiation by integral exponents)

[Feng Wang]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=gb2312, Size: 2443 bytes --]

 --- Tobias_Schlüter <tobias.schlueter@physik.uni-muenchen.de> µÄÕýÎÄ£º> [
forwarding to gcc@gcc.gnu.org so more knowledgeable people can comment 
> on the point I make in the last paragraph ]
> 
> Feng Wang wrote:
> > Hi, Tobi, Paul, etc
> >   I missed the discussion because of my poor modem. But I have implemented
> this
> > and the patch is under test. IMHO, we have to implement the algorithm
> described
> > by Knuth in the FE. BUILT_IN_POW only deals with Real type. How about
> complex
> > type? There are also many problems to consider when an integer is raised to
> an
> > negative integer. The result is just 0, -1, or 1. So it is not correct to
> > convert integer to real. 
> 
> This is a good point that I hadn't thought about.
> 
> > I think we should also implement the runtime library
> > function powi. When a value is raised to an varible integer, we just call
> the
> > library function. The value may be of integer type, real type or complex
> type.
> 
> Yeah, I thought so as well. I was already looking for an implementation.
> 
> > I have done these and in a few days I will give the patch. I didn't port
> Andy's
> > implementation. Andy's vertion only deal with exponent under 100 and don't
> > consider (integer ** negative integer). The main algorithm in my
> implementation
> > is from builtins.c and can deal with an arbitrary integer exponent. The
> > algorithm in powi library function is from libf77.
> 
> If your patch is finished I agree that we should go with your patch, as 
> mine is far from finished. I chose to port Andy's implementation as this 
> was my first step in GCC trees, and I didn't want to do something from 
> scratch :-)
> 
> I don't necessarily agree that this should be handled in the FE, though. 
> There might be other languages that have an "integral exponent" idiom, 
> so a language independent solution might be preferable.

To this point it is reasonable. But thus we will have to build and expand
BUILT_IN_POWII (int ** int) and  BUILT_IN_POWCI (complex ** int) in the BE. Is
this necessary?  Maybe the GCC community can give us some suggestion.

Feng Wang

_________________________________________________________
Do You Yahoo!? 
»ÝÆÕTTÓÎÏ·¾ç£¬ÍæÓÎÏ·£¬Öд󽱣¡
http://cn.rd.yahoo.com/mail_cn/tag/SIG=1402c0to2/**http%3A%2F%2Fhp.allyes.com%2Flaserjet%2Fgamestory%2Findex.html%3Fjumpid%3Dex_hphqapcn_MongooseLJ1010%2F201073CN407016%2FYahoo

Re: [gfortran] Exponentiation by integral exponents

[Andrew Pinski]

On Apr 27, 2004, at 17:14, Tobias Schlüter wrote:

>
> FYI I have ported Andy's code for exponentiation by an integral 
> exponent to our tree. This is an implementation of Knuth's algorithm 
> which uses the minimum number of multiplications for exponents < 100. 
> As an additional bonus there's no more need to special case an 
> exponent of three, the optimal code is generated automatically. I'll 
> submit this once my copyright assignment is handled.
>
> Does anybody have any insight on how to write testcases for this?

You should not need it if you use __builtin_pow and you turn on
flag_unsafe_math_optimizations on.  Maybe the best way is to have 
another flag
to say expand __builtin_pow always.

Thanks,
Andrew Pinski

Re: [gfortran] Exponentiation by integral exponents

[Tobias Schlüter]

Andrew Pinski wrote:
> 
> On Apr 27, 2004, at 17:14, Tobias Schlüter wrote:
> 
>>
>> FYI I have ported Andy's code for exponentiation by an integral 
>> exponent to our tree. This is an implementation of Knuth's algorithm 
...
> 
> You should not need it if you use __builtin_pow and you turn on
> flag_unsafe_math_optimizations on.  Maybe the best way is to have 
> another flag
> to say expand __builtin_pow always.
> 

Does the builtin recognize the case pow(x,(float)i), where i is an 
integer? Then this sounds like a very good idea.

- Tobi

Re: [gfortran] Exponentiation by integral exponents

[Andrew Pinski]

On Apr 27, 2004, at 18:07, Tobias Schlüter wrote:

> Andrew Pinski wrote:
>> On Apr 27, 2004, at 17:14, Tobias Schlüter wrote:
>>>
>>> FYI I have ported Andy's code for exponentiation by an integral 
>>> exponent to our tree. This is an implementation of Knuth's algorithm
> ...
>> You should not need it if you use __builtin_pow and you turn on
>> flag_unsafe_math_optimizations on.  Maybe the best way is to have 
>> another flag
>> to say expand __builtin_pow always.
>
> Does the builtin recognize the case pow(x,(float)i), where i is an 
> integer? Then this sounds like a very good idea.

Yes it does except that flag_unsafe_math_optimizations has to be true 
but we can
easily change that.

Thanks,
Andrew Pinski

Re: [gfortran] Exponentiation by integral exponents

[Paul Brook]

On Tuesday 27 April 2004 23:07, Tobias Schlüter wrote:
> Andrew Pinski wrote:
> > On Apr 27, 2004, at 17:14, Tobias Schlüter wrote:
> >> FYI I have ported Andy's code for exponentiation by an integral
> >> exponent to our tree. This is an implementation of Knuth's algorithm
>
> ...
>
> > You should not need it if you use __builtin_pow and you turn on
> > flag_unsafe_math_optimizations on.  Maybe the best way is to have
> > another flag
> > to say expand __builtin_pow always.
>
> Does the builtin recognize the case pow(x,(float)i), where i is an
> integer? Then this sounds like a very good idea.

Maybe the way to indicate we always want to expand __builtin_pow would be to 
pass the second parameter with an integer type. It may be easier to add 
__builtin_powi to avoid needing polymorphic builtins.

Paul

Re: [gfortran] Exponentiation by integral exponents

[Tobias Schlüter]

Paul Brook wrote:
> On Tuesday 27 April 2004 23:07, Tobias Schlüter wrote:
> 
>>Andrew Pinski wrote:
>>
>>>On Apr 27, 2004, at 17:14, Tobias Schlüter wrote:
>>>
>>>>FYI I have ported Andy's code for exponentiation by an integral
>>>>exponent to our tree. This is an implementation of Knuth's algorithm
>>
>>...
>>
>>
>>>You should not need it if you use __builtin_pow and you turn on
>>>flag_unsafe_math_optimizations on.  Maybe the best way is to have
>>>another flag
>>>to say expand __builtin_pow always.
>>
>>Does the builtin recognize the case pow(x,(float)i), where i is an
>>integer? Then this sounds like a very good idea.
> 
> 
> Maybe the way to indicate we always want to expand __builtin_pow would be to 
> pass the second parameter with an integer type. It may be easier to add 
> __builtin_powi to avoid needing polymorphic builtins.

Definitely.

Anyway, I tried to implement Andrew's suggestion as a quick'n'dirty 
hack. Right now I get an ICE. What is the correct way to generate the 
equivalent of a typecast in C?

What I tried was this: gfc_conv_power_op has this code:

   type = TREE_TYPE (lse.expr);

   kind = expr->op1->ts.kind;
   switch (expr->op2->ts.type)
     {
     case BT_INTEGER:
       /* Integer powers are expanded inline as multiplications.  */
       gfc_conv_integer_power (se, lse.expr, rse.expr);
       return;

Instead of calling gfc_integer_power and returning, I want to convert 
rse.expr to the type of lse.expr. So I tried both of the following 
(gfc_conv_expr_type has no explanatory comment, so I'm just guessing 
that this might be the function I'm looking for):
       gfc_conv_expr_type (&rse, expr->op2, type); // first try
       rse.expr = convert (type, rse.expr);        // second try

After that I select the function based on the type of lse.expr as in the 
real case and continue as if rse.expr had not been int all the time.

What am I missing? I'm still within my first three hours of messing with 
gcc trees, so I might well be missing the obvious.

- Tobi