path: root/src/jit/jitgcinfo.h

//
// Copyright (c) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
//

//  Garbage-collector information
//  Keeps track of which variables hold pointers.
//  Generates the GC-tables

#ifndef _JITGCINFO_H_
#define _JITGCINFO_H_
#include "gcinfo.h"

#ifndef JIT32_GCENCODER
#include "gcinfoencoder.h"
#include "gcinfotypes.h"
#endif

/*****************************************************************************/

#ifndef JIT32_GCENCODER
// Shash typedefs
struct RegSlotIdKey
{
    unsigned short m_regNum;
    unsigned short m_flags;

    RegSlotIdKey() {}

    RegSlotIdKey(unsigned short regNum, unsigned short flags) : m_regNum(regNum), m_flags(flags) {}

    static unsigned GetHashCode(RegSlotIdKey rsk)
    {
        return (rsk.m_flags << (8*sizeof(unsigned short))) + rsk.m_regNum;
    }

    static bool Equals(RegSlotIdKey rsk1, RegSlotIdKey rsk2)
    {
        return rsk1.m_regNum == rsk2.m_regNum && rsk1.m_flags == rsk2.m_flags;
    }
};

struct StackSlotIdKey
{
    int m_offset;
    bool  m_fpRel;
    unsigned short m_flags;

    StackSlotIdKey() {}

    StackSlotIdKey(int offset, bool fpRel, unsigned short flags) : m_offset(offset), m_fpRel(fpRel), m_flags(flags) {}

    static unsigned GetHashCode(StackSlotIdKey ssk)
    {
        return (ssk.m_flags << (8*sizeof(unsigned short))) ^ (unsigned)ssk.m_offset ^ (ssk.m_fpRel ? 0x1000000 : 0);
    }

    static bool Equals(StackSlotIdKey ssk1, StackSlotIdKey ssk2)
    {
        return ssk1.m_offset == ssk2.m_offset && ssk1.m_fpRel == ssk2.m_fpRel && ssk1.m_flags == ssk2.m_flags;
    }
};

typedef SimplerHashTable<RegSlotIdKey, RegSlotIdKey, GcSlotId, DefaultSimplerHashBehavior>     RegSlotMap;
typedef SimplerHashTable<StackSlotIdKey, StackSlotIdKey, GcSlotId, DefaultSimplerHashBehavior> StackSlotMap;
#endif

typedef SimplerHashTable<GenTreePtr, PtrKeyFuncs<GenTree>, VARSET_TP*, DefaultSimplerHashBehavior> NodeToVarsetPtrMap;

class GCInfo
{
    friend class CodeGen;

private:
    Compiler*           compiler;
    RegSet*             regSet;

public :

    GCInfo(Compiler* theCompiler);

    void                gcResetForBB        ();

    void                gcMarkRegSetGCref   (regMaskTP  regMask DEBUG_ARG(bool forceOutput = false));
    void                gcMarkRegSetByref   (regMaskTP  regMask DEBUG_ARG(bool forceOutput = false));
    void                gcMarkRegSetNpt     (regMaskTP  regMask DEBUG_ARG(bool forceOutput = false));
    void                gcMarkRegPtrVal     (regNumber  reg, var_types type);
    void                gcMarkRegPtrVal     (GenTreePtr tree);

#ifdef DEBUG    
    void                gcDspGCrefSetChanges(regMaskTP gcRegGCrefSetNew DEBUG_ARG(bool forceOutput = false));
    void                gcDspByrefSetChanges(regMaskTP gcRegByrefSetNew DEBUG_ARG(bool forceOutput = false));
#endif // DEBUG    

/*****************************************************************************/


    //-------------------------------------------------------------------------
    //
    //  The following keeps track of which registers currently hold pointer
    //  values.
    //

    regMaskTP           gcRegGCrefSetCur;   // current regs holding GCrefs
    regMaskTP           gcRegByrefSetCur;   // current regs holding Byrefs

    VARSET_TP           gcTrkStkPtrLcls;    // set of tracked stack ptr lcls (GCref and Byref) - no args
    VARSET_TP           gcVarPtrSetCur;     // currently live part of "gcTrkStkPtrLcls"

    //-------------------------------------------------------------------------
    //
    //  The following keeps track of the lifetimes of non-register variables that
    //  hold pointers.
    //

    struct varPtrDsc
    {
        varPtrDsc   *   vpdNext;

        unsigned        vpdVarNum;         // which variable is this about?

        unsigned        vpdBegOfs ;        // the offset where life starts
        unsigned        vpdEndOfs;         // the offset where life starts
    };

    varPtrDsc   *       gcVarPtrList;
    varPtrDsc   *       gcVarPtrLast;

    void                gcVarPtrSetInit();

/*****************************************************************************/

    //  'pointer value' register tracking and argument pushes/pops tracking.

    enum    rpdArgType_t    { rpdARG_POP, rpdARG_PUSH, rpdARG_KILL };

    struct  regPtrDsc
    {
        regPtrDsc  *          rpdNext;            // next entry in the list
        unsigned              rpdOffs;            // the offset of the instruction

        union                                     // 2-16 byte union (depending on architecture)
        {
            struct                                // 2-16 byte structure (depending on architecture)
            {
                regMaskSmall  rpdAdd;             // regptr bitset being added
                regMaskSmall  rpdDel;             // regptr bitset being removed
            }
                              rpdCompiler;

            unsigned short    rpdPtrArg;          // arg offset or popped arg count
        };

#ifndef JIT32_GCENCODER
        unsigned char         rpdCallInstrSize;    // Length of the call instruction.
#endif

        unsigned short        rpdArg          :1;  // is this an argument descriptor?
        unsigned short        rpdArgType      :2;  // is this an argument push,pop, or kill?
        rpdArgType_t          rpdArgTypeGet() { return (rpdArgType_t) rpdArgType; }

        unsigned short        rpdGCtype       :2;  // is this a pointer, after all?
        GCtype                rpdGCtypeGet()  { return (GCtype) rpdGCtype; }

        unsigned short        rpdIsThis       :1;  // is it the 'this' pointer
        unsigned short        rpdCall         :1;  // is this a true call site?
        unsigned short                        :1;  // Padding bit, so next two start on a byte boundary
        unsigned short        rpdCallGCrefRegs:CNT_CALLEE_SAVED; // Callee-saved registers containing GC pointers.
        unsigned short        rpdCallByrefRegs:CNT_CALLEE_SAVED; // Callee-saved registers containing byrefs.

#ifndef JIT32_GCENCODER
        bool                  rpdIsCallInstr()
        {
            return rpdCall && rpdCallInstrSize != 0;
        }
#endif
    };

    regPtrDsc  *        gcRegPtrList;
    regPtrDsc  *        gcRegPtrLast;
    unsigned            gcPtrArgCnt;

#ifndef JIT32_GCENCODER
    enum MakeRegPtrMode
    {
        MAKE_REG_PTR_MODE_ASSIGN_SLOTS,
        MAKE_REG_PTR_MODE_DO_WORK
    };

    // This method has two modes.  In the "assign slots" mode, it figures out what stack locations are
    // used to contain GC references, and whether those locations contain byrefs or pinning references,
    // building up mappings from tuples of <offset X byref/pinning> to the corresponding slot id.
    // In the "do work" mode, we use these slot ids to actually declare live ranges to the encoder.
    void                gcMakeVarPtrTable (GcInfoEncoder* gcInfoEncoder,
                                           MakeRegPtrMode mode);

    // This method expands the tracked stack variables lifetimes so that any lifetimes within filters
    // are reported as pinned.
    void                gcMarkFilterVarsPinned();


    // At instruction offset "instrOffset," the set of registers indicated by "regMask" is becoming live or dead, depending
    // on whether "newState" is "GC_SLOT_DEAD" or "GC_SLOT_LIVE".  The subset of registers whose corresponding
    // bits are set in "byRefMask" contain by-refs rather than regular GC pointers. "*pPtrRegs" is the set of
    // registers currently known to contain pointers.  If "mode" is "ASSIGN_SLOTS", computes and records slot
    // ids for the registers.  If "mode" is "DO_WORK", informs "gcInfoEncoder" about the state transition,
    // using the previously assigned slot ids, and updates "*pPtrRegs" appropriately.
    void gcInfoRecordGCRegStateChange(GcInfoEncoder* gcInfoEncoder,
                                      MakeRegPtrMode mode,
                                      unsigned instrOffset,
                                      regMaskSmall regMask, 
                                      GcSlotState newState,
                                      regMaskSmall byRefMask,
                                      regMaskSmall* pPtrRegs);

    // regPtrDsc is also used to encode writes to the outgoing argument space (as if they were pushes)
    void gcInfoRecordGCStackArgLive  (GcInfoEncoder* gcInfoEncoder,
                                      MakeRegPtrMode mode,
                                      regPtrDsc* genStackPtr);

    // Walk all the pushes between genStackPtrFirst (inclusive) and genStackPtrLast (exclusive)
    // and mark them as going dead at instrOffset
    void gcInfoRecordGCStackArgsDead (GcInfoEncoder* gcInfoEncoder,
                                      unsigned instrOffset,
                                      regPtrDsc* genStackPtrFirst,
                                      regPtrDsc* genStackPtrLast);

#endif

#if MEASURE_PTRTAB_SIZE
    static size_t       s_gcRegPtrDscSize;
    static size_t       s_gcTotalPtrTabSize;
#endif

    regPtrDsc  *        gcRegPtrAllocDsc      ();

/*****************************************************************************/


    //-------------------------------------------------------------------------
    //
    //  If we're not generating fully interruptible code, we create a simple
    //  linked list of call descriptors.
    //

    struct  CallDsc
    {
        CallDsc     *       cdNext;
        void        *       cdBlock;        // the code block of the call
        unsigned            cdOffs;         // the offset     of the call
#ifndef JIT32_GCENCODER
        unsigned short      cdCallInstrSize;// the size       of the call instruction.
#endif

        unsigned short      cdArgCnt;

        union
        {
            struct                          // used if cdArgCnt == 0
            {
                unsigned    cdArgMask;      // ptr arg bitfield
                unsigned    cdByrefArgMask; // byref qualifier for cdArgMask
            } u1;

            unsigned    *   cdArgTable;     // used if cdArgCnt != 0
        };

        regMaskSmall        cdGCrefRegs;
        regMaskSmall        cdByrefRegs;
    };

    CallDsc    *        gcCallDescList;
    CallDsc    *        gcCallDescLast;

    //-------------------------------------------------------------------------

    void                gcCountForHeader  (UNALIGNED unsigned int * untrackedCount,
                                           UNALIGNED unsigned int * varPtrTableSize);

#ifdef JIT32_GCENCODER
    size_t              gcMakeRegPtrTable (BYTE *         dest,
                                           int            mask,
                                           const InfoHdr& header,
                                           unsigned       codeSize,
                                           size_t*       pArgTabOffset);
#else
    RegSlotMap*   m_regSlotMap;
    StackSlotMap* m_stackSlotMap;
    // This method has two modes.  In the "assign slots" mode, it figures out what registers and stack
    // locations are used to contain GC references, and whether those locations contain byrefs or pinning
    // references, building up mappings from tuples of <reg/offset X byref/pinning> to the corresponding
    // slot id (in the two member fields declared above).  In the "do work" mode, we use these slot ids to 
    // actually declare live ranges to the encoder.
    void                gcMakeRegPtrTable (GcInfoEncoder* gcInfoEncoder,
                                           unsigned       codeSize,
                                           unsigned       prologSize,
                                           MakeRegPtrMode mode);
#endif

#ifdef JIT32_GCENCODER
    size_t              gcPtrTableSize    (const InfoHdr& header,
                                           unsigned       codeSize,
                                           size_t*       pArgTabOffset);
    BYTE    *           gcPtrTableSave    (BYTE *         destPtr,
                                           const InfoHdr& header,
                                           unsigned       codeSize,
                                           size_t*       pArgTabOffset);
#endif
    void                gcRegPtrSetInit   ();
/*****************************************************************************/

    // This enumeration yields the result of the analysis below, whether a store
    // requires a write barrier:
    enum WriteBarrierForm
    {
        WBF_NoBarrier,          // No barrier is required
        WBF_BarrierUnknown,     // A barrier is required, no information on checked/unchecked.
        WBF_BarrierChecked,     // A checked barrier is required.
        WBF_BarrierUnchecked,   // An unchecked barrier is required.
        WBF_NoBarrier_CheckNotHeapInDebug,  // We believe that no barrier is required because the
                                            // target is not in the heap -- but in debug build use a
                                            // barrier call that verifies this property.  (Because the
                                            // target not being in the heap relies on a convention that
                                            // might accidentally be violated in the future.)
    };

    WriteBarrierForm        gcIsWriteBarrierCandidate(GenTreePtr tgt, GenTreePtr assignVal);
    bool                    gcIsWriteBarrierAsgNode  (GenTreePtr op);

    // Returns a WriteBarrierForm decision based on the form of "tgtAddr", which is assumed to be the
    // argument of a GT_IND LHS.
    WriteBarrierForm        gcWriteBarrierFormFromTargetAddress(GenTreePtr tgtAddr);

    //-------------------------------------------------------------------------
    //
    //  These record the info about the procedure in the info-block
    //

#ifdef JIT32_GCENCODER
private:
    BYTE    *           gcEpilogTable;

    unsigned            gcEpilogPrevOffset;

    size_t              gcInfoBlockHdrSave(BYTE *       dest,
                                           int          mask,
                                           unsigned     methodSize,
                                           unsigned     prologSize,
                                           unsigned     epilogSize,
                                           InfoHdr *    header,
                                           int *        s_cached);
public:
    static void         gcInitEncoderLookupTable ();
private:
    static size_t       gcRecordEpilog    (void *       pCallBackData,
                                           unsigned     offset);
#else // JIT32_GCENCODER
    void                gcInfoBlockHdrSave(GcInfoEncoder* gcInfoEncoder,
                                           unsigned       methodSize,
                                           unsigned       prologSize);

#ifdef DEBUG
    void                gcDumpVarPtrDsc   (varPtrDsc*     desc);
#endif // DEBUG

#endif // JIT32_GCENCODER


#if DUMP_GC_TABLES

    void                gcFindPtrsInFrame (const void * infoBlock,
                                           const void * codeBlock,
                                           unsigned     offs);

#ifdef JIT32_GCENCODER
    unsigned            gcInfoBlockHdrDump(const BYTE * table,
                                           InfoHdr    * header,       /* OUT */
                                           unsigned   * methodSize);  /* OUT */

    unsigned            gcDumpPtrTable    (const BYTE *   table,
                                           const InfoHdr& header,
                                           unsigned       methodSize);

#endif // JIT32_GCENCODER
#endif // DUMP_GC_TABLES

#ifndef LEGACY_BACKEND
    // This method updates the appropriate reg masks when a variable is moved.
public:
    void                gcUpdateForRegVarMove(regMaskTP srcMask, regMaskTP dstMask, LclVarDsc *varDsc);
#endif // !LEGACY_BACKEND
};


inline
unsigned char encodeUnsigned(BYTE *dest, unsigned value)
{
    unsigned char size = 1;
    unsigned tmp = value;
    while (tmp > 0x7F) {
        tmp >>= 7;
        assert(size < 6);  // Invariant.
        size++;
    }
    if (dest) {
        // write the bytes starting at the end of dest in LSB to MSB order
        BYTE* p    = dest + size;
        BYTE  cont = 0; // The last byte has no continuation flag
        while (value > 0x7F) {
            *--p = cont | (value & 0x7f);
            value >>= 7;
            cont = 0x80;        // Non last bytes have a continuation flag
        }
        *--p = cont | (BYTE)value;    // Now write the first byte
        assert(p == dest);
    }
    return size;
}

inline
unsigned char encodeUDelta(BYTE *dest, unsigned value, unsigned lastValue)
{
    assert(value >= lastValue);
    return encodeUnsigned(dest, value - lastValue);
}

inline
unsigned char encodeSigned(BYTE *dest, int val)
{
    unsigned char size  = 1;
    unsigned value = val;
    BYTE  neg = 0;
    if ( val < 0) {
        value = -val;
        neg = 0x40;
    }
    unsigned tmp   = value;
    while (tmp > 0x3F) {
        tmp >>= 7;
        assert(size < 16); // Definitely sufficient for unsigned.  Fits in an unsigned char, certainly.
        size++;
    }
    if (dest) {
        // write the bytes starting at the end of dest in LSB to MSB order
        BYTE* p    = dest + size;
        BYTE  cont = 0; // The last byte has no continuation flag
        while (value > 0x3F) {
            *--p = cont | (value & 0x7f);
            value >>= 7;
            cont = 0x80;        // Non last bytes have a continuation flag
        }
        *--p = neg | cont | (BYTE)value; // Now write the first byte
        assert(p == dest);
    }
    return size;
}



#endif // _JITGCINFO_H_