Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / image-func.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: image-func.h,v 1.37 2008/09/03 06:08:44 jaw Exp $
33
34 #ifndef IMAGE_FUNC_H
35 #define IMAGE_FUNC_H
36
37 #include <string>
38 #include "common/h/Vector.h"
39 #include "common/h/Types.h"
40 #include "common/h/Pair.h"
41 #include "codeRange.h"
42 #include "arch.h" // instruction
43 #include "parRegion.h"
44 #include "dyninstAPI/h/BPatch_Set.h"
45 #include "common/h/Dictionary.h"
46 #include "symtabAPI/h/Symbol.h"
47 #include "dyninstAPI/src/bitArray.h"
48 #include "InstructionCache.h"
49 #include "InstructionAdapter.h"
50 #include <set>
51
52 #include "symtabAPI/h/Function.h"
53
54 using namespace Dyninst;
55 using namespace Dyninst::SymtabAPI;
56 using namespace std;
57
58 class pdmodule;
59 class InstrucIter;
60
61 // Slight modifications (and specialization) of BPatch_*
62 class image_basicBlock;
63 class image_instPoint;
64
65 // CFG edges are typed
66 class image_edge;
67    
68
69 class InstructionAdapter;
70 #if !defined(ESSENTIAL_PARSING_ENUMS)
71 #define ESSENTIAL_PARSING_ENUMS
72
73    
74 enum EdgeTypeEnum {
75    ET_CALL,
76    ET_COND_TAKEN,
77    ET_COND_NOT_TAKEN,
78    ET_INDIR,
79    ET_DIRECT,
80    ET_FALLTHROUGH,
81    ET_CATCH,
82    ET_FUNLINK,  // connect block ended by call instruction with next block
83                // (see BIT)
84    ET_NOEDGE
85 };
86
87 // Function return status. We initially assume that all functions
88 // do not return. Unresolvable control flow edges change the status
89 // to UNKNOWN, and return instructions (or the equivalent) change
90 // status to RETURN
91 enum FuncReturnStatus {
92     RS_UNSET,       // convenience for parsing
93     RS_NORETURN,
94     RS_UNKNOWN,
95     RS_RETURN
96 };
97
98
99 // There are three levels of function-level "instrumentability":
100 // 1) The function can be instrumented normally with no problems (normal case)
101 // 2) The function contains unresolved indirect branches; we have to assume
102 //    these can go anywhere in the function to be safe, so we must instrument
103 //    safely (e.g., with traps)
104 // 3) The function is flatly uninstrumentable and must not be touched.
105 enum InstrumentableLevel {
106     NORMAL,
107     HAS_BR_INDIR,
108     UNINSTRUMENTABLE
109 };
110 #endif //!defined(ESSENTIAL_PARSING_ENUMS)
111
112
113 // Indicates the source of this function, e.g. whether
114 // it was listed in a symbol table, discovered with
115 // recursive traversal, speculatively found in gap parsing, etc
116 enum FuncSource {
117     FS_SYMTAB,
118     FS_RT,
119     FS_GAP,
120     FS_ONDEMAND,
121     FS_GAPRT
122 };
123
124 class image_edge {
125     friend class image_basicBlock;
126  public:
127    image_edge(image_basicBlock *source, 
128               image_basicBlock *target, 
129               EdgeTypeEnum type) :
130       source_(source),
131       target_(target),
132       type_(type) {}
133
134    image_basicBlock * getSource() const { return source_; }
135    image_basicBlock * getTarget() const { return target_; }
136    EdgeTypeEnum getType() const { return type_; }
137
138    void breakEdge();
139
140    const char * getTypeString();
141
142  private:
143    image_basicBlock *source_;
144    image_basicBlock *target_;
145    EdgeTypeEnum type_;
146 };
147
148 class image_basicBlock : public codeRange {
149     friend class image_func;
150  public:
151
152     image_basicBlock(image_func *func, Address firstOffset);
153
154     Address firstInsnOffset() const { return firstInsnOffset_; }
155     Address lastInsnOffset() const { return lastInsnOffset_; }
156     // Just to be obvious -- this is the end addr of the block
157     Address endOffset() const { return blockEndOffset_; }
158     Address getSize() const { return blockEndOffset_ - firstInsnOffset_; }
159     
160     bool isEntryBlock(image_func * f) const;
161     bool isExitBlock() const { return isExitBlock_; }
162
163     // Reverse if isEntryBlock; if we're the entry for a function return it.
164     image_func *getEntryFunc() const;
165
166     bool isShared() const { return isShared_; }
167
168     struct compare {
169         bool operator()(image_basicBlock * const &b1,
170                         image_basicBlock * const &b2) const {
171             if(b1->firstInsnOffset() < b2->firstInsnOffset())
172                 return true;
173             if(b2->firstInsnOffset() < b1->firstInsnOffset())
174                 return false;
175
176             // XXX the remainder is debugging, and should be removed
177             if(b1 != b2)
178                 fprintf(stderr,"error: two blocks (%p,%p) at 0x%lx\n",
179                     b1,b2,b1->firstInsnOffset());
180
181             assert(b1 == b2);
182             return false;
183         }
184     };
185
186     typedef std::set<image_basicBlock *, image_basicBlock::compare> blockSet;
187
188     void debugPrint();
189
190     void getSources(pdvector<image_edge *> &ins) const;
191     void getTargets(pdvector<image_edge *> &outs) const;
192
193     Address get_address() const { return firstInsnOffset(); }
194     unsigned get_size() const { return getSize(); }
195     void *getPtrToInstruction(Address addr) const;
196
197     // splitting blocks
198     image_basicBlock * split(Address loc, image_func *succ_func);
199     void split(image_basicBlock * &newBlk);
200
201     bool addTarget(image_edge *edge);
202     bool addSource(image_edge *edge);
203
204     void removeTarget(image_edge *edge);
205     void removeSource(image_edge *edge);
206
207     int id() const { return blockNumber_; }
208
209     const set<image_func *> & getFuncs() const;
210
211     // convenience method: sometimes any function will do
212     image_func * getFirstFunc() const
213     {
214         if(!funcs_.empty())
215             return *funcs_.begin();
216         else
217             return NULL;
218     }
219
220     bool containedIn(image_func * f);
221
222     // add another owning function to this basic block
223     void addFunc(image_func *func);
224
225     bool containsRet() { return containsRet_; }
226
227     bool containsCall() { return containsCall_; }
228
229     image_instPoint * getCallInstPoint();
230     image_instPoint * getRetInstPoint();
231
232     bool canBeRelocated() const { return canBeRelocated_; }
233     bool needsRelocation() const { return needsRelocation_; }
234     void markAsNeedingRelocation() { needsRelocation_ = true; }
235
236 #if defined(cap_liveness)
237     const bitArray &getLivenessIn();
238     // This is copied from the union of all successor blocks
239     const bitArray getLivenessOut() const;
240 #endif
241
242 #if defined(cap_instruction_api)
243     void getInsnInstances(std::vector<std::pair<InstructionAPI::Instruction::Ptr, Offset> > &instances);
244 #endif
245
246    private:
247     // Try to shrink memory usage down.
248     void finalize();
249
250     Address firstInsnOffset_;
251     Address lastInsnOffset_;
252     Address blockEndOffset_;
253
254     bool isEntryBlock_;
255     bool isExitBlock_;
256     bool needsRelocation_;
257     bool isShared_;     // block shared by > 1 functions
258
259     int blockNumber_;
260
261     bool isStub_;       // used in parsing -- if true, has not been parsed
262     bool containsRet_; // both of these are tantamount to saying "ends with X"
263     bool containsCall_;
264     bool canBeRelocated_; // some blocks contain uninstrumentable constructs
265
266     pdvector<image_edge *> targets_;
267     pdvector<image_edge *> sources_;
268
269     set<image_func *> funcs_;
270
271 #if defined(cap_liveness)
272     /* Liveness analysis variables */
273     /** gen registers */
274     
275     bitArray use; // Registers used by instructions within the block
276     bitArray def; // Registers defined by instructions within the block
277     bitArray in;  // Summarized input liveness; we calculate output on the fly
278  public:
279     static InstructionCache cachedLivenessInfo;
280     
281  private:
282     void summarizeBlockLivenessInfo();
283     // Returns true if any information changed; false otherwise
284     bool updateBlockLivenessInfo();
285 #endif
286
287
288 };
289
290 // Handle creation of edges and insertion of source/target pointers
291 // in basic block objects
292 void addEdge(image_basicBlock *source, 
293              image_basicBlock *target, 
294              EdgeTypeEnum type);
295
296 void checkIfRelocatable (instruction insn, bool &canBeRelocated);
297
298 bool isRealCall(instruction insn, 
299                 Address addr, 
300                 image *owner, 
301                 bool &validTarget);
302
303 #include "ast.h"
304
305 class image_func_registers {
306  public:
307   std::set<Register> generalPurposeRegisters;
308   std::set<Register> floatingPointRegisters;
309   std::set<Register> specialPurposeRegisters;
310 };
311
312 // Parse-level function object. Knows about offsets, names, and suchlike; 
313 // does _not_ do function relocation.
314 class image_func : public codeRange,
315                    public AnnotatableSparse
316 {
317  public:
318    static std::string emptyString;
319
320    image_func() {}
321    // Almost everything gets filled in later.
322    image_func(const std::string &symbol, 
323               Address offset, 
324               const unsigned symTabSize, 
325               pdmodule *m,
326               image *i,
327           FuncSource src);
328   
329    image_func(Function *func, pdmodule *m, image *i, FuncSource src);
330
331    ~image_func();
332
333
334    ////////////////////////////////////////////////
335    // Basic output functions
336    ////////////////////////////////////////////////
337
338    Function* getSymtabFunction() const{
339       return  func_; 
340    }    
341
342    const string &symTabName() const { 
343        return func_->getFirstSymbol()->getName();
344    }
345    const string &prettyName() const {
346        return func_->getFirstSymbol()->getPrettyName();
347    }
348    const string &typedName() const {
349        return func_->getFirstSymbol()->getTypedName();
350    }
351
352    const vector<string> &symTabNameVector() const {
353        return func_->getAllMangledNames();
354    }
355    const vector<string> &prettyNameVector() const {
356        return func_->getAllPrettyNames();
357    }
358    const vector<string> &typedNameVector() const {
359        return func_->getAllTypedNames();
360    }
361    void copyNames(image_func *duplicate);
362
363    // Bool: returns true if the name is new (and therefore added)
364    bool addSymTabName(std::string name, bool isPrimary = false);
365    bool addPrettyName(std::string name, bool isPrimary = false);
366    bool addTypedName(std::string name, bool isPrimary = false);
367
368    Address getOffset() const {return func_->getFirstSymbol()->getOffset();}
369    Address getPtrOffset() const {return func_->getFirstSymbol()->getPtrOffset();}
370    Address getEndOffset(); // May trigger parsing
371    unsigned getSymTabSize() const { return func_->getFirstSymbol()->getSize(); }
372
373    // coderange needs a get_address...
374    Address get_address() const { return getOffset();}
375    unsigned get_size() const { return endOffset_ - getOffset(); }
376
377    void *getPtrToInstruction(Address addr) const;
378
379
380    // extra debuggering info....
381    ostream & operator<<(ostream &s) const;
382    friend ostream &operator<<(ostream &os, image_func &f);
383    pdmodule *pdmod() const { return mod_;}
384    image *img() const { return image_; }
385    void changeModule(pdmodule *mod);
386
387    ////////////////////////////////////////////////
388    // CFG and other function body methods
389    ////////////////////////////////////////////////
390
391    const set<image_basicBlock*, image_basicBlock::compare> &blocks();
392
393    bool hasNoStackFrame();
394    bool makesNoCalls();
395    bool savesFramePointer();
396    bool cleansOwnStack();
397
398    ////////////////////////////////////////////////
399    // Parsing support methods
400    ////////////////////////////////////////////////
401
402    void parseSharedBlocks(image_basicBlock * firstBlock,
403                 BPatch_Set< Address > &leaders,
404                 dictionary_hash< Address, image_basicBlock * > &leadersToBlock,
405                 Address & funcEnd);
406    void parseSharedBlocks(image_basicBlock * firstBlock);
407
408    // Helper function: create a new basic block and add to various data
409    // structures (if the new addr is valid)
410    bool addBasicBlock(Address newAddr,
411                       image_basicBlock *oldBlock,
412                       BPatch_Set<Address> &leaders,
413                       dictionary_hash<Address, image_basicBlock *> &leadersToBlock,
414                       EdgeTypeEnum edgeType,
415                       pdvector<Address> &worklist);
416
417    // Add a basic block to the blocklist when this is not the function
418    // being parsed. Helps maintain consistency across basic block split
419    // operations initiated by another function's parsing.
420    void addToBlocklist(image_basicBlock *newBlk);
421
422    // Can we determine whether this function returns?
423    FuncReturnStatus returnStatus() { return retStatus_; }
424
425    // Sort basic block list, instrumentation points, and finalize vector
426    // data structures to reduce memory
427    bool finalize();
428
429    // Check the targets of _call_ instrumentation points and link up
430    // dangling targets, if possible
431    void checkCallPoints();
432    void checkCallPoints(pdvector<image_instPoint *> &points);
433     
434    Address newCallPoint(Address adr, const instruction code, bool &err);
435
436    ////////////////////////////////////////////////
437    // Architecture-dependent parsing support
438    ////////////////////////////////////////////////
439
440     bool archIsUnparseable();
441     bool archAvoidParsing();
442     bool archNoRelocate();
443     void archSetFrameSize(int frameSize);
444     bool archGetMultipleJumpTargets( 
445              BPatch_Set< Address >& targets,
446              image_basicBlock *currBlk,
447              InstrucIter &ah,
448              pdvector< instruction >& allInstructions);
449     bool archProcExceptionBlock(Address &catchStart, Address a);
450 #if !defined(cap_instruction_api)    
451     bool archIsATailCall(InstrucIter &ah,
452              pdvector< instruction >& allInstructions);
453     bool archIsIndirectTailCall(InstrucIter &ah);
454     bool archIsRealCall(InstrucIter &ah, bool &validTarget, bool
455 &simulateJump);
456     bool archCheckEntry(InstrucIter &ah, image_func *func );
457     bool archIsIPRelativeBranch(InstrucIter& ah);
458 #endif    
459     void archInstructionProc(InstructionAdapter &ah);
460     /*void processJump(InstructionAdapter& ah,
461                 image_basicBlock* currBlk,
462                 Address& funcBegin,
463                 Address& funcEnd,
464                 pdvector<instruction>& allInstructions,
465                 BPatch_Set<Address>& leaders,
466                 pdvector<Address>& worklist,
467                 dictionary_hash<Address, image_basicBlock*>& leadersToBlock,
468     dictionary_hash<Address, std::string> *pltFuncs);*/
469
470    
471    ////////////////////////////////////////////////
472    // Instpoints!
473    ////////////////////////////////////////////////
474
475    const pdvector<image_instPoint*> &funcEntries();
476    const pdvector<image_instPoint*> &funcExits();
477    const pdvector<image_instPoint*> &funcCalls();
478   
479    // Initiate parsing on this function
480    bool parse();
481  
482    // Do most of the parsing work. Calls architecture-dependent routines
483    // defined in image-<arch>.C
484    bool buildCFG(pdvector<image_basicBlock *> &funcEntry, Address funcBegin);
485
486    bool isTrapFunc() const {return isTrap;}
487
488    const pdvector<image_parRegion*> &parRegions();
489
490    bool isInstrumentable() const { return instLevel_ != UNINSTRUMENTABLE; }
491    InstrumentableLevel instLevel() const { return instLevel_; }
492
493    void addCallInstPoint(image_instPoint *p);
494    void addExitInstPoint(image_instPoint *p);
495
496    // ----------------------------------------------------------------------
497
498    ////////////////////////////////////////////////
499    // Misc
500    ////////////////////////////////////////////////
501
502    codeRange *copy() const;
503
504     struct compare {
505         bool operator()(image_func * const &f1,
506                         image_func * const &f2) const {
507             return (f1->getOffset() < f2->getOffset());
508         }
509     };
510
511 #if defined(arch_ia64) || defined(arch_x86) || defined(arch_x86_64)
512
513    bool isTrueCallInsn(const instruction insn);
514 #endif
515
516 #if defined(sparc_sun_solaris2_4)
517    bool is_o7_live(){ return o7_live; }
518 #endif
519
520    // Only defined on alpha right now
521    int             frame_size; // stack frame size
522
523 #if defined(arch_ia64)
524    // We need to know where all the alloc instructions in the
525    // function are to do a reasonable job of register allocation
526    // in the base tramp.  
527    pdvector< Address > allocs;
528    
529    // Place to store the results of doFloatingPointStaticAnalysis().
530    // This way, if they are ever needed in a mini-tramp, emitFuncJump()
531    // for example, the expensive operation doesn't need to happen again.
532    bool * usedFPregs;
533    
534    // Since the IA-64 ABI does not define a frame pointer register,
535    // we use DWARF debug records (DW_AT_frame_base entries) to 
536    // construct an AST which calculates the frame pointer.
537    int getFramePointerCalculator();
538 #endif
539
540    // Ifdef relocation... but set at parse time.
541    bool canBeRelocated() const { return canBeRelocated_; }
542    bool needsRelocation() const { return needsRelocation_; }
543    void markAsNeedingRelocation(bool foo) { needsRelocation_ = foo; }
544
545    bool containsSharedBlocks() const { return containsSharedBlocks_; }
546
547    image_basicBlock * entryBlock();
548
549    /****** OpenMP Parsing Functions *******/
550    std::string calcParentFunc(const image_func * imf, pdvector<image_parRegion *> & pR);
551    void parseOMP(image_parRegion * parReg, image_func * parentFunc, int & currentSectionNum);
552    void parseOMPSectFunc(image_func * parentFunc);
553    void parseOMPFunc(bool hasLoop);
554    bool parseOMPParent(image_parRegion * iPar, int desiredNum, int & currentSectionNum);
555    void addRegion(image_parRegion * iPar) { parRegionsList.push_back(iPar); }
556    bool OMPparsed() { return OMPparsed_; }
557    bool isPLTFunction() { return isPLTFunction_; }
558    /****************************************/
559
560    bool parsed() { return parsed_; }
561
562    // Not completely implemented, and so commented out.
563    std::set<Register> * usedGPRs() { calcUsedRegs(); return &(usedRegisters->generalPurposeRegisters);}
564    std::set<Register> * usedFPRs() { calcUsedRegs(); return &(usedRegisters->floatingPointRegisters);}
565
566    bool isLeafFunc();
567
568    bool writesFPRs(unsigned level = 0);
569    bool writesSPRs(unsigned level = 0);
570
571 #if defined(cap_liveness)
572    void calcBlockLevelLiveness();
573 #endif
574
575    FuncSource howDiscovered() const { return howDiscovered_; }
576    
577    const Function *func() const { return func_; }
578
579    bool containsBlock(image_basicBlock *);
580
581  private:
582      void markBlockEnd(image_basicBlock* curBlock,
583                        InstructionAdapter& ah,
584                        Address& funcEnd);
585      bool isNonReturningCall(image_func* targetFunc,
586                              bool isInPLT,
587                              std::string pltEntryForTarget,
588                              Address currAddr,
589                              Address target);
590    
591    void calcUsedRegs();/* Does one time calculation of registers used in a function, if called again
592                           it just refers to the stored values and returns that */
593
594    ///////////////////// Basic func info
595    Function *func_;                     /* pointer to the underlying symtab Function */
596
597    Address endOffset_;          /* Address of the (next instruction after) the end of the func */
598    pdmodule *mod_;              /* pointer to file that defines func. */
599    image *image_;
600    bool parsed_;                /* Set to true in findInstPoints */
601    bool OMPparsed_;              /* Set true in parseOMPFunc */
602    bool cleansOwnStack_;
603
604    /////  Variables for liveness Analysis
605    image_func_registers * usedRegisters;// container class for all the registers the function uses
606
607    enum regUseState { unknown, used, unused };
608
609    regUseState containsFPRWrites_;   // does this function have floating point write instructions
610    regUseState containsSPRWrites_;   // Does this function write to SPRs.
611
612
613    ///////////////////// CFG and function body
614    set<image_basicBlock*, image_basicBlock::compare> blockList;
615
616    bool noStackFrame; // formerly "leaf".  True iff this fn has no stack frame.
617    bool makesNoCalls_;
618    bool savesFP_;
619
620    bool containsSharedBlocks_;  // True if one or more blocks in this
621                                 // function are shared with another function.
622
623    FuncReturnStatus retStatus_; // Does this function return or not?
624
625    // Bind a call target to the current basic block
626    // May initiate recursive parsing of the target function
627    image_func* bindCallTarget(Address target, image_basicBlock * curBlk);
628
629     // Find an existing image_func object or create a new one
630    image_func* FindOrCreateFunc(Address target, FuncSource src, bool & created);
631
632    
633    ///////////////////// Instpoints 
634
635    pdvector<image_instPoint*> funcEntries_;     /* place to instrument entry 
636                                                    (often not addr) */
637    pdvector<image_instPoint*> funcReturns;      /* return point(s). */
638    pdvector<image_instPoint*> calls;            /* pointer to the calls */
639
640    //  OpenMP (and other parallel language) support
641    pdvector<image_parRegion*> parRegionsList; /* vector of all parallel regions within function */
642    // End OpenMP support
643
644
645
646    bool isTrap;                 // true if function contains a trap instruct
647    InstrumentableLevel instLevel_;   // the degree of freedom we have in
648                                     // instrumenting the function
649    
650    bool canBeRelocated_;           // True if nothing prevents us from
651                                    // relocating function
652    bool needsRelocation_;          // Override -- "relocate this func"
653
654    void *originalCode;   // points to copy of original function
655
656    // Hacky way around parsing things -- we can stick things known to be 
657    // unparseable in here.
658    bool isInstrumentableByFunctionName();
659
660    // Misc   
661
662    // the vector "calls" should not be accessed until this is true.
663    bool o7_live;
664
665    // Functions only have one entry basic block
666    image_basicBlock *entryBlock_;
667
668 #if defined(cap_liveness)
669    bool livenessCalculated_;
670 #endif
671    bool isPLTFunction_;
672
673    // How we discovered this function (e.g., from symbol, RT, etc)
674    FuncSource howDiscovered_;
675 };
676
677 typedef image_func *ifuncPtr;
678
679 struct ifuncCmp
680 {
681     int operator()( const ifuncPtr &f1, const ifuncPtr &f2 ) const
682     {
683         if( f1->getOffset() > f2->getOffset() )
684             return 1;
685         if( f1->getOffset() < f2->getOffset() )
686             return -1;
687         return 0;
688     }
689 };
690
691 #endif /* FUNCTION_H */