[Loads] Skip non load/store instructions when finding available load

[tejohnson]

Summary

Detect and skip non load and store instructions, up to a limit,
when finding available loads for a pointer. The scan limit is only 6
instructions which is fairly small, so for example type test and assume
intrinsics inserted for whole program devirtualization would prevent
analysis, sometimes causing profile matching issues. On the other hand,
debug and pseudo instructions were skipped indefinitely.

We now skip all of the unrelated instruction types when scanning for an
available load or intervening memory write, up to a default limit of 32
instructions. This supercedes the unlimited skipping of debug and pseudo
instructions that previously existed.

This exposed an issue where a caller from jump threading could end up
infinitely looping due to an unreachable loop with a single predecessor
(the backedge). It was not exposed before because the branch instruction
was counted towards the scan limit of 6 instructions, so iteration would
terminate. Fix this and added a test case.

[nikic]

Not a big fan of this -- this is effectively whitelisting a specific pattern, and doesn't generalize.

For this code, there are two limits of interest: The total number of instructions we look at, and the number of alias-analysis queries we perform. Currently we limit both through a small number of total instructions. However, the only expensive part, and what needs to be aggressively limited, is the number of alias analysis queries.

I think what we can do here is to have a relatively liberal upper limit on the number of scanned instructions (say 32), while having a tight limit on the number of AA queries or AA query candidates (say 4). This should make the code more resilient against additional bitcast/assume instructions in between, while still limiting compile-time impact.

Do you think something along those lines would address your motivation here?

[tejohnson]

In D101553#2726674, @nikic wrote:

Not a big fan of this -- this is effectively whitelisting a specific pattern, and doesn't generalize.

For this code, there are two limits of interest: The total number of instructions we look at, and the number of alias-analysis queries we perform. Currently we limit both through a small number of total instructions. However, the only expensive part, and what needs to be aggressively limited, is the number of alias analysis queries.

There's sort of 3 categories of instructions from what I can tell, in increasing order of expense:

1. Insts that are not loads or stores and don't modify memory - these can be skipped immediately
2. Loads and stores which are compared to the given pointer by comparing the pointer values but not with AA (in getAvailableLoadStore)
3. (Subset of category 2) Instructions that are compared using AA analysis (insts that may write memory)

I think what we can do here is to have a relatively liberal upper limit on the number of scanned instructions (say 32), while having a tight limit on the number of AA queries or AA query candidates (say 4). This should make the code more resilient against additional bitcast/assume instructions in between, while still limiting compile-time impact.

Do you think something along those lines would address your motivation here?

It would help, but we could still end up with corner cases where with -fwhole-program-vtables enabled for the optimization build we might end up with IR profile matching issues due to different simplification optimizations prior. Although with a larger window the chances of that would presumably be reduced.

One thing I am wondering is whether for the first category above (non load/store/may write memory), if there needs to be any limit since they can be skipped immediately (e.g. instead of just dbg or pseudo insts as it does now). I am not sure how expensive it would be to allow quickly skipping through all of them in the block as we scan for memory accesses. I did some measurements for a large binary build with ~20k input files. With that change, essentially to convert:

if (isa<DbgInfoIntrinsic>(Inst))
  continue;

to

if (!isa<LoadInst>(&Inst) && !isa<StoreInst>(&Inst) && !Inst.mayWriteToMemory())
  continue;

across all the input files there are about 40% more iterations of the loop in findAvailablePtrLoadStore and about 47% more iterations in FindAvailableLoadedValue. I left the existing default scan limit of 6 for the loads/stores/maywrite insts, so these were largely just skipping through without any analysis. I didn't compare the compile times of all of the individual files in detail, but the slowest compiling files did not increase in compile time nor did the overall build.

If that isn't acceptable, perhaps a larger limit such as 100? Note this could either subsume the existing unlimited skipping of dbg and pseudo instructions, or allow those to be skipped unconditionally as now. Right now with the current skipping of all dbg and pseudo instructions, the max iteration of this loop is ~1K, so if we include those instructions in the limit it will have a potentially negative effect on optimization over the status quo.

[Prazek]

llvm/lib/Analysis/Loads.cpp

633–643

nit: This comment (which is very useful) is a big duplication in code.
What do you think of wrapping this chunk of code to a function, so that either logic, or the comment will not get out of sync?
Something like:

if (isUnrelatedToLoadOrStore(Inst)) // Probably could be named better.
  continue;

[tejohnson]

llvm/lib/Analysis/Loads.cpp

633–643

I ended up simplifying this code which meant it no longer required a big comment about these particular instruction types.

[tejohnson]

Update patch as discussed, to skip a larger number of non ld/st instructions

[tejohnson]

ping

[tejohnson]

In D101553#2726674, @nikic wrote:

Not a big fan of this -- this is effectively whitelisting a specific pattern, and doesn't generalize.

For this code, there are two limits of interest: The total number of instructions we look at, and the number of alias-analysis queries we perform. Currently we limit both through a small number of total instructions. However, the only expensive part, and what needs to be aggressively limited, is the number of alias analysis queries.

I think what we can do here is to have a relatively liberal upper limit on the number of scanned instructions (say 32), while having a tight limit on the number of AA queries or AA query candidates (say 4). This should make the code more resilient against additional bitcast/assume instructions in between, while still limiting compile-time impact.

Do you think something along those lines would address your motivation here?

@nikic ping, I believe I implemented your suggested alternative, ptal

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/include/llvm/IR/IntrinsicInst.h

public:
   static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::assume;
   }
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
+/// This represents the llvm.type.test intrinsic.
+class TypeTestInst : public IntrinsicInst {
+public:
+  static bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::type_test;
+  }
+  static bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_IR_INTRINSICINST_H

llvm/lib/Analysis/Loads.cpp

Value *llvm::findAvailablePtrLoadStore(
 
   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
   const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
 
   while (ScanFrom != ScanBB->begin()) {
     // We must ignore debug info directives when counting (otherwise they
     // would affect codegen).
     Instruction *Inst = &*--ScanFrom;
-    if (Inst->isDebugOrPseudoInst())
+    // Ignore unrelated instruction types that in particular may only be
+    // inserted under special compile modes. The scan limit is set quite small
+    // (6 instructions) by default, so these can have an outsized effect on this
+    // optimization. Additionally, if these instructions are only applied when
+    // feeding back instrumentation PGO, different optimization can affect
+    // matching. Specifically, it is not uncommon to apply -g or whole program
+    // devirtualization (which results in bitcast / llvm.type.test / llvm.assume
+    // sequences) only when feeding back profiles and not for the
+    // instrumentation build.
+    if (Inst->isDebugOrPseudoInst() || isa<AssumeInst>(Inst) ||
+        isa<TypeTestInst>(Inst) || isa<BitCastInst>(Inst))
       continue;
 
     // Restore ScanFrom to expected value in case next test succeeds
     ScanFrom++;
 
     if (NumScanedInst)
       ++(*NumScanedInst);
 
if (!Load->isUnordered())
     return nullptr;
 
   // Try to find an available value first, and delay expensive alias analysis
   // queries until later.
   Value *Available = nullptr;;
   SmallVector<Instruction *> MustNotAliasInsts;
   for (Instruction &Inst : make_range(++Load->getReverseIterator(),
                                       ScanBB->rend())) {
-    if (Inst.isDebugOrPseudoInst())
+    // Ignore unrelated instruction types that in particular may only be
+    // inserted under special compile modes. The scan limit is set quite small
+    // (6 instructions) by default, so these can have an outsized effect on this
+    // optimization. Additionally, if these instructions are only applied when
+    // feeding back instrumentation PGO, different optimization can affect
+    // matching. Specifically, it is not uncommon to apply -g or whole program
+    // devirtualization (which results in bitcast / llvm.type.test / llvm.assume
+    // sequences) only when feeding back profiles and not for the
+    // instrumentation build.
+    if (Inst.isDebugOrPseudoInst() || isa<AssumeInst>(&Inst) ||
+        isa<TypeTestInst>(&Inst) || isa<BitCastInst>(&Inst))
       continue;
 
     if (MaxInstsToScan-- == 0)
       return nullptr;
 
     Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,
                                       AtLeastAtomic, DL, IsLoadCSE);
     if (Available)

llvm/test/Transforms/InstCombine/load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -instcombine -S < %s | FileCheck %s
-; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+; Set available-load-scan-limit to the current default of 6 so that the test
+; works the same if the limit is adjusted in the future.
+; RUN: opt -instcombine -available-load-scan-limit=6 -S < %s | FileCheck %s
+; RUN: opt -passes=instcombine -available-load-scan-limit=6 -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-p:64:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 @X = constant i32 42    ; <i32*> [#uses=2]
 @X2 = constant i32 47   ; <i32*> [#uses=1]
 @Y = constant [2 x { i32, float }] [ { i32, float } { i32 12, float 1.000000e+00 }, { i32, float } { i32 37, float 0x3FF3B2FEC0000000 } ]    ; <[2 x { i32, float }]*> [#uses=2]
 @Z = constant [2 x { i32, float }] zeroinitializer    ; <[2 x { i32, float }]*> [#uses=1]
 

 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    ret i32 1
 ;
   store i32 1, i32* %P
   %X = load i32, i32* %P    ; <i32> [#uses=1]
   ret i32 %X
 }
 
+declare void @llvm.assume(i1)
+declare i1 @llvm.type.test(i8*, metadata) nounwind readnone
+
+; Ensure that load store forwarding not prevented by the bitcast / type test /
+; assume sequences inserted for whole program devirtualization.
+define i32 @test8_type_test_assume(i32* %P, [3 x i8*]* %vtable) {
+; CHECK-LABEL: @test8_type_test_assume(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    bitcast [3 x i8*]* %vtable to i8*
+; CHECK-NEXT:    call i1 @llvm.type.test
+; CHECK-NEXT:    call void @llvm.assume
+; CHECK-NEXT:    bitcast [3 x i8*]* %vtable to i8*
+; CHECK-NEXT:    call i1 @llvm.type.test
+; CHECK-NEXT:    call void @llvm.assume
+; CHECK-NEXT:    ret i32 1
+;
+  store i32 1, i32* %P
+
+  ; Insert 2 bitcast / type test / assume sequences so that we would be above
+  ; the scan limit of 6 if they were not ignored.
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"foo")
+  tail call void @llvm.assume(i1 %p)
+  %vtablei82 = bitcast [3 x i8*]* %vtable to i8*
+  %p2 = call i1 @llvm.type.test(i8* %vtablei82, metadata !"foo")
+  tail call void @llvm.assume(i1 %p2)
+
+  %X = load i32, i32* %P    ; <i32> [#uses=1]
+  ret i32 %X
+}
+
 define i32 @test9(i32* %P) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:    ret i32 0
 ;
   %X = load i32, i32* %P    ; <i32> [#uses=1]
   %Y = load i32, i32* %P    ; <i32> [#uses=1]
   %Z = sub i32 %X, %Y   ; <i32> [#uses=1]
   ret i32 %Z

llvm/test/Transforms/JumpThreading/thread-loads.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -jump-threading -S | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes=jump-threading -S | FileCheck %s
+; Set available-load-scan-limit to the current default of 6 so that the test
+; works the same if the limit is adjusted in the future.
+; RUN: opt < %s -jump-threading -available-load-scan-limit=6 -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes=jump-threading -available-load-scan-limit=6 -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"
 target triple = "i386-apple-darwin7"
 
 ; Test that we can thread through the block with the partially redundant load (%2).
 ; rdar://6402033
 define i32 @test1(i32* %P) nounwind {
 ; CHECK-LABEL: @test1(

 
 left_x:
   ret i32 20
 
 right_x:
   ret i32 10
 }
 
+declare void @llvm.assume(i1)
+declare i1 @llvm.type.test(i8*, metadata) nounwind readnone
+
+; Test that we can thread through the block with the partially redundant load (%2),
+; ensuring that the threading is not prevented by the bitcast / type test /
+; assume sequences inserted for whole program devirtualization.
+define i32 @test1_type_test_assume(i32* %P, [3 x i8*]* %vtable) nounwind {
+; CHECK-LABEL: @test1_type_test_assume(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = tail call i32 (...) @f1() #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BB1:%.*]], label [[BB1_THREAD:%.*]]
+; CHECK:       bb1.thread:
+; CHECK-NEXT:    store i32 42, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    bitcast [3 x i8*]* %vtable to i8*
+; CHECK-NEXT:    call i1 @llvm.type.test
+; CHECK-NEXT:    call void @llvm.assume
+; CHECK-NEXT:    bitcast [3 x i8*]* %vtable to i8*
+; CHECK-NEXT:    call i1 @llvm.type.test
+; CHECK-NEXT:    call void @llvm.assume
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[DOTPR:%.*]] = load i32, i32* [[P]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[DOTPR]], 36
+; CHECK-NEXT:    br i1 [[TMP2]], label [[BB3]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 (...) @f2() #[[ATTR0]]
+; CHECK-NEXT:    ret i32 0
+; CHECK:       bb3:
+; CHECK-NEXT:    [[RES_02:%.*]] = phi i32 [ 1, [[BB1_THREAD]] ], [ 0, [[BB1]] ]
+; CHECK-NEXT:    ret i32 [[RES_02]]
+;
+entry:
+  %0 = tail call i32 (...) @f1() nounwind    ; <i32> [#uses=1]
+  %1 = icmp eq i32 %0, 0    ; <i1> [#uses=1]
+  br i1 %1, label %bb1, label %bb
+
+bb:   ; preds = %entry
+  store i32 42, i32* %P, align 4
+
+  ; Insert 2 bitcast / type test / assume sequences so that we would be above
+  ; the scan limit of 6 if they were not ignored.
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"foo")
+  tail call void @llvm.assume(i1 %p)
+  %vtablei82 = bitcast [3 x i8*]* %vtable to i8*
+  %p2 = call i1 @llvm.type.test(i8* %vtablei82, metadata !"foo")
+  tail call void @llvm.assume(i1 %p2)
+
+  br label %bb1
+
+bb1:    ; preds = %entry, %bb
+  %res.0 = phi i32 [ 1, %bb ], [ 0, %entry ]    ; <i32> [#uses=2]
+  %2 = load i32, i32* %P, align 4    ; <i32> [#uses=1]
+  %3 = icmp sgt i32 %2, 36    ; <i1> [#uses=1]
+  br i1 %3, label %bb3, label %bb2
+
+bb2:    ; preds = %bb1
+  %4 = tail call i32 (...) @f2() nounwind    ; <i32> [#uses=0]
+  ret i32 %res.0
+
+bb3:    ; preds = %bb1
+  ret i32 %res.0
+}
 
 ; CHECK: [[RNG4]] = !{i32 0, i32 1}
 
 !0 = !{!3, !3, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"int", !1}
 !4 = !{ i32 0, i32 1 }
 !5 = !{ i32 8, i32 10 }
 !6 = !{!6}
 !7 = !{!7, !6}
 !8 = !{!8, !6}
 !9 = !{!7}
 !10 = !{!8}