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 "src/compiler/typed-optimization.h"
6
7 #include "src/compilation-dependencies.h"
8 #include "src/compiler/js-graph.h"
9 #include "src/compiler/node-properties.h"
10 #include "src/compiler/simplified-operator.h"
11 #include "src/compiler/type-cache.h"
12 #include "src/isolate-inl.h"
13
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17
TypedOptimization(Editor * editor,CompilationDependencies * dependencies,Flags flags,JSGraph * jsgraph)18 TypedOptimization::TypedOptimization(Editor* editor,
19 CompilationDependencies* dependencies,
20 Flags flags, JSGraph* jsgraph)
21 : AdvancedReducer(editor),
22 dependencies_(dependencies),
23 flags_(flags),
24 jsgraph_(jsgraph),
25 true_type_(Type::HeapConstant(factory()->true_value(), graph()->zone())),
26 false_type_(
27 Type::HeapConstant(factory()->false_value(), graph()->zone())),
28 type_cache_(TypeCache::Get()) {}
29
~TypedOptimization()30 TypedOptimization::~TypedOptimization() {}
31
Reduce(Node * node)32 Reduction TypedOptimization::Reduce(Node* node) {
33 // Check if the output type is a singleton. In that case we already know the
34 // result value and can simply replace the node if it's eliminable.
35 if (!NodeProperties::IsConstant(node) && NodeProperties::IsTyped(node) &&
36 node->op()->HasProperty(Operator::kEliminatable)) {
37 // TODO(v8:5303): We must not eliminate FinishRegion here. This special
38 // case can be removed once we have separate operators for value and
39 // effect regions.
40 if (node->opcode() == IrOpcode::kFinishRegion) return NoChange();
41 // We can only constant-fold nodes here, that are known to not cause any
42 // side-effect, may it be a JavaScript observable side-effect or a possible
43 // eager deoptimization exit (i.e. {node} has an operator that doesn't have
44 // the Operator::kNoDeopt property).
45 Type* upper = NodeProperties::GetType(node);
46 if (upper->IsInhabited()) {
47 if (upper->IsHeapConstant()) {
48 Node* replacement =
49 jsgraph()->Constant(upper->AsHeapConstant()->Value());
50 ReplaceWithValue(node, replacement);
51 return Changed(replacement);
52 } else if (upper->Is(Type::MinusZero())) {
53 Node* replacement = jsgraph()->Constant(factory()->minus_zero_value());
54 ReplaceWithValue(node, replacement);
55 return Changed(replacement);
56 } else if (upper->Is(Type::NaN())) {
57 Node* replacement = jsgraph()->NaNConstant();
58 ReplaceWithValue(node, replacement);
59 return Changed(replacement);
60 } else if (upper->Is(Type::Null())) {
61 Node* replacement = jsgraph()->NullConstant();
62 ReplaceWithValue(node, replacement);
63 return Changed(replacement);
64 } else if (upper->Is(Type::PlainNumber()) &&
65 upper->Min() == upper->Max()) {
66 Node* replacement = jsgraph()->Constant(upper->Min());
67 ReplaceWithValue(node, replacement);
68 return Changed(replacement);
69 } else if (upper->Is(Type::Undefined())) {
70 Node* replacement = jsgraph()->UndefinedConstant();
71 ReplaceWithValue(node, replacement);
72 return Changed(replacement);
73 }
74 }
75 }
76 switch (node->opcode()) {
77 case IrOpcode::kCheckHeapObject:
78 return ReduceCheckHeapObject(node);
79 case IrOpcode::kCheckMaps:
80 return ReduceCheckMaps(node);
81 case IrOpcode::kCheckString:
82 return ReduceCheckString(node);
83 case IrOpcode::kLoadField:
84 return ReduceLoadField(node);
85 case IrOpcode::kNumberCeil:
86 case IrOpcode::kNumberRound:
87 case IrOpcode::kNumberTrunc:
88 return ReduceNumberRoundop(node);
89 case IrOpcode::kNumberFloor:
90 return ReduceNumberFloor(node);
91 case IrOpcode::kNumberToUint8Clamped:
92 return ReduceNumberToUint8Clamped(node);
93 case IrOpcode::kPhi:
94 return ReducePhi(node);
95 case IrOpcode::kReferenceEqual:
96 return ReduceReferenceEqual(node);
97 case IrOpcode::kSelect:
98 return ReduceSelect(node);
99 default:
100 break;
101 }
102 return NoChange();
103 }
104
105 namespace {
106
GetStableMapFromObjectType(Type * object_type)107 MaybeHandle<Map> GetStableMapFromObjectType(Type* object_type) {
108 if (object_type->IsHeapConstant()) {
109 Handle<Map> object_map(object_type->AsHeapConstant()->Value()->map());
110 if (object_map->is_stable()) return object_map;
111 }
112 return MaybeHandle<Map>();
113 }
114
115 } // namespace
116
ReduceCheckHeapObject(Node * node)117 Reduction TypedOptimization::ReduceCheckHeapObject(Node* node) {
118 Node* const input = NodeProperties::GetValueInput(node, 0);
119 Type* const input_type = NodeProperties::GetType(input);
120 if (!input_type->Maybe(Type::SignedSmall())) {
121 ReplaceWithValue(node, input);
122 return Replace(input);
123 }
124 return NoChange();
125 }
126
ReduceCheckMaps(Node * node)127 Reduction TypedOptimization::ReduceCheckMaps(Node* node) {
128 // The CheckMaps(o, ...map...) can be eliminated if map is stable,
129 // o has type Constant(object) and map == object->map, and either
130 // (1) map cannot transition further, or
131 // (2) we can add a code dependency on the stability of map
132 // (to guard the Constant type information).
133 Node* const object = NodeProperties::GetValueInput(node, 0);
134 Type* const object_type = NodeProperties::GetType(object);
135 Node* const effect = NodeProperties::GetEffectInput(node);
136 Handle<Map> object_map;
137 if (GetStableMapFromObjectType(object_type).ToHandle(&object_map)) {
138 for (int i = 1; i < node->op()->ValueInputCount(); ++i) {
139 Node* const map = NodeProperties::GetValueInput(node, i);
140 Type* const map_type = NodeProperties::GetType(map);
141 if (map_type->IsHeapConstant() &&
142 map_type->AsHeapConstant()->Value().is_identical_to(object_map)) {
143 if (object_map->CanTransition()) {
144 dependencies()->AssumeMapStable(object_map);
145 }
146 return Replace(effect);
147 }
148 }
149 }
150 return NoChange();
151 }
152
ReduceCheckString(Node * node)153 Reduction TypedOptimization::ReduceCheckString(Node* node) {
154 Node* const input = NodeProperties::GetValueInput(node, 0);
155 Type* const input_type = NodeProperties::GetType(input);
156 if (input_type->Is(Type::String())) {
157 ReplaceWithValue(node, input);
158 return Replace(input);
159 }
160 return NoChange();
161 }
162
ReduceLoadField(Node * node)163 Reduction TypedOptimization::ReduceLoadField(Node* node) {
164 Node* const object = NodeProperties::GetValueInput(node, 0);
165 Type* const object_type = NodeProperties::GetType(object);
166 FieldAccess const& access = FieldAccessOf(node->op());
167 if (access.base_is_tagged == kTaggedBase &&
168 access.offset == HeapObject::kMapOffset) {
169 // We can replace LoadField[Map](o) with map if is stable, and
170 // o has type Constant(object) and map == object->map, and either
171 // (1) map cannot transition further, or
172 // (2) deoptimization is enabled and we can add a code dependency on the
173 // stability of map (to guard the Constant type information).
174 Handle<Map> object_map;
175 if (GetStableMapFromObjectType(object_type).ToHandle(&object_map)) {
176 if (object_map->CanTransition()) {
177 if (flags() & kDeoptimizationEnabled) {
178 dependencies()->AssumeMapStable(object_map);
179 } else {
180 return NoChange();
181 }
182 }
183 Node* const value = jsgraph()->HeapConstant(object_map);
184 ReplaceWithValue(node, value);
185 return Replace(value);
186 }
187 }
188 return NoChange();
189 }
190
ReduceNumberFloor(Node * node)191 Reduction TypedOptimization::ReduceNumberFloor(Node* node) {
192 Node* const input = NodeProperties::GetValueInput(node, 0);
193 Type* const input_type = NodeProperties::GetType(input);
194 if (input_type->Is(type_cache_.kIntegerOrMinusZeroOrNaN)) {
195 return Replace(input);
196 }
197 if (input_type->Is(Type::PlainNumber()) &&
198 input->opcode() == IrOpcode::kNumberDivide) {
199 Node* const lhs = NodeProperties::GetValueInput(input, 0);
200 Type* const lhs_type = NodeProperties::GetType(lhs);
201 Node* const rhs = NodeProperties::GetValueInput(input, 1);
202 Type* const rhs_type = NodeProperties::GetType(rhs);
203 if (lhs_type->Is(Type::Unsigned32()) && rhs_type->Is(Type::Unsigned32())) {
204 // We can replace
205 //
206 // NumberFloor(NumberDivide(lhs: unsigned32,
207 // rhs: unsigned32)): plain-number
208 //
209 // with
210 //
211 // NumberToUint32(NumberDivide(lhs, rhs))
212 //
213 // and just smash the type of the {lhs} on the {node},
214 // as the truncated result must be in the same range as
215 // {lhs} since {rhs} cannot be less than 1 (due to the
216 // plain-number type constraint on the {node}).
217 NodeProperties::ChangeOp(node, simplified()->NumberToUint32());
218 NodeProperties::SetType(node, lhs_type);
219 return Changed(node);
220 }
221 }
222 return NoChange();
223 }
224
ReduceNumberRoundop(Node * node)225 Reduction TypedOptimization::ReduceNumberRoundop(Node* node) {
226 Node* const input = NodeProperties::GetValueInput(node, 0);
227 Type* const input_type = NodeProperties::GetType(input);
228 if (input_type->Is(type_cache_.kIntegerOrMinusZeroOrNaN)) {
229 return Replace(input);
230 }
231 return NoChange();
232 }
233
ReduceNumberToUint8Clamped(Node * node)234 Reduction TypedOptimization::ReduceNumberToUint8Clamped(Node* node) {
235 Node* const input = NodeProperties::GetValueInput(node, 0);
236 Type* const input_type = NodeProperties::GetType(input);
237 if (input_type->Is(type_cache_.kUint8)) {
238 return Replace(input);
239 }
240 return NoChange();
241 }
242
ReducePhi(Node * node)243 Reduction TypedOptimization::ReducePhi(Node* node) {
244 // Try to narrow the type of the Phi {node}, which might be more precise now
245 // after lowering based on types, i.e. a SpeculativeNumberAdd has a more
246 // precise type than the JSAdd that was in the graph when the Typer was run.
247 DCHECK_EQ(IrOpcode::kPhi, node->opcode());
248 int arity = node->op()->ValueInputCount();
249 Type* type = NodeProperties::GetType(node->InputAt(0));
250 for (int i = 1; i < arity; ++i) {
251 type = Type::Union(type, NodeProperties::GetType(node->InputAt(i)),
252 graph()->zone());
253 }
254 Type* const node_type = NodeProperties::GetType(node);
255 if (!node_type->Is(type)) {
256 type = Type::Intersect(node_type, type, graph()->zone());
257 NodeProperties::SetType(node, type);
258 return Changed(node);
259 }
260 return NoChange();
261 }
262
ReduceReferenceEqual(Node * node)263 Reduction TypedOptimization::ReduceReferenceEqual(Node* node) {
264 DCHECK_EQ(IrOpcode::kReferenceEqual, node->opcode());
265 Node* const lhs = NodeProperties::GetValueInput(node, 0);
266 Node* const rhs = NodeProperties::GetValueInput(node, 1);
267 Type* const lhs_type = NodeProperties::GetType(lhs);
268 Type* const rhs_type = NodeProperties::GetType(rhs);
269 if (!lhs_type->Maybe(rhs_type)) {
270 return Replace(jsgraph()->FalseConstant());
271 }
272 return NoChange();
273 }
274
ReduceSelect(Node * node)275 Reduction TypedOptimization::ReduceSelect(Node* node) {
276 DCHECK_EQ(IrOpcode::kSelect, node->opcode());
277 Node* const condition = NodeProperties::GetValueInput(node, 0);
278 Type* const condition_type = NodeProperties::GetType(condition);
279 Node* const vtrue = NodeProperties::GetValueInput(node, 1);
280 Type* const vtrue_type = NodeProperties::GetType(vtrue);
281 Node* const vfalse = NodeProperties::GetValueInput(node, 2);
282 Type* const vfalse_type = NodeProperties::GetType(vfalse);
283 if (condition_type->Is(true_type_)) {
284 // Select(condition:true, vtrue, vfalse) => vtrue
285 return Replace(vtrue);
286 }
287 if (condition_type->Is(false_type_)) {
288 // Select(condition:false, vtrue, vfalse) => vfalse
289 return Replace(vfalse);
290 }
291 if (vtrue_type->Is(true_type_) && vfalse_type->Is(false_type_)) {
292 // Select(condition, vtrue:true, vfalse:false) => condition
293 return Replace(condition);
294 }
295 if (vtrue_type->Is(false_type_) && vfalse_type->Is(true_type_)) {
296 // Select(condition, vtrue:false, vfalse:true) => BooleanNot(condition)
297 node->TrimInputCount(1);
298 NodeProperties::ChangeOp(node, simplified()->BooleanNot());
299 return Changed(node);
300 }
301 // Try to narrow the type of the Select {node}, which might be more precise
302 // now after lowering based on types.
303 Type* type = Type::Union(vtrue_type, vfalse_type, graph()->zone());
304 Type* const node_type = NodeProperties::GetType(node);
305 if (!node_type->Is(type)) {
306 type = Type::Intersect(node_type, type, graph()->zone());
307 NodeProperties::SetType(node, type);
308 return Changed(node);
309 }
310 return NoChange();
311 }
312
factory() const313 Factory* TypedOptimization::factory() const { return isolate()->factory(); }
314
graph() const315 Graph* TypedOptimization::graph() const { return jsgraph()->graph(); }
316
isolate() const317 Isolate* TypedOptimization::isolate() const { return jsgraph()->isolate(); }
318
simplified() const319 SimplifiedOperatorBuilder* TypedOptimization::simplified() const {
320 return jsgraph()->simplified();
321 }
322
323 } // namespace compiler
324 } // namespace internal
325 } // namespace v8
326