[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

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

322

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

343

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

369

s/has value/have values/

470

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

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.

lib/CodeGen/ImplicitNullChecks.cpp

enum AliasResult {
     AR_NoAlias,
     AR_MayAlias,
     AR_WillAliasEverything
   };
   /// Returns AR_NoAlias if \p MI memory operation does not alias with
   /// \p PrevMI, AR_MayAlias if they may alias and AR_WillAliasEverything if
   /// they may alias and any further memory operation may alias with \p PrevMI.
   AliasResult areMemoryOpsAliased(MachineInstr &MI, MachineInstr *PrevMI);
+  AliasResult areMemoryOpsAliased(MachineInstr &MI,
+                                  ArrayRef<MachineInstr *> Block);
 
   enum SuitabilityResult {
     SR_Suitable,
     SR_Unsuitable,
     SR_Impossible
   };
   /// Return SR_Suitable if \p MI a memory operation that can be used to
   /// implicitly null check the value in \p PointerReg, SR_Unsuitable if
for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
        ++AR)
     if (MBB->isLiveIn(*AR))
       return true;
   return false;
 }
 
 ImplicitNullChecks::AliasResult
 ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
+                                        ArrayRef<MachineInstr *> Block) {
+  for (auto *PrevMI : Block) {
+    AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
+    if (AR != AR_NoAlias)
+      return AR;
+  }
+  return AR_NoAlias;
+}
+
+ImplicitNullChecks::AliasResult
+ImplicitNullChecks::areMemoryOpsAliased(MachineInstr &MI,
                                         MachineInstr *PrevMI) {
   // If it is not memory access, skip the check.
   if (!(PrevMI->mayStore() || PrevMI->mayLoad()))
     return AR_NoAlias;
   // Load-Load may alias
   if (!(MI.mayStore() || PrevMI->mayStore()))
     return AR_NoAlias;
   // We lost info, conservatively alias. If it was store then no sense to
   // continue because we won't be able to check against it further.
   if (MI.memoperands_empty())
     return MI.mayStore() ? AR_WillAliasEverything : AR_MayAlias;
   if (PrevMI->memoperands_empty())
     return PrevMI->mayStore() ? AR_WillAliasEverything : AR_MayAlias;
 
   for (MachineMemOperand *MMO1 : MI.memoperands()) {
-    // MMO1 should have a value due it comes from operation we'd like to use
-    // as implicit null check.
-    assert(MMO1->getValue() && "MMO1 should have a Value!");
+    // Remember whether MMO1 is a pseudo value.
+    const PseudoSourceValue *PSV1 = MMO1->getPseudoValue();
+
     for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
-      if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
-        if (PSV->mayAlias(MFI))
+      if (const PseudoSourceValue *PSV2 = MMO2->getPseudoValue()) {
+        if (PSV1) {
+          // Special case, both are pseudo values.
+          // If they are of different kind they are not alias.
+          if (PSV1->kind() != PSV2->kind())
+            continue;
+          // If both of them are Fixed stack slot then check whether it is the
+          // same index.
+          // Otherwise they may alias for simplification.
+          if (auto *FSPSV1 =
+                  dyn_cast_or_null<FixedStackPseudoSourceValue>(PSV1))
+            if (auto *FSPSV2 = dyn_cast<FixedStackPseudoSourceValue>(PSV2))
+              if (FSPSV1->getFrameIndex() != FSPSV2->getFrameIndex())
+                continue;
+          return AR_MayAlias;
+        }
+        // The MMO1 is not pseudo while MMO2 is pseudo.
+        if (PSV2->mayAlias(MFI))
+          return AR_MayAlias;
+        continue;
+      }
+      // MMO2 is not a pseudo source value. If MMO1 is then check it.
+      if (PSV1) {
+        if (PSV1->mayAlias(MFI))
           return AR_MayAlias;
         continue;
       }
+      // Both MMO1 and MMO2 has value represented by LLVM IR.
       llvm::AliasResult AAResult = AA->alias(
           MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize,
                          MMO1->getAAInfo()),
           MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize,
                          MMO2->getAAInfo()));
       if (AAResult != NoAlias)
         return AR_MayAlias;
     }
ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
 
   // We want the mem access to be issued at a sane offset from PointerReg,
   // so that if PointerReg is null then the access reliably page faults.
   if (!((MI.mayLoad() || MI.mayStore()) && !MI.isPredicable() &&
         Offset < PageSize))
     return SR_Unsuitable;
 
   // Finally, check whether the current memory access aliases with previous one.
-  for (auto *PrevMI : PrevInsts) {
-    AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
-    if (AR == AR_WillAliasEverything)
-      return SR_Impossible;
-    if (AR == AR_MayAlias)
-      return SR_Unsuitable;
-  }
+  AliasResult AR = areMemoryOpsAliased(MI, PrevInsts);
   return SR_Suitable;
 }
 
 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
                                       unsigned PointerReg,
                                       ArrayRef<MachineInstr *> InstsSeenSoFar,
                                       MachineBasicBlock *NullSucc,
                                       MachineInstr *&Dependence) {
bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
   }
 
   auto DepDepResult =
       computeDependence(DependenceMI, {InstsSeenSoFar.begin(), DependenceItr});
 
   if (!DepDepResult.CanReorder || DepDepResult.PotentialDependence)
     return false;
 
+  // Verify that DependenceMI does not alias with any instructions seen so far.
+  if (DependenceMI->mayLoadOrStore())
+    if (areMemoryOpsAliased(*DependenceMI, { InstsSeenSoFar.begin(),
+                                             DependenceItr }) != AR_NoAlias)
+      return false;
+
   Dependence = DependenceMI;
   return true;
 }
 
 /// Analyze MBB to check if its terminating branch can be turned into an
 /// implicit null check.  If yes, append a description of the said null check to
 /// NullCheckList and return true, else return false.
 bool ImplicitNullChecks::analyzeBlockForNullChecks(

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
+  }
+
+  define i32 @inc_spill_dep_good(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
+
+...
+---
+name:            inc_spill_dep_good
+# CHECK-LABEL: inc_spill_dep_good
+# CHECK: bb.0.entry:
+# CHECK:  %edi = FAULTING_OP 1, %bb.2.is_null, {{[0-9]+}}, %rdi, 1, _, 8, _ :: (load 4 from %ir.ptr)
+# CHECK-NEXT: JMP_1 %bb.1.not_null
+# CHECK: bb.1.not_null
+
+alignment:       4
+tracksRegLiveness: true
+stack:
+  - { id: 0, type: spill-slot, offset: -8, size: 8, alignment: 8}
+  - { id: 1, type: spill-slot, offset: -16, 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.1)
+    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.1)
+    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
+
+...