mescc: Refactor compiler.
[mes.git] / module / language / c99 / compiler.mes
1 ;;; -*-scheme-*-
2
3 ;;; Mes --- Maxwell Equations of Software
4 ;;; Copyright © 2016,2017 Jan Nieuwenhuizen <janneke@gnu.org>
5 ;;;
6 ;;; This file is part of Mes.
7 ;;;
8 ;;; Mes is free software; you can redistribute it and/or modify it
9 ;;; under the terms of the GNU General Public License as published by
10 ;;; the Free Software Foundation; either version 3 of the License, or (at
11 ;;; your option) any later version.
12 ;;;
13 ;;; Mes is distributed in the hope that it will be useful, but
14 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
15 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 ;;; GNU General Public License for more details.
17 ;;;
18 ;;; You should have received a copy of the GNU General Public License
19 ;;; along with Mes.  If not, see <http://www.gnu.org/licenses/>.
20
21 ;;; Commentary:
22
23 ;;; compiler.mes produces an i386 binary from the C produced by
24 ;;; Nyacc c99.
25
26 ;;; Code:
27
28 (cond-expand
29  (guile-2
30   (set-port-encoding! (current-output-port) "ISO-8859-1"))
31  (guile)
32  (mes
33   (mes-use-module (nyacc lang c99 parser))
34   (mes-use-module (mes elf-util))
35   (mes-use-module (mes pmatch))
36   (mes-use-module (mes elf))
37   (mes-use-module (mes libc-i386))
38   (mes-use-module (mes optargs))))
39
40 (define (logf port string . rest)
41   (apply format (cons* port string rest))
42   (force-output port)
43   #t)
44
45 (define (stderr string . rest)
46   (apply logf (cons* (current-error-port) string rest)))
47
48 (define (gnuc-xdef? name mode) (if (equal? name "__GNUC__") #f (eq? mode 'code)))
49
50 (define (mescc)
51   (parse-c99
52    #:inc-dirs (string-split (getenv "C_INCLUDE_PATH") #\:)
53    #:cpp-defs '(
54                 ("__GNUC__" . "0")
55                 ("__NYACC__" . "1")
56                 ("VERSION" . "0.4")
57                 ("PREFIX" . "")
58                 )
59    #:xdef? gnuc-xdef?
60    #:mode 'code
61    ))
62
63 (define (write-any x)
64   (write-char (cond ((char? x) x)
65                     ((number? x) (integer->char (if (>= x 0) x (+ x 256))))
66                     (else (stderr "write-any: ~a\n" x) barf))))
67
68 (define (ast:function? o)
69   (and (pair? o) (eq? (car o) 'fctn-defn)))
70
71 (define (.name o)
72   (pmatch o
73     ((fctn-defn _ (ftn-declr (ident ,name) _) _) name)
74     ((fctn-defn _ (ptr-declr (pointer) (ftn-declr (ident ,name) _)) _) name)
75     ((param-decl _ (param-declr (ident ,name))) name)
76     ((param-decl _ (param-declr (ptr-declr (pointer) (ident ,name)))) name)
77     ((param-decl _ (param-declr (ptr-declr (pointer) (array-of (ident ,name))))) name)
78     (_
79      (format (current-error-port) "SKIP .name =~a\n" o))))
80
81 (define (.statements o)
82   (pmatch o
83     ((fctn-defn _ (ftn-declr (ident ,name) _) (compd-stmt (block-item-list . ,statements))) statements)
84     ((fctn-defn _ (ptr-declr (pointer) (ftn-declr (ident ,name) _)) (compd-stmt (block-item-list . ,statements))) statements)))
85
86 (define <info> '<info>)
87 (define <functions> '<functions>)
88 (define <globals> '<globals>)
89 (define <locals> '<locals>)
90 (define <text> '<text>)
91 (define* (make o #:key (functions '()) (globals '()) (locals '()) (text '()))
92   (pmatch o
93     (<info> (list <info>
94                   (cons <functions> functions)
95                   (cons <globals> globals)
96                   (cons <locals> locals)
97                   (cons <text> text)))))
98
99 (define (.functions o)
100   (pmatch o
101     ((<info> . ,alist) (assq-ref alist <functions>))))
102
103 (define (.globals o)
104   (pmatch o
105     ((<info> . ,alist) (assq-ref alist <globals>))))
106
107 (define (.locals o)
108   (pmatch o
109     ((<info> . ,alist) (assq-ref alist <locals>))))
110
111 (define (.text o)
112   (pmatch o
113     ((<info> . ,alist) (assq-ref alist <text>))))
114
115 (define (info? o)
116   (and (pair? o) (eq? (car o) <info>)))
117
118 (define (clone o . rest)
119   (cond ((info? o)
120          (let ((functions (.functions o))
121                (globals (.globals o))
122                (locals (.locals o))
123                (text (.text o)))
124            (let-keywords rest
125                          #f
126                          ((functions functions)
127                           (globals globals)
128                           (locals locals)
129                           (text text))
130                          (make <info> #:functions functions #:globals globals #:locals locals #:text text))))))
131
132 (define (ref-local locals)
133   (lambda (o)
134     ;; (stderr "IDENT REF[~a]: ~a => ~a\n" o (assoc-ref locals o) (i386:ref-local (assoc-ref locals o)))
135     (i386:ref-local (assoc-ref locals o))))
136
137 (define (ref-global globals)
138   (lambda (o)
139     (lambda (f g t d)
140       (i386:ref-global (+ (data-offset o g;;lobals
141                                        ) d)))))
142
143 (define (expr->arg globals locals) ;; FIXME: get Mes curried-definitions
144   (lambda (o)
145     (pmatch o
146       ((p-expr (fixed ,value)) (string->number value))
147       ((p-expr (string ,string)) ((ref-global globals) string))
148       ((p-expr (ident ,name)) ((ref-local locals) name))
149
150       ((array-ref (p-expr (fixed ,value)) (p-expr (ident ,name)))
151        (let ((value (string->number value))
152              (size 4)) ;; FIXME: type: int
153          (lambda (f g t d)
154            (append
155             ((ident->base locals) name)
156             (i386:value->accu (* size value)) ;; FIXME: type: int
157             (i386:mem->accu) ;; FIXME: type: int
158             (i386:push-accu) ;; hmm
159             ))))
160
161       (_
162        (format (current-error-port) "SKIP expr->arg=~a\n" o)     
163        0))))
164
165 (define (ident->accu locals)
166   (lambda (o)
167     (i386:local->accu (assoc-ref locals o))))
168
169 (define (accu->ident locals)
170   (lambda (o)
171     (i386:accu->local (assoc-ref locals o))))
172
173 (define (ident->base locals)
174   (lambda (o)
175     (i386:local->base (assoc-ref locals o))))
176
177 (define (expr->accu info)
178   (lambda (o)
179     (pmatch o
180       ((p-expr (fixed ,value)) (string->number value))
181       ((p-expr (ident ,name)) ((ident->accu (.locals info)) name))
182       (_
183        (format (current-error-port) "SKIP expr-accu=~a\n" o)
184        0)
185       )))
186
187 (define (string->global string)
188   (cons string (append (string->list string) (list #\nul))))
189
190 (define (expr->global o)
191   (pmatch o
192     ((p-expr (string ,string)) (string->global string))
193     (_ #f)))
194
195 (define (dec->hex o)
196   (number->string o 16))
197
198 (define (byte->hex o)
199   (string->number (string-drop o 2) 16))
200
201 (define (asm->hex o)
202   (let ((prefix ".byte "))
203     (if (not (string-prefix? prefix o)) (begin (stderr "SKIP:~a\n" o)'())
204         (let ((s (string-drop o (string-length prefix))))
205           (map byte->hex (string-split s #\space))))))
206
207 (define (ast->info info)
208   (lambda (o)
209     (let ((globals (.globals info))
210           (locals (.locals info))
211           (text (.text info)))
212       (define (add-local name)
213          (acons name (1+ (or (and=> (member 1 (map cdr locals)) length) 0)) locals))
214
215       ;; (stderr "S=~a\n" o)
216       ;; (stderr "   info=~a\n" info)
217       ;; (stderr "   globals=~a\n" globals)
218       (pmatch o
219         (((trans-unit . _) . _) ((ast-list->info info) o))
220         ((trans-unit . ,elements) ((ast-list->info info) elements))
221         ((fctn-defn . _) ((function->info info) o))
222         ((comment . _) info)
223         ((cpp-stmt (define (name ,name) (repl ,value)))
224          (stderr "SKIP: #define ~a ~a\n" name value)
225          info)
226
227         ((compd-stmt (block-item-list . ,statements)) ((ast-list->info info) statements))
228         
229         ((expr-stmt (fctn-call (p-expr (ident ,name))
230                                (expr-list (p-expr (string ,string)))))
231          ;;(stderr "S1 string=~a\n" string)
232          (if (equal? name "asm") (clone info #:text (append text (list (lambda (f g t d) (asm->hex string)))))
233              (let ((globals (append globals (list (string->global string)))))
234                (clone info #:text
235                       (append text (list (lambda (f g t d)
236                                            (i386:call f g t d
237                                                       (+ t (function-offset name f))
238                                                       (+ d (data-offset string globals
239                                                                         ))))))
240                       #:globals globals))))
241         
242         ((expr-stmt (fctn-call (p-expr (ident ,name)) (expr-list . ,expr-list)))
243          ;;(stderr "S1 expr-list=~a\n" expr-list)
244          (let* ((globals (append globals (filter-map expr->global expr-list)))
245                 (args (map (expr->arg globals locals) expr-list)))
246            (clone info #:text
247                   (append text (list (lambda (f g t d)
248                                        (apply i386:call (cons* f g t d
249                                                                (+ t (function-offset name f)) args)))))
250                   #:globals globals)))
251
252         ((if (gt (p-expr (ident ,name)) (p-expr (fixed ,value))) ,body)
253          (let* ((value (string->number value))
254                 (info (clone info #:text '()))
255                 (body-info ((ast->info info) body))
256                 (body-text (.text body-info))
257                 (body-length (length (text->list body-text))))
258
259            (clone info #:text
260                   (append text
261                           (list (lambda (f g t d)
262                                   (append
263                                    (i386:local-test (assoc-ref locals name) value)
264                                    (i386:jump-le body-length))))
265                           body-text)
266                   #:globals (.globals body-info))))
267
268         ((while ,test ,body)
269          (let* ((info (clone info #:text '()))
270                 (body-info ((ast->info info) body))
271                 (body-text (.text body-info))
272                 (body-length (length (text->list body-text)))
273
274                 (test-info ((ast->info info) test))
275                 (test-text (.text test-info))
276                 (test-length (length (text->list test-text))))
277
278            (clone info #:text
279                   (append text
280                           (list (lambda (f g t d) (i386:jump body-length)))
281                           body-text
282                           test-text
283                           (list (lambda (f g t d) (i386:jump-nz (- (+ body-length test-length))))))
284                   #:globals (.globals body-info))))
285
286         ((array-ref (p-expr (fixed ,value)) (p-expr (ident ,name)))
287          (let ((value (string->number value)))
288            (clone info #:text
289                   (append text (list (lambda (f g t d)
290                                        (append
291                                         ((ident->base locals) name)
292                                         (i386:value->accu value)
293                                         (i386:mem-byte->accu)))))))) ; FIXME: type: char
294         
295         ((array-ref (p-expr (ident ,name)) (p-expr (ident ,index)))
296          (clone info #:text
297                 (append text (list (lambda (f g t d)
298                                      (append
299                                       ((ident->base locals) name)
300                                       ((ident->accu locals) index)
301                                       (i386:mem-byte->accu))))))) ; FIXME: type: char
302         
303         ((expr-stmt (post-inc (p-expr (ident ,name))))
304          (clone info #:text
305                 (append text (list (lambda (f g t d)
306                                      (i386:local-add (assoc-ref locals name) 1))))))
307
308         ((return ,expr)
309          (clone info #:text
310                 (append text (list (i386:ret ((expr->accu info) expr))))))
311
312         ;; int i;
313         ((decl (decl-spec-list (type-spec (fixed-type ,type))) (init-declr-list (init-declr (ident ,name))))
314          (clone info #:locals (add-local name)))
315
316         ((decl (decl-spec-list (type-spec (fixed-type ,type))) (init-declr-list (init-declr (ident ,name) (initzer (p-expr (fixed ,value))))))
317          (let ((locals (add-local name)))
318            (let ((value (string->number value)))
319              (clone info #:text
320                     (append text (list (lambda (f g t d)
321                                        (i386:local-assign (assoc-ref locals name) value))))
322                   #:locals locals))))
323
324         ;; int i = argc;
325         ((decl (decl-spec-list (type-spec (fixed-type ,type))) (init-declr-list (init-declr (ident ,name) (initzer (p-expr (ident ,local))))))
326          (let ((locals (add-local name)))
327           (clone info #:text
328                  (append text (list (lambda (f g t d)
329                                       (append
330                                        ((ident->accu locals) local)
331                                        ((accu->ident locals) name)))))
332                  #:locals locals)))
333
334         ;; SCM i = argc;
335         ((decl (decl-spec-list (type-spec (typename ,type))) (init-declr-list (init-declr (ident ,name) (initzer (p-expr (ident ,local))))))
336          (let ((locals (add-local name)))
337            (clone info #:text
338                 (append text (list (lambda (f g t d)
339                                      (append
340                                       ((ident->accu locals) local)
341                                       ((accu->ident locals) name)))))
342                 #:locals locals)))
343         
344         ;; int i = f ();
345         ((decl (decl-spec-list (type-spec (fixed-type ,type))) (init-declr-list (init-declr (ident ,name) (initzer (fctn-call . ,call)))))
346          (let* ((locals (add-local name))
347                 (info (clone info #:locals locals)))
348            (let ((info ((ast->info info) `(expr-stmt (fctn-call ,@call)))))
349              (clone info
350                     #:text
351                     (append (.text info)
352                             (list (lambda (f g t d)
353                                     (i386:ret-local (assoc-ref locals name)))))
354                     #:locals locals))))
355         
356         ;; i = 0;
357         ((expr-stmt (assn-expr (p-expr (ident ,name)) (op _) (p-expr (fixed ,value))))
358          ;;(stderr "RET LOCAL[~a]: ~a\n" name (assoc-ref locals name))
359          (let ((value (string->number value)))
360            (clone info #:text (append text (list (lambda (f g t d) (i386:local-assign (assoc-ref locals name) value)))))))
361         
362         ((expr-stmt (assn-expr (p-expr (ident ,name)) (op _) (fctn-call . ,call)))
363          (let* ((info ((ast->info info) `(expr-stmt (fctn-call ,@call)))))
364            (clone info #:text (append (.text info) (list (lambda (f g t d) (i386:ret-local (assoc-ref locals name))))))))
365
366         (_
367          (format (current-error-port) "SKIP statement=~a\n" o)
368          info)))))
369
370 (define (info->exe info)
371   (display "dumping elf\n" (current-error-port))
372   (map write-any (make-elf (.functions info) (.globals info))))
373
374 (define (.formals o)
375   (pmatch o
376     ((fctn-defn _ (ftn-declr _ ,formals) _) formals)
377     ((fctn-defn _ (ptr-declr (pointer) (ftn-declr _ ,formals)) _) formals)
378     (_ (format (current-error-port) ".formals: no match: ~a\n" o)
379        barf)))
380
381 (define (formal->text n)
382   (lambda (o i)
383     ;;(i386:formal i n)
384     '()
385     ))
386
387 (define (formals->text o)
388   (pmatch o
389     ((param-list . ,formals)
390      (let ((n (length formals)))
391        (list (lambda (f g t d)
392                (append
393                 (i386:function-preamble)
394                 (append-map (formal->text n) formals (iota n))
395                 (i386:function-locals))))))
396     (_ (format (current-error-port) "formals->text: no match: ~a\n" o)
397        barf)))
398
399 (define (formals->locals o)
400   (pmatch o
401     ((param-list . ,formals)
402      (let ((n (length formals)))
403        ;;(stderr "FORMALS: ~a ==> ~a\n" formals n)
404        (map cons (map .name formals) (iota n -2 -1))))
405     (_ (format (current-error-port) "formals->info: no match: ~a\n" o)
406        barf)))
407
408 (define (function->info info)
409   (lambda (o)
410     ;;(stderr "\n")
411     (format (current-error-port) "compiling ~a\n" (.name o))
412     ;;(stderr "formals=~a\n" (.formals o))
413     (let* ((text (formals->text (.formals o)))
414            (locals (formals->locals (.formals o))))
415       ;;(stderr "locals=~a\n" locals)
416       (let loop ((statements (.statements o))
417                  (info (clone info #:locals locals #:text text)))
418         (if (null? statements) (clone info
419                                       #:functions (append (.functions info) (list (cons (.name o) (.text info)))))
420             (let* ((statement (car statements)))
421               (loop (cdr statements) ((ast->info info) (car statements)))))))))
422
423 (define (ast-list->info info)
424   (lambda (elements)
425     (let loop ((elements elements) (info info))
426       (if (null? elements) info
427           (loop (cdr elements) ((ast->info info) (car elements)))))))
428
429 (define _start
430   (let* ((argc-argv
431           (string-append ".byte"
432                          " 0x89 0xe8"      ; mov    %ebp,%eax
433                          " 0x83 0xc0 0x08" ; add    $0x8,%eax
434                          " 0x50"           ; push   %eax
435                          " 0x89 0xe8"      ; mov    %ebp,%eax
436                          " 0x83 0xc0 0x04" ; add    $0x4,%eax
437                          " 0x0f 0xb6 0x00" ; movzbl (%eax),%eax
438                          " 0x50"           ; push   %eax
439                          ))
440          (ast (with-input-from-string
441                   
442                   (string-append "int _start () {int i;asm(\"" argc-argv "\");i=main ();exit (i);}")
443                 parse-c99)))
444     ast))
445
446 (define strlen
447   (let* ((ast (with-input-from-string
448                   "
449 int
450 strlen (char const* s)
451 {
452   int i = 0;
453   while (s[i]) i++;
454   return i;
455 }
456 "
457 ;;paredit:"
458                 parse-c99)))
459     ast))
460
461 (define eputs
462   (let* ((ast (with-input-from-string
463                   "
464 int
465 eputs (char const* s)
466 {
467   //write (STDERR, s, strlen (s));
468   //write (2, s, strlen (s));
469   int i = strlen (s);
470   write (2, s, i);
471   return 0;
472 }
473 "
474 ;;paredit:"
475                 parse-c99)))
476     ast))
477
478 (define fputs
479   (let* ((ast (with-input-from-string
480                   "
481 int
482 fputs (char const* s, int fd)
483 {
484  int i = strlen (s);
485   write (fd, s, i);
486   return 0;
487 }
488 "
489 ;;paredit:"
490                 parse-c99)))
491     ast))
492
493 (define puts
494   (let* ((ast (with-input-from-string
495                   "
496 int
497 puts (char const* s)
498 {
499   //write (STDOUT, s, strlen (s));
500   //int i = write (STDOUT, s, strlen (s));
501   int i = strlen (s);
502   write (1, s, i);
503   return 0;
504 }
505 "
506 ;;paredit:"
507                 parse-c99)))
508     ast))
509
510 (define i386:libc
511   (list
512    (cons "exit" (list i386:exit))
513    (cons "write" (list i386:write))))
514
515 (define libc
516   (list
517    strlen
518    eputs
519    fputs
520    puts))
521
522 (define (compile)
523   (let* ((ast (mescc))
524          (info (make <info> #:functions i386:libc))
525          (info ((ast->info info) libc))
526          (info ((ast->info info) ast))
527          (info ((ast->info info) _start)))
528     (info->exe info)))