| 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 class SsaTypePropagator extends HBaseVisitor implements OptimizationPhase { | |
| 8 final Map<int, HInstruction> workmap = new Map<int, HInstruction>(); | |
| 9 final List<int> worklist = new List<int>(); | |
| 10 final Map<HInstruction, Function> pendingOptimizations = | |
| 11 new Map<HInstruction, Function>(); | |
| 12 | |
| 13 final Compiler compiler; | |
| 14 final ClassWorld classWorld; | |
| 15 JavaScriptBackend get backend => compiler.backend; | |
| 16 String get name => 'type propagator'; | |
| 17 | |
| 18 SsaTypePropagator(Compiler compiler) | |
| 19 : this.compiler = compiler, | |
| 20 this.classWorld = compiler.world; | |
| 21 | |
| 22 TypeMask computeType(HInstruction instruction) { | |
| 23 return instruction.accept(this); | |
| 24 } | |
| 25 | |
| 26 // Re-compute and update the type of the instruction. Returns | |
| 27 // whether or not the type was changed. | |
| 28 bool updateType(HInstruction instruction) { | |
| 29 // Compute old and new types. | |
| 30 TypeMask oldType = instruction.instructionType; | |
| 31 TypeMask newType = computeType(instruction); | |
| 32 assert(newType != null); | |
| 33 // We unconditionally replace the propagated type with the new type. The | |
| 34 // computeType must make sure that we eventually reach a stable state. | |
| 35 instruction.instructionType = newType; | |
| 36 return oldType != newType; | |
| 37 } | |
| 38 | |
| 39 void visitGraph(HGraph graph) { | |
| 40 visitDominatorTree(graph); | |
| 41 processWorklist(); | |
| 42 } | |
| 43 | |
| 44 visitBasicBlock(HBasicBlock block) { | |
| 45 if (block.isLoopHeader()) { | |
| 46 block.forEachPhi((HPhi phi) { | |
| 47 // Set the initial type for the phi. We're not using the type | |
| 48 // the phi thinks it has because new optimizations may imply | |
| 49 // changing it. | |
| 50 // In theory we would need to mark | |
| 51 // the type of all other incoming edges as "unitialized" and take this | |
| 52 // into account when doing the propagation inside the phis. Just | |
| 53 // setting the propagated type is however easier. | |
| 54 phi.instructionType = phi.inputs[0].instructionType; | |
| 55 addToWorkList(phi); | |
| 56 }); | |
| 57 } else { | |
| 58 block.forEachPhi((HPhi phi) { | |
| 59 if (updateType(phi)) { | |
| 60 addDependentInstructionsToWorkList(phi); | |
| 61 } | |
| 62 }); | |
| 63 } | |
| 64 | |
| 65 HInstruction instruction = block.first; | |
| 66 while (instruction != null) { | |
| 67 if (updateType(instruction)) { | |
| 68 addDependentInstructionsToWorkList(instruction); | |
| 69 } | |
| 70 instruction = instruction.next; | |
| 71 } | |
| 72 } | |
| 73 | |
| 74 void processWorklist() { | |
| 75 do { | |
| 76 while (!worklist.isEmpty) { | |
| 77 int id = worklist.removeLast(); | |
| 78 HInstruction instruction = workmap[id]; | |
| 79 assert(instruction != null); | |
| 80 workmap.remove(id); | |
| 81 if (updateType(instruction)) { | |
| 82 addDependentInstructionsToWorkList(instruction); | |
| 83 } | |
| 84 } | |
| 85 // While processing the optimizable arithmetic instructions, we | |
| 86 // may discover better type information for dominated users of | |
| 87 // replaced operands, so we may need to take another stab at | |
| 88 // emptying the worklist afterwards. | |
| 89 processPendingOptimizations(); | |
| 90 } while (!worklist.isEmpty); | |
| 91 } | |
| 92 | |
| 93 | |
| 94 void addToWorkList(HInstruction instruction) { | |
| 95 final int id = instruction.id; | |
| 96 | |
| 97 if (!workmap.containsKey(id)) { | |
| 98 worklist.add(id); | |
| 99 workmap[id] = instruction; | |
| 100 } | |
| 101 } | |
| 102 | |
| 103 TypeMask visitBinaryArithmetic(HBinaryArithmetic instruction) { | |
| 104 HInstruction left = instruction.left; | |
| 105 HInstruction right = instruction.right; | |
| 106 if (left.isInteger(compiler) && right.isInteger(compiler)) { | |
| 107 return backend.intType; | |
| 108 } | |
| 109 if (left.isDouble(compiler)) return backend.doubleType; | |
| 110 return backend.numType; | |
| 111 } | |
| 112 | |
| 113 TypeMask checkPositiveInteger(HBinaryArithmetic instruction) { | |
| 114 HInstruction left = instruction.left; | |
| 115 HInstruction right = instruction.right; | |
| 116 if (left.isPositiveInteger(compiler) && right.isPositiveInteger(compiler)) { | |
| 117 return backend.positiveIntType; | |
| 118 } | |
| 119 return visitBinaryArithmetic(instruction); | |
| 120 } | |
| 121 | |
| 122 TypeMask visitMultiply(HMultiply instruction) { | |
| 123 return checkPositiveInteger(instruction); | |
| 124 } | |
| 125 | |
| 126 TypeMask visitAdd(HAdd instruction) { | |
| 127 return checkPositiveInteger(instruction); | |
| 128 } | |
| 129 | |
| 130 TypeMask visitNegate(HNegate instruction) { | |
| 131 HInstruction operand = instruction.operand; | |
| 132 // We have integer subclasses that represent ranges, so widen any int | |
| 133 // subclass to full integer. | |
| 134 if (operand.isInteger(compiler)) return backend.intType; | |
| 135 return instruction.operand.instructionType; | |
| 136 } | |
| 137 | |
| 138 TypeMask visitInstruction(HInstruction instruction) { | |
| 139 assert(instruction.instructionType != null); | |
| 140 return instruction.instructionType; | |
| 141 } | |
| 142 | |
| 143 TypeMask visitPhi(HPhi phi) { | |
| 144 TypeMask candidateType = backend.emptyType; | |
| 145 for (int i = 0, length = phi.inputs.length; i < length; i++) { | |
| 146 TypeMask inputType = phi.inputs[i].instructionType; | |
| 147 candidateType = candidateType.union(inputType, classWorld); | |
| 148 } | |
| 149 return candidateType; | |
| 150 } | |
| 151 | |
| 152 TypeMask visitTypeConversion(HTypeConversion instruction) { | |
| 153 HInstruction input = instruction.checkedInput; | |
| 154 TypeMask inputType = input.instructionType; | |
| 155 TypeMask checkedType = instruction.checkedType; | |
| 156 if (instruction.isArgumentTypeCheck || instruction.isReceiverTypeCheck) { | |
| 157 // We must make sure a type conversion for receiver or argument check | |
| 158 // does not try to do an int check, because an int check is not enough. | |
| 159 // We only do an int check if the input is integer or null. | |
| 160 if (checkedType.containsOnlyNum(classWorld) | |
| 161 && !checkedType.containsOnlyDouble(classWorld) | |
| 162 && input.isIntegerOrNull(compiler)) { | |
| 163 instruction.checkedType = backend.intType; | |
| 164 } else if (checkedType.containsOnlyInt(classWorld) | |
| 165 && !input.isIntegerOrNull(compiler)) { | |
| 166 instruction.checkedType = backend.numType; | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 TypeMask outputType = checkedType.intersection(inputType, classWorld); | |
| 171 if (outputType.isEmpty && !outputType.isNullable) { | |
| 172 // Intersection of double and integer conflicts (is empty), but JS numbers | |
| 173 // can be both int and double at the same time. For example, the input | |
| 174 // can be a literal double '8.0' that is marked as an integer (because 'is | |
| 175 // int' will return 'true'). What we really need to do is make the | |
| 176 // overlap between int and double values explicit in the TypeMask system. | |
| 177 if (inputType.containsOnlyInt(classWorld) | |
| 178 && checkedType.containsOnlyDouble(classWorld)) { | |
| 179 if (inputType.isNullable && checkedType.isNullable) { | |
| 180 outputType = backend.doubleType.nullable(); | |
| 181 } else { | |
| 182 outputType = backend.doubleType; | |
| 183 } | |
| 184 } | |
| 185 } | |
| 186 return outputType; | |
| 187 } | |
| 188 | |
| 189 TypeMask visitTypeKnown(HTypeKnown instruction) { | |
| 190 HInstruction input = instruction.checkedInput; | |
| 191 return instruction.knownType.intersection( | |
| 192 input.instructionType, classWorld); | |
| 193 } | |
| 194 | |
| 195 void convertInput(HInvokeDynamic instruction, | |
| 196 HInstruction input, | |
| 197 TypeMask type, | |
| 198 int kind) { | |
| 199 Selector selector = (kind == HTypeConversion.RECEIVER_TYPE_CHECK) | |
| 200 ? instruction.selector | |
| 201 : null; | |
| 202 HTypeConversion converted = new HTypeConversion( | |
| 203 null, kind, type, input, selector); | |
| 204 instruction.block.addBefore(instruction, converted); | |
| 205 input.replaceAllUsersDominatedBy(instruction, converted); | |
| 206 } | |
| 207 | |
| 208 bool isCheckEnoughForNsmOrAe(HInstruction instruction, | |
| 209 TypeMask type) { | |
| 210 // In some cases, we want the receiver to be an integer, | |
| 211 // but that does not mean we will get a NoSuchMethodError | |
| 212 // if it's not: the receiver could be a double. | |
| 213 if (type.containsOnlyInt(classWorld)) { | |
| 214 // If the instruction's type is integer or null, the codegen | |
| 215 // will emit a null check, which is enough to know if it will | |
| 216 // hit a noSuchMethod. | |
| 217 return instruction.isIntegerOrNull(compiler); | |
| 218 } | |
| 219 return true; | |
| 220 } | |
| 221 | |
| 222 // Add a receiver type check when the call can only hit | |
| 223 // [noSuchMethod] if the receiver is not of a specific type. | |
| 224 // Return true if the receiver type check was added. | |
| 225 bool checkReceiver(HInvokeDynamic instruction) { | |
| 226 assert(instruction.isInterceptedCall); | |
| 227 HInstruction receiver = instruction.inputs[1]; | |
| 228 if (receiver.isNumber(compiler)) return false; | |
| 229 if (receiver.isNumberOrNull(compiler)) { | |
| 230 convertInput(instruction, | |
| 231 receiver, | |
| 232 receiver.instructionType.nonNullable(), | |
| 233 HTypeConversion.RECEIVER_TYPE_CHECK); | |
| 234 return true; | |
| 235 } else if (instruction.element == null) { | |
| 236 Iterable<Element> targets = | |
| 237 compiler.world.allFunctions.filter(instruction.selector); | |
| 238 if (targets.length == 1) { | |
| 239 Element target = targets.first; | |
| 240 ClassElement cls = target.enclosingClass; | |
| 241 TypeMask type = new TypeMask.nonNullSubclass( | |
| 242 cls.declaration, classWorld); | |
| 243 // TODO(ngeoffray): We currently only optimize on primitive | |
| 244 // types. | |
| 245 if (!type.satisfies(backend.jsIndexableClass, classWorld) && | |
| 246 !type.containsOnlyNum(classWorld) && | |
| 247 !type.containsOnlyBool(classWorld)) { | |
| 248 return false; | |
| 249 } | |
| 250 if (!isCheckEnoughForNsmOrAe(receiver, type)) return false; | |
| 251 instruction.element = target; | |
| 252 convertInput(instruction, | |
| 253 receiver, | |
| 254 type, | |
| 255 HTypeConversion.RECEIVER_TYPE_CHECK); | |
| 256 return true; | |
| 257 } | |
| 258 } | |
| 259 return false; | |
| 260 } | |
| 261 | |
| 262 // Add an argument type check if the argument is not of a type | |
| 263 // expected by the call. | |
| 264 // Return true if the argument type check was added. | |
| 265 bool checkArgument(HInvokeDynamic instruction) { | |
| 266 // We want the right error in checked mode. | |
| 267 if (compiler.enableTypeAssertions) return false; | |
| 268 HInstruction left = instruction.inputs[1]; | |
| 269 HInstruction right = instruction.inputs[2]; | |
| 270 | |
| 271 Selector selector = instruction.selector; | |
| 272 if (selector.isOperator && left.isNumber(compiler)) { | |
| 273 if (right.isNumber(compiler)) return false; | |
| 274 TypeMask type = right.isIntegerOrNull(compiler) | |
| 275 ? right.instructionType.nonNullable() | |
| 276 : backend.numType; | |
| 277 // TODO(ngeoffray): Some number operations don't have a builtin | |
| 278 // variant and will do the check in their method anyway. We | |
| 279 // still add a check because it allows to GVN these operations, | |
| 280 // but we should find a better way. | |
| 281 convertInput(instruction, | |
| 282 right, | |
| 283 type, | |
| 284 HTypeConversion.ARGUMENT_TYPE_CHECK); | |
| 285 return true; | |
| 286 } | |
| 287 return false; | |
| 288 } | |
| 289 | |
| 290 void processPendingOptimizations() { | |
| 291 pendingOptimizations.forEach((instruction, action) => action()); | |
| 292 pendingOptimizations.clear(); | |
| 293 } | |
| 294 | |
| 295 void addDependentInstructionsToWorkList(HInstruction instruction) { | |
| 296 for (int i = 0, length = instruction.usedBy.length; i < length; i++) { | |
| 297 // The type propagator only propagates types forward. We | |
| 298 // thus only need to add the users of the [instruction] to the list. | |
| 299 addToWorkList(instruction.usedBy[i]); | |
| 300 } | |
| 301 } | |
| 302 | |
| 303 void addAllUsersBut(HInvokeDynamic invoke, HInstruction instruction) { | |
| 304 instruction.usedBy.forEach((HInstruction user) { | |
| 305 if (user != invoke) addToWorkList(user); | |
| 306 }); | |
| 307 } | |
| 308 | |
| 309 TypeMask visitInvokeDynamic(HInvokeDynamic instruction) { | |
| 310 if (instruction.isInterceptedCall) { | |
| 311 // We cannot do the following optimization now, because we have | |
| 312 // to wait for the type propagation to be stable. The receiver | |
| 313 // of [instruction] might move from number to dynamic. | |
| 314 pendingOptimizations.putIfAbsent(instruction, () => () { | |
| 315 Selector selector = instruction.selector; | |
| 316 if (selector.isOperator && selector.name != '==') { | |
| 317 if (checkReceiver(instruction)) { | |
| 318 addAllUsersBut(instruction, instruction.inputs[1]); | |
| 319 } | |
| 320 if (!selector.isUnaryOperator && checkArgument(instruction)) { | |
| 321 addAllUsersBut(instruction, instruction.inputs[2]); | |
| 322 } | |
| 323 } | |
| 324 }); | |
| 325 } | |
| 326 | |
| 327 HInstruction receiver = instruction.getDartReceiver(compiler); | |
| 328 TypeMask receiverType = receiver.instructionType; | |
| 329 Selector selector = | |
| 330 new TypedSelector(receiverType, instruction.selector, classWorld); | |
| 331 instruction.selector = selector; | |
| 332 | |
| 333 // Try to specialize the receiver after this call. | |
| 334 if (receiver.dominatedUsers(instruction).length != 1 | |
| 335 && !selector.isClosureCall) { | |
| 336 TypeMask newType = compiler.world.allFunctions.receiverType(selector); | |
| 337 newType = newType.intersection(receiverType, classWorld); | |
| 338 var next = instruction.next; | |
| 339 if (next is HTypeKnown && next.checkedInput == receiver) { | |
| 340 // We already have refined [receiver]. We still update the | |
| 341 // type of the [HTypeKnown] instruction because it may have | |
| 342 // been refined with a correct type at the time, but | |
| 343 // incorrect now. | |
| 344 if (next.instructionType != newType) { | |
| 345 next.knownType = next.instructionType = newType; | |
| 346 addDependentInstructionsToWorkList(next); | |
| 347 } | |
| 348 } else if (newType != receiverType) { | |
| 349 // Insert a refinement node after the call and update all | |
| 350 // users dominated by the call to use that node instead of | |
| 351 // [receiver]. | |
| 352 HTypeKnown converted = | |
| 353 new HTypeKnown.witnessed(newType, receiver, instruction); | |
| 354 instruction.block.addBefore(instruction.next, converted); | |
| 355 receiver.replaceAllUsersDominatedBy(converted.next, converted); | |
| 356 addDependentInstructionsToWorkList(converted); | |
| 357 } | |
| 358 } | |
| 359 | |
| 360 return instruction.specializer.computeTypeFromInputTypes( | |
| 361 instruction, compiler); | |
| 362 } | |
| 363 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 693183006:
Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart