[ImplicitNullCheck] Fix the bug when dependent instruction accesses memory

[skatkov]

Summary

It is possible that dependent instruction may access memory.
In this case we must reject optimization because the memory change will
be visible in null handler basic block. So we will execute an instruction which
we must not execute if check fails.

[sanjoy]

lgtm with minor comments

lib/CodeGen/ImplicitNullChecks.cpp

315 ↗

(On Diff #109966)

IIUC this isn't optimal -- we can early return with AR_MayAlias when processing further would have given us AR_WillAliasEverything.

322 ↗

(On Diff #109966)

Minor, but I'd be consistent here and either take both as refs or pointers.

343 ↗

(On Diff #109966)

There are too many continues and returns here -- do you mind splitting out a mayAlias(MachineMemOperand *, MachineMemOperand *) helper?

369 ↗

(On Diff #109966)

s/has value/have values/

470 ↗

(On Diff #109966)

I vaguely remember that originally we did not allow the dependence MI to touch memory. Do you know when this changed (or am I misremembering)?

[skatkov]

Hi Sanjoy, thank you for the quick review and a good point about stores at all. I think this patch is incorrect and will upload other version soon.

lib/CodeGen/ImplicitNullChecks.cpp

470 ↗

(On Diff #109966)

This is really good question and I came to it last night (before going to sleep) as well.
It seems it is incorrect. for DependenceMI we check that registers it defines are not used in null branch handling. actually the same we should do for memory change. So it means that if DependenceMI changes the memory we must ensure that memory is not used in null case handler because we did a change which should not happen if null happened. It is really difficult to do and it makes me thinking that we must just prohibit stores for DependenceMI.

Please note that we have already prohibit loads (line 428 this file). And we should do the same for store.

Actually I've discussed this today with Philip offline and he made a good point about DependenceMI. It should not do any visible side-effects to the branch handling null case. We already check the definition of registers. Also we do not allow different instructions like call. We should not allow stores (will upload a patch). I will also check whether we cover other cases if they exists.

[skatkov]

Sanjoy, please take a look.

[sanjoy]

lgtm again

[skatkov]

Thank you Sanjoy!
You asked about when we allowed stores. DependenceMI did not check for stores but it was hidden in canHandle. when I implemented INC based on stores and added alias analysis I removed the check from canHandle but did not add it to DependenceMI. so it was my fault.

llvm/trunk/lib/CodeGen/ImplicitNullChecks.cpp

bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
   }
 
   auto DependenceItr = *DepResult.PotentialDependence;
   auto *DependenceMI = *DependenceItr;
 
   // We don't want to reason about speculating loads.  Note -- at this point
   // we should have already filtered out all of the other non-speculatable
   // things, like calls and stores.
+  // We also do not want to hoist stores because it might change the memory
+  // while the FaultingMI may result in faulting.
   assert(canHandle(DependenceMI) && "Should never have reached here!");
-  if (DependenceMI->mayLoad())
+  if (DependenceMI->mayLoadOrStore())
     return false;
 
   for (auto &DependenceMO : DependenceMI->operands()) {
     if (!(DependenceMO.isReg() && DependenceMO.getReg()))
       continue;
 
     // Make sure that we won't clobber any live ins to the sibling block by
     // hoisting Dependency.  For instance, we can't hoist INST to before the

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

--- |
 
   not_null:
     ret i32 undef
 
   is_null:
     ret i32 undef
   }
 
+  define i32 @inc_spill_dep(i32* %ptr, i32 %val) {
+  entry:
+    %ptr_is_null = icmp eq i32* %ptr, null
+    br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !0
+
+  not_null:
+    ret i32 undef
+
+  is_null:
+    ret i32 undef
+  }
+
   attributes #0 = { "target-features"="+bmi,+bmi2" }
 
   !0 = !{}
 ...
 ---
 name:            imp_null_check_with_bitwise_op_0
 # CHECK-LABEL: name:            imp_null_check_with_bitwise_op_0
 alignment:       4
bb.1.not_null:
     %eax = MOV32rm killed %rdi, 1, _, 0, _ :: (load 4 from %ir.ptr)
     RETQ %eax
 
   bb.2.is_null:
     %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags
     RETQ %eax
 
 ...
+---
+name:            inc_spill_dep
+# CHECK-LABEL: inc_spill_dep
+# CHECK: bb.0.entry:
+# CHECK:    TEST64rr %rdi, %rdi, implicit-def %eflags
+# CHECK-NEXT:    JE_1 %bb.2.is_null, implicit killed %eflags
+# CHECK: bb.1.not_null
+
+alignment:       4
+tracksRegLiveness: true
+stack:
+  - { id: 0, type: spill-slot, offset: -8, size: 8, alignment: 8}
+liveins:
+  - { reg: '%rdi' }
+  - { reg: '%rsi' }
+body:             |
+  bb.0.entry:
+    liveins: %rdi, %rsi
+
+    %rsp = frame-setup SUB64ri8 %rsp, 8, implicit-def dead %eflags
+    MOV32mr %rsp, 1, %noreg, 0, %noreg, %esi :: (store 4 into %stack.0)
+    TEST64rr %rdi, %rdi, implicit-def %eflags
+    JE_1 %bb.2.is_null, implicit killed %eflags
+
+  bb.1.not_null:
+    liveins: %rdi, %rsi
+
+    %r14d = MOV32rm %rsp, 1, %noreg, 0, %noreg :: (load 4 from %stack.0)
+    MOV64mr %rsp, 1, %noreg, 0, %noreg, %rdi :: (store 8 into %stack.0)
+    %edi = MOV32rm %rdi, 1, %noreg, 8, %noreg :: (load 4 from %ir.ptr)
+    %eax = MOV32rr %edi
+    RETQ %eax
+
+  bb.2.is_null:
+    %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags
+    RETQ %eax
+
+...