Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / BPatch_flowGraph.C
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 #define BPATCH_FILE
33
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <assert.h>
37 #include <string.h>
38 #include <string>
39
40 #include "common/h/Types.h"
41 #include "common/h/Vector.h"
42 #include "common/h/Dictionary.h"
43 #include "common/h/Pair.h"
44
45 #include "BPatch_process.h"
46 #include "BPatch_edge.h"
47
48 #include "util.h"
49 #include "process.h"
50 #include "symtab.h"
51 #include "instPoint.h"
52
53 #if defined(cap_instruction_api)
54 #include "Instruction.h"
55 #else
56 #include "InstrucIter.h"
57 #endif
58
59 #include "BPatch_statement.h"
60
61 #include "BPatch_flowGraph.h"
62 #include "mapped_object.h"
63 #include "dominator.h"
64 #include "function.h"
65
66 // constructor of the class. It creates the CFG and
67 // deletes the unreachable code.
68 BPatch_flowGraph::BPatch_flowGraph(BPatch_function *func, 
69                                    bool &valid)
70     : func_(func), addSpace(func->getAddSpace()), mod(func->getModule()), 
71       loops(NULL), loopRoot(NULL), isDominatorInfoReady(false), 
72       isPostDominatorInfoReady(false), isSourceBlockInfoReady(false) 
73 {
74    // fill the information of the basic blocks after creating
75    // them. The dominator information will also be filled
76    valid = true;
77
78    unsigned tmpSize = func->getSize();
79    if(!tmpSize){
80       fprintf(stderr, "Func has no size!\n");
81       valid = false;
82       return;
83    }
84
85    if (!createBasicBlocks()) {
86       fprintf(stderr, "Failed to make basic blocks!\n");
87       valid = false;
88       return;
89    }
90 }
91
92 bool DEBUG_LOOP = false;
93
94 void 
95 BPatch_flowGraph::findLoopExitInstPoints(BPatch_loop *loop,
96                                          BPatch_Vector<BPatch_point*> *points)
97 {
98     BPatch_Vector<BPatch_basicBlock*> blocks;
99     loop->getLoopBasicBlocks(blocks);
100     
101     // for each block in this loop (including its subloops)
102     for (unsigned i = 0; i < blocks.size(); i++) {
103         BPatch_Vector<BPatch_edge*> edges;
104         blocks[i]->getOutgoingEdges(edges);
105         
106         // for each of its outgoing edges, if the edge's target is
107         // outside this loop then this edge exits this loop
108         for (unsigned j = 0; j < edges.size(); j++) 
109             if (!loop->hasBlock(edges[j]->target)) {
110                 if (DEBUG_LOOP) edges[j]->dump();
111                 BPatch_point *bP = edges[j]->getPoint();
112                 if (!bP) {
113                     fprintf(stderr, "ERROR: exit edge had no inst point\n");
114                 }
115                 else {
116                     bP->overrideType(BPatch_locLoopExit);
117                     bP->setLoop(loop);
118                     points->push_back(bP);
119                 }
120                 
121             }
122     }
123 }
124
125 BPatch_Vector<BPatch_point*> *
126 BPatch_flowGraph::findLoopInstPointsInt(const BPatch_procedureLocation loc, 
127                                      BPatch_loop *loop)
128 {
129     /*
130      * We need to detect and handle following cases:
131      * 
132      * (1) If a loop has no entry edge, e.g. the loop head is also
133      * first basic block of the function, we need to create a loop
134      * preheader.  we probably want to relocate the function at this
135      * point.
136      * 
137      *        ___   
138      *       v   |
139      *   f: [_]--/
140      *       |
141      *      [ ]
142      *
143      *
144      * (2) If a loop header is shared between two loops then add a new
145      * nop node N, redirect the back edge of each loop to N and make N
146      * jump to the header. this transforms the two loops into a single
147      * loop.
148      * 
149      *      _              _
150      * --->[_]<---        [_]<---
151      * |  _/ \_  |       _/ \_  |
152      * \-[_] [_]-/      [_] [_] |
153      *                    \_/   |
154      *                    [N]---/
155      *
156      *
157      *  Also, loop instrumentation works on the control flow as it was
158      *  _originally_ parsed. Function entry/exit instrumentation may
159      *  have modified the this control flow, but this new
160      *  instrumentation is not cognizant of these modifications. This
161      *  instrumentation therefore may clobber any instrumentation that
162      *  was added because it has an inaccurate view of the binary.
163      *
164      */
165
166     if (DEBUG_LOOP) 
167         fprintf(stderr,"%s findLoopInstPoints 0x%p\n",
168                 ll_func()->prettyName().c_str(), loop);
169
170     BPatch_Vector<BPatch_point*> *points = new BPatch_Vector<BPatch_point *>;
171
172     switch (loc) {
173
174     case BPatch_locLoopEntry: {
175         if (DEBUG_LOOP) fprintf(stderr,"loop entry\n");
176
177         // return inst points for each edge e where e's target is this
178         // loop's head and e's source is not a block in this loop or
179         // its subloops. we assume a natural loop, that the loop is
180         // always entered through the head
181         BPatch_Vector<BPatch_edge*> edges;
182         loop->getLoopHead()->getIncomingEdges(edges);
183         for (unsigned i = 0; i < edges.size(); i++) {
184             // hasBlock is inclusive, checks subloops
185             if (!loop->hasBlock(edges[i]->source)) {
186                 if (DEBUG_LOOP) edges[i]->dump();
187                 BPatch_point *iP = edges[i]->getPoint();
188                 if (!iP) {
189                   fprintf(stderr, "ERROR: failed to find loop entry point!\n");
190                 } 
191                 else {
192                    iP->overrideType(BPatch_locLoopEntry);
193                    iP->setLoop(loop);
194                    points->push_back(iP);
195                 }
196             }
197         }
198
199         if (0 == points->size()) {
200             fprintf(stderr,"Warning: request to instrument loop entry "
201                     "of a loop w/o an entry edge.");
202         }
203
204         break;        
205     }
206
207     case BPatch_locLoopExit: {
208         if (DEBUG_LOOP) fprintf(stderr,"loop exit\n");
209
210         // return inst points for all edges e such that e->source is a
211         // member of this loop (including subloops) and e->target is
212         // not a member of this loop (including its subloops)
213         findLoopExitInstPoints(loop, points);
214         if (!points->size())
215           fprintf(stderr, "ERROR: failed to find loop exit points!\n");
216
217         break;
218     }
219
220     case BPatch_locLoopStartIter: {
221         if (DEBUG_LOOP) fprintf(stderr,"loop start iter\n");
222
223         // instrument the head of the loop
224         BPatch_point *p;
225         void *addr = (void*)loop->getLoopHead()->getStartAddress();
226         p = BPatch_point::createInstructionInstPoint(getAddSpace(), addr, func_);
227         p->overrideType(BPatch_locLoopStartIter);
228         p->setLoop(loop);
229         points->push_back(p);
230
231         break;
232     }
233
234     case BPatch_locLoopEndIter: {
235         if (DEBUG_LOOP) fprintf(stderr,"loop end iter\n");
236
237         // point for the backedge of this loop 
238         BPatch_edge *edge = loop->backEdge;
239         if (DEBUG_LOOP) edge->dump();
240         BPatch_point *iP = edge->getPoint();
241         iP->overrideType(BPatch_locLoopEndIter);
242         iP->setLoop(loop);
243         points->push_back(iP);
244
245         // and all edges which exit the loop
246         findLoopExitInstPoints(loop, points);
247
248         break;
249     }
250
251     default: {
252         bperr("called findLoopInstPoints with non-loop location\n");
253         assert(0);
254     }
255
256     }
257
258     return points;
259 }
260
261 void BPatch_flowGraph::BPatch_flowGraph_dtor()
262 {
263     unsigned int i;
264
265     if (loops) {
266       BPatch_loop **lelements = new BPatch_loop *[loops->size()];
267       
268       loops->elements(lelements);
269       
270       for (i=0; i < loops->size(); i++)
271          delete lelements [i];
272       
273       delete[] lelements;
274       delete loops;
275     }
276    
277    BPatch_basicBlock **belements = new BPatch_basicBlock *[allBlocks.size()];
278    
279    allBlocks.elements (belements);
280    
281    for (i=0; i < allBlocks.size(); i++)
282       delete belements [i];
283    
284    delete[] belements;
285
286    delete loopRoot;
287    func_->cfg = NULL;
288 }
289
290 bool
291 BPatch_flowGraph::getAllBasicBlocksInt(BPatch_Set<BPatch_basicBlock*>& abb)
292 {
293    BPatch_basicBlock** belements =
294       new BPatch_basicBlock* [allBlocks.size()];
295    
296    allBlocks.elements(belements);
297    
298    for (unsigned int i=0;i<allBlocks.size(); i++)
299       abb += belements[i];
300    
301    delete[] belements;
302    return true;
303 }
304
305 bool
306 BPatch_flowGraph::getAllBasicBlocksSTL(std::set<BPatch_basicBlock*>& abb)
307 {
308    BPatch_basicBlock** belements =
309       new BPatch_basicBlock* [allBlocks.size()];
310    
311    allBlocks.elements(belements);
312    
313    for (unsigned int i=0;i<allBlocks.size(); i++)
314        abb.insert(belements[i]);
315    
316    delete[] belements;
317    return true;
318 }
319
320
321
322 // this is the method that returns the set of entry points
323 // basic blocks, to the control flow graph. Actually, there must be
324 // only one entry point to each control flow graph but the definition
325 // given API specifications say there might be more.
326 bool
327 BPatch_flowGraph::getEntryBasicBlockInt(BPatch_Vector<BPatch_basicBlock*>& ebb) 
328 {
329    BPatch_basicBlock *bb;
330    int_function *func = ll_func();
331    for (unsigned i=0; i<func->blocks().size(); i++)
332    {
333       if (func->blocks()[i]->isEntryBlock())
334       {
335          bb = (BPatch_basicBlock *) func->blocks()[i]->getHighLevelBlock();
336          ebb.push_back(bb);
337       }
338    }
339    return true;
340 }
341
342 // this method returns the set of basic blocks that are the
343 // exit basic blocks from the control flow graph. That is those
344 // are the basic blocks that contains the instruction for
345 // returning from the function
346 bool 
347 BPatch_flowGraph::getExitBasicBlockInt(BPatch_Vector<BPatch_basicBlock*>& nbb)
348 {
349    BPatch_basicBlock *bb;
350    int_function *func = ll_func();
351    for (unsigned i=0; i<func->blocks().size(); i++)
352    {
353       if (func->blocks()[i]->isExitBlock())
354       {
355          bb = (BPatch_basicBlock *) func->blocks()[i]->getHighLevelBlock();
356          nbb.push_back(bb);
357       }
358    }
359    return true;
360 }
361
362
363 void 
364 BPatch_flowGraph::createLoops()
365 {
366     loops = new BPatch_Set<BPatch_loop*>;
367     
368     BPatch_edge **allBackEdges = new BPatch_edge*[backEdges.size()];
369     backEdges.elements(allBackEdges);
370
371     // for each back edge
372     unsigned i;
373     for (i = 0; i < backEdges.size(); i++) {
374         assert(allBackEdges[i] != NULL);
375         BPatch_loop *loop = new BPatch_loop(allBackEdges[i], this);
376             
377         // find all basic blocks in the loop and keep a map used
378         // to find the nest structure 
379         findBBForBackEdge(allBackEdges[i], loop->basicBlocks);
380
381         (*loops) += loop;
382     }
383
384     delete[] allBackEdges;
385
386     BPatch_loop **allLoops = new BPatch_loop*[loops->size()];
387     loops->elements(allLoops);
388     
389     // for each pair of loops l1,l2
390     for (i = 0; i < loops->size(); i++) {
391         for (unsigned j=0; j < loops->size(); j++) {
392             if (i==j) continue;
393             
394             BPatch_loop *l1 = allLoops[i];
395             BPatch_loop *l2 = allLoops[j];
396
397             // Note that address ranges (as were previously used here)
398             // between the target of the back edge and the last instruction
399             // of the source of the back edge are insufficient to determine
400             // whether a block lies within a loop, given all possible
401             // layouts of loops in the address space. Instead, check
402             // for set membership. 
403             //
404             // If loop A contains both the head block and the source
405             // of the back edge of loop B, it contains loop B (for
406             // nested natural loops)
407             if(l1->hasBlock(l2->getLoopHead()) &&
408                l1->hasBlock(l2->getBackEdge()->source))
409             {
410                 // l1 contains l2
411                 l1->containedLoops += l2;
412
413                 // l2 has no parent, l1 is best so far
414                 if(!l2->parent) 
415                 {
416                     l2->parent = l1;
417                 }
418                 else
419                 {
420                    // if l1 is closer to l2 than l2's existing parent
421                     if(l2->parent->hasBlock(l1->getLoopHead()) &&
422                        l2->parent->hasBlock(l1->getBackEdge()->source))
423                     {
424                         l2->parent = l1;
425                     }
426                 }
427             }
428         }
429     }
430     
431     delete[] allLoops;
432 }
433
434 // this methods returns the loop objects that exist in the control flow
435 // grap. It returns a set. And if there are no loops, then it returns the empty
436 // set. not NULL. 
437 void BPatch_flowGraph::getLoopsByNestingLevel(BPatch_Vector<BPatch_loop*>& lbb,
438                                               bool outerMostOnly)
439 {
440    if (!loops) {
441       fillDominatorInfo();
442       createBackEdges();
443       createLoops();
444    }
445     
446    BPatch_loop **lelements = new BPatch_loop* [loops->size()];
447    
448    loops->elements(lelements);
449    
450    for (unsigned i=0; i < loops->size(); i++)
451    {
452       // if we are only getting the outermost loops
453       if (outerMostOnly) {
454          // if this loop has no parent then it is outermost
455          if (NULL == lelements[i]->parent) {
456             lbb.push_back(lelements[i]);
457          }
458       }
459       else {
460          lbb.push_back(lelements[i]);
461       }
462    }
463    delete[] lelements;
464    return;
465 }
466
467
468 // get all the loops in this flow graph
469 bool 
470 BPatch_flowGraph::getLoopsInt(BPatch_Vector<BPatch_basicBlockLoop*>& lbb)
471 {
472     getLoopsByNestingLevel(lbb, false);
473     return true;
474 }
475
476 // get the outermost loops in this flow graph
477 bool 
478 BPatch_flowGraph::getOuterLoopsInt(BPatch_Vector<BPatch_basicBlockLoop*>& lbb)
479 {
480     getLoopsByNestingLevel(lbb, true);
481     return true;
482 }
483
484
485 //this is the main method to create the basic blocks and the
486 //the edges between basic blocks. The assumption of the
487 //method is as follows: It assumes existence of four machine dependent
488 //functions as given in InstrucIter.h.
489 //after finding the leaders, for each leader a basic block is created and
490 //then the predecessors and successors of the basic blocks are inserted
491 //to the basic blocks by passing from the function address space again, one
492 //instruction at a time, and using maps from basic blocks to leaders, and
493 //leaders to basic blocks. 
494 //The basic block of which the
495 //leader is the start address of the function is assumed to be the entry block
496 //to control flow graph. This makes only one basic block to be in the
497 //entryBlocks field of the controlflow grpah. If it is possible
498 //to enter a function from many points some modification is needed
499 //to insert all entry basic blocks to the esrelevant field of the class.
500 bool BPatch_flowGraph::createBasicBlocks()
501
502     assert(ll_func());
503     // create blocks from int_basicBlocks
504     const std::vector< int_basicBlock* > &iblocks       = ll_func()->blocks();
505     for( unsigned int i = 0; i < iblocks.size(); i++ )
506     {
507        BPatch_basicBlock *newblock = new BPatch_basicBlock(iblocks[i], this);
508        allBlocks += newblock;
509     }
510
511     // create edges from target & source block lists in int_basicBlock
512     BPatch_Set<BPatch_basicBlock*, BPatch_basicBlock::compare>::iterator 
513         bIter = allBlocks.begin();
514     while(bIter != allBlocks.end()) {
515         pdvector<int_basicBlock *> sourceBlocks, targetBlocks; 
516         (*bIter)->lowlevel_block()->getSources(sourceBlocks);
517         (*bIter)->lowlevel_block()->getTargets(targetBlocks);
518         for (unsigned sidx =0; sidx < sourceBlocks.size(); sidx++) {
519             (*bIter)->incomingEdges.insert
520                 (new BPatch_edge((BPatch_basicBlock*)
521                                  (sourceBlocks[sidx]->getHighLevelBlock()), 
522                                  *bIter, this));
523         }
524         for (unsigned tidx =0; tidx < targetBlocks.size(); tidx++) {
525             (*bIter)->outgoingEdges.insert
526                 (new BPatch_edge(*bIter, (BPatch_basicBlock*)
527                                  (targetBlocks[tidx]->getHighLevelBlock()), this));
528         }
529         bIter++;
530     }
531
532     return true;
533 }
534
535
536 // This function must be called only after basic blocks have been created
537 // by calling createBasicBlocks. It computes the source block for each
538 // basic block. For now, a source block is represented by the starting
539 // and ending line numbers in the source block for the basic block.
540
541 bool BPatch_flowGraph::createSourceBlocksInt() {
542     if( isSourceBlockInfoReady ) { return true; }
543     
544     /* Iterate over every basic block, looking for the lines corresponding to the
545        addresses it contains. */
546     BPatch_basicBlock ** elements = new BPatch_basicBlock * [ allBlocks.size() ];
547     allBlocks.elements( elements );
548     
549     for( unsigned int i = 0; i < allBlocks.size(); i++ ) {
550         BPatch_basicBlock * currentBlock = elements[i];
551         
552         BPatch_Vector<BPatch_statement> lines;
553 #if defined(cap_instruction_api)
554         using namespace Dyninst::InstructionAPI;
555         std::vector<std::pair< Instruction::Ptr, Address > > insnsByAddr;
556         currentBlock->getInstructions(insnsByAddr);
557         for(std::vector<std::pair< Instruction::Ptr, Address > >::const_iterator cur = insnsByAddr.begin();
558             cur != insnsByAddr.end();
559            ++cur)
560         {
561             if( getAddSpace()->getSourceLines(cur->second, lines ) ) {
562                 // /* DEBUG */ fprintf( stderr, "%s[%d]: 0x%lx\n", __FILE__, __LINE__, cur->second );
563             }
564         }
565 #else
566         InstrucIter insnIterator( currentBlock );
567         
568         for( ; insnIterator.hasMore(); ++insnIterator ) {
569             if( getAddSpace()->getSourceLines( * insnIterator, lines ) ) {
570                 // /* DEBUG */ fprintf( stderr, "%s[%d]: 0x%lx\n", __FILE__, __LINE__, * insnIterator );
571             }
572         }
573 #endif        
574         if( lines.size() != 0 ) {
575             if( ! currentBlock->sourceBlocks ) {
576                 currentBlock->sourceBlocks = new BPatch_Vector< BPatch_sourceBlock * >();
577             }
578             
579             BPatch_Set< unsigned short > lineNos;
580             const char * currentSourceFile = lines[0].fileName();
581             for( unsigned int j = 0; j < lines.size(); j++ ) {
582                 if( strcmp( currentSourceFile, lines[j].fileName() ) == 0 ) {
583                     lineNos.insert( (unsigned short) lines[j].lineNumber() );
584                     continue;
585                 }
586                 
587                 // /* DEBUG */ fprintf( stderr, "%s[%d]: Inserting %s:", __FILE__, __LINE__, currentSourceFile );
588                 // /* DEBUG */ BPatch_Set< unsigned short >::iterator iter = lineNos.begin();
589                 // /* DEBUG */ for( ; iter != lineNos.end(); iter++ ) { fprintf( stderr, " %d", * iter ); }
590                 // /* DEBUG */ fprintf( stderr, "\n" );
591                 BPatch_sourceBlock * sourceBlock = new BPatch_sourceBlock( currentSourceFile, lineNos );
592                 currentBlock->sourceBlocks->push_back( sourceBlock );
593                 
594                 /* Wonder why there isn't a clear().  (For that matter, why there isn't a const_iterator
595                    or a prefix increment operator for the iterator.) */
596                 lineNos = BPatch_Set< unsigned short >();
597                 currentSourceFile = lines[j].fileName();
598                 lineNos.insert( (unsigned short)lines[j].lineNumber() );
599             }
600             if( lineNos.size() != 0 ) {
601                 // /* DEBUG */ fprintf( stderr, "%s[%d]: Inserting %s:", __FILE__, __LINE__, currentSourceFile );
602                 // /* DEBUG */ BPatch_Set< unsigned short >::iterator iter = lineNos.begin();
603                 // /* DEBUG */ for( ; iter != lineNos.end(); iter++ ) { fprintf( stderr, " %d", * iter ); }
604                 // /* DEBUG */ fprintf( stderr, "\n" );
605                 
606                 BPatch_sourceBlock * sourceBlock = new BPatch_sourceBlock( currentSourceFile, lineNos );
607                 currentBlock->sourceBlocks->push_back( sourceBlock );
608             }                           
609             
610         } /* end if we found anything */
611     } /* end iteration over all basic blocks */
612     
613     isSourceBlockInfoReady = true;    
614     delete [] elements;
615     return true;
616 } /* end createSourceBlocks() */
617
618 //this method fill the dominator information of each basic block
619 //looking at the control flow edges. It uses a fixed point calculation
620 //to find the immediate dominator of the basic blocks and the set of
621 //basic blocks that are immediately dominated by this one.
622 //Before calling this method all the dominator information
623 //is going to give incorrect results. So first this function must
624 //be called to process dominator related fields and methods.
625 void BPatch_flowGraph::fillDominatorInfoInt()
626 {
627   if(isDominatorInfoReady)
628     return;
629   isDominatorInfoReady = true;
630   
631   dominatorCFG domcfg(this);
632   domcfg.calcDominators();
633 }
634  
635 void BPatch_flowGraph::fillPostDominatorInfoInt()
636 {
637   if(isPostDominatorInfoReady)
638     return;
639   isPostDominatorInfoReady = true;
640   
641   dominatorCFG domcfg(this);
642   domcfg.calcPostDominators();
643 }
644
645 // Adds each back edge in the flow graph to the given set. A back edge
646 // in a flow graph is an edge whose head dominates its tail. 
647 void BPatch_flowGraph::createBackEdges()
648 {
649    /*
650     * Indirect jumps are NOT currently handled correctly
651     */
652    
653    BPatch_basicBlock **blks = new BPatch_basicBlock*[allBlocks.size()];
654    allBlocks.elements(blks);
655    
656    // for each block in the graph
657    for (unsigned i = 0; i < allBlocks.size(); i++) {
658       BPatch_basicBlock *source = blks[i];
659
660       BPatch_Vector<BPatch_edge *> outEdges;
661       blks[i]->getOutgoingEdges(outEdges);
662       unsigned numTargs = outEdges.size();
663
664       // create edges
665
666       Address lastinsnaddr = source->getLastInsnAddress();
667       if (lastinsnaddr == 0) {
668          fprintf(stderr, "ERROR: 0 addr for block end!\n");
669          continue;
670       }
671
672       if (numTargs == 1) {
673          //         BPatch_edge *edge = blks[i]->incomingEdges.find();
674          //         edge = new BPatch_edge(source, targs[0], this);
675
676          //         targs[0]->incomingEdges += edge;
677          //         source->outgoingEdges += edge;
678
679          //             fprintf(stderr, "t1 %2d %2d\n",source->blockNo(),
680          //                     targs[0]->blockNo());
681          if (outEdges[0]->getTarget()->dominates(source))
682             backEdges += outEdges[0];
683       }
684       else if (numTargs == 2) {
685          //XXX could be an indirect jump with two targets
686
687          // conditional jumps create two edges from a block
688          //         BPatch_edge *edge0 = 
689          //            new BPatch_edge(source, targs[0], this); 
690
691          //         BPatch_edge *edge1 = 
692          //            new BPatch_edge(source, targs[1], this); 
693
694          //             fprintf(stderr, "t2 %2d %2d\n",source->blockNo(),
695          //                     targs[0]->blockNo());
696          //         fprintf(stderr, "t2 %2d %2d\n",source->blockNo(),
697          //                     targs[1]->blockNo());
698
699          //         source->outgoingEdges += edge0;
700          //         source->outgoingEdges += edge1;
701
702          //         targs[0]->incomingEdges += edge0;
703          //         targs[1]->incomingEdges += edge1;
704
705          if (outEdges[0]->getTarget()->dominates(source))
706             backEdges += outEdges[0];
707
708          if (outEdges[1]->getTarget()->dominates(source))
709             backEdges += outEdges[1];
710
711          // taken and fall-through edge should not both be back edges
712          //         if (targs[0]->dominates(source) && targs[1]->dominates(source)) {
713          //                 bperr("Both edge targets can not dominate the source.\n");
714          //             edge0->dump();
715          //             edge1->dump();
716          //         }
717
718          //assert(!(targs[0]->dominates(source) && 
719          //targs[1]->dominates(source)));
720       }
721       else {
722          //XXX indirect jumps, set conditional buddy?
723         // 7 Dec 06, tugrul
724         // create edges for each target even if there are more than two
725         // the last instruction of this block is an indirect jump (such as a switch statement)
726         //      BPatch_edge *edge;
727         for(unsigned j=0; j<numTargs; j++) {
728           // create edge between source and this target
729           //      edge = new BPatch_edge(source, targs[j], this);
730           
731           //      targs[j]->incomingEdges += edge;
732           //      source->outgoingEdges += edge;
733
734           // update backEdges if target already dominates source
735           if (outEdges[j]->getTarget()->dominates(source))
736             backEdges += outEdges[j];
737         }
738       }
739    }
740    delete[] blks;
741 }
742
743 // this method is used to find the basic blocks contained by the loop
744 // defined by a backedge. The tail of the backedge is the starting point and
745 // the predecessors of the tail is inserted as a member of the loop.
746 // then the predecessors of the newly inserted blocks are also inserted
747 // until the head of the backedge is in the set(reached).
748
749 void BPatch_flowGraph::findBBForBackEdge(BPatch_edge* backEdge,
750                                          BPatch_Set<BPatch_basicBlock*>& bbSet)
751 {
752    typedef struct STACK {
753       unsigned size;
754       int top;
755       BPatch_basicBlock** data;
756         
757       STACK() : size(0),top(-1),data(NULL) {}
758       ~STACK() { free(data); }
759       bool empty() { return (top < 0); }
760       void push(BPatch_basicBlock* b) {
761          if (!size) 
762             data = (BPatch_basicBlock**) malloc( sizeof(BPatch_basicBlock*)*(++size));
763          else if(top == ((int)size-1))
764             data = (BPatch_basicBlock**)realloc( data,sizeof(BPatch_basicBlock*)*(++size));
765          top++;
766          data[top] = b;
767       }
768       BPatch_basicBlock* pop() {
769          if(empty()) return NULL;
770          return data[top--];
771       }
772    } STACK;
773     
774    STACK* stack = new STACK;
775    pdvector<int_basicBlock *> blocks;
776    BPatch_basicBlock *pred;
777
778    bbSet += backEdge->target;
779
780    if (!bbSet.contains(backEdge->source)) {
781       bbSet += backEdge->source;
782       stack->push(backEdge->source);
783    }
784
785    while (!stack->empty()) {
786       BPatch_basicBlock* bb = stack->pop();
787       
788       blocks.clear();
789       bb->iblock->getSources(blocks);
790       for (unsigned i=0; i<blocks.size(); i++)
791       {
792          pred = (BPatch_basicBlock*) blocks[i]->getHighLevelBlock();
793          if (!bbSet.contains(pred)) {
794             bbSet += pred;
795             stack->push(pred);
796          }
797       }
798    }
799    delete stack;
800 }
801
802
803
804 // return a pair of the min and max source lines for this loop
805    pdpair<u_short, u_short> 
806 getLoopMinMaxSourceLines(BPatch_loop * loop) 
807 {
808    BPatch_Vector<BPatch_basicBlock*> blocks;
809    loop->getLoopBasicBlocks(blocks);
810
811    BPatch_Vector<u_short> lines;
812
813    for (u_int j = 0; j < blocks.size (); j++) {
814       BPatch_Vector<BPatch_sourceBlock*> sourceBlocks;
815       blocks[j]->getSourceBlocks(sourceBlocks);
816
817       for (u_int k = 0; k < sourceBlocks.size (); k++) {
818          BPatch_Vector<u_short> sourceLines;
819          sourceBlocks[k]->getSourceLines(sourceLines);
820          for (u_int l = 0; l < sourceLines.size(); l++) 
821             lines.push_back(sourceLines[l]);
822       }
823    }
824
825    pdpair<u_short, u_short> mm = min_max_pdpair<u_short>(lines);
826    return mm;
827 }
828
829
830 // sort blocks by address ascending
831 void bsort_loops_addr_asc(BPatch_Vector<BPatch_loop*> &v) 
832 {
833    if (v.size()==0) return;
834    for (unsigned i=0; i < v.size()-1; i++) 
835       for (unsigned j=0; j < v.size()-1-i; j++)
836          if (v[j+1]->getLoopHead()->getStartAddress() 
837                < v[j]->getLoopHead()->getStartAddress()) {    
838             BPatch_loop *tmp = v[j]; 
839             v[j] = v[j+1];
840             v[j+1] = tmp;
841          }
842 }
843
844
845 void dfsCreateLoopHierarchy(BPatch_loopTreeNode * parent,
846       BPatch_Vector<BPatch_loop *> &loops, 
847       std::string level)
848 {
849    for (unsigned int i = 0; i < loops.size (); i++) {
850       // loop name is hierarchical level
851       std::string clevel = (level != "") 
852          ? level + "." + utos(i+1)
853          : utos(i+1);
854
855       // add new tree nodes to parent
856       BPatch_loopTreeNode * child = 
857          new BPatch_loopTreeNode(loops[i],
858                (std::string("loop_"+clevel)).c_str());
859
860       parent->children.push_back(child);
861
862       // recurse with this child's outer loops
863       BPatch_Vector<BPatch_loop*> outerLoops;
864       loops[i]->getOuterLoops(outerLoops);
865       bsort_loops_addr_asc(outerLoops);
866
867       dfsCreateLoopHierarchy(child, outerLoops, clevel);
868    }
869 }
870
871
872 void BPatch_flowGraph::createLoopHierarchy()
873 {
874    loopRoot = new BPatch_loopTreeNode(NULL, NULL);
875
876    BPatch_Vector<BPatch_loop *> outerLoops;
877    getOuterLoops(outerLoops);
878
879    bsort_loops_addr_asc(outerLoops);
880
881    dfsCreateLoopHierarchy(loopRoot, outerLoops, "");
882
883    //Callees
884    {
885      const pdvector<instPoint*> &instPs = ll_func()->funcCalls();
886      for (unsigned i = 0; i < instPs.size(); i++) {
887        int_function *f = instPs[i]->findCallee();
888        if (f != NULL) 
889          insertCalleeIntoLoopHierarchy(f, instPs[i]->addr());
890      }
891    }
892
893    //Entry points
894    {
895      const pdvector<instPoint*> &instPs = ll_func()->funcEntries();
896      for (unsigned i = 0; i < instPs.size(); i++) {
897        int_function *f = instPs[i]->findCallee();
898        if (f != NULL) 
899          insertCalleeIntoLoopHierarchy(f, instPs[i]->addr());
900      }
901    }
902
903    //Exit points
904    {
905      const pdvector<instPoint*> &instPs = ll_func()->funcExits();
906      for (unsigned i = 0; i < instPs.size(); i++) {
907        int_function *f = instPs[i]->findCallee();
908        if (f != NULL) 
909          insertCalleeIntoLoopHierarchy(f, instPs[i]->addr());
910      }
911    }
912 }
913
914
915 // try to insert func into the appropriate spot in the loop tree based on
916 // address ranges. if succesful return true, return false otherwise.
917 bool BPatch_flowGraph::dfsInsertCalleeIntoLoopHierarchy(BPatch_loopTreeNode *node, 
918       int_function *callee,
919       unsigned long addr)
920 {
921    // if this node contains func then insert it
922    if ((node->loop != NULL) && node->loop->containsAddress(addr)) {
923       node->callees.push_back(callee);
924       return true;
925    }
926
927    // otherwise recur with each of node's children
928    bool success = false;
929
930    for (unsigned int i = 0; i < node->children.size(); i++) 
931       success = success || 
932          dfsInsertCalleeIntoLoopHierarchy(node->children[i], callee, addr);
933
934    return success;
935 }
936
937
938 void BPatch_flowGraph::insertCalleeIntoLoopHierarchy(int_function *callee,
939       unsigned long addr)
940 {
941    // try to insert func into the loop hierarchy
942    bool success = dfsInsertCalleeIntoLoopHierarchy(loopRoot, callee, addr);
943
944    // if its not in a loop make it a child of the root
945    if (!success) {
946       loopRoot->callees.push_back(callee);
947    }
948 }
949
950
951 BPatch_loopTreeNode *BPatch_flowGraph::getLoopTreeInt() 
952
953    if (loopRoot == NULL) 
954       createLoopHierarchy();
955    return loopRoot; 
956 }
957
958
959 BPatch_loop *BPatch_flowGraph::findLoopInt(const char *name) 
960
961    return getLoopTree()->findLoop(name);
962 }
963
964
965 void BPatch_flowGraph::dfsPrintLoops(BPatch_loopTreeNode *n) 
966 {
967    if (n->loop != NULL) {
968       //    pdpair<u_short, u_short> mm = getLoopMinMaxSourceLines(n->loop);
969       //  printf("%s (source %d-%d)\n", n->name(), mm.first, mm.second);
970
971       printf("%s %s\n", n->name(),ll_func()->prettyName().c_str());
972    }
973
974    for (unsigned i = 0; i < n->children.size(); i++) {
975       dfsPrintLoops(n->children[i]);
976    }
977 }
978
979
980 void BPatch_flowGraph::printLoopsInt()
981 {    
982    dfsPrintLoops(getLoopTree());
983 }
984
985
986 void BPatch_flowGraph::dump()
987 {    
988    BPatch_basicBlock **blocks = new BPatch_basicBlock *[allBlocks.size()];
989    allBlocks.elements(blocks);
990    for (unsigned i=0; i < allBlocks.size(); i++) {
991       fprintf(stderr,"[%u 0x%p 0x%p]\n",
992             blocks[i]->blockNo(),
993             (void *)blocks[i]->getStartAddress(), 
994             (void *)blocks[i]->getEndAddress());
995
996    }
997
998 }
999
1000 bool BPatch_flowGraph::containsDynamicCallsitesInt()
1001 {
1002    return (ll_func()->getNumDynamicCalls() > 0);
1003 }
1004
1005 int_function *BPatch_flowGraph::ll_func() const {
1006    return func_->lowlevel_func();
1007 }
1008
1009 AddressSpace *BPatch_flowGraph::getllAddSpace() const 
1010
1011    return func_->lladdSpace; 
1012 }