bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "bytecode.h"
3
4#include "ic.h"
5#include "runtime.h"
6
7namespace py {
8
9const char* const kBytecodeNames[] = {
10#define NAME(name, value, handler) #name,
11 FOREACH_BYTECODE(NAME)
12#undef NAME
13};
14
15BytecodeOp nextBytecodeOp(const MutableBytes& bytecode, word* index) {
16 word i = *index;
17 Bytecode bc = rewrittenBytecodeOpAt(bytecode, i);
18 int32_t arg = rewrittenBytecodeArgAt(bytecode, i);
19 uint16_t cache = rewrittenBytecodeCacheAt(bytecode, i);
20 i++;
21 while (bc == Bytecode::EXTENDED_ARG) {
22 bc = rewrittenBytecodeOpAt(bytecode, i);
23 arg = (arg << kBitsPerByte) | rewrittenBytecodeArgAt(bytecode, i);
24 i++;
25 }
26 DCHECK(i - *index <= 8, "EXTENDED_ARG-encoded arg must fit in int32_t");
27 *index = i;
28 return BytecodeOp{bc, arg, cache};
29}
30
31const word kOpcodeOffset = 0;
32const word kArgOffset = 1;
33const word kCacheOffset = 2;
34
35word bytecodeLength(const Bytes& bytecode) {
36 return bytecode.length() / kCompilerCodeUnitSize;
37}
38
39Bytecode bytecodeOpAt(const Bytes& bytecode, word index) {
40 return static_cast<Bytecode>(
41 bytecode.byteAt(index * kCompilerCodeUnitSize + kOpcodeOffset));
42}
43
44byte bytecodeArgAt(const Bytes& bytecode, word index) {
45 return bytecode.byteAt(index * kCompilerCodeUnitSize + kArgOffset);
46}
47
48word rewrittenBytecodeLength(const MutableBytes& bytecode) {
49 return bytecode.length() / kCodeUnitSize;
50}
51
52Bytecode rewrittenBytecodeOpAt(const MutableBytes& bytecode, word index) {
53 return static_cast<Bytecode>(
54 bytecode.byteAt(index * kCodeUnitSize + kOpcodeOffset));
55}
56
57void rewrittenBytecodeOpAtPut(const MutableBytes& bytecode, word index,
58 Bytecode op) {
59 bytecode.byteAtPut(index * kCodeUnitSize + kOpcodeOffset,
60 static_cast<byte>(op));
61}
62
63byte rewrittenBytecodeArgAt(const MutableBytes& bytecode, word index) {
64 return bytecode.byteAt(index * kCodeUnitSize + kArgOffset);
65}
66
67void rewrittenBytecodeArgAtPut(const MutableBytes& bytecode, word index,
68 byte arg) {
69 bytecode.byteAtPut(index * kCodeUnitSize + kArgOffset, arg);
70}
71
72uint16_t rewrittenBytecodeCacheAt(const MutableBytes& bytecode, word index) {
73 return bytecode.uint16At(index * kCodeUnitSize + kCacheOffset);
74}
75
76void rewrittenBytecodeCacheAtPut(const MutableBytes& bytecode, word index,
77 uint16_t cache) {
78 bytecode.uint16AtPut(index * kCodeUnitSize + kCacheOffset, cache);
79}
80
81int8_t opargFromObject(RawObject object) {
82 DCHECK(!object.isHeapObject(), "Heap objects are disallowed");
83 return static_cast<int8_t>(object.raw());
84}
85
86struct RewrittenOp {
87 Bytecode bc;
88 int32_t arg;
89 bool needs_inline_cache;
90};
91
92static RewrittenOp rewriteOperation(const Function& function, BytecodeOp op) {
93 auto cached_binop = [](Interpreter::BinaryOp bin_op) {
94 return RewrittenOp{BINARY_OP_ANAMORPHIC, static_cast<int32_t>(bin_op),
95 true};
96 };
97 auto cached_inplace = [](Interpreter::BinaryOp bin_op) {
98 return RewrittenOp{INPLACE_OP_ANAMORPHIC, static_cast<int32_t>(bin_op),
99 true};
100 };
101 auto cached_unop = [](Interpreter::UnaryOp unary_op) {
102 // TODO(emacs): Add caching for methods on non-smallints
103 return RewrittenOp{UNARY_OP_ANAMORPHIC, static_cast<int32_t>(unary_op),
104 false};
105 };
106 switch (op.bc) {
107 case BINARY_ADD:
108 return cached_binop(Interpreter::BinaryOp::ADD);
109 case BINARY_AND:
110 return cached_binop(Interpreter::BinaryOp::AND);
111 case BINARY_FLOOR_DIVIDE:
112 return cached_binop(Interpreter::BinaryOp::FLOORDIV);
113 case BINARY_LSHIFT:
114 return cached_binop(Interpreter::BinaryOp::LSHIFT);
115 case BINARY_MATRIX_MULTIPLY:
116 return cached_binop(Interpreter::BinaryOp::MATMUL);
117 case BINARY_MODULO:
118 return cached_binop(Interpreter::BinaryOp::MOD);
119 case BINARY_MULTIPLY:
120 return cached_binop(Interpreter::BinaryOp::MUL);
121 case BINARY_OR:
122 return cached_binop(Interpreter::BinaryOp::OR);
123 case BINARY_POWER:
124 return cached_binop(Interpreter::BinaryOp::POW);
125 case BINARY_RSHIFT:
126 return cached_binop(Interpreter::BinaryOp::RSHIFT);
127 case BINARY_SUBSCR:
128 return RewrittenOp{BINARY_SUBSCR_ANAMORPHIC, op.arg, true};
129 case BINARY_SUBTRACT:
130 return cached_binop(Interpreter::BinaryOp::SUB);
131 case BINARY_TRUE_DIVIDE:
132 return cached_binop(Interpreter::BinaryOp::TRUEDIV);
133 case BINARY_XOR:
134 return cached_binop(Interpreter::BinaryOp::XOR);
135 case COMPARE_OP:
136 switch (op.arg) {
137 case CompareOp::LT:
138 case CompareOp::LE:
139 case CompareOp::EQ:
140 case CompareOp::NE:
141 case CompareOp::GT:
142 case CompareOp::GE:
143 return RewrittenOp{COMPARE_OP_ANAMORPHIC, op.arg, true};
144 case CompareOp::IN:
145 return RewrittenOp{COMPARE_IN_ANAMORPHIC, 0, true};
146 // TODO(T61327107): Implement COMPARE_NOT_IN.
147 case CompareOp::IS:
148 return RewrittenOp{COMPARE_IS, 0, false};
149 case CompareOp::IS_NOT:
150 return RewrittenOp{COMPARE_IS_NOT, 0, false};
151 }
152 break;
153 case CALL_FUNCTION:
154 return RewrittenOp{CALL_FUNCTION_ANAMORPHIC, op.arg, true};
155 case FOR_ITER:
156 return RewrittenOp{FOR_ITER_ANAMORPHIC, op.arg, true};
157 case INPLACE_ADD:
158 return cached_inplace(Interpreter::BinaryOp::ADD);
159 case INPLACE_AND:
160 return cached_inplace(Interpreter::BinaryOp::AND);
161 case INPLACE_FLOOR_DIVIDE:
162 return cached_inplace(Interpreter::BinaryOp::FLOORDIV);
163 case INPLACE_LSHIFT:
164 return cached_inplace(Interpreter::BinaryOp::LSHIFT);
165 case INPLACE_MATRIX_MULTIPLY:
166 return cached_inplace(Interpreter::BinaryOp::MATMUL);
167 case INPLACE_MODULO:
168 return cached_inplace(Interpreter::BinaryOp::MOD);
169 case INPLACE_MULTIPLY:
170 return cached_inplace(Interpreter::BinaryOp::MUL);
171 case INPLACE_OR:
172 return cached_inplace(Interpreter::BinaryOp::OR);
173 case INPLACE_POWER:
174 return cached_inplace(Interpreter::BinaryOp::POW);
175 case INPLACE_RSHIFT:
176 return cached_inplace(Interpreter::BinaryOp::RSHIFT);
177 case INPLACE_SUBTRACT:
178 return cached_inplace(Interpreter::BinaryOp::SUB);
179 case INPLACE_TRUE_DIVIDE:
180 return cached_inplace(Interpreter::BinaryOp::TRUEDIV);
181 case INPLACE_XOR:
182 return cached_inplace(Interpreter::BinaryOp::XOR);
183 // TODO(emacs): Fill in other unary ops
184 case UNARY_NEGATIVE:
185 return cached_unop(Interpreter::UnaryOp::NEGATIVE);
186 case LOAD_ATTR:
187 return RewrittenOp{LOAD_ATTR_ANAMORPHIC, op.arg, true};
188 case LOAD_FAST: {
189 CHECK(op.arg < Code::cast(function.code()).nlocals(),
190 "unexpected local number");
191 word total_locals = function.totalLocals();
192 // Check if the original opcode uses an extended arg
193 if (op.arg > kMaxByte) {
194 break;
195 }
196 int32_t reverse_arg = total_locals - op.arg - 1;
197 // Check that the new value fits in a byte
198 if (reverse_arg > kMaxByte) {
199 break;
200 }
201 return RewrittenOp{LOAD_FAST_REVERSE, reverse_arg, false};
202 }
203 case LOAD_METHOD:
204 return RewrittenOp{LOAD_METHOD_ANAMORPHIC, op.arg, true};
205 case STORE_ATTR:
206 return RewrittenOp{STORE_ATTR_ANAMORPHIC, op.arg, true};
207 case STORE_FAST: {
208 CHECK(op.arg < Code::cast(function.code()).nlocals(),
209 "unexpected local number");
210 // Check if the original opcode uses an extended arg
211 if (op.arg > kMaxByte) {
212 break;
213 }
214 word total_locals = function.totalLocals();
215 int32_t reverse_arg = total_locals - op.arg - 1;
216 // Check that the new value fits in a byte
217 if (reverse_arg > kMaxByte) {
218 break;
219 }
220 return RewrittenOp{STORE_FAST_REVERSE, reverse_arg, false};
221 }
222 case STORE_SUBSCR:
223 return RewrittenOp{STORE_SUBSCR_ANAMORPHIC, op.arg, true};
224 case LOAD_CONST: {
225 RawObject arg_obj =
226 Tuple::cast(Code::cast(function.code()).consts()).at(op.arg);
227 if (!arg_obj.isHeapObject()) {
228 if (arg_obj.isBool()) {
229 // We encode true/false not as 1/0 but as 0x80/0 to save an x86
230 // assembly instruction; moving the value to the 2nd byte can be done
231 // with a multiplication by 2 as part of an address expression rather
232 // than needing a separate shift by 8 in the 1/0 variant.
233 return RewrittenOp{LOAD_BOOL, Bool::cast(arg_obj).value() ? 0x80 : 0,
234 false};
235 }
236 // This condition is true only the object fits in a byte. Some
237 // immediate values of SmallInt and SmallStr do not satify this
238 // condition.
239 if (arg_obj == objectFromOparg(opargFromObject(arg_obj))) {
240 return RewrittenOp{LOAD_IMMEDIATE, opargFromObject(arg_obj), false};
241 }
242 }
243 } break;
244 case BINARY_OP_ANAMORPHIC:
245 case COMPARE_OP_ANAMORPHIC:
246 case FOR_ITER_ANAMORPHIC:
247 case INPLACE_OP_ANAMORPHIC:
248 case LOAD_ATTR_ANAMORPHIC:
249 case LOAD_FAST_REVERSE:
250 case LOAD_METHOD_ANAMORPHIC:
251 case STORE_ATTR_ANAMORPHIC:
252 case UNARY_OP_ANAMORPHIC:
253 UNREACHABLE("should not have cached opcode in input");
254 default:
255 break;
256 }
257 return RewrittenOp{UNUSED_BYTECODE_0, 0, false};
258}
259
260RawObject expandBytecode(Thread* thread, const Bytes& bytecode) {
261 // Bytecode comes in in (OP, ARG) pairs. Bytecode goes out in (OP, ARG,
262 // CACHE, CACHE) four-tuples.
263 HandleScope scope(thread);
264 word num_opcodes = bytecodeLength(bytecode);
265 MutableBytes result(&scope, thread->runtime()->newMutableBytesUninitialized(
266 num_opcodes * kCodeUnitSize));
267 for (word i = 0; i < num_opcodes; i++) {
268 rewrittenBytecodeOpAtPut(result, i, bytecodeOpAt(bytecode, i));
269 rewrittenBytecodeArgAtPut(result, i, bytecodeArgAt(bytecode, i));
270 rewrittenBytecodeCacheAtPut(result, i, 0);
271 }
272 return *result;
273}
274
275static const word kMaxCaches = 65536;
276
277void rewriteBytecode(Thread* thread, const Function& function) {
278 HandleScope scope(thread);
279 Runtime* runtime = thread->runtime();
280 // Add cache entries for global variables.
281 // TODO(T58223091): This is going to over allocate somewhat in order
282 // to simplify the indexing arithmetic. Not all names are used for
283 // globals, some are used for attributes. This is good enough for
284 // now.
285 word names_length = Tuple::cast(Code::cast(function.code()).names()).length();
286 word num_global_caches = Utils::roundUpDiv(names_length, kIcPointersPerEntry);
287 if (!function.hasOptimizedOrNewlocals()) {
288 if (num_global_caches > 0) {
289 MutableTuple caches(&scope, runtime->newMutableTuple(
290 num_global_caches * kIcPointersPerEntry));
291 caches.fill(NoneType::object());
292 function.setCaches(*caches);
293 }
294 return;
295 }
296 MutableBytes bytecode(&scope, function.rewrittenBytecode());
297 word num_opcodes = rewrittenBytecodeLength(bytecode);
298 word cache = num_global_caches;
299 for (word i = 0; i < num_opcodes;) {
300 BytecodeOp op = nextBytecodeOp(bytecode, &i);
301 word previous_index = i - 1;
302 RewrittenOp rewritten = rewriteOperation(function, op);
303 if (rewritten.bc == UNUSED_BYTECODE_0) continue;
304 if (rewritten.needs_inline_cache) {
305 if (cache < kMaxCaches) {
306 rewrittenBytecodeOpAtPut(bytecode, previous_index, rewritten.bc);
307 rewrittenBytecodeArgAtPut(bytecode, previous_index,
308 static_cast<byte>(rewritten.arg));
309 rewrittenBytecodeCacheAtPut(bytecode, previous_index, cache);
310
311 cache++;
312 }
313 continue;
314 }
315 if (rewritten.arg != op.arg || rewritten.bc != op.bc) {
316 rewrittenBytecodeOpAtPut(bytecode, previous_index, rewritten.bc);
317 rewrittenBytecodeArgAtPut(bytecode, previous_index,
318 static_cast<byte>(rewritten.arg));
319 }
320 }
321 // It may end up exactly equal to kMaxCaches; that's fine because it's a post
322 // increment.
323 DCHECK(cache <= kMaxCaches, "Too many caches: %ld", cache);
324 if (cache > 0) {
325 MutableTuple caches(&scope,
326 runtime->newMutableTuple(cache * kIcPointersPerEntry));
327 caches.fill(NoneType::object());
328 function.setCaches(*caches);
329 }
330}
331
332} // namespace py