diff options
Diffstat (limited to 'src/libfsm/asm.cc')
| -rw-r--r-- | src/libfsm/asm.cc | 2046 |
1 files changed, 2046 insertions, 0 deletions
diff --git a/src/libfsm/asm.cc b/src/libfsm/asm.cc new file mode 100644 index 00000000..ecfe1c0f --- /dev/null +++ b/src/libfsm/asm.cc @@ -0,0 +1,2046 @@ +/* + * Copyright 2014-2018 Adrian Thurston <thurston@colm.net> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "ragel.h" +#include "asm.h" +#include "redfsm.h" +#include "gendata.h" +#include "bstmap.h" +#include "ragel.h" +#include "redfsm.h" +#include "bstmap.h" +#include "gendata.h" +#include "parsedata.h" +#include <sstream> + +using std::ostream; +using std::ostringstream; +using std::string; +using std::endl; +using std::istream; +using std::ifstream; +using std::ostream; +using std::ios; +using std::cin; +using std::endl; + +extern int numSplitPartitions; +bool printStatistics = false; + +/* Enables transition logging in the form that score-based state sorting can + * processes. This bit of code is intended to increase locality and reduce + * cache misses. Gains are minimal, 1-2%. */ +// #define LOG_TRANS 1 + +void asmLineDirective( ostream &out, const char *fileName, int line ) +{ + /* Write the preprocessor line info for to the input file. */ + out << "#line " << line << " \""; + for ( const char *pc = fileName; *pc != 0; pc++ ) { + if ( *pc == '\\' ) + out << "\\\\"; + else + out << *pc; + } + out << '"'; + + out << '\n'; +} + +/* Init code gen with in parameters. */ +AsmCodeGen::AsmCodeGen( const CodeGenArgs &args ) +: + CodeGenData( args ), + nextLmSwitchLabel( 1 ), + stackCS( false ) +{ +} + +void AsmCodeGen::genAnalysis() +{ + /* For directly executable machines there is no required state + * ordering. Choose a depth-first ordering to increase the + * potential for fall-throughs. */ + redFsm->depthFirstOrdering(); + + /* Choose default transitions and make the flat transitions by character class. */ + redFsm->chooseDefaultSpan(); + redFsm->makeFlatClass(); + + /* If any errors have occured in the input file then don't write anything. */ + if ( red->id->errorCount > 0 ) + return; + + redFsm->setInTrans(); + + /* Anlayze Machine will find the final action reference counts, among other + * things. We will use these in reporting the usage of fsm directives in + * action code. */ + red->analyzeMachine(); +} + +/* Write out the fsm name. */ +string AsmCodeGen::FSM_NAME() +{ + return fsmName; +} + +/* Emit the offset of the start state as a decimal integer. */ +string AsmCodeGen::START_STATE_ID() +{ + ostringstream ret; + ret << redFsm->startState->id; + return ret.str(); +}; + +string AsmCodeGen::ACCESS() +{ + ostringstream ret; + if ( red->accessExpr != 0 ) + INLINE_LIST( ret, red->accessExpr, 0, false, false ); + return ret.str(); +} + + +string AsmCodeGen::P() +{ + ostringstream ret; + if ( red->pExpr == 0 ) + ret << "%r12"; + else { + INLINE_LIST( ret, red->pExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::PE() +{ + ostringstream ret; + if ( red->peExpr == 0 ) + ret << "%r13"; + else { + INLINE_LIST( ret, red->peExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::vCS() +{ + ostringstream ret; + if ( red->csExpr == 0 ) { + if ( stackCS ) + ret << "-48(%rbp)"; + else + ret << "%r11"; + } + else { + INLINE_LIST( ret, red->csExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::TOP() +{ + ostringstream ret; + if ( red->topExpr == 0 ) + ret << "-64(%rbp)"; + else { + ret << "("; + INLINE_LIST( ret, red->topExpr, 0, false, false ); + ret << ")"; + } + return ret.str(); +} + +string AsmCodeGen::NFA_STACK() +{ + return string( "-80(%rbp)" ); +} + +string AsmCodeGen::NFA_TOP() +{ + return string( "-88(%rbp)" ); +} + +string AsmCodeGen::NFA_SZ() +{ + return string( "-96(%rbp)" ); +} + +string AsmCodeGen::STACK() +{ + ostringstream ret; + if ( red->stackExpr == 0 ) + ret << "-56(%rbp)"; + else { + ret << "("; + INLINE_LIST( ret, red->stackExpr, 0, false, false ); + ret << ")"; + } + return ret.str(); +} + +string AsmCodeGen::vEOF() +{ + ostringstream ret; + if ( red->eofExpr == 0 ) + ret << "-8(%rbp)"; + else { + INLINE_LIST( ret, red->eofExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::TOKSTART() +{ + ostringstream ret; + if ( red->tokstartExpr == 0 ) + ret << "-16(%rbp)"; + else { + INLINE_LIST( ret, red->tokstartExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::TOKEND() +{ + ostringstream ret; + if ( red->tokendExpr == 0 ) + ret << "-24(%rbp)"; + else { + INLINE_LIST( ret, red->tokendExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::ACT() +{ + ostringstream ret; + if ( red->actExpr == 0 ) + ret << "-32(%rbp)"; + else { + INLINE_LIST( ret, red->actExpr, 0, false, false ); + } + return ret.str(); +} + +string AsmCodeGen::NBREAK() +{ + return string("-33(%rbp)"); +} + +string AsmCodeGen::GET_KEY() +{ + ostringstream ret; + if ( red->getKeyExpr != 0 ) { + /* Emit the user supplied method of retrieving the key. */ + ret << "("; + INLINE_LIST( ret, red->getKeyExpr, 0, false, false ); + ret << ")"; + } + else { + /* Expression for retrieving the key, use simple dereference. */ + ret << "(" << P() << ")"; + } + return ret.str(); +} + +string AsmCodeGen::COND_KEY( CondKey key ) +{ + ostringstream ret; + ret << "$" << key.getVal(); + return ret.str(); +} + + +/* Write out a key from the fsm code gen. Depends on wether or not the key is + * signed. */ +string AsmCodeGen::KEY( Key key ) +{ + ostringstream ret; + ret << "$" << key.getVal(); + return ret.str(); +} + +bool AsmCodeGen::isAlphTypeSigned() +{ + return keyOps->isSigned; +} + +void AsmCodeGen::EXEC( ostream &ret, GenInlineItem *item, int targState, int inFinish ) +{ + /* The parser gives fexec two children. The double brackets are for D + * code. If the inline list is a single word it will get interpreted as a + * C-style cast by the D compiler. */ + + ret << + " subq $1, "; + INLINE_LIST( ret, item->children, targState, inFinish, false ); + ret << + "\n" + " movq "; + INLINE_LIST( ret, item->children, targState, inFinish, false ); + ret << ", " << P() << "\n"; +} + +void AsmCodeGen::LM_SWITCH( ostream &ret, GenInlineItem *item, + int targState, int inFinish, bool csForced ) +{ + long done = nextLmSwitchLabel++; + + ret << + " movq " << ACT() << ", %rax\n"; + + for ( GenInlineList::Iter lma = *item->children; lma.lte(); lma++ ) { + long l = nextLmSwitchLabel++; + + /* Write the case label, the action and the case break. */ + if ( lma->lmId < 0 ) { + } + else { + ret << + " cmpq $" << lma->lmId << ", %rax\n" + " jne " << LABEL( "lm_switch_next", l ) << "\n"; + } + + INLINE_LIST( ret, lma->children, targState, inFinish, csForced ); + + ret << + " jmp " << LABEL( "lm_done", done ) << "\n" + "" << LABEL( "lm_switch_next", l ) << ":\n"; + } + + ret << + "" << LABEL( "lm_done", done ) << ":\n"; +} + +void AsmCodeGen::SET_ACT( ostream &ret, GenInlineItem *item ) +{ + ret << + " movq $" << item->lmId << ", " << ACT() << "\n"; +} + +void AsmCodeGen::SET_TOKEND( ostream &ret, GenInlineItem *item ) +{ + /* Sets tokend, there may be an offset. */ + ret << + " movq " << P() << ", %rax\n"; + + if ( item->offset != 0 ) { + out << + " addq $" << item->offset << ", %rax\n"; + } + + out << + " movq %rax, " << TOKEND() << "\n"; +} + +void AsmCodeGen::GET_TOKEND( ostream &ret, GenInlineItem *item ) +{ + ret << + " movq " << TOKEND() << ", " << "%rax\n"; +} + +void AsmCodeGen::INIT_TOKSTART( ostream &ret, GenInlineItem *item ) +{ + ret << + " movq $0, " << TOKSTART() << "\n"; +} + +void AsmCodeGen::INIT_ACT( ostream &ret, GenInlineItem *item ) +{ + ret << + " movq $0, " << ACT() << "\n"; +} + +void AsmCodeGen::SET_TOKSTART( ostream &ret, GenInlineItem *item ) +{ + ret << + " movq " << P() << ", " << TOKSTART() << "\n"; +} + +void AsmCodeGen::HOST_STMT( ostream &ret, GenInlineItem *item, + int targState, bool inFinish, bool csForced ) +{ + if ( item->children->length() > 0 ) { + /* Write the block and close it off. */ + INLINE_LIST( ret, item->children, targState, inFinish, csForced ); + } +} + +void AsmCodeGen::HOST_EXPR( ostream &ret, GenInlineItem *item, + int targState, bool inFinish, bool csForced ) +{ + if ( item->children->length() > 0 ) { + /* Write the block and close it off. */ + INLINE_LIST( ret, item->children, targState, inFinish, csForced ); + } +} + +void AsmCodeGen::HOST_TEXT( ostream &ret, GenInlineItem *item, + int targState, bool inFinish, bool csForced ) +{ + if ( item->children->length() > 0 ) { + /* Write the block and close it off. */ + INLINE_LIST( ret, item->children, targState, inFinish, csForced ); + } +} + +void AsmCodeGen::GEN_STMT( ostream &ret, GenInlineItem *item, + int targState, bool inFinish, bool csForced ) +{ + if ( item->children->length() > 0 ) { + /* Write the block and close it off. */ + INLINE_LIST( ret, item->children, targState, inFinish, csForced ); + } +} + +void AsmCodeGen::GEN_EXPR( ostream &ret, GenInlineItem *item, + int targState, bool inFinish, bool csForced ) +{ + if ( item->children->length() > 0 ) { + /* Write the block and close it off. */ + INLINE_LIST( ret, item->children, targState, inFinish, csForced ); + } +} + +void AsmCodeGen::LM_EXEC( ostream &ret, GenInlineItem *item, int targState, int inFinish ) +{ + /* The parser gives fexec two children. The double brackets are for D code. + * If the inline list is a single word it will get interpreted as a C-style + * cast by the D compiler. This should be in the D code generator. */ + INLINE_LIST( ret, item->children, targState, inFinish, false ); + + ret << + " movq %rax, " << P() << "\n" + " subq $1, " << P() << "\n"; +} + +void AsmCodeGen::NBREAK( ostream &ret, int targState, bool csForced ) +{ + outLabelUsed = true; + ret << + " addq $1, " << P() << "\n"; + + if ( !csForced ) { + ret << + " movq $" << targState << ", " << vCS() << "\n"; + } + + ret << + " movb $1, " << NBREAK() << "\n" + " jmp " << LABEL( "pop" ) << "\n"; +} + +/* Write out an inline tree structure. Walks the list and possibly calls out + * to virtual functions than handle language specific items in the tree. */ +void AsmCodeGen::INLINE_LIST( ostream &ret, GenInlineList *inlineList, + int targState, bool inFinish, bool csForced ) +{ + for ( GenInlineList::Iter item = *inlineList; item.lte(); item++ ) { + switch ( item->type ) { + case GenInlineItem::Text: + ret << item->data; + break; + case GenInlineItem::Goto: + GOTO( ret, item->targState->id, inFinish ); + break; + case GenInlineItem::Call: + CALL( ret, item->targState->id, targState, inFinish ); + break; + case GenInlineItem::Next: + NEXT( ret, item->targState->id, inFinish ); + break; + case GenInlineItem::Ret: + RET( ret, inFinish ); + break; + case GenInlineItem::PChar: + ret << P(); + break; + case GenInlineItem::Char: + ret << GET_KEY(); + break; + case GenInlineItem::Hold: + ret << + " subq $1, " << P() << "\n"; + break; + case GenInlineItem::Exec: + EXEC( ret, item, targState, inFinish ); + break; + case GenInlineItem::Curs: + CURS( ret, inFinish ); + break; + case GenInlineItem::Targs: + TARGS( ret, inFinish, targState ); + break; + case GenInlineItem::Entry: + ret << item->targState->id; + break; + case GenInlineItem::GotoExpr: + GOTO_EXPR( ret, item, inFinish ); + break; + case GenInlineItem::CallExpr: + CALL_EXPR( ret, item, targState, inFinish ); + break; + case GenInlineItem::NextExpr: + NEXT_EXPR( ret, item, inFinish ); + break; + case GenInlineItem::LmSwitch: + LM_SWITCH( ret, item, targState, inFinish, csForced ); + break; + case GenInlineItem::LmSetActId: + SET_ACT( ret, item ); + break; + case GenInlineItem::LmSetTokEnd: + SET_TOKEND( ret, item ); + break; + case GenInlineItem::LmGetTokEnd: + GET_TOKEND( ret, item ); + break; + case GenInlineItem::LmInitTokStart: + INIT_TOKSTART( ret, item ); + break; + case GenInlineItem::LmInitAct: + INIT_ACT( ret, item ); + break; + case GenInlineItem::LmSetTokStart: + SET_TOKSTART( ret, item ); + break; + case GenInlineItem::Break: + BREAK( ret, targState, csForced ); + break; + /* Stubbed. */ + case GenInlineItem::Ncall: + NCALL( ret, item->targState->id, targState, inFinish ); + break; + case GenInlineItem::NcallExpr: + NCALL_EXPR( ret, item, targState, inFinish ); + break; + case GenInlineItem::Nret: + NRET( ret, inFinish ); + break; + case GenInlineItem::Nbreak: + NBREAK( ret, targState, csForced ); + break; + case GenInlineItem::LmCase: + break; + + case GenInlineItem::LmExec: + LM_EXEC( ret, item, targState, inFinish ); + break; + + case GenInlineItem::LmHold: + ret << + " subq $1, " << P() << "\n"; + break; + case GenInlineItem::NfaClear: + ret << + " movq $0, " << NFA_TOP() << "\n"; + break; + + case GenInlineItem::HostStmt: + HOST_STMT( ret, item, targState, inFinish, csForced ); + break; + case GenInlineItem::HostExpr: + HOST_EXPR( ret, item, targState, inFinish, csForced ); + break; + case GenInlineItem::HostText: + HOST_TEXT( ret, item, targState, inFinish, csForced ); + break; + case GenInlineItem::GenStmt: + GEN_STMT( ret, item, targState, inFinish, csForced ); + break; + case GenInlineItem::GenExpr: + GEN_EXPR( ret, item, targState, inFinish, csForced ); + break; + /* Handled at the top level. */ + case GenInlineItem::NfaWrapAction: + case GenInlineItem::NfaWrapConds: + break; + } + } +} +/* Write out paths in line directives. Escapes any special characters. */ +string AsmCodeGen::LDIR_PATH( char *path ) +{ + ostringstream ret; + for ( char *pc = path; *pc != 0; pc++ ) { + if ( *pc == '\\' ) + ret << "\\\\"; + else + ret << *pc; + } + return ret.str(); +} + +void AsmCodeGen::ACTION( ostream &ret, GenAction *action, int targState, + bool inFinish, bool csForced ) +{ + /* Write the preprocessor line info for going into the source file. */ + asmLineDirective( ret, action->loc.fileName, action->loc.line ); + + /* Write the block and close it off. */ + INLINE_LIST( ret, action->inlineList, targState, inFinish, csForced ); +} + +void AsmCodeGen::CONDITION( ostream &ret, GenAction *condition ) +{ + ret << "\n"; + asmLineDirective( ret, condition->loc.fileName, condition->loc.line ); + INLINE_LIST( ret, condition->inlineList, 0, false, false ); +} + +bool singleItem( GenAction *action, GenInlineItem::Type type ) +{ + return action->inlineList->length() == 1 && + action->inlineList->head->type == type; +} + +void AsmCodeGen::NFA_CONDITION( ostream &ret, GenAction *condition, bool last ) +{ + if ( singleItem( condition, GenInlineItem::NfaWrapAction ) ) + { + GenAction *action = condition->inlineList->head->wrappedAction; + ACTION( out, action, 0, false, false ); + } + else if ( singleItem( condition, GenInlineItem::NfaWrapConds ) ) + { + GenCondSpace *condSpace = condition->inlineList->head->condSpace; + const CondKeySet &condKeySet = condition->inlineList->head->condKeySet; + + out << " movq $0, %r9\n"; + for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) { + out << + " pushq %r9\n"; + + CONDITION( out, *csi ); + out << + "\n" + " test %eax, %eax\n" + " setne %cl\n" + " movsbq %cl, %rcx\n" + " salq $" << csi.pos() << ", %rcx\n" + " popq %r9\n" + " addq %rcx, %r9\n"; + } + + for ( int c = 0; c < condKeySet.length(); c++ ) { + CondKey key = condKeySet[c]; + out << + " cmpq " << COND_KEY( key ) << ", %r9\n" + " je 102f\n"; + } + + out << + " jmp " << LABEL( "pop_fail" ) << "\n" + "102:\n"; + } + else { + CONDITION( ret, condition ); + out << + " test %eax, %eax\n" + " jz " << LABEL( "pop_fail" ) << "\n"; + } +} + +string AsmCodeGen::ERROR_STATE() +{ + ostringstream ret; + if ( redFsm->errState != 0 ) + ret << redFsm->errState->id; + else + ret << "-1"; + return ret.str(); +} + +string AsmCodeGen::FIRST_FINAL_STATE() +{ + ostringstream ret; + if ( redFsm->firstFinState != 0 ) + ret << redFsm->firstFinState->id; + else + ret << redFsm->nextStateId; + return ret.str(); +} + +void AsmCodeGen::writeInit() +{ + if ( !noCS ) { + /* Don't use vCS here. vCS may assumes CS needs to be on the stack. + * Just use the interface register. */ + out << + " movq $" << redFsm->startState->id << ", %r11\n"; + } + + if ( redFsm->anyNfaStates() ) { + out << + " movq $0, " << NFA_TOP() << "\n"; + } + + /* If there are any calls, then the stack top needs initialization. */ + if ( redFsm->anyActionCalls() || redFsm->anyActionRets() ) { + out << + " movq $0, " << TOP() << "\n"; + } + + if ( red->hasLongestMatch ) { + out << + " movq $0, " << TOKSTART() << "\n" + " movq $0, " << TOKEND() << "\n" + " movq $0, " << ACT() << "\n"; + } +} + +string AsmCodeGen::DATA_PREFIX() +{ + if ( !noPrefix ) + return FSM_NAME() + "_"; + return ""; +} + +/* Emit the alphabet data type. */ +string AsmCodeGen::ALPH_TYPE() +{ + string ret = alphType->data1; + if ( alphType->data2 != 0 ) { + ret += " "; + ret += + alphType->data2; + } + return ret; +} + +void AsmCodeGen::STATIC_CONST_INT( const string &name, const string &value ) +{ + out << + " .align 8\n" + " .type " << name << ", @object\n" + " .size " << name << ", 8\n" << + name << ":\n" + " .long " << value << "\n"; +} + +void AsmCodeGen::STATE_IDS() +{ + if ( redFsm->startState != 0 ) + STATIC_CONST_INT( START(), START_STATE_ID() ); + + if ( !noFinal ) + STATIC_CONST_INT( FIRST_FINAL(), FIRST_FINAL_STATE() ); + + if ( !noError ) + STATIC_CONST_INT( ERROR(), ERROR_STATE() ); + + out << "\n"; + + if ( red->entryPointNames.length() > 0 ) { + for ( EntryNameVect::Iter en = red->entryPointNames; en.lte(); en++ ) { + ostringstream ret; + ret << redFsm->startState->id; + + STATIC_CONST_INT( string( DATA_PREFIX() + "en_" + *en ), + ret.str() ); + } + out << "\n"; + } +} + +void AsmCodeGen::writeStart() +{ + out << START_STATE_ID(); +} + +void AsmCodeGen::writeFirstFinal() +{ + out << FIRST_FINAL_STATE(); +} + +void AsmCodeGen::writeError() +{ + out << ERROR_STATE(); +} + +string AsmCodeGen::PTR_CONST() +{ + return "const "; +} + +string AsmCodeGen::PTR_CONST_END() +{ + return ""; +} + +std::ostream &AsmCodeGen::OPEN_ARRAY( string type, string name ) +{ + out << "static const " << type << " " << name << "[] = {\n"; + return out; +} + +std::ostream &AsmCodeGen::CLOSE_ARRAY() +{ + return out << "};\n"; +} + +std::ostream &AsmCodeGen::STATIC_VAR( string type, string name ) +{ + out << "static const " << type << " " << name; + return out; +} + +string AsmCodeGen::UINT( ) +{ + return "unsigned int"; +} + +string AsmCodeGen::ARR_OFF( string ptr, string offset ) +{ + return ptr + " + " + offset; +} + +string AsmCodeGen::CAST( string type ) +{ + return "(" + type + ")"; +} + +string AsmCodeGen::NULL_ITEM() +{ + return "0"; +} + +string AsmCodeGen::POINTER() +{ + return " *"; +} + +std::ostream &AsmCodeGen::SWITCH_DEFAULT() +{ + return out; +} + +string AsmCodeGen::CTRL_FLOW() +{ + return ""; +} + +void AsmCodeGen::writeExports() +{ + if ( red->exportList.length() > 0 ) { + for ( ExportList::Iter ex = red->exportList; ex.lte(); ex++ ) { + out << "#define " << DATA_PREFIX() << "ex_" << ex->name << " " << + KEY(ex->key) << "\n"; + } + out << "\n"; + } +} + +string AsmCodeGen::LABEL( const char *type, long i ) +{ + std::stringstream s; + s << ".L" << red->machineId << "_" << type << "_" << i; + return s.str(); +} + +string AsmCodeGen::LABEL( const char *name ) +{ + std::stringstream s; + s << ".L" << red->machineId << "_" << name; + return s.str(); +} + +void AsmCodeGen::emitSingleIfElseIf( RedStateAp *state ) +{ + /* Load up the singles. */ + int numSingles = state->outSingle.length(); + RedTransEl *data = state->outSingle.data; + + /* Write out the single indices. */ + for ( int j = 0; j < numSingles; j++ ) { + out << + " cmpb " << KEY( data[j].lowKey ) << ", %r10b\n" + " je " << TRANS_GOTO_TARG( data[j].value ) << "\n"; + } +} + +void AsmCodeGen::emitSingleJumpTable( RedStateAp *state, string def ) +{ + int numSingles = state->outSingle.length(); + RedTransEl *data = state->outSingle.data; + + long long low = data[0].lowKey.getVal(); + long long high = data[numSingles-1].lowKey.getVal(); + + if ( def.size() == 0 ) + def = LABEL( "sjf", state->id ); + + out << + " movzbq %r10b, %rax\n" + " subq $" << low << ", %rax\n" + " cmpq $" << (high - low) << ", %rax\n" + " ja " << def << "\n" + " leaq " << LABEL( "sjt", state->id ) << "(%rip), %rcx\n" + " movslq (%rcx,%rax,4), %rdx\n" + " addq %rcx, %rdx\n" + " jmp *%rdx\n" + " .section .rodata\n" + " .align 4\n" + << LABEL( "sjt", state->id ) << ":\n"; + + for ( long long j = 0; j < numSingles; j++ ) { + /* Fill in gap between prev and this. */ + if ( j > 0 ) { + long long span = keyOps->span( data[j-1].lowKey, data[j].lowKey ) - 2; + for ( long long k = 0; k < span; k++ ) { + out << " .long " << def << " - " << + LABEL( "sjt", state->id ) << "\n"; + } + } + + out << " .long " << TRANS_GOTO_TARG( data[j].value ) << " - " << + LABEL( "sjt", state->id ) << "\n"; + } + + out << + " .text\n" + "" << LABEL( "sjf", state->id ) << ":\n"; +} + + +void AsmCodeGen::emitRangeBSearch( RedStateAp *state, int low, int high ) +{ + static int nl = 1; + + /* Get the mid position, staying on the lower end of the range. */ + int mid = (low + high) >> 1; + RedTransEl *data = state->outRange.data; + + /* Determine if we need to look higher or lower. */ + bool anyLower = mid > low; + bool anyHigher = mid < high; + + /* Determine if the keys at mid are the limits of the alphabet. */ + bool limitLow = keyOps->eq( data[mid].lowKey, keyOps->minKey ); + bool limitHigh = keyOps->eq( data[mid].highKey, keyOps->maxKey ); + +// string nf = TRANS_GOTO_TARG( state->defTrans ); + + /* For some reason the hop is faster and results in smaller code. Not sure + * why. */ + string nf = LABEL( "nf", state->id ); + + if ( anyLower && anyHigher ) { + int l1 = nl++; + string targ = TRANS_GOTO_TARG( data[mid].value ); + + /* Can go lower and higher than mid. */ + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n" + " jge " << LABEL( "nl", l1 ) << "\n"; + + + emitRangeBSearch( state, low, mid-1 ); + + out << + LABEL( "nl", l1 ) << ":\n"; + + if ( !keyOps->eq( data[mid].lowKey, data[mid].highKey ) ) { + out << + " cmpb " << KEY ( data[mid].highKey ) << ", %r10b\n"; + } + + out << + " jle " << targ << "\n"; + + emitRangeBSearch( state, mid+1, high ); + } + else if ( anyLower && !anyHigher ) { + + string targ; + if ( limitHigh ) + targ = TRANS_GOTO_TARG( data[mid].value ); + else + targ = LABEL( "nl", nl++ ); + + /* Can go lower than mid but not higher. */ + + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n" + " jge " << targ << "\n"; + + emitRangeBSearch( state, low, mid-1 ); + + /* If the higher is the highest in the alphabet then there is no sense + * testing it. */ + if ( !limitHigh ) { + + out << + targ << ":\n"; + + if ( ! keyOps->eq( data[mid].lowKey, data[mid].highKey ) ) { + out << + " cmpb " << KEY ( data[mid].highKey ) << ", %r10b\n"; + } + + out << + " jg " << nf << "\n"; + + TRANS_GOTO( data[mid].value ); + } + } + else if ( !anyLower && anyHigher ) { + string targ; + if ( limitLow ) + targ = TRANS_GOTO_TARG( data[mid].value ); + else + targ = LABEL( "nl", nl++ ); + + /* Can go higher than mid but not lower. */ + + out << + " cmpb " << KEY( data[mid].highKey ) << ", %r10b\n" + " jle " << targ << "\n"; + + emitRangeBSearch( state, mid+1, high ); + + /* If the lower end is the lowest in the alphabet then there is no + * sense testing it. */ + if ( !limitLow ) { + + out << + targ << ":\n"; + + if ( !keyOps->eq( data[mid].lowKey, data[mid].highKey ) ) { + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n"; + } + + out << + " jl " << nf << "\n"; + + TRANS_GOTO( data[mid].value ); + } + } + else { + /* Cannot go higher or lower than mid. It's mid or bust. What + * tests to do depends on limits of alphabet. */ + if ( !limitLow && !limitHigh ) { + + if ( !keyOps->eq( data[mid].lowKey, data[mid].highKey ) ) { + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n" + " jl " << nf << "\n" + " cmpb " << KEY( data[mid].highKey ) << ", %r10b\n" + " jg " << nf << "\n"; + } + else { + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n" + " jne " << nf << "\n"; + } + + TRANS_GOTO( data[mid].value ); + } + else if ( limitLow && !limitHigh ) { + + out << + " cmpb " << KEY( data[mid].highKey ) << ", %r10b\n" + " jg " << nf << "\n"; + + TRANS_GOTO( data[mid].value ); + } + else if ( !limitLow && limitHigh ) { + + out << + " cmpb " << KEY( data[mid].lowKey ) << ", %r10b\n" + " jl " << nf << "\n"; + + TRANS_GOTO( data[mid].value ); + } + else { + /* Both high and low are at the limit. No tests to do. */ + TRANS_GOTO( data[mid].value ); + } + } +} + +void AsmCodeGen::emitCharClassIfElseIf( RedStateAp *st ) +{ + long long span = st->high - st->low + 1; + for ( long long pos = 0; pos < span; pos++ ) { + out << + " cmpb " << KEY( st->low + pos ) << ", %r10b\n" + " je " << TRANS_GOTO_TARG( st->transList[pos] ) << "\n"; + } +} + +void AsmCodeGen::emitCharClassJumpTable( RedStateAp *st, string def ) +{ + long long low = st->low; + long long high = st->high; + + if ( def.size() == 0 ) + def = LABEL( "ccf", st->id ); + + out << + " movzbq %r10b, %rax\n" + " subq $" << low << ", %rax\n" + " cmpq $" << (high - low) << ", %rax\n" + " ja " << def << "\n" + " leaq " << LABEL( "cct", st->id ) << "(%rip), %rcx\n" + " movslq (%rcx,%rax,4), %rdx\n" + " addq %rcx, %rdx\n" + " jmp *%rdx\n" + " .section .rodata\n" + " .align 4\n" + << LABEL( "cct", st->id ) << ":\n"; + + long long span = st->high - st->low + 1; + for ( long long pos = 0; pos < span; pos++ ) { + out << " .long " << TRANS_GOTO_TARG( st->transList[pos] ) << " - " << + LABEL( "cct", st->id ) << "\n"; + } + + out << + " .text\n" + "" << LABEL( "ccf", st->id ) << ":\n"; +} + +void AsmCodeGen::NFA_PUSH( RedStateAp *st ) +{ + if ( st->nfaTargs != 0 && st->nfaTargs->length() > 0 ) { + if ( red->nfaPrePushExpr != 0 ) { + out << " movq $" << st->nfaTargs->length() << ", %rdi\n"; + INLINE_LIST( out, red->nfaPrePushExpr->inlineList, 0, false, false ); + } + + for ( RedNfaTargs::Iter t = *st->nfaTargs; t.lte(); t++ ) { + out << + " movq " << NFA_STACK() << ", %rax\n" + " movq " << NFA_TOP() << ", %rcx\n" + " imulq $24, %rcx\n" + " movq $" << t->state->id << ", 0(%rax,%rcx,)\n" + " movq " << P() << ", 8(%rax,%rcx,)\n"; + + out << + " # pop action id " << t->id << "\n" + " movq $" << t->id << ", 16(%rax,%rcx,)\n"; + + if ( t->push ) { + for ( GenActionTable::Iter item = t->push->key; item.lte(); item++ ) { + ACTION( out, item->value, st->id, false, + t->push->anyNextStmt() ); + out << "\n"; + } + } + + out << + " movq " << NFA_TOP() << ", %rcx\n" + " addq $1, %rcx\n" + " movq %rcx, " << NFA_TOP() << "\n"; + } + } +} + +void AsmCodeGen::STATE_GOTOS() +{ + bool eof = redFsm->anyEofActivity() || redFsm->anyNfaStates(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Writing code above state gotos. */ + IN_TRANS_ACTIONS( st ); + + if ( st->labelNeeded ) + out << LABEL( "st", st->id ) << ":\n"; + + + /* need to do this if the transition is an eof transition, or if the action + * contains fexec. Otherwise, no need. */ + if ( eof ) { + out << + " cmpq " << P() << ", " << vEOF() << "\n"; + + if ( st->isFinal ) + out << " je " << LABEL( "out", st->id ) << "\n"; + else + out << " je " << LABEL( "pop", st->id ) << "\n"; + } + + if ( st->toStateAction != 0 ) { + /* Remember that we wrote an action. Write every action in the list. */ + for ( GenActionTable::Iter item = st->toStateAction->key; item.lte(); item++ ) { + ACTION( out, item->value, st->id, false, + st->toStateAction->anyNextStmt() ); + out << "\n"; + } + } + + if ( st == redFsm->errState ) { + out << LABEL( "en", st->id ) << ":\n"; + + /* Break out here. */ + outLabelUsed = true; + + out << + " movq $" << st->id << ", " << vCS() << "\n" + " jmp " << LABEL( "pop" ) << "\n"; + } + else { + /* Advance and test buffer pos. */ + if ( st->labelNeeded ) { + out << + " addq $1, " << P() << "\n"; + + } + + /* This is the entry label for starting a run. */ + out << LABEL( "en", st->id ) << ":\n"; + + if ( !noEnd ) { + if ( eof ) { + out << + " cmpq " << P() << ", " << PE() << "\n" + " jne " << LABEL( "nope", st->id ) << "\n" << + " cmpq " << P() << ", " << vEOF() << "\n" + " jne " << LABEL( "out", st->id ) << "\n" << + LABEL( "nope", st->id ) << ":\n"; + } + else { + out << + " cmpq " << P() << ", " << PE() << "\n" + " je " << LABEL( "out", st->id ) << "\n"; + } + } + + NFA_PUSH( st ); + + if ( st->fromStateAction != 0 ) { + /* Remember that we wrote an action. Write every action in the list. */ + for ( GenActionTable::Iter item = st->fromStateAction->key; + item.lte(); item++ ) + { + ACTION( out, item->value, st->id, false, + st->fromStateAction->anyNextStmt() ); + out << "\n"; + } + } + + if ( !noEnd && eof ) { + out << + " cmpq " << P() << ", " << vEOF() << "\n" + " jne " << LABEL( "neofd", st->id ) << "\n"; + + if ( st->eofTrans != 0 ) + TRANS_GOTO( st->eofTrans ); + else { + if ( st->isFinal || !redFsm->anyNfaStates() ) + out << "jmp " << LABEL( "out", st->id ) << "\n"; + else + out << "jmp " << LABEL( "pop", st->id ) << "\n"; + } + + out << + " jmp " << LABEL( "deofd", st->id ) << "\n"; + + out << LABEL( "neofd", st->id ) << ":\n"; + } + + /* Record the prev state if necessary. */ + if ( st->anyRegCurStateRef() ) { + out << + " movq $" << st->id << ", -72(%rbp)\n"; + } + + +#ifdef LOG_TRANS + out << + " movzbl (" << P() << "), %r10d\n" + " movq $" << machineId << ", %rdi\n" + " movq $" << st->id << ", %rsi\n" + " movslq %r10d, %rdx\n" + " call " << LABEL( "log_trans" ) << "\n" + ; +#endif + + /* Load *p. */ + if ( st->transList != 0 ) { + long lowKey = redFsm->lowKey.getVal(); + long highKey = redFsm->highKey.getVal(); + + out << + " movzbl (" << P() << "), %r10d\n" + " cmpl $" << lowKey << ", %r10d\n" + " jl " << LABEL( "nf", st->id ) << "\n" + " cmpl $" << highKey << ", %r10d\n" + " jg " << LABEL( "nf", st->id ) << "\n" + " subl " << KEY( lowKey ) << ", %r10d\n" + " leaq " << LABEL( "char_class" ) << "(%rip), %rcx\n" + " movslq %r10d, %rax\n" + " movb (%rcx, %rax), %r10b\n" + ; + + + long len = ( st->high - st->low + 1 ); + + if ( len < 8 ) + emitCharClassIfElseIf( st ); + else { + string def; + if ( st->outRange.length() == 0 ) + def = TRANS_GOTO_TARG( st->defTrans ); + emitCharClassJumpTable( st, def ); + } + } + + /* Write the default transition. */ + out << LABEL( "nf", st->id ) << ":\n"; + TRANS_GOTO( st->defTrans ); + + if ( !noEnd && eof ) { + out << LABEL( "deofd", st->id) << ":\n"; + } + } + } +} + +unsigned int AsmCodeGen::TO_STATE_ACTION( RedStateAp *state ) +{ + int act = 0; + if ( state->toStateAction != 0 ) + act = state->toStateAction->location+1; + return act; +} + +unsigned int AsmCodeGen::FROM_STATE_ACTION( RedStateAp *state ) +{ + int act = 0; + if ( state->fromStateAction != 0 ) + act = state->fromStateAction->location+1; + return act; +} + +unsigned int AsmCodeGen::EOF_ACTION( RedStateAp *state ) +{ + int act = 0; + if ( state->eofAction != 0 ) + act = state->eofAction->location+1; + return act; +} + +bool AsmCodeGen::useAgainLabel() +{ + return redFsm->anyActionRets() || + redFsm->anyActionByValControl() || + redFsm->anyRegNextStmt(); +} + +void AsmCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish ) +{ + ret << + " jmp " << LABEL( "st", gotoDest ) << "\n"; +} + +void AsmCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish ) +{ + if ( red->prePushExpr != 0 ) + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + + ret << + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " movq $" << targState << ", (%rax, %rcx, 8)\n" + " addq $1, %rcx\n" + " movq %rcx, " << TOP() << "\n" + ; + + ret << + " jmp " << LABEL( "st", callDest ) << "\n"; + ; +} + +void AsmCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish ) +{ + if ( red->prePushExpr != 0 ) + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + + ret << + "\n" + " movq "; + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << ", %rdx\n" + "\n" + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " movq $" << targState << ", (%rax, %rcx, 8)\n" + " addq $1, %rcx\n" + " movq %rcx, " << TOP() << "\n" + " movq %rdx, " << vCS() << "\n" + ; + + ret << + " jmp " << LABEL( "again" ) << "\n"; +} + +void AsmCodeGen::RET( ostream &ret, bool inFinish ) +{ + ret << + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " subq $1, %rcx\n" + " movq (%rax, %rcx, 8), %rax\n" + " movq %rax, " << vCS() << "\n" + " movq %rcx, " << TOP() << "\n"; + + if ( red->postPopExpr != 0 ) + INLINE_LIST( ret, red->postPopExpr->inlineList, 0, false, false ); + + ret << + " jmp " << LABEL("again") << "\n"; +} + +void AsmCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish ) +{ + ret << " movq "; + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << ", " << vCS() << "\n"; + + ret << + " jmp " << LABEL("again") << "\n"; +} + +void AsmCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish ) +{ + ret << + " movq $" << nextDest << ", " << vCS() << "\n"; +} + +void AsmCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish ) +{ + ret << " movq "; + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << ", " << vCS() << "\n"; +} + +void AsmCodeGen::NCALL( ostream &ret, int callDest, int targState, bool inFinish ) +{ + if ( red->prePushExpr != 0 ) + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + + ret << + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " movq $" << targState << ", (%rax, %rcx, 8)\n" + " addq $1, %rcx\n" + " movq %rcx, " << TOP() << "\n" + " movq $" << callDest << ", " << vCS() << "\n"; +} + +void AsmCodeGen::NCALL_EXPR( ostream &ret, GenInlineItem *ilItem, + int targState, bool inFinish ) +{ + if ( red->prePushExpr != 0 ) + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + + ret << + "\n" + " movq "; + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << ", %rdx\n" + "\n" + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " movq $" << targState << ", (%rax, %rcx, 8)\n" + " addq $1, %rcx\n" + " movq %rcx, " << TOP() << "\n" + " movq %rdx, " << vCS() << "\n"; +} + +void AsmCodeGen::NRET( ostream &ret, bool inFinish ) +{ + ret << + " movq " << STACK() << ", %rax\n" + " movq " << TOP() << ", %rcx\n" + " subq $1, %rcx\n" + " movq (%rax, %rcx, 8), %rax\n" + " movq %rax, " << vCS() << "\n" + " movq %rcx, " << TOP() << "\n"; + + if ( red->postPopExpr != 0 ) + INLINE_LIST( ret, red->postPopExpr->inlineList, 0, false, false ); +} + +void AsmCodeGen::CURS( ostream &ret, bool inFinish ) +{ + ret << + " movq -72(%rbp), %rax\n"; +} + +void AsmCodeGen::TARGS( ostream &ret, bool inFinish, int targState ) +{ + ret << + " movq $" << targState << ", %rax\n"; +} + +void AsmCodeGen::BREAK( ostream &ret, int targState, bool csForced ) +{ + outLabelUsed = true; + ret << "{" << P() << "++; "; + if ( !csForced ) + ret << vCS() << " = " << targState << "; "; + ret << CTRL_FLOW() << "goto _out;}"; +} + +bool AsmCodeGen::IN_TRANS_ACTIONS( RedStateAp *state ) +{ + bool anyWritten = false; + + /* Emit any transitions that have actions and that go to this state. */ + for ( int it = 0; it < state->numInCondTests; it++ ) { + /* Write the label for the transition so it can be jumped to. */ + RedTransAp *trans = state->inCondTests[it]; + out << LABEL( "ctr", trans->id ) << ":\n"; + + if ( trans->condSpace->condSet.length() == 1 ) { + RedCondPair *tp, *fp; + if ( trans->numConds() == 1 ) { + /* The single condition is either false or true, errCond is the + * opposite. */ + if ( trans->outCondKey(0) == 0 ) { + fp = trans->outCond(0); + tp = trans->errCond(); + } + else { + tp = trans->outCond(0); + fp = trans->errCond(); + } + } + else { + /* Full list, goes false, then true. */ + fp = trans->outCond(0); + tp = trans->outCond(1); + } + + GenCondSet::Iter csi = trans->condSpace->condSet; + CONDITION( out, *csi ); + + out << + " test %eax, %eax\n" + " je " << TRANS_GOTO_TARG( fp ) << "\n" + " jmp " << TRANS_GOTO_TARG( tp ) << "\n"; + } + else { + out << " movq $0, %r9\n"; + + for ( GenCondSet::Iter csi = trans->condSpace->condSet; csi.lte(); csi++ ) { + out << + " pushq %r9\n"; + + CONDITION( out, *csi ); + out << + "\n" + " test %eax, %eax\n" + " setne %cl\n" + " movsbq %cl, %rcx\n" + " salq $" << csi.pos() << ", %rcx\n" + " popq %r9\n" + " addq %rcx, %r9\n"; + } + + for ( int c = 0; c < trans->numConds(); c++ ) { + CondKey key = trans->outCondKey( c ); + RedCondPair *pair = trans->outCond( c ); + out << + " cmpq " << COND_KEY( key ) << ", %r9\n" + " je " << TRANS_GOTO_TARG( pair ) << "\n"; + + } + + RedCondPair *err = trans->errCond(); + if ( err != 0 ) { + out << + " jmp " << TRANS_GOTO_TARG( err ) << "\n"; + } + } + } + + /* Emit any transitions that have actions and that go to this state. */ + for ( int it = 0; it < state->numInConds; it++ ) { + RedCondPair *pair = state->inConds[it]; + if ( pair->action != 0 /* && pair->labelNeeded */ ) { + /* Remember that we wrote an action so we know to write the + * line directive for going back to the output. */ + anyWritten = true; + + /* Write the label for the transition so it can be jumped to. */ + out << LABEL( "tr", pair->id ) << ":\n"; + + /* If the action contains a next, then we must preload the current + * state since the action may or may not set it. */ + if ( pair->action->anyNextStmt() ) { + out << + " movq $" << pair->targ->id << ", " << vCS() << "\n"; + } + + if ( redFsm->anyRegNbreak() ) { + out << + " movb $0, " << NBREAK() << "\n"; + } + + /* Write each action in the list. */ + for ( GenActionTable::Iter item = pair->action->key; item.lte(); item++ ) { + ACTION( out, item->value, pair->targ->id, false, + pair->action->anyNextStmt() ); + out << "\n"; + } + + if ( redFsm->anyRegNbreak() ) { + out << + " cmpb $0, " << NBREAK() << "\n" + " jne " << LABEL( "pop" ) << "\n"; + outLabelUsed = true; + } + + + /* If the action contains a next then we need to reload, otherwise + * jump directly to the target state. */ + if ( pair->action->anyNextStmt() ) + out << " jmp " << LABEL( "again" ) << "\n"; + else + out << " jmp " << LABEL( "st", pair->targ->id ) << "\n"; + } + } + + return anyWritten; +} + +std::string AsmCodeGen::TRANS_GOTO_TARG( RedCondPair *pair ) +{ + std::stringstream s; + if ( pair->action != 0 ) { + /* Go to the transition which will go to the state. */ + s << LABEL( "tr", pair->id ); + } + else { + /* Go directly to the target state. */ + s << LABEL( "st", pair->targ->id ); + } + return s.str(); +} + +std::string AsmCodeGen::TRANS_GOTO_TARG( RedTransAp *trans ) +{ + if ( trans->condSpace != 0 ) { + /* Need to jump to the trans since there are conditions. */ + return LABEL( "ctr", trans->id ); + } + else { + return TRANS_GOTO_TARG( &trans->p ); + } +} + +/* Emit the goto to take for a given transition. */ +std::ostream &AsmCodeGen::TRANS_GOTO( RedTransAp *trans ) +{ + out << " jmp " << TRANS_GOTO_TARG( trans ) << "\n"; + return out; +} + +std::ostream &AsmCodeGen::EXIT_STATES() +{ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + out << + LABEL( "out", st->id ) << ":\n" + " movq $" << st->id << ", " << vCS() << "\n" + " jmp " << LABEL( "out" ) << "\n"; + + out << + LABEL( "pop", st->id ) << ":\n" + " movq $" << st->id << ", " << vCS() << "\n" + " jmp " << LABEL( "pop" ) << "\n"; + } + return out; +} + +std::ostream &AsmCodeGen::AGAIN_CASES() +{ + /* Jump into the machine based on the current state. */ + out << + " leaq " << LABEL( "again_jmp" ) << "(%rip), %rcx\n"; + + if ( stackCS ) { + out << + " movq " << vCS() << ", %r11\n"; + } + + out << + " movq (%rcx,%r11,8), %rcx\n" + " jmp *%rcx\n" + " .section .rodata\n" + " .align 8\n" + << LABEL( "again_jmp" ) << ":\n"; + + for ( int stId = 0; stId < redFsm->stateList.length(); stId++ ) { + out << + " .quad " << LABEL( "st", stId ) << "\n"; + } + + out << + " .text\n"; + + return out; +} + +std::ostream &AsmCodeGen::ENTRY_CASES() +{ + out << + " movq (%rcx,%r11,8), %rcx\n" + " jmp *%rcx\n" + " .section .rodata\n" + " .align 8\n" + << LABEL( "entry_jmp" ) << ":\n"; + + for ( int stId = 0; stId < redFsm->stateList.length(); stId++ ) { + out << + " .quad " << LABEL( "en", stId ) << "\n"; + } + + out << + " .text\n"; + return out; +} + + +std::ostream &AsmCodeGen::FINISH_CASES() +{ + /* The current state is in %rax. */ + /*long done = */ nextLmSwitchLabel++; + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + out << + " cmpq $" << st->id << ", %rax\n" + " jne " << LABEL( "fc", st->id ) << "\n"; + + if ( st->fromStateAction != 0 ) { + /* Remember that we wrote an action. Write every action in the list. */ + for ( GenActionTable::Iter item = st->fromStateAction->key; + item.lte(); item++ ) + { + ACTION( out, item->value, st->id, false, + st->fromStateAction->anyNextStmt() ); + out << "\n"; + } + } + + out << + " jmp " << TRANS_GOTO_TARG( st->eofTrans ) << "\n" << + LABEL( "fc", st->id ) << ":\n"; + } + } + + return out; +} + +void AsmCodeGen::setLabelsNeeded( GenInlineList *inlineList ) +{ + for ( GenInlineList::Iter item = *inlineList; item.lte(); item++ ) { + switch ( item->type ) { + case GenInlineItem::Goto: case GenInlineItem::Call: { + /* Mark the target as needing a label. */ + item->targState->labelNeeded = true; + break; + } + default: break; + } + + if ( item->children != 0 ) + setLabelsNeeded( item->children ); + } +} + +void AsmCodeGen::setLabelsNeeded( RedCondPair *pair ) +{ + /* If there is no action with a next statement, then the label will be + * needed. */ + if ( pair->action == 0 || !pair->action->anyNextStmt() ) + pair->targ->labelNeeded = true; + + /* Need labels for states that have goto or calls in action code + * invoked on characters (ie, not from out action code). */ + if ( pair->action != 0 ) { + /* Loop the actions. */ + for ( GenActionTable::Iter act = pair->action->key; act.lte(); act++ ) { + /* Get the action and walk it's tree. */ + setLabelsNeeded( act->value->inlineList ); + } + } +} + +/* Set up labelNeeded flag for each state. */ +void AsmCodeGen::setLabelsNeeded() +{ + /* If we use the _again label, then we the _again switch, which uses all + * labels. */ + if ( useAgainLabel() ) { + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + st->labelNeeded = true; + } + else { + /* Do not use all labels by default, init all labelNeeded vars to false. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + st->labelNeeded = false; + + for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) { + if ( trans->condSpace == 0 ) + setLabelsNeeded( &trans->p ); + } + + for ( CondApSet::Iter cond = redFsm->condSet; cond.lte(); cond++ ) + setLabelsNeeded( &cond->p ); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofAction != 0 ) { + for ( GenActionTable::Iter item = st->eofAction->key; item.lte(); item++ ) + setLabelsNeeded( item->value->inlineList ); + } + } + } + + if ( !noEnd ) { + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + st->outNeeded = st->labelNeeded; + } +} + +void AsmCodeGen::writeData() +{ + STATE_IDS(); + + long long maxSpan = keyOps->span( redFsm->lowKey, redFsm->highKey ); + + out << + " .type " << LABEL( "char_class" ) << ", @object\n" << + LABEL( "char_class" ) << ":\n"; + + for ( long long pos = 0; pos < maxSpan; pos++ ) { + out << + " .byte " << redFsm->classMap[pos] << "\n"; + } + +#ifdef LOG_TRANS + out << + LABEL( "fmt_log_trans" ) << ":\n" + " .string \"%i %i %i\\n\"\n"; +#endif +} + +void AsmCodeGen::setNfaIds() +{ + long nextId = 1; + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs != 0 ) { + for ( RedNfaTargs::Iter targ = *st->nfaTargs; targ.lte(); targ++ ) { + targ->id = nextId; + nextId += 1; + } + } + } +} + +void AsmCodeGen::writeExec() +{ + /* Must set labels immediately before writing because we may depend on the + * noend write option. */ + setLabelsNeeded(); + testEofUsed = false; + outLabelUsed = false; + + setNfaIds(); + + /* If there are eof actions then we need to run code after exporting the + * final state to vCS. Since the interface register is calee-save, we need + * it to live on the stack. */ + stackCS = redFsm->anyEofActivity(); + + /* + * This code needs 88 bytes of stack (offset 0 from %rbp). + * + * cv : %r9 -- caller-save, used internally, condition char, undefined in + * conditions and actions, can use + * + * pc : %r10b -- caller-save, used internally, undefined in conditions + * actions, can use + * + * cs : %r11 -- caller-save, written by write init, read and + * written by exec, undefined in conditions and actions + * + * p : %r12 -- callee-save, interface, persistent + * + * pe : %r13 -- callee-save, interface, persistent + * + * eof: -8(%rbp) + * + * ts: -16(%rbp) + * + * te: -24(%rbp) + * + * act: -32(%rbp) + * + * _nbreak: -40(%rbp) + * + * stackCS: -48(%rbp) + * + * stack: -56(%rbp) + * top: -64(%rbp) + * + * _ps: -72(%rbp) + * + * nfa_stack -80(%rbp) + * nfa_top -88(%rbp) + * nfa_sz -96(%rbp) + */ + + if ( redFsm->anyRegCurStateRef() ) { + out << + " movq $0, -72(%rbp)\n"; + } + + if ( stackCS ) { + /* Only need a persistent cs in the case of eof actions when exiting the + * block. Where CS lives is a matter of performance though, so we should + * only do this if necessary. */ + out << + " movq %r11, " << vCS() << "\n"; + } + + if ( useAgainLabel() ) { + out << + " jmp " << LABEL( "resume" ) << "\n" + << LABEL( "again" ) << ":\n"; + + AGAIN_CASES(); + } + + if ( useAgainLabel() || redFsm->anyNfaStates() ) + out << LABEL( "resume" ) << ":\n"; + + /* Jump into the machine based on the current state. */ + out << + " leaq " << LABEL( "entry_jmp" ) << "(%rip), %rcx\n"; + + if ( stackCS ) { + out << + " movq " << vCS() << ", %r11\n"; + } + + ENTRY_CASES(); + + STATE_GOTOS(); + + EXIT_STATES(); + + out << LABEL( "pop" ) << ":\n"; + + if ( redFsm->anyNfaStates() ) { + out << + " movq " << NFA_TOP() << ", %rcx\n" + " cmpq $0, %rcx\n" + " je " << LABEL( "nfa_stack_empty" ) << "\n" + " movq " << NFA_TOP() << ", %rcx\n" + " subq $1, %rcx\n" + " movq %rcx, " << NFA_TOP() << "\n" + " movq " << NFA_STACK() << ", %rax\n" + " imulq $24, %rcx\n" + " movq 0(%rax,%rcx,), %r11\n" + " movq 8(%rax,%rcx,), " << P() << "\n" + " movq %r11, " << vCS() << "\n" + ; + + if ( redFsm->bAnyNfaPops ) { + out << + " movq %r11, %r14\n" + " movq 16(%rax,%rcx,), %rax\n"; + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs != 0 ) { + for ( RedNfaTargs::Iter targ = *st->nfaTargs; targ.lte(); targ++ ) { + + /* Write the entry label. */ + out << + " # pop action select\n" + " cmp $" << targ->id << ", %rax\n" + " jne 100f\n"; + + if ( targ->popTest != 0 ) { + /* Write each action in the list of action items. */ + for ( GenActionTable::Iter item = targ->popTest->key; item.lte(); item++ ) + NFA_CONDITION( out, item->value, item.last() ); + } + + out << + " jmp 101f\n" + "100:\n"; + + } + } + } + + out << + "101:\n" + " movq %r14, %r11\n"; + } + + out << + " jmp " << LABEL( "resume" ) << "\n" << + LABEL( "pop_fail" ) << ":\n" + " movq $" << ERROR_STATE() << ", " << vCS() << "\n" + " jmp " << LABEL( "resume" ) << "\n" << + LABEL( "nfa_stack_empty" ) << ":\n"; + } + + if ( stackCS ) { + out << + " movq " << vCS() << ", %r11\n"; + } + + out << + "# WRITE EXEC END\n"; + + out << LABEL( "out" ) << ":\n"; + + if ( stackCS ) { + out << + " movq " << vCS() << ", %r11\n"; + } + +#ifdef LOG_TRANS + out << + " jmp " << LABEL( "skip" ) << "\n" << + LABEL( "log_trans" ) << ":\n" + " movq %rdx, %rcx\n" + " movq %rsi, %rdx\n" + " movq %rdi, %rsi\n" + " movq " << LABEL( "fmt_log_trans" ) << "@GOTPCREL(%rip), %rdi\n" + " movq $0, %rax\n" + " call printf@PLT\n" + " ret\n" << + LABEL( "skip" ) << ":\n" + "\n"; +#endif +} |