[PM/AA] Port alias analysis evaluator to the new pass manager, and use it to actually test the new pass manager AA wiring.

[chandlerc]

Summary

This patch was extracted from the (somewhat too large) D12357 and
rebosed on top of the slightly different design of the new pass manager
AA wiring that I just landed. With this we can start testing the AA in
a thorough way with the new pass manager.

Some minor cleanups to the code in the pass was necessitated here, but
otherwise it is a very minimal change.

Let me know if you want me to just do subsequent changes porting AA-related
things with post-commit review. They're fairly noisy in terms of changed lines,
but are getting highly mechanical and the interesting design decisions are
dwindling rapidly.

[reames]

LGTM w/minor comment.

include/llvm/Analysis/AliasAnalysisEvaluator.h

13 ↗

(On Diff #48294)

A bit more detail would be good here. When first reading, I wasn't sure why I might use such a thing.

Something along the lines of "The result is a set of statistics about the number of results for each alias result type and modref state returned. This can be used to evaluate a change in alias analysis implementation, algorithm, or pass ordering."

[chandlerc]

This is just moving an existing (perhaps bad) comment around. Gonna land the refactoring, happy to keep chatting about how to document this better.

I know I've been doing some tidying and spring cleaning as I refactor things some of the time, I just hadn't here because frankly I'm not an expert on this code and so it seemed like it might better come from others more familiar with it.

include/llvm/Analysis/AliasAnalysisEvaluator.h

13 ↗

(On Diff #48294)

This is just a move of the original comment. I'd love to have an improvement such as what you suggest, but it probably shouldn't be this patch. Would you be willing to send the improvement? If not, I guess I can. But I don't actually know anything about this pass, so I'm somewhat operating from ignorance here...

llvm/trunk/include/llvm/Analysis/AliasAnalysisEvaluator.h

+//===- AliasAnalysisEvaluator.h - Alias Analysis Accuracy Evaluator -------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a simple N^2 alias analysis accuracy evaluator.
+// Basically, for each function in the program, it simply queries to see how the
+// alias analysis implementation answers alias queries between each pair of
+// pointers in the function.
+//
+// This is inspired and adapted from code by: Naveen Neelakantam, Francesco
+// Spadini, and Wojciech Stryjewski.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ALIASANALYSISEVALUATOR_H
+#define LLVM_ANALYSIS_ALIASANALYSISEVALUATOR_H
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+class AAResults;
+
+class AAEvaluator {
+  int64_t FunctionCount;
+  int64_t NoAliasCount, MayAliasCount, PartialAliasCount, MustAliasCount;
+  int64_t NoModRefCount, ModCount, RefCount, ModRefCount;
+
+public:
+  AAEvaluator()
+      : FunctionCount(), NoAliasCount(), MayAliasCount(), PartialAliasCount(),
+        MustAliasCount(), NoModRefCount(), ModCount(), RefCount(),
+        ModRefCount() {}
+  AAEvaluator(AAEvaluator &&Arg)
+      : FunctionCount(Arg.FunctionCount), NoAliasCount(Arg.NoAliasCount),
+        MayAliasCount(Arg.MayAliasCount),
+        PartialAliasCount(Arg.PartialAliasCount),
+        MustAliasCount(Arg.MustAliasCount), NoModRefCount(Arg.NoModRefCount),
+        ModCount(Arg.ModCount), RefCount(Arg.RefCount),
+        ModRefCount(Arg.ModRefCount) {
+    Arg.FunctionCount = 0;
+  }
+  ~AAEvaluator();
+
+  static StringRef name() { return "AAEvaluator"; }
+
+  /// \brief Run the pass over the function.
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+private:
+  // Allow the legacy pass to run this using an internal API.
+  friend class AAEvalLegacyPass;
+
+  void runInternal(Function &F, AAResults &AA);
+};
+
+/// Create a wrapper of the above for the legacy pass manager.
+FunctionPass *createAAEvalPass();
+
+}
+
+#endif

llvm/trunk/include/llvm/Analysis/Passes.h

namespace llvm {
   class ImmutablePass;
   class LoopPass;
   class ModulePass;
   class Pass;
   class PassInfo;
 
   //===--------------------------------------------------------------------===//
   //
-  // createAAEvalPass - This pass implements a simple N^2 alias analysis
-  // accuracy evaluator.
-  //
-  FunctionPass *createAAEvalPass();
-
-  //===--------------------------------------------------------------------===//
-  //
   // createObjCARCAAWrapperPass - This pass implements ObjC-ARC-based
   // alias analysis.
   //
   ImmutablePass *createObjCARCAAWrapperPass();
 
   FunctionPass *createPAEvalPass();
 
   //===--------------------------------------------------------------------===//

llvm/trunk/include/llvm/InitializePasses.h

 void initializeAnalysis(PassRegistry&);
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeCodeGen(PassRegistry&);
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
-void initializeAAEvalPass(PassRegistry&);
+void initializeAAEvalLegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsPass(PassRegistry&);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeBDCEPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlwaysInlinerPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAtomicExpandPass(PassRegistry&);
 void initializeSampleProfileLoaderPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LINKALLPASSES_H
 #define LLVM_LINKALLPASSES_H
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasSetTracker.h"
+#include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAliasAnalysis.h"
 #include "llvm/Analysis/CallPrinter.h"
 #include "llvm/Analysis/DomPrinter.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IntervalPartition.h"
 #include "llvm/Analysis/Lint.h"
 #include "llvm/Analysis/Passes.h"

llvm/trunk/lib/Analysis/AliasAnalysisEvaluator.cpp

 //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
-//
-// This file implements a simple N^2 alias analysis accuracy evaluator.
-// Basically, for each function in the program, it simply queries to see how the
-// alias analysis implementation answers alias queries between each pair of
-// pointers in the function.
-//
-// This is inspired and adapted from code by: Naveen Neelakantam, Francesco
-// Spadini, and Wojciech Stryjewski.
-//
-//===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/InstIterator.h"

 
 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
 
 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
 
-namespace {
-  class AAEval : public FunctionPass {
-    unsigned NoAliasCount, MayAliasCount, PartialAliasCount, MustAliasCount;
-    unsigned NoModRefCount, ModCount, RefCount, ModRefCount;
-
-  public:
-    static char ID; // Pass identification, replacement for typeid
-    AAEval() : FunctionPass(ID) {
-      initializeAAEvalPass(*PassRegistry::getPassRegistry());
-    }
-
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.addRequired<AAResultsWrapperPass>();
-      AU.setPreservesAll();
-    }
-
-    bool doInitialization(Module &M) override {
-      NoAliasCount = MayAliasCount = PartialAliasCount = MustAliasCount = 0;
-      NoModRefCount = ModCount = RefCount = ModRefCount = 0;
-
-      if (PrintAll) {
-        PrintNoAlias = PrintMayAlias = true;
-        PrintPartialAlias = PrintMustAlias = true;
-        PrintNoModRef = PrintMod = PrintRef = PrintModRef = true;
-      }
-      return false;
-    }
-
-    bool runOnFunction(Function &F) override;
-    bool doFinalization(Module &M) override;
-  };
-}
-
-char AAEval::ID = 0;
-INITIALIZE_PASS_BEGIN(AAEval, "aa-eval",
-                "Exhaustive Alias Analysis Precision Evaluator", false, true)
-INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
-INITIALIZE_PASS_END(AAEval, "aa-eval",
-                "Exhaustive Alias Analysis Precision Evaluator", false, true)
-
-FunctionPass *llvm::createAAEvalPass() { return new AAEval(); }
-
 static void PrintResults(const char *Msg, bool P, const Value *V1,
                          const Value *V2, const Module *M) {
-  if (P) {
+  if (PrintAll || P) {
     std::string o1, o2;
     {
       raw_string_ostream os1(o1), os2(o2);
       V1->printAsOperand(os1, true, M);
       V2->printAsOperand(os2, true, M);
     }
     
     if (o2 < o1)
       std::swap(o1, o2);
     errs() << "  " << Msg << ":\t"
            << o1 << ", "
            << o2 << "\n";
   }
 }
 
 static inline void
 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr,
                    Module *M) {
-  if (P) {
+  if (PrintAll || P) {
     errs() << "  " << Msg << ":  Ptr: ";
     Ptr->printAsOperand(errs(), true, M);
     errs() << "\t<->" << *I << '\n';
   }
 }
 
 static inline void
 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB,
                    Module *M) {
-  if (P) {
+  if (PrintAll || P) {
     errs() << "  " << Msg << ": " << *CSA.getInstruction()
            << " <-> " << *CSB.getInstruction() << '\n';
   }
 }
 
 static inline void
 PrintLoadStoreResults(const char *Msg, bool P, const Value *V1,
                       const Value *V2, const Module *M) {
-  if (P) {
+  if (PrintAll || P) {
     errs() << "  " << Msg << ": " << *V1
            << " <-> " << *V2 << '\n';
   }
 }
 
 static inline bool isInterestingPointer(Value *V) {
   return V->getType()->isPointerTy()
       && !isa<ConstantPointerNull>(V);
 }
 
-bool AAEval::runOnFunction(Function &F) {
+PreservedAnalyses AAEvaluator::run(Function &F, AnalysisManager<Function> *AM) {
+  runInternal(F, AM->getResult<AAManager>(F));
+  return PreservedAnalyses::all();
+}
+
+void AAEvaluator::runInternal(Function &F, AAResults &AA) {
   const DataLayout &DL = F.getParent()->getDataLayout();
-  AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
+
+  ++FunctionCount;
 
   SetVector<Value *> Pointers;
   SmallSetVector<CallSite, 16> CallSites;
   SetVector<Value *> Loads;
   SetVector<Value *> Stores;
 
   for (auto &I : F.args())
     if (I.getType()->isPointerTy())    // Add all pointer arguments.
if (auto CS = CallSite(&Inst)) {
       // Consider all operands.
       for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
            OI != OE; ++OI)
         if (isInterestingPointer(*OI))
           Pointers.insert(*OI);
     }
   }
 
-  if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias ||
-      PrintNoModRef || PrintMod || PrintRef || PrintModRef)
+  if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias ||
+      PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef)
     errs() << "Function: " << F.getName() << ": " << Pointers.size()
            << " pointers, " << CallSites.size() << " call sites\n";
 
   // iterate over the worklist, and run the full (n^2)/2 disambiguations
   for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
        I1 != E; ++I1) {
     uint64_t I1Size = MemoryLocation::UnknownSize;
     Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
for (auto D = CallSites.begin(); D != Ce; ++D) {
         break;
       case MRI_ModRef:
         PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent());
         ++ModRefCount;
         break;
       }
     }
   }
-
-  return false;
 }
 
-static void PrintPercent(unsigned Num, unsigned Sum) {
-  errs() << "(" << Num*100ULL/Sum << "."
-         << ((Num*1000ULL/Sum) % 10) << "%)\n";
+static void PrintPercent(int64_t Num, int64_t Sum) {
+  errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
+         << "%)\n";
 }
 
-bool AAEval::doFinalization(Module &M) {
-  unsigned AliasSum =
+AAEvaluator::~AAEvaluator() {
+  if (FunctionCount == 0)
+    return;
+
+  int64_t AliasSum =
       NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
   errs() << "===== Alias Analysis Evaluator Report =====\n";
   if (AliasSum == 0) {
     errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
   } else {
     errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
     errs() << "  " << NoAliasCount << " no alias responses ";
     PrintPercent(NoAliasCount, AliasSum);
     errs() << "  " << MayAliasCount << " may alias responses ";
     PrintPercent(MayAliasCount, AliasSum);
     errs() << "  " << PartialAliasCount << " partial alias responses ";
     PrintPercent(PartialAliasCount, AliasSum);
     errs() << "  " << MustAliasCount << " must alias responses ";
     PrintPercent(MustAliasCount, AliasSum);
     errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
            << NoAliasCount * 100 / AliasSum << "%/"
            << MayAliasCount * 100 / AliasSum << "%/"
            << PartialAliasCount * 100 / AliasSum << "%/"
            << MustAliasCount * 100 / AliasSum << "%\n";
   }
 
   // Display the summary for mod/ref analysis
-  unsigned ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount;
+  int64_t ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount;
   if (ModRefSum == 0) {
     errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no "
               "mod/ref!\n";
   } else {
     errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
     errs() << "  " << NoModRefCount << " no mod/ref responses ";
     PrintPercent(NoModRefCount, ModRefSum);
     errs() << "  " << ModCount << " mod responses ";
     PrintPercent(ModCount, ModRefSum);
     errs() << "  " << RefCount << " ref responses ";
     PrintPercent(RefCount, ModRefSum);
     errs() << "  " << ModRefCount << " mod & ref responses ";
     PrintPercent(ModRefCount, ModRefSum);
     errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
            << NoModRefCount * 100 / ModRefSum << "%/"
            << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
            << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
   }
+}
+
+namespace llvm {
+class AAEvalLegacyPass : public FunctionPass {
+  std::unique_ptr<AAEvaluator> P;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  AAEvalLegacyPass() : FunctionPass(ID) {
+    initializeAAEvalLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
 
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AAResultsWrapperPass>();
+    AU.setPreservesAll();
+  }
+
+  bool doInitialization(Module &M) override {
+    P.reset(new AAEvaluator());
     return false;
   }
+
+  bool runOnFunction(Function &F) override {
+    P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
+    return false;
+  }
+  bool doFinalization(Module &M) override {
+    P.reset();
+    return false;
+  }
+};
+}
+
+char AAEvalLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval",
+                      "Exhaustive Alias Analysis Precision Evaluator", false,
+                      true)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_END(AAEvalLegacyPass, "aa-eval",
+                    "Exhaustive Alias Analysis Precision Evaluator", false,
+                    true)
+
+FunctionPass *llvm::createAAEvalPass() { return new AAEvalLegacyPass(); }

llvm/trunk/lib/Analysis/Analysis.cpp

 #include "llvm/PassRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstring>
 
 using namespace llvm;
 
 /// initializeAnalysis - Initialize all passes linked into the Analysis library.
 void llvm::initializeAnalysis(PassRegistry &Registry) {
-  initializeAAEvalPass(Registry);
+  initializeAAEvalLegacyPassPass(Registry);
   initializeAliasSetPrinterPass(Registry);
   initializeBasicAAWrapperPassPass(Registry);
   initializeBlockFrequencyInfoWrapperPassPass(Registry);
   initializeBranchProbabilityInfoWrapperPassPass(Registry);
   initializeCallGraphWrapperPassPass(Registry);
   initializeCallGraphPrinterPass(Registry);
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);

llvm/trunk/lib/Passes/PassBuilder.cpp

 /// static pass registry as well as related functionality. It also provides
 /// helpers to aid in analyzing, debugging, and testing passes and pass
 /// pipelines.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"

llvm/trunk/lib/Passes/PassRegistry.def

 #endif
 FUNCTION_ALIAS_ANALYSIS("basic-aa", BasicAA())
 #undef FUNCTION_ALIAS_ANALYSIS
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS
 #define FUNCTION_PASS(NAME, CREATE_PASS)
 #endif
+FUNCTION_PASS("aa-eval", AAEvaluator())
 FUNCTION_PASS("adce", ADCEPass())
 FUNCTION_PASS("early-cse", EarlyCSEPass())
 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))
 FUNCTION_PASS("simplify-cfg", SimplifyCFGPass())
 FUNCTION_PASS("sroa", SROA())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 #undef FUNCTION_PASS

llvm/trunk/test/Analysis/BasicAA/phi-aa.ll

 ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; rdar://7282591
 
 @X = common global i32 0
 @Y = common global i32 0
 @Z = common global i32 0

llvm/trunk/unittests/Analysis/MixedTBAATest.cpp

 //===--- MixedTBAATest.cpp - Mixed TBAA unit tests ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/CommandLine.h"