If-conversion RFC 4 - x86 only (for now), use cmovXX

Replacement of tiny conditional jump graphlets with
conditional move instructions.

Currently enabled only for x86. Arm64 support using cselXX
will be essentially identical.

Adds (internal) frontend sel0/sel1 ops with flag-specific
backend xselXX following jnz implementation pattern.

Testing: standard QBE, cproc, harec, hare, roland

1 files changed, 121 insertions, 0 deletions

diff --git a/ifopt.c b/ifopt.c
new file mode 100644
index 0000000..3e45f52
--- /dev/null
+++ b/ifopt.c
@@ -0,0 +1,121 @@
+#include "all.h"
+
+enum {
+	MaxIns = 2,
+	MaxPhis = 2,
+};
+
+static int
+okbranch(Blk *b)
+{
+	Ins *i;
+	int n;
+
+	n = 0;
+	for (i=b->ins; i<&b->ins[b->nins]; i++)
+		if (i->op != Odbgloc) {
+			if (pinned(i))
+				return 0;
+			if (i->op != Onop)
+				n++;
+		}
+	return n <= MaxIns;
+}
+
+static int
+okjoin(Blk *b)
+{
+	Phi *p;
+	int n;
+
+	n = 0;
+	for (p=b->phi; p; p=p->link) {
+		if (KBASE(p->cls) != 0)
+			return 0;
+		n++;
+	}
+	return n <= MaxPhis;
+}
+
+static int
+okgraph(Blk *ifb, Blk *thenb, Blk *elseb, Blk *joinb)
+{
+	if (joinb->npred != 2 || !okjoin(joinb))
+		return 0;
+	assert(thenb != elseb);
+	if (thenb != ifb && !okbranch(thenb))
+		return 0;
+	if (elseb != ifb && !okbranch(elseb))
+		return 0;
+	return 1;
+}
+
+static void
+convert(Blk *ifb, Blk *thenb, Blk *elseb, Blk *joinb)
+{
+	Ins *ins, sel;
+	Phi *p;
+	uint nins;
+
+	ins = vnew(0, sizeof ins[0], PHeap);
+	nins = 0;
+	addbins(&ins, &nins, ifb);
+	if (thenb != ifb)
+		addbins(&ins, &nins, thenb);
+	if (elseb != ifb)
+		addbins(&ins, &nins, elseb);
+	assert(joinb->npred == 2);
+	if (joinb->phi) {
+		sel = (Ins){
+			.op = Osel0, .cls = Kw,
+			.arg = {ifb->jmp.arg},
+		};
+		addins(&ins, &nins, &sel);
+	}
+	sel = (Ins){.op = Osel1};
+	for (p=joinb->phi; p; p=p->link) {
+		sel.to = p->to;
+		sel.cls = p->cls;
+		sel.arg[0] = phiarg(p, thenb);
+		sel.arg[1] = phiarg(p, elseb);
+		addins(&ins, &nins, &sel);
+	}
+	idup(ifb, ins, nins);
+	ifb->jmp.type = Jjmp;
+	ifb->jmp.arg = R;
+	ifb->s1 = joinb;
+	ifb->s2 = 0;
+	joinb->npred = 1;
+	joinb->pred[0] = ifb;
+	joinb->phi = 0;
+	vfree(ins);
+}
+
+/* eliminate if-then[-else] graphlets
+ * using sel instructions
+ * needs rpo pred use; breaks cfg use
+ */
+void
+ifconvert(Fn *fn)
+{
+	Blk *ifb, *thenb, *elseb, *joinb;
+
+	if (debug['K'])
+		fputs("\n> If-conversion:\n", stderr);
+
+	for (ifb=fn->start; ifb; ifb=ifb->link)
+		if (ifgraph(ifb, &thenb, &elseb, &joinb))
+		if (okgraph(ifb, thenb, elseb, joinb)) {
+			if (debug['K'])
+				fprintf(stderr,
+					"    @%s -> @%s, @%s -> @%s\n",
+					ifb->name, thenb->name, elseb->name,
+					joinb->name);
+			convert(ifb, thenb, elseb, joinb);
+		}
+
+	if (debug['K']) {
+		fprintf(stderr, "\n> After if-conversion:\n");
+		printfn(fn, stderr);
+	}
+}