[MergeICmps] Ignore clobbering instructions before the loads

[nikic]

Summary

This is another followup to D106591. Even if there is an instruction that clobbers one of the loads, this doesn't matter if it happens before the loads. Those instructions aren't affected by the transform at all.

The gep-references-bb.ll is modified to preserve the spirit of the test, as the store @g no longer impacts the transform.

[courbet]

Nice, thanks!

llvm/test/Transforms/MergeICmps/X86/split-block-does-work.ll

144

happens*

[pcc]

Looks like this change caused this crash, can you please take a look?

$ cat test.ii
class a {
public:
  enum b {};
  struct c {
    b j;
    int *d;
    void *e;
  };
};
class f {
  bool operator==(const f &) const;
  a::c g() const;
};
bool f::operator==(const f &) const {
  a::c h = g(), i = g();
  return h.e == i.e && h.d == i.d && h.j == i.j;
}
$ clang++ -c  -o test.o test.ii -O2
Instruction does not dominate all uses!
  %h = alloca %"struct.a::c", align 8
  %1 = bitcast %"struct.a::c"* %h to i32*
Instruction does not dominate all uses!
  %i = alloca %"struct.a::c", align 8
  %2 = bitcast %"struct.a::c"* %i to i32*
Instruction does not dominate all uses!
  %i = alloca %"struct.a::c", align 8
  %18 = bitcast %"struct.a::c"* %i to i8*
Instruction does not dominate all uses!
  %h = alloca %"struct.a::c", align 8
  %19 = bitcast %"struct.a::c"* %h to i8*
in function _ZNK1feqERKS_
fatal error: error in backend: Broken function found, compilation aborted!

[nikic]

Thanks for the report! This seems to have exposed a pre-existing problem. Here's a variant that fails also prior to this patch (note the commented init calls):

target triple = "x86_64-unknown-linux-gnu"

%"struct.a::c" = type { i32, i32*, i8* }

define i1 @test() {
entry:
  %h = alloca %"struct.a::c", align 8
  %i = alloca %"struct.a::c", align 8
  ;call void @init(%"struct.a::c"* %h)
  ;call void @init(%"struct.a::c"* %i)
  %e = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %h, i64 0, i32 2
  %v3 = load i8*, i8** %e, align 8
  %e2 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %i, i64 0, i32 2
  %v4 = load i8*, i8** %e2, align 8
  %cmp = icmp eq i8* %v3, %v4
  br i1 %cmp, label %land.lhs.true, label %land.end

land.lhs.true:                                    ; preds = %entry
  %d = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %h, i64 0, i32 1
  %v5 = load i32*, i32** %d, align 8
  %d3 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %i, i64 0, i32 1
  %v6 = load i32*, i32** %d3, align 8
  %cmp4 = icmp eq i32* %v5, %v6
  br i1 %cmp4, label %land.rhs, label %land.end

land.rhs:                                         ; preds = %land.lhs.true
  %j = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %h, i64 0, i32 0
  %v7 = load i32, i32* %j, align 8
  %j5 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %i, i64 0, i32 0
  %v8 = load i32, i32* %j5, align 8
  %cmp6 = icmp eq i32 %v7, %v8
  br label %land.end

land.end:                                         ; preds = %land.rhs, %land.lhs.true, %entry
  %v9 = phi i1 [ false, %land.lhs.true ], [ false, %entry ], [ %cmp6, %land.rhs ]
  ret i1 %v9
}

declare void @init(%"struct.a::c"*)

The result of the transform looks like this:

define i1 @test() {
land.rhs2:
  %0 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %h, i64 0, i32 0
  %1 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %i, i64 0, i32 0
  %2 = load i32, i32* %0, align 4
  %3 = load i32, i32* %1, align 4
  %4 = icmp eq i32 %2, %3
  br i1 %4, label %"land.lhs.true+entry", label %land.end

"land.lhs.true+entry":                            ; preds = %land.rhs2
  %h = alloca %"struct.a::c", align 8
  %i = alloca %"struct.a::c", align 8
  %5 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %h, i64 0, i32 1
  %6 = getelementptr inbounds %"struct.a::c", %"struct.a::c"* %i, i64 0, i32 1
  %cstr = bitcast i32** %5 to i8*
  %cstr1 = bitcast i32** %6 to i8*
  %memcmp = call i32 @memcmp(i8* %cstr, i8* %cstr1, i64 16)
  %7 = icmp eq i32 %memcmp, 0
  br label %land.end

land.end:                                         ; preds = %land.rhs2, %"land.lhs.true+entry"
  %v9 = phi i1 [ %7, %"land.lhs.true+entry" ], [ false, %land.rhs2 ]
  ret i1 %v9
}

The comparison at offset 0 doesn't get merged as it's non-contiguous, but for some reason it also gets moved to the start, such that the allocas are effectively sunk,

llvm/lib/Transforms/Scalar/MergeICmps.cpp

private:
   BCECmp Cmp;
 };
 
 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
                                     AliasAnalysis &AA) const {
   // If this instruction may clobber the loads and is in middle of the BCE cmp
   // block instructions, then bail for now.
   if (Inst->mayWriteToMemory()) {
-    // Disallow instructions that might modify the BCE operands
-    MemoryLocation LLoc = MemoryLocation::get(Cmp.Lhs.LoadI);
-    MemoryLocation RLoc = MemoryLocation::get(Cmp.Rhs.LoadI);
-    if (isModSet(AA.getModRefInfo(Inst, LLoc)) ||
-        isModSet(AA.getModRefInfo(Inst, RLoc)))
+    auto MayClobber = [&](LoadInst *LI) {
+      // If a potentially clobbering instruction comes before the load,
+      // we can still safely sink the load.
+      return !Inst->comesBefore(LI) &&
+             isModSet(AA.getModRefInfo(Inst, MemoryLocation::get(LI)));
+    };
+    if (MayClobber(Cmp.Lhs.LoadI) || MayClobber(Cmp.Rhs.LoadI))
       return false;
   }
   // Make sure this instruction does not use any of the BCE cmp block
   // instructions as operand.
   return llvm::none_of(Inst->operands(), [&](const Value *Op) {
     const Instruction *OpI = dyn_cast<Instruction>(Op);
     return OpI && BlockInsts.contains(OpI);
   });

llvm/test/Transforms/MergeICmps/X86/gep-references-bb.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -mergeicmps -verify-dom-info | FileCheck %s
 target triple = "x86_64"
 
 %Triple = type { i32, i32, i32, i32 }
 
 @g = external global i32
 
 ; bb1 references a gep introduced in bb0. The gep must remain available after
 ; the merge.
 define i1 @bug(%Triple* nonnull dereferenceable(16) %lhs, %Triple* nonnull dereferenceable(16) %rhs) nofree nosync {
 ; CHECK-LABEL: @bug(
 ; CHECK-NEXT:  bb0:
-; CHECK-NEXT:    store i32 1, i32* @g, align 4
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [[TRIPLE:%.*]], %Triple* [[RHS:%.*]], i64 0, i32 0
 ; CHECK-NEXT:    [[L0_ADDR:%.*]] = getelementptr inbounds [[TRIPLE]], %Triple* [[LHS:%.*]], i64 0, i32 0
 ; CHECK-NEXT:    [[L0:%.*]] = load i32, i32* [[L0_ADDR]], align 4
 ; CHECK-NEXT:    [[R0_ADDR:%.*]] = getelementptr inbounds [[TRIPLE]], %Triple* [[RHS]], i64 0, i32 0
 ; CHECK-NEXT:    [[R0:%.*]] = load i32, i32* [[R0_ADDR]], align 4
+; CHECK-NEXT:    store i32 1, i32* @g, align 4
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp eq i32 [[L0]], [[R0]]
 ; CHECK-NEXT:    br i1 [[CMP0]], label %"bb1+bb2", label [[FINAL:%.*]]
 ; CHECK:       "bb1+bb2":
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds [[TRIPLE]], %Triple* [[LHS]], i64 0, i32 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i32, i32* [[GEP]], i64 2
 ; CHECK-NEXT:    [[CSTR:%.*]] = bitcast i32* [[TMP0]] to i8*
 ; CHECK-NEXT:    [[CSTR1:%.*]] = bitcast i32* [[TMP1]] to i8*
 ; CHECK-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[CSTR]], i8* [[CSTR1]], i64 8)
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[MEMCMP]], 0
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
 ; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ false, [[BB0:%.*]] ], [ [[TMP2]], %"bb1+bb2" ]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;
 bb0:
-  store i32 1, i32* @g
   %gep = getelementptr %Triple, %Triple* %rhs, i64 0, i32 0
   %l0_addr = getelementptr inbounds %Triple, %Triple* %lhs, i64 0, i32 0
   %l0 = load i32, i32* %l0_addr, align 4
   %r0_addr = getelementptr inbounds %Triple, %Triple* %rhs, i64 0, i32 0
   %r0 = load i32, i32* %r0_addr, align 4
+  store i32 1, i32* @g
   %cmp0 = icmp eq i32 %l0, %r0
   br i1 %cmp0, label %bb1, label %final
 
 bb1:                                           ; preds = %bb0
   %l1_addr = getelementptr inbounds %Triple, %Triple* %lhs, i64 0, i32 2
   %l1 = load i32, i32* %l1_addr, align 4
   %r1_addr = getelementptr inbounds i32, i32* %gep, i64 2
   %r1 = load i32, i32* %r1_addr, align 4

llvm/test/Transforms/MergeICmps/X86/split-block-does-work.ll

land.rhs.i.3:
   %cmp4.i = icmp eq i32 %6, %7
   br label %opeq1.exit
 
 opeq1.exit:
   %8 = phi i1 [ false, %entry ], [ false, %land.rhs.i] , [ false, %land.rhs.i.2 ], [ %cmp4.i, %land.rhs.i.3 ]
   ret i1 %8
 }
 
-; TODO: The call happen before the loads, so it cannot clobber them.
+; The call happens before the loads, so it cannot clobber them.
 define zeroext i1 @opeq1_call_before_loads(
 ; X86-LABEL: @opeq1_call_before_loads(
-; X86-NEXT:  entry:
+; X86-NEXT:  "entry+land.rhs.i+land.rhs.i.2+land.rhs.i.3":
 ; X86-NEXT:    call void (...) @foo()
-; X86-NEXT:    [[FIRST_I:%.*]] = getelementptr inbounds [[S:%.*]], %S* [[A:%.*]], i64 0, i32 0
-; X86-NEXT:    [[TMP0:%.*]] = load i32, i32* [[FIRST_I]], align 4
-; X86-NEXT:    [[FIRST1_I:%.*]] = getelementptr inbounds [[S]], %S* [[B:%.*]], i64 0, i32 0
-; X86-NEXT:    [[TMP1:%.*]] = load i32, i32* [[FIRST1_I]], align 4
-; X86-NEXT:    [[CMP_I:%.*]] = icmp eq i32 [[TMP0]], [[TMP1]]
-; X86-NEXT:    br i1 [[CMP_I]], label %"land.rhs.i+land.rhs.i.2+land.rhs.i.3", label [[OPEQ1_EXIT:%.*]]
-; X86:       "land.rhs.i+land.rhs.i.2+land.rhs.i.3":
-; X86-NEXT:    [[TMP2:%.*]] = getelementptr inbounds [[S]], %S* [[A]], i64 0, i32 1
-; X86-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [[S]], %S* [[B]], i64 0, i32 1
-; X86-NEXT:    [[CSTR:%.*]] = bitcast i32* [[TMP2]] to i8*
-; X86-NEXT:    [[CSTR1:%.*]] = bitcast i32* [[TMP3]] to i8*
-; X86-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[CSTR]], i8* [[CSTR1]], i64 12)
-; X86-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[MEMCMP]], 0
-; X86-NEXT:    br label [[OPEQ1_EXIT]]
+; X86-NEXT:    [[TMP0:%.*]] = getelementptr inbounds [[S:%.*]], %S* [[A:%.*]], i64 0, i32 0
+; X86-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [[S]], %S* [[B:%.*]], i64 0, i32 0
+; X86-NEXT:    [[CSTR:%.*]] = bitcast i32* [[TMP0]] to i8*
+; X86-NEXT:    [[CSTR1:%.*]] = bitcast i32* [[TMP1]] to i8*
+; X86-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[CSTR]], i8* [[CSTR1]], i64 16)
+; X86-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[MEMCMP]], 0
+; X86-NEXT:    br label [[OPEQ1_EXIT:%.*]]
 ; X86:       opeq1.exit:
-; X86-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[TMP4]], %"land.rhs.i+land.rhs.i.2+land.rhs.i.3" ]
-; X86-NEXT:    ret i1 [[TMP5]]
+; X86-NEXT:    ret i1 [[TMP2]]
 ;
 ; Make sure this call is moved to the beginning of the entry block.
   %S* nocapture readonly dereferenceable(16) %a,
   %S* nocapture readonly dereferenceable(16) %b) local_unnamed_addr nofree nosync {
 entry:
   call void (...) @foo()
   %first.i = getelementptr inbounds %S, %S* %a, i64 0, i32 0
   %0 = load i32, i32* %first.i, align 4