[CVP] simplify phi with constant incoming values that match common variable edge values

[spatel]

Summary

This is based on an example that was recently posted on llvm-dev:

void *propagate_null(void* b, int* g) {
        if (!b) {
                return 0;
        }
        (*g)++;
        return b;
}

https://godbolt.org/g/xYk3qG

The original code or constant propagation in other passes has obscured the fact that the phi can be removed completely.

There's an instcombine proposal to fix part of this at D45378, but I don't think we want instcombine doing things like that (and I'm not sure that patch is correct as-is).

[efriedma]

Any idea how often this triggers in practice?

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

156

This could potentially be improved to handle the !CommonValue case, I think, but I guess it might be tricky to find the appropriate value.

166

I don't think you have to check this separately for each incoming block; it should be enough that CommonInst dominates the block which contains the PHI node.

[fhahn]

test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

5

It looks like the reason we miss those cases is that we are missing the links between the null constants in the comparison and the PHI node.

Now, if we would have something like the code below, GVN could handle it.

define i8* @simplify_phi_common_value_op0(i8* %ptr, i32* %b, i8* %cmp) {
entry:
  %null.v = call i8* @llvm.ssa.copy.p0i8(i8* null)
  %isnull = icmp eq i8* %ptr, %cmp
  br i1 %isnull, label %return, label %else

else:                                             ; preds = %entry
  %lb = load i32, i32* %b
  %add = add nsw i32 %lb, 1
  store i32 %add, i32* %b
  br label %return

return:                                           ; preds = %else, %entry
  ret i8* %ptr
}

Unfortunately I don't think we have an easy way to get to that. In theory, I think should be able to annotate constants with the possible variables they are equal to, similar to what PredicateInfo does. Then we could use that to check if a constant is equal to a helpful variable. But that is a long shot and also (much) more work than this solution.

[spatel]

In D45448#1062055, @efriedma wrote:

Any idea how often this triggers in practice?

I didn't, but I added a debug stat and built test-suite -O3. This fired 94 times across 48 files.

For some context, the existing CVP phi optimization counter shows that it fired 6758 times across 680 files. That one counts both the existing threading over select transform here in CVP and any folds done by instsimplify when called from here.

Not sure how to judge this data in the larger context...rare, but not impossible, so worth the effort of looking for the pattern?

[spatel]

Patch updated:

1. Move the dominance check, so it only happens once. This matches the logic in InstSimplify that handles the simpler case of a phi where all incoming values are identical except for undefs.
2. Added a debug statistic to count how often this fires.

To expand on the previous test-suite experiment, I moved the existing counter above the call to InstSimplify (that's not in this patch though). This tells us how often the phi-select transform fires vs. the common value simplification in InstSimplify. The split of the 6758 cases is: 1830 are here in CVP for the select transform and 4928 is the easy elimination of a phi with all common incoming values in InstSimplify. So we use the more complicated common value analysis of this patch about 2% (94/4928) of the time to eliminate a phi.

[efriedma]

Seems like it triggers frequently enough to be worth doing.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

161

if (!SQ.DT->dominates(CommonInst, P->getParent())) is probably closer to what you want; the two-instruction form actually scans the block if the two instructions are in the same BB. (We should probably get rid of the two-instruction form at some point...)

[spatel]

Patch updated:
Fixed the call to dominates() to use the phi's block, not the phi itself.

[efriedma]

LGTM

[• dberlin]

(and i have patches to start down this path if anyone is ever interested)

[fhahn]

In D45448#1063675, @dberlin wrote:

(and i have patches to start down this path if anyone is ever interested)

Looks like I am missing something here. Down which path? :)

[• dberlin]

oh phabricator email and it's inability to be consistent about putting emails in comments.
Read the thread on llvm-commits and it'll make more sense :)

[fhahn]

In D45448#1064926, @dberlin wrote:

oh phabricator email and it's inability to be consistent about putting emails in comments.
Read the thread on llvm-commits and it'll make more sense :)

Oh yes! Weirdly I still could not find it on the list.

[• dberlin]

https://bugs.llvm.org/show_bug.cgi?id=34531

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "correlated-value-propagation"
 
 STATISTIC(NumPhis,      "Number of phis propagated");
+STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
 STATISTIC(NumUDivs,     "Number of udivs whose width was decreased");
 STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
   S->replaceAllUsesWith(ReplaceWith);
   S->eraseFromParent();
 
   ++NumSelects;
 
   return true;
 }
 
+/// Try to simplify a phi with constant incoming values that match the edge
+/// values of a non-constant value on all other edges:
+/// bb0:
+///   %isnull = icmp eq i8* %x, null
+///   br i1 %isnull, label %bb2, label %bb1
+/// bb1:
+///   br label %bb2
+/// bb2:
+///   %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
+/// -->
+///   %r = %x
+static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI,
+                                   const SimplifyQuery &SQ) {
+  // Collect incoming constants and initialize possible common value.
+  SmallVector<std::pair<Constant *, unsigned>, 4> IncomingConstants;
+  Value *CommonValue = nullptr;
+  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
+    Value *Incoming = P->getIncomingValue(i);
+    if (auto *IncomingConstant = dyn_cast<Constant>(Incoming)) {
+      IncomingConstants.push_back(std::make_pair(IncomingConstant, i));
+    } else if (!CommonValue) {
+      // The potential common value is initialized to the first non-constant.
+      CommonValue = Incoming;
+    } else if (Incoming != CommonValue) {
+      // There can be only one non-constant common value.
+      return false;
+    }
+  }
+
+  if (!CommonValue || IncomingConstants.empty())
+    return false;
+
+  // The common value must be valid in all incoming blocks.
+  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
+    if (!SQ.DT->dominates(CommonInst, P))
+      return false;
+
+  // We have a phi with exactly 1 variable incoming value and 1 or more constant
+  // incoming values. See if all constant incoming values can be mapped back to
+  // the same incoming variable value.
+  BasicBlock *ToBB = P->getParent();
+  for (auto &IncomingConstant : IncomingConstants) {
+    Constant *C = IncomingConstant.first;
+    BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
+    if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
+      return false;
+  }
+
+  // All constant incoming values map to the same variable along the incoming
+  // edges of the phi. The phi is unnecessary.
+  P->replaceAllUsesWith(CommonValue);
+  P->eraseFromParent();
+  ++NumPhiCommon;
+  return true;
+}
+
 static bool processPHI(PHINode *P, LazyValueInfo *LVI,
                        const SimplifyQuery &SQ) {
   bool Changed = false;
 
   BasicBlock *BB = P->getParent();
   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
     Value *Incoming = P->getIncomingValue(i);
     if (isa<Constant>(Incoming)) continue;
static bool processPHI(PHINode *P, LazyValueInfo *LVI,
   }
 
   if (Value *V = SimplifyInstruction(P, SQ)) {
     P->replaceAllUsesWith(V);
     P->eraseFromParent();
     Changed = true;
   }
 
+  if (!Changed)
+    Changed = simplifyCommonValuePhi(P, LVI, SQ);
+
   if (Changed)
     ++NumPhis;
 
   return Changed;
 }
 
 static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) {
   Value *Pointer = nullptr;

test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+define i8* @simplify_phi_common_value_op0(i8* %ptr, i32* %b) {
+; CHECK-LABEL: @simplify_phi_common_value_op0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ISNULL:%.*]] = icmp eq i8* [[PTR:%.*]], null
+; CHECK-NEXT:    br i1 [[ISNULL]], label [[RETURN:%.*]], label [[ELSE:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    [[LB:%.*]] = load i32, i32* [[B:%.*]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[LB]], 1
+; CHECK-NEXT:    store i32 [[ADD]], i32* [[B]]
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i8* [[PTR]]
+;
+entry:
+  %isnull = icmp eq i8* %ptr, null
+  br i1 %isnull, label %return, label %else
+
+else:
+  %lb = load i32, i32* %b
+  %add = add nsw i32 %lb, 1
+  store i32 %add, i32* %b
+  br label %return
+
+return:
+  %r = phi i8* [ %ptr, %else ], [ null, %entry ]
+  ret i8* %r
+}
+
+define i8* @simplify_phi_common_value_op1(i8* %ptr, i32* %b) {
+; CHECK-LABEL: @simplify_phi_common_value_op1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ISNULL:%.*]] = icmp eq i8* [[PTR:%.*]], null
+; CHECK-NEXT:    br i1 [[ISNULL]], label [[RETURN:%.*]], label [[ELSE:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    [[LB:%.*]] = load i32, i32* [[B:%.*]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LB]], 1
+; CHECK-NEXT:    store i32 [[ADD]], i32* [[B]]
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i8* [[PTR]]
+;
+entry:
+  %isnull = icmp eq i8* %ptr, null
+  br i1 %isnull, label %return, label %else
+
+else:
+  %lb = load i32, i32* %b
+  %add = add i32 %lb, 1
+  store i32 %add, i32* %b
+  br label %return
+
+return:
+  %r = phi i8* [ null, %entry], [ %ptr, %else ]
+  ret i8* %r
+}
+
+define i8 @simplify_phi_multiple_constants(i8 %x, i32* %b) {
+; CHECK-LABEL: @simplify_phi_multiple_constants(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[IS0:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[IS0]], label [[RETURN:%.*]], label [[ELSE1:%.*]]
+; CHECK:       else1:
+; CHECK-NEXT:    [[IS42:%.*]] = icmp eq i8 [[X]], 42
+; CHECK-NEXT:    br i1 [[IS42]], label [[RETURN]], label [[ELSE2:%.*]]
+; CHECK:       else2:
+; CHECK-NEXT:    [[LB:%.*]] = load i32, i32* [[B:%.*]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LB]], 1
+; CHECK-NEXT:    store i32 [[ADD]], i32* [[B]]
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i8 [[X]]
+;
+entry:
+  %is0 = icmp eq i8 %x, 0
+  br i1 %is0, label %return, label %else1
+
+else1:
+  %is42 = icmp eq i8 %x, 42
+  br i1 %is42, label %return, label %else2
+
+else2:
+  %lb = load i32, i32* %b
+  %add = add i32 %lb, 1
+  store i32 %add, i32* %b
+  br label %return
+
+return:
+  %r = phi i8 [ 0, %entry], [ %x, %else2 ], [ 42, %else1 ]
+  ret i8 %r
+}
+