[InstCombinePHI] Partial simplification of identity operations.

Consider this code:

BB:
  %i = phi i32 [ 0, %if.then ], [ %c, %if.else ]
  %add = add nsw i32 %i, %b
  ...

In this common case the add can be moved to the %if.else basic block, because
adding zero is an identity operation. If we go though %if.then branch it's
always a win, because add is not executed; if not, the number of instructions
stays the same.

This pattern applies also to other instructions like sub, shl, shr, ashr | 0,
mul, sdiv, div | 1.

Patch by Jakub Kuderski!

llvm-svn: 244887

2 files changed, 238 insertions, 1 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
index 460f6eb6a82..71ac8aa6894 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
@@ -781,6 +781,106 @@ Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
   return ReplaceInstUsesWith(FirstPhi, Undef);
 }
 
+// If a PHI node has two edges and the PHI node is used in instructions like
+// add, sub, mul, div, shifts; if one of incoming values is a constant
+// that makes the instruction and identity operation, we can hoist this
+// instruction into one of the basic blocks.
+// Because of such a transformation, the identity operation won't be
+// executed, since it doesn't contribute to the result.
+//
+static Instruction *PartiallySimplifyIdentityOps(PHINode &PN, const Constant &C,
+                                                 Value &IncomingVal,
+                                                 Instruction &PNUser,
+                                                 InstCombiner &IC) {
+  if (!PNUser.isBinaryOp())
+    return nullptr;
+  if (PN.getParent() != PNUser.getParent())
+    return nullptr;
+
+  //       C                  IncomingVal
+  //        \                     /
+  //         \  0             1  / -- (IncomingValIdx)
+  //          \                 /
+  // PN = phi [C , ...] [ IncomingVal, BB ]
+  // ...
+  //              0  1 -- (OpOperandIdx)
+  // PNUser = op PN, x
+  const unsigned IncomingValIdx =
+      (&IncomingVal == PN.getIncomingValue(0)) ? 0 : 1;
+  const unsigned OpOperandIdx = (&PN == PNUser.getOperand(0)) ? 1 : 0;
+
+  // Exit if not an identity operation.
+  // For everything except add Add and Mul constant must be on the RHS.
+  switch (PNUser.getOpcode()) {
+  default:
+    return nullptr;
+  case Instruction::Add:
+    if (!C.isZeroValue())
+      return nullptr;
+    break;
+
+  case Instruction::Sub:
+  case Instruction::Shl:
+  case Instruction::LShr:
+  case Instruction::AShr:
+    if (!C.isZeroValue() || OpOperandIdx == 1)
+      return nullptr;
+    break;
+
+  case Instruction::Mul:
+    if (!C.isOneValue())
+      return nullptr;
+    break;
+
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+    if (!C.isOneValue() || OpOperandIdx == 1)
+      return nullptr;
+    break;
+  }
+
+  BasicBlock *BB = PN.getIncomingBlock(IncomingValIdx);
+  auto *Terminator = BB->getTerminator();
+
+  if (const auto *Incoming = dyn_cast<Instruction>(&IncomingVal))
+    if (!IC.getDominatorTree()->dominates(Incoming, Terminator))
+      return nullptr;
+
+  // Operand must be available in newly generated instruction and
+  // as an incoming value of the PHI node.
+  if (const auto *Operand =
+          dyn_cast<Instruction>(PNUser.getOperand(OpOperandIdx)))
+    if (!IC.getDominatorTree()->dominates(Operand, Terminator) ||
+        !IC.getDominatorTree()->dominates(Operand, &PN))
+      return nullptr;
+
+  // Ensure that the non-constant value in the PHI node doesn't come
+  // from the same BasicBlock as the PHI node. This prevents errors
+  // that could appear with loops (loop backedge could have this
+  // problem).
+  if (PN.getIncomingBlock(IncomingValIdx) == PN.getParent())
+    return nullptr;
+
+  Value *LHS = &IncomingVal, *RHS = PNUser.getOperand(OpOperandIdx);
+  if (OpOperandIdx == 0)
+    std::swap(LHS, RHS);
+
+  // Add new instruction to one of the edges.
+  IRBuilder<> Builder(Terminator);
+  auto *NewInst =
+      Builder.CreateBinOp(cast<BinaryOperator>(PNUser).getOpcode(), LHS, RHS);
+  cast<BinaryOperator>(NewInst)->copyIRFlags(&PNUser);
+
+  // The new incoming values are:
+  // - result of the newly emmited instruction
+  // - operand of the instruction
+  PN.setIncomingValue(IncomingValIdx, NewInst);
+  PN.setIncomingValue(IncomingValIdx == 0 ? 1 : 0,
+                      PNUser.getOperand(OpOperandIdx));
+  IC.ReplaceInstUsesWith(PNUser, &PN);
+  return &PN;
+}
+
 // PHINode simplification
 //
 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
@@ -822,6 +922,21 @@ Instruction *InstCombiner::visitPHINode(PHINode &PN) {
         PHIUser->user_back() == &PN) {
       return ReplaceInstUsesWith(PN, UndefValue::get(PN.getType()));
     }
+
+    // If this phi has one use, exactly 2 edges and one is a constant, we
+    // may be able to apply the PartiallySimplifyIdentityOps optimization.
+    if (PN.getNumIncomingValues() == 2) {
+      const Constant *C = dyn_cast<Constant>(PN.getIncomingValue(0));
+      Value *Val = PN.getIncomingValue(1);
+      if (!C) {
+        C = dyn_cast<Constant>(PN.getIncomingValue(1));
+        Val = PN.getIncomingValue(0);
+      }
+      if (C && !isa<Constant>(Val))
+        if (auto *I =
+                PartiallySimplifyIdentityOps(PN, *C, *Val, *PHIUser, *this))
+          return I;
+    }
   }
 
   // We sometimes end up with phi cycles that non-obviously end up being the
diff --git a/llvm/test/Transforms/InstCombine/phi.ll b/llvm/test/Transforms/InstCombine/phi.ll
index 54cc4cfe459..3026167000b 100644
--- a/llvm/test/Transforms/InstCombine/phi.ll
+++ b/llvm/test/Transforms/InstCombine/phi.ll
@@ -247,8 +247,9 @@ end:
   ret i64 %tmp2
 ; CHECK-LABEL: @test12(
 ; CHECK-NOT: zext
+; CHECK: %[[X:.*]] = add i64 %{{.*}}, %Val
 ; CHECK: end:
-; CHECK-NEXT: phi i64 [ 0, %entry ], [ %Val, %two ]
+; CHECK-NEXT: phi i64 [ %tmp41, %entry ], [ %[[X]], %two ]
 ; CHECK-NOT: phi
 ; CHECK: ret i64
 }
@@ -630,3 +631,124 @@ done:
   %y = phi i32 [ undef, %entry ]
   ret i32 %y
 }
+
+; CHECK-LABEL: @test28(
+; CHECK add nsw i32 %x, %dfd
+; CHECK: if.end:
+; CHECK-NEXT: phi i32 [ %{{.*}}, %if.else ], [ %x, %entry ]
+; CHECK-NEXT: ret
+define i32 @test28(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ %1, %if.else ], [ 0, %entry ]
+  %div = add nsw i32 %x, %v.addr.0
+  ret i32 %div
+}
+
+; CHECK-LABEL: @test29(
+; CHECK: ashr i32 %x, %1
+; CHECK: if.end:
+; CHECK-NEXT: phi i32 [ %{{.*}}, %if.else ], [ %x, %entry ]
+; CHECK-NEXT: ret
+define i32 @test29(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ %1, %if.else ], [ 0, %entry ]
+  %div = ashr i32 %x, %v.addr.0
+  ret i32 %div
+}
+
+; CHECK-LABEL: @test30(
+; CHECK: sdiv i32 %x, %1
+; CHECK: if.end:
+; CHECK-NEXT: phi i32 [ %{{.*}}, %if.else ], [ %x, %entry ]
+; CHECK-NEXT: ret
+define i32 @test30(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ %1, %if.else ], [ 1, %entry ]
+  %div = sdiv i32 %x, %v.addr.0
+  ret i32 %div
+}
+
+; CHECK-LABEL: @test31(
+; CHECK: mul i32
+; CHECK: if.end:
+; CHECK-NEXT: phi i32 [ %{{.*}}, %if.else ], [ %x, %entry ]
+; CHECK-NEXT: ret
+define i32 @test31(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ %1, %if.else ], [ 1, %entry ]
+  %div = mul i32 %x, %v.addr.0
+  ret i32 %div
+}
+
+; CHECK-LABEL: @test32(
+; CHECK: sdiv i32 %x, %1
+; CHECK: if.end:
+; CHECK-NEXT: phi i32 [ %x, %entry ], [ %{{.*}}, %if.else ]
+; CHECK-NEXT: ret
+define i32 @test32(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ 1, %entry ], [ %1, %if.else ]
+  %div = sdiv i32 %x, %v.addr.0
+  ret i32 %div
+}
+
+; Constant (0) is on the LHS of shift - should not aplpy the transformation
+; CHECK-LABEL: @test33(
+; CHECK: if.end:
+; CHECK-NEXT: %v.addr.0 = phi i32 [ 0, %entry ], [ %1, %if.else ]
+; CHECK-NEXT: shl
+; CHECK-NEXT: ret
+define i32 @test33(i1* nocapture readonly %cond, i32* nocapture readonly %a, i32 %x, i32 %v) {
+entry:
+  %0 = load volatile i1, i1* %cond, align 1
+  br i1 %0, label %if.else, label %if.end
+
+if.else:
+  %1 = load volatile i32, i32* %a, align 4
+  br label %if.end
+
+if.end:
+  %v.addr.0 = phi i32 [ 0, %entry ], [ %1, %if.else ]
+  %div = shl i32 %v.addr.0, %x
+  ret i32 %div
+}