--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mc-switch.c	Sun Jun 06 20:19:36 2004 +0900
@@ -0,0 +1,344 @@
+/* Micro-C Switch Code generation Part */
+/* $Id$ */
+
+#define EXTERN extern
+#include "mc.h"
+#include "mc-code.h"
+#include "mc-codegen.h"
+
+#if CASE_CODE
+
+extern void genswitch(int cslist,int cslabel,int dlabel);
+
+/*
+  value label pair
+      cslist = list3(value,next,label)  label==0 means skip
+  continuous cslist
+      chunks:  list4(cslist,next,delta,list3(count,min,max))
+  mergeable chunks count list
+      merge:   list4(continuous number of chunk,next,delta,case_count);
+  index list
+      index:   list4(label,next,max,min);
+ */
+
+#define chunk_max(chunks) caddr(cadddr(chunks))
+#define chunk_min(chunks) cadr(cadddr(chunks))
+#define index_max(index)  caddr(index)
+#define index_min(index)  cadddr(index)
+
+/*
+   group continous case value
+ */
+
+static int
+make_chunk(int cslist)
+{
+    int delta,delta1,list,p,count;
+    // cslist is already sorted
+    delta = 0;
+    list = list4(cslist,0,1,list3(0,car(cslist) /* min */,0)); 
+    count=1;
+    for(p=0;cadr(cslist);cslist = cadr(cslist),count++) {
+        // compute new delta
+	delta1 = car(cadr(cslist))-car(cslist);
+        // empty case
+	if (!caddr(cslist)) count--;
+	if (delta==0) {
+            // 2nd element
+	    caddr(list) = delta = delta1;
+	    if (p) cadr(p)=0;  // terminate previous chunk
+	} else if (delta1!=delta) {
+	    // not contiguous, start new list
+	    caddr(cadddr(list)) = car(cslist);      // max
+	    car(cadddr(list)) = count; count=0;
+            delta = 0;
+	    list = list4(cadr(cslist),list,1,list3(0,0,0));
+	    cadr(cadddr(list)) = car(cadr(cslist)); // min
+            // prepare terminate point for next turn
+	    p=cslist;
+	}
+    }
+    if (p) cadr(p)=0;  // terminate previous chunk
+    car(cadddr(list)) = count;
+    caddr(cadddr(list)) = car(cslist);   // max
+    return list;
+}
+
+#define CASE_MERGE_RATE 70
+
+static int gcd(int i,int j)
+{
+    int k;
+    if (i<j) { k=i; i=j; j=k;}
+    for(;;) {
+	if ((k=i%j)==0) return j;
+	i = j; j = k;
+    }
+}
+
+/*
+    check two chunks are mergeable or not.
+ */
+
+static int
+merge_chunk_p(int *delta,int max,int min,int *count,int delta1,int count1) 
+{
+    int range = max-min;
+    int g;
+    // compute possible merge delta
+    g = gcd(*delta,delta1);
+    g = gcd(g,range);
+    range /= g;
+    *count = count1 = count1+*count;
+    *delta = g;
+#if 1
+    if (count1*128>(range*128*CASE_MERGE_RATE/100)) {
+	printf("# min %d, max %d, count %d, delta %d, rate %g t=%d\n",
+	    min,max,count1,g,
+		 ((double)count1)*100.0/range,
+	       count1*128>(range*128*CASE_MERGE_RATE/100)
+	);
+    }
+#endif
+    //    count/((max-min)/delta) > 0.8
+    return count1*128>(range*128*CASE_MERGE_RATE/100);
+}
+
+
+static int
+merge_chunk(int chunks)
+{
+    int list = chunks;
+    int tail,last,max,min,i;
+    int count,c_count,p,widest,delta=1;
+    int merge = 0;
+    while(cadr(list)) {
+	p = cadddr(list);
+	c_count = count = car(p); max=caddr(p);
+	widest = 1; last = list;
+	delta = caddr(list);
+        // check possible merge against the end of the chunks
+	for(i=1,tail=cadr(list);cadr(tail); tail=cadr(tail),i++) {
+	    p = cadddr(tail);
+	    min = cadr(p);
+	    if (merge_chunk_p(&delta,max,min,&count,caddr(tail),car(p))) {
+                // It is mergeable.
+		widest = i+1; last = tail; c_count=count;
+	    }
+	}
+	merge = list4(widest,merge,delta,c_count);
+        // skip merged chunks
+	list = cadr(last);
+    }
+    // last one can remain.
+    if (list) merge = list4(1,merge,caddr(list),car(cadddr(list)));
+    return merge;
+}
+
+static int
+table_jump(int count,int delta,int cslist)
+{
+    int list;
+    for(;count-->0;cslist=cadr(cslist)) {
+	list = car(cslist);
+	printf("# table cases delta=%d count=%d min=%d max=%d\n",
+		caddr(cslist),car(cadddr(cslist)),
+				cadr(cadddr(cslist)),caddr(cadddr(cslist))
+		);
+	for(;list; list=cadr(list)) {
+	    if (caddr(list))
+		cmpdimm(car(list),csvalue1,caddr(list),0);
+	}
+    }
+    return cslist;
+}
+
+static int
+cascade_compare(int count,int cslist)
+{
+    int list;
+    for(;count-->0;cslist=cadr(cslist)) {
+	list = car(cslist);
+	printf("# cascade cases delta=%d count=%d min=%d max=%d\n",
+		caddr(cslist),car(cadddr(cslist)),
+				cadr(cadddr(cslist)),caddr(cadddr(cslist))
+		);
+	for(;list; list=cadr(list)) {
+	    if (caddr(list))
+		cmpdimm(car(list),csvalue1,caddr(list),0);
+                //      value     register  label    mode
+	}
+    }
+    return cslist;
+}
+
+#define CASE_TABLE_COUNT 10
+#define CASE_INDEX_COUNT 10
+
+
+/*
+     generate index jmp
+ */
+
+static void
+switch_index_jmp(int index,int label)
+{
+    int value = car(car(caddr(caddr(index))));
+    cmpdimm(value,csvalue1,label,LT);
+    //      value     register  label    mode
+}
+
+/*
+     generate leaf index branch
+ */
+
+static int
+switch_make_index_leaf(int count,int index)
+{
+    for(;count-- !=0 && cadr(index);index=cadr(index)) {
+	switch_index_jmp(
+		cadr(index),      /* next max */
+		car(caddr(index)) /*label*/ );
+    }
+    if (!cadr(index)) {
+	// don't check max boundary
+	jmp(car(caddr(index)));
+	return 0;
+    }
+    if (count!=0) error(-1);
+    return index;
+}
+
+/*
+     generate index switch branch (no table).
+     if necessary generate higher index.
+ */
+
+static void
+switch_make_index(int index0,int count,int cslabel)
+{
+    int index=0;
+    int icount=0;
+    int l,min,max;
+    while (index0 && count > CASE_INDEX_COUNT) {
+	l = backdef();
+	min = index_min(index0);
+	index0=switch_make_index_leaf(CASE_INDEX_COUNT,index0);
+	max = index_min(index0);
+	index = list4(l,index,max,min);
+	count-=CASE_INDEX_COUNT;
+	icount++;
+    }
+    if (index) {
+	switch_make_index(reverse0(index),icount,cslabel);
+	if (dlabel) jmp(dlabel);
+    } else {
+	fwddef(cslabel);
+	switch_make_index_leaf(-1,index0);
+	if (dlabel) jmp(dlabel);
+    }
+}
+
+/*
+     generate leaf switch branch or table jump
+ */
+
+static int
+switch_leaf(int count,int merge,int cslist)
+{
+    for(;count-- !=0 && merge;merge=cadr(merge)) {
+	printf("# merge count %d delta %d c_count %d\n",
+		car(merge),caddr(merge),cadddr(merge));
+	if (cadddr(merge)>CASE_TABLE_COUNT)
+	    cslist = table_jump(car(merge),caddr(merge),cslist);
+	else
+	    cslist = cascade_compare(car(merge),cslist);
+    }
+    return cslist;
+}
+
+/*
+    make index if necessary or
+    generate case branch or table jump 
+ */
+
+static void
+switch_index(int merge,int chunks,int cslabel,int dlabel,int gmax)
+{
+    int m,l,max,min;
+    int chnkcnt = 0;
+    int icount = 0;
+    int count = 0;
+    int index = 0;
+    for(m=merge;m;m=cadr(m)) {
+        chnkcnt++;
+	count += cadddr(m);
+	if (count > CASE_INDEX_COUNT || (index && !cadr(m))) {
+	    icount++;
+	    min = car(car(chunks));
+	    l = backdef();
+	    chunks= switch_leaf(chnkcnt,merge,chunks);
+	    max = chunks?car(car(chunks)):gmax;
+            index = list4(l,index,max,min);
+	    merge = cadr(m); count = 0; chnkcnt = 0;
+	    if (dlabel) jmp(dlabel);
+	}
+    }
+    if (index) {
+	index = reverse0(index);
+        // check lower bound
+	switch_index_jmp(index,dlabel?dlabel:blabel); 
+	switch_make_index(index,icount,cslabel);
+	if (dlabel) jmp(dlabel);
+    } else {
+	fwddef(cslabel);
+	switch_leaf(-1,merge,chunks);
+	if (dlabel) jmp(dlabel);
+    }
+}
+
+/*  generate switch table, index, cascading branch */
+
+
+void
+genswitch(int cslist,int cslabel,int dlabel)
+{
+    int chunks,merge,gmax;
+    int i,j;
+#if 0
+    for(i=cslist;i;i=cadr(i)) {
+	printf("# case %d L_%d\n",car(i),caddr(i));
+    }
+#endif
+    /* find stepwise chunks */
+    chunks=make_chunk(cslist);
+#if 1
+    chunks = 0;
+    for(i=cslist;i;i=cadr(i)) {
+        chunks++;
+    }
+    j = chunks;
+#endif
+    /* possible merge of loose stepwise chunks */
+    merge = merge_chunk(chunks);
+#if 0
+    //  chunks: list3(widest,next,delta);
+    printf("# chunks %d = sum ",j);
+    j = 0;
+    for(i=merge;i;i=cadr(i)) {
+	printf(" %d/%d",car(i),caddr(i));
+	j+=car(i);
+    }
+    printf(" sum = %d\n",j);
+#endif
+    /* make index branch or table jump */
+    gmax = chunk_max(chunks);
+    chunks = reverse0(chunks);
+    switch_index(merge,chunks,cslabel,dlabel,gmax);
+}
+
+#endif
+
+
+
+/* end */