[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 ↗

(On Diff #155710)

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 ↗

(On Diff #155710)

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 ↗

(On Diff #155710)

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 ↗

(On Diff #155710)

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

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.

llvm/trunk/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)) {
+        // We run Solve() after we resolved an undef in a function, because
+        // we might deduce a fact that eliminates an undef in another function.
+        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;
 

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

+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; CHECK-LABEL: @testf(
+; CHECK:         ret i32 undef
+;
+define internal i32 @testf() {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry, %if.then
+  br label %if.end
+
+if.end:                                          ; preds = %if.then1, %entry
+  ret i32 10
+}
+
+; CHECK-LABEL: @test1(
+; CHECK:         ret i32 undef
+;
+define internal i32 @test1() {
+entry:
+  br label %if.then
+
+if.then:                                          ; preds = %entry, %if.then
+  %call = call i32 @testf()
+  %res = icmp eq i32 %call, 10
+  br i1 %res, label %ret1, label %ret2
+
+ret1:                                           ; preds = %if.then, %entry
+  ret i32 99
+
+ret2:                                           ; preds = %if.then, %entry
+  ret i32 0
+}
+
+; CHECK-LABEL: @main(
+; CHECK-NEXT:    %res = call i32 @test1()
+; CHECK-NEXT:    ret i32 99
+;
+define i32 @main() {
+  %res = call i32 @test1()
+  ret i32 %res
+}

llvm/trunk/test/Transforms/SCCP/ipsccp-basic.ll

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