/*
 *  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, Mikhail Y. Fursov
 */

#include "Ia32CodeLayout.h"
#include "Ia32IRManager.h"
#include "Log.h"
#include "Ia32Printer.h"
#include "Ia32CodeLayoutTopDown.h"
#include "Ia32CodeLayoutBottomUp.h"
namespace Jitrino
{
namespace Ia32 {

static ActionFactory <Layouter> _layout("layout");

#define ACCEPTABLE_DOUBLE_PRECISION_LOSS  0.000000001 

Linearizer::Linearizer(IRManager* irMgr) : irManager(irMgr) {
}



static Edge* findEdgeToAddJump(BasicBlock* block) {
    Inst* lastInst = (Inst*)block->getLastInst();
    BasicBlock* layoutSuccessor = block->getLayoutSucc();
    if (lastInst && lastInst->hasKind(Inst::Kind_BranchInst)) {
        BranchInst* br = (BranchInst*)lastInst;
        if (br->isDirect() && br->getFalseTarget() != layoutSuccessor) {
            return block->getFalseEdge();
        }
        return NULL;
    }
    if (lastInst && lastInst->hasKind(Inst::Kind_ControlTransferInst) && !lastInst->hasKind(Inst::Kind_CallInst)) { 
        //unconditional jumps (jump inst, ret, switch)
        return NULL;
    }
    
    if (block->getOutDegree() == 1 && block->getExceptionEdge()!=NULL) {
        return NULL; //throw
    }

    Edge* uncondEdge = block->getUnconditionalEdge();
    assert(uncondEdge);
    return uncondEdge->getTargetNode() == layoutSuccessor ? NULL : uncondEdge;
}


/**  Fix branches to work with the code layout */
void Linearizer::fixBranches() {
    MemoryManager tmpMM("Linearizer::fixBranches");
    Nodes nodes(tmpMM);
    irManager->getFlowGraph()->getNodes(nodes);
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node* node = *it;
        if (node->isBlockNode()) {
            BasicBlock* block = (BasicBlock*)node;
            BasicBlock* layoutSuccessor = block->getLayoutSucc();
            
            // If block ends with true branch to its layout successor reverse
            // the branch to fallthrough to the layout successor
            Inst * lastInst = (Inst*)block->getLastInst();
            if (lastInst!=NULL && lastInst->hasKind(Inst::Kind_BranchInst)) {
                BranchInst* bInst =  (BranchInst *)lastInst;
                if (bInst->isDirect()) {
                    Node * target = bInst->getTrueTarget();
                    if (target == layoutSuccessor) {
                        reverseBranchIfPossible(block);
                    }
                }
            }
            
            //check for every out edge that additional jump block is needed
            Edge* edge = findEdgeToAddJump(block);
            if (edge!=NULL) {
                BasicBlock * jmpBlk = addJumpBlock(edge);
                //  Put jump block after the block in code layout
                jmpBlk->setLayoutSucc(layoutSuccessor);
                block->setLayoutSucc(jmpBlk);
            }   
        }
    }
}


/**  Reverse branch predicate. 
     We assume that branch is the last instruction in the node.
  */
bool Linearizer::reverseBranchIfPossible(Node * bb) {
    //  Last instruction of the basic block should be predicated branch:
    //      (p1) br  N
    //  Find p2 in (p1,p2) or (p2,p1) produced by the compare.
    assert(bb->isBlockNode() && !bb->isEmpty() && ((Inst*)bb->getLastInst())->hasKind(Inst::Kind_BranchInst));
    BranchInst * branch = (BranchInst *)bb->getLastInst();
    assert(branch->isDirect());
    Edge* edge = bb->getTrueEdge();
    if (canEdgeBeMadeToFallThrough(edge)) {
        branch->reverse(irManager);
    }
    return true;
}


 /**  Add block containing jump instruction to the fallthrough successor
  *  after this block
  */
BasicBlock* Linearizer::addJumpBlock(Edge * fallEdge) {
    irManager->invalidateLivenessInfo();
    Inst* jumpInst = irManager->newJumpInst();
    Node* jumpBlock = irManager->getFlowGraph()->spliceBlockOnEdge(fallEdge, jumpInst);
    return (BasicBlock*)jumpBlock;
}



// Returns true if edge can be converted to a fall-through edge (i.e. an edge
// not requiring a branch) assuming the edge's head block is laid out after the tail block. 
bool Linearizer::canEdgeBeMadeToFallThrough(Edge *edge) {
    Inst *inst = (Inst*)edge->getSourceNode()->getLastInst();
    if (edge->isUnconditionalEdge()) {
        return inst == NULL || !inst->hasKind(Inst::Kind_SwitchInst);
    }
    assert(edge->isTrueEdge());
    assert(inst->hasKind(Inst::Kind_BranchInst));
    return ((BranchInst*)inst)->canReverse();
}

bool Linearizer::isBlockLayoutDone() {
    bool lastBlockFound = false;
    const Nodes& nodes = irManager->getFlowGraph()->getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node* node = *it;
        if (!node->isBlockNode()) {
            continue;
        }
        BasicBlock* block  = (BasicBlock*)node;
        if (block->getLayoutSucc()==NULL) {
           if (lastBlockFound) {
               return false; //two blocks without layout successor found
           }
           lastBlockFound = true;
        }
    }
    return lastBlockFound;
}

void Linearizer::linearizeCfg() {
    assert(!irManager->isLaidOut());
#ifdef _DEBUG
    bool livenessIsOkOnStart = irManager->hasLivenessInfo();
#endif
    
    linearizeCfgImpl();

    fixBranches();
    
    assert(isBlockLayoutDone());
    irManager->setLaidOut(true);
#ifdef _DEBUG
    checkLayout(irManager);
    if (livenessIsOkOnStart) {
        assert(irManager->ensureLivenessInfoIsValid());
    }
#endif
}


void Linearizer::doLayout(LinearizerType t, IRManager* irManager) {
    if (t == TOPDOWN) {
        TopDownLayout linearizer(irManager);
        linearizer.linearizeCfg();
    } else if (t == BOTTOM_UP) {
        BottomUpLayout linearizer(irManager);
        linearizer.linearizeCfg();
    } else {
        assert (t == TOPOLOGICAL);
        TopologicalLayout linearizer(irManager);
        linearizer.linearizeCfg();
    }
}

void Linearizer::checkLayout(IRManager* irm) {
#ifdef _DEBUG
    U_32 maxNodes = irm->getFlowGraph()->getMaxNodeId();
    StlVector<U_32> numVisits(irm->getMemoryManager(), maxNodes, 0); 
    StlVector<bool> isBB(irm->getMemoryManager(), maxNodes, false);
    
    // Find basic blocks
    bool wasLast = false;
    const Nodes& nodes = irm->getFlowGraph()->getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node *node = *it;
        if (node->isBlockNode()) {
            isBB[node->getId()] = true;
            BasicBlock* layoutSucc =((BasicBlock*)node)->getLayoutSucc();
            if (layoutSucc==NULL )  {
                assert(!wasLast);
                wasLast = true;
            } else {
                U_32 id = layoutSucc->getId();
                numVisits[id]++;
                assert(numVisits[id] == 1);
            }
        }
    }

    
    // Check that every basic block has been visited once
    bool wasFirst = false;
    for (U_32 i = 0; i < maxNodes; i++) {
        U_32 correctNumVisits = isBB[i] ? 1 : 0;
        if (numVisits[i] != correctNumVisits) {
            if (isBB[i] && numVisits[i] == 0 && !wasFirst) {
                wasFirst = true;
            } else {
                assert(0);
            }
        }
    }

    //check fallthru successors
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node *node = *it;
        if (node->isBlockNode()) {
            BasicBlock* block = (BasicBlock*)node;
            BasicBlock* layoutSucc = block->getLayoutSucc();
            Edge* fallEdge = layoutSucc==NULL ? NULL : block->findEdgeTo(true, layoutSucc);
            if (fallEdge == NULL) {
                Inst *inst = (Inst*)block->getLastInst();
                assert(!inst->hasKind(Inst::Kind_BranchInst)); //false edge must be fallthru
                bool ok = inst->hasKind(Inst::Kind_ControlTransferInst) && !inst->hasKind(Inst::Kind_CallInst);
                ok = ok || (block->getOutDegree() == 1 && block->getExceptionEdge() != NULL);
                assert(ok);
            } else {
                assert(fallEdge->isUnconditionalEdge() || fallEdge->isFalseEdge());
            }
        }
    }

#endif 
}




/////////////////////////////////////////////////////////////////////
/////////////////// TOPOLOGICAL LAYOUT //////////////////////////////

void TopologicalLayout::linearizeCfgImpl() {
    BasicBlock* prev = NULL;
    const Nodes& postOrderedNodes = irManager->getFlowGraph()->getNodesPostOrder();
    for (Nodes::const_reverse_iterator it = postOrderedNodes.rbegin(), end = postOrderedNodes.rend(); it!=end; ++it) {
        Node* node = *it;    
        if (!node->isBlockNode()) {
            continue;
        }
        BasicBlock* block = (BasicBlock*)node;
        if (prev!= NULL) {
            prev->setLayoutSucc(block);
        } else {
            assert(block == irManager->getFlowGraph()->getEntryNode());
        }
        prev=block; 
    }
}

//////////////////////////////////////////////////////////////////////////
///////////////////IRTransformer impl ////////////////////////////////////
void Layouter::runImpl() {
    const char* params = getArg("type");
    ControlFlowGraph* fg = irManager->getFlowGraph();
    bool hasEdgeProfile = fg->hasEdgeProfile();
    bool isClinit = irManager->getMethodDesc().isClassInitializer();
    Linearizer::LinearizerType type = hasEdgeProfile && !isClinit ? Linearizer::BOTTOM_UP : Linearizer::TOPOLOGICAL;
    if (params != NULL) {
        if (!strcmp(params, "bottomup")) {
            type = Linearizer::BOTTOM_UP;
        } else if (!strcmp(params, "topdown")) {
            type = Linearizer::TOPDOWN;
        } else if (!strcmp(params, "mixed")) {
            LoopTree* lt = fg->getLoopTree();
            type = lt->hasLoops() ? Linearizer::BOTTOM_UP  : Linearizer::TOPDOWN;
        } else if (!strcmp(params, "topological")) {
            type = Linearizer::TOPOLOGICAL;
        } else {
            if (Log::isEnabled()) {
                Log::out() << "Layout: unsupported layout type: '"<<params<<"' using default\n";;
            }
        }
    }
    if (type != Linearizer::TOPOLOGICAL && !hasEdgeProfile) {
        type = Linearizer::TOPOLOGICAL;
        if (Log::isEnabled()) {
            Log::out() << "Layout: not edge profile found: '"<<params<<"' using topological layout\n";;
        }
    }
    
    fg->purgeEmptyNodes();
    fg->getLoopTree()->rebuild(false);
    irManager->fixEdgeProfile();

    Linearizer::doLayout(type, &getIRManager());
}

}}//namespace