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 *
findPointerGetSet(iCode * sic,operand * op)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
pattern1(iCode * sic,eBBlock * ebb)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
pattern2(iCode * sic,eBBlock * ebb)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
ptrPostIncDecOpt(iCode * sic,eBBlock * ebb)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
addPattern1(iCode * ic)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
ptrAddition(iCode * sic)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 *
ptrBaseRematSym(symbol * ptrsym)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
ptrPseudoSymSafe(symbol * sym,iCode * dic)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
ptrPseudoSymConvert(symbol * sym,iCode * dic,const char * name)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 }
421