Add a pass to eliminate nullchecks after objects have been dereferenced (WIP)

[fhahn]

Summary

This patch adds a new pass that keeps track of dereferenced objects and
eliminates null checks that are dominated by a memory instruction that
dereferences the underlying object.

Currently this works by collecting all object dereferences and null
checks with known underlying objects. Those are then sorted by DomTree DFS
numbers of their containing blocks and the relative order in a basic
block. Then we iterate over the list and keep track of the currently
dereferenced objects. We remove objects once we encounter a block that
is not dominated by the dereference instruction.

Currently this is O(N * log(N)), where N is the number of memory
instructions that dereference a known underlying object plus number of
null checks of known underlying objects. As it is, the compile time
impact is +0.33% geomean for -O3 ThinLTO
(http://llvm-compile-time-tracker.com/compare.php?from=a5bd75aab861df8cea8d1c6b88e764ad4a2c09ea&to=c02c43b0fe6648772d70c3f3de41a9e5e29e0628&stat=instructions)

It is probably possible to improve that if we would directly traverse
the dominator tree.

This currently results in 1924 compare simplifications on
MultiSource/SPEC2000/SPEC2006 with -O3 -flto.

[nikic]

It is probably possible to improve that if we would directly traverse the dominator tree.

Yes, I think that would make more sense. Another possibility would be to traverse in RPO and intersect nonnull objects from visited predecessors (I think that's legal, because these must be nonnull on backedges as well). That would come at the cost of set intersections though.

llvm/lib/Transforms/Scalar/DereferenceNullCheckElimination.cpp

170

For memory intrinsics, it's also necessary to check that the length is non-zero. Per LangRef:

If “len” is 0, the pointers may be NULL or dangling. However, they must still be appropriately aligned.

llvm/include/llvm/InitializePasses.h

 void initializeModuleSummaryIndexWrapperPassPass(PassRegistry&);
 void initializeModuloScheduleTestPass(PassRegistry&);
 void initializeMustExecutePrinterPass(PassRegistry&);
 void initializeMustBeExecutedContextPrinterPass(PassRegistry&);
 void initializeNameAnonGlobalLegacyPassPass(PassRegistry&);
 void initializeUniqueInternalLinkageNamesLegacyPassPass(PassRegistry &);
 void initializeNaryReassociateLegacyPassPass(PassRegistry&);
 void initializeNewGVNLegacyPassPass(PassRegistry&);
+void initializeNullCheckEliminationPass(PassRegistry &);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializeOptimizationRemarkEmitterWrapperPassPass(PassRegistry&);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry&);

llvm/include/llvm/Transforms/Scalar.h

 //
 // GVN - This pass performs global value numbering and redundant load
 // elimination cotemporaneously.
 //
 FunctionPass *createNewGVNPass();
 
 //===----------------------------------------------------------------------===//
 //
+//
+FunctionPass *createNullCheckEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
 // DivRemPairs - Hoist/decompose integer division and remainder instructions.
 //
 FunctionPass *createDivRemPairsPass();
 
 //===----------------------------------------------------------------------===//
 //
 // MemCpyOpt - This pass performs optimizations related to eliminating memcpy
 // calls and/or combining multiple stores into memset's.

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

if (OptLevel > 1) {
     }
   }
 
   if (OptLevel > 1) {
     // Speculative execution if the target has divergent branches; otherwise nop.
     MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass());
 
     MPM.add(createJumpThreadingPass());         // Thread jumps.
+    MPM.add(createNullCheckEliminationPass());
     MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   }
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   // Combine silly seq's
   if (OptLevel > 2)
     MPM.add(createAggressiveInstCombinerPass());
   MPM.add(createInstructionCombiningPass());
   if (SizeLevel == 0 && !DisableLibCallsShrinkWrap)
void PassManagerBuilder::addFunctionSimplificationPasses(
   MPM.add(createBitTrackingDCEPass());        // Delete dead bit computations
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   MPM.add(createInstructionCombiningPass());
   addExtensionsToPM(EP_Peephole, MPM);
   if (OptLevel > 1) {
     MPM.add(createJumpThreadingPass());         // Thread jumps
+    MPM.add(createNullCheckEliminationPass());
     MPM.add(createCorrelatedValuePropagationPass());
     MPM.add(createDeadStoreEliminationPass());  // Delete dead stores
     MPM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
   }
 
   addExtensionsToPM(EP_ScalarOptimizerLate, MPM);
 
   if (RerollLoops)
if (OptLevel > 1 && ExtraVectorizerPasses) {
     // At higher optimization levels, try to clean up any runtime overlap and
     // alignment checks inserted by the vectorizer. We want to track correllated
     // runtime checks for two inner loops in the same outer loop, fold any
     // common computations, hoist loop-invariant aspects out of any outer loop,
     // and unswitch the runtime checks if possible. Once hoisted, we may have
     // dead (or speculatable) control flows or more combining opportunities.
     MPM.add(createEarlyCSEPass());
     MPM.add(createCorrelatedValuePropagationPass());
+    MPM.add(createNullCheckEliminationPass());
     MPM.add(createInstructionCombiningPass());
     MPM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
     MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3, DivergentTarget));
     MPM.add(createCFGSimplificationPass());
     MPM.add(createInstructionCombiningPass());
   }
 
   // Cleanup after loop vectorization, etc. Simplification passes like CVP and

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   LowerMatrixIntrinsics.cpp
   LowerWidenableCondition.cpp
   MakeGuardsExplicit.cpp
   MemCpyOptimizer.cpp
   MergeICmps.cpp
   MergedLoadStoreMotion.cpp
   NaryReassociate.cpp
   NewGVN.cpp
+  DereferenceNullCheckElimination.cpp
   PartiallyInlineLibCalls.cpp
   PlaceSafepoints.cpp
   Reassociate.cpp
   Reg2Mem.cpp
   RewriteStatepointsForGC.cpp
   SCCP.cpp
   SROA.cpp
   Scalar.cpp

llvm/lib/Transforms/Scalar/DereferenceNullCheckElimination.cpp

+//===- LowerMatrixIntrinsics.cpp -  Lower matrix intrinsics -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/DebugCounter.h"
+#include "llvm/Transforms/Scalar.h"
+
+using namespace llvm;
+using namespace PatternMatch;
+
+#define DEBUG_TYPE "nullcheck-elimination"
+
+STATISTIC(NumCmpsRemoved, "Number of cmps simplified");
+
+struct CmpOrDeref {
+  unsigned NumIn;
+  unsigned NumOut;
+  Instruction *I;
+
+  CmpOrDeref(DomTreeNode *DTN, Instruction *I)
+      : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), I(I) {}
+};
+
+struct StackEntry {
+  unsigned NumIn;
+  unsigned NumOut;
+  const Value *Obj;
+
+  StackEntry(unsigned NumIn, unsigned NumOut, const Value *Obj)
+      : NumIn(NumIn), NumOut(NumOut), Obj(Obj) {}
+};
+
+struct UnderlyingObjCache {
+  const DataLayout &DL;
+  DenseMap<const Value *, const Value *> UnderlyingObjs;
+
+  UnderlyingObjCache(const DataLayout &DL) : DL(DL) {}
+
+  const Value *getUnderlyingObjFor(const Value *Ptr) {
+    auto I = UnderlyingObjs.insert({Ptr, nullptr});
+    if (I.second) {
+      const Value *UO = GetUnderlyingObject(Ptr, DL);
+      I.first->second = UO;
+    }
+
+    return I.first->second;
+  }
+};
+
+static bool eliminateNullChecks(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+  DT.updateDFSNumbers();
+  SmallVector<CmpOrDeref, 64> WorkList;
+
+  auto DL = F.getParent()->getDataLayout();
+  UnderlyingObjCache ObjCache(DL);
+  for (BasicBlock &BB : F) {
+    if (!DT.getNode(&BB))
+      continue;
+    auto *DTN = DT.getNode(&BB);
+    SmallPtrSet<const Value *, 16> UOInBlock;
+    for (auto &I : BB) {
+
+      CmpInst::Predicate Pred;
+      Value *Ptr;
+      if (match(&I, m_ICmp(Pred, m_Value(Ptr), m_Zero())) ||
+          match(&I, m_ICmp(Pred, m_Zero(), m_Value(Ptr)))) {
+        if (!I.getOperand(0)->getType()->isPointerTy())
+          continue;
+        if (Pred != CmpInst::ICMP_EQ && Pred != CmpInst::ICMP_NE)
+          continue;
+
+        if (!ObjCache.getUnderlyingObjFor(Ptr))
+          continue;
+
+        WorkList.emplace_back(DTN, &I);
+        continue;
+      }
+
+      auto MaybeMemLoc = MemoryLocation::getOrNone(&I);
+      if (!MaybeMemLoc)
+        continue;
+
+      auto *UO = ObjCache.getUnderlyingObjFor(MaybeMemLoc->Ptr);
+      if (!UOInBlock.insert(UO).second)
+        continue;
+
+      WorkList.emplace_back(DTN, &I);
+    }
+  }
+
+  sort(WorkList.begin(), WorkList.end(),
+       [](const CmpOrDeref &A, const CmpOrDeref &B) {
+         if (A.NumIn == B.NumIn && A.NumOut == B.NumOut) {
+           return A.I->comesBefore(B.I);
+         }
+         return A.NumIn < B.NumIn;
+       });
+
+  SmallVector<StackEntry, 16> DFSInStack;
+  DenseMap<Value *, unsigned> Value2Index;
+  SmallPtrSet<const Value *, 32> DereferencedObjs;
+  for (CmpOrDeref &CB : WorkList) {
+    while (!DFSInStack.empty()) {
+      auto &E = DFSInStack.back();
+      LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
+                        << "\n");
+      LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
+      bool IsDom = CB.NumIn >= E.NumIn && CB.NumOut <= E.NumOut;
+      if (IsDom)
+        break;
+      LLVM_DEBUG(dbgs() << "Removing " << *E.Obj << " "
+                        << "\n");
+      DereferencedObjs.erase(E.Obj);
+      DFSInStack.pop_back();
+    }
+
+    CmpInst::Predicate Pred;
+    Value *Ptr;
+    if (match(CB.I, m_ICmp(Pred, m_Value(Ptr), m_Zero())) ||
+        match(CB.I, m_ICmp(Pred, m_Zero(), m_Value(Ptr)))) {
+      assert(Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE);
+      const Value *UO = ObjCache.getUnderlyingObjFor(Ptr);
+      assert(UO);
+      if (Pred == CmpInst::ICMP_EQ && DereferencedObjs.count(UO)) {
+        CB.I->replaceAllUsesWith(ConstantInt::getFalse(CB.I->getType()));
+        CB.I->eraseFromParent();
+        NumCmpsRemoved++;
+      } else if (Pred == CmpInst::ICMP_NE && DereferencedObjs.count(UO)) {
+        CB.I->replaceAllUsesWith(ConstantInt::getTrue(CB.I->getType()));
+        CB.I->eraseFromParent();
+        NumCmpsRemoved++;
+      }
+      continue;
+    }
+
+    if (auto *MTI = dyn_cast<AnyMemTransferInst>(CB.I)) {
+      const Value *UOSrc =
+          ObjCache.getUnderlyingObjFor(MemoryLocation::getForSource(MTI).Ptr);
+      if (UOSrc) {
+        DereferencedObjs.insert(UOSrc);
+        DFSInStack.emplace_back(CB.NumIn, CB.NumOut, UOSrc);
+      }
+
+      const Value *UODest =
+          ObjCache.getUnderlyingObjFor(MemoryLocation::getForDest(MTI).Ptr);
+      if (UODest) {
+        DereferencedObjs.insert(UODest);
+        DFSInStack.emplace_back(CB.NumIn, CB.NumOut, UODest);
+      }
+    } else {
+      const Value *UO =
+          ObjCache.getUnderlyingObjFor(MemoryLocation::get(CB.I).Ptr);
+      assert(UO);
+      DereferencedObjs.insert(UO);
+      DFSInStack.emplace_back(CB.NumIn, CB.NumOut, UO);
+    }
+  }
+
+  return Changed;
+}
+
+namespace {
+
+class NullCheckElimination : public FunctionPass {
+public:
+  static char ID;
+
+  NullCheckElimination() : FunctionPass(ID) {
+    initializeNullCheckEliminationPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    return eliminateNullChecks(F, DT);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+  }
+};
+
+} // end anonymous namespace
+
+char NullCheckElimination::ID = 0;
+
+INITIALIZE_PASS_BEGIN(NullCheckElimination, "nullcheck-elimination",
+                      "Dereferenced Nullcheck Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
+INITIALIZE_PASS_END(NullCheckElimination, "nullcheck-elimination",
+                    "Dereferenced Nullcheck Elimination", false, false)
+
+FunctionPass *llvm::createNullCheckEliminationPass() {
+  return new NullCheckElimination();
+}

llvm/lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeDeadInstEliminationPass(Registry);
   initializeDivRemPairsLegacyPassPass(Registry);
   initializeScalarizerLegacyPassPass(Registry);
   initializeDSELegacyPassPass(Registry);
   initializeGuardWideningLegacyPassPass(Registry);
   initializeLoopGuardWideningLegacyPassPass(Registry);
   initializeGVNLegacyPassPass(Registry);
   initializeNewGVNLegacyPassPass(Registry);
+  initializeNullCheckEliminationPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeEarlyCSEMemSSALegacyPassPass(Registry);
   initializeMakeGuardsExplicitLegacyPassPass(Registry);
   initializeGVNHoistLegacyPassPass(Registry);
   initializeGVNSinkLegacyPassPass(Registry);
   initializeFlattenCFGPassPass(Registry);
   initializeIRCELegacyPassPass(Registry);
   initializeIndVarSimplifyLegacyPassPass(Registry);