Author: hans Date: Thu Aug 10 10:15:06 2017 New Revision: 310629 URL: http://llvm.org/viewvc/llvm-project?rev=310629&view=rev Log: 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 `SCEVAddRecExpr`s into one. By default, max allowed size of the resulting AddRecExpr is set to 16. Differential Revision: https://reviews.llvm.org/D35664 ------------------------------------------------------------------------ Added: llvm/branches/release_50/test/Analysis/ScalarEvolution/max-addrec-size.ll - copied unchanged from r308847, llvm/trunk/test/Analysis/ScalarEvolution/max-addrec-size.ll Modified: llvm/branches/release_50/ (props changed) llvm/branches/release_50/lib/Analysis/ScalarEvolution.cpp Propchange: llvm/branches/release_50/ ------------------------------------------------------------------------------ --- svn:mergeinfo (original) +++ svn:mergeinfo Thu Aug 10 10:15:06 2017 @@ -1,3 +1,3 @@ /llvm/branches/Apple/Pertwee:110850,110961 /llvm/branches/type-system-rewrite:133420-134817 -/llvm/trunk:155241,308483-308484,308503,308808,308813,308891,308906,308950,308963,308978,308986,309113,309302,309321,309323,309325,309330,309343,309353,309355,309422,309481,309483,309495,309555,309561,309594,309651,309744,309758,309849,309928,309930,310071,310190,310240-310242,310250,310253,310267,310534 +/llvm/trunk:155241,308483-308484,308503,308808,308813,308847,308891,308906,308950,308963,308978,308986,309113,309302,309321,309323,309325,309330,309343,309353,309355,309422,309481,309483,309495,309555,309561,309594,309651,309744,309758,309849,309928,309930,310071,310190,310240-310242,310250,310253,310267,310534 Modified: llvm/branches/release_50/lib/Analysis/ScalarEvolution.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_50/lib/Analysis/ScalarEvolution.cpp?rev=310629&r1=310628&r2=310629&view=diff ============================================================================== --- llvm/branches/release_50/lib/Analysis/ScalarEvolution.cpp (original) +++ llvm/branches/release_50/lib/Analysis/ScalarEvolution.cpp Thu Aug 10 10:15:06 2017 @@ -162,6 +162,11 @@ static cl::opt<unsigned> cl::desc("Maximum depth of recursive SExt/ZExt"), cl::init(8)); +static cl::opt<unsigned> + MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, + cl::desc("Max coefficients in AddRec during evolving"), + cl::init(16)); + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -2878,6 +2883,12 @@ const SCEV *ScalarEvolution::getMulExpr( if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop) continue; + // Limit max number of arguments to avoid creation of unreasonably big + // SCEVAddRecs with very complex operands. + if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 > + MaxAddRecSize) + continue; + bool Overflow = false; Type *Ty = AddRec->getType(); bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64; _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits