Talk:Data-flow analysis

Partial Order and monotonicity

Partial Order, finity height and Monotonicity are probably not enough for dataflow Analysis. In our Course we learned that you need a complette lattice, Ascending Chain Condition and monotonicity for a dataflow-analysis. While finite height => Ascending Chain Condition, there still is not the complette lattice. According to this article you could do an analysis with a domain in which no element is in relation to any other element. e.g. Domain={red, car, banana}. Obviously english is not my first language, so please consider my input and change the article (if i'm correct) accordingly. -- 134.61.74.48 (talk) 12:37, 2 March 2013 (UTC)

not enyclopedic

This should probably be moved to wikibooks, as it is not an encyclopedic article. Thue | talk 15:07, 15 Jul 2004 (UTC)

Agreed that this is not encyclopedic, but disagree that it should be moved to wikibooks. If I knew anything about data-flow analysis, I would write it here, but I don't (which is why I am here). Suggested sub-topics:

• what it is
• why it is used
• history/background

the FolDoc entry might be a good place to start.

--Lenehey 22:36, July 28, 2005 (UTC)

Definition

There should be a definition of "dataflow analysis".

We can say something like : "Data flow analysis is a process for collecting run-time information about data in programs without actually executing them" --Cocothebo 10:36, 30 March 2006

Spelling

Technically, it's data-flow (with a hyphen) analysis. FAdmMatt 20:59, 3 May 2005

You seem very certain of this. Why is "control flow analysis" always spelled without the hyphen? Certainly, the Dragon book uses the hyphen, but I find that most papers on the subject do not (some use a space, some neither a space nor a hyphen). I'd really like to know the definitive answer. --Mike Van Emmerik 12:09, 14 February 2006 (UTC)

Reverse postorder is not the same as preorder!

It's really scary that this article has claimed since its creation in 2004 that reverse postorder is just another name for preorder. So much for the many-eyes philosophy. This is the worst kind of mistake an article can have, because once you get an idea like this into people's heads it tends to be very difficult to get it out. I fixed the problem, but I'm placing an erratum here in the hope of catching the eye of a few of the people who were misled by the article. -- BenRG 15:04, 2 September 2006 (UTC)

Hmm, actually on rereading that paragraph I'm not sure what it's talking about. What does "except when the successor is reached by a back edge" mean? Is it just talking about the fact that you don't revisit nodes you've already visited? Unless there are objections, I think I'll rewrite this paragraph to simply say that reverse postorder is the reverse of postorder. -- BenRG 15:15, 2 September 2006 (UTC)

It probably means that you can't order a flow graph with loops in it based on successor relations only. The back edge is defining a loop in the program. Mauritsmaartendejong 11:03, 16 July 2007 (UTC)

If you rewrite it, it would be nice to have an actual example flowgraph with the different orders written out, and evaluated in terms of number of basic block visits. Mauritsmaartendejong 11:03, 16 July 2007 (UTC)

Actually, as it stands now, this entire paragraph is complete nonsense. It really depends on the actual data flow analysis whether or not the order matters. I know quite a few analyses where order does not matter at all. So I don't know if this paragraph should even be in there. In any case it should be rephrased. Ericbodden 04:02, 11 May 2007 (UTC)

Could you name a few of those analyses where order does not matter ? I've been seeing quite a few wrong orderings leading to quadratic behaviour and compilations taking hours or even days to complete which were brought back to minutes by careful ordering. I would say that this makes the notion at least relevant. Perhaps we should qualify the statement with the cases where it does matter. My intuition says that whenever you propagate information from one basic block to another, you better try to order the blocks according to that propagation direction. In my view, this propagation is the essence of data flow analysis. Mauritsmaartendejong 11:03, 16 July 2007 (UTC)

Suggestion for new structure

I think data flow analysis is an important topic in compiler optimizations, and would like to get this article in good shape.

I would propose the following topics:

• Introduction
  • examples
  • applications, e.g. live variables in relation to dead code elimination
• intra block data flow
  • statements
  • direction of flow
• inter block data flow
  • basic blocks && control flow graph
  • in and out sets
  • gen and kill sets
  • join operation
  • data flow equations
  • fixed point algorithm.
    • conditions for termination.
    • work-list approach
    • work-list ordering
• structured program analysis
• bit vector representations
• more elaborate applications
  • abstract interpretation
  • value range analysis
• use of ssa
• history
• ...

Comments are welcome. Count me in as a contributor, but I'd hate to do this on my own.

Mauritsmaartendejong 12:18, 16 July 2007 (UTC)

Removed from "Sensitivities" section

I removed this:

These terms aren't specific to data-flow analysis. The following definitions should be moved somewhere else and fleshed out with more verbose examples. Wikipedia's inter-document structure for static analysis could use some rework.

As correct as this remark may be, it doesn't belong in the article itself. --Doradus (talk) 15:15, 28 January 2009 (UTC)

Definition of path-sensitive is wrong

A path-sensitive analysis is one that takes into account the path leading up to the node. Just propagating different information along different out edges doesn't make it really path-sensitive. Sparse conditional constant propagation isn't considered path-sensitive in my understanding. —Preceding unsigned comment added by 128.84.96.80 (talk) 18:26, 1 December 2009 (UTC)

Backward Analysis

Those examples are messed up IMHO. The in and out states are reversed. Can someone proofread them, please? — Preceding unsigned comment added by Descent89 (talk • contribs) 16:54, 20 January 2012 (UTC) I hopefully fixed them using http://en.wikipedia.org/w/index.php?title=Live_variable_analysis&action=edit . — Preceding unsigned comment added by Descent89 (talk • contribs) 17:01, 20 January 2012 (UTC)

Rewrite and clarify

I have to agree with the other comments - this article is like wading through treacle and could at best be described as a reference document. It certainly doesn't "tell" very much about Data-flow analysis. Does anybody feel like tackling a re-write or a clean-up? Introduction and examples vital. And wording should cover all ground but try to be simple enough to be read by fellow human beings who are not experts in the subject. (That is after all what encyclopedias are all about - the passing on of knowledge)

-Sam, UK — Preceding unsigned comment added by 2.97.170.153 (talk) 20:48, 10 March 2013 (UTC)

What does this sentence mean?

"The most common way of solving the data-flow equations is by using an iterative algorithm."

What kind of data does a solution represent here?