1  /*
  2   * Copyright (C) 2013, 2015 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  #pragma once
 27  
 28  #include "BytecodeBasicBlock.h"
 29  #include "BytecodeGraph.h"
 30  #include "CodeBlock.h"
 31  #include <wtf/Bitmap.h>
 32  #include <wtf/FastBitVector.h>
 33  
 34  namespace JSC {
 35  
 36  class BytecodeKills;
 37  class FullBytecodeLiveness;
 38  
 39  // We model our bytecode effects like the following and insert the liveness calculation points.
 40  //
 41  // <- BeforeUse
 42  //     Use
 43  // <- AfterUse
 44  //     Use by exception handlers
 45  //     Def
 46  enum class LivenessCalculationPoint : uint8_t {
 47      BeforeUse,
 48      AfterUse,
 49  };
 50  
 51  class BytecodeLivenessPropagation {
 52  public:
 53      template<typename CodeBlockType, typename UseFunctor>
 54      static void stepOverBytecodeIndexUse(CodeBlockType*, const InstructionStream&, BytecodeGraph&, BytecodeIndex, const UseFunctor&);
 55      template<typename CodeBlockType, typename UseFunctor>
 56      static void stepOverBytecodeIndexUseInExceptionHandler(CodeBlockType*, const InstructionStream&, BytecodeGraph&, BytecodeIndex, const UseFunctor&);
 57      template<typename CodeBlockType, typename DefFunctor>
 58      static void stepOverBytecodeIndexDef(CodeBlockType*, const InstructionStream&, BytecodeGraph&, BytecodeIndex, const DefFunctor&);
 59  
 60      template<typename CodeBlockType, typename UseFunctor, typename DefFunctor>
 61      static void stepOverBytecodeIndex(CodeBlockType*, const InstructionStream&, BytecodeGraph&, BytecodeIndex, const UseFunctor&, const DefFunctor&);
 62  
 63      template<typename CodeBlockType>
 64      static void stepOverInstruction(CodeBlockType*, const InstructionStream&, BytecodeGraph&, BytecodeIndex, FastBitVector& out);
 65  
 66      template<typename CodeBlockType, typename Instructions>
 67      static bool computeLocalLivenessForInstruction(CodeBlockType*, const Instructions&, BytecodeGraph&, BytecodeBasicBlock&, BytecodeIndex, FastBitVector& result);
 68  
 69      template<typename CodeBlockType, typename Instructions>
 70      static bool computeLocalLivenessForBlock(CodeBlockType*, const Instructions&, BytecodeGraph&, BytecodeBasicBlock&);
 71  
 72      template<typename CodeBlockType, typename Instructions>
 73      static FastBitVector getLivenessInfoAtInstruction(CodeBlockType*, const Instructions&, BytecodeGraph&, BytecodeIndex);
 74  
 75      template<typename CodeBlockType, typename Instructions>
 76      static void runLivenessFixpoint(CodeBlockType*, const Instructions&, BytecodeGraph&);
 77  };
 78  
 79  class BytecodeLivenessAnalysis : private BytecodeLivenessPropagation {
 80      WTF_MAKE_FAST_ALLOCATED;
 81      WTF_MAKE_NONCOPYABLE(BytecodeLivenessAnalysis);
 82  public:
 83      friend class BytecodeLivenessPropagation;
 84      BytecodeLivenessAnalysis(CodeBlock*);
 85      
 86      FastBitVector getLivenessInfoAtInstruction(CodeBlock* codeBlock, BytecodeIndex bytecodeIndex) { return BytecodeLivenessPropagation::getLivenessInfoAtInstruction(codeBlock, codeBlock->instructions(), m_graph, bytecodeIndex); }
 87      
 88      void computeFullLiveness(CodeBlock*, FullBytecodeLiveness& result);
 89  
 90      BytecodeGraph& graph() { return m_graph; }
 91  
 92  private:
 93      void dumpResults(CodeBlock*);
 94  
 95      BytecodeGraph m_graph;
 96  };
 97  
 98  Bitmap<maxNumCheckpointTmps> tmpLivenessForCheckpoint(const CodeBlock&, BytecodeIndex);
 99  
100  inline bool operandIsAlwaysLive(int operand);
101  inline bool operandThatIsNotAlwaysLiveIsLive(const FastBitVector& out, int operand);
102  inline bool operandIsLive(const FastBitVector& out, int operand);
103  inline bool isValidRegisterForLiveness(int operand);
104  
105  } // namespace JSC