[CodeExtractor] Factor out and reuse shrinkwrap analysis
authorVedant Kumar <vsk@apple.com>
Tue, 8 Oct 2019 17:17:51 +0000 (17:17 +0000)
committerVedant Kumar <vsk@apple.com>
Tue, 8 Oct 2019 17:17:51 +0000 (17:17 +0000)
commit9852699dcb18dd26866695a861e31a07bcc16e82
treefd4fcadee38bbfaf30f60fa0d7f816fe9b4f413d
parentd8245e7a36d50310c85cbefe6b79f27f745e7cee
[CodeExtractor] Factor out and reuse shrinkwrap analysis

Factor out CodeExtractor's analysis of allocas (for shrinkwrapping
purposes), and allow the analysis to be reused.

This resolves a quadratic compile-time bug observed when compiling
AMDGPUDisassembler.cpp.o.

Pre-patch (Release + LTO clang):

```
   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  176.5278 ( 57.8%)   0.4915 ( 18.5%)  177.0192 ( 57.4%)  177.4112 ( 57.3%)  Hot Cold Splitting
```

Post-patch (ReleaseAsserts clang):

```
   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  1.4051 (  3.3%)   0.0079 (  0.3%)   1.4129 (  3.2%)   1.4129 (  3.2%)  Hot Cold Splitting
```

Testing: check-llvm, and comparing the AMDGPUDisassembler.cpp.o binary
pre- vs. post-patch.

An alternate approach is to hide CodeExtractorAnalysisCache from clients
of CodeExtractor, and to recompute the analysis from scratch inside of
CodeExtractor::extractCodeRegion(). This eliminates some redundant work
in the shrinkwrapping legality check. However, some clients continue to
exhibit O(n^2) compile time behavior as computing the analysis is O(n).

rdar://55912966

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

llvm-svn: 374089
llvm/include/llvm/Transforms/IPO/HotColdSplitting.h
llvm/include/llvm/Transforms/Utils/CodeExtractor.h
llvm/lib/Transforms/IPO/BlockExtractor.cpp
llvm/lib/Transforms/IPO/HotColdSplitting.cpp
llvm/lib/Transforms/IPO/LoopExtractor.cpp
llvm/lib/Transforms/IPO/PartialInlining.cpp
llvm/lib/Transforms/Utils/CodeExtractor.cpp
llvm/unittests/Transforms/Utils/CodeExtractorTest.cpp