Lably
Skip to content

Strength reduction

Compiler optimization

  • 38 min read
  • 4 chapters

Related on Lably

Through Compiler, Exponentiation and Identity matrix

Lab · Class 8Exponents & PowersLab · Class 8Exponents & PowersLabExponents and PowersLabExponents and Powers

Examples of strength reduction include replacing a multiplication within a loop with an addition and replacing exponentiation within a loop with a multiplication.

Code analysis

Most of a program's execution time is typically spent in a small section of code (called a hot spot), and that code is often inside a loop that is executed over and over.

A compiler uses methods to identify loops and recognize the characteristics of register values within those loops. For strength reduction, the compiler is interested in:

  • Loop invariants: the values which do not change within the body of a loop.
  • Induction variables: the values which are being iterated each time through the loop.

Loop invariants are essentially constants within a loop, but their value may change outside of the loop. Induction variables are changing by known amounts. The terms are relative to a particular loop. When loops are nested, an induction variable in the outer loop can be a loop invariant in the inner loop.

Strength reduction looks for expressions involving a loop invariant and an induction variable. Some of those expressions can be simplified. For example, the multiplication of loop invariant c and induction variable i

<span id="mwHw"></span><span class="n" id="mwIA">c</span><span class="w" id="mwIQ"> </span><span class="o" id="mwIg">=</span><span class="w" id="mwIw"> </span><span class="mi" id="mwJA">7</span><span class="p" id="mwJQ">;</span> <span class="k" id="mwJg">for</span><span class="w" id="mwJw"> </span><span class="p" id="mwKA">(</span><span class="n" id="mwKQ">i</span><span class="w" id="mwKg"> </span><span class="o" id="mwKw">=</span><span class="w" id="mwLA"> </span><span class="mi" id="mwLQ">0</span><span class="p" id="mwLg">;</span><span class="w" id="mwLw"> </span><span class="n" id="mwMA">i</span><span class="w" id="mwMQ"> </span><span class="o" id="mwMg"><</span><span class="w" id="mwMw"> </span><span class="n" id="mwNA">N</span><span class="p" id="mwNQ">;</span><span class="w" id="mwNg"> </span><span class="n" id="mwNw">i</span><span class="o" id="mwOA">++</span><span class="p" id="mwOQ">)</span> <span class="p" id="mwOg">{</span> <span class="w" id="mwOw"> </span><span class="n" id="mwPA">y</span><span class="p" id="mwPQ">[</span><span class="n" id="mwPg">i</span><span class="p" id="mwPw">]</span><span class="w" id="mwQA"> </span><span class="o" id="mwQQ">=</span><span class="w" id="mwQg"> </span><span class="n" id="mwQw">c</span><span class="w" id="mwRA"> </span><span class="o" id="mwRQ">*</span><span class="w" id="mwRg"> </span><span class="n" id="mwRw">i</span><span class="p" id="mwSA">;</span> <span class="p" id="mwSQ">}</span>

can be replaced with successive weaker additions

<span id="mwTQ"></span><span class="n" id="mwTg">c</span><span class="w" id="mwTw"> </span><span class="o" id="mwUA">=</span><span class="w" id="mwUQ"> </span><span class="mi" id="mwUg">7</span><span class="p" id="mwUw">;</span> <span class="n" id="mwVA">k</span><span class="w" id="mwVQ"> </span><span class="o" id="mwVg">=</span><span class="w" id="mwVw"> </span><span class="mi" id="mwWA">0</span><span class="p" id="mwWQ">;</span> <span class="k" id="mwWg">for</span><span class="w" id="mwWw"> </span><span class="p" id="mwXA">(</span><span class="n" id="mwXQ">i</span><span class="w" id="mwXg"> </span><span class="o" id="mwXw">=</span><span class="w" id="mwYA"> </span><span class="mi" id="mwYQ">0</span><span class="p" id="mwYg">;</span><span class="w" id="mwYw"> </span><span class="n" id="mwZA">i</span><span class="w" id="mwZQ"> </span><span class="o" id="mwZg"><</span><span class="w" id="mwZw"> </span><span class="n" id="mwaA">N</span><span class="p" id="mwaQ">;</span><span class="w" id="mwag"> </span><span class="n" id="mwaw">i</span><span class="o" id="mwbA">++</span><span class="p" id="mwbQ">)</span> <span class="p" id="mwbg">{</span> <span class="w" id="mwbw"> </span><span class="n" id="mwcA">y</span><span class="p" id="mwcQ">[</span><span class="n" id="mwcg">i</span><span class="p" id="mwcw">]</span><span class="w" id="mwdA"> </span><span class="o" id="mwdQ">=</span><span class="w" id="mwdg"> </span><span class="n" id="mwdw">k</span><span class="p" id="mweA">;</span> <span class="w" id="mweQ"> </span><span class="n" id="mweg">k</span><span class="w" id="mwew"> </span><span class="o" id="mwfA">=</span><span class="w" id="mwfQ"> </span><span class="n" id="mwfg">k</span><span class="w" id="mwfw"> </span><span class="o" id="mwgA">+</span><span class="w" id="mwgQ"> </span><span class="n" id="mwgg">c</span><span class="p" id="mwgw">;</span> <span class="p" id="mwhA">}</span>

Sign in to keep reading

3 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard