Author: joerg Date: Wed Jun 1 09:10:10 2016 New Revision: 271394 URL: http://llvm.org/viewvc/llvm-project?rev=271394&view=rev Log: Merging rr261430: ------------------------------------------------------------------------ r261430 | joerg | 2016-02-20 12:24:44 +0100 (Sat, 20 Feb 2016) | 15 lines
When MemoryDependenceAnalysis hits a CFG with many transparent blocks, the algorithm easily degrades into quadratic memory and time complexity. The easiest example is a long chain of BBs that don't otherwise use a location. The caching will add an entry for every intermediate block and limiting the number of results doesn't help as no results are produced until a definition is found. Introduce a limit similar to the existing instructions-per-block limit. This limit counts the total number of blocks checked. If the limit is reached, entries are considered unknown. The initial value is 1000, which avoids regressions for normal sized functions while still limiting edge cases to reasnable memory consumption and execution time. Differential Revision: http://reviews.llvm.org/D16123 ------------------------------------------------------------------------ Modified: llvm/branches/release_38/lib/Analysis/MemoryDependenceAnalysis.cpp llvm/branches/release_38/utils/release/merge.sh Modified: llvm/branches/release_38/lib/Analysis/MemoryDependenceAnalysis.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_38/lib/Analysis/MemoryDependenceAnalysis.cpp?rev=271394&r1=271393&r2=271394&view=diff ============================================================================== --- llvm/branches/release_38/lib/Analysis/MemoryDependenceAnalysis.cpp (original) +++ llvm/branches/release_38/lib/Analysis/MemoryDependenceAnalysis.cpp Wed Jun 1 09:10:10 2016 @@ -57,6 +57,11 @@ static cl::opt<unsigned> BlockScanLimit( cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)")); +static cl::opt<unsigned> BlockNumberLimit( + "memdep-block-number-limit", cl::Hidden, cl::init(1000), + cl::desc("The number of blocks to scan during memory " + "dependency analysis (default = 1000)")); + // Limit on the number of memdep results to process. static const unsigned int NumResultsLimit = 100; @@ -1246,6 +1251,8 @@ bool MemoryDependenceAnalysis::getNonLoc // won't get any reuse from currently inserted values, because we don't // revisit blocks after we insert info for them. unsigned NumSortedEntries = Cache->size(); + unsigned WorklistEntries = BlockNumberLimit; + bool GotWorklistLimit = false; DEBUG(AssertSorted(*Cache)); while (!Worklist.empty()) { @@ -1324,6 +1331,15 @@ bool MemoryDependenceAnalysis::getNonLoc goto PredTranslationFailure; } } + if (NewBlocks.size() > WorklistEntries) { + // Make sure to clean up the Visited map before continuing on to + // PredTranslationFailure. + for (unsigned i = 0; i < NewBlocks.size(); i++) + Visited.erase(NewBlocks[i]); + GotWorklistLimit = true; + goto PredTranslationFailure; + } + WorklistEntries -= NewBlocks.size(); Worklist.append(NewBlocks.begin(), NewBlocks.end()); continue; } @@ -1469,18 +1485,22 @@ bool MemoryDependenceAnalysis::getNonLoc if (SkipFirstBlock) return true; - for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) { - assert(I != Cache->rend() && "Didn't find current block??"); - if (I->getBB() != BB) + bool foundBlock = false; + for (NonLocalDepEntry &I: llvm::reverse(*Cache)) { + if (I.getBB() != BB) continue; - assert((I->getResult().isNonLocal() || !DT->isReachableFromEntry(BB)) && + assert((GotWorklistLimit || I.getResult().isNonLocal() || \ + !DT->isReachableFromEntry(BB)) && "Should only be here with transparent block"); - I->setResult(MemDepResult::getUnknown()); - Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), + foundBlock = true; + I.setResult(MemDepResult::getUnknown()); + Result.push_back(NonLocalDepResult(I.getBB(), I.getResult(), Pointer.getAddr())); break; } + (void)foundBlock; + assert((foundBlock || GotWorklistLimit) && "Current block not in cache?"); } // Okay, we're done now. If we added new values to the cache, re-sort it. Modified: llvm/branches/release_38/utils/release/merge.sh URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_38/utils/release/merge.sh?rev=271394&r1=271393&r2=271394&view=diff ============================================================================== --- llvm/branches/release_38/utils/release/merge.sh (original) +++ llvm/branches/release_38/utils/release/merge.sh Wed Jun 1 09:10:10 2016 @@ -17,12 +17,14 @@ set -e rev="" proj="" revert="no" +srcdir="" -function usage() { +usage() { echo "usage: `basename $0` [OPTIONS]" echo " -proj PROJECT The project to merge the result into" echo " -rev NUM The revision to merge into the project" echo " -revert Revert rather than merge the commit" + echo " -srcdir The root of the project checkout" } while [ $# -gt 0 ]; do @@ -35,6 +37,10 @@ while [ $# -gt 0 ]; do shift proj=$1 ;; + --srcdir | -srcdir | -s) + shift + srcdir=$1 + ;; -h | -help | --help ) usage ;; @@ -51,6 +57,10 @@ while [ $# -gt 0 ]; do shift done +if [ -z "$srcdir" ]; then + srcdir="$proj.src" +fi + if [ "x$rev" = "x" -o "x$proj" = "x" ]; then echo "error: need to specify project and revision" echo @@ -72,7 +82,7 @@ else fi svn log -c $rev http://llvm.org/svn/llvm-project/$proj/trunk >> $tempfile 2>&1 -cd $proj.src +cd "$srcdir" echo "# Updating tree" svn up _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
