sdcc/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))) || (POINTER_GET (ic) && isOperandEqual (op, IC_LEFT (ic))))
  39         return ic;
  40
  41       /* if we find any other usage or definition of op null */
  42       if (IC_RESULT (ic) && isOperandEqual (IC_RESULT (ic), op))
  43         return NULL;
  44
  45       if (IC_RIGHT (ic) && isOperandEqual (IC_RIGHT (ic), op))
  46         return NULL;
  47
  48       if (IC_LEFT (ic) && isOperandEqual (IC_LEFT (ic), op))
  49         return NULL;
  50
  51     }
  52
  53   return NULL;
  54 }
  55
  56 static int
  57 pattern1 (iCode * sic, eBBlock * ebb)
  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 let's start , here I use negative
  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 == '=' && !POINTER_SET (sic->next->next)))
  86     return 0;
  87   if (!isOperandEqual (IC_LEFT (sic->next), IC_RIGHT (sic)) || !IS_OP_LITERAL (IC_RIGHT (sic->next)))
  88     return 0;
  89   if (operandLitValue (IC_RIGHT (sic->next)) != getSize (operandType (IC_RIGHT (sic))->next))
  90     return 0;
  91   if (!isOperandEqual (IC_RESULT (sic->next->next), IC_RIGHT (sic)))
  92     return 0;
  93   if (!isOperandEqual (IC_RESULT (sic->next), IC_RIGHT (sic->next->next)))
  94     return 0;
  95   if (!(pgs = findPointerGetSet (sic->next->next, IC_RESULT (sic))))
  96     return 0;
  97
  98   /* found the pattern .. now do the transformation */
  99   sh = sic->next;
 100   st = sic->next->next;
 101
 102   /* take the two out of the chain */
 103   sic->next = st->next;
 104   st->next->prev = sic;
 105
 106   /* and put them after the pointer get/set icode */
 107   if ((st->next = pgs->next))
 108     st->next->prev = st;
 109   if (!st->next)
 110     ebb->ech = st;
 111   pgs->next = sh;
 112   sh->prev = pgs;
 113   return 1;
 114 }
 115
 116 static int
 117 pattern2 (iCode * sic, eBBlock * ebb)
 118 {
 119   /* this is what we do. look for sequences like
 120
 121      iTempX := _SOME_POINTER_;
 122      iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)      sic->next
 123      iTempK := iTempY;                                                       sic->next->next
 124      _SOME_POINTER_ := iTempK;                                               sic->next->next->next
 125      either
 126      iTempZ := @[iTempX];                                                    sic->next->next->next->next
 127      or
 128      *(iTempX) := ..something..                                              sic->next->next->next->next
 129      if we find this then transform this to
 130      iTempX := _SOME_POINTER_;
 131      either
 132      iTempZ := @[iTempX];
 133      or
 134      *(iTempX) := ..something..
 135      iTempY := _SOME_POINTER_ + nn ;   nn  = sizeof (pointed to object)
 136      iTempK := iTempY;
 137      _SOME_POINTER_ := iTempK; */
 138
 139   /* sounds simple enough so let's start , here I use negative
 140      tests all the way to return if any test fails */
 141   iCode *pgs, *sh, *st;
 142
 143   if (!(sic->next && sic->next->next && sic->next->next->next && sic->next->next->next->next))
 144     return 0;
 145
 146   /* yes I can OR them together and make one large if... but I have
 147      simple mind and like to keep things simple & readable */
 148   if (!(sic->next->op == '+' || sic->next->op == '-'))
 149     return 0;
 150   if (!isOperandEqual (IC_RIGHT (sic), IC_LEFT (sic->next)))
 151     return 0;
 152   if (!IS_OP_LITERAL (IC_RIGHT (sic->next)))
 153     return 0;
 154   if (operandLitValue (IC_RIGHT (sic->next)) != getSize (operandType (IC_RIGHT (sic))->next))
 155     return 0;
 156   if (!IS_ASSIGN_ICODE (sic->next->next))
 157     return 0;
 158   if (!isOperandEqual (IC_RIGHT (sic->next->next), IC_RESULT (sic->next)))
 159     return 0;
 160   if (!IS_ASSIGN_ICODE (sic->next->next->next))
 161     return 0;
 162   if (!isOperandEqual (IC_RIGHT (sic->next->next->next), IC_RESULT (sic->next->next)))
 163     return 0;
 164   if (!isOperandEqual (IC_RESULT (sic->next->next->next), IC_LEFT (sic->next)))
 165     return 0;
 166   if (!(pgs = findPointerGetSet (sic->next->next->next, IC_RESULT (sic))))
 167     return 0;
 168
 169   /* found the pattern .. now do the transformation */
 170   sh = sic->next;
 171   st = sic->next->next->next;
 172
 173   /* take the three out of the chain */
 174   sic->next = st->next;
 175   st->next->prev = sic;
 176
 177   /* and put them after the pointer get/set icode */
 178   if ((st->next = pgs->next))
 179     st->next->prev = st;
 180   if (!st->next)
 181     ebb->ech = st;
 182   pgs->next = sh;
 183   sh->prev = pgs;
 184   return 1;
 185 }
 186
 187 /*-----------------------------------------------------------------------*/
 188 /* ptrPostIncDecOpts - will do some pointer post increment optimizations */
 189 /*                     this will help register allocation amongst others */
 190 /*-----------------------------------------------------------------------*/
 191 void
 192 ptrPostIncDecOpt (iCode * sic, eBBlock * ebb)
 193 {
 194   if (pattern1 (sic, ebb))
 195     return;
 196   pattern2 (sic, ebb);
 197 }
 198
 199 /*-----------------------------------------------------------------------*/
 200 /* addPattern1 - transform addition to pointer of variables              */
 201 /*-----------------------------------------------------------------------*/
 202 static int
 203 addPattern1 (iCode * ic)
 204 {
 205   iCode *dic;
 206   operand *tmp;
 207   /* transform :
 208      iTempAA = iTempBB + iTempCC
 209      iTempDD = iTempAA + CONST
 210      to
 211      iTempAA = iTempBB + CONST
 212      iTempDD = iTempAA + iTempCC
 213    */
 214   if (!isOperandLiteral (IC_RIGHT (ic)))
 215     return 0;
 216   if ((dic = findBackwardDef (IC_LEFT (ic), ic->prev)) == NULL)
 217     return 0;
 218   if (bitVectnBitsOn (OP_SYMBOL (IC_RESULT (dic))->uses) > 1)
 219     return 0;
 220   if (dic->op != '+')
 221     return 0;
 222   tmp = IC_RIGHT (ic);
 223   IC_RIGHT (ic) = IC_RIGHT (dic);
 224   IC_RIGHT (dic) = tmp;
 225   return 1;
 226 }
 227
 228 /*-----------------------------------------------------------------------*/
 229 /* ptrAddition - optimize pointer additions                              */
 230 /*-----------------------------------------------------------------------*/
 231 int
 232 ptrAddition (iCode * sic)
 233 {
 234   if (addPattern1 (sic))
 235     return 1;
 236   return 0;
 237 }
 238
 239 /*--------------------------------------------------------------------*/
 240 /* ptrBaseRematSym - find the base symbol of a remat. pointer         */
 241 /*--------------------------------------------------------------------*/
 242 symbol *
 243 ptrBaseRematSym (symbol * ptrsym)
 244 {
 245   iCode *ric;
 246
 247   if (!ptrsym->remat)
 248     return NULL;
 249
 250   ric = ptrsym->rematiCode;
 251   while (ric)
 252     {
 253       if (ric->op == '+' || ric->op == '-')
 254         ric = OP_SYMBOL (IC_LEFT (ric))->rematiCode;
 255       else if (IS_CAST_ICODE (ric))
 256         ric = OP_SYMBOL (IC_RIGHT (ric))->rematiCode;
 257       else
 258         break;
 259     }
 260
 261   if (ric && IS_SYMOP (IC_LEFT (ric)))
 262     return OP_SYMBOL (IC_LEFT (ric));
 263   else
 264     return NULL;
 265 }
 266
 267
 268 /*--------------------------------------------------------------------*/
 269 /* ptrPseudoSymSafe - check to see if the conversion of the result of */
 270 /*   a pointerGet of a rematerializable pointer to a pseudo symbol is */
 271 /*   safe. Returns true if safe, or false if hazards were detected.   */
 272 /*--------------------------------------------------------------------*/
 273 int
 274 ptrPseudoSymSafe (symbol * sym, iCode * dic)
 275 {
 276   symbol *ptrsym;
 277   symbol *basesym;
 278   iCode *ric;
 279   iCode *ic;
 280   int ptrsymDclType;
 281   //int isGlobal;
 282
 283   assert (POINTER_GET (dic));
 284
 285   /* Can't if spills to this symbol are prohibited */
 286   if (sym->noSpilLoc)
 287     return 0;
 288
 289   /* Get the pointer */
 290   if (!IS_SYMOP (IC_LEFT (dic)))
 291     return 0;
 292   ptrsym = OP_SYMBOL (IC_LEFT (dic));
 293
 294   /* Must be a rematerializable pointer */
 295   if (!ptrsym->remat)
 296     return 0;
 297
 298   /* The pointer type must be uncasted */
 299   if (IS_CAST_ICODE (ptrsym->rematiCode))
 300     return 0;
 301
 302   /* The symbol's live range must not preceed its definition */
 303   if (dic->seq > sym->liveFrom)
 304     return 0;
 305
 306   /* Ok, this is a good candidate for a pseudo symbol.      */
 307   /* However, we must check for two hazards:                */
 308   /*   1) The symbol's live range must not include a CALL   */
 309   /*      or PCALL iCode.                                   */
 310   /*   2) The symbol's live range must not include any      */
 311   /*      writes to the variable the pointer rematerializes */
 312   /*      within (to avoid aliasing problems)               */
 313
 314   /* Find the base symbol the rematerialization is based on */
 315   ric = ptrsym->rematiCode;
 316   while (ric->op == '+' || ric->op == '-')
 317     ric = OP_SYMBOL (IC_LEFT (ric))->rematiCode;
 318   if (IS_CAST_ICODE (ric))
 319     return 0;
 320   basesym = OP_SYMBOL (IC_LEFT (ric));
 321
 322   //isGlobal = !basesym->islocal && !basesym->ismyparm;
 323   ptrsymDclType = aggrToPtrDclType (ptrsym->type, FALSE);
 324
 325   ic = dic->next;
 326   while (ic && ic->seq <= sym->liveTo)
 327     {
 328       if (!(SKIP_IC3 (ic) || ic->op == IFX))
 329         {
 330           /* Check for hazard #1 */
 331           if ((ic->op == CALL || ic->op == PCALL) /* && isGlobal */ )
 332             {
 333               if (ic->seq <= sym->liveTo)
 334                 return 0;
 335             }
 336           /* Check for hazard #2 */
 337           else if (POINTER_SET (ic))
 338             {
 339               symbol *ptrsym2;
 340
 341               if (!IS_SYMOP (IC_RESULT (ic)))
 342                 return 0;
 343
 344               ptrsym2 = OP_SYMBOL (IC_RESULT (ic));
 345
 346               if (ptrsym2->remat)
 347                 {
 348                   /* Must not be the same base symbol */
 349                   if (basesym == ptrBaseRematSym (ptrsym2))
 350                     return 0;
 351                 }
 352               else
 353                 {
 354                   int ptrsym2DclType = aggrToPtrDclType (ptrsym2->type, FALSE);
 355
 356                   /* Pointer must have no memory space in common */
 357                   if (ptrsym2DclType == ptrsymDclType || ptrsym2DclType == GPOINTER || ptrsymDclType == GPOINTER)
 358                     return 0;
 359                 }
 360             }
 361           else if (IC_RESULT (ic))
 362             {
 363               symbol *rsym;
 364
 365               if (!IS_SYMOP (IC_RESULT (ic)))
 366                 return 0;
 367
 368               rsym = OP_SYMBOL (IC_RESULT (ic));
 369
 370               /* Make sure there is no conflict with another pseudo symbol */
 371               if (rsym->psbase == basesym)
 372                 return 0;
 373               if (rsym->isspilt && rsym->usl.spillLoc)
 374                 rsym = rsym->usl.spillLoc;
 375               if (rsym->psbase == basesym)
 376                 return 0;
 377             }
 378         }
 379
 380       if (ic->seq == sym->liveTo)
 381         break;
 382       ic = ic->next;
 383     }
 384
 385   /* If the live range went past the end of the defining basic */
 386   /* block, then a full analysis is too complicated to attempt */
 387   /* here. To be safe, we must assume the worst.               */
 388   if (!ic)
 389     return 0;
 390
 391   /* Ok, looks safe */
 392   return 1;
 393 }
 394
 395 /*--------------------------------------------------------------------*/
 396 /* ptrPseudoSymConvert - convert the result of a pointerGet to a      */
 397 /*   pseudo symbol. The pointer must be rematerializable.             */
 398 /*--------------------------------------------------------------------*/
 399 void
 400 ptrPseudoSymConvert (symbol * sym, iCode * dic, const char *name)
 401 {
 402   symbol *psym = newSymbol (name, 1);
 403   psym->psbase = ptrBaseRematSym (OP_SYMBOL (IC_LEFT (dic)));
 404   psym->type = sym->type;
 405   psym->etype = psym->psbase->etype;
 406
 407   strcpy (psym->rname, psym->name);
 408   sym->isspilt = 1;
 409   sym->usl.spillLoc = psym;
 410 #if 0                           // an alternative fix for bug #480076
 411   /* now this is a useless assignment to itself */
 412   remiCodeFromeBBlock (ebbs, dic);
 413 #else
 414   /* now this really is an assignment to itself, make it so;
 415      it will be optimized out later */
 416   dic->op = '=';
 417   ReplaceOpWithCheaperOp (&IC_RIGHT (dic), IC_RESULT (dic));
 418   IC_LEFT (dic) = NULL;
 419 #endif
 420 }