[coroutines] Part 4a: Coroutine Devirtualization: Lower coro.resume and coro.destroy.

[GorNishanov]

Summary

This is the forth patch in the coroutine series. CoroEaly pass now lowers coro.resume
and coro.destroy intrinsics by replacing them with an indirect call to an address
returned by coro.subfn.addr intrinsic. This is done so that CGPassManager recognizes
devirtualization when CoroElide replaces a call to coro.subfn.addr with an appropriate
function address.

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. (https://reviews.llvm.org/D22847)
4.Add coroutine devirtualization + tests.

ab) Lower coro.resume and coro.destroy <= we are here
c) Do devirtualization

5.Add CGSCC restart trigger + tests.
6.Add coroutine heap elision + tests.
7.Add the rest of the logic (split into more patches)

[majnemer]

lib/Transforms/Coroutines/CoroEarly.cpp

28–31

Please clang-format this, pointers and refs lean right.

41–42

This doesn't look clang-format'd.

44

Why do we change the calling convention?

47

clang-format this, pointers and refs lean right.

48

Variables start with caps.

51

I'd suggest auto * to make it clear we are copying around a pointer.

70

Please clang-format this.

71

Could you use the llvm_coro_{destroy,resume} intrinsic IDs instead?

72

LLVM has a make_unique implementation.

74

Please clang-format this.

91

The reference should lean right.

lib/Transforms/Coroutines/CoroInstr.h

2

The file path doesn't match the file, I'd just make it "CoroInstr.h"

37

We don't use this naming style for enums, see here

48

I'd make this auto just int64_t.

54

clang-format this.

lib/Transforms/Coroutines/CoroInternal.h

23–24

Please sort these.

34–36

Pointers lean right.

lib/Transforms/Coroutines/Coroutines.cpp

70–74

Please clang-format this.

82–93

This doesn't look clang-format'd.

84

Should we assert that Index is >= 0?

84–92

We prefer auto * to make it clear we are copying around pointers.

87–88

I think you can just sink the args list right into the CallInst::Create, ArrayRef has a std::initializer_list constructor.

[mehdi_amini]

lib/Transforms/Coroutines/CoroEarly.cpp

71

Can we find if an intrinsic is declared/used in a Module using the ID?

[mehdi_amini]

lib/Transforms/Coroutines/CoroInternal.h

35

M and C aren't great variable names. Also, is C used outside of the ctor? (The name does not help for grep...)

[majnemer]

lib/Transforms/Coroutines/CoroEarly.cpp

71

Ah, maybe not...

[GorNishanov]

lib/Transforms/Coroutines/CoroEarly.cpp

44

The coro.resume / coro.destroy intrinsics hide from the frontend details of the exact calling convention of post split coroutine subfunctions. LLVM knows that the extracted parts will have fastcc calling conventions (since we will be generating them in CoroSplit and will select fastcc calling convention in later patches).

71

Yep. M.getDeclaration(ID, Types) will call getOrInsertFunction that will insert a declaration if one was not available.

I was looking for least expensive check and was following an example of:

/// \brief Test if the given module looks interesting to run ARC optimization on
inline bool ModuleHasARC(const Module &M) {
  return
    M.getNamedValue("objc_retain") ||
    M.getNamedValue("objc_release") ||

lib/Transforms/Coroutines/CoroInstr.h

37

s/kFrame/Frame
s/kIndex/Index ?

It is a private enum inside of the class, so it does not need a prefix according to the coding guidelines.

I did want to have it stand out a little to signify that it is a constant. I considered

s/kFrame/FRAME
s/kIndex/INDEX ?

but then it maybe consumed with a macro.

lib/Transforms/Coroutines/CoroInternal.h

35

I was following examples of similar classes in other components, such as in FunctionImportUtils.h, WholeProgramDevirt.cpp and many others.

But, I will be happy to change them to:

LLVMContext &Context;
Module &TheModule;

These also seem to be popular choices in the codebase.

Context is not used outside of the constructor in this patch. It will be in future patches. I can remove it for now.

[majnemer]

lib/Transforms/Coroutines/CoroInstr.h

37

I'd name it Frame and Index.

lib/Transforms/Coroutines/Coroutines.cpp

82–83

Please clang-format this.

[mehdi_amini]

lib/Transforms/Coroutines/CoroInternal.h

35

Yeah, maybe it's me, but I keep single letter variable name for an iterator or other "short-lived" ones.

If you already know for sure you're gonna need soon the Context in multiple methods of this class, I don't mind you leaving it here for now.

[GorNishanov]

Addressed review comments:

1. Wholesale clang-format
2. M/C renamed TheModule/Context
3. kIndex, kFrame renamed IndexArg, FrameArg
4. use {Frame,Index} instead of creating a SmallVector<2, Arg>
5. auto X / auto* X where appropriate
6. Continue using getNamedValue as a way to check if there is any work to do.
7. added assert in makeSubFnCall to check that index is in range
8. use llvm::make_unique
9. s/changed/Changed

[GorNishanov]

Checked all checkboxes as done.

[majnemer]

LGTM

[GorNishanov]

Folded part4b (handling EH for coro.resume / coro.destroy) into this patch.

[mehdi_amini]

lib/Transforms/Coroutines/CoroInstr.h

33

It is not great to use #define in headers, especially public ones.

[GorNishanov]

Update CallSite::getIntrinsicID(), not to use anything from Intrinsics.h

[GorNishanov]

lib/Transforms/Coroutines/CoroInstr.h

34

It is internal header used by Coroutine library. These constants are used (or will be used) by several coroutine passes in this directory.

When we drop MSVC 2013, these #define could be replaced with constexpr StringRef or something like that.

[mehdi_amini]

lib/Transforms/Coroutines/CoroInstr.h

34

Sorry I looked at the path and for some reason thought it was a public one...

Nevertheless, I wonder if other passes are even trying to "hide" the intrinsic names or just using it plain everywhere, I might more readable to read M.getNamedValue("llvm.coro.destroy") instead of M.getNamedValue(CORO_DESTROY_STR)

[GorNishanov]

Switch to using

declaresIntrinsics(M, {"llvm.coro.resume", "llvm.coro.destroy"})

helper function that validates that there is a named value in the module and that the name is one of the coroutine intrinsics (in debug mode).

[GorNishanov]

remove CORO_DESTROY_STR and CORO_RESUME_STR macros, as now we can use declaresIntrinsics helper function.

[GorNishanov]

lib/Transforms/Coroutines/CoroInstr.h

35

How about now? I got rid of the macros and use plain strings in a call to declaresIntrinsic helper function.

To guard against mis-spelling, delaresIntrinsic in debug mode checks whether the name is a valid coroutine intrinsic name.

[GorNishanov]

add getIntrinsicName() to CoroXXXInst wrappers and use it instead of #define CORO_XXX_STR

[majnemer]

include/llvm/IR/CallSite.h

116

Pointers lean right.

lib/Transforms/Coroutines/CoroInstr.h

33

Hmm, this looks like trouble. CoroResumeInst is an IntrinsicInst but llvm.coro.resume is marked as Throws and IntrinsicInst derives from CallInst.

I think the right thing to do here is to make a helper function... Something like getIntrinsicCallSite which takes the intrinsic id (maybe as a template parameter? maybe not?) and returns an empty CallSite if there is no match or a populated CallSite if there was a match.

46

Ditto.

[GorNishanov]

Go back to declaresIntrinsic and fix "auto* F" to "auto *F" in CallSite.h

[majnemer]

LGTM w/ nits addressed.

lib/Transforms/Coroutines/Coroutines.cpp

99

Functions start with a lower case letter.

122–124

Please clang-format this.

[GorNishanov]

Nits addressed

include/llvm/IR/CallSite.h

public:
 
   /// setCalledFunction - Set the callee to the specified value.
   ///
   void setCalledFunction(Value *V) {
     assert(getInstruction() && "Not a call or invoke instruction!");
     *getCallee() = V;
   }
 
+  /// Return the intrinsic ID of the intrinsic called by this CallSite,
+  /// or Intrinsic::not_intrinsic if the called function is not an
+  /// intrinsic, or if this CallSite is an indirect call.
+  Intrinsic::ID getIntrinsicID() const {
+    if (auto *F = getCalledFunction())
+      return F->getIntrinsicID();
+    // Don't use Intrinsic::not_intrinsic, as it will require pulling
+    // Intrinsics.h into every header that uses CallSite.
+    return static_cast<Intrinsic::ID>(0);
+  }
+
   /// isCallee - Determine whether the passed iterator points to the
   /// callee operand's Use.
   bool isCallee(Value::const_user_iterator UI) const {
     return isCallee(&UI.getUse());
   }
 
   /// Determine whether this Use is the callee operand's Use.
   bool isCallee(const Use *U) const { return getCallee() == U; }

lib/IR/Verifier.cpp

if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
       // taken.
       Assert(
           !F->hasLLVMReservedName() ||
               i == (isa<CallInst>(I) ? e - 1 : isa<InvokeInst>(I) ? e - 3 : 0),
           "Cannot take the address of an intrinsic!", &I);
       Assert(
           !F->isIntrinsic() || isa<CallInst>(I) ||
               F->getIntrinsicID() == Intrinsic::donothing ||
+              F->getIntrinsicID() == Intrinsic::coro_resume ||
+              F->getIntrinsicID() == Intrinsic::coro_destroy ||
               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_void ||
               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_i64 ||
               F->getIntrinsicID() == Intrinsic::experimental_gc_statepoint,
-          "Cannot invoke an intrinsic other than donothing, patchpoint or "
-          "statepoint",
+          "Cannot invoke an intrinsic other than donothing, patchpoint, "
+          "statepoint, coro_resume or coro_destroy",
           &I);
       Assert(F->getParent() == M, "Referencing function in another module!",
              &I, M, F, F->getParent());
     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
       Assert(OpBB->getParent() == BB->getParent(),
              "Referring to a basic block in another function!", &I);
     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
       Assert(OpArg->getParent() == BB->getParent(),

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/IR/CallSite.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "coro-early"
 
+namespace {
+// Created on demand if CoroEarly pass has work to do.
+class Lowerer : public coro::LowererBase {
+  void lowerResumeOrDestroy(CallSite CS, CoroSubFnInst::ResumeKind);
+
+public:
+  Lowerer(Module &M) : LowererBase(M) {}
+  static std::unique_ptr<Lowerer> createIfNeeded(Module &M);
+  bool lowerEarlyIntrinsics(Function &F);
+};
+}
+
+// Replace a direct call to coro.resume or coro.destroy with an indirect call to
+// an address returned by coro.subfn.addr intrinsic. This is done so that
+// CGPassManager recognizes devirtualization when CoroElide pass replaces a call
+// to coro.subfn.addr with an appropriate function address.
+void Lowerer::lowerResumeOrDestroy(CallSite CS,
+                                   CoroSubFnInst::ResumeKind Index) {
+  Value *ResumeAddr =
+      makeSubFnCall(CS.getArgOperand(0), Index, CS.getInstruction());
+  CS.setCalledFunction(ResumeAddr);
+  CS.setCallingConv(CallingConv::Fast);
+}
+
+bool Lowerer::lowerEarlyIntrinsics(Function &F) {
+  bool Changed = false;
+  for (auto IB = inst_begin(F), IE = inst_end(F); IB != IE;) {
+    Instruction &I = *IB++;
+    if (auto CS = CallSite(&I)) {
+      switch (CS.getIntrinsicID()) {
+      default:
+        continue;
+      case Intrinsic::coro_resume:
+        lowerResumeOrDestroy(CS, CoroSubFnInst::ResumeIndex);
+        break;
+      case Intrinsic::coro_destroy:
+        lowerResumeOrDestroy(CS, CoroSubFnInst::DestroyIndex);
+        break;
+      }
+      Changed = true;
+      continue;
+    }
+  }
+  return Changed;
+}
+
+// This pass has work to do only if we find intrinsics we are going to lower in
+// the module.
+std::unique_ptr<Lowerer> Lowerer::createIfNeeded(Module &M) {
+  if (declaresIntrinsics(M, {"llvm.coro.resume", "llvm.coro.destroy"}))
+    return llvm::make_unique<Lowerer>(M);
+
+  return {};
+}
+
 //===----------------------------------------------------------------------===//
 //                              Top Level Driver
 //===----------------------------------------------------------------------===//
 
 namespace {
 
 struct CoroEarly : public FunctionPass {
-  static char ID; // Pass identification, replacement for typeid
+  static char ID; // Pass identification, replacement for typeid.
   CoroEarly() : FunctionPass(ID) {}
 
-  bool runOnFunction(Function &F) override { return false; }
+  std::unique_ptr<Lowerer> L;
+
+  bool doInitialization(Module &M) override {
+    L = Lowerer::createIfNeeded(M);
+    return false;
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (!L)
+      return false;
+
+    return L->lowerEarlyIntrinsics(F);
+  }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesAll();
+    AU.setPreservesCFG();
   }
 };
 
 }
 
 char CoroEarly::ID = 0;
 INITIALIZE_PASS(CoroEarly, "coro-early", "Lower early coroutine intrinsics",
                 false, false)
 
 Pass *llvm::createCoroEarlyPass() { return new CoroEarly(); }

lib/Transforms/Coroutines/CoroInstr.h

+//===-- CoroInstr.h - Coroutine Intrinsics Instruction Wrappers -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file defines classes that make it really easy to deal with intrinsic
+// functions with the isa/dyncast family of functions.  In particular, this
+// allows you to do things like:
+//
+//     if (auto *SF = dyn_cast<CoroSubFnInst>(Inst))
+//        ... SF->getFrame() ... SF->getAlloc() ...
+//
+// All intrinsic function calls are instances of the call instruction, so these
+// are all subclasses of the CallInst class.  Note that none of these classes
+// has state or virtual methods, which is an important part of this gross/neat
+// hack working.
+//
+// The helpful comment above is borrowed from llvm/IntrinsicInst.h, we keep
+// coroutine intrinsic wrappers here since they are only used by the passes in
+// the Coroutine library.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IntrinsicInst.h"
+
+namespace llvm {
+
+/// This class represents the llvm.coro.subfn.addr instruction.
+class LLVM_LIBRARY_VISIBILITY CoroSubFnInst : public IntrinsicInst {
+  enum { FrameArg, IndexArg };
+
+public:
+  enum ResumeKind {
+    ResumeIndex,
+    DestroyIndex,
+    IndexLast,
+    IndexFirst = ResumeIndex
+  };
+
+  Value *getFrame() const { return getArgOperand(FrameArg); }
+  ResumeKind getIndex() const {
+    int64_t Index = getRawIndex()->getValue().getSExtValue();
+    assert(Index >= IndexFirst && Index < IndexLast &&
+           "unexpected CoroSubFnInst index argument");
+    return static_cast<ResumeKind>(Index);
+  }
+
+  ConstantInt *getRawIndex() const {
+    return cast<ConstantInt>(getArgOperand(IndexArg));
+  }
+
+  // Methods to support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::coro_subfn_addr;
+  }
+  static inline bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+};
+
+} // End namespace llvm.

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 "CoroInstr.h"
 #include "llvm/Transforms/Coroutines.h"
 
 namespace llvm {
 
+class FunctionType;
+class LLVMContext;
+class Module;
 class PassRegistry;
 
 void initializeCoroEarlyPass(PassRegistry &);
 void initializeCoroSplitPass(PassRegistry &);
 void initializeCoroElidePass(PassRegistry &);
 void initializeCoroCleanupPass(PassRegistry &);
 
-}
+namespace coro {
+
+// Keeps data and helper functions for lowering coroutine intrinsics.
+struct LowererBase {
+  Module &TheModule;
+  LLVMContext &Context;
+  FunctionType *const ResumeFnType;
+
+  LowererBase(Module &M);
+  Value *makeSubFnCall(Value *Arg, int Index, Instruction *InsertPt);
+  static bool declaresIntrinsics(Module &M, std::initializer_list<StringRef>);
+};
+
+} // End namespace coro.
+} // End namespace llvm
 
 #endif

lib/Transforms/Coroutines/Coroutines.cpp

Builder.addExtension(PassManagerBuilder::EP_EnabledOnOptLevel0,
                        addCoroutineOpt0Passes);
   Builder.addExtension(PassManagerBuilder::EP_CGSCCOptimizerLate,
                        addCoroutineSCCPasses);
   Builder.addExtension(PassManagerBuilder::EP_ScalarOptimizerLate,
                        addCoroutineScalarOptimizerPasses);
   Builder.addExtension(PassManagerBuilder::EP_OptimizerLast,
                        addCoroutineOptimizerLastPasses);
 }
+
+// Construct the lowerer base class and initialize its members.
+coro::LowererBase::LowererBase(Module &M)
+    : TheModule(M), Context(M.getContext()),
+      ResumeFnType(FunctionType::get(Type::getVoidTy(Context),
+                                     Type::getInt8PtrTy(Context),
+                                     /*isVarArg=*/false)) {}
+
+// Creates a sequence of instructions to obtain a resume function address using
+// llvm.coro.subfn.addr. It generates the following sequence:
+//
+//    call i8* @llvm.coro.subfn.addr(i8* %Arg, i8 %index)
+//    bitcast i8* %2 to void(i8*)*
+
+Value *coro::LowererBase::makeSubFnCall(Value *Arg, int Index,
+                                        Instruction *InsertPt) {
+  auto *IndexVal = ConstantInt::get(Type::getInt8Ty(Context), Index);
+  auto *Fn = Intrinsic::getDeclaration(&TheModule, Intrinsic::coro_subfn_addr);
+
+  assert(Index >= CoroSubFnInst::IndexFirst &&
+         Index < CoroSubFnInst::IndexLast &&
+         "makeSubFnCall: Index value out of range");
+  auto *Call = CallInst::Create(Fn, {Arg, IndexVal}, "", InsertPt);
+
+  auto *Bitcast =
+      new BitCastInst(Call, ResumeFnType->getPointerTo(), "", InsertPt);
+  return Bitcast;
+}
+
+#ifndef NDEBUG
+static bool IsCoroutineIntrinsicName(StringRef Name) {
+  // NOTE: Must be sorted!
+  static const char *const CoroIntrinsics[] = {
+    "llvm.coro.alloc",
+    "llvm.coro.begin",
+    "llvm.coro.destroy",
+    "llvm.coro.done",
+    "llvm.coro.end",
+    "llvm.coro.frame",
+    "llvm.coro.free",
+    "llvm.coro.param",
+    "llvm.coro.promise",
+    "llvm.coro.resume",
+    "llvm.coro.save",
+    "llvm.coro.size",
+    "llvm.coro.suspend",
+  };
+  return Intrinsic::lookupLLVMIntrinsicByName(CoroIntrinsics, Name) != -1;
+}
+#endif
+
+// Verifies if a module has named values listed. Also, in debug mode verifies
+// that names are intrinsic names.
+bool coro::LowererBase::declaresIntrinsics(Module &M,
+  std::initializer_list<StringRef> List) {
+
+  for (StringRef Name : List) {
+    assert(IsCoroutineIntrinsicName(Name) && "not a coroutine intrinsic");
+    if (M.getNamedValue(Name))
+      return true;
+  }
+
+  return false;
+}

test/Transforms/Coroutines/coro-early.ll

+; Tests that CoroEarly pass correctly lowers coro.resume and coro.destroy
+; intrinsics.
+; RUN: opt < %s -S -coro-early | FileCheck %s
+
+; CHECK-LABEL: @callResume
+define void @callResume(i8* %hdl) {
+; CHECK-NEXT: entry
+entry:
+; CHECK-NEXT: %0 = call i8* @llvm.coro.subfn.addr(i8* %hdl, i8 0)
+; CHECK-NEXT: %1 = bitcast i8* %0 to void (i8*)*
+; CHECK-NEXT: call fastcc void %1(i8* %hdl)
+  call void @llvm.coro.resume(i8* %hdl)
+
+; CHECK-NEXT: %2 = call i8* @llvm.coro.subfn.addr(i8* %hdl, i8 1)
+; CHECK-NEXT: %3 = bitcast i8* %2 to void (i8*)*
+; CHECK-NEXT: call fastcc void %3(i8* %hdl)
+  call void @llvm.coro.destroy(i8* %hdl)
+
+  ret void
+; CHECK-NEXT: ret void
+}
+
+; CHECK-LABEL: @eh
+define void @eh(i8* %hdl) personality i8* null {
+; CHECK-NEXT: entry
+entry:
+;  CHECK-NEXT: %0 = call i8* @llvm.coro.subfn.addr(i8* %hdl, i8 0)
+;  CHECK-NEXT: %1 = bitcast i8* %0 to void (i8*)*
+;  CHECK-NEXT: invoke fastcc void %1(i8* %hdl)
+  invoke void @llvm.coro.resume(i8* %hdl)
+          to label %cont unwind label %ehcleanup
+cont:
+  ret void
+
+ehcleanup:
+  %0 = cleanuppad within none []
+  cleanupret from %0 unwind to caller
+}
+
+declare void @llvm.coro.resume(i8*)
+declare void @llvm.coro.destroy(i8*)