diff options
22 files changed, 392 insertions, 2029 deletions
diff --git a/include/llvm/IR/Instructions.h b/include/llvm/IR/Instructions.h index e05c3a823e..6adee6a5c2 100644 --- a/include/llvm/IR/Instructions.h +++ b/include/llvm/IR/Instructions.h @@ -23,8 +23,6 @@ #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 { @@ -2457,31 +2455,10 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(BranchInst, Value) 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(); @@ -2506,25 +2483,121 @@ protected: 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); @@ -2560,23 +2633,23 @@ public: /// 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 @@ -2584,10 +2657,10 @@ public: /// 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. @@ -2596,13 +2669,13 @@ public: /// 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(); } @@ -2628,19 +2701,13 @@ public: /// 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 { @@ -2652,190 +2719,7 @@ public: 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; } diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h deleted file mode 100644 index 64b79ee083..0000000000 --- a/include/llvm/Support/IntegersSubset.h +++ /dev/null @@ -1,540 +0,0 @@ -//===-- 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 */ diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h deleted file mode 100644 index 641ce78c5d..0000000000 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ /dev/null @@ -1,588 +0,0 @@ -//===- 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 */ diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp index b77c3489ba..3ac6e038fd 100644 --- a/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/lib/Bitcode/Reader/BitcodeReader.cpp @@ -2491,7 +2491,10 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { 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(); @@ -2508,7 +2511,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { 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++]; @@ -2528,20 +2531,22 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { 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; } diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp index 0aa919c55b..ed3c267b2d 100644 --- a/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -60,10 +60,7 @@ enum { 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) { @@ -865,34 +862,6 @@ static void emitSignedInt64(SmallVectorImpl<uint64_t> &Vals, uint64_t V) { 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) { @@ -976,7 +945,23 @@ static void WriteConstants(unsigned FirstVal, unsigned LastVal, } 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(); @@ -1184,13 +1169,6 @@ static void pushValue(const Value *V, unsigned InstID, 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) { @@ -1314,63 +1292,16 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, 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: diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 086313b733..0971e8a926 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -49,7 +49,6 @@ #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" @@ -1618,8 +1617,7 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, } 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(); @@ -1627,9 +1625,9 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, 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)); @@ -2145,7 +2143,7 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, 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; } @@ -2179,7 +2177,7 @@ static inline bool areJTsAllowed(const TargetLowering &TLI) { 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); } @@ -2246,7 +2244,7 @@ bool SelectionDAGBuilder::handleJTSwitchCase(CaseRec &CR, 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; @@ -2420,7 +2418,7 @@ bool SelectionDAGBuilder::handleBTSplitSwitchCase(CaseRec& CR, // 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); @@ -2493,7 +2491,7 @@ bool SelectionDAGBuilder::handleBitTestsSwitchCase(CaseRec& CR, // 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; @@ -2568,12 +2566,7 @@ bool SelectionDAGBuilder::handleBitTestsSwitchCase(CaseRec& CR, /// 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 @@ -2582,27 +2575,40 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& 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; diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index e995424527..6463ecaca5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -182,6 +182,17 @@ private: 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; diff --git a/lib/ExecutionEngine/Interpreter/Execution.cpp b/lib/ExecutionEngine/Interpreter/Execution.cpp index e02ba15ab1..fb86cb2e78 100644 --- a/lib/ExecutionEngine/Interpreter/Execution.cpp +++ b/lib/ExecutionEngine/Interpreter/Execution.cpp @@ -898,40 +898,11 @@ void Interpreter::visitSwitchInst(SwitchInst &I) { // 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); diff --git a/lib/IR/Instructions.cpp b/lib/IR/Instructions.cpp index 205cb43e39..37b6782580 100644 --- a/lib/IR/Instructions.cpp +++ b/lib/IR/Instructions.cpp @@ -3267,7 +3267,6 @@ SwitchInst::SwitchInst(const SwitchInst &SI) OL[i] = InOL[i]; OL[i+1] = InOL[i+1]; } - TheSubsets = SI.TheSubsets; SubclassOptionalData = SI.SubclassOptionalData; } @@ -3279,16 +3278,6 @@ SwitchInst::~SwitchInst() { /// 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) @@ -3296,17 +3285,14 @@ void SwitchInst::addCase(IntegersSubset& OnVal, BasicBlock *Dest) { // 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!!!"); @@ -3323,16 +3309,6 @@ void SwitchInst::removeCase(CaseIt& i) { // 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; } diff --git a/lib/IR/Verifier.cpp b/lib/IR/Verifier.cpp index 64b7aaa9a7..d939084052 100644 --- a/lib/IR/Verifier.cpp +++ b/lib/IR/Verifier.cpp @@ -1168,27 +1168,12 @@ void Verifier::visitSwitchInst(SwitchInst &SI) { // 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); diff --git a/lib/Target/CppBackend/CPPBackend.cpp b/lib/Target/CppBackend/CPPBackend.cpp index ace4b746db..6f27af45a1 100644 --- a/lib/Target/CppBackend/CPPBackend.cpp +++ b/lib/Target/CppBackend/CPPBackend.cpp @@ -1140,7 +1140,7 @@ void CppWriter::printInstruction(const Instruction *I, 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) << ", " diff --git a/lib/Transforms/Instrumentation/DebugIR.cpp b/lib/Transforms/Instrumentation/DebugIR.cpp index 651381d88b..9489bb2556 100644 --- a/lib/Transforms/Instrumentation/DebugIR.cpp +++ b/lib/Transforms/Instrumentation/DebugIR.cpp @@ -25,6 +25,7 @@ #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" diff --git a/lib/Transforms/Utils/CodeExtractor.cpp b/lib/Transforms/Utils/CodeExtractor.cpp index 82013f95f2..6f00864436 100644 --- a/lib/Transforms/Utils/CodeExtractor.cpp +++ b/lib/Transforms/Utils/CodeExtractor.cpp @@ -665,8 +665,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 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; } } diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index f2fac5e930..8f7314d9ca 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -196,33 +196,28 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // 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; } diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp index 955b853533..2d2a8a54a0 100644 --- a/lib/Transforms/Utils/LowerSwitch.cpp +++ b/lib/Transforms/Utils/LowerSwitch.cpp @@ -66,6 +66,18 @@ namespace { 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; @@ -147,7 +159,7 @@ BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, 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); @@ -222,34 +234,40 @@ BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, // 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 diff --git a/test/Bitcode/2012-05-07-SwitchInstRangesSupport.ll b/test/Bitcode/2012-05-07-SwitchInstRangesSupport.ll deleted file mode 100644 index 583b9a853b..0000000000 --- a/test/Bitcode/2012-05-07-SwitchInstRangesSupport.ll +++ /dev/null @@ -1,33 +0,0 @@ -; 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 -} - diff --git a/test/Bitcode/case-ranges-3.3.ll b/test/Bitcode/case-ranges-3.3.ll new file mode 100644 index 0000000000..6e1d0a69a5 --- /dev/null +++ b/test/Bitcode/case-ranges-3.3.ll @@ -0,0 +1,67 @@ +; 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 +} diff --git a/test/Bitcode/case-ranges-3.3.ll.bc b/test/Bitcode/case-ranges-3.3.ll.bc Binary files differnew file mode 100644 index 0000000000..998f7475a4 --- /dev/null +++ b/test/Bitcode/case-ranges-3.3.ll.bc diff --git a/test/Transforms/LowerSwitch/feature.ll b/test/Transforms/LowerSwitch/feature.ll index cc77d3c44d..e85f03ee5c 100644 --- a/test/Transforms/LowerSwitch/feature.ll +++ b/test/Transforms/LowerSwitch/feature.ll @@ -7,88 +7,88 @@ ;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) { diff --git a/tools/llvm-diff/DifferenceEngine.cpp b/tools/llvm-diff/DifferenceEngine.cpp index 4b11315b08..ba15667d8c 100644 --- a/tools/llvm-diff/DifferenceEngine.cpp +++ b/tools/llvm-diff/DifferenceEngine.cpp @@ -316,15 +316,15 @@ class FunctionDifferenceEngine { 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()); @@ -336,7 +336,7 @@ class FunctionDifferenceEngine { } } 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; diff --git a/unittests/IR/WaymarkTest.cpp b/unittests/IR/WaymarkTest.cpp index cf7d76dffc..9a9b4a2ad4 100644 --- a/unittests/IR/WaymarkTest.cpp +++ b/unittests/IR/WaymarkTest.cpp @@ -9,6 +9,7 @@ // 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" diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp deleted file mode 100644 index f4298bf595..0000000000 --- a/unittests/Support/IntegersSubsetTest.cpp +++ /dev/null @@ -1,326 +0,0 @@ -//===- 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); - } - } -} |