[MachineSink] Don't break ImplicitNulls

[sanjoy]

Summary

This teaches MachineSink to not sink instructions that might break the
implicit null check optimization that runs later. This should not
affect frontends that do not use implicit null checks.

[sanjoy]

I added a comment to the ImplicitNullChecks pass stating why it is difficult to work with loads sunk below control flow: http://reviews.llvm.org/rL253020

lib/CodeGen/MachineSink.cpp

684

Reading this on phabricator makes me feel that the naming here is not great -- I'll rename this function to SinkingPreventsImplicitNullCheck tomorrow.

[sanjoy]

• rename helper to SinkingPreventsImplicitNullCheck

[majnemer]

lib/CodeGen/MachineSink.cpp

694

Can't getBasicBlock fail? IIRC, MachineBasicBlocks aren't obligated to map back to a BasicBlock.

[sanjoy]

lib/CodeGen/MachineSink.cpp

694

I think the failure mode is to return nullptr, which should be caught by the check below.

[majnemer]

lib/CodeGen/MachineSink.cpp

694

Ah, my eyes didn't see it. Sorry for the noise.

[sanjoy]

ping!

[sanjoy]

ping!

[sanjoy]

ping!

[atrick]

Looks fine to me. At least I don't see any harm in this.

lib/CodeGen/MachineSink.cpp

 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 using namespace llvm;
 
MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI,
   // It's not safe to sink instructions to EH landing pad. Control flow into
   // landing pad is implicitly defined.
   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
     return nullptr;
 
   return SuccToSinkTo;
 }
 
+/// \brief Return true if MI is likely to be usable as a memory operation by the
+/// implicit null check optimization.
+///
+/// This is a "best effort" heuristic, and should not be relied upon for
+/// correctness.  This returning true does not guarantee that the implicit null
+/// check optimization is legal over MI, and this returning false does not
+/// guarantee MI cannot possibly be used to do a null check.
+static bool SinkingPreventsImplicitNullCheck(MachineInstr *MI,
+                                             const TargetInstrInfo *TII,
+                                             const TargetRegisterInfo *TRI) {
+  typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
+
+  auto *MBB = MI->getParent();
+  if (MBB->pred_size() != 1)
+    return false;
+
+  auto *PredMBB = *MBB->pred_begin();
+  auto *PredBB = PredMBB->getBasicBlock();
+
+  // Frontends that don't use implicit null checks have no reason to emit
+  // branches with make.implicit metadata, and this function should always
+  // return false for them.
+  if (!PredBB ||
+      !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
+    return false;
+
+  unsigned BaseReg, Offset;
+  if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
+    return false;
+
+  if (!(MI->mayLoad() && !MI->isPredicable()))
+    return false;
+
+  MachineBranchPredicate MBP;
+  if (TII->AnalyzeBranchPredicate(*PredMBB, MBP, false))
+    return false;
+
+  return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
+         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
+          MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
+         MBP.LHS.getReg() == BaseReg;
+}
+
 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 /// instruction out of its current block into a successor.
 bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore,
                                      AllSuccsCache &AllSuccessors) {
   // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to
   // be close to the source to make it easier to coalesce.
   if (AvoidsSinking(MI, MRI))
     return false;
 
   // Check if it's safe to move the instruction.
   if (!MI->isSafeToMove(AA, SawStore))
     return false;
 
   // Convergent operations may not be made control-dependent on additional
   // values.
   if (MI->isConvergent())
     return false;
 
+  // Don't break implicit null checks.  This is a performance heuristic, and not
+  // required for correctness.
+  if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
+    return false;
+
   // FIXME: This should include support for sinking instructions within the
   // block they are currently in to shorten the live ranges.  We often get
   // instructions sunk into the top of a large block, but it would be better to
   // also sink them down before their first use in the block.  This xform has to
   // be careful not to *increase* register pressure though, e.g. sinking
   // "x = y + z" down if it kills y and z would increase the live ranges of y
   // and z and only shrink the live range of x.
 

test/CodeGen/X86/machine-sink-and-implicit-null-checks.ll

+; RUN: llc -mtriple=x86_64-apple-macosx -O3 -enable-implicit-null-checks -o - < %s 2>&1 | FileCheck %s
+
+declare void @throw0()
+declare void @throw1()
+
+define i1 @f(i8* %p0, i8* %p1) {
+ entry:
+  %c0 = icmp eq i8* %p0, null
+  br i1 %c0, label %throw0, label %continue0, !make.implicit !0
+
+ continue0:
+  %v0 = load i8, i8* %p0
+  %c1 = icmp eq i8* %p1, null
+  br i1 %c1, label %throw1, label %continue1, !make.implicit !0
+
+ continue1:
+  %v1 = load i8, i8* %p1
+  %v = icmp eq i8 %v0, %v1
+  ret i1 %v
+
+ throw0:
+  call void @throw0()
+  unreachable
+
+ throw1:
+  call void @throw1()
+  unreachable
+}
+
+; Check that we have two implicit null checks in @f
+
+; CHECK: __LLVM_FaultMaps:
+; CHECK-NEXT:        .byte   1
+; CHECK-NEXT:        .byte   0
+; CHECK-NEXT:        .short  0
+; CHECK-NEXT:        .long   1
+
+; FunctionInfo[0] =
+
+; FunctionAddress =
+; CHECK-NEXT:        .quad   _f
+
+; NumFaultingPCs =
+; CHECK-NEXT:        .long   2
+
+; Reserved =
+; CHECK-NEXT:        .long   0
+
+!0 = !{}