OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import '../closure.dart'; | 5 import '../closure.dart'; |
6 import '../common.dart'; | 6 import '../common.dart'; |
7 import '../common/backend_api.dart' show BackendClasses; | 7 import '../common/backend_api.dart' show BackendClasses; |
8 import '../compiler.dart' show Compiler; | 8 import '../compiler.dart' show Compiler; |
9 import '../constants/constant_system.dart'; | 9 import '../constants/constant_system.dart'; |
10 import '../constants/values.dart'; | 10 import '../constants/values.dart'; |
(...skipping 848 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
859 } else { | 859 } else { |
860 bool res = dominatesCache[other]; | 860 bool res = dominatesCache[other]; |
861 if (res != null) return res; | 861 if (res != null) return res; |
862 } | 862 } |
863 do { | 863 do { |
864 if (identical(this, other)) return dominatesCache[other] = true; | 864 if (identical(this, other)) return dominatesCache[other] = true; |
865 other = other.dominator; | 865 other = other.dominator; |
866 } while (other != null && other.id >= id); | 866 } while (other != null && other.id >= id); |
867 return dominatesCache[other] = false; | 867 return dominatesCache[other] = false; |
868 } | 868 } |
869 | |
870 toString() => 'HBasicBlock($id)'; | |
871 } | 869 } |
872 | 870 |
873 abstract class HInstruction implements Spannable { | 871 abstract class HInstruction implements Spannable { |
874 Entity sourceElement; | 872 Entity sourceElement; |
875 SourceInformation sourceInformation; | 873 SourceInformation sourceInformation; |
876 | 874 |
877 final int id; | 875 final int id; |
878 static int idCounter; | 876 static int idCounter; |
879 | 877 |
880 final List<HInstruction> inputs; | 878 final List<HInstruction> inputs; |
(...skipping 391 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1272 assert(newInput != null && !identical(oldInput, newInput)); | 1270 assert(newInput != null && !identical(oldInput, newInput)); |
1273 for (int i = 0; i < inputs.length; i++) { | 1271 for (int i = 0; i < inputs.length; i++) { |
1274 if (identical(inputs[i], oldInput)) { | 1272 if (identical(inputs[i], oldInput)) { |
1275 inputs[i] = newInput; | 1273 inputs[i] = newInput; |
1276 newInput.usedBy.add(this); | 1274 newInput.usedBy.add(this); |
1277 } | 1275 } |
1278 } | 1276 } |
1279 removeFromList(oldInput.usedBy, this); | 1277 removeFromList(oldInput.usedBy, this); |
1280 } | 1278 } |
1281 | 1279 |
| 1280 // Compute the set of users of this instruction that is dominated by |
| 1281 // [other]. If [other] is a user of [this], it is included in the |
| 1282 // returned set. |
| 1283 Setlet<HInstruction> dominatedUsers(HInstruction other) { |
| 1284 // Keep track of all instructions that we have to deal with later |
| 1285 // and count the number of them that are in the current block. |
| 1286 Setlet<HInstruction> users = new Setlet<HInstruction>(); |
| 1287 int usersInCurrentBlock = 0; |
| 1288 |
| 1289 // Run through all the users and see if they are dominated or |
| 1290 // potentially dominated by [other]. |
| 1291 HBasicBlock otherBlock = other.block; |
| 1292 for (int i = 0, length = usedBy.length; i < length; i++) { |
| 1293 HInstruction current = usedBy[i]; |
| 1294 HBasicBlock currentBlock = current.block; |
| 1295 if (otherBlock.dominates(currentBlock)) { |
| 1296 if (identical(currentBlock, otherBlock)) usersInCurrentBlock++; |
| 1297 users.add(current); |
| 1298 } |
| 1299 } |
| 1300 |
| 1301 // Run through all the phis in the same block as [other] and remove them |
| 1302 // from the users set. |
| 1303 if (usersInCurrentBlock > 0) { |
| 1304 for (HPhi phi = otherBlock.phis.first; phi != null; phi = phi.next) { |
| 1305 if (users.contains(phi)) { |
| 1306 users.remove(phi); |
| 1307 if (--usersInCurrentBlock == 0) break; |
| 1308 } |
| 1309 } |
| 1310 } |
| 1311 |
| 1312 // Run through all the instructions before [other] and remove them |
| 1313 // from the users set. |
| 1314 if (usersInCurrentBlock > 0) { |
| 1315 HInstruction current = otherBlock.first; |
| 1316 while (!identical(current, other)) { |
| 1317 if (users.contains(current)) { |
| 1318 users.remove(current); |
| 1319 if (--usersInCurrentBlock == 0) break; |
| 1320 } |
| 1321 current = current.next; |
| 1322 } |
| 1323 } |
| 1324 |
| 1325 return users; |
| 1326 } |
| 1327 |
1282 void replaceAllUsersDominatedBy( | 1328 void replaceAllUsersDominatedBy( |
1283 HInstruction cursor, HInstruction newInstruction) { | 1329 HInstruction cursor, HInstruction newInstruction) { |
1284 DominatedUses.of(this, cursor).replaceWith(newInstruction); | 1330 Setlet<HInstruction> users = dominatedUsers(cursor); |
| 1331 for (HInstruction user in users) { |
| 1332 user.changeUse(this, newInstruction); |
| 1333 } |
1285 } | 1334 } |
1286 | 1335 |
1287 void moveBefore(HInstruction other) { | 1336 void moveBefore(HInstruction other) { |
1288 assert(this is! HControlFlow); | 1337 assert(this is! HControlFlow); |
1289 assert(this is! HPhi); | 1338 assert(this is! HPhi); |
1290 assert(other is! HPhi); | 1339 assert(other is! HPhi); |
1291 block.detach(this); | 1340 block.detach(this); |
1292 other.block.internalAddBefore(other, this); | 1341 other.block.internalAddBefore(other, this); |
1293 block = other.block; | 1342 block = other.block; |
1294 } | 1343 } |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1361 | 1410 |
1362 /** | 1411 /** |
1363 * Return whether the instructions do not belong to a loop or | 1412 * Return whether the instructions do not belong to a loop or |
1364 * belong to the same loop. | 1413 * belong to the same loop. |
1365 */ | 1414 */ |
1366 bool hasSameLoopHeaderAs(HInstruction other) { | 1415 bool hasSameLoopHeaderAs(HInstruction other) { |
1367 return block.enclosingLoopHeader == other.block.enclosingLoopHeader; | 1416 return block.enclosingLoopHeader == other.block.enclosingLoopHeader; |
1368 } | 1417 } |
1369 } | 1418 } |
1370 | 1419 |
1371 /// The set of uses of [source] that are dominated by [dominator]. | |
1372 class DominatedUses { | |
1373 final HInstruction _source; | |
1374 final HInstruction _dominator; | |
1375 | |
1376 // Two list of matching length holding (instruction, input-index) pairs for | |
1377 // the dominated uses. | |
1378 final List<HInstruction> _instructions = <HInstruction>[]; | |
1379 final List<int> _indexes = <int>[]; | |
1380 | |
1381 DominatedUses._(this._source, this._dominator); | |
1382 | |
1383 /// The uses of [source] that are dominated by [dominator]. | |
1384 /// | |
1385 /// The uses by [dominator] are included in the result, unless | |
1386 /// [excludeDominator] is `true`, so `true` selects uses following | |
1387 /// [dominator]. | |
1388 /// | |
1389 /// The uses include the in-edges of a HPhi node that corresponds to a | |
1390 /// dominated block. (There can be many such edges on a single phi at the exit | |
1391 /// of a loop with many break statements). If [excludePhiOutEdges] is `true` | |
1392 /// then these edge uses are not included. | |
1393 static of(HInstruction source, HInstruction dominator, | |
1394 {bool excludeDominator: false, bool excludePhiOutEdges: false}) { | |
1395 return new DominatedUses._(source, dominator) | |
1396 .._compute(source, dominator, excludeDominator, excludePhiOutEdges); | |
1397 } | |
1398 | |
1399 bool get isEmpty => _instructions.isEmpty; | |
1400 bool get isNotEmpty => !isEmpty; | |
1401 | |
1402 /// Changes all the uses in the set to [newInstruction]. | |
1403 void replaceWith(HInstruction newInstruction) { | |
1404 assert(!identical(newInstruction, _source)); | |
1405 if (isEmpty) return; | |
1406 for (int i = 0; i < _instructions.length; i++) { | |
1407 HInstruction user = _instructions[i]; | |
1408 int index = _indexes[i]; | |
1409 HInstruction oldInstruction = user.inputs[index]; | |
1410 assert( | |
1411 identical(oldInstruction, _source), | |
1412 'Input ${index} of ${user} changed.' | |
1413 '\n Found: ${oldInstruction}\n Expected: ${_source}'); | |
1414 user.inputs[index] = newInstruction; | |
1415 oldInstruction.usedBy.remove(user); | |
1416 newInstruction.usedBy.add(user); | |
1417 } | |
1418 } | |
1419 | |
1420 void _addUse(HInstruction user, int inputIndex) { | |
1421 _instructions.add(user); | |
1422 _indexes.add(inputIndex); | |
1423 } | |
1424 | |
1425 void _compute(HInstruction source, HInstruction dominator, | |
1426 bool excludeDominator, bool excludePhiOutEdges) { | |
1427 // Keep track of all instructions that we have to deal with later and count | |
1428 // the number of them that are in the current block. | |
1429 Set<HInstruction> users = new Setlet<HInstruction>(); | |
1430 Set<HInstruction> seen = new Setlet<HInstruction>(); | |
1431 int usersInCurrentBlock = 0; | |
1432 | |
1433 HBasicBlock dominatorBlock = dominator.block; | |
1434 | |
1435 // Run through all the users and see if they are dominated, or potentially | |
1436 // dominated, or partially dominated by [dominator]. It is easier to | |
1437 // de-duplicate [usedBy] and process all inputs of an instruction than to | |
1438 // track the repeated elements of usedBy and match them up by index. | |
1439 for (HInstruction current in source.usedBy) { | |
1440 if (!seen.add(current)) continue; | |
1441 HBasicBlock currentBlock = current.block; | |
1442 if (dominatorBlock.dominates(currentBlock)) { | |
1443 users.add(current); | |
1444 if (identical(currentBlock, dominatorBlock)) usersInCurrentBlock++; | |
1445 } else if (!excludePhiOutEdges && current is HPhi) { | |
1446 // A non-dominated HPhi. | |
1447 // See if there a dominated edge into the phi. The input must be | |
1448 // [source] and the position must correspond to a dominated block. | |
1449 List<HBasicBlock> predecessors = currentBlock.predecessors; | |
1450 for (int i = 0; i < predecessors.length; i++) { | |
1451 if (current.inputs[i] != source) continue; | |
1452 HBasicBlock predecessor = predecessors[i]; | |
1453 if (dominatorBlock.dominates(predecessor)) { | |
1454 _addUse(current, i); | |
1455 } | |
1456 } | |
1457 } | |
1458 } | |
1459 | |
1460 // Run through all the phis in the same block as [dominator] and remove them | |
1461 // from the users set. These come before [dominator]. | |
1462 // TODO(sra): Could we simply not add them in the first place? | |
1463 if (usersInCurrentBlock > 0) { | |
1464 for (HPhi phi = dominatorBlock.phis.first; phi != null; phi = phi.next) { | |
1465 if (users.remove(phi)) { | |
1466 if (--usersInCurrentBlock == 0) break; | |
1467 } | |
1468 } | |
1469 } | |
1470 | |
1471 // Run through all the instructions before [dominator] and remove them from | |
1472 // the users set. | |
1473 if (usersInCurrentBlock > 0) { | |
1474 HInstruction current = dominatorBlock.first; | |
1475 while (!identical(current, dominator)) { | |
1476 if (users.remove(current)) { | |
1477 if (--usersInCurrentBlock == 0) break; | |
1478 } | |
1479 current = current.next; | |
1480 } | |
1481 if (excludeDominator) { | |
1482 users.remove(dominator); | |
1483 } | |
1484 } | |
1485 | |
1486 // Convert users into a list of (user, input-index) uses. | |
1487 for (HInstruction user in users) { | |
1488 var inputs = user.inputs; | |
1489 for (int i = 0; i < inputs.length; i++) { | |
1490 if (inputs[i] == source) { | |
1491 _addUse(user, i); | |
1492 } | |
1493 } | |
1494 } | |
1495 } | |
1496 } | |
1497 | |
1498 /// A reference to a [HInstruction] that can hold its own source information. | 1420 /// A reference to a [HInstruction] that can hold its own source information. |
1499 /// | 1421 /// |
1500 /// This used for attaching source information to reads of locals. | 1422 /// This used for attaching source information to reads of locals. |
1501 class HRef extends HInstruction { | 1423 class HRef extends HInstruction { |
1502 HRef(HInstruction value, SourceInformation sourceInformation) | 1424 HRef(HInstruction value, SourceInformation sourceInformation) |
1503 : super([value], value.instructionType) { | 1425 : super([value], value.instructionType) { |
1504 this.sourceInformation = sourceInformation; | 1426 this.sourceInformation = sourceInformation; |
1505 } | 1427 } |
1506 | 1428 |
1507 HInstruction get value => inputs[0]; | 1429 HInstruction get value => inputs[0]; |
(...skipping 2012 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3520 // ignore: MISSING_RETURN | 3442 // ignore: MISSING_RETURN |
3521 String get kindAsString { | 3443 String get kindAsString { |
3522 switch (kind) { | 3444 switch (kind) { |
3523 case TypeInfoExpressionKind.COMPLETE: | 3445 case TypeInfoExpressionKind.COMPLETE: |
3524 return 'COMPLETE'; | 3446 return 'COMPLETE'; |
3525 case TypeInfoExpressionKind.INSTANCE: | 3447 case TypeInfoExpressionKind.INSTANCE: |
3526 return 'INSTANCE'; | 3448 return 'INSTANCE'; |
3527 } | 3449 } |
3528 } | 3450 } |
3529 } | 3451 } |
OLD | NEW |