#include "compiler/IroPropagate.h"
#include "compiler/IroCSE.h"
#include "compiler/IroDump.h"
#include "compiler/IroEval.h"
#include "compiler/IroFlowgraph.h"
#include "compiler/IroLinearForm.h"
#include "compiler/IROUseDef.h"
#include "compiler/IroUtil.h"
#include "compiler/IroVars.h"
#include "compiler/objects.h"
#include "compiler/CExpr.h"
#include "compiler/CompilerTools.h"
#include "compiler/CParser.h"
#include "compiler/InlineAsm.h"
#include "compiler/InlineAsmPPC.h"

IROAssign *IRO_FirstAssign;
IROAssign *IRO_LastAssign;
SInt32 IRO_NumAssign;

static Boolean VarIsUsedInOtherFNodes(VarRecord *var, IRONode *node) {
    if (var->defs && var->uses) {
        IROUse *use;
        IRODef *def = NULL;
        for (use = var->uses; use; use = use->varnext) {
            if (!def && use->node == node && use->linear && !(use->linear->flags & IROLF_Assigned)) {
                for (def = var->defs; def; def = def->varnext) {
                    if (Bv_IsBitSet(def->index, use->x18))
                        break;
                }
            }
        }

        if (def) {
            for (use = var->uses; use; use = use->varnext) {
                if (use->node != node && use->linear && !(use->linear->flags & IROLF_Assigned)) {
                    if (Bv_IsBitSet(def->index, use->x18))
                        return 1;
                }
            }
        }
    } else {
        IROLinear *linear;
        IRONode *scan;
        for (scan = IRO_FirstNode; scan; scan = scan->nextnode) {
            if (scan != node) {
                linear = scan->first;
                while (1) {
                    if (!linear)
                        break;

                    if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) {
                        if (IRO_FindVar(linear->u.diadic.left->u.node->data.objref, 0, 1) == var)
                            return 1;
                    }

                    if (linear == scan->last)
                        break;
                    linear = linear->next;
                }
            }
        }
        IRO_CheckForUserBreak();
    }

    return 0;
}

static void GetExprUses(IROLinear *linear, Boolean isFirst) {
    if (isFirst && IS_LINEAR_ENODE(linear, EOBJREF)) {
        Object *obj = linear->u.node->data.objref;
        if ((linear->flags & IROLF_Ind) && (!(linear->flags & IROLF_Assigned) || (linear->flags & IROLF_Used))) {
            VarRecord *var = IRO_FindVar(obj, 0, 1);
            if (var)
                Bv_SetBit(var->index, IRO_VarKills);
        }
    }
}

static void GetExprKills(IROLinear *linear, Boolean isFirst) {
    if (isFirst)
        IRO_GetKills(linear);
}

static void CheckUnorderedRegionForDefs(IROLinear *linear, BitVector *a, BitVector *b, Boolean *flag) {
    Bv_Clear(a);
    Bv_Clear(IRO_VarKills);
    IRO_WalkTree(linear, GetExprKills);
    Bv_Or(IRO_VarKills, a);
    if (Bv_BitsInCommon(a, b))
        *flag = 1;
}

static void CheckUnorderedRegionsForDefs(IROLinear *linear1, IROLinear *linear2, BitVector *a, BitVector *b, Boolean *flag) {
    int i;

    switch (linear1->type) {
        case IROLinearOp2Arg:
            if (linear1->nodetype == ELAND) break;
            if (linear1->nodetype == ELOR) break;
            if (linear1->nodetype == ECOMMA) break;
            if (linear1->u.diadic.left != linear2)
                CheckUnorderedRegionForDefs(linear1->u.diadic.left, a, b, flag);
            if (linear1->u.diadic.right != linear2)
                CheckUnorderedRegionForDefs(linear1->u.diadic.right, a, b, flag);
            break;
        case IROLinearFunccall:
            if (linear1->u.funccall.linear8 != linear2)
                CheckUnorderedRegionForDefs(linear1->u.funccall.linear8, a, b, flag);
            for (i = 0; !*flag && i < linear1->u.funccall.argCount; i++) {
                if (linear1->u.funccall.args[i] != linear2)
                    CheckUnorderedRegionForDefs(linear1->u.funccall.args[i], a, b, flag);
            }
            break;
    }
}

static Boolean PropagationHasDefsInUnorderedRegions(IROLinear *a, IROLinear *b) {
    Boolean flag;
    IROLinear *father;
    BitVector *bv1;
    BitVector *bv2;
    VarRecord *var;

    flag = 0;
    if ((father = IRO_LocateFather(a))) {
        Bv_AllocVector(&bv1, IRO_NumVars + 1);
        Bv_AllocVector(&bv2, IRO_NumVars + 1);
        Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1);
        IRO_WalkTree(b, GetExprUses);
        Bv_Or(IRO_VarKills, bv2);
        var = IRO_FindVar(a->u.diadic.left->u.node->data.objref, 0, 1);
        Bv_SetBit(var->index, bv2);
        while (father && !flag) {
            CheckUnorderedRegionsForDefs(father, a, bv1, bv2, &flag);
            a = father;
            father = IRO_LocateFather(father);
        }
    }

    return flag;
}

int IRO_IsRegable(Object *obj) {
    if (obj->datatype == DLOCAL && obj->u.var.info)
        return obj->u.var.info->noregister == 0;
    return 0;
}

static Boolean IsPropagatable(IROLinear *linear) {
    Object *obj;
    Object *obj2;

    if (IS_LINEAR_DIADIC(linear, EASS) && (obj = IRO_IsVariable(linear->u.diadic.left)) && obj->type == linear->rtype && !is_volatile_object(obj)) {
        if (linear->u.diadic.left->flags & IROLF_BitfieldIndirect) {
            if (!IRO_IsConstant(linear->u.diadic.right))
                return 0;
            else
                return 1;
        }

        if (IRO_IsConstant(linear->u.diadic.right))
            return 1;

        if ((obj2 = IRO_IsVariable(linear->u.diadic.right)) && !is_volatile_object(obj2) && IRO_TypesEqual(obj->type, linear->rtype)) {
            if (!Inline_IsObjectData(linear->u.diadic.right->u.monadic->u.node->data.objref)) {
                if (IRO_IsRegable(obj) && !IRO_IsRegable(obj2))
                    return 0;
                return 1;
            }
        }
    }

    return 0;
}

static Boolean IsIntGenKillCandidate(IROLinear *linear) {
    if (linear->type == IROLinearFunccall)
        return 1;

    if (IRO_IsAssignOp[linear->nodetype] && (linear->type == IROLinearOp1Arg || linear->type == IROLinearOp2Arg))
        return 1;

    if (linear->type == IROLinearAsm)
        return 1;

    return 0;
}

static Boolean IsPropagatableExpr(IROLinear *linear, IROList *list) {
    Object *obj;
    if (IS_LINEAR_DIADIC(linear, EASS) && !(linear->flags & IROLF_Reffed)) {
        if ((obj = IRO_IsVariable(linear->u.diadic.left)) && !is_volatile_object(obj) && !(linear->u.diadic.left->flags & IROLF_BitfieldIndirect)) {
            if (!IRO_IsRegable(obj))
                return 0;
            if (IS_LINEAR_ENODE(linear->u.diadic.right, ESTRINGCONST))
                return 0;

            IRO_FindDepends(linear->u.diadic.right);
            if (!IRO_NotSubable)
                return 1;
        }
    }

    return 0;
}

static void ClearAvailibilityOnNode(IRONode *node, UInt32 bit) {
    IRONode *scan;

    for (scan = node->nextnode; scan; scan = scan->nextnode)
        Bv_ClearBit(bit, scan->x16);
}

Boolean IRO_CopyAndConstantPropagation(void) {
    IROAssign *ass2;
    IROAssign *ass;
    IROLinear *linear;
    IRONode *node;
    VarRecord *var;
    BitVector *bv;
    Boolean flag;
    Boolean result;

    IRO_FirstAssign = NULL;
    IRO_NumAssign = 0;
    result = 0;

    for (node = IRO_FirstNode; node; node = node->nextnode) {
        linear = node->first;
        while (1) {
            if (!linear)
                break;

            if (IsPropagatable(linear) && (var = IRO_FindAssigned(linear))) {
                IROAssign *newass;
                IRO_Dump("Found propagatable assignment at: %d\n", linear->index);
                newass = oalloc(sizeof(IROAssign));
                newass->linear = linear;
                newass->next = NULL;
                newass->index = ++IRO_NumAssign;
                newass->varIndex = var->index;
                newass->linear2 = linear->u.diadic.right;
                newass->var = NULL;
                newass->varObj = IRO_IsVariable(linear->u.diadic.right);
                newass->node = node;
                if (newass->varObj)
                    newass->var = IRO_FindVar(newass->varObj, 0, 1);
                if (!IRO_FirstAssign)
                    IRO_FirstAssign = newass;
                else
                    IRO_LastAssign->next = newass;
                IRO_LastAssign = newass;
            }

            if (linear == node->last)
                break;
            linear = linear->next;
        }
    }

    IRO_CheckForUserBreak();

    node = IRO_FirstNode;
    ass = IRO_FirstAssign;
    Bv_AllocVector(&IRO_VarKills, IRO_NumVars + 1);
    while (node) {
        Bv_AllocVector(&node->x16, IRO_NumAssign);
        if (node != IRO_FirstNode)
            Bv_Set(node->x16);
        Bv_AllocVector(&node->x22, IRO_NumAssign);
        Bv_AllocVector(&node->x1E, IRO_NumAssign);
        Bv_AllocVector(&node->x2A, IRO_NumAssign);
        node->x1A = NULL;

        linear = node->first;
        while (1) {
            if (!linear)
                break;

            if (IsIntGenKillCandidate(linear)) {
                //IROAssign *ass2;
                Bv_Clear(IRO_VarKills);
                IRO_GetKills(linear);

                for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) {
                    if (Bv_IsBitSet(ass2->varIndex, IRO_VarKills)) {
                        Bv_SetBit(ass2->index, node->x22);
                        Bv_ClearBit(ass2->index, node->x1E);
                    }
                    if (ass2->var && Bv_IsBitSet(ass2->var->index, IRO_VarKills)) {
                        Bv_SetBit(ass2->index, node->x22);
                        Bv_ClearBit(ass2->index, node->x1E);
                    }
                }
            }

            while (ass && ass->linear == linear) {
                Bv_SetBit(ass->index, node->x1E);
                ass = ass->next;
            }

            if (linear == node->last)
                break;
            linear = linear->next;
        }

        Bv_Copy(node->x16, node->x2A);
        Bv_Minus(node->x22, node->x2A);
        Bv_Or(node->x1E, node->x2A);
        node = node->nextnode;
    }

    IRO_CheckForUserBreak();

    Bv_AllocVector(&bv, IRO_NumAssign);
    do {
        flag = 0;
        for (node = IRO_FirstNode; node; node = node->nextnode) {
            if (node == IRO_FirstNode) {
                Bv_Clear(bv);
            } else {
                UInt16 i;
                Bv_Set(bv);
                for (i = 0; i < node->numpred; i++)
                    Bv_And(IRO_NodeTable[node->pred[i]]->x2A, bv);
            }

            if (!Bv_Compare(bv, node->x16)) {
                flag = 1;
                Bv_Copy(bv, node->x16);
            }

            Bv_Copy(node->x16, node->x2A);
            Bv_Minus(node->x22, node->x2A);
            Bv_Or(node->x1E, node->x2A);
        }
    } while (flag);

    IRO_CheckForUserBreak();

    node = IRO_FirstNode;
    ass = IRO_FirstAssign;
    while (node) {
        IRO_Avail = node->x16;
        linear = node->first;
        while (1) {
            if (!linear)
                break;

            if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) {
                if ((var = IRO_FindVar(linear->u.diadic.left->u.node->data.objref, 0, 1))) {
                    //IROAssign *ass2;
                    for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) {
                        if (
                                ass2->varIndex == var->index &&
                                Bv_IsBitSet(ass2->index, IRO_Avail) &&
                                (IRO_IsConstant(ass2->linear2) || node->loopdepth <= ass2->node->loopdepth) &&
                                !PropagationHasDefsInUnorderedRegions(linear, ass2->linear2)
                                ) {
                            if (ass2->linear2->type == IROLinearOperand && IRO_is_CPtypeequal(linear->rtype, ass2->linear->u.diadic.left->rtype)) {
                                ENode *enode = IRO_NewENode(ass2->linear2->u.node->type);
                                *enode = *ass2->linear2->u.node;
                                if (enode->type == EINTCONST) {
                                    if (linear->flags & IROLF_BitfieldIndirect) {
                                        IRO_TruncateBitfieldValueToType(&enode->data.intval, linear->rtype, var->x1A);
                                        enode->rtype = linear->rtype;
                                        result = 1;
                                    } else {
                                        IRO_TruncateValueToType(&enode->data.intval, linear->rtype);
                                        enode->rtype = linear->rtype;
                                    }
                                }
                                linear->u.monadic->type = IROLinearNop;
                                linear->type = IROLinearOperand;
                                linear->u.node = enode;
                            } else if (ass2->varObj && IRO_is_CPtypeequal(linear->rtype, ass2->linear->rtype)) {
                                linear->u.diadic.left->u.node = create_objectrefnode(ass2->varObj);
                                if (ass2->linear2->flags & IROLF_BitfieldIndirect)
                                    linear->flags |= IROLF_BitfieldIndirect;
                            }
                            IRO_Dump("Found propagation at %d from %d\n", linear->index, ass2->linear->index);
                            break;
                        }
                    }
                }
            } else if (linear->type == IROLinearAsm) {
                IAEffects effects;
                int i;
                CodeGen_GetAsmEffects(linear->u.asm_stmt, &effects);

                for (i = 0; i < effects.numoperands; i++) {
                    if (effects.operands[i].type == IAEffect_0 && effects.operands[i].offset == 0 && effects.operands[i].object->type->size == effects.operands[i].size) {
                        if ((var = IRO_FindVar(effects.operands[i].object, 0, 1))) {
                            //IROAssign *ass2;
                            for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) {
                                if (ass2->varIndex == var->index && Bv_IsBitSet(ass2->index, IRO_Avail) && ass2->linear->rtype->size == effects.operands[i].size) {
                                    ENode *enode;
                                    if (ass2->varObj) {
                                        enode = create_objectrefnode(ass2->varObj);
                                    } else if (ass2->linear2->type == IROLinearOperand) {
                                        enode = ass2->linear2->u.node;
                                    } else {
#line 768
                                        CError_FATAL();
                                    }
                                    CodeGen_PropagateIntoAsm(linear->u.asm_stmt, effects.operands[i].object, enode);
                                    break;
                                }
                            }
                        }
                    }
                }
            }

            if (IsIntGenKillCandidate(linear)) {
                //IROAssign *ass2;
                Bv_Clear(IRO_VarKills);
                IRO_GetKills(linear);

                for (ass2 = IRO_FirstAssign; ass2; ass2 = ass2->next) {
                    if (Bv_IsBitSet(ass2->varIndex, IRO_VarKills)) {
                        Bv_ClearBit(ass2->index, IRO_Avail);
                    }
                    if (ass2->var && Bv_IsBitSet(ass2->var->index, IRO_VarKills)) {
                        Bv_ClearBit(ass2->index, IRO_Avail);
                    }
                }

                while (ass && ass->linear == linear) {
                    Bv_SetBit(ass->index, IRO_Avail);
                    ass = ass->next;
                }
            }

            if (linear == node->last)
                break;
            linear = linear->next;
        }
        node = node->nextnode;
    }

    IRO_CheckForUserBreak();

    return result;
}

void IRO_ExpressionPropagation(void) {
    IRONode *node;
    IROLinear *linear;
    Object *obj;
    VarRecord *var;
    IROAssign *ass;

    for (node = IRO_FirstNode; node; node = node->nextnode) {
        IRO_FirstAssign = NULL;
        IRO_LastAssign = NULL;
        IRO_NumAssign = 0;

        linear = node->first;
        while (1) {
            IROList list;
            if (!linear)
                break;

            IRO_InitList(&list);
            if (IsPropagatableExpr(linear, &list)) {
                if ((var = IRO_FindAssigned(linear))) {
                    IRO_Dump("Found propagatable expression assignment at: %d\n", linear->index);
                    ass = oalloc(sizeof(IROAssign));
                    ass->linear = linear;
                    ass->next = NULL;
                    ass->index = ++IRO_NumAssign;
                    ass->varIndex = var->index;
                    ass->linear2 = linear->u.diadic.right;
                    ass->x20 = 0;
                    ass->node = node;
                    IRO_FindDepends(linear->u.diadic.right);
                    ass->depends = IRO_Depends;
                    if (!IRO_FirstAssign) {
                        IRO_FirstAssign = ass;
                        ass->prev = NULL;
                    } else {
                        IRO_LastAssign->next = ass;
                        ass->prev = IRO_LastAssign;
                    }
                    IRO_LastAssign = ass;
                }
            }

            if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) {
                if ((var = IRO_FindVar(linear->u.monadic->u.node->data.objref, 0, 1))) {
                    for (ass = IRO_LastAssign; ass; ass = ass->prev) {
                        if (ass->varIndex == var->index)
                            ass->x20++;
                    }
                }
            }

            if (linear == node->last)
                break;
            linear = linear->next;
        }

        Bv_AllocVector(&IRO_Avail, IRO_NumAssign);

        linear = node->first;
        while (1) {
            if (!linear)
                break;

            if (IRO_IsVariable(linear) && !(linear->flags & IROLF_Assigned)) {
                if ((var = IRO_FindVar(linear->u.monadic->u.node->data.objref, 0, 1))) {
                    for (ass = IRO_LastAssign; ass; ass = ass->next) {
                        if (ass->varIndex == var->index && Bv_IsBitSet(ass->index, IRO_Avail) && !PropagationHasDefsInUnorderedRegions(linear, ass->linear2)) {
                            if (ass->linear2->type == IROLinearOperand && IRO_is_CPtypeequal(linear->rtype, ass->linear->u.diadic.left->rtype)) {
                                ENode *enode = IRO_NewENode(ass->linear2->u.node->type);
                                *enode = *ass->linear2->u.node;
                                if (enode->type == EINTCONST) {
                                    IRO_TruncateValueToType(&enode->data.intval, linear->rtype);
                                    enode->rtype = linear->rtype;
                                } else if (enode->type == EOBJREF) {
                                    IROLinear *tmp = IRO_LocateFather(linear);
                                    if (tmp && (tmp->flags & IROLF_Assigned))
                                        linear->flags |= IROLF_Assigned;
                                }
                                linear->u.monadic->type = IROLinearNop;
                                linear->type = IROLinearOperand;
                                linear->u.node = enode;
                            } else if (IRO_IsVariable(ass->linear2) && IRO_is_CPtypeequal(linear->rtype, ass->linear->rtype)) {
                                linear->u.monadic->u.node = create_objectrefnode(ass->linear2->u.monadic->u.node->data.objref);
                                if (ass->linear2->flags & IROLF_BitfieldIndirect)
                                    linear->flags |= IROLF_BitfieldIndirect;
                            } else if (IRO_is_CPtypeequal(linear->rtype, ass->linear->rtype) && ass->x20 == 1 && !VarIsUsedInOtherFNodes(var, node)) {
                                IROList list;
                                IRO_InitList(&list);
                                IRO_DuplicateExpr(ass->linear->u.diadic.right, &list);
                                if (IS_TYPE_FLOAT(ass->linear->rtype)) {
                                    IROLinear *tmp = IRO_NewLinear(IROLinearOp1Arg);
                                    tmp->index = ++IRO_NumLinear;
                                    tmp->rtype = ass->linear->rtype;
                                    tmp->nodetype = ETYPCON;
                                    tmp->nodeflags = ENODE_FLAG_80;
                                    tmp->u.monadic = list.tail;
                                    IRO_AddToList(tmp, &list);
                                }
                                IRO_PasteAfter(list.head, list.tail, linear);
                                IRO_LocateFather_Cut_And_Paste(linear, list.tail);
                                linear = list.tail;
                            }
                            IRO_Dump("Found expression propagation at %d from %d\n", linear->index, ass->linear->index);
                            break;
                        }
                    }
                }
            }

            if (linear->type != IROLinearNop && IsIntGenKillCandidate(linear)) {
                Bv_Clear(IRO_VarKills);
                IRO_GetKills(linear);
                for (ass = IRO_FirstAssign; ass; ass = ass->next) {
                    if (Bv_IsBitSet(ass->varIndex, IRO_VarKills))
                        Bv_ClearBit(ass->index, IRO_Avail);
                    if ((obj = IRO_IsVariable(ass->linear->u.diadic.right))) {
                        if ((var = IRO_FindVar(obj, 0, 1))) {
                            if (Bv_IsBitSet(var->index, IRO_VarKills))
                                Bv_ClearBit(ass->index, IRO_Avail);
                        }
                    } else {
                        IROList list;
                        IRO_InitList(&list);
                        IRO_Depends = ass->depends;
                        IRO_FindDepends_NoAlloc(ass->linear->u.diadic.right);
                        if (Bv_BitsInCommon(IRO_VarKills, ass->depends))
                            Bv_ClearBit(ass->index, IRO_Avail);
                    }
                }

                for (ass = IRO_FirstAssign; ass; ass = ass->next) {
                    IRO_Depends = ass->depends;
                    IRO_FindDepends_NoAlloc(ass->linear->u.diadic.right);
                    if (ass->linear == linear && !Bv_IsBitSet(ass->varIndex, ass->depends))
                        Bv_SetBit(ass->index, IRO_Avail);
                }
            }

            if (linear == node->last)
                break;
            linear = linear->next;
        }
    }

    IRO_CheckForUserBreak();
}