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