Normalized loop: Difference between revisions

Revision as of 21:09, 4 December 2009

Latest revision as of 21:31, 8 January 2024

(19 intermediate revisions by 17 users not shown)

Line 1:

{{multiple issues|

In [[computer science]], a normalized loop (sometimes called well-behaved loop), is a loop which the loop variable starts at 0 (or any constant) and get incremented by one at every iteration until the exit condition is met. Normalized loops are very important for [[compiler theory]], [[loop dependence analysis]] as they simplify the [[data dependence]] analysis.

{{more citations needed|date=January 2018}}

{{original research|date=January 2018}}

}}

In [[computer science]], a '''normalized loop''' (sometimes called well-behaved loop), is a loop in which the loop variable starts at 0 (or any constant) and getgets incremented by one at every iteration until the exit condition is met. Normalized loops are very important for [[compiler theory]], [[loop dependence analysis]] as they simplify the [[data dependence]] analysis.{{citation needed|date=January 2018}}<ref>{{Cite web |title=Normalized hysteresis loops |url=https://www.researchgate.net/figure/Normalized-hysteresis-loops-a-hysteresis-loop-for-Py-SiNWs-deposited-at-A-18-V-H_fig5_282598676}}</ref>

==Well-behaved loops==

Line 5 ⟶ 10:

A well behaved loop is normally of the form:

<sourcesyntaxhighlight lang=c>

for ( i = 0; i < MAX; i++ )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Because the increment is unitary and constant, it's very easy to see that, if both ''a'' and ''b'' are bigger than MAX, this loop will never access memory outside the allocated range.

Line 18 ⟶ 23:

A simple example, where it doesn't start at the beginning and increments by more than one:

<sourcesyntaxhighlight lang=c>

// Example 1

for ( i = 7; i < MAX; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

A more complicated example, with an additional exit condition:

<sourcesyntaxhighlight lang=c>

// Example 2

for ( i = 7; i < MAX || i > MIN; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Loops can also have non-predictable behaviourbehavior during compilation time, where tethe exit condition depends on the contents of the data being modified:

<sourcesyntaxhighlight lang=c>

// Example 3

for ( i = 7; i < MAX && a[i]; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Or even dynamic calculations by means of function calls:

<sourcesyntaxhighlight lang=c>

// Example 4

for ( i = start(); i < max(); i+=increment() )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Reverse loops are also very simple, and can be easily normalized:

<sourcesyntaxhighlight lang=c>

// Example 5

for ( i = MAX; i > 0; i-- )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

===Converting to a normalized loop===

If the non-normalized doesn't have dynamic behaviour, it's normally very easy to transform it to a normalized one. For instance, the fistfirst example (Example 1) above can easily be converted to:

<sourcesyntaxhighlight lang=c>

// Example 1 -> normalized

for ( i = 0; i < (MAX/3-7)/3; i++ )

a[i*3+7] = b[i*3+7] + 5;

</syntaxhighlight>

</source>

While the third example can be partially normalized to allow some parallelization, but still lack the ability to know the loop span (how many iterations there will be), making it harder to vectorize by using multi-media hardware.

Starting at 7 is not so much of a problem, as long as the increment is regular, preferably one. When multiple statements inside the loop use the index, some private temporary variables may be created to cope with the different iteration paces.

The reverse loop (Example 5) is also easy to normalize:

<syntaxhighlight lang=c>

// Example 5 -> normalized

for ( i = 0; i < MAX; i++ )

a[MAX-i] = b[MAX-i] + 5;

</syntaxhighlight>

Note that the access is still backwards. In this case, it makes no sense to leave it backwards (as there is no [[data dependence]]), but where dependences exist, caution must be taken to revert the access as well, as it could disrupt the order of assignments.

===Impossible conversions===

The lastExample example4 above makes it impossible to predict anything from that loop. Unless the functions themselves are trivial (constant), there is no way to know where the loop will start, stop and how much it'll increment each iteration. Those loops are not only hard to parallelize, but they also perform horribly.

Each iteration, the loop will evaluate two functions ('''max()''' and '''increment()'''). Even if the functions are inlined, the condition becomes too complex to be worth optimizing. The programmer should take extra care not to create those loops unless strictly necessary (if ever).

Another danger of such loops appear if the evaluation depends on the data being modified. For instance, a normal error when using iterators is to remove items from a list while modifying it, or relying on sizes (for exit condition) that are not true any more.

== See also ==

* [[Dependence analysis]]

* [[Loop transformation]]

* [[Loop splitting]]

* [[Loop fusion]]

* [[Loop interchange]]

* [[Loop skewing]]

* [[Automatic parallelization]]

* [[Automatic vectorization]]

* [[Loop dependence analysis]]

== References ==

{{Reflist}}

[[Category:Compiler construction]]