dfg/DFGBinarySwitch.h

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