Essential complexity: Difference between revisions

Revision as of 22:08, 7 September 2019

Revision as of 16:08, 17 December 2019

Line 34:

</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>

==See also==