1// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_CALL_SPECIALIZER_H_
6#define RUNTIME_VM_COMPILER_CALL_SPECIALIZER_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "vm/compiler/backend/flow_graph.h"
13#include "vm/compiler/backend/il.h"
14
15namespace dart {
16
17class SpeculativeInliningPolicy;
18
19// Call specialization pass is responsible for replacing instance calls by
20// faster alternatives based on type feedback (JIT), type speculations (AOT),
21// locally propagated type information or global type information.
22//
23// This pass for example can
24//
25// * Replace a call to a binary arithmetic operator with corresponding IL
26// instructions and necessary checks;
27// * Replace a dynamic call with a static call, if reciever is known
28// to have a certain class id;
29// * Replace type check with a range check
30//
31// CallSpecializer is a base class that contains logic shared between
32// JIT and AOT compilation pipelines, see JitCallSpecializer for JIT specific
33// optimizations and AotCallSpecializer for AOT specific optimizations.
34class CallSpecializer : public FlowGraphVisitor {
35 public:
36 CallSpecializer(FlowGraph* flow_graph,
37 SpeculativeInliningPolicy* speculative_policy,
38 bool should_clone_fields)
39 : FlowGraphVisitor(flow_graph->reverse_postorder()),
40 speculative_policy_(speculative_policy),
41 should_clone_fields_(should_clone_fields),
42 flow_graph_(flow_graph) {}
43
44 virtual ~CallSpecializer() {}
45
46 FlowGraph* flow_graph() const { return flow_graph_; }
47
48 void set_flow_graph(FlowGraph* flow_graph) {
49 flow_graph_ = flow_graph;
50 set_block_order(flow_graph->reverse_postorder());
51 }
52
53 // Use ICData to optimize, replace or eliminate instructions.
54 void ApplyICData();
55
56 // Use propagated class ids to optimize, replace or eliminate instructions.
57 void ApplyClassIds();
58
59 virtual void ReplaceInstanceCallsWithDispatchTableCalls();
60
61 void InsertBefore(Instruction* next,
62 Instruction* instr,
63 Environment* env,
64 FlowGraph::UseKind use_kind) {
65 flow_graph_->InsertBefore(next, instr, env, use_kind);
66 }
67
68 virtual void VisitStaticCall(StaticCallInstr* instr);
69
70 // TODO(dartbug.com/30633) these methods have nothing to do with
71 // specialization of calls. They are here for historical reasons.
72 // Find a better place for them.
73 virtual void VisitLoadCodeUnits(LoadCodeUnitsInstr* instr);
74
75 protected:
76 Thread* thread() const { return flow_graph_->thread(); }
77 Isolate* isolate() const { return flow_graph_->isolate(); }
78 Zone* zone() const { return flow_graph_->zone(); }
79 const Function& function() const { return flow_graph_->function(); }
80
81 bool TryReplaceWithIndexedOp(InstanceCallInstr* call);
82
83 bool TryReplaceWithBinaryOp(InstanceCallInstr* call, Token::Kind op_kind);
84 bool TryReplaceWithUnaryOp(InstanceCallInstr* call, Token::Kind op_kind);
85
86 bool TryReplaceWithEqualityOp(InstanceCallInstr* call, Token::Kind op_kind);
87 bool TryReplaceWithRelationalOp(InstanceCallInstr* call, Token::Kind op_kind);
88
89 bool TryInlineInstanceGetter(InstanceCallInstr* call);
90 bool TryInlineInstanceSetter(InstanceCallInstr* call);
91
92 bool TryInlineInstanceMethod(InstanceCallInstr* call);
93 void ReplaceWithInstanceOf(InstanceCallInstr* instr);
94
95 // Replaces a call where the replacement code does not end in a
96 // value-returning instruction, so we must specify what definition should be
97 // used instead to replace uses of the call return value.
98 void ReplaceCallWithResult(Definition* call,
99 Instruction* replacement,
100 Definition* result);
101 void ReplaceCall(Definition* call, Definition* replacement);
102
103 // Add a class check for the call's first argument (receiver).
104 void AddReceiverCheck(InstanceCallInstr* call) {
105 AddCheckClass(call->Receiver()->definition(), call->Targets(),
106 call->deopt_id(), call->env(), call);
107 }
108
109 // Insert a null check if needed.
110 void AddCheckNull(Value* to_check,
111 const String& function_name,
112 intptr_t deopt_id,
113 Environment* deopt_environment,
114 Instruction* insert_before);
115
116 // Attempt to build ICData for call using propagated class-ids.
117 virtual bool TryCreateICData(InstanceCallInstr* call);
118
119 virtual bool TryReplaceInstanceOfWithRangeCheck(InstanceCallInstr* call,
120 const AbstractType& type);
121
122 virtual bool TryOptimizeStaticCallUsingStaticTypes(StaticCallInstr* call) = 0;
123
124 protected:
125 void InlineImplicitInstanceGetter(Definition* call, const Field& field);
126
127 // Insert a check of 'to_check' determined by 'unary_checks'. If the
128 // check fails it will deoptimize to 'deopt_id' using the deoptimization
129 // environment 'deopt_environment'. The check is inserted immediately
130 // before 'insert_before'.
131 void AddCheckClass(Definition* to_check,
132 const Cids& cids,
133 intptr_t deopt_id,
134 Environment* deopt_environment,
135 Instruction* insert_before);
136
137 SpeculativeInliningPolicy* speculative_policy_;
138 const bool should_clone_fields_;
139
140 private:
141 bool TypeCheckAsClassEquality(const AbstractType& type);
142
143 // Insert a Smi check if needed.
144 void AddCheckSmi(Definition* to_check,
145 intptr_t deopt_id,
146 Environment* deopt_environment,
147 Instruction* insert_before);
148
149 // Add a class check for a call's nth argument immediately before the
150 // call, using the call's IC data to determine the check, and the call's
151 // deopt ID and deoptimization environment if the check fails.
152 void AddChecksForArgNr(InstanceCallInstr* call,
153 Definition* argument,
154 int argument_number);
155
156 bool InlineSimdBinaryOp(InstanceCallInstr* call,
157 intptr_t cid,
158 Token::Kind op_kind);
159
160 bool TryInlineImplicitInstanceGetter(InstanceCallInstr* call);
161
162 BoolPtr InstanceOfAsBool(const ICData& ic_data,
163 const AbstractType& type,
164 ZoneGrowableArray<intptr_t>* results) const;
165
166 bool TryOptimizeInstanceOfUsingStaticTypes(InstanceCallInstr* call,
167 const AbstractType& type);
168
169 void ReplaceWithMathCFunction(InstanceCallInstr* call,
170 MethodRecognizer::Kind recognized_kind);
171
172 bool TryStringLengthOneEquality(InstanceCallInstr* call, Token::Kind op_kind);
173
174 void SpecializePolymorphicInstanceCall(PolymorphicInstanceCallInstr* call);
175
176 // Tries to add cid tests to 'results' so that no deoptimization is
177 // necessary for common number-related type tests. Unconditionally adds an
178 // entry for the Smi type to the start of the array.
179 static bool SpecializeTestCidsForNumericTypes(
180 ZoneGrowableArray<intptr_t>* results,
181 const AbstractType& type);
182
183 FlowGraph* flow_graph_;
184};
185
186#define PUBLIC_TYPED_DATA_CLASS_LIST(V) \
187 V(Int8List, int8_list_type_, int_type_, kTypedDataInt8ArrayCid) \
188 V(Uint8List, uint8_list_type_, int_type_, kTypedDataUint8ArrayCid) \
189 V(Uint8ClampedList, uint8_clamped_type_, int_type_, \
190 kTypedDataUint8ClampedArrayCid) \
191 V(Int16List, int16_list_type_, int_type_, kTypedDataInt16ArrayCid) \
192 V(Uint16List, uint16_list_type_, int_type_, kTypedDataUint16ArrayCid) \
193 V(Int32List, int32_list_type_, int_type_, kTypedDataInt32ArrayCid) \
194 V(Uint32List, uint32_list_type_, int_type_, kTypedDataUint32ArrayCid) \
195 V(Int64List, int64_list_type_, int_type_, kTypedDataInt64ArrayCid) \
196 V(Uint64List, uint64_list_type_, int_type_, kTypedDataUint64ArrayCid) \
197 V(Float32List, float32_list_type_, double_type_, kTypedDataFloat32ArrayCid) \
198 V(Float64List, float64_list_type_, double_type_, kTypedDataFloat64ArrayCid)
199
200// Specializes instance/static calls with receiver type being a typed data
201// interface (if that interface is only implemented by internal/external/view
202// typed data classes).
203//
204// For example:
205//
206// foo(Uint8List bytes) => bytes[0];
207//
208// Would be translated to something like this:
209//
210// v0 <- Constant(0)
211//
212// // Ensures the list is non-null.
213// v1 <- ParameterInstr(0)
214// v2 <- CheckNull(v1)
215//
216// // Load the length & perform bounds checks
217// v3 <- LoadField(v2, "TypedDataBase.length");
218// v4 <- GenericCheckBounds(v3, v0);
219//
220// // Directly access the byte, independent of whether `bytes` is
221// // _Uint8List, _Uint8ArrayView or _ExternalUint8Array.
222// v5 <- LoadUntagged(v1, "TypedDataBase.data");
223// v5 <- LoadIndexed(v5, v4)
224//
225class TypedDataSpecializer : public FlowGraphVisitor {
226 public:
227 static void Optimize(FlowGraph* flow_graph);
228
229 virtual void VisitInstanceCall(InstanceCallInstr* instr);
230 virtual void VisitStaticCall(StaticCallInstr* instr);
231
232 private:
233 // clang-format off
234 explicit TypedDataSpecializer(FlowGraph* flow_graph)
235 : FlowGraphVisitor(flow_graph->reverse_postorder()),
236 thread_(Thread::Current()),
237 zone_(thread_->zone()),
238 flow_graph_(flow_graph),
239#define ALLOCATE_HANDLE(iface, member_name, type, cid) \
240 member_name(AbstractType::Handle(zone_)),
241 PUBLIC_TYPED_DATA_CLASS_LIST(ALLOCATE_HANDLE)
242#undef INIT_HANDLE
243 int_type_(AbstractType::Handle()),
244 double_type_(AbstractType::Handle()),
245 implementor_(Class::Handle()) {
246 }
247 // clang-format on
248
249 void EnsureIsInitialized();
250 bool HasThirdPartyImplementor(const GrowableObjectArray& direct_implementors);
251 void TryInlineCall(TemplateDartCall<0>* call);
252 void ReplaceWithLengthGetter(TemplateDartCall<0>* call);
253 void ReplaceWithIndexGet(TemplateDartCall<0>* call, classid_t cid);
254 void ReplaceWithIndexSet(TemplateDartCall<0>* call, classid_t cid);
255 void AppendNullCheck(TemplateDartCall<0>* call, Definition** array);
256 void AppendBoundsCheck(TemplateDartCall<0>* call,
257 Definition* array,
258 Definition** index);
259 Definition* AppendLoadLength(TemplateDartCall<0>* call, Definition* array);
260 Definition* AppendLoadIndexed(TemplateDartCall<0>* call,
261 Definition* array,
262 Definition* index,
263 classid_t cid);
264 void AppendStoreIndexed(TemplateDartCall<0>* call,
265 Definition* array,
266 Definition* index,
267 Definition* value,
268 classid_t cid);
269
270 Zone* zone() const { return zone_; }
271
272 Thread* thread_;
273 Zone* zone_;
274 FlowGraph* flow_graph_;
275 bool initialized_ = false;
276
277#define DEF_HANDLE(iface, member_name, type, cid) AbstractType& member_name;
278 PUBLIC_TYPED_DATA_CLASS_LIST(DEF_HANDLE)
279#undef DEF_HANDLE
280
281 AbstractType& int_type_;
282 AbstractType& double_type_;
283 Class& implementor_;
284};
285
286} // namespace dart
287
288#endif // RUNTIME_VM_COMPILER_CALL_SPECIALIZER_H_
289