From 17352b8b8d945a556eaae3f74d486ed8a0f51631 Mon Sep 17 00:00:00 2001
From: ceriel <none@none>
Date: Wed, 20 Nov 1991 15:53:11 +0000
Subject: [PATCH] Added code to optimize multiplies with constants

---
 util/opt/ext.h      |   2 +
 util/opt/main.c     |   7 +-
 util/opt/peephole.c | 153 +++++++++++++++++++++++++++++++++++++++++++-
 util/opt/proto.make |   2 +-
 util/opt/var.c      |   2 +
 5 files changed, 163 insertions(+), 3 deletions(-)

diff --git a/util/opt/ext.h b/util/opt/ext.h
index 5eba32a4d..a389eb428 100644
--- a/util/opt/ext.h
+++ b/util/opt/ext.h
@@ -11,6 +11,8 @@ extern	unsigned linecount;
 extern	int	prodepth;
 extern	bool	Lflag;
 extern	bool	nflag;
+extern	int	repl_muls;
+extern	bool	repl_longmuls;
 extern	byte	em_flag[];
 extern	line_p	instrs,pseudos;
 extern	FILE	*outfile;
diff --git a/util/opt/main.c b/util/opt/main.c
index 33b0ea89a..74d42b555 100644
--- a/util/opt/main.c
+++ b/util/opt/main.c
@@ -28,7 +28,7 @@ main(argc,argv) int argc; char *argv[]; {
 	while (argc-->1 && **++argv == '-')
 		flags(*argv);
 	if (argc>1) {
-		fprintf(stderr,"Usage: %s [-Ln] [name]\n",progname);
+		fprintf(stderr,"Usage: %s [-Ln] [-m<num>] [name]\n",progname);
 		exit(-1);
 	}
 	if (argc)
@@ -47,6 +47,11 @@ flags(s) register char *s; {
 		switch(*s) {
 		case 'L':	Lflag = TRUE; break;
 		case 'n':	nflag = TRUE; break;
+		case 'm':	if (*(s+1) == 'l') {
+					s++;
+					repl_longmuls = TRUE;
+				}
+				repl_muls = atoi(s+1); break;
 		}
 }
 
diff --git a/util/opt/peephole.c b/util/opt/peephole.c
index 2f117d5d2..3df804144 100644
--- a/util/opt/peephole.c
+++ b/util/opt/peephole.c
@@ -608,7 +608,30 @@ basicblock(alpp) line_p *alpp; {
 
 	lpp = alpp; madeopt = FALSE;
 	while ((*lpp) != (line_p) 0 && ((*lpp)->l_instr&BMASK) != op_lab) {
-		lp = *lpp; next = &lp->l_next;
+		lp = *lpp;
+		if (repl_muls) {
+			line_p b_repl, e_repl;
+			int cnt = repl_mul(lp, &b_repl, &e_repl);
+
+			if (cnt > 0 && cnt <= repl_muls) {
+				*lpp = b_repl;
+				e_repl->l_next = lp->l_next->l_next;
+				oldline(lp->l_next);
+				oldline(lp);
+				lp = b_repl;
+				madeopt = TRUE;
+			}
+			else {
+				while (b_repl != (line_p) 0) {
+					line_p n = b_repl->l_next;
+
+					oldline(b_repl);
+					b_repl = n;
+				}
+			}
+		}
+
+		next = &lp->l_next;
 		hash[0] = lp->l_instr&BMASK;
 		lp=lp->l_next;
 		if (lp != (line_p) 0) {
@@ -655,3 +678,131 @@ basicblock(alpp) line_p *alpp; {
 	}
 	return madeopt;
 }
+
+repl_mul(lp, b, e)
+	register line_p	lp;
+	line_p	*b, *e;
+{
+	register line_p next = lp->l_next;
+	int	ins;
+	int	sz;
+	unsigned long	n;
+	int	n0, n1;
+  	int	virgin = 1;
+	int	retval = 0;
+
+	*b = 0;
+	if (! next) return 0;
+	if ((ins = (next->l_instr & BMASK)) != op_mli && ins != op_mlu) {
+		return 0;
+	}
+	if ((ins = (lp->l_instr & BMASK)) != op_loc && ins != op_ldc) {
+		return 0;
+	}
+	switch(next->l_optyp) {
+	case OPNO:
+		return 0;
+	case OPSHORT:
+		sz = next->l_a.la_short;
+		break;
+#ifdef LONGOFF
+	case OPOFFSET:
+		sz = next->l_a.la_offset;
+		break;
+#endif
+	default:
+		sz = (next->l_optyp & BMASK) - Z_OPMINI;
+		break;
+	}
+	if (ins == op_loc && sz != wordsize) return 0;
+	if (ins == op_ldc && sz != 2*wordsize) return 0;
+	if (! repl_longmuls && sz != wordsize) return 0;
+	switch(lp->l_optyp) {
+	case OPSHORT:
+		n = (long) lp->l_a.la_short;
+		break;
+#ifdef LONGOFF
+	case OPOFFSET:
+		n = lp->l_a.la_offset;
+		break;
+#endif
+	default:
+		n = (long)((lp->l_optyp & BMASK) - Z_OPMINI);
+		break;
+	}
+
+#define newinstr(res, opcode, val)	(*(res) = newline((short)(val)+Z_OPMINI), (*(res))->l_instr = (opcode))
+
+  	while (n) {
+		/* first find "0*1*$" in n */
+		for (n1 = 0; n & 1; n>>=1) ++n1;	/* count "1" bits */
+		if (n)
+			for (n0 = 0; !(n & 1); n>>=1)	/* count "0" bits */
+				++n0;
+		else
+			n0 = 0;
+
+		if (n1 == 0) {
+			if (n0) {
+				newinstr(b, op_loc, n0); b = &((*b)->l_next);
+				newinstr(b, op_slu, sz); b = &((*b)->l_next);
+				retval++;
+			}
+		} else if (n1 == 1) {
+			if (virgin) {
+				newinstr(b, op_dup, sz); b = &((*b)->l_next);
+				virgin = 0;
+			}
+			else {
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
+				newinstr(b, op_asp, sz); b = &((*b)->l_next);
+				newinstr(b, op_adu, sz); b = &((*b)->l_next);
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				retval++;
+			}
+			if (n) {
+				newinstr(b, op_loc, n0+n1); b = &((*b)->l_next);
+				newinstr(b, op_slu, sz); b = &((*b)->l_next);
+				retval++;
+			}
+		} else {
+			if (virgin) {
+				newinstr(b, op_dup, sz); b = &((*b)->l_next);
+				newinstr(b, op_loc, 0); b = &((*b)->l_next);
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				virgin = 0;
+			}
+			else {
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
+				newinstr(b, op_asp, sz); b = &((*b)->l_next);
+				newinstr(b, op_sbu, sz); b = &((*b)->l_next);
+				retval++;
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				newinstr(b, op_loc, n1); b = &((*b)->l_next);
+				newinstr(b, op_slu, sz); b = &((*b)->l_next);
+				retval++;
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
+				newinstr(b, op_asp, sz); b = &((*b)->l_next);
+				newinstr(b, op_adu, sz); b = &((*b)->l_next);
+				newinstr(b, op_exg, sz); b = &((*b)->l_next);
+				retval++;
+			}
+			if (n0) {
+				newinstr(b, op_loc, n0); b = &((*b)->l_next);
+				newinstr(b, op_slu, sz); b = &((*b)->l_next);
+				retval++;
+			}
+		}
+  	}
+	newinstr(b, op_asp, sz);
+  	if (virgin) {
+		b = &((*b)->l_next);
+		newinstr(b, sz == wordsize ? op_loc : op_ldc, 0);
+  	}
+	*e = *b;
+	return retval == 0 ? 1 : retval;
+#undef newinstr
+}
diff --git a/util/opt/proto.make b/util/opt/proto.make
index 1fc06cc04..a4b5d5587 100644
--- a/util/opt/proto.make
+++ b/util/opt/proto.make
@@ -23,7 +23,7 @@ CFLAGS= -DNDEBUG $(INCLUDES) $(COPTIONS)
 UCFLAGS= -DNDEBUG $(INCLUDES) $(UCOPTIONS)
 LDFLAGS=$(LDOPTIONS)
 ULDFLAGS=$(ULDOPTIONS)
-LINTFLAGS=$(INCLUDES) -DNDEBUG $(LINTOPTIONS)
+LINTFLAGS=$(INCLUDES) -DNDEBUG -DNORCSID $(LINTOPTIONS)
 CPP=$(UTIL_HOME)/lib.bin/cpp
 
 all:	opt opt2
diff --git a/util/opt/var.c b/util/opt/var.c
index 6f9f70e24..ace670a2b 100644
--- a/util/opt/var.c
+++ b/util/opt/var.c
@@ -20,6 +20,8 @@ unsigned linecount = 0;		/* "line"number for errormessages */
 int	prodepth  = 0;		/* Level of nesting */
 bool	Lflag	  = 0;		/* make library module */
 bool	nflag	  = 0;		/* do not optimize */
+int	repl_muls = 0;		/* max # of shifts/adds for replacing muls */
+bool	repl_longmuls = 0;	/* replacing longmuls as well? */
 line_p	instrs,pseudos;		/* pointers to chains */
 sym_p	symhash[NSYMHASH];	/* array of pointers to chains */
 FILE	*outfile;
-- 
2.34.1