[IPSCCP] Run Solve each time we resolved an undef in a function.

[fhahn]

Summary

Once we resolved an undef in a function we can run Solve, which could
lead to finding a constant return value for the function, which in turn
could turn undefs into constants in other functions that call it, before
resolving undefs there.

Computationally the amount of work we are doing stays the same, just the
order we process things is slightly different and potentially there are
a few less undefs to resolve.

We are still relying on the order of functions in the IR, which means
depending on the order, we are able to resolve the optimal undef first
or not. For example, if @test1 comes before @testf, we find the constant
return value of @testf too late and we cannot use it while solving
@test1.

This on its own does not lead to more constants removed in the
test-suite, probably because currently we have to be very lucky to visit
applicable functions in the right order.

Maybe it would make sense to resolve undefs depending on the call graph,
e.g. leaf functions first, but I am not sure how/if that would be doable
in a lightweight fashion.

[efriedma]

Computationally the amount of work we are doing stays the same

I don't think this is right; each call to Solve() has a cost proportional to the size of the module, if I'm not mistaken.

Maybe it would make sense to resolve undefs depending on the call graph, e.g. leaf functions first

We have scc_iterator, but I'm not sure resolving leaf functions first is actually more effective in general.

test/Transforms/SCCP/ipsccp-basic.ll

253

What is this supposed to be testing? ctpop is readnone.

[fhahn]

In D49385#1164243, @efriedma wrote:

Computationally the amount of work we are doing stays the same

I don't think this is right; each call to Solve() has a cost proportional to the size of the module, if I'm not mistaken.

IIUC Solve() only processes instructions in OverdefinedInstWorkList, InstWorkList and BBWorkList. Before calling ResolvedUndefsIn, those should be empty and ResolvedUndefsIn(F) should only add the instruction we resolved a undef for or mark the false successor of a conditional branch on undef executable.

So calling Solve() after resolving undefs should process roughly the same instructions as adding the resolved undef for each function to the worklists. If a discovered return value helps us to get rid of an undef in a later function, we would add a different undef to the worklist, leading to a slightly different set of instructions visited.

Maybe it would make sense to resolve undefs depending on the call graph, e.g. leaf functions first

We have scc_iterator, but I'm not sure resolving leaf functions first is actually more effective in general.

Yeah I do not think that will be optimal in all cases, I'll give it a try though. Another strategy that might make sense would be resolving the functions with no unknown incoming values/function calls, but I guess in general it's quite tricky.

test/Transforms/SCCP/ipsccp-basic.ll

253

I am not entirely sure. I think what happen before was that we marked call i64 @test11a() as overdefined because test11a was unknown, and now we discover the return value of test11a first and can fold llvm.ctpop.i64 based on the known argument.

[efriedma]

Oh, didn't realize we kept separate worklists like that. LGTM, then.

test/Transforms/SCCP/ipsccp-basic.ll

256

Please change this test to return the result of the ctpop call, so it's clear it's getting folded to zero or whatever.

[davide]

LGTM modulo minor.

lib/Transforms/Scalar/SCCP.cpp

1911–1913

Please add a comment explaining what we're doing here.

[jdoerfert]

llvm/trunk/test/Transforms/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll

15 ↗

(On Diff #155877)

This test seems broken to me:
(1) branching on undef is UB (I think).
(2) even if it's not UB, what other than 10 would this function return? Literally looking at the single return statements makes this already clear. So if it returns, it has to be 10.

I'll put a patch with IPConstantProp tests improvements up soon and for this one I have looks sth like this:

define internal i32 @testf(i1 %c) #0 { 
entry:
  br i1 %c, label %if.cond, label %if.end
if.cond: 
  br i1 undef, label %if.then, label %if.end
if.then:
  ret i32 99
if.end:
  ret i32 10
}

Let me know what you think.

lib/Transforms/Scalar/SCCP.cpp

bool llvm::runIPSCCP(Module &M, const DataLayout &DL,
   for (GlobalVariable &G : M.globals()) {
     G.removeDeadConstantUsers();
     if (canTrackGlobalVariableInterprocedurally(&G))
       Solver.TrackValueOfGlobalVariable(&G);
   }
 
   // Solve for constants.
   bool ResolvedUndefs = true;
-  while (ResolvedUndefs) {
-    Solver.Solve();
-
+  while (ResolvedUndefs) {
     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
     ResolvedUndefs = false;
     for (Function &F : M)
-      ResolvedUndefs |= Solver.ResolvedUndefsIn(F);
+      if (Solver.ResolvedUndefsIn(F)) {
+        Solver.Solve();
+        ResolvedUndefs = true;
+      }
   }
 
   bool MadeChanges = false;
 
   // Iterate over all of the instructions in the module, replacing them with
   // constants if we have found them to be of constant values.
   SmallVector<BasicBlock*, 512> BlocksToErase;
 

test/Transforms/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll

+; RUN: opt < %s -S -ipsccp | FileCheck %s
+
+; We re-run the solver each time we resolved an undef in a function. This allows
+; us to find the constant return value of @testf before resolving undefs in
+; @test1.
+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 undef
+;
+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
+}
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-LABEL: if.then:
+; CHECK:         call i1 @testf()
+; CHECK-NEXT:    br i1 true, 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
+}

test/Transforms/SCCP/ipsccp-basic.ll

define i64 @test11a() {
   ret i64 %xor
 ; CHECK-LABEL: define i64 @test11a
 ; CHECK: ret i64 0
 }
 
 define void @test11b() {
   %call1 = call i64 @test11a()
   %call2 = call i64 @llvm.ctpop.i64(i64 %call1)
   ret void
 ; CHECK-LABEL: define void @test11b
 ; CHECK: %[[call1:.*]] = call i64 @test11a()
-; CHECK: %[[call2:.*]] = call i64 @llvm.ctpop.i64(i64 0)
+; CHECK-NOT: call i64 @llvm.ctpop.i64
 }
 
 declare i64 @llvm.ctpop.i64(i64)