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 15 namespace v8 { 16 namespace internal { 17 18 namespace interpreter { 19 20 const 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 33 std::string BytecodeName(Bytecode bytecode) { 34 return "Bytecode::k" + std::string(Bytecodes::ToString(bytecode)); 35 } 36 37 class 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 75 const char* PeepholeActionTableWriter::kIndent = " "; 76 const char* PeepholeActionTableWriter::kNamespaceElements[] = {"v8", "internal", 77 "interpreter"}; 78 79 // static 80 PeepholeActionAndData 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 // If there is no last bytecode to optimize against, store the incoming 196 // bytecode or for jumps emit incoming bytecode immediately. 197 if (last == Bytecode::kIllegal) { 198 if (Bytecodes::IsJump(current)) { 199 return {PeepholeAction::kUpdateLastJumpAction, Bytecode::kIllegal}; 200 } else if (current == Bytecode::kNop) { 201 return {PeepholeAction::kUpdateLastIfSourceInfoPresentAction, 202 Bytecode::kIllegal}; 203 } else { 204 return {PeepholeAction::kUpdateLastAction, Bytecode::kIllegal}; 205 } 206 } 207 208 // No matches, take the default action. 209 if (Bytecodes::IsJump(current)) { 210 return {PeepholeAction::kDefaultJumpAction, Bytecode::kIllegal}; 211 } else { 212 return {PeepholeAction::kDefaultAction, Bytecode::kIllegal}; 213 } 214 } 215 216 void PeepholeActionTableWriter::Write(std::ostream& os) { 217 WriteHeader(os); 218 WriteIncludeFiles(os); 219 WriteOpenNamespace(os); 220 WriteUniqueRows(os); 221 WriteRowMap(os); 222 WriteClassMethods(os); 223 WriteCloseNamespace(os); 224 } 225 226 void PeepholeActionTableWriter::WriteHeader(std::ostream& os) { 227 os << "// Copyright 2016 the V8 project authors. All rights reserved.\n" 228 << "// Use of this source code is governed by a BSD-style license that\n" 229 << "// can be found in the LICENSE file.\n\n" 230 << "// Autogenerated by " __FILE__ ". Do not edit.\n\n"; 231 } 232 233 void PeepholeActionTableWriter::WriteIncludeFiles(std::ostream& os) { 234 os << "#include \"src/interpreter/bytecode-peephole-table.h\"\n\n"; 235 } 236 237 void PeepholeActionTableWriter::WriteUniqueRows(std::ostream& os) { 238 os << "const PeepholeActionAndData PeepholeActionTable::row_data_[" 239 << table_.size() << "][" << kNumberOfBytecodes << "] = {\n"; 240 for (size_t i = 0; i < table_.size(); ++i) { 241 os << "{\n"; 242 WriteRow(os, i); 243 os << "},\n"; 244 } 245 os << "};\n\n"; 246 } 247 248 void PeepholeActionTableWriter::WriteRowMap(std::ostream& os) { 249 os << "const PeepholeActionAndData* const PeepholeActionTable::row_[" 250 << kNumberOfBytecodes << "] = {\n"; 251 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { 252 os << kIndent << " PeepholeActionTable::row_data_[" << row_map_[i] 253 << "], \n"; 254 } 255 os << "};\n\n"; 256 } 257 258 void PeepholeActionTableWriter::WriteRow(std::ostream& os, size_t row_index) { 259 const Row row = table_.at(row_index); 260 for (PeepholeActionAndData action_data : row) { 261 os << kIndent << "{" << ActionName(action_data.action) << "," 262 << BytecodeName(action_data.bytecode) << "},\n"; 263 } 264 } 265 266 void PeepholeActionTableWriter::WriteOpenNamespace(std::ostream& os) { 267 for (auto element : kNamespaceElements) { 268 os << "namespace " << element << " {\n"; 269 } 270 os << "\n"; 271 } 272 273 void PeepholeActionTableWriter::WriteCloseNamespace(std::ostream& os) { 274 for (auto element : kNamespaceElements) { 275 os << "} // namespace " << element << "\n"; 276 } 277 } 278 279 void PeepholeActionTableWriter::WriteClassMethods(std::ostream& os) { 280 os << "// static\n" 281 << "const PeepholeActionAndData*\n" 282 << "PeepholeActionTable::Lookup(Bytecode last, Bytecode current) {\n" 283 << kIndent 284 << "return &row_[Bytecodes::ToByte(last)][Bytecodes::ToByte(current)];\n" 285 << "}\n\n"; 286 } 287 288 void PeepholeActionTableWriter::BuildTable() { 289 std::map<size_t, size_t> hash_to_row_map; 290 Row row; 291 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { 292 uint8_t byte_value = static_cast<uint8_t>(i); 293 Bytecode last = Bytecodes::FromByte(byte_value); 294 BuildRow(last, &row); 295 size_t row_hash = HashRow(&row); 296 InsertRow(i, &row, row_hash, &hash_to_row_map); 297 } 298 } 299 300 void PeepholeActionTableWriter::BuildRow(Bytecode last, Row* row) { 301 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { 302 uint8_t byte_value = static_cast<uint8_t>(i); 303 Bytecode current = Bytecodes::FromByte(byte_value); 304 PeepholeActionAndData action_data = LookupActionAndData(last, current); 305 row->at(i) = action_data; 306 } 307 } 308 309 // static 310 bool PeepholeActionTableWriter::RowsEqual(const Row* const first, 311 const Row* const second) { 312 return memcmp(first, second, sizeof(*first)) == 0; 313 } 314 315 // static 316 void PeepholeActionTableWriter::InsertRow( 317 size_t row_index, const Row* const row, size_t row_hash, 318 std::map<size_t, size_t>* hash_to_row_map) { 319 // Insert row if no existing row matches, otherwise use existing row. 320 auto iter = hash_to_row_map->find(row_hash); 321 if (iter == hash_to_row_map->end()) { 322 row_map_[row_index] = table()->size(); 323 table()->push_back(*row); 324 } else { 325 row_map_[row_index] = iter->second; 326 327 // If the following DCHECK fails, the HashRow() is not adequate. 328 DCHECK(RowsEqual(&table()->at(iter->second), row)); 329 } 330 } 331 332 // static 333 size_t PeepholeActionTableWriter::HashRow(const Row* row) { 334 static const size_t kHashShift = 3; 335 std::size_t result = (1u << 31) - 1u; 336 const uint8_t* raw_data = reinterpret_cast<const uint8_t*>(row); 337 for (size_t i = 0; i < sizeof(*row); ++i) { 338 size_t top_bits = result >> (kBitsPerByte * sizeof(size_t) - kHashShift); 339 result = (result << kHashShift) ^ top_bits ^ raw_data[i]; 340 } 341 return result; 342 } 343 344 } // namespace interpreter 345 } // namespace internal 346 } // namespace v8 347 348 int main(int argc, const char* argv[]) { 349 CHECK_EQ(argc, 2); 350 351 std::ofstream ofs(argv[1], std::ofstream::trunc); 352 v8::internal::interpreter::PeepholeActionTableWriter writer; 353 writer.BuildTable(); 354 writer.Write(ofs); 355 ofs.flush(); 356 ofs.close(); 357 358 return 0; 359 } 360