ART: Faster implementation of GVN's hash table
The basic hash table in Optimizing's GVN pass does not scale for
larger methods and quickly becomes a bottleneck. This patch provides
a different implementation, focusing on the following:
(1) Proper buckets with chaining for near constant-time lookup.
(2) Bucket inheritance for faster cloning. A clone does not actually
copy the entries until a first change is made.
(3) Table resizing for better load management. Done during cloning.
(4) Kill() and IntersectWith() applied only on impure instructions.
This is achieved by splitting (im)pure entries between even- and
odd-indexed buckets.
Benchmarks show that this optimization speeds up GVN by ~10%, which
translates to a rougly 2% change in the overall compilation time.
Change-Id: Ib4058359701d990194cfd49c6ee46ac2372f090c
1 file changed