[PhiValues] Remove redundant map searches

[ekatz]

Summary

Remove redundant map searches.
For example, every call to "operator[]" is actually translated to a "find" call, and 2 consecutive calls to the operator, without changing the map in-between, is just redundant, and inefficient.

[ekatz]

Ping

[ekatz]

Ping

[john.brawn]

Reducing the repeated lookups in DepthMap seems reasonable, but the changes to the loop where ReachableMap is updated make it quite a bit more difficult to understand (as the task of updating ReachableMap is smushed together with the task of updating NonPhiReachableMap). Could you do just the first part? Or are there cases where this majorly speeds things up?

llvm/lib/Analysis/PhiValues.cpp

88

It looks like this line is deleted and there's no equivalent to it in the patch.

[ekatz]

llvm/lib/Analysis/PhiValues.cpp

88

It is done at line 124 of the patch.

[ekatz]

Separated the update of NonPhiReachableMap from ReachableMap as requested.

[john.brawn]

LGTM

llvm/include/llvm/Analysis/PhiValues.h

private:
   /// A set of callbacks to the values that processPhi has seen.
   DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
 
   /// The function that the PhiValues is for.
   const Function &F;
 
   /// Process a phi so that its entries in the depth and reachable maps are
   /// fully populated.
-  void processPhi(const PHINode *PN, SmallVector<const PHINode *, 8> &Stack);
+  void processPhi(const PHINode *PN, SmallVectorImpl<const PHINode *> &Stack);
 };
 
 /// The analysis pass which yields a PhiValues
 ///
 /// The analysis does nothing by itself, and just returns an empty PhiValues
 /// which will get filled in as it's used.
 class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> {
   friend AnalysisInfoMixin<PhiValuesAnalysis>;

llvm/lib/Analysis/PhiValues.cpp

 //  * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
 //    never completes a component before the components reachable from it have
 //    been completed. This means that when we complete a component we have
 //    everything we need to collect the values reachable from that component.
 //  * We collect both the non-phi values reachable from each SCC, as that's what
 //    we're ultimately interested in, and all of the reachable values, i.e.
 //    including phis, as that makes invalidateValue easier.
 void PhiValues::processPhi(const PHINode *Phi,
-                           SmallVector<const PHINode *, 8> &Stack) {
+                           SmallVectorImpl<const PHINode *> &Stack) {
   // Initialize the phi with the next depth number.
   assert(DepthMap.lookup(Phi) == 0);
   assert(NextDepthNumber != UINT_MAX);
-  unsigned int DepthNumber = ++NextDepthNumber;
-  DepthMap[Phi] = DepthNumber;
+  unsigned int RootDepthNumber = ++NextDepthNumber;
+  DepthMap[Phi] = RootDepthNumber;
 
   // Recursively process the incoming phis of this phi.
   TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
   for (Value *PhiOp : Phi->incoming_values()) {
     if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
       // Recurse if the phi has not yet been visited.
-      if (DepthMap.lookup(PhiPhiOp) == 0)
+      unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp);
+      if (OpDepthNumber == 0) {
         processPhi(PhiPhiOp, Stack);
-      assert(DepthMap.lookup(PhiPhiOp) != 0);
+        OpDepthNumber = DepthMap.lookup(PhiPhiOp);
+        assert(OpDepthNumber != 0);
+      }
       // If the phi did not become part of a component then this phi and that
       // phi are part of the same component, so adjust the depth number.
-      if (!ReachableMap.count(DepthMap[PhiPhiOp]))
-        DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
+      if (!ReachableMap.count(OpDepthNumber))
+        DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber);
     } else {
       TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
     }
   }
 
   // Now that incoming phis have been handled, push this phi to the stack.
   Stack.push_back(Phi);
 
   // If the depth number has not changed then we've finished collecting the phis
   // of a strongly connected component.
-  if (DepthMap[Phi] == DepthNumber) {
+  if (DepthMap[Phi] == RootDepthNumber) {
     // Collect the reachable values for this component. The phis of this
-    // component will be those on top of the depth stach with the same or
+    // component will be those on top of the depth stack with the same or
     // greater depth number.
-    ConstValueSet Reachable;
-    while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) {
+    ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
+    while (true) {
       const PHINode *ComponentPhi = Stack.pop_back_val();
       Reachable.insert(ComponentPhi);
-      DepthMap[ComponentPhi] = DepthNumber;
+
       for (Value *Op : ComponentPhi->incoming_values()) {
         if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
           // If this phi is not part of the same component then that component
           // is guaranteed to have been completed before this one. Therefore we
           // can just add its reachable values to the reachable values of this
           // component.
-          auto It = ReachableMap.find(DepthMap[PhiOp]);
+          unsigned int OpDepthNumber = DepthMap[PhiOp];
+          if (OpDepthNumber != RootDepthNumber) {
+            auto It = ReachableMap.find(OpDepthNumber);
             if (It != ReachableMap.end())
               Reachable.insert(It->second.begin(), It->second.end());
-        } else {
-          Reachable.insert(Op);
           }
+        } else
+          Reachable.insert(Op);
       }
+
+      if (Stack.empty())
+        break;
+
+      unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
+      if (ComponentDepthNumber < RootDepthNumber)
+        break;
+
+      ComponentDepthNumber = RootDepthNumber;
     }
-    ReachableMap.insert({DepthNumber,Reachable});
 
     // Filter out phis to get the non-phi reachable values.
-    ValueSet NonPhi;
+    ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
     for (const Value *V : Reachable)
       if (!isa<PHINode>(V))
-        NonPhi.insert(const_cast<Value*>(V));
-    NonPhiReachableMap.insert({DepthNumber,NonPhi});
+        NonPhi.insert(const_cast<Value *>(V));
   }
 }
 
 const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
-  if (DepthMap.count(PN) == 0) {
+  unsigned int DepthNumber = DepthMap.lookup(PN);
+  if (DepthNumber == 0) {
     SmallVector<const PHINode *, 8> Stack;
     processPhi(PN, Stack);
+    DepthNumber = DepthMap.lookup(PN);
     assert(Stack.empty());
+    assert(DepthNumber != 0);
   }
-  assert(DepthMap.lookup(PN) != 0);
-  return NonPhiReachableMap[DepthMap[PN]];
+  return NonPhiReachableMap[DepthNumber];
 }
 
 void PhiValues::invalidateValue(const Value *V) {
   // Components that can reach V are invalid.
   SmallVector<unsigned int, 8> InvalidComponents;
   for (auto &Pair : ReachableMap)
     if (Pair.second.count(V))
       InvalidComponents.push_back(Pair.first);