Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(281)

Side by Side Diff: pkg/compiler/lib/src/ssa/nodes.dart

Issue 2802323002: Redo "dart2js: Insert HTypeKnown refinement nodes on dominated edges of HPhi nodes." (Closed)
Patch Set: Work around VM performance bug (29302) Created 3 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | pkg/compiler/lib/src/ssa/optimize.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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)';
869 } 871 }
870 872
871 abstract class HInstruction implements Spannable { 873 abstract class HInstruction implements Spannable {
872 Entity sourceElement; 874 Entity sourceElement;
873 SourceInformation sourceInformation; 875 SourceInformation sourceInformation;
874 876
875 final int id; 877 final int id;
876 static int idCounter; 878 static int idCounter;
877 879
878 final List<HInstruction> inputs; 880 final List<HInstruction> inputs;
(...skipping 391 matching lines...) Expand 10 before | Expand all | Expand 10 after
1270 assert(newInput != null && !identical(oldInput, newInput)); 1272 assert(newInput != null && !identical(oldInput, newInput));
1271 for (int i = 0; i < inputs.length; i++) { 1273 for (int i = 0; i < inputs.length; i++) {
1272 if (identical(inputs[i], oldInput)) { 1274 if (identical(inputs[i], oldInput)) {
1273 inputs[i] = newInput; 1275 inputs[i] = newInput;
1274 newInput.usedBy.add(this); 1276 newInput.usedBy.add(this);
1275 } 1277 }
1276 } 1278 }
1277 removeFromList(oldInput.usedBy, this); 1279 removeFromList(oldInput.usedBy, this);
1278 } 1280 }
1279 1281
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
1328 void replaceAllUsersDominatedBy( 1282 void replaceAllUsersDominatedBy(
1329 HInstruction cursor, HInstruction newInstruction) { 1283 HInstruction cursor, HInstruction newInstruction) {
1330 Setlet<HInstruction> users = dominatedUsers(cursor); 1284 DominatedUses.of(this, cursor).replaceWith(newInstruction);
1331 for (HInstruction user in users) {
1332 user.changeUse(this, newInstruction);
1333 }
1334 } 1285 }
1335 1286
1336 void moveBefore(HInstruction other) { 1287 void moveBefore(HInstruction other) {
1337 assert(this is! HControlFlow); 1288 assert(this is! HControlFlow);
1338 assert(this is! HPhi); 1289 assert(this is! HPhi);
1339 assert(other is! HPhi); 1290 assert(other is! HPhi);
1340 block.detach(this); 1291 block.detach(this);
1341 other.block.internalAddBefore(other, this); 1292 other.block.internalAddBefore(other, this);
1342 block = other.block; 1293 block = other.block;
1343 } 1294 }
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after
1410 1361
1411 /** 1362 /**
1412 * Return whether the instructions do not belong to a loop or 1363 * Return whether the instructions do not belong to a loop or
1413 * belong to the same loop. 1364 * belong to the same loop.
1414 */ 1365 */
1415 bool hasSameLoopHeaderAs(HInstruction other) { 1366 bool hasSameLoopHeaderAs(HInstruction other) {
1416 return block.enclosingLoopHeader == other.block.enclosingLoopHeader; 1367 return block.enclosingLoopHeader == other.block.enclosingLoopHeader;
1417 } 1368 }
1418 } 1369 }
1419 1370
1371 /// The set of uses of [source] that are dominated by [dominator].
1372 class DominatedUses {
1373 final HInstruction _source;
1374
1375 // Two list of matching length holding (instruction, input-index) pairs for
1376 // the dominated uses.
1377 final List<HInstruction> _instructions = <HInstruction>[];
1378 final List<int> _indexes = <int>[];
1379
1380 DominatedUses._(this._source);
1381
1382 /// The uses of [source] that are dominated by [dominator].
1383 ///
1384 /// The uses by [dominator] are included in the result, unless
1385 /// [excludeDominator] is `true`, so `true` selects uses following
1386 /// [dominator].
1387 ///
1388 /// The uses include the in-edges of a HPhi node that corresponds to a
1389 /// dominated block. (There can be many such edges on a single phi at the exit
1390 /// of a loop with many break statements). If [excludePhiOutEdges] is `true`
1391 /// then these edge uses are not included.
1392 static of(HInstruction source, HInstruction dominator,
1393 {bool excludeDominator: false, bool excludePhiOutEdges: false}) {
1394 return new DominatedUses._(source)
1395 .._compute(source, dominator, excludeDominator, excludePhiOutEdges);
1396 }
1397
1398 bool get isEmpty => _instructions.isEmpty;
1399 bool get isNotEmpty => !isEmpty;
1400
1401 /// Changes all the uses in the set to [newInstruction].
1402 void replaceWith(HInstruction newInstruction) {
1403 assert(!identical(newInstruction, _source));
1404 if (isEmpty) return;
1405 for (int i = 0; i < _instructions.length; i++) {
1406 HInstruction user = _instructions[i];
1407 int index = _indexes[i];
1408 HInstruction oldInstruction = user.inputs[index];
1409 assert(
1410 identical(oldInstruction, _source),
1411 'Input ${index} of ${user} changed.'
1412 '\n Found: ${oldInstruction}\n Expected: ${_source}');
1413 user.inputs[index] = newInstruction;
1414 oldInstruction.usedBy.remove(user);
1415 newInstruction.usedBy.add(user);
1416 }
1417 }
1418
1419 void _addUse(HInstruction user, int inputIndex) {
1420 _instructions.add(user);
1421 _indexes.add(inputIndex);
1422 }
1423
1424 void _compute(HInstruction source, HInstruction dominator,
1425 bool excludeDominator, bool excludePhiOutEdges) {
1426 // Keep track of all instructions that we have to deal with later and count
1427 // the number of them that are in the current block.
1428 Set<HInstruction> users = new Setlet<HInstruction>();
1429 Set<HInstruction> seen = new Setlet<HInstruction>();
1430 int usersInCurrentBlock = 0;
1431
1432 HBasicBlock dominatorBlock = dominator.block;
1433
1434 // Run through all the users and see if they are dominated, or potentially
1435 // dominated, or partially dominated by [dominator]. It is easier to
1436 // de-duplicate [usedBy] and process all inputs of an instruction than to
1437 // track the repeated elements of usedBy and match them up by index.
1438 for (HInstruction current in source.usedBy) {
1439 if (!seen.add(current)) continue;
1440 HBasicBlock currentBlock = current.block;
1441 if (dominatorBlock.dominates(currentBlock)) {
1442 users.add(current);
1443 if (identical(currentBlock, dominatorBlock)) usersInCurrentBlock++;
1444 } else if (!excludePhiOutEdges && current is HPhi) {
1445 // A non-dominated HPhi.
1446 // See if there a dominated edge into the phi. The input must be
1447 // [source] and the position must correspond to a dominated block.
1448 List<HBasicBlock> predecessors = currentBlock.predecessors;
1449 for (int i = 0; i < predecessors.length; i++) {
1450 if (current.inputs[i] != source) continue;
1451 HBasicBlock predecessor = predecessors[i];
1452 if (dominatorBlock.dominates(predecessor)) {
1453 _addUse(current, i);
1454 }
1455 }
1456 }
1457 }
1458
1459 // Run through all the phis in the same block as [dominator] and remove them
1460 // from the users set. These come before [dominator].
1461 // TODO(sra): Could we simply not add them in the first place?
1462 if (usersInCurrentBlock > 0) {
1463 for (HPhi phi = dominatorBlock.phis.first; phi != null; phi = phi.next) {
1464 if (users.remove(phi)) {
1465 if (--usersInCurrentBlock == 0) break;
1466 }
1467 }
1468 }
1469
1470 // Run through all the instructions before [dominator] and remove them from
1471 // the users set.
1472 if (usersInCurrentBlock > 0) {
1473 HInstruction current = dominatorBlock.first;
1474 while (!identical(current, dominator)) {
1475 if (users.contains(current)) {
1476 // TODO(29302): Use 'user.remove(current)' as the condition.
1477 users.remove(current);
1478 if (--usersInCurrentBlock == 0) break;
1479 }
1480 current = current.next;
1481 }
1482 if (excludeDominator) {
1483 users.remove(dominator);
1484 }
1485 }
1486
1487 // Convert users into a list of (user, input-index) uses.
1488 for (HInstruction user in users) {
1489 var inputs = user.inputs;
1490 for (int i = 0; i < inputs.length; i++) {
1491 if (inputs[i] == source) {
1492 _addUse(user, i);
1493 }
1494 }
1495 }
1496 }
1497 }
1498
1420 /// A reference to a [HInstruction] that can hold its own source information. 1499 /// A reference to a [HInstruction] that can hold its own source information.
1421 /// 1500 ///
1422 /// This used for attaching source information to reads of locals. 1501 /// This used for attaching source information to reads of locals.
1423 class HRef extends HInstruction { 1502 class HRef extends HInstruction {
1424 HRef(HInstruction value, SourceInformation sourceInformation) 1503 HRef(HInstruction value, SourceInformation sourceInformation)
1425 : super([value], value.instructionType) { 1504 : super([value], value.instructionType) {
1426 this.sourceInformation = sourceInformation; 1505 this.sourceInformation = sourceInformation;
1427 } 1506 }
1428 1507
1429 HInstruction get value => inputs[0]; 1508 HInstruction get value => inputs[0];
(...skipping 2012 matching lines...) Expand 10 before | Expand all | Expand 10 after
3442 // ignore: MISSING_RETURN 3521 // ignore: MISSING_RETURN
3443 String get kindAsString { 3522 String get kindAsString {
3444 switch (kind) { 3523 switch (kind) {
3445 case TypeInfoExpressionKind.COMPLETE: 3524 case TypeInfoExpressionKind.COMPLETE:
3446 return 'COMPLETE'; 3525 return 'COMPLETE';
3447 case TypeInfoExpressionKind.INSTANCE: 3526 case TypeInfoExpressionKind.INSTANCE:
3448 return 'INSTANCE'; 3527 return 'INSTANCE';
3449 } 3528 }
3450 } 3529 }
3451 } 3530 }
OLDNEW
« no previous file with comments | « no previous file | pkg/compiler/lib/src/ssa/optimize.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698