Optimize the x86/x86_64 stack alignment sequence.
[dyninst.git] / dyninstAPI / src / registerSpace.h
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.h,v 1.18 2008/06/19 19:53:37 legendre Exp $
33
34 #ifndef REGISTER_SPACE_H
35 #define REGISTER_SPACE_H
36
37 #include <stdio.h>
38 #include <string>
39 #include <map>
40 #include <set>
41 #include "common/h/Vector.h"
42 #include "common/h/Dictionary.h"
43 #include "common/h/Types.h"
44 #include "inst.h" // callWhen...
45
46 #if defined(cap_liveness)
47 #include "bitArray.h"
48 #endif
49
50 class codeGen;
51 class instPoint;
52 class process;
53 class AddressSpace;
54 class image_basicBlock;
55
56 // A class to retain information about where the original register can be found. It can be in one of the following states: 
57 // 1) Unsaved, and available via the register itself;
58 // 2) Saved in a frame, e.g., a base tramp;
59 // 3) Pushed on the stack at a relative offset from the current stack pointer.
60 // 4) TODO: we could subclass this and make "get me the current value" a member function; not sure it's really worth it for the minimal amount of memory multiple types will use.
61
62 // We also need a better way of tracking what state a register is in. Here's some possibilities, not at all mutually independent:
63
64 // Live at the start of instrumentation, or dead;
65 // Used during the generation of a subexpression
66 // Currently reserved by another AST, but we could recalculate if necessary
67 // At a function call node, is it carrying a value?
68
69 // Terminology:
70 // "Live" : contains a value outside of instrumentation, and so must be saved before use
71 // "Used" : used by instrumentation code. 
72
73 class RealRegister {
74    //This is currently only used on x86_32 to represent the 
75    // virtual/real register difference.  'Register' still refers
76    // to virtual registers on this platform.  Contained in a struct
77    // so that no one can accidently cast a Register into a RealRegister
78    friend class registerSpace;
79    signed int r;
80  public:
81    RealRegister() { r = 0; }
82    explicit RealRegister(int reg) { r = reg; }
83    int reg() const { return r; }
84 };
85
86 #if defined(arch_x86_64)
87 #include "inst-x86.h"
88 #endif
89
90 class registerSlot {
91  public:
92    int alloc_num; //MATT TODO: Remove
93     const Register number;    // what register is it, using our Register enum
94     const std::string name;
95
96     typedef enum { deadAlways, deadABI, liveAlways } initialLiveness_t;
97     const initialLiveness_t initialState;
98
99     // Are we off limits for allocation in this particular instance?
100     const bool offLimits; 
101
102     typedef enum { invalid, GPR, FPR, SPR, realReg} regType_t;
103     const regType_t type; 
104
105     ////////// Code generation
106
107     int refCount;       // == 0 if free
108
109     typedef enum { live, spilled, dead } livenessState_t;
110     livenessState_t liveState;
111
112     bool keptValue;     // Are we keeping this (as long as we can) to save
113     // the pre-calculated value? Note: refCount can be 0 and
114     // this still set.
115
116     bool beenUsed;      // Has this register been used by generated code?
117
118     // New version of "if we were saved, then where?" It's a pair - true/false,
119     // then offset from the "zeroed" stack pointer. 
120     typedef enum { unspilled, framePointer } spillReference_t;
121     spillReference_t spilledState;
122     int saveOffset; // Offset where this register can be
123                     // retrieved.
124     // AMD-64: this is the number of words
125     // POWER: this is the number of bytes
126     // I know it's inconsistent, but it's easier this way since POWER
127     // has some funky math.
128
129     //////// Member functions
130
131     unsigned encoding() const;
132
133     void cleanSlot();
134
135     void markUsed(bool incRefCount) {
136         assert(offLimits == false);
137         assert(refCount == 0);
138         assert(liveState != live);
139         
140         if (incRefCount) 
141             refCount = 1;
142         beenUsed = true;
143     }
144     
145     // Default is just fine
146     // registerSlot(const registerSlot &r)
147
148     void debugPrint(const char *str = NULL);
149
150     // Don't want to use this...
151     registerSlot() :
152        alloc_num(0),
153         number(REG_NULL),
154         name("DEFAULT REGISTER"),
155         initialState(deadAlways),
156         offLimits(true),
157         type(invalid)
158         {};
159
160     registerSlot(Register num,
161                  std::string name_,
162                  bool offLimits_,
163                  initialLiveness_t initial,
164                  regType_t type_) : 
165        alloc_num(0),
166         number(num),
167         name(name_),
168         initialState(initial),
169         offLimits(offLimits_),
170         type(type_),
171         refCount(0),
172         liveState(live),
173         keptValue(false),
174         beenUsed(false),
175         spilledState(unspilled),
176         saveOffset(-1) {}
177
178 };
179
180 class instPoint;
181
182 typedef struct {
183    bool is_allocatable;
184    bool been_used;
185    int last_used;
186    registerSlot *contains;
187 } RealRegsState;
188
189
190 class regState_t {
191  public:
192    regState_t();
193    int pc_rel_offset;
194    int timeline;
195    int stack_height;
196    std::vector<RealRegsState> registerStates;
197 };
198
199 class registerSpace {
200    friend class baseTrampInstance;
201  private:
202     // A global mapping of register names to slots
203     static registerSpace *globalRegSpace_;
204     static registerSpace *globalRegSpace64_;
205
206     static void createRegSpaceInt(pdvector<registerSlot *> &regs,
207                                   registerSpace *regSpace);
208
209  public:
210     // Pre-set unknown register state:
211     // Everything is live...
212     static registerSpace *conservativeRegSpace(AddressSpace *proc);
213     // Everything is dead...
214     static registerSpace *optimisticRegSpace(AddressSpace *proc);
215     // IRPC-specific - everything live for now
216     static registerSpace *irpcRegSpace(AddressSpace *proc);
217     // Aaand instPoint-specific
218     static registerSpace *actualRegSpace(instPoint *iP, callWhen location);
219     // DO NOT DELETE THESE. 
220     static registerSpace *savedRegSpace(AddressSpace *proc);
221
222     static registerSpace *getRegisterSpace(AddressSpace *proc);
223     static registerSpace *getRegisterSpace(unsigned addr_width);
224     
225     registerSpace();
226     
227     static void createRegisterSpace(pdvector<registerSlot *> &registers);
228     static void createRegisterSpace64(pdvector<registerSlot *> &registers);
229     
230     ~registerSpace();
231
232     // IA-64... it overrides the register space with particular register
233     // numbers based on its rotating window mechanism.
234     // Note: this screws with the default registerSpace, and so 
235     // _really_ needs to be used continually or not at all.
236     static void overwriteRegisterSpace(unsigned firstReg, unsigned lastReg);
237     static void overwriteRegisterSpace64(unsigned firstReg, unsigned lastReg);
238
239     // Read the value in register souce from wherever we've stored it in
240     // memory (including the register itself), and stick it in actual register
241     // destination. So the source is the label, and destination is an actual.
242     // Size is a legacy parameter for places where we don't have register information
243     // (SPARC/IA-64)
244     bool readProgramRegister(codeGen &gen, Register source, 
245                              Register destination,
246                              unsigned size);
247
248     // And the reverse
249     bool writeProgramRegister(codeGen &gen, Register destination, 
250                               Register source,
251                               unsigned size);
252
253
254     Register allocateRegister(codeGen &gen, bool noCost);
255     bool allocateSpecificRegister(codeGen &gen, Register r, bool noCost = true);
256
257
258     // Like allocate, but don't keep it around; if someone else tries to
259     // allocate they might get this one. 
260     Register getScratchRegister(codeGen &gen, bool noCost = true); 
261     // Like the above, but excluding a set of registers (that we don't want
262     // to touch)
263     Register getScratchRegister(codeGen &gen, pdvector<Register> &excluded, bool noCost = true);
264
265
266     bool trySpecificRegister(codeGen &gen, Register reg, bool noCost = true);
267
268     bool saveAllRegisters(codeGen &gen, bool noCost);
269     bool restoreAllRegisters(codeGen &gen, bool noCost);
270
271     // For now, we save registers elsewhere and mark them here. 
272     bool markSavedRegister(Register num, int offsetFromFP);
273     bool markSavedRegister(RealRegister num, int offsetFromFP);
274
275     // 
276     bool markKeptRegister(Register num);
277
278     // Things that will be modified implicitly by anything else we
279     // generate - condition registers, etc.
280     bool checkVolatileRegisters(codeGen &gen, registerSlot::livenessState_t);
281     bool saveVolatileRegisters(codeGen &gen);
282     bool restoreVolatileRegisters(codeGen &gen);
283
284     // Free the specified register (decrement its refCount)
285     void freeRegister(Register k);
286     // Free the register even if its refCount is greater that 1
287     void forceFreeRegister(Register k);
288     // And mark a register as not being kept any more
289     void unKeepRegister(Register k);
290
291
292     // Mark all registers as unallocated, but keep live/dead info
293     void cleanSpace();
294     
295     // Check to see if the register is free
296     // DO NOT USE THIS!!!! to tell if you can use a register as
297     // a scratch register; do that with trySpecificRegister
298     // or allocateSpecificRegister. This is _ONLY_ to determine
299     // if a register should be saved (e.g., over a call).
300     bool isFreeRegister(Register k);
301     
302     // Checks to see if register starts live
303     bool isRegStartsLive(Register reg);
304     int fillDeadRegs(Register * deadRegs, int num);
305     
306     // Bump up the reference count. Occasionally, we underestimate it
307     // and call this routine to correct this.
308     void incRefCount(Register k);
309     
310     // Reset when the regSpace is reset - marked offlimits for 
311     // allocation.
312     bool markReadOnly(Register k);
313     bool readOnlyRegister(Register k);
314     // Make sure that no registers remain allocated, except "to_exclude"
315     // Used for assertion checking.
316     void checkLeaks(Register to_exclude);
317     
318     int getAddressWidth() { return addr_width; }
319     void debugPrint();
320     void printAllocedRegisters();
321
322     int numGPRs() const { return GPRs_.size(); }
323     int numFPRs() const { return FPRs_.size(); }
324     int numSPRs() const { return SPRs_.size(); }
325     int numRegisters() const { return registers_.size(); }
326
327     pdvector <registerSlot *> &GPRs() { return GPRs_; }
328     pdvector <registerSlot *> &FPRs() { return FPRs_; }
329     pdvector <registerSlot *> &SPRs() { return SPRs_; }
330
331     pdvector <registerSlot *> &realRegs();
332
333     pdvector <registerSlot *> &trampRegs(); //realRegs() on x86-32, GPRs on all others
334
335     registerSlot *operator[](Register);
336
337     // For platforms with "save all" semantics...
338     bool anyLiveGPRsAtEntry() const;
339     bool anyLiveFPRsAtEntry() const;
340     bool anyLiveSPRsAtEntry() const;
341
342     // And for the bitarrays we use to track these
343     static bitArray getBitArray();
344
345     /**
346      * The following set of 'public' and 'private' methods and data deal with
347      * virtual registers, currently used only on x86.  The above 'Register' class
348      * allocates and uses virtual registers, these methods provide mappings from 
349      * virtual registers to real registers.
350      **/
351  public:
352     //Put VReg into RReg
353     RealRegister loadVirtual(registerSlot *virt_r, codeGen &gen); 
354     RealRegister loadVirtual(Register virt_r, codeGen &gen);
355
356     //Put VReg into specific real register
357     void loadVirtualToSpecific(registerSlot *virt_r, RealRegister real_r, codeGen &gen);
358     void loadVirtualToSpecific(Register virt_r, RealRegister real_r, codeGen &gen);
359
360     //Spill away any virtual register in a real so that the real
361     // can be used freely.  Careful with this, no guarentee it won't
362     // be reallocated in the next step.
363     void makeRegisterAvail(RealRegister r, codeGen &gen);
364
365     //Tell the tracker that we've manually put some virtual into a real
366     void noteVirtualInReal(Register v_r, RealRegister r_r);
367     void noteVirtualInReal(registerSlot *v_r, RealRegister r_r);
368
369     //Like loadVirtual, but don't load orig value first
370     RealRegister loadVirtualForWrite(Register virt_r, codeGen &gen);
371     RealRegister loadVirtualForWrite(registerSlot *virt_r, codeGen &gen);
372
373     void markVirtualDead(Register num);
374     bool spilledAnything();
375
376     Register pc_rel_reg;
377     int pc_rel_use_count;
378     int& pc_rel_offset();
379     void incStack(int val);
380     int getInstFrameSize();
381     void setInstFrameSize(int val);
382     int getStackHeight();
383     void setStackHeight(int val);
384
385     void unifyTopRegStates(codeGen &gen);
386     void pushNewRegState();
387
388  private:
389     int instFrameSize_;  // How much stack space we allocate for
390                          // instrumentation before a frame is set up.
391
392     std::vector<regState_t *> regStateStack;
393     int cur_register_state;
394
395     std::vector<RealRegsState>& regState();
396     int& timeline();
397
398     std::set<registerSlot *> regs_been_spilled;
399
400     void initRealRegSpace();
401
402     //High-level functions that track data structures and call code gen
403     RealRegister findReal(registerSlot *virt_r, bool &already_setup);
404     void spillReal(RealRegister r, codeGen &gen);
405     void loadReal(RealRegister r, registerSlot *v_r, codeGen &gen);
406     void freeReal(RealRegister r);
407
408     //low-level functions for code gen
409     void spillToVReg(RealRegister reg, registerSlot *v_reg, codeGen &gen);
410     void movVRegToReal(registerSlot *v_reg, RealRegister r, codeGen &gen); 
411     void movRegToReg(RealRegister dest, RealRegister src, codeGen &gen);
412
413     unsigned savedFlagSize;
414
415  private:
416
417     registerSpace(const registerSpace &);
418     
419     registerSlot &getRegisterSlot(Register reg);
420
421     registerSlot *findRegister(Register reg); 
422     registerSlot *findRegister(RealRegister reg);
423
424     bool spillRegister(Register reg, codeGen &gen, bool noCost);
425     bool stealRegister(Register reg, codeGen &gen, bool noCost);
426
427     bool restoreRegister(Register reg, codeGen &gen, bool noCost); 
428     bool popRegister(Register reg, codeGen &gen, bool noCost);
429
430     bool markSavedRegister(registerSlot *num, int offsetFromFP);
431     
432     int currStackPointer; 
433
434     typedef dictionary_hash_iter<Register, registerSlot *> regDictIter;
435     dictionary_hash<Register, registerSlot *> registers_;
436
437     // And convenience vectors
438     pdvector<registerSlot *> GPRs_;
439     pdvector<registerSlot *> FPRs_;
440     pdvector<registerSlot *> SPRs_;
441
442     // Used on platforms that have "virtual" registers to provide a mapping
443     // for real (e.g., architectural) registers
444     pdvector<registerSlot *> realRegisters_;
445
446     static void initialize();
447     static void initialize32();
448     static void initialize64();
449
450
451     registerSpace &operator=(const registerSpace &src);
452
453     typedef enum {arbitrary, ABI_boundary, allSaved} rs_location_t;
454
455     // Specialize liveness as represented by a bit array
456     void specializeSpace(rs_location_t state);
457
458 #if defined(cap_liveness)
459     void specializeSpace(const bitArray &);
460 #endif
461
462     unsigned addr_width;
463
464  public:
465     static bool hasXMM;  // for Intel architectures, XMM registers
466     
467  public:
468 #if defined(arch_power)
469     typedef enum { r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12,
470                    r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23,
471                    r24, r25, r26, r27, r28, r29, r30, r31,
472                    fpr0, fpr1, fpr2, fpr3, fpr4, fpr5, fpr6, 
473                    fpr7, fpr8, fpr9, fpr10, fpr11, fpr12, fpr13,
474                    fpr14, fpr15, fpr16, fpr17, fpr18, fpr19, fpr20,
475                    fpr21, fpr22, fpr23, fpr24, fpr25, fpr26, fpr27,
476                    fpr28, fpr29, fpr30, fpr31,
477                    xer, lr, ctr, mq, cr, lastReg, ignored } powerRegisters_t;
478     static unsigned GPR(Register x) { return x; }
479     static unsigned FPR(Register x) { return x - fpr0; }
480     static unsigned SPR(Register x);
481     int framePointer() { return r1; }
482 #endif
483 #if defined(arch_x86) || defined(arch_x86_64)
484     int framePointer();
485 #endif
486     // Create a map of register names to register numbers
487     std::map<std::string, Register> registersByName;
488     // The reverse map can be handled by doing a rs[x]->name
489
490     Register getRegByName(const std::string name);
491     std::string getRegByNumber(Register num);
492     void getAllRegisterNames(std::vector<std::string> &ret);
493
494     // Bit vectors that represent the ABI behavior at call points
495     // and exits. 
496
497 #if defined(cap_liveness)
498
499     const bitArray &getCallReadRegisters() const;
500     const bitArray &getCallWrittenRegisters() const;
501     const bitArray &getReturnReadRegisters() const;
502     // No such thing as return written...
503
504     // Syscall!
505     const bitArray &getSyscallReadRegisters() const;
506     const bitArray &getSyscallWrittenRegisters() const;
507
508     const bitArray &getAllRegs() const;
509  private:
510     static bitArray callRead_;
511     static bitArray callRead64_;
512
513     static bitArray callWritten_;
514     static bitArray callWritten64_;
515
516     static bitArray returnRead_;
517     static bitArray returnRead64_;
518
519     static bitArray syscallRead_;
520     static bitArray syscallRead64_;
521
522     static bitArray syscallWritten_;
523     static bitArray syscallWritten64_;
524
525     static bitArray allRegs_;
526     static bitArray allRegs64_;
527
528 #endif
529
530
531 };
532
533 #endif