8
votes
Accepted
Formal notion of a call graph for Turing machines
Turing machines have no concept of "calling".
Tou can jump to another state and that can look quite a lot like a procedure call, especially if an author's description of the machine in English uses ...
- 82.1k
5
votes
When is it useful to split critical edges?
An easy google search shows in Muchnick, Advanced Compiler Design & Implementation, Section 13.3 Partial-Redundancy Elimination, pp 407-408:
A key point in the algorithm is that it can be much ...
- 8,262
4
votes
Accepted
Which language is used to construct a type system?
OCaml and Scala are popular choices for types systems, but they are by no means the only languages you can write a compiler, interpreter, typechecker, or type system in.
Type-checking involves ...
- 29.9k
4
votes
Formal notion of a call graph for Turing machines
For TMs, there is no such notion and there can not be. Compare plain TMs with assembler: there are rudimentary operations which together create some effect, but there is little to know syntactic ...
- 72.8k
4
votes
Memory needed for computational graph
Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled Inapproximability of treewidth, one-shot pebbling, and related layout problems (J. ...
- 278k
4
votes
Accepted
Why use a CFG instead of a DFG
A control-flow graph serves a different purpose than a data-flow graph. They aren't alternatives. A control-flow graph represents the flow of control: which instruction can follow another. A data-...
D.W.♦
- 164k
3
votes
Accepted
Why is it better to do the data flow analysis in the basic blocks
It isn't "better" in the sense that the analysis is more precise. It's just more compact and cheaper to compute.
There's no reason why you can't compute an old-school iterative bit-vector-based ...
- 23.1k
3
votes
Accepted
Data-flow analysis problem adjust to Ullman-Aho's framework?
Checking initialization: Yes, you can use this framework. You need only a single boolean for each variable. The lattice is $V\to \{\bot,\top\}$, i.e., $2^V$, where $V$ is the set of variables. The ...
D.W.♦
- 164k
3
votes
Accepted
Cut costly functions in inter-procedural abstract interpretation
Sure. "Cut off and return Top" is sound. It's valid. It seems like a reasonable thing to do.
I don't know if it has been studied or used before in the literature. I wouldn't be surprised if it ...
D.W.♦
- 164k
2
votes
Data flow equations to determine value dependencies
Well, it seems that this can be reduced to the Reaching Definition problem, who's equations are:
$REACH_{in}(S) = \bigcup_{p \in pred(S)} REACH_{out}(p)$
$REACH_{out}(S) = GEN(S) \cup (REACH_{in}(S)...
- 333
2
votes
Formal notion of a call graph for Turing machines
Quoth Hopcroft and Ullman:
A Turing machine can be formally defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where
$Q$ is a finite, non-empty set of states
$...
- 5,961
2
votes
When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis
Registers are different from memory in that you only have an absolute addressing mode, no indirect or relative addressing modes. They are also a finite resource in a way that can't be avoided (memory ...
- 17.8k
2
votes
When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis
It's a tradeoff between accuracy vs running time. CSA often provides more accurate (more precise) results than CIA; but it takes longer. There's no hard-and-fast rule about when you must use one or ...
D.W.♦
- 164k
2
votes
Accepted
How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?
In this case, the notation $F^n$ denotes iterated composition, that is, repeatedly applying the function $F$, for $n$ iterations:
$F^0(x) = x$.
$F^1(x) = F(x)$.
$F^2(x) = F(F(x))$.
$F^3(x) = F(F(F(x))...
- 278k
2
votes
Accepted
Dataflow Analysis: Available Expressions, why is OUT[B] initialized to universal set?
I had a similar question. I think the conclusion is that starting with the empty set will give you a valid solution, but it won't always be the largest possible solution. We desire the largest ...
2
votes
Accepted
What is the intepretation of the top & bottom elements of a lattice?
No, there is no intrinsic meaning. Their meaning depends on the specific data analysis and how it uses the particular lattice or what interpretation we put on them.
Often, bottom is used for ...
D.W.♦
- 164k
1
vote
How to verify no side effects from added code in C++?
I'd guess that the best you can do in practice, in most situations, is manual code review.
In most cases, static analysis is unlikely to be effective at evaluating risks that (1) the new code uses up ...
D.W.♦
- 164k
1
vote
Accepted
data flow analysis reaching definition analysis meaning
First, the author is talking about basic blocks only.
Second, you are right about the part that when the basic block has a code line $a = b + c$, then the old definitions of $a$ are killed and this is ...
- 46
1
vote
Accepted
Can reading a value of a variable kill the definition of the variable?
I can't find the errata sheet for the 1st edition (this came from the first ed, right? That diagram is so 1980's) but it sure looks like a mistake. The 2nd edition says
"We say a definition d ...
- 209
1
vote
Difference between forward/backward slicing and reaching definition - def/use - use/def chains
Backward slicing includes both data and control dependencies while ud-chains consider only data depedencies.
- 11
1
vote
Accepted
How to Compute the Fixed Point on a DataFlow Lattice
You don't compute the least fixpoint of a lattice; you compute the least fixpoint of a function $f$. The standard method is to use a method called chaotic iteration, which is exactly the iterative ...
D.W.♦
- 164k
1
vote
Accepted
How to Construct a Lattice from Program Statements
There is no such thing as a "DataFlow Graph lattice". Those are two separate things. A data flow graph is a graph that represents how data flows in a program, which can be helpful in data flow ...
D.W.♦
- 164k
1
vote
Accepted
Saving information from reaching definition
Here are just a few examples:
dead-code elimination,
instruction reordering, and
(implementation of) scoping/shadowing.
- 72.8k
1
vote
Accepted
Inferring used fields in return type
Few otherwise general-purpose languages bother to deeply integrate with (relational) databases. Most languages I've seen that do do some integration (though fairly shallowly) are bolt-on abominations. ...
- 12.1k
1
vote
Accepted
What makes data flow analysis higher level than control flow analysis?
Look at Wikipedia article "Control Flow". It contains typical flow chart. Arcs are the ways where control token moves from one node to another.
Now imagine you want to employ parallelism and launch ...
- 126
1
vote
Backward data-flow: post-order or RPO on reverse CFG?
It is mostly due to the speed of convergence. To clarify, RPO visits as many predecessors possible before visiting a node so in case of forward data flow problems (like Dominator computation) this ...
- 139
Only top scored, non community-wiki answers of a minimum length are eligible