Repository: mmcloughlin/avo
Pull request #80 (2019-04-14 17:22:19)

pass: add PruneSelfMoves cleanup pass
Issue #76 showed that in some cases natural use of abstraction in avo programs can lead to redundant move instructions, specifically self-moves such as `MOVQ AX, AX`. This does not produce incorrect code but it is incorrect and inelegant.

This diff introduces a PruneSelfMoves pass that removes such unnecessary instructions.

codecov-io: # [Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=h1) Report
> Merging [#80](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=desc) into [master](https://codecov.io/gh/mmcloughlin/avo/commit/5d3176b111e16ae92514c410a718e55459588db1?src=pr&el=desc) will **increase** coverage by `0.02%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/mmcloughlin/avo/pull/80/graphs/tree.svg?width=650&token=DaOLKxzdQS&height=150&src=pr)](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master      #80      +/-   ##
==========================================
+ Coverage   76.01%   76.03%   +0.02%     
==========================================
  Files          51       52       +1     
  Lines       31136    31159      +23     
==========================================
+ Hits        23669    23693      +24     
+ Misses       7367     7366       -1     
  Partials      100      100
```

| Flag | Coverage Δ | |
|---|---|---|
| #integration | `6.16% <100%> (+0.07%)` | :arrow_up: |
| #unittests | `74.26% <100%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pass/pass.go](https://codecov.io/gh/mmcloughlin/avo/pull/80/diff?src=pr&el=tree#diff-cGFzcy9wYXNzLmdv) | `60% <ø> (ø)` | :arrow_up: |
| [pass/cleanup.go](https://codecov.io/gh/mmcloughlin/avo/pull/80/diff?src=pr&el=tree#diff-cGFzcy9jbGVhbnVwLmdv) | `100% <100%> (ø)` | |
| [operand/checks.go](https://codecov.io/gh/mmcloughlin/avo/pull/80/diff?src=pr&el=tree#diff-b3BlcmFuZC9jaGVja3MuZ28=) | `98.98% <0%> (+1.01%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=footer). Last update [5d3176b...b493569](https://codecov.io/gh/mmcloughlin/avo/pull/80?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/pass/cleanup.go b/pass/cleanup.go
new file mode 100644
index 0000000..fd3821f
--- /dev/null
+++ b/pass/cleanup.go
@@ -0,0 +1,50 @@
+package pass
+
+import (
+	"github.com/mmcloughlin/avo/ir"
+	"github.com/mmcloughlin/avo/operand"
+)
+
+// PruneSelfMoves removes move instructions from one register to itself.
+func PruneSelfMoves(fn *ir.Function) error {
+	return removeinstructions(fn, func(i *ir.Instruction) bool {
+		switch i.Opcode {
+		case "MOVB", "MOVW", "MOVL", "MOVQ":
+		default:
+			return false
+		}
+
+		return operand.IsRegister(i.Operands[0]) && operand.IsRegister(i.Operands[1]) && i.Operands[0] == i.Operands[1]
+	})
+}
+
+// removeinstructions deletes instructions from the given function which match predicate.
+func removeinstructions(fn *ir.Function, predicate func(*ir.Instruction) bool) error {
+	// Removal of instructions has the potential to invalidate CFG structures.
+	// Clear them to prevent accidental use of stale structures after this pass.
+	invalidatecfg(fn)
+
+	for i := 0; i < len(fn.Nodes); i++ {
+		n := fn.Nodes[i]
+
+		inst, ok := n.(*ir.Instruction)
+		if !ok || !predicate(inst) {
+			continue
+		}
+
+		copy(fn.Nodes[i:], fn.Nodes[i+1:])
+		fn.Nodes[len(fn.Nodes)-1] = nil
+		fn.Nodes = fn.Nodes[:len(fn.Nodes)-1]
+	}
+
+	return nil
+}
+
+// invalidatecfg clears CFG structures.
+func invalidatecfg(fn *ir.Function) {
+	fn.LabelTarget = nil
+	for _, i := range fn.Instructions() {
+		i.Pred = nil
+		i.Succ = nil
+	}
+}
diff --git a/pass/pass.go b/pass/pass.go
index c184465..b059588 100644
--- a/pass/pass.go
+++ b/pass/pass.go
@@ -18,6 +18,7 @@ var Compile = Concat(
 	FunctionPass(BindRegisters),
 	FunctionPass(VerifyAllocation),
 	Func(IncludeTextFlagHeader),
+	FunctionPass(PruneSelfMoves),
 )
 
 // Interface for a processing pass.


Test patch:
diff --git a/pass/cleanup_test.go b/pass/cleanup_test.go
new file mode 100644
index 0000000..021cd5e
--- /dev/null
+++ b/pass/cleanup_test.go
@@ -0,0 +1,44 @@
+package pass_test
+
+import (
+	"reflect"
+	"testing"
+
+	"github.com/mmcloughlin/avo/build"
+	"github.com/mmcloughlin/avo/ir"
+	"github.com/mmcloughlin/avo/operand"
+	"github.com/mmcloughlin/avo/pass"
+	"github.com/mmcloughlin/avo/reg"
+)
+
+func TestPruneSelfMoves(t *testing.T) {
+	// Construct a function containing a self-move.
+	ctx := build.NewContext()
+	ctx.Function("add")
+	ctx.MOVQ(operand.U64(1), reg.RAX)
+	ctx.MOVQ(operand.U64(2), reg.RCX)
+	ctx.MOVQ(reg.RAX, reg.RAX) // self move
+	ctx.MOVQ(reg.RCX, reg.R8)
+	ctx.ADDQ(reg.R8, reg.RAX)
+
+	// Build the function without the pass and save the nodes.
+	fn := BuildFunction(t, ctx)
+	pre := append([]ir.Node{}, fn.Nodes...)
+
+	// Apply the pass.
+	if err := pass.PruneSelfMoves(fn); err != nil {
+		t.Fatal(err)
+	}
+
+	// Confirm the self-move was removed and everything else was untouched.
+	expect := []ir.Node{}
+	for i, n := range pre {
+		if i != 2 {
+			expect = append(expect, n)
+		}
+	}
+
+	if !reflect.DeepEqual(fn.Nodes, expect) {
+		t.Fatal("unexpected result from self-move pruning")
+	}
+}
diff --git a/pass/reg_test.go b/pass/reg_test.go
index f19d7b3..353a80f 100644
--- a/pass/reg_test.go
+++ b/pass/reg_test.go
@@ -3,7 +3,6 @@ package pass_test
 import (
 	"testing"
 
-	"github.com/mmcloughlin/avo/internal/test"
 	"github.com/mmcloughlin/avo/ir"
 	"github.com/mmcloughlin/avo/reg"
 
@@ -58,28 +57,5 @@ func AssertRegistersMatchSet(t *testing.T, rs []reg.Register, s reg.Set) {
 }
 
 func ConstructLiveness(t *testing.T, ctx *build.Context) *ir.Function {
-	f, err := ctx.Result()
-	if err != nil {
-		build.LogError(test.Logger(t), err, 0)
-		t.FailNow()
-	}
-
-	fns := f.Functions()
-	if len(fns) != 1 {
-		t.Fatalf("expect 1 function")
-	}
-	fn := fns[0]
-
-	passes := []func(*ir.Function) error{
-		pass.LabelTarget,
-		pass.CFG,
-		pass.Liveness,
-	}
-	for _, p := range passes {
-		if err := p(fn); err != nil {
-			t.Fatal(err)
-		}
-	}
-
-	return fn
+	return BuildFunction(t, ctx, pass.LabelTarget, pass.CFG, pass.Liveness)
 }
diff --git a/pass/util_test.go b/pass/util_test.go
new file mode 100644
index 0000000..7929e40
--- /dev/null
+++ b/pass/util_test.go
@@ -0,0 +1,36 @@
+package pass_test
+
+import (
+	"testing"
+
+	"github.com/mmcloughlin/avo/build"
+	"github.com/mmcloughlin/avo/internal/test"
+	"github.com/mmcloughlin/avo/ir"
+	"github.com/mmcloughlin/avo/pass"
+)
+
+// BuildFunction is a helper to compile a build context containing a single
+// function and (optionally) apply a list of FunctionPasses to it.
+func BuildFunction(t *testing.T, ctx *build.Context, passes ...pass.FunctionPass) *ir.Function {
+	t.Helper()
+
+	f, err := ctx.Result()
+	if err != nil {
+		build.LogError(test.Logger(t), err, 0)
+		t.FailNow()
+	}
+
+	fns := f.Functions()
+	if len(fns) != 1 {
+		t.Fatalf("expect 1 function")
+	}
+	fn := fns[0]
+
+	for _, p := range passes {
+		if err := p(fn); err != nil {
+			t.Fatal(err)
+		}
+	}
+
+	return fn
+}
diff --git a/tests/fixedbugs/issue76/asm.go b/tests/fixedbugs/issue76/asm.go
new file mode 100644
index 0000000..72ce4d5
--- /dev/null
+++ b/tests/fixedbugs/issue76/asm.go
@@ -0,0 +1,29 @@
+// +build ignore
+
+package main
+
+import (
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/reg"
+)
+
+func main() {
+	TEXT("Issue76", NOSPLIT, "func(x, y uint64) uint64")
+	x := Load(Param("x"), GP64())
+	y := Load(Param("y"), GP64())
+	s := add(x, y)
+	Store(s, ReturnIndex(0))
+	RET()
+	Generate()
+}
+
+// add generates code to add x and y. The intent here is to demonstrate how a
+// natural subroutine in avo typically requires temporary registers, which in
+// turn can be "optimized out" by the register allocator and result in redundant
+// self-moves.
+func add(x, y Register) Register {
+	s := GP64()
+	MOVQ(x, s) // likely to become a self move
+	ADDQ(y, s)
+	return s
+}
diff --git a/tests/fixedbugs/issue76/doc.go b/tests/fixedbugs/issue76/doc.go
new file mode 100644
index 0000000..70c58d9
--- /dev/null
+++ b/tests/fixedbugs/issue76/doc.go
@@ -0,0 +1,4 @@
+// Package issue76 deliberately produces redundant MOV instructions.
+//
+// The intent is to confirm redundant self-move instructions are correctly removed.
+package issue76
diff --git a/tests/fixedbugs/issue76/issue76.s b/tests/fixedbugs/issue76/issue76.s
new file mode 100644
index 0000000..1e838be
--- /dev/null
+++ b/tests/fixedbugs/issue76/issue76.s
@@ -0,0 +1,11 @@
+// Code generated by command: go run asm.go -out issue76.s -stubs stub.go. DO NOT EDIT.
+
+#include "textflag.h"
+
+// func Issue76(x uint64, y uint64) uint64
+TEXT ·Issue76(SB), NOSPLIT, $0-24
+	MOVQ x+0(FP), AX
+	MOVQ y+8(FP), CX
+	ADDQ CX, AX
+	MOVQ AX, ret+16(FP)
+	RET
diff --git a/tests/fixedbugs/issue76/issue76_test.go b/tests/fixedbugs/issue76/issue76_test.go
new file mode 100644
index 0000000..2a6190e
--- /dev/null
+++ b/tests/fixedbugs/issue76/issue76_test.go
@@ -0,0 +1,15 @@
+package issue76
+
+import (
+	"testing"
+	"testing/quick"
+)
+
+//go:generate go run asm.go -out issue76.s -stubs stub.go
+
+func TestIssue76(t *testing.T) {
+	expect := func(x, y uint64) uint64 { return x + y }
+	if err := quick.CheckEqual(Issue76, expect, nil); err != nil {
+		t.Fatal(err)
+	}
+}
diff --git a/tests/fixedbugs/issue76/stub.go b/tests/fixedbugs/issue76/stub.go
new file mode 100644
index 0000000..932f21b
--- /dev/null
+++ b/tests/fixedbugs/issue76/stub.go
@@ -0,0 +1,5 @@
+// Code generated by command: go run asm.go -out issue76.s -stubs stub.go. DO NOT EDIT.
+
+package issue76
+
+func Issue76(x uint64, y uint64) uint64