Essential CFG IR instructions
Issue: https://github.com/dart-lang/sdk/issues/61635
Change-Id: I7de7c4a3bd7008c03c81243c73a71c2018ab7c70
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/459382
Commit-Queue: Alexander Markov <alexmarkov@google.com>
Reviewed-by: Slava Egorov <vegorov@google.com>
diff --git a/pkg/cfg/lib/ir/constant_value.dart b/pkg/cfg/lib/ir/constant_value.dart
new file mode 100644
index 0000000..2825223
--- /dev/null
+++ b/pkg/cfg/lib/ir/constant_value.dart
@@ -0,0 +1,251 @@
+// Copyright (c) 2025, 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:cfg/ir/instructions.dart';
+import 'package:cfg/ir/global_context.dart';
+import 'package:cfg/ir/types.dart';
+import 'package:cfg/utils/misc.dart';
+import 'package:kernel/ast.dart' as ast;
+import 'package:kernel/src/printer.dart' as ast_printer show AstPrinter;
+import 'package:kernel/type_environment.dart' show StaticTypeContext;
+
+/// Represents an arbitrary constant value.
+///
+/// [ConstantValue] is a thin wrapper around [ast.Constant].
+/// Constants which do not have corresponding representation in AST
+/// (e.g. constant type arguments) have dedicated subclasses of
+/// [ast.AuxiliaryConstant].
+extension type ConstantValue(ast.Constant constant) {
+ factory ConstantValue.fromInt(int value) =>
+ ConstantValue(ast.IntConstant(value));
+ factory ConstantValue.fromDouble(double value) =>
+ ConstantValue(ast.DoubleConstant(value));
+ factory ConstantValue.fromBool(bool value) =>
+ ConstantValue(ast.BoolConstant(value));
+ factory ConstantValue.fromNull() => ConstantValue(ast.NullConstant());
+ factory ConstantValue.fromString(String value) =>
+ ConstantValue(ast.StringConstant(value));
+
+ int get intValue => (constant as ast.IntConstant).value;
+ double get doubleValue => (constant as ast.DoubleConstant).value;
+ bool get boolValue => (constant as ast.BoolConstant).value;
+ String get stringValue => (constant as ast.StringConstant).value;
+
+ bool get isInt => constant is ast.IntConstant;
+ bool get isDouble => constant is ast.DoubleConstant;
+ bool get isBool => constant is ast.BoolConstant;
+ bool get isNull => constant is ast.NullConstant;
+ bool get isString => constant is ast.StringConstant;
+
+ CType get type => switch (constant) {
+ ast.IntConstant() => const IntType(),
+ ast.DoubleConstant() => const DoubleType(),
+ ast.BoolConstant() => const BoolType(),
+ ast.NullConstant() => const NullType(),
+ ast.StringConstant() => const StringType(),
+ TypeArgumentsConstant() => const TypeArgumentsType(),
+ _ => StaticType(
+ constant.getType(GlobalContext.instance.staticTypeContextForConstants),
+ ),
+ };
+
+ bool get isZero => switch (constant) {
+ ast.IntConstant(:var value) => value == 0,
+ ast.DoubleConstant(:var value) => value == 0.0,
+ _ => false,
+ };
+
+ bool get isNegative => switch (constant) {
+ ast.IntConstant(:var value) => value < 0,
+ ast.DoubleConstant(:var value) => value.isNegative,
+ _ => false,
+ };
+
+ String valueToString() => switch (constant) {
+ ast.StringConstant(:var value) => '"${value}"',
+ ast.PrimitiveConstant(:var value) => value.toString(),
+ _ => constant.toString(),
+ };
+}
+
+/// Utility class to perform operations on constant values.
+///
+/// Methods of this class return `null` when constant folding
+/// cannot be performed (e.g. corresponding operation would
+/// throw an exception at runtime).
+class ConstantFolding {
+ const ConstantFolding();
+
+ ConstantValue comparison(
+ ComparisonOpcode op,
+ ConstantValue left,
+ ConstantValue right,
+ ) {
+ final result = switch (op) {
+ ComparisonOpcode.equal => left.constant == right.constant,
+ ComparisonOpcode.notEqual => left.constant != right.constant,
+ ComparisonOpcode.identical => left.constant == right.constant,
+ ComparisonOpcode.notIdentical => left.constant != right.constant,
+ ComparisonOpcode.intEqual => left.intValue == right.intValue,
+ ComparisonOpcode.intNotEqual => left.intValue != right.intValue,
+ ComparisonOpcode.intLess => left.intValue < right.intValue,
+ ComparisonOpcode.intLessOrEqual => left.intValue <= right.intValue,
+ ComparisonOpcode.intGreater => left.intValue > right.intValue,
+ ComparisonOpcode.intGreaterOrEqual => left.intValue >= right.intValue,
+ ComparisonOpcode.intTestIsZero => (left.intValue & right.intValue) == 0,
+ ComparisonOpcode.intTestIsNotZero =>
+ (left.intValue & right.intValue) != 0,
+ ComparisonOpcode.doubleEqual => left.doubleValue == right.doubleValue,
+ ComparisonOpcode.doubleNotEqual => left.doubleValue != right.doubleValue,
+ ComparisonOpcode.doubleLess => left.doubleValue < right.doubleValue,
+ ComparisonOpcode.doubleLessOrEqual =>
+ left.doubleValue <= right.doubleValue,
+ ComparisonOpcode.doubleGreater => left.doubleValue > right.doubleValue,
+ ComparisonOpcode.doubleGreaterOrEqual =>
+ left.doubleValue >= right.doubleValue,
+ };
+ return ConstantValue.fromBool(result);
+ }
+
+ ConstantValue? binaryIntOp(
+ BinaryIntOpcode op,
+ ConstantValue left,
+ ConstantValue right,
+ ) {
+ final a = left.intValue;
+ final b = right.intValue;
+ switch (op) {
+ case BinaryIntOpcode.add:
+ return ConstantValue.fromInt(a + b);
+ case BinaryIntOpcode.sub:
+ return ConstantValue.fromInt(a - b);
+ case BinaryIntOpcode.mul:
+ return ConstantValue.fromInt(a * b);
+ case BinaryIntOpcode.truncatingDiv:
+ return (b != 0) ? ConstantValue.fromInt(a ~/ b) : null;
+ case BinaryIntOpcode.mod:
+ return (b != 0) ? ConstantValue.fromInt(a % b) : null;
+ case BinaryIntOpcode.rem:
+ return (b != 0) ? ConstantValue.fromInt(a.remainder(b)) : null;
+ case BinaryIntOpcode.bitOr:
+ return ConstantValue.fromInt(a | b);
+ case BinaryIntOpcode.bitAnd:
+ return ConstantValue.fromInt(a & b);
+ case BinaryIntOpcode.bitXor:
+ return ConstantValue.fromInt(a ^ b);
+ case BinaryIntOpcode.shiftLeft:
+ return (b >= 0) ? ConstantValue.fromInt(a << b) : null;
+ case BinaryIntOpcode.shiftRight:
+ return (b >= 0) ? ConstantValue.fromInt(a >> b) : null;
+ case BinaryIntOpcode.unsignedShiftRight:
+ return (b >= 0) ? ConstantValue.fromInt(a >>> b) : null;
+ }
+ }
+
+ ConstantValue? unaryIntOp(UnaryIntOpcode op, ConstantValue operand) {
+ final x = operand.intValue;
+ switch (op) {
+ case UnaryIntOpcode.neg:
+ return ConstantValue.fromInt(-x);
+ case UnaryIntOpcode.bitNot:
+ return ConstantValue.fromInt(~x);
+ case UnaryIntOpcode.toDouble:
+ return ConstantValue.fromDouble(x.toDouble());
+ case UnaryIntOpcode.abs:
+ return ConstantValue.fromInt(x.abs());
+ case UnaryIntOpcode.sign:
+ return ConstantValue.fromInt(x.sign);
+ }
+ }
+
+ ConstantValue? binaryDoubleOp(
+ BinaryDoubleOpcode op,
+ ConstantValue left,
+ ConstantValue right,
+ ) {
+ final a = left.doubleValue;
+ final b = right.doubleValue;
+ switch (op) {
+ case BinaryDoubleOpcode.add:
+ return ConstantValue.fromDouble(a + b);
+ case BinaryDoubleOpcode.sub:
+ return ConstantValue.fromDouble(a - b);
+ case BinaryDoubleOpcode.mul:
+ return ConstantValue.fromDouble(a * b);
+ case BinaryDoubleOpcode.mod:
+ return ConstantValue.fromDouble(a % b);
+ case BinaryDoubleOpcode.rem:
+ return ConstantValue.fromDouble(a.remainder(b));
+ case BinaryDoubleOpcode.div:
+ return ConstantValue.fromDouble(a / b);
+ case BinaryDoubleOpcode.truncatingDiv:
+ final doubleResult = a / b;
+ return doubleResult.isFinite
+ ? ConstantValue.fromInt(doubleResult.truncate())
+ : null;
+ }
+ }
+
+ ConstantValue? unaryDoubleOp(UnaryDoubleOpcode op, ConstantValue operand) {
+ final x = operand.doubleValue;
+ switch (op) {
+ case UnaryDoubleOpcode.neg:
+ return ConstantValue.fromDouble(-x);
+ case UnaryDoubleOpcode.abs:
+ return ConstantValue.fromDouble(x.abs());
+ case UnaryDoubleOpcode.sign:
+ return ConstantValue.fromDouble(x.sign);
+ case UnaryDoubleOpcode.square:
+ return ConstantValue.fromDouble(x * x);
+ case UnaryDoubleOpcode.round:
+ return x.isFinite ? ConstantValue.fromInt(x.round()) : null;
+ case UnaryDoubleOpcode.floor:
+ return x.isFinite ? ConstantValue.fromInt(x.floor()) : null;
+ case UnaryDoubleOpcode.ceil:
+ return x.isFinite ? ConstantValue.fromInt(x.ceil()) : null;
+ case UnaryDoubleOpcode.truncate:
+ return x.isFinite ? ConstantValue.fromInt(x.truncate()) : null;
+ case UnaryDoubleOpcode.roundToDouble:
+ return ConstantValue.fromDouble(x.roundToDouble());
+ case UnaryDoubleOpcode.floorToDouble:
+ return ConstantValue.fromDouble(x.floorToDouble());
+ case UnaryDoubleOpcode.ceilToDouble:
+ return ConstantValue.fromDouble(x.ceilToDouble());
+ case UnaryDoubleOpcode.truncateToDouble:
+ return ConstantValue.fromDouble(x.truncateToDouble());
+ }
+ }
+}
+
+/// Constant type arguments.
+class TypeArgumentsConstant extends ast.AuxiliaryConstant {
+ final List<ast.DartType> types;
+
+ TypeArgumentsConstant(this.types);
+
+ @override
+ void visitChildren(ast.Visitor v) {
+ ast.visitList(types, v);
+ }
+
+ @override
+ void toTextInternal(ast_printer.AstPrinter printer) {
+ printer.writeTypeArguments(types);
+ }
+
+ @override
+ String toString() => toStringInternal();
+
+ @override
+ int get hashCode => listHashCode(types);
+
+ @override
+ bool operator ==(Object other) {
+ return other is TypeArgumentsConstant &&
+ listEquals(this.types, other.types);
+ }
+
+ @override
+ ast.DartType getType(StaticTypeContext context) => const ast.DynamicType();
+}
diff --git a/pkg/cfg/lib/ir/flow_graph.dart b/pkg/cfg/lib/ir/flow_graph.dart
new file mode 100644
index 0000000..995be0e
--- /dev/null
+++ b/pkg/cfg/lib/ir/flow_graph.dart
@@ -0,0 +1,152 @@
+// Copyright (c) 2025, 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:cfg/ir/constant_value.dart';
+import 'package:cfg/ir/functions.dart';
+import 'package:cfg/ir/instructions.dart';
+import 'package:cfg/ir/local_variable.dart';
+import 'package:cfg/ir/use_lists.dart';
+import 'package:cfg/utils/arena.dart';
+
+/// Control-flow graph of instructions implementing a single function.
+///
+/// [FlowGraph] is also an arena to allocate use lists.
+class FlowGraph extends Uint32Arena {
+ final CFunction function;
+
+ /// Local variables used in this graph.
+ final List<LocalVariable> localVariables = [];
+
+ /// All instructions used in this graph.
+ /// [Instruction.id] is an index in this list.
+ final List<Instruction> instructions = [];
+
+ /// Empty array of uses. Used by all instructions with 0 inputs.
+ late final UsesArray emptyUsesArray = UsesArray.allocate(this, 0);
+
+ /// Mapping between constant values and corresponding [Constant]
+ /// instructions in the graph.
+ final Map<ConstantValue, Constant> _constants = {};
+
+ /// New [Constant] instructions are inserted after this instruction.
+ late Instruction _constantInsertionPoint;
+
+ /// Entry basic block in this control-flow graph.
+ late final EntryBlock entryBlock;
+
+ /// Basic block preorder.
+ final List<Block> preorder = [];
+
+ /// Basic block postorder.
+ final List<Block> postorder = [];
+
+ /// Basic block reverse postorder.
+ Iterable<Block> get reversePostorder => postorder.reversed;
+
+ /// Whether this graph was converted to SSA form.
+ bool inSSAForm = false;
+
+ /// Create a new control-flow graph for the given [function].
+ FlowGraph(this.function) {
+ entryBlock = EntryBlock(this, function.sourcePosition);
+ _constantInsertionPoint = entryBlock;
+ }
+
+ /// Return a [Constant] instruction with given [value], adding it to
+ /// the graph if necessary.
+ Constant getConstant(ConstantValue value) =>
+ _constants[value] ??= _createConstant(value);
+
+ Constant _createConstant(ConstantValue value) {
+ final instr = Constant(this, value);
+ final insertionPoint = _constantInsertionPoint;
+ if (insertionPoint.next != null) {
+ instr.insertAfter(insertionPoint);
+ } else {
+ insertionPoint.appendInstruction(instr);
+ }
+ _constantInsertionPoint = instr;
+ return instr;
+ }
+
+ /// Remove given [Constant] instruction from the graph.
+ /// The instruction should be unused.
+ void removeConstant(Constant instr) {
+ assert(!instr.hasUses);
+ _constants.remove(instr.value);
+ if (instr == _constantInsertionPoint) {
+ _constantInsertionPoint = instr.previous!;
+ }
+ }
+
+ /// Populate [preorder], [postorder], [Block.predecessors],
+ /// [Block.preorderNumber] and [Block.postorderNumber].
+ void discoverBlocks() {
+ preorder.clear();
+ postorder.clear();
+
+ final stack = <(Block, int)>[];
+ _discoverBlock(null, entryBlock);
+ stack.add((entryBlock, entryBlock.successors.length - 1));
+ while (stack.isNotEmpty) {
+ final (block, successorIndex) = stack.removeLast();
+ if (successorIndex >= 0) {
+ stack.add((block, successorIndex - 1));
+ final successor = block.successors[successorIndex];
+ if (_discoverBlock(block, successor)) {
+ stack.add((successor, successor.successors.length - 1));
+ }
+ } else {
+ // All successors have been processed.
+ block.postorderNumber = postorder.length;
+ postorder.add(block);
+ }
+ }
+ assert(postorder.length == preorder.length);
+ }
+
+ /// Detect that a block has been visited as part of the current
+ /// [discoverBlocks] ([discoverBlocks] can be called multiple times).
+ /// The block will be 'marked' by (1) having a preorder number in the range of the
+ /// [preorder] and (2) being in the preorder list at that index.
+ bool _isVisited(Block block) {
+ final preorderNumber = block.preorderNumber;
+ return preorderNumber >= 0 &&
+ preorderNumber < preorder.length &&
+ preorder[preorderNumber] == block;
+ }
+
+ /// Visit control-flow edge between [predecessor] and [block].
+ ///
+ /// Must be called on all graph blocks in preorder.
+ /// Sets [Block.preorderNumber], populates [Block.predecessors] and
+ /// [FlowGraph.preorder].
+ /// Returns true when called the first time on this particular block
+ /// within one graph traversal, and false on all successive calls.
+ bool _discoverBlock(Block? predecessor, Block block) {
+ // If this block has a predecessor (i.e., is not the graph entry) we can
+ // assume the preorder array is non-empty.
+ assert(predecessor == null || preorder.isNotEmpty);
+ // Blocks with a single predecessor cannot have been reached before.
+ assert(block is JoinBlock || !_isVisited(block));
+
+ // If the block has already been reached, add current block as a
+ // basic-block predecessor and we are done.
+ if (_isVisited(block)) {
+ block.predecessors.add(predecessor!);
+ return false;
+ }
+
+ // Otherwise, clear the predecessors which might have been computed on
+ // some earlier call to DiscoverBlocks and record this predecessor.
+ block.predecessors.clear();
+ if (predecessor != null) block.predecessors.add(predecessor);
+
+ // Assign the preorder number and add the block to the list.
+ block.preorderNumber = preorder.length;
+ preorder.add(block);
+
+ return true;
+ }
+}
diff --git a/pkg/cfg/lib/ir/instructions.dart b/pkg/cfg/lib/ir/instructions.dart
new file mode 100644
index 0000000..b397b41
--- /dev/null
+++ b/pkg/cfg/lib/ir/instructions.dart
@@ -0,0 +1,1253 @@
+// Copyright (c) 2025, 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' as ast show DartType, Name;
+import 'package:cfg/ir/constant_value.dart';
+import 'package:cfg/ir/flow_graph.dart';
+import 'package:cfg/ir/functions.dart';
+import 'package:cfg/ir/local_variable.dart';
+import 'package:cfg/ir/source_position.dart';
+import 'package:cfg/ir/types.dart';
+import 'package:cfg/ir/use_lists.dart';
+import 'package:cfg/ir/visitor.dart';
+import 'package:cfg/utils/misc.dart';
+
+/// Base class for all instructions.
+abstract base class Instruction {
+ /// Enclosing control-flow graph.
+ final FlowGraph graph;
+
+ /// Index in the [FlowGraph.instructions].
+ final int id;
+
+ /// Source position associated with this instruction.
+ final SourcePosition sourcePosition;
+
+ /// Explicit inputs.
+ final UsesArray _inputs;
+
+ /// Enclosing basic block.
+ Block? block;
+
+ /// Next instruction in basic block.
+ Instruction? next;
+
+ /// Previous instruction in basic block.
+ Instruction? previous;
+
+ /// Values implicitly used by this instruction
+ /// e.g. for exception handling and deoptimization).
+ UsesArray? implicitInputs;
+
+ /// Create a new instruction.
+ ///
+ /// The newly created instruction belongs to [graph] but not linked into
+ /// a basic block and uses lists.
+ Instruction(this.graph, this.sourcePosition, int inputCount)
+ : id = graph.instructions.length,
+ _inputs = inputCount == 0
+ ? graph.emptyUsesArray
+ : UsesArray.allocate(graph, inputCount) {
+ for (int i = 0; i < inputCount; ++i) {
+ _inputs.at(graph, i).init(graph, this);
+ }
+ graph.instructions.add(this);
+ }
+
+ /// Returns true if this instruction is linked into a list of instructions
+ /// in a basic block (also imlplies inputs are linked in their use lists).
+ bool get isInGraph => block != null;
+
+ /// Number of explicit inputs.
+ int get inputCount => _inputs.getLength(graph);
+
+ /// [Use] corresponding to an [i]-th explicit input.
+ Use inputAt(int i) => _inputs.at(graph, i);
+
+ /// [Definition] of [i]-th explicit input.
+ Definition inputDefAt(int i) => inputAt(i).getDefinition(graph);
+
+ /// Set [i]-th input to the given [value]. Can be done only once.
+ void setInputAt(int i, Definition value) {
+ final input = inputAt(i);
+ assert(input.getNext(graph) == Use.Null);
+ assert(input.getPrevious(graph) == Use.Null);
+ input.setDefinition(graph, value);
+ }
+
+ /// Replace [i]-th input with [value]. This instruction should be
+ /// linked into a basic block.
+ void replaceInputAt(int i, Definition value) {
+ assert(isInGraph);
+ removeInputFromUseList(i);
+ setInputAt(i, value);
+ addInputToUseList(i);
+ }
+
+ /// Reduce number of inputs to [newInputCount].
+ void truncateInputs(int newInputCount) {
+ _inputs.truncateTo(graph, newInputCount);
+ }
+
+ /// Link this instruction to the [next] instruction in basic block.
+ void linkTo(Instruction next) {
+ assert(!identical(this, next));
+ this.next = next;
+ next.previous = this;
+ next.block = this.block;
+ }
+
+ /// Add [inputIndex]-th input to use list of its definition.
+ ///
+ /// This is a low-level operation which is rarely needed.
+ /// Prefer using [appendInstruction] or [insertAfter].
+ void addInputToUseList(int inputIndex) {
+ final input = inputAt(inputIndex);
+ assert(input.getNext(graph) == Use.Null);
+ assert(input.getPrevious(graph) == Use.Null);
+ final def = input.getDefinition(graph);
+ final nextUse = def._inputUses;
+ if (nextUse != Use.Null) {
+ assert(nextUse.getPrevious(graph) == Use.Null);
+ input.setNext(graph, nextUse);
+ nextUse.setPrevious(graph, input);
+ }
+ def._inputUses = input;
+ }
+
+ void _addInputsToUseLists() {
+ for (int i = 0, n = inputCount; i < n; ++i) {
+ addInputToUseList(i);
+ }
+ assert(implicitInputs == null);
+ }
+
+ /// Remove [inputIndex]-th input from use list of its definition.
+ ///
+ /// This is a low-level operation which is rarely needed.
+ /// Prefer using [replaceInputAt] or [removeFromGraph].
+ void removeInputFromUseList(int inputIndex) {
+ final input = inputAt(inputIndex);
+ assert(input.getInstruction(graph) == this);
+ final nextUse = input.getNext(graph);
+ final prevUse = input.getPrevious(graph);
+ if (prevUse == Use.Null) {
+ final def = input.getDefinition(graph);
+ assert(def._inputUses == input);
+ def._inputUses = nextUse;
+ } else {
+ prevUse.setNext(graph, nextUse);
+ }
+ if (nextUse != Use.Null) {
+ nextUse.setPrevious(graph, prevUse);
+ }
+ input.setNext(graph, Use.Null);
+ input.setPrevious(graph, Use.Null);
+ }
+
+ /// Remove all inputs from their use lists.
+ void removeInputsFromUseLists() {
+ for (int i = 0, n = inputCount; i < n; ++i) {
+ removeInputFromUseList(i);
+ }
+ }
+
+ /// Append an unlinked [instr] after this instruction,
+ /// which should be the last instruction appended into basic block.
+ ///
+ /// Also, add all inputs of [instr] to their use lists.
+ void appendInstruction(Instruction instr) {
+ assert(isInGraph);
+ assert(!instr.isInGraph);
+ assert(this.next == null);
+ assert(this.block!.lastInstruction == this);
+ assert(instr.next == null);
+ assert(instr.previous == null);
+ assert(instr.block == null);
+ linkTo(instr);
+ instr._addInputsToUseLists();
+ block!.lastInstruction = instr;
+ }
+
+ /// Insert this instruction between [previous] and [previous.next].
+ /// (which should be linked into a basic block).
+ ///
+ /// If [addInputsToUseLists], then also add all inputs to their use lists.
+ void insertAfter(Instruction previous, {bool addInputsToUseLists = true}) {
+ assert(previous.isInGraph);
+ assert(!isInGraph);
+ final next = previous.next!;
+ assert(previous.block != null);
+ assert(this.next == null);
+ assert(this.previous == null);
+ assert(this.block == null);
+
+ this.previous = previous;
+ this.next = next;
+ this.block = previous.block;
+ next.previous = this;
+ previous.next = this;
+
+ if (addInputsToUseLists) {
+ _addInputsToUseLists();
+ }
+ }
+
+ /// Insert this instruction between [next.previous] and [next].
+ /// (which should be linked into a basic block).
+ ///
+ /// If [addInputsToUseLists], then also add all inputs to their use lists.
+ void insertBefore(Instruction next, {bool addInputsToUseLists = true}) {
+ assert(next.isInGraph);
+ insertAfter(next.previous!, addInputsToUseLists: addInputsToUseLists);
+ }
+
+ /// Unlink this instruction from its basic block and use lists.
+ void removeFromGraph() {
+ assert(isInGraph);
+ assert(block != null);
+ assert(this != block);
+
+ removeInputsFromUseLists();
+ final next = this.next;
+ final previous = this.previous!;
+ previous.next = next;
+ if (next != null) {
+ next.previous = previous;
+ } else {
+ assert(this is ControlFlowInstruction);
+ assert(this == block!.lastInstruction);
+ block!.lastInstruction = previous;
+ }
+ this.next = null;
+ this.previous = null;
+ this.block = null;
+ assert(!isInGraph);
+ }
+
+ /// Whether this instruction can potentially throw a Dart exception.
+ bool get canThrow;
+
+ /// Whether this instruction can have any visible side-effects.
+ bool get hasSideEffects;
+
+ /// Returns true if this instruction is idempotent (i.e.
+ /// repeating this instruction does not have any effect),
+ /// and it is a subject to value numbering.
+ bool get isIdempotent => false;
+
+ /// Returns true if extra instruction attributes are equal.
+ /// Used only for idempotent instructions of the same type.
+ bool attributesEqual(Instruction other) =>
+ throw 'Not implemented for ${runtimeType}';
+
+ R accept<R>(InstructionVisitor<R> v);
+}
+
+/// Trait of instructions which can potentially throw Dart exceptions.
+base mixin CanThrow on Instruction {
+ bool get canThrow => true;
+}
+
+/// Trait of instructions which cannot throw Dart exceptions.
+base mixin NoThrow on Instruction {
+ bool get canThrow => false;
+}
+
+/// Trait of instructions which can have visible side-effects.
+base mixin HasSideEffects on Instruction {
+ bool get hasSideEffects => true;
+}
+
+/// Trait of instructions which do not have any side-effects.
+base mixin Pure on Instruction {
+ bool get hasSideEffects => false;
+}
+
+/// Trait of idempotent instructions.
+base mixin Idempotent on Instruction {
+ bool get isIdempotent => true;
+}
+
+/// Base class for instructions which yield a value.
+abstract base class Definition extends Instruction {
+ Use _inputUses = Use.Null;
+ Use _implicitUses = Use.Null;
+
+ Definition(super.graph, super.sourcePosition, super.inputCount);
+
+ UsesIterable get inputUses => UsesIterable(graph, _inputUses);
+ UsesIterable get implicitUses => UsesIterable(graph, _implicitUses);
+
+ bool get hasInputUses => _inputUses != Use.Null;
+ bool get hasImplicitUses => _implicitUses != Use.Null;
+ bool get hasUses => hasInputUses || hasImplicitUses;
+
+ /// Replace all uses of this instruction with [other].
+ void replaceUsesWith(Definition other) {
+ if (hasInputUses) {
+ Use last = Use.Null;
+ for (final use in inputUses) {
+ use.setDefinition(graph, other);
+ last = use;
+ }
+ final tail = other._inputUses;
+ last.setNext(graph, tail);
+ if (tail != Use.Null) {
+ tail.setPrevious(graph, last);
+ }
+ other._inputUses = this._inputUses;
+ this._inputUses = Use.Null;
+ }
+ if (hasImplicitUses) {
+ Use last = Use.Null;
+ for (final use in implicitUses) {
+ use.setDefinition(graph, other);
+ last = use;
+ }
+ final tail = other._implicitUses;
+ last.setNext(graph, tail);
+ if (tail != Use.Null) {
+ tail.setPrevious(graph, last);
+ }
+ other._implicitUses = this._implicitUses;
+ this._implicitUses = Use.Null;
+ }
+ }
+
+ /// Result type of this instruction.
+ CType get type;
+
+ /// Whether this instruction can yield a zero value.
+ bool get canBeZero => true;
+
+ /// Whether this instruction can yield a negative value.
+ bool get canBeNegative => true;
+
+ /// Returns the only instruction which uses result of this instruction as
+ /// an explicit input.
+ ///
+ /// Returns `null` if there are no or multiple uses.
+ Instruction? get singleUser {
+ if (hasInputUses && !hasImplicitUses) {
+ final use = _inputUses;
+ if (use.getNext(graph) == Use.Null) {
+ return use.getInstruction(graph);
+ }
+ }
+ return null;
+ }
+}
+
+/// Forward iterator over instructions in the block.
+final class _InstructionsIterator implements Iterator<Instruction> {
+ Instruction? _current;
+ Instruction? _next;
+
+ _InstructionsIterator(this._next);
+
+ @override
+ bool moveNext() {
+ _current = _next;
+ _next = _current?.next;
+ return (_current != null);
+ }
+
+ @override
+ Instruction get current => _current!;
+}
+
+/// Backwards iterator over instructions in the block.
+final class _ReverseInstructionsIterator implements Iterator<Instruction> {
+ Instruction? _current;
+ Instruction _previous;
+
+ _ReverseInstructionsIterator(this._previous);
+
+ @override
+ bool moveNext() {
+ final instr = _previous.previous;
+ if (instr == null) {
+ assert(_previous is Block);
+ _current = null;
+ return false;
+ } else {
+ _current = _previous;
+ _previous = instr;
+ return true;
+ }
+ }
+
+ @override
+ Instruction get current => _current!;
+}
+
+/// Iterable for backwards iteration of instructions in the block.
+final class _ReverseInstructionsIterable extends Iterable<Instruction> {
+ final Block _block;
+
+ _ReverseInstructionsIterable(this._block);
+
+ @override
+ Iterator<Instruction> get iterator =>
+ _ReverseInstructionsIterator(_block.lastInstruction);
+}
+
+/// Basic block.
+abstract base class Block extends Instruction
+ with NoThrow, Pure, Iterable<Instruction> {
+ final List<Block> predecessors = [];
+ final List<Block> successors = [];
+ late Instruction lastInstruction;
+ CatchBlock? exceptionHandler;
+
+ int preorderNumber = -1;
+ int postorderNumber = -1;
+
+ Block(FlowGraph graph, SourcePosition sourcePosition)
+ : super(graph, sourcePosition, 0) {
+ this.block = this;
+ this.lastInstruction = this;
+ }
+
+ /// Replace [oldPredecessor] with [newPredecessor].
+ void replacePredecessor(Block oldPredecessor, Block newPredecessor) {
+ final predecessors = this.predecessors;
+ for (int i = 0, n = predecessors.length; i < n; ++i) {
+ if (predecessors[i] == oldPredecessor) {
+ predecessors[i] = newPredecessor;
+ }
+ }
+ }
+
+ /// Iterate over instructions in the block from the first to the last.
+ /// Iteration is robust wrt removal of the current instruction.
+ @override
+ Iterator<Instruction> get iterator => _InstructionsIterator(next);
+
+ /// Iterate over instructions in the block from the last to the first.
+ /// Iteration is robust wrt removal of the current instruction.
+ Iterable<Instruction> get reversed => _ReverseInstructionsIterable(this);
+}
+
+/// The entry block in the [FlowGraph].
+///
+/// Contains all [Constant] instructions and [Parameter] instructions
+/// corresponding to the function parameters.
+final class EntryBlock extends Block {
+ EntryBlock(super.graph, super.sourcePosition);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitEntryBlock(this);
+}
+
+/// Iterator over [Phi] instructions in the [JoinBlock].
+final class _PhiIterator implements Iterator<Phi> {
+ Phi? _current;
+ Phi? _next;
+
+ _PhiIterator(JoinBlock block) {
+ final nextInstruction = block.next;
+ _next = (nextInstruction is Phi) ? nextInstruction : null;
+ }
+
+ @override
+ bool moveNext() {
+ _current = _next;
+ final nextInstruction = _current?.next;
+ _next = (nextInstruction is Phi) ? nextInstruction : null;
+ return (_current != null);
+ }
+
+ @override
+ Phi get current => _current!;
+}
+
+/// Iterable over [Phi] instructions in the [JoinBlock].
+final class _PhiIterable extends Iterable<Phi> {
+ final JoinBlock _block;
+
+ _PhiIterable(this._block);
+
+ @override
+ Iterator<Phi> get iterator => _PhiIterator(_block);
+}
+
+/// Basic block which can have multiple predecessors.
+///
+/// May contain [Phi] instructions in the beginning of the block.
+final class JoinBlock extends Block {
+ JoinBlock(super.graph, super.sourcePosition);
+
+ Iterable<Phi> get phis => _PhiIterable(this);
+
+ bool get hasPhis => next is Phi;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitJoinBlock(this);
+}
+
+/// Target block of a branch.
+final class TargetBlock extends Block {
+ TargetBlock(super.graph, super.sourcePosition);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTargetBlock(this);
+}
+
+/// Exception handler block.
+///
+/// May contain [Parameter] instructions in the beginning of the block
+/// to represent incoming values of local variables, exception object and
+/// stack trace.
+final class CatchBlock extends Block {
+ CatchBlock(super.graph, super.sourcePosition);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitCatchBlock(this);
+}
+
+/// Marker interface for instructions which can end basic block.
+abstract class ControlFlowInstruction {}
+
+/// Unconditional jump to the sole successor of this basic block.
+final class Goto extends Instruction
+ with NoThrow, Pure
+ implements ControlFlowInstruction {
+ Goto(FlowGraph graph, SourcePosition sourcePosition)
+ : super(graph, sourcePosition, 0);
+
+ Block get target => block!.successors.single;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitGoto(this);
+}
+
+/// Conditional branch to either true of false successors of this basic block.
+final class Branch extends Instruction
+ with NoThrow, Pure
+ implements ControlFlowInstruction {
+ Branch(FlowGraph graph, SourcePosition sourcePosition, Definition condition)
+ : super(graph, sourcePosition, 1) {
+ setInputAt(0, condition);
+ }
+
+ Definition get condition => inputDefAt(0);
+ TargetBlock get trueSuccessor => block!.successors[0] as TargetBlock;
+ TargetBlock get falseSuccessor => block!.successors[1] as TargetBlock;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitBranch(this);
+}
+
+/// Unconditional jump to the try block body (the first succesor of this
+/// basic block). The second successor of this basic block is a catch block.
+final class TryEntry extends Instruction
+ with NoThrow, Pure
+ implements ControlFlowInstruction {
+ TryEntry(FlowGraph graph, SourcePosition sourcePosition)
+ : super(graph, sourcePosition, 0);
+
+ TargetBlock get tryBody => block!.successors[0] as TargetBlock;
+ CatchBlock get catchBlock => block!.successors[1] as CatchBlock;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTryEntry(this);
+}
+
+/// The result of instruction `v = Phi(v[0],...,v[N-1])` is `v[i]` when
+/// control is transferred from the i-th predecessor block.
+///
+/// Number of inputs always matches number of predecessor blocks.
+final class Phi extends Definition with NoThrow, Pure {
+ /// Local variable for which this [Phi] was originally created.
+ final LocalVariable variable;
+
+ Phi(super.graph, super.sourcePosition, this.variable, super.inputCount);
+
+ @override
+ CType get type => variable.type;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitPhi(this);
+}
+
+/// Return value from the current function.
+final class Return extends Instruction
+ with NoThrow, Pure
+ implements ControlFlowInstruction {
+ Return(FlowGraph graph, SourcePosition sourcePosition, Definition value)
+ : super(graph, sourcePosition, 1) {
+ setInputAt(0, value);
+ }
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitReturn(this);
+}
+
+enum ComparisonOpcode {
+ // Simple object pointer equality.
+ equal('=='),
+ notEqual('!='),
+ // identical with special cases for num.
+ identical('==='),
+ notIdentical('!=='),
+ // int comparisons.
+ intEqual('int =='),
+ intNotEqual('int !='),
+ intLess('int <'),
+ intLessOrEqual('int <='),
+ intGreater('int >'),
+ intGreaterOrEqual('int >='),
+ // int bitwise tests
+ intTestIsZero('int & == 0'),
+ intTestIsNotZero('int & != 0'),
+ // double comparisons.
+ doubleEqual('double =='),
+ doubleNotEqual('double !='),
+ doubleLess('double <'),
+ doubleLessOrEqual('double <='),
+ doubleGreater('double >'),
+ doubleGreaterOrEqual('double >=');
+
+ final String token;
+ const ComparisonOpcode(this.token);
+
+ bool get isIntComparison => switch (this) {
+ intEqual ||
+ intNotEqual ||
+ intLess ||
+ intLessOrEqual ||
+ intGreater ||
+ intGreaterOrEqual ||
+ intTestIsZero ||
+ intTestIsNotZero => true,
+ _ => false,
+ };
+
+ bool get isDoubleComparison => switch (this) {
+ doubleEqual ||
+ doubleNotEqual ||
+ doubleLess ||
+ doubleLessOrEqual ||
+ doubleGreater ||
+ doubleGreaterOrEqual => true,
+ _ => false,
+ };
+
+ ComparisonOpcode flipOperands() => switch (this) {
+ equal ||
+ notEqual ||
+ identical ||
+ notIdentical ||
+ intEqual ||
+ intNotEqual ||
+ intTestIsZero ||
+ intTestIsNotZero ||
+ doubleEqual ||
+ doubleNotEqual => this,
+ intLess => intGreaterOrEqual,
+ intLessOrEqual => intGreater,
+ intGreater => intLessOrEqual,
+ intGreaterOrEqual => intLess,
+ doubleLess => doubleGreaterOrEqual,
+ doubleLessOrEqual => doubleGreater,
+ doubleGreater => doubleLessOrEqual,
+ doubleGreaterOrEqual => doubleLess,
+ };
+
+ bool get canBeNegated => switch (this) {
+ doubleLess ||
+ doubleLessOrEqual ||
+ doubleGreater ||
+ doubleGreaterOrEqual => false,
+ _ => true,
+ };
+
+ ComparisonOpcode negate() => switch (this) {
+ equal => notEqual,
+ notEqual => equal,
+ identical => notIdentical,
+ notIdentical => identical,
+ intEqual => intNotEqual,
+ intNotEqual => intEqual,
+ intLess => intGreaterOrEqual,
+ intLessOrEqual => intGreater,
+ intGreater => intLessOrEqual,
+ intGreaterOrEqual => intLess,
+ intTestIsZero => intTestIsNotZero,
+ intTestIsNotZero => intTestIsZero,
+ doubleEqual => doubleNotEqual,
+ doubleNotEqual => doubleEqual,
+ doubleLess ||
+ doubleLessOrEqual ||
+ doubleGreater ||
+ doubleGreaterOrEqual => throw '${token} cannot be negated',
+ };
+}
+
+/// Compare two operands.
+final class Comparison extends Definition with NoThrow, Pure, Idempotent {
+ ComparisonOpcode op;
+
+ Comparison(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition left,
+ Definition right,
+ ) : super(graph, sourcePosition, 2) {
+ setInputAt(0, left);
+ setInputAt(1, right);
+ }
+
+ Definition get left => inputDefAt(0);
+ Definition get right => inputDefAt(1);
+
+ @override
+ CType get type => const BoolType();
+
+ @override
+ bool attributesEqual(covariant Comparison other) => op == other.op;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitComparison(this);
+}
+
+/// Instruction representing a constant value.
+///
+/// Should not be created directly, use [FlowGraph.getConstant] instead.
+final class Constant extends Definition with NoThrow, Pure {
+ final ConstantValue value;
+
+ Constant(FlowGraph graph, this.value) : super(graph, noPosition, 0);
+
+ @override
+ bool get canBeZero => value.isZero;
+
+ @override
+ bool get canBeNegative => value.isNegative;
+
+ @override
+ CType get type => value.type;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitConstant(this);
+}
+
+/// Base class for various calls.
+abstract base class CallInstruction extends Definition
+ with CanThrow, HasSideEffects {
+ CallInstruction(super.graph, super.sourcePosition, super.inputCount);
+
+ bool get hasTypeArguments => inputCount > 0 && inputDefAt(0) is TypeArguments;
+ TypeArguments? get typeArguments =>
+ hasTypeArguments ? inputDefAt(0) as TypeArguments : null;
+}
+
+/// Direct call of the target function.
+final class DirectCall extends CallInstruction {
+ final CFunction target;
+
+ @override
+ final CType type;
+
+ DirectCall(
+ super.graph,
+ super.sourcePosition,
+ this.target,
+ super.inputCount,
+ this.type,
+ );
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitDirectCall(this);
+}
+
+/// Interface call via given interface target.
+final class InterfaceCall extends CallInstruction {
+ final CFunction interfaceTarget;
+
+ @override
+ final CType type;
+
+ InterfaceCall(
+ super.graph,
+ super.sourcePosition,
+ this.interfaceTarget,
+ super.inputCount,
+ this.type,
+ );
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitInterfaceCall(this);
+}
+
+enum DynamicCallKind { method, getter, setter }
+
+/// Dynamic call via given selector.
+final class DynamicCall extends CallInstruction {
+ final ast.Name selector;
+ final DynamicCallKind kind;
+
+ DynamicCall(
+ super.graph,
+ super.sourcePosition,
+ this.selector,
+ this.kind,
+ super.inputCount,
+ );
+
+ @override
+ CType get type => const TopType();
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitDynamicCall(this);
+}
+
+/// Parameter of a function or a catch block.
+final class Parameter extends Definition with NoThrow, Pure {
+ final LocalVariable variable;
+
+ Parameter(FlowGraph graph, SourcePosition sourcePosition, this.variable)
+ : super(graph, sourcePosition, 0);
+
+ bool get isFunctionParameter => block is EntryBlock;
+ bool get isCatchParameter => block is CatchBlock;
+
+ @override
+ CType get type => variable.type;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitParameter(this);
+}
+
+/// Loads value from the local variable.
+///
+/// [LoadLocal] instructions are only used before
+/// IR is converted to SSA form.
+final class LoadLocal extends Definition with NoThrow, Pure {
+ final LocalVariable variable;
+
+ LoadLocal(FlowGraph graph, SourcePosition sourcePosition, this.variable)
+ : super(graph, sourcePosition, 0);
+
+ @override
+ CType get type => variable.type;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitLoadLocal(this);
+}
+
+/// Store value to the local variable.
+///
+/// [StoreLocal] instructions are only used before
+/// IR is converted to SSA form.
+final class StoreLocal extends Instruction with NoThrow, HasSideEffects {
+ final LocalVariable variable;
+
+ StoreLocal(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.variable,
+ Definition value,
+ ) : super(graph, sourcePosition, 1) {
+ setInputAt(0, value);
+ }
+
+ Definition get value => inputDefAt(0);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitStoreLocal(this);
+}
+
+/// Throw given exception object. Also takes optional stack trace
+/// input to rethrow exception object without collecting a new stack trace.
+final class Throw extends Instruction
+ with CanThrow, HasSideEffects
+ implements ControlFlowInstruction {
+ Throw(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ Definition exception,
+ Definition? stackTrace,
+ ) : super(graph, sourcePosition, stackTrace != null ? 2 : 1) {
+ setInputAt(0, exception);
+ if (stackTrace != null) {
+ setInputAt(1, stackTrace);
+ }
+ }
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitThrow(this);
+}
+
+/// Represents collection of class and function type parameters.
+final class TypeParameters extends Definition with NoThrow, Pure {
+ TypeParameters(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ Definition? receiver,
+ ) : super(graph, sourcePosition, receiver != null ? 1 : 0) {
+ if (receiver != null) {
+ setInputAt(0, receiver);
+ }
+ }
+
+ @override
+ CType get type => const TypeParametersType();
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTypeParameters(this);
+}
+
+/// Casts input object to the given type.
+///
+/// Checked casts throw TypeError if
+/// object is not assignable to the given type.
+final class TypeCast extends Definition with CanThrow, Pure, Idempotent {
+ /// Target type for the type cast.
+ final CType testedType;
+
+ /// Whether this type cast involves check at runtime.
+ bool isChecked;
+
+ TypeCast(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ Definition object,
+ this.testedType,
+ Definition? typeParameters, {
+ this.isChecked = true,
+ }) : super(graph, sourcePosition, typeParameters != null ? 2 : 1) {
+ setInputAt(0, object);
+ if (typeParameters != null) {
+ setInputAt(1, typeParameters);
+ }
+ }
+
+ Definition get operand => inputDefAt(0);
+ Definition? get typeParameters => (inputCount > 1) ? inputDefAt(1) : null;
+
+ @override
+ CType get type => testedType;
+
+ @override
+ bool get canThrow => isChecked;
+
+ @override
+ bool attributesEqual(covariant TypeCast other) =>
+ // 'isChecked' is not taken into account as checked and unchecked casts
+ // against the same type are congruent wrt value numbering.
+ testedType == other.testedType;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTypeCast(this);
+}
+
+/// Test if input object is assignable to the given type.
+final class TypeTest extends Definition with NoThrow, Pure, Idempotent {
+ final CType testedType;
+
+ TypeTest(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ Definition object,
+ this.testedType,
+ Definition? typeParameters,
+ ) : super(graph, sourcePosition, typeParameters != null ? 2 : 1) {
+ setInputAt(0, object);
+ if (typeParameters != null) {
+ setInputAt(1, typeParameters);
+ }
+ }
+
+ Definition get operand => inputDefAt(0);
+ Definition? get typeParameters => (inputCount > 1) ? inputDefAt(1) : null;
+
+ @override
+ CType get type => const BoolType();
+
+ @override
+ bool attributesEqual(covariant TypeTest other) =>
+ testedType == other.testedType;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTypeTest(this);
+}
+
+/// Represents a list of type arguments passed to a call.
+///
+/// Only used as the first input of call instructions.
+final class TypeArguments extends Definition with NoThrow, Pure, Idempotent {
+ final List<ast.DartType> types;
+ TypeArguments(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.types,
+ Definition? typeParameters,
+ ) : super(graph, sourcePosition, typeParameters != null ? 1 : 0) {
+ if (typeParameters != null) {
+ setInputAt(0, typeParameters);
+ }
+ }
+
+ Definition? get typeParameters => (inputCount > 0) ? inputDefAt(0) : null;
+
+ @override
+ CType get type => const TypeArgumentsType();
+
+ @override
+ bool attributesEqual(covariant TypeArguments other) =>
+ listEquals(types, other.types);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitTypeArguments(this);
+}
+
+enum BinaryIntOpcode {
+ add('+'),
+ sub('-'),
+ mul('*'),
+ truncatingDiv('~/'),
+ mod('%'),
+ rem('remainder'),
+ bitOr('|'),
+ bitAnd('&'),
+ bitXor('^'),
+ shiftLeft('<<'),
+ shiftRight('>>'),
+ unsignedShiftRight('>>>');
+
+ final String token;
+ const BinaryIntOpcode(this.token);
+
+ bool get isCommutative => switch (this) {
+ add || mul || bitOr || bitAnd || bitXor => true,
+ _ => false,
+ };
+}
+
+/// Binary operation on two int operands.
+final class BinaryIntOp extends Definition with Pure, Idempotent {
+ BinaryIntOpcode op;
+
+ BinaryIntOp(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition left,
+ Definition right,
+ ) : super(graph, sourcePosition, 2) {
+ setInputAt(0, left);
+ setInputAt(1, right);
+ }
+
+ Definition get left => inputDefAt(0);
+ Definition get right => inputDefAt(1);
+
+ @override
+ bool get canThrow => switch (op) {
+ BinaryIntOpcode.truncatingDiv ||
+ BinaryIntOpcode.mod ||
+ BinaryIntOpcode.rem => right.canBeZero,
+ BinaryIntOpcode.shiftLeft ||
+ BinaryIntOpcode.shiftRight ||
+ BinaryIntOpcode.unsignedShiftRight => right.canBeNegative,
+ _ => false,
+ };
+
+ @override
+ CType get type => const IntType();
+
+ @override
+ bool attributesEqual(covariant BinaryIntOp other) => op == other.op;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitBinaryIntOp(this);
+}
+
+enum UnaryIntOpcode {
+ neg('-'),
+ bitNot('~'),
+ toDouble('toDouble'),
+ abs('abs'),
+ sign('sign');
+
+ final String token;
+ const UnaryIntOpcode(this.token);
+}
+
+/// Unary operation on the int operand.
+final class UnaryIntOp extends Definition with NoThrow, Pure, Idempotent {
+ UnaryIntOpcode op;
+
+ UnaryIntOp(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition operand,
+ ) : super(graph, sourcePosition, 1) {
+ setInputAt(0, operand);
+ }
+
+ Definition get operand => inputDefAt(0);
+
+ @override
+ CType get type => switch (op) {
+ UnaryIntOpcode.toDouble => const DoubleType(),
+ _ => const IntType(),
+ };
+
+ @override
+ bool attributesEqual(covariant UnaryIntOp other) => op == other.op;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitUnaryIntOp(this);
+}
+
+enum BinaryDoubleOpcode {
+ add('+'),
+ sub('-'),
+ mul('*'),
+ div('/'),
+ truncatingDiv('~/'),
+ mod('%'),
+ rem('remainder');
+
+ final String token;
+ const BinaryDoubleOpcode(this.token);
+
+ bool get isCommutative => switch (this) {
+ add || mul => true,
+ _ => false,
+ };
+}
+
+/// Binary operation on two double operands.
+final class BinaryDoubleOp extends Definition with NoThrow, Pure, Idempotent {
+ BinaryDoubleOpcode op;
+
+ BinaryDoubleOp(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition left,
+ Definition right,
+ ) : super(graph, sourcePosition, 2) {
+ setInputAt(0, left);
+ setInputAt(1, right);
+ }
+
+ Definition get left => inputDefAt(0);
+ Definition get right => inputDefAt(1);
+
+ @override
+ CType get type => switch (op) {
+ BinaryDoubleOpcode.truncatingDiv => const IntType(),
+ _ => const DoubleType(),
+ };
+
+ @override
+ bool attributesEqual(covariant BinaryDoubleOp other) => op == other.op;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitBinaryDoubleOp(this);
+}
+
+enum UnaryDoubleOpcode {
+ neg('-'),
+ abs('abs'),
+ sign('sign'),
+ square('square'),
+ round('round'),
+ floor('floor'),
+ ceil('ceil'),
+ truncate('truncate'),
+ roundToDouble('roundToDouble'),
+ floorToDouble('floorToDouble'),
+ ceilToDouble('ceilToDouble'),
+ truncateToDouble('truncateToDouble');
+
+ final String token;
+ const UnaryDoubleOpcode(this.token);
+}
+
+/// Unary operation on the double operand.
+final class UnaryDoubleOp extends Definition with NoThrow, Pure, Idempotent {
+ UnaryDoubleOpcode op;
+
+ UnaryDoubleOp(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition operand,
+ ) : super(graph, sourcePosition, 1) {
+ setInputAt(0, operand);
+ }
+
+ Definition get operand => inputDefAt(0);
+
+ @override
+ CType get type => switch (op) {
+ UnaryDoubleOpcode.round ||
+ UnaryDoubleOpcode.floor ||
+ UnaryDoubleOpcode.ceil ||
+ UnaryDoubleOpcode.truncate => const IntType(),
+ _ => const DoubleType(),
+ };
+
+ @override
+ bool attributesEqual(covariant UnaryDoubleOp other) => op == other.op;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitUnaryDoubleOp(this);
+}
+
+/// Marker for the back-end specific instructions.
+base mixin BackendInstruction on Instruction {}
+
+/// Combined comparison and branch.
+///
+/// Certain back-ends may create [CompareAndBranch] during lowering.
+final class CompareAndBranch extends Instruction
+ with NoThrow, Pure, BackendInstruction
+ implements ControlFlowInstruction {
+ ComparisonOpcode op;
+
+ CompareAndBranch(
+ FlowGraph graph,
+ SourcePosition sourcePosition,
+ this.op,
+ Definition left,
+ Definition right,
+ ) : super(graph, sourcePosition, 2) {
+ setInputAt(0, left);
+ setInputAt(1, right);
+ }
+
+ Definition get left => inputDefAt(0);
+ Definition get right => inputDefAt(1);
+ TargetBlock get trueSuccessor => block!.successors[0] as TargetBlock;
+ TargetBlock get falseSuccessor => block!.successors[1] as TargetBlock;
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitCompareAndBranch(this);
+}
+
+/// Base class for move operations, part of [ParallelMove].
+abstract base class MoveOp {}
+
+/// In native back-ends, register allocator inserts [ParallelMove]
+/// instructions to copy values atomically between registers
+/// and memory locations.
+final class ParallelMove extends Instruction
+ with NoThrow, HasSideEffects, BackendInstruction {
+ final List<MoveOp> moves = [];
+
+ ParallelMove(FlowGraph graph) : super(graph, noPosition, 0);
+
+ @override
+ R accept<R>(InstructionVisitor<R> v) => v.visitParallelMove(this);
+}
diff --git a/pkg/cfg/lib/ir/local_variable.dart b/pkg/cfg/lib/ir/local_variable.dart
new file mode 100644
index 0000000..52e5434
--- /dev/null
+++ b/pkg/cfg/lib/ir/local_variable.dart
@@ -0,0 +1,29 @@
+// Copyright (c) 2025, 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' as ast show VariableDeclaration;
+import 'package:cfg/ir/types.dart';
+
+/// Local variable or a function parameter.
+///
+/// Local variables are used in the flow graph before
+/// it is converted to SSA form.
+class LocalVariable {
+ /// Name of the variable.
+ final String name;
+
+ /// Declaration of the variable in the AST, if any.
+ final ast.VariableDeclaration? declaration;
+
+ /// Index of the variable in the [FlowGraph.localVariables].
+ final int index;
+
+ /// Type of the variable.
+ final CType type;
+
+ LocalVariable(this.name, this.declaration, this.index, this.type);
+
+ @override
+ String toString() => name;
+}
diff --git a/pkg/cfg/lib/ir/use_lists.dart b/pkg/cfg/lib/ir/use_lists.dart
new file mode 100644
index 0000000..4075280
--- /dev/null
+++ b/pkg/cfg/lib/ir/use_lists.dart
@@ -0,0 +1,125 @@
+// Copyright (c) 2025, 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:cfg/ir/flow_graph.dart';
+import 'package:cfg/ir/instructions.dart';
+import 'package:cfg/utils/arena.dart';
+
+/// A single use of the result of the instruction in another instruction.
+extension type const Use(ArenaPointer _ptr) {
+ // Terminator in the use lists.
+ static const Use Null = Use(ArenaPointer.Null);
+
+ // Each use occupies 4 slots:
+ // instruction index, definition index, next use, previous use.
+ static const int instructionOffset = 0;
+ static const int definitionOffset = 1;
+ static const int nextOffset = 2;
+ static const int previousOffset = 3;
+
+ // Size of each use. Should be a power of 2 for efficiency.
+ static const int useSize = 4;
+
+ @pragma("vm:prefer-inline")
+ void init(FlowGraph graph, Instruction instr) {
+ setInstruction(graph, instr);
+ setNext(graph, Use.Null);
+ setPrevious(graph, Use.Null);
+ }
+
+ @pragma("vm:prefer-inline")
+ Instruction getInstruction(FlowGraph graph) =>
+ graph.instructions[graph[_ptr + instructionOffset]];
+
+ @pragma("vm:prefer-inline")
+ void setInstruction(FlowGraph graph, Instruction value) {
+ graph[_ptr + instructionOffset] = value.id;
+ }
+
+ @pragma("vm:prefer-inline")
+ Definition getDefinition(FlowGraph graph) =>
+ graph.instructions[graph[_ptr + definitionOffset]] as Definition;
+
+ @pragma("vm:prefer-inline")
+ void setDefinition(FlowGraph graph, Definition value) {
+ graph[_ptr + definitionOffset] = value.id;
+ }
+
+ @pragma("vm:prefer-inline")
+ Use getNext(FlowGraph graph) => Use(ArenaPointer(graph[_ptr + nextOffset]));
+
+ @pragma("vm:prefer-inline")
+ void setNext(FlowGraph graph, Use value) {
+ graph[_ptr + nextOffset] = value._ptr.toInt();
+ }
+
+ @pragma("vm:prefer-inline")
+ Use getPrevious(FlowGraph graph) =>
+ Use(ArenaPointer(graph[_ptr + previousOffset]));
+
+ @pragma("vm:prefer-inline")
+ void setPrevious(FlowGraph graph, Use value) {
+ graph[_ptr + previousOffset] = value._ptr.toInt();
+ }
+}
+
+/// Fixed-size array of uses.
+extension type const UsesArray(ArenaPointer _ptr) {
+ // Array has a length, followed by elements.
+ static const int lengthOffset = 0;
+ static const int elementsOffset = 1;
+
+ int getLength(FlowGraph graph) {
+ assert(_ptr != ArenaPointer.Null);
+ return graph[_ptr + lengthOffset];
+ }
+
+ Use at(FlowGraph graph, int index) {
+ assert(_ptr != ArenaPointer.Null);
+ assert(0 <= index && index < getLength(graph));
+ return Use(_ptr + elementsOffset + index * Use.useSize);
+ }
+
+ void truncateTo(FlowGraph graph, int newLength) {
+ assert(_ptr != ArenaPointer.Null);
+ assert((0 <= newLength) && (newLength <= getLength(graph)));
+ graph[_ptr + lengthOffset] = newLength;
+ }
+
+ static UsesArray allocate(FlowGraph graph, int length) {
+ assert(length >= 0);
+ final ptr = graph.allocate(elementsOffset + length * Use.useSize);
+ graph[ptr + lengthOffset] = length;
+ return UsesArray(ptr);
+ }
+}
+
+class _UsesIterator implements Iterator<Use> {
+ final FlowGraph graph;
+ Use _current = Use.Null;
+ Use _next;
+
+ _UsesIterator(this.graph, this._next);
+
+ @override
+ bool moveNext() {
+ _current = _next;
+ _next = (_current != Use.Null) ? _current.getNext(graph) : Use.Null;
+ return (_current != Use.Null);
+ }
+
+ @override
+ Use get current => _current;
+}
+
+class UsesIterable extends Iterable<Use> {
+ final FlowGraph graph;
+ Use _first;
+
+ UsesIterable(this.graph, this._first);
+ UsesIterable.empty(this.graph) : _first = Use.Null;
+
+ @override
+ Iterator<Use> get iterator => _UsesIterator(graph, _first);
+}
diff --git a/pkg/cfg/lib/ir/visitor.dart b/pkg/cfg/lib/ir/visitor.dart
new file mode 100644
index 0000000..f7a608f
--- /dev/null
+++ b/pkg/cfg/lib/ir/visitor.dart
@@ -0,0 +1,93 @@
+// Copyright (c) 2025, 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:cfg/ir/instructions.dart';
+
+/// Visitor over [Instruction].
+abstract interface class InstructionVisitor<R> {
+ // Basic blocks.
+ R visitEntryBlock(EntryBlock instr);
+ R visitJoinBlock(JoinBlock instr);
+ R visitTargetBlock(TargetBlock instr);
+ R visitCatchBlock(CatchBlock instr);
+ // Regular instructions.
+ R visitGoto(Goto instr);
+ R visitBranch(Branch instr);
+ R visitTryEntry(TryEntry instr);
+ R visitPhi(Phi instr);
+ R visitReturn(Return instr);
+ R visitComparison(Comparison instr);
+ R visitConstant(Constant instr);
+ R visitDirectCall(DirectCall instr);
+ R visitInterfaceCall(InterfaceCall instr);
+ R visitDynamicCall(DynamicCall instr);
+ R visitParameter(Parameter instr);
+ R visitLoadLocal(LoadLocal instr);
+ R visitStoreLocal(StoreLocal instr);
+ R visitThrow(Throw instr);
+ R visitTypeParameters(TypeParameters instr);
+ R visitTypeCast(TypeCast instr);
+ R visitTypeTest(TypeTest instr);
+ R visitTypeArguments(TypeArguments instr);
+ R visitBinaryIntOp(BinaryIntOp instr);
+ R visitUnaryIntOp(UnaryIntOp instr);
+ R visitBinaryDoubleOp(BinaryDoubleOp instr);
+ R visitUnaryDoubleOp(UnaryDoubleOp instr);
+ // Back-end specific instructions.
+ R visitCompareAndBranch(CompareAndBranch instr);
+ R visitParallelMove(ParallelMove instr);
+}
+
+/// Visitor over [Instruction] which has an overridable default behavior for
+/// different categories of instructions.
+abstract mixin class DefaultInstructionVisitor<R>
+ implements InstructionVisitor<R> {
+ /// Default behavior for all instructions.
+ R defaultInstruction(Instruction instr);
+
+ /// Default behavior for basic blocks.
+ R defaultBlock(Block instr) => defaultInstruction(instr);
+
+ /// Default behavior for back-end specific instructions.
+ R defaultBackendInstruction(BackendInstruction instr) =>
+ defaultInstruction(instr);
+
+ // Basic blocks.
+ R visitEntryBlock(EntryBlock instr) => defaultBlock(instr);
+ R visitJoinBlock(JoinBlock instr) => defaultBlock(instr);
+ R visitTargetBlock(TargetBlock instr) => defaultBlock(instr);
+ R visitCatchBlock(CatchBlock instr) => defaultBlock(instr);
+ // Regular instructions.
+ R visitGoto(Goto instr) => defaultInstruction(instr);
+ R visitBranch(Branch instr) => defaultInstruction(instr);
+ R visitTryEntry(TryEntry instr) => defaultInstruction(instr);
+ R visitPhi(Phi instr) => defaultInstruction(instr);
+ R visitReturn(Return instr) => defaultInstruction(instr);
+ R visitComparison(Comparison instr) => defaultInstruction(instr);
+ R visitConstant(Constant instr) => defaultInstruction(instr);
+ R visitDirectCall(DirectCall instr) => defaultInstruction(instr);
+ R visitInterfaceCall(InterfaceCall instr) => defaultInstruction(instr);
+ R visitDynamicCall(DynamicCall instr) => defaultInstruction(instr);
+ R visitParameter(Parameter instr) => defaultInstruction(instr);
+ R visitLoadLocal(LoadLocal instr) => defaultInstruction(instr);
+ R visitStoreLocal(StoreLocal instr) => defaultInstruction(instr);
+ R visitThrow(Throw instr) => defaultInstruction(instr);
+ R visitTypeParameters(TypeParameters instr) => defaultInstruction(instr);
+ R visitTypeCast(TypeCast instr) => defaultInstruction(instr);
+ R visitTypeTest(TypeTest instr) => defaultInstruction(instr);
+ R visitTypeArguments(TypeArguments instr) => defaultInstruction(instr);
+ R visitBinaryIntOp(BinaryIntOp instr) => defaultInstruction(instr);
+ R visitUnaryIntOp(UnaryIntOp instr) => defaultInstruction(instr);
+ R visitBinaryDoubleOp(BinaryDoubleOp instr) => defaultInstruction(instr);
+ R visitUnaryDoubleOp(UnaryDoubleOp instr) => defaultInstruction(instr);
+ // Back-end specific instructions.
+ R visitCompareAndBranch(CompareAndBranch instr) =>
+ defaultBackendInstruction(instr);
+ R visitParallelMove(ParallelMove instr) => defaultBackendInstruction(instr);
+}
+
+/// Visitor over [Instruction] which does not yield a value.
+base class VoidInstructionVisitor extends DefaultInstructionVisitor<void> {
+ void defaultInstruction(Instruction instr) {}
+}
diff --git a/pkg/cfg/test/ir/constant_value_test.dart b/pkg/cfg/test/ir/constant_value_test.dart
new file mode 100644
index 0000000..41f238e
--- /dev/null
+++ b/pkg/cfg/test/ir/constant_value_test.dart
@@ -0,0 +1,512 @@
+// Copyright (c) 2025, 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:cfg/ir/constant_value.dart';
+import 'package:cfg/ir/global_context.dart';
+import 'package:cfg/ir/instructions.dart';
+import 'package:cfg/ir/types.dart';
+import 'package:kernel/ast.dart' as ast;
+import 'package:kernel/class_hierarchy.dart' show ClassHierarchy;
+import 'package:kernel/core_types.dart' show CoreTypes;
+import 'package:kernel/type_environment.dart';
+import 'package:test/test.dart';
+import '../test_helpers.dart';
+
+void main() {
+ final component = readVmPlatformKernelFile();
+ final coreTypes = CoreTypes(component);
+ final classHierarchy = ClassHierarchy(component, coreTypes);
+ final typeEnvironment = TypeEnvironment(coreTypes, classHierarchy);
+ final globalContext = GlobalContext(typeEnvironment: typeEnvironment);
+
+ group('constant values', () {
+ setUp(() {
+ GlobalContext.setCurrentContext(globalContext);
+ });
+
+ tearDown(() {
+ GlobalContext.setCurrentContext(null);
+ });
+
+ test('int', () {
+ final values = <int>[
+ 0x80000000_00000000,
+ 0x7fffffff_ffffffff,
+ -1,
+ 0,
+ 1,
+ 42,
+ -0xffffffff,
+ ];
+ for (final v in values) {
+ final cv = ConstantValue.fromInt(v);
+ expect(ConstantValue(ast.IntConstant(v)), equals(cv));
+ expect(cv.isInt, isTrue);
+ expect(cv.isDouble, isFalse);
+ expect(cv.isBool, isFalse);
+ expect(cv.isNull, isFalse);
+ expect(cv.isString, isFalse);
+ expect(cv.intValue, equals(v));
+ expect(cv.type is IntType, isTrue);
+ expect(cv.isZero, equals(v == 0));
+ expect(cv.isNegative, equals(v < 0));
+ expect(cv.valueToString(), equals(v.toString()));
+ }
+ });
+
+ test('double', () {
+ final values = <double>[
+ -1.0,
+ -0.0,
+ 0.0,
+ 1.0,
+ double.infinity,
+ double.negativeInfinity,
+ double.nan,
+ 1e100,
+ ];
+ for (final v in values) {
+ final cv = ConstantValue.fromDouble(v);
+ expect(ConstantValue(ast.DoubleConstant(v)), equals(cv));
+ expect(cv.isInt, isFalse);
+ expect(cv.isDouble, isTrue);
+ expect(cv.isBool, isFalse);
+ expect(cv.isNull, isFalse);
+ expect(cv.isString, isFalse);
+ expect(cv.doubleValue, same(v));
+ expect(cv.type is DoubleType, isTrue);
+ expect(cv.isZero, equals(v == 0.0));
+ expect(cv.isNegative, equals(v.isNegative));
+ expect(cv.valueToString(), equals(v.toString()));
+ }
+ });
+
+ test('bool', () {
+ final values = <bool>[true, false];
+ for (final v in values) {
+ final cv = ConstantValue.fromBool(v);
+ expect(ConstantValue(ast.BoolConstant(v)), equals(cv));
+ expect(cv.isInt, isFalse);
+ expect(cv.isDouble, isFalse);
+ expect(cv.isBool, isTrue);
+ expect(cv.isNull, isFalse);
+ expect(cv.isString, isFalse);
+ expect(cv.boolValue, equals(v));
+ expect(cv.type is BoolType, isTrue);
+ expect(cv.isZero, isFalse);
+ expect(cv.isNegative, isFalse);
+ expect(cv.valueToString(), equals(v.toString()));
+ }
+ });
+
+ test('null', () {
+ final cv = ConstantValue.fromNull();
+ expect(ConstantValue(ast.NullConstant()), equals(cv));
+ expect(cv.isInt, isFalse);
+ expect(cv.isDouble, isFalse);
+ expect(cv.isBool, isFalse);
+ expect(cv.isNull, isTrue);
+ expect(cv.isString, isFalse);
+ expect(cv.type is NullType, isTrue);
+ expect(cv.isZero, isFalse);
+ expect(cv.isNegative, isFalse);
+ expect(cv.valueToString(), equals(null.toString()));
+ });
+
+ test('string', () {
+ final values = <String>['', 'a', 'abcdef'];
+ for (final v in values) {
+ final cv = ConstantValue.fromString(v);
+ expect(ConstantValue(ast.StringConstant(v)), equals(cv));
+ expect(cv.isInt, isFalse);
+ expect(cv.isDouble, isFalse);
+ expect(cv.isBool, isFalse);
+ expect(cv.isNull, isFalse);
+ expect(cv.isString, isTrue);
+ expect(cv.stringValue, equals(v));
+ expect(cv.type is StringType, isTrue);
+ expect(cv.isZero, isFalse);
+ expect(cv.isNegative, isFalse);
+ expect(cv.valueToString(), equals('"$v"'));
+ }
+ });
+
+ test('type arguments', () {
+ final values = <List<ast.DartType>>[
+ [],
+ [coreTypes.stringNullableRawType],
+ [coreTypes.intNonNullableRawType, coreTypes.stringNonNullableRawType],
+ ];
+ for (final v in values) {
+ final cv = ConstantValue(TypeArgumentsConstant(v));
+ expect(ConstantValue(TypeArgumentsConstant(List.of(v))), equals(cv));
+ expect(cv.isInt, isFalse);
+ expect(cv.isDouble, isFalse);
+ expect(cv.isBool, isFalse);
+ expect(cv.isNull, isFalse);
+ expect(cv.isString, isFalse);
+ expect(cv.type is TypeArgumentsType, isTrue);
+ expect(cv.isZero, isFalse);
+ expect(cv.isNegative, isFalse);
+ }
+ });
+ });
+
+ group('constant folding', () {
+ final constantFolding = const ConstantFolding();
+
+ setUp(() {
+ GlobalContext.setCurrentContext(globalContext);
+ });
+
+ tearDown(() {
+ GlobalContext.setCurrentContext(null);
+ });
+
+ test('comparison - equal', () {
+ void eq(ConstantValue left, ConstantValue right) {
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.equal, left, right)
+ .boolValue,
+ isTrue,
+ );
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.notEqual, left, right)
+ .boolValue,
+ isFalse,
+ );
+ }
+
+ void ne(ConstantValue left, ConstantValue right) {
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.equal, left, right)
+ .boolValue,
+ isFalse,
+ );
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.notEqual, left, right)
+ .boolValue,
+ isTrue,
+ );
+ }
+
+ eq(ConstantValue.fromString('a'), ConstantValue.fromString('a'));
+ ne(ConstantValue.fromString('a'), ConstantValue.fromString('b'));
+ eq(ConstantValue.fromInt(42), ConstantValue.fromInt(42));
+ ne(ConstantValue.fromInt(42), ConstantValue.fromInt(43));
+ ne(ConstantValue.fromInt(0), ConstantValue.fromDouble(0.0));
+ eq(
+ ConstantValue.fromDouble(double.nan),
+ ConstantValue.fromDouble(double.nan),
+ );
+ ne(ConstantValue.fromDouble(0.0), ConstantValue.fromDouble(-0.0));
+ });
+
+ test('comparison - identical', () {
+ void eq(ConstantValue left, ConstantValue right) {
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.identical, left, right)
+ .boolValue,
+ isTrue,
+ );
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.notIdentical, left, right)
+ .boolValue,
+ isFalse,
+ );
+ }
+
+ void ne(ConstantValue left, ConstantValue right) {
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.identical, left, right)
+ .boolValue,
+ isFalse,
+ );
+ expect(
+ constantFolding
+ .comparison(ComparisonOpcode.notIdentical, left, right)
+ .boolValue,
+ isTrue,
+ );
+ }
+
+ eq(ConstantValue.fromString('a'), ConstantValue.fromString('a'));
+ ne(ConstantValue.fromString('a'), ConstantValue.fromString('b'));
+ eq(ConstantValue.fromInt(42), ConstantValue.fromInt(42));
+ ne(ConstantValue.fromInt(42), ConstantValue.fromInt(43));
+ ne(ConstantValue.fromInt(0), ConstantValue.fromDouble(0.0));
+ eq(
+ ConstantValue.fromDouble(double.nan),
+ ConstantValue.fromDouble(double.nan),
+ );
+ ne(ConstantValue.fromDouble(0.0), ConstantValue.fromDouble(-0.0));
+ });
+
+ test('comparison - int', () {
+ final values = <(int, int)>[
+ (0, 1),
+ (1, 0),
+ (42, 6),
+ (10, -5),
+ (-3, 1),
+ (0x80000000_00000000, -1),
+ (-10, 0x7fffffff_ffffffff),
+ ];
+
+ void testOp(
+ ComparisonOpcode opcode,
+ bool Function(int, int) expectedBehavior,
+ ) {
+ for (final pair in values) {
+ expect(
+ constantFolding
+ .comparison(
+ opcode,
+ ConstantValue.fromInt(pair.$1),
+ ConstantValue.fromInt(pair.$2),
+ )
+ .boolValue,
+ equals(expectedBehavior(pair.$1, pair.$2)),
+ );
+ }
+ }
+
+ testOp(ComparisonOpcode.intEqual, (int a, int b) => a == b);
+ testOp(ComparisonOpcode.intNotEqual, (int a, int b) => a != b);
+ testOp(ComparisonOpcode.intLess, (int a, int b) => a < b);
+ testOp(ComparisonOpcode.intLessOrEqual, (int a, int b) => a <= b);
+ testOp(ComparisonOpcode.intGreater, (int a, int b) => a > b);
+ testOp(ComparisonOpcode.intGreaterOrEqual, (int a, int b) => a >= b);
+ });
+
+ test('comparison - double', () {
+ final values = <(double, double)>[
+ (1.0, 1.0),
+ (1.0, -1.0),
+ (0.0, -0.0),
+ (42.0, double.infinity),
+ (double.negativeInfinity, -1e100),
+ (1.0, double.nan),
+ (double.nan, double.nan),
+ ];
+
+ void testOp(
+ ComparisonOpcode opcode,
+ bool Function(double, double) expectedBehavior,
+ ) {
+ for (final pair in values) {
+ expect(
+ constantFolding
+ .comparison(
+ opcode,
+ ConstantValue.fromDouble(pair.$1),
+ ConstantValue.fromDouble(pair.$2),
+ )
+ .boolValue,
+ equals(expectedBehavior(pair.$1, pair.$2)),
+ );
+ }
+ }
+
+ testOp(ComparisonOpcode.doubleEqual, (double a, double b) => a == b);
+ testOp(ComparisonOpcode.doubleNotEqual, (double a, double b) => a != b);
+ testOp(ComparisonOpcode.doubleLess, (double a, double b) => a < b);
+ testOp(
+ ComparisonOpcode.doubleLessOrEqual,
+ (double a, double b) => a <= b,
+ );
+ testOp(ComparisonOpcode.doubleGreater, (double a, double b) => a > b);
+ testOp(
+ ComparisonOpcode.doubleGreaterOrEqual,
+ (double a, double b) => a >= b,
+ );
+ });
+
+ test('binary int op', () {
+ final values = <(int, int)>[
+ (0, 1),
+ (1, 0),
+ (42, 6),
+ (10, -5),
+ (-3, 1),
+ (0x80000000_00000000, -1),
+ (-10, 0x7fffffff_ffffffff),
+ ];
+
+ void testOp(
+ BinaryIntOpcode opcode,
+ int Function(int, int) expectedBehavior,
+ ) {
+ for (final pair in values) {
+ ConstantValue? expected;
+ try {
+ expected = ConstantValue.fromInt(
+ expectedBehavior(pair.$1, pair.$2),
+ );
+ } on Error {
+ // Ignore runtime errors.
+ }
+ expect(
+ constantFolding.binaryIntOp(
+ opcode,
+ ConstantValue.fromInt(pair.$1),
+ ConstantValue.fromInt(pair.$2),
+ ),
+ equals(expected),
+ );
+ }
+ }
+
+ testOp(BinaryIntOpcode.add, (int a, int b) => a + b);
+ testOp(BinaryIntOpcode.sub, (int a, int b) => a - b);
+ testOp(BinaryIntOpcode.mul, (int a, int b) => a * b);
+ testOp(BinaryIntOpcode.truncatingDiv, (int a, int b) => a ~/ b);
+ testOp(BinaryIntOpcode.mod, (int a, int b) => a % b);
+ testOp(BinaryIntOpcode.rem, (int a, int b) => a.remainder(b));
+ testOp(BinaryIntOpcode.bitOr, (int a, int b) => a | b);
+ testOp(BinaryIntOpcode.bitAnd, (int a, int b) => a & b);
+ testOp(BinaryIntOpcode.bitXor, (int a, int b) => a ^ b);
+ testOp(BinaryIntOpcode.shiftLeft, (int a, int b) => a << b);
+ testOp(BinaryIntOpcode.shiftRight, (int a, int b) => a >> b);
+ testOp(BinaryIntOpcode.unsignedShiftRight, (int a, int b) => a >>> b);
+ });
+
+ test('unary int op', () {
+ final values = <int>[
+ 0,
+ 1,
+ -1,
+ 42,
+ -123,
+ 0x80000000_00000000,
+ 0x7fffffff_ffffffff,
+ ];
+
+ void testOp(UnaryIntOpcode opcode, num Function(int) expectedBehavior) {
+ for (final v in values) {
+ final expected = expectedBehavior(v);
+ final expectedConstValue = switch (expected) {
+ double() => ConstantValue.fromDouble(expected),
+ int() => ConstantValue.fromInt(expected),
+ };
+ expect(
+ constantFolding.unaryIntOp(opcode, ConstantValue.fromInt(v)),
+ equals(expectedConstValue),
+ );
+ }
+ }
+
+ testOp(UnaryIntOpcode.neg, (int v) => -v);
+ testOp(UnaryIntOpcode.bitNot, (int v) => ~v);
+ testOp(UnaryIntOpcode.toDouble, (int v) => v.toDouble());
+ testOp(UnaryIntOpcode.abs, (int v) => v.abs());
+ testOp(UnaryIntOpcode.sign, (int v) => v.sign);
+ });
+
+ test('binary double op', () {
+ final values = <(double, double)>[
+ (1.0, 1.0),
+ (1.0, -1.0),
+ (0.0, -0.0),
+ (42.0, double.infinity),
+ (double.negativeInfinity, -1e100),
+ (1.0, double.nan),
+ (double.nan, double.nan),
+ ];
+
+ void testOp(
+ BinaryDoubleOpcode opcode,
+ num Function(double, double) expectedBehavior,
+ ) {
+ for (final pair in values) {
+ ConstantValue? expectedConstValue;
+ try {
+ final expected = expectedBehavior(pair.$1, pair.$2);
+ expectedConstValue = switch (expected) {
+ double() => ConstantValue.fromDouble(expected),
+ int() => ConstantValue.fromInt(expected),
+ };
+ } on Error {
+ // Ignore runtime errors.
+ }
+ expect(
+ constantFolding.binaryDoubleOp(
+ opcode,
+ ConstantValue.fromDouble(pair.$1),
+ ConstantValue.fromDouble(pair.$2),
+ ),
+ equals(expectedConstValue),
+ );
+ }
+ }
+
+ testOp(BinaryDoubleOpcode.add, (double a, double b) => a + b);
+ testOp(BinaryDoubleOpcode.sub, (double a, double b) => a - b);
+ testOp(BinaryDoubleOpcode.mul, (double a, double b) => a * b);
+ testOp(BinaryDoubleOpcode.mod, (double a, double b) => a % b);
+ testOp(BinaryDoubleOpcode.rem, (double a, double b) => a.remainder(b));
+ testOp(BinaryDoubleOpcode.div, (double a, double b) => a / b);
+ testOp(BinaryDoubleOpcode.truncatingDiv, (double a, double b) => a ~/ b);
+ });
+
+ test('unary double op', () {
+ final values = <double>[
+ 1.0,
+ -1.0,
+ 0.0,
+ -0.0,
+ 42.0,
+ -1e100,
+ double.infinity,
+ double.negativeInfinity,
+ double.nan,
+ ];
+
+ void testOp(
+ UnaryDoubleOpcode opcode,
+ num Function(double) expectedBehavior,
+ ) {
+ for (final v in values) {
+ ConstantValue? expectedConstValue;
+ try {
+ final expected = expectedBehavior(v);
+ expectedConstValue = switch (expected) {
+ double() => ConstantValue.fromDouble(expected),
+ int() => ConstantValue.fromInt(expected),
+ };
+ } on Error {
+ // Ignore runtime errors.
+ }
+ expect(
+ constantFolding.unaryDoubleOp(opcode, ConstantValue.fromDouble(v)),
+ equals(expectedConstValue),
+ );
+ }
+ }
+
+ testOp(UnaryDoubleOpcode.neg, (double v) => -v);
+ testOp(UnaryDoubleOpcode.abs, (double v) => v.abs());
+ testOp(UnaryDoubleOpcode.sign, (double v) => v.sign);
+ testOp(UnaryDoubleOpcode.square, (double v) => v * v);
+ testOp(UnaryDoubleOpcode.round, (double v) => v.round());
+ testOp(UnaryDoubleOpcode.floor, (double v) => v.floor());
+ testOp(UnaryDoubleOpcode.ceil, (double v) => v.ceil());
+ testOp(UnaryDoubleOpcode.truncate, (double v) => v.truncate());
+ testOp(UnaryDoubleOpcode.roundToDouble, (double v) => v.roundToDouble());
+ testOp(UnaryDoubleOpcode.floorToDouble, (double v) => v.floorToDouble());
+ testOp(UnaryDoubleOpcode.ceilToDouble, (double v) => v.ceilToDouble());
+ testOp(
+ UnaryDoubleOpcode.truncateToDouble,
+ (double v) => v.truncateToDouble(),
+ );
+ });
+ });
+}
