Bytecode liveness analysis should have more lambdas and fewer sets
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 13 Mar 2015 01:57:59 +0000 (01:57 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 13 Mar 2015 01:57:59 +0000 (01:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=142647

Reviewed by Mark Lam.

Source/JavaScriptCore:

In bug 141174 I'll need to identify all of the bytecode kill sites. This requires hooking into
the bytecode analysis' stepOverFunction method, except in such a way that we observe uses that
are not in outs. This refactors stepOverFunction so that you can pass it use/def functors that
can either be used to propagate outs (as we do right now) or to additionally detect kills or
whatever else.

In order to achieve this, the liveness analysis was moved off of maintaining uses/defs
bitvectors. This wasn't helping the abstraction and was probably inefficient. The new code
should be a bit faster since we don't have to clear uses/defs bitvectors on each instruction. On
the other hand, being able to intercept each use means that our code for exception handlers is
no longer a bitwise-merge; it requires finding set bits. Fortunately, this code only kicks in
for instructions inside a try, and its performance is O(live at catch), so that's probably not
bad.

* bytecode/BytecodeLivenessAnalysis.cpp:
(JSC::indexForOperand):
(JSC::stepOverInstruction):
(JSC::computeLocalLivenessForBytecodeOffset):
(JSC::BytecodeLivenessAnalysis::computeFullLiveness):
(JSC::setForOperand): Deleted.
* bytecode/BytecodeUseDef.h:
(JSC::computeUsesForBytecodeOffset):
(JSC::computeDefsForBytecodeOffset):
* bytecode/CodeBlock.cpp:

Source/WTF:

Add a method for iterating each set bit in a FastBitVector. Uses a functor as a callback since
this allows for a more efficient algorithm.

* wtf/FastBitVector.h:
(WTF::FastBitVector::forEachSetBit):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp
Source/JavaScriptCore/bytecode/BytecodeUseDef.h
Source/JavaScriptCore/bytecode/CodeBlock.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/FastBitVector.h

index f55a200..f3cf1e3 100644 (file)
@@ -1,3 +1,35 @@
+2015-03-12  Filip Pizlo  <fpizlo@apple.com>
+
+        Bytecode liveness analysis should have more lambdas and fewer sets
+        https://bugs.webkit.org/show_bug.cgi?id=142647
+
+        Reviewed by Mark Lam.
+        
+        In bug 141174 I'll need to identify all of the bytecode kill sites. This requires hooking into
+        the bytecode analysis' stepOverFunction method, except in such a way that we observe uses that
+        are not in outs. This refactors stepOverFunction so that you can pass it use/def functors that
+        can either be used to propagate outs (as we do right now) or to additionally detect kills or
+        whatever else.
+        
+        In order to achieve this, the liveness analysis was moved off of maintaining uses/defs
+        bitvectors. This wasn't helping the abstraction and was probably inefficient. The new code
+        should be a bit faster since we don't have to clear uses/defs bitvectors on each instruction. On
+        the other hand, being able to intercept each use means that our code for exception handlers is
+        no longer a bitwise-merge; it requires finding set bits. Fortunately, this code only kicks in
+        for instructions inside a try, and its performance is O(live at catch), so that's probably not
+        bad.
+
+        * bytecode/BytecodeLivenessAnalysis.cpp:
+        (JSC::indexForOperand):
+        (JSC::stepOverInstruction):
+        (JSC::computeLocalLivenessForBytecodeOffset):
+        (JSC::BytecodeLivenessAnalysis::computeFullLiveness):
+        (JSC::setForOperand): Deleted.
+        * bytecode/BytecodeUseDef.h:
+        (JSC::computeUsesForBytecodeOffset):
+        (JSC::computeDefsForBytecodeOffset):
+        * bytecode/CodeBlock.cpp:
+
 2015-03-12  Ryosuke Niwa  <rniwa@webkit.org>
 
         "this" should be in TDZ until super is called in the constructor of a derived class
index 926334c..20a71d5 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
@@ -58,37 +58,15 @@ static bool isValidRegisterForLiveness(CodeBlock* codeBlock, int operand)
     return true;
 }
 
-static void setForOperand(CodeBlock* codeBlock, FastBitVector& bits, int operand)
+static unsigned indexForOperand(CodeBlock* codeBlock, int operand)
 {
     ASSERT(isValidRegisterForLiveness(codeBlock, operand));
     VirtualRegister virtualReg(operand);
     if (virtualReg.offset() > codeBlock->captureStart())
-        bits.set(virtualReg.toLocal());
-    else
-        bits.set(virtualReg.toLocal() - codeBlock->captureCount());
+        return virtualReg.toLocal();
+    return virtualReg.toLocal() - codeBlock->captureCount();
 }
 
-namespace {
-
-class SetBit {
-public:
-    SetBit(FastBitVector& bits)
-        : m_bits(bits)
-    {
-    }
-    
-    void operator()(CodeBlock* codeBlock, Instruction*, OpcodeID, int operand)
-    {
-        if (isValidRegisterForLiveness(codeBlock, operand))
-            setForOperand(codeBlock, m_bits, operand);
-    }
-    
-private:
-    FastBitVector& m_bits;
-};
-
-} // anonymous namespace
-
 static unsigned getLeaderOffsetForBasicBlock(RefPtr<BytecodeBasicBlock>* basicBlock)
 {
     return (*basicBlock)->leaderBytecodeOffset();
@@ -133,28 +111,63 @@ static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<RefPtr<Bytecod
     return basicBlock[1].get();
 }
 
-static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& uses, FastBitVector& defs, FastBitVector& out)
+// 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)
 {
-    uses.clearAll();
-    defs.clearAll();
+    // 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
+    // operand, like:
+    //
+    //     op_add loc1, loc1, loc2
+    //
+    // The use of loc1 happens before the def of loc1. That's a semantic requirement since the add
+    // operation cannot travel forward in time to read the value that it will produce after reading that
+    // value. Since we are executing in reverse, this means that we must do defs before uses (reverse of
+    // uses before defs).
+    //
+    // Since this is a liveness analysis, this ordering ends up being particularly important: if we did
+    // uses before defs, then the add operation above would appear to not have loc1 live, since we'd
+    // first add it to the out set (the use), and then we'd remove it (the def).
     
-    SetBit setUses(uses);
-    SetBit setDefs(defs);
-    computeUsesForBytecodeOffset(codeBlock, bytecodeOffset, setUses);
-    computeDefsForBytecodeOffset(codeBlock, bytecodeOffset, setDefs);
-    
-    out.exclude(defs);
-    out.merge(uses);
+    computeDefsForBytecodeOffset(
+        codeBlock, bytecodeOffset,
+        [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
+            if (isValidRegisterForLiveness(codeBlock, operand))
+                def(indexForOperand(codeBlock, operand));
+        });
     
+    computeUsesForBytecodeOffset(
+        codeBlock, bytecodeOffset,
+        [&] (CodeBlock* codeBlock, Instruction*, OpcodeID, int operand) {
+            if (isValidRegisterForLiveness(codeBlock, operand))
+                use(indexForOperand(codeBlock, operand));
+        });
+        
     // If we have an exception handler, we want the live-in variables of the 
     // exception handler block to be included in the live-in of this particular bytecode.
     if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset)) {
         BytecodeBasicBlock* handlerBlock = findBasicBlockWithLeaderOffset(basicBlocks, handler->target);
         ASSERT(handlerBlock);
-        out.merge(handlerBlock->in());
+        handlerBlock->in().forEachSetBit(use);
     }
 }
 
+static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& out)
+{
+    stepOverInstruction(
+        codeBlock, basicBlocks, bytecodeOffset,
+        [&] (unsigned bitIndex) {
+            // This is the use functor, so we set the bit.
+            out.set(bitIndex);
+        },
+        [&] (unsigned bitIndex) {
+            // This is the def functor, so we clear the bit.
+            out.clear(bitIndex);
+        });
+}
+
 static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned targetOffset, FastBitVector& result)
 {
     ASSERT(!block->isExitBlock());
@@ -162,17 +175,12 @@ static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, Bytecode
 
     FastBitVector out = block->out();
 
-    FastBitVector uses;
-    FastBitVector defs;
-    uses.resize(out.numBits());
-    defs.resize(out.numBits());
-
     for (int i = block->bytecodeOffsets().size() - 1; i >= 0; i--) {
         unsigned bytecodeOffset = block->bytecodeOffsets()[i];
         if (targetOffset > bytecodeOffset)
             break;
         
-        stepOverInstruction(codeBlock, basicBlocks, bytecodeOffset, uses, defs, out);
+        stepOverInstruction(codeBlock, basicBlocks, bytecodeOffset, out);
     }
 
     result.set(out);
@@ -277,8 +285,6 @@ FastBitVector BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(unsigned
 void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
 {
     FastBitVector out;
-    FastBitVector uses;
-    FastBitVector defs;
     
     result.m_codeBlock = m_codeBlock;
     result.m_map.clear();
@@ -289,12 +295,10 @@ void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
             continue;
         
         out = block->out();
-        uses.resize(out.numBits());
-        defs.resize(out.numBits());
         
         for (unsigned i = block->bytecodeOffsets().size(); i--;) {
             unsigned bytecodeOffset = block->bytecodeOffsets()[i];
-            stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, uses, defs, out);
+            stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, out);
             result.m_map.add(bytecodeOffset, out);
         }
     }
index 21ece95..8952cda 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
@@ -32,7 +32,7 @@ namespace JSC {
 
 template<typename Functor>
 void computeUsesForBytecodeOffset(
-    CodeBlock* codeBlock, unsigned bytecodeOffset, Functor& functor)
+    CodeBlock* codeBlock, unsigned bytecodeOffset, const Functor& functor)
 {
     Interpreter* interpreter = codeBlock->vm()->interpreter;
     Instruction* instructionsBegin = codeBlock->instructions().begin();
@@ -235,7 +235,7 @@ void computeUsesForBytecodeOffset(
 }
 
 template<typename Functor>
-void computeDefsForBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, Functor& functor)
+void computeDefsForBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, const Functor& functor)
 {
     Interpreter* interpreter = codeBlock->vm()->interpreter;
     Instruction* instructionsBegin = codeBlock->instructions().begin();
index 16fcaaa..3d3539d 100644 (file)
@@ -3881,7 +3881,7 @@ String CodeBlock::nameForRegister(VirtualRegister virtualRegister)
 namespace {
 
 struct VerifyCapturedDef {
-    void operator()(CodeBlock* codeBlock, Instruction* instruction, OpcodeID opcodeID, int operand)
+    void operator()(CodeBlock* codeBlock, Instruction* instruction, OpcodeID opcodeID, int operand) const
     {
         unsigned bytecodeOffset = instruction - codeBlock->instructions().begin();
         
index ba490d6..b6f2969 100644 (file)
@@ -1,3 +1,16 @@
+2015-03-12  Filip Pizlo  <fpizlo@apple.com>
+
+        Bytecode liveness analysis should have more lambdas and fewer sets
+        https://bugs.webkit.org/show_bug.cgi?id=142647
+
+        Reviewed by Mark Lam.
+        
+        Add a method for iterating each set bit in a FastBitVector. Uses a functor as a callback since
+        this allows for a more efficient algorithm.
+
+        * wtf/FastBitVector.h:
+        (WTF::FastBitVector::forEachSetBit):
+
 2015-03-12  Michael Saboff  <msaboff@apple.com>
 
         Disable Yarr JIT for ARMv7k
index f96180d..15c0a55 100644 (file)
@@ -177,6 +177,22 @@ public:
         return result;
     }
     
+    template<typename Functor>
+    void forEachSetBit(const Functor& functor)
+    {
+        unsigned n = arrayLength();
+        for (unsigned i = 0; i < n; ++i) {
+            uint32_t word = m_array[i];
+            unsigned j = i << 5;
+            while (word) {
+                if (word & 1)
+                    functor(j);
+                word >>= 1;
+                j++;
+            }
+        }
+    }
+    
     WTF_EXPORT_PRIVATE void dump(PrintStream&) const;
     
 private: