From owner-svn-src-all@freebsd.org Sun Mar 5 19:56:21 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 851DFCFA259; Sun, 5 Mar 2017 19:56:21 +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 470DA12BB; Sun, 5 Mar 2017 19:56: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 v25JuK8G039507; Sun, 5 Mar 2017 19:56:20 GMT (envelope-from dim@FreeBSD.org) Received: (from dim@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v25JuKoO039506; Sun, 5 Mar 2017 19:56:20 GMT (envelope-from dim@FreeBSD.org) Message-Id: <201703051956.v25JuKoO039506@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dim set sender to dim@FreeBSD.org using -f From: Dimitry Andric Date: Sun, 5 Mar 2017 19:56:20 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r314708 - 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: Sun, 05 Mar 2017 19:56:21 -0000 Author: dim Date: Sun Mar 5 19:56:20 2017 New Revision: 314708 URL: https://svnweb.freebsd.org/changeset/base/314708 Log: For now, revert 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 This commit is the cause of excessive compile times on skein_block.c (and possibly other files) during kernel builds on amd64. We never saw the problematic behavior described in this upstream commit, so for now it is better to revert it. An upstream bug has been filed here: https://bugs.llvm.org/show_bug.cgi?id=32142 Reported by: mjg Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Modified: head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp ============================================================================== --- head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Sun Mar 5 18:37:25 2017 (r314707) +++ head/contrib/llvm/lib/Analysis/ScalarEvolution.cpp Sun Mar 5 19:56:20 2017 (r314708) @@ -127,11 +127,6 @@ static cl::opt MulOpsInlineThr cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(1000)); -static cl::opt - MaxCompareDepth("scalar-evolution-max-compare-depth", cl::Hidden, - cl::desc("Maximum depth of recursive compare complexity"), - cl::init(32)); - //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -480,8 +475,8 @@ bool SCEVUnknown::isOffsetOf(Type *&CTy, static int CompareValueComplexity(SmallSet, 8> &EqCache, const LoopInfo *const LI, Value *LV, Value *RV, - unsigned Depth) { - if (Depth > MaxCompareDepth || EqCache.count({LV, RV})) + unsigned DepthLeft = 2) { + if (DepthLeft == 0 || EqCache.count({LV, RV})) return 0; // Order pointer values after integer values. This helps SCEVExpander form @@ -542,23 +537,21 @@ CompareValueComplexity(SmallSetgetOperand(Idx), - RInst->getOperand(Idx), Depth + 1); + RInst->getOperand(Idx), DepthLeft - 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( - SmallSet, 8> &EqCacheSCEV, - const LoopInfo *const LI, const SCEV *LHS, const SCEV *RHS, - unsigned Depth = 0) { +static int CompareSCEVComplexity(const LoopInfo *const LI, const SCEV *LHS, + const SCEV *RHS) { // Fast-path: SCEVs are uniqued so we can do a quick equality check. if (LHS == RHS) return 0; @@ -568,8 +561,6 @@ static int CompareSCEVComplexity( if (LType != RType) return (int)LType - (int)RType; - if (Depth > MaxCompareDepth || 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. @@ -579,11 +570,7 @@ static int CompareSCEVComplexity( const SCEVUnknown *RU = cast(RHS); SmallSet, 8> EqCache; - int X = CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue(), - Depth + 1); - if (X == 0) - EqCacheSCEV.insert({LHS, RHS}); - return X; + return CompareValueComplexity(EqCache, LI, LU->getValue(), RU->getValue()); } case scConstant: { @@ -618,12 +605,11 @@ static int CompareSCEVComplexity( // Lexicographically compare. for (unsigned i = 0; i != LNumOps; ++i) { - int X = CompareSCEVComplexity(EqCacheSCEV, LI, LA->getOperand(i), - RA->getOperand(i), Depth + 1); + long X = CompareSCEVComplexity(LI, LA->getOperand(i), RA->getOperand(i)); if (X != 0) return X; } - EqCacheSCEV.insert({LHS, RHS}); + return 0; } @@ -642,13 +628,11 @@ static int CompareSCEVComplexity( for (unsigned i = 0; i != LNumOps; ++i) { if (i >= RNumOps) return 1; - int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(i), - RC->getOperand(i), Depth + 1); + long X = CompareSCEVComplexity(LI, LC->getOperand(i), RC->getOperand(i)); if (X != 0) return X; } - EqCacheSCEV.insert({LHS, RHS}); - return 0; + return (int)LNumOps - (int)RNumOps; } case scUDivExpr: { @@ -656,15 +640,10 @@ static int CompareSCEVComplexity( const SCEVUDivExpr *RC = cast(RHS); // Lexicographically compare udiv expressions. - int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getLHS(), RC->getLHS(), - Depth + 1); + long X = CompareSCEVComplexity(LI, LC->getLHS(), RC->getLHS()); if (X != 0) return X; - X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getRHS(), RC->getRHS(), - Depth + 1); - if (X == 0) - EqCacheSCEV.insert({LHS, RHS}); - return X; + return CompareSCEVComplexity(LI, LC->getRHS(), RC->getRHS()); } case scTruncate: @@ -674,11 +653,7 @@ static int CompareSCEVComplexity( const SCEVCastExpr *RC = cast(RHS); // Compare cast expressions by operand. - int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(), - RC->getOperand(), Depth + 1); - if (X == 0) - EqCacheSCEV.insert({LHS, RHS}); - return X; + return CompareSCEVComplexity(LI, LC->getOperand(), RC->getOperand()); } case scCouldNotCompute: @@ -700,21 +675,19 @@ static int CompareSCEVComplexity( 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(EqCache, LI, RHS, LHS) < 0) + if (CompareSCEVComplexity(LI, RHS, LHS) < 0) std::swap(LHS, RHS); return; } // Do the rough sort by complexity. std::stable_sort(Ops.begin(), Ops.end(), - [&EqCache, LI](const SCEV *LHS, const SCEV *RHS) { - return CompareSCEVComplexity(EqCache, LI, LHS, RHS) < 0; + [LI](const SCEV *LHS, const SCEV *RHS) { + return CompareSCEVComplexity(LI, LHS, RHS) < 0; }); // Now that we are sorted by complexity, group elements of the same