[ImplicitNullCheck] Add alias analysis usage

[skatkov]

Summary

With this change ImplicitNullCheck optimization uses alias analysis and
can use load/store memory access for implicit null check if there are other
load/store before but memory accesses do not alias.

[sanjoy]

Some comments inline.

lib/CodeGen/ImplicitNullChecks.cpp

374–385

s/alias/aliases/

380

Can we pull the body of this loop out into a static helper?

386

Can we return SR_Impossible here if the MachineInstr that was the store also has no mem operands?

393

The indents are off -- please use clang-format.

402

Maybe move this check up to avoid wasting work if AA isn't available?

Btw, given the way you're getting AA, I'd expect it always be present since otherwise getAnalysis<AAResultsWrapperPass>().getAAResults() will have to be a null reference which is undefined behavior.

409

What about multiple memoperands on the same machine instruction?

[skatkov]

Will prepapre an update.

lib/CodeGen/ImplicitNullChecks.cpp

374–385

ok

380

will do

386

makes sense.

393

sure

402

we can be in a good shape even if AA is not available. Say if other instruction is a spill. See the previous check: PSV != null and PSV->mayAlias is false. So it is not good to move AA check earlier. WRT AA is not null I will double check your idea.

409

Not sure it is possible but we can iterate over mem operands.

[sanjoy]

lib/CodeGen/ImplicitNullChecks.cpp

409

I'd also be happy with either of:

• An assert that says that there is only one mem operand
• A bailout if there are more than one mem operand (if they are very rare)

[skatkov]

Address comments. Please review again.

[sanjoy]

Comments inline.

lib/CodeGen/ImplicitNullChecks.cpp

347

Can we name this as a verb, like areMemoryOpsAliased?

364

This clause is a bit odd -- without this clause, the nested loop returns SR_Suitable only if all pairs of mem operands are NoAlias. But this clause returns SR_Suitable even if one of PrevMI mem operands is a PseudoSourceValue with !PSV->mayAlias(MFI). Why do we have this difference? If we have to, I'd prefer checking for PseudoSourceValue in a loop only over PrevMI->memoperands() outside this nested loop.

Also: can one of MI.memoperands() be a PseudoSourceValue? If not, please add an assert.

373

Spacing is off here, but I'll run clang-format on the diff before pushing it so don't bother fixing it right now.

376

s/SR_impossible/SR_Impossible/

378

This layering seems odd to me -- AliasMemoryOp should not return a SuitabilityResult IMO, since it has no idea on why it has been asked to compute aliasing between the two instructions. It almost feels like it should return a tri-stated AliasResult with AR_NoAlias, AR_MayAlias and AR_WillAliasEverything. That would be a bit more code, but I think the intent will be cleaner.

[skatkov]

addressed comments, please review.

Also I've run clang-format against ImplicitNullChecks.cpp and it shows a bit other issues not directly related to my change.
Specifically it does not like one-line enum. If you'd like I can fix it as well.

[skatkov]

lib/CodeGen/ImplicitNullChecks.cpp

364

Good catch, fixed.

378

Sounds reasonable to me.

[sanjoy]

In D30331#688112, @skatkov wrote:

addressed comments, please review.

Also I've run clang-format against ImplicitNullChecks.cpp and it shows a bit other issues not directly related to my change.

You can use git clang-format (after installing https://github.com/llvm-mirror/clang/blob/master/tools/clang-format/git-clang-format) to format just code touched by a specific commit. For instance, to format the code touched in the most recent commit, you can do git clang-format HEAD^.

Specifically it does not like one-line enum. If you'd like I can fix it as well.

[sanjoy]

lgtm with really minor tweaks

lib/CodeGen/ImplicitNullChecks.cpp

167

The ImplicitNullChecks:: is not needed here, is it?

Also, I'd prefer plural here, as areMemoryOpsAliased.

316

s/if/If/

331

No need for the else. That is, you can say:

if (...)
  return ...;
continue;

[skatkov]

Sanjoy, please land if you are ok with this.

lib/CodeGen/ImplicitNullChecks.cpp

public:
 
     MachineInstr *getOnlyDependency() const { return OnlyDependency; }
   };
 
   const TargetInstrInfo *TII = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
   AliasAnalysis *AA = nullptr;
   MachineModuleInfo *MMI = nullptr;
+  MachineFrameInfo *MFI = nullptr;
 
   bool analyzeBlockForNullChecks(MachineBasicBlock &MBB,
                                  SmallVectorImpl<NullCheck> &NullCheckList);
   MachineInstr *insertFaultingInstr(MachineInstr *MI, MachineBasicBlock *MBB,
                                     MachineBasicBlock *HandlerMBB);
   void rewriteNullChecks(ArrayRef<NullCheck> NullCheckList);
 
-  enum SuitabilityResult { SR_Suitable, SR_Unsuitable, SR_Impossible };
-
+  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);
+
+  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
   /// \p MI cannot be used to null check and SR_Impossible if there is
   /// no sense to continue lookup due to any other instruction will not be able
   /// to be used. \p PrevInsts is the set of instruction seen since
-  /// the explicit null check on \p PointerReg. \p SeenLoad means that load
-  /// instruction has been observed in \PrevInsts set.
+  /// the explicit null check on \p PointerReg.
   SuitabilityResult isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
-                                       ArrayRef<MachineInstr *> PrevInsts,
-                                       bool &SeenLoad);
+                                       ArrayRef<MachineInstr *> PrevInsts);
 
   /// Return true if \p FaultingMI can be hoisted from after the the
   /// instructions in \p InstsSeenSoFar to before them.  Set \p Dependence to a
   /// non-null value if we also need to (and legally can) hoist a depedency.
   bool canHoistInst(MachineInstr *FaultingMI, unsigned PointerReg,
                     ArrayRef<MachineInstr *> InstsSeenSoFar,
                     MachineBasicBlock *NullSucc, MachineInstr *&Dependence);
 
bool ImplicitNullChecks::canReorder(const MachineInstr *A,
 
   return true;
 }
 
 bool ImplicitNullChecks::runOnMachineFunction(MachineFunction &MF) {
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getRegInfo().getTargetRegisterInfo();
   MMI = &MF.getMMI();
+  MFI = &MF.getFrameInfo();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   SmallVector<NullCheck, 16> NullCheckList;
 
   for (auto &MBB : MF)
     analyzeBlockForNullChecks(MBB, NullCheckList);
 
   if (!NullCheckList.empty())
     rewriteNullChecks(NullCheckList);
 
   return !NullCheckList.empty();
 }
 
 // Return true if any register aliasing \p Reg is live-in into \p MBB.
 static bool AnyAliasLiveIn(const TargetRegisterInfo *TRI,
                            MachineBasicBlock *MBB, unsigned Reg) {
   for (MCRegAliasIterator AR(Reg, TRI, /*IncludeSelf*/ true); AR.isValid();
        ++AR)
     if (MBB->isLiveIn(*AR))
       return true;
   return false;
 }
 
+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!");
+    for (MachineMemOperand *MMO2 : PrevMI->memoperands()) {
+      if (const PseudoSourceValue *PSV = MMO2->getPseudoValue()) {
+        if (PSV->mayAlias(MFI))
+          return AR_MayAlias;
+        continue;
+      }
+      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;
+    }
+  }
+  return AR_NoAlias;
+}
+
 ImplicitNullChecks::SuitabilityResult
 ImplicitNullChecks::isSuitableMemoryOp(MachineInstr &MI, unsigned PointerReg,
-                                       ArrayRef<MachineInstr *> PrevInsts,
-                                       bool &SeenLoad) {
+                                       ArrayRef<MachineInstr *> PrevInsts) {
   int64_t Offset;
   unsigned BaseReg;
 
-  // First, if it is a store and we saw load before we bail out
-  // because we will not be able to re-order load-store without
-  // using alias analysis.
-  if (SeenLoad && MI.mayStore())
-    return SR_Impossible;
-
-  SeenLoad = SeenLoad || MI.mayLoad();
-
-  // Without alias analysis we cannot re-order store with anything.
-  // so if this instruction is not a candidate we should stop.
-  SuitabilityResult Unsuitable = MI.mayStore() ? SR_Impossible : SR_Unsuitable;
-
   if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI) ||
       BaseReg != PointerReg)
-    return Unsuitable;
+    return SR_Unsuitable;
 
   // 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 Unsuitable;
+    return SR_Unsuitable;
 
   // Finally, we need to make sure that the access instruction actually is
   // accessing from PointerReg, and there isn't some re-definition of PointerReg
   // between the compare and the memory access.
   // If PointerReg has been redefined before then there is no sense to continue
   // lookup due to this condition will fail for any further instruction.
+  SuitabilityResult Suitable = SR_Suitable;
   for (auto *PrevMI : PrevInsts)
-    for (auto &PrevMO : PrevMI->operands())
+    for (auto &PrevMO : PrevMI->operands()) {
       if (PrevMO.isReg() && PrevMO.getReg() && PrevMO.isDef() &&
           TRI->regsOverlap(PrevMO.getReg(), PointerReg))
         return SR_Impossible;
 
-  return SR_Suitable;
+      // Check whether the current memory access aliases with previous one.
+      // If we already found that it aliases then no need to continue.
+      // But we continue base pointer check as it can result in SR_Impossible.
+      if (Suitable == SR_Suitable) {
+        AliasResult AR = areMemoryOpsAliased(MI, PrevMI);
+        if (AR == AR_WillAliasEverything)
+          return SR_Impossible;
+        if (AR == AR_MayAlias)
+          Suitable = SR_Unsuitable;
+      }
+    }
+  return Suitable;
 }
 
 bool ImplicitNullChecks::canHoistInst(MachineInstr *FaultingMI,
                                       unsigned PointerReg,
                                       ArrayRef<MachineInstr *> InstsSeenSoFar,
                                       MachineBasicBlock *NullSucc,
                                       MachineInstr *&Dependence) {
   auto DepResult = computeDependence(FaultingMI, InstsSeenSoFar);
   if (!DepResult.CanReorder)
     return false;
 
   if (!DepResult.PotentialDependence) {
     Dependence = nullptr;
     return true;
   }
 
   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.
   assert(canHandle(DependenceMI) && "Should never have reached here!");
   if (DependenceMI->mayLoad())
     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
bool ImplicitNullChecks::analyzeBlockForNullChecks(
   // ptr -- clause (2) above does not apply in this case.  In the above program
   // the safety of ptr->field can be dependent on some_cond; and, for instance,
   // ptr could be some non-null invalid reference that never gets loaded from
   // because some_cond is always true.
 
   const unsigned PointerReg = MBP.LHS.getReg();
 
   SmallVector<MachineInstr *, 8> InstsSeenSoFar;
-  bool SeenLoad = false;
 
   for (auto &MI : *NotNullSucc) {
     if (!canHandle(&MI) || InstsSeenSoFar.size() >= MaxInstsToConsider)
       return false;
 
     MachineInstr *Dependence;
-    SuitabilityResult SR =
-        isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar, SeenLoad);
+    SuitabilityResult SR = isSuitableMemoryOp(MI, PointerReg, InstsSeenSoFar);
     if (SR == SR_Impossible)
       return false;
     if (SR == SR_Suitable &&
         canHoistInst(&MI, PointerReg, InstsSeenSoFar, NullSucc, Dependence)) {
       NullCheckList.emplace_back(&MI, MBP.ConditionDef, &MBB, NotNullSucc,
                                  NullSucc, Dependence);
       return true;
     }

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

--- |
 
   not_null:
     ret void
 
   is_null:
     ret void
   }
 
+  define i32 @inc_store_and_load_no_alias(i32* noalias %ptr, i32* noalias %ptr2) {
+  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_store_and_load_alias(i32* %ptr, i32* %ptr2) {
+  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.2.is_null:
     %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags
     RETQ %eax
 
 ...
 ---
 name:            use_alternate_load_op
 # CHECK-LABEL: name:            use_alternate_load_op
 # CHECK: bb.0.entry:
-# CHECK: %r10 = FAULTING_OP 1, %bb.2.is_null, {{[0-9]+}}, killed %rdi, 1, _, 0, _
+# CHECK: %rax = FAULTING_OP 1, %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.0.entry:
     successors: %bb.2.is_null, %bb.1.not_null
     liveins: %rdi, %rsi
 
     TEST64rr %rdi, %rdi, implicit-def %eflags
     JE_1 %bb.2.is_null, implicit killed %eflags
 
   bb.1.not_null:
     liveins: %rdi, %rsi
 
     %rcx = MOV64rm killed %rsi, 1, _, 0, _
-    %rdx = AND64rm killed %rcx, %rdi, 1, _, 0, _, implicit-def dead %eflags
-    %r10 = MOV64rm killed %rdi, 1, _, 0, _
-    RETQ %r10d
+    %rcx = AND64rm killed %rcx, %rdi, 1, _, 0, _, implicit-def dead %eflags
+    %rax = MOV64rm killed %rdi, 1, _, 0, _
+    RETQ %eax
 
   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
bb.1.not_null:
     %esi = ADD32rr %esi, %esi, implicit-def dead %eflags
     ADD32mr killed %rdi, 1, _, 0, _, killed %esi, implicit-def dead %eflags
     RETQ
 
   bb.2.is_null:
     RETQ
 
 ...
+---
+name:            inc_store_and_load_no_alias
+# CHECK-LABEL: inc_store_and_load_no_alias
+# CHECK: bb.0.entry:
+# CHECK:  %eax = FAULTING_OP 1, %bb.2.is_null, {{[0-9]+}}, killed %rdi, 1, _, 0, _ :: (load 4 from %ir.ptr)
+# CHECK-NEXT: JMP_1 %bb.1.not_null
+# CHECK: bb.1.not_null
+
+alignment:       4
+tracksRegLiveness: true
+liveins:
+  - { reg: '%rdi' }
+  - { reg: '%rsi' }
+body:             |
+  bb.0.entry:
+    successors: %bb.2.is_null, %bb.1.not_null
+    liveins: %rdi, %rsi
+
+    TEST64rr %rdi, %rdi, implicit-def %eflags
+    JE_1 %bb.2.is_null, implicit killed %eflags
+
+  bb.1.not_null:
+    liveins: %rdi, %rsi
+
+    MOV32mi killed %rsi, 1, _, 0, _, 3 :: (store 4 into %ir.ptr2)
+    %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_store_and_load_alias
+# CHECK-LABEL: inc_store_and_load_alias
+# 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
+liveins:
+  - { reg: '%rdi' }
+  - { reg: '%rsi' }
+body:             |
+  bb.0.entry:
+    successors: %bb.2.is_null, %bb.1.not_null
+    liveins: %rdi, %rsi
+
+    TEST64rr %rdi, %rdi, implicit-def %eflags
+    JE_1 %bb.2.is_null, implicit killed %eflags
+
+  bb.1.not_null:
+    liveins: %rdi, %rsi
+
+    MOV32mi killed %rsi, 1, _, 0, _, 3 :: (store 4 into %ir.ptr2)
+    %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
+
+...