| // Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'package:kernel/ast.dart'; |
| import 'package:kernel/target/targets.dart' show Target; |
| import 'package:kernel/type_environment.dart' show StaticTypeContext; |
| |
| import 'vm_constant_evaluator.dart' show VMConstantEvaluator; |
| |
| /// Simple unreachable code elimination: removes asserts and if statements |
| /// with constant conditions. Does a very limited constant folding of |
| /// logical expressions. |
| /// |
| /// Also performs some additional constant evaluation via [evaluator], which is |
| /// applied to certain types of expressions (currently only StaticGet). |
| Component transformComponent(Target target, Component component, |
| VMConstantEvaluator evaluator, bool enableAsserts) { |
| SimpleUnreachableCodeElimination(evaluator, enableAsserts: enableAsserts) |
| .visitComponent(component, null); |
| return component; |
| } |
| |
| class SimpleUnreachableCodeElimination extends RemovingTransformer { |
| final bool enableAsserts; |
| final VMConstantEvaluator constantEvaluator; |
| StaticTypeContext? _staticTypeContext; |
| |
| SimpleUnreachableCodeElimination(this.constantEvaluator, |
| {required this.enableAsserts}); |
| |
| Never _throwPlatformConstError(Member node, String message) { |
| final uri = constantEvaluator.getFileUri(node); |
| final offset = constantEvaluator.getFileOffset(uri, node); |
| throw PlatformConstError(message, node, uri, offset); |
| } |
| |
| void _checkPlatformConstMember(Member node) { |
| if (node is Field) { |
| if (!node.isStatic) { |
| _throwPlatformConstError(node, 'not a static field'); |
| } |
| // Static fields currently always have an initializer set, even if it's |
| // the implicit null initializer for a nullable field. |
| assert(node.initializer != null); |
| } else if (node is Procedure) { |
| if (!node.isStatic) { |
| _throwPlatformConstError(node, 'not a static method'); |
| } |
| if (!node.isGetter) { |
| _throwPlatformConstError(node, 'not a getter'); |
| } |
| } else { |
| _throwPlatformConstError(node, 'not a field or method'); |
| } |
| } |
| |
| @override |
| TreeNode defaultMember(Member node, TreeNode? removalSentinel) { |
| _staticTypeContext = |
| StaticTypeContext(node, constantEvaluator.typeEnvironment); |
| if (constantEvaluator.shouldEvaluateMember(node)) { |
| _checkPlatformConstMember(node); |
| // Create a StaticGet to ensure the member is evaluated at least once, |
| // and then replace the field initializer or getter body with the result. |
| final staticGet = StaticGet(node)..fileOffset = node.fileOffset; |
| final result = |
| staticGet.accept1(this, cannotRemoveSentinel) as ConstantExpression; |
| if (node is Field) { |
| final initializer = node.initializer; |
| if (initializer == null) { |
| assert(node.isExternal); |
| } else { |
| node.initializer = result |
| ..fileOffset = initializer.fileOffset |
| ..parent = node; |
| } |
| } else if (node is Procedure) { |
| final body = node.function.body; |
| if (body == null) { |
| assert(node.isExternal); |
| } else { |
| node.function.body = ReturnStatement(result) |
| ..fileOffset = body.fileOffset |
| ..parent = node.function; |
| } |
| } |
| } |
| final result = super.defaultMember(node, removalSentinel); |
| _staticTypeContext = null; |
| return result; |
| } |
| |
| bool? _getBoolConstantValue(Expression node) { |
| if (node is BoolLiteral) return node.value; |
| if (node is! ConstantExpression) return null; |
| final constant = node.constant; |
| return constant is BoolConstant ? constant.value : null; |
| } |
| |
| Expression _createBoolConstantExpression(bool value, Expression node) => |
| ConstantExpression(constantEvaluator.makeBoolConstant(value), |
| node.getStaticType(_staticTypeContext!)) |
| ..fileOffset = node.fileOffset; |
| |
| Statement _makeEmptyBlockIfEmptyStatement(Statement node, TreeNode parent) => |
| node is EmptyStatement ? (Block(<Statement>[])..parent = parent) : node; |
| |
| @override |
| TreeNode visitIfStatement(IfStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final condition = node.condition; |
| final value = _getBoolConstantValue(condition); |
| if (value != null) { |
| return value |
| ? node.then |
| : (node.otherwise ?? removalSentinel ?? new EmptyStatement()); |
| } |
| node.then = _makeEmptyBlockIfEmptyStatement(node.then, node); |
| return node; |
| } |
| |
| @override |
| visitConditionalExpression( |
| ConditionalExpression node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final condition = node.condition; |
| final value = _getBoolConstantValue(condition); |
| if (value != null) { |
| return value ? node.then : node.otherwise; |
| } |
| return node; |
| } |
| |
| @override |
| TreeNode visitNot(Not node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final operand = node.operand; |
| final value = _getBoolConstantValue(operand); |
| if (value != null) { |
| return _createBoolConstantExpression(!value, node); |
| } |
| return node; |
| } |
| |
| @override |
| TreeNode visitLogicalExpression( |
| LogicalExpression node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| bool? value = _getBoolConstantValue(node.left); |
| // Because of short-circuiting, these operators cannot be treated as |
| // symmetric, so a non-constant left and a constant right is left as-is. |
| if (value == null) return node; |
| switch (node.operatorEnum) { |
| case LogicalExpressionOperator.OR: |
| return value ? node.left : node.right; |
| case LogicalExpressionOperator.AND: |
| return value ? node.right : node.left; |
| } |
| } |
| |
| @override |
| TreeNode visitSwitchStatement( |
| SwitchStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final tested = node.expression; |
| if (tested is! ConstantExpression) return node; |
| |
| // First, keep any reachable case. As a side effect, any expressions that |
| // cannot match in the SwitchCases are removed. An expression cannot match |
| // if it is a non-matching constant expression or it follows a constant |
| // expression that is guaranteed to match. |
| final toKeep = <SwitchCase>{}; |
| bool foundMatchingCase = false; |
| for (final c in node.cases) { |
| if (foundMatchingCase) { |
| c.expressions.clear(); |
| continue; |
| } |
| c.expressions.retainWhere((e) { |
| if (foundMatchingCase) return false; |
| if (e is! ConstantExpression) return true; |
| foundMatchingCase = e.constant == tested.constant; |
| return foundMatchingCase; |
| }); |
| if (c.isDefault || c.expressions.isNotEmpty) { |
| toKeep.add(c); |
| } |
| } |
| |
| if (toKeep.isEmpty) { |
| if (node.isExhaustive) { |
| throw 'Expected at least one kept case from exhaustive switch: $node'; |
| } |
| return removalSentinel ?? new EmptyStatement(); |
| } |
| |
| // Now iteratively find additional cases to keep by following targets of |
| // continue statements in kept cases. |
| final worklist = [...toKeep]; |
| final collector = ContinueSwitchStatementTargetCollector(node); |
| while (worklist.isNotEmpty) { |
| final next = worklist.removeLast(); |
| final targets = collector.collectTargets(next); |
| for (final target in targets) { |
| if (toKeep.add(target)) { |
| worklist.add(target); |
| } |
| } |
| } |
| |
| // Finally, remove any cases not marked for keeping. If only one case |
| // is kept, then the switch statement can be replaced with its body. |
| if (toKeep.length == 1) { |
| return toKeep.first.body; |
| } |
| node.cases.retainWhere(toKeep.contains); |
| if (foundMatchingCase && !node.hasDefault) { |
| // While the expression may not be explicitly exhaustive for the type |
| // of the tested expression, it is guaranteed to execute at least one |
| // of the remaining cases, so the backends don't need to handle the case |
| // where no listed case is hit for this switch. |
| // |
| // If the original program has the matching case directly falls through |
| // to the default case for some reason: |
| // |
| // switch (4) { |
| // ... |
| // case 4: |
| // default: |
| // ... |
| // } |
| // |
| // this means the default case is kept despite finding a guaranteed to |
| // match expression, as it contains that matching expression. If that |
| // happens, then we don't do this, to keep the invariant that |
| // isExplicitlyExhaustive is false if there is a default case. |
| node.isExplicitlyExhaustive = true; |
| } |
| return node; |
| } |
| |
| @override |
| TreeNode visitStaticGet(StaticGet node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final target = node.target; |
| if (target is Field && target.isConst) { |
| throw 'StaticGet from const field $target should be evaluated by front-end: $node'; |
| } |
| |
| if (!constantEvaluator.shouldEvaluateMember(target)) { |
| return super.visitStaticGet(node, removalSentinel); |
| } |
| |
| _checkPlatformConstMember(target); |
| final constant = constantEvaluator.evaluate(_staticTypeContext!, node); |
| if (constant is UnevaluatedConstant) { |
| _throwPlatformConstError(target, 'cannot evaluate to a constant'); |
| } |
| final type = node.getStaticType(_staticTypeContext!); |
| return ConstantExpression(constant, type)..fileOffset = node.fileOffset; |
| } |
| |
| @override |
| TreeNode visitAssertStatement( |
| AssertStatement node, TreeNode? removalSentinel) { |
| if (!enableAsserts) { |
| return removalSentinel ?? new EmptyStatement(); |
| } |
| return super.visitAssertStatement(node, removalSentinel); |
| } |
| |
| @override |
| TreeNode visitAssertBlock(AssertBlock node, TreeNode? removalSentinel) { |
| if (!enableAsserts) { |
| return removalSentinel ?? new EmptyStatement(); |
| } |
| return super.visitAssertBlock(node, removalSentinel); |
| } |
| |
| @override |
| TreeNode visitAssertInitializer( |
| AssertInitializer node, TreeNode? removalSentinel) { |
| if (!enableAsserts) { |
| // Initializers only occur in the initializer list where they are always |
| // removable. |
| return removalSentinel!; |
| } |
| return super.visitAssertInitializer(node, removalSentinel); |
| } |
| |
| @override |
| TreeNode visitTryFinally(TryFinally node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| final fin = node.finalizer; |
| if (fin is EmptyStatement || (fin is Block && fin.statements.isEmpty)) { |
| return node.body; |
| } |
| return node; |
| } |
| |
| bool _isRethrow(Statement body) { |
| if (body is ExpressionStatement && body.expression is Rethrow) { |
| return true; |
| } else if (body is Block && body.statements.length == 1) { |
| return _isRethrow(body.statements.single); |
| } |
| return false; |
| } |
| |
| @override |
| TreeNode visitTryCatch(TryCatch node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| // Can replace try/catch with its body if all catches are just rethrow. |
| for (Catch catchClause in node.catches) { |
| if (!_isRethrow(catchClause.body)) { |
| return node; |
| } |
| } |
| return node.body; |
| } |
| |
| // Make sure we're not generating `null` bodies. |
| // Try/catch, try/finally and switch/case statements |
| // always have a Block in a body, so there is no |
| // need to guard against null. |
| |
| @override |
| TreeNode visitWhileStatement(WhileStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| node.body = _makeEmptyBlockIfEmptyStatement(node.body, node); |
| return node; |
| } |
| |
| @override |
| TreeNode visitDoStatement(DoStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| node.body = _makeEmptyBlockIfEmptyStatement(node.body, node); |
| return node; |
| } |
| |
| @override |
| TreeNode visitForStatement(ForStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| node.body = _makeEmptyBlockIfEmptyStatement(node.body, node); |
| return node; |
| } |
| |
| @override |
| TreeNode visitForInStatement(ForInStatement node, TreeNode? removalSentinel) { |
| node.transformOrRemoveChildren(this); |
| node.body = _makeEmptyBlockIfEmptyStatement(node.body, node); |
| return node; |
| } |
| } |
| |
| class ContinueSwitchStatementTargetCollector extends RecursiveVisitor { |
| final SwitchStatement parent; |
| late Set<SwitchCase> collected; |
| |
| ContinueSwitchStatementTargetCollector(this.parent); |
| |
| Set<SwitchCase> collectTargets(SwitchCase node) { |
| collected = {}; |
| node.accept(this); |
| return collected; |
| } |
| |
| @override |
| void visitContinueSwitchStatement(ContinueSwitchStatement node) { |
| node.visitChildren(this); |
| // Only keep targets that are within the original node being checked. |
| if (node.target.parent == parent) { |
| collected.add(node.target); |
| } |
| } |
| } |
| |
| class PlatformConstError extends Error { |
| final Object? message; |
| final Member member; |
| final Uri? uri; |
| final int offset; |
| |
| PlatformConstError(this.message, this.member, this.uri, this.offset); |
| |
| @override |
| String toString() => '${uri ?? ''}:$offset ' |
| 'Error for annotated member ${member.name}: $message'; |
| } |