IonMonkey/Global value numbering

GVN is a very powerful optimization for the engine. It folds similar expressions making sure we only have to execute it once, but also folds common expressions. wiki:Global_value_numbering

Overview

Every MIR node has to implement functions for different functionality.
For GVN these functions are:

bool congruentTo(const MDefinition* ins)
MDefinition* foldsTo(TempAllocator& alloc)

Both these function will by default return values that will disable any GVN optimizations. Every MIR node can override the default behaviour and opt-into GVN

Similar expressions

bool congruentTo(const MDefinition* ins)

This function is used to see if two MIR nodes do the exact same thing. It has to return true when the argument ins computes the same thing as this. That means this function has to check if both MIR nodes are the same opcode, check if the return type is the same, if the flags are similar and if the operands are the same. When this function returns true GVN can optimize these two MIR nodes. It will remove one of MIR nodes and all uses of that MIR node will be replaced with the other MIR node.

Examples

bool congruentTo(const MDefinition* ins) const override {                                      
    return congruentIfOperandsEqual(ins);                                                      
}

The helperfunction "congruentIfOperandsEqual" is provided that does the most basic testing. It does all the tests that are needed if the MIR node doesn't save any internal state.

bool congruentTo(const MDefinition* ins) const override {                                      
        if (op() != ins->op())
            return false;

        if (type() != ins->type())
            return false;

        if (isEffectful() || ins->isEffectful())
            return false;

        if (getOperand(0) == ins->getOperand(0) &&
            getOperand(1) == ins->getOperand(1))
        {
            return true;
        }

        if (getOperand(0) == ins->getOperand(1) &&
            getOperand(1) == ins->getOperand(0))
        {
            return true;
        }

        return false;
}

Some MIR nodes are commutative. As a result we need to check if "MNode a b" matches "MNode a b" or "MNode b a". The above snippit does this, which is for example used for MAdd (addition).

bool congruentTo(const MDefinition* ins) const override {                                      
    if (!congruentIfOperandsEqual(ins))
        return false;
    return !ins->toUnbox()->mode() == mode();                   
}

Here you see an example of a MIR node that saves internal state. The mode of an MUnbox decides how the unboxing should happen. As a result two MUnbox nodes are only similar if the mode is the same.

Common expressions

MDefinition* foldsTo(TempAllocator& alloc)

This function is used to fold common expressions into simpler or faster variants. The function returns this when it cannot get folded and the new MIR node when it can get folded. A common uses of this function is to replace MIR nodes that have constant operands and replace this node with the computed value. But it is not limited to constant folding. Specific combinations of MIR nodes can get matched and replaced by this function.

There are some caveats when implementing such a function:

• One needs to keep type consistent. The output type of the replacement MIR node must be the same as the replaced MIR node.
• If you make an assumption on type of the operand and don't use that operand in the replacement MIR node you need to mark that the operand as "setGuardRangeBailouts". That will make sure the engine doesn't remove the type assumption.

Examples

MDefinition*
MNot::foldsTo(TempAllocator& alloc)
{
    // 1) Fold constant inputs
    if (MConstant* inputConst = input()->maybeConstantValue()) {
        bool b;
        if (inputConst->valueToBoolean(&b))
            return MConstant::New(alloc, BooleanValue(!b));
    }

    // 2) Fold MNot (MNot (MNot x)) to MNot x
    MDefinition* op = getOperand(0);
    if (op->isNot()) {
        MDefinition* opop = op->getOperand(0);
        if (opop->isNot())
            return opop;
    }

    // 3) Fold specific input types to constants
    if (input()->type() == MIRType::Undefined || input()->type() == MIRType::Null)
        return MConstant::New(alloc, BooleanValue(true));
    if (input()->type() == MIRType::Symbol)
        return MConstant::New(alloc, BooleanValue(false));
    if (input()->type() == MIRType::Object)
        return MConstant::New(alloc, BooleanValue(false));

    return this;
}

This is an example of the implementation of MNot. Here we can distinguish folding happing based on three different reasons.

1. The first checks are for constant propagation. If the input is a constant it is possible to just compute the result.
2. Second part is checking for a common combination of MIR nodes. We try to find a succession of three MNot and remove the two unneeded MNots.
3. Last part shows how we can look at the input type of the MNot and use that information to fold this MNot.