[FunctionPropertiesAnalysis] Add detailed analysis

[aidengrossman]

Summary

This patch adds more detailed function properties gated behind a command line flag for use primarily in experimentation and gathering statistics on the functions in a module or project. The runtime cost should be minimal as the computation is only done when the flag is set. There will be a slight memory overhead when the ML inliner is enabled, but it should be fairly small at a handful of bytes per function.

This is an adapted form of https://reviews.llvm.org/D109661.

[jdoerfert]

can u add a lit test that checks the printout?

[mtrofin]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

350

why did this shift to the right?

[aidengrossman]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

350

In the actual git diff it doesn't look like it did. https://github.com/boomanaiden154/llvm-project/commit/688dbdba8bc1b27a363f32b1d92e8fe10c21a504
I uploaded this patch manually by copying the output from git diff HEAD~1 and phabricator seems to be messing up the formatting for some reason (not sure why, same process worked perfectly for other patches recently).

This section of the file didn't actually change at all in the diff.

[mtrofin]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

350

can you try again with arcanist?

[aidengrossman]

Add lit-test, update to format diff correctly.

[mtrofin]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

90

pred_size

Is the test catching this?

105

probably want to ignore debug instructions

also, do you care if it's an intrinsic?

119

++IntegerConstantCount?

121

++FloatingPointConstantCount

[aidengrossman]

Address reviewer feedback.

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

90

Tests were not currently catching that. I've added a new unit test case to make sure the behavior is as expected when the number of successors and predecessors is different.

105

Not currently. I'm probably going to add a couple more features in the future and a count of instructions that are intrinsics would be nice to have, but currently focused on getting the original feature set in.

119

I've switched to doing += Direction so that this better matches the behavior of the rest of the function when updating a function analysis. It doesn't really matter in my case, but definitely shouldn't purposefully be different.

llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h

public:
   // Maximum Loop Depth in the Function
   int64_t MaxLoopDepth = 0;
 
   // Number of Top Level Loops in the Function
   int64_t TopLevelLoopCount = 0;
 
   // All non-debug instructions
   int64_t TotalInstructionCount = 0;
+
+  // Basic blocks grouped by number of successors.
+  int64_t BasicBlocksWithSingleSuccessor = 0;
+  int64_t BasicBlocksWithTwoSuccessors = 0;
+  int64_t BasicBlocksWithMoreThanTwoSuccessors = 0;
+
+  // Basic blocks grouped by number of predecessors.
+  int64_t BasicBlocksWithSinglePredecessor = 0;
+  int64_t BasicBlocksWithTwoPredecessors = 0;
+  int64_t BasicBlocksWithMoreThanTwoPredecessors = 0;
+
+  // Basic blocks grouped by size as determined by the number of non-debug
+  // instructions that they contain.
+  int64_t BigBasicBlocks = 0;
+  int64_t MediumBasicBlocks = 0;
+  int64_t SmallBasicBlocks = 0;
+
+  // The number of cast instructions inside the function.
+  int64_t CastInstructionCount = 0;
+
+  // The number of floating point instructions inside the function.
+  int64_t FloatingPointInstructionCount = 0;
+
+  // The number of integer instructions inside the function.
+  int64_t IntegerInstructionCount = 0;
+
+  // The number of integer constant operands inside the function.
+  int64_t IntegerConstantCount = 0;
+
+  // The number of floating point constant operands inside the function.
+  int64_t FloatingPointConstantCount = 0;
 };
 
 // Analysis pass
 class FunctionPropertiesAnalysis
     : public AnalysisInfoMixin<FunctionPropertiesAnalysis> {
 
 public:
   static AnalysisKey Key;

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

 
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/Support/CommandLine.h"
 #include <deque>
 
 using namespace llvm;
 
+cl::opt<bool> EnableDetailedFunctionProperties(
+    "enable-detailed-function-properties", cl::Hidden, cl::init(false),
+    cl::desc("Whether or not to compute detailed function properties."));
+
+cl::opt<unsigned> BigBasicBlockInstructionThreshold(
+    "big-basic-block-instruction-threshold", cl::Hidden, cl::init(500),
+    cl::desc("The minimum number of instructions a basic block should contain "
+             "before being considered big."));
+
+cl::opt<unsigned> MediumBasicBlockInstructionThreshold(
+    "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15),
+    cl::desc("The minimum number of instructions a basic block should contain "
+             "before being considered medium-sized."));
+
 namespace {
 int64_t getNrBlocksFromCond(const BasicBlock &BB) {
   int64_t Ret = 0;
   if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
     if (BI->isConditional())
       Ret += BI->getNumSuccessors();
   } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
     Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
for (const auto &I : BB) {
     }
     if (I.getOpcode() == Instruction::Load) {
       LoadInstCount += Direction;
     } else if (I.getOpcode() == Instruction::Store) {
       StoreInstCount += Direction;
     }
   }
   TotalInstructionCount += Direction * BB.sizeWithoutDebug();
+
+  if (EnableDetailedFunctionProperties) {
+    unsigned SuccessorCount = succ_size(&BB);
+    if (SuccessorCount == 1)
+      BasicBlocksWithSingleSuccessor += Direction;
+    else if (SuccessorCount == 2)
+      BasicBlocksWithTwoSuccessors += Direction;
+    else if (SuccessorCount > 2)
+      BasicBlocksWithMoreThanTwoSuccessors += Direction;
+
+    unsigned PredecessorCount = pred_size(&BB);
+    if (PredecessorCount == 1)
+      BasicBlocksWithSinglePredecessor += Direction;
+    else if (PredecessorCount == 2)
+      BasicBlocksWithTwoPredecessors += Direction;
+    else if (PredecessorCount > 2)
+      BasicBlocksWithMoreThanTwoPredecessors += Direction;
+
+    if (TotalInstructionCount > BigBasicBlockInstructionThreshold)
+      BigBasicBlocks += Direction;
+    else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold)
+      MediumBasicBlocks += Direction;
+    else
+      SmallBasicBlocks += Direction;
+
+    for (const Instruction &I : BB.instructionsWithoutDebug()) {
+      if (I.isCast())
+        CastInstructionCount += Direction;
+
+      if (I.getType()->isFloatTy())
+        FloatingPointInstructionCount += Direction;
+      else if (I.getType()->isIntegerTy())
+        IntegerInstructionCount += Direction;
+
+      for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();
+           ++OperandIndex) {
+        if (const Constant *C =
+                dyn_cast<Constant>(I.getOperand(OperandIndex))) {
+          if (C->getType()->isIntegerTy())
+            IntegerConstantCount += Direction;
+          else if (C->getType()->isFloatTy())
+            FloatingPointConstantCount += Direction;
+        }
+      }
+    }
+  }
 }
 
 void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
                                                   const LoopInfo &LI) {
 
   Uses = getUses(F);
   TopLevelLoopCount = llvm::size(LI);
   MaxLoopDepth = 0;
OS << "BasicBlockCount: " << BasicBlockCount << "\n"
      << BlocksReachedFromConditionalInstruction << "\n"
      << "Uses: " << Uses << "\n"
      << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions
      << "\n"
      << "LoadInstCount: " << LoadInstCount << "\n"
      << "StoreInstCount: " << StoreInstCount << "\n"
      << "MaxLoopDepth: " << MaxLoopDepth << "\n"
      << "TopLevelLoopCount: " << TopLevelLoopCount << "\n"
-     << "TotalInstructionCount: " << TotalInstructionCount << "\n\n";
+     << "TotalInstructionCount: " << TotalInstructionCount << "\n";
+  if (EnableDetailedFunctionProperties) {
+    OS << "BasicBlocksWithSingleSuccessor: " << BasicBlocksWithSingleSuccessor
+       << "\n"
+       << "BasicBlocksWithTwoSuccessors: " << BasicBlocksWithTwoSuccessors
+       << "\n"
+       << "BasicBlocksWithMoreThanTwoSuccessors: "
+       << BasicBlocksWithMoreThanTwoSuccessors << "\n"
+       << "BasicBlocksWithSinglePredecessor: "
+       << BasicBlocksWithSinglePredecessor << "\n"
+       << "BasicBlocksWithTwoPredecessors: " << BasicBlocksWithTwoPredecessors
+       << "\n"
+       << "BasicBlocksWithMoreThanTwoPredecessors: "
+       << BasicBlocksWithMoreThanTwoPredecessors << "\n"
+       << "BigBasicBlocks: " << BigBasicBlocks << "\n"
+       << "MediumBasicBlocks: " << MediumBasicBlocks << "\n"
+       << "SmallBasicBlocks: " << SmallBasicBlocks << "\n"
+       << "CastInstructionCount: " << CastInstructionCount << "\n"
+       << "FloatingPointInstructionCount: " << FloatingPointInstructionCount
+       << "\n"
+       << "IntegerInstructionCount: " << IntegerInstructionCount << "\n"
+       << "IntegerConstantCount: " << IntegerConstantCount << "\n"
+       << "FloatingPointConstantCount: " << FloatingPointConstantCount << "\n";
+  }
+  OS << "\n";
 }
 
 AnalysisKey FunctionPropertiesAnalysis::Key;
 
 FunctionPropertiesInfo
 FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM);
 }

 
 bool FunctionPropertiesUpdater::isUpdateValid(Function &F,
                                               const FunctionPropertiesInfo &FPI,
                                               FunctionAnalysisManager &FAM) {
   DominatorTree DT(F);
   LoopInfo LI(DT);
   auto Fresh = FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI);
   return FPI == Fresh;
-}
+}
 

llvm/test/Analysis/FunctionPropertiesAnalysis/matmul.ll

 ; RUN: opt < %s -passes='print<func-properties>' -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -passes='print<func-properties>' -disable-output 2>&1 -enable-detailed-function-properties | FileCheck %s --check-prefix=DETAILED-PROPERTIES
 
 define i32 @main() {
 ; CHECK-DAG: Printing analysis results of CFA for function 'main':
+; DETAILED-PROPERTIES-DAG: Printing analysis results of CFA for function 'main':
 
 entry:
   %retval = alloca i32, align 4
   %mat1 = alloca [2 x [2 x i32]], align 16
   %mat2 = alloca [2 x [2 x i32]], align 16
   %res = alloca [2 x [2 x i32]], align 16
   %i = alloca i32, align 4
   %j = alloca i32, align 4
   store i32 0, i32* %retval, align 4
   %arraydecay = getelementptr inbounds [2 x [2 x i32]], [2 x [2 x i32]]* %mat1, i64 0, i64 0
   %arraydecay1 = getelementptr inbounds [2 x [2 x i32]], [2 x [2 x i32]]* %mat2, i64 0, i64 0
   %arraydecay2 = getelementptr inbounds [2 x [2 x i32]], [2 x [2 x i32]]* %res, i64 0, i64 0
   call void @multiply([2 x i32]* %arraydecay, [2 x i32]* %arraydecay1, [2 x i32]* %arraydecay2)
   ret i32 0
 }
 ; CHECK-DAG: BasicBlockCount: 1
 ; CHECK-DAG: BlocksReachedFromConditionalInstruction: 0
 ; CHECK-DAG: Uses: 1
 ; CHECK-DAG: DirectCallsToDefinedFunctions: 1
 ; CHECK-DAG: LoadInstCount: 0
 ; CHECK-DAG: StoreInstCount: 1
 ; CHECK-DAG: MaxLoopDepth: 0
 ; CHECK-DAG: TopLevelLoopCount: 0
 
+; DETAILED-PROPERTIES-DAG: BasicBlockCount: 1
+; DETAILED-PROPERTIES-DAG: BlocksReachedFromConditionalInstruction: 0
+; DETAILED-PROPERTIES-DAG: Uses: 1
+; DETAILED-PROPERTIES-DAG: DirectCallsToDefinedFunctions: 1
+; DETAILED-PROPERTIES-DAG: LoadInstCount: 0
+; DETAILED-PROPERTIES-DAG: StoreInstCount: 1
+; DETAILED-PROPERTIES-DAG: MaxLoopDepth: 0
+; DETAILED-PROPERTIES-DAG: TopLevelLoopCount: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithSingleSuccessor: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithTwoSuccessors: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithMoreThanTwoSuccessors: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithSinglePredecessor: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithTwoPredecessors: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithMoreThanTwoPredecessors: 0
+; DETAILED-PROPERTIES-DAG: BigBasicBlocks: 0
+; DETAILED-PROPERTIES-DAG: MediumBasicBlocks: 0
+; DETAILED-PROPERTIES-DAG: SmallBasicBlocks: 1
+; DETAILED-PROPERTIES-DAG: CastInstructionCount: 0
+; DETAILED-PROPERTIES-DAG: FloatingPointInstructionCount: 0
+; DETAILED-PROPERTIES-DAG: IntegerInstructionCount: 0
+; DETAILED-PROPERTIES-DAG: IntegerConstantCount: 14
+; DETAILED-PROPERTIES-DAG: FloatingPointConstantCount: 0
+
 define void @multiply([2 x i32]* %mat1, [2 x i32]* %mat2, [2 x i32]* %res) {
 ; CHECK-DAG: Printing analysis results of CFA for function 'multiply':
+; DETAILED-PROPERTIES-DAG: Printing analysis results of CFA for function 'multiply':
 entry:
   %mat1.addr = alloca [2 x i32]*, align 8
   %mat2.addr = alloca [2 x i32]*, align 8
   %res.addr = alloca [2 x i32]*, align 8
   %i = alloca i32, align 4
   %j = alloca i32, align 4
   %k = alloca i32, align 4
   store [2 x i32]* %mat1, [2 x i32]** %mat1.addr, align 8

 
 ; CHECK-DAG: BasicBlockCount: 13
 ; CHECK-DAG: BlocksReachedFromConditionalInstruction: 6
 ; CHECK-DAG: Uses: 2
 ; CHECK-DAG: DirectCallsToDefinedFunctions: 0
 ; CHECK-DAG: LoadInstCount: 21
 ; CHECK-DAG: StoreInstCount: 11
 ; CHECK-DAG: MaxLoopDepth: 3
-; CHECK-DAG: TopLevelLoopCount: 1
+; CHECK-DAG: TopLevelLoopCount: 1
+
+; DETAILED-PROPERTIES-DAG: BasicBlockCount: 13
+; DETAILED-PROPERTIES-DAG: BlocksReachedFromConditionalInstruction: 6
+; DETAILED-PROPERTIES-DAG: Uses: 2
+; DETAILED-PROPERTIES-DAG: DirectCallsToDefinedFunctions: 0
+; DETAILED-PROPERTIES-DAG: LoadInstCount: 21
+; DETAILED-PROPERTIES-DAG: StoreInstCount: 11
+; DETAILED-PROPERTIES-DAG: MaxLoopDepth: 3
+; DETAILED-PROPERTIES-DAG: TopLevelLoopCount: 1
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithSingleSuccessor: 9
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithTwoSuccessors: 3
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithMoreThanTwoSuccessors: 0
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithSinglePredecessor: 9
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithTwoPredecessors: 3
+; DETAILED-PROPERTIES-DAG: BasicBlocksWithMoreThanTwoPredecessors: 0
+; DETAILED-PROPERTIES-DAG: BigBasicBlocks: 0
+; DETAILED-PROPERTIES-DAG: MediumBasicBlocks: 11
+; DETAILED-PROPERTIES-DAG: SmallBasicBlocks: 2
+; DETAILED-PROPERTIES-DAG: CastInstructionCount: 8
+; DETAILED-PROPERTIES-DAG: FloatingPointInstructionCount: 0
+; DETAILED-PROPERTIES-DAG: IntegerInstructionCount: 33
+; DETAILED-PROPERTIES-DAG: IntegerConstantCount: 20
+; DETAILED-PROPERTIES-DAG: FloatingPointConstantCount: 0

llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp

 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Passes/StandardInstrumentations.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "gtest/gtest.h"
 #include <cstring>
 
 using namespace llvm;
+
+extern cl::opt<bool> EnableDetailedFunctionProperties;
+extern cl::opt<bool> BigBasicBlockInstructionThreshold;
+extern cl::opt<bool> MediumBasicBlockInstrutionThreshold;
+
 namespace {
 
 class FunctionPropertiesAnalysisTest : public testing::Test {
 public:
   FunctionPropertiesAnalysisTest() {
     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
     FAM.registerPass([&] { return LoopAnalysis(); });
     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
)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);
+
+  EnableDetailedFunctionProperties.setValue(true);
+  FunctionPropertiesInfo DetailedBranchesFeatures = buildFPI(*BranchesFunction);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithSingleSuccessor, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithTwoSuccessors, 1);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithMoreThanTwoSuccessors, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithSinglePredecessor, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithTwoPredecessors, 1);
+  EXPECT_EQ(DetailedBranchesFeatures.BasicBlocksWithMoreThanTwoPredecessors, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.BigBasicBlocks, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.MediumBasicBlocks, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.SmallBasicBlocks, 4);
+  EXPECT_EQ(DetailedBranchesFeatures.CastInstructionCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.FloatingPointInstructionCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.IntegerInstructionCount, 4);
+  EXPECT_EQ(DetailedBranchesFeatures.IntegerConstantCount, 1);
+  EXPECT_EQ(DetailedBranchesFeatures.FloatingPointConstantCount, 0);
+  EnableDetailedFunctionProperties.setValue(false);
+}
+
+TEST_F(FunctionPropertiesAnalysisTest, DifferentPredecessorSuccessorCounts) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = makeLLVMModule(C,
+                                             R"IR(
+define i64 @f1() {
+  br i1 0, label %br1, label %finally
+br1:
+  ret i64 0
+finally:
+  ret i64 3
+}
+)IR");
+
+  Function *F1 = M->getFunction("f1");
+  EnableDetailedFunctionProperties.setValue(true);
+  FunctionPropertiesInfo DetailedF1Properties = buildFPI(*F1);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithSingleSuccessor, 0);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithTwoSuccessors, 1);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithMoreThanTwoSuccessors, 0);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithSinglePredecessor, 2);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithTwoPredecessors, 0);
+  EXPECT_EQ(DetailedF1Properties.BasicBlocksWithMoreThanTwoPredecessors, 0);
+  EXPECT_EQ(DetailedF1Properties.BigBasicBlocks, 0);
+  EXPECT_EQ(DetailedF1Properties.MediumBasicBlocks, 0);
+  EXPECT_EQ(DetailedF1Properties.SmallBasicBlocks, 3);
+  EXPECT_EQ(DetailedF1Properties.CastInstructionCount, 0);
+  EXPECT_EQ(DetailedF1Properties.FloatingPointInstructionCount, 0);
+  EXPECT_EQ(DetailedF1Properties.IntegerInstructionCount, 0);
+  EXPECT_EQ(DetailedF1Properties.IntegerConstantCount, 3);
+  EXPECT_EQ(DetailedF1Properties.FloatingPointConstantCount, 0);
+  EnableDetailedFunctionProperties.setValue(false);
 }
 
 TEST_F(FunctionPropertiesAnalysisTest, InlineSameBBSimple) {
   LLVMContext C;
   std::unique_ptr<Module> M = makeLLVMModule(C,
                                              R"IR(
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-linux-gnu"