{
  "id": "enwiki-001374353515",
  "slug": "strength-reduction",
  "title": "Strength reduction",
  "qid": "",
  "lead": "In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts strong multiplications inside a loop into weaker additions &ndash; something that frequently occurs in array addressing. Examples of strength reduction include replacing a multiplication within a loop with an addition and replacing exponentiation within a loop with a multiplication.",
  "body": "In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts strong multiplications inside a loop into weaker additions &ndash; something that frequently occurs in array addressing. Examples of strength reduction include replacing a multiplication within a loop with an addition and replacing exponentiation within a loop with a multiplication. c = 7; for (i = 0; i can be replaced with successive weaker additions c = 7; k = 0; for (i = 0; i for (i = 0; i ===Intermediate code=== The compiler will view this code as 0010 ; for (i = 0, i This expresses 2-dimensional array A as a 1-dimensional array of n*n size, so that whenever the high-level code expresses A[x, y] it will internally be A[(x*n)+y] for any given valid indices x and y. 0010 ; for (i = 0, i There are more optimizations to do. Register r3 is the main variable in the innermost loop (0140-0260); it gets incremented by 1 each time through the loop. Register r8 (which is invariant in the innermost loop) is added to r3. Instead of using r3, the compiler can eliminate r3 and use r9. The loop, instead of being controlled by r3 = 0 to n-1, can be controlled by r9=r8+0 to r8+n-1. That adds four instructions and kills four instructions, but there's one fewer instruction inside the loop. 0110 ; r3 = #0 killed ; j = 0 0115 r9 = r8 ; new assignment 0117 r20 = r8 + r2 ; new limit 0120 G0002: 0140 ; cmp r3, r2 killed ; j Now r9 is the loop variable, but it interacts with the multiply by 8. Here we get to do some strength reduction. The multiply by 8 can be reduced to some successive additions of 8. Now there are no multiplications inside the loop. 0115 r9 = r8 ; new assignment 0117 r20 = r8 + r2 ; new limit 0118 r10 = r8 * #8 ; initial value of r10 0120 G0002: 0145 cmp r9, r20 ; r8 + j Registers r9 and r10 (= 8*r9) aren't both needed; r9 can be eliminated in the loop. The loop is now 5 instructions. 0115 ; r9 = r8 killed 0117 r20 = r8 + r2 ; limit 0118 r10 = r8 * #8 ; initial value of r10 0119 r22 = r20 * #8 ; new limit 0120 G0002: 0145 ; cmp r9, r20 killed ; r8 + j 0010 ; for (i = 0, i There are now four multiplications within the outer loop that increments r1. Register r8 = r1*r2 at 0190 can be strength reduced by setting it before entering the loop (0055) and incrementing it by r2 at the bottom of the loop (0385). The value r8*8 (at 0118) can be strength reduced by initializing it (0056) and adding 8*r2 to it when r8 gets incremented (0386). Register r20 is being incremented by the invariant/constant r2 each time through the loop at 0117. After being incremented, it is multiplied by 8 to create r22 at 0119. That multiplication can be strength reduced by adding 8*r2 each time through the loop. 0010 ; for (i = 0, i ===The last multiply=== That leaves the two loops with only one multiplication operation (at 0330) within the outer loop and no multiplications within the inner loop. 0010 ; for (i = 0, i At line 0320, r14 is the sum of r8 and r1, and r8 and r1 are being incremented in the loop. Register r8 is being bumped by r2 (=n) and r1 is being bumped by 1. Consequently, r14 is being bumped by n+1 each time through the loop. The last loop multiply at 0330 can be strength reduced by adding (r2+1)*8 each time through the loop. 0010 ; for (i = 0, i There's still more to go. Constant folding will recognize that r1=0 in the preamble, so several instructions will clean up. Register r8 isn't used in the loop, so it can disappear. Furthermore, r1 is only being used to control the loop, so r1 can be replaced by a different induction variable such as r40. Where i went 0 0010 ; for (i = 0, i f x = ... (3 ** x) ... (f (x + 1)) ... becomes f x = f' x 1 where f' x z = ... z ... (f' (x + 1) (3 * z)) ... Here modified recursive function takes a second parameter z = 3 ** x, allowing the expensive computation (3 ** x) to be replaced by the cheaper (3 * z). ==See also== Fast inverse square root Hacker's Delight Partial evaluation ==Notes== ==References==",
  "categories": [
    "23118434",
    "23603337",
    "24927790"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374353515",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789128301.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001374353515",
    "type": "webpage",
    "title": "Strength reduction",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/strength-reduction",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374353515",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374353515",
    "note": "Immutable snapshot enwiki-001374353515"
  }
}