diff --git a/llvm/include/llvm/Analysis/LoopPropertiesAnalysis.h b/llvm/include/llvm/Analysis/LoopPropertiesAnalysis.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/LoopPropertiesAnalysis.h @@ -0,0 +1,106 @@ +//=- LoopPropertiesAnalysis.h - Loop 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 LoopPropertiesInfo and LoopPropertiesAnalysis +// classes used to extract loop properties. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPPROPERTIESANALYSIS_H +#define LLVM_ANALYSIS_LOOPPROPERTIESANALYSIS_H + +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/PassManager.h" + +#include + +namespace llvm { + +class LPMUpdater; +class Loop; +class raw_ostream; + +class LoopPropertiesInfo { +public: + static LoopPropertiesInfo getLoopPropertiesInfo(Loop *L, LoopInfo *LI, + ScalarEvolution *SE); + + void print(raw_ostream &OS) const; + + /// Is Innermost Loop + bool IsInnerMostLoop = false; + uint64_t LoopDepth = 0; + + /// Preheader Block Size (by instructions) + bool HasLoopPreheader = false; + uint64_t PreheaderBlocksize = 0; + + /// Is Countable Loop + bool IsCountableLoop = false; + + /// Loop Backedge Count (if countable) + bool IsLoopBackEdgeConstant = false; + APInt LoopBackEdgeCount; + + /// Number of basic blocks + /// Ignoring blocks for subloops + uint64_t BasicBlockCount = 0; + + /// Loop Block Sizes (block size, loop count) + /// Ignoring blocks for subloops + std::map LoopBlocksizes; + + /// Number of loop latches + uint64_t LoopLatchCount = 0; + + /// Load Instruction Count + uint64_t LoadInstCount = 0; + + /// Store Instruction Count + uint64_t StoreInstCount = 0; + + /// Binary instructions Count + uint64_t BinaryInstCount = 0; + + /// Logical Instruction Count + uint64_t LogicalInstCount = 0; + + /// Cast Instruction Count + uint64_t CastInstCount = 0; +}; + +// Analysis pass +class LoopPropertiesAnalysis + : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static AnalysisKey Key; + +public: + using Result = const LoopPropertiesInfo; + + LoopPropertiesInfo run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR); +}; + +/// Printer pass for the LoopPropertiesAnalysis results. +class LoopPropertiesPrinterPass + : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit LoopPropertiesPrinterPass(raw_ostream &OS) : OS(OS) {} + + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // namespace llvm +#endif // LLVM_ANALYSIS_LOOPPROPERTIESANALYSIS_H 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 @@ -95,6 +95,7 @@ LoopAnalysisManager.cpp LoopCacheAnalysis.cpp LoopNestAnalysis.cpp + LoopPropertiesAnalysis.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp diff --git a/llvm/lib/Analysis/LoopPropertiesAnalysis.cpp b/llvm/lib/Analysis/LoopPropertiesAnalysis.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/LoopPropertiesAnalysis.cpp @@ -0,0 +1,117 @@ +//===- LoopPropertiesAnalysis.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 LoopPropertiesInfo and LoopPropertiesAnalysis +// classes used to extract function properties. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopPropertiesAnalysis.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" + +using namespace llvm; + +LoopPropertiesInfo +LoopPropertiesInfo::getLoopPropertiesInfo(Loop *L, LoopInfo *LI, + ScalarEvolution *SE) { + + LoopPropertiesInfo LPI; + + LPI.IsInnerMostLoop = L->isInnermost(); + LPI.LoopDepth = L->getLoopDepth(); + + if (BasicBlock *Preheader = L->getLoopPreheader()) { + LPI.HasLoopPreheader = true; + LPI.PreheaderBlocksize = Preheader->size(); + } + + if (SE->hasLoopInvariantBackedgeTakenCount(L)) { + LPI.IsCountableLoop = true; + const SCEV *BECount = SE->getBackedgeTakenCount(L); + if (const SCEVConstant *BEConst = dyn_cast(BECount)) { + LPI.IsLoopBackEdgeConstant = true; + LPI.LoopBackEdgeCount = BEConst->getAPInt(); + } + } + + for (BasicBlock *BB : L->getBlocks()) { + // Ignore blocks in subloops. + if (LI->getLoopFor(BB) != L) + continue; + + ++LPI.BasicBlockCount; + ++LPI.LoopBlocksizes[BB->size()]; + + if (L->isLoopLatch(BB)) + ++LPI.LoopLatchCount; + + for (Instruction &I : *BB) { + unsigned Opcode = I.getOpcode(); + if (Opcode == Instruction::Load) { + ++LPI.LoadInstCount; + } else if (Opcode == Instruction::Store) { + ++LPI.StoreInstCount; + } else if (Instruction::Add <= Opcode && Opcode <= Instruction::FRem) { + ++LPI.BinaryInstCount; + } else if (Instruction::Shl <= Opcode && Opcode <= Instruction::Xor) { + ++LPI.LogicalInstCount; + } else if (Instruction::Trunc <= Opcode && + Opcode <= Instruction::AddrSpaceCast) { + ++LPI.CastInstCount; + } + } + } + + return LPI; +} + +void LoopPropertiesInfo::print(raw_ostream &OS) const { + OS << "IsInnerMostLoop: " << IsInnerMostLoop << "\n" + << "LoopDepth: " << LoopDepth << "\n" + << "HasLoopPreheader: " << HasLoopPreheader << "\n" + << "PreheaderBlocksize: " << PreheaderBlocksize << "\n" + << "IsCountableLoop: " << IsCountableLoop << "\n" + << "IsLoopBackEdgeConstant: " << IsLoopBackEdgeConstant << "\n" + << "LoopBackEdgeCount: " << LoopBackEdgeCount << "\n" + << "BasicBlockCount: " << BasicBlockCount << "\n" + << "LoopBlocksizes: "; + for (auto Pair : LoopBlocksizes) { + OS << "{" << Pair.first << ", " << Pair.second << "} "; + } + OS << "\n"; + OS << "LoopLatchCount: " << LoopLatchCount << "\n" + << "LoadInstCount: " << LoadInstCount << "\n" + << "StoreInstCount: " << StoreInstCount << "\n" + << "BinaryInstCount: " << BinaryInstCount << "\n" + << "LogicalInstCount: " << LogicalInstCount << "\n" + << "CastInstCount: " << CastInstCount << "\n\n"; +} + +AnalysisKey LoopPropertiesAnalysis::Key; + +LoopPropertiesInfo +LoopPropertiesAnalysis::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR) { + return LoopPropertiesInfo::getLoopPropertiesInfo(&L, &AR.LI, &AR.SE); +} + +PreservedAnalyses +LoopPropertiesPrinterPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U) { + OS << "Printing analysis results for Loop " + << "'" << L.getName() << "':" + << "\n"; + AM.getResult(L, AR).print(OS); + // AM.getResult(L, AR).print(OS); + // AM.getResult(*L, LAR); + return PreservedAnalyses::all(); +} 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 @@ -51,6 +51,7 @@ #include "llvm/Analysis/LoopCacheAnalysis.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/Analysis/LoopPropertiesAnalysis.h" #include "llvm/Analysis/MemDerefPrinter.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemorySSA.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 @@ -516,6 +516,7 @@ LOOP_ANALYSIS("ddg", DDGAnalysis()) LOOP_ANALYSIS("iv-users", IVUsersAnalysis()) LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) +LOOP_ANALYSIS("loop-properties", LoopPropertiesAnalysis()) #undef LOOP_ANALYSIS #ifndef LOOP_PASS @@ -538,6 +539,7 @@ LOOP_PASS("print", IVUsersPrinterPass(dbgs())) LOOP_PASS("print", LoopNestPrinterPass(dbgs())) LOOP_PASS("print", LoopCachePrinterPass(dbgs())) +LOOP_PASS("print", LoopPropertiesPrinterPass(dbgs())) LOOP_PASS("loop-predication", LoopPredicationPass()) LOOP_PASS("guard-widening", GuardWideningPass()) LOOP_PASS("loop-bound-split", LoopBoundSplitPass()) 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 @@ -33,6 +33,7 @@ LoadsTest.cpp LoopInfoTest.cpp LoopNestTest.cpp + LoopPropertiesAnalysisTest.cpp MemoryBuiltinsTest.cpp MemoryProfileInfoTest.cpp MemorySSATest.cpp diff --git a/llvm/unittests/Analysis/LoopPropertiesAnalysisTest.cpp b/llvm/unittests/Analysis/LoopPropertiesAnalysisTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Analysis/LoopPropertiesAnalysisTest.cpp @@ -0,0 +1,137 @@ +//===- LoopPropertiesAnalysisTest.cpp - LoopInfo 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/LoopPropertiesAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/Support/SourceMgr.h" +#include "gtest/gtest.h" + +using namespace llvm; +namespace { + +static std::unique_ptr makeLLVMModule(LLVMContext &Context, + const char *ModuleStr) { + SMDiagnostic Err; + return parseAssemblyString(ModuleStr, Err, Context); +} + +/// Build the loop info and scalar evolution for the function and run the Test. +static void runWithLoopInfo( + Module &M, StringRef FuncName, + function_ref Test) { + auto *F = M.getFunction(FuncName); + ASSERT_NE(F, nullptr) << "Could not find " << FuncName; + + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI(TLII); + AssumptionCache AC(*F); + DominatorTree DT(*F); + LoopInfo LI(DT); + ScalarEvolution SE(*F, TLI, AC, DT, LI); + Test(*F, LI, SE); +} + +TEST(LoopPropertiesAnalysisTest, BasicTest) { + const char *ModuleStr = R"IR( +define i32 @foo() { +entry: + br label %for.body + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret i32 0 + +for.body: ; preds = %entry, %for.cond.cleanup3 + %i.016 = phi i32 [ 1, %entry ], [ %inc8, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup3: ; preds = %for.inc + %inc8 = add nuw nsw i32 %i.016, 1 + %exitcond17.not = icmp eq i32 %inc8, 4 + br i1 %exitcond17.not, label %for.cond.cleanup, label %for.body + +for.body4: ; preds = %for.body, %for.inc + %j.015 = phi i32 [ 1, %for.body ], [ %inc, %for.inc ] + %rem = and i32 %j.015, 1 + %cmp5.not = icmp eq i32 %rem, 0 + br i1 %cmp5.not, label %if.end, label %for.inc + +if.end: ; preds = %for.body4 + br label %for.inc + +for.inc: ; preds = %for.body4, %if.end + %inc = add nuw nsw i32 %j.015, 1 + %exitcond.not = icmp eq i32 %inc, 8 + br i1 %exitcond.not, label %for.cond.cleanup3, label %for.body4 +} +)IR"; + + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runWithLoopInfo( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + for (BasicBlock &BB : F) { + if (BB.getName() == "for.body") { + Loop *L = LI.getLoopFor(&BB); + LoopPropertiesInfo LPI = + LoopPropertiesInfo::getLoopPropertiesInfo(L, &LI, &SE); + EXPECT_FALSE(LPI.IsInnerMostLoop); + EXPECT_EQ(LPI.LoopDepth, 1); + EXPECT_TRUE(LPI.HasLoopPreheader); + EXPECT_EQ(LPI.PreheaderBlocksize, 1); + EXPECT_TRUE(LPI.IsCountableLoop); + EXPECT_TRUE(LPI.IsLoopBackEdgeConstant); + EXPECT_EQ(LPI.LoopBackEdgeCount, 2); + EXPECT_EQ(LPI.BasicBlockCount, 2); + EXPECT_EQ(LPI.LoopBlocksizes.count(2), 1); + EXPECT_EQ(LPI.LoopBlocksizes[2], 1); + EXPECT_EQ(LPI.LoopBlocksizes.count(3), 1); + EXPECT_EQ(LPI.LoopBlocksizes[3], 1); + EXPECT_EQ(LPI.LoopLatchCount, 1); + EXPECT_EQ(LPI.LoadInstCount, 0); + EXPECT_EQ(LPI.StoreInstCount, 0); + EXPECT_EQ(LPI.BinaryInstCount, 1); + EXPECT_EQ(LPI.LogicalInstCount, 0); + EXPECT_EQ(LPI.CastInstCount, 0); + } + if (BB.getName() == "for.body4") { + Loop *L = LI.getLoopFor(&BB); + LoopPropertiesInfo LPI = + LoopPropertiesInfo::getLoopPropertiesInfo(L, &LI, &SE); + EXPECT_TRUE(LPI.IsInnerMostLoop); + EXPECT_EQ(LPI.LoopDepth, 2); + EXPECT_TRUE(LPI.HasLoopPreheader); + EXPECT_EQ(LPI.PreheaderBlocksize, 2); + EXPECT_TRUE(LPI.IsCountableLoop); + EXPECT_TRUE(LPI.IsLoopBackEdgeConstant); + EXPECT_EQ(LPI.LoopBackEdgeCount, 6); + EXPECT_EQ(LPI.BasicBlockCount, 3); + EXPECT_EQ(LPI.LoopBlocksizes.count(1), 1); + EXPECT_EQ(LPI.LoopBlocksizes[1], 1); + EXPECT_EQ(LPI.LoopBlocksizes.count(3), 1); + EXPECT_EQ(LPI.LoopBlocksizes[3], 1); + EXPECT_EQ(LPI.LoopBlocksizes.count(4), 1); + EXPECT_EQ(LPI.LoopBlocksizes[4], 1); + EXPECT_EQ(LPI.LoopLatchCount, 1); + EXPECT_EQ(LPI.LoadInstCount, 0); + EXPECT_EQ(LPI.StoreInstCount, 0); + EXPECT_EQ(LPI.BinaryInstCount, 1); + EXPECT_EQ(LPI.LogicalInstCount, 1); + EXPECT_EQ(LPI.CastInstCount, 0); + } + } + }); +} + +} // end anonymous namespace