SLPVectorizer: limit the number of alias checks to reduce the runtime.

[eeckstein]

Summary

Beside caching the alias results, this is another step to reduce the SLPVectorizer's runtime.
In case of blocks with many memory-accessing instructions, alias checking can take lot of time (because calculating the memory dependencies has quadratic complexity).
I chose a limit which resulted in no changes when running the benchmarks.

[aschwaighofer]

I think that this should be a global at the top of the file so that it is more visible to folks would want to experiment with thresholds.

Maybe we could also make the name reflect that is only counting the failed alias checks: FailedAliasChecksLimit or so.

Otherwise, LGTM.

[eeckstein]

Arnold, thanks for your comments.
I renamed the const to "AliasedCheckLimit"

[eeckstein]

Committed in r226439

lib/Transforms/Vectorize/SLPVectorizer.cpp

 
 static const unsigned RecursionMaxDepth = 12;
 
+// Limit the number of alias checks. The limit is chosen so that
+// it has no negative effect on the llvm benchmarks.
+static const unsigned AliasedCheckLimit = 10;
+
 /// \returns the parent basic block if all of the instructions in \p VL
 /// are in the same block or null otherwise.
 static BasicBlock *getSameBlock(ArrayRef<Value *> VL) {

           Instruction *SrcInst = BundleMember->Inst;
           AliasAnalysis::Location SrcLoc = getLocation(SrcInst, SLP->AA);
           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
+          unsigned numAliased = 0;
 
           while (DepDest) {
             assert(isInSchedulingRegion(DepDest));
             if (SrcMayWrite || DepDest->Inst->mayWriteToMemory()) {
-              if (SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)) {
+
+              // Limit the number of alias checks, becaus SLP->isAliased() is
+              // the expensive part in the following loop.
+              if (numAliased >= AliasedCheckLimit
+                  || SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)) {
+
+                // We increment the counter only if the locations are aliased
+                // (instead of counting all alias checks). This gives a better
+                // balance between reduced runtime accurate dependencies.
+                numAliased++;
+
                 DepDest->MemoryDependencies.push_back(BundleMember);
                 BundleMember->Dependencies++;
                 ScheduleData *DestBundle = DepDest->FirstInBundle;