<!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>[279042] 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/279042">279042</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2021-06-18 11:25:50 -0700 (Fri, 18 Jun 2021)</dd>
</dl>

<h3>Log Message</h3>
<pre>Add a new pattern to B3ReduceStrength based on Bug 226984
https://bugs.webkit.org/show_bug.cgi?id=227138

Patch by Yijia Huang <yijia_huang@apple.com> on 2021-06-18
Reviewed by Filip Pizlo.

In the previous patch bug 226984, a new pattern could be introduced to
B3ReduceStrength.cpp for further optimization, which is that:

dest = (src >> shiftAmount) & mask

is equivalent to

src >> shiftAmount

under these constraints:

1. shiftAmount >= 0
2. mask has a binary format in contiguous ones starting from the
   least significant bit.
3. shiftAmount + bitCount(mask) == maxBitWidth

For instance (32-bit):

(src >> 12) & 0x000fffff == src >> 12

This reduction is more beneficial than UBFX in this case.

// B3 IR
Int @0 = ArgumentReg(%0)
Int @1 = 12
Int @2 = ZShr(@0, @1)
Int @3 = 0x000fffff
Int @4 = BitAnd(@2, @3))
Void@5 = Return(@4, Terminal)

w/o the pattern:
// Old optimized AIR
Ubfx %0, $12, $20, %0, @4
Ret  %0,               @5

w/ the pattern:
// New optimized AIR
Urshift %0, $12, %0, @3
Ret32   %0,          @6

* b3/B3ReduceStrength.cpp:
* b3/testb3.h:
* b3/testb3_2.cpp:
(testBitAndZeroShiftRightImmMask32):
(testBitAndZeroShiftRightImmMask64):
(addBitTests):</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp">trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3h">trunk/Source/JavaScriptCore/b3/testb3.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3_2cpp">trunk/Source/JavaScriptCore/b3/testb3_2.cpp</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (279041 => 279042)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog    2021-06-18 17:17:45 UTC (rev 279041)
+++ trunk/Source/JavaScriptCore/ChangeLog       2021-06-18 18:25:50 UTC (rev 279042)
</span><span class="lines">@@ -1,3 +1,57 @@
</span><ins>+2021-06-18  Yijia Huang  <yijia_huang@apple.com>
+
+        Add a new pattern to B3ReduceStrength based on Bug 226984
+        https://bugs.webkit.org/show_bug.cgi?id=227138
+
+        Reviewed by Filip Pizlo.
+
+        In the previous patch bug 226984, a new pattern could be introduced to 
+        B3ReduceStrength.cpp for further optimization, which is that:
+
+        dest = (src >> shiftAmount) & mask
+
+        is equivalent to
+
+        src >> shiftAmount
+
+        under these constraints:
+
+        1. shiftAmount >= 0 
+        2. mask has a binary format in contiguous ones starting from the 
+           least significant bit.
+        3. shiftAmount + bitCount(mask) == maxBitWidth
+
+        For instance (32-bit):
+
+        (src >> 12) & 0x000fffff == src >> 12
+
+        This reduction is more beneficial than UBFX in this case.  
+
+        // B3 IR
+        Int @0 = ArgumentReg(%0)
+        Int @1 = 12
+        Int @2 = ZShr(@0, @1)
+        Int @3 = 0x000fffff
+        Int @4 = BitAnd(@2, @3))
+        Void@5 = Return(@4, Terminal)    
+
+        w/o the pattern:
+        // Old optimized AIR
+        Ubfx %0, $12, $20, %0, @4
+        Ret  %0,               @5
+
+        w/ the pattern:
+        // New optimized AIR
+        Urshift %0, $12, %0, @3
+        Ret32   %0,          @6
+
+        * b3/B3ReduceStrength.cpp:
+        * b3/testb3.h:
+        * b3/testb3_2.cpp:
+        (testBitAndZeroShiftRightImmMask32):
+        (testBitAndZeroShiftRightImmMask64):
+        (addBitTests):
+
</ins><span class="cx"> 2021-06-18  Robin Morisset  <rmorisset@apple.com>
</span><span class="cx"> 
</span><span class="cx">         [DFG] Untyped branches should eliminate checks based on results from the AbstractInterpreter
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp (279041 => 279042)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp      2021-06-18 17:17:45 UTC (rev 279041)
+++ trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2021-06-18 18:25:50 UTC (rev 279042)
</span><span class="lines">@@ -42,6 +42,7 @@
</span><span class="cx"> #include "B3ValueKeyInlines.h"
</span><span class="cx"> #include "B3ValueInlines.h"
</span><span class="cx"> #include <wtf/HashMap.h>
</span><ins>+#include <wtf/StdLibExtras.h>
</ins><span class="cx"> 
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx"> 
</span><span class="lines">@@ -1035,6 +1036,23 @@
</span><span class="cx">                 break;
</span><span class="cx">             }
</span><span class="cx"> 
</span><ins>+            // Turn this: BitAnd(ZShr(value, shiftAmount), mask)
+            // - shiftAmount >= 0 and mask is contiguous ones from LSB, example 0b01111111
+            // - shiftAmount + bitCount(mask) == maxBitWidth
+            // Into this: ZShr(value, shiftAmount)
+            if (m_value->child(0)->opcode() == ZShr
+                && m_value->child(0)->child(1)->hasInt()
+                && m_value->child(1)->hasInt()) {
+                int64_t shiftAmount = m_value->child(0)->child(1)->asInt();
+                uint64_t mask = m_value->child(1)->asInt();
+                bool isValid = mask && !(mask & (mask + 1));
+                uint64_t maxBitWidth = m_value->child(0)->child(0)->type() == Int64 ? 64 : 32;
+                if (shiftAmount >= 0 && isValid && static_cast<uint64_t>(shiftAmount + WTF::bitCount(mask)) == maxBitWidth) {
+                    replaceWithIdentity(m_value->child(0));
+                    break;
+                }
+            }
+
</ins><span class="cx">             // Turn this: BitAnd(value, all-ones)
</span><span class="cx">             // Into this: value.
</span><span class="cx">             if ((m_value->type() == Int64 && m_value->child(1)->isInt64(std::numeric_limits<uint64_t>::max()))
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3h"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3.h (279041 => 279042)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3.h  2021-06-18 17:17:45 UTC (rev 279041)
+++ trunk/Source/JavaScriptCore/b3/testb3.h     2021-06-18 18:25:50 UTC (rev 279042)
</span><span class="lines">@@ -420,6 +420,8 @@
</span><span class="cx"> void testUbfx32PatternMatch();
</span><span class="cx"> void testUbfx64();
</span><span class="cx"> void testUbfx64PatternMatch();
</span><ins>+void testBitAndZeroShiftRightArgImmMask32();
+void testBitAndZeroShiftRightArgImmMask64();
</ins><span class="cx"> void testBasicSelect();
</span><span class="cx"> void testSelectTest();
</span><span class="cx"> void testSelectCompareDouble();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3_2cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3_2.cpp (279041 => 279042)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3_2.cpp      2021-06-18 17:17:45 UTC (rev 279041)
+++ trunk/Source/JavaScriptCore/b3/testb3_2.cpp 2021-06-18 18:25:50 UTC (rev 279042)
</span><span class="lines">@@ -2688,6 +2688,78 @@
</span><span class="cx">     }
</span><span class="cx"> }
</span><span class="cx"> 
</span><ins>+void testBitAndZeroShiftRightArgImmMask32()
+{
+    // Turn this: (tmp >> imm) & mask 
+    // Into this: tmp >> imm
+    uint32_t tmp = 0xffffffff;
+    Vector<uint32_t> imms = { 4, 28 };
+    Vector<uint32_t> masks = { 0x0fffffff, 0xf };
+
+    auto test = [&] (uint32_t imm, uint32_t mask) {
+        Procedure proc;
+        BasicBlock* root = proc.addBlock();
+
+        Value* tmpValue = root->appendNew<Value>(
+            proc, Trunc, Origin(), 
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        Value* immValue = root->appendNew<Const32Value>(proc, Origin(), imm);
+        Value* leftValue = root->appendNew<Value>(proc, ZShr, Origin(), tmpValue, immValue);
+        Value* rightValue = root->appendNew<Const32Value>(proc, Origin(), mask);
+        root->appendNewControlValue(
+            proc, Return, Origin(),
+            root->appendNew<Value>(proc, BitAnd, Origin(), leftValue, rightValue));
+
+        auto code = compileProc(proc);
+        if (isARM64()) {
+            checkUsesInstruction(*code, "lsr");
+            checkDoesNotUseInstruction(*code, "and");
+            checkDoesNotUseInstruction(*code, "ubfx");
+        }
+        uint32_t lhs = invoke<uint32_t>(*code, tmp);
+        uint32_t rhs = tmp >> imm;
+        CHECK(lhs == rhs);
+    };
+
+    for (size_t i = 0; i < imms.size(); ++i)
+        test(imms.at(i), masks.at(i));
+}
+
+void testBitAndZeroShiftRightArgImmMask64()
+{
+    // Turn this: (tmp >> imm) & mask 
+    // Into this: tmp >> imm
+    uint64_t tmp = 0xffffffffffffffff;
+    Vector<uint64_t> imms = { 4, 60 };
+    Vector<uint64_t> masks = { 0x0fffffffffffffff, 0xf };
+
+    auto test = [&] (uint64_t imm, uint64_t mask) {
+        Procedure proc;
+        BasicBlock* root = proc.addBlock();
+
+        Value* tmpValue = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+        Value* immValue = root->appendNew<Const32Value>(proc, Origin(), imm);
+        Value* leftValue = root->appendNew<Value>(proc, ZShr, Origin(), tmpValue, immValue);
+        Value* rightValue = root->appendNew<Const64Value>(proc, Origin(), mask);
+        root->appendNewControlValue(
+            proc, Return, Origin(),
+            root->appendNew<Value>(proc, BitAnd, Origin(), leftValue, rightValue));
+
+        auto code = compileProc(proc);
+        if (isARM64()) {
+            checkUsesInstruction(*code, "lsr");
+            checkDoesNotUseInstruction(*code, "and");
+            checkDoesNotUseInstruction(*code, "ubfx");
+        }
+        uint64_t lhs = invoke<uint64_t>(*code, tmp);
+        uint64_t rhs = tmp >> imm;
+        CHECK(lhs == rhs);
+    };
+
+    for (size_t i = 0; i < imms.size(); ++i)
+        test(imms.at(i), masks.at(i));
+}
+
</ins><span class="cx"> static void testBitAndArgs(int64_t a, int64_t b)
</span><span class="cx"> {
</span><span class="cx">     Procedure proc;
</span><span class="lines">@@ -3506,7 +3578,8 @@
</span><span class="cx">     RUN(testUbfx32PatternMatch());
</span><span class="cx">     RUN(testUbfx64());
</span><span class="cx">     RUN(testUbfx64PatternMatch());
</span><del>-
</del><ins>+    RUN(testBitAndZeroShiftRightArgImmMask32());
+    RUN(testBitAndZeroShiftRightArgImmMask64());
</ins><span class="cx">     RUN(testBitAndArgs(43, 43));
</span><span class="cx">     RUN(testBitAndArgs(43, 0));
</span><span class="cx">     RUN(testBitAndArgs(10, 3));
</span></span></pre>
</div>
</div>

</body>
</html>