d9e7a67056bd52d113150c517e8433f62b9b5bf2
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGBinarySwitch.cpp
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 #include "config.h"
27
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGBinarySwitch.h"
31
32 #include "JSCInlines.h"
33
34 namespace JSC { namespace DFG {
35
36 BinarySwitch::BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type type)
37     : m_value(value)
38     , m_index(0)
39     , m_caseIndex(UINT_MAX)
40     , m_medianBias(0)
41     , m_type(type)
42 {
43     if (cases.isEmpty())
44         return;
45     
46     for (unsigned i = 0; i < cases.size(); ++i)
47         m_cases.append(Case(cases[i], i));
48     std::sort(m_cases.begin(), m_cases.end());
49     build(0, m_cases.size());
50 }
51
52 bool BinarySwitch::advance(MacroAssembler& jit)
53 {
54     if (m_cases.isEmpty()) {
55         m_fallThrough.append(jit.jump());
56         return false;
57     }
58     
59     if (m_index == m_branches.size()) {
60         RELEASE_ASSERT(m_jumpStack.isEmpty());
61         return false;
62     }
63     
64     for (;;) {
65         const BranchCode& code = m_branches[m_index++];
66         switch (code.kind) {
67         case NotEqualToFallThrough:
68             switch (m_type) {
69             case Int32:
70                 m_fallThrough.append(jit.branch32(
71                     MacroAssembler::NotEqual, m_value,
72                     MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
73                 break;
74             case IntPtr:
75                 m_fallThrough.append(jit.branchPtr(
76                     MacroAssembler::NotEqual, m_value,
77                     MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
78                 break;
79             }
80             break;
81         case NotEqualToPush:
82             switch (m_type) {
83             case Int32:
84                 m_jumpStack.append(jit.branch32(
85                     MacroAssembler::NotEqual, m_value,
86                     MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
87                 break;
88             case IntPtr:
89                 m_jumpStack.append(jit.branchPtr(
90                     MacroAssembler::NotEqual, m_value,
91                     MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
92                 break;
93             }
94             break;
95         case LessThanToPush:
96             switch (m_type) {
97             case Int32:
98                 m_jumpStack.append(jit.branch32(
99                     MacroAssembler::LessThan, m_value,
100                     MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
101                 break;
102             case IntPtr:
103                 m_jumpStack.append(jit.branchPtr(
104                     MacroAssembler::LessThan, m_value,
105                     MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
106                 break;
107             }
108             break;
109         case Pop:
110             m_jumpStack.takeLast().link(&jit);
111             break;
112         case ExecuteCase:
113             m_caseIndex = code.index;
114             return true;
115         }
116     }
117 }
118
119 void BinarySwitch::build(unsigned start, unsigned end)
120 {
121     unsigned size = end - start;
122     
123     switch (size) {
124     case 0: {
125         RELEASE_ASSERT_NOT_REACHED();
126         break;
127     }
128         
129     case 1: {
130         if (start
131             && m_cases[start - 1].value == m_cases[start].value - 1
132             && start + 1 < m_cases.size()
133             && m_cases[start + 1].value == m_cases[start].value + 1) {
134             m_branches.append(BranchCode(ExecuteCase, start));
135             break;
136         }
137         
138         m_branches.append(BranchCode(NotEqualToFallThrough, start));
139         m_branches.append(BranchCode(ExecuteCase, start));
140         break;
141     }
142         
143     case 2: {
144         if (m_cases[start].value + 1 == m_cases[start + 1].value
145             && start
146             && m_cases[start - 1].value == m_cases[start].value - 1
147             && start + 2 < m_cases.size()
148             && m_cases[start + 2].value == m_cases[start + 1].value + 1) {
149             m_branches.append(BranchCode(NotEqualToPush, start));
150             m_branches.append(BranchCode(ExecuteCase, start));
151             m_branches.append(BranchCode(Pop));
152             m_branches.append(BranchCode(ExecuteCase, start + 1));
153             break;
154         }
155         
156         unsigned firstCase = start;
157         unsigned secondCase = start + 1;
158         if (m_medianBias)
159             std::swap(firstCase, secondCase);
160         m_medianBias ^= 1;
161         
162         m_branches.append(BranchCode(NotEqualToPush, firstCase));
163         m_branches.append(BranchCode(ExecuteCase, firstCase));
164         m_branches.append(BranchCode(Pop));
165         m_branches.append(BranchCode(NotEqualToFallThrough, secondCase));
166         m_branches.append(BranchCode(ExecuteCase, secondCase));
167         break;
168     }
169         
170     default: {
171         unsigned medianIndex = (start + end) / 2;
172         if (!(size & 1)) {
173             // Because end is exclusive, in the even case, this rounds up by
174             // default. Hence median bias sometimes flips to subtracing one
175             // in order to get round-down behavior.
176             medianIndex -= m_medianBias;
177             m_medianBias ^= 1;
178         }
179         
180         RELEASE_ASSERT(medianIndex > start);
181         RELEASE_ASSERT(medianIndex + 1 < end);
182         
183         m_branches.append(BranchCode(LessThanToPush, medianIndex));
184         m_branches.append(BranchCode(NotEqualToPush, medianIndex));
185         m_branches.append(BranchCode(ExecuteCase, medianIndex));
186         
187         m_branches.append(BranchCode(Pop));
188         build(medianIndex + 1, end);
189         
190         m_branches.append(BranchCode(Pop));
191         build(start, medianIndex);
192         break;
193     } }
194 }
195
196 } } // namespace JSC::DFG
197
198 #endif // ENABLE(DFG_JIT)
199