Heatmap, etc.

- factor out prologue and epilogue
- -H, -L
- sourcemapping
- separate settings
- heatmap.py

6 files changed, 426 insertions, 107 deletions

diff --git a/.gitignore b/.gitignore
index 261e785..65a23cc 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,3 +2,9 @@ bfcomp
 *.o
 *.dSYM
 dst
+*.asm.h
+*.bf
+*.bf.asm
+*.html
+heatmap.txt
+dst.asm
diff --git a/Makefile b/Makefile
index 73e948a..fa0c505 100644
--- a/Makefile
+++ b/Makefile
@@ -1,16 +1,21 @@
 CC := gcc
 CFLAGS := -Wall -Wextra -std=c11 -O2 -fwrapv
 BIN := bfcomp
+SNIPPETS := $(wildcard *.snippet.asm)
+SNIPPETHEADERS := $(patsubst %.asm,%.asm.h,$(SNIPPETS))
 
 .PHONY: all clean remake
 
 all: $(BIN)
 
 clean:
-	rm -rf $(BIN) *.dSYM
+	rm -rf $(BIN) *.asm.h *.dSYM
 
 remake: clean all
 
 
-$(BIN): $(wildcard *.c *.h)
+$(BIN): $(wildcard *.c *.h) $(SNIPPETHEADERS)
 	$(CC) $(CFLAGS) -o $@ $(filter-out %.h,$^)
+
+%.asm.h: %.asm
+	(printf '#pragma once\n\n'; xxd -i $^ | sed 's/[0-9a-f]$$/&, 0x00/' | sed 's/unsigned //g') >$@
diff --git a/bfcomp.c b/bfcomp.c
index 5c4db60..8065fc4 100644
--- a/bfcomp.c
+++ b/bfcomp.c
@@ -6,6 +6,9 @@
 #include <time.h>
 #include <assert.h>
 
+#include "prologue.snippet.asm.h"
+#include "epilogue.snippet.asm.h"
+
 #define DBGTIME(tag,block) \
 	do { \
 		clock_t start=clock(); \
@@ -41,6 +44,8 @@ void usage(const char *argv0){
 		"in <dstfile>.\n"
 		"Uses nasm for assembling and gcc for linking.\n"
 		"  -h             Show help\n"
+		"  -H             Calculate heatmap while executing\n"
+		"  -L             Output last cell reached\n"
 		"  -m <memsize>   Specify amount of tape cells (bytes) for the BF code\n"
 		"  -v             Show more info about the compile process\n",
 		argv0);
@@ -54,9 +59,9 @@ __attribute__((noreturn)) void usage1(const char *argv0){
 typedef struct Params{
 	int memsize;
 	const char *srcfname,*dstfname;
-	bool verbose;
+	bool lastcell,verbose,heatmap;
 } Params;
-Params params={30000,NULL,NULL,false};
+Params params={30000,NULL,NULL,false,false,false};
 
 void parseargs(int argc,char **argv){
 	if(argc<2)usage1(argv[0]);
@@ -70,6 +75,14 @@ void parseargs(int argc,char **argv){
 						usage(argv[0]);
 						exit(0);
 
+					case 'H':
+						params.heatmap=true;
+						break;
+
+					case 'L':
+						params.lastcell=true;
+						break;
+
 					case 'm':{
 						if(i==argc-1)usage1(argv[0]);
 						char *endp;
@@ -93,7 +106,31 @@ void parseargs(int argc,char **argv){
 	if(!params.srcfname||!params.dstfname)usage1(argv[0]);
 }
 
-int runcmd(const char *cmd/*,int in,int out*/){
+typedef struct Range{
+	int from,to; //[from,to); empty range indicates no mapping
+} Range;
+
+typedef struct Sourcemap{
+	int len,origlen;
+	Range *maps;
+} Sourcemap;
+
+Sourcemap* sourcemap_init(int len){
+	Sourcemap *sm=malloc(sizeof(Sourcemap));
+	if(!sm)outofmem();
+	sm->len=len;
+	sm->origlen=-1;
+	sm->maps=calloc(len,sizeof(Range));
+	if(!sm->maps)outofmem();
+	return sm;
+}
+
+void sourcemap_destroy(Sourcemap *sm){
+	if(sm->maps)free(sm->maps);
+	free(sm);
+}
+
+int runcmd(const char *cmd){
 	clock_t start=clock();
 	pid_t pid=fork();
 	if(pid<0){
@@ -101,8 +138,6 @@ int runcmd(const char *cmd/*,int in,int out*/){
 		exit(1);
 	}
 	if(pid==0){
-		/*dup2(in,0);
-		dup2(out,1);*/
 		execl("/bin/sh","/bin/sh","-c",cmd,NULL);
 		__builtin_unreachable();
 	} else {
@@ -132,55 +167,44 @@ FILE* gettempfilew(char name[20]){
 int compilechain(const char *asmfname,const char *dstfname){
 	char ofname[20];
 	FILE *f=gettempfilew(ofname);
-	assert(strlen(ofname)==19);
 	fclose(f);
-	char buf[25+19+1+strlen(asmfname)+1];
-	sprintf(buf,"nasm -f macho64 -w+all -o %s %s",ofname,asmfname);
+
+	char *buf;
+
+	asprintf(&buf,"nasm -f macho64 -w+all -o %s %s",ofname,asmfname);
+	if(!buf)outofmem();
 	int ret=runcmd(buf);
+	free(buf);
 	if(ret)return ret;
-	char buf2[4+19+4+strlen(dstfname)+1];
-	sprintf(buf2,"gcc %s -o %s",ofname,dstfname);
-	ret=runcmd(buf2);
+
+	asprintf(&buf,"gcc %s -o %s",ofname,dstfname);
+	if(!buf)outofmem();
+	ret=runcmd(buf);
+	free(buf);
+
 	unlink(ofname);
 	if(params.verbose)fprintf(stderr,"unlink(%s)  (ofile)\n",ofname);
 	return ret;
 }
 
+void writesettings(FILE *asmf,Sourcemap *sm){
+	fprintf(asmf,"%%define PARAMS_MEMSIZE %d\n",params.memsize);
+	if(params.lastcell)fprintf(asmf,"%%define OUTPUT_LAST_CELL\n");
+	if(params.heatmap){
+		assert(sm);
+		fprintf(asmf,"%%define HEATMAP\n");
+		fprintf(asmf,"%%define SOURCE_LENGTH %d\n",sm->origlen);
+	}
+	fputc('\n',asmf);
+}
+
 void writeprologue(FILE *asmf){
-	fprintf(asmf,
-		"global _main\n"
-		"\n"
-		"extern _malloc\n"
-		"extern _free\n"
-		"extern _printf\n"
-		"extern _getchar\n"
-		"extern _putchar\n"
-		"extern _write\n"
-		"extern ___stdoutp\n"
-		"extern _fflush\n"
-		"\n"
-		"default rel\n"
-		"\n"
-		"section .text\n"
-		"\n"
-		"_main:\n"
-		"\tpush rbp  ; prologue\n"
-		"\tmov rbp, rsp\n"
-		"\tadd rsp, 8\n"
-		"\tpush rbx\n"
-		"\tmov edi, %d\n"
-		"\tcall _malloc\n"
-		"\tcmp rax, 0\n"
-		"\tjz nomem\n"
-		"\tmov rbx, rax ;bufp\n"
-		"\tmov [buf], rax ;buf\n"
-		"\n",
-		params.memsize);
+	fwrite(prologue_snippet_asm,1,prologue_snippet_asm_len,asmf);
 }
 
-void writeprogram(char *source,FILE *asmf){
+void writeprogram(char *source,FILE *asmf,Sourcemap *sm){
 	int addc=0,shiftc=0;
-	//int lastshiftc=0;
+	int lastshiftc=0;
 	struct stackitem {int id; struct stackitem *next;} *loopstack=NULL;
 	int i=0;
 	do {
@@ -194,21 +218,32 @@ void writeprogram(char *source,FILE *asmf){
 		}
 		if(shiftc&&c!='>'&&c!='<'){
 			shiftc=(shiftc%256)+256%256;
-			/*if(lastshiftc>0&&shiftc<0){
-				int id=uniqid();
-				fprintf(asmf,
-					"\tcmp [maxp], rbx\n"
-					"\tjge skip%d\n"
-					"\tmov [maxp], rbx\n"
-					"skip%d:\n",
-					id,id);
+			if(params.lastcell){
+				if(lastshiftc>0&&shiftc<0){
+					int id=uniqid();
+					fprintf(asmf,
+						"%%ifdef OUTPUT_LAST_CELL\n"
+						"\tcmp [maxp], rbx\n"
+						"\tjge skip%d\n"
+						"\tmov [maxp], rbx\n"
+						"skip%d:\n"
+						"%%endif\n",
+						id,id);
+				}
+				lastshiftc=shiftc;
 			}
-			lastshiftc=shiftc;*/
 			if(shiftc==1)fprintf(asmf,"\tinc rbx  ; 1 >\n");
 			else if(shiftc==-1)fprintf(asmf,"\tdec rbx  ; 1 <\n");
 			else fprintf(asmf,"\tadd rbx, %d  ; %d %c\n",shiftc,shiftc<0?-shiftc:shiftc,shiftc<0?'<':'>');
 			shiftc=0;
 		}
+
+		if(sm){
+			for(int j=sm->maps[i].from;j<sm->maps[i].to;j++){
+				fprintf(asmf,"\tinc dword [r12+%d]\n",4*j);
+			}
+		}
+
 		switch(c){
 			case '+': addc++; break;
 			case '-': addc--; break;
@@ -276,79 +311,65 @@ void writeprogram(char *source,FILE *asmf){
 }
 
 void writeepilogue(FILE *asmf){
-	fprintf(asmf,
-		"\n"
-		"\tmov rdi, [buf]  ; epilogue\n"
-		"\tcall _free\n"
-		"\n"
-		/*"\tlea rdi, [formatstr] ;output last cell reached\n"
-		"\tmov rsi, [maxp]\n"
-		"\tsub rsi, [buf]\n"
-		"\txor eax, eax\n"
-		"\tcall _printf\n"
-		"\n"*/
-		"\txor eax, eax\n"
-		"\tjmp mainend\n"
-		"\n"
-		"nomem:\n"
-		"\tmov edi, 2\n"
-		"\tlea rsi, [nomemstr]\n"
-		"\tmov rdx, nomemstr.len\n"
-		"\tcall _write\n"
-		"\tmov eax, 1\n"
-		"\n"
-		"mainend:\n"
-		"\tpop rbx\n"
-		"\tmov rsp, rbp\n"
-		"\tpop rbp\n"
-		"\tret\n"
-		"\n"
-		"\n"
-		"section .data\n"
-		"sectalign 8\n"
-		"\n"
-		"nomemstr: db \"Out of memory!\"\n"
-		".len: equ $-nomemstr\n"
-		/*"\n"
-		"formatstr: db \"Last cell reached: %%d\", 10, 0\n"
-		"\n"
-		"align 8, db 0\n"
-		"maxp: dq 0\n"*/
-		"\n"
-		"\n"
-		"section .bss\n"
-		"sectalign 8\n"
-		"\n"
-		"buf: resq 1\n");
+	fwrite(epilogue_snippet_asm,1,epilogue_snippet_asm_len,asmf);
 }
 
-void readsource(FILE *f,char **sourcep){
+void readsource(FILE *f,char **sourcep,Sourcemap **smp){
 	int sz=1024;
+	Sourcemap *sm=NULL;
+	if(smp)sm=sourcemap_init(sz);
 	char *source=malloc(sz);
 	if(!source)outofmem();
 	int i=0;
+	int sourcei=0;
 	while(true){
 		if(i==sz-1){
 			sz*=2;
 			source=realloc(source,sz);
 			if(!source)outofmem();
+			sm->maps=realloc(sm->maps,sz*sizeof(Range));
+			if(!sm->maps)outofmem();
+			memset(sm->maps+sz/2,0,sz/2*sizeof(Range));
 		}
 		char c=fgetc(f);
 		if(feof(f))break;
-		if(!strchr("+-><[].,",c))continue;
+		if(!strchr("+-><[].,",c)){
+			sourcei++;
+			continue;
+		}
+		if(sm)sm->maps[i].from=sourcei;
+		if(sm)sm->maps[i].to=sourcei+1;
 		source[i++]=c;
+		sourcei++;
 	}
 	source[i]='\0';
+	if(sm){
+		sm->len=i;
+		sm->origlen=sourcei;
+	}
 	*sourcep=source;
+	if(sm)*smp=sm;
 }
 
-void optimise(char *source){
-	int j=0;
-#define COPY do {if(j<i)source[j]=source[i]; j++;} while(0)
-	for(int i=0;source[i];i++){
+void optimise(char *source,const Sourcemap *srcsm,Sourcemap **dstsm){
+	Sourcemap *sm=NULL;
+	if(dstsm)sm=sourcemap_init(srcsm->len);
+	int i,j=0;
+
+#define COPY do { \
+			if(j<i)source[j]=source[i]; \
+			if(sm)sm->maps[j]=srcsm->maps[i]; \
+			j++; \
+		} while(0)
+
+	for(i=0;source[i];i++){
 		switch(source[i]){
 			case '[':
 				if(source[i+1]=='-'&&source[i+2]==']'){
+					if(sm){
+						sm->maps[j].from=srcsm->maps[i].from;
+						sm->maps[j].to=srcsm->maps[i+2].to;
+					}
 					source[j++]='0';
 					i+=2;
 				} else COPY;
@@ -359,8 +380,13 @@ void optimise(char *source){
 				break;
 		}
 	}
+	if(sm){
+		sm->len=j;
+		sm->origlen=srcsm->origlen;
+	}
 	source[j]='\0';
 #undef COPY
+	if(sm)*dstsm=sm;
 }
 
 int main(int argc,char **argv){
@@ -374,25 +400,28 @@ int main(int argc,char **argv){
 	}
 
 	char *source;
-	readsource(srcf,&source);
+	Sourcemap *sm1=NULL;
+	readsource(srcf,&source,params.heatmap?&sm1:NULL);
 	assert(source);
 
 	fclose(srcf);
 
-	optimise(source);
+	Sourcemap *sm2=NULL;
+	optimise(source,sm1,params.heatmap?&sm2:NULL);
 
 	char asmfname[20];
 	FILE *asmf=gettempfilew(asmfname);
 	if(params.verbose)fprintf(stderr,"asm -> %s\n",asmfname);
 
+	DBGTIME("writesettings",writesettings(asmf,sm2););
 	DBGTIME("writeprologue",writeprologue(asmf););
-	DBGTIME("writeprogram",writeprogram(source,asmf););
+	DBGTIME("writeprogram",writeprogram(source,asmf,sm2););
 	DBGTIME("writeepilogue",writeepilogue(asmf););
 
 	fclose(asmf);
 
 	/*char *b;
-	asprintf(&b,"cat -n %s",asmfname);
+	asprintf(&b,"cp %s %s.asm",asmfname,params.srcfname);
 	runcmd(b);
 	free(b);*/
 	int ret=compilechain(asmfname,params.dstfname);
diff --git a/epilogue.snippet.asm b/epilogue.snippet.asm
new file mode 100644
index 0000000..fffddb7
--- /dev/null
+++ b/epilogue.snippet.asm
@@ -0,0 +1,81 @@
+
+	mov rdi, [buf]  ; EPILOGUE
+	call _free
+
+%ifdef OUTPUT_LAST_CELL
+	lea rdi, [strbuf64] ; snprintf(strbuf64,64,LCRformatstr,maxp-buf)
+	mov esi, 64
+	lea rdx, [LCRformatstr]
+	mov rcx, qword [maxp]
+	sub rcx, qword [buf]
+	call _snprintf
+
+	mov edi, 2
+	lea rsi, [strbuf64]
+	mov edx, eax
+	call _write
+%endif
+
+%ifdef HEATMAP
+	mov ebx, 0 ;loop counter
+hmloop:
+	lea rdi, [strbuf64]  ; snprintf(strbuf64,64,HMformatstr,ebx /*counter*/,r12[rbx])
+	mov esi, 64
+	lea rdx, [HMformatstr]
+	mov ecx, ebx
+	mov r8d, dword [r12+4*rbx]
+	xor eax, eax
+	call _snprintf
+
+	mov edi, 2
+	lea rsi, [strbuf64]
+	mov edx, eax
+	call _write
+
+	inc ebx
+	cmp ebx, SOURCE_LENGTH
+	jl hmloop
+%endif
+
+	xor eax, eax
+
+mainend:
+	pop r12
+	pop rbx
+	mov rsp, rbp
+	pop rbp
+	ret
+
+nomem:
+	mov edi, 2
+	lea rsi, [nomemstr]
+	mov rdx, nomemstr.len
+	call _write
+	mov eax, 1
+	jmp mainend
+
+
+section .data
+sectalign 8
+
+nomemstr: db "Out of memory!"
+.len: equ $-nomemstr
+
+%ifdef OUTPUT_LAST_CELL
+	LCRformatstr: db "Last cell reached: %d", 10, 0
+
+	align 8, db 0
+	maxp: dq 0
+%endif
+
+%ifdef HEATMAP
+	HMformatstr: db "%d %d", 10, 0
+%endif
+
+
+section .bss
+sectalign 8
+
+buf: resq 1
+
+strbuf64: resb 64
diff --git a/heatmap.py b/heatmap.py
new file mode 100755
index 0000000..37dcdf1
--- /dev/null
+++ b/heatmap.py
@@ -0,0 +1,158 @@
+#!/usr/bin/env python3
+
+import sys, math, re
+
+if len(sys.argv)!=3:
+	print("Usage: {0} <source.bf> <heatmap.txt>".format(sys.argv[0]),file=sys.stderr)
+	sys.exit(1)
+
+bffname=sys.argv[1]
+hmfname=sys.argv[2]
+
+#def setgray(brightness):
+#	ramp=[231,230,225,224,219,218,213,212,207,206,201,200,199,198,197,196]
+#	code="\x1B[38;5;{0}m".format(ramp[int(brightness*(len(ramp)-1))])
+#	brightness=int(brightness*25)
+#	#if brightness==0: code="\x1B[0;30m"
+#	#elif brightness==25: code="\x1B[1;37m"
+#	#else: code="\x1B[38;5;{0}m".format(brightness-1+232)
+#	print(code,end="")
+
+#for (c,count) in source:
+#	setgray(math.log(count/maxcount*3+1)/math.log(4))
+#	print(c,end="")
+
+def htmlconvert(ch):
+	if ch=="<": return "&lt;"
+	elif ch==">": return "&gt;"
+	elif ch=="\n": return "<br>"
+	elif ch==" ": return "&nbsp;"
+	else: return ch
+
+def hexcolor(r,g,b):
+	r,g,b=[int(x*255) for x in [r,g,b]]
+	return "#{0:0>2}{1:0>2}{2:0>2}".format(hex(r)[2:],hex(g)[2:],hex(b)[2:])
+
+def colorfor(freq):
+	ramp=[
+		(0.0,  (1.0,1.0,1.0)),
+		(0.3,  (0.3,0.5,0.5)),
+		(0.7,  (0.2,0.2,1.0)),
+		(0.85, (0.6,0.1,1.0)),
+		(1.0,  (1.0,0.0,0.0))
+	]
+	for i in range(len(ramp)):
+		if ramp[i][0]>=freq:
+			break;
+	if i==0:
+		return hexcolor(*ramp[i][1])
+	c1=ramp[i-1][1]
+	c2=ramp[i][1]
+	t=(freq-ramp[i-1][0])/(ramp[i][0]-ramp[i-1][0])
+	return hexcolor(*[c1[i]*(1-t)+c2[i]*t for i in [0,1,2]])
+
+with open(bffname) as f:
+	source=[c for c in f.read()]
+
+maxcount=0
+with open(hmfname) as f:
+	for line in f:
+		idx,count=[int(x) for x in line.split(" ")]
+		source[idx]=(htmlconvert(source[idx]),count)
+		maxcount=max(maxcount,count)
+
+print("""<!doctype html>
+<html>
+<head>
+<meta charset="utf-8">
+<title>Heatmap for execution of """+bffname+"""</title>
+<style>
+body{
+	font-family:Monaco,Meslo,monospace;
+	font-size:13px;
+}
+span.s{
+	border-radius:3px;
+	padding-top:1px;
+	padding-bottom:1px;
+}
+span.s:hover{
+	-webkit-box-shadow: inset 0px 0px 6px 0px rgba(0, 0, 0, 0.6);
+	-moz-box-shadow: inset 0px 0px 6px 0px rgba(0, 0, 0, 0.6);
+	box-shadow: inset 0px 0px 6px 0px rgba(0, 0, 0, 0.6);
+}
+div.codebox{
+	line-height:1.4em;
+}
+div#tooltip{
+	position:absolute;
+	display:none;
+	font-size:11px;
+	padding:3px;
+	background-color:black;
+	color:white;
+	opacity:0.9;
+	border-radius:6px;
+}
+div#tooltip.shown{
+	display:block;
+}
+</style>
+<script>
+var incounter=0;
+var tooltip,ttfreq,ttperc;
+
+function menter(e){
+	incounter++;
+	ttfreq.innerHTML=e.target.getAttribute("data-freq");
+	ttperc.innerHTML=e.target.getAttribute("data-perc");
+	var bbox=e.target.getBoundingClientRect();
+	tooltip.style.left=bbox.left+30+"px";
+	tooltip.style.top=document.body.scrollTop+bbox.top+18+"px";
+	tooltip.classList.add("shown");
+}
+function mleave(e){
+	incounter--;
+	if(incounter<0)incounter=0;
+	if(incounter==0)tooltip.classList.remove("shown");
+}
+
+window.addEventListener("load",function(){
+	tooltip=document.getElementById("tooltip");
+	tooltip.setAttribute("style","left:0;top:0");
+	ttfreq=tooltip.getElementsByClassName("ttfreq")[0];
+	ttperc=tooltip.getElementsByClassName("ttperc")[0];
+	var l=document.getElementsByClassName("s");
+	var i;
+	for(i=0;i<l.length;i++){
+		l[i].addEventListener("mouseenter",menter);
+		l[i].addEventListener("mouseleave",mleave);
+		//l[i].setAttribute("title","count: "+l[i].getAttribute("data-freq")+"\\nfreq: "+l[i].getAttribute("data-perc")+"%");
+	}
+});
+</script>
+</head>
+<body>
+<h1>"""+bffname+"""</h1>
+<div id="tooltip">
+	Frequency: <span class="ttfreq"></span><br>
+	(<span class="ttperc"></span>% of maximum)
+</div>
+<div class="codebox">""")
+
+i=0
+for (c,count) in source:
+	if i==0 or source[i-1][1]!=count:
+		print(
+			"<span class=\"s\" data-freq=\"{1}\" data-perc=\"{2}\" style=\"background-color:{0}\">"
+				.format(colorfor(count/maxcount),count,int(count/maxcount*100)),
+			end="")
+	print(c,end="")
+	if i==len(source)-1 or source[i+1][1]!=count:
+		print("</span>",end="")
+	i+=1
+
+print("""
+</pre>
+</body>
+</html>""")
diff --git a/prologue.snippet.asm b/prologue.snippet.asm
new file mode 100644
index 0000000..e706651
--- /dev/null
+++ b/prologue.snippet.asm
@@ -0,0 +1,40 @@
+global _main
+
+extern _calloc
+extern _fflush
+extern _free
+extern _getchar
+extern _malloc
+extern _printf
+extern _putchar
+extern _snprintf
+extern _write
+
+default rel
+
+section .text
+
+_main:
+	push rbp  ; PROLOGUE
+	mov rbp, rsp
+	push rbx
+	push r12
+	mov edi, PARAMS_MEMSIZE
+	call _malloc
+	cmp rax, 0
+	jz nomem
+	mov rbx, rax ;bufp
+	mov [buf], rax ;buf
+
+%ifdef HEATMAP
+	mov edi, SOURCE_LENGTH
+	mov esi, 4
+	call _calloc
+	cmp rax, 0
+	jz nomem
+	mov r12, rax
+%endif
+
+; rbx = bufp
+; r12 = heatmap
+