Linter Demo

Errors: 0

Warnings: 1

File: /home/fstrocco/Dart/dart/benchmark/compiler/lib/src/cps_ir/redundant_phi.dart

// Copyright (c) 2014, 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. part of dart2js.cps_ir.optimizers; /// Eliminate redundant phis from the given [FunctionDefinition]. /// /// Phis in this case are [Continuations] together with corresponding /// [InvokeContinuation]s. A [Continuation] parameter at position i is redundant /// if for all [InvokeContinuation]s, the parameter at position i is identical /// (except for feedback). Redundant parameters are removed from the /// continuation signature, all invocations, and replaced within the /// continuation body. class RedundantPhiEliminator extends RecursiveVisitor implements Pass { String get passName => 'Redundant phi elimination'; final Set<Continuation> workSet = new Set<Continuation>(); @override void rewrite(RootNode root) { if (root.isEmpty) return; // Set all parent pointers. new ParentVisitor().visit(root); // Traverse the tree once to build the work set. visit(root); // Process each continuation one-by-one. while (workSet.isNotEmpty) { Continuation cont = workSet.first; workSet.remove(cont); if (cont.isReturnContinuation) { continue; // Skip function return continuations. } _processContinuation(cont); } } /// Called for each continuation on the work set. Modifies the IR graph if /// [cont] is a candidate for redundant phi elimination. void _processContinuation(Continuation cont) { // Generate the list of all cont invocations. If cont is used in any other // context (i.e. as a continuation of InvokeMethod), it is not possible to // optimize. List<InvokeContinuation> invokes = <InvokeContinuation>[]; for (Reference ref = cont.firstRef; ref != null; ref = ref.next) { Node parent = ref.parent; if (parent is InvokeContinuation && ref == parent.continuation) { invokes.add(parent); } else { return; // Can't optimize. } } if (invokes.isEmpty) { return; // Continuation is never invoked, can't optimize. } /// Returns the unique definition of parameter i if it exists and null /// otherwise. A definition is unique if it is the only value used to /// invoke the continuation, excluding feedback. Definition uniqueDefinitionOf(int i) { Definition value = null; for (InvokeContinuation invoke in invokes) { Definition def = invoke.arguments[i].definition; if (cont.parameters[i] == def) { // Invocation param == param in LetCont (i.e. a recursive call). continue; } else if (value == null) { value = def; // Set initial comparison value. } else if (value != def) { return null; // Differing invocation arguments. } } return value; } // If uniqueDefinition is in the body of the LetCont binding the // continuation, then we will drop the continuation binding to just inside // the binding of uniqueDefiniton. This is not safe if we drop the // continuation binding inside a LetHandler exception handler binding. LetCont letCont = cont.parent; bool safeForHandlers(Definition uniqueDefinition) { bool seenHandler = false; Node current = uniqueDefinition.parent; while (current != null) { if (current == letCont) return !seenHandler; seenHandler = seenHandler || current is LetHandler; current = current.parent; } // When uniqueDefinition is not in the body of the LetCont binding the // continuation, we will not move any code, so that is safe. return true; } // Check if individual parameters are always called with a unique // definition, and remove them if that is the case. During each iteration, // we read the current parameter/argument from index `src` and copy it // to index `dst`. int dst = 0; for (int src = 0; src < cont.parameters.length; src++) { // Is the current phi redundant? Definition uniqueDefinition = uniqueDefinitionOf(src); if (uniqueDefinition == null || !safeForHandlers(uniqueDefinition)) { // Reorganize parameters and arguments in case of deletions. if (src != dst) { cont.parameters[dst] = cont.parameters[src]; for (InvokeContinuation invoke in invokes) { invoke.arguments[dst] = invoke.arguments[src]; } } dst++; continue; } Definition oldDefinition = cont.parameters[src]; // Add continuations of about-to-be modified invokes to worklist since // we might introduce new optimization opportunities. for (Reference ref = oldDefinition.firstRef; ref != null; ref = ref.next) { Node parent = ref.parent; if (parent is InvokeContinuation) { Continuation thatCont = parent.continuation.definition; if (thatCont != cont) { workSet.add(thatCont); } } } // Replace individual parameters: // * In the continuation body, replace occurrence of param with value, // * and implicitly remove param from continuation signature and // invocations by not incrementing `dst`. References of removed // arguments are unlinked to keep definition usages up to date. uniqueDefinition.substituteFor(oldDefinition); for (InvokeContinuation invoke in invokes) { invoke.arguments[src].unlink(); } // Finally, if the substituted definition is not in scope of the affected // continuation, move the continuation binding. This is safe to do since // the continuation is referenced only as the target in continuation // invokes, and all such invokes must be within the scope of // [uniqueDefinition]. Note that this is linear in the depth of // the binding of [uniqueDefinition]. assert(letCont != null); _moveIntoScopeOf(letCont, uniqueDefinition); } // Remove trailing items from parameter and argument lists. cont.parameters.length = dst; for (InvokeContinuation invoke in invokes) { invoke.arguments.length = dst; } } void processLetCont(LetCont node) { node.continuations.forEach(workSet.add); } } /// Returns true, iff [letCont] is not scope of [definition]. /// Linear in the depth of definition within the IR graph. bool _isInScopeOf(LetCont letCont, Definition definition) { for (Node node = definition.parent; node != null; node = node.parent) { if (node == letCont) { return false; } } return true; } /// Moves [letCont] below the binding of [definition] within the IR graph. /// Does nothing if [letCont] is already within the scope of [definition]. /// Assumes that one argument is nested within the scope of the other /// when this method is called. void _moveIntoScopeOf(LetCont letCont, Definition definition) { if (_isInScopeOf(letCont, definition)) return; // Remove the continuation binding from its current spot. InteriorNode parent = letCont.parent; parent.body = letCont.body; letCont.body.parent = parent; // Insert it just below the binding of definition. InteriorNode binding = definition.parent; letCont.body = binding.body; binding.body.parent = letCont; binding.body = letCont; letCont.parent = binding; }