1/* 2 * Copyright (C) 2013 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef DFGBinarySwitch_h 27#define DFGBinarySwitch_h 28 29#if ENABLE(DFG_JIT) 30 31#include "GPRInfo.h" 32#include "MacroAssembler.h" 33 34namespace JSC { namespace DFG { 35 36// The BinarySwitch class makes it easy to emit a switch statement over either 37// 32-bit integers or pointers, where the switch uses a tree of branches 38// rather than a jump table. This makes it particularly useful if the case 39// values are too far apart to make a jump table practical, or if there are 40// sufficiently few cases that the total cost of log(numCases) branches is 41// less than the cost of an indirected jump. 42// 43// In an effort to simplify the logic of emitting code for each case, this 44// uses an iterator style, rather than a functor callback style. This makes 45// sense because even the iterator implementation found herein is relatively 46// simple, whereas the code it's used from is usually quite complex - one 47// example being the trie-of-trees string switch implementation, where the 48// code emitted for each case involves recursing to emit code for a sub-trie. 49// 50// Use this like so: 51// 52// BinarySwitch switch(valueReg, casesVector, BinarySwitch::Int32); 53// while (switch.advance(jit)) { 54// int value = switch.caseValue(); 55// unsigned index = switch.caseIndex(); // index into casesVector, above 56// ... // generate code for this case 57// } 58// switch.fallThrough().link(&jit); 59 60class BinarySwitch { 61public: 62 enum Type { 63 Int32, 64 IntPtr 65 }; 66 67 BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type); 68 69 unsigned caseIndex() const { return m_cases[m_caseIndex].index; } 70 int64_t caseValue() const { return m_cases[m_caseIndex].value; } 71 72 bool advance(MacroAssembler&); 73 74 MacroAssembler::JumpList& fallThrough() { return m_fallThrough; } 75 76private: 77 void build(unsigned start, unsigned end); 78 79 GPRReg m_value; 80 81 struct Case { 82 Case() { } 83 84 Case(int64_t value, unsigned index) 85 : value(value) 86 , index(index) 87 { 88 } 89 90 bool operator<(const Case& other) const 91 { 92 return value < other.value; 93 } 94 95 int64_t value; 96 unsigned index; 97 }; 98 99 Vector<Case> m_cases; 100 101 enum BranchKind { 102 NotEqualToFallThrough, 103 NotEqualToPush, 104 LessThanToPush, 105 Pop, 106 ExecuteCase 107 }; 108 109 struct BranchCode { 110 BranchCode() { } 111 112 BranchCode(BranchKind kind, unsigned index = UINT_MAX) 113 : kind(kind) 114 , index(index) 115 { 116 } 117 118 BranchKind kind; 119 unsigned index; 120 }; 121 122 Vector<BranchCode> m_branches; 123 124 unsigned m_index; 125 unsigned m_caseIndex; 126 Vector<MacroAssembler::Jump> m_jumpStack; 127 128 MacroAssembler::JumpList m_fallThrough; 129 130 unsigned m_medianBias; 131 132 Type m_type; 133}; 134 135} } // namespace JSC::DFG 136 137#endif // ENABLE(DFG_JIT) 138 139#endif // DFGBinarySwitch_h 140 141