initial dyninstAPI commit for code coverage
[dyninst.git] / dyninstAPI / src / BPatch_flowGraph.C
1 #define BPATCH_FILE
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <assert.h>
6 #include <string.h>
7
8 #include "common/h/Types.h"
9 #include "common/h/Vector.h"
10 #include "common/h/Dictionary.h"
11
12 #include "util.h"
13 #include "process.h"
14 #include "symtab.h"
15 #include "instPoint.h"
16
17 #include "AddressHandle.h"
18
19 #include "LineInformation.h"
20
21 #include "BPatch_flowGraph.h"
22
23 class TarjanDominator;
24
25 const int BPatch_flowGraph::WHITE = 0;
26 const int BPatch_flowGraph::GRAY  = 1;
27 const int BPatch_flowGraph::BLACK = 2;
28
29 //constructor of the class. It creates the CFG and
30 //deletes the unreachable code.
31 BPatch_flowGraph::BPatch_flowGraph(BPatch_function *bpf)
32         : bpFunction(bpf),loops(NULL),isDominatorInfoReady(false),
33           isSourceBlockInfoReady(false)
34 {
35         //fill the information of the basic blocks after creating
36         //them. The dominator information will also be filled
37         createBasicBlocks();
38         findAndDeleteUnreachable();
39 }
40
41 //contsructor of class. It finds the bpatch function which has the name
42 //given as a parameter and calls the other constructor using the bpatch 
43 //function value.
44 BPatch_flowGraph::BPatch_flowGraph(BPatch_image *bpim,char *functionName){
45         BPatch_function *bpf = NULL;
46         bpf = bpim->findBPFunction(functionName);
47         if(bpf)
48                 *(this) = *(new BPatch_flowGraph(bpf));
49         else{
50                 cerr << "ERROR : BPatch_flowGraph::BPatch_flowGraph : ";
51                 cerr << functionName <<" does not have BPatch_function object\n" ;
52         }
53 }
54
55 //destructor for the class 
56 BPatch_flowGraph::~BPatch_flowGraph(){
57         int i;
58         if(loops){
59                 BPatch_basicBlockLoop** lelements = 
60                         new BPatch_basicBlockLoop*[loops->size()];
61                 loops->elements(lelements);
62                 for(i=0;i<loops->size();i++)
63                         delete lelements[i];
64                 delete[] lelements;
65                 delete loops;
66         }
67
68         BPatch_basicBlock** belements =new BPatch_basicBlock*[allBlocks.size()];
69         allBlocks.elements(belements);
70         for(i=0;i<allBlocks.size();i++)
71                 delete belements[i];
72         delete[] belements;
73         if(bpFunction)
74                 bpFunction->cfg = NULL;
75 }
76
77 void BPatch_flowGraph::getAllBasicBlocks(BPatch_Set<BPatch_basicBlock*>& abb){
78         BPatch_basicBlock** belements =
79                 new BPatch_basicBlock*[allBlocks.size()];
80         allBlocks.elements(belements);
81         for(int i=0;i<allBlocks.size();i++)
82                 abb += belements[i];
83         delete[] belements;
84 }
85
86 //this is the method that returns the set of entry points
87 //basic blocks, to the control flow graph. Actually, there must be
88 //only one entry point to each control flow graph but the definition
89 //given API specifications say there might be more.
90 void BPatch_flowGraph::getEntryBasicBlock(BPatch_Vector<BPatch_basicBlock*>& ebb){
91         
92         BPatch_basicBlock** belements =new BPatch_basicBlock*[entryBlock.size()];
93         entryBlock.elements(belements);
94         for(int i=0;i<entryBlock.size();i++)
95                 ebb.push_back(belements[i]);
96         delete[] belements;
97 }
98
99 //this method returns the set of basic blocks that are the
100 //exit basic blocks from the control flow graph. That is those
101 //are the basic blocks that contains the instruction for
102 //returning from the function
103 void BPatch_flowGraph::getExitBasicBlock(BPatch_Vector<BPatch_basicBlock*>& nbb){
104
105         BPatch_basicBlock** belements =new BPatch_basicBlock*[exitBlock.size()];
106         exitBlock.elements(belements);
107         for(int i=0;i<exitBlock.size();i++)
108                 nbb.push_back(belements[i]);
109         delete[] belements;
110 }
111
112 //this methods returns the loop objects that exist in the control flow
113 //grap. It retuns a set. And if ther is no loop then it returns empty
114 //set. not NULL. 
115 void BPatch_flowGraph::getLoops(BPatch_Vector<BPatch_basicBlockLoop*>& lbb){
116         int i;
117
118         if(!loops){
119                 //creating the loops field which was NULL initially
120                 loops = new BPatch_Set<BPatch_basicBlockLoop*>;
121
122                 //filling the dominator info since to find the loops
123                 //structure we need the dominator info
124                 fillDominatorInfo();
125
126                 //create an array of all blocks size to store the mapping from
127                 //basic block to set of basic blocks as back edges
128                 BPatch_Set<BPatch_basicBlock*>** backEdges = 
129                         new BPatch_Set<BPatch_basicBlock*>*[allBlocks.size()];
130                 for(i=0;i<allBlocks.size();i++)
131                         backEdges[i] = NULL;
132
133                 //using dfs we find the back edeges which define the
134                 //natural loop
135                 findBackEdges(backEdges);
136
137                 //a map from basic block number to basic block pointer
138                 //which will be used to get the basic block pointer
139                 //from its number from the map. I am using this way
140                 //as I do not want to include dictionary_hash in include files
141                 //or use other class(empty) to get around this problem.
142                 //this does not give any drawback for efficency or space.
143
144                 BPatch_basicBlock** bnoToBBptr =
145                                 new BPatch_basicBlock*[allBlocks.size()];
146
147                 BPatch_basicBlock** elements =
148                         new BPatch_basicBlock*[allBlocks.size()];
149                 allBlocks.elements(elements);
150                 for(i=0;i<allBlocks.size();i++)
151                         bnoToBBptr[elements[i]->blockNumber] = elements[i];
152                 delete[] elements;
153
154                 //now using the map find the basic blocks inside the loops
155                 fillLoopInfo(backEdges,bnoToBBptr);
156
157                 //delete the temporary storages since it is done.
158                 for(i=0;i<allBlocks.size();i++)
159                         delete backEdges[i];
160                 delete[] backEdges;
161                 delete[] bnoToBBptr;
162         }
163
164         BPatch_basicBlockLoop** lelements = 
165                 new BPatch_basicBlockLoop*[loops->size()];
166         loops->elements(lelements);
167         for(i=0;i<loops->size();i++)
168                 lbb.push_back(lelements[i]);
169         delete[] lelements;
170 }
171
172 //this is the main method to create the basic blocks and the
173 //the edges between basic blocks. The assumption of the
174 //method is as follows: It assumes existence of four machine dependent
175 //functions as given in AddressHandle.h.
176 //after finding the leaders, for each leader a basic block is created and
177 //then the predecessors and successors of the basic blocks are inserted
178 //to the basic blocks by passing from the function address space again, one
179 //instruction at a time, and using maps from basic blocks to leaders, and
180 //leaders to basic blocks. 
181 //The basic block of which the
182 //leader is the start address of the function is assumed to be the entry block
183 //to control flow graph. This makes only one basic block to be in the
184 //entryBlocks field of the controlflow grpah. If it is possible
185 //to enter a function from many points some modification is needed
186 //to insert all entry basic blocks to the relevant field of the class.
187 void BPatch_flowGraph::createBasicBlocks(){
188
189         int tbs = 0,i,j;
190
191         Address effectiveAddress = (Address) (bpFunction->getBaseAddr());
192         Address relativeAddress = (Address) (bpFunction->getBaseAddrRelative());
193 #if defined(i386_unknown_nt4_0) || defined(mips_unknown_ce2_11) //ccw 6 apr 2001
194         long diffAddress = effectiveAddress;
195 #else
196         long long diffAddress = effectiveAddress;
197 #endif
198         diffAddress -= relativeAddress;
199
200         //initializing the variables to use. Creating an address handle
201         //a set of leaders and a map from leaders to the basic blocks.
202         AddressHandle ah(bpFunction->proc,
203                          bpFunction->mod->mod->exec(),
204                          relativeAddress,
205                          bpFunction->getSize());
206
207         Address baddr = relativeAddress;
208         Address maddr = relativeAddress + bpFunction->getSize();
209         Address taddr;
210
211         BPatch_Set<Address> leaders;
212         dictionary_hash<Address,BPatch_basicBlock*> leaderToBlock(addrHash);
213         
214         //start inserting the leader information. The initial address of the
215         //function is inserted as a leader and a basic block is created for it
216         //and inserted into the map.
217
218         leaders += relativeAddress;
219         leaderToBlock[relativeAddress] = new BPatch_basicBlock(this, tbs++);
220         allBlocks += leaderToBlock[relativeAddress];
221
222         //while there are still instructions to check for in the
223         //address space of the function
224         instruction inst;
225
226
227         for(;ah.hasMore();){
228                 //get the inctruction and the address
229                 inst = ah.getInstruction();
230                 Address pos = ah++;
231
232                 //if it is a conditional branch 
233                 if(isACondBranchInstruction(inst)){
234                         //if also it is inside the function space
235                         //then insert the target address as a leader
236                         //and create the basic block for the leader
237                         taddr = getBranchTargetAddress(inst,pos);
238                         if((baddr <= taddr) && (taddr < maddr) && 
239                            !leaders.contains(taddr)) {
240                                 leaders += taddr;
241                                 leaderToBlock[taddr] =
242                                     new BPatch_basicBlock(this, tbs++);
243                                 allBlocks += leaderToBlock[taddr];
244                         }
245
246                         if(AddressHandle::delayInstructionSupported())
247                             if(!isAnneal(inst))
248                                 //if the dleay instruction is supported by the
249                                 //architecture then skip one more instruction
250                                 ++ah;
251
252                         //if the next address is still in the address
253                         //space of the function then it is also a leader
254                         //since the condition may not be met
255                         taddr = *ah;
256                         if((taddr < maddr) && !leaders.contains(taddr)){
257                                 leaders += taddr;
258                                 leaderToBlock[taddr] =
259                                     new BPatch_basicBlock(this, tbs++);
260                                 allBlocks += leaderToBlock[taddr];
261                         }
262                 }
263                 else if(isAJumpInstruction(inst)) {
264                         //if it is unconditional jump then find the
265                         //target address and insert it as a leader and create
266                         //a basic block for it.
267                         taddr = getBranchTargetAddress(inst,pos);
268                         if((baddr <= taddr) && (taddr < maddr) && 
269                            !leaders.contains(taddr)) {
270                                 leaders += taddr;
271                                 leaderToBlock[taddr] =
272                                     new BPatch_basicBlock(this, tbs++);
273                                 allBlocks += leaderToBlock[taddr];
274                         }
275
276                         if(AddressHandle::delayInstructionSupported())
277                              if(!isAnneal(inst))
278                                 //if the dleay instruction is supported by the
279                                 //architecture then skip one more instruction
280                                 ++ah;
281 #if defined(alpha_dec_osf4_0)
282                         taddr = *ah;
283                         if((taddr < maddr) && !leaders.contains(taddr)){
284                                 leaders += taddr;
285                                 leaderToBlock[taddr] =
286                                     new BPatch_basicBlock(this, tbs++);
287                                 allBlocks += leaderToBlock[taddr];
288                         }
289 #endif
290                 }
291 #if defined(rs6000_ibm_aix4_1)
292                 else if(isAIndirectJumpInstruction(inst,AddressHandle(ah))){
293 #else
294                 else if(isAIndirectJumpInstruction(inst)){
295 #endif
296                         AddressHandle ah2(ah);
297                         BPatch_Set<Address> possTargets; 
298 #if defined(i386_unknown_linux2_0) ||\
299     defined(i386_unknown_solaris2_5) ||\
300     defined(i386_unknown_nt4_0)
301                         ah2.getMultipleJumpTargets(possTargets,ah);
302 #else
303                         ah2.getMultipleJumpTargets(possTargets);
304 #endif
305                         Address* telements = new Address[possTargets.size()];
306                         possTargets.elements(telements);
307                         for(i=0;i<possTargets.size();i++){
308                                 taddr = telements[i];
309                                 if((baddr <= taddr) && (taddr < maddr) &&
310                                    !leaders.contains(taddr)) {
311                                         leaders += taddr;
312                                         leaderToBlock[taddr] =
313                                             new BPatch_basicBlock(this, tbs++);
314                                         allBlocks += leaderToBlock[taddr];
315                                 }
316                         }
317                         delete[] telements;
318
319                         if(AddressHandle::delayInstructionSupported())
320                                 //if the dleay instruction is supported by the
321                                 //architecture then skip one more instruction
322                                 ++ah;
323                         
324                 }
325 #if defined(i386_unknown_linux2_0) ||\
326     defined(i386_unknown_solaris2_5) ||\
327     defined(i386_unknown_nt4_0)
328                 else if(isAReturnInstruction(inst)){
329                         if(AddressHandle::delayInstructionSupported())
330                                 ++ah;
331                         taddr = *ah;
332                         if((baddr <= taddr) && (taddr < maddr) && 
333                            !leaders.contains(taddr)) {
334                                 leaders += taddr;
335                                 leaderToBlock[taddr] =
336                                     new BPatch_basicBlock(this, tbs++);
337                                 allBlocks += leaderToBlock[taddr];
338                         }
339                 }
340 #endif
341         }
342
343
344         //to process the leaders easily sort the leaders according to their
345         //values, that is according to the address value they have
346         Address* elements = new Address[leaders.size()];
347         leaders.elements(elements);
348
349         //insert the first leaders corresponding basic block as a entry
350         //block to the control flow graph.
351
352         leaderToBlock[elements[0]]->isEntryBasicBlock = true;
353         entryBlock += leaderToBlock[elements[0]];
354
355         //for each leader take the address value and continue procesing
356         //the instruction till the next leader or the end of the
357         //function space is seen
358         for(i=0;i<leaders.size();i++){
359                 //set the value of address handle to be the value of the leader
360                 ah.setCurrentAddress(elements[i]);
361                 BPatch_basicBlock * bb = leaderToBlock[elements[i]];
362                 bb->startAddress = (Address)(elements[i]+diffAddress);
363
364                 //while the address handle has instructions to process
365                 while(ah.hasMore()){
366                         //get the current instruction
367                         inst = ah.getInstruction();
368                         Address pos = *ah;
369
370                         //if the next leaders instruction is seen and it is not
371                         //the end of the function yet, find out whether
372                         //the successors of the basic block already has
373                         //some information. If not then it has no branch
374                         //instruction as a last instruction. So the next
375                         //leaders basic block must be in the successor list
376                         //and break processing for the current leader
377                         if((i < (leaders.size()-1)) && (pos == elements[i+1])){
378                                 bb->endAddress = (Address)(ah.prevAddress() + diffAddress);
379                                 if(bb->targets.size() == 0){
380                                         bb->targets += leaderToBlock[pos];
381                                         leaderToBlock[pos]->sources += bb;      
382                                 }
383                                 break;
384                         }
385
386                         //increment the address handle;
387                         ah++;
388
389                         //if the instruction is conditional branch then
390                         //find the target address and find the corresponding 
391                         //leader and basic block for it. Then insert the found
392                         //basic block to the successor list of current leader's
393                         //basic block, and insert current basic block to the
394                         //predecessor field of the other one. Do the
395                         //same thing for the following ( or the other one
396                         //if delay instruction is supported) as a leader.
397                         if(isACondBranchInstruction(inst)){
398                                 taddr = getBranchTargetAddress(inst,pos);
399                                 if((baddr <= taddr) && (taddr < maddr)){
400                                         bb->targets += leaderToBlock[taddr];
401                                         leaderToBlock[taddr]->sources += bb;
402                                 } 
403                                 else
404                                         exitBlock += bb;
405
406                                 if(AddressHandle::delayInstructionSupported())
407                                      if(!isAnneal(inst))
408                                         //if the delay instruction is supported
409                                         ++ah;
410
411                                 taddr = *ah;
412                                 if(taddr < maddr){
413                                         bb->targets += leaderToBlock[taddr];
414                                         leaderToBlock[taddr]->sources += bb;
415                                 }
416                         }
417                         else if(isAJumpInstruction(inst)){
418                                 //if the branch is unconditional then only
419                                 //find the target and leader and basic block 
420                                 //coressponding to the leader. And update 
421                                 //predecessor and successor fields of the 
422                                 //basic blocks.
423                                 taddr = getBranchTargetAddress(inst,pos);
424                                 if((baddr <= taddr) && (taddr < maddr)){
425                                         bb->targets += leaderToBlock[taddr];
426                                         leaderToBlock[taddr]->sources += bb;
427                                 }
428                                 else 
429                                         exitBlock += bb;
430
431                                 if(AddressHandle::delayInstructionSupported())
432                                      if(!isAnneal(inst))
433                                         //if the delay instruction is supported
434                                         ++ah;
435                         }
436 #if defined(rs6000_ibm_aix4_1)
437                         else if(isAIndirectJumpInstruction(inst,AddressHandle(ah))){
438 #else
439                         else if(isAIndirectJumpInstruction(inst)){
440 #endif
441                                 AddressHandle ah2(ah);
442                                 BPatch_Set<Address> possTargets; 
443 #if defined(i386_unknown_linux2_0) ||\
444     defined(i386_unknown_solaris2_5) ||\
445     defined(i386_unknown_nt4_0)
446                                 ah2.getMultipleJumpTargets(possTargets,ah);
447 #else
448                                 ah2.getMultipleJumpTargets(possTargets);
449 #endif
450                                 Address* telements = new Address[possTargets.size()];
451                                 possTargets.elements(telements);
452                                 for(j=0;j<possTargets.size();j++){
453                                         taddr = telements[j];
454                                         if((baddr <= taddr) && (taddr < maddr)){
455                                                 bb->targets += leaderToBlock[taddr];
456                                                 leaderToBlock[taddr]->sources += bb;
457                                         }
458                                         else
459                                                 exitBlock += bb;
460                                 }
461                                 delete[] telements;
462
463                                 if(AddressHandle::delayInstructionSupported())
464                                         //if the dleay instruction is supported by the
465                                         //architecture then skip one more instruction
466                                         ++ah;
467                         }
468                         else if(isAReturnInstruction(inst)){
469                                 exitBlock += bb;
470                                 bb->isExitBasicBlock = true;
471                         }
472                 }
473                 //if the while loop terminated due to recahing the
474                 //end of the address space of the function then set the
475                 //end addresss of the basic block to the last instruction's
476                 //address in the address space.
477                 if(i == (leaders.size()-1))
478                         bb->endAddress = (Address)(ah.prevAddress()+diffAddress);
479
480         }
481         delete[] elements;
482
483 }
484
485 // This function must be called only after basic blocks have been created
486 // by calling createBasicBlocks. It computes the source block for each
487 // basic block. For now, a source block is represented by the starting
488 // and ending line numbers in the source block for the basic block.
489 void BPatch_flowGraph::createSourceBlocks(){
490
491         if (isSourceBlockInfoReady)
492                 return;
493         isSourceBlockInfoReady = true;
494
495         BPatch_image* bpImage = bpFunction->mod->img;
496
497         char functionName[1024];
498         bpFunction->getMangledName(functionName, sizeof(functionName));
499         string fName(functionName);
500         unsigned int i;
501
502         //get the line information object which contains the information for 
503         //this function
504
505         LineInformation* lineInformation;
506         FileLineInformation* fLineInformation = NULL; 
507
508         BPatch_Vector<BPatch_module*>* appModules =  bpImage->getModules();
509         for(i=0;i<appModules->size();i++){
510                 lineInformation = (*appModules)[i]->lineInformation;
511                 if(!lineInformation)
512                         continue;
513                 fLineInformation = lineInformation->getFunctionLineInformation(fName);
514                 if(fLineInformation)
515                         break;
516         }
517
518         if(!fLineInformation){
519                 cerr << "WARNING : Line information is missing >> Function : " ;
520                 cerr << fName  << "\n";
521                 return;
522         }
523
524         Address effectiveAddress = (Address) (bpFunction->getBaseAddr());
525
526
527         //now it is time to look the starting and ending line addresses
528         //of the basic blocks in the control flow graph. To define
529         //the line numbers we will use the beginAddress and endAddress
530         //fields of the basic blocks in the control flow graph
531         //and find the closest lines to these addresses.
532
533         //get the address handle for the region
534         AddressHandle ah(bpFunction->proc,
535                          bpFunction->mod->mod->exec(),
536                          effectiveAddress,
537                          bpFunction->getSize()); 
538
539         //for every basic block in the control flow graph
540
541         BPatch_basicBlock** elements = new BPatch_basicBlock*[allBlocks.size()];
542         allBlocks.elements(elements);
543         for(i=0;i<(unsigned)allBlocks.size();i++){
544                 BPatch_basicBlock *bb = elements[i];
545
546                 //set the address handle to the start address
547                 ah.setCurrentAddress(bb->startAddress);
548
549                 //create the set of unsigned integers for line numbers
550                 //in the basic block
551                 BPatch_Set<unsigned short> lSet;
552
553                 Address cAddr;
554                 //while the address is valid  go backwards and find the
555                 //entry in the mapping from address to line number for closest
556                 //if the address is coming after a line number information
557                 while(ah.hasMore()){
558                         cAddr = ah--;
559                         if(fLineInformation->getLineFromAddr(fName,lSet,cAddr))
560                                 break;
561                 }
562
563                 //set the address handle to the start address
564                 ah.setCurrentAddress(bb->startAddress);
565
566                 //while the address is valid go forward and find the entry
567                 //in the mapping from address to line number for closest
568                 while(ah.hasMore()){
569                         cAddr = ah++;
570                         if(cAddr > bb->endAddress) 
571                                 break;
572                         fLineInformation->getLineFromAddr(fName,lSet,cAddr);
573                 }
574                 
575                 //create the source block for the above address set
576                 //and assign it to the basic block field
577                 bb->sourceBlock = new BPatch_sourceBlock(lSet);
578         }
579         delete[] elements; 
580 }
581
582 /* class that calculates the dominators of a flow graph using
583    tarjan's algorithms with results an almost linear complexity
584    for graphs with less than 8 basic blocks */
585
586 class TarjanDominator {
587 private:
588         int n,r;
589         BPatch_basicBlock** numberToBlock;
590         int *dom,*parent, *ancestor, *child, *vertex, *label, *semi,*size;
591         BPatch_Set<int>** bucket;
592
593         inline int bbToint(BPatch_basicBlock* bb){
594                 return bb->blockNumber + 1;
595         }
596         void dfs(int v,int* dfsNo){
597                 semi[v] = ++(*dfsNo);
598                 vertex[*dfsNo] = v;
599                 label[v] = v;
600                 ancestor[v] = 0;
601                 child[v] = 0;
602                 size[v] = 1;
603                 BPatch_basicBlock* bb = numberToBlock[v];
604                 BPatch_basicBlock** elements = new BPatch_basicBlock*[bb->targets.size()];
605                 bb->targets.elements(elements);
606                 for(int i=0;i<bb->targets.size();i++){
607                         int w = bbToint(elements[i]);
608                         if(semi[w] == 0){
609                                 parent[w] = v;
610                                 dfs(w,dfsNo);
611                         }
612                 }
613                 delete[] elements;
614         }
615         void COMPRESS(int v){
616                 if(ancestor[ancestor[v]] != 0){
617                         COMPRESS(ancestor[v]);
618                         if(semi[label[ancestor[v]]] < semi[label[v]])
619                                 label[v] = label[ancestor[v]];
620                         ancestor[v] = ancestor[ancestor[v]];
621                 }
622         }
623         int EVAL(int v){
624                 if(ancestor[v] == 0)
625                         return label[v];
626                 COMPRESS(v);
627                 if(semi[label[ancestor[v]]] >= semi[label[v]])
628                         return label[v];
629                 return label[ancestor[v]];
630         }
631         void LINK(int v,int w){
632                 int s = w;
633                 while(semi[label[w]] < semi[label[child[s]]]){
634                         if((size[s]+size[child[child[s]]]) >= (2*size[child[s]])){
635                                 ancestor[child[s]] = s;
636                                 child[s] = child[child[s]];
637                         }
638                         else{
639                                 size[child[s]] = size[s];
640                                 ancestor[s] = child[s];
641                                 s = child[s];
642                         }
643                 }
644                 label[s] = label[w];
645                 size[v] += size[w];
646                 if(size[v] < (2*size[w])){
647                         int tmp = s;
648                         child[v] = s;
649                         s = tmp;
650                 }
651                 while(s != 0){
652                         ancestor[s] = v;
653                         s = child[s];
654                 }
655         }
656 public:
657         TarjanDominator(int size,BPatch_basicBlock* root,BPatch_basicBlock** blocks) 
658                 : n(size),r(bbToint(root)) 
659         {
660                 int i;
661
662                 size++;
663                 numberToBlock = new BPatch_basicBlock*[size];
664                 numberToBlock[0] = NULL;
665                 for(i=0;i<n;i++)
666                         numberToBlock[bbToint(blocks[i])] = blocks[i];  
667
668                 dom = new int[size];
669
670                 parent = new int[size];
671                 ancestor = new int[size];
672                 child = new int[size];
673                 vertex = new int[size];
674                 label = new int[size];
675                 semi = new int[size];
676                 this->size = new int[size];
677                 bucket = new BPatch_Set<int>*[size];
678
679                 for(i=0;i<size;i++){
680                         bucket[i] = new BPatch_Set<int>;
681                         semi[i] = 0;    
682                 }
683         }
684         ~TarjanDominator(){
685                 int i;
686                 delete[] numberToBlock;
687                 delete[] parent;
688                 delete[] ancestor;
689                 delete[] child;
690                 delete[] vertex;
691                 delete[] label;
692                 delete[] semi;
693                 delete[] size;
694                 delete[] dom;
695                 for(i=0;i<(n+1);i++)
696                         delete bucket[i];
697                 delete[] bucket;
698         }
699         void findDominators(){
700                 int i;
701                 int dfsNo = 0;
702                 dfs(r,&dfsNo);
703
704                 size[0] = 0;
705                 label[0] = 0;
706                 semi[0] = 0;
707
708                 for(i=n;i>1;i--){
709                         int w =  vertex[i];
710
711                         BPatch_basicBlock* bb = numberToBlock[w];
712                         BPatch_basicBlock** elements = new BPatch_basicBlock*[bb->sources.size()];
713                         bb->sources.elements(elements);
714                         for(int j=0;j<bb->sources.size();j++){
715                                 int v = bbToint(elements[j]);
716                                 int u = EVAL(v);
717                                 if(semi[u] < semi[w])
718                                         semi[w] = semi[u];
719                         }
720                         bucket[vertex[semi[w]]]->insert(w);
721                         LINK(parent[w],w);
722                         int v = 0;
723                         BPatch_Set<int>* bs = bucket[parent[w]];
724                         while(bs->extract(v)){
725                                 int u = EVAL(v);
726                                 dom[v] = ( semi[u] < semi[v] ) ? u : parent[w];
727                         }
728                 }
729                 for(i=2;i<=n;i++){
730                         int w = vertex[i];
731                         if(dom[w] != vertex[semi[w]])
732                                 dom[w] = dom[dom[w]];
733                 }
734                 dom[r] = 0;
735
736                 for(i=1;i<=n;i++){
737                         int w = vertex[i];
738                         BPatch_basicBlock* bb = numberToBlock[w];
739                         bb->immediateDominator = numberToBlock[dom[w]];
740                         if(bb->immediateDominator){
741                                 if(!bb->immediateDominator->immediateDominates)
742                                         bb->immediateDominator->immediateDominates =
743                                                 new BPatch_Set<BPatch_basicBlock*>;
744                                 bb->immediateDominator->immediateDominates->insert(bb);
745                         }
746                 }
747         }
748 };
749
750 //this method fill the dominator information of each basic block
751 //looking at the control flow edges. It uses a fixed point calculation
752 //to find the immediate dominator of the basic blocks and the set of
753 //basic blocks that are immediately dominated by this one.
754 //Before calling this method all the dominator information
755 //is going to give incorrect results. So first this function must
756 //be called to process dominator related fields and methods.
757 void BPatch_flowGraph::fillDominatorInfo(){
758
759         int i,j,k;
760         BPatch_basicBlock* bb;
761         BPatch_Set<BPatch_basicBlock*>* domSet;
762         BPatch_basicBlock** elements = NULL;
763
764         if(isDominatorInfoReady)
765                 return;
766         isDominatorInfoReady = true;
767
768         /* if the number of basic blocks is greater than 8 then use
769            tarjan's fast dominator algorithm. Otherwise use the 
770            previous one */
771
772         if(allBlocks.size() >= 8 ){
773                 elements = new BPatch_basicBlock*[allBlocks.size()];
774                 allBlocks.elements(elements);
775                 TarjanDominator tarjanDominator(allBlocks.size(),
776                                                 entryBlock.minimum(),
777                                                 elements);
778                 delete[] elements;
779                 tarjanDominator.findDominators();
780
781                 return;
782         }
783
784         /* end of the tarjan dominator claculation  if used */
785
786         BPatch_Set<BPatch_basicBlock*>** blockToDominator = 
787                         new BPatch_Set<BPatch_basicBlock*>*[allBlocks.size()];
788
789         //for each basic block set the set of dominators to 
790         //all basic blocks in the control flow. For the entry basic blocks
791         //the set contains only the basic block itself initially, and through
792         //the algorithm since they can not be dominated by any other basic 
793         //block.
794
795         int tmp = 0;
796         BPatch_basicBlock** belements = 
797                 new BPatch_basicBlock*[allBlocks.size()];
798         int* bbToColor = new int[allBlocks.size()];
799         for(i=0;i<allBlocks.size();i++){
800                 bbToColor[i] = WHITE;
801                 belements[i] = NULL;
802         }
803
804         //a dfs order of basic blocks
805         elements = new BPatch_basicBlock*[entryBlock.size()];
806         entryBlock.elements(elements);
807         for(i=0;i<entryBlock.size();i++)
808                 if(bbToColor[elements[i]->blockNumber] == WHITE)
809                         dfsVisit(elements[i],bbToColor,NULL,&tmp,belements);
810         delete[] elements;
811         delete[] bbToColor;
812
813         for(i=0;i<allBlocks.size();i++){
814                 bb = belements[i];
815                 domSet = new BPatch_Set<BPatch_basicBlock*>;
816                 if(entryBlock.contains(bb))
817                         //if enntry basic block then insert itself
818                         domSet->insert(bb);
819                 else 
820                         *domSet |= allBlocks;
821
822                 blockToDominator[bb->blockNumber] = domSet; 
823         }
824
825         bool done = true ;
826         //fix-point calculation start here. When the fix point is reached for 
827         //the set then done will be true and no more iterations will be done
828         do{
829                 done = true;
830                 for(i=0;i<allBlocks.size();i++){
831                         bb = belements[i];
832
833                         //the processing is done for basic blocks that are not
834                         //entry points to the control flow graph. Since
835                         //entry basic blocks can not be dominated by other 
836                         //basic blocks
837                         if(!entryBlock.contains(bb))
838                         {
839                                 BPatch_Set<BPatch_basicBlock*>* oldSet = 
840                                         blockToDominator[bb->blockNumber];
841                                 BPatch_Set<BPatch_basicBlock*>* newSet = 
842                                         new BPatch_Set<BPatch_basicBlock*>;
843
844                                 //initialize the new set
845                                 if(bb->sources.size() != 0)
846                                         *newSet |= allBlocks;
847                                 assert(bb->sources.size());
848
849                                 //intersect the dominators of the predecessors
850                                 //since a block is dominated by the common 
851                                 //blocks that dominate each predecessor of the
852                                 //basic block.
853
854                                 BPatch_basicBlock** selements = 
855                                         new BPatch_basicBlock*[bb->sources.size()];
856                                 bb->sources.elements(selements); 
857                                 for(int j=0;j<bb->sources.size();j++)
858                                         *newSet &= *blockToDominator[selements[j]->blockNumber];
859                                 delete[] selements;
860
861                                 //add the basic block itself. Since every block
862                                 //is dominated by itself.
863                                 *newSet += bb;
864                                 blockToDominator[bb->blockNumber] = newSet;
865         
866                                 //if the previous set for basic block is the 
867                                 //same with the new one generated then this
868                                 //basic blocks dominator set reached the fix 
869                                 //point. But if at least one basic block did 
870                                 //not reach the fix point the iteration will
871                                 //be done once more.
872                                 if(*oldSet != *newSet)
873                                         done = false;
874                                 delete oldSet;
875                         }
876                 }
877         }while(!done);
878
879         //since the output of the previous set is the set of basic blocks
880         //that dominate a basic block we have to use this information
881         //and change it to the set of basic blocks that the basic block
882         //dominates and using this information we have to fill the
883         //immediate dominates field of each basic block. 
884
885         //at this pointdominator tree construction is easy since
886         //all the necessary information is ready. Finding immediate
887         //dominators is enough for many purposes. To find the
888         //immediate dominator of each block the dominators of basic 
889         //blocks will be used. 
890
891         //initially we initialize a mapping from a basic block to a basic block set
892         //to keep track of the immediate dominators. We initialize sets corresponding
893         //to a basic block with its dominator set except itself
894
895         for(i=0;i<allBlocks.size();i++)
896                 blockToDominator[belements[i]->blockNumber]->remove(belements[i]);
897
898         //then for each node we eliminate the unnecessary basic blocks to reach 
899         //the immediate dominator. What we do it we look at the dominators of 
900         //the basic block. Then for each dominator we take an element and iterate 
901         //on the remaining ones. If the dominatos of the 
902         //chosen elemnt contains one of the others then we delete the latter one 
903         //from the set since it can not be immediate dominator. At the end of 
904         //the loops the each set will contain immediate dominator
905
906         for(i=0;i<allBlocks.size();i++)
907                 if(!entryBlock.contains(belements[i])){
908                         BPatch_basicBlock *currBlock = belements[i];
909
910                         BPatch_Set<BPatch_basicBlock*> ts1(*blockToDominator[currBlock->blockNumber]);
911                         BPatch_basicBlock** it1 = new BPatch_basicBlock*[ts1.size()];
912                         ts1.elements(it1);
913
914                         for(j=0;j<ts1.size();j++){
915                                 BPatch_basicBlock *bb1 = it1[j];
916                                 BPatch_Set<BPatch_basicBlock*> ts2(*blockToDominator[currBlock->blockNumber]);
917                                 ts2.remove(bb1);
918                                 BPatch_basicBlock** it2 = new BPatch_basicBlock*[ts2.size()];
919                                 ts2.elements(it2);
920                                 for(k=0;k<ts2.size();k++){
921                                         BPatch_basicBlock *bb2 = it2[k];
922                                         if(blockToDominator[bb1->blockNumber]->contains(bb2))
923                                                 blockToDominator[currBlock->blockNumber]->remove(bb2);
924                                 }
925                                 delete[] it2;
926                         }
927
928                         delete[] it1;
929                 }
930
931         //using the previous imformation we will initialize the immediateDominator field 
932         //of each basic blocks in control flow graph
933         //if for a basic block another basic blocks dominator set
934         //contains the former one, then we insert the latter to the
935         //dominates field of the first one.
936
937
938         for(i=0;i<allBlocks.size();i++){        
939                 bb = belements[i];
940                 if(entryBlock.contains(bb) ||
941                   !blockToDominator[bb->blockNumber]->extract(bb->immediateDominator))
942                         bb->immediateDominator = NULL;
943                 assert(!blockToDominator[bb->blockNumber]->size());
944                 delete blockToDominator[bb->blockNumber];
945                 if(!entryBlock.contains(bb)){
946                         BPatch_basicBlock* dominator = bb->immediateDominator;
947                         domSet = dominator->immediateDominates;
948                         if(!domSet){
949                                 domSet = new BPatch_Set<BPatch_basicBlock*>;
950                                 dominator->immediateDominates = domSet;
951                         }
952                         domSet->insert(bb);
953                 }
954         }
955         delete[] blockToDominator;
956         delete[] belements;
957 }
958
959
960
961 //method that finds the unreachable basic blocks and then deletes
962 //the structures allocated for that block. If the argument is 
963 //NULL then it deletes unreachable code. 
964 void BPatch_flowGraph::findBackEdges(BPatch_Set<BPatch_basicBlock*>** backEdges)
965 {
966         int i;
967         int* bbToColor = new int[allBlocks.size()];
968         for(i=0;i<allBlocks.size();i++)
969                 bbToColor[i] = WHITE;
970         
971         //a dfs based back edge discovery
972         BPatch_basicBlock** elements = 
973                 new BPatch_basicBlock*[entryBlock.size()];
974         entryBlock.elements(elements);
975         for(i=0;i<entryBlock.size();i++)
976                 if(bbToColor[elements[i]->blockNumber] == WHITE)
977                         dfsVisit(elements[i],bbToColor,backEdges);
978         delete[] elements;
979         delete[] bbToColor;
980 }
981
982 //method that implements the depth first visit operation
983 void BPatch_flowGraph::dfsVisit(BPatch_basicBlock* bb,
984                                 int* bbToColor,
985                                 BPatch_Set<BPatch_basicBlock*>** backEdges,
986                                 int* which,
987                                 BPatch_basicBlock** order)
988 {
989         if(order) order[(*which)++] = bb;       
990         bbToColor[bb->blockNumber] = GRAY;
991         BPatch_basicBlock** elements =  
992                         new BPatch_basicBlock*[bb->targets.size()];
993         bb->targets.elements(elements);
994         for(int i=0;i<bb->targets.size();i++)
995                 if(bbToColor[elements[i]->blockNumber] == WHITE)
996                         dfsVisit(elements[i],bbToColor,backEdges,which,order);
997                 else if(backEdges && 
998                         (bbToColor[elements[i]->blockNumber] == GRAY))
999                 {
1000                         BPatch_Set<BPatch_basicBlock*>* newSet = backEdges[bb->blockNumber];
1001                         if(!newSet){
1002                                 newSet = new BPatch_Set<BPatch_basicBlock*>;
1003                                 backEdges[bb->blockNumber] = newSet;
1004                         }
1005                         newSet->insert(elements[i]);
1006                 }
1007         bbToColor[bb->blockNumber] = BLACK;
1008         delete[] elements;
1009 }
1010
1011 typedef struct SortTuple{
1012         Address address;
1013         BPatch_basicBlock* bb;
1014 }SortTuple;
1015 int tupleSort(const void* arg1,const void* arg2){
1016         if(((const SortTuple*)arg1)->address >
1017            ((const SortTuple*)arg2)->address)
1018                 return 1;
1019         if(((const SortTuple*)arg1)->address <
1020            ((const SortTuple*)arg2)->address)
1021                 return -1;
1022         return 0;
1023 }
1024 void BPatch_flowGraph::findAndDeleteUnreachable()
1025 {
1026
1027         int i,j;
1028
1029         int* bbToColor = new int[allBlocks.size()];
1030         for(i=0;i<allBlocks.size();i++)
1031                 bbToColor[i] = WHITE;
1032
1033         //a dfs based back edge discovery
1034         BPatch_basicBlock** elements = 
1035                         new BPatch_basicBlock*[entryBlock.size()];
1036         entryBlock.elements(elements);
1037         for(i=0;i<entryBlock.size();i++)
1038                 if(bbToColor[elements[i]->blockNumber] == WHITE)
1039                         dfsVisit(elements[i],bbToColor,NULL);
1040
1041         delete[] elements;
1042
1043         BPatch_Set<BPatch_basicBlock*> toDelete;
1044         elements =  new BPatch_basicBlock*[allBlocks.size()];
1045         allBlocks.elements(elements);
1046         int oldCount = allBlocks.size();
1047         for(i=0;i<oldCount;i++){
1048                 BPatch_basicBlock* bb = elements[i];
1049                 if(bbToColor[bb->blockNumber] == WHITE){
1050
1051                         BPatch_basicBlock** selements = 
1052                                 new BPatch_basicBlock*[bb->sources.size()];
1053                         bb->sources.elements(selements);
1054                         int count = bb->sources.size();
1055                         for(j=0;j<count;j++)
1056                                 selements[j]->targets.remove(bb);
1057                         delete[] selements;
1058
1059                         selements = new BPatch_basicBlock*[bb->targets.size()];
1060                         bb->targets.elements(selements);
1061                         count = bb->targets.size();
1062                         for(j=0;j<count;j++)
1063                                 selements[j]->sources.remove(bb);
1064                         delete[] selements;
1065
1066                         allBlocks.remove(bb);
1067                         exitBlock.remove(bb);
1068                         toDelete += bb;
1069                 }
1070         }
1071         delete[] elements;
1072         elements = new BPatch_basicBlock*[toDelete.size()];
1073         toDelete.elements(elements);    
1074         for(i=0;i<toDelete.size();i++)
1075                 delete elements[i];
1076         delete[] elements;
1077         delete[] bbToColor;
1078
1079         int orderArraySize = allBlocks.size();
1080         SortTuple* orderArray = new SortTuple[orderArraySize];
1081         elements = new BPatch_basicBlock*[allBlocks.size()];
1082         allBlocks.elements(elements);
1083         for(i=0;i<orderArraySize;i++){
1084                 orderArray[i].bb = elements[i];
1085                 orderArray[i].address = elements[i]->startAddress;
1086         }
1087         qsort((void*)orderArray,orderArraySize,sizeof(SortTuple),tupleSort);
1088         for(i=0;i<orderArraySize;i++)
1089                 orderArray[i].bb->setBlockNumber(i);
1090         delete[] orderArray;
1091         delete[] elements;
1092 }
1093
1094 //this method is used find the basic blocks contained by the loop
1095 //defined by a backedge. The tail of the backedge is the starting point and
1096 //the predecessors of the tail is inserted as a member of the loop.
1097 //then the predecessors of the newly inserted blocks are also inserted
1098 //until the head of the backedge is in the set(reached).
1099
1100 void BPatch_flowGraph::findBBForBackEdge(
1101                         BPatch_basicBlock* from,
1102                         BPatch_basicBlock* to,
1103                         BPatch_Set<BPatch_basicBlock*>& bbSet)
1104 {
1105 typedef struct STACK {
1106         unsigned size;
1107         int top;
1108         BPatch_basicBlock** data;
1109
1110         STACK() : size(0),top(-1),data(NULL) {}
1111         ~STACK() { free(data); }
1112         bool empty() { return (top < 0); }
1113         void push(BPatch_basicBlock* b) {
1114                 if(!size) 
1115                     data = (BPatch_basicBlock**) malloc(
1116                                 sizeof(BPatch_basicBlock*)*(++size));
1117                 else if(top == ((int)size-1))
1118                     data = (BPatch_basicBlock**)realloc(
1119                                 data,sizeof(BPatch_basicBlock*)*(++size));
1120                 top++;
1121                 data[top] = b;
1122         }
1123         BPatch_basicBlock* pop() {
1124                 if(empty()) return NULL;
1125                 return data[top--];
1126         }
1127 } STACK;
1128
1129         STACK* stack = new STACK;
1130
1131         bbSet += to;
1132         if(!bbSet.contains(from)){
1133                 bbSet += from;
1134                 stack->push(from);
1135         }
1136         while(!stack->empty()){
1137                 BPatch_basicBlock* bb = stack->pop();
1138                 BPatch_basicBlock** elements = 
1139                         new BPatch_basicBlock*[bb->sources.size()];
1140                 bb->sources.elements(elements);
1141                 for(int i=0;i<bb->sources.size();i++)
1142                         if(!bbSet.contains(elements[i])){
1143                                 bbSet += elements[i];
1144                                 stack->push(elements[i]);
1145                         }
1146                 delete[] elements;
1147         }
1148         delete stack;
1149 }
1150
1151 //this method find all loops in the control flow graph.
1152 //The loops are defined by backedges and the backedge defines
1153 //a loop if the head of the backedge dominates the tail of the backedge.
1154 //Then after finding all loops then the basic blocks in the loops
1155 //are found and the nesting structure of the loops are found and the
1156 //relevant fields of the loops are filled by the information discovered.
1157 void BPatch_flowGraph::fillLoopInfo(BPatch_Set<BPatch_basicBlock*>** backEdges,
1158                                     BPatch_basicBlock** bToP)
1159 {
1160         //for each back edge find the dominator relationship and if the
1161         //head basic block dominates the tail then find the loop basic blocks
1162
1163         for(int bNo=0;bNo<allBlocks.size();bNo++){
1164                 if(!backEdges[bNo])
1165                         continue;
1166
1167                 BPatch_Set<BPatch_basicBlock*>* toBlocks = backEdges[bNo];
1168                 BPatch_basicBlock* bbFrom = bToP[bNo];
1169                 BPatch_basicBlock** elements = 
1170                         new BPatch_basicBlock*[toBlocks->size()];
1171                 toBlocks->elements(elements);
1172                 for(int i=0;i<toBlocks->size();i++){
1173                         BPatch_basicBlock* bbTo = elements[i];
1174                         if(bbTo->dominates(bbFrom)){
1175                                 //then check whether
1176                                 //it dominates the current
1177                                 //basic block. If so then
1178                                 //it defines a loop. Otherwise
1179                                 //there is no regular loop
1180                                 //create the loop
1181                                 BPatch_basicBlockLoop* l = 
1182                                         new BPatch_basicBlockLoop(bbTo);
1183
1184                                 //initialize some fields of the
1185                                 //loop object
1186                                 l->backEdges += bbFrom;
1187                                 (*loops) += l;
1188
1189                                 //find all basic blocks in the
1190                                 //loop and keep a map used
1191                                 //to find the nest structure 
1192                                 findBBForBackEdge(bbFrom,bbTo,l->basicBlocks);
1193                         }
1194                 }
1195                 delete[] elements;
1196         }
1197
1198         //create two iterators on the elements of the map which is from
1199         //loop object to the set of basic blocks
1200         //for each loop object pair check whether one is subset of the
1201         //other. That is the set of basic blocks in the loop. If one is
1202         //subset of the other one then the smaller one is nested in the
1203         //bigger one so insert the smaller one to the containedLoops 
1204         //field of the loop object.
1205
1206         BPatch_basicBlockLoop** it = 
1207                         new BPatch_basicBlockLoop*[loops->size()];
1208         loops->elements(it);
1209         for(int i=0;i<loops->size();i++)
1210                 for(int j=0;j<loops->size();j++)
1211                         if(i != j){
1212                                 BPatch_basicBlockLoop* l1 = it[i];
1213                                 BPatch_basicBlockLoop* l2 = it[j];
1214                                 BPatch_Set<BPatch_basicBlock*> diff(l1->basicBlocks);
1215                                 diff -= l2->basicBlocks;
1216                                 if(diff.empty())
1217                                         l2->containedLoops += l1;
1218                         }
1219         delete[] it;
1220 }
1221
1222 //print method
1223 ostream& operator<<(ostream& os,BPatch_flowGraph& fg){
1224         int i;
1225         os << "Begin CFG :\n";
1226         BPatch_basicBlock** belements = 
1227                 new BPatch_basicBlock*[fg.allBlocks.size()];
1228         fg.allBlocks.elements(belements);
1229         for(i=0;i<fg.allBlocks.size();i++)
1230                 os << *belements[i];
1231         delete[] belements;
1232
1233         if(fg.loops){
1234                 BPatch_basicBlockLoop** lelements = 
1235                         new BPatch_basicBlockLoop*[fg.loops->size()];
1236                 fg.loops->elements(lelements);  
1237                 for(i=0;i<fg.loops->size();i++)
1238                         os << *lelements[i];
1239                 delete[] lelements;
1240         }
1241         os << "End CFG :\n";
1242         return os;
1243 }