Infinite inlining of recursive functions

[Quuxplusone]

Bugzilla Link	PR26371
Status	NEW
Importance	P normal
Reported by	Artur Pilipenko (apilipenko@azulsystems.com)
Reported on	2016-01-29 08:04:20 -0800
Last modified on	2016-02-01 23:23:04 -0800
Version	trunk
Hardware	PC All
CC	chandlerc@gmail.com, listmail@philipreames.com, llvm-bugs@lists.llvm.org, sanjoy@playingwithpointers.com
Fixed by commit(s)
Attachments	inline.ll (451 bytes, application/octet-stream)
Blocks
Blocked by
See also

Created attachment 15752
Reproducer

To prevent infinite inlining of recursive functions Inliner maintains
InlineHistory structure. However in some cases we might still end up inlining
recursive function chain. It happens when Inliner is executed in a CallGraphSCC
pass manager iteration. CGSCC pass manager spins one more iteration of inlining
if some indirect call site was devirtualized by other CGSCC passes. No
InlineHistory is maintained between these inliner iterations. Small reproducer
is in the attachment.

In practice it's rarely a problem because the number of iterations in CGSCC is
limited by 4 by default. But theoretically it can lead to an exponential growth
of code size.

The suggested fix is to mark recursive call sites encountered by Inliner with
NoInline attribute, so this information will be maintained between inlining
iterations.

[Quuxplusone]

Attached inline.ll (451 bytes, application/octet-stream): Reproducer