1  /*
  2   * Copyright (C) 2016 Yusuke Suzuki <utatane.tea@gmail.com>
  3   * Copyright (C) 2016 Apple Inc. All rights reserved.
  4   *
  5   * Redistribution and use in source and binary forms, with or without
  6   * modification, are permitted provided that the following conditions
  7   * are met:
  8   * 1. Redistributions of source code must retain the above copyright
  9   *    notice, this list of conditions and the following disclaimer.
 10   * 2. Redistributions in binary form must reproduce the above copyright
 11   *    notice, this list of conditions and the following disclaimer in the
 12   *    documentation and/or other materials provided with the distribution.
 13   *
 14   * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 15   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 16   * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 17   * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 18   * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 19   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 20   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 21   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 22   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 23   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 24   * THE POSSIBILITY OF SUCH DAMAGE.
 25   */
 26  
 27  #pragma once
 28  
 29  #include "BytecodeGenerator.h"
 30  #include "BytecodeGraph.h"
 31  #include "BytecodeStructs.h"
 32  #include "Bytecodes.h"
 33  #include "Opcode.h"
 34  #include "UnlinkedCodeBlock.h"
 35  #include <wtf/Insertion.h>
 36  
 37  namespace JSC {
 38  
 39  // BytecodeRewriter offers the ability to insert and remove the bytecodes including jump operations.
 40  //
 41  // We use the original bytecode offsets as labels. When you emit some jumps, you can specify the jump target by
 42  // using the original bytecode offsets. These bytecode offsets are later converted appropriate values by the
 43  // rewriter. And we also use the labels to represents the position the new bytecodes inserted.
 44  //
 45  //                      |  [bytecode]  |  [bytecode]  |
 46  //   offsets            A              B              C
 47  //
 48  // We can use the above "A", "B", and "C" offsets as labels. And the rewriter has the ability to insert bytecode fragments
 49  // before and after the label. For example, if you insert the fragment after "B", the layout becomes like this.
 50  //
 51  //                      |  [bytecode]  |  [fragment]  [bytecode]  |
 52  //   offsets            A              B                          C
 53  //
 54  //  And even if you remove some original bytecodes, the offset remains as labels. For example, when you remove the A's bytecode,
 55  //  the layout becomes like this.
 56  //
 57  //                      |              |  [bytecode]  |
 58  //   offsets            A              B              C
 59  //
 60  //  And still you can insert fragments before and after "A".
 61  //
 62  //                      |  [fragment]  |  [bytecode]  |
 63  //   offsets            A              B              C
 64  //
 65  //   We can insert bytecode fragments "Before" and "After" the labels. This inserted position, either "Before" and "After",
 66  //   has effect when the label is involved with jumps. For example, when you have jump to the position "B",
 67  //
 68  //                      |  [bytecode]  |  [bytecode]  |
 69  //   offsets            A              B              C
 70  //                                     ^
 71  //                                     jump to here.
 72  //
 73  //  and you insert the bytecode before/after "B",
 74  //
 75  //                      |  [bytecode] [before]  |  [after] [bytecode]  |
 76  //   offsets            A                       B              C
 77  //                                              ^
 78  //                                              jump to here.
 79  //
 80  //  as you can see, the execution jumping into "B" does not execute [before] code.
 81  class BytecodeRewriter {
 82  WTF_MAKE_NONCOPYABLE(BytecodeRewriter);
 83  public:
 84      enum class Position : int8_t {
 85          EntryPoint = -2,
 86          Before = -1,
 87          LabelPoint = 0,
 88          After = 1,
 89          OriginalBytecodePoint = 2,
 90      };
 91  
 92      enum class IncludeBranch : uint8_t {
 93          No = 0,
 94          Yes = 1,
 95      };
 96  
 97      struct InsertionPoint {
 98          int32_t bytecodeOffset;
 99          Position position;
100  
101          InsertionPoint(InstructionStream::Offset offset, Position pos)
102              : bytecodeOffset(offset)
103              , position(pos)
104          {
105          }
106  
107          bool operator<(const InsertionPoint& other) const
108          {
109              if (bytecodeOffset == other.bytecodeOffset)
110                  return position < other.position;
111              return bytecodeOffset < other.bytecodeOffset;
112          }
113  
114          bool operator==(const InsertionPoint& other) const
115          {
116              return bytecodeOffset == other.bytecodeOffset && position == other.position;
117          }
118      };
119  
120  private:
121      struct Insertion {
122          enum class Type : uint8_t { Insert = 0, Remove = 1, };
123  
124          size_t length() const
125          {
126              if (type == Type::Remove)
127                  return removeLength;
128              return instructions.size();
129          }
130  
131          InsertionPoint index;
132          Type type;
133          IncludeBranch includeBranch;
134          size_t removeLength;
135          InstructionStreamWriter instructions;
136      };
137  
138  public:
139      class Fragment {
140      WTF_MAKE_NONCOPYABLE(Fragment);
141      public:
142          Fragment(BytecodeGenerator& bytecodeGenerator, InstructionStreamWriter& writer, IncludeBranch& includeBranch)
143              : m_bytecodeGenerator(bytecodeGenerator)
144              , m_writer(writer)
145              , m_includeBranch(includeBranch)
146          {
147          }
148  
149          template<class Op, class... Args>
150          void appendInstruction(Args... args)
151          {
152              if (isBranch(Op::opcodeID))
153                  m_includeBranch = IncludeBranch::Yes;
154  
155              m_bytecodeGenerator.withWriter(m_writer, [&] {
156                  Op::emit(&m_bytecodeGenerator, std::forward<Args>(args)...);
157              });
158          }
159  
160          void align()
161          {
162  #if CPU(NEEDS_ALIGNED_ACCESS)
163              m_bytecodeGenerator.withWriter(m_writer, [&] {
164                  while (m_bytecodeGenerator.instructions().size() % OpcodeSize::Wide32)
165                      OpNop::emit<OpcodeSize::Narrow>(&m_bytecodeGenerator);
166              });
167  #endif
168          }
169  
170      private:
171          BytecodeGenerator& m_bytecodeGenerator;
172          InstructionStreamWriter& m_writer;
173          IncludeBranch& m_includeBranch;
174      };
175  
176      BytecodeRewriter(BytecodeGenerator& bytecodeGenerator, BytecodeGraph& graph, UnlinkedCodeBlockGenerator* codeBlock, InstructionStreamWriter& writer)
177          : m_bytecodeGenerator(bytecodeGenerator)
178          , m_graph(graph)
179          , m_codeBlock(codeBlock)
180          , m_writer(writer)
181      {
182      }
183  
184      template<class Function>
185      void insertFragmentBefore(const InstructionStream::Ref& instruction, Function function)
186      {
187          IncludeBranch includeBranch = IncludeBranch::No;
188          InstructionStreamWriter writer;
189          Fragment fragment(m_bytecodeGenerator, writer, includeBranch);
190          function(fragment);
191          fragment.align();
192          insertImpl(InsertionPoint(instruction.offset(), Position::Before), includeBranch, WTFMove(writer));
193      }
194  
195      template<class Function>
196      void insertFragmentAfter(const InstructionStream::Ref& instruction, Function function)
197      {
198          IncludeBranch includeBranch = IncludeBranch::No;
199          InstructionStreamWriter writer;
200          Fragment fragment(m_bytecodeGenerator, writer, includeBranch);
201          function(fragment);
202          fragment.align();
203          insertImpl(InsertionPoint(instruction.offset(), Position::After), includeBranch, WTFMove(writer));
204      }
205  
206      void removeBytecode(const InstructionStream::Ref& instruction)
207      {
208          m_insertions.append(Insertion { InsertionPoint(instruction.offset(), Position::OriginalBytecodePoint), Insertion::Type::Remove, IncludeBranch::No, instruction->size(), { } });
209      }
210  
211      void execute();
212  
213      BytecodeGraph& graph() { return m_graph; }
214  
215      int32_t adjustAbsoluteOffset(InstructionStream::Offset absoluteOffset)
216      {
217          return adjustJumpTarget(InsertionPoint(0, Position::EntryPoint), InsertionPoint(absoluteOffset, Position::LabelPoint));
218      }
219  
220      int32_t adjustJumpTarget(InstructionStream::Offset originalBytecodeOffset, int32_t originalJumpTarget)
221      {
222          return adjustJumpTarget(InsertionPoint(originalBytecodeOffset, Position::LabelPoint), InsertionPoint(originalJumpTarget, Position::LabelPoint));
223      }
224  
225      void adjustJumpTargets();
226  
227  private:
228      void insertImpl(InsertionPoint, IncludeBranch, InstructionStreamWriter&& fragment);
229  
230      friend class UnlinkedCodeBlockGenerator;
231      void applyModification();
232      void adjustJumpTargetsInFragment(unsigned finalOffset, Insertion&);
233  
234      int adjustJumpTarget(InsertionPoint startPoint, InsertionPoint jumpTargetPoint);
235      template<typename Iterator> int calculateDifference(Iterator begin, Iterator end);
236  
237      BytecodeGenerator& m_bytecodeGenerator;
238      BytecodeGraph& m_graph;
239      UnlinkedCodeBlockGenerator* m_codeBlock;
240      InstructionStreamWriter& m_writer;
241      Vector<Insertion, 8> m_insertions;
242  };
243  
244  template<typename Iterator>
245  inline int BytecodeRewriter::calculateDifference(Iterator begin, Iterator end)
246  {
247      int result = 0;
248      for (; begin != end; ++begin) {
249          if (begin->type == Insertion::Type::Remove)
250              result -= begin->length();
251          else
252              result += begin->length();
253      }
254      return result;
255  }
256  
257  } // namespace JSC