Evaluation of phi nodes.
Created by: wks
Currently all instructions are evaluated sequentially, including PHI nodes. Theoretically all PHI nodes in the beginning of a particular basic block should be evaluated at the same time.
If a subsequent PHI node depends on a previous PHI node, the value of the previous PHI node is updated before the subsequent PHI node can get its old value. This causes error in some programs.
int swaps(int x, int y, int c) {
for(int i=0; i<c; i++) {
int tmp = x; x = y; y = tmp;
}
return x;
}
SSA form:
.funcdef .... (%x %y %c) {
%entry:
BRANCH %head
%head:
%x1 = PHI { %entry: %x; %body: %y1; }
%y1 = PHI { %entry: %y; %body: %x1; }
%i1 = PHI { %entry: @I64_0; %body: %i2; }
%lt = SLT %i1 %c
BRANCH2 %lt %body %exit
%body:
%i2 = ADD %i1 @I64_1;
BRANCH %head
%exit:
RET %x1
}
Given arguments x=1, y=2, c=3. When entering head from entry, %x1 = 1, %y1 = 2
. When branching back from body to head, the value of %x1
and %y1
should be swapped. However, the current implementation evaluates the PHI nodes one at a time.
// %body -> %head
%x1 = %y1 = 2
%y1 = %x1 = 2 // should be the old %x1, which was 1
The semantic of the Mu virtual machine itself should also be made clearer accordingly.