1  /*
  2   * Copyright (C) 2013-2017 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 "BytecodeGraph.h"
 29  #include "BytecodeLivenessAnalysis.h"
 30  #include "BytecodeUseDef.h"
 31  #include "CodeBlock.h"
 32  #include "InterpreterInlines.h"
 33  
 34  namespace JSC {
 35  
 36  inline bool virtualRegisterIsAlwaysLive(VirtualRegister reg)
 37  {
 38      return !reg.isLocal();
 39  }
 40  
 41  inline bool virtualRegisterThatIsNotAlwaysLiveIsLive(const FastBitVector& out, VirtualRegister reg)
 42  {
 43      unsigned local = reg.toLocal();
 44      if (local >= out.numBits())
 45          return false;
 46      return out[local];
 47  }
 48  
 49  inline bool virtualRegisterIsLive(const FastBitVector& out, VirtualRegister operand)
 50  {
 51      return virtualRegisterIsAlwaysLive(operand) || virtualRegisterThatIsNotAlwaysLiveIsLive(out, operand);
 52  }
 53  
 54  inline bool isValidRegisterForLiveness(VirtualRegister operand)
 55  {
 56      if (operand.isConstant())
 57          return false;
 58      return operand.isLocal();
 59  }
 60  
 61  template<typename CodeBlockType, typename DefFunctor>
 62  inline void BytecodeLivenessPropagation::stepOverBytecodeIndexDef(CodeBlockType* codeBlock, const InstructionStream& instructions, BytecodeGraph&, BytecodeIndex bytecodeIndex, const DefFunctor& def)
 63  {
 64      auto* instruction = instructions.at(bytecodeIndex).ptr();
 65      computeDefsForBytecodeIndex(
 66          codeBlock, instruction, bytecodeIndex.checkpoint(),
 67          [&] (VirtualRegister operand) {
 68              if (isValidRegisterForLiveness(operand))
 69                  def(operand.toLocal());
 70          });
 71  }
 72  
 73  template<typename CodeBlockType, typename UseFunctor>
 74  inline void BytecodeLivenessPropagation::stepOverBytecodeIndexUse(CodeBlockType* codeBlock, const InstructionStream& instructions, BytecodeGraph&, BytecodeIndex bytecodeIndex, const UseFunctor& use)
 75  {
 76      auto* instruction = instructions.at(bytecodeIndex).ptr();
 77      computeUsesForBytecodeIndex(
 78          codeBlock, instruction, bytecodeIndex.checkpoint(),
 79          [&] (VirtualRegister operand) {
 80              if (isValidRegisterForLiveness(operand))
 81                  use(operand.toLocal());
 82          });
 83  }
 84  
 85  template<typename CodeBlockType, typename UseFunctor>
 86  inline void BytecodeLivenessPropagation::stepOverBytecodeIndexUseInExceptionHandler(CodeBlockType* codeBlock, const InstructionStream&, BytecodeGraph& graph, BytecodeIndex bytecodeIndex, const UseFunctor& use)
 87  {
 88      // If we have an exception handler, we want the live-in variables of the 
 89      // exception handler block to be included in the live-in of this particular BytecodeIndex.
 90      if (auto* handler = codeBlock->handlerForBytecodeIndex(bytecodeIndex)) {
 91          BytecodeBasicBlock* handlerBlock = graph.findBasicBlockWithLeaderOffset(handler->target);
 92          ASSERT(handlerBlock);
 93          handlerBlock->in().forEachSetBit(use);
 94      }
 95  }
 96  
 97  // Simplified interface to bytecode use/def, which determines defs first and then uses, and includes
 98  // exception handlers in the uses.
 99  template<typename CodeBlockType, typename UseFunctor, typename DefFunctor>
100  inline void BytecodeLivenessPropagation::stepOverBytecodeIndex(CodeBlockType* codeBlock, const InstructionStream& instructions, BytecodeGraph& graph, BytecodeIndex bytecodeIndex, const UseFunctor& use, const DefFunctor& def)
101  {
102      // This abstractly executes the BytecodeIndex in reverse. Instructions logically first use operands and
103      // then define operands. This logical ordering is necessary for operations that use and def the same
104      // operand, like:
105      //
106      //     op_add loc1, loc1, loc2
107      //
108      // The use of loc1 happens before the def of loc1. That's a semantic requirement since the add
109      // operation cannot travel forward in time to read the value that it will produce after reading that
110      // value. Since we are executing in reverse, this means that we must do defs before uses (reverse of
111      // uses before defs).
112      //
113      // Since this is a liveness analysis, this ordering ends up being particularly important: if we did
114      // uses before defs, then the add operation above would appear to not have loc1 live, since we'd
115      // first add it to the out set (the use), and then we'd remove it (the def).
116  
117      stepOverBytecodeIndexDef(codeBlock, instructions, graph, bytecodeIndex, def);
118      stepOverBytecodeIndexUseInExceptionHandler(codeBlock, instructions, graph, bytecodeIndex, use);
119      stepOverBytecodeIndexUse(codeBlock, instructions, graph, bytecodeIndex, use);
120  }
121  
122  template<typename CodeBlockType>
123  inline void BytecodeLivenessPropagation::stepOverInstruction(CodeBlockType* codeBlock, const InstructionStream& instructions, BytecodeGraph& graph, BytecodeIndex bytecodeIndex, FastBitVector& out)
124  {
125      auto numberOfCheckpoints = instructions.at(bytecodeIndex)->numberOfCheckpoints();
126      for (Checkpoint checkpoint = numberOfCheckpoints; checkpoint--;) {
127          stepOverBytecodeIndex(
128              codeBlock, instructions, graph, bytecodeIndex.withCheckpoint(checkpoint),
129              [&] (unsigned bitIndex) {
130                  // This is the use functor, so we set the bit.
131                  out[bitIndex] = true;
132              },
133              [&] (unsigned bitIndex) {
134                  // This is the def functor, so we clear the bit.
135                  out[bitIndex] = false;
136              });
137      }
138  }
139  
140  template<typename CodeBlockType, typename Instructions>
141  inline bool BytecodeLivenessPropagation::computeLocalLivenessForInstruction(CodeBlockType* codeBlock, const Instructions& instructions, BytecodeGraph& graph, BytecodeBasicBlock& block, BytecodeIndex targetIndex, FastBitVector& result)
142  {
143      ASSERT(!block.isExitBlock());
144      ASSERT(!block.isEntryBlock());
145      ASSERT_WITH_MESSAGE(!targetIndex.checkpoint(), "computeLocalLivenessForInstruction can't be used to ask questions about checkpoints");
146  
147      FastBitVector out = block.out();
148  
149      unsigned cursor = block.totalLength();
150      for (unsigned i = block.delta().size(); i--;) {
151          cursor -= block.delta()[i];
152          BytecodeIndex bytecodeIndex = BytecodeIndex(block.leaderOffset() + cursor);
153          if (targetIndex.offset() > bytecodeIndex.offset())
154              break;
155          stepOverInstruction(codeBlock, instructions, graph, bytecodeIndex, out);
156      }
157  
158      return result.setAndCheck(out);
159  }
160  
161  template<typename CodeBlockType, typename Instructions>
162  inline bool BytecodeLivenessPropagation::computeLocalLivenessForBlock(CodeBlockType* codeBlock, const Instructions& instructions, BytecodeGraph& graph, BytecodeBasicBlock& block)
163  {
164      if (block.isExitBlock() || block.isEntryBlock())
165          return false;
166      return computeLocalLivenessForInstruction(codeBlock, instructions, graph, block, BytecodeIndex(block.leaderOffset()), block.in());
167  }
168  
169  template<typename CodeBlockType, typename Instructions>
170  inline FastBitVector BytecodeLivenessPropagation::getLivenessInfoAtInstruction(CodeBlockType* codeBlock, const Instructions& instructions, BytecodeGraph& graph, BytecodeIndex bytecodeIndex)
171  {
172      ASSERT_WITH_MESSAGE(!bytecodeIndex.checkpoint(), "getLivenessInfoAtInstruction can't be used to ask questions about checkpoints");
173      BytecodeBasicBlock* block = graph.findBasicBlockForBytecodeOffset(bytecodeIndex.offset());
174      ASSERT(block);
175      ASSERT(!block->isEntryBlock());
176      ASSERT(!block->isExitBlock());
177      FastBitVector out;
178      out.resize(block->out().numBits());
179      computeLocalLivenessForInstruction(codeBlock, instructions, graph, *block, bytecodeIndex, out);
180      return out;
181  }
182  
183  template<typename CodeBlockType, typename Instructions>
184  inline void BytecodeLivenessPropagation::runLivenessFixpoint(CodeBlockType* codeBlock, const Instructions& instructions, BytecodeGraph& graph)
185  {
186      unsigned numberOfVariables = codeBlock->numCalleeLocals();
187      for (BytecodeBasicBlock& block : graph) {
188          block.in().resize(numberOfVariables);
189          block.out().resize(numberOfVariables);
190          block.in().clearAll();
191          block.out().clearAll();
192      }
193  
194      bool changed;
195      BytecodeBasicBlock& lastBlock = graph.last();
196      lastBlock.in().clearAll();
197      lastBlock.out().clearAll();
198      FastBitVector newOut;
199      newOut.resize(lastBlock.out().numBits());
200      do {
201          changed = false;
202          for (BytecodeBasicBlock& block : graph.basicBlocksInReverseOrder()) {
203              newOut.clearAll();
204              for (unsigned blockIndex : block.successors()) {
205                  BytecodeBasicBlock& successor = graph[blockIndex];
206                  newOut |= successor.in();
207              }
208              block.out() = newOut;
209              changed |= computeLocalLivenessForBlock(codeBlock, instructions, graph, block);
210          }
211      } while (changed);
212  }
213  
214  } // namespace JSC