25#undef KIND_DEFN
26
27 enum RangeSize {
28 kRangeBoundarySmi,
29 kRangeBoundaryInt8,
30 kRangeBoundaryInt16,
31 kRangeBoundaryInt32,
32 kRangeBoundaryInt64,
33 };
34
35 RangeBoundary() : kind_(
kUnknown), value_(0), offset_(0) {}
36
37 RangeBoundary(const RangeBoundary& other)
38 : ValueObject(),
39 kind_(other.kind_),
40 value_(other.value_),
41 offset_(other.offset_) {}
42
43 explicit RangeBoundary(int64_t val)
44 : kind_(kConstant), value_(val), offset_(0) {}
45
46 RangeBoundary& operator=(const RangeBoundary& other) {
47 kind_ = other.kind_;
48 value_ = other.value_;
49 offset_ = other.offset_;
50 return *this;
51 }
52
53 static constexpr int64_t kMin =
kMinInt64;
55
56
57 static RangeBoundary FromConstant(int64_t val) { return RangeBoundary(val); }
58
59
60 static RangeBoundary FromDefinition(Definition* defn, int64_t offs = 0);
61
62 static bool IsValidOffsetForSymbolicRangeBoundary(int64_t
offset) {
63 if ((
offset > (kMaxInt64 - compiler::target::kSmiMax)) ||
64 (
offset < (kMinInt64 - compiler::target::kSmiMin))) {
65
66 return false;
67 }
68 return true;
69 }
70
71
72 static RangeBoundary MinSmi() {
73 return FromConstant(compiler::target::kSmiMin);
74 }
75
76
77 static RangeBoundary MaxSmi() {
78 return FromConstant(compiler::target::kSmiMax);
79 }
80
81
82 static RangeBoundary MinConstant(RangeSize size) {
83 switch (size) {
84 case kRangeBoundarySmi:
85 return FromConstant(compiler::target::kSmiMin);
86 case kRangeBoundaryInt8:
87 return FromConstant(kMinInt8);
88 case kRangeBoundaryInt16:
89 return FromConstant(kMinInt16);
90 case kRangeBoundaryInt32:
91 return FromConstant(kMinInt32);
92 case kRangeBoundaryInt64:
93 return FromConstant(kMinInt64);
94 }
96 return FromConstant(kMinInt64);
97 }
98
99 static RangeBoundary MaxConstant(RangeSize size) {
100 switch (size) {
101 case kRangeBoundarySmi:
102 return FromConstant(compiler::target::kSmiMax);
103 case kRangeBoundaryInt8:
104 return FromConstant(kMaxInt8);
105 case kRangeBoundaryInt16:
106 return FromConstant(kMaxInt16);
107 case kRangeBoundaryInt32:
108 return FromConstant(kMaxInt32);
109 case kRangeBoundaryInt64:
110 return FromConstant(kMaxInt64);
111 }
113 return FromConstant(kMaxInt64);
114 }
115
116
117
118
119
120 static RangeBoundary IntersectionMin(RangeBoundary
a, RangeBoundary
b);
121
122
123
124
125
126 static RangeBoundary IntersectionMax(RangeBoundary
a, RangeBoundary
b);
127
128
129
130
131
132
133
134 static RangeBoundary JoinMin(RangeBoundary
a,
136 RangeBoundary::RangeSize size);
137
138
139
140
141
142
143
144 static RangeBoundary JoinMax(RangeBoundary
a,
146 RangeBoundary::RangeSize size);
147
148
149 bool OverflowedSmi() const {
150 return IsConstant() && !compiler::target::IsSmi(ConstantValue());
151 }
152
153 bool Overflowed(RangeBoundary::RangeSize size) const {
155 return !
Equals(Clamp(size));
156 }
157
158
159 RangeBoundary Clamp(RangeSize size) const {
160 if (IsConstant()) {
161 const RangeBoundary range_min = RangeBoundary::MinConstant(size);
162 const RangeBoundary range_max = RangeBoundary::MaxConstant(size);
163
164 if (ConstantValue() <= range_min.ConstantValue()) {
165 return range_min;
166 }
167 if (ConstantValue() >= range_max.ConstantValue()) {
168 return range_max;
169 }
170 }
171
172
173
174 return *this;
175 }
176
177 bool IsMinimumOrBelow(RangeSize size) const {
178 return IsConstant() && (ConstantValue() <=
179 RangeBoundary::MinConstant(size).ConstantValue());
180 }
181
182 bool IsMaximumOrAbove(RangeSize size) const {
183 return IsConstant() && (ConstantValue() >=
184 RangeBoundary::MaxConstant(size).ConstantValue());
185 }
186
187 intptr_t kind() const { return kind_; }
188
189
190 bool IsUnknown()
const {
return kind_ ==
kUnknown; }
191 bool IsConstant() const { return kind_ == kConstant; }
192 bool IsSymbol() const { return kind_ == kSymbol; }
193
194
195 int64_t ConstantValue() const;
196
197
198 Definition* symbol() const {
200 return reinterpret_cast<Definition*>(value_);
201 }
202
203
204 int64_t
offset()
const {
return offset_; }
205
206
207
208
209 RangeBoundary LowerBound() const;
210
211
212
213
214 RangeBoundary UpperBound() const;
215
216 void PrintTo(BaseTextBuffer* f)
const;
217 const char* ToCString() const;
218
219 static bool WillAddOverflow(
const RangeBoundary&
a,
const RangeBoundary&
b);
220
221 static RangeBoundary Add(
const RangeBoundary&
a,
const RangeBoundary&
b);
222
223 static bool WillSubOverflow(
const RangeBoundary&
a,
const RangeBoundary&
b);
224
225 static RangeBoundary Sub(
const RangeBoundary&
a,
const RangeBoundary&
b);
226
227 static bool WillShlOverflow(
const RangeBoundary&
a, int64_t shift_count);
228
229 static RangeBoundary Shl(const RangeBoundary& value_boundary,
230 int64_t shift_count);
231
232 static RangeBoundary Shr(const RangeBoundary& value_boundary,
233 int64_t shift_count);
234
235
236
237
238
239 static bool SymbolicAdd(
const RangeBoundary&
a,
240 const RangeBoundary&
b,
242
243
244
245
246 static bool SymbolicSub(
const RangeBoundary&
a,
247 const RangeBoundary&
b,
249
250 bool Equals(
const RangeBoundary& other)
const;
251
252 int64_t UpperBound(RangeSize size) const {
253 return UpperBound().Clamp(size).ConstantValue();
254 }
255
256 int64_t LowerBound(RangeSize size) const {
257 return LowerBound().Clamp(size).ConstantValue();
258 }
259
260 int64_t SmiUpperBound() const { return UpperBound(kRangeBoundarySmi); }
261
262 int64_t SmiLowerBound() const { return LowerBound(kRangeBoundarySmi); }
263
264 void Write(FlowGraphSerializer*
s)
const;
265 explicit RangeBoundary(FlowGraphDeserializer*
d);
266
267 private:
268 RangeBoundary(
Kind kind, int64_t value, int64_t
offset)
270
272 int64_t value_;
273 int64_t offset_;
274};
275
276class Range : public ZoneAllocated {
277 public:
279
282 }
283
284 Range(const Range& other)
286
287 Range& operator=(const Range& other) {
290 return *this;
291 }
292
293 static bool IsUnknown(const Range* other) {
294 if (other == nullptr) {
295 return true;
296 }
297 return other->min().IsUnknown();
298 }
299
300 static Range Full(RangeBoundary::RangeSize size) {
301 return Range(RangeBoundary::MinConstant(size),
302 RangeBoundary::MaxConstant(size));
303 }
304
305 static Range Full(Representation rep);
306
307 void PrintTo(BaseTextBuffer* f)
const;
308 static const char* ToCString(const Range* range);
309
310 bool Equals(
const Range* other) {
312 if (other == nullptr) {
313 return min_.IsUnknown();
314 }
315 return min_.Equals(other->min_) &&
max_.Equals(other->max_);
316 }
317
318 const RangeBoundary&
min()
const {
return min_; }
319 const RangeBoundary&
max()
const {
return max_; }
320
321 void set_min(
const RangeBoundary& value) {
min_ =
value; }
322
323 void set_max(
const RangeBoundary& value) {
max_ =
value; }
324
325 static RangeBoundary ConstantMinSmi(const Range* range) {
326 return ConstantMin(range, RangeBoundary::kRangeBoundarySmi);
327 }
328
329 static RangeBoundary ConstantMaxSmi(const Range* range) {
330 return ConstantMax(range, RangeBoundary::kRangeBoundarySmi);
331 }
332
333 static RangeBoundary ConstantMin(const Range* range) {
334 return ConstantMin(range, RangeBoundary::kRangeBoundaryInt64);
335 }
336
337 static RangeBoundary ConstantMax(const Range* range) {
338 return ConstantMax(range, RangeBoundary::kRangeBoundaryInt64);
339 }
340
341 static RangeBoundary ConstantMin(const Range* range,
342 RangeBoundary::RangeSize size) {
343 if (range == nullptr) {
344 return RangeBoundary::MinConstant(size);
345 }
346 return range->min().LowerBound().Clamp(size);
347 }
348
349 static RangeBoundary ConstantMax(const Range* range,
350 RangeBoundary::RangeSize size) {
351 if (range == nullptr) {
352 return RangeBoundary::MaxConstant(size);
353 }
354 return range->max().UpperBound().Clamp(size);
355 }
356
357
358 bool IsPositive() const;
359
360
361 bool IsNegative() const;
362
363
364 bool OnlyLessThanOrEqualTo(int64_t val) const;
365
366
367 bool OnlyGreaterThanOrEqualTo(int64_t val) const;
368
369
370 bool IsWithin(int64_t min_int, int64_t max_int) const;
371
372
373 bool IsWithin(const Range* other) const;
374
375
376 bool Overlaps(int64_t min_int, int64_t max_int) const;
377
378 bool IsUnsatisfiable() const;
379
380 bool IsSingleton() const {
381 return min_.IsConstant() &&
max_.IsConstant() &&
382 min_.ConstantValue() ==
max_.ConstantValue();
383 }
384
385 int64_t Singleton() const {
387 return min_.ConstantValue();
388 }
389
390 Range Intersect(const Range* other) const {
391 return Range(RangeBoundary::IntersectionMin(
min(), other->min()),
392 RangeBoundary::IntersectionMax(
max(), other->max()));
393 }
394
395 bool Fits(RangeBoundary::RangeSize size) const {
396 return !
min().LowerBound().Overflowed(size) &&
397 !
max().UpperBound().Overflowed(size);
398 }
399
400
401
402 static bool Fits(Range* range, Representation rep) {
403 if (range == nullptr) return false;
404 if (!RepresentationUtils::IsUnboxedInteger(rep)) return false;
405 const Range& other = Range::Full(rep);
406 return range->IsWithin(&other);
407 }
408
409
410 void Clamp(RangeBoundary::RangeSize size);
411
412
413 void ClampToConstant(RangeBoundary::RangeSize size);
414
415 static void Add(const Range* left_range,
416 const Range* right_range,
419 Definition* left_defn);
420
421 static void Sub(const Range* left_range,
422 const Range* right_range,
425 Definition* left_defn);
426
427 static void Mul(const Range* left_range,
428 const Range* right_range,
431
432 static void TruncDiv(const Range* left_range,
433 const Range* right_range,
436
437 static void Mod(const Range* right_range,
440
441 static void Shr(const Range* left_range,
442 const Range* right_range,
445
446 static void Ushr(const Range* left_range,
447 const Range* right_range,
450
451 static void Shl(const Range* left_range,
452 const Range* right_range,
455
456 static void And(const Range* left_range,
457 const Range* right_range,
460
461 static void BitwiseOp(const Range* left_range,
462 const Range* right_range,
465
466
467 static bool OnlyPositiveOrZero(
const Range&
a,
const Range&
b);
468
469
470 static bool OnlyNegativeOrZero(
const Range&
a,
const Range&
b);
471
472
473 static int64_t ConstantAbsMax(const Range* range);
474
475
476 static int64_t ConstantAbsMin(const Range* range);
477
478 static void BinaryOp(const Token::Kind op,
479 const Range* left_range,
480 const Range* right_range,
481 Definition* left_defn,
483
484 void Write(FlowGraphSerializer*
s)
const;
485 explicit Range(FlowGraphDeserializer*
d);
486
487 private:
490};
491
492class RangeUtils : public AllStatic {
493 public:
494 static bool Fits(Range* range, RangeBoundary::RangeSize size) {
495 return !Range::IsUnknown(range) && range->Fits(size);
496 }
497
498 static bool IsWithin(
const Range* range, int64_t
min, int64_t
max) {
499 return !Range::IsUnknown(range) && range->IsWithin(
min,
max);
500 }
501
502 static bool IsWithin(const Range* range, const Range* other) {
503 return !Range::IsUnknown(range) && range->IsWithin(other);
504 }
505
506 static bool IsPositive(Range* range) {
507 return !Range::IsUnknown(range) && range->IsPositive();
508 }
509 static bool IsNegative(Range* range) {
510 return !Range::IsUnknown(range) && range->IsNegative();
511 }
512
513 static bool Overlaps(Range* range, intptr_t
min, intptr_t
max) {
514 return Range::IsUnknown(range) || range->Overlaps(
min,
max);
515 }
516
517 static bool CanBeZero(Range* range) { return Overlaps(range, 0, 0); }
518
519 static bool OnlyLessThanOrEqualTo(Range* range, intptr_t value) {
520 return !Range::IsUnknown(range) && range->OnlyLessThanOrEqualTo(value);
521 }
522
523 static bool IsSingleton(Range* range) {
524 return !Range::IsUnknown(range) && range->IsSingleton();
525 }
526};
527
528
529class RangeAnalysis : public ValueObject {
530 public:
531 explicit RangeAnalysis(FlowGraph* flow_graph)
532 : flow_graph_(flow_graph),
533 smi_range_(Range::Full(RangeBoundary::kRangeBoundarySmi)),
534 int64_range_(Range::Full(RangeBoundary::kRangeBoundaryInt64)) {}
535
536
537
538 void Analyze();
539
540
541
542
543
544 const Range* GetSmiRange(
Value* value)
const;
545 const Range* GetIntRange(
Value* value)
const;
546
547 static bool IsIntegerDefinition(Definition* defn) {
548 return defn->Type()->IsInt();
549 }
550
551 void AssignRangesRecursively(Definition* defn);
552
553 private:
554 enum JoinOperator { NONE, WIDEN, NARROW };
555 static char OpPrefix(JoinOperator op);
556
557
558
559 void CollectValues();
560
561
562
563 void InsertConstraints();
564
565
566
567
568
569 void InsertConstraintsFor(Definition* defn);
570
571
572
573 ConstraintInstr* InsertConstraintFor(
Value* use,
574 Definition* defn,
575 Range* constraint,
576 Instruction* after);
577
578 bool ConstrainValueAfterBranch(
Value* use, Definition* defn);
579 void ConstrainValueAfterCheckBound(
Value* use,
580 CheckBoundBaseInstr*
check,
581 Definition* defn);
582
583
584 void InferRanges();
585
586
587 void CollectDefinitions(BitVector* set);
588
589
590
591 void Iterate(JoinOperator op, intptr_t max_iterations);
592 bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
593
594
595
596 void EliminateRedundantBoundsChecks();
597
598
599 void MarkUnreachableBlocks();
600
601
602 void NarrowMintToInt32();
603
604
605
606 void RemoveConstraints();
607
608 Range* ConstraintSmiRange(Token::Kind op, Definition* boundary);
609
610 Zone* zone() const { return flow_graph_->zone(); }
611
612 FlowGraph* flow_graph_;
613
614
615 Range smi_range_;
616
617 Range int64_range_;
618
619
620 GrowableArray<Definition*> values_;
621
622
623 GrowableArray<BinaryInt64OpInstr*> binary_int64_ops_;
624 GrowableArray<ShiftIntegerOpInstr*> shift_int64_ops_;
625
626
627 GrowableArray<CheckBoundBaseInstr*> bounds_checks_;
628
629
630
631 GrowableArray<ConstraintInstr*> constraints_;
632
633
634
635 GrowableArray<Definition*> definitions_;
636
638};
639
640
641
642class IntegerInstructionSelector : public ValueObject {
643 public:
644 explicit IntegerInstructionSelector(FlowGraph* flow_graph);
645
646 void Select();
647
648 private:
649 bool IsPotentialUint32Definition(Definition* def);
650 void FindPotentialUint32Definitions();
651 bool IsUint32NarrowingDefinition(Definition* def);
652 void FindUint32NarrowingDefinitions();
653 bool AllUsesAreUint32Narrowing(
Value* list_head);
654 bool CanBecomeUint32(Definition* def);
655 void Propagate();
656 Definition* ConstructReplacementFor(Definition* def);
657 void ReplaceInstructions();
658
659 Zone* zone() const { return zone_; }
660
661 GrowableArray<Definition*> potential_uint32_defs_;
662 BitVector* selected_uint32_defs_;
663
664 FlowGraph* flow_graph_;
665 Zone* zone_;
666};
667
668}
669
670#endif
#define check(reporter, ref, unref, make, kill)
bool Equals(const SkPath &a, const SkPath &b)
VULKAN_HPP_DEFAULT_DISPATCH_LOADER_DYNAMIC_STORAGE auto & d
void PrintTo(FlValue *v, std::ostream *os)
static float max(float r, float g, float b)
static float min(float r, float g, float b)
constexpr int64_t kMaxInt64
constexpr int64_t kMinInt64
#define FOR_EACH_RANGE_BOUNDARY_KIND(V)