[SCCP] zap multiple return values

[davide]

Summary

We can replace the return values with undef if we replaced all the call uses with a constant/undef, in the multiple return value case.

[eli.friedman]

lib/Transforms/Scalar/SCCP.cpp

1908

Given the isStructTy assert, can you just use cast<> here?

1914

If this actually passes make check, we need more tests. (There are two loops here.)

[davide]

Fixed a silly bug, added a test.

lib/Transforms/Scalar/SCCP.cpp

1908

Done.

1914

Indeed.

[davide]

Pass AddressTakenFunctions by reference to avoid an useless copy.

[davide]

ping

[eli.friedman]

Sorry about the delay. LGTM.

[davide]

ping

In D22336#490128, @eli.friedman wrote:

Sorry about the delay. LGTM.

Thanks for your review, Eli.

lib/Transforms/Scalar/SCCP.cpp

   }
 
   /// getTrackedGlobals - Get and return the set of inferred initializers for
   /// global variables.
   const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
     return TrackedGlobals;
   }
 
+  /// getMRVFunctionsTracked - Get the set of functions which return multiple
+  /// values tracked by the pass.
+  const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
+    return MRVFunctionsTracked;
+  }
+
   void markOverdefined(Value *V) {
     assert(!V->getType()->isStructTy() && "Should use other method");
     markOverdefined(ValueState[V], V);
   }
 
   /// markAnythingOverdefined - Mark the specified value overdefined.  This
   /// works with both scalars and structs.
   void markAnythingOverdefined(Value *V) {
     if (StructType *STy = dyn_cast<StructType>(V->getType()))
       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
         markOverdefined(getStructValueState(V, i), V);
     else
       markOverdefined(V);
   }
 
+  // isStructLatticeConstant - Return true if all the lattice values
+  // corresponding to elements of the structure are not overdefined,
+  // false otherwise.
+  bool isStructLatticeConstant(Function *F, StructType *STy) {
+    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
+      const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
+      assert(It != TrackedMultipleRetVals.end());
+      LatticeVal LV = It->second;
+      if (LV.isOverdefined())
+        return false;
+    }
+    return true;
+  }
+
 private:
   // pushToWorkList - Helper for markConstant/markForcedConstant
   void pushToWorkList(LatticeVal &IV, Value *V) {
     if (IV.isOverdefined())
       return OverdefinedInstWorkList.push_back(V);
     InstWorkList.push_back(V);
   }
 

       // of label.
     } else {
       return true;
     }
   }
   return false;
 }
 
+static void findReturnsToZap(Function &F,
+                             SmallPtrSet<Function *, 32> AddressTakenFunctions,
+                             SmallVector<ReturnInst *, 8> &ReturnsToZap) {
+  // We can only do this if we know that nothing else can call the function.
+  if (!F.hasLocalLinkage() || AddressTakenFunctions.count(&F))
+    return;
+
+  for (BasicBlock &BB : F)
+    if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
+      if (!isa<UndefValue>(RI->getOperand(0)))
+        ReturnsToZap.push_back(RI);
+}
+
 static bool runIPSCCP(Module &M, const DataLayout &DL,
                       const TargetLibraryInfo *TLI) {
   SCCPSolver Solver(DL, TLI);
 
   // AddressTakenFunctions - This set keeps track of the address-taken functions
   // that are in the input.  As IPSCCP runs through and simplifies code,
   // functions that were address taken can end up losing their
   // address-taken-ness.  Because of this, we keep track of their addresses from

   //
   // Do this in two stages: first identify the functions we should process, then
   // actually zap their returns.  This is important because we can only do this
   // if the address of the function isn't taken.  In cases where a return is the
   // last use of a function, the order of processing functions would affect
   // whether other functions are optimizable.
   SmallVector<ReturnInst*, 8> ReturnsToZap;
 
-  // TODO: Process multiple value ret instructions also.
   const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     Function *F = I.first;
     if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
       continue;
+    findReturnsToZap(*F, AddressTakenFunctions, ReturnsToZap);
+  }
 
-    // We can only do this if we know that nothing else can call the function.
-    if (!F->hasLocalLinkage() || AddressTakenFunctions.count(F))
-      continue;
-
-    for (BasicBlock &BB : *F)
-      if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
-        if (!isa<UndefValue>(RI->getOperand(0)))
-          ReturnsToZap.push_back(RI);
+  for (const auto &F : Solver.getMRVFunctionsTracked()) {
+    assert(F->getReturnType()->isStructTy() &&
+           "The return type should be a struct");
+    StructType *STy = cast<StructType>(F->getReturnType());
+    if (Solver.isStructLatticeConstant(F, STy))
+      findReturnsToZap(*F, AddressTakenFunctions, ReturnsToZap);
   }
 
   // Zap all returns which we've identified as zap to change.
   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
     Function *F = ReturnsToZap[i]->getParent()->getParent();
     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
   }
 

test/Transforms/SCCP/dont-zap-return.ll

+; RUN: opt -ipsccp < %s -S | FileCheck %s
+
+define internal {i32, i32} @identity(i32 %patatino) {
+  %foo = insertvalue {i32, i32} {i32 1, i32 undef}, i32 %patatino, 1
+  ret {i32, i32} %foo
+}
+
+; Check that the return value is not transformed to undef
+; CHECK: define internal { i32, i32 } @identity(i32 %patatino) {
+; CHECK-NEXT:  %foo = insertvalue { i32, i32 } { i32 1, i32 undef }, i32 %patatino, 1
+; CHECK-NEXT:  ret { i32, i32 } %foo
+; CHECK-NEXT: }
+
+
+define {i32, i32} @caller(i32 %pat) {
+  %S1 = call {i32, i32} @identity(i32 %pat)
+  ret {i32, i32} %S1
+}
+
+; Check that we don't invent values and propagate them.
+; CHECK: define { i32, i32 } @caller(i32 %pat) {
+; CHECK-NEXT:  %S1 = call { i32, i32 } @identity(i32 %pat)
+; CHECK-NEXT:  ret { i32, i32 } %S1
+; CHECK-NEXT: }

test/Transforms/SCCP/ipsccp-basic.ll

 
 define internal {i64,i64} @test4a() {
   %a = insertvalue {i64,i64} undef, i64 4, 1
   %b = insertvalue {i64,i64} %a, i64 5, 0
   ret {i64,i64} %b
 }
 
 ; CHECK-LABEL: define internal { i64, i64 } @test4a(
-; CHECK-NEXT:   ret { i64, i64 } { i64 5, i64 4 }
+; CHECK-NEXT:   ret { i64, i64 } undef
 ; CHECK-NEXT: }
 
 define i64 @test4b() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
   %a = invoke {i64,i64} @test4a()
           to label %A unwind label %B
 A:
   %b = extractvalue {i64,i64} %a, 0
   %c = call i64 @test4c(i64 %b)

 %T = type {i32,i32}
 
 define internal %T @test7a(i32 %A) {
   %X = add i32 1, %A
   %mrv0 = insertvalue %T undef, i32 %X, 0
   %mrv1 = insertvalue %T %mrv0, i32 %A, 1
   ret %T %mrv1
 ; CHECK-LABEL: @test7a(
-; CHECK-NEXT: ret %T { i32 18, i32 17 }
+; CHECK-NEXT: ret %T undef
 }
 
 define i32 @test7b() {
   %X = call %T @test7a(i32 17)
         %Y = extractvalue %T %X, 0
   %Z = add i32 %Y, %Y
   ret i32 %Z
 ; CHECK-LABEL: define i32 @test7b(