git.gag.com Git - fw/sdcc/blob - src/z80/peep.c

   1 /*-------------------------------------------------------------------------\r
   2   peep.c - source file for peephole optimizer helper functions\r
   3 \r
   4   Written By -  Philipp Klaus Krause\r
   5 \r
   6   This program is free software; you can redistribute it and/or modify it\r
   7   under the terms of the GNU General Public License as published by the\r
   8   Free Software Foundation; either version 2, or (at your option) any\r
   9   later version.\r
  10 \r
  11   This program is distributed in the hope that it will be useful,\r
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  14   GNU General Public License for more details.\r
  15 \r
  16   You should have received a copy of the GNU General Public License\r
  17   along with this program; if not, write to the Free Software\r
  18   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.\r
  19 \r
  20   In other words, you are welcome to use, share and improve this program.\r
  21   You are forbidden to forbid anyone else to use, share and improve\r
  22   what you give them.   Help stamp out software-hoarding!\r
  23 -------------------------------------------------------------------------*/\r
  24 \r
  25 #include "common.h"\r
  26 #include "SDCCicode.h"\r
  27 #include "z80.h"\r
  28 #include "SDCCglobl.h"\r
  29 #include "SDCCpeeph.h"\r
  30 #include "gen.h"\r
  31 \r
  32 #define NOTUSEDERROR() do {werror(E_INTERNAL_ERROR, __FILE__, __LINE__, "error in notUsed()");} while(0)\r
  33 \r
  34 /*#define D(_s) { printf _s; fflush(stdout); }*/\r
  35 #define D(_s)\r
  36 \r
  37 typedef enum\r
  38 {\r
  39   S4O_CONDJMP,\r
  40   S4O_WR_OP,\r
  41   S4O_RD_OP,\r
  42   S4O_TERM,\r
  43   S4O_VISITED,\r
  44   S4O_ABORT,\r
  45   S4O_CONTINUE\r
  46 } S4O_RET;\r
  47 \r
  48 static struct\r
  49 {\r
  50   lineNode *head;\r
  51 } _G;\r
  52 \r
  53 /*-----------------------------------------------------------------*/\r
  54 /* univisitLines - clear "visited" flag in all lines               */\r
  55 /*-----------------------------------------------------------------*/\r
  56 static void\r
  57 unvisitLines (lineNode *pl)\r
  58 {\r
  59   for (; pl; pl = pl->next)\r
  60     pl->visited = FALSE;\r
  61 }\r
  62 \r
  63 #define AOP(op) op->aop\r
  64 #define AOP_SIZE(op) AOP(op)->size\r
  65 \r
  66 static bool\r
  67 isReturned(const char *what)\r
  68 {\r
  69   symbol *sym;\r
  70   sym_link *sym_lnk;\r
  71   int size;\r
  72   lineNode *l;\r
  73 \r
  74   if(strncmp(what, "iy", 2) == 0)\r
  75     return FALSE;\r
  76   if(strlen(what) != 1)\r
  77     return TRUE;\r
  78 \r
  79   l = _G.head;\r
  80   do\r
  81   {\r
  82     l = l->next;\r
  83   } while(l->ic->op != FUNCTION);\r
  84 \r
  85   sym = OP_SYMBOL(IC_LEFT(_G.head->next->next->ic));\r
  86 \r
  87   if(sym && IS_DECL(sym->type))\r
  88     {\r
  89       // Find size of return value.\r
  90       specifier *spec;\r
  91       if(sym->type->select.d.dcl_type != FUNCTION)\r
  92         NOTUSEDERROR();\r
  93       spec = &(sym->etype->select.s);\r
  94       if(spec->noun == V_VOID)\r
  95          size = 0;\r
  96       else if(spec->noun == V_CHAR)\r
  97          size = 1;\r
  98       else if(spec->noun == V_INT && !(spec->b_long))\r
  99          size = 2;\r
 100       else\r
 101         size = 4;\r
 102 \r
 103       // Check for returned pointer.\r
 104       sym_lnk = sym->type;\r
 105       while (sym_lnk && !IS_PTR (sym_lnk))\r
 106         sym_lnk = sym_lnk->next;\r
 107       if(IS_PTR(sym_lnk))\r
 108         size = 2;\r
 109     }\r
 110   else\r
 111     {\r
 112       NOTUSEDERROR();\r
 113       size = 4;\r
 114     }\r
 115 \r
 116   switch(*what)\r
 117     {\r
 118     case 'd':\r
 119       return(size >= 4);\r
 120     case 'e':\r
 121       return(size >= 3);\r
 122     case 'h':\r
 123       return(size >= 2);\r
 124     case 'l':\r
 125       return(size >= 1);\r
 126     default:\r
 127       return FALSE;\r
 128     }\r
 129 }\r
 130 \r
 131 /*-----------------------------------------------------------------*/\r
 132 /* incLabelJmpToCount - increment counter "jmpToCount" in entry    */\r
 133 /* of the list labelHash                                           */\r
 134 /*-----------------------------------------------------------------*/\r
 135 static bool\r
 136 incLabelJmpToCount (const char *label)\r
 137 {\r
 138   labelHashEntry *entry;\r
 139 \r
 140   entry = getLabelRef (label, _G.head);\r
 141   if (!entry)\r
 142     return FALSE;\r
 143   entry->jmpToCount++;\r
 144   return TRUE;\r
 145 }\r
 146 \r
 147 /*-----------------------------------------------------------------*/\r
 148 /* findLabel -                                                     */\r
 149 /* 1. extracts label in the opcode pl                              */\r
 150 /* 2. increment "label jump-to count" in labelHash                 */\r
 151 /* 3. search lineNode with label definition and return it          */\r
 152 /*-----------------------------------------------------------------*/\r
 153 static lineNode *\r
 154 findLabel (const lineNode *pl)\r
 155 {\r
 156   char *p;\r
 157   lineNode *cpl;\r
 158 \r
 159   /* 1. extract label in opcode */\r
 160 \r
 161   /* In each mcs51 jumping opcode the label is at the end of the opcode */\r
 162   p = strlen (pl->line) - 1 + pl->line;\r
 163 \r
 164   /* scan backward until ',' or '\t' */\r
 165   for (; p > pl->line; p--)\r
 166     if (*p == ',' || *p == '\t')\r
 167       break;\r
 168 \r
 169   /* sanity check */\r
 170   if (p == pl->line)\r
 171     {\r
 172       NOTUSEDERROR();\r
 173       return NULL;\r
 174     }\r
 175 \r
 176   /* skip ',' resp. '\t' */\r
 177   ++p;\r
 178 \r
 179   /* 2. increment "label jump-to count" */\r
 180   if (!incLabelJmpToCount (p))\r
 181     return NULL;\r
 182 \r
 183   /* 3. search lineNode with label definition and return it */\r
 184   for (cpl = _G.head; cpl; cpl = cpl->next)\r
 185     {\r
 186       if (   cpl->isLabel\r
 187           && strncmp (p, cpl->line, strlen(p)) == 0)\r
 188         {\r
 189           return cpl;\r
 190         }\r
 191     }\r
 192   return NULL;\r
 193 }\r
 194 \r
 195 static bool\r
 196 z80MightRead(const lineNode *pl, const char *what)\r
 197 {\r
 198   if(strcmp(pl->line, "call\t__initrleblock") == 0)\r
 199     return TRUE;\r
 200 \r
 201   if(strcmp(what, "iyl") == 0 || strcmp(what, "iyh") == 0)\r
 202     what = "iy";\r
 203 \r
 204   if(strncmp(pl->line, "call\t", 5) == 0 && strchr(pl->line, ',') == 0)\r
 205     return FALSE;\r
 206 \r
 207   if(strncmp(pl->line, "ret", 3) == 0 && !isReturned(what))\r
 208     return FALSE;\r
 209 \r
 210   if(strcmp(pl->line, "ex\tde,hl") == 0 && strchr(what, 'h') == 0 && strchr(what, 'l') == 0 && strchr(what, 'd') == 0&& strchr(what, 'e') == 0)\r
 211     return FALSE;\r
 212   if(strncmp(pl->line, "ld\t", 3) == 0)\r
 213     {\r
 214       if(strstr(strchr(pl->line, ','), what) && strchr(pl->line, ',')[1] != '#')\r
 215         return TRUE;\r
 216       if(*(strchr(pl->line, ',') - 1) == ')' && strstr(pl->line + 3, what) && (strchr(pl->line, '#') == 0 || strchr(pl->line, '#') > strchr(pl->line, ',')))\r
 217         return TRUE;\r
 218       return FALSE;\r
 219     }\r
 220 \r
 221   if(strcmp(pl->line, "xor\ta,a") == 0)\r
 222     return FALSE;\r
 223 \r
 224   if(strncmp(pl->line, "adc\t", 4) == 0 ||\r
 225     strncmp(pl->line, "add\t", 4) == 0 ||\r
 226     strncmp(pl->line, "and\t", 4) == 0 ||\r
 227     strncmp(pl->line, "or\t", 3) == 0 ||\r
 228     strncmp(pl->line, "sbc\t", 4) == 0 ||\r
 229     strncmp(pl->line, "sub\t", 4) == 0 ||\r
 230     strncmp(pl->line, "xor\t", 4) == 0)\r
 231     {\r
 232       if( strstr(pl->line + 3, what) == 0 && strcmp("a", what))\r
 233         return FALSE;\r
 234     }\r
 235 \r
 236   if(strncmp(pl->line, "pop\t", 4) == 0)\r
 237     return FALSE;\r
 238 \r
 239   if(strncmp(pl->line, "push\t", 5) == 0)\r
 240     return(strstr(pl->line + 5, what) != 0);\r
 241 \r
 242   if(\r
 243     strncmp(pl->line, "dec\t", 4) == 0 ||\r
 244     strncmp(pl->line, "inc\t", 4) == 0 ||\r
 245     strncmp(pl->line, "rl\t", 3) == 0 ||\r
 246     strncmp(pl->line, "rr\t", 3) == 0 ||  \r
 247     strncmp(pl->line, "sla\t", 4) == 0 ||\r
 248     strncmp(pl->line, "srl\t", 4) == 0)\r
 249     {\r
 250        return (strstr(pl->line + 3, what) != 0);\r
 251     }\r
 252 \r
 253   if(strncmp(pl->line, "jp\t", 3) == 0 ||\r
 254     (bool)(strncmp(pl->line, "jr\t", 3)) == 0)\r
 255     return FALSE;\r
 256 \r
 257   if(strncmp(pl->line, "rla", 3) == 0 ||\r
 258     strncmp(pl->line, "rlca", 4) == 0)\r
 259     return(strcmp(what, "a") == 0);\r
 260 \r
 261   return TRUE;\r
 262 }\r
 263 \r
 264 static bool\r
 265 z80UncondJump(const lineNode *pl)\r
 266 {\r
 267   if((strncmp(pl->line, "jp\t", 3) == 0 ||\r
 268     strncmp(pl->line, "jr\t", 3) == 0) && strchr(pl->line, ',') == 0)\r
 269     return TRUE;\r
 270   return FALSE;\r
 271 }\r
 272 \r
 273 static bool\r
 274 z80CondJump(const lineNode *pl)\r
 275 {\r
 276   if((strncmp(pl->line, "jp\t", 3) == 0 ||\r
 277     strncmp(pl->line, "jr\t", 3) == 0) && strchr(pl->line, ',') != 0)\r
 278     return TRUE;\r
 279   return FALSE;\r
 280 }\r
 281 \r
 282 static bool\r
 283 z80SurelyWrites(const lineNode *pl, const char *what)\r
 284 {\r
 285   if(strcmp(pl->line, "xor\ta,a") == 0 && strcmp(what, "a") == 0)\r
 286     return TRUE;\r
 287   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "hl", 2) == 0 && (what[0] == 'h' || what[0] == 'l'))\r
 288     return TRUE;\r
 289   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "de", 2) == 0 && (what[0] == 'd' || what[0] == 'e'))\r
 290     return TRUE;\r
 291   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "bc", 2) == 0 && (what[0] == 'b' || what[0] == 'c'))\r
 292     return TRUE;\r
 293   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, what, strlen(what)) == 0 && pl->line[3 + strlen(what)] == ',')\r
 294     return TRUE;\r
 295   if(strncmp(pl->line, "pop\t", 4) == 0 && strstr(pl->line + 4, what))\r
 296     return TRUE;\r
 297   if(strncmp(pl->line, "call\t", 5) == 0 && strchr(pl->line, ',') == 0)\r
 298     return TRUE;\r
 299   if(strcmp(pl->line, "ret") == 0)\r
 300     return TRUE;\r
 301   if(strncmp(pl->line, "ld\tiy", 5) == 0 && strncmp(what, "iy", 2) == 0)\r
 302     return TRUE;\r
 303   return FALSE;\r
 304 }\r
 305 \r
 306 static bool\r
 307 z80SurelyReturns(const lineNode *pl)\r
 308 {\r
 309   if(strcmp(pl->line, "\tret") == 0)\r
 310     return TRUE;\r
 311   return FALSE;\r
 312 }\r
 313 \r
 314 /*-----------------------------------------------------------------*/\r
 315 /* scan4op - "executes" and examines the assembler opcodes,        */\r
 316 /* follows conditional and un-conditional jumps.                   */\r
 317 /* Moreover it registers all passed labels.                        */\r
 318 /*                                                                 */\r
 319 /* Parameter:                                                      */\r
 320 /*    lineNode **pl                                                */\r
 321 /*       scanning starts from pl;                                  */\r
 322 /*       pl also returns the last scanned line                     */\r
 323 /*    const char *pReg                                             */\r
 324 /*       points to a register (e.g. "ar0"). scan4op() tests for    */\r
 325 /*       read or write operations with this register               */\r
 326 /*    const char *untilOp                                          */\r
 327 /*       points to NULL or a opcode (e.g. "push").                 */\r
 328 /*       scan4op() returns if it hits this opcode.                 */\r
 329 /*    lineNode **plCond                                            */\r
 330 /*       If a conditional branch is met plCond points to the       */\r
 331 /*       lineNode of the conditional branch                        */\r
 332 /*                                                                 */\r
 333 /* Returns:                                                        */\r
 334 /*    S4O_ABORT                                                    */\r
 335 /*       on error                                                  */\r
 336 /*    S4O_VISITED                                                  */\r
 337 /*       hit lineNode with "visited" flag set: scan4op() already   */\r
 338 /*       scanned this opcode.                                      */\r
 339 /*    S4O_FOUNDOPCODE                                              */\r
 340 /*       found opcode and operand, to which untilOp and pReg are   */\r
 341 /*       pointing to.                                              */\r
 342 /*    S4O_RD_OP, S4O_WR_OP                                         */\r
 343 /*       hit an opcode reading or writing from pReg                */\r
 344 /*    S4O_CONDJMP                                                  */\r
 345 /*       hit a conditional jump opcode. pl and plCond return the   */\r
 346 /*       two possible branches.                                    */\r
 347 /*    S4O_TERM                                                     */\r
 348 /*       acall, lcall, ret and reti "terminate" a scan.            */\r
 349 /*-----------------------------------------------------------------*/\r
 350 static S4O_RET\r
 351 scan4op (lineNode **pl, const char *what, const char *untilOp,\r
 352          lineNode **plCond)\r
 353 {\r
 354   for (; *pl; *pl = (*pl)->next)\r
 355     {\r
 356       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment || (*pl)->isLabel)\r
 357         continue;\r
 358       D(("Scanning %s for %s\n", (*pl)->line, what));\r
 359       /* don't optimize across inline assembler,\r
 360          e.g. isLabel doesn't work there */\r
 361       if ((*pl)->isInline)\r
 362         return S4O_ABORT;\r
 363 \r
 364       if ((*pl)->visited)\r
 365         return S4O_VISITED;\r
 366       (*pl)->visited = TRUE;\r
 367 \r
 368       if(z80MightRead(*pl, what))\r
 369         {\r
 370           D(("S4O_RD_OP\n"));\r
 371           return S4O_RD_OP;\r
 372         }\r
 373 \r
 374       if(z80UncondJump(*pl))\r
 375         {\r
 376           *pl = findLabel (*pl);\r
 377             if (!*pl)\r
 378               {\r
 379                 D(("S4O_ABORT\n"));\r
 380                 return S4O_ABORT;\r
 381               }\r
 382         }\r
 383       if(z80CondJump(*pl))\r
 384         {\r
 385           *plCond = findLabel (*pl);\r
 386           if (!*plCond)\r
 387             {\r
 388               D(("S4O_ABORT\n"));\r
 389               return S4O_ABORT;\r
 390             }\r
 391           D(("S4O_CONDJMP\n"));\r
 392           return S4O_CONDJMP;\r
 393         }\r
 394 \r
 395       if(z80SurelyWrites(*pl, what))\r
 396         {\r
 397           D(("S4O_WR_OP\n"));\r
 398           return S4O_WR_OP;\r
 399         }\r
 400 \r
 401       /* Don't need to check for de, hl since z80MightRead() does that */\r
 402       if(z80SurelyReturns(*pl))\r
 403         {\r
 404           D(("S4O_TERM\n"));\r
 405           return S4O_TERM;\r
 406         }\r
 407     }\r
 408   D(("S4O_ABORT\n"));\r
 409   return S4O_ABORT;\r
 410 }\r
 411 \r
 412 /*-----------------------------------------------------------------*/\r
 413 /* doTermScan - scan through area 2. This small wrapper handles:   */\r
 414 /* - action required on different return values                    */\r
 415 /* - recursion in case of conditional branches                     */\r
 416 /*-----------------------------------------------------------------*/\r
 417 static bool\r
 418 doTermScan (lineNode **pl, const char *what)\r
 419 {\r
 420   lineNode *plConditional;\r
 421 \r
 422   for (;; *pl = (*pl)->next)\r
 423     {\r
 424       switch (scan4op (pl, what, NULL, &plConditional))\r
 425         {\r
 426           case S4O_TERM:\r
 427           case S4O_VISITED:\r
 428           case S4O_WR_OP:\r
 429             /* all these are terminating condtions */\r
 430             return TRUE;\r
 431           case S4O_CONDJMP:\r
 432             /* two possible destinations: recurse */\r
 433               {\r
 434                 lineNode *pl2 = plConditional;\r
 435                 D(("CONDJMP trying other branch first\n"));\r
 436                 if (!doTermScan (&pl2, what))\r
 437                   return FALSE;\r
 438                 D(("Other branch OK.\n"));\r
 439               }\r
 440             continue;\r
 441           case S4O_RD_OP:\r
 442           default:\r
 443             /* no go */\r
 444             return FALSE;\r
 445         }\r
 446     }\r
 447 }\r
 448 \r
 449 static bool\r
 450 isReg(const char *what)\r
 451 {\r
 452   if(strcmp(what, "iyl") == 0 || strcmp(what, "iyh") == 0)\r
 453     return TRUE;\r
 454   if(strlen(what) != 1)\r
 455     return FALSE;\r
 456   switch(*what)\r
 457     {\r
 458     case 'a':\r
 459     case 'b':\r
 460     case 'c':\r
 461     case 'd':\r
 462     case 'e':\r
 463     case 'h':\r
 464     case 'l':\r
 465       return TRUE;\r
 466     }\r
 467   return FALSE;\r
 468 }\r
 469 \r
 470 static bool\r
 471 isRegPair(const char *what)\r
 472 {\r
 473   if(strlen(what) != 2)\r
 474     return FALSE;\r
 475   if(strcmp(what, "bc") == 0)\r
 476     return TRUE;\r
 477   if(strcmp(what, "de") == 0)\r
 478     return TRUE;\r
 479   if(strcmp(what, "hl") == 0)\r
 480     return TRUE;\r
 481   if(strcmp(what, "iy") == 0)\r
 482     return TRUE;\r
 483   return FALSE;\r
 484 }\r
 485 \r
 486 /* Check that what is never read after endPl. */\r
 487 \r
 488 bool\r
 489 z80notUsed (const char *what, lineNode *endPl, lineNode *head)\r
 490 {\r
 491   lineNode *pl;\r
 492   D(("Checking for %s\n", what));\r
 493   if(isRegPair(what))\r
 494     {\r
 495       char low[2], high[2];\r
 496       low[0] = what[1];\r
 497       high[0] = what[0];\r
 498       low[1] = 0;\r
 499       high[1] = 0;\r
 500       if(strcmp(what, "iy") == 0)\r
 501         return(z80notUsed("iyl", endPl, head) && z80notUsed("iyh", endPl, head));\r
 502       return(z80notUsed(low, endPl, head) && z80notUsed(high, endPl, head));\r
 503     }\r
 504 \r
 505   if(!isReg(what))\r
 506     return FALSE;\r
 507 \r
 508   _G.head = head;\r
 509 \r
 510   unvisitLines (_G.head);\r
 511 \r
 512   pl = endPl->next;\r
 513   if (!doTermScan (&pl, what))\r
 514     return FALSE;\r
 515 \r
 516   return TRUE;\r
 517 }\r
 518 \r