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