[Analysis] Analysis of storing unchanged loaded value

[ara-sc]

Summary

Presumably patterns of the following kind could be optimized:

%0 = load i8, ptr %c, align 1
store i8 %0, ptr %a, align 1
%1 = load i8, ptr %c, align 1
store i8 %1, ptr %b, align 1

InstCombine is responsible for these optimization. Only this pass (InstCombinerImpl::visitLoadInst) uses llvm::FindAvailableLoadedValue to find previous available loads.
So we can add simple helper to get rid of the redundant code.

[nikic]

InstCombine is responsible for these optimization.

Not really. The pass responsible for this is GVN, via MemDepAnalysis and to a lesser degree EarlyCSE via MSSA. InstCombine implements a very weak version of load CSE optimization for phase ordering reasons. I'm skeptical about making InstCombine handle patterns that GVN cannot handle, because the optimization in InstCombine is fundamentally limited to a tiny instruction window.

llvm/lib/Analysis/Loads.cpp

while (ScanFrom != ScanBB->begin()) {
     }
   }
 
   // Got to the start of the block, we didn't find it, but are done for this
   // block.
   return nullptr;
 }
 
+static bool mayOverlapLoadedMemory(const StoreInst *Store, const LoadInst *Load,
+                                   const DataLayout &DL) {
+  if (Store->getValueOperand() != Load) {
+    return true;
+  }
+  auto *Ty = Load->getType();
+  if (Ty->isScalableTy()) {
+    return true;
+  }
+  auto AlignValue = Load->getAlign().value();
+  if (Store->getAlign().value() != AlignValue) {
+    return true;
+  }
+  auto TyStoreSize = DL.getTypeStoreSize(Ty).getFixedSize();
+  if (TyStoreSize > AlignValue) {
+    return true;
+  }
+  return false;
+}
+
+static bool writesUnchangedLoadedValueToSameLocation(const Instruction *Inst,
+                                                     const Value *Available,
+                                                     const DataLayout &DL) {
+  auto *Store = dyn_cast_or_null<StoreInst>(Inst);
+  auto *Load = dyn_cast_or_null<LoadInst>(Available);
+  if (!Store || !Load || mayOverlapLoadedMemory(Store, Load, DL)) {
+    return false;
+  }
+  return true;
+}
+
 Value *llvm::FindAvailableLoadedValue(LoadInst *Load, AAResults &AA,
                                       bool *IsLoadCSE,
                                       unsigned MaxInstsToScan) {
   const DataLayout &DL = Load->getModule()->getDataLayout();
   Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
   BasicBlock *ScanBB = Load->getParent();
   Type *AccessTy = Load->getType();
   bool AtLeastAtomic = Load->isAtomic();
for (Instruction &Inst : make_range(++Load->getReverseIterator(),
     if (Inst.mayWriteToMemory())
       MustNotAliasInsts.push_back(&Inst);
   }
 
   // If we found an available value, ensure that the instructions in between
   // did not modify the memory location.
   if (Available) {
     MemoryLocation Loc = MemoryLocation::get(Load);
-    for (Instruction *Inst : MustNotAliasInsts)
+    for (Instruction *Inst : MustNotAliasInsts) {
+      if (writesUnchangedLoadedValueToSameLocation(Inst, Available, DL)) {
+        continue;
+      }
       if (isModSet(AA.getModRefInfo(Inst, Loc)))
         return nullptr;
     }
+  }
 
   return Available;
 }
 
 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
                                      Instruction *CtxI) {
   Type *Ty = A->getType();
   assert(Ty == B->getType() && Ty->isPointerTy() &&

llvm/test/Transforms/InstCombine/load-elimination.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine -S < %s | FileCheck %s
 
 define void @load_elimination_i8(ptr noundef %a, ptr noundef %b, ptr noundef %c) {
 ; CHECK-LABEL: @load_elimination_i8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[C:%.*]], align 1
 ; CHECK-NEXT:    store i8 [[TMP0]], ptr [[A:%.*]], align 1
-; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[C]], align 1
-; CHECK-NEXT:    store i8 [[TMP1]], ptr [[B:%.*]], align 1
+; CHECK-NEXT:    store i8 [[TMP0]], ptr [[B:%.*]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = load i8, ptr %c, align 1
   store i8 %0, ptr %a, align 1
   %1 = load i8, ptr %c, align 1
   store i8 %1, ptr %b, align 1
   ret void
 }
 
 define void @load_elimination_i32(ptr noundef %a, ptr noundef %b, ptr noundef %c) {
 ; CHECK-LABEL: @load_elimination_i32(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    store i32 [[TMP0]], ptr [[A:%.*]], align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[C]], align 4
-; CHECK-NEXT:    store i32 [[TMP1]], ptr [[B:%.*]], align 4
+; CHECK-NEXT:    store i32 [[TMP0]], ptr [[B:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = load i32, ptr %c, align 4
   store i32 %0, ptr %a, align 4
   %1 = load i32, ptr %c, align 4
   store i32 %1, ptr %b, align 4
   ret void
entry:
   ret void
 }
 
 define void @load_elimination_float(ptr %x, ptr %a, ptr %b, ptr %c) {
 ; CHECK-LABEL: @load_elimination_float(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = load float, ptr [[X:%.*]], align 4
 ; CHECK-NEXT:    store float [[X1]], ptr [[A:%.*]], align 4
-; CHECK-NEXT:    [[X2:%.*]] = load float, ptr [[X]], align 4
-; CHECK-NEXT:    store float [[X2]], ptr [[C:%.*]], align 4
+; CHECK-NEXT:    store float [[X1]], ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x1 = load float, ptr %x
   store float %x1, ptr %a
   %x2 = load float, ptr %x
   store float %x2, ptr %c
   ret void
 }

llvm/test/Transforms/InstCombine/load.ll

 ; when there is a valid integer type.
 
 define void @test16(ptr %x, ptr %a, ptr %b, ptr %c) {
 ; CHECK-LABEL: @test16(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = load float, ptr [[X:%.*]], align 4
 ; CHECK-NEXT:    store float [[X1]], ptr [[A:%.*]], align 4
 ; CHECK-NEXT:    store float [[X1]], ptr [[B:%.*]], align 4
-; CHECK-NEXT:    [[X2:%.*]] = load float, ptr [[X]], align 4
-; CHECK-NEXT:    store float [[X2]], ptr [[B]], align 4
-; CHECK-NEXT:    store float [[X2]], ptr [[C:%.*]], align 4
+; CHECK-NEXT:    store float [[X1]], ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
 
   %x1 = load float, ptr %x
   store float %x1, ptr %a
   store float %x1, ptr %b
 
   %x2 = load float, ptr %x
   store float %x2, ptr %b
   %x2.cast = bitcast float %x2 to i32
   store i32 %x2.cast, ptr %c
 
   ret void
 }
 
 define void @test16-vect(ptr %x, ptr %a, ptr %b, ptr %c) {
 ; CHECK-LABEL: @test16-vect(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = load <4 x i8>, ptr [[X:%.*]], align 4
 ; CHECK-NEXT:    store <4 x i8> [[X1]], ptr [[A:%.*]], align 4
 ; CHECK-NEXT:    store <4 x i8> [[X1]], ptr [[B:%.*]], align 4
-; CHECK-NEXT:    [[X2:%.*]] = load <4 x i8>, ptr [[X]], align 4
-; CHECK-NEXT:    store <4 x i8> [[X2]], ptr [[B]], align 4
-; CHECK-NEXT:    store <4 x i8> [[X2]], ptr [[C:%.*]], align 4
+; CHECK-NEXT:    store <4 x i8> [[X1]], ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
 
   %x1 = load <4 x i8>, ptr %x
   store <4 x i8> %x1, ptr %a
   store <4 x i8> %x1, ptr %b