f6a4967bcef25ae0b10c3826da4f4f62571ab08c
[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
34 namespace JSC {
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 //     ... = jit.jump(); // you have to jump out yourself; falling through causes undefined behavior
58 // }
59 // switch.fallThrough().link(&jit);
60
61 class BinarySwitch {
62 public:
63     enum Type {
64         Int32,
65         IntPtr
66     };
67     
68     BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type);
69     
70     unsigned caseIndex() const { return m_cases[m_caseIndex].index; }
71     int64_t caseValue() const { return m_cases[m_caseIndex].value; }
72     
73     bool advance(MacroAssembler&);
74     
75     MacroAssembler::JumpList& fallThrough() { return m_fallThrough; }
76     
77 private:
78     void build(unsigned start, unsigned end);
79     
80     GPRReg m_value;
81     
82     struct Case {
83         Case() { }
84
85         Case(int64_t value, unsigned index)
86             : value(value)
87             , index(index)
88         {
89         }
90         
91         bool operator<(const Case& other) const
92         {
93             return value < other.value;
94         }
95         
96         int64_t value;
97         unsigned index;
98     };
99     
100     Vector<Case> m_cases;
101     
102     enum BranchKind {
103         NotEqualToFallThrough,
104         NotEqualToPush,
105         LessThanToPush,
106         Pop,
107         ExecuteCase
108     };
109         
110     struct BranchCode {
111         BranchCode() { }
112         
113         BranchCode(BranchKind kind, unsigned index = UINT_MAX)
114             : kind(kind)
115             , index(index)
116         {
117         }
118         
119         BranchKind kind;
120         unsigned index;
121     };
122     
123     Vector<BranchCode> m_branches;
124
125     unsigned m_index;
126     unsigned m_caseIndex;
127     Vector<MacroAssembler::Jump> m_jumpStack;
128     
129     MacroAssembler::JumpList m_fallThrough;
130     
131     unsigned m_medianBias;
132     
133     Type m_type;
134 };
135
136 } // namespace JSC
137
138 #endif // ENABLE(JIT)
139
140 #endif // BinarySwitch_h
141