'''Essential complexity''' is also a numeric measure defined by McCabe in his highly- cited, 1976 paper better known for introducing [[cyclomatic complexity]]. McCabe, defined essential complexity as the cyclomatic complexity of the reduced [[control flow graph]] after iteratively replacing (reducing) all [[structured programming]] [[control structure]]s, i.e. those having a single entry point and a single exit point (for example if-then-else and while loops) with placeholder single statements.<ref name="mccabe76">{{cite journal| last=McCabe| date=December 1976| journal=IEEE Transactions on Software Engineering| pages=308–320| title=A Complexity Measure|format=}}</ref>{{rp|317}}<ref>http://www.mccabe.com/pdf/mccabe-nist235r.pdf</ref>{{rp|80}}<!-- note that the original paper has an error in the final formula for ev, but this is corrected the technical report-->
McCabe's reduction process is intended to simulate the conceptual replacement of control structures (and actual statements they contain) with subroutine calls, hence the requirement for the control structures to have a single entry and a single exit point.<ref name="mccabe76"/>{{rp|317}} (Nowadays a process like this would fall under the umbrella term of [[refactoring]].) All structured programs evidently have an essential complexity of 1 as defined by McCabe because they can all be iteratively reduced to a single call to a top-level subroutine.<ref name="mccabe76"/>{{rp|318}} As McCabe explains in his paper, his essential complexity metric was designed to provide a measure of how far off this ideal (of being completely structured) a given program was.<ref name="mccabe76"/>{{rp|317}} Thus higher essential complexity numbers, which can only be obtained for non-structured programs, indicate that they are further away from the structured programming ideal.<ref name="mccabe76"/>{{rp|317}}
Line 47:
</source>
The notionidea of CFG reducibility introduced by McCabesuccessive collapses of sub-graphs (ultimately to a single node for definingwell-behaved essentialCFGs) complexityis findsalso applicationsused in modern compiler optimization. The areas of the CFG that cannot be reduced (to structured"nice" programs, technically called [[natural loop]]s (which have a rather involved definition that we elide in this article) are now called ''improper regions'';, and these regions end up having a relatively simple definition: multiple-entry strongly connected components of the CFG. (Multiple exits do not cause problems to modern compilers. Thus the simplest improper region is a loop with two entry points.) Improper regions cause additional difficulties in optimizing generated 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}}</ref>
