[Attributor][NFCI] Avoid lookups when resolving returned values

[jdoerfert]

Summary

If the number of potentially returned values not change since the last
traversal we do not need to visit the returned values again. This works
as we only add values to the returned values set now.

[jdoerfert]

Remove accidentally included code

[jdoerfert]

Use the call site as a key for the cache

[sstefan1]

LGTM

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

 /// If there is a unique returned value R, the manifest method will:
 ///   - mark R with the "returned" attribute, if R is an argument.
 class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState {
 
   /// Mapping of values potentially returned by the associated function to the
   /// return instructions that might return them.
   DenseMap<Value *, SmallSetVector<ReturnInst *, 4>> ReturnedValues;
 
+  /// Mapping to remember the number of returned values for a call site such
+  /// that we can avoid updates if nothing changed.
+  DenseMap<const CallBase *, unsigned> NumReturnedValuesPerKnownAA;
+
+  /// Set of unresolved calls returned by the associated function.
   SmallSetVector<CallBase *, 4> UnresolvedCalls;
 
   /// State flags
   ///
   ///{
-  bool IsFixed;
-  bool IsValidState;
+  bool IsFixed = false;
+  bool IsValidState = true;
   ///}
 
 public:
   AAReturnedValuesImpl(const IRPosition &IRP) : AAReturnedValues(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     // Reset the state.
public:
   bool isAtFixpoint() const override { return IsFixed; }
 
   /// See AbstractState::isValidState().
   bool isValidState() const override { return IsValidState; }
 
   /// See AbstractState::indicateOptimisticFixpoint(...).
   ChangeStatus indicateOptimisticFixpoint() override {
     IsFixed = true;
-    IsValidState &= true;
     return ChangeStatus::UNCHANGED;
   }
 
   ChangeStatus indicatePessimisticFixpoint() override {
     IsFixed = true;
     IsValidState = false;
     return ChangeStatus::CHANGED;
   }
for (auto &RetValAAIt : RetValAA.returned_values()) {
       UnresolvedCalls.insert(CB);
       Unresolved = true;
       break;
     }
 
     if (Unresolved)
       continue;
 
+    // Now track transitively returned values.
+    unsigned &NumRetAA = NumReturnedValuesPerKnownAA[CB];
+    if (NumRetAA == RetValAA.getNumReturnValues()) {
+      LLVM_DEBUG(dbgs() << "[AAReturnedValues] Skip call as it has not "
+                           "changed since it was seen last\n");
+      continue;
+    }
+    NumRetAA = RetValAA.getNumReturnValues();
+
     for (auto &RetValAAIt : RetValAA.returned_values()) {
       Value *RetVal = RetValAAIt.first;
       if (Argument *Arg = dyn_cast<Argument>(RetVal)) {
         // Arguments are mapped to call site operands and we begin the traversal
         // again.
         bool Unused = false;
         RVState RVS({NewRVsMap, Unused, RetValAAIt.second});
         VisitReturnedValue(*CB->getArgOperand(Arg->getArgNo()), RVS);