[InstCombine] Try to resubmit the combine of A->B->A BitCast and fix for pr27996

[Carrot]

Summary

The original patch of the A->B->A BitCast optimization was reverted by r274094 because it may cause infinite loop inside compiler https://llvm.org/bugs/show_bug.cgi?id=27996.

The problem is with following code

xB = load (type B);
xA = load (type A);
+yA = (A)xB; B -> A
+zAn = PHI[yA, xA]; PHI
+zBn = (B)zAn; // A -> B
store zAn;
store zBn;

optimizeBitCastFromPhi generates

+zBn = (B)zAn; // A -> B

and expects it will be combined with the following store instruction to another

store zAn

Unfortunately before combineStoreToValueType is called on the store instruction, optimizeBitCastFromPhi is called on the new BitCast again, and this pattern repeats indefinitely.

optimizeBitCastFromPhi only generates BitCast for load/store instructions, and BitCast with load/store instructions can easily be handled by InstCombineLoadStoreAlloca.cpp. So the solution to the problem is if all users of a CI are load/store instructions, we should not do optimizeBitCastFromPhi on it. Then optimizeBitCastFromPhi will not be called on the new BitCast instructions.

[Carrot]

ping

[Carrot]

ping

[evstupac]

Hi,

InstCombine is supposed to run to fix-point

Have you addressed David's comment?

Am I right that current fix-point is when all CI users are memory instructions?

Thanks,
Evgeny

lib/Transforms/InstCombine/InstCombineCasts.cpp

1806 ↗

(On Diff #69303)

To follow one stile you I'd put LI definition into comparison.

[Carrot]

In D23896#537933, @evstupac wrote:

Hi,

InstCombine is supposed to run to fix-point

Have you addressed David's comment?

Am I right that current fix-point is when all CI users are memory instructions?

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions, and now it will not work on BitCast used by MemOp only, so it will never work on the BitCast generated by itself.

[evstupac]

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions,

In the code I see Constants as well.
It would be nice to have more comments at return explaining why this is a fix point.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1860 ↗

(On Diff #69303)

New BitCast instruction is created if one of OldPN operands is Load, right?

L = Load
X = Phi [L, ...]

To:

L = Load
NewL = BitCast (L)
NewX = Phi [NewL, ...]

The new BitCast instruction user is PHI, not Load or Store.
Will it pass your fix point?

[Carrot]

In D23896#540377, @evstupac wrote:

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions,

In the code I see Constants as well.

I expect the BitCasted Constant will be returned by instruction builder directly.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1860 ↗

(On Diff #69303)

This function is called on the following pattern

p = Phi [...]
b =BitCast(p)

The BitCast of Load is not a candidate of this optimization.

[evstupac]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1768 ↗

(On Diff #69303)

Here you check that for
b = BitCast(p)
All Users are
"st b", "st to address b" or "ld from address b"
I don't see how your transformation can create BitCast for "load form b".

[Carrot]

Change the hasMemOpUsersOnly to hasStoreUsersOnly.

[Carrot]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1768 ↗

(On Diff #69303)

You are right. And BitCast used by Load is not handled by InstCombineLoadStoreAlloca.cpp.

[evstupac]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1768 ↗

(On Diff #71713)

Ok.
You are generating BitCast only for 1 store operand:
SI->setOperand(0, Builder->CreateBitCast(NewPNodes[PN], SrcTy));

Here you are exiting if BitCast goes to one of store operand (0 or 1). What is the reason?

1879 ↗

(On Diff #71713)

Could you please insert an assert on newly Created BitCast (to be sure we'll not hit it on next iteration)?

[Carrot]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1768 ↗

(On Diff #71713)

Because the following case

bitcast oldval to val
store val, addr

can be handled by InstCombineLoadStoreAlloca.cpp, and transformed to

bitcast addr to addr_with_diff_type
store oldval, addr_with_diff_type

This is the form you have question. It can be further transformed to

store oldval, (bitcast addr to addr_with_diff_type)

This is an optimized result.

[Carrot]

ping

[majnemer]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1765 ↗

(On Diff #72727)

"Store" should probably be "StoreInsts".

1767–1771 ↗

(On Diff #72727)

I think this can be simplified to llvm::all_of(CI.users(), [](User *U) { return isa<StoreInst>(U); });

1878 ↗

(On Diff #72727)

This looks unidiomatic. I'd cast<BitCastInst> the result of CreateBitCast. CreateBitCast cannot be a Constant because its operand is a PHINode.

[Carrot]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1767–1771 ↗

(On Diff #72727)

It is also used by following assert statement, so it's better to just leave it here.

[majnemer]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1896 ↗

(On Diff #75609)

I'd hoist this cast<BitCastInst> over to the call to Builder->CreateBitCast

[majnemer]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1873 ↗

(On Diff #75653)

It'd be more obvious why you don't need to mess with the builder insertion point if you used ConstantExpr::getBitCast instead.

1875–1876 ↗

(On Diff #75653)

I think this would do the wrong thing if the incoming block was an EH pad. Could we insert the bitcast after LI?

1893–1894 ↗

(On Diff #75653)

auto *, also please clang-format this line.

[majnemer]

LGTM

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

 //===- InstCombineCasts.cpp -----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visit functions for cast operations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
 
   unsigned NumElts = ExtElt->getVectorOperandType()->getNumElements();
   auto *NewVecType = VectorType::get(DestType, NumElts);
   auto *NewBC = IC.Builder->CreateBitCast(ExtElt->getVectorOperand(),
                                           NewVecType, "bc");
   return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand());
 }
 
+/// Check if all users of CI are StoreInsts.
+static bool hasStoreUsersOnly(CastInst &CI) {
+  for (User *U : CI.users()) {
+    if (!isa<StoreInst>(U))
+      return false;
+  }
+  return true;
+}
+
+/// This function handles following case
+///
+///     A  ->  B    cast
+///     PHI
+///     B  ->  A    cast
+///
+/// All the related PHI nodes can be replaced by new PHI nodes with type A.
+/// The uses of \p CI can be changed to the new PHI node corresponding to \p PN.
+Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) {
+  // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp.
+  if (hasStoreUsersOnly(CI))
+    return nullptr;
+
+  Value *Src = CI.getOperand(0);
+  Type *SrcTy = Src->getType();         // Type B
+  Type *DestTy = CI.getType();          // Type A
+
+  SmallVector<PHINode *, 4> PhiWorklist;
+  SmallSetVector<PHINode *, 4> OldPhiNodes;
+
+  // Find all of the A->B casts and PHI nodes.
+  // We need to inpect all related PHI nodes, but PHIs can be cyclic, so
+  // OldPhiNodes is used to track all known PHI nodes, before adding a new
+  // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first.
+  PhiWorklist.push_back(PN);
+  OldPhiNodes.insert(PN);
+  while (!PhiWorklist.empty()) {
+    auto *OldPN = PhiWorklist.pop_back_val();
+    for (Value *IncValue : OldPN->incoming_values()) {
+      if (isa<Constant>(IncValue))
+        continue;
+
+      if (auto *LI = dyn_cast<LoadInst>(IncValue)) {
+        // If there is a sequence of one or more load instructions, each loaded
+        // value is used as address of later load instruction, bitcast is
+        // necessary to change the value type, don't optimize it. For
+        // simplicity we give up if the load address comes from another load.
+        Value *Addr = LI->getOperand(0);
+        if (Addr == &CI || isa<LoadInst>(Addr))
+          return nullptr;
+        if (LI->hasOneUse() && LI->isSimple())
+          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;
+    }
+  }
+
+  // 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;
+  }
+
+  // Fill in the operands of new PHI nodes.
+  for (auto *OldPN : OldPhiNodes) {
+    PHINode *NewPN = NewPNodes[OldPN];
+    for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) {
+      Value *V = OldPN->getOperand(j);
+      Value *NewV = nullptr;
+      if (auto *C = dyn_cast<Constant>(V)) {
+        NewV = ConstantExpr::getBitCast(C, DestTy);
+      } else if (auto *LI = dyn_cast<LoadInst>(V)) {
+        Builder->SetInsertPoint(LI->getNextNode());
+        NewV = Builder->CreateBitCast(LI, DestTy);
+        Worklist.Add(LI);
+      } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
+        NewV = BCI->getOperand(0);
+      } else if (auto *PrevPN = dyn_cast<PHINode>(V)) {
+        NewV = NewPNodes[PrevPN];
+      }
+      assert(NewV);
+      NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j));
+    }
+  }
+
+  // If there is a store with type B, change it to type A.
+  for (User *U : PN->users()) {
+    auto *SI = dyn_cast<StoreInst>(U);
+    if (SI && SI->isSimple() && SI->getOperand(0) == PN) {
+      Builder->SetInsertPoint(SI);
+      auto *NewBC =
+          cast<BitCastInst>(Builder->CreateBitCast(NewPNodes[PN], SrcTy));
+      SI->setOperand(0, NewBC);
+      Worklist.Add(SI);
+      assert(hasStoreUsersOnly(*NewBC));
+    }
+  }
+
+  return replaceInstUsesWith(CI, NewPNodes[PN]);
+}
+
 Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
   // If the operands are integer typed then apply the integer transforms,
   // otherwise just apply the common ones.
   Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType();
   Type *DestTy = CI.getType();
 
   // Get rid of casts from one type to the same type. These are useless and can
if (SVI->hasOneUse() && DestTy->isVectorTy() &&
         Value *RHS = Builder->CreateBitCast(SVI->getOperand(1), DestTy);
         // Return a new shuffle vector.  Use the same element ID's, as we
         // know the vector types match #elts.
         return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2));
       }
     }
   }
 
+  // Handle the A->B->A cast, and there is an intervening PHI node.
+  if (PHINode *PN = dyn_cast<PHINode>(Src))
+    if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
+      return I;
+
   if (Instruction *I = canonicalizeBitCastExtElt(CI, *this, DL))
     return I;
 
   if (SrcTy->isPointerTy())
     return commonPointerCastTransforms(CI);
   return commonCastTransforms(CI);
 }
 

llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS, Instruction &CxtI);
   bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction &CxtI);
   bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction &CxtI);
   bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction &CxtI);
   Value *EmitGEPOffset(User *GEP);
   Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
   Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
   Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
+  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
 
   /// Determine if a pair of casts can be replaced by a single cast.
   ///
   /// \param CI1 The first of a pair of casts.
   /// \param CI2 The second of a pair of casts.
   ///
   /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
   /// Instruction::CastOps value for a cast that can replace the pair, casting

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

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+%"struct.std::complex" = type { { float, float } }
+@dd = external global %"struct.std::complex", align 4
+@dd2 = external global %"struct.std::complex", align 4
+
+define void @_Z3fooi(i32 signext %n) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %ldd.sroa.0.0 = phi i32 [ 0, %entry ], [ %5, %for.body ]
+  %ldd.sroa.6.0 = phi i32 [ 0, %entry ], [ %7, %for.body ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %0 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd, i64 0, i32 0, i32 0), align 4
+  %1 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd, i64 0, i32 0, i32 1), align 4
+  %2 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd2, i64 0, i32 0, i32 0), align 4
+  %3 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd2, i64 0, i32 0, i32 1), align 4
+  %mul.i = fmul float %0, %2
+  %mul4.i = fmul float %1, %3
+  %sub.i = fsub float %mul.i, %mul4.i
+  %mul5.i = fmul float %1, %2
+  %mul6.i = fmul float %0, %3
+  %add.i4 = fadd float %mul5.i, %mul6.i
+  %4 = bitcast i32 %ldd.sroa.0.0 to float
+  %add.i = fadd float %sub.i, %4
+  %5 = bitcast float %add.i to i32
+  %6 = bitcast i32 %ldd.sroa.6.0 to float
+  %add4.i = fadd float %add.i4, %6
+  %7 = bitcast float %add4.i to i32
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  store i32 %ldd.sroa.0.0, i32* bitcast (%"struct.std::complex"* @dd to i32*), align 4
+  store i32 %ldd.sroa.6.0, i32* bitcast (float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd, i64 0, i32 0, i32 1) to i32*), align 4
+  ret void
+
+; CHECK: phi float
+; CHECK: store float
+; CHECK-NOT: bitcast
+}
+
+
+define void @multi_phi(i32 signext %n) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %ldd.sroa.0.0 = phi i32 [ 0, %entry ], [ %9, %odd.bb ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %odd.bb ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %0 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd, i64 0, i32 0, i32 0), align 4
+  %1 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd, i64 0, i32 0, i32 1), align 4
+  %2 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd2, i64 0, i32 0, i32 0), align 4
+  %3 = load float, float* getelementptr inbounds (%"struct.std::complex", %"struct.std::complex"* @dd2, i64 0, i32 0, i32 1), align 4
+  %mul.i = fmul float %0, %2
+  %mul4.i = fmul float %1, %3
+  %sub.i = fsub float %mul.i, %mul4.i
+  %4 = bitcast i32 %ldd.sroa.0.0 to float
+  %add.i = fadd float %sub.i, %4
+  %5 = bitcast float %add.i to i32
+  %inc = add nsw i32 %i.0, 1
+  %bit0 = and i32 %inc, 1
+  %even = icmp slt i32 %bit0, 1
+  br i1 %even, label %even.bb, label %odd.bb
+
+even.bb:
+  %6 = bitcast i32 %5 to float
+  %7 = fadd float %sub.i, %6
+  %8 = bitcast float %7 to i32
+  br label %odd.bb
+
+odd.bb:
+  %9 = phi i32 [ %5, %for.body ], [ %8, %even.bb ]
+  br label %for.cond
+
+for.end:
+  store i32 %ldd.sroa.0.0, i32* bitcast (%"struct.std::complex"* @dd to i32*), align 4
+  ret void
+
+; CHECK-LABEL: @multi_phi(
+; CHECK: phi float
+; CHECK: store float
+; CHECK-NOT: bitcast
+}

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

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define void @mem() {
+bb:
+  br label %bb6
+
+bb6:
+  %.0 = phi i8** [ undef, %bb ], [ %t2, %bb6 ]
+  %tmp = load i8*, i8** %.0, align 8
+  %bc = bitcast i8* %tmp to i8**
+  %t1 = load i8*, i8** %bc, align 8
+  %t2 = bitcast i8* %t1 to i8**
+  br label %bb6
+
+bb206:
+  ret void
+; CHECK: phi
+; CHECK: bitcast
+; CHECK: load
+}

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

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+
+@i = constant i32 1, align 4
+@f = constant float 0x3FF19999A0000000, align 4
+@cmp = common global i32 0, align 4
+@resf = common global float* null, align 8
+@resi = common global i32* null, align 8
+
+define i32 @foo() {
+entry:
+  br label %while.cond
+
+while.cond:
+  %res.0 = phi i32* [ null, %entry ], [ @i, %if.then ], [ bitcast (float* @f to i32*), %if.else ]
+  %0 = load i32, i32* @cmp, align 4
+  %shr = ashr i32 %0, 1
+  store i32 %shr, i32* @cmp, align 4
+  %tobool = icmp ne i32 %shr, 0
+  br i1 %tobool, label %while.body, label %while.end
+
+while.body:
+  %and = and i32 %shr, 1
+  %tobool1 = icmp ne i32 %and, 0
+  br i1 %tobool1, label %if.then, label %if.else
+
+if.then:
+  br label %while.cond
+
+if.else:
+  br label %while.cond
+
+while.end:
+  %1 = bitcast i32* %res.0 to float*
+  store float* %1, float** @resf, align 8
+  store i32* %res.0, i32** @resi, align 8
+  ret i32 0
+
+; CHECK-NOT: bitcast i32
+}
+