1 /*-------------------------------------------------------------------------
2
3 SDCClrange.c - source file for live range computations
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 #include "limits.h"
28
29 int iCodeSeq = 0;
30 hTab *liveRanges = NULL;
31 hTab *iCodehTab = NULL;
32 hTab *iCodeSeqhTab = NULL;
33
34 /* all symbols, for which the previous definition is searched
35 and warning is emitted if there's none. */
36 #define IS_AUTOSYM(op) (IS_ITEMP(op) || \
37 (IS_SYMOP(op) && IS_AUTO(OP_SYMBOL (op)) && !IS_PARM(op)))
38
39 /*-----------------------------------------------------------------*/
40 /* hashiCodeKeys - add all iCodes to the hash table */
41 /*-----------------------------------------------------------------*/
42 void
hashiCodeKeys(eBBlock ** ebbs,int count)43 hashiCodeKeys (eBBlock ** ebbs, int count)
44 {
45 int i;
46
47 for (i = 0; i < count; i++)
48 {
49 iCode *ic;
50 for (ic = ebbs[i]->sch; ic; ic = ic->next)
51 hTabAddItem (&iCodehTab, ic->key, ic);
52 }
53 }
54
55 /*-----------------------------------------------------------------*/
56 /* sequenceiCode - creates a sequence number for the iCode & add */
57 /*-----------------------------------------------------------------*/
58 static void
sequenceiCode(eBBlock ** ebbs,int count)59 sequenceiCode (eBBlock ** ebbs, int count)
60 {
61 int i;
62
63 for (i = 0; i < count; i++)
64 {
65
66 iCode *ic;
67 ebbs[i]->fSeq = iCodeSeq + 1;
68 for (ic = ebbs[i]->sch; ic; ic = ic->next)
69 {
70 ic->seq = ++iCodeSeq;
71 ic->depth = ebbs[i]->depth;
72 //hTabAddItem (&iCodehTab, ic->key, ic);
73 hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
74 }
75 ebbs[i]->lSeq = iCodeSeq;
76 }
77 }
78
79 /*-----------------------------------------------------------------*/
80 /* setFromRange - sets the from range of a given operand */
81 /*-----------------------------------------------------------------*/
82 #if 0
83 static void
84 setFromRange (operand * op, int from)
85 {
86 /* only for compiler defined temporaries */
87 if (!IS_ITEMP (op))
88 return;
89
90 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
91
92 if (op->isaddr)
93 OP_SYMBOL (op)->isptr = 1;
94
95 if (!OP_LIVEFROM (op) ||
96 OP_LIVEFROM (op) > from)
97 OP_LIVEFROM (op) = from;
98 }
99 #endif
100
101 /*-----------------------------------------------------------------*/
102 /* setToRange - set the range to for an operand */
103 /*-----------------------------------------------------------------*/
104 void
setToRange(operand * op,int to,bool check)105 setToRange (operand * op, int to, bool check)
106 {
107 /* only for compiler defined temps */
108 if (!IS_ITEMP (op))
109 return;
110
111 OP_SYMBOL (op)->key = op->key;
112 hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
113
114 if (op->isaddr)
115 OP_SYMBOL (op)->isptr = 1;
116
117 if (check)
118 if (!OP_LIVETO (op))
119 OP_LIVETO (op) = to;
120 else;
121 else
122 OP_LIVETO (op) = to;
123 }
124
125 /*-----------------------------------------------------------------*/
126 /* setFromRange - sets the from range of a given operand */
127 /*-----------------------------------------------------------------*/
128 static void
setLiveFrom(symbol * sym,int from)129 setLiveFrom (symbol * sym, int from)
130 {
131 if (!sym->liveFrom || sym->liveFrom > from)
132 sym->liveFrom = from;
133 }
134
135 /*-----------------------------------------------------------------*/
136 /* setToRange - set the range to for an operand */
137 /*-----------------------------------------------------------------*/
138 static void
setLiveTo(symbol * sym,int to)139 setLiveTo (symbol *sym, int to)
140 {
141 if (!sym->liveTo || sym->liveTo < to)
142 sym->liveTo = to;
143 }
144
145 /*-----------------------------------------------------------------*/
146 /* markLiveRanges - for each operand mark the liveFrom & liveTo */
147 /*-----------------------------------------------------------------*/
148 static void
markLiveRanges(eBBlock ** ebbs,int count)149 markLiveRanges (eBBlock **ebbs, int count)
150 {
151 int i, key;
152 symbol *sym;
153
154 for (i = 0; i < count; i++)
155 {
156 iCode *ic;
157
158 for (ic = ebbs[i]->sch; ic; ic = ic->next)
159 {
160 if (ic->op == CALL || ic->op == PCALL)
161 if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
162 bitVectUnSetBit (ebbs[i]->defSet, ic->key);
163
164 /* for all iTemps alive at this iCode */
165 for (key = 1; key < ic->rlive->size; key++)
166 {
167 if (!bitVectBitValue(ic->rlive, key))
168 continue;
169
170 sym = hTabItemWithKey(liveRanges, key);
171 setLiveTo(sym, ic->seq);
172 setLiveFrom(sym, ic->seq);
173 }
174
175 }
176 }
177 }
178
179 /*-----------------------------------------------------------------*/
180 /* markAlive - marks the operand as alive between sic and eic */
181 /*-----------------------------------------------------------------*/
182 static void
markAlive(iCode * sic,iCode * eic,int key)183 markAlive (iCode * sic, iCode * eic, int key)
184 {
185 iCode *dic;
186
187 for (dic = sic; dic != eic->next; dic = dic->next)
188 {
189 dic->rlive = bitVectSetBit (dic->rlive, key);
190 }
191 }
192
193 /*-----------------------------------------------------------------*/
194 /* findNextUseSym - finds the next use of the symbol and marks it */
195 /* alive in between */
196 /* Return 0 iff there is no next use. */
197 /*-----------------------------------------------------------------*/
198 static int
findNextUseSym(eBBlock * ebp,iCode * ic,symbol * sym)199 findNextUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
200 {
201 int retval = 0;
202 iCode *uic;
203 eBBlock *succ;
204
205 hTabAddItemIfNotP (&liveRanges, sym->key, sym);
206
207 if (!ic)
208 goto check_successors;
209
210 /* if we check a complete block and the symbol */
211 /* is alive at the beginning of the block */
212 /* and not defined in the first instructions */
213 /* then a next use exists (return 1) */
214 if ((ic == ebp->sch) && bitVectBitValue(ic->rlive, sym->key))
215 {
216 /* check if the first instruction is a def of this op */
217 if (ic->op == JUMPTABLE || ic->op == IFX || SKIP_IC2(ic))
218 return 1;
219
220 if (IS_ITEMP(IC_RESULT(ic)))
221 if (IC_RESULT(ic)->key == sym->key)
222 return 0;
223
224 return 1;
225 }
226
227 if (ebp->visited)
228 return 0;
229
230 if (ic == ebp->sch)
231 ebp->visited = 1;
232
233 /* for all remaining instructions in current block */
234 for (uic = ic; uic; uic = uic->next)
235 {
236
237 if (SKIP_IC2(uic))
238 continue;
239
240 if (uic->op == JUMPTABLE)
241 {
242 if (IS_ITEMP(IC_JTCOND(uic)) && IC_JTCOND(uic)->key == sym->key)
243 {
244 markAlive(ic, uic, sym->key);
245 return 1;
246 }
247 continue;
248 }
249
250 if (uic->op == IFX)
251 {
252 if (IS_ITEMP(IC_COND(uic)) && IC_COND(uic)->key == sym->key)
253 {
254 markAlive(ic, uic, sym->key);
255 return 1;
256 }
257 continue;
258 }
259
260 if (IS_ITEMP (IC_LEFT (uic)))
261 if (IC_LEFT (uic)->key == sym->key)
262 {
263 markAlive(ic, uic, sym->key);
264 return 1;
265 }
266
267 if (IS_ITEMP (IC_RIGHT (uic)))
268 if (IC_RIGHT (uic)->key == sym->key)
269 {
270 markAlive (ic, uic, sym->key);
271 return 1;
272 }
273
274 if (IS_ITEMP (IC_RESULT (uic)))
275 if (IC_RESULT (uic)->key == sym->key)
276 {
277 if (POINTER_SET (uic))
278 {
279 markAlive (ic, uic, sym->key);
280 return 1;
281 }
282 else
283 return 0;
284 }
285
286 }
287
288 /* check all successors */
289 check_successors:
290
291 succ = setFirstItem (ebp->succList);
292 for (; succ; succ = setNextItem (ebp->succList))
293 {
294 retval += findNextUseSym (succ, succ->sch, sym);
295 }
296
297 if (retval)
298 {
299 if (ic) markAlive (ic, ebp->ech, sym->key);
300 return 1;
301 }
302
303 return 0;
304 }
305
306 /*-----------------------------------------------------------------*/
307 /* findNextUse - finds the next use of the operand and marks it */
308 /* alive in between */
309 /* Return 0 iff there is no next use. */
310 /*-----------------------------------------------------------------*/
311 static int
findNextUse(eBBlock * ebp,iCode * ic,operand * op)312 findNextUse (eBBlock *ebp, iCode *ic, operand *op)
313 {
314 if (op->isaddr)
315 OP_SYMBOL (op)->isptr = 1;
316
317 OP_SYMBOL (op)->key = op->key;
318
319 return findNextUseSym (ebp, ic, OP_SYMBOL(op));
320 }
321
322 /*-----------------------------------------------------------------*/
323 /* unvisitBlocks - clears visited in all blocks */
324 /*-----------------------------------------------------------------*/
325 static void
unvisitBlocks(eBBlock ** ebbs,int count)326 unvisitBlocks (eBBlock ** ebbs, int count)
327 {
328 int i;
329
330 for (i = 0; i < count; i++)
331 ebbs[i]->visited = 0;
332 }
333
334 /*------------------------------------------------------------------*/
335 /* markWholeLoop - mark the symbol 'key' alive in all blocks */
336 /* included by the outermost loop */
337 /*------------------------------------------------------------------*/
338 static void
markWholeLoop(eBBlock * ebp,int key)339 markWholeLoop (eBBlock *ebp, int key)
340 {
341 eBBlock *ebpi;
342
343 /* avoid endless loops */
344 ebp->visited = 1;
345
346 /* recurse through all predecessors */
347 for (ebpi = setFirstItem (ebp->predList);
348 ebpi;
349 ebpi = setNextItem (ebp->predList))
350 {
351 if (ebpi->visited)
352 continue;
353 /* is the predecessor still in the loop? */
354 if (ebpi->depth == 0)
355 continue;
356 markWholeLoop (ebpi, key);
357 }
358
359 /* recurse through all successors */
360 for (ebpi = setFirstItem (ebp->succList);
361 ebpi;
362 ebpi = setNextItem (ebp->succList))
363 {
364 if (ebpi->visited)
365 continue;
366 if (ebpi->depth == 0)
367 continue;
368 markWholeLoop (ebpi, key);
369 }
370
371 markAlive (ebp->sch, ebp->ech, key);
372 }
373
374 /*------------------------------------------------------------------*/
375 /* findPrevUseSym - search for a previous definition of a symbol in */
376 /* - the previous icodes */
377 /* - all branches of predecessors */
378 /*------------------------------------------------------------------*/
379 static bool
findPrevUseSym(eBBlock * ebp,iCode * ic,symbol * sym)380 findPrevUseSym (eBBlock *ebp, iCode *ic, symbol * sym)
381 {
382 eBBlock * pred;
383 iCode * uic;
384
385 if (ebp->visited)
386 {
387 /* already visited: this branch must have been succesfull, */
388 /* because otherwise the search would have been aborted. */
389 return TRUE;
390 }
391 ebp->visited = 1;
392
393 /* search backward in the current block */
394 for (uic = ic; uic; uic = uic->prev)
395 {
396 if (!POINTER_SET (uic) && IS_AUTOSYM (IC_RESULT (uic)))
397 {
398 if (IC_RESULT (uic)->key == sym->key)
399 {
400 /* Ok, found a definition */
401 return TRUE;
402 }
403 }
404 /* address taken from symbol? */
405 if (uic->op == ADDRESS_OF && IS_AUTOSYM (IC_LEFT (uic)))
406 {
407 if (IC_LEFT (uic)->key == sym->key)
408 {
409 /* Ok, found a definition */
410 return TRUE;
411 }
412 }
413 }
414
415 /* There's no definition in this bblock, */
416 /* let's have a look at all predecessors. */
417 pred = setFirstItem (ebp->predList);
418 if (!pred)
419 {
420 /* no more predecessors and nothing found yet :-( */
421 return FALSE;
422 }
423 for (; pred; pred = setNextItem (ebp->predList))
424 {
425 /* recurse into all predecessors */
426 if (!findPrevUseSym (pred, pred->ech, sym))
427 {
428 /* found nothing: abort */
429 return FALSE;
430 }
431 }
432
433 /* Success! Went through all branches with no abort: */
434 /* all branches end with a definition */
435 return TRUE;
436 }
437
438 /*------------------------------------------------------------------*/
439 /* findPrevUse - search for a previous definition of an operand */
440 /* If there's no definition let's: */
441 /* - emit a warning */
442 /* - fix the life range, if the symbol is used in */
443 /* a loop */
444 /*------------------------------------------------------------------*/
445 static void
findPrevUse(eBBlock * ebp,iCode * ic,operand * op,eBBlock ** ebbs,int count,bool emitWarnings)446 findPrevUse (eBBlock *ebp, iCode *ic, operand *op,
447 eBBlock ** ebbs, int count,
448 bool emitWarnings)
449 {
450 unvisitBlocks (ebbs, count);
451
452 if (op->isaddr)
453 OP_SYMBOL (op)->isptr = 1;
454 OP_SYMBOL (op)->key = op->key;
455
456 /* There must be a definition in each branch of predecessors */
457 if (!findPrevUseSym (ebp, ic->prev, OP_SYMBOL(op)))
458 {
459 /* computeLiveRanges() is called at least twice */
460 if (emitWarnings)
461 {
462 if (IS_ITEMP (op))
463 {
464 if (OP_SYMBOL (op)->prereqv)
465 {
466 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
467 OP_SYMBOL (op)->prereqv->name);
468 OP_SYMBOL (op)->prereqv->reqv = NULL;
469 OP_SYMBOL (op)->prereqv->allocreq = 1;
470 }
471 }
472 else
473 {
474 werrorfl (ic->filename, ic->lineno, W_LOCAL_NOINIT,
475 OP_SYMBOL (op)->name);
476 }
477 }
478 /* is this block part of a loop? */
479 if (IS_ITEMP (op) && ebp->depth != 0)
480 {
481 /* extend the life range to the outermost loop */
482 unvisitBlocks(ebbs, count);
483 markWholeLoop (ebp, op->key);
484 }
485 }
486 }
487
488 /*-----------------------------------------------------------------*/
489 /* incUsed - increment a symbol's usage count */
490 /*-----------------------------------------------------------------*/
491 static void
incUsed(iCode * ic,operand * op)492 incUsed (iCode *ic, operand *op)
493 {
494 if (ic->depth)
495 OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
496 else
497 OP_SYMBOL (op)->used += 1;
498 }
499
500 /*-----------------------------------------------------------------*/
501 /* rliveClear - clears the rlive bitVectors */
502 /*-----------------------------------------------------------------*/
503 static void
rliveClear(eBBlock ** ebbs,int count)504 rliveClear (eBBlock **ebbs, int count)
505 {
506 int i;
507
508 /* for all blocks do */
509 for (i = 0; i < count; i++)
510 {
511 iCode *ic;
512
513 /* for all instructions in this block do */
514 for (ic = ebbs[i]->sch; ic; ic = ic->next)
515 {
516 freeBitVect (ic->rlive);
517 ic->rlive = NULL;
518 }
519 }
520 }
521
522 /*-----------------------------------------------------------------*/
523 /* rlivePoint - for each point compute the ranges that are alive */
524 /* The live range is only stored for ITEMPs; the same code is used */
525 /* to find use of unitialized AUTOSYMs (an ITEMP is an AUTOSYM). */
526 /* also, update funcUsesVolatile flag for current function */
527 /*-----------------------------------------------------------------*/
528 static void
rlivePoint(eBBlock ** ebbs,int count,bool emitWarnings)529 rlivePoint (eBBlock ** ebbs, int count, bool emitWarnings)
530 {
531 int i, key;
532 eBBlock *succ;
533 bitVect *alive;
534
535 bool uses_volatile = false;
536
537 /* for all blocks do */
538 for (i = 0; i < count; i++)
539 {
540 iCode *ic;
541
542 /* for all instructions in this block do */
543 for (ic = ebbs[i]->sch; ic; ic = ic->next)
544 {
545 uses_volatile |= POINTER_GET (ic) && IS_VOLATILE (operandType (IC_LEFT(ic))->next) || IS_OP_VOLATILE (IC_LEFT(ic)) || IS_OP_VOLATILE (IC_RIGHT(ic));
546 uses_volatile |= POINTER_SET (ic) && IS_VOLATILE (operandType (IC_RESULT(ic))->next) || IS_OP_VOLATILE (IC_RESULT(ic));
547
548 if (!ic->rlive)
549 ic->rlive = newBitVect (operandKey);
550
551 if (SKIP_IC2(ic))
552 continue;
553
554 if (ic->op == JUMPTABLE && IS_SYMOP(IC_JTCOND(ic)))
555 {
556 incUsed (ic, IC_JTCOND(ic));
557
558 if (!IS_AUTOSYM(IC_JTCOND(ic)))
559 continue;
560
561 findPrevUse (ebbs[i], ic, IC_JTCOND(ic), ebbs, count, emitWarnings);
562 if (IS_ITEMP(IC_JTCOND(ic)))
563 {
564 unvisitBlocks(ebbs, count);
565 ic->rlive = bitVectSetBit (ic->rlive, IC_JTCOND(ic)->key);
566 findNextUse (ebbs[i], ic->next, IC_JTCOND(ic));
567 }
568
569 continue;
570 }
571
572 if (ic->op == IFX && IS_SYMOP(IC_COND(ic)))
573 {
574 incUsed (ic, IC_COND(ic));
575
576 if (!IS_AUTOSYM(IC_COND(ic)))
577 continue;
578
579 findPrevUse (ebbs[i], ic, IC_COND(ic), ebbs, count, emitWarnings);
580 if (IS_ITEMP(IC_COND(ic)))
581 {
582 unvisitBlocks (ebbs, count);
583 ic->rlive = bitVectSetBit (ic->rlive, IC_COND(ic)->key);
584 findNextUse (ebbs[i], ic->next, IC_COND(ic));
585 }
586
587 continue;
588 }
589
590 if (IS_SYMOP(IC_LEFT(ic)))
591 {
592 incUsed (ic, IC_LEFT(ic));
593 if (IS_AUTOSYM(IC_LEFT(ic)) &&
594 ic->op != ADDRESS_OF)
595 {
596 findPrevUse (ebbs[i], ic, IC_LEFT(ic), ebbs, count, emitWarnings);
597 if (IS_ITEMP(IC_LEFT(ic)))
598 {
599 unvisitBlocks(ebbs, count);
600 ic->rlive = bitVectSetBit (ic->rlive, IC_LEFT(ic)->key);
601 findNextUse (ebbs[i], ic->next, IC_LEFT(ic));
602
603 /* if this is a send extend the LR to the call */
604 if (ic->op == SEND)
605 {
606 iCode *lic;
607 for (lic = ic; lic; lic = lic->next)
608 {
609 if (lic->op == CALL || lic->op == PCALL)
610 {
611 markAlive (ic, lic->prev, IC_LEFT (ic)->key);
612 break;
613 }
614 }
615 }
616 }
617 }
618 }
619
620 if (IS_SYMOP(IC_RIGHT(ic)))
621 {
622 incUsed (ic, IC_RIGHT(ic));
623 if (IS_AUTOSYM(IC_RIGHT(ic)))
624 {
625 findPrevUse (ebbs[i], ic, IC_RIGHT(ic), ebbs, count, emitWarnings);
626 if (IS_ITEMP(IC_RIGHT(ic)))
627 {
628 unvisitBlocks(ebbs, count);
629 ic->rlive = bitVectSetBit (ic->rlive, IC_RIGHT(ic)->key);
630 findNextUse (ebbs[i], ic->next, IC_RIGHT(ic));
631 }
632 }
633 }
634
635 if (POINTER_SET(ic) && IS_SYMOP(IC_RESULT(ic)))
636 incUsed (ic, IC_RESULT(ic));
637
638 if (IS_AUTOSYM(IC_RESULT(ic)))
639 {
640 if (POINTER_SET(ic))
641 {
642 findPrevUse (ebbs[i], ic, IC_RESULT(ic), ebbs, count, emitWarnings);
643 }
644 if (IS_ITEMP(IC_RESULT(ic)))
645 {
646 unvisitBlocks(ebbs, count);
647 ic->rlive = bitVectSetBit (ic->rlive, IC_RESULT(ic)->key);
648 findNextUse (ebbs[i], ic->next, IC_RESULT(ic));
649 /* findNextUse sometimes returns 0 here, which means that ic is
650 dead code. Something should be done about this dead code since
651 e.g. register allocation suffers. */
652 }
653 }
654
655 if (!POINTER_SET(ic) && IC_RESULT(ic))
656 ic->defKey = IC_RESULT(ic)->key;
657
658 }
659
660 /* check all symbols that are alive in the last instruction */
661 /* but are not alive in all successors */
662
663 succ = setFirstItem (ebbs[i]->succList);
664 if (!succ)
665 continue;
666
667 alive = succ->sch->rlive;
668 while ((succ = setNextItem (ebbs[i]->succList)))
669 {
670 if (succ->sch)
671 alive = bitVectIntersect (alive, succ->sch->rlive);
672 }
673
674 if (ebbs[i]->ech)
675 alive = bitVectCplAnd ( bitVectCopy (ebbs[i]->ech->rlive), alive);
676
677 if(!alive)
678 continue;
679 for (key = 1; key < alive->size; key++)
680 {
681 if (!bitVectBitValue (alive, key))
682 continue;
683
684 unvisitBlocks(ebbs, count);
685 findNextUseSym (ebbs[i], NULL, hTabItemWithKey (liveRanges, key));
686 }
687
688 }
689
690 if(currFunc)
691 currFunc->funcUsesVolatile = uses_volatile;
692 }
693
694 /*-----------------------------------------------------------------*/
695 /* computeClash - find out which live ranges collide with others */
696 /*-----------------------------------------------------------------*/
697 static void
computeClash(eBBlock ** ebbs,int count)698 computeClash (eBBlock ** ebbs, int count)
699 {
700 int i;
701
702 /* for all blocks do */
703 for (i = 0; i < count; i++)
704 {
705 iCode *ic;
706
707 /* for every iCode do */
708 for (ic = ebbs[i]->sch; ic; ic = ic->next)
709 {
710 symbol *sym1, *sym2;
711 int key1, key2;
712
713 /* for all iTemps alive at this iCode */
714 for (key1 = 1; key1 < ic->rlive->size; key1++)
715 {
716 if (!bitVectBitValue(ic->rlive, key1))
717 continue;
718
719 sym1 = hTabItemWithKey(liveRanges, key1);
720
721 if (!sym1->isitmp)
722 continue;
723
724 /* for all other iTemps alive at this iCode */
725 for (key2 = key1+1; key2 < ic->rlive->size; key2++)
726 {
727 if (!bitVectBitValue(ic->rlive, key2))
728 continue;
729
730 sym2 = hTabItemWithKey(liveRanges, key2);
731
732 if (!sym2->isitmp)
733 continue;
734
735 /* if the result and left or right is an iTemp */
736 /* than possibly the iTemps do not clash */
737 if ((ic->op != JUMPTABLE) && (ic->op != IFX) &&
738 IS_ITEMP(IC_RESULT(ic)) &&
739 (IS_ITEMP(IC_LEFT(ic)) || IS_ITEMP(IC_RIGHT(ic))))
740 {
741 if (OP_SYMBOL(IC_RESULT(ic))->key == key1
742 && sym1->liveFrom == ic->seq
743 && sym2->liveTo == ic->seq)
744 {
745 if (IS_SYMOP(IC_LEFT(ic)))
746 if (OP_SYMBOL(IC_LEFT(ic))->key == key2)
747 continue;
748 if (IS_SYMOP(IC_RIGHT(ic)))
749 if (OP_SYMBOL(IC_RIGHT(ic))->key == key2)
750 continue;
751 }
752
753 if (OP_SYMBOL(IC_RESULT(ic))->key == key2
754 && sym2->liveFrom == ic->seq
755 && sym1->liveTo == ic->seq)
756 {
757 if (IS_SYMOP(IC_LEFT(ic)))
758 if (OP_SYMBOL(IC_LEFT(ic))->key == key1)
759 continue;
760 if (IS_SYMOP(IC_RIGHT(ic)))
761 if (OP_SYMBOL(IC_RIGHT(ic))->key == key1)
762 continue;
763 }
764 }
765
766 /* the iTemps do clash. set the bits in clashes */
767 sym1->clashes = bitVectSetBit (sym1->clashes, key2);
768 sym2->clashes = bitVectSetBit (sym2->clashes, key1);
769
770 /* check if they share the same spill location */
771 /* what is this good for? */
772 if (SYM_SPIL_LOC(sym1) && SYM_SPIL_LOC(sym2) &&
773 SYM_SPIL_LOC(sym1) == SYM_SPIL_LOC(sym2))
774 {
775 if (sym1->reqv && !sym2->reqv) SYM_SPIL_LOC(sym2)=NULL;
776 else if (sym2->reqv && !sym1->reqv) SYM_SPIL_LOC(sym1)=NULL;
777 else if (sym1->used > sym2->used) SYM_SPIL_LOC(sym2)=NULL;
778 else SYM_SPIL_LOC(sym1)=NULL;
779 }
780 }
781 }
782 }
783 }
784 }
785
786 /*-----------------------------------------------------------------*/
787 /* allDefsOutOfRange - all definitions are out of a range */
788 /*-----------------------------------------------------------------*/
789 bool
allDefsOutOfRange(bitVect * defs,int fseq,int toseq)790 allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
791 {
792 int i;
793
794 if (!defs)
795 return TRUE;
796
797 for (i = 0; i < defs->size; i++)
798 {
799 iCode *ic;
800
801 if (bitVectBitValue (defs, i) &&
802 (ic = hTabItemWithKey (iCodehTab, i)) &&
803 (ic->seq >= fseq && ic->seq <= toseq))
804 return FALSE;
805
806 }
807
808 return TRUE;
809 }
810
811 /*-----------------------------------------------------------------*/
812 /* notUsedInBlock - not used in this block */
813 /*-----------------------------------------------------------------*/
814 int
notUsedInBlock(symbol * sym,eBBlock * ebp,iCode * ic)815 notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
816 {
817 return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
818 allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
819 allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
820 }
821
822 /*-----------------------------------------------------------------*/
823 /* adjustIChain - correct the sch and ech pointers */
824 /*-----------------------------------------------------------------*/
825 void
adjustIChain(eBBlock ** ebbs,int count)826 adjustIChain (eBBlock ** ebbs, int count)
827 {
828 int i;
829
830 for (i = 0; i < count; i++)
831 {
832 iCode *ic;
833
834 if (ebbs[i]->noPath)
835 continue;
836
837 ic = ebbs[i]->sch;
838
839 /* is there any code for this eBBlock? (e.g. ROM assignment) */
840 if(!ic)continue;
841
842 while (ic->prev)
843 ic = ic->prev;
844 ebbs[i]->sch = ic;
845
846 ic = ebbs[i]->ech;
847 while (ic->next)
848 ic = ic->next;
849 ebbs[i]->ech = ic;
850 }
851 }
852
853 /*-----------------------------------------------------------------*/
854 /* computeLiveRanges - computes the live ranges for variables */
855 /*-----------------------------------------------------------------*/
856 void
computeLiveRanges(eBBlock ** ebbs,int count,bool emitWarnings)857 computeLiveRanges (eBBlock **ebbs, int count, bool emitWarnings)
858 {
859 /* first look through all blocks and adjust the
860 sch and ech pointers */
861 adjustIChain (ebbs, count);
862
863 /* sequence the code the live ranges are computed
864 in terms of this sequence additionally the
865 routine will also create a hashtable of instructions */
866 iCodeSeq = 0;
867 setToNull ((void *) &iCodehTab);
868 iCodehTab = newHashTable (iCodeKey);
869 hashiCodeKeys (ebbs, count);
870 setToNull ((void *) &iCodeSeqhTab);
871 iCodeSeqhTab = newHashTable (iCodeKey);
872 sequenceiCode (ebbs, count);
873
874 /* mark the ranges live for each point */
875 setToNull ((void *) &liveRanges);
876 rlivePoint (ebbs, count, emitWarnings);
877
878 /* mark the from & to live ranges for variables used */
879 markLiveRanges (ebbs, count);
880
881 /* compute which overlaps with what */
882 computeClash(ebbs, count);
883 }
884
885 /*-----------------------------------------------------------------*/
886 /* recomputeLiveRanges - recomputes the live ranges for variables */
887 /*-----------------------------------------------------------------*/
888 void
recomputeLiveRanges(eBBlock ** ebbs,int count,bool emitWarnings)889 recomputeLiveRanges (eBBlock **ebbs, int count, bool emitWarnings)
890 {
891 symbol * sym;
892 int key;
893
894 /* clear all rlive bitVectors */
895 rliveClear (ebbs, count);
896
897 sym = hTabFirstItem (liveRanges, &key);
898 if (sym)
899 {
900 do {
901 sym->used = 0;
902 sym->liveFrom = 0;
903 sym->liveTo = 0;
904 freeBitVect (sym->clashes);
905 sym->clashes = NULL;
906 } while ( (sym = hTabNextItem (liveRanges, &key)));
907 }
908
909 /* do the LR computation again */
910 computeLiveRanges (ebbs, count, emitWarnings);
911 }
912
913 /*-----------------------------------------------------------------*/
914 /* dump icode->rlive in all blocks */
915 /*-----------------------------------------------------------------*/
916 #if 0
917 void
918 dumpIcRlive (eBBlock ** ebbs, int count)
919 {
920 int i, j;
921 iCode *ic;
922
923 /* for all blocks do */
924 for (i = 0; i < count; i++)
925 {
926 printf ("bb %d %s alive symbols:\n", i, ebbs[i]->entryLabel->name);
927 /* for all instructions in this block do */
928 for (ic = ebbs[i]->sch; ic; ic = ic->next)
929 {
930 printf ("\tic->key %d\n", ic->key);
931
932 if (!ic->rlive)
933 continue;
934 /* for all live Ranges alive at this point */
935 for (j = 1; j < ic->rlive->size; j++)
936 {
937 symbol *sym;
938
939 if (!bitVectBitValue (ic->rlive, j))
940 continue;
941
942 /* find the live range we are interested in */
943 if ((sym = hTabItemWithKey (liveRanges, j)))
944 printf ("\t\tsym->key %2d: %s\n", sym->key, sym->rname[0] ? sym->rname : sym->name);
945 }
946 }
947 }
948 }
949 #endif
950
951 /*-----------------------------------------------------------------*/
952 /* Visit all iCodes reachable from ic */
953 /*-----------------------------------------------------------------*/
visit(set ** visited,iCode * ic,const int key)954 static void visit (set **visited, iCode *ic, const int key)
955 {
956 symbol *lbl;
957
958 while (ic && !isinSet (*visited, ic) && bitVectBitValue (ic->rlive, key))
959 {
960 addSet (visited, ic);
961
962 switch (ic->op)
963 {
964 case GOTO:
965 ic = hTabItemWithKey (labelDef, (IC_LABEL (ic))->key);
966 break;
967 case RETURN:
968 ic = hTabItemWithKey (labelDef, returnLabel->key);
969 break;
970 case JUMPTABLE:
971 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl; lbl = setNextItem (IC_JTLABELS (ic)))
972 visit (visited, hTabItemWithKey (labelDef, lbl->key), key);
973 break;
974 case IFX:
975 visit (visited, hTabItemWithKey (labelDef, (IC_TRUE(ic) ? IC_TRUE (ic) : IC_FALSE (ic))->key), key);
976 ic = ic->next;
977 break;
978 default:
979 ic = ic->next;
980 if (!POINTER_SET (ic) && IC_RESULT (ic) && IS_SYMOP (IC_RESULT (ic)) && OP_SYMBOL_CONST (IC_RESULT (ic))->key == key)
981 {
982 addSet (visited, ic);
983 return;
984 }
985 }
986 }
987 }
988
989 /*-----------------------------------------------------------------*/
990 /* Split temporaries that have non-connected live ranges */
991 /* Such temporaries can result from GCSE and losrpe, */
992 /* And can confuse register allocation and rematerialization. */
993 /*-----------------------------------------------------------------*/
994 int
separateLiveRanges(iCode * sic,ebbIndex * ebbi)995 separateLiveRanges (iCode *sic, ebbIndex *ebbi)
996 {
997 set *candidates = 0;
998 symbol *sym;
999 int num_separated = 0;
1000
1001 // printf("separateLiveRanges()\n");
1002
1003 for (iCode *ic = sic; ic; ic = ic->next)
1004 {
1005 if (ic->op == IFX || ic->op == GOTO || ic->op == JUMPTABLE || !IC_RESULT (ic) || !IS_ITEMP (IC_RESULT (ic)) || bitVectnBitsOn (OP_DEFS (IC_RESULT (ic))) <= 1 || isinSet (candidates, OP_SYMBOL (IC_RESULT (ic))))
1006 continue;
1007
1008 addSet (&candidates, OP_SYMBOL (IC_RESULT (ic)));
1009 }
1010
1011 if (!candidates)
1012 return (0);
1013
1014 for(sym = setFirstItem (candidates); sym; sym = setNextItem (candidates))
1015 {
1016 // printf("Looking at %s, %d definitions\n", sym->name, bitVectnBitsOn (sym->defs));
1017
1018 set *defs = 0;
1019 set *uses = 0;
1020 bool skip_uses = false;
1021
1022 for (int i = 0; i < sym->defs->size; i++)
1023 {
1024 if (bitVectBitValue (sym->defs, i))
1025 {
1026 iCode *dic;
1027 if(dic = hTabItemWithKey (iCodehTab, i))
1028 addSet (&defs, dic);
1029 else
1030 {
1031 werror (W_INTERNAL_ERROR, __FILE__, __LINE__, "Definition not found");
1032 return (num_separated);
1033 }
1034 }
1035 if (bitVectBitValue (sym->uses, i))
1036 {
1037 iCode *uic;
1038 if(uic = hTabItemWithKey (iCodehTab, i))
1039 addSet (&uses, uic);
1040 else
1041 skip_uses = true; // werror (W_INTERNAL_ERROR, __FILE__, __LINE__, "Use not found"); // return (num_separated); seems too harsh.
1042 }
1043 }
1044 do
1045 {
1046 set *visited = 0;
1047 set *newdefs = 0;
1048 int oldsize;
1049
1050 wassert (defs);
1051 wassert (setFirstItem (defs));
1052
1053 // printf("Looking at def at %d now\n", ((iCode *)(setFirstItem (defs)))->key);
1054
1055 if (!bitVectBitValue (((iCode *)(setFirstItem (defs)))->rlive, sym->key))
1056 {
1057 werror (W_INTERNAL_ERROR, __FILE__, __LINE__, "Variable is not alive at one of its definitions");
1058 break;
1059 }
1060
1061 visit (&visited, setFirstItem (defs), sym->key);
1062 addSet (&newdefs, setFirstItem (defs));
1063
1064 do
1065 {
1066 oldsize = elementsInSet(visited);
1067 setFirstItem (defs);
1068 for(iCode *ic = setNextItem (defs); ic; ic = setNextItem (defs))
1069 {
1070 // printf("Looking at other def at %d now\n", ic->key);
1071 set *visited2 = 0;
1072 set *intersection = 0;
1073 visit (&visited2, ic, sym->key);
1074 intersection = intersectSets (visited, visited2, THROW_NONE);
1075 intersection = subtractFromSet (intersection, defs, THROW_DEST);
1076 if (intersection)
1077 {
1078 visited = unionSets (visited, visited2, THROW_DEST);
1079 addSet (&newdefs, ic);
1080 }
1081 deleteSet (&intersection);
1082 deleteSet (&visited2);
1083 }
1084 }
1085 while (oldsize < elementsInSet(visited));
1086
1087 defs = subtractFromSet (defs, newdefs, THROW_DEST);
1088
1089 if (newdefs && defs)
1090 {
1091 operand *tmpop = newiTempOperand (operandType (IC_RESULT ((iCode *)(setFirstItem (newdefs)))), TRUE);
1092
1093 // printf("Splitting %s from %s, using def at %d, op %d\n", OP_SYMBOL_CONST(tmpop)->name, sym->name, ((iCode *)(setFirstItem (newdefs)))->key, ((iCode *)(setFirstItem (newdefs)))->op);
1094
1095 for (iCode *ic = setFirstItem (visited); ic; ic = setNextItem (visited))
1096 {
1097 if (IC_LEFT (ic) && IS_ITEMP (IC_LEFT (ic)) && OP_SYMBOL (IC_LEFT (ic)) == sym)
1098 IC_LEFT (ic) = operandFromOperand (tmpop);
1099 if (IC_RIGHT (ic) && IS_ITEMP (IC_RIGHT (ic)) && OP_SYMBOL (IC_RIGHT (ic)) == sym)
1100 IC_RIGHT (ic) = operandFromOperand (tmpop);
1101 if (IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)) && OP_SYMBOL (IC_RESULT (ic)) == sym && !POINTER_SET(ic) && ic->next && !isinSet (visited, ic->next))
1102 continue;
1103 if (IC_RESULT (ic) && IS_ITEMP (IC_RESULT (ic)) && OP_SYMBOL (IC_RESULT (ic)) == sym)
1104 {
1105 bool pset = POINTER_SET(ic);
1106 IC_RESULT (ic) = operandFromOperand (tmpop);
1107 if (pset)
1108 IC_RESULT(ic)->isaddr = TRUE;
1109 else
1110 bitVectUnSetBit (sym->defs, ic->key);
1111 }
1112 bitVectUnSetBit (sym->uses, ic->key);
1113
1114 skip_uses = true;
1115 num_separated++;
1116 }
1117 }
1118 else if (!skip_uses)
1119 {
1120 set *undefined_uses = 0;
1121 undefined_uses = subtractFromSet (uses, visited, THROW_NONE);
1122
1123 // Eliminate uses of undefined variables.
1124 for (iCode *ic = setFirstItem (undefined_uses); ic; ic = setNextItem (undefined_uses))
1125 {
1126 iCode *prev = ic->prev;
1127 iCode *next = ic->next;
1128 if (prev && next)
1129 {
1130 prev->next = next;
1131 next->prev = prev;
1132 }
1133
1134 bitVectUnSetBit (sym->uses, ic->key);
1135 if (IS_SYMOP (IC_RESULT (ic)))
1136 bitVectUnSetBit (OP_DEFS (IC_RESULT (ic)), ic->key);
1137 }
1138
1139 deleteSet (&undefined_uses);
1140 }
1141
1142 deleteSet (&newdefs);
1143 deleteSet (&visited);
1144 }
1145 while (elementsInSet(defs) > 1);
1146
1147 deleteSet (&defs);
1148 deleteSet (&uses);
1149 }
1150
1151 deleteSet (&candidates);
1152
1153 return (num_separated);
1154 }
1155
1156 /*-----------------------------------------------------------------*/
1157 /* Shorten live ranges by swapping order of operations */
1158 /*-----------------------------------------------------------------*/
1159 int
shortenLiveRanges(iCode * sic,ebbIndex * ebbi)1160 shortenLiveRanges (iCode *sic, ebbIndex *ebbi)
1161 {
1162 int change = 0;
1163
1164 for (iCode *ic = sic; ic; ic = ic->next)
1165 {
1166 iCode *ifx = 0;
1167
1168 iCode *pic = ic->prev;
1169 iCode *nic = ic->next;
1170
1171 if (!pic || !nic)
1172 continue;
1173
1174 if (ic->op == IFX || nic->op == IFX)
1175 continue;
1176
1177 if (nic->op == IPUSH || nic->op == SEND || nic->op == RETURN)
1178 continue;
1179
1180 if (pic->op != '=' || !IS_ITEMP (IC_RESULT (pic)) || bitVectnBitsOn (OP_DEFS (IC_RESULT (pic))) != 1)
1181 continue;
1182
1183 if (IC_LEFT (nic) != IC_RESULT (pic) && IC_RIGHT (nic) != IC_RESULT (pic) || bitVectnBitsOn (OP_USES (IC_RESULT (pic))) != 1)
1184 continue;
1185
1186 if (IS_OP_VOLATILE (IC_RIGHT (pic)) || IS_OP_VOLATILE (IC_LEFT (nic)) || IS_OP_VOLATILE (IC_RIGHT (nic)) || IS_OP_VOLATILE (IC_RESULT (nic)))
1187 continue;
1188
1189 if (isOperandEqual (IC_RESULT (pic), IC_LEFT (ic)) || isOperandEqual (IC_RESULT (pic), IC_RIGHT (ic)))
1190 continue;
1191
1192 if (isOperandEqual (IC_RESULT (ic), IC_LEFT (nic)) || isOperandEqual (IC_RESULT (ic), IC_RIGHT (nic)))
1193 continue;
1194
1195 if ((POINTER_SET (nic) || isOperandGlobal (IC_RESULT (nic))) && (POINTER_GET (ic) || isOperandGlobal (IC_LEFT (ic)) || isOperandGlobal (IC_RIGHT (ic))) ||
1196 (POINTER_GET (nic) || isOperandGlobal (IC_LEFT (nic)) || isOperandGlobal (IC_RIGHT (nic))) && (POINTER_SET (ic) || POINTER_SET (nic) && isOperandGlobal (IC_RESULT (ic))))
1197 continue;
1198
1199 if (isOperandGlobal (IC_RIGHT (pic)) && !TARGET_IS_STM8 && !TARGET_PDK_LIKE) // Might result in too many global operands per op for backend.
1200 continue;
1201
1202 if (ifx = ifxForOp (IC_RESULT (nic), nic))
1203 {
1204 const symbol *starget = IC_TRUE (ifx) ? IC_TRUE (ifx) : IC_FALSE (ifx);
1205 const iCode *itarget = eBBWithEntryLabel(ebbi, starget)->sch;
1206
1207 if (nic->next != ifx || bitVectBitValue(itarget->rlive, IC_RESULT (ic)->key))
1208 continue;
1209 }
1210
1211 if (IC_LEFT (nic) == IC_RESULT (pic))
1212 IC_LEFT (nic) = IC_RIGHT (pic);
1213 if (IC_RIGHT (nic) == IC_RESULT (pic))
1214 IC_RIGHT (nic) = IC_RIGHT (pic);
1215 bitVectUnSetBit (OP_USES (IC_RESULT (pic)), nic->key);
1216 if (IS_SYMOP (IC_RIGHT (pic)))
1217 bitVectSetBit (OP_USES (IC_RIGHT (pic)), nic->key);
1218
1219 // Assignment to self will get optimized out later
1220 IC_LEFT (pic) = IC_RESULT (pic);
1221 bitVectSetBit (OP_USES (IC_RESULT (pic)), pic->key);
1222
1223 pic->next = nic;
1224 nic->prev = pic;
1225 ic->prev = nic;
1226 ic->next = nic->next;
1227 nic->next = ic;
1228 if (ic->next)
1229 ic->next->prev = ic;
1230
1231 if (ifx) // Move calculation beyond ifx.
1232 {
1233 ifx->prev = ic->prev;
1234 ic->next = ifx->next;
1235 ifx->next = ic;
1236 ic->prev = ifx;
1237
1238 ifx->prev->next = ifx;
1239 if (ic->next)
1240 ic->next->prev = ic;
1241 }
1242
1243 change++;
1244 }
1245
1246 return (change);
1247 }
1248
1249