| 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.loop_hierarchy; | |
| 6 | |
| 7 import 'cps_fragment.dart'; | |
| 8 import 'cps_ir_nodes.dart'; | |
| 9 | |
| 10 /// Determines the effective nesting of loops. | |
| 11 /// | |
| 12 /// The effective nesting of loops is different from the lexical nesting, since | |
| 13 /// recursive continuations can generally contain all the code following | |
| 14 /// after the loop in addition to the looping code itself. | |
| 15 /// | |
| 16 /// For example, the 'else' branch below is not effectively part of the loop: | |
| 17 /// | |
| 18 /// let rec kont x = | |
| 19 /// if (<loop condition>) | |
| 20 /// <loop body> | |
| 21 /// InvokeContinuation kont x' | |
| 22 /// else | |
| 23 /// <after loop> | |
| 24 /// return p.foo() | |
| 25 /// | |
| 26 /// We use the term "loop" to mean recursive continuation. | |
| 27 /// The `null` value is used to represent a context not part of any loop. | |
| 28 class LoopHierarchy { | |
| 29 /// Nesting depth of the given loop. | |
| 30 Map<Continuation, int> loopDepth = <Continuation, int>{}; | |
| 31 | |
| 32 /// The innermost loop (other than itself) that may be invoked recursively | |
| 33 /// as a result of invoking the given continuation. | |
| 34 Map<Continuation, Continuation> loopTarget = <Continuation, Continuation>{}; | |
| 35 | |
| 36 /// Current nesting depth. | |
| 37 int _currentDepth = 0; | |
| 38 | |
| 39 /// The loop target to use for missing code. Used by [update]. | |
| 40 Continuation _exitLoop; | |
| 41 | |
| 42 /// Computes the loop hierarchy for the given function. | |
| 43 /// | |
| 44 /// Parent pointers must be computed for [node]. | |
| 45 LoopHierarchy(FunctionDefinition node) { | |
| 46 _processBlock(node.body, null); | |
| 47 } | |
| 48 | |
| 49 /// Returns the innermost loop which [cont] is effectively part of. | |
| 50 Continuation getLoopHeader(Continuation cont) { | |
| 51 return cont.isRecursive ? cont : loopTarget[cont]; | |
| 52 } | |
| 53 | |
| 54 /// Returns the innermost loop which the given continuation is part of, other | |
| 55 /// than itself. | |
| 56 Continuation getEnclosingLoop(Continuation cont) { | |
| 57 return loopTarget[cont]; | |
| 58 } | |
| 59 | |
| 60 /// Marks the innermost loop as a subloop of the other loop. | |
| 61 /// | |
| 62 /// Returns the innermost loop. | |
| 63 /// | |
| 64 /// Both continuations, [c1] and [c2] may be null (i.e. no loop). | |
| 65 /// | |
| 66 /// A loop is said to be a subloop of an enclosing loop if it can invoke | |
| 67 /// that loop recursively. This information is stored in [loopTarget]. | |
| 68 /// | |
| 69 /// This method is only invoked with two distinct loops if there is a | |
| 70 /// point that can reach a recursive invocation of both loops. | |
| 71 /// This implies that one loop is nested in the other, because they must | |
| 72 /// both be in scope at that point. | |
| 73 Continuation _markInnerLoop(Continuation c1, Continuation c2) { | |
| 74 assert(c1 == null || c1.isRecursive); | |
| 75 assert(c2 == null || c2.isRecursive); | |
| 76 if (c1 == null) return c2; | |
| 77 if (c2 == null) return c1; | |
| 78 if (c1 == c2) return c1; | |
| 79 if (loopDepth[c1] > loopDepth[c2]) { | |
| 80 loopTarget[c1] = _markInnerLoop(loopTarget[c1], c2); | |
| 81 return c1; | |
| 82 } else { | |
| 83 loopTarget[c2] = _markInnerLoop(loopTarget[c2], c1); | |
| 84 return c2; | |
| 85 } | |
| 86 } | |
| 87 | |
| 88 /// Analyzes the body of [cont] and returns the innermost loop | |
| 89 /// that can be invoked recursively from [cont] (other than [cont] itself). | |
| 90 /// | |
| 91 /// [catchLoop] is the innermost loop that can be invoked recursively | |
| 92 /// from the current exception handler. | |
| 93 Continuation _processContinuation(Continuation cont, Continuation catchLoop) { | |
| 94 if (cont.isRecursive) { | |
| 95 ++_currentDepth; | |
| 96 loopDepth[cont] = _currentDepth; | |
| 97 Continuation target = _processBlock(cont.body, catchLoop); | |
| 98 _markInnerLoop(loopTarget[cont], target); | |
| 99 --_currentDepth; | |
| 100 } else { | |
| 101 loopTarget[cont] = _processBlock(cont.body, catchLoop); | |
| 102 } | |
| 103 return loopTarget[cont]; | |
| 104 } | |
| 105 | |
| 106 /// Analyzes a basic block and returns the innermost loop that | |
| 107 /// can be invoked recursively from that block. | |
| 108 Continuation _processBlock(Expression node, Continuation catchLoop) { | |
| 109 for (; node != null && node is! TailExpression; node = node.next) { | |
| 110 if (node is LetCont) { | |
| 111 for (Continuation cont in node.continuations) { | |
| 112 _processContinuation(cont, catchLoop); | |
| 113 } | |
| 114 } else if (node is LetHandler) { | |
| 115 catchLoop = _processContinuation(node.handler, catchLoop); | |
| 116 } | |
| 117 } | |
| 118 Continuation target; | |
| 119 if (node is InvokeContinuation) { | |
| 120 if (node.isRecursive) { | |
| 121 target = node.continuation; | |
| 122 } else { | |
| 123 target = loopTarget[node.continuation]; | |
| 124 } | |
| 125 } else if (node is Branch) { | |
| 126 target = _markInnerLoop(loopTarget[node.trueContinuation], | |
| 127 loopTarget[node.falseContinuation]); | |
| 128 } else if (node == null) { | |
| 129 // If the code ends abruptly, use the exit loop provided in [update]. | |
| 130 target = _exitLoop; | |
| 131 } else { | |
| 132 assert(node is Unreachable || node is Throw || node == null); | |
| 133 } | |
| 134 return _markInnerLoop(target, catchLoop); | |
| 135 } | |
| 136 | |
| 137 /// Returns the innermost loop that effectively encloses both | |
| 138 /// c1 and c2 (or `null` if there is no such loop). | |
| 139 Continuation lowestCommonAncestor(Continuation c1, Continuation c2) { | |
| 140 int d1 = getDepth(c1), d2 = getDepth(c2); | |
| 141 while (c1 != c2) { | |
| 142 if (d1 <= d2) { | |
| 143 c2 = getEnclosingLoop(c2); | |
| 144 d2 = getDepth(c2); | |
| 145 } else { | |
| 146 c1 = getEnclosingLoop(c1); | |
| 147 d1 = getDepth(c1); | |
| 148 } | |
| 149 } | |
| 150 return c1; | |
| 151 } | |
| 152 | |
| 153 /// Returns the lexical nesting depth of [loop]. | |
| 154 int getDepth(Continuation loop) { | |
| 155 if (loop == null) return 0; | |
| 156 return loopDepth[loop]; | |
| 157 } | |
| 158 | |
| 159 /// Sets the loop header for each continuation bound inside the given | |
| 160 /// fragment. | |
| 161 /// | |
| 162 /// If the fragment is open, [exitLoop] denotes the loop header for | |
| 163 /// the code that will occur after the fragment. | |
| 164 /// | |
| 165 /// [catchLoop] is the loop target for the catch clause of the try/catch | |
| 166 /// surrounding the inserted fragment. | |
| 167 void update(CpsFragment fragment, | |
| 168 {Continuation exitLoop, Continuation catchLoop}) { | |
| 169 if (fragment.isEmpty) return; | |
| 170 _exitLoop = exitLoop; | |
| 171 _currentDepth = getDepth(exitLoop); | |
| 172 _processBlock(fragment.root, catchLoop); | |
| 173 _exitLoop = null; | |
| 174 } | |
| 175 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
