Optimize the x86/x86_64 stack alignment sequence.
[dyninst.git] / dyninstAPI / src / registerSpace.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // $Id: registerSpace.C,v 1.25 2008/10/27 17:23:53 mlam Exp $
33
34 #include "dyninstAPI/src/symtab.h"
35 #include "dyninstAPI/src/process.h"
36 #include "dyninstAPI/src/inst.h"
37 #include "dyninstAPI/src/instP.h"
38 #include "dyninstAPI/src/instPoint.h"
39 #include "dyninstAPI/src/ast.h"
40 #include "dyninstAPI/src/util.h"
41 #include "dyninstAPI/src/debug.h"
42
43 #include "dyninstAPI/src/registerSpace.h"
44
45 #include "dyninstAPI/h/BPatch.h"
46 #include "dyninstAPI/src/BPatch_collections.h"
47 #include "dyninstAPI/h/BPatch_type.h"
48 #include "dyninstAPI/src/BPatch_libInfo.h" // For instPoint->BPatch_point mapping
49
50 #include "dyninstAPI/h/BPatch_point.h"
51 #include "dyninstAPI/h/BPatch_memoryAccess_NP.h"
52
53 #include <map>
54
55 #if defined(arch_sparc)
56 #include "dyninstAPI/src/inst-sparc.h"
57 #elif defined(arch_power)
58 #include "dyninstAPI/src/inst-power.h"
59 #include "dyninstAPI/src/emit-power.h"
60 #elif defined(arch_x86) || defined(arch_x86_64)
61 #include "dyninstAPI/src/inst-x86.h"
62 #include "dyninstAPI/src/emit-x86.h"
63 #endif
64
65 registerSpace *registerSpace::globalRegSpace_ = NULL;
66 registerSpace *registerSpace::globalRegSpace64_ = NULL;
67
68 #if defined(cap_liveness)
69 bitArray registerSpace::callRead_;
70 bitArray registerSpace::callWritten_;
71 bitArray registerSpace::returnRead_;
72 bitArray registerSpace::syscallRead_;
73 bitArray registerSpace::syscallWritten_;
74
75 bitArray registerSpace::callRead64_;
76 bitArray registerSpace::callWritten64_;
77 bitArray registerSpace::returnRead64_;
78 bitArray registerSpace::syscallRead64_;
79 bitArray registerSpace::syscallWritten64_;
80 bitArray registerSpace::allRegs_;
81 bitArray registerSpace::allRegs64_;
82 #endif
83
84 bool registerSpace::hasXMM = false;
85
86 void registerSlot::cleanSlot() {
87     assert(this);
88     // number does not change
89     refCount = 0;
90     //liveState = live;
91     //liveState does not change
92     keptValue = false;
93     beenUsed = false;
94     // initialState doesn't change
95     // offLimits doesn't change
96     spilledState = unspilled;
97     saveOffset = 0;
98     // type doesn't change
99 }
100
101 unsigned registerSlot::encoding() const {
102     // Should write this for all platforms when the encoding is done.
103 #if defined(arch_power)
104     switch (type) {
105     case GPR:
106         return registerSpace::GPR(number);
107         break;
108     case FPR:
109         return registerSpace::FPR(number);
110         break;
111     case SPR:
112         return registerSpace::SPR(number);
113         break;
114     default:
115         assert(0);
116         return REG_NULL;
117         break;
118     }
119 #elif defined(arch_x86) || defined(arch_x86_64)
120     // Should do a mapping here from entire register space to "expected" encodings.
121     return number;
122 #else
123     assert(0);
124     return 0;
125 #endif
126 }
127
128 registerSpace *registerSpace::getRegisterSpace(unsigned width) {
129     if (globalRegSpace_ == NULL) initialize();
130     registerSpace *ret = (width == 4) ? globalRegSpace_ : globalRegSpace64_;
131     assert(ret);
132     return ret;
133 }
134
135 registerSpace *registerSpace::getRegisterSpace(AddressSpace *as) {
136     return getRegisterSpace(as->getAddressWidth());
137 }
138
139 registerSpace *registerSpace::conservativeRegSpace(AddressSpace *proc) {
140     registerSpace *ret = getRegisterSpace(proc);
141     ret->specializeSpace(arbitrary);
142     return ret;
143 }
144
145 registerSpace *registerSpace::optimisticRegSpace(AddressSpace *proc) {
146     registerSpace *ret = getRegisterSpace(proc);
147     ret->specializeSpace(ABI_boundary);
148     return ret;
149 }
150
151 registerSpace *registerSpace::irpcRegSpace(AddressSpace *proc) {
152    registerSpace *rspace = conservativeRegSpace(proc);
153    rspace->initRealRegSpace();
154    return rspace;
155 }
156
157 registerSpace *registerSpace::savedRegSpace(AddressSpace *proc) {
158     registerSpace *ret = getRegisterSpace(proc);
159     ret->specializeSpace(allSaved);
160     return ret;
161 }
162
163 registerSpace *registerSpace::actualRegSpace(instPoint *iP, 
164                                              callWhen 
165 #if defined(cap_liveness)
166                                              when 
167 #endif
168                                              ) 
169 {
170 #if defined(cap_liveness)
171     if (BPatch::bpatch->livenessAnalysisOn()) {
172         assert(iP);
173         registerSpace *ret = NULL;
174
175         liveness_printf("%s[%d] Asking for actualRegSpace for iP at 0x%lx, dumping info:\n",
176                         FILE__, __LINE__, iP->addr());
177         liveness_cerr << iP->liveRegisters(when) << endl;
178
179         ret = getRegisterSpace(iP->proc());
180         ret->specializeSpace(iP->liveRegisters(when));
181
182         ret->cleanSpace();
183         return ret;
184     }
185 #endif
186     // Use one of the other registerSpaces...
187     // If we're entry/exit/call site, return the optimistic version
188     /*    if (iP->getPointType() == functionEntry)
189         return optimisticRegSpace(iP->proc());
190     if (iP->getPointType() == functionExit)
191         return optimisticRegSpace(iP->proc());
192     if (iP->getPointType() == callSite)
193     return optimisticRegSpace(iP->proc());*/
194     
195     return conservativeRegSpace(iP->proc());
196 }
197
198 void registerSpace::overwriteRegisterSpace(Register,
199                                            Register) {
200     // This should _NOT_ be used; it's defined to catch errors.
201     assert(0);
202 }
203
204 // Ugly IA-64-age.
205 void registerSpace::overwriteRegisterSpace64(Register first,
206                                              Register last) {
207     delete globalRegSpace64_;
208     globalRegSpace64_ = new registerSpace();
209     
210     pdvector<registerSlot *> regs;
211     for (unsigned i = first; i <= last; i++) {
212         char buf[128];
213         sprintf(buf, "reg%d", i);
214         regs.push_back(new registerSlot(i,
215                                         buf,
216                                         false,
217                                         registerSlot::deadAlways,
218                                         registerSlot::GPR));
219     }
220     createRegSpaceInt(regs, globalRegSpace64_);
221 }
222
223
224 registerSpace::registerSpace() :
225     savedFlagSize(0),
226     currStackPointer(0),
227     registers_(uiHash),
228     addr_width(0)
229 {
230 }
231
232 registerSpace::~registerSpace()
233 {
234     for (regDictIter i = registers_.begin(); i != registers_.end(); i++) {
235         delete i.currval();
236     }
237 }
238
239 void registerSpace::createRegisterSpace(pdvector<registerSlot *> &registers) {
240     // We need to initialize the following:
241     // registers_ (dictionary_hash)
242     // GPRs_ (vector of pointers to elements in registers_
243     // FPRs_ (vector of pointers ...)
244     // SPRs_ (...)
245
246     assert(globalRegSpace_ == NULL);
247     globalRegSpace_ = new registerSpace();
248     globalRegSpace_->addr_width = 4;
249     createRegSpaceInt(registers, globalRegSpace_);
250
251 }
252
253 void registerSpace::createRegisterSpace64(pdvector<registerSlot *> &registers) {
254     // We need to initialize the following:
255     // registers_ (dictionary_hash)
256     // GPRs_ (vector of pointers to elements in registers_
257     // FPRs_ (vector of pointers ...)
258     // SPRs_ (...)
259
260     assert(globalRegSpace64_ == NULL);
261     globalRegSpace64_ = new registerSpace();
262     globalRegSpace64_->addr_width = 8;
263     createRegSpaceInt(registers, globalRegSpace64_);
264     
265 }
266
267 void registerSpace::createRegSpaceInt(pdvector<registerSlot *> &registers,
268                                       registerSpace *rs) {
269     for (unsigned i = 0; i < registers.size(); i++) {
270         Register reg = registers[i]->number;
271
272         rs->registers_[reg] = registers[i];
273
274         rs->registersByName[registers[i]->name] = registers[i]->number;
275
276         switch (registers[i]->type) {
277         case registerSlot::GPR: 
278             rs->GPRs_.push_back(registers[i]);
279             break;
280         case registerSlot::FPR:
281             rs->FPRs_.push_back(registers[i]);
282             break;
283         case registerSlot::SPR:
284             rs->SPRs_.push_back(registers[i]);
285             break;
286         case registerSlot::realReg:
287             rs->realRegisters_.push_back(registers[i]);
288             break;
289         default:
290             fprintf(stderr, "Error: no match for %d\n", registers[i]->type);
291             assert(0);
292             break;
293         }
294     }
295
296 }
297
298 bool registerSpace::trySpecificRegister(codeGen &gen, Register num, 
299                                         bool noCost)
300 {
301     registerSlot *tmp;
302     registers_.find(num, tmp);
303     if (!tmp) return false;
304
305     registerSlot *reg = registers_[num];
306     if (reg->offLimits) return false;
307     else if (reg->refCount > 0) return false;
308     else if (reg->liveState == registerSlot::live) {
309         if (!spillRegister(num, gen, noCost)) {
310             return false;
311         }
312     }
313     else if (reg->keptValue) {
314       return false;
315     }
316     
317     reg->markUsed(true);
318
319     regalloc_printf("Allocated register %d\n", num);
320
321     return true;
322 }
323
324 bool registerSpace::allocateSpecificRegister(codeGen &gen, Register num,
325                                              bool noCost) 
326 {
327     registerSlot *tmp;
328     registers_.find(num, tmp);
329     if (!tmp) return false;
330
331     registerSlot *reg = registers_[num];
332     if (reg->offLimits) return false;
333     else if (reg->refCount > 0) return false;
334     else if (reg->liveState == registerSlot::live) {
335         if (!spillRegister(num, gen, noCost)) {
336             return false;
337         }
338     }
339     else if (reg->keptValue) {
340         if (!stealRegister(num, gen, noCost)) return false;
341     }
342     
343     reg->markUsed(true);
344
345     regalloc_printf("Allocated register %d\n", num);
346
347     return true;
348 }
349
350 Register registerSpace::getScratchRegister(codeGen &gen, bool noCost) {
351     pdvector<Register> empty;
352     return getScratchRegister(gen, empty, noCost);
353 }
354
355 Register registerSpace::getScratchRegister(codeGen &gen, pdvector<Register> &excluded, bool noCost) {
356    static int num_allocs = 0;
357
358     pdvector<registerSlot *> couldBeStolen;
359     pdvector<registerSlot *> couldBeSpilled;
360
361     debugPrint();
362
363     registerSlot *toUse = NULL;
364
365     for (unsigned i = 0; i < GPRs_.size(); i++) {
366         registerSlot *reg = GPRs_[i];
367
368         regalloc_printf("%s[%d]: getting scratch register, examining %d of %d: reg %d, offLimits %d, refCount %d, liveState %s, keptValue %d\n",
369                         FILE__, __LINE__, i, GPRs_.size(),
370                         reg->number,
371                         reg->offLimits,
372                         reg->refCount,
373                         (reg->liveState == registerSlot::live) ? "live" : ((reg->liveState == registerSlot::dead) ? "dead" : "spilled"),
374                         reg->keptValue);
375
376         bool found = false;
377         for (unsigned int i = 0; i < excluded.size(); ++i) {
378            Register &ex_reg = excluded[i];
379            if (reg->number == ex_reg) {
380               found = true;
381               break;
382            }
383         }
384
385         if (found) continue;
386
387         if (reg->offLimits) continue;
388         if (reg->refCount > 0) continue;
389         if (reg->liveState == registerSlot::live) {
390             // Don't do anything for now, but add to the "could be" list
391             couldBeSpilled.push_back(reg);
392             continue;
393         }
394         if (reg->keptValue) {
395             // As above
396             couldBeStolen.push_back(reg);
397             continue;
398         }
399         // Hey, got one.
400         toUse = reg;
401         break;
402     }
403 /*
404     if (toUse == NULL) {
405         // Argh. Let's assume spilling is cheaper
406         for (unsigned i = 0; i < couldBeSpilled.size(); i++) {
407             if (spillRegister(couldBeSpilled[i]->number, gen, noCost)) {
408                 toUse = couldBeSpilled[i];
409                 break;
410             }
411         }
412     }
413 */    
414     // Still?
415     if (toUse == NULL) {
416         for (unsigned i = 0; i < couldBeStolen.size(); i++) {
417             if (stealRegister(couldBeStolen[i]->number, gen, noCost)) {
418                 toUse = couldBeStolen[i];
419                 break;
420             }
421         }
422     }
423
424     if (toUse == NULL) {
425         // Crap.
426         debugPrint();
427         return REG_NULL;
428     }
429
430     toUse->alloc_num = num_allocs;
431     num_allocs++;
432
433     toUse->markUsed(false);
434     return toUse->number;
435 }
436
437 Register registerSpace::allocateRegister(codeGen &gen, 
438                                          bool noCost) 
439 {
440     regalloc_printf("Allocating and retaining register...\n");
441     Register reg = getScratchRegister(gen, noCost);
442     regalloc_printf("retaining register %d\n", reg);
443     if (reg == REG_NULL) return REG_NULL;
444
445     registers_[reg]->refCount = 1;
446     regalloc_printf("Allocated register %d\n", reg);
447     return reg;
448 }
449
450 bool registerSpace::spillRegister(Register reg, codeGen &/*gen*/, bool /*noCost*/) {
451     assert(!registers_[reg]->offLimits);
452
453     assert(0 && "Unimplemented!");
454
455     return true;
456 }
457
458 bool registerSpace::stealRegister(Register reg, codeGen &gen, bool /*noCost*/) {
459     // Can be made a return false; this for correctness.
460     assert(registers_[reg]->refCount == 0);
461     assert(registers_[reg]->keptValue == true);
462     assert(registers_[reg]->liveState != registerSlot::live);
463
464     regalloc_printf("Stealing register %d\n", reg);
465
466     // Let the AST know it just lost...
467     if (!gen.tracker()->stealKeptRegister(registers_[reg]->number)) return false;
468     registers_[reg]->keptValue = false;
469     
470     return true;
471 }
472
473
474 // This might mean something different later, but for now means
475 // "Save special purpose registers". We may want to define a "volatile"
476 // later - something like "can be unintentionally nuked". For example,
477 // x86 flags register. 
478 #if defined(arch_x86_64) || defined(arch_x86)
479 bool registerSpace::checkVolatileRegisters(codeGen &gen,
480                                            registerSlot::livenessState_t state)
481 {
482     if (addr_width == 8) {
483         for (unsigned i = REGNUM_OF; i <= REGNUM_RF; i++) {
484             if (registers_[i]->liveState == state)
485                 return true;
486         }
487         return false;
488     }
489
490     assert(addr_width == 4);
491     return (registers_[IA32_FLAG_VIRTUAL_REGISTER]->liveState == state);
492 }
493 #else
494 bool registerSpace::checkVolatileRegisters(codeGen &,
495                                            registerSlot::livenessState_t)
496 {
497     assert(0);
498     return false;
499 }
500 #endif
501
502 #if defined(arch_x86_64) || defined(arch_x86)
503 bool registerSpace::saveVolatileRegisters(codeGen &gen)
504 {
505     savedFlagSize = 0;
506     if (!checkVolatileRegisters(gen, registerSlot::live))
507         return false;
508
509     // Okay, save.
510     if (addr_width == 8) {
511         // save flags (PUSHFQ)
512         emitSimpleInsn(0x9C, gen);
513
514         // And mark flags as spilled.
515         for (unsigned i = REGNUM_OF; i <= REGNUM_RF; i++) {
516             registers_[i]->liveState = registerSlot::spilled;
517         }
518
519     } else {
520         assert(addr_width == 4);
521
522         emitPush(RealRegister(REGNUM_EAX), gen);
523         emitSimpleInsn(0x9f, gen);
524         emitSaveO(gen);
525         gen.markRegDefined(REGNUM_EAX);
526         //emitSimpleInsn(PUSHFD, gen);
527         registers_[IA32_FLAG_VIRTUAL_REGISTER]->liveState =
528             registerSlot::spilled;
529     }
530
531     savedFlagSize = addr_width;
532     return true;
533 }
534 #else
535 bool registerSpace::saveVolatileRegisters(codeGen &) {
536     assert(0);
537     return true;
538 }
539 #endif
540
541 #if defined(arch_x86_64) || defined(arch_x86)
542 bool registerSpace::restoreVolatileRegisters(codeGen &gen)
543 {
544     if (!checkVolatileRegisters(gen, registerSlot::spilled))
545         return false;
546
547     // Okay, restore.
548     if (addr_width == 8) {
549         // restore flags (POPFQ)
550         emitSimpleInsn(0x9D, gen);
551
552         // Don't care about their state...
553
554     } else {
555         assert(addr_width == 4);
556
557         emitRestoreO(gen);
558         emitSimpleInsn(0x9E, gen);
559         emitPop(RealRegister(REGNUM_EAX), gen);
560         // State stays at spilled, which is incorrect - but will never matter.
561     }
562
563     return true;
564 }
565 #else
566 bool registerSpace::restoreVolatileRegisters(codeGen &) {
567     assert(0);
568     return true;
569 }
570 #endif
571
572 // Free the specified register (decrement its refCount)
573 void registerSpace::freeRegister(Register num) 
574 {
575     registerSlot *reg = findRegister(num);
576     if (!reg) return;
577
578     reg->refCount--;
579     regalloc_printf("Freed register %d: refcount now %d\n", num, reg->refCount);
580
581     if( reg->refCount < 0 ) {
582         //bperr( "Freed free register!\n" );
583         reg->refCount = 0;
584     }
585
586 #if defined(arch_x86)
587     if (reg->refCount == 0 && !registers_[num]->keptValue) {
588        markVirtualDead(num);
589     }
590 #endif
591     return;
592
593 }
594
595 // Free the register even if its refCount is greater that 1
596 void registerSpace::forceFreeRegister(Register num) 
597 {
598     registerSlot *reg = findRegister(num);
599     if (!reg) return;
600
601     reg->refCount = 0;
602 }
603
604 // DO NOT USE THIS!!!! to tell if you can use a register as
605 // a scratch register; do that with trySpecificRegister
606 // or allocateSpecificRegister. This is _ONLY_ to determine
607 // if a register should be saved (e.g., over a call).
608 bool registerSpace::isFreeRegister(Register num) {
609     registerSlot *reg = findRegister(num);
610     if (!reg) return false;
611
612     if (reg->refCount > 0)
613         return false; 
614     if (reg->keptValue) 
615       return false;
616     return true;
617 }
618
619 // Bump up the reference count. Occasionally, we underestimate it
620 // and call this routine to correct this.
621 void registerSpace::incRefCount(Register num)
622 {
623     registerSlot *reg = findRegister(num);
624     if (!reg) return;
625     reg->refCount++;
626 }
627
628 void registerSpace::cleanSpace() {
629     regalloc_printf("============== CLEAN ==============\n");
630
631     for (regDictIter i = registers_.begin(); i != registers_.end(); i++) {
632         i.currval()->cleanSlot();
633     }
634     for (unsigned i=0; i<realRegisters_.size(); i++) {
635        realRegisters_[i]->cleanSlot();
636     }
637 }
638
639 bool registerSpace::restoreAllRegisters(codeGen &, bool) {
640     assert(0);
641     return true;
642 }
643
644 bool registerSpace::restoreRegister(Register, codeGen &, bool /*noCost*/) 
645 {
646     assert(0);
647     return true;
648 }
649
650 bool registerSpace::popRegister(Register, codeGen &, bool) {
651     assert(0);
652     return true;
653 }
654
655 bool registerSpace::markReadOnly(Register) {
656     assert(0);
657     return true;
658 }
659
660 bool registerSpace::readProgramRegister(codeGen &gen,
661                                         Register source,
662                                         Register destination,
663                                         unsigned 
664 #if !defined(arch_power)
665                                         size
666 #endif  
667
668 {
669 #if !defined(arch_power)
670     emitLoadPreviousStackFrameRegister((Address)source,
671                                        destination,
672                                        gen,
673                                        size,
674                                        true);
675     return true;
676 #else
677     // Real version that uses stored information
678
679     // First step: identify the registerSlot that contains information
680     // about the source register.
681     // cap_emitter
682
683     registerSlot *src = registers_[source];
684     assert(src);
685     registerSlot *dest = registers_[destination];
686     assert(dest);
687
688     // Okay. We need to know where the register is compared with our
689     // current location vis-a-vis the stack pointer. Now, on most
690     // platforms this doesn't matter, as the SP never moves. Well, not
691     // so x86. 
692     switch (src->spilledState) {
693     case registerSlot::unspilled:
694             printf(" emitMovRegToReg source %d dest %d \n", source, destination);
695                     printf(" emitMovRegToReg source %d dest %d GPR %d SPR %d \n", src->type, dest->type, registerSlot::GPR, registerSlot::SPR);
696                             printf(" emitMovRegToReg source %d dest %d \n", src->number, dest->number);
697
698         gen.codeEmitter()->emitMoveRegToReg(src, dest, gen);
699         return true;
700         break;
701     case registerSlot::framePointer: {
702         registerSlot *frame = registers_[framePointer()];
703         assert(frame);
704
705         // We can't use existing mechanisms because they're all built
706         // off the "non-instrumented" case - emit a load from the
707         // "original" frame pointer, whereas we want the current one. 
708         gen.codeEmitter()->emitLoadRelative(destination, src->saveOffset, framePointer(),  gen.addrSpace()->getAddressWidth(), gen);
709         return true;
710         break;
711     }
712     default:
713         assert(0);
714         return false;
715         break;
716     }
717 #endif         
718     
719 }
720 bool registerSpace::writeProgramRegister(codeGen &gen,
721                                          Register destination,
722                                          Register source,
723                                          unsigned 
724 #if !defined(arch_x86) && !defined(arch_power)
725                                          size
726 #endif
727 ) {
728 #if !defined(arch_x86) && !defined(arch_power)
729     emitStorePreviousStackFrameRegister((Address) destination,
730                                         source,
731                                         gen,
732                                         size,
733                                         true);
734     return true;
735 #else
736     registerSlot *src = registers_[source];
737     assert(source);
738     registerSlot *dest = registers_[destination];
739     assert(dest);
740
741     // Okay. We need to know where the register is compared with our
742     // current location vis-a-vis the stack pointer. Now, on most
743     // platforms this doesn't matter, as the SP never moves. Well, not
744     // so x86. 
745
746     switch (src->spilledState) {
747     case registerSlot::unspilled:
748         if (source != destination)
749             gen.codeEmitter()->emitMoveRegToReg(source, destination, gen);
750         return true;
751         break;
752     case registerSlot::framePointer: {
753         registerSlot *frame = registers_[framePointer()];
754         assert(frame);
755
756         // When this register was saved we stored its offset from the base
757         // pointer.  Use that to load it.
758         int addrWidth = gen.addrSpace()->getAddressWidth();
759         gen.codeEmitter()->emitStoreRelative(source,
760                                              addrWidth * dest->saveOffset,
761                                              framePointer(),
762                                              addrWidth,
763                                              gen);
764         return true;
765         break;
766     }
767     default:
768         assert(0);
769         return false;
770         break;
771     }
772 #endif
773 }
774
775
776 registerSlot *registerSpace::findRegister(Register source) {
777     // Oh, oops... we're handed a register number... and we can't tell if it's
778     // GPR, FPR, or SPR...
779     if (source == REG_NULL) return NULL;
780     registerSlot *reg = NULL;
781     if (!registers_.find(source, reg)) return NULL;
782     return reg;
783 }
784
785 registerSlot *registerSpace::findRegister(RealRegister source) {
786     return realRegisters_[source.reg()];
787 }
788
789 bool registerSpace::markSavedRegister(RealRegister num, int offsetFromFP) {
790    regalloc_printf("Marking register %d as saved, %d from frame pointer\n",
791                    num.reg(), offsetFromFP);
792    registerSlot *s = findRegister(num);
793    return markSavedRegister(s, offsetFromFP);   
794 }
795
796 bool registerSpace::markSavedRegister(Register num, int offsetFromFP) {
797     regalloc_printf("Marking register %d as saved, %d from frame pointer\n",
798                     num, offsetFromFP);
799     // Find the register slot
800     registerSlot *s = findRegister(num);
801     return markSavedRegister(s, offsetFromFP);
802 }
803
804 bool registerSpace::markSavedRegister(registerSlot *s, int offsetFromFP) {
805     if (s == NULL)  {
806         // We get this on platforms where we save registers we don't use in
807         // code generation... like, say, RSP or RBP on AMD-64.
808         //fprintf(stderr, "ERROR: unable to find register %d\n", num);
809         return false;
810     }
811
812     if (s->spilledState != registerSlot::unspilled) {
813         // Things to do... add this check in, yo. Right now we don't clean
814         // properly.
815         
816 //        assert(0);
817     }
818
819     s->liveState = registerSlot::spilled;
820
821     s->spilledState = registerSlot::framePointer;
822     s->saveOffset = offsetFromFP;
823     return true;
824 }
825
826 void registerSlot::debugPrint(const char *prefix) {
827     if (!dyn_debug_regalloc) return;
828
829         if (prefix) fprintf(stderr, "%s", prefix);
830         fprintf(stderr, "Num: %d, name %s, type %s, refCount %d, liveState %s, beenUsed %d, initialState %s, offLimits %d, keptValue %d, alloc %d\n",
831                 number, 
832                 name.c_str(),
833                 (type == GPR) ? "GPR" : ((type == FPR) ? "FPR" : "SPR"),
834                 refCount, 
835                 (liveState == live ) ? "live" : ((liveState == spilled) ? "spilled" : "dead"),
836                 beenUsed, 
837                 (initialState == deadAlways) ? "always dead" : ((initialState == deadABI) ? "ABI dead" : "always live"),
838                 offLimits, 
839                 keptValue,
840                 alloc_num);
841 }
842
843 void registerSpace::debugPrint() {
844     if (!dyn_debug_regalloc) return;
845
846         // Dump out our data
847         fprintf(stderr, "Beginning debug print of registerSpace at %p...", this);
848         fprintf(stderr, "GPRs: %ld, FPRs: %ld, SPRs: %ld\n", 
849            (long) GPRs_.size(), (long) FPRs_.size(), (long) SPRs_.size());
850         fprintf(stderr, "Stack pointer is at %d\n",
851                 currStackPointer);
852         fprintf(stderr, "Register dump:");
853         fprintf(stderr, "=====GPRs=====\n");
854         for (unsigned i = 0; i < GPRs_.size(); i++) {
855       GPRs_[i]->debugPrint("\t");
856    }
857         for (unsigned i = 0; i < FPRs_.size(); i++) {
858       FPRs_[i]->debugPrint("\t");
859    }
860         for (unsigned i = 0; i < SPRs_.size(); i++) {
861       SPRs_[i]->debugPrint("\t");
862    }
863 }
864
865 bool registerSpace::markKeptRegister(Register reg) {
866         regalloc_printf("Marking register %d as kept\n", reg);
867    registers_[reg]->keptValue = true;
868    return false;
869 }
870
871 void registerSpace::unKeepRegister(Register reg) {
872         regalloc_printf("Marking register %d as unkept\n", reg);
873    registers_[reg]->keptValue = false;
874 }
875
876
877 void registerSpace::specializeSpace(rs_location_t state) {
878     for (regDictIter i = registers_.begin(); i != registers_.end(); i++) {
879         registerSlot *reg = i.currval();
880         switch (state) {
881         case arbitrary:
882             if (reg->initialState == registerSlot::deadAlways)
883                 reg->liveState = registerSlot::dead;
884             else
885                 reg->liveState = registerSlot::live;
886             break;
887         case ABI_boundary:
888             if ((reg->initialState == registerSlot::deadABI) ||
889                 (reg->initialState == registerSlot::deadAlways))
890                 reg->liveState = registerSlot::dead;
891             else
892                 reg->liveState = registerSlot::live;
893             break;
894         case allSaved:
895             reg->liveState = registerSlot::dead;
896             break;
897         default:
898             assert(0);
899         }
900     }
901     cleanSpace();
902
903     regalloc_printf("%s[%d]: specialize space done with argument %d\n", FILE__, __LINE__, state);
904 }
905
906 bool registerSpace::anyLiveGPRsAtEntry() const {
907     for (unsigned i = 0; i < GPRs_.size(); i++) {
908         if (GPRs_[i]->liveState != registerSlot::dead)
909             return true;
910     }
911     return false;
912 }
913
914 bool registerSpace::anyLiveFPRsAtEntry() const {
915     for (unsigned i = 0; i < FPRs_.size(); i++) {
916         if (FPRs_[i]->liveState != registerSlot::dead)
917             return true;
918     }
919     return false;
920 }
921
922 bool registerSpace::anyLiveSPRsAtEntry() const {
923     for (unsigned i = 0; i < SPRs_.size(); i++) {
924         if (SPRs_[i]->liveState != registerSlot::dead)
925             return true;
926     }
927     return false;
928 }
929
930 pdvector<registerSlot *>& registerSpace::trampRegs()
931 {
932 #if defined(arch_x86) || defined(arch_x86_64)
933    if (addr_width == 4)
934       return realRegs();
935 #endif
936    return GPRs_;
937 }
938
939 registerSlot *registerSpace::operator[](Register reg) {
940     return registers_[reg];
941 }
942
943 #if defined(cap_liveness)
944 const bitArray &registerSpace::getCallReadRegisters() const {
945     if (addr_width == 4)
946         return callRead_;
947     else if (addr_width == 8)
948         return callRead64_;
949     else {
950         assert(0);
951         return callRead_;
952     }
953 }
954     
955
956 const bitArray &registerSpace::getCallWrittenRegisters() const {
957     if (addr_width == 4)
958         return callWritten_;
959     else if (addr_width == 8)
960         return callWritten64_;
961     else {
962         assert(0);
963         return callWritten_;
964     }
965 }
966     
967 const bitArray &registerSpace::getReturnReadRegisters() const {
968     if (addr_width == 4)
969         return returnRead_;
970     else if (addr_width == 8)
971         return returnRead64_;
972     else {
973         assert(0);
974         return returnRead_;
975     }
976 }
977
978 const bitArray &registerSpace::getSyscallReadRegisters() const {
979     if (addr_width == 4)
980         return syscallRead_;
981     else if (addr_width == 8)
982         return syscallRead64_;
983     else {
984         assert(0);
985         return syscallRead_;
986     }
987 }
988 const bitArray &registerSpace::getSyscallWrittenRegisters() const {
989     if (addr_width == 4)
990         return syscallWritten_;
991     else if (addr_width == 8)
992         return syscallWritten64_;
993     else {
994         assert(0);
995         return syscallWritten_;
996     }
997 }
998
999 const bitArray &registerSpace::getAllRegs() const
1000 {
1001    if (addr_width == 4)
1002       return allRegs_;
1003    else if (addr_width == 8)
1004       return allRegs64_;
1005    else {
1006       assert(0);
1007       return allRegs_;
1008    }   
1009 }
1010
1011 #endif
1012
1013 bitArray registerSpace::getBitArray()  {
1014 #if defined(arch_x86) || defined(arch_x86_64)
1015     return bitArray(REGNUM_IGNORED+1);
1016 #elif defined(arch_power)
1017     return bitArray(lastReg);
1018 #else
1019     return bitArray();
1020 #endif
1021 }
1022
1023 // Big honkin' name->register map
1024
1025 void registerSpace::getAllRegisterNames(std::vector<std::string> &ret) {
1026     // Currently GPR only
1027     for (unsigned i = 0; i < GPRs_.size(); i++) {
1028         ret.push_back(GPRs_[i]->name);
1029     }
1030 }
1031
1032 Register registerSpace::getRegByName(const std::string name) {
1033     map<std::string,Register>::iterator cur = registersByName.find(name);
1034     if (cur == registersByName.end())
1035         return REG_NULL;
1036     return (*cur).second;
1037 }
1038
1039 std::string registerSpace::getRegByNumber(Register reg) {
1040     return registers_[reg]->name;
1041 }
1042
1043 // If we have defined realRegisters_ (IA-32 and 32-bit mode AMD-64) 
1044 // return that. Otherwise return GPRs. 
1045 pdvector<registerSlot *> &registerSpace::realRegs() {
1046     if (realRegisters_.size())
1047        return realRegisters_;
1048     else
1049        return GPRs();
1050 }
1051
1052 RealRegister registerSpace::findReal(registerSlot *virt_r, bool &already_setup)
1053 {
1054    assert(virt_r);
1055    
1056    int oldest_reg = -1;
1057    int oldest_free_reg = -1;
1058    int used_free_reg = -1;
1059    already_setup = false;
1060    
1061    for (unsigned i=0; i<regState().size(); i++) {
1062       RealRegsState &real_reg = regState()[i];
1063       if (!real_reg.is_allocatable)
1064          continue;
1065
1066       if (virt_r == real_reg.contains) {
1067          //We already have this virtual register stored in a real register.
1068          // just return it.
1069          real_reg.last_used = timeline()++;
1070          already_setup = true;
1071          return RealRegister(i);
1072       }
1073       if (!real_reg.contains &&
1074           real_reg.been_used)
1075       {
1076          used_free_reg = i;
1077       }
1078       if (!real_reg.contains && 
1079           (oldest_free_reg == -1 || 
1080            real_reg.last_used < regState()[oldest_free_reg].last_used)) 
1081       {
1082          //There's a free register, remember it.
1083          oldest_free_reg = i;
1084       }
1085       if (real_reg.contains && 
1086           (oldest_reg == -1 ||
1087            real_reg.last_used < regState()[oldest_reg].last_used))
1088       {
1089          //Keep track of the LRU register, in case we don't
1090          // have anything free.  LRU isn't ideal for register
1091          // allocation, but we're trying to keep this single pass.
1092          oldest_reg = i;
1093       }
1094    }
1095
1096    //We shouldn't have no free registers and no oldest alloced registers.
1097    assert(oldest_free_reg != -1 || oldest_reg != -1 || used_free_reg != -1);
1098    if (used_free_reg != -1)
1099       return RealRegister(used_free_reg);
1100    if (oldest_free_reg != -1) {
1101       return RealRegister(oldest_free_reg);
1102    }
1103    return RealRegister(oldest_reg);
1104 }
1105
1106 void registerSpace::spillReal(RealRegister r, codeGen &gen)
1107 {
1108    if (!regState()[r.reg()].is_allocatable)
1109       return;
1110    if (!regState()[r.reg()].contains)
1111       return;
1112    regs_been_spilled.insert(regState()[r.reg()].contains);
1113    spillToVReg(r, regState()[r.reg()].contains, gen);
1114    freeReal(r);
1115 }
1116
1117 void registerSpace::loadReal(RealRegister r, registerSlot *virt_r, codeGen &gen)
1118 {
1119    
1120    assert(!regState()[r.reg()].contains);
1121    if (regs_been_spilled.count(virt_r)) {
1122       movVRegToReal(virt_r, r, gen);
1123    }
1124    regState()[r.reg()].contains = virt_r;
1125    regState()[r.reg()].last_used = timeline()++;
1126 }
1127
1128 void registerSpace::freeReal(RealRegister r)
1129 {
1130    assert(regState()[r.reg()].contains);
1131    regState()[r.reg()].contains = NULL;
1132    regState()[r.reg()].last_used = timeline()++;
1133 }
1134
1135 RealRegister registerSpace::loadVirtual(registerSlot *virt_r, codeGen &gen)
1136 {
1137    assert(virt_r);
1138    bool done;
1139
1140    RealRegister reg_to_use = findReal(virt_r, done);
1141    if (done) {
1142       return reg_to_use;
1143    }
1144
1145    spillReal(reg_to_use, gen);
1146    loadReal(reg_to_use, virt_r, gen);
1147
1148    return reg_to_use;
1149 }
1150
1151 RealRegister registerSpace::loadVirtual(Register virt_r, codeGen &gen)
1152 {
1153    return loadVirtual((*this)[virt_r], gen);
1154 }
1155
1156 RealRegister registerSpace::loadVirtualForWrite(registerSlot *virt_r, codeGen &gen)
1157 {
1158    assert(virt_r);
1159    bool done;
1160
1161    RealRegister reg_to_use = findReal(virt_r, done);
1162    if (done) {
1163       return reg_to_use;
1164    }
1165
1166    spillReal(reg_to_use, gen);
1167    regState()[reg_to_use.reg()].contains = virt_r;
1168    regState()[reg_to_use.reg()].last_used = timeline()++;
1169
1170    gen.markRegDefined(reg_to_use.reg());
1171    return reg_to_use;
1172 }
1173
1174 RealRegister registerSpace::loadVirtualForWrite(Register virt_r, codeGen &gen)
1175 {
1176    return loadVirtualForWrite((*this)[virt_r], gen);
1177 }
1178
1179 void registerSpace::makeRegisterAvail(RealRegister r, codeGen &gen) {
1180    spillReal(r, gen);
1181    gen.markRegDefined(r.reg());
1182 }
1183
1184 void registerSpace::noteVirtualInReal(registerSlot *v_r, RealRegister r_r)
1185 {
1186    int reg = r_r.reg();
1187
1188    bool already_allocd;
1189    RealRegister old_location = findReal(v_r, already_allocd);
1190    if (already_allocd) {
1191       regState()[old_location.reg()].contains = NULL;
1192       regState()[old_location.reg()].last_used = timeline()++;
1193    }
1194
1195    assert (!regState()[reg].contains);
1196    regState()[reg].contains = v_r;
1197    regState()[reg].last_used = timeline()++;
1198 }
1199
1200 void registerSpace::noteVirtualInReal(Register v_r, RealRegister r_r)
1201 {
1202    noteVirtualInReal((*this)[v_r], r_r);
1203 }
1204
1205 void registerSpace::loadVirtualToSpecific(registerSlot *virt_r, RealRegister real_r, codeGen &gen)
1206 {
1207    bool already_in_reg;
1208    RealRegister old_loc = findReal(virt_r, already_in_reg);
1209    if (already_in_reg && old_loc.reg() == real_r.reg()) {
1210       return;
1211    }
1212
1213    spillReal(real_r, gen);
1214
1215    if (already_in_reg) {
1216       movRegToReg(real_r, old_loc, gen);
1217       freeReal(old_loc);
1218    }
1219    else {
1220       loadReal(real_r, virt_r, gen);
1221    }
1222 }
1223
1224 void registerSpace::loadVirtualToSpecific(Register virt_r, RealRegister real_r, codeGen &gen)
1225 {
1226    loadVirtualToSpecific((*this)[virt_r], real_r, gen);
1227 }
1228
1229 void registerSpace::markVirtualDead(Register num)
1230 {
1231    registerSlot *slot = (*this)[num];
1232    for (unsigned i=0; i<regState().size(); i++) {
1233       if (regState()[i].contains == slot) {
1234          regState()[i].contains = NULL;
1235          regState()[i].last_used = 0;
1236       }
1237    }
1238 }
1239
1240 bool registerSpace::spilledAnything()
1241 {
1242    return regs_been_spilled.size() != 0;
1243 }
1244
1245 /**
1246  * This handles merging register states at merges
1247  * in the generated code CFG.  Used for things like
1248  * 'if' statements.  
1249  * Takes the top level registerState (e.g, the code that was
1250  * generated in an 'if') and emits the saves/restores such to
1251  * takes us back to the preceding registerState (e.g, the code
1252  * we would be in if the 'if' hadn't executed).
1253  **/
1254 void registerSpace::unifyTopRegStates(codeGen &gen)
1255 {
1256    if (addr_width == 8) {
1257       //Not implemented on x86_64 yet
1258       return;
1259    }
1260    if (regStateStack.size() == 0)
1261       return;
1262    assert(regStateStack.size() >= 2);
1263    regState_t *src = regStateStack[regStateStack.size() - 1];
1264    regState_t *dest = regStateStack[regStateStack.size() - 2];
1265
1266    assert(src->registerStates.size() == dest->registerStates.size());
1267    
1268    //Make a map of loaded dest virtuals -> reals
1269    std::map<registerSlot*, unsigned> dest_virts;
1270    for (unsigned i=0; i<dest->registerStates.size(); i++) {
1271       RealRegsState &rrs = dest->registerStates[i];
1272       if (!rrs.is_allocatable || !rrs.contains)
1273          continue;
1274       dest_virts[rrs.contains] = i;
1275    }
1276
1277    //For any loaded virtual in src that's not loaded or not loaded in the 
1278    // proper place in dest,  unload that virtual in src.
1279    for (unsigned i=0; i<src->registerStates.size(); i++) {
1280       RealRegsState &rrs = src->registerStates[i];
1281       if (!rrs.is_allocatable || !rrs.contains) {
1282          //Unloaded in src or uninteresting register
1283          continue;
1284       }
1285       std::map<registerSlot*, unsigned>::iterator j = dest_virts.find(rrs.contains);
1286       if (j != dest_virts.end() && (*j).second == i) {
1287          //Loaded in the same place in dest and src
1288          continue;
1289       }
1290       spillReal(RealRegister(i), gen);
1291    }
1292
1293    //Make a map of loaded src virtuals -> reals
1294    std::map<registerSlot*, unsigned> src_virts;
1295    for (unsigned i=0; i<src->registerStates.size(); i++) {
1296       RealRegsState &rrs = src->registerStates[i];
1297       if (!rrs.is_allocatable || !rrs.contains)
1298          continue;
1299       src_virts[rrs.contains] = i;
1300    }
1301
1302    //For any loaded virtual in dest that's not loaded in src, 
1303    // load that virtual in src. 
1304    for (unsigned i=0; i<dest->registerStates.size(); i++) {
1305       RealRegsState &rrs = dest->registerStates[i];
1306       if (!rrs.is_allocatable || !rrs.contains) {
1307          //Unloaded in src or uninteresting register
1308          continue;
1309       }
1310       std::map<registerSlot*, unsigned>::iterator j = src_virts.find(rrs.contains);
1311       if (j != src_virts.end()) {
1312          //Loaded in src
1313          assert((*j).second == i); //assert it's loaded in the same place
1314          continue;
1315       }
1316       loadReal(RealRegister(i), rrs.contains, gen);
1317    }
1318
1319    for (unsigned i=0; i<src->registerStates.size(); i++) {
1320       assert(src->registerStates[i].contains == dest->registerStates[i].contains);
1321    }
1322
1323    if (dest->pc_rel_offset == -1 && src->pc_rel_offset != -1) {
1324       //src allocated a register for the PCREL operations.  We'll
1325       // have to free that bad boy.
1326       gen.rs()->freeRegister(gen.rs()->pc_rel_reg);
1327    }
1328    regStateStack.pop_back();
1329    delete src;
1330 }
1331
1332 void registerSpace::pushNewRegState()
1333 {
1334    if (regStateStack.size() == 0)
1335       return;
1336    regState_t *new_top = new regState_t();
1337    regState_t *old_top = regStateStack[regStateStack.size()-1];
1338    new_top->pc_rel_offset = old_top->pc_rel_offset;
1339    new_top->timeline = old_top->timeline;
1340    new_top->registerStates = old_top->registerStates;
1341    new_top->stack_height = old_top->stack_height;
1342    regStateStack.push_back(new_top);
1343 }
1344
1345 #if defined(arch_x86) || defined(arch_x86_64)
1346 int& registerSpace::pc_rel_offset()
1347 {
1348    if (!regStateStack.size())
1349       initRealRegSpace();
1350    return regStateStack[regStateStack.size()-1]->pc_rel_offset;
1351 }
1352
1353 int& registerSpace::timeline()
1354 {
1355    if (!regStateStack.size())
1356       initRealRegSpace();
1357    return regStateStack[regStateStack.size()-1]->timeline;
1358 }
1359
1360 std::vector<RealRegsState>& registerSpace::regState()
1361 {
1362    if (!regStateStack.size())
1363       initRealRegSpace();
1364
1365    return regStateStack[regStateStack.size()-1]->registerStates;
1366 }
1367
1368 void registerSpace::incStack(int val) {
1369    if (!regStateStack.size())
1370       initRealRegSpace();
1371    regStateStack[regStateStack.size()-1]->stack_height += val;
1372 }
1373
1374 void registerSpace::setStackHeight(int val) {
1375    if (!regStateStack.size())
1376       initRealRegSpace();
1377    regStateStack[regStateStack.size()-1]->stack_height = val;
1378 }
1379
1380 int registerSpace::getStackHeight()
1381 {
1382    if (!regStateStack.size())
1383       initRealRegSpace();
1384    return regStateStack[regStateStack.size()-1]->stack_height;
1385 }
1386
1387 void registerSpace::setInstFrameSize(int val) {
1388     instFrameSize_ = val;
1389 }
1390
1391 int registerSpace::getInstFrameSize() {
1392     return instFrameSize_;
1393 }
1394
1395 #endif
1396
1397 #if !defined(arch_x86) && !defined(arch_x86_64)
1398 void registerSpace::initRealRegSpace()
1399 {
1400 }
1401
1402 void registerSpace::spillToVReg(RealRegister /*reg*/, registerSlot * /*v_reg*/, 
1403                                 codeGen & /*gen*/)
1404 {
1405    assert(0);
1406 }
1407
1408 void registerSpace::movVRegToReal(registerSlot * /*v_reg*/, RealRegister /*r*/, 
1409                                   codeGen & /*gen*/)
1410 {
1411    assert(0);
1412 }
1413
1414 void registerSpace::movRegToReg(RealRegister /*dest*/, RealRegister /*src*/, codeGen & /*gen*/)
1415 {
1416    assert(0);
1417 }
1418
1419 regState_t::regState_t()
1420 {
1421    assert(0);
1422 }
1423
1424 int& registerSpace::pc_rel_offset()
1425 {
1426    static int none = 0;
1427    return none;
1428 }
1429
1430 int& registerSpace::timeline()
1431 {
1432    static int none = 0;
1433    return none;
1434 }
1435
1436 std::vector<RealRegsState>& registerSpace::regState()
1437 {
1438    static std::vector<RealRegsState> none;
1439    return none;
1440 }
1441
1442 void registerSpace::incStack(int) {
1443 }
1444
1445 void registerSpace::setStackHeight(int) {
1446 }
1447
1448 int registerSpace::getStackHeight()
1449 {
1450    return 0;
1451 }
1452
1453 void registerSpace::setInstFrameSize(int) {
1454     assert(0 && "Not implemented for this platform!");
1455 }
1456
1457 int registerSpace::getInstFrameSize() {
1458     assert(0 && "Not implemented for this platform!");
1459     return 0;
1460 }
1461
1462 #endif