Make edge type information available to upper layers, replacing
[dyninst.git] / dyninstAPI / src / function.h
1 /*
2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41  
42 // $Id: function.h,v 1.26 2006/02/27 23:35:09 nater Exp $
43
44 #ifndef FUNCTION_H
45 #define FUNCTION_H
46
47 #include "common/h/String.h"
48 #include "common/h/Vector.h"
49 #include "common/h/Types.h"
50 #include "common/h/Pair.h"
51 #include "codeRange.h"
52 #include "arch.h" // instruction
53 #include "util.h"
54
55 #if !defined(BPATCH_LIBRARY)
56 #include "paradynd/src/resource.h"
57 #endif
58
59 #include "image-func.h"
60
61 class process;
62 class mapped_module;
63 class mapped_object;
64
65 class BPatch_flowGraph;
66 class BPatch_loopTreeNode;
67 class BPatch_basicBlock;
68 class BPatch_basicBlockLoop;
69
70 class instPointInstance;
71
72 #include "dyninstAPI/h/BPatch_Set.h"
73
74 class instPoint;
75
76 class Frame;
77
78 class functionReplacement;
79
80 class int_function;
81 class int_basicBlock;
82 class bitArray;
83
84 class funcMod;
85
86 // A specific instance (relocated version) of a basic block
87 // It's really a semi-smart struct...
88 class bblInstance : public codeRange {
89     friend class int_basicBlock;
90     friend class int_function;
91
92     // "We'll set things up later" constructor. Private because only int_basicBlock
93     // should be playing in here
94     bblInstance(int_basicBlock *parent, int version);
95  public:
96     bblInstance(Address start, Address last, Address end, int_basicBlock *parent, int version);
97     bblInstance(const bblInstance *parent, int_basicBlock *block);
98     ~bblInstance();
99
100     Address firstInsnAddr() const { return firstInsnAddr_; }
101     Address lastInsnAddr() const { return lastInsnAddr_; }
102     // Just to be obvious -- this is the end addr of the block
103     Address endAddr() const { return blockEndAddr_; }
104     Address getSize() const { return blockEndAddr_ - firstInsnAddr_; }
105
106     // And equivalence in addresses...
107     Address equivAddr(bblInstance *otherBBL, Address otherAddr) const;
108
109     // As a note: do _NOT_ create an address-based comparison of this
110     // class unless you just need some sort of ordering. We may create these
111     // blocks in some random place; depending on address is just plain dumb.
112
113     Address get_address_cr() const { return firstInsnAddr(); }
114     unsigned get_size_cr() const { return getSize(); }
115     void *getPtrToInstruction(Address addr) const;
116     
117     process *proc() const;
118     int_function *func() const;
119     int_basicBlock *block() const;
120     int version() const;
121
122 #if defined(cap_relocation)
123     // Get the most space necessary to relocate this basic block,
124     // using worst-case analysis.
125     bool relocationSetup(bblInstance *orig, pdvector<funcMod *> &mods);
126     unsigned sizeRequired();
127     // Pin a block to a particular address; in theory, we can only
128     // do these for blocks that can be entered via jumps, but for now
129     // we do it all the time.
130     void setStartAddr(Address addr);
131
132     // And generate a moved copy into ze basic block
133     bool generate();
134     // And write the block into the addr space
135     bool install();
136     // Check for safety...
137     bool check(pdvector<Address> &checkPCs);
138     // Link things up
139     bool link(pdvector<codeRange *> &overwrittenObjs);
140 #endif
141
142  private:
143 #if defined(cap_relocation)
144     class reloc_info_t {
145     public:
146        dictionary_hash<Address, Address> changedAddrs_;
147        pdvector<instruction *> insns_;
148        unsigned maxSize_;
149        bblInstance *origInstance_;
150        pdvector<funcMod *> appliedMods_;
151        codeGen generatedBlock_; // Kept so we can quickly iterate over the block
152        // in the future.
153        functionReplacement *jumpToBlock_; // Kept here between generate->link
154
155        reloc_info_t();
156        reloc_info_t(reloc_info_t *parent, int_basicBlock *block);
157        ~reloc_info_t();
158     };
159
160     //Setter functions for relocation information
161     dictionary_hash<Address, Address> &changedAddrs();
162     pdvector<instruction *> &insns();
163     unsigned &maxSize();
164     bblInstance *&origInstance();
165     pdvector<funcMod *> &appliedMods();
166     codeGen &generatedBlock();
167     functionReplacement *&jumpToBlock();
168
169     //Getter functions for relocation information
170     dictionary_hash<Address, Address> &getChangedAddrs() const;
171     pdvector<instruction *> &getInsns() const;
172     unsigned getMaxSize() const;
173     bblInstance *getOrigInstance() const;
174     pdvector<funcMod *> &getAppliedMods() const;
175     codeGen &getGeneratedBlock() const;
176     functionReplacement *getJumpToBlock() const;
177
178     reloc_info_t *reloc_info;
179 #endif
180
181     Address firstInsnAddr_;
182     Address lastInsnAddr_;
183     Address blockEndAddr_;
184     int_basicBlock *block_;
185     int version_;
186 };
187
188 class int_basicBlock {
189     friend class int_function;
190  public:
191     int_basicBlock(const image_basicBlock *ib, Address baseAddr, int_function *func, int id);
192     int_basicBlock(const int_basicBlock *parent, int_function *func, int id);
193     ~int_basicBlock();
194
195         // just because a block is an entry block doesn't mean it is
196         // an entry block that this block's function cares about
197     bool isEntryBlock() const;
198     bool isExitBlock() const { return ib_->isExitBlock(); }
199
200         // int_basicBlocks are not shared, but their underlying blocks
201         // may be
202     bool hasSharedBase() const { return ib_->isShared(); }
203
204     const image_basicBlock * llb() const { return ib_; }
205     
206     static int compare(int_basicBlock *&b1,
207                        int_basicBlock *&b2) {
208         // First instance: original bbl.
209         if (b1->instances_[0]->firstInsnAddr() < b2->instances_[0]->firstInsnAddr())
210             return -1;
211         if (b2->instances_[0]->firstInsnAddr() < b1->instances_[0]->firstInsnAddr())
212             return 1;
213         assert(b1 == b2);
214         return 0;
215     }
216
217     const pdvector<bblInstance *> &instances() const;
218     bblInstance *origInstance() const;
219     bblInstance *instVer(unsigned index) const;
220     void removeVersion(unsigned index);
221
222     void debugPrint();
223
224     void getSources(pdvector<int_basicBlock *> &ins) const;
225     void getTargets(pdvector<int_basicBlock *> &outs) const;
226     EdgeTypeEnum getEdgeType(int_basicBlock * target) const;
227
228     int_basicBlock *getFallthrough() const;
229
230     int id() const { return id_; }
231
232     // A block will need relocation (when instrumenting) if
233     // its underlying image_basicBlock is shared (this is independant
234     // of relocation requirements dependant on size available)
235     bool needsRelocation() const;
236
237     int_function *func() const { return func_; }
238     process *proc() const;
239
240 #if defined(arch_ia64)
241     // Data flow... for register analysis. Right now just used for 
242     // IA64 alloc calculations
243     // We need a set...
244     void setDataFlowIn(BPatch_Set<int_basicBlock *> *in);
245     void setDataFlowOut(BPatch_Set<int_basicBlock *> *out);
246     void setDataFlowGen(int_basicBlock *gen);
247     void setDataFlowKill(int_basicBlock *kill);
248
249     BPatch_Set<int_basicBlock *> *getDataFlowOut();
250     BPatch_Set<int_basicBlock *> *getDataFlowIn();
251     int_basicBlock *getDataFlowGen();
252     int_basicBlock *getDataFlowKill();    
253 #endif
254
255     // Liveness functions for AIX && AMD64
256 #if defined(os_aix) || defined(arch_x86_64)
257     
258     /** Initializes the gen/kill sets for register liveness analysis */
259     bool initRegisterGenKill();
260    
261     /** Used in the fixed point iteration part of liveness */
262     bool updateRegisterInOut(bool isFP);
263    
264     /** Returns in set for GPR */
265     bitArray * getInSet();
266    
267     /** Returns in set for FPR */
268     bitArray * getInFPSet();
269    
270     /** Puts the live registers from bitArrays to integers stored by inst point */
271     int liveRegistersIntoSet(int *& liveReg, int *& liveFPReg,
272                              unsigned long address);
273
274     /** Puts the live SP registers from bitArrays to integers stored by inst point */
275     int liveSPRegistersIntoSet(int *& liveSPReg,
276                                unsigned long address);
277 #endif     
278
279     void setHighLevelBlock(void *newb);
280     void *getHighLevelBlock() const;
281
282  private:
283     void *highlevel_block; //Should point to a BPatch_basicBlock, if they've
284                            //been created.
285 #if defined(arch_ia64)
286     BPatch_Set<int_basicBlock *> *dataFlowIn;
287     BPatch_Set<int_basicBlock *> *dataFlowOut;
288     int_basicBlock *dataFlowGen;
289     int_basicBlock *dataFlowKill;
290 #endif
291
292 #if defined(os_aix) || defined(arch_x86_64)
293    /* Liveness analysis variables */
294    /** gen registers */
295    bitArray * gen;
296    bitArray * genFP;
297    
298    /** kill registers */
299    bitArray * kill;
300    bitArray * killFP;
301    
302    /** in registers */
303    bitArray * in;
304    bitArray * inFP;
305    
306    /** out registers */
307    bitArray * out;
308    bitArray * outFP;
309 #endif
310
311
312     int_function *func_;
313     const image_basicBlock *ib_;
314
315     int id_;
316
317     // A single "logical" basic block may correspond to multiple
318     // physical areas of code. In particular, we may relocate the
319     // block (either replaced or duplicated).
320     pdvector<bblInstance *> instances_;
321 };
322
323 class int_function {
324   friend class int_basicBlock;
325  public:
326    static pdstring emptyString;
327
328    // Almost everything gets filled in later.
329    int_function(image_func *f,
330                 Address baseAddr,
331                 mapped_module *mod);
332
333    int_function(const int_function *parent,
334                 mapped_module *child_mod);
335
336    ~int_function();
337
338    ////////////////////////////////////////////////
339    // Passthrough functions.
340    ////////////////////////////////////////////////
341    // To minimize wasted memory (since there will be many copies of
342    // this function) we make most methods passthroughs to the original
343    // parsed version.
344
345    const pdstring &symTabName() const;
346    const pdstring &prettyName() const { return ifunc_->prettyName(); };
347    const pdstring &typedName() const { return ifunc_->typedName(); };
348    const pdvector<pdstring> &symTabNameVector() const { return ifunc_->symTabNameVector(); }
349    const pdvector<pdstring> &prettyNameVector() const { return ifunc_->prettyNameVector(); }
350    const pdvector<pdstring> &typedNameVector() const { return ifunc_->typedNameVector(); }
351
352    // Debuggering functions
353    void debugPrint() const;
354
355    // And add...
356    // Don't make the pdstring a reference; we want a copy.
357    void addSymTabName(const pdstring name, bool isPrimary = false);
358    void addPrettyName(const pdstring name, bool isPrimary = false);
359
360    // May change when we relocate...
361    Address getAddress() const {return addr_;}
362    // Don't use this...
363    unsigned getSize_NP();
364
365
366    // Not defined here so we don't have to play header file magic
367    // Not const; we can add names via the Dyninst layer
368    image_func *ifunc();
369    mapped_module *mod() const;
370    mapped_object *obj() const;
371    process *proc() const;
372
373    // Necessary for BPatch_set which needs a structure with a ()
374    // operator. Odd.
375    struct cmpAddr {
376      int operator() (const int_function *f1, const int_function *f2) const {
377        if (f1->getAddress() > f2->getAddress())
378          return 1;
379        else if (f1->getAddress() < f2->getAddress())
380          return -1;
381        else
382          return 0;
383      }
384    };
385
386    // extra debuggering info....
387    ostream & operator<<(ostream &s) const;
388    friend ostream &operator<<(ostream &os, int_function &f);
389
390    ////////////////////////////////////////////////
391    // Process-dependent (inter-module) parsing
392    ////////////////////////////////////////////////
393    void checkCallPoints();
394
395    ////////////////////////////////////////////////
396    // CFG and other function body methods
397    ////////////////////////////////////////////////
398
399    const pdvector< int_basicBlock* > &blocks();
400
401    // Perform a lookup (either linear or log(n)).
402    int_basicBlock *findBlockByAddr(Address addr);
403    int_basicBlock *findBlockByOffset(Address offset) { return findBlockByAddr(offset + getAddress()); }
404    bblInstance *findBlockInstanceByAddr(Address addr);
405
406
407    bool hasNoStackFrame() const {return ifunc_->hasNoStackFrame();}
408    bool makesNoCalls() const {return ifunc_->makesNoCalls();}
409    bool savesFramePointer() const {return ifunc_->savesFramePointer();}
410
411    //BPatch_flowGraph * getCFG();
412    //BPatch_loopTreeNode * getLoopTree();
413
414    ////////////////////////////////////////////////
415    // Instpoints!
416    ////////////////////////////////////////////////
417
418    void addArbitraryPoint(instPoint *insp);
419
420    const pdvector<instPoint*> &funcEntries();
421    // Note: the vector is constant, the instPoints aren't.
422    const pdvector<instPoint*> &funcExits();
423    const pdvector<instPoint*> &funcCalls();
424    const pdvector<instPoint*> &funcArbitraryPoints();
425    
426    bool isInstrumentable() const { return ifunc_->isInstrumentable(); }
427
428
429 #if defined(arch_x86) || defined(arch_x86_64)
430    //Replaces the function with a 'return val' statement.
431    // currently needed only on Linux/x86
432    // Defined in inst-x86.C
433    bool setReturnValue(int val);
434
435    //bool hasJumpToFirstFiveBytes() { return ifunc_->hasJumpToFirstFiveBytes(); }
436    // ----------------------------------------------------------------------
437 #endif
438
439    ////////////////////////////////////////////////
440    // Relocation
441    ////////////////////////////////////////////////
442
443    bool canBeRelocated() const { return ifunc_->canBeRelocated(); }
444    bool needsRelocation() const { return ifunc_->needsRelocation(); }
445    int version() const { return version_; }
446    void getSharingFuncs(int_basicBlock *b,
447                         pdvector<int_function *> &funcs);
448
449    ////////////////////////////////////////////////
450    // Misc
451    ////////////////////////////////////////////////
452
453    bool containsSharedBlocks() const { return ifunc_->containsSharedBlocks(); }
454
455    unsigned getNumDynamicCalls();
456
457 #ifndef BPATCH_LIBRARY
458    // Fill in <callees> vector with pointers to all other pd functions
459    //  statically determined to be called from any call sites in 
460    //  this function.
461    // Returns false if unable to fill in that information....
462    bool getStaticCallees(pdvector <int_function *> &callees);
463 #endif
464
465     // Fill the <callers> vector with pointers to the statically-determined
466     // list of functions that call this function.
467     void getStaticCallers(pdvector <int_function *> &callers);
468
469    codeRange *copy() const;
470     
471 #if defined(arch_alpha)
472    int frame_size() const { return ifunc_->frame_size; };
473
474 #endif
475
476 #if defined(sparc_sun_solaris2_4)
477    bool is_o7_live(){ return ifunc_->is_o7_live(); }
478 #endif
479
480    void updateForFork(process *childProcess, const process *parentProcess);
481
482 #ifndef BPATCH_LIBRARY
483    void SetFuncResource(resource *r) {
484       assert(r != NULL); 
485       funcResource = r;
486    }
487
488    pdstring ResourceFullName() {
489       assert(funcResource); 
490       return funcResource->full_name();
491    }
492
493    bool FuncResourceSet() {
494       return (funcResource != NULL);
495    }
496 #endif
497
498 #if defined(arch_ia64)
499    // We need to know where all the alloc instructions in the
500    // function are to do a reasonable job of register allocation
501    // in the base tramp.  
502    pdvector< Address > allocs;
503    
504    // Since the IA-64 ABI does not define a frame pointer register,
505    // we use DWARF debug records (DW_AT_frame_base entries) to 
506    // construct an AST which calculates the frame pointer.
507    AstNode * framePointerCalculator;
508    
509    // Place to store the results of doFloatingPointStaticAnalysis().
510    // This way, if they are ever needed in a mini-tramp, emitFuncJump()
511    // for example, the expensive operation doesn't need to happen again.
512    bool * usedFPregs;
513 #endif
514
515 #if defined(cap_relocation)
516    // These are defined in reloc-func.C to keep large chunks of
517    // functionality separate!
518
519    // Deceptively simple... take a list of requested changes,
520    // and make a copy of the function somewhere out in space.
521    // Defaults to the first version of the function = 0
522    bool relocationGenerate(pdvector<funcMod *> &mods, 
523                            int version,
524                            pdvector<int_function *> &needReloc);
525    // The above gives us a set of basic blocks that have little
526    // code segments. Install them in the address space....
527    bool relocationInstall();
528    // Check whether we can overwrite...
529    bool relocationCheck(pdvector<Address> &checkPCs);
530    // And overwrite code with jumps to the relocated version
531    bool relocationLink(pdvector<codeRange *> &overwritten_objs);
532
533    // Cleanup code: remove (back to) the latest installed version...
534    bool relocationInvalidate();
535
536    // A top-level function; for each instPoint, see if we need to 
537    // relocate the function.
538    bool expandForInstrumentation();
539
540    pdvector<funcMod *> &enlargeMods() { return enlargeMods_; }
541
542 #endif
543
544  private:
545
546    ///////////////////// Basic func info
547    Address addr_; // Absolute address of the start of the function
548
549    image_func *ifunc_;
550    mapped_module *mod_; // This is really a dodge; translate a list of
551                         // image_funcs to int_funcs
552
553    ///////////////////// CFG and function body
554    pdvector< int_basicBlock* > blockList;
555
556    // Added to support translation between function-specific int_basicBlocks
557    // and potentially shared image_basicBlocks
558    dictionary_hash<int, int> blockIDmap;
559
560    //BPatch_flowGraph *flowGraph;
561
562    ///////////////////// Instpoints 
563
564    pdvector<instPoint*> entryPoints_;   /* place to instrument entry (often not addr) */
565    pdvector<instPoint*> exitPoints_;    /* return point(s). */
566    pdvector<instPoint*> callPoints_;    /* pointer to the calls */
567    pdvector<instPoint*> arbitraryPoints_;              /* pointer to the calls */
568
569 #if defined(cap_relocation)
570    // Status tracking variables
571    int generatedVersion_;
572    int installedVersion_;
573    int linkedVersion_;
574
575    // We want to keep around expansions for instrumentation
576    pdvector<funcMod *> enlargeMods_;
577
578    // The actual relocation workhorse (the public method is just a facade)
579    bool relocationGenerateInt(pdvector<funcMod *> &mods, 
580                               int version,
581                               pdvector<int_function *> &needReloc);
582 #endif
583
584    // Used to sync with instPoints
585    int version_;
586
587    codeRangeTree blocksByAddr_;
588    void addBBLInstance(bblInstance *instance);
589    void deleteBBLInstance(bblInstance *instance);
590
591 #ifndef BPATCH_LIBRARY
592    resource *funcResource;
593 #endif
594 };
595
596 // All-purpose; use for function relocation, actual function
597 // replacement, etc.
598 class functionReplacement : public codeRange {
599
600  public:
601     functionReplacement(int_basicBlock *sourceBlock,
602                         int_basicBlock *targetBlock,
603                         unsigned sourceVersion = 0,
604                         unsigned targetVersion = 0);
605     ~functionReplacement() {};
606
607     unsigned maxSizeRequired();
608
609     bool generateFuncRep(pdvector<int_function *> &needReloc);
610     bool installFuncRep();
611     bool checkFuncRep(pdvector<Address> &checkPCs);
612     bool linkFuncRep(pdvector<codeRange *> &overwrittenObjs);
613     void removeFuncRep();
614     
615     bool overwritesMultipleBlocks();
616
617     int_basicBlock *source();
618     int_basicBlock *target();
619     unsigned sourceVersion();
620     unsigned targetVersion();
621
622     Address get_address_cr() const;
623     unsigned get_size_cr() const;
624
625  private:
626     codeGen jumpToRelocated;
627     codeGen origInsns;
628
629     int_basicBlock *sourceBlock_;
630     int_basicBlock *targetBlock_;
631
632     // If no relocation, these will be zero.
633     unsigned sourceVersion_;
634     unsigned targetVersion_;
635
636     // We may need more room than there is in a block;
637     // this makes things "interesting".
638     bool overwritesMultipleBlocks_; 
639 };
640
641
642
643 #endif /* FUNCTION_H */