|
|
|
|
|
Use-define ChainUse-define chains model the relation among definitions of variables and their uses in a sequence of assignments within computer programming. The list of statements determines a strong order among statements. We label statements using the following conventions: s(i) where i is an integer in 1,n and n is the number of statements in the basic block; we identify variables in italic (e.g., v,u and t); we assume that every variable has a definition in the context (or scope): for a variable v we identify its declaration as V (italic capital letter) and for short we identify as s(0). In general, a declaration of a variable can be in an outer scope (e.g., we may deal with a global variable). Definition of a variable: when a variable v is on the LHS of an assignment statement s(j), then s(j) is a definition of v. Every variable v has at least one definition by its declaration V (or initialization). Use of a variable: if variable v is on the RHS of a statement s(j), there is a statement s(i), with i and min(j-i), that it is definition of v and it has a use at s(j). (we may use for short that when a variable v is on the RHS of a statement s(j), then v has a use at statement s(j).) Consider now the sequential execution of the list of statements s(i) and consider that we observe the computation at statement j: - A definition at statement s(i) with i is alive at j, if it has a use at a statement s(k) with k>=j. We define the set of alive definitions at statement i as A(i) and we denote the number of alive definitions as |A(i)|.
- A(i) is a simple but powerful concept: extremely important theoretical and practical results in such as Space Complexity Theory, Access complexity (I/O complexity), Register allocation and cache locality exploitation are based on A(i).
- A definition at statement s(i) kills all previous definitions (s(k) with k) for the same variables.
We build a use-def (or ud) chain as follows: set definitions in statement s(0) for each i in 1,n find alive definitions that have use in statement s(i) make a link among definitions and uses. set as definition statement the statement s(i) kill previous definitions With this algorithm we do two things: - We create a DAG structures among variables. The DAG specifies a data dependency among assignment statements and also it specifies a partial order (therefore parallelism among statements).
#When we reach a statement s(i) we have a list of alive variables-statements.
|
 |
| |
|
|