HomePhabricator

Merging r308847:

Description

Merging r308847:

r308847 | mkazantsev | 2017-07-23 08:40:19 -0700 (Sun, 23 Jul 2017) | 24 lines

[SCEV] Limit max size of AddRecExpr during evolving

When SCEV calculates product of two SCEVAddRecs from the same loop, it
tries to combine them into one big AddRecExpr. If the sizes of the initial
SCEVs were S1 and S2, the size of their product is S1 + S2 - 1, and every
operand of the resulting SCEV is combined from operands of initial SCEV and
has much higher complexity than they have.

As result, if we try to calculate something like:

%x1 = {a,+,b}
%x2 = mul i32 %x1, %x1
%x3 = mul i32 %x2, %x1
%x4 = mul i32 %x3, %x2
...

The size of such SCEVs grows as 2^N, and the arguments
become more and more complex as we go forth. This leads
to long compilation and huge memory consumption.

This patch sets a limit after which we don't try to combine two
SCEVAddRecExprs into one. By default, max allowed size of the
resulting AddRecExpr is set to 16.

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


Details

Committed
hansAug 10 2017, 10:15 AM
Differential Revision
D35664: [SCEV] Limit max size of AddRecExpr during evolving
Parents
rL310628: Merging r310534:
Branches
Unknown
Tags
Unknown