Page MenuHomePhabricator

LowerTypeTests: Improve performance by optimising type metadata queries.

Authored by pcc on Dec 6 2016, 1:55 PM.



Requesting metadata for a global is a relatively expensive operation as it
involves a map lookup, but it's one that we need to do relatively frequently in
this pass to collect the list of type metadata nodes associated with a global.
This change improves the performance of type metadata queries by prebuilding
data structures that keep the global together with its list of type metadata,
and changing the pass to use that data structure wherever we were previously
passing global references around.

This change also eliminates some O(N^2) behavior by collecting the list of
globals associated with each type identifier during the first pass over the
list of globals rather than visiting each global to compute that list every
time we add a new type identifier.

Reduces pass runtime on a module containing Chrome's vtables from over 60s
to 0.9s.

Diff Detail


Event Timeline

pcc updated this revision to Diff 80478.Dec 6 2016, 1:55 PM
pcc retitled this revision from to LowerTypeTests: Improve performance by optimising type metadata queries..
pcc updated this object.
pcc added a reviewer: eugenis.
pcc added subscribers: krasin, llvm-commits.
eugenis accepted this revision.Dec 6 2016, 3:00 PM
eugenis edited edge metadata.

Looks great!

This revision is now accepted and ready to land.Dec 6 2016, 3:00 PM
This revision was automatically updated to reflect the committed changes.