#include "llvm/DerivedTypes.h"
#include "llvm/Attributes.h"
#include "llvm/CallingConv.h"
-#include "llvm/Support/ConstantRangesSet.h"
-#include "llvm/Support/CRSBuilder.h"
+#include "llvm/Support/IntegersSubset.h"
+#include "llvm/Support/IntegersSubsetMapping.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/ErrorHandling.h"
/// Note:
/// This action invalidates case_end(). Old case_end() iterator will
/// point to the added case.
- void addCase(ConstantRangesSet& OnVal, BasicBlock *Dest);
+ 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
/// @Deprecated
ConstantIntTy *getCaseValue() {
assert(Index < SI->getNumCases() && "Index out the number of cases.");
- ConstantRangesSet CRS =
+ IntegersSubset CaseRanges =
reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
- ConstantRangesSet::Range R = CRS.getItem(0);
+ IntegersSubset::Range R = CaseRanges.getItem(0);
// FIXME: Currently we work with ConstantInt based cases.
// So return CaseValue as ConstantInt.
}
/// Resolves case value for current case.
- ConstantRangesSet getCaseValueEx() {
+ IntegersSubset getCaseValueEx() {
assert(Index < SI->getNumCases() && "Index out the number of cases.");
return reinterpret_cast<Constant*>(SI->getOperand(2 + Index*2));
}
/// @Deprecated.
void setValue(ConstantInt *V) {
assert(Index < SI->getNumCases() && "Index out the number of cases.");
- CRSBuilder CB;
+ IntegersSubsetToBB Mapping;
// FIXME: Currently we work with ConstantInt based cases.
// So inititalize IntItem container directly from ConstantInt.
- CB.add(IntItem::fromConstantInt(V));
+ Mapping.add(IntItem::fromConstantInt(V));
SI->setOperand(2 + Index*2,
- reinterpret_cast<Value*>((Constant*)CB.getCase()));
+ reinterpret_cast<Value*>((Constant*)Mapping.getCase()));
}
/// Sets the new value for current case.
- void setValueEx(ConstantRangesSet& V) {
+ void setValueEx(IntegersSubset& V) {
assert(Index < SI->getNumCases() && "Index out the number of cases.");
SI->setOperand(2 + Index*2, reinterpret_cast<Value*>((Constant*)V));
}
+++ /dev/null
-//===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-/// @file
-/// CRSBuilder allows to build and parse ConstantRangesSet objects.
-/// There is such features like add/remove range, or combine
-/// Two ConstantRangesSet object with neighboring ranges merging.
-/// Set IsReadonly=true if you want to operate with "const ConstantInt" and
-/// "const ConstantRangesSet" objects.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef CRSBUILDER_H_
-#define CRSBUILDER_H_
-
-#include "llvm/Support/ConstantRangesSet.h"
-#include <list>
-#include <map>
-#include <vector>
-
-namespace llvm {
-
-template <class SuccessorClass>
-class CRSBuilderBase {
-public:
-
- typedef ConstantRangesSet::Range RangeTy;
-
- struct RangeEx : public RangeTy {
- typedef ConstantRangesSet::Range RangeTy;
- RangeEx() : Weight(1) {}
- RangeEx(const RangeTy &R) : RangeTy(R.Low, R.High), Weight(1) {}
- RangeEx(const IntItem &C) : RangeTy(C), Weight(1) {}
- RangeEx(const IntItem &L, const IntItem &H) : RangeTy(L, H), Weight(1) {}
- RangeEx(const IntItem &L, const IntItem &H, unsigned W) :
- RangeTy(L, H), Weight(W) {}
- unsigned Weight;
- };
-
- typedef std::pair<RangeEx, SuccessorClass*> Cluster;
-
-protected:
-
- typedef std::vector<Cluster> CaseItems;
- typedef typename CaseItems::iterator CaseItemIt;
- typedef typename CaseItems::const_iterator CaseItemConstIt;
-
- 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.High->uge(RItem->first.Low);
- }
-
- 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.Low;
- if (RLow != APInt::getNullValue(RLow.getBitWidth()))
- --RLow;
- return LItem->first.High->uge(RLow);
- }
-
- void sort() {
- if (!Sorted) {
- std::sort(Items.begin(), Items.end(), ClustersCmp());
- Sorted = true;
- }
- }
-
-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;
-
- CRSBuilderBase() {
- Items.reserve(32);
- Sorted = false;
- }
-
- bool verify(RangeIterator& errItem) {
- if (Items.empty())
- return true;
- sort();
- for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
- j != e; i = j++) {
- if (isIntersected(j, i) && j->second != i->second) {
- errItem = j;
- return false;
- }
- }
- return true;
- }
-
- void optimize() {
- if (Items.size() < 2)
- return;
- sort();
- CaseItems OldItems = Items;
- Items.clear();
- IntItem *Low = &OldItems.begin()->first.Low;
- IntItem *High = &OldItems.begin()->first.High;
- unsigned Weight = 1;
- SuccessorClass *Successor = OldItems.begin()->second;
- for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
- j != e; i = j++) {
- if (isJoinable(i, j)) {
- IntItem *CurHigh = &j->first.High;
- ++Weight;
- if ((*CurHigh)->ugt(*High))
- High = CurHigh;
- } else {
- RangeEx R(*Low, *High, Weight);
- add(R, Successor);
- Low = &j->first.Low;
- High = &j->first.High;
- Weight = 1;
- 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 IntItem &C, SuccessorClass *S = 0) {
- RangeTy R(C);
- add(R, S);
- }
-
- /// Adds a range.
- void add(const IntItem &Low, const IntItem &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
- /// CRSBuilder object.
- void add(const ConstantRangesSet &CRS, SuccessorClass *S = 0) {
- for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
- RangeTy R = CRS.getItem(i);
- add(R, S);
- }
- }
-
- /// Removes items from set.
- void removeItem(RangeIterator i) { Items.erase(i); }
-
- /// Returns true if there is no ranges and values inside.
- bool empty() const { return Items.empty(); }
-
- RangeIterator begin() { return Items.begin(); }
- RangeIterator end() { return Items.end(); }
-};
-
-template <class SuccessorClass>
-class CRSBuilderT : public CRSBuilderBase<SuccessorClass> {
-public:
-
- typedef typename CRSBuilderBase<SuccessorClass>::RangeTy RangeTy;
- typedef typename CRSBuilderBase<SuccessorClass>::RangeIterator
- RangeIterator;
-
-private:
-
- typedef std::list<RangeTy> RangesCollection;
- typedef typename RangesCollection::iterator RangesCollectionIt;
-
- typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
- typedef typename CRSMap::iterator CRSMapIt;
-
- ConstantRangesSet getCase(RangesCollection& Src) {
- std::vector<Constant*> Elts;
- Elts.reserve(Src.size());
- for (RangesCollectionIt i = Src.begin(), e = Src.end(); i != e; ++i) {
- RangeTy &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.Low.toConstantInt());
- r.push_back(R.High.toConstantInt());
- } else {
- r.reserve(1);
- r.push_back(R.Low.toConstantInt());
- }
- Constant *CV = ConstantVector::get(r);
- Elts.push_back(CV);
- }
- ArrayType *ArrTy =
- ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
- Constant *Array = ConstantArray::get(ArrTy, Elts);
- return ConstantRangesSet(Array);
- }
-
-public:
-
- typedef std::pair<SuccessorClass*, ConstantRangesSet> Case;
- typedef std::list<Case> Cases;
-
- /// Builds the finalized case objects.
- void getCases(Cases& TheCases) {
- 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, getCase(i->second)));
- }
-
- /// Builds the finalized case objects ignoring successor values, as though
- /// all ranges belongs to the same successor.
- ConstantRangesSet getCase() {
- RangesCollection Ranges;
- for (RangeIterator i = this->begin(); i != this->end(); ++i)
- Ranges.push_back(i->first);
- return getCase(Ranges);
- }
-};
-
-class BasicBlock;
-typedef CRSBuilderT<BasicBlock> CRSBuilder;
-typedef CRSBuilderBase<BasicBlock> CRSBuilderConst;
-
-}
-
-#endif /* CRSBUILDER_H_ */
+++ /dev/null
-//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- 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>]. Mainly, this set is used by SwitchInst and
-/// represents case value that may contain multiple ranges for a single
-/// successor.
-///
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef CONSTANTRANGESSET_H_
-#define CONSTANTRANGESSET_H_
-
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/LLVMContext.h"
-
-namespace llvm {
-
-template <class ImplTy>
-class IntItemBase {
-protected:
- ImplTy Implementation;
- typedef IntItemBase<ImplTy> self;
-public:
-
- IntItemBase() {}
-
- IntItemBase(const ImplTy &impl) : Implementation(impl) {}
-
- // implicit
- IntItemBase(const APInt& src) : Implementation(src) {}
-
- operator const APInt&() const {
- return (const APInt&)Implementation;
- }
- bool operator<(const self& RHS) const {
- return ((const APInt&)*this).ult(RHS);
- }
- bool operator==(const self& RHS) const {
- return (const APInt&)*this == (const APInt&)RHS;
- }
- bool operator!=(const self& RHS) const {
- return (const APInt&)*this != (const APInt&)RHS;
- }
- self& operator=(const ImplTy& RHS) {
- Implementation = RHS;
- return *this;
- }
- const APInt* operator->() const {
- return &((const APInt&)Implementation);
- }
- const APInt& operator*() const {
- return ((const APInt&)Implementation);
- }
- // FIXME: Hack. Will removed.
- ImplTy& getImplementation() {
- return Implementation;
- }
-};
-
-class IntItemConstantIntImpl {
- const ConstantInt *ConstantIntVal;
-public:
- IntItemConstantIntImpl() : ConstantIntVal(0) {}
- IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {}
- IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) {
- ConstantIntVal = cast<ConstantInt>(ConstantInt::get(Ctx, src));
- }
- explicit IntItemConstantIntImpl(const APInt& src) {
- ConstantIntVal =
- cast<ConstantInt>(ConstantInt::get(llvm::getGlobalContext(), src));
- }
- operator const APInt&() const {
- return ConstantIntVal->getValue();
- }
- operator const ConstantInt*() {
- return ConstantIntVal;
- }
-};
-
-class IntItem : public IntItemBase<IntItemConstantIntImpl> {
- typedef IntItemBase<IntItemConstantIntImpl> ParentTy;
- IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {}
-public:
-
- IntItem() {}
-
- // implicit
- IntItem(const APInt& src) : ParentTy(src) {}
-
- static IntItem fromConstantInt(const ConstantInt *V) {
- IntItemConstantIntImpl Impl(V);
- return IntItem(Impl);
- }
- static IntItem fromType(Type* Ty, const APInt& V) {
- ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
- return fromConstantInt(C);
- }
- ConstantInt *toConstantInt() {
- return const_cast<ConstantInt*>((const ConstantInt*)Implementation);
- }
-};
-
-// TODO: it should be a class in next commit.
-struct IntRange {
-
- IntItem Low;
- IntItem High;
- bool IsEmpty : 1;
- bool IsSingleNumber : 1;
-// TODO:
-// public:
-
- typedef std::pair<IntRange, IntRange> SubRes;
-
- IntRange() : IsEmpty(true) {}
- IntRange(const IntRange &RHS) :
- Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
- IntRange(const IntItem &C) :
- Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
- IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
- IsEmpty(false), IsSingleNumber(false) {}
-
- bool isEmpty() const { return IsEmpty; }
- bool isSingleNumber() const { return IsSingleNumber; }
-
- const IntItem& getLow() {
- assert(!IsEmpty && "Range is empty.");
- return Low;
- }
- const IntItem& getHigh() {
- assert(!IsEmpty && "Range is empty.");
- return High;
- }
-
- bool operator<(const IntRange &RHS) const {
- assert(!IsEmpty && "Left range is empty.");
- assert(!RHS.IsEmpty && "Right range is empty.");
- if (Low->getBitWidth() == RHS.Low->getBitWidth()) {
- if (Low->eq(RHS.Low)) {
- if (High->ult(RHS.High))
- return true;
- return false;
- }
- if (Low->ult(RHS.Low))
- return true;
- return false;
- } else
- return Low->getBitWidth() < RHS.Low->getBitWidth();
- }
-
- bool operator==(const IntRange &RHS) const {
- assert(!IsEmpty && "Left range is empty.");
- assert(!RHS.IsEmpty && "Right range is empty.");
- if (Low->getBitWidth() != RHS.Low->getBitWidth())
- return false;
- return Low == RHS.Low && High == RHS.High;
- }
-
- bool operator!=(const IntRange &RHS) const {
- return !operator ==(RHS);
- }
-
- static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
- assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
- "This type of comparison requires equal bit width for LHS and RHS");
- APInt LSize = *LHS.High - *LHS.Low;
- APInt RSize = *RHS.High - *RHS.Low;
- return LSize.ult(RSize);
- }
-
- bool isInRange(const APInt &IntVal) const {
- assert(!IsEmpty && "Range is empty.");
- if (IntVal.getBitWidth() != Low->getBitWidth())
- return false;
- return IntVal.uge(Low) && IntVal.ule(High);
- }
-
- SubRes sub(const IntRange &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(IntRange(Low, High), IntRange());
-
- return Res;
- }
-
- if (Low->ult(RHS.Low)) {
- Res.first.Low = Low;
- APInt NewHigh = RHS.Low;
- --NewHigh;
- Res.first.High = NewHigh;
- }
- if (High->ugt(RHS.High)) {
- APInt NewLow = RHS.High;
- ++NewLow;
- Res.second.Low = NewLow;
- Res.second.High = High;
- }
- return Res;
- }
- };
-
-//===----------------------------------------------------------------------===//
-/// ConstantRangesSet - class that implements constant set of ranges.
-/// It is a wrapper for some real "holder" class (currently ConstantArray).
-/// It contains functions, that allows to parse "holder" like a set of ranges.
-/// Note: It is assumed that "holder" is inherited from Constant object.
-/// ConstantRangesSet may be converted to and from Constant* pointer.
-///
-class ConstantRangesSet {
- Constant *Array;
-public:
-
- bool IsWide;
-
- // implicit
- ConstantRangesSet(Constant *V) : Array(V) {
- ArrayType *ArrTy = cast<ArrayType>(Array->getType());
- VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
- IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
- IsWide = IntTy->getBitWidth() > 64;
- }
-
- operator Constant*() { return Array; }
- operator const Constant*() const { return Array; }
- Constant *operator->() { return Array; }
- const Constant *operator->() const { return Array; }
-
- typedef IntRange 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 IntItem &CheckingVal) const {
- for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
- const Constant *CV = Array->getAggregateElement(i);
- unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
- switch (VecSize) {
- case 1:
- if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
- CheckingVal)
- return true;
- break;
- case 2: {
- const APInt &Lo =
- cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
- const APInt &Hi =
- cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
- if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
- return true;
- }
- break;
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- break;
- }
- }
- return false;
- }
-
- /// Returns set's item with given index.
- Range getItem(unsigned idx) {
- Constant *CV = Array->getAggregateElement(idx);
- unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
- switch (NumEls) {
- case 1:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))));
- case 2:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(1U))));
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- return Range();
- }
- }
-
- const Range getItem(unsigned idx) const {
- const Constant *CV = Array->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();
- }
- }
-
- /// Return number of items (ranges) stored in set.
- unsigned getNumItems() const {
- return cast<ArrayType>(Array->getType())->getNumElements();
- }
-
- bool isWideNumberFormat() const { return IsWide; }
-
- bool isSingleNumber(unsigned idx) const {
- Constant *CV = Array->getAggregateElement(idx);
- return cast<VectorType>(CV->getType())->getNumElements() == 1;
- }
-
- /// 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(getItem(0).Low->getBitWidth(), 0);
- for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
- const APInt &Low = getItem(i).Low;
- const APInt &High = getItem(i).High;
- const APInt &S = High - Low;
- 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(getItem(0).Low->getBitWidth(), 0);
- for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
- const APInt &Low = getItem(i).Low;
- const APInt &High = getItem(i).High;
- const APInt& S = High - Low;
- APInt oldSz = sz;
- sz += S;
- if (oldSz.uge(i) && sz.ult(i)) {
- APInt Res = Low;
- APInt Offset(oldSz.getBitWidth(), i);
- Offset -= oldSz;
- Res += Offset;
- return Res;
- }
- }
- assert(0 && "Index exceeds high border.");
- return sz;
- }
-};
-
-}
-
-#endif /* CONSTANTRANGESSET_H_ */
--- /dev/null
+//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- 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>]. Mainly, this set is used by SwitchInst and
+/// represents case value that may contain multiple ranges for a single
+/// successor.
+///
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CONSTANTRANGESSET_H_
+#define CONSTANTRANGESSET_H_
+
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/LLVMContext.h"
+
+namespace llvm {
+
+template <class ImplTy>
+class IntItemBase {
+protected:
+ ImplTy Implementation;
+ typedef IntItemBase<ImplTy> self;
+public:
+
+ IntItemBase() {}
+
+ IntItemBase(const ImplTy &impl) : Implementation(impl) {}
+
+ // implicit
+ IntItemBase(const APInt& src) : Implementation(src) {}
+
+ operator const APInt&() const {
+ return (const APInt&)Implementation;
+ }
+ bool operator<(const self& RHS) const {
+ return ((const APInt&)*this).ult(RHS);
+ }
+ bool operator==(const self& RHS) const {
+ return (const APInt&)*this == (const APInt&)RHS;
+ }
+ bool operator!=(const self& RHS) const {
+ return (const APInt&)*this != (const APInt&)RHS;
+ }
+ self& operator=(const ImplTy& RHS) {
+ Implementation = RHS;
+ return *this;
+ }
+ const APInt* operator->() const {
+ return &((const APInt&)Implementation);
+ }
+ const APInt& operator*() const {
+ return ((const APInt&)Implementation);
+ }
+ // FIXME: Hack. Will removed.
+ ImplTy& getImplementation() {
+ return Implementation;
+ }
+};
+
+class IntItemConstantIntImpl {
+ const ConstantInt *ConstantIntVal;
+public:
+ IntItemConstantIntImpl() : ConstantIntVal(0) {}
+ IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {}
+ IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) {
+ ConstantIntVal = cast<ConstantInt>(ConstantInt::get(Ctx, src));
+ }
+ explicit IntItemConstantIntImpl(const APInt& src) {
+ ConstantIntVal =
+ cast<ConstantInt>(ConstantInt::get(llvm::getGlobalContext(), src));
+ }
+ operator const APInt&() const {
+ return ConstantIntVal->getValue();
+ }
+ operator const ConstantInt*() {
+ return ConstantIntVal;
+ }
+};
+
+class IntItem : public IntItemBase<IntItemConstantIntImpl> {
+ typedef IntItemBase<IntItemConstantIntImpl> ParentTy;
+ IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {}
+public:
+
+ IntItem() {}
+
+ // implicit
+ IntItem(const APInt& src) : ParentTy(src) {}
+
+ static IntItem fromConstantInt(const ConstantInt *V) {
+ IntItemConstantIntImpl Impl(V);
+ return IntItem(Impl);
+ }
+ static IntItem fromType(Type* Ty, const APInt& V) {
+ ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
+ return fromConstantInt(C);
+ }
+ ConstantInt *toConstantInt() {
+ return const_cast<ConstantInt*>((const ConstantInt*)Implementation);
+ }
+};
+
+// TODO: it should be a class in next commit.
+struct IntRange {
+
+ IntItem Low;
+ IntItem High;
+ bool IsEmpty : 1;
+ bool IsSingleNumber : 1;
+// TODO:
+// public:
+
+ typedef std::pair<IntRange, IntRange> SubRes;
+
+ IntRange() : IsEmpty(true) {}
+ IntRange(const IntRange &RHS) :
+ Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
+ IntRange(const IntItem &C) :
+ Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
+ IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
+ IsEmpty(false), IsSingleNumber(false) {}
+
+ bool isEmpty() const { return IsEmpty; }
+ bool isSingleNumber() const { return IsSingleNumber; }
+
+ const IntItem& getLow() {
+ assert(!IsEmpty && "Range is empty.");
+ return Low;
+ }
+ const IntItem& getHigh() {
+ assert(!IsEmpty && "Range is empty.");
+ return High;
+ }
+
+ bool operator<(const IntRange &RHS) const {
+ assert(!IsEmpty && "Left range is empty.");
+ assert(!RHS.IsEmpty && "Right range is empty.");
+ if (Low->getBitWidth() == RHS.Low->getBitWidth()) {
+ if (Low->eq(RHS.Low)) {
+ if (High->ult(RHS.High))
+ return true;
+ return false;
+ }
+ if (Low->ult(RHS.Low))
+ return true;
+ return false;
+ } else
+ return Low->getBitWidth() < RHS.Low->getBitWidth();
+ }
+
+ bool operator==(const IntRange &RHS) const {
+ assert(!IsEmpty && "Left range is empty.");
+ assert(!RHS.IsEmpty && "Right range is empty.");
+ if (Low->getBitWidth() != RHS.Low->getBitWidth())
+ return false;
+ return Low == RHS.Low && High == RHS.High;
+ }
+
+ bool operator!=(const IntRange &RHS) const {
+ return !operator ==(RHS);
+ }
+
+ static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
+ assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
+ "This type of comparison requires equal bit width for LHS and RHS");
+ APInt LSize = *LHS.High - *LHS.Low;
+ APInt RSize = *RHS.High - *RHS.Low;
+ return LSize.ult(RSize);
+ }
+
+ bool isInRange(const APInt &IntVal) const {
+ assert(!IsEmpty && "Range is empty.");
+ if (IntVal.getBitWidth() != Low->getBitWidth())
+ return false;
+ return IntVal.uge(Low) && IntVal.ule(High);
+ }
+
+ SubRes sub(const IntRange &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(IntRange(Low, High), IntRange());
+
+ return Res;
+ }
+
+ if (Low->ult(RHS.Low)) {
+ Res.first.Low = Low;
+ APInt NewHigh = RHS.Low;
+ --NewHigh;
+ Res.first.High = NewHigh;
+ }
+ if (High->ugt(RHS.High)) {
+ APInt NewLow = RHS.High;
+ ++NewLow;
+ Res.second.Low = NewLow;
+ Res.second.High = High;
+ }
+ return Res;
+ }
+ };
+
+//===----------------------------------------------------------------------===//
+/// ConstantRangesSet - class that implements constant set of ranges.
+/// It is a wrapper for some real "holder" class (currently ConstantArray).
+/// It contains functions, that allows to parse "holder" like a set of ranges.
+/// Note: It is assumed that "holder" is inherited from Constant object.
+/// ConstantRangesSet may be converted to and from Constant* pointer.
+///
+class IntegersSubset {
+ Constant *Array;
+public:
+
+ bool IsWide;
+
+ // implicit
+ IntegersSubset(Constant *V) : Array(V) {
+ ArrayType *ArrTy = cast<ArrayType>(Array->getType());
+ VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
+ IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
+ IsWide = IntTy->getBitWidth() > 64;
+ }
+
+ operator Constant*() { return Array; }
+ operator const Constant*() const { return Array; }
+ Constant *operator->() { return Array; }
+ const Constant *operator->() const { return Array; }
+
+ typedef IntRange 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 IntItem &CheckingVal) const {
+ for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
+ const Constant *CV = Array->getAggregateElement(i);
+ unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
+ switch (VecSize) {
+ case 1:
+ if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
+ CheckingVal)
+ return true;
+ break;
+ case 2: {
+ const APInt &Lo =
+ cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
+ const APInt &Hi =
+ cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
+ if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
+ return true;
+ }
+ break;
+ default:
+ assert(0 && "Only pairs and single numbers are allowed here.");
+ break;
+ }
+ }
+ return false;
+ }
+
+ /// Returns set's item with given index.
+ Range getItem(unsigned idx) {
+ Constant *CV = Array->getAggregateElement(idx);
+ unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
+ switch (NumEls) {
+ case 1:
+ return Range(IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(0U))));
+ case 2:
+ return Range(IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(0U))),
+ IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(1U))));
+ default:
+ assert(0 && "Only pairs and single numbers are allowed here.");
+ return Range();
+ }
+ }
+
+ const Range getItem(unsigned idx) const {
+ const Constant *CV = Array->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();
+ }
+ }
+
+ /// Return number of items (ranges) stored in set.
+ unsigned getNumItems() const {
+ return cast<ArrayType>(Array->getType())->getNumElements();
+ }
+
+ bool isWideNumberFormat() const { return IsWide; }
+
+ bool isSingleNumber(unsigned idx) const {
+ Constant *CV = Array->getAggregateElement(idx);
+ return cast<VectorType>(CV->getType())->getNumElements() == 1;
+ }
+
+ /// 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(getItem(0).Low->getBitWidth(), 0);
+ for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
+ const APInt &Low = getItem(i).Low;
+ const APInt &High = getItem(i).High;
+ const APInt &S = High - Low;
+ 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(getItem(0).Low->getBitWidth(), 0);
+ for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
+ const APInt &Low = getItem(i).Low;
+ const APInt &High = getItem(i).High;
+ const APInt& S = High - Low;
+ APInt oldSz = sz;
+ sz += S;
+ if (oldSz.uge(i) && sz.ult(i)) {
+ APInt Res = Low;
+ APInt Offset(oldSz.getBitWidth(), i);
+ Offset -= oldSz;
+ Res += Offset;
+ return Res;
+ }
+ }
+ assert(0 && "Index exceeds high border.");
+ return sz;
+ }
+};
+
+}
+
+#endif /* CONSTANTRANGESSET_H_ */
--- /dev/null
+//===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// @file
+/// CRSBuilder allows to build and parse ConstantRangesSet objects.
+/// There is such features like add/remove range, or combine
+/// Two ConstantRangesSet object with neighboring ranges merging.
+/// Set IsReadonly=true if you want to operate with "const ConstantInt" and
+/// "const ConstantRangesSet" objects.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CRSBUILDER_H_
+#define CRSBUILDER_H_
+
+#include "llvm/Support/IntegersSubset.h"
+#include <list>
+#include <map>
+#include <vector>
+
+namespace llvm {
+
+template <class SuccessorClass>
+class IntegersSubsetMapping {
+public:
+
+ typedef IntegersSubset::Range RangeTy;
+
+ struct RangeEx : public RangeTy {
+ typedef IntegersSubset::Range RangeTy;
+ RangeEx() : Weight(1) {}
+ RangeEx(const RangeTy &R) : RangeTy(R.Low, R.High), Weight(1) {}
+ RangeEx(const IntItem &C) : RangeTy(C), Weight(1) {}
+ RangeEx(const IntItem &L, const IntItem &H) : RangeTy(L, H), Weight(1) {}
+ RangeEx(const IntItem &L, const IntItem &H, unsigned W) :
+ RangeTy(L, H), Weight(W) {}
+ unsigned Weight;
+ };
+
+ typedef std::pair<RangeEx, SuccessorClass*> Cluster;
+
+protected:
+
+ typedef std::vector<Cluster> CaseItems;
+ typedef typename CaseItems::iterator CaseItemIt;
+ typedef typename CaseItems::const_iterator CaseItemConstIt;
+
+ typedef std::list<RangeTy> RangesCollection;
+ typedef typename RangesCollection::iterator RangesCollectionIt;
+
+ 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.High->uge(RItem->first.Low);
+ }
+
+ 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.Low;
+ if (RLow != APInt::getNullValue(RLow.getBitWidth()))
+ --RLow;
+ return LItem->first.High->uge(RLow);
+ }
+
+ void sort() {
+ if (!Sorted) {
+ std::sort(Items.begin(), Items.end(), ClustersCmp());
+ Sorted = true;
+ }
+ }
+
+ IntegersSubset getCase(RangesCollection& Src) {
+ std::vector<Constant*> Elts;
+ Elts.reserve(Src.size());
+ for (RangesCollectionIt i = Src.begin(), e = Src.end(); i != e; ++i) {
+ RangeTy &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.Low.toConstantInt());
+ r.push_back(R.High.toConstantInt());
+ } else {
+ r.reserve(1);
+ r.push_back(R.Low.toConstantInt());
+ }
+ Constant *CV = ConstantVector::get(r);
+ Elts.push_back(CV);
+ }
+ ArrayType *ArrTy =
+ ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
+ Constant *Array = ConstantArray::get(ArrTy, Elts);
+ return IntegersSubset(Array);
+ }
+
+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*, IntegersSubset> Case;
+ typedef std::list<Case> Cases;
+
+ IntegersSubsetMapping() {
+ Items.reserve(32);
+ Sorted = false;
+ }
+
+ bool verify(RangeIterator& errItem) {
+ if (Items.empty())
+ return true;
+ sort();
+ for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
+ j != e; i = j++) {
+ if (isIntersected(j, i) && j->second != i->second) {
+ errItem = j;
+ return false;
+ }
+ }
+ return true;
+ }
+
+ void optimize() {
+ if (Items.size() < 2)
+ return;
+ sort();
+ CaseItems OldItems = Items;
+ Items.clear();
+ IntItem *Low = &OldItems.begin()->first.Low;
+ IntItem *High = &OldItems.begin()->first.High;
+ unsigned Weight = 1;
+ SuccessorClass *Successor = OldItems.begin()->second;
+ for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
+ j != e; i = j++) {
+ if (isJoinable(i, j)) {
+ IntItem *CurHigh = &j->first.High;
+ ++Weight;
+ if ((*CurHigh)->ugt(*High))
+ High = CurHigh;
+ } else {
+ RangeEx R(*Low, *High, Weight);
+ add(R, Successor);
+ Low = &j->first.Low;
+ High = &j->first.High;
+ Weight = 1;
+ 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 IntItem &C, SuccessorClass *S = 0) {
+ RangeTy R(C);
+ add(R, S);
+ }
+
+ /// Adds a range.
+ void add(const IntItem &Low, const IntItem &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
+ /// CRSBuilder object.
+ void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
+ for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
+ RangeTy R = CRS.getItem(i);
+ add(R, S);
+ }
+ }
+
+ /// Removes items from set.
+ void removeItem(RangeIterator i) { Items.erase(i); }
+
+ /// Builds the finalized case objects.
+ void getCases(Cases& TheCases) {
+ 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, getCase(i->second)));
+ }
+
+ /// Builds the finalized case objects ignoring successor values, as though
+ /// all ranges belongs to the same successor.
+ IntegersSubset getCase() {
+ RangesCollection Ranges;
+ for (RangeIterator i = this->begin(); i != this->end(); ++i)
+ Ranges.push_back(i->first);
+ return getCase(Ranges);
+ }
+
+ /// Returns true if there is no ranges and values inside.
+ bool empty() const { return Items.empty(); }
+
+ RangeIterator begin() { return Items.begin(); }
+ RangeIterator end() { return Items.end(); }
+};
+
+class BasicBlock;
+typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
+
+}
+
+#endif /* CRSBUILDER_H_ */
unsigned CurIdx = 5;
for (unsigned i = 0; i != NumCases; ++i) {
- CRSBuilder CaseBuilder;
+ IntegersSubsetToBB CaseBuilder;
unsigned NumItems = Record[CurIdx++];
for (unsigned ci = 0; ci != NumItems; ++ci) {
bool isSingleNumber = Record[CurIdx++];
CaseBuilder.add(IntItem::fromType(OpTy, Low));
}
BasicBlock *DestBB = getBasicBlock(Record[CurIdx++]);
- ConstantRangesSet Case = CaseBuilder.getCase();
+ IntegersSubset Case = CaseBuilder.getCase();
SI->addCase(Case, DestBB);
}
uint16_t Hash = SI->hash();
Vals64.push_back(SI.getNumCases());
for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end();
i != e; ++i) {
- ConstantRangesSet CRS = i.getCaseValueEx();
- Vals64.push_back(CRS.getNumItems());
- for (unsigned ri = 0, rn = CRS.getNumItems(); ri != rn; ++ri) {
- ConstantRangesSet::Range r = CRS.getItem(ri);
+ IntegersSubset CaseRanges = i.getCaseValueEx();
+ Vals64.push_back(CaseRanges.getNumItems());
+ for (unsigned ri = 0, rn = CaseRanges.getNumItems(); ri != rn; ++ri) {
+ IntegersSubset::Range r = CaseRanges.getItem(ri);
- Vals64.push_back(CRS.isSingleNumber(ri));
+ Vals64.push_back(CaseRanges.isSingleNumber(ri));
const APInt &Low = r.Low;
const APInt &High = r.High;
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/CRSBuilder.h"
+#include "llvm/Support/IntegersSubsetMapping.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
/// Use a shorter form of declaration, and also
/// show the we want to use CRSBuilder as Clusterifier.
- typedef CRSBuilderBase<MachineBasicBlock> Clusterifier;
+ typedef IntegersSubsetMapping<MachineBasicBlock> Clusterifier;
Clusterifier TheClusterifier;
// 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) {
- ConstantRangesSet Case = i.getCaseValueEx();
+ IntegersSubset Case = i.getCaseValueEx();
for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) {
- ConstantRangesSet::Range r = Case.getItem(n);
+ IntegersSubset::Range r = Case.getItem(n);
// FIXME: Currently work with ConstantInt based numbers.
const ConstantInt *LowCI = r.Low.getImplementation();
const ConstantInt *HighCI = r.High.getImplementation();
nl(Out);
for (SwitchInst::ConstCaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
- const ConstantRangesSet CaseVal = i.getCaseValueEx();
+ const IntegersSubset CaseVal = i.getCaseValueEx();
const BasicBlock *BB = i.getCaseSuccessor();
Out << iName << "->addCase("
<< getOpName(CaseVal) << ", "
// 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();
- ConstantRangesSet CRS = FirstCase.getCaseValueEx();
- if (CRS.getNumItems() == 1 && CRS.isSingleNumber(0)) {
+ IntegersSubset CaseRanges = FirstCase.getCaseValueEx();
+ if (CaseRanges.getNumItems() == 1 && CaseRanges.isSingleNumber(0)) {
// FIXME: Currently work with ConstantInt based numbers.
Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
- CRS.getItem(0).Low.toConstantInt(),
+ CaseRanges.getItem(0).Low.toConstantInt(),
"cond");
// Insert the new branch.
// Clusterify - Transform simple list of Cases into list of CaseRange's
unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
- CRSBuilder TheClusterifier;
+ IntegersSubsetToBB TheClusterifier;
// Start with "simple" cases
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
BasicBlock *SuccBB = i.getCaseSuccessor();
- ConstantRangesSet CRS = i.getCaseValueEx();
- TheClusterifier.add(CRS, SuccBB);
+ IntegersSubset CaseRanges = i.getCaseValueEx();
+ TheClusterifier.add(CaseRanges, SuccBB);
}
TheClusterifier.optimize();
size_t numCmps = 0;
- for (CRSBuilder::RangeIterator i = TheClusterifier.begin(),
+ for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(),
e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- CRSBuilder::Cluster &C = *i;
+ IntegersSubsetToBB::Cluster &C = *i;
// FIXME: Currently work with ConstantInt based numbers.
// Changing it to APInt based is a pretty heavy for this commit.
/// addCase - Add an entry to the switch instruction...
///
void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
- CRSBuilder CB;
+ IntegersSubsetToBB Mapping;
// FIXME: Currently we work with ConstantInt based cases.
// So inititalize IntItem container directly from ConstantInt.
- CB.add(IntItem::fromConstantInt(OnVal));
- ConstantRangesSet CRS = CB.getCase();
- addCase(CRS, Dest);
+ Mapping.add(IntItem::fromConstantInt(OnVal));
+ IntegersSubset CaseRanges = Mapping.getCase();
+ addCase(CaseRanges, Dest);
}
-void SwitchInst::addCase(ConstantRangesSet& OnVal, BasicBlock *Dest) {
+void SwitchInst::addCase(IntegersSubset& OnVal, BasicBlock *Dest) {
unsigned NewCaseIdx = getNumCases();
unsigned OpNo = NumOperands;
if (OpNo+2 > ReservedSpace)
// have the same type as the switched-on value.
Type *SwitchTy = SI.getCondition()->getType();
IntegerType *IntTy = cast<IntegerType>(SwitchTy);
- CRSBuilder Builder;
- std::map<ConstantRangesSet::Range, unsigned> RangeSetMap;
+ IntegersSubsetToBB Mapping;
+ std::map<IntegersSubset::Range, unsigned> RangeSetMap;
for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) {
- ConstantRangesSet RS = i.getCaseValueEx();
- for (unsigned ri = 0, rie = RS.getNumItems(); ri < rie; ++ri) {
- ConstantRangesSet::Range r = RS.getItem(ri);
+ IntegersSubset CaseRanges = i.getCaseValueEx();
+ for (unsigned ri = 0, rie = CaseRanges.getNumItems(); ri < rie; ++ri) {
+ IntegersSubset::Range r = CaseRanges.getItem(ri);
Assert1(r.Low->getBitWidth() == IntTy->getBitWidth(),
"Switch constants must all be same type as switch value!", &SI);
Assert1(r.High->getBitWidth() == IntTy->getBitWidth(),
"Switch constants must all be same type as switch value!", &SI);
- Builder.add(r);
+ Mapping.add(r);
RangeSetMap[r] = i.getCaseIndex();
}
}
- CRSBuilder::RangeIterator errItem;
- if (!Builder.verify(errItem)) {
+ 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());
for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end();
I != E; ++I) {
- ConstantRangesSet CaseValue = I.getCaseValueEx();
+ IntegersSubset CaseValue = I.getCaseValueEx();
BasicBlock *LCase = LCases[CaseValue];
if (LCase) {
if (TryUnify) tryUnify(LCase, I.getCaseSuccessor());
projects / oota-llvm.git / commitdiff