Introduce print-memderefs to test isDereferenceablePointer

[artagnon]

Summary

Since testing the function indirectly is tricky, introduce a direct
print-memderefs pass, in the same spirit as print-memdeps, which prints
dereferenceability information matched by FileCheck.

[reames]

I'd suggest splitting this into two patches: adding the new analysis, adding the new optimization and testing it. If you really didn't want to for some reason, it's not that big a deal, but it would make it easier to review quickly.

include/llvm/IR/InstIterator.h

130

I might call this inst_range. I'm usually not a fan of extra verbosity, but I see potential confusion resulting from a such short relatively common name being added to the llvm namespace.

lib/Analysis/MemDepPrinter.cpp

147

Please separate this refactoring into a separate change.

lib/Analysis/MemDerefPrinter.cpp

1

Please split the introduction of the printer and one or two example tests into it's own change. I'll be happy to LGTM that one quickly.

22

Why do you need to capture F?

24

Why is this enum needed?

43

You should also clear your small vector. (I think)

lib/IR/Value.cpp

575

I'd suggest using isGCRelocate here.

[artagnon]

Split print-memderefs into its own change. Fix all-round sloppiness.

[reames]

LGTM.

For future reference, I read your comment "Split print-memderefs into its own change." as meaning that you'd split the MemDerefPrinter into a separate review thread. Since the original semantic change (which I thought was this thread) was blocked on that, I deleted the email without looking further.

lib/Analysis/MemDerefPrinter.cpp

49

It would be better to get the data layout if available and use it here. You'll get far more precise results.

(This can be separate change if desired.)

include/llvm/Analysis/Passes.h

namespace llvm {
   // createMemDepPrinter - This pass exhaustively collects all memdep
   // information and prints it with -analyze.
   //
   FunctionPass *createMemDepPrinter();
 
   // createJumpInstrTableInfoPass - This creates a pass that stores information
   // about the jump tables created by JumpInstrTables
   ImmutablePass *createJumpInstrTableInfoPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createMemDerefPrinter - This pass collects memory dereferenceability
+  // information and prints it with -analyze.
+  //
+  FunctionPass *createMemDerefPrinter();
+
 }
 
 #endif

include/llvm/IR/InstIterator.h

typedef InstIterator<iplist<BasicBlock>,
                      Instruction> inst_iterator;
 typedef InstIterator<const iplist<BasicBlock>,
                      Function::const_iterator,
                      BasicBlock::const_iterator,
                      const Instruction> const_inst_iterator;
 
 inline inst_iterator inst_begin(Function *F) { return inst_iterator(*F); }
 inline inst_iterator inst_end(Function *F)   { return inst_iterator(*F, true); }
+inline iterator_range<inst_iterator> insts(Function *F) {
+  return iterator_range<inst_iterator>(inst_begin(F), inst_end(F));
+}
 inline const_inst_iterator inst_begin(const Function *F) {
   return const_inst_iterator(*F);
 }
 inline const_inst_iterator inst_end(const Function *F) {
   return const_inst_iterator(*F, true);
 }
+inline iterator_range<const_inst_iterator> insts(const Function *F) {
+  return iterator_range<const_inst_iterator>(inst_begin(F), inst_end(F));
+}
 inline inst_iterator inst_begin(Function &F) { return inst_iterator(F); }
 inline inst_iterator inst_end(Function &F)   { return inst_iterator(F, true); }
+inline iterator_range<inst_iterator> insts(Function &F) {
+  return iterator_range<inst_iterator>(inst_begin(F), inst_end(F));
+}
 inline const_inst_iterator inst_begin(const Function &F) {
   return const_inst_iterator(F);
 }
 inline const_inst_iterator inst_end(const Function &F) {
   return const_inst_iterator(F, true);
 }
+inline iterator_range<const_inst_iterator> insts(const Function &F) {
+  return iterator_range<const_inst_iterator>(inst_begin(F), inst_end(F));
+}
 
 } // End llvm namespace
 
 #endif

include/llvm/InitializePasses.h

 void initializeMachineModuleInfoPass(PassRegistry&);
 void initializeMachineRegionInfoPassPass(PassRegistry&);
 void initializeMachineSchedulerPass(PassRegistry&);
 void initializeMachineSinkingPass(PassRegistry&);
 void initializeMachineTraceMetricsPass(PassRegistry&);
 void initializeMachineVerifierPassPass(PassRegistry&);
 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
+void initializeMemDerefPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
 void initializeObjCARCAliasAnalysisPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createInstructionSimplifierPass();
       (void) llvm::createLoopVectorizePass();
       (void) llvm::createSLPVectorizerPass();
       (void) llvm::createBBVectorizePass();
       (void) llvm::createPartiallyInlineLibCallsPass();
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
       (void) llvm::createRewriteSymbolsPass();
+      (void) llvm::createMemDerefPrinter();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolution();
       ((llvm::Function*)nullptr)->viewCFGOnly();
       llvm::RGPassManager RGM;
       ((llvm::RegionPass*)nullptr)->runOnRegion((llvm::Region*)nullptr, RGM);
       llvm::AliasSetTracker X(*(llvm::AliasAnalysis*)nullptr);
       X.add(nullptr, 0, llvm::AAMDNodes()); // for -print-alias-sets
     }
   } ForcePassLinking; // Force link by creating a global definition.
 }
 
 #endif

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeJumpInstrTableInfoPass(Registry);
   initializeLazyValueInfoPass(Registry);
   initializeLibCallAliasAnalysisPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
+  initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializePostDominatorTreePass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   LazyValueInfo.cpp
   LibCallAliasAnalysis.cpp
   LibCallSemantics.cpp
   Lint.cpp
   Loads.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MemDepPrinter.cpp
+  MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp
   ModuleDebugInfoPrinter.cpp
   NoAliasAnalysis.cpp
   PHITransAddr.cpp
   PostDominators.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp

lib/Analysis/MemDepPrinter.cpp

for (const_inst_iterator I = inst_begin(*F), E = inst_end(*F); I != E; ++I) {
     const Instruction *Inst = &*I;
 
     DepSetMap::const_iterator DI = Deps.find(Inst);
     if (DI == Deps.end())
       continue;
 
     const DepSet &InstDeps = DI->second;
 
-    for (DepSet::const_iterator I = InstDeps.begin(), E = InstDeps.end();
-         I != E; ++I) {
-      const Instruction *DepInst = I->first.getPointer();
-      DepType type = I->first.getInt();
-      const BasicBlock *DepBB = I->second;
+    for (auto I: InstDeps) {
+      const Instruction *DepInst = I.first.getPointer();
+      DepType type = I.first.getInt();
+      const BasicBlock *DepBB = I.second;
 
       OS << "    ";
       OS << DepTypeStr[type];
       if (DepBB) {
         OS << " in block ";
         DepBB->printAsOperand(OS, /*PrintType=*/false, M);
       }
       if (DepInst) {

lib/Analysis/MemDerefPrinter.cpp

+//===- MemDerefPrinter.cpp - Printer for isDereferenceablePointer ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/Passes.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+namespace {
+  struct MemDerefPrinter : public FunctionPass {
+    const Function *F;
+
+    enum DepType {
+      Clobber = 0,
+      Def,
+      NonFuncLocal,
+      Unknown
+    };
+
+    SmallVector<Value *, 4> Vec;
+
+    static char ID; // Pass identifcation, replacement for typeid
+    MemDerefPrinter() : FunctionPass(ID) {
+      initializeMemDerefPrinterPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F) override;
+
+    void print(raw_ostream &OS, const Module * = nullptr) const override;
+
+    void releaseMemory() override {
+      F = nullptr;
+    }
+  };
+}
+
+char MemDerefPrinter::ID = 0;
+INITIALIZE_PASS(MemDerefPrinter, "print-memderefs",
+                "Memory Dereferenciblity of pointers in function", false, true)
+
+FunctionPass *llvm::createMemDerefPrinter() {
+  return new MemDerefPrinter();
+}
+
+bool MemDerefPrinter::runOnFunction(Function &F) {
+  this->F = &F;
+
+  for (auto &I: insts(F)) {
+    if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
+      Value *PO = LI->getPointerOperand();
+      if (PO->isDereferenceablePointer(nullptr))
+        Vec.push_back(PO);
+    }
+  }
+  return false;
+}
+
+void MemDerefPrinter::print(raw_ostream &OS, const Module *M) const {
+  OS << "The following are dereferenceable:\n";
+  for (auto &V: Vec) {
+    V->print(OS);
+    OS << "\n\n";
+  }
+}

lib/IR/Value.cpp

 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/Statepoint.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include <algorithm>
 using namespace llvm;
 
for (User::const_op_iterator I = GEP->op_begin()+1,
         return false;
       if (CI->getZExtValue() >= ATy->getNumElements())
         return false;
     }
     // Indices check out; this is dereferenceable.
     return true;
   }
 
+  // For gc.relocate, look through relocations
+  if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+    if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) {
+      GCRelocateOperands RelocateInst(I);
+      return isDereferenceablePointer(RelocateInst.derivedPtr(), DL, Visited);
+    }
+
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     return isDereferenceablePointer(ASC->getOperand(0), DL, Visited);
 
   // If we don't know, assume the worst.
   return false;
 }
 
 bool Value::isDereferenceablePointer(const DataLayout *DL) const {

test/Analysis/ValueTracking/memory-dereferenceable.ll

+; RUN: opt -print-memderefs -analyze -S <%s | FileCheck %s
+
+; Uses the print-deref (+ analyze to print) pass to run
+; isDereferenceablePointer() on many load instruction operands
+
+declare zeroext i1 @return_i1()
+
+@globalstr = global [6 x i8] c"hello\00"
+
+define void @test(i32 addrspace(1)* byval %dparam) {
+; CHECK: The following are dereferenceable:
+; CHECK: %globalptr
+; CHECK: %alloca
+; CHECK: %dparam
+; CHECK: %relocate
+; CHECK-NOT: %nparam
+entry:
+    %globalptr = getelementptr inbounds [6 x i8]* @globalstr, i32 0, i32 0
+    %load1 = load i8* %globalptr
+    %alloca = alloca i1
+    %load2 = load i1* %alloca
+    %load3 = load i32 addrspace(1)* %dparam
+    %tok = tail call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 addrspace(1)* %dparam)
+    %relocate = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %tok, i32 4, i32 4)
+    %load4 = load i32 addrspace(1)* %relocate
+    %nparam = getelementptr i32 addrspace(1)* %dparam, i32 5
+    %load5 = load i32 addrspace(1)* %nparam
+    ret void
+}
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()*, i32, i32, ...)
+declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32, i32, i32)
 No newline at end of file