[ImplicitNullChecks] Be smarter in picking the memory op.

[sanjoy]

Summary

Before this change ImplicitNullChecks would only pick loads of the form:

  test Reg, Reg
  jz elsewhere
fallthrough:
  movl 32(Reg), Reg2

but not (say)

  test Reg, Reg
  jz elsewhere
fallthrough:
  inc Reg3
  movl 32(Reg), Reg2

This change teaches ImplicitNullChecks to look through "unrelated"
instructions like inc Reg3 when searching for a load instruction
to convert to a trapping load.

[reames]

lib/CodeGen/ImplicitNullChecks.cpp

212

Naming wise, this is a bit confusing. It's specifically whether the instruction is safe to reorder past the previously saved information. At first, I had expected this predicate to by applied to each instruction skipped.

255

If one of these loads potentially overlap with the value we eventually load from, don't we end up with a faulting instruction not recorded in the side table?

(To say this differently, I think you need to account for aliasing in your loads.)

[sanjoy]

lib/CodeGen/ImplicitNullChecks.cpp

212

Makes sense, I'll try and come up with a better name tomorrow.

255

The faulting instruction is reordered to where the original branch was, so the control flow remains intact. So if I start with

test reg, reg
jz throw_NPE
maybe_aliasing_load
candidate_load

I'll end up with

candidate_load ;; handler_pc = throw_NPE
maybe_aliasing_load

so maybe_aliasing_load won't execute if reg was null.

Does this answer your question?

[JosephTremoulet]

LGTM, aside from the one question.

lib/CodeGen/ImplicitNullChecks.cpp

274–278

This may just be my ignorance of machine instruction modeling, but this reads like you're taking care to skip explicit use operands; why is that?

lib/CodeGen/ImplicitNullChecks.cpp

 //   ...
 //
 // With the help of a runtime that understands the .fault_maps section,
 // faulting_load_op branches to throw_npe if executing movl (%r10), %esi incurs
 // a page fault.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/Support/CommandLine.h"
bool ImplicitNullChecks::analyzeBlockForNullChecks(
   //
   //   test %RAX, %RAX
   //   jne LblNotNull
   //
   //  LblNull:
   //   callq throw_NullPointerException
   //
   //  LblNotNull:
+  //   Inst0
+  //   Inst1
+  //   ...
   //   Def = Load (%RAX + <offset>)
   //   ...
   //
   //
   // we want to end up with
   //
   //   Def = TrappingLoad (%RAX + <offset>), LblNull
   //   jmp LblNotNull ;; explicit or fallthrough
   //
   //  LblNotNull:
+  //   Inst0
+  //   Inst1
   //   ...
   //
   //  LblNull:
   //   callq throw_NullPointerException
   //
 
   unsigned PointerReg = MBP.LHS.getReg();
-  MachineInstr *MemOp = &*NotNullSucc->begin();
+
+  // As we scan NotNullSucc for a suitable load instruction, we keep track of
+  // the registers defined and used by the instructions we scan past.  This bit
+  // of information lets us decide if it is legal to reorder the load
+  // instruction we find (if we do find such an instruction) to before
+  // NotNullSucc.
+  DenseSet<unsigned> RegDefs, RegUses;
+
+  // Returns true if it is safe to reorder MI to before NotNullSucc.
+  auto IsSafeToReorder = [&](MachineInstr *MI) {
+    // Right now we don't want to worry about LLVM's memory model.  This can be
+    // made more precise later.
+    for (auto *MMO : MI->memoperands())
+      if (!MMO->isUnordered())
+        return false;
+
+    for (auto &MO : MI->operands()) {
+      if (MO.isReg() && MO.getReg()) {
+        for (unsigned Reg : RegDefs)
+          if (TRI->regsOverlap(Reg, MO.getReg()))
+            return false;  // We found a write-after-write or read-after-write
+
+        if (MO.isDef())
+          for (unsigned Reg : RegUses)
+            if (TRI->regsOverlap(Reg, MO.getReg()))
+              return false;  // We found a write-after-read
+      }
+    }
+
+    return true;
+  };
+
+  for (auto MII = NotNullSucc->begin(), MIE = NotNullSucc->end(); MII != MIE;
+       ++MII) {
+    MachineInstr *MI = &*MII;
     unsigned BaseReg, Offset;
-  if (TII->getMemOpBaseRegImmOfs(MemOp, BaseReg, Offset, TRI))
-    if (MemOp->mayLoad() && !MemOp->isPredicable() && BaseReg == PointerReg &&
-        Offset < PageSize && MemOp->getDesc().getNumDefs() == 1) {
-      NullCheckList.emplace_back(MemOp, MBP.ConditionDef, &MBB, NotNullSucc,
+    if (TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
+      if (MI->mayLoad() && !MI->isPredicable() && BaseReg == PointerReg &&
+          Offset < PageSize && MI->getDesc().getNumDefs() == 1 &&
+          IsSafeToReorder(MI)) {
+        NullCheckList.emplace_back(MI, MBP.ConditionDef, &MBB, NotNullSucc,
                                    NullSucc);
         return true;
       }
 
+    // MI did not match our criteria for conversion to a trapping load.  Check
+    // if we can continue looking.
+
+    if (MI->mayStore() || MI->hasUnmodeledSideEffects())
+      return false;
+
+    for (auto *MMO : MI->memoperands())
+      // Right now we don't want to worry about LLVM's memory model.
+      if (!MMO->isUnordered())
+        return false;
+
+    // It _may_ be okay to reorder a later load instruction across MI.  Make a
+    // note of its operands so that we can make the legality check if we find a
+    // suitable load instruction:
+
+    auto RecordOperand = [&](const MachineOperand &MO) {
+      if (!MO.isReg() || !MO.getReg())
+        return;
+
+      if (MO.isDef())
+        RegDefs.insert(MO.getReg());
+      else
+        RegUses.insert(MO.getReg());
+    };
+
+    for (auto &MO : MI->defs())
+      RecordOperand(MO);
+
+    for (auto &IMO : MI->implicit_operands())
+      RecordOperand(IMO);
+  }
+
   return false;
 }
 
 /// Wrap a machine load instruction, LoadMI, into a FAULTING_LOAD_OP machine
 /// instruction.  The FAULTING_LOAD_OP instruction does the same load as LoadMI
 /// (defining the same register), and branches to HandlerLabel if the load
 /// faults.  The FAULTING_LOAD_OP instruction is inserted at the end of MBB.
 MachineInstr *ImplicitNullChecks::insertFaultingLoad(MachineInstr *LoadMI,

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

  is_null:
   ret i32 42
 
  not_null:
   %t = load i32, i32* %x
   ret i32 %t
 }
 
+define i32 @imp_null_check_no_hoist_over_acquire_load(i32* %x, i32* %y) {
+; We cannot hoist %t1 over %t0 since %t0 is an acquire load
+ 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:
+  %t0 = load atomic i32, i32* %y acquire, align 4
+  %t1 = load i32, i32* %x
+  %p = add i32 %t0, %t1
+  ret i32 %p
+}
+
+define i32 @imp_null_check_add_result(i32* %x, i32* %y) {
+; This will codegen to:
+;
+;   movl    (%rsi), %eax
+;   addl    (%rdi), %eax
+;
+; The load instruction we wish to hoist is the addl, but there is a
+; write-after-write hazard preventing that from happening.  We could
+; get fancy here and exploit the commutativity of addition, but right
+; now -implicit-null-checks isn't that smart.
+;
+
+ 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:
+  %t0 = load i32, i32* %y
+  %t1 = load i32, i32* %x
+  %p = add i32 %t0, %t1
+  ret i32 %p
+}
+
 !0 = !{}

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

is_null:
   ret i32 42
 
  not_null:
   %t = load i32, i32* %x
   %p1 = add i32 %t, %p
   ret i32 %p1
 }
 
+define i32 @imp_null_check_hoist_over_unrelated_load(i32* %x, i32* %y, i32* %z) {
+; CHECK-LABEL: _imp_null_check_hoist_over_unrelated_load:
+; CHECK: Ltmp7:
+; CHECK: movl (%rdi), %eax
+; CHECK: movl (%rsi), %ecx
+; CHECK: movl %ecx, (%rdx)
+; CHECK: retq
+; CHECK: Ltmp6:
+; 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:
+  %t0 = load i32, i32* %y
+  %t1 = load i32, i32* %x
+  store i32 %t0, i32* %z
+  ret i32 %t1
+}
+
 !0 = !{}
 
 ; CHECK-LABEL: __LLVM_FaultMaps:
 
 ; Version:
 ; CHECK-NEXT: .byte 1
 
 ; Reserved x2
 ; CHECK-NEXT: .byte 0
 ; CHECK-NEXT: .short 0
 
 ; # functions:
-; CHECK-NEXT: .long 3
+; CHECK-NEXT: .long 4
 
 ; 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 Ltmp3-_imp_null_check_gep_load
 ; Fault[0].HandlerOffset:
 ; CHECK-NEXT: .long Ltmp2-_imp_null_check_gep_load
 
 ; 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 Ltmp7-_imp_null_check_hoist_over_unrelated_load
+; Fault[0].HandlerOffset:
+; CHECK-NEXT: .long Ltmp6-_imp_null_check_hoist_over_unrelated_load
+
+; FunctionAddr:
 ; CHECK-NEXT: .quad _imp_null_check_load
 ; NumFaultingPCs
 ; CHECK-NEXT: .long 1
 ; Reserved:
 ; CHECK-NEXT: .long 0
 ; Fault[0].Type:
 ; CHECK-NEXT: .long 1
 ; Fault[0].FaultOffset:
 ; CHECK-NEXT: .long Ltmp1-_imp_null_check_load
 ; Fault[0].HandlerOffset:
 ; CHECK-NEXT: .long Ltmp0-_imp_null_check_load
 
 ; OBJDUMP: FaultMap table:
 ; OBJDUMP-NEXT: Version: 0x1
-; OBJDUMP-NEXT: NumFunctions: 3
+; OBJDUMP-NEXT: NumFunctions: 4
 ; 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: 7
+; OBJDUMP-NEXT: FunctionAddress: 0x000000, NumFaultingPCs: 1
 ; OBJDUMP-NEXT: Fault kind: FaultingLoad, faulting PC offset: 0, handling PC offset: 3