summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore6
-rw-r--r--Makefile9
-rw-r--r--bfcomp.c239
-rw-r--r--epilogue.snippet.asm81
-rwxr-xr-xheatmap.py158
-rw-r--r--prologue.snippet.asm40
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
+