[FunctionPropertiesAnalysis] Add CFG and call properties

[aidengrossman]

Summary

This patch adds in a couple more properties related to call instructions
and the CFG within the function that should expose a little bit more
about the characteristics of the function.

[jdoerfert]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

118

This counts each critical edge #predecessors times, doesn't it?

147–150

[aidengrossman]

Address reviewer feedback

• Fix issue with critical edge counting

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

118

Yes. I forgot to add the conditional that the number of successors of the block must be greater than zero. Fixed in the latest patch (with a test case added).

[aidengrossman]

Address reviewer feedback

[arsenm]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

145

What about vector of int / vector of fp / vector of pointer

[aidengrossman]

Address reviewer feedback

• Add handling for vector return types

[aidengrossman]

llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp

145

Thanks for the suggestion! Added. Could provide some interesting information.

[jdoerfert]

llvm/test/Analysis/FunctionPropertiesAnalysis/matmul.ll

220

add the missing check lines.

llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h

public:
   int64_t ConstantFPOperandCount = 0;
   int64_t ConstantOperandCount = 0;
   int64_t InstructionOperandCount = 0;
   int64_t BasicBlockOperandCount = 0;
   int64_t GlobalValueOperandCount = 0;
   int64_t InlineAsmOperandCount = 0;
   int64_t ArgumentOperandCount = 0;
   int64_t UnknownOperandCount = 0;
+
+  // Additional CFG Properties
+  int64_t CriticalEdgeCount = 0;
+  int64_t ControlFlowEdgeCount = 0;
+  int64_t UnconditionalBranchCount = 0;
+
+  // Call related instructions
+  int64_t IntrinsicCount = 0;
+  int64_t DirectCallCount = 0;
+  int64_t IndirectCallCount = 0;
+  int64_t CallReturnsIntegerCount = 0;
+  int64_t CallReturnsFloatCount = 0;
+  int64_t CallReturnsPointerCount = 0;
+  int64_t CallWithManyArgumentsCount = 0;
+  int64_t CallWithPointerArgumentCount = 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/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.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."));
 
+cl::opt<unsigned> CallWithManyArgumentsThreshold(
+    "call-with-many-arguments-threshold", cl::Hidden, cl::init(4),
+    cl::desc("The minimum number of arguments a function call must have before "
+             "it is considered having many arguments."));
+
 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()));
if (EnableDetailedFunctionProperties) {
 
     if (TotalInstructionCount > BigBasicBlockInstructionThreshold)
       BigBasicBlocks += Direction;
     else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold)
       MediumBasicBlocks += Direction;
     else
       SmallBasicBlocks += Direction;
 
+    // Calculate critical edges by looking through all successors of a basic
+    // block and finding ones that have multiple predecessors, which represents
+    // a critical edge.
+    for (const auto *Successor : successors(&BB)) {
+      if (pred_size(Successor) > 1)
+        CriticalEdgeCount += Direction;
+    }
+
+    ControlFlowEdgeCount += Direction * SuccessorCount;
+
+    if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
+      if (!BI->isConditional())
+        UnconditionalBranchCount += 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;
 
+      if (isa<IntrinsicInst>(I))
+        ++IntrinsicCount;
+
+      if (const auto *Call = dyn_cast<CallInst>(&I)) {
+        if (Call->isIndirectCall())
+          IndirectCallCount += Direction;
+        else
+          DirectCallCount += Direction;
+
+        if (Call->getType()->isIntegerTy())
+          CallReturnsIntegerCount += Direction;
+        if (Call->getType()->isFloatingPointTy())
+          CallReturnsFloatCount += Direction;
+        if (Call->getType()->isPointerTy())
+          CallReturnsPointerCount += Direction;
+
+        if (Call->arg_size() > CallWithManyArgumentsThreshold)
+          CallWithManyArgumentsCount += Direction;
+
+        for (const auto &Arg : Call->args()) {
+          if (Arg->getType()->isPointerTy()) {
+            CallWithPointerArgumentCount += Direction;
+            break;
+          }
+        }
+      }
+
 #define COUNT_OPERAND(OPTYPE)                                                  \
   if (isa<OPTYPE>(Operand)) {                                                  \
     OPTYPE##OperandCount += Direction;                                         \
     continue;                                                                  \
   }
 
       for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();
            ++OperandIndex) {
if (EnableDetailedFunctionProperties) {
     PRINT_PROPERTY(ConstantFPOperandCount)
     PRINT_PROPERTY(ConstantOperandCount)
     PRINT_PROPERTY(InstructionOperandCount)
     PRINT_PROPERTY(BasicBlockOperandCount)
     PRINT_PROPERTY(GlobalValueOperandCount)
     PRINT_PROPERTY(InlineAsmOperandCount)
     PRINT_PROPERTY(ArgumentOperandCount)
     PRINT_PROPERTY(UnknownOperandCount)
+    PRINT_PROPERTY(CriticalEdgeCount)
+    PRINT_PROPERTY(ControlFlowEdgeCount)
+    PRINT_PROPERTY(UnconditionalBranchCount)
+    PRINT_PROPERTY(IntrinsicCount)
+    PRINT_PROPERTY(DirectCallCount)
+    PRINT_PROPERTY(IndirectCallCount)
+    PRINT_PROPERTY(CallReturnsIntegerCount)
+    PRINT_PROPERTY(CallReturnsFloatCount)
+    PRINT_PROPERTY(CallReturnsPointerCount)
+    PRINT_PROPERTY(CallWithManyArgumentsCount)
+    PRINT_PROPERTY(CallWithPointerArgumentCount)
   }
 
 #undef PRINT_PROPERTY
 
   OS << "\n";
 }
 
 AnalysisKey FunctionPropertiesAnalysis::Key;

llvm/test/Analysis/FunctionPropertiesAnalysis/matmul.ll

 ; DETAILED-PROPERTIES-DAG: ConstantFPOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: ConstantOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: InstructionOperandCount: 7
 ; DETAILED-PROPERTIES-DAG: BasicBlockOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: GlobalValueOperandCount: 1
 ; DETAILED-PROPERTIES-DAG: InlineAsmOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: ArgumentOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: UnknownOperandCount: 0
+; DETAILED-PROPERTIES-DAG: DirectCallCount: 1
+; DETAILED-PROPERTIES-DAG: IndirectCallCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsIntegerCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsFloatCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsPointerCount: 0
+; DETAILED-PROPERTIES-DAG: CallWithManyArgumentsCount: 0
+; DETAILED-PROPERTIES-DAG: CallWithPointerArgumentCount: 1
 
 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

 ; DETAILED-PROPERTIES-DAG: ConstantFPOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: ConstantOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: InstructionOperandCount: 73
 ; DETAILED-PROPERTIES-DAG: BasicBlockOperandCount: 15
 ; DETAILED-PROPERTIES-DAG: GlobalValueOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: InlineAsmOperandCount: 0
 ; DETAILED-PROPERTIES-DAG: ArgumentOperandCount: 3
 ; DETAILED-PROPERTIES-DAG: UnknownOperandCount: 0
+; DETAILED-PROPERTIES-DAG: DirectCallCount: 0
+; DETAILED-PROPERTIES-DAG: IndirectCallCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsIntegerCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsFloatCount: 0
+; DETAILED-PROPERTIES-DAG: CallReturnsPointerCount: 0
+; DETAILED-PROPERTIES-DAG: CallWithManyArgumentsCount: 0
+; DETAILED-PROPERTIES-DAG: CallWithPointerArgumentCount: 0
 

llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp

)IR");
   EXPECT_EQ(DetailedBranchesFeatures.ConstantFPOperandCount, 0);
   EXPECT_EQ(DetailedBranchesFeatures.ConstantOperandCount, 0);
   EXPECT_EQ(DetailedBranchesFeatures.InstructionOperandCount, 4);
   EXPECT_EQ(DetailedBranchesFeatures.BasicBlockOperandCount, 4);
   EXPECT_EQ(DetailedBranchesFeatures.GlobalValueOperandCount, 2);
   EXPECT_EQ(DetailedBranchesFeatures.InlineAsmOperandCount, 0);
   EXPECT_EQ(DetailedBranchesFeatures.ArgumentOperandCount, 3);
   EXPECT_EQ(DetailedBranchesFeatures.UnknownOperandCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.CriticalEdgeCount, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.ControlFlowEdgeCount, 4);
+  EXPECT_EQ(DetailedBranchesFeatures.UnconditionalBranchCount, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.IntrinsicCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.DirectCallCount, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.IndirectCallCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.CallReturnsIntegerCount, 2);
+  EXPECT_EQ(DetailedBranchesFeatures.CallReturnsFloatCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.CallReturnsPointerCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.CallWithManyArgumentsCount, 0);
+  EXPECT_EQ(DetailedBranchesFeatures.CallWithPointerArgumentCount, 0);
   EnableDetailedFunctionProperties.setValue(false);
 }
 
 TEST_F(FunctionPropertiesAnalysisTest, DifferentPredecessorSuccessorCounts) {
   LLVMContext C;
   std::unique_ptr<Module> M = makeLLVMModule(C,
                                              R"IR(
 define i64 @f1() {
)IR");
   EXPECT_EQ(DetailedF1Properties.ConstantFPOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.ConstantOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.InstructionOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.BasicBlockOperandCount, 2);
   EXPECT_EQ(DetailedF1Properties.GlobalValueOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.InlineAsmOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.ArgumentOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.UnknownOperandCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CriticalEdgeCount, 0);
+  EXPECT_EQ(DetailedF1Properties.ControlFlowEdgeCount, 2);
+  EXPECT_EQ(DetailedF1Properties.UnconditionalBranchCount, 0);
+  EXPECT_EQ(DetailedF1Properties.IntrinsicCount, 0);
+  EXPECT_EQ(DetailedF1Properties.DirectCallCount, 0);
+  EXPECT_EQ(DetailedF1Properties.IndirectCallCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsIntegerCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsFloatCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsPointerCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithManyArgumentsCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithPointerArgumentCount, 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"
)IR");
   EXPECT_EQ(DetailedF1Properties.ConstantFPOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.ConstantOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.InstructionOperandCount, 4);
   EXPECT_EQ(DetailedF1Properties.BasicBlockOperandCount, 0);
   EXPECT_EQ(DetailedF1Properties.GlobalValueOperandCount, 1);
   EXPECT_EQ(DetailedF1Properties.InlineAsmOperandCount, 1);
   EXPECT_EQ(DetailedF1Properties.ArgumentOperandCount, 1);
   EXPECT_EQ(DetailedF1Properties.UnknownOperandCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CriticalEdgeCount, 0);
+  EXPECT_EQ(DetailedF1Properties.ControlFlowEdgeCount, 0);
+  EXPECT_EQ(DetailedF1Properties.UnconditionalBranchCount, 0);
+  EXPECT_EQ(DetailedF1Properties.IntrinsicCount, 0);
+  EXPECT_EQ(DetailedF1Properties.DirectCallCount, 1);
+  EXPECT_EQ(DetailedF1Properties.IndirectCallCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsIntegerCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsFloatCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsPointerCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithManyArgumentsCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithPointerArgumentCount, 0);
+  EnableDetailedFunctionProperties.setValue(false);
+}
+
+TEST_F(FunctionPropertiesAnalysisTest, IntrinsicCount) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = makeLLVMModule(C,
+                                             R"IR(
+define float @f1(float %a) {
+  %b = call float @llvm.cos.f32(float %a)
+  ret float %b
+}
+declare float @llvm.cos.f32(float)
+)IR");
+
+  Function *F1 = M->getFunction("f1");
+  EnableDetailedFunctionProperties.setValue(true);
+  FunctionPropertiesInfo DetailedF1Properties = buildFPI(*F1);
+  EXPECT_EQ(DetailedF1Properties.IntrinsicCount, 1);
+  EXPECT_EQ(DetailedF1Properties.DirectCallCount, 1);
+  EXPECT_EQ(DetailedF1Properties.IndirectCallCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsIntegerCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsFloatCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsPointerCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithManyArgumentsCount, 0);
+  EXPECT_EQ(DetailedF1Properties.CallWithPointerArgumentCount, 0);
+  EnableDetailedFunctionProperties.setValue(false);
+}
+
+TEST_F(FunctionPropertiesAnalysisTest, FunctionCallMetrics) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = makeLLVMModule(C,
+                                             R"IR(
+define i64 @f1(i64 %a) {
+  %b = call i64 @f2(i64 %a, i64 %a, i64 %a, i64 %a, i64 %a)
+  %c = call ptr @f3()
+  call void @f4(ptr %c)
+  %d = call float @f5()
+  %e = call i64 %c(i64 %b)
+  ret i64 %b
+}
+
+declare i64 @f2(i64,i64,i64,i64,i64)
+declare ptr @f3()
+declare void @f4(ptr)
+declare float @f5()
+)IR");
+
+  Function *F1 = M->getFunction("f1");
+  EnableDetailedFunctionProperties.setValue(true);
+  FunctionPropertiesInfo DetailedF1Properties = buildFPI(*F1);
+  EXPECT_EQ(DetailedF1Properties.IntrinsicCount, 0);
+  EXPECT_EQ(DetailedF1Properties.DirectCallCount, 4);
+  EXPECT_EQ(DetailedF1Properties.IndirectCallCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsIntegerCount, 2);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsFloatCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallReturnsPointerCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallWithManyArgumentsCount, 1);
+  EXPECT_EQ(DetailedF1Properties.CallWithPointerArgumentCount, 1);
   EnableDetailedFunctionProperties.setValue(false);
 }
 } // end anonymous namespace