InstCombinePHI: Partial simplification of identity operations

[kuhar]

Summary

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, udiv | 1.

[jmolloy]

Hi Jakub,

Thanks for working on this! I've got a bunch of comments from this first round of review.

Cheers,

James

lib/Transforms/InstCombine/InstCombinePHI.cpp

785

"if *a* PHI node"

788

"we can hoist this instruction into only one of the incoming blocks"

The use of "hoist" is important, I think.

796

There are a lot of ternary operators (x ? y : z) going on in this function, and it's a bit difficult to assert that they're all correct.

What I'd like to see is some ascii-art of the situation, with each of the nodes having a name. Then variables refer to those names later, which means I don't get confused which node OpOperandIdx refers to!

C        V
  \      /
   Phi
X  |
 \  |
   Op

Something like that? ^

810

Remove braces and put break on its own line.

818

Same as line 809, and for the rest.

819

No parens () around the second expression.

839

You need to handle the case where dyn_cast returns nullptr here.

844

Same as line 838.

847

I think this second check is unnecessary. As the terminator leads to the block with the PHI in, any instruction that dominates the terminator must also dominate PN.

857

What is this doing? What situation can cause whatever this is checking against?

866

Better to use a cast<> rather than a C-style cast for PNUser.getOpcode(); that's safer:

auto *NewInst = Builder.CreateBinOp(cast<BinaryOperator>(PNUser).getOpcode(), LHS, RHS);
cast<BinaryOperator>(NewInst)->copyIRFlags(&PNUser);

[kuhar]

lib/Transforms/InstCombine/InstCombinePHI.cpp

839

If it returns null, we are fine and can continue (ex. value that is a function parameter).

844

saa

847

Well, sometimes it is necessary when things get little more tricky. Consider duff's device with the do-while inside a switch. You end up with such IR:

for.cond:                                         ; preds = %for.body, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %cmp = icmp eq i32 %i.0, 100
  br i1 %cmp, label %for.end, label %for.body

for.body:                                         ; preds = %for.cond
  %conv = trunc i32 %i.0 to i16
  %idxprom = sext i32 %i.0 to i64
  %arrayidx = getelementptr inbounds [100 x i16], [100 x i16]* %Array, i64 0, i64 %idxprom
  store i16 %conv, i16* %arrayidx, align 2
  %inc = add nsw i32 %i.0, 1
  br label %for.cond

for.end:                                          ; preds = %for.cond
  %arraydecay = getelementptr inbounds [100 x i16], [100 x i16]* %Array, i64 0, i64 0
  br label %sw.bb.10.i

do.body.i:                                        ; preds = %sw.bb.10.i
  %incdec.ptr.i = getelementptr inbounds i16, i16* %incdec.ptr29.i, i64 1
  %0 = load i16, i16* %incdec.ptr29.i, align 2
  %add2.i = add i16 %add32.i, %0
  %incdec.ptr5.i = getelementptr inbounds i16, i16* %incdec.ptr.i, i64 1
  %1 = load i16, i16* %incdec.ptr.i, align 2
  %add8.i = add i16 %add2.i, %1
  %2 = add i16 %add8.i, %4
  br label %sw.bb.10.i

sw.bb.10.i:                                       ; preds = %do.body.i, %for.end
  %3 = phi i16 [ %add8.i, %do.body.i ], [ 0, %for.end ]
  %from.addr.2.i = phi i16* [ %incdec.ptr5.i, %do.body.i ], [ %arraydecay, %for.end ]
  %n.2.i = phi i32 [ %dec.i, %do.body.i ], [ 17, %for.end ]
  %incdec.ptr11.i = getelementptr inbounds i16, i16* %from.addr.2.i, i64 1
  %4 = load i16, i16* %from.addr.2.i, align 2
  %add14.i = add i16 %3, %4
  %incdec.ptr17.i = getelementptr inbounds i16, i16* %incdec.ptr11.i, i64 1
  %5 = load i16, i16* %incdec.ptr11.i, align 2
  %add20.i = add i16 %add14.i, %5
  %incdec.ptr23.i = getelementptr inbounds i16, i16* %incdec.ptr17.i, i64 1
  %6 = load i16, i16* %incdec.ptr17.i, align 2
  %add26.i = add i16 %add20.i, %6
  %incdec.ptr29.i = getelementptr inbounds i16, i16* %incdec.ptr23.i, i64 1
  %7 = load i16, i16* %incdec.ptr23.i, align 2
  %add32.i = add i16 %add26.i, %7
  %dec.i = add nsw i32 %n.2.i, -1
  %cmp.i = icmp sgt i32 %n.2.i, 1
  br i1 %cmp.i, label %do.body.i, label %sum.exit

Here you want to replace
%3 = phi i16 [ %add8.i, %do.body.i ], [ 0, %for.end ]
%add14.i = add i16 %3, %4
with
%2 = add i16 %add8.i, %4 (in for.end)
%3 = phi i16 [ %2, %do.body.i ], [ %4, %for.end ]
Which is illegal (detected by the domination check of Operand and PN).

857

It's checking if the newly inserted instruction would dominate all of its uses. I'm checking against Terminator not to add the new instruction and remove it afterwards (equivalent).
The if (PN.getIncomingBlock(IncomingValIdx) == PN.getParent()) is essentially detecting some subset of illegal cases of the check in the for loop, but it's the most common one and can be detected without using dominator tree at all.

[jmolloy]

Hi Jakub,

Thanks for making those changes. I just have one more tranche of changes to request; they're all to do with the testcase.

Cheers,

James

lib/Transforms/InstCombine/InstCombinePHI.cpp

847

Okay, after chatting with Jakub offline, the simpler case here is a single-block loop where "Operand" is inside the loop. It'll dominate the teminator, but not the PHI node because it is between them.

test/Transforms/InstCombine/phi.ll

636

Your CHECKs here need to be more explicit. I don't think they're tight enough now to validate that the test does what it's supposed to.

You should check that the if.end block contains only a PHI and a ret:

// CHECK: if.end:
// CHECK-NEXT: phi [ %{{.*}}, %if.else ], [ %v.addr.0, %entry ]
// CHECK-NEXT: ret

655

Same for all the rest of these; be more specific.

[kuhar]

Thanks for the review, James.
Tests updated.

[jmolloy]

LGTM!

[• chatur01]

Landed r244887.

[majnemer]

This commit resulted in PR24470, I reverted r244887 in r245194. Please
take a look when you get the chance.

[kuhar]

Fixed bug reported as PR24470.

[kuhar]

Thanks for reporting the bug and for the minimalistic test, it should be fixed now.

[jmolloy]

For clarity, this review has been reopened due to code reversion and now requires David's sayso to proceed.

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

883–885

Please do not create instructions that you end up destroying once you realize that the transform isn't appropriate. Instead, perform an upfront check.

[kuhar]

Perform all checks before adding new instruction

[kuhar]

I've changed the check form using isSafeToSpeculativelyExecute to simply checking for division instruction - from all the cases I deal with only this one could result in trap.

[majnemer]

In D11648#227672, @kuhar wrote:

I've changed the check form using isSafeToSpeculativelyExecute to simply checking for division instruction - from all the cases I deal with only this one could result in trap.

Why is it OK to hoist if the incoming block unconditionally branches or ends in a switch or indirectbr?

[kuhar]

Don't perform the optimization if incoming edge's terminator is not a Branch Instruction.

[kuhar]

In D11648#227701, @majnemer wrote:

In D11648#227672, @kuhar wrote:

I've changed the check form using isSafeToSpeculativelyExecute to simply checking for division instruction - from all the cases I deal with only this one could result in trap.

Why is it OK to hoist if the incoming block unconditionally branches or ends in a switch or indirectbr?

It may be not, good catch. Thanks.

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

847–856

Why not just check if BB->getUniqueSuccessor() != nullptr?

[kuhar]

lib/Transforms/InstCombine/InstCombinePHI.cpp

847–856

Do you also suggest removing this check for UDiv/SDiv with conditional branch?

[kuhar]

lib/Transforms/InstCombine/InstCombinePHI.cpp

847–856

I can either continue checking if an instruction is a branch and make sure that if it's conditional branch hoisting operation won't potentially cause a trap (sdiv/udiv); or I can only apply the optimization to unconditional branches.

Currently I follow the first option, so I cast the instruction to BranchInst and then check if it's conditional. getUniqueSuccessor won't simplify anything here (I think).

[majnemer]

lib/Transforms/InstCombine/InstCombinePHI.cpp

851–856

I think the correct logic would be:

// We can only push the instruction to a predecessor if our predecessor is guaranteed to have a single, unique successor.
if (BB->getUniqueSuccessor() != PN.getParent())
  return nullptr;

It should always be safe to hoist the instruction so long as it is inserted before the terminator.

[kuhar]

ping

[kuhar]

ping

[kuhar]

Ping! David, do you have any further comments?

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"
 using namespace llvm;
 
 #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));
Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
   // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
   // with undefs.
   Value *Undef = UndefValue::get(FirstPhi.getType());
   for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
     ReplaceInstUsesWith(*PHIsToSlice[i], Undef);
   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 = cast<BinaryOperator>(
+      Builder.CreateBinOp(cast<BinaryOperator>(PNUser).getOpcode(), LHS, RHS));
+  NewInst->copyIRFlags(&PNUser);
+
+  // Cannot hoist an operation if the incoming BasicBlock has conditional branch
+  // and when the new instruction could trigger undefined behaviour or other
+  // side effects. 
+  if (const auto *BI = dyn_cast<BranchInst>(Terminator))
+    if (BI->isConditional() &&
+        !isSafeToSpeculativelyExecute(NewInst, NewInst, IC.getDominatorTree(),
+                                      IC.getTargetLibraryInfo())) {
+      NewInst->eraseFromParent();
+      return nullptr;
+    }
+
+  // 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) {
   if (Value *V = SimplifyInstruction(&PN, DL, TLI, DT, AC))
     return ReplaceInstUsesWith(PN, V);
 
   // If all PHI operands are the same operation, pull them through the PHI,
   // reducing code size.
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()));
     }
+
+    // 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
   // 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.

test/Transforms/InstCombine/phi.ll

end:
   %tmp32 = trunc i128 %tmp869.0 to i64            ; <i64> [#uses=1]
   %tmp29 = lshr i128 %tmp869.0, 64                ; <i128> [#uses=1]
   %tmp30 = trunc i128 %tmp29 to i64               ; <i64> [#uses=1]
 
   %tmp2 = add i64 %tmp32, %tmp30
   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
 }
 
 declare void @test13f(double, i32)
 
 define void @test13(i1 %cond, i32 %V1, double %Vald) {
 entry:

 ; CHECK: ret i32 undef
 define i32 @test27(i1 %b) {
 entry:
   br label %done
 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
+}
+
+; SDiv %div2 is not always executed - shouldn't hoist it into incoming block cond.false
+; CHECK-LABEL: @test34(
+; CHECK: cond.true:
+; CHECK-NEXT: %cond10 = phi i32 [ %div, %cond.false ], [ 1, %entry ]
+; CHECK-NEXT: %div2 = sdiv i32 %.pre, %cond10
+; CHECK-NEXT: br label %cond.end
+define i32 @test34(i1* nocapture readonly %cond, i1* nocapture readonly %cond2,
+                   i32* nocapture readonly %a, i32* nocapture readonly %b, i32* nocapture %c) {
+entry:
+  %0 = load volatile i32, i32* %a, align 4
+  %tobool = icmp eq i32 %0, 0
+  %.pre = load volatile i32, i32* %a, align 4
+  br i1 %tobool, label %cond.true, label %cond.false
+
+cond.false:
+  %div = sdiv i32 %.pre, %0
+  %tobool1 = icmp eq i32 %div, 0
+  br i1 %tobool1, label %cond.end, label %cond.true
+
+cond.true:
+  %cond10 = phi i32 [ %div, %cond.false ], [ 1, %entry ]
+  %div2 = sdiv i32 %.pre, %cond10
+  br label %cond.end
+
+cond.end:
+  %cond6 = phi i32 [ %div2, %cond.true ], [ 0, %cond.false ]
+  store volatile i32 %cond6, i32* %c, align 4
+  ret i32 0
+}
+