When can we fold copies in SSA?

We are clearly allowed to fold a copy such as

a0 = call foo()
b0 = a0

But what about a program such as

a0 = call foo()
C0 = call bar() // ignore sinking briefly, assume this is used later
if(a0) {
    a1 = C0
a2 = phi(a0, a1)
call print(a2)

We can't fold the a1 = C0 copy because phi(a0, C0) would have altered meaning: both its parameters dominate the phi node and it will always evaluate to C0.

Two more cases:

a0 = call foo();
a1 = call bar();
do {
    a2 = phi(a0, t0)
    call print(a2)
    t0 = a1
} while(...)

Can't fold the t0 = a1 copy for the same reason as the first case (it would become dominated by both parameters).

x0 = call foo()
C0 = call bar() // constant / loop invariant
do {
    a0 = C0
    if(x0) {
        a1 = call baz()
    a2 = phi(a0, a1)
    call print(a2)
} while(...)

Can't fold the a0 = C0 copy here because that makes the phi node (which becomes phi(C0, a1)) invalid across loop iterations. As soon as the x0 branch is taken, the phi(C0, a1) phi node can never evaluate to C0 in subsequent iterations.

Restrictions: I have a couple restrictions in my IR which may help the analysis:

  1. All loops are canonicalized into do-while loops so I can assume they run at least once
  2. The CFG is reducible and a phi node will always have two parameters

What I've tried: Here's the logic I've been able to come up with currently: Cannot fold a copy if

  • The copy (let's call it a = b) has a phi node dependant and a does not dominate the phi but b does.
  • Or the copy is in the same loop as one of its phi node dependants and the replacement (b) dominates the phi.

Question: My question boils down to

  • How can I improve this logic
  • How can I better encapsulate the third case / generalize
  • Or, am I attempting to solve the wrong problem here?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.