From 0e856d9c20595d961502a6c1f4ee41eeeac55a79 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 13 Sep 2007 08:35:08 +0000 Subject: [PATCH] simplify ExecutionGraph code --- .../TaskStateAnalysis/EGTaskNode.java | 20 +- .../TaskStateAnalysis/ExecutionGraph.java | 247 ++++-------------- .../src/Analysis/TaskStateAnalysis/FEdge.java | 14 +- .../Analysis/TaskStateAnalysis/FlagState.java | 47 ++-- .../OptionalTaskDescriptor.java | 20 +- .../Analysis/TaskStateAnalysis/Predicate.java | 11 +- .../TaskStateAnalysis/SafetyAnalysis.java | 39 +-- .../TaskStateAnalysis/TaskAnalysis.java | 109 ++++---- Robust/src/Runtime/DSTM/interface/trans.c | 2 +- Robust/src/Util/Edge.java | 10 - 10 files changed, 155 insertions(+), 364 deletions(-) diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java index 59745582..5d567fbf 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java +++ b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java @@ -18,27 +18,19 @@ public class EGTaskNode extends TaskNode { private TaskDescriptor td; protected HashSet edges = new HashSet(); public EGTaskNode(){ - super("default"); - this.fs = null; - this.td = null; + this("default", null, null); } public EGTaskNode(String name){ - super(name); - this.fs = null; - this.td = null; + this(name, null, null); } public EGTaskNode(String name, FlagState fs){ - super(name); - this.fs = fs; - this.td = null; + this(name, fs, null); } public EGTaskNode(String name, TaskDescriptor td){ - super(name); - this.fs = null; - this.td = td; + this(name, null, td); } public EGTaskNode(String name, FlagState fs, TaskDescriptor td){ @@ -54,7 +46,7 @@ public class EGTaskNode extends TaskNode { public boolean equals(Object o){ if(o instanceof EGTaskNode){ EGTaskNode tn=(EGTaskNode) o; - return (tn.getLabel().compareTo(this.getLabel())==0) ? true : false; + return tn.getLabel().equals(getLabel()); } return false; } @@ -164,6 +156,4 @@ public class EGTaskNode extends TaskNode { public int type(){ return type; } - - } diff --git a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java index 493ac644..afcff39c 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java +++ b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java @@ -10,19 +10,18 @@ import java.io.FileOutputStream; import Util.Edge; public class ExecutionGraph { - private TaskAnalysis taskanalysis; private State state; - private Hashtable graph; private Hashtable executiongraph; - private SymbolTable tasks; - + private HashSet marked; + private HashSet processed; + public ExecutionGraph(State state, TaskAnalysis ta){ this.taskanalysis=ta; this.state=state; - this.tasks = this.state. getTaskSymbolTable(); - this.graph=new Hashtable(); this.executiongraph = new Hashtable(); + this.marked=new HashSet(); + this.processed=new HashSet(); } public Hashtable getExecutionGraph(){ @@ -30,175 +29,75 @@ public class ExecutionGraph { } public void createExecutionGraph() throws java.io.IOException { - /*Explore the taskanalysis structure*/ - System.out.println("------- BUILDING THE EXECUTION GRAPH -------"); + //Cycle through classes Enumeration e=taskanalysis.flagstates.keys(); while (e.hasMoreElements()) { - System.out.println("\nBuilding class :"); ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); - System.out.println("\t"+(cdtemp.getSymbol())+ "\n"); - exploreGraph(cdtemp); - test(); - adapt(cdtemp); + HashSet graph=exploreGraph(cdtemp); + adapt(cdtemp,graph); } printDOTFile(); - } - private void exploreGraph(ClassDescriptor cd) { - - LinkedList fifo = new LinkedList(); - Vector sourceNodeList = new Vector(); - Enumeration e; - graph.clear(); - - /* Search for starting nodes */ - Collection nodes = ((Hashtable)taskanalysis.flagstates.get(cd)).values(); - Iterator it = nodes.iterator(); + private HashSet exploreGraph(ClassDescriptor cd) { + LinkedList fifo = new LinkedList(); + HashSet nodes=new HashSet(); + Hashtable map=new Hashtable(); + + // Go through nodes + Iterator it = taskanalysis.getFlagStates(cd).iterator(); while (it.hasNext()) { - FlagState fs = (FlagState)it.next(); - if(fs.isSourceNode()){ - sourceNodeList.addElement(fs); - } - } - - /* Perform the Breadth first search algorithm and build ExecutionGraph */ - FlagState fstemp, fstemp2; - Iterator sourceit = sourceNodeList.iterator(); - while( sourceit.hasNext() ){ - FlagState fs = (FlagState)sourceit.next(); - - fs.doMarking(); - fifo.addLast(fs); - - while ( !fifo.isEmpty() ){ - - fstemp = (FlagState)fifo.getFirst(); - fifo.removeFirst(); - - System.out.println("IN FS : "+fstemp.getTextLabel()); - - Iterator edges = fstemp.edges(); - if (edges.hasNext()){ - - //build corresponding nodes of the ExecutionGraph - createNode(fstemp); - - //add the other non marked (prevent looping) fses to the fifo - while(edges.hasNext()){ - + FlagState fs = it.next(); + if(fs.isSourceNode()) { + for (Iterator allocit = ((Vector)fs.getAllocatingTasks()).iterator(); allocit.hasNext();) { + TaskDescriptor alloctask=(TaskDescriptor)allocit.next(); + EGTaskNode srcnode=new EGTaskNode(alloctask.getSymbol(),alloctask); + nodes.add(srcnode); + srcnode.setSource(); + for (Iterator edges = fs.edges(); edges.hasNext();){ FEdge edge = (FEdge)edges.next(); - fstemp2 = (FlagState)edge.getTarget(); - - if ( !fstemp2.isMarked() ) { - fstemp2.doMarking(); - fifo.addLast(fstemp2); - } - } - - //if the flagstate is not entirely processed, back into fifo - if (!isFinished(fstemp)){ - fifo.addLast(fstemp); - } - } - - } - } - } - - private void createNode(FlagState fs){ - Enumeration allocatingtasks; - EGTaskNode tn; - EGTaskNode target; - FEdge edge; - //the idea is to look at the inedges to find the "parents" nodes. Then create the "children" and link them to the "parents". - if (fs.isSourceNode()){ - //in the case of sourcenode, "parents" are the allocating tasks - for (Iterator inedges = ((Vector)fs.getAllocatingTasks()).iterator(); inedges.hasNext();){ - String tname = new String(((TaskDescriptor)inedges.next()).getSymbol()); - //the hashkey for source EGTaskNodes is : nextfs+taskname. - String key1 = new String(fs.getTextLabel()+tname); - //get the parent - if (graph.containsKey(key1)){ - tn = (EGTaskNode)graph.get(key1); - } - else{//if not existing, create it - tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname)); - tn.setSource(); - } - //create the children. the key is : nextfs+taskname+previousfs (that ensures that only one node can have that key). - for (Iterator edges = fs.edges(); edges.hasNext();){ - edge = (FEdge)edges.next(); - target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel())); - String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel()); - //mark if is self loop - if (((FlagState)edge.getTarget()).isMarked()){ - target.doSelfLoopMarking(); - } - //check if child already exists. if not, create it. - //link to the parent. - if (graph.containsKey(key2)){ - target = (EGTaskNode)graph.get(key2); - EGEdge newedge=new EGEdge(target); - tn.addEdge(newedge); - } - else { - EGEdge newedge=new EGEdge(target); - tn.addEdge(newedge); + EGTaskNode targetnode=getNode(edge, map, nodes); + EGEdge newedge=new EGEdge(targetnode); + srcnode.addEdge(newedge); } - //put child in graph - graph.put(key2, target); } - //put parent in graph - graph.put(key1, tn); } - } - - for (Iterator inedges = fs.inedges(); inedges.hasNext();){ - //regular case, "parents" are the inedges. - FEdge in=(FEdge)inedges.next(); - if (!in.isProcessed()){ - //the key to search is : nextfs+taskname+previousfs. - String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel()); - tn = (EGTaskNode)graph.get(key1); - //if the TaskNode does not exist, that means that we are in the case of a loop. - //The fs will not be entirely processed, will be put back in the fifo until the TaskNode has finaly been created. - if (tn != null){ - //same process than with the sourcenode. - for (Iterator edges = fs.edges(); edges.hasNext();){ - edge = (FEdge)edges.next(); - target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel())); - String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel()); - if (((String)((FlagState)edge.getTarget()).getTextLabel()).compareTo(fs.getTextLabel())==0){ - target.doSelfLoopMarking(); - } - if (graph.containsKey(key2)){ - target = (EGTaskNode)graph.get(key2); - EGEdge newedge=new EGEdge(target); - tn.addEdge(newedge); - } - else { - EGEdge newedge=new EGEdge(target); - tn.addEdge(newedge); - } - graph.put(key2, target); - } - graph.put(key1, tn); - in.setProcessed(); + for(Iterator init=fs.inedges();init.hasNext();) { + FEdge inedge=(FEdge)init.next(); + EGTaskNode srcnode=getNode(inedge, map, nodes); + for(Iterator outit=fs.edges();outit.hasNext();) { + FEdge outedge=(FEdge)outit.next(); + EGTaskNode dstnode=getNode(outedge, map, nodes); + EGEdge newedge=new EGEdge(dstnode); + srcnode.addEdge(newedge); } } - } - } + + } + return nodes; + } + private EGTaskNode getNode(FEdge fedge, Hashtable map, HashSet nodes) { + if (map.containsKey(fedge)) + return map.get(fedge); + EGTaskNode egnode=new EGTaskNode(fedge.getLabel(), (FlagState) fedge.getSource(), fedge.getTask()); + if (fedge.getTarget()==fedge.getSource()) + egnode.doSelfLoopMarking(); + map.put(fedge, egnode); + nodes.add(egnode); + return egnode; + } + //put the graph into executiongraph - private void adapt(ClassDescriptor cd) { + private void adapt(ClassDescriptor cd, HashSet nodes) { Vector tasknodes = new Vector(); - tasknodes.addAll(graph.values()); + tasknodes.addAll(nodes); executiongraph.put(cd,tasknodes); } + //print the contain of graph - private void test() { + private void test(Hashtable graph) { System.out.println("\nGraph contains :"); Collection c = graph.values(); for ( Iterator it = c.iterator(); it.hasNext();){ @@ -207,30 +106,6 @@ public class ExecutionGraph { } } - //test if a flagstate has been entirely processed - private boolean isFinished(FlagState fs){ - - for (Iterator inedges = fs.inedges(); inedges.hasNext();){ - - FEdge in=(FEdge)inedges.next(); - - if (!in.isProcessed()){ - String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel()); - - if (graph.get(key1)==null){ - //except for the case of self loop, if the pointed tn is not present, fs is not totally processed - if (((String)((FlagState)in.getSource()).getTextLabel()).compareTo(fs.getTextLabel())!=0){ - return false; - } - } - - } - } - return true; - } - - - //********DEBUG //create dot files execution_classname_.dot private void printDOTFile()throws java.io.IOException { Enumeration e = executiongraph.keys(); @@ -262,25 +137,9 @@ public class ExecutionGraph { if (tn.isMultipleParams()) output.println(", color=blue"); output.println("];"); - for(Iterator it2 = tn.edges();it2.hasNext();){ output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((EGEdge)it2.next()).getTarget()).getLabel()+";"); } } } - //********************* - } - - - - - - - - - - - - - diff --git a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java index 27599174..2134b66f 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java @@ -11,12 +11,14 @@ import Util.Edge; public class FEdge extends Edge { private String label; + private TaskDescriptor td; /** Class Constructor * */ - public FEdge(FlagState target, String label) { + public FEdge(FlagState target, String label, TaskDescriptor td) { super(target); this.label = label; + this.td=td; } public String getLabel() { @@ -26,12 +28,18 @@ public class FEdge extends Edge { public int hashCode(){ return target.hashCode()^label.hashCode(); } + + public TaskDescriptor getTask() { + return td; + } public boolean equals(Object o) { if (o instanceof FEdge) { FEdge e=(FEdge)o; - return e.label.equals(label)&& - e.target.equals(target); + if (e.label.equals(label)&& + e.target.equals(target)&& + e.td==td) + return true; } return false; } diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index 4f7078ef..9a781812 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -24,9 +24,6 @@ public class FlagState extends GraphNode { private boolean issourcenode; private Vector tasks; - private boolean marked=false; - - /** Class constructor * Creates a new flagstate with all flags set to false. * @param cd ClassDescriptor @@ -58,18 +55,6 @@ public class FlagState extends GraphNode { return uid; } - public boolean isMarked() { - return marked; - } - - public void doUnmarking() { - marked = false; - } - - public void doMarking() { - marked = true; - } - /** Accessor method * @param fd FlagDescriptor * @return true if the flagstate contains fd else false. @@ -86,23 +71,23 @@ public class FlagState extends GraphNode { return issourcenode; } - /** Sets the flagstate as a source node. + /** Sets the flagstate as a source node. */ - public void setAsSourceNode(){ - if(!issourcenode){ - issourcenode=true; - this.tasks=new Vector(); - } - } - - public void addAllocatingTask(TaskDescriptor task){ - tasks.add(task); - } - - public Vector getAllocatingTasks(){ - return tasks; - } - + public void setAsSourceNode(){ + if(!issourcenode){ + issourcenode=true; + this.tasks=new Vector(); + } + } + + public void addAllocatingTask(TaskDescriptor task){ + tasks.add(task); + } + + public Vector getAllocatingTasks(){ + return tasks; + } + public String toString() { return cd.toString()+getTextLabel(); diff --git a/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java b/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java index 380112ed..4097af97 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java +++ b/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java @@ -6,7 +6,7 @@ import IR.Flat.*; import java.io.*; import Util.Edge; -public class OptionalTaskDescriptor{ +public class OptionalTaskDescriptor { public TaskDescriptor td; public HashSet flagstates; public int depth; @@ -15,30 +15,24 @@ public class OptionalTaskDescriptor{ private static int nodeid=0; private int uid; - protected OptionalTaskDescriptor(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate){ + protected OptionalTaskDescriptor(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate) { this.td = td; this.flagstates = flagstates; this.depth = depth; this.exitfses = new HashSet(); this.predicate = predicate; this.uid = OptionalTaskDescriptor.nodeid++; - } public boolean equals(Object o){ if (o instanceof OptionalTaskDescriptor) { OptionalTaskDescriptor otd = (OptionalTaskDescriptor) o; - /*if (this.td.getSymbol().compareTo(otd.td.getSymbol())==0) - if(this.flagstates.equals(otd.flagstates)) - if(this.predicate.equals(otd.predicate)) - return true; - return false;*/ - if(this.hashCode()==otd.hashCode()) + if (td==otd.td&& + flagstates.equals(otd.flagstates)&& + predicate.equals(otd.predicate)) return true; - return false; } - else return false; - + return false; } public int hashCode() { @@ -52,6 +46,4 @@ public class OptionalTaskDescriptor{ public int getuid() { return uid; } - - } diff --git a/Robust/src/Analysis/TaskStateAnalysis/Predicate.java b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java index b00b8984..51f4cfe6 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/Predicate.java +++ b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java @@ -5,7 +5,7 @@ import IR.Tree.*; import IR.Flat.*; import Util.Edge; -public class Predicate{ +public class Predicate { public Hashtable vardescriptors; public Hashtable> flags; public Hashtable tags; //if there is a tag change, we stop the analysis @@ -17,18 +17,15 @@ public class Predicate{ } public boolean equals(Object o){ - if(o instanceof Predicate){ + if(o instanceof Predicate) { Predicate p = (Predicate) o; - if(this.vardescriptors.equals(p.vardescriptors)) + if(vardescriptors.equals(p.vardescriptors)) return true; - return false; } - else return false; + return false; } public int hashCode(){ return vardescriptors.hashCode(); } - - } diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java index 3a999b4a..36ec073e 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -110,12 +110,11 @@ public class SafetyAnalysis { System.out.println("\t"+classname+ "\n"); //get the graph result of executiongraph class Vector nodes = new Vector(); - nodes = getConcernedClass( classname ); + nodes = getConcernedClass(classname); if(nodes==null) { System.out.println("Impossible to find "+classname+". Unexpected."); continue; - } - else if(nodes.size()==0){ + } else if (nodes.size()==0) { System.out.println("Nothing to do"); continue; } @@ -269,13 +268,13 @@ public class SafetyAnalysis { if (extremity.isMarked() || !((Iterator)extremity.edges()).hasNext()){ if (!((Iterator)extremity.edges()).hasNext()) extremity.mark(); reducedgraph.put(extremity.getuid(), extremity); - } - else { + } else { //do the marking process(extremity); reducedgraph.put(extremity.getuid(), extremity); extremity.mark(); - //calls doGraphMarking recursively with the next nodes as params + //calls doGraphMarking recursively with the next nodes as + //params for( Iterator it = extremity.edges(); it.hasNext(); ){ EGEdge edge = (EGEdge)it.next(); doGraphMarking((EGTaskNode)edge.getTarget()); @@ -705,25 +704,18 @@ public class SafetyAnalysis { private HashSet createIntersection( HashSet A, HashSet B){ HashSet result = new HashSet(); - //HashSet processed = new HashSet(); for(Iterator b_it = B.iterator(); b_it.hasNext();){ OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next(); for(Iterator a_it = A.iterator(); a_it.hasNext();){ OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next(); if(((String)otd_a.td.getSymbol()).compareTo((String)otd_b.td.getSymbol())==0){ - //processed.add(otd_a); - //processed.add(otd_b); - HashSet newfs = new HashSet(); newfs.addAll(otd_a.flagstates); newfs.addAll(otd_b.flagstates); int newdepth = (otd_a.depth < otd_b.depth) ? otd_a.depth : otd_b.depth; OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, newfs, newdepth, combinePredicates(otd_a.predicate, otd_b.predicate)); if(optionaltaskdescriptors.get(processedclass).get(newotd)!=null){ - //System.out.println("OTD found"); - System.out.println("before "+newotd.getuid()); newotd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(newotd); - System.out.println("after "+newotd.getuid()); } else optionaltaskdescriptors.get(processedclass).put(newotd, newotd); result.add(newotd); @@ -731,16 +723,6 @@ public class SafetyAnalysis { } } - /* for(Iterator a_it = A.iterator(); a_it.hasNext();){ - OptionalTaskDescriptor otd = (OptionalTaskDescriptor)a_it.next(); - if(!processed.contains(otd)) - optionaltaskdescriptors.get(processedclass).remove(otd); - } - for(Iterator b_it = B.iterator(); b_it.hasNext();){ - OptionalTaskDescriptor otd = (OptionalTaskDescriptor)b_it.next(); - if(!processed.contains(otd)) - optionaltaskdescriptors.get(processedclass).remove(otd); - } */ return result; } @@ -754,7 +736,6 @@ public class SafetyAnalysis { VarDescriptor vd = (VarDescriptor)varit.next(); if(result.vardescriptors.containsKey(vd.getName())) System.out.println("Already in "); else { - //System.out.println("Not already in..."); result.vardescriptors.put(vd.getName(), vd); } } @@ -763,7 +744,6 @@ public class SafetyAnalysis { VarDescriptor vd = (VarDescriptor)varit.next(); HashSet bflags = B.flags.get(vd.getName()); if( bflags == null ){ - //System.out.println("not in B"); continue; } else{ @@ -839,9 +819,6 @@ public class SafetyAnalysis { if (fn1.kind()==FKind.FlatFlagActionNode) { FlatFlagActionNode ffan=(FlatFlagActionNode)fn1; if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { - //*** - //System.out.println("TASKEXIT"); - //*** HashSet tempset = new HashSet(); for(Iterator it_fs = otd.flagstates.iterator(); it_fs.hasNext();){ FlagState fstemp = (FlagState)it_fs.next(); @@ -852,16 +829,12 @@ public class SafetyAnalysis { fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp)); } } - //System.out.println("new flag : "+fstemp.getTextLabel()); tempset.add(fstemp); } result.add(tempset); continue; // avoid queueing the return node if reachable } }else if (fn1.kind()==FKind.FlatReturnNode) { - //*** - //System.out.println("RETURN NODE REACHABLE WITHOUT TASKEXITS"); - //*** result.add(otd.flagstates); } @@ -876,8 +849,6 @@ public class SafetyAnalysis { } otd.exitfses=result; } - - } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index c5b626a9..8776df82 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -24,25 +24,25 @@ public class TaskAnalysis { * @param state a flattened State object * @see State */ - public TaskAnalysis(State state, TagAnalysis taganalysis) - { + public TaskAnalysis(State state, TagAnalysis taganalysis) { this.state=state; this.typeutil=new TypeUtil(state); this.taganalysis=taganalysis; - } - /** Builds a table of flags for each class in the Bristlecone program. - * It creates two hashtables: one which holds the ClassDescriptors and arrays of - * FlagDescriptors as key-value pairs; the other holds the ClassDescriptor and the - * number of external flags for that specific class. + /** Builds a table of flags for each class in the Bristlecone + * program. It creates two hashtables: one which holds the + * ClassDescriptors and arrays of * FlagDescriptors as key-value + * pairs; the other holds the ClassDescriptor and the * number of + * external flags for that specific class. */ private void getFlagsfromClasses() { flags=new Hashtable(); extern_flags = new Hashtable(); - /** Iterate through the classes used in the program to build the table of flags + /** Iterate through the classes used in the program to build + * the table of flags */ for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) { @@ -86,8 +86,7 @@ public class TaskAnalysis { } } } - /** Method which starts up the analysis - * + /** Method which starts up the analysis */ public void taskAnalysis() throws java.io.IOException { @@ -124,7 +123,8 @@ public class TaskAnalysis { sourcenodes.put(fsstartup,fsstartup); toprocess.add(fsstartup); - /** Looping through the flagstates in the toprocess queue to perform the state analysis */ + /** Looping through the flagstates in the toprocess queue to + * perform the state analysis */ while (!toprocess.isEmpty()) { FlagState trigger=toprocess.poll(); createPossibleRuntimeStates(trigger); @@ -157,8 +157,8 @@ private void analyseTasks(FlagState fs) { TaskDescriptor td = (TaskDescriptor)it_tasks.next(); String taskname=td.getSymbol(); - /** counter to keep track of the number of parameters (of the task being analyzed) that - * are satisfied by the flagstate. + /** counter to keep track of the number of parameters (of the + * task being analyzed) that are satisfied by the flagstate. */ int trigger_ctr=0; TempDescriptor temp=null; @@ -168,8 +168,10 @@ private void analyseTasks(FlagState fs) { FlagExpressionNode fen=td.getFlag(td.getParameter(i)); TagExpressionList tel=td.getTag(td.getParameter(i)); - /** Checking to see if the parameter is of the same type/class as the - * flagstate's and also if the flagstate fs triggers the given task*/ + /** Checking to see if the parameter is of the same + * type/class as the flagstate's and also if the + * flagstate fs triggers the given task*/ + if (typeutil.isSuperorType(td.getParamType(i).getClassDesc(),cd) && isTaskTrigger_flag(fen,fs) && isTaskTrigger_tag(tel,fs)) { @@ -209,7 +211,7 @@ private void analyseTasks(FlagState fs) { if (fn1.kind()==FKind.FlatReturnNode) { /* Self edge */ - FEdge newedge=new FEdge(fs, taskname); + FEdge newedge=new FEdge(fs, taskname, td); fs.addEdge(newedge); continue; } else if (fn1.kind()==FKind.FlatFlagActionNode) { @@ -227,7 +229,7 @@ private void analyseTasks(FlagState fs) { } //seen this node already fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit); - FEdge newedge=new FEdge(fs_taskexit,taskname); + FEdge newedge=new FEdge(fs_taskexit,taskname, td); fs.addEdge(newedge); } continue; @@ -374,55 +376,52 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ } /** Returns the flag states for the class descriptor. */ - public Set getFlagStates(ClassDescriptor cd) { + public Set getFlagStates(ClassDescriptor cd) { if (flagstates.containsKey(cd)) - return ((Hashtable)flagstates.get(cd)).keySet(); + return ((Hashtable)flagstates.get(cd)).keySet(); else return null; } private void createPossibleRuntimeStates(FlagState fs) { - ClassDescriptor cd = fs.getClassDescriptor(); - Hashtable sourcenodes=(Hashtable)flagstates.get(cd); - FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd); - int externs=((Integer)extern_flags.get(cd)).intValue(); - - if(externs==0) - return; - - int noOfIterations=(1< sourcenodes=(Hashtable)flagstates.get(cd); + FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd); + int externs=((Integer)extern_flags.get(cd)).intValue(); - FlagState fstemp=fs; + if(externs==0) + return; - for(int i=0; i < externs;i++) { - fstemp=fstemp.setFlag(fd[i],BoolValTable[i]); - } - if (!sourcenodes.containsKey(fstemp)) - toprocess.add(fstemp); - - fstemp=canonicalizeFlagState(sourcenodes,fstemp); - fs.addEdge(new FEdge(fstemp,"Runtime")); - } - } + int noOfIterations=(1<