FTL should lower its abstract heaps to B3 heap ranges
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 28 Feb 2016 20:34:03 +0000 (20:34 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 28 Feb 2016 20:34:03 +0000 (20:34 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154782

Reviewed by Saam Barati.

The FTL can describe the abstract heaps (points-to sets) that a memory operation will
affect. The abstract heaps are arranged as a hierarchy. We used to transform this into
TBAA hierarchies in LLVM, but we never got around to wiring this up to B3's equivalent
notion - the HeapRange. That's what this patch fixes.

B3 has a minimalistic alias analysis. It represents abstract heaps using unsigned 32-bit
integers. There are 1<<32 abstract heaps. The B3 client can describe what an operation
affects by specifying a heap range: a begin...end pair that says that the operation
affects all abstract heaps H such that begin <= H < end.

This peculiar scheme was a deliberate attempt to distill what the abstract heap
hierarchy is all about. We can assign begin...end numbers to abstract heaps so that:

- A heap's end is greater than its begin.
- A heap's begin is greater than or equal to its parent's begin.
- A heap's end is less than or equal to its parent's end.

This is easy to do using a recursive traversal of the abstract heap hierarchy. I almost
went for the iterative traversal, which is a splendid algorithm, but it's totally
unnecessary here since we tightly control the height of the heap hierarchy.

Because abstract heaps are produced on-the-fly by FTL lowering, due to the fact that we
generate new ones for field names and constant indices we encounter, we can't actually
decorate the B3 instructions we create in lowering until all lowering is done. Adding a
new abstract heap to the hierarchy after ranges were already computed would require
updating the ranges of any heaps "to the right" of that heap in the hierarchy. This
patch solves that problem by recording the associations between abstract heaps and their
intended roles in the generated IR, and then decorating all of the relevant B3 values
after we compute the ranges of the hierarchy after lowering.

This is perf-neutral. I was hoping for a small speed-up, but I could not detect a
speed-up on any benchmark. That's not too surprising. We already have very precise CSE
in the DFG, so there aren't many opportunities left for the B3 CSE and it may have
already been getting the big ones even without alias analysis.

Even without a speed-up, this patch is valuable because it makes it easier to implement
other optimizations, like store elimination.

* b3/B3HeapRange.h:
(JSC::B3::HeapRange::HeapRange):
* ftl/FTLAbstractHeap.cpp:
(JSC::FTL::AbstractHeap::AbstractHeap):
(JSC::FTL::AbstractHeap::changeParent):
(JSC::FTL::AbstractHeap::compute):
(JSC::FTL::AbstractHeap::shallowDump):
(JSC::FTL::AbstractHeap::dump):
(JSC::FTL::AbstractHeap::deepDump):
(JSC::FTL::AbstractHeap::badRangeError):
(JSC::FTL::IndexedAbstractHeap::IndexedAbstractHeap):
(JSC::FTL::IndexedAbstractHeap::baseIndex):
(JSC::FTL::IndexedAbstractHeap::atSlow):
(JSC::FTL::IndexedAbstractHeap::initialize):
(JSC::FTL::AbstractHeap::decorateInstruction): Deleted.
(JSC::FTL::AbstractField::dump): Deleted.
* ftl/FTLAbstractHeap.h:
(JSC::FTL::AbstractHeap::AbstractHeap):
(JSC::FTL::AbstractHeap::isInitialized):
(JSC::FTL::AbstractHeap::initialize):
(JSC::FTL::AbstractHeap::parent):
(JSC::FTL::AbstractHeap::heapName):
(JSC::FTL::AbstractHeap::range):
(JSC::FTL::AbstractHeap::offset):
(JSC::FTL::IndexedAbstractHeap::atAnyIndex):
(JSC::FTL::IndexedAbstractHeap::at):
(JSC::FTL::IndexedAbstractHeap::operator[]):
(JSC::FTL::IndexedAbstractHeap::returnInitialized):
(JSC::FTL::IndexedAbstractHeap::WithoutZeroOrOneHashTraits::constructDeletedValue):
(JSC::FTL::IndexedAbstractHeap::WithoutZeroOrOneHashTraits::isDeletedValue):
(JSC::FTL::AbstractHeap::changeParent): Deleted.
(JSC::FTL::AbstractField::AbstractField): Deleted.
(JSC::FTL::AbstractField::initialize): Deleted.
(JSC::FTL::AbstractField::offset): Deleted.
* ftl/FTLAbstractHeapRepository.cpp:
(JSC::FTL::AbstractHeapRepository::AbstractHeapRepository):
(JSC::FTL::AbstractHeapRepository::~AbstractHeapRepository):
(JSC::FTL::AbstractHeapRepository::decorateMemory):
(JSC::FTL::AbstractHeapRepository::decorateCCallRead):
(JSC::FTL::AbstractHeapRepository::decorateCCallWrite):
(JSC::FTL::AbstractHeapRepository::decoratePatchpointRead):
(JSC::FTL::AbstractHeapRepository::decoratePatchpointWrite):
(JSC::FTL::AbstractHeapRepository::computeRangesAndDecorateInstructions):
* ftl/FTLAbstractHeapRepository.h:
(JSC::FTL::AbstractHeapRepository::forArrayType):
(JSC::FTL::AbstractHeapRepository::HeapForValue::HeapForValue):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::lower):
* ftl/FTLOutput.cpp:
(JSC::FTL::Output::load):
(JSC::FTL::Output::load8SignExt32):
(JSC::FTL::Output::load8ZeroExt32):
(JSC::FTL::Output::load16SignExt32):
(JSC::FTL::Output::load16ZeroExt32):
(JSC::FTL::Output::store):
(JSC::FTL::Output::store32As8):
(JSC::FTL::Output::store32As16):
(JSC::FTL::Output::baseIndex):
* ftl/FTLOutput.h:
(JSC::FTL::Output::address):
(JSC::FTL::Output::absolute):
(JSC::FTL::Output::load8SignExt32):
(JSC::FTL::Output::load8ZeroExt32):
(JSC::FTL::Output::load16SignExt32):
(JSC::FTL::Output::load16ZeroExt32):
(JSC::FTL::Output::load32):
(JSC::FTL::Output::load64):
(JSC::FTL::Output::loadPtr):
(JSC::FTL::Output::loadDouble):
(JSC::FTL::Output::store32):
(JSC::FTL::Output::store64):
(JSC::FTL::Output::storePtr):
(JSC::FTL::Output::storeDouble):
(JSC::FTL::Output::ascribeRange):
(JSC::FTL::Output::nonNegative32):
(JSC::FTL::Output::load32NonNegative):
(JSC::FTL::Output::equal):
(JSC::FTL::Output::notEqual):
* ftl/FTLTypedPointer.h:
(JSC::FTL::TypedPointer::operator!):
(JSC::FTL::TypedPointer::heap):
(JSC::FTL::TypedPointer::value):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3HeapRange.h
Source/JavaScriptCore/ftl/FTLAbstractHeap.cpp
Source/JavaScriptCore/ftl/FTLAbstractHeap.h
Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.cpp
Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/ftl/FTLOutput.cpp
Source/JavaScriptCore/ftl/FTLOutput.h
Source/JavaScriptCore/ftl/FTLTypedPointer.h

index f025a84..99826b0 100644 (file)
@@ -1,3 +1,131 @@
+2016-02-27  Filip Pizlo  <fpizlo@apple.com>
+
+        FTL should lower its abstract heaps to B3 heap ranges
+        https://bugs.webkit.org/show_bug.cgi?id=154782
+
+        Reviewed by Saam Barati.
+
+        The FTL can describe the abstract heaps (points-to sets) that a memory operation will
+        affect. The abstract heaps are arranged as a hierarchy. We used to transform this into
+        TBAA hierarchies in LLVM, but we never got around to wiring this up to B3's equivalent
+        notion - the HeapRange. That's what this patch fixes.
+
+        B3 has a minimalistic alias analysis. It represents abstract heaps using unsigned 32-bit
+        integers. There are 1<<32 abstract heaps. The B3 client can describe what an operation
+        affects by specifying a heap range: a begin...end pair that says that the operation
+        affects all abstract heaps H such that begin <= H < end.
+
+        This peculiar scheme was a deliberate attempt to distill what the abstract heap
+        hierarchy is all about. We can assign begin...end numbers to abstract heaps so that:
+
+        - A heap's end is greater than its begin.
+        - A heap's begin is greater than or equal to its parent's begin.
+        - A heap's end is less than or equal to its parent's end.
+
+        This is easy to do using a recursive traversal of the abstract heap hierarchy. I almost
+        went for the iterative traversal, which is a splendid algorithm, but it's totally
+        unnecessary here since we tightly control the height of the heap hierarchy.
+
+        Because abstract heaps are produced on-the-fly by FTL lowering, due to the fact that we
+        generate new ones for field names and constant indices we encounter, we can't actually
+        decorate the B3 instructions we create in lowering until all lowering is done. Adding a
+        new abstract heap to the hierarchy after ranges were already computed would require
+        updating the ranges of any heaps "to the right" of that heap in the hierarchy. This
+        patch solves that problem by recording the associations between abstract heaps and their
+        intended roles in the generated IR, and then decorating all of the relevant B3 values
+        after we compute the ranges of the hierarchy after lowering.
+
+        This is perf-neutral. I was hoping for a small speed-up, but I could not detect a
+        speed-up on any benchmark. That's not too surprising. We already have very precise CSE
+        in the DFG, so there aren't many opportunities left for the B3 CSE and it may have
+        already been getting the big ones even without alias analysis.
+
+        Even without a speed-up, this patch is valuable because it makes it easier to implement
+        other optimizations, like store elimination.
+
+        * b3/B3HeapRange.h:
+        (JSC::B3::HeapRange::HeapRange):
+        * ftl/FTLAbstractHeap.cpp:
+        (JSC::FTL::AbstractHeap::AbstractHeap):
+        (JSC::FTL::AbstractHeap::changeParent):
+        (JSC::FTL::AbstractHeap::compute):
+        (JSC::FTL::AbstractHeap::shallowDump):
+        (JSC::FTL::AbstractHeap::dump):
+        (JSC::FTL::AbstractHeap::deepDump):
+        (JSC::FTL::AbstractHeap::badRangeError):
+        (JSC::FTL::IndexedAbstractHeap::IndexedAbstractHeap):
+        (JSC::FTL::IndexedAbstractHeap::baseIndex):
+        (JSC::FTL::IndexedAbstractHeap::atSlow):
+        (JSC::FTL::IndexedAbstractHeap::initialize):
+        (JSC::FTL::AbstractHeap::decorateInstruction): Deleted.
+        (JSC::FTL::AbstractField::dump): Deleted.
+        * ftl/FTLAbstractHeap.h:
+        (JSC::FTL::AbstractHeap::AbstractHeap):
+        (JSC::FTL::AbstractHeap::isInitialized):
+        (JSC::FTL::AbstractHeap::initialize):
+        (JSC::FTL::AbstractHeap::parent):
+        (JSC::FTL::AbstractHeap::heapName):
+        (JSC::FTL::AbstractHeap::range):
+        (JSC::FTL::AbstractHeap::offset):
+        (JSC::FTL::IndexedAbstractHeap::atAnyIndex):
+        (JSC::FTL::IndexedAbstractHeap::at):
+        (JSC::FTL::IndexedAbstractHeap::operator[]):
+        (JSC::FTL::IndexedAbstractHeap::returnInitialized):
+        (JSC::FTL::IndexedAbstractHeap::WithoutZeroOrOneHashTraits::constructDeletedValue):
+        (JSC::FTL::IndexedAbstractHeap::WithoutZeroOrOneHashTraits::isDeletedValue):
+        (JSC::FTL::AbstractHeap::changeParent): Deleted.
+        (JSC::FTL::AbstractField::AbstractField): Deleted.
+        (JSC::FTL::AbstractField::initialize): Deleted.
+        (JSC::FTL::AbstractField::offset): Deleted.
+        * ftl/FTLAbstractHeapRepository.cpp:
+        (JSC::FTL::AbstractHeapRepository::AbstractHeapRepository):
+        (JSC::FTL::AbstractHeapRepository::~AbstractHeapRepository):
+        (JSC::FTL::AbstractHeapRepository::decorateMemory):
+        (JSC::FTL::AbstractHeapRepository::decorateCCallRead):
+        (JSC::FTL::AbstractHeapRepository::decorateCCallWrite):
+        (JSC::FTL::AbstractHeapRepository::decoratePatchpointRead):
+        (JSC::FTL::AbstractHeapRepository::decoratePatchpointWrite):
+        (JSC::FTL::AbstractHeapRepository::computeRangesAndDecorateInstructions):
+        * ftl/FTLAbstractHeapRepository.h:
+        (JSC::FTL::AbstractHeapRepository::forArrayType):
+        (JSC::FTL::AbstractHeapRepository::HeapForValue::HeapForValue):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::lower):
+        * ftl/FTLOutput.cpp:
+        (JSC::FTL::Output::load):
+        (JSC::FTL::Output::load8SignExt32):
+        (JSC::FTL::Output::load8ZeroExt32):
+        (JSC::FTL::Output::load16SignExt32):
+        (JSC::FTL::Output::load16ZeroExt32):
+        (JSC::FTL::Output::store):
+        (JSC::FTL::Output::store32As8):
+        (JSC::FTL::Output::store32As16):
+        (JSC::FTL::Output::baseIndex):
+        * ftl/FTLOutput.h:
+        (JSC::FTL::Output::address):
+        (JSC::FTL::Output::absolute):
+        (JSC::FTL::Output::load8SignExt32):
+        (JSC::FTL::Output::load8ZeroExt32):
+        (JSC::FTL::Output::load16SignExt32):
+        (JSC::FTL::Output::load16ZeroExt32):
+        (JSC::FTL::Output::load32):
+        (JSC::FTL::Output::load64):
+        (JSC::FTL::Output::loadPtr):
+        (JSC::FTL::Output::loadDouble):
+        (JSC::FTL::Output::store32):
+        (JSC::FTL::Output::store64):
+        (JSC::FTL::Output::storePtr):
+        (JSC::FTL::Output::storeDouble):
+        (JSC::FTL::Output::ascribeRange):
+        (JSC::FTL::Output::nonNegative32):
+        (JSC::FTL::Output::load32NonNegative):
+        (JSC::FTL::Output::equal):
+        (JSC::FTL::Output::notEqual):
+        * ftl/FTLTypedPointer.h:
+        (JSC::FTL::TypedPointer::operator!):
+        (JSC::FTL::TypedPointer::heap):
+        (JSC::FTL::TypedPointer::value):
+
 2016-02-28  Skachkov Oleksandr  <gskachkov@gmail.com>
 
         [ES6] Arrow function syntax. Emit loading&putting this/super only if they are used in arrow function
index 7ab5196..80f18ff 100644 (file)
@@ -37,6 +37,12 @@ namespace JSC { namespace B3 {
 // Alias analysis in B3 is done by checking if two integer ranges overlap. This is powerful enough
 // to be used for TBAA-style alias analysis used by the DFG, FTL, and LLVM: you just turn each node
 // in the tree of abstract heaps into a pre/post range.
+//
+// Note that the 'begin' is inclusive, while the 'end' is exclusive. These two ranges are non-
+// overlapping:
+//
+//     rangeA = 0...8
+//     rangeB = 8...16
 
 class HeapRange {
 public:
@@ -48,6 +54,13 @@ public:
     {
     }
 
+    explicit HeapRange(unsigned value)
+        : m_begin(value)
+        , m_end(value + 1)
+    {
+        ASSERT(m_end >= m_begin);
+    }
+
     HeapRange(unsigned begin, unsigned end)
         : m_begin(begin)
         , m_end(end)
index e72f35f..90211fd 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 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
 
 namespace JSC { namespace FTL {
 
-void AbstractHeap::decorateInstruction(LValue instruction, const AbstractHeapRepository& repository) const
+using namespace B3;
+
+AbstractHeap::AbstractHeap(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
+    : m_offset(offset)
+    , m_heapName(heapName)
 {
-    UNUSED_PARAM(instruction);
-    UNUSED_PARAM(repository);
+    changeParent(parent);
+}
+
+void AbstractHeap::changeParent(AbstractHeap* parent)
+{
+    if (m_parent) {
+        bool result = m_parent->m_children.removeFirst(this);
+        RELEASE_ASSERT(result);
+    }
+
+    m_parent = parent;
+
+    if (parent) {
+        ASSERT(!m_parent->m_children.contains(this));
+        m_parent->m_children.append(this);
+    }
+}
+
+void AbstractHeap::compute(unsigned begin)
+{
+    // This recursively computes the ranges of the tree. This solves the following constraints
+    // in linear time:
+    //
+    // - A node's end is greater than its begin.
+    // - A node's begin is greater than or equal to its parent's begin.
+    // - A node's end is less than or equal to its parent's end.
+    // - The ranges are as small as possible.
+    //
+    // It's OK to recurse because we keep the depth of our abstract heap hierarchy fairly sane.
+    // I think that it gets 4 deep at most.
+
+    if (m_children.isEmpty()) {
+        // Must special-case leaves so that they use just one slot on the number line.
+        m_range = HeapRange(begin);
+        return;
+    }
+
+    unsigned current = begin;
+    for (AbstractHeap* child : m_children) {
+        child->compute(current);
+        current = child->range().end();
+    }
+
+    m_range = HeapRange(begin, current);
+}
+
+void AbstractHeap::shallowDump(PrintStream& out) const
+{
+    out.print(heapName(), "(", m_offset, ")");
+    if (m_range)
+        out.print("<", m_range, ">");
 }
 
 void AbstractHeap::dump(PrintStream& out) const
 {
-    out.print(heapName());
+    shallowDump(out);
     if (m_parent)
         out.print("->", *m_parent);
 }
 
-void AbstractField::dump(PrintStream& out) const
+void AbstractHeap::deepDump(PrintStream& out, unsigned indent) const
 {
-    out.print(heapName(), "(", m_offset, ")");
-    if (parent())
-        out.print("->", *parent());
+    auto printIndent = [&] () {
+        for (unsigned i = indent; i--;)
+            out.print("    ");
+    };
+
+    printIndent();
+    shallowDump(out);
+
+    if (m_children.isEmpty()) {
+        out.print("\n");
+        return;
+    }
+
+    out.print(":\n");
+    for (AbstractHeap* child : m_children)
+        child->deepDump(out, indent + 1);
+}
+
+void AbstractHeap::badRangeError() const
+{
+    dataLog("Heap does not have range: ", *this, "\n");
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 IndexedAbstractHeap::IndexedAbstractHeap(AbstractHeap* parent, const char* heapName, ptrdiff_t offset, size_t elementSize)
@@ -80,23 +152,23 @@ TypedPointer IndexedAbstractHeap::baseIndex(Output& out, LValue base, LValue ind
     return TypedPointer(atAnyIndex(), out.addPtr(result, m_offset + offset));
 }
 
-const AbstractField& IndexedAbstractHeap::atSlow(ptrdiff_t index)
+const AbstractHeap& IndexedAbstractHeap::atSlow(ptrdiff_t index)
 {
     ASSERT(static_cast<size_t>(index) >= m_smallIndices.size());
     
     if (UNLIKELY(!m_largeIndices))
         m_largeIndices = std::make_unique<MapType>();
 
-    std::unique_ptr<AbstractField>& field = m_largeIndices->add(index, nullptr).iterator->value;
+    std::unique_ptr<AbstractHeap>& field = m_largeIndices->add(index, nullptr).iterator->value;
     if (!field) {
-        field = std::make_unique<AbstractField>();
+        field = std::make_unique<AbstractHeap>();
         initialize(*field, index);
     }
 
     return *field;
 }
 
-void IndexedAbstractHeap::initialize(AbstractField& field, ptrdiff_t signedIndex)
+void IndexedAbstractHeap::initialize(AbstractHeap& field, ptrdiff_t signedIndex)
 {
     // Build up a name of the form:
     //
@@ -115,9 +187,10 @@ void IndexedAbstractHeap::initialize(AbstractField& field, ptrdiff_t signedIndex
     //
     //    Blah_neg_A
     //
-    // This used to be important because we used to use the string to distinguish the types. This is
-    // not relevant anymore, and this code will be removed eventually.
-    // FIXME: https://bugs.webkit.org/show_bug.cgi?id=154319
+    // This naming convention comes from our previous use of LLVM. It's not clear that we need
+    // it anymore, though it is sort of nifty. Basically, B3 doesn't need string names for
+    // abstract heaps, but the fact that we have a reasonably efficient way to always name the
+    // heaps will probably come in handy for debugging.
     
     static const char* negSplit = "_neg_";
     static const char* posSplit = "_";
index 07668cf..9b17868 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 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
@@ -28,6 +28,7 @@
 
 #if ENABLE(FTL_JIT)
 
+#include "B3HeapRange.h"
 #include "FTLAbbreviatedTypes.h"
 #include "JSCJSValue.h"
 #include <array>
 
 namespace JSC { namespace FTL {
 
-// This is here because we used to generate LLVM's TBAA. In the future we will want to generate
-// B3 HeapRanges instead.
-// FIXME: https://bugs.webkit.org/show_bug.cgi?id=154319
-
 class AbstractHeapRepository;
 class Output;
 class TypedPointer;
@@ -51,35 +48,29 @@ class AbstractHeap {
     WTF_MAKE_NONCOPYABLE(AbstractHeap); WTF_MAKE_FAST_ALLOCATED;
 public:
     AbstractHeap()
-        : m_parent(0)
-        , m_heapName(0)
-    {
-    }
-    
-    AbstractHeap(AbstractHeap* parent, const char* heapName)
-        : m_parent(parent)
-        , m_heapName(heapName)
     {
     }
     
+    AbstractHeap(AbstractHeap* parent, const char* heapName, ptrdiff_t offset = 0);
+
     bool isInitialized() const { return !!m_heapName; }
     
-    void initialize(AbstractHeap* parent, const char* heapName)
+    void initialize(AbstractHeap* parent, const char* heapName, ptrdiff_t offset = 0)
     {
-        m_parent = parent;
+        changeParent(parent);
         m_heapName = heapName;
+        m_offset = offset;
     }
     
-    void changeParent(AbstractHeap* parent)
-    {
-        m_parent = parent;
-    }
+    void changeParent(AbstractHeap* parent);
 
     AbstractHeap* parent() const
     {
         ASSERT(isInitialized());
         return m_parent;
     }
+
+    const Vector<AbstractHeap*>& children() const;
     
     const char* heapName() const
     {
@@ -87,47 +78,44 @@ public:
         return m_heapName;
     }
 
-    void decorateInstruction(LValue instruction, const AbstractHeapRepository&) const;
-
-    void dump(PrintStream&) const;
-
-private:
-    friend class AbstractHeapRepository;
-
-    AbstractHeap* m_parent;
-    const char* m_heapName;
-};
-
-// Think of "AbstractField" as being an "AbstractHeapWithOffset". I would have named
-// it the latter except that I don't like typing that much.
-class AbstractField : public AbstractHeap {
-public:
-    AbstractField()
+    B3::HeapRange range() const
     {
+        // This will not have a valid value until after all lowering is done. Do associate an
+        // AbstractHeap with a B3::Value*, use AbstractHeapRepository::decorateXXX().
+        if (!m_range)
+            badRangeError();
+        
+        return m_range;
     }
-    
-    AbstractField(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
-        : AbstractHeap(parent, heapName)
-        , m_offset(offset)
-    {
-    }
-    
-    void initialize(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
-    {
-        AbstractHeap::initialize(parent, heapName);
-        m_offset = offset;
-    }
-    
+
+    // WARNING: Not all abstract heaps have a meaningful offset.
     ptrdiff_t offset() const
     {
         ASSERT(isInitialized());
         return m_offset;
     }
-    
+
+    void compute(unsigned begin = 0);
+
+    // Print information about just this heap.
+    void shallowDump(PrintStream&) const;
+
+    // Print information about this heap and its ancestors. This is the default.
     void dump(PrintStream&) const;
 
+    // Print information about this heap and its descendents. This is a multi-line dump.
+    void deepDump(PrintStream&, unsigned indent = 0) const;
+
 private:
-    ptrdiff_t m_offset;
+    friend class AbstractHeapRepository;
+
+    NO_RETURN_DUE_TO_CRASH void badRangeError() const;
+
+    AbstractHeap* m_parent { nullptr };
+    Vector<AbstractHeap*> m_children;
+    intptr_t m_offset { 0 };
+    B3::HeapRange m_range;
+    const char* m_heapName { nullptr };
 };
 
 class IndexedAbstractHeap {
@@ -137,41 +125,41 @@ public:
     
     const AbstractHeap& atAnyIndex() const { return m_heapForAnyIndex; }
     
-    const AbstractField& at(ptrdiff_t index)
+    const AbstractHeap& at(ptrdiff_t index)
     {
         if (static_cast<size_t>(index) < m_smallIndices.size())
             return returnInitialized(m_smallIndices[index], index);
         return atSlow(index);
     }
     
-    const AbstractField& operator[](ptrdiff_t index) { return at(index); }
+    const AbstractHeap& operator[](ptrdiff_t index) { return at(index); }
     
     TypedPointer baseIndex(Output& out, LValue base, LValue index, JSValue indexAsConstant = JSValue(), ptrdiff_t offset = 0);
     
     void dump(PrintStream&) const;
 
 private:
-    const AbstractField& returnInitialized(AbstractField& field, ptrdiff_t index)
+    const AbstractHeap& returnInitialized(AbstractHeap& field, ptrdiff_t index)
     {
         if (UNLIKELY(!field.isInitialized()))
             initialize(field, index);
         return field;
     }
 
-    const AbstractField& atSlow(ptrdiff_t index);
-    void initialize(AbstractField& field, ptrdiff_t index);
+    const AbstractHeap& atSlow(ptrdiff_t index);
+    void initialize(AbstractHeap& field, ptrdiff_t index);
 
     AbstractHeap m_heapForAnyIndex;
     size_t m_heapNameLength;
     ptrdiff_t m_offset;
     size_t m_elementSize;
-    std::array<AbstractField, 16> m_smallIndices;
+    std::array<AbstractHeap, 16> m_smallIndices;
     
     struct WithoutZeroOrOneHashTraits : WTF::GenericHashTraits<ptrdiff_t> {
         static void constructDeletedValue(ptrdiff_t& slot) { slot = 1; }
         static bool isDeletedValue(ptrdiff_t value) { return value == 1; }
     };
-    typedef HashMap<ptrdiff_t, std::unique_ptr<AbstractField>, WTF::IntHash<ptrdiff_t>, WithoutZeroOrOneHashTraits> MapType;
+    typedef HashMap<ptrdiff_t, std::unique_ptr<AbstractHeap>, WTF::IntHash<ptrdiff_t>, WithoutZeroOrOneHashTraits> MapType;
     
     std::unique_ptr<MapType> m_largeIndices;
     Vector<CString, 16> m_largeIndexNames;
index 6026a04..a8d215d 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-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
 
 #if ENABLE(FTL_JIT)
 
+#include "B3CCallValue.h"
+#include "B3MemoryValue.h"
+#include "B3PatchpointValue.h"
+#include "B3ValueInlines.h"
 #include "DirectArguments.h"
+#include "FTLState.h"
 #include "GetterSetter.h"
 #include "JSEnvironmentRecord.h"
 #include "JSPropertyNameEnumerator.h"
 
 namespace JSC { namespace FTL {
 
+using namespace B3;
+
 AbstractHeapRepository::AbstractHeapRepository()
-    : root(0, "jscRoot")
+    : root(nullptr, "jscRoot")
 
 #define ABSTRACT_HEAP_INITIALIZATION(name) , name(&root, #name)
     FOR_EACH_ABSTRACT_HEAP(ABSTRACT_HEAP_INITIALIZATION)
@@ -80,6 +87,52 @@ AbstractHeapRepository::~AbstractHeapRepository()
 {
 }
 
+void AbstractHeapRepository::decorateMemory(const AbstractHeap* heap, Value* value)
+{
+    m_heapForMemory.append(HeapForValue(heap, value));
+}
+
+void AbstractHeapRepository::decorateCCallRead(const AbstractHeap* heap, Value* value)
+{
+    m_heapForCCallRead.append(HeapForValue(heap, value));
+}
+
+void AbstractHeapRepository::decorateCCallWrite(const AbstractHeap* heap, Value* value)
+{
+    m_heapForCCallWrite.append(HeapForValue(heap, value));
+}
+
+void AbstractHeapRepository::decoratePatchpointRead(const AbstractHeap* heap, Value* value)
+{
+    m_heapForPatchpointRead.append(HeapForValue(heap, value));
+}
+
+void AbstractHeapRepository::decoratePatchpointWrite(const AbstractHeap* heap, Value* value)
+{
+    m_heapForPatchpointWrite.append(HeapForValue(heap, value));
+}
+
+void AbstractHeapRepository::computeRangesAndDecorateInstructions()
+{
+    root.compute();
+
+    if (verboseCompilationEnabled()) {
+        dataLog("Abstract Heap Repository:\n");
+        root.deepDump(WTF::dataFile());
+    }
+
+    for (HeapForValue entry : m_heapForMemory)
+        entry.value->as<MemoryValue>()->setRange(entry.heap->range());
+    for (HeapForValue entry : m_heapForCCallRead)
+        entry.value->as<CCallValue>()->effects.reads = entry.heap->range();
+    for (HeapForValue entry : m_heapForCCallWrite)
+        entry.value->as<CCallValue>()->effects.writes = entry.heap->range();
+    for (HeapForValue entry : m_heapForPatchpointRead)
+        entry.value->as<CCallValue>()->effects.reads = entry.heap->range();
+    for (HeapForValue entry : m_heapForPatchpointWrite)
+        entry.value->as<CCallValue>()->effects.writes = entry.heap->range();
+}
+
 } } // namespace JSC::FTL
 
 #endif // ENABLE(FTL_JIT)
index 8c9f22a..99e5148 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-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
@@ -28,6 +28,7 @@
 
 #if ENABLE(FTL_JIT)
 
+#include "B3Value.h"
 #include "DFGArrayMode.h"
 #include "FTLAbstractHeap.h"
 #include "IndexingType.h"
@@ -127,11 +128,11 @@ public:
     FOR_EACH_ABSTRACT_HEAP(ABSTRACT_HEAP_DECLARATION)
 #undef ABSTRACT_HEAP_DECLARATION
 
-#define ABSTRACT_FIELD_DECLARATION(name, offset) AbstractField name;
+#define ABSTRACT_FIELD_DECLARATION(name, offset) AbstractHeap name;
     FOR_EACH_ABSTRACT_FIELD(ABSTRACT_FIELD_DECLARATION)
 #undef ABSTRACT_FIELD_DECLARATION
     
-    AbstractField& JSCell_freeListNext;
+    AbstractHeap& JSCell_freeListNext;
     
 #define INDEXED_ABSTRACT_HEAP_DECLARATION(name, offset, size) IndexedAbstractHeap name;
     FOR_EACH_INDEXED_ABSTRACT_HEAP(INDEXED_ABSTRACT_HEAP_DECLARATION)
@@ -186,8 +187,36 @@ public:
         }
     }
 
+    void decorateMemory(const AbstractHeap*, B3::Value*);
+    void decorateCCallRead(const AbstractHeap*, B3::Value*);
+    void decorateCCallWrite(const AbstractHeap*, B3::Value*);
+    void decoratePatchpointRead(const AbstractHeap*, B3::Value*);
+    void decoratePatchpointWrite(const AbstractHeap*, B3::Value*);
+
+    void computeRangesAndDecorateInstructions();
+
 private:
-    friend class AbstractHeap;
+
+    struct HeapForValue {
+        HeapForValue()
+        {
+        }
+
+        HeapForValue(const AbstractHeap* heap, B3::Value* value)
+            : heap(heap)
+            , value(value)
+        {
+        }
+        
+        const AbstractHeap* heap { nullptr };
+        B3::Value* value { nullptr };
+    };
+
+    Vector<HeapForValue> m_heapForMemory;
+    Vector<HeapForValue> m_heapForCCallRead;
+    Vector<HeapForValue> m_heapForCCallWrite;
+    Vector<HeapForValue> m_heapForPatchpointRead;
+    Vector<HeapForValue> m_heapForPatchpointWrite;
 };
 
 } } // namespace JSC::FTL
index ba51001..13113c6 100644 (file)
@@ -279,6 +279,12 @@ public:
         for (DFG::BasicBlock* block : preOrder)
             compileBlock(block);
 
+        // Make sure everything is decorated. This does a bunch of deferred decorating. This has
+        // to happen last because our abstract heaps are generated lazily. They have to be
+        // generated lazily because we have an infiniten number of numbered, indexed, and
+        // absolute heaps. We only become aware of the ones we actually mention while lowering.
+        m_heaps.computeRangesAndDecorateInstructions();
+
         // We create all Phi's up front, but we may then decide not to compile the basic block
         // that would have contained one of them. So this creates orphans, which triggers B3
         // validation failures. Calling this fixes the issue.
index d731c2c..b4ae275 100644 (file)
@@ -102,7 +102,7 @@ LValue Output::logicalNot(LValue value)
 LValue Output::load(TypedPointer pointer, LType type)
 {
     LValue load = m_block->appendNew<MemoryValue>(m_proc, Load, type, origin(), pointer.value());
-    pointer.heap().decorateInstruction(load, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), load);
     return load;
 }
 
@@ -153,47 +153,47 @@ LValue Output::unsignedToDouble(LValue value)
 LValue Output::load8SignExt32(TypedPointer pointer)
 {
     LValue load = m_block->appendNew<MemoryValue>(m_proc, Load8S, Int32, origin(), pointer.value());
-    pointer.heap().decorateInstruction(load, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), load);
     return load;
 }
 
 LValue Output::load8ZeroExt32(TypedPointer pointer)
 {
     LValue load = m_block->appendNew<MemoryValue>(m_proc, Load8Z, Int32, origin(), pointer.value());
-    pointer.heap().decorateInstruction(load, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), load);
     return load;
 }
 
 LValue Output::load16SignExt32(TypedPointer pointer)
 {
     LValue load = m_block->appendNew<MemoryValue>(m_proc, Load16S, Int32, origin(), pointer.value());
-    pointer.heap().decorateInstruction(load, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), load);
     return load;
 }
 
 LValue Output::load16ZeroExt32(TypedPointer pointer)
 {
     LValue load = m_block->appendNew<MemoryValue>(m_proc, Load16Z, Int32, origin(), pointer.value());
-    pointer.heap().decorateInstruction(load, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), load);
     return load;
 }
 
 void Output::store(LValue value, TypedPointer pointer)
 {
     LValue store = m_block->appendNew<MemoryValue>(m_proc, Store, origin(), value, pointer.value());
-    pointer.heap().decorateInstruction(store, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), store);
 }
 
 void Output::store32As8(LValue value, TypedPointer pointer)
 {
     LValue store = m_block->appendNew<MemoryValue>(m_proc, Store8, origin(), value, pointer.value());
-    pointer.heap().decorateInstruction(store, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), store);
 }
 
 void Output::store32As16(LValue value, TypedPointer pointer)
 {
     LValue store = m_block->appendNew<MemoryValue>(m_proc, Store16, origin(), value, pointer.value());
-    pointer.heap().decorateInstruction(store, *m_heaps);
+    m_heaps->decorateMemory(pointer.heap(), store);
 }
 
 LValue Output::baseIndex(LValue base, LValue index, Scale scale, ptrdiff_t offset)
index 10cf8e4..78a5ca5 100644 (file)
@@ -289,7 +289,7 @@ public:
     // Construct an address by offsetting base by the amount specified by the field,
     // and optionally an additional amount (use this with care), and then creating
     // a TypedPointer with the given field as the heap.
-    TypedPointer address(LValue base, const AbstractField& field, ptrdiff_t offset = 0)
+    TypedPointer address(LValue base, const AbstractHeap& field, ptrdiff_t offset = 0)
     {
         return address(field, base, offset + field.offset());
     }
@@ -310,18 +310,18 @@ public:
         return TypedPointer(m_heaps->absolute[address], constIntPtr(address));
     }
 
-    LValue load8SignExt32(LValue base, const AbstractField& field) { return load8SignExt32(address(base, field)); }
-    LValue load8ZeroExt32(LValue base, const AbstractField& field) { return load8ZeroExt32(address(base, field)); }
-    LValue load16SignExt32(LValue base, const AbstractField& field) { return load16SignExt32(address(base, field)); }
-    LValue load16ZeroExt32(LValue base, const AbstractField& field) { return load16ZeroExt32(address(base, field)); }
-    LValue load32(LValue base, const AbstractField& field) { return load32(address(base, field)); }
-    LValue load64(LValue base, const AbstractField& field) { return load64(address(base, field)); }
-    LValue loadPtr(LValue base, const AbstractField& field) { return loadPtr(address(base, field)); }
-    LValue loadDouble(LValue base, const AbstractField& field) { return loadDouble(address(base, field)); }
-    void store32(LValue value, LValue base, const AbstractField& field) { store32(value, address(base, field)); }
-    void store64(LValue value, LValue base, const AbstractField& field) { store64(value, address(base, field)); }
-    void storePtr(LValue value, LValue base, const AbstractField& field) { storePtr(value, address(base, field)); }
-    void storeDouble(LValue value, LValue base, const AbstractField& field) { storeDouble(value, address(base, field)); }
+    LValue load8SignExt32(LValue base, const AbstractHeap& field) { return load8SignExt32(address(base, field)); }
+    LValue load8ZeroExt32(LValue base, const AbstractHeap& field) { return load8ZeroExt32(address(base, field)); }
+    LValue load16SignExt32(LValue base, const AbstractHeap& field) { return load16SignExt32(address(base, field)); }
+    LValue load16ZeroExt32(LValue base, const AbstractHeap& field) { return load16ZeroExt32(address(base, field)); }
+    LValue load32(LValue base, const AbstractHeap& field) { return load32(address(base, field)); }
+    LValue load64(LValue base, const AbstractHeap& field) { return load64(address(base, field)); }
+    LValue loadPtr(LValue base, const AbstractHeap& field) { return loadPtr(address(base, field)); }
+    LValue loadDouble(LValue base, const AbstractHeap& field) { return loadDouble(address(base, field)); }
+    void store32(LValue value, LValue base, const AbstractHeap& field) { store32(value, address(base, field)); }
+    void store64(LValue value, LValue base, const AbstractHeap& field) { store64(value, address(base, field)); }
+    void storePtr(LValue value, LValue base, const AbstractHeap& field) { storePtr(value, address(base, field)); }
+    void storeDouble(LValue value, LValue base, const AbstractHeap& field) { storeDouble(value, address(base, field)); }
 
     // FIXME: Explore adding support for value range constraints to B3. Maybe it could be as simple as having
     // a load instruction that guarantees that its result is non-negative.
@@ -329,7 +329,7 @@ public:
     void ascribeRange(LValue, const ValueRange&) { }
     LValue nonNegative32(LValue loadInstruction) { return loadInstruction; }
     LValue load32NonNegative(TypedPointer pointer) { return load32(pointer); }
-    LValue load32NonNegative(LValue base, const AbstractField& field) { return load32(base, field); }
+    LValue load32NonNegative(LValue base, const AbstractHeap& field) { return load32(base, field); }
 
     LValue equal(LValue left, LValue right) { return m_block->appendNew<B3::Value>(m_proc, B3::Equal, origin(), left, right); }
     LValue notEqual(LValue left, LValue right) { return m_block->appendNew<B3::Value>(m_proc, B3::NotEqual, origin(), left, right); }
index d22faba..e39c3d8 100644 (file)
@@ -53,7 +53,7 @@ public:
         return !m_heap;
     }
     
-    const AbstractHeap& heap() const { return *m_heap; }
+    const AbstractHeap* heap() const { return m_heap; }
     LValue value() const { return m_value; }
 
 private: