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