interp: fix phi instruction

I've discovered a bug in the implementation of the PHI instruction in
the interp package. This commit fixes the bug.

I've found this issue while investigating an issue with maps after
running interp per package.

5 files changed, 93 insertions, 21 deletions

diff --git a/interp/compiler.go b/interp/compiler.go
index e9bf36c3e..20723c646 100644
--- a/interp/compiler.go
+++ b/interp/compiler.go
@@ -25,6 +25,7 @@ type function struct {
 // basicBlock represents a LLVM basic block and contains a slice of
 // instructions. The last instruction must be a terminator instruction.
 type basicBlock struct {
+	phiNodes     []instruction
 	instructions []instruction
 }
 
@@ -346,7 +347,13 @@ func (r *runner) compileFunction(llvmFn llvm.Value) *function {
 				// This error is handled when actually trying to interpret this
 				// instruction (to not trigger on code that won't be executed).
 			}
-			bb.instructions = append(bb.instructions, inst)
+			if inst.opcode == llvm.PHI {
+				// PHI nodes need to be treated specially, see the comment in
+				// interpreter.go for an explanation.
+				bb.phiNodes = append(bb.phiNodes, inst)
+			} else {
+				bb.instructions = append(bb.instructions, inst)
+			}
 		}
 	}
 	return fn
diff --git a/interp/interp_test.go b/interp/interp_test.go
index 29a405dc5..6fabdd519 100644
--- a/interp/interp_test.go
+++ b/interp/interp_test.go
@@ -13,6 +13,7 @@ import (
 func TestInterp(t *testing.T) {
 	for _, name := range []string{
 		"basic",
+		"phi",
 		"slice-copy",
 		"consteval",
 		"map",
diff --git a/interp/interpreter.go b/interp/interpreter.go
index bdaee4e97..73707811c 100644
--- a/interp/interpreter.go
+++ b/interp/interpreter.go
@@ -33,6 +33,50 @@ func (r *runner) run(fn *function, params []value, parentMem *memoryView, indent
 	lastBB := -1 // last basic block is undefined, only defined after a branch
 	var operands []value
 	for instIndex := 0; instIndex < len(bb.instructions); instIndex++ {
+		if instIndex == 0 {
+			// This is the start of a new basic block.
+			// There may be PHI nodes that need to be resolved. Resolve all PHI
+			// nodes before continuing with regular instructions.
+			// PHI nodes need to be treated specially because they can have a
+			// mutual dependency:
+			//   for.loop:
+			//     %a = phi i8 [ 1, %entry ], [ %b, %for.loop ]
+			//     %b = phi i8 [ 3, %entry ], [ %a, %for.loop ]
+			// If these PHI nodes are processed like a regular instruction, %a
+			// and %b are both 3 on the second iteration of the loop because %b
+			// loads the value of %a from the second iteration, while it should
+			// load the value from the previous iteration. The correct behavior
+			// is that these two values swap each others place on each
+			// iteration.
+			var phiValues []value
+			var phiIndices []int
+			for _, inst := range bb.phiNodes {
+				var result value
+				for i := 0; i < len(inst.operands); i += 2 {
+					if int(inst.operands[i].(literalValue).value.(uint32)) == lastBB {
+						incoming := inst.operands[i+1]
+						if local, ok := incoming.(localValue); ok {
+							result = locals[fn.locals[local.value]]
+						} else {
+							result = incoming
+						}
+						break
+					}
+				}
+				if r.debug {
+					fmt.Fprintln(os.Stderr, indent+"phi", inst.operands, "->", result)
+				}
+				if result == nil {
+					panic("could not find PHI input")
+				}
+				phiValues = append(phiValues, result)
+				phiIndices = append(phiIndices, inst.localIndex)
+			}
+			for i, value := range phiValues {
+				locals[phiIndices[i]] = value
+			}
+		}
+
 		inst := bb.instructions[instIndex]
 		operands = operands[:0]
 		isRuntimeInst := false
@@ -121,26 +165,6 @@ func (r *runner) run(fn *function, params []value, parentMem *memoryView, indent
 			if r.debug {
 				fmt.Fprintln(os.Stderr, indent+"switch", operands, "->", currentBB)
 			}
-		case llvm.PHI:
-			var result value
-			for i := 0; i < len(inst.operands); i += 2 {
-				if int(inst.operands[i].(literalValue).value.(uint32)) == lastBB {
-					incoming := inst.operands[i+1]
-					if local, ok := incoming.(localValue); ok {
-						result = locals[fn.locals[local.value]]
-					} else {
-						result = incoming
-					}
-					break
-				}
-			}
-			if r.debug {
-				fmt.Fprintln(os.Stderr, indent+"phi", inst.operands, "->", result)
-			}
-			if result == nil {
-				panic("could not find PHI input")
-			}
-			locals[inst.localIndex] = result
 		case llvm.Select:
 			// Select is much like a ternary operator: it picks a result from
 			// the second and third operand based on the boolean first operand.
diff --git a/interp/testdata/phi.ll b/interp/testdata/phi.ll
new file mode 100644
index 000000000..0a0dad729
--- /dev/null
+++ b/interp/testdata/phi.ll
@@ -0,0 +1,31 @@
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64--linux"
+
[email protected] = global i8 0
[email protected] = global i8 0
+
+define void @runtime.initAll() {
+  call void @main.init()
+  ret void
+}
+
+; PHI nodes always use the value from the previous block, even in a loop. This
+; means that the loop below should swap the values %a and %b on each iteration.
+; Previously there was a bug which resulted in %b getting the value 3 on the
+; second iteration while it should have gotten 1 (from the first iteration of
+; %for.loop).
+define internal void @main.init() {
+entry:
+  br label %for.loop
+
+for.loop:
+  %a = phi i8 [ 1, %entry ], [ %b, %for.loop ]
+  %b = phi i8 [ 3, %entry ], [ %a, %for.loop ]
+  %icmp = icmp eq i8 %a, 3
+  br i1 %icmp, label %for.done, label %for.loop
+
+for.done:
+  store i8 %a, i8* @main.phiNodesResultA
+  store i8 %b, i8* @main.phiNodesResultB
+  ret void
+}
diff --git a/interp/testdata/phi.out.ll b/interp/testdata/phi.out.ll
new file mode 100644
index 000000000..ea587bd16
--- /dev/null
+++ b/interp/testdata/phi.out.ll
@@ -0,0 +1,9 @@
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64--linux"
+
[email protected] = local_unnamed_addr global i8 3
[email protected] = local_unnamed_addr global i8 1
+
+define void @runtime.initAll() local_unnamed_addr {
+  ret void
+}