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 /* Check if reading arg implies reading what. */
 196 static bool argCont(const char *arg, const char *what)
 197 {
 198         if(arg[0] == '#')
 199                 return FALSE;
 200         return(strstr(arg, what));;
 201 }
 202
 203 static bool
 204 z80MightRead(const lineNode *pl, const char *what)
 205 {
 206   if(strcmp(what, "iyl") == 0 || strcmp(what, "iyh") == 0)
 207     what = "iy";
 208
 209   if(strcmp(pl->line, "call\t__initrleblock") == 0)
 210     return TRUE;
 211
 212   if(strncmp(pl->line, "call\t", 5) == 0 && strchr(pl->line, ',') == 0)
 213     return FALSE;
 214
 215   if(strncmp(pl->line, "ret", 3) == 0 && !isReturned(what))
 216     return FALSE;
 217
 218   if(strcmp(pl->line, "ex\tde,hl") == 0 && strchr(what, 'h') == 0 && strchr(what, 'l') == 0 && strchr(what, 'd') == 0&& strchr(what, 'e') == 0)
 219     return FALSE;
 220   if(strncmp(pl->line, "ld\t", 3) == 0)
 221     {
 222       if(strstr(strchr(pl->line, ','), what) && strchr(pl->line, ',')[1] != '#')
 223         return TRUE;
 224       if(*(strchr(pl->line, ',') - 1) == ')' && strstr(pl->line + 3, what) && (strchr(pl->line, '#') == 0 || strchr(pl->line, '#') > strchr(pl->line, ',')))
 225         return TRUE;
 226       return FALSE;
 227     }
 228
 229   if(strcmp(pl->line, "xor\ta,a") == 0)
 230     return FALSE;
 231
 232   if(strncmp(pl->line, "adc\t", 4) == 0 ||
 233     strncmp(pl->line, "add\t", 4) == 0 ||
 234     strncmp(pl->line, "and\t", 4) == 0 ||
 235     strncmp(pl->line, "sbc\t", 4) == 0 ||
 236     strncmp(pl->line, "sub\t", 4) == 0 ||
 237     strncmp(pl->line, "xor\t", 4) == 0)
 238     {
 239       if(argCont(pl->line + 4, what))
 240         return TRUE;
 241       if(strstr(pl->line + 4, "hl") == 0 && strcmp("a", what) == 0)
 242         return TRUE;
 243       return FALSE;
 244     }
 245
 246   if(strncmp(pl->line, "or\t", 3) == 0)
 247     {
 248       if(argCont(pl->line + 3, what))
 249         return TRUE;
 250       if(strcmp("a", what) == 0)
 251         return TRUE;
 252       return FALSE;
 253     }
 254
 255   if(strncmp(pl->line, "pop\t", 4) == 0)
 256     return FALSE;
 257
 258   if(strncmp(pl->line, "push\t", 5) == 0)
 259     return(strstr(pl->line + 5, what) != 0);
 260
 261   if(
 262     strncmp(pl->line, "dec\t", 4) == 0 ||
 263     strncmp(pl->line, "inc\t", 4) == 0 ||
 264     strncmp(pl->line, "rl\t", 4) == 0 ||
 265     strncmp(pl->line, "rr\t", 4) == 0 ||
 266     strncmp(pl->line, "sla\t", 4) == 0 ||
 267     strncmp(pl->line, "sra\t", 4) == 0 ||
 268     strncmp(pl->line, "srl\t", 4) == 0)
 269     {
 270        return (argCont(pl->line + 4, what));
 271     }
 272
 273   if(
 274     strncmp(pl->line, "rl\t", 3) == 0 ||
 275     strncmp(pl->line, "rr\t", 3) == 0)
 276     {
 277        return (argCont(pl->line + 3, what));
 278     }
 279
 280   if(strncmp(pl->line, "jp\t", 3) == 0 ||
 281     (bool)(strncmp(pl->line, "jr\t", 3)) == 0)
 282     return FALSE;
 283
 284   if(strncmp(pl->line, "djnz\t", 5) == 0)
 285     return(strchr(what, 'b') != 0);
 286
 287   if(strncmp(pl->line, "rla", 3) == 0 ||
 288     strncmp(pl->line, "rlca", 4) == 0)
 289     return(strcmp(what, "a") == 0);
 290
 291   return TRUE;
 292 }
 293
 294 static bool
 295 z80UncondJump(const lineNode *pl)
 296 {
 297   if((strncmp(pl->line, "jp\t", 3) == 0 ||
 298     strncmp(pl->line, "jr\t", 3) == 0) && strchr(pl->line, ',') == 0)
 299     return TRUE;
 300   return FALSE;
 301 }
 302
 303 static bool
 304 z80CondJump(const lineNode *pl)
 305 {
 306   if(((strncmp(pl->line, "jp\t", 3) == 0 ||
 307     strncmp(pl->line, "jr\t", 3) == 0) && strchr(pl->line, ',') != 0) ||
 308     strncmp(pl->line, "djnz\t", 5) == 0)
 309     return TRUE;
 310   return FALSE;
 311 }
 312
 313 static bool
 314 z80SurelyWrites(const lineNode *pl, const char *what)
 315 {
 316   if(strcmp(pl->line, "xor\ta,a") == 0 && strcmp(what, "a") == 0)
 317     return TRUE;
 318   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "hl", 2) == 0 && (what[0] == 'h' || what[0] == 'l'))
 319     return TRUE;
 320   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "de", 2) == 0 && (what[0] == 'd' || what[0] == 'e'))
 321     return TRUE;
 322   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, "bc", 2) == 0 && (what[0] == 'b' || what[0] == 'c'))
 323     return TRUE;
 324   if(strncmp(pl->line, "ld\t", 3) == 0 && strncmp(pl->line + 3, what, strlen(what)) == 0 && pl->line[3 + strlen(what)] == ',')
 325     return TRUE;
 326   if(strncmp(pl->line, "pop\t", 4) == 0 && strstr(pl->line + 4, what))
 327     return TRUE;
 328   if(strncmp(pl->line, "call\t", 5) == 0 && strchr(pl->line, ',') == 0)
 329     return TRUE;
 330   if(strcmp(pl->line, "ret") == 0)
 331     return TRUE;
 332   if(strncmp(pl->line, "ld\tiy", 5) == 0 && strncmp(what, "iy", 2) == 0)
 333     return TRUE;
 334   return FALSE;
 335 }
 336
 337 static bool
 338 z80SurelyReturns(const lineNode *pl)
 339 {
 340   if(strcmp(pl->line, "\tret") == 0)
 341     return TRUE;
 342   return FALSE;
 343 }
 344
 345 /*-----------------------------------------------------------------*/
 346 /* scan4op - "executes" and examines the assembler opcodes,        */
 347 /* follows conditional and un-conditional jumps.                   */
 348 /* Moreover it registers all passed labels.                        */
 349 /*                                                                 */
 350 /* Parameter:                                                      */
 351 /*    lineNode **pl                                                */
 352 /*       scanning starts from pl;                                  */
 353 /*       pl also returns the last scanned line                     */
 354 /*    const char *pReg                                             */
 355 /*       points to a register (e.g. "ar0"). scan4op() tests for    */
 356 /*       read or write operations with this register               */
 357 /*    const char *untilOp                                          */
 358 /*       points to NULL or a opcode (e.g. "push").                 */
 359 /*       scan4op() returns if it hits this opcode.                 */
 360 /*    lineNode **plCond                                            */
 361 /*       If a conditional branch is met plCond points to the       */
 362 /*       lineNode of the conditional branch                        */
 363 /*                                                                 */
 364 /* Returns:                                                        */
 365 /*    S4O_ABORT                                                    */
 366 /*       on error                                                  */
 367 /*    S4O_VISITED                                                  */
 368 /*       hit lineNode with "visited" flag set: scan4op() already   */
 369 /*       scanned this opcode.                                      */
 370 /*    S4O_FOUNDOPCODE                                              */
 371 /*       found opcode and operand, to which untilOp and pReg are   */
 372 /*       pointing to.                                              */
 373 /*    S4O_RD_OP, S4O_WR_OP                                         */
 374 /*       hit an opcode reading or writing from pReg                */
 375 /*    S4O_CONDJMP                                                  */
 376 /*       hit a conditional jump opcode. pl and plCond return the   */
 377 /*       two possible branches.                                    */
 378 /*    S4O_TERM                                                     */
 379 /*       acall, lcall, ret and reti "terminate" a scan.            */
 380 /*-----------------------------------------------------------------*/
 381 static S4O_RET
 382 scan4op (lineNode **pl, const char *what, const char *untilOp,
 383          lineNode **plCond)
 384 {
 385   for (; *pl; *pl = (*pl)->next)
 386     {
 387       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment || (*pl)->isLabel)
 388         continue;
 389       D(("Scanning %s for %s\n", (*pl)->line, what));
 390       /* don't optimize across inline assembler,
 391          e.g. isLabel doesn't work there */
 392       if ((*pl)->isInline)
 393         return S4O_ABORT;
 394
 395       if ((*pl)->visited)
 396         return S4O_VISITED;
 397       (*pl)->visited = TRUE;
 398
 399       if(z80MightRead(*pl, what))
 400         {
 401           D(("S4O_RD_OP\n"));
 402           return S4O_RD_OP;
 403         }
 404
 405       if(z80UncondJump(*pl))
 406         {
 407           *pl = findLabel (*pl);
 408             if (!*pl)
 409               {
 410                 D(("S4O_ABORT\n"));
 411                 return S4O_ABORT;
 412               }
 413         }
 414       if(z80CondJump(*pl))
 415         {
 416           *plCond = findLabel (*pl);
 417           if (!*plCond)
 418             {
 419               D(("S4O_ABORT\n"));
 420               return S4O_ABORT;
 421             }
 422           D(("S4O_CONDJMP\n"));
 423           return S4O_CONDJMP;
 424         }
 425
 426       if(z80SurelyWrites(*pl, what))
 427         {
 428           D(("S4O_WR_OP\n"));
 429           return S4O_WR_OP;
 430         }
 431
 432       /* Don't need to check for de, hl since z80MightRead() does that */
 433       if(z80SurelyReturns(*pl))
 434         {
 435           D(("S4O_TERM\n"));
 436           return S4O_TERM;
 437         }
 438     }
 439   D(("S4O_ABORT\n"));
 440   return S4O_ABORT;
 441 }
 442
 443 /*-----------------------------------------------------------------*/
 444 /* doTermScan - scan through area 2. This small wrapper handles:   */
 445 /* - action required on different return values                    */
 446 /* - recursion in case of conditional branches                     */
 447 /*-----------------------------------------------------------------*/
 448 static bool
 449 doTermScan (lineNode **pl, const char *what)
 450 {
 451   lineNode *plConditional;
 452
 453   for (;; *pl = (*pl)->next)
 454     {
 455       switch (scan4op (pl, what, NULL, &plConditional))
 456         {
 457           case S4O_TERM:
 458           case S4O_VISITED:
 459           case S4O_WR_OP:
 460             /* all these are terminating condtions */
 461             return TRUE;
 462           case S4O_CONDJMP:
 463             /* two possible destinations: recurse */
 464               {
 465                 lineNode *pl2 = plConditional;
 466                 D(("CONDJMP trying other branch first\n"));
 467                 if (!doTermScan (&pl2, what))
 468                   return FALSE;
 469                 D(("Other branch OK.\n"));
 470               }
 471             continue;
 472           case S4O_RD_OP:
 473           default:
 474             /* no go */
 475             return FALSE;
 476         }
 477     }
 478 }
 479
 480 static bool
 481 isReg(const char *what)
 482 {
 483   if(strcmp(what, "iyl") == 0 || strcmp(what, "iyh") == 0)
 484     return TRUE;
 485   if(strlen(what) != 1)
 486     return FALSE;
 487   switch(*what)
 488     {
 489     case 'a':
 490     case 'b':
 491     case 'c':
 492     case 'd':
 493     case 'e':
 494     case 'h':
 495     case 'l':
 496       return TRUE;
 497     }
 498   return FALSE;
 499 }
 500
 501 static bool
 502 isRegPair(const char *what)
 503 {
 504   if(strlen(what) != 2)
 505     return FALSE;
 506   if(strcmp(what, "bc") == 0)
 507     return TRUE;
 508   if(strcmp(what, "de") == 0)
 509     return TRUE;
 510   if(strcmp(what, "hl") == 0)
 511     return TRUE;
 512   if(strcmp(what, "iy") == 0)
 513     return TRUE;
 514   return FALSE;
 515 }
 516
 517 /* Check that what is never read after endPl. */
 518
 519 bool
 520 z80notUsed (const char *what, lineNode *endPl, lineNode *head)
 521 {
 522   lineNode *pl;
 523   D(("Checking for %s\n", what));
 524   if(isRegPair(what))
 525     {
 526       char low[2], high[2];
 527       low[0] = what[1];
 528       high[0] = what[0];
 529       low[1] = 0;
 530       high[1] = 0;
 531       if(strcmp(what, "iy") == 0)
 532         return(z80notUsed("iyl", endPl, head) && z80notUsed("iyh", endPl, head));
 533       return(z80notUsed(low, endPl, head) && z80notUsed(high, endPl, head));
 534     }
 535
 536   if(!isReg(what))
 537     return FALSE;
 538
 539   _G.head = head;
 540
 541   unvisitLines (_G.head);
 542
 543   pl = endPl->next;
 544   if (!doTermScan (&pl, what))
 545     return FALSE;
 546
 547   return TRUE;
 548 }
 549