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