This revision was automatically updated to reflect the committed changes.
Closed by commit rL284166: [analyzer] Remove superquadratic behaviour from
DataflowWorklist (authored by alexshap).
Changed prior to commit:
https://reviews.llvm.org/D25503?vs=74437=74585#toc
Repository:
rL LLVM
NoQ accepted this revision.
NoQ added a comment.
In https://reviews.llvm.org/D25503#569046, @a.sidorin wrote:
> Did you test Artem's approach?
I don't think this is necessary, the priority queue looks like "the" data
structure to use here.
Repository:
rL LLVM
a.sidorin accepted this revision.
a.sidorin added a comment.
This patch reduces both the analysis time and the line count. I like it! :)
Did you test Artem's approach?
Repository:
rL LLVM
https://reviews.llvm.org/D25503
___
cfe-commits mailing
krememek added a comment.
Looks great to me too. Thanks for doing this!
Repository:
rL LLVM
https://reviews.llvm.org/D25503
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
zaks.anna accepted this revision.
zaks.anna added a comment.
This revision is now accepted and ready to land.
LGTM!
I would add info on how much speedup you see in the cryptographic libraries to
the commit message. (You could say something like "on a cryptographic library
that uses code
alexshap added a comment.
I've just run scan-build against LLVM & clang & clang-extra-tools - the new
version (with PriorityQueue) is a bit faster - i was running the build on OSX &
-j8 and the total time for the new version is 88 minutes vs 92 minutes for the
old one. Certainly i think that
alexshap updated the summary for this revision.
alexshap updated this revision to Diff 74437.
alexshap added a comment.
Switch to priority queue.
I have rerun the tests - they are all green.
I will post the numbers about the perf a bit later.
Repository:
rL LLVM
alexshap added inline comments.
Comment at: lib/Analysis/LiveVariables.cpp:66
return nullptr;
- const CFGBlock *b = worklist.pop_back_val();
+ const auto I = --worklist.end();
+ const CFGBlock *b = *I;
alexshap wrote:
> alexshap wrote:
> > zaks.anna
alexshap added inline comments.
Comment at: lib/Analysis/LiveVariables.cpp:66
return nullptr;
- const CFGBlock *b = worklist.pop_back_val();
+ const auto I = --worklist.end();
+ const CFGBlock *b = *I;
alexshap wrote:
> zaks.anna wrote:
> >
alexshap added inline comments.
Comment at: lib/Analysis/LiveVariables.cpp:66
return nullptr;
- const CFGBlock *b = worklist.pop_back_val();
+ const auto I = --worklist.end();
+ const CFGBlock *b = *I;
zaks.anna wrote:
> '--wroklist.end()' ->
NoQ added a reviewer: a.sidorin.
NoQ added a comment.
This looks familiar, i think i've seen significant slowdowns around there on
some very rare files. Nice catch! Probably a binary-search insert could have
also been much better than re-sorting, even if it's still a vector.
Repository:
rL
zaks.anna added a comment.
Do you have results that show how this effects performance on average code and
machine generated code?
One concern is that multiset is malloc intensive. See
http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task.
Maybe
alexshap created this revision.
alexshap added reviewers: NoQ, zaks.anna.
alexshap added a subscriber: cfe-commits.
alexshap set the repository for this revision to rL LLVM.
The class DataflowWorklist internally maintains a sorted list of pointers to
CFGBlock and
the method enqueuePredecessors
13 matches
Mail list logo
