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 dart2js.cps_ir.let_sinking; |
| 6 |
| 7 import 'cps_ir_nodes.dart'; |
| 8 import 'optimizers.dart'; |
| 9 |
| 10 /// Sinks single-use primitives to the use when this is safe and profitable. |
| 11 /// |
| 12 /// To avoid sinking non-constant primitives into loops, this pass performs a |
| 13 /// control-flow analysis to determine the effective nesting of loops. |
| 14 /// |
| 15 /// In the example below, the value 'p' can be sunk to its use site in the |
| 16 /// 'else' branch because that branch is not effectively part of a loop, |
| 17 /// despite being lexically nested in a recursive continuation. |
| 18 /// |
| 19 /// let prim p = getInterceptor(<something>) |
| 20 /// let rec kont x = |
| 21 /// if (<loop condition>) |
| 22 /// <loop body> |
| 23 /// InvokeContinuation kont x' |
| 24 /// else |
| 25 /// <after loop> |
| 26 /// return p.foo() |
| 27 /// |
| 28 class LetSinker extends RecursiveVisitor implements Pass { |
| 29 String get passName => 'Let sinking'; |
| 30 |
| 31 LoopHierarchy loopHierarchy; |
| 32 List<Continuation> stack = <Continuation>[]; |
| 33 Set<LetPrim> sunkNodes = new Set<LetPrim>(); |
| 34 |
| 35 void rewrite(FunctionDefinition node) { |
| 36 new ParentVisitor().visit(node); |
| 37 loopHierarchy = new LoopHierarchy(node); |
| 38 visit(node.body); |
| 39 } |
| 40 |
| 41 void visitLetPrim(LetPrim node) { |
| 42 // Visit the body, wherein this primitive may be sunk to its use site. |
| 43 visit(node.body); |
| 44 |
| 45 if (node.primitive != null) { |
| 46 // The primitive could not be sunk. Sink dependencies to this location. |
| 47 visit(node.primitive); |
| 48 } else { |
| 49 // The primitive was sunk. Destroy the old LetPrim. |
| 50 InteriorNode parent = node.parent; |
| 51 parent.body = node.body; |
| 52 node.body.parent = parent; |
| 53 } |
| 54 } |
| 55 |
| 56 void processReference(Reference ref) { |
| 57 Definition definition = ref.definition; |
| 58 if (definition is Primitive && |
| 59 definition is! Parameter && |
| 60 definition.hasExactlyOneUse && |
| 61 definition.isSafeForReordering) { |
| 62 // Check if use is in the same loop. |
| 63 LetPrim binding = definition.parent; |
| 64 Continuation bindingLoop = loopHierarchy.getLoopHeader(binding); |
| 65 Expression use = getEnclosingExpression(ref.parent); |
| 66 Continuation useLoop = loopHierarchy.getLoopHeader(use); |
| 67 if (bindingLoop == useLoop || definition is Constant) { |
| 68 // Sink the definition. |
| 69 |
| 70 binding.primitive = null; // Mark old binding for deletion. |
| 71 LetPrim newBinding = new LetPrim(definition); |
| 72 definition.parent = newBinding; |
| 73 InteriorNode useParent = use.parent; |
| 74 useParent.body = newBinding; |
| 75 newBinding.body = use; |
| 76 use.parent = newBinding; |
| 77 newBinding.parent = useParent; |
| 78 |
| 79 // Now that the final binding location has been found, sink the |
| 80 // dependencies of the definition down here as well. |
| 81 visit(definition); |
| 82 } |
| 83 } |
| 84 } |
| 85 |
| 86 Expression getEnclosingExpression(Node node) { |
| 87 while (node is! Expression) { |
| 88 node = node.parent; |
| 89 } |
| 90 return node; |
| 91 } |
| 92 } |
| 93 |
| 94 /// Determines the effective nesting of loops. |
| 95 /// |
| 96 /// The effective nesting of loops is different from the lexical nesting, since |
| 97 /// recursive continuations can generally contain all the code following |
| 98 /// after the loop in addition to the looping code itself. |
| 99 /// |
| 100 /// For example, the 'else' branch below is not effectively part of the loop: |
| 101 /// |
| 102 /// let rec kont x = |
| 103 /// if (<loop condition>) |
| 104 /// <loop body> |
| 105 /// InvokeContinuation kont x' |
| 106 /// else |
| 107 /// <after loop> |
| 108 /// return p.foo() |
| 109 /// |
| 110 /// We use the term "loop" to mean recursive continuation. |
| 111 /// The `null` value is used to represent a context not part of any loop. |
| 112 class LoopHierarchy { |
| 113 /// Nesting depth of the given loop. |
| 114 Map<Continuation, int> loopDepth = <Continuation, int>{}; |
| 115 |
| 116 /// The innermost loop (other than itself) that may be invoked recursively |
| 117 /// as a result of invoking the given continuation. |
| 118 Map<Continuation, Continuation> loopTarget = <Continuation, Continuation>{}; |
| 119 |
| 120 /// Current nesting depth. |
| 121 int currentDepth = 0; |
| 122 |
| 123 /// Computes the loop hierarchy for the given function. |
| 124 /// |
| 125 /// Parent pointers must be computed for [node]. |
| 126 LoopHierarchy(FunctionDefinition node) { |
| 127 _processBlock(node.body, null); |
| 128 } |
| 129 |
| 130 /// Returns the innermost loop which [node] is effectively part of. |
| 131 Continuation getLoopHeader(Expression exp) { |
| 132 Node node = exp.parent; |
| 133 while (node != null && node is! Continuation) { |
| 134 node = node.parent; |
| 135 } |
| 136 if (node is Continuation) { |
| 137 if (node.isRecursive) { |
| 138 return node; |
| 139 } else { |
| 140 return loopTarget[node]; |
| 141 } |
| 142 } |
| 143 return null; |
| 144 } |
| 145 |
| 146 /// Marks the innermost loop as a subloop of the other loop. |
| 147 /// |
| 148 /// Returns the innermost loop. |
| 149 /// |
| 150 /// Both continuations, [c1] and [c2] may be null (i.e. no loop). |
| 151 /// |
| 152 /// A loop is said to be a subloop of an enclosing loop if it can invoke |
| 153 /// that loop recursively. This information is stored in [loopTarget]. |
| 154 /// |
| 155 /// This method is only invoked with two distinct loops if there is a |
| 156 /// point that can reach a recursive invocation of both loops. |
| 157 /// This implies that one loop is nested in the other, because they must |
| 158 /// both be in scope at that point. |
| 159 Continuation _markInnerLoop(Continuation c1, Continuation c2) { |
| 160 assert(c1 == null || c1.isRecursive); |
| 161 assert(c2 == null || c2.isRecursive); |
| 162 if (c1 == null) return c2; |
| 163 if (c2 == null) return c1; |
| 164 if (c1 == c2) return c1; |
| 165 if (loopDepth[c1] > loopDepth[c2]) { |
| 166 loopTarget[c1] = _markInnerLoop(loopTarget[c1], c2); |
| 167 return c1; |
| 168 } else { |
| 169 loopTarget[c2] = _markInnerLoop(loopTarget[c2], c1); |
| 170 return c2; |
| 171 } |
| 172 } |
| 173 |
| 174 /// Analyzes the body of [cont] and returns the innermost loop |
| 175 /// that can be invoked recursively from [cont] (other than [cont] itself). |
| 176 /// |
| 177 /// [catchLoop] is the innermost loop that can be invoked recursively |
| 178 /// from the current exception handler. |
| 179 Continuation _processContinuation(Continuation cont, Continuation catchLoop) { |
| 180 if (cont.isRecursive) { |
| 181 ++currentDepth; |
| 182 loopDepth[cont] = currentDepth; |
| 183 Continuation target = _processBlock(cont.body, catchLoop); |
| 184 _markInnerLoop(loopTarget[cont], target); |
| 185 --currentDepth; |
| 186 } else { |
| 187 loopTarget[cont] = _processBlock(cont.body, catchLoop); |
| 188 } |
| 189 return loopTarget[cont]; |
| 190 } |
| 191 |
| 192 bool _isCallContinuation(Continuation cont) { |
| 193 return cont.hasExactlyOneUse && cont.firstRef.parent is CallExpression; |
| 194 } |
| 195 |
| 196 /// Analyzes a basic block and returns the innermost loop that |
| 197 /// can be invoked recursively from that block. |
| 198 Continuation _processBlock(Expression node, Continuation catchLoop) { |
| 199 List<Continuation> callContinuations = <Continuation>[]; |
| 200 for (; node is! TailExpression; node = node.next) { |
| 201 if (node is LetCont) { |
| 202 for (Continuation cont in node.continuations) { |
| 203 if (!_isCallContinuation(cont)) { |
| 204 // Process non-call continuations at the binding site, so they |
| 205 // their loop target is known at all use sites. |
| 206 _processContinuation(cont, catchLoop); |
| 207 } else { |
| 208 // To avoid deep recursion, do not analyze call continuations |
| 209 // recursively. This basic block traversal steps into the |
| 210 // call contiunation after visiting its use site. We store the |
| 211 // continuations in a list so we can set the loop target once |
| 212 // it is known. |
| 213 callContinuations.add(cont); |
| 214 } |
| 215 } |
| 216 } else if (node is LetHandler) { |
| 217 catchLoop = _processContinuation(node.handler, catchLoop); |
| 218 } |
| 219 } |
| 220 Continuation target; |
| 221 if (node is InvokeContinuation) { |
| 222 if (node.isRecursive) { |
| 223 target = node.continuation.definition; |
| 224 } else { |
| 225 target = loopTarget[node.continuation.definition]; |
| 226 } |
| 227 } else if (node is Branch) { |
| 228 target = _markInnerLoop( |
| 229 loopTarget[node.trueContinuation.definition], |
| 230 loopTarget[node.falseContinuation.definition]); |
| 231 } else { |
| 232 assert(node is Unreachable || node is Throw); |
| 233 } |
| 234 target = _markInnerLoop(target, catchLoop); |
| 235 for (Continuation cont in callContinuations) { |
| 236 // Store the loop target on each call continuation in the basic block. |
| 237 // Because we walk over call continuations as part of the basic block |
| 238 // traversal, these do not get their loop target set otherwise. |
| 239 loopTarget[cont] = target; |
| 240 } |
| 241 return target; |
| 242 } |
| 243 } |
OLD | NEW |