| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, 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 dart2js.cps_ir.shrinking_reductions; | |
| 6 | |
| 7 import 'cps_ir_nodes.dart'; | |
| 8 import 'optimizers.dart'; | |
| 9 | |
| 10 /** | |
| 11 * [ShrinkingReducer] applies shrinking reductions to CPS terms as described | |
| 12 * in 'Compiling with Continuations, Continued' by Andrew Kennedy. | |
| 13 */ | |
| 14 class ShrinkingReducer extends Pass { | |
| 15 String get passName => 'Shrinking reductions'; | |
| 16 | |
| 17 final List<_ReductionTask> _worklist = new List<_ReductionTask>(); | |
| 18 | |
| 19 /// Applies shrinking reductions to root, mutating root in the process. | |
| 20 @override | |
| 21 void rewrite(FunctionDefinition root) { | |
| 22 _RedexVisitor redexVisitor = new _RedexVisitor(_worklist); | |
| 23 | |
| 24 // Sweep over the term, collecting redexes into the worklist. | |
| 25 redexVisitor.visit(root); | |
| 26 | |
| 27 _iterateWorklist(); | |
| 28 } | |
| 29 | |
| 30 void _iterateWorklist() { | |
| 31 while (_worklist.isNotEmpty) { | |
| 32 _ReductionTask task = _worklist.removeLast(); | |
| 33 _processTask(task); | |
| 34 } | |
| 35 } | |
| 36 | |
| 37 /// Call instead of [_iterateWorklist] to check at every step that no | |
| 38 /// redex was missed. | |
| 39 void _debugWorklist(FunctionDefinition root) { | |
| 40 while (_worklist.isNotEmpty) { | |
| 41 _ReductionTask task = _worklist.removeLast(); | |
| 42 String irBefore = | |
| 43 root.debugString({task.node: '${task.kind} applied here'}); | |
| 44 _processTask(task); | |
| 45 Set seenRedexes = _worklist.where(isValidTask).toSet(); | |
| 46 Set actualRedexes = (new _RedexVisitor([])..visit(root)).worklist.toSet(); | |
| 47 if (!seenRedexes.containsAll(actualRedexes)) { | |
| 48 _ReductionTask missedTask = | |
| 49 actualRedexes.firstWhere((x) => !seenRedexes.contains(x)); | |
| 50 print('\nBEFORE $task:\n'); | |
| 51 print(irBefore); | |
| 52 print('\nAFTER $task:\n'); | |
| 53 root.debugPrint({missedTask.node: 'MISSED ${missedTask.kind}'}); | |
| 54 throw 'Missed $missedTask after processing $task'; | |
| 55 } | |
| 56 } | |
| 57 } | |
| 58 | |
| 59 bool isValidTask(_ReductionTask task) { | |
| 60 switch (task.kind) { | |
| 61 case _ReductionKind.DEAD_VAL: | |
| 62 return _isDeadVal(task.node); | |
| 63 case _ReductionKind.DEAD_CONT: | |
| 64 return _isDeadCont(task.node); | |
| 65 case _ReductionKind.BETA_CONT_LIN: | |
| 66 return _isBetaContLin(task.node); | |
| 67 case _ReductionKind.ETA_CONT: | |
| 68 return _isEtaCont(task.node); | |
| 69 case _ReductionKind.DEAD_PARAMETER: | |
| 70 return _isDeadParameter(task.node); | |
| 71 case _ReductionKind.BRANCH: | |
| 72 return _isBranchRedex(task.node); | |
| 73 } | |
| 74 } | |
| 75 | |
| 76 /// Removes the given node from the CPS graph, replacing it with its body | |
| 77 /// and marking it as deleted. The node's parent must be a [[InteriorNode]]. | |
| 78 void _removeNode(InteriorNode node) { | |
| 79 Node body = node.body; | |
| 80 InteriorNode parent = node.parent; | |
| 81 assert(parent.body == node); | |
| 82 | |
| 83 body.parent = parent; | |
| 84 parent.body = body; | |
| 85 node.parent = null; | |
| 86 | |
| 87 // The removed node could be the last node between a continuation and | |
| 88 // an InvokeContinuation in the body. | |
| 89 if (parent is Continuation) { | |
| 90 _checkEtaCont(parent); | |
| 91 _checkUselessBranchTarget(parent); | |
| 92 } | |
| 93 } | |
| 94 | |
| 95 /// Remove a given continuation from the CPS graph. The LetCont itself is | |
| 96 /// removed if the given continuation is the only binding. | |
| 97 void _removeContinuation(Continuation cont) { | |
| 98 LetCont parent = cont.parent; | |
| 99 if (parent.continuations.length == 1) { | |
| 100 _removeNode(parent); | |
| 101 } else { | |
| 102 parent.continuations.remove(cont); | |
| 103 } | |
| 104 cont.parent = null; | |
| 105 } | |
| 106 | |
| 107 void _processTask(_ReductionTask task) { | |
| 108 // Skip tasks for deleted nodes. | |
| 109 if (task.node.parent == null) { | |
| 110 return; | |
| 111 } | |
| 112 | |
| 113 switch (task.kind) { | |
| 114 case _ReductionKind.DEAD_VAL: | |
| 115 _reduceDeadVal(task); | |
| 116 break; | |
| 117 case _ReductionKind.DEAD_CONT: | |
| 118 _reduceDeadCont(task); | |
| 119 break; | |
| 120 case _ReductionKind.BETA_CONT_LIN: | |
| 121 _reduceBetaContLin(task); | |
| 122 break; | |
| 123 case _ReductionKind.ETA_CONT: | |
| 124 _reduceEtaCont(task); | |
| 125 break; | |
| 126 case _ReductionKind.DEAD_PARAMETER: | |
| 127 _reduceDeadParameter(task); | |
| 128 break; | |
| 129 case _ReductionKind.BRANCH: | |
| 130 _reduceBranch(task); | |
| 131 break; | |
| 132 } | |
| 133 } | |
| 134 | |
| 135 /// Applies the dead-val reduction: | |
| 136 /// letprim x = V in E -> E (x not free in E). | |
| 137 void _reduceDeadVal(_ReductionTask task) { | |
| 138 if (_isRemoved(task.node)) return; | |
| 139 assert(_isDeadVal(task.node)); | |
| 140 | |
| 141 LetPrim deadLet = task.node; | |
| 142 Primitive deadPrim = deadLet.primitive; | |
| 143 assert(deadPrim.hasNoRefinedUses); | |
| 144 // The node has no effective uses but can have refinement uses, which | |
| 145 // themselves can have more refinements uses (but only refinement uses). | |
| 146 // We must remove the entire refinement tree while looking for redexes | |
| 147 // whenever we remove one. | |
| 148 List<Primitive> deadlist = <Primitive>[deadPrim]; | |
| 149 while (deadlist.isNotEmpty) { | |
| 150 Primitive node = deadlist.removeLast(); | |
| 151 while (node.firstRef != null) { | |
| 152 Reference ref = node.firstRef; | |
| 153 Refinement use = ref.parent; | |
| 154 deadlist.add(use); | |
| 155 ref.unlink(); | |
| 156 } | |
| 157 LetPrim binding = node.parent; | |
| 158 _removeNode(binding); // Remove the binding and check for eta redexes. | |
| 159 } | |
| 160 | |
| 161 // Perform bookkeeping on removed body and scan for new redexes. | |
| 162 new _RemovalVisitor(_worklist).visit(deadPrim); | |
| 163 } | |
| 164 | |
| 165 /// Applies the dead-cont reduction: | |
| 166 /// letcont k x = E0 in E1 -> E1 (k not free in E1). | |
| 167 void _reduceDeadCont(_ReductionTask task) { | |
| 168 assert(_isDeadCont(task.node)); | |
| 169 | |
| 170 // Remove dead continuation. | |
| 171 Continuation cont = task.node; | |
| 172 _removeContinuation(cont); | |
| 173 | |
| 174 // Perform bookkeeping on removed body and scan for new redexes. | |
| 175 new _RemovalVisitor(_worklist).visit(cont); | |
| 176 } | |
| 177 | |
| 178 /// Applies the beta-cont-lin reduction: | |
| 179 /// letcont k x = E0 in E1[k y] -> E1[E0[y/x]] (k not free in E1). | |
| 180 void _reduceBetaContLin(_ReductionTask task) { | |
| 181 // Might have been mutated, recheck if reduction is still valid. | |
| 182 // In the following example, the beta-cont-lin reduction of k0 could have | |
| 183 // been invalidated by removal of the dead continuation k1: | |
| 184 // | |
| 185 // letcont k0 x0 = E0 in | |
| 186 // letcont k1 x1 = k0 x1 in | |
| 187 // return x2 | |
| 188 if (!_isBetaContLin(task.node)) { | |
| 189 return; | |
| 190 } | |
| 191 | |
| 192 Continuation cont = task.node; | |
| 193 InvokeContinuation invoke = cont.firstRef.parent; | |
| 194 InteriorNode invokeParent = invoke.parent; | |
| 195 Expression body = cont.body; | |
| 196 | |
| 197 // Replace the invocation with the continuation body. | |
| 198 invokeParent.body = body; | |
| 199 body.parent = invokeParent; | |
| 200 cont.body = null; | |
| 201 | |
| 202 // Substitute the invocation argument for the continuation parameter. | |
| 203 for (int i = 0; i < invoke.argumentRefs.length; i++) { | |
| 204 Parameter param = cont.parameters[i]; | |
| 205 Primitive argument = invoke.argument(i); | |
| 206 param.replaceUsesWith(argument); | |
| 207 argument.useElementAsHint(param.hint); | |
| 208 _checkConstantBranchCondition(argument); | |
| 209 } | |
| 210 | |
| 211 // Remove the continuation after inlining it so we can check for eta redexes | |
| 212 // which may arise after removing the LetCont. | |
| 213 _removeContinuation(cont); | |
| 214 | |
| 215 // Perform bookkeeping on substituted body and scan for new redexes. | |
| 216 new _RemovalVisitor(_worklist).visit(invoke); | |
| 217 | |
| 218 if (invokeParent is Continuation) { | |
| 219 _checkEtaCont(invokeParent); | |
| 220 _checkUselessBranchTarget(invokeParent); | |
| 221 } | |
| 222 } | |
| 223 | |
| 224 /// Applies the eta-cont reduction: | |
| 225 /// letcont k x = j x in E -> E[j/k]. | |
| 226 /// If k is unused, degenerates to dead-cont. | |
| 227 void _reduceEtaCont(_ReductionTask task) { | |
| 228 // Might have been mutated, recheck if reduction is still valid. | |
| 229 // In the following example, the eta-cont reduction of k1 could have been | |
| 230 // invalidated by an earlier beta-cont-lin reduction of k0. | |
| 231 // | |
| 232 // letcont k0 x0 = E0 in | |
| 233 // letcont k1 x1 = k0 x1 in E1 | |
| 234 if (!_isEtaCont(task.node)) { | |
| 235 return; | |
| 236 } | |
| 237 | |
| 238 // Remove the continuation. | |
| 239 Continuation cont = task.node; | |
| 240 _removeContinuation(cont); | |
| 241 | |
| 242 InvokeContinuation invoke = cont.body; | |
| 243 Continuation wrappedCont = invoke.continuation; | |
| 244 | |
| 245 for (int i = 0; i < cont.parameters.length; ++i) { | |
| 246 wrappedCont.parameters[i].useElementAsHint(cont.parameters[i].hint); | |
| 247 } | |
| 248 | |
| 249 // If the invocation of wrappedCont is escaping, then all invocations of | |
| 250 // cont will be as well, after the reduction. | |
| 251 if (invoke.isEscapingTry) { | |
| 252 Reference current = cont.firstRef; | |
| 253 while (current != null) { | |
| 254 InvokeContinuation owner = current.parent; | |
| 255 owner.isEscapingTry = true; | |
| 256 current = current.next; | |
| 257 } | |
| 258 } | |
| 259 | |
| 260 // Replace all occurrences with the wrapped continuation and find redexes. | |
| 261 while (cont.firstRef != null) { | |
| 262 Reference ref = cont.firstRef; | |
| 263 ref.changeTo(wrappedCont); | |
| 264 Node use = ref.parent; | |
| 265 if (use is InvokeContinuation && use.parent is Continuation) { | |
| 266 _checkUselessBranchTarget(use.parent); | |
| 267 } | |
| 268 } | |
| 269 | |
| 270 // Perform bookkeeping on removed body and scan for new redexes. | |
| 271 new _RemovalVisitor(_worklist).visit(cont); | |
| 272 } | |
| 273 | |
| 274 void _reduceBranch(_ReductionTask task) { | |
| 275 Branch branch = task.node; | |
| 276 // Replace Branch with InvokeContinuation of one of the targets. When the | |
| 277 // branch is deleted the other target becomes unreferenced and the chosen | |
| 278 // target becomes available for eta-cont and further reductions. | |
| 279 Continuation target; | |
| 280 Primitive condition = branch.condition; | |
| 281 if (condition is Constant) { | |
| 282 target = isTruthyConstant(condition.value, strict: branch.isStrictCheck) | |
| 283 ? branch.trueContinuation | |
| 284 : branch.falseContinuation; | |
| 285 } else if (_isBranchTargetOfUselessIf(branch.trueContinuation)) { | |
| 286 target = branch.trueContinuation; | |
| 287 } else { | |
| 288 return; | |
| 289 } | |
| 290 | |
| 291 InvokeContinuation invoke = new InvokeContinuation(target, <Primitive>[] | |
| 292 // TODO(sra): Add sourceInformation. | |
| 293 /*, sourceInformation: branch.sourceInformation*/); | |
| 294 branch.parent.body = invoke; | |
| 295 invoke.parent = branch.parent; | |
| 296 branch.parent = null; | |
| 297 | |
| 298 new _RemovalVisitor(_worklist).visit(branch); | |
| 299 } | |
| 300 | |
| 301 void _reduceDeadParameter(_ReductionTask task) { | |
| 302 // Continuation eta-reduction can destroy a dead parameter redex. For | |
| 303 // example, in the term: | |
| 304 // | |
| 305 // let cont k0(v0) = /* v0 is not used */ in | |
| 306 // let cont k1(v1) = k0(v1) in | |
| 307 // call foo () k1 | |
| 308 // | |
| 309 // Continuation eta-reduction of k1 gives: | |
| 310 // | |
| 311 // let cont k0(v0) = /* v0 is not used */ in | |
| 312 // call foo () k0 | |
| 313 // | |
| 314 // Where the dead parameter reduction is no longer valid because we do not | |
| 315 // allow removing the paramter of call continuations. We disallow such eta | |
| 316 // reductions in [_isEtaCont]. | |
| 317 Parameter parameter = task.node; | |
| 318 if (_isParameterRemoved(parameter)) return; | |
| 319 assert(_isDeadParameter(parameter)); | |
| 320 | |
| 321 Continuation continuation = parameter.parent; | |
| 322 int index = continuation.parameters.indexOf(parameter); | |
| 323 assert(index != -1); | |
| 324 continuation.parameters.removeAt(index); | |
| 325 parameter.parent = null; // Mark as removed. | |
| 326 | |
| 327 // Remove the index'th argument from each invocation. | |
| 328 for (Reference ref = continuation.firstRef; ref != null; ref = ref.next) { | |
| 329 InvokeContinuation invoke = ref.parent; | |
| 330 Reference<Primitive> argument = invoke.argumentRefs[index]; | |
| 331 argument.unlink(); | |
| 332 invoke.argumentRefs.removeAt(index); | |
| 333 // Removing an argument can create a dead primitive or an eta-redex | |
| 334 // in case the parent is a continuation that now has matching parameters. | |
| 335 _checkDeadPrimitive(argument.definition); | |
| 336 if (invoke.parent is Continuation) { | |
| 337 _checkEtaCont(invoke.parent); | |
| 338 _checkUselessBranchTarget(invoke.parent); | |
| 339 } | |
| 340 } | |
| 341 | |
| 342 // Removing an unused parameter can create an eta-redex, in case the | |
| 343 // body is an InvokeContinuation that now has matching arguments. | |
| 344 _checkEtaCont(continuation); | |
| 345 } | |
| 346 | |
| 347 void _checkEtaCont(Continuation continuation) { | |
| 348 if (_isEtaCont(continuation)) { | |
| 349 _worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, continuation)); | |
| 350 } | |
| 351 } | |
| 352 | |
| 353 void _checkUselessBranchTarget(Continuation continuation) { | |
| 354 if (_isBranchTargetOfUselessIf(continuation)) { | |
| 355 _worklist.add(new _ReductionTask( | |
| 356 _ReductionKind.BRANCH, continuation.firstRef.parent)); | |
| 357 } | |
| 358 } | |
| 359 | |
| 360 void _checkConstantBranchCondition(Primitive primitive) { | |
| 361 if (primitive is! Constant) return; | |
| 362 for (Reference ref = primitive.firstRef; ref != null; ref = ref.next) { | |
| 363 Node use = ref.parent; | |
| 364 if (use is Branch) { | |
| 365 _worklist.add(new _ReductionTask(_ReductionKind.BRANCH, use)); | |
| 366 } | |
| 367 } | |
| 368 } | |
| 369 | |
| 370 void _checkDeadPrimitive(Primitive primitive) { | |
| 371 primitive = primitive.unrefined; | |
| 372 if (primitive is Parameter) { | |
| 373 if (_isDeadParameter(primitive)) { | |
| 374 _worklist | |
| 375 .add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, primitive)); | |
| 376 } | |
| 377 } else if (primitive.parent is LetPrim) { | |
| 378 LetPrim letPrim = primitive.parent; | |
| 379 if (_isDeadVal(letPrim)) { | |
| 380 _worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, letPrim)); | |
| 381 } | |
| 382 } | |
| 383 } | |
| 384 } | |
| 385 | |
| 386 bool _isRemoved(InteriorNode node) { | |
| 387 return node.parent == null; | |
| 388 } | |
| 389 | |
| 390 bool _isParameterRemoved(Parameter parameter) { | |
| 391 // A parameter can be removed directly or because its continuation is removed. | |
| 392 return parameter.parent == null || _isRemoved(parameter.parent); | |
| 393 } | |
| 394 | |
| 395 /// Returns true iff the bound primitive is unused, and has no effects | |
| 396 /// preventing it from being eliminated. | |
| 397 bool _isDeadVal(LetPrim node) { | |
| 398 return !_isRemoved(node) && | |
| 399 node.primitive.hasNoRefinedUses && | |
| 400 node.primitive.isSafeForElimination; | |
| 401 } | |
| 402 | |
| 403 /// Returns true iff the continuation is unused. | |
| 404 bool _isDeadCont(Continuation cont) { | |
| 405 return !_isRemoved(cont) && | |
| 406 !cont.isReturnContinuation && | |
| 407 !cont.hasAtLeastOneUse; | |
| 408 } | |
| 409 | |
| 410 /// Returns true iff the continuation has a body (i.e., it is not the return | |
| 411 /// continuation), it is used exactly once, and that use is as the continuation | |
| 412 /// of a continuation invocation. | |
| 413 bool _isBetaContLin(Continuation cont) { | |
| 414 if (_isRemoved(cont)) return false; | |
| 415 | |
| 416 // There is a restriction on continuation eta-redexes that the body is not an | |
| 417 // invocation of the return continuation, because that leads to worse code | |
| 418 // when translating back to direct style (it duplicates returns). There is no | |
| 419 // such restriction here because continuation beta-reduction is only performed | |
| 420 // for singly referenced continuations. Thus, there is no possibility of code | |
| 421 // duplication. | |
| 422 if (cont.isReturnContinuation || !cont.hasExactlyOneUse) { | |
| 423 return false; | |
| 424 } | |
| 425 | |
| 426 if (cont.firstRef.parent is! InvokeContinuation) return false; | |
| 427 | |
| 428 InvokeContinuation invoke = cont.firstRef.parent; | |
| 429 | |
| 430 // Beta-reduction will move the continuation's body to its unique invocation | |
| 431 // site. This is not safe if the body is moved into an exception handler | |
| 432 // binding. | |
| 433 if (invoke.isEscapingTry) return false; | |
| 434 | |
| 435 return true; | |
| 436 } | |
| 437 | |
| 438 /// Returns true iff the continuation consists of a continuation | |
| 439 /// invocation, passing on all parameters. Special cases exist (see below). | |
| 440 bool _isEtaCont(Continuation cont) { | |
| 441 if (_isRemoved(cont)) return false; | |
| 442 | |
| 443 if (!cont.isJoinContinuation || cont.body is! InvokeContinuation) { | |
| 444 return false; | |
| 445 } | |
| 446 | |
| 447 InvokeContinuation invoke = cont.body; | |
| 448 Continuation invokedCont = invoke.continuation; | |
| 449 | |
| 450 // Do not eta-reduce return join-points since the direct-style code is worse | |
| 451 // in the common case (i.e. returns are moved inside `if` branches). | |
| 452 if (invokedCont.isReturnContinuation) { | |
| 453 return false; | |
| 454 } | |
| 455 | |
| 456 // Translation to direct style generates different statements for recursive | |
| 457 // and non-recursive invokes. It should still be possible to apply eta-cont if | |
| 458 // this is not a self-invocation. | |
| 459 // | |
| 460 // TODO(kmillikin): Remove this restriction if it makes sense to do so. | |
| 461 if (invoke.isRecursive) { | |
| 462 return false; | |
| 463 } | |
| 464 | |
| 465 // If cont has more parameters than the invocation has arguments, the extra | |
| 466 // parameters will be dead and dead-parameter will eventually create the | |
| 467 // eta-redex if possible. | |
| 468 // | |
| 469 // If the invocation's arguments are simply a permutation of cont's | |
| 470 // parameters, then there is likewise a possible reduction that involves | |
| 471 // rewriting the invocations of cont. We are missing that reduction here. | |
| 472 // | |
| 473 // If cont has fewer parameters than the invocation has arguments then a | |
| 474 // reduction would still possible, since the extra invocation arguments must | |
| 475 // be in scope at all the invocations of cont. For example: | |
| 476 // | |
| 477 // let cont k1(x1) = k0(x0, x1) in E -eta-> E' | |
| 478 // where E' has k0(x0, v) substituted for each k1(v). | |
| 479 // | |
| 480 // HOWEVER, adding continuation parameters is unlikely to be an optimization | |
| 481 // since it duplicates assignments used in direct-style to implement parameter | |
| 482 // passing. | |
| 483 // | |
| 484 // TODO(kmillikin): find real occurrences of these patterns, and see if they | |
| 485 // can be optimized. | |
| 486 if (cont.parameters.length != invoke.argumentRefs.length) { | |
| 487 return false; | |
| 488 } | |
| 489 | |
| 490 // TODO(jgruber): Linear in the parameter count. Can be improved to near | |
| 491 // constant time by using union-find data structure. | |
| 492 for (int i = 0; i < cont.parameters.length; i++) { | |
| 493 if (invoke.argument(i) != cont.parameters[i]) { | |
| 494 return false; | |
| 495 } | |
| 496 } | |
| 497 | |
| 498 return true; | |
| 499 } | |
| 500 | |
| 501 Expression _unfoldDeadRefinements(Expression node) { | |
| 502 while (node is LetPrim) { | |
| 503 LetPrim let = node; | |
| 504 Primitive prim = let.primitive; | |
| 505 if (prim.hasAtLeastOneUse || prim is! Refinement) return node; | |
| 506 node = node.next; | |
| 507 } | |
| 508 return node; | |
| 509 } | |
| 510 | |
| 511 bool _isBranchRedex(Branch branch) { | |
| 512 return _isUselessIf(branch) || branch.condition is Constant; | |
| 513 } | |
| 514 | |
| 515 bool _isBranchTargetOfUselessIf(Continuation cont) { | |
| 516 // A useless-if has an empty then and else branch, e.g. `if (cond);`. | |
| 517 // | |
| 518 // Detect T or F in | |
| 519 // | |
| 520 // let cont Join() = ... | |
| 521 // in let cont T() = Join() | |
| 522 // F() = Join() | |
| 523 // in branch condition T F | |
| 524 // | |
| 525 if (!cont.hasExactlyOneUse) return false; | |
| 526 Node use = cont.firstRef.parent; | |
| 527 if (use is! Branch) return false; | |
| 528 return _isUselessIf(use); | |
| 529 } | |
| 530 | |
| 531 bool _isUselessIf(Branch branch) { | |
| 532 Continuation trueCont = branch.trueContinuation; | |
| 533 Expression trueBody = _unfoldDeadRefinements(trueCont.body); | |
| 534 if (trueBody is! InvokeContinuation) return false; | |
| 535 Continuation falseCont = branch.falseContinuation; | |
| 536 Expression falseBody = _unfoldDeadRefinements(falseCont.body); | |
| 537 if (falseBody is! InvokeContinuation) return false; | |
| 538 InvokeContinuation trueInvoke = trueBody; | |
| 539 InvokeContinuation falseInvoke = falseBody; | |
| 540 if (trueInvoke.continuation != falseInvoke.continuation) { | |
| 541 return false; | |
| 542 } | |
| 543 // Matching zero arguments should be adequate, since isomorphic true and false | |
| 544 // invocations should result in redundant phis which are removed elsewhere. | |
| 545 // | |
| 546 // Note that the argument lists are not necessarily the same length here, | |
| 547 // because we could be looking for new redexes in the middle of performing a | |
| 548 // dead parameter reduction, where some but not all of the invocations have | |
| 549 // been rewritten. In that case, we will find the redex (once) after both | |
| 550 // of these invocations have been rewritten. | |
| 551 return trueInvoke.argumentRefs.isEmpty && falseInvoke.argumentRefs.isEmpty; | |
| 552 } | |
| 553 | |
| 554 bool _isDeadParameter(Parameter parameter) { | |
| 555 if (_isParameterRemoved(parameter)) return false; | |
| 556 | |
| 557 // We cannot remove function parameters as an intraprocedural optimization. | |
| 558 if (parameter.parent is! Continuation || parameter.hasAtLeastOneUse) { | |
| 559 return false; | |
| 560 } | |
| 561 | |
| 562 // We cannot remove the parameter to a call continuation, because the | |
| 563 // resulting expression will not be well-formed (call continuations have | |
| 564 // exactly one argument). The return continuation is a call continuation, so | |
| 565 // we cannot remove its dummy parameter. | |
| 566 Continuation continuation = parameter.parent; | |
| 567 if (!continuation.isJoinContinuation) return false; | |
| 568 | |
| 569 return true; | |
| 570 } | |
| 571 | |
| 572 /// Traverses a term and adds any found redexes to the worklist. | |
| 573 class _RedexVisitor extends TrampolineRecursiveVisitor { | |
| 574 final List<_ReductionTask> worklist; | |
| 575 | |
| 576 _RedexVisitor(this.worklist); | |
| 577 | |
| 578 void processLetPrim(LetPrim node) { | |
| 579 if (_isDeadVal(node)) { | |
| 580 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node)); | |
| 581 } | |
| 582 } | |
| 583 | |
| 584 void processBranch(Branch node) { | |
| 585 if (_isBranchRedex(node)) { | |
| 586 worklist.add(new _ReductionTask(_ReductionKind.BRANCH, node)); | |
| 587 } | |
| 588 } | |
| 589 | |
| 590 void processContinuation(Continuation node) { | |
| 591 // While it would be nice to remove exception handlers that are provably | |
| 592 // unnecessary (e.g., the body cannot throw), that takes more sophisticated | |
| 593 // analysis than we do in this pass. | |
| 594 if (node.parent is LetHandler) return; | |
| 595 | |
| 596 // Continuation beta- and eta-redexes can overlap, namely when an eta-redex | |
| 597 // is invoked exactly once. We prioritize continuation beta-redexes over | |
| 598 // eta-redexes because some reductions (e.g., dead parameter elimination) | |
| 599 // can destroy a continuation eta-redex. If we prioritized eta- over | |
| 600 // beta-redexes, this would implicitly "create" the corresponding beta-redex | |
| 601 // (in the sense that it would still apply) and the algorithm would not | |
| 602 // detect it. | |
| 603 if (_isDeadCont(node)) { | |
| 604 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node)); | |
| 605 } else if (_isBetaContLin(node)) { | |
| 606 worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node)); | |
| 607 } else if (_isEtaCont(node)) { | |
| 608 worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node)); | |
| 609 } | |
| 610 } | |
| 611 | |
| 612 void processParameter(Parameter node) { | |
| 613 if (_isDeadParameter(node)) { | |
| 614 worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, node)); | |
| 615 } | |
| 616 } | |
| 617 } | |
| 618 | |
| 619 /// Traverses a deleted CPS term, marking nodes that might participate in a | |
| 620 /// redex as deleted and adding newly created redexes to the worklist. | |
| 621 /// | |
| 622 /// Deleted nodes that might participate in a reduction task are marked so that | |
| 623 /// any corresponding tasks can be skipped. Nodes are marked so by setting | |
| 624 /// their parent to the deleted sentinel. | |
| 625 class _RemovalVisitor extends TrampolineRecursiveVisitor { | |
| 626 final List<_ReductionTask> worklist; | |
| 627 | |
| 628 _RemovalVisitor(this.worklist); | |
| 629 | |
| 630 void processLetPrim(LetPrim node) { | |
| 631 node.parent = null; | |
| 632 } | |
| 633 | |
| 634 void processContinuation(Continuation node) { | |
| 635 node.parent = null; | |
| 636 } | |
| 637 | |
| 638 void processBranch(Branch node) { | |
| 639 node.parent = null; | |
| 640 } | |
| 641 | |
| 642 void processReference(Reference reference) { | |
| 643 reference.unlink(); | |
| 644 | |
| 645 if (reference.definition is Primitive) { | |
| 646 Primitive primitive = reference.definition.unrefined; | |
| 647 Node parent = primitive.parent; | |
| 648 // The parent might be the deleted sentinel, or it might be a | |
| 649 // Continuation or FunctionDefinition if the primitive is an argument. | |
| 650 if (parent is LetPrim && _isDeadVal(parent)) { | |
| 651 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent)); | |
| 652 } else if (primitive is Parameter && _isDeadParameter(primitive)) { | |
| 653 worklist | |
| 654 .add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, primitive)); | |
| 655 } | |
| 656 } else if (reference.definition is Continuation) { | |
| 657 Continuation cont = reference.definition; | |
| 658 Node parent = cont.parent; | |
| 659 // The parent might be the deleted sentinel, or it might be a | |
| 660 // Body if the continuation is the return continuation. | |
| 661 if (parent is LetCont) { | |
| 662 if (cont.isRecursive && cont.hasAtMostOneUse) { | |
| 663 // Convert recursive to nonrecursive continuations. If the | |
| 664 // continuation is still in use, it is either dead and will be | |
| 665 // removed, or it is called nonrecursively outside its body. | |
| 666 cont.isRecursive = false; | |
| 667 } | |
| 668 if (_isDeadCont(cont)) { | |
| 669 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, cont)); | |
| 670 } else if (_isBetaContLin(cont)) { | |
| 671 worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, cont)); | |
| 672 } else if (_isBranchTargetOfUselessIf(cont)) { | |
| 673 worklist.add( | |
| 674 new _ReductionTask(_ReductionKind.BRANCH, cont.firstRef.parent)); | |
| 675 } | |
| 676 } | |
| 677 } | |
| 678 } | |
| 679 } | |
| 680 | |
| 681 enum _ReductionKind { | |
| 682 DEAD_VAL, | |
| 683 DEAD_CONT, | |
| 684 BETA_CONT_LIN, | |
| 685 ETA_CONT, | |
| 686 DEAD_PARAMETER, | |
| 687 BRANCH | |
| 688 } | |
| 689 | |
| 690 /// Represents a reduction task on the worklist. Implements both hashCode and | |
| 691 /// operator== since instantiations are used as Set elements. | |
| 692 class _ReductionTask { | |
| 693 final _ReductionKind kind; | |
| 694 final Node node; | |
| 695 | |
| 696 int get hashCode { | |
| 697 return (node.hashCode << 3) | kind.index; | |
| 698 } | |
| 699 | |
| 700 _ReductionTask(this.kind, this.node) { | |
| 701 assert(node is Continuation || | |
| 702 node is LetPrim || | |
| 703 node is Parameter || | |
| 704 node is Branch); | |
| 705 } | |
| 706 | |
| 707 bool operator ==(_ReductionTask that) { | |
| 708 return (that.kind == this.kind && that.node == this.node); | |
| 709 } | |
| 710 | |
| 711 String toString() => "$kind: $node"; | |
| 712 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
