[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 ↗

(On Diff #29288)

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 ↗

(On Diff #29288)

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 ↗

(On Diff #29288)

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

255 ↗

(On Diff #29288)

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 ↗

(On Diff #29288)

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?

llvm/trunk/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 hoist 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 IsSafeToHoist = [&](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 &&
+          IsSafeToHoist(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:
+
+    for (auto &MO : MI->operands()) {
+      if (!MO.isReg() || !MO.getReg())
+        continue;
+
+      if (MO.isDef())
+        RegDefs.insert(MO.getReg());
+      else
+        RegUses.insert(MO.getReg());
+    }
+  }
+
   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,

llvm/trunk/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 = !{}

llvm/trunk/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