Source/JavaScriptCore/dfg/DFGSSACalculator.h

/*
 * Copyright (C) 2014 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#pragma once

#if ENABLE(DFG_JIT)

#include "DFGDominators.h"
#include "DFGGraph.h"

namespace JSC { namespace DFG {

// SSACalculator provides a reusable tool for using the Cytron, Ferrante, Rosen, Wegman, and
// Zadeck "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph"
// (TOPLAS'91) algorithm for computing SSA. SSACalculator doesn't magically do everything for you
// but it maintains the major data structures and handles most of the non-local reasoning. Here's
// the workflow of using SSACalculator to execute this algorithm:
//
// 0) Create a fresh SSACalculator instance. You will need this instance only for as long as
//    you're not yet done computing SSA.
//
// 1) Create an SSACalculator::Variable for every variable that you want to do Phi insertion
//    on. SSACalculator::Variable::index() is a dense indexing of the Variables that you
//    created, so you can easily use a Vector to map the SSACalculator::Variables to your
//    variables.
//
// 2) Create a SSACalculator::Def for every assignment to those variables. A Def knows about the
//    variable, the block, and the DFG::Node* that has the value being put into the variable.
//    Note that creating a Def in block B for variable V if block B already has a def for variable
//    V will overwrite the previous Def's DFG::Node* value. This enables you to create Defs by
//    processing basic blocks in forward order. If a block has multiple Defs of a variable, this
//    "just works" because each block will then remember the last Def of each variable.
//
// 3) Call SSACalculator::computePhis(). This takes a functor that will create the Phi nodes. The
//    functor returns either the Phi node it created, or nullptr, if it chooses to prune. (As an
//    aside, it's always sound not to prune, and the safest reason for pruning is liveness.) The
//    computePhis() code will record the created Phi nodes as Defs, and it will separately record
//    the list of Phis inserted at each block. It's OK for the functor you pass here to modify the
//    DFG::Graph on the fly, but the easiest way to write this is to just create the Phi nodes by
//    doing Graph::addNode() and return them. It's then best to insert all Phi nodes for a block
//    in bulk as part of the pass you do below, in step (4).
//
// 4) Modify the graph to create the SSA data flow. For each block, this should:
//
//    4.0) Compute the set of reaching defs (aka available values) for each variable by calling
//         SSACalculator::reachingDefAtHead() for each variable. Record this in a local table that
//         will be incrementally updated as you proceed through the block in forward order in the
//         next steps:
//
//         FIXME: It might be better to compute reaching defs for all live variables in one go, to
//         avoid doing repeated dom tree traversals.
//         https://bugs.webkit.org/show_bug.cgi?id=136610
//
//    4.1) Insert all of the Phi nodes for the block by using SSACalculator::phisForBlock(), and
//         record those Phi nodes as being available values.
//
//    4.2) Process the block in forward order. For each load from a variable, replace it with the
//         available SSA value for that variable. For each store, delete it and record the stored
//         value as being available.
//
//         Note that you have two options of how to replace loads with SSA values. You can replace
//         the load with an Identity node; this will end up working fairly naturally so long as
//         you run GCSE after your phase. Or, you can replace all uses of the load with the SSA
//         value yourself (using the Graph::performSubstitution() idiom), but that requires that
//         your loop over basic blocks proceeds in the appropriate graph order, for example
//         preorder.
//
//         FIXME: Make it easier to do this, that doesn't involve rerunning GCSE.
//         https://bugs.webkit.org/show_bug.cgi?id=136639
//
//    4.3) Insert Upsilons at the end of the current block for the corresponding Phis in each successor block. 
//         Use the available values table to decide the source value for each Phi's variable. Note that 
//         you could also use SSACalculator::reachingDefAtTail() instead of the available values table, 
//         though your local available values table is likely to be more efficient.
//
// The most obvious use of SSACalculator is for the CPS->SSA conversion itself, but it's meant to
// also be used for SSA update and for things like the promotion of heap fields to local SSA
// variables.

class SSACalculator {
public:
    SSACalculator(Graph&);
    ~SSACalculator();
    
    void reset();
    
    class Variable {
    public:
        unsigned index() const { return m_index; }
        
        void dump(PrintStream&) const;
        void dumpVerbose(PrintStream&) const;
        
    private:
        friend class SSACalculator;
        
        Variable()
            : m_index(UINT_MAX)
        {
        }
        
        Variable(unsigned index)
            : m_index(index)
        {
        }

        BlockList m_blocksWithDefs;
        unsigned m_index;
    };
    
    class Def {
    public:
        Variable* variable() const { return m_variable; }
        BasicBlock* block() const { return m_block; }
        
        Node* value() const { return m_value; }
        
        void dump(PrintStream&) const;
        
    private:
        friend class SSACalculator;
        
        Def()
            : m_variable(nullptr)
            , m_block(nullptr)
            , m_value(nullptr)
        {
        }
        
        Def(Variable* variable, BasicBlock* block, Node* value)
            : m_variable(variable)
            , m_block(block)
            , m_value(value)
        {
        }
        
        Variable* m_variable;
        BasicBlock* m_block;
        Node* m_value;
    };
    
    Variable* newVariable();
    Def* newDef(Variable*, BasicBlock*, Node*);
    
    Variable* variable(unsigned index) { return &m_variables[index]; }
    
    // The PhiInsertionFunctor takes a Variable and a BasicBlock and either inserts a Phi and
    // returns the Node for that Phi, or it decides that it's not worth it to insert a Phi at that
    // block because of some additional pruning condition (typically liveness) and returns
    // nullptr. If a non-null Node* is returned, a new Def is created, so that
    // nonLocalReachingDef() will find it later. Note that it is generally always sound to not
    // prune any Phis (that is, to always have the functor insert a Phi and never return nullptr).
    template<typename PhiInsertionFunctor>
    void computePhis(const PhiInsertionFunctor& functor)
    {
        DFG_ASSERT(m_graph, nullptr, m_graph.m_ssaDominators);
        
        for (Variable& variable : m_variables) {
            m_graph.m_ssaDominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
                variable.m_blocksWithDefs,
                [&] (BasicBlock* block) -> bool {
                    Node* phiNode = functor(&variable, block);
                    if (!phiNode)
                        return false;
                    
                    BlockData& data = m_data[block];
                    Def* phiDef = m_phis.add(Def(&variable, block, phiNode));
                    data.m_phis.append(phiDef);
                    
                    // Note that it's possible to have a block that looks like this before SSA
                    // conversion:
                    //
                    // label:
                    //     print(x);
                    //     ...
                    //     x = 42;
                    //     goto label;
                    //
                    // And it may look like this after SSA conversion:
                    //
                    // label:
                    //     x1: Phi()
                    //     ...
                    //     Upsilon(42, ^x1)
                    //     goto label;
                    //
                    // In this case, we will want to insert a Phi in this block, and the block
                    // will already have a Def for the variable. When this happens, we don't want
                    // the Phi to override the original Def, since the Phi is at the top, the
                    // original Def in the m_defs table would have been at the bottom, and we want
                    // m_defs to tell us about defs at tail.
                    //
                    // So, we rely on the fact that HashMap::add() does nothing if the key was
                    // already present.
                    data.m_defs.add(&variable, phiDef);
                    return true;
                });
        }
    }
    
    const Vector<Def*>& phisForBlock(BasicBlock* block)
    {
        return m_data[block].m_phis;
    }
    
    // Ignores defs within the given block; it assumes that you've taken care of those
    // yourself.
    Def* nonLocalReachingDef(BasicBlock*, Variable*);
    Def* reachingDefAtHead(BasicBlock* block, Variable* variable)
    {
        return nonLocalReachingDef(block, variable);
    }
    
    // Considers the def within the given block, but only works at the tail of the block.
    Def* reachingDefAtTail(BasicBlock*, Variable*);
    
    void dump(PrintStream&) const;
    
private:
    SegmentedVector<Variable> m_variables;
    Bag<Def> m_defs;
    
    Bag<Def> m_phis;
    
    struct BlockData {
        HashMap<Variable*, Def*> m_defs;
        Vector<Def*> m_phis;
    };
    
    BlockMap<BlockData> m_data;
    
    Graph& m_graph;
};

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)