| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library cps_ir.optimization.insert_refinements; | |
| 6 | |
| 7 import 'dart:math' show min; | |
| 8 | |
| 9 import '../common/names.dart'; | |
| 10 import '../elements/elements.dart'; | |
| 11 import '../types/types.dart' show TypeMask; | |
| 12 import '../universe/selector.dart'; | |
| 13 import 'cps_ir_nodes.dart'; | |
| 14 import 'optimizers.dart' show Pass; | |
| 15 import 'type_mask_system.dart'; | |
| 16 | |
| 17 /// Inserts [Refinement] nodes in the IR to allow for sparse path-sensitive | |
| 18 /// type analysis in the [TypePropagator] pass. | |
| 19 /// | |
| 20 /// Refinement nodes are inserted at the arms of a [Branch] node with a | |
| 21 /// condition of form `x is T` or `x == null`. | |
| 22 /// | |
| 23 /// Refinement nodes are inserted after a method invocation to refine the | |
| 24 /// receiver to the types that can respond to the given selector. | |
| 25 class InsertRefinements extends TrampolineRecursiveVisitor implements Pass { | |
| 26 String get passName => 'Insert refinement nodes'; | |
| 27 | |
| 28 final TypeMaskSystem types; | |
| 29 | |
| 30 /// Maps unrefined primitives to its refinement currently in scope (if any). | |
| 31 final Map<Primitive, Refinement> refinementFor = <Primitive, Refinement>{}; | |
| 32 | |
| 33 InsertRefinements(this.types); | |
| 34 | |
| 35 void rewrite(FunctionDefinition node) { | |
| 36 visit(node.body); | |
| 37 } | |
| 38 | |
| 39 /// Updates references to refer to the refinement currently in scope. | |
| 40 void processReference(Reference node) { | |
| 41 Definition definition = node.definition; | |
| 42 if (definition is Primitive) { | |
| 43 Primitive prim = definition.effectiveDefinition; | |
| 44 Refinement refined = refinementFor[prim]; | |
| 45 if (refined != null && refined != definition) { | |
| 46 node.changeTo(refined); | |
| 47 } | |
| 48 } | |
| 49 } | |
| 50 | |
| 51 /// Sinks the binding of [cont] to immediately above [use]. | |
| 52 /// | |
| 53 /// This is used to ensure that everything in scope at [use] is also in scope | |
| 54 /// inside [cont], so refinements can be inserted inside [cont] without | |
| 55 /// accidentally referencing a primitive out of scope. | |
| 56 /// | |
| 57 /// It is always safe to do this for single-use continuations, because | |
| 58 /// strictly more things are in scope at the use site, and there can't be any | |
| 59 /// other use of [cont] that might fall out of scope since there is only | |
| 60 /// that single use. | |
| 61 void sinkContinuationToUse(Continuation cont, Expression use) { | |
| 62 assert(cont.hasExactlyOneUse && cont.firstRef.parent == use); | |
| 63 assert(!cont.isRecursive); | |
| 64 LetCont let = cont.parent; | |
| 65 InteriorNode useParent = use.parent; | |
| 66 if (useParent == let) return; | |
| 67 if (let.continuations.length > 1) { | |
| 68 // Create a new LetCont binding only this continuation. | |
| 69 let.continuations.remove(cont); | |
| 70 let = new LetCont(cont, null); | |
| 71 } else { | |
| 72 let.remove(); // Reuse the existing LetCont. | |
| 73 } | |
| 74 let.insertAbove(use); | |
| 75 } | |
| 76 | |
| 77 /// Sets [refined] to be the current refinement for its value, and pushes an | |
| 78 /// action that will restore the original scope again. | |
| 79 /// | |
| 80 /// The refinement is inserted as the child of [insertionParent] if it has | |
| 81 /// at least one use after its scope has been processed. | |
| 82 void applyRefinement(InteriorNode insertionParent, Refinement refined) { | |
| 83 Primitive value = refined.effectiveDefinition; | |
| 84 Primitive currentRefinement = refinementFor[value]; | |
| 85 refinementFor[value] = refined; | |
| 86 pushAction(() { | |
| 87 refinementFor[value] = currentRefinement; | |
| 88 if (refined.hasNoUses) { | |
| 89 // Clean up refinements that are not used. | |
| 90 refined.destroy(); | |
| 91 } else { | |
| 92 LetPrim let = new LetPrim(refined); | |
| 93 let.insertBelow(insertionParent); | |
| 94 } | |
| 95 }); | |
| 96 } | |
| 97 | |
| 98 /// Enqueues [cont] for processing in a context where [refined] is the | |
| 99 /// current refinement for its value. | |
| 100 void pushRefinement(Continuation cont, Refinement refined) { | |
| 101 pushAction(() { | |
| 102 applyRefinement(cont, refined); | |
| 103 push(cont); | |
| 104 }); | |
| 105 } | |
| 106 | |
| 107 /// Refine the type of each argument on [node] according to the provided | |
| 108 /// type masks. | |
| 109 void _refineArguments( | |
| 110 InvocationPrimitive node, List<TypeMask> argumentSuccessTypes) { | |
| 111 if (argumentSuccessTypes == null) return; | |
| 112 | |
| 113 // Note: node.dartArgumentsLength is shorter when the call doesn't include | |
| 114 // some optional arguments. | |
| 115 int length = min(argumentSuccessTypes.length, node.argumentRefs.length); | |
| 116 for (int i = 0; i < length; i++) { | |
| 117 TypeMask argSuccessType = argumentSuccessTypes[i]; | |
| 118 | |
| 119 // Skip arguments that provide no refinement. | |
| 120 if (argSuccessType == types.dynamicType) continue; | |
| 121 | |
| 122 applyRefinement( | |
| 123 node.parent, new Refinement(node.argument(i), argSuccessType)); | |
| 124 } | |
| 125 } | |
| 126 | |
| 127 void visitInvokeStatic(InvokeStatic node) { | |
| 128 node.argumentRefs.forEach(processReference); | |
| 129 _refineArguments(node, _getSuccessTypesForStaticMethod(types, node.target)); | |
| 130 } | |
| 131 | |
| 132 void visitInvokeMethod(InvokeMethod node) { | |
| 133 // Update references to their current refined values. | |
| 134 processReference(node.receiverRef); | |
| 135 node.argumentRefs.forEach(processReference); | |
| 136 | |
| 137 // If the call is intercepted, we want to refine the actual receiver, | |
| 138 // not the interceptor. | |
| 139 Primitive receiver = node.receiver; | |
| 140 | |
| 141 // Do not try to refine the receiver of closure calls; the class world | |
| 142 // does not know about closure classes. | |
| 143 Selector selector = node.selector; | |
| 144 if (!selector.isClosureCall) { | |
| 145 // Filter away receivers that throw on this selector. | |
| 146 TypeMask type = types.receiverTypeFor(selector, node.mask); | |
| 147 Refinement refinement = new Refinement(receiver, type); | |
| 148 LetPrim letPrim = node.parent; | |
| 149 applyRefinement(letPrim, refinement); | |
| 150 | |
| 151 // Refine arguments of methods on numbers which we know will throw on | |
| 152 // invalid argument values. | |
| 153 _refineArguments( | |
| 154 node, _getSuccessTypesForInstanceMethod(types, type, selector)); | |
| 155 } | |
| 156 } | |
| 157 | |
| 158 void visitTypeCast(TypeCast node) { | |
| 159 Primitive value = node.value; | |
| 160 | |
| 161 processReference(node.valueRef); | |
| 162 node.typeArgumentRefs.forEach(processReference); | |
| 163 | |
| 164 // Refine the type of the input. | |
| 165 TypeMask type = types.subtypesOf(node.dartType).nullable(); | |
| 166 Refinement refinement = new Refinement(value, type); | |
| 167 LetPrim letPrim = node.parent; | |
| 168 applyRefinement(letPrim, refinement); | |
| 169 } | |
| 170 | |
| 171 void visitRefinement(Refinement node) { | |
| 172 // We found a pre-existing refinement node. These are generated by the | |
| 173 // IR builder to hold information from --trust-type-annotations. | |
| 174 // Update its input to use our own current refinement, then update the | |
| 175 // environment to use this refinement. | |
| 176 processReference(node.value); | |
| 177 Primitive value = node.value.definition.effectiveDefinition; | |
| 178 Primitive oldRefinement = refinementFor[value]; | |
| 179 refinementFor[value] = node; | |
| 180 pushAction(() { | |
| 181 refinementFor[value] = oldRefinement; | |
| 182 }); | |
| 183 } | |
| 184 | |
| 185 bool isTrue(Primitive prim) { | |
| 186 return prim is Constant && prim.value.isTrue; | |
| 187 } | |
| 188 | |
| 189 void visitBranch(Branch node) { | |
| 190 processReference(node.conditionRef); | |
| 191 Primitive condition = node.condition; | |
| 192 | |
| 193 Continuation trueCont = node.trueContinuation; | |
| 194 Continuation falseCont = node.falseContinuation; | |
| 195 | |
| 196 // Sink both continuations to the Branch to ensure everything in scope | |
| 197 // here is also in scope inside the continuations. | |
| 198 sinkContinuationToUse(trueCont, node); | |
| 199 sinkContinuationToUse(falseCont, node); | |
| 200 | |
| 201 // If the condition is an 'is' check, promote the checked value. | |
| 202 if (condition is TypeTest) { | |
| 203 Primitive value = condition.value; | |
| 204 TypeMask type = types.subtypesOf(condition.dartType); | |
| 205 Primitive refinedValue = new Refinement(value, type); | |
| 206 pushRefinement(trueCont, refinedValue); | |
| 207 push(falseCont); | |
| 208 return; | |
| 209 } | |
| 210 | |
| 211 // If the condition is comparison with a constant, promote the other value. | |
| 212 // This can happen either for calls to `==` or `identical` calls, such | |
| 213 // as the ones inserted by the unsugaring pass. | |
| 214 | |
| 215 void refineEquality(Primitive first, Primitive second, | |
| 216 Continuation trueCont, Continuation falseCont) { | |
| 217 if (second is Constant && second.value.isNull) { | |
| 218 Refinement refinedTrue = new Refinement(first, types.nullType); | |
| 219 Refinement refinedFalse = new Refinement(first, types.nonNullType); | |
| 220 pushRefinement(trueCont, refinedTrue); | |
| 221 pushRefinement(falseCont, refinedFalse); | |
| 222 } else if (first is Constant && first.value.isNull) { | |
| 223 Refinement refinedTrue = new Refinement(second, types.nullType); | |
| 224 Refinement refinedFalse = new Refinement(second, types.nonNullType); | |
| 225 pushRefinement(trueCont, refinedTrue); | |
| 226 pushRefinement(falseCont, refinedFalse); | |
| 227 } else { | |
| 228 push(trueCont); | |
| 229 push(falseCont); | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 if (condition is InvokeMethod && condition.selector == Selectors.equals) { | |
| 234 refineEquality( | |
| 235 condition.receiver, condition.argument(0), trueCont, falseCont); | |
| 236 return; | |
| 237 } | |
| 238 | |
| 239 if (condition is ApplyBuiltinOperator && | |
| 240 condition.operator == BuiltinOperator.Identical) { | |
| 241 refineEquality( | |
| 242 condition.argument(0), condition.argument(1), trueCont, falseCont); | |
| 243 return; | |
| 244 } | |
| 245 | |
| 246 push(trueCont); | |
| 247 push(falseCont); | |
| 248 } | |
| 249 | |
| 250 @override | |
| 251 Expression traverseLetCont(LetCont node) { | |
| 252 for (Continuation cont in node.continuations) { | |
| 253 // Do not push the branch continuations here. visitBranch will do that. | |
| 254 if (!(cont.hasExactlyOneUse && cont.firstRef.parent is Branch)) { | |
| 255 push(cont); | |
| 256 } | |
| 257 } | |
| 258 return node.body; | |
| 259 } | |
| 260 } | |
| 261 | |
| 262 // TODO(sigmund): ideally this whitelist information should be stored as | |
| 263 // metadata annotations on the runtime libraries so we can keep it in sync with | |
| 264 // the implementation more easily. | |
| 265 // TODO(sigmund): add support for constructors. | |
| 266 // TODO(sigmund): add checks for RegExp and DateTime (currently not exposed as | |
| 267 // easily in TypeMaskSystem). | |
| 268 // TODO(sigmund): after the above TODOs are fixed, add: | |
| 269 // ctor JSArray.fixed: [types.uint32Type], | |
| 270 // ctor JSArray.growable: [types.uintType], | |
| 271 // ctor DateTime': [int, int, int, int, int, int, int], | |
| 272 // ctor DateTime.utc': [int, int, int, int, int, int, int], | |
| 273 // ctor DateTime._internal': [int, int, int, int, int, int, int, bool], | |
| 274 // ctor RegExp': [string, dynamic, dynamic], | |
| 275 // method RegExp.allMatches: [string, int], | |
| 276 // method RegExp.firstMatch: [string], | |
| 277 // method RegExp.hasMatch: [string], | |
| 278 List<TypeMask> _getSuccessTypesForInstanceMethod( | |
| 279 TypeMaskSystem types, TypeMask receiver, Selector selector) { | |
| 280 if (types.isDefinitelyInt(receiver)) { | |
| 281 switch (selector.name) { | |
| 282 case 'toSigned': | |
| 283 case 'toUnsigned': | |
| 284 case 'modInverse': | |
| 285 case 'gcd': | |
| 286 return [types.intType]; | |
| 287 | |
| 288 case 'modPow': | |
| 289 return [types.intType, types.intType]; | |
| 290 } | |
| 291 // Note: num methods on int values are handled below. | |
| 292 } | |
| 293 | |
| 294 if (types.isDefinitelyNum(receiver)) { | |
| 295 switch (selector.name) { | |
| 296 case 'clamp': | |
| 297 return [types.numType, types.numType]; | |
| 298 case 'toStringAsFixed': | |
| 299 case 'toStringAsPrecision': | |
| 300 case 'toRadixString': | |
| 301 return [types.intType]; | |
| 302 case 'toStringAsExponential': | |
| 303 return [types.intType.nullable()]; | |
| 304 case 'compareTo': | |
| 305 case 'remainder': | |
| 306 case '+': | |
| 307 case '-': | |
| 308 case '/': | |
| 309 case '*': | |
| 310 case '%': | |
| 311 case '~/': | |
| 312 case '<<': | |
| 313 case '>>': | |
| 314 case '&': | |
| 315 case '|': | |
| 316 case '^': | |
| 317 case '<': | |
| 318 case '>': | |
| 319 case '<=': | |
| 320 case '>=': | |
| 321 return [types.numType]; | |
| 322 default: | |
| 323 return null; | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 if (types.isDefinitelyString(receiver)) { | |
| 328 switch (selector.name) { | |
| 329 case 'allMatches': | |
| 330 return [types.stringType, types.intType]; | |
| 331 case 'endsWith': | |
| 332 return [types.stringType]; | |
| 333 case 'replaceAll': | |
| 334 return [types.dynamicType, types.stringType]; | |
| 335 case 'replaceFirst': | |
| 336 return [types.dynamicType, types.stringType, types.intType]; | |
| 337 case 'replaceFirstMapped': | |
| 338 return [ | |
| 339 types.dynamicType, | |
| 340 types.dynamicType.nonNullable(), | |
| 341 types.intType | |
| 342 ]; | |
| 343 case 'split': | |
| 344 return [types.dynamicType.nonNullable()]; | |
| 345 case 'replaceRange': | |
| 346 return [types.intType, types.intType, types.stringType]; | |
| 347 case 'startsWith': | |
| 348 return [types.dynamicType, types.intType]; | |
| 349 case 'substring': | |
| 350 return [types.intType, types.uintType.nullable()]; | |
| 351 case 'indexOf': | |
| 352 return [types.dynamicType.nonNullable(), types.uintType]; | |
| 353 case 'lastIndexOf': | |
| 354 return [types.dynamicType.nonNullable(), types.uintType.nullable()]; | |
| 355 case 'contains': | |
| 356 return [ | |
| 357 types.dynamicType.nonNullable(), | |
| 358 // TODO(sigmund): update runtime to add check for int? | |
| 359 types.dynamicType | |
| 360 ]; | |
| 361 case 'codeUnitAt': | |
| 362 return [types.uintType]; | |
| 363 case '+': | |
| 364 return [types.stringType]; | |
| 365 case '*': | |
| 366 return [types.uint32Type]; | |
| 367 case '[]': | |
| 368 return [types.uintType]; | |
| 369 default: | |
| 370 return null; | |
| 371 } | |
| 372 } | |
| 373 | |
| 374 if (types.isDefinitelyArray(receiver)) { | |
| 375 switch (selector.name) { | |
| 376 case 'removeAt': | |
| 377 case 'insert': | |
| 378 return [types.uintType]; | |
| 379 case 'sublist': | |
| 380 return [types.uintType, types.uintType.nullable()]; | |
| 381 case 'length': | |
| 382 return selector.isSetter ? [types.uintType] : null; | |
| 383 case '[]': | |
| 384 case '[]=': | |
| 385 return [types.uintType]; | |
| 386 default: | |
| 387 return null; | |
| 388 } | |
| 389 } | |
| 390 return null; | |
| 391 } | |
| 392 | |
| 393 List<TypeMask> _getSuccessTypesForStaticMethod( | |
| 394 TypeMaskSystem types, FunctionElement target) { | |
| 395 var lib = target.library; | |
| 396 if (lib.isDartCore) { | |
| 397 var cls = target.enclosingClass?.name; | |
| 398 if (cls == 'int' && target.name == 'parse') { | |
| 399 // source, onError, radix | |
| 400 return [types.stringType, types.dynamicType, types.uint31Type.nullable()]; | |
| 401 } else if (cls == 'double' && target.name == 'parse') { | |
| 402 return [types.stringType, types.dynamicType]; | |
| 403 } | |
| 404 } | |
| 405 | |
| 406 if (lib.isPlatformLibrary && '${lib.canonicalUri}' == 'dart:math') { | |
| 407 switch (target.name) { | |
| 408 case 'sqrt': | |
| 409 case 'sin': | |
| 410 case 'cos': | |
| 411 case 'tan': | |
| 412 case 'acos': | |
| 413 case 'asin': | |
| 414 case 'atan': | |
| 415 case 'atan2': | |
| 416 case 'exp': | |
| 417 case 'log': | |
| 418 return [types.numType]; | |
| 419 case 'pow': | |
| 420 return [types.numType, types.numType]; | |
| 421 } | |
| 422 } | |
| 423 | |
| 424 return null; | |
| 425 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
