Loop fusion

In computer science, loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one. It is possible when two loops iterate over the same range and do not reference each other's data.

Loop fusion does not always improve run-time speed. On some architectures, two loops may actually perform better than one loop because, for example, there is increased data locality within each loop. In these cases, a single loop may be transformed into two, which is called loop fission.

Example in C

  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
    a[i] = 1;                     
  for (i = 0; i < 100; i++)
    b[i] = 2;

is equivalent to:

  int i, a[100], b[100];
  for (i = 0; i < 100; i++)
  {
    a[i] = 1; 
    b[i] = 2;
  }

Compiler optimizations

Basic block	Peephole optimization

Loop optimization	Induction variable Strength reduction Loop fusion Loop inversion Loop interchange Loop-invariant code motion Loop nest optimization Loop unrolling Loop splitting Loop unswitching Software pipelining Automatic parallelization

Data-flow analysis	Common subexpression elimination Constant folding Induction variable recognition and elimination Dead store elimination Use-define chain Live variable analysis Available expression

SSA-based	Global value numbering Sparse conditional constant propagation

Code generation	Register allocation Instruction selection Instruction scheduling Rematerialization

Functional	Removing recursion Deforestation

Global	Interprocedural optimization

Other	Bounds-checking elimination Dead code elimination Inline expansion Jump threading

Static analysis	Alias analysis Pointer analysis Shape analysis Escape analysis Array access analysis Dependence analysis Control flow analysis Data flow analysis

This article is issued from Wikipedia - version of the Wednesday, January 20, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Loop fusion

Example in C

See also