Definition-use graph

Concepts

• The definition-use graph is a program graph suitable to represent the different status of a variable. <bib>rapps-weyuker:1982</bib>, <bib>vincenzi-etal:slides:2007</bib>

Facts

• The definition-use graph is called of DUG. <bib>vincenzi-etal:slides:2007</bib>, <bib>vincenzi-maldonado:slides:2007</bib>

• The definition-use graph is an extension of the control flow graph. <bib>vincenzi-etal:slides:2007</bib>, <bib>vincenzi-maldonado:slides:2007</bib>

• The definition-use graph includes information about variable definitions, uses and destructions on each node. <bib>vincenzi-etal:slides:2007</bib>, <bib>vincenzi-maldonado:slides:2007</bib>

• The definition-use graph can be static or dynamically analyzed: statically to examine the diagram (formally through inspections or informally through look-sees); dynamically to construct and execute test cases. <bib>vincenzi-maldonado:slides:2007</bib>

• The definition-use graph contains all definition-use pairs for a program. <bib>mathur:2008, 461</bib>

Procedures

• Definition-use graph construction <bib>mathur:2008, 458</bib>
  1. Consider a control-flow graph G = (N, E) of a program P, where N is the set of nodes and E the set of edges. Each node in G corresponds to a code block in P: those blocks are denoted as <math>b_{1}, b_{2}, ..., b_{k}</math>, assuming that P contains k > 0 code blocks.
  2. Let <math>def_{i}</math> denote the set of variables defined in code block i.
  3. Let <math>c-use_{i}</math> denote the set of variables that have a computational use in code block i.
  4. Let <math>p-use_{i}</math> denote the set of variables that have a predicative use in code block i.
  5. Compute <math>def_{i}</math>, <math>c-use_{i}</math>, and <math>p-use_{i}</math> for each code block i in P.
  6. Associate each node i in N with <math>def_{i}</math>, <math>c-use_{i}</math>, and <math>p-use_{i}</math>.
  7. For each node i that as a nonempty predicative use sets and ends in condition C, associate edges (i, j) and (i, k) with C and !C, respectively, given that edge (i, j) is taken when the condition is true and (i, k) is taken when the condition is false.