[IPSCCP] Do not zap return if the return value is overdefined at any call site.

[fhahn]

Summary

We cannot zap a return if the return value at any of the function's call
sites is overdefined. This can happen, for example, when the return
value is used as a condition on for a branch and the return value is
still unknown when the branch is visited during ResolvedUndefsIn(). Then
the return value of the call site will be force to false.

Alternatively, we could mark functions as 'do not zap' if we go to
overdefined when handling call instructions, but the current approach
seems more direct.

In general, it is unfortunate that we fail to do the optimal thing
here. I guess we could force the return value to the known constant
after solving to at least replace the uses, but this seems like a slight
hack without much benefit.

[efriedma]

Stuff like this really makes me want to kill off ResolveUndefsIn. But this works for now.

lib/Transforms/Scalar/SCCP.cpp

2021

I think cast<Instruction>(U) will fail if there's a BlockAddress user of F.

[fhahn]

In D49384#1164252, @efriedma wrote:

Stuff like this really makes me want to kill off ResolveUndefsIn. But this works for now.

Yeah I guess if we continue to make SCCP more powerful, we hit more cases like this. For example, the problem was exposed by rL336098. I am not sure what a good alternative to ResolvedUndefsIn() would be. Just marking undef conditions as overdefined after a round of Solve()? I am not sure how big the ResolvedUndefsIn contributes to the overall precision.

[efriedma]

Thought about it a bit more, came up with an alternative fix: https://reviews.llvm.org/D49408. It's a bit more aggressive, and avoids the weirdness of calling markForcedConstant on an arbitrary value.

Just marking undef conditions as overdefined after a round of Solve()?

I'm not completely sure.

The academic algorithm for SCCP has three lattice states. The first state, there's no viable path to execute the instruction producing the value ("undef"). The second state, all viable paths produce the same value ("constant"). The third state, there are multiple possible values ("overdefined").

The LLVM version essentially tries to incorporate a fourth state: the instruction executes, but the result is the LLVM value "undef", so we can choose a constant to replace it later. But the implementation is awkward because the lattice doesn't represent the difference between this state and the "undef" state, and we try to fix it up later in ResolveUndefsIn. I think we should fix the lattice to represent this explicitly: "undef" should be split into "dead" and "indeterminate". (This would probably allow SCCP to find more constants, because we wouldn't need to ResolvedUndefsIn on dead instructions.) If we do that, though, I guess we have to continue using something like ResolvedUndefsIn; but at least it would be more clear why it's necessary.

[davide]

FWIW, my take is that we should kill ResolvedUndefsIn (as already pointed by Eli, and probably me, and others in the past).
My take is that the benefit of having a forth lattice state is really little compared to the amount of effort we had to put to fix bugs.
If somebody is willing to take the time to do the work I'd rather zap away undef from the lattice and see how many constant we lose (and what's the runtime cost). But I understand this is a fair amount of work. That said, I think I like Eli's proof of concept a little better than this, so I'm happy if you want to pursue that path, Florian.

[fhahn]

In D49384#1164478, @efriedma wrote:

Thought about it a bit more, came up with an alternative fix: https://reviews.llvm.org/D49408. It's a bit more aggressive, and avoids the weirdness of calling markForcedConstant on an arbitrary value.

Great, I think back-propagating false to the condition is the biggest troublemaker, responsible for this bug and also D48327, so getting rid of it is great. And D49408 solves both problems.

[fhahn]

Abandoned in favor of D49408

lib/Transforms/Scalar/SCCP.cpp

for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
       }
 
       // Finally, delete the basic block.
       F.getBasicBlockList().erase(DeadBB);
     }
     BlocksToErase.clear();
   }
 
-  // If we inferred constant or undef return values for a function, we replaced
-  // all call uses with the inferred value.  This means we don't need to bother
-  // actually returning anything from the function.  Replace all return
+  // If we inferred constant or undef return values for a function and replace
+  // all call uses with the inferred value, it means we don't need to bother
+  // actually returning anything from the function. Replace all return
   // instructions with return undef.
   //
   // 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;
 
   const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     Function *F = I.first;
     if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
       continue;
+
+    if (any_of(F->users(), [&Solver](Value *U) {
+          assert(Solver.isBlockExecutable(cast<Instruction>(U)->getParent()) &&
+                 "All unreachable calls should have been removed already.");
+          return CallSite(U) && Solver.getLatticeValueFor(U).isOverdefined();
+        }))
+      continue;
+
     findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   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))

test/Transforms/IPConstantProp/return-zapped.ll

+; RUN: opt < %s -S -ipsccp | FileCheck %s
+
+; After the firs round of Solver.Solve(), the return value of @testf still
+; undefined as we hit a branch on undef. Therefore the conditional branch on
+; @testf's return value in @bar is unknown. In ResolvedUndefsIn, we force the
+; condition of the branch to false. We later discover that @testf actually
+; returns true and merge that value with the value at the call site, which
+; becomes overdefined. We cannot change the return value of @testf to undef,
+; because we failed to replace the result of the call with true.
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-LABEL: if.then:
+; CHECK:         [[CALL:%.+]] = call i1 @testf()
+; CHECK-NEXT:    br i1 [[CALL]], label %if.end, label %if.then
+;
+entry:
+  br label %if.then
+if.then:                                          ; preds = %entry, %if.then
+  %foo = phi i32 [ 0, %entry], [ %next, %if.then]
+  %next = add i32 %foo, 1
+  %call = call i1 @testf()
+  br i1 %call, label %if.end, label %if.then
+
+if.end:                                           ; preds = %if.then, %entry
+  ret void
+}
+
+define internal i1 @testf() {
+; CHECK-LABEL: define internal i1 @testf(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IF_END3:%.*]]
+; CHECK:       if.end3:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 undef, label %if.then1, label %if.end3
+
+if.then1:                                         ; preds = %if.end
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.then1, %entry
+  ret i1 true
+}
+
+
+; Call sites in unreachable blocks should not be a problem.
+; CHECK-LABEL: define i1 @test2() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   br label %if.end
+; CHECK-LABEL: if.end:                                           ; preds = %entry
+; CHECK-NEXT:   %call2 = call i1 @testf()
+; CHECK-NEXT:   ret i1 true
+define i1 @test2() {
+entry:
+  br label %if.end
+
+if.then:                                          ; preds = %entry, %if.then
+  %call = call i1 @testf()
+  br i1 %call, label %if.end, label %if.then
+
+if.end:                                           ; preds = %if.then, %entry
+  %call2 = call i1 @testf()
+  ret i1 %call2
+}
+
+; Non-callsite uses of a function are ignored.
+; CHECK-LABEL: @test3(i1 ()** %p) {
+; CHECK:  store i1 ()* @testf, i1 ()** %p
+; CHECK:  ret i1 true
+define i1 @test3(i1 ()** %p) {
+entry:
+  store i1 ()* @testf, i1 ()** %p
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %call2 = call i1 @testf()
+  ret i1 %call2
+}