| 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 | |
| 8 class ValueRangeInfo { | |
| 9 final ConstantSystem constantSystem; | |
| 10 | |
| 11 IntValue intZero; | |
| 12 IntValue intOne; | |
| 13 | |
| 14 ValueRangeInfo(this.constantSystem) { | |
| 15 intZero = newIntValue(0); | |
| 16 intOne = newIntValue(1); | |
| 17 } | |
| 18 | |
| 19 Value newIntValue(int value) { | |
| 20 return new IntValue(value, this); | |
| 21 } | |
| 22 | |
| 23 Value newInstructionValue(HInstruction instruction) { | |
| 24 return new InstructionValue(instruction, this); | |
| 25 } | |
| 26 | |
| 27 Value newPositiveValue(HInstruction instruction) { | |
| 28 return new PositiveValue(instruction, this); | |
| 29 } | |
| 30 | |
| 31 Value newAddValue(Value left, Value right) { | |
| 32 return new AddValue(left, right, this); | |
| 33 } | |
| 34 | |
| 35 Value newSubtractValue(Value left, Value right) { | |
| 36 return new SubtractValue(left, right, this); | |
| 37 } | |
| 38 | |
| 39 Value newNegateValue(Value value) { | |
| 40 return new NegateValue(value, this); | |
| 41 } | |
| 42 | |
| 43 Range newUnboundRange() { | |
| 44 return new Range.unbound(this); | |
| 45 } | |
| 46 | |
| 47 Range newNormalizedRange(Value low, Value up) { | |
| 48 return new Range.normalize(low, up, this); | |
| 49 } | |
| 50 | |
| 51 Range newMarkerRange() { | |
| 52 return new Range(new MarkerValue(false, this), | |
| 53 new MarkerValue(true, this), | |
| 54 this); | |
| 55 } | |
| 56 } | |
| 57 | |
| 58 /** | |
| 59 * A [Value] represents both symbolic values like the value of a | |
| 60 * parameter, or the length of an array, and concrete values, like | |
| 61 * constants. | |
| 62 */ | |
| 63 abstract class Value { | |
| 64 final ValueRangeInfo info; | |
| 65 const Value(this.info); | |
| 66 | |
| 67 Value operator +(Value other) => const UnknownValue(); | |
| 68 Value operator -(Value other) => const UnknownValue(); | |
| 69 Value operator -() => const UnknownValue(); | |
| 70 Value operator &(Value other) => const UnknownValue(); | |
| 71 | |
| 72 Value min(Value other) { | |
| 73 if (this == other) return this; | |
| 74 if (other == const MinIntValue()) return other; | |
| 75 if (other == const MaxIntValue()) return this; | |
| 76 Value value = this - other; | |
| 77 if (value.isPositive) return other; | |
| 78 if (value.isNegative) return this; | |
| 79 return const UnknownValue(); | |
| 80 } | |
| 81 | |
| 82 Value max(Value other) { | |
| 83 if (this == other) return this; | |
| 84 if (other == const MinIntValue()) return this; | |
| 85 if (other == const MaxIntValue()) return other; | |
| 86 Value value = this - other; | |
| 87 if (value.isPositive) return this; | |
| 88 if (value.isNegative) return other; | |
| 89 return const UnknownValue(); | |
| 90 } | |
| 91 | |
| 92 bool get isNegative => false; | |
| 93 bool get isPositive => false; | |
| 94 bool get isZero => false; | |
| 95 } | |
| 96 | |
| 97 /** | |
| 98 * The [MarkerValue] class is used to recognize ranges of loop | |
| 99 * updates. | |
| 100 */ | |
| 101 class MarkerValue extends Value { | |
| 102 /// If [positive] is true (respectively false), the marker goes | |
| 103 /// to [MaxIntValue] (respectively [MinIntValue]) when being added | |
| 104 /// to a positive (respectively negative) value. | |
| 105 final bool positive; | |
| 106 | |
| 107 const MarkerValue(this.positive, info) : super(info); | |
| 108 | |
| 109 Value operator +(Value other) { | |
| 110 if (other.isPositive && positive) return const MaxIntValue(); | |
| 111 if (other.isNegative && !positive) return const MinIntValue(); | |
| 112 if (other is IntValue) return this; | |
| 113 return const UnknownValue(); | |
| 114 } | |
| 115 | |
| 116 Value operator -(Value other) { | |
| 117 if (other.isPositive && !positive) return const MinIntValue(); | |
| 118 if (other.isNegative && positive) return const MaxIntValue(); | |
| 119 if (other is IntValue) return this; | |
| 120 return const UnknownValue(); | |
| 121 } | |
| 122 } | |
| 123 | |
| 124 /** | |
| 125 * An [IntValue] contains a constant integer value. | |
| 126 */ | |
| 127 class IntValue extends Value { | |
| 128 final int value; | |
| 129 | |
| 130 const IntValue(this.value, info) : super(info); | |
| 131 | |
| 132 Value operator +(other) { | |
| 133 if (other.isZero) return this; | |
| 134 if (other is !IntValue) return other + this; | |
| 135 ConstantSystem constantSystem = info.constantSystem; | |
| 136 var constant = constantSystem.add.fold( | |
| 137 constantSystem.createInt(value), constantSystem.createInt(other.value)); | |
| 138 if (!constant.isInt) return const UnknownValue(); | |
| 139 return info.newIntValue(constant.primitiveValue); | |
| 140 } | |
| 141 | |
| 142 Value operator -(other) { | |
| 143 if (other.isZero) return this; | |
| 144 if (other is !IntValue) return -other + this; | |
| 145 ConstantSystem constantSystem = info.constantSystem; | |
| 146 var constant = constantSystem.subtract.fold( | |
| 147 constantSystem.createInt(value), constantSystem.createInt(other.value)); | |
| 148 if (!constant.isInt) return const UnknownValue(); | |
| 149 return info.newIntValue(constant.primitiveValue); | |
| 150 } | |
| 151 | |
| 152 Value operator -() { | |
| 153 if (isZero) return this; | |
| 154 ConstantSystem constantSystem = info.constantSystem; | |
| 155 var constant = constantSystem.negate.fold( | |
| 156 constantSystem.createInt(value)); | |
| 157 if (!constant.isInt) return const UnknownValue(); | |
| 158 return info.newIntValue(constant.primitiveValue); | |
| 159 } | |
| 160 | |
| 161 Value operator &(other) { | |
| 162 if (other is !IntValue) return const UnknownValue(); | |
| 163 ConstantSystem constantSystem = info.constantSystem; | |
| 164 var constant = constantSystem.bitAnd.fold( | |
| 165 constantSystem.createInt(value), constantSystem.createInt(other.value)); | |
| 166 return info.newIntValue(constant.primitiveValue); | |
| 167 } | |
| 168 | |
| 169 Value min(other) { | |
| 170 if (other is !IntValue) return other.min(this); | |
| 171 return this.value < other.value ? this : other; | |
| 172 } | |
| 173 | |
| 174 Value max(other) { | |
| 175 if (other is !IntValue) return other.max(this); | |
| 176 return this.value < other.value ? other : this; | |
| 177 } | |
| 178 | |
| 179 bool operator ==(other) { | |
| 180 if (other is !IntValue) return false; | |
| 181 return this.value == other.value; | |
| 182 } | |
| 183 | |
| 184 int get hashCode => throw new UnsupportedError('IntValue.hashCode'); | |
| 185 | |
| 186 String toString() => 'IntValue $value'; | |
| 187 bool get isNegative => value < 0; | |
| 188 bool get isPositive => value >= 0; | |
| 189 bool get isZero => value == 0; | |
| 190 } | |
| 191 | |
| 192 /** | |
| 193 * The [MaxIntValue] represents the maximum value an integer can have, | |
| 194 * which is currently +infinity. | |
| 195 */ | |
| 196 class MaxIntValue extends Value { | |
| 197 const MaxIntValue() : super(null); | |
| 198 Value operator +(Value other) => this; | |
| 199 Value operator -(Value other) => this; | |
| 200 Value operator -() => const MinIntValue(); | |
| 201 Value min(Value other) => other; | |
| 202 Value max(Value other) => this; | |
| 203 String toString() => 'Max'; | |
| 204 bool get isNegative => false; | |
| 205 bool get isPositive => true; | |
| 206 } | |
| 207 | |
| 208 /** | |
| 209 * The [MinIntValue] represents the minimum value an integer can have, | |
| 210 * which is currently -infinity. | |
| 211 */ | |
| 212 class MinIntValue extends Value { | |
| 213 const MinIntValue() : super(null); | |
| 214 Value operator +(Value other) => this; | |
| 215 Value operator -(Value other) => this; | |
| 216 Value operator -() => const MaxIntValue(); | |
| 217 Value min(Value other) => this; | |
| 218 Value max(Value other) => other; | |
| 219 String toString() => 'Min'; | |
| 220 bool get isNegative => true; | |
| 221 bool get isPositive => false; | |
| 222 } | |
| 223 | |
| 224 /** | |
| 225 * The [UnknownValue] is the sentinel in our analysis to mark an | |
| 226 * operation that could not be done because of too much complexity. | |
| 227 */ | |
| 228 class UnknownValue extends Value { | |
| 229 const UnknownValue() : super(null); | |
| 230 Value operator +(Value other) => const UnknownValue(); | |
| 231 Value operator -(Value other) => const UnknownValue(); | |
| 232 Value operator -() => const UnknownValue(); | |
| 233 Value min(Value other) => const UnknownValue(); | |
| 234 Value max(Value other) => const UnknownValue(); | |
| 235 bool get isNegative => false; | |
| 236 bool get isPositive => false; | |
| 237 String toString() => 'Unknown'; | |
| 238 } | |
| 239 | |
| 240 /** | |
| 241 * A symbolic value representing an [HInstruction]. | |
| 242 */ | |
| 243 class InstructionValue extends Value { | |
| 244 final HInstruction instruction; | |
| 245 InstructionValue(this.instruction, info) : super(info); | |
| 246 | |
| 247 bool operator ==(other) { | |
| 248 if (other is !InstructionValue) return false; | |
| 249 return this.instruction == other.instruction; | |
| 250 } | |
| 251 | |
| 252 int get hashCode => throw new UnsupportedError('InstructionValue.hashCode'); | |
| 253 | |
| 254 Value operator +(Value other) { | |
| 255 if (other.isZero) return this; | |
| 256 if (other is IntValue) { | |
| 257 if (other.isNegative) { | |
| 258 return info.newSubtractValue(this, -other); | |
| 259 } | |
| 260 return info.newAddValue(this, other); | |
| 261 } | |
| 262 if (other is InstructionValue) { | |
| 263 return info.newAddValue(this, other); | |
| 264 } | |
| 265 return other + this; | |
| 266 } | |
| 267 | |
| 268 Value operator -(Value other) { | |
| 269 if (other.isZero) return this; | |
| 270 if (this == other) return info.intZero; | |
| 271 if (other is IntValue) { | |
| 272 if (other.isNegative) { | |
| 273 return info.newAddValue(this, -other); | |
| 274 } | |
| 275 return info.newSubtractValue(this, other); | |
| 276 } | |
| 277 if (other is InstructionValue) { | |
| 278 return info.newSubtractValue(this, other); | |
| 279 } | |
| 280 return -other + this; | |
| 281 } | |
| 282 | |
| 283 Value operator -() { | |
| 284 return info.newNegateValue(this); | |
| 285 } | |
| 286 | |
| 287 bool get isNegative => false; | |
| 288 bool get isPositive => false; | |
| 289 | |
| 290 String toString() => 'Instruction: $instruction'; | |
| 291 } | |
| 292 | |
| 293 /** | |
| 294 * Special value for instructions whose type is a positive integer. | |
| 295 */ | |
| 296 class PositiveValue extends InstructionValue { | |
| 297 PositiveValue(HInstruction instruction, info) : super(instruction, info); | |
| 298 bool get isPositive => true; | |
| 299 } | |
| 300 | |
| 301 /** | |
| 302 * Represents a binary operation on two [Value], where the operation | |
| 303 * did not yield a canonical value. | |
| 304 */ | |
| 305 class BinaryOperationValue extends Value { | |
| 306 final Value left; | |
| 307 final Value right; | |
| 308 BinaryOperationValue(this.left, this.right, info) : super(info); | |
| 309 } | |
| 310 | |
| 311 class AddValue extends BinaryOperationValue { | |
| 312 AddValue(left, right, info) : super(left, right, info); | |
| 313 | |
| 314 bool operator ==(other) { | |
| 315 if (other is !AddValue) return false; | |
| 316 return (left == other.left && right == other.right) | |
| 317 || (left == other.right && right == other.left); | |
| 318 } | |
| 319 | |
| 320 int get hashCode => throw new UnsupportedError('AddValue.hashCode'); | |
| 321 | |
| 322 Value operator -() => -left - right; | |
| 323 | |
| 324 Value operator +(Value other) { | |
| 325 if (other.isZero) return this; | |
| 326 Value value = left + other; | |
| 327 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 328 return value + right; | |
| 329 } | |
| 330 // If the result is not simple enough, we try the same approach | |
| 331 // with [right]. | |
| 332 value = right + other; | |
| 333 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 334 return left + value; | |
| 335 } | |
| 336 return const UnknownValue(); | |
| 337 } | |
| 338 | |
| 339 Value operator -(Value other) { | |
| 340 if (other.isZero) return this; | |
| 341 Value value = left - other; | |
| 342 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 343 return value + right; | |
| 344 } | |
| 345 // If the result is not simple enough, we try the same approach | |
| 346 // with [right]. | |
| 347 value = right - other; | |
| 348 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 349 return left + value; | |
| 350 } | |
| 351 return const UnknownValue(); | |
| 352 } | |
| 353 | |
| 354 bool get isNegative => left.isNegative && right.isNegative; | |
| 355 bool get isPositive => left.isPositive && right.isPositive; | |
| 356 String toString() => '$left + $right'; | |
| 357 } | |
| 358 | |
| 359 class SubtractValue extends BinaryOperationValue { | |
| 360 SubtractValue(left, right, info) : super(left, right, info); | |
| 361 | |
| 362 bool operator ==(other) { | |
| 363 if (other is !SubtractValue) return false; | |
| 364 return left == other.left && right == other.right; | |
| 365 } | |
| 366 | |
| 367 int get hashCode => throw new UnsupportedError('SubtractValue.hashCode'); | |
| 368 | |
| 369 Value operator -() => right - left; | |
| 370 | |
| 371 Value operator +(Value other) { | |
| 372 if (other.isZero) return this; | |
| 373 Value value = left + other; | |
| 374 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 375 return value - right; | |
| 376 } | |
| 377 // If the result is not simple enough, we try the same approach | |
| 378 // with [right]. | |
| 379 value = other - right; | |
| 380 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 381 return left + value; | |
| 382 } | |
| 383 return const UnknownValue(); | |
| 384 } | |
| 385 | |
| 386 Value operator -(Value other) { | |
| 387 if (other.isZero) return this; | |
| 388 Value value = left - other; | |
| 389 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 390 return value - right; | |
| 391 } | |
| 392 // If the result is not simple enough, we try the same approach | |
| 393 // with [right]. | |
| 394 value = right + other; | |
| 395 if (value != const UnknownValue() && value is! BinaryOperationValue) { | |
| 396 return left - value; | |
| 397 } | |
| 398 return const UnknownValue(); | |
| 399 } | |
| 400 | |
| 401 bool get isNegative => left.isNegative && right.isPositive; | |
| 402 bool get isPositive => left.isPositive && right.isNegative; | |
| 403 String toString() => '$left - $right'; | |
| 404 } | |
| 405 | |
| 406 class NegateValue extends Value { | |
| 407 final Value value; | |
| 408 NegateValue(this.value, info) : super(info); | |
| 409 | |
| 410 bool operator ==(other) { | |
| 411 if (other is !NegateValue) return false; | |
| 412 return value == other.value; | |
| 413 } | |
| 414 | |
| 415 int get hashCode => throw new UnsupportedError('Negate.hashCode'); | |
| 416 | |
| 417 Value operator +(other) { | |
| 418 if (other.isZero) return this; | |
| 419 if (other == value) return info.intZero; | |
| 420 if (other is NegateValue) return this - other.value; | |
| 421 if (other is IntValue) { | |
| 422 if (other.isNegative) { | |
| 423 return info.newSubtractValue(this, -other); | |
| 424 } | |
| 425 return info.newSubtractValue(other, value); | |
| 426 } | |
| 427 if (other is InstructionValue) { | |
| 428 return info.newSubtractValue(other, value); | |
| 429 } | |
| 430 return other - value; | |
| 431 } | |
| 432 | |
| 433 Value operator &(Value other) => const UnknownValue(); | |
| 434 | |
| 435 Value operator -(other) { | |
| 436 if (other.isZero) return this; | |
| 437 if (other is IntValue) { | |
| 438 if (other.isNegative) { | |
| 439 return info.newSubtractValue(-other, value); | |
| 440 } | |
| 441 return info.newSubtractValue(this, other); | |
| 442 } | |
| 443 if (other is InstructionValue) { | |
| 444 return info.newSubtractValue(this, other); | |
| 445 } | |
| 446 if (other is NegateValue) return this + other.value; | |
| 447 return -other - value; | |
| 448 } | |
| 449 | |
| 450 Value operator -() => value; | |
| 451 | |
| 452 bool get isNegative => value.isPositive; | |
| 453 bool get isPositive => value.isNegative; | |
| 454 String toString() => '-$value'; | |
| 455 } | |
| 456 | |
| 457 /** | |
| 458 * A [Range] represents the possible integer values an instruction | |
| 459 * can have, from its [lower] bound to its [upper] bound, both | |
| 460 * included. | |
| 461 */ | |
| 462 class Range { | |
| 463 final Value lower; | |
| 464 final Value upper; | |
| 465 final ValueRangeInfo info; | |
| 466 Range(this.lower, this.upper, this.info) { | |
| 467 assert(lower != const UnknownValue()); | |
| 468 assert(upper != const UnknownValue()); | |
| 469 } | |
| 470 | |
| 471 Range.unbound(info) : this(const MinIntValue(), const MaxIntValue(), info); | |
| 472 | |
| 473 /** | |
| 474 * Checks if the given values are unknown, and creates a | |
| 475 * range that does not have any unknown values. | |
| 476 */ | |
| 477 Range.normalize(Value low, Value up, info) : this( | |
| 478 low == const UnknownValue() ? const MinIntValue() : low, | |
| 479 up == const UnknownValue() ? const MaxIntValue() : up, | |
| 480 info); | |
| 481 | |
| 482 Range union(Range other) { | |
| 483 return info.newNormalizedRange( | |
| 484 lower.min(other.lower), upper.max(other.upper)); | |
| 485 } | |
| 486 | |
| 487 Range intersection(Range other) { | |
| 488 Value low = lower.max(other.lower); | |
| 489 Value up = upper.min(other.upper); | |
| 490 // If we could not compute max or min, pick a value in the two | |
| 491 // ranges, with priority to [IntValue]s because they are simpler. | |
| 492 if (low == const UnknownValue()) { | |
| 493 if (lower is IntValue) low = lower; | |
| 494 else if (other.lower is IntValue) low = other.lower; | |
| 495 else low = lower; | |
| 496 } | |
| 497 if (up == const UnknownValue()) { | |
| 498 if (upper is IntValue) up = upper; | |
| 499 else if (other.upper is IntValue) up = other.upper; | |
| 500 else up = upper; | |
| 501 } | |
| 502 return info.newNormalizedRange(low, up); | |
| 503 } | |
| 504 | |
| 505 Range operator +(Range other) { | |
| 506 return info.newNormalizedRange(lower + other.lower, upper + other.upper); | |
| 507 } | |
| 508 | |
| 509 Range operator -(Range other) { | |
| 510 return info.newNormalizedRange(lower - other.upper, upper - other.lower); | |
| 511 } | |
| 512 | |
| 513 Range operator -() { | |
| 514 return info.newNormalizedRange(-upper, -lower); | |
| 515 } | |
| 516 | |
| 517 Range operator &(Range other) { | |
| 518 if (isSingleValue | |
| 519 && other.isSingleValue | |
| 520 && lower is IntValue | |
| 521 && other.lower is IntValue) { | |
| 522 return info.newNormalizedRange(lower & other.lower, upper & other.upper); | |
| 523 } | |
| 524 if (isPositive && other.isPositive) { | |
| 525 Value up = upper.min(other.upper); | |
| 526 if (up == const UnknownValue()) { | |
| 527 // If we could not find a trivial bound, just try to use the | |
| 528 // one that is an int. | |
| 529 up = upper is IntValue ? upper : other.upper; | |
| 530 // Make sure we get the same upper bound, whether it's a & b | |
| 531 // or b & a. | |
| 532 if (up is! IntValue && upper != other.upper) up = const MaxIntValue(); | |
| 533 } | |
| 534 return info.newNormalizedRange(info.intZero, up); | |
| 535 } else if (isPositive) { | |
| 536 return info.newNormalizedRange(info.intZero, upper); | |
| 537 } else if (other.isPositive) { | |
| 538 return info.newNormalizedRange(info.intZero, other.upper); | |
| 539 } else { | |
| 540 return info.newUnboundRange(); | |
| 541 } | |
| 542 } | |
| 543 | |
| 544 bool operator ==(other) { | |
| 545 if (other is! Range) return false; | |
| 546 return other.lower == lower && other.upper == upper; | |
| 547 } | |
| 548 | |
| 549 int get hashCode => throw new UnsupportedError('Range.hashCode'); | |
| 550 | |
| 551 bool operator <(Range other) { | |
| 552 return upper != other.lower && upper.min(other.lower) == upper; | |
| 553 } | |
| 554 | |
| 555 bool operator >(Range other) { | |
| 556 return lower != other.upper && lower.max(other.upper) == lower; | |
| 557 } | |
| 558 | |
| 559 bool operator <=(Range other) { | |
| 560 return upper.min(other.lower) == upper; | |
| 561 } | |
| 562 | |
| 563 bool operator >=(Range other) { | |
| 564 return lower.max(other.upper) == lower; | |
| 565 } | |
| 566 | |
| 567 bool get isNegative => upper.isNegative; | |
| 568 bool get isPositive => lower.isPositive; | |
| 569 bool get isSingleValue => lower == upper; | |
| 570 | |
| 571 String toString() => '[$lower, $upper]'; | |
| 572 } | |
| 573 | |
| 574 /** | |
| 575 * Visits the graph in dominator order, and computes value ranges for | |
| 576 * integer instructions. While visiting the graph, this phase also | |
| 577 * removes unnecessary bounds checks, and comparisons that are proven | |
| 578 * to be true or false. | |
| 579 */ | |
| 580 class SsaValueRangeAnalyzer extends HBaseVisitor implements OptimizationPhase { | |
| 581 String get name => 'SSA value range builder'; | |
| 582 | |
| 583 /** | |
| 584 * List of [HRangeConversion] instructions created by the phase. We | |
| 585 * save them here in order to remove them once the phase is done. | |
| 586 */ | |
| 587 final List<HRangeConversion> conversions = <HRangeConversion>[]; | |
| 588 | |
| 589 /** | |
| 590 * Value ranges for integer instructions. This map gets populated by | |
| 591 * the dominator tree visit. | |
| 592 */ | |
| 593 final Map<HInstruction, Range> ranges = new Map<HInstruction, Range>(); | |
| 594 | |
| 595 final Compiler compiler; | |
| 596 final ConstantSystem constantSystem; | |
| 597 final ValueRangeInfo info; | |
| 598 | |
| 599 CodegenWorkItem work; | |
| 600 HGraph graph; | |
| 601 | |
| 602 SsaValueRangeAnalyzer(this.compiler, constantSystem, this.work) | |
| 603 : info = new ValueRangeInfo(constantSystem), | |
| 604 this.constantSystem = constantSystem; | |
| 605 | |
| 606 void visitGraph(HGraph graph) { | |
| 607 this.graph = graph; | |
| 608 visitDominatorTree(graph); | |
| 609 // We remove the range conversions after visiting the graph so | |
| 610 // that the graph does not get polluted with these instructions | |
| 611 // only necessary for this phase. | |
| 612 removeRangeConversion(); | |
| 613 JavaScriptBackend backend = compiler.backend; | |
| 614 // TODO(herhut): Find a cleaner way to pass around ranges. | |
| 615 backend.optimizer.ranges = ranges; | |
| 616 } | |
| 617 | |
| 618 void removeRangeConversion() { | |
| 619 conversions.forEach((HRangeConversion instruction) { | |
| 620 instruction.block.rewrite(instruction, instruction.inputs[0]);; | |
| 621 instruction.block.remove(instruction); | |
| 622 }); | |
| 623 } | |
| 624 | |
| 625 void visitBasicBlock(HBasicBlock block) { | |
| 626 | |
| 627 void visit(HInstruction instruction) { | |
| 628 Range range = instruction.accept(this); | |
| 629 if (instruction.isInteger(compiler)) { | |
| 630 assert(range != null); | |
| 631 ranges[instruction] = range; | |
| 632 } | |
| 633 } | |
| 634 | |
| 635 block.forEachPhi(visit); | |
| 636 block.forEachInstruction(visit); | |
| 637 } | |
| 638 | |
| 639 Range visitInstruction(HInstruction instruction) { | |
| 640 if (instruction.isPositiveInteger(compiler)) { | |
| 641 return info.newNormalizedRange( | |
| 642 info.intZero, info.newPositiveValue(instruction)); | |
| 643 } else if (instruction.isInteger(compiler)) { | |
| 644 InstructionValue value = info.newInstructionValue(instruction); | |
| 645 return info.newNormalizedRange(value, value); | |
| 646 } else { | |
| 647 return info.newUnboundRange(); | |
| 648 } | |
| 649 } | |
| 650 | |
| 651 Range visitPhi(HPhi phi) { | |
| 652 if (!phi.isInteger(compiler)) return info.newUnboundRange(); | |
| 653 // Some phases may replace instructions that change the inputs of | |
| 654 // this phi. Only the [SsaTypesPropagation] phase will update the | |
| 655 // phi type. Play it safe by assuming the [SsaTypesPropagation] | |
| 656 // phase is not necessarily run before the [ValueRangeAnalyzer]. | |
| 657 if (phi.inputs.any((i) => !i.isInteger(compiler))) { | |
| 658 return info.newUnboundRange(); | |
| 659 } | |
| 660 if (phi.block.isLoopHeader()) { | |
| 661 Range range = new LoopUpdateRecognizer(compiler, ranges, info).run(phi); | |
| 662 if (range == null) return info.newUnboundRange(); | |
| 663 return range; | |
| 664 } | |
| 665 | |
| 666 Range range = ranges[phi.inputs[0]]; | |
| 667 for (int i = 1; i < phi.inputs.length; i++) { | |
| 668 range = range.union(ranges[phi.inputs[i]]); | |
| 669 } | |
| 670 return range; | |
| 671 } | |
| 672 | |
| 673 Range visitConstant(HConstant hConstant) { | |
| 674 if (!hConstant.isInteger(compiler)) return info.newUnboundRange(); | |
| 675 ConstantValue constant = hConstant.constant; | |
| 676 NumConstantValue constantNum; | |
| 677 if (constant is DeferredConstantValue) { | |
| 678 constantNum = constant.referenced; | |
| 679 } else { | |
| 680 constantNum = constant; | |
| 681 } | |
| 682 if (constantNum.isMinusZero) constantNum = new IntConstantValue(0); | |
| 683 Value value = info.newIntValue(constantNum.primitiveValue); | |
| 684 return info.newNormalizedRange(value, value); | |
| 685 } | |
| 686 | |
| 687 Range visitFieldGet(HFieldGet fieldGet) { | |
| 688 if (!fieldGet.isInteger(compiler)) return info.newUnboundRange(); | |
| 689 if (!fieldGet.receiver.isIndexablePrimitive(compiler)) { | |
| 690 return visitInstruction(fieldGet); | |
| 691 } | |
| 692 JavaScriptBackend backend = compiler.backend; | |
| 693 assert(fieldGet.element == backend.jsIndexableLength); | |
| 694 PositiveValue value = info.newPositiveValue(fieldGet); | |
| 695 // We know this range is above zero. To simplify the analysis, we | |
| 696 // put the zero value as the lower bound of this range. This | |
| 697 // allows to easily remove the second bound check in the following | |
| 698 // expression: a[1] + a[0]. | |
| 699 return info.newNormalizedRange(info.intZero, value); | |
| 700 } | |
| 701 | |
| 702 Range visitBoundsCheck(HBoundsCheck check) { | |
| 703 // Save the next instruction, in case the check gets removed. | |
| 704 HInstruction next = check.next; | |
| 705 Range indexRange = ranges[check.index]; | |
| 706 Range lengthRange = ranges[check.length]; | |
| 707 if (indexRange == null) { | |
| 708 indexRange = info.newUnboundRange(); | |
| 709 assert(!check.index.isInteger(compiler)); | |
| 710 } | |
| 711 assert(check.length.isInteger(compiler)); | |
| 712 | |
| 713 // Check if the index is strictly below the upper bound of the length | |
| 714 // range. | |
| 715 Value maxIndex = lengthRange.upper - info.intOne; | |
| 716 bool belowLength = maxIndex != const MaxIntValue() | |
| 717 && indexRange.upper.min(maxIndex) == indexRange.upper; | |
| 718 | |
| 719 // Check if the index is strictly below the lower bound of the length | |
| 720 // range. | |
| 721 belowLength = belowLength | |
| 722 || (indexRange.upper != lengthRange.lower | |
| 723 && indexRange.upper.min(lengthRange.lower) == indexRange.upper); | |
| 724 if (indexRange.isPositive && belowLength) { | |
| 725 check.block.rewrite(check, check.index); | |
| 726 check.block.remove(check); | |
| 727 } else if (indexRange.isNegative || lengthRange < indexRange) { | |
| 728 check.staticChecks = HBoundsCheck.ALWAYS_FALSE; | |
| 729 // The check is always false, and whatever instruction it | |
| 730 // dominates is dead code. | |
| 731 return indexRange; | |
| 732 } else if (indexRange.isPositive) { | |
| 733 check.staticChecks = HBoundsCheck.ALWAYS_ABOVE_ZERO; | |
| 734 } else if (belowLength) { | |
| 735 check.staticChecks = HBoundsCheck.ALWAYS_BELOW_LENGTH; | |
| 736 } | |
| 737 | |
| 738 if (indexRange.isPositive) { | |
| 739 // If the test passes, we know the lower bound of the length is | |
| 740 // greater or equal than the lower bound of the index. | |
| 741 Value low = lengthRange.lower.max(indexRange.lower); | |
| 742 if (low != const UnknownValue()) { | |
| 743 HInstruction instruction = | |
| 744 createRangeConversion(next, check.length); | |
| 745 ranges[instruction] = info.newNormalizedRange(low, lengthRange.upper); | |
| 746 } | |
| 747 } | |
| 748 | |
| 749 // Update the range of the index if using the maximum index | |
| 750 // narrows it. Use that new range for this instruction as well. | |
| 751 Range newIndexRange = indexRange.intersection( | |
| 752 info.newNormalizedRange(info.intZero, maxIndex)); | |
| 753 if (indexRange == newIndexRange) return indexRange; | |
| 754 // Explicitly attach the range information to the index instruction, | |
| 755 // which may be used by other instructions. Returning the new range will | |
| 756 // attach it to this instruction. | |
| 757 HInstruction instruction = createRangeConversion(next, check.index); | |
| 758 ranges[instruction] = newIndexRange; | |
| 759 return newIndexRange; | |
| 760 } | |
| 761 | |
| 762 Range visitRelational(HRelational relational) { | |
| 763 HInstruction right = relational.right; | |
| 764 HInstruction left = relational.left; | |
| 765 if (!left.isInteger(compiler)) return info.newUnboundRange(); | |
| 766 if (!right.isInteger(compiler)) return info.newUnboundRange(); | |
| 767 BinaryOperation operation = relational.operation(constantSystem); | |
| 768 Range rightRange = ranges[relational.right]; | |
| 769 Range leftRange = ranges[relational.left]; | |
| 770 | |
| 771 if (relational is HIdentity) { | |
| 772 handleEqualityCheck(relational); | |
| 773 } else if (operation.apply(leftRange, rightRange)) { | |
| 774 relational.block.rewrite( | |
| 775 relational, graph.addConstantBool(true, compiler)); | |
| 776 relational.block.remove(relational); | |
| 777 } else if (negateOperation(operation).apply(leftRange, rightRange)) { | |
| 778 relational.block.rewrite( | |
| 779 relational, graph.addConstantBool(false, compiler)); | |
| 780 relational.block.remove(relational); | |
| 781 } | |
| 782 return info.newUnboundRange(); | |
| 783 } | |
| 784 | |
| 785 void handleEqualityCheck(HRelational node) { | |
| 786 Range right = ranges[node.right]; | |
| 787 Range left = ranges[node.left]; | |
| 788 if (left.isSingleValue && right.isSingleValue && left == right) { | |
| 789 node.block.rewrite( | |
| 790 node, graph.addConstantBool(true, compiler)); | |
| 791 node.block.remove(node); | |
| 792 } | |
| 793 } | |
| 794 | |
| 795 Range handleInvokeModulo(HInvokeDynamicMethod invoke) { | |
| 796 HInstruction left = invoke.inputs[1]; | |
| 797 HInstruction right = invoke.inputs[2]; | |
| 798 Range divisor = ranges[right]; | |
| 799 if (divisor != null) { | |
| 800 // For Integer values we can be precise in the upper bound, | |
| 801 // so special case those. | |
| 802 if (left.isInteger(compiler) && right.isInteger(compiler)) { | |
| 803 if (divisor.isPositive) { | |
| 804 return info.newNormalizedRange(info.intZero, divisor.upper - | |
| 805 info.intOne); | |
| 806 } else if (divisor.isNegative) { | |
| 807 return info.newNormalizedRange(info.intZero, info.newNegateValue( | |
| 808 divisor.lower) - info.intOne); | |
| 809 } | |
| 810 } else if (left.isNumber(compiler) && right.isNumber(compiler)) { | |
| 811 if (divisor.isPositive) { | |
| 812 return info.newNormalizedRange(info.intZero, divisor.upper); | |
| 813 } else if (divisor.isNegative) { | |
| 814 return info.newNormalizedRange(info.intZero, info.newNegateValue( | |
| 815 divisor.lower)); | |
| 816 } | |
| 817 } | |
| 818 } | |
| 819 return info.newUnboundRange(); | |
| 820 } | |
| 821 | |
| 822 Range visitInvokeDynamicMethod(HInvokeDynamicMethod invoke) { | |
| 823 if ((invoke.inputs.length == 3) && (invoke.selector.name == "%")) | |
| 824 return handleInvokeModulo(invoke); | |
| 825 return super.visitInvokeDynamicMethod(invoke); | |
| 826 } | |
| 827 | |
| 828 Range handleBinaryOperation(HBinaryArithmetic instruction) { | |
| 829 if (!instruction.isInteger(compiler)) return info.newUnboundRange(); | |
| 830 return instruction.operation(constantSystem).apply( | |
| 831 ranges[instruction.left], ranges[instruction.right]); | |
| 832 } | |
| 833 | |
| 834 Range visitAdd(HAdd add) { | |
| 835 return handleBinaryOperation(add); | |
| 836 } | |
| 837 | |
| 838 Range visitSubtract(HSubtract sub) { | |
| 839 return handleBinaryOperation(sub); | |
| 840 } | |
| 841 | |
| 842 Range visitBitAnd(HBitAnd node) { | |
| 843 if (!node.isInteger(compiler)) return info.newUnboundRange(); | |
| 844 HInstruction right = node.right; | |
| 845 HInstruction left = node.left; | |
| 846 if (left.isInteger(compiler) && right.isInteger(compiler)) { | |
| 847 return ranges[left] & ranges[right]; | |
| 848 } | |
| 849 | |
| 850 Range tryComputeRange(HInstruction instruction) { | |
| 851 Range range = ranges[instruction]; | |
| 852 if (range.isPositive) { | |
| 853 return info.newNormalizedRange(info.intZero, range.upper); | |
| 854 } else if (range.isNegative) { | |
| 855 return info.newNormalizedRange(range.lower, info.intZero); | |
| 856 } | |
| 857 return info.newUnboundRange(); | |
| 858 } | |
| 859 | |
| 860 if (left.isInteger(compiler)) { | |
| 861 return tryComputeRange(left); | |
| 862 } else if (right.isInteger(compiler)) { | |
| 863 return tryComputeRange(right); | |
| 864 } | |
| 865 return info.newUnboundRange(); | |
| 866 } | |
| 867 | |
| 868 Range visitCheck(HCheck instruction) { | |
| 869 if (ranges[instruction.checkedInput] == null) { | |
| 870 return visitInstruction(instruction); | |
| 871 } | |
| 872 return ranges[instruction.checkedInput]; | |
| 873 } | |
| 874 | |
| 875 HInstruction createRangeConversion(HInstruction cursor, | |
| 876 HInstruction instruction) { | |
| 877 JavaScriptBackend backend = compiler.backend; | |
| 878 HRangeConversion newInstruction = | |
| 879 new HRangeConversion(instruction, backend.intType); | |
| 880 conversions.add(newInstruction); | |
| 881 cursor.block.addBefore(cursor, newInstruction); | |
| 882 // Update the users of the instruction dominated by [cursor] to | |
| 883 // use the new instruction, that has an narrower range. | |
| 884 instruction.replaceAllUsersDominatedBy(cursor, newInstruction); | |
| 885 return newInstruction; | |
| 886 } | |
| 887 | |
| 888 static BinaryOperation negateOperation(BinaryOperation operation) { | |
| 889 if (operation == const LessOperation()) { | |
| 890 return const GreaterEqualOperation(); | |
| 891 } else if (operation == const LessEqualOperation()) { | |
| 892 return const GreaterOperation(); | |
| 893 } else if (operation == const GreaterOperation()) { | |
| 894 return const LessEqualOperation(); | |
| 895 } else if (operation == const GreaterEqualOperation()) { | |
| 896 return const LessOperation(); | |
| 897 } else { | |
| 898 return null; | |
| 899 } | |
| 900 } | |
| 901 | |
| 902 static BinaryOperation flipOperation(BinaryOperation operation) { | |
| 903 if (operation == const LessOperation()) { | |
| 904 return const GreaterOperation(); | |
| 905 } else if (operation == const LessEqualOperation()) { | |
| 906 return const GreaterEqualOperation(); | |
| 907 } else if (operation == const GreaterOperation()) { | |
| 908 return const LessOperation(); | |
| 909 } else if (operation == const GreaterEqualOperation()) { | |
| 910 return const LessEqualOperation(); | |
| 911 } else { | |
| 912 return null; | |
| 913 } | |
| 914 } | |
| 915 | |
| 916 Range computeConstrainedRange(BinaryOperation operation, | |
| 917 Range leftRange, | |
| 918 Range rightRange) { | |
| 919 Range range; | |
| 920 if (operation == const LessOperation()) { | |
| 921 range = info.newNormalizedRange( | |
| 922 const MinIntValue(), rightRange.upper - info.intOne); | |
| 923 } else if (operation == const LessEqualOperation()) { | |
| 924 range = info.newNormalizedRange(const MinIntValue(), rightRange.upper); | |
| 925 } else if (operation == const GreaterOperation()) { | |
| 926 range = info.newNormalizedRange( | |
| 927 rightRange.lower + info.intOne, const MaxIntValue()); | |
| 928 } else if (operation == const GreaterEqualOperation()) { | |
| 929 range = info.newNormalizedRange(rightRange.lower, const MaxIntValue()); | |
| 930 } else { | |
| 931 range = info.newUnboundRange(); | |
| 932 } | |
| 933 return range.intersection(leftRange); | |
| 934 } | |
| 935 | |
| 936 Range visitConditionalBranch(HConditionalBranch branch) { | |
| 937 var condition = branch.condition; | |
| 938 // TODO(ngeoffray): Handle complex conditions. | |
| 939 if (condition is !HRelational) return info.newUnboundRange(); | |
| 940 if (condition is HIdentity) return info.newUnboundRange(); | |
| 941 HInstruction right = condition.right; | |
| 942 HInstruction left = condition.left; | |
| 943 if (!left.isInteger(compiler)) return info.newUnboundRange(); | |
| 944 if (!right.isInteger(compiler)) return info.newUnboundRange(); | |
| 945 | |
| 946 Range rightRange = ranges[right]; | |
| 947 Range leftRange = ranges[left]; | |
| 948 Operation operation = condition.operation(constantSystem); | |
| 949 Operation mirrorOp = flipOperation(operation); | |
| 950 // Only update the true branch if this block is the only | |
| 951 // predecessor. | |
| 952 if (branch.trueBranch.predecessors.length == 1) { | |
| 953 assert(branch.trueBranch.predecessors[0] == branch.block); | |
| 954 // Update the true branch to use narrower ranges for [left] and | |
| 955 // [right]. | |
| 956 Range range = computeConstrainedRange(operation, leftRange, rightRange); | |
| 957 if (leftRange != range) { | |
| 958 HInstruction instruction = | |
| 959 createRangeConversion(branch.trueBranch.first, left); | |
| 960 ranges[instruction] = range; | |
| 961 } | |
| 962 | |
| 963 range = computeConstrainedRange(mirrorOp, rightRange, leftRange); | |
| 964 if (rightRange != range) { | |
| 965 HInstruction instruction = | |
| 966 createRangeConversion(branch.trueBranch.first, right); | |
| 967 ranges[instruction] = range; | |
| 968 } | |
| 969 } | |
| 970 | |
| 971 // Only update the false branch if this block is the only | |
| 972 // predecessor. | |
| 973 if (branch.falseBranch.predecessors.length == 1) { | |
| 974 assert(branch.falseBranch.predecessors[0] == branch.block); | |
| 975 Operation reverse = negateOperation(operation); | |
| 976 Operation reversedMirror = flipOperation(reverse); | |
| 977 // Update the false branch to use narrower ranges for [left] and | |
| 978 // [right]. | |
| 979 Range range = computeConstrainedRange(reverse, leftRange, rightRange); | |
| 980 if (leftRange != range) { | |
| 981 HInstruction instruction = | |
| 982 createRangeConversion(branch.falseBranch.first, left); | |
| 983 ranges[instruction] = range; | |
| 984 } | |
| 985 | |
| 986 range = computeConstrainedRange(reversedMirror, rightRange, leftRange); | |
| 987 if (rightRange != range) { | |
| 988 HInstruction instruction = | |
| 989 createRangeConversion(branch.falseBranch.first, right); | |
| 990 ranges[instruction] = range; | |
| 991 } | |
| 992 } | |
| 993 | |
| 994 return info.newUnboundRange(); | |
| 995 } | |
| 996 | |
| 997 Range visitRangeConversion(HRangeConversion conversion) { | |
| 998 return ranges[conversion]; | |
| 999 } | |
| 1000 } | |
| 1001 | |
| 1002 /** | |
| 1003 * Tries to find a range for the update instruction of a loop phi. | |
| 1004 */ | |
| 1005 class LoopUpdateRecognizer extends HBaseVisitor { | |
| 1006 final Compiler compiler; | |
| 1007 final Map<HInstruction, Range> ranges; | |
| 1008 final ValueRangeInfo info; | |
| 1009 LoopUpdateRecognizer(this.compiler, this.ranges, this.info); | |
| 1010 | |
| 1011 Range run(HPhi loopPhi) { | |
| 1012 // Create a marker range for the loop phi, so that if the update | |
| 1013 // uses the loop phi, it has a range to use. | |
| 1014 ranges[loopPhi] = info.newMarkerRange(); | |
| 1015 Range updateRange = visit(loopPhi.inputs[1]); | |
| 1016 ranges[loopPhi] = null; | |
| 1017 if (updateRange == null) return null; | |
| 1018 Range startRange = ranges[loopPhi.inputs[0]]; | |
| 1019 // If the lower (respectively upper) value is the marker, we know | |
| 1020 // the loop does not change it, so we can just use the | |
| 1021 // [startRange]'s lower (upper) value. Otherwise the lower (upper) value | |
| 1022 // is the minimum of the [startRange]'s lower (upper) and the | |
| 1023 // [updateRange]'s lower (upper). | |
| 1024 Value low = updateRange.lower is MarkerValue | |
| 1025 ? startRange.lower | |
| 1026 : updateRange.lower.min(startRange.lower); | |
| 1027 Value up = updateRange.upper is MarkerValue | |
| 1028 ? startRange.upper | |
| 1029 : updateRange.upper.max(startRange.upper); | |
| 1030 return info.newNormalizedRange(low, up); | |
| 1031 } | |
| 1032 | |
| 1033 Range visit(HInstruction instruction) { | |
| 1034 if (!instruction.isInteger(compiler)) return null; | |
| 1035 if (ranges[instruction] != null) return ranges[instruction]; | |
| 1036 return instruction.accept(this); | |
| 1037 } | |
| 1038 | |
| 1039 Range visitPhi(HPhi phi) { | |
| 1040 // If the update of a loop phi involves another loop phi, we give | |
| 1041 // up. | |
| 1042 if (phi.block.isLoopHeader()) return null; | |
| 1043 Range phiRange; | |
| 1044 for (HInstruction input in phi.inputs) { | |
| 1045 Range inputRange = visit(input); | |
| 1046 if (inputRange == null) return null; | |
| 1047 if (phiRange == null) { | |
| 1048 phiRange = inputRange; | |
| 1049 } else { | |
| 1050 phiRange = phiRange.union(inputRange); | |
| 1051 } | |
| 1052 } | |
| 1053 return phiRange; | |
| 1054 } | |
| 1055 | |
| 1056 Range visitCheck(HCheck instruction) { | |
| 1057 return visit(instruction.checkedInput); | |
| 1058 } | |
| 1059 | |
| 1060 Range visitAdd(HAdd operation) { | |
| 1061 return handleBinaryOperation(operation); | |
| 1062 } | |
| 1063 | |
| 1064 Range visitSubtract(HSubtract operation) { | |
| 1065 return handleBinaryOperation(operation); | |
| 1066 } | |
| 1067 | |
| 1068 Range handleBinaryOperation(HBinaryArithmetic instruction) { | |
| 1069 Range leftRange = visit(instruction.left); | |
| 1070 Range rightRange = visit(instruction.right); | |
| 1071 if (leftRange == null || rightRange == null) return null; | |
| 1072 BinaryOperation operation = instruction.operation(info.constantSystem); | |
| 1073 return operation.apply(leftRange, rightRange); | |
| 1074 } | |
| 1075 } | |
| 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