commit f2cc7778e6a8922ae886ac1df50c01e87d17e3a5
parent b07998c29e9de4be362348f8e9594b43841f92ed
Author: erai <erai@omiltem.net>
Date: Sat, 1 Feb 2025 15:50:48 +0000
Add call graph
Diffstat:
| M | .gitignore | | | 1 | + |
| M | bootstrap.sh | | | 4 | ++-- |
| M | build.sh | | | 24 | ++++++++++++------------ |
| M | cc0.c | | | 80 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------- |
| M | cc1.om | | | 84 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------- |
| M | decl.om | | | 2 | ++ |
| M | ir.om | | | 17 | +++++++++-------- |
| M | syscall.om | | | 2 | ++ |
8 files changed, 163 insertions(+), 51 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -26,3 +26,4 @@ peg0
*.out*
*_peg.c
*.lines
+*.call
diff --git a/bootstrap.sh b/bootstrap.sh
@@ -8,10 +8,10 @@ SOURCES="cc1.om type.om parse2.om parse3.om peglib.om as.om decl.om node.om cout
gcc -std=c99 ${BOOTSTRAP} -o cc0
./cc0 -P P_ cc3.peg -o parse3.om
./cc0 -P PEG_ peg.peg -o parsepeg.om
-./cc0 ${LIBS} ${SOURCES} -o cc1 -n cc1.lines
+./cc0 ${LIBS} ${SOURCES} -o cc1 -n cc1.lines -G cc1.call
# Double check the bootstrap and self hosting compiler have the same output
-./cc1 ${LIBS} ${SOURCES} -o cc2 -n cc2.lines
+./cc1 ${LIBS} ${SOURCES} -o cc2 -n cc2.lines -G cc2.call
cmp cc1 cc2 || echo cc mismatch
# Verify the saved bootstrap matches
diff --git a/build.sh b/build.sh
@@ -10,18 +10,18 @@ SHELL="echo.om cmp.om rm.om ls.om cat.om xxd.om mv.om mkdir.om cpio.om sh.om"
BIN="echo cmp rm ls cat xxd mv mkdir cpio sh sshd init cc1 build.sh peg.peg cc3.peg"
ALL="${LIBS} ${CC} ${PEG} ${SSHD} ${KERNEL} ${SHELL} ${BIN}"
-./cc1 ${LIBS} echo.om -o echo -n echo.lines
-./cc1 ${LIBS} cmp.om -o cmp -n cmp.lines
-./cc1 ${LIBS} rm.om -o rm -n rm.lines
-./cc1 ${LIBS} mv.om -o mv -n mv.lines
-./cc1 ${LIBS} mkdir.om -o mkdir -n mkdir.lines
-./cc1 ${LIBS} ls.om -o ls -n ls.lines
-./cc1 ${LIBS} cat.om -o cat -n cat.lines
-./cc1 ${LIBS} xxd.om -o xxd -n xxd.lines
-./cc1 ${LIBS} cpio.om -o cpio -n cpio.lines
-./cc1 ${LIBS} sh.om -o sh -n sh.lines
-./cc1 ${LIBS} ${CRYPTO} sshd.om -o sshd -n sshd.lines
+./cc1 ${LIBS} echo.om -o echo -n echo.lines -G echo.call
+./cc1 ${LIBS} cmp.om -o cmp -n cmp.lines -G cmp.call
+./cc1 ${LIBS} rm.om -o rm -n rm.lines -G rm.call
+./cc1 ${LIBS} mv.om -o mv -n mv.lines -G mv.call
+./cc1 ${LIBS} mkdir.om -o mkdir -n mkdir.lines -G mkdir.call
+./cc1 ${LIBS} ls.om -o ls -n ls.lines -G ls.call
+./cc1 ${LIBS} cat.om -o cat -n cat.lines -G cat.call
+./cc1 ${LIBS} xxd.om -o xxd -n xxd.lines -G xxd.call
+./cc1 ${LIBS} cpio.om -o cpio -n cpio.lines -G cpio.call
+./cc1 ${LIBS} sh.om -o sh -n sh.lines -G sh.call
+./cc1 ${LIBS} ${CRYPTO} sshd.om -o sshd -n sshd.lines -G sshd.call
for name in ${ALL}; do echo ${name}; done | ./cpio -o > initramfs
-./cc1 kernel.om -o kernel -n kernel.lines
+./cc1 kernel.om -o kernel -n kernel.lines -G kernel.call
diff --git a/cc0.c b/cc0.c
@@ -76,6 +76,7 @@ struct my_compiler {
struct my_decl* my_decls;
unsigned long my_do_cout;
struct my_file* my_cout;
+ struct my_file* my_call_out;
struct my_label* my_start;
struct my_label* my_kstart;
struct my_decl* my_used_top;
@@ -87,6 +88,8 @@ struct my_decl {
struct my_decl* my_l;
struct my_decl* my_r;
struct my_decl* my_used_next;
+ unsigned long my_used_forward;
+ unsigned long my_used_backward;
unsigned long my_func_defined;
struct my_type* my_func_type;
struct my_label* my_func_label;
@@ -492,10 +495,12 @@ enum {
my_OP_WRMSR = 3888,
my_OP_WRSR = 142,
my_OP_XORRM = 51,
+ my_O_APPEND = 1024,
my_O_CREAT = 64,
my_O_DIRECTORY = 4096,
my_O_RDONLY = 0,
my_O_RDWR = 2,
+ my_O_TRUNC = 512,
my_O_WRONLY = 1,
my_PEG_alternative = 3,
my_PEG_any = 9,
@@ -780,7 +785,7 @@ unsigned long( my_literal)(struct my_peg* my_c,unsigned char* my_s);
void( my_locals_to_ir)(struct my_irfunc* my_ic,struct my_node* my_n);
void( my_main)(unsigned long my_argc,unsigned char** my_argv,unsigned char** my_envp);
void( my_mark_expr_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my_node* my_n);
-void( my_mark_func_used)(struct my_compiler* my_c,struct my_decl* my_d);
+void( my_mark_func_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my_decl* my_v);
void( my_mark_stmt_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my_node* my_n);
unsigned long( my_memcmp)(unsigned char* my_a,unsigned char* my_b,unsigned long my_n);
void( my_memcpy)(unsigned char* my_dest,unsigned char* my_src,unsigned long my_size);
@@ -806,6 +811,7 @@ unsigned long( my_mmap)(unsigned long my_addr,unsigned long my_len,unsigned long
struct my_decl*( my_next_decl)(struct my_compiler* my_c,struct my_decl* my_d);
unsigned char*( my_node_to_str)(unsigned long my_kind);
unsigned long( my_open)(unsigned char* my_name,unsigned long my_flags,unsigned long my_mode);
+void( my_open_call_out)(struct my_compiler* my_c,unsigned char* my_filename);
void( my_open_coutput)(struct my_compiler* my_c,unsigned char* my_filename);
void( my_open_lines_out)(struct my_compiler* my_c,unsigned char* my_filename);
void( my_open_output)(struct my_assembler* my_c,unsigned char* my_filename);
@@ -1786,7 +1792,7 @@ void( my_commit)(struct my_peg* my_c){
}
struct my_compiler*( my_comp_setup)(struct my_alloc* my_a){
struct my_compiler* my_c = 0;
- (my_c)=((struct my_compiler*)(my_alloc)((my_a),(96UL)));
+ (my_c)=((struct my_compiler*)(my_alloc)((my_a),(104UL)));
((my_c)->my_a)=(my_a);
((my_c)->my_p)=((my_setup_parser)((my_a)));
((my_c)->my_filename)=((void *)0);
@@ -1804,6 +1810,7 @@ struct my_compiler*( my_comp_setup)(struct my_alloc* my_a){
void( my_compile)(struct my_compiler* my_c,struct my_node* my_p){
struct my_node* my_n = 0;
struct my_decl* my_d = 0;
+ struct my_decl* my_v = 0;
unsigned long my_kind = 0;
(my_n)=(my_p);
while (1) {
@@ -1858,12 +1865,27 @@ void( my_compile)(struct my_compiler* my_c,struct my_node* my_p){
(my_d)=((my_find)((my_c),((unsigned char *)"_start"),((void *)0),(0UL)));
if ((unsigned long)((my_d)&&((my_d)->my_func_defined))) {
((my_c)->my_start)=((my_d)->my_func_label);
- (my_mark_func_used)((my_c),(my_d));
+ (my_mark_func_used)((my_c),((void *)0),(my_d));
}
(my_d)=((my_find)((my_c),((unsigned char *)"_kstart"),((void *)0),(0UL)));
if ((unsigned long)((my_d)&&((my_d)->my_func_defined))) {
((my_c)->my_kstart)=((my_d)->my_func_label);
- (my_mark_func_used)((my_c),(my_d));
+ (my_mark_func_used)((my_c),((void *)0),(my_d));
+ }
+ (my_check_usage)((my_c));
+ (my_d)=((my_find)((my_c),((unsigned char *)"_isr0"),((void *)0),(0UL)));
+ if ((unsigned long)((my_d)&&((my_d)->my_func_used))) {
+ (my_v)=((my_find)((my_c),((unsigned char *)"_isr"),((void *)0),(0UL)));
+ if ((unsigned long)((my_v)&&((my_v)->my_func_defined))) {
+ (my_mark_func_used)((my_c),(my_d),(my_v));
+ }
+ }
+ (my_d)=((my_find)((my_c),((unsigned char *)"_ssr0"),((void *)0),(0UL)));
+ if ((unsigned long)((my_d)&&((my_d)->my_func_used))) {
+ (my_v)=((my_find)((my_c),((unsigned char *)"_ssr"),((void *)0),(0UL)));
+ if ((unsigned long)((my_v)&&((my_v)->my_func_defined))) {
+ (my_mark_func_used)((my_c),(my_d),(my_v));
+ }
}
(my_check_usage)((my_c));
(my_d)=((my_first_decl)((my_c)));
@@ -4162,7 +4184,7 @@ struct my_decl*( my_find)(struct my_compiler* my_c,unsigned char* my_name,unsign
if ((unsigned long)(!(my_make))) {
return (void *)0;
}
- (my_d)=((struct my_decl*)(my_alloc)(((my_c)->my_a),(248UL)));
+ (my_d)=((struct my_decl*)(my_alloc)(((my_c)->my_a),(264UL)));
((my_d)->my_name)=(my_name);
((my_d)->my_member_name)=(my_member_name);
((my_d)->my_p)=(my_p);
@@ -4994,6 +5016,15 @@ void( my_main)(unsigned long my_argc,unsigned char** my_argv,unsigned char** my_
(my_i)=((unsigned long)(((unsigned long)(my_i))+((unsigned long)(1UL))));
continue;
}
+ if ((unsigned long)(!((my_strcmp)(((my_argv)[my_i]),((unsigned char *)"-G"))))) {
+ (my_i)=((unsigned long)(((unsigned long)(my_i))+((unsigned long)(1UL))));
+ if ((unsigned long)(((long)(my_i))>=((long)(my_argc)))) {
+ (my_die)(((unsigned char *)"invalid -P at end of argument list"));
+ }
+ (my_open_call_out)((my_c),((my_argv)[my_i]));
+ (my_i)=((unsigned long)(((unsigned long)(my_i))+((unsigned long)(1UL))));
+ continue;
+ }
if ((unsigned long)(!((my_strcmp)(((my_argv)[my_i]),((unsigned char *)"-n"))))) {
(my_i)=((unsigned long)(((unsigned long)(my_i))+((unsigned long)(1UL))));
if ((unsigned long)(((long)(my_i))>=((long)(my_argc)))) {
@@ -5091,7 +5122,7 @@ void( my_mark_expr_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my
}
(my_v)=((my_find)((my_c),((my_n)->my_s),((void *)0),(0UL)));
if ((unsigned long)((my_v)&&((my_v)->my_func_defined))) {
- (my_mark_func_used)((my_c),(my_v));
+ (my_mark_func_used)((my_c),(my_d),(my_v));
return;
}
(my_cdie)((my_c),((unsigned char *)"no such variable"));
@@ -5108,13 +5139,26 @@ void( my_mark_expr_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my
(my_cdie)((my_c),((unsigned char *)"not an expression"));
}
}
-void( my_mark_func_used)(struct my_compiler* my_c,struct my_decl* my_d){
- if ((my_d)->my_func_used) {
+void( my_mark_func_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my_decl* my_v){
+ struct my_decl* my_edge = 0;
+ if (my_d) {
+ (my_edge)=((my_find)((my_c),((my_d)->my_name),((my_v)->my_name),(1UL)));
+ if ((unsigned long)(((my_c)->my_call_out)&&((unsigned long)(!((my_edge)->my_used_forward))))) {
+ (my_fputs)(((my_c)->my_call_out),((my_d)->my_name));
+ (my_fputs)(((my_c)->my_call_out),((unsigned char *)" -> "));
+ (my_fputs)(((my_c)->my_call_out),((my_v)->my_name));
+ (my_fputs)(((my_c)->my_call_out),((unsigned char *)"\012"));
+ }
+ ((my_edge)->my_used_forward)=(1UL);
+ (my_edge)=((my_find)((my_c),((my_v)->my_name),((my_d)->my_name),(1UL)));
+ ((my_edge)->my_used_backward)=(1UL);
+ }
+ if ((my_v)->my_func_used) {
return;
}
- ((my_d)->my_func_used)=(1UL);
- ((my_d)->my_used_next)=((my_c)->my_used_top);
- ((my_c)->my_used_top)=(my_d);
+ ((my_v)->my_func_used)=(1UL);
+ ((my_v)->my_used_next)=((my_c)->my_used_top);
+ ((my_c)->my_used_top)=(my_v);
}
void( my_mark_stmt_used)(struct my_compiler* my_c,struct my_decl* my_d,struct my_node* my_n){
unsigned long my_kind = 0;
@@ -5571,13 +5615,20 @@ unsigned char*( my_node_to_str)(unsigned long my_kind){
unsigned long( my_open)(unsigned char* my_name,unsigned long my_flags,unsigned long my_mode){
return (my_syscall)((2UL),((unsigned long)my_name),(my_flags),(my_mode),(0UL),(0UL),(0UL));
}
+void( my_open_call_out)(struct my_compiler* my_c,unsigned char* my_filename){
+ unsigned long my_fd = 0;
+ (my_fd)=((my_open)((my_filename),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(my_O_CREAT))|((unsigned long)(my_O_WRONLY)))))|((unsigned long)(my_O_TRUNC)))),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(6UL)))))+((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(3UL))))))))+((unsigned long)(6UL))))));
+ if ((unsigned long)(((long)(my_fd))<((long)(0UL)))) {
+ (my_die)(((unsigned char *)"failed to open output"));
+ }
+ ((my_c)->my_call_out)=((my_fopen)((my_fd),((my_c)->my_a)));
+}
void( my_open_coutput)(struct my_compiler* my_c,unsigned char* my_filename){
unsigned long my_fd = 0;
if ((my_c)->my_cout) {
(my_die)(((unsigned char *)"multiple output files"));
}
- (my_unlink)((my_filename));
- (my_fd)=((my_open)((my_filename),((unsigned long)(((unsigned long)(my_O_CREAT))|((unsigned long)(my_O_WRONLY)))),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(6UL)))))+((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(3UL))))))))+((unsigned long)(6UL))))));
+ (my_fd)=((my_open)((my_filename),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(my_O_CREAT))|((unsigned long)(my_O_WRONLY)))))|((unsigned long)(my_O_TRUNC)))),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(6UL)))))+((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(3UL))))))))+((unsigned long)(6UL))))));
if ((unsigned long)(((long)(my_fd))<((long)(0UL)))) {
(my_die)(((unsigned char *)"failed to open output"));
}
@@ -5585,8 +5636,7 @@ void( my_open_coutput)(struct my_compiler* my_c,unsigned char* my_filename){
}
void( my_open_lines_out)(struct my_compiler* my_c,unsigned char* my_filename){
unsigned long my_fd = 0;
- (my_unlink)((my_filename));
- (my_fd)=((my_open)((my_filename),((unsigned long)(((unsigned long)(my_O_CREAT))|((unsigned long)(my_O_WRONLY)))),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(6UL)))))+((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(3UL))))))))+((unsigned long)(6UL))))));
+ (my_fd)=((my_open)((my_filename),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(my_O_CREAT))|((unsigned long)(my_O_WRONLY)))))|((unsigned long)(my_O_TRUNC)))),((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(6UL)))))+((unsigned long)((unsigned long)(((unsigned long)(6UL))<<((unsigned long)(3UL))))))))+((unsigned long)(6UL))))));
if ((unsigned long)(((long)(my_fd))<((long)(0UL)))) {
(my_die)(((unsigned char *)"failed to open output"));
}
diff --git a/cc1.om b/cc1.om
@@ -20,6 +20,9 @@ struct compiler {
do_cout: int;
cout: *file;
+ // Call graph
+ call_out: *file;
+
// Entry points
start: *label;
kstart: *label;
@@ -83,9 +86,7 @@ func open_coutput(c: *compiler, filename: *byte) {
die("multiple output files");
}
- unlink(filename);
-
- fd = open(filename, O_CREAT | O_WRONLY, (6 << 6) + (6 << 3) + 6);
+ fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, (6 << 6) + (6 << 3) + 6);
if (fd < 0) {
die("failed to open output");
}
@@ -100,6 +101,7 @@ func flush_coutput(c: *compiler) {
func compile(c: *compiler, p: *node) {
var n: *node;
var d: *decl;
+ var v: *decl;
var kind: int;
// Process enum and struct declarations
@@ -172,13 +174,31 @@ func compile(c: *compiler, p: *node) {
d = find(c, "_start", nil, 0);
if (d && d.func_defined) {
c.start = d.func_label;
- mark_func_used(c, d);
+ mark_func_used(c, nil, d);
}
d = find(c, "_kstart", nil, 0);
if (d && d.func_defined) {
c.kstart = d.func_label;
- mark_func_used(c, d);
+ mark_func_used(c, nil, d);
+ }
+
+ check_usage(c);
+
+ d = find(c, "_isr0", nil, 0);
+ if d && d.func_used {
+ v = find(c, "_isr", nil, 0);
+ if (v && v.func_defined) {
+ mark_func_used(c, d, v);
+ }
+ }
+
+ d = find(c, "_ssr0", nil, 0);
+ if d && d.func_used {
+ v = find(c, "_ssr", nil, 0);
+ if (v && v.func_defined) {
+ mark_func_used(c, d, v);
+ }
}
check_usage(c);
@@ -212,14 +232,31 @@ func compile(c: *compiler, p: *node) {
}
}
-func mark_func_used(c: *compiler, d: *decl) {
- if d.func_used {
+func mark_func_used(c: *compiler, d: *decl, v: *decl) {
+ var edge: *decl;
+
+ if d {
+ // name uses member
+ edge = find(c, d.name, v.name, 1);
+ if c.call_out && !edge.used_forward {
+ fputs(c.call_out, d.name);
+ fputs(c.call_out, " -> ");
+ fputs(c.call_out, v.name);
+ fputs(c.call_out, "\n");
+ }
+ edge.used_forward = 1;
+ // member uses name
+ edge = find(c, v.name, d.name, 1);
+ edge.used_backward = 1;
+ }
+
+ if v.func_used {
return;
}
- d.func_used = 1;
- d.used_next = c.used_top;
- c.used_top = d;
+ v.func_used = 1;
+ v.used_next = c.used_top;
+ c.used_top = v;
}
func mark_expr_used(c: *compiler, d: *decl, n: *node) {
@@ -259,7 +296,7 @@ func mark_expr_used(c: *compiler, d: *decl, n: *node) {
v = find(c, n.s, nil, 0);
if v && v.func_defined {
- mark_func_used(c, v);
+ mark_func_used(c, d, v);
return;
}
@@ -2130,12 +2167,21 @@ func emit_builtin(c: *compiler) {
}
}
-func open_lines_out(c: *compiler, filename: *byte) {
+func open_call_out(c: *compiler, filename: *byte) {
var fd: int;
- unlink(filename);
+ fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, (6 << 6) + (6 << 3) + 6);
+ if (fd < 0) {
+ die("failed to open output");
+ }
+
+ c.call_out = fopen(fd, c.a);
+}
+
+func open_lines_out(c: *compiler, filename: *byte) {
+ var fd: int;
- fd = open(filename, O_CREAT | O_WRONLY, (6 << 6) + (6 << 3) + 6);
+ fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, (6 << 6) + (6 << 3) + 6);
if (fd < 0) {
die("failed to open output");
}
@@ -2199,6 +2245,16 @@ func main(argc: int, argv: **byte, envp: **byte) {
continue;
}
+ if (!strcmp(argv[i], "-G")) {
+ i = i + 1;
+ if (i >= argc) {
+ die("invalid -P at end of argument list");
+ }
+ open_call_out(c, argv[i]);
+ i = i + 1;
+ continue;
+ }
+
if (!strcmp(argv[i], "-n")) {
i = i + 1;
if (i >= argc) {
diff --git a/decl.om b/decl.om
@@ -6,6 +6,8 @@ struct decl {
r: *decl;
used_next: *decl;
+ used_forward: int;
+ used_backward: int;
func_defined: int;
func_type: *type;
diff --git a/ir.om b/ir.om
@@ -2087,21 +2087,22 @@ func output_irexpr(ic: *irfunc, b: *irblock, o: *irop) {
}
}
-// evaluator
-// instruction selection
+// constant folding
+// common subexpression
// register allocation
// inline
// intrinsics
-// common subexpression
-// constant folding
+// instruction selection
// flow control graph simplification
// dead code
-// c generator from ir
+
// type check with ir
// parse to ir
-// value numbering
+// c generator from ir
+
// loop detection
// unrolling
-// strength reduction / algebra
// loop motion / fusion
-// proof check from ir
+
+// strength reduction / algebra
+// alias analysis
diff --git a/syscall.om b/syscall.om
@@ -5,6 +5,8 @@ enum {
O_WRONLY = 1,
O_RDWR = 2,
O_CREAT = 64,
+ O_TRUNC = 512,
+ O_APPEND = 1024,
O_DIRECTORY = 0x1000,
EINTR = 4,
