[InstCombine] Enhance cast-of-load->load-of-bitcast fold to handle multiple identical casts

[lebedev.ri]

Summary

Seen in real code, although not sure it's really impactful.
Currently the fold is limited to the case where there is a single use of load,
which is a cast, which generally makes sense. But if originally have
several identical casts in different BB's, and don't decide to hoist
them into some one BB, we won't CSE them, and the fold won't happen..

Instead, let's be smart, and let's simply natively handle the case
where all uses of load are identical casts.

[spatel]

This feels like we're pushing the limits of instcombine. What if we view this as a SimplifyCFG problem instead: for any no-op cast or other zero-cost instruction with operand defined in a different BB, hoist the cast up to its operand's BB because that helps CSE and instcombine?

[lebedev.ri]

Hm, why SimplifyCFG?
I'm aware that we (still) don't have specialized hoisting/sinking pass..

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

589

This should use replaceInstUsesWith().

[jfb]

Please add tests for volatile loads.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

561

This comment is pretty obvious, I'd rather not have it.

563

Same here.

571

This seems like a pre-existing bug: you should bail on volatile as well. For example, if user code does a volatile load of int32 and then casts to float, we should probably try to emit an integer load (even if that's not guaranteed by the language).

576

Does this bail on address space casts to different address spaces (when the value is a pointer)?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

I can do that, but could you point me to the appropriate langref wording?

576

/// This function determines if the CastInst does not require any bits to be
/// changed in order to effect the cast. Essentially, it identifies cases where
/// no code gen is necessary for the cast, hence the name no-op cast.  For
/// example, the following are all no-op casts:
/// # bitcast i32* %x to i8*
/// # bitcast <2 x i32> %x to <4 x i16>
/// # ptrtoint i32* %x to i32     ; on 32-bit plaforms only
/// Determine if the described cast is a no-op.
bool CastInst::isNoopCast(Instruction::CastOps Opcode,
                          Type *SrcTy,
                          Type *DestTy,
                          const DataLayout &DL) {
  switch (Opcode) {
    default: llvm_unreachable("Invalid CastOp");
    case Instruction::Trunc:
    case Instruction::ZExt:
    case Instruction::SExt:
    case Instruction::FPTrunc:
    case Instruction::FPExt:
    case Instruction::UIToFP:
    case Instruction::SIToFP:
    case Instruction::FPToUI:
    case Instruction::FPToSI:
    case Instruction::AddrSpaceCast:
      // TODO: Target informations may give a more accurate answer here.
      return false;
    case Instruction::BitCast:
      return true;  // BitCast never modifies bits.
    case Instruction::PtrToInt:
      return DL.getIntPtrType(SrcTy)->getScalarSizeInBits() ==
             DestTy->getScalarSizeInBits();
    case Instruction::IntToPtr:
      return DL.getIntPtrType(DestTy)->getScalarSizeInBits() ==
             SrcTy->getScalarSizeInBits();
  }
}

589

I suppose it would be good to eradicate usages of "wrong" spellings so we don't accidentally use the "deprecated" one.

[spatel]

In D75505#1903785, @lebedev.ri wrote:

Hm, why SimplifyCFG?
I'm aware that we (still) don't have specialized hoisting/sinking pass..

Time to change that? :)
I was just grepping around in SimplifyCFG and saw that it has hoisting transforms gated by instruction costs, so I thought maybe there's a way to squeeze this into the existing code, but I know that's a stretch too.

[lebedev.ri]

In D75505#1903908, @spatel wrote:

In D75505#1903785, @lebedev.ri wrote:

Hm, why SimplifyCFG?
I'm aware that we (still) don't have specialized hoisting/sinking pass..

Time to change that? :)

In principle - hell yeah :)

But i'm not sure i have clear understanding how that would look,
so for now i'd settle for either just not touching the pattern,
or doing this conservative instcombine-level change.

I was just grepping around in SimplifyCFG and saw that it has hoisting transforms gated by instruction costs, so I thought maybe there's a way to squeeze this into the existing code, but I know that's a stretch too.

[jfb]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

I don't think we're super clear on what we guarantee, but knowing people who use volatile: when they say "load an integer and cast it to a float" they expect to do an integer, followed by an integer->float register transfer. That's a reasonable expectation IMO.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

People also expect UB to be ignored by compiler.
Unless it's spelled out in langref i don't believe i know why this should be changed.

[jfb]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

That's a user-hostile approach to compiler optimizations. It's not a useful thing to optimize, and developers don't have a way to express this, so they'd have to turn to assembly. We could simply be nice and do what's trivial for us to do.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

That is not what i'm saying :)

You have either pointed out a miscompile, or not. If it's a miscompile,
then someone knowledgeable (you) should document it [in langref]
for future reference, to avoid having this disscussion in the future
and simplify the life of whoever would want to be aware of it later.

I don't care either way, i just don't want to have such undocumented
limitation/guaranteed spelled out in the code and not in documentation.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

570–573

Ah, i see why volatile is currently not being transformed.

[lebedev.ri]

Review notes addressed, PTAL.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

571

Tests are being added by D75644, this fold is apparently not happening
for volatile loads and i'm not planning on changing that.
Nothing further to do.

[jfb]

Can you add a few tests for this specifically, both with identical subsequent bitcasts as well as with mixed ones?

[lebedev.ri]

In D75505#1910065, @jfb wrote:

Can you add a few tests for this specifically, both with identical subsequent bitcasts as well as with mixed ones?

I'm not sure i'm following.
There are negative tests for this in llvm/test/Transforms/InstCombine/multi-use-load-casts.ll.
On top of those, what other tests would you like to see?

[lebedev.ri]

In D75505#1910122, @lebedev.ri wrote:

In D75505#1910065, @jfb wrote:

Can you add a few tests for this specifically, both with identical subsequent bitcasts as well as with mixed ones?

I'm not sure i'm following.
There are negative tests for this in llvm/test/Transforms/InstCombine/multi-use-load-casts.ll.
On top of those, what other tests would you like to see?

up

[lebedev.ri]

@spatel could you please specify if you don't want this in instcombine

[spatel]

In D75505#1914300, @lebedev.ri wrote:

@spatel could you please specify if you don't want this in instcombine

If the consensus is that this is good, I'm not going to block it, but...

1. Loads are usually between 10-25% of all instructions, so walking the users of every load has potential to substantially increase compile-time.
2. According to the summary text, we don't have practical evidence of the benefit.
3. We agree that we could do hoisting/sinking more generally and more efficiently in a stand-alone pass.

So I'd prefer an alternative route or at least some preliminary perf data if that's feasible.

I was just rummaging around in CGP and noticed that it has CodeGenPrepare::tryToSinkFreeOperands(). Maybe we could move that up as a utility function and extend it to try hoisting too?

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (!match(V, m_Select(m_Cmp(Pred, m_Instruction(L1), m_Instruction(L2)),
     return false;
   LoadTy = L1->getType();
   return (match(L1, m_Load(m_Specific(LHS))) &&
           match(L2, m_Load(m_Specific(RHS)))) ||
          (match(L1, m_Load(m_Specific(RHS))) &&
           match(L2, m_Load(m_Specific(LHS))));
 }
 
+// Fold away bit casts of the loaded value by loading the desired type.
+// We can do this for BitCastInsts as well as casts from and to pointer types,
+// as long as those are noops (i.e., the source or dest type have the same
+// bitwidth as the target's pointers).
+static Instruction *combineIdenticalCastsIntoLoad(InstCombiner &IC,
+                                                  LoadInst &LI) {
+  llvm::SmallVector<CastInst *, 4> Casts;
+  Type *DestTy = nullptr;
+
+  for (User *U : LI.users()) {
+    auto *CI = dyn_cast<CastInst>(U);
+    if (!CI)
+      return nullptr;
+    // If this is the first cast we've encountered, capture the dest type.
+    if (!DestTy) {
+      DestTy = CI->getDestTy();
+      // Note that if load is atomic, we might not be able to change load type.
+      if (LI.isAtomic() && !isSupportedAtomicType(DestTy))
+        return nullptr;
+    }
+    // All casts must have identical destination type.
+    if (DestTy != CI->getDestTy())
+      return nullptr;
+    // The cast must actually be something that can be folded into load.
+    if (!CI->isNoopCast(IC.getDataLayout()))
+      return nullptr;
+    // Great, cast appears to be identical.
+    Casts.emplace_back(CI);
+  }
+  if (Casts.empty())
+    return nullptr; // No users?
+
+  // Great, can CSE casts and fold it into load.
+  LoadInst *NewLoad = IC.combineLoadToNewType(LI, DestTy);
+  for (CastInst *CI : Casts) {
+    IC.replaceInstUsesWith(*CI, NewLoad);
+    IC.eraseInstFromFunction(*CI);
+  }
+  assert(LI.use_empty() && "Failed to remove all users of the load!");
+
+  return &LI;
+}
+
 /// Combine loads to match the type of their uses' value after looking
 /// through intervening bitcasts.
 ///
 /// The core idea here is that if the result of a load is used in an operation,
 /// we should load the type most conducive to that operation. For example, when
 /// loading an integer and converting that immediately to a pointer, we should
 /// instead directly load a pointer.
 ///
 /// However, this routine must never change the width of a load or the number of
 /// loads as that would introduce a semantic change. This combine is expected to
 /// be a semantic no-op which just allows loads to more closely model the types
 /// of their consuming operations.
 ///
 /// Currently, we also refuse to change the precise type used for an atomic load
 /// or a volatile load. This is debatable, and might be reasonable to change
 /// later. However, it is risky in case some backend or other part of LLVM is
 /// relying on the exact type loaded to select appropriate atomic operations.
 static Instruction *combineLoadToOperationType(InstCombiner &IC, LoadInst &LI) {
   // FIXME: We could probably with some care handle both volatile and ordered
   // atomic loads here but it isn't clear that this is important.
   if (!LI.isUnordered())
     return nullptr;
 
   if (LI.use_empty())
     return nullptr;
 
   // swifterror values can't be bitcasted.
   if (LI.getPointerOperand()->isSwiftError())
     return nullptr;
 
if (all_of(LI.users(), [&LI](User *U) {
         IC.eraseInstFromFunction(*SI);
       }
       assert(LI.use_empty() && "Failed to remove all users of the load!");
       // Return the old load so the combiner can delete it safely.
       return &LI;
     }
   }
 
-  // Fold away bit casts of the loaded value by loading the desired type.
-  // We can do this for BitCastInsts as well as casts from and to pointer types,
-  // as long as those are noops (i.e., the source or dest type have the same
-  // bitwidth as the target's pointers).
-  if (LI.hasOneUse())
-    if (auto* CI = dyn_cast<CastInst>(LI.user_back()))
-      if (CI->isNoopCast(DL))
-        if (!LI.isAtomic() || isSupportedAtomicType(CI->getDestTy())) {
-          LoadInst *NewLoad = IC.combineLoadToNewType(LI, CI->getDestTy());
-          CI->replaceAllUsesWith(NewLoad);
-          IC.eraseInstFromFunction(*CI);
-          return &LI;
-        }
+  // If all users of this load are identical casts, fold them into load.
+  if (Instruction *NewLoad = combineIdenticalCastsIntoLoad(IC, LI))
+    return NewLoad;
 
   // FIXME: We should also canonicalize loads of vectors when their elements are
   // cast to other types.
   return nullptr;
 }
 
 static Instruction *unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI) {
   // FIXME: We could probably with some care handle both volatile and atomic

llvm/test/Transforms/InstCombine/multi-use-load-casts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Positive test - all uses are identical casts.
 define void @t0(i1 zeroext %c0, i1 zeroext %c1, i64* nocapture readonly %src) {
 ; CHECK-LABEL: @t0(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[DATA:%.*]] = load i64, i64* [[SRC:%.*]], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i64* [[SRC:%.*]] to i32**
+; CHECK-NEXT:    [[DATA1:%.*]] = load i32*, i32** [[TMP0]], align 8
 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[BB3:%.*]], label [[BB7:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    tail call void @abort()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb5:
-; CHECK-NEXT:    [[PTR0:%.*]] = inttoptr i64 [[DATA]] to i32*
-; CHECK-NEXT:    tail call void @sink0(i32* [[PTR0]])
+; CHECK-NEXT:    tail call void @sink0(i32* [[DATA1]])
 ; CHECK-NEXT:    br label [[BB9:%.*]]
 ; CHECK:       bb7:
-; CHECK-NEXT:    [[PTR1:%.*]] = inttoptr i64 [[DATA]] to i32*
-; CHECK-NEXT:    tail call void @sink1(i32* [[PTR1]])
+; CHECK-NEXT:    tail call void @sink1(i32* [[DATA1]])
 ; CHECK-NEXT:    br label [[BB9]]
 ; CHECK:       bb9:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %data = load i64, i64* %src, align 8
   br i1 %c0, label %bb3, label %bb7