B3 trapping memory accesses should be documented
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Oct 2016 18:36:55 +0000 (18:36 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Oct 2016 18:36:55 +0000 (18:36 +0000)
https://bugs.webkit.org/show_bug.cgi?id=162845

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

While writing some documentation, I found some small holes in the code.

* b3/B3Effects.cpp:
(JSC::B3::Effects::operator==): Need this to write tests.
(JSC::B3::Effects::operator!=): Need this to write tests.
* b3/B3Effects.h:
* b3/B3HeapRange.h:
* b3/B3MemoryValue.cpp:
(JSC::B3::MemoryValue::dumpMeta): Sometimes the heap range dump won't show you the memory value's actual range. This makes the dump show you the actual range in that case.
* b3/B3Value.cpp:
(JSC::B3::Value::effects): While documenting this, I remembered that trapping also has to imply reading top. I fixed this.
* b3/testb3.cpp:
(JSC::B3::testTrappingLoad): Added checks for the effects of trapping loads.
(JSC::B3::testTrappingStore): Added checks for the effects of trapping stores.
(JSC::B3::testMoveConstants): Made this not crash with validation.

Websites/webkit.org:

Added documentation for the Traps flag, and factored out the documentation of the Chill flag
to a new flags section.

* docs/b3/intermediate-representation.html:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@206739 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3Effects.cpp
Source/JavaScriptCore/b3/B3Effects.h
Source/JavaScriptCore/b3/B3HeapRange.h
Source/JavaScriptCore/b3/B3MemoryValue.cpp
Source/JavaScriptCore/b3/B3Value.cpp
Source/JavaScriptCore/b3/testb3.cpp
Websites/webkit.org/ChangeLog
Websites/webkit.org/docs/b3/intermediate-representation.html

index 46e5a9a..accb7ec 100644 (file)
@@ -1,3 +1,26 @@
+2016-10-03  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 trapping memory accesses should be documented
+        https://bugs.webkit.org/show_bug.cgi?id=162845
+
+        Reviewed by Geoffrey Garen.
+        
+        While writing some documentation, I found some small holes in the code.
+
+        * b3/B3Effects.cpp:
+        (JSC::B3::Effects::operator==): Need this to write tests.
+        (JSC::B3::Effects::operator!=): Need this to write tests.
+        * b3/B3Effects.h:
+        * b3/B3HeapRange.h:
+        * b3/B3MemoryValue.cpp:
+        (JSC::B3::MemoryValue::dumpMeta): Sometimes the heap range dump won't show you the memory value's actual range. This makes the dump show you the actual range in that case.
+        * b3/B3Value.cpp:
+        (JSC::B3::Value::effects): While documenting this, I remembered that trapping also has to imply reading top. I fixed this.
+        * b3/testb3.cpp:
+        (JSC::B3::testTrappingLoad): Added checks for the effects of trapping loads.
+        (JSC::B3::testTrappingStore): Added checks for the effects of trapping stores.
+        (JSC::B3::testMoveConstants): Made this not crash with validation.
+
 2016-10-03  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [ES6] GeneratorFunction (a.k.a. GeneratorWrapperFunction)'s prototype object does not have constructor property
index dea0ece..a0d7517 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-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
@@ -76,6 +76,22 @@ bool Effects::interferes(const Effects& other) const
         || reads.overlaps(other.writes);
 }
 
+bool Effects::operator==(const Effects& other) const
+{
+    return terminal == other.terminal
+        && exitsSideways == other.exitsSideways
+        && controlDependent == other.controlDependent
+        && writesLocalState == other.writesLocalState
+        && readsLocalState == other.readsLocalState
+        && writes == other.writes
+        && reads == other.reads;
+}
+
+bool Effects::operator!=(const Effects& other) const
+{
+    return !(*this == other);
+}
+
 void Effects::dump(PrintStream& out) const
 {
     CommaPrinter comma("|");
index 720955f..c04748f 100644 (file)
@@ -86,8 +86,11 @@ struct Effects {
     // Returns true if reordering instructions with these respective effects would change program
     // behavior in an observable way.
     bool interferes(const Effects&) const;
+    
+    JS_EXPORT_PRIVATE bool operator==(const Effects&) const;
+    JS_EXPORT_PRIVATE bool operator!=(const Effects&) const;
 
-    void dump(PrintStream& out) const;
+    JS_EXPORT_PRIVATE void dump(PrintStream& out) const;
 };
 
 } } // namespace JSC::B3
index a7eac0c..03866bd 100644 (file)
@@ -98,7 +98,7 @@ public:
         return WTF::rangesOverlap(m_begin, m_end, other.m_begin, other.m_end);
     }
 
-    void dump(PrintStream& out) const;
+    JS_EXPORT_PRIVATE void dump(PrintStream& out) const;
 
 private:
     unsigned m_begin;
index 8f78714..3764b74 100644 (file)
@@ -59,6 +59,9 @@ void MemoryValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
 {
     if (m_offset)
         out.print(comma, "offset = ", m_offset);
+    if ((isLoad() && effects().reads != range())
+        || (isStore() && effects().writes != range()))
+        out.print(comma, "range = ", range());
 }
 
 Value* MemoryValue::cloneImpl() const
index f0b06e0..161aced 100644 (file)
@@ -635,7 +635,10 @@ Effects Value::effects() const
         result.terminal = true;
         break;
     }
-    result.exitsSideways |= traps();
+    if (traps()) {
+        result.exitsSideways = true;
+        result.reads = HeapRange::top();
+    }
     return result;
 }
 
index 1c9b981..f8648a0 100644 (file)
@@ -13113,11 +13113,19 @@ void testTrappingLoad()
     Procedure proc;
     BasicBlock* root = proc.addBlock();
     int x = 42;
-    root->appendNew<Value>(
-        proc, Return, Origin(),
-        root->appendNew<MemoryValue>(
-            proc, trapping(Load), Int32, Origin(),
-            root->appendNew<ConstPtrValue>(proc, Origin(), &x)));
+    MemoryValue* value = root->appendNew<MemoryValue>(
+        proc, trapping(Load), Int32, Origin(),
+        root->appendNew<ConstPtrValue>(proc, Origin(), &x));
+    Effects expectedEffects;
+    expectedEffects.exitsSideways = true;
+    expectedEffects.controlDependent= true;
+    expectedEffects.reads = HeapRange::top();
+    CHECK_EQ(value->range(), HeapRange::top());
+    CHECK_EQ(value->effects(), expectedEffects);
+    value->setRange(HeapRange(0));
+    CHECK_EQ(value->range(), HeapRange(0));
+    CHECK_EQ(value->effects(), expectedEffects); // We still reads top!
+    root->appendNew<Value>(proc, Return, Origin(), value);
     CHECK_EQ(compileAndRun<int>(proc), 42);
     unsigned trapsCount = 0;
     for (Air::BasicBlock* block : proc.code()) {
@@ -13134,10 +13142,21 @@ void testTrappingStore()
     Procedure proc;
     BasicBlock* root = proc.addBlock();
     int x = 42;
-    root->appendNew<MemoryValue>(
+    MemoryValue* value = root->appendNew<MemoryValue>(
         proc, trapping(Store), Origin(),
         root->appendNew<Const32Value>(proc, Origin(), 111),
         root->appendNew<ConstPtrValue>(proc, Origin(), &x));
+    Effects expectedEffects;
+    expectedEffects.exitsSideways = true;
+    expectedEffects.controlDependent= true;
+    expectedEffects.reads = HeapRange::top();
+    expectedEffects.writes = HeapRange::top();
+    CHECK_EQ(value->range(), HeapRange::top());
+    CHECK_EQ(value->effects(), expectedEffects);
+    value->setRange(HeapRange(0));
+    CHECK_EQ(value->range(), HeapRange(0));
+    expectedEffects.writes = HeapRange(0);
+    CHECK_EQ(value->effects(), expectedEffects); // We still reads top!
     root->appendNew<Value>(proc, Return, Origin());
     compileAndRun<int>(proc);
     CHECK_EQ(x, 111);
@@ -13258,10 +13277,10 @@ void testMoveConstants()
         Procedure proc;
         BasicBlock* root = proc.addBlock();
         Value* a = root->appendNew<MemoryValue>(
-            proc, Load, Int32, Origin(), 
+            proc, Load, pointerType(), Origin(), 
             root->appendNew<ConstPtrValue>(proc, Origin(), 0x123412341234));
         Value* b = root->appendNew<MemoryValue>(
-            proc, Load, Int32, Origin(),
+            proc, Load, pointerType(), Origin(),
             root->appendNew<ConstPtrValue>(proc, Origin(), 0x123412341334));
         root->appendNew<CCallValue>(proc, Void, Origin(), a, b);
         root->appendNew<Value>(proc, Return, Origin());
index 17b55a4..bf0cff1 100644 (file)
@@ -1,3 +1,15 @@
+2016-10-03  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 trapping memory accesses should be documented
+        https://bugs.webkit.org/show_bug.cgi?id=162845
+
+        Reviewed by Geoffrey Garen.
+        
+        Added documentation for the Traps flag, and factored out the documentation of the Chill flag
+        to a new flags section.
+
+        * docs/b3/intermediate-representation.html:
+
 2016-09-30  Filip Pizlo  <fpizlo@apple.com>
 
         Air should have a way of expressing additional instruction flags
index b1d3b2d..bdc57a1 100644 (file)
@@ -84,7 +84,8 @@
     
     <p>The value kind is a combination of an opcode and optional flags. The flags allow a single
       opcode to have many variants. For example, Div and Mod may have the Chill flag set to indicate
-      that they should not trap on corner cases.</p>
+      that they should not trap on corner cases. Alternatively, Load/Store opcodes may have the
+      Traps flag set to indicate that they should trap deterministically.</p>
     
     <p>Values also have a unique 32-bit index that is used as the name.</p>
     
       T)".  This means that the value must take two children of the same type and returns a
       value of that type.  We use the type IntPtr to mean either Int32, or Int64, depending on
       the platform.</p>
+    
+    <p>Some opcodes can have some flags set. A description of flags follows the description of
+      opcodes.</p>
 
     <h3>Opcode descriptions</h3>
 
         according to the IEEE 854 spec.</dd>
 
       <dt>T Div(T, T)</dt>
-      <dd>
-        <p>Works with any type except Void.  For integer types, this represents signed
-          division with round-to-zero.  By default, its behavior is undefined for x/0 or
-          -2<sup>31</sup>/-1.  For floating point types, this represents division according
-          to the IEEE 854 spec.</p>
-        <p>Integer Div may have the Chill flag set. You can create a Chill Div by saying
-          <code>chill(Div)</code> instead of <code>Div</code>; the former creates a Kind
-          that has Div as the opcode and has the Chill bit set. An operation is said to be
-          chill if it returns a sensible value whenever its non-chill form would have had
-          undefined behavior. Chill Div turns x/0 into 0 and -2<sup>31</sup>/-1 into
-          -2<sup>31</sup>. We recognize this in IR because it's exactly the semantics of
-          division on ARM64, and it's also exactly the semantics that JavaScript wants for
-          "(x/y)|0".</p>
-      </dd>
+      <dd>Works with any type except Void.  For integer types, this represents signed
+        division with round-to-zero.  By default, its behavior is undefined for x/0 or
+        -2<sup>31</sup>/-1.  For floating point types, this represents division according
+        to the IEEE 854 spec. Integer Div may have the Chill flag set.</dd>
 
       <dt>T Mod(T, T)</dt>
-      <dd>
-        <p>Works with any type except Void.  For integer types, this represents signed
-          modulo. By default, its behavior is undefined for x%0 or -2<sup>31</sup>%-1.  For
-          floating point types, this represents modulo according to "fmod()".</p>
-        <p>Integer Mod may have the Chill flag set. You can create a Chill Mod by saying
-          <code>chill(Mod)</code>. Chill Mod turns x%0 into 0 and -2<sup>31</sup>%-1 into
-          0.</p>
-      </dd>
+      <dd>Works with any type except Void.  For integer types, this represents signed
+        modulo. By default, its behavior is undefined for x%0 or -2<sup>31</sup>%-1.  For
+        floating point types, this represents modulo according to "fmod()". Integer Mod may have the
+        Chill flag set.</dd>
 
       <dt>T Neg(T)</dt>
       <dd>Works with any type except Void.  For integer types, this represents twos-complement
       <dt>Int32 Load8Z(IntPtr, offset)</dt>
       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
         signed integer offset to the child value.  Zero extends the loaded byte, so the high 24
-        bits are all zero.  Must use the MemoryValue class.</dd>
+        bits are all zero.  Must use the MemoryValue class.  May have the Traps flag set.</dd>
 
       <dt>Int32 Load8S(IntPtr, offset)</dt>
       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
         signed integer offset to the child value.  Sign extends the loaded byte.  Must use the
-        MemoryValue class.</dd>
+        MemoryValue class.  May have the Traps flag set.</dd>
 
       <dt>Int32 Load16Z(IntPtr, offset)</dt>
       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
         32-bit signed integer offset to the child value.  Zero extends the loaded 16-bit
         integer, so the high 16 bits are all zero.  Misaligned loads are not penalized.  Must
-        use the MemoryValue class.</dd>
+        use the MemoryValue class.  May have the Traps flag set.</dd>
 
       <dt>Int32 Load16S(IntPtr, offset)</dt>
       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
         32-bit signed integer offset to the child value.  Sign extends the loaded 16-bit
-        integer.  Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
+        integer.  Misaligned loads are not penalized.  Must use the MemoryValue class.  May have the
+        Traps flag set.</dd>
 
       <dt>T Load(IntPtr, offset)</dt>
       <dd>Valid for any type except Void.  Loads a value of that type from the address, which is
         computed by adding the compile-time 32-bit signed integer offset to the child value.
-        Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
+        Misaligned loads are not penalized.  Must use the MemoryValue class.  May have the Traps
+        flag set.</dd>
 
       <dt>Void Store8(Int32, IntPtr, offset)</dt>
       <dd>Stores a the low byte of the first child into the address computed by adding the
         compile-time 32-bit signed integer offset to the second child.  Must use the MemoryValue
-        class.</dd>
+        class.  May have the Traps flag set.</dd>
 
       <dt>Void Store16(Int32, IntPtr, offset)</dt>
       <dd>Stores a the low 16 bits of the first child into the address computed by adding the
         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
-        not penalized.  Must use the MemoryValue class.</dd>
+        not penalized.  Must use the MemoryValue class.  May have the Traps flag set.</dd>
 
       <dt>Void Store(T, IntPtr, offset)</dt>
       <dd>Stores the value in the first child into the address computed by adding the
         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
-        not penalized.  Must use the MemoryValue class.</dd>
+        not penalized.  Must use the MemoryValue class.  May have the Traps flag set.</dd>
       
       <dt>Void Fence()</dt>
       <dd>Abstracts standalone data fences on x86 and ARM. Must use the FenceValue class, which has
@@ -634,7 +626,46 @@ root->appendSuccessor(thirdEntrypoint);</code></pre>
         at the end of the basic block.  The block must have zero successors. Note that we also use
         the Oops opcode to mean "no such opcode" in some B3 transformations.</dd>
     </dl>
-
+    
+    <h2>Flags</h2>
+    
+    <p>This section describes flags. These may be set in
+      <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Kind.h"><code>Kind</code></a>.</p>
+    
+    <dl>
+      <dt>Chill</dt>
+      <dd><i>Applies to: Div, Mod.</i> You can create a chill Div/Mod by saying
+        <code>chill(Div)</code>. This creates a Kind that has the Chill flag set. This can only be
+        used with interer types. An operation is said to be chill if it returns a sensible value
+        whenever its non-chill form would have had undefined behavior. Chill Div turns x/0 into 0
+        and -2<sup>31</sup>/-1 into -2<sup>31</sup>. We recognize this in IR because it's exactly
+        the semantics of division on ARM64, and it's also exactly the semantics that JavaScript
+        wants for "(x/y)|0". Chill Mod turns x%0 into 0 and -2<sup>31</sup>%-1 into 0. This matches
+        the semantics of JavaScript "(x%y)|0".</dd>
+      
+      <dt>Traps</dt>
+      <dd><i>Applies to: Load8Z, Load8S, Load16Z, Load16S, Load, Store8, Store16, Store.</i> You can
+        create a trapping Kind from an opcode by saying <code>trapping(opcode)</code>. For example,
+        <code>trapping(Load)</code>. An operation is said to be trapping if it will cause a page
+        fault when used on an invalid pointer and this page fault will be observed. This means that
+        the compiler cannot fudge when the page fault happens. This is logically equivalent to what
+        B3 calls <code>Effects::exitsSideways</code>, but further implies that if any of the B3
+        values used to fuse an Air instruction were trapping, then the Air instruction must have its
+        <code>Air::Kind::traps</code> flag set. The compiler won't help you identify where you
+        trapped. Even if you use the compiler's origin facility to track down the trap location, you
+        may get the origin of any B3 value that was incorporated into the fused instruction that
+        caused the trap. For example, "Add(Load&lt;Traps&gt;(ptr), $1)" may claim to trap at the Add
+        rather than the Load on x86, because this pattern is a perfect candidate for add-load
+        fusion. Nevertheless, you are guaranteed to get the trap and the trap will be observed at
+        the point you intended. For example, the compiler will not hoist a trapping load past any
+        effects, even those outside of its read range, because the trap is presumed to read top. The
+        compiler will not attempt to DCE a trapping load. The compiler will not attempt to sink or
+        eliminate any trapping stores, even if they are dead because of a guaranteed subsequent
+        store to the same address, because we conservatively assume that the store was done for the
+        trap effect. This feature is meant to support high throughput memory safety checks in
+        WebAssembly.</dd>
+    </dl>
+    
   </div>
 </body>
 </html>