1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <array>
6#include <fstream>
7#include <map>
8#include <string>
9#include <vector>
10
11#include "src/globals.h"
12#include "src/interpreter/bytecode-peephole-table.h"
13#include "src/interpreter/bytecodes.h"
14
15namespace v8 {
16namespace internal {
17
18namespace interpreter {
19
20const char* ActionName(PeepholeAction action) {
21  switch (action) {
22#define CASE(Name)              \
23  case PeepholeAction::k##Name: \
24    return "PeepholeAction::k" #Name;
25    PEEPHOLE_ACTION_LIST(CASE)
26#undef CASE
27    default:
28      UNREACHABLE();
29      return "";
30  }
31}
32
33std::string BytecodeName(Bytecode bytecode) {
34  return "Bytecode::k" + std::string(Bytecodes::ToString(bytecode));
35}
36
37class PeepholeActionTableWriter final {
38 public:
39  static const size_t kNumberOfBytecodes =
40      static_cast<size_t>(Bytecode::kLast) + 1;
41  typedef std::array<PeepholeActionAndData, kNumberOfBytecodes> Row;
42
43  void BuildTable();
44  void Write(std::ostream& os);
45
46 private:
47  static const char* kIndent;
48  static const char* kNamespaceElements[];
49
50  void WriteHeader(std::ostream& os);
51  void WriteIncludeFiles(std::ostream& os);
52  void WriteClassMethods(std::ostream& os);
53  void WriteUniqueRows(std::ostream& os);
54  void WriteRowMap(std::ostream& os);
55  void WriteRow(std::ostream& os, size_t row_index);
56  void WriteOpenNamespace(std::ostream& os);
57  void WriteCloseNamespace(std::ostream& os);
58
59  PeepholeActionAndData LookupActionAndData(Bytecode last, Bytecode current);
60  void BuildRow(Bytecode last, Row* row);
61  size_t HashRow(const Row* row);
62  void InsertRow(size_t row_index, const Row* const row, size_t row_hash,
63                 std::map<size_t, size_t>* hash_to_row_map);
64  bool RowsEqual(const Row* const first, const Row* const second);
65
66  std::vector<Row>* table() { return &table_; }
67
68  // Table of unique rows.
69  std::vector<Row> table_;
70
71  // Mapping of row index to unique row index.
72  std::array<size_t, kNumberOfBytecodes> row_map_;
73};
74
75const char* PeepholeActionTableWriter::kIndent = "  ";
76const char* PeepholeActionTableWriter::kNamespaceElements[] = {"v8", "internal",
77                                                               "interpreter"};
78
79// static
80PeepholeActionAndData PeepholeActionTableWriter::LookupActionAndData(
81    Bytecode last, Bytecode current) {
82  // ToName bytecodes can be replaced by Star with the same output register if
83  // the value in the accumulator is already a name.
84  if (current == Bytecode::kToName && Bytecodes::PutsNameInAccumulator(last)) {
85    return {PeepholeAction::kChangeBytecodeAction, Bytecode::kStar};
86  }
87
88  // Nop are placeholders for holding source position information and can be
89  // elided if there is no source information.
90  if (last == Bytecode::kNop) {
91    if (Bytecodes::IsJump(current)) {
92      return {PeepholeAction::kElideLastBeforeJumpAction, Bytecode::kIllegal};
93    } else {
94      return {PeepholeAction::kElideLastAction, Bytecode::kIllegal};
95    }
96  }
97
98  // The accumulator is invisible to the debugger. If there is a sequence
99  // of consecutive accumulator loads (that don't have side effects) then
100  // only the final load is potentially visible.
101  if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) &&
102      Bytecodes::IsAccumulatorLoadWithoutEffects(current)) {
103    return {PeepholeAction::kElideLastAction, Bytecode::kIllegal};
104  }
105
106  // The current instruction clobbers the accumulator without reading
107  // it. The load in the last instruction can be elided as it has no
108  // effect.
109  if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) &&
110      Bytecodes::GetAccumulatorUse(current) == AccumulatorUse::kWrite) {
111    return {PeepholeAction::kElideLastAction, Bytecode::kIllegal};
112  }
113
114  // Ldar and Star make the accumulator and register hold equivalent
115  // values. Only the first bytecode is needed if there's a sequence
116  // of back-to-back Ldar and Star bytecodes with the same operand.
117  if (Bytecodes::IsLdarOrStar(last) && Bytecodes::IsLdarOrStar(current)) {
118    return {PeepholeAction::kElideCurrentIfOperand0MatchesAction,
119            Bytecode::kIllegal};
120  }
121
122  // TODO(rmcilroy): Add elide for consecutive mov to and from the same
123  // register.
124
125  // Remove ToBoolean coercion from conditional jumps where possible.
126  if (Bytecodes::WritesBooleanToAccumulator(last)) {
127    if (Bytecodes::IsJumpIfToBoolean(current)) {
128      return {PeepholeAction::kChangeJumpBytecodeAction,
129              Bytecodes::GetJumpWithoutToBoolean(current)};
130    } else if (current == Bytecode::kToBooleanLogicalNot) {
131      return {PeepholeAction::kChangeBytecodeAction, Bytecode::kLogicalNot};
132    }
133  }
134
135  // Fuse LdaSmi followed by binary op to produce binary op with a
136  // immediate integer argument. This savaes on dispatches and size.
137  if (last == Bytecode::kLdaSmi) {
138    switch (current) {
139      case Bytecode::kAdd:
140        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
141                Bytecode::kAddSmi};
142      case Bytecode::kSub:
143        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
144                Bytecode::kSubSmi};
145      case Bytecode::kBitwiseAnd:
146        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
147                Bytecode::kBitwiseAndSmi};
148      case Bytecode::kBitwiseOr:
149        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
150                Bytecode::kBitwiseOrSmi};
151      case Bytecode::kShiftLeft:
152        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
153                Bytecode::kShiftLeftSmi};
154      case Bytecode::kShiftRight:
155        return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction,
156                Bytecode::kShiftRightSmi};
157      default:
158        break;
159    }
160  }
161
162  // Fuse LdaZero followed by binary op to produce binary op with a
163  // zero immediate argument. This saves dispatches, but not size.
164  if (last == Bytecode::kLdaZero) {
165    switch (current) {
166      case Bytecode::kAdd:
167        return {
168            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
169            Bytecode::kAddSmi};
170      case Bytecode::kSub:
171        return {
172            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
173            Bytecode::kSubSmi};
174      case Bytecode::kBitwiseAnd:
175        return {
176            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
177            Bytecode::kBitwiseAndSmi};
178      case Bytecode::kBitwiseOr:
179        return {
180            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
181            Bytecode::kBitwiseOrSmi};
182      case Bytecode::kShiftLeft:
183        return {
184            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
185            Bytecode::kShiftLeftSmi};
186      case Bytecode::kShiftRight:
187        return {
188            PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction,
189            Bytecode::kShiftRightSmi};
190      default:
191        break;
192    }
193  }
194
195  // Fuse LdaNull/LdaUndefined followed by a equality comparison with test
196  // undetectable. Testing undetectable is a simple check on the map which is
197  // more efficient than the full comparison operation.
198  if (last == Bytecode::kLdaNull || last == Bytecode::kLdaUndefined) {
199    if (current == Bytecode::kTestEqual) {
200      return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction,
201              Bytecode::kTestUndetectable};
202    }
203  }
204
205  // Fuse LdaNull/LdaUndefined followed by a strict equals with
206  // TestNull/TestUndefined.
207  if (current == Bytecode::kTestEqualStrict) {
208    if (last == Bytecode::kLdaNull) {
209      return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction,
210              Bytecode::kTestNull};
211    } else if (last == Bytecode::kLdaUndefined) {
212      return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction,
213              Bytecode::kTestUndefined};
214    }
215  }
216
217  // If there is no last bytecode to optimize against, store the incoming
218  // bytecode or for jumps emit incoming bytecode immediately.
219  if (last == Bytecode::kIllegal) {
220    if (Bytecodes::IsJump(current)) {
221      return {PeepholeAction::kUpdateLastJumpAction, Bytecode::kIllegal};
222    } else if (current == Bytecode::kNop) {
223      return {PeepholeAction::kUpdateLastIfSourceInfoPresentAction,
224              Bytecode::kIllegal};
225    } else {
226      return {PeepholeAction::kUpdateLastAction, Bytecode::kIllegal};
227    }
228  }
229
230  // No matches, take the default action.
231  if (Bytecodes::IsJump(current)) {
232    return {PeepholeAction::kDefaultJumpAction, Bytecode::kIllegal};
233  } else {
234    return {PeepholeAction::kDefaultAction, Bytecode::kIllegal};
235  }
236}
237
238void PeepholeActionTableWriter::Write(std::ostream& os) {
239  WriteHeader(os);
240  WriteIncludeFiles(os);
241  WriteOpenNamespace(os);
242  WriteUniqueRows(os);
243  WriteRowMap(os);
244  WriteClassMethods(os);
245  WriteCloseNamespace(os);
246}
247
248void PeepholeActionTableWriter::WriteHeader(std::ostream& os) {
249  os << "// Copyright 2016 the V8 project authors. All rights reserved.\n"
250     << "// Use of this source code is governed by a BSD-style license that\n"
251     << "// can be found in the LICENSE file.\n\n"
252     << "// Autogenerated by " __FILE__ ". Do not edit.\n\n";
253}
254
255void PeepholeActionTableWriter::WriteIncludeFiles(std::ostream& os) {
256  os << "#include \"src/interpreter/bytecode-peephole-table.h\"\n\n";
257}
258
259void PeepholeActionTableWriter::WriteUniqueRows(std::ostream& os) {
260  os << "const PeepholeActionAndData PeepholeActionTable::row_data_["
261     << table_.size() << "][" << kNumberOfBytecodes << "] = {\n";
262  for (size_t i = 0; i < table_.size(); ++i) {
263    os << "{\n";
264    WriteRow(os, i);
265    os << "},\n";
266  }
267  os << "};\n\n";
268}
269
270void PeepholeActionTableWriter::WriteRowMap(std::ostream& os) {
271  os << "const PeepholeActionAndData* const PeepholeActionTable::row_["
272     << kNumberOfBytecodes << "] = {\n";
273  for (size_t i = 0; i < kNumberOfBytecodes; ++i) {
274    os << kIndent << " PeepholeActionTable::row_data_[" << row_map_[i]
275       << "], \n";
276  }
277  os << "};\n\n";
278}
279
280void PeepholeActionTableWriter::WriteRow(std::ostream& os, size_t row_index) {
281  const Row row = table_.at(row_index);
282  for (PeepholeActionAndData action_data : row) {
283    os << kIndent << "{" << ActionName(action_data.action) << ","
284       << BytecodeName(action_data.bytecode) << "},\n";
285  }
286}
287
288void PeepholeActionTableWriter::WriteOpenNamespace(std::ostream& os) {
289  for (auto element : kNamespaceElements) {
290    os << "namespace " << element << " {\n";
291  }
292  os << "\n";
293}
294
295void PeepholeActionTableWriter::WriteCloseNamespace(std::ostream& os) {
296  for (auto element : kNamespaceElements) {
297    os << "}  // namespace " << element << "\n";
298  }
299}
300
301void PeepholeActionTableWriter::WriteClassMethods(std::ostream& os) {
302  os << "// static\n"
303     << "const PeepholeActionAndData*\n"
304     << "PeepholeActionTable::Lookup(Bytecode last, Bytecode current) {\n"
305     << kIndent
306     << "return &row_[Bytecodes::ToByte(last)][Bytecodes::ToByte(current)];\n"
307     << "}\n\n";
308}
309
310void PeepholeActionTableWriter::BuildTable() {
311  std::map<size_t, size_t> hash_to_row_map;
312  Row row;
313  for (size_t i = 0; i < kNumberOfBytecodes; ++i) {
314    uint8_t byte_value = static_cast<uint8_t>(i);
315    Bytecode last = Bytecodes::FromByte(byte_value);
316    BuildRow(last, &row);
317    size_t row_hash = HashRow(&row);
318    InsertRow(i, &row, row_hash, &hash_to_row_map);
319  }
320}
321
322void PeepholeActionTableWriter::BuildRow(Bytecode last, Row* row) {
323  for (size_t i = 0; i < kNumberOfBytecodes; ++i) {
324    uint8_t byte_value = static_cast<uint8_t>(i);
325    Bytecode current = Bytecodes::FromByte(byte_value);
326    PeepholeActionAndData action_data = LookupActionAndData(last, current);
327    row->at(i) = action_data;
328  }
329}
330
331// static
332bool PeepholeActionTableWriter::RowsEqual(const Row* const first,
333                                          const Row* const second) {
334  return memcmp(first, second, sizeof(*first)) == 0;
335}
336
337// static
338void PeepholeActionTableWriter::InsertRow(
339    size_t row_index, const Row* const row, size_t row_hash,
340    std::map<size_t, size_t>* hash_to_row_map) {
341  // Insert row if no existing row matches, otherwise use existing row.
342  auto iter = hash_to_row_map->find(row_hash);
343  if (iter == hash_to_row_map->end()) {
344    row_map_[row_index] = table()->size();
345    table()->push_back(*row);
346  } else {
347    row_map_[row_index] = iter->second;
348
349    // If the following DCHECK fails, the HashRow() is not adequate.
350    DCHECK(RowsEqual(&table()->at(iter->second), row));
351  }
352}
353
354// static
355size_t PeepholeActionTableWriter::HashRow(const Row* row) {
356  static const size_t kHashShift = 3;
357  std::size_t result = (1u << 31) - 1u;
358  const uint8_t* raw_data = reinterpret_cast<const uint8_t*>(row);
359  for (size_t i = 0; i < sizeof(*row); ++i) {
360    size_t top_bits = result >> (kBitsPerByte * sizeof(size_t) - kHashShift);
361    result = (result << kHashShift) ^ top_bits ^ raw_data[i];
362  }
363  return result;
364}
365
366}  // namespace interpreter
367}  // namespace internal
368}  // namespace v8
369
370int main(int argc, const char* argv[]) {
371  CHECK_EQ(argc, 2);
372
373  std::ofstream ofs(argv[1], std::ofstream::trunc);
374  v8::internal::interpreter::PeepholeActionTableWriter writer;
375  writer.BuildTable();
376  writer.Write(ofs);
377  ofs.flush();
378  ofs.close();
379
380  return 0;
381}
382