[FunctionPropertiesAnalysis] Add `PreciseFunctionPropertiesAnalysis`

[uenoku]

Summary

This patch adds an another analysis pass which is similar to FunctionPropertiesAnalysis to get more function features like
numbers of instructions, basic blocks, and so on.

[uenoku]

@jdoerfert @mtrofin
Currently, I created a new pass because I'm not sure additional costs to calculates new features are affordable at MLInliner.
I'd like to put new features on FunctionPropertiesInfo if computational costs don't matter.

[uenoku]

And if you wish to add other features not listed here, please let me know.

[jdoerfert]

In D109661#2996443, @uenoku wrote:

@jdoerfert @mtrofin
Currently, I created a new pass because I'm not sure additional costs to calculates new features are affordable at MLInliner.
I'd like to put new features on FunctionPropertiesInfo if computational costs don't matter.

We could always make it an argument for the pass, e.g., when you create it you select the precision. Or, a command line option to get higher/lower precision. I think by default it should track all features and we can have subsets defined in a command line option if necessary. So if a user wants only 10 of the 40 features they add a selector into a command line enum and use it to skip features.

Wdyt?

[uenoku]

We could always make it an argument for the pass, e.g., when you create it you select the precision. Or, a command line option to get higher/lower precision. I think by default it should track all features and we can have subsets defined in a command line option if necessary. So if a user wants only 10 of the 40 features they add a selector into a command line enum and use it to skip features.

Creating an argument for the pass sounds good for me. IMHO, we don't need command option for the pass because I guess all use cases are from LLVM internal.

[mtrofin]

llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h

85

Nit: Is it "Precise" or "Detailed"?

101

please expose these through a getter, and hide the setter. It simplifies maintenance - easier to read and reason about code when it's easy to find where state can be mutated

[uenoku]

Add setters/getters and rename the class name.

[uenoku]

We could always make it an argument for the pass, e.g., when you create it you select the precision. Or, a command line option to get higher/lower precision. I think by default it should track all features and we can have subsets defined in a command line option if necessary. So if a user wants only 10 of the 40 features they add a selector into a command line enum and use it to skip features.

On the second thought, I think it is better to separate the pass.
Currently, FunctionPropertiesInfo is specialized for MLInliner and intended to be used practically.
We might want DetailedFunctionPropertiesInfo to be very rich analayzer which do not much care about the runtime cost.
Users can use the features of DetailedFunctionPropertiesInfo in experimentally until they find the essential features for their applications.

Wdyt?

[mtrofin]

llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h

92

does the visitor need to be public?

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

143

make 500 a flag (it's arbitrary otherwise. well... it's arbitrary after that, too, but at least it's user-controllable.). same with 15 below

156

style: capitalize variables. since you have an "I", maybe s/i/OpIdx

171

unsigned LoopDepth

[aidengrossman]

@uenoku I'm interested in getting this patch into upstream LLVM and addressing the other reviewer comments. Do you mind if I commandeer this revision and tag you as a co-author on the eventual commit?

I talked with @mtrofin briefly (only covering flags/separate pass), and the plan is as follows

• address remaining inline comments
• Refactor DetailedFunctionPropertiesAnalysis into FunctionPropertiesAnalysis and keep the additional options behind a command line flag. I would like to use actual pass options here similar to how passes like instcombine can take in arguments, but the new pass manager doesn't seem to currently have support for analysis passes with parameters like is present for traditional function passes. I'm not sure how difficult it would be to get this implemented, but it doesn't look trivial.
• Address additional comments, land the patch.

llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h

class FunctionPropertiesPrinterPass
   raw_ostream &OS;
 
 public:
   explicit FunctionPropertiesPrinterPass(raw_ostream &OS) : OS(OS) {}
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
+class DetailedFunctionPropertiesInfo {
+public:
+  static DetailedFunctionPropertiesInfo
+  getDetailedFunctionPropertiesInfo(const Function &F, const LoopInfo &LI);
+
+  void print(raw_ostream &OS) const;
+
+  void visitInstruction(Instruction &I) {
+    errs() << "Instruction Count does not know about " << I;
+    llvm_unreachable(nullptr);
+  }
+
+#define HANDLE_INST(N, OPCODE, CLASS)                                          \
+private:                                                                       \
+  int64_t OPCODE##InstCount = 0;                                               \
+  void set##OPCODE##InstCount(int64_t value) { OPCODE##InstCount = value; }    \
+  void increment##OPCODE##InstCount() { ++OPCODE##InstCount; }                 \
+                                                                               \
+public:                                                                        \
+  int64_t get##OPCODE##InstCount() const { return OPCODE##InstCount; }
+
+#include "llvm/IR/Instruction.def"
+
+#define DEFINE_FEATURE_VARIABLE(NAME)                                          \
+private:                                                                       \
+  int64_t NAME = 0;                                                            \
+  void increment##NAME() { ++NAME; }                                           \
+  void set##NAME(int64_t value) { NAME = value; }                              \
+                                                                               \
+public:                                                                        \
+  int64_t get##NAME() const { return NAME; }
+
+  // Number of Basic Blocks.
+  DEFINE_FEATURE_VARIABLE(BasicBlockCount);
+
+  /// Number of Basic Blocks with specific successors.
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithSingleSuccessor);
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithTwoSuccessors);
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithMoreThanTwoSuccessors);
+
+  /// Number of Basic Blocks with specific predecessors.
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithSinglePredecessor);
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithTwoPredecessors);
+  DEFINE_FEATURE_VARIABLE(BasicBlockWithMoreThanTwoPredecessors);
+
+  // Number of basic blocks with more than 500 instructions.
+  DEFINE_FEATURE_VARIABLE(BigBasicBlock);
+
+  // Number of basic blocks with 15 ~ 500 instructions.
+  DEFINE_FEATURE_VARIABLE(MediumBasicBlock);
+
+  // Number of basic blocks with less than 15 instructions.
+  DEFINE_FEATURE_VARIABLE(SmallBasicBlock);
+
+  /// Number of Cast-like Instruction Count in the Function.
+  DEFINE_FEATURE_VARIABLE(CastInstCount);
+
+  /// Number of Floating Point Instruction Count.
+  DEFINE_FEATURE_VARIABLE(FloatingPointInstCount);
+
+  /// Number of Integer Instruction Count.
+  DEFINE_FEATURE_VARIABLE(IntegerInstCount);
+
+  /// Number of Occurences of Constants.
+  DEFINE_FEATURE_VARIABLE(IntegerConstantOccurrences);
+  DEFINE_FEATURE_VARIABLE(FloatingConstantOccurrences);
+  /// Maximum Loop Depth in the Function.
+  DEFINE_FEATURE_VARIABLE(MaxLoopDepth);
+
+  /// Number of Top Level Loops in the Function.
+  DEFINE_FEATURE_VARIABLE(TopLevelLoopCount);
+#undef DEFINE_FEATURE_VARIABLE
+};
+
+// Analysis pass
+class DetailedFunctionPropertiesAnalysis
+    : public AnalysisInfoMixin<DetailedFunctionPropertiesAnalysis> {
+
+public:
+  static AnalysisKey Key;
+
+  using Result = DetailedFunctionPropertiesInfo;
+
+  Result run(Function &F, FunctionAnalysisManager &FAM);
+};
+
+/// Printer pass for the DetailedFunctionPropertiesAnalysis results.
+class DetailedFunctionPropertiesPrinterPass
+    : public PassInfoMixin<DetailedFunctionPropertiesPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit DetailedFunctionPropertiesPrinterPass(raw_ostream &OS) : OS(OS) {}
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
 } // namespace llvm
 #endif // LLVM_ANALYSIS_FUNCTIONPROPERTIESANALYSIS_H

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

 //===- FunctionPropertiesAnalysis.cpp - Function Properties Analysis ------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the FunctionPropertiesInfo and FunctionPropertiesAnalysis
 // classes used to extract function properties.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
+#include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 
 using namespace llvm;
 
 FunctionPropertiesInfo
 FunctionPropertiesInfo::getFunctionPropertiesInfo(const Function &F,
                                                   const LoopInfo &LI) {
 

 PreservedAnalyses
 FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
   OS << "Printing analysis results of CFA for function "
      << "'" << F.getName() << "':"
      << "\n";
   AM.getResult<FunctionPropertiesAnalysis>(F).print(OS);
   return PreservedAnalyses::all();
 }
+
+DetailedFunctionPropertiesInfo
+DetailedFunctionPropertiesInfo::getDetailedFunctionPropertiesInfo(
+    const Function &F, const LoopInfo &LI) {
+  class InstCount : public InstVisitor<InstCount> {
+    friend class InstVisitor<InstCount>;
+
+#define HANDLE_INST(N, OPCODE, CLASS)                                          \
+  void visit##OPCODE(CLASS &) { FPI.increment##OPCODE##InstCount(); }
+
+#include "llvm/IR/Instruction.def"
+
+    void visitInstruction(Instruction &I) {
+      errs() << "Instruction Count does not know about " << I;
+      llvm_unreachable(nullptr);
+    }
+    void visitFunction(Function &F) {
+      errs() << "Should never visit a function " << F;
+      llvm_unreachable(nullptr);
+    }
+    void visitBasicBlock(BasicBlock &BB) {
+      errs() << "Should never visit a basic block " << BB;
+      llvm_unreachable(nullptr);
+    }
+
+    DetailedFunctionPropertiesInfo &FPI;
+
+  public:
+    InstCount(DetailedFunctionPropertiesInfo &FPI) : FPI(FPI) {}
+  };
+
+  DetailedFunctionPropertiesInfo FPI;
+  InstCount IC(FPI);
+
+  for (const auto &BB : F) {
+    FPI.incrementBasicBlockCount();
+
+    unsigned SuccSize = succ_size(&BB);
+    unsigned PredSize = pred_size(&BB);
+    if (SuccSize == 1)
+      FPI.incrementBasicBlockWithSingleSuccessor();
+    else if (SuccSize == 2)
+      FPI.incrementBasicBlockWithTwoSuccessors();
+    else if (SuccSize > 2)
+      FPI.incrementBasicBlockWithMoreThanTwoSuccessors();
+
+    if (PredSize == 1)
+      FPI.incrementBasicBlockWithSinglePredecessor();
+    else if (PredSize == 2)
+      FPI.incrementBasicBlockWithTwoPredecessors();
+    else if (PredSize > 2)
+      FPI.incrementBasicBlockWithMoreThanTwoPredecessors();
+
+    if (BB.size() > 500)
+      FPI.incrementBigBasicBlock();
+    else if (BB.size() >= 15)
+      FPI.incrementMediumBasicBlock();
+    else
+      FPI.incrementSmallBasicBlock();
+
+    for (const auto &I : BB) {
+      if (I.getType()->isFloatTy())
+        FPI.incrementFloatingPointInstCount();
+      else if (I.getType()->isIntegerTy())
+        FPI.incrementIntegerInstCount();
+
+      for (unsigned int i = 0; i < I.getNumOperands(); i++)
+        if (auto *C = dyn_cast<Constant>(I.getOperand(i))) {
+          if (C->getType()->isIntegerTy())
+            FPI.incrementIntegerConstantOccurrences();
+          else if (C->getType()->isFloatTy())
+            FPI.incrementFloatingConstantOccurrences();
+        }
+
+      if (I.isCast())
+        FPI.incrementCastInstCount();
+      IC.visit(const_cast<Instruction *>(&I));
+    }
+  }
+
+  for (const auto &BB : F) {
+    int LoopDepth = LI.getLoopDepth(&BB);
+    if (FPI.getMaxLoopDepth() < LoopDepth)
+      FPI.setMaxLoopDepth(LoopDepth);
+  }
+
+  FPI.setTopLevelLoopCount(llvm::size(LI));
+  return FPI;
+}
+
+AnalysisKey DetailedFunctionPropertiesAnalysis::Key;
+
+DetailedFunctionPropertiesInfo
+DetailedFunctionPropertiesAnalysis::run(Function &F,
+                                        FunctionAnalysisManager &FAM) {
+  return DetailedFunctionPropertiesInfo::getDetailedFunctionPropertiesInfo(
+      F, FAM.getResult<LoopAnalysis>(F));
+}
+
+void DetailedFunctionPropertiesInfo::print(raw_ostream &OS) const {
+  OS << "BasicBlockCount: " << BasicBlockCount << "\n"
+     << "BasicBlockWithSingleSuccessor: " << BasicBlockWithSingleSuccessor
+     << "\n"
+     << "BasicBlockWithTwoSuccessors: " << BasicBlockWithTwoSuccessors << "\n"
+     << "BasicBlockWithMoreThanTwoSuccessors: "
+     << BasicBlockWithMoreThanTwoSuccessors << "\n"
+     << "BasicBlockWithSinglePredecessor: " << BasicBlockWithSinglePredecessor
+     << "\n"
+     << "BasicBlockWithTwoPredecessors: " << BasicBlockWithTwoPredecessors
+     << "\n"
+     << "BasicBlockWithMoreThanTwoPredecessors: "
+     << BasicBlockWithMoreThanTwoPredecessors << "\n"
+     << "BigBasicBlock: " << BigBasicBlock << "\n"
+     << "MediumBasicBlock: " << MediumBasicBlock << "\n"
+     << "SmallBasicBlock: " << SmallBasicBlock << "\n"
+     << "CastInstCount: " << CastInstCount << "\n"
+     << "FloatingPointInstCount: " << FloatingPointInstCount << "\n"
+     << "IntegerInstCount: " << IntegerInstCount << "\n"
+     << "IntegerConstantOccurrences: " << IntegerConstantOccurrences << "\n"
+     << "FloatingConstantOccurrences: " << FloatingConstantOccurrences << "\n"
+     << "MaxLoopDepth: " << MaxLoopDepth << "\n"
+     << "TopLevelLoopCount: " << TopLevelLoopCount << "\n";
+#define HANDLE_INST(N, OPCODE, CLASS)                                          \
+  OS << #OPCODE << "InstCount"                                                 \
+     << ": " << OPCODE##InstCount << "\n";
+
+#include "llvm/IR/Instruction.def"
+}
+
+PreservedAnalyses
+DetailedFunctionPropertiesPrinterPass::run(Function &F,
+                                           FunctionAnalysisManager &AM) {
+  OS << "Printing analysis results of CFA for function "
+     << "'" << F.getName() << "':"
+     << "\n";
+  AM.getResult<DetailedFunctionPropertiesAnalysis>(F).print(OS);
+  return PreservedAnalyses::all();
+}
 No newline at end of file

llvm/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis())
 FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("func-properties", FunctionPropertiesAnalysis())
+FUNCTION_ANALYSIS("detailed-func-properties",
+                  DetailedFunctionPropertiesAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())
 FUNCTION_ANALYSIS("inliner-size-estimator", InlineSizeEstimatorAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis())
 FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())

 FUNCTION_PASS("print<da>", DependenceAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<divergence>", DivergenceAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<delinearization>", DelinearizationPrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<func-properties>", FunctionPropertiesPrinterPass(dbgs()))
+FUNCTION_PASS("print<detailed-func-properties>",
+              DetailedFunctionPropertiesPrinterPass(dbgs()))
 FUNCTION_PASS("print<inline-cost>", InlineCostAnnotationPrinterPass(dbgs()))
 FUNCTION_PASS("print<inliner-size-estimator>",
   InlineSizeEstimatorAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<memoryssa>", MemorySSAPrinterPass(dbgs()))
 FUNCTION_PASS("print<memoryssa-walker>", MemorySSAWalkerPrinterPass(dbgs()))
 FUNCTION_PASS("print<phi-values>", PhiValuesPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))

llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp

protected:
   std::unique_ptr<LoopInfo> LI;
 
   FunctionPropertiesInfo buildFPI(Function &F) {
     DT.reset(new DominatorTree(F));
     LI.reset(new LoopInfo(*DT));
     return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, *LI);
   }
 
+  DetailedFunctionPropertiesInfo buildDetailedFPI(Function &F) {
+    DT.reset(new DominatorTree(F));
+    LI.reset(new LoopInfo(*DT));
+    return DetailedFunctionPropertiesInfo::getDetailedFunctionPropertiesInfo(
+        F, *LI);
+  }
+
   std::unique_ptr<Module> makeLLVMModule(LLVMContext &C, const char *IR) {
     SMDiagnostic Err;
     std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
     if (!Mod)
       Err.print("MLAnalysisTests", errs());
     return Mod;
   }
 };
)IR");
   EXPECT_EQ(TopFeatures.BasicBlockCount, 1);
   EXPECT_EQ(TopFeatures.BlocksReachedFromConditionalInstruction, 0);
   EXPECT_EQ(TopFeatures.Uses, 0);
   EXPECT_EQ(TopFeatures.DirectCallsToDefinedFunctions, 1);
   EXPECT_EQ(BranchesFeatures.LoadInstCount, 0);
   EXPECT_EQ(BranchesFeatures.StoreInstCount, 0);
   EXPECT_EQ(BranchesFeatures.MaxLoopDepth, 0);
   EXPECT_EQ(BranchesFeatures.TopLevelLoopCount, 0);
+
+  DetailedFunctionPropertiesInfo DetailedFeatures =
+      buildDetailedFPI(*BranchesFunction);
+  EXPECT_EQ(DetailedFeatures.getBasicBlockCount(), 4);
+  EXPECT_EQ(DetailedFeatures.getBasicBlockWithSingleSuccessor(), 2);
+  EXPECT_EQ(DetailedFeatures.getBasicBlockWithTwoSuccessors(), 1);
+  EXPECT_EQ(DetailedFeatures.getBasicBlockWithSinglePredecessor(), 2);
+  EXPECT_EQ(DetailedFeatures.getSmallBasicBlock(), 4);
+  EXPECT_EQ(DetailedFeatures.getIntegerInstCount(), 4);
+  EXPECT_EQ(DetailedFeatures.getIntegerConstantOccurrences(), 1);
+  EXPECT_EQ(DetailedFeatures.getRetInstCount(), 1);
+  EXPECT_EQ(DetailedFeatures.getBrInstCount(), 3);
+  EXPECT_EQ(DetailedFeatures.getICmpInstCount(), 1);
+  EXPECT_EQ(DetailedFeatures.getPHIInstCount(), 1);
+  EXPECT_EQ(DetailedFeatures.getCallInstCount(), 2);
 }
 } // end anonymous namespace
 No newline at end of file