backend.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404
  1. /*****************************************************************************
  2. * Project: dcc
  3. * File: backend.c
  4. * Purpose: Back-end module. Generates C code for each procedure.
  5. * (C) Cristina Cifuentes
  6. ****************************************************************************/
  7. #include <cassert>
  8. #include <string>
  9. #include "dcc.h"
  10. #include <fstream>
  11. #include <string.h>
  12. #include <stdio.h>
  13. bundle cCode; /* Procedure declaration and code */
  14. using namespace std;
  15. /* Indentation buffer */
  16. #define indSize 81 /* size of the indentation buffer. Each indentation
  17. * is of 4 spaces => max. 20 indentation levels */
  18. static char indentBuf[indSize] =
  19. " ";
  20. /* Indentation according to the depth of the statement */
  21. char *indent (Int indLevel)
  22. {
  23. return (&indentBuf[indSize-(indLevel*4)-1]);
  24. }
  25. /* Returns a unique index to the next label */
  26. Int getNextLabel()
  27. {
  28. static Int labelIdx = 1; /* index of the next label */
  29. return (labelIdx++);
  30. }
  31. /* displays statistics on the subroutine */
  32. void Function::displayStats ()
  33. {
  34. printf("\nStatistics - Subroutine %s\n", name.c_str());
  35. printf ("Number of Icode instructions:\n");
  36. printf (" Low-level : %4d\n", stats.numLLIcode);
  37. if (! (flg & PROC_ASM))
  38. {
  39. printf (" High-level: %4d\n", stats.numHLIcode);
  40. printf (" Percentage reduction: %2.2f%%\n", 100.0 - (stats.numHLIcode *
  41. 100.0) / stats.numLLIcode);
  42. }
  43. }
  44. /**** this proc is not required any more?? ****/
  45. #if 0
  46. static void fixupLabels (PPROC pProc)
  47. /* Checks the graph (pProc->cfg) for any nodes that have labels, and gives
  48. * a unique label number for it. This label is placed in the associated
  49. * icode for the node (pProc->Icode). The procedure is done in sequential
  50. * order of dsfLast numbering. */
  51. { Int i; /* index into the dfsLast array */
  52. PBB *dfsLast; /* pointer to the dfsLast array */
  53. dfsLast = pProc->dfsLast;
  54. for (i = 0; i < pProc->numBBs; i++)
  55. if (dfsLast[i]->flg/* & BB_HAS_LABEL*/) {
  56. pProc->Icode.icode[dfsLast[i]->start].ic.ll.flg |= HLL_LABEL;
  57. pProc->Icode.icode[dfsLast[i]->start].ic.ll.hllLabNum = getNextLabel();
  58. }
  59. }
  60. #endif
  61. /* Returns the corresponding C string for the given character c. Character
  62. * constants such as carriage return and line feed, require 2 C characters. */
  63. char *cChar (byte c)
  64. {
  65. static char res[3];
  66. switch (c) {
  67. case 0x8: /* backspace */
  68. sprintf (res, "\\b");
  69. break;
  70. case 0x9: /* horizontal tab */
  71. sprintf (res, "\\t");
  72. break;
  73. case 0x0A: /* new line */
  74. sprintf (res, "\\n");
  75. break;
  76. case 0x0C: /* form feed */
  77. sprintf (res, "\\f");
  78. break;
  79. case 0x0D: /* carriage return */
  80. sprintf (res, "\\r");
  81. break;
  82. default: /* any other character*/
  83. sprintf (res, "%c", c);
  84. }
  85. return (res);
  86. }
  87. /* Prints the variable's name and initial contents on the file.
  88. * Note: to get to the value of the variable:
  89. * com file: prog.Image[operand]
  90. * exe file: prog.Image[operand+0x100] */
  91. static void printGlobVar (SYM * psym)
  92. {
  93. Int j;
  94. dword relocOp = prog.fCOM ? psym->label : psym->label + 0x100;
  95. char *strContents; /* initial contents of variable */
  96. switch (psym->size) {
  97. case 1: cCode.appendDecl( "byte\t%s = %ld;\n",
  98. psym->name, prog.Image[relocOp]);
  99. break;
  100. case 2: cCode.appendDecl( "word\t%s = %ld;\n",
  101. psym->name, LH(prog.Image+relocOp));
  102. break;
  103. case 4: if (psym->type == TYPE_PTR) /* pointer */
  104. cCode.appendDecl( "word\t*%s = %ld;\n",
  105. psym->name, LH(prog.Image+relocOp));
  106. else /* char */
  107. cCode.appendDecl(
  108. "char\t%s[4] = \"%c%c%c%c\";\n",
  109. psym->name, prog.Image[relocOp],
  110. prog.Image[relocOp+1], prog.Image[relocOp+2],
  111. prog.Image[relocOp+3]);
  112. break;
  113. default:
  114. strContents = (char *)malloc((psym->size*2+1) *sizeof(char));
  115. strContents[0] = '\0';
  116. for (j=0; j < psym->size; j++)
  117. strcat (strContents, cChar(prog.Image[relocOp + j]));
  118. cCode.appendDecl( "char\t*%s = \"%s\";\n",
  119. psym->name, strContents);
  120. free(strContents);
  121. }
  122. }
  123. // Note: Not called at present.
  124. /* Writes the contents of the symbol table, along with any variable
  125. * initialization. */
  126. static void writeGlobSymTable()
  127. {
  128. Int idx;
  129. char type[10];
  130. SYM * pSym;
  131. if (not symtab.empty())
  132. {
  133. cCode.appendDecl( "/* Global variables */\n");
  134. for (idx = 0; idx < symtab.size(); idx++)
  135. {
  136. pSym = &symtab[idx];
  137. if (symtab[idx].duVal.isUSE_VAL()) /* first used */
  138. printGlobVar (&symtab[idx]);
  139. else { /* first defined */
  140. switch (pSym->size) {
  141. case 1: strcpy (type, "byte\t"); break;
  142. case 2: strcpy (type, "int\t"); break;
  143. case 4: if (pSym->type == TYPE_PTR)
  144. strcpy (type, "int\t*");
  145. else
  146. strcpy (type, "char\t*");
  147. break;
  148. default: strcpy (type, "char\t*");
  149. }
  150. cCode.appendDecl( "%s%s;\t/* size = %ld */\n",
  151. type, pSym->name, pSym->size);
  152. }
  153. }
  154. cCode.appendDecl( "\n");
  155. }
  156. }
  157. /* Writes the header information and global variables to the output C file
  158. * fp. */
  159. static void writeHeader (std::ostream &ios, char *fileName)
  160. {
  161. /* Write header information */
  162. newBundle (&cCode);
  163. cCode.appendDecl( "/*\n");
  164. cCode.appendDecl( " * Input file\t: %s\n", fileName);
  165. cCode.appendDecl( " * File type\t: %s\n", (prog.fCOM)?"COM":"EXE");
  166. cCode.appendDecl( " */\n\n#include \"dcc.h\"\n\n");
  167. /* Write global symbol table */
  168. /** writeGlobSymTable(); *** need to change them into locident fmt ***/
  169. writeBundle (ios, cCode);
  170. freeBundle (&cCode);
  171. }
  172. /* Writes the registers that are set in the bitvector */
  173. static void writeBitVector (dword regi)
  174. {
  175. Int j;
  176. for (j = 0; j < INDEXBASE; j++)
  177. {
  178. if ((regi & power2(j)) != 0)
  179. printf ("%s ", allRegs[j]);
  180. }
  181. }
  182. static void writeBitVector (const std::bitset<32> &regi)
  183. { Int j;
  184. for (j = 0; j < INDEXBASE; j++)
  185. {
  186. if (regi.test(j))
  187. printf ("%s ", allRegs[j]);
  188. }
  189. }
  190. // Note: Not currently called!
  191. /* Checks the given icode to determine whether it has a label associated
  192. * to it. If so, a goto is emitted to this label; otherwise, a new label
  193. * is created and a goto is also emitted.
  194. * Note: this procedure is to be used when the label is to be forward on
  195. * the code; that is, the target code has not been traversed yet. */
  196. static void emitFwdGotoLabel (ICODE * pt, Int indLevel)
  197. {
  198. if (! (pt->ic.ll.flg & HLL_LABEL)) /* node hasn't got a lab */
  199. {
  200. /* Generate new label */
  201. pt->ic.ll.hllLabNum = getNextLabel();
  202. pt->ic.ll.flg |= HLL_LABEL;
  203. }
  204. cCode.appendCode( "%sgoto l%ld;\n", indent(indLevel),
  205. pt->ic.ll.hllLabNum);
  206. }
  207. /* Writes the procedure's declaration (including arguments), local variables,
  208. * and invokes the procedure that writes the code of the given record *hli */
  209. void Function::codeGen (std::ostream &fs)
  210. {
  211. Int i, numLoc;
  212. //STKFRAME * args; /* Procedure arguments */
  213. char buf[200], /* Procedure's definition */
  214. arg[30]; /* One argument */
  215. ID *locid; /* Pointer to one local identifier */
  216. BB *pBB; /* Pointer to basic block */
  217. /* Write procedure/function header */
  218. newBundle (&cCode);
  219. if (flg & PROC_IS_FUNC) /* Function */
  220. cCode.appendDecl( "\n%s %s (", hlTypes[retVal.type],name.c_str());
  221. else /* Procedure */
  222. cCode.appendDecl( "\nvoid %s (", name.c_str());
  223. /* Write arguments */
  224. memset (buf, 0, sizeof(buf));
  225. for (i = 0; i < args.sym.size(); i++)
  226. {
  227. if (args.sym[i].invalid == FALSE)
  228. {
  229. sprintf (arg,"%s %s",hlTypes[args.sym[i].type], args.sym[i].name);
  230. strcat (buf, arg);
  231. if (i < (args.sym.size() - 1))
  232. strcat (buf, ", ");
  233. }
  234. }
  235. strcat (buf, ")\n");
  236. cCode.appendDecl( "%s", buf);
  237. /* Write comments */
  238. writeProcComments();
  239. /* Write local variables */
  240. if (! (flg & PROC_ASM))
  241. {
  242. numLoc = 0;
  243. for (i = 0; i < localId.csym(); i++)
  244. {
  245. locid = &localId.id_arr[i];
  246. /* Output only non-invalidated entries */
  247. if (locid->illegal == FALSE)
  248. {
  249. if (locid->loc == REG_FRAME)
  250. {
  251. /* Register variables are assigned to a local variable */
  252. if (((flg & SI_REGVAR) && (locid->id.regi == rSI)) ||
  253. ((flg & DI_REGVAR) && (locid->id.regi == rDI)))
  254. {
  255. sprintf (locid->name, "loc%ld", ++numLoc);
  256. cCode.appendDecl( "int %s;\n", locid->name);
  257. }
  258. /* Other registers are named when they are first used in
  259. * the output C code, and appended to the proc decl. */
  260. }
  261. else if (locid->loc == STK_FRAME)
  262. {
  263. /* Name local variables and output appropriate type */
  264. sprintf (locid->name, "loc%ld", ++numLoc);
  265. cCode.appendDecl( "%s %s;\n",hlTypes[locid->type], locid->name);
  266. }
  267. }
  268. }
  269. }
  270. /* Write procedure's code */
  271. if (flg & PROC_ASM) /* generate assembler */
  272. disassem (3, this);
  273. else /* generate C */
  274. m_cfg.front()->writeCode (1, this, &numLoc, MAX, UN_INIT);
  275. cCode.appendCode( "}\n\n");
  276. writeBundle (fs, cCode);
  277. freeBundle (&cCode);
  278. /* Write Live register analysis information */
  279. if (option.verbose)
  280. for (i = 0; i < numBBs; i++)
  281. {
  282. pBB = m_dfsLast[i];
  283. if (pBB->flg & INVALID_BB) continue; /* skip invalid BBs */
  284. printf ("BB %d\n", i);
  285. printf (" Start = %d, end = %d\n", pBB->begin(), pBB->end());
  286. printf (" LiveUse = ");
  287. writeBitVector (pBB->liveUse);
  288. printf ("\n Def = ");
  289. writeBitVector (pBB->def);
  290. printf ("\n LiveOut = ");
  291. writeBitVector (pBB->liveOut);
  292. printf ("\n LiveIn = ");
  293. writeBitVector (pBB->liveIn);
  294. printf ("\n\n");
  295. }
  296. }
  297. /* Recursive procedure. Displays the procedure's code in depth-first order
  298. * of the call graph. */
  299. static void backBackEnd (char *filename, CALL_GRAPH * pcallGraph, std::ostream &ios)
  300. {
  301. Int i;
  302. // IFace.Yield(); /* This is a good place to yield to other apps */
  303. /* Check if this procedure has been processed already */
  304. if ((pcallGraph->proc->flg & PROC_OUTPUT) ||
  305. (pcallGraph->proc->flg & PROC_ISLIB))
  306. return;
  307. pcallGraph->proc->flg |= PROC_OUTPUT;
  308. /* Dfs if this procedure has any successors */
  309. for (i = 0; i < pcallGraph->outEdges.size(); i++)
  310. {
  311. backBackEnd (filename, pcallGraph->outEdges[i], ios);
  312. }
  313. /* Generate code for this procedure */
  314. stats.numLLIcode = pcallGraph->proc->Icode.size();
  315. stats.numHLIcode = 0;
  316. pcallGraph->proc->codeGen (ios);
  317. /* Generate statistics */
  318. if (option.Stats)
  319. pcallGraph->proc->displayStats ();
  320. if (! (pcallGraph->proc->flg & PROC_ASM))
  321. {
  322. stats.totalLL += stats.numLLIcode;
  323. stats.totalHL += stats.numHLIcode;
  324. }
  325. }
  326. /* Invokes the necessary routines to produce code one procedure at a time. */
  327. void BackEnd (char *fileName, CALL_GRAPH * pcallGraph)
  328. {
  329. std::ofstream fs; /* Output C file */
  330. /* Get output file name */
  331. std::string outNam(fileName);
  332. outNam = outNam.substr(0,outNam.rfind("."))+".b"; /* b for beta */
  333. /* Open output file */
  334. fs.open(outNam);
  335. if(!fs.is_open())
  336. fatalError (CANNOT_OPEN, outNam.c_str());
  337. printf ("dcc: Writing C beta file %s\n", outNam.c_str());
  338. /* Header information */
  339. writeHeader (fs, fileName);
  340. /* Initialize total Icode instructions statistics */
  341. stats.totalLL = 0;
  342. stats.totalHL = 0;
  343. /* Process each procedure at a time */
  344. backBackEnd (fileName, pcallGraph, fs);
  345. /* Close output file */
  346. fs.close();
  347. printf ("dcc: Finished writing C beta file\n");
  348. }