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