Assorted bugfixes: don't die on DW_OP_piece, remove unimplemented stream operators...
[dyninst.git] / dyninstAPI / src / parse-cfg.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30  
31 // $Id: parse-cfg.h,v 1.37 2008/09/03 06:08:44 jaw Exp $
32
33 #ifndef IMAGE_FUNC_H
34 #define IMAGE_FUNC_H
35
36 #include <string>
37 #include "common/src/Vector.h"
38 #include "common/src/Types.h"
39 #include "common/src/Pair.h"
40 #include "common/src/arch.h" // instruction
41 #include "codeRange.h"
42 #include "parRegion.h"
43 #include <unordered_map>
44 #include "symtabAPI/h/Symbol.h"
45 #include "bitArray.h"
46 #include "InstructionCache.h"
47 #include <set>
48
49 #include "Parsing.h"
50
51 #include "symtabAPI/h/Function.h"
52
53 #include <queue>
54
55 using namespace Dyninst;
56
57 class pdmodule;
58
59 class parse_block;
60 class image_edge;
61
62 class parse_block : public codeRange, public ParseAPI::Block  {
63     friend class parse_func;
64     friend class DynCFGFactory;
65  private:
66     parse_block(ParseAPI::CodeObject *, ParseAPI::CodeRegion*, Address);
67  public:
68     parse_block(parse_func*,ParseAPI::CodeRegion*,Address);
69     ~parse_block();
70
71     // just pass through to Block
72     Address firstInsnOffset() const;
73     Address lastInsnOffset() const;
74     Address endOffset() const;
75     Address getSize() const;
76
77     // cfg access & various predicates 
78     bool isShared() const { return containingFuncs() > 1; }
79     bool isExitBlock();
80     bool isCallBlock();
81     bool isEntryBlock(parse_func * f) const;
82     parse_func *getEntryFunc() const;  // func starting with this bock
83
84     bool unresolvedCF() const { return unresolvedCF_; }
85     bool abruptEnd() const { return abruptEnd_; }
86     void setUnresolvedCF(bool newVal);
87     void setAbruptEnd(bool newVal) { abruptEnd_ = newVal; }
88
89     // misc utility
90     int id() const { return blockNumber_; }
91     void debugPrint();
92     image *img();
93     
94     // Find callees
95     parse_func *getCallee();
96     // Returns the address of our callee (if we're a call block, of course)
97     std::pair<bool, Address> callTarget();
98
99     // instrumentation-related
100     bool needsRelocation() const { return needsRelocation_; }
101     void markAsNeedingRelocation() { needsRelocation_ = true; }
102
103     // codeRange implementation
104     void *getPtrToInstruction(Address addr) const;
105     Address get_address() const { return firstInsnOffset(); }
106     unsigned get_size() const { return getSize(); }
107
108     // etc.
109     struct compare {
110         bool operator()(parse_block * const &b1,
111                         parse_block * const &b2) const {
112             if(b1->firstInsnOffset() < b2->firstInsnOffset())
113                 return true;
114             if(b2->firstInsnOffset() < b1->firstInsnOffset())
115                 return false;
116
117             // XXX the remainder is debugging, and should be removed
118             if(b1 != b2)
119                 fprintf(stderr,"error: two blocks (%p,%p) at 0x%lx\n",
120                     b1,b2,b1->firstInsnOffset());
121
122             assert(b1 == b2);
123             return false;
124         }
125     };
126     typedef std::set<parse_block *, parse_block::compare> blockSet;
127
128     const bitArray &getLivenessIn(parse_func * context);
129     // This is copied from the union of all successor blocks
130     const bitArray getLivenessOut(parse_func * context);
131
132     typedef std::map<Offset, InstructionAPI::Instruction::Ptr> Insns;
133     // The provided parameter is a magic offset to add to each instruction's
134     // address; we do this to avoid a copy when getting Insns from block_instances
135     void getInsns(Insns &instances, Address offset = 0);
136
137  private:
138     bool needsRelocation_;
139     int blockNumber_;
140
141     bool unresolvedCF_;
142     bool abruptEnd_;
143
144     /* Liveness analysis variables */
145     /** gen registers */
146     
147     bitArray use; // Registers used by instructions within the block
148     bitArray def; // Registers defined by instructions within the block
149     bitArray in;  // Summarized input liveness; we calculate output on the fly
150  public:
151     static InstructionCache cachedLivenessInfo;
152     
153  private:
154     void summarizeBlockLivenessInfo(parse_func * context);
155     // Returns true if any information changed; false otherwise
156     bool updateBlockLivenessInfo(parse_func * context);
157
158
159 };
160
161 inline Address 
162 parse_block::firstInsnOffset() const {
163     return ParseAPI::Block::start(); 
164 }
165 inline Address 
166 parse_block::lastInsnOffset() const {
167     return ParseAPI::Block::lastInsnAddr();
168 }
169 inline Address 
170 parse_block::endOffset() const {
171     return ParseAPI::Block::end();
172 }
173 inline Address 
174 parse_block::getSize() const {
175     return ParseAPI::Block::size();
176 }
177
178 void checkIfRelocatable (instruction insn, bool &canBeRelocated);
179
180 class image_edge : public ParseAPI::Edge {
181     friend class parse_block;
182  public:
183     image_edge(parse_block *source, 
184                parse_block *target, 
185                EdgeTypeEnum type) :
186     ParseAPI::Edge(source,target,type)
187    { }
188
189     // MSVC++ 2003 does not properly support covariant return types
190     // in overloaded methods
191 #if !defined _MSC_VER || _MSC_VER > 1310 
192    virtual parse_block * src() const { return (parse_block*)_source; }
193    virtual parse_block * trg() const { return (parse_block*)_target; }
194 #endif
195
196    const char * getTypeString();
197 };
198
199 #include "ast.h"
200 class parse_func_registers {
201  public:
202   std::set<Register> generalPurposeRegisters;
203   std::set<Register> floatingPointRegisters;
204   std::set<Register> specialPurposeRegisters;
205 };
206
207 class parse_func : public ParseAPI::Function
208 {
209    enum UnresolvedCF {
210       UNSET_CF,
211       HAS_UNRESOLVED_CF,
212       NO_UNRESOLVED_CF
213    };
214
215   friend class DynCFGFactory;
216   friend class DynParseCallback;
217   public:
218    /* Annotatable requires a default constructor */
219    parse_func() { }
220   public:
221    parse_func(SymtabAPI::Function *func, 
222         pdmodule *m, 
223         image *i, 
224         ParseAPI::CodeObject * obj,
225         ParseAPI::CodeRegion * reg,
226         InstructionSource * isrc,
227         FuncSource src);
228
229    ~parse_func();
230
231    SymtabAPI::Function* getSymtabFunction() const{
232       return  func_; 
233    }    
234
235    /*** Function naming ***/
236    const string &symTabName() const { 
237        return func_->getFirstSymbol()->getMangledName();
238    }
239    const string &prettyName() const {
240        return func_->getFirstSymbol()->getPrettyName();
241    }
242    const string &typedName() const {
243        return func_->getFirstSymbol()->getTypedName();
244    }
245    const vector<string> &symTabNameVector() const {
246        return func_->getAllMangledNames();
247    }
248    const vector<string> &prettyNameVector() const {
249        return func_->getAllPrettyNames();
250    }
251    const vector<string> &typedNameVector() const {
252        return func_->getAllTypedNames();
253    }
254    void copyNames(parse_func *duplicate);
255    // return true if the name is new (and therefore added)
256    bool addSymTabName(std::string name, bool isPrimary = false);
257    bool addPrettyName(std::string name, bool isPrimary = false);
258    bool addTypedName(std::string name, bool isPrimary = false);
259
260    /*** Location queries ***/
261    Address getOffset() const;
262    Address getPtrOffset() const;
263    unsigned getSymTabSize() const;
264    Address getEndOffset(); // May trigger parsing
265
266    void *getPtrToInstruction(Address addr) const;
267
268    /*** misc. accessors ***/
269    pdmodule *pdmod() const { return mod_;}
270    image *img() const { return image_; }
271    void changeModule(pdmodule *mod);
272
273    ////////////////////////////////////////////////
274    // CFG and other function body methods
275    ////////////////////////////////////////////////
276
277    bool makesNoCalls();
278
279    ////////////////////////////////////////////////
280    // Instpoints!
281    ////////////////////////////////////////////////
282
283    // Initiate parsing on this function
284    bool parse();
285  
286    const pdvector<image_parRegion*> &parRegions();
287
288    bool isInstrumentable();
289    bool hasUnresolvedCF();
290
291    // ----------------------------------------------------------------------
292
293
294    ///////////////////////////////////////////////////
295    // Mutable function code, used for hybrid analysis
296    ///////////////////////////////////////////////////
297    
298    void getReachableBlocks
299    ( const std::set<parse_block*> &exceptBlocks, // input
300      const std::list<parse_block*> &seedBlocks, // input
301      std::set<parse_block*> &reachableBlocks ); // output
302    ParseAPI::FuncReturnStatus init_retstatus() const; // only call on defensive binaries
303    void setinit_retstatus(ParseAPI::FuncReturnStatus rs); //also sets retstatus
304    bool hasWeirdInsns() { return hasWeirdInsns_; } // true if we stopped the 
305                                 // parse at a weird instruction (e.g., arpl)
306    void setHasWeirdInsns(bool wi);
307    void setPrevBlocksUnresolvedCF(int newVal) { prevBlocksUnresolvedCF_ = newVal; };
308    int getPrevBlocksUnresolvedCF() const { return prevBlocksUnresolvedCF_; };
309
310
311    // ----------------------------------------------------------------------
312
313
314    ////////////////////////////////////////////////
315    // Misc
316    ////////////////////////////////////////////////
317
318     struct compare {
319         bool operator()(parse_func * const &f1,
320                         parse_func * const &f2) const {
321             return (f1->getOffset() < f2->getOffset());
322         }
323     };
324
325 #if defined(arch_x86) || defined(arch_x86_64)
326    bool isTrueCallInsn(const instruction insn);
327 #endif
328
329 #if defined(arch_power)
330    bool savesReturnAddr() const { return ppc_saves_return_addr_; }
331 #endif
332
333    bool containsSharedBlocks() const { return containsSharedBlocks_; }
334
335    parse_block * entryBlock();
336
337    /****** OpenMP Parsing Functions *******/
338    std::string calcParentFunc(const parse_func * imf, pdvector<image_parRegion *> & pR);
339    void parseOMP(image_parRegion * parReg, parse_func * parentFunc, int & currentSectionNum);
340    void parseOMPSectFunc(parse_func * parentFunc);
341    void parseOMPFunc(bool hasLoop);
342    bool parseOMPParent(image_parRegion * iPar, int desiredNum, int & currentSectionNum);
343    void addRegion(image_parRegion * iPar) { parRegionsList.push_back(iPar); }
344    bool OMPparsed() { return OMPparsed_; }
345    /****************************************/
346    bool isPLTFunction();
347
348    std::set<Register> * usedGPRs() { calcUsedRegs(); return &(usedRegisters->generalPurposeRegisters);}
349    std::set<Register> * usedFPRs() { calcUsedRegs(); return &(usedRegisters->floatingPointRegisters);}
350
351    bool isLeafFunc();
352
353    bool writesFPRs(unsigned level = 0);
354    bool writesSPRs(unsigned level = 0);
355
356
357    void invalidateLiveness() { livenessCalculated_ = false; }
358    void calcBlockLevelLiveness();
359
360    const SymtabAPI::Function *func() const { return func_; }
361
362  private:
363    void calcUsedRegs();/* Does one time calculation of registers used in a function, if called again
364                           it just refers to the stored values and returns that */
365
366    ///////////////////// Basic func info
367    SymtabAPI::Function *func_;                  /* pointer to the underlying symtab Function */
368
369    pdmodule *mod_;              /* pointer to file that defines func. */
370    image *image_;
371    bool OMPparsed_;              /* Set true in parseOMPFunc */
372
373    /////  Variables for liveness Analysis
374    enum regUseState { unknown, used, unused };
375    parse_func_registers * usedRegisters;
376    regUseState containsFPRWrites_;   // floating point registers
377    regUseState containsSPRWrites_;   // stack pointer registers
378
379    ///////////////////// CFG and function body
380    bool containsSharedBlocks_;  // True if one or more blocks in this
381                                 // function are shared with another function.
382
383    //  OpenMP (and other parallel language) support
384    pdvector<image_parRegion*> parRegionsList; /* vector of all parallel regions within function */
385     void addParRegion(Address begin, Address end, parRegType t);
386    // End OpenMP support
387
388    bool hasWeirdInsns_;            // true if we stopped the parse at a 
389                                                                            // weird instruction (e.g., arpl)
390    int prevBlocksUnresolvedCF_; // num func blocks when calculated
391
392    // Some functions are known to be unparesable by name
393    bool isInstrumentableByFunctionName();
394    UnresolvedCF unresolvedCF_;
395
396    ParseAPI::FuncReturnStatus init_retstatus_;
397
398    // Architecture specific data
399    bool o7_live;
400    bool ppc_saves_return_addr_;
401
402    bool livenessCalculated_;
403    bool isPLTFunction_;
404 };
405
406 typedef parse_func *ifuncPtr;
407
408 struct ifuncCmp
409 {
410     int operator()( const ifuncPtr &f1, const ifuncPtr &f2 ) const
411     {
412         if( f1->getOffset() > f2->getOffset() )
413             return 1;
414         if( f1->getOffset() < f2->getOffset() )
415             return -1;
416         return 0;
417     }
418 };
419
420 inline Address 
421 parse_func::getOffset() const {
422     return ParseAPI::Function::addr();
423 }
424 inline Address 
425 parse_func::getPtrOffset() const {
426     return func_->getFirstSymbol()->getPtrOffset();
427 }
428 inline unsigned 
429 parse_func::getSymTabSize() const { 
430     return func_->getFirstSymbol()->getSize();
431 }
432
433
434
435 #endif /* FUNCTION_H */