Use-define Chain - Method of Building A use-def (or ud) Chain

Method of Building A use-def (or ud) Chain

  1. Set definitions in statement s(0)
  2. For each i in, find live definitions that have use in statement s(i)
  3. Make a link among definitions and uses
  4. Set the statement s(i), as definition statement
  5. Kill previous definitions

With this algorithm, two things are accomplished:

  1. A directed acyclic graph (DAG) is created on the variable uses and definitions. The DAG specifies a data dependency among assignment statements, as well as a partial order (therefore parallelism among statements).
  2. When statement s(i) is reached, there is a list of live variable assignments. If only one assignment is live, for example, constant propagation might be used.

Read more about this topic:  Use-define Chain

Famous quotes containing the words method, building and/or chain:

    “Methinks the human method of expression by sound of tongue is very elementary, & ought to be substituted for some ingenious invention which should be able to give vent to at least six coherent sentences at once.”
    —Virginia Woolf (1882–1941)

    “The real dividing line between early childhood and middle childhood is not between the fifth year and the sixth year—it is more nearly when children are about seven or eight, moving on toward nine. Building the barrier at six has no psychological basis. It has come about only from the historic-economic-political fact that the age of six is when we provide schools for all.”
    —James L. Hymes, Jr. (20th century)

    “To avoid tripping on the chain of the past, you have to pick it up and wind it about you.”
    —Mason Cooley (b. 1927)