[llvm-dev] [RFC] Clean up the way we store optional Function data

[Vedant Kumar via llvm-dev]

Function's have three kinds of optional data: prefix data, prologue data, and
personalities. We don't have a consistent way of storing this data, IMO. This
RFC discusses a new way of managing optional data that makes llvm::Function
cleaner, more consistent, and a little smaller.


What do we do currently?
========================

Prefix and prologue data are attached to Functions via DenseMaps in
LLVMContextImpl:

    typedef DenseMap<const Function *, ReturnInst *> FunctionDataMapTy;
    FunctionDataMapTy PrefixDataMap;
    FunctionDataMapTy PrologueDataMap;

To attach prefix data to a Function, we create an orphan ReturnInst:

    RI = ReturnInst::Create(F->getContext(), PrefixData);
    PrefixDataMap[F] = RI;

Personalities are stored as ``optional`` Function operands. We actually always
allocate the space for this ``optional`` operand: there's a FIXME in the
destructor for Function about this.


What's wrong with this?
=======================

1. Functions without personalities pay the space-cost for them.

2. We handle personalities differently from prefix and prologue data.

3. Suppose N functions share the same prefix or prologue data. We create N
   different ReturnInsts to point to the same thing. I think that's wasteful.

4. These hidden ReturnInsts effectively make a Function an indirect user of
   its optional data. This relationship should be made explicit to avoid bugs.


Proposal: Introduce a new Constant, llvm::IndirectUser
======================================================

This is my take on Duncan's proposed solution to PR24755 [1].

It involves creating a new type of Constant. A sketch:

    struct llvm::IndirectUser : llvm::Constant {
        Constant *Data;     // Operand 0
        unsigned  RefCount; // Metadata (not an operand)

        /// Get or create an IndirectUser for C.
        static IndirectUser *GetOrCreateIndirectUser(Constant *C);
        
        /// Drop a reference to C's IndirectUser.
        static void ReleaseIndirectUser(Constant *C);
    };

Here's how to attach prefix data to a Function:

    IU = IndirectUser::GetOrCreateIndirectUser(PrefixData);
    PrefixDataMap[F] = IU;

Prologue data and personality functions work the same way (though we'll need to
add a PersonalityFnMap).

If two functions share prefix/prologue data, or personalities, they get the
same IndirectUser (with a bumped refcount).

This addresses all the points in the previous section.


Implementation details
======================

When an IndirectUser is constructed, it adds itself to its Constant's users
list. When the IndirectUser's refcount hits 0, we can invoke destroyConstant().
The only tricky part is handling ReplaceAllUsesWith.

There are two RAUW cases. Case 1 is easy:

    <IndirectUser 1> = { Data = A, RefCount = X }
    RAUW(A, B)

Result:

    <IndirectUser 1> = { Data = B, RefCount = X }

Case 2 is a bit more involved:

    <IndirectUser 1> = { Data = A, RefCount = X }
    <IndirectUser 2> = { Data = B, RefCount = Y }
    RAUW(A, B)

Result:

    <IndirectUser 2> = { Data = B, RefCount = X + Y }
    <IndirectUser 1> = { Data = <IndirectUser 2>, RefCount = 0 }

I've left out a sub-case where <IndirectUser 2> is already part of a daisy
chain. There are strict asserts in place to keep the daisy-chaining sane.

I have this mostly working. There's just one outstanding issue in clang. The
PersonalityHasOnlyCXXUses() routine needs to look up all the Function objects
which refer to a particular personality function.  I plan on supporting this by
defining a ``Function::getPersonalityFnUsers(Fn)`` routine.

I'm hoping to have patches out for review by Monday. I thought I'd send this
out now to get feedback on my approach -- plus, I didn't want to send stuff in
out of the blue.

Let me know what you think!

vedant

[1] https://llvm.org/bugs/show_bug.cgi?id=24755