From: Erik Eckstein Date: Tue, 13 Jan 2015 14:36:46 +0000 (+0000) Subject: Revert "SLPVectorizer: Cache results from memory alias checking." X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=046c3e807db7b9c5f5f934530ab9768da209f6d6 Revert "SLPVectorizer: Cache results from memory alias checking." The alias cache has a problem of incorrect collisions in case a new instruction is allocated at the same address as a previously deleted instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@225790 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp index 8fb87b80954..9281bcb2c51 100644 --- a/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -19,7 +19,6 @@ #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" @@ -389,15 +388,6 @@ static bool InTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst, } } -/// \returns the AA location that is being access by the instruction. -static AliasAnalysis::Location getLocation(Instruction *I, AliasAnalysis *AA) { - if (StoreInst *SI = dyn_cast(I)) - return AA->getLocation(SI); - if (LoadInst *LI = dyn_cast(I)) - return AA->getLocation(LI); - return AliasAnalysis::Location(); -} - /// Bottom Up SLP Vectorizer. class BoUpSLP { public: @@ -565,35 +555,6 @@ private: }; typedef SmallVector UserList; - /// Checks if two instructions may access the same memory. - /// - /// \p Loc1 is the location of \p Inst1. It is passed explicitly because it - /// is invariant in the calling loop. - bool isAliased(const AliasAnalysis::Location &Loc1, Instruction *Inst1, - Instruction *Inst2) { - - // First check if the result is already in the cache. - AliasCacheKey key = std::make_pair(Inst1, Inst2); - Optional &result = AliasCache[key]; - if (result.hasValue()) { - return result.getValue(); - } - AliasAnalysis::Location Loc2 = getLocation(Inst2, AA); - bool aliased = true; - if (Loc1.Ptr && Loc2.Ptr) { - // Do the alias check. - aliased = AA->alias(Loc1, Loc2); - } - // Store the result in the cache. - result = aliased; - return aliased; - } - - typedef std::pair AliasCacheKey; - - /// Cache for alias results. - DenseMap> AliasCache; - /// A list of values that need to extracted out of the tree. /// This list holds pairs of (Internal Scalar : External User). UserList ExternalUses; @@ -830,7 +791,7 @@ private: /// Checks if a bundle of instructions can be scheduled, i.e. has no /// cyclic dependencies. This is only a dry-run, no instructions are /// actually moved at this stage. - bool tryScheduleBundle(ArrayRef VL, BoUpSLP *SLP); + bool tryScheduleBundle(ArrayRef VL, AliasAnalysis *AA); /// Un-bundles a group of instructions. void cancelScheduling(ArrayRef VL); @@ -847,7 +808,7 @@ private: /// Updates the dependency information of a bundle and of all instructions/ /// bundles which depend on the original bundle. void calculateDependencies(ScheduleData *SD, bool InsertInReadyList, - BoUpSLP *SLP); + AliasAnalysis *AA); /// Sets all instruction in the scheduling region to un-scheduled. void resetSchedule(); @@ -1108,7 +1069,7 @@ void BoUpSLP::buildTree_rec(ArrayRef VL, unsigned Depth) { } BlockScheduling &BS = *BSRef.get(); - if (!BS.tryScheduleBundle(VL, this)) { + if (!BS.tryScheduleBundle(VL, AA)) { DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n"); BS.cancelScheduling(VL); newTreeEntry(VL, false); @@ -2499,7 +2460,7 @@ void BoUpSLP::optimizeGatherSequence() { // Groups the instructions to a bundle (which is then a single scheduling entity) // and schedules instructions until the bundle gets ready. bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef VL, - BoUpSLP *SLP) { + AliasAnalysis *AA) { if (isa(VL[0])) return true; @@ -2556,7 +2517,7 @@ bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef VL, DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block " << BB->getName() << "\n"); - calculateDependencies(Bundle, true, SLP); + calculateDependencies(Bundle, true, AA); // Now try to schedule the new bundle. As soon as the bundle is "ready" it // means that there are no cyclic dependencies and we can schedule it. @@ -2687,9 +2648,18 @@ void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI, } } +/// \returns the AA location that is being access by the instruction. +static AliasAnalysis::Location getLocation(Instruction *I, AliasAnalysis *AA) { + if (StoreInst *SI = dyn_cast(I)) + return AA->getLocation(SI); + if (LoadInst *LI = dyn_cast(I)) + return AA->getLocation(LI); + return AliasAnalysis::Location(); +} + void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD, bool InsertInReadyList, - BoUpSLP *SLP) { + AliasAnalysis *AA) { assert(SD->isSchedulingEntity()); SmallVector WorkList; @@ -2734,14 +2704,14 @@ void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD, // Handle the memory dependencies. ScheduleData *DepDest = BundleMember->NextLoadStore; if (DepDest) { - Instruction *SrcInst = BundleMember->Inst; - AliasAnalysis::Location SrcLoc = getLocation(SrcInst, SLP->AA); + AliasAnalysis::Location SrcLoc = getLocation(BundleMember->Inst, AA); bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory(); while (DepDest) { assert(isInSchedulingRegion(DepDest)); if (SrcMayWrite || DepDest->Inst->mayWriteToMemory()) { - if (SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)) { + AliasAnalysis::Location DstLoc = getLocation(DepDest->Inst, AA); + if (!SrcLoc.Ptr || !DstLoc.Ptr || AA->alias(SrcLoc, DstLoc)) { DepDest->MemoryDependencies.push_back(BundleMember); BundleMember->Dependencies++; ScheduleData *DestBundle = DepDest->FirstInBundle; @@ -2809,7 +2779,7 @@ void BoUpSLP::scheduleBlock(BlockScheduling *BS) { "scheduler and vectorizer have different opinion on what is a bundle"); SD->FirstInBundle->SchedulingPriority = Idx++; if (SD->isSchedulingEntity()) { - BS->calculateDependencies(SD, false, this); + BS->calculateDependencies(SD, false, AA); NumToSchedule++; } }