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