[dart2js] Better dead phi removal
Remove dead phis including back-edges and cycles.
Add a postcondition validation for optimization phases.
Add post-phase validation test for dead-phi removal and dead-code elimination.
Bug: https://github.com/dart-lang/sdk/issues/48397
Change-Id: I178cda52dd165e825b9e2d9ae642c22162cee2e3
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/232782
Reviewed-by: Sigmund Cherem <sigmund@google.com>
Commit-Queue: Stephen Adams <sra@google.com>
diff --git a/pkg/compiler/lib/src/ssa/interceptor_finalizer.dart b/pkg/compiler/lib/src/ssa/interceptor_finalizer.dart
index 2c20593..b8dcd74 100644
--- a/pkg/compiler/lib/src/ssa/interceptor_finalizer.dart
+++ b/pkg/compiler/lib/src/ssa/interceptor_finalizer.dart
@@ -49,6 +49,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
visitBasicBlock(HBasicBlock node) {
HInstruction instruction = node.first;
while (instruction != null) {
diff --git a/pkg/compiler/lib/src/ssa/interceptor_simplifier.dart b/pkg/compiler/lib/src/ssa/interceptor_simplifier.dart
index b52be9d..c474639 100644
--- a/pkg/compiler/lib/src/ssa/interceptor_simplifier.dart
+++ b/pkg/compiler/lib/src/ssa/interceptor_simplifier.dart
@@ -47,6 +47,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
void visitBasicBlock(HBasicBlock node) {
currentBlock = node;
diff --git a/pkg/compiler/lib/src/ssa/optimize.dart b/pkg/compiler/lib/src/ssa/optimize.dart
index fe51fdd..d7433a0 100644
--- a/pkg/compiler/lib/src/ssa/optimize.dart
+++ b/pkg/compiler/lib/src/ssa/optimize.dart
@@ -39,12 +39,14 @@
import 'nodes.dart';
import 'types.dart';
import 'types_propagation.dart';
+import 'validate.dart' show NoUnusedPhiValidator;
import 'value_range_analyzer.dart';
import 'value_set.dart';
abstract class OptimizationPhase {
String get name;
void visitGraph(HGraph graph);
+ bool validPostcondition(HGraph graph);
}
class SsaOptimizerTask extends CompilerTask {
@@ -70,6 +72,8 @@
measureSubtask(phase.name, () => phase.visitGraph(graph));
codegen.tracer.traceGraph(phase.name, graph);
assert(graph.isValid(), 'Graph not valid after ${phase.name}');
+ assert(phase.validPostcondition(graph),
+ 'Graph does not satify phase postcondition after ${phase.name}');
}
SsaCodeMotion codeMotion;
@@ -244,6 +248,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
visitBasicBlock(HBasicBlock block) {
simplifyPhis(block);
HInstruction instruction = block.first;
@@ -2518,6 +2525,11 @@
}
@override
+ bool validPostcondition(HGraph graph) {
+ return NoUnusedPhiValidator.containsNoUnusedPhis(graph);
+ }
+
+ @override
void visitBasicBlock(HBasicBlock block) {
bool isDeadBlock = analyzer.isDeadBlock(block);
block.isLive = !isDeadBlock;
@@ -2827,27 +2839,33 @@
}
}
- // Remove phis that are not live.
- // Traverse in reverse order to remove phis with no uses before the
- // phis that they might use.
- // NOTICE: Doesn't handle circular references, but we don't currently
- // create any.
- List<HBasicBlock> blocks = graph.blocks;
- for (int i = blocks.length - 1; i >= 0; i--) {
- HBasicBlock block = blocks[i];
- HPhi current = block.phis.first;
- HPhi next = null;
- while (current != null) {
- next = current.next;
- if (!livePhis.contains(current)
- // TODO(ahe): Not sure the following is correct.
- &&
- current.usedBy.isEmpty) {
- block.removePhi(current);
- }
- current = next;
- }
+ // Collect dead phis.
+ List<HPhi> deadPhis = [];
+ for (final block in graph.blocks) {
+ block.forEachPhi((phi) {
+ if (!livePhis.contains(phi)) deadPhis.add(phi);
+ });
}
+
+ // Two-phase removal, phase 1: unlink all the input nodes.
+ for (final phi in deadPhis) {
+ for (final input in phi.inputs) {
+ input.removeUser(phi);
+ }
+ phi.inputs.clear();
+ }
+
+ // Two-phase removal, phase 2: remove the now-disconnected phis.
+ for (final phi in deadPhis) {
+ assert(phi.inputs.isEmpty);
+ assert(phi.usedBy.isEmpty);
+ phi.block.removePhi(phi);
+ }
+ }
+
+ @override
+ bool validPostcondition(HGraph graph) {
+ return NoUnusedPhiValidator.containsNoUnusedPhis(graph);
}
}
@@ -2903,6 +2921,9 @@
}
}
}
+
+ @override
+ bool validPostcondition(HGraph graph) => true;
}
class GvnWorkItem {
@@ -2933,6 +2954,9 @@
} while (!workQueue.isEmpty);
}
+ @override
+ bool validPostcondition(HGraph graph) => true;
+
void moveLoopInvariantCode(HGraph graph) {
for (int i = graph.blocks.length - 1; i >= 0; i--) {
HBasicBlock block = graph.blocks[i];
@@ -3158,6 +3182,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
void visitBasicBlock(HBasicBlock block) {
List<HBasicBlock> successors = block.successors;
@@ -3261,6 +3288,9 @@
visitDominatorTree(graph);
}
+ @override
+ bool validPostcondition(HGraph graph) => true;
+
// Update users of [input] that are dominated by [:dominator.first:]
// to use [TypeKnown] of [input] instead. As the type information depends
// on the control flow, we mark the inserted [HTypeKnown] nodes as
@@ -3444,6 +3474,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
void visitBasicBlock(HBasicBlock block) {
final predecessors = block.predecessors;
final indegree = predecessors.length;
diff --git a/pkg/compiler/lib/src/ssa/types_propagation.dart b/pkg/compiler/lib/src/ssa/types_propagation.dart
index a8ff036..5a88ac3 100644
--- a/pkg/compiler/lib/src/ssa/types_propagation.dart
+++ b/pkg/compiler/lib/src/ssa/types_propagation.dart
@@ -71,6 +71,9 @@
}
@override
+ bool validPostcondition(HGraph graph) => true;
+
+ @override
visitBasicBlock(HBasicBlock block) {
if (block.isLoopHeader()) {
block.forEachPhi((HPhi phi) {
diff --git a/pkg/compiler/lib/src/ssa/validate.dart b/pkg/compiler/lib/src/ssa/validate.dart
index 251368b..04c7f00 100644
--- a/pkg/compiler/lib/src/ssa/validate.dart
+++ b/pkg/compiler/lib/src/ssa/validate.dart
@@ -220,3 +220,28 @@
}
}
}
+
+/// Validate that the graph contains no unused phi nodes.
+///
+/// assert(NoUnusedPhiValidator.containsNoUnusedPhis(graph));
+class NoUnusedPhiValidator extends HGraphVisitor {
+ bool isValid = true;
+
+ static bool containsNoUnusedPhis(HGraph graph) {
+ final validator = NoUnusedPhiValidator();
+ validator.visitDominatorTree(graph);
+ return validator.isValid;
+ }
+
+ @override
+ void visitBasicBlock(HBasicBlock block) {
+ block.forEachPhi(visitPhi);
+ }
+
+ void visitPhi(HPhi phi) {
+ if (phi.usedBy.isEmpty) {
+ print('Unused $phi in B${phi.block.id}');
+ isValid = false;
+ }
+ }
+}
diff --git a/pkg/compiler/lib/src/ssa/value_range_analyzer.dart b/pkg/compiler/lib/src/ssa/value_range_analyzer.dart
index 2b20fa4..d84928d 100644
--- a/pkg/compiler/lib/src/ssa/value_range_analyzer.dart
+++ b/pkg/compiler/lib/src/ssa/value_range_analyzer.dart
@@ -665,6 +665,9 @@
optimizer.ranges = ranges;
}
+ @override
+ bool validPostcondition(HGraph graph) => true;
+
void removeRangeConversion() {
conversions.forEach((HRangeConversion instruction) {
instruction.block.rewrite(instruction, instruction.inputs[0]);
