#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/IntegersSubset.h"
-#include "llvm/Support/IntegersSubsetMapping.h"
#include <iterator>
namespace llvm {
class SwitchInst : public TerminatorInst {
void *operator new(size_t, unsigned) LLVM_DELETED_FUNCTION;
unsigned ReservedSpace;
- // Operands format:
// Operand[0] = Value to switch on
// Operand[1] = Default basic block destination
// Operand[2n ] = Value to match
// Operand[2n+1] = BasicBlock to go to on match
-
- // Store case values separately from operands list. We needn't User-Use
- // concept here, since it is just a case value, it will always constant,
- // and case value couldn't reused with another instructions/values.
- // Additionally:
- // It allows us to use custom type for case values that is not inherited
- // from Value. Since case value is a complex type that implements
- // the subset of integers, we needn't extract sub-constants within
- // slow getAggregateElement method.
- // For case values we will use std::list to by two reasons:
- // 1. It allows to add/remove cases without whole collection reallocation.
- // 2. In most of cases we needn't random access.
- // Currently case values are also stored in Operands List, but it will moved
- // out in future commits.
- typedef std::list<IntegersSubset> Subsets;
- typedef Subsets::iterator SubsetsIt;
- typedef Subsets::const_iterator SubsetsConstIt;
-
- Subsets TheSubsets;
-
SwitchInst(const SwitchInst &SI);
void init(Value *Value, BasicBlock *Default, unsigned NumReserved);
void growOperands();
virtual SwitchInst *clone_impl() const;
public:
- // FIXME: Currently there are a lot of unclean template parameters,
- // we need to make refactoring in future.
- // All these parameters are used to implement both iterator and const_iterator
- // without code duplication.
- // SwitchInstTy may be "const SwitchInst" or "SwitchInst"
- // ConstantIntTy may be "const ConstantInt" or "ConstantInt"
- // SubsetsItTy may be SubsetsConstIt or SubsetsIt
- // BasicBlockTy may be "const BasicBlock" or "BasicBlock"
- template <class SwitchInstTy, class ConstantIntTy,
- class SubsetsItTy, class BasicBlockTy>
- class CaseIteratorT;
-
- typedef CaseIteratorT<const SwitchInst, const ConstantInt,
- SubsetsConstIt, const BasicBlock> ConstCaseIt;
- class CaseIt;
-
// -2
static const unsigned DefaultPseudoIndex = static_cast<unsigned>(~0L-1);
+ template <class SwitchInstTy, class ConstantIntTy, class BasicBlockTy>
+ class CaseIteratorT {
+ protected:
+
+ SwitchInstTy *SI;
+ unsigned Index;
+
+ public:
+
+ typedef CaseIteratorT<SwitchInstTy, ConstantIntTy, BasicBlockTy> Self;
+
+ /// Initializes case iterator for given SwitchInst and for given
+ /// case number.
+ CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
+ this->SI = SI;
+ Index = CaseNum;
+ }
+
+ /// Initializes case iterator for given SwitchInst and for given
+ /// TerminatorInst's successor index.
+ static Self fromSuccessorIndex(SwitchInstTy *SI, unsigned SuccessorIndex) {
+ assert(SuccessorIndex < SI->getNumSuccessors() &&
+ "Successor index # out of range!");
+ return SuccessorIndex != 0 ?
+ Self(SI, SuccessorIndex - 1) :
+ Self(SI, DefaultPseudoIndex);
+ }
+
+ /// Resolves case value for current case.
+ ConstantIntTy *getCaseValue() {
+ assert(Index < SI->getNumCases() && "Index out the number of cases.");
+ return reinterpret_cast<ConstantIntTy*>(SI->getOperand(2 + Index*2));
+ }
+
+ /// Resolves successor for current case.
+ BasicBlockTy *getCaseSuccessor() {
+ assert((Index < SI->getNumCases() ||
+ Index == DefaultPseudoIndex) &&
+ "Index out the number of cases.");
+ return SI->getSuccessor(getSuccessorIndex());
+ }
+
+ /// Returns number of current case.
+ unsigned getCaseIndex() const { return Index; }
+
+ /// Returns TerminatorInst's successor index for current case successor.
+ unsigned getSuccessorIndex() const {
+ assert((Index == DefaultPseudoIndex || Index < SI->getNumCases()) &&
+ "Index out the number of cases.");
+ return Index != DefaultPseudoIndex ? Index + 1 : 0;
+ }
+
+ Self operator++() {
+ // Check index correctness after increment.
+ // Note: Index == getNumCases() means end().
+ assert(Index+1 <= SI->getNumCases() && "Index out the number of cases.");
+ ++Index;
+ return *this;
+ }
+ Self operator++(int) {
+ Self tmp = *this;
+ ++(*this);
+ return tmp;
+ }
+ Self operator--() {
+ // Check index correctness after decrement.
+ // Note: Index == getNumCases() means end().
+ // Also allow "-1" iterator here. That will became valid after ++.
+ assert((Index == 0 || Index-1 <= SI->getNumCases()) &&
+ "Index out the number of cases.");
+ --Index;
+ return *this;
+ }
+ Self operator--(int) {
+ Self tmp = *this;
+ --(*this);
+ return tmp;
+ }
+ bool operator==(const Self& RHS) const {
+ assert(RHS.SI == SI && "Incompatible operators.");
+ return RHS.Index == Index;
+ }
+ bool operator!=(const Self& RHS) const {
+ assert(RHS.SI == SI && "Incompatible operators.");
+ return RHS.Index != Index;
+ }
+ };
+
+ typedef CaseIteratorT<const SwitchInst, const ConstantInt, const BasicBlock>
+ ConstCaseIt;
+
+ class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> {
+
+ typedef CaseIteratorT<SwitchInst, ConstantInt, BasicBlock> ParentTy;
+
+ public:
+
+ CaseIt(const ParentTy& Src) : ParentTy(Src) {}
+ CaseIt(SwitchInst *SI, unsigned CaseNum) : ParentTy(SI, CaseNum) {}
+
+ /// Sets the new value for current case.
+ void setValue(ConstantInt *V) {
+ assert(Index < SI->getNumCases() && "Index out the number of cases.");
+ SI->setOperand(2 + Index*2, reinterpret_cast<Value*>(V));
+ }
+
+ /// Sets the new successor for current case.
+ void setSuccessor(BasicBlock *S) {
+ SI->setSuccessor(getSuccessorIndex(), S);
+ }
+ };
+
static SwitchInst *Create(Value *Value, BasicBlock *Default,
unsigned NumCases, Instruction *InsertBefore = 0) {
return new SwitchInst(Value, Default, NumCases, InsertBefore);
/// Returns a read/write iterator that points to the first
/// case in SwitchInst.
CaseIt case_begin() {
- return CaseIt(this, 0, TheSubsets.begin());
+ return CaseIt(this, 0);
}
/// Returns a read-only iterator that points to the first
/// case in the SwitchInst.
ConstCaseIt case_begin() const {
- return ConstCaseIt(this, 0, TheSubsets.begin());
+ return ConstCaseIt(this, 0);
}
/// Returns a read/write iterator that points one past the last
/// in the SwitchInst.
CaseIt case_end() {
- return CaseIt(this, getNumCases(), TheSubsets.end());
+ return CaseIt(this, getNumCases());
}
/// Returns a read-only iterator that points one past the last
/// in the SwitchInst.
ConstCaseIt case_end() const {
- return ConstCaseIt(this, getNumCases(), TheSubsets.end());
+ return ConstCaseIt(this, getNumCases());
}
/// Returns an iterator that points to the default case.
/// Note: this iterator allows to resolve successor only. Attempt
/// Also note, that increment and decrement also causes an assertion and
/// makes iterator invalid.
CaseIt case_default() {
- return CaseIt(this, DefaultPseudoIndex, TheSubsets.end());
+ return CaseIt(this, DefaultPseudoIndex);
}
ConstCaseIt case_default() const {
- return ConstCaseIt(this, DefaultPseudoIndex, TheSubsets.end());
+ return ConstCaseIt(this, DefaultPseudoIndex);
}
/// findCaseValue - Search all of the case values for the specified constant.
/// that it is handled by the default handler.
CaseIt findCaseValue(const ConstantInt *C) {
for (CaseIt i = case_begin(), e = case_end(); i != e; ++i)
- if (i.getCaseValueEx().isSatisfies(IntItem::fromConstantInt(C)))
+ if (i.getCaseValue() == C)
return i;
return case_default();
}
ConstCaseIt findCaseValue(const ConstantInt *C) const {
for (ConstCaseIt i = case_begin(), e = case_end(); i != e; ++i)
- if (i.getCaseValueEx().isSatisfies(IntItem::fromConstantInt(C)))
+ if (i.getCaseValue() == C)
return i;
return case_default();
}
/// point to the added case.
void addCase(ConstantInt *OnVal, BasicBlock *Dest);
- /// addCase - Add an entry to the switch instruction.
- /// Note:
- /// This action invalidates case_end(). Old case_end() iterator will
- /// point to the added case.
- void addCase(IntegersSubset& OnVal, BasicBlock *Dest);
-
/// removeCase - This method removes the specified case and its successor
/// from the switch instruction. Note that this operation may reorder the
/// remaining cases at index idx and above.
/// Note:
/// This action invalidates iterators for all cases following the one removed,
/// including the case_end() iterator.
- void removeCase(CaseIt& i);
+ void removeCase(CaseIt i);
unsigned getNumSuccessors() const { return getNumOperands()/2; }
BasicBlock *getSuccessor(unsigned idx) const {
setOperand(idx*2+1, (Value*)NewSucc);
}
- uint16_t hash() const {
- uint32_t NumberOfCases = (uint32_t)getNumCases();
- uint16_t Hash = (0xFFFF & NumberOfCases) ^ (NumberOfCases >> 16);
- for (ConstCaseIt i = case_begin(), e = case_end();
- i != e; ++i) {
- uint32_t NumItems = (uint32_t)i.getCaseValueEx().getNumItems();
- Hash = (Hash << 1) ^ (0xFFFF & NumItems) ^ (NumItems >> 16);
- }
- return Hash;
- }
-
- // Case iterators definition.
-
- template <class SwitchInstTy, class ConstantIntTy,
- class SubsetsItTy, class BasicBlockTy>
- class CaseIteratorT {
- protected:
-
- SwitchInstTy *SI;
- unsigned Index;
- SubsetsItTy SubsetIt;
-
- /// Initializes case iterator for given SwitchInst and for given
- /// case number.
- friend class SwitchInst;
- CaseIteratorT(SwitchInstTy *SI, unsigned SuccessorIndex,
- SubsetsItTy CaseValueIt) {
- this->SI = SI;
- Index = SuccessorIndex;
- this->SubsetIt = CaseValueIt;
- }
-
- public:
- typedef typename SubsetsItTy::reference IntegersSubsetRef;
- typedef CaseIteratorT<SwitchInstTy, ConstantIntTy,
- SubsetsItTy, BasicBlockTy> Self;
-
- CaseIteratorT(SwitchInstTy *SI, unsigned CaseNum) {
- this->SI = SI;
- Index = CaseNum;
- SubsetIt = SI->TheSubsets.begin();
- std::advance(SubsetIt, CaseNum);
- }
-
-
- /// Initializes case iterator for given SwitchInst and for given
- /// TerminatorInst's successor index.
- static Self fromSuccessorIndex(SwitchInstTy *SI, unsigned SuccessorIndex) {
- assert(SuccessorIndex < SI->getNumSuccessors() &&
- "Successor index # out of range!");
- return SuccessorIndex != 0 ?
- Self(SI, SuccessorIndex - 1) :
- Self(SI, DefaultPseudoIndex);
- }
-
- /// Resolves case value for current case.
- ConstantIntTy *getCaseValue() {
- assert(Index < SI->getNumCases() && "Index out the number of cases.");
- IntegersSubsetRef CaseRanges = *SubsetIt;
-
- // FIXME: Currently we work with ConstantInt based cases.
- // So return CaseValue as ConstantInt.
- return CaseRanges.getSingleNumber(0).toConstantInt();
- }
-
- /// Resolves case value for current case.
- IntegersSubsetRef getCaseValueEx() {
- assert(Index < SI->getNumCases() && "Index out the number of cases.");
- return *SubsetIt;
- }
-
- /// Resolves successor for current case.
- BasicBlockTy *getCaseSuccessor() {
- assert((Index < SI->getNumCases() ||
- Index == DefaultPseudoIndex) &&
- "Index out the number of cases.");
- return SI->getSuccessor(getSuccessorIndex());
- }
-
- /// Returns number of current case.
- unsigned getCaseIndex() const { return Index; }
-
- /// Returns TerminatorInst's successor index for current case successor.
- unsigned getSuccessorIndex() const {
- assert((Index == DefaultPseudoIndex || Index < SI->getNumCases()) &&
- "Index out the number of cases.");
- return Index != DefaultPseudoIndex ? Index + 1 : 0;
- }
-
- Self operator++() {
- // Check index correctness after increment.
- // Note: Index == getNumCases() means end().
- assert(Index+1 <= SI->getNumCases() && "Index out the number of cases.");
- ++Index;
- if (Index == 0)
- SubsetIt = SI->TheSubsets.begin();
- else
- ++SubsetIt;
- return *this;
- }
- Self operator++(int) {
- Self tmp = *this;
- ++(*this);
- return tmp;
- }
- Self operator--() {
- // Check index correctness after decrement.
- // Note: Index == getNumCases() means end().
- // Also allow "-1" iterator here. That will became valid after ++.
- unsigned NumCases = SI->getNumCases();
- assert((Index == 0 || Index-1 <= NumCases) &&
- "Index out the number of cases.");
- --Index;
- if (Index == NumCases) {
- SubsetIt = SI->TheSubsets.end();
- return *this;
- }
-
- if (Index != -1U)
- --SubsetIt;
-
- return *this;
- }
- Self operator--(int) {
- Self tmp = *this;
- --(*this);
- return tmp;
- }
- bool operator==(const Self& RHS) const {
- assert(RHS.SI == SI && "Incompatible operators.");
- return RHS.Index == Index;
- }
- bool operator!=(const Self& RHS) const {
- assert(RHS.SI == SI && "Incompatible operators.");
- return RHS.Index != Index;
- }
- };
-
- class CaseIt : public CaseIteratorT<SwitchInst, ConstantInt,
- SubsetsIt, BasicBlock> {
- typedef CaseIteratorT<SwitchInst, ConstantInt, SubsetsIt, BasicBlock>
- ParentTy;
-
- protected:
- friend class SwitchInst;
- CaseIt(SwitchInst *SI, unsigned CaseNum, SubsetsIt SubsetIt) :
- ParentTy(SI, CaseNum, SubsetIt) {}
-
- void updateCaseValueOperand(IntegersSubset& V) {
- SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));
- }
-
- public:
-
- CaseIt(SwitchInst *SI, unsigned CaseNum) : ParentTy(SI, CaseNum) {}
-
- CaseIt(const ParentTy& Src) : ParentTy(Src) {}
-
- /// Sets the new value for current case.
- void setValue(ConstantInt *V) {
- assert(Index < SI->getNumCases() && "Index out the number of cases.");
- IntegersSubsetToBB Mapping;
- // FIXME: Currently we work with ConstantInt based cases.
- // So inititalize IntItem container directly from ConstantInt.
- Mapping.add(IntItem::fromConstantInt(V));
- *SubsetIt = Mapping.getCase();
- updateCaseValueOperand(*SubsetIt);
- }
-
- /// Sets the new value for current case.
- void setValueEx(IntegersSubset& V) {
- assert(Index < SI->getNumCases() && "Index out the number of cases.");
- *SubsetIt = V;
- updateCaseValueOperand(*SubsetIt);
- }
-
- /// Sets the new successor for current case.
- void setSuccessor(BasicBlock *S) {
- SI->setSuccessor(getSuccessorIndex(), S);
- }
- };
-
// Methods for support type inquiry through isa, cast, and dyn_cast:
-
static inline bool classof(const Instruction *I) {
return I->getOpcode() == Instruction::Switch;
}
+++ /dev/null
-//===-- 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;
- --NewHigh;
- Res.first.High = NewHigh;
- }
- if (High > RHS.High) {
- IntType NewLow = RHS.High;
- ++NewLow;
- Res.second.Low = NewLow;
- Res.second.High = High;
- }
- return Res;
- }
- };
-
-//===----------------------------------------------------------------------===//
-/// IntegersSubsetGeneric - class that implements the subset of integers. It
-/// consists from ranges and single numbers.
-template <class IntTy>
-class IntegersSubsetGeneric {
-public:
- // Use Chris Lattner idea, that was initially described here:
- // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
- // In short, for more compact memory consumption we can store flat
- // numbers collection, and define range as pair of indices.
- // In that case we can safe some memory on 32 bit machines.
- typedef std::vector<IntTy> FlatCollectionTy;
- typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
- typedef std::vector<RangeLinkTy> RangeLinksTy;
- typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
-
- typedef IntegersSubsetGeneric<IntTy> self;
-
-protected:
-
- FlatCollectionTy FlatCollection;
- RangeLinksTy RangeLinks;
-
- bool IsSingleNumber;
- bool IsSingleNumbersOnly;
-
-public:
-
- template<class RangesCollectionTy>
- explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
- assert(Links.size() && "Empty ranges are not allowed.");
-
- // In case of big set of single numbers consumes additional RAM space,
- // but allows to avoid additional reallocation.
- FlatCollection.reserve(Links.size() * 2);
- RangeLinks.reserve(Links.size());
- IsSingleNumbersOnly = true;
- for (typename RangesCollectionTy::const_iterator i = Links.begin(),
- e = Links.end(); i != e; ++i) {
- RangeLinkTy RangeLink;
- FlatCollection.push_back(i->getLow());
- RangeLink.first = &FlatCollection.back();
- if (i->getLow() != i->getHigh()) {
- FlatCollection.push_back(i->getHigh());
- IsSingleNumbersOnly = false;
- }
- RangeLink.second = &FlatCollection.back();
- RangeLinks.push_back(RangeLink);
- }
- IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
- }
-
- IntegersSubsetGeneric(const self& RHS) {
- *this = RHS;
- }
-
- self& operator=(const self& RHS) {
- FlatCollection.clear();
- RangeLinks.clear();
- FlatCollection.reserve(RHS.RangeLinks.size() * 2);
- RangeLinks.reserve(RHS.RangeLinks.size());
- for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
- i != e; ++i) {
- RangeLinkTy RangeLink;
- FlatCollection.push_back(*(i->first));
- RangeLink.first = &FlatCollection.back();
- if (i->first != i->second)
- FlatCollection.push_back(*(i->second));
- RangeLink.second = &FlatCollection.back();
- RangeLinks.push_back(RangeLink);
- }
- IsSingleNumber = RHS.IsSingleNumber;
- IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
- return *this;
- }
-
- typedef IntRange<IntTy> Range;
-
- /// Checks is the given constant satisfies this case. Returns
- /// true if it equals to one of contained values or belongs to the one of
- /// contained ranges.
- bool isSatisfies(const IntTy &CheckingVal) const {
- if (IsSingleNumber)
- return FlatCollection.front() == CheckingVal;
- if (IsSingleNumbersOnly)
- return std::find(FlatCollection.begin(),
- FlatCollection.end(),
- CheckingVal) != FlatCollection.end();
-
- for (size_t i = 0, e = getNumItems(); i < e; ++i) {
- if (RangeLinks[i].first == RangeLinks[i].second) {
- if (*RangeLinks[i].first == CheckingVal)
- return true;
- } else if (*RangeLinks[i].first <= CheckingVal &&
- *RangeLinks[i].second >= CheckingVal)
- return true;
- }
- return false;
- }
-
- /// Returns set's item with given index.
- Range getItem(unsigned idx) const {
- const RangeLinkTy &Link = RangeLinks[idx];
- if (Link.first != Link.second)
- return Range(*Link.first, *Link.second);
- else
- return Range(*Link.first);
- }
-
- /// Return number of items (ranges) stored in set.
- size_t getNumItems() const {
- return RangeLinks.size();
- }
-
- /// Returns true if whole subset contains single element.
- bool isSingleNumber() const {
- return IsSingleNumber;
- }
-
- /// Returns true if whole subset contains only single numbers, no ranges.
- bool isSingleNumbersOnly() const {
- return IsSingleNumbersOnly;
- }
-
- /// Does the same like getItem(idx).isSingleNumber(), but
- /// works faster, since we avoid creation of temporary range object.
- bool isSingleNumber(unsigned idx) const {
- return RangeLinks[idx].first == RangeLinks[idx].second;
- }
-
- /// Returns set the size, that equals number of all values + sizes of all
- /// ranges.
- /// Ranges set is considered as flat numbers collection.
- /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
- /// for range [<0>, <1>, <5>] the size will 3
- unsigned getSize() const {
- APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
- for (size_t i = 0, e = getNumItems(); i != e; ++i) {
- const APInt Low = getItem(i).getLow();
- const APInt High = getItem(i).getHigh();
- APInt S = High - Low + 1;
- sz += S;
- }
- return sz.getZExtValue();
- }
-
- /// Allows to access single value even if it belongs to some range.
- /// Ranges set is considered as flat numbers collection.
- /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
- /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
- APInt getSingleValue(unsigned idx) const {
- APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
- for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
- const APInt Low = getItem(i).getLow();
- const APInt High = getItem(i).getHigh();
- APInt S = High - Low + 1;
- APInt oldSz = sz;
- sz += S;
- if (sz.ugt(idx)) {
- APInt Res = Low;
- APInt Offset(oldSz.getBitWidth(), idx);
- Offset -= oldSz;
- Res += Offset;
- return Res;
- }
- }
- assert(0 && "Index exceeds high border.");
- return sz;
- }
-
- /// Does the same as getSingleValue, but works only if subset contains
- /// single numbers only.
- const IntTy& getSingleNumber(unsigned idx) const {
- assert(IsSingleNumbersOnly && "This method works properly if subset "
- "contains single numbers only.");
- return FlatCollection[idx];
- }
-};
-
-//===----------------------------------------------------------------------===//
-/// IntegersSubset - currently is extension of IntegersSubsetGeneric
-/// that also supports conversion to/from Constant* object.
-class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
-
- typedef IntegersSubsetGeneric<IntItem> ParentTy;
-
- Constant *Holder;
-
- static unsigned getNumItemsFromConstant(Constant *C) {
- return cast<ArrayType>(C->getType())->getNumElements();
- }
-
- static Range getItemFromConstant(Constant *C, unsigned idx) {
- const Constant *CV = C->getAggregateElement(idx);
-
- unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
- switch (NumEls) {
- case 1:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(cast<ConstantInt>(
- cast<ConstantInt>(CV->getAggregateElement(0U)))));
- case 2:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(1))));
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- return Range();
- }
- }
-
- std::vector<Range> rangesFromConstant(Constant *C) {
- unsigned NumItems = getNumItemsFromConstant(C);
- std::vector<Range> r;
- r.reserve(NumItems);
- for (unsigned i = 0, e = NumItems; i != e; ++i)
- r.push_back(getItemFromConstant(C, i));
- return r;
- }
-
-public:
-
- explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
- Holder(C) {}
-
- IntegersSubset(const IntegersSubset& RHS) :
- ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc.
- Holder(RHS.Holder) {}
-
- template<class RangesCollectionTy>
- explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
- std::vector<Constant*> Elts;
- Elts.reserve(Src.size());
- for (typename RangesCollectionTy::const_iterator i = Src.begin(),
- e = Src.end(); i != e; ++i) {
- const Range &R = *i;
- std::vector<Constant*> r;
- if (R.isSingleNumber()) {
- r.reserve(2);
- // FIXME: Since currently we have ConstantInt based numbers
- // use hack-conversion of IntItem to ConstantInt
- r.push_back(R.getLow().toConstantInt());
- r.push_back(R.getHigh().toConstantInt());
- } else {
- r.reserve(1);
- r.push_back(R.getLow().toConstantInt());
- }
- Constant *CV = ConstantVector::get(r);
- Elts.push_back(CV);
- }
- ArrayType *ArrTy =
- ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
- Holder = ConstantArray::get(ArrTy, Elts);
- }
-
- operator Constant*() { return Holder; }
- operator const Constant*() const { return Holder; }
- Constant *operator->() { return Holder; }
- const Constant *operator->() const { return Holder; }
-};
-
-}
-
-#endif /* CLLVM_SUPPORT_INTEGERSSUBSET_H */
+++ /dev/null
-//===- IntegersSubsetMapping.h - Mapping subset ==> Successor ---*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-/// @file
-/// IntegersSubsetMapping is mapping from A to B, where
-/// Items in A is subsets of integers,
-/// Items in B some pointers (Successors).
-/// If user which to add another subset for successor that is already
-/// exists in mapping, IntegersSubsetMapping merges existing subset with
-/// added one.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_SUPPORT_INTEGERSSUBSETMAPPING_H
-#define LLVM_SUPPORT_INTEGERSSUBSETMAPPING_H
-
-#include "llvm/Support/IntegersSubset.h"
-#include <list>
-#include <map>
-#include <vector>
-
-namespace llvm {
-
-template <class SuccessorClass,
- class IntegersSubsetTy = IntegersSubset,
- class IntTy = IntItem>
-class IntegersSubsetMapping {
- // FIXME: To much similar iterators typedefs, similar names.
- // - Rename RangeIterator to the cluster iterator.
- // - Remove unused "add" methods.
- // - Class contents needs cleaning.
-public:
-
- typedef IntRange<IntTy> RangeTy;
-
- struct RangeEx : public RangeTy {
- RangeEx() : Weight(1) {}
- RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
- RangeEx(const RangeTy &R, unsigned W) : RangeTy(R), Weight(W) {}
- RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
- RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
- RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
- RangeTy(L, H), Weight(W) {}
- unsigned Weight;
- };
-
- typedef std::pair<RangeEx, SuccessorClass*> Cluster;
-
- typedef std::list<RangeTy> RangesCollection;
- typedef typename RangesCollection::iterator RangesCollectionIt;
- typedef typename RangesCollection::const_iterator RangesCollectionConstIt;
- typedef IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> self;
-
-protected:
-
- typedef std::list<Cluster> CaseItems;
- typedef typename CaseItems::iterator CaseItemIt;
- typedef typename CaseItems::const_iterator CaseItemConstIt;
-
- // TODO: Change unclean CRS prefixes to SubsetMap for example.
- typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
- typedef typename CRSMap::iterator CRSMapIt;
-
- struct ClustersCmp {
- bool operator()(const Cluster &C1, const Cluster &C2) {
- return C1.first < C2.first;
- }
- };
-
- CaseItems Items;
- bool Sorted;
-
- bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
- return LItem->first.getHigh() >= RItem->first.getLow();
- }
-
- bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
- if (LItem->second != RItem->second) {
- assert(!isIntersected(LItem, RItem) &&
- "Intersected items with different successors!");
- return false;
- }
- APInt RLow = RItem->first.getLow();
- if (RLow != APInt::getNullValue(RLow.getBitWidth()))
- --RLow;
- return LItem->first.getHigh() >= RLow;
- }
-
- void sort() {
- if (!Sorted) {
- std::vector<Cluster> clustersVector;
- clustersVector.reserve(Items.size());
- clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
- std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
- Items.clear();
- Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
- Sorted = true;
- }
- }
-
- enum DiffProcessState {
- L_OPENED,
- INTERSECT_OPENED,
- R_OPENED,
- ALL_IS_CLOSED
- };
-
- class DiffStateMachine {
-
- DiffProcessState State;
- IntTy OpenPt;
- SuccessorClass *CurrentLSuccessor;
- SuccessorClass *CurrentRSuccessor;
-
- self *LeftMapping;
- self *IntersectionMapping;
- self *RightMapping;
-
- public:
-
- typedef
- IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
-
- DiffStateMachine(MappingTy *L,
- MappingTy *Intersection,
- MappingTy *R) :
- State(ALL_IS_CLOSED),
- LeftMapping(L),
- IntersectionMapping(Intersection),
- RightMapping(R)
- {}
-
- void onLOpen(const IntTy &Pt, SuccessorClass *S) {
- switch (State) {
- case R_OPENED:
- if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping)
- RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
- State = INTERSECT_OPENED;
- break;
- case ALL_IS_CLOSED:
- State = L_OPENED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- CurrentLSuccessor = S;
- OpenPt = Pt;
- }
-
- void onLClose(const IntTy &Pt) {
- switch (State) {
- case L_OPENED:
- assert(Pt >= OpenPt &&
- "Subset is not sorted or contains overlapped ranges");
- if (LeftMapping)
- LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
- State = ALL_IS_CLOSED;
- break;
- case INTERSECT_OPENED:
- if (IntersectionMapping)
- IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
- OpenPt = Pt + 1;
- State = R_OPENED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- }
-
- void onROpen(const IntTy &Pt, SuccessorClass *S) {
- switch (State) {
- case L_OPENED:
- if (Pt > OpenPt && LeftMapping)
- LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
- State = INTERSECT_OPENED;
- break;
- case ALL_IS_CLOSED:
- State = R_OPENED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- CurrentRSuccessor = S;
- OpenPt = Pt;
- }
-
- void onRClose(const IntTy &Pt) {
- switch (State) {
- case R_OPENED:
- assert(Pt >= OpenPt &&
- "Subset is not sorted or contains overlapped ranges");
- if (RightMapping)
- RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
- State = ALL_IS_CLOSED;
- break;
- case INTERSECT_OPENED:
- if (IntersectionMapping)
- IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
- OpenPt = Pt + 1;
- State = L_OPENED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- }
-
- void onLROpen(const IntTy &Pt,
- SuccessorClass *LS,
- SuccessorClass *RS) {
- switch (State) {
- case ALL_IS_CLOSED:
- State = INTERSECT_OPENED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- CurrentLSuccessor = LS;
- CurrentRSuccessor = RS;
- OpenPt = Pt;
- }
-
- void onLRClose(const IntTy &Pt) {
- switch (State) {
- case INTERSECT_OPENED:
- if (IntersectionMapping)
- IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
- State = ALL_IS_CLOSED;
- break;
- default:
- assert(0 && "Got unexpected point.");
- break;
- }
- }
-
- bool isLOpened() { return State == L_OPENED; }
- bool isROpened() { return State == R_OPENED; }
- };
-
-public:
-
- // Don't public CaseItems itself. Don't allow edit the Items directly.
- // Just present the user way to iterate over the internal collection
- // sharing iterator, begin() and end(). Editing should be controlled by
- // factory.
- typedef CaseItemIt RangeIterator;
-
- typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
- typedef std::list<Case> Cases;
- typedef typename Cases::iterator CasesIt;
-
- IntegersSubsetMapping() {
- Sorted = false;
- }
-
- bool verify() {
- RangeIterator DummyErrItem;
- return verify(DummyErrItem);
- }
-
- bool verify(RangeIterator& errItem) {
- if (Items.empty())
- return true;
- sort();
- for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
- j != e; i = j++) {
- if (isIntersected(i, j) && i->second != j->second) {
- errItem = j;
- return false;
- }
- }
- return true;
- }
-
- bool isOverlapped(self &RHS) {
- if (Items.empty() || RHS.empty())
- return true;
-
- for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
- el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
-
- const RangeTy &LRange = L->first;
- const RangeTy &RRange = R->first;
-
- if (LRange.getLow() > RRange.getLow()) {
- if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
- ++R;
- else
- return true;
- } else if (LRange.getLow() < RRange.getLow()) {
- if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
- ++L;
- else
- return true;
- } else // iRange.getLow() == jRange.getLow()
- return true;
- }
- return false;
- }
-
-
- void optimize() {
- if (Items.size() < 2)
- return;
- sort();
- CaseItems OldItems = Items;
- Items.clear();
- const IntTy *Low = &OldItems.begin()->first.getLow();
- const IntTy *High = &OldItems.begin()->first.getHigh();
- unsigned Weight = OldItems.begin()->first.Weight;
- SuccessorClass *Successor = OldItems.begin()->second;
- for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
- j != e; i = j++) {
- if (isJoinable(i, j)) {
- const IntTy *CurHigh = &j->first.getHigh();
- Weight += j->first.Weight;
- if (*CurHigh > *High)
- High = CurHigh;
- } else {
- RangeEx R(*Low, *High, Weight);
- add(R, Successor);
- Low = &j->first.getLow();
- High = &j->first.getHigh();
- Weight = j->first.Weight;
- Successor = j->second;
- }
- }
- RangeEx R(*Low, *High, Weight);
- add(R, Successor);
- // We recollected the Items, but we kept it sorted.
- Sorted = true;
- }
-
- /// Adds a constant value.
- void add(const IntTy &C, SuccessorClass *S = 0) {
- RangeTy R(C);
- add(R, S);
- }
-
- /// Adds a range.
- void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
- RangeTy R(Low, High);
- add(R, S);
- }
- void add(const RangeTy &R, SuccessorClass *S = 0) {
- RangeEx REx = R;
- add(REx, S);
- }
- void add(const RangeEx &R, SuccessorClass *S = 0) {
- Items.push_back(std::make_pair(R, S));
- Sorted = false;
- }
-
- /// Adds all ranges and values from given ranges set to the current
- /// mapping.
- void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0,
- unsigned Weight = 0) {
- unsigned ItemWeight = 1;
- if (Weight)
- // Weight is associated with CRS, for now we perform a division to
- // get the weight for each item.
- ItemWeight = Weight / CRS.getNumItems();
- for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
- RangeTy R = CRS.getItem(i);
- RangeEx REx(R, ItemWeight);
- add(REx, S);
- }
- }
-
- void add(self& RHS) {
- Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
- }
-
- void add(self& RHS, SuccessorClass *S) {
- for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
- add(i->first, S);
- }
-
- void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
- for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
- add(*i, S);
- }
-
- /// Removes items from set.
- void removeItem(RangeIterator i) { Items.erase(i); }
-
- /// Moves whole case from current mapping to the NewMapping object.
- void detachCase(self& NewMapping, SuccessorClass *Succ) {
- for (CaseItemIt i = Items.begin(); i != Items.end();)
- if (i->second == Succ) {
- NewMapping.add(i->first, i->second);
- Items.erase(i++);
- } else
- ++i;
- }
-
- /// Removes all clusters for given successor.
- void removeCase(SuccessorClass *Succ) {
- for (CaseItemIt i = Items.begin(); i != Items.end();)
- if (i->second == Succ) {
- Items.erase(i++);
- } else
- ++i;
- }
-
- /// Find successor that satisfies given value.
- SuccessorClass *findSuccessor(const IntTy& Val) {
- for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
- if (i->first.isInRange(Val))
- return i->second;
- }
- return 0;
- }
-
- /// Calculates the difference between this mapping and RHS.
- /// THIS without RHS is placed into LExclude,
- /// RHS without THIS is placed into RExclude,
- /// THIS intersect RHS is placed into Intersection.
- void diff(self *LExclude, self *Intersection, self *RExclude,
- const self& RHS) {
-
- DiffStateMachine Machine(LExclude, Intersection, RExclude);
-
- CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
- while (L != Items.end() && R != RHS.Items.end()) {
- const Cluster &LCluster = *L;
- const RangeEx &LRange = LCluster.first;
- const Cluster &RCluster = *R;
- const RangeEx &RRange = RCluster.first;
-
- if (LRange.getHigh() < RRange.getLow()) {
- Machine.onLOpen(LRange.getLow(), LCluster.second);
- Machine.onLClose(LRange.getHigh());
- ++L;
- continue;
- }
-
- if (LRange.getLow() > RRange.getHigh()) {
- Machine.onROpen(RRange.getLow(), RCluster.second);
- Machine.onRClose(RRange.getHigh());
- ++R;
- continue;
- }
-
- if (LRange.getLow() < RRange.getLow()) {
- // May be opened in previous iteration.
- if (!Machine.isLOpened())
- Machine.onLOpen(LRange.getLow(), LCluster.second);
- Machine.onROpen(RRange.getLow(), RCluster.second);
- }
- else if (RRange.getLow() < LRange.getLow()) {
- if (!Machine.isROpened())
- Machine.onROpen(RRange.getLow(), RCluster.second);
- Machine.onLOpen(LRange.getLow(), LCluster.second);
- }
- else
- Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
-
- if (LRange.getHigh() < RRange.getHigh()) {
- Machine.onLClose(LRange.getHigh());
- ++L;
- while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
- Machine.onLOpen(L->first.getLow(), L->second);
- Machine.onLClose(L->first.getHigh());
- ++L;
- }
- }
- else if (RRange.getHigh() < LRange.getHigh()) {
- Machine.onRClose(RRange.getHigh());
- ++R;
- while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
- Machine.onROpen(R->first.getLow(), R->second);
- Machine.onRClose(R->first.getHigh());
- ++R;
- }
- }
- else {
- Machine.onLRClose(LRange.getHigh());
- ++L;
- ++R;
- }
- }
-
- if (L != Items.end()) {
- if (Machine.isLOpened()) {
- Machine.onLClose(L->first.getHigh());
- ++L;
- }
- if (LExclude)
- while (L != Items.end()) {
- LExclude->add(L->first, L->second);
- ++L;
- }
- } else if (R != RHS.Items.end()) {
- if (Machine.isROpened()) {
- Machine.onRClose(R->first.getHigh());
- ++R;
- }
- if (RExclude)
- while (R != RHS.Items.end()) {
- RExclude->add(R->first, R->second);
- ++R;
- }
- }
- }
-
- /// Builds the finalized case objects.
- void getCases(Cases& TheCases, bool PreventMerging = false) {
- //FIXME: PreventMerging is a temporary parameter.
- //Currently a set of passes is still knows nothing about
- //switches with case ranges, and if these passes meet switch
- //with complex case that crashs the application.
- if (PreventMerging) {
- for (RangeIterator i = this->begin(); i != this->end(); ++i) {
- RangesCollection SingleRange;
- SingleRange.push_back(i->first);
- TheCases.push_back(std::make_pair(i->second,
- IntegersSubsetTy(SingleRange)));
- }
- return;
- }
- CRSMap TheCRSMap;
- for (RangeIterator i = this->begin(); i != this->end(); ++i)
- TheCRSMap[i->second].push_back(i->first);
- for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
- TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
- }
-
- /// Builds the finalized case objects ignoring successor values, as though
- /// all ranges belongs to the same successor.
- IntegersSubsetTy getCase() {
- RangesCollection Ranges;
- for (RangeIterator i = this->begin(); i != this->end(); ++i)
- Ranges.push_back(i->first);
- return IntegersSubsetTy(Ranges);
- }
-
- /// Returns pointer to value of case if it is single-numbered or 0
- /// in another case.
- const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
- const IntTy* Res = 0;
- for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
- if (i->second == Succ) {
- if (!i->first.isSingleNumber())
- return 0;
- if (Res)
- return 0;
- else
- Res = &(i->first.getLow());
- }
- return Res;
- }
-
- /// Returns true if there is no ranges and values inside.
- bool empty() const { return Items.empty(); }
-
- void clear() {
- Items.clear();
- // Don't reset Sorted flag:
- // 1. For empty mapping it matters nothing.
- // 2. After first item will added Sorted flag will cleared.
- }
-
- // Returns number of clusters
- unsigned size() const {
- return Items.size();
- }
-
- RangeIterator begin() { return Items.begin(); }
- RangeIterator end() { return Items.end(); }
-};
-
-class BasicBlock;
-typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
-
-}
-
-#endif /* LLVM_SUPPORT_INTEGERSSUBSETMAPPING_CRSBUILDER_H */
case bitc::FUNC_CODE_INST_SWITCH: { // SWITCH: [opty, op0, op1, ...]
// Check magic
if ((Record[0] >> 16) == SWITCH_INST_MAGIC) {
- // New SwitchInst format with case ranges.
+ // "New" SwitchInst format with case ranges. The changes to write this
+ // format were reverted but we still recognize bitcode that uses it.
+ // Hopefully someday we will have support for case ranges and can use
+ // this format again.
Type *OpTy = getTypeByID(Record[1]);
unsigned ValueBitWidth = cast<IntegerType>(OpTy)->getBitWidth();
unsigned CurIdx = 5;
for (unsigned i = 0; i != NumCases; ++i) {
- IntegersSubsetToBB CaseBuilder;
+ SmallVector<ConstantInt*, 1> CaseVals;
unsigned NumItems = Record[CurIdx++];
for (unsigned ci = 0; ci != NumItems; ++ci) {
bool isSingleNumber = Record[CurIdx++];
APInt High =
ReadWideAPInt(makeArrayRef(&Record[CurIdx], ActiveWords),
ValueBitWidth);
-
- CaseBuilder.add(IntItem::fromType(OpTy, Low),
- IntItem::fromType(OpTy, High));
CurIdx += ActiveWords;
+
+ // FIXME: It is not clear whether values in the range should be
+ // compared as signed or unsigned values. The partially
+ // implemented changes that used this format in the past used
+ // unsigned comparisons.
+ for ( ; Low.ule(High); ++Low)
+ CaseVals.push_back(ConstantInt::get(Context, Low));
} else
- CaseBuilder.add(IntItem::fromType(OpTy, Low));
+ CaseVals.push_back(ConstantInt::get(Context, Low));
}
BasicBlock *DestBB = getBasicBlock(Record[CurIdx++]);
- IntegersSubset Case = CaseBuilder.getCase();
- SI->addCase(Case, DestBB);
+ for (SmallVector<ConstantInt*, 1>::iterator cvi = CaseVals.begin(),
+ cve = CaseVals.end(); cvi != cve; ++cvi)
+ SI->addCase(*cvi, DestBB);
}
- uint16_t Hash = SI->hash();
- if (Hash != (Record[0] & 0xFFFF))
- return Error("Invalid SWITCH record");
I = SI;
break;
}
FUNCTION_INST_CAST_ABBREV,
FUNCTION_INST_RET_VOID_ABBREV,
FUNCTION_INST_RET_VAL_ABBREV,
- FUNCTION_INST_UNREACHABLE_ABBREV,
-
- // SwitchInst Magic
- SWITCH_INST_MAGIC = 0x4B5 // May 2012 => 1205 => Hex
+ FUNCTION_INST_UNREACHABLE_ABBREV
};
static unsigned GetEncodedCastOpcode(unsigned Opcode) {
Vals.push_back((-V << 1) | 1);
}
-static void EmitAPInt(SmallVectorImpl<uint64_t> &Vals,
- unsigned &Code, unsigned &AbbrevToUse, const APInt &Val,
- bool EmitSizeForWideNumbers = false
- ) {
- if (Val.getBitWidth() <= 64) {
- uint64_t V = Val.getSExtValue();
- emitSignedInt64(Vals, V);
- Code = bitc::CST_CODE_INTEGER;
- AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
- } else {
- // Wide integers, > 64 bits in size.
- // We have an arbitrary precision integer value to write whose
- // bit width is > 64. However, in canonical unsigned integer
- // format it is likely that the high bits are going to be zero.
- // So, we only write the number of active words.
- unsigned NWords = Val.getActiveWords();
-
- if (EmitSizeForWideNumbers)
- Vals.push_back(NWords);
-
- const uint64_t *RawWords = Val.getRawData();
- for (unsigned i = 0; i != NWords; ++i) {
- emitSignedInt64(Vals, RawWords[i]);
- }
- Code = bitc::CST_CODE_WIDE_INTEGER;
- }
-}
-
static void WriteConstants(unsigned FirstVal, unsigned LastVal,
const ValueEnumerator &VE,
BitstreamWriter &Stream, bool isGlobal) {
} else if (isa<UndefValue>(C)) {
Code = bitc::CST_CODE_UNDEF;
} else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
- EmitAPInt(Record, Code, AbbrevToUse, IV->getValue());
+ if (IV->getBitWidth() <= 64) {
+ uint64_t V = IV->getSExtValue();
+ emitSignedInt64(Record, V);
+ Code = bitc::CST_CODE_INTEGER;
+ AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
+ } else { // Wide integers, > 64 bits in size.
+ // We have an arbitrary precision integer value to write whose
+ // bit width is > 64. However, in canonical unsigned integer
+ // format it is likely that the high bits are going to be zero.
+ // So, we only write the number of active words.
+ unsigned NWords = IV->getValue().getActiveWords();
+ const uint64_t *RawWords = IV->getValue().getRawData();
+ for (unsigned i = 0; i != NWords; ++i) {
+ emitSignedInt64(Record, RawWords[i]);
+ }
+ Code = bitc::CST_CODE_WIDE_INTEGER;
+ }
} else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
Code = bitc::CST_CODE_FLOAT;
Type *Ty = CFP->getType();
Vals.push_back(InstID - ValID);
}
-static void pushValue64(const Value *V, unsigned InstID,
- SmallVectorImpl<uint64_t> &Vals,
- ValueEnumerator &VE) {
- uint64_t ValID = VE.getValueID(V);
- Vals.push_back(InstID - ValID);
-}
-
static void pushValueSigned(const Value *V, unsigned InstID,
SmallVectorImpl<uint64_t> &Vals,
ValueEnumerator &VE) {
break;
case Instruction::Switch:
{
- // Redefine Vals, since here we need to use 64 bit values
- // explicitly to store large APInt numbers.
- SmallVector<uint64_t, 128> Vals64;
-
Code = bitc::FUNC_CODE_INST_SWITCH;
const SwitchInst &SI = cast<SwitchInst>(I);
-
- uint32_t SwitchRecordHeader = SI.hash() | (SWITCH_INST_MAGIC << 16);
- Vals64.push_back(SwitchRecordHeader);
-
- Vals64.push_back(VE.getTypeID(SI.getCondition()->getType()));
- pushValue64(SI.getCondition(), InstID, Vals64, VE);
- Vals64.push_back(VE.getValueID(SI.getDefaultDest()));
- Vals64.push_back(SI.getNumCases());
+ Vals.push_back(VE.getTypeID(SI.getCondition()->getType()));
+ pushValue(SI.getCondition(), InstID, Vals, VE);
+ Vals.push_back(VE.getValueID(SI.getDefaultDest()));
for (SwitchInst::ConstCaseIt i = SI.case_begin(), e = SI.case_end();
i != e; ++i) {
- const IntegersSubset& CaseRanges = i.getCaseValueEx();
- unsigned Code, Abbrev; // will unused.
-
- if (CaseRanges.isSingleNumber()) {
- Vals64.push_back(1/*NumItems = 1*/);
- Vals64.push_back(true/*IsSingleNumber = true*/);
- EmitAPInt(Vals64, Code, Abbrev, CaseRanges.getSingleNumber(0), true);
- } else {
-
- Vals64.push_back(CaseRanges.getNumItems());
-
- if (CaseRanges.isSingleNumbersOnly()) {
- for (unsigned ri = 0, rn = CaseRanges.getNumItems();
- ri != rn; ++ri) {
-
- Vals64.push_back(true/*IsSingleNumber = true*/);
-
- EmitAPInt(Vals64, Code, Abbrev,
- CaseRanges.getSingleNumber(ri), true);
- }
- } else
- for (unsigned ri = 0, rn = CaseRanges.getNumItems();
- ri != rn; ++ri) {
- IntegersSubset::Range r = CaseRanges.getItem(ri);
- bool IsSingleNumber = CaseRanges.isSingleNumber(ri);
-
- Vals64.push_back(IsSingleNumber);
-
- EmitAPInt(Vals64, Code, Abbrev, r.getLow(), true);
- if (!IsSingleNumber)
- EmitAPInt(Vals64, Code, Abbrev, r.getHigh(), true);
- }
- }
- Vals64.push_back(VE.getValueID(i.getCaseSuccessor()));
+ Vals.push_back(VE.getValueID(i.getCaseValue()));
+ Vals.push_back(VE.getValueID(i.getCaseSuccessor()));
}
-
- Stream.EmitRecord(Code, Vals64, AbbrevToUse);
-
- // Also do expected action - clear external Vals collection:
- Vals.clear();
- return;
}
break;
case Instruction::IndirectBr:
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/IntegersSubsetMapping.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetFrameLowering.h"
} else
Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
} else {
- assert(CB.CC == ISD::SETCC_INVALID &&
- "Condition is undefined for to-the-range belonging check.");
+ assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
SDValue CmpOp = getValue(CB.CmpMHS);
EVT VT = CmpOp.getValueType();
- if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(false)) {
+ if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, VT),
- ISD::SETULE);
+ ISD::SETLE);
} else {
SDValue SUB = DAG.getNode(ISD::SUB, dl,
VT, CmpOp, DAG.getConstant(Low, VT));
CC = ISD::SETEQ;
LHS = SV; RHS = I->High; MHS = NULL;
} else {
- CC = ISD::SETCC_INVALID;
+ CC = ISD::SETLE;
LHS = I->Low; MHS = SV; RHS = I->High;
}
static APInt ComputeRange(const APInt &First, const APInt &Last) {
uint32_t BitWidth = std::max(Last.getBitWidth(), First.getBitWidth()) + 1;
- APInt LastExt = Last.zext(BitWidth), FirstExt = First.zext(BitWidth);
+ APInt LastExt = Last.sext(BitWidth), FirstExt = First.sext(BitWidth);
return (LastExt - FirstExt + 1ULL);
}
const APInt &Low = cast<ConstantInt>(I->Low)->getValue();
const APInt &High = cast<ConstantInt>(I->High)->getValue();
- if (Low.ule(TEI) && TEI.ule(High)) {
+ if (Low.sle(TEI) && TEI.sle(High)) {
DestBBs.push_back(I->BB);
if (TEI==High)
++I;
// Create a CaseBlock record representing a conditional branch to
// the LHS node if the value being switched on SV is less than C.
// Otherwise, branch to LHS.
- CaseBlock CB(ISD::SETULT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB);
+ CaseBlock CB(ISD::SETLT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB);
if (CR.CaseBB == SwitchBB)
visitSwitchCase(CB, SwitchBB);
// Optimize the case where all the case values fit in a
// word without having to subtract minValue. In this case,
// we can optimize away the subtraction.
- if (maxValue.ult(IntPtrBits)) {
+ if (minValue.isNonNegative() && maxValue.slt(IntPtrBits)) {
cmpRange = maxValue;
} else {
lowBound = minValue;
/// Clusterify - Transform simple list of Cases into list of CaseRange's
size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
const SwitchInst& SI) {
-
- /// Use a shorter form of declaration, and also
- /// show the we want to use CRSBuilder as Clusterifier.
- typedef IntegersSubsetMapping<MachineBasicBlock> Clusterifier;
-
- Clusterifier TheClusterifier;
+ size_t numCmps = 0;
BranchProbabilityInfo *BPI = FuncInfo.BPI;
// Start with "simple" cases
const BasicBlock *SuccBB = i.getCaseSuccessor();
MachineBasicBlock *SMBB = FuncInfo.MBBMap[SuccBB];
- TheClusterifier.add(i.getCaseValueEx(), SMBB,
- BPI ? BPI->getEdgeWeight(SI.getParent(), i.getSuccessorIndex()) : 0);
- }
-
- TheClusterifier.optimize();
+ uint32_t ExtraWeight =
+ BPI ? BPI->getEdgeWeight(SI.getParent(), i.getSuccessorIndex()) : 0;
+
+ Cases.push_back(Case(i.getCaseValue(), i.getCaseValue(),
+ SMBB, ExtraWeight));
+ }
+ std::sort(Cases.begin(), Cases.end(), CaseCmp());
+
+ // Merge case into clusters
+ if (Cases.size() >= 2)
+ // Must recompute end() each iteration because it may be
+ // invalidated by erase if we hold on to it
+ for (CaseItr I = Cases.begin(), J = llvm::next(Cases.begin());
+ J != Cases.end(); ) {
+ const APInt& nextValue = cast<ConstantInt>(J->Low)->getValue();
+ const APInt& currentValue = cast<ConstantInt>(I->High)->getValue();
+ MachineBasicBlock* nextBB = J->BB;
+ MachineBasicBlock* currentBB = I->BB;
+
+ // If the two neighboring cases go to the same destination, merge them
+ // into a single case.
+ if ((nextValue - currentValue == 1) && (currentBB == nextBB)) {
+ I->High = J->High;
+ I->ExtraWeight += J->ExtraWeight;
+ J = Cases.erase(J);
+ } else {
+ I = J++;
+ }
+ }
- size_t numCmps = 0;
- for (Clusterifier::RangeIterator i = TheClusterifier.begin(),
- e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- Clusterifier::Cluster &C = *i;
- // Update edge weight for the cluster.
- unsigned W = C.first.Weight;
-
- // FIXME: Currently work with ConstantInt based numbers.
- // Changing it to APInt based is a pretty heavy for this commit.
- Cases.push_back(Case(C.first.getLow().toConstantInt(),
- C.first.getHigh().toConstantInt(), C.second, W));
-
- if (C.first.getLow() != C.first.getHigh())
- // A range counts double, since it requires two compares.
- ++numCmps;
+ for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
+ if (I->Low != I->High)
+ // A range counts double, since it requires two compares.
+ ++numCmps;
}
return numCmps;
typedef std::vector<CaseRec> CaseRecVector;
+ /// The comparison function for sorting the switch case values in the vector.
+ /// WARNING: Case ranges should be disjoint!
+ struct CaseCmp {
+ bool operator()(const Case &C1, const Case &C2) {
+ assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
+ const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
+ const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
+ return CI1->getValue().slt(CI2->getValue());
+ }
+ };
+
struct CaseBitsCmp {
bool operator()(const CaseBits &C1, const CaseBits &C2) {
return C1.Bits > C2.Bits;
// Check to see if any of the cases match...
BasicBlock *Dest = 0;
for (SwitchInst::CaseIt i = I.case_begin(), e = I.case_end(); i != e; ++i) {
- IntegersSubset& Case = i.getCaseValueEx();
- if (Case.isSingleNumber()) {
- // FIXME: Currently work with ConstantInt based numbers.
- const ConstantInt *CI = Case.getSingleNumber(0).toConstantInt();
- GenericValue Val = getOperandValue(const_cast<ConstantInt*>(CI), SF);
- if (executeICMP_EQ(Val, CondVal, ElTy).IntVal != 0) {
- Dest = cast<BasicBlock>(i.getCaseSuccessor());
- break;
- }
+ GenericValue CaseVal = getOperandValue(i.getCaseValue(), SF);
+ if (executeICMP_EQ(CondVal, CaseVal, ElTy).IntVal != 0) {
+ Dest = cast<BasicBlock>(i.getCaseSuccessor());
+ break;
}
- if (Case.isSingleNumbersOnly()) {
- for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) {
- // FIXME: Currently work with ConstantInt based numbers.
- const ConstantInt *CI = Case.getSingleNumber(n).toConstantInt();
- GenericValue Val = getOperandValue(const_cast<ConstantInt*>(CI), SF);
- if (executeICMP_EQ(Val, CondVal, ElTy).IntVal != 0) {
- Dest = cast<BasicBlock>(i.getCaseSuccessor());
- break;
- }
- }
- } else
- for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) {
- IntegersSubset::Range r = Case.getItem(n);
- // FIXME: Currently work with ConstantInt based numbers.
- const ConstantInt *LowCI = r.getLow().toConstantInt();
- const ConstantInt *HighCI = r.getHigh().toConstantInt();
- GenericValue Low = getOperandValue(const_cast<ConstantInt*>(LowCI), SF);
- GenericValue High = getOperandValue(const_cast<ConstantInt*>(HighCI), SF);
- if (executeICMP_ULE(Low, CondVal, ElTy).IntVal != 0 &&
- executeICMP_ULE(CondVal, High, ElTy).IntVal != 0) {
- Dest = cast<BasicBlock>(i.getCaseSuccessor());
- break;
- }
- }
}
if (!Dest) Dest = I.getDefaultDest(); // No cases matched: use default
SwitchToNewBasicBlock(Dest, SF);
OL[i] = InOL[i];
OL[i+1] = InOL[i+1];
}
- TheSubsets = SI.TheSubsets;
SubclassOptionalData = SI.SubclassOptionalData;
}
/// addCase - Add an entry to the switch instruction...
///
void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
- IntegersSubsetToBB Mapping;
-
- // FIXME: Currently we work with ConstantInt based cases.
- // So inititalize IntItem container directly from ConstantInt.
- Mapping.add(IntItem::fromConstantInt(OnVal));
- IntegersSubset CaseRanges = Mapping.getCase();
- addCase(CaseRanges, Dest);
-}
-
-void SwitchInst::addCase(IntegersSubset& OnVal, BasicBlock *Dest) {
unsigned NewCaseIdx = getNumCases();
unsigned OpNo = NumOperands;
if (OpNo+2 > ReservedSpace)
// Initialize some new operands.
assert(OpNo+1 < ReservedSpace && "Growing didn't work!");
NumOperands = OpNo+2;
-
- SubsetsIt TheSubsetsIt = TheSubsets.insert(TheSubsets.end(), OnVal);
-
- CaseIt Case(this, NewCaseIdx, TheSubsetsIt);
- Case.updateCaseValueOperand(OnVal);
+ CaseIt Case(this, NewCaseIdx);
+ Case.setValue(OnVal);
Case.setSuccessor(Dest);
}
/// removeCase - This method removes the specified case and its successor
/// from the switch instruction.
-void SwitchInst::removeCase(CaseIt& i) {
+void SwitchInst::removeCase(CaseIt i) {
unsigned idx = i.getCaseIndex();
assert(2 + idx*2 < getNumOperands() && "Case index out of range!!!");
// Nuke the last value.
OL[NumOps-2].set(0);
OL[NumOps-2+1].set(0);
-
- // Do the same with TheCases collection:
- if (i.SubsetIt != --TheSubsets.end()) {
- *i.SubsetIt = TheSubsets.back();
- TheSubsets.pop_back();
- } else {
- TheSubsets.pop_back();
- i.SubsetIt = TheSubsets.end();
- }
-
NumOperands = NumOps-2;
}
// Check to make sure that all of the constants in the switch instruction
// have the same type as the switched-on value.
Type *SwitchTy = SI.getCondition()->getType();
- IntegerType *IntTy = cast<IntegerType>(SwitchTy);
- IntegersSubsetToBB Mapping;
- std::map<IntegersSubset::Range, unsigned> RangeSetMap;
+ SmallPtrSet<ConstantInt*, 32> Constants;
for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) {
- IntegersSubset CaseRanges = i.getCaseValueEx();
- for (unsigned ri = 0, rie = CaseRanges.getNumItems(); ri < rie; ++ri) {
- IntegersSubset::Range r = CaseRanges.getItem(ri);
- Assert1(((const APInt&)r.getLow()).getBitWidth() == IntTy->getBitWidth(),
- "Switch constants must all be same type as switch value!", &SI);
- Assert1(((const APInt&)r.getHigh()).getBitWidth() == IntTy->getBitWidth(),
- "Switch constants must all be same type as switch value!", &SI);
- Mapping.add(r);
- RangeSetMap[r] = i.getCaseIndex();
- }
- }
-
- IntegersSubsetToBB::RangeIterator errItem;
- if (!Mapping.verify(errItem)) {
- unsigned CaseIndex = RangeSetMap[errItem->first];
- SwitchInst::CaseIt i(&SI, CaseIndex);
- Assert2(false, "Duplicate integer as switch case", &SI, i.getCaseValueEx());
+ Assert1(i.getCaseValue()->getType() == SwitchTy,
+ "Switch constants must all be same type as switch value!", &SI);
+ Assert2(Constants.insert(i.getCaseValue()),
+ "Duplicate integer as switch case", &SI, i.getCaseValue());
}
visitTerminatorInst(SI);
nl(Out);
for (SwitchInst::ConstCaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
- const IntegersSubset CaseVal = i.getCaseValueEx();
+ const ConstantInt* CaseVal = i.getCaseValue();
const BasicBlock *BB = i.getCaseSuccessor();
Out << iName << "->addCase("
<< getOpName(CaseVal) << ", "
#include "llvm/InstVisitor.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Instruction.h"
+#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Transforms/Instrumentation.h"
#include "llvm/Transforms/Utils/Cloning.h"
TheSwitch->setCondition(call);
TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
// Remove redundant case
- SwitchInst::CaseIt ToBeRemoved(TheSwitch, NumExitBlocks-1);
- TheSwitch->removeCase(ToBeRemoved);
+ TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
break;
}
}
// Otherwise, we can fold this switch into a conditional branch
// instruction if it has only one non-default destination.
SwitchInst::CaseIt FirstCase = SI->case_begin();
- IntegersSubset& Case = FirstCase.getCaseValueEx();
- if (Case.isSingleNumber()) {
- // FIXME: Currently work with ConstantInt based numbers.
- Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
- Case.getSingleNumber(0).toConstantInt(),
- "cond");
-
- // Insert the new branch.
- BranchInst *NewBr = Builder.CreateCondBr(Cond,
- FirstCase.getCaseSuccessor(),
- SI->getDefaultDest());
- MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
- if (MD && MD->getNumOperands() == 3) {
- ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2));
- ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1));
- assert(SICase && SIDef);
- // The TrueWeight should be the weight for the single case of SI.
- NewBr->setMetadata(LLVMContext::MD_prof,
- MDBuilder(BB->getContext()).
- createBranchWeights(SICase->getValue().getZExtValue(),
- SIDef->getValue().getZExtValue()));
- }
+ Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
+ FirstCase.getCaseValue(), "cond");
- // Delete the old switch.
- SI->eraseFromParent();
- return true;
+ // Insert the new branch.
+ BranchInst *NewBr = Builder.CreateCondBr(Cond,
+ FirstCase.getCaseSuccessor(),
+ SI->getDefaultDest());
+ MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
+ if (MD && MD->getNumOperands() == 3) {
+ ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2));
+ ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1));
+ assert(SICase && SIDef);
+ // The TrueWeight should be the weight for the single case of SI.
+ NewBr->setMetadata(LLVMContext::MD_prof,
+ MDBuilder(BB->getContext()).
+ createBranchWeights(SICase->getValue().getZExtValue(),
+ SIDef->getValue().getZExtValue()));
}
+
+ // Delete the old switch.
+ SI->eraseFromParent();
+ return true;
}
return false;
}
BasicBlock* OrigBlock, BasicBlock* Default);
unsigned Clusterify(CaseVector& Cases, SwitchInst *SI);
};
+
+ /// The comparison function for sorting the switch case values in the vector.
+ /// WARNING: Case ranges should be disjoint!
+ struct CaseCmp {
+ bool operator () (const LowerSwitch::CaseRange& C1,
+ const LowerSwitch::CaseRange& C2) {
+
+ const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
+ const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
+ return CI1->getValue().slt(CI2->getValue());
+ }
+ };
}
char LowerSwitch::ID = 0;
Function::iterator FI = OrigBlock;
F->getBasicBlockList().insert(++FI, NewNode);
- ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_ULT,
+ ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT,
Val, Pivot.Low, "Pivot");
NewNode->getInstList().push_back(Comp);
BranchInst::Create(LBranch, RBranch, Comp, NewNode);
// Clusterify - Transform simple list of Cases into list of CaseRange's
unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
-
- IntegersSubsetToBB TheClusterifier;
+ unsigned numCmps = 0;
// Start with "simple" cases
- for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
- i != e; ++i) {
- BasicBlock *SuccBB = i.getCaseSuccessor();
- IntegersSubset CaseRanges = i.getCaseValueEx();
- TheClusterifier.add(CaseRanges, SuccBB);
- }
-
- TheClusterifier.optimize();
+ for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
+ Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(),
+ i.getCaseSuccessor()));
- size_t numCmps = 0;
- for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(),
- e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- IntegersSubsetToBB::Cluster &C = *i;
-
- // FIXME: Currently work with ConstantInt based numbers.
- // Changing it to APInt based is a pretty heavy for this commit.
- Cases.push_back(CaseRange(C.first.getLow().toConstantInt(),
- C.first.getHigh().toConstantInt(), C.second));
- if (C.first.isSingleNumber())
+ std::sort(Cases.begin(), Cases.end(), CaseCmp());
+
+ // Merge case into clusters
+ if (Cases.size()>=2)
+ for (CaseItr I=Cases.begin(), J=llvm::next(Cases.begin()); J!=Cases.end(); ) {
+ int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue();
+ int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue();
+ BasicBlock* nextBB = J->BB;
+ BasicBlock* currentBB = I->BB;
+
+ // If the two neighboring cases go to the same destination, merge them
+ // into a single case.
+ if ((nextValue-currentValue==1) && (currentBB == nextBB)) {
+ I->High = J->High;
+ J = Cases.erase(J);
+ } else {
+ I = J++;
+ }
+ }
+
+ for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
+ if (I->Low != I->High)
// A range counts double, since it requires two compares.
++numCmps;
}
- return numCmps;
+ return numCmps;
}
// processSwitchInst - Replace the specified switch instruction with a sequence
+++ /dev/null
-; RUN: rm -f %t.bc
-; RUN: rm -f %t.ll
-; RUN: rm -f %t2.bc
-; RUN: rm -f %t2.ll
-; RUN: llvm-as %s -o %t.bc
-; RUN: llvm-dis %t.bc -o - | tail -n +2 > %t.ll
-; RUN: llvm-as %t.ll -o %t2.bc
-; RUN: llvm-dis %t2.bc -o - | tail -n +2 > %t2.ll
-; RUN: llvm-diff %t.ll %t2.ll
-
-define void @test() {
- %mem = alloca i32
- store i32 2, i32* %mem
- %c = load i32* %mem
- switch i32 %c, label %exit [
- i32 1, label %exit
- i32 2, label %exit
- ]
-exit:
- ret void
-}
-define void @test_wide() {
- %mem = alloca i256
- store i256 2, i256* %mem
- %c = load i256* %mem
- switch i256 %c, label %exit [
- i256 123456789012345678901234567890, label %exit
- i256 2, label %exit
- ]
-exit:
- ret void
-}
-
--- /dev/null
+; RUN: llvm-dis < %s.bc| FileCheck %s
+
+; case-ranges.ll.bc was generated by passing this file to llvm-as from the 3.3
+; release of LLVM. This tests that the bitcode for switches from that release
+; can still be read.
+
+define i32 @foo(i32 %x) nounwind ssp uwtable {
+; CHECK: define i32 @foo
+ %1 = alloca i32, align 4
+ %2 = alloca i32, align 4
+ store i32 %x, i32* %2, align 4
+ %3 = load i32* %2, align 4
+ switch i32 %3, label %9 [
+; CHECK: switch i32 %3, label %9
+ i32 -3, label %4
+; CHECK-NEXT: i32 -3, label %4
+ i32 -2, label %4
+; CHECK-NEXT: i32 -2, label %4
+ i32 -1, label %4
+; CHECK-NEXT: i32 -1, label %4
+ i32 0, label %4
+; CHECK-NEXT: i32 0, label %4
+ i32 1, label %4
+; CHECK-NEXT: i32 1, label %4
+ i32 2, label %4
+; CHECK-NEXT: i32 2, label %4
+ i32 4, label %5
+; CHECK-NEXT: i32 4, label %5
+ i32 5, label %6
+; CHECK-NEXT: i32 5, label %6
+ i32 6, label %7
+; CHECK-NEXT: i32 6, label %7
+ i32 7, label %8
+; CHECK-NEXT: i32 7, label %8
+ ]
+
+; <label>:4
+ store i32 -1, i32* %1
+ br label %11
+
+; <label>:5
+ store i32 2, i32* %1
+ br label %11
+
+; <label>:6
+ store i32 1, i32* %1
+ br label %11
+
+; <label>:7
+ store i32 4, i32* %1
+ br label %11
+
+; <label>:8
+ store i32 3, i32* %1
+ br label %11
+
+; <label>:9
+ br label %10
+
+; <label>:10
+ store i32 0, i32* %1
+ br label %11
+
+; <label>:11
+ %12 = load i32* %1
+ ret i32 %12
+}
;CHECK-NEXT: br label %NodeBlock37
;CHECK: NodeBlock37: ; preds = %entry
-;CHECK-NEXT: %Pivot38 = icmp ult i32 %tmp158, 11
+;CHECK-NEXT: %Pivot38 = icmp slt i32 %tmp158, 10
;CHECK-NEXT: br i1 %Pivot38, label %NodeBlock13, label %NodeBlock35
;CHECK: NodeBlock35: ; preds = %NodeBlock37
-;CHECK-NEXT: %Pivot36 = icmp ult i32 %tmp158, 14
+;CHECK-NEXT: %Pivot36 = icmp slt i32 %tmp158, 13
;CHECK-NEXT: br i1 %Pivot36, label %NodeBlock23, label %NodeBlock33
;CHECK: NodeBlock33: ; preds = %NodeBlock35
-;CHECK-NEXT: %Pivot34 = icmp ult i32 %tmp158, 15
+;CHECK-NEXT: %Pivot34 = icmp slt i32 %tmp158, 14
;CHECK-NEXT: br i1 %Pivot34, label %LeafBlock25, label %NodeBlock31
;CHECK: NodeBlock31: ; preds = %NodeBlock33
-;CHECK-NEXT: %Pivot32 = icmp ult i32 %tmp158, -6
+;CHECK-NEXT: %Pivot32 = icmp slt i32 %tmp158, 15
;CHECK-NEXT: br i1 %Pivot32, label %LeafBlock27, label %LeafBlock29
;CHECK: LeafBlock29: ; preds = %NodeBlock31
-;CHECK-NEXT: %tmp158.off = add i32 %tmp158, 6
-;CHECK-NEXT: %SwitchLeaf30 = icmp ule i32 %tmp158.off, 4
-;CHECK-NEXT: br i1 %SwitchLeaf30, label %bb338, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf30 = icmp eq i32 %tmp158, 15
+;CHECK-NEXT: br i1 %SwitchLeaf30, label %bb334, label %NewDefault
;CHECK: LeafBlock27: ; preds = %NodeBlock31
-;CHECK-NEXT: %SwitchLeaf28 = icmp eq i32 %tmp158, 15
-;CHECK-NEXT: br i1 %SwitchLeaf28, label %bb334, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf28 = icmp eq i32 %tmp158, 14
+;CHECK-NEXT: br i1 %SwitchLeaf28, label %bb332, label %NewDefault
;CHECK: LeafBlock25: ; preds = %NodeBlock33
-;CHECK-NEXT: %SwitchLeaf26 = icmp eq i32 %tmp158, 14
-;CHECK-NEXT: br i1 %SwitchLeaf26, label %bb332, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf26 = icmp eq i32 %tmp158, 13
+;CHECK-NEXT: br i1 %SwitchLeaf26, label %bb330, label %NewDefault
;CHECK: NodeBlock23: ; preds = %NodeBlock35
-;CHECK-NEXT: %Pivot24 = icmp ult i32 %tmp158, 12
+;CHECK-NEXT: %Pivot24 = icmp slt i32 %tmp158, 11
;CHECK-NEXT: br i1 %Pivot24, label %LeafBlock15, label %NodeBlock21
;CHECK: NodeBlock21: ; preds = %NodeBlock23
-;CHECK-NEXT: %Pivot22 = icmp ult i32 %tmp158, 13
+;CHECK-NEXT: %Pivot22 = icmp slt i32 %tmp158, 12
;CHECK-NEXT: br i1 %Pivot22, label %LeafBlock17, label %LeafBlock19
;CHECK: LeafBlock19: ; preds = %NodeBlock21
-;CHECK-NEXT: %SwitchLeaf20 = icmp eq i32 %tmp158, 13
-;CHECK-NEXT: br i1 %SwitchLeaf20, label %bb330, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf20 = icmp eq i32 %tmp158, 12
+;CHECK-NEXT: br i1 %SwitchLeaf20, label %bb328, label %NewDefault
;CHECK: LeafBlock17: ; preds = %NodeBlock21
-;CHECK-NEXT: %SwitchLeaf18 = icmp eq i32 %tmp158, 12
-;CHECK-NEXT: br i1 %SwitchLeaf18, label %bb328, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf18 = icmp eq i32 %tmp158, 11
+;CHECK-NEXT: br i1 %SwitchLeaf18, label %bb326, label %NewDefault
;CHECK: LeafBlock15: ; preds = %NodeBlock23
-;CHECK-NEXT: %SwitchLeaf16 = icmp eq i32 %tmp158, 11
-;CHECK-NEXT: br i1 %SwitchLeaf16, label %bb326, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf16 = icmp eq i32 %tmp158, 10
+;CHECK-NEXT: br i1 %SwitchLeaf16, label %bb324, label %NewDefault
;CHECK: NodeBlock13: ; preds = %NodeBlock37
-;CHECK-NEXT: %Pivot14 = icmp ult i32 %tmp158, 8
+;CHECK-NEXT: %Pivot14 = icmp slt i32 %tmp158, 7
;CHECK-NEXT: br i1 %Pivot14, label %NodeBlock, label %NodeBlock11
;CHECK: NodeBlock11: ; preds = %NodeBlock13
-;CHECK-NEXT: %Pivot12 = icmp ult i32 %tmp158, 9
+;CHECK-NEXT: %Pivot12 = icmp slt i32 %tmp158, 8
;CHECK-NEXT: br i1 %Pivot12, label %LeafBlock3, label %NodeBlock9
;CHECK: NodeBlock9: ; preds = %NodeBlock11
-;CHECK-NEXT: %Pivot10 = icmp ult i32 %tmp158, 10
+;CHECK-NEXT: %Pivot10 = icmp slt i32 %tmp158, 9
;CHECK-NEXT: br i1 %Pivot10, label %LeafBlock5, label %LeafBlock7
;CHECK: LeafBlock7: ; preds = %NodeBlock9
-;CHECK-NEXT: %SwitchLeaf8 = icmp eq i32 %tmp158, 10
-;CHECK-NEXT: br i1 %SwitchLeaf8, label %bb324, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf8 = icmp eq i32 %tmp158, 9
+;CHECK-NEXT: br i1 %SwitchLeaf8, label %bb322, label %NewDefault
;CHECK: LeafBlock5: ; preds = %NodeBlock9
-;CHECK-NEXT: %SwitchLeaf6 = icmp eq i32 %tmp158, 9
-;CHECK-NEXT: br i1 %SwitchLeaf6, label %bb322, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf6 = icmp eq i32 %tmp158, 8
+;CHECK-NEXT: br i1 %SwitchLeaf6, label %bb338, label %NewDefault
;CHECK: LeafBlock3: ; preds = %NodeBlock11
-;CHECK-NEXT: %SwitchLeaf4 = icmp eq i32 %tmp158, 8
-;CHECK-NEXT: br i1 %SwitchLeaf4, label %bb338, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf4 = icmp eq i32 %tmp158, 7
+;CHECK-NEXT: br i1 %SwitchLeaf4, label %bb, label %NewDefault
;CHECK: NodeBlock: ; preds = %NodeBlock13
-;CHECK-NEXT: %Pivot = icmp ult i32 %tmp158, 7
+;CHECK-NEXT: %Pivot = icmp slt i32 %tmp158, 0
;CHECK-NEXT: br i1 %Pivot, label %LeafBlock, label %LeafBlock1
;CHECK: LeafBlock1: ; preds = %NodeBlock
-;CHECK-NEXT: %SwitchLeaf2 = icmp eq i32 %tmp158, 7
-;CHECK-NEXT: br i1 %SwitchLeaf2, label %bb, label %NewDefault
+;CHECK-NEXT: %SwitchLeaf2 = icmp ule i32 %tmp158, 6
+;CHECK-NEXT: br i1 %SwitchLeaf2, label %bb338, label %NewDefault
;CHECK: LeafBlock: ; preds = %NodeBlock
-;CHECK-NEXT: %SwitchLeaf = icmp ule i32 %tmp158, 6
+;CHECK-NEXT: %tmp158.off = add i32 %tmp158, 6
+;CHECK-NEXT: %SwitchLeaf = icmp ule i32 %tmp158.off, 4
;CHECK-NEXT: br i1 %SwitchLeaf, label %bb338, label %NewDefault
define i32 @main(i32 %tmp158) {
bool Difference = false;
- DenseMap<Constant*, BasicBlock*> LCases;
+ DenseMap<ConstantInt*,BasicBlock*> LCases;
for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end();
I != E; ++I)
- LCases[I.getCaseValueEx()] = I.getCaseSuccessor();
+ LCases[I.getCaseValue()] = I.getCaseSuccessor();
for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end();
I != E; ++I) {
- IntegersSubset CaseValue = I.getCaseValueEx();
+ ConstantInt *CaseValue = I.getCaseValue();
BasicBlock *LCase = LCases[CaseValue];
if (LCase) {
if (TryUnify) tryUnify(LCase, I.getCaseSuccessor());
}
}
if (!Difference)
- for (DenseMap<Constant*, BasicBlock*>::iterator
+ for (DenseMap<ConstantInt*,BasicBlock*>::iterator
I = LCases.begin(), E = LCases.end(); I != E; ++I) {
if (Complain)
Engine.logf("left switch has extra case %l") << I->first;
// we perform white-box tests
//
+#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
+++ /dev/null
-//===- llvm/unittest/Support/IntegersSubsetTest.cpp - IntegersSubset tests ===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Support/IntegersSubset.h"
-#include "llvm/ADT/APInt.h"
-#include "llvm/Support/IntegersSubsetMapping.h"
-#include "gtest/gtest.h"
-#include <vector>
-
-using namespace llvm;
-
-namespace {
-
- class Int : public APInt {
- public:
- Int() {}
- Int(uint64_t V) : APInt(64, V) {}
- Int(const APInt& Src) : APInt(Src) {}
- bool operator < (const APInt& RHS) const { return ult(RHS); }
- bool operator > (const APInt& RHS) const { return ugt(RHS); }
- bool operator <= (const APInt& RHS) const { return ule(RHS); }
- bool operator >= (const APInt& RHS) const { return uge(RHS); }
- };
-
- typedef IntRange<Int> Range;
- typedef IntegersSubsetGeneric<Int> Subset;
- typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
-
- TEST(IntegersSubsetTest, GeneralTest) {
-
- // Test construction.
-
- std::vector<Range> Ranges;
- Ranges.reserve(3);
-
- // Initialize Subset as union of three pairs:
- // { {0, 8}, {10, 18}, {20, 28} }
- for (unsigned i = 0; i < 3; ++i)
- Ranges.push_back(Range(Int(i*10), Int(i*10 + 8)));
-
- Subset TheSubset(Ranges);
-
- for (unsigned i = 0; i < 3; ++i) {
- EXPECT_EQ(TheSubset.getItem(i).getLow(), Int(i*10));
- EXPECT_EQ(TheSubset.getItem(i).getHigh(), Int(i*10 + 8));
- }
-
- EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
-
- // Test belonging to range.
-
- EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
- EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
-
- // Test when subset contains the only item.
-
- Ranges.clear();
- Ranges.push_back(Range(Int(10), Int(10)));
-
- Subset TheSingleNumber(Ranges);
-
- EXPECT_TRUE(TheSingleNumber.isSingleNumber());
-
- Ranges.push_back(Range(Int(12), Int(15)));
-
- Subset NotASingleNumber(Ranges);
-
- EXPECT_FALSE(NotASingleNumber.isSingleNumber());
-
- // Test when subset contains items that are not a ranges but
- // the single numbers.
-
- Ranges.clear();
- Ranges.push_back(Range(Int(10), Int(10)));
- Ranges.push_back(Range(Int(15), Int(19)));
-
- Subset WithSingleNumberItems(Ranges);
-
- EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
- EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
-
- // Test size of subset. Note subset itself may be not optimized (improper),
- // so it may contain duplicates, and the size of subset { {0, 9} {5, 9} }
- // will 15 instead of 10.
-
- Ranges.clear();
- Ranges.push_back(Range(Int(0), Int(9)));
- Ranges.push_back(Range(Int(5), Int(9)));
-
- Subset NotOptimizedSubset(Ranges);
-
- EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
-
- // Test access to a single value.
- // getSingleValue(idx) method represents subset as flat numbers collection,
- // so subset { {0, 3}, {8, 10} } will represented as array
- // { 0, 1, 2, 3, 8, 9, 10 }.
-
- Ranges.clear();
- Ranges.push_back(Range(Int(0), Int(3)));
- Ranges.push_back(Range(Int(8), Int(10)));
-
- Subset OneMoreSubset(Ranges);
-
- EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
- }
-
- TEST(IntegersSubsetTest, MappingTest) {
-
- Mapping::Cases TheCases;
-
- unsigned Successors[3] = {0, 1, 2};
-
- // Test construction.
-
- Mapping TheMapping;
- for (unsigned i = 0; i < 3; ++i)
- TheMapping.add(Int(10*i), Int(10*i + 9), Successors + i);
- TheMapping.add(Int(111), Int(222), Successors);
- TheMapping.removeItem(--TheMapping.end());
-
- TheMapping.getCases(TheCases);
-
- EXPECT_EQ(TheCases.size(), 3ULL);
-
- for (unsigned i = 0; i < 3; ++i) {
- Mapping::Cases::iterator CaseIt = TheCases.begin();
- std::advance(CaseIt, i);
- EXPECT_EQ(CaseIt->first, Successors + i);
- EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
- EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(10*i), Int(10*i + 9)));
- }
-
- // Test verification.
-
- Mapping ImproperMapping;
- ImproperMapping.add(Int(10), Int(11), Successors + 0);
- ImproperMapping.add(Int(11), Int(12), Successors + 1);
-
- Mapping::RangeIterator ErrItem;
- EXPECT_FALSE(ImproperMapping.verify(ErrItem));
- EXPECT_EQ(ErrItem, --ImproperMapping.end());
-
- Mapping ProperMapping;
- ProperMapping.add(Int(10), Int(11), Successors + 0);
- ProperMapping.add(Int(12), Int(13), Successors + 1);
-
- EXPECT_TRUE(ProperMapping.verify(ErrItem));
-
- // Test optimization.
-
- Mapping ToBeOptimized;
-
- for (unsigned i = 0; i < 3; ++i) {
- ToBeOptimized.add(Int(i * 10), Int(i * 10 + 1), Successors + i);
- ToBeOptimized.add(Int(i * 10 + 2), Int(i * 10 + 9), Successors + i);
- }
-
- ToBeOptimized.optimize();
-
- TheCases.clear();
- ToBeOptimized.getCases(TheCases);
-
- EXPECT_EQ(TheCases.size(), 3ULL);
-
- for (unsigned i = 0; i < 3; ++i) {
- Mapping::Cases::iterator CaseIt = TheCases.begin();
- std::advance(CaseIt, i);
- EXPECT_EQ(CaseIt->first, Successors + i);
- EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
- EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9)));
- }
- }
-
- typedef unsigned unsigned_pair[2];
- typedef unsigned_pair unsigned_ranges[];
-
- void TestDiff(
- const unsigned_ranges LHS,
- unsigned LSize,
- const unsigned_ranges RHS,
- unsigned RSize,
- const unsigned_ranges ExcludeRes,
- unsigned ExcludeResSize,
- const unsigned_ranges IntersectRes,
- unsigned IntersectResSize
- ) {
-
- Mapping::RangesCollection Ranges;
-
- Mapping LHSMapping;
- for (unsigned i = 0; i < LSize; ++i)
- Ranges.push_back(Range(Int(LHS[i][0]), Int(LHS[i][1])));
- LHSMapping.add(Ranges);
-
- Ranges.clear();
-
- Mapping RHSMapping;
- for (unsigned i = 0; i < RSize; ++i)
- Ranges.push_back(Range(Int(RHS[i][0]), Int(RHS[i][1])));
- RHSMapping.add(Ranges);
-
- Mapping LExclude, Intersection;
-
- LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping);
-
- if (ExcludeResSize) {
- EXPECT_EQ(LExclude.size(), ExcludeResSize);
-
- unsigned i = 0;
- for (Mapping::RangeIterator rei = LExclude.begin(),
- e = LExclude.end(); rei != e; ++rei, ++i)
- EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
- } else
- EXPECT_TRUE(LExclude.empty());
-
- if (IntersectResSize) {
- EXPECT_EQ(Intersection.size(), IntersectResSize);
-
- unsigned i = 0;
- for (Mapping::RangeIterator ii = Intersection.begin(),
- e = Intersection.end(); ii != e; ++ii, ++i)
- EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1]));
- } else
- EXPECT_TRUE(Intersection.empty());
-
- LExclude.clear();
- Intersection.clear();
- RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping);
-
- // Check LExclude again.
- if (ExcludeResSize) {
- EXPECT_EQ(LExclude.size(), ExcludeResSize);
-
- unsigned i = 0;
- for (Mapping::RangeIterator rei = LExclude.begin(),
- e = LExclude.end(); rei != e; ++rei, ++i)
- EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
- } else
- EXPECT_TRUE(LExclude.empty());
- }
-
- TEST(IntegersSubsetTest, DiffTest) {
-
- static const unsigned NOT_A_NUMBER = 0xffff;
-
- {
- unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
- unsigned_ranges RHS = { { 3, 14 } };
- unsigned_ranges ExcludeRes = { { 0, 2 }, { 15, 17 } };
- unsigned_ranges IntersectRes = { { 3, 4 }, { 7, 10 }, { 13, 14 } };
-
- TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3);
- }
-
- {
- unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
- unsigned_ranges RHS = { { 0, 4 }, { 13, 17 } };
- unsigned_ranges ExcludeRes = { { 7, 10 } };
- unsigned_ranges IntersectRes = { { 0, 4 }, { 13, 17 } };
-
- TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2);
- }
-
- {
- unsigned_ranges LHS = { { 0, 17 } };
- unsigned_ranges RHS = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
- unsigned_ranges ExcludeRes =
- { { 0, 0 }, { 6, 9 }, { 13, 14 }, { 17, 17 } };
- unsigned_ranges IntersectRes = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
-
- TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3);
- }
-
- {
- unsigned_ranges LHS = { { 2, 4 } };
- unsigned_ranges RHS = { { 0, 5 } };
- unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
- unsigned_ranges IntersectRes = { { 2, 4 } };
-
- TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1);
- }
-
- {
- unsigned_ranges LHS = { { 2, 4 } };
- unsigned_ranges RHS = { { 7, 8 } };
- unsigned_ranges ExcludeRes = { { 2, 4 } };
- unsigned_ranges IntersectRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
-
- TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
- }
-
- {
- unsigned_ranges LHS = { { 3, 7 } };
- unsigned_ranges RHS = { { 1, 4 } };
- unsigned_ranges ExcludeRes = { { 5, 7 } };
- unsigned_ranges IntersectRes = { { 3, 4 } };
-
- TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1);
- }
-
- {
- unsigned_ranges LHS = { { 0, 7 } };
- unsigned_ranges RHS = { { 0, 5 }, { 6, 9 } };
- unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
- unsigned_ranges IntersectRes = { { 0, 5 }, {6, 7} };
-
- TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2);
- }
-
- {
- unsigned_ranges LHS = { { 17, 17 } };
- unsigned_ranges RHS = { { 4, 4 } };
- unsigned_ranges ExcludeRes = { {17, 17} };
- unsigned_ranges IntersectRes = { { NOT_A_NUMBER, NOT_A_NUMBER } };
-
- TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
- }
- }
-}
projects / oota-llvm.git / commitdiff