Control-flow analysis: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 12:26, 24 June 2024

In computer science, control-flow analysis (CFA) is a static-code-analysis technique for determining the control flow of a program. The control flow is expressed as a control-flow graph (CFG). For both functional programming languages and object-oriented programming languages, the term CFA, and elaborations such as k-CFA, refer to specific algorithms that compute control flow.^{[dubious – discuss]}

For many imperative programming languages, the control flow of a program is explicit in a program's source code.^{[dubious – discuss]} As a result, interprocedural control-flow analysis implicitly usually refers to a static analysis technique for determining the receivers of function or method calls in computer programs written in a higher-order programming language.^{[dubious – discuss]} For example, in a programming language with higher-order functions like Scheme, the target of a function call may not be explicit: in the isolated expression

(lambda (f) (f x))

it is unclear to which procedure f may refer. A control-flow analysis must consider where this expression could be invoked and what argument it may receive to determine the possible targets.

Techniques such as abstract interpretation, constraint solving, and type systems may be used for control-flow analysis.^[1]^{[page needed]}

References[edit]

^ Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.

External links[edit]

[1] Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.

[1]

@@ Line 1: / Line 1: @@
+{{Short description|Compiler technique}}
-'''Control flow analysis''' is a [[static code analysis]] technique for determining the [[control flow]] of a program. The control flow is expressed as a [[control flow graph]] (CFG).
+{{Cleanup-rewrite|date=July 2014}}
+In [[computer science]], '''control-flow analysis''' ('''CFA''') is a [[static code analysis|static-code-analysis]] technique for determining the [[control flow]] of a program. The control flow is expressed as a [[control-flow graph]] (CFG). For both [[functional programming language]]s and [[object-oriented programming language]]s, the term CFA, and elaborations such as ''k''-CFA, refer to specific algorithms that compute control flow.{{dubious|date=July 2014}}
-For many languages, the control flow of a program is explicit in a program's source code.   As a result, control-flow analysis implicitly usually refers to a [[static analysis]] technique for determining the receiver(s) of function or method calls in computer programs written in a [[higher-order programming language]].  For both [[functional programming language]]s and [[object-oriented programming language]]s, the term [[CFA]] refers to an algorithm that computes control flow.
+For many [[imperative programming language]]s, the control flow of a program is explicit in a program's source code.{{dubious|date=July 2014}}  As a result, [[interprocedural analysis|interprocedural]] control-flow analysis implicitly usually refers to a [[static analysis]] technique for determining the receivers of function or method calls in computer programs written in a [[higher-order programming language]].{{dubious|date=July 2014}} For example, in a programming language with [[higher-order function]]s like [[Scheme (programming language)|Scheme]], the target of a function call may not be explicit: in the isolated expression
+<syntaxhighlight lang="scheme">
-The term '''control flow analysis''' was introduced independently by Neil D. Jones<ref>{{citation
+(lambda (f) (f x))
- | author = Neil D. Jones
+</syntaxhighlight>
- | title = Flow analysis of lambda expressions
- | journal = Automata, Languages and Programming
- | year = 1981
- | doi = 10.1007/3-540-10843-2_10
- | pages = 114–128
-}}</ref> and Olin Shivers<ref>{{citation
- | last = Shivers
- | first = Olin
- | title = Control-flow analysis in Scheme
- | pages = 164–174
- | note = Reprinted in \emph{20 Years of the ACM SIGPLAN Conference on
-          Programming Language Design and Implementation (1979--1999):
-          A Selection
- | journal = Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI)
- | series = SIGPLAN Notices, Vol.23, No.7
- | year = 1988
- | doi = 10.1145/53990.54007
-}}</ref>.
+it is unclear to which procedure <code>f</code> may refer.  A control-flow analysis must consider where this expression could be invoked and what argument it may receive to determine the possible targets.
-In a programming language like Scheme, the target of a function call may not be explicit.  For example in the isolated expression:
+Techniques such as [[abstract interpretation]], [[constraint solving]], and [[type system]]s may be used for control-flow analysis.<ref>{{cite book |author-first1=Flemming |author-last1=Nielson |author-first2=Hanne Riis |author-last2=Nielson |author-first3=Chris |author-last3=Hankin |title=Principles of Program Analysis |publisher=[[Springer Science+Business Media]] |date=2005}}</ref>{{page needed|date=July 2014}}
- (lambda (f) (f x))
+==See also==
-it is unclear to which procedure <code>f</code> may refer.  To determine the possible targets, a control-flow analysis must consider where this expression could be invoked, and what argument it may receive.
+* [[Control-flow diagram]] (CFD)
+* [[Data-flow analysis]]
+* [[Cartesian product algorithm]]
-[[Abstract interpretation]], [[constraint solving]] and [[type system]]s may be used to compute control-flow analysis.
+* [[Pointer analysis]]
 ==References==
 {{reflist}}
+==External links==
+{{Commonscat|Control-flow analysis}}
+*[https://web.archive.org/web/20140728203154/http://pages.cs.wisc.edu/~cs701-1/NOTES/3.CONTROL-FLOW-ANALYSIS.html for textbook intraprocedural CFA in imperative languages]
+*[http://janmidtgaard.dk/papers/Midtgaard-CSur-final.pdf CFA in functional programs (survey)]
+*[http://cgi.di.uoa.gr/~smaragd/kcfa-pldi10.pdf for the relationship between CFA analysis in functional languages and points-to analysis in imperative/OOP languages]
+{{Compiler optimizations}}
 [[Category:Control-flow analysis| ]]

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Use-define chain
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Latest revision as of 12:26, 24 June 2024

See also[edit]

References[edit]

External links[edit]