src/jit/sm.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   6 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   7 XX                                                                           XX
   8 XX                 State machine used in the JIT                             XX
   9 XX                                                                           XX
  10 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  11 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  12 */
  13
  14 #include "jitpch.h"
  15 #ifdef _MSC_VER
  16 #pragma hdrstop
  17 #endif
  18
  19 #include "smcommon.cpp"
  20
  21 //
  22 // The array to map from EE opcodes (i.e. CEE_ ) to state machine opcodes (i.e. SM_ )
  23 //
  24 const SM_OPCODE smOpcodeMap[] = {
  25 #define OPCODEMAP(eename, eestring, smname) smname,
  26 #include "smopcodemap.def"
  27 #undef OPCODEMAP
  28 };
  29
  30 // ????????? How to make this method inlinable, since it refers to smOpcodeMap????
  31 /* static */ SM_OPCODE CodeSeqSM::MapToSMOpcode(OPCODE opcode)
  32 {
  33     assert(opcode < CEE_COUNT);
  34
  35     SM_OPCODE smOpcode = smOpcodeMap[opcode];
  36     assert(smOpcode < SM_COUNT);
  37     return smOpcode;
  38 }
  39
  40 void CodeSeqSM::Start(Compiler* comp)
  41 {
  42     pComp          = comp;
  43     States         = gp_SMStates;
  44     JumpTableCells = gp_SMJumpTableCells;
  45     StateWeights   = gp_StateWeights;
  46     NativeSize     = 0;
  47
  48     Reset();
  49 }
  50
  51 void CodeSeqSM::Reset()
  52 {
  53     curState = SM_STATE_ID_START;
  54
  55 #ifdef DEBUG
  56     // Reset the state occurence counts
  57     memset(StateMatchedCounts, 0, sizeof(StateMatchedCounts));
  58 #endif
  59 }
  60
  61 void CodeSeqSM::End()
  62 {
  63     if (States[curState].term)
  64     {
  65         TermStateMatch(curState DEBUGARG(pComp->verbose));
  66     }
  67 }
  68
  69 void CodeSeqSM::Run(SM_OPCODE opcode DEBUGARG(int level))
  70 {
  71     SM_STATE_ID nextState;
  72     SM_STATE_ID rollbackState;
  73
  74     SM_OPCODE opcodesToRevisit[MAX_CODE_SEQUENCE_LENGTH];
  75
  76     assert(level <= MAX_CODE_SEQUENCE_LENGTH);
  77
  78 _Next:
  79     nextState = GetDestState(curState, opcode);
  80
  81     if (nextState != 0)
  82     {
  83         // This is easy, Just go to the next state.
  84         curState = nextState;
  85         return;
  86     }
  87
  88     assert(curState != SM_STATE_ID_START);
  89
  90     if (States[curState].term)
  91     {
  92         TermStateMatch(curState DEBUGARG(pComp->verbose));
  93         curState = SM_STATE_ID_START;
  94         goto _Next;
  95     }
  96
  97     // This is hard. We need to rollback to the longest matched term state and restart from there.
  98
  99     rollbackState = States[curState].longestTermState;
 100     TermStateMatch(rollbackState DEBUGARG(pComp->verbose));
 101
 102     assert(States[curState].length > States[rollbackState].length);
 103
 104     unsigned numOfOpcodesToRevisit = States[curState].length - States[rollbackState].length + 1;
 105     assert(numOfOpcodesToRevisit > 1 &&
 106            numOfOpcodesToRevisit <= MAX_CODE_SEQUENCE_LENGTH); // So it can fit in the local array opcodesToRevisit[]
 107
 108     SM_OPCODE* p = opcodesToRevisit + (numOfOpcodesToRevisit - 1);
 109
 110     *p = opcode;
 111
 112     // Fill in the local array:
 113     for (unsigned i = 0; i < numOfOpcodesToRevisit - 1; ++i)
 114     {
 115         *(--p)   = States[curState].opc;
 116         curState = States[curState].prevState;
 117     }
 118
 119     assert(curState == rollbackState);
 120
 121     // Now revisit these opcodes, starting from SM_STATE_ID_START.
 122     curState = SM_STATE_ID_START;
 123     for (p = opcodesToRevisit; p < opcodesToRevisit + numOfOpcodesToRevisit; ++p)
 124     {
 125         Run(*p DEBUGARG(level + 1));
 126     }
 127 }
 128
 129 SM_STATE_ID CodeSeqSM::GetDestState(SM_STATE_ID srcState, SM_OPCODE opcode)
 130 {
 131     assert(opcode < SM_COUNT);
 132
 133     JumpTableCell* pThisJumpTable = (JumpTableCell*)(((PBYTE)JumpTableCells) + States[srcState].jumpTableByteOffset);
 134
 135     JumpTableCell* cell = pThisJumpTable + opcode;
 136
 137     if (cell->srcState != srcState)
 138     {
 139         assert(cell->srcState == 0 ||
 140                cell->srcState != srcState); // Either way means there is not outgoing edge from srcState.
 141         return 0;
 142     }
 143     else
 144     {
 145         return cell->destState;
 146     }
 147 }
 148
 149 #ifdef DEBUG
 150
 151 const char* CodeSeqSM::StateDesc(SM_STATE_ID stateID)
 152 {
 153     static char      s_StateDesc[500];
 154     static SM_OPCODE s_StateDescOpcodes[MAX_CODE_SEQUENCE_LENGTH];
 155
 156     if (stateID == 0)
 157     {
 158         return "invalid";
 159     }
 160     if (stateID == SM_STATE_ID_START)
 161     {
 162         return "start";
 163     }
 164     unsigned i = 0;
 165
 166     SM_STATE_ID b = stateID;
 167
 168     while (States[b].prevState != 0)
 169     {
 170         s_StateDescOpcodes[i] = States[b].opc;
 171         b                     = States[b].prevState;
 172         ++i;
 173     }
 174
 175     assert(i == States[stateID].length && i > 0);
 176
 177     *s_StateDesc = 0;
 178
 179     while (--i > 0)
 180     {
 181         strcat(s_StateDesc, smOpcodeNames[s_StateDescOpcodes[i]]);
 182         strcat(s_StateDesc, " -> ");
 183     }
 184
 185     strcat(s_StateDesc, smOpcodeNames[s_StateDescOpcodes[0]]);
 186
 187     return s_StateDesc;
 188 }
 189
 190 #endif // DEBUG