Control-flow analysis: Difference between revisions

Revision as of 20:21, 16 September 2013

Latest revision as of 22:15, 5 August 2024

(33 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Compiler technique}}

In [[computer science]], '''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). The term "control flow analysis" was introduced independently by [[Neil D. Jones]]<ref>{{citation

{{Cleanup-rewrite|date=July 2014}}

| author = Neil D. Jones

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). TheFor termboth "control[[functional flowprogramming analysis"language]]s was introduced independently byand [[Neilobject-oriented D.programming Joneslanguage]]<ref>s, the term CFA, and elaborations such as ''k''-CFA, refer to specific algorithms that compute control flow.{{citationdubious|date=July 2014}}

| 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

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

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 receiver(s)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 functionsfunction]]s like [[Scheme (programming language)|Scheme]], the target of a function call may not be explicit: in the isolated expression

<sourcesyntaxhighlight lang="scheme">

(lambda (f) (f x))

</syntaxhighlight>

</source>

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.

it is unclear to which procedure <code>f</code> may refer. To determine the possible targets, aA 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 system]]s may be used to compute control-flow analysis.<ref>Flemming Nielson, Hanne Riis Nielson & Chris Hankin (1999). ''Principles of Program Analysis''. Springer.</ref>

Techniques such as [[abstract interpretation]], [[constraint solving]], and [[type system]]s may be used to computefor control-flow analysis.<ref>{{cite book |author-first1=Flemming |author-last1=Nielson, |author-first2=Hanne Riis |author-last2=Nielson &|author2-link=Hanne Riis Nielson|author-first3=Chris |author-last3=Hankin (1999). ''|title=Principles of Program Analysis''. |publisher=[[Springer. Science+Business Media]] |date=2005}}</ref>{{page needed|date=July 2014}}

== See also ==

== See also ==

* [[Control-flow diagram]] (CFD)

* [[Data-flow analysis]]

* [[Cartesian product algorithm]]

* [[Pointer analysis]]

==References==

{{reflist}}

==External links==

{{Commonscat| title = Control-flow analysis in Scheme}}

*[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| ]]