acc.cpp revision 46f2bd2080115122f1ba5f3e12f6ce6a81a82fae 
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#define LOG_TAG "acc"
12#include <cutils/log.h>
13
14#include <ctype.h>
15#include <errno.h>
16#include <limits.h>
17#include <stdarg.h>
18#include <stdint.h>
19#include <stdio.h>
20#include <stdlib.h>
21#include <string.h>
22#include <unistd.h>
23
24#include <cutils/hashmap.h>
25
26#if defined(__i386__)
27#include <sys/mman.h>
28#endif
29
30
31#if defined(__arm__)
32#define DEFAULT_ARM_CODEGEN
33#define PROVIDE_ARM_CODEGEN
34#elif defined(__i386__)
35#define DEFAULT_X86_CODEGEN
36#define PROVIDE_X86_CODEGEN
37#elif defined(__x86_64__)
38#define DEFAULT_X64_CODEGEN
39#define PROVIDE_X64_CODEGEN
40#endif
41
42#if (defined(__VFP_FP__) && !defined(__SOFTFP__))
43#define ARM_USE_VFP
44#endif
45
46#include <acc/acc.h>
47
48#define LOG_API(...) do {} while(0)
49// #define LOG_API(...) fprintf (stderr, __VA_ARGS__)
50
51#define LOG_STACK(...) do {} while(0)
52// #define LOG_STACK(...) fprintf (stderr, __VA_ARGS__)
53
54// #define PROVIDE_TRACE_CODEGEN
55
56// Uncomment to disable ARM peephole optimizations
57// #define DISABLE_ARM_PEEPHOLE
58
59// Uncomment to save input to a text file in DEBUG_DUMP_PATTERN
60// #define DEBUG_SAVE_INPUT_TO_FILE
61
62#ifdef DEBUG_SAVE_INPUT_TO_FILE
63#ifdef ARM_USE_VFP
64#define DEBUG_DUMP_PATTERN "/data/misc/acc_dump/%d.c"
65#else
66#define DEBUG_DUMP_PATTERN "/tmp/acc_dump/%d.c"
67#endif
68#endif
69
70#define assert(b) assertImpl(b, __LINE__)
71
72namespace acc {
73
74// Subset of STL vector.
75template<class E> class Vector {
76    public:
77    Vector() {
78        mpBase = 0;
79        mUsed = 0;
80        mSize = 0;
81    }
82
83    ~Vector() {
84        if (mpBase) {
85            for(size_t i = 0; i < mUsed; i++)  {
86                mpBase[mUsed].~E();
87            }
88            free(mpBase);
89        }
90    }
91
92    inline E& operator[](size_t i) {
93        return mpBase[i];
94    }
95
96    inline E& front() {
97        return mpBase[0];
98    }
99
100    inline E& back() {
101        return mpBase[mUsed - 1];
102    }
103
104    void pop_back() {
105        mUsed -= 1;
106        mpBase[mUsed].~E();
107    }
108
109    void push_back(const E& item) {
110        * ensure(1) = item;
111    }
112
113    size_t size() {
114        return mUsed;
115    }
116
117private:
118    E* ensure(int n) {
119        size_t newUsed = mUsed + n;
120        if (newUsed > mSize) {
121            size_t newSize = mSize * 2 + 10;
122            if (newSize < newUsed) {
123                newSize = newUsed;
124            }
125            mpBase = (E*) realloc(mpBase, sizeof(E) * newSize);
126            mSize = newSize;
127        }
128        E* result = mpBase + mUsed;
129        mUsed = newUsed;
130        return result;
131    }
132
133    E* mpBase;
134    size_t mUsed;
135    size_t mSize;
136};
137
138class ErrorSink {
139public:
140    void error(const char *fmt, ...) {
141        va_list ap;
142        va_start(ap, fmt);
143        verror(fmt, ap);
144        va_end(ap);
145    }
146
147    virtual ~ErrorSink() {}
148    virtual void verror(const char* fmt, va_list ap) = 0;
149};
150
151class Compiler : public ErrorSink {
152    typedef int tokenid_t;
153    enum TypeTag {
154        TY_UNKNOWN =     -1,
155        TY_INT,       // 0
156        TY_CHAR,      // 1
157        TY_SHORT,     // 2
158        TY_VOID,      // 3
159        TY_FLOAT,     // 4
160        TY_DOUBLE,    // 5
161        TY_POINTER,   // 6
162        TY_ARRAY,     // 7
163        TY_STRUCT,    // 8
164        TY_FUNC,      // 9
165        TY_PARAM      // 10
166    };
167
168    enum StorageClass {
169        SC_DEFAULT,  // 0
170        SC_AUTO,     // 1
171        SC_REGISTER, // 2
172        SC_STATIC,   // 3
173        SC_EXTERN,   // 4
174        SC_TYPEDEF   // 5
175    };
176
177    struct Type {
178        TypeTag tag;
179        StorageClass  storageClass;
180        tokenid_t id; // For function arguments, global vars, local vars, struct elements
181        tokenid_t structTag; // For structs the name of the struct
182        int length; // length of array, offset of struct element. -1 means struct is forward defined
183        int alignment; // for structs only
184        Type* pHead; // For a struct this is the prototype struct.
185        Type* pTail;
186    };
187
188    enum ExpressionType {
189        ET_RVALUE,
190        ET_LVALUE
191    };
192
193    struct ExpressionValue {
194        ExpressionValue() {
195            et = ET_RVALUE;
196            pType = NULL;
197        }
198        ExpressionType et;
199        Type* pType;
200    };
201
202    class ICodeBuf {
203    public:
204        virtual ~ICodeBuf() {}
205        virtual void init(int size) = 0;
206        virtual void setErrorSink(ErrorSink* pErrorSink) = 0;
207        virtual void o4(int n) = 0;
208        virtual void ob(int n) = 0;
209        virtual void* getBase() = 0;
210        virtual intptr_t getSize() = 0;
211        virtual intptr_t getPC() = 0;
212        // Call this before trying to modify code in the buffer.
213        virtual void flush() = 0;
214    };
215
216    class CodeBuf : public ICodeBuf {
217        char* ind; // Output code pointer
218        char* pProgramBase;
219        ErrorSink* mErrorSink;
220        int mSize;
221        bool mOverflowed;
222
223        void release() {
224            if (pProgramBase != 0) {
225                free(pProgramBase);
226                pProgramBase = 0;
227            }
228        }
229
230        bool check(int n) {
231            int newSize = ind - pProgramBase + n;
232            bool overflow = newSize > mSize;
233            if (overflow && !mOverflowed) {
234                mOverflowed = true;
235                if (mErrorSink) {
236                    mErrorSink->error("Code too large: %d bytes", newSize);
237                }
238            }
239            return overflow;
240        }
241
242    public:
243        CodeBuf() {
244            pProgramBase = 0;
245            ind = 0;
246            mErrorSink = 0;
247            mSize = 0;
248            mOverflowed = false;
249        }
250
251        virtual ~CodeBuf() {
252            release();
253        }
254
255        virtual void init(int size) {
256            release();
257            mSize = size;
258            pProgramBase = (char*) calloc(1, size);
259            ind = pProgramBase;
260        }
261
262        virtual void setErrorSink(ErrorSink* pErrorSink) {
263            mErrorSink = pErrorSink;
264        }
265
266        virtual void o4(int n) {
267            if(check(4)) {
268                return;
269            }
270            * (int*) ind = n;
271            ind += 4;
272        }
273
274        /*
275         * Output a byte. Handles all values, 0..ff.
276         */
277        virtual void ob(int n) {
278            if(check(1)) {
279                return;
280            }
281            *ind++ = n;
282        }
283
284        virtual void* getBase() {
285            return (void*) pProgramBase;
286        }
287
288        virtual intptr_t getSize() {
289            return ind - pProgramBase;
290        }
291
292        virtual intptr_t getPC() {
293            return (intptr_t) ind;
294        }
295
296        virtual void flush() {}
297    };
298
299    /**
300     * A code generator creates an in-memory program, generating the code on
301     * the fly. There is one code generator implementation for each supported
302     * architecture.
303     *
304     * The code generator implements the following abstract machine:
305     * R0 - the accumulator.
306     * FP - a frame pointer for accessing function arguments and local
307     *      variables.
308     * SP - a stack pointer for storing intermediate results while evaluating
309     *      expressions. The stack pointer grows downwards.
310     *
311     * The function calling convention is that all arguments are placed on the
312     * stack such that the first argument has the lowest address.
313     * After the call, the result is in R0. The caller is responsible for
314     * removing the arguments from the stack.
315     * The R0 register is not saved across function calls. The
316     * FP and SP registers are saved.
317     */
318
319    class CodeGenerator {
320    public:
321        CodeGenerator() {
322            mErrorSink = 0;
323            pCodeBuf = 0;
324            pushType();
325        }
326        virtual ~CodeGenerator() {}
327
328        virtual void init(ICodeBuf* pCodeBuf) {
329            this->pCodeBuf = pCodeBuf;
330            pCodeBuf->setErrorSink(mErrorSink);
331        }
332
333        virtual void setErrorSink(ErrorSink* pErrorSink) {
334            mErrorSink = pErrorSink;
335            if (pCodeBuf) {
336                pCodeBuf->setErrorSink(mErrorSink);
337            }
338        }
339
340        /* Give the code generator some utility types so it can
341         * use its own types as needed for the results of some
342         * operations like gcmp.
343         */
344
345        void setTypes(Type* pInt) {
346            mkpInt = pInt;
347        }
348
349        /* Emit a function prolog.
350         * pDecl is the function declaration, which gives the arguments.
351         * Save the old value of the FP.
352         * Set the new value of the FP.
353         * Convert from the native platform calling convention to
354         * our stack-based calling convention. This may require
355         * pushing arguments from registers to the stack.
356         * Allocate "N" bytes of stack space. N isn't known yet, so
357         * just emit the instructions for adjusting the stack, and return
358         * the address to patch up. The patching will be done in
359         * functionExit().
360         * returns address to patch with local variable size.
361        */
362        virtual int functionEntry(Type* pDecl) = 0;
363
364        /* Emit a function epilog.
365         * Restore the old SP and FP register values.
366         * Return to the calling function.
367         * argCount - the number of arguments to the function.
368         * localVariableAddress - returned from functionEntry()
369         * localVariableSize - the size in bytes of the local variables.
370         */
371        virtual void functionExit(Type* pDecl, int localVariableAddress,
372                                  int localVariableSize) = 0;
373
374        /* load immediate value to R0 */
375        virtual void li(int i) = 0;
376
377        /* Load floating point value from global address. */
378        virtual void loadFloat(int address, Type* pType) = 0;
379
380        /* Add the struct offset in bytes to R0, change the type to pType */
381        virtual void addStructOffsetR0(int offset, Type* pType) = 0;
382
383        /* Jump to a target, and return the address of the word that
384         * holds the target data, in case it needs to be fixed up later.
385         */
386        virtual int gjmp(int t) = 0;
387
388        /* Test R0 and jump to a target if the test succeeds.
389         * l = 0: je, l == 1: jne
390         * Return the address of the word that holds the targed data, in
391         * case it needs to be fixed up later.
392         */
393        virtual int gtst(bool l, int t) = 0;
394
395        /* Compare TOS against R0, and store the boolean result in R0.
396         * Pops TOS.
397         * op specifies the comparison.
398         */
399        virtual void gcmp(int op) = 0;
400
401        /* Perform the arithmetic op specified by op. TOS is the
402         * left argument, R0 is the right argument.
403         * Pops TOS.
404         */
405        virtual void genOp(int op) = 0;
406
407        /* Compare 0 against R0, and store the boolean result in R0.
408         * op specifies the comparison.
409         */
410        virtual void gUnaryCmp(int op) = 0;
411
412        /* Perform the arithmetic op specified by op. 0 is the
413         * left argument, R0 is the right argument.
414         */
415        virtual void genUnaryOp(int op) = 0;
416
417        /* Push R0 onto the stack. (Also known as "dup" for duplicate.)
418         */
419        virtual void pushR0() = 0;
420
421        /* Turn R0, TOS into R0 TOS R0 */
422
423        virtual void over() = 0;
424
425        /* Pop R0 from the stack. (Also known as "drop")
426         */
427        virtual void popR0() = 0;
428
429        /* Store R0 to the address stored in TOS.
430         * The TOS is popped.
431         */
432        virtual void storeR0ToTOS() = 0;
433
434        /* Load R0 from the address stored in R0.
435         */
436        virtual void loadR0FromR0() = 0;
437
438        /* Load the absolute address of a variable to R0.
439         * If ea <= LOCAL, then this is a local variable, or an
440         * argument, addressed relative to FP.
441         * else it is an absolute global address.
442         *
443         * et is ET_RVALUE for things like string constants, ET_LVALUE for
444         * variables.
445         */
446        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) = 0;
447
448        /* Load the pc-relative address of a forward-referenced variable to R0.
449         * Return the address of the 4-byte constant so that it can be filled
450         * in later.
451         */
452        virtual int leaForward(int ea, Type* pPointerType) = 0;
453
454        /**
455         * Convert R0 to the given type.
456         */
457
458        void convertR0(Type* pType) {
459            convertR0Imp(pType, false);
460        }
461
462        void castR0(Type* pType) {
463            convertR0Imp(pType, true);
464        }
465
466        virtual void convertR0Imp(Type* pType, bool isCast) = 0;
467
468        /* Emit code to adjust the stack for a function call. Return the
469         * label for the address of the instruction that adjusts the
470         * stack size. This will be passed as argument "a" to
471         * endFunctionCallArguments.
472         */
473        virtual int beginFunctionCallArguments() = 0;
474
475        /* Emit code to store R0 to the stack at byte offset l.
476         * Returns stack size of object (typically 4 or 8 bytes)
477         */
478        virtual size_t storeR0ToArg(int l, Type* pArgType) = 0;
479
480        /* Patch the function call preamble.
481         * a is the address returned from beginFunctionCallArguments
482         * l is the number of bytes the arguments took on the stack.
483         * Typically you would also emit code to convert the argument
484         * list into whatever the native function calling convention is.
485         * On ARM for example you would pop the first 5 arguments into
486         * R0..R4
487         */
488        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) = 0;
489
490        /* Emit a call to an unknown function. The argument "symbol" needs to
491         * be stored in the location where the address should go. It forms
492         * a chain. The address will be patched later.
493         * Return the address of the word that has to be patched.
494         */
495        virtual int callForward(int symbol, Type* pFunc) = 0;
496
497        /* Call a function pointer. L is the number of bytes the arguments
498         * take on the stack. The address of the function is stored at
499         * location SP + l.
500         */
501        virtual void callIndirect(int l, Type* pFunc) = 0;
502
503        /* Adjust SP after returning from a function call. l is the
504         * number of bytes of arguments stored on the stack. isIndirect
505         * is true if this was an indirect call. (In which case the
506         * address of the function is stored at location SP + l.)
507         */
508        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) = 0;
509
510        /* Generate a symbol at the current PC. t is the head of a
511         * linked list of addresses to patch.
512         */
513        virtual void gsym(int t) = 0;
514
515        /* Resolve a forward reference function at the current PC.
516         * t is the head of a
517         * linked list of addresses to patch.
518         * (Like gsym, but using absolute address, not PC relative address.)
519         */
520        virtual void resolveForward(int t) = 0;
521
522        /*
523         * Do any cleanup work required at the end of a compile.
524         * For example, an instruction cache might need to be
525         * invalidated.
526         * Return non-zero if there is an error.
527         */
528        virtual int finishCompile() = 0;
529
530        /**
531         * Adjust relative branches by this amount.
532         */
533        virtual int jumpOffset() = 0;
534
535        /**
536         * Memory alignment (in bytes) for this type of data
537         */
538        virtual size_t alignmentOf(Type* type) = 0;
539
540        /**
541         * Array element alignment (in bytes) for this type of data.
542         */
543        virtual size_t sizeOf(Type* type) = 0;
544
545        virtual Type* getR0Type() {
546            return mExpressionStack.back().pType;
547        }
548
549        virtual ExpressionType getR0ExpressionType() {
550            return mExpressionStack.back().et;
551        }
552
553        virtual void setR0ExpressionType(ExpressionType et) {
554            mExpressionStack.back().et = et;
555        }
556
557        virtual size_t getExpressionStackDepth() {
558            return mExpressionStack.size();
559        }
560
561        virtual void forceR0RVal() {
562            if (getR0ExpressionType() == ET_LVALUE) {
563                loadR0FromR0();
564            }
565        }
566
567    protected:
568        /*
569         * Output a byte. Handles all values, 0..ff.
570         */
571        void ob(int n) {
572            pCodeBuf->ob(n);
573        }
574
575        void o4(int data) {
576            pCodeBuf->o4(data);
577        }
578
579        intptr_t getBase() {
580            return (intptr_t) pCodeBuf->getBase();
581        }
582
583        intptr_t getPC() {
584            return pCodeBuf->getPC();
585        }
586
587        intptr_t getSize() {
588            return pCodeBuf->getSize();
589        }
590
591        void flush() {
592            pCodeBuf->flush();
593        }
594
595        void error(const char* fmt,...) {
596            va_list ap;
597            va_start(ap, fmt);
598            mErrorSink->verror(fmt, ap);
599            va_end(ap);
600        }
601
602        void assertImpl(bool test, int line) {
603            if (!test) {
604                error("code generator assertion failed at line %s:%d.", __FILE__, line);
605                LOGD("code generator assertion failed at line %s:%d.", __FILE__, line);
606                * (char*) 0 = 0;
607            }
608        }
609
610        void setR0Type(Type* pType) {
611            assert(pType != NULL);
612            mExpressionStack.back().pType = pType;
613            mExpressionStack.back().et = ET_RVALUE;
614        }
615
616        void setR0Type(Type* pType, ExpressionType et) {
617            assert(pType != NULL);
618            mExpressionStack.back().pType = pType;
619            mExpressionStack.back().et = et;
620        }
621
622        Type* getTOSType() {
623            return mExpressionStack[mExpressionStack.size()-2].pType;
624        }
625
626        void pushType() {
627            if (mExpressionStack.size()) {
628                mExpressionStack.push_back(mExpressionStack.back());
629            } else {
630                mExpressionStack.push_back(ExpressionValue());
631            }
632
633        }
634
635        void overType() {
636            size_t size = mExpressionStack.size();
637            if (size >= 2) {
638                mExpressionStack.push_back(mExpressionStack.back());
639                mExpressionStack[size-1] = mExpressionStack[size-2];
640                mExpressionStack[size-2] = mExpressionStack[size];
641            }
642        }
643
644        void popType() {
645            mExpressionStack.pop_back();
646        }
647
648        bool bitsSame(Type* pA, Type* pB) {
649            return collapseType(pA->tag) == collapseType(pB->tag);
650        }
651
652        TypeTag collapseType(TypeTag tag) {
653            static const TypeTag collapsedTag[] = {
654                    TY_INT,
655                    TY_INT,
656                    TY_INT,
657                    TY_VOID,
658                    TY_FLOAT,
659                    TY_DOUBLE,
660                    TY_INT,
661                    TY_INT,
662                    TY_VOID,
663                    TY_VOID,
664                    TY_VOID
665                };
666            return collapsedTag[tag];
667        }
668
669        TypeTag collapseTypeR0() {
670            return collapseType(getR0Type()->tag);
671        }
672
673        static bool isFloatType(Type* pType) {
674            return isFloatTag(pType->tag);
675        }
676
677        static bool isFloatTag(TypeTag tag) {
678            return tag == TY_FLOAT || tag == TY_DOUBLE;
679        }
680
681        static bool isPointerType(Type* pType) {
682            return isPointerTag(pType->tag);
683        }
684
685        static bool isPointerTag(TypeTag tag) {
686            return tag == TY_POINTER || tag == TY_ARRAY;
687        }
688
689        Type* getPointerArithmeticResultType(Type* a, Type* b) {
690            TypeTag aTag = a->tag;
691            TypeTag bTag = b->tag;
692            if (aTag == TY_POINTER) {
693                return a;
694            }
695            if (bTag == TY_POINTER) {
696                return b;
697            }
698            if (aTag == TY_ARRAY) {
699                return a->pTail;
700            }
701            if (bTag == TY_ARRAY) {
702                return b->pTail;
703            }
704            return NULL;
705        }
706        Type* mkpInt;
707
708    private:
709        Vector<ExpressionValue> mExpressionStack;
710        ICodeBuf* pCodeBuf;
711        ErrorSink* mErrorSink;
712    };
713
714#ifdef PROVIDE_ARM_CODEGEN
715
716    static size_t rotateRight(size_t n, size_t rotate) {
717        return (n >> rotate) | (n << (32 - rotate));
718    }
719
720    static size_t rotateLeft(size_t n, size_t rotate) {
721        return (n << rotate) | (n >> (32 - rotate));
722    }
723
724    static bool encode12BitImmediate(size_t immediate, size_t* pResult) {
725        for(size_t i = 0; i < 16; i++) {
726            size_t rotate = i * 2;
727            size_t mask = rotateRight(0xff, rotate);
728            if ((immediate | mask) == mask) {
729                size_t bits8 = rotateLeft(immediate, rotate);
730                // assert(bits8 <= 0xff);
731                *pResult = (i << 8) | bits8;
732                return true;
733            }
734        }
735        return false;
736    }
737
738    static size_t decode12BitImmediate(size_t immediate) {
739        size_t data = immediate & 0xff;
740        size_t rotate = 2 * ((immediate >> 8) & 0xf);
741        return rotateRight(data, rotate);
742    }
743
744    static bool isPowerOfTwo(size_t n) {
745        return (n != 0) & ((n & (n-1)) == 0);
746    }
747
748    static size_t log2(size_t n) {
749        int result = 0;
750        while (n >>= 1) {
751            result++;
752        }
753        return result;
754    }
755
756    class ARMCodeBuf : public ICodeBuf {
757        ICodeBuf* mpBase;
758        ErrorSink* mErrorSink;
759
760        class CircularQueue {
761            static const int SIZE = 16; // Must be power of 2
762            static const int MASK = SIZE-1;
763            unsigned int mBuf[SIZE];
764            int mHead;
765            int mCount;
766
767        public:
768            CircularQueue() {
769                mHead = 0;
770                mCount = 0;
771            }
772
773            void pushBack(unsigned int data) {
774                mBuf[(mHead + mCount) & MASK] = data;
775                mCount += 1;
776            }
777
778            unsigned int popFront() {
779                unsigned int result = mBuf[mHead];
780                mHead = (mHead + 1) & MASK;
781                mCount -= 1;
782                return result;
783            }
784
785            void popBack(int n) {
786                mCount -= n;
787            }
788
789            inline int count() {
790                return mCount;
791            }
792
793            bool empty() {
794                return mCount == 0;
795            }
796
797            bool full() {
798                return mCount == SIZE;
799            }
800
801            // The valid indexes are 1 - count() to 0
802            unsigned int operator[](int i) {
803                return mBuf[(mHead + mCount + i) & MASK];
804            }
805        };
806
807        CircularQueue mQ;
808
809        void error(const char* fmt,...) {
810            va_list ap;
811            va_start(ap, fmt);
812            mErrorSink->verror(fmt, ap);
813            va_end(ap);
814        }
815
816        void flush() {
817            while (!mQ.empty()) {
818                mpBase->o4(mQ.popFront());
819            }
820            mpBase->flush();
821        }
822
823    public:
824        ARMCodeBuf(ICodeBuf* pBase) {
825            mpBase = pBase;
826        }
827
828        virtual ~ARMCodeBuf() {
829            delete mpBase;
830        }
831
832        void init(int size) {
833            mpBase->init(size);
834        }
835
836        void setErrorSink(ErrorSink* pErrorSink) {
837            mErrorSink = pErrorSink;
838            mpBase->setErrorSink(pErrorSink);
839        }
840
841        void o4(int n) {
842            if (mQ.full()) {
843                mpBase->o4(mQ.popFront());
844            }
845            mQ.pushBack(n);
846
847#ifndef DISABLE_ARM_PEEPHOLE
848            // Peephole check
849            bool didPeep;
850            do {
851                static const unsigned int opMask = 0x01e00000;
852                static const unsigned int immediateMask = 0x00000fff;
853                static const unsigned int BMask = 0x00400000;
854                didPeep = false;
855                if (mQ.count() >= 4) {
856
857                    // Operand by a small constant
858                    // push;mov #imm;pop;op ==> op #imm
859
860                    if (mQ[-4] == 0xe92d0001  && // stmfd    r13!, {r0}
861                        (mQ[-3] & ~immediateMask) == 0xe3a00000  && // mov    r0, #X
862                        mQ[-2] == 0xe8bd0002  && // ldmea    r13!, {r1}
863                        (mQ[-1] & ~opMask) == (0xe0810000 & ~opMask)) {  // OP    r0, r1, r0
864                        unsigned int movConst = mQ[-3];
865                        unsigned int op = mQ[-1];
866                        unsigned int combined = 0xe2000000 | (op & opMask) | (movConst & immediateMask);
867                        // fprintf(stderr, "op %x movConst %x combined %x\n", op, movConst, combined);
868                        if (! (combined == 0xe2800000 || combined == 0xe2400000)) { // add/sub #0
869                            mQ.popBack(4);
870                            mQ.pushBack(combined);
871                            didPeep = true;
872                        } else {
873                            mQ.popBack(4);
874                            didPeep = true;
875                        }
876                    }
877                }
878
879                // Load local variable
880                // sub r0,r11,#imm;ldr/ldrb r0,[r0]  ==> ldr/ldrb r0, [r11,#-imm]
881                if (mQ.count() >= 2) {
882                    if ((mQ[-2] & ~immediateMask) == 0xe24b0000) { // sub r0,r11,#imm
883                        const unsigned int encodedImmediate = mQ[-2] & immediateMask;
884                        const unsigned int ld = mQ[-1];
885                        if ((ld & ~BMask) == 0xe5900000) { // ldr{b} r0, [r0]
886                            unsigned int combined = encodedImmediate | (0xE51B0000 | (ld & BMask)); // ldr r0, [r11, #-0]
887                            mQ.popBack(2);
888                            mQ.pushBack(combined);
889                            didPeep = true;
890                        } else if (ld == 0xedd07a00) {  // ldcl    p10, c7, [r0, #0x000]
891                            unsigned int decodedImmediate = decode12BitImmediate(encodedImmediate);
892                            if (decodedImmediate <= 1020 && ((decodedImmediate & 3) == 0)) {
893                                unsigned int combined = (decodedImmediate >> 2) | 0xed5b7a00; // ldcl    p10, c7, [r11, #-0]
894                                mQ.popBack(2);
895                                mQ.pushBack(combined);
896                                didPeep = true;
897                            }
898                        }
899                    }
900                }
901
902                // Constant array lookup
903
904                if (mQ.count() >= 6 &&
905                    mQ[-6] == 0xe92d0001 && // stmfd r13!, {r0}
906                    (mQ[-5] & ~immediateMask)== 0xe3a00000 && // mov r0, #0x00000001
907                    mQ[-4] == 0xe8bd0002 && // ldmea r13!, {r1}
908                    (mQ[-3] & ~immediateMask)== 0xe3a02000 && // mov r2, #0x00000004
909                    mQ[-2] == 0xe0000092 && // mul r0, r2, r0
910                    mQ[-1] == 0xe0810000) { // add r0, r1, r0
911                    unsigned int mov1 = mQ[-5];
912                    unsigned int mov2 = mQ[-3];
913                    unsigned int const1 = decode12BitImmediate(mov1);
914                    unsigned int const2 = decode12BitImmediate(mov2);
915                    unsigned int comboConst = const1 * const2;
916                    size_t immediate = 0;
917                    if (encode12BitImmediate(comboConst, &immediate)) {
918                        mQ.popBack(6);
919                        unsigned int add = immediate | 0xE2800000; // add r0, r0, #n
920                        if (comboConst) {
921                            mQ.pushBack(add);
922                        }
923                        didPeep = true;
924                    }
925                }
926
927                // Pointer arithmetic with a stride that is a power of two
928
929                if (mQ.count() >= 3 &&
930                    (mQ[-3] & ~ immediateMask) == 0xe3a02000 &&  // mov    r2, #stride
931                     mQ[-2] == 0xe0000092 && // mul    r0, r2, r0
932                     mQ[-1] == 0xe0810000) {  // add r0, r1, r0
933                    int stride = decode12BitImmediate(mQ[-3]);
934                    if (isPowerOfTwo(stride)) {
935                        mQ.popBack(3);
936                        unsigned int add = 0xe0810000 | (log2(stride) << 7); // add r0, r1, r0, LSL #log2(stride)
937                        mQ.pushBack(add);
938                        didPeep = true;
939                    }
940                }
941
942            } while (didPeep);
943#endif
944        }
945
946        void ob(int n) {
947            error("ob() not supported.");
948        }
949
950        void* getBase() {
951            flush();
952            return mpBase->getBase();
953        }
954
955        intptr_t getSize() {
956            flush();
957            return mpBase->getSize();
958        }
959
960        intptr_t getPC() {
961            flush();
962            return mpBase->getPC();
963        }
964    };
965
966    class ARMCodeGenerator : public CodeGenerator {
967    public:
968        ARMCodeGenerator() {
969#ifdef ARM_USE_VFP
970            // LOGD("Using ARM VFP hardware floating point.");
971#else
972            // LOGD("Using ARM soft floating point.");
973#endif
974        }
975
976        virtual ~ARMCodeGenerator() {}
977
978        /* returns address to patch with local variable size
979        */
980        virtual int functionEntry(Type* pDecl) {
981            mStackUse = 0;
982            // sp -> arg4 arg5 ...
983            // Push our register-based arguments back on the stack
984            int regArgCount = calcRegArgCount(pDecl);
985            if (regArgCount > 0) {
986                mStackUse += regArgCount * 4;
987                o4(0xE92D0000 | ((1 << regArgCount) - 1)); // stmfd    sp!, {}
988            }
989            // sp -> arg0 arg1 ...
990            o4(0xE92D4800); // stmfd sp!, {fp, lr}
991            mStackUse += 2 * 4;
992            // sp, fp -> oldfp, retadr, arg0 arg1 ....
993            o4(0xE1A0B00D); // mov    fp, sp
994            LOG_STACK("functionEntry: %d\n", mStackUse);
995            int pc = getPC();
996            o4(0xE24DD000); // sub    sp, sp, # <local variables>
997            // We don't know how many local variables we are going to use,
998            // but we will round the allocation up to a multiple of
999            // STACK_ALIGNMENT, so it won't affect the stack alignment.
1000            return pc;
1001        }
1002
1003        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
1004            // Round local variable size up to a multiple of stack alignment
1005            localVariableSize = ((localVariableSize + STACK_ALIGNMENT - 1) /
1006                STACK_ALIGNMENT) * STACK_ALIGNMENT;
1007            // Patch local variable allocation code:
1008            if (localVariableSize < 0 || localVariableSize > 255) {
1009                error("localVariables out of range: %d", localVariableSize);
1010            }
1011            *(char*) (localVariableAddress) = localVariableSize;
1012
1013#ifdef ARM_USE_VFP
1014            {
1015                Type* pReturnType = pDecl->pHead;
1016                switch(pReturnType->tag) {
1017                case TY_FLOAT:
1018                    o4(0xEE170A90); // fmrs    r0, s15
1019                    break;
1020                case TY_DOUBLE:
1021                    o4(0xEC510B17); // fmrrd r0, r1, d7
1022                    break;
1023                default:
1024                    break;
1025                }
1026            }
1027#endif
1028
1029            // sp -> locals .... fp -> oldfp, retadr, arg0, arg1, ...
1030            o4(0xE1A0E00B); // mov lr, fp
1031            o4(0xE59BB000); // ldr fp, [fp]
1032            o4(0xE28ED004); // add sp, lr, #4
1033            // sp -> retadr, arg0, ...
1034            o4(0xE8BD4000); // ldmfd    sp!, {lr}
1035            // sp -> arg0 ....
1036
1037            // We store the PC into the lr so we can adjust the sp before
1038            // returning. We need to pull off the registers we pushed
1039            // earlier. We don't need to actually store them anywhere,
1040            // just adjust the stack.
1041            int regArgCount = calcRegArgCount(pDecl);
1042            if (regArgCount) {
1043                o4(0xE28DD000 | (regArgCount << 2)); // add sp, sp, #argCount << 2
1044            }
1045            o4(0xE12FFF1E); // bx lr
1046        }
1047
1048        /* load immediate value */
1049        virtual void li(int t) {
1050            liReg(t, 0);
1051            setR0Type(mkpInt);
1052        }
1053
1054        virtual void loadFloat(int address, Type* pType) {
1055            setR0Type(pType);
1056            // Global, absolute address
1057            o4(0xE59F0000); //        ldr r0, .L1
1058            o4(0xEA000000); //        b .L99
1059            o4(address);         // .L1:   .word ea
1060                                 // .L99:
1061
1062            switch (pType->tag) {
1063            case TY_FLOAT:
1064#ifdef ARM_USE_VFP
1065                o4(0xEDD07A00);      // flds    s15, [r0]
1066#else
1067                o4(0xE5900000);      // ldr r0, [r0]
1068#endif
1069                break;
1070            case TY_DOUBLE:
1071#ifdef ARM_USE_VFP
1072                o4(0xED907B00);      // fldd    d7, [r0]
1073#else
1074                o4(0xE1C000D0);      // ldrd r0, [r0]
1075#endif
1076                break;
1077            default:
1078                assert(false);
1079                break;
1080            }
1081        }
1082
1083
1084        virtual void addStructOffsetR0(int offset, Type* pType) {
1085            if (offset) {
1086                size_t immediate = 0;
1087                if (encode12BitImmediate(offset, &immediate)) {
1088                    o4(0xE2800000 | immediate); // add    r0, r0, #offset
1089                } else {
1090                    error("structure offset out of range: %d", offset);
1091                }
1092            }
1093            setR0Type(pType, ET_LVALUE);
1094        }
1095
1096        virtual int gjmp(int t) {
1097            int pc = getPC();
1098            o4(0xEA000000 | encodeAddress(t)); // b .L33
1099            return pc;
1100        }
1101
1102        /* l = 0: je, l == 1: jne */
1103        virtual int gtst(bool l, int t) {
1104            Type* pR0Type = getR0Type();
1105            TypeTag tagR0 = pR0Type->tag;
1106            switch(tagR0) {
1107                case TY_FLOAT:
1108#ifdef ARM_USE_VFP
1109                    o4(0xEEF57A40); // fcmpzs    s15
1110                    o4(0xEEF1FA10); // fmstat
1111#else
1112                    callRuntime((void*) runtime_is_non_zero_f);
1113                    o4(0xE3500000); // cmp r0,#0
1114#endif
1115                    break;
1116                case TY_DOUBLE:
1117#ifdef ARM_USE_VFP
1118                    o4(0xEEB57B40); // fcmpzd    d7
1119                    o4(0xEEF1FA10); // fmstat
1120#else
1121                    callRuntime((void*) runtime_is_non_zero_d);
1122                    o4(0xE3500000); // cmp r0,#0
1123#endif
1124                    break;
1125                default:
1126                    o4(0xE3500000); // cmp r0,#0
1127                    break;
1128            }
1129            int branch = l ? 0x1A000000 : 0x0A000000; // bne : beq
1130            int pc = getPC();
1131            o4(branch | encodeAddress(t));
1132            return pc;
1133        }
1134
1135        virtual void gcmp(int op) {
1136            Type* pR0Type = getR0Type();
1137            Type* pTOSType = getTOSType();
1138            TypeTag tagR0 = collapseType(pR0Type->tag);
1139            TypeTag tagTOS = collapseType(pTOSType->tag);
1140            if (tagR0 == TY_INT && tagTOS == TY_INT) {
1141                setupIntPtrArgs();
1142                o4(0xE1510000); // cmp r1, r1
1143                switch(op) {
1144                case OP_EQUALS:
1145                    o4(0x03A00001); // moveq r0,#1
1146                    o4(0x13A00000); // movne r0,#0
1147                    break;
1148                case OP_NOT_EQUALS:
1149                    o4(0x03A00000); // moveq r0,#0
1150                    o4(0x13A00001); // movne r0,#1
1151                    break;
1152                case OP_LESS_EQUAL:
1153                    o4(0xD3A00001); // movle r0,#1
1154                    o4(0xC3A00000); // movgt r0,#0
1155                    break;
1156                case OP_GREATER:
1157                    o4(0xD3A00000); // movle r0,#0
1158                    o4(0xC3A00001); // movgt r0,#1
1159                    break;
1160                case OP_GREATER_EQUAL:
1161                    o4(0xA3A00001); // movge r0,#1
1162                    o4(0xB3A00000); // movlt r0,#0
1163                    break;
1164                case OP_LESS:
1165                    o4(0xA3A00000); // movge r0,#0
1166                    o4(0xB3A00001); // movlt r0,#1
1167                    break;
1168                default:
1169                    error("Unknown comparison op %d", op);
1170                    break;
1171                }
1172            } else if (tagR0 == TY_DOUBLE || tagTOS == TY_DOUBLE) {
1173                setupDoubleArgs();
1174#ifdef ARM_USE_VFP
1175                o4(0xEEB46BC7); //         fcmped    d6, d7
1176                   o4(0xEEF1FA10); // fmstat
1177                switch(op) {
1178                case OP_EQUALS:
1179                    o4(0x03A00001); // moveq r0,#1
1180                    o4(0x13A00000); // movne r0,#0
1181                    break;
1182                case OP_NOT_EQUALS:
1183                    o4(0x03A00000); // moveq r0,#0
1184                    o4(0x13A00001); // movne r0,#1
1185                    break;
1186                case OP_LESS_EQUAL:
1187                    o4(0xD3A00001); // movle r0,#1
1188                    o4(0xC3A00000); // movgt r0,#0
1189                    break;
1190                case OP_GREATER:
1191                    o4(0xD3A00000); // movle r0,#0
1192                    o4(0xC3A00001); // movgt r0,#1
1193                    break;
1194                case OP_GREATER_EQUAL:
1195                    o4(0xA3A00001); // movge r0,#1
1196                    o4(0xB3A00000); // movlt r0,#0
1197                    break;
1198                case OP_LESS:
1199                    o4(0xA3A00000); // movge r0,#0
1200                    o4(0xB3A00001); // movlt r0,#1
1201                    break;
1202                default:
1203                    error("Unknown comparison op %d", op);
1204                    break;
1205                }
1206#else
1207                switch(op) {
1208                    case OP_EQUALS:
1209                        callRuntime((void*) runtime_cmp_eq_dd);
1210                        break;
1211                    case OP_NOT_EQUALS:
1212                        callRuntime((void*) runtime_cmp_ne_dd);
1213                        break;
1214                    case OP_LESS_EQUAL:
1215                        callRuntime((void*) runtime_cmp_le_dd);
1216                        break;
1217                    case OP_GREATER:
1218                        callRuntime((void*) runtime_cmp_gt_dd);
1219                        break;
1220                    case OP_GREATER_EQUAL:
1221                        callRuntime((void*) runtime_cmp_ge_dd);
1222                        break;
1223                    case OP_LESS:
1224                        callRuntime((void*) runtime_cmp_lt_dd);
1225                        break;
1226                    default:
1227                        error("Unknown comparison op %d", op);
1228                        break;
1229                }
1230#endif
1231            } else {
1232                setupFloatArgs();
1233#ifdef ARM_USE_VFP
1234                o4(0xEEB47AE7); // fcmpes s14, s15
1235                   o4(0xEEF1FA10); // fmstat
1236                switch(op) {
1237                case OP_EQUALS:
1238                    o4(0x03A00001); // moveq r0,#1
1239                    o4(0x13A00000); // movne r0,#0
1240                    break;
1241                case OP_NOT_EQUALS:
1242                    o4(0x03A00000); // moveq r0,#0
1243                    o4(0x13A00001); // movne r0,#1
1244                    break;
1245                case OP_LESS_EQUAL:
1246                    o4(0xD3A00001); // movle r0,#1
1247                    o4(0xC3A00000); // movgt r0,#0
1248                    break;
1249                case OP_GREATER:
1250                    o4(0xD3A00000); // movle r0,#0
1251                    o4(0xC3A00001); // movgt r0,#1
1252                    break;
1253                case OP_GREATER_EQUAL:
1254                    o4(0xA3A00001); // movge r0,#1
1255                    o4(0xB3A00000); // movlt r0,#0
1256                    break;
1257                case OP_LESS:
1258                    o4(0xA3A00000); // movge r0,#0
1259                    o4(0xB3A00001); // movlt r0,#1
1260                    break;
1261                default:
1262                    error("Unknown comparison op %d", op);
1263                    break;
1264                }
1265#else
1266                switch(op) {
1267                    case OP_EQUALS:
1268                        callRuntime((void*) runtime_cmp_eq_ff);
1269                        break;
1270                    case OP_NOT_EQUALS:
1271                        callRuntime((void*) runtime_cmp_ne_ff);
1272                        break;
1273                    case OP_LESS_EQUAL:
1274                        callRuntime((void*) runtime_cmp_le_ff);
1275                        break;
1276                    case OP_GREATER:
1277                        callRuntime((void*) runtime_cmp_gt_ff);
1278                        break;
1279                    case OP_GREATER_EQUAL:
1280                        callRuntime((void*) runtime_cmp_ge_ff);
1281                        break;
1282                    case OP_LESS:
1283                        callRuntime((void*) runtime_cmp_lt_ff);
1284                        break;
1285                    default:
1286                        error("Unknown comparison op %d", op);
1287                        break;
1288                }
1289#endif
1290            }
1291            setR0Type(mkpInt);
1292        }
1293
1294        virtual void genOp(int op) {
1295            Type* pR0Type = getR0Type();
1296            Type* pTOSType = getTOSType();
1297            TypeTag tagR0 = pR0Type->tag;
1298            TypeTag tagTOS = pTOSType->tag;
1299            bool isFloatR0 = isFloatTag(tagR0);
1300            bool isFloatTOS = isFloatTag(tagTOS);
1301            if (!isFloatR0 && !isFloatTOS) {
1302                setupIntPtrArgs();
1303                bool isPtrR0 = isPointerTag(tagR0);
1304                bool isPtrTOS = isPointerTag(tagTOS);
1305                if (isPtrR0 || isPtrTOS) {
1306                    if (isPtrR0 && isPtrTOS) {
1307                        if (op != OP_MINUS) {
1308                            error("Unsupported pointer-pointer operation %d.", op);
1309                        }
1310                        if (! typeEqual(pR0Type, pTOSType)) {
1311                            error("Incompatible pointer types for subtraction.");
1312                        }
1313                        o4(0xE0410000); // sub     r0,r1,r0
1314                        setR0Type(mkpInt);
1315                        int size = sizeOf(pR0Type->pHead);
1316                        if (size != 1) {
1317                            pushR0();
1318                            li(size);
1319                            // TODO: Optimize for power-of-two.
1320                            genOp(OP_DIV);
1321                        }
1322                    } else {
1323                        if (! (op == OP_PLUS || (op == OP_MINUS && isPtrR0))) {
1324                            error("Unsupported pointer-scalar operation %d", op);
1325                        }
1326                        Type* pPtrType = getPointerArithmeticResultType(
1327                                pR0Type, pTOSType);
1328                        int size = sizeOf(pPtrType->pHead);
1329                        if (size != 1) {
1330                            // TODO: Optimize for power-of-two.
1331                            liReg(size, 2);
1332                            if (isPtrR0) {
1333                                o4(0x0E0010192); // mul     r1,r2,r1
1334                            } else {
1335                                o4(0x0E0000092); // mul     r0,r2,r0
1336                            }
1337                        }
1338                        switch(op) {
1339                            case OP_PLUS:
1340                            o4(0xE0810000); // add     r0,r1,r0
1341                            break;
1342                            case OP_MINUS:
1343                            o4(0xE0410000); // sub     r0,r1,r0
1344                            break;
1345                        }
1346                        setR0Type(pPtrType);
1347                    }
1348                } else {
1349                    switch(op) {
1350                        case OP_MUL:
1351                        o4(0x0E0000091); // mul     r0,r1,r0
1352                        break;
1353                        case OP_DIV:
1354                        callRuntime((void*) runtime_DIV);
1355                        break;
1356                        case OP_MOD:
1357                        callRuntime((void*) runtime_MOD);
1358                        break;
1359                        case OP_PLUS:
1360                        o4(0xE0810000); // add     r0,r1,r0
1361                        break;
1362                        case OP_MINUS:
1363                        o4(0xE0410000); // sub     r0,r1,r0
1364                        break;
1365                        case OP_SHIFT_LEFT:
1366                        o4(0xE1A00011); // lsl     r0,r1,r0
1367                        break;
1368                        case OP_SHIFT_RIGHT:
1369                        o4(0xE1A00051); // asr     r0,r1,r0
1370                        break;
1371                        case OP_BIT_AND:
1372                        o4(0xE0010000); // and     r0,r1,r0
1373                        break;
1374                        case OP_BIT_XOR:
1375                        o4(0xE0210000); // eor     r0,r1,r0
1376                        break;
1377                        case OP_BIT_OR:
1378                        o4(0xE1810000); // orr     r0,r1,r0
1379                        break;
1380                        case OP_BIT_NOT:
1381                        o4(0xE1E00000); // mvn     r0, r0
1382                        break;
1383                        default:
1384                        error("Unimplemented op %d\n", op);
1385                        break;
1386                    }
1387                }
1388            } else {
1389                Type* pResultType = tagR0 > tagTOS ? pR0Type : pTOSType;
1390                if (pResultType->tag == TY_DOUBLE) {
1391                    setupDoubleArgs();
1392
1393                    switch(op) {
1394                    case OP_MUL:
1395#ifdef ARM_USE_VFP
1396                        o4(0xEE267B07); // fmuld d7, d6, d7
1397#else
1398                        callRuntime((void*) runtime_op_mul_dd);
1399#endif
1400                        break;
1401                    case OP_DIV:
1402#ifdef ARM_USE_VFP
1403                        o4(0xEE867B07); // fdivd d7, d6, d7
1404#else
1405                        callRuntime((void*) runtime_op_div_dd);
1406#endif
1407                        break;
1408                    case OP_PLUS:
1409#ifdef ARM_USE_VFP
1410                        o4(0xEE367B07); // faddd d7, d6, d7
1411#else
1412                        callRuntime((void*) runtime_op_add_dd);
1413#endif
1414                        break;
1415                    case OP_MINUS:
1416#ifdef ARM_USE_VFP
1417                        o4(0xEE367B47); // fsubd d7, d6, d7
1418#else
1419                        callRuntime((void*) runtime_op_sub_dd);
1420#endif
1421                        break;
1422                    default:
1423                        error("Unsupported binary floating operation %d\n", op);
1424                        break;
1425                    }
1426                } else {
1427                    setupFloatArgs();
1428                    switch(op) {
1429                    case OP_MUL:
1430#ifdef ARM_USE_VFP
1431                        o4(0xEE677A27); // fmuls s15, s14, s15
1432#else
1433                        callRuntime((void*) runtime_op_mul_ff);
1434#endif
1435                        break;
1436                    case OP_DIV:
1437#ifdef ARM_USE_VFP
1438                        o4(0xEEC77A27); // fdivs s15, s14, s15
1439#else
1440                        callRuntime((void*) runtime_op_div_ff);
1441#endif
1442                        break;
1443                    case OP_PLUS:
1444#ifdef ARM_USE_VFP
1445                        o4(0xEE777A27); // fadds s15, s14, s15
1446#else
1447                        callRuntime((void*) runtime_op_add_ff);
1448#endif
1449                        break;
1450                    case OP_MINUS:
1451#ifdef ARM_USE_VFP
1452                        o4(0xEE777A67); // fsubs s15, s14, s15
1453#else
1454                        callRuntime((void*) runtime_op_sub_ff);
1455#endif
1456                        break;
1457                    default:
1458                        error("Unsupported binary floating operation %d\n", op);
1459                        break;
1460                    }
1461                }
1462                setR0Type(pResultType);
1463            }
1464        }
1465
1466        virtual void gUnaryCmp(int op) {
1467            if (op != OP_LOGICAL_NOT) {
1468                error("Unknown unary cmp %d", op);
1469            } else {
1470                Type* pR0Type = getR0Type();
1471                TypeTag tag = collapseType(pR0Type->tag);
1472                switch(tag) {
1473                    case TY_INT:
1474                        o4(0xE3A01000); // mov    r1, #0
1475                        o4(0xE1510000); // cmp r1, r0
1476                        o4(0x03A00001); // moveq r0,#1
1477                        o4(0x13A00000); // movne r0,#0
1478                        break;
1479                    case TY_FLOAT:
1480#ifdef ARM_USE_VFP
1481                        o4(0xEEF57A40); // fcmpzs s15
1482                        o4(0xEEF1FA10); // fmstat
1483                        o4(0x03A00001); // moveq r0,#1
1484                        o4(0x13A00000); // movne r0,#0
1485#else
1486                        callRuntime((void*) runtime_is_zero_f);
1487#endif
1488                        break;
1489                    case TY_DOUBLE:
1490#ifdef ARM_USE_VFP
1491                        o4(0xEEB57B40); // fcmpzd d7
1492                        o4(0xEEF1FA10); // fmstat
1493                        o4(0x03A00001); // moveq r0,#1
1494                        o4(0x13A00000); // movne r0,#0
1495#else
1496                        callRuntime((void*) runtime_is_zero_d);
1497#endif
1498                        break;
1499                    default:
1500                        error("gUnaryCmp unsupported type");
1501                        break;
1502                }
1503            }
1504            setR0Type(mkpInt);
1505        }
1506
1507        virtual void genUnaryOp(int op) {
1508            Type* pR0Type = getR0Type();
1509            TypeTag tag = collapseType(pR0Type->tag);
1510            switch(tag) {
1511                case TY_INT:
1512                    switch(op) {
1513                    case OP_MINUS:
1514                        o4(0xE3A01000);  // mov    r1, #0
1515                        o4(0xE0410000);  // sub     r0,r1,r0
1516                        break;
1517                    case OP_BIT_NOT:
1518                        o4(0xE1E00000);  // mvn     r0, r0
1519                        break;
1520                    default:
1521                        error("Unknown unary op %d\n", op);
1522                        break;
1523                    }
1524                    break;
1525                case TY_FLOAT:
1526                case TY_DOUBLE:
1527                    switch (op) {
1528                        case OP_MINUS:
1529                            if (tag == TY_FLOAT) {
1530#ifdef ARM_USE_VFP
1531                                o4(0xEEF17A67); // fnegs    s15, s15
1532#else
1533                                callRuntime((void*) runtime_op_neg_f);
1534#endif
1535                            } else {
1536#ifdef ARM_USE_VFP
1537                                o4(0xEEB17B47); // fnegd    d7, d7
1538#else
1539                                callRuntime((void*) runtime_op_neg_d);
1540#endif
1541                            }
1542                            break;
1543                        case OP_BIT_NOT:
1544                            error("Can't apply '~' operator to a float or double.");
1545                            break;
1546                        default:
1547                            error("Unknown unary op %d\n", op);
1548                            break;
1549                        }
1550                    break;
1551                default:
1552                    error("genUnaryOp unsupported type");
1553                    break;
1554            }
1555        }
1556
1557        virtual void pushR0() {
1558            Type* pR0Type = getR0Type();
1559            TypeTag r0ct = collapseType(pR0Type->tag);
1560
1561#ifdef ARM_USE_VFP
1562            switch (r0ct ) {
1563            case TY_FLOAT:
1564                o4(0xED6D7A01); // fstmfds   sp!,{s15}
1565                mStackUse += 4;
1566                break;
1567            case TY_DOUBLE:
1568                o4(0xED2D7B02); // fstmfdd   sp!,{d7}
1569                mStackUse += 8;
1570                break;
1571            default:
1572                o4(0xE92D0001);  // stmfd   sp!,{r0}
1573                mStackUse += 4;
1574            }
1575#else
1576
1577            if (r0ct != TY_DOUBLE) {
1578                    o4(0xE92D0001);  // stmfd   sp!,{r0}
1579                    mStackUse += 4;
1580            } else {
1581                    o4(0xE92D0003);  // stmfd   sp!,{r0,r1}
1582                    mStackUse += 8;
1583            }
1584#endif
1585            pushType();
1586            LOG_STACK("pushR0: %d\n", mStackUse);
1587        }
1588
1589        virtual void over() {
1590            // We know it's only used for int-ptr ops (++/--)
1591
1592            Type* pR0Type = getR0Type();
1593            TypeTag r0ct = collapseType(pR0Type->tag);
1594
1595            Type* pTOSType = getTOSType();
1596            TypeTag tosct = collapseType(pTOSType->tag);
1597
1598            assert (r0ct == TY_INT  && tosct == TY_INT);
1599
1600            o4(0xE8BD0002);  // ldmfd   sp!,{r1}
1601            o4(0xE92D0001);  // stmfd   sp!,{r0}
1602            o4(0xE92D0002);  // stmfd   sp!,{r1}
1603            overType();
1604            mStackUse += 4;
1605        }
1606
1607        virtual void popR0() {
1608            Type* pTOSType = getTOSType();
1609            TypeTag tosct = collapseType(pTOSType->tag);
1610#ifdef ARM_USE_VFP
1611            if (tosct == TY_FLOAT || tosct == TY_DOUBLE) {
1612                error("Unsupported popR0 float/double");
1613            }
1614#endif
1615            switch (tosct){
1616                case TY_INT:
1617                case TY_FLOAT:
1618                    o4(0xE8BD0001);  // ldmfd   sp!,{r0}
1619                    mStackUse -= 4;
1620                    break;
1621                case TY_DOUBLE:
1622                    o4(0xE8BD0003);  // ldmfd   sp!,{r0, r1}  // Restore R0
1623                        mStackUse -= 8;
1624                    break;
1625                default:
1626                    error("Can't pop this type.");
1627                    break;
1628            }
1629            popType();
1630            LOG_STACK("popR0: %d\n", mStackUse);
1631        }
1632
1633        virtual void storeR0ToTOS() {
1634            Type* pPointerType = getTOSType();
1635            assert(pPointerType->tag == TY_POINTER);
1636            Type* pDestType = pPointerType->pHead;
1637            convertR0(pDestType);
1638            o4(0xE8BD0004);  // ldmfd   sp!,{r2}
1639            popType();
1640            mStackUse -= 4;
1641            switch (pDestType->tag) {
1642                case TY_POINTER:
1643                case TY_INT:
1644                    o4(0xE5820000); // str r0, [r2]
1645                    break;
1646                case TY_FLOAT:
1647#ifdef ARM_USE_VFP
1648                    o4(0xEDC27A00); // fsts    s15, [r2, #0]
1649#else
1650                    o4(0xE5820000); // str r0, [r2]
1651#endif
1652                    break;
1653                case TY_SHORT:
1654                    o4(0xE1C200B0); // strh r0, [r2]
1655                    break;
1656                case TY_CHAR:
1657                    o4(0xE5C20000); // strb r0, [r2]
1658                    break;
1659                case TY_DOUBLE:
1660#ifdef ARM_USE_VFP
1661                    o4(0xED827B00); // fstd    d7, [r2, #0]
1662#else
1663                    o4(0xE1C200F0); // strd r0, [r2]
1664#endif
1665                    break;
1666                case TY_STRUCT:
1667                {
1668                    int size = sizeOf(pDestType);
1669                    if (size > 0) {
1670                        liReg(size, 1);
1671                        callRuntime((void*) runtime_structCopy);
1672                    }
1673                }
1674                    break;
1675                default:
1676                    error("storeR0ToTOS: unimplemented type %d",
1677                            pDestType->tag);
1678                    break;
1679            }
1680        }
1681
1682        virtual void loadR0FromR0() {
1683            Type* pPointerType = getR0Type();
1684            assert(pPointerType->tag == TY_POINTER);
1685            Type* pNewType = pPointerType->pHead;
1686            TypeTag tag = pNewType->tag;
1687            switch (tag) {
1688                case TY_POINTER:
1689                case TY_INT:
1690                    o4(0xE5900000); // ldr r0, [r0]
1691                    break;
1692                case TY_FLOAT:
1693#ifdef ARM_USE_VFP
1694                    o4(0xEDD07A00); // flds    s15, [r0, #0]
1695#else
1696                    o4(0xE5900000); // ldr r0, [r0]
1697#endif
1698                    break;
1699                case TY_SHORT:
1700                    o4(0xE1D000F0); // ldrsh r0, [r0]
1701                    break;
1702                case TY_CHAR:
1703                    o4(0xE5D00000); // ldrb r0, [r0]
1704                    break;
1705                case TY_DOUBLE:
1706#ifdef ARM_USE_VFP
1707                    o4(0xED907B00); // fldd    d7, [r0, #0]
1708#else
1709                    o4(0xE1C000D0); // ldrd   r0, [r0]
1710#endif
1711                    break;
1712                case TY_ARRAY:
1713                    pNewType = pNewType->pTail;
1714                    break;
1715                case TY_STRUCT:
1716                    break;
1717                default:
1718                    error("loadR0FromR0: unimplemented type %d", tag);
1719                    break;
1720            }
1721            setR0Type(pNewType);
1722        }
1723
1724        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
1725            if (ea > -LOCAL && ea < LOCAL) {
1726                // Local, fp relative
1727
1728                size_t immediate = 0;
1729                bool inRange = false;
1730                if (ea < 0) {
1731                    inRange = encode12BitImmediate(-ea, &immediate);
1732                    o4(0xE24B0000 | immediate); // sub    r0, fp, #ea
1733                } else {
1734                    inRange = encode12BitImmediate(ea, &immediate);
1735                    o4(0xE28B0000 | immediate); // add    r0, fp, #ea
1736                }
1737                if (! inRange) {
1738                    error("Offset out of range: %08x", ea);
1739                }
1740            } else {
1741                // Global, absolute.
1742                o4(0xE59F0000); //        ldr    r0, .L1
1743                o4(0xEA000000); //        b .L99
1744                o4(ea);         // .L1:   .word 0
1745                                // .L99:
1746            }
1747            setR0Type(pPointerType, et);
1748        }
1749
1750        virtual int leaForward(int ea, Type* pPointerType) {
1751            setR0Type(pPointerType);
1752            int result = ea;
1753            int pc = getPC();
1754            int offset = 0;
1755            if (ea) {
1756                offset = (pc - ea - 8) >> 2;
1757                if ((offset & 0xffff) != offset) {
1758                    error("function forward reference out of bounds");
1759                }
1760            } else {
1761                offset = 0;
1762            }
1763            o4(0xE59F0000 | offset); //        ldr    r0, .L1
1764
1765            if (ea == 0) {
1766                o4(0xEA000000); //        b .L99
1767                result = getPC();
1768                o4(ea);         // .L1:   .word 0
1769                            // .L99:
1770            }
1771            return result;
1772        }
1773
1774        virtual void convertR0Imp(Type* pType, bool isCast){
1775            Type* pR0Type = getR0Type();
1776            if (isPointerType(pType) && isPointerType(pR0Type)) {
1777                Type* pA = pR0Type;
1778                Type* pB = pType;
1779                // Array decays to pointer
1780                if (pA->tag == TY_ARRAY && pB->tag == TY_POINTER) {
1781                    pA = pA->pTail;
1782                }
1783                if (! (typeEqual(pA, pB)
1784                        || pB->pHead->tag == TY_VOID
1785                        || (pA->tag == TY_POINTER && pB->tag == TY_POINTER && isCast)
1786                    )) {
1787                    error("Incompatible pointer or array types");
1788                }
1789            } else if (bitsSame(pType, pR0Type)) {
1790                // do nothing special
1791            } else {
1792                TypeTag r0Tag = collapseType(pR0Type->tag);
1793                TypeTag destTag = collapseType(pType->tag);
1794                if (r0Tag == TY_INT) {
1795                    if (destTag == TY_FLOAT) {
1796#ifdef ARM_USE_VFP
1797                        o4(0xEE070A90); // fmsr    s15, r0
1798                        o4(0xEEF87AE7); // fsitos s15, s15
1799
1800#else
1801                        callRuntime((void*) runtime_int_to_float);
1802#endif
1803                    } else {
1804                        assert(destTag == TY_DOUBLE);
1805#ifdef ARM_USE_VFP
1806                        o4(0xEE070A90); // fmsr s15, r0
1807                        o4(0xEEB87BE7); // fsitod d7, s15
1808
1809#else
1810                        callRuntime((void*) runtime_int_to_double);
1811#endif
1812                    }
1813                } else if (r0Tag == TY_FLOAT) {
1814                    if (destTag == TY_INT) {
1815#ifdef ARM_USE_VFP
1816                        o4(0xEEFD7AE7); // ftosizs s15, s15
1817                        o4(0xEE170A90); // fmrs r0, s15
1818#else
1819                        callRuntime((void*) runtime_float_to_int);
1820#endif
1821                    } else {
1822                        assert(destTag == TY_DOUBLE);
1823#ifdef ARM_USE_VFP
1824                        o4(0xEEB77AE7); // fcvtds    d7, s15
1825#else
1826                        callRuntime((void*) runtime_float_to_double);
1827#endif
1828                    }
1829                } else {
1830                    if (r0Tag == TY_DOUBLE) {
1831                        if (destTag == TY_INT) {
1832#ifdef ARM_USE_VFP
1833                            o4(0xEEFD7BC7); // ftosizd s15, d7
1834                            o4(0xEE170A90); // fmrs r0, s15
1835#else
1836                            callRuntime((void*) runtime_double_to_int);
1837#endif
1838                        } else {
1839                            if(destTag == TY_FLOAT) {
1840#ifdef ARM_USE_VFP
1841                                o4(0xEEF77BC7); // fcvtsd s15, d7
1842#else
1843                                callRuntime((void*) runtime_double_to_float);
1844#endif
1845                            } else {
1846                                incompatibleTypes(pR0Type, pType);
1847                            }
1848                        }
1849                    } else {
1850                        incompatibleTypes(pR0Type, pType);
1851                    }
1852                }
1853            }
1854            setR0Type(pType);
1855        }
1856
1857        virtual int beginFunctionCallArguments() {
1858            int pc = getPC();
1859            o4(0xE24DDF00); // Placeholder sub  sp, sp, #0
1860            return pc;
1861        }
1862
1863        virtual size_t storeR0ToArg(int l, Type* pArgType) {
1864            convertR0(pArgType);
1865            Type* pR0Type = getR0Type();
1866            TypeTag r0ct = collapseType(pR0Type->tag);
1867#ifdef ARM_USE_VFP
1868            switch(r0ct) {
1869                case TY_INT:
1870                    if (l < 0 || l > 4096-4) {
1871                        error("l out of range for stack offset: 0x%08x", l);
1872                    }
1873                    o4(0xE58D0000 | l); // str r0, [sp, #l]
1874                    return 4;
1875                case TY_FLOAT:
1876                    if (l < 0 || l > 1020 || (l & 3)) {
1877                        error("l out of range for stack offset: 0x%08x", l);
1878                    }
1879                    o4(0xEDCD7A00 | (l >> 2)); // fsts    s15, [sp, #l]
1880                    return 4;
1881                case TY_DOUBLE: {
1882                    // Align to 8 byte boundary
1883                    int l2 = (l + 7) & ~7;
1884                    if (l2 < 0 || l2 > 1020 || (l2 & 3)) {
1885                        error("l out of range for stack offset: 0x%08x", l);
1886                    }
1887                    o4(0xED8D7B00 | (l2 >> 2)); // fstd    d7, [sp, #l2]
1888                    return (l2 - l) + 8;
1889                }
1890                default:
1891                    assert(false);
1892                    return 0;
1893            }
1894#else
1895            switch(r0ct) {
1896                case TY_INT:
1897                case TY_FLOAT:
1898                    if (l < 0 || l > 4096-4) {
1899                        error("l out of range for stack offset: 0x%08x", l);
1900                    }
1901                    o4(0xE58D0000 + l); // str r0, [sp, #l]
1902                    return 4;
1903                case TY_DOUBLE: {
1904                    // Align to 8 byte boundary
1905                    int l2 = (l + 7) & ~7;
1906                    if (l2 < 0 || l2 > 4096-8) {
1907                        error("l out of range for stack offset: 0x%08x", l);
1908                    }
1909                    o4(0xE58D0000 + l2); // str r0, [sp, #l]
1910                    o4(0xE58D1000 + l2 + 4); // str r1, [sp, #l+4]
1911                    return (l2 - l) + 8;
1912                }
1913                default:
1914                    assert(false);
1915                    return 0;
1916            }
1917#endif
1918        }
1919
1920        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
1921            int argumentStackUse = l;
1922            // Have to calculate register arg count from actual stack size,
1923            // in order to properly handle ... functions.
1924            int regArgCount = l >> 2;
1925            if (regArgCount > 4) {
1926                regArgCount = 4;
1927            }
1928            if (regArgCount > 0) {
1929                argumentStackUse -= regArgCount * 4;
1930                o4(0xE8BD0000 | ((1 << regArgCount) - 1)); // ldmfd   sp!,{}
1931            }
1932            mStackUse += argumentStackUse;
1933
1934            // Align stack.
1935            int missalignment = mStackUse - ((mStackUse / STACK_ALIGNMENT)
1936                    * STACK_ALIGNMENT);
1937            mStackAlignmentAdjustment = 0;
1938            if (missalignment > 0) {
1939                mStackAlignmentAdjustment = STACK_ALIGNMENT - missalignment;
1940            }
1941            l += mStackAlignmentAdjustment;
1942
1943            if (l < 0 || l > 0x3FC) {
1944                error("L out of range for stack adjustment: 0x%08x", l);
1945            }
1946            flush();
1947            * (int*) a = 0xE24DDF00 | (l >> 2); // sub    sp, sp, #0 << 2
1948            mStackUse += mStackAlignmentAdjustment;
1949            LOG_STACK("endFunctionCallArguments mStackUse: %d, mStackAlignmentAdjustment %d\n",
1950                      mStackUse, mStackAlignmentAdjustment);
1951        }
1952
1953        virtual int callForward(int symbol, Type* pFunc) {
1954            setR0Type(pFunc->pHead);
1955            // Forward calls are always short (local)
1956            int pc = getPC();
1957            o4(0xEB000000 | encodeAddress(symbol));
1958            return pc;
1959        }
1960
1961        virtual void callIndirect(int l, Type* pFunc) {
1962            assert(pFunc->tag == TY_FUNC);
1963            popType(); // Get rid of indirect fn pointer type
1964            int argCount = l >> 2;
1965            int poppedArgs = argCount > 4 ? 4 : argCount;
1966            int adjustedL = l - (poppedArgs << 2) + mStackAlignmentAdjustment;
1967            if (adjustedL < 0 || adjustedL > 4096-4) {
1968                error("l out of range for stack offset: 0x%08x", l);
1969            }
1970            o4(0xE59DC000 | (0xfff & adjustedL)); // ldr    r12, [sp,#adjustedL]
1971            o4(0xE12FFF3C); // blx r12
1972            Type* pReturnType = pFunc->pHead;
1973            setR0Type(pReturnType);
1974#ifdef ARM_USE_VFP
1975            switch(pReturnType->tag) {
1976            case TY_FLOAT:
1977                o4(0xEE070A90); // fmsr s15, r0
1978                break;
1979            case TY_DOUBLE:
1980                o4(0xEC410B17); // fmdrr d7, r0, r1
1981                break;
1982            default:
1983                break;
1984            }
1985#endif
1986        }
1987
1988        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
1989            int argCount = l >> 2;
1990            // Have to calculate register arg count from actual stack size,
1991            // in order to properly handle ... functions.
1992            int regArgCount = l >> 2;
1993            if (regArgCount > 4) {
1994                regArgCount = 4;
1995            }
1996            int stackArgs = argCount - regArgCount;
1997            int stackUse =  stackArgs + (isIndirect ? 1 : 0)
1998                + (mStackAlignmentAdjustment >> 2);
1999            if (stackUse) {
2000                if (stackUse < 0 || stackUse > 255) {
2001                    error("L out of range for stack adjustment: 0x%08x", l);
2002                }
2003                o4(0xE28DDF00 | stackUse); // add    sp, sp, #stackUse << 2
2004                mStackUse -= stackUse * 4;
2005                LOG_STACK("adjustStackAfterCall: %d\n", mStackUse);
2006            }
2007        }
2008
2009        virtual int jumpOffset() {
2010            return 8;
2011        }
2012
2013        /* output a symbol and patch all calls to it */
2014        virtual void gsym(int t) {
2015            int n;
2016            int base = getBase();
2017            int pc = getPC();
2018            while (t) {
2019                int data = * (int*) t;
2020                int decodedOffset = ((BRANCH_REL_ADDRESS_MASK & data) << 2);
2021                if (decodedOffset == 0) {
2022                    n = 0;
2023                } else {
2024                    n = base + decodedOffset; /* next value */
2025                }
2026                *(int *) t = (data & ~BRANCH_REL_ADDRESS_MASK)
2027                    | encodeRelAddress(pc - t - 8);
2028                t = n;
2029            }
2030        }
2031
2032        /* output a symbol and patch all calls to it */
2033        virtual void resolveForward(int t) {
2034            if (t) {
2035                int pc = getPC();
2036                *(int *) t = pc;
2037            }
2038        }
2039
2040        virtual int finishCompile() {
2041#if defined(__arm__)
2042            const long base = long(getBase());
2043            const long curr = long(getPC());
2044            int err = cacheflush(base, curr, 0);
2045            return err;
2046#else
2047            return 0;
2048#endif
2049        }
2050
2051        /**
2052         * alignment (in bytes) for this type of data
2053         */
2054        virtual size_t alignmentOf(Type* pType){
2055            switch(pType->tag) {
2056                case TY_CHAR:
2057                    return 1;
2058                case TY_SHORT:
2059                    return 2;
2060                case TY_DOUBLE:
2061                    return 8;
2062                case TY_ARRAY:
2063                    return alignmentOf(pType->pHead);
2064                case TY_STRUCT:
2065                    return pType->pHead->alignment & 0x7fffffff;
2066                case TY_FUNC:
2067                    error("alignment of func not supported");
2068                    return 1;
2069                default:
2070                    return 4;
2071            }
2072        }
2073
2074        /**
2075         * Array element alignment (in bytes) for this type of data.
2076         */
2077        virtual size_t sizeOf(Type* pType){
2078            switch(pType->tag) {
2079                case TY_INT:
2080                    return 4;
2081                case TY_SHORT:
2082                    return 2;
2083                case TY_CHAR:
2084                    return 1;
2085                case TY_FLOAT:
2086                    return 4;
2087                case TY_DOUBLE:
2088                    return 8;
2089                case TY_POINTER:
2090                    return 4;
2091                case TY_ARRAY:
2092                    return pType->length * sizeOf(pType->pHead);
2093                case TY_STRUCT:
2094                    return pType->pHead->length;
2095                default:
2096                    error("Unsupported type %d", pType->tag);
2097                    return 0;
2098            }
2099        }
2100
2101    private:
2102
2103        static const int BRANCH_REL_ADDRESS_MASK = 0x00ffffff;
2104
2105        /** Encode a relative address that might also be
2106         * a label.
2107         */
2108        int encodeAddress(int value) {
2109            int base = getBase();
2110            if (value >= base && value <= getPC() ) {
2111                // This is a label, encode it relative to the base.
2112                value = value - base;
2113            }
2114            return encodeRelAddress(value);
2115        }
2116
2117        int encodeRelAddress(int value) {
2118            return BRANCH_REL_ADDRESS_MASK & (value >> 2);
2119        }
2120
2121        int calcRegArgCount(Type* pDecl) {
2122            int reg = 0;
2123            Type* pArgs = pDecl->pTail;
2124            while (pArgs && reg < 4) {
2125                Type* pArg = pArgs->pHead;
2126                if ( pArg->tag == TY_DOUBLE) {
2127                    int evenReg = (reg + 1) & ~1;
2128                    if (evenReg >= 4) {
2129                        break;
2130                    }
2131                    reg = evenReg + 2;
2132                } else {
2133                    reg++;
2134                }
2135                pArgs = pArgs->pTail;
2136            }
2137            return reg;
2138        }
2139
2140        void setupIntPtrArgs() {
2141            o4(0xE8BD0002);  // ldmfd   sp!,{r1}
2142            mStackUse -= 4;
2143            popType();
2144        }
2145
2146        /* Pop TOS to R1 (use s14 if VFP)
2147         * Make sure both R0 and TOS are floats. (Could be ints)
2148         * We know that at least one of R0 and TOS is already a float
2149         */
2150        void setupFloatArgs() {
2151            Type* pR0Type = getR0Type();
2152            Type* pTOSType = getTOSType();
2153            TypeTag tagR0 = collapseType(pR0Type->tag);
2154            TypeTag tagTOS = collapseType(pTOSType->tag);
2155            if (tagR0 != TY_FLOAT) {
2156                assert(tagR0 == TY_INT);
2157#ifdef ARM_USE_VFP
2158                o4(0xEE070A90); // fmsr    s15, r0
2159                o4(0xEEF87AE7); // fsitos s15, s15
2160#else
2161                callRuntime((void*) runtime_int_to_float);
2162#endif
2163            }
2164            if (tagTOS != TY_FLOAT) {
2165                assert(tagTOS == TY_INT);
2166                assert(tagR0 == TY_FLOAT);
2167#ifdef ARM_USE_VFP
2168                o4(0xECBD7A01); // fldmfds sp!, {s14}
2169                o4(0xEEB87AC7); // fsitos s14, s14
2170#else
2171                o4(0xE92D0001);  // stmfd   sp!,{r0}  // push R0
2172                o4(0xE59D0004);  // ldr     r0, [sp, #4]
2173                callRuntime((void*) runtime_int_to_float);
2174                o4(0xE1A01000);  // mov r1, r0
2175                o4(0xE8BD0001);  // ldmfd   sp!,{r0}  // pop R0
2176                o4(0xE28DD004);  // add sp, sp, #4 // Pop sp
2177#endif
2178            } else {
2179                // Pop TOS
2180#ifdef ARM_USE_VFP
2181                o4(0xECBD7A01); // fldmfds sp!, {s14}
2182
2183#else
2184                o4(0xE8BD0002);  // ldmfd   sp!,{r1}
2185#endif
2186            }
2187            mStackUse -= 4;
2188            popType();
2189        }
2190
2191        /* Pop TOS into R2..R3 (use D6 if VFP)
2192         * Make sure both R0 and TOS are doubles. Could be floats or ints.
2193         * We know that at least one of R0 and TOS are already a double.
2194         */
2195
2196        void setupDoubleArgs() {
2197            Type* pR0Type = getR0Type();
2198            Type* pTOSType = getTOSType();
2199            TypeTag tagR0 = collapseType(pR0Type->tag);
2200            TypeTag tagTOS = collapseType(pTOSType->tag);
2201            if (tagR0 != TY_DOUBLE) {
2202                if (tagR0 == TY_INT) {
2203#ifdef ARM_USE_VFP
2204                    o4(0xEE070A90); // fmsr s15, r0
2205                    o4(0xEEB87BE7); // fsitod d7, s15
2206
2207#else
2208                    callRuntime((void*) runtime_int_to_double);
2209#endif
2210                } else {
2211                    assert(tagR0 == TY_FLOAT);
2212#ifdef ARM_USE_VFP
2213                    o4(0xEEB77AE7); // fcvtds    d7, s15
2214#else
2215                    callRuntime((void*) runtime_float_to_double);
2216#endif
2217                }
2218            }
2219            if (tagTOS != TY_DOUBLE) {
2220#ifdef ARM_USE_VFP
2221                if (tagTOS == TY_INT) {
2222                    o4(0xECFD6A01);  // fldmfds sp!,{s13}
2223                    o4(0xEEB86BE6);  // fsitod  d6, s13
2224                } else {
2225                    assert(tagTOS == TY_FLOAT);
2226                    o4(0xECFD6A01);  // fldmfds sp!,{s13}
2227                    o4(0xEEB76AE6);  // fcvtds    d6, s13
2228                }
2229#else
2230                o4(0xE92D0003);  // stmfd   sp!,{r0,r1}  // push r0,r1
2231                o4(0xE59D0008);  // ldr     r0, [sp, #8]
2232                if (tagTOS == TY_INT) {
2233                    callRuntime((void*) runtime_int_to_double);
2234                } else {
2235                    assert(tagTOS == TY_FLOAT);
2236                    callRuntime((void*) runtime_float_to_double);
2237                }
2238                o4(0xE1A02000);  // mov r2, r0
2239                o4(0xE1A03001);  // mov r3, r1
2240                o4(0xE8BD0003);  // ldmfd   sp!,{r0, r1}  // Restore R0
2241                o4(0xE28DD004);  // add sp, sp, #4 // Pop sp
2242#endif
2243                mStackUse -= 4;
2244            } else {
2245#ifdef ARM_USE_VFP
2246                o4(0xECBD6B02);  // fldmfdd    sp!, {d6}
2247#else
2248                o4(0xE8BD000C);  // ldmfd   sp!,{r2,r3}
2249#endif
2250                mStackUse -= 8;
2251            }
2252            popType();
2253        }
2254
2255        void liReg(int t, int reg) {
2256            assert(reg >= 0 && reg < 16);
2257            int rN = (reg & 0xf) << 12;
2258            size_t encodedImmediate;
2259            if (encode12BitImmediate(t, &encodedImmediate)) {
2260                 o4(0xE3A00000 | encodedImmediate | rN); // mov    rN, #0
2261            } else if (encode12BitImmediate(-(t+1), &encodedImmediate)) {
2262                // mvn means move constant ^ ~0
2263                o4(0xE3E00000 | encodedImmediate | rN); // mvn    rN, #0
2264            } else {
2265                o4(0xE51F0000 | rN); //         ldr    rN, .L3
2266                o4(0xEA000000); //         b .L99
2267                o4(t);          // .L3:   .word 0
2268                                  // .L99:
2269            }
2270        }
2271
2272        void incompatibleTypes(Type* pR0Type, Type* pType) {
2273            error("Incompatible types old: %d new: %d", pR0Type->tag, pType->tag);
2274        }
2275
2276        void callRuntime(void* fn) {
2277            o4(0xE59FC000); // ldr    r12, .L1
2278            o4(0xEA000000); // b      .L99
2279            o4((int) fn);   //.L1:  .word  fn
2280            o4(0xE12FFF3C); //.L99: blx    r12
2281        }
2282
2283        // Integer math:
2284
2285        static int runtime_DIV(int b, int a) {
2286            return a / b;
2287        }
2288
2289        static int runtime_MOD(int b, int a) {
2290            return a % b;
2291        }
2292
2293        static void runtime_structCopy(void* src, size_t size, void* dest) {
2294            memcpy(dest, src, size);
2295        }
2296
2297#ifndef ARM_USE_VFP
2298
2299        // Comparison to zero
2300
2301        static int runtime_is_non_zero_f(float a) {
2302            return a != 0;
2303        }
2304
2305        static int runtime_is_non_zero_d(double a) {
2306            return a != 0;
2307        }
2308
2309        // Comparison to zero
2310
2311        static int runtime_is_zero_f(float a) {
2312            return a == 0;
2313        }
2314
2315        static int runtime_is_zero_d(double a) {
2316            return a == 0;
2317        }
2318
2319        // Type conversion
2320
2321        static int runtime_float_to_int(float a) {
2322            return (int) a;
2323        }
2324
2325        static double runtime_float_to_double(float a) {
2326            return (double) a;
2327        }
2328
2329        static int runtime_double_to_int(double a) {
2330            return (int) a;
2331        }
2332
2333        static float runtime_double_to_float(double a) {
2334            return (float) a;
2335        }
2336
2337        static float runtime_int_to_float(int a) {
2338            return (float) a;
2339        }
2340
2341        static double runtime_int_to_double(int a) {
2342            return (double) a;
2343        }
2344
2345        // Comparisons float
2346
2347        static int runtime_cmp_eq_ff(float b, float a) {
2348            return a == b;
2349        }
2350
2351        static int runtime_cmp_ne_ff(float b, float a) {
2352            return a != b;
2353        }
2354
2355        static int runtime_cmp_lt_ff(float b, float a) {
2356            return a < b;
2357        }
2358
2359        static int runtime_cmp_le_ff(float b, float a) {
2360            return a <= b;
2361        }
2362
2363        static int runtime_cmp_ge_ff(float b, float a) {
2364            return a >= b;
2365        }
2366
2367        static int runtime_cmp_gt_ff(float b, float a) {
2368            return a > b;
2369        }
2370
2371        // Comparisons double
2372
2373        static int runtime_cmp_eq_dd(double b, double a) {
2374            return a == b;
2375        }
2376
2377        static int runtime_cmp_ne_dd(double b, double a) {
2378            return a != b;
2379        }
2380
2381        static int runtime_cmp_lt_dd(double b, double a) {
2382            return a < b;
2383        }
2384
2385        static int runtime_cmp_le_dd(double b, double a) {
2386            return a <= b;
2387        }
2388
2389        static int runtime_cmp_ge_dd(double b, double a) {
2390            return a >= b;
2391        }
2392
2393        static int runtime_cmp_gt_dd(double b, double a) {
2394            return a > b;
2395        }
2396
2397        // Math float
2398
2399        static float runtime_op_add_ff(float b, float a) {
2400            return a + b;
2401        }
2402
2403        static float runtime_op_sub_ff(float b, float a) {
2404            return a - b;
2405        }
2406
2407        static float runtime_op_mul_ff(float b, float a) {
2408            return a * b;
2409        }
2410
2411        static float runtime_op_div_ff(float b, float a) {
2412            return a / b;
2413        }
2414
2415        static float runtime_op_neg_f(float a) {
2416            return -a;
2417        }
2418
2419        // Math double
2420
2421        static double runtime_op_add_dd(double b, double a) {
2422            return a + b;
2423        }
2424
2425        static double runtime_op_sub_dd(double b, double a) {
2426            return a - b;
2427        }
2428
2429        static double runtime_op_mul_dd(double b, double a) {
2430            return a * b;
2431        }
2432
2433        static double runtime_op_div_dd(double b, double a) {
2434            return a / b;
2435        }
2436
2437        static double runtime_op_neg_d(double a) {
2438            return -a;
2439        }
2440
2441#endif
2442
2443        static const int STACK_ALIGNMENT = 8;
2444        int mStackUse;
2445        // This variable holds the amount we adjusted the stack in the most
2446        // recent endFunctionCallArguments call. It's examined by the
2447        // following adjustStackAfterCall call.
2448        int mStackAlignmentAdjustment;
2449    };
2450
2451#endif // PROVIDE_ARM_CODEGEN
2452
2453#ifdef PROVIDE_X86_CODEGEN
2454
2455    class X86CodeGenerator : public CodeGenerator {
2456    public:
2457        X86CodeGenerator() {}
2458        virtual ~X86CodeGenerator() {}
2459
2460        /* returns address to patch with local variable size
2461        */
2462        virtual int functionEntry(Type* pDecl) {
2463            o(0xe58955); /* push   %ebp, mov %esp, %ebp */
2464            return oad(0xec81, 0); /* sub $xxx, %esp */
2465        }
2466
2467        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
2468            o(0xc3c9); /* leave, ret */
2469            *(int *) localVariableAddress = localVariableSize; /* save local variables */
2470        }
2471
2472        /* load immediate value */
2473        virtual void li(int i) {
2474            oad(0xb8, i); /* mov $xx, %eax */
2475            setR0Type(mkpInt);
2476        }
2477
2478        virtual void loadFloat(int address, Type* pType) {
2479            setR0Type(pType);
2480            switch (pType->tag) {
2481            case TY_FLOAT:
2482                oad(0x05D9, address);      // flds
2483                break;
2484            case TY_DOUBLE:
2485                oad(0x05DD, address);      // fldl
2486                break;
2487            default:
2488                assert(false);
2489                break;
2490            }
2491        }
2492
2493        virtual void addStructOffsetR0(int offset, Type* pType) {
2494            if (offset) {
2495                oad(0x05, offset); // addl offset, %eax
2496            }
2497            setR0Type(pType, ET_LVALUE);
2498        }
2499
2500        virtual int gjmp(int t) {
2501            return psym(0xe9, t);
2502        }
2503
2504        /* l = 0: je, l == 1: jne */
2505        virtual int gtst(bool l, int t) {
2506            Type* pR0Type = getR0Type();
2507            TypeTag tagR0 = pR0Type->tag;
2508            bool isFloatR0 = isFloatTag(tagR0);
2509            if (isFloatR0) {
2510                o(0xeed9); // fldz
2511                o(0xe9da); // fucompp
2512                o(0xe0df); // fnstsw %ax
2513                o(0x9e);   // sahf
2514            } else {
2515                o(0xc085); // test %eax, %eax
2516            }
2517            // Use two output statements to generate one instruction.
2518            o(0x0f);   // je/jne xxx
2519            return psym(0x84 + l, t);
2520        }
2521
2522        virtual void gcmp(int op) {
2523            Type* pR0Type = getR0Type();
2524            Type* pTOSType = getTOSType();
2525            TypeTag tagR0 = pR0Type->tag;
2526            TypeTag tagTOS = pTOSType->tag;
2527            bool isFloatR0 = isFloatTag(tagR0);
2528            bool isFloatTOS = isFloatTag(tagTOS);
2529            if (!isFloatR0 && !isFloatTOS) {
2530                int t = decodeOp(op);
2531                o(0x59); /* pop %ecx */
2532                o(0xc139); /* cmp %eax,%ecx */
2533                li(0);
2534                o(0x0f); /* setxx %al */
2535                o(t + 0x90);
2536                o(0xc0);
2537                popType();
2538            } else {
2539                setupFloatOperands();
2540                switch (op) {
2541                    case OP_EQUALS:
2542                        o(0xe9da);   // fucompp
2543                        o(0xe0df);   // fnstsw %ax
2544                        o(0x9e);     // sahf
2545                        o(0xc0940f); // sete %al
2546                        o(0xc29b0f); // setnp %dl
2547                        o(0xd021);   // andl %edx, %eax
2548                        break;
2549                    case OP_NOT_EQUALS:
2550                        o(0xe9da);   // fucompp
2551                        o(0xe0df);   // fnstsw %ax
2552                        o(0x9e);     // sahf
2553                        o(0xc0950f); // setne %al
2554                        o(0xc29a0f); // setp %dl
2555                        o(0xd009);   // orl %edx, %eax
2556                        break;
2557                    case OP_GREATER_EQUAL:
2558                        o(0xe9da);   // fucompp
2559                        o(0xe0df);   // fnstsw %ax
2560                        o(0x05c4f6); // testb $5, %ah
2561                        o(0xc0940f); // sete %al
2562                        break;
2563                    case OP_LESS:
2564                        o(0xc9d9);   // fxch %st(1)
2565                        o(0xe9da);   // fucompp
2566                        o(0xe0df);   // fnstsw %ax
2567                        o(0x9e);     // sahf
2568                        o(0xc0970f); // seta %al
2569                        break;
2570                    case OP_LESS_EQUAL:
2571                        o(0xc9d9);   // fxch %st(1)
2572                        o(0xe9da);   // fucompp
2573                        o(0xe0df);   // fnstsw %ax
2574                        o(0x9e);     // sahf
2575                        o(0xc0930f); // setea %al
2576                        break;
2577                    case OP_GREATER:
2578                        o(0xe9da);   // fucompp
2579                        o(0xe0df);   // fnstsw %ax
2580                        o(0x45c4f6); // testb $69, %ah
2581                        o(0xc0940f); // sete %al
2582                        break;
2583                    default:
2584                        error("Unknown comparison op");
2585                }
2586                o(0xc0b60f); // movzbl %al, %eax
2587            }
2588            setR0Type(mkpInt);
2589        }
2590
2591        virtual void genOp(int op) {
2592            Type* pR0Type = getR0Type();
2593            Type* pTOSType = getTOSType();
2594            TypeTag tagR0 = pR0Type->tag;
2595            TypeTag tagTOS = pTOSType->tag;
2596            bool isFloatR0 = isFloatTag(tagR0);
2597            bool isFloatTOS = isFloatTag(tagTOS);
2598            if (!isFloatR0 && !isFloatTOS) {
2599                bool isPtrR0 = isPointerTag(tagR0);
2600                bool isPtrTOS = isPointerTag(tagTOS);
2601                if (isPtrR0 || isPtrTOS) {
2602                    if (isPtrR0 && isPtrTOS) {
2603                        if (op != OP_MINUS) {
2604                            error("Unsupported pointer-pointer operation %d.", op);
2605                        }
2606                        if (! typeEqual(pR0Type, pTOSType)) {
2607                            error("Incompatible pointer types for subtraction.");
2608                        }
2609                        o(0x59); /* pop %ecx */
2610                        o(decodeOp(op));
2611                        popType();
2612                        setR0Type(mkpInt);
2613                        int size = sizeOf(pR0Type->pHead);
2614                        if (size != 1) {
2615                            pushR0();
2616                            li(size);
2617                            // TODO: Optimize for power-of-two.
2618                            genOp(OP_DIV);
2619                        }
2620                    } else {
2621                        if (! (op == OP_PLUS || (op == OP_MINUS && isPtrR0))) {
2622                            error("Unsupported pointer-scalar operation %d", op);
2623                        }
2624                        Type* pPtrType = getPointerArithmeticResultType(
2625                                pR0Type, pTOSType);
2626                        o(0x59); /* pop %ecx */
2627                        int size = sizeOf(pPtrType->pHead);
2628                        if (size != 1) {
2629                            // TODO: Optimize for power-of-two.
2630                            if (isPtrR0) {
2631                                oad(0xC969, size); // imull $size, %ecx
2632                            } else {
2633                                oad(0xC069, size); // mul $size, %eax
2634                            }
2635                        }
2636                        o(decodeOp(op));
2637                        popType();
2638                        setR0Type(pPtrType);
2639                    }
2640                } else {
2641                    o(0x59); /* pop %ecx */
2642                    o(decodeOp(op));
2643                    if (op == OP_MOD)
2644                        o(0x92); /* xchg %edx, %eax */
2645                    popType();
2646                }
2647            } else {
2648                Type* pResultType = tagR0 > tagTOS ? pR0Type : pTOSType;
2649                setupFloatOperands();
2650                // Both float. x87 R0 == left hand, x87 R1 == right hand
2651                switch (op) {
2652                    case OP_MUL:
2653                        o(0xc9de); // fmulp
2654                        break;
2655                    case OP_DIV:
2656                        o(0xf1de); // fdivp
2657                        break;
2658                    case OP_PLUS:
2659                        o(0xc1de); // faddp
2660                        break;
2661                    case OP_MINUS:
2662                        o(0xe1de); // fsubp
2663                        break;
2664                    default:
2665                        error("Unsupported binary floating operation.");
2666                        break;
2667                }
2668                setR0Type(pResultType);
2669            }
2670        }
2671
2672        virtual void gUnaryCmp(int op) {
2673            if (op != OP_LOGICAL_NOT) {
2674                error("Unknown unary cmp %d", op);
2675            } else {
2676                Type* pR0Type = getR0Type();
2677                TypeTag tag = collapseType(pR0Type->tag);
2678                switch(tag) {
2679                    case TY_INT: {
2680                            oad(0xb9, 0); /* movl $0, %ecx */
2681                            int t = decodeOp(op);
2682                            o(0xc139); /* cmp %eax,%ecx */
2683                            li(0);
2684                            o(0x0f); /* setxx %al */
2685                            o(t + 0x90);
2686                            o(0xc0);
2687                        }
2688                        break;
2689                    case TY_FLOAT:
2690                    case TY_DOUBLE:
2691                        o(0xeed9);   // fldz
2692                        o(0xe9da);   // fucompp
2693                        o(0xe0df);   // fnstsw %ax
2694                        o(0x9e);     // sahf
2695                        o(0xc0950f); // setne %al
2696                        o(0xc29a0f); // setp %dl
2697                        o(0xd009);   // orl %edx, %eax
2698                        o(0xc0b60f); // movzbl %al, %eax
2699                        o(0x01f083); // xorl $1,  %eax
2700                        break;
2701                    default:
2702                        error("gUnaryCmp unsupported type");
2703                        break;
2704                }
2705            }
2706            setR0Type(mkpInt);
2707        }
2708
2709        virtual void genUnaryOp(int op) {
2710            Type* pR0Type = getR0Type();
2711            TypeTag tag = collapseType(pR0Type->tag);
2712            switch(tag) {
2713                case TY_INT:
2714                    oad(0xb9, 0); /* movl $0, %ecx */
2715                    o(decodeOp(op));
2716                    break;
2717                case TY_FLOAT:
2718                case TY_DOUBLE:
2719                    switch (op) {
2720                        case OP_MINUS:
2721                            o(0xe0d9);  // fchs
2722                            break;
2723                        case OP_BIT_NOT:
2724                            error("Can't apply '~' operator to a float or double.");
2725                            break;
2726                        default:
2727                            error("Unknown unary op %d\n", op);
2728                            break;
2729                        }
2730                    break;
2731                default:
2732                    error("genUnaryOp unsupported type");
2733                    break;
2734            }
2735        }
2736
2737        virtual void pushR0() {
2738            Type* pR0Type = getR0Type();
2739            TypeTag r0ct = collapseType(pR0Type->tag);
2740            switch(r0ct) {
2741                case TY_INT:
2742                    o(0x50); /* push %eax */
2743                    break;
2744                case TY_FLOAT:
2745                    o(0x50); /* push %eax */
2746                    o(0x241cd9); // fstps 0(%esp)
2747                    break;
2748                case TY_DOUBLE:
2749                    o(0x50); /* push %eax */
2750                    o(0x50); /* push %eax */
2751                    o(0x241cdd); // fstpl 0(%esp)
2752                    break;
2753                default:
2754                    error("pushR0 unsupported type %d", r0ct);
2755                    break;
2756            }
2757            pushType();
2758        }
2759
2760        virtual void over() {
2761            // We know it's only used for int-ptr ops (++/--)
2762
2763            Type* pR0Type = getR0Type();
2764            TypeTag r0ct = collapseType(pR0Type->tag);
2765
2766            Type* pTOSType = getTOSType();
2767            TypeTag tosct = collapseType(pTOSType->tag);
2768
2769            assert (r0ct == TY_INT && tosct == TY_INT);
2770
2771            o(0x59); /* pop %ecx */
2772            o(0x50); /* push %eax */
2773            o(0x51); /* push %ecx */
2774
2775            overType();
2776        }
2777
2778        virtual void popR0() {
2779            Type* pR0Type = getR0Type();
2780            TypeTag r0ct = collapseType(pR0Type->tag);
2781            switch(r0ct) {
2782                case TY_INT:
2783                    o(0x58); /* popl %eax */
2784                    break;
2785                case TY_FLOAT:
2786                    o(0x2404d9); // flds (%esp)
2787                    o(0x58); /* popl %eax */
2788                    break;
2789                case TY_DOUBLE:
2790                    o(0x2404dd); // fldl (%esp)
2791                    o(0x58); /* popl %eax */
2792                    o(0x58); /* popl %eax */
2793                    break;
2794                default:
2795                    error("popR0 unsupported type %d", r0ct);
2796                    break;
2797            }
2798            popType();
2799        }
2800
2801        virtual void storeR0ToTOS() {
2802            Type* pPointerType = getTOSType();
2803            assert(pPointerType->tag == TY_POINTER);
2804            Type* pTargetType = pPointerType->pHead;
2805            convertR0(pTargetType);
2806            o(0x59); /* pop %ecx */
2807            popType();
2808            switch (pTargetType->tag) {
2809                case TY_POINTER:
2810                case TY_INT:
2811                    o(0x0189); /* movl %eax/%al, (%ecx) */
2812                    break;
2813                case TY_SHORT:
2814                    o(0x018966); /* movw %ax, (%ecx) */
2815                    break;
2816                case TY_CHAR:
2817                    o(0x0188); /* movl %eax/%al, (%ecx) */
2818                    break;
2819                case TY_FLOAT:
2820                    o(0x19d9); /* fstps (%ecx) */
2821                    break;
2822                case TY_DOUBLE:
2823                    o(0x19dd); /* fstpl (%ecx) */
2824                    break;
2825                case TY_STRUCT:
2826                {
2827                    // TODO: use alignment information to use movsw/movsl instead of movsb
2828                    int size = sizeOf(pTargetType);
2829                    if (size > 0) {
2830                        o(0x9c);         // pushf
2831                        o(0x57);         // pushl %edi
2832                        o(0x56);         // pushl %esi
2833                        o(0xcf89);       // movl %ecx, %edi
2834                        o(0xc689);       // movl %eax, %esi
2835                        oad(0xb9, size);  // mov #size, %ecx
2836                        o(0xfc);         // cld
2837                        o(0xf3);         // rep
2838                        o(0xa4);         // movsb
2839                        o(0x5e);         // popl %esi
2840                        o(0x5f);         // popl %edi
2841                        o(0x9d);         // popf
2842                    }
2843                }
2844                    break;
2845                default:
2846                    error("storeR0ToTOS: unsupported type %d",
2847                            pTargetType->tag);
2848                    break;
2849            }
2850        }
2851
2852        virtual void loadR0FromR0() {
2853            Type* pPointerType = getR0Type();
2854            assert(pPointerType->tag == TY_POINTER);
2855            Type* pNewType = pPointerType->pHead;
2856            TypeTag tag = pNewType->tag;
2857            switch (tag) {
2858                case TY_POINTER:
2859                case TY_INT:
2860                    o2(0x008b); /* mov (%eax), %eax */
2861                    break;
2862                case TY_SHORT:
2863                    o(0xbf0f); /* movswl (%eax), %eax */
2864                    ob(0);
2865                    break;
2866                case TY_CHAR:
2867                    o(0xbe0f); /* movsbl (%eax), %eax */
2868                    ob(0); /* add zero in code */
2869                    break;
2870                case TY_FLOAT:
2871                    o2(0x00d9); // flds (%eax)
2872                    break;
2873                case TY_DOUBLE:
2874                    o2(0x00dd); // fldl (%eax)
2875                    break;
2876                case TY_ARRAY:
2877                    pNewType = pNewType->pTail;
2878                    break;
2879                case TY_STRUCT:
2880                    break;
2881                default:
2882                    error("loadR0FromR0: unsupported type %d", tag);
2883                    break;
2884            }
2885            setR0Type(pNewType);
2886        }
2887
2888        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
2889            gmov(10, ea); /* leal EA, %eax */
2890            setR0Type(pPointerType, et);
2891        }
2892
2893        virtual int leaForward(int ea, Type* pPointerType) {
2894            oad(0xb8, ea); /* mov $xx, %eax */
2895            setR0Type(pPointerType);
2896            return getPC() - 4;
2897        }
2898
2899        virtual void convertR0Imp(Type* pType, bool isCast){
2900            Type* pR0Type = getR0Type();
2901            if (pR0Type == NULL) {
2902                assert(false);
2903                setR0Type(pType);
2904                return;
2905            }
2906            if (isPointerType(pType) && isPointerType(pR0Type)) {
2907                Type* pA = pR0Type;
2908                Type* pB = pType;
2909                // Array decays to pointer
2910                if (pA->tag == TY_ARRAY && pB->tag == TY_POINTER) {
2911                    pA = pA->pTail;
2912                }
2913                if (! (typeEqual(pA, pB)
2914                        || pB->pHead->tag == TY_VOID
2915                        || (pA->tag == TY_POINTER && pB->tag == TY_POINTER && isCast)
2916                    )) {
2917                    error("Incompatible pointer or array types");
2918                }
2919            } else if (bitsSame(pType, pR0Type)) {
2920                // do nothing special
2921            } else if (isFloatType(pType) && isFloatType(pR0Type)) {
2922                // do nothing special, both held in same register on x87.
2923            } else {
2924                TypeTag r0Tag = collapseType(pR0Type->tag);
2925                TypeTag destTag = collapseType(pType->tag);
2926                if (r0Tag == TY_INT && isFloatTag(destTag)) {
2927                    // Convert R0 from int to float
2928                    o(0x50);      // push %eax
2929                    o(0x2404DB);  // fildl 0(%esp)
2930                    o(0x58);      // pop %eax
2931                } else if (isFloatTag(r0Tag) && destTag == TY_INT) {
2932                    // Convert R0 from float to int. Complicated because
2933                    // need to save and restore the rounding mode.
2934                    o(0x50);       // push %eax
2935                    o(0x50);       // push %eax
2936                    o(0x02247cD9); // fnstcw 2(%esp)
2937                    o(0x2444b70f); // movzwl 2(%esp), %eax
2938                    o(0x02);
2939                    o(0x0cb4);     // movb $12, %ah
2940                    o(0x24048966); // movw %ax, 0(%esp)
2941                    o(0x242cd9);   // fldcw 0(%esp)
2942                    o(0x04245cdb); // fistpl 4(%esp)
2943                    o(0x02246cd9); // fldcw  2(%esp)
2944                    o(0x58); // pop %eax
2945                    o(0x58); // pop %eax
2946                } else {
2947                    error("Incompatible types old: %d new: %d",
2948                          pR0Type->tag, pType->tag);
2949                }
2950            }
2951            setR0Type(pType);
2952        }
2953
2954        virtual int beginFunctionCallArguments() {
2955            return oad(0xec81, 0); /* sub $xxx, %esp */
2956        }
2957
2958        virtual size_t storeR0ToArg(int l, Type* pArgType) {
2959            convertR0(pArgType);
2960            Type* pR0Type = getR0Type();
2961            TypeTag r0ct = collapseType(pR0Type->tag);
2962            switch(r0ct) {
2963                case TY_INT:
2964                    oad(0x248489, l); /* movl %eax, xxx(%esp) */
2965                    return 4;
2966                case TY_FLOAT:
2967                    oad(0x249CD9, l); /* fstps   xxx(%esp) */
2968                    return 4;
2969                case TY_DOUBLE:
2970                    oad(0x249CDD, l); /* fstpl   xxx(%esp) */
2971                    return 8;
2972                default:
2973                    assert(false);
2974                    return 0;
2975            }
2976        }
2977
2978        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
2979            * (int*) a = l;
2980        }
2981
2982        virtual int callForward(int symbol, Type* pFunc) {
2983            assert(pFunc->tag == TY_FUNC);
2984            setR0Type(pFunc->pHead);
2985            return psym(0xe8, symbol); /* call xxx */
2986        }
2987
2988        virtual void callIndirect(int l, Type* pFunc) {
2989            assert(pFunc->tag == TY_FUNC);
2990            popType(); // Get rid of indirect fn pointer type
2991            setR0Type(pFunc->pHead);
2992            oad(0x2494ff, l); /* call *xxx(%esp) */
2993        }
2994
2995        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
2996            assert(pDecl->tag == TY_FUNC);
2997            if (isIndirect) {
2998                l += 4;
2999            }
3000            if (l > 0) {
3001                oad(0xc481, l); /* add $xxx, %esp */
3002            }
3003        }
3004
3005        virtual int jumpOffset() {
3006            return 5;
3007        }
3008
3009        /* output a symbol and patch all calls to it */
3010        virtual void gsym(int t) {
3011            int n;
3012            int pc = getPC();
3013            while (t) {
3014                n = *(int *) t; /* next value */
3015                *(int *) t = pc - t - 4;
3016                t = n;
3017            }
3018        }
3019
3020        /* output a symbol and patch all calls to it, using absolute address */
3021        virtual void resolveForward(int t) {
3022            int n;
3023            int pc = getPC();
3024            while (t) {
3025                n = *(int *) t; /* next value */
3026                *(int *) t = pc;
3027                t = n;
3028            }
3029        }
3030
3031        virtual int finishCompile() {
3032            size_t pagesize = 4096;
3033            size_t base = (size_t) getBase() & ~ (pagesize - 1);
3034            size_t top =  ((size_t) getPC() + pagesize - 1) & ~ (pagesize - 1);
3035            int err = mprotect((void*) base, top - base, PROT_READ | PROT_WRITE | PROT_EXEC);
3036            if (err) {
3037               error("mprotect() failed: %d", errno);
3038            }
3039            return err;
3040        }
3041
3042        /**
3043         * Alignment (in bytes) for this type of data
3044         */
3045        virtual size_t alignmentOf(Type* pType){
3046            switch (pType->tag) {
3047            case TY_CHAR:
3048                return 1;
3049            case TY_SHORT:
3050                return 2;
3051            case TY_ARRAY:
3052                return alignmentOf(pType->pHead);
3053            case TY_STRUCT:
3054                return pType->pHead->alignment & 0x7fffffff;
3055            case TY_FUNC:
3056                error("alignment of func not supported");
3057                return 1;
3058            default:
3059                return 4;
3060            }
3061        }
3062
3063        /**
3064         * Array element alignment (in bytes) for this type of data.
3065         */
3066        virtual size_t sizeOf(Type* pType){
3067            switch(pType->tag) {
3068                case TY_INT:
3069                    return 4;
3070                case TY_SHORT:
3071                    return 2;
3072                case TY_CHAR:
3073                    return 1;
3074                case TY_FLOAT:
3075                    return 4;
3076                case TY_DOUBLE:
3077                    return 8;
3078                case TY_POINTER:
3079                    return 4;
3080                case TY_ARRAY:
3081                    return pType->length * sizeOf(pType->pHead);
3082                case TY_STRUCT:
3083                    return pType->pHead->length;
3084                default:
3085                    error("Unsupported type %d", pType->tag);
3086                    return 0;
3087            }
3088        }
3089
3090    private:
3091
3092        /** Output 1 to 4 bytes.
3093         *
3094         */
3095        void o(int n) {
3096            /* cannot use unsigned, so we must do a hack */
3097            while (n && n != -1) {
3098                ob(n & 0xff);
3099                n = n >> 8;
3100            }
3101        }
3102
3103        /* Output exactly 2 bytes
3104         */
3105        void o2(int n) {
3106            ob(n & 0xff);
3107            ob(0xff & (n >> 8));
3108        }
3109
3110        /* psym is used to put an instruction with a data field which is a
3111         reference to a symbol. It is in fact the same as oad ! */
3112        int psym(int n, int t) {
3113            return oad(n, t);
3114        }
3115
3116        /* instruction + address */
3117        int oad(int n, int t) {
3118            o(n);
3119            int result = getPC();
3120            o4(t);
3121            return result;
3122        }
3123
3124        static const int operatorHelper[];
3125
3126        int decodeOp(int op) {
3127            if (op < 0 || op > OP_COUNT) {
3128                error("Out-of-range operator: %d\n", op);
3129                op = 0;
3130            }
3131            return operatorHelper[op];
3132        }
3133
3134        void gmov(int l, int t) {
3135            o(l + 0x83);
3136            oad((t > -LOCAL && t < LOCAL) << 7 | 5, t);
3137        }
3138
3139        void setupFloatOperands() {
3140            Type* pR0Type = getR0Type();
3141            Type* pTOSType = getTOSType();
3142            TypeTag tagR0 = pR0Type->tag;
3143            TypeTag tagTOS = pTOSType->tag;
3144            bool isFloatR0 = isFloatTag(tagR0);
3145            bool isFloatTOS = isFloatTag(tagTOS);
3146            if (! isFloatR0) {
3147                // Convert R0 from int to float
3148                o(0x50);      // push %eax
3149                o(0x2404DB);  // fildl 0(%esp)
3150                o(0x58);      // pop %eax
3151            }
3152            if (! isFloatTOS){
3153                o(0x2404DB);  // fildl 0(%esp);
3154                o(0x58);      // pop %eax
3155            } else {
3156                if (tagTOS == TY_FLOAT) {
3157                    o(0x2404d9);  // flds (%esp)
3158                    o(0x58);      // pop %eax
3159                } else {
3160                    o(0x2404dd);  // fldl (%esp)
3161                    o(0x58);      // pop %eax
3162                    o(0x58);      // pop %eax
3163                }
3164            }
3165            popType();
3166        }
3167    };
3168
3169#endif // PROVIDE_X86_CODEGEN
3170
3171#ifdef PROVIDE_TRACE_CODEGEN
3172    class TraceCodeGenerator : public CodeGenerator {
3173    private:
3174        CodeGenerator* mpBase;
3175
3176    public:
3177        TraceCodeGenerator(CodeGenerator* pBase) {
3178            mpBase = pBase;
3179        }
3180
3181        virtual ~TraceCodeGenerator() {
3182            delete mpBase;
3183        }
3184
3185        virtual void init(ICodeBuf* pCodeBuf) {
3186            mpBase->init(pCodeBuf);
3187        }
3188
3189        void setErrorSink(ErrorSink* pErrorSink) {
3190            mpBase->setErrorSink(pErrorSink);
3191        }
3192
3193        /* returns address to patch with local variable size
3194        */
3195        virtual int functionEntry(Type* pDecl) {
3196            int result = mpBase->functionEntry(pDecl);
3197            fprintf(stderr, "functionEntry(pDecl) -> %d\n", result);
3198            return result;
3199        }
3200
3201        virtual void functionExit(Type* pDecl, int localVariableAddress, int localVariableSize) {
3202            fprintf(stderr, "functionExit(pDecl, %d, %d)\n",
3203                    localVariableAddress, localVariableSize);
3204            mpBase->functionExit(pDecl, localVariableAddress, localVariableSize);
3205        }
3206
3207        /* load immediate value */
3208        virtual void li(int t) {
3209            fprintf(stderr, "li(%d)\n", t);
3210            mpBase->li(t);
3211        }
3212
3213        virtual void loadFloat(int address, Type* pType) {
3214            fprintf(stderr, "loadFloat(%d, type=%d)\n", address, pType->tag);
3215            mpBase->loadFloat(address, pType);
3216        }
3217
3218        virtual void addStructOffsetR0(int offset, Type* pType) {
3219            fprintf(stderr, "addStructOffsetR0(%d, type=%d)\n", offset, pType->tag);
3220            mpBase->addStructOffsetR0(offset, pType);
3221        }
3222
3223        virtual int gjmp(int t) {
3224            int result = mpBase->gjmp(t);
3225            fprintf(stderr, "gjmp(%d) = %d\n", t, result);
3226            return result;
3227        }
3228
3229        /* l = 0: je, l == 1: jne */
3230        virtual int gtst(bool l, int t) {
3231            int result = mpBase->gtst(l, t);
3232            fprintf(stderr, "gtst(%d,%d) = %d\n", l, t, result);
3233            return result;
3234        }
3235
3236        virtual void gcmp(int op) {
3237            fprintf(stderr, "gcmp(%d)\n", op);
3238            mpBase->gcmp(op);
3239        }
3240
3241        virtual void genOp(int op) {
3242            fprintf(stderr, "genOp(%d)\n", op);
3243            mpBase->genOp(op);
3244        }
3245
3246
3247        virtual void gUnaryCmp(int op) {
3248            fprintf(stderr, "gUnaryCmp(%d)\n", op);
3249            mpBase->gUnaryCmp(op);
3250        }
3251
3252        virtual void genUnaryOp(int op) {
3253            fprintf(stderr, "genUnaryOp(%d)\n", op);
3254            mpBase->genUnaryOp(op);
3255        }
3256
3257        virtual void pushR0() {
3258            fprintf(stderr, "pushR0()\n");
3259            mpBase->pushR0();
3260        }
3261
3262        virtual void over() {
3263            fprintf(stderr, "over()\n");
3264            mpBase->over();
3265        }
3266
3267        virtual void popR0() {
3268            fprintf(stderr, "popR0()\n");
3269            mpBase->popR0();
3270        }
3271
3272        virtual void storeR0ToTOS() {
3273            fprintf(stderr, "storeR0ToTOS()\n");
3274            mpBase->storeR0ToTOS();
3275        }
3276
3277        virtual void loadR0FromR0() {
3278            fprintf(stderr, "loadR0FromR0()\n");
3279            mpBase->loadR0FromR0();
3280        }
3281
3282        virtual void leaR0(int ea, Type* pPointerType, ExpressionType et) {
3283            fprintf(stderr, "leaR0(%d, %d, %d)\n", ea,
3284                    pPointerType->pHead->tag, et);
3285            mpBase->leaR0(ea, pPointerType, et);
3286        }
3287
3288        virtual int leaForward(int ea, Type* pPointerType) {
3289            fprintf(stderr, "leaForward(%d)\n", ea);
3290            return mpBase->leaForward(ea, pPointerType);
3291        }
3292
3293        virtual void convertR0Imp(Type* pType, bool isCast){
3294            fprintf(stderr, "convertR0(pType tag=%d, %d)\n",  pType->tag, isCast);
3295            mpBase->convertR0Imp(pType, isCast);
3296        }
3297
3298        virtual int beginFunctionCallArguments() {
3299            int result = mpBase->beginFunctionCallArguments();
3300            fprintf(stderr, "beginFunctionCallArguments() = %d\n", result);
3301            return result;
3302        }
3303
3304        virtual size_t storeR0ToArg(int l, Type* pArgType) {
3305            fprintf(stderr, "storeR0ToArg(%d, pArgType=%d)\n", l,
3306                    pArgType->tag);
3307            return mpBase->storeR0ToArg(l, pArgType);
3308        }
3309
3310        virtual void endFunctionCallArguments(Type* pDecl, int a, int l) {
3311            fprintf(stderr, "endFunctionCallArguments(%d, %d)\n", a, l);
3312            mpBase->endFunctionCallArguments(pDecl, a, l);
3313        }
3314
3315        virtual int callForward(int symbol, Type* pFunc) {
3316            int result = mpBase->callForward(symbol, pFunc);
3317            fprintf(stderr, "callForward(%d) = %d\n", symbol, result);
3318            return result;
3319        }
3320
3321        virtual void callIndirect(int l, Type* pFunc) {
3322            fprintf(stderr, "callIndirect(%d returntype = %d)\n", l,
3323                    pFunc->pHead->tag);
3324            mpBase->callIndirect(l, pFunc);
3325        }
3326
3327        virtual void adjustStackAfterCall(Type* pDecl, int l, bool isIndirect) {
3328            fprintf(stderr, "adjustStackAfterCall(pType, %d, %d)\n", l, isIndirect);
3329            mpBase->adjustStackAfterCall(pDecl, l, isIndirect);
3330        }
3331
3332        virtual int jumpOffset() {
3333            return mpBase->jumpOffset();
3334        }
3335
3336        /* output a symbol and patch all calls to it */
3337        virtual void gsym(int t) {
3338            fprintf(stderr, "gsym(%d)\n", t);
3339            mpBase->gsym(t);
3340        }
3341
3342        virtual void resolveForward(int t) {
3343            mpBase->resolveForward(t);
3344        }
3345
3346        virtual int finishCompile() {
3347            int result = mpBase->finishCompile();
3348            fprintf(stderr, "finishCompile() = %d\n", result);
3349            return result;
3350        }
3351
3352        /**
3353         * Alignment (in bytes) for this type of data
3354         */
3355        virtual size_t alignmentOf(Type* pType){
3356            return mpBase->alignmentOf(pType);
3357        }
3358
3359        /**
3360         * Array element alignment (in bytes) for this type of data.
3361         */
3362        virtual size_t sizeOf(Type* pType){
3363            return mpBase->sizeOf(pType);
3364        }
3365
3366        virtual Type* getR0Type() {
3367            return mpBase->getR0Type();
3368        }
3369
3370        virtual ExpressionType getR0ExpressionType() {
3371            return mpBase->getR0ExpressionType();
3372        }
3373
3374        virtual void setR0ExpressionType(ExpressionType et) {
3375            mpBase->setR0ExpressionType(et);
3376        }
3377
3378        virtual size_t getExpressionStackDepth() {
3379            return mpBase->getExpressionStackDepth();
3380        }
3381
3382        virtual void forceR0RVal() {
3383            return mpBase->forceR0RVal();
3384        }
3385    };
3386
3387#endif // PROVIDE_TRACE_CODEGEN
3388
3389    class Arena {
3390    public:
3391        // Used to record a given allocation amount.
3392        // Used:
3393        // Mark mark = arena.mark();
3394        // ... lots of arena.allocate()
3395        // arena.free(mark);
3396
3397        struct Mark {
3398            size_t chunk;
3399            size_t offset;
3400        };
3401
3402        Arena() {
3403            mCurrentChunk = 0;
3404            Chunk start(CHUNK_SIZE);
3405            mData.push_back(start);
3406        }
3407
3408        ~Arena() {
3409            for(size_t i = 0; i < mData.size(); i++) {
3410                mData[i].free();
3411            }
3412        }
3413
3414        // Alloc using the standard alignment size safe for any variable
3415        void* alloc(size_t size) {
3416            return alloc(size, 8);
3417        }
3418
3419        Mark mark(){
3420            Mark result;
3421            result.chunk = mCurrentChunk;
3422            result.offset = mData[mCurrentChunk].mOffset;
3423            return result;
3424        }
3425
3426        void freeToMark(const Mark& mark) {
3427            mCurrentChunk = mark.chunk;
3428            mData[mCurrentChunk].mOffset = mark.offset;
3429        }
3430
3431    private:
3432        // Allocate memory aligned to a given size
3433        // and a given power-of-two-sized alignment (e.g. 1,2,4,8,...)
3434        // Memory is not zero filled.
3435
3436        void* alloc(size_t size, size_t alignment) {
3437            while (size > mData[mCurrentChunk].remainingCapacity(alignment)) {
3438                if (mCurrentChunk + 1 < mData.size()) {
3439                    mCurrentChunk++;
3440                } else {
3441                    size_t allocSize = CHUNK_SIZE;
3442                    if (allocSize < size + alignment - 1) {
3443                        allocSize = size + alignment - 1;
3444                    }
3445                    Chunk chunk(allocSize);
3446                    mData.push_back(chunk);
3447                    mCurrentChunk++;
3448                }
3449            }
3450            return mData[mCurrentChunk].allocate(size, alignment);
3451        }
3452
3453        static const size_t CHUNK_SIZE = 128*1024;
3454        // Note: this class does not deallocate its
3455        // memory when it's destroyed. It depends upon
3456        // its parent to deallocate the memory.
3457        struct Chunk {
3458            Chunk() {
3459                mpData = 0;
3460                mSize = 0;
3461                mOffset = 0;
3462            }
3463
3464            Chunk(size_t size) {
3465                mSize = size;
3466                mpData = (char*) malloc(size);
3467                mOffset = 0;
3468            }
3469
3470            ~Chunk() {
3471                // Doesn't deallocate memory.
3472            }
3473
3474            void* allocate(size_t size, size_t alignment) {
3475                size_t alignedOffset = aligned(mOffset, alignment);
3476                void* result = mpData + alignedOffset;
3477                mOffset = alignedOffset + size;
3478                return result;
3479            }
3480
3481            void free() {
3482                if (mpData) {
3483                    ::free(mpData);
3484                    mpData = 0;
3485                }
3486            }
3487
3488            size_t remainingCapacity(size_t alignment) {
3489                return aligned(mSize, alignment) - aligned(mOffset, alignment);
3490            }
3491
3492            // Assume alignment is a power of two
3493            inline size_t aligned(size_t v, size_t alignment) {
3494                size_t mask = alignment-1;
3495                return (v + mask) & ~mask;
3496            }
3497
3498            char* mpData;
3499            size_t mSize;
3500            size_t mOffset;
3501        };
3502
3503        size_t mCurrentChunk;
3504
3505        Vector<Chunk> mData;
3506    };
3507
3508    struct VariableInfo;
3509
3510    struct Token {
3511        int hash;
3512        size_t length;
3513        char* pText;
3514        tokenid_t id;
3515
3516        // Current values for the token
3517        char* mpMacroDefinition;
3518        VariableInfo* mpVariableInfo;
3519        VariableInfo* mpStructInfo;
3520    };
3521
3522    class TokenTable {
3523    public:
3524        // Don't use 0..0xff, allows characters and operators to be tokens too.
3525
3526        static const int TOKEN_BASE = 0x100;
3527        TokenTable() {
3528            mpMap = hashmapCreate(128, hashFn, equalsFn);
3529        }
3530
3531        ~TokenTable() {
3532            hashmapFree(mpMap);
3533        }
3534
3535        void setArena(Arena* pArena) {
3536            mpArena = pArena;
3537        }
3538
3539        // Returns a token for a given string of characters.
3540        tokenid_t intern(const char* pText, size_t length) {
3541            Token probe;
3542            int hash = hashmapHash((void*) pText, length);
3543            {
3544                Token probe;
3545                probe.hash = hash;
3546                probe.length = length;
3547                probe.pText = (char*) pText;
3548                Token* pValue = (Token*) hashmapGet(mpMap, &probe);
3549                if (pValue) {
3550                    return pValue->id;
3551                }
3552            }
3553
3554            Token* pToken = (Token*) mpArena->alloc(sizeof(Token));
3555            memset(pToken, 0, sizeof(*pToken));
3556            pToken->hash = hash;
3557            pToken->length = length;
3558            pToken->pText = (char*) mpArena->alloc(length + 1);
3559            memcpy(pToken->pText, pText, length);
3560            pToken->pText[length] = 0;
3561            pToken->id = mTokens.size() + TOKEN_BASE;
3562            mTokens.push_back(pToken);
3563            hashmapPut(mpMap, pToken, pToken);
3564            return pToken->id;
3565        }
3566
3567        // Return the Token for a given tokenid.
3568        Token& operator[](tokenid_t id) {
3569            return *mTokens[id - TOKEN_BASE];
3570        }
3571
3572        inline size_t size() {
3573            return mTokens.size();
3574        }
3575
3576    private:
3577
3578        static int hashFn(void* pKey) {
3579            Token* pToken = (Token*) pKey;
3580            return pToken->hash;
3581        }
3582
3583        static bool equalsFn(void* keyA, void* keyB) {
3584            Token* pTokenA = (Token*) keyA;
3585            Token* pTokenB = (Token*) keyB;
3586            // Don't need to compare hash values, they should always be equal
3587            return pTokenA->length == pTokenB->length
3588                && strcmp(pTokenA->pText, pTokenB->pText) == 0;
3589        }
3590
3591        Hashmap* mpMap;
3592        Vector<Token*> mTokens;
3593        Arena* mpArena;
3594    };
3595
3596    class InputStream {
3597    public:
3598        virtual ~InputStream() {}
3599        virtual int getChar() = 0;
3600    };
3601
3602    class TextInputStream : public InputStream {
3603    public:
3604        TextInputStream(const char* text, size_t textLength)
3605            : pText(text), mTextLength(textLength), mPosition(0) {
3606        }
3607
3608        virtual int getChar() {
3609            return mPosition < mTextLength ? pText[mPosition++] : EOF;
3610        }
3611
3612    private:
3613        const char* pText;
3614        size_t mTextLength;
3615        size_t mPosition;
3616    };
3617
3618    class String {
3619    public:
3620        String() {
3621            mpBase = 0;
3622            mUsed = 0;
3623            mSize = 0;
3624        }
3625
3626        String(const char* item, int len, bool adopt) {
3627            if (len < 0) {
3628                len = strlen(item);
3629            }
3630            if (adopt) {
3631                mpBase = (char*) item;
3632                mUsed = len;
3633                mSize = len + 1;
3634            } else {
3635                mpBase = 0;
3636                mUsed = 0;
3637                mSize = 0;
3638                appendBytes(item, len);
3639            }
3640        }
3641
3642        String(const String& other) {
3643            mpBase = 0;
3644            mUsed = 0;
3645            mSize = 0;
3646            appendBytes(other.getUnwrapped(), other.len());
3647        }
3648
3649        ~String() {
3650            if (mpBase) {
3651                free(mpBase);
3652            }
3653        }
3654
3655        String& operator=(const String& other) {
3656            clear();
3657            appendBytes(other.getUnwrapped(), other.len());
3658            return *this;
3659        }
3660
3661        inline char* getUnwrapped() const {
3662            return mpBase;
3663        }
3664
3665        void clear() {
3666            mUsed = 0;
3667            if (mSize > 0) {
3668                mpBase[0] = 0;
3669            }
3670        }
3671
3672        void appendCStr(const char* s) {
3673            appendBytes(s, strlen(s));
3674        }
3675
3676        void appendBytes(const char* s, int n) {
3677            memcpy(ensure(n), s, n + 1);
3678        }
3679
3680        void append(char c) {
3681            * ensure(1) = c;
3682        }
3683
3684        void append(String& other) {
3685            appendBytes(other.getUnwrapped(), other.len());
3686        }
3687
3688        char* orphan() {
3689            char* result = mpBase;
3690            mpBase = 0;
3691            mUsed = 0;
3692            mSize = 0;
3693            return result;
3694        }
3695
3696        void printf(const char* fmt,...) {
3697            va_list ap;
3698            va_start(ap, fmt);
3699            vprintf(fmt, ap);
3700            va_end(ap);
3701        }
3702
3703        void vprintf(const char* fmt, va_list ap) {
3704            char* temp;
3705            int numChars = vasprintf(&temp, fmt, ap);
3706            memcpy(ensure(numChars), temp, numChars+1);
3707            free(temp);
3708        }
3709
3710        inline size_t len() const {
3711            return mUsed;
3712        }
3713
3714    private:
3715        char* ensure(int n) {
3716            size_t newUsed = mUsed + n;
3717            if (newUsed > mSize) {
3718                size_t newSize = mSize * 2 + 10;
3719                if (newSize < newUsed) {
3720                    newSize = newUsed;
3721                }
3722                mpBase = (char*) realloc(mpBase, newSize + 1);
3723                mSize = newSize;
3724            }
3725            mpBase[newUsed] = '\0';
3726            char* result = mpBase + mUsed;
3727            mUsed = newUsed;
3728            return result;
3729        }
3730
3731        char* mpBase;
3732        size_t mUsed;
3733        size_t mSize;
3734    };
3735
3736    void internKeywords() {
3737        // Note: order has to match TOK_ constants
3738        static const char* keywords[] = {
3739            "int",
3740            "char",
3741            "void",
3742            "if",
3743            "else",
3744            "while",
3745            "break",
3746            "return",
3747            "for",
3748            "auto",
3749            "case",
3750            "const",
3751            "continue",
3752            "default",
3753            "do",
3754            "double",
3755            "enum",
3756            "extern",
3757            "float",
3758            "goto",
3759            "long",
3760            "register",
3761            "short",
3762            "signed",
3763            "sizeof",
3764            "static",
3765            "struct",
3766            "switch",
3767            "typedef",
3768            "union",
3769            "unsigned",
3770            "volatile",
3771            "_Bool",
3772            "_Complex",
3773            "_Imaginary",
3774            "inline",
3775            "restrict",
3776
3777            // predefined tokens that can also be symbols start here:
3778            "pragma",
3779            "define",
3780            "line",
3781            0};
3782
3783        for(int i = 0; keywords[i]; i++) {
3784            mTokenTable.intern(keywords[i], strlen(keywords[i]));
3785        }
3786    }
3787
3788    struct InputState {
3789        InputStream* pStream;
3790        int oldCh;
3791    };
3792
3793    struct VariableInfo {
3794        void* pAddress;
3795        void* pForward; // For a forward direction, linked list of data to fix up
3796        tokenid_t tok;
3797        size_t level;
3798        VariableInfo* pOldDefinition;
3799        Type* pType;
3800        bool isStructTag;
3801    };
3802
3803    class SymbolStack {
3804    public:
3805        SymbolStack() {
3806            mpArena = 0;
3807            mpTokenTable = 0;
3808        }
3809
3810        void setArena(Arena* pArena) {
3811            mpArena = pArena;
3812        }
3813
3814        void setTokenTable(TokenTable* pTokenTable) {
3815            mpTokenTable = pTokenTable;
3816        }
3817
3818        void pushLevel() {
3819            Mark mark;
3820            mark.mArenaMark = mpArena->mark();
3821            mark.mSymbolHead = mStack.size();
3822            mLevelStack.push_back(mark);
3823        }
3824
3825        void popLevel() {
3826            // Undo any shadowing that was done:
3827            Mark mark = mLevelStack.back();
3828            mLevelStack.pop_back();
3829            while (mStack.size() > mark.mSymbolHead) {
3830                VariableInfo* pV = mStack.back();
3831                mStack.pop_back();
3832                if (pV->isStructTag) {
3833                    (*mpTokenTable)[pV->tok].mpStructInfo = pV->pOldDefinition;
3834                } else {
3835                    (*mpTokenTable)[pV->tok].mpVariableInfo = pV->pOldDefinition;
3836                }
3837            }
3838            mpArena->freeToMark(mark.mArenaMark);
3839        }
3840
3841        bool isDefinedAtCurrentLevel(tokenid_t tok) {
3842            VariableInfo* pV = (*mpTokenTable)[tok].mpVariableInfo;
3843            return pV && pV->level == level();
3844        }
3845
3846        bool isStructTagDefinedAtCurrentLevel(tokenid_t tok) {
3847            VariableInfo* pV = (*mpTokenTable)[tok].mpStructInfo;
3848            return pV && pV->level == level();
3849        }
3850
3851        VariableInfo* add(tokenid_t tok) {
3852            Token& token = (*mpTokenTable)[tok];
3853            VariableInfo* pOldV = token.mpVariableInfo;
3854            VariableInfo* pNewV =
3855                (VariableInfo*) mpArena->alloc(sizeof(VariableInfo));
3856            memset(pNewV, 0, sizeof(VariableInfo));
3857            pNewV->tok = tok;
3858            pNewV->level = level();
3859            pNewV->pOldDefinition = pOldV;
3860            token.mpVariableInfo = pNewV;
3861            mStack.push_back(pNewV);
3862            return pNewV;
3863        }
3864
3865        VariableInfo* addStructTag(tokenid_t tok) {
3866            Token& token = (*mpTokenTable)[tok];
3867            VariableInfo* pOldS = token.mpStructInfo;
3868            VariableInfo* pNewS =
3869                (VariableInfo*) mpArena->alloc(sizeof(VariableInfo));
3870            memset(pNewS, 0, sizeof(VariableInfo));
3871            pNewS->tok = tok;
3872            pNewS->level = level();
3873            pNewS->isStructTag = true;
3874            pNewS->pOldDefinition = pOldS;
3875            token.mpStructInfo = pNewS;
3876            mStack.push_back(pNewS);
3877            return pNewS;
3878        }
3879
3880        VariableInfo* add(Type* pType) {
3881            VariableInfo* pVI = add(pType->id);
3882            pVI->pType = pType;
3883            return pVI;
3884        }
3885
3886        void forEach(bool (*fn)(VariableInfo*, void*), void* context) {
3887            for (size_t i = 0; i < mStack.size(); i++) {
3888                if (! fn(mStack[i], context)) {
3889                    break;
3890                }
3891            }
3892        }
3893
3894    private:
3895        inline size_t level() {
3896            return mLevelStack.size();
3897        }
3898
3899        struct Mark {
3900            Arena::Mark mArenaMark;
3901            size_t mSymbolHead;
3902        };
3903
3904        Arena* mpArena;
3905        TokenTable* mpTokenTable;
3906        Vector<VariableInfo*> mStack;
3907        Vector<Mark> mLevelStack;
3908    };
3909
3910    struct MacroState {
3911        tokenid_t name; // Name of the current macro we are expanding
3912        char* dptr; // point to macro text during macro playback
3913        int dch; // Saves old value of ch during a macro playback
3914    };
3915
3916#define MACRO_NESTING_MAX 32
3917    MacroState macroState[MACRO_NESTING_MAX];
3918    int macroLevel; // -1 means not playing any macro.
3919
3920    int ch; // Current input character, or EOF
3921    tokenid_t tok;      // token
3922    intptr_t tokc;    // token extra info
3923    double tokd;     // floating point constant value
3924    int tokl;         // token operator level
3925    intptr_t rsym; // return symbol
3926    Type* pReturnType; // type of the current function's return.
3927    intptr_t loc; // local variable index
3928    char* glo;  // global variable index
3929    String mTokenString;
3930    bool mbSuppressMacroExpansion;
3931    char* pGlobalBase;
3932    ACCSymbolLookupFn mpSymbolLookupFn;
3933    void* mpSymbolLookupContext;
3934
3935    // Arena for the duration of the compile
3936    Arena mGlobalArena;
3937    // Arena for data that's only needed when compiling a single function
3938    Arena mLocalArena;
3939
3940    Arena* mpCurrentArena;
3941
3942    TokenTable mTokenTable;
3943    SymbolStack mGlobals;
3944    SymbolStack mLocals;
3945
3946    SymbolStack* mpCurrentSymbolStack;
3947
3948    // Prebuilt types, makes things slightly faster.
3949    Type* mkpInt;        // int
3950    Type* mkpShort;      // short
3951    Type* mkpChar;       // char
3952    Type* mkpVoid;       // void
3953    Type* mkpFloat;
3954    Type* mkpDouble;
3955    Type* mkpIntFn;
3956    Type* mkpIntPtr;
3957    Type* mkpCharPtr;
3958    Type* mkpFloatPtr;
3959    Type* mkpDoublePtr;
3960    Type* mkpPtrIntFn;
3961
3962    InputStream* file;
3963    int mLineNumber;
3964    bool mbBumpLine;
3965
3966    ICodeBuf* pCodeBuf;
3967    CodeGenerator* pGen;
3968
3969    String mErrorBuf;
3970
3971    String mPragmas;
3972    int mPragmaStringCount;
3973    int mCompileResult;
3974
3975    static const int ALLOC_SIZE = 99999;
3976
3977    static const int TOK_DUMMY = 1;
3978    static const int TOK_NUM = 2;
3979    static const int TOK_NUM_FLOAT = 3;
3980    static const int TOK_NUM_DOUBLE = 4;
3981    static const int TOK_OP_ASSIGNMENT = 5;
3982    static const int TOK_OP_ARROW = 6;
3983
3984    // 3..255 are character and/or operators
3985
3986    // Keywords start at 0x100 and increase by 1
3987    // Order has to match string list in "internKeywords".
3988    enum {
3989        TOK_KEYWORD = TokenTable::TOKEN_BASE,
3990        TOK_INT = TOK_KEYWORD,
3991        TOK_CHAR,
3992        TOK_VOID,
3993        TOK_IF,
3994        TOK_ELSE,
3995        TOK_WHILE,
3996        TOK_BREAK,
3997        TOK_RETURN,
3998        TOK_FOR,
3999        TOK_AUTO,
4000        TOK_CASE,
4001        TOK_CONST,
4002        TOK_CONTINUE,
4003        TOK_DEFAULT,
4004        TOK_DO,
4005        TOK_DOUBLE,
4006        TOK_ENUM,
4007        TOK_EXTERN,
4008        TOK_FLOAT,
4009        TOK_GOTO,
4010        TOK_LONG,
4011        TOK_REGISTER,
4012        TOK_SHORT,
4013        TOK_SIGNED,
4014        TOK_SIZEOF,
4015        TOK_STATIC,
4016        TOK_STRUCT,
4017        TOK_SWITCH,
4018        TOK_TYPEDEF,
4019        TOK_UNION,
4020        TOK_UNSIGNED,
4021        TOK_VOLATILE,
4022        TOK__BOOL,
4023        TOK__COMPLEX,
4024        TOK__IMAGINARY,
4025        TOK_INLINE,
4026        TOK_RESTRICT,
4027
4028        // Symbols start after keywords
4029
4030        TOK_SYMBOL,
4031        TOK_PRAGMA = TOK_SYMBOL,
4032        TOK_DEFINE,
4033        TOK_LINE
4034    };
4035
4036    static const int LOCAL = 0x200;
4037
4038    /* tokens in string heap */
4039    static const int TAG_TOK = ' ';
4040
4041    static const int OP_INCREMENT = 0;
4042    static const int OP_DECREMENT = 1;
4043    static const int OP_MUL = 2;
4044    static const int OP_DIV = 3;
4045    static const int OP_MOD = 4;
4046    static const int OP_PLUS = 5;
4047    static const int OP_MINUS = 6;
4048    static const int OP_SHIFT_LEFT = 7;
4049    static const int OP_SHIFT_RIGHT = 8;
4050    static const int OP_LESS_EQUAL = 9;
4051    static const int OP_GREATER_EQUAL = 10;
4052    static const int OP_LESS = 11;
4053    static const int OP_GREATER = 12;
4054    static const int OP_EQUALS = 13;
4055    static const int OP_NOT_EQUALS = 14;
4056    static const int OP_LOGICAL_AND = 15;
4057    static const int OP_LOGICAL_OR = 16;
4058    static const int OP_BIT_AND = 17;
4059    static const int OP_BIT_XOR = 18;
4060    static const int OP_BIT_OR = 19;
4061    static const int OP_BIT_NOT = 20;
4062    static const int OP_LOGICAL_NOT = 21;
4063    static const int OP_COUNT = 22;
4064
4065    /* Operators are searched from front, the two-character operators appear
4066     * before the single-character operators with the same first character.
4067     * @ is used to pad out single-character operators.
4068     */
4069    static const char* operatorChars;
4070    static const char operatorLevel[];
4071
4072    /* Called when we detect an internal problem. Does nothing in production.
4073     *
4074     */
4075    void internalError() {
4076        * (char*) 0 = 0;
4077    }
4078
4079    void assertImpl(bool isTrue, int line) {
4080        if (!isTrue) {
4081            LOGD("%d: assertion failed at line %s:%d.", mLineNumber, __FILE__, line);
4082            internalError();
4083        }
4084    }
4085
4086    bool isSymbol(tokenid_t t) {
4087        return t >= TOK_SYMBOL &&
4088            ((size_t) (t-TOK_SYMBOL)) < mTokenTable.size();
4089    }
4090
4091    bool isSymbolOrKeyword(tokenid_t t) {
4092        return t >= TOK_KEYWORD &&
4093            ((size_t) (t-TOK_KEYWORD)) < mTokenTable.size();
4094    }
4095
4096    VariableInfo* VI(tokenid_t t) {
4097        assert(isSymbol(t));
4098        VariableInfo* pV = mTokenTable[t].mpVariableInfo;
4099        if (pV && pV->tok != t) {
4100            internalError();
4101        }
4102        return pV;
4103    }
4104
4105    inline bool isDefined(tokenid_t t) {
4106        return t >= TOK_SYMBOL && VI(t) != 0;
4107    }
4108
4109    const char* nameof(tokenid_t t) {
4110        assert(isSymbolOrKeyword(t));
4111        return mTokenTable[t].pText;
4112    }
4113
4114    void pdef(int t) {
4115        mTokenString.append(t);
4116    }
4117
4118    void inp() {
4119        // Close any totally empty macros. We leave them on the stack until now
4120        // so that we know which macros are being expanded when checking if the
4121        // last token in the macro is a macro that's already being expanded.
4122        while (macroLevel >= 0 && macroState[macroLevel].dptr == NULL) {
4123            macroLevel--;
4124        }
4125        if (macroLevel >= 0) {
4126            ch = *macroState[macroLevel].dptr++;
4127            if (ch == 0) {
4128                ch = macroState[macroLevel].dch;
4129                macroState[macroLevel].dptr = NULL; // This macro's done
4130            }
4131        } else {
4132            if (mbBumpLine) {
4133                mLineNumber++;
4134                mbBumpLine = false;
4135            }
4136            ch = file->getChar();
4137            if (ch == '\n') {
4138                mbBumpLine = true;
4139            }
4140        }
4141#if 0
4142        printf("ch='%c' 0x%x\n", ch, ch);
4143#endif
4144    }
4145
4146    int isid() {
4147        return isalnum(ch) | (ch == '_');
4148    }
4149
4150    int decodeHex(int c) {
4151        if (isdigit(c)) {
4152            c -= '0';
4153        } else if (c <= 'F') {
4154            c = c - 'A' + 10;
4155        } else {
4156            c =c - 'a' + 10;
4157        }
4158        return c;
4159    }
4160
4161    /* read a character constant, advances ch to after end of constant */
4162    int getq() {
4163        int val = ch;
4164        if (ch == '\\') {
4165            inp();
4166            if (isoctal(ch)) {
4167                // 1 to 3 octal characters.
4168                val = 0;
4169                for(int i = 0; i < 3; i++) {
4170                    if (isoctal(ch)) {
4171                        val = (val << 3) + ch - '0';
4172                        inp();
4173                    }
4174                }
4175                return val;
4176            } else if (ch == 'x' || ch == 'X') {
4177                // N hex chars
4178                inp();
4179                if (! isxdigit(ch)) {
4180                    error("'x' character escape requires at least one digit.");
4181                } else {
4182                    val = 0;
4183                    while (isxdigit(ch)) {
4184                        val = (val << 4) + decodeHex(ch);
4185                        inp();
4186                    }
4187                }
4188            } else {
4189                int val = ch;
4190                switch (ch) {
4191                    case 'a':
4192                        val = '\a';
4193                        break;
4194                    case 'b':
4195                        val = '\b';
4196                        break;
4197                    case 'f':
4198                        val = '\f';
4199                        break;
4200                    case 'n':
4201                        val = '\n';
4202                        break;
4203                    case 'r':
4204                        val = '\r';
4205                        break;
4206                    case 't':
4207                        val = '\t';
4208                        break;
4209                    case 'v':
4210                        val = '\v';
4211                        break;
4212                    case '\\':
4213                        val = '\\';
4214                        break;
4215                    case '\'':
4216                        val = '\'';
4217                        break;
4218                    case '"':
4219                        val = '"';
4220                        break;
4221                    case '?':
4222                        val = '?';
4223                        break;
4224                    default:
4225                        error("Undefined character escape %c", ch);
4226                        break;
4227                }
4228                inp();
4229                return val;
4230            }
4231        } else {
4232            inp();
4233        }
4234        return val;
4235    }
4236
4237    static bool isoctal(int ch) {
4238        return ch >= '0' && ch <= '7';
4239    }
4240
4241    bool acceptCh(int c) {
4242        bool result = c == ch;
4243        if (result) {
4244            pdef(ch);
4245            inp();
4246        }
4247        return result;
4248    }
4249
4250    bool acceptDigitsCh() {
4251        bool result = false;
4252        while (isdigit(ch)) {
4253            result = true;
4254            pdef(ch);
4255            inp();
4256        }
4257        return result;
4258    }
4259
4260    void parseFloat() {
4261        tok = TOK_NUM_DOUBLE;
4262        // mTokenString already has the integral part of the number.
4263        if(mTokenString.len() == 0) {
4264            mTokenString.append('0');
4265        }
4266        acceptCh('.');
4267        acceptDigitsCh();
4268        if (acceptCh('e') || acceptCh('E')) {
4269            acceptCh('-') || acceptCh('+');
4270            acceptDigitsCh();
4271        }
4272        if (ch == 'f' || ch == 'F') {
4273            tok = TOK_NUM_FLOAT;
4274            inp();
4275        } else if (ch == 'l' || ch == 'L') {
4276            inp();
4277            error("Long floating point constants not supported.");
4278        }
4279        char* pText = mTokenString.getUnwrapped();
4280        char* pEnd = pText + strlen(pText);
4281        char* pEndPtr = 0;
4282        errno = 0;
4283        if (tok == TOK_NUM_FLOAT) {
4284            tokd = strtof(pText, &pEndPtr);
4285        } else {
4286            tokd = strtod(pText, &pEndPtr);
4287        }
4288        if (errno || pEndPtr != pEnd) {
4289            error("Can't parse constant: %s", pText);
4290        }
4291        // fprintf(stderr, "float constant: %s (%d) %g\n", pText, tok, tokd);
4292    }
4293
4294    bool currentlyBeingExpanded(tokenid_t id) {
4295        for (int i = 0; i <= macroLevel; i++) {
4296            if (macroState[macroLevel].name == id) {
4297                return true;
4298            }
4299        }
4300        return false;
4301    }
4302
4303    void next() {
4304        int l, a;
4305
4306        while (isspace(ch) | (ch == '#')) {
4307            if (ch == '#') {
4308                inp();
4309                next();
4310                if (tok == TOK_DEFINE) {
4311                    doDefine();
4312                } else if (tok == TOK_PRAGMA) {
4313                    doPragma();
4314                } else if (tok == TOK_LINE) {
4315                    doLine();
4316                } else {
4317                    error("Unsupported preprocessor directive \"%s\"",
4318                          mTokenString.getUnwrapped());
4319                }
4320            }
4321            inp();
4322        }
4323        tokl = 0;
4324        tok = ch;
4325        /* encode identifiers & numbers */
4326        if (isdigit(ch) || ch == '.') {
4327            // Start of a numeric constant. Could be integer, float, or
4328            // double, won't know until we look further.
4329            mTokenString.clear();
4330            pdef(ch);
4331            inp();
4332            if (tok == '.' && !isdigit(ch)) {
4333                goto done;
4334            }
4335            int base = 10;
4336            if (tok == '0') {
4337                if (ch == 'x' || ch == 'X') {
4338                    base = 16;
4339                    tok = TOK_NUM;
4340                    tokc = 0;
4341                    inp();
4342                    while ( isxdigit(ch) ) {
4343                        tokc = (tokc << 4) + decodeHex(ch);
4344                        inp();
4345                    }
4346                } else if (isoctal(ch)){
4347                    base = 8;
4348                    tok = TOK_NUM;
4349                    tokc = 0;
4350                    while ( isoctal(ch) ) {
4351                        tokc = (tokc << 3) + (ch - '0');
4352                        inp();
4353                    }
4354                }
4355            } else if (isdigit(tok)){
4356                acceptDigitsCh();
4357            }
4358            if (base == 10) {
4359                if (tok == '.' || ch == '.' || ch == 'e' || ch == 'E') {
4360                    parseFloat();
4361                } else {
4362                    // It's an integer constant
4363                    char* pText = mTokenString.getUnwrapped();
4364                    char* pEnd = pText + strlen(pText);
4365                    char* pEndPtr = 0;
4366                    errno = 0;
4367                    tokc = strtol(pText, &pEndPtr, base);
4368                    if (errno || pEndPtr != pEnd) {
4369                        error("Can't parse constant: %s %d %d", pText, base, errno);
4370                    }
4371                    tok = TOK_NUM;
4372                }
4373            }
4374        } else if (isid()) {
4375            mTokenString.clear();
4376            while (isid()) {
4377                pdef(ch);
4378                inp();
4379            }
4380            tok = mTokenTable.intern(mTokenString.getUnwrapped(), mTokenString.len());
4381            if (! mbSuppressMacroExpansion) {
4382                // Is this a macro?
4383                char* pMacroDefinition = mTokenTable[tok].mpMacroDefinition;
4384                if (pMacroDefinition && !currentlyBeingExpanded(tok)) {
4385                    // Yes, it is a macro
4386#if 0
4387                    printf("Expanding macro %s -> %s",
4388                            mTokenString.getUnwrapped(), pMacroDefinition);
4389#endif
4390                    if (macroLevel >= MACRO_NESTING_MAX-1) {
4391                        error("Too many levels of macro recursion.");
4392                    } else {
4393                        macroLevel++;
4394                        macroState[macroLevel].name = tok;
4395                        macroState[macroLevel].dptr = pMacroDefinition;
4396                        macroState[macroLevel].dch = ch;
4397                        inp();
4398                        next();
4399                    }
4400                }
4401            }
4402        } else {
4403            inp();
4404            if (tok == '\'') {
4405                tok = TOK_NUM;
4406                tokc = getq();
4407                if (ch != '\'') {
4408                    error("Expected a ' character, got %c", ch);
4409                } else {
4410                  inp();
4411                }
4412            } else if ((tok == '/') & (ch == '*')) {
4413                inp();
4414                while (ch && ch != EOF) {
4415                    while (ch != '*' && ch != EOF)
4416                        inp();
4417                    inp();
4418                    if (ch == '/')
4419                        ch = 0;
4420                }
4421                if (ch == EOF) {
4422                    error("End of file inside comment.");
4423                }
4424                inp();
4425                next();
4426            } else if ((tok == '/') & (ch == '/')) {
4427                inp();
4428                while (ch && (ch != '\n') && (ch != EOF)) {
4429                    inp();
4430                }
4431                inp();
4432                next();
4433            } else if ((tok == '-') & (ch == '>')) {
4434                inp();
4435                tok = TOK_OP_ARROW;
4436            } else {
4437                const char* t = operatorChars;
4438                int opIndex = 0;
4439                while ((l = *t++) != 0) {
4440                    a = *t++;
4441                    tokl = operatorLevel[opIndex];
4442                    tokc = opIndex;
4443                    if ((l == tok) & ((a == ch) | (a == '@'))) {
4444#if 0
4445                        printf("%c%c -> tokl=%d tokc=0x%x\n",
4446                                l, a, tokl, tokc);
4447#endif
4448                        if (a == ch) {
4449                            inp();
4450                            tok = TOK_DUMMY; /* dummy token for double tokens */
4451                        }
4452                        /* check for op=, valid for * / % + - << >> & ^ | */
4453                        if (ch == '=' &&
4454                                ((tokl >= 1 && tokl <= 3)
4455                                        || (tokl >=6 && tokl <= 8)) ) {
4456                            inp();
4457                            tok = TOK_OP_ASSIGNMENT;
4458                        }
4459                        break;
4460                    }
4461                    opIndex++;
4462                }
4463                if (l == 0) {
4464                    tokl = 0;
4465                    tokc = 0;
4466                }
4467            }
4468        }
4469
4470    done: ;
4471#if 0
4472        {
4473            String buf;
4474            decodeToken(buf, tok, true);
4475            fprintf(stderr, "%s\n", buf.getUnwrapped());
4476        }
4477#endif
4478    }
4479
4480    void doDefine() {
4481        mbSuppressMacroExpansion = true;
4482        next();
4483        mbSuppressMacroExpansion = false;
4484        tokenid_t name = tok;
4485        if (ch == '(') {
4486            error("Defines with arguments not supported");
4487            return;
4488        }
4489        while (isspace(ch)) {
4490            inp();
4491        }
4492        String value;
4493        bool appendToValue = true;
4494        while (ch != '\n' && ch != EOF) {
4495            // Check for '//' comments.
4496            if (appendToValue && ch == '/') {
4497                inp();
4498                if (ch == '/') {
4499                    appendToValue = false;
4500                } else {
4501                    value.append('/');
4502                }
4503            }
4504            if (appendToValue && ch != EOF) {
4505                value.append(ch);
4506            }
4507            inp();
4508        }
4509        char* pDefn = (char*)mGlobalArena.alloc(value.len() + 1);
4510        memcpy(pDefn, value.getUnwrapped(), value.len());
4511        pDefn[value.len()] = 0;
4512        mTokenTable[name].mpMacroDefinition = pDefn;
4513#if 0
4514        {
4515            String buf;
4516            decodeToken(buf, name, true);
4517            fprintf(stderr, "define %s = \"%s\"\n", buf.getUnwrapped(), pDefn);
4518        }
4519#endif
4520    }
4521
4522    void doPragma() {
4523        // # pragma name(val)
4524        int state = 0;
4525        while(ch != EOF && ch != '\n' && state < 10) {
4526            switch(state) {
4527                case 0:
4528                    if (isspace(ch)) {
4529                        inp();
4530                    } else {
4531                        state++;
4532                    }
4533                    break;
4534                case 1:
4535                    if (isalnum(ch)) {
4536                        mPragmas.append(ch);
4537                        inp();
4538                    } else if (ch == '(') {
4539                        mPragmas.append(0);
4540                        inp();
4541                        state++;
4542                    } else {
4543                        state = 11;
4544                    }
4545                    break;
4546                case 2:
4547                    if (isalnum(ch)) {
4548                        mPragmas.append(ch);
4549                        inp();
4550                    } else if (ch == ')') {
4551                        mPragmas.append(0);
4552                        inp();
4553                        state = 10;
4554                    } else {
4555                        state = 11;
4556                    }
4557                    break;
4558            }
4559        }
4560        if(state != 10) {
4561            error("Unexpected pragma syntax");
4562        }
4563        mPragmaStringCount += 2;
4564    }
4565
4566    void doLine() {
4567        // # line number { "filename "}
4568        next();
4569        if (tok != TOK_NUM) {
4570            error("Expected a line-number");
4571        } else {
4572            mLineNumber = tokc-1; // The end-of-line will increment it.
4573        }
4574        while(ch != EOF && ch != '\n') {
4575            inp();
4576        }
4577    }
4578
4579    virtual void verror(const char* fmt, va_list ap) {
4580        mErrorBuf.printf("%ld: ", mLineNumber);
4581        mErrorBuf.vprintf(fmt, ap);
4582        mErrorBuf.printf("\n");
4583    }
4584
4585    void skip(intptr_t c) {
4586        if (!accept(c)) {
4587            error("'%c' expected", c);
4588        }
4589    }
4590
4591    bool accept(intptr_t c) {
4592        if (tok == c) {
4593            next();
4594            return true;
4595        }
4596        return false;
4597    }
4598
4599    bool acceptStringLiteral() {
4600        if (tok == '"') {
4601            pGen->leaR0((int) glo, mkpCharPtr, ET_RVALUE);
4602            // This while loop merges multiple adjacent string constants.
4603            while (tok == '"') {
4604                while (ch != '"' && ch != EOF) {
4605                    *allocGlobalSpace(1,1) = getq();
4606                }
4607                if (ch != '"') {
4608                    error("Unterminated string constant.");
4609                }
4610                inp();
4611                next();
4612            }
4613            /* Null terminate */
4614            *glo = 0;
4615            /* align heap */
4616            allocGlobalSpace(1,(char*) (((intptr_t) glo + 4) & -4) - glo);
4617
4618            return true;
4619        }
4620        return false;
4621    }
4622
4623    void linkGlobal(tokenid_t t, bool isFunction) {
4624        VariableInfo* pVI = VI(t);
4625        void* n = NULL;
4626        if (mpSymbolLookupFn) {
4627            n = mpSymbolLookupFn(mpSymbolLookupContext, nameof(t));
4628        }
4629        if (pVI->pType == NULL) {
4630            if (isFunction) {
4631                pVI->pType = mkpIntFn;
4632            } else {
4633                pVI->pType = mkpInt;
4634            }
4635        }
4636        pVI->pAddress = n;
4637    }
4638
4639    void unaryOrAssignment() {
4640        unary();
4641        if (accept('=')) {
4642            checkLVal();
4643            pGen->pushR0();
4644            expr();
4645            pGen->forceR0RVal();
4646            pGen->storeR0ToTOS();
4647        } else if (tok == TOK_OP_ASSIGNMENT) {
4648            int t = tokc;
4649            next();
4650            checkLVal();
4651            pGen->pushR0();
4652            pGen->forceR0RVal();
4653            pGen->pushR0();
4654            expr();
4655            pGen->forceR0RVal();
4656            pGen->genOp(t);
4657            pGen->storeR0ToTOS();
4658        }
4659    }
4660
4661    /* Parse and evaluate a unary expression.
4662     */
4663    void unary() {
4664        tokenid_t t;
4665        intptr_t a;
4666        t = 0;
4667        if (acceptStringLiteral()) {
4668            // Nothing else to do.
4669        } else {
4670            int c = tokl;
4671            a = tokc;
4672            double ad = tokd;
4673            t = tok;
4674            next();
4675            if (t == TOK_NUM) {
4676                pGen->li(a);
4677            } else if (t == TOK_NUM_FLOAT) {
4678                // Align to 4-byte boundary
4679                glo = (char*) (((intptr_t) glo + 3) & -4);
4680                * (float*) glo = (float) ad;
4681                pGen->loadFloat((int) glo, mkpFloat);
4682                glo += 4;
4683            } else if (t == TOK_NUM_DOUBLE) {
4684                // Align to 8-byte boundary
4685                glo = (char*) (((intptr_t) glo + 7) & -8);
4686                * (double*) glo = ad;
4687                pGen->loadFloat((int) glo, mkpDouble);
4688                glo += 8;
4689            } else if (c == 2) {
4690                /* -, +, !, ~ */
4691                unary();
4692                pGen->forceR0RVal();
4693                if (t == '!')
4694                    pGen->gUnaryCmp(a);
4695                else if (t == '+') {
4696                    // ignore unary plus.
4697                } else {
4698                    pGen->genUnaryOp(a);
4699                }
4700            } else if (c == 11) {
4701                // pre increment / pre decrement
4702                unary();
4703                doIncDec(a == OP_INCREMENT, 0);
4704            }
4705            else if (t == '(') {
4706                // It's either a cast or an expression
4707                Type* pCast = acceptCastTypeDeclaration();
4708                if (pCast) {
4709                    skip(')');
4710                    unary();
4711                    pGen->forceR0RVal();
4712                    pGen->castR0(pCast);
4713                } else {
4714                    commaExpr();
4715                    skip(')');
4716                }
4717            } else if (t == '*') {
4718                /* This is a pointer dereference.
4719                 */
4720                unary();
4721                doPointer();
4722            } else if (t == '&') {
4723                unary();
4724                doAddressOf();
4725            } else if (t == EOF ) {
4726                error("Unexpected EOF.");
4727            } else if (t == ';') {
4728                error("Unexpected ';'");
4729            } else if (!checkSymbol(t)) {
4730                // Don't have to do anything special here, the error
4731                // message was printed by checkSymbol() above.
4732            } else {
4733                if (!isDefined(t)) {
4734                    mGlobals.add(t);
4735                    // printf("Adding new global function %s\n", nameof(t));
4736                }
4737                VariableInfo* pVI = VI(t);
4738                int n = (intptr_t) pVI->pAddress;
4739                /* forward reference: try our lookup function */
4740                if (!n) {
4741                    linkGlobal(t, tok == '(');
4742                    n = (intptr_t) pVI->pAddress;
4743                    if (!n && tok != '(') {
4744                        error("Undeclared variable %s", nameof(t));
4745                    }
4746                }
4747                if (tok != '(') {
4748                    /* variable or function name */
4749                    if (!n) {
4750                        linkGlobal(t, false);
4751                        n = (intptr_t) pVI->pAddress;
4752                        if (!n) {
4753                            error("Undeclared variable %s", nameof(t));
4754                        }
4755                    }
4756                }
4757                // load a variable
4758                Type* pVal;
4759                ExpressionType et;
4760                if (pVI->pType->tag == TY_ARRAY) {
4761                    pVal = pVI->pType;
4762                    et = ET_RVALUE;
4763                } else {
4764                    pVal = createPtrType(pVI->pType);
4765                    et = ET_LVALUE;
4766                }
4767                if (n) {
4768                    int tag = pVal->pHead->tag;
4769                    if (tag == TY_FUNC) {
4770                        et = ET_RVALUE;
4771                    }
4772                    pGen->leaR0(n, pVal, et);
4773                } else {
4774                    pVI->pForward = (void*) pGen->leaForward(
4775                            (int) pVI->pForward, pVal);
4776                }
4777            }
4778        }
4779
4780        /* Now handle postfix operators */
4781        for(;;) {
4782            if (tokl == 11) {
4783                // post inc / post dec
4784                doIncDec(tokc == OP_INCREMENT, true);
4785                next();
4786            } else if (accept('[')) {
4787                // Array reference
4788                pGen->forceR0RVal();
4789                pGen->pushR0();
4790                commaExpr();
4791                pGen->forceR0RVal();
4792                pGen->genOp(OP_PLUS);
4793                doPointer();
4794                skip(']');
4795            } else if (accept('.')) {
4796                // struct element
4797                pGen->forceR0RVal();
4798                Type* pStruct = pGen->getR0Type();
4799                if (pStruct->tag == TY_STRUCT) {
4800                    doStructMember(pStruct, true);
4801                } else {
4802                    error("expected a struct value to the left of '.'");
4803                }
4804            } else if (accept(TOK_OP_ARROW)) {
4805                pGen->forceR0RVal();
4806                Type* pPtr = pGen->getR0Type();
4807                if (pPtr->tag == TY_POINTER && pPtr->pHead->tag == TY_STRUCT) {
4808                    pGen->loadR0FromR0();
4809                    doStructMember(pPtr->pHead, false);
4810                } else {
4811                    error("Expected a pointer to a struct to the left of '->'");
4812                }
4813            } else  if (accept('(')) {
4814                /* function call */
4815                Type* pDecl = NULL;
4816                VariableInfo* pVI = NULL;
4817                Type* pFn = pGen->getR0Type();
4818                if (pFn->tag == TY_POINTER && pFn->pHead->tag == TY_FUNC) {
4819                    pDecl = pFn->pHead;
4820                    pGen->pushR0();
4821                    Type* pArgList = pDecl->pTail;
4822                    bool varArgs = pArgList == NULL;
4823                    /* push args and invert order */
4824                    a = pGen->beginFunctionCallArguments();
4825                    int l = 0;
4826                    int argCount = 0;
4827                    while (tok != ')' && tok != EOF) {
4828                        if (! varArgs && !pArgList) {
4829                            error("Unexpected argument.");
4830                        }
4831                        expr();
4832                        pGen->forceR0RVal();
4833                        Type* pTargetType;
4834                        if (pArgList) {
4835                            pTargetType = pArgList->pHead;
4836                            pArgList = pArgList->pTail;
4837                        } else {
4838                            // This is a ... function, just pass arguments in their
4839                            // natural type.
4840                            pTargetType = pGen->getR0Type();
4841                            if (pTargetType->tag == TY_FLOAT) {
4842                                pTargetType = mkpDouble;
4843                            } else if (pTargetType->tag == TY_ARRAY) {
4844                                // Pass arrays by pointer.
4845                                pTargetType = pTargetType->pTail;
4846                            }
4847                        }
4848                        if (pTargetType->tag == TY_VOID) {
4849                            error("Can't pass void value for argument %d",
4850                                  argCount + 1);
4851                        } else {
4852                            l += pGen->storeR0ToArg(l, pTargetType);
4853                        }
4854                        if (accept(',')) {
4855                            // fine
4856                        } else if ( tok != ')') {
4857                            error("Expected ',' or ')'");
4858                        }
4859                        argCount += 1;
4860                    }
4861                    if (! varArgs && pArgList) {
4862                        error("Expected more argument(s). Saw %d", argCount);
4863                    }
4864                    pGen->endFunctionCallArguments(pDecl, a, l);
4865                    skip(')');
4866                    pGen->callIndirect(l, pDecl);
4867                    pGen->adjustStackAfterCall(pDecl, l, true);
4868                } else {
4869                    error("Expected a function value to left of '('.");
4870                }
4871            } else {
4872                break;
4873            }
4874        }
4875    }
4876
4877    void doStructMember(Type* pStruct, bool isDot) {
4878        Type* pStructElement = lookupStructMember(pStruct, tok);
4879        if (pStructElement) {
4880            next();
4881            pGen->addStructOffsetR0(pStructElement->length, createPtrType(pStructElement->pHead));
4882        } else {
4883            String buf;
4884            decodeToken(buf, tok, true);
4885            error("Expected a struct member to the right of '%s', got %s",
4886                    isDot ? "." : "->", buf.getUnwrapped());
4887        }
4888    }
4889
4890    void doIncDec(int isInc, int isPost) {
4891        // R0 already has the lval
4892        checkLVal();
4893        int lit = isInc ? 1 : -1;
4894        pGen->pushR0();
4895        pGen->loadR0FromR0();
4896        int tag = pGen->getR0Type()->tag;
4897        if (!(tag == TY_INT || tag == TY_SHORT || tag == TY_CHAR ||
4898                tag == TY_POINTER)) {
4899            error("++/-- illegal for this type. %d", tag);
4900        }
4901        if (isPost) {
4902            pGen->over();
4903            pGen->pushR0();
4904            pGen->li(lit);
4905            pGen->genOp(OP_PLUS);
4906            pGen->storeR0ToTOS();
4907            pGen->popR0();
4908        } else {
4909            pGen->pushR0();
4910            pGen->li(lit);
4911            pGen->genOp(OP_PLUS);
4912            pGen->over();
4913            pGen->storeR0ToTOS();
4914            pGen->popR0();
4915        }
4916    }
4917
4918    void doPointer() {
4919        pGen->forceR0RVal();
4920        Type* pR0Type = pGen->getR0Type();
4921        if (pR0Type->tag != TY_POINTER) {
4922            error("Expected a pointer type.");
4923        } else {
4924            if (pR0Type->pHead->tag != TY_FUNC) {
4925                pGen->setR0ExpressionType(ET_LVALUE);
4926            }
4927        }
4928    }
4929
4930    void doAddressOf() {
4931        Type* pR0 = pGen->getR0Type();
4932        bool isFuncPtr = pR0->tag == TY_POINTER && pR0->pHead->tag == TY_FUNC;
4933        if ((! isFuncPtr) && pGen->getR0ExpressionType() != ET_LVALUE) {
4934            error("Expected an lvalue");
4935        }
4936        Type* pR0Type = pGen->getR0Type();
4937        pGen->setR0ExpressionType(ET_RVALUE);
4938    }
4939
4940    /* Recursive descent parser for binary operations.
4941     */
4942    void binaryOp(int level) {
4943        intptr_t t, a;
4944        t = 0;
4945        if (level-- == 1)
4946            unaryOrAssignment();
4947        else {
4948            binaryOp(level);
4949            a = 0;
4950            while (level == tokl) {
4951                t = tokc;
4952                next();
4953                pGen->forceR0RVal();
4954                if (level > 8) {
4955                    a = pGen->gtst(t == OP_LOGICAL_OR, a); /* && and || output code generation */
4956                    binaryOp(level);
4957                } else {
4958                    pGen->pushR0();
4959                    binaryOp(level);
4960                    // Check for syntax error.
4961                    if (pGen->getR0Type() == NULL) {
4962                        // We failed to parse a right-hand argument.
4963                        // Push a dummy value so we don't fail
4964                        pGen->li(0);
4965                    }
4966                    pGen->forceR0RVal();
4967                    if ((level == 4) | (level == 5)) {
4968                        pGen->gcmp(t);
4969                    } else {
4970                        pGen->genOp(t);
4971                    }
4972                }
4973            }
4974            /* && and || output code generation */
4975            if (a && level > 8) {
4976                pGen->forceR0RVal();
4977                a = pGen->gtst(t == OP_LOGICAL_OR, a);
4978                pGen->li(t != OP_LOGICAL_OR);
4979                int b = pGen->gjmp(0);
4980                pGen->gsym(a);
4981                pGen->li(t == OP_LOGICAL_OR);
4982                pGen->gsym(b);
4983            }
4984        }
4985    }
4986
4987    void commaExpr() {
4988        for(;;) {
4989            expr();
4990            if (!accept(',')) {
4991                break;
4992            }
4993        }
4994    }
4995
4996    void expr() {
4997        binaryOp(11);
4998    }
4999
5000    int test_expr() {
5001        commaExpr();
5002        pGen->forceR0RVal();
5003        return pGen->gtst(0, 0);
5004    }
5005
5006    void block(intptr_t* breakLabel, intptr_t continueAddress, bool outermostFunctionBlock) {
5007        intptr_t a, n, t;
5008
5009        Type* pBaseType;
5010        if ((pBaseType = acceptPrimitiveType(true))) {
5011            /* declarations */
5012            localDeclarations(pBaseType);
5013        } else if (tok == TOK_IF) {
5014            next();
5015            skip('(');
5016            a = test_expr();
5017            skip(')');
5018            block(breakLabel, continueAddress, false);
5019            if (tok == TOK_ELSE) {
5020                next();
5021                n = pGen->gjmp(0); /* jmp */
5022                pGen->gsym(a);
5023                block(breakLabel, continueAddress, false);
5024                pGen->gsym(n); /* patch else jmp */
5025            } else {
5026                pGen->gsym(a); /* patch if test */
5027            }
5028        } else if ((tok == TOK_WHILE) | (tok == TOK_FOR)) {
5029            t = tok;
5030            next();
5031            skip('(');
5032            if (t == TOK_WHILE) {
5033                n = pCodeBuf->getPC(); // top of loop, target of "next" iteration
5034                a = test_expr();
5035            } else {
5036                if (tok != ';')
5037                    commaExpr();
5038                skip(';');
5039                n = pCodeBuf->getPC();
5040                a = 0;
5041                if (tok != ';')
5042                    a = test_expr();
5043                skip(';');
5044                if (tok != ')') {
5045                    t = pGen->gjmp(0);
5046                    commaExpr();
5047                    pGen->gjmp(n - pCodeBuf->getPC() - pGen->jumpOffset());
5048                    pGen->gsym(t);
5049                    n = t + 4;
5050                }
5051            }
5052            skip(')');
5053            block(&a, n, false);
5054            pGen->gjmp(n - pCodeBuf->getPC() - pGen->jumpOffset()); /* jmp */
5055            pGen->gsym(a);
5056        } else if (tok == '{') {
5057            if (! outermostFunctionBlock) {
5058                mLocals.pushLevel();
5059            }
5060            next();
5061            while (tok != '}' && tok != EOF)
5062                block(breakLabel, continueAddress, false);
5063            skip('}');
5064            if (! outermostFunctionBlock) {
5065                mLocals.popLevel();
5066            }
5067        } else {
5068            if (accept(TOK_RETURN)) {
5069                if (tok != ';') {
5070                    commaExpr();
5071                    pGen->forceR0RVal();
5072                    if (pReturnType->tag == TY_VOID) {
5073                        error("Must not return a value from a void function");
5074                    } else {
5075                        pGen->convertR0(pReturnType);
5076                    }
5077                } else {
5078                    if (pReturnType->tag != TY_VOID) {
5079                        error("Must specify a value here");
5080                    }
5081                }
5082                rsym = pGen->gjmp(rsym); /* jmp */
5083            } else if (accept(TOK_BREAK)) {
5084                if (breakLabel) {
5085                    *breakLabel = pGen->gjmp(*breakLabel);
5086                } else {
5087                    error("break statement must be within a for, do, while, or switch statement");
5088                }
5089            } else if (accept(TOK_CONTINUE)) {
5090                if (continueAddress) {
5091                    pGen->gjmp(continueAddress - pCodeBuf->getPC() - pGen->jumpOffset());
5092                } else {
5093                    error("continue statement must be within a for, do, or while statement");
5094                }
5095            } else if (tok != ';')
5096                commaExpr();
5097            skip(';');
5098        }
5099    }
5100
5101    static bool typeEqual(Type* a, Type* b) {
5102        if (a == b) {
5103            return true;
5104        }
5105        if (a == NULL || b == NULL) {
5106            return false;
5107        }
5108        TypeTag at = a->tag;
5109        if (at != b->tag) {
5110            return false;
5111        }
5112        if (at == TY_POINTER) {
5113            return typeEqual(a->pHead, b->pHead);
5114        } else if (at == TY_ARRAY) {
5115            return a->length == b->length && typeEqual(a->pHead, b->pHead);
5116        } else if (at == TY_FUNC || at == TY_PARAM) {
5117            return typeEqual(a->pHead, b->pHead)
5118                && typeEqual(a->pTail, b->pTail);
5119        } else if (at == TY_STRUCT) {
5120            return a->pHead == b->pHead;
5121        }
5122        return true;
5123    }
5124
5125    Type* createType(TypeTag tag, Type* pHead, Type* pTail) {
5126        assert(tag >= TY_UNKNOWN && tag <= TY_PARAM);
5127        Type* pType = (Type*) mpCurrentArena->alloc(sizeof(Type));
5128        memset(pType, 0, sizeof(*pType));
5129        pType->storageClass = SC_DEFAULT;
5130        pType->tag = tag;
5131        pType->pHead = pHead;
5132        pType->pTail = pTail;
5133        return pType;
5134    }
5135
5136    Type* createPtrType(Type* pType) {
5137        return createType(TY_POINTER, pType, NULL);
5138    }
5139
5140    /**
5141     * Try to print a type in declaration order
5142     */
5143    void decodeType(String& buffer, Type* pType) {
5144        buffer.clear();
5145        if (pType == NULL) {
5146            buffer.appendCStr("null");
5147            return;
5148        }
5149        decodeTypeImp(buffer, pType);
5150    }
5151
5152    void decodeTypeImp(String& buffer, Type* pType) {
5153        decodeTypeImpPrefix(buffer, pType);
5154        decodeId(buffer, pType->id);
5155        decodeTypeImpPostfix(buffer, pType);
5156    }
5157
5158    void decodeId(String& buffer, tokenid_t id) {
5159        if (id) {
5160            String temp;
5161            decodeToken(temp, id, false);
5162            buffer.append(temp);
5163        }
5164    }
5165
5166    void decodeTypeImpPrefix(String& buffer, Type* pType) {
5167        TypeTag tag = pType->tag;
5168
5169        if ((tag >= TY_INT && tag <= TY_DOUBLE) || tag == TY_STRUCT) {
5170            switch (tag) {
5171                case TY_INT:
5172                    buffer.appendCStr("int");
5173                    break;
5174                case TY_SHORT:
5175                    buffer.appendCStr("short");
5176                    break;
5177                case TY_CHAR:
5178                    buffer.appendCStr("char");
5179                    break;
5180                case TY_VOID:
5181                    buffer.appendCStr("void");
5182                    break;
5183                case TY_FLOAT:
5184                    buffer.appendCStr("float");
5185                    break;
5186                case TY_DOUBLE:
5187                    buffer.appendCStr("double");
5188                    break;
5189                case TY_STRUCT:
5190                {
5191                    bool isStruct = (pType->pHead->alignment & 0x80000000) != 0;
5192                    buffer.appendCStr(isStruct ? "struct" : "union");
5193                    if (pType->pHead && pType->pHead->structTag) {
5194                        buffer.append(' ');
5195                        decodeId(buffer, pType->pHead->structTag);
5196                    }
5197                }
5198                    break;
5199                default:
5200                    break;
5201            }
5202            buffer.append(' ');
5203        }
5204
5205        switch (tag) {
5206            case TY_INT:
5207                break;
5208            case TY_SHORT:
5209                break;
5210            case TY_CHAR:
5211                break;
5212            case TY_VOID:
5213                 break;
5214            case TY_FLOAT:
5215                 break;
5216            case TY_DOUBLE:
5217                break;
5218            case TY_POINTER:
5219                decodeTypeImpPrefix(buffer, pType->pHead);
5220                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
5221                    buffer.append('(');
5222                }
5223                buffer.append('*');
5224                break;
5225            case TY_ARRAY:
5226                decodeTypeImpPrefix(buffer, pType->pHead);
5227                break;
5228            case TY_STRUCT:
5229                break;
5230            case TY_FUNC:
5231                decodeTypeImp(buffer, pType->pHead);
5232                break;
5233            case TY_PARAM:
5234                decodeTypeImp(buffer, pType->pHead);
5235                break;
5236            default:
5237                String temp;
5238                temp.printf("Unknown tag %d", pType->tag);
5239                buffer.append(temp);
5240                break;
5241        }
5242    }
5243
5244    void decodeTypeImpPostfix(String& buffer, Type* pType) {
5245        TypeTag tag = pType->tag;
5246
5247        switch(tag) {
5248            case TY_POINTER:
5249                if(pType->pHead && pType->pHead->tag == TY_FUNC) {
5250                    buffer.append(')');
5251                }
5252                decodeTypeImpPostfix(buffer, pType->pHead);
5253                break;
5254            case TY_ARRAY:
5255                {
5256                    String temp;
5257                    temp.printf("[%d]", pType->length);
5258                    buffer.append(temp);
5259                }
5260                break;
5261            case TY_STRUCT:
5262                if (pType->pHead->length >= 0) {
5263                    buffer.appendCStr(" {");
5264                    for(Type* pArg = pType->pTail; pArg; pArg = pArg->pTail) {
5265                        decodeTypeImp(buffer, pArg->pHead);
5266                        buffer.appendCStr(";");
5267                    }
5268                    buffer.append('}');
5269                }
5270                break;
5271            case TY_FUNC:
5272                buffer.append('(');
5273                for(Type* pArg = pType->pTail; pArg; pArg = pArg->pTail) {
5274                    decodeTypeImp(buffer, pArg);
5275                    if (pArg->pTail) {
5276                        buffer.appendCStr(", ");
5277                    }
5278                }
5279                buffer.append(')');
5280                break;
5281            default:
5282                break;
5283        }
5284    }
5285
5286    void printType(Type* pType) {
5287        String buffer;
5288        decodeType(buffer, pType);
5289        fprintf(stderr, "%s\n", buffer.getUnwrapped());
5290    }
5291
5292    void insertTypeSpecifier(Type** ppType, TypeTag tag) {
5293        if (! *ppType) {
5294            *ppType = createType(tag, NULL, NULL);
5295        } else {
5296            if ((*ppType)->tag != TY_UNKNOWN) {
5297                error("Only one type specifier allowed.");
5298            } else {
5299                (*ppType)->tag = tag;
5300            }
5301        }
5302    }
5303
5304    void insertStorageClass(Type** ppType, StorageClass storageClass) {
5305        if (! *ppType) {
5306            *ppType = createType(TY_UNKNOWN, NULL, NULL);
5307        }
5308        if ((*ppType)->storageClass != SC_DEFAULT) {
5309            error("Only one storage class allowed.");
5310        } else {
5311            (*ppType)->storageClass = storageClass;
5312        }
5313    }
5314
5315    Type* acceptPrimitiveType(bool allowStorageClass) {
5316        Type* pType = NULL;
5317        for (bool keepGoing = true; keepGoing;) {
5318            switch(tok) {
5319            case TOK_AUTO:
5320                insertStorageClass(&pType, SC_AUTO);
5321                break;
5322            case TOK_REGISTER:
5323                insertStorageClass(&pType, SC_REGISTER);
5324                break;
5325            case TOK_STATIC:
5326                insertStorageClass(&pType, SC_STATIC);
5327                break;
5328            case TOK_EXTERN:
5329                insertStorageClass(&pType, SC_EXTERN);
5330                break;
5331            case TOK_TYPEDEF:
5332                insertStorageClass(&pType, SC_TYPEDEF);
5333                break;
5334            case TOK_INT:
5335                insertTypeSpecifier(&pType, TY_INT);
5336                break;
5337            case TOK_SHORT:
5338                insertTypeSpecifier(&pType, TY_SHORT);
5339                break;
5340            case TOK_CHAR:
5341                insertTypeSpecifier(&pType, TY_CHAR);
5342                break;
5343            case TOK_VOID:
5344                insertTypeSpecifier(&pType, TY_VOID);
5345                break;
5346            case TOK_FLOAT:
5347                insertTypeSpecifier(&pType, TY_FLOAT);
5348                break;
5349            case TOK_DOUBLE:
5350                insertTypeSpecifier(&pType, TY_DOUBLE);
5351                break;
5352            case TOK_STRUCT:
5353            case TOK_UNION:
5354            {
5355                insertTypeSpecifier(&pType, TY_STRUCT);
5356                bool isStruct = (tok == TOK_STRUCT);
5357                next();
5358                pType = acceptStruct(pType, isStruct);
5359                keepGoing = false;
5360            }
5361                break;
5362            default:
5363                // Is it a typedef?
5364                if (isSymbol(tok)) {
5365                    VariableInfo* pV = VI(tok);
5366                    if (pV && pV->pType->storageClass == SC_TYPEDEF) {
5367                        if (! pType) {
5368                            pType = createType(TY_UNKNOWN, NULL, NULL);
5369                        }
5370                        StorageClass storageClass = pType->storageClass;
5371                        *pType = *pV->pType;
5372                        pType->storageClass = storageClass;
5373                    } else {
5374                        keepGoing = false;
5375                    }
5376                } else {
5377                    keepGoing = false;
5378                }
5379            }
5380            if (keepGoing) {
5381                next();
5382            }
5383        }
5384        if (pType) {
5385            if (pType->tag == TY_UNKNOWN) {
5386                pType->tag = TY_INT;
5387            }
5388            if (allowStorageClass) {
5389                switch(pType->storageClass) {
5390                case SC_AUTO: error("auto not supported."); break;
5391                case SC_REGISTER: error("register not supported."); break;
5392                case SC_STATIC: error("static not supported."); break;
5393                case SC_EXTERN: error("extern not supported."); break;
5394                default: break;
5395                }
5396            } else {
5397                if (pType->storageClass != SC_DEFAULT) {
5398                    error("An explicit storage class is not allowed in this type declaration");
5399                }
5400            }
5401        }
5402        return pType;
5403    }
5404
5405    Type* acceptStruct(Type* pStructType, bool isStruct) {
5406        tokenid_t structTag = acceptSymbol();
5407        bool isDeclaration = accept('{');
5408        bool fail = false;
5409
5410        if (structTag) {
5411            Token* pToken = &mTokenTable[structTag];
5412            VariableInfo* pStructInfo = pToken->mpStructInfo;
5413            bool needToDeclare = !pStructInfo;
5414            if (pStructInfo) {
5415                if (isDeclaration) {
5416                    if (mpCurrentSymbolStack->isStructTagDefinedAtCurrentLevel(structTag)) {
5417                        if (pStructInfo->pType->pHead->length == -1) {
5418                            // we're filling in a forward declaration.
5419                            needToDeclare = false;
5420                        } else {
5421                            error("A struct with the same name is already defined at this level.");
5422                            fail = true;
5423                        }
5424                    } else {
5425                        needToDeclare = true;
5426                    }
5427                }
5428                if (!fail) {
5429                     assert(pStructInfo->isStructTag);
5430                     pStructType->pHead = pStructInfo->pType;
5431                     pStructType->pTail = pStructType->pHead->pTail;
5432                }
5433            }
5434
5435            if (needToDeclare) {
5436                // This is a new struct name
5437                pToken->mpStructInfo = mpCurrentSymbolStack->addStructTag(structTag);
5438                StorageClass storageClass = pStructType->storageClass;
5439                pStructType = createType(TY_STRUCT, NULL, NULL);
5440                pStructType->structTag = structTag;
5441                pStructType->pHead = pStructType;
5442                pStructType->storageClass = storageClass;
5443                if (! isDeclaration) {
5444                    // A forward declaration
5445                    pStructType->length = -1;
5446                }
5447                pToken->mpStructInfo->pType = pStructType;
5448            }
5449        } else {
5450            // An anonymous struct
5451            pStructType->pHead = pStructType;
5452        }
5453
5454        if (isDeclaration) {
5455            size_t offset = 0;
5456            size_t structSize = 0;
5457            size_t structAlignment = 0;
5458            Type** pParamHolder = & pStructType->pHead->pTail;
5459            while (tok != '}' && tok != EOF) {
5460                Type* pPrimitiveType = expectPrimitiveType(false);
5461                if (pPrimitiveType) {
5462                    while (tok != ';' && tok != EOF) {
5463                        Type* pItem = acceptDeclaration(pPrimitiveType, true, false);
5464                        if (!pItem) {
5465                            break;
5466                        }
5467                        if (lookupStructMember(pStructType, pItem->id)) {
5468                            String buf;
5469                            decodeToken(buf, pItem->id, false);
5470                            error("Duplicate struct member %s", buf.getUnwrapped());
5471                        }
5472                        Type* pStructElement = createType(TY_PARAM, pItem, NULL);
5473                        size_t alignment = pGen->alignmentOf(pItem);
5474                        if (alignment > structAlignment) {
5475                            structAlignment = alignment;
5476                        }
5477                        size_t alignmentMask = alignment - 1;
5478                        offset = (offset + alignmentMask) & ~alignmentMask;
5479                        pStructElement->length = offset;
5480                        size_t size = pGen->sizeOf(pItem);
5481                        if (isStruct) {
5482                            offset += size;
5483                            structSize = offset;
5484                        } else {
5485                            if (size >= structSize) {
5486                                structSize = size;
5487                            }
5488                        }
5489                        *pParamHolder = pStructElement;
5490                        pParamHolder = &pStructElement->pTail;
5491                        accept(',');
5492                    }
5493                    skip(';');
5494                } else {
5495                    // Some sort of syntax error, skip token and keep trying
5496                    next();
5497                }
5498            }
5499            if (!fail) {
5500                pStructType->pHead->length = structSize;
5501                pStructType->pHead->alignment = structAlignment | (isStruct << 31);
5502            }
5503            skip('}');
5504        }
5505        if (fail) {
5506            pStructType = NULL;
5507        }
5508        return pStructType;
5509    }
5510
5511    Type* lookupStructMember(Type* pStruct, tokenid_t memberId) {
5512        for(Type* pStructElement = pStruct->pHead->pTail; pStructElement; pStructElement = pStructElement->pTail) {
5513            if (pStructElement->pHead->id == memberId) {
5514                return pStructElement;
5515            }
5516        }
5517        return NULL;
5518    }
5519
5520    Type* acceptDeclaration(Type* pType, bool nameAllowed, bool nameRequired) {
5521        tokenid_t declName = 0;
5522        bool reportFailure = false;
5523        StorageClass storageClass = pType->storageClass;
5524        pType = acceptDecl2(pType, declName, nameAllowed,
5525                                  nameRequired, reportFailure);
5526        if (declName) {
5527            // Clone the parent type so we can set a unique ID
5528            Type* pOldType = pType;
5529            pType = createType(pType->tag, pType->pHead, pType->pTail);
5530            *pType = *pOldType;
5531            pType->id = declName;
5532            pType->storageClass = storageClass;
5533        } else if (nameRequired) {
5534            error("Expected a variable name");
5535        }
5536#if 0
5537        fprintf(stderr, "Parsed a declaration:       ");
5538        printType(pType);
5539#endif
5540        if (reportFailure) {
5541            return NULL;
5542        }
5543        return pType;
5544    }
5545
5546    Type* expectDeclaration(Type* pBaseType) {
5547        bool nameRequired = pBaseType->tag != TY_STRUCT;
5548        Type* pType = acceptDeclaration(pBaseType, true, nameRequired);
5549        if (! pType) {
5550            error("Expected a declaration");
5551        }
5552        return pType;
5553    }
5554
5555    /* Used for accepting types that appear in casts */
5556    Type* acceptCastTypeDeclaration() {
5557        Type* pType = acceptPrimitiveType(false);
5558        if (pType) {
5559            pType = acceptDeclaration(pType, false, false);
5560        }
5561        return pType;
5562    }
5563
5564    Type* expectCastTypeDeclaration() {
5565        Type* pType = acceptCastTypeDeclaration();
5566        if (! pType) {
5567            error("Expected a declaration");
5568        }
5569        return pType;
5570    }
5571
5572    Type* acceptDecl2(Type* pType, tokenid_t& declName,
5573                      bool nameAllowed, bool nameRequired,
5574                      bool& reportFailure) {
5575        while (accept('*')) {
5576            pType = createType(TY_POINTER, pType, NULL);
5577        }
5578        pType = acceptDecl3(pType, declName, nameAllowed, nameRequired,
5579                            reportFailure);
5580        return pType;
5581    }
5582
5583    Type* acceptDecl3(Type* pType, tokenid_t& declName,
5584                      bool nameAllowed, bool nameRequired,
5585                      bool& reportFailure) {
5586        // direct-dcl :
5587        //   name
5588        //  (dcl)
5589        //   direct-dcl()
5590        //   direct-dcl[]
5591        Type* pNewHead = NULL;
5592        if (accept('(')) {
5593            pNewHead = acceptDecl2(pNewHead, declName, nameAllowed,
5594                                nameRequired, reportFailure);
5595            skip(')');
5596        } else if ((declName = acceptSymbol()) != 0) {
5597            if (nameAllowed == false && declName) {
5598                error("Symbol %s not allowed here", nameof(declName));
5599                reportFailure = true;
5600            }
5601        } else if (nameRequired && ! declName) {
5602            String temp;
5603            decodeToken(temp, tok, true);
5604            error("Expected name. Got %s", temp.getUnwrapped());
5605            reportFailure = true;
5606        }
5607        for(;;) {
5608            if (accept('(')) {
5609                // Function declaration
5610                Type* pTail = acceptArgs(nameAllowed);
5611                pType = createType(TY_FUNC, pType, pTail);
5612                skip(')');
5613            } if (accept('[')) {
5614                if (tok != ']') {
5615                    if (tok != TOK_NUM || tokc <= 0) {
5616                        error("Expected positive integer constant");
5617                    } else {
5618                        Type* pDecayType = createPtrType(pType);
5619                        pType = createType(TY_ARRAY, pType, pDecayType);
5620                        pType->length = tokc;
5621                    }
5622                    next();
5623                }
5624                skip(']');
5625            } else {
5626                break;
5627            }
5628        }
5629
5630        if (pNewHead) {
5631            Type* pA = pNewHead;
5632            while (pA->pHead) {
5633                pA = pA->pHead;
5634            }
5635            pA->pHead = pType;
5636            pType = pNewHead;
5637        }
5638        return pType;
5639    }
5640
5641    Type* acceptArgs(bool nameAllowed) {
5642        Type* pHead = NULL;
5643        Type* pTail = NULL;
5644        for(;;) {
5645            Type* pBaseArg = acceptPrimitiveType(false);
5646            if (pBaseArg) {
5647                Type* pArg = acceptDeclaration(pBaseArg, nameAllowed, false);
5648                if (pArg) {
5649                    Type* pParam = createType(TY_PARAM, pArg, NULL);
5650                    if (!pHead) {
5651                        pHead = pParam;
5652                        pTail = pParam;
5653                    } else {
5654                        pTail->pTail = pParam;
5655                        pTail = pParam;
5656                    }
5657                }
5658            }
5659            if (! accept(',')) {
5660                break;
5661            }
5662        }
5663        return pHead;
5664    }
5665
5666    Type* expectPrimitiveType(bool allowStorageClass) {
5667        Type* pType = acceptPrimitiveType(allowStorageClass);
5668        if (!pType) {
5669            String buf;
5670            decodeToken(buf, tok, true);
5671            error("Expected a type, got %s", buf.getUnwrapped());
5672        }
5673        return pType;
5674    }
5675
5676    void checkLVal() {
5677        if (pGen->getR0ExpressionType() != ET_LVALUE) {
5678            error("Expected an lvalue");
5679        }
5680    }
5681
5682    void addGlobalSymbol(Type* pDecl) {
5683        tokenid_t t = pDecl->id;
5684        VariableInfo* pVI = VI(t);
5685        if(pVI && pVI->pAddress) {
5686            reportDuplicate(t);
5687        }
5688        mGlobals.add(pDecl);
5689    }
5690
5691    void reportDuplicate(tokenid_t t) {
5692        error("Duplicate definition of %s", nameof(t));
5693    }
5694
5695    void addLocalSymbol(Type* pDecl) {
5696        tokenid_t t = pDecl->id;
5697        if (mLocals.isDefinedAtCurrentLevel(t)) {
5698            reportDuplicate(t);
5699        }
5700        mLocals.add(pDecl);
5701    }
5702
5703    bool checkUndeclaredStruct(Type* pBaseType) {
5704        if (pBaseType->tag == TY_STRUCT && pBaseType->length < 0) {
5705            String temp;
5706            decodeToken(temp, pBaseType->structTag, false);
5707            error("Undeclared struct %s", temp.getUnwrapped());
5708            return true;
5709        }
5710        return false;
5711    }
5712
5713    void localDeclarations(Type* pBaseType) {
5714        intptr_t a;
5715
5716        while (pBaseType) {
5717            while (tok != ';' && tok != EOF) {
5718                Type* pDecl = expectDeclaration(pBaseType);
5719                if (!pDecl) {
5720                    break;
5721                }
5722                if (!pDecl->id) {
5723                    break;
5724                }
5725                if (checkUndeclaredStruct(pDecl)) {
5726                    break;
5727                }
5728                addLocalSymbol(pDecl);
5729                if (pDecl->tag == TY_FUNC) {
5730                    if (tok == '{') {
5731                        error("Nested functions are not allowed. Did you forget a '}' ?");
5732                        break;
5733                    }
5734                    // Else it's a forward declaration of a function.
5735                } else if (pDecl->storageClass != SC_TYPEDEF) {
5736                    int variableAddress = 0;
5737                    size_t alignment = pGen->alignmentOf(pDecl);
5738                    assert(alignment > 0);
5739                    size_t alignmentMask = ~ (alignment - 1);
5740                    size_t sizeOf = pGen->sizeOf(pDecl);
5741                    assert(sizeOf > 0);
5742                    loc = (loc + alignment - 1) & alignmentMask;
5743                    size_t alignedSize = (sizeOf + alignment - 1) & alignmentMask;
5744                    loc = loc + alignedSize;
5745                    variableAddress = -loc;
5746                    VI(pDecl->id)->pAddress = (void*) variableAddress;
5747                    if (accept('=')) {
5748                        /* assignment */
5749                        pGen->leaR0(variableAddress, createPtrType(pDecl), ET_LVALUE);
5750                        pGen->pushR0();
5751                        expr();
5752                        pGen->forceR0RVal();
5753                        pGen->storeR0ToTOS();
5754                    }
5755                }
5756                if (tok == ',')
5757                    next();
5758            }
5759            skip(';');
5760            pBaseType = acceptPrimitiveType(true);
5761        }
5762    }
5763
5764    bool checkSymbol() {
5765        return checkSymbol(tok);
5766    }
5767
5768    void decodeToken(String& buffer, tokenid_t token, bool quote) {
5769        if (token == EOF ) {
5770            buffer.printf("EOF");
5771        } else if (token == TOK_NUM) {
5772            buffer.printf("numeric constant %d(0x%x)", tokc, tokc);
5773        } else if (token == TOK_NUM_FLOAT) {
5774            buffer.printf("numeric constant float %g", tokd);
5775        } else if (token == TOK_NUM_DOUBLE) {
5776            buffer.printf("numeric constant double %g", tokd);
5777        }  else if (token >= 0 && token < 256) {
5778            if (token < 32) {
5779                buffer.printf("'\\x%02x'", token);
5780            } else {
5781                buffer.printf("'%c'", token);
5782            }
5783        } else {
5784            if (quote) {
5785                if (token >= TOK_KEYWORD && token < TOK_SYMBOL) {
5786                    buffer.printf("keyword \"%s\"", nameof(token));
5787                } else {
5788                    buffer.printf("symbol \"%s\"", nameof(token));
5789                }
5790            } else {
5791                buffer.printf("%s", nameof(token));
5792            }
5793        }
5794    }
5795
5796    void printToken(tokenid_t token) {
5797        String buffer;
5798        decodeToken(buffer, token, true);
5799        fprintf(stderr, "%s\n", buffer.getUnwrapped());
5800    }
5801
5802    bool checkSymbol(tokenid_t token) {
5803        bool result = token >= TOK_SYMBOL;
5804        if (!result) {
5805            String temp;
5806            decodeToken(temp, token, true);
5807            error("Expected symbol. Got %s", temp.getUnwrapped());
5808        }
5809        return result;
5810    }
5811
5812    tokenid_t acceptSymbol() {
5813        tokenid_t result = 0;
5814        if (tok >= TOK_SYMBOL) {
5815            result = tok;
5816            next();
5817        }
5818        return result;
5819    }
5820
5821    void globalDeclarations() {
5822        mpCurrentSymbolStack = &mGlobals;
5823        while (tok != EOF) {
5824            Type* pBaseType = expectPrimitiveType(true);
5825            if (!pBaseType) {
5826                break;
5827            }
5828            Type* pDecl = expectDeclaration(pBaseType);
5829            if (!pDecl) {
5830                break;
5831            }
5832            if (!pDecl->id) {
5833                skip(';');
5834                continue;
5835            }
5836
5837            if (checkUndeclaredStruct(pDecl)) {
5838                skip(';');
5839                continue;
5840            }
5841            if (! isDefined(pDecl->id)) {
5842                addGlobalSymbol(pDecl);
5843            }
5844            VariableInfo* name = VI(pDecl->id);
5845            if (name && name->pAddress) {
5846                error("Already defined global %s", nameof(pDecl->id));
5847            }
5848            if (pDecl->tag < TY_FUNC) {
5849                // it's a variable declaration
5850                for(;;) {
5851                    if (pDecl->storageClass == SC_TYPEDEF) {
5852                        // Do not allocate storage.
5853                    } else {
5854                        if (name && !name->pAddress) {
5855                            name->pAddress = (int*) allocGlobalSpace(
5856                                                       pGen->alignmentOf(name->pType),
5857                                                       pGen->sizeOf(name->pType));
5858                        }
5859                        if (accept('=')) {
5860                            if (tok == TOK_NUM) {
5861                                if (name) {
5862                                    * (int*) name->pAddress = tokc;
5863                                }
5864                                next();
5865                            } else {
5866                                error("Expected an integer constant");
5867                            }
5868                        }
5869                    }
5870                    if (!accept(',')) {
5871                        break;
5872                    }
5873                    pDecl = expectDeclaration(pBaseType);
5874                    if (!pDecl) {
5875                        break;
5876                    }
5877                    if (! isDefined(pDecl->id)) {
5878                        addGlobalSymbol(pDecl);
5879                    }
5880                    name = VI(pDecl->id);
5881                }
5882                skip(';');
5883            } else {
5884                // Function declaration
5885                if (accept(';')) {
5886                    // forward declaration.
5887                } else if (tok != '{') {
5888                    error("expected '{'");
5889                } else {
5890                    mpCurrentArena = &mLocalArena;
5891                    mpCurrentSymbolStack = &mLocals;
5892                    if (name) {
5893                        /* patch forward references */
5894                        pGen->resolveForward((int) name->pForward);
5895                        /* put function address */
5896                        name->pAddress = (void*) pCodeBuf->getPC();
5897                    }
5898                    // Calculate stack offsets for parameters
5899                    mLocals.pushLevel();
5900                    intptr_t a = 8;
5901                    int argCount = 0;
5902                    for (Type* pP = pDecl->pTail; pP; pP = pP->pTail) {
5903                        Type* pArg = pP->pHead;
5904                        if (pArg->id) {
5905                            addLocalSymbol(pArg);
5906                        }
5907                        /* read param name and compute offset */
5908                        Type* pPassingType = passingType(pArg);
5909                        size_t alignment = pGen->alignmentOf(pPassingType);
5910                        a = (a + alignment - 1) & ~ (alignment-1);
5911                        if (pArg->id) {
5912                            VI(pArg->id)->pAddress = (void*) a;
5913                        }
5914                        a = a + pGen->sizeOf(pPassingType);
5915                        argCount++;
5916                    }
5917                    rsym = loc = 0;
5918                    pReturnType = pDecl->pHead;
5919                    a = pGen->functionEntry(pDecl);
5920                    block(0, 0, true);
5921                    pGen->gsym(rsym);
5922                    pGen->functionExit(pDecl, a, loc);
5923                    mLocals.popLevel();
5924                    mpCurrentArena = &mGlobalArena;
5925                    mpCurrentSymbolStack = &mGlobals;
5926                }
5927            }
5928        }
5929    }
5930
5931    Type* passingType(Type* pType) {
5932        switch (pType->tag) {
5933        case TY_CHAR:
5934        case TY_SHORT:
5935            return mkpInt;
5936        default:
5937            return pType;
5938        }
5939    }
5940
5941    char* allocGlobalSpace(size_t alignment, size_t bytes) {
5942        size_t base = (((size_t) glo) + alignment - 1) & ~(alignment-1);
5943        size_t end = base + bytes;
5944        if ((end - (size_t) pGlobalBase) > (size_t) ALLOC_SIZE) {
5945            error("Global space exhausted");
5946            assert(false);
5947            return NULL;
5948        }
5949        char* result = (char*) base;
5950        glo = (char*) end;
5951        return result;
5952    }
5953
5954    void cleanup() {
5955        if (pGlobalBase != 0) {
5956            free(pGlobalBase);
5957            pGlobalBase = 0;
5958        }
5959        if (pGen) {
5960            delete pGen;
5961            pGen = 0;
5962        }
5963        if (pCodeBuf) {
5964            delete pCodeBuf;
5965            pCodeBuf = 0;
5966        }
5967        if (file) {
5968            delete file;
5969            file = 0;
5970        }
5971    }
5972
5973    // One-time initialization, when class is constructed.
5974    void init() {
5975        mpSymbolLookupFn = 0;
5976        mpSymbolLookupContext = 0;
5977    }
5978
5979    void clear() {
5980        tok = 0;
5981        tokc = 0;
5982        tokl = 0;
5983        ch = 0;
5984        rsym = 0;
5985        loc = 0;
5986        glo = 0;
5987        macroLevel = -1;
5988        file = 0;
5989        pGlobalBase = 0;
5990        pCodeBuf = 0;
5991        pGen = 0;
5992        mPragmaStringCount = 0;
5993        mCompileResult = 0;
5994        mLineNumber = 1;
5995        mbBumpLine = false;
5996        mbSuppressMacroExpansion = false;
5997    }
5998
5999    void setArchitecture(const char* architecture) {
6000        delete pGen;
6001        pGen = 0;
6002
6003        delete pCodeBuf;
6004        pCodeBuf = new CodeBuf();
6005
6006        if (architecture != NULL) {
6007#ifdef PROVIDE_ARM_CODEGEN
6008            if (! pGen && strcmp(architecture, "arm") == 0) {
6009                pGen = new ARMCodeGenerator();
6010                pCodeBuf = new ARMCodeBuf(pCodeBuf);
6011            }
6012#endif
6013#ifdef PROVIDE_X86_CODEGEN
6014            if (! pGen && strcmp(architecture, "x86") == 0) {
6015                pGen = new X86CodeGenerator();
6016            }
6017#endif
6018            if (!pGen ) {
6019                error("Unknown architecture %s\n", architecture);
6020            }
6021        }
6022
6023        if (pGen == NULL) {
6024#if defined(DEFAULT_ARM_CODEGEN)
6025            pGen = new ARMCodeGenerator();
6026            pCodeBuf = new ARMCodeBuf(pCodeBuf);
6027#elif defined(DEFAULT_X86_CODEGEN)
6028            pGen = new X86CodeGenerator();
6029#endif
6030        }
6031        if (pGen == NULL) {
6032            error("No code generator defined.");
6033        } else {
6034            pGen->setErrorSink(this);
6035            pGen->setTypes(mkpInt);
6036        }
6037    }
6038
6039public:
6040    struct args {
6041        args() {
6042            architecture = 0;
6043        }
6044        const char* architecture;
6045    };
6046
6047    Compiler() {
6048        init();
6049        clear();
6050    }
6051
6052    ~Compiler() {
6053        cleanup();
6054    }
6055
6056    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
6057        mpSymbolLookupFn = pFn;
6058        mpSymbolLookupContext = pContext;
6059    }
6060
6061    int compile(const char* text, size_t textLength) {
6062        int result;
6063
6064        mpCurrentArena = &mGlobalArena;
6065        createPrimitiveTypes();
6066        cleanup();
6067        clear();
6068        mTokenTable.setArena(&mGlobalArena);
6069        mGlobals.setArena(&mGlobalArena);
6070        mGlobals.setTokenTable(&mTokenTable);
6071        mLocals.setArena(&mLocalArena);
6072        mLocals.setTokenTable(&mTokenTable);
6073
6074        internKeywords();
6075        setArchitecture(NULL);
6076        if (!pGen) {
6077            return -1;
6078        }
6079#ifdef PROVIDE_TRACE_CODEGEN
6080            pGen = new TraceCodeGenerator(pGen);
6081#endif
6082        pGen->setErrorSink(this);
6083
6084        if (pCodeBuf) {
6085            pCodeBuf->init(ALLOC_SIZE);
6086        }
6087        pGen->init(pCodeBuf);
6088        file = new TextInputStream(text, textLength);
6089        pGlobalBase = (char*) calloc(1, ALLOC_SIZE);
6090        glo = pGlobalBase;
6091        inp();
6092        next();
6093        globalDeclarations();
6094        checkForUndefinedForwardReferences();
6095        result = pGen->finishCompile();
6096        if (result == 0) {
6097            if (mErrorBuf.len()) {
6098                result = -2;
6099            }
6100        }
6101        mCompileResult = result;
6102        return result;
6103    }
6104
6105    void createPrimitiveTypes() {
6106        mkpInt = createType(TY_INT, NULL, NULL);
6107        mkpShort = createType(TY_SHORT, NULL, NULL);
6108        mkpChar = createType(TY_CHAR, NULL, NULL);
6109        mkpVoid = createType(TY_VOID, NULL, NULL);
6110        mkpFloat = createType(TY_FLOAT, NULL, NULL);
6111        mkpDouble = createType(TY_DOUBLE, NULL, NULL);
6112        mkpIntFn =  createType(TY_FUNC, mkpInt, NULL);
6113        mkpIntPtr = createPtrType(mkpInt);
6114        mkpCharPtr = createPtrType(mkpChar);
6115        mkpFloatPtr = createPtrType(mkpFloat);
6116        mkpDoublePtr = createPtrType(mkpDouble);
6117        mkpPtrIntFn = createPtrType(mkpIntFn);
6118    }
6119
6120    void checkForUndefinedForwardReferences() {
6121        mGlobals.forEach(static_ufrcFn, this);
6122    }
6123
6124    static bool static_ufrcFn(VariableInfo* value, void* context) {
6125        Compiler* pCompiler = (Compiler*) context;
6126        return pCompiler->undefinedForwardReferenceCheck(value);
6127    }
6128
6129    bool undefinedForwardReferenceCheck(VariableInfo* value) {
6130        if (!value->pAddress && value->pForward) {
6131            error("Undefined forward reference: %s",
6132                  mTokenTable[value->tok].pText);
6133        }
6134        return true;
6135    }
6136
6137    /* Look through the symbol table to find a symbol.
6138     * If found, return its value.
6139     */
6140    void* lookup(const char* name) {
6141        if (mCompileResult == 0) {
6142            tokenid_t tok = mTokenTable.intern(name, strlen(name));
6143            VariableInfo* pVariableInfo = VI(tok);
6144            if (pVariableInfo) {
6145                return pVariableInfo->pAddress;
6146            }
6147        }
6148        return NULL;
6149    }
6150
6151    void getPragmas(ACCsizei* actualStringCount,
6152                    ACCsizei maxStringCount, ACCchar** strings) {
6153        int stringCount = mPragmaStringCount;
6154        if (actualStringCount) {
6155            *actualStringCount = stringCount;
6156        }
6157        if (stringCount > maxStringCount) {
6158            stringCount = maxStringCount;
6159        }
6160        if (strings) {
6161            char* pPragmas = mPragmas.getUnwrapped();
6162            while (stringCount-- > 0) {
6163                *strings++ = pPragmas;
6164                pPragmas += strlen(pPragmas) + 1;
6165            }
6166        }
6167    }
6168
6169    void getProgramBinary(ACCvoid** base, ACCsizei* length) {
6170        *base = pCodeBuf->getBase();
6171        *length = (ACCsizei) pCodeBuf->getSize();
6172    }
6173
6174    char* getErrorMessage() {
6175        return mErrorBuf.getUnwrapped();
6176    }
6177};
6178
6179const char* Compiler::operatorChars =
6180    "++--*@/@%@+@-@<<>><=>=<@>@==!=&&||&@^@|@~@!@";
6181
6182const char Compiler::operatorLevel[] =
6183    {11, 11, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4,
6184            5, 5, /* ==, != */
6185            9, 10, /* &&, || */
6186            6, 7, 8, /* & ^ | */
6187            2, 2 /* ~ ! */
6188            };
6189
6190#ifdef PROVIDE_X86_CODEGEN
6191const int Compiler::X86CodeGenerator::operatorHelper[] = {
6192        0x1,     // ++
6193        0xff,    // --
6194        0xc1af0f, // *
6195        0xf9f79991, // /
6196        0xf9f79991, // % (With manual assist to swap results)
6197        0xc801, // +
6198        0xd8f7c829, // -
6199        0xe0d391, // <<
6200        0xf8d391, // >>
6201        0xe, // <=
6202        0xd, // >=
6203        0xc, // <
6204        0xf, // >
6205        0x4, // ==
6206        0x5, // !=
6207        0x0, // &&
6208        0x1, // ||
6209        0xc821, // &
6210        0xc831, // ^
6211        0xc809, // |
6212        0xd0f7, // ~
6213        0x4     // !
6214};
6215#endif
6216
6217struct ACCscript {
6218    ACCscript() {
6219        text = 0;
6220        textLength = 0;
6221        accError = ACC_NO_ERROR;
6222    }
6223
6224    ~ACCscript() {
6225        delete text;
6226    }
6227
6228    void registerSymbolCallback(ACCSymbolLookupFn pFn, ACCvoid* pContext) {
6229        compiler.registerSymbolCallback(pFn, pContext);
6230    }
6231
6232    void setError(ACCenum error) {
6233        if (accError == ACC_NO_ERROR && error != ACC_NO_ERROR) {
6234            accError = error;
6235        }
6236    }
6237
6238    ACCenum getError() {
6239        ACCenum result = accError;
6240        accError = ACC_NO_ERROR;
6241        return result;
6242    }
6243
6244    Compiler compiler;
6245    char* text;
6246    int textLength;
6247    ACCenum accError;
6248};
6249
6250
6251extern "C"
6252ACCscript* accCreateScript() {
6253    return new ACCscript();
6254}
6255
6256extern "C"
6257ACCenum accGetError( ACCscript* script ) {
6258    return script->getError();
6259}
6260
6261extern "C"
6262void accDeleteScript(ACCscript* script) {
6263    delete script;
6264}
6265
6266extern "C"
6267void accRegisterSymbolCallback(ACCscript* script, ACCSymbolLookupFn pFn,
6268                               ACCvoid* pContext) {
6269    script->registerSymbolCallback(pFn, pContext);
6270}
6271
6272extern "C"
6273void accScriptSource(ACCscript* script,
6274    ACCsizei count,
6275    const ACCchar ** string,
6276    const ACCint * length) {
6277    int totalLength = 0;
6278    for(int i = 0; i < count; i++) {
6279        int len = -1;
6280        const ACCchar* s = string[i];
6281        if (length) {
6282            len = length[i];
6283        }
6284        if (len < 0) {
6285            len = strlen(s);
6286        }
6287        totalLength += len;
6288    }
6289    delete script->text;
6290    char* text = new char[totalLength + 1];
6291    script->text = text;
6292    script->textLength = totalLength;
6293    char* dest = text;
6294    for(int i = 0; i < count; i++) {
6295        int len = -1;
6296        const ACCchar* s = string[i];
6297        if (length) {
6298            len = length[i];
6299        }
6300        if (len < 0) {
6301            len = strlen(s);
6302        }
6303        memcpy(dest, s, len);
6304        dest += len;
6305    }
6306    text[totalLength] = '\0';
6307
6308#ifdef DEBUG_SAVE_INPUT_TO_FILE
6309    LOGD("Saving input to file...");
6310    int counter;
6311    char path[PATH_MAX];
6312    for (counter = 0; counter < 4096; counter++) {
6313        sprintf(path, DEBUG_DUMP_PATTERN, counter);
6314        if(access(path, F_OK) != 0) {
6315            break;
6316        }
6317    }
6318    if (counter < 4096) {
6319        LOGD("Saving input to file %s", path);
6320        FILE* fd = fopen(path, "w");
6321        if (fd) {
6322            fwrite(text, totalLength, 1, fd);
6323            fclose(fd);
6324            LOGD("Saved input to file %s", path);
6325        } else {
6326            LOGD("Could not save. errno: %d", errno);
6327        }
6328    }
6329#endif
6330}
6331
6332extern "C"
6333void accCompileScript(ACCscript* script) {
6334    int result = script->compiler.compile(script->text, script->textLength);
6335    if (result) {
6336        script->setError(ACC_INVALID_OPERATION);
6337    }
6338}
6339
6340extern "C"
6341void accGetScriptiv(ACCscript* script,
6342    ACCenum pname,
6343    ACCint * params) {
6344    switch (pname) {
6345        case ACC_INFO_LOG_LENGTH:
6346            *params = 0;
6347            break;
6348    }
6349}
6350
6351extern "C"
6352void accGetScriptInfoLog(ACCscript* script,
6353    ACCsizei maxLength,
6354    ACCsizei * length,
6355    ACCchar * infoLog) {
6356    char* message = script->compiler.getErrorMessage();
6357    int messageLength = strlen(message) + 1;
6358    if (length) {
6359        *length = messageLength;
6360    }
6361    if (infoLog && maxLength > 0) {
6362        int trimmedLength = maxLength < messageLength ?
6363                maxLength : messageLength;
6364        memcpy(infoLog, message, trimmedLength);
6365        infoLog[trimmedLength] = 0;
6366    }
6367}
6368
6369extern "C"
6370void accGetScriptLabel(ACCscript* script, const ACCchar * name,
6371                       ACCvoid ** address) {
6372    void* value = script->compiler.lookup(name);
6373    if (value) {
6374        *address = value;
6375    } else {
6376        script->setError(ACC_INVALID_VALUE);
6377    }
6378}
6379
6380extern "C"
6381void accGetPragmas(ACCscript* script, ACCsizei* actualStringCount,
6382                   ACCsizei maxStringCount, ACCchar** strings){
6383    script->compiler.getPragmas(actualStringCount, maxStringCount, strings);
6384}
6385
6386extern "C"
6387void accGetProgramBinary(ACCscript* script,
6388    ACCvoid** base, ACCsizei* length) {
6389    script->compiler.getProgramBinary(base, length);
6390}
6391
6392
6393} // namespace acc
6394
6395