[MLGO] Add LoopPropertiesAnalysis pass

[eopXD]

Summary

This pass mimics FunctionPropertiesAnalysis.

The analysis will be used to extract features from loop. The follow-up
patches will be extending MLGO onto helping the loop partial unroll
decision, using this pass to extract features of a loop.

[eopXD]

This comment was removed by eopXD.

[eopXD]

Rebase upon latest main.

[jdoerfert]

Generally looks good. Two minor comments.

llvm/include/llvm/Analysis/LoopPropertiesAnalysis.h

51

This bool and the one above are not strictly needed, one can just check the size and APInt for their value.

llvm/lib/Analysis/LoopPropertiesAnalysis.cpp

72

It is probably better to do the checks via isa<CastInst> and similar. New stuff is added and this seems hard to maintain.

llvm/include/llvm/Analysis/LoopPropertiesAnalysis.h

+//=- 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 <map>
+
+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<unsigned, unsigned> 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<LoopPropertiesAnalysis> {
+  friend AnalysisInfoMixin<LoopPropertiesAnalysis>;
+  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<LoopPropertiesPrinterPass> {
+  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

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   LazyValueInfo.cpp
   LegacyDivergenceAnalysis.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp
   LoopAnalysisManager.cpp
   LoopCacheAnalysis.cpp
   LoopNestAnalysis.cpp
+  LoopPropertiesAnalysis.cpp
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MLInlineAdvisor.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp

llvm/lib/Analysis/LoopPropertiesAnalysis.cpp

+//===- 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<SCEVConstant>(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<LoopPropertiesAnalysis>(L, AR).print(OS);
+  // AM.getResult<IVUsersAnalysis>(L, AR).print(OS);
+  // AM.getResult<LoopAccessAnalysis>(*L, LAR);
+  return PreservedAnalyses::all();
+}

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/InstCount.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/Lint.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #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"
 #include "llvm/Analysis/ModuleDebugInfoPrinter.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"

llvm/lib/Passes/PassRegistry.def

 
 #ifndef LOOP_ANALYSIS
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)
 #endif
 LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis())
 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
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass())
 LOOP_PASS("dot-ddg", DDGDotPrinterPass())
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("loop-rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("loop-simplifycfg", LoopSimplifyCFGPass())
 LOOP_PASS("loop-reduce", LoopStrengthReducePass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
 LOOP_PASS("loop-unroll-full", LoopFullUnrollPass())
 LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<iv-users>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loopnest>", LoopNestPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
+LOOP_PASS("print<loop-properties>", LoopPropertiesPrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())
 LOOP_PASS("loop-bound-split", LoopBoundSplitPass())
 LOOP_PASS("loop-reroll", LoopRerollPass())
 LOOP_PASS("loop-versioning-licm", LoopVersioningLICMPass())
 #undef LOOP_PASS
 
 #ifndef LOOP_PASS_WITH_PARAMS

llvm/unittests/Analysis/CMakeLists.txt

set(ANALYSIS_TEST_SOURCES
   FunctionPropertiesAnalysisTest.cpp
   InlineCostTest.cpp
   IRSimilarityIdentifierTest.cpp
   IVDescriptorsTest.cpp
   LazyCallGraphTest.cpp
   LoadsTest.cpp
   LoopInfoTest.cpp
   LoopNestTest.cpp
+  LoopPropertiesAnalysisTest.cpp
   MemoryBuiltinsTest.cpp
   MemoryProfileInfoTest.cpp
   MemorySSATest.cpp
   MLModelRunnerTest.cpp
   PhiValuesTest.cpp
   PluginInlineAdvisorAnalysisTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp

llvm/unittests/Analysis/LoopPropertiesAnalysisTest.cpp

+//===- 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<Module> 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<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> 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<Module> 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