acc.cpp revision 5b65909f93f7c35fc1e7aaf7dccc2198e30d17d1 
1/*
2 * Android "Almost" C Compiler.
3 * This is a compiler for a small subset of the C language, intended for use
4 * in scripting environments where speed and memory footprint are important.
5 *
6 * This code is based upon the "unobfuscated" version of the
7 * Obfuscated Tiny C compiler, see the file LICENSE for details.
8 *
9 */
10
11#include <ctype.h>
12#include <errno.h>
13#include <stdarg.h>
14#include <stdint.h>
15#include <stdio.h>
16#include <stdlib.h>
17#include <string.h>
18#include <cutils/hashmap.h>
19
20#if defined(__i386__)
21#include <sys/mman.h>
22#endif
23
24#if defined(__arm__)
25#include <unistd.h>
26#endif
27
28#if defined(__arm__)
29#define DEFAULT_ARM_CODEGEN
30#define PROVIDE_ARM_CODEGEN
31#elif defined(__i386__)
32#define DEFAULT_X86_CODEGEN
33#define PROVIDE_X86_CODEGEN
34#elif defined(__x86_64__)
35#define DEFAULT_X64_CODEGEN
36#define PROVIDE_X64_CODEGEN
37#endif
38
39#ifdef PROVIDE_ARM_CODEGEN
40#include "disassem.h"
41#endif
42
43#include <acc/acc.h>
44
45#define LOG_API(...) do {} while(0)
46// #define LOG_API(...) fprintf (stderr, __VA_ARGS__)
47
48#define LOG_STACK(...) do {} while(0)
49// #define LOG_STACK(...) fprintf (stderr, __VA_ARGS__)
50
51#define ENABLE_ARM_DISASSEMBLY
52// #define PROVIDE_TRACE_CODEGEN
53
54namespace acc {
55
56// Subset of STL vector.
57template<class E> class Vector {
58    public:
59    Vector() {
60        mpBase = 0;
61        mUsed = 0;
62        mSize = 0;
63    }
64
65    ~Vector() {
66        if (mpBase) {
67            for(size_t i = 0; i < mUsed; i++)  {
68                mpBase[mUsed].~E();
69            }
70            free(mpBase);
71        }
72    }
73
74    inline E& operator[](size_t i) {
75        return mpBase[i];
76    }
77
78    inline E& front() {
79        return mpBase[0];
80    }
81
82    inline E& back() {
83        return mpBase[mUsed - 1];
84    }
85
86    void pop_back() {
87        mUsed -= 1;
88        mpBase[mUsed].~E();
89    }
90
91    void push_back(const E& item) {
92        * ensure(1) = item;
93    }
94
95    size_t size() {
96        return mUsed;
97    }
98
99private:
100    E* ensure(int n) {
101        size_t newUsed = mUsed + n;
102        if (newUsed > mSize) {
103            size_t newSize = mSize * 2 + 10;
104            if (newSize < newUsed) {
105                newSize = newUsed;
106            }
107            mpBase = (E*) realloc(mpBase, sizeof(E) * newSize);
108            mSize = newSize;
109        }
110        E* result = mpBase + mUsed;
111        mUsed = newUsed;
112        return result;
113    }
114
115    E* mpBase;
116    size_t mUsed;
117    size_t mSize;
118};
119
120class ErrorSink {
121public:
122    void error(const char *fmt, ...) {
123        va_list ap;
124        va_start(ap, fmt);
125        verror(fmt, ap);
126        va_end(ap);
127    }
128
129    virtual ~ErrorSink() {}
130    virtual void verror(const char* fmt, va_list ap) = 0;
131};
132
133class Compiler : public ErrorSink {
134    typedef int tokenid_t;
135    enum TypeTag {
136        TY_INT, TY_CHAR, TY_VOID, TY_FLOAT, TY_DOUBLE,
137        TY_POINTER, TY_FUNC, TY_PARAM
138    };
139
140    struct Type {
141        TypeTag tag;
142        tokenid_t id; // For function arguments
143        Type* pHead;
144        Type* pTail;
145    };
146
147    enum ExpressionType {
148        ET_RVALUE,
149        ET_LVALUE
150    };
151
152    struct ExpressionValue {
153        ExpressionValue() {
154            et = ET_RVALUE;
155            pType = NULL;
156        }
157        ExpressionType et;
158        Type* pType;
159    };
160
161    class CodeBuf {
162        char* ind; // Output code pointer
163        char* pProgramBase;
164        ErrorSink* mErrorSink;
165        int mSize;
166        bool mOverflowed;
167
168        void release() {
169            if (pProgramBase != 0) {
170                free(pProgramBase);
171                pProgramBase = 0;
172            }
173        }
174
175        bool check(int n) {
176            int newSize = ind - pProgramBase + n;
177            bool overflow = newSize > mSize;
178            if (overflow && !mOverflowed) {
179                mOverflowed = true;
180                if (mErrorSink) {
181                    mErrorSink->error("Code too large: %d bytes", newSize);
182                }
183            }
184            return overflow;
185        }
186
187    public:
188        CodeBuf() {
189            pProgramBase = 0;
190            ind = 0;
191            mErrorSink = 0;
192            mSize = 0;
193            mOverflowed = false;
194        }
195
196        ~CodeBuf() {
197            release();
198        }
199
200        void init(int size) {
201            release();
202            mSize = size;
203            pProgramBase = (char*) calloc(1, size);
204            ind = pProgramBase;
205        }
206
207        void setErrorSink(ErrorSink* pErrorSink) {
208            mErrorSink = pErrorSink;
209        }
210
211        int o4(int n) {
212            if(check(4)) {
213                return 0;
214            }
215            intptr_t result = (intptr_t) ind;
216            * (int*) ind = n;
217            ind += 4;
218            return result;
219        }
220
221        /*
222         * Output a byte. Handles all values, 0..ff.
223         */
224        void ob(int n) {
225            if(check(1)) {
226                return;
227            }
228            *ind++ = n;
229        }
230
231        inline void* getBase() {
232            return (void*) pProgramBase;
233        }
234
235        intptr_t getSize() {
236            return ind - pProgramBase;
237        }
238
239        intptr_t getPC() {
240            return (intptr_t) ind;
241        }
242    };
243
244    /**
245     * A code generator creates an in-memory program, generating the code on
246     * the fly. There is one code generator implementation for each supported
247     * architecture.
248     *
249     * The code generator implements the following abstract machine:
250     * R0 - the accumulator.
251     * FP - a frame pointer for accessing function arguments and local
252     *      variables.
253     * SP - a stack pointer for storing intermediate results while evaluating
254     *      expressions. The stack pointer grows downwards.
255     *
256     * The function calling convention is that all arguments are placed on the
257     * stack such that the first argument has the lowest address.
258     * After the call, the result is in R0. The caller is responsible for
259     * removing the arguments from the stack.
260     * The R0 register is not saved across function calls. The
261     * FP and SP registers are saved.
262     */
263
264    class CodeGenerator {
265    public:
266        CodeGenerator() {
267            mErrorSink = 0;
268            pCodeBuf = 0;
269            pushType();
270        }
271        virtual ~CodeGenerator() {}
272
273        virtual void init(CodeBuf* pCodeBuf) {
274            this->pCodeBuf = pCodeBuf;
275            pCodeBuf->setErrorSink(mErrorSink);
276        }
277
278        virtual void setErrorSink(ErrorSink* pErrorSink) {
279            mErrorSink = pErrorSink;
280            if (pCodeBuf) {
281                pCodeBuf->setErrorSink(mErrorSink);
282            }
283        }
284
285        /* Give the code generator some utility types so it can
286         * use its own types as needed for the results of some
287         * operations like gcmp.
288         */
289
290        void setTypes(Type* pInt) {
291            mkpInt = pInt;
292        }
293
294        /* Emit a function prolog.
295         * pDecl is the function declaration, which gives the arguments.
296         * Save the old value of the FP.
297         * Set the new value of the FP.
298         * Convert from the native platform calling convention to
299         * our stack-based calling convention. This may require
300         * pushing arguments from registers to the stack.
301         * Allocate "N" bytes of stack space. N isn't known yet, so
302         * just emit the instructions for adjusting the stack, and return
303         * the address to patch up. The patching will be done in
304         * functionExit().
305         * returns address to patch with local variable size.
306        */
307        virtual int functionEntry(Type* pDecl) = 0;
308
309        /* Emit a function epilog.
310         * Restore the old SP and FP register values.
311         * Return to the calling function.
312         * argCount - the number of arguments to the function.
313         * localVariableAddress - returned from functionEntry()
314         * localVariableSize - the size in bytes of the local variables.
315         */
316        virtual void functionExit(Type* pDecl, int localVariableAddress,
317                                  int localVariableSize) = 0;
318
319        /* load immediate value to R0 */
320        virtual void li(int i) = 0;
321
322        /* Load floating point value from global address. */
323        virtual void loadFloat(int address, Type* pType) = 0;
324
325        /* Jump to a target, and return the address of the word that
326         * holds the target data, in case it needs to be fixed up later.
327         */
328        virtual int gjmp(int t) = 0;
329
330        /* Test R0 and jump to a target if the test succeeds.
331         * l = 0: je, l == 1: jne
332         * Return the address of the word that holds the targed data, in
333         * case it needs to be fixed up later.
334         */
335        virtual int gtst(bool l, int t) = 0;
336
337        /* Compare TOS against R0, and store the boolean result in R0.
338         * Pops TOS.
339         * op specifies the comparison.
340         */
341        virtual void gcmp(int op) = 0;
342
343        /* Perform the arithmetic op specified by op. TOS is the
344         * left argument, R0 is the right argument.
345         * Pops TOS.
346         */
347        virtual void genOp(int op) = 0;
348
349        /* Compare 0 against R0, and store the boolean result in R0.
350         * op specifies the comparison.
351         */
352        virtual void gUnaryCmp(int op) = 0;
353
354        /* Perform the arithmetic op specified by op. 0 is the
355         * left argument, R0 is the right argument.
356         */
357        virtual void genUnaryOp(int op) = 0;
358
359        /* Push R0 onto the stack. (Also known as "dup" for duplicate.)
360         */
361        virtual void pushR0() = 0;
362
363        /* Turn R0, TOS into R0 TOS R0 */
364
365        virtual void over() = 0;
366
367        /* Pop R0 from the stack. (Also known as "drop")
368         */
369        virtual void popR0() = 0;
370
371        /* Store R0 to the address stored in TOS.
372         * The TOS is popped.
373         */
374        virtual void storeR0ToTOS() = 0;
375
376        /* Load R0 from the address stored in R0.
377         */
378        virtual void loadR0FromR0() = 0;
379
380        /* Load the absolute address of a variable to R0.
381         * If ea <= LOCAL, then this is a local variable, or an
382         * argument, addressed relative to FP.
383         * else it is an absolute global address.
384         *
385         * et is ET_RVALUE for things like string constants, ET_LVALUE for
386         * variables.
387         */
388        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) = 0;
389
390        /* Load the pc-relative address of a forward-referenced variable to R0.
391         * Return the address of the 4-byte constant so that it can be filled
392         * in later.
393         */
394        virtual int leaForward(int ea, Type* pPointerType) = 0;
395
396        /**
397         * Convert R0 to the given type.
398         */
399        virtual void convertR0(Type* pType) = 0;
400
401        /* Emit code to adjust the stack for a function call. Return the
402         * label for the address of the instruction that adjusts the
403         * stack size. This will be passed as argument "a" to
404         * endFunctionCallArguments.
405         */
406        virtual int beginFunctionCallArguments() = 0;
407
408        /* Emit code to store R0 to the stack at byte offset l.
409         * Returns stack size of object (typically 4 or 8 bytes)
410         */
411        virtual size_t storeR0ToArg(int l, Type* pArgType) = 0;
412
413        /* Patch the function call preamble.
414         * a is the address returned from beginFunctionCallArguments
415         * l is the number of bytes the arguments took on the stack.
416         * Typically you would also emit code to convert the argument
417         * list into whatever the native function calling convention is.
418         * On ARM for example you would pop the first 5 arguments into
419         * R0..R4
420         */
421        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) = 0;
422
423        /* Emit a call to an unknown function. The argument "symbol" needs to
424         * be stored in the location where the address should go. It forms
425         * a chain. The address will be patched later.
426         * Return the address of the word that has to be patched.
427         */
428        virtual int callForward(int symbol, Type* pFunc) = 0;
429
430        /* Call a function pointer. L is the number of bytes the arguments
431         * take on the stack. The address of the function is stored at
432         * location SP + l.
433         */
434        virtual void callIndirect(int l, Type* pFunc) = 0;
435
436        /* Adjust SP after returning from a function call. l is the
437         * number of bytes of arguments stored on the stack. isIndirect
438         * is true if this was an indirect call. (In which case the
439         * address of the function is stored at location SP + l.)
440         */
441        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) = 0;
442
443        /* Print a disassembly of the assembled code to out. Return
444         * non-zero if there is an error.
445         */
446        virtual int disassemble(FILE* out) = 0;
447
448        /* Generate a symbol at the current PC. t is the head of a
449         * linked list of addresses to patch.
450         */
451        virtual void gsym(int t) = 0;
452
453        /* Resolve a forward reference function at the current PC.
454         * t is the head of a
455         * linked list of addresses to patch.
456         * (Like gsym, but using absolute address, not PC relative address.)
457         */
458        virtual void resolveForward(int t) = 0;
459
460        /*
461         * Do any cleanup work required at the end of a compile.
462         * For example, an instruction cache might need to be
463         * invalidated.
464         * Return non-zero if there is an error.
465         */
466        virtual int finishCompile() = 0;
467
468        /**
469         * Adjust relative branches by this amount.
470         */
471        virtual int jumpOffset() = 0;
472
473        /**
474         * Memory alignment (in bytes) for this type of data
475         */
476        virtual size_t alignmentOf(Type* type) = 0;
477
478        /**
479         * Array element alignment (in bytes) for this type of data.
480         */
481        virtual size_t sizeOf(Type* type) = 0;
482
483        /**
484         * Stack alignment of this type of data
485         */
486        virtual size_t stackAlignmentOf(Type* pType) = 0;
487
488        /**
489         * Argument stack argument size of this data type.
490         */
491        virtual size_t stackSizeOf(Type* pType) = 0;
492
493        virtual Type* getR0Type() {
494            return mExpressionStack.back().pType;
495        }
496
497        virtual ExpressionType getR0ExpressionType() {
498            return mExpressionStack.back().et;
499        }
500
501        virtual void setR0ExpressionType(ExpressionType et) {
502            mExpressionStack.back().et = et;
503        }
504
505        virtual size_t getExpressionStackDepth() {
506            return mExpressionStack.size();
507        }
508
509        virtual void forceR0RVal() {
510            if (getR0ExpressionType() == ET_LVALUE) {
511                loadR0FromR0();
512            }
513        }
514
515    protected:
516        /*
517         * Output a byte. Handles all values, 0..ff.
518         */
519        void ob(int n) {
520            pCodeBuf->ob(n);
521        }
522
523        intptr_t o4(int data) {
524            return pCodeBuf->o4(data);
525        }
526
527        intptr_t getBase() {
528            return (intptr_t) pCodeBuf->getBase();
529        }
530
531        intptr_t getPC() {
532            return pCodeBuf->getPC();
533        }
534
535        intptr_t getSize() {
536            return pCodeBuf->getSize();
537        }
538
539        void error(const char* fmt,...) {
540            va_list ap;
541            va_start(ap, fmt);
542            mErrorSink->verror(fmt, ap);
543            va_end(ap);
544        }
545
546        void assert(bool test) {
547            if (!test) {
548                * (char*) 0 = 0;
549                error("code generator assertion failed.");
550            }
551        }
552
553        void setR0Type(Type* pType) {
554            assert(pType != NULL);
555            mExpressionStack.back().pType = pType;
556            mExpressionStack.back().et = ET_RVALUE;
557        }
558
559        void setR0Type(Type* pType, ExpressionType et) {
560            assert(pType != NULL);
561            mExpressionStack.back().pType = pType;
562            mExpressionStack.back().et = et;
563        }
564
565        Type* getTOSType() {
566            return mExpressionStack[mExpressionStack.size()-2].pType;
567        }
568
569        void pushType() {
570            if (mExpressionStack.size()) {
571                mExpressionStack.push_back(mExpressionStack.back());
572            } else {
573                mExpressionStack.push_back(ExpressionValue());
574            }
575
576        }
577
578        void overType() {
579            size_t size = mExpressionStack.size();
580            if (size >= 2) {
581                mExpressionStack.push_back(mExpressionStack.back());
582                mExpressionStack[size-1] = mExpressionStack[size-2];
583                mExpressionStack[size-2] = mExpressionStack[size];
584            }
585        }
586
587        void popType() {
588            mExpressionStack.pop_back();
589        }
590
591        bool bitsSame(Type* pA, Type* pB) {
592            return collapseType(pA->tag) == collapseType(pB->tag);
593        }
594
595        TypeTag collapseType(TypeTag tag) {
596            static const TypeTag collapsedTag[] = {
597                    TY_INT, TY_INT, TY_VOID, TY_FLOAT, TY_DOUBLE, TY_INT,
598                    TY_VOID, TY_VOID};
599            return collapsedTag[tag];
600        }
601
602        TypeTag collapseTypeR0() {
603            return collapseType(getR0Type()->tag);
604        }
605
606        bool isFloatType(Type* pType) {
607            return isFloatTag(pType->tag);
608        }
609
610        bool isFloatTag(TypeTag tag) {
611            return tag == TY_FLOAT || tag == TY_DOUBLE;
612        }
613
614        Type* mkpInt;
615
616    private:
617        Vector<ExpressionValue> mExpressionStack;
618        CodeBuf* pCodeBuf;
619        ErrorSink* mErrorSink;
620    };
621
622#ifdef PROVIDE_ARM_CODEGEN
623
624    class ARMCodeGenerator : public CodeGenerator {
625    public:
626        ARMCodeGenerator() {}
627
628        virtual ~ARMCodeGenerator() {}
629
630        /* returns address to patch with local variable size
631        */
632        virtual int functionEntry(Type* pDecl) {
633            mStackUse = 0;
634            // sp -> arg4 arg5 ...
635            // Push our register-based arguments back on the stack
636            int regArgCount = calcRegArgCount(pDecl);
637            if (regArgCount > 0) {
638                mStackUse += regArgCount * 4;
639                o4(0xE92D0000 | ((1 << regArgCount) - 1)); // stmfd    sp!, {}
640            }
641            // sp -> arg0 arg1 ...
642            o4(0xE92D4800); // stmfd sp!, {fp, lr}
643            mStackUse += 2 * 4;
644            // sp, fp -> oldfp, retadr, arg0 arg1 ....
645            o4(0xE1A0B00D); // mov    fp, sp
646            LOG_STACK("functionEntry: %d\n", mStackUse);
647            return o4(0xE24DD000); // sub    sp, sp, # <local variables>
648            // We don't know how many local variables we are going to use,
649            // but we will round the allocation up to a multiple of
650            // STACK_ALIGNMENT, so it won't affect the stack alignment.
651        }
652
653        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
654            // Round local variable size up to a multiple of stack alignment
655            localVariableSize = ((localVariableSize + STACK_ALIGNMENT - 1) /
656                STACK_ALIGNMENT) * STACK_ALIGNMENT;
657            // Patch local variable allocation code:
658            if (localVariableSize < 0 || localVariableSize > 255) {
659                error("localVariables out of range: %d", localVariableSize);
660            }
661            *(char*) (localVariableAddress) = localVariableSize;
662
663            // sp -> locals .... fp -> oldfp, retadr, arg0, arg1, ...
664            o4(0xE1A0E00B); // mov lr, fp
665            o4(0xE59BB000); // ldr fp, [fp]
666            o4(0xE28ED004); // add sp, lr, #4
667            // sp -> retadr, arg0, ...
668            o4(0xE8BD4000); // ldmfd    sp!, {lr}
669            // sp -> arg0 ....
670
671            // We store the PC into the lr so we can adjust the sp before
672            // returning. We need to pull off the registers we pushed
673            // earlier. We don't need to actually store them anywhere,
674            // just adjust the stack.
675            int regArgCount = calcRegArgCount(pDecl);
676            if (regArgCount) {
677                o4(0xE28DD000 | (regArgCount << 2)); // add sp, sp, #argCount << 2
678            }
679            o4(0xE12FFF1E); // bx lr
680        }
681
682        /* load immediate value */
683        virtual void li(int t) {
684            liReg(t, 0);
685            setR0Type(mkpInt);
686        }
687
688        virtual void loadFloat(int address, Type* pType) {
689            setR0Type(pType);
690            // Global, absolute address
691            o4(0xE59F0000); //        ldr r0, .L1
692            o4(0xEA000000); //        b .L99
693            o4(address);         // .L1:   .word ea
694                                 // .L99:
695
696            switch (pType->tag) {
697            case TY_FLOAT:
698                o4(0xE5900000);      // ldr r0, [r0]
699                break;
700            case TY_DOUBLE:
701                o4(0xE1C000D0);      // ldrd r0, [r0]
702                break;
703            default:
704                assert(false);
705                break;
706            }
707        }
708
709        virtual int gjmp(int t) {
710            return o4(0xEA000000 | encodeAddress(t)); // b .L33
711        }
712
713        /* l = 0: je, l == 1: jne */
714        virtual int gtst(bool l, int t) {
715            Type* pR0Type = getR0Type();
716            TypeTag tagR0 = pR0Type->tag;
717            switch(tagR0) {
718                case TY_FLOAT:
719                    callRuntime((void*) runtime_is_non_zero_f);
720                    break;
721                case TY_DOUBLE:
722                    callRuntime((void*) runtime_is_non_zero_d);
723                    break;
724                default:
725                    break;
726            }
727            o4(0xE3500000); // cmp r0,#0
728            int branch = l ? 0x1A000000 : 0x0A000000; // bne : beq
729            return o4(branch | encodeAddress(t));
730        }
731
732        virtual void gcmp(int op) {
733            Type* pR0Type = getR0Type();
734            Type* pTOSType = getTOSType();
735            TypeTag tagR0 = collapseType(pR0Type->tag);
736            TypeTag tagTOS = collapseType(pTOSType->tag);
737            if (tagR0 == TY_INT && tagTOS == TY_INT) {
738                setupIntPtrArgs();
739                o4(0xE1510000); // cmp r1, r1
740                switch(op) {
741                case OP_EQUALS:
742                    o4(0x03A00001); // moveq r0,#1
743                    o4(0x13A00000); // movne r0,#0
744                    break;
745                case OP_NOT_EQUALS:
746                    o4(0x03A00000); // moveq r0,#0
747                    o4(0x13A00001); // movne r0,#1
748                    break;
749                case OP_LESS_EQUAL:
750                    o4(0xD3A00001); // movle r0,#1
751                    o4(0xC3A00000); // movgt r0,#0
752                    break;
753                case OP_GREATER:
754                    o4(0xD3A00000); // movle r0,#0
755                    o4(0xC3A00001); // movgt r0,#1
756                    break;
757                case OP_GREATER_EQUAL:
758                    o4(0xA3A00001); // movge r0,#1
759                    o4(0xB3A00000); // movlt r0,#0
760                    break;
761                case OP_LESS:
762                    o4(0xA3A00000); // movge r0,#0
763                    o4(0xB3A00001); // movlt r0,#1
764                    break;
765                default:
766                    error("Unknown comparison op %d", op);
767                    break;
768                }
769            } else if (tagR0 == TY_DOUBLE || tagTOS == TY_DOUBLE) {
770                setupDoubleArgs();
771                switch(op) {
772                    case OP_EQUALS:
773                        callRuntime((void*) runtime_cmp_eq_dd);
774                        break;
775                    case OP_NOT_EQUALS:
776                        callRuntime((void*) runtime_cmp_ne_dd);
777                        break;
778                    case OP_LESS_EQUAL:
779                        callRuntime((void*) runtime_cmp_le_dd);
780                        break;
781                    case OP_GREATER:
782                        callRuntime((void*) runtime_cmp_gt_dd);
783                        break;
784                    case OP_GREATER_EQUAL:
785                        callRuntime((void*) runtime_cmp_ge_dd);
786                        break;
787                    case OP_LESS:
788                        callRuntime((void*) runtime_cmp_lt_dd);
789                        break;
790                    default:
791                        error("Unknown comparison op %d", op);
792                        break;
793                }
794            } else {
795                setupFloatArgs();
796                switch(op) {
797                    case OP_EQUALS:
798                        callRuntime((void*) runtime_cmp_eq_ff);
799                        break;
800                    case OP_NOT_EQUALS:
801                        callRuntime((void*) runtime_cmp_ne_ff);
802                        break;
803                    case OP_LESS_EQUAL:
804                        callRuntime((void*) runtime_cmp_le_ff);
805                        break;
806                    case OP_GREATER:
807                        callRuntime((void*) runtime_cmp_gt_ff);
808                        break;
809                    case OP_GREATER_EQUAL:
810                        callRuntime((void*) runtime_cmp_ge_ff);
811                        break;
812                    case OP_LESS:
813                        callRuntime((void*) runtime_cmp_lt_ff);
814                        break;
815                    default:
816                        error("Unknown comparison op %d", op);
817                        break;
818                }
819            }
820            setR0Type(mkpInt);
821        }
822
823        virtual void genOp(int op) {
824            Type* pR0Type = getR0Type();
825            Type* pTOSType = getTOSType();
826            TypeTag tagR0 = pR0Type->tag;
827            TypeTag tagTOS = pTOSType->tag;
828            bool isFloatR0 = isFloatTag(tagR0);
829            bool isFloatTOS = isFloatTag(tagTOS);
830            if (!isFloatR0 && !isFloatTOS) {
831                setupIntPtrArgs();
832                bool isPtrR0 = tagR0 == TY_POINTER;
833                bool isPtrTOS = tagTOS == TY_POINTER;
834                if (isPtrR0 || isPtrTOS) {
835                    if (isPtrR0 && isPtrTOS) {
836                        if (op != OP_MINUS) {
837                            error("Unsupported pointer-pointer operation %d.", op);
838                        }
839                        if (! typeEqual(pR0Type, pTOSType)) {
840                            error("Incompatible pointer types for subtraction.");
841                        }
842                        o4(0xE0410000); // sub     r0,r1,r0
843                        setR0Type(mkpInt);
844                        int size = sizeOf(pR0Type->pHead);
845                        if (size != 1) {
846                            pushR0();
847                            li(size);
848                            // TODO: Optimize for power-of-two.
849                            genOp(OP_DIV);
850                        }
851                    } else {
852                        if (! (op == OP_PLUS || (op == OP_MINUS && isPtrR0))) {
853                            error("Unsupported pointer-scalar operation %d", op);
854                        }
855                        Type* pPtrType = isPtrR0 ? pR0Type : pTOSType;
856                        int size = sizeOf(pPtrType->pHead);
857                        if (size != 1) {
858                            // TODO: Optimize for power-of-two.
859                            liReg(size, 2);
860                            if (isPtrR0) {
861                                o4(0x0E0010192); // mul     r1,r2,r1
862                            } else {
863                                o4(0x0E0000092); // mul     r0,r2,r0
864                            }
865                        }
866                        switch(op) {
867                            case OP_PLUS:
868                            o4(0xE0810000); // add     r0,r1,r0
869                            break;
870                            case OP_MINUS:
871                            o4(0xE0410000); // sub     r0,r1,r0
872                            break;
873                        }
874                        setR0Type(pPtrType);
875                    }
876                } else {
877                    switch(op) {
878                        case OP_MUL:
879                        o4(0x0E0000091); // mul     r0,r1,r0
880                        break;
881                        case OP_DIV:
882                        callRuntime((void*) runtime_DIV);
883                        break;
884                        case OP_MOD:
885                        callRuntime((void*) runtime_MOD);
886                        break;
887                        case OP_PLUS:
888                        o4(0xE0810000); // add     r0,r1,r0
889                        break;
890                        case OP_MINUS:
891                        o4(0xE0410000); // sub     r0,r1,r0
892                        break;
893                        case OP_SHIFT_LEFT:
894                        o4(0xE1A00011); // lsl     r0,r1,r0
895                        break;
896                        case OP_SHIFT_RIGHT:
897                        o4(0xE1A00051); // asr     r0,r1,r0
898                        break;
899                        case OP_BIT_AND:
900                        o4(0xE0010000); // and     r0,r1,r0
901                        break;
902                        case OP_BIT_XOR:
903                        o4(0xE0210000); // eor     r0,r1,r0
904                        break;
905                        case OP_BIT_OR:
906                        o4(0xE1810000); // orr     r0,r1,r0
907                        break;
908                        case OP_BIT_NOT:
909                        o4(0xE1E00000); // mvn     r0, r0
910                        break;
911                        default:
912                        error("Unimplemented op %d\n", op);
913                        break;
914                    }
915                }
916            } else {
917                Type* pResultType = tagR0 > tagTOS ? pR0Type : pTOSType;
918                if (pResultType->tag == TY_DOUBLE) {
919                    setupDoubleArgs();
920                    switch(op) {
921                    case OP_MUL:
922                        callRuntime((void*) runtime_op_mul_dd);
923                        break;
924                    case OP_DIV:
925                        callRuntime((void*) runtime_op_div_dd);
926                        break;
927                    case OP_PLUS:
928                        callRuntime((void*) runtime_op_add_dd);
929                        break;
930                    case OP_MINUS:
931                        callRuntime((void*) runtime_op_sub_dd);
932                        break;
933                    default:
934                        error("Unsupported binary floating operation %d\n", op);
935                        break;
936                    }
937                } else {
938                    setupFloatArgs();
939                    switch(op) {
940                    case OP_MUL:
941                        callRuntime((void*) runtime_op_mul_ff);
942                        break;
943                    case OP_DIV:
944                        callRuntime((void*) runtime_op_div_ff);
945                        break;
946                    case OP_PLUS:
947                        callRuntime((void*) runtime_op_add_ff);
948                        break;
949                    case OP_MINUS:
950                        callRuntime((void*) runtime_op_sub_ff);
951                        break;
952                    default:
953                        error("Unsupported binary floating operation %d\n", op);
954                        break;
955                    }
956                }
957                setR0Type(pResultType);
958            }
959        }
960
961        virtual void gUnaryCmp(int op) {
962            if (op != OP_LOGICAL_NOT) {
963                error("Unknown unary cmp %d", op);
964            } else {
965                Type* pR0Type = getR0Type();
966                TypeTag tag = collapseType(pR0Type->tag);
967                switch(tag) {
968                    case TY_INT:
969                        o4(0xE3A01000); // mov    r1, #0
970                        o4(0xE1510000); // cmp r1, r0
971                        o4(0x03A00001); // moveq r0,#1
972                        o4(0x13A00000); // movne r0,#0
973                        break;
974                    case TY_FLOAT:
975                        callRuntime((void*) runtime_is_zero_f);
976                        break;
977                    case TY_DOUBLE:
978                        callRuntime((void*) runtime_is_zero_d);
979                        break;
980                    default:
981                        error("gUnaryCmp unsupported type");
982                        break;
983                }
984            }
985            setR0Type(mkpInt);
986        }
987
988        virtual void genUnaryOp(int op) {
989            Type* pR0Type = getR0Type();
990            TypeTag tag = collapseType(pR0Type->tag);
991            switch(tag) {
992                case TY_INT:
993                    switch(op) {
994                    case OP_MINUS:
995                        o4(0xE3A01000);  // mov    r1, #0
996                        o4(0xE0410000);  // sub     r0,r1,r0
997                        break;
998                    case OP_BIT_NOT:
999                        o4(0xE1E00000);  // mvn     r0, r0
1000                        break;
1001                    default:
1002                        error("Unknown unary op %d\n", op);
1003                        break;
1004                    }
1005                    break;
1006                case TY_FLOAT:
1007                case TY_DOUBLE:
1008                    switch (op) {
1009                        case OP_MINUS:
1010                            if (tag == TY_FLOAT) {
1011                                callRuntime((void*) runtime_op_neg_f);
1012                            } else {
1013                                callRuntime((void*) runtime_op_neg_d);
1014                            }
1015                            break;
1016                        case OP_BIT_NOT:
1017                            error("Can't apply '~' operator to a float or double.");
1018                            break;
1019                        default:
1020                            error("Unknown unary op %d\n", op);
1021                            break;
1022                        }
1023                    break;
1024                default:
1025                    error("genUnaryOp unsupported type");
1026                    break;
1027            }
1028        }
1029
1030        virtual void pushR0() {
1031            Type* pR0Type = getR0Type();
1032            TypeTag r0ct = collapseType(pR0Type->tag);
1033            if (r0ct != TY_DOUBLE) {
1034                    o4(0xE92D0001);  // stmfd   sp!,{r0}
1035                    mStackUse += 4;
1036            } else {
1037                    o4(0xE92D0003);  // stmfd   sp!,{r0,r1}
1038                    mStackUse += 8;
1039            }
1040            pushType();
1041            LOG_STACK("pushR0: %d\n", mStackUse);
1042        }
1043
1044        virtual void over() {
1045            // We know it's only used for int-ptr ops (++/--)
1046
1047            Type* pR0Type = getR0Type();
1048            TypeTag r0ct = collapseType(pR0Type->tag);
1049
1050            Type* pTOSType = getTOSType();
1051            TypeTag tosct = collapseType(pTOSType->tag);
1052
1053            assert (r0ct == TY_INT  && tosct == TY_INT);
1054
1055            o4(0xE8BD0002);  // ldmfd   sp!,{r1}
1056            o4(0xE92D0001);  // stmfd   sp!,{r0}
1057            o4(0xE92D0002);  // stmfd   sp!,{r1}
1058            overType();
1059            mStackUse += 4;
1060        }
1061
1062        virtual void popR0() {
1063            Type* pTOSType = getTOSType();
1064            switch (collapseType(pTOSType->tag)){
1065                case TY_INT:
1066                case TY_FLOAT:
1067                    o4(0xE8BD0001);  // ldmfd   sp!,{r0}
1068                    mStackUse -= 4;
1069                    break;
1070                case TY_DOUBLE:
1071                    o4(0xE8BD0003);  // ldmfd   sp!,{r0, r1}  // Restore R0
1072                        mStackUse -= 8;
1073                    break;
1074                default:
1075                    error("Can't pop this type.");
1076                    break;
1077            }
1078            popType();
1079            LOG_STACK("popR0: %d\n", mStackUse);
1080        }
1081
1082        virtual void storeR0ToTOS() {
1083            Type* pPointerType = getTOSType();
1084            assert(pPointerType->tag == TY_POINTER);
1085            Type* pDestType = pPointerType->pHead;
1086            convertR0(pDestType);
1087            o4(0xE8BD0004);  // ldmfd   sp!,{r2}
1088            popType();
1089            mStackUse -= 4;
1090            switch (pDestType->tag) {
1091                case TY_POINTER:
1092                case TY_INT:
1093                case TY_FLOAT:
1094                    o4(0xE5820000); // str r0, [r2]
1095                    break;
1096                case TY_CHAR:
1097                    o4(0xE5C20000); // strb r0, [r2]
1098                    break;
1099                case TY_DOUBLE:
1100                    o4(0xE1C200F0); // strd r0, [r2]
1101                    break;
1102                default:
1103                    error("storeR0ToTOS: unimplemented type %d",
1104                            pDestType->tag);
1105                    break;
1106            }
1107        }
1108
1109        virtual void loadR0FromR0() {
1110            Type* pPointerType = getR0Type();
1111            assert(pPointerType->tag == TY_POINTER);
1112            switch (pPointerType->pHead->tag) {
1113                case TY_POINTER:
1114                case TY_INT:
1115                case TY_FLOAT:
1116                    o4(0xE5900000); // ldr r0, [r0]
1117                    break;
1118                case TY_CHAR:
1119                    o4(0xE5D00000); // ldrb r0, [r0]
1120                    break;
1121                case TY_DOUBLE:
1122                    o4(0xE1C000D0); // ldrd   r0, [r0]
1123                    break;
1124                default:
1125                    error("loadR0FromR0: unimplemented type");
1126                    break;
1127            }
1128            setR0Type(pPointerType->pHead);
1129        }
1130
1131        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
1132            if (ea > -LOCAL && ea < LOCAL) {
1133                // Local, fp relative
1134                if (ea < -1023 || ea > 1023 || ((ea & 3) != 0)) {
1135                    error("Offset out of range: %08x", ea);
1136                }
1137                if (ea < 0) {
1138                    o4(0xE24B0F00 | (0xff & ((-ea) >> 2))); // sub    r0, fp, #ea
1139                } else {
1140                    o4(0xE28B0F00 | (0xff & (ea >> 2))); // add    r0, fp, #ea
1141                }
1142            } else {
1143                // Global, absolute.
1144                o4(0xE59F0000); //        ldr    r0, .L1
1145                o4(0xEA000000); //        b .L99
1146                o4(ea);         // .L1:   .word 0
1147                                // .L99:
1148            }
1149            setR0Type(pPointerType, et);
1150        }
1151
1152        virtual int leaForward(int ea, Type* pPointerType) {
1153            setR0Type(pPointerType);
1154            int result = ea;
1155            int pc = getPC();
1156            int offset = 0;
1157            if (ea) {
1158                offset = (pc - ea - 8) >> 2;
1159                if ((offset & 0xffff) != offset) {
1160                    error("function forward reference out of bounds");
1161                }
1162            } else {
1163                offset = 0;
1164            }
1165            o4(0xE59F0000 | offset); //        ldr    r0, .L1
1166
1167            if (ea == 0) {
1168                o4(0xEA000000); //        b .L99
1169                result = o4(ea);         // .L1:   .word 0
1170                            // .L99:
1171            }
1172            return result;
1173        }
1174
1175        virtual void convertR0(Type* pType){
1176            Type* pR0Type = getR0Type();
1177            if (bitsSame(pType, pR0Type)) {
1178                // do nothing special
1179            } else {
1180                TypeTag r0Tag = collapseType(pR0Type->tag);
1181                TypeTag destTag = collapseType(pType->tag);
1182                if (r0Tag == TY_INT) {
1183                    if (destTag == TY_FLOAT) {
1184                        callRuntime((void*) runtime_int_to_float);
1185                    } else {
1186                        assert(destTag == TY_DOUBLE);
1187                        callRuntime((void*) runtime_int_to_double);
1188                    }
1189                } else if (r0Tag == TY_FLOAT) {
1190                    if (destTag == TY_INT) {
1191                        callRuntime((void*) runtime_float_to_int);
1192                    } else {
1193                        assert(destTag == TY_DOUBLE);
1194                        callRuntime((void*) runtime_float_to_double);
1195                    }
1196                } else {
1197                    assert (r0Tag == TY_DOUBLE);
1198                    if (destTag == TY_INT) {
1199                        callRuntime((void*) runtime_double_to_int);
1200                    } else {
1201                        assert(destTag == TY_FLOAT);
1202                        callRuntime((void*) runtime_double_to_float);
1203                    }
1204                }
1205            }
1206            setR0Type(pType);
1207        }
1208
1209        virtual int beginFunctionCallArguments() {
1210            return o4(0xE24DDF00); // Placeholder
1211        }
1212
1213        virtual size_t storeR0ToArg(int l, Type* pArgType) {
1214            convertR0(pArgType);
1215            Type* pR0Type = getR0Type();
1216            TypeTag r0ct = collapseType(pR0Type->tag);
1217            switch(r0ct) {
1218                case TY_INT:
1219                case TY_FLOAT:
1220                    if (l < 0 || l > 4096-4) {
1221                        error("l out of range for stack offset: 0x%08x", l);
1222                    }
1223                    o4(0xE58D0000 + l); // str r0, [sp, #l]
1224                    return 4;
1225                case TY_DOUBLE: {
1226                    // Align to 8 byte boundary
1227                    int l2 = (l + 7) & ~7;
1228                    if (l2 < 0 || l2 > 4096-8) {
1229                        error("l out of range for stack offset: 0x%08x", l);
1230                    }
1231                    o4(0xE58D0000 + l2); // str r0, [sp, #l]
1232                    o4(0xE58D1000 + l2 + 4); // str r1, [sp, #l+4]
1233                    return (l2 - l) + 8;
1234                }
1235                default:
1236                    assert(false);
1237                    return 0;
1238            }
1239        }
1240
1241        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
1242            int argumentStackUse = l;
1243            // Have to calculate register arg count from actual stack size,
1244            // in order to properly handle ... functions.
1245            int regArgCount = l >> 2;
1246            if (regArgCount > 4) {
1247                regArgCount = 4;
1248            }
1249            if (regArgCount > 0) {
1250                argumentStackUse -= regArgCount * 4;
1251                o4(0xE8BD0000 | ((1 << regArgCount) - 1)); // ldmfd   sp!,{}
1252            }
1253            mStackUse += argumentStackUse;
1254
1255            // Align stack.
1256            int missalignment = mStackUse - ((mStackUse / STACK_ALIGNMENT)
1257                    * STACK_ALIGNMENT);
1258            mStackAlignmentAdjustment = 0;
1259            if (missalignment > 0) {
1260                mStackAlignmentAdjustment = STACK_ALIGNMENT - missalignment;
1261            }
1262            l += mStackAlignmentAdjustment;
1263
1264            if (l < 0 || l > 0x3FC) {
1265                error("L out of range for stack adjustment: 0x%08x", l);
1266            }
1267            * (int*) a = 0xE24DDF00 | (l >> 2); // sub    sp, sp, #0 << 2
1268            mStackUse += mStackAlignmentAdjustment;
1269            LOG_STACK("endFunctionCallArguments mStackUse: %d, mStackAlignmentAdjustment %d\n",
1270                      mStackUse, mStackAlignmentAdjustment);
1271        }
1272
1273        virtual int callForward(int symbol, Type* pFunc) {
1274            setR0Type(pFunc->pHead);
1275            // Forward calls are always short (local)
1276            return o4(0xEB000000 | encodeAddress(symbol));
1277        }
1278
1279        virtual void callIndirect(int l, Type* pFunc) {
1280            assert(pFunc->tag == TY_FUNC);
1281            popType(); // Get rid of indirect fn pointer type
1282            setR0Type(pFunc->pHead);
1283            int argCount = l >> 2;
1284            int poppedArgs = argCount > 4 ? 4 : argCount;
1285            int adjustedL = l - (poppedArgs << 2) + mStackAlignmentAdjustment;
1286            if (adjustedL < 0 || adjustedL > 4096-4) {
1287                error("l out of range for stack offset: 0x%08x", l);
1288            }
1289            o4(0xE59DC000 | (0xfff & adjustedL)); // ldr    r12, [sp,#adjustedL]
1290            o4(0xE12FFF3C); // blx r12
1291        }
1292
1293        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
1294            int argCount = l >> 2;
1295            // Have to calculate register arg count from actual stack size,
1296            // in order to properly handle ... functions.
1297            int regArgCount = l >> 2;
1298            if (regArgCount > 4) {
1299                regArgCount = 4;
1300            }
1301            int stackArgs = argCount - regArgCount;
1302            int stackUse =  stackArgs + (isIndirect ? 1 : 0)
1303                + (mStackAlignmentAdjustment >> 2);
1304            if (stackUse) {
1305                if (stackUse < 0 || stackUse > 255) {
1306                    error("L out of range for stack adjustment: 0x%08x", l);
1307                }
1308                o4(0xE28DDF00 | stackUse); // add    sp, sp, #stackUse << 2
1309                mStackUse -= stackUse * 4;
1310                LOG_STACK("adjustStackAfterCall: %d\n", mStackUse);
1311            }
1312        }
1313
1314        virtual int jumpOffset() {
1315            return 8;
1316        }
1317
1318        /* output a symbol and patch all calls to it */
1319        virtual void gsym(int t) {
1320            int n;
1321            int base = getBase();
1322            int pc = getPC();
1323            while (t) {
1324                int data = * (int*) t;
1325                int decodedOffset = ((BRANCH_REL_ADDRESS_MASK & data) << 2);
1326                if (decodedOffset == 0) {
1327                    n = 0;
1328                } else {
1329                    n = base + decodedOffset; /* next value */
1330                }
1331                *(int *) t = (data & ~BRANCH_REL_ADDRESS_MASK)
1332                    | encodeRelAddress(pc - t - 8);
1333                t = n;
1334            }
1335        }
1336
1337        /* output a symbol and patch all calls to it */
1338        virtual void resolveForward(int t) {
1339            if (t) {
1340                int pc = getPC();
1341                *(int *) t = pc;
1342            }
1343        }
1344
1345        virtual int finishCompile() {
1346#if defined(__arm__)
1347            const long base = long(getBase());
1348            const long curr = long(getPC());
1349            int err = cacheflush(base, curr, 0);
1350            return err;
1351#else
1352            return 0;
1353#endif
1354        }
1355
1356        virtual int disassemble(FILE* out) {
1357#ifdef ENABLE_ARM_DISASSEMBLY
1358            disasmOut = out;
1359            disasm_interface_t  di;
1360            di.di_readword = disassemble_readword;
1361            di.di_printaddr = disassemble_printaddr;
1362            di.di_printf = disassemble_printf;
1363
1364            int base = getBase();
1365            int pc = getPC();
1366            for(int i = base; i < pc; i += 4) {
1367                fprintf(out, "%08x: %08x  ", i, *(int*) i);
1368                ::disasm(&di, i, 0);
1369            }
1370#endif
1371            return 0;
1372        }
1373
1374        /**
1375         * alignment (in bytes) for this type of data
1376         */
1377        virtual size_t alignmentOf(Type* pType){
1378            switch(pType->tag) {
1379                case TY_CHAR:
1380                    return 1;
1381                case TY_DOUBLE:
1382                    return 8;
1383                default:
1384                    return 4;
1385            }
1386        }
1387
1388        /**
1389         * Array element alignment (in bytes) for this type of data.
1390         */
1391        virtual size_t sizeOf(Type* pType){
1392            switch(pType->tag) {
1393                case TY_INT:
1394                    return 4;
1395                case TY_CHAR:
1396                    return 1;
1397                default:
1398                    return 0;
1399                case TY_FLOAT:
1400                    return 4;
1401                case TY_DOUBLE:
1402                    return 8;
1403                case TY_POINTER:
1404                    return 4;
1405            }
1406        }
1407
1408        virtual size_t stackAlignmentOf(Type* pType) {
1409            switch(pType->tag) {
1410                case TY_DOUBLE:
1411                    return 8;
1412                default:
1413                    return 4;
1414            }
1415        }
1416
1417        virtual size_t stackSizeOf(Type* pType) {
1418            switch(pType->tag) {
1419                case TY_DOUBLE:
1420                    return 8;
1421                default:
1422                    return 4;
1423            }
1424        }
1425
1426    private:
1427        static FILE* disasmOut;
1428
1429        static u_int
1430        disassemble_readword(u_int address)
1431        {
1432            return(*((u_int *)address));
1433        }
1434
1435        static void
1436        disassemble_printaddr(u_int address)
1437        {
1438            fprintf(disasmOut, "0x%08x", address);
1439        }
1440
1441        static void
1442        disassemble_printf(const char *fmt, ...) {
1443            va_list ap;
1444            va_start(ap, fmt);
1445            vfprintf(disasmOut, fmt, ap);
1446            va_end(ap);
1447        }
1448
1449        static const int BRANCH_REL_ADDRESS_MASK = 0x00ffffff;
1450
1451        /** Encode a relative address that might also be
1452         * a label.
1453         */
1454        int encodeAddress(int value) {
1455            int base = getBase();
1456            if (value >= base && value <= getPC() ) {
1457                // This is a label, encode it relative to the base.
1458                value = value - base;
1459            }
1460            return encodeRelAddress(value);
1461        }
1462
1463        int encodeRelAddress(int value) {
1464            return BRANCH_REL_ADDRESS_MASK & (value >> 2);
1465        }
1466
1467        int calcRegArgCount(Type* pDecl) {
1468            int reg = 0;
1469            Type* pArgs = pDecl->pTail;
1470            while (pArgs && reg < 4) {
1471                Type* pArg = pArgs->pHead;
1472                if ( pArg->tag == TY_DOUBLE) {
1473                    int evenReg = (reg + 1) & ~1;
1474                    if (evenReg >= 4) {
1475                        break;
1476                    }
1477                    reg = evenReg + 2;
1478                } else {
1479                    reg++;
1480                }
1481                pArgs = pArgs->pTail;
1482            }
1483            return reg;
1484        }
1485
1486        void setupIntPtrArgs() {
1487            o4(0xE8BD0002);  // ldmfd   sp!,{r1}
1488            mStackUse -= 4;
1489            popType();
1490        }
1491
1492        /* Pop TOS to R1
1493         * Make sure both R0 and TOS are floats. (Could be ints)
1494         * We know that at least one of R0 and TOS is already a float
1495         */
1496        void setupFloatArgs() {
1497            Type* pR0Type = getR0Type();
1498            Type* pTOSType = getTOSType();
1499            TypeTag tagR0 = collapseType(pR0Type->tag);
1500            TypeTag tagTOS = collapseType(pTOSType->tag);
1501            if (tagR0 != TY_FLOAT) {
1502                assert(tagR0 == TY_INT);
1503                callRuntime((void*) runtime_int_to_float);
1504            }
1505            if (tagTOS != TY_FLOAT) {
1506                assert(tagTOS == TY_INT);
1507                assert(tagR0 == TY_FLOAT);
1508                o4(0xE92D0001);  // stmfd   sp!,{r0}  // push R0
1509                o4(0xE59D0004);  // ldr     r0, [sp, #4]
1510                callRuntime((void*) runtime_int_to_float);
1511                o4(0xE1A01000);  // mov r1, r0
1512                o4(0xE8BD0001);  // ldmfd   sp!,{r0}  // pop R0
1513                o4(0xE28DD004);  // add sp, sp, #4 // Pop sp
1514            } else {
1515                // Pop TOS
1516                o4(0xE8BD0002);  // ldmfd   sp!,{r1}
1517            }
1518            mStackUse -= 4;
1519            popType();
1520        }
1521
1522        /* Pop TOS into R2..R3
1523         * Make sure both R0 and TOS are doubles. Could be floats or ints.
1524         * We know that at least one of R0 and TOS are already a double.
1525         */
1526
1527        void setupDoubleArgs() {
1528            Type* pR0Type = getR0Type();
1529            Type* pTOSType = getTOSType();
1530            TypeTag tagR0 = collapseType(pR0Type->tag);
1531            TypeTag tagTOS = collapseType(pTOSType->tag);
1532            if (tagR0 != TY_DOUBLE) {
1533                if (tagR0 == TY_INT) {
1534                    callRuntime((void*) runtime_int_to_double);
1535                } else {
1536                    assert(tagR0 == TY_FLOAT);
1537                    callRuntime((void*) runtime_float_to_double);
1538                }
1539            }
1540            if (tagTOS != TY_DOUBLE) {
1541                o4(0xE92D0003);  // stmfd   sp!,{r0,r1}  // push r0,r1
1542                o4(0xE59D0008);  // ldr     r0, [sp, #8]
1543                if (tagTOS == TY_INT) {
1544                    callRuntime((void*) runtime_int_to_double);
1545                } else {
1546                    assert(tagTOS == TY_FLOAT);
1547                    callRuntime((void*) runtime_float_to_double);
1548                }
1549                o4(0xE1A02000);  // mov r2, r0
1550                o4(0xE1A03001);  // mov r3, r1
1551                o4(0xE8BD0003);  // ldmfd   sp!,{r0, r1}  // Restore R0
1552                o4(0xE28DD004);  // add sp, sp, #4 // Pop sp
1553                mStackUse -= 4;
1554            } else {
1555                o4(0xE8BD000C);  // ldmfd   sp!,{r2,r3}
1556                mStackUse -= 8;
1557            }
1558            popType();
1559        }
1560
1561        void liReg(int t, int reg) {
1562            assert(reg >= 0 && reg < 16);
1563            int rN = (reg & 0xf) << 12;
1564            if (t >= 0 && t < 255) {
1565                 o4((0xE3A00000 + t) | rN); // mov    rN, #0
1566            } else if (t >= -256 && t < 0) {
1567                // mvn means move constant ^ ~0
1568                o4((0xE3E00000 - (t+1)) | rN); // mvn    rN, #0
1569            } else {
1570                  o4(0xE51F0000 | rN); //         ldr    rN, .L3
1571                  o4(0xEA000000); //         b .L99
1572                  o4(t);          // .L3:   .word 0
1573                                  // .L99:
1574            }
1575        }
1576
1577        void callRuntime(void* fn) {
1578            o4(0xE59FC000); // ldr    r12, .L1
1579            o4(0xEA000000); // b      .L99
1580            o4((int) fn);   //.L1:  .word  fn
1581            o4(0xE12FFF3C); //.L99: blx    r12
1582        }
1583
1584        // Integer math:
1585
1586        static int runtime_DIV(int b, int a) {
1587            return a / b;
1588        }
1589
1590        static int runtime_MOD(int b, int a) {
1591            return a % b;
1592        }
1593
1594        // Comparison to zero
1595
1596        static int runtime_is_non_zero_f(float a) {
1597            return a != 0;
1598        }
1599
1600        static int runtime_is_non_zero_d(double a) {
1601            return a != 0;
1602        }
1603
1604        // Comparison to zero
1605
1606        static int runtime_is_zero_f(float a) {
1607            return a == 0;
1608        }
1609
1610        static int runtime_is_zero_d(double a) {
1611            return a == 0;
1612        }
1613
1614        // Type conversion
1615
1616        static int runtime_float_to_int(float a) {
1617            return (int) a;
1618        }
1619
1620        static double runtime_float_to_double(float a) {
1621            return (double) a;
1622        }
1623
1624        static int runtime_double_to_int(double a) {
1625            return (int) a;
1626        }
1627
1628        static float runtime_double_to_float(double a) {
1629            return (float) a;
1630        }
1631
1632        static float runtime_int_to_float(int a) {
1633            return (float) a;
1634        }
1635
1636        static double runtime_int_to_double(int a) {
1637            return (double) a;
1638        }
1639
1640        // Comparisons float
1641
1642        static int runtime_cmp_eq_ff(float b, float a) {
1643            return a == b;
1644        }
1645
1646        static int runtime_cmp_ne_ff(float b, float a) {
1647            return a != b;
1648        }
1649
1650        static int runtime_cmp_lt_ff(float b, float a) {
1651            return a < b;
1652        }
1653
1654        static int runtime_cmp_le_ff(float b, float a) {
1655            return a <= b;
1656        }
1657
1658        static int runtime_cmp_ge_ff(float b, float a) {
1659            return a >= b;
1660        }
1661
1662        static int runtime_cmp_gt_ff(float b, float a) {
1663            return a > b;
1664        }
1665
1666        // Comparisons double
1667
1668        static int runtime_cmp_eq_dd(double b, double a) {
1669            return a == b;
1670        }
1671
1672        static int runtime_cmp_ne_dd(double b, double a) {
1673            return a != b;
1674        }
1675
1676        static int runtime_cmp_lt_dd(double b, double a) {
1677            return a < b;
1678        }
1679
1680        static int runtime_cmp_le_dd(double b, double a) {
1681            return a <= b;
1682        }
1683
1684        static int runtime_cmp_ge_dd(double b, double a) {
1685            return a >= b;
1686        }
1687
1688        static int runtime_cmp_gt_dd(double b, double a) {
1689            return a > b;
1690        }
1691
1692        // Math float
1693
1694        static float runtime_op_add_ff(float b, float a) {
1695            return a + b;
1696        }
1697
1698        static float runtime_op_sub_ff(float b, float a) {
1699            return a - b;
1700        }
1701
1702        static float runtime_op_mul_ff(float b, float a) {
1703            return a * b;
1704        }
1705
1706        static float runtime_op_div_ff(float b, float a) {
1707            return a / b;
1708        }
1709
1710        static float runtime_op_neg_f(float a) {
1711            return -a;
1712        }
1713
1714        // Math double
1715
1716        static double runtime_op_add_dd(double b, double a) {
1717            return a + b;
1718        }
1719
1720        static double runtime_op_sub_dd(double b, double a) {
1721            return a - b;
1722        }
1723
1724        static double runtime_op_mul_dd(double b, double a) {
1725            return a * b;
1726        }
1727
1728        static double runtime_op_div_dd(double b, double a) {
1729            return a / b;
1730        }
1731
1732        static double runtime_op_neg_d(double a) {
1733            return -a;
1734        }
1735
1736        static const int STACK_ALIGNMENT = 8;
1737        int mStackUse;
1738        // This variable holds the amount we adjusted the stack in the most
1739        // recent endFunctionCallArguments call. It's examined by the
1740        // following adjustStackAfterCall call.
1741        int mStackAlignmentAdjustment;
1742    };
1743
1744#endif // PROVIDE_ARM_CODEGEN
1745
1746#ifdef PROVIDE_X86_CODEGEN
1747
1748    class X86CodeGenerator : public CodeGenerator {
1749    public:
1750        X86CodeGenerator() {}
1751        virtual ~X86CodeGenerator() {}
1752
1753        /* returns address to patch with local variable size
1754        */
1755        virtual int functionEntry(Type* pDecl) {
1756            o(0xe58955); /* push   %ebp, mov %esp, %ebp */
1757            return oad(0xec81, 0); /* sub $xxx, %esp */
1758        }
1759
1760        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
1761            o(0xc3c9); /* leave, ret */
1762            *(int *) localVariableAddress = localVariableSize; /* save local variables */
1763        }
1764
1765        /* load immediate value */
1766        virtual void li(int i) {
1767            oad(0xb8, i); /* mov $xx, %eax */
1768            setR0Type(mkpInt);
1769        }
1770
1771        virtual void loadFloat(int address, Type* pType) {
1772            setR0Type(pType);
1773            switch (pType->tag) {
1774            case TY_FLOAT:
1775                oad(0x05D9, address);      // flds
1776                break;
1777            case TY_DOUBLE:
1778                oad(0x05DD, address);      // fldl
1779                break;
1780            default:
1781                assert(false);
1782                break;
1783            }
1784        }
1785
1786        virtual int gjmp(int t) {
1787            return psym(0xe9, t);
1788        }
1789
1790        /* l = 0: je, l == 1: jne */
1791        virtual int gtst(bool l, int t) {
1792            Type* pR0Type = getR0Type();
1793            TypeTag tagR0 = pR0Type->tag;
1794            bool isFloatR0 = isFloatTag(tagR0);
1795            if (isFloatR0) {
1796                o(0xeed9); // fldz
1797                o(0xe9da); // fucompp
1798                o(0xe0df); // fnstsw %ax
1799                o(0x9e);   // sahf
1800            } else {
1801                o(0xc085); // test %eax, %eax
1802            }
1803            // Use two output statements to generate one instruction.
1804            o(0x0f);   // je/jne xxx
1805            return psym(0x84 + l, t);
1806        }
1807
1808        virtual void gcmp(int op) {
1809            Type* pR0Type = getR0Type();
1810            Type* pTOSType = getTOSType();
1811            TypeTag tagR0 = pR0Type->tag;
1812            TypeTag tagTOS = pTOSType->tag;
1813            bool isFloatR0 = isFloatTag(tagR0);
1814            bool isFloatTOS = isFloatTag(tagTOS);
1815            if (!isFloatR0 && !isFloatTOS) {
1816                int t = decodeOp(op);
1817                o(0x59); /* pop %ecx */
1818                o(0xc139); /* cmp %eax,%ecx */
1819                li(0);
1820                o(0x0f); /* setxx %al */
1821                o(t + 0x90);
1822                o(0xc0);
1823                popType();
1824            } else {
1825                setupFloatOperands();
1826                switch (op) {
1827                    case OP_EQUALS:
1828                        o(0xe9da);   // fucompp
1829                        o(0xe0df);   // fnstsw %ax
1830                        o(0x9e);     // sahf
1831                        o(0xc0940f); // sete %al
1832                        o(0xc29b0f); // setnp %dl
1833                        o(0xd021);   // andl %edx, %eax
1834                        break;
1835                    case OP_NOT_EQUALS:
1836                        o(0xe9da);   // fucompp
1837                        o(0xe0df);   // fnstsw %ax
1838                        o(0x9e);     // sahf
1839                        o(0xc0950f); // setne %al
1840                        o(0xc29a0f); // setp %dl
1841                        o(0xd009);   // orl %edx, %eax
1842                        break;
1843                    case OP_GREATER_EQUAL:
1844                        o(0xe9da);   // fucompp
1845                        o(0xe0df);   // fnstsw %ax
1846                        o(0x05c4f6); // testb $5, %ah
1847                        o(0xc0940f); // sete %al
1848                        break;
1849                    case OP_LESS:
1850                        o(0xc9d9);   // fxch %st(1)
1851                        o(0xe9da);   // fucompp
1852                        o(0xe0df);   // fnstsw %ax
1853                        o(0x9e);     // sahf
1854                        o(0xc0970f); // seta %al
1855                        break;
1856                    case OP_LESS_EQUAL:
1857                        o(0xc9d9);   // fxch %st(1)
1858                        o(0xe9da);   // fucompp
1859                        o(0xe0df);   // fnstsw %ax
1860                        o(0x9e);     // sahf
1861                        o(0xc0930f); // setea %al
1862                        break;
1863                    case OP_GREATER:
1864                        o(0xe9da);   // fucompp
1865                        o(0xe0df);   // fnstsw %ax
1866                        o(0x45c4f6); // testb $69, %ah
1867                        o(0xc0940f); // sete %al
1868                        break;
1869                    default:
1870                        error("Unknown comparison op");
1871                }
1872                o(0xc0b60f); // movzbl %al, %eax
1873            }
1874            setR0Type(mkpInt);
1875        }
1876
1877        virtual void genOp(int op) {
1878            Type* pR0Type = getR0Type();
1879            Type* pTOSType = getTOSType();
1880            TypeTag tagR0 = pR0Type->tag;
1881            TypeTag tagTOS = pTOSType->tag;
1882            bool isFloatR0 = isFloatTag(tagR0);
1883            bool isFloatTOS = isFloatTag(tagTOS);
1884            if (!isFloatR0 && !isFloatTOS) {
1885                bool isPtrR0 = tagR0 == TY_POINTER;
1886                bool isPtrTOS = tagTOS == TY_POINTER;
1887                if (isPtrR0 || isPtrTOS) {
1888                    if (isPtrR0 && isPtrTOS) {
1889                        if (op != OP_MINUS) {
1890                            error("Unsupported pointer-pointer operation %d.", op);
1891                        }
1892                        if (! typeEqual(pR0Type, pTOSType)) {
1893                            error("Incompatible pointer types for subtraction.");
1894                        }
1895                        o(0x59); /* pop %ecx */
1896                        o(decodeOp(op));
1897                        popType();
1898                        setR0Type(mkpInt);
1899                        int size = sizeOf(pR0Type->pHead);
1900                        if (size != 1) {
1901                            pushR0();
1902                            li(size);
1903                            // TODO: Optimize for power-of-two.
1904                            genOp(OP_DIV);
1905                        }
1906                    } else {
1907                        if (! (op == OP_PLUS || (op == OP_MINUS && isPtrR0))) {
1908                            error("Unsupported pointer-scalar operation %d", op);
1909                        }
1910                        Type* pPtrType = isPtrR0 ? pR0Type : pTOSType;
1911                        o(0x59); /* pop %ecx */
1912                        int size = sizeOf(pPtrType->pHead);
1913                        if (size != 1) {
1914                            // TODO: Optimize for power-of-two.
1915                            if (isPtrR0) {
1916                                oad(0xC969, size); // imull $size, %ecx
1917                            } else {
1918                                oad(0xC069, size); // mul $size, %eax
1919                            }
1920                        }
1921                        o(decodeOp(op));
1922                        popType();
1923                        setR0Type(pPtrType);
1924                    }
1925                } else {
1926                    o(0x59); /* pop %ecx */
1927                    o(decodeOp(op));
1928                    if (op == OP_MOD)
1929                        o(0x92); /* xchg %edx, %eax */
1930                    popType();
1931                }
1932            } else {
1933                Type* pResultType = tagR0 > tagTOS ? pR0Type : pTOSType;
1934                setupFloatOperands();
1935                // Both float. x87 R0 == left hand, x87 R1 == right hand
1936                switch (op) {
1937                    case OP_MUL:
1938                        o(0xc9de); // fmulp
1939                        break;
1940                    case OP_DIV:
1941                        o(0xf1de); // fdivp
1942                        break;
1943                    case OP_PLUS:
1944                        o(0xc1de); // faddp
1945                        break;
1946                    case OP_MINUS:
1947                        o(0xe1de); // fsubp
1948                        break;
1949                    default:
1950                        error("Unsupported binary floating operation.");
1951                        break;
1952                }
1953                setR0Type(pResultType);
1954            }
1955        }
1956
1957        virtual void gUnaryCmp(int op) {
1958            if (op != OP_LOGICAL_NOT) {
1959                error("Unknown unary cmp %d", op);
1960            } else {
1961                Type* pR0Type = getR0Type();
1962                TypeTag tag = collapseType(pR0Type->tag);
1963                switch(tag) {
1964                    case TY_INT: {
1965                            oad(0xb9, 0); /* movl $0, %ecx */
1966                            int t = decodeOp(op);
1967                            o(0xc139); /* cmp %eax,%ecx */
1968                            li(0);
1969                            o(0x0f); /* setxx %al */
1970                            o(t + 0x90);
1971                            o(0xc0);
1972                        }
1973                        break;
1974                    case TY_FLOAT:
1975                    case TY_DOUBLE:
1976                        o(0xeed9);   // fldz
1977                        o(0xe9da);   // fucompp
1978                        o(0xe0df);   // fnstsw %ax
1979                        o(0x9e);     // sahf
1980                        o(0xc0950f); // setne %al
1981                        o(0xc29a0f); // setp %dl
1982                        o(0xd009);   // orl %edx, %eax
1983                        o(0xc0b60f); // movzbl %al, %eax
1984                        o(0x01f083); // xorl $1,  %eax
1985                        break;
1986                    default:
1987                        error("gUnaryCmp unsupported type");
1988                        break;
1989                }
1990            }
1991            setR0Type(mkpInt);
1992        }
1993
1994        virtual void genUnaryOp(int op) {
1995            Type* pR0Type = getR0Type();
1996            TypeTag tag = collapseType(pR0Type->tag);
1997            switch(tag) {
1998                case TY_INT:
1999                    oad(0xb9, 0); /* movl $0, %ecx */
2000                    o(decodeOp(op));
2001                    break;
2002                case TY_FLOAT:
2003                case TY_DOUBLE:
2004                    switch (op) {
2005                        case OP_MINUS:
2006                            o(0xe0d9);  // fchs
2007                            break;
2008                        case OP_BIT_NOT:
2009                            error("Can't apply '~' operator to a float or double.");
2010                            break;
2011                        default:
2012                            error("Unknown unary op %d\n", op);
2013                            break;
2014                        }
2015                    break;
2016                default:
2017                    error("genUnaryOp unsupported type");
2018                    break;
2019            }
2020        }
2021
2022        virtual void pushR0() {
2023            Type* pR0Type = getR0Type();
2024            TypeTag r0ct = collapseType(pR0Type->tag);
2025            switch(r0ct) {
2026                case TY_INT:
2027                    o(0x50); /* push %eax */
2028                    break;
2029                case TY_FLOAT:
2030                    o(0x50); /* push %eax */
2031                    o(0x241cd9); // fstps 0(%esp)
2032                    break;
2033                case TY_DOUBLE:
2034                    o(0x50); /* push %eax */
2035                    o(0x50); /* push %eax */
2036                    o(0x241cdd); // fstpl 0(%esp)
2037                    break;
2038                default:
2039                    error("pushR0 unsupported type %d", r0ct);
2040                    break;
2041            }
2042            pushType();
2043        }
2044
2045        virtual void over() {
2046            // We know it's only used for int-ptr ops (++/--)
2047
2048            Type* pR0Type = getR0Type();
2049            TypeTag r0ct = collapseType(pR0Type->tag);
2050
2051            Type* pTOSType = getTOSType();
2052            TypeTag tosct = collapseType(pTOSType->tag);
2053
2054            assert (r0ct == TY_INT && tosct == TY_INT);
2055
2056            o(0x59); /* pop %ecx */
2057            o(0x50); /* push %eax */
2058            o(0x51); /* push %ecx */
2059
2060            overType();
2061        }
2062
2063        virtual void popR0() {
2064            Type* pR0Type = getR0Type();
2065            TypeTag r0ct = collapseType(pR0Type->tag);
2066            switch(r0ct) {
2067                case TY_INT:
2068                    o(0x58); /* popl %eax */
2069                    break;
2070                case TY_FLOAT:
2071                    o(0x2404d9); // flds (%esp)
2072                    o(0x58); /* popl %eax */
2073                    break;
2074                case TY_DOUBLE:
2075                    o(0x2404dd); // fldl (%esp)
2076                    o(0x58); /* popl %eax */
2077                    o(0x58); /* popl %eax */
2078                    break;
2079                default:
2080                    error("popR0 unsupported type %d", r0ct);
2081                    break;
2082            }
2083            popType();
2084        }
2085
2086        virtual void storeR0ToTOS() {
2087            Type* pPointerType = getTOSType();
2088            assert(pPointerType->tag == TY_POINTER);
2089            Type* pTargetType = pPointerType->pHead;
2090            convertR0(pTargetType);
2091            o(0x59); /* pop %ecx */
2092            popType();
2093            switch (pTargetType->tag) {
2094                case TY_POINTER:
2095                case TY_INT:
2096                    o(0x0189); /* movl %eax/%al, (%ecx) */
2097                    break;
2098                case TY_CHAR:
2099                    o(0x0188); /* movl %eax/%al, (%ecx) */
2100                    break;
2101                case TY_FLOAT:
2102                    o(0x19d9); /* fstps (%ecx) */
2103                    break;
2104                case TY_DOUBLE:
2105                    o(0x19dd); /* fstpl (%ecx) */
2106                    break;
2107                default:
2108                    error("storeR0ToTOS: unsupported type %d",
2109                            pTargetType->tag);
2110                    break;
2111            }
2112        }
2113
2114        virtual void loadR0FromR0() {
2115            Type* pPointerType = getR0Type();
2116            assert(pPointerType->tag == TY_POINTER);
2117            switch (pPointerType->pHead->tag) {
2118                case TY_POINTER:
2119                case TY_INT:
2120                    o2(0x008b); /* mov (%eax), %eax */
2121                    break;
2122                case TY_CHAR:
2123                    o(0xbe0f); /* movsbl (%eax), %eax */
2124                    ob(0); /* add zero in code */
2125                    break;
2126                case TY_FLOAT:
2127                    o2(0x00d9); // flds (%eax)
2128                    break;
2129                case TY_DOUBLE:
2130                    o2(0x00dd); // fldl (%eax)
2131                    break;
2132                default:
2133                    error("loadR0FromR0: unsupported type");
2134                    break;
2135            }
2136            setR0Type(pPointerType->pHead);
2137        }
2138
2139        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
2140            gmov(10, ea); /* leal EA, %eax */
2141            setR0Type(pPointerType, et);
2142        }
2143
2144        virtual int leaForward(int ea, Type* pPointerType) {
2145            oad(0xb8, ea); /* mov $xx, %eax */
2146            setR0Type(pPointerType);
2147            return getPC() - 4;
2148        }
2149
2150        virtual void convertR0(Type* pType){
2151            Type* pR0Type = getR0Type();
2152            if (pR0Type == NULL) {
2153                assert(false);
2154                setR0Type(pType);
2155                return;
2156            }
2157            if (bitsSame(pType, pR0Type)) {
2158                // do nothing special
2159            } else if (isFloatType(pType) && isFloatType(pR0Type)) {
2160                // do nothing special, both held in same register on x87.
2161            } else {
2162                TypeTag r0Tag = collapseType(pR0Type->tag);
2163                TypeTag destTag = collapseType(pType->tag);
2164                if (r0Tag == TY_INT && isFloatTag(destTag)) {
2165                    // Convert R0 from int to float
2166                    o(0x50);      // push %eax
2167                    o(0x2404DB);  // fildl 0(%esp)
2168                    o(0x58);      // pop %eax
2169                } else if (isFloatTag(r0Tag) && destTag == TY_INT) {
2170                    // Convert R0 from float to int. Complicated because
2171                    // need to save and restore the rounding mode.
2172                    o(0x50);       // push %eax
2173                    o(0x50);       // push %eax
2174                    o(0x02247cD9); // fnstcw 2(%esp)
2175                    o(0x2444b70f); // movzwl 2(%esp), %eax
2176                    o(0x02);
2177                    o(0x0cb4);     // movb $12, %ah
2178                    o(0x24048966); // movw %ax, 0(%esp)
2179                    o(0x242cd9);   // fldcw 0(%esp)
2180                    o(0x04245cdb); // fistpl 4(%esp)
2181                    o(0x02246cd9); // fldcw  2(%esp)
2182                    o(0x58); // pop %eax
2183                    o(0x58); // pop %eax
2184                } else {
2185                    error("Incompatible types old: %d new: %d",
2186                          pR0Type->tag, pType->tag);
2187                }
2188            }
2189            setR0Type(pType);
2190        }
2191
2192        virtual int beginFunctionCallArguments() {
2193            return oad(0xec81, 0); /* sub $xxx, %esp */
2194        }
2195
2196        virtual size_t storeR0ToArg(int l, Type* pArgType) {
2197            convertR0(pArgType);
2198            Type* pR0Type = getR0Type();
2199            TypeTag r0ct = collapseType(pR0Type->tag);
2200            switch(r0ct) {
2201                case TY_INT:
2202                    oad(0x248489, l); /* movl %eax, xxx(%esp) */
2203                    return 4;
2204                case TY_FLOAT:
2205                    oad(0x249CD9, l); /* fstps   xxx(%esp) */
2206                    return 4;
2207                case TY_DOUBLE:
2208                    oad(0x249CDD, l); /* fstpl   xxx(%esp) */
2209                    return 8;
2210                default:
2211                    assert(false);
2212                    return 0;
2213            }
2214        }
2215
2216        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
2217            * (int*) a = l;
2218        }
2219
2220        virtual int callForward(int symbol, Type* pFunc) {
2221            assert(pFunc->tag == TY_FUNC);
2222            setR0Type(pFunc->pHead);
2223            return psym(0xe8, symbol); /* call xxx */
2224        }
2225
2226        virtual void callIndirect(int l, Type* pFunc) {
2227            assert(pFunc->tag == TY_FUNC);
2228            popType(); // Get rid of indirect fn pointer type
2229            setR0Type(pFunc->pHead);
2230            oad(0x2494ff, l); /* call *xxx(%esp) */
2231        }
2232
2233        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
2234            assert(pDecl->tag == TY_FUNC);
2235            if (isIndirect) {
2236                l += 4;
2237            }
2238            if (l > 0) {
2239                oad(0xc481, l); /* add $xxx, %esp */
2240            }
2241        }
2242
2243        virtual int jumpOffset() {
2244            return 5;
2245        }
2246
2247        virtual int disassemble(FILE* out) {
2248            return 0;
2249        }
2250
2251        /* output a symbol and patch all calls to it */
2252        virtual void gsym(int t) {
2253            int n;
2254            int pc = getPC();
2255            while (t) {
2256                n = *(int *) t; /* next value */
2257                *(int *) t = pc - t - 4;
2258                t = n;
2259            }
2260        }
2261
2262        /* output a symbol and patch all calls to it, using absolute address */
2263        virtual void resolveForward(int t) {
2264            int n;
2265            int pc = getPC();
2266            while (t) {
2267                n = *(int *) t; /* next value */
2268                *(int *) t = pc;
2269                t = n;
2270            }
2271        }
2272
2273        virtual int finishCompile() {
2274            size_t pagesize = 4096;
2275            size_t base = (size_t) getBase() & ~ (pagesize - 1);
2276            size_t top =  ((size_t) getPC() + pagesize - 1) & ~ (pagesize - 1);
2277            int err = mprotect((void*) base, top - base, PROT_READ | PROT_WRITE | PROT_EXEC);
2278            if (err) {
2279               error("mprotect() failed: %d", errno);
2280            }
2281            return err;
2282        }
2283
2284        /**
2285         * Alignment (in bytes) for this type of data
2286         */
2287        virtual size_t alignmentOf(Type* pType){
2288            switch (pType->tag) {
2289            case TY_CHAR:
2290                return 1;
2291            default:
2292                return 4;
2293            }
2294        }
2295
2296        /**
2297         * Array element alignment (in bytes) for this type of data.
2298         */
2299        virtual size_t sizeOf(Type* pType){
2300            switch(pType->tag) {
2301                case TY_INT:
2302                    return 4;
2303                case TY_CHAR:
2304                    return 1;
2305                default:
2306                    return 0;
2307                case TY_FLOAT:
2308                    return 4;
2309                case TY_DOUBLE:
2310                    return 8;
2311                case TY_POINTER:
2312                    return 4;
2313            }
2314        }
2315
2316        virtual size_t stackAlignmentOf(Type* pType){
2317            return 4;
2318        }
2319
2320        virtual size_t stackSizeOf(Type* pType) {
2321            switch(pType->tag) {
2322                case TY_DOUBLE:
2323                    return 8;
2324                default:
2325                    return 4;
2326            }
2327        }
2328
2329    private:
2330
2331        /** Output 1 to 4 bytes.
2332         *
2333         */
2334        void o(int n) {
2335            /* cannot use unsigned, so we must do a hack */
2336            while (n && n != -1) {
2337                ob(n & 0xff);
2338                n = n >> 8;
2339            }
2340        }
2341
2342        /* Output exactly 2 bytes
2343         */
2344        void o2(int n) {
2345            ob(n & 0xff);
2346            ob(0xff & (n >> 8));
2347        }
2348
2349        /* psym is used to put an instruction with a data field which is a
2350         reference to a symbol. It is in fact the same as oad ! */
2351        int psym(int n, int t) {
2352            return oad(n, t);
2353        }
2354
2355        /* instruction + address */
2356        int oad(int n, int t) {
2357            o(n);
2358            int result = getPC();
2359            o4(t);
2360            return result;
2361        }
2362
2363        static const int operatorHelper[];
2364
2365        int decodeOp(int op) {
2366            if (op < 0 || op > OP_COUNT) {
2367                error("Out-of-range operator: %d\n", op);
2368                op = 0;
2369            }
2370            return operatorHelper[op];
2371        }
2372
2373        void gmov(int l, int t) {
2374            o(l + 0x83);
2375            oad((t > -LOCAL && t < LOCAL) << 7 | 5, t);
2376        }
2377
2378        void setupFloatOperands() {
2379            Type* pR0Type = getR0Type();
2380            Type* pTOSType = getTOSType();
2381            TypeTag tagR0 = pR0Type->tag;
2382            TypeTag tagTOS = pTOSType->tag;
2383            bool isFloatR0 = isFloatTag(tagR0);
2384            bool isFloatTOS = isFloatTag(tagTOS);
2385            if (! isFloatR0) {
2386                // Convert R0 from int to float
2387                o(0x50);      // push %eax
2388                o(0x2404DB);  // fildl 0(%esp)
2389                o(0x58);      // pop %eax
2390            }
2391            if (! isFloatTOS){
2392                o(0x2404DB);  // fildl 0(%esp);
2393                o(0x58);      // pop %eax
2394            } else {
2395                if (tagTOS == TY_FLOAT) {
2396                    o(0x2404d9);  // flds (%esp)
2397                    o(0x58);      // pop %eax
2398                } else {
2399                    o(0x2404dd);  // fldl (%esp)
2400                    o(0x58);      // pop %eax
2401                    o(0x58);      // pop %eax
2402                }
2403            }
2404            popType();
2405        }
2406    };
2407
2408#endif // PROVIDE_X86_CODEGEN
2409
2410#ifdef PROVIDE_TRACE_CODEGEN
2411    class TraceCodeGenerator : public CodeGenerator {
2412    private:
2413        CodeGenerator* mpBase;
2414
2415    public:
2416        TraceCodeGenerator(CodeGenerator* pBase) {
2417            mpBase = pBase;
2418        }
2419
2420        virtual ~TraceCodeGenerator() {
2421            delete mpBase;
2422        }
2423
2424        virtual void init(CodeBuf* pCodeBuf) {
2425            mpBase->init(pCodeBuf);
2426        }
2427
2428        void setErrorSink(ErrorSink* pErrorSink) {
2429            mpBase->setErrorSink(pErrorSink);
2430        }
2431
2432        /* returns address to patch with local variable size
2433        */
2434        virtual int functionEntry(Type* pDecl) {
2435            int result = mpBase->functionEntry(pDecl);
2436            fprintf(stderr, "functionEntry(pDecl) -> %d\n", result);
2437            return result;
2438        }
2439
2440        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
2441            fprintf(stderr, "functionExit(pDecl, %d, %d)\n",
2442                    localVariableAddress, localVariableSize);
2443            mpBase->functionExit(pDecl, localVariableAddress, localVariableSize);
2444        }
2445
2446        /* load immediate value */
2447        virtual void li(int t) {
2448            fprintf(stderr, "li(%d)\n", t);
2449            mpBase->li(t);
2450        }
2451
2452        virtual void loadFloat(int address, Type* pType) {
2453            fprintf(stderr, "loadFloat(%d, type=%d)\n", address, pType->tag);
2454            mpBase->loadFloat(address, pType);
2455        }
2456
2457        virtual int gjmp(int t) {
2458            int result = mpBase->gjmp(t);
2459            fprintf(stderr, "gjmp(%d) = %d\n", t, result);
2460            return result;
2461        }
2462
2463        /* l = 0: je, l == 1: jne */
2464        virtual int gtst(bool l, int t) {
2465            int result = mpBase->gtst(l, t);
2466            fprintf(stderr, "gtst(%d,%d) = %d\n", l, t, result);
2467            return result;
2468        }
2469
2470        virtual void gcmp(int op) {
2471            fprintf(stderr, "gcmp(%d)\n", op);
2472            mpBase->gcmp(op);
2473        }
2474
2475        virtual void genOp(int op) {
2476            fprintf(stderr, "genOp(%d)\n", op);
2477            mpBase->genOp(op);
2478        }
2479
2480
2481        virtual void gUnaryCmp(int op) {
2482            fprintf(stderr, "gUnaryCmp(%d)\n", op);
2483            mpBase->gUnaryCmp(op);
2484        }
2485
2486        virtual void genUnaryOp(int op) {
2487            fprintf(stderr, "genUnaryOp(%d)\n", op);
2488            mpBase->genUnaryOp(op);
2489        }
2490
2491        virtual void pushR0() {
2492            fprintf(stderr, "pushR0()\n");
2493            mpBase->pushR0();
2494        }
2495
2496        virtual void over() {
2497            fprintf(stderr, "over()\n");
2498            mpBase->over();
2499        }
2500
2501        virtual void popR0() {
2502            fprintf(stderr, "popR0()\n");
2503            mpBase->popR0();
2504        }
2505
2506        virtual void storeR0ToTOS() {
2507            fprintf(stderr, "storeR0ToTOS()\n");
2508            mpBase->storeR0ToTOS();
2509        }
2510
2511        virtual void loadR0FromR0() {
2512            fprintf(stderr, "loadR0FromR0()\n");
2513            mpBase->loadR0FromR0();
2514        }
2515
2516        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
2517            fprintf(stderr, "leaR0(%d, %d, %d)\n", ea,
2518                    pPointerType->pHead->tag, et);
2519            mpBase->leaR0(ea, pPointerType, et);
2520        }
2521
2522        virtual int leaForward(int ea, Type* pPointerType) {
2523            fprintf(stderr, "leaForward(%d)\n", ea);
2524            return mpBase->leaForward(ea, pPointerType);
2525        }
2526
2527        virtual void convertR0(Type* pType){
2528            fprintf(stderr, "convertR0(pType tag=%d)\n",  pType->tag);
2529            mpBase->convertR0(pType);
2530        }
2531
2532        virtual int beginFunctionCallArguments() {
2533            int result = mpBase->beginFunctionCallArguments();
2534            fprintf(stderr, "beginFunctionCallArguments() = %d\n", result);
2535            return result;
2536        }
2537
2538        virtual size_t storeR0ToArg(int l, Type* pArgType) {
2539            fprintf(stderr, "storeR0ToArg(%d, pArgType=%d)\n", l,
2540                    pArgType->tag);
2541            return mpBase->storeR0ToArg(l, pArgType);
2542        }
2543
2544        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
2545            fprintf(stderr, "endFunctionCallArguments(%d, %d)\n", a, l);
2546            mpBase->endFunctionCallArguments(pDecl, a, l);
2547        }
2548
2549        virtual int callForward(int symbol, Type* pFunc) {
2550            int result = mpBase->callForward(symbol, pFunc);
2551            fprintf(stderr, "callForward(%d) = %d\n", symbol, result);
2552            return result;
2553        }
2554
2555        virtual void callIndirect(int l, Type* pFunc) {
2556            fprintf(stderr, "callIndirect(%d returntype = %d)\n", l,
2557                    pFunc->pHead->tag);
2558            mpBase->callIndirect(l, pFunc);
2559        }
2560
2561        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
2562            fprintf(stderr, "adjustStackAfterCall(pType, %d, %d)\n", l, isIndirect);
2563            mpBase->adjustStackAfterCall(pDecl, l, isIndirect);
2564        }
2565
2566        virtual int jumpOffset() {
2567            return mpBase->jumpOffset();
2568        }
2569
2570        virtual int disassemble(FILE* out) {
2571            return mpBase->disassemble(out);
2572        }
2573
2574        /* output a symbol and patch all calls to it */
2575        virtual void gsym(int t) {
2576            fprintf(stderr, "gsym(%d)\n", t);
2577            mpBase->gsym(t);
2578        }
2579
2580        virtual void resolveForward(int t) {
2581            mpBase->resolveForward(t);
2582        }
2583
2584        virtual int finishCompile() {
2585            int result = mpBase->finishCompile();
2586            fprintf(stderr, "finishCompile() = %d\n", result);
2587            return result;
2588        }
2589
2590        /**
2591         * Alignment (in bytes) for this type of data
2592         */
2593        virtual size_t alignmentOf(Type* pType){
2594            return mpBase->alignmentOf(pType);
2595        }
2596
2597        /**
2598         * Array element alignment (in bytes) for this type of data.
2599         */
2600        virtual size_t sizeOf(Type* pType){
2601            return mpBase->sizeOf(pType);
2602        }
2603
2604
2605        virtual size_t stackAlignmentOf(Type* pType) {
2606            return mpBase->stackAlignmentOf(pType);
2607        }
2608
2609
2610        virtual size_t stackSizeOf(Type* pType) {
2611            return mpBase->stackSizeOf(pType);
2612        }
2613
2614        virtual Type* getR0Type() {
2615            return mpBase->getR0Type();
2616        }
2617
2618        virtual ExpressionType getR0ExpressionType() {
2619            return mpBase->getR0ExpressionType();
2620        }
2621
2622        virtual void setR0ExpressionType(ExpressionType et) {
2623            mpBase->setR0ExpressionType(et);
2624        }
2625
2626        virtual size_t getExpressionStackDepth() {
2627            return mpBase->getExpressionStackDepth();
2628        }
2629
2630        virtual void forceR0RVal() {
2631            return mpBase->forceR0RVal();
2632        }
2633    };
2634
2635#endif // PROVIDE_TRACE_CODEGEN
2636
2637    class Arena {
2638    public:
2639        // Used to record a given allocation amount.
2640        // Used:
2641        // Mark mark = arena.mark();
2642        // ... lots of arena.allocate()
2643        // arena.free(mark);
2644
2645        struct Mark {
2646            size_t chunk;
2647            size_t offset;
2648        };
2649
2650        Arena() {
2651            mCurrentChunk = 0;
2652            Chunk start(CHUNK_SIZE);
2653            mData.push_back(start);
2654        }
2655
2656        ~Arena() {
2657            for(size_t i = 0; i < mData.size(); i++) {
2658                mData[i].free();
2659            }
2660        }
2661
2662        // Alloc using the standard alignment size safe for any variable
2663        void* alloc(size_t size) {
2664            return alloc(size, 8);
2665        }
2666
2667        Mark mark(){
2668            Mark result;
2669            result.chunk = mCurrentChunk;
2670            result.offset = mData[mCurrentChunk].mOffset;
2671            return result;
2672        }
2673
2674        void freeToMark(const Mark& mark) {
2675            mCurrentChunk = mark.chunk;
2676            mData[mCurrentChunk].mOffset = mark.offset;
2677        }
2678
2679    private:
2680        // Allocate memory aligned to a given size
2681        // and a given power-of-two-sized alignment (e.g. 1,2,4,8,...)
2682        // Memory is not zero filled.
2683
2684        void* alloc(size_t size, size_t alignment) {
2685            while (size > mData[mCurrentChunk].remainingCapacity(alignment)) {
2686                if (mCurrentChunk + 1 < mData.size()) {
2687                    mCurrentChunk++;
2688                } else {
2689                    size_t allocSize = CHUNK_SIZE;
2690                    if (allocSize < size + alignment - 1) {
2691                        allocSize = size + alignment - 1;
2692                    }
2693                    Chunk chunk(allocSize);
2694                    mData.push_back(chunk);
2695                    mCurrentChunk++;
2696                }
2697            }
2698            return mData[mCurrentChunk].allocate(size, alignment);
2699        }
2700
2701        static const size_t CHUNK_SIZE = 128*1024;
2702        // Note: this class does not deallocate its
2703        // memory when it's destroyed. It depends upon
2704        // its parent to deallocate the memory.
2705        struct Chunk {
2706            Chunk() {
2707                mpData = 0;
2708                mSize = 0;
2709                mOffset = 0;
2710            }
2711
2712            Chunk(size_t size) {
2713                mSize = size;
2714                mpData = (char*) malloc(size);
2715                mOffset = 0;
2716            }
2717
2718            ~Chunk() {
2719                // Doesn't deallocate memory.
2720            }
2721
2722            void* allocate(size_t size, size_t alignment) {
2723                size_t alignedOffset = aligned(mOffset, alignment);
2724                void* result = mpData + alignedOffset;
2725                mOffset = alignedOffset + size;
2726                return result;
2727            }
2728
2729            void free() {
2730                if (mpData) {
2731                    ::free(mpData);
2732                    mpData = 0;
2733                }
2734            }
2735
2736            size_t remainingCapacity(size_t alignment) {
2737                return aligned(mSize, alignment) - aligned(mOffset, alignment);
2738            }
2739
2740            // Assume alignment is a power of two
2741            inline size_t aligned(size_t v, size_t alignment) {
2742                size_t mask = alignment-1;
2743                return (v + mask) & ~mask;
2744            }
2745
2746            char* mpData;
2747            size_t mSize;
2748            size_t mOffset;
2749        };
2750
2751        size_t mCurrentChunk;
2752
2753        Vector<Chunk> mData;
2754    };
2755
2756    struct VariableInfo;
2757
2758    struct Token {
2759        int hash;
2760        size_t length;
2761        char* pText;
2762        tokenid_t id;
2763
2764        // Current values for the token
2765        char* mpMacroDefinition;
2766        VariableInfo* mpVariableInfo;
2767    };
2768
2769    class TokenTable {
2770    public:
2771        // Don't use 0..0xff, allows characters and operators to be tokens too.
2772
2773        static const int TOKEN_BASE = 0x100;
2774        TokenTable() {
2775            mpMap = hashmapCreate(128, hashFn, equalsFn);
2776        }
2777
2778        ~TokenTable() {
2779            hashmapFree(mpMap);
2780        }
2781
2782        void setArena(Arena* pArena) {
2783            mpArena = pArena;
2784        }
2785
2786        // Returns a token for a given string of characters.
2787        tokenid_t intern(const char* pText, size_t length) {
2788            Token probe;
2789            int hash = hashmapHash((void*) pText, length);
2790            {
2791                Token probe;
2792                probe.hash = hash;
2793                probe.length = length;
2794                probe.pText = (char*) pText;
2795                Token* pValue = (Token*) hashmapGet(mpMap, &probe);
2796                if (pValue) {
2797                    return pValue->id;
2798                }
2799            }
2800
2801            Token* pToken = (Token*) mpArena->alloc(sizeof(Token));
2802            memset(pToken, 0, sizeof(*pToken));
2803            pToken->hash = hash;
2804            pToken->length = length;
2805            pToken->pText = (char*) mpArena->alloc(length + 1);
2806            memcpy(pToken->pText, pText, length);
2807            pToken->pText[length] = 0;
2808            pToken->id = mTokens.size() + TOKEN_BASE;
2809            mTokens.push_back(pToken);
2810            hashmapPut(mpMap, pToken, pToken);
2811            return pToken->id;
2812        }
2813
2814        // Return the Token for a given tokenid.
2815        Token& operator[](tokenid_t id) {
2816            return *mTokens[id - TOKEN_BASE];
2817        }
2818
2819        inline size_t size() {
2820            return mTokens.size();
2821        }
2822
2823    private:
2824
2825        static int hashFn(void* pKey) {
2826            Token* pToken = (Token*) pKey;
2827            return pToken->hash;
2828        }
2829
2830        static bool equalsFn(void* keyA, void* keyB) {
2831            Token* pTokenA = (Token*) keyA;
2832            Token* pTokenB = (Token*) keyB;
2833            // Don't need to compare hash values, they should always be equal
2834            return pTokenA->length == pTokenB->length
2835                && strcmp(pTokenA->pText, pTokenB->pText) == 0;
2836        }
2837
2838        Hashmap* mpMap;
2839        Vector<Token*> mTokens;
2840        Arena* mpArena;
2841    };
2842
2843    class InputStream {
2844    public:
2845        virtual ~InputStream() {}
2846        virtual int getChar() = 0;
2847    };
2848
2849    class TextInputStream : public InputStream {
2850    public:
2851        TextInputStream(const char* text, size_t textLength)
2852            : pText(text), mTextLength(textLength), mPosition(0) {
2853        }
2854
2855        virtual int getChar() {
2856            return mPosition < mTextLength ? pText[mPosition++] : EOF;
2857        }
2858
2859    private:
2860        const char* pText;
2861        size_t mTextLength;
2862        size_t mPosition;
2863    };
2864
2865    class String {
2866    public:
2867        String() {
2868            mpBase = 0;
2869            mUsed = 0;
2870            mSize = 0;
2871        }
2872
2873        String(const char* item, int len, bool adopt) {
2874            if (len < 0) {
2875                len = strlen(item);
2876            }
2877            if (adopt) {
2878                mpBase = (char*) item;
2879                mUsed = len;
2880                mSize = len + 1;
2881            } else {
2882                mpBase = 0;
2883                mUsed = 0;
2884                mSize = 0;
2885                appendBytes(item, len);
2886            }
2887        }
2888
2889        String(const String& other) {
2890            mpBase = 0;
2891            mUsed = 0;
2892            mSize = 0;
2893            appendBytes(other.getUnwrapped(), other.len());
2894        }
2895
2896        ~String() {
2897            if (mpBase) {
2898                free(mpBase);
2899            }
2900        }
2901
2902        String& operator=(const String& other) {
2903            clear();
2904            appendBytes(other.getUnwrapped(), other.len());
2905            return *this;
2906        }
2907
2908        inline char* getUnwrapped() const {
2909            return mpBase;
2910        }
2911
2912        void clear() {
2913            mUsed = 0;
2914            if (mSize > 0) {
2915                mpBase[0] = 0;
2916            }
2917        }
2918
2919        void appendCStr(const char* s) {
2920            appendBytes(s, strlen(s));
2921        }
2922
2923        void appendBytes(const char* s, int n) {
2924            memcpy(ensure(n), s, n + 1);
2925        }
2926
2927        void append(char c) {
2928            * ensure(1) = c;
2929        }
2930
2931        void append(String& other) {
2932            appendBytes(other.getUnwrapped(), other.len());
2933        }
2934
2935        char* orphan() {
2936            char* result = mpBase;
2937            mpBase = 0;
2938            mUsed = 0;
2939            mSize = 0;
2940            return result;
2941        }
2942
2943        void printf(const char* fmt,...) {
2944            va_list ap;
2945            va_start(ap, fmt);
2946            vprintf(fmt, ap);
2947            va_end(ap);
2948        }
2949
2950        void vprintf(const char* fmt, va_list ap) {
2951            char* temp;
2952            int numChars = vasprintf(&temp, fmt, ap);
2953            memcpy(ensure(numChars), temp, numChars+1);
2954            free(temp);
2955        }
2956
2957        inline size_t len() const {
2958            return mUsed;
2959        }
2960
2961    private:
2962        char* ensure(int n) {
2963            size_t newUsed = mUsed + n;
2964            if (newUsed > mSize) {
2965                size_t newSize = mSize * 2 + 10;
2966                if (newSize < newUsed) {
2967                    newSize = newUsed;
2968                }
2969                mpBase = (char*) realloc(mpBase, newSize + 1);
2970                mSize = newSize;
2971            }
2972            mpBase[newUsed] = '\0';
2973            char* result = mpBase + mUsed;
2974            mUsed = newUsed;
2975            return result;
2976        }
2977
2978        char* mpBase;
2979        size_t mUsed;
2980        size_t mSize;
2981    };
2982
2983    void internKeywords() {
2984        // Note: order has to match TOK_ constants
2985        static const char* keywords[] = {
2986            "int",
2987            "char",
2988            "void",
2989            "if",
2990            "else",
2991            "while",
2992            "break",
2993            "return",
2994            "for",
2995            "auto",
2996            "case",
2997            "const",
2998            "continue",
2999            "default",
3000            "do",
3001            "double",
3002            "enum",
3003            "extern",
3004            "float",
3005            "goto",
3006            "long",
3007            "register",
3008            "short",
3009            "signed",
3010            "sizeof",
3011            "static",
3012            "struct",
3013            "switch",
3014            "typedef",
3015            "union",
3016            "unsigned",
3017            "volatile",
3018            "_Bool",
3019            "_Complex",
3020            "_Imaginary",
3021            "inline",
3022            "restrict",
3023
3024            // predefined tokens that can also be symbols start here:
3025            "pragma",
3026            "define",
3027            "line",
3028            0};
3029
3030        for(int i = 0; keywords[i]; i++) {
3031            mTokenTable.intern(keywords[i], strlen(keywords[i]));
3032        }
3033    }
3034
3035    struct InputState {
3036        InputStream* pStream;
3037        int oldCh;
3038    };
3039
3040    struct VariableInfo {
3041        void* pAddress;
3042        void* pForward; // For a forward direction, linked list of data to fix up
3043        tokenid_t tok;
3044        size_t level;
3045        VariableInfo* pOldDefinition;
3046        Type* pType;
3047    };
3048
3049    class SymbolStack {
3050    public:
3051        SymbolStack() {
3052            mpArena = 0;
3053            mpTokenTable = 0;
3054        }
3055
3056        void setArena(Arena* pArena) {
3057            mpArena = pArena;
3058        }
3059
3060        void setTokenTable(TokenTable* pTokenTable) {
3061            mpTokenTable = pTokenTable;
3062        }
3063
3064        void pushLevel() {
3065            Mark mark;
3066            mark.mArenaMark = mpArena->mark();
3067            mark.mSymbolHead = mStack.size();
3068            mLevelStack.push_back(mark);
3069        }
3070
3071        void popLevel() {
3072            // Undo any shadowing that was done:
3073            Mark mark = mLevelStack.back();
3074            mLevelStack.pop_back();
3075            while (mStack.size() > mark.mSymbolHead) {
3076                VariableInfo* pV = mStack.back();
3077                mStack.pop_back();
3078                (*mpTokenTable)[pV->tok].mpVariableInfo = pV->pOldDefinition;
3079            }
3080            mpArena->freeToMark(mark.mArenaMark);
3081        }
3082
3083        bool isDefinedAtCurrentLevel(tokenid_t tok) {
3084            VariableInfo* pV = (*mpTokenTable)[tok].mpVariableInfo;
3085            return pV && pV->level == level();
3086        }
3087
3088        VariableInfo* add(tokenid_t tok) {
3089            Token& token = (*mpTokenTable)[tok];
3090            VariableInfo* pOldV = token.mpVariableInfo;
3091            VariableInfo* pNewV =
3092                (VariableInfo*) mpArena->alloc(sizeof(VariableInfo));
3093            memset(pNewV, 0, sizeof(VariableInfo));
3094            pNewV->tok = tok;
3095            pNewV->level = level();
3096            pNewV->pOldDefinition = pOldV;
3097            token.mpVariableInfo = pNewV;
3098            mStack.push_back(pNewV);
3099            return pNewV;
3100        }
3101
3102        VariableInfo* add(Type* pType) {
3103            VariableInfo* pVI = add(pType->id);
3104            pVI->pType = pType;
3105            return pVI;
3106        }
3107
3108        void forEach(bool (*fn)(VariableInfo*, void*), void* context) {
3109            for (size_t i = 0; i < mStack.size(); i++) {
3110                if (! fn(mStack[i], context)) {
3111                    break;
3112                }
3113            }
3114        }
3115
3116    private:
3117        inline size_t level() {
3118            return mLevelStack.size();
3119        }
3120
3121        struct Mark {
3122            Arena::Mark mArenaMark;
3123            size_t mSymbolHead;
3124        };
3125
3126        Arena* mpArena;
3127        TokenTable* mpTokenTable;
3128        Vector<VariableInfo*> mStack;
3129        Vector<Mark> mLevelStack;
3130    };
3131
3132    int ch; // Current input character, or EOF
3133    tokenid_t tok;      // token
3134    intptr_t tokc;    // token extra info
3135    double tokd;     // floating point constant value
3136    int tokl;         // token operator level
3137    intptr_t rsym; // return symbol
3138    Type* pReturnType; // type of the current function's return.
3139    intptr_t loc; // local variable index
3140    char* glo;  // global variable index
3141    String mTokenString;
3142    char* dptr; // Macro state: Points to macro text during macro playback.
3143    int dch;    // Macro state: Saves old value of ch during a macro playback.
3144    char* pGlobalBase;
3145    ACCSymbolLookupFn mpSymbolLookupFn;
3146    void* mpSymbolLookupContext;
3147
3148    // Arena for the duration of the compile
3149    Arena mGlobalArena;
3150    // Arena for data that's only needed when compiling a single function
3151    Arena mLocalArena;
3152
3153    Arena* mpCurrentArena;
3154
3155    TokenTable mTokenTable;
3156    SymbolStack mGlobals;
3157    SymbolStack mLocals;
3158
3159    // Prebuilt types, makes things slightly faster.
3160    Type* mkpInt;        // int
3161    Type* mkpChar;       // char
3162    Type* mkpVoid;       // void
3163    Type* mkpFloat;
3164    Type* mkpDouble;
3165    Type* mkpIntFn;
3166    Type* mkpIntPtr;
3167    Type* mkpCharPtr;
3168    Type* mkpFloatPtr;
3169    Type* mkpDoublePtr;
3170    Type* mkpPtrIntFn;
3171
3172    InputStream* file;
3173    int mLineNumber;
3174    bool mbBumpLine;
3175
3176    CodeBuf codeBuf;
3177    CodeGenerator* pGen;
3178
3179    String mErrorBuf;
3180
3181    String mPragmas;
3182    int mPragmaStringCount;
3183    int mCompileResult;
3184
3185    static const int ALLOC_SIZE = 99999;
3186
3187    static const int TOK_DUMMY = 1;
3188    static const int TOK_NUM = 2;
3189    static const int TOK_NUM_FLOAT = 3;
3190    static const int TOK_NUM_DOUBLE = 4;
3191    static const int TOK_OP_ASSIGNMENT = 5;
3192
3193    // 3..255 are character and/or operators
3194
3195    // Keywords start at 0x100 and increase by 1
3196    // Order has to match string list in "internKeywords".
3197    enum {
3198        TOK_KEYWORD = TokenTable::TOKEN_BASE,
3199        TOK_INT = TOK_KEYWORD,
3200        TOK_CHAR,
3201        TOK_VOID,
3202        TOK_IF,
3203        TOK_ELSE,
3204        TOK_WHILE,
3205        TOK_BREAK,
3206        TOK_RETURN,
3207        TOK_FOR,
3208        TOK_AUTO,
3209        TOK_CASE,
3210        TOK_CONST,
3211        TOK_CONTINUE,
3212        TOK_DEFAULT,
3213        TOK_DO,
3214        TOK_DOUBLE,
3215        TOK_ENUM,
3216        TOK_EXTERN,
3217        TOK_FLOAT,
3218        TOK_GOTO,
3219        TOK_LONG,
3220        TOK_REGISTER,
3221        TOK_SHORT,
3222        TOK_SIGNED,
3223        TOK_SIZEOF,
3224        TOK_STATIC,
3225        TOK_STRUCT,
3226        TOK_SWITCH,
3227        TOK_TYPEDEF,
3228        TOK_UNION,
3229        TOK_UNSIGNED,
3230        TOK_VOLATILE,
3231        TOK__BOOL,
3232        TOK__COMPLEX,
3233        TOK__IMAGINARY,
3234        TOK_INLINE,
3235        TOK_RESTRICT,
3236
3237        // Symbols start after keywords
3238
3239        TOK_SYMBOL,
3240        TOK_PRAGMA = TOK_SYMBOL,
3241        TOK_DEFINE,
3242        TOK_LINE
3243    };
3244
3245    static const int LOCAL = 0x200;
3246
3247    static const int SYM_FORWARD = 0;
3248    static const int SYM_DEFINE = 1;
3249
3250    /* tokens in string heap */
3251    static const int TAG_TOK = ' ';
3252
3253    static const int OP_INCREMENT = 0;
3254    static const int OP_DECREMENT = 1;
3255    static const int OP_MUL = 2;
3256    static const int OP_DIV = 3;
3257    static const int OP_MOD = 4;
3258    static const int OP_PLUS = 5;
3259    static const int OP_MINUS = 6;
3260    static const int OP_SHIFT_LEFT = 7;
3261    static const int OP_SHIFT_RIGHT = 8;
3262    static const int OP_LESS_EQUAL = 9;
3263    static const int OP_GREATER_EQUAL = 10;
3264    static const int OP_LESS = 11;
3265    static const int OP_GREATER = 12;
3266    static const int OP_EQUALS = 13;
3267    static const int OP_NOT_EQUALS = 14;
3268    static const int OP_LOGICAL_AND = 15;
3269    static const int OP_LOGICAL_OR = 16;
3270    static const int OP_BIT_AND = 17;
3271    static const int OP_BIT_XOR = 18;
3272    static const int OP_BIT_OR = 19;
3273    static const int OP_BIT_NOT = 20;
3274    static const int OP_LOGICAL_NOT = 21;
3275    static const int OP_COUNT = 22;
3276
3277    /* Operators are searched from front, the two-character operators appear
3278     * before the single-character operators with the same first character.
3279     * @ is used to pad out single-character operators.
3280     */
3281    static const char* operatorChars;
3282    static const char operatorLevel[];
3283
3284    /* Called when we detect an internal problem. Does nothing in production.
3285     *
3286     */
3287    void internalError() {
3288        * (char*) 0 = 0;
3289    }
3290
3291    void assert(bool isTrue) {
3292        if (!isTrue) {
3293            internalError();
3294        }
3295    }
3296
3297    bool isSymbol(tokenid_t t) {
3298        return t >= TOK_SYMBOL &&
3299            ((size_t) (t-TOK_SYMBOL)) < mTokenTable.size();
3300    }
3301
3302    bool isSymbolOrKeyword(tokenid_t t) {
3303        return t >= TOK_KEYWORD &&
3304            ((size_t) (t-TOK_KEYWORD)) < mTokenTable.size();
3305    }
3306
3307    VariableInfo* VI(tokenid_t t) {
3308        assert(isSymbol(t));
3309        VariableInfo* pV = mTokenTable[t].mpVariableInfo;
3310        if (pV && pV->tok != t) {
3311            internalError();
3312        }
3313        return pV;
3314    }
3315
3316    inline bool isDefined(tokenid_t t) {
3317        return t >= TOK_SYMBOL && VI(t) != 0;
3318    }
3319
3320    const char* nameof(tokenid_t t) {
3321        assert(isSymbolOrKeyword(t));
3322        return mTokenTable[t].pText;
3323    }
3324
3325    void pdef(int t) {
3326        mTokenString.append(t);
3327    }
3328
3329    void inp() {
3330        if (dptr) {
3331            ch = *dptr++;
3332            if (ch == 0) {
3333                dptr = 0;
3334                ch = dch;
3335            }
3336        } else {
3337            if (mbBumpLine) {
3338                mLineNumber++;
3339                mbBumpLine = false;
3340            }
3341            ch = file->getChar();
3342            if (ch == '\n') {
3343                mbBumpLine = true;
3344            }
3345        }
3346#if 0
3347        printf("ch='%c' 0x%x\n", ch, ch);
3348#endif
3349    }
3350
3351    int isid() {
3352        return isalnum(ch) | (ch == '_');
3353    }
3354
3355    int decodeHex(int c) {
3356        if (isdigit(c)) {
3357            c -= '0';
3358        } else if (c <= 'F') {
3359            c = c - 'A' + 10;
3360        } else {
3361            c =c - 'a' + 10;
3362        }
3363        return c;
3364    }
3365
3366    /* read a character constant, advances ch to after end of constant */
3367    int getq() {
3368        int val = ch;
3369        if (ch == '\\') {
3370            inp();
3371            if (isoctal(ch)) {
3372                // 1 to 3 octal characters.
3373                val = 0;
3374                for(int i = 0; i < 3; i++) {
3375                    if (isoctal(ch)) {
3376                        val = (val << 3) + ch - '0';
3377                        inp();
3378                    }
3379                }
3380                return val;
3381            } else if (ch == 'x' || ch == 'X') {
3382                // N hex chars
3383                inp();
3384                if (! isxdigit(ch)) {
3385                    error("'x' character escape requires at least one digit.");
3386                } else {
3387                    val = 0;
3388                    while (isxdigit(ch)) {
3389                        val = (val << 4) + decodeHex(ch);
3390                        inp();
3391                    }
3392                }
3393            } else {
3394                int val = ch;
3395                switch (ch) {
3396                    case 'a':
3397                        val = '\a';
3398                        break;
3399                    case 'b':
3400                        val = '\b';
3401                        break;
3402                    case 'f':
3403                        val = '\f';
3404                        break;
3405                    case 'n':
3406                        val = '\n';
3407                        break;
3408                    case 'r':
3409                        val = '\r';
3410                        break;
3411                    case 't':
3412                        val = '\t';
3413                        break;
3414                    case 'v':
3415                        val = '\v';
3416                        break;
3417                    case '\\':
3418                        val = '\\';
3419                        break;
3420                    case '\'':
3421                        val = '\'';
3422                        break;
3423                    case '"':
3424                        val = '"';
3425                        break;
3426                    case '?':
3427                        val = '?';
3428                        break;
3429                    default:
3430                        error("Undefined character escape %c", ch);
3431                        break;
3432                }
3433                inp();
3434                return val;
3435            }
3436        } else {
3437            inp();
3438        }
3439        return val;
3440    }
3441
3442    static bool isoctal(int ch) {
3443        return ch >= '0' && ch <= '7';
3444    }
3445
3446    bool acceptCh(int c) {
3447        bool result = c == ch;
3448        if (result) {
3449            pdef(ch);
3450            inp();
3451        }
3452        return result;
3453    }
3454
3455    bool acceptDigitsCh() {
3456        bool result = false;
3457        while (isdigit(ch)) {
3458            result = true;
3459            pdef(ch);
3460            inp();
3461        }
3462        return result;
3463    }
3464
3465    void parseFloat() {
3466        tok = TOK_NUM_DOUBLE;
3467        // mTokenString already has the integral part of the number.
3468        if(mTokenString.len() == 0) {
3469            mTokenString.append('0');
3470        }
3471        acceptCh('.');
3472        acceptDigitsCh();
3473        if (acceptCh('e') || acceptCh('E')) {
3474            acceptCh('-') || acceptCh('+');
3475            acceptDigitsCh();
3476        }
3477        if (ch == 'f' || ch == 'F') {
3478            tok = TOK_NUM_FLOAT;
3479            inp();
3480        } else if (ch == 'l' || ch == 'L') {
3481            inp();
3482            error("Long floating point constants not supported.");
3483        }
3484        char* pText = mTokenString.getUnwrapped();
3485        char* pEnd = pText + strlen(pText);
3486        char* pEndPtr = 0;
3487        errno = 0;
3488        if (tok == TOK_NUM_FLOAT) {
3489            tokd = strtof(pText, &pEndPtr);
3490        } else {
3491            tokd = strtod(pText, &pEndPtr);
3492        }
3493        if (errno || pEndPtr != pEnd) {
3494            error("Can't parse constant: %s", pText);
3495        }
3496        // fprintf(stderr, "float constant: %s (%d) %g\n", pText, tok, tokd);
3497    }
3498
3499    void next() {
3500        int l, a;
3501
3502        while (isspace(ch) | (ch == '#')) {
3503            if (ch == '#') {
3504                inp();
3505                next();
3506                if (tok == TOK_DEFINE) {
3507                    doDefine();
3508                } else if (tok == TOK_PRAGMA) {
3509                    doPragma();
3510                } else if (tok == TOK_LINE) {
3511                    doLine();
3512                } else {
3513                    error("Unsupported preprocessor directive \"%s\"",
3514                          mTokenString.getUnwrapped());
3515                }
3516            }
3517            inp();
3518        }
3519        tokl = 0;
3520        tok = ch;
3521        /* encode identifiers & numbers */
3522        if (isdigit(ch) || ch == '.') {
3523            // Start of a numeric constant. Could be integer, float, or
3524            // double, won't know until we look further.
3525            mTokenString.clear();
3526            pdef(ch);
3527            inp();
3528            int base = 10;
3529            if (tok == '0') {
3530                if (ch == 'x' || ch == 'X') {
3531                    base = 16;
3532                    tok = TOK_NUM;
3533                    tokc = 0;
3534                    inp();
3535                    while ( isxdigit(ch) ) {
3536                        tokc = (tokc << 4) + decodeHex(ch);
3537                        inp();
3538                    }
3539                } else if (isoctal(ch)){
3540                    base = 8;
3541                    tok = TOK_NUM;
3542                    tokc = 0;
3543                    while ( isoctal(ch) ) {
3544                        tokc = (tokc << 3) + (ch - '0');
3545                        inp();
3546                    }
3547                }
3548            } else if (isdigit(tok)){
3549                acceptDigitsCh();
3550            }
3551            if (base == 10) {
3552                if (tok == '.' || ch == '.' || ch == 'e' || ch == 'E') {
3553                    parseFloat();
3554                } else {
3555                    // It's an integer constant
3556                    char* pText = mTokenString.getUnwrapped();
3557                    char* pEnd = pText + strlen(pText);
3558                    char* pEndPtr = 0;
3559                    errno = 0;
3560                    tokc = strtol(pText, &pEndPtr, base);
3561                    if (errno || pEndPtr != pEnd) {
3562                        error("Can't parse constant: %s %d %d", pText, base, errno);
3563                    }
3564                    tok = TOK_NUM;
3565                }
3566            }
3567        } else if (isid()) {
3568            mTokenString.clear();
3569            while (isid()) {
3570                pdef(ch);
3571                inp();
3572            }
3573            tok = mTokenTable.intern(mTokenString.getUnwrapped(), mTokenString.len());
3574            // Is this a macro?
3575            char* pMacroDefinition = mTokenTable[tok].mpMacroDefinition;
3576            if (pMacroDefinition) {
3577                // Yes, it is a macro
3578                dptr = pMacroDefinition;
3579                dch = ch;
3580                inp();
3581                next();
3582            }
3583        } else {
3584            inp();
3585            if (tok == '\'') {
3586                tok = TOK_NUM;
3587                tokc = getq();
3588                if (ch != '\'') {
3589                    error("Expected a ' character, got %c", ch);
3590                } else {
3591                  inp();
3592                }
3593            } else if ((tok == '/') & (ch == '*')) {
3594                inp();
3595                while (ch && ch != EOF) {
3596                    while (ch != '*' && ch != EOF)
3597                        inp();
3598                    inp();
3599                    if (ch == '/')
3600                        ch = 0;
3601                }
3602                if (ch == EOF) {
3603                    error("End of file inside comment.");
3604                }
3605                inp();
3606                next();
3607            } else if ((tok == '/') & (ch == '/')) {
3608                inp();
3609                while (ch && (ch != '\n') && (ch != EOF)) {
3610                    inp();
3611                }
3612                inp();
3613                next();
3614            } else {
3615                const char* t = operatorChars;
3616                int opIndex = 0;
3617                while ((l = *t++) != 0) {
3618                    a = *t++;
3619                    tokl = operatorLevel[opIndex];
3620                    tokc = opIndex;
3621                    if ((l == tok) & ((a == ch) | (a == '@'))) {
3622#if 0
3623                        printf("%c%c -> tokl=%d tokc=0x%x\n",
3624                                l, a, tokl, tokc);
3625#endif
3626                        if (a == ch) {
3627                            inp();
3628                            tok = TOK_DUMMY; /* dummy token for double tokens */
3629                        }
3630                        /* check for op=, valid for * / % + - << >> & ^ | */
3631                        if (ch == '=' &&
3632                                ((tokl >= 1 && tokl <= 3)
3633                                        || tokl >=6 && tokl <= 8) ) {
3634                            inp();
3635                            tok = TOK_OP_ASSIGNMENT;
3636                        }
3637                        break;
3638                    }
3639                    opIndex++;
3640                }
3641                if (l == 0) {
3642                    tokl = 0;
3643                    tokc = 0;
3644                }
3645            }
3646        }
3647#if 0
3648        {
3649            String buf;
3650            decodeToken(buf, tok, true);
3651            fprintf(stderr, "%s\n", buf.getUnwrapped());
3652        }
3653#endif
3654    }
3655
3656    void doDefine() {
3657        next();
3658        tokenid_t name = tok;
3659        String* pName = new String();
3660        while (isspace(ch)) {
3661            inp();
3662        }
3663        if (ch == '(') {
3664            delete pName;
3665            error("Defines with arguments not supported");
3666            return;
3667        }
3668        while (isspace(ch)) {
3669            inp();
3670        }
3671        String value;
3672        while (ch != '\n' && ch != EOF) {
3673            value.append(ch);
3674            inp();
3675        }
3676        char* pDefn = (char*)mGlobalArena.alloc(value.len() + 1);
3677        memcpy(pDefn, value.getUnwrapped(), value.len());
3678        pDefn[value.len()] = 0;
3679        mTokenTable[name].mpMacroDefinition = pDefn;
3680    }
3681
3682    void doPragma() {
3683        // # pragma name(val)
3684        int state = 0;
3685        while(ch != EOF && ch != '\n' && state < 10) {
3686            switch(state) {
3687                case 0:
3688                    if (isspace(ch)) {
3689                        inp();
3690                    } else {
3691                        state++;
3692                    }
3693                    break;
3694                case 1:
3695                    if (isalnum(ch)) {
3696                        mPragmas.append(ch);
3697                        inp();
3698                    } else if (ch == '(') {
3699                        mPragmas.append(0);
3700                        inp();
3701                        state++;
3702                    } else {
3703                        state = 11;
3704                    }
3705                    break;
3706                case 2:
3707                    if (isalnum(ch)) {
3708                        mPragmas.append(ch);
3709                        inp();
3710                    } else if (ch == ')') {
3711                        mPragmas.append(0);
3712                        inp();
3713                        state = 10;
3714                    } else {
3715                        state = 11;
3716                    }
3717                    break;
3718            }
3719        }
3720        if(state != 10) {
3721            error("Unexpected pragma syntax");
3722        }
3723        mPragmaStringCount += 2;
3724    }
3725
3726    void doLine() {
3727        // # line number { "filename "}
3728        next();
3729        if (tok != TOK_NUM) {
3730            error("Expected a line-number");
3731        } else {
3732            mLineNumber = tokc-1; // The end-of-line will increment it.
3733        }
3734        while(ch != EOF && ch != '\n') {
3735            inp();
3736        }
3737    }
3738
3739    virtual void verror(const char* fmt, va_list ap) {
3740        mErrorBuf.printf("%ld: ", mLineNumber);
3741        mErrorBuf.vprintf(fmt, ap);
3742        mErrorBuf.printf("\n");
3743    }
3744
3745    void skip(intptr_t c) {
3746        if (tok != c) {
3747            error("'%c' expected", c);
3748        }
3749        next();
3750    }
3751
3752    bool accept(intptr_t c) {
3753        if (tok == c) {
3754            next();
3755            return true;
3756        }
3757        return false;
3758    }
3759
3760    bool acceptStringLiteral() {
3761        if (tok == '"') {
3762            pGen->leaR0((int) glo, mkpCharPtr, ET_RVALUE);
3763            // This while loop merges multiple adjacent string constants.
3764            while (tok == '"') {
3765                while (ch != '"' && ch != EOF) {
3766                    *allocGlobalSpace(1,1) = getq();
3767                }
3768                if (ch != '"') {
3769                    error("Unterminated string constant.");
3770                }
3771                inp();
3772                next();
3773            }
3774            /* Null terminate */
3775            *glo = 0;
3776            /* align heap */
3777            allocGlobalSpace(1,(char*) (((intptr_t) glo + 4) & -4) - glo);
3778
3779            return true;
3780        }
3781        return false;
3782    }
3783
3784    void linkGlobal(tokenid_t t, bool isFunction) {
3785        VariableInfo* pVI = VI(t);
3786        void* n = NULL;
3787        if (mpSymbolLookupFn) {
3788            n = mpSymbolLookupFn(mpSymbolLookupContext, nameof(t));
3789        }
3790        if (pVI->pType == NULL) {
3791            if (isFunction) {
3792                pVI->pType = mkpIntFn;
3793            } else {
3794                pVI->pType = mkpInt;
3795            }
3796        }
3797        pVI->pAddress = n;
3798    }
3799
3800    void unaryOrAssignment() {
3801        unary();
3802        if (accept('=')) {
3803            checkLVal();
3804            pGen->pushR0();
3805            expr();
3806            pGen->forceR0RVal();
3807            pGen->storeR0ToTOS();
3808        } else if (tok == TOK_OP_ASSIGNMENT) {
3809            int t = tokc;
3810            next();
3811            checkLVal();
3812            pGen->pushR0();
3813            pGen->forceR0RVal();
3814            pGen->pushR0();
3815            expr();
3816            pGen->forceR0RVal();
3817            pGen->genOp(t);
3818            pGen->storeR0ToTOS();
3819        }
3820    }
3821
3822    /* Parse and evaluate a unary expression.
3823     */
3824    void unary() {
3825        tokenid_t t;
3826        intptr_t a;
3827        t = 0;
3828        if (acceptStringLiteral()) {
3829            // Nothing else to do.
3830        } else {
3831            int c = tokl;
3832            a = tokc;
3833            double ad = tokd;
3834            t = tok;
3835            next();
3836            if (t == TOK_NUM) {
3837                pGen->li(a);
3838            } else if (t == TOK_NUM_FLOAT) {
3839                // Align to 4-byte boundary
3840                glo = (char*) (((intptr_t) glo + 3) & -4);
3841                * (float*) glo = (float) ad;
3842                pGen->loadFloat((int) glo, mkpFloat);
3843                glo += 4;
3844            } else if (t == TOK_NUM_DOUBLE) {
3845                // Align to 8-byte boundary
3846                glo = (char*) (((intptr_t) glo + 7) & -8);
3847                * (double*) glo = ad;
3848                pGen->loadFloat((int) glo, mkpDouble);
3849                glo += 8;
3850            } else if (c == 2) {
3851                /* -, +, !, ~ */
3852                unary();
3853                pGen->forceR0RVal();
3854                if (t == '!')
3855                    pGen->gUnaryCmp(a);
3856                else if (t == '+') {
3857                    // ignore unary plus.
3858                } else {
3859                    pGen->genUnaryOp(a);
3860                }
3861            } else if (c == 11) {
3862                // pre increment / pre decrement
3863                unary();
3864                doIncDec(a == OP_INCREMENT, 0);
3865            }
3866            else if (t == '(') {
3867                // It's either a cast or an expression
3868                Type* pCast = acceptCastTypeDeclaration();
3869                if (pCast) {
3870                    skip(')');
3871                    unary();
3872                    pGen->forceR0RVal();
3873                    pGen->convertR0(pCast);
3874                } else {
3875                    commaExpr();
3876                    skip(')');
3877                }
3878            } else if (t == '*') {
3879                /* This is a pointer dereference.
3880                 */
3881                unary();
3882                pGen->forceR0RVal();
3883                Type* pR0Type = pGen->getR0Type();
3884                if (pR0Type->tag != TY_POINTER) {
3885                    error("Expected a pointer type.");
3886                } else {
3887                    if (pR0Type->pHead->tag == TY_FUNC) {
3888                        t = 0;
3889                    }
3890                    if (t) {
3891                        pGen->setR0ExpressionType(ET_LVALUE);
3892                    }
3893                }
3894            } else if (t == '&') {
3895                VariableInfo* pVI = VI(tok);
3896                pGen->leaR0((int) pVI->pAddress, createPtrType(pVI->pType),
3897                        ET_RVALUE);
3898                next();
3899            } else if (t == EOF ) {
3900                error("Unexpected EOF.");
3901            } else if (t == ';') {
3902                error("Unexpected ';'");
3903            } else if (!checkSymbol(t)) {
3904                // Don't have to do anything special here, the error
3905                // message was printed by checkSymbol() above.
3906            } else {
3907                if (!isDefined(t)) {
3908                    mGlobals.add(t);
3909                    // printf("Adding new global function %s\n", nameof(t));
3910                }
3911                VariableInfo* pVI = VI(t);
3912                int n = (intptr_t) pVI->pAddress;
3913                /* forward reference: try our lookup function */
3914                if (!n) {
3915                    linkGlobal(t, tok == '(');
3916                    n = (intptr_t) pVI->pAddress;
3917                    if (!n && tok != '(') {
3918                        error("Undeclared variable %s\n", nameof(t));
3919                    }
3920                }
3921                if (tok != '(') {
3922                    /* variable or function name */
3923                    if (!n) {
3924                        linkGlobal(t, false);
3925                        n = (intptr_t) pVI->pAddress;
3926                        if (!n) {
3927                            error("Undeclared variable %s\n", nameof(t));
3928                        }
3929                    }
3930                }
3931                // load a variable
3932                Type* pVal = createPtrType(pVI->pType);
3933                if (n) {
3934                    ExpressionType et = ET_LVALUE;
3935                    if (pVal->pHead->tag == TY_FUNC) {
3936                        et = ET_RVALUE;
3937                    }
3938                    pGen->leaR0(n, pVal, et);
3939                } else {
3940                    pVI->pForward = (void*) pGen->leaForward(
3941                            (int) pVI->pForward, pVal);
3942                }
3943            }
3944        }
3945
3946        /* Now handle postfix operators */
3947        for(;;) {
3948            if (tokl == 11) {
3949                // post inc / post dec
3950                doIncDec(tokc == OP_INCREMENT, true);
3951                next();
3952            } else  if (accept('(')) {
3953                /* function call */
3954                Type* pDecl = NULL;
3955                VariableInfo* pVI = NULL;
3956                Type* pFn = pGen->getR0Type();
3957                assert(pFn->tag == TY_POINTER);
3958                assert(pFn->pHead->tag == TY_FUNC);
3959                pDecl = pFn->pHead;
3960                pGen->pushR0();
3961                Type* pArgList = pDecl->pTail;
3962                bool varArgs = pArgList == NULL;
3963                /* push args and invert order */
3964                a = pGen->beginFunctionCallArguments();
3965                int l = 0;
3966                int argCount = 0;
3967                while (tok != ')' && tok != EOF) {
3968                    if (! varArgs && !pArgList) {
3969                        error("Unexpected argument.");
3970                    }
3971                    expr();
3972                    pGen->forceR0RVal();
3973                    Type* pTargetType;
3974                    if (pArgList) {
3975                        pTargetType = pArgList->pHead;
3976                        pArgList = pArgList->pTail;
3977                    } else {
3978                        // This is a ... function, just pass arguments in their
3979                        // natural type.
3980                        pTargetType = pGen->getR0Type();
3981                        if (pTargetType->tag == TY_FLOAT) {
3982                            pTargetType = mkpDouble;
3983                        }
3984                    }
3985                    if (pTargetType->tag == TY_VOID) {
3986                        error("Can't pass void value for argument %d",
3987                              argCount + 1);
3988                    } else {
3989                        l += pGen->storeR0ToArg(l, pTargetType);
3990                    }
3991                    if (accept(',')) {
3992                        // fine
3993                    } else if ( tok != ')') {
3994                        error("Expected ',' or ')'");
3995                    }
3996                    argCount += 1;
3997                }
3998                if (! varArgs && pArgList) {
3999                    error("Expected more argument(s). Saw %d", argCount);
4000                }
4001                pGen->endFunctionCallArguments(pDecl, a, l);
4002                skip(')');
4003                pGen->callIndirect(l, pDecl);
4004                pGen->adjustStackAfterCall(pDecl, l, true);
4005            } else {
4006                break;
4007            }
4008        }
4009    }
4010
4011    void doIncDec(int isInc, int isPost) {
4012        // R0 already has the lval
4013        checkLVal();
4014        int lit = isInc ? 1 : -1;
4015        pGen->pushR0();
4016        pGen->loadR0FromR0();
4017        int tag = pGen->getR0Type()->tag;
4018        if (!(tag == TY_INT || tag == TY_CHAR || tag == TY_POINTER)) {
4019            error("++/-- illegal for this type. %d", tag);
4020        }
4021        if (isPost) {
4022            pGen->over();
4023            pGen->pushR0();
4024            pGen->li(lit);
4025            pGen->genOp(OP_PLUS);
4026            pGen->storeR0ToTOS();
4027            pGen->popR0();
4028        } else {
4029            pGen->pushR0();
4030            pGen->li(lit);
4031            pGen->genOp(OP_PLUS);
4032            pGen->over();
4033            pGen->storeR0ToTOS();
4034            pGen->popR0();
4035        }
4036    }
4037
4038    /* Recursive descent parser for binary operations.
4039     */
4040    void binaryOp(int level) {
4041        intptr_t t, a;
4042        t = 0;
4043        if (level-- == 1)
4044            unaryOrAssignment();
4045        else {
4046            binaryOp(level);
4047            a = 0;
4048            while (level == tokl) {
4049                t = tokc;
4050                next();
4051                pGen->forceR0RVal();
4052                if (level > 8) {
4053                    a = pGen->gtst(t == OP_LOGICAL_OR, a); /* && and || output code generation */
4054                    binaryOp(level);
4055                } else {
4056                    pGen->pushR0();
4057                    binaryOp(level);
4058                    // Check for syntax error.
4059                    if (pGen->getR0Type() == NULL) {
4060                        // We failed to parse a right-hand argument.
4061                        // Push a dummy value so we don't fail
4062                        pGen->li(0);
4063                    }
4064                    pGen->forceR0RVal();
4065                    if ((level == 4) | (level == 5)) {
4066                        pGen->gcmp(t);
4067                    } else {
4068                        pGen->genOp(t);
4069                    }
4070                }
4071            }
4072            /* && and || output code generation */
4073            if (a && level > 8) {
4074                pGen->forceR0RVal();
4075                a = pGen->gtst(t == OP_LOGICAL_OR, a);
4076                pGen->li(t != OP_LOGICAL_OR);
4077                int b = pGen->gjmp(0);
4078                pGen->gsym(a);
4079                pGen->li(t == OP_LOGICAL_OR);
4080                pGen->gsym(b);
4081            }
4082        }
4083    }
4084
4085    void commaExpr() {
4086        for(;;) {
4087            expr();
4088            if (!accept(',')) {
4089                break;
4090            }
4091        }
4092    }
4093
4094    void expr() {
4095        binaryOp(11);
4096    }
4097
4098    int test_expr() {
4099        commaExpr();
4100        pGen->forceR0RVal();
4101        return pGen->gtst(0, 0);
4102    }
4103
4104    void block(intptr_t l, bool outermostFunctionBlock) {
4105        intptr_t a, n, t;
4106
4107        Type* pBaseType;
4108        if ((pBaseType = acceptPrimitiveType())) {
4109            /* declarations */
4110            localDeclarations(pBaseType);
4111        } else if (tok == TOK_IF) {
4112            next();
4113            skip('(');
4114            a = test_expr();
4115            skip(')');
4116            block(l, false);
4117            if (tok == TOK_ELSE) {
4118                next();
4119                n = pGen->gjmp(0); /* jmp */
4120                pGen->gsym(a);
4121                block(l, false);
4122                pGen->gsym(n); /* patch else jmp */
4123            } else {
4124                pGen->gsym(a); /* patch if test */
4125            }
4126        } else if ((tok == TOK_WHILE) | (tok == TOK_FOR)) {
4127            t = tok;
4128            next();
4129            skip('(');
4130            if (t == TOK_WHILE) {
4131                n = codeBuf.getPC(); // top of loop, target of "next" iteration
4132                a = test_expr();
4133            } else {
4134                if (tok != ';')
4135                    commaExpr();
4136                skip(';');
4137                n = codeBuf.getPC();
4138                a = 0;
4139                if (tok != ';')
4140                    a = test_expr();
4141                skip(';');
4142                if (tok != ')') {
4143                    t = pGen->gjmp(0);
4144                    commaExpr();
4145                    pGen->gjmp(n - codeBuf.getPC() - pGen->jumpOffset());
4146                    pGen->gsym(t);
4147                    n = t + 4;
4148                }
4149            }
4150            skip(')');
4151            block((intptr_t) &a, false);
4152            pGen->gjmp(n - codeBuf.getPC() - pGen->jumpOffset()); /* jmp */
4153            pGen->gsym(a);
4154        } else if (tok == '{') {
4155            if (! outermostFunctionBlock) {
4156                mLocals.pushLevel();
4157            }
4158            next();
4159            while (tok != '}' && tok != EOF)
4160                block(l, false);
4161            skip('}');
4162            if (! outermostFunctionBlock) {
4163                mLocals.popLevel();
4164            }
4165        } else {
4166            if (accept(TOK_RETURN)) {
4167                if (tok != ';') {
4168                    commaExpr();
4169                    pGen->forceR0RVal();
4170                    if (pReturnType->tag == TY_VOID) {
4171                        error("Must not return a value from a void function");
4172                    } else {
4173                        pGen->convertR0(pReturnType);
4174                    }
4175                } else {
4176                    if (pReturnType->tag != TY_VOID) {
4177                        error("Must specify a value here");
4178                    }
4179                }
4180                rsym = pGen->gjmp(rsym); /* jmp */
4181            } else if (accept(TOK_BREAK)) {
4182                *(int *) l = pGen->gjmp(*(int *) l);
4183            } else if (tok != ';')
4184                commaExpr();
4185            skip(';');
4186        }
4187    }
4188
4189    static bool typeEqual(Type* a, Type* b) {
4190        if (a == b) {
4191            return true;
4192        }
4193        if (a == NULL || b == NULL) {
4194            return false;
4195        }
4196        TypeTag at = a->tag;
4197        if (at != b->tag) {
4198            return false;
4199        }
4200        if (at == TY_POINTER) {
4201            return typeEqual(a->pHead, b->pHead);
4202        } else if (at == TY_FUNC || at == TY_PARAM) {
4203            return typeEqual(a->pHead, b->pHead)
4204                && typeEqual(a->pTail, b->pTail);
4205        }
4206        return true;
4207    }
4208
4209    Type* createType(TypeTag tag, Type* pHead, Type* pTail) {
4210        assert(tag >= TY_INT && tag <= TY_PARAM);
4211        Type* pType = (Type*) mpCurrentArena->alloc(sizeof(Type));
4212        memset(pType, 0, sizeof(*pType));
4213        pType->tag = tag;
4214        pType->pHead = pHead;
4215        pType->pTail = pTail;
4216        return pType;
4217    }
4218
4219    Type* createPtrType(Type* pType) {
4220        return createType(TY_POINTER, pType, NULL);
4221    }
4222
4223    /**
4224     * Try to print a type in declaration order
4225     */
4226    void decodeType(String& buffer, Type* pType) {
4227        buffer.clear();
4228        if (pType == NULL) {
4229            buffer.appendCStr("null");
4230            return;
4231        }
4232        decodeTypeImp(buffer, pType);
4233    }
4234
4235    void decodeTypeImp(String& buffer, Type* pType) {
4236        decodeTypeImpPrefix(buffer, pType);
4237
4238        String temp;
4239        if (pType->id != 0) {
4240            decodeToken(temp, pType->id, false);
4241            buffer.append(temp);
4242        }
4243
4244        decodeTypeImpPostfix(buffer, pType);
4245    }
4246
4247    void decodeTypeImpPrefix(String& buffer, Type* pType) {
4248        TypeTag tag = pType->tag;
4249
4250        if (tag >= TY_INT && tag <= TY_DOUBLE) {
4251            switch (tag) {
4252                case TY_INT:
4253                    buffer.appendCStr("int");
4254                    break;
4255                case TY_CHAR:
4256                    buffer.appendCStr("char");
4257                    break;
4258                case TY_VOID:
4259                    buffer.appendCStr("void");
4260                    break;
4261                case TY_FLOAT:
4262                    buffer.appendCStr("float");
4263                    break;
4264                case TY_DOUBLE:
4265                    buffer.appendCStr("double");
4266                    break;
4267                default:
4268                    break;
4269            }
4270            buffer.append(' ');
4271        }
4272
4273        switch (tag) {
4274            case TY_INT:
4275                break;
4276            case TY_CHAR:
4277                break;
4278            case TY_VOID:
4279                 break;
4280            case TY_FLOAT:
4281                 break;
4282            case TY_DOUBLE:
4283                break;
4284            case TY_POINTER:
4285                decodeTypeImpPrefix(buffer, pType->pHead);
4286                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
4287                    buffer.append('(');
4288                }
4289                buffer.append('*');
4290                break;
4291            case TY_FUNC:
4292                decodeTypeImp(buffer, pType->pHead);
4293                break;
4294            case TY_PARAM:
4295                decodeTypeImp(buffer, pType->pHead);
4296                break;
4297            default:
4298                String temp;
4299                temp.printf("Unknown tag %d", pType->tag);
4300                buffer.append(temp);
4301                break;
4302        }
4303    }
4304
4305    void decodeTypeImpPostfix(String& buffer, Type* pType) {
4306        TypeTag tag = pType->tag;
4307
4308        switch(tag) {
4309            case TY_POINTER:
4310                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
4311                    buffer.append(')');
4312                }
4313                decodeTypeImpPostfix(buffer, pType->pHead);
4314                break;
4315            case TY_FUNC:
4316                buffer.append('(');
4317                for(Type* pArg = pType->pTail; pArg; pArg = pArg->pTail) {
4318                    decodeTypeImp(buffer, pArg);
4319                    if (pArg->pTail) {
4320                        buffer.appendCStr(", ");
4321                    }
4322                }
4323                buffer.append(')');
4324                break;
4325            default:
4326                break;
4327        }
4328    }
4329
4330    void printType(Type* pType) {
4331        String buffer;
4332        decodeType(buffer, pType);
4333        fprintf(stderr, "%s\n", buffer.getUnwrapped());
4334    }
4335
4336    Type* acceptPrimitiveType() {
4337        Type* pType;
4338        if (tok == TOK_INT) {
4339            pType = mkpInt;
4340        } else if (tok == TOK_CHAR) {
4341            pType = mkpChar;
4342        } else if (tok == TOK_VOID) {
4343            pType = mkpVoid;
4344        } else if (tok == TOK_FLOAT) {
4345            pType = mkpFloat;
4346        } else if (tok == TOK_DOUBLE) {
4347            pType = mkpDouble;
4348        } else {
4349            return NULL;
4350        }
4351        next();
4352        return pType;
4353    }
4354
4355    Type* acceptDeclaration(Type* pType, bool nameAllowed, bool nameRequired) {
4356        tokenid_t declName = 0;
4357        bool reportFailure = false;
4358        pType = acceptDecl2(pType, declName, nameAllowed,
4359                                  nameRequired, reportFailure);
4360        if (declName) {
4361            // Clone the parent type so we can set a unique ID
4362            pType = createType(pType->tag, pType->pHead, pType->pTail);
4363
4364            pType->id = declName;
4365        }
4366        // fprintf(stderr, "Parsed a declaration:       ");
4367        // printType(pType);
4368        if (reportFailure) {
4369            return NULL;
4370        }
4371        return pType;
4372    }
4373
4374    Type* expectDeclaration(Type* pBaseType) {
4375        Type* pType = acceptDeclaration(pBaseType, true, true);
4376        if (! pType) {
4377            error("Expected a declaration");
4378        }
4379        return pType;
4380    }
4381
4382    /* Used for accepting types that appear in casts */
4383    Type* acceptCastTypeDeclaration() {
4384        Type* pType = acceptPrimitiveType();
4385        if (pType) {
4386            pType = acceptDeclaration(pType, false, false);
4387        }
4388        return pType;
4389    }
4390
4391    Type* expectCastTypeDeclaration() {
4392        Type* pType = acceptCastTypeDeclaration();
4393        if (! pType) {
4394            error("Expected a declaration");
4395        }
4396        return pType;
4397    }
4398
4399    Type* acceptDecl2(Type* pType, tokenid_t& declName,
4400                      bool nameAllowed, bool nameRequired,
4401                      bool& reportFailure) {
4402        int ptrCounter = 0;
4403        while (accept('*')) {
4404            ptrCounter++;
4405        }
4406        pType = acceptDecl3(pType, declName, nameAllowed, nameRequired,
4407                            reportFailure);
4408        while (ptrCounter-- > 0) {
4409            pType = createType(TY_POINTER, pType, NULL);
4410        }
4411        return pType;
4412    }
4413
4414    Type* acceptDecl3(Type* pType, tokenid_t& declName,
4415                      bool nameAllowed, bool nameRequired,
4416                      bool& reportFailure) {
4417        // direct-dcl :
4418        //   name
4419        //  (dcl)
4420        //   direct-dcl()
4421        //   direct-dcl[]
4422        Type* pNewHead = NULL;
4423        if (accept('(')) {
4424            pNewHead = acceptDecl2(pNewHead, declName, nameAllowed,
4425                                nameRequired, reportFailure);
4426            skip(')');
4427        } else if ((declName = acceptSymbol()) != 0) {
4428            if (nameAllowed == false && declName) {
4429                error("Symbol %s not allowed here", nameof(declName));
4430                reportFailure = true;
4431            }
4432        } else if (nameRequired && ! declName) {
4433            String temp;
4434            decodeToken(temp, tok, true);
4435            error("Expected name. Got %s", temp.getUnwrapped());
4436            reportFailure = true;
4437        }
4438        while (accept('(')) {
4439            // Function declaration
4440            Type* pTail = acceptArgs(nameAllowed);
4441            pType = createType(TY_FUNC, pType, pTail);
4442            skip(')');
4443        }
4444
4445        if (pNewHead) {
4446            Type* pA = pNewHead;
4447            while (pA->pHead) {
4448                pA = pA->pHead;
4449            }
4450            pA->pHead = pType;
4451            pType = pNewHead;
4452        }
4453        return pType;
4454    }
4455
4456    Type* acceptArgs(bool nameAllowed) {
4457        Type* pHead = NULL;
4458        Type* pTail = NULL;
4459        for(;;) {
4460            Type* pBaseArg = acceptPrimitiveType();
4461            if (pBaseArg) {
4462                Type* pArg = acceptDeclaration(pBaseArg, nameAllowed, false);
4463                if (pArg) {
4464                    Type* pParam = createType(TY_PARAM, pArg, NULL);
4465                    if (!pHead) {
4466                        pHead = pParam;
4467                        pTail = pParam;
4468                    } else {
4469                        pTail->pTail = pParam;
4470                        pTail = pParam;
4471                    }
4472                }
4473            }
4474            if (! accept(',')) {
4475                break;
4476            }
4477        }
4478        return pHead;
4479    }
4480
4481    Type* expectPrimitiveType() {
4482        Type* pType = acceptPrimitiveType();
4483        if (!pType) {
4484            String buf;
4485            decodeToken(buf, tok, true);
4486            error("Expected a type, got %s", buf.getUnwrapped());
4487        }
4488        return pType;
4489    }
4490
4491    void checkLVal() {
4492        if (pGen->getR0ExpressionType() != ET_LVALUE) {
4493            error("Expected an lval");
4494        }
4495    }
4496
4497    void addGlobalSymbol(Type* pDecl) {
4498        tokenid_t t = pDecl->id;
4499        VariableInfo* pVI = VI(t);
4500        if(pVI && pVI->pAddress) {
4501            reportDuplicate(t);
4502        }
4503        mGlobals.add(pDecl);
4504    }
4505
4506    void reportDuplicate(tokenid_t t) {
4507        error("Duplicate definition of %s", nameof(t));
4508    }
4509
4510    void addLocalSymbol(Type* pDecl) {
4511        tokenid_t t = pDecl->id;
4512        if (mLocals.isDefinedAtCurrentLevel(t)) {
4513            reportDuplicate(t);
4514        }
4515        mLocals.add(pDecl);
4516    }
4517
4518    void localDeclarations(Type* pBaseType) {
4519        intptr_t a;
4520
4521        while (pBaseType) {
4522            while (tok != ';' && tok != EOF) {
4523                Type* pDecl = expectDeclaration(pBaseType);
4524                if (!pDecl) {
4525                    break;
4526                }
4527                int variableAddress = 0;
4528                addLocalSymbol(pDecl);
4529                size_t alignment = pGen->stackAlignmentOf(pDecl);
4530                size_t alignmentMask = ~ (alignment - 1);
4531                size_t sizeOf = pGen->sizeOf(pDecl);
4532                loc = (loc + alignment - 1) & alignmentMask;
4533                size_t alignedSize = (sizeOf + alignment - 1) & alignmentMask;
4534                loc = loc + alignedSize;
4535                variableAddress = -loc;
4536                VI(pDecl->id)->pAddress = (void*) variableAddress;
4537                if (accept('=')) {
4538                    /* assignment */
4539                    pGen->leaR0(variableAddress, createPtrType(pDecl), ET_LVALUE);
4540                    pGen->pushR0();
4541                    expr();
4542                    pGen->forceR0RVal();
4543                    pGen->storeR0ToTOS();
4544                }
4545                if (tok == ',')
4546                    next();
4547            }
4548            skip(';');
4549            pBaseType = acceptPrimitiveType();
4550        }
4551    }
4552
4553    bool checkSymbol() {
4554        return checkSymbol(tok);
4555    }
4556
4557    void decodeToken(String& buffer, tokenid_t token, bool quote) {
4558        if (token == EOF ) {
4559            buffer.printf("EOF");
4560        } else if (token == TOK_NUM) {
4561            buffer.printf("numeric constant");
4562        } else if (token >= 0 && token < 256) {
4563            if (token < 32) {
4564                buffer.printf("'\\x%02x'", token);
4565            } else {
4566                buffer.printf("'%c'", token);
4567            }
4568        } else {
4569            if (quote) {
4570                if (token >= TOK_KEYWORD && token < TOK_SYMBOL) {
4571                    buffer.printf("keyword \"%s\"", nameof(token));
4572                } else {
4573                    buffer.printf("symbol \"%s\"", nameof(token));
4574                }
4575            } else {
4576                buffer.printf("%s", nameof(token));
4577            }
4578        }
4579    }
4580
4581    bool checkSymbol(tokenid_t token) {
4582        bool result = token >= TOK_SYMBOL;
4583        if (!result) {
4584            String temp;
4585            decodeToken(temp, token, true);
4586            error("Expected symbol. Got %s", temp.getUnwrapped());
4587        }
4588        return result;
4589    }
4590
4591    tokenid_t acceptSymbol() {
4592        tokenid_t result = 0;
4593        if (tok >= TOK_SYMBOL) {
4594            result = tok;
4595            next();
4596        }
4597        return result;
4598    }
4599
4600    void globalDeclarations() {
4601        while (tok != EOF) {
4602            Type* pBaseType = expectPrimitiveType();
4603            if (!pBaseType) {
4604                break;
4605            }
4606            Type* pDecl = expectDeclaration(pBaseType);
4607            if (!pDecl) {
4608                break;
4609            }
4610            if (! isDefined(pDecl->id)) {
4611                addGlobalSymbol(pDecl);
4612            }
4613            VariableInfo* name = VI(pDecl->id);
4614            if (name && name->pAddress) {
4615                error("Already defined global %s", nameof(pDecl->id));
4616            }
4617            if (pDecl->tag < TY_FUNC) {
4618                // it's a variable declaration
4619                for(;;) {
4620                    if (name && !name->pAddress) {
4621                        name->pAddress = (int*) allocGlobalSpace(
4622                                                   pGen->alignmentOf(name->pType),
4623                                                   pGen->sizeOf(name->pType));
4624                    }
4625                    if (accept('=')) {
4626                        if (tok == TOK_NUM) {
4627                            if (name) {
4628                                * (int*) name->pAddress = tokc;
4629                            }
4630                            next();
4631                        } else {
4632                            error("Expected an integer constant");
4633                        }
4634                    }
4635                    if (!accept(',')) {
4636                        break;
4637                    }
4638                    pDecl = expectDeclaration(pBaseType);
4639                    if (!pDecl) {
4640                        break;
4641                    }
4642                    if (! isDefined(pDecl->id)) {
4643                        addGlobalSymbol(pDecl);
4644                    }
4645                    name = VI(pDecl->id);
4646                }
4647                skip(';');
4648            } else {
4649                // Function declaration
4650                if (accept(';')) {
4651                    // forward declaration.
4652                } else if (tok != '{') {
4653                    error("expected '{'");
4654                } else {
4655                    mpCurrentArena = &mLocalArena;
4656                    if (name) {
4657                        /* patch forward references */
4658                        pGen->resolveForward((int) name->pForward);
4659                        /* put function address */
4660                        name->pAddress = (void*) codeBuf.getPC();
4661                    }
4662                    // Calculate stack offsets for parameters
4663                    mLocals.pushLevel();
4664                    intptr_t a = 8;
4665                    int argCount = 0;
4666                    for (Type* pP = pDecl->pTail; pP; pP = pP->pTail) {
4667                        Type* pArg = pP->pHead;
4668                        addLocalSymbol(pArg);
4669                        /* read param name and compute offset */
4670                        size_t alignment = pGen->stackAlignmentOf(pArg);
4671                        a = (a + alignment - 1) & ~ (alignment-1);
4672                        VI(pArg->id)->pAddress = (void*) a;
4673                        a = a + pGen->stackSizeOf(pArg);
4674                        argCount++;
4675                    }
4676                    rsym = loc = 0;
4677                    pReturnType = pDecl->pHead;
4678                    a = pGen->functionEntry(pDecl);
4679                    block(0, true);
4680                    pGen->gsym(rsym);
4681                    pGen->functionExit(pDecl, a, loc);
4682                    mLocals.popLevel();
4683                    mpCurrentArena = &mGlobalArena;
4684                }
4685            }
4686        }
4687    }
4688
4689    char* allocGlobalSpace(size_t alignment, size_t bytes) {
4690        size_t base = (((size_t) glo) + alignment - 1) & ~(alignment-1);
4691        size_t end = base + bytes;
4692        if ((end - (size_t) pGlobalBase) > (size_t) ALLOC_SIZE) {
4693            error("Global space exhausted");
4694            return NULL;
4695        }
4696        char* result = (char*) base;
4697        glo = (char*) end;
4698        return result;
4699    }
4700
4701    void cleanup() {
4702        if (pGlobalBase != 0) {
4703            free(pGlobalBase);
4704            pGlobalBase = 0;
4705        }
4706        if (pGen) {
4707            delete pGen;
4708            pGen = 0;
4709        }
4710        if (file) {
4711            delete file;
4712            file = 0;
4713        }
4714    }
4715
4716    // One-time initialization, when class is constructed.
4717    void init() {
4718        mpSymbolLookupFn = 0;
4719        mpSymbolLookupContext = 0;
4720    }
4721
4722    void clear() {
4723        tok = 0;
4724        tokc = 0;
4725        tokl = 0;
4726        ch = 0;
4727        rsym = 0;
4728        loc = 0;
4729        glo = 0;
4730        dptr = 0;
4731        dch = 0;
4732        file = 0;
4733        pGlobalBase = 0;
4734        pGen = 0;
4735        mPragmaStringCount = 0;
4736        mCompileResult = 0;
4737        mLineNumber = 1;
4738        mbBumpLine = false;
4739    }
4740
4741    void setArchitecture(const char* architecture) {
4742        delete pGen;
4743        pGen = 0;
4744
4745        if (architecture != NULL) {
4746#ifdef PROVIDE_ARM_CODEGEN
4747            if (! pGen && strcmp(architecture, "arm") == 0) {
4748                pGen = new ARMCodeGenerator();
4749            }
4750#endif
4751#ifdef PROVIDE_X86_CODEGEN
4752            if (! pGen && strcmp(architecture, "x86") == 0) {
4753                pGen = new X86CodeGenerator();
4754            }
4755#endif
4756            if (!pGen ) {
4757                error("Unknown architecture %s\n", architecture);
4758            }
4759        }
4760
4761        if (pGen == NULL) {
4762#if defined(DEFAULT_ARM_CODEGEN)
4763            pGen = new ARMCodeGenerator();
4764#elif defined(DEFAULT_X86_CODEGEN)
4765            pGen = new X86CodeGenerator();
4766#endif
4767        }
4768        if (pGen == NULL) {
4769            error("No code generator defined.");
4770        } else {
4771            pGen->setErrorSink(this);
4772            pGen->setTypes(mkpInt);
4773        }
4774    }
4775
4776public:
4777    struct args {
4778        args() {
4779            architecture = 0;
4780        }
4781        const char* architecture;
4782    };
4783
4784    Compiler() {
4785        init();
4786        clear();
4787    }
4788
4789    ~Compiler() {
4790        cleanup();
4791    }
4792
4793    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
4794        mpSymbolLookupFn = pFn;
4795        mpSymbolLookupContext = pContext;
4796    }
4797
4798    int compile(const char* text, size_t textLength) {
4799        int result;
4800
4801        mpCurrentArena = &mGlobalArena;
4802        createPrimitiveTypes();
4803        cleanup();
4804        clear();
4805        mTokenTable.setArena(&mGlobalArena);
4806        mGlobals.setArena(&mGlobalArena);
4807        mGlobals.setTokenTable(&mTokenTable);
4808        mLocals.setArena(&mLocalArena);
4809        mLocals.setTokenTable(&mTokenTable);
4810
4811        internKeywords();
4812        codeBuf.init(ALLOC_SIZE);
4813        setArchitecture(NULL);
4814        if (!pGen) {
4815            return -1;
4816        }
4817#ifdef PROVIDE_TRACE_CODEGEN
4818            pGen = new TraceCodeGenerator(pGen);
4819#endif
4820            pGen->setErrorSink(this);
4821        pGen->init(&codeBuf);
4822        file = new TextInputStream(text, textLength);
4823        pGlobalBase = (char*) calloc(1, ALLOC_SIZE);
4824        glo = pGlobalBase;
4825        inp();
4826        next();
4827        globalDeclarations();
4828        checkForUndefinedForwardReferences();
4829        result = pGen->finishCompile();
4830        if (result == 0) {
4831            if (mErrorBuf.len()) {
4832                result = -2;
4833            }
4834        }
4835        mCompileResult = result;
4836        return result;
4837    }
4838
4839    void createPrimitiveTypes() {
4840        mkpInt = createType(TY_INT, NULL, NULL);
4841        mkpChar = createType(TY_CHAR, NULL, NULL);
4842        mkpVoid = createType(TY_VOID, NULL, NULL);
4843        mkpFloat = createType(TY_FLOAT, NULL, NULL);
4844        mkpDouble = createType(TY_DOUBLE, NULL, NULL);
4845        mkpIntFn =  createType(TY_FUNC, mkpInt, NULL);
4846        mkpIntPtr = createPtrType(mkpInt);
4847        mkpCharPtr = createPtrType(mkpChar);
4848        mkpFloatPtr = createPtrType(mkpFloat);
4849        mkpDoublePtr = createPtrType(mkpDouble);
4850        mkpPtrIntFn = createPtrType(mkpIntFn);
4851    }
4852
4853    void checkForUndefinedForwardReferences() {
4854        mGlobals.forEach(static_ufrcFn, this);
4855    }
4856
4857    static bool static_ufrcFn(VariableInfo* value, void* context) {
4858        Compiler* pCompiler = (Compiler*) context;
4859        return pCompiler->undefinedForwardReferenceCheck(value);
4860    }
4861
4862    bool undefinedForwardReferenceCheck(VariableInfo* value) {
4863        if (!value->pAddress && value->pForward) {
4864            error("Undefined forward reference: %s",
4865                  mTokenTable[value->tok].pText);
4866        }
4867        return true;
4868    }
4869
4870    int dump(FILE* out) {
4871        fwrite(codeBuf.getBase(), 1, codeBuf.getSize(), out);
4872        return 0;
4873    }
4874
4875    int disassemble(FILE* out) {
4876        return pGen->disassemble(out);
4877    }
4878
4879    /* Look through the symbol table to find a symbol.
4880     * If found, return its value.
4881     */
4882    void* lookup(const char* name) {
4883        if (mCompileResult == 0) {
4884            tokenid_t tok = mTokenTable.intern(name, strlen(name));
4885            VariableInfo* pVariableInfo = VI(tok);
4886            if (pVariableInfo) {
4887                return pVariableInfo->pAddress;
4888            }
4889        }
4890        return NULL;
4891    }
4892
4893    void getPragmas(ACCsizei* actualStringCount,
4894                    ACCsizei maxStringCount, ACCchar** strings) {
4895        int stringCount = mPragmaStringCount;
4896        if (actualStringCount) {
4897            *actualStringCount = stringCount;
4898        }
4899        if (stringCount > maxStringCount) {
4900            stringCount = maxStringCount;
4901        }
4902        if (strings) {
4903            char* pPragmas = mPragmas.getUnwrapped();
4904            while (stringCount-- > 0) {
4905                *strings++ = pPragmas;
4906                pPragmas += strlen(pPragmas) + 1;
4907            }
4908        }
4909    }
4910
4911    char* getErrorMessage() {
4912        return mErrorBuf.getUnwrapped();
4913    }
4914
4915};
4916
4917const char* Compiler::operatorChars =
4918    "++--*@/@%@+@-@<<>><=>=<@>@==!=&&||&@^@|@~@!@";
4919
4920const char Compiler::operatorLevel[] =
4921    {11, 11, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4,
4922            5, 5, /* ==, != */
4923            9, 10, /* &&, || */
4924            6, 7, 8, /* & ^ | */
4925            2, 2 /* ~ ! */
4926            };
4927
4928#ifdef PROVIDE_ARM_CODEGEN
4929FILE* Compiler::ARMCodeGenerator::disasmOut;
4930#endif
4931
4932#ifdef PROVIDE_X86_CODEGEN
4933const int Compiler::X86CodeGenerator::operatorHelper[] = {
4934        0x1,     // ++
4935        0xff,    // --
4936        0xc1af0f, // *
4937        0xf9f79991, // /
4938        0xf9f79991, // % (With manual assist to swap results)
4939        0xc801, // +
4940        0xd8f7c829, // -
4941        0xe0d391, // <<
4942        0xf8d391, // >>
4943        0xe, // <=
4944        0xd, // >=
4945        0xc, // <
4946        0xf, // >
4947        0x4, // ==
4948        0x5, // !=
4949        0x0, // &&
4950        0x1, // ||
4951        0xc821, // &
4952        0xc831, // ^
4953        0xc809, // |
4954        0xd0f7, // ~
4955        0x4     // !
4956};
4957#endif
4958
4959struct ACCscript {
4960    ACCscript() {
4961        text = 0;
4962        textLength = 0;
4963        accError = ACC_NO_ERROR;
4964    }
4965
4966    ~ACCscript() {
4967        delete text;
4968    }
4969
4970    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
4971        compiler.registerSymbolCallback(pFn, pContext);
4972    }
4973
4974    void setError(ACCenum error) {
4975        if (accError == ACC_NO_ERROR && error != ACC_NO_ERROR) {
4976            accError = error;
4977        }
4978    }
4979
4980    ACCenum getError() {
4981        ACCenum result = accError;
4982        accError = ACC_NO_ERROR;
4983        return result;
4984    }
4985
4986    Compiler compiler;
4987    char* text;
4988    int textLength;
4989    ACCenum accError;
4990};
4991
4992
4993extern "C"
4994ACCscript* accCreateScript() {
4995    return new ACCscript();
4996}
4997
4998extern "C"
4999ACCenum accGetError( ACCscript* script ) {
5000    return script->getError();
5001}
5002
5003extern "C"
5004void accDeleteScript(ACCscript* script) {
5005    delete script;
5006}
5007
5008extern "C"
5009void accRegisterSymbolCallback(ACCscript* script, ACCSymbolLookupFn pFn,
5010                               ACCvoid* pContext) {
5011    script->registerSymbolCallback(pFn, pContext);
5012}
5013
5014extern "C"
5015void accScriptSource(ACCscript* script,
5016    ACCsizei count,
5017    const ACCchar ** string,
5018    const ACCint * length) {
5019    int totalLength = 0;
5020    for(int i = 0; i < count; i++) {
5021        int len = -1;
5022        const ACCchar* s = string[i];
5023        if (length) {
5024            len = length[i];
5025        }
5026        if (len < 0) {
5027            len = strlen(s);
5028        }
5029        totalLength += len;
5030    }
5031    delete script->text;
5032    char* text = new char[totalLength + 1];
5033    script->text = text;
5034    script->textLength = totalLength;
5035    char* dest = text;
5036    for(int i = 0; i < count; i++) {
5037        int len = -1;
5038        const ACCchar* s = string[i];
5039        if (length) {
5040            len = length[i];
5041        }
5042        if (len < 0) {
5043            len = strlen(s);
5044        }
5045        memcpy(dest, s, len);
5046        dest += len;
5047    }
5048    text[totalLength] = '\0';
5049}
5050
5051extern "C"
5052void accCompileScript(ACCscript* script) {
5053    int result = script->compiler.compile(script->text, script->textLength);
5054    if (result) {
5055        script->setError(ACC_INVALID_OPERATION);
5056    }
5057}
5058
5059extern "C"
5060void accGetScriptiv(ACCscript* script,
5061    ACCenum pname,
5062    ACCint * params) {
5063    switch (pname) {
5064        case ACC_INFO_LOG_LENGTH:
5065            *params = 0;
5066            break;
5067    }
5068}
5069
5070extern "C"
5071void accGetScriptInfoLog(ACCscript* script,
5072    ACCsizei maxLength,
5073    ACCsizei * length,
5074    ACCchar * infoLog) {
5075    char* message = script->compiler.getErrorMessage();
5076    int messageLength = strlen(message) + 1;
5077    if (length) {
5078        *length = messageLength;
5079    }
5080    if (infoLog && maxLength > 0) {
5081        int trimmedLength = maxLength < messageLength ?
5082                maxLength : messageLength;
5083        memcpy(infoLog, message, trimmedLength);
5084        infoLog[trimmedLength] = 0;
5085    }
5086}
5087
5088extern "C"
5089void accGetScriptLabel(ACCscript* script, const ACCchar * name,
5090                       ACCvoid ** address) {
5091    void* value = script->compiler.lookup(name);
5092    if (value) {
5093        *address = value;
5094    } else {
5095        script->setError(ACC_INVALID_VALUE);
5096    }
5097}
5098
5099extern "C"
5100void accGetPragmas(ACCscript* script, ACCsizei* actualStringCount,
5101                   ACCsizei maxStringCount, ACCchar** strings){
5102    script->compiler.getPragmas(actualStringCount, maxStringCount, strings);
5103}
5104
5105extern "C"
5106void accDisassemble(ACCscript* script) {
5107    script->compiler.disassemble(stderr);
5108}
5109
5110
5111} // namespace acc
5112
5113