dart / sdk.git / 294a9c6c4194ae7049aa177c3b8a6bb27e06c206 / . / pkg / kernel / lib / type_propagation / constraints.dart

// Copyright (c) 2016, 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. | |

library kernel.type_propagation.constraints; | |

import 'canonicalizer.dart'; | |

/// A system of constraints representing dataflow in a Dart program. | |

/// | |

/// The system consists of variables, values, and lattice points, as well as | |

/// constraints that express the relationships between these. | |

/// | |

/// Internally, variables, values, and lattice points are represented as | |

/// integers starting at 0. The namespaces for these are overlapping; there is | |

/// no runtime tag to distinguish variables from values from lattice points, so | |

/// great care must be taken not to mix them up. | |

/// | |

/// Externally, the methods on [ConstraintSystem] apply a layer of sanity checks | |

/// using the sign bit to distinguish values from variables and lattice points. | |

/// Users should therefore access the constraint system using either its methods | |

/// or its fields, but not both. | |

/// | |

/// The constraint system has the traditional Andersen-style constraints: | |

/// | |

/// Allocate: `x = value` | |

/// Assign: `x = y` | |

/// Store: `x.f = y` | |

/// Load: `x = y.f` | |

/// | |

/// Additionally, there is a "sink" constraint which acts as an assignment but | |

/// only after the fixed-point has been found. | |

/// | |

/// Lattice points represent sets of values. All values must belong to one | |

/// particular lattice point and are implicitly contained in the value set of | |

/// all lattice points above it. | |

/// | |

/// A solution to the constraint system is an assignment from each variable to | |

/// a lattice point containing all values that may flow into the variable. | |

class ConstraintSystem { | |

int _numberOfVariables = 0; | |

final List<int> assignments = <int>[]; | |

final List<int> sinks = <int>[]; | |

final List<int> loads = <int>[]; | |

final List<int> stores = <int>[]; | |

final List<int> allocations = <int>[]; | |

final List<int> latticePointOfValue = <int>[]; | |

final Uint31PairMap<int> storeLocations = new Uint31PairMap<int>(); | |

final Uint31PairMap<int> loadLocations = new Uint31PairMap<int>(); | |

/// The same as [storeLocations], for traversal instead of fast lookup. | |

final List<int> storeLocationList = <int>[]; | |

/// The same as [loadLocations], for traversal instead of fast lookup. | |

final List<int> loadLocationList = <int>[]; | |

final List<List<int>> parentsOfLatticePoint = <List<int>>[]; | |

final List<int> bitmaskInputs = <int>[]; | |

int get numberOfVariables => _numberOfVariables; | |

int get numberOfValues => latticePointOfValue.length; | |

int get numberOfLatticePoints => parentsOfLatticePoint.length; | |

int newVariable() { | |

return _numberOfVariables++; | |

} | |

/// Creates a new lattice point, initially representing or containing no | |

/// values. | |

/// | |

/// Values can be added to the lattice point passing it to [newValue] or by | |

/// creating lattice points below it and adding values to those. | |

/// | |

/// The first lattice point created must be an ancestor of all lattice points. | |

int newLatticePoint(List<int> supers) { | |

assert(supers != null); | |

int id = parentsOfLatticePoint.length; | |

parentsOfLatticePoint.add(supers); | |

return id; | |

} | |

/// Creates a new value as a member of the given [latticePoint], with the | |

/// given mutable fields. | |

/// | |

/// The lattice point should be specific to this value or the solver will not | |

/// be able to distinguish it from other values in the same lattice point. | |

/// | |

/// To help debugging, this method returns the the negated ID for the value. | |

/// Every method on the constraint system checks that arguments representing | |

/// values are non-positive in order to catch accidental bugs where a | |

/// variable or lattice point was accidentally used in place of a value. | |

int newValue(int latticePoint) { | |

assert(0 <= latticePoint && latticePoint < numberOfLatticePoints); | |

int valueId = latticePointOfValue.length; | |

latticePointOfValue.add(latticePoint); | |

return -valueId; | |

} | |

/// Sets [variable] as the storage location for values dynamically stored | |

/// into [field] on [value]. | |

/// | |

/// Any store constraint where [value] can reach the receiver will propagate | |

/// the stored value into [variable]. | |

void setStoreLocation(int value, int field, int variable) { | |

assert(value <= 0); | |

assert(field >= 0); | |

assert(variable >= 0); | |

value = -value; | |

int location = storeLocations.lookup(value, field); | |

assert(location == null); | |

storeLocations.put(variable); | |

storeLocationList..add(value)..add(field)..add(variable); | |

} | |

/// Sets [variable] as the storage location for values dynamically loaded | |

/// from [field] on [value]. | |

/// | |

/// Any load constraint where [value] can reach the receiver object will | |

/// propagate the value from [variable] into the result of the load. | |

void setLoadLocation(int value, int field, int variable) { | |

assert(value <= 0); | |

assert(field >= 0); | |

assert(variable >= 0); | |

value = -value; | |

int location = loadLocations.lookup(value, field); | |

assert(location == null); | |

loadLocations.put(variable); | |

loadLocationList..add(value)..add(field)..add(variable); | |

} | |

void addAllocation(int value, int destination) { | |

assert(value <= 0); | |

assert(destination >= 0); | |

value = -value; | |

allocations..add(value)..add(destination); | |

} | |

void addBitmaskInput(int bitmask, int destination) { | |

bitmaskInputs..add(bitmask)..add(destination); | |

} | |

void addAssign(int source, int destination) { | |

assert(source >= 0); | |

assert(destination >= 0); | |

assignments..add(source)..add(destination); | |

} | |

void addLoad(int object, int field, int destination) { | |

assert(object >= 0); | |

assert(field >= 0); | |

assert(destination >= 0); | |

loads..add(object)..add(field)..add(destination); | |

} | |

void addStore(int object, int field, int source) { | |

assert(object >= 0); | |

assert(field >= 0); | |

assert(source >= 0); | |

stores..add(object)..add(field)..add(source); | |

} | |

/// Like an assignment from [source] to [sink], but is only propagated once | |

/// after the fixed-point has been found. | |

/// | |

/// This is for storing the results of the analysis in the [sink] variable | |

/// without intefering with the solver's escape analysis. | |

void addSink(int source, int sink) { | |

assert(source >= 0); | |

assert(sink >= 0); | |

sinks..add(source)..add(sink); | |

} | |

int get numberOfAllocations => allocations.length ~/ 2; | |

int get numberOfAssignments => assignments.length ~/ 2; | |

int get numberOfLoads => loads.length ~/ 3; | |

int get numberOfStores => stores.length ~/ 3; | |

} |