Re: strength redcution

Danny.Dube@ift.ulaval.ca (Danny =?iso-8859-1?q?Dub=E9?=)
1 May 2005 01:59:58 -0400

          From comp.compilers

Related articles
strength redcution julie.spicer@verizon.net (Vespasian) (2005-04-30)
Re: strength redcution Danny.Dube@ift.ulaval.ca (2005-05-01)
Re: strength redcution gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-01)
| List of all articles for this month |

From: Danny.Dube@ift.ulaval.ca (Danny =?iso-8859-1?q?Dub=E9?=)
Newsgroups: comp.compilers
Date: 1 May 2005 01:59:58 -0400
Organization: Compilers Central
References: 05-04-097
Keywords: optimize

Vespasian <julie.spicer@verizon.net> writes:
> Anyone know how to replace the expression,
>
> i div c,
>
> with addition and/or subtraction, where c in a constant and
> i is the index of a loop that increments with a step size of 1
> [Seems to me you'd have to keep a separate counter and each time
> that counter reached c, add one to the quotient value and reset
> the counter. -John]


The following paper may present a solution to your problem:


                http://citeseer.ist.psu.edu/granlund94division.html


The authors explain how to replace the expression:


                i div c


where c is a constant by an equivalent expression:


                (i * t) div (2 ^ k)


where t and k are constants. The benefits come from the fact that a
division by a power of 2 can be simulated (on most machines) using a
shift of the bits to the right, which turns the expression into:


                (i * t) >> k


What is particularly interesting in your case is that i is an
induction variable and the value of i div c is easy to update when i
is incremented. The update can be done using only an addition and a
shift. You need to introduce a temporary variable x which holds the
current value of i * t. When i is initialized to V, you need to
initialize x to V * t. Each time i is incremented, you add t to x.
Then the current value of the quotient can be obtained by computing
x >> k.


Note that you have to be careful because, in worst case, you need to
perform the replacement computations in n+1 bits in order to correctly
simulate the division in n bits.


--
                Danny Dubé
                Danny.Dube@ift.ulaval.ca
[Seems like an awfully complicated way to do a modulo counter. -John]



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.