[LCG] Switch one of the update methods for the LazyCallGraph to support
authorChandler Carruth <chandlerc@gmail.com>
Wed, 9 Aug 2017 09:05:27 +0000 (09:05 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Wed, 9 Aug 2017 09:05:27 +0000 (09:05 +0000)
commit23c2f44cc7b8a2fd24eb951616b9c4d2c6459d28
tree55536a54b404943df0a411c07db26e93f2cd1ac8
parent64c32411549e1ea94a0e0ba557b90fa4e962d328
[LCG] Switch one of the update methods for the LazyCallGraph to support
limited batch updates.

Specifically, allow removing multiple reference edges starting from
a common source node. There are a few constraints that play into
supporting this form of batching:

1) The way updates occur during the CGSCC walk, about the most we can
   functionally batch together are those with a common source node. This
   also makes the batching simpler to implement, so it seems
   a worthwhile restriction.
2) The far and away hottest function for large C++ files I measured
   (generated code for protocol buffers) showed a huge amount of time
   was spent removing ref edges specifically, so it seems worth focusing
   there.
3) The algorithm for removing ref edges is very amenable to this
   restricted batching. There are just both API and implementation
   special casing for the non-batch case that gets in the way. Once
   removed, supporting batches is nearly trivial.

This does modify the API in an interesting way -- now, we only preserve
the target RefSCC when the RefSCC structure is unchanged. In the face of
any splits, we create brand new RefSCC objects. However, all of the
users were OK with it that I could find. Only the unittest needed
interesting updates here.

How much does batching these updates help? I instrumented the compiler
when run over a very large generated source file for a protocol buffer
and found that the majority of updates are intrinsically updating one
function at a time. However, nearly 40% of the total ref edges removed
are removed as part of a batch of removals greater than one, so these
are the cases batching can help with.

When compiling the IR for this file with 'opt' and 'O3', this patch
reduces the total time by 8-9%.

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

llvm-svn: 310450
llvm/include/llvm/Analysis/LazyCallGraph.h
llvm/lib/Analysis/CGSCCPassManager.cpp
llvm/lib/Analysis/LazyCallGraph.cpp
llvm/unittests/Analysis/LazyCallGraphTest.cpp