/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "Ion.h"
#include "IonBuilder.h"
#include "IonSpewer.h"
#include "CompileInfo.h"
#include "ValueNumbering.h"

using namespace js;
using namespace js::jit;

ValueNumberer::ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic)
  : mir(mir),
    graph_(graph),
    pessimisticPass_(!optimistic),
    count_(0)
{ }

uint32_t
ValueNumberer::lookupValue(MDefinition *ins)
{
    ValueMap::AddPtr p = values.lookupForAdd(ins);
    if (p) {
        // make sure this is in the correct group
        setClass(ins, p->key);
        return p->value;
    }

    if (!values.add(p, ins, ins->id()))
        return 0;
    breakClass(ins);

    return ins->id();
}

MDefinition *
ValueNumberer::simplify(MDefinition *def, bool useValueNumbers)
{
    if (def->isEffectful())
        return def;

    MDefinition *ins = def->foldsTo(useValueNumbers);

    if (ins == def || !ins->updateForFolding(def))
        return def;

    // ensure this instruction has a VN
    if (!ins->valueNumberData())
        ins->setValueNumberData(new ValueNumberData);
    if (!ins->block()) {
        // In this case, we made a new def by constant folding, for
        // example, we replaced add(#3,#4) with a new const(#7) node.

        // We will only fold a phi into one of its operands.
        JS_ASSERT(!def->isPhi());

        def->block()->insertAfter(def->toInstruction(), ins->toInstruction());
        ins->setValueNumber(lookupValue(ins));
    }

    JS_ASSERT(ins->id() != 0);

    def->replaceAllUsesWith(ins);

    IonSpew(IonSpew_GVN, "Folding %d to be %d", def->id(), ins->id());
    return ins;
}

MControlInstruction *
ValueNumberer::simplifyControlInstruction(MControlInstruction *def)
{
    if (def->isEffectful())
        return def;

    MDefinition *repl = def->foldsTo(false);
    if (repl == def || !repl->updateForFolding(def))
        return def;

    // Ensure this instruction has a value number.
    if (!repl->valueNumberData())
        repl->setValueNumberData(new ValueNumberData);

    MBasicBlock *block = def->block();

    // MControlInstructions should not have consumers.
    JS_ASSERT(repl->isControlInstruction());
    JS_ASSERT(def->useCount() == 0);

    if (def->isInWorklist())
        repl->setInWorklist();

    block->discardLastIns();
    block->end((MControlInstruction *)repl);
    return (MControlInstruction *)repl;
}

void
ValueNumberer::markDefinition(MDefinition *def)
{
    if (isMarked(def))
        return;

    IonSpew(IonSpew_GVN, "marked %d", def->id());
    def->setInWorklist();
    count_++;
}

void
ValueNumberer::unmarkDefinition(MDefinition *def)
{
    if (pessimisticPass_)
        return;

    JS_ASSERT(count_ > 0);
    IonSpew(IonSpew_GVN, "unmarked %d", def->id());
    def->setNotInWorklist();
    count_--;
}

void
ValueNumberer::markBlock(MBasicBlock *block)
{
    for (MDefinitionIterator iter(block); iter; iter++)
        markDefinition(*iter);
    markDefinition(block->lastIns());
}

void
ValueNumberer::markConsumers(MDefinition *def)
{
    if (pessimisticPass_)
        return;

    JS_ASSERT(!def->isInWorklist());
    JS_ASSERT(!def->isControlInstruction());
    for (MUseDefIterator use(def); use; use++)
        markDefinition(use.def());
}

bool
ValueNumberer::computeValueNumbers()
{
    // At the end of this function, we will have the value numbering stored in
    // each instruction.
    //
    // We also need an "optimistic" value number, for temporary use, which is
    // stored in a hashtable.
    //
    // For the instruction x := y op z, we map (op, VN[y], VN[z]) to a value
    // number, say v. If it is not in the map, we use the instruction id.
    //
    // If the instruction in question's value number is not already
    // v, we break the congruence and set it to v. We repeat until saturation.
    // This will take at worst O(d) time, where d is the loop connectedness
    // of the SSA def/use graph.
    //
    // The algorithm is the simple RPO-based algorithm from
    // "SCC-Based Value Numbering" by Cooper and Simpson.
    //
    // If we are performing a pessimistic pass, then we assume that every
    // definition is in its own congruence class, since we know nothing about
    // values that enter Phi nodes through back edges. We then make one pass
    // through the graph, ignoring back edges. This yields less congruences on
    // any graph with back-edges, but is much faster to perform.

    IonSpew(IonSpew_GVN, "Numbering instructions");

    if (!values.init())
        return false;
    // Stick a VN object onto every mdefinition
    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
        if (mir->shouldCancel("Value Numbering (preparation loop"))
            return false;
        for (MDefinitionIterator iter(*block); iter; iter++)
            iter->setValueNumberData(new ValueNumberData);
        MControlInstruction *jump = block->lastIns();
        jump->setValueNumberData(new ValueNumberData);
    }

    // Assign unique value numbers if pessimistic.
    // It might be productive to do this in the MDefinition constructor or
    // possibly in a previous pass, if it seems reasonable.
    if (pessimisticPass_) {
        for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
            for (MDefinitionIterator iter(*block); iter; iter++)
                iter->setValueNumber(iter->id());
        }
    } else {
        // For each root block, add all of its instructions to the worklist.
        markBlock(*(graph_.begin()));
        if (graph_.osrBlock())
            markBlock(graph_.osrBlock());
    }

    while (count_ > 0) {
#ifdef DEBUG
        if (!pessimisticPass_) {
            size_t debugCount = 0;
            IonSpew(IonSpew_GVN, "The following instructions require processing:");
            for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
                for (MDefinitionIterator iter(*block); iter; iter++) {
                    if (iter->isInWorklist()) {
                        IonSpew(IonSpew_GVN, "\t%d", iter->id());
                        debugCount++;
                    }
                }
                if (block->lastIns()->isInWorklist()) {
                    IonSpew(IonSpew_GVN, "\t%d", block->lastIns()->id());
                    debugCount++;
                }
            }
            if (!debugCount)
                IonSpew(IonSpew_GVN, "\tNone");
            JS_ASSERT(debugCount == count_);
        }
#endif
        for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
            if (mir->shouldCancel("Value Numbering (main loop)"))
                return false;
            for (MDefinitionIterator iter(*block); iter; ) {

                if (!isMarked(*iter)) {
                    iter++;
                    continue;
                }

                JS_ASSERT_IF(!pessimisticPass_, count_ > 0);
                unmarkDefinition(*iter);

                MDefinition *ins = simplify(*iter, false);

                if (ins != *iter) {
                    iter = block->discardDefAt(iter);
                    continue;
                }

                uint32_t value = lookupValue(ins);

                if (!value)
                    return false; // Hashtable insertion failed

                if (ins->valueNumber() != value) {
                    IonSpew(IonSpew_GVN,
                            "Broke congruence for instruction %d (%p) with VN %d (now using %d)",
                            ins->id(), (void *) ins, ins->valueNumber(), value);
                    ins->setValueNumber(value);
                    markConsumers(ins);
                }

                iter++;
            }
            // Process control flow instruction:
            MControlInstruction *jump = block->lastIns();
            jump = simplifyControlInstruction(jump);

            // If we are pessimistic, then this will never get set.
            if (!jump->isInWorklist())
                continue;
            unmarkDefinition(jump);
            if (jump->valueNumber() == 0) {
                jump->setValueNumber(jump->id());
                for (size_t i = 0; i < jump->numSuccessors(); i++)
                    markBlock(jump->getSuccessor(i));
            }

        }

        // If we are doing a pessimistic pass, we only go once through the
        // instruction list.
        if (pessimisticPass_)
            break;
    }
#ifdef DEBUG
    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
        for (MDefinitionIterator iter(*block); iter; iter++) {
            JS_ASSERT(!iter->isInWorklist());
            JS_ASSERT(iter->valueNumber() != 0);
        }
    }
#endif
    return true;
}

MDefinition *
ValueNumberer::findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index)
{
    JS_ASSERT(ins->valueNumber() != 0);
    InstructionMap::Ptr p = defs.lookup(ins->valueNumber());
    MDefinition *dom;
    if (!p || index > p->value.validUntil) {
        DominatingValue value;
        value.def = ins;
        // Since we are traversing the dominator tree in pre-order, when we
        // are looking at the |index|-th block, the next numDominated() blocks
        // we traverse are precisely the set of blocks that are dominated.
        //
        // So, this value is visible in all blocks if:
        // index <= index + ins->block->numDominated()
        // and becomes invalid after that.
        value.validUntil = index + ins->block()->numDominated();

        if(!defs.put(ins->valueNumber(), value))
            return NULL;

        dom = ins;
    } else {
        dom = p->value.def;
    }

    return dom;
}

bool
ValueNumberer::eliminateRedundancies()
{
    // A definition is 'redundant' iff it is dominated by another definition
    // with the same value number.
    //
    // So, we traverse the dominator tree in pre-order, maintaining a hashmap
    // from value numbers to instructions.
    //
    // For each definition d with value number v, we look up v in the hashmap.
    //
    // If there is a definition d' in the hashmap, and the current traversal
    // index is within that instruction's dominated range, then we eliminate d,
    // replacing all uses of d with uses of d'.
    //
    // If there is no valid definition in the hashtable (the current definition
    // is not in dominated scope), then we insert the current instruction,
    // since it is the most dominant instruction with the given value number.

    InstructionMap defs;

    if (!defs.init())
        return false;

    IonSpew(IonSpew_GVN, "Eliminating redundant instructions");

    // Stack for pre-order CFG traversal.
    Vector<MBasicBlock *, 1, IonAllocPolicy> worklist;

    // The index of the current block in the CFG traversal.
    size_t index = 0;

    // Add all self-dominating blocks to the worklist.
    // This includes all roots. Order does not matter.
    for (MBasicBlockIterator i(graph_.begin()); i != graph_.end(); i++) {
        MBasicBlock *block = *i;
        if (block->immediateDominator() == block) {
            if (!worklist.append(block))
                return false;
        }
    }

    // Starting from each self-dominating block, traverse the CFG in pre-order.
    while (!worklist.empty()) {
        if (mir->shouldCancel("Value Numbering (eliminate loop)"))
            return false;
        MBasicBlock *block = worklist.popCopy();

        IonSpew(IonSpew_GVN, "Looking at block %d", block->id());

        // Add all immediate dominators to the front of the worklist.
        if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
                             block->immediatelyDominatedBlocksEnd()))
            return false;

        // For each instruction, attempt to look up a dominating definition.
        for (MDefinitionIterator iter(block); iter; ) {
            MDefinition *ins = simplify(*iter, true);

            // Instruction was replaced, and all uses have already been fixed.
            if (ins != *iter) {
                iter = block->discardDefAt(iter);
                continue;
            }

            // Instruction has side-effects and cannot be folded.
            if (!ins->isMovable() || ins->isEffectful()) {
                iter++;
                continue;
            }

            MDefinition *dom = findDominatingDef(defs, ins, index);
            if (!dom)
                return false; // Insertion failed.

            if (dom == ins || !dom->updateForReplacement(ins)) {
                iter++;
                continue;
            }

            IonSpew(IonSpew_GVN, "instruction %d is dominated by instruction %d (from block %d)",
                    ins->id(), dom->id(), dom->block()->id());

            ins->replaceAllUsesWith(dom);

            JS_ASSERT(!ins->hasUses());
            JS_ASSERT(ins->block() == block);
            JS_ASSERT(!ins->isEffectful());
            JS_ASSERT(ins->isMovable());

            iter = ins->block()->discardDefAt(iter);
        }
        index++;
    }

    JS_ASSERT(index == graph_.numBlocks());
    return true;
}

// Exported method, called by the compiler.
bool
ValueNumberer::analyze()
{
    return computeValueNumbers() && eliminateRedundancies();
}

// Called by the compiler if we need to re-run GVN.
bool
ValueNumberer::clear()
{
    IonSpew(IonSpew_GVN, "Clearing value numbers");

    // Clear the VN of every MDefinition
    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
        if (mir->shouldCancel("Value Numbering (clearing)"))
            return false;
        for (MDefinitionIterator iter(*block); iter; iter++)
            iter->clearValueNumberData();
        block->lastIns()->clearValueNumberData();
    }

    return true;
}

uint32_t
MDefinition::valueNumber() const
{
    JS_ASSERT(block_);
    if (valueNumber_ == NULL)
        return 0;
    return valueNumber_->valueNumber();
}
void
MDefinition::setValueNumber(uint32_t vn)
{
    valueNumber_->setValueNumber(vn);
}
// Set the class of this to the given representative value.
void
ValueNumberer::setClass(MDefinition *def, MDefinition *rep)
{
    def->valueNumberData()->setClass(def, rep);
}

MDefinition *
ValueNumberer::findSplit(MDefinition *def)
{
    for (MDefinition *vncheck = def->valueNumberData()->classNext;
         vncheck != NULL;
         vncheck = vncheck->valueNumberData()->classNext) {
        if (!def->congruentTo(vncheck)) {
            IonSpew(IonSpew_GVN, "Proceeding with split because %d is not congruent to %d",
                    def->id(), vncheck->id());
            return vncheck;
        }
    }
    return NULL;
}

void
ValueNumberer::breakClass(MDefinition *def)
{
    if (def->valueNumber() == def->id()) {
        IonSpew(IonSpew_GVN, "Breaking congruence with itself: %d", def->id());
        ValueNumberData *defdata = def->valueNumberData();
        JS_ASSERT(defdata->classPrev == NULL);
        // If the def was the only member of the class, then there is nothing to do.
        if (defdata->classNext == NULL)
            return;
        // If upon closer inspection, we are still equivalent to this class
        // then there isn't anything for us to do.
        MDefinition *newRep = findSplit(def);
        if (!newRep)
            return;
        ValueNumberData *newdata = newRep->valueNumberData();

        // Right now, |defdata| is at the front of the list, and |newdata| is
        // somewhere in the middle.
        //
        // We want to move |defdata| and everything up to but excluding
        // |newdata| to a new list, with |defdata| still as the canonical
        // element.
        //
        // We then want to take |newdata| and everything after, and
        // mark them for processing (since |newdata| is now a new canonical
        // element).
        //
        MDefinition *lastOld = newdata->classPrev;

        JS_ASSERT(lastOld); // newRep is NOT the first element of the list.
        JS_ASSERT(lastOld->valueNumberData()->classNext == newRep);

        //lastOld is now the last element of the old list (congruent to
        //|def|)
        lastOld->valueNumberData()->classNext = NULL;

#ifdef DEBUG
        for (MDefinition *tmp = def; tmp != NULL; tmp = tmp->valueNumberData()->classNext) {
            JS_ASSERT(tmp->valueNumber() == def->valueNumber());
            JS_ASSERT(tmp->congruentTo(def));
            JS_ASSERT(tmp != newRep);
        }
#endif
        //|newRep| is now the first element of a new list, therefore it is the
        //new canonical element. Mark the remaining elements in the list
        //(including |newRep|)
        newdata->classPrev = NULL;
        IonSpew(IonSpew_GVN, "Choosing a new representative: %d", newRep->id());

        // make the VN of every member in the class the VN of the new representative number.
        for (MDefinition *tmp = newRep; tmp != NULL; tmp = tmp->valueNumberData()->classNext) {
            // if this instruction is already scheduled to be processed, don't do anything.
            if (tmp->isInWorklist())
                continue;
            IonSpew(IonSpew_GVN, "Moving to a new congruence class: %d", tmp->id());
            tmp->setValueNumber(newRep->id());
            markConsumers(tmp);
            markDefinition(tmp);
        }

        // Insert the new representative => number mapping into the table
        // Logically, there should not be anything in the table currently, but
        // old values are never removed, so there's a good chance something will
        // already be there.
        values.put(newRep, newRep->id());
    } else {
        // The element that is breaking from the list isn't the representative element
        // just strip it from the list
        ValueNumberData *defdata = def->valueNumberData();
        if (defdata->classPrev)
            defdata->classPrev->valueNumberData()->classNext = defdata->classNext;
        if (defdata->classNext)
            defdata->classNext->valueNumberData()->classPrev = defdata->classPrev;

        // Make sure there is no nastinees accidentally linking elements into the old list later.
        defdata->classPrev = NULL;
        defdata->classNext = NULL;
    }
}