DFGBinarySwitch.h 4.23 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/*
 * Copyright (C) 2013 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. 
 */

#ifndef DFGBinarySwitch_h
#define DFGBinarySwitch_h

#include <wtf/Platform.h>

#if ENABLE(DFG_JIT)

33
#include "GPRInfo.h"
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
#include "MacroAssembler.h"

namespace JSC { namespace DFG {

// The BinarySwitch class makes it easy to emit a switch statement over either
// 32-bit integers or pointers, where the switch uses a tree of branches
// rather than a jump table. This makes it particularly useful if the case
// values are too far apart to make a jump table practical, or if there are
// sufficiently few cases that the total cost of log(numCases) branches is
// less than the cost of an indirected jump.
//
// In an effort to simplify the logic of emitting code for each case, this
// uses an iterator style, rather than a functor callback style. This makes
// sense because even the iterator implementation found herein is relatively
// simple, whereas the code it's used from is usually quite complex - one
// example being the trie-of-trees string switch implementation, where the
// code emitted for each case involves recursing to emit code for a sub-trie.
//
// Use this like so:
//
// BinarySwitch switch(valueReg, casesVector, BinarySwitch::Int32);
// while (switch.advance(jit)) {
//     int value = switch.caseValue();
//     unsigned index = switch.caseIndex(); // index into casesVector, above
//     ... // generate code for this case
// }
// switch.fallThrough().link(&jit);

class BinarySwitch {
public:
    enum Type {
        Int32,
        IntPtr
    };
    
    BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type);
    
    unsigned caseIndex() const { return m_cases[m_caseIndex].index; }
72
    int64_t caseValue() const { return m_cases[m_caseIndex].value; }
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
    
    bool advance(MacroAssembler&);
    
    MacroAssembler::JumpList& fallThrough() { return m_fallThrough; }
    
private:
    void build(unsigned start, unsigned end);
    
    GPRReg m_value;
    
    struct Case {
        Case() { }

        Case(int64_t value, unsigned index)
            : value(value)
            , index(index)
        {
        }
        
        bool operator<(const Case& other) const
        {
            return value < other.value;
        }
        
        int64_t value;
        unsigned index;
    };
    
    Vector<Case> m_cases;
    
    enum BranchKind {
        NotEqualToFallThrough,
        NotEqualToPush,
        LessThanToPush,
        Pop,
        ExecuteCase
    };
        
    struct BranchCode {
        BranchCode() { }
        
        BranchCode(BranchKind kind, unsigned index = UINT_MAX)
            : kind(kind)
            , index(index)
        {
        }
        
        BranchKind kind;
        unsigned index;
    };
    
    Vector<BranchCode> m_branches;

    unsigned m_index;
    unsigned m_caseIndex;
    Vector<MacroAssembler::Jump> m_jumpStack;
    
    MacroAssembler::JumpList m_fallThrough;
    
    unsigned m_medianBias;
    
    Type m_type;
};

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)

#endif // DFGBinarySwitch_h