BinarySwitch should be faster on average
[WebKit.git] / Source / JavaScriptCore / jit / BinarySwitch.h
1 /*
2  * Copyright (C) 2013, 2015 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 BinarySwitch_h
27 #define BinarySwitch_h
28
29 #if ENABLE(JIT)
30
31 #include "GPRInfo.h"
32 #include "MacroAssembler.h"
33 #include "WeakRandom.h"
34
35 namespace JSC {
36
37 // The BinarySwitch class makes it easy to emit a switch statement over either
38 // 32-bit integers or pointers, where the switch uses a tree of branches
39 // rather than a jump table. This makes it particularly useful if the case
40 // values are too far apart to make a jump table practical, or if there are
41 // sufficiently few cases that the total cost of log(numCases) branches is
42 // less than the cost of an indirected jump.
43 //
44 // In an effort to simplify the logic of emitting code for each case, this
45 // uses an iterator style, rather than a functor callback style. This makes
46 // sense because even the iterator implementation found herein is relatively
47 // simple, whereas the code it's used from is usually quite complex - one
48 // example being the trie-of-trees string switch implementation, where the
49 // code emitted for each case involves recursing to emit code for a sub-trie.
50 //
51 // Use this like so:
52 //
53 // BinarySwitch switch(valueReg, casesVector, BinarySwitch::Int32);
54 // while (switch.advance(jit)) {
55 //     int value = switch.caseValue();
56 //     unsigned index = switch.caseIndex(); // index into casesVector, above
57 //     ... // generate code for this case
58 //     ... = jit.jump(); // you have to jump out yourself; falling through causes undefined behavior
59 // }
60 // switch.fallThrough().link(&jit);
61
62 class BinarySwitch {
63 public:
64     enum Type {
65         Int32,
66         IntPtr
67     };
68     
69     BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type);
70     ~BinarySwitch();
71     
72     unsigned caseIndex() const { return m_cases[m_caseIndex].index; }
73     int64_t caseValue() const { return m_cases[m_caseIndex].value; }
74     
75     bool advance(MacroAssembler&);
76     
77     MacroAssembler::JumpList& fallThrough() { return m_fallThrough; }
78     
79 private:
80     void build(unsigned start, bool hardStart, unsigned end);
81     
82     GPRReg m_value;
83     
84     struct Case {
85         Case() { }
86
87         Case(int64_t value, unsigned index)
88             : value(value)
89             , index(index)
90         {
91         }
92         
93         bool operator<(const Case& other) const
94         {
95             return value < other.value;
96         }
97         
98         int64_t value;
99         unsigned index;
100     };
101     
102     Vector<Case> m_cases;
103     
104     enum BranchKind {
105         NotEqualToFallThrough,
106         NotEqualToPush,
107         LessThanToPush,
108         Pop,
109         ExecuteCase
110     };
111         
112     struct BranchCode {
113         BranchCode() { }
114         
115         BranchCode(BranchKind kind, unsigned index = UINT_MAX)
116             : kind(kind)
117             , index(index)
118         {
119         }
120         
121         BranchKind kind;
122         unsigned index;
123     };
124     
125     WeakRandom m_weakRandom;
126     
127     Vector<BranchCode> m_branches;
128
129     unsigned m_index;
130     unsigned m_caseIndex;
131     Vector<MacroAssembler::Jump> m_jumpStack;
132     
133     MacroAssembler::JumpList m_fallThrough;
134     
135     Type m_type;
136 };
137
138 } // namespace JSC
139
140 #endif // ENABLE(JIT)
141
142 #endif // BinarySwitch_h
143