diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | Makefile | 9 | ||||
| -rw-r--r-- | bfcomp.c | 239 | ||||
| -rw-r--r-- | epilogue.snippet.asm | 81 | ||||
| -rwxr-xr-x | heatmap.py | 158 | ||||
| -rw-r--r-- | prologue.snippet.asm | 40 |
6 files changed, 426 insertions, 107 deletions
@@ -2,3 +2,9 @@ bfcomp *.o *.dSYM dst +*.asm.h +*.bf +*.bf.asm +*.html +heatmap.txt +dst.asm @@ -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') >$@ @@ -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 "<" + elif ch==">": return ">" + elif ch=="\n": return "<br>" + elif ch==" ": return " " + 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 + |