| // Copyright (c) 2015, 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 tree_ir.optimization.variable_merger; |
| |
| import 'optimization.dart' show Pass; |
| import '../tree_ir_nodes.dart'; |
| |
| /// Merges variables based on liveness and source variable information. |
| /// |
| /// This phase cleans up artifacts introduced by the translation through CPS, |
| /// where each source variable is translated into several copies. The copies |
| /// are merged again when they are not live simultaneously. |
| class VariableMerger implements Pass { |
| String get passName => 'Variable merger'; |
| |
| final bool minifying; |
| |
| VariableMerger({this.minifying: false}); |
| |
| void rewrite(FunctionDefinition node) { |
| BlockGraphBuilder builder = new BlockGraphBuilder()..build(node); |
| _computeLiveness(builder.blocks); |
| PriorityPairs priority = new PriorityPairs()..build(node); |
| Map<Variable, Variable> subst = _computeRegisterAllocation( |
| builder.blocks, node.parameters, priority, minifying: minifying); |
| new SubstituteVariables(subst).apply(node); |
| } |
| } |
| |
| /// A read or write access to a variable. |
| class VariableAccess { |
| Variable variable; |
| bool isRead; |
| bool get isWrite => !isRead; |
| |
| VariableAccess.read(this.variable) : isRead = true; |
| VariableAccess.write(this.variable) : isRead = false; |
| } |
| |
| /// Basic block in a control-flow graph. |
| class Block { |
| /// List of predecessors in the control-flow graph. |
| final List<Block> predecessors = <Block>[]; |
| |
| /// Entry to the catch block for the enclosing try, or `null`. |
| final Block catchBlock; |
| |
| /// List of nodes with this block as [catchBlock]. |
| final List<Block> catchPredecessors = <Block>[]; |
| |
| /// Sequence of read and write accesses in the block. |
| final List<VariableAccess> accesses = <VariableAccess>[]; |
| |
| /// Auxiliary fields used by the liveness analysis. |
| bool inWorklist = true; |
| Set<Variable> liveIn; |
| Set<Variable> liveOut = new Set<Variable>(); |
| Set<Variable> gen = new Set<Variable>(); |
| Set<Variable> kill = new Set<Variable>(); |
| |
| /// Adds a read operation to the block and updates gen/kill sets accordingly. |
| void addRead(Variable variable) { |
| // Operations are seen in forward order. |
| // If the read is not preceded by a write, then add it to the GEN set. |
| if (!kill.contains(variable)) { |
| gen.add(variable); |
| } |
| accesses.add(new VariableAccess.read(variable)); |
| } |
| |
| /// Adds a write operation to the block and updates gen/kill sets accordingly. |
| void addWrite(Variable variable) { |
| // If the write is not preceded by a read, then add it to the KILL set. |
| if (!gen.contains(variable)) { |
| kill.add(variable); |
| } |
| accesses.add(new VariableAccess.write(variable)); |
| } |
| |
| Block(this.catchBlock) { |
| if (catchBlock != null) { |
| catchBlock.catchPredecessors.add(this); |
| } |
| } |
| } |
| |
| /// Builds a control-flow graph suitable for performing liveness analysis. |
| class BlockGraphBuilder extends RecursiveVisitor { |
| Map<Label, Block> _jumpTarget = <Label, Block>{}; |
| Block _currentBlock; |
| List<Block> blocks = <Block>[]; |
| |
| /// Variables with an assignment that should be treated as final. |
| /// |
| /// Such variables cannot be merged with any other variables, so we exclude |
| /// them from the control-flow graph entirely. |
| Set<Variable> _ignoredVariables = new Set<Variable>(); |
| |
| void build(FunctionDefinition node) { |
| _currentBlock = newBlock(); |
| node.parameters.forEach(write); |
| visitStatement(node.body); |
| } |
| |
| /// Creates a new block with the current exception handler or [catchBlock] |
| /// if provided. |
| Block newBlock({Block catchBlock}) { |
| if (catchBlock == null && _currentBlock != null) { |
| catchBlock = _currentBlock.catchBlock; |
| } |
| Block block = new Block(catchBlock); |
| blocks.add(block); |
| return block; |
| } |
| |
| /// Starts a new block after the end of [block]. |
| void branchFrom(Block block, {Block catchBlock}) { |
| _currentBlock = newBlock(catchBlock: catchBlock)..predecessors.add(block); |
| } |
| |
| /// Starts a new block with the given blocks as predecessors. |
| void joinFrom(Block block1, Block block2) { |
| assert(block1.catchBlock == block2.catchBlock); |
| _currentBlock = newBlock(catchBlock: block1.catchBlock); |
| _currentBlock.predecessors.add(block1); |
| _currentBlock.predecessors.add(block2); |
| } |
| |
| /// Called when reading from [variable]. |
| /// |
| /// Appends a read operation to the current basic block. |
| void read(Variable variable) { |
| if (variable.isCaptured) return; |
| if (_ignoredVariables.contains(variable)) return; |
| _currentBlock.addRead(variable); |
| } |
| |
| /// Called when writing to [variable]. |
| /// |
| /// Appends a write operation to the current basic block. |
| void write(Variable variable) { |
| if (variable.isCaptured) return; |
| if (_ignoredVariables.contains(variable)) return; |
| _currentBlock.addWrite(variable); |
| } |
| |
| /// Called to indicate that [variable] should not be merged, and therefore |
| /// be excluded from the control-flow graph. |
| /// Subsequent calls to [read] and [write] will ignore it. |
| void ignoreVariable(Variable variable) { |
| _ignoredVariables.add(variable); |
| } |
| |
| visitVariableUse(VariableUse node) { |
| read(node.variable); |
| } |
| |
| visitAssign(Assign node) { |
| visitExpression(node.value); |
| write(node.variable); |
| } |
| |
| visitIf(If node) { |
| visitExpression(node.condition); |
| Block afterCondition = _currentBlock; |
| branchFrom(afterCondition); |
| visitStatement(node.thenStatement); |
| Block afterThen = _currentBlock; |
| branchFrom(afterCondition); |
| visitStatement(node.elseStatement); |
| joinFrom(_currentBlock, afterThen); |
| } |
| |
| visitLabeledStatement(LabeledStatement node) { |
| Block join = _jumpTarget[node.label] = newBlock(); |
| visitStatement(node.body); // visitBreak will add predecessors to join. |
| _currentBlock = join; |
| visitStatement(node.next); |
| } |
| |
| visitBreak(Break node) { |
| _jumpTarget[node.target].predecessors.add(_currentBlock); |
| } |
| |
| visitContinue(Continue node) { |
| _jumpTarget[node.target].predecessors.add(_currentBlock); |
| } |
| |
| visitWhileTrue(WhileTrue node) { |
| Block join = _jumpTarget[node.label] = newBlock(); |
| join.predecessors.add(_currentBlock); |
| _currentBlock = join; |
| visitStatement(node.body); // visitContinue will add predecessors to join. |
| } |
| |
| visitFor(For node) { |
| Block entry = _currentBlock; |
| _currentBlock = _jumpTarget[node.label] = newBlock(); |
| node.updates.forEach(visitExpression); |
| joinFrom(entry, _currentBlock); |
| visitExpression(node.condition); |
| Block afterCondition = _currentBlock; |
| branchFrom(afterCondition); |
| visitStatement(node.body); // visitContinue will add predecessors to join. |
| branchFrom(afterCondition); |
| visitStatement(node.next); |
| } |
| |
| visitTry(Try node) { |
| Block outerCatchBlock = _currentBlock.catchBlock; |
| Block catchBlock = newBlock(catchBlock: outerCatchBlock); |
| branchFrom(_currentBlock, catchBlock: catchBlock); |
| visitStatement(node.tryBody); |
| Block afterTry = _currentBlock; |
| _currentBlock = catchBlock; |
| // Catch parameters cannot be hoisted to the top of the function, so to |
| // avoid complications with scoping, we do not attempt to merge them. |
| node.catchParameters.forEach(ignoreVariable); |
| visitStatement(node.catchBody); |
| Block afterCatch = _currentBlock; |
| _currentBlock = newBlock(catchBlock: outerCatchBlock); |
| _currentBlock.predecessors.add(afterCatch); |
| _currentBlock.predecessors.add(afterTry); |
| } |
| |
| visitConditional(Conditional node) { |
| visitExpression(node.condition); |
| Block afterCondition = _currentBlock; |
| branchFrom(afterCondition); |
| visitExpression(node.thenExpression); |
| Block afterThen = _currentBlock; |
| branchFrom(afterCondition); |
| visitExpression(node.elseExpression); |
| joinFrom(_currentBlock, afterThen); |
| } |
| |
| visitLogicalOperator(LogicalOperator node) { |
| visitExpression(node.left); |
| Block afterLeft = _currentBlock; |
| branchFrom(afterLeft); |
| visitExpression(node.right); |
| joinFrom(_currentBlock, afterLeft); |
| } |
| } |
| |
| /// Collects prioritized variable pairs -- pairs that lead to significant code |
| /// reduction if merged into one variable. |
| /// |
| /// These arise from moving assigments `v1 = v2`, and compoundable assignments |
| /// `v1 = v2 [+] E` where [+] is a compoundable operator. |
| // |
| // TODO(asgerf): We could have a more fine-grained priority level. All pairs |
| // are treated as equally important, but some pairs can eliminate more than |
| // one assignment. |
| // Also, some assignments are more important to remove than others, as they |
| // can block a later optimization, such rewriting a loop, or removing the |
| // 'else' part of an 'if'. |
| // |
| class PriorityPairs extends RecursiveVisitor { |
| final Map<Variable, List<Variable>> _priority = <Variable, List<Variable>>{}; |
| |
| void build(FunctionDefinition node) { |
| visitStatement(node.body); |
| } |
| |
| void _prioritize(Variable x, Variable y) { |
| _priority.putIfAbsent(x, () => new List<Variable>()).add(y); |
| _priority.putIfAbsent(y, () => new List<Variable>()).add(x); |
| } |
| |
| visitAssign(Assign node) { |
| super.visitAssign(node); |
| Expression value = node.value; |
| if (value is VariableUse) { |
| _prioritize(node.variable, value.variable); |
| } else if (value is ApplyBuiltinOperator && |
| isCompoundableOperator(value.operator) && |
| value.arguments[0] is VariableUse) { |
| VariableUse use = value.arguments[0]; |
| _prioritize(node.variable, use.variable); |
| } |
| } |
| |
| /// Returns the other half of every priority pair containing [variable]. |
| List<Variable> getPriorityPairsWith(Variable variable) { |
| return _priority[variable] ?? const <Variable>[]; |
| } |
| |
| bool hasPriorityPairs(Variable variable) { |
| return _priority.containsKey(variable); |
| } |
| } |
| |
| /// Computes liveness information of the given control-flow graph. |
| /// |
| /// The results are stored in [Block.liveIn] and [Block.liveOut]. |
| void _computeLiveness(List<Block> blocks) { |
| // We use a LIFO queue as worklist. Blocks are given in AST order, so by |
| // inserting them in this order, we initially visit them backwards, which |
| // is a good ordering. |
| // The choice of LIFO for re-inserted blocks is currently arbitrary, |
| List<Block> worklist = new List<Block>.from(blocks); |
| while (!worklist.isEmpty) { |
| Block block = worklist.removeLast(); |
| block.inWorklist = false; |
| |
| bool changed = false; |
| |
| // The liveIn set is computed as: |
| // |
| // liveIn = (liveOut - kill) + gen |
| // |
| // We do the computation in two steps: |
| // |
| // 1. liveIn = gen |
| // 2. liveIn += (liveOut - kill) |
| // |
| // However, since liveIn only grows, and gen never changes, we only have |
| // to do the first step at the first iteration. Moreover, the gen set is |
| // not needed anywhere else, so we don't even need to copy it. |
| if (block.liveIn == null) { |
| block.liveIn = block.gen; |
| block.gen = null; |
| changed = true; |
| } |
| |
| // liveIn += (liveOut - kill) |
| for (Variable variable in block.liveOut) { |
| if (!block.kill.contains(variable)) { |
| if (block.liveIn.add(variable)) { |
| changed = true; |
| } |
| } |
| } |
| |
| // If anything changed, propagate liveness backwards. |
| if (changed) { |
| // Propagate live variables to predecessors. |
| for (Block predecessor in block.predecessors) { |
| int lengthBeforeChange = predecessor.liveOut.length; |
| predecessor.liveOut.addAll(block.liveIn); |
| if (!predecessor.inWorklist && |
| predecessor.liveOut.length != lengthBeforeChange) { |
| worklist.add(predecessor); |
| predecessor.inWorklist = true; |
| } |
| } |
| |
| // Propagate live variables to catch predecessors. |
| for (Block pred in block.catchPredecessors) { |
| bool changed = false; |
| int lengthBeforeChange = pred.liveOut.length; |
| pred.liveOut.addAll(block.liveIn); |
| if (pred.liveOut.length != lengthBeforeChange) { |
| changed = true; |
| } |
| // Assigning to a variable that is live in the catch block, does not |
| // kill the variable, because we conservatively assume that an exception |
| // could be thrown immediately before the assignment. |
| // Therefore remove live variables from all kill sets inside the try. |
| // Since the kill set is only used to subtract live variables from a |
| // set, the analysis remains monotone. |
| lengthBeforeChange = pred.kill.length; |
| pred.kill.removeAll(block.liveIn); |
| if (pred.kill.length != lengthBeforeChange) { |
| changed = true; |
| } |
| if (changed && !pred.inWorklist) { |
| worklist.add(pred); |
| pred.inWorklist = true; |
| } |
| } |
| } |
| } |
| } |
| |
| /// Based on liveness information, computes a map of variable substitutions to |
| /// merge variables. |
| /// |
| /// Constructs a register interference graph. This is an undirected graph of |
| /// variables, with an edge between two variables if they cannot be merged |
| /// (because they are live simultaneously). |
| /// |
| /// We then compute a graph coloring, where the color of a node denotes which |
| /// variable it will be substituted by. |
| Map<Variable, Variable> _computeRegisterAllocation(List<Block> blocks, |
| List<Variable> parameters, |
| PriorityPairs priority, |
| {bool minifying}) { |
| Map<Variable, Set<Variable>> interference = <Variable, Set<Variable>>{}; |
| |
| bool allowUnmotivatedMerge(Variable x, Variable y) { |
| if (minifying) return true; |
| // Do not allow merging temporaries with named variables if they are |
| // not connected by a phi. That would leads to confusing mergings like: |
| // var v0 = receiver.length; |
| // ==> |
| // receiver = receiver.length; |
| return x.element?.name == y.element?.name; |
| } |
| |
| bool allowPhiMerge(Variable x, Variable y) { |
| if (minifying) return true; |
| // Temporaries may be merged with a named variable if this eliminates a phi. |
| // The presence of the phi implies that the two variables can contain the |
| // same value, so it is not that confusing that they get the same name. |
| return x.element == null || |
| y.element == null || |
| x.element.name == y.element.name; |
| } |
| |
| Set<Variable> empty = new Set<Variable>(); |
| |
| // At the assignment to a variable x, add an edge to every variable that is |
| // live after the assignment (if it came from the same source variable). |
| for (Block block in blocks) { |
| // Track the live set while traversing the block. |
| Set<Variable> live = new Set<Variable>(); |
| for (Variable variable in block.liveOut) { |
| live.add(variable); |
| interference.putIfAbsent(variable, () => new Set<Variable>()); |
| } |
| // Get variables that are live at the catch block. |
| Set<Variable> liveCatch = block.catchBlock != null |
| ? block.catchBlock.liveIn |
| : empty; |
| // Add edges for each variable being assigned here. |
| for (VariableAccess access in block.accesses.reversed) { |
| Variable variable = access.variable; |
| interference.putIfAbsent(variable, () => new Set<Variable>()); |
| if (access.isRead) { |
| live.add(variable); |
| } else { |
| if (!liveCatch.contains(variable)) { |
| // Assignment to a variable that is not live in the catch block. |
| live.remove(variable); |
| } |
| for (Variable other in live) { |
| interference[variable].add(other); |
| interference[other].add(variable); |
| } |
| } |
| } |
| } |
| |
| // Sort the variables by descending degree. |
| // The most constrained variables will be assigned a color first. |
| List<Variable> variables = interference.keys.toList(); |
| variables.sort((x, y) => interference[y].length - interference[x].length); |
| |
| List<Variable> registers = <Variable>[]; |
| Map<Variable, Variable> subst = <Variable, Variable>{}; |
| |
| /// Called when [variable] has been assigned [target] as its register/color. |
| /// Will immediately try to satisfy its priority pairs by assigning the same |
| /// color the other half of each pair. |
| void searchPriorityPairs(Variable variable, Variable target) { |
| if (!priority.hasPriorityPairs(variable)) { |
| return; // Most variables (around 90%) do not have priority pairs. |
| } |
| List<Variable> worklist = <Variable>[variable]; |
| while (worklist.isNotEmpty) { |
| Variable v1 = worklist.removeLast(); |
| for (Variable v2 in priority.getPriorityPairsWith(v1)) { |
| // If v2 already has a color, we cannot change it. |
| if (subst.containsKey(v2)) continue; |
| |
| // Do not merge differently named variables. |
| if (!allowPhiMerge(v1, v2)) continue; |
| |
| // Ensure the graph coloring remains valid. If a neighbour of v2 already |
| // has the desired color, we cannot assign the same color to v2. |
| if (interference[v2].any((v3) => subst[v3] == target)) continue; |
| |
| subst[v2] = target; |
| target.element ??= v2.element; // Preserve the name. |
| worklist.add(v2); |
| } |
| } |
| } |
| |
| void assignRegister(Variable variable, Variable registerRepresentative) { |
| subst[variable] = registerRepresentative; |
| // Ensure this register is never assigned to a variable with another name. |
| // This also ensures that named variables keep their name when merged |
| // with a temporary. |
| registerRepresentative.element ??= variable.element; |
| searchPriorityPairs(variable, registerRepresentative); |
| } |
| |
| void assignNewRegister(Variable variable) { |
| registers.add(variable); |
| subst[variable] = variable; |
| searchPriorityPairs(variable, variable); |
| } |
| |
| // Parameters cannot be merged with each other. Ensure that they are not |
| // substituted. Other variables can still be substituted by a parameter. |
| for (Variable parameter in parameters) { |
| if (parameter.isCaptured) continue; |
| registers.add(parameter); |
| subst[parameter] = parameter; |
| } |
| |
| // Try to merge parameters with locals to eliminate phis. |
| for (Variable parameter in parameters) { |
| searchPriorityPairs(parameter, parameter); |
| } |
| |
| v1loop: |
| for (Variable v1 in variables) { |
| // Ignore if the variable has already been assigned a register. |
| if (subst.containsKey(v1)) continue; |
| |
| // Optimization: If there are no interference edges for this variable, |
| // find a color for it without copying the register list. |
| Set<Variable> interferenceSet = interference[v1]; |
| if (interferenceSet.isEmpty) { |
| // Use the first register where naming constraints allow the merge. |
| for (Variable v2 in registers) { |
| if (allowUnmotivatedMerge(v1, v2)) { |
| assignRegister(v1, v2); |
| continue v1loop; |
| } |
| } |
| // No register allows merging with this one, create a new register. |
| assignNewRegister(v1); |
| continue; |
| } |
| |
| // Find an unused color. |
| Set<Variable> potential = new Set<Variable>.from( |
| registers.where((v2) => allowUnmotivatedMerge(v1, v2))); |
| for (Variable v2 in interferenceSet) { |
| Variable v2subst = subst[v2]; |
| if (v2subst != null) { |
| potential.remove(v2subst); |
| if (potential.isEmpty) break; |
| } |
| } |
| |
| if (potential.isEmpty) { |
| // If no free color was found, add this variable as a new color. |
| assignNewRegister(v1); |
| } else { |
| assignRegister(v1, potential.first); |
| } |
| } |
| |
| return subst; |
| } |
| |
| /// Performs variable substitution and removes redundant assignments. |
| class SubstituteVariables extends RecursiveTransformer { |
| |
| Map<Variable, Variable> mapping; |
| |
| SubstituteVariables(this.mapping); |
| |
| Variable replaceRead(Variable variable) { |
| Variable w = mapping[variable]; |
| if (w == null) return variable; // Skip ignored variables. |
| w.readCount++; |
| variable.readCount--; |
| return w; |
| } |
| |
| Variable replaceWrite(Variable variable) { |
| Variable w = mapping[variable]; |
| if (w == null) return variable; // Skip ignored variables. |
| w.writeCount++; |
| variable.writeCount--; |
| return w; |
| } |
| |
| void apply(FunctionDefinition node) { |
| for (int i = 0; i < node.parameters.length; ++i) { |
| node.parameters[i] = replaceWrite(node.parameters[i]); |
| } |
| node.body = visitStatement(node.body); |
| } |
| |
| Expression visitVariableUse(VariableUse node) { |
| node.variable = replaceRead(node.variable); |
| return node; |
| } |
| |
| Expression visitAssign(Assign node) { |
| node.variable = replaceWrite(node.variable); |
| node.value = visitExpression(node.value); |
| |
| // Remove assignments of form "x := x" |
| if (node.value is VariableUse) { |
| VariableUse value = node.value; |
| if (value.variable == node.variable) { |
| --node.variable.writeCount; |
| return value; |
| } |
| } |
| |
| return node; |
| } |
| |
| Statement visitExpressionStatement(ExpressionStatement node) { |
| node.expression = visitExpression(node.expression); |
| node.next = visitStatement(node.next); |
| if (node.expression is VariableUse) { |
| VariableUse use = node.expression; |
| --use.variable.readCount; |
| return node.next; |
| } |
| return node; |
| } |
| } |