path: root/include/llvm/Support/IntegersSubset.h

//===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// @file
/// This file contains class that implements constant set of ranges:
/// [<Low0,High0>,...,<LowN,HighN>]. Initially, this class was created for
/// SwitchInst and was used for case value representation that may contain
/// multiple ranges for a single successor.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_INTEGERSSUBSET_H
#define LLVM_SUPPORT_INTEGERSSUBSET_H

#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/LLVMContext.h"
#include <list>

namespace llvm {

  // The IntItem is a wrapper for APInt.
  // 1. It determines sign of integer, it allows to use
  //    comparison operators >,<,>=,<=, and as result we got shorter and cleaner
  //    constructions.
  // 2. It helps to implement PR1255 (case ranges) as a series of small patches.
  // 3. Currently we can interpret IntItem both as ConstantInt and as APInt.
  //    It allows to provide SwitchInst methods that works with ConstantInt for
  //    non-updated passes. And it allows to use APInt interface for new methods.
  // 4. IntItem can be easily replaced with APInt.

  // The set of macros that allows to propagate APInt operators to the IntItem.

#define INT_ITEM_DEFINE_COMPARISON(op,func) \
  bool operator op (const APInt& RHS) const { \
    return getAPIntValue().func(RHS); \
  }

#define INT_ITEM_DEFINE_UNARY_OP(op) \
  IntItem operator op () const { \
    APInt res = op(getAPIntValue()); \
    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
    return IntItem(cast<ConstantInt>(NewVal)); \
  }

#define INT_ITEM_DEFINE_BINARY_OP(op) \
  IntItem operator op (const APInt& RHS) const { \
    APInt res = getAPIntValue() op RHS; \
    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
    return IntItem(cast<ConstantInt>(NewVal)); \
  }

#define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
  IntItem& operator op (const APInt& RHS) {\
    APInt res = getAPIntValue();\
    res op RHS; \
    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
    ConstantIntVal = cast<ConstantInt>(NewVal); \
    return *this; \
  }

#define INT_ITEM_DEFINE_PREINCDEC(op) \
    IntItem& operator op () { \
      APInt res = getAPIntValue(); \
      op(res); \
      Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
      ConstantIntVal = cast<ConstantInt>(NewVal); \
      return *this; \
    }

#define INT_ITEM_DEFINE_POSTINCDEC(op) \
    IntItem& operator op (int) { \
      APInt res = getAPIntValue();\
      op(res); \
      Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
      OldConstantIntVal = ConstantIntVal; \
      ConstantIntVal = cast<ConstantInt>(NewVal); \
      return IntItem(OldConstantIntVal); \
    }

#define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
  RetTy operator op (IntTy RHS) const { \
    return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \
  }

class IntItem {
  ConstantInt *ConstantIntVal;
  const APInt* APIntVal;
  IntItem(const ConstantInt *V) :
    ConstantIntVal(const_cast<ConstantInt*>(V)),
    APIntVal(&ConstantIntVal->getValue()){}
  const APInt& getAPIntValue() const {
    return *APIntVal;
  }
public:

  IntItem() {}

  operator const APInt&() const {
    return getAPIntValue();
  }

  // Propagate APInt operators.
  // Note, that
  // /,/=,>>,>>= are not implemented in APInt.
  // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.

  INT_ITEM_DEFINE_COMPARISON(<, ult)
  INT_ITEM_DEFINE_COMPARISON(>, ugt)
  INT_ITEM_DEFINE_COMPARISON(<=, ule)
  INT_ITEM_DEFINE_COMPARISON(>=, uge)

  INT_ITEM_DEFINE_COMPARISON(==, eq)
  INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)

  INT_ITEM_DEFINE_COMPARISON(!=, ne)
  INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)

  INT_ITEM_DEFINE_BINARY_OP(*)
  INT_ITEM_DEFINE_BINARY_OP(+)
  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
  INT_ITEM_DEFINE_BINARY_OP(-)
  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
  INT_ITEM_DEFINE_BINARY_OP(<<)
  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
  INT_ITEM_DEFINE_BINARY_OP(&)
  INT_ITEM_DEFINE_BINARY_OP(^)
  INT_ITEM_DEFINE_BINARY_OP(|)

  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)

  // Special case for <<=
  IntItem& operator <<= (unsigned RHS) {
    APInt res = getAPIntValue();
    res <<= RHS;
    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
    ConstantIntVal = cast<ConstantInt>(NewVal);
    return *this;
  }

  INT_ITEM_DEFINE_UNARY_OP(-)
  INT_ITEM_DEFINE_UNARY_OP(~)

  INT_ITEM_DEFINE_PREINCDEC(++)
  INT_ITEM_DEFINE_PREINCDEC(--)

  // The set of workarounds, since currently we use ConstantInt implemented
  // integer.

  static IntItem fromConstantInt(const ConstantInt *V) {
    return IntItem(V);
  }
  static IntItem fromType(Type* Ty, const APInt& V) {
    ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
    return fromConstantInt(C);
  }
  static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
    ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
        LikeThis.ConstantIntVal->getContext(), V));
    return fromConstantInt(C);
  }
  ConstantInt *toConstantInt() const {
    return ConstantIntVal;
  }
};

template<class IntType>
class IntRange {
protected:
    IntType Low;
    IntType High;
    bool IsEmpty : 1;
    bool IsSingleNumber : 1;

public:
    typedef IntRange<IntType> self;
    typedef std::pair<self, self> SubRes;

    IntRange() : IsEmpty(true) {}
    IntRange(const self &RHS) :
      Low(RHS.Low), High(RHS.High),
      IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
    IntRange(const IntType &C) :
      Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}

    IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
      IsEmpty(false), IsSingleNumber(Low == High) {}

    bool isEmpty() const { return IsEmpty; }
    bool isSingleNumber() const { return IsSingleNumber; }

    const IntType& getLow() const {
      assert(!IsEmpty && "Range is empty.");
      return Low;
    }
    const IntType& getHigh() const {
      assert(!IsEmpty && "Range is empty.");
      return High;
    }

    bool operator<(const self &RHS) const {
      assert(!IsEmpty && "Left range is empty.");
      assert(!RHS.IsEmpty && "Right range is empty.");
      if (Low == RHS.Low) {
        if (High > RHS.High)
          return true;
        return false;
      }
      if (Low < RHS.Low)
        return true;
      return false;
    }

    bool operator==(const self &RHS) const {
      assert(!IsEmpty && "Left range is empty.");
      assert(!RHS.IsEmpty && "Right range is empty.");
      return Low == RHS.Low && High == RHS.High;
    }

    bool operator!=(const self &RHS) const {
      return !operator ==(RHS);
    }

    static bool LessBySize(const self &LHS, const self &RHS) {
      return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
    }

    bool isInRange(const IntType &IntVal) const {
      assert(!IsEmpty && "Range is empty.");
      return IntVal >= Low && IntVal <= High;
    }

    SubRes sub(const self &RHS) const {
      SubRes Res;

      // RHS is either more global and includes this range or
      // if it doesn't intersected with this range.
      if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {

        // If RHS more global (it is enough to check
        // only one border in this case.
        if (RHS.isInRange(Low))
          return std::make_pair(self(Low, High), self());

        return Res;
      }

      if (Low < RHS.Low) {
        Res.first.Low = Low;
        IntType NewHigh = RHS.Low;