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
33
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
72
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
143
144
145
146
147
|
/*
* Copyright (C) 2013, 2015 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 BinarySwitch_h
#define BinarySwitch_h
#if ENABLE(JIT)
#include "GPRInfo.h"
#include "MacroAssembler.h"
#include <wtf/WeakRandom.h>
namespace JSC {
// 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
// ... = jit.jump(); // you have to jump out yourself; falling through causes undefined behavior
// }
// switch.fallThrough().link(&jit);
class BinarySwitch {
public:
enum Type {
Int32,
IntPtr
};
BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type);
~BinarySwitch();
unsigned caseIndex() const { return m_cases[m_caseIndex].index; }
int64_t caseValue() const { return m_cases[m_caseIndex].value; }
bool advance(MacroAssembler&);
MacroAssembler::JumpList& fallThrough() { return m_fallThrough; }
private:
void build(unsigned start, bool hardStart, 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;
}
void dump(PrintStream& out) const;
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)
{
}
void dump(PrintStream& out) const;
BranchKind kind;
unsigned index;
};
WeakRandom m_weakRandom;
Vector<BranchCode> m_branches;
unsigned m_index;
unsigned m_caseIndex;
Vector<MacroAssembler::Jump> m_jumpStack;
MacroAssembler::JumpList m_fallThrough;
Type m_type;
};
} // namespace JSC
#endif // ENABLE(JIT)
#endif // BinarySwitch_h
|
