| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library dart2js.cps_ir.bounds_checker; | |
| 6 | |
| 7 import '../constants/values.dart'; | |
| 8 import '../types/types.dart'; | |
| 9 import '../world.dart'; | |
| 10 import 'cps_fragment.dart'; | |
| 11 import 'cps_ir_nodes.dart'; | |
| 12 import 'effects.dart'; | |
| 13 import 'loop_effects.dart'; | |
| 14 import 'octagon.dart'; | |
| 15 import 'optimizers.dart' show Pass; | |
| 16 import 'type_mask_system.dart'; | |
| 17 | |
| 18 /// Eliminates bounds checks when they can be proven safe. | |
| 19 /// | |
| 20 /// In general, this pass will try to eliminate any branch with arithmetic | |
| 21 /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc. | |
| 22 /// | |
| 23 /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon | |
| 24 /// analyzers, we do not use a closed matrix representation, but just maintain | |
| 25 /// a bucket of constraints. Constraints can therefore be added and removed | |
| 26 /// on-the-fly without significant overhead. | |
| 27 /// | |
| 28 /// We never copy the constraint system. While traversing the IR, the | |
| 29 /// constraint system is mutated to take into account the knowledge that is | |
| 30 /// valid for the current location. Constraints are added when entering a | |
| 31 /// branch, for instance, and removed again after the branch has been processed. | |
| 32 /// | |
| 33 /// Loops are analyzed in two passes. The first pass establishes monotonicity | |
| 34 /// of loop variables, which the second pass uses to compute upper/lower bounds. | |
| 35 /// | |
| 36 /// The two-pass scheme is suboptimal compared to a least fixed-point | |
| 37 /// computation, but does not require repeated iteration. Repeated iteration | |
| 38 /// would be expensive, since we cannot perform a sparse analysis with our | |
| 39 /// mutable octagon representation. | |
| 40 class BoundsChecker extends TrampolineRecursiveVisitor implements Pass { | |
| 41 String get passName => 'Bounds checker'; | |
| 42 | |
| 43 static const int MAX_UINT32 = (1 << 32) - 1; | |
| 44 | |
| 45 /// All integers of this magnitude or less are representable as JS numbers. | |
| 46 static const int MAX_SAFE_INT = (1 << 53) - 1; | |
| 47 | |
| 48 /// Marker to indicate that a continuation should get a unique effect number. | |
| 49 static const int NEW_EFFECT = -1; | |
| 50 | |
| 51 final TypeMaskSystem types; | |
| 52 final World world; | |
| 53 | |
| 54 /// Fields for the constraint system and its variables. | |
| 55 final Octagon octagon = new Octagon(); | |
| 56 final Map<Primitive, SignedVariable> valueOf = {}; | |
| 57 final Map<Primitive, Map<int, SignedVariable>> lengthOf = {}; | |
| 58 | |
| 59 /// Fields for the two-pass handling of loops. | |
| 60 final Map<Parameter, Monotonicity> monotonicity = <Parameter, Monotonicity>{}; | |
| 61 bool isStrongLoopPass; | |
| 62 bool foundLoop = false; | |
| 63 | |
| 64 /// Fields for tracking side effects. | |
| 65 /// | |
| 66 /// The IR is divided into regions wherein the lengths of indexable objects | |
| 67 /// are known not to change. Regions are identified by their "effect number". | |
| 68 LoopSideEffects loopEffects; | |
| 69 final Map<Continuation, int> effectNumberAt = <Continuation, int>{}; | |
| 70 int currentEffectNumber = 0; | |
| 71 int effectNumberCounter = 0; | |
| 72 | |
| 73 BoundsChecker(this.types, this.world); | |
| 74 | |
| 75 void rewrite(FunctionDefinition node) { | |
| 76 loopEffects = new LoopSideEffects(node, world); | |
| 77 isStrongLoopPass = false; | |
| 78 visit(node); | |
| 79 if (foundLoop) { | |
| 80 isStrongLoopPass = true; | |
| 81 effectNumberAt.clear(); | |
| 82 visit(node); | |
| 83 } | |
| 84 } | |
| 85 | |
| 86 // ------------- VARIABLES ----------------- | |
| 87 | |
| 88 int makeNewEffect() => ++effectNumberCounter; | |
| 89 | |
| 90 bool isInt(Primitive prim) { | |
| 91 return types.isDefinitelyInt(prim.type); | |
| 92 } | |
| 93 | |
| 94 bool isUInt32(Primitive prim) { | |
| 95 return types.isDefinitelyUint32(prim.type); | |
| 96 } | |
| 97 | |
| 98 bool isNonNegativeInt(Primitive prim) { | |
| 99 return types.isDefinitelyNonNegativeInt(prim.type); | |
| 100 } | |
| 101 | |
| 102 /// Get a constraint variable representing the numeric value of [number]. | |
| 103 SignedVariable getValue(Primitive number) { | |
| 104 number = number.effectiveDefinition; | |
| 105 int min, max; | |
| 106 if (isUInt32(number)) { | |
| 107 min = 0; | |
| 108 max = MAX_UINT32; | |
| 109 } else if (isNonNegativeInt(number)) { | |
| 110 min = 0; | |
| 111 } | |
| 112 return valueOf.putIfAbsent(number, () => octagon.makeVariable(min, max)); | |
| 113 } | |
| 114 | |
| 115 /// Get a constraint variable representing the length of [indexableObject] at | |
| 116 /// program locations with the given [effectNumber]. | |
| 117 SignedVariable getLength(Primitive indexableObject, int effectNumber) { | |
| 118 indexableObject = indexableObject.effectiveDefinition; | |
| 119 TypeMask type = indexableObject.type.nonNullable(); | |
| 120 if (types.isDefinitelyFixedLengthIndexable(type)) { | |
| 121 // Always use the same effect number if the length is immutable. | |
| 122 effectNumber = 0; | |
| 123 } | |
| 124 return lengthOf | |
| 125 .putIfAbsent(indexableObject, () => <int, SignedVariable>{}) | |
| 126 .putIfAbsent(effectNumber, () { | |
| 127 int length = types.getContainerLength(type); | |
| 128 if (length != null) { | |
| 129 return octagon.makeVariable(length, length); | |
| 130 } else { | |
| 131 return octagon.makeVariable(0, MAX_UINT32); | |
| 132 } | |
| 133 }); | |
| 134 } | |
| 135 | |
| 136 // ------------- CONSTRAINT HELPERS ----------------- | |
| 137 | |
| 138 /// Puts the given constraint "in scope" by adding it to the octagon, and | |
| 139 /// pushing a stack action that will remove it again. | |
| 140 void applyConstraint(SignedVariable v1, SignedVariable v2, int k) { | |
| 141 Constraint constraint = new Constraint(v1, v2, k); | |
| 142 octagon.pushConstraint(constraint); | |
| 143 pushAction(() => octagon.popConstraint(constraint)); | |
| 144 } | |
| 145 | |
| 146 /// Return true if we can prove that `v1 + v2 <= k`. | |
| 147 bool testConstraint(SignedVariable v1, SignedVariable v2, int k) { | |
| 148 // Add the negated constraint and check for solvability. | |
| 149 // !(v1 + v2 <= k) <==> -v1 - v2 <= -k-1 | |
| 150 Constraint constraint = new Constraint(v1.negated, v2.negated, -k - 1); | |
| 151 octagon.pushConstraint(constraint); | |
| 152 bool answer = octagon.isUnsolvable; | |
| 153 octagon.popConstraint(constraint); | |
| 154 return answer; | |
| 155 } | |
| 156 | |
| 157 void makeLessThanOrEqual(SignedVariable v1, SignedVariable v2) { | |
| 158 // v1 <= v2 <==> v1 - v2 <= 0 | |
| 159 applyConstraint(v1, v2.negated, 0); | |
| 160 } | |
| 161 | |
| 162 void makeLessThan(SignedVariable v1, SignedVariable v2) { | |
| 163 // v1 < v2 <==> v1 - v2 <= -1 | |
| 164 applyConstraint(v1, v2.negated, -1); | |
| 165 } | |
| 166 | |
| 167 void makeGreaterThanOrEqual(SignedVariable v1, SignedVariable v2) { | |
| 168 // v1 >= v2 <==> v2 - v1 <= 0 | |
| 169 applyConstraint(v2, v1.negated, 0); | |
| 170 } | |
| 171 | |
| 172 void makeGreaterThan(SignedVariable v1, SignedVariable v2) { | |
| 173 // v1 > v2 <==> v2 - v1 <= -1 | |
| 174 applyConstraint(v2, v1.negated, -1); | |
| 175 } | |
| 176 | |
| 177 void makeLessThanOrEqualToConstant(SignedVariable v1, int k) { | |
| 178 // v1 + v1 <= 2k | |
| 179 applyConstraint(v1, v1, 2 * k); | |
| 180 } | |
| 181 | |
| 182 void makeGreaterThanOrEqualToConstant(SignedVariable v1, int k) { | |
| 183 // -v1 - v1 <= -2k | |
| 184 applyConstraint(v1.negated, v1.negated, -2 * k); | |
| 185 } | |
| 186 | |
| 187 void makeConstant(SignedVariable v1, int k) { | |
| 188 // We model this using the constraints: | |
| 189 // v1 + v1 <= 2k | |
| 190 // -v1 - v1 <= -2k | |
| 191 applyConstraint(v1, v1, 2 * k); | |
| 192 applyConstraint(v1.negated, v1.negated, -2 * k); | |
| 193 } | |
| 194 | |
| 195 /// Make `v1 = v2 + k`. | |
| 196 void makeExactSum(SignedVariable v1, SignedVariable v2, int k) { | |
| 197 applyConstraint(v1, v2.negated, k); | |
| 198 applyConstraint(v1.negated, v2, -k); | |
| 199 } | |
| 200 | |
| 201 /// Make `v1 = v2 [+] k` where [+] represents floating-point addition. | |
| 202 void makeFloatingPointSum(SignedVariable v1, SignedVariable v2, int k) { | |
| 203 if (isDefinitelyLessThanOrEqualToConstant(v2, MAX_SAFE_INT - k) && | |
| 204 isDefinitelyGreaterThanOrEqualToConstant(v2, -MAX_SAFE_INT + k)) { | |
| 205 // The result is known to be in the 53-bit range, so no rounding occurs. | |
| 206 makeExactSum(v1, v2, k); | |
| 207 } else { | |
| 208 // A rounding error may occur, so the result may not be exactly v2 + k. | |
| 209 // We can still add monotonicity constraints: | |
| 210 // adding a positive number cannot return a lesser number | |
| 211 // adding a negative number cannot return a greater number | |
| 212 if (k >= 0) { | |
| 213 // v1 >= v2 <==> v2 - v1 <= 0 <==> -v1 + v2 <= 0 | |
| 214 applyConstraint(v1.negated, v2, 0); | |
| 215 } else { | |
| 216 // v1 <= v2 <==> v1 - v2 <= 0 | |
| 217 applyConstraint(v1, v2.negated, 0); | |
| 218 } | |
| 219 } | |
| 220 } | |
| 221 | |
| 222 void makeEqual(SignedVariable v1, SignedVariable v2) { | |
| 223 // We model this using the constraints: | |
| 224 // v1 <= v2 <==> v1 - v2 <= 0 | |
| 225 // v1 >= v2 <==> v2 - v1 <= 0 | |
| 226 applyConstraint(v1, v2.negated, 0); | |
| 227 applyConstraint(v2, v1.negated, 0); | |
| 228 } | |
| 229 | |
| 230 void makeNotEqual(SignedVariable v1, SignedVariable v2) { | |
| 231 // The octagon cannot represent non-equality, but we can sharpen a weak | |
| 232 // inequality to a sharp one. If v1 and v2 are already known to be equal, | |
| 233 // this will create a contradiction and eliminate a dead branch. | |
| 234 // This is necessary for eliminating concurrent modification checks. | |
| 235 if (isDefinitelyLessThanOrEqualTo(v1, v2)) { | |
| 236 makeLessThan(v1, v2); | |
| 237 } else if (isDefinitelyGreaterThanOrEqualTo(v1, v2)) { | |
| 238 makeGreaterThan(v1, v2); | |
| 239 } | |
| 240 } | |
| 241 | |
| 242 /// Return true if we can prove that `v1 <= v2`. | |
| 243 bool isDefinitelyLessThanOrEqualTo(SignedVariable v1, SignedVariable v2) { | |
| 244 return testConstraint(v1, v2.negated, 0); | |
| 245 } | |
| 246 | |
| 247 /// Return true if we can prove that `v1 < v2`. | |
| 248 bool isDefinitelyLessThan(SignedVariable v1, SignedVariable v2) { | |
| 249 return testConstraint(v1, v2.negated, -1); | |
| 250 } | |
| 251 | |
| 252 /// Return true if we can prove that `v1 >= v2`. | |
| 253 bool isDefinitelyGreaterThanOrEqualTo(SignedVariable v1, SignedVariable v2) { | |
| 254 return testConstraint(v2, v1.negated, 0); | |
| 255 } | |
| 256 | |
| 257 bool isDefinitelyLessThanOrEqualToConstant(SignedVariable v1, int value) { | |
| 258 // v1 <= value <==> v1 + v1 <= 2 * value | |
| 259 return testConstraint(v1, v1, 2 * value); | |
| 260 } | |
| 261 | |
| 262 bool isDefinitelyGreaterThanOrEqualToConstant(SignedVariable v1, int value) { | |
| 263 // v1 >= value <==> -v1 - v1 <= -2 * value | |
| 264 return testConstraint(v1.negated, v1.negated, -2 * value); | |
| 265 } | |
| 266 | |
| 267 // ------------- TAIL EXPRESSIONS ----------------- | |
| 268 | |
| 269 @override | |
| 270 void visitBranch(Branch node) { | |
| 271 Primitive condition = node.condition; | |
| 272 Continuation trueCont = node.trueContinuation; | |
| 273 Continuation falseCont = node.falseContinuation; | |
| 274 effectNumberAt[trueCont] = currentEffectNumber; | |
| 275 effectNumberAt[falseCont] = currentEffectNumber; | |
| 276 pushAction(() { | |
| 277 // If the branching condition is known statically, either or both of the | |
| 278 // branch continuations will be replaced by Unreachable. Clean up the | |
| 279 // branch afterwards. | |
| 280 if (trueCont.body is Unreachable && falseCont.body is Unreachable) { | |
| 281 destroyAndReplace(node, new Unreachable()); | |
| 282 } else if (trueCont.body is Unreachable) { | |
| 283 destroyAndReplace( | |
| 284 node, new InvokeContinuation(falseCont, <Parameter>[])); | |
| 285 } else if (falseCont.body is Unreachable) { | |
| 286 destroyAndReplace( | |
| 287 node, new InvokeContinuation(trueCont, <Parameter>[])); | |
| 288 } | |
| 289 }); | |
| 290 void pushTrue(makeConstraint()) { | |
| 291 pushAction(() { | |
| 292 makeConstraint(); | |
| 293 push(trueCont); | |
| 294 }); | |
| 295 } | |
| 296 | |
| 297 void pushFalse(makeConstraint()) { | |
| 298 pushAction(() { | |
| 299 makeConstraint(); | |
| 300 push(falseCont); | |
| 301 }); | |
| 302 } | |
| 303 | |
| 304 if (condition is ApplyBuiltinOperator && | |
| 305 condition.argumentRefs.length == 2 && | |
| 306 isInt(condition.argument(0)) && | |
| 307 isInt(condition.argument(1))) { | |
| 308 SignedVariable v1 = getValue(condition.argument(0)); | |
| 309 SignedVariable v2 = getValue(condition.argument(1)); | |
| 310 switch (condition.operator) { | |
| 311 case BuiltinOperator.NumLe: | |
| 312 pushTrue(() => makeLessThanOrEqual(v1, v2)); | |
| 313 pushFalse(() => makeGreaterThan(v1, v2)); | |
| 314 return; | |
| 315 case BuiltinOperator.NumLt: | |
| 316 pushTrue(() => makeLessThan(v1, v2)); | |
| 317 pushFalse(() => makeGreaterThanOrEqual(v1, v2)); | |
| 318 return; | |
| 319 case BuiltinOperator.NumGe: | |
| 320 pushTrue(() => makeGreaterThanOrEqual(v1, v2)); | |
| 321 pushFalse(() => makeLessThan(v1, v2)); | |
| 322 return; | |
| 323 case BuiltinOperator.NumGt: | |
| 324 pushTrue(() => makeGreaterThan(v1, v2)); | |
| 325 pushFalse(() => makeLessThanOrEqual(v1, v2)); | |
| 326 return; | |
| 327 case BuiltinOperator.StrictEq: | |
| 328 pushTrue(() => makeEqual(v1, v2)); | |
| 329 pushFalse(() => makeNotEqual(v1, v2)); | |
| 330 return; | |
| 331 case BuiltinOperator.StrictNeq: | |
| 332 pushTrue(() => makeNotEqual(v1, v2)); | |
| 333 pushFalse(() => makeEqual(v1, v2)); | |
| 334 return; | |
| 335 default: | |
| 336 } | |
| 337 } | |
| 338 | |
| 339 push(trueCont); | |
| 340 push(falseCont); | |
| 341 } | |
| 342 | |
| 343 @override | |
| 344 void visitConstant(Constant node) { | |
| 345 // TODO(asgerf): It might be faster to inline the constant in the | |
| 346 // constraints that reference it. | |
| 347 if (node.value.isInt) { | |
| 348 IntConstantValue constant = node.value; | |
| 349 makeConstant(getValue(node), constant.primitiveValue); | |
| 350 } | |
| 351 } | |
| 352 | |
| 353 @override | |
| 354 void visitApplyBuiltinOperator(ApplyBuiltinOperator node) { | |
| 355 if (!isInt(node)) return; | |
| 356 if (node.argumentRefs.length == 1) { | |
| 357 applyUnaryOperator(node); | |
| 358 } else if (node.argumentRefs.length == 2) { | |
| 359 applyBinaryOperator(node); | |
| 360 } | |
| 361 } | |
| 362 | |
| 363 void applyBinaryOperator(ApplyBuiltinOperator node) { | |
| 364 Primitive left = node.argument(0); | |
| 365 Primitive right = node.argument(1); | |
| 366 if (!isInt(left) || !isInt(right)) { | |
| 367 return; | |
| 368 } | |
| 369 SignedVariable leftVar = getValue(left); | |
| 370 SignedVariable rightVar = getValue(right); | |
| 371 SignedVariable result = getValue(node); | |
| 372 switch (node.operator) { | |
| 373 case BuiltinOperator.NumAdd: | |
| 374 int leftConst = getIntConstant(left); | |
| 375 if (leftConst != null) { | |
| 376 makeFloatingPointSum(result, rightVar, leftConst); | |
| 377 } | |
| 378 int rightConst = getIntConstant(right); | |
| 379 if (rightConst != null) { | |
| 380 makeFloatingPointSum(result, leftVar, rightConst); | |
| 381 } | |
| 382 // Attempt to compute the sign of the result. | |
| 383 // TODO(asgerf): Compute upper/lower bounds instead of using 0. | |
| 384 if (testConstraint(leftVar, rightVar, 0)) { | |
| 385 makeLessThanOrEqualToConstant(result, 0); | |
| 386 } | |
| 387 if (testConstraint(leftVar.negated, rightVar.negated, 0)) { | |
| 388 makeGreaterThanOrEqualToConstant(result, 0); | |
| 389 } | |
| 390 // Classical octagon-based analyzers would compute upper and lower | |
| 391 // bounds for the two operands and add constraints for the result based | |
| 392 // on those. For performance reasons we only compute the sign | |
| 393 // TODO(asgerf): It seems expensive, but we should evaluate it. | |
| 394 break; | |
| 395 | |
| 396 case BuiltinOperator.NumSubtract: | |
| 397 int leftConst = getIntConstant(left); | |
| 398 if (leftConst != null) { | |
| 399 // result = leftConst - right = (-right) + leftConst | |
| 400 makeFloatingPointSum(result, rightVar.negated, leftConst); | |
| 401 } | |
| 402 int rightConst = getIntConstant(right); | |
| 403 if (rightConst != null) { | |
| 404 // result = left - rightConst = left + (-rightConst) | |
| 405 makeFloatingPointSum(result, leftVar, -rightConst); | |
| 406 } | |
| 407 // Attempt to compute the sign of the result. | |
| 408 if (isDefinitelyGreaterThanOrEqualTo(leftVar, rightVar)) { | |
| 409 makeGreaterThanOrEqualToConstant(result, 0); | |
| 410 } | |
| 411 if (isDefinitelyLessThanOrEqualTo(leftVar, rightVar)) { | |
| 412 makeLessThanOrEqualToConstant(result, 0); | |
| 413 } | |
| 414 break; | |
| 415 | |
| 416 case BuiltinOperator.NumTruncatingDivideToSigned32: | |
| 417 if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) { | |
| 418 // If we divide by a positive number, the result is closer to zero. | |
| 419 // If we divide by a negative number, the result is negative, and | |
| 420 // thus less than the original (non-negative) number. | |
| 421 // TODO(asgerf): The divisor is currently always positive, because | |
| 422 // type propagation checks that, but we could do better. | |
| 423 makeLessThanOrEqual(result, leftVar); | |
| 424 } | |
| 425 break; | |
| 426 | |
| 427 case BuiltinOperator.NumShr: | |
| 428 if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0)) { | |
| 429 makeLessThanOrEqual(result, leftVar); | |
| 430 } | |
| 431 int shiftAmount = getIntConstant(right); | |
| 432 if (shiftAmount != null) { | |
| 433 // TODO(asgerf): Compute upper bound on [leftVar] and use that | |
| 434 // instead of MAX_UINT32. | |
| 435 makeLessThanOrEqualToConstant(result, MAX_UINT32 >> shiftAmount); | |
| 436 } | |
| 437 break; | |
| 438 | |
| 439 case BuiltinOperator.NumRemainder: | |
| 440 // TODO(asgerf): This check overlaps with checks performed in a type | |
| 441 // propagation transformation, and we can do it more precisely here. | |
| 442 // Should we do the rewrite here? | |
| 443 if (isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) && | |
| 444 isDefinitelyGreaterThanOrEqualToConstant(rightVar, 1)) { | |
| 445 makeLessThanOrEqual(result, leftVar); | |
| 446 makeLessThan(result, rightVar); | |
| 447 } | |
| 448 break; | |
| 449 | |
| 450 case BuiltinOperator.NumAnd: | |
| 451 // We use the faster UInt32 check instead of constraint based checks | |
| 452 // here, because the common case is that one operand is a constant. | |
| 453 if (isUInt32(left)) { | |
| 454 makeLessThanOrEqual(result, leftVar); | |
| 455 } | |
| 456 if (isUInt32(right)) { | |
| 457 makeLessThanOrEqual(result, rightVar); | |
| 458 } | |
| 459 break; | |
| 460 | |
| 461 default: | |
| 462 } | |
| 463 } | |
| 464 | |
| 465 void applyUnaryOperator(ApplyBuiltinOperator node) { | |
| 466 Primitive argument = node.argument(0); | |
| 467 if (!isInt(argument)) return; | |
| 468 if (node.operator == BuiltinOperator.NumNegate) { | |
| 469 valueOf[node] = getValue(argument).negated; | |
| 470 } | |
| 471 } | |
| 472 | |
| 473 int getIntConstant(Primitive prim) { | |
| 474 if (prim is Constant && prim.value.isInt) { | |
| 475 IntConstantValue constant = prim.value; | |
| 476 return constant.primitiveValue; | |
| 477 } | |
| 478 return null; | |
| 479 } | |
| 480 | |
| 481 @override | |
| 482 void visitRefinement(Refinement node) { | |
| 483 // In general we should get the container length of the refined type and | |
| 484 // add a constraint if we know the length after the refinement. | |
| 485 // However, our current type system removes container information when a | |
| 486 // type becomes part of a union, so this cannot happen. | |
| 487 } | |
| 488 | |
| 489 @override | |
| 490 void visitGetLength(GetLength node) { | |
| 491 valueOf[node] = getLength(node.object, currentEffectNumber); | |
| 492 } | |
| 493 | |
| 494 @override | |
| 495 void visitBoundsCheck(BoundsCheck node) { | |
| 496 if (node.checks == BoundsCheck.NONE) return; | |
| 497 assert(node.indexRef != null); // Because there is at least one check. | |
| 498 SignedVariable length = | |
| 499 node.lengthRef == null ? null : getValue(node.length); | |
| 500 SignedVariable index = getValue(node.index); | |
| 501 if (node.hasUpperBoundCheck) { | |
| 502 if (isDefinitelyLessThan(index, length)) { | |
| 503 node.checks &= ~BoundsCheck.UPPER_BOUND; | |
| 504 } else { | |
| 505 makeLessThan(index, length); | |
| 506 } | |
| 507 } | |
| 508 if (node.hasLowerBoundCheck) { | |
| 509 if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) { | |
| 510 node.checks &= ~BoundsCheck.LOWER_BOUND; | |
| 511 } else { | |
| 512 makeGreaterThanOrEqualToConstant(index, 0); | |
| 513 } | |
| 514 } | |
| 515 if (node.hasEmptinessCheck) { | |
| 516 if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) { | |
| 517 node.checks &= ~BoundsCheck.EMPTINESS; | |
| 518 } else { | |
| 519 makeGreaterThanOrEqualToConstant(length, 1); | |
| 520 } | |
| 521 } | |
| 522 if (!node.lengthUsedInCheck && node.lengthRef != null) { | |
| 523 node | |
| 524 ..lengthRef.unlink() | |
| 525 ..lengthRef = null; | |
| 526 } | |
| 527 if (node.checks == BoundsCheck.NONE) { | |
| 528 // We can't remove the bounds check node because it may still be used to | |
| 529 // restrict code motion. But the index is no longer needed. | |
| 530 node | |
| 531 ..indexRef.unlink() | |
| 532 ..indexRef = null; | |
| 533 } | |
| 534 } | |
| 535 | |
| 536 void analyzeLoopEntry(InvokeContinuation node) { | |
| 537 foundLoop = true; | |
| 538 Continuation cont = node.continuation; | |
| 539 if (isStrongLoopPass) { | |
| 540 for (int i = 0; i < node.argumentRefs.length; ++i) { | |
| 541 Parameter param = cont.parameters[i]; | |
| 542 if (!isInt(param)) continue; | |
| 543 Primitive initialValue = node.argument(i); | |
| 544 SignedVariable initialVariable = getValue(initialValue); | |
| 545 Monotonicity mono = monotonicity[param]; | |
| 546 if (mono == null) { | |
| 547 // Value never changes. This is extremely uncommon. | |
| 548 param.replaceUsesWith(initialValue); | |
| 549 } else if (mono == Monotonicity.Increasing) { | |
| 550 makeGreaterThanOrEqual(getValue(param), initialVariable); | |
| 551 } else if (mono == Monotonicity.Decreasing) { | |
| 552 makeLessThanOrEqual(getValue(param), initialVariable); | |
| 553 } | |
| 554 } | |
| 555 } | |
| 556 if (loopEffects.changesIndexableLength(cont)) { | |
| 557 currentEffectNumber = effectNumberAt[cont] = makeNewEffect(); | |
| 558 } | |
| 559 push(cont); | |
| 560 } | |
| 561 | |
| 562 void analyzeLoopContinue(InvokeContinuation node) { | |
| 563 Continuation cont = node.continuation; | |
| 564 | |
| 565 // During the strong loop phase, there is no need to compute monotonicity, | |
| 566 // and we already put bounds on the loop variables when we went into the | |
| 567 // loop. | |
| 568 if (isStrongLoopPass) return; | |
| 569 | |
| 570 // For each loop parameter, try to prove that the new value is definitely | |
| 571 // less/greater than its old value. When we fail to prove this, update the | |
| 572 // monotonicity flag accordingly. | |
| 573 for (int i = 0; i < node.argumentRefs.length; ++i) { | |
| 574 Parameter param = cont.parameters[i]; | |
| 575 if (!isInt(param)) continue; | |
| 576 SignedVariable arg = getValue(node.argument(i)); | |
| 577 SignedVariable paramVar = getValue(param); | |
| 578 if (!isDefinitelyLessThanOrEqualTo(arg, paramVar)) { | |
| 579 // We couldn't prove that the value does not increase, so assume | |
| 580 // henceforth that it might be increasing. | |
| 581 markMonotonicity(cont.parameters[i], Monotonicity.Increasing); | |
| 582 } | |
| 583 if (!isDefinitelyGreaterThanOrEqualTo(arg, paramVar)) { | |
| 584 // We couldn't prove that the value does not decrease, so assume | |
| 585 // henceforth that it might be decreasing. | |
| 586 markMonotonicity(cont.parameters[i], Monotonicity.Decreasing); | |
| 587 } | |
| 588 } | |
| 589 } | |
| 590 | |
| 591 void markMonotonicity(Parameter param, Monotonicity mono) { | |
| 592 Monotonicity current = monotonicity[param]; | |
| 593 if (current == null) { | |
| 594 monotonicity[param] = mono; | |
| 595 } else if (current != mono) { | |
| 596 monotonicity[param] = Monotonicity.NotMonotone; | |
| 597 } | |
| 598 } | |
| 599 | |
| 600 @override | |
| 601 void visitInvokeContinuation(InvokeContinuation node) { | |
| 602 Continuation cont = node.continuation; | |
| 603 if (node.isRecursive) { | |
| 604 analyzeLoopContinue(node); | |
| 605 } else if (cont.isRecursive) { | |
| 606 analyzeLoopEntry(node); | |
| 607 } else { | |
| 608 int effect = effectNumberAt[cont]; | |
| 609 if (effect == null) { | |
| 610 effectNumberAt[cont] = currentEffectNumber; | |
| 611 } else if (effect != currentEffectNumber && effect != NEW_EFFECT) { | |
| 612 effectNumberAt[cont] = NEW_EFFECT; | |
| 613 } | |
| 614 // TODO(asgerf): Compute join for parameters to increase precision? | |
| 615 } | |
| 616 } | |
| 617 | |
| 618 // ---------------- PRIMITIVES -------------------- | |
| 619 | |
| 620 @override | |
| 621 Expression traverseLetPrim(LetPrim node) { | |
| 622 visit(node.primitive); | |
| 623 // visitApplyBuiltinMethod updates the effect number. | |
| 624 if (node.primitive is! ApplyBuiltinMethod) { | |
| 625 if (node.primitive.effects & Effects.changesIndexableLength != 0) { | |
| 626 currentEffectNumber = makeNewEffect(); | |
| 627 } | |
| 628 } | |
| 629 return node.body; | |
| 630 } | |
| 631 | |
| 632 @override | |
| 633 void visitInvokeMethod(InvokeMethod node) { | |
| 634 if (node.selector.isGetter && node.selector.name == 'length') { | |
| 635 // If the receiver type is not known to be indexable, the length call | |
| 636 // was not rewritten to GetLength. But if we can prove that the call only | |
| 637 // succeeds for indexables, we can trust that it returns the length. | |
| 638 TypeMask successType = | |
| 639 types.receiverTypeFor(node.selector, node.receiver.type); | |
| 640 if (types.isDefinitelyIndexable(successType)) { | |
| 641 valueOf[node] = getLength(node.receiver, currentEffectNumber); | |
| 642 } | |
| 643 } | |
| 644 } | |
| 645 | |
| 646 @override | |
| 647 void visitApplyBuiltinMethod(ApplyBuiltinMethod node) { | |
| 648 Primitive receiver = node.receiver; | |
| 649 int effectBefore = currentEffectNumber; | |
| 650 currentEffectNumber = makeNewEffect(); | |
| 651 int effectAfter = currentEffectNumber; | |
| 652 SignedVariable lengthBefore = getLength(receiver, effectBefore); | |
| 653 SignedVariable lengthAfter = getLength(receiver, effectAfter); | |
| 654 switch (node.method) { | |
| 655 case BuiltinMethod.Push: | |
| 656 // after = before + count | |
| 657 int count = node.argumentRefs.length; | |
| 658 makeExactSum(lengthAfter, lengthBefore, count); | |
| 659 break; | |
| 660 | |
| 661 case BuiltinMethod.Pop: | |
| 662 // after = before - 1 | |
| 663 makeExactSum(lengthAfter, lengthBefore, -1); | |
| 664 break; | |
| 665 | |
| 666 case BuiltinMethod.SetLength: | |
| 667 makeEqual(lengthAfter, getValue(node.argument(0))); | |
| 668 break; | |
| 669 } | |
| 670 } | |
| 671 | |
| 672 @override | |
| 673 void visitLiteralList(LiteralList node) { | |
| 674 makeConstant(getLength(node, currentEffectNumber), node.valueRefs.length); | |
| 675 } | |
| 676 | |
| 677 // ---------------- INTERIOR EXPRESSIONS -------------------- | |
| 678 | |
| 679 @override | |
| 680 Expression traverseContinuation(Continuation cont) { | |
| 681 if (octagon.isUnsolvable) { | |
| 682 destroyAndReplace(cont.body, new Unreachable()); | |
| 683 } else { | |
| 684 int effect = effectNumberAt[cont]; | |
| 685 if (effect != null) { | |
| 686 currentEffectNumber = effect == NEW_EFFECT ? makeNewEffect() : effect; | |
| 687 } | |
| 688 } | |
| 689 return cont.body; | |
| 690 } | |
| 691 | |
| 692 @override | |
| 693 Expression traverseLetCont(LetCont node) { | |
| 694 // Join continuations should be pushed at declaration-site, so all their | |
| 695 // call sites are seen before they are analyzed. | |
| 696 // Other continuations are pushed at the use site. | |
| 697 for (Continuation cont in node.continuations) { | |
| 698 if (cont.hasAtLeastOneUse && | |
| 699 !cont.isRecursive && | |
| 700 cont.firstRef.parent is InvokeContinuation) { | |
| 701 push(cont); | |
| 702 } | |
| 703 } | |
| 704 return node.body; | |
| 705 } | |
| 706 } | |
| 707 | |
| 708 /// Lattice representing the known (weak) monotonicity of a loop variable. | |
| 709 /// | |
| 710 /// The lattice bottom is represented by `null` and represents the case where | |
| 711 /// the loop variable never changes value during the loop. | |
| 712 enum Monotonicity { NotMonotone, Increasing, Decreasing, } | |
| OLD | NEW |
|---|
Chromium Code Reviews
