[JSC] Reduce the memory usage of BytecodeLivenessAnalysis
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 24 Aug 2015 06:18:42 +0000 (06:18 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 24 Aug 2015 06:18:42 +0000 (06:18 +0000)
https://bugs.webkit.org/show_bug.cgi?id=148353

Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-08-23
Reviewed by Darin Adler.

BytecodeLivenessAnalysis easily takes kilobytes of memory for
non trivial blocks and that memory sticks around because
it stored on CodeBlock.

This patch reduces that memory use a bit.

Most of the memory is in the array of BytecodeBasicBlock.
BytecodeBasicBlock is shrunk by:
-Making it not ref-counted.
-Removing m_predecessors, it was only used for debugging and
 is usually big.
-Added a shrinkToFit() phase to shrink the vectors once we are
 done building the BytecodeBasicBlock.

There are more things we should do in the future:
-Store all the BytecodeBasicBlock direclty in the array.
 We know the size ahead of time, this would be a pure win.
 The only tricky part is changing m_successors to have the
 index of the successor instead of a pointer.
-Stop putting duplicates in m_successors.

* bytecode/BytecodeBasicBlock.cpp:
(JSC::computeBytecodeBasicBlocks):
(JSC::BytecodeBasicBlock::shrinkToFit): Deleted.
(JSC::linkBlocks): Deleted.
* bytecode/BytecodeBasicBlock.h:
(JSC::BytecodeBasicBlock::addSuccessor):
(JSC::BytecodeBasicBlock::addPredecessor): Deleted.
(JSC::BytecodeBasicBlock::predecessors): Deleted.
* bytecode/BytecodeLivenessAnalysis.cpp:
(JSC::getLeaderOffsetForBasicBlock):
(JSC::findBasicBlockWithLeaderOffset):
(JSC::findBasicBlockForBytecodeOffset):
(JSC::stepOverInstruction):
(JSC::computeLocalLivenessForBytecodeOffset):
(JSC::computeLocalLivenessForBlock):
(JSC::BytecodeLivenessAnalysis::dumpResults): Deleted.
* bytecode/BytecodeLivenessAnalysis.h:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/BytecodeBasicBlock.cpp
Source/JavaScriptCore/bytecode/BytecodeBasicBlock.h
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.h
Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp
Source/JavaScriptCore/bytecode/PreciseJumpTargets.h

index d008baf..1099dda 100644 (file)
@@ -1,3 +1,49 @@
+2015-08-23  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Reduce the memory usage of BytecodeLivenessAnalysis
+        https://bugs.webkit.org/show_bug.cgi?id=148353
+
+        Reviewed by Darin Adler.
+
+        BytecodeLivenessAnalysis easily takes kilobytes of memory for
+        non trivial blocks and that memory sticks around because
+        it stored on CodeBlock.
+
+        This patch reduces that memory use a bit.
+
+        Most of the memory is in the array of BytecodeBasicBlock.
+        BytecodeBasicBlock is shrunk by:
+        -Making it not ref-counted.
+        -Removing m_predecessors, it was only used for debugging and
+         is usually big.
+        -Added a shrinkToFit() phase to shrink the vectors once we are
+         done building the BytecodeBasicBlock.
+
+        There are more things we should do in the future:
+        -Store all the BytecodeBasicBlock direclty in the array.
+         We know the size ahead of time, this would be a pure win.
+         The only tricky part is changing m_successors to have the
+         index of the successor instead of a pointer.
+        -Stop putting duplicates in m_successors.
+
+        * bytecode/BytecodeBasicBlock.cpp:
+        (JSC::computeBytecodeBasicBlocks):
+        (JSC::BytecodeBasicBlock::shrinkToFit): Deleted.
+        (JSC::linkBlocks): Deleted.
+        * bytecode/BytecodeBasicBlock.h:
+        (JSC::BytecodeBasicBlock::addSuccessor):
+        (JSC::BytecodeBasicBlock::addPredecessor): Deleted.
+        (JSC::BytecodeBasicBlock::predecessors): Deleted.
+        * bytecode/BytecodeLivenessAnalysis.cpp:
+        (JSC::getLeaderOffsetForBasicBlock):
+        (JSC::findBasicBlockWithLeaderOffset):
+        (JSC::findBasicBlockForBytecodeOffset):
+        (JSC::stepOverInstruction):
+        (JSC::computeLocalLivenessForBytecodeOffset):
+        (JSC::computeLocalLivenessForBlock):
+        (JSC::BytecodeLivenessAnalysis::dumpResults): Deleted.
+        * bytecode/BytecodeLivenessAnalysis.h:
+
 2015-08-23  Geoffrey Garen  <ggaren@apple.com>
 
         Unreviewed, rolling back in r188792.
index 961eadb..54dfd16 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2015 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 {
 
+void BytecodeBasicBlock::shrinkToFit()
+{
+    m_bytecodeOffsets.shrinkToFit();
+    m_successors.shrinkToFit();
+}
+
 static bool isBranch(OpcodeID opcodeID)
 {
     switch (opcodeID) {
@@ -91,38 +97,36 @@ static bool isThrow(OpcodeID opcodeID)
     }
 }
 
-static bool isJumpTarget(OpcodeID opcodeID, Vector<unsigned, 32>& jumpTargets, unsigned bytecodeOffset)
+static bool isJumpTarget(OpcodeID opcodeID, const Vector<unsigned, 32>& jumpTargets, unsigned bytecodeOffset)
 {
     if (opcodeID == op_catch)
         return true;
 
-    for (unsigned i = 0; i < jumpTargets.size(); i++) {
-        if (bytecodeOffset == jumpTargets[i])
-            return true;
-    }
-    return false;
+    return std::binary_search(jumpTargets.begin(), jumpTargets.end(), bytecodeOffset);
 }
 
 static void linkBlocks(BytecodeBasicBlock* predecessor, BytecodeBasicBlock* successor)
 {
     predecessor->addSuccessor(successor);
-    successor->addPredecessor(predecessor);
 }
 
-void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks)
+void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks)
 {
     Vector<unsigned, 32> jumpTargets;
     computePreciseJumpTargets(codeBlock, jumpTargets);
 
     // Create the entry and exit basic blocks.
-    BytecodeBasicBlock* entry = new BytecodeBasicBlock(BytecodeBasicBlock::EntryBlock);
-    basicBlocks.append(adoptRef(entry));
-    BytecodeBasicBlock* exit = new BytecodeBasicBlock(BytecodeBasicBlock::ExitBlock);
+    basicBlocks.reserveCapacity(jumpTargets.size() + 2);
+
+    auto entry = std::make_unique<BytecodeBasicBlock>(BytecodeBasicBlock::EntryBlock);
+    auto firstBlock = std::make_unique<BytecodeBasicBlock>(0, 0);
+    linkBlocks(entry.get(), firstBlock.get());
+
+    basicBlocks.append(WTF::move(entry));
+    BytecodeBasicBlock* current = firstBlock.get();
+    basicBlocks.append(WTF::move(firstBlock));
 
-    // Find basic block boundaries.
-    BytecodeBasicBlock* current = new BytecodeBasicBlock(0, 0);
-    linkBlocks(entry, current);
-    basicBlocks.append(adoptRef(current));
+    auto exit = std::make_unique<BytecodeBasicBlock>(BytecodeBasicBlock::ExitBlock);
 
     bool nextInstructionIsLeader = false;
 
@@ -136,9 +140,9 @@ void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
         bool createdBlock = false;
         // If the current bytecode is a jump target, then it's the leader of its own basic block.
         if (isJumpTarget(opcodeID, jumpTargets, bytecodeOffset) || nextInstructionIsLeader) {
-            BytecodeBasicBlock* block = new BytecodeBasicBlock(bytecodeOffset, opcodeLength);
-            basicBlocks.append(adoptRef(block));
-            current = block;
+            auto newBlock = std::make_unique<BytecodeBasicBlock>(bytecodeOffset, opcodeLength);
+            current = newBlock.get();
+            basicBlocks.append(WTF::move(newBlock));
             createdBlock = true;
             nextInstructionIsLeader = false;
             bytecodeOffset += opcodeLength;
@@ -171,7 +175,7 @@ void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
             // If we found a terminal bytecode, link to the exit block.
             if (isTerminal(opcodeID)) {
                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());
-                linkBlocks(block, exit);
+                linkBlocks(block, exit.get());
                 fallsThrough = false;
                 break;
             }
@@ -184,7 +188,7 @@ void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
                 HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset);
                 fallsThrough = false;
                 if (!handler) {
-                    linkBlocks(block, exit);
+                    linkBlocks(block, exit.get());
                     break;
                 }
                 for (unsigned i = 0; i < basicBlocks.size(); i++) {
@@ -225,7 +229,10 @@ void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
         }
     }
 
-    basicBlocks.append(adoptRef(exit));
+    basicBlocks.append(WTF::move(exit));
+    
+    for (auto& basicBlock : basicBlocks)
+        basicBlock->shrinkToFit();
 }
 
 } // namespace JSC
index 736ba85..bd7d3ae 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -36,11 +36,13 @@ namespace JSC {
 
 class CodeBlock;
 
-class BytecodeBasicBlock : public RefCounted<BytecodeBasicBlock> {
+class BytecodeBasicBlock {
+    WTF_MAKE_FAST_ALLOCATED;
 public:
     enum SpecialBlockType { EntryBlock, ExitBlock };
     BytecodeBasicBlock(unsigned start, unsigned length);
     BytecodeBasicBlock(SpecialBlockType);
+    void shrinkToFit();
 
     bool isEntryBlock() { return !m_leaderBytecodeOffset && !m_totalBytecodeLength; }
     bool isExitBlock() { return m_leaderBytecodeOffset == UINT_MAX && m_totalBytecodeLength == UINT_MAX; }
@@ -51,11 +53,8 @@ public:
     Vector<unsigned>& bytecodeOffsets() { return m_bytecodeOffsets; }
     void addBytecodeLength(unsigned);
 
-    void addPredecessor(BytecodeBasicBlock* block) { m_predecessors.append(block); }
-    void addSuccessor(BytecodeBasicBlock* block) { m_successors.append(block); }
-
-    Vector<BytecodeBasicBlock*>& predecessors() { return m_predecessors; }
     Vector<BytecodeBasicBlock*>& successors() { return m_successors; }
+    void addSuccessor(BytecodeBasicBlock* block) { m_successors.append(block); }
 
     FastBitVector& in() { return m_in; }
     FastBitVector& out() { return m_out; }
@@ -65,15 +64,13 @@ private:
     unsigned m_totalBytecodeLength;
 
     Vector<unsigned> m_bytecodeOffsets;
-
-    Vector<BytecodeBasicBlock*> m_predecessors;
     Vector<BytecodeBasicBlock*> m_successors;
 
     FastBitVector m_in;
     FastBitVector m_out;
 };
 
-void computeBytecodeBasicBlocks(CodeBlock*, Vector<RefPtr<BytecodeBasicBlock> >&);
+void computeBytecodeBasicBlocks(CodeBlock*, Vector<std::unique_ptr<BytecodeBasicBlock>>&);
 
 inline BytecodeBasicBlock::BytecodeBasicBlock(unsigned start, unsigned length)
     : m_leaderBytecodeOffset(start)
index 80173ac..c77abea 100644 (file)
@@ -51,14 +51,14 @@ static bool isValidRegisterForLiveness(CodeBlock* codeBlock, int operand)
     return virtualReg.isLocal();
 }
 
-static unsigned getLeaderOffsetForBasicBlock(RefPtr<BytecodeBasicBlock>* basicBlock)
+static unsigned getLeaderOffsetForBasicBlock(std::unique_ptr<BytecodeBasicBlock>* basicBlock)
 {
     return (*basicBlock)->leaderBytecodeOffset();
 }
 
-static BytecodeBasicBlock* findBasicBlockWithLeaderOffset(Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned leaderOffset)
+static BytecodeBasicBlock* findBasicBlockWithLeaderOffset(Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned leaderOffset)
 {
-    return (*tryBinarySearch<RefPtr<BytecodeBasicBlock>, unsigned>(basicBlocks, basicBlocks.size(), leaderOffset, getLeaderOffsetForBasicBlock)).get();
+    return (*tryBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(basicBlocks, basicBlocks.size(), leaderOffset, getLeaderOffsetForBasicBlock)).get();
 }
 
 static bool blockContainsBytecodeOffset(BytecodeBasicBlock* block, unsigned bytecodeOffset)
@@ -67,7 +67,7 @@ static bool blockContainsBytecodeOffset(BytecodeBasicBlock* block, unsigned byte
     return bytecodeOffset >= leaderOffset && bytecodeOffset < leaderOffset + block->totalBytecodeLength();
 }
 
-static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned bytecodeOffset)
+static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset)
 {
 /*
     for (unsigned i = 0; i < basicBlocks.size(); i++) {
@@ -76,7 +76,7 @@ static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<RefPtr<Bytecod
     }
     return 0;
 */
-    RefPtr<BytecodeBasicBlock>* basicBlock = approximateBinarySearch<RefPtr<BytecodeBasicBlock>, unsigned>(
+    std::unique_ptr<BytecodeBasicBlock>* basicBlock = approximateBinarySearch<std::unique_ptr<BytecodeBasicBlock>, unsigned>(
         basicBlocks, basicBlocks.size(), bytecodeOffset, getLeaderOffsetForBasicBlock);
     // We found the block we were looking for.
     if (blockContainsBytecodeOffset((*basicBlock).get(), bytecodeOffset))
@@ -98,7 +98,7 @@ static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<RefPtr<Bytecod
 // Simplified interface to bytecode use/def, which determines defs first and then uses, and includes
 // exception handlers in the uses.
 template<typename UseFunctor, typename DefFunctor>
-static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, const UseFunctor& use, const DefFunctor& def)
+static void stepOverInstruction(CodeBlock* codeBlock, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, const UseFunctor& use, const DefFunctor& def)
 {
     // This abstractly execute the instruction in reverse. Instructions logically first use operands and
     // then define operands. This logical ordering is necessary for operations that use and def the same
@@ -138,7 +138,7 @@ static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
     }
 }
 
-static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& out)
+static void stepOverInstruction(CodeBlock* codeBlock, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& out)
 {
     stepOverInstruction(
         codeBlock, basicBlocks, bytecodeOffset,
@@ -152,7 +152,7 @@ static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasi
         });
 }
 
-static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned targetOffset, FastBitVector& result)
+static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks, unsigned targetOffset, FastBitVector& result)
 {
     ASSERT(!block->isExitBlock());
     ASSERT(!block->isEntryBlock());
@@ -170,7 +170,7 @@ static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, Bytecode
     result.set(out);
 }
 
-static void computeLocalLivenessForBlock(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks)
+static void computeLocalLivenessForBlock(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks)
 {
     if (block->isExitBlock() || block->isEntryBlock())
         return;
@@ -294,12 +294,6 @@ void BytecodeLivenessAnalysis::dumpResults()
     for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
         BytecodeBasicBlock* block = m_basicBlocks[i].get();
         dataLogF("\nBytecode basic block %u: %p (offset: %u, length: %u)\n", i, block, block->leaderBytecodeOffset(), block->totalBytecodeLength());
-        dataLogF("Predecessors: ");
-        for (unsigned j = 0; j < block->predecessors().size(); j++) {
-            BytecodeBasicBlock* predecessor = block->predecessors()[j];
-            dataLogF("%p ", predecessor);
-        }
-        dataLogF("\n");
         dataLogF("Successors: ");
         for (unsigned j = 0; j < block->successors().size(); j++) {
             BytecodeBasicBlock* successor = block->successors()[j];
index 3134e79..ece16f2 100644 (file)
@@ -39,6 +39,7 @@ class FullBytecodeLiveness;
 
 class BytecodeLivenessAnalysis {
     WTF_MAKE_FAST_ALLOCATED;
+    WTF_MAKE_NONCOPYABLE(BytecodeLivenessAnalysis);
 public:
     BytecodeLivenessAnalysis(CodeBlock*);
     
@@ -56,7 +57,7 @@ private:
     void getLivenessInfoAtBytecodeOffset(unsigned bytecodeOffset, FastBitVector&);
 
     CodeBlock* m_codeBlock;
-    Vector<RefPtr<BytecodeBasicBlock> > m_basicBlocks;
+    Vector<std::unique_ptr<BytecodeBasicBlock>> m_basicBlocks;
 };
 
 inline bool operandIsAlwaysLive(int operand);
index 6bba492..414dfd9 100644 (file)
@@ -119,6 +119,7 @@ void computePreciseJumpTargets(CodeBlock* codeBlock, Vector<unsigned, 32>& out)
         lastValue = value;
     }
     out.resize(toIndex);
+    out.shrinkToFit();
 }
 
 void findJumpTargetsForBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, Vector<unsigned, 1>& out)
index fb60f9b..852413d 100644 (file)
@@ -30,7 +30,9 @@
 
 namespace JSC {
 
+// Return a sorted list of bytecode index that are the destination of a jump.
 void computePreciseJumpTargets(CodeBlock*, Vector<unsigned, 32>& out);
+
 void findJumpTargetsForBytecodeOffset(CodeBlock*, unsigned bytecodeOffset, Vector<unsigned, 1>& out);
 
 } // namespace JSC