[IR] Switch AttributeList to use an array for O(1) access
Summary:
Before this change, AttributeLists stored a pair of index and
AttributeSet. This is memory efficient if most arguments do not have
attributes. However, it requires doing a search over the pairs to test
an argument or function attribute. Profiling shows that this loop was
0.76% of the time in 'opt -O2' of sqlite3.c, because LLVM constantly
tests values for nullability.
This was worth about 2.5% of mid-level optimization cycles on the
sqlite3 amalgamation. Here are the full perf results:
https://reviews.llvm.org/P7995
Here are just the before and after cycle counts:
```
$ perf stat -r 5 ./opt_before -O2 sqlite3.bc -o /dev/null
13,274,181,184 cycles # 3.047 GHz ( +- 0.28% )
$ perf stat -r 5 ./opt_after -O2 sqlite3.bc -o /dev/null
12,906,927,263 cycles # 3.043 GHz ( +- 0.51% )
```
This patch *does not* change the indices used to query attributes, as
requested by reviewers. Tracking whether an index is usable for array
indexing is a huge pain that affects many of the internal APIs, so it
would be good to come back later and do a cleanup to remove this
internal adjustment.
Reviewers: pete, chandlerc
Subscribers: javed.absar, llvm-commits
Differential Revision: https://reviews.llvm.org/D32819
llvm-svn: 303654
diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
index 1f8b503..e29b225 100644
--- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -660,10 +660,12 @@
SmallVector<uint64_t, 64> Record;
for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
- const AttributeList &A = Attrs[i];
- for (unsigned i = 0, e = A.getNumSlots(); i != e; ++i)
- Record.push_back(
- VE.getAttributeGroupID({A.getSlotIndex(i), A.getSlotAttributes(i)}));
+ AttributeList AL = Attrs[i];
+ for (unsigned i = AL.index_begin(), e = AL.index_end(); i != e; ++i) {
+ AttributeSet AS = AL.getAttributes(i);
+ if (AS.hasAttributes())
+ Record.push_back(VE.getAttributeGroupID({i, AS}));
+ }
Stream.EmitRecord(bitc::PARAMATTR_CODE_ENTRY, Record);
Record.clear();
diff --git a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
index fd76400..bb626ba 100644
--- a/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
+++ b/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -902,8 +902,11 @@
}
// Do lookups for all attribute groups.
- for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
- IndexAndAttrSet Pair = {PAL.getSlotIndex(i), PAL.getSlotAttributes(i)};
+ for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) {
+ AttributeSet AS = PAL.getAttributes(i);
+ if (!AS.hasAttributes())
+ continue;
+ IndexAndAttrSet Pair = {i, AS};
unsigned &Entry = AttributeGroupMap[Pair];
if (Entry == 0) {
AttributeGroups.push_back(Pair);