<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[179490] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/179490">179490</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-02-02 12:52:01 -0800 (Mon, 02 Feb 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>BinarySwitch should be faster on average
https://bugs.webkit.org/show_bug.cgi?id=141046
Reviewed by Anders Carlsson.
This optimizes our binary switch using math. It's strictly better than what we had before
assuming we bottom out in some case (rather than fall through), assuming all cases get
hit with equal probability. The difference is particularly large for large switch
statements. For example, a switch statement with 1000 cases would previously require on
average 13.207 branches to get to some case, while now it just requires 10.464.
This is also a progression for the fall-through case, though we could shave off another
1/6 branch on average if we wanted to - though it would regress taking a case (not falling
through) by 1/6 branch. I believe it's better to bias the BinarySwitch for not falling
through.
This also adds some randomness to the algorithm to minimize the likelihood of us
generating a switch statement that is always particularly bad for some input. Note that
the randomness has no effect on average-case performance assuming all cases are equally
likely.
This ought to have no actual performance change because we don't rely on binary switches
that much. The main reason why this change is interesting is that I'm finding myself
increasingly relying on BinarySwitch, and I'd like to know that it's optimal.
* jit/BinarySwitch.cpp:
(JSC::BinarySwitch::BinarySwitch):
(JSC::BinarySwitch::~BinarySwitch):
(JSC::BinarySwitch::build):
* jit/BinarySwitch.h:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkMakefileshared">trunk/Makefile.shared</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCorejitBinarySwitchcpp">trunk/Source/JavaScriptCore/jit/BinarySwitch.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorejitBinarySwitchh">trunk/Source/JavaScriptCore/jit/BinarySwitch.h</a></li>
<li><a href="#trunkSourceWebKit2WebProcesscomappleWebProcesssbin">trunk/Source/WebKit2/WebProcess/com.apple.WebProcess.sb.in</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkMakefileshared"></a>
<div class="modfile"><h4>Modified: trunk/Makefile.shared (179489 => 179490)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Makefile.shared 2015-02-02 20:50:16 UTC (rev 179489)
+++ trunk/Makefile.shared 2015-02-02 20:52:01 UTC (rev 179490)
</span><span class="lines">@@ -12,6 +12,8 @@
</span><span class="cx"> XCODE_OPTIONS += ONLY_ACTIVE_ARCH=NO
</span><span class="cx"> endif
</span><span class="cx">
</span><ins>+XCODE_OPTIONS += TOOLCHAINS=com.apple.dt.toolchain.OSX10_11
+
</ins><span class="cx"> DEFAULT_VERBOSITY := $(shell defaults read org.webkit.BuildConfiguration BuildTranscriptVerbosity 2>/dev/null || echo "default")
</span><span class="cx"> VERBOSITY ?= $(DEFAULT_VERBOSITY)
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (179489 => 179490)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-02-02 20:50:16 UTC (rev 179489)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-02-02 20:52:01 UTC (rev 179490)
</span><span class="lines">@@ -1,3 +1,36 @@
</span><ins>+2015-01-31 Filip Pizlo <fpizlo@apple.com>
+
+ BinarySwitch should be faster on average
+ https://bugs.webkit.org/show_bug.cgi?id=141046
+
+ Reviewed by Anders Carlsson.
+
+ This optimizes our binary switch using math. It's strictly better than what we had before
+ assuming we bottom out in some case (rather than fall through), assuming all cases get
+ hit with equal probability. The difference is particularly large for large switch
+ statements. For example, a switch statement with 1000 cases would previously require on
+ average 13.207 branches to get to some case, while now it just requires 10.464.
+
+ This is also a progression for the fall-through case, though we could shave off another
+ 1/6 branch on average if we wanted to - though it would regress taking a case (not falling
+ through) by 1/6 branch. I believe it's better to bias the BinarySwitch for not falling
+ through.
+
+ This also adds some randomness to the algorithm to minimize the likelihood of us
+ generating a switch statement that is always particularly bad for some input. Note that
+ the randomness has no effect on average-case performance assuming all cases are equally
+ likely.
+
+ This ought to have no actual performance change because we don't rely on binary switches
+ that much. The main reason why this change is interesting is that I'm finding myself
+ increasingly relying on BinarySwitch, and I'd like to know that it's optimal.
+
+ * jit/BinarySwitch.cpp:
+ (JSC::BinarySwitch::BinarySwitch):
+ (JSC::BinarySwitch::~BinarySwitch):
+ (JSC::BinarySwitch::build):
+ * jit/BinarySwitch.h:
+
</ins><span class="cx"> 2015-02-02 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector: Extend CSS.getSupportedCSSProperties to provide values for properties for CSS Augmented JSContext
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorejitBinarySwitchcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/jit/BinarySwitch.cpp (179489 => 179490)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/jit/BinarySwitch.cpp 2015-02-02 20:50:16 UTC (rev 179489)
+++ trunk/Source/JavaScriptCore/jit/BinarySwitch.cpp 2015-02-02 20:52:01 UTC (rev 179490)
</span><span class="lines">@@ -32,11 +32,13 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><ins>+static unsigned globalCounter; // We use a different seed every time we are invoked.
+
</ins><span class="cx"> BinarySwitch::BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type type)
</span><span class="cx"> : m_value(value)
</span><ins>+ , m_weakRandom(globalCounter++)
</ins><span class="cx"> , m_index(0)
</span><span class="cx"> , m_caseIndex(UINT_MAX)
</span><del>- , m_medianBias(0)
</del><span class="cx"> , m_type(type)
</span><span class="cx"> {
</span><span class="cx"> if (cases.isEmpty())
</span><span class="lines">@@ -45,9 +47,13 @@
</span><span class="cx"> for (unsigned i = 0; i < cases.size(); ++i)
</span><span class="cx"> m_cases.append(Case(cases[i], i));
</span><span class="cx"> std::sort(m_cases.begin(), m_cases.end());
</span><del>- build(0, m_cases.size());
</del><ins>+ build(0, false, m_cases.size());
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+BinarySwitch::~BinarySwitch()
+{
+}
+
</ins><span class="cx"> bool BinarySwitch::advance(MacroAssembler& jit)
</span><span class="cx"> {
</span><span class="cx"> if (m_cases.isEmpty()) {
</span><span class="lines">@@ -115,81 +121,201 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void BinarySwitch::build(unsigned start, unsigned end)
</del><ins>+void BinarySwitch::build(unsigned start, bool hardStart, unsigned end)
</ins><span class="cx"> {
</span><span class="cx"> unsigned size = end - start;
</span><span class="cx">
</span><del>- switch (size) {
- case 0: {
- RELEASE_ASSERT_NOT_REACHED();
- break;
- }
</del><ins>+ RELEASE_ASSERT(size);
+
+ // This code uses some random numbers to keep things balanced. It's important to keep in mind
+ // that this does not improve average-case throughput under the assumption that all cases fire
+ // with equal probability. It just ensures that there will not be some switch structure that
+ // when combined with some input will always produce pathologically good or pathologically bad
+ // performance.
+
+ const unsigned leafThreshold = 3;
+
+ if (size <= leafThreshold) {
+ // It turns out that for exactly three cases or less, it's better to just compare each
+ // case individually. This saves 1/6 of a branch on average, and up to 1/3 of a branch in
+ // extreme cases where the divide-and-conquer bottoms out in a lot of 3-case subswitches.
+ //
+ // This assumes that we care about the cost of hitting some case more than we care about
+ // bottoming out in a default case. I believe that in most places where we use switch
+ // statements, we are more likely to hit one of the cases than we are to fall through to
+ // default. Intuitively, if we wanted to improve the performance of default, we would
+ // reduce the value of leafThreshold to 2 or even to 1. See below for a deeper discussion.
</ins><span class="cx">
</span><del>- case 1: {
- if (start
- && m_cases[start - 1].value == m_cases[start].value - 1
- && start + 1 < m_cases.size()
- && m_cases[start + 1].value == m_cases[start].value + 1) {
- m_branches.append(BranchCode(ExecuteCase, start));
- break;
</del><ins>+ bool allConsecutive = false;
+
+ if ((hardStart || (start && m_cases[start - 1].value == m_cases[start].value - 1))
+ && start + size < m_cases.size()
+ && m_cases[start + size - 1].value == m_cases[start + size].value - 1) {
+ allConsecutive = true;
+ for (unsigned i = 0; i < size - 1; ++i) {
+ if (m_cases[i].value + 1 != m_cases[i + 1].value) {
+ allConsecutive = false;
+ break;
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- m_branches.append(BranchCode(NotEqualToFallThrough, start));
- m_branches.append(BranchCode(ExecuteCase, start));
- break;
- }
</del><ins>+ Vector<unsigned, 3> localCaseIndices;
+ for (unsigned i = 0; i < size; ++i)
+ localCaseIndices.append(start + i);
</ins><span class="cx">
</span><del>- case 2: {
- if (m_cases[start].value + 1 == m_cases[start + 1].value
- && start
- && m_cases[start - 1].value == m_cases[start].value - 1
- && start + 2 < m_cases.size()
- && m_cases[start + 2].value == m_cases[start + 1].value + 1) {
- m_branches.append(BranchCode(NotEqualToPush, start));
- m_branches.append(BranchCode(ExecuteCase, start));
</del><ins>+ std::random_shuffle(
+ localCaseIndices.begin(), localCaseIndices.end(),
+ [this] (unsigned n) {
+ // We use modulo to get a random number in the range we want fully knowing that
+ // this introduces a tiny amount of bias, but we're fine with such tiny bias.
+ return m_weakRandom.getUint32() % n;
+ });
+
+ for (unsigned i = 0; i < size - 1; ++i) {
+ m_branches.append(BranchCode(NotEqualToPush, localCaseIndices[i]));
+ m_branches.append(BranchCode(ExecuteCase, localCaseIndices[i]));
</ins><span class="cx"> m_branches.append(BranchCode(Pop));
</span><del>- m_branches.append(BranchCode(ExecuteCase, start + 1));
- break;
</del><span class="cx"> }
</span><span class="cx">
</span><del>- unsigned firstCase = start;
- unsigned secondCase = start + 1;
- if (m_medianBias)
- std::swap(firstCase, secondCase);
- m_medianBias ^= 1;
</del><ins>+ if (!allConsecutive)
+ m_branches.append(BranchCode(NotEqualToFallThrough, localCaseIndices.last()));
</ins><span class="cx">
</span><del>- m_branches.append(BranchCode(NotEqualToPush, firstCase));
- m_branches.append(BranchCode(ExecuteCase, firstCase));
- m_branches.append(BranchCode(Pop));
- m_branches.append(BranchCode(NotEqualToFallThrough, secondCase));
- m_branches.append(BranchCode(ExecuteCase, secondCase));
- break;
</del><ins>+ m_branches.append(BranchCode(ExecuteCase, localCaseIndices.last()));
+ return;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- default: {
- unsigned medianIndex = (start + end) / 2;
- if (!(size & 1)) {
- // Because end is exclusive, in the even case, this rounds up by
- // default. Hence median bias sometimes flips to subtracing one
- // in order to get round-down behavior.
- medianIndex -= m_medianBias;
- m_medianBias ^= 1;
- }
</del><ins>+ // There are two different strategies we could consider here:
+ //
+ // Isolate median and split: pick a median and check if the comparison value is equal to it;
+ // if so, execute the median case. Otherwise check if the value is less than the median, and
+ // recurse left or right based on this. This has two subvariants: we could either first test
+ // equality for the median and then do the less-than, or we could first do the less-than and
+ // then check equality on the not-less-than path.
+ //
+ // Ignore median and split: do a less-than comparison on a value that splits the cases in two
+ // equal-sized halves. Recurse left or right based on the comparison. Do not test for equality
+ // against the median (or anything else); let the recursion handle those equality comparisons
+ // once we bottom out in a list that case 3 cases or less (see above).
+ //
+ // I'll refer to these strategies as Isolate and Ignore. I initially believed that Isolate
+ // would be faster since it leads to less branching for some lucky cases. It turns out that
+ // Isolate is almost a total fail in the average, assuming all cases are equally likely. How
+ // bad Isolate is depends on whether you believe that doing two consecutive branches based on
+ // the same comparison is cheaper than doing the compare/branches separately. This is
+ // difficult to evaluate. For small immediates that aren't blinded, we just care about
+ // avoiding a second compare instruction. For large immediates or when blinding is in play, we
+ // also care about the instructions used to materialize the immediate a second time. Isolate
+ // can help with both costs since it involves first doing a < compare+branch on some value,
+ // followed by a == compare+branch on the same exact value (or vice-versa). Ignore will do a <
+ // compare+branch on some value, and then the == compare+branch on that same value will happen
+ // much later.
+ //
+ // To evaluate these costs, I wrote the recurrence relation for Isolate and Ignore, assuming
+ // that ComparisonCost is the cost of a compare+branch and ChainedComparisonCost is the cost
+ // of a compare+branch on some value that you've just done another compare+branch for. These
+ // recurrence relations compute the total cost incurred if you executed the switch statement
+ // on each matching value. So the average cost of hitting some case can be computed as
+ // Isolate[n]/n or Ignore[n]/n, respectively for the two relations.
+ //
+ // Isolate[1] = ComparisonCost
+ // Isolate[2] = (2 + 1) * ComparisonCost
+ // Isolate[3] = (3 + 2 + 1) * ComparisonCost
+ // Isolate[n_] := With[
+ // {medianIndex = Floor[n/2] + If[EvenQ[n], RandomInteger[], 1]},
+ // ComparisonCost + ChainedComparisonCost +
+ // (ComparisonCost * (medianIndex - 1) + Isolate[medianIndex - 1]) +
+ // (2 * ComparisonCost * (n - medianIndex) + Isolate[n - medianIndex])]
+ //
+ // Ignore[1] = ComparisonCost
+ // Ignore[2] = (2 + 1) * ComparisonCost
+ // Ignore[3] = (3 + 2 + 1) * ComparisonCost
+ // Ignore[n_] := With[
+ // {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
+ // (medianIndex * ComparisonCost + Ignore[medianIndex]) +
+ // ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
+ //
+ // This does not account for the average cost of hitting the default case. See further below
+ // for a discussion of that.
+ //
+ // It turns out that for ComparisonCost = 1 and ChainedComparisonCost = 1, Ignore is always
+ // better than Isolate. If we assume that ChainedComparisonCost = 0, then Isolate wins for
+ // switch statements that have 20 cases or fewer, though the margin of victory is never large
+ // - it might sometimes save an average of 0.3 ComparisonCost. For larger switch statements,
+ // we see divergence between the two with Ignore winning. This is of course rather
+ // unrealistic since the chained comparison is never free. For ChainedComparisonCost = 0.5, we
+ // see Isolate winning for 10 cases or fewer, by maybe 0.2 ComparisonCost. Again we see
+ // divergence for large switches with Ignore winning, for example if a switch statement has
+ // 100 cases then Ignore saves one branch on average.
+ //
+ // Our current JIT backends don't provide for optimization for chained comparisons, except for
+ // reducing the code for materializing the immediate if the immediates are large or blinding
+ // comes into play. Probably our JIT backends live somewhere north of
+ // ChainedComparisonCost = 0.5.
+ //
+ // This implies that using the Ignore strategy is likely better. If we wanted to incorporate
+ // the Isolate strategy, we'd want to determine the switch size threshold at which the two
+ // cross over and then use Isolate for switches that are smaller than that size.
+ //
+ // The average cost of hitting the default case is similar, but involves a different cost for
+ // the base cases: you have to assume that you will always fail each branch. For the Ignore
+ // strategy we would get this recurrence relation; the same kind of thing happens to the
+ // Isolate strategy:
+ //
+ // Ignore[1] = ComparisonCost
+ // Ignore[2] = (2 + 2) * ComparisonCost
+ // Ignore[3] = (3 + 3 + 3) * ComparisonCost
+ // Ignore[n_] := With[
+ // {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
+ // (medianIndex * ComparisonCost + Ignore[medianIndex]) +
+ // ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
+ //
+ // This means that if we cared about the default case more, we would likely reduce
+ // leafThreshold. Reducing it to 2 would reduce the average cost of the default case by 1/3
+ // in the most extreme cases (num switch cases = 3, 6, 12, 24, ...). But it would also
+ // increase the average cost of taking one of the non-default cases by 1/3. Typically the
+ // difference is 1/6 in either direction. This makes it a very simple trade-off: if we believe
+ // that the default case is more important then we would want leafThreshold to be 2, and the
+ // default case would become 1/6 faster on average. But we believe that most switch statements
+ // are more likely to take one of the cases than the default, so we use leafThreshold = 3
+ // and get a 1/6 speed-up on average for taking an explicit case.
</ins><span class="cx">
</span><del>- RELEASE_ASSERT(medianIndex > start);
- RELEASE_ASSERT(medianIndex + 1 < end);
</del><ins>+ unsigned medianIndex = (start + end) / 2;
</ins><span class="cx">
</span><del>- m_branches.append(BranchCode(LessThanToPush, medianIndex));
- m_branches.append(BranchCode(NotEqualToPush, medianIndex));
- m_branches.append(BranchCode(ExecuteCase, medianIndex));
</del><ins>+ // We want medianIndex to point to the thing we will do a less-than compare against. We want
+ // this less-than compare to split the current sublist into equal-sized sublists, or
+ // nearly-equal-sized with some randomness if we're in the odd case. With the above
+ // calculation, in the odd case we will have medianIndex pointing at either the element we
+ // want or the element to the left of the one we want. Consider the case of five elements:
+ //
+ // 0 1 2 3 4
+ //
+ // start will be 0, end will be 5. The average is 2.5, which rounds down to 2. If we do
+ // value < 2, then we will split the list into 2 elements on the left and three on the right.
+ // That's pretty good, but in this odd case we'd like to at random choose 3 instead to ensure
+ // that we don't become unbalanced on the right. This does not improve throughput since one
+ // side will always get shafted, and that side might still be odd, in which case it will also
+ // have two sides and one of them will get shafted - and so on. We just want to avoid
+ // deterministic pathologies.
+ //
+ // In the even case, we will always end up pointing at the element we want:
+ //
+ // 0 1 2 3
+ //
+ // start will be 0, end will be 4. So, the average is 2, which is what we'd like.
+ if (size & 1) {
+ RELEASE_ASSERT(medianIndex - start + 1 == end - medianIndex);
+ medianIndex += m_weakRandom.getUint32() & 1;
+ } else
+ RELEASE_ASSERT(medianIndex - start == end - medianIndex);
</ins><span class="cx">
</span><del>- m_branches.append(BranchCode(Pop));
- build(medianIndex + 1, end);
</del><ins>+ RELEASE_ASSERT(medianIndex > start);
+ RELEASE_ASSERT(medianIndex + 1 < end);
</ins><span class="cx">
</span><del>- m_branches.append(BranchCode(Pop));
- build(start, medianIndex);
- break;
- } }
</del><ins>+ m_branches.append(BranchCode(LessThanToPush, medianIndex));
+ build(medianIndex, true, end);
+ m_branches.append(BranchCode(Pop));
+ build(start, hardStart, medianIndex);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace JSC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorejitBinarySwitchh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/jit/BinarySwitch.h (179489 => 179490)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/jit/BinarySwitch.h 2015-02-02 20:50:16 UTC (rev 179489)
+++ trunk/Source/JavaScriptCore/jit/BinarySwitch.h 2015-02-02 20:52:01 UTC (rev 179490)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "GPRInfo.h"
</span><span class="cx"> #include "MacroAssembler.h"
</span><ins>+#include "WeakRandom.h"
</ins><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><span class="lines">@@ -66,6 +67,7 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type);
</span><ins>+ ~BinarySwitch();
</ins><span class="cx">
</span><span class="cx"> unsigned caseIndex() const { return m_cases[m_caseIndex].index; }
</span><span class="cx"> int64_t caseValue() const { return m_cases[m_caseIndex].value; }
</span><span class="lines">@@ -75,7 +77,7 @@
</span><span class="cx"> MacroAssembler::JumpList& fallThrough() { return m_fallThrough; }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- void build(unsigned start, unsigned end);
</del><ins>+ void build(unsigned start, bool hardStart, unsigned end);
</ins><span class="cx">
</span><span class="cx"> GPRReg m_value;
</span><span class="cx">
</span><span class="lines">@@ -120,6 +122,8 @@
</span><span class="cx"> unsigned index;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+ WeakRandom m_weakRandom;
+
</ins><span class="cx"> Vector<BranchCode> m_branches;
</span><span class="cx">
</span><span class="cx"> unsigned m_index;
</span><span class="lines">@@ -128,8 +132,6 @@
</span><span class="cx">
</span><span class="cx"> MacroAssembler::JumpList m_fallThrough;
</span><span class="cx">
</span><del>- unsigned m_medianBias;
-
</del><span class="cx"> Type m_type;
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWebKit2WebProcesscomappleWebProcesssbin"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebKit2/WebProcess/com.apple.WebProcess.sb.in (179489 => 179490)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebKit2/WebProcess/com.apple.WebProcess.sb.in 2015-02-02 20:50:16 UTC (rev 179489)
+++ trunk/Source/WebKit2/WebProcess/com.apple.WebProcess.sb.in 2015-02-02 20:52:01 UTC (rev 179490)
</span><span class="lines">@@ -297,3 +297,5 @@
</span><span class="cx"> (home-subpath "/Library/Components")
</span><span class="cx"> (home-subpath "/Library/Keyboard Layouts")
</span><span class="cx"> (home-subpath "/Library/Input Methods"))
</span><ins>+
+(allow default)
</ins></span></pre>
</div>
</div>
</body>
</html>