Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 6340 > L5 > Flashcards

L5 Flashcards

1
Q

dataflow analysis

A

reasoning about flow of data in program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

different kinds of dataflow analysis

A

constants, variables, expressions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what do dataflow analysis used in

A

bug-finding tools and compilers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is a control-flow graph?

A

a graph that summarizes the flow of control in all possible runs of the program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what does each node represent?

A

a unique primitive statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what does each edge represent?

A

denotes immediate possible successor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

can we achieve soundness, completeness, and termination?

A

no

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what does dataflow analysis sacrifice?

A

completeness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How does dataflow analysis sacrifice completeness?

A

abstract away control-flow condition with non-deterministic choice

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what non-deterministic choice does dataflow analysis use?

A

assume a condition can be evaluated to true or false. It considers path that is not possible in the actual run, thus incomplete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

applications of dataflow analysis

A

reaching definition analysis, very busy expression analysis, available expression analysis, and live variable analysis.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

reaching definition analysis

A

find usages of uninitialized variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

very busy expression analysis

A

reduce code size (use in pacemakers)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

available expression analysis

A

use by the compiler to avoid recomputing expressions. Start with all available expression, and cross each out whenever it changes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

live variable analysis

A

use by the compiler to efficiently allocate registers to program variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

reaching definition analysis’ goal

A
  • determines with assignment might reach each program point.
  • determines for each program point, which assignments have been made and not overwritten, when execution reaches that point along some path.
17
Q

result of dataflow analysis (informally)

A
  • set of facts at each program point in the form ex: ,
18
Q

result of dataflow analysis (formally)

A
  • compute the set of fact in and out each node: IN(n) and OUT(n), repeat until they stop changing (saturated or fixed point)
19
Q

(reaching definition analysis operation 1) how to compute IN[n]

A

IN[n] = U(OUT[predecessors(n)])

20
Q

(reaching definition analysis operation 2) how to compute OUT[n]

A

OUT(n) = (IN[n] - KILL[n]) U GEN[n]

21
Q

(reaching definition analysis) KILL[n]) & GEN[n] of a condtion

A

empty sets

22
Q

(reaching definition analysis) KILL[n] & GEN[n] of an assignment

A

GEN[n] = {}; KILL[n]={: m!=n}

23
Q

(reaching definition analysis) Chaotic Iteration

A 
for (each node n):
IN[n] = OUT[n] = null
OUT[entry] = {: v is a program variable}
Repeat:
for each node n: operation1; operation2; until IN[n] & OUT[n] stop changing
24
Q

why does it always terminate

A
  • the 2 operations are monotonic: the IN[n] & OUT[n] sets never shrink, only grow
  • largest is the set of all definitions in the program, which is finite
25
Q

very busy expression analysis’ goal

A

determine very busy expressions at the exit from the point

26
Q

what is a very busy expression

A

an expression (not a statement, only the right side of the “=” sign) that is used before any of the variables occurring in it are redefined.

27
Q

(very busy expression operation 1) how to compute OUT[n]

A

OUT[n] = Intersection(In[successors(n)])

28
Q

(very busy expression operation 2) how to compute IN[n]

A

IN[n] = (OUT[n] - KILL[n]) U GEN[n]

29
Q

(very busy expression) KILL[n]) & GEN[n] of a condtion

A

empty sets

30
Q

(very busy expression) KILL[n]) & GEN[n] of an assignment

A

GEN[n] = {a}; KILL[n]={expr e: e contains x}

31
Q

(very busy expression) Chaotic Iteration

A

for (each node n):
IN[n] = OUT[n] = set of all exprs in the program
IN[exit] = {}
Repeat:
for each node n: operation1; operation2; until IN[n] & OUT[n] stop changing

32
Q

available expression analysis’ goal

A

determine, for each program point, which expression must already have been computed, and not later modified, on all paths to the program point

33
Q

live variable analysis’ goal

A

determine for each program point which variables could be live at the point’s exit

34
Q

what is a live variable? (at point P)

A

if there is a path to a use of the variable that doesn’t redefine the variable (at or after point P)

35
Q

may vs must facts

A

may: facts along some paths
must: facts along all paths

CS 6340 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions