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