scc

commit 48b664b106b3aadb1b8b2db95bfb1da0fe7daa0b
parent 2cad94c36488366e50eaacc2fd669760a1b9020a
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date:   Wed, 11 Jan 2023 11:45:41 +0100

cc1: Reduce modulo operations to and operations

When a modulo operation is done using a power of two
then it is possible to implement it using a bitwise
and.

Diffstat:
M
src/cmd/cc/cc1/cc1.h
 | 
1
+
M
src/cmd/cc/cc1/expr.c
 | 
26
++++++++++++++++++++++++++
M
src/cmd/cc/cc1/fold.c
 | 
44
++++++++++++++++++++++++++++++++++++--------

3 files changed, 63 insertions(+), 8 deletions(-)
diff --git a/src/cmd/cc/cc1/cc1.h b/src/cmd/cc/cc1/cc1.h
@@ -497,6 +497,7 @@ extern Node *constexpr(void), *condexpr(int neg), *expr(void);
 extern int isnodecmp(int op);
 extern int negop(int op);
 extern int cmpnode(Node *np, TUINT val);
+extern int power2node(Node *, int *);
 
 /* init.c */
 extern void initializer(Symbol *sym, Type *tp);
diff --git a/src/cmd/cc/cc1/expr.c b/src/cmd/cc/cc1/expr.c
@@ -9,6 +9,32 @@
 #define XCHG(lp, rp, np) (np = lp, lp = rp, rp = np)
 
 int
+power2node(Node *np, int *log)
+{
+	int n;
+	TUINT u;
+	Symbol *sym;
+
+	if (!np || !(np->flags & NCONST) || !np->sym)
+		return 0;
+
+	sym = np->sym;
+	if (sym->type->op != INT)
+		return 0;
+
+	n = 0;
+	for (u = sym->u.u; u; u >>= 1) {
+		if (u & 1)
+			n++;
+	}
+
+	if (log)
+		*log = n;
+
+	return n == 1;
+}
+
+int
 cmpnode(Node *np, TUINT val)
 {
 	Symbol *sym;
diff --git a/src/cmd/cc/cc1/fold.c b/src/cmd/cc/cc1/fold.c
@@ -586,7 +586,6 @@ identity(Node *np)
 		return np;
 	case OMOD:
 		/* i % 1  => i,1 */
-		/* TODO: i % 2^n => i & n-1 */
 		if (isoner)
 			goto change_to_comma;
 	default:
@@ -634,21 +633,45 @@ foldternary(Node *np)
 	return np;
 }
 
-
 static Node *xsimplify(Node *);
 
+static void
+reduce(Node *np)
+{
+	Node *lp = np->left, *rp = np->right;
+	Node *aux, *aux2;
+	int op = np->op;
+
+	switch (op) {
+	case OMOD:
+		/* i % 2^n => i & n-1 */
+		if (power2node(rp, NULL)) {
+			np->op = OBAND;
+			rp->sym->u.u--;
+			break;
+		}
+		return;
+	default:
+		return;
+	}
+
+	DBG("FOLD reduce %d->%d", op, np->op);
+}
+
 /* TODO: fold OCOMMA */
 static Node *
 xxsimplify(Node *np)
 {
-	Node *p, *l, *r;
+	int op;
 
 	np->left = xsimplify(np->left);
 	np->right = xsimplify(np->right);
 
-	switch (np->op) {
+repeat:
+	switch (op = np->op) {
 	case OASK:
-		return foldternary(np);
+		np = foldternary(np);
+		break;
 	case OCALL:
 	case OPAR:
 	case OSYM:
@@ -663,7 +686,7 @@ xxsimplify(Node *np)
 	case OA_AND:
 	case OA_XOR:
 	case OA_OR:
-		return np;
+		break;
 	case OSNEG:
 	case OCPL:
 	case OADDR:
@@ -675,13 +698,18 @@ xxsimplify(Node *np)
 		assert(!np->right);
 		np = foldunary(np);
 		np = fold(np);
-		return np;
+		break;
 	default:
 		commutative(np);
 		np = fold(np);
 		np = identity(np);
-		return np;
+		reduce(np);
+		break;
 	}
+
+	if (op != np->op)
+		goto repeat;
+	return np;
 }
 
 static Node *