Do not widen load for different variable in GVN.

[danielcdh]

Summary

Widening load in GVN is too early because it will block other optimizations like PRE, LICM.

https://llvm.org/bugs/show_bug.cgi?id=29110

The SPECCPU2006 benchmark impact of this patch:

Reference: o2_nopatch
(1): o2_patched

Benchmark             Base:Reference   (1)

---

spec/2006/fp/C++/444.namd 25.2 -0.08%
spec/2006/fp/C++/447.dealII 45.92 +1.05%
spec/2006/fp/C++/450.soplex 41.7 -0.26%
spec/2006/fp/C++/453.povray 35.65 +1.68%
spec/2006/fp/C/433.milc 23.79 +0.42%
spec/2006/fp/C/470.lbm 41.88 -1.12%
spec/2006/fp/C/482.sphinx3 47.94 +1.67%
spec/2006/int/C++/471.omnetpp 22.46 -0.36%
spec/2006/int/C++/473.astar 21.19 +0.24%
spec/2006/int/C++/483.xalancbmk 36.09 -0.11%
spec/2006/int/C/400.perlbench 33.28 +1.35%
spec/2006/int/C/401.bzip2 22.76 -0.04%
spec/2006/int/C/403.gcc 32.36 +0.12%
spec/2006/int/C/429.mcf 41.04 -0.41%
spec/2006/int/C/445.gobmk 26.94 +0.04%
spec/2006/int/C/456.hmmer 24.5 -0.20%
spec/2006/int/C/458.sjeng 28 -0.46%
spec/2006/int/C/462.libquantum 55.25 +0.27%
spec/2006/int/C/464.h264ref 45.87 +0.72%

geometric mean +0.23%

For most benchmarks, it's a wash, but we do see stable improvements on some benchmarks, e.g. 447,453,482,400.

[• dberlin]

I believe you can simply disable memdep returning these as clobbers to get the same result.

IE remove lines 583-588, and then simplify the if to be:

if (isLoad && R == NoAlias)
continue;

[danielcdh]

In D24096#530713, @dberlin wrote:

I believe you can simply disable memdep returning these as clobbers to get the same result.

IE remove lines 583-588, and then simplify the if to be:

if (isLoad && R == NoAlias)
continue;

You mean completly remove isLoadLoadClobberIfExtendedToFullWidth in MemoryDependenceAnalysis.cpp?

Then the corresponding code in GVN becomes dead code, and we can completely remove AnalyzeLoadFromClobberingLoad?

[danielcdh]

The reason I kept the code was because one test in test/Transforms/GVN/PRE/atomic.ll can still benefit from it:

; CHECK-LABEL: @test13(
; atomic to non-atomic forwarding is legal
define i32 @test13(i32* %P1) {

%a = load atomic i32, i32* %P1 seq_cst, align 4
%b = load i32, i32* %P1
%res = sub i32 %a, %b
ret i32 %res
; CHECK: load atomic i32, i32* %P1
; CHECK: ret i32 0

}

But seems this case should not be common in real code, so maybe it's okay to remove the code as well as this test?

[danielcdh]

cleanup

[reames]

In D24096#530759, @danielcdh wrote:

The reason I kept the code was because one test in test/Transforms/GVN/PRE/atomic.ll can still benefit from it:

; CHECK-LABEL: @test13(
; atomic to non-atomic forwarding is legal
define i32 @test13(i32* %P1) {

%a = load atomic i32, i32* %P1 seq_cst, align 4
%b = load i32, i32* %P1
%res = sub i32 %a, %b
ret i32 %res
; CHECK: load atomic i32, i32* %P1
; CHECK: ret i32 0

}

But seems this case should not be common in real code, so maybe it's okay to remove the code as well as this test?

The context for this comment seems to be lost in the review thread. Which piece of code was this comment in reference to? This test shouldn't be effected by a widening change. If it is, that's more than a bit suspicious.

[danielcdh]

update to fix atomic support

[reames]

Please revert the GVN changes entirely and revisit the tests. I think several of them are stale.

lib/Transforms/Scalar/GVN.cpp

1260 ↗

(On Diff #70487)

I think this comment may be misleading. Let me rewrite the example in modern IR.
%p = ...
load i32, i32* %p
%p2 = bitcast i32* to i8*
%p3 = getelementptr i8, i8* %p2, 1
load i8, i8* %p

The two loads overlap without needing to widen either load.

1272 ↗

(On Diff #70487)

Leave this as it was.

[danielcdh]

completely revert gvn

[reames]

Once we land this, remind me to come back and prune some dead cases from the GVN code. I'd like to do that separately as the code changes will be subtle.

[danielcdh]

In the latest patch, I reverted all changes in GVN, only updates the memdep to disable load-widening.

[reames]

Do you have any performance data here? I'm a bit concerned about the interactions with inlining.

test/Transforms/GVN/PRE/rle.ll

626

Add a comment that says we explicitly choose NOT to widen here and are testing to make sure we don't.

test/Transforms/GVN/big-endian.ll

10–12

Please use CHECK: forms so that we tell what's being done here. Same in other cases.

[danielcdh]

update comment

[danielcdh]

I have the perf data from the original patch (in the patch description), I don't expect it to change with the updated patch. But I can rerun test and update the result soon.

[danielcdh]

Updated perf test result:

spec/2006/fp/C++/444.namd 25.2 +0.12%
spec/2006/fp/C++/447.dealII 45.92 +0.72%
spec/2006/fp/C++/450.soplex 41.7 +0.19%
spec/2006/fp/C++/453.povray 35.65 +0.90%
spec/2006/fp/C/433.milc 23.79 +0.08%
spec/2006/fp/C/470.lbm 41.88 +0.14%
spec/2006/fp/C/482.sphinx3 47.94 +0.48%
spec/2006/int/C++/471.omnetpp 22.46 +0.18%
spec/2006/int/C++/473.astar 21.19 -0.61%
spec/2006/int/C++/483.xalancbmk 36.09 -1.66%
spec/2006/int/C/400.perlbench 33.28 +2.28%
spec/2006/int/C/401.bzip2 22.76 +0.26%
spec/2006/int/C/403.gcc 32.36 +0.22%
spec/2006/int/C/429.mcf 41.04 +0.24%
spec/2006/int/C/445.gobmk 26.94 -0.11%
spec/2006/int/C/456.hmmer 24.5 -0.16%
spec/2006/int/C/458.sjeng 28 -0.54%
spec/2006/int/C/462.libquantum 55.25 -0.07%
spec/2006/int/C/464.h264ref 45.87 +1.00%

geometric mean +0.19%

[danielcdh]

The xalan regression is secondary effect. I compared all top functions, they are all bit-identical except for different function start addresses. It shouldn't be the blocker of this patch.

[danielcdh]

Does anyone else have additional comments on this change?

If not, could someone help approve this patch?

Thanks!
Dehao

[reames]

Danny LGTM'd this in the email thread, but it's not showing up in the phabricator review for some reason. Also, LGTM by me as well.

lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceResults::getCallSiteDependencyFrom(
 
   // No dependence found.  If this is the entry block of the function, it is
   // unknown, otherwise it is non-local.
   if (BB != &BB->getParent()->getEntryBlock())
     return MemDepResult::getNonLocal();
   return MemDepResult::getNonFuncLocal();
 }
 
-/// Return true if LI is a load that would fully overlap MemLoc if done as
-/// a wider legal integer load.
-///
-/// MemLocBase, MemLocOffset are lazily computed here the first time the
-/// base/offs of memloc is needed.
-static bool isLoadLoadClobberIfExtendedToFullWidth(const MemoryLocation &MemLoc,
-                                                   const Value *&MemLocBase,
-                                                   int64_t &MemLocOffs,
-                                                   const LoadInst *LI) {
-  const DataLayout &DL = LI->getModule()->getDataLayout();
-
-  // If we haven't already computed the base/offset of MemLoc, do so now.
-  if (!MemLocBase)
-    MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL);
-
-  unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
-      MemLocBase, MemLocOffs, MemLoc.Size, LI);
-  return Size != 0;
-}
-
 unsigned MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
     const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize,
     const LoadInst *LI) {
   // We can only extend simple integer loads.
   if (!isa<IntegerType>(LI->getType()) || !LI->isSimple())
     return 0;
 
   // Load widening is hostile to ThreadSanitizer: it may cause false positives
while (!LoadOperandsQueue.empty()) {
     }
   }
   return Result;
 }
 
 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
     BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
-
-  const Value *MemLocBase = nullptr;
-  int64_t MemLocOffset = 0;
   bool isInvariantLoad = false;
 
   if (!Limit) {
     unsigned DefaultLimit = BlockScanLimit;
     return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst,
                                           &DefaultLimit);
   }
 
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
       }
 
       MemoryLocation LoadLoc = MemoryLocation::get(LI);
 
       // If we found a pointer, check if it could be the same as our pointer.
       AliasResult R = AA.alias(LoadLoc, MemLoc);
 
       if (isLoad) {
-        if (R == NoAlias) {
-          // If this is an over-aligned integer load (for example,
-          // "load i8* %P, align 4") see if it would obviously overlap with the
-          // queried location if widened to a larger load (e.g. if the queried
-          // location is 1 byte at P+1).  If so, return it as a load/load
-          // clobber result, allowing the client to decide to widen the load if
-          // it wants to.
-          if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) {
-            if (LI->getAlignment() * 8 > ITy->getPrimitiveSizeInBits() &&
-                isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
-                                                       MemLocOffset, LI))
-              return MemDepResult::getClobber(Inst);
-          }
+        if (R == NoAlias)
           continue;
-        }
 
         // Must aliased loads are defs of each other.
         if (R == MustAlias)
           return MemDepResult::getDef(Inst);
 
 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
       // in terms of clobbering loads, but since it does this by looking
       // at the clobbering load directly, it doesn't know about any

test/Instrumentation/AddressSanitizer/asan-vs-gvn.ll

 ; CHECK: end_test_widening_bad
 }
 
 define void @end_test_widening_bad() {
   entry:
   ret void
 }
 
-;; Accessing bytes 4 and 5. Ok to widen to i16.
+;; Accessing bytes 4 and 5. No widen to i16.
 
 define i32 @test_widening_ok(i8* %P) nounwind ssp noredzone sanitize_address {
 entry:
   %tmp = load i8, i8* getelementptr inbounds (%struct_of_7_bytes_4_aligned, %struct_of_7_bytes_4_aligned* @f, i64 0, i32 1), align 4
   %conv = zext i8 %tmp to i32
   %tmp1 = load i8, i8* getelementptr inbounds (%struct_of_7_bytes_4_aligned, %struct_of_7_bytes_4_aligned* @f, i64 0, i32 2), align 1
   %conv2 = zext i8 %tmp1 to i32
   %add = add nsw i32 %conv, %conv2
   ret i32 %add
 ; CHECK: @test_widening_ok
-; CHECK: __asan_report_load2
+; CHECK: __asan_report_load1
+; CHECK: __asan_report_load1
 ; CHECK-NOT: __asan_report
 ; CHECK: end_test_widening_ok
 }
 
 define void @end_test_widening_ok() {
   entry:
   ret void
 }

test/Transforms/GVN/PRE/load-pre-nonlocal.ll

for.cond.for.end_crit_edge:
   br label %for.end
 
 for.end:
   %s.0.lcssa = phi i32 [ %add.lcssa, %for.cond.for.end_crit_edge ], [ 0, %entry ]
   ret i32 %s.0.lcssa
 }
 
 ; %1 is partially redundant if %0 can be widened to a 64-bit load.
+; But we should not widen %0 to 64-bit load.
 
 ; CHECK-LABEL: define i32 @overaligned_load
 ; CHECK: if.then:
-; CHECK:   %0 = load i64
-; CHECK:   [[LSHR:%[0-9]+]] = lshr i64 %0, 32, !dbg [[LSHR_LOC:![0-9]+]]
-; CHECK:   trunc i64 [[LSHR]] to i32
+; CHECK-NOT:   %0 = load i64
+; CHECK-NOT:   [[LSHR:%[0-9]+]] = lshr i64 %0, 32, !dbg [[LSHR_LOC:![0-9]+]]
+; CHECK-NOT:   trunc i64 [[LSHR]] to i32
 ; CHECK: if.end:
-; CHECK-NOT: %1 = load i32, i32*
-; CHECK: [[LSHR_LOC]] = !DILocation(line: 101, column: 1, scope: !{{.*}})
+; CHECK: %1 = load i32, i32*
+; CHECK-NOT: [[LSHR_LOC]] = !DILocation(line: 101, column: 1, scope: !{{.*}})
 
 define i32 @overaligned_load(i32 %a, i32* nocapture %b) !dbg !13 {
 entry:
   %cmp = icmp sgt i32 %a, 0, !dbg !14
   br i1 %cmp, label %if.then, label %if.else, !dbg !14
 
 if.then:
   %0 = load i32, i32* getelementptr inbounds (%struct.S1, %struct.S1* @s1, i64 0, i32 0), align 8, !tbaa !5, !dbg !15

test/Transforms/GVN/PRE/rle.ll

 ; TEMPORARILY_DISABLED-LABEL: @load_load_partial_alias_cross_block(
 ; TEMPORARILY_DISABLED: land.lhs.true:
 ; TEMPORARILY_DISABLED-NOT: load i8
 ; TEMPORARILY_DISABLED: ret i32 %conv6
 }
 
 
 ;;===----------------------------------------------------------------------===;;
 ;; Load Widening
+;; We explicitly choose NOT to widen. And are testing to make sure we don't.
 ;;===----------------------------------------------------------------------===;;
 
 %widening1 = type { i32, i8, i8, i8, i8 }
 
 @f = global %widening1 zeroinitializer, align 4
 
 define i32 @test_widening1(i8* %P) nounwind ssp noredzone {
 entry:
   %tmp = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 1), align 4
   %conv = zext i8 %tmp to i32
   %tmp1 = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 2), align 1
   %conv2 = zext i8 %tmp1 to i32
   %add = add nsw i32 %conv, %conv2
   ret i32 %add
 ; CHECK-LABEL: @test_widening1(
 ; CHECK-NOT: load
-; CHECK: load i16, i16*
+; CHECK: load i8, i8*
+; CHECK: load i8, i8*
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
 define i32 @test_widening2() nounwind ssp noredzone {
 entry:
   %tmp = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 1), align 4
   %conv = zext i8 %tmp to i32
   %tmp1 = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 2), align 1
   %conv2 = zext i8 %tmp1 to i32
   %add = add nsw i32 %conv, %conv2
 
   %tmp2 = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 3), align 2
   %conv3 = zext i8 %tmp2 to i32
   %add2 = add nsw i32 %add, %conv3
 
   %tmp3 = load i8, i8* getelementptr inbounds (%widening1, %widening1* @f, i64 0, i32 4), align 1
   %conv4 = zext i8 %tmp3 to i32
   %add3 = add nsw i32 %add2, %conv3
 
   ret i32 %add3
 ; CHECK-LABEL: @test_widening2(
 ; CHECK-NOT: load
-; CHECK: load i32, i32*
+; CHECK: load i8, i8*
+; CHECK: load i8, i8*
+; CHECK: load i8, i8*
+; CHECK: load i8, i8*
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
 declare void @llvm.memcpy.p0i8.p1i8.i64(i8* nocapture, i8 addrspace(1)* nocapture, i64, i32, i1) nounwind

test/Transforms/GVN/big-endian.ll

 ; RUN: opt -gvn -S < %s | FileCheck %s
 
 target datalayout = "E-m:e-i64:64-n32:64"                                                                                         
 target triple = "powerpc64-unknown-linux-gnu"                                                                                     
 
 ;; Make sure we use correct bit shift based on storage size for
 ;; loads reusing a load value.
 define i64 @test1({ i1, i8 }* %predA, { i1, i8 }* %predB) {
 ; CHECK-LABEL: @test1
-; CHECK: [[V1:%.*]] = load i16, i16* %{{.*}}
-; CHECK: [[V2:%.*]] = lshr i16 [[V1]], 8
-; CHECK: trunc i16 [[V2]] to i1
+; CHECK-NOT: [[V1:%.*]] = load i16, i16* %{{.*}}
+; CHECK-NOT: [[V2:%.*]] = lshr i16 [[V1]], 8
+; CHECK-NOT: trunc i16 [[V2]] to i1
 
   %valueLoadA.fca.0.gep = getelementptr inbounds { i1, i8 }, { i1, i8 }* %predA, i64 0, i32 0
   %valueLoadA.fca.0.load = load i1, i1* %valueLoadA.fca.0.gep, align 8
   %valueLoadB.fca.0.gep = getelementptr inbounds { i1, i8 }, { i1, i8 }* %predB, i64 0, i32 0
   %valueLoadB.fca.0.load = load i1, i1* %valueLoadB.fca.0.gep, align 8
   %isTrue = and i1 %valueLoadA.fca.0.load, %valueLoadB.fca.0.load
   %valueLoadA.fca.1.gep = getelementptr inbounds { i1, i8 }, { i1, i8 }* %predA, i64 0, i32 1
   %valueLoadA.fca.1.load = load i8, i8* %valueLoadA.fca.1.gep, align 1

test/Transforms/GVN/no_speculative_loads_with_asan.ll

; <label>:6                                       ; preds = %0
   br label %11
 
 ; <label>:11                                      ; preds = %0, %6
   %12 = phi i32 [ %10, %6 ], [ 0, %0 ]
   ret i32 %12
 }
 
 ; CHECK-LABEL: @TestNoAsan
-; CHECK: %[[LOAD:[^ ]+]] = load i32
-; CHECK: {{.*}} = ashr i32 %[[LOAD]]
-; CHECK-NOT: {{.*}} = phi
+; CHECK: ret i32 0
 
 define i32 @TestAsan() sanitize_address {
   %1 = tail call noalias i8* @_Znam(i64 2)
   %2 = getelementptr inbounds i8, i8* %1, i64 1
   store i8 0, i8* %2, align 1
   store i8 0, i8* %1, align 1
   %3 = bitcast i8* %1 to i16*
   %4 = load i16, i16* %3, align 4

test/Transforms/GVN/pr25440.ll

 entry:
   br label %bb0
 
 bb0:                                      ; preds = %land.lhs.true, %entry
 ;CHECK: bb0:
   %x.tr = phi %struct.a* [ %x, %entry ], [ null, %land.lhs.true ]
   %code1 = getelementptr inbounds %struct.a, %struct.a* %x.tr, i32 0, i32 0
   %0 = load i16, i16* %code1, align 4
-; CHECK: load i32, i32*
+; CHECK: load i16, i16*
   %conv = zext i16 %0 to i32
   switch i32 %conv, label %if.end.50 [
     i32 43, label %cleanup
     i32 52, label %if.then.5
   ]
 
 if.then.5:                                        ; preds = %bb0
   br i1 undef, label %land.lhs.true, label %if.then.26
 
 land.lhs.true:                                    ; preds = %if.then.5
   br i1 undef, label %cleanup, label %bb0
 
 if.then.26:                                       ; preds = %if.then.5
   %x.tr.lcssa163 = phi %struct.a* [ %x.tr, %if.then.5 ]
   br i1 undef, label %cond.end, label %cond.false
 
 cond.false:                                       ; preds = %if.then.26
 ; CHECK: cond.false:
-; CHECK-NOT: load
+; CHECK: load i16
   %mode = getelementptr inbounds %struct.a, %struct.a* %x.tr.lcssa163, i32 0, i32 1
   %bf.load = load i16, i16* %mode, align 2
   %bf.shl = shl i16 %bf.load, 8
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %if.then.26
   br i1 undef, label %if.then.44, label %cleanup