| OLD | NEW |
|---|
| (Empty) |
| 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 // Optimize various accumulator loads followed by store accumulator | |
| 83 // to an equivalent register load and loading the accumulator with | |
| 84 // the register. The latter accumulator load can often be elided as | |
| 85 // it is side-effect free and often followed by another accumulator | |
| 86 // load so can be elided. | |
| 87 if (current == Bytecode::kStar) { | |
| 88 switch (last) { | |
| 89 case Bytecode::kLdaNamedProperty: | |
| 90 return {PeepholeAction::kTransformLdaStarToLdrLdarAction, | |
| 91 Bytecode::kLdrNamedProperty}; | |
| 92 case Bytecode::kLdaKeyedProperty: | |
| 93 return {PeepholeAction::kTransformLdaStarToLdrLdarAction, | |
| 94 Bytecode::kLdrKeyedProperty}; | |
| 95 case Bytecode::kLdaGlobal: | |
| 96 return {PeepholeAction::kTransformLdaStarToLdrLdarAction, | |
| 97 Bytecode::kLdrGlobal}; | |
| 98 case Bytecode::kLdaContextSlot: | |
| 99 return {PeepholeAction::kTransformLdaStarToLdrLdarAction, | |
| 100 Bytecode::kLdrContextSlot}; | |
| 101 case Bytecode::kLdaUndefined: | |
| 102 return {PeepholeAction::kTransformLdaStarToLdrLdarAction, | |
| 103 Bytecode::kLdrUndefined}; | |
| 104 default: | |
| 105 break; | |
| 106 } | |
| 107 } | |
| 108 | |
| 109 // ToName optimizations: remove unnecessary ToName bytecodes. | |
| 110 if (current == Bytecode::kToName) { | |
| 111 if (last == Bytecode::kLdaConstant) { | |
| 112 return {PeepholeAction::kElideCurrentIfLoadingNameConstantAction, | |
| 113 Bytecode::kIllegal}; | |
| 114 } else if (Bytecodes::PutsNameInAccumulator(last)) { | |
| 115 return {PeepholeAction::kElideCurrentAction, Bytecode::kIllegal}; | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 // Nop are placeholders for holding source position information and can be | |
| 120 // elided if there is no source information. | |
| 121 if (last == Bytecode::kNop) { | |
| 122 if (Bytecodes::IsJump(current)) { | |
| 123 return {PeepholeAction::kElideLastBeforeJumpAction, Bytecode::kIllegal}; | |
| 124 } else { | |
| 125 return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; | |
| 126 } | |
| 127 } | |
| 128 | |
| 129 // The accumulator is invisible to the debugger. If there is a sequence | |
| 130 // of consecutive accumulator loads (that don't have side effects) then | |
| 131 // only the final load is potentially visible. | |
| 132 if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) && | |
| 133 Bytecodes::IsAccumulatorLoadWithoutEffects(current)) { | |
| 134 return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; | |
| 135 } | |
| 136 | |
| 137 // The current instruction clobbers the accumulator without reading | |
| 138 // it. The load in the last instruction can be elided as it has no | |
| 139 // effect. | |
| 140 if (Bytecodes::IsAccumulatorLoadWithoutEffects(last) && | |
| 141 Bytecodes::GetAccumulatorUse(current) == AccumulatorUse::kWrite) { | |
| 142 return {PeepholeAction::kElideLastAction, Bytecode::kIllegal}; | |
| 143 } | |
| 144 | |
| 145 // Ldar and Star make the accumulator and register hold equivalent | |
| 146 // values. Only the first bytecode is needed if there's a sequence | |
| 147 // of back-to-back Ldar and Star bytecodes with the same operand. | |
| 148 if (Bytecodes::IsLdarOrStar(last) && Bytecodes::IsLdarOrStar(current)) { | |
| 149 return {PeepholeAction::kElideCurrentIfOperand0MatchesAction, | |
| 150 Bytecode::kIllegal}; | |
| 151 } | |
| 152 | |
| 153 // Remove ToBoolean coercion from conditional jumps where possible. | |
| 154 if (Bytecodes::WritesBooleanToAccumulator(last)) { | |
| 155 if (Bytecodes::IsJumpIfToBoolean(current)) { | |
| 156 return {PeepholeAction::kChangeJumpBytecodeAction, | |
| 157 Bytecodes::GetJumpWithoutToBoolean(current)}; | |
| 158 } else if (current == Bytecode::kToBooleanLogicalNot) { | |
| 159 return {PeepholeAction::kChangeBytecodeAction, Bytecode::kLogicalNot}; | |
| 160 } | |
| 161 } | |
| 162 | |
| 163 // Fuse LdaSmi followed by binary op to produce binary op with a | |
| 164 // immediate integer argument. This savaes on dispatches and size. | |
| 165 if (last == Bytecode::kLdaSmi) { | |
| 166 switch (current) { | |
| 167 case Bytecode::kAdd: | |
| 168 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 169 Bytecode::kAddSmi}; | |
| 170 case Bytecode::kSub: | |
| 171 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 172 Bytecode::kSubSmi}; | |
| 173 case Bytecode::kBitwiseAnd: | |
| 174 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 175 Bytecode::kBitwiseAndSmi}; | |
| 176 case Bytecode::kBitwiseOr: | |
| 177 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 178 Bytecode::kBitwiseOrSmi}; | |
| 179 case Bytecode::kShiftLeft: | |
| 180 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 181 Bytecode::kShiftLeftSmi}; | |
| 182 case Bytecode::kShiftRight: | |
| 183 return {PeepholeAction::kTransformLdaSmiBinaryOpToBinaryOpWithSmiAction, | |
| 184 Bytecode::kShiftRightSmi}; | |
| 185 default: | |
| 186 break; | |
| 187 } | |
| 188 } | |
| 189 | |
| 190 // Fuse LdaZero followed by binary op to produce binary op with a | |
| 191 // zero immediate argument. This saves dispatches, but not size. | |
| 192 if (last == Bytecode::kLdaZero) { | |
| 193 switch (current) { | |
| 194 case Bytecode::kAdd: | |
| 195 return { | |
| 196 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 197 Bytecode::kAddSmi}; | |
| 198 case Bytecode::kSub: | |
| 199 return { | |
| 200 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 201 Bytecode::kSubSmi}; | |
| 202 case Bytecode::kBitwiseAnd: | |
| 203 return { | |
| 204 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 205 Bytecode::kBitwiseAndSmi}; | |
| 206 case Bytecode::kBitwiseOr: | |
| 207 return { | |
| 208 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 209 Bytecode::kBitwiseOrSmi}; | |
| 210 case Bytecode::kShiftLeft: | |
| 211 return { | |
| 212 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 213 Bytecode::kShiftLeftSmi}; | |
| 214 case Bytecode::kShiftRight: | |
| 215 return { | |
| 216 PeepholeAction::kTransformLdaZeroBinaryOpToBinaryOpWithZeroAction, | |
| 217 Bytecode::kShiftRightSmi}; | |
| 218 default: | |
| 219 break; | |
| 220 } | |
| 221 } | |
| 222 | |
| 223 // If there is no last bytecode to optimize against, store the incoming | |
| 224 // bytecode or for jumps emit incoming bytecode immediately. | |
| 225 if (last == Bytecode::kIllegal) { | |
| 226 if (Bytecodes::IsJump(current)) { | |
| 227 return {PeepholeAction::kUpdateLastJumpAction, Bytecode::kIllegal}; | |
| 228 } else if (current == Bytecode::kNop) { | |
| 229 return {PeepholeAction::kUpdateLastIfSourceInfoPresentAction, | |
| 230 Bytecode::kIllegal}; | |
| 231 } else { | |
| 232 return {PeepholeAction::kUpdateLastAction, Bytecode::kIllegal}; | |
| 233 } | |
| 234 } | |
| 235 | |
| 236 // No matches, take the default action. | |
| 237 if (Bytecodes::IsJump(current)) { | |
| 238 return {PeepholeAction::kDefaultJumpAction, Bytecode::kIllegal}; | |
| 239 } else { | |
| 240 return {PeepholeAction::kDefaultAction, Bytecode::kIllegal}; | |
| 241 } | |
| 242 } | |
| 243 | |
| 244 void PeepholeActionTableWriter::Write(std::ostream& os) { | |
| 245 WriteHeader(os); | |
| 246 WriteIncludeFiles(os); | |
| 247 WriteOpenNamespace(os); | |
| 248 WriteUniqueRows(os); | |
| 249 WriteRowMap(os); | |
| 250 WriteClassMethods(os); | |
| 251 WriteCloseNamespace(os); | |
| 252 } | |
| 253 | |
| 254 void PeepholeActionTableWriter::WriteHeader(std::ostream& os) { | |
| 255 os << "// Copyright 2016 the V8 project authors. All rights reserved.\n" | |
| 256 << "// Use of this source code is governed by a BSD-style license that\n" | |
| 257 << "// can be found in the LICENSE file.\n\n" | |
| 258 << "// Autogenerated by " __FILE__ ". Do not edit.\n\n"; | |
| 259 } | |
| 260 | |
| 261 void PeepholeActionTableWriter::WriteIncludeFiles(std::ostream& os) { | |
| 262 os << "#include \"src/interpreter/bytecode-peephole-table.h\"\n\n"; | |
| 263 } | |
| 264 | |
| 265 void PeepholeActionTableWriter::WriteUniqueRows(std::ostream& os) { | |
| 266 os << "const PeepholeActionAndData PeepholeActionTable::row_data_[" | |
| 267 << table_.size() << "][" << kNumberOfBytecodes << "] = {\n"; | |
| 268 for (size_t i = 0; i < table_.size(); ++i) { | |
| 269 os << "{\n"; | |
| 270 WriteRow(os, i); | |
| 271 os << "},\n"; | |
| 272 } | |
| 273 os << "};\n\n"; | |
| 274 } | |
| 275 | |
| 276 void PeepholeActionTableWriter::WriteRowMap(std::ostream& os) { | |
| 277 os << "const PeepholeActionAndData* const PeepholeActionTable::row_[" | |
| 278 << kNumberOfBytecodes << "] = {\n"; | |
| 279 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { | |
| 280 os << kIndent << " PeepholeActionTable::row_data_[" << row_map_[i] | |
| 281 << "], \n"; | |
| 282 } | |
| 283 os << "};\n\n"; | |
| 284 } | |
| 285 | |
| 286 void PeepholeActionTableWriter::WriteRow(std::ostream& os, size_t row_index) { | |
| 287 const Row row = table_.at(row_index); | |
| 288 for (PeepholeActionAndData action_data : row) { | |
| 289 os << kIndent << "{" << ActionName(action_data.action) << "," | |
| 290 << BytecodeName(action_data.bytecode) << "},\n"; | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 void PeepholeActionTableWriter::WriteOpenNamespace(std::ostream& os) { | |
| 295 for (auto element : kNamespaceElements) { | |
| 296 os << "namespace " << element << " {\n"; | |
| 297 } | |
| 298 os << "\n"; | |
| 299 } | |
| 300 | |
| 301 void PeepholeActionTableWriter::WriteCloseNamespace(std::ostream& os) { | |
| 302 for (auto element : kNamespaceElements) { | |
| 303 os << "} // namespace " << element << "\n"; | |
| 304 } | |
| 305 } | |
| 306 | |
| 307 void PeepholeActionTableWriter::WriteClassMethods(std::ostream& os) { | |
| 308 os << "// static\n" | |
| 309 << "const PeepholeActionAndData*\n" | |
| 310 << "PeepholeActionTable::Lookup(Bytecode last, Bytecode current) {\n" | |
| 311 << kIndent | |
| 312 << "return &row_[Bytecodes::ToByte(last)][Bytecodes::ToByte(current)];\n" | |
| 313 << "}\n\n"; | |
| 314 } | |
| 315 | |
| 316 void PeepholeActionTableWriter::BuildTable() { | |
| 317 std::map<size_t, size_t> hash_to_row_map; | |
| 318 Row row; | |
| 319 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { | |
| 320 uint8_t byte_value = static_cast<uint8_t>(i); | |
| 321 Bytecode last = Bytecodes::FromByte(byte_value); | |
| 322 BuildRow(last, &row); | |
| 323 size_t row_hash = HashRow(&row); | |
| 324 InsertRow(i, &row, row_hash, &hash_to_row_map); | |
| 325 } | |
| 326 } | |
| 327 | |
| 328 void PeepholeActionTableWriter::BuildRow(Bytecode last, Row* row) { | |
| 329 for (size_t i = 0; i < kNumberOfBytecodes; ++i) { | |
| 330 uint8_t byte_value = static_cast<uint8_t>(i); | |
| 331 Bytecode current = Bytecodes::FromByte(byte_value); | |
| 332 PeepholeActionAndData action_data = LookupActionAndData(last, current); | |
| 333 row->at(i) = action_data; | |
| 334 } | |
| 335 } | |
| 336 | |
| 337 // static | |
| 338 bool PeepholeActionTableWriter::RowsEqual(const Row* const first, | |
| 339 const Row* const second) { | |
| 340 return memcmp(first, second, sizeof(*first)) == 0; | |
| 341 } | |
| 342 | |
| 343 // static | |
| 344 void PeepholeActionTableWriter::InsertRow( | |
| 345 size_t row_index, const Row* const row, size_t row_hash, | |
| 346 std::map<size_t, size_t>* hash_to_row_map) { | |
| 347 // Insert row if no existing row matches, otherwise use existing row. | |
| 348 auto iter = hash_to_row_map->find(row_hash); | |
| 349 if (iter == hash_to_row_map->end()) { | |
| 350 row_map_[row_index] = table()->size(); | |
| 351 table()->push_back(*row); | |
| 352 } else { | |
| 353 row_map_[row_index] = iter->second; | |
| 354 | |
| 355 // If the following DCHECK fails, the HashRow() is not adequate. | |
| 356 DCHECK(RowsEqual(&table()->at(iter->second), row)); | |
| 357 } | |
| 358 } | |
| 359 | |
| 360 // static | |
| 361 size_t PeepholeActionTableWriter::HashRow(const Row* row) { | |
| 362 static const size_t kHashShift = 3; | |
| 363 std::size_t result = (1u << 31) - 1u; | |
| 364 const uint8_t* raw_data = reinterpret_cast<const uint8_t*>(row); | |
| 365 for (size_t i = 0; i < sizeof(*row); ++i) { | |
| 366 size_t top_bits = result >> (kBitsPerByte * sizeof(size_t) - kHashShift); | |
| 367 result = (result << kHashShift) ^ top_bits ^ raw_data[i]; | |
| 368 } | |
| 369 return result; | |
| 370 } | |
| 371 | |
| 372 } // namespace interpreter | |
| 373 } // namespace internal | |
| 374 } // namespace v8 | |
| 375 | |
| 376 int main(int argc, const char* argv[]) { | |
| 377 CHECK_EQ(argc, 2); | |
| 378 | |
| 379 std::ofstream ofs(argv[1], std::ofstream::trunc); | |
| 380 v8::internal::interpreter::PeepholeActionTableWriter writer; | |
| 381 writer.BuildTable(); | |
| 382 writer.Write(ofs); | |
| 383 ofs.flush(); | |
| 384 ofs.close(); | |
| 385 | |
| 386 return 0; | |
| 387 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2161563002:
Revert of [interpeter] Move to table based peephole optimizer. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master