InstCombine: Don't rewrite phi-of-bitcast when the phi has other users

[cwabbott]

Summary

Judging by the existing comments, this was the intention, but the
transform never actually checked if the existing phi's would be removed.
See https://bugs.llvm.org/show_bug.cgi?id=44242 for an example where
this causes much worse code generation on AMDGPU.

[spatel]

I'm not sure if these patches conflict, but D71164 is also trying to fix a bug in this code.

[lebedev.ri]

I agree that we shouldn't be increasing instruction count, especially PHI count.

llvm/test/Transforms/InstCombine/pr44242.ll

1

Please autogenerate and precommit tests.

[cwabbott]

llvm/test/Transforms/InstCombine/pr44242.ll

1

Sorry, but what exactly do you mean?

[nikic]

Change looks fine to me. I'd suggest to add test coverage for a few more of the cases you check. In particular, right now you only cover the case where the outer phi has extra uses, but not the case where an inner phi has them.

llvm/test/Transforms/InstCombine/pr44242.ll

1

You can use utils/update_test_checks.py to generate the expected output. Then you should first commit just the test (with generated output without your patch). The patch will then only show the IR diff in the test, making is clearer what actually changed.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

I think we should be doing those checks here.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

The OldPhiNodes.count(PHI) == 0 part of the check wouldn't work correctly at this points -- it needs all PHIs to be collected first.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

Right. But the rest can be done here, no?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

While it could be done, I don't think there'd be much benefit. We'd have to iterate all the users a second time just to check the phi nodes. The current implementation is also nicely symmetric between the checking loop (added in this patch) and the replacement loop (preexisting), and I think it's worth keeping that symmetry.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

I don't have a strong opinion *here*, but in general the earlier we error-out
the less pointless work that was in vain (read: compile-time cost) we waste.

[cwabbott]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2203

I'd agree with @nikic here that this sounds like a premature optimization. It would split up the two parts which must be in sync into three, and break the symmetry between them, making it even harder to verify that the already-complex transform is correct, all for a theoretical performance benefit. I can do it if you require it, but otherwise I'd rather not.

[foad]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

2300–2307

In a Release build I get "warning: unused variable" for TyA and TyB.

[cwabbott]

• Update precommitted test in this commit.
• Make the test match the original bug better. It turns out that in my attempt to make it harder for other transforms to happen beforehand and break the test, I accidentally made another transform kick in which broke it anyways. Use this form with a loop which should hopefully defeat other optimizations better.

[cwabbott]

Add diff for new test.

[cwabbott]

Suppress unused variable warnings in release builds.

[cwabbott]

llvm/test/Transforms/InstCombine/pr44242.ll

1

Hopefully I did that right.

[nikic]

LGTM, thanks for adding the extra test coverage.

[nikic]

Do you plan to land this soon?

[cwabbott]

I just asked earlier this week to get my commit rights back, but I haven't heard back right away, so you can commit it if I don't get it first.

[mareko]

Would somebody please push this?

[mareko]

@nhaehnle

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

for (Value *IncValue : OldPN->incoming_values()) {
           continue;
         // If a LoadInst has more than one use, changing the type of loaded
         // value may create another bitcast.
         return nullptr;
       }
 
       if (auto *PNode = dyn_cast<PHINode>(IncValue)) {
         if (OldPhiNodes.insert(PNode))
           PhiWorklist.push_back(PNode);
         continue;
       }
 
       auto *BCI = dyn_cast<BitCastInst>(IncValue);
       // We can't handle other instructions.
       if (!BCI)
         return nullptr;
 
       // Verify it's a A->B cast.
       Type *TyA = BCI->getOperand(0)->getType();
       Type *TyB = BCI->getType();
       if (TyA != DestTy || TyB != SrcTy)
         return nullptr;
     }
   }
 
+  // Check that each user of each old PHI node is something that we can
+  // rewrite, so that all of the old PHI nodes can be cleaned up afterwards.
+  for (auto *OldPN : OldPhiNodes) {
+    for (User *V : OldPN->users()) {
+      if (auto *SI = dyn_cast<StoreInst>(V)) {
+        if (!SI->isSimple() || SI->getOperand(0) != OldPN)
+          return nullptr;
+      } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
+        // Verify it's a B->A cast.
+        Type *TyB = BCI->getOperand(0)->getType();
+        Type *TyA = BCI->getType();
+        if (TyA != DestTy || TyB != SrcTy)
+          return nullptr;
+      } else if (auto *PHI = dyn_cast<PHINode>(V)) {
+        // As long as the user is another old PHI node, then even if we don't
+        // rewrite it, the PHI web we're considering won't have any users
+        // outside itself, so it'll be dead.
+        if (OldPhiNodes.count(PHI) == 0)
+          return nullptr;
+      } else {
+        return nullptr;
+      }
+    }
+  }
+
   // For each old PHI node, create a corresponding new PHI node with a type A.
   SmallDenseMap<PHINode *, PHINode *> NewPNodes;
   for (auto *OldPN : OldPhiNodes) {
     Builder.SetInsertPoint(OldPN);
     PHINode *NewPN = Builder.CreatePHI(DestTy, OldPN->getNumOperands());
     NewPNodes[OldPN] = NewPN;
   }
 
Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) {
 
   // Replace users of BitCast B->A with NewPHI. These will help
   // later to get rid off a closure formed by OldPHI nodes.
   Instruction *RetVal = nullptr;
   for (auto *OldPN : OldPhiNodes) {
     PHINode *NewPN = NewPNodes[OldPN];
     for (User *V : OldPN->users()) {
       if (auto *SI = dyn_cast<StoreInst>(V)) {
-        if (SI->isSimple() && SI->getOperand(0) == OldPN) {
-          Builder.SetInsertPoint(SI);
-          auto *NewBC =
-            cast<BitCastInst>(Builder.CreateBitCast(NewPN, SrcTy));
-          SI->setOperand(0, NewBC);
-          Worklist.Add(SI);
-          assert(hasStoreUsersOnly(*NewBC));
-        }
-      }
+        assert(SI->isSimple() && SI->getOperand(0) == OldPN);
       else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
-        // Verify it's a B->A cast.
         Type *TyB = BCI->getOperand(0)->getType();
         Type *TyA = BCI->getType();
-        if (TyA == DestTy && TyB == SrcTy) {
-          Instruction *I = replaceInstUsesWith(*BCI, NewPN);
-          if (BCI == &CI)
-            RetVal = I;
-        }
+        assert(TyA == DestTy && TyB == SrcTy);
+      } else if (auto *PHI = dyn_cast<PHINode>(V)) {
+        assert(OldPhiNodes.count(PHI) > 0);
+      } else {
+        llvm_unreachable("all uses should be handled");
       }
     }
   }
 
   return RetVal;
 }
 
 Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {

llvm/test/Transforms/InstCombine/pr44242.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 ; Check that we don't create two redundant phi nodes when %val is used in a
 ; form where we can't rewrite it in terms of the new phi node.
 
 ; Use %val in an instruction type not supported by optimizeBitCastFromPhi.
 define float @sitofp(float %x) {
 ; CHECK-LABEL: @sitofp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop_header:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[VAL_INCR:%.*]], [[LOOP:%.*]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = phi float [ 0.000000e+00, [[ENTRY]] ], [ [[PHITMP:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[VAL_INCR_CASTED:%.*]], [[LOOP:%.*]] ]
+; CHECK-NEXT:    [[VAL_CASTED:%.*]] = bitcast i32 [[VAL]] to float
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[VAL_CASTED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[LOOP]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[VAL_INCR]] = fadd float [[TMP0]], 1.000000e+00
-; CHECK-NEXT:    [[VAL_INCR_CASTED:%.*]] = bitcast float [[VAL_INCR]] to i32
-; CHECK-NEXT:    [[PHITMP]] = sitofp i32 [[VAL_INCR_CASTED]] to float
+; CHECK-NEXT:    [[VAL_INCR:%.*]] = fadd float [[VAL_CASTED]], 1.000000e+00
+; CHECK-NEXT:    [[VAL_INCR_CASTED]] = bitcast float [[VAL_INCR]] to i32
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret float [[VAL]]
+; CHECK-NEXT:    [[RESULT:%.*]] = sitofp i32 [[VAL]] to float
+; CHECK-NEXT:    ret float [[RESULT]]
 ;
 entry:
   br label %loop_header
 loop_header:
   %val = phi i32 [ 0, %entry ], [ %val_incr_casted, %loop ]
   %val_casted = bitcast i32 %val to float
   %cmp = fcmp ogt float %val_casted, %x
   br i1 %cmp, label %end, label %loop
 loop:
   %val_incr = fadd float %val_casted, 1.0
   %val_incr_casted = bitcast float %val_incr to i32
   br label %loop_header
 end:
   %result = sitofp i32 %val to float
   ret float %result
 }
 
 ; Use %val in an incompatible bitcast.
 define <2 x i16> @bitcast(float %x) {
 ; CHECK-LABEL: @bitcast(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop_header:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[VAL_INCR:%.*]], [[LOOP:%.*]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = phi <2 x i16> [ zeroinitializer, [[ENTRY]] ], [ [[PHITMP:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[VAL_INCR_CASTED:%.*]], [[LOOP:%.*]] ]
+; CHECK-NEXT:    [[VAL_CASTED:%.*]] = bitcast i32 [[VAL]] to float
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[VAL_CASTED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[LOOP]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[VAL_INCR]] = fadd float [[TMP0]], 1.000000e+00
-; CHECK-NEXT:    [[PHITMP]] = bitcast float [[VAL_INCR]] to <2 x i16>
+; CHECK-NEXT:    [[VAL_INCR:%.*]] = fadd float [[VAL_CASTED]], 1.000000e+00
+; CHECK-NEXT:    [[VAL_INCR_CASTED]] = bitcast float [[VAL_INCR]] to i32
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret <2 x i16> [[VAL]]
+; CHECK-NEXT:    [[RESULT:%.*]] = bitcast i32 [[VAL]] to <2 x i16>
+; CHECK-NEXT:    ret <2 x i16> [[RESULT]]
 ;
 entry:
   br label %loop_header
 loop_header:
   %val = phi i32 [ 0, %entry ], [ %val_incr_casted, %loop ]
   %val_casted = bitcast i32 %val to float
   %cmp = fcmp ogt float %val_casted, %x
   br i1 %cmp, label %end, label %loop

 @global = global i32 0
 
 ; Use %val with a volatile store.
 define void @store_volatile(float %x) {
 ; CHECK-LABEL: @store_volatile(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop_header:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[VAL_INCR:%.*]], [[LOOP:%.*]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[VAL_INCR_CASTED:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[VAL_INCR_CASTED:%.*]], [[LOOP:%.*]] ]
+; CHECK-NEXT:    [[VAL_CASTED:%.*]] = bitcast i32 [[VAL]] to float
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[VAL_CASTED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[LOOP]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[VAL_INCR]] = fadd float [[TMP0]], 1.000000e+00
+; CHECK-NEXT:    [[VAL_INCR:%.*]] = fadd float [[VAL_CASTED]], 1.000000e+00
 ; CHECK-NEXT:    [[VAL_INCR_CASTED]] = bitcast float [[VAL_INCR]] to i32
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       end:
 ; CHECK-NEXT:    store volatile i32 [[VAL]], i32* @global, align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop_header

 }
 
 ; Use %val with a store where it's actually the address.
 define void @store_address(i32 %x) {
 ; CHECK-LABEL: @store_address(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop_header:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi float* [ bitcast (i32* @global to float*), [[ENTRY:%.*]] ], [ [[VAL_INCR:%.*]], [[LOOP:%.*]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = phi i32* [ @global, [[ENTRY]] ], [ [[VAL_INCR_CASTED:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[VAL:%.*]] = phi i32* [ @global, [[ENTRY:%.*]] ], [ [[VAL_INCR1:%.*]], [[LOOP:%.*]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[LOOP]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[VAL_INCR]] = getelementptr float, float* [[TMP0]], i64 1
-; CHECK-NEXT:    [[VAL_INCR_CASTED]] = bitcast float* [[VAL_INCR]] to i32*
+; CHECK-NEXT:    [[VAL_INCR1]] = getelementptr i32, i32* [[VAL]], i64 1
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       end:
 ; CHECK-NEXT:    store i32 0, i32* [[VAL]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop_header
 loop_header:

 
 ; Test where a phi (%val2) other than the original one (%val) has an
 ; incompatible use.
 define i32 @multiple_phis(float %x) {
 ; CHECK-LABEL: @multiple_phis(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop_header:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[TMP1:%.*]], [[LOOP_END:%.*]] ]
-; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[VAL2:%.*]], [[LOOP_END]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[VAL2:%.*]], [[LOOP_END:%.*]] ]
+; CHECK-NEXT:    [[VAL_CASTED:%.*]] = bitcast i32 [[VAL]] to float
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[VAL_CASTED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[END:%.*]], label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ogt float [[TMP0]], 2.000000e+00
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ogt float [[VAL_CASTED]], 2.000000e+00
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[IF:%.*]], label [[LOOP_END]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[VAL_INCR:%.*]] = fadd float [[TMP0]], 1.000000e+00
+; CHECK-NEXT:    [[VAL_INCR:%.*]] = fadd float [[VAL_CASTED]], 1.000000e+00
 ; CHECK-NEXT:    [[VAL_INCR_CASTED:%.*]] = bitcast float [[VAL_INCR]] to i32
 ; CHECK-NEXT:    br label [[LOOP_END]]
 ; CHECK:       loop_end:
-; CHECK-NEXT:    [[TMP1]] = phi float [ [[TMP0]], [[LOOP]] ], [ [[VAL_INCR]], [[IF]] ]
 ; CHECK-NEXT:    [[VAL2]] = phi i32 [ [[VAL]], [[LOOP]] ], [ [[VAL_INCR_CASTED]], [[IF]] ]
 ; CHECK-NEXT:    store volatile i32 [[VAL2]], i32* @global, align 4
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret i32 [[VAL]]
 ;
 entry:
   br label %loop_header