| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012, 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 part of ssa; | |
| 6 | |
| 7 /** | |
| 8 * The [LiveRange] class covers a range where an instruction is live. | |
| 9 */ | |
| 10 class LiveRange { | |
| 11 final int start; | |
| 12 // [end] is not final because it can be updated due to loops. | |
| 13 int end; | |
| 14 LiveRange(this.start, this.end) { | |
| 15 assert(start <= end); | |
| 16 } | |
| 17 | |
| 18 String toString() => '[$start $end['; | |
| 19 } | |
| 20 | |
| 21 /** | |
| 22 * The [LiveInterval] class contains the list of ranges where an | |
| 23 * instruction is live. | |
| 24 */ | |
| 25 class LiveInterval { | |
| 26 /** | |
| 27 * The id where the instruction is defined. | |
| 28 */ | |
| 29 int start; | |
| 30 final List<LiveRange> ranges; | |
| 31 LiveInterval() : ranges = <LiveRange>[]; | |
| 32 | |
| 33 // We want [HCheck] instructions to have the same name as the | |
| 34 // instruction it checks, so both instructions should share the same | |
| 35 // live ranges. | |
| 36 LiveInterval.forCheck(this.start, LiveInterval checkedInterval) | |
| 37 : ranges = checkedInterval.ranges; | |
| 38 | |
| 39 /** | |
| 40 * Update all ranges that are contained in [from, to[ to | |
| 41 * die at [to]. | |
| 42 */ | |
| 43 void loopUpdate(int from, int to) { | |
| 44 for (LiveRange range in ranges) { | |
| 45 if (from <= range.start && range.end < to) { | |
| 46 range.end = to; | |
| 47 } | |
| 48 } | |
| 49 } | |
| 50 | |
| 51 /** | |
| 52 * Add a new range to this interval. | |
| 53 */ | |
| 54 void add(LiveRange interval) { | |
| 55 ranges.add(interval); | |
| 56 } | |
| 57 | |
| 58 /** | |
| 59 * Returns true if one of the ranges of this interval dies at [at]. | |
| 60 */ | |
| 61 bool diesAt(int at) { | |
| 62 for (LiveRange range in ranges) { | |
| 63 if (range.end == at) return true; | |
| 64 } | |
| 65 return false; | |
| 66 } | |
| 67 | |
| 68 String toString() { | |
| 69 List<String> res = new List<String>(); | |
| 70 for (final interval in ranges) res.add(interval.toString()); | |
| 71 return '(${res.join(", ")})'; | |
| 72 } | |
| 73 } | |
| 74 | |
| 75 /** | |
| 76 * The [LiveEnvironment] class contains the liveIn set of a basic | |
| 77 * block. A liveIn set of a block contains the instructions that are | |
| 78 * live when entering that block. | |
| 79 */ | |
| 80 class LiveEnvironment { | |
| 81 /** | |
| 82 * The instruction id where the basic block starts. See | |
| 83 * [SsaLiveIntervalBuilder.instructionId]. | |
| 84 */ | |
| 85 int startId; | |
| 86 | |
| 87 /** | |
| 88 * The instruction id where the basic block ends. | |
| 89 */ | |
| 90 final int endId; | |
| 91 | |
| 92 /** | |
| 93 * Loop markers that will be updated once the loop header is | |
| 94 * visited. The liveIn set of the loop header will be merged into this | |
| 95 * environment. [loopMarkers] is a mapping from block header to the | |
| 96 * end instruction id of the loop exit block. | |
| 97 */ | |
| 98 final Map<HBasicBlock, int> loopMarkers; | |
| 99 | |
| 100 /** | |
| 101 * The instructions that are live in this basic block. The values of | |
| 102 * the map contain the instruction ids where the instructions die. | |
| 103 * It will be used when adding a range to the live interval of an | |
| 104 * instruction. | |
| 105 */ | |
| 106 final Map<HInstruction, int> liveInstructions; | |
| 107 | |
| 108 /** | |
| 109 * Map containing the live intervals of instructions. | |
| 110 */ | |
| 111 final Map<HInstruction, LiveInterval> liveIntervals; | |
| 112 | |
| 113 LiveEnvironment(this.liveIntervals, this.endId) | |
| 114 : liveInstructions = new Map<HInstruction, int>(), | |
| 115 loopMarkers = new Map<HBasicBlock, int>(); | |
| 116 | |
| 117 /** | |
| 118 * Remove an instruction from the liveIn set. This method also | |
| 119 * updates the live interval of [instruction] to contain the new | |
| 120 * range: [id, / id contained in [liveInstructions] /]. | |
| 121 */ | |
| 122 void remove(HInstruction instruction, int id) { | |
| 123 LiveInterval interval = liveIntervals.putIfAbsent( | |
| 124 instruction, () => new LiveInterval()); | |
| 125 int lastId = liveInstructions[instruction]; | |
| 126 // If [lastId] is null, then this instruction is not being used. | |
| 127 interval.add(new LiveRange(id, lastId == null ? id : lastId)); | |
| 128 // The instruction is defined at [id]. | |
| 129 interval.start = id; | |
| 130 liveInstructions.remove(instruction); | |
| 131 } | |
| 132 | |
| 133 /** | |
| 134 * Add [instruction] to the liveIn set. If the instruction is not | |
| 135 * already in the set, we save the id where it dies. | |
| 136 */ | |
| 137 void add(HInstruction instruction, int userId) { | |
| 138 // Note that we are visiting the graph in post-dominator order, so | |
| 139 // the first time we see a variable is when it dies. | |
| 140 liveInstructions.putIfAbsent(instruction, () => userId); | |
| 141 } | |
| 142 | |
| 143 /** | |
| 144 * Merge this environment with [other]. Update the end id of | |
| 145 * instructions in case they are different between this and [other]. | |
| 146 */ | |
| 147 void mergeWith(LiveEnvironment other) { | |
| 148 other.liveInstructions.forEach((HInstruction instruction, int existingId) { | |
| 149 // If both environments have the same instruction id of where | |
| 150 // [instruction] dies, there is no need to update the live | |
| 151 // interval of [instruction]. For example the if block and the | |
| 152 // else block have the same end id for an instruction that is | |
| 153 // being used in the join block and defined before the if/else. | |
| 154 if (existingId == endId) return; | |
| 155 LiveInterval range = liveIntervals.putIfAbsent( | |
| 156 instruction, () => new LiveInterval()); | |
| 157 range.add(new LiveRange(other.startId, existingId)); | |
| 158 liveInstructions[instruction] = endId; | |
| 159 }); | |
| 160 other.loopMarkers.forEach((k, v) { loopMarkers[k] = v; }); | |
| 161 } | |
| 162 | |
| 163 void addLoopMarker(HBasicBlock header, int id) { | |
| 164 assert(!loopMarkers.containsKey(header)); | |
| 165 loopMarkers[header] = id; | |
| 166 } | |
| 167 | |
| 168 void removeLoopMarker(HBasicBlock header) { | |
| 169 assert(loopMarkers.containsKey(header)); | |
| 170 loopMarkers.remove(header); | |
| 171 } | |
| 172 | |
| 173 bool get isEmpty => liveInstructions.isEmpty && loopMarkers.isEmpty; | |
| 174 bool contains(HInstruction instruction) => | |
| 175 liveInstructions.containsKey(instruction); | |
| 176 String toString() => liveInstructions.toString(); | |
| 177 } | |
| 178 | |
| 179 /** | |
| 180 * Builds the live intervals of each instruction. The algorithm visits | |
| 181 * the graph post-dominator tree to find the last uses of an | |
| 182 * instruction, and computes the liveIns of each basic block. | |
| 183 */ | |
| 184 class SsaLiveIntervalBuilder extends HBaseVisitor { | |
| 185 final Compiler compiler; | |
| 186 final Set<HInstruction> generateAtUseSite; | |
| 187 final Set<HInstruction> controlFlowOperators; | |
| 188 | |
| 189 /** | |
| 190 * A counter to assign start and end ids to live ranges. The initial | |
| 191 * value is not relevant. Note that instructionId goes downward to ease | |
| 192 * reasoning about live ranges (the first instruction of a graph has | |
| 193 * the lowest id). | |
| 194 */ | |
| 195 int instructionId = 0; | |
| 196 | |
| 197 /** | |
| 198 * The liveIns of basic blocks. | |
| 199 */ | |
| 200 final Map<HBasicBlock, LiveEnvironment> liveInstructions; | |
| 201 | |
| 202 /** | |
| 203 * The live intervals of instructions. | |
| 204 */ | |
| 205 final Map<HInstruction, LiveInterval> liveIntervals; | |
| 206 | |
| 207 SsaLiveIntervalBuilder( | |
| 208 this.compiler, this.generateAtUseSite, this.controlFlowOperators) | |
| 209 : liveInstructions = new Map<HBasicBlock, LiveEnvironment>(), | |
| 210 liveIntervals = new Map<HInstruction, LiveInterval>(); | |
| 211 | |
| 212 void visitGraph(HGraph graph) { | |
| 213 visitPostDominatorTree(graph); | |
| 214 if (!liveInstructions[graph.entry].isEmpty) { | |
| 215 compiler.internalError(CURRENT_ELEMENT_SPANNABLE, 'LiveIntervalBuilder.'); | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 void markInputsAsLiveInEnvironment(HInstruction instruction, | |
| 220 LiveEnvironment environment) { | |
| 221 for (int i = 0, len = instruction.inputs.length; i < len; i++) { | |
| 222 markAsLiveInEnvironment(instruction.inputs[i], environment); | |
| 223 } | |
| 224 } | |
| 225 | |
| 226 // Returns the non-HCheck instruction, or the last [HCheck] in the | |
| 227 // check chain that is not generate at use site. | |
| 228 // | |
| 229 // For example: | |
| 230 // | |
| 231 // t1 = GeneratedAtUseSite instruction | |
| 232 // t2 = check(t1) | |
| 233 // t3 = check(t2) | |
| 234 // t4 = use(t3) | |
| 235 // t5 = use(t3) | |
| 236 // t6 = use(t2) | |
| 237 // | |
| 238 // The t1 is generate-at-use site, and the live-range must thus be on t2 and | |
| 239 // not on the checked instruction t1. | |
| 240 // When looking for the checkedInstructionOrNonGenerateAtUseSite of t3 we must | |
| 241 // return t2. | |
| 242 HInstruction checkedInstructionOrNonGenerateAtUseSite(HCheck check) { | |
| 243 var checked = check.checkedInput; | |
| 244 while (checked is HCheck) { | |
| 245 HInstruction next = checked.checkedInput; | |
| 246 if (generateAtUseSite.contains(next)) break; | |
| 247 checked = next; | |
| 248 } | |
| 249 return checked; | |
| 250 } | |
| 251 | |
| 252 void markAsLiveInEnvironment(HInstruction instruction, | |
| 253 LiveEnvironment environment) { | |
| 254 if (generateAtUseSite.contains(instruction)) { | |
| 255 markInputsAsLiveInEnvironment(instruction, environment); | |
| 256 } else { | |
| 257 environment.add(instruction, instructionId); | |
| 258 // Special case the HCheck instruction to mark the actual | |
| 259 // checked instruction live. The checked instruction and the | |
| 260 // [HCheck] will share the same live ranges. | |
| 261 if (instruction is HCheck) { | |
| 262 HCheck check = instruction; | |
| 263 HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check); | |
| 264 if (!generateAtUseSite.contains(checked)) { | |
| 265 environment.add(checked, instructionId); | |
| 266 } | |
| 267 } | |
| 268 } | |
| 269 } | |
| 270 | |
| 271 void removeFromEnvironment(HInstruction instruction, | |
| 272 LiveEnvironment environment) { | |
| 273 environment.remove(instruction, instructionId); | |
| 274 // Special case the HCheck instruction to have the same live | |
| 275 // interval as the instruction it is checking. | |
| 276 if (instruction is HCheck) { | |
| 277 HCheck check = instruction; | |
| 278 HInstruction checked = checkedInstructionOrNonGenerateAtUseSite(check); | |
| 279 if (!generateAtUseSite.contains(checked)) { | |
| 280 liveIntervals.putIfAbsent(checked, () => new LiveInterval()); | |
| 281 // Unconditionally force the live ranges of the HCheck to | |
| 282 // be the live ranges of the instruction it is checking. | |
| 283 liveIntervals[instruction] = | |
| 284 new LiveInterval.forCheck(instructionId, liveIntervals[checked]); | |
| 285 } | |
| 286 } | |
| 287 } | |
| 288 | |
| 289 void visitBasicBlock(HBasicBlock block) { | |
| 290 LiveEnvironment environment = | |
| 291 new LiveEnvironment(liveIntervals, instructionId); | |
| 292 | |
| 293 // If the control flow instruction in this block will actually be | |
| 294 // inlined in the codegen in the join block, we need to make | |
| 295 // whatever is used by that control flow instruction as live in | |
| 296 // the join block. | |
| 297 if (controlFlowOperators.contains(block.last)) { | |
| 298 HIf ifInstruction = block.last; | |
| 299 HBasicBlock joinBlock = ifInstruction.joinBlock; | |
| 300 if (generateAtUseSite.contains(joinBlock.phis.first)) { | |
| 301 markInputsAsLiveInEnvironment( | |
| 302 ifInstruction, liveInstructions[joinBlock]); | |
| 303 } | |
| 304 } | |
| 305 | |
| 306 // Add to the environment the liveIn of its successor, as well as | |
| 307 // the inputs of the phis of the successor that flow from this block. | |
| 308 for (int i = 0; i < block.successors.length; i++) { | |
| 309 HBasicBlock successor = block.successors[i]; | |
| 310 LiveEnvironment successorEnv = liveInstructions[successor]; | |
| 311 if (successorEnv != null) { | |
| 312 environment.mergeWith(successorEnv); | |
| 313 } else { | |
| 314 environment.addLoopMarker(successor, instructionId); | |
| 315 } | |
| 316 | |
| 317 int index = successor.predecessors.indexOf(block); | |
| 318 for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) { | |
| 319 markAsLiveInEnvironment(phi.inputs[index], environment); | |
| 320 } | |
| 321 } | |
| 322 | |
| 323 // Iterate over all instructions to remove an instruction from the | |
| 324 // environment and add its inputs. | |
| 325 HInstruction instruction = block.last; | |
| 326 while (instruction != null) { | |
| 327 if (!generateAtUseSite.contains(instruction)) { | |
| 328 removeFromEnvironment(instruction, environment); | |
| 329 markInputsAsLiveInEnvironment(instruction, environment); | |
| 330 } | |
| 331 instructionId--; | |
| 332 instruction = instruction.previous; | |
| 333 } | |
| 334 | |
| 335 // We just remove the phis from the environment. The inputs of the | |
| 336 // phis will be put in the environment of the predecessors. | |
| 337 for (HPhi phi = block.phis.first; phi != null; phi = phi.next) { | |
| 338 if (!generateAtUseSite.contains(phi)) { | |
| 339 environment.remove(phi, instructionId); | |
| 340 } | |
| 341 } | |
| 342 | |
| 343 // Save the liveInstructions of that block. | |
| 344 environment.startId = instructionId + 1; | |
| 345 liveInstructions[block] = environment; | |
| 346 | |
| 347 // If the block is a loop header, we can remove the loop marker, | |
| 348 // because it will just recompute the loop phis. | |
| 349 // We also check if this loop header has any back edges. If not, | |
| 350 // we know there is no loop marker for it. | |
| 351 if (block.isLoopHeader() && block.predecessors.length > 1) { | |
| 352 updateLoopMarker(block); | |
| 353 } | |
| 354 } | |
| 355 | |
| 356 void updateLoopMarker(HBasicBlock header) { | |
| 357 LiveEnvironment env = liveInstructions[header]; | |
| 358 int lastId = env.loopMarkers[header]; | |
| 359 // Update all instructions that are liveIns in [header] to have a | |
| 360 // range that covers the loop. | |
| 361 env.liveInstructions.forEach((HInstruction instruction, int id) { | |
| 362 LiveInterval range = env.liveIntervals.putIfAbsent( | |
| 363 instruction, () => new LiveInterval()); | |
| 364 range.loopUpdate(env.startId, lastId); | |
| 365 env.liveInstructions[instruction] = lastId; | |
| 366 }); | |
| 367 | |
| 368 env.removeLoopMarker(header); | |
| 369 | |
| 370 // Update all liveIns set to contain the liveIns of [header]. | |
| 371 liveInstructions.forEach((HBasicBlock block, LiveEnvironment other) { | |
| 372 if (other.loopMarkers.containsKey(header)) { | |
| 373 env.liveInstructions.forEach((HInstruction instruction, int id) { | |
| 374 other.liveInstructions[instruction] = id; | |
| 375 }); | |
| 376 other.removeLoopMarker(header); | |
| 377 env.loopMarkers.forEach((k, v) { other.loopMarkers[k] = v; }); | |
| 378 } | |
| 379 }); | |
| 380 } | |
| 381 } | |
| 382 | |
| 383 /** | |
| 384 * Represents a copy from one instruction to another. The codegen | |
| 385 * also uses this class to represent a copy from one variable to | |
| 386 * another. | |
| 387 */ | |
| 388 class Copy { | |
| 389 final source; | |
| 390 final destination; | |
| 391 Copy(this.source, this.destination); | |
| 392 String toString() => '$destination <- $source'; | |
| 393 } | |
| 394 | |
| 395 /** | |
| 396 * A copy handler contains the copies that a basic block needs to do | |
| 397 * after executing all its instructions. | |
| 398 */ | |
| 399 class CopyHandler { | |
| 400 /** | |
| 401 * The copies from an instruction to a phi of the successor. | |
| 402 */ | |
| 403 final List<Copy> copies; | |
| 404 | |
| 405 /** | |
| 406 * Assignments from an instruction that does not need a name (e.g. a | |
| 407 * constant) to the phi of a successor. | |
| 408 */ | |
| 409 final List<Copy> assignments; | |
| 410 | |
| 411 CopyHandler() | |
| 412 : copies = new List<Copy>(), | |
| 413 assignments = new List<Copy>(); | |
| 414 | |
| 415 void addCopy(HInstruction source, HInstruction destination) { | |
| 416 copies.add(new Copy(source, destination)); | |
| 417 } | |
| 418 | |
| 419 void addAssignment(HInstruction source, HInstruction destination) { | |
| 420 assignments.add(new Copy(source, destination)); | |
| 421 } | |
| 422 | |
| 423 String toString() => 'Copies: $copies, assignments: $assignments'; | |
| 424 bool get isEmpty => copies.isEmpty && assignments.isEmpty; | |
| 425 } | |
| 426 | |
| 427 /** | |
| 428 * Contains the mapping between instructions and their names for code | |
| 429 * generation, as well as the [CopyHandler] for each basic block. | |
| 430 */ | |
| 431 class VariableNames { | |
| 432 final Map<HInstruction, String> ownName; | |
| 433 final Map<HBasicBlock, CopyHandler> copyHandlers; | |
| 434 | |
| 435 // Used to control heuristic that determines how local variables are declared. | |
| 436 final Set<String> allUsedNames; | |
| 437 /** | |
| 438 * Name that is used as a temporary to break cycles in | |
| 439 * parallel copies. We make sure this name is not being used | |
| 440 * anywhere by reserving it when we allocate names for instructions. | |
| 441 */ | |
| 442 final String swapTemp; | |
| 443 | |
| 444 String getSwapTemp() { | |
| 445 allUsedNames.add(swapTemp); | |
| 446 return swapTemp; | |
| 447 } | |
| 448 | |
| 449 VariableNames() | |
| 450 : ownName = new Map<HInstruction, String>(), | |
| 451 copyHandlers = new Map<HBasicBlock, CopyHandler>(), | |
| 452 allUsedNames = new Set<String>(), | |
| 453 swapTemp = 't0'; | |
| 454 | |
| 455 int get numberOfVariables => allUsedNames.length; | |
| 456 | |
| 457 String getName(HInstruction instruction) { | |
| 458 return ownName[instruction]; | |
| 459 } | |
| 460 | |
| 461 CopyHandler getCopyHandler(HBasicBlock block) { | |
| 462 return copyHandlers[block]; | |
| 463 } | |
| 464 | |
| 465 void addNameUsed(String name) { | |
| 466 allUsedNames.add(name); | |
| 467 } | |
| 468 | |
| 469 bool hasName(HInstruction instruction) => ownName.containsKey(instruction); | |
| 470 | |
| 471 void addCopy(HBasicBlock block, HInstruction source, HPhi destination) { | |
| 472 CopyHandler handler = | |
| 473 copyHandlers.putIfAbsent(block, () => new CopyHandler()); | |
| 474 handler.addCopy(source, destination); | |
| 475 } | |
| 476 | |
| 477 void addAssignment(HBasicBlock block, HInstruction source, HPhi destination) { | |
| 478 CopyHandler handler = | |
| 479 copyHandlers.putIfAbsent(block, () => new CopyHandler()); | |
| 480 handler.addAssignment(source, destination); | |
| 481 } | |
| 482 } | |
| 483 | |
| 484 /** | |
| 485 * Allocates variable names for instructions, making sure they don't collide. | |
| 486 */ | |
| 487 class VariableNamer { | |
| 488 final VariableNames names; | |
| 489 final Compiler compiler; | |
| 490 final Set<String> usedNames; | |
| 491 final List<String> freeTemporaryNames; | |
| 492 int temporaryIndex = 0; | |
| 493 static final RegExp regexp = new RegExp('t[0-9]+'); | |
| 494 | |
| 495 VariableNamer(LiveEnvironment environment, | |
| 496 this.names, | |
| 497 this.compiler) | |
| 498 : usedNames = new Set<String>(), | |
| 499 freeTemporaryNames = new List<String>() { | |
| 500 // [VariableNames.swapTemp] is used when there is a cycle in a copy handler. | |
| 501 // Therefore we make sure no one uses it. | |
| 502 usedNames.add(names.swapTemp); | |
| 503 | |
| 504 // All liveIns instructions must have a name at this point, so we | |
| 505 // add them to the list of used names. | |
| 506 environment.liveInstructions.forEach((HInstruction instruction, int index) { | |
| 507 String name = names.getName(instruction); | |
| 508 if (name != null) { | |
| 509 usedNames.add(name); | |
| 510 names.addNameUsed(name); | |
| 511 } | |
| 512 }); | |
| 513 } | |
| 514 | |
| 515 String allocateWithHint(String originalName) { | |
| 516 int i = 0; | |
| 517 JavaScriptBackend backend = compiler.backend; | |
| 518 String name = backend.namer.safeVariableName(originalName); | |
| 519 while (usedNames.contains(name)) { | |
| 520 name = backend.namer.safeVariableName('$originalName${i++}'); | |
| 521 } | |
| 522 return name; | |
| 523 } | |
| 524 | |
| 525 String allocateTemporary() { | |
| 526 while (!freeTemporaryNames.isEmpty) { | |
| 527 String name = freeTemporaryNames.removeLast(); | |
| 528 if (!usedNames.contains(name)) return name; | |
| 529 } | |
| 530 String name = 't${temporaryIndex++}'; | |
| 531 while (usedNames.contains(name)) name = 't${temporaryIndex++}'; | |
| 532 return name; | |
| 533 } | |
| 534 | |
| 535 HPhi firstPhiUserWithElement(HInstruction instruction) { | |
| 536 for (HInstruction user in instruction.usedBy) { | |
| 537 if (user is HPhi && user.sourceElement != null) { | |
| 538 return user; | |
| 539 } | |
| 540 } | |
| 541 return null; | |
| 542 } | |
| 543 | |
| 544 String allocateName(HInstruction instruction) { | |
| 545 String name; | |
| 546 if (instruction is HCheck) { | |
| 547 // Special case this instruction to use the name of its | |
| 548 // input if it has one. | |
| 549 var temp = instruction; | |
| 550 do { | |
| 551 temp = temp.checkedInput; | |
| 552 name = names.ownName[temp]; | |
| 553 } while (name == null && temp is HCheck); | |
| 554 if (name != null) return addAllocatedName(instruction, name); | |
| 555 } | |
| 556 | |
| 557 if (instruction.sourceElement != null) { | |
| 558 name = allocateWithHint(instruction.sourceElement.name); | |
| 559 } else { | |
| 560 // We could not find an element for the instruction. If the | |
| 561 // instruction is used by a phi, try to use the name of the phi. | |
| 562 // Otherwise, just allocate a temporary name. | |
| 563 HPhi phi = firstPhiUserWithElement(instruction); | |
| 564 if (phi != null) { | |
| 565 name = allocateWithHint(phi.sourceElement.name); | |
| 566 } else { | |
| 567 name = allocateTemporary(); | |
| 568 } | |
| 569 } | |
| 570 return addAllocatedName(instruction, name); | |
| 571 } | |
| 572 | |
| 573 String addAllocatedName(HInstruction instruction, String name) { | |
| 574 usedNames.add(name); | |
| 575 names.addNameUsed(name); | |
| 576 names.ownName[instruction] = name; | |
| 577 return name; | |
| 578 } | |
| 579 | |
| 580 /** | |
| 581 * Frees [instruction]'s name so it can be used for other instructions. | |
| 582 */ | |
| 583 void freeName(HInstruction instruction) { | |
| 584 String ownName = names.ownName[instruction]; | |
| 585 if (ownName != null) { | |
| 586 // We check if we have already looked for temporary names | |
| 587 // because if we haven't, chances are the temporary we allocate | |
| 588 // in this block can match a phi with the same name in the | |
| 589 // successor block. | |
| 590 if (temporaryIndex != 0 && regexp.hasMatch(ownName)) { | |
| 591 freeTemporaryNames.add(ownName); | |
| 592 } | |
| 593 usedNames.remove(ownName); | |
| 594 } | |
| 595 } | |
| 596 } | |
| 597 | |
| 598 /** | |
| 599 * Visits all blocks in the graph, sets names to instructions, and | |
| 600 * creates the [CopyHandler] for each block. This class needs to have | |
| 601 * the liveIns set as well as all the live intervals of instructions. | |
| 602 * It visits the graph in dominator order, so that at each entry of a | |
| 603 * block, the instructions in its liveIns set have names. | |
| 604 * | |
| 605 * When visiting a block, it goes through all instructions. For each | |
| 606 * instruction, it frees the names of the inputs that die at that | |
| 607 * instruction, and allocates a name to the instruction. For each phi, | |
| 608 * it adds a copy to the CopyHandler of the corresponding predecessor. | |
| 609 */ | |
| 610 class SsaVariableAllocator extends HBaseVisitor { | |
| 611 | |
| 612 final Compiler compiler; | |
| 613 final Map<HBasicBlock, LiveEnvironment> liveInstructions; | |
| 614 final Map<HInstruction, LiveInterval> liveIntervals; | |
| 615 final Set<HInstruction> generateAtUseSite; | |
| 616 | |
| 617 final VariableNames names; | |
| 618 | |
| 619 SsaVariableAllocator(this.compiler, | |
| 620 this.liveInstructions, | |
| 621 this.liveIntervals, | |
| 622 this.generateAtUseSite) | |
| 623 : this.names = new VariableNames(); | |
| 624 | |
| 625 void visitGraph(HGraph graph) { | |
| 626 visitDominatorTree(graph); | |
| 627 } | |
| 628 | |
| 629 void visitBasicBlock(HBasicBlock block) { | |
| 630 VariableNamer namer = new VariableNamer( | |
| 631 liveInstructions[block], names, compiler); | |
| 632 | |
| 633 block.forEachPhi((HPhi phi) { | |
| 634 handlePhi(phi, namer); | |
| 635 }); | |
| 636 | |
| 637 block.forEachInstruction((HInstruction instruction) { | |
| 638 handleInstruction(instruction, namer); | |
| 639 }); | |
| 640 } | |
| 641 | |
| 642 /** | |
| 643 * Returns whether [instruction] needs a name. Instructions that | |
| 644 * have no users or that are generated at use site do not need a name. | |
| 645 */ | |
| 646 bool needsName(instruction) { | |
| 647 if (instruction is HThis) return false; | |
| 648 if (instruction is HParameterValue) return true; | |
| 649 if (instruction.usedBy.isEmpty) return false; | |
| 650 if (generateAtUseSite.contains(instruction)) return false; | |
| 651 return !instruction.nonCheck().isCodeMotionInvariant(); | |
| 652 } | |
| 653 | |
| 654 /** | |
| 655 * Returns whether [instruction] dies at the instruction [at]. | |
| 656 */ | |
| 657 bool diesAt(HInstruction instruction, HInstruction at) { | |
| 658 LiveInterval atInterval = liveIntervals[at]; | |
| 659 LiveInterval instructionInterval = liveIntervals[instruction]; | |
| 660 int start = atInterval.start; | |
| 661 return instructionInterval.diesAt(start); | |
| 662 } | |
| 663 | |
| 664 void freeUsedNamesAt(HInstruction instruction, | |
| 665 HInstruction at, | |
| 666 VariableNamer namer) { | |
| 667 if (needsName(instruction)) { | |
| 668 if (diesAt(instruction, at)) { | |
| 669 namer.freeName(instruction); | |
| 670 } | |
| 671 } else if (generateAtUseSite.contains(instruction)) { | |
| 672 // If the instruction is generated at use site, then all its | |
| 673 // inputs may also die at [at]. | |
| 674 for (int i = 0, len = instruction.inputs.length; i < len; i++) { | |
| 675 HInstruction input = instruction.inputs[i]; | |
| 676 freeUsedNamesAt(input, at, namer); | |
| 677 } | |
| 678 } | |
| 679 } | |
| 680 | |
| 681 void handleInstruction(HInstruction instruction, VariableNamer namer) { | |
| 682 if (generateAtUseSite.contains(instruction)) { | |
| 683 assert(!liveIntervals.containsKey(instruction)); | |
| 684 return; | |
| 685 } | |
| 686 | |
| 687 for (int i = 0, len = instruction.inputs.length; i < len; i++) { | |
| 688 HInstruction input = instruction.inputs[i]; | |
| 689 freeUsedNamesAt(input, instruction, namer); | |
| 690 } | |
| 691 | |
| 692 if (needsName(instruction)) { | |
| 693 namer.allocateName(instruction); | |
| 694 } | |
| 695 } | |
| 696 | |
| 697 void handlePhi(HPhi phi, VariableNamer namer) { | |
| 698 if (!needsName(phi)) return; | |
| 699 | |
| 700 for (int i = 0; i < phi.inputs.length; i++) { | |
| 701 HInstruction input = phi.inputs[i]; | |
| 702 HBasicBlock predecessor = phi.block.predecessors[i]; | |
| 703 // A [HTypeKnown] instruction never has a name, but its checked | |
| 704 // input might, therefore we need to do a copy instead of an | |
| 705 // assignment. | |
| 706 while (input is HTypeKnown) input = input.inputs[0]; | |
| 707 if (!needsName(input)) { | |
| 708 names.addAssignment(predecessor, input, phi); | |
| 709 } else { | |
| 710 names.addCopy(predecessor, input, phi); | |
| 711 } | |
| 712 } | |
| 713 | |
| 714 namer.allocateName(phi); | |
| 715 } | |
| 716 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart