[coroutines] Part 3 of N: Adding Boilerplate for Coroutine Passes

[GorNishanov]

Summary

This is the third patch in the coroutine series. It adds boilerplate code for all coroutine passes that do absolutely nothing and adds a small test to verify that passes execute in expected order or not at all if not enabled.

Documentation and overview is here: http://llvm.org/docs/Coroutines.html.

Upstreaming sequence (rough plan)
1.Add documentation. (https://reviews.llvm.org/D22603)
2.Add coroutine intrinsics. (https://reviews.llvm.org/D22659)
3.Add empty coroutine passes. <= we are here
4.Add coroutine devirtualization + tests.
5.Add CGSCC restart trigger + tests.
6.Add coroutine heap elision + tests.
7.Add the rest of the logic (split into more patches)

[chandlerc]

(tiny comment below just about factoring of patches)

include/llvm/Transforms/IPO/PassManagerBuilder.h

103–107

FWIW, I think this is independent of the coroutines stuff, and I'd suggest splitting it out and sending it separately.

(And FWIW, I'm very much in favor of the general idea.)

[GorNishanov]

"Adding EP_CGSCCOptimizerLate extension point" extracted into its own patch: https://reviews.llvm.org/D22897

[majnemer]

LGTM

docs/Coroutines.rst

 CoroCleanup
 -----------
 This pass runs late to lower all coroutine related intrinsics not replaced by
 earlier passes.
 
 Upstreaming sequence (rough plan)
 =================================
 #. Add documentation.
-#. Add coroutine intrinsics.  <= we are here
-#. Add empty coroutine passes.
+#. Add coroutine intrinsics.
+#. Add empty coroutine passes.  <= we are here
 #. Add coroutine devirtualization + tests.
 #. Add CGSCC restart trigger + tests.
 #. Add coroutine heap elision + tests.
 #. Add custom allocation heap elision + tests.
 #. Add coroutine splitting logic + tests.
 #. Add simple coroutine frame builder + tests.
 #. Add the rest of the logic + tests. (Maybe split further as needed).
 

include/llvm/InitializePasses.h

 void initializeIPO(PassRegistry&);
 
 /// Initialize all passes linked into the Instrumentation library.
 void initializeInstrumentation(PassRegistry&);
 
 /// Initialize all passes linked into the Analysis library.
 void initializeAnalysis(PassRegistry&);
 
+/// Initialize all passes linked into the Coroutines library.
+void initializeCoroutines(PassRegistry&);
+
 /// Initialize all passes linked into the CodeGen library.
 void initializeCodeGen(PassRegistry&);
 
 /// Initialize all passes linked into the GlobalISel library.
 void initializeGlobalISel(PassRegistry &Registry);
 
 /// Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);

include/llvm/Transforms/Coroutines.h

+//===-- Coroutines.h - Coroutine Transformations ----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Declare accessor functions for coroutine lowering passes.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_COROUTINES_H
+#define LLVM_TRANSFORMS_COROUTINES_H
+
+namespace llvm {
+
+class Pass;
+class PassManagerBuilder;
+
+/// Add all coroutine passes to appropriate extension points.
+void addCoroutinePassesToExtensionPoints(PassManagerBuilder &Builder);
+
+/// Lower coroutine intrinsics that are not needed by later passes.
+Pass *createCoroEarlyPass();
+
+/// Split up coroutines into multiple functions driving their state machines.
+Pass *createCoroSplitPass();
+
+/// Analyze coroutines use sites, devirtualize resume/destroy calls and elide
+/// heap allocation for coroutine frame where possible.
+Pass *createCoroElidePass();
+
+/// Lower all remaining coroutine intrinsics.
+Pass *createCoroCleanupPass();
+
+}
+
+#endif

include/llvm/Transforms/IPO/PassManagerBuilder.h

enum ExtensionPointTy {
     /// should not be disabled by O0 optimization level. The passes will be
     /// inserted after the inlining pass.
     EP_EnabledOnOptLevel0,
 
     /// EP_Peephole - This extension point allows adding passes that perform
     /// peephole optimizations similar to the instruction combiner. These passes
     /// will be inserted after each instance of the instruction combiner pass.
     EP_Peephole,
+
+    /// EP_CGSCCOptimizerLate - This extension point allows adding CallGraphSCC
+    /// passes at the end of the main CallGraphSCC passes and before any
+    /// function simplification passes run by CGPassManager.
+    EP_CGSCCOptimizerLate,
   };
 
   /// The Optimization Level - Specify the basic optimization level.
   ///    0 = -O0, 1 = -O1, 2 = -O2, 3 = -O3
   unsigned OptLevel;
 
   /// SizeLevel - How much we're optimizing for size.
   ///    0 = none, 1 = -Os, 2 = -Oz

lib/Transforms/CMakeLists.txt

 add_subdirectory(Utils)
 add_subdirectory(Instrumentation)
 add_subdirectory(InstCombine)
 add_subdirectory(Scalar)
 add_subdirectory(IPO)
 add_subdirectory(Vectorize)
 add_subdirectory(Hello)
 add_subdirectory(ObjCARC)
+add_subdirectory(Coroutines)

lib/Transforms/Coroutines/CMakeLists.txt

+add_llvm_library(LLVMCoroutines
+  Coroutines.cpp
+  CoroCleanup.cpp
+  CoroEarly.cpp
+  CoroElide.cpp
+  CoroSplit.cpp
+  )
+

lib/Transforms/Coroutines/CoroCleanup.cpp

+//===- CoroCleanup.cpp - Coroutine Cleanup Pass ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This pass lowers all remaining coroutine intrinsics.
+//===----------------------------------------------------------------------===//
+
+#include "CoroInternal.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "coro-cleanup"
+
+//===----------------------------------------------------------------------===//
+//                              Top Level Driver
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+struct CoroCleanup : FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+
+  CoroCleanup() : FunctionPass(ID) {}
+
+  bool runOnFunction(Function &F) override { return false; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
+}
+
+char CoroCleanup::ID = 0;
+INITIALIZE_PASS(CoroCleanup, "coro-cleanup",
+                "Lower all coroutine related intrinsics", false, false)
+
+Pass *llvm::createCoroCleanupPass() { return new CoroCleanup(); }

lib/Transforms/Coroutines/CoroEarly.cpp

+//===- CoroEarly.cpp - Coroutine Early Function Pass ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This pass lowers coroutine intrinsics that hide the details of the exact
+// calling convention for coroutine resume and destroy functions and details of
+// the structure of the coroutine frame.
+//===----------------------------------------------------------------------===//
+
+#include "CoroInternal.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "coro-early"
+
+//===----------------------------------------------------------------------===//
+//                              Top Level Driver
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+struct CoroEarly : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  CoroEarly() : FunctionPass(ID) {}
+
+  bool runOnFunction(Function &F) override { return false; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
+}
+
+char CoroEarly::ID = 0;
+INITIALIZE_PASS(CoroEarly, "coro-early", "Lower early coroutine intrinsics",
+                false, false)
+
+Pass *llvm::createCoroEarlyPass() { return new CoroEarly(); }

lib/Transforms/Coroutines/CoroElide.cpp

+//===- CoroElide.cpp - Coroutine Frame Allocation Elision Pass ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This pass replaces dynamic allocation of coroutine frame with alloca and
+// replaces calls to llvm.coro.resume and llvm.coro.destroy with direct calls
+// to coroutine sub-functions.
+//===----------------------------------------------------------------------===//
+
+#include "CoroInternal.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "coro-elide"
+
+//===----------------------------------------------------------------------===//
+//                              Top Level Driver
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+struct CoroElide : FunctionPass {
+  static char ID;
+  CoroElide() : FunctionPass(ID) {}
+  bool runOnFunction(Function &F) override { return false; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
+}
+
+char CoroElide::ID = 0;
+INITIALIZE_PASS_BEGIN(
+    CoroElide, "coro-elide",
+    "Coroutine frame allocation elision and indirect calls replacement", false,
+    false)
+INITIALIZE_PASS_END(
+    CoroElide, "coro-elide",
+    "Coroutine frame allocation elision and indirect calls replacement", false,
+    false)
+
+Pass *llvm::createCoroElidePass() { return new CoroElide(); }

lib/Transforms/Coroutines/CoroInternal.h

+//===- CoroInternal.h - Internal Coroutine interfaces ---------*- C++ -*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Common definitions/declarations used internally by coroutine lowering passes.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TRANSFORMS_COROUTINES_COROINTERNAL_H
+#define LLVM_LIB_TRANSFORMS_COROUTINES_COROINTERNAL_H
+
+#include "llvm/Transforms/Coroutines.h"
+
+namespace llvm {
+
+class PassRegistry;
+
+void initializeCoroEarlyPass(PassRegistry &);
+void initializeCoroSplitPass(PassRegistry &);
+void initializeCoroElidePass(PassRegistry &);
+void initializeCoroCleanupPass(PassRegistry &);
+
+}
+
+#endif

lib/Transforms/Coroutines/CoroSplit.cpp

+//===- CoroSplit.cpp - Converts a coroutine into a state machine ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This pass builds the coroutine frame and outlines resume and destroy parts
+// of the coroutine into separate functions.
+//===----------------------------------------------------------------------===//
+
+#include "CoroInternal.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "coro-split"
+
+//===----------------------------------------------------------------------===//
+//                              Top Level Driver
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+struct CoroSplit : public CallGraphSCCPass {
+  static char ID; // Pass identification, replacement for typeid
+  CoroSplit() : CallGraphSCCPass(ID) {}
+
+  bool runOnSCC(CallGraphSCC &SCC) override { return false; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+    CallGraphSCCPass::getAnalysisUsage(AU);
+  }
+};
+
+}
+
+char CoroSplit::ID = 0;
+INITIALIZE_PASS(
+    CoroSplit, "coro-split",
+    "Split coroutine into a set of functions driving its state machine", false,
+    false)
+
+Pass *llvm::createCoroSplitPass() { return new CoroSplit(); }

lib/Transforms/Coroutines/Coroutines.cpp

+//===-- Coroutines.cpp ----------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file implements the common infrastructure for Coroutine Passes.
+//===----------------------------------------------------------------------===//
+
+#include "CoroInternal.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+
+using namespace llvm;
+
+void llvm::initializeCoroutines(PassRegistry &Registry) {
+  initializeCoroEarlyPass(Registry);
+  initializeCoroSplitPass(Registry);
+  initializeCoroElidePass(Registry);
+  initializeCoroCleanupPass(Registry);
+}
+
+static void addCoroutineOpt0Passes(const PassManagerBuilder &Builder,
+                                   legacy::PassManagerBase &PM) {
+  PM.add(createCoroSplitPass());
+  PM.add(createCoroElidePass());
+
+  PM.add(createBarrierNoopPass());
+  PM.add(createCoroCleanupPass());
+}
+
+static void addCoroutineEarlyPasses(const PassManagerBuilder &Builder,
+                                    legacy::PassManagerBase &PM) {
+  PM.add(createCoroEarlyPass());
+}
+
+static void addCoroutineScalarOptimizerPasses(const PassManagerBuilder &Builder,
+                                              legacy::PassManagerBase &PM) {
+  PM.add(createCoroElidePass());
+}
+
+static void addCoroutineSCCPasses(const PassManagerBuilder &Builder,
+                                  legacy::PassManagerBase &PM) {
+  PM.add(createCoroSplitPass());
+}
+
+static void addCoroutineOptimizerLastPasses(const PassManagerBuilder &Builder,
+                                            legacy::PassManagerBase &PM) {
+  PM.add(createCoroCleanupPass());
+}
+
+void llvm::addCoroutinePassesToExtensionPoints(PassManagerBuilder &Builder) {
+  Builder.addExtension(PassManagerBuilder::EP_EarlyAsPossible,
+                       addCoroutineEarlyPasses);
+  Builder.addExtension(PassManagerBuilder::EP_EnabledOnOptLevel0,
+                       addCoroutineOpt0Passes);
+  Builder.addExtension(PassManagerBuilder::EP_CGSCCOptimizerLate,
+                       addCoroutineSCCPasses);
+  Builder.addExtension(PassManagerBuilder::EP_ScalarOptimizerLate,
+                       addCoroutineScalarOptimizerPasses);
+  Builder.addExtension(PassManagerBuilder::EP_OptimizerLast,
+                       addCoroutineOptimizerLastPasses);
+}

lib/Transforms/Coroutines/LLVMBuild.txt

+;===- ./lib/Transforms/Coroutines/LLVMBuild.txt ----------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = Coroutines
+parent = Transforms
+required_libraries = Analysis Core IPO Scalar Support TransformUtils

lib/Transforms/IPO/PassManagerBuilder.cpp

if (Inliner) {
     MPM.add(Inliner);
     Inliner = nullptr;
   }
   if (!DisableUnitAtATime)
     MPM.add(createPostOrderFunctionAttrsLegacyPass());
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
 
+  addExtensionsToPM(EP_CGSCCOptimizerLate, MPM);
   addFunctionSimplificationPasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
   // pass manager that we are specifically trying to avoid. To prevent this
   // we must insert a no-op module pass to reset the pass manager.
   MPM.add(createBarrierNoopPass());
 
   if (!DisableUnitAtATime && OptLevel > 1 && !PrepareForLTO &&

lib/Transforms/LLVMBuild.txt

 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [common]
-subdirectories = IPO InstCombine Instrumentation Scalar Utils Vectorize ObjCARC
+subdirectories = Coroutines IPO InstCombine Instrumentation Scalar Utils Vectorize ObjCARC
 
 [component_0]
 type = Group
 name = Transforms
 parent = Libraries

test/Transforms/Coroutines/smoketest.ll

+; Test that all coroutine passes run in the correct order at all optimization
+; levels and -disable-coroutines removes coroutine passes from the pipeline.
+;
+; RUN: opt < %s -disable-output -enable-coroutines -debug-pass=Arguments -O1 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -enable-coroutines -debug-pass=Arguments -O2 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -enable-coroutines -debug-pass=Arguments -O3 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -enable-coroutines -debug-pass=Arguments \
+; RUN:     -coro-early -coro-split -coro-elide -coro-cleanup 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -debug-pass=Arguments 2>&1 \
+; RUN:     | FileCheck %s -check-prefix=NOCORO
+
+; CHECK: coro-early
+; CHECK: coro-split
+; CHECK: coro-elide
+; CHECK: coro-cleanup
+
+; NOCORO-NOT: coro-early
+; NOCORO-NOT: coro-split
+; NOCORO-NOT: coro-elide
+; NOCORO-NOT: coro-cleanup
+
+define void @foo() {
+  ret void
+}

tools/opt/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   Analysis
   BitWriter
   CodeGen
   Core
+  Coroutines
   IPO
   IRReader
   InstCombine
   Instrumentation
   MC
   ObjCARCOpts
   ScalarOpts
   Support

tools/opt/opt.cpp

 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/SystemUtils.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Coroutines.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include <algorithm>
 #include <memory>
 using namespace llvm;
 using namespace opt_tool;
 
 // The OptimizationList is automatically populated with registered Passes by the
RunTwice("run-twice",
              cl::desc("Run all passes twice, re-using the same pass manager."),
              cl::init(false), cl::Hidden);
 
 static cl::opt<bool> DiscardValueNames(
     "discard-value-names",
     cl::desc("Discard names from Value (other than GlobalValue)."),
     cl::init(false), cl::Hidden);
 
+static cl::opt<bool> Coroutines(
+  "enable-coroutines",
+  cl::desc("Enable coroutine passes."),
+  cl::init(false), cl::Hidden);
+
 static cl::opt<bool> PassRemarksWithHotness(
     "pass-remarks-with-hotness",
     cl::desc("With PGO, include profile count in optimization remarks"),
     cl::Hidden);
 
 static inline void addPass(legacy::PassManagerBase &PM, Pass *P) {
   // Add the pass to the pass manager...
   PM.add(P);
static void AddOptimizationPasses(legacy::PassManagerBase &MPM,
   // Add target-specific passes that need to run as early as possible.
   if (TM)
     Builder.addExtension(
         PassManagerBuilder::EP_EarlyAsPossible,
         [&](const PassManagerBuilder &, legacy::PassManagerBase &PM) {
           TM->addEarlyAsPossiblePasses(PM);
         });
 
+  if (Coroutines)
+    addCoroutinePassesToExtensionPoints(Builder);
+
   Builder.populateFunctionPassManager(FPM);
   Builder.populateModulePassManager(MPM);
 }
 
 static void AddStandardLinkPasses(legacy::PassManagerBase &PM) {
   PassManagerBuilder Builder;
   Builder.VerifyInput = true;
   if (DisableOptimizations)
int main(int argc, char **argv) {
 
   InitializeAllTargets();
   InitializeAllTargetMCs();
   InitializeAllAsmPrinters();
 
   // Initialize passes
   PassRegistry &Registry = *PassRegistry::getPassRegistry();
   initializeCore(Registry);
+  initializeCoroutines(Registry);
   initializeScalarOpts(Registry);
   initializeObjCARCOpts(Registry);
   initializeVectorization(Registry);
   initializeIPO(Registry);
   initializeAnalysis(Registry);
   initializeTransformUtils(Registry);
   initializeInstCombine(Registry);
   initializeInstrumentation(Registry);