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