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