[llvm-dev] LLVM is getting faster, April edition

[Davide Italiano via llvm-dev]

On Thu, Apr 13, 2017 at 1:52 PM, Davide Italiano <davide at freebsd.org> wrote:
> On Tue, Apr 11, 2017 at 7:52 PM, Mikhail Zolotukhin via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> Hi,
>>
>> It's been a while since I sent the last compile time report [1], where it
>> was shown that LLVM was getting slower over time. But now I'm happy to bring
>> some good news: finally, LLVM is getting faster, not slower :)
>>
>
> Thanks a lot for the update, this is very good to hear :)
>
>> *** Current status ***
>> Many areas of LLVM have been examined and improved since then: InstCombine,
>> SCEV, APInt implementation, and that resulted in almost 10% improvement
>> compared to January compiler. I remeasured compile time data for CTMark
>> tests and annotated the biggest changes, the graphs for Os and O0-g are
>> attached below. Thick black line represents geomean, colored thin lines
>> represent individual tests. The data is normalized on the first revision in
>> the range (which is ~Jun, 2015).
>>
>> *** Future work ***
>> There are still plenty of opportunities to make LLVM faster. Here is a list
>> of some ideas that can further help compile-time:
>>
>> - KnownBits Cache. InstCombine and other passes use known bits, which often
>> happens to be pretty expensive. Hal posted a patch [2] that implements a
>> cache for known bits, but there are still some issues to fix there.
>> - SCEV. Some parts of SCEV still need to be improved. For instance,
>> createAddRecFromPHI function seems to be very inefficient: it can perform
>> many expensive traversals over entire function/loop nest, and most of them
>> are probably redundant.
>> - Forming LCSSA. PR31851 reports that the current implementation of LCSSA
>> forming can be expensive. A WIP patch [3] should address the problem, but
>> probably there are more to be improved here.
>
> https://reviews.llvm.org/rL300255 is a first step towards the goal.
> For some large tests, LCSSA is still slow, and that's due to a lot of
> time spent in the updater. I'll try to fix that one next.
>
> --
> Davide

To clarify, here's the profiler output
https://reviews.llvm.org/F3221946
I think there's not much we can do (easily) for `getExitBlocks()` as
we already cache the call for each loop in `fromLCSSAfoInstructions`
but switching to a faster renamer should help. Dan, do you think it's
possible to move your O(def + use) renamer out of PredicateInfo to a
common file and use that here?


-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare