Constant folding: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Chris day
mNo edit summary
 
(5 intermediate revisions by 5 users not shown)
Line 1: Line 1:
In [[computer science]], '''constant folding''' is a [[translation system|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.
{{subpages}}
 
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|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 effect|side effects]], computes (using the mathematics of the target machine) the result, and replaces the entire expression with instructions to load the result.
Constant folding is most easily implemented on a [[directed acyclic graph|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 effect|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 ==
== 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 <math>N\times M</math> array of integers, row major, with <math>S_{int}</math> bytes per integer.  Given the array's base address <math>B</math>, to select the element from the <math>i</math>th row and the <math>j</math>th column, the compiler generates instructions to calculate the address as follows:
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 <math>N\times M</math> array of integers, row major, with <math>S_{int}</math> bytes per integer.  Given the array's base address <math>B</math>, to select the element from the <math>i</math>th row and the <math>j</math>th column, the compiler generates instructions to calculate the address as follows:


<math>Address = B + i\times S_{int} + j\times N\times S_{int}</math>
: <math>Address = B + i\times S_{int} + j\times N\times S_{int}</math>


Suppose that, in the execution of a program, one or more of the row index <math>i</math> or the column index <math>j</math> was constant, then the expression can be simplified at compile time.  For instance, if we choose a constant row <math>i_K</math>,
Suppose that, in the execution of a program, one or more of the row index <math>i</math> or the column index <math>j</math> was constant, then the expression can be simplified at compile time.  For instance, if we choose a constant row <math>i_K</math>,
Line 18: Line 20:
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.
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 ==
== Constant folding with associativity ==
 
Suppose that a computer program had an expression of the form <math>A \times X \times B</math>, where A, B are constants and X is a variable.  During [[parse|parsing]], the compiler will apply rules of [[associativity]], and depeding on the language interpret this expression as either <math>(A \times X) \times B</math> or <math>A\times (X \times B)</math>.  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, given the associativity of the operator.


== Common Pitfalls ==
Suppose that a computer program had an expression of the form <math>A \times X \times B</math>, where ''A'', ''B'' are constants and ''X'' is a variable.  During [[parse|parsing]], the compiler will apply rules of [[associativity]], and depending on the language interpret this expression as either <math>(A \times X) \times B</math> or <math>A\times (X \times B)</math>.  In either case, a naive implementation of constant folding cannot simplify this since neither of the multiplications involve two constant operands.


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.
A less naive implementation of constant folding will be able to fold this expression by rewriting it as <math>(A \times B) \times X</math>. When ''A'', ''B'' and ''X'' are [[floating-point number]]s, this introduces a very small error because <math>(A \times X) \times B</math> and <math>(A \times B) \times X</math> are generally not equal in floating-point arithmetics.


{{stub}}
== Common pitfalls ==


[[Category:Computers Workgroup]]
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.[[Category:Suggestion Bot Tag]]
[[Category:Compiler Optimizations]]
[[Category:CZ_Live]]

Latest revision as of 12:01, 1 August 2024

This article is developed but not approved.
Main Article
Discussion
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.