OSDN Git Service

[SCEV] Limit max size of AddRecExpr during evolving
authorMax Kazantsev <max.kazantsev@azul.com>
Sun, 23 Jul 2017 15:40:19 +0000 (15:40 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Sun, 23 Jul 2017 15:40:19 +0000 (15:40 +0000)
commit33ec7a1ff082803fe71cc532ee5f11472a427878
treec1083fc884d7c56182f39e93c1171c0bde8b78b4
parent4e2037d4ad7259846d27d9954f0dc0bd195b373f
[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
`SCEVAddRecExpr`s into one. By default, max allowed size of the
resulting AddRecExpr is set to 16.

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@308847 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Analysis/ScalarEvolution.cpp
test/Analysis/ScalarEvolution/max-addrec-size.ll [new file with mode: 0644]