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