Essential complexity: Difference between revisions

Content deleted Content added
Line 47:
</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. TheHowever areasthe notion from structured programming of thesingle-entry CFGand thatsingle-exit cannotcontrol bestructure reducedis toreplaced "nice"with programs,that technically calledof [[natural loop]]s, (which haveis defined as a rather"single-entry, involvedmultiple-exit definitionloop, with only a single branch back to the entry from within it". The areas of the CFG that wecannot omitbe here),reduced to natural loops are called ''improper regions'', and; these regions end up having a relativelyfairly simple definition: multiple-entry, strongly connected components of the CFG. (Multiple exits do not cause problems to modern compilers. Thus theThe 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=196-197 and 215}}</ref>
 
==See also==