pkg/compiler/lib/src/cps_ir/gvn.dart - Issue 2246623002: Delete CPS IR

Unified Diff: pkg/compiler/lib/src/cps_ir/gvn.dart

Issue 2246623002: Delete CPS IR (Closed) Base URL: git@github.com:dart-lang/sdk.git@master

Patch Set: Created 4 years, 4 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: pkg/compiler/lib/src/cps_ir/gvn.dart

diff --git a/pkg/compiler/lib/src/cps_ir/gvn.dart b/pkg/compiler/lib/src/cps_ir/gvn.dart

deleted file mode 100644

index 4c49d7ab4a433b607b0343f1a24367f36404c916..0000000000000000000000000000000000000000

--- a/pkg/compiler/lib/src/cps_ir/gvn.dart

+++ /dev/null

@@ -1,618 +0,0 @@

-// BSD-style license that can be found in the LICENSE file.

-library dart2js.cps_ir.gvn;

-import '../compiler.dart' show Compiler;

-import '../elements/elements.dart';

-import '../js_backend/js_backend.dart' show JavaScriptBackend;

-import '../world.dart';

-import 'cps_ir_nodes.dart';

-import 'effects.dart';

-import 'loop_effects.dart';

-import 'loop_hierarchy.dart';

-import 'optimizers.dart' show Pass;

-import 'type_mask_system.dart';

-/// Eliminates redundant primitives by reusing the value of another primitive

-/// that is known to have the same result. Primitives are also hoisted out of

-/// loops when possible.

-///

-/// Reusing values can introduce new temporaries, which in some cases is more

-/// expensive than recomputing the value on-demand. For example, pulling an

-/// expression such as "n+1" out of a loop is generally not worth it.

-/// Such primitives are said to be "trivial".

-///

-/// Trivial primitives are shared on-demand, i.e. they are only shared if

-/// this enables a non-trivial primitive to be hoisted out of a loop.

-//

-// TODO(asgerf): Enable hoisting across refinement guards when this is safe:

-// - Determine the type required for a given primitive to be "safe"

-// - Recompute the type of a primitive after hoisting.

-// E.g. GetIndex on a String can become a GetIndex on an arbitrary

-// indexable, which is still safe but the type may change

-// - Since the new type may be worse, insert a refinement at the old

-// definition site, so we do not degrade existing type information.

-//

-class GVN extends TrampolineRecursiveVisitor implements Pass {

- String get passName => 'GVN';

- final Compiler compiler;

- final TypeMaskSystem types;

- JavaScriptBackend get backend => compiler.backend;

- World get world => compiler.world;

- final GvnTable gvnTable = new GvnTable();

- GvnVectorBuilder gvnVectorBuilder;

- LoopHierarchy loopHierarchy;

- LoopSideEffects loopEffects;

- final EffectNumberer effectNumberer = new EffectNumberer();

- /// Effect numbers at the given join point.

- Map<Continuation, EffectNumbers> effectsAt = <Continuation, EffectNumbers>{};

- /// The effect numbers at the current position (during traversal).

- EffectNumbers effectNumbers;

- /// The loop currently enclosing the binding of a given primitive.

- final Map<Primitive, Continuation> loopHeaderFor =

- <Primitive, Continuation>{};

- /// The GVNs for primitives that have been hoisted outside the given loop.

- ///

- /// These should be removed from the environment when exiting the loop.

- final Map<Continuation, List<int>> loopHoistedBindings =

- <Continuation, List<int>>{};

- /// Maps GVNs to a currently-in-scope binding for that value.

- final Map<int, Primitive> environment = <int, Primitive>{};

- /// Maps GVN'able primitives to their global value number.

- final Map<Primitive, int> gvnFor = <Primitive, int>{};

- Continuation currentLoopHeader;

- GVN(this.compiler, this.types);

- void rewrite(FunctionDefinition node) {

- effectNumbers = new EffectNumbers.fresh(effectNumberer);

- gvnVectorBuilder = new GvnVectorBuilder(gvnFor, compiler, types);

- loopHierarchy = new LoopHierarchy(node);

- loopEffects =

- new LoopSideEffects(node, world, loopHierarchy: loopHierarchy);

- visit(node);

- }

- // ------------------ GLOBAL VALUE NUMBERING ---------------------

- /// True if [prim] can be eliminated if its value is already in scope.

- bool canReplaceWithExistingValue(Primitive prim) {

- // Primitives that have no side effects other than potentially throwing are

- // known not the throw if the value is already in scope. Handling those

- // specially is equivalent to updating refinements during GVN.

- // GetLazyStatic cannot have side effects because the field has already

- // been initialized.

- return prim.isSafeForElimination ||

- prim is GetField ||

- prim is GetLength ||

- prim is GetIndex ||

- prim is GetLazyStatic;

- }

- @override

- Expression traverseLetPrim(LetPrim node) {

- Expression next = node.body;

- Primitive prim = node.primitive;

- loopHeaderFor[prim] = currentLoopHeader;

- if (prim is Refinement) {

- // Do not share refinements (they have no runtime or code size cost), and

- // do not put them in the GVN table because GvnVectorBuilder unfolds

- // refinements by itself.

- return next;

- }

- // Update effect numbers due to side effects from a static initializer.

- // GetLazyStatic is GVN'ed like a GetStatic, but the effects of the static

- // initializer occur before reading the field.

- if (prim is GetLazyStatic) {

- addSideEffectsOfPrimitive(prim);

- }

- // Compute the GVN vector for this computation.

- List vector = gvnVectorBuilder.make(prim, effectNumbers);

- // Update effect numbers due to side effects.

- // Do this after computing the GVN vector so the primitive's GVN is not

- // influenced by its own side effects, except in the case of GetLazyStatic.

- if (prim is! GetLazyStatic) {

- addSideEffectsOfPrimitive(prim);

- }

- if (vector == null) {

- // The primitive is not GVN'able. Move on.

- return next;

- }

- // Compute the GVN for this primitive.

- int gvn = gvnTable.insert(vector);

- gvnFor[prim] = gvn;

- // Try to reuse a previously computed value with the same GVN.

- Primitive existing = environment[gvn];

- if (existing != null &&

- canReplaceWithExistingValue(prim) &&

- !isFastConstant(prim)) {

- if (prim is Interceptor) {

- Interceptor interceptor = existing;

- interceptor.interceptedClasses.addAll(prim.interceptedClasses);

- }

- prim

- ..replaceUsesWith(existing)

- ..destroy();

- node.remove();

- return next;

- }

- if (tryToHoistOutOfLoop(prim, gvn)) {

- return next;

- }

- // The primitive could not be hoisted. Put the primitive in the

- // environment while processing the body of the LetPrim.

- environment[gvn] = prim;

- pushAction(() {

- assert(environment[gvn] == prim);

- environment[gvn] = existing;

- });

- return next;

- }

- bool isFirstImpureExpressionInLoop(Expression exp) {

- InteriorNode node = exp.parent;

- for (; node is Expression; node = node.parent) {

- if (node is LetPrim && node.primitive.isSafeForElimination) {

- continue;

- }

- if (node is LetCont) {

- continue;

- }

- return false;

- }

- return node == currentLoopHeader;

- }

- bool isHoistablePrimitive(Primitive prim) {

- if (prim.isSafeForElimination) return true;

- if (prim is ReceiverCheck ||

- prim is BoundsCheck ||

- prim is GetLength ||

- prim is GetField ||

- prim is GetIndex) {

- // Expressions that potentially throw but have no other effects can be

- // hoisted if they occur as the first impure expression in a loop.

- // Note regarding BoundsCheck: the current array length is an input to

- // check, so the check itself has no heap dependency. It will only be

- // hoisted if the length was hoisted.

- // TODO(asgerf): In general we could hoist these out of multiple loops,

- // but the trick we use here only works for one loop level.

- return isFirstImpureExpressionInLoop(prim.parent);

- }

- return false;

- }

- /// Try to hoist the binding of [prim] out of loops. Returns `true` if it was

- /// hoisted or marked as a trivial hoist-on-demand primitive.

- bool tryToHoistOutOfLoop(Primitive prim, int gvn) {

- // Bail out fast if the primitive is not inside a loop.

- if (currentLoopHeader == null) return false;

- // Do not hoist primitives with side effects.

- if (!isHoistablePrimitive(prim)) return false;

- LetPrim letPrim = prim.parent;

- // Find the depth of the outermost scope where we can bind the primitive

- // without bringing a reference out of scope. 0 is the depth of the

- // top-level scope.

- int hoistDepth = 0;

- List<Primitive> inputsHoistedOnDemand = <Primitive>[];

- InputVisitor.forEach(prim, (Reference ref) {

- Primitive input = ref.definition;

- if (canIgnoreRefinementGuards(prim)) {

- input = input.effectiveDefinition;

- }

- if (isFastConstant(input)) {

- // Fast constants can be hoisted all the way out, but should only be

- // hoisted if needed to hoist something else.

- inputsHoistedOnDemand.add(input);

- } else {

- Continuation loopHeader = loopHeaderFor[input];

- Continuation referencedLoop =

- loopHierarchy.lowestCommonAncestor(loopHeader, currentLoopHeader);

- int depth = loopHierarchy.getDepth(referencedLoop);

- if (depth > hoistDepth) {

- hoistDepth = depth;

- }

- });

- // Bail out if it can not be hoisted further out than it is now.

- if (hoistDepth == loopHierarchy.getDepth(currentLoopHeader)) return false;

- // Walk up the loop hierarchy and check at every step that any heap

- // dependencies can safely be hoisted out of the loop.

- Continuation enclosingLoop = currentLoopHeader;

- Continuation hoistTarget = null;

- while (loopHierarchy.getDepth(enclosingLoop) > hoistDepth &&

- canHoistHeapDependencyOutOfLoop(prim, enclosingLoop)) {

- hoistTarget = enclosingLoop;

- enclosingLoop = loopHierarchy.getEnclosingLoop(enclosingLoop);

- }

- // Bail out if heap dependencies prohibit any hoisting at all.

- if (hoistTarget == null) return false;

- if (isFastConstant(prim)) {

- // The overhead from introducting a temporary might be greater than

- // the overhead of evaluating this primitive at every iteration.

- // Only hoist if this enables hoisting of a non-trivial primitive.

- return true;

- }

- LetCont loopBinding = hoistTarget.parent;

- // The primitive may depend on values that have not yet been

- // hoisted as far as they can. Hoist those now.

- for (Primitive input in inputsHoistedOnDemand) {

- hoistTrivialPrimitive(input, loopBinding, enclosingLoop);

- }

- // Hoist the primitive.

- letPrim.remove();

- letPrim.insertAbove(loopBinding);

- loopHeaderFor[prim] = enclosingLoop;

- // If a refinement guard was bypassed, use the best refinement

- // currently in scope.

- if (canIgnoreRefinementGuards(prim)) {

- int target = loopHierarchy.getDepth(enclosingLoop);

- InputVisitor.forEach(prim, (Reference ref) {

- Primitive input = ref.definition;

- while (input is Refinement) {

- Continuation loop = loopHeaderFor[input];

- loop = loopHierarchy.lowestCommonAncestor(loop, currentLoopHeader);

- if (loopHierarchy.getDepth(loop) <= target) break;

- Refinement refinement = input;

- input = refinement.value.definition;

- }

- ref.changeTo(input);

- });

- }

- // Put the primitive in the environment while processing the loop.

- environment[gvn] = prim;

- loopHoistedBindings.putIfAbsent(hoistTarget, () => <int>[]).add(gvn);

- return true;

- }

- /// If the given primitive is a trivial primitive that should be hoisted

- /// on-demand, hoist it and its dependent values above [loopBinding].

- void hoistTrivialPrimitive(

- Primitive prim, LetCont loopBinding, Continuation enclosingLoop) {

- assert(isFastConstant(prim));

- // The primitive might already be bound in an outer scope. Do not relocate

- // the primitive unless we are lifting it. For example;

- // t1 = a + b

- // t2 = t1 + c

- // t3 = t1 * t2

- // If it was decided that `t3` should be hoisted, `t1` will be seen twice by

- // this method: by the direct reference and by reference through `t2`.

- // The second time it is seen, it will already have been moved.

- Continuation currentLoop = loopHeaderFor[prim];

- int currentDepth = loopHierarchy.getDepth(currentLoop);

- int targetDepth = loopHierarchy.getDepth(enclosingLoop);

- if (currentDepth <= targetDepth) return;

- // Hoist the trivial primitives being depended on so they remain in scope.

- InputVisitor.forEach(prim, (Reference ref) {

- hoistTrivialPrimitive(ref.definition, loopBinding, enclosingLoop);

- });

- // Move the primitive.

- LetPrim binding = prim.parent;

- binding.remove();

- binding.insertAbove(loopBinding);

- loopHeaderFor[prim] = enclosingLoop;

- }

- bool canIgnoreRefinementGuards(Primitive primitive) {

- return primitive is Interceptor;

- }

- /// Returns true if [prim] is a constant that has no significant runtime cost.

- bool isFastConstant(Primitive prim) {

- return prim is Constant && (prim.value.isPrimitive || prim.value.isDummy);

- }

- /// Assuming [prim] has no side effects, returns true if it can safely

- /// be hoisted out of [loop] without changing its value or changing the timing

- /// of a thrown exception.

- bool canHoistHeapDependencyOutOfLoop(Primitive prim, Continuation loop) {

- // If the primitive might throw, we have to check that it is the first

- // impure expression in the loop. This has already been checked if

- // [loop] is the current loop header, but for other loops we just give up.

- if (!prim.isSafeForElimination && loop != currentLoopHeader) {

- return false;

- }

- int effects = loopEffects.getSideEffectsInLoop(loop);

- return Effects.changesToDepends(effects) & prim.effects == 0;

- }

- // ------------------ TRAVERSAL AND EFFECT NUMBERING ---------------------

- //

- // These methods traverse the IR while updating the current effect numbers.

- // They are not specific to GVN.

- void addSideEffectsOfPrimitive(Primitive prim) {

- addSideEffects(prim.effects);

- }

- void addSideEffects(int effectFlags) {

- effectNumbers.change(effectNumberer, effectFlags);

- }

- Expression traverseLetHandler(LetHandler node) {

- // Assume any kind of side effects may occur in the try block.

- effectsAt[node.handler] = new EffectNumbers.fresh(effectNumberer);

- push(node.handler);

- return node.body;

- }

- Expression traverseContinuation(Continuation cont) {

- Continuation oldLoopHeader = currentLoopHeader;

- currentLoopHeader = loopHierarchy.getLoopHeader(cont);

- pushAction(() {

- currentLoopHeader = oldLoopHeader;

- });

- for (Parameter param in cont.parameters) {

- loopHeaderFor[param] = currentLoopHeader;

- }

- if (cont.isRecursive) {

- addSideEffects(loopEffects.getSideEffectsInLoop(cont));

- pushAction(() {

- List<int> hoistedBindings = loopHoistedBindings[cont];

- if (hoistedBindings != null) {

- hoistedBindings.forEach(environment.remove);

- }

- });

- } else {

- effectNumbers = effectsAt[cont];

- assert(effectNumbers != null);

- }

- return cont.body;

- }

- void visitInvokeContinuation(InvokeContinuation node) {

- Continuation cont = node.continuation;

- if (cont.isRecursive) return;

- EffectNumbers join = effectsAt[cont];

- if (join == null) {

- effectsAt[cont] = effectNumbers.copy();

- } else {

- join.join(effectNumberer, effectNumbers);

- }

- void visitBranch(Branch node) {

- Continuation trueCont = node.trueContinuation;

- Continuation falseCont = node.falseContinuation;

- // Copy the effect number vector once, so the analysis of one branch does

- // not influence the other.

- effectsAt[trueCont] = effectNumbers;

- effectsAt[falseCont] = effectNumbers.copy();

- }

-/// Maps vectors to numbers, such that two vectors with the same contents

-/// map to the same number.

-class GvnTable {

- Map<GvnEntry, int> _table = <GvnEntry, int>{};

- int _usedGvns = 0;

- int _makeNewGvn() => ++_usedGvns;

- int insert(List vector) {

- return _table.putIfAbsent(new GvnEntry(vector), _makeNewGvn);

- }

-/// Wrapper around a [List] that compares for equality based on contents

-/// instead of object identity.

-class GvnEntry {

- final List vector;

- final int hashCode;

- GvnEntry(List vector)

- : vector = vector,

- hashCode = computeHashCode(vector);

- bool operator ==(other) {

- if (other is! GvnEntry) return false;

- GvnEntry entry = other;

- List otherVector = entry.vector;

- if (vector.length != otherVector.length) return false;

- for (int i = 0; i < vector.length; ++i) {

- if (vector[i] != otherVector[i]) return false;

- }

- return true;

- }

- /// Combines the hash codes of [vector] using Jenkin's hash function, with

- /// intermediate results truncated to SMI range.

- static int computeHashCode(List vector) {

- int hash = 0;

- for (int i = 0; i < vector.length; ++i) {

- hash = 0x1fffffff & (hash + vector[i].hashCode);

- hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));

- hash = hash ^ (hash >> 6);

- }

- hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3));

- hash = hash ^ (hash >> 11);

- return 0x1fffffff & (hash + ((0x00003fff & hash) << 15));

- }

-/// Converts GVN'able primitives to a vector containing all the values

-/// to be considered when computing a GVN for it.

-///

-/// This includes the instruction type, inputs, effect numbers for any part

-/// of the heap being depended on, as well as any instruction-specific payload

-/// such as any DartTypes, Elements, and operator kinds.

-///

-/// Each `visit` or `process` method for a primitive must initialize [vector]

-/// if the primitive is GVN'able and fill in any components except the inputs.

-/// The inputs will be filled in by [processReference].

-class GvnVectorBuilder extends DeepRecursiveVisitor {

- List vector;

- final Map<Primitive, int> gvnFor;

- final Compiler compiler;

- World get world => compiler.world;

- JavaScriptBackend get backend => compiler.backend;

- final TypeMaskSystem types;

- EffectNumbers effectNumbers;

- GvnVectorBuilder(this.gvnFor, this.compiler, this.types);

- List make(Primitive prim, EffectNumbers effectNumbers) {

- this.effectNumbers = effectNumbers;

- vector = null;

- visit(prim);

- return vector;

- }

- /// The `process` methods below do not insert the referenced arguments into

- /// the vector, but instead rely on them being inserted here.

- processReference(Reference ref) {

- if (vector == null) return;

- Primitive prim = ref.definition.effectiveDefinition;

- vector.add(gvnFor[prim] ?? prim);

- }

- processTypeTest(TypeTest node) {

- vector = [GvnCode.TYPE_TEST, node.dartType];

- }

- processTypeTestViaFlag(TypeTestViaFlag node) {

- vector = [GvnCode.TYPE_TEST_VIA_FLAG, node.dartType];

- }

- processApplyBuiltinOperator(ApplyBuiltinOperator node) {

- vector = [GvnCode.BUILTIN_OPERATOR, node.operator.index];

- }

- processGetLength(GetLength node) {

- if (node.isFinal) {

- // Omit the effect number for fixed-length lists. Note that if a the list

- // gets refined to a fixed-length type, we still won't be able to GVN a

- // GetLength across the refinement, because the first GetLength uses an

- // effect number in its vector while the second one does not.

- vector = [GvnCode.GET_LENGTH];

- } else {

- vector = [GvnCode.GET_LENGTH, effectNumbers.indexableLength];

- }

- bool isNativeField(FieldElement field) {

- // TODO(asgerf): We should add a GetNativeField instruction.

- return backend.isNative(field);

- }

- processGetField(GetField node) {

- if (isNativeField(node.field)) {

- vector = null; // Native field access cannot be GVN'ed.

- } else if (node.isFinal) {

- vector = [GvnCode.GET_FIELD, node.field];

- } else {

- vector = [GvnCode.GET_FIELD, node.field, effectNumbers.instanceField];

- }

- processGetIndex(GetIndex node) {

- vector = [GvnCode.GET_INDEX, effectNumbers.indexableContent];

- }

- visitGetStatic(GetStatic node) {

- if (node.isFinal) {

- vector = [GvnCode.GET_STATIC, node.element];

- } else {

- vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField];

- }

- // Suppress visit to witness argument.

- }

- processGetLazyStatic(GetLazyStatic node) {

- if (node.isFinal) {

- vector = [GvnCode.GET_STATIC, node.element];

- } else {

- vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField];

- }

- processConstant(Constant node) {

- vector = [GvnCode.CONSTANT, node.value];

- }

- processReifyRuntimeType(ReifyRuntimeType node) {

- vector = [GvnCode.REIFY_RUNTIME_TYPE];

- }

- processReadTypeVariable(ReadTypeVariable node) {

- vector = [GvnCode.READ_TYPE_VARIABLE, node.variable];

- }

- processTypeExpression(TypeExpression node) {

- vector = [GvnCode.TYPE_EXPRESSION, node.kind.index, node.dartType];

- }

- processInterceptor(Interceptor node) {

- vector = [GvnCode.INTERCEPTOR];

- }

-class GvnCode {

- static const int TYPE_TEST = 1;

- static const int TYPE_TEST_VIA_FLAG = 2;

- static const int BUILTIN_OPERATOR = 3;

- static const int GET_LENGTH = 4;

- static const int GET_FIELD = 5;

- static const int GET_INDEX = 6;

- static const int GET_STATIC = 7;

- static const int CONSTANT = 8;

- static const int REIFY_RUNTIME_TYPE = 9;

- static const int READ_TYPE_VARIABLE = 10;

- static const int TYPE_EXPRESSION = 11;

- static const int INTERCEPTOR = 12;

-typedef ReferenceCallback(Reference ref);

-class InputVisitor extends DeepRecursiveVisitor {

- ReferenceCallback callback;

- InputVisitor(this.callback);

- @override

- processReference(Reference ref) {

- callback(ref);

- }

- static void forEach(Primitive node, ReferenceCallback callback) {

- new InputVisitor(callback).visit(node);

- }

« no previous file with comments | « pkg/compiler/lib/src/cps_ir/finalize.dart ('k') | pkg/compiler/lib/src/cps_ir/inline.dart » ('j') | no next file with comments »