Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(375)

Unified Diff: pkg/compiler/lib/src/ssa/variable_allocator.dart

Issue 693183006: Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month 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
Download patch
« no previous file with comments | « pkg/compiler/lib/src/ssa/value_set.dart ('k') | pkg/compiler/lib/src/string_validator.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: pkg/compiler/lib/src/ssa/variable_allocator.dart
diff --git a/pkg/compiler/lib/src/ssa/variable_allocator.dart b/pkg/compiler/lib/src/ssa/variable_allocator.dart
deleted file mode 100644
index bd95f58b00f2735768f5dfbd517aa42d437fde5e..0000000000000000000000000000000000000000
--- a/pkg/compiler/lib/src/ssa/variable_allocator.dart
+++ /dev/null
@@ -1,716 +0,0 @@
-// Copyright (c) 2012, 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 ssa;
-
-/**
- * The [LiveRange] class covers a range where an instruction is live.
- */
-class LiveRange {
- final int start;
- // [end] is not final because it can be updated due to loops.
- int end;
- LiveRange(this.start, this.end) {
- assert(start <= end);
- }
-
- String toString() => '[$start $end[';
-}
-
-/**
- * The [LiveInterval] class contains the list of ranges where an
- * instruction is live.
- */
-class LiveInterval {
- /**
- * The id where the instruction is defined.
- */
- int start;
- final List<LiveRange> ranges;
- LiveInterval() : ranges = <LiveRange>[];
-
- // We want [HCheck] instructions to have the same name as the
- // instruction it checks, so both instructions should share the same
- // live ranges.
- LiveInterval.forCheck(this.start, LiveInterval checkedInterval)
- : ranges = checkedInterval.ranges;
-
- /**
- * Update all ranges that are contained in [from, to[ to
- * die at [to].
- */
- void loopUpdate(int from, int to) {
- for (LiveRange range in ranges) {
- if (from <= range.start && range.end < to) {
- range.end = to;
- }
- }
- }
-
- /**
- * Add a new range to this interval.
- */
- void add(LiveRange interval) {
- ranges.add(interval);
- }
-
- /**
- * Returns true if one of the ranges of this interval dies at [at].
- */
- bool diesAt(int at) {
- for (LiveRange range in ranges) {
- if (range.end == at) return true;
- }
- return false;
- }
-
- String toString() {
- List<String> res = new List<String>();
- for (final interval in ranges) res.add(interval.toString());
- return '(${res.join(", ")})';
- }
-}
-
-/**
- * The [LiveEnvironment] class contains the liveIn set of a basic
- * block. A liveIn set of a block contains the instructions that are
- * live when entering that block.
- */
-class LiveEnvironment {
- /**
- * The instruction id where the basic block starts. See
- * [SsaLiveIntervalBuilder.instructionId].
- */
- int startId;
-
- /**
- * The instruction id where the basic block ends.
- */
- final int endId;
-
- /**
- * Loop markers that will be updated once the loop header is
- * visited. The liveIn set of the loop header will be merged into this
- * environment. [loopMarkers] is a mapping from block header to the
- * end instruction id of the loop exit block.
- */
- final Map<HBasicBlock, int> loopMarkers;
-
- /**
- * The instructions that are live in this basic block. The values of
- * the map contain the instruction ids where the instructions die.
- * It will be used when adding a range to the live interval of an
- * instruction.
- */
- final Map<HInstruction, int> liveInstructions;
-
- /**
- * Map containing the live intervals of instructions.
- */
- final Map<HInstruction, LiveInterval> liveIntervals;
-
- LiveEnvironment(this.liveIntervals, this.endId)
- : liveInstructions = new Map<HInstruction, int>(),
- loopMarkers = new Map<HBasicBlock, int>();
-
- /**
- * Remove an instruction from the liveIn set. This method also
- * updates the live interval of [instruction] to contain the new
- * range: [id, / id contained in [liveInstructions] /].
- */
- void remove(HInstruction instruction, int id) {
- LiveInterval interval = liveIntervals.putIfAbsent(
- instruction, () => new LiveInterval());
- int lastId = liveInstructions[instruction];
- // If [lastId] is null, then this instruction is not being used.
- interval.add(new LiveRange(id, lastId == null ? id : lastId));
- // The instruction is defined at [id].
- interval.start = id;
- liveInstructions.remove(instruction);
- }
-
- /**
- * Add [instruction] to the liveIn set. If the instruction is not
- * already in the set, we save the id where it dies.
- */
- void add(HInstruction instruction, int userId) {
- // Note that we are visiting the graph in post-dominator order, so
- // the first time we see a variable is when it dies.
- liveInstructions.putIfAbsent(instruction, () => userId);
- }
-
- /**
- * Merge this environment with [other]. Update the end id of
- * instructions in case they are different between this and [other].
- */
- void mergeWith(LiveEnvironment other) {
- other.liveInstructions.forEach((HInstruction instruction, int existingId) {
- // If both environments have the same instruction id of where
- // [instruction] dies, there is no need to update the live
- // interval of [instruction]. For example the if block and the
- // else block have the same end id for an instruction that is
- // being used in the join block and defined before the if/else.
- if (existingId == endId) return;
- LiveInterval range = liveIntervals.putIfAbsent(
- instruction, () => new LiveInterval());
- range.add(new LiveRange(other.startId, existingId));
- liveInstructions[instruction] = endId;
- });
- other.loopMarkers.forEach((k, v) { loopMarkers[k] = v; });
- }
-
- void addLoopMarker(HBasicBlock header, int id) {
- assert(!loopMarkers.containsKey(header));
- loopMarkers[header] = id;
- }
-
- void removeLoopMarker(HBasicBlock header) {
- assert(loopMarkers.containsKey(header));
- loopMarkers.remove(header);
- }
-
- bool get isEmpty => liveInstructions.isEmpty && loopMarkers.isEmpty;
- bool contains(HInstruction instruction) =>
- liveInstructions.containsKey(instruction);
- String toString() => liveInstructions.toString();
-}
-
-/**
- * Builds the live intervals of each instruction. The algorithm visits
- * the graph post-dominator tree to find the last uses of an
- * instruction, and computes the liveIns of each basic block.
- */
-class SsaLiveIntervalBuilder extends HBaseVisitor {
- final Compiler compiler;
- final Set<HInstruction> generateAtUseSite;
- final Set<HInstruction> controlFlowOperators;
-
- /**
- * A counter to assign start and end ids to live ranges. The initial
- * value is not relevant. Note that instructionId goes downward to ease
- * reasoning about live ranges (the first instruction of a graph has
- * the lowest id).
- */
- int instructionId = 0;
-
- /**
- * The liveIns of basic blocks.
- */
- final Map<HBasicBlock, LiveEnvironment> liveInstructions;
-
- /**
- * The live intervals of instructions.
- */
- final Map<HInstruction, LiveInterval> liveIntervals;
-
- SsaLiveIntervalBuilder(
- this.compiler, this.generateAtUseSite, this.controlFlowOperators)
- : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(),
- liveIntervals = new Map<HInstruction, LiveInterval>();
-
- void visitGraph(HGraph graph) {
- visitPostDominatorTree(graph);
- if (!liveInstructions[graph.entry].isEmpty) {
- compiler.internalError(CURRENT_ELEMENT_SPANNABLE, 'LiveIntervalBuilder.');
- }
- }
-
- void markInputsAsLiveInEnvironment(HInstruction instruction,
- LiveEnvironment environment) {
- for (int i = 0, len = instruction.inputs.length; i < len; i++) {
- markAsLiveInEnvironment(instruction.inputs[i], environment);
- }
- }
-
- // Returns the non-HCheck instruction, or the last [HCheck] in the
- // check chain that is not generate at use site.
- //
- // For example:
- //
- // t1 = GeneratedAtUseSite instruction
- // t2 = check(t1)
- // t3 = check(t2)
- // t4 = use(t3)
- // t5 = use(t3)
- // t6 = use(t2)
- //
- // The t1 is generate-at-use site, and the live-range must thus be on t2 and
- // not on the checked instruction t1.
- // When looking for the checkedInstructionOrNonGenerateAtUseSite of t3 we must
- // return t2.
- HInstruction checkedInstructionOrNonGenerateAtUseSite(HCheck check) {
- var checked = check.checkedInput;
- while (checked is HCheck) {
- HInstruction next = checked.checkedInput;
- if (generateAtUseSite.contains(next)) break;
- checked = next;
- }
- return checked;
- }
-
- void markAsLiveInEnvironment(HInstruction instruction,
- LiveEnvironment environment) {
- if (generateAtUseSite.contains(instruction)) {
- markInputsAsLiveInEnvironment(instruction, environment);
- } else {
- environment.add(instruction, instructionId);
- // Special case the HCheck instruction to mark the actual
- // checked instruction live. The checked instruction and the
- // [HCheck] will share the same live ranges.
- if (instruction is HCheck) {
- HCheck check = instruction;
- HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check);
- if (!generateAtUseSite.contains(checked)) {
- environment.add(checked, instructionId);
- }
- }
- }
- }
-
- void removeFromEnvironment(HInstruction instruction,
- LiveEnvironment environment) {
- environment.remove(instruction, instructionId);
- // Special case the HCheck instruction to have the same live
- // interval as the instruction it is checking.
- if (instruction is HCheck) {
- HCheck check = instruction;
- HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check);
- if (!generateAtUseSite.contains(checked)) {
- liveIntervals.putIfAbsent(checked, () => new LiveInterval());
- // Unconditionally force the live ranges of the HCheck to
- // be the live ranges of the instruction it is checking.
- liveIntervals[instruction] =
- new LiveInterval.forCheck(instructionId, liveIntervals[checked]);
- }
- }
- }
-
- void visitBasicBlock(HBasicBlock block) {
- LiveEnvironment environment =
- new LiveEnvironment(liveIntervals, instructionId);
-
- // If the control flow instruction in this block will actually be
- // inlined in the codegen in the join block, we need to make
- // whatever is used by that control flow instruction as live in
- // the join block.
- if (controlFlowOperators.contains(block.last)) {
- HIf ifInstruction = block.last;
- HBasicBlock joinBlock = ifInstruction.joinBlock;
- if (generateAtUseSite.contains(joinBlock.phis.first)) {
- markInputsAsLiveInEnvironment(
- ifInstruction, liveInstructions[joinBlock]);
- }
- }
-
- // Add to the environment the liveIn of its successor, as well as
- // the inputs of the phis of the successor that flow from this block.
- for (int i = 0; i < block.successors.length; i++) {
- HBasicBlock successor = block.successors[i];
- LiveEnvironment successorEnv = liveInstructions[successor];
- if (successorEnv != null) {
- environment.mergeWith(successorEnv);
- } else {
- environment.addLoopMarker(successor, instructionId);
- }
-
- int index = successor.predecessors.indexOf(block);
- for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) {
- markAsLiveInEnvironment(phi.inputs[index], environment);
- }
- }
-
- // Iterate over all instructions to remove an instruction from the
- // environment and add its inputs.
- HInstruction instruction = block.last;
- while (instruction != null) {
- if (!generateAtUseSite.contains(instruction)) {
- removeFromEnvironment(instruction, environment);
- markInputsAsLiveInEnvironment(instruction, environment);
- }
- instructionId--;
- instruction = instruction.previous;
- }
-
- // We just remove the phis from the environment. The inputs of the
- // phis will be put in the environment of the predecessors.
- for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
- if (!generateAtUseSite.contains(phi)) {
- environment.remove(phi, instructionId);
- }
- }
-
- // Save the liveInstructions of that block.
- environment.startId = instructionId + 1;
- liveInstructions[block] = environment;
-
- // If the block is a loop header, we can remove the loop marker,
- // because it will just recompute the loop phis.
- // We also check if this loop header has any back edges. If not,
- // we know there is no loop marker for it.
- if (block.isLoopHeader() && block.predecessors.length > 1) {
- updateLoopMarker(block);
- }
- }
-
- void updateLoopMarker(HBasicBlock header) {
- LiveEnvironment env = liveInstructions[header];
- int lastId = env.loopMarkers[header];
- // Update all instructions that are liveIns in [header] to have a
- // range that covers the loop.
- env.liveInstructions.forEach((HInstruction instruction, int id) {
- LiveInterval range = env.liveIntervals.putIfAbsent(
- instruction, () => new LiveInterval());
- range.loopUpdate(env.startId, lastId);
- env.liveInstructions[instruction] = lastId;
- });
-
- env.removeLoopMarker(header);
-
- // Update all liveIns set to contain the liveIns of [header].
- liveInstructions.forEach((HBasicBlock block, LiveEnvironment other) {
- if (other.loopMarkers.containsKey(header)) {
- env.liveInstructions.forEach((HInstruction instruction, int id) {
- other.liveInstructions[instruction] = id;
- });
- other.removeLoopMarker(header);
- env.loopMarkers.forEach((k, v) { other.loopMarkers[k] = v; });
- }
- });
- }
-}
-
-/**
- * Represents a copy from one instruction to another. The codegen
- * also uses this class to represent a copy from one variable to
- * another.
- */
-class Copy {
- final source;
- final destination;
- Copy(this.source, this.destination);
- String toString() => '$destination <- $source';
-}
-
-/**
- * A copy handler contains the copies that a basic block needs to do
- * after executing all its instructions.
- */
-class CopyHandler {
- /**
- * The copies from an instruction to a phi of the successor.
- */
- final List<Copy> copies;
-
- /**
- * Assignments from an instruction that does not need a name (e.g. a
- * constant) to the phi of a successor.
- */
- final List<Copy> assignments;
-
- CopyHandler()
- : copies = new List<Copy>(),
- assignments = new List<Copy>();
-
- void addCopy(HInstruction source, HInstruction destination) {
- copies.add(new Copy(source, destination));
- }
-
- void addAssignment(HInstruction source, HInstruction destination) {
- assignments.add(new Copy(source, destination));
- }
-
- String toString() => 'Copies: $copies, assignments: $assignments';
- bool get isEmpty => copies.isEmpty && assignments.isEmpty;
-}
-
-/**
- * Contains the mapping between instructions and their names for code
- * generation, as well as the [CopyHandler] for each basic block.
- */
-class VariableNames {
- final Map<HInstruction, String> ownName;
- final Map<HBasicBlock, CopyHandler> copyHandlers;
-
- // Used to control heuristic that determines how local variables are declared.
- final Set<String> allUsedNames;
- /**
- * Name that is used as a temporary to break cycles in
- * parallel copies. We make sure this name is not being used
- * anywhere by reserving it when we allocate names for instructions.
- */
- final String swapTemp;
-
- String getSwapTemp() {
- allUsedNames.add(swapTemp);
- return swapTemp;
- }
-
- VariableNames()
- : ownName = new Map<HInstruction, String>(),
- copyHandlers = new Map<HBasicBlock, CopyHandler>(),
- allUsedNames = new Set<String>(),
- swapTemp = 't0';
-
- int get numberOfVariables => allUsedNames.length;
-
- String getName(HInstruction instruction) {
- return ownName[instruction];
- }
-
- CopyHandler getCopyHandler(HBasicBlock block) {
- return copyHandlers[block];
- }
-
- void addNameUsed(String name) {
- allUsedNames.add(name);
- }
-
- bool hasName(HInstruction instruction) => ownName.containsKey(instruction);
-
- void addCopy(HBasicBlock block, HInstruction source, HPhi destination) {
- CopyHandler handler =
- copyHandlers.putIfAbsent(block, () => new CopyHandler());
- handler.addCopy(source, destination);
- }
-
- void addAssignment(HBasicBlock block, HInstruction source, HPhi destination) {
- CopyHandler handler =
- copyHandlers.putIfAbsent(block, () => new CopyHandler());
- handler.addAssignment(source, destination);
- }
-}
-
-/**
- * Allocates variable names for instructions, making sure they don't collide.
- */
-class VariableNamer {
- final VariableNames names;
- final Compiler compiler;
- final Set<String> usedNames;
- final List<String> freeTemporaryNames;
- int temporaryIndex = 0;
- static final RegExp regexp = new RegExp('t[0-9]+');
-
- VariableNamer(LiveEnvironment environment,
- this.names,
- this.compiler)
- : usedNames = new Set<String>(),
- freeTemporaryNames = new List<String>() {
- // [VariableNames.swapTemp] is used when there is a cycle in a copy handler.
- // Therefore we make sure no one uses it.
- usedNames.add(names.swapTemp);
-
- // All liveIns instructions must have a name at this point, so we
- // add them to the list of used names.
- environment.liveInstructions.forEach((HInstruction instruction, int index) {
- String name = names.getName(instruction);
- if (name != null) {
- usedNames.add(name);
- names.addNameUsed(name);
- }
- });
- }
-
- String allocateWithHint(String originalName) {
- int i = 0;
- JavaScriptBackend backend = compiler.backend;
- String name = backend.namer.safeVariableName(originalName);
- while (usedNames.contains(name)) {
- name = backend.namer.safeVariableName('$originalName${i++}');
- }
- return name;
- }
-
- String allocateTemporary() {
- while (!freeTemporaryNames.isEmpty) {
- String name = freeTemporaryNames.removeLast();
- if (!usedNames.contains(name)) return name;
- }
- String name = 't${temporaryIndex++}';
- while (usedNames.contains(name)) name = 't${temporaryIndex++}';
- return name;
- }
-
- HPhi firstPhiUserWithElement(HInstruction instruction) {
- for (HInstruction user in instruction.usedBy) {
- if (user is HPhi && user.sourceElement != null) {
- return user;
- }
- }
- return null;
- }
-
- String allocateName(HInstruction instruction) {
- String name;
- if (instruction is HCheck) {
- // Special case this instruction to use the name of its
- // input if it has one.
- var temp = instruction;
- do {
- temp = temp.checkedInput;
- name = names.ownName[temp];
- } while (name == null && temp is HCheck);
- if (name != null) return addAllocatedName(instruction, name);
- }
-
- if (instruction.sourceElement != null) {
- name = allocateWithHint(instruction.sourceElement.name);
- } else {
- // We could not find an element for the instruction. If the
- // instruction is used by a phi, try to use the name of the phi.
- // Otherwise, just allocate a temporary name.
- HPhi phi = firstPhiUserWithElement(instruction);
- if (phi != null) {
- name = allocateWithHint(phi.sourceElement.name);
- } else {
- name = allocateTemporary();
- }
- }
- return addAllocatedName(instruction, name);
- }
-
- String addAllocatedName(HInstruction instruction, String name) {
- usedNames.add(name);
- names.addNameUsed(name);
- names.ownName[instruction] = name;
- return name;
- }
-
- /**
- * Frees [instruction]'s name so it can be used for other instructions.
- */
- void freeName(HInstruction instruction) {
- String ownName = names.ownName[instruction];
- if (ownName != null) {
- // We check if we have already looked for temporary names
- // because if we haven't, chances are the temporary we allocate
- // in this block can match a phi with the same name in the
- // successor block.
- if (temporaryIndex != 0 && regexp.hasMatch(ownName)) {
- freeTemporaryNames.add(ownName);
- }
- usedNames.remove(ownName);
- }
- }
-}
-
-/**
- * Visits all blocks in the graph, sets names to instructions, and
- * creates the [CopyHandler] for each block. This class needs to have
- * the liveIns set as well as all the live intervals of instructions.
- * It visits the graph in dominator order, so that at each entry of a
- * block, the instructions in its liveIns set have names.
- *
- * When visiting a block, it goes through all instructions. For each
- * instruction, it frees the names of the inputs that die at that
- * instruction, and allocates a name to the instruction. For each phi,
- * it adds a copy to the CopyHandler of the corresponding predecessor.
- */
-class SsaVariableAllocator extends HBaseVisitor {
-
- final Compiler compiler;
- final Map<HBasicBlock, LiveEnvironment> liveInstructions;
- final Map<HInstruction, LiveInterval> liveIntervals;
- final Set<HInstruction> generateAtUseSite;
-
- final VariableNames names;
-
- SsaVariableAllocator(this.compiler,
- this.liveInstructions,
- this.liveIntervals,
- this.generateAtUseSite)
- : this.names = new VariableNames();
-
- void visitGraph(HGraph graph) {
- visitDominatorTree(graph);
- }
-
- void visitBasicBlock(HBasicBlock block) {
- VariableNamer namer = new VariableNamer(
- liveInstructions[block], names, compiler);
-
- block.forEachPhi((HPhi phi) {
- handlePhi(phi, namer);
- });
-
- block.forEachInstruction((HInstruction instruction) {
- handleInstruction(instruction, namer);
- });
- }
-
- /**
- * Returns whether [instruction] needs a name. Instructions that
- * have no users or that are generated at use site do not need a name.
- */
- bool needsName(instruction) {
- if (instruction is HThis) return false;
- if (instruction is HParameterValue) return true;
- if (instruction.usedBy.isEmpty) return false;
- if (generateAtUseSite.contains(instruction)) return false;
- return !instruction.nonCheck().isCodeMotionInvariant();
- }
-
- /**
- * Returns whether [instruction] dies at the instruction [at].
- */
- bool diesAt(HInstruction instruction, HInstruction at) {
- LiveInterval atInterval = liveIntervals[at];
- LiveInterval instructionInterval = liveIntervals[instruction];
- int start = atInterval.start;
- return instructionInterval.diesAt(start);
- }
-
- void freeUsedNamesAt(HInstruction instruction,
- HInstruction at,
- VariableNamer namer) {
- if (needsName(instruction)) {
- if (diesAt(instruction, at)) {
- namer.freeName(instruction);
- }
- } else if (generateAtUseSite.contains(instruction)) {
- // If the instruction is generated at use site, then all its
- // inputs may also die at [at].
- for (int i = 0, len = instruction.inputs.length; i < len; i++) {
- HInstruction input = instruction.inputs[i];
- freeUsedNamesAt(input, at, namer);
- }
- }
- }
-
- void handleInstruction(HInstruction instruction, VariableNamer namer) {
- if (generateAtUseSite.contains(instruction)) {
- assert(!liveIntervals.containsKey(instruction));
- return;
- }
-
- for (int i = 0, len = instruction.inputs.length; i < len; i++) {
- HInstruction input = instruction.inputs[i];
- freeUsedNamesAt(input, instruction, namer);
- }
-
- if (needsName(instruction)) {
- namer.allocateName(instruction);
- }
- }
-
- void handlePhi(HPhi phi, VariableNamer namer) {
- if (!needsName(phi)) return;
-
- for (int i = 0; i < phi.inputs.length; i++) {
- HInstruction input = phi.inputs[i];
- HBasicBlock predecessor = phi.block.predecessors[i];
- // A [HTypeKnown] instruction never has a name, but its checked
- // input might, therefore we need to do a copy instead of an
- // assignment.
- while (input is HTypeKnown) input = input.inputs[0];
- if (!needsName(input)) {
- names.addAssignment(predecessor, input, phi);
- } else {
- names.addCopy(predecessor, input, phi);
- }
- }
-
- namer.allocateName(phi);
- }
-}
« no previous file with comments | « pkg/compiler/lib/src/ssa/value_set.dart ('k') | pkg/compiler/lib/src/string_validator.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698