/* * tcode.c -- translator functions for traversing parse trees and generating * code. */ #include "..\h\config.h" #include "general.h" #include "tproto.h" #include "globals.h" #include "trans.h" #include "token.h" #include "tree.h" #include "tsym.h" /* * Prototypes. */ hidden int alclab Params((int n)); hidden novalue binop Params((int op)); hidden novalue emit Params((char *s)); hidden novalue emitl Params((char *s,int a)); hidden novalue emitlab Params((int l)); hidden novalue emitn Params((char *s,int a)); hidden novalue emits Params((char *s,char *a)); hidden novalue setloc Params((nodeptr n)); hidden int traverse Params((nodeptr t)); hidden novalue unopa Params((int op, nodeptr t)); hidden novalue unopb Params((int op)); extern int tfatals; extern int nocode; extern char *comfile; /* * Code generator parameters. */ #define LoopDepth 20 /* max. depth of nested loops */ #define CaseDepth 10 /* max. depth of nested case statements */ #define CreatDepth 10 /* max. depth of nested create statements */ /* * loopstk structures hold information about nested loops. */ struct loopstk { int nextlab; /* label for next exit */ int breaklab; /* label for break exit */ int markcount; /* number of marks */ int ltype; /* loop type */ }; /* * casestk structure hold information about case statements. */ struct casestk { int endlab; /* label for exit from case statement */ nodeptr deftree; /* pointer to tree for default clause */ }; /* * creatstk structures hold information about create statements. */ struct creatstk { int nextlab; /* previous value of nextlab */ int breaklab; /* previous value of breaklab */ }; static int nextlab; /* next label allocated by alclab() */ /* * codegen - traverse tree t, generating code. */ novalue codegen(t) nodeptr t; { nextlab = 1; traverse(t); } /* * traverse - traverse tree rooted at t and generate code. This is just * plug and chug code for each of the node types. */ static int traverse(t) register nodeptr t; { register int lab, n, i; struct loopstk loopsave; static struct loopstk loopstk[LoopDepth]; /* loop stack */ static struct loopstk *loopsp; static struct casestk casestk[CaseDepth]; /* case stack */ static struct casestk *casesp; static struct creatstk creatstk[CreatDepth]; /* create stack */ static struct creatstk *creatsp; n = 1; switch (TType(t)) { case N_Activat: /* co-expression activation */ if (Val0(Tree0(t)) == AUGACT) { emit("pnull"); } traverse(Tree2(t)); /* evaluate result expression */ if (Val0(Tree0(t)) == AUGACT) emit("sdup"); traverse(Tree1(t)); /* evaluate activate expression */ setloc(t); emit("coact"); if (Val0(Tree0(t)) == AUGACT) emit("asgn"); break; case N_Alt: /* alternation */ lab = alclab(2); emitl("mark", lab); loopsp->markcount++; traverse(Tree0(t)); /* evaluate first alternative */ loopsp->markcount--; emit("esusp"); /* and suspend with its result */ emitl("goto", lab+1); emitlab(lab); traverse(Tree1(t)); /* evaluate second alternative */ emitlab(lab+1); break; case N_Augop: /* augmented assignment */ case N_Binop: /* or a binary operator */ emit("pnull"); traverse(Tree1(t)); if (TType(t) == N_Augop) emit("dup"); traverse(Tree2(t)); setloc(t); binop((int)Val0(Tree0(t))); break; case N_Bar: /* repeated alternation */ lab = alclab(1); emitlab(lab); emit("mark0"); /* fail if expr fails first time */ loopsp->markcount++; traverse(Tree0(t)); /* evaluate first alternative */ loopsp->markcount--; emitl("chfail", lab); /* change to loop on failure */ emit("esusp"); /* suspend result */ break; case N_Break: /* break expression */ if (loopsp->breaklab <= 0) nfatal(t, "invalid context for break"); else { for (i = 0; i < loopsp->markcount; i++) emit("unmark"); loopsave = *loopsp--; traverse(Tree0(t)); *++loopsp = loopsave; emitl("goto", loopsp->breaklab); } break; case N_Case: /* case expression */ lab = alclab(1); casesp++; casesp->endlab = lab; casesp->deftree = NULL; emit("mark0"); loopsp->markcount++; traverse(Tree0(t)); /* evaluate control expression */ loopsp->markcount--; emit("eret"); traverse(Tree1(t)); /* do rest of case (CLIST) */ if (casesp->deftree != NULL) { /* evaluate default clause */ emit("pop"); traverse(casesp->deftree); } else emit("efail"); emitlab(lab); /* end label */ casesp--; break; case N_Ccls: /* case expression clause */ if (TType(Tree0(t)) == N_Res && /* default clause */ Val0(Tree0(t)) == DEFAULT) { if (casesp->deftree != NULL) nfatal(t, "more than one default clause"); else casesp->deftree = Tree1(t); } else { /* case clause */ lab = alclab(1); emitl("mark", lab); loopsp->markcount++; emit("ccase"); traverse(Tree0(t)); /* evaluate selector */ setloc(t); emit("eqv"); loopsp->markcount--; emit("unmark"); emit("pop"); traverse(Tree1(t)); /* evaluate expression */ emitl("goto", casesp->endlab); /* goto end label */ emitlab(lab); /* label for next clause */ } break; case N_Clist: /* list of case clauses */ traverse(Tree0(t)); traverse(Tree1(t)); break; case N_Conj: /* conjunction */ if (Val0(Tree0(t)) == AUGAND) { emit("pnull"); } traverse(Tree1(t)); if (Val0(Tree0(t)) != AUGAND) emit("pop"); traverse(Tree2(t)); if (Val0(Tree0(t)) == AUGAND) { setloc(t); emit("asgn"); } break; case N_Create: /* create expression */ creatsp++; creatsp->nextlab = loopsp->nextlab; creatsp->breaklab = loopsp->breaklab; loopsp->nextlab = 0; /* make break and next illegal */ loopsp->breaklab = 0; lab = alclab(3); emitl("goto", lab+2); /* skip over code for co-expression */ emitlab(lab); /* entry point */ emit("pop"); /* pop the result from activation */ emitl("mark", lab+1); loopsp->markcount++; traverse(Tree0(t)); /* traverse code for co-expression */ loopsp->markcount--; setloc(t); emit("coret"); /* return to activator */ emit("efail"); /* drive co-expression */ emitlab(lab+1); /* loop on exhaustion */ emit("cofail"); /* and fail each time */ emitl("goto", lab+1); emitlab(lab+2); emitl("create", lab); /* create entry block */ loopsp->nextlab = creatsp->nextlab; /* legalize break and next */ loopsp->breaklab = creatsp->breaklab; creatsp--; break; case N_Cset: /* cset literal */ emitn("cset", (int)Val0(t)); break; case N_Elist: /* expression list */ n = traverse(Tree0(t)); n += traverse(Tree1(t)); break; case N_Empty: /* a missing expression */ emit("pnull"); break; case N_Field: /* field reference */ emit("pnull"); traverse(Tree0(t)); setloc(t); emits("field", Str0(Tree1(t))); break; case N_Id: /* identifier */ emitn("var", (int)Val0(t)); break; case N_If: /* if expression */ if (TType(Tree2(t)) == N_Empty) { lab = 0; emit("mark0"); } else { lab = alclab(2); emitl("mark", lab); } loopsp->markcount++; traverse(Tree0(t)); loopsp->markcount--; emit("unmark"); traverse(Tree1(t)); if (lab > 0) { emitl("goto", lab+1); emitlab(lab); traverse(Tree2(t)); emitlab(lab+1); } break; case N_Int: /* integer literal */ emitn("int", (int)Val0(t)); break; case N_Apply: /* application */ traverse(Tree0(t)); traverse(Tree1(t)); emitn("invoke", -1); break; case N_Invok: /* invocation */ if (TType(Tree0(t)) != N_Empty) { traverse(Tree0(t)); } else { emit("pushn1"); /* default to -1(e1,...,en) */ } n = traverse(Tree1(t)); setloc(t); emitn("invoke", n); n = 1; break; case N_Key: /* keyword reference */ setloc(t); emitn("keywd", (int)Val0(t)); break; case N_Limit: /* limitation */ traverse(Tree1(t)); setloc(t); emit("limit"); loopsp->markcount++; traverse(Tree0(t)); loopsp->markcount--; emit("lsusp"); break; case N_List: /* list construction */ emit("pnull"); if (TType(Tree0(t)) == N_Empty) n = 0; else n = traverse(Tree0(t)); setloc(t); emitn("llist", n); n = 1; break; case N_Loop: /* loop */ switch ((int)Val0(Tree0(t))) { case EVERY: lab = alclab(2); loopsp++; loopsp->ltype = EVERY; loopsp->nextlab = lab; loopsp->breaklab = lab + 1; loopsp->markcount = 1; emit("mark0"); traverse(Tree1(t)); emit("pop"); if (TType(Tree2(t)) != N_Empty) { /* every e1 do e2 */ emit("mark0"); loopsp->ltype = N_Loop; loopsp->markcount++; traverse(Tree2(t)); loopsp->markcount--; emit("unmark"); } emitlab(loopsp->nextlab); emit("efail"); emitlab(loopsp->breaklab); loopsp--; break; case REPEAT: lab = alclab(3); loopsp++; loopsp->ltype = N_Loop; loopsp->nextlab = lab + 1; loopsp->breaklab = lab + 2; loopsp->markcount = 1; emitlab(lab); emitl("mark", lab); traverse(Tree1(t)); emitlab(loopsp->nextlab); emit("unmark"); emitl("goto", lab); emitlab(loopsp->breaklab); loopsp--; break; case SUSPEND: /* suspension expression */ if (creatsp > creatstk) nfatal(t, "invalid context for suspend"); lab = alclab(2); loopsp++; loopsp->ltype = EVERY; /* like every ... do for next */ loopsp->nextlab = lab; loopsp->breaklab = lab + 1; loopsp->markcount = 1; emit("mark0"); traverse(Tree1(t)); setloc(t); emit("psusp"); emit("pop"); if (TType(Tree2(t)) != N_Empty) { /* suspend e1 do e2 */ emit("mark0"); loopsp->ltype = N_Loop; loopsp->markcount++; traverse(Tree2(t)); loopsp->markcount--; emit("unmark"); } emitlab(loopsp->nextlab); emit("efail"); emitlab(loopsp->breaklab); loopsp--; break; case WHILE: lab = alclab(3); loopsp++; loopsp->ltype = N_Loop; loopsp->nextlab = lab + 1; loopsp->breaklab = lab + 2; loopsp->markcount = 1; emitlab(lab); emit("mark0"); traverse(Tree1(t)); if (TType(Tree2(t)) != N_Empty) { emit("unmark"); emitl("mark", lab); traverse(Tree2(t)); } emitlab(loopsp->nextlab); emit("unmark"); emitl("goto", lab); emitlab(loopsp->breaklab); loopsp--; break; case UNTIL: lab = alclab(4); loopsp++; loopsp->ltype = N_Loop; loopsp->nextlab = lab + 2; loopsp->breaklab = lab + 3; loopsp->markcount = 1; emitlab(lab); emitl("mark", lab+1); traverse(Tree1(t)); emit("unmark"); emit("efail"); emitlab(lab+1); emitl("mark", lab); traverse(Tree2(t)); emitlab(loopsp->nextlab); emit("unmark"); emitl("goto", lab); emitlab(loopsp->breaklab); loopsp--; break; } break; case N_Next: /* next expression */ if (loopsp < loopstk || loopsp->nextlab <= 0) nfatal(t, "invalid context for next"); else { if (loopsp->ltype != EVERY && loopsp->markcount > 1) for (i = 0; i < loopsp->markcount - 1; i++) emit("unmark"); emitl("goto", loopsp->nextlab); } break; case N_Not: /* not expression */ lab = alclab(1); emitl("mark", lab); loopsp->markcount++; traverse(Tree0(t)); loopsp->markcount--; emit("unmark"); emit("efail"); emitlab(lab); emit("pnull"); break; case N_Proc: /* procedure */ loopsp = loopstk; loopsp->nextlab = 0; loopsp->breaklab = 0; loopsp->markcount = 0; casesp = casestk; creatsp = creatstk; writecheck(fprintf(codefile, "proc %s\n", Str0(Tree0(t)))); lout(codefile); cout(codefile); emit("declend"); setloc(t); if (TType(Tree1(t)) != N_Empty) { lab = alclab(1); emitl("init", lab); emitl("mark", lab); traverse(Tree1(t)); emit("unmark"); emitlab(lab); } if (TType(Tree2(t)) != N_Empty) traverse(Tree2(t)); setloc(Tree3(t)); emit("pfail"); emit("end"); if (!silent) fprintf(stderr, " %s (%lu/%ld)\n", Str0(Tree0(t)), (unsigned long)DiffPtrs(tfree,tree)/sizeof(word),(long)tsize); break; case N_Real: /* real literal */ emitn("real", (int)Val0(t)); break; case N_Ret: /* return expression */ if (creatsp > creatstk) nfatal(t, "invalid context for return or fail"); if (Val0(Tree0(t)) != FAIL) { lab = alclab(1); emitl("mark", lab); loopsp->markcount++; traverse(Tree1(t)); loopsp->markcount--; setloc(t); emit("pret"); emitlab(lab); } setloc(t); emit("pfail"); break; case N_Scan: /* scanning expression */ if (Val0(Tree0(t)) == SCANASGN) emit("pnull"); traverse(Tree1(t)); if (Val0(Tree0(t)) == SCANASGN) emit("sdup"); setloc(t); emit("bscan"); traverse(Tree2(t)); setloc(t); emit("escan"); if (Val0(Tree0(t)) == SCANASGN) emit("asgn"); break; case N_Sect: /* section operation */ emit("pnull"); traverse(Tree1(t)); traverse(Tree2(t)); if (Val0(Tree0(t)) == PCOLON || Val0(Tree0(t)) == MCOLON) emit("dup"); traverse(Tree3(t)); setloc(Tree0(t)); if (Val0(Tree0(t)) == PCOLON) emit("plus"); else if (Val0(Tree0(t)) == MCOLON) emit("minus"); setloc(t); emit("sect"); break; case N_Slist: /* semicolon-separated expr list */ lab = alclab(1); emitl("mark", lab); loopsp->markcount++; traverse(Tree0(t)); loopsp->markcount--; emit("unmark"); emitlab(lab); traverse(Tree1(t)); break; case N_Str: /* string literal */ emitn("str", (int)Val0(t)); break; case N_To: /* to expression */ emit("pnull"); traverse(Tree0(t)); traverse(Tree1(t)); emit("push1"); setloc(t); emit("toby"); break; case N_ToBy: /* to-by expression */ emit("pnull"); traverse(Tree0(t)); traverse(Tree1(t)); traverse(Tree2(t)); setloc(t); emit("toby"); break; case N_Unop: /* unary operator */ unopa((int)Val0(Tree0(t)),t); traverse(Tree1(t)); setloc(t); unopb((int)Val0(Tree0(t))); break; default: emitn("?????", TType(t)); tsyserr("traverse: undefined node type"); } return n; } /* * binop emits code for binary operators. For non-augmented operators, * the name of operator is emitted. For augmented operators, an "asgn" * is emitted after the name of the operator. */ static novalue binop(op) int op; { register int asgn; register char *name; asgn = 0; switch (op) { case ASSIGN: name = "asgn"; break; case CARETASGN: asgn++; case CARET: name = "power"; break; case CONCATASGN: asgn++; case CONCAT: name = "cat"; break; case DIFFASGN: asgn++; case DIFF: name = "diff"; break; case AUGEQV: asgn++; case EQUIV: name = "eqv"; break; case INTERASGN: asgn++; case INTER: name = "inter"; break; case LBRACK: name = "subsc"; break; case LCONCATASGN: asgn++; case LCONCAT: name = "lconcat"; break; case AUGSEQ: asgn++; case LEXEQ: name = "lexeq"; break; case AUGSGE: asgn++; case LEXGE: name = "lexge"; break; case AUGSGT: asgn++; case LEXGT: name = "lexgt"; break; case AUGSLE: asgn++; case LEXLE: name = "lexle"; break; case AUGSLT: asgn++; case LEXLT: name = "lexlt"; break; case AUGSNE: asgn++; case LEXNE: name = "lexne"; break; case MINUSASGN: asgn++; case MINUS: name = "minus"; break; case MODASGN: asgn++; case MOD: name = "mod"; break; case AUGNEQV: asgn++; case NOTEQUIV: name = "neqv"; break; case AUGEQ: asgn++; case NUMEQ: name = "numeq"; break; case AUGGE: asgn++; case NUMGE: name = "numge"; break; case AUGGT: asgn++; case NUMGT: name = "numgt"; break; case AUGLE: asgn++; case NUMLE: name = "numle"; break; case AUGLT: asgn++; case NUMLT: name = "numlt"; break; case AUGNE: asgn++; case NUMNE: name = "numne"; break; case PLUSASGN: asgn++; case PLUS: name = "plus"; break; case REVASSIGN: name = "rasgn"; break; case REVSWAP: name = "rswap"; break; case SLASHASGN: asgn++; case SLASH: name = "div"; break; case STARASGN: asgn++; case STAR: name = "mult"; break; case SWAP: name = "swap"; break; case UNIONASGN: asgn++; case UNION: name = "unions"; break; default: emitn("?binop", op); tsyserr("binop: undefined binary operator"); } emit(name); if (asgn) emit("asgn"); } /* * unopa and unopb handle code emission for unary operators. unary operator * sequences that are the same as binary operator sequences are recognized * by the lexical analyzer as binary operators. For example, ~===x means to * do three tab(match(...)) operations and then a cset complement, but the * lexical analyzer sees the operator sequence as the "neqv" binary * operation. unopa and unopb unravel tokens of this form. * * When a N_Unop node is encountered, unopa is called to emit the necessary * number of "pnull" operations to receive the intermediate results. This * amounts to a pnull for each operation. */ static novalue unopa(op,t) int op; nodeptr t; { switch (op) { case NOTEQUIV: /* unary ~ and three = operators */ emit("pnull"); case LEXNE: /* unary ~ and two = operators */ case EQUIV: /* three unary = operators */ emit("pnull"); case NUMNE: /* unary ~ and = operators */ case UNION: /* two unary + operators */ case DIFF: /* two unary - operators */ case LEXEQ: /* two unary = operators */ case INTER: /* two unary * operators */ emit("pnull"); case BACKSLASH: /* unary \ operator */ case BANG: /* unary ! operator */ case CARET: /* unary ^ operator */ case PLUS: /* unary + operator */ case TILDE: /* unary ~ operator */ case MINUS: /* unary - operator */ case NUMEQ: /* unary = operator */ case STAR: /* unary * operator */ case QMARK: /* unary ? operator */ case SLASH: /* unary / operator */ emit("pnull"); break; case DOT: /* unary . operator */ if (TType(Tree1(t)) == N_Int || TType(Tree1(t)) == N_Real) { if (!silent) { nfatal(t,"dereferencing operator applied to numeric literal"); tfatals--; /* for now */ nocode--; } } emit("pnull"); break; default: tsyserr("unopa: undefined unary operator"); } } /* * unopb is the back-end code emitter for unary operators. It emits * the operations represented by the token op. For tokens representing * a single operator, the name of the operator is emitted. For tokens * representing a sequence of operators, recursive calls are used. In * such a case, the operator sequence is "scanned" from right to left * and unopb is called with the token for the appropriate operation. * * For example, consider the sequence of calls and code emission for "~===": * unopb(NOTEQUIV) ~=== * unopb(NUMEQ) = * emits "tabmat" * unopb(NUMEQ) = * emits "tabmat" * unopb(NUMEQ) = * emits "tabmat" * emits "compl" */ static novalue unopb(op) int op; { register char *name; switch (op) { case DOT: /* unary . operator */ name = "value"; break; case BACKSLASH: /* unary \ operator */ name = "nonnull"; break; case BANG: /* unary ! operator */ name = "bang"; break; case CARET: /* unary ^ operator */ name = "refresh"; break; case UNION: /* two unary + operators */ unopb(PLUS); case PLUS: /* unary + operator */ name = "number"; break; case NOTEQUIV: /* unary ~ and three = operators */ unopb(NUMEQ); case LEXNE: /* unary ~ and two = operators */ unopb(NUMEQ); case NUMNE: /* unary ~ and = operators */ unopb(NUMEQ); case TILDE: /* unary ~ operator (cset compl) */ name = "compl"; break; case DIFF: /* two unary - operators */ unopb(MINUS); case MINUS: /* unary - operator */ name = "neg"; break; case EQUIV: /* three unary = operators */ unopb(NUMEQ); case LEXEQ: /* two unary = operators */ unopb(NUMEQ); case NUMEQ: /* unary = operator */ name = "tabmat"; break; case INTER: /* two unary * operators */ unopb(STAR); case STAR: /* unary * operator */ name = "size"; break; case QMARK: /* unary ? operator */ name = "random"; break; case SLASH: /* unary / operator */ name = "null"; break; default: emitn("?unop", op); tsyserr("unopb: undefined unary operator"); } emit(name); } /* * setloc emits "filen" and "line" directives for the source location of * node n. A directive is only emitted if the corrosponding value * has changed since the last time setloc was called. Note: File(n) * reportedly occasionally points at uninitialized data, producing * bogus results (as well as reams of filen commands). We could use * comfile here instead; that would ignore any #line directives. */ static char *lastfiln = NULL; static int lastline = 0; #ifdef EvalTrace static int lastcol = 0; #endif /* EvalTrace */ static novalue setloc(n) nodeptr n; { if ((n != NULL) && (TType(n) != N_Empty) && (File(n) != NULL) && (lastfiln == NULL || strcmp(File(n), lastfiln) != 0)) { lastfiln = File(n); emits("filen", lastfiln); } if (Line(n) != lastline) { lastline = Line(n); emitn("line", Line(n)); } #ifdef EvalTrace if (Col(n) != lastcol) { lastcol = Col(n); emitn("colm", Col(n)); } #endif /* EvalTrace */ } #ifdef MultipleRuns /* * Reinitialize last file name and line number for repeated runs. */ novalue tcodeinit() { lastfiln = NULL; #ifdef EvalTrace lastcol = 0; #endif /* EvalTrace */ } #endif /* Multiple Runs */ /* * The emit* routines output ucode to codefile. The various routines are: * * emitlab(l) - emit "lab" instruction for label l. * emit(s) - emit instruction s. * emitl(s,a) - emit instruction s with reference to label a. * emitn(s,n) - emit instruction s with numeric argument a. * emits(s,a) - emit instruction s with string argument a. */ static novalue emitlab(l) int l; { writecheck(fprintf(codefile, "lab L%d\n", l)); } static novalue emit(s) char *s; { writecheck(fprintf(codefile, "\t%s\n", s)); } static novalue emitl(s, a) char *s; int a; { writecheck(fprintf(codefile, "\t%s\tL%d\n", s, a)); } static novalue emitn(s, a) char *s; int a; { writecheck(fprintf(codefile, "\t%s\t%d\n", s, a)); } static novalue emits(s, a) char *s, *a; { writecheck(fprintf(codefile, "\t%s\t%s\n", s, a)); } /* * alclab allocates n labels and returns the first. For the interpreter, * labels are restarted at 1 for each procedure, while in the compiler, * they start at 1 and increase throughout the entire compilation. */ static int alclab(n) int n; { register int lab; lab = nextlab; nextlab += n; return lab; }