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)

TODO