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