[InstCombine] Fix for trunc folding build break

[anna]

Summary

We can fold truncs whose operand feeds from a load, if the trunc value is available through a prior load/store.

This change is from: http://reviews.llvm.org/D21246, which folded the trunc but missed the bitcast or ptrtoint/inttoptr required in the RAUW call, when the load type didnt match the prior load/store type.

The change was reverted in: r273703 due to fail in Chromium and sanitizer build. This was the bad RAUW assertion:
Assertion failed: New->getType() == getType() && "replaceAllUses of value with new value of different type!", file ..\lib\IR\Value.cpp, line 375

Load being used:

%138 = load float, float* %m_x.i527, align 4, !dbg !447

Trunc being replaced:

%155 = trunc i64 %140 to i32, !dbg !470

This change fixes the above issue, and I've added a testcase to make sure that we don't fail the assertion (@trunc_avoid_bitcast). Also, couple of other testcases added.

[anna]

Could think of 3 possible ways to fix the build breakage caused by type mismatch (the test case which showcases the breakage is @trunc_avoid_bitcast):

1. The RAUW return replaceInstUsesWith(CI, AvailableVal); should be return replaceInstUsesWith( CI, Builder->CreateBitOrPointerCast(AvailableVal, CI.getType(), CI.getName() + ".cast"));

2. Avoid the RAUW when the AvailableVal type is not the same as DestTy of trunc.
3. Special case the trunc type in FindAvailableLoadedValue (i.e. check for exact match rather than CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) Error-prone solution whose benefit is minimal.

I followed #2.

What #1 does is replace the trunc with a bitcast or PointerCast. While generating bitcast would be useful if FindAvailableLoadedValue was used to replace loads, there does not seem to be a *strong* benefit in replacing the trunc with bitcast or pointercast. Looking at SelectionDAG::visitBitCast and all the pointer cast instructions, it may or may not be a noop. I didnot see an obvious benefit (i.e. hold true in all cases) in using BitOrPointerCast instead of trunc.
Also, this avoids possible performance regression creeping up due to some specific target lowering or due to optimizations that benefit trunc rather than BitOrPointerCast.

[sanjoy]

Hi Anna,

In D21791#468817, @anna wrote:

Could think of 3 possible ways to fix the build breakage caused by
type mismatch (the test case which showcases the breakage is
@trunc_avoid_bitcast):

1. The RAUW return replaceInstUsesWith(CI, AvailableVal); should be return replaceInstUsesWith( CI, Builder->CreateBitOrPointerCast(AvailableVal, CI.getType(), CI.getName() + ".cast"));

2. Avoid the RAUW when the AvailableVal type is not the same as DestTy of trunc.
3. Special case the trunc type in FindAvailableLoadedValue (i.e. check for exact match rather than CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) Error-prone solution whose benefit is minimal.

I followed #2.

What #1 does is replace the trunc with a bitcast or
PointerCast. While generating bitcast would be useful if
FindAvailableLoadedValue was used to replace loads, there does not
seem to be a *strong* benefit in replacing the trunc with bitcast or
pointercast. Looking at SelectionDAG::visitBitCast and all the
pointer cast instructions, it may or may not be a noop. I didnot see
an obvious benefit (i.e. hold true in all cases) in using
BitOrPointerCast instead of trunc.

The normal LLVM meme is "bitcasts are free", so I'd be tempted to with
#1. That is also less surprising (a "spurious" pointer cast won't
break optimization). ISDOpcodes.h says that there are cases where
ISD::BITCAST will not be a no-op, but my guess is that it is still
better to replace a trunc with bitcast (i.e. even in the "worst"
case a bitcast will be no worse than a trunc).

Also, this avoids possible performance regression creeping up due to
some specific target lowering or due to optimizations that benefit
trunc rather than BitOrPointerCast.

Given how ubiquitous bitcast s are in LLVM IR, I think that ^ is
unlikely (and if we find such an optimization that is broken by a
bitcast, we should fix the optimization).

[anna]

The RAUW in visitTrunc inserts BitOrPointerCast if required and replaces all uses of the trunc.

[sanjoy]

lib/Transforms/InstCombine/InstCombineCasts.cpp

592 ↗

(On Diff #62216)

Don't we have to check if LI is at most unordered? I realize I missed this the last time.

Please also add a test case.

[anna]

addressed Sanjoy's comments - load atomic ordering should be at most unordered. Added test case trunc_atomic_monotonic

[anna]

corrected trunc_atomic_monotonic test Filecheck statement.

[anna]

ping.

[reames]

LGTM w/comments addressed.

lib/Analysis/Loads.cpp

328 ↗

(On Diff #62380)

I'm not following why you need this new interface. Why can't we reuse the existing interface? We have the load instruction don't we?

... I think I see it. The issue is we need to use the narrower type right? The comment seams to be stale. You're really using the size of the access ty. Can you adjust the comment to make this more obvious.

p.s. Please don't repeat function comments in the cpp. And yes, I know the near by code does. This is older style.

lib/Transforms/InstCombine/InstCombineCasts.cpp

595 ↗

(On Diff #62380)

I think what you've got here is entirely correct, but let me sketch and alternate framing to see if you think this is simpler. Instead of splitting out the properties of the load, we leave the interface that of the load, but add the accessty (which is asserts as less than the load type). If we do that, the atomicity check can be sunk into the common code.

test/Transforms/InstCombine/trunc.ll

186 ↗

(On Diff #62380)

Add a comment about this only be legal for non-atomic loads since you essentially split the load here.

198 ↗

(On Diff #62380)

Add check lines for the other half of the original load.

213 ↗

(On Diff #62380)

Add positive checks for the two consume lines at least.

258 ↗

(On Diff #62380)

Add a positive test for the two consume lines.

276 ↗

(On Diff #62380)

This looks to be a missed optimization. Please comment it as such.

[anna]

lib/Analysis/Loads.cpp

328 ↗

(On Diff #62380)

This function FindAvailableLoadedValue is used to see if we have the contents of type AccessTy at location Ptr.

This function can be called for either full or partial sizes, as mentioned in start of the comment:

Scan the ScanBB block backwards checking to see if we have the value at the memory address \p Ptr of type \p AccessTy

Will remove the comment from cpp, and try to make the need for the interface more obvious.

lib/Transforms/InstCombine/InstCombineCasts.cpp

595 ↗

(On Diff #62380)

We had this in one of the iterations in prior review.

We changed the function signature to be a memory location, rather than an load instruction (http://reviews.llvm.org/D21246#463566).

Discussed with Sanjoy and reasons were:

1. we can use this function to see (partial or full) memory contents of any operation -- memcpy, load etc. Required constraints should be verified at the caller, as mentioned in function comments.

/// Note that we assume the \p *Ptr is accessed through a non-volatile but
/// potentially atomic load. Any other constraints should be verified at the
/// caller.

2. Use FindAvailableLoadedValue as-is in most optimizations which require the full load value. No change to function signature.

I had added the Type *accessTy to the original interface with the LoadInst, but this was error prone since there was ambiguity on whether LoadInst->getType() or AccessTy (from visitTrunc) are used. Your suggestion would allow us to use a single type accessTy , but change the calls to this function used in various optimizations.

[anna]

test/Transforms/InstCombine/trunc.ll

186 ↗

(On Diff #62380)

the load is not split/shrunk. Only the trunc is removed, and all uses of trunc replaced by corresponding store value.

198 ↗

(On Diff #62380)

Added checks for making sure load is as it is.

[anna]

Addressed review comments:
Updated comment for AvailableLoadedValue. Updated comments and file checks for tests

llvm/trunk/include/llvm/Analysis/Loads.h

bool isSafeToLoadUnconditionally(Value *V, unsigned Align,
                                  const DataLayout &DL,
                                  Instruction *ScanFrom = nullptr,
                                  const DominatorTree *DT = nullptr);
 
 /// DefMaxInstsToScan - the default number of maximum instructions
 /// to scan in the block, used by FindAvailableLoadedValue().
 extern cl::opt<unsigned> DefMaxInstsToScan;
 
+/// \brief Scan backwards to see if we have the value of type \p AccessTy
+/// at the memory address \p Ptr locally available within a
+/// small number of instructions. If the value is available, return it.
+///
+/// You can use this function to scan across multiple blocks: after you call
+/// this function, if ScanFrom points at the beginning of the block, it's safe
+/// to continue scanning the predecessors.
+/// Note that we assume the \p *Ptr is accessed through a non-volatile but
+/// potentially atomic load. Any other constraints should be verified at the
+/// caller.
+///
+/// \param Ptr The memory location whose contents we are retrieving
+/// \param AccessTy The type (and size) of the contents we need from \p Ptr
+/// \param IsAtomicMemOp specifies the atomicity of the memory operation that accesses
+/// \p *Ptr. We verify atomicity constraints are satisfied when value forwarding
+/// from another memory operation that has value \p *Ptr available.
+/// \param ScanBB The basic block to scan. FIXME: This is redundant.
+/// \param [in,out] ScanFrom The location to start scanning from. When this
+/// function returns, it points at the last instruction scanned.
+/// \param MaxInstsToScan The maximum number of instructions to scan. If this
+/// is zero, the whole block will be scanned.
+/// \param AA Optional pointer to alias analysis, to make the scan more
+/// precise.
+/// \param [out] AATags The aliasing metadata for the operation which produced
+/// the value. FIXME: This is basically useless.
+///
+/// \param [out] IsLoadCSE Whether the returned value is a load from the same
+/// location in memory, as opposed to the value operand of a store.
+///
+/// \returns The found value, or nullptr if no value is found.
+Value *FindAvailableLoadedValue(Value *Ptr, Type *AccessTy, bool IsAtomicMemOp,
+                                BasicBlock *ScanBB,
+                                BasicBlock::iterator &ScanFrom,
+                                unsigned MaxInstsToScan,
+                                AliasAnalysis *AA = nullptr,
+                                AAMDNodes *AATags = nullptr,
+                                bool *IsLoadCSE = nullptr);
+
 /// \brief Scan backwards to see if we have the value of the given load
 /// available locally within a small number of instructions.
 ///
 /// You can use this function to scan across multiple blocks: after you call
 /// this function, if ScanFrom points at the beginning of the block, it's safe
 /// to continue scanning the predecessors.
 ///
 /// Note that performing load CSE requires special care to make sure the

llvm/trunk/lib/Analysis/Loads.cpp

 /// At that point, the value of MaxInstsToScan was already set to '6'
 /// without documented explanation.
 cl::opt<unsigned>
 llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
   cl::desc("Use this to specify the default maximum number of instructions "
            "to scan backward from a given instruction, when searching for "
            "available loaded value"));
 
-Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
+
+Value *llvm::FindAvailableLoadedValue(Value *Ptr, Type *AccessTy,
+                                      bool IsAtomicMemOp, BasicBlock *ScanBB,
                                       BasicBlock::iterator &ScanFrom,
                                       unsigned MaxInstsToScan,
                                       AliasAnalysis *AA, AAMDNodes *AATags,
                                       bool *IsLoadCSE) {
+
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
-
-  Value *Ptr = Load->getPointerOperand();
-  Type *AccessTy = Load->getType();
-
-  // We can never remove a volatile load
-  if (Load->isVolatile())
-    return nullptr;
-
-  // Anything stronger than unordered is currently unimplemented.
-  if (!Load->isUnordered())
-    return nullptr;
-
   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
-
   // Try to get the store size for the type.
   uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
 
   Value *StrippedPtr = Ptr->stripPointerCasts();
 
   while (ScanFrom != ScanBB->begin()) {
     // We must ignore debug info directives when counting (otherwise they
     // would affect codegen).
while (ScanFrom != ScanBB->begin()) {
     // those cases are unlikely.)
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
       if (AreEquivalentAddressValues(
               LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) &&
           CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
 
         // We can value forward from an atomic to a non-atomic, but not the
         // other way around.
-        if (LI->isAtomic() < Load->isAtomic())
+        if (LI->isAtomic() < IsAtomicMemOp)
           return nullptr;
 
         if (AATags)
           LI->getAAMetadata(*AATags);
         if (IsLoadCSE)
             *IsLoadCSE = true;
         return LI;
       }
 
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
       // If this is a store through Ptr, the value is available!
       // (This is true even if the store is volatile or atomic, although
       // those cases are unlikely.)
       if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
           CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(),
                                                AccessTy, DL)) {
 
         // We can value forward from an atomic to a non-atomic, but not the
         // other way around.
-        if (SI->isAtomic() < Load->isAtomic())
+        if (SI->isAtomic() < IsAtomicMemOp)
           return nullptr;
 
         if (AATags)
           SI->getAAMetadata(*AATags);
         return SI->getOperand(0);
       }
 
       // If both StrippedPtr and StorePtr reach all the way to an alloca or
if (Inst->mayWriteToMemory()) {
       return nullptr;
     }
   }
 
   // Got to the start of the block, we didn't find it, but are done for this
   // block.
   return nullptr;
 }
+
+
+Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
+                                      BasicBlock::iterator &ScanFrom,
+                                      unsigned MaxInstsToScan,
+                                      AliasAnalysis *AA, AAMDNodes *AATags,
+                                      bool *IsLoadCSE) {
+
+  // We can never remove a volatile load
+  if (Load->isVolatile())
+    return nullptr;
+
+  // Anything stronger than unordered is currently unimplemented.
+  if (!Load->isUnordered())
+    return nullptr;
+
+  // Return the full value of the load if available.
+  return FindAvailableLoadedValue(Load->getPointerOperand(), Load->getType(),
+                                  Load->isAtomic(), ScanBB, ScanFrom,
+                                  MaxInstsToScan, AA, AATags, IsLoadCSE);
+}

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/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/TargetLibraryInfo.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"
 
 /// Analyze 'Val', seeing if it is a simple linear expression.
 /// If so, decompose it, returning some value X, such that Val is
 /// X*Scale+Offset.
if (Src->hasOneUse() && isa<IntegerType>(SrcTy) &&
     Value *NewTrunc = Builder->CreateTrunc(A, DestTy, A->getName() + ".tr");
     return BinaryOperator::CreateAnd(NewTrunc,
                                      ConstantExpr::getTrunc(Cst, DestTy));
   }
 
   if (Instruction *I = foldVecTruncToExtElt(CI, *this, DL))
     return I;
 
+  // When trunc operand is a widened load, see if we can get the value from a
+  // previous store/load
+  if (auto *LI = dyn_cast<LoadInst>(Src)) {
+    BasicBlock::iterator BBI(*LI);
+
+    // Scan a few instructions up from LI and if we find a partial load/store
+    // of Type DestTy that feeds into LI, we can replace all uses of the trunc
+    // with the load/store value.
+    // This replacement can be done only in the case of non-volatile loads, with
+    // ordering at most unordered. If the load is atomic, its only use should be
+    // the trunc instruction. We don't want to allow other users of LI to see a
+    // value that is out of sync with the value we're folding the trunc to (in
+    // case of a race).
+    if (LI->isUnordered() && (!LI->isAtomic() || LI->hasOneUse()))
+      if (Value *AvailableVal = FindAvailableLoadedValue(
+              LI->getPointerOperand(), DestTy, LI->isAtomic(), LI->getParent(),
+              BBI, DefMaxInstsToScan))
+        return replaceInstUsesWith(
+            CI, Builder->CreateBitOrPointerCast(AvailableVal, CI.getType(),
+                                                CI.getName() + ".cast"));
+  }
   return nullptr;
 }
 
 /// Transform (zext icmp) to bitwise / integer operations in order to eliminate
 /// the icmp.
 Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, Instruction &CI,
                                              bool DoXform) {
   // If we are just checking for a icmp eq of a single bit and zext'ing it

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

 bb1:
   %tmp5 = sub i32 0, %tmp1
   %tmp6 = sub i32 %tmp5, 1
   unreachable
 
 bb2:
   unreachable
 }
+
+
+; the trunc can be replaced from value available from store
+; load feeding into trunc left as-is.
+declare void @consume(i8) readonly
+define i1 @trunc_load_store(i8* align 2 %a) {
+  store i8 0, i8 *%a, align 2
+  %bca  = bitcast i8* %a to i16*
+  %wide.load = load i16, i16* %bca, align 2
+  %lowhalf.1 = trunc i16 %wide.load to i8
+  call void @consume(i8 %lowhalf.1)
+  %cmp.2 = icmp ult i16 %wide.load, 256
+  ret i1 %cmp.2
+; CHECK-LABEL: @trunc_load_store
+; CHECK: %wide.load = load i16, i16* %bca, align 2
+; CHECK-NOT: trunc
+; CHECK: call void @consume(i8 0)
+}
+
+
+; The trunc can be replaced with the load value.
+; both loads left as-is, since they have uses.
+define i1 @trunc_load_load(i8* align 2 %a) {
+  %pload = load i8, i8* %a, align 2
+  %bca  = bitcast i8* %a to i16*
+  %wide.load = load i16, i16* %bca, align 2
+  %lowhalf = trunc i16 %wide.load to i8
+  call void @consume(i8 %lowhalf)
+  call void @consume(i8 %pload)
+  %cmp.2 = icmp ult i16 %wide.load, 256
+  ret i1 %cmp.2
+; CHECK-LABEL: @trunc_load_load
+; CHECK-NEXT: %pload = load i8, i8* %a, align 2
+; CHECK-NEXT: %bca  = bitcast i8* %a to i16*
+; CHECK-NEXT: %wide.load = load i16, i16* %bca, align 2
+; CHECK-NEXT: call void @consume(i8 %pload)
+; CHECK-NEXT: call void @consume(i8 %pload)
+; CHECK-NEXT: %cmp.2 = icmp ult i16 %wide.load, 256
+}
+
+; Store and load to same memory location address generated through GEP.
+; trunc can be removed by using the store value.
+define void @trunc_with_gep_memaccess(i16* align 2 %p) {
+  %t0 = getelementptr i16, i16* %p, i32 1
+  store i16 2, i16* %t0
+  %t1 = getelementptr i16, i16* %p, i32 1
+  %x = load i16, i16* %t1
+  %lowhalf = trunc i16 %x to i8
+  call void @consume(i8 %lowhalf)
+  ret void
+; CHECK-LABEL: @trunc_with_gep_memaccess
+; CHECK-NOT: trunc
+; CHECK: call void @consume(i8 2)
+}
+
+; trunc should not be replaced since atomic load %wide.load has more than one use.
+; different values can be seen by the uses of %wide.load in case of race.
+define i1 @trunc_atomic_loads(i8* align 2 %a) {
+  %pload = load atomic i8, i8* %a unordered, align 2
+  %bca  = bitcast i8* %a to i16*
+  %wide.load = load atomic i16, i16* %bca unordered, align 2
+  %lowhalf = trunc i16 %wide.load to i8
+  call void @consume(i8 %lowhalf)
+  call void @consume(i8 %pload)
+  %cmp.2 = icmp ult i16 %wide.load, 256
+  ret i1 %cmp.2
+; CHECK-LABEL: @trunc_atomic_loads
+; CHECK: trunc
+}
+
+; trunc can be replaced since atomic load has single use.
+; atomic load is also removed since use is removed.
+define void @trunc_atomic_single_load(i8* align 2 %a) {
+  %pload = load atomic i8, i8* %a unordered, align 2
+  %bca  = bitcast i8* %a to i16*
+  %wide.load = load atomic i16, i16* %bca unordered, align 2
+  %lowhalf = trunc i16 %wide.load to i8
+  call void @consume(i8 %lowhalf)
+  call void @consume(i8 %pload)
+  ret void
+; CHECK-LABEL: @trunc_atomic_single_load
+; CHECK-NOT: trunc
+; CHECK-NOT: %wide.load = load atomic i16, i16* %bca unordered, align 2
+}
+
+
+; trunc cannot be replaced since load's atomic ordering is higher than unordered
+define void @trunc_atomic_monotonic(i8* align 2 %a) {
+  %pload = load atomic i8, i8* %a monotonic, align 2
+  %bca  = bitcast i8* %a to i16*
+  %wide.load = load atomic i16, i16* %bca monotonic, align 2
+  %lowhalf = trunc i16 %wide.load to i8
+  call void @consume(i8 %lowhalf)
+  call void @consume(i8 %pload)
+  ret void
+; CHECK-LABEL: @trunc_atomic_monotonic
+; CHECK: %wide.load = load atomic i16, i16* %bca monotonic, align 2
+; CHECK: trunc
+}
+
+; trunc cannot be replaced since store size (i16) is not trunc result size (i8).
+; FIXME: we could get the i8 content of trunc from the i16 store value.
+define i1 @trunc_different_size_load(i16 * align 2 %a) {
+  store i16 0, i16 *%a, align 2
+  %bca  = bitcast i16* %a to i32*
+  %wide.load = load i32, i32* %bca, align 2
+  %lowhalf = trunc i32 %wide.load to i8
+  call void @consume(i8 %lowhalf)
+  %cmp.2 = icmp ult i32 %wide.load, 256
+  ret i1 %cmp.2
+; CHECK-LABEL: @trunc_different_size_load
+; CHECK: %lowhalf = trunc i32 %wide.load to i8
+}
+
+declare void @consume_f(float) readonly
+; bitcast required since trunc result type and %fload are different types.
+; so replace the trunc with bitcast.
+define i1 @trunc_avoid_bitcast(float* %b) {
+  %fload = load float, float* %b
+  %bca = bitcast float* %b to i64*
+  %iload = load i64, i64* %bca
+  %low32 = trunc i64 %iload to i32
+  call void @consume_f(float %fload)
+  %cmp.2 = icmp ult i32 %low32, 256
+  ret i1 %cmp.2
+; CHECK-LABEL: @trunc_avoid_bitcast
+; CHECK-NOT: %low32 = trunc i64 %iload to i32
+; CHECK: %low32.cast = bitcast float %fload to i32
+; CHECK: %cmp.2 = icmp ult i32 %low32.cast, 256
+}