missing optimization opportunity: recursive inlining

[llvmbot]

Bugzilla Link	11507
Version	trunk
OS	Linux
Attachments	Test case in C++, The same test case in llvm-ir after opt -O3
Reporter	LLVM Bugzilla Contributor
CC	@d0k,@efriedma-quic

Extended Description

I saw a lot of std::map usage in the llvm compiler which uses lots of operators, especially to check if the map is empty. But thinking this check is cheap is too naive as you will see in the test case:

_ZNSt8_Rb_treeIiSt4pairIKiiESt10_Select1stIS2_ESt4lessIiESaIS2_EE8_M_eraseEPSt13_Rb_tree_nodeIS2_E is called with null as the second parameter. _ZNSt8_Rb_treeIiSt4pairIKiiESt10_Select1stIS2_ESt4lessIiESaIS2_EE8_M_eraseEPSt13_Rb_tree_nodeIS2_E itself starts with a comparison of the second parameter against null. So inlining this function can fold a lot (the test case is designed to be a completely empty program).

[efriedma-quic]

Note that the recursive function in question is the recursive function which destroys the std::map.

One way to approach this optimization is that we can prove the function does not recurse in the case where the second argument is null.

[d0k]

The current iteration of the inliner knows how to do this. It doesn't fully optimize the C++ testcase on the first pass though, probably a phase ordering issue. Running opt -O3 twice folds it down to "ret i32 0".