| 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 part of dart2js.optimizers; | |
| 6 | |
| 7 /** | |
| 8 * [[ShrinkingReducer]] applies shrinking reductions to CPS terms as described | |
| 9 * in 'Compiling with Continuations, Continued' by Andrew Kennedy. | |
| 10 */ | |
| 11 class ShrinkingReducer implements Pass { | |
| 12 _RedexVisitor _redexVisitor; | |
| 13 Set<_ReductionTask> _worklist; | |
| 14 | |
| 15 static final _DeletedNode _DELETED = new _DeletedNode(); | |
| 16 | |
| 17 /// Applies shrinking reductions to root, mutating root in the process. | |
| 18 void rewrite(FunctionDefinition root) { | |
| 19 if (root.isAbstract) return; | |
| 20 | |
| 21 _worklist = new Set<_ReductionTask>(); | |
| 22 _redexVisitor = new _RedexVisitor(_worklist); | |
| 23 | |
| 24 // Set all parent pointers. | |
| 25 new _ParentVisitor().visit(root); | |
| 26 | |
| 27 // Sweep over the term, collecting redexes into the worklist. | |
| 28 _redexVisitor.visitFunctionDefinition(root); | |
| 29 | |
| 30 // Process the worklist. | |
| 31 while (_worklist.isNotEmpty) { | |
| 32 _ReductionTask task = _worklist.first; | |
| 33 _worklist.remove(task); | |
| 34 _processTask(task); | |
| 35 } | |
| 36 } | |
| 37 | |
| 38 /// Removes the given node from the CPS graph, replacing it with its body | |
| 39 /// and marking it as deleted. The node's parent must be a [[InteriorNode]]. | |
| 40 void _removeNode(InteriorNode node) { | |
| 41 Node body = node.body; | |
| 42 InteriorNode parent = node.parent; | |
| 43 assert(parent.body == node); | |
| 44 | |
| 45 body.parent = parent; | |
| 46 parent.body = body; | |
| 47 node.parent = _DELETED; | |
| 48 } | |
| 49 | |
| 50 void _processTask(_ReductionTask task) { | |
| 51 // Lazily skip tasks for deleted nodes. | |
| 52 if (task.node.parent == _DELETED) { | |
| 53 return; | |
| 54 } | |
| 55 | |
| 56 switch (task.kind) { | |
| 57 case _ReductionKind.DEAD_VAL: | |
| 58 _reduceDeadVal(task); | |
| 59 break; | |
| 60 case _ReductionKind.DEAD_CONT: | |
| 61 _reduceDeadCont(task); | |
| 62 break; | |
| 63 case _ReductionKind.BETA_CONT_LIN: | |
| 64 _reduceBetaContLin(task); | |
| 65 break; | |
| 66 case _ReductionKind.ETA_CONT: | |
| 67 _reduceEtaCont(task); | |
| 68 break; | |
| 69 default: | |
| 70 assert(false); | |
| 71 } | |
| 72 } | |
| 73 | |
| 74 /// Applies the dead-val reduction: | |
| 75 /// letprim x = V in E -> E (x not free in E). | |
| 76 void _reduceDeadVal(_ReductionTask task) { | |
| 77 assert(_isDeadVal(task.node)); | |
| 78 | |
| 79 // Remove dead primitive. | |
| 80 LetPrim letPrim = task.node;; | |
| 81 _removeNode(letPrim); | |
| 82 | |
| 83 // Perform bookkeeping on removed body and scan for new redexes. | |
| 84 new _RemovalRedexVisitor(_worklist).visit(letPrim.primitive); | |
| 85 } | |
| 86 | |
| 87 /// Applies the dead-cont reduction: | |
| 88 /// letcont k x = E0 in E1 -> E1 (k not free in E1). | |
| 89 void _reduceDeadCont(_ReductionTask task) { | |
| 90 assert(_isDeadCont(task.node)); | |
| 91 | |
| 92 // Remove dead continuation. | |
| 93 LetCont letCont = task.node; | |
| 94 _removeNode(letCont); | |
| 95 | |
| 96 // Perform bookkeeping on removed body and scan for new redexes. | |
| 97 new _RemovalRedexVisitor(_worklist).visit(letCont.continuation); | |
| 98 } | |
| 99 | |
| 100 /// Applies the beta-cont-lin reduction: | |
| 101 /// letcont k x = E0 in E1[k y] -> E1[E0[y/x]] (k not free in E1). | |
| 102 void _reduceBetaContLin(_ReductionTask task) { | |
| 103 // Might have been mutated, recheck if reduction is still valid. | |
| 104 // In the following example, the beta-cont-lin reduction of k0 could have | |
| 105 // been invalidated by removal of the dead continuation k1: | |
| 106 // | |
| 107 // letcont k0 x0 = E0 in | |
| 108 // letcont k1 x1 = k0 x1 in | |
| 109 // return x2 | |
| 110 if (!_isBetaContLin(task.node)) { | |
| 111 return; | |
| 112 } | |
| 113 | |
| 114 // Remove the continuation. | |
| 115 LetCont letCont = task.node; | |
| 116 Continuation cont = letCont.continuation; | |
| 117 _removeNode(letCont); | |
| 118 | |
| 119 // Replace its invocation with the continuation body. | |
| 120 InvokeContinuation invoke = cont.firstRef.parent; | |
| 121 InteriorNode invokeParent = invoke.parent; | |
| 122 | |
| 123 cont.body.parent = invokeParent; | |
| 124 invokeParent.body = cont.body; | |
| 125 | |
| 126 // Substitute the invocation argument for the continuation parameter. | |
| 127 for (int i = 0; i < invoke.arguments.length; i++) { | |
| 128 Reference argRef = invoke.arguments[i]; | |
| 129 argRef.definition.substituteFor(cont.parameters[i]); | |
| 130 } | |
| 131 | |
| 132 // Perform bookkeeping on removed body and scan for new redexes. | |
| 133 new _RemovalRedexVisitor(_worklist).visit(invoke); | |
| 134 } | |
| 135 | |
| 136 /// Applies the eta-cont reduction: | |
| 137 /// letcont k x = j x in E -> E[j/k]. | |
| 138 /// If k is unused, degenerates to dead-cont. | |
| 139 void _reduceEtaCont(_ReductionTask task) { | |
| 140 // Might have been mutated, recheck if reduction is still valid. | |
| 141 // In the following example, the eta-cont reduction of k1 could have been | |
| 142 // invalidated by an earlier beta-cont-lin reduction of k0. | |
| 143 // | |
| 144 // letcont k0 x0 = E0 in | |
| 145 // letcont k1 x1 = k0 x1 in E1 | |
| 146 if (!_isEtaCont(task.node)) { | |
| 147 return; | |
| 148 } | |
| 149 | |
| 150 // Remove the continuation. | |
| 151 LetCont letCont = task.node; | |
| 152 Continuation cont = letCont.continuation; | |
| 153 _removeNode(letCont); | |
| 154 | |
| 155 InvokeContinuation invoke = cont.body; | |
| 156 Continuation wrappedCont = invoke.continuation.definition; | |
| 157 | |
| 158 // Replace all occurrences with the wrapped continuation. | |
| 159 wrappedCont.substituteFor(cont); | |
| 160 | |
| 161 // Perform bookkeeping on removed body and scan for new redexes. | |
| 162 new _RemovalRedexVisitor(_worklist).visit(cont); | |
| 163 } | |
| 164 } | |
| 165 | |
| 166 /// Returns true iff the bound primitive is unused. | |
| 167 bool _isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse; | |
| 168 | |
| 169 /// Returns true iff the bound continuation is unused. | |
| 170 bool _isDeadCont(LetCont node) => !node.continuation.hasAtLeastOneUse; | |
| 171 | |
| 172 /// Returns true iff the bound continuation is used exactly once, and that | |
| 173 /// use is as the receiver of a continuation invocation. | |
| 174 bool _isBetaContLin(LetCont node) { | |
| 175 Continuation cont = node.continuation; | |
| 176 if (!cont.hasExactlyOneUse) { | |
| 177 return false; | |
| 178 } | |
| 179 | |
| 180 if (cont.firstRef.parent is InvokeContinuation) { | |
| 181 InvokeContinuation invoke = cont.firstRef.parent; | |
| 182 return (cont == invoke.continuation.definition); | |
| 183 } | |
| 184 | |
| 185 return false; | |
| 186 | |
| 187 } | |
| 188 | |
| 189 /// Returns true iff the bound continuation consists of a continuation | |
| 190 /// invocation, passing on all parameters. Special cases exist (see below). | |
| 191 bool _isEtaCont(LetCont node) { | |
| 192 Continuation cont = node.continuation; | |
| 193 if (!(cont.body is InvokeContinuation)) { | |
| 194 return false; | |
| 195 } | |
| 196 | |
| 197 InvokeContinuation invoke = cont.body; | |
| 198 Continuation invokedCont = invoke.continuation.definition; | |
| 199 | |
| 200 // Do not eta-reduce return join-points since the resulting code is worse | |
| 201 // in the common case (i.e. returns are moved inside `if` branches). | |
| 202 if (invokedCont.isReturnContinuation) { | |
| 203 return false; | |
| 204 } | |
| 205 | |
| 206 // Translation to direct style generates different statements for recursive | |
| 207 // and non-recursive invokes. It should be possible to apply eta-cont, but | |
| 208 // higher order continuations require escape analysis, left as a possibility | |
| 209 // for future improvements. | |
| 210 if (invoke.isRecursive) { | |
| 211 return false; | |
| 212 } | |
| 213 | |
| 214 if (cont.parameters.length != invoke.arguments.length) { | |
| 215 return false; | |
| 216 } | |
| 217 | |
| 218 // TODO(jgruber): Linear in the parameter count. Can be improved to near | |
| 219 // constant time by using union-find data structure. | |
| 220 for (int i = 0; i < cont.parameters.length; i++) { | |
| 221 if (invoke.arguments[i].definition != cont.parameters[i]) { | |
| 222 return false; | |
| 223 } | |
| 224 } | |
| 225 | |
| 226 return true; | |
| 227 } | |
| 228 | |
| 229 /// Traverses a term and adds any found redexes to the worklist. | |
| 230 class _RedexVisitor extends RecursiveVisitor { | |
| 231 final Set<_ReductionTask> worklist; | |
| 232 | |
| 233 _RedexVisitor(this.worklist); | |
| 234 | |
| 235 void processLetPrim(LetPrim node) { | |
| 236 if (node.parent == ShrinkingReducer._DELETED) { | |
| 237 return; | |
| 238 } else if (_isDeadVal(node)) { | |
| 239 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node)); | |
| 240 } | |
| 241 } | |
| 242 | |
| 243 void processLetCont(LetCont node) { | |
| 244 if (node.parent == ShrinkingReducer._DELETED) { | |
| 245 return; | |
| 246 } else if (_isDeadCont(node)) { | |
| 247 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node)); | |
| 248 } else if (_isEtaCont(node)) { | |
| 249 worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node)); | |
| 250 } else if (_isBetaContLin(node)){ | |
| 251 worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node)); | |
| 252 } | |
| 253 } | |
| 254 } | |
| 255 | |
| 256 /// Traverses a deleted CPS term, marking existing tasks associated with a node | |
| 257 /// within the term as deleted (which causes them to be skipped lazily when | |
| 258 /// popped from the worklist), and adding newly created redexes to the worklist. | |
| 259 class _RemovalRedexVisitor extends _RedexVisitor { | |
| 260 _RemovalRedexVisitor(Set<_ReductionTask> worklist) : super(worklist); | |
| 261 | |
| 262 void processLetPrim(LetPrim node) { | |
| 263 node.parent = ShrinkingReducer._DELETED; | |
| 264 } | |
| 265 | |
| 266 void processLetCont(LetCont node) { | |
| 267 node.parent = ShrinkingReducer._DELETED; | |
| 268 } | |
| 269 | |
| 270 void processReference(Reference reference) { | |
| 271 reference.unlink(); | |
| 272 | |
| 273 if (reference.definition is Primitive) { | |
| 274 Primitive primitive = reference.definition; | |
| 275 Node parent = primitive.parent; | |
| 276 if (parent is LetPrim && _isDeadVal(parent)) { | |
| 277 worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent)); | |
| 278 } | |
| 279 } else if (reference.definition is Continuation) { | |
| 280 Continuation cont = reference.definition; | |
| 281 if (cont.isRecursive && cont.hasAtMostOneUse) { | |
| 282 // Convert recursive to nonrecursive continuations. | |
| 283 // If the continuation is still in use, it is either dead and will be | |
| 284 // removed, or it is called nonrecursively outside its body. | |
| 285 cont.isRecursive = false; | |
| 286 } | |
| 287 Node parent = cont.parent; | |
| 288 if (parent is LetCont && _isDeadCont(parent)) { | |
| 289 worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent)); | |
| 290 } | |
| 291 } | |
| 292 } | |
| 293 } | |
| 294 | |
| 295 /// Traverses the CPS term and sets node.parent for each visited node. | |
| 296 class _ParentVisitor extends RecursiveVisitor { | |
| 297 | |
| 298 processFunctionDefinition(FunctionDefinition node) { | |
| 299 node.body.parent = node; | |
| 300 node.parameters.forEach((Parameter p) => p.parent = node); | |
| 301 } | |
| 302 | |
| 303 // Expressions. | |
| 304 | |
| 305 processLetPrim(LetPrim node) { | |
| 306 node.primitive.parent = node; | |
| 307 node.body.parent = node; | |
| 308 } | |
| 309 | |
| 310 processLetCont(LetCont node) { | |
| 311 node.continuation.parent = node; | |
| 312 node.body.parent = node; | |
| 313 } | |
| 314 | |
| 315 processInvokeStatic(InvokeStatic node) { | |
| 316 node.continuation.parent = node; | |
| 317 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 318 } | |
| 319 | |
| 320 processInvokeContinuation(InvokeContinuation node) { | |
| 321 node.continuation.parent = node; | |
| 322 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 323 } | |
| 324 | |
| 325 processInvokeMethod(InvokeMethod node) { | |
| 326 node.receiver.parent = node; | |
| 327 node.continuation.parent = node; | |
| 328 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 329 } | |
| 330 | |
| 331 processInvokeSuperMethod(InvokeSuperMethod node) { | |
| 332 node.continuation.parent = node; | |
| 333 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 334 } | |
| 335 | |
| 336 processInvokeConstructor(InvokeConstructor node) { | |
| 337 node.continuation.parent = node; | |
| 338 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 339 } | |
| 340 | |
| 341 processConcatenateStrings(ConcatenateStrings node) { | |
| 342 node.continuation.parent = node; | |
| 343 node.arguments.forEach((Reference ref) => ref.parent = node); | |
| 344 } | |
| 345 | |
| 346 processBranch(Branch node) { | |
| 347 node.condition.parent = node; | |
| 348 node.trueContinuation.parent = node; | |
| 349 node.falseContinuation.parent = node; | |
| 350 } | |
| 351 | |
| 352 processTypeOperator(TypeOperator node) { | |
| 353 node.continuation.parent = node; | |
| 354 node.receiver.parent = node; | |
| 355 } | |
| 356 | |
| 357 processSetClosureVariable(SetClosureVariable node) { | |
| 358 node.body.parent = node; | |
| 359 node.value.parent = node; | |
| 360 } | |
| 361 | |
| 362 processDeclareFunction(DeclareFunction node) { | |
| 363 node.definition.parent = node; | |
| 364 node.body.parent = node; | |
| 365 } | |
| 366 | |
| 367 // Definitions. | |
| 368 | |
| 369 processLiteralList(LiteralList node) { | |
| 370 node.values.forEach((Reference ref) => ref.parent = node); | |
| 371 } | |
| 372 | |
| 373 processLiteralMap(LiteralMap node) { | |
| 374 node.entries.forEach((LiteralMapEntry entry) { | |
| 375 entry.key.parent = node; | |
| 376 entry.value.parent = node; | |
| 377 }); | |
| 378 } | |
| 379 | |
| 380 processCreateFunction(CreateFunction node) { | |
| 381 node.definition.parent = node; | |
| 382 } | |
| 383 | |
| 384 processContinuation(Continuation node) { | |
| 385 node.body.parent = node; | |
| 386 node.parameters.forEach((Parameter param) => param.parent = node); | |
| 387 } | |
| 388 | |
| 389 // Conditions. | |
| 390 | |
| 391 processIsTrue(IsTrue node) { | |
| 392 node.value.parent = node; | |
| 393 } | |
| 394 } | |
| 395 | |
| 396 class _ReductionKind { | |
| 397 final String name; | |
| 398 final int hashCode; | |
| 399 | |
| 400 const _ReductionKind(this.name, this.hashCode); | |
| 401 | |
| 402 static const _ReductionKind DEAD_VAL = const _ReductionKind('dead-val', 0); | |
| 403 static const _ReductionKind DEAD_CONT = const _ReductionKind('dead-cont', 1); | |
| 404 static const _ReductionKind BETA_CONT_LIN = | |
| 405 const _ReductionKind('beta-cont-lin', 2); | |
| 406 static const _ReductionKind ETA_CONT = const _ReductionKind('eta-cont', 3); | |
| 407 | |
| 408 String toString() => name; | |
| 409 } | |
| 410 | |
| 411 /// Represents a reduction task on the worklist. Implements both hashCode and | |
| 412 /// operator== since instantiations are used as Set elements. | |
| 413 class _ReductionTask { | |
| 414 final _ReductionKind kind; | |
| 415 final Node node; | |
| 416 | |
| 417 int get hashCode { | |
| 418 assert(kind.hashCode < (1 << 2)); | |
| 419 return (node.hashCode << 2) | kind.hashCode; | |
| 420 } | |
| 421 | |
| 422 _ReductionTask(this.kind, this.node) { | |
| 423 // If new node types are added, they must be marked as deleted in | |
| 424 // [[_RemovalRedexVisitor]]. | |
| 425 assert(node is LetCont || node is LetPrim); | |
| 426 } | |
| 427 | |
| 428 bool operator==(_ReductionTask that) { | |
| 429 return (that.kind == this.kind && that.node == this.node); | |
| 430 } | |
| 431 | |
| 432 String toString() => "$kind: $node"; | |
| 433 } | |
| 434 | |
| 435 /// A dummy class used solely to mark nodes as deleted once they are removed | |
| 436 /// from a term. | |
| 437 class _DeletedNode extends Node { | |
| 438 accept(_) => null; | |
| 439 } | |
| 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