<p>I wrote a global value numbering algorithm according to <a href="https://www.cs.wustl.edu/%7Ecytron/cs531/Resources/Papers/valnum.pdf" rel="nofollow noreferrer">this paper</a> and I would like to verify if certain behaviour of the algorithm is correct. My implementation as is performs the following code transformation on my three address code:</p>
<pre><code>block_a:
  a = /* ... */;
  goto end;

block_b:
  b = /* ... */;
  goto end;

end:
  c = phi(block_a: a, block_b: b);
  x = f(c);
</code></pre>
<p>is transformed to</p>
<pre><code>block_a:
  a = /* ... */;
  x_1 = f(a);
  goto end;

block_b:
  b = /* ... */;
  x_2 = f(b);
  goto end;

end:
  x = phi(block_a: x_1, block_b: x_2);
</code></pre>
<p>where <code>f</code> is some computation. I understand the GVN algorithm tries to &quot;move up&quot; computations along the CFG edges to hopefully merge them and thereby reduce redundancy. But this means it has to introduce additional redundancy (at least temporarily) as shown above. It does not introduce speculative code execution but it does increase the binary size if a computation is duplicated and placed in two blocks instead of just one. Also this moves compare operations away from branch instructions which makes lowering them to efficient machine code unnecessarily hard.</p>
<p>So my question is, is this behaviour intended by the algorithm and I should write another later &quot;rematerialization&quot; pass that undoes some of these transforms or is my GVN implementation flawed?</p>

<compilers><optimization><variables>
Global value numbering implementation
CC BY-SA 4.0
2023-12-22T12:25:57.843Z
I suggest looking at what muchnick's compiler book says about 'partial redundancy elimination'.
Moonchild
# Global value numbering implementation
Posted by: username_0 on 2023-12-22
I wrote a global value numbering algorithm according to this paper and I would like to verify if certain behaviour of the algorithm is correct. My implementation as is performs the following code transformation on my three address code:
block_a:
  a = /* ... */;
  goto end;

block_b:
  b = /* ... */;
  goto end;

end:
  c = phi(block_a: a, block_b: b);
  x = f(c);

is transformed to
block_a:
  a = /* ... */;
  x_1 = f(a);
  goto end;

block_b:
  b = /* ... */;
  x_2 = f(b);
  goto end;

end:
  x = phi(block_a: x_1, block_b: x_2);

where f is some computation. I understand the GVN algorithm tries to "move up" computations along the CFG edges to hopefully merge them and thereby reduce redundancy. But this means it has to introduce additional redundancy (at least temporarily) as shown above. It does not introduce speculative code execution but it does increase the binary size if a computation is duplicated and placed in two blocks instead of just one. Also this moves compare operations away from branch instructions which makes lowering them to efficient machine code unnecessarily hard.
So my question is, is this behaviour intended by the algorithm and I should write another later "rematerialization" pass that undoes some of these transforms or is my GVN implementation flawed?
**Tags:** compilers optimization variables
> **Comments:**
> **username_1**: I suggest looking at what muchnick's compiler book says about 'partial redundancy elimination'.  
---
## 0 answers
