|
|
I've studied about dominator tree of a Control flow graph. I have stored my CFG as an adjacency matrix. I wanted to compute the dominator tree for this and store it in dominator matrix. I wrote the following but somehow it doesn't work. Please help....
Ive used the following algo.
To calculate the dominator matrix dm:
dm[1]= [1] union [ intersection of dominators of all predecessors of 1} and so on for all.
I've initialised a matrix dmin which will be used for doing the union.
i've done the part of finding the predecessors and taking intersection in the intersect function.
Code:
#include <iostream>
#include <stdio.h>
using namespace std;
int intersect(int x);
int am[10][10],dm[10][10],dmin[10][10],i,j,x,k,s,l,m,n,it,jt,kt;
int main()
{
for(i=0;i<10;i++)
{ for(j=0;j<10;j++)
{
if (j==i)
{
dmin[j]=1;
}
else
{
dmin[j]=0;
}
//cout<<"Enter the "<<i<<"th row "<<j<<" th element";
//cin>>am[j];
//am[j]=1; // adjacency matrix
}
}
int am[10][10]= { { 0,1,1,0,0,0,0,0,0,0},{0,0,1,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,0},{0,0,1,0,1,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,1,0,0,0},{0,0,0,1,0,0,0,1,0,0},{0,0,1,0,0,0,0,0,1,1},{1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0 } };
for(it=0;it<10;it++)
{
for(jt=0;jt<10;jt++)
{
intersect(it);
dm[it][jt]= dmin[it][jt] or dm[it][jt];
}
}
cout<<"the adjacency matrix is=\n"; //to print the adjacency matrix
for(i=0;i<10;i++)
{ for(j=0;j<10;j++)
{
cout<<am[j];
}
cout<<"\n";
}
cout<<"the dm initialisation matrix is=\n"; //i've made this matrix and named as initialisation matrix to do the union with this for the dominator tree.
for(i=0;i<10;i++)
{ for(j=0;j<10;j++)
{
cout<<dmin[j];
}
cout<<"\n";
}
cout<<"the dominator matrix is=\n"; //to print dominator tree.
for(i=0;i<10;i++)
{ for(j=0;j<10;j++)
{
cout<<dm[j];
}
cout<<"\n";
}
return 0;
}
int intersect(int x) // function to calculate the intersection of all predecessors of a node.
{
int j=0,k=0,l;
for(j=0;j<x;j++)
{
for(k=0;k<10;k++)
{
if(am[k][x]==1)
{
for(l=0;l<10;l++)
{
dm[x][l]=dm[x][l] and dm[k][l];
}
}
else {}
}
}
return 0;
}
|
|
|
|
|
anubhavagrawal
