bytecode/BytecodeLivenessAnalysis.cpp

   1 /*
   2  * Copyright (C) 2013 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "BytecodeLivenessAnalysis.h"
  28
  29 #include "BytecodeLivenessAnalysisInlines.h"
  30 #include "BytecodeUseDef.h"
  31 #include "CodeBlock.h"
  32 #include "FullBytecodeLiveness.h"
  33 #include "PreciseJumpTargets.h"
  34
  35 namespace JSC {
  36
  37 BytecodeLivenessAnalysis::BytecodeLivenessAnalysis(CodeBlock* codeBlock)
  38     : m_codeBlock(codeBlock)
  39 {
  40     ASSERT(m_codeBlock);
  41     compute();
  42 }
  43
  44 static bool isValidRegisterForLiveness(CodeBlock* codeBlock, int operand)
  45 {
  46     if (codeBlock->isConstantRegisterIndex(operand))
  47         return false;
  48
  49     VirtualRegister virtualReg(operand);
  50     if (!virtualReg.isLocal())
  51         return false;
  52
  53     if (codeBlock->captureCount()
  54         && operand <= codeBlock->captureStart()
  55         && operand > codeBlock->captureEnd())
  56         return false;
  57
  58     return true;
  59 }
  60
  61 static void setForOperand(CodeBlock* codeBlock, FastBitVector& bits, int operand)
  62 {
  63     ASSERT(isValidRegisterForLiveness(codeBlock, operand));
  64     VirtualRegister virtualReg(operand);
  65     if (virtualReg.offset() > codeBlock->captureStart())
  66         bits.set(virtualReg.toLocal());
  67     else
  68         bits.set(virtualReg.toLocal() - codeBlock->captureCount());
  69 }
  70
  71 namespace {
  72
  73 class SetBit {
  74 public:
  75     SetBit(FastBitVector& bits)
  76         : m_bits(bits)
  77     {
  78     }
  79
  80     void operator()(CodeBlock* codeBlock, Instruction*, OpcodeID, int operand)
  81     {
  82         if (isValidRegisterForLiveness(codeBlock, operand))
  83             setForOperand(codeBlock, m_bits, operand);
  84     }
  85
  86 private:
  87     FastBitVector& m_bits;
  88 };
  89
  90 } // anonymous namespace
  91
  92 static unsigned getLeaderOffsetForBasicBlock(RefPtr<BytecodeBasicBlock>* basicBlock)
  93 {
  94     return (*basicBlock)->leaderBytecodeOffset();
  95 }
  96
  97 static BytecodeBasicBlock* findBasicBlockWithLeaderOffset(Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned leaderOffset)
  98 {
  99     return (*tryBinarySearch<RefPtr<BytecodeBasicBlock>, unsigned>(basicBlocks, basicBlocks.size(), leaderOffset, getLeaderOffsetForBasicBlock)).get();
 100 }
 101
 102 static bool blockContainsBytecodeOffset(BytecodeBasicBlock* block, unsigned bytecodeOffset)
 103 {
 104     unsigned leaderOffset = block->leaderBytecodeOffset();
 105     return bytecodeOffset >= leaderOffset && bytecodeOffset < leaderOffset + block->totalBytecodeLength();
 106 }
 107
 108 static BytecodeBasicBlock* findBasicBlockForBytecodeOffset(Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned bytecodeOffset)
 109 {
 110 /*
 111     for (unsigned i = 0; i < basicBlocks.size(); i++) {
 112         if (blockContainsBytecodeOffset(basicBlocks[i].get(), bytecodeOffset))
 113             return basicBlocks[i].get();
 114     }
 115     return 0;
 116 */
 117     RefPtr<BytecodeBasicBlock>* basicBlock = approximateBinarySearch<RefPtr<BytecodeBasicBlock>, unsigned>(
 118         basicBlocks, basicBlocks.size(), bytecodeOffset, getLeaderOffsetForBasicBlock);
 119     // We found the block we were looking for.
 120     if (blockContainsBytecodeOffset((*basicBlock).get(), bytecodeOffset))
 121         return (*basicBlock).get();
 122
 123     // Basic block is to the left of the returned block.
 124     if (bytecodeOffset < (*basicBlock)->leaderBytecodeOffset()) {
 125         ASSERT(basicBlock - 1 >= basicBlocks.data());
 126         ASSERT(blockContainsBytecodeOffset(basicBlock[-1].get(), bytecodeOffset));
 127         return basicBlock[-1].get();
 128     }
 129
 130     // Basic block is to the right of the returned block.
 131     ASSERT(&basicBlock[1] <= &basicBlocks.last());
 132     ASSERT(blockContainsBytecodeOffset(basicBlock[1].get(), bytecodeOffset));
 133     return basicBlock[1].get();
 134 }
 135
 136 static void stepOverInstruction(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock>>& basicBlocks, unsigned bytecodeOffset, FastBitVector& uses, FastBitVector& defs, FastBitVector& out)
 137 {
 138     uses.clearAll();
 139     defs.clearAll();
 140
 141     SetBit setUses(uses);
 142     SetBit setDefs(defs);
 143     computeUsesForBytecodeOffset(codeBlock, bytecodeOffset, setUses);
 144     computeDefsForBytecodeOffset(codeBlock, bytecodeOffset, setDefs);
 145
 146     out.exclude(defs);
 147     out.merge(uses);
 148
 149     // If we have an exception handler, we want the live-in variables of the
 150     // exception handler block to be included in the live-in of this particular bytecode.
 151     if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset)) {
 152         BytecodeBasicBlock* handlerBlock = findBasicBlockWithLeaderOffset(basicBlocks, handler->target);
 153         ASSERT(handlerBlock);
 154         out.merge(handlerBlock->in());
 155     }
 156 }
 157
 158 static void computeLocalLivenessForBytecodeOffset(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks, unsigned targetOffset, FastBitVector& result)
 159 {
 160     ASSERT(!block->isExitBlock());
 161     ASSERT(!block->isEntryBlock());
 162
 163     FastBitVector out = block->out();
 164
 165     FastBitVector uses;
 166     FastBitVector defs;
 167     uses.resize(out.numBits());
 168     defs.resize(out.numBits());
 169
 170     for (int i = block->bytecodeOffsets().size() - 1; i >= 0; i--) {
 171         unsigned bytecodeOffset = block->bytecodeOffsets()[i];
 172         if (targetOffset > bytecodeOffset)
 173             break;
 174
 175         stepOverInstruction(codeBlock, basicBlocks, bytecodeOffset, uses, defs, out);
 176     }
 177
 178     result.set(out);
 179 }
 180
 181 static void computeLocalLivenessForBlock(CodeBlock* codeBlock, BytecodeBasicBlock* block, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks)
 182 {
 183     if (block->isExitBlock() || block->isEntryBlock())
 184         return;
 185     computeLocalLivenessForBytecodeOffset(codeBlock, block, basicBlocks, block->leaderBytecodeOffset(), block->in());
 186 }
 187
 188 void BytecodeLivenessAnalysis::runLivenessFixpoint()
 189 {
 190     UnlinkedCodeBlock* unlinkedCodeBlock = m_codeBlock->unlinkedCodeBlock();
 191     unsigned numberOfVariables =
 192         unlinkedCodeBlock->m_numCalleeRegisters - m_codeBlock->captureCount();
 193
 194     for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
 195         BytecodeBasicBlock* block = m_basicBlocks[i].get();
 196         block->in().resize(numberOfVariables);
 197         block->out().resize(numberOfVariables);
 198     }
 199
 200     bool changed;
 201     m_basicBlocks.last()->in().clearAll();
 202     m_basicBlocks.last()->out().clearAll();
 203     FastBitVector newOut;
 204     newOut.resize(m_basicBlocks.last()->out().numBits());
 205     do {
 206         changed = false;
 207         for (int i = m_basicBlocks.size() - 2; i >= 0; i--) {
 208             BytecodeBasicBlock* block = m_basicBlocks[i].get();
 209             newOut.clearAll();
 210             for (unsigned j = 0; j < block->successors().size(); j++)
 211                 newOut.merge(block->successors()[j]->in());
 212             bool outDidChange = block->out().setAndCheck(newOut);
 213             computeLocalLivenessForBlock(m_codeBlock, block, m_basicBlocks);
 214             changed |= outDidChange;
 215         }
 216     } while (changed);
 217 }
 218
 219 void BytecodeLivenessAnalysis::getLivenessInfoForNonCapturedVarsAtBytecodeOffset(unsigned bytecodeOffset, FastBitVector& result)
 220 {
 221     BytecodeBasicBlock* block = findBasicBlockForBytecodeOffset(m_basicBlocks, bytecodeOffset);
 222     ASSERT(block);
 223     ASSERT(!block->isEntryBlock());
 224     ASSERT(!block->isExitBlock());
 225     result.resize(block->out().numBits());
 226     computeLocalLivenessForBytecodeOffset(m_codeBlock, block, m_basicBlocks, bytecodeOffset, result);
 227 }
 228
 229 bool BytecodeLivenessAnalysis::operandIsLiveAtBytecodeOffset(int operand, unsigned bytecodeOffset)
 230 {
 231     if (operandIsAlwaysLive(m_codeBlock, operand))
 232         return true;
 233     FastBitVector result;
 234     getLivenessInfoForNonCapturedVarsAtBytecodeOffset(bytecodeOffset, result);
 235     return operandThatIsNotAlwaysLiveIsLive(m_codeBlock, result, operand);
 236 }
 237
 238 FastBitVector getLivenessInfo(CodeBlock* codeBlock, const FastBitVector& out)
 239 {
 240     FastBitVector result;
 241
 242     unsigned numCapturedVars = codeBlock->captureCount();
 243     if (numCapturedVars) {
 244         int firstCapturedLocal = VirtualRegister(codeBlock->captureStart()).toLocal();
 245         result.resize(out.numBits() + numCapturedVars);
 246         for (unsigned i = 0; i < numCapturedVars; ++i)
 247             result.set(firstCapturedLocal + i);
 248     } else
 249         result.resize(out.numBits());
 250
 251     int outLength = out.numBits();
 252     ASSERT(outLength >= 0);
 253     for (int i = 0; i < outLength; i++) {
 254         if (!out.get(i))
 255             continue;
 256
 257         if (!numCapturedVars) {
 258             result.set(i);
 259             continue;
 260         }
 261
 262         if (virtualRegisterForLocal(i).offset() > codeBlock->captureStart())
 263             result.set(i);
 264         else
 265             result.set(numCapturedVars + i);
 266     }
 267     return result;
 268 }
 269
 270 FastBitVector BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(unsigned bytecodeOffset)
 271 {
 272     FastBitVector out;
 273     getLivenessInfoForNonCapturedVarsAtBytecodeOffset(bytecodeOffset, out);
 274     return getLivenessInfo(m_codeBlock, out);
 275 }
 276
 277 void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
 278 {
 279     FastBitVector out;
 280     FastBitVector uses;
 281     FastBitVector defs;
 282
 283     result.m_codeBlock = m_codeBlock;
 284     result.m_map.clear();
 285
 286     for (unsigned i = m_basicBlocks.size(); i--;) {
 287         BytecodeBasicBlock* block = m_basicBlocks[i].get();
 288         if (block->isEntryBlock() || block->isExitBlock())
 289             continue;
 290
 291         out = block->out();
 292         uses.resize(out.numBits());
 293         defs.resize(out.numBits());
 294
 295         for (unsigned i = block->bytecodeOffsets().size(); i--;) {
 296             unsigned bytecodeOffset = block->bytecodeOffsets()[i];
 297             stepOverInstruction(m_codeBlock, m_basicBlocks, bytecodeOffset, uses, defs, out);
 298             result.m_map.add(bytecodeOffset, out);
 299         }
 300     }
 301 }
 302
 303 void BytecodeLivenessAnalysis::dumpResults()
 304 {
 305     Interpreter* interpreter = m_codeBlock->vm()->interpreter;
 306     Instruction* instructionsBegin = m_codeBlock->instructions().begin();
 307     for (unsigned i = 0; i < m_basicBlocks.size(); i++) {
 308         BytecodeBasicBlock* block = m_basicBlocks[i].get();
 309         dataLogF("\nBytecode basic block %u: %p (offset: %u, length: %u)\n", i, block, block->leaderBytecodeOffset(), block->totalBytecodeLength());
 310         dataLogF("Predecessors: ");
 311         for (unsigned j = 0; j < block->predecessors().size(); j++) {
 312             BytecodeBasicBlock* predecessor = block->predecessors()[j];
 313             dataLogF("%p ", predecessor);
 314         }
 315         dataLogF("\n");
 316         dataLogF("Successors: ");
 317         for (unsigned j = 0; j < block->successors().size(); j++) {
 318             BytecodeBasicBlock* successor = block->successors()[j];
 319             dataLogF("%p ", successor);
 320         }
 321         dataLogF("\n");
 322         if (block->isEntryBlock()) {
 323             dataLogF("Entry block %p\n", block);
 324             continue;
 325         }
 326         if (block->isExitBlock()) {
 327             dataLogF("Exit block: %p\n", block);
 328             continue;
 329         }
 330         for (unsigned bytecodeOffset = block->leaderBytecodeOffset(); bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength();) {
 331             const Instruction* currentInstruction = &instructionsBegin[bytecodeOffset];
 332
 333             dataLogF("Live variables: ");
 334             FastBitVector liveBefore = getLivenessInfoAtBytecodeOffset(bytecodeOffset);
 335             for (unsigned j = 0; j < liveBefore.numBits(); j++) {
 336                 if (liveBefore.get(j))
 337                     dataLogF("%u ", j);
 338             }
 339             dataLogF("\n");
 340             m_codeBlock->dumpBytecode(WTF::dataFile(), m_codeBlock->globalObject()->globalExec(), instructionsBegin, currentInstruction);
 341
 342             OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);
 343             unsigned opcodeLength = opcodeLengths[opcodeID];
 344             bytecodeOffset += opcodeLength;
 345         }
 346
 347         dataLogF("Live variables: ");
 348         FastBitVector liveAfter = block->out();
 349         for (unsigned j = 0; j < liveAfter.numBits(); j++) {
 350             if (liveAfter.get(j))
 351                 dataLogF("%u ", j);
 352         }
 353         dataLogF("\n");
 354     }
 355 }
 356
 357 void BytecodeLivenessAnalysis::compute()
 358 {
 359     computeBytecodeBasicBlocks(m_codeBlock, m_basicBlocks);
 360     ASSERT(m_basicBlocks.size());
 361     runLivenessFixpoint();
 362
 363     if (Options::dumpBytecodeLivenessResults())
 364         dumpResults();
 365 }
 366
 367 } // namespace JSC