git.gag.com Git - debian/cc1111/blob - src/SDCCptropt.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCCptropt.c - source file for pointer arithmetic Optimizations
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21    In other words, you are welcome to use, share and improve this program.
  22    You are forbidden to forbid anyone else to use, share and improve
  23    what you give them.   Help stamp out software-hoarding!
  24 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27
  28 /*-----------------------------------------------------------------------*/
  29 /* findPointerGetSet - find the pointer get or set for a operand         */
  30 /*-----------------------------------------------------------------------*/
  31 static iCode *
  32 findPointerGetSet (iCode * sic, operand * op)
  33 {
  34   iCode *ic = sic;
  35
  36   for (; ic; ic = ic->next)
  37     {
  38       if ((POINTER_SET (ic) && isOperandEqual (op, IC_RESULT (ic))) ||
  39           (POINTER_GET (ic) && isOperandEqual (op, IC_LEFT (ic))))
  40         return ic;
  41
  42       /* if we find any other usage or definition of op null */
  43       if (IC_RESULT (ic) && isOperandEqual (IC_RESULT (ic), op))
  44         return NULL;
  45
  46       if (IC_RIGHT (ic) && isOperandEqual (IC_RIGHT (ic), op))
  47         return NULL;
  48
  49       if (IC_LEFT (ic) && isOperandEqual (IC_LEFT (ic), op))
  50         return NULL;
  51
  52     }
  53
  54   return NULL;
  55 }
  56
  57 static int pattern1 (iCode *sic)
  58 {
  59         /* this is what we do. look for sequences like
  60
  61         iTempX := _SOME_POINTER_;
  62         iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)      sic->next
  63         _SOME_POINTER_ := iTempY;                                               sic->next->next
  64         either
  65         iTempZ := @[iTempX];                                                    sic->next->next->next
  66         or
  67         *(iTempX) := ..something..                                              sic->next->next->next
  68         if we find this then transform this to
  69         iTempX := _SOME_POINTER_;
  70         either
  71         iTempZ := @[iTempX];
  72         or
  73         *(iTempX) := ..something..
  74         iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)
  75         _SOME_POINTER_ := iTempY; */
  76
  77         /* sounds simple enough so lets start , here I use -ve
  78            tests all the way to return if any test fails */
  79         iCode *pgs, *sh, *st;
  80
  81         if (!(sic->next && sic->next->next && sic->next->next->next))
  82                 return 0;
  83         if (sic->next->op != '+' && sic->next->op != '-')
  84                 return 0;
  85         if (!(sic->next->next->op == '=' &&
  86               !POINTER_SET (sic->next->next)))
  87                 return 0;
  88         if (!isOperandEqual (IC_LEFT (sic->next), IC_RIGHT (sic)) ||
  89             !IS_OP_LITERAL (IC_RIGHT (sic->next)))
  90                 return 0;
  91         if (operandLitValue (IC_RIGHT (sic->next)) !=
  92             getSize (operandType (IC_RIGHT (sic))->next))
  93                 return 0;
  94         if (!isOperandEqual (IC_RESULT (sic->next->next),
  95                              IC_RIGHT (sic)))
  96                 return 0;
  97         if (!isOperandEqual (IC_RESULT (sic->next), IC_RIGHT (sic->next->next)))
  98                 return 0;
  99         if (!(pgs = findPointerGetSet (sic->next->next, IC_RESULT (sic))))
 100                 return 0;
 101
 102         /* found the patter .. now do the transformation */
 103         sh = sic->next;
 104         st = sic->next->next;
 105
 106         /* take the two out of the chain */
 107         sic->next = st->next;
 108         st->next->prev = sic;
 109
 110         /* and put them after the pointer get/set icode */
 111         if ((st->next = pgs->next))
 112                 st->next->prev = st;
 113         pgs->next = sh;
 114         sh->prev = pgs;
 115         return 1;
 116 }
 117
 118 static int pattern2 (iCode *sic)
 119 {
 120         /* this is what we do. look for sequences like
 121
 122         iTempX := _SOME_POINTER_;
 123         iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)      sic->next
 124         iTempK := iTempY;                                                       sic->next->next
 125         _SOME_POINTER_ := iTempK;                                               sic->next->next->next
 126         either
 127         iTempZ := @[iTempX];                                                    sic->next->next->next->next
 128         or
 129         *(iTempX) := ..something..                                              sic->next->next->next->next
 130         if we find this then transform this to
 131         iTempX := _SOME_POINTER_;
 132         either
 133         iTempZ := @[iTempX];
 134         or
 135         *(iTempX) := ..something..
 136         iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)
 137         iTempK := iTempY;
 138         _SOME_POINTER_ := iTempK; */
 139
 140         /* sounds simple enough so lets start , here I use -ve
 141            tests all the way to return if any test fails */
 142         iCode *pgs, *sh, *st;
 143
 144         if (!(sic->next && sic->next->next && sic->next->next->next &&
 145               sic->next->next->next->next))
 146                 return 0;
 147
 148         /* yes I can OR them together and make one large if... but I have
 149            simple mind and like to keep things simple & readable */
 150         if (!(sic->next->op == '+' || sic->next->op == '-')) return 0;
 151         if (!isOperandEqual(IC_RIGHT(sic),IC_LEFT(sic->next))) return 0;
 152         if (!IS_OP_LITERAL (IC_RIGHT (sic->next))) return 0;
 153         if (operandLitValue (IC_RIGHT (sic->next)) !=
 154             getSize (operandType (IC_RIGHT (sic))->next)) return 0;
 155         if (!IS_ASSIGN_ICODE(sic->next->next)) return 0;
 156         if (!isOperandEqual(IC_RIGHT(sic->next->next),IC_RESULT(sic->next))) return 0;
 157         if (!IS_ASSIGN_ICODE(sic->next->next->next)) return 0;
 158         if (!isOperandEqual(IC_RIGHT(sic->next->next->next),IC_RESULT(sic->next->next))) return 0;
 159         if (!isOperandEqual(IC_RESULT(sic->next->next->next),IC_LEFT(sic->next))) return 0;
 160         if (!(pgs = findPointerGetSet (sic->next->next->next, IC_RESULT (sic)))) return 0;
 161
 162         /* found the patter .. now do the transformation */
 163         sh = sic->next;
 164         st = sic->next->next->next;
 165
 166         /* take the three out of the chain */
 167         sic->next = st->next;
 168         st->next->prev = sic;
 169
 170         /* and put them after the pointer get/set icode */
 171         if ((st->next = pgs->next))
 172                 st->next->prev = st;
 173         pgs->next = sh;
 174         sh->prev = pgs;
 175         return 1;
 176 }
 177
 178 /*-----------------------------------------------------------------------*/
 179 /* ptrPostIncDecOpts - will do some pointer post increment optimizations */
 180 /*                     this will help register allocation amongst others */
 181 /*-----------------------------------------------------------------------*/
 182 void
 183 ptrPostIncDecOpt (iCode * sic)
 184 {
 185         if (pattern1(sic)) return ;
 186         pattern2(sic);
 187 }
 188
 189 /*-----------------------------------------------------------------------*/
 190 /* addPattern1 - transform addition to pointer of variables              */
 191 /*-----------------------------------------------------------------------*/
 192 static int addPattern1(iCode *ic)
 193 {
 194         iCode *dic;
 195         operand *tmp;
 196         /* transform :
 197            iTempAA = iTempBB + iTempCC
 198            iTempDD = iTempAA + CONST
 199            to
 200            iTempAA = iTempBB + CONST
 201            iTempDD = iTempAA + iTempCC
 202         */
 203         if (!isOperandLiteral(IC_RIGHT(ic))) return 0;
 204         if ((dic=findBackwardDef(IC_LEFT(ic),ic->prev)) == NULL) return 0;
 205         if (bitVectnBitsOn(OP_SYMBOL(IC_RESULT(dic))->uses) > 1) return 0;
 206         if (dic->op != '+') return 0;
 207         tmp = IC_RIGHT(ic);
 208         IC_RIGHT(ic) = IC_RIGHT(dic);
 209         IC_RIGHT(dic) = tmp;
 210         return 1;
 211 }
 212
 213 /*-----------------------------------------------------------------------*/
 214 /* ptrAddition - optimize pointer additions                              */
 215 /*-----------------------------------------------------------------------*/
 216 int ptrAddition (iCode *sic)
 217 {
 218         if (addPattern1(sic)) return 1;
 219         return 0;
 220 }
 221
 222 /*--------------------------------------------------------------------*/
 223 /* ptrBaseRematSym - find the base symbol of a remat. pointer         */
 224 /*--------------------------------------------------------------------*/
 225 symbol *
 226 ptrBaseRematSym (symbol *ptrsym)
 227 {
 228   iCode * ric;
 229
 230   if (!ptrsym->remat)
 231     return NULL;
 232
 233   ric = ptrsym->rematiCode;
 234   while (ric)
 235     {
 236       if (ric->op == '+' || ric->op == '-')
 237         ric = OP_SYMBOL (IC_LEFT (ric))->rematiCode;
 238       else if (IS_CAST_ICODE (ric))
 239         ric = OP_SYMBOL (IC_RIGHT (ric))->rematiCode;
 240       else
 241         break;
 242     }
 243
 244   if (ric && IS_SYMOP (IC_LEFT (ric)))
 245     return OP_SYMBOL (IC_LEFT (ric));
 246   else
 247     return NULL;
 248 }
 249
 250
 251 /*--------------------------------------------------------------------*/
 252 /* ptrPseudoSymSafe - check to see if the conversion of the result of */
 253 /*   a pointerGet of a rematerializable pointer to a pseudo symbol is */
 254 /*   safe. Returns true if safe, or false if hazards were detected.   */
 255 /*--------------------------------------------------------------------*/
 256 int
 257 ptrPseudoSymSafe (symbol *sym, iCode *dic)
 258 {
 259   symbol * ptrsym;
 260   symbol * basesym;
 261   iCode * ric;
 262   iCode * ic;
 263   int ptrsymDclType;
 264   //int isGlobal;
 265
 266   assert(POINTER_GET (dic));
 267
 268   /* Can't if spills to this symbol are prohibited */
 269   if (sym->noSpilLoc)
 270     return 0;
 271
 272   /* Get the pointer */
 273   if (!IS_SYMOP (IC_LEFT (dic)))
 274     return 0;
 275   ptrsym = OP_SYMBOL (IC_LEFT (dic));
 276
 277   /* Must be a rematerializable pointer */
 278   if (!ptrsym->remat)
 279     return 0;
 280
 281   /* The pointer type must be uncasted */
 282   if (IS_CAST_ICODE (ptrsym->rematiCode))
 283     return 0;
 284
 285   /* The symbol's live range must not preceed its definition */
 286   if (dic->seq > sym->liveFrom)
 287     return 0;
 288
 289   /* Ok, this is a good candidate for a pseudo symbol.      */
 290   /* However, we must check for two hazards:                */
 291   /*   1) The symbol's live range must not include a CALL   */
 292   /*      or PCALL iCode.                                   */
 293   /*   2) The symbol's live range must not include any      */
 294   /*      writes to the variable the pointer rematerializes */
 295   /*      within (to avoid aliasing problems)               */
 296
 297   /* Find the base symbol the rematerialization is based on */
 298   ric = ptrsym->rematiCode;
 299   while (ric->op == '+' || ric->op == '-')
 300     ric = OP_SYMBOL (IC_LEFT (ric))->rematiCode;
 301   if (IS_CAST_ICODE(ric))
 302     return 0;
 303   basesym = OP_SYMBOL (IC_LEFT (ric));
 304
 305   //isGlobal = !basesym->islocal && !basesym->ismyparm;
 306   ptrsymDclType = aggrToPtrDclType (ptrsym->type, FALSE);
 307
 308   ic = dic->next;
 309   while (ic && ic->seq <= sym->liveTo)
 310     {
 311       if (!(SKIP_IC3 (ic) || ic->op == IFX))
 312         {
 313           /* Check for hazard #1 */
 314           if ((ic->op == CALL || ic->op == PCALL) /* && isGlobal */ )
 315             {
 316               if (ic->seq <= sym->liveTo)
 317                 return 0;
 318             }
 319           /* Check for hazard #2 */
 320           else if (POINTER_SET (ic))
 321             {
 322               symbol * ptrsym2 = OP_SYMBOL (IC_RESULT (ic));
 323
 324               if (ptrsym2->remat)
 325                 {
 326                   /* Must not be the same base symbol */
 327                   if (basesym == ptrBaseRematSym (ptrsym2))
 328                     return 0;
 329                 }
 330               else
 331                 {
 332                   int ptrsym2DclType = aggrToPtrDclType (ptrsym2->type, FALSE);
 333
 334                   /* Pointer must have no memory space in common */
 335                   if (ptrsym2DclType == ptrsymDclType
 336                       || ptrsym2DclType == GPOINTER
 337                       || ptrsymDclType == GPOINTER)
 338                     return 0;
 339                 }
 340             }
 341           else if (IC_RESULT (ic))
 342             {
 343               symbol * rsym = OP_SYMBOL (IC_RESULT (ic));
 344
 345               /* Make sure there is no conflict with another pseudo symbol */
 346               if (rsym->psbase == basesym)
 347                 return 0;
 348               if (rsym->isspilt && rsym->usl.spillLoc)
 349                 rsym = rsym->usl.spillLoc;
 350               if (rsym->psbase == basesym)
 351                 return 0;
 352             }
 353         }
 354
 355       if (ic->seq == sym->liveTo)
 356          break;
 357       ic = ic->next;
 358     }
 359
 360   /* If the live range went past the end of the defining basic */
 361   /* block, then a full analysis is too complicated to attempt */
 362   /* here. To be safe, we must assume the worst.               */
 363   if (!ic)
 364     return 0;
 365
 366   /* Ok, looks safe */
 367   return 1;
 368 }
 369
 370 /*--------------------------------------------------------------------*/
 371 /* ptrPseudoSymConvert - convert the result of a pointerGet to a      */
 372 /*   pseudo symbol. The pointer must be rematerializable.             */
 373 /*--------------------------------------------------------------------*/
 374 void
 375 ptrPseudoSymConvert (symbol *sym, iCode *dic, char *name)
 376 {
 377   symbol *psym = newSymbol (name, 1);
 378   psym->psbase = ptrBaseRematSym (OP_SYMBOL (IC_LEFT (dic)));
 379   psym->type = sym->type;
 380   psym->etype = psym->psbase->etype;
 381
 382   strcpy (psym->rname, psym->name);
 383   sym->isspilt = 1;
 384   sym->usl.spillLoc = psym;
 385 #if 0 // an alternative fix for bug #480076
 386   /* now this is a useless assignment to itself */
 387   remiCodeFromeBBlock (ebbs, dic);
 388 #else
 389   /* now this really is an assignment to itself, make it so;
 390      it will be optimized out later */
 391   dic->op='=';
 392   ReplaceOpWithCheaperOp(&IC_RIGHT(dic), IC_RESULT(dic));
 393   IC_LEFT(dic)=NULL;
 394 #endif
 395 }