Essential complexity: Difference between revisions

Revision as of 16:08, 17 December 2019

Revision as of 17:44, 11 May 2020

Line 13:

For example, the following C program fragment has an essential complexity of 1, because the inner '''if''' statement and the '''for''' can be reduced, i.e. it is a structured program.

<sourcesyntaxhighlight lang="C">

for (i = 0; i < 3; i++) {

if (a[i] == 0) b[i] += 2;

}

</syntaxhighlight>

</source>

The following C program fragment has an essential complexity of four; its CFG is irreducible. The program finds the first row of z which is all zero and puts that index in i; if there is none, it puts -1 in i.

<sourcesyntaxhighlight lang="C">

for (i = 0; i < m; i++) {

for (j = 0; j < n; j++) {

Line 32:

i = -1;

found:

</syntaxhighlight>

</source>

The idea of CFG reducibility by successive collapses of sub-graphs (ultimately to a single node for well-behaved CFGs) is also used in modern compiler optimization. However the notion from structured programming of single-entry and single-exit control structure is replaced with that of [[natural loop]], which is defined as a "single-entry, multiple-exit loop, with only a single branch back to the entry from within it". The areas of the CFG that cannot be reduced to natural loops are called ''improper regions''; these regions end up having a fairly simple definition: multiple-entry, strongly connected components of the CFG. The simplest improper region is thus a loop with two entry points. Multiple exits do not cause analysis problems in modern compilers. Improper regions (multiple-entries into loops) do cause additional difficulties in optimizing code.<ref name="Muchnick1997">{{cite book|author=Steven S. Muchnick|title=Advanced Compiler Design Implementation|year=1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2|pages=[https://archive.org/details/advancedcompiler00much/page/196 196–197 and 215]|url-access=registration|url=https://archive.org/details/advancedcompiler00much/page/196}}</ref>