[InstCombin] Continue scanning loaded values through single predecessors

[junbuml]

Summary

This change allow continue scanning to find a loaded value through single predecessors, instead of being limited within the current block, while respecting the backward scan limit.

[• dberlin]

I'm going to ask the same question i did about the jumpthreading case:

This seems to be a thing other passes get, and do it cheaper.

I would rather see us *remove this code entirely* than extend it. We don't need to do everything everywhere.
The testcases given are optimizations we will get elsewhere.
If there are good reasons to do this in instcombine, great, let's test those reasons :)

[junbuml]

I also observed this change was applied pretty widely in my spec2000/2006 and had impacts on the final output code, which means the opportunities are exposed in InstCombin and they are not handled in other places in the whole pipeline; let me try to reduce such case from my spec tests. I added the testcase to describe what this patch do in instcombine itself, not to show the case which can only be handled in instcombine.

[• dberlin]

In D30004#677832, @junbuml wrote:

I also observed this change was applied pretty widely in my spec2000/2006 and had impacts on the final output code, which means the opportunities are exposed in InstCombin and they are not handled in other places in the whole pipeline;

We definitely should investigate that.
Because that is very worrying, and we should definitely fix those deficiencies. But without seeing them,i'm not sure i'd fix them in instcombine, and the general preference would be "make pass that should be catching it, catch it

let me try to reduce such case from my spec tests. I added the testcase to describe what this patch do in instcombine itself, not to show the case which can only be handled in instcombine.

Sure, but i'd like us to try to test stuff that is specific to the pass.
Otherwise, we'd even be better off unifying these tests in a single place and testing every pass that can do it.
(IE we have no reason to copy the same test 20 times in the codebase)
;)

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   if (Instruction *Res = unpackLoadToAggregate(*this, LI))
     return Res;
 
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI(LI);
   bool IsLoadCSE = false;
-  if (Value *AvailableVal = FindAvailableLoadedValue(
-          &LI, LI.getParent(), BBI, DefMaxInstsToScan, AA, &IsLoadCSE)) {
+  unsigned NumScannedInst = 0;
+  Value *AvailableVal =
+      FindAvailableLoadedValue(&LI, LI.getParent(), BBI, DefMaxInstsToScan, AA,
+                               &IsLoadCSE, &NumScannedInst);
+  // If the current block has a single predecessor, continue scanning through
+  // the single precessor.
+  BasicBlock *SinglePredBB = LI.getParent();
+  while (!AvailableVal && SinglePredBB && BBI == SinglePredBB->begin() &&
+         NumScannedInst < DefMaxInstsToScan) {
+    SinglePredBB = SinglePredBB->getSinglePredecessor();
+   if (SinglePredBB) {
+      BBI = SinglePredBB->end();
+      AvailableVal = FindAvailableLoadedValue(
+            &LI, SinglePredBB, BBI, (DefMaxInstsToScan - NumScannedInst),
+            nullptr, &IsLoadCSE, &NumScannedInst);
+    }
+  }
+
+  if (AvailableVal) {
     if (IsLoadCSE)
       combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI);
 
     return replaceInstUsesWith(
         LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
                                             LI.getName() + ".cast"));
   }
 

test/Transforms/InstCombine/2011-06-13-nsw-alloca.ll

-; RUN: opt -S -instcombine < %s | FileCheck %s
+; RUN: opt -S -instcombine -available-load-scan-limit=3 < %s | FileCheck %s
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
 target triple = "i386-apple-darwin10.0.0"
 
 ; CHECK-LABEL: define void @fu1(
 define void @fu1(i32 %parm) nounwind ssp {
   %1 = alloca i32, align 4
 ; CHECK: alloca double*
   %ptr = alloca double*, align 4

test/Transforms/InstCombine/load.ll

 entry:
   %tmp = alloca i8*, align 8
   call void @initi8(i8** %tmp)
   %swifterror = bitcast i8** %tmp to %swift.error**
   %err.res = load %swift.error*, %swift.error** %swifterror, align 8
   store %swift.error* %err.res, %swift.error** %err, align 8
   ret void
 }
+
+; Check that %ld is removed as it loads from the same location to which %a is stored in
+; %entry.
+; CHECK-LABEL: @test20(
+; CHECK-LABEL: return
+; CHECK-NOT: load
+define i32 @test20(i32* %P, i32 %a) {
+entry:
+  store i32 %a, i32 * %P
+  br label %return
+
+return:                                           ; preds = %entry
+  %ld = load i32 , i32* %P
+  ret i32 %ld
+}