summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/utils/TableGen/CodeGenDAGPatterns.cpp80
-rw-r--r--llvm/utils/TableGen/CodeGenDAGPatterns.h172
-rw-r--r--llvm/utils/TableGen/InfoByHwMode.h15
3 files changed, 222 insertions, 45 deletions
diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
index 86238b6c847..633b5b349b8 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -43,15 +43,16 @@ static inline bool isScalar(MVT VT) {
return !VT.isVector();
}
-template <typename T, typename Predicate>
-static bool berase_if(std::set<T> &S, Predicate P) {
+template <typename Predicate>
+static bool berase_if(MachineValueTypeSet &S, Predicate P) {
bool Erased = false;
- for (auto I = S.begin(); I != S.end(); ) {
- if (P(*I)) {
- Erased = true;
- I = S.erase(I);
- } else
- ++I;
+ // It is ok to iterate over MachineValueTypeSet and remove elements from it
+ // at the same time.
+ for (MVT T : S) {
+ if (!P(T))
+ continue;
+ Erased = true;
+ S.erase(T);
}
return Erased;
}
@@ -125,7 +126,7 @@ bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {
unsigned M = I.first;
if (M == DefaultMode || hasMode(M))
continue;
- Map[M] = Map[DefaultMode];
+ Map.insert({M, Map.at(DefaultMode)});
Changed = true;
}
}
@@ -183,7 +184,9 @@ std::string TypeSetByHwMode::getAsString() const {
}
std::string TypeSetByHwMode::getAsString(const SetType &S) {
- std::vector<MVT> Types(S.begin(), S.end());
+ std::vector<MVT> Types;
+ for (MVT T : S)
+ Types.push_back(T);
array_pod_sort(Types.begin(), Types.end());
std::stringstream str;
@@ -202,6 +205,12 @@ bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {
if (HaveDefault != VTS.hasDefault())
return false;
+ if (isSimple()) {
+ if (VTS.isSimple())
+ return *begin() == *VTS.begin();
+ return false;
+ }
+
std::set<unsigned> Modes;
for (auto &I : *this)
Modes.insert(I.first);
@@ -253,18 +262,31 @@ bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
// For example
// { iPTR } * { i32 } -> { i32 }
// { iPTR } * { i32 i64 } -> { iPTR }
-
+ // and
+ // { iPTR i32 } * { i32 } -> { i32 }
+ // { iPTR i32 } * { i32 i64 } -> { i32 i64 }
+ // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 }
+
+ // Compute the difference between the two sets in such a way that the
+ // iPTR is in the set that is being subtracted. This is to see if there
+ // are any extra scalars in the set without iPTR that are not in the
+ // set containing iPTR. Then the iPTR could be considered a "wildcard"
+ // matching these scalars. If there is only one such scalar, it would
+ // replace the iPTR, if there are more, the iPTR would be retained.
SetType Diff;
if (InP) {
- std::copy_if(Out.begin(), Out.end(), std::inserter(Diff, Diff.end()),
- [&In](MVT T) { return !In.count(T); });
+ Diff = Out;
+ berase_if(Diff, [&In](MVT T) { return In.count(T); });
+ // Pre-remove these elements and rely only on InP/OutP to determine
+ // whether a change has been made.
berase_if(Out, [&Diff](MVT T) { return Diff.count(T); });
} else {
- std::copy_if(In.begin(), In.end(), std::inserter(Diff, Diff.end()),
- [&Out](MVT T) { return !Out.count(T); });
+ Diff = In;
+ berase_if(Diff, [&Out](MVT T) { return Out.count(T); });
Out.erase(MVT::iPTR);
}
+ // The actual intersection.
bool Changed = berase_if(Out, Int);
unsigned NumD = Diff.size();
if (NumD == 0)
@@ -276,8 +298,9 @@ bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
// being replaced).
Changed |= OutP;
} else {
+ // Multiple elements from Out are now replaced with iPTR.
Out.insert(MVT::iPTR);
- Changed |= InP;
+ Changed |= !OutP;
}
return Changed;
}
@@ -758,13 +781,12 @@ void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) {
void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
const TypeSetByHwMode::SetType &Legal) {
std::set<MVT> Ovs;
- for (auto I = Out.begin(); I != Out.end(); ) {
- if (I->isOverloaded()) {
- Ovs.insert(*I);
- I = Out.erase(I);
+ for (MVT T : Out) {
+ if (!T.isOverloaded())
continue;
- }
- ++I;
+ Ovs.insert(T);
+ // MachineValueTypeSet allows iteration and erasing.
+ Out.erase(T);
}
for (MVT Ov : Ovs) {
@@ -805,13 +827,15 @@ void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
}
TypeSetByHwMode TypeInfer::getLegalTypes() {
+ if (!LegalTypesCached) {
+ // Stuff all types from all modes into the default mode.
+ const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();
+ for (const auto &I : LTS)
+ LegalCache.insert(I.second);
+ LegalTypesCached = true;
+ }
TypeSetByHwMode VTS;
- TypeSetByHwMode::SetType &DS = VTS.getOrCreate(DefaultMode);
- const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();
-
- // Stuff all types from all modes into the default mode.
- for (const auto &I : LTS)
- DS.insert(I.second.begin(), I.second.end());
+ VTS.getOrCreate(DefaultMode) = LegalCache;
return VTS;
}
diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.h b/llvm/utils/TableGen/CodeGenDAGPatterns.h
index bc25419e556..310fbfcc790 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.h
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.h
@@ -21,24 +21,160 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
#include <algorithm>
+#include <array>
#include <map>
#include <set>
#include <vector>
namespace llvm {
- class Record;
- class Init;
- class ListInit;
- class DagInit;
- class SDNodeInfo;
- class TreePattern;
- class TreePatternNode;
- class CodeGenDAGPatterns;
- class ComplexPattern;
-
-struct TypeSetByHwMode : public InfoByHwMode<std::set<MVT>> {
- typedef std::set<MVT> SetType;
+
+class Record;
+class Init;
+class ListInit;
+class DagInit;
+class SDNodeInfo;
+class TreePattern;
+class TreePatternNode;
+class CodeGenDAGPatterns;
+class ComplexPattern;
+
+/// This represents a set of MVTs. Since the underlying type for the MVT
+/// is uint8_t, there are at most 256 values. To reduce the number of memory
+/// allocations and deallocations, represent the set as a sequence of bits.
+/// To reduce the allocations even further, make MachineValueTypeSet own
+/// the storage and use std::array as the bit container.
+struct MachineValueTypeSet {
+ static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
+ uint8_t>::value,
+ "Change uint8_t here to the SimpleValueType's type");
+ static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1;
+ using WordType = uint64_t;
+ static unsigned constexpr WordWidth = 8*sizeof(WordType);
+ static unsigned constexpr NumWords = Capacity/WordWidth;
+ static_assert(NumWords*WordWidth == Capacity,
+ "Capacity should be a multiple of WordWidth");
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ MachineValueTypeSet() {
+ clear();
+ }
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ unsigned size() const {
+ unsigned Count = 0;
+ for (WordType W : Words)
+ Count += countPopulation(W);
+ return Count;
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ void clear() {
+ std::memset(Words.data(), 0, NumWords*sizeof(WordType));
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ bool empty() const {
+ for (WordType W : Words)
+ if (W != 0)
+ return false;
+ return true;
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ unsigned count(MVT T) const {
+ return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
+ }
+ std::pair<MachineValueTypeSet&,bool> insert(MVT T) {
+ bool V = count(T.SimpleTy);
+ Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
+ return {*this, V};
+ }
+ MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
+ for (unsigned i = 0; i != NumWords; ++i)
+ Words[i] |= S.Words[i];
+ return *this;
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ void erase(MVT T) {
+ Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
+ }
+
+ struct const_iterator {
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ MVT operator*() const {
+ assert(Pos != Capacity);
+ return MVT::SimpleValueType(Pos);
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
+ Pos = End ? Capacity : find_from_pos(0);
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ const_iterator &operator++() {
+ assert(Pos != Capacity);
+ Pos = find_from_pos(Pos+1);
+ return *this;
+ }
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ bool operator==(const const_iterator &It) const {
+ return Set == It.Set && Pos == It.Pos;
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ bool operator!=(const const_iterator &It) const {
+ return !operator==(It);
+ }
+
+ private:
+ unsigned find_from_pos(unsigned P) const {
+ unsigned SkipWords = P / WordWidth;
+ unsigned SkipBits = P % WordWidth;
+ unsigned Count = SkipWords * WordWidth;
+
+ // If P is in the middle of a word, process it manually here, because
+ // the trailing bits need to be masked off to use findFirstSet.
+ if (SkipBits != 0) {
+ WordType W = Set->Words[SkipWords];
+ W &= maskLeadingOnes<WordType>(WordWidth-SkipBits);
+ if (W != 0)
+ return Count + findFirstSet(W);
+ Count += WordWidth;
+ SkipWords++;
+ }
+
+ for (unsigned i = SkipWords; i != NumWords; ++i) {
+ WordType W = Set->Words[i];
+ if (W != 0)
+ return Count + findFirstSet(W);
+ Count += WordWidth;
+ }
+ return Capacity;
+ }
+
+ const MachineValueTypeSet *Set;
+ unsigned Pos;
+ };
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ const_iterator begin() const { return const_iterator(this, false); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ const_iterator end() const { return const_iterator(this, true); }
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ bool operator==(const MachineValueTypeSet &S) const {
+ return Words == S.Words;
+ }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
+ bool operator!=(const MachineValueTypeSet &S) const {
+ return !operator==(S);
+ }
+
+private:
+ friend struct const_iterator;
+ std::array<WordType,NumWords> Words;
+};
+
+struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
+ using SetType = MachineValueTypeSet;
TypeSetByHwMode() = default;
TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
@@ -56,19 +192,23 @@ struct TypeSetByHwMode : public InfoByHwMode<std::set<MVT>> {
bool isValueTypeByHwMode(bool AllowEmpty) const;
ValueTypeByHwMode getValueTypeByHwMode() const;
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool isMachineValueType() const {
return isDefaultOnly() && Map.begin()->second.size() == 1;
}
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
MVT getMachineValueType() const {
assert(isMachineValueType());
return *Map.begin()->second.begin();
}
bool isPossible() const;
+
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool isDefaultOnly() const {
- return Map.size() == 1 &&
- Map.begin()->first == DefaultMode;
+ return Map.size() == 1 && Map.begin()->first == DefaultMode;
}
bool insert(const ValueTypeByHwMode &VVT);
@@ -178,6 +318,10 @@ struct TypeInfer {
private:
TypeSetByHwMode getLegalTypes();
+
+ /// Cached legal types.
+ bool LegalTypesCached = false;
+ TypeSetByHwMode::SetType LegalCache = {};
};
/// Set type used to track multiply used variables in patterns
diff --git a/llvm/utils/TableGen/InfoByHwMode.h b/llvm/utils/TableGen/InfoByHwMode.h
index d20bdabf7ec..71149e8da19 100644
--- a/llvm/utils/TableGen/InfoByHwMode.h
+++ b/llvm/utils/TableGen/InfoByHwMode.h
@@ -63,23 +63,30 @@ struct InfoByHwMode {
typedef typename MapType::const_iterator const_iterator;
InfoByHwMode() = default;
- InfoByHwMode(const MapType &&M) : Map(M) {}
+ InfoByHwMode(const MapType &M) : Map(M) {}
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
iterator begin() { return Map.begin(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
iterator end() { return Map.end(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
const_iterator begin() const { return Map.begin(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
const_iterator end() const { return Map.end(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool empty() const { return Map.empty(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool hasMode(unsigned M) const { return Map.find(M) != Map.end(); }
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool hasDefault() const { return hasMode(DefaultMode); }
InfoT &get(unsigned Mode) {
if (!hasMode(Mode)) {
assert(hasMode(DefaultMode));
- Map[Mode] = Map[DefaultMode];
+ Map.insert({Mode, Map.at(DefaultMode)});
}
- return Map[Mode];
+ return Map.at(Mode);
}
const InfoT &get(unsigned Mode) const {
auto F = Map.find(Mode);
@@ -89,9 +96,11 @@ struct InfoByHwMode {
return F->second;
}
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
bool isSimple() const {
return Map.size() == 1 && Map.begin()->first == DefaultMode;
}
+ LLVM_ATTRIBUTE_ALWAYS_INLINE
InfoT getSimple() const {
assert(isSimple());
return Map.begin()->second;
OpenPOWER on IntegriCloud