Constant folding

From Citizendium
Revision as of 12:34, 26 September 2007 by Jitse Niesen (Talk | contribs) (Constant folding with associativity: rewrite because this optimization uses associativity and commutativity; mention issue with floating-point arithmetic)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
This article is developed but not approved.
Main Article
Definition [?]
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
This editable, developed Main Article is subject to a disclaimer.

In computer science, constant folding is a compiler optimization in which arithmetic instructions that always produce the same result are replaced by their result. This optimization can only be performed when the instructions in question can be shown at compile time to produce the same result. In some cases, constant folding is quite similar to reduction in strength optimizations.

Constant folding is most easily implemented on a directed acyclic graph (DAG) intermediate representation, though it can be performed in almost any stage of compilation, even in a peephole optimizer. Basically, the compiler seeks any operation that has constant operands and without side effects, computes (using the mathematics of the target machine) the result, and replaces the entire expression with instructions to load the result.

Why constant folding is effective

In many circumstances, the compiler may emit instructions which can be simplified by constant folding. One common source is array index expressions. For instance, suppose we had a array of integers, row major, with bytes per integer. Given the array's base address , to select the element from the th row and the th column, the compiler generates instructions to calculate the address as follows:

Suppose that, in the execution of a program, one or more of the row index or the column index was constant, then the expression can be simplified at compile time. For instance, if we choose a constant row ,

  1. for
  2. for
  3. for

Thus, replacing three multiplication operations and two addition operations with a simple multiplication and a single addition. Additionally, since data types generally occupy a power of two size, reduction in strength optimizations will generally further enhance this code.

Constant folding with associativity

Suppose that a computer program had an expression of the form , where A, B are constants and X is a variable. During parsing, the compiler will apply rules of associativity, and depending on the language interpret this expression as either or . In either case, a naive implementation of constant folding cannot simplify this since neither of the multiplications involve two constant operands.

A less naive implementation of constant folding will be able to fold this expression by rewriting it as . When A, B and X are floating-point numbers, this introduces a very small error because and are generally not equal in floating-point arithmetics.

Common pitfalls

In cross compilers, the arithmetic is often performed to different precisions on the compiling machine and the target machine. In this case, it is critical that the compiler perform the arithmetic in the precision of the target machine.