[InstCombine] Simplify a known nonzero incoming value of PHI

[junbuml]

Summary

When a PHI is used only to be compared with zero, it is possible to replace an
incoming value with any non-zero constant if the incoming value can be proved as
a known nonzero value. For example, in below code, we can replace the incoming value %v with
any non-zero constant based on the fact that the PHI is only used to be compared with zero
and %v is a known non-zero value:

%v = select %cond, 1, 2
%p = phi [%v, BB] ...
%c = icmp eq, %p, 0

[sanjoy]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

Why do you care about VA having only one use?

941 ↗

(On Diff #45024)

Can't CtxI be the terminator of the i th incoming block?

[junbuml]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

In correctness perspective, we don't have to check VA->hasOneUse(), but I expected the real impact on performance only when the incoming value become a dead code from this modification. I'm okay with removing this check (VA->hasOneUse()) if we can expect any indirect benefit.

941 ↗

(On Diff #45024)

Not sure about this comment. Can you give me more detail about it ?

[mssimpso]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

I think keeping the one-use check makes sense. If we only expect there to be a benefit if VA becomes dead, we want to avoid increasing compile-time. The only corner case that I can think of is if all of VAs users are PHIs that are compared with zero.

[junbuml]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

The only corner case that I can think of is if all of VAs users are PHIs that are compared with zero.

This could a possible corner case, but to be simple for now, I may want to handle it as an extension if we need it.

[sanjoy]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

I appreciate that there is a compile time tradeoff here, but reducing
the number of users of VA can help if it changes VA to have only
one user left (there are optimizations in instcombine predicated on
instructions having only one use). In general, my opinion is that if
it does not hurt performance to do this transform for VA with
more than one user, then we should not bail out.

942 ↗

(On Diff #45024)

isKnownNonZero will try to prove the predicate for the location you
pass in as CtxI. You're passing in PN for CtxI, so currently
you won't optimize cases like:

  br (%x > 0), label %left, label %right

left:
  br label %merge  ;; == LOC

right:
  br label %merge

merge:
  %p = phi i32 [ %x, %left ], [ %y, %right ]
  %cmp = icmp eq i32 0, %p

The optimization won't trigger in this case because %x is not
provably non-zero at %p. However, %x is provably non-zero at
LOC, so passing in LOC for CtxI to isKnownNonZero should
return true.

[majnemer]

My gut reaction would be to ask why we aren't trying to fold the comparison across the PHI as that would catch this case (and others) quite naturally.

lib/Transforms/InstCombine/InstCombinePHI.cpp

19–20 ↗

(On Diff #45024)

Please sort these.

test/Transforms/InstCombine/phi.ll

763–764 ↗

(On Diff #45024)

This is not a sufficient test. Please make the test highlight the instruction which you have altered.

[junbuml]

Addressed comments from Sanjoy and David.

My gut reaction would be to ask why we aren't trying to fold the comparison across the PHI as that would catch this case (and others) quite naturally.

The main purpose of this change is not to fold the cmp, but to replace incoming values to a nonzero constant because for a phi with multiple non constant operands, only some of its operands could be a known nonzero. By replacing some of incoming values with constants, we can expect to make the incoming value dead as well as increase chances to fold users (e.g., the cmp) of the phi.

[junbuml]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45024)

Looks like FoldOpIntoPhi() also continue trying to fold when a PHI has one non-constant incoming value. So, I removed VA->hasOneUse() check here.

942 ↗

(On Diff #45024)

Thanks Sanjoy for the detail. Instead of PN, I pass the terminator of incoming block as CtxI.

test/Transforms/InstCombine/phi.ll

763–764 ↗

(On Diff #45024)

I added check for modified PHI.
Thanks David for the comment.

[junbuml]

Kindly ping ?

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

933 ↗

(On Diff #45317)

Please use auto * here.

935 ↗

(On Diff #45317)

CmpInst->isEquality() will return true if the comparison is ICMP_NE. Please add a testcase for this.

936–937 ↗

(On Diff #45317)

Please add using namespace llvm::PatternMatch; to this file so that you don't need to qualify m_Zero.

936–937 ↗

(On Diff #45317)

Instructions are canonicalized so that the RHS will have the constant. Please remove the code regarding the LHS.

[sanjoy]

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45317)

I think InBB will always be non-null and have a terminator in a valid CFG. Have you seen otherwise?

[junbuml]

Addressed David's comments.

lib/Transforms/InstCombine/InstCombinePHI.cpp

940 ↗

(On Diff #45317)

I haven't seen any null terminator in my environment. But, getTerminator() possibly returns nullptr. Since I cannot guarantee non-null terminator in all situations I'd rather keep the null check.

TerminatorInst *BasicBlock::getTerminator() {
  if (InstList.empty()) return nullptr;
  return dyn_cast<TerminatorInst>(&InstList.back());
}

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

941 ↗

(On Diff #45700)

It will only be null for BasicBlocks which are newly created. Your basic block will not be newly created, please remove the null check.

[junbuml]

lib/Transforms/InstCombine/InstCombinePHI.cpp

941 ↗

(On Diff #45700)

Thanks David. Removed the null check.

[junbuml]

ping ?

[junbuml]

Kindly ping

[hfinkel]

lib/Transforms/InstCombine/InstCombinePHI.cpp

941 ↗

(On Diff #45717)

You skip constants, why? And if there is a constant (aside from zero), should we not reuse it instead of creating a new one (1 in this case). We might end up materializing more constants this way.

[junbuml]

Addressed Hal's comments and added two more test cases to show that it reuse the existing non-zero constant.

[junbuml]

Minor renaming.

[sanjoy]

LGTM with minor nits inline.

lib/Transforms/InstCombine/InstCombinePHI.cpp

651 ↗

(On Diff #47321)

Use for (Value *V : PN.operands()) here.

652 ↗

(On Diff #47321)

Use auto *ConstVA here.

953 ↗

(On Diff #47321)

I'd just pass PN by reference here (and change GetAnyNonZeroConstInt to take PHINode &).

llvm/trunk/lib/Transforms/InstCombine/InstCombinePHI.cpp

 // This file implements the visitPHINode function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
+using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
 /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
 /// adds all have a single use, turn this into a phi and a single binop.
 Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
   assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
         return false;
     } else if (Op != NonPhiInVal)
       return false;
   }
 
   return true;
 }
 
+/// Return an existing non-zero constant if this phi node has, otherwise ruturn
+/// constant 1.
+static ConstantInt *GetAnyNonZeroConstInt(PHINode &PN) {
+  assert(isa<IntegerType>(PN.getType()) && "Expect only intger type phi");
+  for (Value *V : PN.operands())
+    if (auto *ConstVA = dyn_cast<ConstantInt>(V))
+      if (!ConstVA->isZeroValue())
+        return ConstVA;
+  return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
+}
 
 namespace {
 struct PHIUsageRecord {
   unsigned PHIId;     // The ID # of the PHI (something determinstic to sort on)
   unsigned Shift;     // The amount shifted.
   Instruction *Inst;  // The trunc instruction.
 
   PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
if (PN.hasOneUse()) {
     // common case here is good because the only other things that catch this
     // are induction variable analysis (sometimes) and ADCE, which is only run
     // late.
     if (PHIUser->hasOneUse() &&
         (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
         PHIUser->user_back() == &PN) {
       return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
     }
+    // When a PHI is used only to be compared with zero, it is safe to replace
+    // an incoming value proved as known nonzero with any non-zero constant.
+    // For example, in below code, the incoming value %v can be replaced with
+    // any non-zero constant based on the fact that the PHI is only used to be
+    // compared with zero and %v is a known non-zero value:
+    // %v = select %cond, 1, 2
+    // %p = phi [%v, BB] ...
+    //      icmp eq, %p, 0
+    auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
+    // FIXME: To be simple, handle only integer type for now.
+    if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
+        match(CmpInst->getOperand(1), m_Zero())) {
+      ConstantInt *NonZeroConst = nullptr;
+      for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
+        Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
+        Value *VA = PN.getIncomingValue(i);
+        if (isKnownNonZero(VA, DL, 0, AC, CtxI, DT)) {
+          if (!NonZeroConst)
+            NonZeroConst = GetAnyNonZeroConstInt(PN);
+          PN.setIncomingValue(i, NonZeroConst);
+        }
+      }
+    }
   }
 
   // We sometimes end up with phi cycles that non-obviously end up being the
   // same value, for example:
   //   z = some value; x = phi (y, z); y = phi (x, z)
   // where the phi nodes don't necessarily need to be in the same block.  Do a
   // quick check to see if the PHI node only contains a single non-phi value, if
   // so, scan to see if the phi cycle is actually equal to that value.

llvm/trunk/test/Transforms/InstCombine/phi.ll

if.end:                                           ; preds = %if.else, %if.then
   %x.0 = phi i32 [ 1, %if.then ], [ 2, %if.else ]
   %or = or i32 %x.0, %a
   %cmp1 = icmp eq i32 %or, 0
   ret i1 %cmp1
 }
 
 declare void @dummy()
 
+; CHECK-LABEL: @phi_knownnonzero_eq
+; CHECK-LABEL: if.then:
+; CHECK-NOT: select
+; CHECK-LABEL: if.end:
+; CHECK: phi i32 [ 1, %if.then ]
+define i1 @phi_knownnonzero_eq(i32 %n, i32 %s, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp slt  i32 %n, %s
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  %cmp = icmp eq i32 %n, %0
+  %1 = select i1 %cmp, i32 1, i32 2
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %1,  %if.then ], [ %n, %entry ]
+  %cmp1 = icmp eq i32 %a.0, 0
+  ret i1  %cmp1
+}
+
+; CHECK-LABEL: @phi_knownnonzero_ne
+; CHECK-LABEL: if.then:
+; CHECK-NOT: select
+; CHECK-LABEL: if.end:
+; CHECK: phi i32 [ 1, %if.then ]
+define i1 @phi_knownnonzero_ne(i32 %n, i32 %s, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp slt  i32 %n, %s
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  %cmp = icmp eq i32 %n, %0
+  %1 = select i1 %cmp, i32 1, i32 2
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %1,  %if.then ], [ %n, %entry ]
+  %cmp1 = icmp ne i32 %a.0, 0
+  ret i1  %cmp1
+}
+
+; CHECK-LABEL: @phi_knownnonzero_eq_2
+; CHECK-LABEL: if.then:
+; CHECK-NOT: select
+; CHECK-LABEL: if.end:
+; CHECK: phi i32 [ 2, %if.else ]
+define i1 @phi_knownnonzero_eq_2(i32 %n, i32 %s, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp slt  i32 %n, %s
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  %tobool2 = icmp slt  i32 %n, %s
+  br i1 %tobool2, label %if.else, label %if.end
+
+if.else:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  %cmp = icmp eq i32 %n, %0
+  %1 = select i1 %cmp, i32 1, i32 2
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %1,  %if.else], [ %n, %entry ], [2, %if.then]
+  %cmp1 = icmp eq i32 %a.0, 0
+  ret i1  %cmp1
+}
+
+; CHECK-LABEL: @phi_knownnonzero_ne_2
+; CHECK-LABEL: if.then:
+; CHECK-NOT: select
+; CHECK-LABEL: if.end:
+; CHECK: phi i32 [ 2, %if.else ]
+define i1 @phi_knownnonzero_ne_2(i32 %n, i32 %s, i32* nocapture readonly %P) {
+entry:
+  %tobool = icmp slt  i32 %n, %s
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  %tobool2 = icmp slt  i32 %n, %s
+  br i1 %tobool2, label %if.else, label %if.end
+
+if.else:                                          ; preds = %entry
+  %0 = load i32, i32* %P
+  %cmp = icmp eq i32 %n, %0
+  %1 = select i1 %cmp, i32 1, i32 2
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %a.0 = phi i32 [ %1,  %if.else], [ %n, %entry ], [2, %if.then]
+  %cmp1 = icmp ne i32 %a.0, 0
+  ret i1  %cmp1
+}