<!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>[281587] 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/281587">281587</a></dd>
<dt>Author</dt> <dd>yijia_huang@apple.com</dd>
<dt>Date</dt> <dd>2021-08-25 14:19:31 -0700 (Wed, 25 Aug 2021)</dd>
</dl>

<h3>Log Message</h3>
<pre>[ARM64] Fix pre-index address mode
https://bugs.webkit.org/show_bug.cgi?id=229175

Reviewed by Saam Barati.

This patch fixes the canonicalization phase for pre/post-increment address mode
due to the potential bugs commented on in the previous patch
https://bugs.webkit.org/show_bug.cgi?id=228538. And this patch removed the
temporary fix in https://bugs.webkit.org/show_bug.cgi?id=229211.

Previously, the pre-index address mode for Load instruction convert the pattern
to the canonical form like this:

    address = Add(base, offset)       address = Add(base, offset)
    ...                          -->  newMemory = Load(base, offset)
    ...                               ...
    memory = Load(base, offset)       memory = Identity(newMemory)

which is wrong. Assume "..." contains a store to a memory location that aliases for address:

    address = Add(base, offset)       address = Add(base, offset)
    ...                          -->  newMemory = Load(base, offset)
    ...                               ...
    Store(value1, address)            Store(value1, address)
    memory = Load(base, offset)       memory = Identity(newMemory)

The loaded value should always be value1 which is not true after the conversion.
So, moving the load above the store is semantically incorrect because it's not identical to
the behavior of the original program. In this case, maybe we should apply alias analysis to
detect the violations of reference updating.

To solve this problem, we moves the address value to just before the memory value instead of
moving memory value upward.

Convert Pre-Index Load Pattern to the Canonical Form:

    address = Add(base, offset)                    address = Nop
    ...                                            ...
    ...                                            newAddress = Add(base, offset)
    memory = Load(base, offset)            -->     memory = Load(base, offset)
    ...                                            ...
    parent = B3Opcode(address, ...)                parent = B3Opcode(newAddress, ...)

Convert Pre-Index Store Pattern to the Canonical Form:

    address = Add(base, offset)                    address = Nop
    ...                                            ...
    ...                                            newAddress = Add(base, offset)
    memory = Store(value1, base, offset)   -->     memory = Store(value1, base, offset)
    ...                                            ...
    parent = B3Opcode(address, ...)                parent = B3Opcode(newAddress, ...)

To move the address value downward, we need to make sure that no use reference of address between
the address and memory values.

* b3/B3CanonicalizePrePostIncrements.cpp:
(JSC::B3::canonicalizePrePostIncrements):
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3ValueKey.h:
* b3/B3ValueKeyInlines.h:
(JSC::B3::ValueKey::ValueKey):
* b3/testb3.h:
* b3/testb3_3.cpp:
(testLoadWithStorePreIndex32):
(testStorePreIndex32):
(testStorePreIndex64):
(testStorePostIndex32):
(testStorePostIndex64):
(addShrTests):
* runtime/OptionsList.h:</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3CanonicalizePrePostIncrementscpp">trunk/Source/JavaScriptCore/b3/B3CanonicalizePrePostIncrements.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Generatecpp">trunk/Source/JavaScriptCore/b3/B3Generate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ValueKeyh">trunk/Source/JavaScriptCore/b3/B3ValueKey.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ValueKeyInlinesh">trunk/Source/JavaScriptCore/b3/B3ValueKeyInlines.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3h">trunk/Source/JavaScriptCore/b3/testb3.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3_3cpp">trunk/Source/JavaScriptCore/b3/testb3_3.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeOptionsListh">trunk/Source/JavaScriptCore/runtime/OptionsList.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog    2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/ChangeLog       2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -1,3 +1,77 @@
</span><ins>+2021-08-25  Yijia Huang  <yijia_huang@apple.com>
+
+        [ARM64] Fix pre-index address mode
+        https://bugs.webkit.org/show_bug.cgi?id=229175
+
+        Reviewed by Saam Barati.
+
+        This patch fixes the canonicalization phase for pre/post-increment address mode
+        due to the potential bugs commented on in the previous patch
+        https://bugs.webkit.org/show_bug.cgi?id=228538. And this patch removed the 
+        temporary fix in https://bugs.webkit.org/show_bug.cgi?id=229211.
+
+        Previously, the pre-index address mode for Load instruction convert the pattern 
+        to the canonical form like this:
+
+            address = Add(base, offset)       address = Add(base, offset)
+            ...                          -->  newMemory = Load(base, offset)
+            ...                               ...
+            memory = Load(base, offset)       memory = Identity(newMemory)
+
+        which is wrong. Assume "..." contains a store to a memory location that aliases for address:
+
+            address = Add(base, offset)       address = Add(base, offset)
+            ...                          -->  newMemory = Load(base, offset)
+            ...                               ...
+            Store(value1, address)            Store(value1, address)
+            memory = Load(base, offset)       memory = Identity(newMemory)
+
+        The loaded value should always be value1 which is not true after the conversion.
+        So, moving the load above the store is semantically incorrect because it's not identical to
+        the behavior of the original program. In this case, maybe we should apply alias analysis to
+        detect the violations of reference updating.
+
+        To solve this problem, we moves the address value to just before the memory value instead of
+        moving memory value upward.
+
+        Convert Pre-Index Load Pattern to the Canonical Form:
+
+            address = Add(base, offset)                    address = Nop
+            ...                                            ...
+            ...                                            newAddress = Add(base, offset)
+            memory = Load(base, offset)            -->     memory = Load(base, offset)
+            ...                                            ...
+            parent = B3Opcode(address, ...)                parent = B3Opcode(newAddress, ...)
+
+        Convert Pre-Index Store Pattern to the Canonical Form:
+
+            address = Add(base, offset)                    address = Nop
+            ...                                            ...
+            ...                                            newAddress = Add(base, offset)
+            memory = Store(value1, base, offset)   -->     memory = Store(value1, base, offset)
+            ...                                            ...
+            parent = B3Opcode(address, ...)                parent = B3Opcode(newAddress, ...)
+
+        To move the address value downward, we need to make sure that no use reference of address between
+        the address and memory values.
+
+        * b3/B3CanonicalizePrePostIncrements.cpp:
+        (JSC::B3::canonicalizePrePostIncrements):
+        * b3/B3Generate.cpp:
+        (JSC::B3::generateToAir):
+        * b3/B3ValueKey.h:
+        * b3/B3ValueKeyInlines.h:
+        (JSC::B3::ValueKey::ValueKey):
+        * b3/testb3.h:
+        * b3/testb3_3.cpp:
+        (testLoadWithStorePreIndex32):
+        (testStorePreIndex32):
+        (testStorePreIndex64):
+        (testStorePostIndex32):
+        (testStorePostIndex64):
+        (addShrTests):
+        * runtime/OptionsList.h:
+
</ins><span class="cx"> 2021-08-25  Xan Lopez  <xan@igalia.com>
</span><span class="cx"> 
</span><span class="cx">         [JSC] Infinite loop in for...in after r280760
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3CanonicalizePrePostIncrementscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3CanonicalizePrePostIncrements.cpp (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3CanonicalizePrePostIncrements.cpp       2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/B3CanonicalizePrePostIncrements.cpp  2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -52,69 +52,57 @@
</span><span class="cx"> 
</span><span class="cx">     unsigned index { 0 };
</span><span class="cx">     InsertionSet insertionSet { proc };
</span><del>-    BlockInsertionSet blockInsertionSet { proc };
</del><span class="cx"> 
</span><span class="cx">     Dominators& dominators = proc.dominators();
</span><span class="cx">     BackwardsDominators& backwardsDominators = proc.backwardsDominators();
</span><span class="cx"> 
</span><del>-    IndexSet<Value*> ignoredValues;
-    HashMap<Value*, Vector<MemoryValue*>> baseToLoads;
-    HashMap<MemoryValue*, Value*> preIndexLoadCandidates;
-    HashMap<MemoryValue*, Value*> postIndexLoadCandidates;
</del><ins>+    IndexSet<Value*> handledValues;
+    HashMap<Value*, unsigned> memoryToIndex;
+    HashMap<Value*, Vector<Value*>> addUses;
+    HashMap<Value*, Vector<MemoryValue*>> baseToMemories;
</ins><span class="cx">     HashMap<ValueKey, Vector<Value*>> baseOffsetToAddresses;
</span><ins>+    HashMap<MemoryValue*, Vector<Value*>> preIndexCandidates;
+    HashMap<MemoryValue*, Vector<Value*>> postIndexCandidates;
+    HashMap<BasicBlock*, HashSet<MemoryValue*>> blockToPrePostIndexCandidates;
</ins><span class="cx"> 
</span><del>-    HashMap<Value*, Vector<MemoryValue*>> baseToStores;
-    HashMap<MemoryValue*, Value*> postIndexStoreCandidates;
-
-    auto tryAddPrePostIndexCandidate = [&] (Value* value) {
</del><ins>+    // Strength Reduction will leave the IR in the form we're matching now. 
+    // It'll take an add(x, constant) that's an address and move the offset 
+    // into the load itself, and that's why we can match this redundancy.
+    auto tryAddCandidates = [&] (Value* value) {
</ins><span class="cx">         switch (value->opcode()) {
</span><del>-        case Load: {
-            // Pre-Index Pattern:
-            //     address = Add(base, offset)
-            //     ...
-            //     memory = Load(base, offset)
-            // Post-Index Pattern:
-            //     memory = Load(base, 0)
-            //     ...
-            //     address = Add(base, offset)
-            auto tryAddpreIndexLoadCandidates = [&] () {
-                MemoryValue* memory = value->as<MemoryValue>();
-                if (memory->type() != Int32 && memory->type() != Int64)
-                    return;
-                if (memory->offset()) {
-                    if (!Arg::isValidIncrementIndexForm(memory->offset()))
-                        return;
-                    ValueKey baseOffsetkey = ValueKey(memory->child(0), static_cast<int64_t>(memory->offset()));
-                    if (!baseOffsetToAddresses.contains(baseOffsetkey))
-                        return;
-                    for (Value* address : baseOffsetToAddresses.get(baseOffsetkey))
-                        preIndexLoadCandidates.add(memory, address);
-                } else
-                    baseToLoads.add(memory->child(0), Vector<MemoryValue*>()).iterator->value.append(memory);
-            };
-
-            tryAddpreIndexLoadCandidates();
-            break;
-        }
-
</del><ins>+        case Load:
</ins><span class="cx">         case Store: {
</span><del>-            // Pre-Index Pattern:
-            //     address = Add(base, offset)
-            //     memory = Store(value, base, offset)
-            // Post-Index Pattern:
-            //     memory = Store(value, base, 0)
-            //     ...
-            //     address = Add(base, offset)
-            auto tryUpdateBaseToStores = [&] () {
-                MemoryValue* memory = value->as<MemoryValue>();
-                if (memory->child(0)->type() != Int32 && memory->child(0)->type() != Int64)
-                    return;
-                if (memory->child(0)->hasInt() || memory->offset())
-                    return;
-                baseToStores.add(memory->child(1), Vector<MemoryValue*>()).iterator->value.append(memory);
-            };
-
-            tryUpdateBaseToStores();
</del><ins>+            MemoryValue* memory = value->as<MemoryValue>();
+            Value* type = value->opcode() == Load ? memory : memory->child(0);
+            if (type->type() != Int32 && type->type() != Int64)
+                break;
+            if (memory->offset()) {
+                // Pre-Index Load/Store Pattern:
+                //     address = Add(base, offset)
+                //     ...
+                //     memory = MemoryValue(base, offset)
+                ValueKey baseOffsetKey = ValueKey(memory->lastChild(), memory->offset());
+                auto iter = baseOffsetToAddresses.find(baseOffsetKey);
+                if (iter == baseOffsetToAddresses.end())
+                    break;
+                for (Value* address : iter->value) {
+                    // The goal is to move the Add to this Load/Store. We only move the Add to this Memory value
+                    // if we guarantee it dominates all uses. If there are already other uses of the Add, it guarantees
+                    // this Memory value doesn't dominate those uses. This is because we're visiting the program in pre-order
+                    // traversal, so we visit this Memory value before all the things it dominates. So if the Add has other
+                    // users, we must not dominate those users. Therefore, this MemoryValue won't be a candidate.
+                    auto addUsesIter = addUses.find(address);
+                    if (addUsesIter != addUses.end() && addUsesIter->value.size() > 0)
+                        continue;
+                    // double check offsets to avoid ValueKey collisions
+                    if (memory->offset() != static_cast<Value::OffsetType>(address->child(1)->asIntPtr()))
+                        continue;
+                    preIndexCandidates.add(memory, Vector<Value*>()).iterator->value.append(address);
+                    blockToPrePostIndexCandidates.add(memory->owner, HashSet<MemoryValue*>()).iterator->value.add(memory);
+                }
+            } else
+                baseToMemories.add(memory->lastChild(), Vector<MemoryValue*>()).iterator->value.append(memory);
+            memoryToIndex.add(memory, index);
</ins><span class="cx">             break;
</span><span class="cx">         }
</span><span class="cx"> 
</span><span class="lines">@@ -122,27 +110,29 @@
</span><span class="cx">             Value* left = value->child(0);
</span><span class="cx">             Value* right = value->child(1);
</span><span class="cx"> 
</span><del>-            auto tryAddpostIndexCandidates = [&] () {
-                if (!right->hasIntPtr() || value->type() != Int64)
-                    return;
-                intptr_t offset = right->asIntPtr();
-                Value::OffsetType smallOffset = static_cast<Value::OffsetType>(offset);
-                if (smallOffset != offset || !Arg::isValidIncrementIndexForm(smallOffset))
-                    return;
-                // so far this Add value is a valid address candidate for both prefix and postfix pattern
-                ValueKey baseOffsetkey = ValueKey(left, static_cast<int64_t>(smallOffset));
-                baseOffsetToAddresses.add(baseOffsetkey, Vector<Value*>()).iterator->value.append(value);
-                if (baseToLoads.contains(left)) {
-                    for (MemoryValue* memory : baseToLoads.get(left))
-                        postIndexLoadCandidates.add(memory, value);
-                }
-                if (baseToStores.contains(left)) {
-                    for (MemoryValue* memory : baseToStores.get(left))
-                        postIndexStoreCandidates.add(memory, value);
-                }
-            };
</del><ins>+            if (!right->hasIntPtr() || value->type() != Int64)
+                break;
+            intptr_t offset = right->asIntPtr();
+            Value::OffsetType smallOffset = static_cast<Value::OffsetType>(offset);
+            if (smallOffset != offset || !Arg::isValidIncrementIndexForm(smallOffset))
+                break;
</ins><span class="cx"> 
</span><del>-            tryAddpostIndexCandidates();
</del><ins>+            // so far this Add value is a valid address candidate for both prefix and postfix pattern
+            addUses.add(value, Vector<Value*>());
+            ValueKey baseOffsetKey = ValueKey(left, smallOffset);
+            baseOffsetToAddresses.add(baseOffsetKey, Vector<Value*>()).iterator->value.append(value);
+
+            // Post-Index Load/Store Pattern:
+            //     memory = MemoryValue(base, 0)
+            //     ...
+            //     address = Add(base, offset)
+            auto iter = baseToMemories.find(left);
+            if (iter == baseToMemories.end())
+                break;
+            for (MemoryValue* memory : iter->value) {
+                postIndexCandidates.add(memory, Vector<Value*>()).iterator->value.append(value);
+                blockToPrePostIndexCandidates.add(memory->owner, HashSet<MemoryValue*>()).iterator->value.add(memory);
+            }
</ins><span class="cx">             break;
</span><span class="cx">         }
</span><span class="cx"> 
</span><span class="lines">@@ -149,11 +139,17 @@
</span><span class="cx">         default:
</span><span class="cx">             break;
</span><span class="cx">         }
</span><ins>+
+        for (Value* child : value->children()) {
+            auto iter = addUses.find(child);
+            if (iter != addUses.end())
+                iter->value.append(value);
+        }
</ins><span class="cx">     };
</span><span class="cx"> 
</span><span class="cx">     for (BasicBlock* basicBlock : proc.blocksInPreOrder()) {
</span><span class="cx">         for (index = 0; index < basicBlock->size(); ++index)
</span><del>-            tryAddPrePostIndexCandidate(basicBlock->at(index));
</del><ins>+            tryAddCandidates(basicBlock->at(index));
</ins><span class="cx">     }
</span><span class="cx"> 
</span><span class="cx">     auto controlEquivalent = [&] (Value* v1, Value* v2) -> bool {
</span><span class="lines">@@ -161,68 +157,75 @@
</span><span class="cx">             || (dominators.dominates(v2->owner, v1->owner) && backwardsDominators.dominates(v1->owner, v2->owner));
</span><span class="cx">     };
</span><span class="cx"> 
</span><del>-    // This search is expensive. However, due to the greedy pattern
-    // matching, no better method can be proposed at present.
-    auto valueIndexInBasicBlock = [&] (Value* value) -> unsigned {
-        unsigned index = 0;
-        BasicBlock* block = value->owner;
-        for (index = 0; index < block->size(); ++index) {
-            if (block->at(index) == value)
-                return index;
-        }
-        return index;
-    };
</del><ins>+    for (const auto& pair : blockToPrePostIndexCandidates) {
+        BasicBlock* basicBlock = pair.key;
+        for (MemoryValue* memory : pair.value) {
+            if (handledValues.contains(memory))
+                continue;
</ins><span class="cx"> 
</span><del>-    for (auto pair : preIndexLoadCandidates) {
-        MemoryValue* memory = pair.key;
-        Value* address = pair.value;
-        if (ignoredValues.contains(memory) || ignoredValues.contains(address) || !controlEquivalent(memory, address))
-            continue;
-        // address = Add(base, offset)       address = Add(base, offset)
-        // ...                          -->  newMemory = Load(base, offset)
-        // ...                               ...
-        // memory = Load(base, offset)       memory = Identity(newMemory)
-        unsigned insertionIndex = valueIndexInBasicBlock(address) + 1;
-        MemoryValue* newMemory = insertionSet.insert<MemoryValue>(insertionIndex, Load, memory->type(), address->origin(), memory->lastChild());
-        newMemory->setOffset(memory->offset());
-        memory->replaceWithIdentity(newMemory);
-        insertionSet.execute(address->owner);
</del><ins>+            // Convert Pre-Index Load/Store Pattern to the Canonical Form:
+            //     address = Add(base, offset)                    address = Nop
+            //     ...                                            ...
+            //     ...                                            newAddress = Add(base, offset)
+            //     memory = MemoryValue(base, offset)     -->     memory = MemoryValue(base, offset)
+            //     ...                                            ...
+            //     parent = B3Opcode(address, ...)                parent = B3Opcode(newAddress, ...)
+            for (Value* address : preIndexCandidates.get(memory)) {
+                if (handledValues.contains(address) || !controlEquivalent(memory, address))
+                    continue;
</ins><span class="cx"> 
</span><del>-        ignoredValues.add(memory);
-        ignoredValues.add(address);
-    }
</del><ins>+                auto dominatesAllAddUses = [&] () -> bool {
+                    auto iter = addUses.find(address);
+                    ASSERT(iter != addUses.end() && iter->value.size());
+                    for (Value* parent : iter->value) {
+                        if (!dominators.dominates(memory->owner, parent->owner))
+                            return false;
+                    }
+                    return true;
+                };
</ins><span class="cx"> 
</span><del>-    auto detectPostIndex = [&] (const HashMap<MemoryValue*, Value*>& candidates) {
-        for (auto pair : candidates) {
-            MemoryValue* memory = pair.key;
-            Value* address = pair.value;
-            if (ignoredValues.contains(memory) || ignoredValues.contains(address) || !controlEquivalent(memory, address))
-                continue;
</del><ins>+                if (!dominatesAllAddUses())
+                    continue;
</ins><span class="cx"> 
</span><del>-            unsigned insertionIndex = valueIndexInBasicBlock(memory);
-            Value* newOffset = insertionSet.insert<Const64Value>(insertionIndex, memory->origin(), address->child(1)->asInt());
-            Value* newAddress = insertionSet.insert<Value>(insertionIndex, Add, memory->origin(), address->child(0), newOffset);
-            address->replaceWithIdentity(newAddress);
-            insertionSet.execute(memory->owner);
</del><ins>+                unsigned insertionIndex = memoryToIndex.get(memory);
+                Value* newAddress = insertionSet.insert<Value>(insertionIndex, Add, memory->origin(), address->child(0), address->child(1));
+                for (Value* parent : addUses.get(address)) {
+                    for (unsigned i = 0; i < parent->numChildren(); ++i) {
+                        Value*& child = parent->child(i);
+                        if (child == address)
+                            child = newAddress;
+                    }
+                }
+                address->replaceWithNopIgnoringType();
</ins><span class="cx"> 
</span><del>-            ignoredValues.add(memory);
-            ignoredValues.add(address);
</del><ins>+                handledValues.add(memory);
+                handledValues.add(address);
+            }
+
+            // Convert Post-Index Load/Store Pattern to the Canonical Form:
+            //     ...                                  newOffset = Constant
+            //     ...                                  newAddress = Add(base, newOffset)
+            //     memory = MemoryValue(base, 0)        memory = MemoryValue(base, 0)
+            //     ...                            -->   ...
+            //     address = Add(base, offset)          address = Identity(newAddress)
+            for (Value* address : postIndexCandidates.get(memory)) {
+                if (handledValues.contains(address) || !controlEquivalent(memory, address))
+                    continue;
+
+                unsigned insertionIndex = memoryToIndex.get(memory);
+                Value* newOffset = insertionSet.insert<Const64Value>(insertionIndex, memory->origin(), address->child(1)->asInt());
+                Value* newAddress = insertionSet.insert<Value>(insertionIndex, Add, memory->origin(), address->child(0), newOffset);
+                address->replaceWithIdentity(newAddress);
+
+                handledValues.add(memory);
+                handledValues.add(address);
+            }
</ins><span class="cx">         }
</span><del>-    };
</del><ins>+        // After this executes, memoryToIndex no longer contains up to date information for this block.
+        // But that's ok because we never touch this block again.
+        insertionSet.execute(basicBlock);
+    }
</ins><span class="cx"> 
</span><del>-    // ...                                  newOffset = Constant
-    // ...                                  newAddress = Add(base, newOffset)
-    // memory = Load(base, 0)               memory = Load(base, 0)
-    // ...                            -->   ...
-    // address = Add(base, offset)          address = Identity(newAddress)
-    detectPostIndex(postIndexLoadCandidates);
-
-    // ...                                  newOffset = Constant
-    // ...                                  newAddress = Add(base, newOffset)
-    // memory = Store(value, base, 0)       memory = Store(value, base, 0)
-    // ...                            -->   ...
-    // address = Add(base, offset)          address = Identity(newAddress)
-    detectPostIndex(postIndexStoreCandidates);
</del><span class="cx">     return true;
</span><span class="cx"> }
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Generatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Generate.cpp (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Generate.cpp    2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/B3Generate.cpp       2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -118,7 +118,7 @@
</span><span class="cx">     lowerMacrosAfterOptimizations(procedure);
</span><span class="cx">     legalizeMemoryOffsets(procedure);
</span><span class="cx">     moveConstants(procedure);
</span><del>-    if (Options::useB3CanonicalizePrePostIncrements() && procedure.optLevel() >= 2)
</del><ins>+    if (procedure.optLevel() >= 2)
</ins><span class="cx">         canonicalizePrePostIncrements(procedure);
</span><span class="cx">     eliminateDeadCode(procedure);
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ValueKeyh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ValueKey.h (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ValueKey.h      2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/B3ValueKey.h 2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -56,7 +56,7 @@
</span><span class="cx">     {
</span><span class="cx">     }
</span><span class="cx"> 
</span><del>-    ValueKey(Value* child, int64_t value);
</del><ins>+    ValueKey(Value* child, int32_t offset);
</ins><span class="cx"> 
</span><span class="cx">     ValueKey(Kind, Type, Value* child);
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ValueKeyInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ValueKeyInlines.h (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ValueKeyInlines.h       2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/B3ValueKeyInlines.h  2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -33,12 +33,14 @@
</span><span class="cx"> 
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx"> 
</span><del>-inline ValueKey::ValueKey(Value* child, int64_t value)
</del><ins>+inline ValueKey::ValueKey(Value* child, int32_t offset)
</ins><span class="cx"> {
</span><span class="cx">     m_kind = Oops;
</span><span class="cx">     m_type = Void;
</span><del>-    u.indices[0] = child->index();
-    u.value = value;
</del><ins>+    // The observation is that when both child->index() and offset are 0's,
+    // HashMap would not accept the ValueKey.
+    u.indices[0] = child->index() + 1;
+    u.indices[1] = offset + 1;
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> inline ValueKey::ValueKey(Kind kind, Type type, Value* child)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3h"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3.h (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3.h  2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/testb3.h     2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -1164,6 +1164,7 @@
</span><span class="cx"> bool shouldRun(const char* filter, const char* testName);
</span><span class="cx"> 
</span><span class="cx"> void testLoadPreIndex32();
</span><ins>+void testLoadWithStorePreIndex32();
</ins><span class="cx"> void testLoadPreIndex64();
</span><span class="cx"> void testLoadPostIndex32();
</span><span class="cx"> void testLoadPostIndex64();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3_3cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3_3.cpp (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3_3.cpp      2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/b3/testb3_3.cpp 2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -102,6 +102,83 @@
</span><span class="cx">     CHECK_EQ(invoke<int32_t>(*code, bitwise_cast<intptr_t>(ptr)), test());
</span><span class="cx"> }
</span><span class="cx"> 
</span><ins>+void testLoadWithStorePreIndex32()
+{
+    if (Options::defaultB3OptLevel() < 2)
+        return;
+
+    int32_t nums[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+    int32_t* ptr = nums;
+
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* loopTest = proc.addBlock();
+    BasicBlock* loopBody = proc.addBlock();
+    BasicBlock* done = proc.addBlock();
+
+    Variable* r = proc.addVariable(Int32);
+    Variable* p = proc.addVariable(Int64);
+
+    // ---------------------- Root_Block
+    // r1 = 0
+    // Upsilon(r1, ^r2)
+    // p1 = addr
+    // Upsilon(p1, ^p2)
+    Value* r1 = root->appendIntConstant(proc, Origin(), Int32, 0);
+    root->appendNew<VariableValue>(proc, B3::Set, Origin(), r, r1);
+    Value* p1 = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+    root->appendNew<VariableValue>(proc, B3::Set, Origin(), p, p1);
+    root->appendNewControlValue(proc, Jump, Origin(), FrequentedBlock(loopTest));
+
+    // ---------------------- Loop_Test_Block
+    // loop:
+    // p2 = Phi()
+    // r2 = Phi()
+    // if r2 >= 10 goto done
+    Value* r2 = loopTest->appendNew<VariableValue>(proc, B3::Get, Origin(), r);
+    Value* p2 = loopTest->appendNew<VariableValue>(proc, B3::Get, Origin(), p);
+    Value* cond = loopTest->appendNew<Value>(proc, AboveEqual, Origin(), r2, loopTest->appendNew<Const32Value>(proc, Origin(), 10));
+    loopTest->appendNewControlValue(proc, Branch, Origin(), cond, FrequentedBlock(done), FrequentedBlock(loopBody));
+
+    // ---------------------- Loop_Body_Block
+    // p3 = p2 + 1
+    // Upsilon(p3, ^p2)
+    // p3' = &p3
+    // store(5, p3')
+    // r3 = r2 + load(p3)
+    // Upsilon(r3, ^r2)
+    // goto loop
+    Value* p3 = loopBody->appendNew<Value>(proc, Add, Origin(), p2, loopBody->appendNew<Const64Value>(proc, Origin(), 4));
+    loopBody->appendNew<VariableValue>(proc, B3::Set, Origin(), p, p3);
+    Value* p3Prime = loopBody->appendNew<Value>(proc, Opaque, Origin(), p3);
+    loopBody->appendNew<MemoryValue>(proc, Store, Origin(), loopBody->appendNew<Const32Value>(proc, Origin(), 5), p3Prime);
+    Value* r3 = loopBody->appendNew<Value>(proc, Add, Origin(), r2, loopBody->appendNew<MemoryValue>(proc, Load, Int32, Origin(), p3));
+    loopBody->appendNew<VariableValue>(proc, B3::Set, Origin(), r, r3);
+    loopBody->appendNewControlValue(proc, Jump, Origin(), FrequentedBlock(loopTest));
+
+    // ---------------------- Done_Block
+    // done:
+    // return r2
+    done->appendNewControlValue(proc, Return, Origin(), r2);
+
+    proc.resetReachability();
+    validate(proc);
+    fixSSA(proc);
+
+    auto code = compileProc(proc);
+
+    auto test = [&] () -> int32_t {
+        int32_t r = 0;
+        while (r < 10) {
+            *++ptr = 5;
+            r += *ptr;
+        }
+        return r;
+    };
+
+    CHECK_EQ(invoke<int32_t>(*code, bitwise_cast<intptr_t>(ptr)), test());
+}
+
</ins><span class="cx"> void testLoadPreIndex64()
</span><span class="cx"> {
</span><span class="cx">     if (Options::defaultB3OptLevel() < 2)
</span><span class="lines">@@ -344,6 +421,7 @@
</span><span class="cx">     auto code = compileProc(proc);
</span><span class="cx">     if (isARM64())
</span><span class="cx">         checkUsesInstruction(*code, "#4]!");
</span><ins>+
</ins><span class="cx">     intptr_t res = invoke<intptr_t>(*code, bitwise_cast<intptr_t>(ptr), 4);
</span><span class="cx">     ptr = bitwise_cast<int32_t*>(res);
</span><span class="cx">     CHECK_EQ(nums[2], *ptr);
</span><span class="lines">@@ -368,6 +446,9 @@
</span><span class="cx">     root->appendNewControlValue(proc, Return, Origin(), preIncrement);
</span><span class="cx"> 
</span><span class="cx">     auto code = compileProc(proc);
</span><ins>+    if (isARM64())
+        checkUsesInstruction(*code, "#8]!");
+
</ins><span class="cx">     intptr_t res = invoke<intptr_t>(*code, bitwise_cast<intptr_t>(ptr), 4);
</span><span class="cx">     ptr = bitwise_cast<int64_t*>(res);
</span><span class="cx">     CHECK_EQ(nums[2], *ptr);
</span><span class="lines">@@ -396,6 +477,7 @@
</span><span class="cx">     auto code = compileProc(proc);
</span><span class="cx">     if (isARM64())
</span><span class="cx">         checkUsesInstruction(*code, "], #4");
</span><ins>+
</ins><span class="cx">     intptr_t res = invoke<intptr_t>(*code, bitwise_cast<intptr_t>(ptr), 4);
</span><span class="cx">     ptr = bitwise_cast<int32_t*>(res);
</span><span class="cx">     CHECK_EQ(nums[1], 4);
</span><span class="lines">@@ -423,6 +505,7 @@
</span><span class="cx">     auto code = compileProc(proc);
</span><span class="cx">     if (isARM64())
</span><span class="cx">         checkUsesInstruction(*code, "], #8");
</span><ins>+
</ins><span class="cx">     intptr_t res = invoke<intptr_t>(*code, bitwise_cast<intptr_t>(ptr), 4);
</span><span class="cx">     ptr = bitwise_cast<int64_t*>(res);
</span><span class="cx">     CHECK_EQ(nums[1], 4);
</span><span class="lines">@@ -4097,17 +4180,15 @@
</span><span class="cx">     RUN(testZShrArgImm32(0xffffffff, 1));
</span><span class="cx">     RUN(testZShrArgImm32(0xffffffff, 63));
</span><span class="cx"> 
</span><del>-    if (Options::useB3CanonicalizePrePostIncrements()) {
-        RUN(testLoadPreIndex32());
-        RUN(testLoadPreIndex64());
-        RUN(testLoadPostIndex32());
-        RUN(testLoadPostIndex64());
</del><ins>+    RUN(testLoadPreIndex32());
+    RUN(testLoadPreIndex64());
+    RUN(testLoadPostIndex32());
+    RUN(testLoadPostIndex64());
</ins><span class="cx"> 
</span><del>-        RUN(testStorePreIndex32());
-        RUN(testStorePreIndex64());
-        RUN(testStorePostIndex32());
-        RUN(testStorePostIndex64());
-    }
</del><ins>+    RUN(testStorePreIndex32());
+    RUN(testStorePreIndex64());
+    RUN(testStorePostIndex32());
+    RUN(testStorePostIndex64());
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> #endif // ENABLE(B3_JIT)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeOptionsListh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/OptionsList.h (281586 => 281587)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/OptionsList.h        2021-08-25 21:18:16 UTC (rev 281586)
+++ trunk/Source/JavaScriptCore/runtime/OptionsList.h   2021-08-25 21:19:31 UTC (rev 281587)
</span><span class="lines">@@ -437,7 +437,6 @@
</span><span class="cx">     v(Unsigned, maxB3TailDupBlockSize, 3, Normal, nullptr) \
</span><span class="cx">     v(Unsigned, maxB3TailDupBlockSuccessors, 3, Normal, nullptr) \
</span><span class="cx">     v(Bool, useB3HoistLoopInvariantValues, false, Normal, nullptr) \
</span><del>-    v(Bool, useB3CanonicalizePrePostIncrements, false, Normal, nullptr) \
</del><span class="cx">     \
</span><span class="cx">     v(Bool, useDollarVM, false, Restricted, "installs the $vm debugging tool in global objects") \
</span><span class="cx">     v(OptionString, functionOverrides, nullptr, Restricted, "file with debugging overrides for function bodies") \
</span></span></pre>
</div>
</div>

</body>
</html>