Fix our tailcall parsing; we've observed conditional tailcalls in the wild and weren...
[dyninst.git] / dyninstAPI / src / parse-cfg.C
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.C,v 1.60 2008/11/03 15:19:24 jaw Exp $
32
33 #include "function.h"
34 #include "instPoint.h"
35
36 #include "instructionAPI/h/InstructionDecoder.h"
37
38 #include "image.h"
39 #include "debug.h"
40
41 using namespace Dyninst;
42 using namespace Dyninst::ParseAPI;
43
44 int parse_func_count = 0;
45
46 const char * image_edge::getTypeString()
47 {
48     switch(type()) {
49         case CALL:
50             return "CALL";
51             break;
52         case COND_TAKEN:
53             return "COND BRANCH - TAKEN";
54             break;
55         case COND_NOT_TAKEN:
56             return "COND BRANCH - NOT TAKEN";
57             break;
58         case INDIRECT:
59             return "INDIRECT BRANCH";
60             break;
61         case DIRECT:
62             return "UNCOND BRANCH";
63             break;
64         case FALLTHROUGH:
65             return "FALLTHROUGH";
66             break;
67         case CATCH:
68             return "CATCH";
69             break;
70         case CALL_FT:
71             return "POST-CALL FALLTHROUGH";
72             break;
73         case RET:
74             return "RETURN";
75             break;
76         default:
77             return "ERROR UNKNOWN";
78             break;
79     }
80 }
81
82 parse_func::parse_func(
83     SymtabAPI::Function *func, 
84     pdmodule *m, 
85     image *i, 
86     CodeObject * obj,
87     CodeRegion * reg,
88     InstructionSource * isrc,
89     FuncSource src):
90   Function(func->getOffset(),func->getFirstSymbol()->getMangledName(),obj,reg,isrc),
91   func_(func),
92   mod_(m),
93   image_(i),
94   usedRegisters(NULL),
95   containsFPRWrites_(unknown),
96   containsSPRWrites_(unknown),
97   containsSharedBlocks_(false),
98   hasWeirdInsns_(false),
99   prevBlocksUnresolvedCF_(0),
100   unresolvedCF_(UNSET_CF),
101   init_retstatus_(UNSET),
102   o7_live(false),
103   ppc_saves_return_addr_(false)
104 #if defined(cap_liveness)
105   , livenessCalculated_(false)
106 #endif
107   ,isPLTFunction_(false)
108 {
109 #if defined(ROUGH_MEMORY_PROFILE)
110     parse_func_count++;
111     if ((parse_func_count % 100) == 0)
112         fprintf(stderr, "parse_func_count: %d (%d)\n",
113                 parse_func_count, parse_func_count*sizeof(parse_func));
114 #endif
115     _src = src;
116     extern AnnotationClass<parse_func> ImageFuncUpPtrAnno;
117     if (!func_->addAnnotation(this, ImageFuncUpPtrAnno))
118     {
119        fprintf(stderr, "%s[%d]:  failed to add annotation here\n", FILE__, __LINE__);
120     }
121 }       
122
123
124 parse_func::~parse_func() 
125 {
126     /* FIXME */ 
127   mal_printf("~image_func() for func at %lx\n",_start);
128   delete usedRegisters;
129 }
130
131 bool parse_func::addSymTabName(std::string name, bool isPrimary) 
132 {
133     if(func_->addMangledName(name.c_str(), isPrimary)){
134         return true;
135     }
136
137     return false;
138 }
139
140 bool parse_func::addPrettyName(std::string name, bool isPrimary) {
141    if (func_->addPrettyName(name.c_str(), isPrimary)) {
142       return true;
143    }
144    
145    return false;
146 }
147
148 bool parse_func::addTypedName(std::string name, bool isPrimary) {
149     // Count this as a pretty name in function lookup...
150     if (func_->addTypedName(name.c_str(), isPrimary)) {
151         return true;
152     }
153
154     return false;
155 }
156
157 void parse_func::changeModule(pdmodule *mod) {
158   // Called from buildFunctionLists, so we aren't entered in any 
159   // module-level data structures. If this changes, UPDATE THE
160   // FUNCTION.
161   mod_ = mod;
162 }
163
164 bool parse_func::isInstrumentableByFunctionName()
165 {
166 #if defined(i386_unknown_solaris2_5)
167     /* On Solaris, this function is called when a signal handler
168        returns.  If it requires trap-based instrumentation, it can foul
169        the handler return mechanism.  So, better exclude it.  */
170     if (prettyName() == "_setcontext" || prettyName() == "setcontext")
171         return false;
172 #endif /* i386_unknown_solaris2_5 */
173     
174     // XXXXX kludge: these functions are called by DYNINSTgetCPUtime, 
175     // they can't be instrumented or we would have an infinite loop
176     if (prettyName() == "gethrvtime" || prettyName() == "_divdi3"
177         || prettyName() == "GetProcessTimes")
178         return false;
179     return true;
180 }
181
182 Address parse_func::getEndOffset() {
183     if (!parsed()) image_->analyzeIfNeeded();
184     if(blocks().empty()) {
185         fprintf(stderr,"error: end offset requested for empty function\n");
186         return addr();
187     } else {
188         return extents().back()->end();
189     }
190 }
191
192
193 const pdvector<image_parRegion *> &parse_func::parRegions() {
194   if (!parsed()) image_->analyzeIfNeeded();
195   return parRegionsList;
196 }
197
198 bool parse_func::isPLTFunction() {
199     return obj()->cs()->linkage().find(addr()) !=
200            obj()->cs()->linkage().end();
201 }
202
203 int parse_block_count = 0;
204
205 /*
206  * For CFGFactory::mksink only 
207  */
208 parse_block::parse_block(
209         CodeObject * obj, 
210         CodeRegion * reg,
211         Address addr) :
212     Block(obj,reg,addr),
213     needsRelocation_(false)
214 {
215      
216 }
217
218 parse_block::parse_block(
219         parse_func * func, 
220         CodeRegion * reg,
221         Address firstOffset) :
222     Block(func->obj(),reg,firstOffset),
223     needsRelocation_(false),
224     unresolvedCF_(false),
225     abruptEnd_(false)
226
227     // basic block IDs are unique within images.
228     blockNumber_ = func->img()->getNextBlockID();
229 #if defined(ROUGH_MEMORY_PROFILE)
230     parse_block_count++;
231     if ((parse_block_count % 100) == 0)
232         fprintf(stderr, "parse_block_count: %d (%d)\n",
233                 parse_block_count, parse_block_count*sizeof(parse_block));
234 #endif
235 }
236
237 parse_block::~parse_block() {
238
239 }
240
241
242 void parse_block::debugPrint() {
243    // no looping if we're not printing anything
244     if(!dyn_debug_parsing)
245         return;
246
247     parsing_printf("Block %d: starts 0x%lx, last 0x%lx, end 0x%lx\n",
248                    blockNumber_,
249                    start(),
250                    lastInsnAddr(),
251                    end());
252
253     parsing_printf("  Sources:\n");
254     const Block::edgelist & srcs = sources();
255     Block::edgelist::const_iterator sit = srcs.begin();
256     unsigned s = 0;
257     for ( ; sit != srcs.end(); ++sit) {
258         parse_block * src = static_cast<parse_block*>((*sit)->src());
259         parsing_printf("    %d: block %d (%s)\n",
260                        s, src->blockNumber_,
261                        static_cast<image_edge*>(*sit)->getTypeString());
262         ++s;
263     }
264     parsing_printf("  Targets:\n");
265     const Block::edgelist & trgs = sources();
266     Block::edgelist::const_iterator tit = trgs.begin();
267     unsigned t = 0;
268     for( ; tit != trgs.end(); ++tit) {
269         parse_block * trg = static_cast<parse_block*>((*tit)->trg());
270         parsing_printf("    %d: block %d (%s)\n",
271                        t, trg->blockNumber_,
272                        static_cast<image_edge*>(*tit)->getTypeString());
273         ++t;
274     }
275 }
276
277 void *parse_block::getPtrToInstruction(Address addr) const {
278     if (addr < start()) return NULL;
279     if (addr >= end()) return NULL;
280     // XXX all potential parent functions have the same image
281     return region()->getPtrToInstruction(addr);
282 }
283
284 /* Returns NULL if the address is not within a block belonging to this function.
285    Why do we even bother returning NULL if the address is outside of this
286    function? FIXME check whether we can do away with that.
287 */
288 void *parse_func::getPtrToInstruction(Address addr) const {
289     // The commented-out code checks whether the address is within
290     // the bytes of this function (one of its basic blocks). Instead,
291     // we do a fast path and just pass the request through to the image.
292     // The old tests are preserved for posterity.
293     /*
294     if (addr < getOffset()) return NULL;
295
296     // XXX this call may modify the current function, so const semantics
297     //     are not actually perserved
298     set<Function *> stab;
299     img()->findFuncs(addr,stab);
300
301     if(!stab.empty()) {
302         set<Function*>::iterator fit = stab.begin();
303         for( ; fit != stab.end(); ++fit) {
304             if(*fit == this)
305                 return obj().getPtrToInstruction(addr);
306         }
307     }
308     return NULL;
309     */
310     return isrc()->getPtrToInstruction(addr);
311 }
312
313 bool parse_block::isEntryBlock(parse_func * f) const
314 {
315     return f->entryBlock() == this;
316
317
318 /*
319  * True if the block has a return edge, or a call that does
320  * not return (i.e., a tail call or non-returning call)
321  */
322 bool parse_block::isExitBlock()
323 {
324     const Block::edgelist & trgs = targets();
325     if(trgs.empty()) {
326         return false;
327     }
328
329     Edge * e = *trgs.begin();
330     if (e->type() == RET) {
331         return true;
332     }
333
334     if (!e->interproc()) {
335         return false;
336     }
337
338     if (e->type() == CALL && trgs.size() > 1) {
339         // there's a CALL edge and at least one other edge, 
340         // it's an exit block if there is no CALL_FT edge
341         for(Block::edgelist::const_iterator eit = ++(trgs.begin());
342             eit != trgs.end();
343             eit++)
344         {
345             if ((*eit)->type() == CALL_FT && !(*eit)->sinkEdge()) {
346                 return false;
347             }
348         }
349     }
350     return true;
351 }
352
353 bool parse_block::isCallBlock()
354 {
355     const Block::edgelist & trgs = targets();
356     if(!trgs.empty())
357     {
358         for (Block::edgelist::const_iterator eit = trgs.begin();
359              eit != trgs.end();
360              eit++) 
361         {
362             if ((*eit)->type() == CALL) {
363                 return true;
364             }
365         }
366     }
367     return false;
368 }
369
370 image *parse_block::img()
371 {
372     vector<Function*> funcs;
373     getFuncs(funcs);
374     return static_cast<parse_func*>(funcs[0])->img();
375 }
376
377 parse_func *parse_block::getEntryFunc() const {
378     parse_func *ret =
379         static_cast<parse_func*>(obj()->findFuncByEntry(region(),start()));
380
381     // sanity check
382     if(ret && ret->entryBlock() != this) {
383         parsing_printf("[%s:%d] anomaly: block [%lx,%lx) is not entry for "
384                        "func at %lx\n",
385             FILE__,__LINE__,start(),end(),ret->addr());
386     }
387     return ret;
388 }
389
390 parse_block * parse_func::entryBlock() { 
391     if (!parsed()) image_->analyzeIfNeeded();
392     return static_cast<parse_block*>(entry());
393 }
394
395 bool parse_func::isLeafFunc() {
396     if (!parsed())
397         image_->analyzeIfNeeded();
398
399     return !callEdges().empty();
400 }
401
402 void parse_func::addParRegion(Address begin, Address end, parRegType t)
403 {
404     image_parRegion * iPar = new image_parRegion(begin, this);
405     iPar->setRegionType(t);
406     iPar->setParentFunc(this); // when not outlined, parent func will be same as regular
407     iPar->setLastInsn(end);
408     parRegionsList.push_back(iPar);
409 }
410
411 void parse_block::getInsns(Insns &insns, Address base) {
412    using namespace InstructionAPI;
413    Offset off = firstInsnOffset();
414    const unsigned char *ptr = (const unsigned char *)getPtrToInstruction(off);
415    if (ptr == NULL) return;
416
417    InstructionDecoder d(ptr, getSize(),obj()->cs()->getArch());
418
419    while (off < endOffset()) {
420       Instruction::Ptr insn = d.decode();
421
422       insns[off + base] = insn;
423       off += insn->size();
424    }
425 }
426
427
428 /* This function is static.
429  *
430  * Find the blocks that are reachable from the seed blocks 
431  * if the except blocks are not part of the CFG
432  */
433 void parse_func::getReachableBlocks
434 (const std::set<parse_block*> &exceptBlocks,
435  const std::list<parse_block*> &seedBlocks,
436  std::set<parse_block*> &reachBlocks)
437 {
438     using namespace ParseAPI;
439     mal_printf("reachable blocks for func %lx from %d start blocks\n",
440                addr(), seedBlocks.size());
441
442     // init visited set with seed and except blocks
443     std::set<parse_block*> visited;
444     visited.insert(exceptBlocks.begin(), exceptBlocks.end());
445     visited.insert(seedBlocks.begin(), seedBlocks.end());
446
447     // add seed blocks to the worklist (unless the seed is in exceptBlocks)
448     std::list<parse_block*> worklist;
449     for (list<parse_block*>::const_iterator sit = seedBlocks.begin();
450          sit != seedBlocks.end();
451          sit++) 
452     {
453         visited.insert(*sit);
454         if (exceptBlocks.end() == exceptBlocks.find(*sit)) {
455             worklist.push_back(*sit);
456             reachBlocks.insert(*sit);
457         }
458     }
459         
460     // iterate through worklist, adding all blocks (except for
461     // seedBlocks) that are reachable through target edges to the
462     // reachBlocks set
463     while(worklist.size()) {
464         parse_block *curBlock = worklist.front();
465         const Block::edgelist & outEdges = curBlock->targets();
466         Block::edgelist::const_iterator tIter = outEdges.begin();
467         for (; tIter != outEdges.end(); tIter++) {
468             parse_block *targB = (parse_block*) (*tIter)->trg();
469             if ( CALL != (*tIter)->type() &&
470                  false == (*tIter)->sinkEdge() &&
471                  visited.end() == visited.find(targB) )
472                  //reachBlocks.end() == reachBlocks.find(targB) &&
473                  //exceptBlocks.end() == exceptBlocks.find(targB) &&
474                  //seedBlocks.end() == seedBlocks.find(targB) )
475             {
476                 worklist.push_back(targB);
477                 reachBlocks.insert(targB);
478                 visited.insert(targB);
479                 mal_printf("block [%lx %lx] is reachable\n",
480                            targB->firstInsnOffset(),
481                            targB->endOffset());
482             }
483         }
484         worklist.pop_front();
485     } 
486 }
487 void parse_func::setinit_retstatus(ParseAPI::FuncReturnStatus rs)
488 {
489     init_retstatus_ = rs;
490     if (rs > retstatus()) {
491         set_retstatus(rs);
492     }
493 }
494 ParseAPI::FuncReturnStatus parse_func::init_retstatus() const
495 {
496     if (UNSET == init_retstatus_) {
497         assert(!obj()->defensiveMode()); // should have been set for defensive binaries
498         return retstatus();
499     }
500     if (init_retstatus_ > retstatus()) {
501         return retstatus();
502     }
503     return init_retstatus_;
504 }
505
506 void parse_func::setHasWeirdInsns(bool wi)
507 {
508    hasWeirdInsns_ = wi;
509 }
510
511 void parse_block::setUnresolvedCF(bool newVal) 
512
513    unresolvedCF_ = newVal;
514 }
515
516 parse_func *parse_block::getCallee() {
517    for (edgelist::const_iterator iter = targets().begin(); iter != targets().end(); ++iter) {
518       if ((*iter)->type() == ParseAPI::CALL) {
519          parse_block *t = static_cast<parse_block *>((*iter)->trg());
520          return t->getEntryFunc();
521       }
522    }
523    return NULL;
524 }
525
526 std::pair<bool, Address> parse_block::callTarget() {
527    using namespace InstructionAPI;
528    Offset off = lastInsnOffset();
529    const unsigned char *ptr = (const unsigned char *)getPtrToInstruction(off);
530    if (ptr == NULL) return std::make_pair(false, 0);
531    InstructionDecoder d(ptr, endOffset() - lastInsnOffset(), obj()->cs()->getArch());
532    Instruction::Ptr insn = d.decode();
533
534    // Bind PC to that insn
535    // We should build a free function to do this...
536    
537    Expression::Ptr cft = insn->getControlFlowTarget();
538    if (cft) {
539       Expression::Ptr pc(new RegisterAST(MachRegister::getPC(obj()->cs()->getArch())));
540       cft->bind(pc.get(), Result(u64, lastInsnAddr()));
541       Result res = cft->eval();
542       if (!res.defined) return std::make_pair(false, 0);
543    
544       return std::make_pair(true, res.convert<Address>());
545    }
546    return std::make_pair(false, 0);
547 }
548
549 bool parse_func::hasUnresolvedCF() {
550    if (unresolvedCF_ == UNSET_CF) {
551       for (blocklist::iterator iter = blocks().begin();
552            iter != blocks().end(); ++iter) {
553          for (Block::edgelist::const_iterator iter2 = (*iter)->targets().begin();
554               iter2 != (*iter)->targets().end(); ++iter2) {
555             if ((*iter2)->sinkEdge() &&
556                 (((*iter2)->type() == ParseAPI::INDIRECT) ||
557                  ((*iter2)->type() == ParseAPI::DIRECT))) {
558                unresolvedCF_ = HAS_UNRESOLVED_CF;
559                break;
560             }
561          }
562          if (unresolvedCF_ == HAS_UNRESOLVED_CF) break;
563       }
564       if (unresolvedCF_ == UNSET_CF)
565          unresolvedCF_ = NO_UNRESOLVED_CF;
566    }
567    return (unresolvedCF_ == HAS_UNRESOLVED_CF);
568 }
569
570 bool parse_func::isInstrumentable() {
571 #if defined(os_vxworks)
572    // Relocatable objects (kernel modules) are instrumentable on VxWorks.
573    if(!isInstrumentableByFunctionName())
574 #else
575    if(!isInstrumentableByFunctionName() || img()->isRelocatableObj())
576 #endif
577       return false;
578    else {
579       // Create instrumentation points for non-plt functions 
580       if(obj()->cs()->linkage().find(getOffset()) != obj()->cs()->linkage().end()) { 
581          return false;
582       }
583     }
584
585    if (hasUnresolvedCF()) {
586       return false;
587    }
588    return true;
589 }