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
  56 void CodeSeqSM::End()
  57 {
  58     if (States[curState].term)
  59     {
  60         TermStateMatch(curState DEBUGARG(pComp->verbose));
  61     }
  62 }
  63
  64 void CodeSeqSM::Run(SM_OPCODE opcode DEBUGARG(int level))
  65 {
  66     SM_STATE_ID nextState;
  67     SM_STATE_ID rollbackState;
  68
  69     SM_OPCODE opcodesToRevisit[MAX_CODE_SEQUENCE_LENGTH];
  70
  71     assert(level <= MAX_CODE_SEQUENCE_LENGTH);
  72
  73 _Next:
  74     nextState = GetDestState(curState, opcode);
  75
  76     if (nextState != 0)
  77     {
  78         // This is easy, Just go to the next state.
  79         curState = nextState;
  80         return;
  81     }
  82
  83     assert(curState != SM_STATE_ID_START);
  84
  85     if (States[curState].term)
  86     {
  87         TermStateMatch(curState DEBUGARG(pComp->verbose));
  88         curState = SM_STATE_ID_START;
  89         goto _Next;
  90     }
  91
  92     // This is hard. We need to rollback to the longest matched term state and restart from there.
  93
  94     rollbackState = States[curState].longestTermState;
  95     TermStateMatch(rollbackState DEBUGARG(pComp->verbose));
  96
  97     assert(States[curState].length > States[rollbackState].length);
  98
  99     unsigned numOfOpcodesToRevisit = States[curState].length - States[rollbackState].length + 1;
 100     assert(numOfOpcodesToRevisit > 1 &&
 101            numOfOpcodesToRevisit <= MAX_CODE_SEQUENCE_LENGTH); // So it can fit in the local array opcodesToRevisit[]
 102
 103     SM_OPCODE* p = opcodesToRevisit + (numOfOpcodesToRevisit - 1);
 104
 105     *p = opcode;
 106
 107     // Fill in the local array:
 108     for (unsigned i = 0; i < numOfOpcodesToRevisit - 1; ++i)
 109     {
 110         *(--p)   = States[curState].opc;
 111         curState = States[curState].prevState;
 112     }
 113
 114     assert(curState == rollbackState);
 115
 116     // Now revisit these opcodes, starting from SM_STATE_ID_START.
 117     curState = SM_STATE_ID_START;
 118     for (p = opcodesToRevisit; p < opcodesToRevisit + numOfOpcodesToRevisit; ++p)
 119     {
 120         Run(*p DEBUGARG(level + 1));
 121     }
 122 }
 123
 124 SM_STATE_ID CodeSeqSM::GetDestState(SM_STATE_ID srcState, SM_OPCODE opcode)
 125 {
 126     assert(opcode < SM_COUNT);
 127
 128     JumpTableCell* pThisJumpTable = (JumpTableCell*)(((PBYTE)JumpTableCells) + States[srcState].jumpTableByteOffset);
 129
 130     JumpTableCell* cell = pThisJumpTable + opcode;
 131
 132     if (cell->srcState != srcState)
 133     {
 134         assert(cell->srcState == 0 ||
 135                cell->srcState != srcState); // Either way means there is not outgoing edge from srcState.
 136         return 0;
 137     }
 138     else
 139     {
 140         return cell->destState;
 141     }
 142 }
 143
 144 #ifdef DEBUG
 145
 146 const char* CodeSeqSM::StateDesc(SM_STATE_ID stateID)
 147 {
 148     static char      s_StateDesc[500];
 149     static SM_OPCODE s_StateDescOpcodes[MAX_CODE_SEQUENCE_LENGTH];
 150
 151     if (stateID == 0)
 152     {
 153         return "invalid";
 154     }
 155     if (stateID == SM_STATE_ID_START)
 156     {
 157         return "start";
 158     }
 159     unsigned i = 0;
 160
 161     SM_STATE_ID b = stateID;
 162
 163     while (States[b].prevState != 0)
 164     {
 165         s_StateDescOpcodes[i] = States[b].opc;
 166         b                     = States[b].prevState;
 167         ++i;
 168     }
 169
 170     assert(i == States[stateID].length && i > 0);
 171
 172     *s_StateDesc = 0;
 173
 174     while (--i > 0)
 175     {
 176         strcat(s_StateDesc, smOpcodeNames[s_StateDescOpcodes[i]]);
 177         strcat(s_StateDesc, " -> ");
 178     }
 179
 180     strcat(s_StateDesc, smOpcodeNames[s_StateDescOpcodes[0]]);
 181
 182     return s_StateDesc;
 183 }
 184
 185 #endif // DEBUG