<!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>[195503] trunk/Source/JavaScriptCore</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/195503">195503</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-01-22 19:24:42 -0800 (Fri, 22 Jan 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3 should strength-reduce division by a constant
https://bugs.webkit.org/show_bug.cgi?id=153386
Reviewed by Benjamin Poulain.
You can turn a 32-bit division by a constant into a 64-bit multiplication by a constant
plus some shifts. A book called "Hacker's Delight" has a bunch of math about this. The
hard part is finding the constant by which to multiply, and the amount by which to shift.
The book tells you some theroems, but you still have to turn that into code by thinking
deep thoughts. Luckily I was able to avoid that because it turns out that LLVM already
has code for this. It's called APInt::magic(), where APInt is their class for reasoning
about integers.
The code has a compatible license to ours and we have already in the past taken code from
LLVM. So, that's what this patch does. The LLVM code is localized in
B3ComputeDivisionMagic.h. Then reduceStrength() uses that to construct the multiply+shift
sequence.
This is an enormous speed-up on AsmBench-0.9/bigfib.cpp.js. It makes us as fast on that
test as LLVM. It reduces our deficit on AsmBench to 1.5%. Previously it was 4.5%.
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3ComputeDivisionMagic.h: Added.
(JSC::B3::computeDivisionMagic):
* b3/B3ReduceStrength.cpp:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp">trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3B3ComputeDivisionMagich">trunk/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (195502 => 195503)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-01-23 02:10:17 UTC (rev 195502)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-01-23 03:24:42 UTC (rev 195503)
</span><span class="lines">@@ -1,3 +1,31 @@
</span><ins>+2016-01-22 Filip Pizlo <fpizlo@apple.com>
+
+ B3 should strength-reduce division by a constant
+ https://bugs.webkit.org/show_bug.cgi?id=153386
+
+ Reviewed by Benjamin Poulain.
+
+ You can turn a 32-bit division by a constant into a 64-bit multiplication by a constant
+ plus some shifts. A book called "Hacker's Delight" has a bunch of math about this. The
+ hard part is finding the constant by which to multiply, and the amount by which to shift.
+ The book tells you some theroems, but you still have to turn that into code by thinking
+ deep thoughts. Luckily I was able to avoid that because it turns out that LLVM already
+ has code for this. It's called APInt::magic(), where APInt is their class for reasoning
+ about integers.
+
+ The code has a compatible license to ours and we have already in the past taken code from
+ LLVM. So, that's what this patch does. The LLVM code is localized in
+ B3ComputeDivisionMagic.h. Then reduceStrength() uses that to construct the multiply+shift
+ sequence.
+
+ This is an enormous speed-up on AsmBench-0.9/bigfib.cpp.js. It makes us as fast on that
+ test as LLVM. It reduces our deficit on AsmBench to 1.5%. Previously it was 4.5%.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3ComputeDivisionMagic.h: Added.
+ (JSC::B3::computeDivisionMagic):
+ * b3/B3ReduceStrength.cpp:
+
</ins><span class="cx"> 2016-01-22 Saam barati <sbarati@apple.com>
</span><span class="cx">
</span><span class="cx"> genericUnwind might overflow the instructions() vector when catching an FTL exception
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (195502 => 195503)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-01-23 02:10:17 UTC (rev 195502)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-01-23 03:24:42 UTC (rev 195503)
</span><span class="lines">@@ -492,6 +492,7 @@
</span><span class="cx"> 0F8335B71639C1E6001443B5 /* ArrayAllocationProfile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */; };
</span><span class="cx"> 0F8335B81639C1EA001443B5 /* ArrayAllocationProfile.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */; };
</span><ins>+ 0F86AE201C5311C5006BE8EC /* B3ComputeDivisionMagic.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */; };
</ins><span class="cx"> 0F885E111849A3BE00F1E3FA /* BytecodeUseDef.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F893BDB1936E23C001211F4 /* DFGStructureAbstractValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */; };
</span><span class="cx"> 0F898F311B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */; };
</span><span class="lines">@@ -2674,6 +2675,7 @@
</span><span class="cx"> 0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ArrayAllocationProfile.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ArrayAllocationProfile.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBranchDirection.h; path = dfg/DFGBranchDirection.h; sourceTree = "<group>"; };
</span><ins>+ 0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ComputeDivisionMagic.h; path = b3/B3ComputeDivisionMagic.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BytecodeUseDef.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStructureAbstractValue.cpp; path = dfg/DFGStructureAbstractValue.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGIntegerRangeOptimizationPhase.cpp; path = dfg/DFGIntegerRangeOptimizationPhase.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4771,6 +4773,7 @@
</span><span class="cx"> 0FEC84C21BDACDAC0080FF74 /* B3Commutativity.h */,
</span><span class="cx"> 0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */,
</span><span class="cx"> 0F338E001BF0276C0013C88F /* B3Compilation.h */,
</span><ins>+ 0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */,
</ins><span class="cx"> 0FEC84C31BDACDAC0080FF74 /* B3Const32Value.cpp */,
</span><span class="cx"> 0FEC84C41BDACDAC0080FF74 /* B3Const32Value.h */,
</span><span class="cx"> 0FEC84C51BDACDAC0080FF74 /* B3Const64Value.cpp */,
</span><span class="lines">@@ -7989,6 +7992,7 @@
</span><span class="cx"> BC18C4560E16F5CD00B34460 /* Protect.h in Headers */,
</span><span class="cx"> 1474C33B16AA2D950062F01D /* PrototypeMap.h in Headers */,
</span><span class="cx"> 0F5780A218FE1E98001E72D9 /* PureNaN.h in Headers */,
</span><ins>+ 0F86AE201C5311C5006BE8EC /* B3ComputeDivisionMagic.h in Headers */,
</ins><span class="cx"> 0F15CD231BA5F9860031FFD3 /* PutByIdFlags.h in Headers */,
</span><span class="cx"> 0F9332A414CA7DD90085F3C6 /* PutByIdStatus.h in Headers */,
</span><span class="cx"> 0F93275F1C21EF7F00CF6564 /* JSObjectInlines.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ComputeDivisionMagich"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h (0 => 195503)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h 2016-01-23 03:24:42 UTC (rev 195503)
</span><span class="lines">@@ -0,0 +1,161 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * This contains code taken from LLVM's APInt class. That code implements finding the magic
+ * numbers for strength-reducing division. The LLVM code on which this code is based was
+ * implemented using "Hacker's Delight", Henry S. Warren, Jr., chapter 10.
+ *
+ * ==============================================================================
+ * LLVM Release License
+ * ==============================================================================
+ * University of Illinois/NCSA
+ * Open Source License
+ *
+ * Copyright (c) 2003-2014 University of Illinois at Urbana-Champaign.
+ * All rights reserved.
+ *
+ * Developed by:
+ *
+ * LLVM Team
+ *
+ * University of Illinois at Urbana-Champaign
+ *
+ * http://llvm.org
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy of
+ * this software and associated documentation files (the "Software"), to deal with
+ * the Software without restriction, including without limitation the rights to
+ * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+ * of the Software, and to permit persons to whom the Software is furnished to do
+ * so, subject to the following conditions:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimers.
+ *
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimers in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the names of the LLVM Team, University of Illinois at
+ * Urbana-Champaign, nor the names of its contributors may be used to
+ * endorse or promote products derived from this Software without specific
+ * prior written permission.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+ * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
+ * SOFTWARE.
+ */
+
+#ifndef B3ComputeDivisionMagic_h
+#define B3ComputeDivisionMagic_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+template<typename T>
+struct DivisionMagic {
+ T magicMultiplier;
+ unsigned shift;
+};
+
+// This contains code taken from LLVM's APInt::magic(). It's modestly adapted to our style, but
+// not completely, to make it easier to apply their changes in the future.
+template<typename T>
+DivisionMagic<T> computeDivisionMagic(T divisor)
+{
+ T d = divisor;
+ unsigned p;
+ T ad, anc, delta, q1, r1, q2, r2, t;
+ T signedMin = std::numeric_limits<T>::min();
+ DivisionMagic<T> mag;
+ unsigned bitWidth = sizeof(divisor) * 8;
+
+ // This code doesn't like to think of signedness as a type. Instead it likes to think that
+ // operations have signedness. This is how we generally do it in B3 as well. For this reason,
+ // this provides helpers for unsigned operations on the signed type (T).
+
+ auto zshr = [&] (T value, int amount) -> T {
+ return static_cast<typename std::make_unsigned<T>::type>(value) >> amount;
+ };
+
+ auto udiv = [&] (T left, T right) -> T {
+ return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) / static_cast<typename std::make_unsigned<T>::type>(right));
+ };
+
+ auto urem = [&] (T left, T right) -> T {
+ return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) % static_cast<typename std::make_unsigned<T>::type>(right));
+ };
+
+ auto aboveEqual = [&] (T left, T right) -> bool {
+ return static_cast<typename std::make_unsigned<T>::type>(left) >= static_cast<typename std::make_unsigned<T>::type>(right);
+ };
+
+ auto below = [&] (T left, T right) -> bool {
+ return static_cast<typename std::make_unsigned<T>::type>(left) < static_cast<typename std::make_unsigned<T>::type>(right);
+ };
+
+ ad = d < 0 ? -d : d;
+ t = signedMin + zshr(d, bitWidth - 1);
+ anc = t - 1 - urem(t, ad); // absolute value of nc
+ p = bitWidth - 1; // initialize p
+ q1 = udiv(signedMin, anc); // initialize q1 = 2p/abs(nc)
+ r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
+ q2 = udiv(signedMin, ad); // initialize q2 = 2p/abs(d)
+ r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
+ do {
+ p = p + 1;
+ q1 = q1 << 1; // update q1 = 2p/abs(nc)
+ r1 = r1 << 1; // update r1 = rem(2p/abs(nc))
+ if (aboveEqual(r1, anc)) { // must be unsigned comparison
+ q1 = q1 + 1;
+ r1 = r1 - anc;
+ }
+ q2 = q2 << 1; // update q2 = 2p/abs(d)
+ r2 = r2 << 1; // update r2 = rem(2p/abs(d))
+ if (aboveEqual(r2,ad)) { // must be unsigned comparison
+ q2 = q2 + 1;
+ r2 = r2 - ad;
+ }
+ delta = ad - r2;
+ } while (below(q1, delta) || (q1 == delta && r1 == 0));
+
+ mag.magicMultiplier = q2 + 1;
+ if (d < 0)
+ mag.magicMultiplier = -mag.magicMultiplier; // resulting magic number
+ mag.shift = p - bitWidth; // resulting shift
+
+ return mag;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3ComputeDivisionMagic_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp (195502 => 195503)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2016-01-23 02:10:17 UTC (rev 195502)
+++ trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2016-01-23 03:24:42 UTC (rev 195503)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "B3BasicBlockInlines.h"
</span><span class="cx"> #include "B3BlockInsertionSet.h"
</span><ins>+#include "B3ComputeDivisionMagic.h"
</ins><span class="cx"> #include "B3ControlValue.h"
</span><span class="cx"> #include "B3Dominators.h"
</span><span class="cx"> #include "B3IndexSet.h"
</span><span class="lines">@@ -508,7 +509,91 @@
</span><span class="cx"> // Note that this uses ChillDiv semantics. That's fine, because the rules for Div
</span><span class="cx"> // are strictly weaker: it has corner cases where it's allowed to do anything it
</span><span class="cx"> // likes.
</span><del>- replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1)));
</del><ins>+ if (replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1))))
+ break;
+
+ if (m_value->child(1)->hasInt()) {
+ switch (m_value->child(1)->asInt()) {
+ case -1:
+ // Turn this: Div(value, -1)
+ // Into this: Neg(value)
+ replaceWithNewValue(
+ m_proc.add<Value>(Neg, m_value->origin(), m_value->child(0)));
+ break;
+
+ case 0:
+ // Turn this: Div(value, 0)
+ // Into this: 0
+ // We can do this because it's precisely correct for ChillDiv and for Div we
+ // are allowed to do whatever we want.
+ m_value->replaceWithIdentity(m_value->child(1));
+ m_changed = true;
+ break;
+
+ case 1:
+ // Turn this: Div(value, 1)
+ // Into this: value
+ m_value->replaceWithIdentity(m_value->child(0));
+ m_changed = true;
+ break;
+
+ default:
+ // Perform super comprehensive strength reduction of division. Currently we
+ // only do this for 32-bit divisions, since we need a high multiply
+ // operation. We emulate it using 64-bit multiply. We can't emulate 64-bit
+ // high multiply with a 128-bit multiply because we don't have a 128-bit
+ // multiply. We could do it with a patchpoint if we cared badly enough.
+
+ if (m_value->type() != Int32)
+ break;
+
+ int32_t divisor = m_value->child(1)->asInt32();
+ DivisionMagic<int32_t> magic = computeDivisionMagic(divisor);
+
+ // Perform the "high" multiplication. We do it just to get the high bits.
+ // This is sort of like multiplying by the reciprocal, just more gnarly. It's
+ // from Hacker's Delight and I don't claim to understand it.
+ Value* magicQuotient = m_insertionSet.insert<Value>(
+ m_index, Trunc, m_value->origin(),
+ m_insertionSet.insert<Value>(
+ m_index, ZShr, m_value->origin(),
+ m_insertionSet.insert<Value>(
+ m_index, Mul, m_value->origin(),
+ m_insertionSet.insert<Value>(
+ m_index, SExt32, m_value->origin(), m_value->child(0)),
+ m_insertionSet.insert<Const64Value>(
+ m_index, m_value->origin(), magic.magicMultiplier)),
+ m_insertionSet.insert<Const32Value>(
+ m_index, m_value->origin(), 32)));
+
+ if (divisor > 0 && magic.magicMultiplier < 0) {
+ magicQuotient = m_insertionSet.insert<Value>(
+ m_index, Add, m_value->origin(), magicQuotient, m_value->child(0));
+ }
+ if (divisor < 0 && magic.magicMultiplier > 0) {
+ magicQuotient = m_insertionSet.insert<Value>(
+ m_index, Sub, m_value->origin(), magicQuotient, m_value->child(0));
+ }
+ if (magic.shift > 0) {
+ magicQuotient = m_insertionSet.insert<Value>(
+ m_index, SShr, m_value->origin(), magicQuotient,
+ m_insertionSet.insert<Const32Value>(
+ m_index, m_value->origin(), magic.shift));
+ }
+ m_value->replaceWithIdentity(
+ m_insertionSet.insert<Value>(
+ m_index, Add, m_value->origin(), magicQuotient,
+ m_insertionSet.insert<Value>(
+ m_index, ZShr, m_value->origin(), magicQuotient,
+ m_insertionSet.insert<Const32Value>(
+ m_index, m_value->origin(), 31))));
+ m_changed = true;
+ break;
+ }
+
+ if (m_value->opcode() != ChillDiv && m_value->opcode() != Div)
+ break;
+ }
</ins><span class="cx"> break;
</span><span class="cx">
</span><span class="cx"> case Mod:
</span></span></pre>
</div>
</div>
</body>
</html>