[BasicAA] Reduce no of map searches. Assert map entry exists. [NFCI]

[asbirlea]

Summary

This is a refactoring patch.

• Reduce the number of map searches by reusing the iterator.
• Add asserts to check that the entry is in the cache, as this is something BasicAA relies on to avoid infinite recursion.

[chandlerc]

lib/Analysis/BasicAliasAnalysis.cpp

1587–1597

While it's a bit awkward, I'd create a scope here because re-using CacheIt will be so tempting and is wrong.

AliasResult OrigAliasResult;
{
  // Limited lifetime iterator as we can't re-use it once we begin processing.
  auto CacheIt = AliasCache.find(Locs);
  ...
}

1610–1612

Here and below, the original code does the same number of lookups and seems more clear?

[asbirlea]

Address comment.

lib/Analysis/BasicAliasAnalysis.cpp

1610–1612

Yes, that's true. This change refers to the second bullet point in the summary: adding the assert to check an entry was already in the map and it should only be updated here, never created.
I got tripped by this by accidentally clearing the cache and going into an infinite recursion.

Let me know if you'd prefer this in a separate change or the title updated to include this.

[chandlerc]

LGTM, really nice!

lib/Analysis/BasicAliasAnalysis.cpp

1610–1612

No, I'd missed that this was enabling the assert, and I understand why that's valuable here, thanks.

lib/Analysis/BasicAliasAnalysis.cpp

if (PN2->getParent() == PN->getParent()) {
         std::swap(Locs.first, Locs.second);
       // Analyse the PHIs' inputs under the assumption that the PHIs are
       // NoAlias.
       // If the PHIs are May/MustAlias there must be (recursively) an input
       // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
       // there must be an operation on the PHIs within the PHIs' value cycle
       // that causes a MayAlias.
       // Pretend the phis do not alias.
       AliasResult Alias = NoAlias;
-      assert(AliasCache.count(Locs) &&
+      AliasResult OrigAliasResult;
+      {
+        // Limited lifetime iterator invalidated by the aliasCheck call below.
+        auto CacheIt = AliasCache.find(Locs);
+        assert((CacheIt != AliasCache.end()) &&
                "There must exist an entry for the phi node");
-      AliasResult OrigAliasResult = AliasCache[Locs];
-      AliasCache[Locs] = NoAlias;
+        OrigAliasResult = CacheIt->second;
+        CacheIt->second = NoAlias;
+      }
 
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         AliasResult ThisAlias =
             aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
                        PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
                        V2Size, V2AAInfo);
         Alias = MergeAliasResults(ThisAlias, Alias);
         if (Alias == MayAlias)
           break;
       }
 
       // Reset if speculation failed.
-      if (Alias != NoAlias)
-        AliasCache[Locs] = OrigAliasResult;
-
+      if (Alias != NoAlias) {
+        auto Pair = AliasCache.insert(std::make_pair(Locs, OrigAliasResult));
+        assert(!Pair.second && "Entry must have existed");
+        Pair.first->second = OrigAliasResult;
+      }
       return Alias;
     }
 
   SmallVector<Value *, 4> V1Srcs;
   bool isRecursive = false;
   if (PV)  {
     // If we have PhiValues then use it to get the underlying phi values.
     const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
     std::swap(V1, V2);
     std::swap(O1, O2);
     std::swap(V1Size, V2Size);
     std::swap(V1AAInfo, V2AAInfo);
   }
   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
     AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo,
                                   V2, V2Size, V2AAInfo, O2);
-    if (Result != MayAlias)
-      return AliasCache[Locs] = Result;
+    if (Result != MayAlias) {
+      Pair = AliasCache.insert(std::make_pair(Locs, Result));
+      assert(!Pair.second && "Entry must have existed");
+      return Pair.first->second = Result;
+    }
   }
 
   if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
     std::swap(V1, V2);
     std::swap(O1, O2);
     std::swap(V1Size, V2Size);
     std::swap(V1AAInfo, V2AAInfo);
   }
   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
     AliasResult Result =
         aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2);
-    if (Result != MayAlias)
-      return AliasCache[Locs] = Result;
+    if (Result != MayAlias) {
+      Pair = AliasCache.insert(std::make_pair(Locs, Result));
+      assert(!Pair.second && "Entry must have existed");
+      return Pair.first->second = Result;
+    }
   }
 
   // If both pointers are pointing into the same object and one of them
   // accesses the entire object, then the accesses must overlap in some way.
   if (O1 == O2)
     if (V1Size.isPrecise() && V2Size.isPrecise() &&
         (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) ||
-         isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation)))
-      return AliasCache[Locs] = PartialAlias;
+         isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) {
+      Pair = AliasCache.insert(std::make_pair(Locs, PartialAlias));
+      assert(!Pair.second && "Entry must have existed");
+      return Pair.first->second = PartialAlias;
+    }
 
   // Recurse back into the best AA results we have, potentially with refined
   // memory locations. We have already ensured that BasicAA has a MayAlias
   // cache result for these, so any recursion back into BasicAA won't loop.
   AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second);
-  return AliasCache[Locs] = Result;
+  Pair = AliasCache.insert(std::make_pair(Locs, Result));
+  assert(!Pair.second && "Entry must have existed");
+  return Pair.first->second = Result;
 }
 
 /// Check whether two Values can be considered equivalent.
 ///
 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
 /// they can not be part of a cycle in the value graph by looking at all
 /// visited phi nodes an making sure that the phis cannot reach the value. We
 /// have to do this because we are looking through phi nodes (That is we say