lib/Backend/IntBounds.cpp

//-------------------------------------------------------------------------------------------------------
// Copyright (C) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
//-------------------------------------------------------------------------------------------------------
#include "Backend.h"

#pragma region IntBounds

IntBounds::IntBounds(
    const IntConstantBounds &constantBounds,
    const bool wasConstantUpperBoundEstablishedExplicitly,
    JitArenaAllocator *const allocator)
    :
    constantLowerBound(constantBounds.LowerBound()),
    constantUpperBound(constantBounds.UpperBound()),
    wasConstantUpperBoundEstablishedExplicitly(wasConstantUpperBoundEstablishedExplicitly),
    relativeLowerBounds(allocator),
    relativeUpperBounds(allocator)
{
}

IntBounds *IntBounds::New(
    const IntConstantBounds &constantBounds,
    const bool wasConstantUpperBoundEstablishedExplicitly,
    JitArenaAllocator *const allocator)
{
    Assert(allocator);
    return JitAnew(allocator, IntBounds, constantBounds, wasConstantUpperBoundEstablishedExplicitly, allocator);
}

IntBounds *IntBounds::Clone() const
{
    JitArenaAllocator *const allocator = relativeLowerBounds.GetAllocator();
    return JitAnew(allocator, IntBounds, *this);
}

void IntBounds::Delete() const
{
    JitArenaAllocator *const allocator = relativeLowerBounds.GetAllocator();
    JitAdelete(allocator, const_cast<IntBounds *>(this));
}

void IntBounds::Verify() const
{
    Assert(this);
    Assert(constantLowerBound <= constantUpperBound);
    Assert(HasBounds());
}

bool IntBounds::HasBounds() const
{
    return constantLowerBound != IntConstMin || constantUpperBound != IntConstMax || RequiresIntBoundedValueInfo();
}

bool IntBounds::RequiresIntBoundedValueInfo(const ValueType valueType) const
{
    Assert(valueType.IsLikelyInt());
    return !valueType.IsInt() || RequiresIntBoundedValueInfo();
}

bool IntBounds::RequiresIntBoundedValueInfo() const
{
    return WasConstantUpperBoundEstablishedExplicitly() || relativeLowerBounds.Count() != 0 || relativeUpperBounds.Count() != 0;
}

int IntBounds::ConstantLowerBound() const
{
    return constantLowerBound;
}

int IntBounds::ConstantUpperBound() const
{
    return constantUpperBound;
}

IntConstantBounds IntBounds::ConstantBounds() const
{
    return IntConstantBounds(ConstantLowerBound(), ConstantUpperBound());
}

bool IntBounds::WasConstantUpperBoundEstablishedExplicitly() const
{
    return wasConstantUpperBoundEstablishedExplicitly;
}

const RelativeIntBoundSet &IntBounds::RelativeLowerBounds() const
{
    return relativeLowerBounds;
}

const RelativeIntBoundSet &IntBounds::RelativeUpperBounds() const
{
    return relativeUpperBounds;
}

void IntBounds::SetLowerBound(const int constantBound)
{
    if(constantLowerBound < constantBound && constantBound <= constantUpperBound)
        constantLowerBound = constantBound;
}

void IntBounds::SetLowerBound(const int constantBoundBase, const int offset)
{
    SetBound<true>(constantBoundBase, offset, false);
}

void IntBounds::SetUpperBound(const int constantBound, const bool wasEstablishedExplicitly)
{
    if(constantLowerBound <= constantBound && constantBound < constantUpperBound)
        constantUpperBound = constantBound;
    if(wasEstablishedExplicitly)
        wasConstantUpperBoundEstablishedExplicitly = true;
}

void IntBounds::SetUpperBound(const int constantBoundBase, const int offset, const bool wasEstablishedExplicitly)
{
    SetBound<false>(constantBoundBase, offset, wasEstablishedExplicitly);
}

template<bool Lower>
void IntBounds::SetBound(const int constantBoundBase, const int offset, const bool wasEstablishedExplicitly)
{
    int constantBound;
    if(offset == 0)
        constantBound = constantBoundBase;
    else if(Int32Math::Add(constantBoundBase, offset, &constantBound))
        return;

    if(Lower)
        SetLowerBound(constantBound);
    else
        SetUpperBound(constantBound, wasEstablishedExplicitly);
}

void IntBounds::SetLowerBound(
    const ValueNumber myValueNumber,
    const Value *const baseValue,
    const bool wasEstablishedExplicitly)
{
    SetLowerBound(myValueNumber, baseValue, 0, wasEstablishedExplicitly);
}

void IntBounds::SetLowerBound(
    const ValueNumber myValueNumber,
    const Value *const baseValue,
    const int offset,
    const bool wasEstablishedExplicitly)
{
    SetBound<true>(myValueNumber, baseValue, offset, wasEstablishedExplicitly);
}

void IntBounds::SetUpperBound(
    const ValueNumber myValueNumber,
    const Value *const baseValue,
    const bool wasEstablishedExplicitly)
{
    SetUpperBound(myValueNumber, baseValue, 0, wasEstablishedExplicitly);
}

void IntBounds::SetUpperBound(
    const ValueNumber myValueNumber,
    const Value *const baseValue,
    const int offset,
    const bool wasEstablishedExplicitly)
{
    SetBound<false>(myValueNumber, baseValue, offset, wasEstablishedExplicitly);
}

template<bool Lower>
void IntBounds::SetBound(
    const ValueNumber myValueNumber,
    const Value *const baseValue,
    const int offset,
    const bool wasEstablishedExplicitly)
{
    Assert(baseValue);
    Assert(baseValue->GetValueNumber() != myValueNumber);

    // Aggressively merge the constant lower or upper bound of the base value, adjusted by the offset
    ValueInfo const * const baseValueInfo = baseValue->GetValueInfo();
    int constantBoundBase = 0xCCCCCCCC;
    const bool success =
        Lower
            ? baseValueInfo->TryGetIntConstantLowerBound(&constantBoundBase, true)
            : baseValueInfo->TryGetIntConstantUpperBound(&constantBoundBase, true);
    Assert(success);
    const bool isBoundConstant = baseValueInfo->HasIntConstantValue();
    SetBound<Lower>(constantBoundBase, offset, wasEstablishedExplicitly && isBoundConstant);

    if(isBoundConstant)
        return;

    // If the base value has relative bounds, pull in the lower or upper bounds adjusted by the offset
    RelativeIntBoundSet &boundSet = Lower ? relativeLowerBounds : relativeUpperBounds;
    const RelativeIntBoundSet &oppositeBoundSet = Lower ? relativeUpperBounds : relativeLowerBounds;
    if(baseValueInfo->IsIntBounded())
    {
        const IntBounds *const baseValueBounds = baseValueInfo->AsIntBounded()->Bounds();
        const RelativeIntBoundSet &baseValueBoundSet =
            Lower ? baseValueBounds->relativeLowerBounds : baseValueBounds->relativeUpperBounds;
        for(auto it = baseValueBoundSet.GetIterator(); it.IsValid(); it.MoveNext())
        {
            ValueRelativeOffset bound(it.CurrentValue());
            if(bound.BaseValueNumber() == myValueNumber || !bound.Add(offset))
                continue;
            const ValueRelativeOffset *existingOppositeBound;
            if(oppositeBoundSet.TryGetReference(bound.BaseValueNumber(), &existingOppositeBound) &&
                (Lower ? bound.Offset() > existingOppositeBound->Offset() : bound.Offset() < existingOppositeBound->Offset()))
            {
                // This bound contradicts the existing opposite bound on the same base value number:
                //     - Setting a lower bound (base + offset) when (base + offset2) is an upper bound and (offset > offset2)
                //     - Setting an upper bound (base + offset) when (base + offset2) is a lower bound and (offset < offset2)
                continue;
            }
            ValueRelativeOffset *existingBound;
            if(boundSet.TryGetReference(bound.BaseValueNumber(), &existingBound))
                existingBound->Merge<Lower, true>(bound);
            else
                boundSet.Add(bound);
        }
    }

    // Set the base value as a relative bound
    const ValueRelativeOffset bound(baseValue, offset, wasEstablishedExplicitly);
    const ValueRelativeOffset *existingOppositeBound;
    if(oppositeBoundSet.TryGetReference(bound.BaseValueNumber(), &existingOppositeBound) &&
        (Lower ? offset > existingOppositeBound->Offset() : offset < existingOppositeBound->Offset()))
    {
        // This bound contradicts the existing opposite bound on the same base value number:
        //     - Setting a lower bound (base + offset) when (base + offset2) is an upper bound and (offset > offset2)
        //     - Setting an upper bound (base + offset) when (base + offset2) is a lower bound and (offset < offset2)
        return;
    }
    ValueRelativeOffset *existingBound;
    if(boundSet.TryGetReference(bound.BaseValueNumber(), &existingBound))
        existingBound->Merge<Lower, true>(bound);
    else
        boundSet.Add(bound);
}

bool IntBounds::SetIsNot(const int constantValue, const bool isExplicit)
{
    if(constantLowerBound == constantUpperBound)
        return false;

    Assert(constantLowerBound < constantUpperBound);
    if(constantValue == constantLowerBound)
    {
        ++constantLowerBound;
        return true;
    }
    if(constantValue == constantUpperBound)
    {
        --constantUpperBound;
        if(isExplicit)
            wasConstantUpperBoundEstablishedExplicitly = true;
        return true;
    }
    return false;
}

bool IntBounds::SetIsNot(const Value *const value, const bool isExplicit)
{
    Assert(value);

    ValueInfo const *const valueInfo = value->GetValueInfo();
    Assert(valueInfo->IsLikelyInt());

    int constantValue;
    bool changed;
    if(valueInfo->TryGetIntConstantValue(&constantValue, true))
    {
        changed = SetIsNot(constantValue, isExplicit);
        if(valueInfo->IsInt())
            return changed;
    }
    else
        changed = false;

    const ValueNumber valueNumber = value->GetValueNumber();
    ValueRelativeOffset *existingLowerBound = nullptr;
    const bool existingLowerBoundOffsetIsZero =
        relativeLowerBounds.TryGetReference(valueNumber, &existingLowerBound) && existingLowerBound->Offset() == 0;
    ValueRelativeOffset *existingUpperBound = nullptr;
    const bool existingUpperBoundOffsetIsZero =
        relativeUpperBounds.TryGetReference(valueNumber, &existingUpperBound) && existingUpperBound->Offset() == 0;
    if(existingLowerBoundOffsetIsZero == existingUpperBoundOffsetIsZero)
        return changed; // neither bound can be changed, or changing a bound would contradict the opposite bound
    if(existingLowerBoundOffsetIsZero)
        existingLowerBound->SetOffset(1);
    else
    {
        existingUpperBound->SetOffset(-1);
        if(isExplicit)
            existingUpperBound->SetWasEstablishedExplicitly();
    }
    return true;
}

bool IntBounds::IsGreaterThanOrEqualTo(const int constantValue, const int constantBoundBase, const int offset)
{
    if(offset == 0)
        return constantValue >= constantBoundBase;
    if(offset == 1)
        return constantValue > constantBoundBase;

    // use unsigned to avoid signed int overflow
    const int constantBound = (unsigned)constantBoundBase + (unsigned)offset;
    return
        offset >= 0
            ? constantBound >= constantBoundBase && constantValue >= constantBound
            : constantBound >= constantBoundBase || constantValue >= constantBound;
}

bool IntBounds::IsLessThanOrEqualTo(const int constantValue, const int constantBoundBase, const int offset)
{
    if(offset == 0)
        return constantValue <= constantBoundBase;
    if(offset == -1)
        return constantValue < constantBoundBase;

    // use unsigned to avoid signed int overflow
    const int constantBound = (unsigned)constantBoundBase + (unsigned)offset;
    return
        offset >= 0
            ? constantBound < constantBoundBase || constantValue <= constantBound
            : constantBound < constantBoundBase && constantValue <= constantBound;
}

bool IntBounds::IsGreaterThanOrEqualTo(const int constantBoundBase, const int offset) const
{
    return IsGreaterThanOrEqualTo(constantLowerBound, constantBoundBase, offset);
}

bool IntBounds::IsLessThanOrEqualTo(const int constantBoundBase, const int offset) const
{
    return IsLessThanOrEqualTo(constantUpperBound, constantBoundBase, offset);
}

bool IntBounds::IsGreaterThanOrEqualTo(const Value *const value, const int offset) const
{
    Assert(value);

    ValueInfo const * const valueInfo = value->GetValueInfo();
    int constantBoundBase = INT32_MAX;
    const bool success = valueInfo->TryGetIntConstantUpperBound(&constantBoundBase, true);
    Assert(success);
    if(IsGreaterThanOrEqualTo(constantBoundBase, offset))
        return true;

    if(valueInfo->HasIntConstantValue())
        return false;

    const ValueRelativeOffset *bound;
    return relativeLowerBounds.TryGetReference(value->GetValueNumber(), &bound) && bound->Offset() >= offset;
}

bool IntBounds::IsLessThanOrEqualTo(const Value *const value, const int offset) const
{
    Assert(value);

    ValueInfo const * const valueInfo = value->GetValueInfo();
    int constantBoundBase = INT32_MIN;
    const bool success = valueInfo->TryGetIntConstantLowerBound(&constantBoundBase, true);
    Assert(success);
    if(IsLessThanOrEqualTo(constantBoundBase, offset))
        return true;

    if(valueInfo->HasIntConstantValue())
        return false;

    const ValueRelativeOffset *bound;
    return relativeUpperBounds.TryGetReference(value->GetValueNumber(), &bound) && bound->Offset() <= offset;
}

const IntBounds *IntBounds::Add(
    const Value *const baseValue,
    const int n,
    const bool baseValueInfoIsPrecise,
    const IntConstantBounds &newConstantBounds,
    JitArenaAllocator *const allocator)
{
    Assert(baseValue);
    Assert(baseValue->GetValueInfo()->IsLikelyInt());
    Assert(!baseValue->GetValueInfo()->HasIntConstantValue());

    // Determine whether the new constant upper bound was established explicitly
    bool wasConstantUpperBoundEstablishedExplicitly = false;
    ValueInfo const * const baseValueInfo = baseValue->GetValueInfo();
    const IntBounds *const baseBounds = baseValueInfo->IsIntBounded() ? baseValueInfo->AsIntBounded()->Bounds() : nullptr;
    if(baseBounds && baseBounds->WasConstantUpperBoundEstablishedExplicitly())
    {
        int baseAdjustedConstantUpperBound;
        if(!Int32Math::Add(baseBounds->ConstantUpperBound(), n, &baseAdjustedConstantUpperBound) &&
            baseAdjustedConstantUpperBound == newConstantBounds.UpperBound())
        {
            wasConstantUpperBoundEstablishedExplicitly = true;
        }
    }

    // Create the new bounds. Don't try to determine the constant bounds by offsetting the current constant bounds, as loop
    // prepasses are conservative. Use the constant bounds that are passed in.
    IntBounds *const newBounds = New(newConstantBounds, wasConstantUpperBoundEstablishedExplicitly, allocator);

    // Adjust the relative bounds by the constant. The base value info would not be precise for instance, when we're in a loop
    // and the value was created before the loop or in a previous loop iteration.
    if(n < 0 && !baseValueInfoIsPrecise)
    {
        // Don't know the number of similar decreases in value that will take place
        Assert(newBounds->constantLowerBound == IntConstMin);
    }
    else if(baseBounds)
    {
        Assert(!baseBounds->relativeLowerBounds.ContainsKey(baseValue->GetValueNumber()));
        newBounds->relativeLowerBounds.Copy(&baseBounds->relativeLowerBounds);
        if(n != 0)
        {
            for(auto it = newBounds->relativeLowerBounds.GetIteratorWithRemovalSupport(); it.IsValid(); it.MoveNext())
            {
                ValueRelativeOffset &bound = it.CurrentValueReference();
                if(!bound.Add(n))
                    it.RemoveCurrent();
            }
        }
    }
    if(n > 0 && !baseValueInfoIsPrecise)
    {
        // Don't know the number of similar increases in value that will take place, so clear the relative upper bounds
        Assert(newBounds->constantUpperBound == IntConstMax);
    }
    else if(baseBounds)
    {
        Assert(!baseBounds->relativeUpperBounds.ContainsKey(baseValue->GetValueNumber()));
        newBounds->relativeUpperBounds.Copy(&baseBounds->relativeUpperBounds);
        if(n != 0)
        {
            for(auto it = newBounds->relativeUpperBounds.GetIteratorWithRemovalSupport(); it.IsValid(); it.MoveNext())
            {
                ValueRelativeOffset &bound = it.CurrentValueReference();
                if(!bound.Add(n))
                    it.RemoveCurrent();
            }
        }
    }

    // The result is equal to (baseValue +/- n), so set that as a relative lower and upper bound
    if(baseValueInfo->HasIntConstantValue())
        return newBounds;
    const ValueRelativeOffset bound(baseValue, n, true);
    if(n >= 0 || baseValueInfoIsPrecise)
        newBounds->relativeLowerBounds.Add(bound);
    if(n <= 0 || baseValueInfoIsPrecise)
        newBounds->relativeUpperBounds.Add(bound);
    return newBounds;
}

bool IntBounds::AddCannotOverflowBasedOnRelativeBounds(const int n) const
{
    Assert(n != 0);

    if(n >= 0)
    {
        const int maxBoundOffset = -n;
        for(auto it = relativeUpperBounds.GetIterator(); it.IsValid(); it.MoveNext())
        {
            // If (a < b), then (a + 1) cannot overflow
            const ValueRelativeOffset &bound = it.CurrentValue();
            if(bound.Offset() <= maxBoundOffset)
                return true;
        }
        return false;
    }

    return n != IntConstMin && SubCannotOverflowBasedOnRelativeBounds(-n);
}

bool IntBounds::SubCannotOverflowBasedOnRelativeBounds(const int n) const
{
    Assert(n != 0);

    if(n >= 0)
    {
        const int minBoundOffset = n;
        for(auto it = relativeLowerBounds.GetIterator(); it.IsValid(); it.MoveNext())
        {
            // If (a > b), then (a - 1) cannot overflow
            const ValueRelativeOffset &bound = it.CurrentValue();
            if(bound.Offset() >= minBoundOffset)
                return true;
        }
        return false;
    }

    return n != IntConstMin && AddCannotOverflowBasedOnRelativeBounds(-n);
}

const IntBounds *IntBounds::Merge(
    const Value *const bounds0Value,
    const IntBounds *const bounds0,
    const Value *const bounds1Value,
    const IntConstantBounds &constantBounds1)
{
    Assert(bounds0Value);
    bounds0->Verify();
    Assert(bounds1Value);

    const IntConstantBounds constantBounds(
        min(bounds0->ConstantLowerBound(), constantBounds1.LowerBound()),
        max(bounds0->ConstantUpperBound(), constantBounds1.UpperBound()));

    const ValueNumber bounds1ValueNumber = bounds1Value->GetValueNumber();
    const ValueRelativeOffset *commonLowerBound;
    if(!bounds0->relativeLowerBounds.TryGetReference(bounds1ValueNumber, &commonLowerBound))
        commonLowerBound = nullptr;
    const ValueRelativeOffset *commonUpperBound;
    if(!bounds0->relativeUpperBounds.TryGetReference(bounds1ValueNumber, &commonUpperBound))
        commonUpperBound = nullptr;

    if(constantBounds.LowerBound() == IntConstMin &&
        constantBounds.UpperBound() == IntConstMax &&
        !commonLowerBound &&
        !commonUpperBound)
    {
        return nullptr;
    }

    IntBounds *const mergedBounds = New(constantBounds, false, bounds0->relativeLowerBounds.GetAllocator());

    // A value is implicitly bounded by itself, so preserve and merge bounds where one value is bounded by the other
    if(bounds0Value->GetValueNumber() == bounds1ValueNumber)
        return mergedBounds;
    if(commonLowerBound)
    {
        ValueRelativeOffset mergedLowerBound(*commonLowerBound);
        if(constantBounds1.IsConstant())
            mergedLowerBound.MergeConstantValue<true, false>(constantBounds1.LowerBound());
        else
            mergedLowerBound.Merge<true, false>(ValueRelativeOffset(bounds1Value, true));
        mergedBounds->relativeLowerBounds.Add(mergedLowerBound);
    }
    if(commonUpperBound)
    {
        ValueRelativeOffset mergedUpperBound(*commonUpperBound);
        if(constantBounds1.IsConstant())
            mergedUpperBound.MergeConstantValue<false, false>(constantBounds1.LowerBound());
        else
            mergedUpperBound.Merge<false, false>(ValueRelativeOffset(bounds1Value, true));
        mergedBounds->relativeUpperBounds.Add(mergedUpperBound);
    }

    mergedBounds->Verify();
    return mergedBounds;
}

const IntBounds *IntBounds::Merge(
    const Value *const bounds0Value,
    const IntBounds *const bounds0,
    const Value *const bounds1Value,
    const IntBounds *const bounds1)
{
    Assert(bounds0Value);
    bounds0->Verify();
    Assert(bounds1Value);
    bounds1->Verify();

    if(bounds0 == bounds1)
        return bounds0;

    JitArenaAllocator *const allocator = bounds0->relativeLowerBounds.GetAllocator();
    IntBounds *const mergedBounds =
        New(IntConstantBounds(
                min(bounds0->constantLowerBound, bounds1->constantLowerBound),
                max(bounds0->constantUpperBound, bounds1->constantUpperBound)),
            bounds0->WasConstantUpperBoundEstablishedExplicitly() && bounds1->WasConstantUpperBoundEstablishedExplicitly(),
            allocator);
    MergeBoundSets<true>(bounds0Value, bounds0, bounds1Value, bounds1, mergedBounds);
    MergeBoundSets<false>(bounds0Value, bounds0, bounds1Value, bounds1, mergedBounds);
    if(mergedBounds->HasBounds())
    {
        mergedBounds->Verify();
        return mergedBounds;
    }
    mergedBounds->Delete();
    return nullptr;
}

template<bool Lower>
void IntBounds::MergeBoundSets(
    const Value *const bounds0Value,
    const IntBounds *const bounds0,
    const Value *const bounds1Value,
    const IntBounds *const bounds1,
    IntBounds *const mergedBounds)
{
    Assert(bounds0Value);
    bounds0->Verify();
    Assert(bounds1Value);
    bounds1->Verify();
    Assert(bounds0 != bounds1);
    Assert(mergedBounds);
    Assert(mergedBounds != bounds0);
    Assert(mergedBounds != bounds1);

    RelativeIntBoundSet *mergedBoundSet;
    const RelativeIntBoundSet *boundSet0, *boundSet1;
    if(Lower)
    {
        mergedBoundSet = &mergedBounds->relativeLowerBounds;
        boundSet0 = &bounds0->relativeLowerBounds;
        boundSet1 = &bounds1->relativeLowerBounds;
    }
    else
    {
        mergedBoundSet = &mergedBounds->relativeUpperBounds;
        boundSet0 = &bounds0->relativeUpperBounds;
        boundSet1 = &bounds1->relativeUpperBounds;
    }

    // Iterate over the smaller set and look up in the larger set for compatible bounds that can be merged
    const RelativeIntBoundSet *iterateOver, *lookUpIn;
    if(boundSet0->Count() <= boundSet1->Count())
    {
        iterateOver = boundSet0;
        lookUpIn = boundSet1;
    }
    else
    {
        iterateOver = boundSet1;
        lookUpIn = boundSet0;
    }
    for(auto it = iterateOver->GetIterator(); it.IsValid(); it.MoveNext())
    {
        const ValueRelativeOffset &iterateOver_bound(it.CurrentValue());
        const ValueNumber baseValueNumber = iterateOver_bound.BaseValueNumber();
        const ValueRelativeOffset *lookUpIn_bound;
        if(!lookUpIn->TryGetReference(baseValueNumber, &lookUpIn_bound))
            continue;
        ValueRelativeOffset mergedBound(iterateOver_bound);
        mergedBound.Merge<Lower, false>(*lookUpIn_bound);
        mergedBoundSet->Add(mergedBound);
    }

    // A value is implicitly bounded by itself, so preserve and merge bounds where one value is bounded by the other
    const ValueNumber bounds0ValueNumber = bounds0Value->GetValueNumber(), bounds1ValueNumber = bounds1Value->GetValueNumber();
    if(bounds0ValueNumber == bounds1ValueNumber)
        return;
    const ValueRelativeOffset *bound;
    if(boundSet0->TryGetReference(bounds1ValueNumber, &bound))
    {
        ValueRelativeOffset mergedBound(bounds1Value, true);
        mergedBound.Merge<Lower, false>(*bound);
        mergedBoundSet->Add(mergedBound);
    }
    if(boundSet1->TryGetReference(bounds0ValueNumber, &bound))
    {
        ValueRelativeOffset mergedBound(bounds0Value, true);
        mergedBound.Merge<Lower, false>(*bound);
        mergedBoundSet->Add(mergedBound);
    }
}

#pragma endregion

#pragma region IntBoundCheckCompatibilityId and IntBoundCheck

IntBoundCheckCompatibilityId::IntBoundCheckCompatibilityId(
    const ValueNumber leftValueNumber,
    const ValueNumber rightValueNumber)
    : leftValueNumber(leftValueNumber), rightValueNumber(rightValueNumber)
{
}

bool IntBoundCheckCompatibilityId::operator ==(const IntBoundCheckCompatibilityId &other) const
{
    return leftValueNumber == other.leftValueNumber && rightValueNumber == other.rightValueNumber;
}

IntBoundCheckCompatibilityId::operator hash_t() const
{
    return static_cast<hash_t>(static_cast<hash_t>(leftValueNumber) + static_cast<hash_t>(rightValueNumber));
}

IntBoundCheck::IntBoundCheck()
#if DBG
    : leftValueNumber(InvalidValueNumber)
#endif
{
    Assert(!IsValid());
}

IntBoundCheck::IntBoundCheck(
    const ValueNumber leftValueNumber,
    const ValueNumber rightValueNumber,
    IR::Instr *const instr,
    BasicBlock *const block)
    : leftValueNumber(leftValueNumber), rightValueNumber(rightValueNumber), instr(instr), block(block)
{
    Assert(IsValid());
}

#if DBG

bool IntBoundCheck::IsValid() const
{
    return leftValueNumber != InvalidValueNumber;
}

#endif

ValueNumber IntBoundCheck::LeftValueNumber() const
{
    Assert(IsValid());
    return leftValueNumber;
}

ValueNumber IntBoundCheck::RightValueNumber() const
{
    Assert(IsValid());
    return rightValueNumber;
}

IR::Instr *IntBoundCheck::Instr() const
{
    Assert(IsValid());
    return instr;
}

BasicBlock *IntBoundCheck::Block() const
{
    Assert(IsValid());
    return block;
}

IntBoundCheckCompatibilityId IntBoundCheck::CompatibilityId() const
{
    return IntBoundCheckCompatibilityId(leftValueNumber, rightValueNumber);
}

bool IntBoundCheck::SetBoundOffset(const int offset, const bool isLoopCountBasedBound) const
{
    Assert(IsValid());

    // Determine the previous offset from the instruction (src1 <= src2 + dst)
    IR::IntConstOpnd *dstOpnd = nullptr;
    IntConstType previousOffset = 0;
    IRType offsetType = TyMachReg;
    if (instr->GetDst())
    {
        dstOpnd = instr->GetDst()->AsIntConstOpnd();
        previousOffset = dstOpnd->GetValue();
        offsetType = dstOpnd->GetType();
    }

    IR::IntConstOpnd *src1Opnd = nullptr;
    if (instr->GetSrc1()->IsIntConstOpnd())
    {
        src1Opnd = instr->GetSrc1()->AsIntConstOpnd();
        if (IntConstMath::Sub(previousOffset, src1Opnd->GetValue(), src1Opnd->GetType(), &previousOffset))
            return false;
        offsetType = src1Opnd->GetType();
    }

    IR::IntConstOpnd *src2Opnd = (instr->GetSrc2()->IsIntConstOpnd() ? instr->GetSrc2()->AsIntConstOpnd() : nullptr);
    if(src2Opnd && IntConstMath::Add(previousOffset, src2Opnd->GetValue(), src2Opnd->GetType(), &previousOffset))
        return false;

    // Given a bounds check (a <= b + offset), the offset may only be decreased such that it does not invalidate the invariant
    // previously established by the check. If the offset needs to be increased, that requirement is already satisfied by the
    // previous check.
    if(offset >= previousOffset)
        return true;

    IntConstType offsetDecrease;
    if(IntConstMath::Sub(previousOffset, offset, offsetType, &offsetDecrease))
        return false;

    Assert(offsetDecrease > 0);
    if(src1Opnd)
    {
        // Prefer to increase src1, as this is an upper bound check and src1 corresponds to the index
        IntConstType newSrc1Value;
        if(IntConstMath::Add(src1Opnd->GetValue(), offsetDecrease, src1Opnd->GetType(), &newSrc1Value))
            return false;
        src1Opnd->SetValue(newSrc1Value);
    }
    else if(dstOpnd)
    {
        IntConstType newDstValue;
        if(IntConstMath::Sub(dstOpnd->GetValue(), offsetDecrease, dstOpnd->GetType(), &newDstValue))
            return false;
        if (newDstValue == 0)
            instr->FreeDst();
        else
            dstOpnd->SetValue(newDstValue);
    }
    else
        instr->SetDst(IR::IntConstOpnd::New(-offsetDecrease, TyMachReg, instr->m_func, true));

    switch(instr->GetBailOutKind())
    {
        case IR::BailOutOnFailedHoistedBoundCheck:
            if(isLoopCountBasedBound)
                instr->SetBailOutKind(IR::BailOutOnFailedHoistedLoopCountBasedBoundCheck);
            break;

        case IR::BailOutOnFailedHoistedLoopCountBasedBoundCheck:
            break;

        default:
            instr->SetBailOutKind(
                isLoopCountBasedBound
                    ? IR::BailOutOnFailedHoistedLoopCountBasedBoundCheck
                    : IR::BailOutOnFailedHoistedBoundCheck);
            break;
    }
    return true;
}

#pragma endregion