5#ifndef RUNTIME_VM_COMPILER_BACKEND_RANGE_ANALYSIS_H_
6#define RUNTIME_VM_COMPILER_BACKEND_RANGE_ANALYSIS_H_
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
19#define FOR_EACH_RANGE_BOUNDARY_KIND(V) \
24#define KIND_DEFN(name) k##name,
42 offset_(other.offset_) {}
45 : kind_(kConstant), value_(val), offset_(0) {}
49 value_ = other.value_;
50 offset_ = other.offset_;
188 intptr_t
kind()
const {
return kind_; }
205 int64_t
offset()
const {
return offset_; }
231 int64_t shift_count);
234 int64_t shift_count);
295 if (other ==
nullptr) {
313 if (other ==
nullptr) {
316 return min_.
Equals(other->min_) && max_.
Equals(other->max_);
344 if (range ==
nullptr) {
352 if (range ==
nullptr) {
371 bool IsWithin(int64_t min_int, int64_t max_int)
const;
377 bool Overlaps(int64_t min_int, int64_t max_int)
const;
404 if (range ==
nullptr)
return false;
416 static void Add(
const Range* left_range,
417 const Range* right_range,
422 static void Sub(
const Range* left_range,
423 const Range* right_range,
428 static void Mul(
const Range* left_range,
429 const Range* right_range,
434 const Range* right_range,
438 static void Mod(
const Range* right_range,
442 static void Shr(
const Range* left_range,
443 const Range* right_range,
447 static void Ushr(
const Range* left_range,
448 const Range* right_range,
452 static void Shl(
const Range* left_range,
453 const Range* right_range,
457 static void And(
const Range* left_range,
458 const Range* right_range,
463 const Range* right_range,
480 const Range* left_range,
481 const Range* right_range,
533 : flow_graph_(flow_graph),
555 enum JoinOperator { NONE, WIDEN, NARROW };
556 static char OpPrefix(JoinOperator op);
560 void CollectValues();
564 void InsertConstraints();
570 void InsertConstraintsFor(Definition* defn);
574 ConstraintInstr* InsertConstraintFor(
Value* use,
579 bool ConstrainValueAfterBranch(
Value* use, Definition* defn);
580 void ConstrainValueAfterCheckBound(
Value* use,
581 CheckBoundBaseInstr*
check,
588 void CollectDefinitions(BitVector* set);
592 void Iterate(JoinOperator op, intptr_t max_iterations);
593 bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
597 void EliminateRedundantBoundsChecks();
600 void MarkUnreachableBlocks();
603 void NarrowMintToInt32();
607 void RemoveConstraints();
609 Range* ConstraintSmiRange(
Token::Kind op, Definition* boundary);
611 Zone* zone()
const {
return flow_graph_->
zone(); }
613 FlowGraph* flow_graph_;
621 GrowableArray<Definition*> values_;
624 GrowableArray<BinaryInt64OpInstr*> binary_int64_ops_;
625 GrowableArray<ShiftIntegerOpInstr*> shift_int64_ops_;
628 GrowableArray<CheckBoundBaseInstr*> bounds_checks_;
632 GrowableArray<ConstraintInstr*> constraints_;
636 GrowableArray<Definition*> definitions_;
650 bool IsPotentialUint32Definition(
Definition* def);
651 void FindPotentialUint32Definitions();
652 bool IsUint32NarrowingDefinition(
Definition* def);
653 void FindUint32NarrowingDefinitions();
654 bool AllUsesAreUint32Narrowing(
Value* list_head);
658 void ReplaceInstructions();
660 Zone* zone()
const {
return zone_; }
#define check(reporter, ref, unref, make, kill)
void AssignRangesRecursively(Definition *defn)
const Range * GetIntRange(Value *value) const
static bool IsIntegerDefinition(Definition *defn)
const Range * GetSmiRange(Value *value) const
RangeAnalysis(FlowGraph *flow_graph)
RangeBoundary(int64_t val)
int64_t UpperBound(RangeSize size) const
bool Equals(const RangeBoundary &other) const
bool OverflowedSmi() const
static bool WillSubOverflow(const RangeBoundary &a, const RangeBoundary &b)
static RangeBoundary FromDefinition(Definition *defn, int64_t offs=0)
@ FOR_EACH_RANGE_BOUNDARY_KIND
void Write(FlowGraphSerializer *s) const
int64_t SmiLowerBound() const
int64_t SmiUpperBound() const
static RangeBoundary MaxSmi()
RangeBoundary Clamp(RangeSize size) const
static bool SymbolicAdd(const RangeBoundary &a, const RangeBoundary &b, RangeBoundary *result)
static bool IsValidOffsetForSymbolicRangeBoundary(int64_t offset)
int64_t LowerBound(RangeSize size) const
bool IsMaximumOrAbove(RangeSize size) const
static bool WillAddOverflow(const RangeBoundary &a, const RangeBoundary &b)
static RangeBoundary MinConstant(RangeSize size)
static RangeBoundary Add(const RangeBoundary &a, const RangeBoundary &b)
RangeBoundary UpperBound() const
static constexpr int64_t kMin
static RangeBoundary JoinMax(RangeBoundary a, RangeBoundary b, RangeBoundary::RangeSize size)
RangeBoundary LowerBound() const
static bool SymbolicSub(const RangeBoundary &a, const RangeBoundary &b, RangeBoundary *result)
static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b)
static RangeBoundary MinSmi()
static RangeBoundary Shr(const RangeBoundary &value_boundary, int64_t shift_count)
static RangeBoundary IntersectionMax(RangeBoundary a, RangeBoundary b)
int64_t ConstantValue() const
static RangeBoundary JoinMin(RangeBoundary a, RangeBoundary b, RangeBoundary::RangeSize size)
static constexpr int64_t kMax
static RangeBoundary Sub(const RangeBoundary &a, const RangeBoundary &b)
RangeBoundary & operator=(const RangeBoundary &other)
RangeBoundary(const RangeBoundary &other)
static RangeBoundary Shl(const RangeBoundary &value_boundary, int64_t shift_count)
static RangeBoundary MaxConstant(RangeSize size)
static bool WillShlOverflow(const RangeBoundary &a, int64_t shift_count)
const char * ToCString() const
void PrintTo(BaseTextBuffer *f) const
bool Overflowed(RangeBoundary::RangeSize size) const
bool IsMinimumOrBelow(RangeSize size) const
static RangeBoundary FromConstant(int64_t val)
Definition * symbol() const
static bool IsSingleton(Range *range)
static bool IsNegative(Range *range)
static bool Overlaps(Range *range, intptr_t min, intptr_t max)
static bool OnlyLessThanOrEqualTo(Range *range, intptr_t value)
static bool Fits(Range *range, RangeBoundary::RangeSize size)
static bool IsWithin(const Range *range, int64_t min, int64_t max)
static bool IsPositive(Range *range)
static bool CanBeZero(Range *range)
static bool IsWithin(const Range *range, const Range *other)
static RangeBoundary ConstantMinSmi(const Range *range)
static int64_t ConstantAbsMax(const Range *range)
static bool OnlyNegativeOrZero(const Range &a, const Range &b)
static void BitwiseOp(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
static const char * ToCString(const Range *range)
void set_max(const RangeBoundary &value)
static RangeBoundary ConstantMin(const Range *range, RangeBoundary::RangeSize size)
static void Shr(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
static bool Fits(Range *range, Representation rep)
static RangeBoundary ConstantMaxSmi(const Range *range)
bool IsWithin(int64_t min_int, int64_t max_int) const
Range Intersect(const Range *other) const
void ClampToConstant(RangeBoundary::RangeSize size)
Range & operator=(const Range &other)
static void Mul(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
Range(RangeBoundary min, RangeBoundary max)
static bool OnlyPositiveOrZero(const Range &a, const Range &b)
static bool IsUnknown(const Range *other)
static void TruncDiv(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
static void Ushr(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
const RangeBoundary & min() const
bool IsUnsatisfiable() const
bool Fits(RangeBoundary::RangeSize size) const
static void BinaryOp(const Token::Kind op, const Range *left_range, const Range *right_range, Definition *left_defn, Range *result)
const RangeBoundary & max() const
Range(const Range &other)
static void Add(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max, Definition *left_defn)
static void And(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
static Range Full(RangeBoundary::RangeSize size)
static void Sub(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max, Definition *left_defn)
void Clamp(RangeBoundary::RangeSize size)
static RangeBoundary ConstantMax(const Range *range, RangeBoundary::RangeSize size)
void Write(FlowGraphSerializer *s) const
static void Shl(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
bool Equals(const Range *other)
bool OnlyGreaterThanOrEqualTo(int64_t val) const
static RangeBoundary ConstantMin(const Range *range)
void set_min(const RangeBoundary &value)
static void Mod(const Range *right_range, RangeBoundary *min, RangeBoundary *max)
void PrintTo(BaseTextBuffer *f) const
bool OnlyLessThanOrEqualTo(int64_t val) const
static RangeBoundary ConstantMax(const Range *range)
bool Overlaps(int64_t min_int, int64_t max_int) const
static int64_t ConstantAbsMin(const Range *range)
int64_t Singleton() const
VULKAN_HPP_DEFAULT_DISPATCH_LOADER_DYNAMIC_STORAGE auto & d
static float max(float r, float g, float b)
static float min(float r, float g, float b)
constexpr int16_t kMaxInt16
constexpr int64_t kMaxInt64
constexpr int64_t kMinInt64
constexpr int32_t kMinInt32
constexpr int8_t kMaxInt8
constexpr int32_t kMaxInt32
constexpr int16_t kMinInt16
constexpr int8_t kMinInt8
static constexpr bool IsUnboxedInteger(Representation rep)