DwarfAccelTable: Fix handling of hash collisions.
authorFrederic Riss <friss@apple.com>
Tue, 10 Mar 2015 00:46:31 +0000 (00:46 +0000)
committerFrederic Riss <friss@apple.com>
Tue, 10 Mar 2015 00:46:31 +0000 (00:46 +0000)
commit14bd47ef85613ec5c5bfc56ad27ae6ebb52a6cbf
tree137e828409a49c1d24c8072e27c8f0bdf3f2582a
parent5225aec964b260411f5bc691118cdb0a99a0ff5e
DwarfAccelTable: Fix handling of hash collisions.

It turns out accelerator tables where totally broken if they contained
entries with colliding hashes. The failure mode is pretty bad, as it not
only impacted the colliding entries, but would basically make all the
entries after the first hash collision pointing in the wrong place.

The testcase uses the symbol names that where found to collide during a
clang build.

From a performance point of view, the patch adds a sort and a linear
walk over each bucket contents. While it has a measurable impact on the
accelerator table emission, it's not showing up significantly in clang
profiles (and I'd argue that correctness is priceless :-)).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231732 91177308-0d34-0410-b5e6-96231b3b80d8
lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp
test/DebugInfo/accel-table-hash-collisions.ll [new file with mode: 0644]