10 /// Used to generate a unique name for the spill location.
12 /// Set of all iTemps spilt onto the stack.
14 /// Similar to stackSpill
18 /// Bitvector of all registers used in this function.
19 bitVect *funcUsedRegs;
20 /// If a bit is set in this then the iCode at that sequence has had
21 /// registers allocated.
29 _findRegById (REG_ID id)
31 REG *r = izt_port->regs;
44 _getSubReg (REG * r, int size, int offset)
46 wassert (r->size >= size);
50 wassert (offset == 0);
53 // We use the hiding table to get the parts of the register.
56 wassert (offset == 0 || offset == 1);
57 return _findRegById (r->hides[offset]);
61 wassert (offset == 0);
62 return _findRegById (r->hides[2]);
70 _numRegsAvailable (int size)
72 REG *r = izt_port->regs;
77 if (r->size == size && r->used == 0)
86 _setClearUsed (REG_ID id, int clear)
88 REG *r = _findRegById (id);
93 // The parent shouldnt be able to be allocated if this child
95 wassert ((r->used & REG_USED_HIDDEN) == 0);
96 r->used |= REG_USED_HIDDEN;
100 wassert ((r->used & REG_USED_HIDDEN) != 0);
101 r->used &= ~REG_USED_HIDDEN;
106 _markAsUsed (REG_ID id)
108 _setClearUsed (id, FALSE);
112 _markAsFree (REG_ID id)
114 _setClearUsed (id, TRUE);
118 _allocateReg (int size)
120 REG *r = izt_port->regs;
124 if (r->size == size && r->used == 0)
126 // Now go through the interference table and mark all other
127 // registers as used.
129 for (i = 0; i < NUM_OF (r->hides); i++)
131 if (r->hides[i] == REG_ID_NONE)
135 _markAsUsed (r->hides[i]);
146 _markRegBits (bitVect * v, REG * r)
150 // Mark the primary register.
151 v = bitVectSetBit (v, r->id);
153 // Now add all the hidden registers.
154 for (i = 0; i < NUM_OF (r->hides); i++)
156 if (r->hides[i] == REG_ID_NONE)
160 v = bitVectSetBit (v, r->hides[i]);
170 wassert (r->used == REG_USED);
174 for (i = 0; i < NUM_OF (r->hides); i++)
176 if (r->hides[i] == REG_ID_NONE)
180 _markAsFree (r->hides[i]);
187 REG *r = izt_port->regs;
199 REG *r = izt_port->regs;
203 printf ("%u\t%u\t%s\t%u\n", r->size, r->id, r->name, r->used);
209 izt_init (IZT_PORT * port)
211 wassert (port && port->regs);
216 /// Lower register pressure by packing iTemps where possible.
218 _packRegisters (eBBlock * ebp)
220 // PENDING: Assignment packing
221 // PENDING: Mark address of a true symbol as remat.
222 // PENDING: Propagate remat through equals.
223 // PENDING: Assign bitwise which is followed by a conditional into carry.
224 // PENDING: Pack for one use on pointer get or set. Assumes that the pointer
225 // is stored in the scratch register.
226 // PENDING: Pack short use iTemps into ACC or the scratch register.
230 _computeRequiredRegs (void)
235 // Iterate over each live range.
236 for (sym = hTabFirstItem (liveRanges, &k); sym;
237 sym = hTabNextItem (liveRanges, &k))
242 // If the symbol is never used, then next.
243 if ((sym->liveTo - sym->liveFrom) == 0)
246 // Only temporaries need registers.
250 // Conditionals live in carry and dont need registers.
251 if (sym->regType == REG_TYPE_CND)
255 #if 0 // PENDING. Currently we dont compute ruonly or accuse.
256 if (sym->ruonly || sym->accuse)
258 if (IS_AGGREGATE (sym->type) || sym->isptr)
259 sym->type = aggrToPtr (sym->type, FALSE);
263 // We need registers.
264 if (IS_AGGREGATE (sym->type) || sym->isptr)
266 // Turn an aggregate into something real.
267 sym->type = aggrToPtr (sym->type, FALSE);
270 sym->nRegs = getSize (sym->type);
271 wassert (sym->nRegs <= 4);
276 _doesntNeedRegs (iCode * ic)
278 // Some types of instructions dont need registers.
279 // PENDING: Flush out the types and make processor specific.
281 ic->op == JUMPTABLE ||
293 _willCauseSpill (int size)
295 return _numRegsAvailable (size) == 0;
299 _deassignLRs (iCode * ic, eBBlock * ebp)
306 for (sym = hTabFirstItem (liveRanges, &ignored); sym; sym = hTabNextItem (liveRanges, &ignored))
309 // Has this symbol expired yet?
310 if (sym->liveTo > ic->seq)
312 // No. Cant deassign.
316 // It has expired. Free up the resources.
318 // If it was spilt, then free up the stack spill location.
323 sym->usl.spillLoc->isFree = 1;
329 // If it currently has no registers assigned, then continue.
330 if (bitVectBitValue (_G.regAssigned, sym->key) == 0)
335 // If it has no registers assigned to it, then continue.
341 // Mark this sym as not having registers assigned.
342 bitVectUnSetBit (_G.regAssigned, sym->key);
344 // Free the registers.
345 _freeReg (sym->regs[0]);
347 // If deallocating will free up enough registers for this iCode
348 // then steal them immediatly.
349 if (IC_RESULT (ic) && !_doesntNeedRegs (ic))
351 result = OP_SYMBOL (IC_RESULT (ic));
352 if (result && // Has a result
353 result->liveTo > ic->seq && // and lives past this instruction
354 result->liveTo <= ebp->lSeq && // and doesnt go past this block
355 result->nRegs && // and actually needs registers
356 !result->isspilt && // and doesnt have them yet
357 !result->remat && // and wouldnt waste them
358 !bitVectBitValue (_G.regAssigned, result->key) && // doesnt have them yet
359 !_willCauseSpill (result->nRegs)
362 result->regs[0] = _allocateReg (result->nRegs);
368 /// Returns true if the live range of the given symbol doesnt overlap
369 /// with any of the live ranges in the set.
371 _noOverlap (set * itmpStack, symbol * fsym)
375 for (sym = setFirstItem (itmpStack); sym; sym = setNextItem (itmpStack))
377 if (sym->liveTo > fsym->liveFrom)
385 /// Set operator that returns 1 if a free spill location is found.
386 DEFSETFUNC (_stackIsFree)
389 V_ARG (symbol **, sloc);
390 V_ARG (symbol *, fsym);
392 // Dont bother if one has already been found.
396 if (sym->isFree && // This location is free...
397 _noOverlap (sym->usl.itmpStack, fsym) && // and its usage doesnt overlap with the usage of this sym
398 getSize (sym->type) >= getSize (fsym->type) && // and the location is big enough to hold the sym
401 // All good. Take this location.
412 /// Create a new spill location on the stack for this symbol.
414 _createStackSpill (symbol * sym)
418 // Try to reuse an exisiting spill location.
419 if (applyToSet (_G.spill.set, _stackIsFree, &sloc, sym))
421 // Found one. Take it over.
422 sym->usl.spillLoc = sloc;
423 sym->stackSpil = TRUE;
425 addSetHead (&sloc->usl.itmpStack, sym);
429 // No existing location. Time to create one.
430 // Give it a pretty name.
431 sprintf (buffer, "sloc%d", ++_G.spill.loc);
433 sloc = newiTemp (buffer);
436 sloc->type = copyLinkChain (sym->type);
437 sloc->etype = getSpec (sloc->type);
438 SPEC_SCLS (sloc->etype) = S_AUTO;
442 // "To prevent compiler warning"
445 // Increase the local variable stack size on this function.
446 if (IN_STACK (sloc->etype))
448 currFunc->stack += getSize (sloc->type);
449 _G.stackExtend += getSize (sloc->type);
453 // The IZT port currently doesnt support loading locals into data space.
457 // And add it to the spill set.
458 addSetHead (&_G.spill.set, sloc);
459 sym->usl.spillLoc = sloc;
460 sym->stackSpil = TRUE;
462 // "Add it to the set of itempStack set of the spill location
463 addSetHead (&sloc->usl.itmpStack, sym);
469 _spillThis (symbol * sym)
471 // Create a spill location if it needs one and doesnt have one yet.
472 if (!(sym->remat || sym->usl.spillLoc))
474 _createStackSpill (sym);
478 // Add it to the spilt set.
479 _G.spill.vect = bitVectSetBit (_G.spill.vect, sym->key);
480 // and remove it from the 'has registers' set.
481 bitVectUnSetBit (_G.regAssigned, sym->key);
483 // Free up any registers that were assigned to this.
486 _freeReg (sym->regs[0]);
490 // CHECK: If this sym now has a spill location, mark it as allocated
491 // so that the stack packing later doesnt remove it.
492 if (sym->usl.spillLoc && !sym->remat)
494 sym->usl.spillLoc->allocreq = TRUE;
501 _findSpillable (iCode * ic)
505 // First create a copy of the currently live ranges.
506 spillable = bitVectCopy (ic->rlive);
507 // Remove those which are already spilt.
508 spillable = bitVectCplAnd (spillable, _G.spill.vect);
509 // Remove those that this iCode uses.
510 spillable = bitVectCplAnd (spillable, ic->uses);
511 // Remove those that this iCode defines.
512 bitVectUnSetBit (spillable, ic->defKey);
514 // Only those that have registers assigned can actually be spilt :)
515 spillable = bitVectIntersect (spillable, _G.regAssigned);
520 /// Finds the least used live range
522 _leastUsedLR (set * sset)
524 // sym is the currently least used symbol.
526 // walk walks the list of symbols in the scan set.
529 // Use the first as the seed.
530 sym = walk = setFirstItem (sset);
534 // Prefer spilling the symbol with the least allocated registers.
536 if (walk->used == sym->used)
538 if (getSize (walk->type) < getSize (sym->type))
543 else if (walk->used < sym->used)
545 // This is used less than the current best. It looses.
549 walk = setNextItem (sset);
552 setToNull ((void **) &sset);
558 /// Applies a function to a given set of live ranges.
560 _liveRangesWith (bitVect * lrs, int (func) (symbol *, eBBlock *, iCode *),
561 eBBlock * ebp, iCode * ic)
566 // Dont do anything if the bitVect is empty.
567 if (!lrs || !lrs->size)
570 for (i = 1; i < lrs->size; i++)
574 // If this bit isnt turned on, skip.
575 if (!bitVectBitValue (lrs, i))
578 // If we don't find it in the live range hash table we are in serious trouble.
579 if (!(sym = hTabItemWithKey (liveRanges, i)))
581 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
582 "liveRangesWith could not find liveRange");
586 // If the function likes it, and it has registers assigned to
587 // it, add it to the return set.
588 if (func (sym, ebp, ic) && bitVectBitValue (_G.regAssigned, sym->key))
590 addSetHead (&rset, sym);
597 /// Returns TRUE always. Used to fetch all live ranges.
599 _allLRs (symbol * sym, eBBlock * ebp, iCode * ic)
605 _serialRegAssign (eBBlock ** ebbs, int count)
609 // For each block, do...
610 for (i = 0; i < count; i++)
614 if (ebbs[i]->noPath &&
615 (ebbs[i]->entryLabel != entryLabel &&
616 ebbs[i]->entryLabel != returnLabel))
618 // PENDING: Dont understand.
623 // For each iCode in this block, do...
624 for (ic = ebbs[i]->sch; ic; ic = ic->next)
631 wassert (ic->op != IPOP);
633 // if result is present && is a true symbol
634 if (IC_RESULT (ic) && ic->op != IFX &&
635 IS_TRUE_SYMOP (IC_RESULT (ic)))
636 OP_SYMBOL (IC_RESULT (ic))->allocreq = 1;
638 // Take away registers from live ranges that end at this
640 _deassignLRs (ic, ebbs[i]);
642 // Some instructions dont need registers.
643 if (_doesntNeedRegs (ic))
648 // If there is no result, then it doesnt need registers.
654 sym = OP_SYMBOL (IC_RESULT (ic));
656 // Does it need any registers?
662 // Is it already split?
668 // Does it already have registers assigned?
669 if (bitVectBitValue (_G.regAssigned, sym->key))
674 // Will it live past this instruction?
675 if (sym->liveTo <= ic->seq)
680 // MLH Doesnt understand this.
681 /* "Iif some liverange has been spilt at the block level
682 and this one live beyond this block then spil this
684 if (_G.blockSpill && sym->liveTo > ebbs[i]->lSeq)
690 // Seems that this symbol needs registers. See if
691 // allocating will cause a spill.
692 willCauseSpill = _willCauseSpill (sym->nRegs);
693 spillable = _findSpillable (ic);
695 // If this is remat., then dont waste any regsiters on it.
702 // If trying to allocate will cause a spill, and nothing
703 // else is spillable then this sym looses.
704 if (willCauseSpill && bitVectIsZero (spillable))
710 // If this will cause a spill, and it already has a spill
711 // location then spill this if it is the least used.
712 if (willCauseSpill && sym->usl.spillLoc)
714 symbol *leastUsed = _leastUsedLR (_liveRangesWith (spillable, _allLRs, ebbs[i], ic));
715 if (leastUsed && leastUsed->used > sym->used)
722 // Hmm. Here we could have no registers available but
723 // we'll still try to allocate. MLH wonders how this will
726 // Mark this iCode as having registers assigned to it.
727 _G.regAssigned = bitVectSetBit (_G.regAssigned, sym->key);
730 sym->regs[0] = _allocateReg (sym->nRegs);
736 DEFSETFUNC (_deallocStackSpil)
744 /// Compute the register mask for an operand.
746 _rUmaskForOp (operand * op)
751 // "Only temporaries are assigned registers"
755 sym = OP_SYMBOL (op);
757 // If its spilt or no registers are needed, then no regs are assigned.
758 if (sym->isspilt || !sym->nRegs)
761 rumask = newBitVect (REG_ID_MAX);
765 rumask = _markRegBits (rumask, sym->regs[0]);
771 /// Returns bit vector of registers used in iCode.
773 _regsUsedIniCode (iCode * ic)
775 bitVect *rmask = newBitVect (REG_ID_MAX);
779 // Special cases first.
782 rmask = bitVectUnion (rmask, _rUmaskForOp (IC_COND (ic)));
786 if (ic->op == JUMPTABLE)
788 rmask = bitVectUnion (rmask, _rUmaskForOp (IC_JTCOND (ic)));
792 // Now the good old left, right, and result.
795 rmask = bitVectUnion (rmask, _rUmaskForOp (IC_LEFT (ic)));
800 rmask = bitVectUnion (rmask, _rUmaskForOp (IC_RIGHT (ic)));
805 rmask = bitVectUnion (rmask, _rUmaskForOp (IC_RESULT (ic)));
813 /// Compute the helper bitVect that contains the register used mask.
815 _createRegMask (eBBlock ** ebbs, int count)
820 for (i = 0; i < count; i++)
824 // If this code is unused, skip it.
825 if (ebbs[i]->noPath &&
826 (ebbs[i]->entryLabel != entryLabel &&
827 ebbs[i]->entryLabel != returnLabel))
832 /* for all instructions */
833 for (ic = ebbs[i]->sch; ic; ic = ic->next)
837 if (SKIP_IC2 (ic) || !ic->rlive)
840 // Mark the registers used in this instruction.
841 ic->rUsed = _regsUsedIniCode (ic);
842 // Mark them as used at least once in the function.
843 _G.funcUsedRegs = bitVectUnion (_G.funcUsedRegs, ic->rUsed);
845 /* now create the register mask for those
846 registers that are in use : this is a
847 super set of ic->rUsed */
848 ic->rMask = newBitVect (REG_ID_MAX + 1);
850 // "For all live Ranges alive at this point"
851 for (j = 1; j < ic->rlive->size; j++)
855 // "If if not alive then continue"
856 if (!bitVectBitValue (ic->rlive, j))
861 // "Find the live range we are interested in"
862 if (!(sym = hTabItemWithKey (liveRanges, j)))
864 werror (E_INTERNAL_ERROR, __FILE__, __LINE__,
865 "createRegMask cannot find live range");
869 // "If no register assigned to it"
870 if (!sym->nRegs || sym->isspilt)
875 // If this has any registers allocated, mark them as such.
878 ic->rMask = _markRegBits (ic->rMask, sym->regs[0]);
886 izt_assignRegisters (eBBlock ** ebbs, int count)
888 // Contains a flat version of ebbs used in code generation.
891 // Clear the bit vector of registers used in this function.
892 // Assumes that assignRegisters is called once per function.
893 setToNull ((void *) &_G.funcUsedRegs);
895 // First scan each live range, and figure out what registers
897 _computeRequiredRegs ();
899 // Now allocate the registers.
900 _serialRegAssign (ebbs, count);
902 // And create the helper register used mask.
903 _createRegMask (ebbs, count);
905 // Turn the bblock array into an optimised list of iCode entries.
906 chain = iCodeLabelOptimize (iCodeFromeBBlock (ebbs, count));
908 // Redo the stack offsets. This will remove any redundent stack
909 // locations ie iTemps that exist only in registers.
914 // Deallocate any stack spill locations.
915 applyToSet (_G.spill.set, _deallocStackSpil);
918 setToNull ((void **) &_G.spill.set);
919 setToNull ((void **) &_G.spill.vect);
921 // And free all registers.
926 warningStopper (void)
928 // For now references all unused functions.
930 _packRegisters (NULL);
931 _getSubReg (NULL, 0, 0);