Debug output cleanning and ParseAPI manual update
[dyninst.git] / parseAPI / src / Function.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 #include <algorithm>
31
32 #include "dyntypes.h"
33
34 #include "CodeObject.h"
35 #include "CFG.h"
36
37 #include "Parser.h"
38 #include "debug_parse.h"
39 #include "util.h"
40 #include "LoopAnalyzer.h"
41 #include "dominator.h"
42
43 #include "dataflowAPI/h/slicing.h"
44 #include "dataflowAPI/h/AbslocInterface.h"
45 #include "instructionAPI/h/InstructionDecoder.h"
46 #include "common/h/Graph.h"
47 #include "StackTamperVisitor.h"
48
49
50 using namespace std;
51
52 using namespace Dyninst;
53 using namespace Dyninst::ParseAPI;
54
55 Function::Function() :
56         _start(0),
57         _obj(NULL),
58         _region(NULL),
59         _isrc(NULL),
60         _src(RT),
61         _rs(UNSET),
62         _entry(NULL),
63          _is_leaf_function(true),
64          _ret_addr(0),
65         _parsed(false),
66         _cache_valid(false),
67         _no_stack_frame(true),
68         _saves_fp(false),
69         _cleans_stack(false),
70         _tamper(TAMPER_UNSET),
71         _tamper_addr(0),
72         _loop_analyzed(false),
73         _loop_root(NULL),
74         isDominatorInfoReady(false),
75         isPostDominatorInfoReady(false)
76
77 {
78     fprintf(stderr,"PROBABLE ERROR, default ParseAPI::Function constructor\n");
79 }
80
81 Function::Function(Address addr, string name, CodeObject * obj, 
82     CodeRegion * region, InstructionSource * isrc) :
83         _start(addr),
84         _obj(obj),
85         _region(region),
86         _isrc(isrc),
87         _src(RT),
88         _rs(UNSET),
89         _name(name),
90         _entry(NULL),
91          _is_leaf_function(true),
92          _ret_addr(0),
93         _parsed(false),
94         _cache_valid(false),
95         _no_stack_frame(true),
96         _saves_fp(false),
97         _cleans_stack(false),
98         _tamper(TAMPER_UNSET),
99         _tamper_addr(0),
100         _loop_analyzed(false),
101         _loop_root(NULL),
102         isDominatorInfoReady(false),
103         isPostDominatorInfoReady(false)
104
105
106 {
107     if (obj->defensiveMode()) {
108         mal_printf("new funct at %lx\n",addr);
109     }
110     if (obj && obj->cs()) {
111         obj->cs()->incrementCounter(PARSE_FUNCTION_COUNT);
112     }
113 }
114
115 ParseAPI::Edge::~Edge() {
116 }
117
118 Function::~Function()
119 {
120     if (_obj && _obj->cs()) {
121         _obj->cs()->decrementCounter(PARSE_FUNCTION_COUNT);
122     }
123     vector<FuncExtent *>::iterator eit = _extents.begin();
124     for( ; eit != _extents.end(); ++eit) {
125         delete *eit;
126     }
127     for (auto lit = _loops.begin(); lit != _loops.end(); ++lit)
128         delete *lit;
129 }
130
131 Function::blocklist
132 Function::blocks()
133 {
134     if(!_cache_valid)
135         finalize();
136     return blocklist(blocks_begin(), blocks_end());
137 }
138
139 // Get the current set of blocks,
140 // as a const operation
141 Function::const_blocklist
142 Function::blocks() const
143 {
144   /*Function* mutable_this = const_cast<Function*>(this);
145   
146   if(!_cache_valid)
147     mutable_this->finalize();
148   */
149   assert(_cache_valid);
150   
151   return const_blocklist(blocks_begin(), blocks_end());
152 }
153
154
155 const Function::edgelist & 
156 Function::callEdges() {
157     if(!_cache_valid)
158         finalize();
159     return _call_edge_list; 
160 }
161
162 Function::const_blocklist
163 Function::returnBlocks() {
164   if (!_cache_valid) 
165     finalize();
166   return const_blocklist(ret_begin(), ret_end());
167 }
168
169 Function::const_blocklist
170 Function::exitBlocks() {
171   if (!_cache_valid) 
172     finalize();
173   return const_blocklist(exit_begin(), exit_end());
174   
175 }
176
177 vector<FuncExtent *> const&
178 Function::extents()
179 {
180     if(!_cache_valid)
181         finalize(); 
182     return _extents;
183 }
184
185 void
186 Function::finalize()
187 {
188   _extents.clear();
189   _exitBL.clear();
190
191   // for each block, decrement its refcount
192   for (auto blk = blocks_begin(); blk != blocks_end(); blk++) {
193     (*blk)->_func_cnt--;
194   }
195   _bmap.clear();
196   _retBL.clear(); 
197   _call_edge_list.clear();
198
199     // The Parser knows how to finalize
200     // a Function's parse data
201     _obj->parser->finalize(this);
202 }
203
204 Function::blocklist
205 Function::blocks_int()
206 {
207     if(_cache_valid || !_entry)
208       return blocklist(blocks_begin(), blocks_end());
209
210     // overloaded map warning:
211     // visited[addr] == 1 means visited
212     // visited[addr] == 2 means already on the return list
213     dyn_hash_map<Address,short> visited;
214     vector<Block *> worklist;
215
216     bool need_entry = true;
217     for(auto bit=blocks_begin();
218         bit!=blocks_end();++bit) 
219     {
220         Block * b = *bit;
221         visited[b->start()] = 1;
222         need_entry = need_entry && (b != _entry);
223     }
224     worklist.insert(worklist.begin(),blocks_begin(), blocks_end());
225
226     if(need_entry) {
227         worklist.push_back(_entry);
228         visited[_entry->start()] = 1;
229         add_block(_entry);
230     }
231
232     // We need to revalidate that the exit blocks we found before are still exit blocks
233     blockmap::iterator nextIt, curIt;
234     for (curIt = _exitBL.begin(); curIt != _exitBL.end(); ) {
235         Block *cur = curIt->second;
236         bool exit_func = false;
237         bool found_call = false;
238         bool found_call_ft = false;
239
240         if (cur->targets().empty()) exit_func = true;
241         for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit) {
242             Edge *e = *eit;
243             Block *t = e->trg();
244             if(e->type() == CALL || e->interproc()) {
245                 found_call = true;
246             }
247             if (e->type() == CALL_FT) {
248                 found_call_ft = true;
249             }
250
251             if (e->type() == RET || t->obj() != cur->obj()) {
252                 exit_func = true;
253                 break;
254             }
255         }
256         if (found_call && !found_call_ft && !obj()->defensiveMode()) exit_func = true;
257
258         if (!exit_func) { 
259             nextIt = curIt;
260             ++nextIt;
261             _exitBL.erase(curIt);
262             curIt = nextIt;
263         } else ++curIt;
264     }
265
266     // avoid adding duplicate return blocks
267     for(auto bit=exit_begin();
268         bit!=exit_end();++bit)
269     {
270         Block * b = *bit;
271         visited[b->start()] = 2;
272     }
273     
274     while(!worklist.empty()) {
275         Block * cur = worklist.back();
276         worklist.pop_back();
277
278         bool link_return = false;
279         bool exits_func = false;
280         bool found_call = false;
281         bool found_call_ft = false;
282         const Block::edgelist & trgs = cur->targets();
283         if (trgs.empty()) {
284            // Woo hlt!
285           parsing_printf("No targets, exits func\n");
286            exits_func = true;
287         }
288         for(Block::edgelist::const_iterator tit=trgs.begin();
289             tit!=trgs.end();++tit) {
290             Edge * e = *tit;
291             Block * t = e->trg();
292
293             parsing_printf("\t Considering target block [0x%lx,0x%lx) from edge %p\n", 
294                            t->start(), t->end(), e); 
295
296             if (e->type() == CALL_FT) {
297                found_call_ft = true;
298             }
299
300             if(e->type() == CALL) {
301                parsing_printf("\t Call typed\n");
302                 _call_edge_list.insert(e);
303                 found_call = true;
304                 continue;
305             }
306
307             if(e->type() == RET) {
308                 link_return = true;
309                 exits_func = true;
310                 parsing_printf("Block has return edge\n");
311                 if (obj()->defensiveMode()) {
312                     if (_tamper != TAMPER_UNSET && _tamper != TAMPER_NONE) 
313                        continue;
314                 }
315                 
316                 set_retstatus(RETURN);
317                 continue;
318             }
319
320             /* Handle tailcall edges */
321             if(e->interproc()) {
322                parsing_printf("\t Interprocedural\n");
323                 _call_edge_list.insert(e);
324                 found_call = true;
325                 continue;
326             }
327             // If we are heading to a different CodeObject, call it a return
328             // and don't add target blocks.
329             if (t->obj() != cur->obj()) {
330                // This is a jump to a different CodeObject; call it an exit
331               parsing_printf("Block exits object\n");
332                exits_func = true;
333                 continue;
334             }
335
336             /* sink edges receive no further processing */
337             if(e->sinkEdge()) {
338                parsing_printf("\t Sink edge, skipping\n");
339                 continue;
340             }
341
342             if(!HASHDEF(visited,t->start())) {
343                parsing_printf("\t Adding target block [%lx,%lx) to worklist according to edge from %lx, type %d\n", t->start(), t->end(), e->src()->last(), e->type());
344                 worklist.push_back(t);
345                 visited[t->start()] = true;
346                 add_block(t);
347             }
348         }
349         if (found_call && !found_call_ft && !obj()->defensiveMode()) {
350           parsing_printf("\t exits func\n");
351            exits_func = true;
352         }
353
354         if (link_return) assert(exits_func);
355
356         if(exits_func) {
357            if (link_return)
358               delayed_link_return(_obj,cur);
359            if(visited[cur->start()] <= 1) {
360              _exitBL[cur->start()] = cur;
361               parsing_printf("Adding block 0x%lx as exit\n", cur->start());
362               if (link_return) 
363               {
364                 _retBL[cur->start()] = cur;
365               }
366               
367            }
368         }
369     }
370
371     return blocklist(blocks_begin(), blocks_end());
372 }
373
374 /* Adds return edges to the CFG for a particular retblk, based 
375  * on callers to this function.  Handles case of return block 
376  * that targets the entry block of a new function separately
377  * (ret to entry happens if the function tampers with its stack 
378  *  and maybe if this function is a signal handler?) 
379  */ 
380 void
381 Function::delayed_link_return(CodeObject * o, Block * retblk)
382 {
383     bool link_entry = false;
384
385     dyn_hash_map<Address,bool> linked;
386     Block::edgelist::const_iterator eit = retblk->targets().begin();
387     for( ; eit != retblk->targets().end(); ++eit) {
388         Edge * e = *eit;
389         linked[e->trg()->start()] = true;
390     }
391
392     eit = _entry->sources().begin();
393     for( ; eit != _entry->sources().end(); ++eit) {
394         Edge * e = *eit;
395         if(e->type() == CALL) {
396             parsing_printf("[%s:%d] linking return edge %lx -> %lx\n",
397                 FILE__,__LINE__,retblk->lastInsnAddr(),e->src()->end());
398
399             // XXX opportunity here to be more conservative about delayed
400             //     determination of return status
401     
402             Block * call_ft = _obj->findBlockByEntry(region(),e->src()->end());
403             if(!call_ft) {
404                 parsing_printf("[%s:%d] no block found, error!\n",
405                     FILE__,__LINE__);
406             } 
407             else if(!HASHDEF(linked,call_ft->start())) {
408                 if(call_ft == _entry)
409                     link_entry = true;
410                 else 
411                     o->add_edge(retblk,call_ft,RET);
412                 linked[call_ft->start()] = true;
413             }
414         }
415     }
416     // can't do this during iteration
417     if(link_entry)
418         o->add_edge(retblk,_entry,RET);
419 }
420
421 void
422 Function::add_block(Block *b)
423 {
424   ++b->_func_cnt;            // block counts references
425   _bmap[b->start()] = b;
426 }
427
428 const string &
429 Function::name() 
430 {
431     return _name;
432 }
433
434 bool
435 Function::contains(Block *b)
436 {
437     if(!_cache_valid)
438         finalize();
439
440     return HASHDEF(_bmap,b->start());
441 }
442
443 void Function::setEntryBlock(Block *new_entry)
444 {
445     obj()->parser->move_func(this, new_entry->start(), new_entry->region());
446     _region = new_entry->region();
447     _start = new_entry->start();
448     _entry = new_entry;
449 }
450
451 void Function::set_retstatus(FuncReturnStatus rs) 
452 {
453     // If we are changing the return status, update prev counter
454     if (_rs != UNSET) {
455         if (_rs == NORETURN) {
456             _obj->cs()->decrementCounter(PARSE_NORETURN_COUNT);
457         } else if (_rs == RETURN) {
458             _obj->cs()->decrementCounter(PARSE_RETURN_COUNT);
459         } else if (_rs == UNKNOWN) {
460             _obj->cs()->decrementCounter(PARSE_UNKNOWN_COUNT);
461         }
462     }
463
464     // Update counter information
465     if (rs == NORETURN) {
466         _obj->cs()->incrementCounter(PARSE_NORETURN_COUNT);
467     } else if (rs == RETURN) {
468         _obj->cs()->incrementCounter(PARSE_RETURN_COUNT);
469     } else if (rs == UNKNOWN) {
470         _obj->cs()->incrementCounter(PARSE_UNKNOWN_COUNT);
471     }
472     _rs = rs;
473 }
474
475 void 
476 Function::removeBlock(Block* dead)
477 {
478     _cache_valid = false;
479     // specify replacement entry prior to deleting entry block, unless 
480     // deleting all blocks
481     if (dead == _entry) {
482         mal_printf("Warning: removing entry block [%lx %lx) for function at "
483                    "%lx\n", dead->start(), dead->end(), addr());
484         _entry = NULL;
485         assert(0);
486     }
487
488     // remove dead block from _retBL and _call_edge_list
489     const Block::edgelist & outs = dead->targets();
490     for (Block::edgelist::const_iterator oit = outs.begin();
491          outs.end() != oit; 
492          oit++ ) 
493     {
494         switch((*oit)->type()) {
495             case CALL: {
496                 bool foundEdge = false;
497                 for (set<Edge*>::iterator cit = _call_edge_list.begin();
498                      _call_edge_list.end() != cit;
499                      cit++) 
500                 {
501                     if (*oit == *cit) {
502                         foundEdge = true;
503                         _call_edge_list.erase(cit);
504                         break;
505                     }
506                 }
507                 assert(foundEdge || (*oit)->sinkEdge());
508                 break;
509             }
510             case RET:
511               _retBL.erase(dead->start());
512               break;
513             default:
514                 break;
515         }
516     }
517     // remove dead block from block map
518     _bmap.erase(dead->start());
519     _exitBL.erase(dead->start());
520 }
521
522 class ST_Predicates : public Slicer::Predicates {};
523
524 StackTamper 
525 Function::tampersStack(bool recalculate)
526 {
527     using namespace SymbolicEvaluation;
528     using namespace InstructionAPI;
529
530     if ( ! obj()->defensiveMode() ) { 
531         assert(0);
532         _tamper = TAMPER_NONE;
533         return _tamper;
534     }
535     // this is above the cond'n below b/c it finalizes the function, 
536     // which could in turn call this function
537     Function::const_blocklist retblks(returnBlocks());
538     if ( retblks.begin() == retblks.end() ) {
539         _tamper = TAMPER_NONE;
540         return _tamper;
541     }
542         // The following line leads to dangling pointers, but leaving
543         // in until we understand why it was originally there.
544         //_cache_valid = false;
545
546     // if we want to re-calculate the tamper address
547     if (!recalculate && TAMPER_UNSET != _tamper) {
548         return _tamper;
549     }
550         assert(_cache_valid);
551     AssignmentConverter converter(true);
552     vector<Assignment::Ptr> assgns;
553     ST_Predicates preds;
554     _tamper = TAMPER_UNSET;
555     for (auto bit = retblks.begin(); retblks.end() != bit; ++bit) {
556                 assert(_cache_valid);
557         Address retnAddr = (*bit)->lastInsnAddr();
558         InstructionDecoder retdec(this->isrc()->getPtrToInstruction(retnAddr), 
559                                   InstructionDecoder::maxInstructionLength, 
560                                   this->region()->getArch() );
561         Instruction::Ptr retn = retdec.decode();
562         converter.convert(retn, retnAddr, this, *bit, assgns);
563         vector<Assignment::Ptr>::iterator ait;
564         AST::Ptr sliceAtRet;
565
566         for (ait = assgns.begin(); assgns.end() != ait; ait++) {
567             AbsRegion & outReg = (*ait)->out();
568             if ( outReg.absloc().isPC() ) {
569                 // First check to see if an input is an unresolved stack slot 
570                 // (or worse, the heap) - since if that's the case there's no use
571                 // in spending a lot of time slicing.
572                 std::vector<AbsRegion>::const_iterator in_iter;
573                 for (in_iter = (*ait)->inputs().begin();
574                     in_iter != (*ait)->inputs().end(); ++in_iter) {
575                     if (in_iter->type() != Absloc::Unknown) {
576                         _tamper = TAMPER_NONZERO;
577                         _tamper_addr = 0;
578                         set_retstatus(NORETURN);
579                         mal_printf("Stack tamper analysis for ret block at "
580                                "%lx found unresolved stack slot or heap "
581                                "addr, marking as TAMPER_NONZERO\n", retnAddr);
582                         return _tamper;
583                     }
584                 }
585
586                 Slicer slicer(*ait,*bit,this);
587                 Graph::Ptr slGraph = slicer.backwardSlice(preds);
588                 DataflowAPI::Result_t slRes;
589                 DataflowAPI::SymEval::expand(slGraph,slRes);
590                 sliceAtRet = slRes[*ait];
591                 if (dyn_debug_malware && sliceAtRet != NULL) {
592                     cerr << "assignment " << (*ait)->format() << " is "
593                          << sliceAtRet->format() << "\n";
594                 }
595                 break;
596             }
597         }
598         if (sliceAtRet == NULL) {
599             mal_printf("Failed to produce a slice for retn at %x %s[%d]\n",
600                        retnAddr, FILE__,__LINE__);
601             continue;
602         } 
603         StackTamperVisitor vis(Absloc(-1 * isrc()->getAddressWidth(), 0, this));
604         Address curTamperAddr=0;
605         StackTamper curtamper = vis.tampersStack(sliceAtRet, curTamperAddr);
606         mal_printf("StackTamperVisitor for func at 0x%lx block[%lx %lx) w/ "
607                    "lastInsn at 0x%lx returns tamper=%d tamperAddr=0x%lx\n",
608                    _start, (*bit)->start(), (*bit)->end(), retnAddr, 
609                    curtamper, curTamperAddr);
610         if (TAMPER_UNSET == _tamper || TAMPER_NONE == _tamper ||
611             (TAMPER_NONZERO == _tamper && 
612              TAMPER_NONE != curtamper))
613         {
614             _tamper = curtamper;
615             _tamper_addr = curTamperAddr;
616         } 
617         else if ((TAMPER_REL == _tamper   || TAMPER_ABS == _tamper) &&
618                  (TAMPER_REL == curtamper || TAMPER_ABS == curtamper))
619         {
620             if (_tamper != curtamper || _tamper_addr != curTamperAddr) {
621                 fprintf(stderr, "WARNING! Unhandled case in stackTamper "
622                         "analysis, func at %lx has distinct tamperAddrs "
623                         "%d:%lx %d:%lx at different return instructions, "
624                         "setting to TAMPER_NONZERO %s[%d]\n", 
625                         this->addr(), _tamper,_tamper_addr, curtamper, 
626                         curTamperAddr, FILE__, __LINE__);
627                 _tamper = TAMPER_NONZERO; // let instrumentation take care of it
628             }
629         }
630         assgns.clear();
631     }
632
633     if ( TAMPER_UNSET == _tamper ) {
634         mal_printf("WARNING: we found no valid slices for function at %lx "
635                    "%s[%d]\n", _start, _tamper_addr, FILE__,__LINE__);
636         _tamper = TAMPER_NONZERO;
637     }
638
639     if ( TAMPER_NONE != _tamper && TAMPER_REL != _tamper && RETURN == _rs ) {
640         set_retstatus(NORETURN);
641     }
642     return _tamper;
643 }
644
645 void Function::destroy(Function *f) {
646    f->obj()->destroy(f);
647 }
648
649 LoopTreeNode* Function::getLoopTree() {
650   if (_loop_root == NULL) {
651       LoopAnalyzer la(this);
652       la.createLoopHierarchy();
653   }
654   return _loop_root;
655 }
656
657 // this methods returns the loop objects that exist in the control flow
658 // grap. It returns a set. And if there are no loops, then it returns the empty
659 // set. not NULL.
660 void Function::getLoopsByNestingLevel(vector<Loop*>& lbb,
661                                               bool outerMostOnly)
662 {
663   if (_loop_analyzed == false) {
664       LoopAnalyzer la(this);
665       la.analyzeLoops();
666       _loop_analyzed = true;
667   }
668
669   for (std::set<Loop *>::iterator iter = _loops.begin();
670        iter != _loops.end(); ++iter) {
671      // if we are only getting the outermost loops
672      if (outerMostOnly && 
673          (*iter)->parent != NULL) continue;
674
675      lbb.push_back(*iter);
676   }
677   return;
678 }
679
680
681 // get all the loops in this flow graph
682 bool
683 Function::getLoops(vector<Loop*>& lbb)
684 {
685   getLoopsByNestingLevel(lbb, false);
686   return true;
687 }
688
689 // get the outermost loops in this flow graph
690 bool
691 Function::getOuterLoops(vector<Loop*>& lbb)
692 {
693   getLoopsByNestingLevel(lbb, true);
694   return true;
695 }
696
697 Loop *Function::findLoop(const char *name)
698 {
699   return getLoopTree()->findLoop(name);
700 }
701
702
703 //this method fill the dominator information of each basic block
704 //looking at the control flow edges. It uses a fixed point calculation
705 //to find the immediate dominator of the basic blocks and the set of
706 //basic blocks that are immediately dominated by this one.
707 //Before calling this method all the dominator information
708 //is going to give incorrect results. So first this function must
709 //be called to process dominator related fields and methods.
710 void Function::fillDominatorInfo()
711 {
712     if (!isDominatorInfoReady) {
713         dominatorCFG domcfg(this);
714         domcfg.calcDominators();
715         isDominatorInfoReady = true;
716     }
717 }
718
719 void Function::fillPostDominatorInfo()
720 {
721     if (!isPostDominatorInfoReady) {
722         dominatorCFG domcfg(this);
723         domcfg.calcPostDominators();
724         isPostDominatorInfoReady = true;
725     }
726 }
727
728 bool Function::dominates(Block* A, Block *B) {
729     if (A == NULL || B == NULL) return false;
730     if (A == B) return true;
731
732     fillDominatorInfo();
733
734     if (!immediateDominates[A]) return false;
735
736     for (auto bit = immediateDominates[A]->begin(); bit != immediateDominates[A]->end(); ++bit)
737         if (dominates(*bit, B)) return true;
738     return false;
739 }
740         
741 Block* Function::getImmediateDominator(Block *A) {
742     fillDominatorInfo();
743     return immediateDominator[A];
744 }
745
746 void Function::getImmediateDominates(Block *A, set<Block*> &imd) {
747     fillDominatorInfo();
748     if (immediateDominates[A] != NULL)
749         imd.insert(immediateDominates[A]->begin(), immediateDominates[A]->end());
750 }
751
752 void Function::getAllDominates(Block *A, set<Block*> &d) {
753     fillDominatorInfo();
754     d.insert(A);
755     if (immediateDominates[A] == NULL) return;
756
757     for (auto bit = immediateDominates[A]->begin(); bit != immediateDominates[A]->end(); ++bit)
758         getAllDominates(*bit, d);
759 }
760
761 bool Function::postDominates(Block* A, Block *B) {
762     if (A == NULL || B == NULL) return false;
763     if (A == B) return true;
764
765     fillPostDominatorInfo();
766
767     if (!immediatePostDominates[A]) return false;
768
769     for (auto bit = immediatePostDominates[A]->begin(); bit != immediatePostDominates[A]->end(); ++bit)
770         if (postDominates(*bit, B)) return true;
771     return false;
772 }
773         
774 Block* Function::getImmediatePostDominator(Block *A) {
775     fillPostDominatorInfo();
776     return immediatePostDominator[A];
777 }
778
779 void Function::getImmediatePostDominates(Block *A, set<Block*> &imd) {
780     fillPostDominatorInfo();
781     if (immediatePostDominates[A] != NULL)
782         imd.insert(immediatePostDominates[A]->begin(), immediatePostDominates[A]->end());
783 }
784
785 void Function::getAllPostDominates(Block *A, set<Block*> &d) {
786     fillPostDominatorInfo();
787     d.insert(A);
788     if (immediatePostDominates[A] == NULL) return;
789
790     for (auto bit = immediatePostDominates[A]->begin(); bit != immediatePostDominates[A]->end(); ++bit)
791         getAllPostDominates(*bit, d);
792 }