[ImplicitNullCheck] Extend canReorder scope

[skatkov]

Summary

This change allows a re-order of two intructions if their uses
are overlapped.

[skatkov]

This change has been done on top of https://reviews.llvm.org/D29119 in my workspace, so in diff you can see code from that change. While the changes are not overlapped sorry for inconvinience.

[sanjoy]

Hi Serguei,

The code itself LGTM.

However:

Can you please try to write MIR test cases for this? That's typically
a more straightforward way to unit test codegen passes.
implicit-null-check.ll was added before the MIR infrastructure was
added to LLVM. You can get started with MIR at
http://llvm.org/docs/MIRLangRef.html, and may use
https://reviews.llvm.org/rL293126 as a template to write your own
test.

Secondly, phabricator tells me that you've changed the permissions on
the .ll files; please make sure you've fixed them before checkin.

[skatkov]

Sanjoy, please take a look.

[sanjoy]

lgtm, but I believe you'll also have to edit the test case I checked in in https://reviews.llvm.org/rL293126

Let me know if you want me to check this in for you. Alternatively, you can ask someone from our Saint Petersburg office.

[skatkov]

This comment was removed by skatkov.

[skatkov]

I will modify test and upload new version.

[skatkov]

The test has been updated. It becomes positive now due to extension of the scope.

[skatkov]

One more place should be fixed I guess.

lib/CodeGen/ImplicitNullChecks.cpp

370–371

I think this should be fixed as well as check only for defs. Will try to write a test today.

[skatkov]

Asssert fixed. Also one test is added. The test passes with assert fix and fails witout it.

[skatkov]

Just a rebase after isSuitable... patch is landed.

lib/CodeGen/ImplicitNullChecks.cpp

for (auto MOA : A->operands()) {
 
     unsigned RegA = MOA.getReg();
     for (auto MOB : B->operands()) {
       if (!(MOB.isReg() && MOB.getReg()))
         continue;
 
       unsigned RegB = MOB.getReg();
 
-      if (TRI->regsOverlap(RegA, RegB))
+      if (TRI->regsOverlap(RegA, RegB) && (MOA.isDef() || MOB.isDef()))
         return false;
     }
   }
 
   return true;
 }
 
 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
 
   // Finally, we need to make sure that the load instruction actually is
   // loading from PointerReg, and there isn't some re-definition of PointerReg
   // between the compare and the load.
   // If PointerReg has been redefined before then there is no sense to continue
   // lookup due to this condition will fail for any further instruction.
   for (auto *PrevMI : PrevInsts)
     for (auto &PrevMO : PrevMI->operands())
-      if (PrevMO.isReg() && PrevMO.getReg() &&
+      if (PrevMO.isReg() && PrevMO.getReg() && PrevMO.isDef() &&
           TRI->regsOverlap(PrevMO.getReg(), PointerReg))
         return SR_Impossible;
 
   return SR_Suitable;
 }
 
 bool ImplicitNullChecks::canHoistLoadInst(
     MachineInstr *FaultingMI, unsigned PointerReg,
for (auto &DependenceMO : DependenceMI->operands()) {
     // same as it would have been had the load not have executed and we'd have
     // branched to NullSucc directly.
     if (AnyAliasLiveIn(TRI, NullSucc, DependenceMO.getReg()))
       return false;
 
     // The Dependency can't be re-defining the base register -- then we won't
     // get the memory operation on the address we want.  This is already
     // checked in \c IsSuitableMemoryOp.
-    assert(!TRI->regsOverlap(DependenceMO.getReg(), PointerReg) &&
+    assert(!(DependenceMO.isDef() &&
+             TRI->regsOverlap(DependenceMO.getReg(), PointerReg)) &&
            "Should have been checked before!");
   }
 
   auto DepDepResult =
       computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
 
   if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
     return false;

test/CodeGen/X86/implicit-null-check.ll

 
  ret_100:
   ret i32 100
 
  ret_200:
   ret i32 200
 }
 
+define i32 @imp_null_check_gep_load_with_use_dep(i32* %x, i32 %a) {
+; CHECK-LABEL: imp_null_check_gep_load_with_use_dep:
+; CHECK: [[BB0_imp_null_check_gep_load_with_use_dep:L[^:]+]]:
+; CHECK: movl (%rdi), %eax
+; CHECK: addl %edi, %esi
+; CHECK: leal 4(%rax,%rsi), %eax
+; CHECK: retq
+; CHECK: [[BB1_imp_null_check_gep_load_with_use_dep:LBB5_[0-9]+]]:
+; CHECK: movl $42, %eax
+; CHECK: retq
+
+ entry:
+  %c = icmp eq i32* %x, null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
+
+ is_null:
+  ret i32 42
+
+ not_null:
+  %x.loc = getelementptr i32, i32* %x, i32 1
+  %y = ptrtoint i32* %x.loc to i32
+  %b = add i32 %a, %y
+  %t = load i32, i32* %x
+  %z = add i32 %t, %b
+  ret i32 %z
+}
+
 !0 = !{}
 
 ; CHECK-LABEL: __LLVM_FaultMaps:
 
 ; Version:
 ; CHECK-NEXT: .byte 1
 
 ; Reserved x2
 ; CHECK-NEXT: .byte 0
 ; CHECK-NEXT: .short 0
 
 ; # functions:
-; CHECK-NEXT: .long 5
+; CHECK-NEXT: .long 6
 
 ; FunctionAddr:
 ; CHECK-NEXT: .quad _imp_null_check_add_result
 ; NumFaultingPCs
 ; CHECK-NEXT: .long 1
 ; Reserved:
 ; CHECK-NEXT: .long 0
 ; Fault[0].Type:

 ; Fault[0].Type:
 ; CHECK-NEXT: .long 1
 ; Fault[0].FaultOffset:
 ; CHECK-NEXT: .long [[BB0_imp_null_check_gep_load]]-_imp_null_check_gep_load
 ; Fault[0].HandlerOffset:
 ; CHECK-NEXT: .long [[BB1_imp_null_check_gep_load]]-_imp_null_check_gep_load
 
 ; FunctionAddr:
+; CHECK-NEXT: .quad _imp_null_check_gep_load_with_use_dep
+; NumFaultingPCs
+; CHECK-NEXT: .long 1
+; Reserved:
+; CHECK-NEXT: .long 0
+; Fault[0].Type:
+; CHECK-NEXT: .long 1
+; Fault[0].FaultOffset:
+; CHECK-NEXT: .long [[BB0_imp_null_check_gep_load_with_use_dep]]-_imp_null_check_gep_load_with_use_dep
+; Fault[0].HandlerOffset:
+; CHECK-NEXT: .long [[BB1_imp_null_check_gep_load_with_use_dep]]-_imp_null_check_gep_load_with_use_dep
+
+; FunctionAddr:
 ; CHECK-NEXT: .quad _imp_null_check_hoist_over_unrelated_load
 ; NumFaultingPCs
 ; CHECK-NEXT: .long 1
 ; Reserved:
 ; CHECK-NEXT: .long 0
 ; Fault[0].Type:
 ; CHECK-NEXT: .long 1
 ; Fault[0].FaultOffset:

 ; CHECK-NEXT: .long   1
 ; Fault[0].FaultOffset:
 ; CHECK-NEXT: .long   [[BB0_imp_null_check_via_mem_comparision]]-_imp_null_check_via_mem_comparision
 ; Fault[0].HandlerOffset:
 ; CHECK-NEXT: .long   [[BB1_imp_null_check_via_mem_comparision]]-_imp_null_check_via_mem_comparision
 
 ; OBJDUMP: FaultMap table:
 ; OBJDUMP-NEXT: Version: 0x1
-; OBJDUMP-NEXT: NumFunctions: 5
+; OBJDUMP-NEXT: NumFunctions: 6
 ; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
 ; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 5
 ; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
 ; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 7
 ; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
+; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 9
+; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
 ; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 7
 ; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
 ; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 3

test/CodeGen/X86/implicit-null-checks.mir

not_null:
     ret i32 undef
 
   is_null:
     ret i32 0
   }
 
   attributes #0 = { "target-features"="+bmi,+bmi2" }
 
+  define i32 @imp_null_check_gep_load_with_use_dep(i32* %x, i32 %a) {
+  entry:
+    %c = icmp eq i32* %x, null
+    br i1 %c, label %is_null, label %not_null, !make.implicit !0
+  
+  is_null:                                          ; preds = %entry
+    ret i32 42
+  
+  not_null:                                         ; preds = %entry
+    %x.loc = getelementptr i32, i32* %x, i32 1
+    %y = ptrtoint i32* %x.loc to i32
+    %b = add i32 %a, %y
+    %t = load i32, i32* %x
+    %z = add i32 %t, %b
+    ret i32 %z
+  }
+
+  define i32 @imp_null_check_load_with_base_sep(i32* %x, i32 %a) {
+  entry:
+    %c = icmp eq i32* %x, null
+    br i1 %c, label %is_null, label %not_null, !make.implicit !0
+  
+  is_null:                                          ; preds = %entry
+    ret i32 42
+  
+  not_null:                                         ; preds = %entry
+    ret i32 undef
+  }
+
   !0 = !{}
 ...
 ---
 name:            imp_null_check_with_bitwise_op_0
 # CHECK-LABEL: name:            imp_null_check_with_bitwise_op_0
 alignment:       4
 tracksRegLiveness: true
 liveins:
bb.2.is_null:
     %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags
     RETQ %eax
 
 ...
 ---
 name:            use_alternate_load_op
 # CHECK-LABEL: use_alternate_load_op
 # CHECK: bb.0.entry:
-# CHECK: TEST64rr %rdi, %rdi, implicit-def %eflags
-# CHECK-NEXT: JE_1 %bb.2.is_null, implicit killed %eflags
+# CHECK: %r10 = FAULTING_LOAD_OP %bb.2.is_null, {{[0-9]+}}, killed %rdi, 1, _, 0, _
+# CHECK-NEXT: JMP_1 %bb.1.not_null
 # CHECK: bb.1.not_null
 
 alignment:       4
 tracksRegLiveness: true
 liveins:
   - { reg: '%rdi' }
   - { reg: '%rsi' }
 body:             |
bb.1.not_null:
     %r10 = MOV64rm killed %rdi, 1, _, 0, _
     RETQ %r10d
 
   bb.2.is_null:
     %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags
     RETQ %eax
 
 ...
+---
+name:            imp_null_check_gep_load_with_use_dep
+# CHECK:  bb.0.entry:
+# CHECK:    %eax = FAULTING_LOAD_OP %bb.2.is_null, {{[0-9]+}}, killed %rdi, 1, _, 0, _, implicit-def %rax :: (load 4 from %ir.x)
+# CHECK-NEXT:    JMP_1 %bb.1.not_null
+alignment:       4
+tracksRegLiveness: true
+liveins:         
+  - { reg: '%rdi' }
+  - { reg: '%rsi' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.is_null(0x30000000), %bb.2.not_null(0x50000000)
+    liveins: %rsi, %rdi
+  
+    TEST64rr %rdi, %rdi, implicit-def %eflags
+    JE_1 %bb.1.is_null, implicit %eflags
+  
+  bb.2.not_null:
+    liveins: %rdi, %rsi
+  
+    %rsi = ADD64rr %rsi, %rdi, implicit-def dead %eflags
+    %eax = MOV32rm killed %rdi, 1, _, 0, _, implicit-def %rax :: (load 4 from %ir.x)
+    %eax = LEA64_32r killed %rax, 1, killed %rsi, 4, _
+    RETQ %eax
+  
+  bb.1.is_null:
+    %eax = MOV32ri 42
+    RETQ %eax
+
+...
+---
+name:            imp_null_check_load_with_base_sep
+# CHECK:  bb.0.entry:
+# CHECK:     %rsi = ADD64rr %rsi, %rdi, implicit-def dead %eflags
+# CHECK-NEXT:    %esi = FAULTING_LOAD_OP %bb.2.is_null, {{[0-9]+}}, killed %esi, %rdi, 1, _, 0, _, implicit-def dead %eflags
+# CHECK-NEXT:    JMP_1 %bb.1.not_null
+alignment:       4
+tracksRegLiveness: true
+liveins:         
+  - { reg: '%rdi' }
+  - { reg: '%rsi' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.is_null(0x30000000), %bb.2.not_null(0x50000000)
+    liveins: %rsi, %rdi
+  
+    TEST64rr %rdi, %rdi, implicit-def %eflags
+    JE_1 %bb.1.is_null, implicit %eflags
+  
+  bb.2.not_null:
+    liveins: %rdi, %rsi
+  
+    %rsi = ADD64rr %rsi, %rdi, implicit-def dead %eflags
+    %esi = AND32rm killed %esi, %rdi, 1, _, 0, _, implicit-def dead %eflags
+    %eax = MOV32rr %esi
+    RETQ %eax
+  
+  bb.1.is_null:
+    %eax = MOV32ri 42
+    RETQ %eax
+
+...