Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
, a loop transformation, which replaces a while loop by an if block containing a do..while loop.
Example in C
int i, a[100];
i = 0;
while (i < 100) {
a[i] = 0;
i++;
}
is equivalent to:
int i, a[100];
i = 0;
if (i < 100) {
do {
a[i] = 0;
i++;
} while (i < 100);
}
At a first glance, this seems like a bad idea: there's more code so it probably takes longer to execute. However, most modern CPUs
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
An instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
for executing instructions. By nature, any jump in the code causes a pipeline stall. Let's watch what happens in Assembly-like Three address code
Three address code
In computer science, three-address code is a form of representing intermediate code used by compilers to aid in the implementation of code-improving transformations...
version of the above code:
Example in Three-address code
i := 0
L1: if i >= 100 goto L2
a[i] := 0
i := i + 1
goto L1
L2:
If i had been initialized at 100, the instructions executed at runtime would have been:
1: if i >= 100
2: goto L2
Let us assume that i had been initialized to some value less than 100. Now let us look at the instructions executed at the moment after i has been incremented to 99 in the loop:
1: goto L1
2: if i < 100
3: a[i] := 0
4: i := i + 1
5: goto L1
6: if i >= 100
7: goto L2
8: <>
Now, let's look at the optimized version:
i := 0
if i >= 100 goto L2
L1: a[i] := 0
i := i + 1
if i < 100 goto L1
L2:
Again, let's look at the instructions executed if i is initialized to 100:
1: if i >= 100
2: goto L2
We didn't waste any cycles compared to the original version. Now consider the case where i has been incremented to 99:
1: if i < 100
2: goto L1
3: a[i] := 0
4: i := i + 1
5: if i < 100
6: <>
As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.
In computer programming, loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program...
to be performed.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
