| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library tree_ir.optimization.variable_merger; | |
| 6 | |
| 7 import '../tree_ir_nodes.dart'; | |
| 8 import 'optimization.dart' show Pass; | |
| 9 | |
| 10 /// Merges variables based on liveness and source variable information. | |
| 11 /// | |
| 12 /// This phase cleans up artifacts introduced by the translation through CPS, | |
| 13 /// where each source variable is translated into several copies. The copies | |
| 14 /// are merged again when they are not live simultaneously. | |
| 15 class VariableMerger implements Pass { | |
| 16 String get passName => 'Variable merger'; | |
| 17 | |
| 18 final bool minifying; | |
| 19 | |
| 20 VariableMerger({this.minifying: false}); | |
| 21 | |
| 22 void rewrite(FunctionDefinition node) { | |
| 23 BlockGraphBuilder builder = new BlockGraphBuilder()..build(node); | |
| 24 _computeLiveness(builder.blocks); | |
| 25 PriorityPairs priority = new PriorityPairs()..build(node); | |
| 26 Map<Variable, Variable> subst = _computeRegisterAllocation( | |
| 27 builder.blocks, node.parameters, priority, | |
| 28 minifying: minifying); | |
| 29 new SubstituteVariables(subst).apply(node); | |
| 30 } | |
| 31 } | |
| 32 | |
| 33 /// A read or write access to a variable. | |
| 34 class VariableAccess { | |
| 35 Variable variable; | |
| 36 bool isRead; | |
| 37 bool get isWrite => !isRead; | |
| 38 | |
| 39 VariableAccess.read(this.variable) : isRead = true; | |
| 40 VariableAccess.write(this.variable) : isRead = false; | |
| 41 } | |
| 42 | |
| 43 /// Basic block in a control-flow graph. | |
| 44 class Block { | |
| 45 /// List of predecessors in the control-flow graph. | |
| 46 final List<Block> predecessors = <Block>[]; | |
| 47 | |
| 48 /// Entry to the catch block for the enclosing try, or `null`. | |
| 49 final Block catchBlock; | |
| 50 | |
| 51 /// List of nodes with this block as [catchBlock]. | |
| 52 final List<Block> catchPredecessors = <Block>[]; | |
| 53 | |
| 54 /// Sequence of read and write accesses in the block. | |
| 55 final List<VariableAccess> accesses = <VariableAccess>[]; | |
| 56 | |
| 57 /// Auxiliary fields used by the liveness analysis. | |
| 58 bool inWorklist = true; | |
| 59 Set<Variable> liveIn; | |
| 60 Set<Variable> liveOut = new Set<Variable>(); | |
| 61 Set<Variable> gen = new Set<Variable>(); | |
| 62 Set<Variable> kill = new Set<Variable>(); | |
| 63 | |
| 64 /// Adds a read operation to the block and updates gen/kill sets accordingly. | |
| 65 void addRead(Variable variable) { | |
| 66 // Operations are seen in forward order. | |
| 67 // If the read is not preceded by a write, then add it to the GEN set. | |
| 68 if (!kill.contains(variable)) { | |
| 69 gen.add(variable); | |
| 70 } | |
| 71 accesses.add(new VariableAccess.read(variable)); | |
| 72 } | |
| 73 | |
| 74 /// Adds a write operation to the block and updates gen/kill sets accordingly. | |
| 75 void addWrite(Variable variable) { | |
| 76 // If the write is not preceded by a read, then add it to the KILL set. | |
| 77 if (!gen.contains(variable)) { | |
| 78 kill.add(variable); | |
| 79 } | |
| 80 accesses.add(new VariableAccess.write(variable)); | |
| 81 } | |
| 82 | |
| 83 Block(this.catchBlock) { | |
| 84 if (catchBlock != null) { | |
| 85 catchBlock.catchPredecessors.add(this); | |
| 86 } | |
| 87 } | |
| 88 } | |
| 89 | |
| 90 /// Builds a control-flow graph suitable for performing liveness analysis. | |
| 91 class BlockGraphBuilder extends RecursiveVisitor { | |
| 92 Map<Label, Block> _jumpTarget = <Label, Block>{}; | |
| 93 Block _currentBlock; | |
| 94 List<Block> blocks = <Block>[]; | |
| 95 | |
| 96 /// Variables with an assignment that should be treated as final. | |
| 97 /// | |
| 98 /// Such variables cannot be merged with any other variables, so we exclude | |
| 99 /// them from the control-flow graph entirely. | |
| 100 Set<Variable> _ignoredVariables = new Set<Variable>(); | |
| 101 | |
| 102 void build(FunctionDefinition node) { | |
| 103 _currentBlock = newBlock(); | |
| 104 node.parameters.forEach(write); | |
| 105 visitStatement(node.body); | |
| 106 } | |
| 107 | |
| 108 /// Creates a new block with the current exception handler or [catchBlock] | |
| 109 /// if provided. | |
| 110 Block newBlock({Block catchBlock}) { | |
| 111 if (catchBlock == null && _currentBlock != null) { | |
| 112 catchBlock = _currentBlock.catchBlock; | |
| 113 } | |
| 114 Block block = new Block(catchBlock); | |
| 115 blocks.add(block); | |
| 116 return block; | |
| 117 } | |
| 118 | |
| 119 /// Starts a new block after the end of [block]. | |
| 120 void branchFrom(Block block, {Block catchBlock}) { | |
| 121 _currentBlock = newBlock(catchBlock: catchBlock)..predecessors.add(block); | |
| 122 } | |
| 123 | |
| 124 /// Starts a new block with the given blocks as predecessors. | |
| 125 void joinFrom(Block block1, Block block2) { | |
| 126 assert(block1.catchBlock == block2.catchBlock); | |
| 127 _currentBlock = newBlock(catchBlock: block1.catchBlock); | |
| 128 _currentBlock.predecessors.add(block1); | |
| 129 _currentBlock.predecessors.add(block2); | |
| 130 } | |
| 131 | |
| 132 /// Called when reading from [variable]. | |
| 133 /// | |
| 134 /// Appends a read operation to the current basic block. | |
| 135 void read(Variable variable) { | |
| 136 if (variable.isCaptured) return; | |
| 137 if (_ignoredVariables.contains(variable)) return; | |
| 138 _currentBlock.addRead(variable); | |
| 139 } | |
| 140 | |
| 141 /// Called when writing to [variable]. | |
| 142 /// | |
| 143 /// Appends a write operation to the current basic block. | |
| 144 void write(Variable variable) { | |
| 145 if (variable.isCaptured) return; | |
| 146 if (_ignoredVariables.contains(variable)) return; | |
| 147 _currentBlock.addWrite(variable); | |
| 148 } | |
| 149 | |
| 150 /// Called to indicate that [variable] should not be merged, and therefore | |
| 151 /// be excluded from the control-flow graph. | |
| 152 /// Subsequent calls to [read] and [write] will ignore it. | |
| 153 void ignoreVariable(Variable variable) { | |
| 154 _ignoredVariables.add(variable); | |
| 155 } | |
| 156 | |
| 157 visitVariableUse(VariableUse node) { | |
| 158 read(node.variable); | |
| 159 } | |
| 160 | |
| 161 visitAssign(Assign node) { | |
| 162 visitExpression(node.value); | |
| 163 write(node.variable); | |
| 164 } | |
| 165 | |
| 166 visitIf(If node) { | |
| 167 visitExpression(node.condition); | |
| 168 Block afterCondition = _currentBlock; | |
| 169 branchFrom(afterCondition); | |
| 170 visitStatement(node.thenStatement); | |
| 171 Block afterThen = _currentBlock; | |
| 172 branchFrom(afterCondition); | |
| 173 visitStatement(node.elseStatement); | |
| 174 joinFrom(_currentBlock, afterThen); | |
| 175 } | |
| 176 | |
| 177 visitLabeledStatement(LabeledStatement node) { | |
| 178 Block join = _jumpTarget[node.label] = newBlock(); | |
| 179 visitStatement(node.body); // visitBreak will add predecessors to join. | |
| 180 _currentBlock = join; | |
| 181 visitStatement(node.next); | |
| 182 } | |
| 183 | |
| 184 visitBreak(Break node) { | |
| 185 _jumpTarget[node.target].predecessors.add(_currentBlock); | |
| 186 } | |
| 187 | |
| 188 visitContinue(Continue node) { | |
| 189 _jumpTarget[node.target].predecessors.add(_currentBlock); | |
| 190 } | |
| 191 | |
| 192 visitWhileTrue(WhileTrue node) { | |
| 193 Block join = _jumpTarget[node.label] = newBlock(); | |
| 194 join.predecessors.add(_currentBlock); | |
| 195 _currentBlock = join; | |
| 196 visitStatement(node.body); // visitContinue will add predecessors to join. | |
| 197 } | |
| 198 | |
| 199 visitFor(For node) { | |
| 200 Block entry = _currentBlock; | |
| 201 _currentBlock = _jumpTarget[node.label] = newBlock(); | |
| 202 node.updates.forEach(visitExpression); | |
| 203 joinFrom(entry, _currentBlock); | |
| 204 visitExpression(node.condition); | |
| 205 Block afterCondition = _currentBlock; | |
| 206 branchFrom(afterCondition); | |
| 207 visitStatement(node.body); // visitContinue will add predecessors to join. | |
| 208 branchFrom(afterCondition); | |
| 209 visitStatement(node.next); | |
| 210 } | |
| 211 | |
| 212 visitTry(Try node) { | |
| 213 Block outerCatchBlock = _currentBlock.catchBlock; | |
| 214 Block catchBlock = newBlock(catchBlock: outerCatchBlock); | |
| 215 branchFrom(_currentBlock, catchBlock: catchBlock); | |
| 216 visitStatement(node.tryBody); | |
| 217 Block afterTry = _currentBlock; | |
| 218 _currentBlock = catchBlock; | |
| 219 // Catch parameters cannot be hoisted to the top of the function, so to | |
| 220 // avoid complications with scoping, we do not attempt to merge them. | |
| 221 node.catchParameters.forEach(ignoreVariable); | |
| 222 visitStatement(node.catchBody); | |
| 223 Block afterCatch = _currentBlock; | |
| 224 _currentBlock = newBlock(catchBlock: outerCatchBlock); | |
| 225 _currentBlock.predecessors.add(afterCatch); | |
| 226 _currentBlock.predecessors.add(afterTry); | |
| 227 } | |
| 228 | |
| 229 visitConditional(Conditional node) { | |
| 230 visitExpression(node.condition); | |
| 231 Block afterCondition = _currentBlock; | |
| 232 branchFrom(afterCondition); | |
| 233 visitExpression(node.thenExpression); | |
| 234 Block afterThen = _currentBlock; | |
| 235 branchFrom(afterCondition); | |
| 236 visitExpression(node.elseExpression); | |
| 237 joinFrom(_currentBlock, afterThen); | |
| 238 } | |
| 239 | |
| 240 visitLogicalOperator(LogicalOperator node) { | |
| 241 visitExpression(node.left); | |
| 242 Block afterLeft = _currentBlock; | |
| 243 branchFrom(afterLeft); | |
| 244 visitExpression(node.right); | |
| 245 joinFrom(_currentBlock, afterLeft); | |
| 246 } | |
| 247 } | |
| 248 | |
| 249 /// Collects prioritized variable pairs -- pairs that lead to significant code | |
| 250 /// reduction if merged into one variable. | |
| 251 /// | |
| 252 /// These arise from moving assigments `v1 = v2`, and compoundable assignments | |
| 253 /// `v1 = v2 [+] E` where [+] is a compoundable operator. | |
| 254 // | |
| 255 // TODO(asgerf): We could have a more fine-grained priority level. All pairs | |
| 256 // are treated as equally important, but some pairs can eliminate more than | |
| 257 // one assignment. | |
| 258 // Also, some assignments are more important to remove than others, as they | |
| 259 // can block a later optimization, such rewriting a loop, or removing the | |
| 260 // 'else' part of an 'if'. | |
| 261 // | |
| 262 class PriorityPairs extends RecursiveVisitor { | |
| 263 final Map<Variable, List<Variable>> _priority = <Variable, List<Variable>>{}; | |
| 264 | |
| 265 void build(FunctionDefinition node) { | |
| 266 visitStatement(node.body); | |
| 267 } | |
| 268 | |
| 269 void _prioritize(Variable x, Variable y) { | |
| 270 _priority.putIfAbsent(x, () => new List<Variable>()).add(y); | |
| 271 _priority.putIfAbsent(y, () => new List<Variable>()).add(x); | |
| 272 } | |
| 273 | |
| 274 visitAssign(Assign node) { | |
| 275 super.visitAssign(node); | |
| 276 Expression value = node.value; | |
| 277 if (value is VariableUse) { | |
| 278 _prioritize(node.variable, value.variable); | |
| 279 } else if (value is ApplyBuiltinOperator && | |
| 280 isCompoundableOperator(value.operator) && | |
| 281 value.arguments[0] is VariableUse) { | |
| 282 VariableUse use = value.arguments[0]; | |
| 283 _prioritize(node.variable, use.variable); | |
| 284 } | |
| 285 } | |
| 286 | |
| 287 /// Returns the other half of every priority pair containing [variable]. | |
| 288 List<Variable> getPriorityPairsWith(Variable variable) { | |
| 289 return _priority[variable] ?? const <Variable>[]; | |
| 290 } | |
| 291 | |
| 292 bool hasPriorityPairs(Variable variable) { | |
| 293 return _priority.containsKey(variable); | |
| 294 } | |
| 295 } | |
| 296 | |
| 297 /// Computes liveness information of the given control-flow graph. | |
| 298 /// | |
| 299 /// The results are stored in [Block.liveIn] and [Block.liveOut]. | |
| 300 void _computeLiveness(List<Block> blocks) { | |
| 301 // We use a LIFO queue as worklist. Blocks are given in AST order, so by | |
| 302 // inserting them in this order, we initially visit them backwards, which | |
| 303 // is a good ordering. | |
| 304 // The choice of LIFO for re-inserted blocks is currently arbitrary, | |
| 305 List<Block> worklist = new List<Block>.from(blocks); | |
| 306 while (!worklist.isEmpty) { | |
| 307 Block block = worklist.removeLast(); | |
| 308 block.inWorklist = false; | |
| 309 | |
| 310 bool changed = false; | |
| 311 | |
| 312 // The liveIn set is computed as: | |
| 313 // | |
| 314 // liveIn = (liveOut - kill) + gen | |
| 315 // | |
| 316 // We do the computation in two steps: | |
| 317 // | |
| 318 // 1. liveIn = gen | |
| 319 // 2. liveIn += (liveOut - kill) | |
| 320 // | |
| 321 // However, since liveIn only grows, and gen never changes, we only have | |
| 322 // to do the first step at the first iteration. Moreover, the gen set is | |
| 323 // not needed anywhere else, so we don't even need to copy it. | |
| 324 if (block.liveIn == null) { | |
| 325 block.liveIn = block.gen; | |
| 326 block.gen = null; | |
| 327 changed = true; | |
| 328 } | |
| 329 | |
| 330 // liveIn += (liveOut - kill) | |
| 331 for (Variable variable in block.liveOut) { | |
| 332 if (!block.kill.contains(variable)) { | |
| 333 if (block.liveIn.add(variable)) { | |
| 334 changed = true; | |
| 335 } | |
| 336 } | |
| 337 } | |
| 338 | |
| 339 // If anything changed, propagate liveness backwards. | |
| 340 if (changed) { | |
| 341 // Propagate live variables to predecessors. | |
| 342 for (Block predecessor in block.predecessors) { | |
| 343 int lengthBeforeChange = predecessor.liveOut.length; | |
| 344 predecessor.liveOut.addAll(block.liveIn); | |
| 345 if (!predecessor.inWorklist && | |
| 346 predecessor.liveOut.length != lengthBeforeChange) { | |
| 347 worklist.add(predecessor); | |
| 348 predecessor.inWorklist = true; | |
| 349 } | |
| 350 } | |
| 351 | |
| 352 // Propagate live variables to catch predecessors. | |
| 353 for (Block pred in block.catchPredecessors) { | |
| 354 bool changed = false; | |
| 355 int lengthBeforeChange = pred.liveOut.length; | |
| 356 pred.liveOut.addAll(block.liveIn); | |
| 357 if (pred.liveOut.length != lengthBeforeChange) { | |
| 358 changed = true; | |
| 359 } | |
| 360 // Assigning to a variable that is live in the catch block, does not | |
| 361 // kill the variable, because we conservatively assume that an exception | |
| 362 // could be thrown immediately before the assignment. | |
| 363 // Therefore remove live variables from all kill sets inside the try. | |
| 364 // Since the kill set is only used to subtract live variables from a | |
| 365 // set, the analysis remains monotone. | |
| 366 lengthBeforeChange = pred.kill.length; | |
| 367 pred.kill.removeAll(block.liveIn); | |
| 368 if (pred.kill.length != lengthBeforeChange) { | |
| 369 changed = true; | |
| 370 } | |
| 371 if (changed && !pred.inWorklist) { | |
| 372 worklist.add(pred); | |
| 373 pred.inWorklist = true; | |
| 374 } | |
| 375 } | |
| 376 } | |
| 377 } | |
| 378 } | |
| 379 | |
| 380 /// Based on liveness information, computes a map of variable substitutions to | |
| 381 /// merge variables. | |
| 382 /// | |
| 383 /// Constructs a register interference graph. This is an undirected graph of | |
| 384 /// variables, with an edge between two variables if they cannot be merged | |
| 385 /// (because they are live simultaneously). | |
| 386 /// | |
| 387 /// We then compute a graph coloring, where the color of a node denotes which | |
| 388 /// variable it will be substituted by. | |
| 389 Map<Variable, Variable> _computeRegisterAllocation( | |
| 390 List<Block> blocks, List<Variable> parameters, PriorityPairs priority, | |
| 391 {bool minifying}) { | |
| 392 Map<Variable, Set<Variable>> interference = <Variable, Set<Variable>>{}; | |
| 393 | |
| 394 bool allowUnmotivatedMerge(Variable x, Variable y) { | |
| 395 if (minifying) return true; | |
| 396 // Do not allow merging temporaries with named variables if they are | |
| 397 // not connected by a phi. That would leads to confusing mergings like: | |
| 398 // var v0 = receiver.length; | |
| 399 // ==> | |
| 400 // receiver = receiver.length; | |
| 401 return x.element?.name == y.element?.name; | |
| 402 } | |
| 403 | |
| 404 bool allowPhiMerge(Variable x, Variable y) { | |
| 405 if (minifying) return true; | |
| 406 // Temporaries may be merged with a named variable if this eliminates a phi. | |
| 407 // The presence of the phi implies that the two variables can contain the | |
| 408 // same value, so it is not that confusing that they get the same name. | |
| 409 return x.element == null || | |
| 410 y.element == null || | |
| 411 x.element.name == y.element.name; | |
| 412 } | |
| 413 | |
| 414 Set<Variable> empty = new Set<Variable>(); | |
| 415 | |
| 416 // At the assignment to a variable x, add an edge to every variable that is | |
| 417 // live after the assignment (if it came from the same source variable). | |
| 418 for (Block block in blocks) { | |
| 419 // Track the live set while traversing the block. | |
| 420 Set<Variable> live = new Set<Variable>(); | |
| 421 for (Variable variable in block.liveOut) { | |
| 422 live.add(variable); | |
| 423 interference.putIfAbsent(variable, () => new Set<Variable>()); | |
| 424 } | |
| 425 // Get variables that are live at the catch block. | |
| 426 Set<Variable> liveCatch = | |
| 427 block.catchBlock != null ? block.catchBlock.liveIn : empty; | |
| 428 // Add edges for each variable being assigned here. | |
| 429 for (VariableAccess access in block.accesses.reversed) { | |
| 430 Variable variable = access.variable; | |
| 431 interference.putIfAbsent(variable, () => new Set<Variable>()); | |
| 432 if (access.isRead) { | |
| 433 live.add(variable); | |
| 434 } else { | |
| 435 if (!liveCatch.contains(variable)) { | |
| 436 // Assignment to a variable that is not live in the catch block. | |
| 437 live.remove(variable); | |
| 438 } | |
| 439 for (Variable other in live) { | |
| 440 interference[variable].add(other); | |
| 441 interference[other].add(variable); | |
| 442 } | |
| 443 } | |
| 444 } | |
| 445 } | |
| 446 | |
| 447 // Sort the variables by descending degree. | |
| 448 // The most constrained variables will be assigned a color first. | |
| 449 List<Variable> variables = interference.keys.toList(); | |
| 450 variables.sort((x, y) => interference[y].length - interference[x].length); | |
| 451 | |
| 452 List<Variable> registers = <Variable>[]; | |
| 453 Map<Variable, Variable> subst = <Variable, Variable>{}; | |
| 454 | |
| 455 /// Called when [variable] has been assigned [target] as its register/color. | |
| 456 /// Will immediately try to satisfy its priority pairs by assigning the same | |
| 457 /// color the other half of each pair. | |
| 458 void searchPriorityPairs(Variable variable, Variable target) { | |
| 459 if (!priority.hasPriorityPairs(variable)) { | |
| 460 return; // Most variables (around 90%) do not have priority pairs. | |
| 461 } | |
| 462 List<Variable> worklist = <Variable>[variable]; | |
| 463 while (worklist.isNotEmpty) { | |
| 464 Variable v1 = worklist.removeLast(); | |
| 465 for (Variable v2 in priority.getPriorityPairsWith(v1)) { | |
| 466 // If v2 already has a color, we cannot change it. | |
| 467 if (subst.containsKey(v2)) continue; | |
| 468 | |
| 469 // Do not merge differently named variables. | |
| 470 if (!allowPhiMerge(v1, v2)) continue; | |
| 471 | |
| 472 // Ensure the graph coloring remains valid. If a neighbour of v2 already | |
| 473 // has the desired color, we cannot assign the same color to v2. | |
| 474 if (interference[v2].any((v3) => subst[v3] == target)) continue; | |
| 475 | |
| 476 subst[v2] = target; | |
| 477 target.element ??= v2.element; // Preserve the name. | |
| 478 worklist.add(v2); | |
| 479 } | |
| 480 } | |
| 481 } | |
| 482 | |
| 483 void assignRegister(Variable variable, Variable registerRepresentative) { | |
| 484 subst[variable] = registerRepresentative; | |
| 485 // Ensure this register is never assigned to a variable with another name. | |
| 486 // This also ensures that named variables keep their name when merged | |
| 487 // with a temporary. | |
| 488 registerRepresentative.element ??= variable.element; | |
| 489 searchPriorityPairs(variable, registerRepresentative); | |
| 490 } | |
| 491 | |
| 492 void assignNewRegister(Variable variable) { | |
| 493 registers.add(variable); | |
| 494 subst[variable] = variable; | |
| 495 searchPriorityPairs(variable, variable); | |
| 496 } | |
| 497 | |
| 498 // Parameters cannot be merged with each other. Ensure that they are not | |
| 499 // substituted. Other variables can still be substituted by a parameter. | |
| 500 for (Variable parameter in parameters) { | |
| 501 if (parameter.isCaptured) continue; | |
| 502 registers.add(parameter); | |
| 503 subst[parameter] = parameter; | |
| 504 } | |
| 505 | |
| 506 // Try to merge parameters with locals to eliminate phis. | |
| 507 for (Variable parameter in parameters) { | |
| 508 searchPriorityPairs(parameter, parameter); | |
| 509 } | |
| 510 | |
| 511 v1loop: for (Variable v1 in variables) { | |
| 512 // Ignore if the variable has already been assigned a register. | |
| 513 if (subst.containsKey(v1)) continue; | |
| 514 | |
| 515 // Optimization: If there are no interference edges for this variable, | |
| 516 // find a color for it without copying the register list. | |
| 517 Set<Variable> interferenceSet = interference[v1]; | |
| 518 if (interferenceSet.isEmpty) { | |
| 519 // Use the first register where naming constraints allow the merge. | |
| 520 for (Variable v2 in registers) { | |
| 521 if (allowUnmotivatedMerge(v1, v2)) { | |
| 522 assignRegister(v1, v2); | |
| 523 continue v1loop; | |
| 524 } | |
| 525 } | |
| 526 // No register allows merging with this one, create a new register. | |
| 527 assignNewRegister(v1); | |
| 528 continue; | |
| 529 } | |
| 530 | |
| 531 // Find an unused color. | |
| 532 Set<Variable> potential = new Set<Variable>.from( | |
| 533 registers.where((v2) => allowUnmotivatedMerge(v1, v2))); | |
| 534 for (Variable v2 in interferenceSet) { | |
| 535 Variable v2subst = subst[v2]; | |
| 536 if (v2subst != null) { | |
| 537 potential.remove(v2subst); | |
| 538 if (potential.isEmpty) break; | |
| 539 } | |
| 540 } | |
| 541 | |
| 542 if (potential.isEmpty) { | |
| 543 // If no free color was found, add this variable as a new color. | |
| 544 assignNewRegister(v1); | |
| 545 } else { | |
| 546 assignRegister(v1, potential.first); | |
| 547 } | |
| 548 } | |
| 549 | |
| 550 return subst; | |
| 551 } | |
| 552 | |
| 553 /// Performs variable substitution and removes redundant assignments. | |
| 554 class SubstituteVariables extends RecursiveTransformer { | |
| 555 Map<Variable, Variable> mapping; | |
| 556 | |
| 557 SubstituteVariables(this.mapping); | |
| 558 | |
| 559 Variable replaceRead(Variable variable) { | |
| 560 Variable w = mapping[variable]; | |
| 561 if (w == null) return variable; // Skip ignored variables. | |
| 562 w.readCount++; | |
| 563 variable.readCount--; | |
| 564 return w; | |
| 565 } | |
| 566 | |
| 567 Variable replaceWrite(Variable variable) { | |
| 568 Variable w = mapping[variable]; | |
| 569 if (w == null) return variable; // Skip ignored variables. | |
| 570 w.writeCount++; | |
| 571 variable.writeCount--; | |
| 572 return w; | |
| 573 } | |
| 574 | |
| 575 void apply(FunctionDefinition node) { | |
| 576 for (int i = 0; i < node.parameters.length; ++i) { | |
| 577 node.parameters[i] = replaceWrite(node.parameters[i]); | |
| 578 } | |
| 579 node.body = visitStatement(node.body); | |
| 580 } | |
| 581 | |
| 582 Expression visitVariableUse(VariableUse node) { | |
| 583 node.variable = replaceRead(node.variable); | |
| 584 return node; | |
| 585 } | |
| 586 | |
| 587 Expression visitAssign(Assign node) { | |
| 588 node.variable = replaceWrite(node.variable); | |
| 589 node.value = visitExpression(node.value); | |
| 590 | |
| 591 // Remove assignments of form "x := x" | |
| 592 if (node.value is VariableUse) { | |
| 593 VariableUse value = node.value; | |
| 594 if (value.variable == node.variable) { | |
| 595 --node.variable.writeCount; | |
| 596 return value; | |
| 597 } | |
| 598 } | |
| 599 | |
| 600 return node; | |
| 601 } | |
| 602 | |
| 603 Statement visitExpressionStatement(ExpressionStatement node) { | |
| 604 node.expression = visitExpression(node.expression); | |
| 605 node.next = visitStatement(node.next); | |
| 606 if (node.expression is VariableUse) { | |
| 607 VariableUse use = node.expression; | |
| 608 --use.variable.readCount; | |
| 609 return node.next; | |
| 610 } | |
| 611 return node; | |
| 612 } | |
| 613 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
