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:

    “There is no method but to be very intelligent.”
    —T.S. (Thomas Stearns)

    “For we know that if the earthly tent we live in is destroyed, we have a building from God, a house not made with hands, eternal in the heavens.”
    —Bible: New Testament, 2 Corinthians 5:1.

    “It could not have come down to us so far,
    Through the interstices of things ajar
    On the long bead chain of repeated birth,
    To be a bird while we are men on earth,”
    —Robert Frost (1874–1963)