Index: llvm/include/llvm/Analysis/ML/FunctionPropertiesAnalysis.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/ML/FunctionPropertiesAnalysis.h @@ -0,0 +1,72 @@ +//===- FunctionPropertiesAnalysis.h - Function Properties Analysis ----------*- C++ -*-===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUNCTIONPROPERTIESANALYSIS_H_ +#define LLVM_FUNCTIONPROPERTIESANALYSIS_H_ + +#include "llvm/IR/PassManager.h" + +namespace llvm { +class Function; + +class FunctionPropertiesInfo{ + public: + /// 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; + + void analyze(const Function &F); + + void print(raw_ostream &OS) const; +}; + +//Analysis pass +class FunctionPropertiesAnalysis + : public AnalysisInfoMixin { + + public: + static AnalysisKey Key; + + using Result = FunctionPropertiesInfo; + + Result run(Function &F, FunctionAnalysisManager &FAM); +}; + +/// Printer pass for the FunctionPropertiesAnalysis results. +class FunctionPropertiesPrinterPass + : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit FunctionPropertiesPrinterPass(raw_ostream &OS) : OS(OS) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // namespace llvm +#endif // LLVM_FUNCTIONPROPERTIESANALYSIS_H_ \ No newline at end of file Index: llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/ML/InlineFeaturesAnalysis.h +++ /dev/null @@ -1,37 +0,0 @@ -#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 Index: llvm/lib/Analysis/ML/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/ML/CMakeLists.txt +++ llvm/lib/Analysis/ML/CMakeLists.txt @@ -1,5 +1,5 @@ add_llvm_component_library(LLVMMLPolicies - InlineFeaturesAnalysis.cpp + FunctionPropertiesAnalysis.cpp DEPENDS intrinsics_gen Index: llvm/lib/Analysis/ML/FunctionPropertiesAnalysis.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/ML/FunctionPropertiesAnalysis.cpp @@ -0,0 +1,69 @@ +//===- 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/ML/FunctionPropertiesAnalysis.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Passes/PassBuilder.h" +#include "llvm/Passes/PassPlugin.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +void FunctionPropertiesInfo::analyze(const Function &F) { + + Uses = ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses(); + + for (const auto &BB : F) { + ++BasicBlockCount; + + if (const auto *BI = dyn_cast(BB.getTerminator())) { + if (BI->isConditional()) + BlocksReachedFromConditionalInstruction += BI->getNumSuccessors(); + } else if (const auto *SI = dyn_cast(BB.getTerminator())) { + 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()) + ++DirectCallsToDefinedFunctions; + } + } + } +} + +void FunctionPropertiesInfo::print(raw_ostream &OS) const { + OS << "BasicBlockCount: " << BasicBlockCount << "\n" + << "BlocksReachedFromConditionalInstruction: " << BlocksReachedFromConditionalInstruction << "\n" + << "Uses: " << Uses << "\n" + << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions << "\n\n"; +} + +AnalysisKey FunctionPropertiesAnalysis::Key; + +FunctionPropertiesInfo FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { + FunctionPropertiesInfo CFI; + CFI.analyze(F); + return CFI; +} + + +PreservedAnalyses FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { + OS << "Printing analysis results of CFA for function " + << "'" << F.getName() << "':" + << "\n"; + AM.getResult(F).print(OS); + return PreservedAnalyses::all(); +} Index: llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp =================================================================== --- llvm/lib/Analysis/ML/InlineFeaturesAnalysis.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#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 Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ llvm/lib/Passes/PassBuilder.cpp @@ -40,7 +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/ML/FunctionPropertiesAnalysis.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -126,6 +126,7 @@ FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis()) FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis()) FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis()) +FUNCTION_ANALYSIS("func-properties", FunctionPropertiesAnalysis()) FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis()) @@ -133,7 +134,6 @@ 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()) @@ -228,6 +228,7 @@ FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) FUNCTION_PASS("print", BranchProbabilityPrinterPass(dbgs())) +FUNCTION_PASS("print", FunctionPropertiesPrinterPass(dbgs())) FUNCTION_PASS("print", DependenceAnalysisPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) Index: llvm/unittests/Analysis/ML/CMakeLists.txt =================================================================== --- llvm/unittests/Analysis/ML/CMakeLists.txt +++ llvm/unittests/Analysis/ML/CMakeLists.txt @@ -8,5 +8,5 @@ ) add_llvm_unittest(MLAnalysisTests - InlineFeaturesAnalysisTest.cpp + FunctionPropertiesAnalysisTest.cpp ) Index: llvm/unittests/Analysis/ML/FunctionPropertiesAnalysisTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/Analysis/ML/FunctionPropertiesAnalysisTest.cpp @@ -0,0 +1,165 @@ +//===- FunctionPropertiesAnalysisTest.cpp - Function Properties 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/FunctionPropertiesAnalysis.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 makeLLVMModule(LLVMContext &C, const char *IR) { + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString(IR, Err, C); + if (!M) + Err.print("MLAnalysisTests", errs()); + return M; +} + +TEST(FunctionPropertiesTest, BasicTest) { + LLVMContext C; + std::unique_ptr M = makeLLVMModule(C, + R"IR( +define i32 @main() #0 { +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 +} + +define void @multiply([2 x i32]* %mat1, [2 x i32]* %mat2, [2 x i32]* %res) #0 { +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 + store [2 x i32]* %mat2, [2 x i32]** %mat2.addr, align 8 + store [2 x i32]* %res, [2 x i32]** %res.addr, align 8 + store i32 0, i32* %i, align 4 + br label %for.cond + +for.cond: ; preds = %for.inc24, %entry + %0 = load i32, i32* %i, align 4 + %cmp = icmp slt i32 %0, 2 + br i1 %cmp, label %for.body, label %for.end26 + +for.body: ; preds = %for.cond + store i32 0, i32* %j, align 4 + br label %for.cond1 + +for.cond1: ; preds = %for.inc21, %for.body + %1 = load i32, i32* %j, align 4 + %cmp2 = icmp slt i32 %1, 2 + br i1 %cmp2, label %for.body3, label %for.end23 + +for.body3: ; preds = %for.cond1 + %2 = load [2 x i32]*, [2 x i32]** %res.addr, align 8 + %3 = load i32, i32* %i, align 4 + %idxprom = sext i32 %3 to i64 + %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %2, i64 %idxprom + %4 = load i32, i32* %j, align 4 + %idxprom4 = sext i32 %4 to i64 + %arrayidx5 = getelementptr inbounds [2 x i32], [2 x i32]* %arrayidx, i64 0, i64 %idxprom4 + store i32 0, i32* %arrayidx5, align 4 + store i32 0, i32* %k, align 4 + br label %for.cond6 + +for.cond6: ; preds = %for.inc, %for.body3 + %5 = load i32, i32* %k, align 4 + %cmp7 = icmp slt i32 %5, 2 + br i1 %cmp7, label %for.body8, label %for.end + +for.body8: ; preds = %for.cond6 + %6 = load [2 x i32]*, [2 x i32]** %mat1.addr, align 8 + %7 = load i32, i32* %i, align 4 + %idxprom9 = sext i32 %7 to i64 + %arrayidx10 = getelementptr inbounds [2 x i32], [2 x i32]* %6, i64 %idxprom9 + %8 = load i32, i32* %k, align 4 + %idxprom11 = sext i32 %8 to i64 + %arrayidx12 = getelementptr inbounds [2 x i32], [2 x i32]* %arrayidx10, i64 0, i64 %idxprom11 + %9 = load i32, i32* %arrayidx12, align 4 + %10 = load [2 x i32]*, [2 x i32]** %mat2.addr, align 8 + %11 = load i32, i32* %k, align 4 + %idxprom13 = sext i32 %11 to i64 + %arrayidx14 = getelementptr inbounds [2 x i32], [2 x i32]* %10, i64 %idxprom13 + %12 = load i32, i32* %j, align 4 + %idxprom15 = sext i32 %12 to i64 + %arrayidx16 = getelementptr inbounds [2 x i32], [2 x i32]* %arrayidx14, i64 0, i64 %idxprom15 + %13 = load i32, i32* %arrayidx16, align 4 + %mul = mul nsw i32 %9, %13 + %14 = load [2 x i32]*, [2 x i32]** %res.addr, align 8 + %15 = load i32, i32* %i, align 4 + %idxprom17 = sext i32 %15 to i64 + %arrayidx18 = getelementptr inbounds [2 x i32], [2 x i32]* %14, i64 %idxprom17 + %16 = load i32, i32* %j, align 4 + %idxprom19 = sext i32 %16 to i64 + %arrayidx20 = getelementptr inbounds [2 x i32], [2 x i32]* %arrayidx18, i64 0, i64 %idxprom19 + %17 = load i32, i32* %arrayidx20, align 4 + %add = add nsw i32 %17, %mul + store i32 %add, i32* %arrayidx20, align 4 + br label %for.inc + +for.inc: ; preds = %for.body8 + %18 = load i32, i32* %k, align 4 + %inc = add nsw i32 %18, 1 + store i32 %inc, i32* %k, align 4 + br label %for.cond6 + +for.end: ; preds = %for.cond6 + br label %for.inc21 + +for.inc21: ; preds = %for.end + %19 = load i32, i32* %j, align 4 + %inc22 = add nsw i32 %19, 1 + store i32 %inc22, i32* %j, align 4 + br label %for.cond1 + +for.end23: ; preds = %for.cond1 + br label %for.inc24 + +for.inc24: ; preds = %for.end23 + %20 = load i32, i32* %i, align 4 + %inc25 = add nsw i32 %20, 1 + store i32 %inc25, i32* %i, align 4 + br label %for.cond + +for.end26: ; preds = %for.cond + ret void +} +)IR"); + + FunctionAnalysisManager FAM; + FunctionPropertiesAnalysis CFA; + + auto MainFeatures = CFA.run(*M->getFunction("main"), FAM); + EXPECT_EQ(MainFeatures.BasicBlockCount, 1); + EXPECT_EQ(MainFeatures.BlocksReachedFromConditionalInstruction, 0); + EXPECT_EQ(MainFeatures.DirectCallsToDefinedFunctions, 1); + EXPECT_EQ(MainFeatures.Uses, 1); + + auto MultiplyFeatures = CFA.run(*M->getFunction("multiply"), FAM); + EXPECT_EQ(MultiplyFeatures.BasicBlockCount, 13); + EXPECT_EQ(MultiplyFeatures.BlocksReachedFromConditionalInstruction, 6); + EXPECT_EQ(MultiplyFeatures.DirectCallsToDefinedFunctions, 0); + EXPECT_EQ(MultiplyFeatures.Uses, 2); +} Index: llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp =================================================================== --- llvm/unittests/Analysis/ML/InlineFeaturesAnalysisTest.cpp +++ /dev/null @@ -1,77 +0,0 @@ -//===- 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); -}