/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Intel
 *
 */

#include "LoopUtils.h"
#include "Inst.h"

namespace Jitrino {

InvariantOpndLoopInfo* InductiveOpndLoopInfo::getStartValue() {
    return startValue;
}

InvariantOpndLoopInfo* InductiveOpndLoopInfo::getEndValue() {
    if (boundType != UNKNOWN_BOUND) {
        return endValue;
    }
    findBoundInfo();
    return endValue;
}

void InductiveOpndLoopInfo::setStartValue(InvariantOpndLoopInfo* start) {
    startValue = start;
}

void InductiveOpndLoopInfo::setEndValue(InvariantOpndLoopInfo* end) {
    endValue = end;
}

BoundType InductiveOpndLoopInfo::getBoundType() {
    if (boundType != UNKNOWN_BOUND) {
        return boundType;
    }
    findBoundInfo();
    return boundType;
}

void InductiveOpndLoopInfo::findBoundInfo() {
    BranchInst* branchInst = NULL;
    OpndLoopInfo* opndInfo = NULL;
    
    const Nodes& loopNodes =  inductionDetector->loopNode->getNodesInLoop();
    for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; it++) {
        Node* node = *it;
        branchInst = ((Inst*)node->getLastInst())->asBranchInst();
        
        if (branchInst == NULL) continue;
        
        SsaOpnd* leftOpnd = branchInst->getSrc(0)->asSsaOpnd();
        SsaOpnd* rightOpnd = (branchInst->getNumSrcOperands() == 2)
            ? branchInst->getSrc(1)->asSsaOpnd() : NULL;
        Edge* trueEdge = node->getTrueEdge();
        Edge* falseEdge = node->getFalseEdge();
        bool isTrueExit = inductionDetector->loopNode->isLoopExit(trueEdge);
        bool isFalseExit = inductionDetector->loopNode->isLoopExit(falseEdge);

        // Check if branch matches.
        if ((isTrueExit || isFalseExit) && (leftOpnd == mainOpnd || rightOpnd == mainOpnd)) {

            ComparisonModifier compMod = branchInst->getComparisonModifier();
            switch (compMod) {
            case Cmp_Zero:
                boundType = isTrueExit ? NE_BOUND : EQ_BOUND;
                endValue = inductionDetector->zero;
                break;
            case Cmp_NonZero:
                boundType = isTrueExit ? EQ_BOUND : NE_BOUND;
                endValue = inductionDetector->zero;
                break;
            case Cmp_EQ: {
                boundType = isTrueExit ? NE_BOUND : EQ_BOUND;
                opndInfo = (leftOpnd == mainOpnd)
                    ? inductionDetector->getOpndInfo(rightOpnd)
                    : inductionDetector->getOpndInfo(leftOpnd);
                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
                break;
            }
            case Cmp_NE_Un:
                boundType = isTrueExit ? EQ_BOUND : NE_BOUND;
                opndInfo = (leftOpnd == mainOpnd)
                    ? inductionDetector->getOpndInfo(rightOpnd)
                    : inductionDetector->getOpndInfo(leftOpnd);
                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
                break;
            case Cmp_GT:
            case Cmp_GT_Un:
                if (leftOpnd == mainOpnd) {
                    // indVar >= invVar
                    boundType = isTrueExit ? UPPER_EQ_BOUND : LOW_BOUND;
                    opndInfo = inductionDetector->getOpndInfo(rightOpnd);
                } else {
                    // invVar >= indVar
                    boundType = isTrueExit ? LOW_EQ_BOUND : UPPER_BOUND;
                    opndInfo = inductionDetector->getOpndInfo(leftOpnd);
                }
                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
                break;
            case Cmp_GTE:
            case Cmp_GTE_Un:
                if (leftOpnd == mainOpnd) {
                    // indVar >= invVar
                    boundType = isTrueExit ? UPPER_BOUND : LOW_EQ_BOUND;
                    opndInfo = inductionDetector->getOpndInfo(rightOpnd);
                } else {
                    // invVar >= indVar
                    boundType = isTrueExit ? LOW_BOUND : UPPER_EQ_BOUND;
                    opndInfo = inductionDetector->getOpndInfo(leftOpnd);
                }
                endValue = (opndInfo != NULL) ? opndInfo->asInvarinat() : NULL;
                break;
            default:;
            };
            return;
        }
    }    
}

InductionDetector::InductionDetector(MemoryManager& mm, LoopNode* loop):
    memoryManager(mm), loopNode(loop), defStack(mm) {

    zero = createConstOpnd(NULL, 0);
    one = createConstOpnd(NULL, 1);
};

OpndLoopInfo* InductionDetector::processOpnd(SsaOpnd * opnd) {
    OpndLoopInfo* resultOpnd = NULL;
    Inst* defInst = opnd->getInst();

    if (std::find(defStack.begin(), defStack.end(), defInst) != defStack.end()) {
        return createInductiveOpnd(opnd, one, NULL, zero);
    }

    Node* defNode = defInst->getNode();
    Opcode opcode = defInst->getOpcode();

    if (opcode == Op_LdConstant) {
        return createConstOpnd(opnd, defInst->asConstInst()->getValue().i4);
    }

    if (!loopNode->inLoop(defNode)) {
        return createInvariantOpnd(opnd);
    }

    defStack.push_back(defInst);

    switch (opcode) {
    case Op_Phi: {
        OpndLoopInfo* info1 = processOpnd(defInst->getSrc(0)->asSsaOpnd());
        OpndLoopInfo* info2 = (info1 != NULL && defInst->getNumSrcOperands() == 2)
            ? processOpnd(defInst->getSrc(1)->asSsaOpnd()) : NULL;
        if (info2 != NULL) {
            InductiveOpndLoopInfo* indOpnd = (info1->isInductive() && !info1->asInductive()->isPhiSplit) ?
                info1->asInductive() : ((info2->isInductive() && !info2->asInductive()->isPhiSplit) ?
                info2->asInductive() : NULL);
            InvariantOpndLoopInfo* invOpnd = info1->isInvariant() ? info1->asInvarinat() :
                (info2->isInvariant() ? info2->asInvarinat() : NULL); 
            if (indOpnd != NULL && invOpnd != NULL) {
                InductiveOpndLoopInfo* resOpnd = createInductiveOpnd(opnd, one,
                    NULL, indOpnd->getStride());
                resOpnd->startValue = invOpnd;
                resOpnd->header = opnd;                
                resOpnd->isPhiSplit = true;
                resultOpnd = resOpnd;
            }
        }
        break;
    } 
    case Op_Add:
    case Op_Sub:
    case Op_Mul: {
        SsaOpnd *op1 = defInst->getSrc(0)->asSsaOpnd();
        SsaOpnd *op2 = defInst->getSrc(1)->asSsaOpnd();
        OpndLoopInfo* info1 = processOpnd(op1);
        OpndLoopInfo* info2 = (info1 != NULL) ? processOpnd(op2) : NULL;

        if (info2 != NULL) {
            if (info1->isInvariant() && info2->isInvariant()) {
                InvariantOpndLoopInfo* invOpnd1 = info1->asInvarinat();
                InvariantOpndLoopInfo* invOpnd2 = info2->asInvarinat();
                if (invOpnd1->isConstant() && invOpnd2->isConstant()) {
                    int val1 = invOpnd1->asConstant()->getValue();
                    int val2 = invOpnd2->asConstant()->getValue();
                    if (opcode == Op_Add) {
                        resultOpnd = createConstOpnd(opnd, val1 + val2);                        
                    } else if (opcode == Op_Sub) {
                        resultOpnd = createConstOpnd(opnd, val1 - val2);
                    } else {
                        assert(opcode == Op_Mul);
                        resultOpnd = createConstOpnd(opnd, val1 * val2);
                    }
                } else {
                    resultOpnd = createInvariantOpnd(opnd);
                }
            } else {
                InductiveOpndLoopInfo* indOpnd = (info1->isInductive() && !info1->asInductive()->isPhiSplit) ?
                    info1->asInductive() : ((info2->isInductive() && !info2->asInductive()->isPhiSplit) ?
                    info2->asInductive() : NULL);
                InvariantOpndLoopInfo* invOpnd = info1->isInvariant() ? info1->asInvarinat() :
                    (info2->isInvariant() ? info2->asInvarinat() : NULL); 
                
                if (indOpnd != NULL && invOpnd != NULL) {
                    InductiveOpndLoopInfo* resOpnd = NULL;
                    if (opcode == Op_Add || opcode == Op_Sub) {
                        resOpnd = createInductiveOpnd(opnd, one, indOpnd, invOpnd);
                    } else {
                        assert(opcode == Op_Mul);
                        resOpnd = createInductiveOpnd(opnd, invOpnd, indOpnd, zero);
                    }
                    resOpnd->isPhiSplit = indOpnd->isPhiSplit;
                    resOpnd->header = indOpnd->header;
                    resultOpnd = resOpnd;
                }
            }
        }
        break;
    }
    case Op_StVar:
    case Op_LdVar: {
        resultOpnd = processOpnd(defInst->getSrc(0)->asSsaOpnd());
        if (resultOpnd != NULL) {
            resultOpnd->mainOpnd = opnd;
        }
        break;
    }
    case Op_TauArrayLen: {
        resultOpnd = processOpnd(defInst->getSrc(0)->asSsaOpnd());
        if (resultOpnd != NULL) {
            resultOpnd->mainOpnd = opnd;
        }
        break;
    }
    default:;
    };

    defStack.pop_back();
    return resultOpnd;
}

OpndLoopInfo* InductionDetector::getOpndInfo(SsaOpnd * opnd,
                                             IVDetectionMode mode) {
    // TODO: Current implementation doesn't support other modes.
    assert(mode == IGNORE_BRANCH);
    defStack.clear();
    ivMode = mode;
    return processOpnd(opnd);
}

} // namespace Jitrino