divide by a constant power of 2

R=rsc
OCL=32858
CL=32858

3 files changed, 136 insertions, 2 deletions

diff --git a/src/cmd/6g/gg.h b/src/cmd/6g/gg.h
index ce5f6c86c..f9f50cc9d 100644
--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -125,6 +125,8 @@ void	sudoclean(void);
 int	sudoaddable(int, Node*, Addr*);
 void	afunclit(Addr*);
 void	datagostring(Strlit*, Addr*);
+int	powtwo(Node*);
+Type*	tounsigned(Type*);
 
 /*
  * obj.c
diff --git a/src/cmd/6g/ggen.c b/src/cmd/6g/ggen.c
index 64220bc84..4e71f75e5 100644
--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -533,8 +533,8 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)
 void
 cgen_div(int op, Node *nl, Node *nr, Node *res)
 {
-	Node ax, dx, oldax, olddx, n1, n2;
-	int rax, rdx;
+	Node ax, dx, oldax, olddx, n1, n2, n3;
+	int rax, rdx, n, w;
 
 	if(nl->ullman >= UINF) {
 		tempname(&n1, nl->type);
@@ -547,6 +547,86 @@ cgen_div(int op, Node *nl, Node *nr, Node *res)
 		nr = &n2;
 	}
 
+	if(nr->op != OLITERAL)
+		goto longdiv;
+
+	// special cases of mod/div
+	// by a constant
+	n = powtwo(nr);
+	w = nl->type->width*8;
+
+	if(n+1 >= w) {
+		// just sign bit
+		goto longdiv;
+	}
+
+	if(n < 0)
+		goto divbymul;
+
+	if(op == OMOD) {
+		// todo
+		goto longdiv;
+	}
+
+	switch(n) {
+	case 0:
+		// divide by 1
+		cgen(nl, res);
+		return;
+	case 1:
+		// divide by 2
+		regalloc(&n1, nl->type, res);
+		cgen(nl, &n1);
+		if(issigned[nl->type->etype]) {
+			// develop -1 iff nl is negative
+			regalloc(&n2, nl->type, N);
+			gmove(&n1, &n2);
+			nodconst(&n3, nl->type, w-1);
+			gins(optoas(ORSH, nl->type), &n3, &n2);
+			gins(optoas(OSUB, nl->type), &n2, &n1);
+			regfree(&n2);
+		}
+		nodconst(&n2, nl->type, n);
+		gins(optoas(ORSH, nl->type), &n2, &n1);
+		gmove(&n1, res);
+		regfree(&n1);
+		return;
+	default:
+		regalloc(&n1, nl->type, res);
+		cgen(nl, &n1);
+		if(issigned[nl->type->etype]) {
+			// develop (2^k)-1 iff nl is negative
+			regalloc(&n2, nl->type, N);
+			gmove(&n1, &n2);
+			nodconst(&n3, nl->type, w-1);
+			gins(optoas(ORSH, nl->type), &n3, &n2);
+			nodconst(&n3, nl->type, w-n);
+			gins(optoas(ORSH, tounsigned(nl->type)), &n3, &n2);
+			gins(optoas(OADD, nl->type), &n2, &n1);
+			regfree(&n2);
+		}
+		nodconst(&n2, nl->type, n);
+		gins(optoas(ORSH, nl->type), &n2, &n1);
+		gmove(&n1, res);
+		regfree(&n1);
+	}
+	return;
+
+divbymul:
+	switch(simtype[nl->type->etype]) {
+	default:
+		goto longdiv;
+
+	case TINT32:
+	case TUINT32:
+	case TINT64:
+	case TUINT64:
+		break;
+	}
+	// todo
+	goto longdiv;
+
+longdiv:
 	rax = reg[D_AX];
 	rdx = reg[D_DX];
 
diff --git a/src/cmd/6g/gsubr.c b/src/cmd/6g/gsubr.c
index 5ed0a8105..136a8d5ef 100644
--- a/src/cmd/6g/gsubr.c
+++ b/src/cmd/6g/gsubr.c
@@ -1861,3 +1861,55 @@ no:
 	sudoclean();
 	return 0;
 }
+
+int
+powtwo(Node *n)
+{
+	uvlong v, b;
+	int i;
+
+	if(n == N || n->op != OLITERAL || n->type == T)
+		goto no;
+	if(!isint[n->type->etype])
+		goto no;
+
+	v = mpgetfix(n->val.u.xval);
+	b = 1ULL;
+	for(i=0; i<64; i++) {
+		if(b == v)
+			return i;
+		b = b<<1;
+	}
+
+no:
+	return -1;
+}
+
+Type*
+tounsigned(Type *t)
+{
+
+	// this is types[et+1], but not sure
+	// that this relation is immutable
+	switch(t->etype) {
+	default:
+		print("tounsigned: unknown type %T\n", t);
+		break;
+	case TINT:
+		t = types[TUINT];
+		break;
+	case TINT8:
+		t = types[TUINT8];
+		break;
+	case TINT16:
+		t = types[TUINT16];
+		break;
+	case TINT32:
+		t = types[TUINT32];
+		break;
+	case TINT64:
+		t = types[TUINT64];
+		break;
+	}
+	return t;
+}