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:

    “The method of painting is the natural growth out of a need. I want to express my feelings rather than illustrate them. Technique is just a means of arriving at a statement.... I can control the flow of paint: there is no accident, just as there is no beginning and no end.”
    —Jackson Pollock (1912–1956)

    “A truly great book should be read in youth, again in maturity and once more in old age, as a fine building should be seen by morning light, at noon and by moonlight.”
    —Robertson Davies (b. 1913)

    “A chain is no stronger than its weakest link, and life is after all a chain.”
    —William James (1842–1910)