Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [data-flow-analysis]

The tag has no usage guidance.

0
votes
0answers
25 views

Sufficient conditions for an analysis using a monotone framework to converge

We define a monotone framework as follows: $\begin{align*} in(\ell) &=\begin{cases} \mathrm{Initial} & \text{when $\ell\in$ Entry Labels}\\\\ \bigoplus \{out(\ell') \mid (\ell',\ell) \in \...
1
vote
0answers
28 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
2
votes
2answers
31 views

When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis

I've been exploring the differences between Context Sensitive Analysis (CSA) and Context Insensitive Analysis (CIA), members of ...
0
votes
1answer
62 views

How to Compute the Fixed Point on a DataFlow Lattice

Wondering the general overview of how to compute the fixed point on a program's dataflow lattice. A fixed point of a function $f(x)$ is one where the output of the function equals the input, so: $$f(...
0
votes
1answer
92 views

How to Construct a Lattice from Program Statements

In order to optimize a program, I am trying to figure out how the idea of a lattice applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a ...
1
vote
1answer
484 views

Why use a CFG instead of a DFG

I just realized a Control-Flow Graph (CFG) is composed of basic blocks, which is a set of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG,...
0
votes
0answers
229 views

Calculation of Gen and Kill set for data flow analys

I'm currently preparing for an exam in compiler construction. The course is mainly about optimization in the backend of the compiler. For the optimization we have to do data flow analysis by hand. In ...
2
votes
1answer
170 views

Why is it better to do the data flow analysis in the basic blocks

I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal. Sadly, quoting the exact source, would be slightly hard as it is not in ...
0
votes
1answer
28 views

Saving information from reaching definition

I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said ...
2
votes
0answers
133 views

Novel escape analysis algorithm for Java

Today I read a very interesting article about escape analysis in Java called Escape Analysis for Object Oriented Languages: Application to Java I think I have some grasp on how escape analysis works ...
2
votes
2answers
29 views

Inferring used fields in return type

A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example: ...
2
votes
1answer
37 views

Cut costly functions in inter-procedural abstract interpretation

I am performing some inter-procedural abstract interpretation to capture certain program properties. Following the standard way, what I am doing is to maintain a work list of to-be-analyzed functions, ...
1
vote
1answer
235 views

What makes data flow analysis higher level than control flow analysis?

I feel understanding why data flow is higher level than control flow is key to writing good code (and convincing others during code reviews). I find this repeatedly when arguing why my functional ...
6
votes
1answer
132 views

Memory needed for computational graph

Suppose we have a set of equations like this p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f() It can be represented by computational ...
2
votes
1answer
70 views

Data-flow analysis problem adjust to Ullman-Aho's framework?

I am reading the classical book "Compilers. Principles, techniques and tools" by Aho et alii. On chapter 9.3 they talk about a general framework to solve data-flow analysis problems that use a ...
7
votes
1answer
335 views

When is it useful to split critical edges?

Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and ...
1
vote
1answer
52 views

Data flow equations to determine value dependencies

I need to define the data-flow analysis equations to determine the value dependencies of an statement. For example: a = 9 b = a + 7 c = b * 2 the value of <...
3
votes
3answers
529 views

Formal notion of a call graph for Turing machines

To most computer programs one can assign a "call graph". Is there a formal notion of call graphs of Turing machines? Motivation is, that one could intuitively call a decidable language $L$ "...
1
vote
1answer
66 views

If Data-Flow Analysis is able to approximate, what does that mean?

I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, ...
3
votes
1answer
1k views

Backward vs Forward Data-flow Analysis

I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one ...
6
votes
1answer
492 views

Backward data-flow: post-order or RPO on reverse CFG?

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which ...
5
votes
1answer
1k views

Difference between “data dependence graph”, “data dependency graph”, and “data flow graph”

Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not. To make things even more complicated, a "...
1
vote
1answer
2k views

What are GEN and KILL statements in dataflow analysis?

In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?