| 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.gvn; | |
| 6 | |
| 7 import '../compiler.dart' show Compiler; | |
| 8 import '../elements/elements.dart'; | |
| 9 import '../js_backend/js_backend.dart' show JavaScriptBackend; | |
| 10 import '../world.dart'; | |
| 11 import 'cps_ir_nodes.dart'; | |
| 12 import 'effects.dart'; | |
| 13 import 'loop_effects.dart'; | |
| 14 import 'loop_hierarchy.dart'; | |
| 15 import 'optimizers.dart' show Pass; | |
| 16 import 'type_mask_system.dart'; | |
| 17 | |
| 18 /// Eliminates redundant primitives by reusing the value of another primitive | |
| 19 /// that is known to have the same result. Primitives are also hoisted out of | |
| 20 /// loops when possible. | |
| 21 /// | |
| 22 /// Reusing values can introduce new temporaries, which in some cases is more | |
| 23 /// expensive than recomputing the value on-demand. For example, pulling an | |
| 24 /// expression such as "n+1" out of a loop is generally not worth it. | |
| 25 /// Such primitives are said to be "trivial". | |
| 26 /// | |
| 27 /// Trivial primitives are shared on-demand, i.e. they are only shared if | |
| 28 /// this enables a non-trivial primitive to be hoisted out of a loop. | |
| 29 // | |
| 30 // TODO(asgerf): Enable hoisting across refinement guards when this is safe: | |
| 31 // - Determine the type required for a given primitive to be "safe" | |
| 32 // - Recompute the type of a primitive after hoisting. | |
| 33 // E.g. GetIndex on a String can become a GetIndex on an arbitrary | |
| 34 // indexable, which is still safe but the type may change | |
| 35 // - Since the new type may be worse, insert a refinement at the old | |
| 36 // definition site, so we do not degrade existing type information. | |
| 37 // | |
| 38 class GVN extends TrampolineRecursiveVisitor implements Pass { | |
| 39 String get passName => 'GVN'; | |
| 40 | |
| 41 final Compiler compiler; | |
| 42 final TypeMaskSystem types; | |
| 43 JavaScriptBackend get backend => compiler.backend; | |
| 44 World get world => compiler.world; | |
| 45 | |
| 46 final GvnTable gvnTable = new GvnTable(); | |
| 47 GvnVectorBuilder gvnVectorBuilder; | |
| 48 LoopHierarchy loopHierarchy; | |
| 49 LoopSideEffects loopEffects; | |
| 50 | |
| 51 final EffectNumberer effectNumberer = new EffectNumberer(); | |
| 52 | |
| 53 /// Effect numbers at the given join point. | |
| 54 Map<Continuation, EffectNumbers> effectsAt = <Continuation, EffectNumbers>{}; | |
| 55 | |
| 56 /// The effect numbers at the current position (during traversal). | |
| 57 EffectNumbers effectNumbers; | |
| 58 | |
| 59 /// The loop currently enclosing the binding of a given primitive. | |
| 60 final Map<Primitive, Continuation> loopHeaderFor = | |
| 61 <Primitive, Continuation>{}; | |
| 62 | |
| 63 /// The GVNs for primitives that have been hoisted outside the given loop. | |
| 64 /// | |
| 65 /// These should be removed from the environment when exiting the loop. | |
| 66 final Map<Continuation, List<int>> loopHoistedBindings = | |
| 67 <Continuation, List<int>>{}; | |
| 68 | |
| 69 /// Maps GVNs to a currently-in-scope binding for that value. | |
| 70 final Map<int, Primitive> environment = <int, Primitive>{}; | |
| 71 | |
| 72 /// Maps GVN'able primitives to their global value number. | |
| 73 final Map<Primitive, int> gvnFor = <Primitive, int>{}; | |
| 74 | |
| 75 Continuation currentLoopHeader; | |
| 76 | |
| 77 GVN(this.compiler, this.types); | |
| 78 | |
| 79 void rewrite(FunctionDefinition node) { | |
| 80 effectNumbers = new EffectNumbers.fresh(effectNumberer); | |
| 81 gvnVectorBuilder = new GvnVectorBuilder(gvnFor, compiler, types); | |
| 82 loopHierarchy = new LoopHierarchy(node); | |
| 83 loopEffects = | |
| 84 new LoopSideEffects(node, world, loopHierarchy: loopHierarchy); | |
| 85 visit(node); | |
| 86 } | |
| 87 | |
| 88 // ------------------ GLOBAL VALUE NUMBERING --------------------- | |
| 89 | |
| 90 /// True if [prim] can be eliminated if its value is already in scope. | |
| 91 bool canReplaceWithExistingValue(Primitive prim) { | |
| 92 // Primitives that have no side effects other than potentially throwing are | |
| 93 // known not the throw if the value is already in scope. Handling those | |
| 94 // specially is equivalent to updating refinements during GVN. | |
| 95 // GetLazyStatic cannot have side effects because the field has already | |
| 96 // been initialized. | |
| 97 return prim.isSafeForElimination || | |
| 98 prim is GetField || | |
| 99 prim is GetLength || | |
| 100 prim is GetIndex || | |
| 101 prim is GetLazyStatic; | |
| 102 } | |
| 103 | |
| 104 @override | |
| 105 Expression traverseLetPrim(LetPrim node) { | |
| 106 Expression next = node.body; | |
| 107 Primitive prim = node.primitive; | |
| 108 | |
| 109 loopHeaderFor[prim] = currentLoopHeader; | |
| 110 | |
| 111 if (prim is Refinement) { | |
| 112 // Do not share refinements (they have no runtime or code size cost), and | |
| 113 // do not put them in the GVN table because GvnVectorBuilder unfolds | |
| 114 // refinements by itself. | |
| 115 return next; | |
| 116 } | |
| 117 | |
| 118 // Update effect numbers due to side effects from a static initializer. | |
| 119 // GetLazyStatic is GVN'ed like a GetStatic, but the effects of the static | |
| 120 // initializer occur before reading the field. | |
| 121 if (prim is GetLazyStatic) { | |
| 122 addSideEffectsOfPrimitive(prim); | |
| 123 } | |
| 124 | |
| 125 // Compute the GVN vector for this computation. | |
| 126 List vector = gvnVectorBuilder.make(prim, effectNumbers); | |
| 127 | |
| 128 // Update effect numbers due to side effects. | |
| 129 // Do this after computing the GVN vector so the primitive's GVN is not | |
| 130 // influenced by its own side effects, except in the case of GetLazyStatic. | |
| 131 if (prim is! GetLazyStatic) { | |
| 132 addSideEffectsOfPrimitive(prim); | |
| 133 } | |
| 134 | |
| 135 if (vector == null) { | |
| 136 // The primitive is not GVN'able. Move on. | |
| 137 return next; | |
| 138 } | |
| 139 | |
| 140 // Compute the GVN for this primitive. | |
| 141 int gvn = gvnTable.insert(vector); | |
| 142 gvnFor[prim] = gvn; | |
| 143 | |
| 144 // Try to reuse a previously computed value with the same GVN. | |
| 145 Primitive existing = environment[gvn]; | |
| 146 if (existing != null && | |
| 147 canReplaceWithExistingValue(prim) && | |
| 148 !isFastConstant(prim)) { | |
| 149 if (prim is Interceptor) { | |
| 150 Interceptor interceptor = existing; | |
| 151 interceptor.interceptedClasses.addAll(prim.interceptedClasses); | |
| 152 } | |
| 153 prim | |
| 154 ..replaceUsesWith(existing) | |
| 155 ..destroy(); | |
| 156 node.remove(); | |
| 157 return next; | |
| 158 } | |
| 159 | |
| 160 if (tryToHoistOutOfLoop(prim, gvn)) { | |
| 161 return next; | |
| 162 } | |
| 163 | |
| 164 // The primitive could not be hoisted. Put the primitive in the | |
| 165 // environment while processing the body of the LetPrim. | |
| 166 environment[gvn] = prim; | |
| 167 pushAction(() { | |
| 168 assert(environment[gvn] == prim); | |
| 169 environment[gvn] = existing; | |
| 170 }); | |
| 171 | |
| 172 return next; | |
| 173 } | |
| 174 | |
| 175 bool isFirstImpureExpressionInLoop(Expression exp) { | |
| 176 InteriorNode node = exp.parent; | |
| 177 for (; node is Expression; node = node.parent) { | |
| 178 if (node is LetPrim && node.primitive.isSafeForElimination) { | |
| 179 continue; | |
| 180 } | |
| 181 if (node is LetCont) { | |
| 182 continue; | |
| 183 } | |
| 184 return false; | |
| 185 } | |
| 186 return node == currentLoopHeader; | |
| 187 } | |
| 188 | |
| 189 bool isHoistablePrimitive(Primitive prim) { | |
| 190 if (prim.isSafeForElimination) return true; | |
| 191 if (prim is ReceiverCheck || | |
| 192 prim is BoundsCheck || | |
| 193 prim is GetLength || | |
| 194 prim is GetField || | |
| 195 prim is GetIndex) { | |
| 196 // Expressions that potentially throw but have no other effects can be | |
| 197 // hoisted if they occur as the first impure expression in a loop. | |
| 198 // Note regarding BoundsCheck: the current array length is an input to | |
| 199 // check, so the check itself has no heap dependency. It will only be | |
| 200 // hoisted if the length was hoisted. | |
| 201 // TODO(asgerf): In general we could hoist these out of multiple loops, | |
| 202 // but the trick we use here only works for one loop level. | |
| 203 return isFirstImpureExpressionInLoop(prim.parent); | |
| 204 } | |
| 205 return false; | |
| 206 } | |
| 207 | |
| 208 /// Try to hoist the binding of [prim] out of loops. Returns `true` if it was | |
| 209 /// hoisted or marked as a trivial hoist-on-demand primitive. | |
| 210 bool tryToHoistOutOfLoop(Primitive prim, int gvn) { | |
| 211 // Bail out fast if the primitive is not inside a loop. | |
| 212 if (currentLoopHeader == null) return false; | |
| 213 | |
| 214 // Do not hoist primitives with side effects. | |
| 215 if (!isHoistablePrimitive(prim)) return false; | |
| 216 | |
| 217 LetPrim letPrim = prim.parent; | |
| 218 | |
| 219 // Find the depth of the outermost scope where we can bind the primitive | |
| 220 // without bringing a reference out of scope. 0 is the depth of the | |
| 221 // top-level scope. | |
| 222 int hoistDepth = 0; | |
| 223 List<Primitive> inputsHoistedOnDemand = <Primitive>[]; | |
| 224 InputVisitor.forEach(prim, (Reference ref) { | |
| 225 Primitive input = ref.definition; | |
| 226 if (canIgnoreRefinementGuards(prim)) { | |
| 227 input = input.effectiveDefinition; | |
| 228 } | |
| 229 if (isFastConstant(input)) { | |
| 230 // Fast constants can be hoisted all the way out, but should only be | |
| 231 // hoisted if needed to hoist something else. | |
| 232 inputsHoistedOnDemand.add(input); | |
| 233 } else { | |
| 234 Continuation loopHeader = loopHeaderFor[input]; | |
| 235 Continuation referencedLoop = | |
| 236 loopHierarchy.lowestCommonAncestor(loopHeader, currentLoopHeader); | |
| 237 int depth = loopHierarchy.getDepth(referencedLoop); | |
| 238 if (depth > hoistDepth) { | |
| 239 hoistDepth = depth; | |
| 240 } | |
| 241 } | |
| 242 }); | |
| 243 | |
| 244 // Bail out if it can not be hoisted further out than it is now. | |
| 245 if (hoistDepth == loopHierarchy.getDepth(currentLoopHeader)) return false; | |
| 246 | |
| 247 // Walk up the loop hierarchy and check at every step that any heap | |
| 248 // dependencies can safely be hoisted out of the loop. | |
| 249 Continuation enclosingLoop = currentLoopHeader; | |
| 250 Continuation hoistTarget = null; | |
| 251 while (loopHierarchy.getDepth(enclosingLoop) > hoistDepth && | |
| 252 canHoistHeapDependencyOutOfLoop(prim, enclosingLoop)) { | |
| 253 hoistTarget = enclosingLoop; | |
| 254 enclosingLoop = loopHierarchy.getEnclosingLoop(enclosingLoop); | |
| 255 } | |
| 256 | |
| 257 // Bail out if heap dependencies prohibit any hoisting at all. | |
| 258 if (hoistTarget == null) return false; | |
| 259 | |
| 260 if (isFastConstant(prim)) { | |
| 261 // The overhead from introducting a temporary might be greater than | |
| 262 // the overhead of evaluating this primitive at every iteration. | |
| 263 // Only hoist if this enables hoisting of a non-trivial primitive. | |
| 264 return true; | |
| 265 } | |
| 266 | |
| 267 LetCont loopBinding = hoistTarget.parent; | |
| 268 | |
| 269 // The primitive may depend on values that have not yet been | |
| 270 // hoisted as far as they can. Hoist those now. | |
| 271 for (Primitive input in inputsHoistedOnDemand) { | |
| 272 hoistTrivialPrimitive(input, loopBinding, enclosingLoop); | |
| 273 } | |
| 274 | |
| 275 // Hoist the primitive. | |
| 276 letPrim.remove(); | |
| 277 letPrim.insertAbove(loopBinding); | |
| 278 loopHeaderFor[prim] = enclosingLoop; | |
| 279 | |
| 280 // If a refinement guard was bypassed, use the best refinement | |
| 281 // currently in scope. | |
| 282 if (canIgnoreRefinementGuards(prim)) { | |
| 283 int target = loopHierarchy.getDepth(enclosingLoop); | |
| 284 InputVisitor.forEach(prim, (Reference ref) { | |
| 285 Primitive input = ref.definition; | |
| 286 while (input is Refinement) { | |
| 287 Continuation loop = loopHeaderFor[input]; | |
| 288 loop = loopHierarchy.lowestCommonAncestor(loop, currentLoopHeader); | |
| 289 if (loopHierarchy.getDepth(loop) <= target) break; | |
| 290 Refinement refinement = input; | |
| 291 input = refinement.value.definition; | |
| 292 } | |
| 293 ref.changeTo(input); | |
| 294 }); | |
| 295 } | |
| 296 | |
| 297 // Put the primitive in the environment while processing the loop. | |
| 298 environment[gvn] = prim; | |
| 299 loopHoistedBindings.putIfAbsent(hoistTarget, () => <int>[]).add(gvn); | |
| 300 return true; | |
| 301 } | |
| 302 | |
| 303 /// If the given primitive is a trivial primitive that should be hoisted | |
| 304 /// on-demand, hoist it and its dependent values above [loopBinding]. | |
| 305 void hoistTrivialPrimitive( | |
| 306 Primitive prim, LetCont loopBinding, Continuation enclosingLoop) { | |
| 307 assert(isFastConstant(prim)); | |
| 308 | |
| 309 // The primitive might already be bound in an outer scope. Do not relocate | |
| 310 // the primitive unless we are lifting it. For example; | |
| 311 // t1 = a + b | |
| 312 // t2 = t1 + c | |
| 313 // t3 = t1 * t2 | |
| 314 // If it was decided that `t3` should be hoisted, `t1` will be seen twice by | |
| 315 // this method: by the direct reference and by reference through `t2`. | |
| 316 // The second time it is seen, it will already have been moved. | |
| 317 Continuation currentLoop = loopHeaderFor[prim]; | |
| 318 int currentDepth = loopHierarchy.getDepth(currentLoop); | |
| 319 int targetDepth = loopHierarchy.getDepth(enclosingLoop); | |
| 320 if (currentDepth <= targetDepth) return; | |
| 321 | |
| 322 // Hoist the trivial primitives being depended on so they remain in scope. | |
| 323 InputVisitor.forEach(prim, (Reference ref) { | |
| 324 hoistTrivialPrimitive(ref.definition, loopBinding, enclosingLoop); | |
| 325 }); | |
| 326 | |
| 327 // Move the primitive. | |
| 328 LetPrim binding = prim.parent; | |
| 329 binding.remove(); | |
| 330 binding.insertAbove(loopBinding); | |
| 331 loopHeaderFor[prim] = enclosingLoop; | |
| 332 } | |
| 333 | |
| 334 bool canIgnoreRefinementGuards(Primitive primitive) { | |
| 335 return primitive is Interceptor; | |
| 336 } | |
| 337 | |
| 338 /// Returns true if [prim] is a constant that has no significant runtime cost. | |
| 339 bool isFastConstant(Primitive prim) { | |
| 340 return prim is Constant && (prim.value.isPrimitive || prim.value.isDummy); | |
| 341 } | |
| 342 | |
| 343 /// Assuming [prim] has no side effects, returns true if it can safely | |
| 344 /// be hoisted out of [loop] without changing its value or changing the timing | |
| 345 /// of a thrown exception. | |
| 346 bool canHoistHeapDependencyOutOfLoop(Primitive prim, Continuation loop) { | |
| 347 // If the primitive might throw, we have to check that it is the first | |
| 348 // impure expression in the loop. This has already been checked if | |
| 349 // [loop] is the current loop header, but for other loops we just give up. | |
| 350 if (!prim.isSafeForElimination && loop != currentLoopHeader) { | |
| 351 return false; | |
| 352 } | |
| 353 int effects = loopEffects.getSideEffectsInLoop(loop); | |
| 354 return Effects.changesToDepends(effects) & prim.effects == 0; | |
| 355 } | |
| 356 | |
| 357 // ------------------ TRAVERSAL AND EFFECT NUMBERING --------------------- | |
| 358 // | |
| 359 // These methods traverse the IR while updating the current effect numbers. | |
| 360 // They are not specific to GVN. | |
| 361 | |
| 362 void addSideEffectsOfPrimitive(Primitive prim) { | |
| 363 addSideEffects(prim.effects); | |
| 364 } | |
| 365 | |
| 366 void addSideEffects(int effectFlags) { | |
| 367 effectNumbers.change(effectNumberer, effectFlags); | |
| 368 } | |
| 369 | |
| 370 Expression traverseLetHandler(LetHandler node) { | |
| 371 // Assume any kind of side effects may occur in the try block. | |
| 372 effectsAt[node.handler] = new EffectNumbers.fresh(effectNumberer); | |
| 373 push(node.handler); | |
| 374 return node.body; | |
| 375 } | |
| 376 | |
| 377 Expression traverseContinuation(Continuation cont) { | |
| 378 Continuation oldLoopHeader = currentLoopHeader; | |
| 379 currentLoopHeader = loopHierarchy.getLoopHeader(cont); | |
| 380 pushAction(() { | |
| 381 currentLoopHeader = oldLoopHeader; | |
| 382 }); | |
| 383 for (Parameter param in cont.parameters) { | |
| 384 loopHeaderFor[param] = currentLoopHeader; | |
| 385 } | |
| 386 if (cont.isRecursive) { | |
| 387 addSideEffects(loopEffects.getSideEffectsInLoop(cont)); | |
| 388 pushAction(() { | |
| 389 List<int> hoistedBindings = loopHoistedBindings[cont]; | |
| 390 if (hoistedBindings != null) { | |
| 391 hoistedBindings.forEach(environment.remove); | |
| 392 } | |
| 393 }); | |
| 394 } else { | |
| 395 effectNumbers = effectsAt[cont]; | |
| 396 assert(effectNumbers != null); | |
| 397 } | |
| 398 | |
| 399 return cont.body; | |
| 400 } | |
| 401 | |
| 402 void visitInvokeContinuation(InvokeContinuation node) { | |
| 403 Continuation cont = node.continuation; | |
| 404 if (cont.isRecursive) return; | |
| 405 EffectNumbers join = effectsAt[cont]; | |
| 406 if (join == null) { | |
| 407 effectsAt[cont] = effectNumbers.copy(); | |
| 408 } else { | |
| 409 join.join(effectNumberer, effectNumbers); | |
| 410 } | |
| 411 } | |
| 412 | |
| 413 void visitBranch(Branch node) { | |
| 414 Continuation trueCont = node.trueContinuation; | |
| 415 Continuation falseCont = node.falseContinuation; | |
| 416 // Copy the effect number vector once, so the analysis of one branch does | |
| 417 // not influence the other. | |
| 418 effectsAt[trueCont] = effectNumbers; | |
| 419 effectsAt[falseCont] = effectNumbers.copy(); | |
| 420 } | |
| 421 } | |
| 422 | |
| 423 /// Maps vectors to numbers, such that two vectors with the same contents | |
| 424 /// map to the same number. | |
| 425 class GvnTable { | |
| 426 Map<GvnEntry, int> _table = <GvnEntry, int>{}; | |
| 427 int _usedGvns = 0; | |
| 428 int _makeNewGvn() => ++_usedGvns; | |
| 429 | |
| 430 int insert(List vector) { | |
| 431 return _table.putIfAbsent(new GvnEntry(vector), _makeNewGvn); | |
| 432 } | |
| 433 } | |
| 434 | |
| 435 /// Wrapper around a [List] that compares for equality based on contents | |
| 436 /// instead of object identity. | |
| 437 class GvnEntry { | |
| 438 final List vector; | |
| 439 final int hashCode; | |
| 440 | |
| 441 GvnEntry(List vector) | |
| 442 : vector = vector, | |
| 443 hashCode = computeHashCode(vector); | |
| 444 | |
| 445 bool operator ==(other) { | |
| 446 if (other is! GvnEntry) return false; | |
| 447 GvnEntry entry = other; | |
| 448 List otherVector = entry.vector; | |
| 449 if (vector.length != otherVector.length) return false; | |
| 450 for (int i = 0; i < vector.length; ++i) { | |
| 451 if (vector[i] != otherVector[i]) return false; | |
| 452 } | |
| 453 return true; | |
| 454 } | |
| 455 | |
| 456 /// Combines the hash codes of [vector] using Jenkin's hash function, with | |
| 457 /// intermediate results truncated to SMI range. | |
| 458 static int computeHashCode(List vector) { | |
| 459 int hash = 0; | |
| 460 for (int i = 0; i < vector.length; ++i) { | |
| 461 hash = 0x1fffffff & (hash + vector[i].hashCode); | |
| 462 hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10)); | |
| 463 hash = hash ^ (hash >> 6); | |
| 464 } | |
| 465 hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3)); | |
| 466 hash = hash ^ (hash >> 11); | |
| 467 return 0x1fffffff & (hash + ((0x00003fff & hash) << 15)); | |
| 468 } | |
| 469 } | |
| 470 | |
| 471 /// Converts GVN'able primitives to a vector containing all the values | |
| 472 /// to be considered when computing a GVN for it. | |
| 473 /// | |
| 474 /// This includes the instruction type, inputs, effect numbers for any part | |
| 475 /// of the heap being depended on, as well as any instruction-specific payload | |
| 476 /// such as any DartTypes, Elements, and operator kinds. | |
| 477 /// | |
| 478 /// Each `visit` or `process` method for a primitive must initialize [vector] | |
| 479 /// if the primitive is GVN'able and fill in any components except the inputs. | |
| 480 /// The inputs will be filled in by [processReference]. | |
| 481 class GvnVectorBuilder extends DeepRecursiveVisitor { | |
| 482 List vector; | |
| 483 final Map<Primitive, int> gvnFor; | |
| 484 final Compiler compiler; | |
| 485 World get world => compiler.world; | |
| 486 JavaScriptBackend get backend => compiler.backend; | |
| 487 final TypeMaskSystem types; | |
| 488 EffectNumbers effectNumbers; | |
| 489 | |
| 490 GvnVectorBuilder(this.gvnFor, this.compiler, this.types); | |
| 491 | |
| 492 List make(Primitive prim, EffectNumbers effectNumbers) { | |
| 493 this.effectNumbers = effectNumbers; | |
| 494 vector = null; | |
| 495 visit(prim); | |
| 496 return vector; | |
| 497 } | |
| 498 | |
| 499 /// The `process` methods below do not insert the referenced arguments into | |
| 500 /// the vector, but instead rely on them being inserted here. | |
| 501 processReference(Reference ref) { | |
| 502 if (vector == null) return; | |
| 503 Primitive prim = ref.definition.effectiveDefinition; | |
| 504 vector.add(gvnFor[prim] ?? prim); | |
| 505 } | |
| 506 | |
| 507 processTypeTest(TypeTest node) { | |
| 508 vector = [GvnCode.TYPE_TEST, node.dartType]; | |
| 509 } | |
| 510 | |
| 511 processTypeTestViaFlag(TypeTestViaFlag node) { | |
| 512 vector = [GvnCode.TYPE_TEST_VIA_FLAG, node.dartType]; | |
| 513 } | |
| 514 | |
| 515 processApplyBuiltinOperator(ApplyBuiltinOperator node) { | |
| 516 vector = [GvnCode.BUILTIN_OPERATOR, node.operator.index]; | |
| 517 } | |
| 518 | |
| 519 processGetLength(GetLength node) { | |
| 520 if (node.isFinal) { | |
| 521 // Omit the effect number for fixed-length lists. Note that if a the list | |
| 522 // gets refined to a fixed-length type, we still won't be able to GVN a | |
| 523 // GetLength across the refinement, because the first GetLength uses an | |
| 524 // effect number in its vector while the second one does not. | |
| 525 vector = [GvnCode.GET_LENGTH]; | |
| 526 } else { | |
| 527 vector = [GvnCode.GET_LENGTH, effectNumbers.indexableLength]; | |
| 528 } | |
| 529 } | |
| 530 | |
| 531 bool isNativeField(FieldElement field) { | |
| 532 // TODO(asgerf): We should add a GetNativeField instruction. | |
| 533 return backend.isNative(field); | |
| 534 } | |
| 535 | |
| 536 processGetField(GetField node) { | |
| 537 if (isNativeField(node.field)) { | |
| 538 vector = null; // Native field access cannot be GVN'ed. | |
| 539 } else if (node.isFinal) { | |
| 540 vector = [GvnCode.GET_FIELD, node.field]; | |
| 541 } else { | |
| 542 vector = [GvnCode.GET_FIELD, node.field, effectNumbers.instanceField]; | |
| 543 } | |
| 544 } | |
| 545 | |
| 546 processGetIndex(GetIndex node) { | |
| 547 vector = [GvnCode.GET_INDEX, effectNumbers.indexableContent]; | |
| 548 } | |
| 549 | |
| 550 visitGetStatic(GetStatic node) { | |
| 551 if (node.isFinal) { | |
| 552 vector = [GvnCode.GET_STATIC, node.element]; | |
| 553 } else { | |
| 554 vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField]; | |
| 555 } | |
| 556 // Suppress visit to witness argument. | |
| 557 } | |
| 558 | |
| 559 processGetLazyStatic(GetLazyStatic node) { | |
| 560 if (node.isFinal) { | |
| 561 vector = [GvnCode.GET_STATIC, node.element]; | |
| 562 } else { | |
| 563 vector = [GvnCode.GET_STATIC, node.element, effectNumbers.staticField]; | |
| 564 } | |
| 565 } | |
| 566 | |
| 567 processConstant(Constant node) { | |
| 568 vector = [GvnCode.CONSTANT, node.value]; | |
| 569 } | |
| 570 | |
| 571 processReifyRuntimeType(ReifyRuntimeType node) { | |
| 572 vector = [GvnCode.REIFY_RUNTIME_TYPE]; | |
| 573 } | |
| 574 | |
| 575 processReadTypeVariable(ReadTypeVariable node) { | |
| 576 vector = [GvnCode.READ_TYPE_VARIABLE, node.variable]; | |
| 577 } | |
| 578 | |
| 579 processTypeExpression(TypeExpression node) { | |
| 580 vector = [GvnCode.TYPE_EXPRESSION, node.kind.index, node.dartType]; | |
| 581 } | |
| 582 | |
| 583 processInterceptor(Interceptor node) { | |
| 584 vector = [GvnCode.INTERCEPTOR]; | |
| 585 } | |
| 586 } | |
| 587 | |
| 588 class GvnCode { | |
| 589 static const int TYPE_TEST = 1; | |
| 590 static const int TYPE_TEST_VIA_FLAG = 2; | |
| 591 static const int BUILTIN_OPERATOR = 3; | |
| 592 static const int GET_LENGTH = 4; | |
| 593 static const int GET_FIELD = 5; | |
| 594 static const int GET_INDEX = 6; | |
| 595 static const int GET_STATIC = 7; | |
| 596 static const int CONSTANT = 8; | |
| 597 static const int REIFY_RUNTIME_TYPE = 9; | |
| 598 static const int READ_TYPE_VARIABLE = 10; | |
| 599 static const int TYPE_EXPRESSION = 11; | |
| 600 static const int INTERCEPTOR = 12; | |
| 601 } | |
| 602 | |
| 603 typedef ReferenceCallback(Reference ref); | |
| 604 | |
| 605 class InputVisitor extends DeepRecursiveVisitor { | |
| 606 ReferenceCallback callback; | |
| 607 | |
| 608 InputVisitor(this.callback); | |
| 609 | |
| 610 @override | |
| 611 processReference(Reference ref) { | |
| 612 callback(ref); | |
| 613 } | |
| 614 | |
| 615 static void forEach(Primitive node, ReferenceCallback callback) { | |
| 616 new InputVisitor(callback).visit(node); | |
| 617 } | |
| 618 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
