[llvm] Add function feature extraction analysis

[mtrofin]

Summary

This patch introduces an analysis pass to extract function features,
which will be needed by the ML InlineAdvisor.

RFC: http://lists.llvm.org/pipermail/llvm-dev/2020-April/140763.html

[jdoerfert]

llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp

13

Note: We could count Uses with getNumUses instead. For inlining there is probably no difference as non-callee uses cannot be inlined anyway, though I somehow feel it might be cleaner.

30

This seems to be a very crude approximation. Do we have to be super fast here or would it make sense to improve on this? I mean, if I read ConditionallyExecutedBlocks I assume blocks not post-dominating the entry of a function, though this counts something else. Simplest example to see the difference is if (a) s(); which would result in 3 blocks, and ConditionallyExecutedBlocks would say 2, though I argue it should be 1.

Either way, we should rename *and* document the Result members. InternalCalls seems to count calls to definitions, not to internal functions.

[mtrofin]

renamed & documented members

llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp

30

Agreed it's crude. We'd want to improve the feature set subsequently in a number of ways, I left a FIXME here with your example, and also renamed / documented members.

[jdoerfert]

Last high-level comment: Should we call this "FeatureAnalysis" (without the Inline)? I can see us reusing this for other (ML) purposes. Nothing in this code is really tied or specific to the inliner I guess.

That said, I think the "analysis" is reasonable given the FIXME (thx!). It is clear there is improvement potential and the results are properly named and described.

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

33

Nit: We now count Uses, not Users.
Nit: uint64_t as all are counts.

[mtrofin]

In D80579#2056301, @jdoerfert wrote:

Last high-level comment: Should we call this "FeatureAnalysis" (without the Inline)? I can see us reusing this for other (ML) purposes. Nothing in this code is really tied or specific to the inliner I guess.

That said, I think the "analysis" is reasonable given the FIXME (thx!). It is clear there is improvement potential and the results are properly named and described.

I'd prefer waiting to see another usecase before renaming, or potentially refactoring (depends on what we'll learn when we get to that usecase) - wdyt?

[mtrofin]

feedback

[mtrofin]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

33

Done the rename part.

Re. signedness / unsignedness: initially, I had them as size_t, but:

• tensorflow works with signed values, and it is the main consumer of this data
• one other use in the (next CL) MLInlineAdvisor is to delta-update some module-wide values (like total nr of edges in a module). With uint64_t, we need to be very careful with how that update happens (subtractions can silently overflow).

With signed int, that's not a problem.

[jdoerfert]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

33

Fair enough.

[mtrofin]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

33

Is the patch good to go?

Thanks!

[jdoerfert]

I don't think this will impact anyone right now so there is little risk. LGTM

[MaskRay]

We should use add_llvm_component_library and LLVMBuild.txt instead of LINK_LIBS (LINK_LIBS are used for system libraries like pthread). There is also a missing dependency in LLVMPasses.

I fixed it in 993bbaf6a35baed4ad3d8422a76c4311140641a8

[rriddle]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

2

These files are missing license headers BTW. Not sure if that was intentional.

[mtrofin]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

2

It wasn't - let me correct that. I'll send a patch shortly and link it here.

[mtrofin]

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

2

https://reviews.llvm.org/D81896

llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h

+#ifndef LLVM_INLINEFEATURESANALYSIS_H_
+#define LLVM_INLINEFEATURESANALYSIS_H_
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+class Function;
+
+class InlineFeaturesAnalysis
+    : public AnalysisInfoMixin<InlineFeaturesAnalysis> {
+public:
+  static AnalysisKey Key;
+  struct Result {
+    /// Number of basic blocks
+    int64_t BasicBlockCount = 0;
+
+    /// Number of blocks reached from a conditional instruction, or that are
+    /// 'cases' of a SwitchInstr.
+    // FIXME: We may want to replace this with a more meaningful metric, like
+    // number of conditionally executed blocks:
+    // 'if (a) s();' would be counted here as 2 blocks, just like
+    // 'if (a) s(); else s2(); s3();' would.
+    int64_t BlocksReachedFromConditionalInstruction = 0;
+
+    /// Number of uses of this function, plus 1 if the function is callable
+    /// outside the module.
+    int64_t Uses = 0;
+
+    /// Number of direct calls made from this function to other functions
+    /// defined in this module.
+    int64_t DirectCallsToDefinedFunctions = 0;
+  };
+  Result run(const Function &F, FunctionAnalysisManager &FAM);
+};
+
+} // namespace llvm
+#endif // LLVM_INLINEFEATURESANALYSIS_H_
 No newline at end of file

llvm/lib/Analysis/CMakeLists.txt

+add_subdirectory(ML)
+
 add_llvm_component_library(LLVMAnalysis
   AliasAnalysis.cpp
   AliasAnalysisEvaluator.cpp
   AliasAnalysisSummary.cpp
   AliasSetTracker.cpp
   Analysis.cpp
   AssumeBundleQueries.cpp
   AssumptionCache.cpp
add_llvm_component_library(LLVMAnalysis
   VectorUtils.cpp
   VFABIDemangling.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Analysis
 
   DEPENDS
   intrinsics_gen
+  LLVMMLPolicies
+
+
+  LINK_LIBS
+  LLVMMLPolicies
   )

llvm/lib/Analysis/ML/CMakeLists.txt

+set (SOURCES InlineFeaturesAnalysis.cpp)
+
+add_llvm_library(LLVMMLPolicies STATIC
+  ${SOURCES}
+
+  DEPENDS
+  intrinsics_gen
+
+  )

llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp

+#include "llvm/Analysis/ML/InlineFeaturesAnalysis.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+AnalysisKey InlineFeaturesAnalysis::Key;
+
+InlineFeaturesAnalysis::Result
+InlineFeaturesAnalysis::run(const Function &F, FunctionAnalysisManager &FAM) {
+  Result Ret;
+  Ret.Uses = ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
+  for (const auto &BB : F) {
+    ++Ret.BasicBlockCount;
+    if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
+      if (BI->isConditional())
+        Ret.BlocksReachedFromConditionalInstruction += BI->getNumSuccessors();
+    } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator()))
+      Ret.BlocksReachedFromConditionalInstruction +=
+          (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
+    for (const auto &I : BB)
+      if (auto *CS = dyn_cast<CallBase>(&I)) {
+        const auto *Callee = CS->getCalledFunction();
+        if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
+          ++Ret.DirectCallsToDefinedFunctions;
+      }
+  }
+  return Ret;
+}
 No newline at end of file

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopCacheAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopNestAnalysis.h"
+#include "llvm/Analysis/ML/InlineFeaturesAnalysis.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/RegionInfo.h"

llvm/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())
+FUNCTION_ANALYSIS("inliner-features", InlineFeaturesAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis())
 FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("stack-safety-local", StackSafetyAnalysis())

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzerTest.cpp
   ValueLatticeTest.cpp
   ValueTrackingTest.cpp
   VectorUtilsTest.cpp
   )
+
+add_subdirectory(ML)
 No newline at end of file

llvm/unittests/Analysis/ML/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Analysis  
+  AsmParser
+  Core
+  MLPolicies
+  Support
+  TransformUtils
+  )
+
+add_llvm_unittest(MLAnalysisTests
+  InlineFeaturesAnalysisTest.cpp
+  )

llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp

+//===- InlineFeaturesAnalysisTest.cpp - inline features unit tests --------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ML/InlineFeaturesAnalysis.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+  if (!Mod)
+    Err.print("MLAnalysisTests", errs());
+  return Mod;
+}
+
+TEST(InlineFeaturesTest, BasicTest) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = parseIR(C,
+                                      R"IR(
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+declare i32 @f1(i32)
+declare i32 @f2(i32)
+
+define i32 @branches(i32) {
+  %cond = icmp slt i32 %0, 3
+  br i1 %cond, label %then, label %else
+
+then:
+  %ret.1 = call i32 @f1(i32 %0)
+  br label %last.block
+
+else:
+  %ret.2 = call i32 @f2(i32 %0)
+  br label %last.block
+
+last.block:
+  %ret = phi i32 [%ret.1, %then], [%ret.2, %else]
+  ret i32 %ret
+}
+
+define internal i32 @top() {
+  %1 = call i32 @branches(i32 2)
+  %2 = call i32 @f1(i32 %1)
+  ret i32 %2
+}
+)IR");
+
+  FunctionAnalysisManager FAM;
+  InlineFeaturesAnalysis FA;
+
+  auto BranchesFeatures = FA.run(*M->getFunction("branches"), FAM);
+  EXPECT_EQ(BranchesFeatures.BasicBlockCount, 4);
+  EXPECT_EQ(BranchesFeatures.BlocksReachedFromConditionalInstruction, 2);
+  EXPECT_EQ(BranchesFeatures.DirectCallsToDefinedFunctions, 0);
+  // 2 Users: top is one. The other is added because @branches is not internal,
+  // so it may have external callers.
+  EXPECT_EQ(BranchesFeatures.Uses, 2);
+
+  auto TopFeatures = FA.run(*M->getFunction("top"), FAM);
+  EXPECT_EQ(TopFeatures.BasicBlockCount, 1);
+  EXPECT_EQ(TopFeatures.BlocksReachedFromConditionalInstruction, 0);
+  EXPECT_EQ(TopFeatures.DirectCallsToDefinedFunctions, 1);
+  EXPECT_EQ(TopFeatures.Uses, 0);
+}