[CGSCC] Add pass which counts the max number of times we visit a function

[aeubanks]

Summary

This will help with finding potential pathological CGSCC cases.

[lenary]

llvm/test/Other/count-visits.ll

7

We're seeing test failures for this on non-asserts builds, which correspond to the message in llvm/lib/Support/Statistic.cpp:250 about needing asserts to be enabled for statistics to work.

[aeubanks]

llvm/test/Other/count-visits.ll

7

sorry, should be fixed in 022d0c6e300300d64a505e2998f066ef81a22784

llvm/include/llvm/Transforms/Utils/CountVisits.h

+//===- CountVisits.h --------------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_COUNT_VISITS_H
+#define LLVM_TRANSFORMS_UTILS_COUNT_VISITS_H
+
+#include "llvm/ADT/StringMap.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class Function;
+
+struct CountVisitsPass : PassInfoMixin<CountVisitsPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+
+private:
+  StringMap<uint32_t> Counts;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_COUNT_VISITS_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/TLSVariableHoist.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
+#include "llvm/Transforms/Utils/CountVisits.h"
 #include "llvm/Transforms/Utils/Debugify.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/FixIrreducible.h"
 #include "llvm/Transforms/Utils/HelloWorld.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
 #include "llvm/Transforms/Utils/InstructionNamer.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"

llvm/lib/Passes/PassBuilderPipelines.cpp

 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
+#include "llvm/Transforms/Utils/CountVisits.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
 #include "llvm/Transforms/Utils/RelLookupTableConverter.h"
 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "llvm/Transforms/Vectorize/SLPVectorizer.h"

 static cl::opt<bool> EnableOrderFileInstrumentation(
     "enable-order-file-instrumentation", cl::init(false), cl::Hidden,
     cl::desc("Enable order file instrumentation (default = off)"));
 
 static cl::opt<bool>
     EnableMatrix("enable-matrix", cl::init(false), cl::Hidden,
                  cl::desc("Enable lowering of the matrix intrinsics"));
 
+static cl::opt<bool> CountCGSCCVisits(
+    "count-cgscc-max-visits", cl::init(false), cl::Hidden,
+    cl::desc("Keep track of the max number of times we visit a function in the "
+             "CGSCC pipeline as a statistic"));
+
 static cl::opt<bool> EnableConstraintElimination(
     "enable-constraint-elimination", cl::init(false), cl::Hidden,
     cl::desc(
         "Enable pass to eliminate conditions based on linear constraints"));
 
 static cl::opt<AttributorRunOption> AttributorRun(
     "attributor-enable", cl::Hidden, cl::init(AttributorRunOption::NONE),
     cl::desc("Enable the attributor inter-procedural deduction pass"),

 
 // TODO: Investigate the cost/benefit of tail call elimination on debugging.
 FunctionPassManager
 PassBuilder::buildO1FunctionSimplificationPipeline(OptimizationLevel Level,
                                                    ThinOrFullLTOPhase Phase) {
 
   FunctionPassManager FPM;
 
+  if (CountCGSCCVisits)
+    FPM.addPass(CountVisitsPass());
+
   // Form SSA out of local memory accesses after breaking apart aggregates into
   // scalars.
   FPM.addPass(SROAPass(SROAOptions::ModifyCFG));
 
   // Catch trivial redundancies
   FPM.addPass(EarlyCSEPass(true /* Enable mem-ssa. */));
 
   // Hoisting of scalars and load expressions.
PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
 
   // The O1 pipeline has a separate pipeline creation function to simplify
   // construction readability.
   if (Level.getSpeedupLevel() == 1)
     return buildO1FunctionSimplificationPipeline(Level, Phase);
 
   FunctionPassManager FPM;
 
+  if (CountCGSCCVisits)
+    FPM.addPass(CountVisitsPass());
+
   // Form SSA out of local memory accesses after breaking apart aggregates into
   // scalars.
   FPM.addPass(SROAPass(SROAOptions::ModifyCFG));
 
   // Catch trivial redundancies
   FPM.addPass(EarlyCSEPass(true /* Enable mem-ssa. */));
   if (EnableKnowledgeRetention)
     FPM.addPass(AssumeSimplifyPass());

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("assume-simplify", AssumeSimplifyPass())
 FUNCTION_PASS("alignment-from-assumptions", AlignmentFromAssumptionsPass())
 FUNCTION_PASS("annotation-remarks", AnnotationRemarksPass())
 FUNCTION_PASS("bdce", BDCEPass())
 FUNCTION_PASS("bounds-checking", BoundsCheckingPass())
 FUNCTION_PASS("break-crit-edges", BreakCriticalEdgesPass())
 FUNCTION_PASS("callsite-splitting", CallSiteSplittingPass())
 FUNCTION_PASS("consthoist", ConstantHoistingPass())
+FUNCTION_PASS("count-visits", CountVisitsPass())
 FUNCTION_PASS("constraint-elimination", ConstraintEliminationPass())
 FUNCTION_PASS("chr", ControlHeightReductionPass())
 FUNCTION_PASS("coro-elide", CoroElidePass())
 FUNCTION_PASS("correlated-propagation", CorrelatedValuePropagationPass())
 FUNCTION_PASS("dce", DCEPass())
 FUNCTION_PASS("dfa-jump-threading", DFAJumpThreadingPass())
 FUNCTION_PASS("div-rem-pairs", DivRemPairsPass())
 FUNCTION_PASS("dse", DSEPass())

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_component_library(LLVMTransformUtils
   CanonicalizeAliases.cpp
   CanonicalizeFreezeInLoops.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
   CodeLayout.cpp
   CodeMoverUtils.cpp
   CtorUtils.cpp
+  CountVisits.cpp
   Debugify.cpp
   DemoteRegToStack.cpp
   EntryExitInstrumenter.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp
   FixIrreducible.cpp
   FlattenCFG.cpp
   FunctionComparator.cpp

llvm/lib/Transforms/Utils/CountVisits.cpp

+//===- CountVisits.cpp ----------------------------------------------------===//
+//
+// 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/Transforms/Utils/CountVisits.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/IR/PassManager.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "count-visits"
+
+STATISTIC(MaxVisited, "Max number of times we visited a function");
+
+PreservedAnalyses CountVisitsPass::run(Function &F, FunctionAnalysisManager &) {
+  uint32_t Count = Counts[F.getName()] + 1;
+  Counts[F.getName()] = Count;
+  if (Count > MaxVisited)
+    MaxVisited = Count;
+  return PreservedAnalyses::all();
+}

llvm/test/Other/count-visits.ll

+; RUN: opt -passes=count-visits -stats 2>&1 -disable-output < %s | FileCheck %s --check-prefix=ONE
+; RUN: opt -passes='cgscc(count-visits)' -stats 2>&1 -disable-output < %s | FileCheck %s --check-prefix=ONE
+; RUN: opt -passes='cgscc(count-visits,instcombine)' -stats 2>&1 -disable-output < %s | FileCheck %s --check-prefix=TWO
+; RUN: opt -passes='default<O1>' -count-cgscc-max-visits -stats 2>&1 -disable-output < %s | FileCheck %s --check-prefix=PIPELINE
+; RUN: opt -passes='default<O3>' -count-cgscc-max-visits -stats 2>&1 -disable-output < %s | FileCheck %s --check-prefix=PIPELINE
+
+; ONE: 1 count-visits - Max number of times we visited a function
+; TWO: 2 count-visits - Max number of times we visited a function
+; PIPELINE: count-visits - Max number of times we visited a function
+
+define void @f() {
+  %a = bitcast ptr @g to ptr
+  call void %a()
+  ret void
+}
+
+define void @g() {
+  call void @f()
+  ret void
+}

llvm/utils/gn/secondary/llvm/lib/Transforms/Utils/BUILD.gn

 static_library("Utils") {
   output_name = "LLVMTransformUtils"
   deps = [
     "//llvm/lib/Analysis",
     "//llvm/lib/IR",
     "//llvm/lib/Support",
     "//llvm/lib/TargetParser",
   ]
   sources = [
     "AMDGPUEmitPrintf.cpp",
     "ASanStackFrameLayout.cpp",
     "AddDiscriminators.cpp",
     "AssumeBundleBuilder.cpp",
+    "CountVisits.cpp",
     "BasicBlockUtils.cpp",
     "BreakCriticalEdges.cpp",
     "BuildLibCalls.cpp",
     "BypassSlowDivision.cpp",
     "CallGraphUpdater.cpp",
     "CallPromotionUtils.cpp",
     "CanonicalizeAliases.cpp",
     "CanonicalizeFreezeInLoops.cpp",