| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012, 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 ssa; | |
| 6 | |
| 7 abstract class OptimizationPhase { | |
| 8 String get name; | |
| 9 void visitGraph(HGraph graph); | |
| 10 } | |
| 11 | |
| 12 class SsaOptimizerTask extends CompilerTask { | |
| 13 final JavaScriptBackend backend; | |
| 14 SsaOptimizerTask(JavaScriptBackend backend) | |
| 15 : this.backend = backend, | |
| 16 super(backend.compiler); | |
| 17 String get name => 'SSA optimizer'; | |
| 18 Compiler get compiler => backend.compiler; | |
| 19 Map<HInstruction, Range> ranges = <HInstruction, Range>{}; | |
| 20 | |
| 21 void runPhases(HGraph graph, List<OptimizationPhase> phases) { | |
| 22 for (OptimizationPhase phase in phases) { | |
| 23 runPhase(graph, phase); | |
| 24 } | |
| 25 } | |
| 26 | |
| 27 void runPhase(HGraph graph, OptimizationPhase phase) { | |
| 28 phase.visitGraph(graph); | |
| 29 compiler.tracer.traceGraph(phase.name, graph); | |
| 30 assert(graph.isValid()); | |
| 31 } | |
| 32 | |
| 33 void optimize(CodegenWorkItem work, HGraph graph) { | |
| 34 ConstantSystem constantSystem = compiler.backend.constantSystem; | |
| 35 JavaScriptItemCompilationContext context = work.compilationContext; | |
| 36 measure(() { | |
| 37 SsaDeadCodeEliminator dce; | |
| 38 List<OptimizationPhase> phases = <OptimizationPhase>[ | |
| 39 // Run trivial instruction simplification first to optimize | |
| 40 // some patterns useful for type conversion. | |
| 41 new SsaInstructionSimplifier(constantSystem, backend, work), | |
| 42 new SsaTypeConversionInserter(compiler), | |
| 43 new SsaRedundantPhiEliminator(), | |
| 44 new SsaDeadPhiEliminator(), | |
| 45 new SsaTypePropagator(compiler), | |
| 46 // After type propagation, more instructions can be | |
| 47 // simplified. | |
| 48 new SsaInstructionSimplifier(constantSystem, backend, work), | |
| 49 new SsaCheckInserter(backend, work, context.boundsChecked), | |
| 50 new SsaInstructionSimplifier(constantSystem, backend, work), | |
| 51 new SsaCheckInserter(backend, work, context.boundsChecked), | |
| 52 new SsaTypePropagator(compiler), | |
| 53 // Run a dead code eliminator before LICM because dead | |
| 54 // interceptors are often in the way of LICM'able instructions. | |
| 55 new SsaDeadCodeEliminator(compiler), | |
| 56 new SsaGlobalValueNumberer(compiler), | |
| 57 // After GVN, some instructions might need their type to be | |
| 58 // updated because they now have different inputs. | |
| 59 new SsaTypePropagator(compiler), | |
| 60 new SsaCodeMotion(), | |
| 61 new SsaLoadElimination(compiler), | |
| 62 new SsaDeadPhiEliminator(), | |
| 63 new SsaTypePropagator(compiler), | |
| 64 new SsaValueRangeAnalyzer(compiler, constantSystem, work), | |
| 65 // Previous optimizations may have generated new | |
| 66 // opportunities for instruction simplification. | |
| 67 new SsaInstructionSimplifier(constantSystem, backend, work), | |
| 68 new SsaCheckInserter(backend, work, context.boundsChecked), | |
| 69 new SsaSimplifyInterceptors(compiler, constantSystem, work), | |
| 70 dce = new SsaDeadCodeEliminator(compiler), | |
| 71 new SsaTypePropagator(compiler)]; | |
| 72 runPhases(graph, phases); | |
| 73 if (dce.eliminatedSideEffects) { | |
| 74 phases = <OptimizationPhase>[ | |
| 75 new SsaGlobalValueNumberer(compiler), | |
| 76 new SsaCodeMotion(), | |
| 77 new SsaValueRangeAnalyzer(compiler, constantSystem, work), | |
| 78 new SsaInstructionSimplifier(constantSystem, backend, work), | |
| 79 new SsaCheckInserter(backend, work, context.boundsChecked), | |
| 80 new SsaSimplifyInterceptors(compiler, constantSystem, work), | |
| 81 new SsaDeadCodeEliminator(compiler)]; | |
| 82 } else { | |
| 83 phases = <OptimizationPhase>[ | |
| 84 // Run the simplifier to remove unneeded type checks inserted | |
| 85 // by type propagation. | |
| 86 new SsaInstructionSimplifier(constantSystem, backend, work)]; | |
| 87 } | |
| 88 runPhases(graph, phases); | |
| 89 }); | |
| 90 } | |
| 91 } | |
| 92 | |
| 93 bool isFixedLength(mask, Compiler compiler) { | |
| 94 ClassWorld classWorld = compiler.world; | |
| 95 JavaScriptBackend backend = compiler.backend; | |
| 96 if (mask.isContainer && mask.length != null) { | |
| 97 // A container on which we have inferred the length. | |
| 98 return true; | |
| 99 } else if (mask.containsOnly(backend.jsFixedArrayClass) | |
| 100 || mask.containsOnlyString(classWorld) | |
| 101 || backend.isTypedArray(mask)) { | |
| 102 return true; | |
| 103 } | |
| 104 return false; | |
| 105 } | |
| 106 | |
| 107 /** | |
| 108 * If both inputs to known operations are available execute the operation at | |
| 109 * compile-time. | |
| 110 */ | |
| 111 class SsaInstructionSimplifier extends HBaseVisitor | |
| 112 implements OptimizationPhase { | |
| 113 | |
| 114 // We don't produce constant-folded strings longer than this unless they have | |
| 115 // a single use. This protects against exponentially large constant folded | |
| 116 // strings. | |
| 117 static const MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH = 512; | |
| 118 | |
| 119 final String name = "SsaInstructionSimplifier"; | |
| 120 final JavaScriptBackend backend; | |
| 121 final CodegenWorkItem work; | |
| 122 final ConstantSystem constantSystem; | |
| 123 HGraph graph; | |
| 124 Compiler get compiler => backend.compiler; | |
| 125 | |
| 126 SsaInstructionSimplifier(this.constantSystem, this.backend, this.work); | |
| 127 | |
| 128 void visitGraph(HGraph visitee) { | |
| 129 graph = visitee; | |
| 130 visitDominatorTree(visitee); | |
| 131 } | |
| 132 | |
| 133 visitBasicBlock(HBasicBlock block) { | |
| 134 HInstruction instruction = block.first; | |
| 135 while (instruction != null) { | |
| 136 HInstruction next = instruction.next; | |
| 137 HInstruction replacement = instruction.accept(this); | |
| 138 if (replacement != instruction) { | |
| 139 block.rewrite(instruction, replacement); | |
| 140 | |
| 141 // The intersection of double and int return conflicting, and | |
| 142 // because of our number implementation for JavaScript, it | |
| 143 // might be that an operation thought to return double, can be | |
| 144 // simplified to an int. For example: | |
| 145 // `2.5 * 10`. | |
| 146 if (!(replacement.isNumberOrNull(compiler) | |
| 147 && instruction.isNumberOrNull(compiler))) { | |
| 148 // If we can replace [instruction] with [replacement], then | |
| 149 // [replacement]'s type can be narrowed. | |
| 150 TypeMask newType = replacement.instructionType.intersection( | |
| 151 instruction.instructionType, compiler.world); | |
| 152 replacement.instructionType = newType; | |
| 153 } | |
| 154 | |
| 155 // If the replacement instruction does not know its | |
| 156 // source element, use the source element of the | |
| 157 // instruction. | |
| 158 if (replacement.sourceElement == null) { | |
| 159 replacement.sourceElement = instruction.sourceElement; | |
| 160 } | |
| 161 if (replacement.sourcePosition == null) { | |
| 162 replacement.sourcePosition = instruction.sourcePosition; | |
| 163 } | |
| 164 if (!replacement.isInBasicBlock()) { | |
| 165 // The constant folding can return an instruction that is already | |
| 166 // part of the graph (like an input), so we only add the replacement | |
| 167 // if necessary. | |
| 168 block.addAfter(instruction, replacement); | |
| 169 // Visit the replacement as the next instruction in case it | |
| 170 // can also be constant folded away. | |
| 171 next = replacement; | |
| 172 } | |
| 173 block.remove(instruction); | |
| 174 } | |
| 175 instruction = next; | |
| 176 } | |
| 177 } | |
| 178 | |
| 179 HInstruction visitInstruction(HInstruction node) { | |
| 180 return node; | |
| 181 } | |
| 182 | |
| 183 HInstruction visitBoolify(HBoolify node) { | |
| 184 List<HInstruction> inputs = node.inputs; | |
| 185 assert(inputs.length == 1); | |
| 186 HInstruction input = inputs[0]; | |
| 187 if (input.isBoolean(compiler)) return input; | |
| 188 // All values that cannot be 'true' are boolified to false. | |
| 189 TypeMask mask = input.instructionType; | |
| 190 if (!mask.contains(backend.jsBoolClass, compiler.world)) { | |
| 191 return graph.addConstantBool(false, compiler); | |
| 192 } | |
| 193 return node; | |
| 194 } | |
| 195 | |
| 196 HInstruction visitNot(HNot node) { | |
| 197 List<HInstruction> inputs = node.inputs; | |
| 198 assert(inputs.length == 1); | |
| 199 HInstruction input = inputs[0]; | |
| 200 if (input is HConstant) { | |
| 201 HConstant constant = input; | |
| 202 bool isTrue = constant.constant.isTrue; | |
| 203 return graph.addConstantBool(!isTrue, compiler); | |
| 204 } else if (input is HNot) { | |
| 205 return input.inputs[0]; | |
| 206 } | |
| 207 return node; | |
| 208 } | |
| 209 | |
| 210 HInstruction visitInvokeUnary(HInvokeUnary node) { | |
| 211 HInstruction folded = | |
| 212 foldUnary(node.operation(constantSystem), node.operand); | |
| 213 return folded != null ? folded : node; | |
| 214 } | |
| 215 | |
| 216 HInstruction foldUnary(UnaryOperation operation, HInstruction operand) { | |
| 217 if (operand is HConstant) { | |
| 218 HConstant receiver = operand; | |
| 219 ConstantValue folded = operation.fold(receiver.constant); | |
| 220 if (folded != null) return graph.addConstant(folded, compiler); | |
| 221 } | |
| 222 return null; | |
| 223 } | |
| 224 | |
| 225 HInstruction tryOptimizeLengthInterceptedGetter(HInvokeDynamic node) { | |
| 226 HInstruction actualReceiver = node.inputs[1]; | |
| 227 if (actualReceiver.isIndexablePrimitive(compiler)) { | |
| 228 if (actualReceiver.isConstantString()) { | |
| 229 HConstant constantInput = actualReceiver; | |
| 230 StringConstantValue constant = constantInput.constant; | |
| 231 return graph.addConstantInt(constant.length, compiler); | |
| 232 } else if (actualReceiver.isConstantList()) { | |
| 233 HConstant constantInput = actualReceiver; | |
| 234 ListConstantValue constant = constantInput.constant; | |
| 235 return graph.addConstantInt(constant.length, compiler); | |
| 236 } | |
| 237 Element element = backend.jsIndexableLength; | |
| 238 bool isFixed = isFixedLength(actualReceiver.instructionType, compiler); | |
| 239 HFieldGet result = new HFieldGet( | |
| 240 element, actualReceiver, backend.positiveIntType, | |
| 241 isAssignable: !isFixed); | |
| 242 return result; | |
| 243 } else if (actualReceiver.isConstantMap()) { | |
| 244 HConstant constantInput = actualReceiver; | |
| 245 MapConstantValue constant = constantInput.constant; | |
| 246 return graph.addConstantInt(constant.length, compiler); | |
| 247 } | |
| 248 return null; | |
| 249 } | |
| 250 | |
| 251 HInstruction handleInterceptedCall(HInvokeDynamic node) { | |
| 252 // Try constant folding the instruction. | |
| 253 Operation operation = node.specializer.operation(constantSystem); | |
| 254 if (operation != null) { | |
| 255 HInstruction instruction = node.inputs.length == 2 | |
| 256 ? foldUnary(operation, node.inputs[1]) | |
| 257 : foldBinary(operation, node.inputs[1], node.inputs[2]); | |
| 258 if (instruction != null) return instruction; | |
| 259 } | |
| 260 | |
| 261 // Try converting the instruction to a builtin instruction. | |
| 262 HInstruction instruction = | |
| 263 node.specializer.tryConvertToBuiltin(node, compiler); | |
| 264 if (instruction != null) return instruction; | |
| 265 | |
| 266 Selector selector = node.selector; | |
| 267 HInstruction input = node.inputs[1]; | |
| 268 | |
| 269 World world = compiler.world; | |
| 270 if (selector.isCall || selector.isOperator) { | |
| 271 Element target; | |
| 272 if (input.isExtendableArray(compiler)) { | |
| 273 if (selector.applies(backend.jsArrayRemoveLast, world)) { | |
| 274 target = backend.jsArrayRemoveLast; | |
| 275 } else if (selector.applies(backend.jsArrayAdd, world)) { | |
| 276 // The codegen special cases array calls, but does not | |
| 277 // inline argument type checks. | |
| 278 if (!compiler.enableTypeAssertions) { | |
| 279 target = backend.jsArrayAdd; | |
| 280 } | |
| 281 } | |
| 282 } else if (input.isStringOrNull(compiler)) { | |
| 283 if (selector.applies(backend.jsStringSplit, world)) { | |
| 284 HInstruction argument = node.inputs[2]; | |
| 285 if (argument.isString(compiler)) { | |
| 286 target = backend.jsStringSplit; | |
| 287 } | |
| 288 } else if (selector.applies(backend.jsStringOperatorAdd, world)) { | |
| 289 // `operator+` is turned into a JavaScript '+' so we need to | |
| 290 // make sure the receiver and the argument are not null. | |
| 291 // TODO(sra): Do this via [node.specializer]. | |
| 292 HInstruction argument = node.inputs[2]; | |
| 293 if (argument.isString(compiler) | |
| 294 && !input.canBeNull()) { | |
| 295 return new HStringConcat(input, argument, null, | |
| 296 node.instructionType); | |
| 297 } | |
| 298 } else if (selector.applies(backend.jsStringToString, world) | |
| 299 && !input.canBeNull()) { | |
| 300 return input; | |
| 301 } | |
| 302 } | |
| 303 if (target != null) { | |
| 304 // TODO(ngeoffray): There is a strong dependency between codegen | |
| 305 // and this optimization that the dynamic invoke does not need an | |
| 306 // interceptor. We currently need to keep a | |
| 307 // HInvokeDynamicMethod and not create a HForeign because | |
| 308 // HForeign is too opaque for the SsaCheckInserter (that adds a | |
| 309 // bounds check on removeLast). Once we start inlining, the | |
| 310 // bounds check will become explicit, so we won't need this | |
| 311 // optimization. | |
| 312 HInvokeDynamicMethod result = new HInvokeDynamicMethod( | |
| 313 node.selector, node.inputs.sublist(1), node.instructionType); | |
| 314 result.element = target; | |
| 315 return result; | |
| 316 } | |
| 317 } else if (selector.isGetter) { | |
| 318 if (selector.asUntyped.applies(backend.jsIndexableLength, world)) { | |
| 319 HInstruction optimized = tryOptimizeLengthInterceptedGetter(node); | |
| 320 if (optimized != null) return optimized; | |
| 321 } | |
| 322 } | |
| 323 | |
| 324 return node; | |
| 325 } | |
| 326 | |
| 327 HInstruction visitInvokeDynamicMethod(HInvokeDynamicMethod node) { | |
| 328 if (node.isInterceptedCall) { | |
| 329 HInstruction folded = handleInterceptedCall(node); | |
| 330 if (folded != node) return folded; | |
| 331 } | |
| 332 | |
| 333 TypeMask receiverType = node.getDartReceiver(compiler).instructionType; | |
| 334 Selector selector = | |
| 335 new TypedSelector(receiverType, node.selector, compiler.world); | |
| 336 Element element = compiler.world.locateSingleElement(selector); | |
| 337 // TODO(ngeoffray): Also fold if it's a getter or variable. | |
| 338 if (element != null | |
| 339 && element.isFunction | |
| 340 // If we found out that the only target is a [:noSuchMethod:], | |
| 341 // we just ignore it. | |
| 342 && element.name == selector.name) { | |
| 343 FunctionElement method = element; | |
| 344 | |
| 345 if (method.isNative) { | |
| 346 HInstruction folded = tryInlineNativeMethod(node, method); | |
| 347 if (folded != null) return folded; | |
| 348 } else { | |
| 349 // TODO(ngeoffray): If the method has optional parameters, | |
| 350 // we should pass the default values. | |
| 351 FunctionSignature parameters = method.functionSignature; | |
| 352 if (parameters.optionalParameterCount == 0 | |
| 353 || parameters.parameterCount == node.selector.argumentCount) { | |
| 354 node.element = element; | |
| 355 } | |
| 356 } | |
| 357 } | |
| 358 return node; | |
| 359 } | |
| 360 | |
| 361 HInstruction tryInlineNativeMethod(HInvokeDynamicMethod node, | |
| 362 FunctionElement method) { | |
| 363 // Enable direct calls to a native method only if we don't run in checked | |
| 364 // mode, where the Dart version may have type annotations on parameters and | |
| 365 // return type that it should check. | |
| 366 // Also check that the parameters are not functions: it's the callee that | |
| 367 // will translate them to JS functions. | |
| 368 // | |
| 369 // TODO(ngeoffray): There are some cases where we could still inline in | |
| 370 // checked mode if we know the arguments have the right type. And we could | |
| 371 // do the closure conversion as well as the return type annotation check. | |
| 372 | |
| 373 if (!node.isInterceptedCall) return null; | |
| 374 | |
| 375 // TODO(sra): Check for legacy methods with bodies in the native strings. | |
| 376 // foo() native 'return something'; | |
| 377 // They should not be used. | |
| 378 | |
| 379 FunctionSignature signature = method.functionSignature; | |
| 380 if (signature.optionalParametersAreNamed) return null; | |
| 381 | |
| 382 // Return types on native methods don't need to be checked, since the | |
| 383 // declaration has to be truthful. | |
| 384 | |
| 385 // The call site might omit optional arguments. The inlined code must | |
| 386 // preserve the number of arguments, so check only the actual arguments. | |
| 387 | |
| 388 List<HInstruction> inputs = node.inputs.sublist(1); | |
| 389 int inputPosition = 1; // Skip receiver. | |
| 390 bool canInline = true; | |
| 391 signature.forEachParameter((ParameterElement element) { | |
| 392 if (inputPosition < inputs.length && canInline) { | |
| 393 HInstruction input = inputs[inputPosition++]; | |
| 394 DartType type = element.type.unalias(compiler); | |
| 395 if (type is FunctionType) { | |
| 396 canInline = false; | |
| 397 } | |
| 398 if (compiler.enableTypeAssertions) { | |
| 399 // TODO(sra): Check if [input] is guaranteed to pass the parameter | |
| 400 // type check. Consider using a strengthened type check to avoid | |
| 401 // passing `null` to primitive types since the native methods usually | |
| 402 // have non-nullable primitive parameter types. | |
| 403 canInline = false; | |
| 404 } | |
| 405 } | |
| 406 }); | |
| 407 | |
| 408 if (!canInline) return null; | |
| 409 | |
| 410 // Strengthen instruction type from annotations to help optimize | |
| 411 // dependent instructions. | |
| 412 native.NativeBehavior nativeBehavior = | |
| 413 native.NativeBehavior.ofMethod(method, compiler); | |
| 414 TypeMask returnType = | |
| 415 TypeMaskFactory.fromNativeBehavior(nativeBehavior, compiler); | |
| 416 HInvokeDynamicMethod result = | |
| 417 new HInvokeDynamicMethod(node.selector, inputs, returnType); | |
| 418 result.element = method; | |
| 419 return result; | |
| 420 } | |
| 421 | |
| 422 HInstruction visitBoundsCheck(HBoundsCheck node) { | |
| 423 HInstruction index = node.index; | |
| 424 if (index.isInteger(compiler)) return node; | |
| 425 if (index.isConstant()) { | |
| 426 HConstant constantInstruction = index; | |
| 427 assert(!constantInstruction.constant.isInt); | |
| 428 if (!constantSystem.isInt(constantInstruction.constant)) { | |
| 429 // -0.0 is a double but will pass the runtime integer check. | |
| 430 node.staticChecks = HBoundsCheck.ALWAYS_FALSE; | |
| 431 } | |
| 432 } | |
| 433 return node; | |
| 434 } | |
| 435 | |
| 436 HInstruction foldBinary(BinaryOperation operation, | |
| 437 HInstruction left, | |
| 438 HInstruction right) { | |
| 439 if (left is HConstant && right is HConstant) { | |
| 440 HConstant op1 = left; | |
| 441 HConstant op2 = right; | |
| 442 ConstantValue folded = operation.fold(op1.constant, op2.constant); | |
| 443 if (folded != null) return graph.addConstant(folded, compiler); | |
| 444 } | |
| 445 return null; | |
| 446 } | |
| 447 | |
| 448 HInstruction visitAdd(HAdd node) { | |
| 449 HInstruction left = node.left; | |
| 450 HInstruction right = node.right; | |
| 451 // We can only perform this rewriting on Integer, as it is not | |
| 452 // valid for -0.0. | |
| 453 if (left.isInteger(compiler) && right.isInteger(compiler)) { | |
| 454 if (left is HConstant && left.constant.isZero) return right; | |
| 455 if (right is HConstant && right.constant.isZero) return left; | |
| 456 } | |
| 457 return super.visitAdd(node); | |
| 458 } | |
| 459 | |
| 460 HInstruction visitMultiply(HMultiply node) { | |
| 461 HInstruction left = node.left; | |
| 462 HInstruction right = node.right; | |
| 463 if (left.isNumber(compiler) && right.isNumber(compiler)) { | |
| 464 if (left is HConstant && left.constant.isOne) return right; | |
| 465 if (right is HConstant && right.constant.isOne) return left; | |
| 466 } | |
| 467 return super.visitMultiply(node); | |
| 468 } | |
| 469 | |
| 470 HInstruction visitInvokeBinary(HInvokeBinary node) { | |
| 471 HInstruction left = node.left; | |
| 472 HInstruction right = node.right; | |
| 473 BinaryOperation operation = node.operation(constantSystem); | |
| 474 HConstant folded = foldBinary(operation, left, right); | |
| 475 if (folded != null) return folded; | |
| 476 return node; | |
| 477 } | |
| 478 | |
| 479 bool allUsersAreBoolifies(HInstruction instruction) { | |
| 480 List<HInstruction> users = instruction.usedBy; | |
| 481 int length = users.length; | |
| 482 for (int i = 0; i < length; i++) { | |
| 483 if (users[i] is! HBoolify) return false; | |
| 484 } | |
| 485 return true; | |
| 486 } | |
| 487 | |
| 488 HInstruction visitRelational(HRelational node) { | |
| 489 if (allUsersAreBoolifies(node)) { | |
| 490 // TODO(ngeoffray): Call a boolified selector. | |
| 491 // This node stays the same, but the Boolify node will go away. | |
| 492 } | |
| 493 // Note that we still have to call [super] to make sure that we end up | |
| 494 // in the remaining optimizations. | |
| 495 return super.visitRelational(node); | |
| 496 } | |
| 497 | |
| 498 HInstruction handleIdentityCheck(HRelational node) { | |
| 499 HInstruction left = node.left; | |
| 500 HInstruction right = node.right; | |
| 501 TypeMask leftType = left.instructionType; | |
| 502 TypeMask rightType = right.instructionType; | |
| 503 | |
| 504 // Intersection of int and double return conflicting, so | |
| 505 // we don't optimize on numbers to preserve the runtime semantics. | |
| 506 if (!(left.isNumberOrNull(compiler) && right.isNumberOrNull(compiler))) { | |
| 507 TypeMask intersection = leftType.intersection(rightType, compiler.world); | |
| 508 if (intersection.isEmpty && !intersection.isNullable) { | |
| 509 return graph.addConstantBool(false, compiler); | |
| 510 } | |
| 511 } | |
| 512 | |
| 513 if (left.isNull() && right.isNull()) { | |
| 514 return graph.addConstantBool(true, compiler); | |
| 515 } | |
| 516 | |
| 517 if (left.isConstantBoolean() && right.isBoolean(compiler)) { | |
| 518 HConstant constant = left; | |
| 519 if (constant.constant.isTrue) { | |
| 520 return right; | |
| 521 } else { | |
| 522 return new HNot(right, backend.boolType); | |
| 523 } | |
| 524 } | |
| 525 | |
| 526 if (right.isConstantBoolean() && left.isBoolean(compiler)) { | |
| 527 HConstant constant = right; | |
| 528 if (constant.constant.isTrue) { | |
| 529 return left; | |
| 530 } else { | |
| 531 return new HNot(left, backend.boolType); | |
| 532 } | |
| 533 } | |
| 534 | |
| 535 return null; | |
| 536 } | |
| 537 | |
| 538 HInstruction visitIdentity(HIdentity node) { | |
| 539 HInstruction newInstruction = handleIdentityCheck(node); | |
| 540 return newInstruction == null ? super.visitIdentity(node) : newInstruction; | |
| 541 } | |
| 542 | |
| 543 void simplifyCondition(HBasicBlock block, | |
| 544 HInstruction condition, | |
| 545 bool value) { | |
| 546 condition.dominatedUsers(block.first).forEach((user) { | |
| 547 HInstruction newCondition = graph.addConstantBool(value, compiler); | |
| 548 user.changeUse(condition, newCondition); | |
| 549 }); | |
| 550 } | |
| 551 | |
| 552 HInstruction visitIf(HIf node) { | |
| 553 HInstruction condition = node.condition; | |
| 554 if (condition.isConstant()) return node; | |
| 555 bool isNegated = condition is HNot; | |
| 556 | |
| 557 if (isNegated) { | |
| 558 condition = condition.inputs[0]; | |
| 559 } else { | |
| 560 // It is possible for LICM to move a negated version of the | |
| 561 // condition out of the loop where it used. We still want to | |
| 562 // simplify the nested use of the condition in that case, so | |
| 563 // we look for all dominating negated conditions and replace | |
| 564 // nested uses of them with true or false. | |
| 565 Iterable<HInstruction> dominating = condition.usedBy.where((user) => | |
| 566 user is HNot && user.dominates(node)); | |
| 567 dominating.forEach((hoisted) { | |
| 568 simplifyCondition(node.thenBlock, hoisted, false); | |
| 569 simplifyCondition(node.elseBlock, hoisted, true); | |
| 570 }); | |
| 571 } | |
| 572 simplifyCondition(node.thenBlock, condition, !isNegated); | |
| 573 simplifyCondition(node.elseBlock, condition, isNegated); | |
| 574 return node; | |
| 575 } | |
| 576 | |
| 577 HInstruction visitIs(HIs node) { | |
| 578 DartType type = node.typeExpression; | |
| 579 Element element = type.element; | |
| 580 | |
| 581 if (!node.isRawCheck) { | |
| 582 return node; | |
| 583 } else if (type.isTypedef) { | |
| 584 return node; | |
| 585 } else if (element == compiler.functionClass) { | |
| 586 return node; | |
| 587 } | |
| 588 | |
| 589 if (element == compiler.objectClass || type.treatAsDynamic) { | |
| 590 return graph.addConstantBool(true, compiler); | |
| 591 } | |
| 592 | |
| 593 ClassWorld classWorld = compiler.world; | |
| 594 HInstruction expression = node.expression; | |
| 595 if (expression.isInteger(compiler)) { | |
| 596 if (identical(element, compiler.intClass) | |
| 597 || identical(element, compiler.numClass) | |
| 598 || Elements.isNumberOrStringSupertype(element, compiler)) { | |
| 599 return graph.addConstantBool(true, compiler); | |
| 600 } else if (identical(element, compiler.doubleClass)) { | |
| 601 // We let the JS semantics decide for that check. Currently | |
| 602 // the code we emit will always return true. | |
| 603 return node; | |
| 604 } else { | |
| 605 return graph.addConstantBool(false, compiler); | |
| 606 } | |
| 607 } else if (expression.isDouble(compiler)) { | |
| 608 if (identical(element, compiler.doubleClass) | |
| 609 || identical(element, compiler.numClass) | |
| 610 || Elements.isNumberOrStringSupertype(element, compiler)) { | |
| 611 return graph.addConstantBool(true, compiler); | |
| 612 } else if (identical(element, compiler.intClass)) { | |
| 613 // We let the JS semantics decide for that check. Currently | |
| 614 // the code we emit will return true for a double that can be | |
| 615 // represented as a 31-bit integer and for -0.0. | |
| 616 return node; | |
| 617 } else { | |
| 618 return graph.addConstantBool(false, compiler); | |
| 619 } | |
| 620 } else if (expression.isNumber(compiler)) { | |
| 621 if (identical(element, compiler.numClass)) { | |
| 622 return graph.addConstantBool(true, compiler); | |
| 623 } else { | |
| 624 // We cannot just return false, because the expression may be of | |
| 625 // type int or double. | |
| 626 } | |
| 627 } else if (expression.canBePrimitiveNumber(compiler) | |
| 628 && identical(element, compiler.intClass)) { | |
| 629 // We let the JS semantics decide for that check. | |
| 630 return node; | |
| 631 // We need the [:hasTypeArguments:] check because we don't have | |
| 632 // the notion of generics in the backend. For example, [:this:] in | |
| 633 // a class [:A<T>:], is currently always considered to have the | |
| 634 // raw type. | |
| 635 } else if (!RuntimeTypes.hasTypeArguments(type)) { | |
| 636 TypeMask expressionMask = expression.instructionType; | |
| 637 assert(TypeMask.assertIsNormalized(expressionMask, classWorld)); | |
| 638 TypeMask typeMask = (element == compiler.nullClass) | |
| 639 ? new TypeMask.subtype(element, classWorld) | |
| 640 : new TypeMask.nonNullSubtype(element, classWorld); | |
| 641 if (expressionMask.union(typeMask, classWorld) == typeMask) { | |
| 642 return graph.addConstantBool(true, compiler); | |
| 643 } else if (expressionMask.intersection(typeMask, | |
| 644 compiler.world).isEmpty) { | |
| 645 return graph.addConstantBool(false, compiler); | |
| 646 } | |
| 647 } | |
| 648 return node; | |
| 649 } | |
| 650 | |
| 651 HInstruction visitTypeConversion(HTypeConversion node) { | |
| 652 HInstruction value = node.inputs[0]; | |
| 653 DartType type = node.typeExpression; | |
| 654 if (type != null) { | |
| 655 if (type.isMalformed) { | |
| 656 // Malformed types are treated as dynamic statically, but should | |
| 657 // throw a type error at runtime. | |
| 658 return node; | |
| 659 } | |
| 660 if (!type.treatAsRaw || type.isTypeVariable) { | |
| 661 return node; | |
| 662 } | |
| 663 if (type.isFunctionType) { | |
| 664 // TODO(johnniwinther): Optimize function type conversions. | |
| 665 return node; | |
| 666 } | |
| 667 } | |
| 668 return removeIfCheckAlwaysSucceeds(node, node.checkedType); | |
| 669 } | |
| 670 | |
| 671 HInstruction visitTypeKnown(HTypeKnown node) { | |
| 672 return removeIfCheckAlwaysSucceeds(node, node.knownType); | |
| 673 } | |
| 674 | |
| 675 HInstruction removeIfCheckAlwaysSucceeds(HCheck node, TypeMask checkedType) { | |
| 676 ClassWorld classWorld = compiler.world; | |
| 677 if (checkedType.containsAll(classWorld)) return node; | |
| 678 HInstruction input = node.checkedInput; | |
| 679 TypeMask inputType = input.instructionType; | |
| 680 return inputType.isInMask(checkedType, classWorld) ? input : node; | |
| 681 } | |
| 682 | |
| 683 VariableElement findConcreteFieldForDynamicAccess(HInstruction receiver, | |
| 684 Selector selector) { | |
| 685 TypeMask receiverType = receiver.instructionType; | |
| 686 return compiler.world.locateSingleField( | |
| 687 new TypedSelector(receiverType, selector, compiler.world)); | |
| 688 } | |
| 689 | |
| 690 HInstruction visitFieldGet(HFieldGet node) { | |
| 691 if (node.isNullCheck) return node; | |
| 692 var receiver = node.receiver; | |
| 693 if (node.element == backend.jsIndexableLength) { | |
| 694 JavaScriptItemCompilationContext context = work.compilationContext; | |
| 695 if (context.allocatedFixedLists.contains(receiver)) { | |
| 696 // TODO(ngeoffray): checking if the second input is an integer | |
| 697 // should not be necessary but it currently makes it easier for | |
| 698 // other optimizations to reason about a fixed length constructor | |
| 699 // that we know takes an int. | |
| 700 if (receiver.inputs[0].isInteger(compiler)) { | |
| 701 return receiver.inputs[0]; | |
| 702 } | |
| 703 } else if (receiver.isConstantList() || receiver.isConstantString()) { | |
| 704 return graph.addConstantInt(receiver.constant.length, compiler); | |
| 705 } else { | |
| 706 var type = receiver.instructionType; | |
| 707 if (type.isContainer && type.length != null) { | |
| 708 HInstruction constant = graph.addConstantInt(type.length, compiler); | |
| 709 if (type.isNullable) { | |
| 710 // If the container can be null, we update all uses of the | |
| 711 // length access to use the constant instead, but keep the | |
| 712 // length access in the graph, to ensure we still have a | |
| 713 // null check. | |
| 714 node.block.rewrite(node, constant); | |
| 715 return node; | |
| 716 } else { | |
| 717 return constant; | |
| 718 } | |
| 719 } | |
| 720 } | |
| 721 } | |
| 722 | |
| 723 // HFieldGet of a constructed constant can be replaced with the constant's | |
| 724 // field. | |
| 725 if (receiver is HConstant) { | |
| 726 ConstantValue constant = receiver.constant; | |
| 727 if (constant.isConstructedObject) { | |
| 728 ConstructedConstantValue constructedConstant = constant; | |
| 729 Map<Element, ConstantValue> fields = constructedConstant.fieldElements; | |
| 730 ConstantValue value = fields[node.element]; | |
| 731 if (value != null) { | |
| 732 return graph.addConstant(value, compiler); | |
| 733 } | |
| 734 } | |
| 735 } | |
| 736 | |
| 737 return node; | |
| 738 } | |
| 739 | |
| 740 HInstruction visitIndex(HIndex node) { | |
| 741 if (node.receiver.isConstantList() && node.index.isConstantInteger()) { | |
| 742 var instruction = node.receiver; | |
| 743 List<ConstantValue> entries = instruction.constant.entries; | |
| 744 instruction = node.index; | |
| 745 int index = instruction.constant.primitiveValue; | |
| 746 if (index >= 0 && index < entries.length) { | |
| 747 return graph.addConstant(entries[index], compiler); | |
| 748 } | |
| 749 } | |
| 750 return node; | |
| 751 } | |
| 752 | |
| 753 HInstruction visitInvokeDynamicGetter(HInvokeDynamicGetter node) { | |
| 754 if (node.isInterceptedCall) { | |
| 755 HInstruction folded = handleInterceptedCall(node); | |
| 756 if (folded != node) return folded; | |
| 757 } | |
| 758 HInstruction receiver = node.getDartReceiver(compiler); | |
| 759 Element field = findConcreteFieldForDynamicAccess(receiver, node.selector); | |
| 760 if (field == null) return node; | |
| 761 return directFieldGet(receiver, field); | |
| 762 } | |
| 763 | |
| 764 HInstruction directFieldGet(HInstruction receiver, Element field) { | |
| 765 bool isAssignable = !compiler.world.fieldNeverChanges(field); | |
| 766 | |
| 767 TypeMask type; | |
| 768 if (field.enclosingClass.isNative) { | |
| 769 type = TypeMaskFactory.fromNativeBehavior( | |
| 770 native.NativeBehavior.ofFieldLoad(field, compiler), | |
| 771 compiler); | |
| 772 } else { | |
| 773 type = TypeMaskFactory.inferredTypeForElement(field, compiler); | |
| 774 } | |
| 775 | |
| 776 return new HFieldGet( | |
| 777 field, receiver, type, isAssignable: isAssignable); | |
| 778 } | |
| 779 | |
| 780 HInstruction visitInvokeDynamicSetter(HInvokeDynamicSetter node) { | |
| 781 if (node.isInterceptedCall) { | |
| 782 HInstruction folded = handleInterceptedCall(node); | |
| 783 if (folded != node) return folded; | |
| 784 } | |
| 785 | |
| 786 HInstruction receiver = node.getDartReceiver(compiler); | |
| 787 VariableElement field = | |
| 788 findConcreteFieldForDynamicAccess(receiver, node.selector); | |
| 789 if (field == null || !field.isAssignable) return node; | |
| 790 // Use [:node.inputs.last:] in case the call follows the | |
| 791 // interceptor calling convention, but is not a call on an | |
| 792 // interceptor. | |
| 793 HInstruction value = node.inputs.last; | |
| 794 if (compiler.enableTypeAssertions) { | |
| 795 DartType type = field.type; | |
| 796 if (!type.treatAsRaw || type.isTypeVariable) { | |
| 797 // We cannot generate the correct type representation here, so don't | |
| 798 // inline this access. | |
| 799 return node; | |
| 800 } | |
| 801 HInstruction other = value.convertType( | |
| 802 compiler, | |
| 803 type, | |
| 804 HTypeConversion.CHECKED_MODE_CHECK); | |
| 805 if (other != value) { | |
| 806 node.block.addBefore(node, other); | |
| 807 value = other; | |
| 808 } | |
| 809 } | |
| 810 return new HFieldSet(field, receiver, value); | |
| 811 } | |
| 812 | |
| 813 HInstruction visitStringConcat(HStringConcat node) { | |
| 814 // Simplify string concat: | |
| 815 // | |
| 816 // "" + R -> R | |
| 817 // L + "" -> L | |
| 818 // "L" + "R" -> "LR" | |
| 819 // (prefix + "L") + "R" -> prefix + "LR" | |
| 820 // | |
| 821 StringConstantValue getString(HInstruction instruction) { | |
| 822 if (!instruction.isConstantString()) return null; | |
| 823 HConstant constant = instruction; | |
| 824 return constant.constant; | |
| 825 } | |
| 826 | |
| 827 StringConstantValue leftString = getString(node.left); | |
| 828 if (leftString != null && leftString.primitiveValue.length == 0) { | |
| 829 return node.right; | |
| 830 } | |
| 831 | |
| 832 StringConstantValue rightString = getString(node.right); | |
| 833 if (rightString == null) return node; | |
| 834 if (rightString.primitiveValue.length == 0) return node.left; | |
| 835 | |
| 836 HInstruction prefix = null; | |
| 837 if (leftString == null) { | |
| 838 if (node.left is! HStringConcat) return node; | |
| 839 HStringConcat leftConcat = node.left; | |
| 840 // Don't undo CSE. | |
| 841 if (leftConcat.usedBy.length != 1) return node; | |
| 842 prefix = leftConcat.left; | |
| 843 leftString = getString(leftConcat.right); | |
| 844 if (leftString == null) return node; | |
| 845 } | |
| 846 | |
| 847 if (leftString.primitiveValue.length + rightString.primitiveValue.length > | |
| 848 MAX_SHARED_CONSTANT_FOLDED_STRING_LENGTH) { | |
| 849 if (node.usedBy.length > 1) return node; | |
| 850 } | |
| 851 | |
| 852 HInstruction folded = graph.addConstant( | |
| 853 constantSystem.createString(new ast.DartString.concat( | |
| 854 leftString.primitiveValue, rightString.primitiveValue)), | |
| 855 compiler); | |
| 856 if (prefix == null) return folded; | |
| 857 return new HStringConcat(prefix, folded, node.node, backend.stringType); | |
| 858 } | |
| 859 | |
| 860 HInstruction visitStringify(HStringify node) { | |
| 861 HInstruction input = node.inputs[0]; | |
| 862 if (input.isString(compiler)) return input; | |
| 863 if (input.isConstant()) { | |
| 864 HConstant constant = input; | |
| 865 if (!constant.constant.isPrimitive) return node; | |
| 866 if (constant.constant.isInt) { | |
| 867 // Only constant-fold int.toString() when Dart and JS results the same. | |
| 868 // TODO(18103): We should be able to remove this work-around when issue | |
| 869 // 18103 is resolved by providing the correct string. | |
| 870 IntConstantValue intConstant = constant.constant; | |
| 871 // Very conservative range. | |
| 872 if (!intConstant.isUInt32()) return node; | |
| 873 } | |
| 874 PrimitiveConstantValue primitive = constant.constant; | |
| 875 return graph.addConstant(constantSystem.createString( | |
| 876 primitive.toDartString()), compiler); | |
| 877 } | |
| 878 return node; | |
| 879 } | |
| 880 | |
| 881 HInstruction visitOneShotInterceptor(HOneShotInterceptor node) { | |
| 882 return handleInterceptedCall(node); | |
| 883 } | |
| 884 } | |
| 885 | |
| 886 class SsaCheckInserter extends HBaseVisitor implements OptimizationPhase { | |
| 887 final Set<HInstruction> boundsChecked; | |
| 888 final CodegenWorkItem work; | |
| 889 final JavaScriptBackend backend; | |
| 890 final String name = "SsaCheckInserter"; | |
| 891 HGraph graph; | |
| 892 | |
| 893 SsaCheckInserter(this.backend, | |
| 894 this.work, | |
| 895 this.boundsChecked); | |
| 896 | |
| 897 void visitGraph(HGraph graph) { | |
| 898 this.graph = graph; | |
| 899 visitDominatorTree(graph); | |
| 900 } | |
| 901 | |
| 902 void visitBasicBlock(HBasicBlock block) { | |
| 903 HInstruction instruction = block.first; | |
| 904 while (instruction != null) { | |
| 905 HInstruction next = instruction.next; | |
| 906 instruction = instruction.accept(this); | |
| 907 instruction = next; | |
| 908 } | |
| 909 } | |
| 910 | |
| 911 HBoundsCheck insertBoundsCheck(HInstruction indexNode, | |
| 912 HInstruction array, | |
| 913 HInstruction indexArgument) { | |
| 914 Compiler compiler = backend.compiler; | |
| 915 HFieldGet length = new HFieldGet( | |
| 916 backend.jsIndexableLength, array, backend.positiveIntType, | |
| 917 isAssignable: !isFixedLength(array.instructionType, compiler)); | |
| 918 indexNode.block.addBefore(indexNode, length); | |
| 919 | |
| 920 TypeMask type = indexArgument.isPositiveInteger(compiler) | |
| 921 ? indexArgument.instructionType | |
| 922 : backend.positiveIntType; | |
| 923 HBoundsCheck check = new HBoundsCheck( | |
| 924 indexArgument, length, array, type); | |
| 925 indexNode.block.addBefore(indexNode, check); | |
| 926 // If the index input to the bounds check was not known to be an integer | |
| 927 // then we replace its uses with the bounds check, which is known to be an | |
| 928 // integer. However, if the input was already an integer we don't do this | |
| 929 // because putting in a check instruction might obscure the real nature of | |
| 930 // the index eg. if it is a constant. The range information from the | |
| 931 // BoundsCheck instruction is attached to the input directly by | |
| 932 // visitBoundsCheck in the SsaValueRangeAnalyzer. | |
| 933 if (!indexArgument.isInteger(compiler)) { | |
| 934 indexArgument.replaceAllUsersDominatedBy(indexNode, check); | |
| 935 } | |
| 936 boundsChecked.add(indexNode); | |
| 937 return check; | |
| 938 } | |
| 939 | |
| 940 void visitIndex(HIndex node) { | |
| 941 if (boundsChecked.contains(node)) return; | |
| 942 HInstruction index = node.index; | |
| 943 index = insertBoundsCheck(node, node.receiver, index); | |
| 944 } | |
| 945 | |
| 946 void visitIndexAssign(HIndexAssign node) { | |
| 947 if (boundsChecked.contains(node)) return; | |
| 948 HInstruction index = node.index; | |
| 949 index = insertBoundsCheck(node, node.receiver, index); | |
| 950 } | |
| 951 | |
| 952 void visitInvokeDynamicMethod(HInvokeDynamicMethod node) { | |
| 953 Element element = node.element; | |
| 954 if (node.isInterceptedCall) return; | |
| 955 if (element != backend.jsArrayRemoveLast) return; | |
| 956 if (boundsChecked.contains(node)) return; | |
| 957 insertBoundsCheck( | |
| 958 node, node.receiver, graph.addConstantInt(0, backend.compiler)); | |
| 959 } | |
| 960 } | |
| 961 | |
| 962 class SsaDeadCodeEliminator extends HGraphVisitor implements OptimizationPhase { | |
| 963 final String name = "SsaDeadCodeEliminator"; | |
| 964 | |
| 965 final Compiler compiler; | |
| 966 SsaLiveBlockAnalyzer analyzer; | |
| 967 bool eliminatedSideEffects = false; | |
| 968 SsaDeadCodeEliminator(this.compiler); | |
| 969 | |
| 970 HInstruction zapInstructionCache; | |
| 971 HInstruction get zapInstruction { | |
| 972 if (zapInstructionCache == null) { | |
| 973 // A constant with no type does not pollute types at phi nodes. | |
| 974 ConstantValue constant = | |
| 975 new DummyConstantValue(const TypeMask.nonNullEmpty()); | |
| 976 zapInstructionCache = analyzer.graph.addConstant(constant, compiler); | |
| 977 } | |
| 978 return zapInstructionCache; | |
| 979 } | |
| 980 | |
| 981 /// Returns whether the next throwing instruction that may have side | |
| 982 /// effects after [instruction], throws [NoSuchMethodError] on the | |
| 983 /// same receiver of [instruction]. | |
| 984 bool hasFollowingThrowingNSM(HInstruction instruction) { | |
| 985 HInstruction receiver = instruction.getDartReceiver(compiler); | |
| 986 HInstruction current = instruction.next; | |
| 987 do { | |
| 988 if ((current.getDartReceiver(compiler) == receiver) | |
| 989 && current.canThrow()) { | |
| 990 return true; | |
| 991 } | |
| 992 if (current.canThrow() || current.sideEffects.hasSideEffects()) { | |
| 993 return false; | |
| 994 } | |
| 995 if (current.next == null && current is HGoto) { | |
| 996 // We do not merge blocks in our SSA graph, so if this block | |
| 997 // just jumps to a single predecessor, visit this predecessor. | |
| 998 assert(current.block.successors.length == 1); | |
| 999 current = current.block.successors[0].first; | |
| 1000 } else { | |
| 1001 current = current.next; | |
| 1002 } | |
| 1003 } while (current != null); | |
| 1004 return false; | |
| 1005 } | |
| 1006 | |
| 1007 bool isDeadCode(HInstruction instruction) { | |
| 1008 if (!instruction.usedBy.isEmpty) return false; | |
| 1009 if (instruction.sideEffects.hasSideEffects()) return false; | |
| 1010 if (instruction.canThrow() | |
| 1011 && instruction.onlyThrowsNSM() | |
| 1012 && hasFollowingThrowingNSM(instruction)) { | |
| 1013 return true; | |
| 1014 } | |
| 1015 return !instruction.canThrow() | |
| 1016 && instruction is !HParameterValue | |
| 1017 && instruction is !HLocalSet; | |
| 1018 } | |
| 1019 | |
| 1020 void visitGraph(HGraph graph) { | |
| 1021 analyzer = new SsaLiveBlockAnalyzer(graph, compiler); | |
| 1022 analyzer.analyze(); | |
| 1023 visitPostDominatorTree(graph); | |
| 1024 cleanPhis(graph); | |
| 1025 } | |
| 1026 | |
| 1027 void visitBasicBlock(HBasicBlock block) { | |
| 1028 bool isDeadBlock = analyzer.isDeadBlock(block); | |
| 1029 block.isLive = !isDeadBlock; | |
| 1030 // Start from the last non-control flow instruction in the block. | |
| 1031 HInstruction instruction = block.last.previous; | |
| 1032 while (instruction != null) { | |
| 1033 var previous = instruction.previous; | |
| 1034 if (isDeadBlock) { | |
| 1035 eliminatedSideEffects = eliminatedSideEffects || | |
| 1036 instruction.sideEffects.hasSideEffects(); | |
| 1037 removeUsers(instruction); | |
| 1038 block.remove(instruction); | |
| 1039 } else if (isDeadCode(instruction)) { | |
| 1040 block.remove(instruction); | |
| 1041 } | |
| 1042 instruction = previous; | |
| 1043 } | |
| 1044 } | |
| 1045 | |
| 1046 void cleanPhis(HGraph graph) { | |
| 1047 L: for (HBasicBlock block in graph.blocks) { | |
| 1048 List<HBasicBlock> predecessors = block.predecessors; | |
| 1049 // Zap all inputs to phis that correspond to dead blocks. | |
| 1050 block.forEachPhi((HPhi phi) { | |
| 1051 for (int i = 0; i < phi.inputs.length; ++i) { | |
| 1052 if (!predecessors[i].isLive && phi.inputs[i] != zapInstruction) { | |
| 1053 replaceInput(i, phi, zapInstruction); | |
| 1054 } | |
| 1055 } | |
| 1056 }); | |
| 1057 if (predecessors.length < 2) continue L; | |
| 1058 // Find the index of the single live predecessor if it exists. | |
| 1059 int indexOfLive = -1; | |
| 1060 for (int i = 0; i < predecessors.length; i++) { | |
| 1061 if (predecessors[i].isLive) { | |
| 1062 if (indexOfLive >= 0) continue L; | |
| 1063 indexOfLive = i; | |
| 1064 } | |
| 1065 } | |
| 1066 // Run through the phis of the block and replace them with their input | |
| 1067 // that comes from the only live predecessor if that dominates the phi. | |
| 1068 block.forEachPhi((HPhi phi) { | |
| 1069 HInstruction replacement = (indexOfLive >= 0) | |
| 1070 ? phi.inputs[indexOfLive] : zapInstruction; | |
| 1071 if (replacement.dominates(phi)) { | |
| 1072 block.rewrite(phi, replacement); | |
| 1073 block.removePhi(phi); | |
| 1074 } | |
| 1075 }); | |
| 1076 } | |
| 1077 } | |
| 1078 | |
| 1079 void replaceInput(int i, HInstruction from, HInstruction by) { | |
| 1080 from.inputs[i].usedBy.remove(from); | |
| 1081 from.inputs[i] = by; | |
| 1082 by.usedBy.add(from); | |
| 1083 } | |
| 1084 | |
| 1085 void removeUsers(HInstruction instruction) { | |
| 1086 instruction.usedBy.forEach((user) { | |
| 1087 removeInput(user, instruction); | |
| 1088 }); | |
| 1089 instruction.usedBy.clear(); | |
| 1090 } | |
| 1091 | |
| 1092 void removeInput(HInstruction user, HInstruction input) { | |
| 1093 List<HInstruction> inputs = user.inputs; | |
| 1094 for (int i = 0, length = inputs.length; i < length; i++) { | |
| 1095 if (input == inputs[i]) { | |
| 1096 user.inputs[i] = zapInstruction; | |
| 1097 zapInstruction.usedBy.add(user); | |
| 1098 } | |
| 1099 } | |
| 1100 } | |
| 1101 } | |
| 1102 | |
| 1103 class SsaLiveBlockAnalyzer extends HBaseVisitor { | |
| 1104 final HGraph graph; | |
| 1105 final Compiler compiler; | |
| 1106 final Set<HBasicBlock> live = new Set<HBasicBlock>(); | |
| 1107 final List<HBasicBlock> worklist = <HBasicBlock>[]; | |
| 1108 | |
| 1109 SsaLiveBlockAnalyzer(this.graph, this.compiler); | |
| 1110 | |
| 1111 JavaScriptBackend get backend => compiler.backend; | |
| 1112 Map<HInstruction, Range> get ranges => backend.optimizer.ranges; | |
| 1113 | |
| 1114 bool isDeadBlock(HBasicBlock block) => !live.contains(block); | |
| 1115 | |
| 1116 void analyze() { | |
| 1117 markBlockLive(graph.entry); | |
| 1118 while (!worklist.isEmpty) { | |
| 1119 HBasicBlock live = worklist.removeLast(); | |
| 1120 live.last.accept(this); | |
| 1121 } | |
| 1122 } | |
| 1123 | |
| 1124 void markBlockLive(HBasicBlock block) { | |
| 1125 if (!live.contains(block)) { | |
| 1126 worklist.add(block); | |
| 1127 live.add(block); | |
| 1128 } | |
| 1129 } | |
| 1130 | |
| 1131 void visitControlFlow(HControlFlow instruction) { | |
| 1132 instruction.block.successors.forEach(markBlockLive); | |
| 1133 } | |
| 1134 | |
| 1135 void visitIf(HIf instruction) { | |
| 1136 HInstruction condition = instruction.condition; | |
| 1137 if (condition.isConstant()) { | |
| 1138 if (condition.isConstantTrue()) { | |
| 1139 markBlockLive(instruction.thenBlock); | |
| 1140 } else { | |
| 1141 markBlockLive(instruction.elseBlock); | |
| 1142 } | |
| 1143 } else { | |
| 1144 visitControlFlow(instruction); | |
| 1145 } | |
| 1146 } | |
| 1147 | |
| 1148 void visitSwitch(HSwitch node) { | |
| 1149 if (node.expression.isInteger(compiler)) { | |
| 1150 Range switchRange = ranges[node.expression]; | |
| 1151 if (switchRange != null && | |
| 1152 switchRange.lower is IntValue && | |
| 1153 switchRange.upper is IntValue) { | |
| 1154 IntValue lowerValue = switchRange.lower; | |
| 1155 IntValue upperValue = switchRange.upper; | |
| 1156 int lower = lowerValue.value; | |
| 1157 int upper = upperValue.value; | |
| 1158 Set<int> liveLabels = new Set<int>(); | |
| 1159 for (int pos = 1; pos < node.inputs.length; pos++) { | |
| 1160 HConstant input = node.inputs[pos]; | |
| 1161 if (!input.isConstantInteger()) continue; | |
| 1162 IntConstantValue constant = input.constant; | |
| 1163 int label = constant.primitiveValue; | |
| 1164 if (!liveLabels.contains(label) && | |
| 1165 label <= upper && | |
| 1166 label >= lower) { | |
| 1167 markBlockLive(node.block.successors[pos - 1]); | |
| 1168 liveLabels.add(label); | |
| 1169 } | |
| 1170 } | |
| 1171 if (liveLabels.length != upper - lower + 1) { | |
| 1172 markBlockLive(node.defaultTarget); | |
| 1173 } | |
| 1174 return; | |
| 1175 } | |
| 1176 } | |
| 1177 visitControlFlow(node); | |
| 1178 } | |
| 1179 } | |
| 1180 | |
| 1181 class SsaDeadPhiEliminator implements OptimizationPhase { | |
| 1182 final String name = "SsaDeadPhiEliminator"; | |
| 1183 | |
| 1184 void visitGraph(HGraph graph) { | |
| 1185 final List<HPhi> worklist = <HPhi>[]; | |
| 1186 // A set to keep track of the live phis that we found. | |
| 1187 final Set<HPhi> livePhis = new Set<HPhi>(); | |
| 1188 | |
| 1189 // Add to the worklist all live phis: phis referenced by non-phi | |
| 1190 // instructions. | |
| 1191 for (final block in graph.blocks) { | |
| 1192 block.forEachPhi((HPhi phi) { | |
| 1193 for (final user in phi.usedBy) { | |
| 1194 if (user is !HPhi) { | |
| 1195 worklist.add(phi); | |
| 1196 livePhis.add(phi); | |
| 1197 break; | |
| 1198 } | |
| 1199 } | |
| 1200 }); | |
| 1201 } | |
| 1202 | |
| 1203 // Process the worklist by propagating liveness to phi inputs. | |
| 1204 while (!worklist.isEmpty) { | |
| 1205 HPhi phi = worklist.removeLast(); | |
| 1206 for (final input in phi.inputs) { | |
| 1207 if (input is HPhi && !livePhis.contains(input)) { | |
| 1208 worklist.add(input); | |
| 1209 livePhis.add(input); | |
| 1210 } | |
| 1211 } | |
| 1212 } | |
| 1213 | |
| 1214 // Remove phis that are not live. | |
| 1215 // Traverse in reverse order to remove phis with no uses before the | |
| 1216 // phis that they might use. | |
| 1217 // NOTICE: Doesn't handle circular references, but we don't currently | |
| 1218 // create any. | |
| 1219 List<HBasicBlock> blocks = graph.blocks; | |
| 1220 for (int i = blocks.length - 1; i >= 0; i--) { | |
| 1221 HBasicBlock block = blocks[i]; | |
| 1222 HPhi current = block.phis.first; | |
| 1223 HPhi next = null; | |
| 1224 while (current != null) { | |
| 1225 next = current.next; | |
| 1226 if (!livePhis.contains(current) | |
| 1227 // TODO(ahe): Not sure the following is correct. | |
| 1228 && current.usedBy.isEmpty) { | |
| 1229 block.removePhi(current); | |
| 1230 } | |
| 1231 current = next; | |
| 1232 } | |
| 1233 } | |
| 1234 } | |
| 1235 } | |
| 1236 | |
| 1237 class SsaRedundantPhiEliminator implements OptimizationPhase { | |
| 1238 final String name = "SsaRedundantPhiEliminator"; | |
| 1239 | |
| 1240 void visitGraph(HGraph graph) { | |
| 1241 final List<HPhi> worklist = <HPhi>[]; | |
| 1242 | |
| 1243 // Add all phis in the worklist. | |
| 1244 for (final block in graph.blocks) { | |
| 1245 block.forEachPhi((HPhi phi) => worklist.add(phi)); | |
| 1246 } | |
| 1247 | |
| 1248 while (!worklist.isEmpty) { | |
| 1249 HPhi phi = worklist.removeLast(); | |
| 1250 | |
| 1251 // If the phi has already been processed, continue. | |
| 1252 if (!phi.isInBasicBlock()) continue; | |
| 1253 | |
| 1254 // Find if the inputs of the phi are the same instruction. | |
| 1255 // The builder ensures that phi.inputs[0] cannot be the phi | |
| 1256 // itself. | |
| 1257 assert(!identical(phi.inputs[0], phi)); | |
| 1258 HInstruction candidate = phi.inputs[0]; | |
| 1259 for (int i = 1; i < phi.inputs.length; i++) { | |
| 1260 HInstruction input = phi.inputs[i]; | |
| 1261 // If the input is the phi, the phi is still candidate for | |
| 1262 // elimination. | |
| 1263 if (!identical(input, candidate) && !identical(input, phi)) { | |
| 1264 candidate = null; | |
| 1265 break; | |
| 1266 } | |
| 1267 } | |
| 1268 | |
| 1269 // If the inputs are not the same, continue. | |
| 1270 if (candidate == null) continue; | |
| 1271 | |
| 1272 // Because we're updating the users of this phi, we may have new | |
| 1273 // phis candidate for elimination. Add phis that used this phi | |
| 1274 // to the worklist. | |
| 1275 for (final user in phi.usedBy) { | |
| 1276 if (user is HPhi) worklist.add(user); | |
| 1277 } | |
| 1278 phi.block.rewrite(phi, candidate); | |
| 1279 phi.block.removePhi(phi); | |
| 1280 } | |
| 1281 } | |
| 1282 } | |
| 1283 | |
| 1284 class GvnWorkItem { | |
| 1285 final HBasicBlock block; | |
| 1286 final ValueSet valueSet; | |
| 1287 GvnWorkItem(this.block, this.valueSet); | |
| 1288 } | |
| 1289 | |
| 1290 class SsaGlobalValueNumberer implements OptimizationPhase { | |
| 1291 final String name = "SsaGlobalValueNumberer"; | |
| 1292 final Compiler compiler; | |
| 1293 final Set<int> visited; | |
| 1294 | |
| 1295 List<int> blockChangesFlags; | |
| 1296 List<int> loopChangesFlags; | |
| 1297 | |
| 1298 SsaGlobalValueNumberer(this.compiler) : visited = new Set<int>(); | |
| 1299 | |
| 1300 void visitGraph(HGraph graph) { | |
| 1301 computeChangesFlags(graph); | |
| 1302 moveLoopInvariantCode(graph); | |
| 1303 List<GvnWorkItem> workQueue = | |
| 1304 <GvnWorkItem>[new GvnWorkItem(graph.entry, new ValueSet())]; | |
| 1305 do { | |
| 1306 GvnWorkItem item = workQueue.removeLast(); | |
| 1307 visitBasicBlock(item.block, item.valueSet, workQueue); | |
| 1308 } while (!workQueue.isEmpty); | |
| 1309 } | |
| 1310 | |
| 1311 void moveLoopInvariantCode(HGraph graph) { | |
| 1312 for (int i = graph.blocks.length - 1; i >= 0; i--) { | |
| 1313 HBasicBlock block = graph.blocks[i]; | |
| 1314 if (block.isLoopHeader()) { | |
| 1315 int changesFlags = loopChangesFlags[block.id]; | |
| 1316 HLoopInformation info = block.loopInformation; | |
| 1317 // Iterate over all blocks of this loop. Note that blocks in | |
| 1318 // inner loops are not visited here, but we know they | |
| 1319 // were visited before because we are iterating in post-order. | |
| 1320 // So instructions that are GVN'ed in an inner loop are in their | |
| 1321 // loop entry, and [info.blocks] contains this loop entry. | |
| 1322 moveLoopInvariantCodeFromBlock(block, block, changesFlags); | |
| 1323 for (HBasicBlock other in info.blocks) { | |
| 1324 moveLoopInvariantCodeFromBlock(other, block, changesFlags); | |
| 1325 } | |
| 1326 } | |
| 1327 } | |
| 1328 } | |
| 1329 | |
| 1330 void moveLoopInvariantCodeFromBlock(HBasicBlock block, | |
| 1331 HBasicBlock loopHeader, | |
| 1332 int changesFlags) { | |
| 1333 assert(block.parentLoopHeader == loopHeader || block == loopHeader); | |
| 1334 HBasicBlock preheader = loopHeader.predecessors[0]; | |
| 1335 int dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); | |
| 1336 HInstruction instruction = block.first; | |
| 1337 bool isLoopAlwaysTaken() { | |
| 1338 HInstruction instruction = loopHeader.last; | |
| 1339 assert(instruction is HGoto || instruction is HLoopBranch); | |
| 1340 return instruction is HGoto | |
| 1341 || instruction.inputs[0].isConstantTrue(); | |
| 1342 } | |
| 1343 bool firstInstructionInLoop = block == loopHeader | |
| 1344 // Compensate for lack of code motion. | |
| 1345 || (blockChangesFlags[loopHeader.id] == 0 | |
| 1346 && isLoopAlwaysTaken() | |
| 1347 && loopHeader.successors[0] == block); | |
| 1348 while (instruction != null) { | |
| 1349 HInstruction next = instruction.next; | |
| 1350 if (instruction.useGvn() && instruction.isMovable | |
| 1351 && (!instruction.canThrow() || firstInstructionInLoop) | |
| 1352 && !instruction.sideEffects.dependsOn(dependsFlags)) { | |
| 1353 bool loopInvariantInputs = true; | |
| 1354 List<HInstruction> inputs = instruction.inputs; | |
| 1355 for (int i = 0, length = inputs.length; i < length; i++) { | |
| 1356 if (isInputDefinedAfterDominator(inputs[i], preheader)) { | |
| 1357 loopInvariantInputs = false; | |
| 1358 break; | |
| 1359 } | |
| 1360 } | |
| 1361 | |
| 1362 // If the inputs are loop invariant, we can move the | |
| 1363 // instruction from the current block to the pre-header block. | |
| 1364 if (loopInvariantInputs) { | |
| 1365 block.detach(instruction); | |
| 1366 preheader.moveAtExit(instruction); | |
| 1367 } else { | |
| 1368 firstInstructionInLoop = false; | |
| 1369 } | |
| 1370 } | |
| 1371 int oldChangesFlags = changesFlags; | |
| 1372 changesFlags |= instruction.sideEffects.getChangesFlags(); | |
| 1373 if (oldChangesFlags != changesFlags) { | |
| 1374 dependsFlags = SideEffects.computeDependsOnFlags(changesFlags); | |
| 1375 } | |
| 1376 instruction = next; | |
| 1377 } | |
| 1378 } | |
| 1379 | |
| 1380 bool isInputDefinedAfterDominator(HInstruction input, | |
| 1381 HBasicBlock dominator) { | |
| 1382 return input.block.id > dominator.id; | |
| 1383 } | |
| 1384 | |
| 1385 void visitBasicBlock( | |
| 1386 HBasicBlock block, ValueSet values, List<GvnWorkItem> workQueue) { | |
| 1387 HInstruction instruction = block.first; | |
| 1388 if (block.isLoopHeader()) { | |
| 1389 int flags = loopChangesFlags[block.id]; | |
| 1390 values.kill(flags); | |
| 1391 } | |
| 1392 while (instruction != null) { | |
| 1393 HInstruction next = instruction.next; | |
| 1394 int flags = instruction.sideEffects.getChangesFlags(); | |
| 1395 assert(flags == 0 || !instruction.useGvn()); | |
| 1396 values.kill(flags); | |
| 1397 if (instruction.useGvn()) { | |
| 1398 HInstruction other = values.lookup(instruction); | |
| 1399 if (other != null) { | |
| 1400 assert(other.gvnEquals(instruction) && instruction.gvnEquals(other)); | |
| 1401 block.rewriteWithBetterUser(instruction, other); | |
| 1402 block.remove(instruction); | |
| 1403 } else { | |
| 1404 values.add(instruction); | |
| 1405 } | |
| 1406 } | |
| 1407 instruction = next; | |
| 1408 } | |
| 1409 | |
| 1410 List<HBasicBlock> dominatedBlocks = block.dominatedBlocks; | |
| 1411 for (int i = 0, length = dominatedBlocks.length; i < length; i++) { | |
| 1412 HBasicBlock dominated = dominatedBlocks[i]; | |
| 1413 // No need to copy the value set for the last child. | |
| 1414 ValueSet successorValues = (i == length - 1) ? values : values.copy(); | |
| 1415 // If we have no values in our set, we do not have to kill | |
| 1416 // anything. Also, if the range of block ids from the current | |
| 1417 // block to the dominated block is empty, there is no blocks on | |
| 1418 // any path from the current block to the dominated block so we | |
| 1419 // don't have to do anything either. | |
| 1420 assert(block.id < dominated.id); | |
| 1421 if (!successorValues.isEmpty && block.id + 1 < dominated.id) { | |
| 1422 visited.clear(); | |
| 1423 List<HBasicBlock> workQueue = <HBasicBlock>[dominated]; | |
| 1424 int changesFlags = 0; | |
| 1425 do { | |
| 1426 HBasicBlock current = workQueue.removeLast(); | |
| 1427 changesFlags |= | |
| 1428 getChangesFlagsForDominatedBlock(block, current, workQueue); | |
| 1429 } while (!workQueue.isEmpty); | |
| 1430 successorValues.kill(changesFlags); | |
| 1431 } | |
| 1432 workQueue.add(new GvnWorkItem(dominated, successorValues)); | |
| 1433 } | |
| 1434 } | |
| 1435 | |
| 1436 void computeChangesFlags(HGraph graph) { | |
| 1437 // Create the changes flags lists. Make sure to initialize the | |
| 1438 // loop changes flags list to zero so we can use bitwise or when | |
| 1439 // propagating loop changes upwards. | |
| 1440 final int length = graph.blocks.length; | |
| 1441 blockChangesFlags = new List<int>(length); | |
| 1442 loopChangesFlags = new List<int>(length); | |
| 1443 for (int i = 0; i < length; i++) loopChangesFlags[i] = 0; | |
| 1444 | |
| 1445 // Run through all the basic blocks in the graph and fill in the | |
| 1446 // changes flags lists. | |
| 1447 for (int i = length - 1; i >= 0; i--) { | |
| 1448 final HBasicBlock block = graph.blocks[i]; | |
| 1449 final int id = block.id; | |
| 1450 | |
| 1451 // Compute block changes flags for the block. | |
| 1452 int changesFlags = 0; | |
| 1453 HInstruction instruction = block.first; | |
| 1454 while (instruction != null) { | |
| 1455 changesFlags |= instruction.sideEffects.getChangesFlags(); | |
| 1456 instruction = instruction.next; | |
| 1457 } | |
| 1458 assert(blockChangesFlags[id] == null); | |
| 1459 blockChangesFlags[id] = changesFlags; | |
| 1460 | |
| 1461 // Loop headers are part of their loop, so update the loop | |
| 1462 // changes flags accordingly. | |
| 1463 if (block.isLoopHeader()) { | |
| 1464 loopChangesFlags[id] |= changesFlags; | |
| 1465 } | |
| 1466 | |
| 1467 // Propagate loop changes flags upwards. | |
| 1468 HBasicBlock parentLoopHeader = block.parentLoopHeader; | |
| 1469 if (parentLoopHeader != null) { | |
| 1470 loopChangesFlags[parentLoopHeader.id] |= (block.isLoopHeader()) | |
| 1471 ? loopChangesFlags[id] | |
| 1472 : changesFlags; | |
| 1473 } | |
| 1474 } | |
| 1475 } | |
| 1476 | |
| 1477 int getChangesFlagsForDominatedBlock(HBasicBlock dominator, | |
| 1478 HBasicBlock dominated, | |
| 1479 List<HBasicBlock> workQueue) { | |
| 1480 int changesFlags = 0; | |
| 1481 List<HBasicBlock> predecessors = dominated.predecessors; | |
| 1482 for (int i = 0, length = predecessors.length; i < length; i++) { | |
| 1483 HBasicBlock block = predecessors[i]; | |
| 1484 int id = block.id; | |
| 1485 // If the current predecessor block is on the path from the | |
| 1486 // dominator to the dominated, it must have an id that is in the | |
| 1487 // range from the dominator to the dominated. | |
| 1488 if (dominator.id < id && id < dominated.id && !visited.contains(id)) { | |
| 1489 visited.add(id); | |
| 1490 changesFlags |= blockChangesFlags[id]; | |
| 1491 // Loop bodies might not be on the path from dominator to dominated, | |
| 1492 // but they can invalidate values. | |
| 1493 changesFlags |= loopChangesFlags[id]; | |
| 1494 workQueue.add(block); | |
| 1495 } | |
| 1496 } | |
| 1497 return changesFlags; | |
| 1498 } | |
| 1499 } | |
| 1500 | |
| 1501 // This phase merges equivalent instructions on different paths into | |
| 1502 // one instruction in a dominator block. It runs through the graph | |
| 1503 // post dominator order and computes a ValueSet for each block of | |
| 1504 // instructions that can be moved to a dominator block. These | |
| 1505 // instructions are the ones that: | |
| 1506 // 1) can be used for GVN, and | |
| 1507 // 2) do not use definitions of their own block. | |
| 1508 // | |
| 1509 // A basic block looks at its sucessors and finds the intersection of | |
| 1510 // these computed ValueSet. It moves all instructions of the | |
| 1511 // intersection into its own list of instructions. | |
| 1512 class SsaCodeMotion extends HBaseVisitor implements OptimizationPhase { | |
| 1513 final String name = "SsaCodeMotion"; | |
| 1514 | |
| 1515 List<ValueSet> values; | |
| 1516 | |
| 1517 void visitGraph(HGraph graph) { | |
| 1518 values = new List<ValueSet>(graph.blocks.length); | |
| 1519 for (int i = 0; i < graph.blocks.length; i++) { | |
| 1520 values[graph.blocks[i].id] = new ValueSet(); | |
| 1521 } | |
| 1522 visitPostDominatorTree(graph); | |
| 1523 } | |
| 1524 | |
| 1525 void visitBasicBlock(HBasicBlock block) { | |
| 1526 List<HBasicBlock> successors = block.successors; | |
| 1527 | |
| 1528 // Phase 1: get the ValueSet of all successors (if there are more than one), | |
| 1529 // compute the intersection and move the instructions of the intersection | |
| 1530 // into this block. | |
| 1531 if (successors.length > 1) { | |
| 1532 ValueSet instructions = values[successors[0].id]; | |
| 1533 for (int i = 1; i < successors.length; i++) { | |
| 1534 ValueSet other = values[successors[i].id]; | |
| 1535 instructions = instructions.intersection(other); | |
| 1536 } | |
| 1537 | |
| 1538 if (!instructions.isEmpty) { | |
| 1539 List<HInstruction> list = instructions.toList(); | |
| 1540 for (HInstruction instruction in list) { | |
| 1541 // Move the instruction to the current block. | |
| 1542 instruction.block.detach(instruction); | |
| 1543 block.moveAtExit(instruction); | |
| 1544 // Go through all successors and rewrite their instruction | |
| 1545 // to the shared one. | |
| 1546 for (final successor in successors) { | |
| 1547 HInstruction toRewrite = values[successor.id].lookup(instruction); | |
| 1548 if (toRewrite != instruction) { | |
| 1549 successor.rewriteWithBetterUser(toRewrite, instruction); | |
| 1550 successor.remove(toRewrite); | |
| 1551 } | |
| 1552 } | |
| 1553 } | |
| 1554 } | |
| 1555 } | |
| 1556 | |
| 1557 // Don't try to merge instructions to a dominator if we have | |
| 1558 // multiple predecessors. | |
| 1559 if (block.predecessors.length != 1) return; | |
| 1560 | |
| 1561 // Phase 2: Go through all instructions of this block and find | |
| 1562 // which instructions can be moved to a dominator block. | |
| 1563 ValueSet set_ = values[block.id]; | |
| 1564 HInstruction instruction = block.first; | |
| 1565 int flags = 0; | |
| 1566 while (instruction != null) { | |
| 1567 int dependsFlags = SideEffects.computeDependsOnFlags(flags); | |
| 1568 flags |= instruction.sideEffects.getChangesFlags(); | |
| 1569 | |
| 1570 HInstruction current = instruction; | |
| 1571 instruction = instruction.next; | |
| 1572 if (!current.useGvn() || !current.isMovable) continue; | |
| 1573 // TODO(sra): We could move throwing instructions provided we keep the | |
| 1574 // exceptions in the same order. This requires they are in the same order | |
| 1575 // in all successors, which is not tracked by the ValueSet. | |
| 1576 if (current.canThrow()) continue; | |
| 1577 if (current.sideEffects.dependsOn(dependsFlags)) continue; | |
| 1578 | |
| 1579 bool canBeMoved = true; | |
| 1580 for (final HInstruction input in current.inputs) { | |
| 1581 if (input.block == block) { | |
| 1582 canBeMoved = false; | |
| 1583 break; | |
| 1584 } | |
| 1585 } | |
| 1586 if (!canBeMoved) continue; | |
| 1587 | |
| 1588 HInstruction existing = set_.lookup(current); | |
| 1589 if (existing == null) { | |
| 1590 set_.add(current); | |
| 1591 } else { | |
| 1592 block.rewriteWithBetterUser(current, existing); | |
| 1593 block.remove(current); | |
| 1594 } | |
| 1595 } | |
| 1596 } | |
| 1597 } | |
| 1598 | |
| 1599 class SsaTypeConversionInserter extends HBaseVisitor | |
| 1600 implements OptimizationPhase { | |
| 1601 final String name = "SsaTypeconversionInserter"; | |
| 1602 final Compiler compiler; | |
| 1603 | |
| 1604 SsaTypeConversionInserter(this.compiler); | |
| 1605 | |
| 1606 void visitGraph(HGraph graph) { | |
| 1607 visitDominatorTree(graph); | |
| 1608 } | |
| 1609 | |
| 1610 // Update users of [input] that are dominated by [:dominator.first:] | |
| 1611 // to use [TypeKnown] of [input] instead. As the type information depends | |
| 1612 // on the control flow, we mark the inserted [HTypeKnown] nodes as | |
| 1613 // non-movable. | |
| 1614 void insertTypePropagationForDominatedUsers(HBasicBlock dominator, | |
| 1615 HInstruction input, | |
| 1616 TypeMask convertedType) { | |
| 1617 Setlet<HInstruction> dominatedUsers = input.dominatedUsers(dominator.first); | |
| 1618 if (dominatedUsers.isEmpty) return; | |
| 1619 | |
| 1620 HTypeKnown newInput = new HTypeKnown.pinned(convertedType, input); | |
| 1621 dominator.addBefore(dominator.first, newInput); | |
| 1622 dominatedUsers.forEach((HInstruction user) { | |
| 1623 user.changeUse(input, newInput); | |
| 1624 }); | |
| 1625 } | |
| 1626 | |
| 1627 void visitIs(HIs instruction) { | |
| 1628 DartType type = instruction.typeExpression; | |
| 1629 Element element = type.element; | |
| 1630 if (!instruction.isRawCheck) { | |
| 1631 return; | |
| 1632 } else if (element.isTypedef) { | |
| 1633 return; | |
| 1634 } | |
| 1635 | |
| 1636 List<HInstruction> ifUsers = <HInstruction>[]; | |
| 1637 List<HInstruction> notIfUsers = <HInstruction>[]; | |
| 1638 | |
| 1639 collectIfUsers(instruction, ifUsers, notIfUsers); | |
| 1640 | |
| 1641 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; | |
| 1642 | |
| 1643 TypeMask convertedType = | |
| 1644 new TypeMask.nonNullSubtype(element, compiler.world); | |
| 1645 HInstruction input = instruction.expression; | |
| 1646 | |
| 1647 for (HIf ifUser in ifUsers) { | |
| 1648 insertTypePropagationForDominatedUsers(ifUser.thenBlock, input, | |
| 1649 convertedType); | |
| 1650 // TODO(ngeoffray): Also change uses for the else block on a type | |
| 1651 // that knows it is not of a specific type. | |
| 1652 } | |
| 1653 for (HIf ifUser in notIfUsers) { | |
| 1654 insertTypePropagationForDominatedUsers(ifUser.elseBlock, input, | |
| 1655 convertedType); | |
| 1656 // TODO(ngeoffray): Also change uses for the then block on a type | |
| 1657 // that knows it is not of a specific type. | |
| 1658 } | |
| 1659 } | |
| 1660 | |
| 1661 void visitIdentity(HIdentity instruction) { | |
| 1662 // At HIf(HIdentity(x, null)) strengthens x to non-null on else branch. | |
| 1663 HInstruction left = instruction.left; | |
| 1664 HInstruction right = instruction.right; | |
| 1665 HInstruction input; | |
| 1666 | |
| 1667 if (left.isConstantNull()) { | |
| 1668 input = right; | |
| 1669 } else if (right.isConstantNull()) { | |
| 1670 input = left; | |
| 1671 } else { | |
| 1672 return; | |
| 1673 } | |
| 1674 | |
| 1675 if (!input.instructionType.isNullable) return; | |
| 1676 | |
| 1677 List<HInstruction> ifUsers = <HInstruction>[]; | |
| 1678 List<HInstruction> notIfUsers = <HInstruction>[]; | |
| 1679 | |
| 1680 collectIfUsers(instruction, ifUsers, notIfUsers); | |
| 1681 | |
| 1682 if (ifUsers.isEmpty && notIfUsers.isEmpty) return; | |
| 1683 | |
| 1684 TypeMask nonNullType = input.instructionType.nonNullable(); | |
| 1685 | |
| 1686 for (HIf ifUser in ifUsers) { | |
| 1687 insertTypePropagationForDominatedUsers(ifUser.elseBlock, input, | |
| 1688 nonNullType); | |
| 1689 // Uses in thenBlock are `null`, but probably not common. | |
| 1690 } | |
| 1691 for (HIf ifUser in notIfUsers) { | |
| 1692 insertTypePropagationForDominatedUsers(ifUser.thenBlock, input, | |
| 1693 nonNullType); | |
| 1694 // Uses in elseBlock are `null`, but probably not common. | |
| 1695 } | |
| 1696 } | |
| 1697 | |
| 1698 collectIfUsers(HInstruction instruction, | |
| 1699 List<HInstruction> ifUsers, | |
| 1700 List<HInstruction> notIfUsers) { | |
| 1701 for (HInstruction user in instruction.usedBy) { | |
| 1702 if (user is HIf) { | |
| 1703 ifUsers.add(user); | |
| 1704 } else if (user is HNot) { | |
| 1705 collectIfUsers(user, notIfUsers, ifUsers); | |
| 1706 } | |
| 1707 } | |
| 1708 } | |
| 1709 } | |
| 1710 | |
| 1711 /** | |
| 1712 * Optimization phase that tries to eliminate memory loads (for | |
| 1713 * example [HFieldGet]), when it knows the value stored in that memory | |
| 1714 * location. | |
| 1715 */ | |
| 1716 class SsaLoadElimination extends HBaseVisitor implements OptimizationPhase { | |
| 1717 final Compiler compiler; | |
| 1718 final String name = "SsaLoadElimination"; | |
| 1719 MemorySet memorySet; | |
| 1720 List<MemorySet> memories; | |
| 1721 | |
| 1722 SsaLoadElimination(this.compiler); | |
| 1723 | |
| 1724 void visitGraph(HGraph graph) { | |
| 1725 memories = new List<MemorySet>(graph.blocks.length); | |
| 1726 List<HBasicBlock> blocks = graph.blocks; | |
| 1727 for (int i = 0; i < blocks.length; i++) { | |
| 1728 HBasicBlock block = blocks[i]; | |
| 1729 visitBasicBlock(block); | |
| 1730 if (block.successors.isNotEmpty && block.successors[0].isLoopHeader()) { | |
| 1731 // We've reached the ending block of a loop. Iterate over the | |
| 1732 // blocks of the loop again to take values that flow from that | |
| 1733 // ending block into account. | |
| 1734 for (int j = block.successors[0].id; j <= block.id; j++) { | |
| 1735 visitBasicBlock(blocks[j]); | |
| 1736 } | |
| 1737 } | |
| 1738 } | |
| 1739 } | |
| 1740 | |
| 1741 void visitBasicBlock(HBasicBlock block) { | |
| 1742 if (block.predecessors.length == 0) { | |
| 1743 // Entry block. | |
| 1744 memorySet = new MemorySet(compiler); | |
| 1745 } else if (block.predecessors.length == 1 | |
| 1746 && block.predecessors[0].successors.length == 1) { | |
| 1747 // No need to clone, there is no other successor for | |
| 1748 // `block.predecessors[0]`, and this block has only one | |
| 1749 // predecessor. Since we are not going to visit | |
| 1750 // `block.predecessors[0]` again, we can just re-use its | |
| 1751 // [memorySet]. | |
| 1752 memorySet = memories[block.predecessors[0].id]; | |
| 1753 } else if (block.predecessors.length == 1) { | |
| 1754 // Clone the memorySet of the predecessor, because it is also used | |
| 1755 // by other successors of it. | |
| 1756 memorySet = memories[block.predecessors[0].id].clone(); | |
| 1757 } else { | |
| 1758 // Compute the intersection of all predecessors. | |
| 1759 memorySet = memories[block.predecessors[0].id]; | |
| 1760 for (int i = 1; i < block.predecessors.length; i++) { | |
| 1761 memorySet = memorySet.intersectionFor( | |
| 1762 memories[block.predecessors[i].id], block, i); | |
| 1763 } | |
| 1764 } | |
| 1765 | |
| 1766 memories[block.id] = memorySet; | |
| 1767 HInstruction instruction = block.first; | |
| 1768 while (instruction != null) { | |
| 1769 HInstruction next = instruction.next; | |
| 1770 instruction.accept(this); | |
| 1771 instruction = next; | |
| 1772 } | |
| 1773 } | |
| 1774 | |
| 1775 void visitFieldGet(HFieldGet instruction) { | |
| 1776 if (instruction.isNullCheck) return; | |
| 1777 Element element = instruction.element; | |
| 1778 HInstruction receiver = | |
| 1779 instruction.getDartReceiver(compiler).nonCheck(); | |
| 1780 HInstruction existing = memorySet.lookupFieldValue(element, receiver); | |
| 1781 if (existing != null) { | |
| 1782 instruction.block.rewriteWithBetterUser(instruction, existing); | |
| 1783 instruction.block.remove(instruction); | |
| 1784 } else { | |
| 1785 memorySet.registerFieldValue(element, receiver, instruction); | |
| 1786 } | |
| 1787 } | |
| 1788 | |
| 1789 void visitFieldSet(HFieldSet instruction) { | |
| 1790 HInstruction receiver = | |
| 1791 instruction.getDartReceiver(compiler).nonCheck(); | |
| 1792 memorySet.registerFieldValueUpdate( | |
| 1793 instruction.element, receiver, instruction.inputs.last); | |
| 1794 } | |
| 1795 | |
| 1796 void visitForeignNew(HForeignNew instruction) { | |
| 1797 memorySet.registerAllocation(instruction); | |
| 1798 int argumentIndex = 0; | |
| 1799 instruction.element.forEachInstanceField((_, Element member) { | |
| 1800 memorySet.registerFieldValue( | |
| 1801 member, instruction, instruction.inputs[argumentIndex++]); | |
| 1802 }, includeSuperAndInjectedMembers: true); | |
| 1803 // In case this instruction has as input non-escaping objects, we | |
| 1804 // need to mark these objects as escaping. | |
| 1805 memorySet.killAffectedBy(instruction); | |
| 1806 } | |
| 1807 | |
| 1808 void visitInstruction(HInstruction instruction) { | |
| 1809 memorySet.killAffectedBy(instruction); | |
| 1810 } | |
| 1811 | |
| 1812 void visitLazyStatic(HLazyStatic instruction) { | |
| 1813 handleStaticLoad(instruction.element, instruction); | |
| 1814 } | |
| 1815 | |
| 1816 void handleStaticLoad(Element element, HInstruction instruction) { | |
| 1817 HInstruction existing = memorySet.lookupFieldValue(element, null); | |
| 1818 if (existing != null) { | |
| 1819 instruction.block.rewriteWithBetterUser(instruction, existing); | |
| 1820 instruction.block.remove(instruction); | |
| 1821 } else { | |
| 1822 memorySet.registerFieldValue(element, null, instruction); | |
| 1823 } | |
| 1824 } | |
| 1825 | |
| 1826 void visitStatic(HStatic instruction) { | |
| 1827 handleStaticLoad(instruction.element, instruction); | |
| 1828 } | |
| 1829 | |
| 1830 void visitStaticStore(HStaticStore instruction) { | |
| 1831 memorySet.registerFieldValueUpdate( | |
| 1832 instruction.element, null, instruction.inputs.last); | |
| 1833 } | |
| 1834 | |
| 1835 void visitLiteralList(HLiteralList instruction) { | |
| 1836 memorySet.registerAllocation(instruction); | |
| 1837 memorySet.killAffectedBy(instruction); | |
| 1838 } | |
| 1839 | |
| 1840 void visitIndex(HIndex instruction) { | |
| 1841 HInstruction receiver = instruction.receiver.nonCheck(); | |
| 1842 HInstruction existing = | |
| 1843 memorySet.lookupKeyedValue(receiver, instruction.index); | |
| 1844 if (existing != null) { | |
| 1845 instruction.block.rewriteWithBetterUser(instruction, existing); | |
| 1846 instruction.block.remove(instruction); | |
| 1847 } else { | |
| 1848 memorySet.registerKeyedValue(receiver, instruction.index, instruction); | |
| 1849 } | |
| 1850 } | |
| 1851 | |
| 1852 void visitIndexAssign(HIndexAssign instruction) { | |
| 1853 HInstruction receiver = instruction.receiver.nonCheck(); | |
| 1854 memorySet.registerKeyedValueUpdate( | |
| 1855 receiver, instruction.index, instruction.value); | |
| 1856 } | |
| 1857 } | |
| 1858 | |
| 1859 /** | |
| 1860 * Holds values of memory places. | |
| 1861 */ | |
| 1862 class MemorySet { | |
| 1863 final Compiler compiler; | |
| 1864 | |
| 1865 /** | |
| 1866 * Maps a field to a map of receiver to value. | |
| 1867 */ | |
| 1868 final Map<Element, Map<HInstruction, HInstruction>> fieldValues = | |
| 1869 <Element, Map<HInstruction, HInstruction>> {}; | |
| 1870 | |
| 1871 /** | |
| 1872 * Maps a receiver to a map of keys to value. | |
| 1873 */ | |
| 1874 final Map<HInstruction, Map<HInstruction, HInstruction>> keyedValues = | |
| 1875 <HInstruction, Map<HInstruction, HInstruction>> {}; | |
| 1876 | |
| 1877 /** | |
| 1878 * Set of objects that we know don't escape the current function. | |
| 1879 */ | |
| 1880 final Setlet<HInstruction> nonEscapingReceivers = new Setlet<HInstruction>(); | |
| 1881 | |
| 1882 MemorySet(this.compiler); | |
| 1883 | |
| 1884 /** | |
| 1885 * Returns whether [first] and [second] always alias to the same object. | |
| 1886 */ | |
| 1887 bool mustAlias(HInstruction first, HInstruction second) { | |
| 1888 return first == second; | |
| 1889 } | |
| 1890 | |
| 1891 /** | |
| 1892 * Returns whether [first] and [second] may alias to the same object. | |
| 1893 */ | |
| 1894 bool mayAlias(HInstruction first, HInstruction second) { | |
| 1895 if (mustAlias(first, second)) return true; | |
| 1896 if (isConcrete(first) && isConcrete(second)) return false; | |
| 1897 if (nonEscapingReceivers.contains(first)) return false; | |
| 1898 if (nonEscapingReceivers.contains(second)) return false; | |
| 1899 // Typed arrays of different types might have a shared buffer. | |
| 1900 if (couldBeTypedArray(first) && couldBeTypedArray(second)) return true; | |
| 1901 TypeMask intersection = first.instructionType.intersection( | |
| 1902 second.instructionType, compiler.world); | |
| 1903 if (intersection.isEmpty) return false; | |
| 1904 return true; | |
| 1905 } | |
| 1906 | |
| 1907 bool isFinal(Element element) { | |
| 1908 return compiler.world.fieldNeverChanges(element); | |
| 1909 } | |
| 1910 | |
| 1911 bool isConcrete(HInstruction instruction) { | |
| 1912 return instruction is HForeignNew | |
| 1913 || instruction is HConstant | |
| 1914 || instruction is HLiteralList; | |
| 1915 } | |
| 1916 | |
| 1917 bool couldBeTypedArray(HInstruction receiver) { | |
| 1918 JavaScriptBackend backend = compiler.backend; | |
| 1919 return backend.couldBeTypedArray(receiver.instructionType); | |
| 1920 } | |
| 1921 | |
| 1922 /** | |
| 1923 * Returns whether [receiver] escapes the current function. | |
| 1924 */ | |
| 1925 bool escapes(HInstruction receiver) { | |
| 1926 return !nonEscapingReceivers.contains(receiver); | |
| 1927 } | |
| 1928 | |
| 1929 void registerAllocation(HInstruction instruction) { | |
| 1930 nonEscapingReceivers.add(instruction); | |
| 1931 } | |
| 1932 | |
| 1933 /** | |
| 1934 * Sets `receiver.element` to contain [value]. Kills all potential | |
| 1935 * places that may be affected by this update. | |
| 1936 */ | |
| 1937 void registerFieldValueUpdate(Element element, | |
| 1938 HInstruction receiver, | |
| 1939 HInstruction value) { | |
| 1940 if (element.isNative) return; // TODO(14955): Remove this restriction? | |
| 1941 // [value] is being set in some place in memory, we remove it from | |
| 1942 // the non-escaping set. | |
| 1943 nonEscapingReceivers.remove(value); | |
| 1944 Map<HInstruction, HInstruction> map = fieldValues.putIfAbsent( | |
| 1945 element, () => <HInstruction, HInstruction> {}); | |
| 1946 map.forEach((key, value) { | |
| 1947 if (mayAlias(receiver, key)) map[key] = null; | |
| 1948 }); | |
| 1949 map[receiver] = value; | |
| 1950 } | |
| 1951 | |
| 1952 /** | |
| 1953 * Registers that `receiver.element` is now [value]. | |
| 1954 */ | |
| 1955 void registerFieldValue(Element element, | |
| 1956 HInstruction receiver, | |
| 1957 HInstruction value) { | |
| 1958 if (element.isNative) return; // TODO(14955): Remove this restriction? | |
| 1959 Map<HInstruction, HInstruction> map = fieldValues.putIfAbsent( | |
| 1960 element, () => <HInstruction, HInstruction> {}); | |
| 1961 map[receiver] = value; | |
| 1962 } | |
| 1963 | |
| 1964 /** | |
| 1965 * Returns the value stored in `receiver.element`. Returns null if | |
| 1966 * we don't know. | |
| 1967 */ | |
| 1968 HInstruction lookupFieldValue(Element element, HInstruction receiver) { | |
| 1969 Map<HInstruction, HInstruction> map = fieldValues[element]; | |
| 1970 return (map == null) ? null : map[receiver]; | |
| 1971 } | |
| 1972 | |
| 1973 /** | |
| 1974 * Kill all places that may be affected by this [instruction]. Also | |
| 1975 * update the set of non-escaping objects in case [instruction] has | |
| 1976 * non-escaping objects in its inputs. | |
| 1977 */ | |
| 1978 void killAffectedBy(HInstruction instruction) { | |
| 1979 // Even if [instruction] does not have side effects, it may use | |
| 1980 // non-escaping objects and store them in a new object, which | |
| 1981 // make these objects escaping. | |
| 1982 // TODO(ngeoffray): We need a new side effect flag to know whether | |
| 1983 // an instruction allocates an object. | |
| 1984 instruction.inputs.forEach((input) { | |
| 1985 nonEscapingReceivers.remove(input); | |
| 1986 }); | |
| 1987 | |
| 1988 if (instruction.sideEffects.changesInstanceProperty() | |
| 1989 || instruction.sideEffects.changesStaticProperty()) { | |
| 1990 fieldValues.forEach((element, map) { | |
| 1991 if (isFinal(element)) return; | |
| 1992 map.forEach((receiver, value) { | |
| 1993 if (escapes(receiver)) { | |
| 1994 map[receiver] = null; | |
| 1995 } | |
| 1996 }); | |
| 1997 }); | |
| 1998 } | |
| 1999 | |
| 2000 if (instruction.sideEffects.changesIndex()) { | |
| 2001 keyedValues.forEach((receiver, map) { | |
| 2002 if (escapes(receiver)) { | |
| 2003 map.forEach((index, value) { | |
| 2004 map[index] = null; | |
| 2005 }); | |
| 2006 } | |
| 2007 }); | |
| 2008 } | |
| 2009 } | |
| 2010 | |
| 2011 /** | |
| 2012 * Returns the value stored in `receiver[index]`. Returns null if | |
| 2013 * we don't know. | |
| 2014 */ | |
| 2015 HInstruction lookupKeyedValue(HInstruction receiver, HInstruction index) { | |
| 2016 Map<HInstruction, HInstruction> map = keyedValues[receiver]; | |
| 2017 return (map == null) ? null : map[index]; | |
| 2018 } | |
| 2019 | |
| 2020 /** | |
| 2021 * Registers that `receiver[index]` is now [value]. | |
| 2022 */ | |
| 2023 void registerKeyedValue(HInstruction receiver, | |
| 2024 HInstruction index, | |
| 2025 HInstruction value) { | |
| 2026 Map<HInstruction, HInstruction> map = keyedValues.putIfAbsent( | |
| 2027 receiver, () => <HInstruction, HInstruction> {}); | |
| 2028 map[index] = value; | |
| 2029 } | |
| 2030 | |
| 2031 /** | |
| 2032 * Sets `receiver[index]` to contain [value]. Kills all potential | |
| 2033 * places that may be affected by this update. | |
| 2034 */ | |
| 2035 void registerKeyedValueUpdate(HInstruction receiver, | |
| 2036 HInstruction index, | |
| 2037 HInstruction value) { | |
| 2038 nonEscapingReceivers.remove(value); | |
| 2039 keyedValues.forEach((key, values) { | |
| 2040 if (mayAlias(receiver, key)) { | |
| 2041 // Typed arrays that are views of the same buffer may have different | |
| 2042 // offsets or element sizes, unless they are the same typed array. | |
| 2043 bool weakIndex = couldBeTypedArray(key) && !mustAlias(receiver, key); | |
| 2044 values.forEach((otherIndex, otherValue) { | |
| 2045 if (weakIndex || mayAlias(index, otherIndex)) { | |
| 2046 values[otherIndex] = null; | |
| 2047 } | |
| 2048 }); | |
| 2049 } | |
| 2050 }); | |
| 2051 | |
| 2052 // Typed arrays may narrow incoming values. | |
| 2053 if (couldBeTypedArray(receiver)) return; | |
| 2054 | |
| 2055 Map<HInstruction, HInstruction> map = keyedValues.putIfAbsent( | |
| 2056 receiver, () => <HInstruction, HInstruction> {}); | |
| 2057 map[index] = value; | |
| 2058 } | |
| 2059 | |
| 2060 /** | |
| 2061 * Returns null if either [first] or [second] is null. Otherwise | |
| 2062 * returns [first] if [first] and [second] are equal. Otherwise | |
| 2063 * creates or re-uses a phi in [block] that holds [first] and [second]. | |
| 2064 */ | |
| 2065 HInstruction findCommonInstruction(HInstruction first, | |
| 2066 HInstruction second, | |
| 2067 HBasicBlock block, | |
| 2068 int predecessorIndex) { | |
| 2069 if (first == null || second == null) return null; | |
| 2070 if (first == second) return first; | |
| 2071 TypeMask phiType = second.instructionType.union( | |
| 2072 first.instructionType, compiler.world); | |
| 2073 if (first is HPhi && first.block == block) { | |
| 2074 HPhi phi = first; | |
| 2075 phi.addInput(second); | |
| 2076 phi.instructionType = phiType; | |
| 2077 return phi; | |
| 2078 } else { | |
| 2079 HPhi phi = new HPhi.noInputs(null, phiType); | |
| 2080 block.addPhi(phi); | |
| 2081 // Previous predecessors had the same input. A phi must have | |
| 2082 // the same number of inputs as its block has predecessors. | |
| 2083 for (int i = 0; i < predecessorIndex; i++) { | |
| 2084 phi.addInput(first); | |
| 2085 } | |
| 2086 phi.addInput(second); | |
| 2087 return phi; | |
| 2088 } | |
| 2089 } | |
| 2090 | |
| 2091 /** | |
| 2092 * Returns the intersection between [this] and [other]. | |
| 2093 */ | |
| 2094 MemorySet intersectionFor(MemorySet other, | |
| 2095 HBasicBlock block, | |
| 2096 int predecessorIndex) { | |
| 2097 MemorySet result = new MemorySet(compiler); | |
| 2098 if (other == null) return result; | |
| 2099 | |
| 2100 fieldValues.forEach((element, values) { | |
| 2101 var otherValues = other.fieldValues[element]; | |
| 2102 if (otherValues == null) return; | |
| 2103 values.forEach((receiver, value) { | |
| 2104 HInstruction instruction = findCommonInstruction( | |
| 2105 value, otherValues[receiver], block, predecessorIndex); | |
| 2106 if (instruction != null) { | |
| 2107 result.registerFieldValue(element, receiver, instruction); | |
| 2108 } | |
| 2109 }); | |
| 2110 }); | |
| 2111 | |
| 2112 keyedValues.forEach((receiver, values) { | |
| 2113 var otherValues = other.keyedValues[receiver]; | |
| 2114 if (otherValues == null) return; | |
| 2115 values.forEach((index, value) { | |
| 2116 HInstruction instruction = findCommonInstruction( | |
| 2117 value, otherValues[index], block, predecessorIndex); | |
| 2118 if (instruction != null) { | |
| 2119 result.registerKeyedValue(receiver, index, instruction); | |
| 2120 } | |
| 2121 }); | |
| 2122 }); | |
| 2123 | |
| 2124 nonEscapingReceivers.forEach((receiver) { | |
| 2125 if (other.nonEscapingReceivers.contains(receiver)) { | |
| 2126 result.nonEscapingReceivers.add(receiver); | |
| 2127 } | |
| 2128 }); | |
| 2129 return result; | |
| 2130 } | |
| 2131 | |
| 2132 /** | |
| 2133 * Returns a copy of [this]. | |
| 2134 */ | |
| 2135 MemorySet clone() { | |
| 2136 MemorySet result = new MemorySet(compiler); | |
| 2137 | |
| 2138 fieldValues.forEach((element, values) { | |
| 2139 result.fieldValues[element] = | |
| 2140 new Map<HInstruction, HInstruction>.from(values); | |
| 2141 }); | |
| 2142 | |
| 2143 keyedValues.forEach((receiver, values) { | |
| 2144 result.keyedValues[receiver] = | |
| 2145 new Map<HInstruction, HInstruction>.from(values); | |
| 2146 }); | |
| 2147 | |
| 2148 result.nonEscapingReceivers.addAll(nonEscapingReceivers); | |
| 2149 return result; | |
| 2150 } | |
| 2151 } | |
| 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