1// Copyright (c) 2014, 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#ifndef RUNTIME_VM_COMPILER_BACKEND_RANGE_ANALYSIS_H_
6#define RUNTIME_VM_COMPILER_BACKEND_RANGE_ANALYSIS_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "vm/compiler/backend/flow_graph.h"
13#include "vm/compiler/backend/il.h"
14
15namespace dart {
16
17class SExpression;
18class FlowGraphSerializer;
19
20class RangeBoundary : public ValueObject {
21 public:
22#define FOR_EACH_RANGE_BOUNDARY_KIND(V) \
23 V(Unknown) \
24 V(NegativeInfinity) \
25 V(PositiveInfinity) \
26 V(Symbol) \
27 V(Constant)
28
29#define KIND_DEFN(name) k##name,
30 enum Kind { FOR_EACH_RANGE_BOUNDARY_KIND(KIND_DEFN) };
31#undef KIND_DEFN
32
33 static const char* KindToCString(Kind kind);
34 static bool ParseKind(const char* str, Kind* out);
35
36 enum RangeSize {
37 kRangeBoundarySmi,
38 kRangeBoundaryInt32,
39 kRangeBoundaryInt64,
40 };
41
42 RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) {}
43
44 RangeBoundary(const RangeBoundary& other)
45 : ValueObject(),
46 kind_(other.kind_),
47 value_(other.value_),
48 offset_(other.offset_) {}
49
50 explicit RangeBoundary(int64_t val)
51 : kind_(kConstant), value_(val), offset_(0) {}
52
53 RangeBoundary& operator=(const RangeBoundary& other) {
54 kind_ = other.kind_;
55 value_ = other.value_;
56 offset_ = other.offset_;
57 return *this;
58 }
59
60 static const int64_t kMin = kMinInt64;
61 static const int64_t kMax = kMaxInt64;
62
63 // Construct a RangeBoundary for a constant value.
64 static RangeBoundary FromConstant(int64_t val) { return RangeBoundary(val); }
65
66 // Construct a RangeBoundary for -inf.
67 static RangeBoundary NegativeInfinity() {
68 return RangeBoundary(kNegativeInfinity, 0, 0);
69 }
70
71 // Construct a RangeBoundary for +inf.
72 static RangeBoundary PositiveInfinity() {
73 return RangeBoundary(kPositiveInfinity, 0, 0);
74 }
75
76 // Construct a RangeBoundary from a definition and offset.
77 static RangeBoundary FromDefinition(Definition* defn, int64_t offs = 0);
78
79 static bool IsValidOffsetForSymbolicRangeBoundary(int64_t offset) {
80 if ((offset > (kMaxInt64 - compiler::target::kSmiMax)) ||
81 (offset < (kMinInt64 - compiler::target::kSmiMin))) {
82 // Avoid creating symbolic range boundaries which can wrap around.
83 return false;
84 }
85 return true;
86 }
87
88 // Construct a RangeBoundary for the constant MinSmi value.
89 static RangeBoundary MinSmi() {
90 return FromConstant(compiler::target::kSmiMin);
91 }
92
93 // Construct a RangeBoundary for the constant MaxSmi value.
94 static RangeBoundary MaxSmi() {
95 return FromConstant(compiler::target::kSmiMax);
96 }
97
98 // Construct a RangeBoundary for the constant kMin value.
99 static RangeBoundary MinConstant(RangeSize size) {
100 switch (size) {
101 case kRangeBoundarySmi:
102 return FromConstant(compiler::target::kSmiMin);
103 case kRangeBoundaryInt32:
104 return FromConstant(kMinInt32);
105 case kRangeBoundaryInt64:
106 return FromConstant(kMinInt64);
107 }
108 UNREACHABLE();
109 return FromConstant(kMinInt64);
110 }
111
112 static RangeBoundary MaxConstant(RangeSize size) {
113 switch (size) {
114 case kRangeBoundarySmi:
115 return FromConstant(compiler::target::kSmiMax);
116 case kRangeBoundaryInt32:
117 return FromConstant(kMaxInt32);
118 case kRangeBoundaryInt64:
119 return FromConstant(kMaxInt64);
120 }
121 UNREACHABLE();
122 return FromConstant(kMaxInt64);
123 }
124
125 // Given two boundaries a and b, select one of them as c so that
126 //
127 // inf {[a, ...) ^ [b, ...)} >= inf {c}
128 //
129 static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b);
130
131 // Given two boundaries a and b, select one of them as c so that
132 //
133 // sup {(..., a] ^ (..., b]} <= sup {c}
134 //
135 static RangeBoundary IntersectionMax(RangeBoundary a, RangeBoundary b);
136
137 // Given two boundaries a and b compute boundary c such that
138 //
139 // inf {[a, ...) U [b, ...)} >= inf {c}
140 //
141 // Try to select c such that it is as close to inf {[a, ...) U [b, ...)}
142 // as possible.
143 static RangeBoundary JoinMin(RangeBoundary a,
144 RangeBoundary b,
145 RangeBoundary::RangeSize size);
146
147 // Given two boundaries a and b compute boundary c such that
148 //
149 // sup {(..., a] U (..., b]} <= sup {c}
150 //
151 // Try to select c such that it is as close to sup {(..., a] U (..., b]}
152 // as possible.
153 static RangeBoundary JoinMax(RangeBoundary a,
154 RangeBoundary b,
155 RangeBoundary::RangeSize size);
156
157 // Returns true when this is a constant that is outside of Smi range.
158 bool OverflowedSmi() const {
159 return (IsConstant() && !compiler::target::IsSmi(ConstantValue())) ||
160 IsInfinity();
161 }
162
163 bool Overflowed(RangeBoundary::RangeSize size) const {
164 ASSERT(IsConstantOrInfinity());
165 return !Equals(Clamp(size));
166 }
167
168 // Returns true if this outside mint range.
169 bool OverflowedMint() const { return IsInfinity(); }
170
171 // -/+ infinity are clamped to MinConstant/MaxConstant of the given type.
172 RangeBoundary Clamp(RangeSize size) const {
173 if (IsNegativeInfinity()) {
174 return RangeBoundary::MinConstant(size);
175 }
176
177 if (IsPositiveInfinity()) {
178 return RangeBoundary::MaxConstant(size);
179 }
180
181 if (IsConstant()) {
182 const RangeBoundary range_min = RangeBoundary::MinConstant(size);
183 const RangeBoundary range_max = RangeBoundary::MaxConstant(size);
184
185 if (ConstantValue() <= range_min.ConstantValue()) {
186 return range_min;
187 }
188 if (ConstantValue() >= range_max.ConstantValue()) {
189 return range_max;
190 }
191 }
192
193 // If this range is a symbolic range, we do not clamp it.
194 // This could lead to some imprecision later on.
195 return *this;
196 }
197
198 bool IsMinimumOrBelow(RangeSize size) const {
199 return IsNegativeInfinity() ||
200 (IsConstant() && (ConstantValue() <=
201 RangeBoundary::MinConstant(size).ConstantValue()));
202 }
203
204 bool IsMaximumOrAbove(RangeSize size) const {
205 return IsPositiveInfinity() ||
206 (IsConstant() && (ConstantValue() >=
207 RangeBoundary::MaxConstant(size).ConstantValue()));
208 }
209
210 intptr_t kind() const { return kind_; }
211
212 // Kind tests.
213 bool IsUnknown() const { return kind_ == kUnknown; }
214 bool IsConstant() const { return kind_ == kConstant; }
215 bool IsSymbol() const { return kind_ == kSymbol; }
216 bool IsNegativeInfinity() const { return kind_ == kNegativeInfinity; }
217 bool IsPositiveInfinity() const { return kind_ == kPositiveInfinity; }
218 bool IsInfinity() const {
219 return IsNegativeInfinity() || IsPositiveInfinity();
220 }
221 bool IsConstantOrInfinity() const { return IsConstant() || IsInfinity(); }
222
223 // Returns the value of a kConstant RangeBoundary.
224 int64_t ConstantValue() const;
225
226 // Returns the Definition associated with a kSymbol RangeBoundary.
227 Definition* symbol() const {
228 ASSERT(IsSymbol());
229 return reinterpret_cast<Definition*>(value_);
230 }
231
232 // Offset from symbol.
233 int64_t offset() const { return offset_; }
234
235 // Computes the LowerBound of this. Three cases:
236 // IsInfinity() -> NegativeInfinity().
237 // IsConstant() -> value().
238 // IsSymbol() -> lower bound computed from definition + offset.
239 RangeBoundary LowerBound() const;
240
241 // Computes the UpperBound of this. Three cases:
242 // IsInfinity() -> PositiveInfinity().
243 // IsConstant() -> value().
244 // IsSymbol() -> upper bound computed from definition + offset.
245 RangeBoundary UpperBound() const;
246
247 void PrintTo(BaseTextBuffer* f) const;
248 const char* ToCString() const;
249 SExpression* ToSExpression(FlowGraphSerializer* s);
250
251 static RangeBoundary Add(const RangeBoundary& a,
252 const RangeBoundary& b,
253 const RangeBoundary& overflow);
254
255 static RangeBoundary Sub(const RangeBoundary& a,
256 const RangeBoundary& b,
257 const RangeBoundary& overflow);
258
259 static RangeBoundary Shl(const RangeBoundary& value_boundary,
260 int64_t shift_count,
261 const RangeBoundary& overflow);
262
263 static RangeBoundary Shr(const RangeBoundary& value_boundary,
264 int64_t shift_count) {
265 ASSERT(value_boundary.IsConstant());
266 ASSERT(shift_count >= 0);
267 const int64_t value = static_cast<int64_t>(value_boundary.ConstantValue());
268 const int64_t result = (shift_count <= 63)
269 ? (value >> shift_count)
270 : (value >= 0 ? 0 : -1); // Dart semantics
271 return RangeBoundary(result);
272 }
273
274 // Attempts to calculate a + b when:
275 // a is a symbol and b is a constant OR
276 // a is a constant and b is a symbol
277 // returns true if it succeeds, output is in result.
278 static bool SymbolicAdd(const RangeBoundary& a,
279 const RangeBoundary& b,
280 RangeBoundary* result);
281
282 // Attempts to calculate a - b when:
283 // a is a symbol and b is a constant
284 // returns true if it succeeds, output is in result.
285 static bool SymbolicSub(const RangeBoundary& a,
286 const RangeBoundary& b,
287 RangeBoundary* result);
288
289 bool Equals(const RangeBoundary& other) const;
290
291 int64_t UpperBound(RangeSize size) const {
292 return UpperBound().Clamp(size).ConstantValue();
293 }
294
295 int64_t LowerBound(RangeSize size) const {
296 return LowerBound().Clamp(size).ConstantValue();
297 }
298
299 int64_t SmiUpperBound() const { return UpperBound(kRangeBoundarySmi); }
300
301 int64_t SmiLowerBound() const { return LowerBound(kRangeBoundarySmi); }
302
303 private:
304 friend class FlowGraphDeserializer; // For setting fields directly.
305
306 RangeBoundary(Kind kind, int64_t value, int64_t offset)
307 : kind_(kind), value_(value), offset_(offset) {}
308
309 Kind kind_;
310 int64_t value_;
311 int64_t offset_;
312};
313
314class Range : public ZoneAllocated {
315 public:
316 Range() : min_(), max_() {}
317
318 Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) {
319 ASSERT(min_.IsUnknown() == max_.IsUnknown());
320
321 if (min_.IsInfinity() || max_.IsInfinity()) {
322 // Value can wrap around, so fall back to the full 64-bit range.
323 SetInt64Range();
324 }
325 }
326
327 Range(const Range& other)
328 : ZoneAllocated(), min_(other.min_), max_(other.max_) {}
329
330 Range& operator=(const Range& other) {
331 min_ = other.min_;
332 max_ = other.max_;
333 return *this;
334 }
335
336 static bool IsUnknown(const Range* other) {
337 if (other == NULL) {
338 return true;
339 }
340 return other->min().IsUnknown();
341 }
342
343 static Range Full(RangeBoundary::RangeSize size) {
344 return Range(RangeBoundary::MinConstant(size),
345 RangeBoundary::MaxConstant(size));
346 }
347
348 void PrintTo(BaseTextBuffer* f) const;
349 static const char* ToCString(const Range* range);
350 SExpression* ToSExpression(FlowGraphSerializer* s);
351
352 bool Equals(const Range* other) {
353 ASSERT(min_.IsUnknown() == max_.IsUnknown());
354 if (other == NULL) {
355 return min_.IsUnknown();
356 }
357 return min_.Equals(other->min_) && max_.Equals(other->max_);
358 }
359
360 const RangeBoundary& min() const { return min_; }
361 const RangeBoundary& max() const { return max_; }
362
363 void set_min(const RangeBoundary& value) {
364 min_ = value;
365
366 if (min_.IsInfinity()) {
367 // Value can wrap around, so fall back to the full 64-bit range.
368 SetInt64Range();
369 }
370 }
371
372 void set_max(const RangeBoundary& value) {
373 max_ = value;
374
375 if (max_.IsInfinity()) {
376 // Value can wrap around, so fall back to the full 64-bit range.
377 SetInt64Range();
378 }
379 }
380
381 static RangeBoundary ConstantMinSmi(const Range* range) {
382 return ConstantMin(range, RangeBoundary::kRangeBoundarySmi);
383 }
384
385 static RangeBoundary ConstantMaxSmi(const Range* range) {
386 return ConstantMax(range, RangeBoundary::kRangeBoundarySmi);
387 }
388
389 static RangeBoundary ConstantMin(const Range* range) {
390 return ConstantMin(range, RangeBoundary::kRangeBoundaryInt64);
391 }
392
393 static RangeBoundary ConstantMax(const Range* range) {
394 return ConstantMax(range, RangeBoundary::kRangeBoundaryInt64);
395 }
396
397 static RangeBoundary ConstantMin(const Range* range,
398 RangeBoundary::RangeSize size) {
399 if (range == NULL) {
400 return RangeBoundary::MinConstant(size);
401 }
402 return range->min().LowerBound().Clamp(size);
403 }
404
405 static RangeBoundary ConstantMax(const Range* range,
406 RangeBoundary::RangeSize size) {
407 if (range == NULL) {
408 return RangeBoundary::MaxConstant(size);
409 }
410 return range->max().UpperBound().Clamp(size);
411 }
412
413 // [0, +inf]
414 bool IsPositive() const;
415
416 // [-inf, val].
417 bool OnlyLessThanOrEqualTo(int64_t val) const;
418
419 // [val, +inf].
420 bool OnlyGreaterThanOrEqualTo(int64_t val) const;
421
422 // Inclusive.
423 bool IsWithin(int64_t min_int, int64_t max_int) const;
424
425 // Inclusive.
426 bool Overlaps(int64_t min_int, int64_t max_int) const;
427
428 bool IsUnsatisfiable() const;
429
430 bool IsFinite() const { return !min_.IsInfinity() && !max_.IsInfinity(); }
431
432 Range Intersect(const Range* other) const {
433 return Range(RangeBoundary::IntersectionMin(min(), other->min()),
434 RangeBoundary::IntersectionMax(max(), other->max()));
435 }
436
437 bool Fits(RangeBoundary::RangeSize size) const {
438 return !min().LowerBound().Overflowed(size) &&
439 !max().UpperBound().Overflowed(size);
440 }
441
442 // Clamp this to be within size.
443 void Clamp(RangeBoundary::RangeSize size);
444
445 // Clamp this to be within size and eliminate symbols.
446 void ClampToConstant(RangeBoundary::RangeSize size);
447
448 static void Add(const Range* left_range,
449 const Range* right_range,
450 RangeBoundary* min,
451 RangeBoundary* max,
452 Definition* left_defn);
453
454 static void Sub(const Range* left_range,
455 const Range* right_range,
456 RangeBoundary* min,
457 RangeBoundary* max,
458 Definition* left_defn);
459
460 static void Mul(const Range* left_range,
461 const Range* right_range,
462 RangeBoundary* min,
463 RangeBoundary* max);
464
465 static void TruncDiv(const Range* left_range,
466 const Range* right_range,
467 RangeBoundary* min,
468 RangeBoundary* max);
469
470 static void Mod(const Range* right_range,
471 RangeBoundary* min,
472 RangeBoundary* max);
473
474 static void Shr(const Range* left_range,
475 const Range* right_range,
476 RangeBoundary* min,
477 RangeBoundary* max);
478
479 static void Shl(const Range* left_range,
480 const Range* right_range,
481 RangeBoundary* min,
482 RangeBoundary* max);
483
484 static void And(const Range* left_range,
485 const Range* right_range,
486 RangeBoundary* min,
487 RangeBoundary* max);
488
489 static void BitwiseOp(const Range* left_range,
490 const Range* right_range,
491 RangeBoundary* min,
492 RangeBoundary* max);
493
494 // Both the a and b ranges are >= 0.
495 static bool OnlyPositiveOrZero(const Range& a, const Range& b);
496
497 // Both the a and b ranges are <= 0.
498 static bool OnlyNegativeOrZero(const Range& a, const Range& b);
499
500 // Return the maximum absolute value included in range.
501 static int64_t ConstantAbsMax(const Range* range);
502
503 // Return the minimum absolute value included in range.
504 static int64_t ConstantAbsMin(const Range* range);
505
506 static void BinaryOp(const Token::Kind op,
507 const Range* left_range,
508 const Range* right_range,
509 Definition* left_defn,
510 Range* result);
511
512 private:
513 friend class FlowGraphDeserializer; // For setting min_/max_ directly.
514
515 RangeBoundary min_;
516 RangeBoundary max_;
517
518 void SetInt64Range() {
519 min_ = RangeBoundary::MinConstant(RangeBoundary::kRangeBoundaryInt64);
520 max_ = RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundaryInt64);
521 }
522};
523
524class RangeUtils : public AllStatic {
525 public:
526 static bool Fits(Range* range, RangeBoundary::RangeSize size) {
527 return !Range::IsUnknown(range) && range->Fits(size);
528 }
529
530 static bool IsWithin(Range* range, int64_t min, int64_t max) {
531 return !Range::IsUnknown(range) && range->IsWithin(min, max);
532 }
533
534 static bool IsPositive(Range* range) {
535 return !Range::IsUnknown(range) && range->IsPositive();
536 }
537
538 static bool Overlaps(Range* range, intptr_t min, intptr_t max) {
539 return Range::IsUnknown(range) || range->Overlaps(min, max);
540 }
541
542 static bool CanBeZero(Range* range) { return Overlaps(range, 0, 0); }
543
544 static bool OnlyLessThanOrEqualTo(Range* range, intptr_t value) {
545 return !Range::IsUnknown(range) && range->OnlyLessThanOrEqualTo(value);
546 }
547};
548
549// Range analysis for integer values.
550class RangeAnalysis : public ValueObject {
551 public:
552 explicit RangeAnalysis(FlowGraph* flow_graph)
553 : flow_graph_(flow_graph),
554 smi_range_(Range::Full(RangeBoundary::kRangeBoundarySmi)),
555 int64_range_(Range::Full(RangeBoundary::kRangeBoundaryInt64)) {}
556
557 // Infer ranges for all values and remove overflow checks from binary smi
558 // operations when proven redundant.
559 void Analyze();
560
561 // Helper that should be used to access ranges of inputs during range
562 // inference.
563 // Returns meaningful results for uses of non-smi/non-int definitions that
564 // have smi/int as a reaching type.
565 const Range* GetSmiRange(Value* value) const;
566 const Range* GetIntRange(Value* value) const;
567
568 static bool IsIntegerDefinition(Definition* defn) {
569 return defn->Type()->IsInt();
570 }
571
572 void AssignRangesRecursively(Definition* defn);
573
574 private:
575 enum JoinOperator { NONE, WIDEN, NARROW };
576 static char OpPrefix(JoinOperator op);
577
578 // Collect all integer values (smi or int), all 64-bit binary
579 // and shift operations, and all check bounds.
580 void CollectValues();
581
582 // Iterate over smi values and constrain them at branch successors.
583 // Additionally constraint values after CheckSmi instructions.
584 void InsertConstraints();
585
586 // Iterate over uses of the given definition and discover branches that
587 // constrain it. Insert appropriate Constraint instructions at true
588 // and false successor and rename all dominated uses to refer to a
589 // Constraint instead of this definition.
590 void InsertConstraintsFor(Definition* defn);
591
592 // Create a constraint for defn, insert it after given instruction and
593 // rename all uses that are dominated by it.
594 ConstraintInstr* InsertConstraintFor(Value* use,
595 Definition* defn,
596 Range* constraint,
597 Instruction* after);
598
599 bool ConstrainValueAfterBranch(Value* use, Definition* defn);
600 void ConstrainValueAfterCheckBound(Value* use,
601 CheckBoundBase* check,
602 Definition* defn);
603
604 // Infer ranges for integer (smi or mint) definitions.
605 void InferRanges();
606
607 // Collect integer definition in the reverse postorder.
608 void CollectDefinitions(BitVector* set);
609
610 // Recompute ranges of all definitions until they stop changing.
611 // Apply the given JoinOperator when computing Phi ranges.
612 void Iterate(JoinOperator op, intptr_t max_iterations);
613 bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
614
615 // Based on computed ranges find and eliminate redundant CheckArrayBound
616 // instructions.
617 void EliminateRedundantBoundsChecks();
618
619 // Find unsatisfiable constraints and mark corresponding blocks unreachable.
620 void MarkUnreachableBlocks();
621
622 // Convert mint operations that stay within int32 range into Int32 operations.
623 void NarrowMintToInt32();
624
625 // Remove artificial Constraint instructions and replace them with actual
626 // unconstrained definitions.
627 void RemoveConstraints();
628
629 Range* ConstraintSmiRange(Token::Kind op, Definition* boundary);
630
631 Zone* zone() const { return flow_graph_->zone(); }
632
633 FlowGraph* flow_graph_;
634
635 // Range object representing full Smi range.
636 Range smi_range_;
637
638 Range int64_range_;
639
640 // All values that are known to be smi or mint.
641 GrowableArray<Definition*> values_;
642
643 // All 64-bit binary and shift operations.
644 GrowableArray<BinaryInt64OpInstr*> binary_int64_ops_;
645 GrowableArray<ShiftIntegerOpInstr*> shift_int64_ops_;
646
647 // All CheckArrayBound/GenericCheckBound instructions.
648 GrowableArray<CheckBoundBase*> bounds_checks_;
649
650 // All Constraints inserted during InsertConstraints phase. They are treated
651 // as smi values.
652 GrowableArray<ConstraintInstr*> constraints_;
653
654 // List of integer (smi or mint) definitions including constraints sorted
655 // in the reverse postorder.
656 GrowableArray<Definition*> definitions_;
657
658 DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
659};
660
661// Replaces Mint IL instructions with Uint32 IL instructions
662// when possible. Uses output of RangeAnalysis.
663class IntegerInstructionSelector : public ValueObject {
664 public:
665 explicit IntegerInstructionSelector(FlowGraph* flow_graph);
666
667 void Select();
668
669 private:
670 bool IsPotentialUint32Definition(Definition* def);
671 void FindPotentialUint32Definitions();
672 bool IsUint32NarrowingDefinition(Definition* def);
673 void FindUint32NarrowingDefinitions();
674 bool AllUsesAreUint32Narrowing(Value* list_head);
675 bool CanBecomeUint32(Definition* def);
676 void Propagate();
677 Definition* ConstructReplacementFor(Definition* def);
678 void ReplaceInstructions();
679
680 Zone* zone() const { return zone_; }
681
682 GrowableArray<Definition*> potential_uint32_defs_;
683 BitVector* selected_uint32_defs_;
684
685 FlowGraph* flow_graph_;
686 Zone* zone_;
687};
688
689} // namespace dart
690
691#endif // RUNTIME_VM_COMPILER_BACKEND_RANGE_ANALYSIS_H_
692