| 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 tree_ir.optimization.pull_into_initializers; | |
| 6 | |
| 7 import '../tree_ir_nodes.dart'; | |
| 8 import 'optimization.dart' show Pass; | |
| 9 | |
| 10 /// Where a variable has been assigned. | |
| 11 enum AssignArea { | |
| 12 /// The variable is only assigned in the initializer block. | |
| 13 Initializer, | |
| 14 | |
| 15 // The variable has at least one assignment outside the initializer block. | |
| 16 Anywhere, | |
| 17 } | |
| 18 | |
| 19 /// Pulls assignment expressions to the top of the function body so they can be | |
| 20 /// translated into declaration-site variable initializaters. | |
| 21 /// | |
| 22 /// This reverts the assignment expression propagation performed by | |
| 23 /// [StatementRewriter] in cases where it not beneficial. | |
| 24 /// | |
| 25 /// EXAMPLE: | |
| 26 /// | |
| 27 /// var x = foo(), | |
| 28 /// y = bar(x); | |
| 29 /// | |
| 30 /// ==> [StatementRewriter] | |
| 31 /// | |
| 32 /// var x, | |
| 33 /// y = bar(x = foo()); | |
| 34 /// | |
| 35 /// ==> [PullIntoInitializers] restores the initializer for x | |
| 36 /// | |
| 37 /// var x = foo(), | |
| 38 /// y = bar(x); | |
| 39 /// | |
| 40 /// | |
| 41 /// Sometimes the assignment propagation will trigger another optimization | |
| 42 /// in the [StatementRewriter] which then prevents [PullIntoInitializers] from | |
| 43 /// restoring the initializer. This is acceptable, since most optimizations | |
| 44 /// at that level are better than restoring an initializer. | |
| 45 /// | |
| 46 /// EXAMPLE: | |
| 47 /// | |
| 48 /// var x = foo(), | |
| 49 /// y = bar(); | |
| 50 /// baz(x, y, y); | |
| 51 /// | |
| 52 /// ==> [StatementRewriter] | |
| 53 /// | |
| 54 /// var y; | |
| 55 /// baz(foo(), y = bar(), y); | |
| 56 /// | |
| 57 /// [PullIntoInitializers] cannot pull `y` into an initializer because | |
| 58 /// the impure expressions `foo()` and `bar()` would then be swapped. | |
| 59 /// | |
| 60 class PullIntoInitializers extends RecursiveTransformer implements Pass { | |
| 61 String get passName => 'Pull into initializers'; | |
| 62 | |
| 63 /// Denotes where each variable is currently assigned. | |
| 64 /// | |
| 65 /// Variables without assignments are absent from the map. | |
| 66 Map<Variable, AssignArea> assignArea = <Variable, AssignArea>{}; | |
| 67 | |
| 68 /// The fragment between [first] and [last] holds the statements | |
| 69 /// we pulled into the initializer block. | |
| 70 /// | |
| 71 /// The "initializer block" is a sequence of [ExpressionStatement]s with | |
| 72 /// [Assign]s that we create in the beginning of the body, with the intent | |
| 73 /// that code generation will convert them to variable initializers. | |
| 74 /// | |
| 75 /// The block is empty when both are `null`. | |
| 76 Statement first, last; | |
| 77 | |
| 78 /// The number of impure expressions separating the current program point | |
| 79 /// from the initializer block. | |
| 80 /// | |
| 81 /// A pure expression is an expression that cannot throw, diverge, have side | |
| 82 /// effects, or depend on mutable state. | |
| 83 /// | |
| 84 /// As a special case, variable uses are also considered pure when their only | |
| 85 /// reaching definition is an assignment in the initializer block. | |
| 86 int impureCounter = 0; | |
| 87 | |
| 88 /// The number of assignments separating the current program point from the | |
| 89 /// initializer block. Note that these are also counted as impure expressions. | |
| 90 /// | |
| 91 /// Assignments are given special treatment because hoisting an assignment | |
| 92 /// may change the reaching definitions of a variable use. The analysis may | |
| 93 /// already have considered such a use to be pure, and we must then ensure | |
| 94 /// that it remains pure. | |
| 95 int assignCounter = 0; | |
| 96 | |
| 97 /// The number of branch points separating the current program point from | |
| 98 /// the initializer block. | |
| 99 /// | |
| 100 /// We do not pull expressions out of branches, not even pure ones, but | |
| 101 /// we sometimes want to traverse branches to check if they are pure. | |
| 102 int branchCounter = 0; | |
| 103 | |
| 104 /// Appends a statement to the initializer block. | |
| 105 void append(Statement node) { | |
| 106 if (first == null) { | |
| 107 first = last = node; | |
| 108 } else { | |
| 109 last.next = node; | |
| 110 last = node; | |
| 111 } | |
| 112 } | |
| 113 | |
| 114 void rewrite(FunctionDefinition node) { | |
| 115 for (Variable param in node.parameters) { | |
| 116 assignArea[param] = AssignArea.Initializer; | |
| 117 } | |
| 118 Statement body = visitStatement(node.body); | |
| 119 append(body); | |
| 120 assert(first != null); | |
| 121 node.body = first; | |
| 122 } | |
| 123 | |
| 124 void destroyVariableUse(VariableUse node) { | |
| 125 --node.variable.readCount; | |
| 126 } | |
| 127 | |
| 128 Statement visitExpressionStatement(ExpressionStatement node) { | |
| 129 node.expression = visitExpression(node.expression); | |
| 130 if (node.expression is VariableUse) { | |
| 131 // The entire expression was pulled into an initializer. | |
| 132 // This can happen when the expression was an assignment that was | |
| 133 // pulled into the initializer block and replaced by a variable use. | |
| 134 // Discard the statement and try to pull in more initializers from | |
| 135 // the next statement. | |
| 136 destroyVariableUse(node.expression); | |
| 137 return visitStatement(node.next); | |
| 138 } | |
| 139 node.next = visitStatement(node.next); | |
| 140 return node; | |
| 141 } | |
| 142 | |
| 143 Statement visitIf(If node) { | |
| 144 node.condition = visitExpression(node.condition); | |
| 145 // We could traverse the branches and pull out pure expressions, but | |
| 146 // some pure expressions might be too slow for this to pay off. | |
| 147 // A CPS transform should decide when things get hoisted out of branches. | |
| 148 return node; | |
| 149 } | |
| 150 | |
| 151 Statement visitLabeledStatement(LabeledStatement node) { | |
| 152 node.body = visitStatement(node.body); | |
| 153 // The 'next' statement might not always get reached, so do not try to | |
| 154 // pull expressions up from there. | |
| 155 return node; | |
| 156 } | |
| 157 | |
| 158 Statement visitWhileTrue(WhileTrue node) { | |
| 159 return node; | |
| 160 } | |
| 161 | |
| 162 Statement visitFor(For node) { | |
| 163 return node; | |
| 164 } | |
| 165 | |
| 166 Statement visitTry(Try node) { | |
| 167 return node; | |
| 168 } | |
| 169 | |
| 170 Statement visitReceiverCheck(ReceiverCheck node) { | |
| 171 if (node.condition != null) { | |
| 172 node.condition = visitExpression(node.condition); | |
| 173 // The value occurs in conditional context, so don't pull from that. | |
| 174 } else { | |
| 175 node.value = visitExpression(node.value); | |
| 176 } | |
| 177 return node; | |
| 178 } | |
| 179 | |
| 180 Expression visitAssign(Assign node) { | |
| 181 bool inImpureContext = impureCounter > 0; | |
| 182 bool inBranch = branchCounter > 0; | |
| 183 | |
| 184 // Remember the number of impure expression seen yet, so we can tell if | |
| 185 // there are any impure expressions on the right-hand side. | |
| 186 int impureBefore = impureCounter; | |
| 187 int assignmentsBefore = assignCounter; | |
| 188 node.value = visitExpression(node.value); | |
| 189 bool rightHandSideIsImpure = (impureCounter > impureBefore); | |
| 190 bool rightHandSideHasAssign = (assignCounter > assignmentsBefore); | |
| 191 | |
| 192 bool alreadyAssigned = assignArea.containsKey(node.variable); | |
| 193 | |
| 194 // An impure right-hand side cannot be pulled out of impure context. | |
| 195 // Expressions should not be pulled out of branches. | |
| 196 // If this is not the first assignment, it cannot be hoisted. | |
| 197 // If the right-hand side contains an unhoistable assignment, this | |
| 198 // assignment cannot be hoisted either. | |
| 199 if (inImpureContext && rightHandSideIsImpure || | |
| 200 inBranch || | |
| 201 alreadyAssigned || | |
| 202 rightHandSideHasAssign) { | |
| 203 assignArea[node.variable] = AssignArea.Anywhere; | |
| 204 ++impureCounter; | |
| 205 ++assignCounter; | |
| 206 return node; | |
| 207 } | |
| 208 | |
| 209 // Pull the assignment into the initializer. Any side-effects in the | |
| 210 // right-hand side will move into the initializer block, so reset the | |
| 211 // impure counter. | |
| 212 assignArea[node.variable] = AssignArea.Initializer; | |
| 213 impureCounter = impureBefore; | |
| 214 append(new ExpressionStatement(node, null)); | |
| 215 return new VariableUse(node.variable); | |
| 216 } | |
| 217 | |
| 218 Expression visitVariableUse(VariableUse node) { | |
| 219 if (assignArea[node.variable] == AssignArea.Anywhere) { | |
| 220 // There is a reaching definition outside the initializer block. | |
| 221 ++impureCounter; | |
| 222 } | |
| 223 return node; | |
| 224 } | |
| 225 | |
| 226 void rewriteList(List<Expression> nodes) { | |
| 227 for (int i = 0; i < nodes.length; ++i) { | |
| 228 nodes[i] = visitExpression(nodes[i]); | |
| 229 } | |
| 230 } | |
| 231 | |
| 232 Expression visitInvokeMethod(InvokeMethod node) { | |
| 233 node.receiver = visitExpression(node.receiver); | |
| 234 if (!node.receiverIsNotNull) { | |
| 235 // If the receiver is null, the method lookup throws. | |
| 236 ++impureCounter; | |
| 237 } | |
| 238 rewriteList(node.arguments); | |
| 239 ++impureCounter; | |
| 240 return node; | |
| 241 } | |
| 242 | |
| 243 Expression visitInvokeStatic(InvokeStatic node) { | |
| 244 super.visitInvokeStatic(node); | |
| 245 ++impureCounter; | |
| 246 return node; | |
| 247 } | |
| 248 | |
| 249 Expression visitInvokeMethodDirectly(InvokeMethodDirectly node) { | |
| 250 super.visitInvokeMethodDirectly(node); | |
| 251 ++impureCounter; | |
| 252 return node; | |
| 253 } | |
| 254 | |
| 255 Expression visitInvokeConstructor(InvokeConstructor node) { | |
| 256 super.visitInvokeConstructor(node); | |
| 257 ++impureCounter; | |
| 258 return node; | |
| 259 } | |
| 260 | |
| 261 Expression visitOneShotInterceptor(OneShotInterceptor node) { | |
| 262 super.visitOneShotInterceptor(node); | |
| 263 ++impureCounter; | |
| 264 return node; | |
| 265 } | |
| 266 | |
| 267 Expression visitAwait(Await node) { | |
| 268 super.visitAwait(node); | |
| 269 ++impureCounter; | |
| 270 return node; | |
| 271 } | |
| 272 | |
| 273 Expression visitConditional(Conditional node) { | |
| 274 node.condition = visitExpression(node.condition); | |
| 275 // Visit the branches to detect impure subexpressions, but do not pull | |
| 276 // expressions out of the branch. | |
| 277 ++branchCounter; | |
| 278 node.thenExpression = visitExpression(node.thenExpression); | |
| 279 node.elseExpression = visitExpression(node.elseExpression); | |
| 280 --branchCounter; | |
| 281 return node; | |
| 282 } | |
| 283 | |
| 284 Expression visitLogicalOperator(LogicalOperator node) { | |
| 285 node.left = visitExpression(node.left); | |
| 286 ++branchCounter; | |
| 287 node.right = visitExpression(node.right); | |
| 288 --branchCounter; | |
| 289 return node; | |
| 290 } | |
| 291 | |
| 292 Expression visitLiteralList(LiteralList node) { | |
| 293 super.visitLiteralList(node); | |
| 294 if (node.type != null) { | |
| 295 ++impureCounter; // Type casts can throw. | |
| 296 } | |
| 297 return node; | |
| 298 } | |
| 299 | |
| 300 Expression visitTypeOperator(TypeOperator node) { | |
| 301 super.visitTypeOperator(node); | |
| 302 if (!node.isTypeTest) { | |
| 303 ++impureCounter; // Type casts can throw. | |
| 304 } | |
| 305 return node; | |
| 306 } | |
| 307 | |
| 308 Expression visitGetField(GetField node) { | |
| 309 super.visitGetField(node); | |
| 310 ++impureCounter; | |
| 311 return node; | |
| 312 } | |
| 313 | |
| 314 Expression visitSetField(SetField node) { | |
| 315 super.visitSetField(node); | |
| 316 ++impureCounter; | |
| 317 return node; | |
| 318 } | |
| 319 | |
| 320 Expression visitGetStatic(GetStatic node) { | |
| 321 ++impureCounter; | |
| 322 return node; | |
| 323 } | |
| 324 | |
| 325 Expression visitSetStatic(SetStatic node) { | |
| 326 super.visitSetStatic(node); | |
| 327 ++impureCounter; | |
| 328 return node; | |
| 329 } | |
| 330 | |
| 331 Expression visitGetTypeTestProperty(GetTypeTestProperty node) { | |
| 332 super.visitGetTypeTestProperty(node); | |
| 333 return node; | |
| 334 } | |
| 335 | |
| 336 Expression visitGetLength(GetLength node) { | |
| 337 super.visitGetLength(node); | |
| 338 ++impureCounter; | |
| 339 return node; | |
| 340 } | |
| 341 | |
| 342 Expression visitGetIndex(GetIndex node) { | |
| 343 super.visitGetIndex(node); | |
| 344 ++impureCounter; | |
| 345 return node; | |
| 346 } | |
| 347 | |
| 348 Expression visitSetIndex(SetIndex node) { | |
| 349 super.visitSetIndex(node); | |
| 350 ++impureCounter; | |
| 351 return node; | |
| 352 } | |
| 353 | |
| 354 Expression visitApplyBuiltinOperator(ApplyBuiltinOperator node) { | |
| 355 rewriteList(node.arguments); | |
| 356 return node; | |
| 357 } | |
| 358 | |
| 359 Expression visitApplyBuiltinMethod(ApplyBuiltinMethod node) { | |
| 360 node.receiver = visitExpression(node.receiver); | |
| 361 if (!node.receiverIsNotNull) { | |
| 362 // If the receiver is null, the method lookup throws. | |
| 363 ++impureCounter; | |
| 364 } | |
| 365 rewriteList(node.arguments); | |
| 366 ++impureCounter; | |
| 367 return node; | |
| 368 } | |
| 369 | |
| 370 @override | |
| 371 Expression visitForeignExpression(ForeignExpression node) { | |
| 372 rewriteList(node.arguments); | |
| 373 if (node.nativeBehavior.sideEffects.hasSideEffects()) { | |
| 374 ++impureCounter; | |
| 375 } | |
| 376 return node; | |
| 377 } | |
| 378 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
