From e3cb0f8facec3723a8e0f6f245c7688cf3da8804 Mon Sep 17 00:00:00 2001 From: Andreas Baumann Date: Thu, 23 Sep 2021 19:05:07 +0200 Subject: cc - proper Pratt parsing of expressions - fixed some register saving around divs and muls --- miniany/cc.c | 175 ++++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 118 insertions(+), 57 deletions(-) (limited to 'miniany/cc.c') diff --git a/miniany/cc.c b/miniany/cc.c index ccda806..4d26893 100644 --- a/miniany/cc.c +++ b/miniany/cc.c @@ -17,8 +17,8 @@ enum { S_INT = 10, S_IDENT = 20, S_NUM = 30, - S_ERR = 40, - S_EOI = 41 + S_EOI = 98, + S_ERR = 99 }; struct Scanner { @@ -340,15 +340,16 @@ enum { A_SUBTRACT, A_MULTIPLY, A_DIVIDE, - A_ASSIGN + A_ASSIGN, + A_ERR = 99 }; struct ASTnode { - int op; - struct ASTnode *left; - struct ASTnode *right; - int intval; /* for A_INT_LITERAL */ - struct Symbol *sym; /* for A_IDENT */ + int op; /* node operation, one of the A_ enums */ + struct ASTnode *left; /* left side operand */ + struct ASTnode *right; /* right side operand (or empty for unary operations */ + int intval; /* value in case of A_INT_LITERAL */ + struct Symbol *sym; /* symbol in case of A_IDENT */ }; struct ASTnode *createASTnode( int op, struct ASTnode *left, struct ASTnode *right, int intval, struct Symbol *sym ) @@ -391,7 +392,7 @@ void freeASTnode( struct ASTnode *node ) free( (char *)node ); } -/* parser/compiler, no forward definitions */ +/* parser/compiler, no forward declarations */ struct Parser { int token; @@ -399,6 +400,14 @@ struct Parser { struct Scope *global_scope; }; +struct Generator { + struct Scanner *scanner; + char **regName; /* names of the registers */ + int *regFree; /* free registers */ + int spillReg; /* index of the current spilled register */ + int debug; /* adds debug output to generated assembly */ +}; + struct Compiler { struct Parser *parser; struct Generator *generator; @@ -416,14 +425,6 @@ enum { NOREG = -1 }; -struct Generator { - struct Scanner *scanner; - char **regName; - int *regFree; - int spillReg; - int debug; -}; - struct Generator *createGenerator( struct Scanner *scanner ) { struct Generator *generator; @@ -650,8 +651,10 @@ int genMul( struct Generator *generator, int leftreg, int rightreg ) if( leftreg == EAX ) { reg = genBinary( "mul", generator, leftreg, rightreg, 1 ); } else { - genSaveReg( generator, EAX ); - if( leftreg != EDX ) { + if( !generator->regFree[EAX] ) { + genSaveReg( generator, EAX ); + } + if( leftreg != EDX && !generator->regFree[EDX] ) { genSaveReg( generator, EDX ); } if( rightreg == EAX ) { @@ -672,10 +675,12 @@ int genMul( struct Generator *generator, int leftreg, int rightreg ) putreg( generator, leftreg ); putstring( ", eax" ); putnl( ); - if( leftreg != EDX ) { + if( leftreg != EDX && !generator->regFree[EDX] ) { genRestoreReg( generator, EDX ); } - genRestoreReg( generator, EAX ); + if( !generator->regFree[EAX] ) { + genRestoreReg( generator, EAX ); + } reg = leftreg; } @@ -689,8 +694,12 @@ int genDiv( struct Generator *generator, int leftreg, int rightreg ) if( leftreg == EAX ) { reg = genBinary( "div", generator, leftreg, rightreg, 1 ); } else { - genSaveReg( generator, EAX ); - genSaveReg( generator, EDX ); + if( !generator->regFree[EAX] ) { + genSaveReg( generator, EAX ); + } + if( !generator->regFree[EDX] ) { + genSaveReg( generator, EDX ); + } if( rightreg == EAX ) { genSaveReg( generator, EBX ); putstring( "mov ebx, eax" ); @@ -711,8 +720,12 @@ int genDiv( struct Generator *generator, int leftreg, int rightreg ) putreg( generator, leftreg ); putstring( ", eax" ); putnl( ); - genRestoreReg( generator, EDX ); - genRestoreReg( generator, EAX ); + if( !generator->regFree[EDX] ) { + genRestoreReg( generator, EDX ); + } + if( !generator->regFree[EAX] ) { + genRestoreReg( generator, EAX ); + } reg = leftreg; } @@ -823,10 +836,71 @@ void parserExpect( struct Parser *parser, int must, char *what ) } } -struct ASTnode *parseExpression( struct Parser *parser ) +int parserTokenToOperator( struct Parser *parser, int token ) { - struct ASTnode *node, *left, *right; + int op; + + op = A_ERR; + switch( token ) { + case S_STAR: + op = A_MULTIPLY; + break; + + case S_SLASH: + op = A_DIVIDE; + break; + + case S_PLUS: + op = A_ADD; + break; + + case S_MINUS: + op = A_SUBTRACT; + break; + + default: + scannerPrintErrorHeader( parser->scanner ); + putstring( "unknown operator token for token " ); + putint( token ); + putnl( ); + exit( EXIT_FAILURE ); + } + + return op; +} + +int parserOperatorPrecedence( struct Parser *parser, int operator ) +{ + int precedence; + + precedence = 0; + switch( operator ) { + case A_MULTIPLY: + case A_DIVIDE: + precedence = 2; + break; + + case A_ADD: + case A_SUBTRACT: + precedence = 1; + break; + + default: + scannerPrintErrorHeader( parser->scanner ); + putstring( "unknown operator precedence for operator " ); + putint( operator ); + putnl( ); + exit( EXIT_FAILURE ); + } + + return precedence; +} + +struct ASTnode *parseExpression( struct Parser *parser, int level ) +{ + struct ASTnode *left, *right; struct Symbol *sym; + int op; if( parser->token == S_EOI ) { scannerPrintErrorHeader( parser->scanner ); @@ -846,7 +920,7 @@ struct ASTnode *parseExpression( struct Parser *parser ) putstring( "' in expression" ); putnl( ); exit( EXIT_FAILURE ); - } + } left = createASTleafSym( A_IDENT, sym ); } else { left = NULL; @@ -859,35 +933,22 @@ struct ASTnode *parseExpression( struct Parser *parser ) } parser->token = getToken( parser->scanner ); - if( parser->token == S_PLUS ) { - parser->token = getToken( parser->scanner ); - right = parseExpression( parser ); - node = createASTbinary( A_ADD, left, right ); - } else if( parser->token == S_MINUS ) { - parser->token = getToken( parser->scanner ); - right = parseExpression( parser ); - node = createASTbinary( A_SUBTRACT, left, right ); - } else if( parser->token == S_STAR ) { - parser->token = getToken( parser->scanner ); - right = parseExpression( parser ); - node = createASTbinary( A_MULTIPLY, left, right ); - } else if( parser->token == S_SLASH ) { + if( parser->token == S_EOI || parser->token == S_SEMICOLON ) { + return left; + } + + op = parserTokenToOperator( parser, parser->token ); + while( parserOperatorPrecedence( parser, op ) > level ) { parser->token = getToken( parser->scanner ); - right = parseExpression( parser ); - node = createASTbinary( A_DIVIDE, left, right ); - } else if( parser->token == S_EOI || parser->token == S_SEMICOLON ) { - node = left; - } else { - node = NULL; - scannerPrintErrorHeader( parser->scanner ); - putstring( "unexpected token '" ); - putint( parser->token ); - putstring( "' in expression" ); - putnl( ); - exit( EXIT_FAILURE ); + right = parseExpression( parser, parserOperatorPrecedence( parser, op ) ); + left = createASTbinary( op, left, right ); + if( parser->token == S_EOI || parser->token == S_SEMICOLON ) { + return left; + } + op = parserTokenToOperator( parser, parser->token ); } - return node; + return left; } void parseDeclaration( struct Compiler *compiler ) @@ -932,7 +993,7 @@ void parseAssignment( struct Compiler *compiler ) } right = createASTleafSym( A_LVIDENT, sym ); parserExpect( parser, S_EQUALS, "=" ); - left = parseExpression( parser ); + left = parseExpression( parser, 0 ); parserExpect( parser, S_SEMICOLON, ";" ); node = createASTbinary( A_ASSIGN, left, right ); @@ -989,8 +1050,8 @@ int main( int argc, char **argv ) struct Compiler *compiler; compiler = createCompiler( ); -/* compiler->parser->scanner->debug = 1; */ -/* compiler->generator->debug = 1; */ + /* compiler->parser->scanner->debug = 1; */ + /* compiler->generator->debug = 1; */ genPrologue( compiler ); compiler->parser->token = getToken( compiler->parser->scanner ); while( compiler->parser->token != S_EOI ) { -- cgit v1.2.3-54-g00ecf