| // Copyright 2016 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <array> |
| #include <fstream> |
| #include <map> |
| #include <string> |
| #include <vector> |
| |
| #include "src/globals.h" |
| #include "src/interpreter/bytecode-peephole-table.h" |
| #include "src/interpreter/bytecodes.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| namespace interpreter { |
| |
| const char* ActionName(PeepholeAction action) { |
| switch (action) { |
| #define CASE(Name) \ |
| case PeepholeAction::k##Name: \ |
| return "PeepholeAction::k" #Name; |
| PEEPHOLE_ACTION_LIST(CASE) |
| #undef CASE |
| default: |
| UNREACHABLE(); |
| return ""; |
| } |
| } |
| |
| std::string BytecodeName(Bytecode bytecode) { |
| return "Bytecode::k" + std::string(Bytecodes::ToString(bytecode)); |
| } |
| |
| class PeepholeActionTableWriter final { |
| public: |
| static const size_t kNumberOfBytecodes = |
| static_cast<size_t>(Bytecode::kLast) + 1; |
| typedef std::array<PeepholeActionAndData, kNumberOfBytecodes> Row; |
| |
| void BuildTable(); |
| void Write(std::ostream& os); |
| |
| private: |
| static const char* kIndent; |
| static const char* kNamespaceElements[]; |
| |
| void WriteHeader(std::ostream& os); |
| void WriteIncludeFiles(std::ostream& os); |
| void WriteClassMethods(std::ostream& os); |
| void WriteUniqueRows(std::ostream& os); |
| void WriteRowMap(std::ostream& os); |
| void WriteRow(std::ostream& os, size_t row_index); |
| void WriteOpenNamespace(std::ostream& os); |
| void WriteCloseNamespace(std::ostream& os); |
| |
| PeepholeActionAndData LookupActionAndData(Bytecode last, Bytecode current); |
| void BuildRow(Bytecode last, Row* row); |
| size_t HashRow(const Row* row); |
| void InsertRow(size_t row_index, const Row* const row, size_t row_hash, |
| std::map<size_t, size_t>* hash_to_row_map); |
| bool RowsEqual(const Row* const first, const Row* const second); |
| |
| std::vector<Row>* table() { return &table_; } |
| |
| // Table of unique rows. |
| std::vector<Row> table_; |
| |
| // Mapping of row index to unique row index. |
| std::array<size_t, kNumberOfBytecodes> row_map_; |
| }; |
| |
| const char* PeepholeActionTableWriter::kIndent = " "; |
| const char* PeepholeActionTableWriter::kNamespaceElements[] = {"v8", "internal", |
| "interpreter"}; |
| |
| // static |
| PeepholeActionAndData PeepholeActionTableWriter::LookupActionAndData( |
| Bytecode last, Bytecode current) { |
| // ToName bytecodes can be replaced by Star with the same output register if |
| // the value in the accumulator is already a name. |
| if (current == Bytecode::kToName && Bytecodes::PutsNameInAccumulator(last)) { |
| return {PeepholeAction::kChangeBytecodeAction, Bytecode::kStar}; |
| } |
| |
| // Nop are placeholders for holding source position information and can be |
| // elided if there is no source information. |
| if (last == Bytecode::kNop) { |
| if (Bytecodes::IsJump(current)) { |
| return {PeepholeAction::kElideLastBeforeJumpAction, Bytecode::kIllegal}; |
| } else { |
| return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; |
| } |
| } |
| |
| // The accumulator is invisible to the debugger. If there is a sequence |
| // of consecutive accumulator loads (that don't have side effects) then |
| // only the final load is potentially visible. |
| if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) && |
| Bytecodes::IsAccumulatorLoadWithoutEffects(current)) { |
| return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; |
| } |
| |
| // The current instruction clobbers the accumulator without reading |
| // it. The load in the last instruction can be elided as it has no |
| // effect. |
| if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) && |
| Bytecodes::GetAccumulatorUse(current) == AccumulatorUse::kWrite) { |
| return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; |
| } |
| |
| // Ldar and Star make the accumulator and register hold equivalent |
| // values. Only the first bytecode is needed if there's a sequence |
| // of back-to-back Ldar and Star bytecodes with the same operand. |
| if (Bytecodes::IsLdarOrStar(last) && Bytecodes::IsLdarOrStar(current)) { |
| return {PeepholeAction::kElideCurrentIfOperand0MatchesAction, |
| Bytecode::kIllegal}; |
| } |
| |
| // TODO(rmcilroy): Add elide for consecutive mov to and from the same |
| // register. |
| |
| // Remove ToBoolean coercion from conditional jumps where possible. |
| if (Bytecodes::WritesBooleanToAccumulator(last)) { |
| if (Bytecodes::IsJumpIfToBoolean(current)) { |
| return {PeepholeAction::kChangeJumpBytecodeAction, |
| Bytecodes::GetJumpWithoutToBoolean(current)}; |
| } else if (current == Bytecode::kToBooleanLogicalNot) { |
| return {PeepholeAction::kChangeBytecodeAction, Bytecode::kLogicalNot}; |
| } |
| } |
| |
| // Fuse LdaSmi followed by binary op to produce binary op with a |
| // immediate integer argument. This savaes on dispatches and size. |
| if (last == Bytecode::kLdaSmi) { |
| switch (current) { |
| case Bytecode::kAdd: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kAddSmi}; |
| case Bytecode::kSub: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kSubSmi}; |
| case Bytecode::kBitwiseAnd: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kBitwiseAndSmi}; |
| case Bytecode::kBitwiseOr: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kBitwiseOrSmi}; |
| case Bytecode::kShiftLeft: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kShiftLeftSmi}; |
| case Bytecode::kShiftRight: |
| return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, |
| Bytecode::kShiftRightSmi}; |
| default: |
| break; |
| } |
| } |
| |
| // Fuse LdaZero followed by binary op to produce binary op with a |
| // zero immediate argument. This saves dispatches, but not size. |
| if (last == Bytecode::kLdaZero) { |
| switch (current) { |
| case Bytecode::kAdd: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kAddSmi}; |
| case Bytecode::kSub: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kSubSmi}; |
| case Bytecode::kBitwiseAnd: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kBitwiseAndSmi}; |
| case Bytecode::kBitwiseOr: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kBitwiseOrSmi}; |
| case Bytecode::kShiftLeft: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kShiftLeftSmi}; |
| case Bytecode::kShiftRight: |
| return { |
| PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, |
| Bytecode::kShiftRightSmi}; |
| default: |
| break; |
| } |
| } |
| |
| // Fuse LdaNull/LdaUndefined followed by a equality comparison with test |
| // undetectable. Testing undetectable is a simple check on the map which is |
| // more efficient than the full comparison operation. |
| if (last == Bytecode::kLdaNull || last == Bytecode::kLdaUndefined) { |
| if (current == Bytecode::kTestEqual) { |
| return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction, |
| Bytecode::kTestUndetectable}; |
| } |
| } |
| |
| // Fuse LdaNull/LdaUndefined followed by a strict equals with |
| // TestNull/TestUndefined. |
| if (current == Bytecode::kTestEqualStrict) { |
| if (last == Bytecode::kLdaNull) { |
| return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction, |
| Bytecode::kTestNull}; |
| } else if (last == Bytecode::kLdaUndefined) { |
| return {PeepholeAction::kTransformEqualityWithNullOrUndefinedAction, |
| Bytecode::kTestUndefined}; |
| } |
| } |
| |
| // If there is no last bytecode to optimize against, store the incoming |
| // bytecode or for jumps emit incoming bytecode immediately. |
| if (last == Bytecode::kIllegal) { |
| if (Bytecodes::IsJump(current)) { |
| return {PeepholeAction::kUpdateLastJumpAction, Bytecode::kIllegal}; |
| } else if (current == Bytecode::kNop) { |
| return {PeepholeAction::kUpdateLastIfSourceInfoPresentAction, |
| Bytecode::kIllegal}; |
| } else { |
| return {PeepholeAction::kUpdateLastAction, Bytecode::kIllegal}; |
| } |
| } |
| |
| // No matches, take the default action. |
| if (Bytecodes::IsJump(current)) { |
| return {PeepholeAction::kDefaultJumpAction, Bytecode::kIllegal}; |
| } else { |
| return {PeepholeAction::kDefaultAction, Bytecode::kIllegal}; |
| } |
| } |
| |
| void PeepholeActionTableWriter::Write(std::ostream& os) { |
| WriteHeader(os); |
| WriteIncludeFiles(os); |
| WriteOpenNamespace(os); |
| WriteUniqueRows(os); |
| WriteRowMap(os); |
| WriteClassMethods(os); |
| WriteCloseNamespace(os); |
| } |
| |
| void PeepholeActionTableWriter::WriteHeader(std::ostream& os) { |
| os << "// Copyright 2016 the V8 project authors. All rights reserved.\n" |
| << "// Use of this source code is governed by a BSD-style license that\n" |
| << "// can be found in the LICENSE file.\n\n" |
| << "// Autogenerated by " __FILE__ ". Do not edit.\n\n"; |
| } |
| |
| void PeepholeActionTableWriter::WriteIncludeFiles(std::ostream& os) { |
| os << "#include \"src/interpreter/bytecode-peephole-table.h\"\n\n"; |
| } |
| |
| void PeepholeActionTableWriter::WriteUniqueRows(std::ostream& os) { |
| os << "const PeepholeActionAndData PeepholeActionTable::row_data_[" |
| << table_.size() << "][" << kNumberOfBytecodes << "] = {\n"; |
| for (size_t i = 0; i < table_.size(); ++i) { |
| os << "{\n"; |
| WriteRow(os, i); |
| os << "},\n"; |
| } |
| os << "};\n\n"; |
| } |
| |
| void PeepholeActionTableWriter::WriteRowMap(std::ostream& os) { |
| os << "const PeepholeActionAndData* const PeepholeActionTable::row_[" |
| << kNumberOfBytecodes << "] = {\n"; |
| for (size_t i = 0; i < kNumberOfBytecodes; ++i) { |
| os << kIndent << " PeepholeActionTable::row_data_[" << row_map_[i] |
| << "], \n"; |
| } |
| os << "};\n\n"; |
| } |
| |
| void PeepholeActionTableWriter::WriteRow(std::ostream& os, size_t row_index) { |
| const Row row = table_.at(row_index); |
| for (PeepholeActionAndData action_data : row) { |
| os << kIndent << "{" << ActionName(action_data.action) << "," |
| << BytecodeName(action_data.bytecode) << "},\n"; |
| } |
| } |
| |
| void PeepholeActionTableWriter::WriteOpenNamespace(std::ostream& os) { |
| for (auto element : kNamespaceElements) { |
| os << "namespace " << element << " {\n"; |
| } |
| os << "\n"; |
| } |
| |
| void PeepholeActionTableWriter::WriteCloseNamespace(std::ostream& os) { |
| for (auto element : kNamespaceElements) { |
| os << "} // namespace " << element << "\n"; |
| } |
| } |
| |
| void PeepholeActionTableWriter::WriteClassMethods(std::ostream& os) { |
| os << "// static\n" |
| << "const PeepholeActionAndData*\n" |
| << "PeepholeActionTable::Lookup(Bytecode last, Bytecode current) {\n" |
| << kIndent |
| << "return &row_[Bytecodes::ToByte(last)][Bytecodes::ToByte(current)];\n" |
| << "}\n\n"; |
| } |
| |
| void PeepholeActionTableWriter::BuildTable() { |
| std::map<size_t, size_t> hash_to_row_map; |
| Row row; |
| for (size_t i = 0; i < kNumberOfBytecodes; ++i) { |
| uint8_t byte_value = static_cast<uint8_t>(i); |
| Bytecode last = Bytecodes::FromByte(byte_value); |
| BuildRow(last, &row); |
| size_t row_hash = HashRow(&row); |
| InsertRow(i, &row, row_hash, &hash_to_row_map); |
| } |
| } |
| |
| void PeepholeActionTableWriter::BuildRow(Bytecode last, Row* row) { |
| for (size_t i = 0; i < kNumberOfBytecodes; ++i) { |
| uint8_t byte_value = static_cast<uint8_t>(i); |
| Bytecode current = Bytecodes::FromByte(byte_value); |
| PeepholeActionAndData action_data = LookupActionAndData(last, current); |
| row->at(i) = action_data; |
| } |
| } |
| |
| // static |
| bool PeepholeActionTableWriter::RowsEqual(const Row* const first, |
| const Row* const second) { |
| return memcmp(first, second, sizeof(*first)) == 0; |
| } |
| |
| // static |
| void PeepholeActionTableWriter::InsertRow( |
| size_t row_index, const Row* const row, size_t row_hash, |
| std::map<size_t, size_t>* hash_to_row_map) { |
| // Insert row if no existing row matches, otherwise use existing row. |
| auto iter = hash_to_row_map->find(row_hash); |
| if (iter == hash_to_row_map->end()) { |
| row_map_[row_index] = table()->size(); |
| table()->push_back(*row); |
| } else { |
| row_map_[row_index] = iter->second; |
| |
| // If the following DCHECK fails, the HashRow() is not adequate. |
| DCHECK(RowsEqual(&table()->at(iter->second), row)); |
| } |
| } |
| |
| // static |
| size_t PeepholeActionTableWriter::HashRow(const Row* row) { |
| static const size_t kHashShift = 3; |
| std::size_t result = (1u << 31) - 1u; |
| const uint8_t* raw_data = reinterpret_cast<const uint8_t*>(row); |
| for (size_t i = 0; i < sizeof(*row); ++i) { |
| size_t top_bits = result >> (kBitsPerByte * sizeof(size_t) - kHashShift); |
| result = (result << kHashShift) ^ top_bits ^ raw_data[i]; |
| } |
| return result; |
| } |
| |
| } // namespace interpreter |
| } // namespace internal |
| } // namespace v8 |
| |
| int main(int argc, const char* argv[]) { |
| CHECK_EQ(argc, 2); |
| |
| std::ofstream ofs(argv[1], std::ofstream::trunc); |
| v8::internal::interpreter::PeepholeActionTableWriter writer; |
| writer.BuildTable(); |
| writer.Write(ofs); |
| ofs.flush(); |
| ofs.close(); |
| |
| return 0; |
| } |