Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(73)

Side by Side Diff: src/interpreter/mkpeephole.cc

Issue 2118183002: [interpeter] Move to table based peephole optimizer. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Broader check for host and target arch wanting separate toolchain. Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/interpreter/bytecodes.cc ('k') | src/v8.gyp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 }
OLDNEW
« no previous file with comments | « src/interpreter/bytecodes.cc ('k') | src/v8.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698