OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/base/flags.h" | 5 #include "src/base/flags.h" |
6 #include "src/bootstrapper.h" | 6 #include "src/bootstrapper.h" |
7 #include "src/compiler/graph-reducer.h" | 7 #include "src/compiler/graph-reducer.h" |
8 #include "src/compiler/js-operator.h" | 8 #include "src/compiler/js-operator.h" |
9 #include "src/compiler/node.h" | 9 #include "src/compiler/node.h" |
10 #include "src/compiler/node-properties.h" | 10 #include "src/compiler/node-properties.h" |
(...skipping 194 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
205 } | 205 } |
206 | 206 |
207 | 207 |
208 Typer::~Typer() { | 208 Typer::~Typer() { |
209 graph_->RemoveDecorator(decorator_); | 209 graph_->RemoveDecorator(decorator_); |
210 } | 210 } |
211 | 211 |
212 | 212 |
213 class Typer::Visitor : public Reducer { | 213 class Typer::Visitor : public Reducer { |
214 public: | 214 public: |
215 explicit Visitor(Typer* typer) : typer_(typer) {} | 215 explicit Visitor(Typer* typer) |
| 216 : typer_(typer), weakened_nodes_(typer->zone()) {} |
216 | 217 |
217 Reduction Reduce(Node* node) OVERRIDE { | 218 Reduction Reduce(Node* node) OVERRIDE { |
218 if (node->op()->ValueOutputCount() == 0) return NoChange(); | 219 if (node->op()->ValueOutputCount() == 0) return NoChange(); |
219 switch (node->opcode()) { | 220 switch (node->opcode()) { |
220 #define DECLARE_CASE(x) \ | 221 #define DECLARE_CASE(x) \ |
221 case IrOpcode::k##x: \ | 222 case IrOpcode::k##x: \ |
222 return UpdateBounds(node, TypeBinaryOp(node, x##Typer)); | 223 return UpdateBounds(node, TypeBinaryOp(node, x##Typer)); |
223 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) | 224 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) |
224 #undef DECLARE_CASE | 225 #undef DECLARE_CASE |
225 | 226 |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
273 } | 274 } |
274 UNREACHABLE(); | 275 UNREACHABLE(); |
275 return Bounds(); | 276 return Bounds(); |
276 } | 277 } |
277 | 278 |
278 Type* TypeConstant(Handle<Object> value); | 279 Type* TypeConstant(Handle<Object> value); |
279 | 280 |
280 private: | 281 private: |
281 Typer* typer_; | 282 Typer* typer_; |
282 MaybeHandle<Context> context_; | 283 MaybeHandle<Context> context_; |
| 284 ZoneSet<NodeId> weakened_nodes_; |
283 | 285 |
284 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); | 286 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); |
285 DECLARE_METHOD(Start) | 287 DECLARE_METHOD(Start) |
286 VALUE_OP_LIST(DECLARE_METHOD) | 288 VALUE_OP_LIST(DECLARE_METHOD) |
287 #undef DECLARE_METHOD | 289 #undef DECLARE_METHOD |
288 | 290 |
289 Bounds BoundsOrNone(Node* node) { | 291 Bounds BoundsOrNone(Node* node) { |
290 return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node) | 292 return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node) |
291 : Bounds(Type::None()); | 293 : Bounds(Type::None()); |
292 } | 294 } |
293 | 295 |
294 Bounds Operand(Node* node, int i) { | 296 Bounds Operand(Node* node, int i) { |
295 Node* operand_node = NodeProperties::GetValueInput(node, i); | 297 Node* operand_node = NodeProperties::GetValueInput(node, i); |
296 return BoundsOrNone(operand_node); | 298 return BoundsOrNone(operand_node); |
297 } | 299 } |
298 | 300 |
299 Bounds WrapContextBoundsForInput(Node* node); | 301 Bounds WrapContextBoundsForInput(Node* node); |
300 Type* Weaken(Type* current_type, Type* previous_type); | 302 Type* Weaken(Node* node, Type* current_type, Type* previous_type); |
301 | 303 |
302 Zone* zone() { return typer_->zone(); } | 304 Zone* zone() { return typer_->zone(); } |
303 Isolate* isolate() { return typer_->isolate(); } | 305 Isolate* isolate() { return typer_->isolate(); } |
304 Graph* graph() { return typer_->graph(); } | 306 Graph* graph() { return typer_->graph(); } |
305 MaybeHandle<Context> context() { return typer_->context(); } | 307 MaybeHandle<Context> context() { return typer_->context(); } |
306 | 308 |
| 309 void SetWeakened(NodeId node_id) { weakened_nodes_.insert(node_id); } |
| 310 bool IsWeakened(NodeId node_id) { |
| 311 return weakened_nodes_.find(node_id) != weakened_nodes_.end(); |
| 312 } |
| 313 |
307 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); | 314 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); |
308 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); | 315 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); |
309 | 316 |
310 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); | 317 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); |
311 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); | 318 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); |
312 | 319 |
313 enum ComparisonOutcomeFlags { | 320 enum ComparisonOutcomeFlags { |
314 kComparisonTrue = 1, | 321 kComparisonTrue = 1, |
315 kComparisonFalse = 2, | 322 kComparisonFalse = 2, |
316 kComparisonUndefined = 4 | 323 kComparisonUndefined = 4 |
(...skipping 27 matching lines...) Expand all Loading... |
344 static Type* JSUnaryNotTyper(Type*, Typer*); | 351 static Type* JSUnaryNotTyper(Type*, Typer*); |
345 static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); | 352 static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); |
346 static Type* JSCallFunctionTyper(Type*, Typer*); | 353 static Type* JSCallFunctionTyper(Type*, Typer*); |
347 | 354 |
348 Reduction UpdateBounds(Node* node, Bounds current) { | 355 Reduction UpdateBounds(Node* node, Bounds current) { |
349 if (NodeProperties::IsTyped(node)) { | 356 if (NodeProperties::IsTyped(node)) { |
350 // Widen the bounds of a previously typed node. | 357 // Widen the bounds of a previously typed node. |
351 Bounds previous = NodeProperties::GetBounds(node); | 358 Bounds previous = NodeProperties::GetBounds(node); |
352 if (node->opcode() == IrOpcode::kPhi) { | 359 if (node->opcode() == IrOpcode::kPhi) { |
353 // Speed up termination in the presence of range types: | 360 // Speed up termination in the presence of range types: |
354 current.upper = Weaken(current.upper, previous.upper); | 361 current.upper = Weaken(node, current.upper, previous.upper); |
355 current.lower = Weaken(current.lower, previous.lower); | 362 current.lower = Weaken(node, current.lower, previous.lower); |
356 } | 363 } |
357 | 364 |
358 // Types should not get less precise. | 365 // Types should not get less precise. |
359 DCHECK(previous.lower->Is(current.lower)); | 366 DCHECK(previous.lower->Is(current.lower)); |
360 DCHECK(previous.upper->Is(current.upper)); | 367 DCHECK(previous.upper->Is(current.upper)); |
361 | 368 |
362 NodeProperties::SetBounds(node, current); | 369 NodeProperties::SetBounds(node, current); |
363 if (!(previous.Narrows(current) && current.Narrows(previous))) { | 370 if (!(previous.Narrows(current) && current.Narrows(previous))) { |
364 // If something changed, revisit all uses. | 371 // If something changed, revisit all uses. |
365 return Changed(node); | 372 return Changed(node); |
(...skipping 915 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1281 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) { | 1288 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) { |
1282 return Bounds::Unbounded(zone()); | 1289 return Bounds::Unbounded(zone()); |
1283 } | 1290 } |
1284 | 1291 |
1285 | 1292 |
1286 // Returns a somewhat larger range if we previously assigned | 1293 // Returns a somewhat larger range if we previously assigned |
1287 // a (smaller) range to this node. This is used to speed up | 1294 // a (smaller) range to this node. This is used to speed up |
1288 // the fixpoint calculation in case there appears to be a loop | 1295 // the fixpoint calculation in case there appears to be a loop |
1289 // in the graph. In the current implementation, we are | 1296 // in the graph. In the current implementation, we are |
1290 // increasing the limits to the closest power of two. | 1297 // increasing the limits to the closest power of two. |
1291 Type* Typer::Visitor::Weaken(Type* current_type, Type* previous_type) { | 1298 Type* Typer::Visitor::Weaken(Node* node, Type* current_type, |
| 1299 Type* previous_type) { |
1292 static const double kWeakenMinLimits[] = { | 1300 static const double kWeakenMinLimits[] = { |
1293 0.0, -1073741824.0, -2147483648.0, -4294967296.0, -8589934592.0, | 1301 0.0, -1073741824.0, -2147483648.0, -4294967296.0, -8589934592.0, |
1294 -17179869184.0, -34359738368.0, -68719476736.0, -137438953472.0, | 1302 -17179869184.0, -34359738368.0, -68719476736.0, -137438953472.0, |
1295 -274877906944.0, -549755813888.0, -1099511627776.0, -2199023255552.0, | 1303 -274877906944.0, -549755813888.0, -1099511627776.0, -2199023255552.0, |
1296 -4398046511104.0, -8796093022208.0, -17592186044416.0, -35184372088832.0, | 1304 -4398046511104.0, -8796093022208.0, -17592186044416.0, -35184372088832.0, |
1297 -70368744177664.0, -140737488355328.0, -281474976710656.0, | 1305 -70368744177664.0, -140737488355328.0, -281474976710656.0, |
1298 -562949953421312.0}; | 1306 -562949953421312.0}; |
1299 static const double kWeakenMaxLimits[] = { | 1307 static const double kWeakenMaxLimits[] = { |
1300 0.0, 1073741823.0, 2147483647.0, 4294967295.0, 8589934591.0, | 1308 0.0, 1073741823.0, 2147483647.0, 4294967295.0, 8589934591.0, |
1301 17179869183.0, 34359738367.0, 68719476735.0, 137438953471.0, | 1309 17179869183.0, 34359738367.0, 68719476735.0, 137438953471.0, |
1302 274877906943.0, 549755813887.0, 1099511627775.0, 2199023255551.0, | 1310 274877906943.0, 549755813887.0, 1099511627775.0, 2199023255551.0, |
1303 4398046511103.0, 8796093022207.0, 17592186044415.0, 35184372088831.0, | 1311 4398046511103.0, 8796093022207.0, 17592186044415.0, 35184372088831.0, |
1304 70368744177663.0, 140737488355327.0, 281474976710655.0, | 1312 70368744177663.0, 140737488355327.0, 281474976710655.0, |
1305 562949953421311.0}; | 1313 562949953421311.0}; |
1306 STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits)); | 1314 STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits)); |
1307 | 1315 |
1308 // If the types have nothing to do with integers, return the types. | 1316 // If the types have nothing to do with integers, return the types. |
1309 if (!current_type->Maybe(typer_->integer) || | 1317 if (!previous_type->Maybe(typer_->integer)) { |
1310 !previous_type->Maybe(typer_->integer)) { | |
1311 return current_type; | 1318 return current_type; |
1312 } | 1319 } |
| 1320 DCHECK(current_type->Maybe(typer_->integer)); |
1313 | 1321 |
1314 Type::RangeType* previous = | 1322 Type* current_integer = |
1315 Type::Intersect(previous_type, typer_->integer, zone())->GetRange(); | 1323 Type::Intersect(current_type, typer_->integer, zone()); |
1316 Type::RangeType* current = | 1324 Type* previous_integer = |
1317 Type::Intersect(current_type, typer_->integer, zone())->GetRange(); | 1325 Type::Intersect(previous_type, typer_->integer, zone()); |
1318 if (current == nullptr || previous == nullptr) { | 1326 |
1319 return current_type; | 1327 // Once we start weakening a node, we should always weaken. |
| 1328 if (!IsWeakened(node->id())) { |
| 1329 // Only weaken if there is range involved; we should converge quickly |
| 1330 // for all other types (the exception is a union of many constants, |
| 1331 // but we currently do not increase the number of constants in unions). |
| 1332 Type::RangeType* previous = previous_integer->GetRange(); |
| 1333 Type::RangeType* current = current_integer->GetRange(); |
| 1334 if (current == nullptr || previous == nullptr) { |
| 1335 return current_type; |
| 1336 } |
| 1337 // Range is involved => we are weakening. |
| 1338 SetWeakened(node->id()); |
1320 } | 1339 } |
1321 | 1340 |
1322 double current_min = current->Min(); | 1341 double current_min = current_integer->Min(); |
1323 double new_min = current_min; | 1342 double new_min = current_min; |
1324 // Find the closest lower entry in the list of allowed | 1343 // Find the closest lower entry in the list of allowed |
1325 // minima (or negative infinity if there is no such entry). | 1344 // minima (or negative infinity if there is no such entry). |
1326 if (current_min != previous->Min()) { | 1345 if (current_min != previous_integer->Min()) { |
1327 new_min = typer_->integer->AsRange()->Min(); | 1346 new_min = typer_->integer->AsRange()->Min(); |
1328 for (double const min : kWeakenMinLimits) { | 1347 for (double const min : kWeakenMinLimits) { |
1329 if (min <= current_min) { | 1348 if (min <= current_min) { |
1330 new_min = min; | 1349 new_min = min; |
1331 break; | 1350 break; |
1332 } | 1351 } |
1333 } | 1352 } |
1334 } | 1353 } |
1335 | 1354 |
1336 double current_max = current->Max(); | 1355 double current_max = current_integer->Max(); |
1337 double new_max = current_max; | 1356 double new_max = current_max; |
1338 // Find the closest greater entry in the list of allowed | 1357 // Find the closest greater entry in the list of allowed |
1339 // maxima (or infinity if there is no such entry). | 1358 // maxima (or infinity if there is no such entry). |
1340 if (current_max != previous->Max()) { | 1359 if (current_max != previous_integer->Max()) { |
1341 new_max = typer_->integer->AsRange()->Max(); | 1360 new_max = typer_->integer->AsRange()->Max(); |
1342 for (double const max : kWeakenMaxLimits) { | 1361 for (double const max : kWeakenMaxLimits) { |
1343 if (max >= current_max) { | 1362 if (max >= current_max) { |
1344 new_max = max; | 1363 new_max = max; |
1345 break; | 1364 break; |
1346 } | 1365 } |
1347 } | 1366 } |
1348 } | 1367 } |
1349 | 1368 |
1350 return Type::Union(current_type, | 1369 return Type::Union(current_type, |
(...skipping 867 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2218 TYPED_ARRAYS(TYPED_ARRAY_CASE) | 2237 TYPED_ARRAYS(TYPED_ARRAY_CASE) |
2219 #undef TYPED_ARRAY_CASE | 2238 #undef TYPED_ARRAY_CASE |
2220 } | 2239 } |
2221 } | 2240 } |
2222 return Type::Constant(value, zone()); | 2241 return Type::Constant(value, zone()); |
2223 } | 2242 } |
2224 | 2243 |
2225 } // namespace compiler | 2244 } // namespace compiler |
2226 } // namespace internal | 2245 } // namespace internal |
2227 } // namespace v8 | 2246 } // namespace v8 |
OLD | NEW |