acc.cpp revision 96138992ac98f8962dc2345d9ba3e99006af80b2 
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                doPointer();
3883            } else if (t == '&') {
3884                VariableInfo* pVI = VI(tok);
3885                pGen->leaR0((int) pVI->pAddress, createPtrType(pVI->pType),
3886                        ET_RVALUE);
3887                next();
3888            } else if (t == EOF ) {
3889                error("Unexpected EOF.");
3890            } else if (t == ';') {
3891                error("Unexpected ';'");
3892            } else if (!checkSymbol(t)) {
3893                // Don't have to do anything special here, the error
3894                // message was printed by checkSymbol() above.
3895            } else {
3896                if (!isDefined(t)) {
3897                    mGlobals.add(t);
3898                    // printf("Adding new global function %s\n", nameof(t));
3899                }
3900                VariableInfo* pVI = VI(t);
3901                int n = (intptr_t) pVI->pAddress;
3902                /* forward reference: try our lookup function */
3903                if (!n) {
3904                    linkGlobal(t, tok == '(');
3905                    n = (intptr_t) pVI->pAddress;
3906                    if (!n && tok != '(') {
3907                        error("Undeclared variable %s\n", nameof(t));
3908                    }
3909                }
3910                if (tok != '(') {
3911                    /* variable or function name */
3912                    if (!n) {
3913                        linkGlobal(t, false);
3914                        n = (intptr_t) pVI->pAddress;
3915                        if (!n) {
3916                            error("Undeclared variable %s\n", nameof(t));
3917                        }
3918                    }
3919                }
3920                // load a variable
3921                Type* pVal = createPtrType(pVI->pType);
3922                if (n) {
3923                    ExpressionType et = ET_LVALUE;
3924                    if (pVal->pHead->tag == TY_FUNC) {
3925                        et = ET_RVALUE;
3926                    }
3927                    pGen->leaR0(n, pVal, et);
3928                } else {
3929                    pVI->pForward = (void*) pGen->leaForward(
3930                            (int) pVI->pForward, pVal);
3931                }
3932            }
3933        }
3934
3935        /* Now handle postfix operators */
3936        for(;;) {
3937            if (tokl == 11) {
3938                // post inc / post dec
3939                doIncDec(tokc == OP_INCREMENT, true);
3940                next();
3941            } else if (accept('[')) {
3942                // Array reference
3943                pGen->forceR0RVal();
3944                pGen->pushR0();
3945                commaExpr();
3946                pGen->forceR0RVal();
3947                pGen->genOp(OP_PLUS);
3948                doPointer();
3949                skip(']');
3950            } else  if (accept('(')) {
3951                /* function call */
3952                Type* pDecl = NULL;
3953                VariableInfo* pVI = NULL;
3954                Type* pFn = pGen->getR0Type();
3955                assert(pFn->tag == TY_POINTER);
3956                assert(pFn->pHead->tag == TY_FUNC);
3957                pDecl = pFn->pHead;
3958                pGen->pushR0();
3959                Type* pArgList = pDecl->pTail;
3960                bool varArgs = pArgList == NULL;
3961                /* push args and invert order */
3962                a = pGen->beginFunctionCallArguments();
3963                int l = 0;
3964                int argCount = 0;
3965                while (tok != ')' && tok != EOF) {
3966                    if (! varArgs && !pArgList) {
3967                        error("Unexpected argument.");
3968                    }
3969                    expr();
3970                    pGen->forceR0RVal();
3971                    Type* pTargetType;
3972                    if (pArgList) {
3973                        pTargetType = pArgList->pHead;
3974                        pArgList = pArgList->pTail;
3975                    } else {
3976                        // This is a ... function, just pass arguments in their
3977                        // natural type.
3978                        pTargetType = pGen->getR0Type();
3979                        if (pTargetType->tag == TY_FLOAT) {
3980                            pTargetType = mkpDouble;
3981                        }
3982                    }
3983                    if (pTargetType->tag == TY_VOID) {
3984                        error("Can't pass void value for argument %d",
3985                              argCount + 1);
3986                    } else {
3987                        l += pGen->storeR0ToArg(l, pTargetType);
3988                    }
3989                    if (accept(',')) {
3990                        // fine
3991                    } else if ( tok != ')') {
3992                        error("Expected ',' or ')'");
3993                    }
3994                    argCount += 1;
3995                }
3996                if (! varArgs && pArgList) {
3997                    error("Expected more argument(s). Saw %d", argCount);
3998                }
3999                pGen->endFunctionCallArguments(pDecl, a, l);
4000                skip(')');
4001                pGen->callIndirect(l, pDecl);
4002                pGen->adjustStackAfterCall(pDecl, l, true);
4003            } else {
4004                break;
4005            }
4006        }
4007    }
4008
4009    void doIncDec(int isInc, int isPost) {
4010        // R0 already has the lval
4011        checkLVal();
4012        int lit = isInc ? 1 : -1;
4013        pGen->pushR0();
4014        pGen->loadR0FromR0();
4015        int tag = pGen->getR0Type()->tag;
4016        if (!(tag == TY_INT || tag == TY_CHAR || tag == TY_POINTER)) {
4017            error("++/-- illegal for this type. %d", tag);
4018        }
4019        if (isPost) {
4020            pGen->over();
4021            pGen->pushR0();
4022            pGen->li(lit);
4023            pGen->genOp(OP_PLUS);
4024            pGen->storeR0ToTOS();
4025            pGen->popR0();
4026        } else {
4027            pGen->pushR0();
4028            pGen->li(lit);
4029            pGen->genOp(OP_PLUS);
4030            pGen->over();
4031            pGen->storeR0ToTOS();
4032            pGen->popR0();
4033        }
4034    }
4035
4036    void doPointer() {
4037        pGen->forceR0RVal();
4038        Type* pR0Type = pGen->getR0Type();
4039        if (pR0Type->tag != TY_POINTER) {
4040            error("Expected a pointer type.");
4041        } else {
4042            if (pR0Type->pHead->tag != TY_FUNC) {
4043                pGen->setR0ExpressionType(ET_LVALUE);
4044            }
4045        }
4046    }
4047
4048    /* Recursive descent parser for binary operations.
4049     */
4050    void binaryOp(int level) {
4051        intptr_t t, a;
4052        t = 0;
4053        if (level-- == 1)
4054            unaryOrAssignment();
4055        else {
4056            binaryOp(level);
4057            a = 0;
4058            while (level == tokl) {
4059                t = tokc;
4060                next();
4061                pGen->forceR0RVal();
4062                if (level > 8) {
4063                    a = pGen->gtst(t == OP_LOGICAL_OR, a); /* && and || output code generation */
4064                    binaryOp(level);
4065                } else {
4066                    pGen->pushR0();
4067                    binaryOp(level);
4068                    // Check for syntax error.
4069                    if (pGen->getR0Type() == NULL) {
4070                        // We failed to parse a right-hand argument.
4071                        // Push a dummy value so we don't fail
4072                        pGen->li(0);
4073                    }
4074                    pGen->forceR0RVal();
4075                    if ((level == 4) | (level == 5)) {
4076                        pGen->gcmp(t);
4077                    } else {
4078                        pGen->genOp(t);
4079                    }
4080                }
4081            }
4082            /* && and || output code generation */
4083            if (a && level > 8) {
4084                pGen->forceR0RVal();
4085                a = pGen->gtst(t == OP_LOGICAL_OR, a);
4086                pGen->li(t != OP_LOGICAL_OR);
4087                int b = pGen->gjmp(0);
4088                pGen->gsym(a);
4089                pGen->li(t == OP_LOGICAL_OR);
4090                pGen->gsym(b);
4091            }
4092        }
4093    }
4094
4095    void commaExpr() {
4096        for(;;) {
4097            expr();
4098            if (!accept(',')) {
4099                break;
4100            }
4101        }
4102    }
4103
4104    void expr() {
4105        binaryOp(11);
4106    }
4107
4108    int test_expr() {
4109        commaExpr();
4110        pGen->forceR0RVal();
4111        return pGen->gtst(0, 0);
4112    }
4113
4114    void block(intptr_t l, bool outermostFunctionBlock) {
4115        intptr_t a, n, t;
4116
4117        Type* pBaseType;
4118        if ((pBaseType = acceptPrimitiveType())) {
4119            /* declarations */
4120            localDeclarations(pBaseType);
4121        } else if (tok == TOK_IF) {
4122            next();
4123            skip('(');
4124            a = test_expr();
4125            skip(')');
4126            block(l, false);
4127            if (tok == TOK_ELSE) {
4128                next();
4129                n = pGen->gjmp(0); /* jmp */
4130                pGen->gsym(a);
4131                block(l, false);
4132                pGen->gsym(n); /* patch else jmp */
4133            } else {
4134                pGen->gsym(a); /* patch if test */
4135            }
4136        } else if ((tok == TOK_WHILE) | (tok == TOK_FOR)) {
4137            t = tok;
4138            next();
4139            skip('(');
4140            if (t == TOK_WHILE) {
4141                n = codeBuf.getPC(); // top of loop, target of "next" iteration
4142                a = test_expr();
4143            } else {
4144                if (tok != ';')
4145                    commaExpr();
4146                skip(';');
4147                n = codeBuf.getPC();
4148                a = 0;
4149                if (tok != ';')
4150                    a = test_expr();
4151                skip(';');
4152                if (tok != ')') {
4153                    t = pGen->gjmp(0);
4154                    commaExpr();
4155                    pGen->gjmp(n - codeBuf.getPC() - pGen->jumpOffset());
4156                    pGen->gsym(t);
4157                    n = t + 4;
4158                }
4159            }
4160            skip(')');
4161            block((intptr_t) &a, false);
4162            pGen->gjmp(n - codeBuf.getPC() - pGen->jumpOffset()); /* jmp */
4163            pGen->gsym(a);
4164        } else if (tok == '{') {
4165            if (! outermostFunctionBlock) {
4166                mLocals.pushLevel();
4167            }
4168            next();
4169            while (tok != '}' && tok != EOF)
4170                block(l, false);
4171            skip('}');
4172            if (! outermostFunctionBlock) {
4173                mLocals.popLevel();
4174            }
4175        } else {
4176            if (accept(TOK_RETURN)) {
4177                if (tok != ';') {
4178                    commaExpr();
4179                    pGen->forceR0RVal();
4180                    if (pReturnType->tag == TY_VOID) {
4181                        error("Must not return a value from a void function");
4182                    } else {
4183                        pGen->convertR0(pReturnType);
4184                    }
4185                } else {
4186                    if (pReturnType->tag != TY_VOID) {
4187                        error("Must specify a value here");
4188                    }
4189                }
4190                rsym = pGen->gjmp(rsym); /* jmp */
4191            } else if (accept(TOK_BREAK)) {
4192                *(int *) l = pGen->gjmp(*(int *) l);
4193            } else if (tok != ';')
4194                commaExpr();
4195            skip(';');
4196        }
4197    }
4198
4199    static bool typeEqual(Type* a, Type* b) {
4200        if (a == b) {
4201            return true;
4202        }
4203        if (a == NULL || b == NULL) {
4204            return false;
4205        }
4206        TypeTag at = a->tag;
4207        if (at != b->tag) {
4208            return false;
4209        }
4210        if (at == TY_POINTER) {
4211            return typeEqual(a->pHead, b->pHead);
4212        } else if (at == TY_FUNC || at == TY_PARAM) {
4213            return typeEqual(a->pHead, b->pHead)
4214                && typeEqual(a->pTail, b->pTail);
4215        }
4216        return true;
4217    }
4218
4219    Type* createType(TypeTag tag, Type* pHead, Type* pTail) {
4220        assert(tag >= TY_INT && tag <= TY_PARAM);
4221        Type* pType = (Type*) mpCurrentArena->alloc(sizeof(Type));
4222        memset(pType, 0, sizeof(*pType));
4223        pType->tag = tag;
4224        pType->pHead = pHead;
4225        pType->pTail = pTail;
4226        return pType;
4227    }
4228
4229    Type* createPtrType(Type* pType) {
4230        return createType(TY_POINTER, pType, NULL);
4231    }
4232
4233    /**
4234     * Try to print a type in declaration order
4235     */
4236    void decodeType(String& buffer, Type* pType) {
4237        buffer.clear();
4238        if (pType == NULL) {
4239            buffer.appendCStr("null");
4240            return;
4241        }
4242        decodeTypeImp(buffer, pType);
4243    }
4244
4245    void decodeTypeImp(String& buffer, Type* pType) {
4246        decodeTypeImpPrefix(buffer, pType);
4247
4248        String temp;
4249        if (pType->id != 0) {
4250            decodeToken(temp, pType->id, false);
4251            buffer.append(temp);
4252        }
4253
4254        decodeTypeImpPostfix(buffer, pType);
4255    }
4256
4257    void decodeTypeImpPrefix(String& buffer, Type* pType) {
4258        TypeTag tag = pType->tag;
4259
4260        if (tag >= TY_INT && tag <= TY_DOUBLE) {
4261            switch (tag) {
4262                case TY_INT:
4263                    buffer.appendCStr("int");
4264                    break;
4265                case TY_CHAR:
4266                    buffer.appendCStr("char");
4267                    break;
4268                case TY_VOID:
4269                    buffer.appendCStr("void");
4270                    break;
4271                case TY_FLOAT:
4272                    buffer.appendCStr("float");
4273                    break;
4274                case TY_DOUBLE:
4275                    buffer.appendCStr("double");
4276                    break;
4277                default:
4278                    break;
4279            }
4280            buffer.append(' ');
4281        }
4282
4283        switch (tag) {
4284            case TY_INT:
4285                break;
4286            case TY_CHAR:
4287                break;
4288            case TY_VOID:
4289                 break;
4290            case TY_FLOAT:
4291                 break;
4292            case TY_DOUBLE:
4293                break;
4294            case TY_POINTER:
4295                decodeTypeImpPrefix(buffer, pType->pHead);
4296                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
4297                    buffer.append('(');
4298                }
4299                buffer.append('*');
4300                break;
4301            case TY_FUNC:
4302                decodeTypeImp(buffer, pType->pHead);
4303                break;
4304            case TY_PARAM:
4305                decodeTypeImp(buffer, pType->pHead);
4306                break;
4307            default:
4308                String temp;
4309                temp.printf("Unknown tag %d", pType->tag);
4310                buffer.append(temp);
4311                break;
4312        }
4313    }
4314
4315    void decodeTypeImpPostfix(String& buffer, Type* pType) {
4316        TypeTag tag = pType->tag;
4317
4318        switch(tag) {
4319            case TY_POINTER:
4320                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
4321                    buffer.append(')');
4322                }
4323                decodeTypeImpPostfix(buffer, pType->pHead);
4324                break;
4325            case TY_FUNC:
4326                buffer.append('(');
4327                for(Type* pArg = pType->pTail; pArg; pArg = pArg->pTail) {
4328                    decodeTypeImp(buffer, pArg);
4329                    if (pArg->pTail) {
4330                        buffer.appendCStr(", ");
4331                    }
4332                }
4333                buffer.append(')');
4334                break;
4335            default:
4336                break;
4337        }
4338    }
4339
4340    void printType(Type* pType) {
4341        String buffer;
4342        decodeType(buffer, pType);
4343        fprintf(stderr, "%s\n", buffer.getUnwrapped());
4344    }
4345
4346    Type* acceptPrimitiveType() {
4347        Type* pType;
4348        if (tok == TOK_INT) {
4349            pType = mkpInt;
4350        } else if (tok == TOK_CHAR) {
4351            pType = mkpChar;
4352        } else if (tok == TOK_VOID) {
4353            pType = mkpVoid;
4354        } else if (tok == TOK_FLOAT) {
4355            pType = mkpFloat;
4356        } else if (tok == TOK_DOUBLE) {
4357            pType = mkpDouble;
4358        } else {
4359            return NULL;
4360        }
4361        next();
4362        return pType;
4363    }
4364
4365    Type* acceptDeclaration(Type* pType, bool nameAllowed, bool nameRequired) {
4366        tokenid_t declName = 0;
4367        bool reportFailure = false;
4368        pType = acceptDecl2(pType, declName, nameAllowed,
4369                                  nameRequired, reportFailure);
4370        if (declName) {
4371            // Clone the parent type so we can set a unique ID
4372            pType = createType(pType->tag, pType->pHead, pType->pTail);
4373
4374            pType->id = declName;
4375        }
4376        // fprintf(stderr, "Parsed a declaration:       ");
4377        // printType(pType);
4378        if (reportFailure) {
4379            return NULL;
4380        }
4381        return pType;
4382    }
4383
4384    Type* expectDeclaration(Type* pBaseType) {
4385        Type* pType = acceptDeclaration(pBaseType, true, true);
4386        if (! pType) {
4387            error("Expected a declaration");
4388        }
4389        return pType;
4390    }
4391
4392    /* Used for accepting types that appear in casts */
4393    Type* acceptCastTypeDeclaration() {
4394        Type* pType = acceptPrimitiveType();
4395        if (pType) {
4396            pType = acceptDeclaration(pType, false, false);
4397        }
4398        return pType;
4399    }
4400
4401    Type* expectCastTypeDeclaration() {
4402        Type* pType = acceptCastTypeDeclaration();
4403        if (! pType) {
4404            error("Expected a declaration");
4405        }
4406        return pType;
4407    }
4408
4409    Type* acceptDecl2(Type* pType, tokenid_t& declName,
4410                      bool nameAllowed, bool nameRequired,
4411                      bool& reportFailure) {
4412        while (accept('*')) {
4413            pType = createType(TY_POINTER, pType, NULL);
4414        }
4415        pType = acceptDecl3(pType, declName, nameAllowed, nameRequired,
4416                            reportFailure);
4417        return pType;
4418    }
4419
4420    Type* acceptDecl3(Type* pType, tokenid_t& declName,
4421                      bool nameAllowed, bool nameRequired,
4422                      bool& reportFailure) {
4423        // direct-dcl :
4424        //   name
4425        //  (dcl)
4426        //   direct-dcl()
4427        //   direct-dcl[]
4428        Type* pNewHead = NULL;
4429        if (accept('(')) {
4430            pNewHead = acceptDecl2(pNewHead, declName, nameAllowed,
4431                                nameRequired, reportFailure);
4432            skip(')');
4433        } else if ((declName = acceptSymbol()) != 0) {
4434            if (nameAllowed == false && declName) {
4435                error("Symbol %s not allowed here", nameof(declName));
4436                reportFailure = true;
4437            }
4438        } else if (nameRequired && ! declName) {
4439            String temp;
4440            decodeToken(temp, tok, true);
4441            error("Expected name. Got %s", temp.getUnwrapped());
4442            reportFailure = true;
4443        }
4444        while (accept('(')) {
4445            // Function declaration
4446            Type* pTail = acceptArgs(nameAllowed);
4447            pType = createType(TY_FUNC, pType, pTail);
4448            skip(')');
4449        }
4450
4451        if (pNewHead) {
4452            Type* pA = pNewHead;
4453            while (pA->pHead) {
4454                pA = pA->pHead;
4455            }
4456            pA->pHead = pType;
4457            pType = pNewHead;
4458        }
4459        return pType;
4460    }
4461
4462    Type* acceptArgs(bool nameAllowed) {
4463        Type* pHead = NULL;
4464        Type* pTail = NULL;
4465        for(;;) {
4466            Type* pBaseArg = acceptPrimitiveType();
4467            if (pBaseArg) {
4468                Type* pArg = acceptDeclaration(pBaseArg, nameAllowed, false);
4469                if (pArg) {
4470                    Type* pParam = createType(TY_PARAM, pArg, NULL);
4471                    if (!pHead) {
4472                        pHead = pParam;
4473                        pTail = pParam;
4474                    } else {
4475                        pTail->pTail = pParam;
4476                        pTail = pParam;
4477                    }
4478                }
4479            }
4480            if (! accept(',')) {
4481                break;
4482            }
4483        }
4484        return pHead;
4485    }
4486
4487    Type* expectPrimitiveType() {
4488        Type* pType = acceptPrimitiveType();
4489        if (!pType) {
4490            String buf;
4491            decodeToken(buf, tok, true);
4492            error("Expected a type, got %s", buf.getUnwrapped());
4493        }
4494        return pType;
4495    }
4496
4497    void checkLVal() {
4498        if (pGen->getR0ExpressionType() != ET_LVALUE) {
4499            error("Expected an lval");
4500        }
4501    }
4502
4503    void addGlobalSymbol(Type* pDecl) {
4504        tokenid_t t = pDecl->id;
4505        VariableInfo* pVI = VI(t);
4506        if(pVI && pVI->pAddress) {
4507            reportDuplicate(t);
4508        }
4509        mGlobals.add(pDecl);
4510    }
4511
4512    void reportDuplicate(tokenid_t t) {
4513        error("Duplicate definition of %s", nameof(t));
4514    }
4515
4516    void addLocalSymbol(Type* pDecl) {
4517        tokenid_t t = pDecl->id;
4518        if (mLocals.isDefinedAtCurrentLevel(t)) {
4519            reportDuplicate(t);
4520        }
4521        mLocals.add(pDecl);
4522    }
4523
4524    void localDeclarations(Type* pBaseType) {
4525        intptr_t a;
4526
4527        while (pBaseType) {
4528            while (tok != ';' && tok != EOF) {
4529                Type* pDecl = expectDeclaration(pBaseType);
4530                if (!pDecl) {
4531                    break;
4532                }
4533                int variableAddress = 0;
4534                addLocalSymbol(pDecl);
4535                size_t alignment = pGen->stackAlignmentOf(pDecl);
4536                size_t alignmentMask = ~ (alignment - 1);
4537                size_t sizeOf = pGen->sizeOf(pDecl);
4538                loc = (loc + alignment - 1) & alignmentMask;
4539                size_t alignedSize = (sizeOf + alignment - 1) & alignmentMask;
4540                loc = loc + alignedSize;
4541                variableAddress = -loc;
4542                VI(pDecl->id)->pAddress = (void*) variableAddress;
4543                if (accept('=')) {
4544                    /* assignment */
4545                    pGen->leaR0(variableAddress, createPtrType(pDecl), ET_LVALUE);
4546                    pGen->pushR0();
4547                    expr();
4548                    pGen->forceR0RVal();
4549                    pGen->storeR0ToTOS();
4550                }
4551                if (tok == ',')
4552                    next();
4553            }
4554            skip(';');
4555            pBaseType = acceptPrimitiveType();
4556        }
4557    }
4558
4559    bool checkSymbol() {
4560        return checkSymbol(tok);
4561    }
4562
4563    void decodeToken(String& buffer, tokenid_t token, bool quote) {
4564        if (token == EOF ) {
4565            buffer.printf("EOF");
4566        } else if (token == TOK_NUM) {
4567            buffer.printf("numeric constant");
4568        } else if (token >= 0 && token < 256) {
4569            if (token < 32) {
4570                buffer.printf("'\\x%02x'", token);
4571            } else {
4572                buffer.printf("'%c'", token);
4573            }
4574        } else {
4575            if (quote) {
4576                if (token >= TOK_KEYWORD && token < TOK_SYMBOL) {
4577                    buffer.printf("keyword \"%s\"", nameof(token));
4578                } else {
4579                    buffer.printf("symbol \"%s\"", nameof(token));
4580                }
4581            } else {
4582                buffer.printf("%s", nameof(token));
4583            }
4584        }
4585    }
4586
4587    bool checkSymbol(tokenid_t token) {
4588        bool result = token >= TOK_SYMBOL;
4589        if (!result) {
4590            String temp;
4591            decodeToken(temp, token, true);
4592            error("Expected symbol. Got %s", temp.getUnwrapped());
4593        }
4594        return result;
4595    }
4596
4597    tokenid_t acceptSymbol() {
4598        tokenid_t result = 0;
4599        if (tok >= TOK_SYMBOL) {
4600            result = tok;
4601            next();
4602        }
4603        return result;
4604    }
4605
4606    void globalDeclarations() {
4607        while (tok != EOF) {
4608            Type* pBaseType = expectPrimitiveType();
4609            if (!pBaseType) {
4610                break;
4611            }
4612            Type* pDecl = expectDeclaration(pBaseType);
4613            if (!pDecl) {
4614                break;
4615            }
4616            if (! isDefined(pDecl->id)) {
4617                addGlobalSymbol(pDecl);
4618            }
4619            VariableInfo* name = VI(pDecl->id);
4620            if (name && name->pAddress) {
4621                error("Already defined global %s", nameof(pDecl->id));
4622            }
4623            if (pDecl->tag < TY_FUNC) {
4624                // it's a variable declaration
4625                for(;;) {
4626                    if (name && !name->pAddress) {
4627                        name->pAddress = (int*) allocGlobalSpace(
4628                                                   pGen->alignmentOf(name->pType),
4629                                                   pGen->sizeOf(name->pType));
4630                    }
4631                    if (accept('=')) {
4632                        if (tok == TOK_NUM) {
4633                            if (name) {
4634                                * (int*) name->pAddress = tokc;
4635                            }
4636                            next();
4637                        } else {
4638                            error("Expected an integer constant");
4639                        }
4640                    }
4641                    if (!accept(',')) {
4642                        break;
4643                    }
4644                    pDecl = expectDeclaration(pBaseType);
4645                    if (!pDecl) {
4646                        break;
4647                    }
4648                    if (! isDefined(pDecl->id)) {
4649                        addGlobalSymbol(pDecl);
4650                    }
4651                    name = VI(pDecl->id);
4652                }
4653                skip(';');
4654            } else {
4655                // Function declaration
4656                if (accept(';')) {
4657                    // forward declaration.
4658                } else if (tok != '{') {
4659                    error("expected '{'");
4660                } else {
4661                    mpCurrentArena = &mLocalArena;
4662                    if (name) {
4663                        /* patch forward references */
4664                        pGen->resolveForward((int) name->pForward);
4665                        /* put function address */
4666                        name->pAddress = (void*) codeBuf.getPC();
4667                    }
4668                    // Calculate stack offsets for parameters
4669                    mLocals.pushLevel();
4670                    intptr_t a = 8;
4671                    int argCount = 0;
4672                    for (Type* pP = pDecl->pTail; pP; pP = pP->pTail) {
4673                        Type* pArg = pP->pHead;
4674                        addLocalSymbol(pArg);
4675                        /* read param name and compute offset */
4676                        size_t alignment = pGen->stackAlignmentOf(pArg);
4677                        a = (a + alignment - 1) & ~ (alignment-1);
4678                        VI(pArg->id)->pAddress = (void*) a;
4679                        a = a + pGen->stackSizeOf(pArg);
4680                        argCount++;
4681                    }
4682                    rsym = loc = 0;
4683                    pReturnType = pDecl->pHead;
4684                    a = pGen->functionEntry(pDecl);
4685                    block(0, true);
4686                    pGen->gsym(rsym);
4687                    pGen->functionExit(pDecl, a, loc);
4688                    mLocals.popLevel();
4689                    mpCurrentArena = &mGlobalArena;
4690                }
4691            }
4692        }
4693    }
4694
4695    char* allocGlobalSpace(size_t alignment, size_t bytes) {
4696        size_t base = (((size_t) glo) + alignment - 1) & ~(alignment-1);
4697        size_t end = base + bytes;
4698        if ((end - (size_t) pGlobalBase) > (size_t) ALLOC_SIZE) {
4699            error("Global space exhausted");
4700            return NULL;
4701        }
4702        char* result = (char*) base;
4703        glo = (char*) end;
4704        return result;
4705    }
4706
4707    void cleanup() {
4708        if (pGlobalBase != 0) {
4709            free(pGlobalBase);
4710            pGlobalBase = 0;
4711        }
4712        if (pGen) {
4713            delete pGen;
4714            pGen = 0;
4715        }
4716        if (file) {
4717            delete file;
4718            file = 0;
4719        }
4720    }
4721
4722    // One-time initialization, when class is constructed.
4723    void init() {
4724        mpSymbolLookupFn = 0;
4725        mpSymbolLookupContext = 0;
4726    }
4727
4728    void clear() {
4729        tok = 0;
4730        tokc = 0;
4731        tokl = 0;
4732        ch = 0;
4733        rsym = 0;
4734        loc = 0;
4735        glo = 0;
4736        dptr = 0;
4737        dch = 0;
4738        file = 0;
4739        pGlobalBase = 0;
4740        pGen = 0;
4741        mPragmaStringCount = 0;
4742        mCompileResult = 0;
4743        mLineNumber = 1;
4744        mbBumpLine = false;
4745    }
4746
4747    void setArchitecture(const char* architecture) {
4748        delete pGen;
4749        pGen = 0;
4750
4751        if (architecture != NULL) {
4752#ifdef PROVIDE_ARM_CODEGEN
4753            if (! pGen && strcmp(architecture, "arm") == 0) {
4754                pGen = new ARMCodeGenerator();
4755            }
4756#endif
4757#ifdef PROVIDE_X86_CODEGEN
4758            if (! pGen && strcmp(architecture, "x86") == 0) {
4759                pGen = new X86CodeGenerator();
4760            }
4761#endif
4762            if (!pGen ) {
4763                error("Unknown architecture %s\n", architecture);
4764            }
4765        }
4766
4767        if (pGen == NULL) {
4768#if defined(DEFAULT_ARM_CODEGEN)
4769            pGen = new ARMCodeGenerator();
4770#elif defined(DEFAULT_X86_CODEGEN)
4771            pGen = new X86CodeGenerator();
4772#endif
4773        }
4774        if (pGen == NULL) {
4775            error("No code generator defined.");
4776        } else {
4777            pGen->setErrorSink(this);
4778            pGen->setTypes(mkpInt);
4779        }
4780    }
4781
4782public:
4783    struct args {
4784        args() {
4785            architecture = 0;
4786        }
4787        const char* architecture;
4788    };
4789
4790    Compiler() {
4791        init();
4792        clear();
4793    }
4794
4795    ~Compiler() {
4796        cleanup();
4797    }
4798
4799    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
4800        mpSymbolLookupFn = pFn;
4801        mpSymbolLookupContext = pContext;
4802    }
4803
4804    int compile(const char* text, size_t textLength) {
4805        int result;
4806
4807        mpCurrentArena = &mGlobalArena;
4808        createPrimitiveTypes();
4809        cleanup();
4810        clear();
4811        mTokenTable.setArena(&mGlobalArena);
4812        mGlobals.setArena(&mGlobalArena);
4813        mGlobals.setTokenTable(&mTokenTable);
4814        mLocals.setArena(&mLocalArena);
4815        mLocals.setTokenTable(&mTokenTable);
4816
4817        internKeywords();
4818        codeBuf.init(ALLOC_SIZE);
4819        setArchitecture(NULL);
4820        if (!pGen) {
4821            return -1;
4822        }
4823#ifdef PROVIDE_TRACE_CODEGEN
4824            pGen = new TraceCodeGenerator(pGen);
4825#endif
4826            pGen->setErrorSink(this);
4827        pGen->init(&codeBuf);
4828        file = new TextInputStream(text, textLength);
4829        pGlobalBase = (char*) calloc(1, ALLOC_SIZE);
4830        glo = pGlobalBase;
4831        inp();
4832        next();
4833        globalDeclarations();
4834        checkForUndefinedForwardReferences();
4835        result = pGen->finishCompile();
4836        if (result == 0) {
4837            if (mErrorBuf.len()) {
4838                result = -2;
4839            }
4840        }
4841        mCompileResult = result;
4842        return result;
4843    }
4844
4845    void createPrimitiveTypes() {
4846        mkpInt = createType(TY_INT, NULL, NULL);
4847        mkpChar = createType(TY_CHAR, NULL, NULL);
4848        mkpVoid = createType(TY_VOID, NULL, NULL);
4849        mkpFloat = createType(TY_FLOAT, NULL, NULL);
4850        mkpDouble = createType(TY_DOUBLE, NULL, NULL);
4851        mkpIntFn =  createType(TY_FUNC, mkpInt, NULL);
4852        mkpIntPtr = createPtrType(mkpInt);
4853        mkpCharPtr = createPtrType(mkpChar);
4854        mkpFloatPtr = createPtrType(mkpFloat);
4855        mkpDoublePtr = createPtrType(mkpDouble);
4856        mkpPtrIntFn = createPtrType(mkpIntFn);
4857    }
4858
4859    void checkForUndefinedForwardReferences() {
4860        mGlobals.forEach(static_ufrcFn, this);
4861    }
4862
4863    static bool static_ufrcFn(VariableInfo* value, void* context) {
4864        Compiler* pCompiler = (Compiler*) context;
4865        return pCompiler->undefinedForwardReferenceCheck(value);
4866    }
4867
4868    bool undefinedForwardReferenceCheck(VariableInfo* value) {
4869        if (!value->pAddress && value->pForward) {
4870            error("Undefined forward reference: %s",
4871                  mTokenTable[value->tok].pText);
4872        }
4873        return true;
4874    }
4875
4876    int dump(FILE* out) {
4877        fwrite(codeBuf.getBase(), 1, codeBuf.getSize(), out);
4878        return 0;
4879    }
4880
4881    int disassemble(FILE* out) {
4882        return pGen->disassemble(out);
4883    }
4884
4885    /* Look through the symbol table to find a symbol.
4886     * If found, return its value.
4887     */
4888    void* lookup(const char* name) {
4889        if (mCompileResult == 0) {
4890            tokenid_t tok = mTokenTable.intern(name, strlen(name));
4891            VariableInfo* pVariableInfo = VI(tok);
4892            if (pVariableInfo) {
4893                return pVariableInfo->pAddress;
4894            }
4895        }
4896        return NULL;
4897    }
4898
4899    void getPragmas(ACCsizei* actualStringCount,
4900                    ACCsizei maxStringCount, ACCchar** strings) {
4901        int stringCount = mPragmaStringCount;
4902        if (actualStringCount) {
4903            *actualStringCount = stringCount;
4904        }
4905        if (stringCount > maxStringCount) {
4906            stringCount = maxStringCount;
4907        }
4908        if (strings) {
4909            char* pPragmas = mPragmas.getUnwrapped();
4910            while (stringCount-- > 0) {
4911                *strings++ = pPragmas;
4912                pPragmas += strlen(pPragmas) + 1;
4913            }
4914        }
4915    }
4916
4917    char* getErrorMessage() {
4918        return mErrorBuf.getUnwrapped();
4919    }
4920
4921};
4922
4923const char* Compiler::operatorChars =
4924    "++--*@/@%@+@-@<<>><=>=<@>@==!=&&||&@^@|@~@!@";
4925
4926const char Compiler::operatorLevel[] =
4927    {11, 11, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4,
4928            5, 5, /* ==, != */
4929            9, 10, /* &&, || */
4930            6, 7, 8, /* & ^ | */
4931            2, 2 /* ~ ! */
4932            };
4933
4934#ifdef PROVIDE_ARM_CODEGEN
4935FILE* Compiler::ARMCodeGenerator::disasmOut;
4936#endif
4937
4938#ifdef PROVIDE_X86_CODEGEN
4939const int Compiler::X86CodeGenerator::operatorHelper[] = {
4940        0x1,     // ++
4941        0xff,    // --
4942        0xc1af0f, // *
4943        0xf9f79991, // /
4944        0xf9f79991, // % (With manual assist to swap results)
4945        0xc801, // +
4946        0xd8f7c829, // -
4947        0xe0d391, // <<
4948        0xf8d391, // >>
4949        0xe, // <=
4950        0xd, // >=
4951        0xc, // <
4952        0xf, // >
4953        0x4, // ==
4954        0x5, // !=
4955        0x0, // &&
4956        0x1, // ||
4957        0xc821, // &
4958        0xc831, // ^
4959        0xc809, // |
4960        0xd0f7, // ~
4961        0x4     // !
4962};
4963#endif
4964
4965struct ACCscript {
4966    ACCscript() {
4967        text = 0;
4968        textLength = 0;
4969        accError = ACC_NO_ERROR;
4970    }
4971
4972    ~ACCscript() {
4973        delete text;
4974    }
4975
4976    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
4977        compiler.registerSymbolCallback(pFn, pContext);
4978    }
4979
4980    void setError(ACCenum error) {
4981        if (accError == ACC_NO_ERROR && error != ACC_NO_ERROR) {
4982            accError = error;
4983        }
4984    }
4985
4986    ACCenum getError() {
4987        ACCenum result = accError;
4988        accError = ACC_NO_ERROR;
4989        return result;
4990    }
4991
4992    Compiler compiler;
4993    char* text;
4994    int textLength;
4995    ACCenum accError;
4996};
4997
4998
4999extern "C"
5000ACCscript* accCreateScript() {
5001    return new ACCscript();
5002}
5003
5004extern "C"
5005ACCenum accGetError( ACCscript* script ) {
5006    return script->getError();
5007}
5008
5009extern "C"
5010void accDeleteScript(ACCscript* script) {
5011    delete script;
5012}
5013
5014extern "C"
5015void accRegisterSymbolCallback(ACCscript* script, ACCSymbolLookupFn pFn,
5016                               ACCvoid* pContext) {
5017    script->registerSymbolCallback(pFn, pContext);
5018}
5019
5020extern "C"
5021void accScriptSource(ACCscript* script,
5022    ACCsizei count,
5023    const ACCchar ** string,
5024    const ACCint * length) {
5025    int totalLength = 0;
5026    for(int i = 0; i < count; i++) {
5027        int len = -1;
5028        const ACCchar* s = string[i];
5029        if (length) {
5030            len = length[i];
5031        }
5032        if (len < 0) {
5033            len = strlen(s);
5034        }
5035        totalLength += len;
5036    }
5037    delete script->text;
5038    char* text = new char[totalLength + 1];
5039    script->text = text;
5040    script->textLength = totalLength;
5041    char* dest = text;
5042    for(int i = 0; i < count; i++) {
5043        int len = -1;
5044        const ACCchar* s = string[i];
5045        if (length) {
5046            len = length[i];
5047        }
5048        if (len < 0) {
5049            len = strlen(s);
5050        }
5051        memcpy(dest, s, len);
5052        dest += len;
5053    }
5054    text[totalLength] = '\0';
5055}
5056
5057extern "C"
5058void accCompileScript(ACCscript* script) {
5059    int result = script->compiler.compile(script->text, script->textLength);
5060    if (result) {
5061        script->setError(ACC_INVALID_OPERATION);
5062    }
5063}
5064
5065extern "C"
5066void accGetScriptiv(ACCscript* script,
5067    ACCenum pname,
5068    ACCint * params) {
5069    switch (pname) {
5070        case ACC_INFO_LOG_LENGTH:
5071            *params = 0;
5072            break;
5073    }
5074}
5075
5076extern "C"
5077void accGetScriptInfoLog(ACCscript* script,
5078    ACCsizei maxLength,
5079    ACCsizei * length,
5080    ACCchar * infoLog) {
5081    char* message = script->compiler.getErrorMessage();
5082    int messageLength = strlen(message) + 1;
5083    if (length) {
5084        *length = messageLength;
5085    }
5086    if (infoLog && maxLength > 0) {
5087        int trimmedLength = maxLength < messageLength ?
5088                maxLength : messageLength;
5089        memcpy(infoLog, message, trimmedLength);
5090        infoLog[trimmedLength] = 0;
5091    }
5092}
5093
5094extern "C"
5095void accGetScriptLabel(ACCscript* script, const ACCchar * name,
5096                       ACCvoid ** address) {
5097    void* value = script->compiler.lookup(name);
5098    if (value) {
5099        *address = value;
5100    } else {
5101        script->setError(ACC_INVALID_VALUE);
5102    }
5103}
5104
5105extern "C"
5106void accGetPragmas(ACCscript* script, ACCsizei* actualStringCount,
5107                   ACCsizei maxStringCount, ACCchar** strings){
5108    script->compiler.getPragmas(actualStringCount, maxStringCount, strings);
5109}
5110
5111extern "C"
5112void accDisassemble(ACCscript* script) {
5113    script->compiler.disassemble(stderr);
5114}
5115
5116
5117} // namespace acc
5118
5119