diff options
| -rw-r--r-- | lib/Analysis/MemoryDependenceAnalysis.cpp | 39 | ||||
| -rw-r--r-- | test/Transforms/GVN/2009-01-21-SortInvalidation.ll | 55 |
2 files changed, 91 insertions, 3 deletions
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 6818da8..ddfb26e 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -326,6 +326,19 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { return LocalCache; } +#ifndef NDEBUG +/// AssertSorted - This method is used when -debug is specified to verify that +/// cache arrays are properly kept sorted. +static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, + int Count = -1) { + if (Count == -1) Count = Cache.size(); + if (Count == 0) return; + + for (unsigned i = 1; i != unsigned(Count); ++i) + assert(Cache[i-1] <= Cache[i] && "Cache isn't sorted!"); +} +#endif + /// getNonLocalCallDependency - Perform a full dependency query for the /// specified call, returning the set of blocks that the value is /// potentially live across. The returned set of results will include a @@ -386,6 +399,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { SmallPtrSet<BasicBlock*, 64> Visited; unsigned NumSortedEntries = Cache.size(); + DEBUG(AssertSorted(Cache)); // Iterate while we still have blocks to update. while (!DirtyBlocks.empty()) { @@ -398,6 +412,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // Do a binary search to see if we already have an entry for this block in // the cache set. If so, find it. + DEBUG(AssertSorted(Cache, NumSortedEntries)); NonLocalDepInfo::iterator Entry = std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries, std::make_pair(DirtyBB, MemDepResult())); @@ -647,6 +662,7 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // 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(); + DEBUG(AssertSorted(*Cache)); while (!Worklist.empty()) { BasicBlock *BB = Worklist.pop_back_val(); @@ -659,6 +675,7 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // Get the dependency info for Pointer in BB. If we have cached // information, we will use it, otherwise we compute it. + DEBUG(AssertSorted(*Cache, NumSortedEntries)); MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad, BB, Cache, NumSortedEntries); @@ -705,7 +722,7 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // If this is directly a PHI node, just use the incoming values for each // pred as the phi translated version. if (PHINode *PtrPHI = dyn_cast<PHINode>(PtrInst)) { - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI){ + for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { BasicBlock *Pred = *PI; Value *PredPtr = PtrPHI->getIncomingValueForBlock(Pred); @@ -728,6 +745,21 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // treat this as a phi translation failure. goto PredTranslationFailure; } + + // We may have added values to the cache list before this PHI + // translation. If so, we haven't done anything to ensure that the + // cache remains sorted. Sort it now (if needed) so that recursive + // invocations of getNonLocalPointerDepFromBB that could reuse the cache + // value will only see properly sorted cache arrays. + if (NumSortedEntries != Cache->size()) { + std::sort(Cache->begin(), Cache->end()); + NumSortedEntries = Cache->size(); + } + + // FIXME: it is entirely possible that PHI translating will end up with + // the same value. Consider PHI translating something like: + // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need* + // to recurse here, pedantically speaking. // If we have a problem phi translating, fall through to the code below // to handle the failure condition. @@ -739,7 +771,8 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // Refresh the CacheInfo/Cache pointer so that it isn't invalidated. CacheInfo = &NonLocalPointerDeps[CacheKey]; Cache = &CacheInfo->second; - + NumSortedEntries = Cache->size(); + // Since we did phi translation, the "Cache" set won't contain all of the // results for the query. This is ok (we can still use it to accelerate // specific block queries) but we can't do the fastpath "return all @@ -817,7 +850,7 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // Added many values, do a full scale sort. std::sort(Cache->begin(), Cache->end()); } - + DEBUG(AssertSorted(*Cache)); return false; } diff --git a/test/Transforms/GVN/2009-01-21-SortInvalidation.ll b/test/Transforms/GVN/2009-01-21-SortInvalidation.ll new file mode 100644 index 0000000..51ca6cb --- /dev/null +++ b/test/Transforms/GVN/2009-01-21-SortInvalidation.ll @@ -0,0 +1,55 @@ +; RUN: llvm-as < %s | opt -gvn | llvm-dis +; PR3358 +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" +target triple = "x86_64-unknown-linux-gnu" + %struct.re_pattern_buffer = type { i8*, i64, i64, i64, i8*, i8*, i64, i8 } + %struct.re_registers = type { i32, i32*, i32* } + +define fastcc i32 @byte_re_match_2_internal(%struct.re_pattern_buffer* nocapture %bufp, i8* %string1, i32 %size1, i8* %string2, i32 %size2, i32 %pos, %struct.re_registers* %regs, i32 %stop) nounwind { +entry: + br label %bb159 + +succeed_label: ; preds = %bb159 + ret i32 0 + +bb159: ; preds = %bb664, %bb554, %bb159, %bb159, %bb159, %entry + %d.0 = phi i8* [ null, %entry ], [ %d.0, %bb159 ], [ %d.0, %bb554 ], [ %d.0, %bb159 ], [ %d.0, %bb159 ], [ %d.12, %bb664 ] ; <i8*> [#uses=5] + switch i32 0, label %bb661 [ + i32 0, label %bb159 + i32 1, label %succeed_label + i32 13, label %bb159 + i32 14, label %bb159 + i32 16, label %bb411 + i32 24, label %bb622 + i32 28, label %bb543 + ] + +bb411: ; preds = %bb411, %bb159 + br label %bb411 + +bb543: ; preds = %bb159 + br i1 false, label %bb549, label %bb550 + +bb549: ; preds = %bb543 + br label %bb554 + +bb550: ; preds = %bb543 + br i1 false, label %bb554, label %bb552 + +bb552: ; preds = %bb550 + %0 = load i8* %d.0, align 8 ; <i8> [#uses=0] + br label %bb554 + +bb554: ; preds = %bb552, %bb550, %bb549 + br i1 false, label %bb159, label %bb661 + +bb622: ; preds = %bb622, %bb159 + br label %bb622 + +bb661: ; preds = %bb554, %bb159 + %d.12 = select i1 false, i8* null, i8* null ; <i8*> [#uses=1] + br label %bb664 + +bb664: ; preds = %bb664, %bb661 + br i1 false, label %bb159, label %bb664 +} |