Use-define chain

Setup

The list of statements determines a strong order among statements.

• Statements are labeled using the following conventions: ⁠${\displaystyle s(i)}$⁠, where i is an integer in ⁠${\displaystyle [1,n]}$⁠; and n is the number of statements in the basic block
• Variables are identified in italic (e.g., v,u and t)
• Every variable is assumed to have a definition in the context or scope. (In static single assignment form, use-define chains are explicit because each chain contains a single element.)

For a variable, such as v, its declaration is identified as V (italic capital letter), and for short, its declaration is identified as ⁠${\displaystyle s(0)}$⁠. In general, a declaration of a variable can be in an outer scope (e.g., a global variable).

Definition of a variable

When a variable, v, is on the LHS of an assignment statement, such as ⁠${\displaystyle s(j)}$⁠, then ⁠${\displaystyle 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 statement ⁠${\displaystyle s(j)}$⁠, there is a statement, ⁠${\displaystyle s(i)}$⁠ with i < j and ⁠${\displaystyle min(j-i)}$⁠, that it is a definition of v and it has a use at ⁠${\displaystyle s(j)}$⁠ (or, in short, when a variable, v, is on the RHS of a statement ⁠${\displaystyle s(j)}$⁠, then v has a use at statement ⁠${\displaystyle s(j)}$⁠).

Execution

Consider the sequential execution of the list of statements, ⁠${\displaystyle s(i)}$⁠, and what can now be observed as the computation at statement, j:

• A definition at statement ⁠${\displaystyle s(i)}$⁠ with i < j is alive at j, if it has a use at a statement ⁠${\displaystyle s(k)}$⁠ with k ≥ j. The set of alive definitions at statement i is denoted as ⁠${\displaystyle A(i)}$⁠ and the number of alive definitions as ${\displaystyle |A(i)|}$. (⁠${\displaystyle A(i)}$⁠ is a simple but powerful concept: theoretical and practical results in space complexity theory, access complexity(I/O complexity), register allocation and cache locality exploitation are based on ⁠${\displaystyle A(i)}$⁠.)
• A definition at statement ⁠${\displaystyle s(i)}$⁠ kills all previous definitions (⁠${\displaystyle s(k)}$⁠ with k < i) for the same variables.

Execution example for def-use-chain

This example is based on a Java algorithm for finding the gcd. (It is not important to understand what this function does.)

<span id="mw1Q"></span><span class="linenos" data-line="1" id="mw1g"></span><span class="cm" id="mw1w">/**</span> <span class="linenos" data-line="2" id="mw2A"></span><span class="cm" id="mw2Q"> * @param(a, b) The values used to calculate the divisor.</span> <span class="linenos" data-line="3" id="mw2g"></span><span class="cm" id="mw2w"> * @return The greatest common divisor of a and b.</span> <span class="linenos" data-line="4" id="mw3A"></span><span class="cm" id="mw3Q"> */</span> <span class="linenos" data-line="5" id="mw3g"></span><span class="kt" id="mw3w">int</span><span class="w" id="mw4A"> </span><span class="nf" id="mw4Q">gcd</span><span class="p" id="mw4g">(</span><span class="kt" id="mw4w">int</span><span class="w" id="mw5A"> </span><span class="n" id="mw5Q">a</span><span class="p" id="mw5g">,</span><span class="w" id="mw5w"> </span><span class="kt" id="mw6A">int</span><span class="w" id="mw6Q"> </span><span class="n" id="mw6g">b</span><span class="p" id="mw6w">)</span><span class="w" id="mw7A"> </span><span class="p" id="mw7Q">{</span><span class="w" id="mw7g"> </span> <span class="linenos" data-line="6" id="mw7w"></span><span class="w" id="mw8A"> </span><span class="kt" id="mw8Q">int</span><span class="w" id="mw8g"> </span><span class="n" id="mw8w">c</span><span class="w" id="mw9A"> </span><span class="o" id="mw9Q">=</span><span class="w" id="mw9g"> </span><span class="n" id="mw9w">a</span><span class="p" id="mw-A">;</span> <span class="linenos" data-line="7" id="mw-Q"></span><span class="w" id="mw-g"> </span><span class="kt" id="mw-w">int</span><span class="w" id="mw_A"> </span><span class="n" id="mw_Q">d</span><span class="w" id="mw_g"> </span><span class="o" id="mw_w">=</span><span class="w" id="mwAQA"> </span><span class="n" id="mwAQE">b</span><span class="p" id="mwAQI">;</span><span class="w" id="mwAQM"> </span> <span class="linenos" data-line="8" id="mwAQQ"></span><span class="w" id="mwAQU"> </span><span class="k" id="mwAQY">if</span><span class="w" id="mwAQc"> </span><span class="p" id="mwAQg">(</span><span class="n" id="mwAQk">c</span><span class="w" id="mwAQo"> </span><span class="o" id="mwAQs">==</span><span class="w" id="mwAQw"> </span><span class="mi" id="mwAQ0">0</span><span class="p" id="mwAQ4">)</span> <span class="linenos" data-line="9" id="mwAQ8"></span><span class="w" id="mwARA"> </span><span class="k" id="mwARE">return</span><span class="w" id="mwARI"> </span><span class="n" id="mwARM">d</span><span class="p" id="mwARQ">;</span> <span class="linenos" data-line="10" id="mwARU"></span><span class="w" id="mwARY"> </span><span class="k" id="mwARc">while</span><span class="w" id="mwARg"> </span><span class="p" id="mwARk">(</span><span class="n" id="mwARo">d</span><span class="w" id="mwARs"> </span><span class="o" id="mwARw">!=</span><span class="w" id="mwAR0"> </span><span class="mi" id="mwAR4">0</span><span class="p" id="mwAR8">)</span><span class="w" id="mwASA"> </span><span class="p" id="mwASE">{</span><span class="w" id="mwASI"> </span> <span class="linenos" data-line="11" id="mwASM"></span><span class="w" id="mwASQ"> </span><span class="k" id="mwASU">if</span><span class="w" id="mwASY"> </span><span class="p" id="mwASc">(</span><span class="n" id="mwASg">c</span><span class="w" id="mwASk"> </span><span class="o" id="mwASo">></span><span class="w" id="mwASs"> </span><span class="n" id="mwASw">d</span><span class="p" id="mwAS0">)</span> <span class="linenos" data-line="12" id="mwAS4"></span><span class="w" id="mwAS8"> </span><span class="n" id="mwATA">c</span><span class="w" id="mwATE"> </span><span class="o" id="mwATI">=</span><span class="w" id="mwATM"> </span><span class="n" id="mwATQ">c</span><span class="w" id="mwATU"> </span><span class="o" id="mwATY">-</span><span class="w" id="mwATc"> </span><span class="n" id="mwATg">d</span><span class="p" id="mwATk">;</span> <span class="linenos" data-line="13" id="mwATo"></span><span class="w" id="mwATs"> </span><span class="k" id="mwATw">else</span> <span class="linenos" data-line="14" id="mwAT0"></span><span class="w" id="mwAT4"> </span><span class="n" id="mwAT8">d</span><span class="w" id="mwAUA"> </span><span class="o" id="mwAUE">=</span><span class="w" id="mwAUI"> </span><span class="n" id="mwAUM">d</span><span class="w" id="mwAUQ"> </span><span class="o" id="mwAUU">-</span><span class="w" id="mwAUY"> </span><span class="n" id="mwAUc">c</span><span class="p" id="mwAUg">;</span> <span class="linenos" data-line="15" id="mwAUk"></span><span class="w" id="mwAUo"> </span><span class="p" id="mwAUs">}</span><span class="w" id="mwAUw"> </span> <span class="linenos" data-line="16" id="mwAU0"></span><span class="w" id="mwAU4"> </span><span class="k" id="mwAU8">return</span><span class="w" id="mwAVA"> </span><span class="n" id="mwAVE">c</span><span class="p" id="mwAVI">;</span><span class="w" id="mwAVM"> </span> <span class="linenos" data-line="17" id="mwAVQ"></span><span class="p" id="mwAVU">}</span>

To find out all def-use-chains for variable d, do the following steps:

1. Search for the first time the variable is defined (write access).

   In this case it is "d=b" (l.7)

2. Search for the first time the variable is read.

   In this case it is "return d"

3. Write down this information in the following style: [name of the variable you are creating a def-use-chain for, the concrete write access, the concrete read access]

   In this case it is: [d, d=b, return d]

Repeat these steps in the following style: combine each write access with each read access (but NOT the other way round).

The result should be:

<span id="mwAWg"></span><span class="linenos" data-line="1" id="mwAWk"></span><span class="w" id="mwAWo"> </span><span class="p" id="mwAWs">[</span><span class="n" id="mwAWw">d</span><span class="p" id="mwAW0">,</span><span class="w" id="mwAW4"> </span><span class="n" id="mwAW8">d</span><span class="o" id="mwAXA">=</span><span class="n" id="mwAXE">b</span><span class="p" id="mwAXI">,</span><span class="w" id="mwAXM"> </span><span class="k" id="mwAXQ">return</span><span class="w" id="mwAXU"> </span><span class="n" id="mwAXY">d</span><span class="p" id="mwAXc">]</span><span class="w" id="mwAXg"> </span> <span class="linenos" data-line="2" id="mwAXk"></span><span class="w" id="mwAXo"> </span><span class="p" id="mwAXs">[</span><span class="n" id="mwAXw">d</span><span class="p" id="mwAX0">,</span><span class="w" id="mwAX4"> </span><span class="n" id="mwAX8">d</span><span class="o" id="mwAYA">=</span><span class="n" id="mwAYE">b</span><span class="p" id="mwAYI">,</span><span class="w" id="mwAYM"> </span><span class="k" id="mwAYQ">while</span><span class="p" id="mwAYU">(</span><span class="n" id="mwAYY">d</span><span class="o" id="mwAYc">!=</span><span class="mi" id="mwAYg">0</span><span class="p" id="mwAYk">)]</span><span class="w" id="mwAYo"> </span> <span class="linenos" data-line="3" id="mwAYs"></span><span class="w" id="mwAYw"> </span><span class="p" id="mwAY0">[</span><span class="n" id="mwAY4">d</span><span class="p" id="mwAY8">,</span><span class="w" id="mwAZA"> </span><span class="n" id="mwAZE">d</span><span class="o" id="mwAZI">=</span><span class="n" id="mwAZM">b</span><span class="p" id="mwAZQ">,</span><span class="w" id="mwAZU"> </span><span class="k" id="mwAZY">if</span><span class="p" id="mwAZc">(</span><span class="n" id="mwAZg">c</span><span class="o" id="mwAZk">></span><span class="n" id="mwAZo">d</span><span class="p" id="mwAZs">)]</span><span class="w" id="mwAZw"> </span> <span class="linenos" data-line="4" id="mwAZ0"></span><span class="w" id="mwAZ4"> </span><span class="p" id="mwAZ8">[</span><span class="n" id="mwAaA">d</span><span class="p" id="mwAaE">,</span><span class="w" id="mwAaI"> </span><span class="n" id="mwAaM">d</span><span class="o" id="mwAaQ">=</span><span class="n" id="mwAaU">b</span><span class="p" id="mwAaY">,</span><span class="w" id="mwAac"> </span><span class="n" id="mwAag">c</span><span class="o" id="mwAak">=</span><span class="n" id="mwAao">c</span><span class="o" id="mwAas">-</span><span class="n" id="mwAaw">d</span><span class="p" id="mwAa0">]</span><span class="w" id="mwAa4"> </span> <span class="linenos" data-line="5" id="mwAa8"></span><span class="w" id="mwAbA"> </span><span class="p" id="mwAbE">[</span><span class="n" id="mwAbI">d</span><span class="p" id="mwAbM">,</span><span class="w" id="mwAbQ"> </span><span class="n" id="mwAbU">d</span><span class="o" id="mwAbY">=</span><span class="n" id="mwAbc">b</span><span class="p" id="mwAbg">,</span><span class="w" id="mwAbk"> </span><span class="n" id="mwAbo">d</span><span class="o" id="mwAbs">=</span><span class="n" id="mwAbw">d</span><span class="o" id="mwAb0">-</span><span class="n" id="mwAb4">c</span><span class="p" id="mwAb8">]</span> <span class="linenos" data-line="6" id="mwAcA"></span><span class="w" id="mwAcE"> </span><span class="p" id="mwAcI">[</span><span class="n" id="mwAcM">d</span><span class="p" id="mwAcQ">,</span><span class="w" id="mwAcU"> </span><span class="n" id="mwAcY">d</span><span class="o" id="mwAcc">=</span><span class="n" id="mwAcg">d</span><span class="o" id="mwAck">-</span><span class="n" id="mwAco">c</span><span class="p" id="mwAcs">,</span><span class="w" id="mwAcw"> </span><span class="k" id="mwAc0">while</span><span class="p" id="mwAc4">(</span><span class="n" id="mwAc8">d</span><span class="o" id="mwAdA">!=</span><span class="mi" id="mwAdE">0</span><span class="p" id="mwAdI">)]</span><span class="w" id="mwAdM"> </span> <span class="linenos" data-line="7" id="mwAdQ"></span><span class="w" id="mwAdU"> </span><span class="p" id="mwAdY">[</span><span class="n" id="mwAdc">d</span><span class="p" id="mwAdg">,</span><span class="w" id="mwAdk"> </span><span class="n" id="mwAdo">d</span><span class="o" id="mwAds">=</span><span class="n" id="mwAdw">d</span><span class="o" id="mwAd0">-</span><span class="n" id="mwAd4">c</span><span class="p" id="mwAd8">,</span><span class="w" id="mwAeA"> </span><span class="k" id="mwAeE">if</span><span class="p" id="mwAeI">(</span><span class="n" id="mwAeM">c</span><span class="o" id="mwAeQ">></span><span class="n" id="mwAeU">d</span><span class="p" id="mwAeY">)]</span><span class="w" id="mwAec"> </span> <span class="linenos" data-line="8" id="mwAeg"></span><span class="w" id="mwAek"> </span><span class="p" id="mwAeo">[</span><span class="n" id="mwAes">d</span><span class="p" id="mwAew">,</span><span class="w" id="mwAe0"> </span><span class="n" id="mwAe4">d</span><span class="o" id="mwAe8">=</span><span class="n" id="mwAfA">d</span><span class="o" id="mwAfE">-</span><span class="n" id="mwAfI">c</span><span class="p" id="mwAfM">,</span><span class="w" id="mwAfQ"> </span><span class="n" id="mwAfU">c</span><span class="o" id="mwAfY">=</span><span class="n" id="mwAfc">c</span><span class="o" id="mwAfg">-</span><span class="n" id="mwAfk">d</span><span class="p" id="mwAfo">]</span><span class="w" id="mwAfs"> </span> <span class="linenos" data-line="9" id="mwAfw"></span><span class="w" id="mwAf0"> </span><span class="p" id="mwAf4">[</span><span class="n" id="mwAf8">d</span><span class="p" id="mwAgA">,</span><span class="w" id="mwAgE"> </span><span class="n" id="mwAgI">d</span><span class="o" id="mwAgM">=</span><span class="n" id="mwAgQ">d</span><span class="o" id="mwAgU">-</span><span class="n" id="mwAgY">c</span><span class="p" id="mwAgc">,</span><span class="w" id="mwAgg"> </span><span class="n" id="mwAgk">d</span><span class="o" id="mwAgo">=</span><span class="n" id="mwAgs">d</span><span class="o" id="mwAgw">-</span><span class="n" id="mwAg0">c</span><span class="p" id="mwAg4">]</span>

You have to take care, if the variable is changed by the time.

For example: From line 7 down to line 13 in the source code, d is not redefined / changed. At line 14, d could be redefined. This is why you have to recombine this write access on d with all possible read accesses which could be reached. In this case, only the code beyond line 10 is relevant. Line 7, for example, cannot be reached again. For your understanding, you can imagine 2 different variables d:

<span id="mwAhs"></span><span class="linenos" data-line="1" id="mwAhw"></span><span class="w" id="mwAh0"> </span><span class="p" id="mwAh4">[</span><span class="n" id="mwAh8">d1</span><span class="p" id="mwAiA">,</span><span class="w" id="mwAiE"> </span><span class="n" id="mwAiI">d1</span><span class="o" id="mwAiM">=</span><span class="n" id="mwAiQ">b</span><span class="p" id="mwAiU">,</span><span class="w" id="mwAiY"> </span><span class="k" id="mwAic">return</span><span class="w" id="mwAig"> </span><span class="n" id="mwAik">d1</span><span class="p" id="mwAio">]</span><span class="w" id="mwAis"> </span> <span class="linenos" data-line="2" id="mwAiw"></span><span class="w" id="mwAi0"> </span><span class="p" id="mwAi4">[</span><span class="n" id="mwAi8">d1</span><span class="p" id="mwAjA">,</span><span class="w" id="mwAjE"> </span><span class="n" id="mwAjI">d1</span><span class="o" id="mwAjM">=</span><span class="n" id="mwAjQ">b</span><span class="p" id="mwAjU">,</span><span class="w" id="mwAjY"> </span><span class="k" id="mwAjc">while</span><span class="p" id="mwAjg">(</span><span class="n" id="mwAjk">d1</span><span class="o" id="mwAjo">!=</span><span class="mi" id="mwAjs">0</span><span class="p" id="mwAjw">)]</span><span class="w" id="mwAj0"> </span> <span class="linenos" data-line="3" id="mwAj4"></span><span class="w" id="mwAj8"> </span><span class="p" id="mwAkA">[</span><span class="n" id="mwAkE">d1</span><span class="p" id="mwAkI">,</span><span class="w" id="mwAkM"> </span><span class="n" id="mwAkQ">d1</span><span class="o" id="mwAkU">=</span><span class="n" id="mwAkY">b</span><span class="p" id="mwAkc">,</span><span class="w" id="mwAkg"> </span><span class="k" id="mwAkk">if</span><span class="p" id="mwAko">(</span><span class="n" id="mwAks">c</span><span class="o" id="mwAkw">></span><span class="n" id="mwAk0">d1</span><span class="p" id="mwAk4">)]</span><span class="w" id="mwAk8"> </span> <span class="linenos" data-line="4" id="mwAlA"></span><span class="w" id="mwAlE"> </span><span class="p" id="mwAlI">[</span><span class="n" id="mwAlM">d1</span><span class="p" id="mwAlQ">,</span><span class="w" id="mwAlU"> </span><span class="n" id="mwAlY">d1</span><span class="o" id="mwAlc">=</span><span class="n" id="mwAlg">b</span><span class="p" id="mwAlk">,</span><span class="w" id="mwAlo"> </span><span class="n" id="mwAls">c</span><span class="o" id="mwAlw">=</span><span class="n" id="mwAl0">c</span><span class="o" id="mwAl4">-</span><span class="n" id="mwAl8">d1</span><span class="p" id="mwAmA">]</span><span class="w" id="mwAmE"> </span> <span class="linenos" data-line="5" id="mwAmI"></span><span class="w" id="mwAmM"> </span><span class="p" id="mwAmQ">[</span><span class="n" id="mwAmU">d1</span><span class="p" id="mwAmY">,</span><span class="w" id="mwAmc"> </span><span class="n" id="mwAmg">d1</span><span class="o" id="mwAmk">=</span><span class="n" id="mwAmo">b</span><span class="p" id="mwAms">,</span><span class="w" id="mwAmw"> </span><span class="n" id="mwAm0">d1</span><span class="o" id="mwAm4">=</span><span class="n" id="mwAm8">d1</span><span class="o" id="mwAnA">-</span><span class="n" id="mwAnE">c</span><span class="p" id="mwAnI">]</span> <span class="linenos" data-line="6" id="mwAnM"></span><span class="w" id="mwAnQ"> </span><span class="p" id="mwAnU">[</span><span class="n" id="mwAnY">d2</span><span class="p" id="mwAnc">,</span><span class="w" id="mwAng"> </span><span class="n" id="mwAnk">d2</span><span class="o" id="mwAno">=</span><span class="n" id="mwAns">d2</span><span class="o" id="mwAnw">-</span><span class="n" id="mwAn0">c</span><span class="p" id="mwAn4">,</span><span class="w" id="mwAn8"> </span><span class="k" id="mwAoA">while</span><span class="p" id="mwAoE">(</span><span class="n" id="mwAoI">d2</span><span class="o" id="mwAoM">!=</span><span class="mi" id="mwAoQ">0</span><span class="p" id="mwAoU">)]</span><span class="w" id="mwAoY"> </span> <span class="linenos" data-line="7" id="mwAoc"></span><span class="w" id="mwAog"> </span><span class="p" id="mwAok">[</span><span class="n" id="mwAoo">d2</span><span class="p" id="mwAos">,</span><span class="w" id="mwAow"> </span><span class="n" id="mwAo0">d2</span><span class="o" id="mwAo4">=</span><span class="n" id="mwAo8">d2</span><span class="o" id="mwApA">-</span><span class="n" id="mwApE">c</span><span class="p" id="mwApI">,</span><span class="w" id="mwApM"> </span><span class="k" id="mwApQ">if</span><span class="p" id="mwApU">(</span><span class="n" id="mwApY">c</span><span class="o" id="mwApc">></span><span class="n" id="mwApg">d2</span><span class="p" id="mwApk">)]</span><span class="w" id="mwApo"> </span> <span class="linenos" data-line="8" id="mwAps"></span><span class="w" id="mwApw"> </span><span class="p" id="mwAp0">[</span><span class="n" id="mwAp4">d2</span><span class="p" id="mwAp8">,</span><span class="w" id="mwAqA"> </span><span class="n" id="mwAqE">d2</span><span class="o" id="mwAqI">=</span><span class="n" id="mwAqM">d2</span><span class="o" id="mwAqQ">-</span><span class="n" id="mwAqU">c</span><span class="p" id="mwAqY">,</span><span class="w" id="mwAqc"> </span><span class="n" id="mwAqg">c</span><span class="o" id="mwAqk">=</span><span class="n" id="mwAqo">c</span><span class="o" id="mwAqs">-</span><span class="n" id="mwAqw">d2</span><span class="p" id="mwAq0">]</span><span class="w" id="mwAq4"> </span> <span class="linenos" data-line="9" id="mwAq8"></span><span class="w" id="mwArA"> </span><span class="p" id="mwArE">[</span><span class="n" id="mwArI">d2</span><span class="p" id="mwArM">,</span><span class="w" id="mwArQ"> </span><span class="n" id="mwArU">d2</span><span class="o" id="mwArY">=</span><span class="n" id="mwArc">d2</span><span class="o" id="mwArg">-</span><span class="n" id="mwArk">c</span><span class="p" id="mwAro">,</span><span class="w" id="mwArs"> </span><span class="n" id="mwArw">d2</span><span class="o" id="mwAr0">=</span><span class="n" id="mwAr4">d2</span><span class="o" id="mwAr8">-</span><span class="n" id="mwAsA">c</span><span class="p" id="mwAsE">]</span>

As a result, you could get something like this. The variable d1 would be replaced by b

<span id="mwAsk"></span><span class="linenos" data-line="1" id="mwAso"></span><span class="cm" id="mwAss">/**</span> <span class="linenos" data-line="2" id="mwAsw"></span><span class="cm" id="mwAs0"> * @param(a, b) The values used to calculate the divisor.</span> <span class="linenos" data-line="3" id="mwAs4"></span><span class="cm" id="mwAs8"> * @return The greatest common divisor of a and b.</span> <span class="linenos" data-line="4" id="mwAtA"></span><span class="cm" id="mwAtE"> **/</span> <span class="linenos" data-line="5" id="mwAtI"></span><span class="kt" id="mwAtM">int</span><span class="w" id="mwAtQ"> </span><span class="nf" id="mwAtU">gcd</span><span class="p" id="mwAtY">(</span><span class="kt" id="mwAtc">int</span><span class="w" id="mwAtg"> </span><span class="n" id="mwAtk">a</span><span class="p" id="mwAto">,</span><span class="w" id="mwAts"> </span><span class="kt" id="mwAtw">int</span><span class="w" id="mwAt0"> </span><span class="n" id="mwAt4">b</span><span class="p" id="mwAt8">)</span><span class="w" id="mwAuA"> </span><span class="p" id="mwAuE">{</span> <span class="linenos" data-line="6" id="mwAuI"></span><span class="w" id="mwAuM"> </span><span class="kt" id="mwAuQ">int</span><span class="w" id="mwAuU"> </span><span class="n" id="mwAuY">c</span><span class="w" id="mwAuc"> </span><span class="o" id="mwAug">=</span><span class="w" id="mwAuk"> </span><span class="n" id="mwAuo">a</span><span class="p" id="mwAus">;</span> <span class="linenos" data-line="7" id="mwAuw"></span><span class="w" id="mwAu0"> </span><span class="kt" id="mwAu4">int</span><span class="w" id="mwAu8"> </span><span class="n" id="mwAvA">d</span><span class="p" id="mwAvE">;</span><span class="w" id="mwAvI"> </span> <span class="linenos" data-line="8" id="mwAvM"></span><span class="w" id="mwAvQ"> </span><span class="k" id="mwAvU">if</span><span class="w" id="mwAvY"> </span><span class="p" id="mwAvc">(</span><span class="n" id="mwAvg">c</span><span class="w" id="mwAvk"> </span><span class="o" id="mwAvo">==</span><span class="w" id="mwAvs"> </span><span class="mi" id="mwAvw">0</span><span class="p" id="mwAv0">)</span> <span class="linenos" data-line="9" id="mwAv4"></span><span class="w" id="mwAv8"> </span><span class="k" id="mwAwA">return</span><span class="w" id="mwAwE"> </span><span class="n" id="mwAwI">b</span><span class="p" id="mwAwM">;</span> <span class="linenos" data-line="10" id="mwAwQ"></span><span class="w" id="mwAwU"> </span><span class="k" id="mwAwY">if</span><span class="w" id="mwAwc"> </span><span class="p" id="mwAwg">(</span><span class="n" id="mwAwk">b</span><span class="w" id="mwAwo"> </span><span class="o" id="mwAws">!=</span><span class="w" id="mwAww"> </span><span class="mi" id="mwAw0">0</span><span class="p" id="mwAw4">)</span><span class="w" id="mwAw8"> </span><span class="p" id="mwAxA">{</span> <span class="linenos" data-line="11" id="mwAxE"></span><span class="w" id="mwAxI"> </span><span class="k" id="mwAxM">if</span><span class="w" id="mwAxQ"> </span><span class="p" id="mwAxU">(</span><span class="n" id="mwAxY">c</span><span class="w" id="mwAxc"> </span><span class="o" id="mwAxg">></span><span class="w" id="mwAxk"> </span><span class="n" id="mwAxo">b</span><span class="p" id="mwAxs">)</span><span class="w" id="mwAxw"> </span><span class="p" id="mwAx0">{</span> <span class="linenos" data-line="12" id="mwAx4"></span><span class="w" id="mwAx8"> </span><span class="n" id="mwAyA">c</span><span class="w" id="mwAyE"> </span><span class="o" id="mwAyI">=</span><span class="w" id="mwAyM"> </span><span class="n" id="mwAyQ">c</span><span class="w" id="mwAyU"> </span><span class="o" id="mwAyY">-</span><span class="w" id="mwAyc"> </span><span class="n" id="mwAyg">b</span><span class="p" id="mwAyk">;</span> <span class="linenos" data-line="13" id="mwAyo"></span><span class="w" id="mwAys"> </span><span class="n" id="mwAyw">d</span><span class="w" id="mwAy0"> </span><span class="o" id="mwAy4">=</span><span class="w" id="mwAy8"> </span><span class="n" id="mwAzA">b</span><span class="p" id="mwAzE">;</span> <span class="linenos" data-line="14" id="mwAzI"></span><span class="w" id="mwAzM"> </span><span class="p" id="mwAzQ">}</span> <span class="linenos" data-line="15" id="mwAzU"></span><span class="w" id="mwAzY"> </span><span class="k" id="mwAzc">else</span> <span class="linenos" data-line="16" id="mwAzg"></span><span class="w" id="mwAzk"> </span><span class="n" id="mwAzo">d</span><span class="w" id="mwAzs"> </span><span class="o" id="mwAzw">=</span><span class="w" id="mwAz0"> </span><span class="n" id="mwAz4">b</span><span class="w" id="mwAz8"> </span><span class="o" id="mwA0A">-</span><span class="w" id="mwA0E"> </span><span class="n" id="mwA0I">c</span><span class="p" id="mwA0M">;</span> <span class="linenos" data-line="17" id="mwA0Q"></span><span class="w" id="mwA0U"> </span><span class="k" id="mwA0Y">while</span><span class="w" id="mwA0c"> </span><span class="p" id="mwA0g">(</span><span class="n" id="mwA0k">d</span><span class="w" id="mwA0o"> </span><span class="o" id="mwA0s">!=</span><span class="w" id="mwA0w"> </span><span class="mi" id="mwA00">0</span><span class="p" id="mwA04">)</span><span class="w" id="mwA08"> </span><span class="p" id="mwA1A">{</span><span class="w" id="mwA1E"> </span> <span class="linenos" data-line="18" id="mwA1I"></span><span class="w" id="mwA1M"> </span><span class="k" id="mwA1Q">if</span><span class="w" id="mwA1U"> </span><span class="p" id="mwA1Y">(</span><span class="n" id="mwA1c">c</span><span class="w" id="mwA1g"> </span><span class="o" id="mwA1k">></span><span class="w" id="mwA1o"> </span><span class="n" id="mwA1s">d</span><span class="p" id="mwA1w">)</span> <span class="linenos" data-line="19" id="mwA10"></span><span class="w" id="mwA14"> </span><span class="n" id="mwA18">c</span><span class="w" id="mwA2A"> </span><span class="o" id="mwA2E">=</span><span class="w" id="mwA2I"> </span><span class="n" id="mwA2M">c</span><span class="w" id="mwA2Q"> </span><span class="o" id="mwA2U">-</span><span class="w" id="mwA2Y"> </span><span class="n" id="mwA2c">d</span><span class="p" id="mwA2g">;</span> <span class="linenos" data-line="20" id="mwA2k"></span><span class="w" id="mwA2o"> </span><span class="k" id="mwA2s">else</span> <span class="linenos" data-line="21" id="mwA2w"></span><span class="w" id="mwA20"> </span><span class="n" id="mwA24">d</span><span class="w" id="mwA28"> </span><span class="o" id="mwA3A">=</span><span class="w" id="mwA3E"> </span><span class="n" id="mwA3I">d</span><span class="w" id="mwA3M"> </span><span class="o" id="mwA3Q">-</span><span class="w" id="mwA3U"> </span><span class="n" id="mwA3Y">c</span><span class="p" id="mwA3c">;</span> <span class="linenos" data-line="22" id="mwA3g"></span><span class="w" id="mwA3k"> </span><span class="p" id="mwA3o">}</span> <span class="linenos" data-line="23" id="mwA3s"></span><span class="w" id="mwA3w"> </span><span class="p" id="mwA30">}</span><span class="w" id="mwA34"> </span> <span class="linenos" data-line="24" id="mwA38"></span><span class="w" id="mwA4A"> </span><span class="k" id="mwA4E">return</span><span class="w" id="mwA4I"> </span><span class="n" id="mwA4M">c</span><span class="p" id="mwA4Q">;</span><span class="w" id="mwA4U"> </span> <span class="linenos" data-line="25" id="mwA4Y"></span><span class="p" id="mwA4c">}</span>

Method of building a use-def (or ud) chain

1. Set definitions in statement ⁠${\displaystyle s(0)}$⁠
2. For each i in ⁠${\displaystyle [1,n]}$⁠, find live definitions that have use in statement ⁠${\displaystyle s(i)}$⁠
3. Make a link among definitions and uses
4. Set the statement ⁠${\displaystyle 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 ⁠${\displaystyle 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.