#include "c.h"
//#define DOPRINTF

#ifndef DOPRINTF
#define PrintRegister(a)
#define PrintTemporary(a)
#endif
//#include <malloc.h>
extern void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
static int maxdepth,hasDangerousOp;
typedef struct tagSymbolList SymbolList;

struct tagSymbolList {
    struct tagSymbolList *Next;
    Symbol sym;
};
extern Symbol shortreg[],charreg[];
extern unsigned int usedmask[];
int RegisterVariablesMask;
SymbolList *SymbolsHead;

typedef struct tagAssignmentSymbolList {
    struct tagAssignmentSymbolList *Next;
    SymbolList *lhs;
    SymbolList *rhs;
    Node node;
} AssignmentDescriptor;

AssignmentDescriptor *AssignmentsList;

typedef struct tagLexicalBlock {
    struct tagLexicalBlock *Next;
    struct tagLexicalBlock *Down;
    struct tagLexicalBlock *Up;
    Code cp;
} LexicalBlock;

Code CurrentLexicalBlock;
typedef struct tagbasicCodeBlock {
    struct tagbasicCodeBlock *Next;
    int Label;
    int NrOfSuccessors;
    int *Successors;
    int NrOfPredecessors;
    int *Predecessors;
    AssignmentDescriptor *DefUse;
    SymbolList *Symbols;
    Coordinate src;
    LexicalBlock *lexicalblock;
    Node Nodes;
    unsigned EndsWithJump:1;
    unsigned hasCalls:1;
    unsigned hasBlockMove:1;
    unsigned hasMul:1;
    unsigned hasDivision:1;
    unsigned hasConditionals:1;
} basicCodeBlock;

Symbol equated (Symbol);


SymbolList *AssignedSymbols;
#ifdef DOPRINTF
#define Printf2(a,b) printf(a,b)
#define Printf3(a,b,c) printf(a,b,c)
#else
#define Printf2(a,b)
#define Printf3(a,b,c)
#endif
basicCodeBlock StartBlock;
static int unsafe;
#define MAXSUCCESORS 1000
static short successorsTable[MAXSUCCESORS];
static int succIdx,currentLabel,endswithjump,hasCalls,hasConditionals;
static basicCodeBlock *RootBlock,*lastBlock;
static Node BlockNodes;
#define MAXALIAS 200
#define MAXJUMPNODES 4096
typedef struct tagAlias {
    unsigned short label;
    unsigned short alias;
    Node plabel;
} alias,*Alias;
static Node JumpNodeTable[MAXJUMPNODES];
static int JumpNodeIndex;

static Alias AliasTable;
static int AliasTableSize;
static int aliasIndex;

SymbolList *AddSymbolToSymbolList(SymbolList **sl,Symbol s)
{
    SymbolList *newsl;

//	if (s->generated || s->temporary) return *sl;
    if (s) {
        NEW0(newsl,FUNC);
        newsl->Next = *sl;
        *sl = newsl;
        newsl->sym = s;
        return newsl;
    }
    return *sl;
}

AssignmentDescriptor *AddAssignment(SymbolList *l,SymbolList *sl,Node n)
{
    AssignmentDescriptor *ad;

    NEW0(ad,FUNC);
    ad->lhs = l;
    ad->rhs = sl;
    ad->node = n;
    ad->Next = AssignmentsList;
    AssignmentsList = ad;
    return(ad);
}
static void treedump(Node p,int level)
{
    printf( "%s(", IR->x._opname[p->op]);
    if (IR->x._arity[p->op] == 0 && p->syms[0])
        printf( "%s", p->syms[0]->name);
    else if (IR->x._arity[p->op] == 1)
        treedump(p->kids[0],level+1);
    else if (IR->x._arity[p->op] == 2) {
        treedump(p->kids[0],level+1);
        printf( ", ");
        treedump(p->kids[1],level+1);
    }
    printf( ")");
}

extern void GenBlockDebugInfo(Code cp);
static void     fixup1(Node p);

static void ClearAliasTable(void)
{
    if (AliasTableSize == 0)
        return;
    memset(AliasTable,0,AliasTableSize*sizeof(alias));
}

static void AddLabelAlias(int label,Node plabel)
{
    Alias a;

    if (AliasTable == NULL) {
        AliasTable = (Alias)malloc(MAXALIAS * sizeof(alias));
        memset(AliasTable,0,MAXALIAS *sizeof(alias));
        AliasTableSize = MAXALIAS;
    }
    if (aliasIndex >= AliasTableSize) {
        AliasTable = (Alias)realloc(AliasTable,(AliasTableSize+MAXALIAS)*sizeof(alias));
        memset(AliasTable+AliasTableSize,0,MAXALIAS*sizeof(alias));
        AliasTableSize += MAXALIAS;
    }
    a = &AliasTable[aliasIndex];
    aliasIndex++;
    a->alias = plabel->syms[0]->u.l.label;
    a->label = label;
    a->plabel = plabel;
}

static void AddJumpNode(Node p)
{
    if (JumpNodeIndex >= MAXJUMPNODES) {
        printf(StrTab[405]);// <Overflow in jump node table>
        return;
    }
    JumpNodeTable[JumpNodeIndex] = p;
    JumpNodeIndex++;
}
#ifdef DOPRINTF
void PrintRegister(Node p)
{
    if (p->syms[RX] && p->x.registered) {
        Printf2("%s ",p->syms[RX]->x.name);
    }
}
static void PrintTemporary(Symbol s)
{
    if (s->computed) {
        if (s->scope == GLOBAL)
            Printf2("global ",0);
        else if( s->sclass == STATIC)
            Printf2("static ",0);
        else if (s->sclass == EXTERN)
            Printf2("extern ",0);
        else {
            Printf2("local ",0);
        }
        Printf2("%s ",s->x.name);
        if (s->x.ArraySymbol)
            Printf2("%s ",s->x.ArraySymbol->name);
    }
    else
        Printf2("%s ",s->name);
}
#endif

#ifdef BLOCKANALYSIS
static void FinishBlock(void)
{
    basicCodeBlock *rvp;

    NEW0(rvp,FUNC);
    if (RootBlock == NULL) {
        RootBlock = rvp;
    }
    else {
        lastBlock->Next = rvp;
    }
    lastBlock = rvp;
    rvp->NrOfSuccessors = succIdx;
    if (succIdx) {
        rvp->Successors = allocate(succIdx * sizeof(int),FUNC);
        memcpy(rvp->Successors,successorsTable,succIdx*sizeof(short));
    }
    rvp->src = src;
    rvp->Label = currentLabel;
    rvp->EndsWithJump = endswithjump;
    rvp->hasCalls = hasCalls;
    rvp->DefUse = AssignmentsList;
    rvp->hasConditionals = hasConditionals;
    rvp->Nodes = BlockNodes;
    AssignmentsList = NULL;
    rvp->Symbols = SymbolsHead;
    SymbolsHead = NULL;
    hasCalls = endswithjump = succIdx = hasConditionals = 0;
    BlockNodes = NULL;
}
#else
static void FinishBlock(void) {
    succIdx = 0;
}
#endif

static int NotUsed(Node p,Symbol s)
{
    if (p == NULL) return 1;
    if (p->syms[0] == s) return 0;
    if (!NotUsed(p->kids[0],s)) return 0;
    if (!NotUsed(p->kids[1],s)) return 0;
    return 1;
}

int CheckBooleanAsgn(Node p)
{
    Node asgn1,asgn2,jumpv,lab1,lab2,newN,asgnN;

    asgn1 = p->x.next;
    if (asgn1 == NULL || asgn1->op != ASGNI) return 0;
    if (asgn1->kids[0]->syms[0] == NULL) return 0;
    if (asgn1->kids[1]->op != CNSTI) return 0;
    jumpv = asgn1->x.next;
    if (jumpv == NULL || jumpv->op != JUMPV)
        return 0;
    lab1 = jumpv->x.next;
    if (lab1 == NULL || lab1->op != LABELV)
        return 0;
    asgn2 = lab1->x.next;
    if (asgn2 == NULL || asgn2->op != ASGNI)
        return 0;
    if (asgn2->kids[1]->op != CNSTI) return 0;
    lab2 = asgn2->x.next;
    if (lab2 == NULL || lab2->op != LABELV)
        return 0;
    if (lab2->syms[0]->ref != 1.0 || lab1->syms[0]->ref != 1.0)
        return 0;
    newN = newnode(JUMPI,asgn2->kids[1],asgn1->kids[1],NULL);
    newN->x.oldop = p->op;
    /*
    Try to avoid a spurious assignment to a temporary. If possible
    assign directly to the destination ignoring the temporary.
    */
    if (lab2->link && lab2->link->op == ASGNI) {
        asgnN = lab2->link;

        if (asgnN->kids[1]->op == INDIRI &&
            asgnN->kids[1]->kids[0]->op == ADDRLP) {

            if (asgnN->kids[1]->kids[0]->syms[0] == asgn1->kids[0]->syms[0]) {
                /*
                We found it. Cut the tree accordingly.
                */
                if (NotUsed(asgnN->x.next,asgn1->kids[0]->syms[0])) {
                    asgnN->kids[1] = newN;
					newN->x.next = lab2->x.next;
                    p->link = asgnN;
                    p->x.next = newN;
                    p->x.booleanAsgn = 1;
                    return 1;
                }
            }
        }
    }
    asgnN = newnode(ASGNI,asgn1->kids[0],newN,asgn1->kids[0]->syms[0]);
    newN->link = asgnN;
	newN->x.next = lab2->x.next;
    asgnN->link = lab2->link;
//	asgnN->x.next = lab2->x.next;
    p->link = asgnN;
//	p->x.next = newN;
    p->x.booleanAsgn = 1;
    return 1;
}

static int FindSymbols(Node p,int level)
{
    int op,result=0;
    Symbol n;

    if (p == NULL) return 0;
    if (p->x.analyzed) return 0;
    p->x.analyzed = 1;
    if (level > maxdepth) maxdepth = level;
    op = generic(p->op);
    if (op != LABEL && BlockNodes == NULL)
        BlockNodes = p;
    if (optype(p->op) == L) {
        unsafe = 1;
        hasDangerousOp = 1;
    }
    switch (op) {
    case LABEL:
        if (p->syms[0]->ref == 0.0) {
            Printf2("Label _$%s not used",p->syms[0]->name);
            p->syms[0]->u.l.label = 0;
            return 1;
        }
        if (BlockNodes == NULL) {
            Printf2("Label _$%d empty",currentLabel);
            AddLabelAlias(currentLabel,p);
            result = 1;
        }
        else FinishBlock();
        currentLabel = p->syms[0]->u.l.label;
        BlockNodes = NULL;
        FindSymbols(p->kids[0],level+1);
        FindSymbols(p->kids[1],level+1);
        break;
    case JUMP:
        if (p->op == JUMPI) {
			break;
		}
        if (p->kids[0] && p->kids[0]->syms[0]) {
            n = equated(p->kids[0]->syms[0]);
            if (succIdx >= MAXSUCCESORS) {
                printf(StrTab[406]);// <Overflow in number of successors\n>
            }
            else {
                successorsTable[succIdx] = n->u.l.label;
                succIdx++;
            }
            AddJumpNode(p);
        }
        endswithjump = 1;
        FindSymbols(p->kids[0],level+1);
        FindSymbols(p->kids[1],level+1);
        break;
    case EQ:
    case LE:
    case NE:
    case LT:
    case GE: