1 package Analysis.TaskStateAnalysis;
5 import IR.ClassDescriptor;
6 import IR.TaskDescriptor;
8 import java.io.FileWriter;
9 import java.io.FileOutputStream;
12 public class ExecutionGraph {
14 private TaskAnalysis taskanalysis;
16 private Hashtable graph;
17 private Hashtable executiongraph;
18 private SymbolTable tasks;
20 public ExecutionGraph(State state, TaskAnalysis ta){
23 this.tasks = this.state. getTaskSymbolTable();
24 this.graph=new Hashtable();
25 this.executiongraph = new Hashtable();
28 public Hashtable getExecutionGraph(){
29 return executiongraph;
32 public void createExecutionGraph() throws java.io.IOException {
33 /*Explore the taskanalysis structure*/
34 System.out.println("------- BUILDING THE EXECUTION GRAPH -------");
35 Enumeration e=taskanalysis.flagstates.keys();
37 while (e.hasMoreElements()) {
38 System.out.println("\nBuilding class :");
39 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
40 System.out.println("\t"+(cdtemp.getSymbol())+ "\n");
49 private void exploreGraph(ClassDescriptor cd) {
51 LinkedList fifo = new LinkedList();
52 Vector sourceNodeList = new Vector();
56 /* Search for starting nodes */
57 Collection nodes = ((Hashtable)taskanalysis.flagstates.get(cd)).values();
58 Iterator it = nodes.iterator();
59 while (it.hasNext()) {
60 FlagState fs = (FlagState)it.next();
61 if(fs.isSourceNode()){
62 sourceNodeList.addElement(fs);
66 /* Perform the Breadth first search algorithm and build ExecutionGraph */
67 FlagState fstemp, fstemp2;
68 Iterator sourceit = sourceNodeList.iterator();
69 while( sourceit.hasNext() ){
70 FlagState fs = (FlagState)sourceit.next();
75 while ( !fifo.isEmpty() ){
77 fstemp = (FlagState)fifo.getFirst();
80 System.out.println("IN FS : "+fstemp.getTextLabel());
82 Iterator edges = fstemp.edges();
85 //build corresponding nodes of the ExecutionGraph
88 //add the other non marked (prevent looping) fses to the fifo
89 while(edges.hasNext()){
91 FEdge edge = (FEdge)edges.next();
92 fstemp2 = (FlagState)edge.getTarget();
94 if ( !fstemp2.isMarked() ) {
96 fifo.addLast(fstemp2);
100 //if the flagstate is not entirely processed, back into fifo
101 if (!isFinished(fstemp)){
102 fifo.addLast(fstemp);
110 private void createNode(FlagState fs){
111 Enumeration allocatingtasks;
115 //the idea is to look at the inedges to find the "parents" nodes. Then create the "children" and link them to the "parents".
116 if (fs.isSourceNode()){
117 //in the case of sourcenode, "parents" are the allocating tasks
118 for (Iterator inedges = ((Vector)fs.getAllocatingTasks()).iterator(); inedges.hasNext();){
119 String tname = new String(((TaskDescriptor)inedges.next()).getSymbol());
120 //the hashkey for source EGTaskNodes is : nextfs+taskname.
121 String key1 = new String(fs.getTextLabel()+tname);
123 if (graph.containsKey(key1)){
124 tn = (EGTaskNode)graph.get(key1);
126 else{//if not existing, create it
127 tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname));
130 //create the children. the key is : nextfs+taskname+previousfs (that ensures that only one node can have that key).
131 for (Iterator edges = fs.edges(); edges.hasNext();){
132 edge = (FEdge)edges.next();
133 target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
134 String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
135 //mark if is self loop
136 if (((FlagState)edge.getTarget()).isMarked()){
137 target.doSelfLoopMarking();
139 //check if child already exists. if not, create it.
140 //link to the parent.
141 if (graph.containsKey(key2)){
142 target = (EGTaskNode)graph.get(key2);
143 EGEdge newedge=new EGEdge(target);
147 EGEdge newedge=new EGEdge(target);
151 graph.put(key2, target);
153 //put parent in graph
158 for (Iterator inedges = fs.inedges(); inedges.hasNext();){
159 //regular case, "parents" are the inedges.
160 FEdge in=(FEdge)inedges.next();
161 if (!in.isProcessed()){
162 //the key to search is : nextfs+taskname+previousfs.
163 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
164 tn = (EGTaskNode)graph.get(key1);
165 //if the TaskNode does not exist, that means that we are in the case of a loop.
166 //The fs will not be entirely processed, will be put back in the fifo until the TaskNode has finaly been created.
168 //same process than with the sourcenode.
169 for (Iterator edges = fs.edges(); edges.hasNext();){
170 edge = (FEdge)edges.next();
171 target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
172 String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
173 if (((String)((FlagState)edge.getTarget()).getTextLabel()).compareTo(fs.getTextLabel())==0){
174 target.doSelfLoopMarking();
176 if (graph.containsKey(key2)){
177 target = (EGTaskNode)graph.get(key2);
178 EGEdge newedge=new EGEdge(target);
182 EGEdge newedge=new EGEdge(target);
185 graph.put(key2, target);
194 //put the graph into executiongraph
195 private void adapt(ClassDescriptor cd) {
196 Vector tasknodes = new Vector();
197 tasknodes.addAll(graph.values());
198 executiongraph.put(cd,tasknodes);
200 //print the contain of graph
201 private void test() {
202 System.out.println("\nGraph contains :");
203 Collection c = graph.values();
204 for ( Iterator it = c.iterator(); it.hasNext();){
205 EGTaskNode tn = (EGTaskNode)it.next();
206 System.out.println(tn.getTextLabel()+" ID "+tn.getLabel()+" FS "+tn.getFSName());
210 //test if a flagstate has been entirely processed
211 private boolean isFinished(FlagState fs){
213 for (Iterator inedges = fs.inedges(); inedges.hasNext();){
215 FEdge in=(FEdge)inedges.next();
217 if (!in.isProcessed()){
218 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
220 if (graph.get(key1)==null){
221 //except for the case of self loop, if the pointed tn is not present, fs is not totally processed
222 if (((String)((FlagState)in.getSource()).getTextLabel()).compareTo(fs.getTextLabel())!=0){
234 //create dot files execution_classname_.dot
235 private void printDOTFile()throws java.io.IOException {
236 Enumeration e = executiongraph.keys();
237 while (e.hasMoreElements()){
238 createDOTFile((ClassDescriptor)e.nextElement());
242 private void createDOTFile(ClassDescriptor cd) throws java.io.IOException {
243 Vector v = (Vector)executiongraph.get(cd);
244 java.io.PrintWriter output;
245 File dotfile_flagstates= new File("execution"+cd.getSymbol()+".dot");
246 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
247 output = new java.io.PrintWriter(dotstream, true);
248 output.println("digraph dotvisitor {");
249 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
250 output.println("\tedge [fontsize=6];");
252 output.println("}\n");
255 private void traverse(java.io.PrintWriter output, Vector v) {
258 for(Iterator it1 = v.iterator(); it1.hasNext();){
259 tn = (EGTaskNode)it1.next();
260 output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
261 if (tn.isSelfLoop()) output.println(", shape=box");
262 if (tn.isMultipleParams()) output.println(", color=blue");
263 output.println("];");
266 for(Iterator it2 = tn.edges();it2.hasNext();){
267 output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((EGEdge)it2.next()).getTarget()).getLabel()+";");
271 //*********************