From owner-svn-src-all@freebsd.org Mon Mar 6 21:14:22 2017 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 04874CFC6EB; Mon, 6 Mar 2017 21:14:22 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id ABCF31332; Mon, 6 Mar 2017 21:14:21 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v26LEKaX064480; Mon, 6 Mar 2017 21:14:20 GMT (envelope-from dim@FreeBSD.org) Received: (from dim@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v26LEKtM064479; Mon, 6 Mar 2017 21:14:20 GMT (envelope-from dim@FreeBSD.org) Message-Id: <201703062114.v26LEKtM064479@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dim set sender to dim@FreeBSD.org using -f From: Dimitry Andric Date: Mon, 6 Mar 2017 21:14:20 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r314795 - head/contrib/llvm/lib/Analysis X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 06 Mar 2017 21:14:22 -0000 Author: dim Date: Mon Mar 6 21:14:20 2017 New Revision: 314795 URL: https://svnweb.freebsd.org/changeset/base/314795 Log: Reapply r287232 from upstream llvm trunk (by Daniil Fukalov): [SCEV] limit recursion depth of CompareSCEVComplexity Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 Pull in r296992 from upstream llvm trunk (by Sanjoy Das): [SCEV] Decrease the recursion threshold for CompareValueComplexity Fixes PR32142. r287232 accidentally increased the recursion threshold for CompareValueComplexity from 2 to 32. This change reverses that change by introducing a separate flag for CompareValueComplexity's threshold. The latter revision fixes the excessive compile times for skein_block.c. Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp ============================================================================== --- head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Mon Mar 6 21:06:55 2017 (r314794) +++ head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Mon Mar 6 21:14:20 2017 (r314795) @@ -127,6 +127,16 @@ static cl::opt MulOpsInlineThr cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(1000)); +static cl::opt MaxSCEVCompareDepth( + "scalar-evolution-max-scev-compare-depth", cl::Hidden, + cl::desc("Maximum depth of recursive SCEV complexity comparisons"), + cl::init(32)); + +static cl::opt MaxValueCompareDepth( + "scalar-evolution-max-value-compare-depth", cl::Hidden, + cl::desc("Maximum depth of recursive value complexity comparisons"), + cl::init(2)); + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -475,8 +485,8 @@ bool SCEVUnknown::isOffsetOf(Type *&CTy, static int CompareValueComplexity(SmallSet, 8> &EqCache, const LoopInfo *const LI, Value *LV, Value *RV, - unsigned DepthLeft = 2) { - if (DepthLeft == 0 || EqCache.count({LV, RV})) + unsigned Depth) { + if (Depth > MaxValueCompareDepth || EqCache.count({LV, RV})) return 0; // Order pointer values after integer values. This helps SCEVExpander form @@ -537,21 +547,23 @@ CompareValueComplexity(SmallSetgetOperand(Idx), - RInst->getOperand(Idx), DepthLeft - 1); + RInst->getOperand(Idx), Depth + 1); if (Result != 0) return Result; - EqCache.insert({LV, RV}); } } + EqCache.insert({LV, RV}); return 0; } // Return negative, zero, or positive, if LHS is less than, equal to, or greater // than RHS, respectively. A three-way result allows recursive comparisons to be // more efficient. -static int CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, - const SCEV *RHS) { +static int CompareSCEVComplexity( + SmallSet, 8> &EqCacheSCEV, + const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, + unsigned Depth = 0) { // Fast-path: SCEVs are uniqued so we can do a quick equality check. if (LHS == RHS) return 0; @@ -561,6 +573,8 @@ static int CompareSCEVComplexity(const L if (LType != RType) return (int)LType - (int)RType; + if (Depth > MaxSCEVCompareDepth || EqCacheSCEV.count({LHS, RHS})) + return 0; // Aside from the getSCEVType() ordering, the particular ordering // isn't very important except that it's beneficial to be consistent, // so that (a + b) and (b + a) don't end up as different expressions. @@ -570,7 +584,11 @@ static int CompareSCEVComplexity(const L const SCEVUnknown *RU = cast(RHS); SmallSet, 8> EqCache; - return CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue()); + int X = CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue(), + Depth + 1); + if (X == 0) + EqCacheSCEV.insert({LHS, RHS}); + return X; } case scConstant: { @@ -605,11 +623,12 @@ static int CompareSCEVComplexity(const L // Lexicographically compare. for (unsigned i = 0; i != LNumOps; ++i) { - long X = CompareSCEVComplexity(LI, LA->getOperand(i), RA->getOperand(i)); + int X = CompareSCEVComplexity(EqCacheSCEV, LI, LA->getOperand(i), + RA->getOperand(i), Depth + 1); if (X != 0) return X; } - + EqCacheSCEV.insert({LHS, RHS}); return 0; } @@ -628,11 +647,13 @@ static int CompareSCEVComplexity(const L for (unsigned i = 0; i != LNumOps; ++i) { if (i >= RNumOps) return 1; - long X = CompareSCEVComplexity(LI, LC->getOperand(i), RC->getOperand(i)); + int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(i), + RC->getOperand(i), Depth + 1); if (X != 0) return X; } - return (int)LNumOps - (int)RNumOps; + EqCacheSCEV.insert({LHS, RHS}); + return 0; } case scUDivExpr: { @@ -640,10 +661,15 @@ static int CompareSCEVComplexity(const L const SCEVUDivExpr *RC = cast(RHS); // Lexicographically compare udiv expressions. - long X = CompareSCEVComplexity(LI, LC->getLHS(), RC->getLHS()); + int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getLHS(), RC->getLHS(), + Depth + 1); if (X != 0) return X; - return CompareSCEVComplexity(LI, LC->getRHS(), RC->getRHS()); + X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getRHS(), RC->getRHS(), + Depth + 1); + if (X == 0) + EqCacheSCEV.insert({LHS, RHS}); + return X; } case scTruncate: @@ -653,7 +679,11 @@ static int CompareSCEVComplexity(const L const SCEVCastExpr *RC = cast(RHS); // Compare cast expressions by operand. - return CompareSCEVComplexity(LI, LC->getOperand(), RC->getOperand()); + int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(), + RC->getOperand(), Depth + 1); + if (X == 0) + EqCacheSCEV.insert({LHS, RHS}); + return X; } case scCouldNotCompute: @@ -675,19 +705,21 @@ static int CompareSCEVComplexity(const L static void GroupByComplexity(SmallVectorImpl &Ops, LoopInfo *LI) { if (Ops.size() < 2) return; // Noop + + SmallSet, 8> EqCache; if (Ops.size() == 2) { // This is the common case, which also happens to be trivially simple. // Special case it. const SCEV *&LHS = Ops[0], *&RHS = Ops[1]; - if (CompareSCEVComplexity(LI, RHS, LHS) < 0) + if (CompareSCEVComplexity(EqCache, LI, RHS, LHS) < 0) std::swap(LHS, RHS); return; } // Do the rough sort by complexity. std::stable_sort(Ops.begin(), Ops.end(), - [LI](const SCEV *LHS, const SCEV *RHS) { - return CompareSCEVComplexity(LI, LHS, RHS) < 0; + [&EqCache, LI](const SCEV *LHS, const SCEV *RHS) { + return CompareSCEVComplexity(EqCache, LI, LHS, RHS) < 0; }); // Now that we are sorted by complexity, group elements of the same