[LiveVariables] Switch Kill/Defs sets to be DenseSet(s).
authorDavide Italiano <davide@freebsd.org>
Thu, 11 May 2017 19:37:43 +0000 (19:37 +0000)
committerDavide Italiano <davide@freebsd.org>
Thu, 11 May 2017 19:37:43 +0000 (19:37 +0000)
commit36acbc716d7da51dc7f1306a172eb7f512a394ae
tree3978ad8365b6efbca4449b856922764d45682eb7
parent2cbd1f6c9fd9792bc5a7e04a5b5defdb64b08c86
[LiveVariables] Switch Kill/Defs sets to be DenseSet(s).

The testcase in PR32984 shows a non linear compile time increase
after a change that made the LoopUnroll pass more aggressive
(increasing the threshold).

My profiling shows all the time of PHI elimination goes to
llvm::LiveVariables::addNewBlock. This is because we keep
Defs/Kills registers in a SmallSet and vfind(const T &V); is O(N).

Switching to a DenseSet reduces the time spent in the pass from
297 seconds to 97 seconds. Profiling still shows a lot of time is
spent iterating the data structure, so I guess there's room for
improvement.

Dan tells me GCC uses real set operations for live registers and
it takes no-time on this testcase. Matthias points out we might
want to switch all this to LiveIntervalAnalysis so it's not entirely
sure if a rewrite is worth it.

Differential Revision:  https://reviews.llvm.org/D33088

llvm-svn: 302819
llvm/lib/CodeGen/LiveVariables.cpp