Induction variable

Induction variable

In computer science, an induction variable is a variable that gets increased or decreased by a fixed amount on every iteration of a loop, or is a linear function of another induction variable.

For example, in the following loop, i and j are induction variables:

for (i=0; i < 10; ++i) { j = 17 * i; }

Application to strength reduction

A common compiler optimization is to recognize the existence of induction variables and replace them with simpler computations; for example, the code above could be rewritten by the compiler as follows, on the assumption that the addition of a constant will be cheaper than a multiplication.

j = 0; for (i=0; i < 10; ++i) { j = j + 17; }

This optimization is a special case of strength reduction.

Application to reduce register pressure

In some cases, it is possible to reverse this optimization in order to remove an induction variable from the code entirely. For example:

extern int sum; int foo(int n) { int i, j; j = 5; for (i=0; i < n; ++i) { j += 2; sum += j; } return sum; }

This function's loop has two induction variables: i and j. Either one can be rewritten as a linear function of the other; therefore, the compiler may optimize this code as if it had been written

extern int sum; int foo(int n) { int i; for (i=0; i < n; ++i) { sum += (5 + 2*i); } return sum; }

Non-linear induction variables

The same optimizations can be applied to induction variables that are not necessarily linear functions of the loop counter; for example, the loop

j = 1; for (i=0; i < 10; ++i) { j = j << 1; }

may be converted to

for (i=0; i < 10; ++i) { j = 1 << i; }

ee also

*Loop optimization


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Variable length intake manifold — (VLIM) is an automobile engine manifold technology. As the name implies, VLIM can vary the length of the intake tract in order to optimize power and torque, as well as provide better fuel efficiency.There are two main effects of variable intake… …   Wikipedia

  • induction — [ ɛ̃dyksjɔ̃ ] n. f. • XIVe; « suggestion » 1290; lat. inductio 1 ♦ Opération mentale qui consiste à remonter des faits à la loi, de cas donnés (propositions inductrices) le plus souvent singuliers ou spéciaux, à une proposition plus générale. ⇒… …   Encyclopédie Universelle

  • Induction Magnétique — Induction électromagnétique Pour les articles homonymes, voir Induction. Chauffage par induction par un solénoïde …   Wikipédia en Français

  • Induction magnetique — Induction électromagnétique Pour les articles homonymes, voir Induction. Chauffage par induction par un solénoïde …   Wikipédia en Français

  • Induction magnétique — Induction électromagnétique Pour les articles homonymes, voir Induction. Chauffage par induction par un solénoïde …   Wikipédia en Français

  • Induction — In*duc tion, n. [L. inductio: cf. F. induction. See {Induct}.] [1913 Webster] 1. The act or process of inducting or bringing in; introduction; entrance; beginning; commencement. [1913 Webster] I know not you; nor am I well pleased to make this… …   The Collaborative International Dictionary of English

  • Induction coil — Induction In*duc tion, n. [L. inductio: cf. F. induction. See {Induct}.] [1913 Webster] 1. The act or process of inducting or bringing in; introduction; entrance; beginning; commencement. [1913 Webster] I know not you; nor am I well pleased to… …   The Collaborative International Dictionary of English

  • Induction pipe — Induction In*duc tion, n. [L. inductio: cf. F. induction. See {Induct}.] [1913 Webster] 1. The act or process of inducting or bringing in; introduction; entrance; beginning; commencement. [1913 Webster] I know not you; nor am I well pleased to… …   The Collaborative International Dictionary of English

  • Induction port — Induction In*duc tion, n. [L. inductio: cf. F. induction. See {Induct}.] [1913 Webster] 1. The act or process of inducting or bringing in; introduction; entrance; beginning; commencement. [1913 Webster] I know not you; nor am I well pleased to… …   The Collaborative International Dictionary of English

  • Induction valve — Induction In*duc tion, n. [L. inductio: cf. F. induction. See {Induct}.] [1913 Webster] 1. The act or process of inducting or bringing in; introduction; entrance; beginning; commencement. [1913 Webster] I know not you; nor am I well pleased to… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”