Loop inversion

In computer science, loop inversion is a compiler optimization and loop transformation in which a while loop is replaced by an if block containing a do..while loop. When used correctly, it may improve performance due to instruction pipelining.

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);
  }

Despite the seemingly greater complexity of the second example, it may actually run faster on modern CPUs because they use an instruction pipeline. By nature, any jump in the code causes a pipeline stall, which is a detriment to performance.

Additionally, loop inversion allows safe loop-invariant code motion.

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   <<at L2>>

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   <<at L2>>

As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.

gollark: Perhaps they're semirandom. Perhaps I devise bespoke bluffs by myself and then share them. Perhaps my bluffs are optimized automatically via testing against high-fidelity computer simulations of all other participants. Perhaps I don't make bluffs but merely disseminate cognitohazards causing perception of bluffs. Perhaps my every word and bluff is meticulously generated to produce minimum guessing of me. Perhaps I never bluff and every word I say is accurate.
gollark: I generate my bluffs via RNG now to avoid the terribleness of human random number generation (heavpoot has data on this), unless I don't and am trying to trick you into not making inferences from them.
gollark: Unless I didn't but am *not* trying to fool you all.
gollark: Unless I didn't and am trying to fool you all, of course.
gollark: I attempted to completely leave any chat here in the guessing phase out of my decision-making.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.