diff --git a/llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h b/llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h @@ -0,0 +1,37 @@ +#ifndef LLVM_INLINEFEATURESANALYSIS_H_ +#define LLVM_INLINEFEATURESANALYSIS_H_ + +#include "llvm/IR/PassManager.h" + +namespace llvm { +class Function; + +class InlineFeaturesAnalysis + : public AnalysisInfoMixin { +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 diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -1,3 +1,5 @@ +add_subdirectory(ML) + add_llvm_component_library(LLVMAnalysis AliasAnalysis.cpp AliasAnalysisEvaluator.cpp @@ -106,4 +108,9 @@ DEPENDS intrinsics_gen + LLVMMLPolicies + + + LINK_LIBS + LLVMMLPolicies ) diff --git a/llvm/lib/Analysis/ML/CMakeLists.txt b/llvm/lib/Analysis/ML/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/ML/CMakeLists.txt @@ -0,0 +1,9 @@ +set (SOURCES InlineFeaturesAnalysis.cpp) + +add_llvm_library(LLVMMLPolicies STATIC + ${SOURCES} + + DEPENDS + intrinsics_gen + + ) diff --git a/llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp b/llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp @@ -0,0 +1,28 @@ +#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(BB.getTerminator())) { + if (BI->isConditional()) + Ret.BlocksReachedFromConditionalInstruction += BI->getNumSuccessors(); + } else if (const auto *SI = dyn_cast(BB.getTerminator())) + Ret.BlocksReachedFromConditionalInstruction += + (SI->getNumCases() + (nullptr != SI->getDefaultDest())); + for (const auto &I : BB) + if (auto *CS = dyn_cast(&I)) { + const auto *Callee = CS->getCalledFunction(); + if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration()) + ++Ret.DirectCallsToDefinedFunctions; + } + } + return Ret; +} \ No newline at end of file diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -40,6 +40,7 @@ #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" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -134,6 +134,7 @@ 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()) diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt --- a/llvm/unittests/Analysis/CMakeLists.txt +++ b/llvm/unittests/Analysis/CMakeLists.txt @@ -41,3 +41,5 @@ ValueTrackingTest.cpp VectorUtilsTest.cpp ) + +add_subdirectory(ML) \ No newline at end of file diff --git a/llvm/unittests/Analysis/ML/CMakeLists.txt b/llvm/unittests/Analysis/ML/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/unittests/Analysis/ML/CMakeLists.txt @@ -0,0 +1,12 @@ +set(LLVM_LINK_COMPONENTS + Analysis + AsmParser + Core + MLPolicies + Support + TransformUtils + ) + +add_llvm_unittest(MLAnalysisTests + InlineFeaturesAnalysisTest.cpp + ) diff --git a/llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp b/llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp @@ -0,0 +1,77 @@ +//===- 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 parseIR(LLVMContext &C, const char *IR) { + SMDiagnostic Err; + std::unique_ptr Mod = parseAssemblyString(IR, Err, C); + if (!Mod) + Err.print("MLAnalysisTests", errs()); + return Mod; +} + +TEST(InlineFeaturesTest, BasicTest) { + LLVMContext C; + std::unique_ptr 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); +}