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

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