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