From 95e1df5e21c9471ad22177d3c4267ec14fa4bfba Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 17 Sep 2007 05:56:15 +0000 Subject: [PATCH] rewrite of William's analysis to clean it up a bit... --- .../Analysis/TaskStateAnalysis/EGEdge.java | 12 +- .../TaskStateAnalysis/EGTaskNode.java | 101 +- .../TaskStateAnalysis/ExecutionGraph.java | 16 +- .../src/Analysis/TaskStateAnalysis/FEdge.java | 13 +- .../OptionalTaskDescriptor.java | 40 +- .../Analysis/TaskStateAnalysis/Predicate.java | 26 +- .../TaskStateAnalysis/SafetyAnalysis.java | 1002 ++++++----------- .../TaskStateAnalysis/TaskAnalysis.java | 20 +- .../Analysis/TaskStateAnalysis/TaskIndex.java | 24 + Robust/src/IR/Flat/BuildCode.java | 54 +- Robust/src/IR/TaskDescriptor.java | 6 +- Robust/src/IR/VarDescriptor.java | 1 - Robust/src/Main/Main.java | 2 +- 13 files changed, 460 insertions(+), 857 deletions(-) create mode 100644 Robust/src/Analysis/TaskStateAnalysis/TaskIndex.java diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java b/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java index 0fe1cd83..12254037 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java +++ b/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java @@ -1,15 +1,17 @@ package Analysis.TaskStateAnalysis; -import IR.*; -import Analysis.TaskStateAnalysis.*; -import IR.Tree.*; -import IR.Flat.*; import java.util.*; import Util.Edge; public class EGEdge extends Edge{ - public EGEdge(EGTaskNode target){ + FlagState fs; + public EGEdge(FlagState fs, EGTaskNode target){ super(target); + this.fs=fs; + } + + public FlagState getFS() { + return fs; } public EGTaskNode getTarget(){ diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java index 5d567fbf..eccb83d1 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java +++ b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java @@ -9,63 +9,42 @@ import Util.GraphNode; public class EGTaskNode extends TaskNode { private boolean source=false; private int loopmarker=0; - private boolean multipleparams=false; - private boolean optional = false; - private boolean marked=false; private boolean tomention=true; - private int type = 0; private FlagState fs; + private FlagState postfs; private TaskDescriptor td; - protected HashSet edges = new HashSet(); - public EGTaskNode(){ - this("default", null, null); - } - - public EGTaskNode(String name){ - this(name, null, null); - } - - public EGTaskNode(String name, FlagState fs){ - this(name, fs, null); - } + private int index; - public EGTaskNode(String name, TaskDescriptor td){ - this(name, null, td); + public EGTaskNode(String name, TaskDescriptor td, FlagState postfs){ + this(name, null, td, -1, postfs); } - public EGTaskNode(String name, FlagState fs, TaskDescriptor td){ + public EGTaskNode(String name, FlagState fs, TaskDescriptor td, int index, FlagState postfs){ super(name); this.fs = fs; this.td = td; + this.index=index; + this.postfs=postfs; } - public int hashCode(){ - return getLabel().hashCode(); + public int getIndex() { + return index; + } + + public FlagState getPostFS() { + return postfs; } - public boolean equals(Object o){ - if(o instanceof EGTaskNode){ - EGTaskNode tn=(EGTaskNode) o; - return tn.getLabel().equals(getLabel()); - } - return false; + public boolean isRuntime() { + return td==null&&getName().equals("Runtime"); } - public HashSet getEdgeSet(){ - return edges; - } - public void addEdge(EGEdge newedge) { - newedge.setSource(this); - edges.add(newedge); - EGTaskNode tonode=newedge.getTarget(); - tonode.inedges.addElement(newedge); + public boolean isOptional() { + return (!isSource()&&td!=null&&td.isOptional(td.getParameter(index))); } - public Iterator edges(){ - return edges.iterator(); - } - + public TaskDescriptor getTD(){ return td; } @@ -100,37 +79,15 @@ public class EGTaskNode extends TaskNode { else return false; } - public void setMultipleParams(){ - multipleparams=true; - } - public boolean isMultipleParams(){ - return multipleparams; + return getTD()!=null&&getTD().numParameters()>1; } - public void setOptional(){ - optional = true; - } - - public boolean isOptional(){ - return optional; - } - - public void mark(){ - marked = true; - } - - public void unMark(){ - marked = false; - } - - public boolean isMarked(){ - return marked; - } - public String getFSName(){ - if(fs == null) return "no flag"; - else return fs.getTextLabel(); + if(fs == null) + return "no flag"; + else + return fs.getTextLabel(); } public FlagState getFS(){ @@ -144,16 +101,4 @@ public class EGTaskNode extends TaskNode { public boolean toMention(){ return tomention; } - - public void setAND(){ - type = 1; - } - - public void setOR(){ - type = 0; - } - - public int type(){ - return type; - } } diff --git a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java index afcff39c..f9296418 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java +++ b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java @@ -52,13 +52,13 @@ public class ExecutionGraph { if(fs.isSourceNode()) { for (Iterator allocit = ((Vector)fs.getAllocatingTasks()).iterator(); allocit.hasNext();) { TaskDescriptor alloctask=(TaskDescriptor)allocit.next(); - EGTaskNode srcnode=new EGTaskNode(alloctask.getSymbol(),alloctask); + EGTaskNode srcnode=new EGTaskNode(alloctask.getSymbol(),alloctask, fs); nodes.add(srcnode); srcnode.setSource(); for (Iterator edges = fs.edges(); edges.hasNext();){ FEdge edge = (FEdge)edges.next(); EGTaskNode targetnode=getNode(edge, map, nodes); - EGEdge newedge=new EGEdge(targetnode); + EGEdge newedge=new EGEdge(fs, targetnode); srcnode.addEdge(newedge); } } @@ -69,7 +69,7 @@ public class ExecutionGraph { for(Iterator outit=fs.edges();outit.hasNext();) { FEdge outedge=(FEdge)outit.next(); EGTaskNode dstnode=getNode(outedge, map, nodes); - EGEdge newedge=new EGEdge(dstnode); + EGEdge newedge=new EGEdge(fs,dstnode); srcnode.addEdge(newedge); } } @@ -81,7 +81,7 @@ public class ExecutionGraph { 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()); + EGTaskNode egnode=new EGTaskNode(fedge.getLabel(), (FlagState) fedge.getSource(), fedge.getTask(), fedge.getIndex(), (FlagState) fedge.getTarget()); if (fedge.getTarget()==fedge.getSource()) egnode.doSelfLoopMarking(); map.put(fedge, egnode); @@ -91,7 +91,7 @@ public class ExecutionGraph { //put the graph into executiongraph private void adapt(ClassDescriptor cd, HashSet nodes) { - Vector tasknodes = new Vector(); + HashSet tasknodes = new HashSet(); tasknodes.addAll(nodes); executiongraph.put(cd,tasknodes); } @@ -115,7 +115,7 @@ public class ExecutionGraph { } private void createDOTFile(ClassDescriptor cd) throws java.io.IOException { - Vector v = (Vector)executiongraph.get(cd); + Set s = (Set)executiongraph.get(cd); java.io.PrintWriter output; File dotfile_flagstates= new File("execution"+cd.getSymbol()+".dot"); FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true); @@ -123,11 +123,11 @@ public class ExecutionGraph { output.println("digraph dotvisitor {"); output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); output.println("\tedge [fontsize=6];"); - traverse(output, v); + traverse(output, s); output.println("}\n"); } - private void traverse(java.io.PrintWriter output, Vector v) { + private void traverse(java.io.PrintWriter output, Set v) { EGTaskNode tn; for(Iterator it1 = v.iterator(); it1.hasNext();){ diff --git a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java index 2134b66f..19b4e5df 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java @@ -12,13 +12,15 @@ public class FEdge extends Edge { private String label; private TaskDescriptor td; + private int parameterindex; /** Class Constructor * */ - public FEdge(FlagState target, String label, TaskDescriptor td) { + public FEdge(FlagState target, String label, TaskDescriptor td, int parameterindex) { super(target); this.label = label; this.td=td; + this.parameterindex=parameterindex; } public String getLabel() { @@ -32,17 +34,20 @@ public class FEdge extends Edge { public TaskDescriptor getTask() { return td; } + + public int getIndex() { + return parameterindex; + } public boolean equals(Object o) { if (o instanceof FEdge) { FEdge e=(FEdge)o; if (e.label.equals(label)&& e.target.equals(target)&& - e.td==td) + e.td==td&& + e.parameterindex==parameterindex) return true; } return false; } - - } diff --git a/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java b/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java index 4097af97..dcf54601 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java +++ b/Robust/src/Analysis/TaskStateAnalysis/OptionalTaskDescriptor.java @@ -8,41 +8,49 @@ import Util.Edge; public class OptionalTaskDescriptor { public TaskDescriptor td; - public HashSet flagstates; - public int depth; + public HashSet enterflagstates; public HashSet exitfses; public Predicate predicate; private static int nodeid=0; + private int index; private int uid; - - protected OptionalTaskDescriptor(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate) { + + protected OptionalTaskDescriptor(TaskDescriptor td, int index, HashSet enterflagstates, Predicate predicate) { this.td = td; - this.flagstates = flagstates; - this.depth = depth; + this.enterflagstates = enterflagstates; this.exitfses = new HashSet(); this.predicate = predicate; - this.uid = OptionalTaskDescriptor.nodeid++; + this.index=index; } - public boolean equals(Object o){ + public int hashCode() { + return td.hashCode()^enterflagstates.hashCode()^predicate.hashCode()^index; + } + + public boolean equals(Object o) { if (o instanceof OptionalTaskDescriptor) { - OptionalTaskDescriptor otd = (OptionalTaskDescriptor) o; - if (td==otd.td&& - flagstates.equals(otd.flagstates)&& - predicate.equals(otd.predicate)) + OptionalTaskDescriptor otd=(OptionalTaskDescriptor) o; + if (otd.td==td&& + otd.enterflagstates.equals(enterflagstates)&& + otd.predicate.equals(predicate)&& + otd.index==index) return true; } return false; } - - public int hashCode() { - return td.getSymbol().hashCode()+flagstates.hashCode()+predicate.hashCode(); + + public int getIndex() { + return index; } - + public String tostring() { return "Optional task "+td.getSymbol(); } + public void setuid() { + uid=nodeid++; + } + public int getuid() { return uid; } diff --git a/Robust/src/Analysis/TaskStateAnalysis/Predicate.java b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java index 51f4cfe6..7fefe6ec 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/Predicate.java +++ b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java @@ -6,26 +6,28 @@ import IR.Flat.*; import Util.Edge; public class Predicate { - public Hashtable vardescriptors; - public Hashtable> flags; - public Hashtable tags; //if there is a tag change, we stop the analysis + public HashSet vardescriptors; + public Hashtable> flags; + public Hashtable tags; + //if there is a tag change, we stop the analysis public Predicate(){ - this.vardescriptors = new Hashtable(); - this.flags = new Hashtable(); - this.tags = new Hashtable(); + this.vardescriptors = new HashSet(); + this.flags = new Hashtable>(); + this.tags = new Hashtable(); } - public boolean equals(Object o){ - if(o instanceof Predicate) { - Predicate p = (Predicate) o; - if(vardescriptors.equals(p.vardescriptors)) + public boolean equals(Object o) { + if (o instanceof Predicate) { + Predicate p=(Predicate)o; + if (vardescriptors.equals(p.vardescriptors)&& + flags.equals(p.flags)&& + tags.equals(p.tags)) return true; } return false; } - - public int hashCode(){ + public int hashCode() { return vardescriptors.hashCode(); } } diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java index 94c9e76a..ffb118ff 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -11,176 +11,375 @@ import Util.Edge; public class SafetyAnalysis { private Hashtable executiongraph; - private Hashtable> safeexecution; //to use to build code - private static final int OR = 0; - private static final int AND = 1; - private Hashtable reducedgraph; - private String classname; + private Hashtable>> safeexecution; //to use to build code private State state; private TaskAnalysis taskanalysis; - private Hashtable optionaltaskdescriptors; + private Hashtable> optionaltaskdescriptors; private ClassDescriptor processedclass; - public Hashtable> getResult(){ + public Hashtable>> getResult() { return safeexecution; } - public Hashtable getOptionalTaskDescriptors(){ + public Hashtable> getOptionalTaskDescriptors() { return optionaltaskdescriptors; } - /*Structure that stores a possible optional - task which would be safe to execute and - the possible flagstates the object could - be in before executing the task during an - execution without failure*/ + /* Structure that stores a possible optional task which would be + safe to execute and the possible flagstates the object could be + in before executing the task during an execution without + failure*/ /*Constructor*/ - public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis){ + public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis) { this.executiongraph = executiongraph; this.safeexecution = new Hashtable(); - this.reducedgraph = new Hashtable(); this.state = state; this.taskanalysis = taskanalysis; this.optionaltaskdescriptors = new Hashtable(); } - /*finds the the source node in the execution graph*/ - private EGTaskNode findSourceNode(Vector nodes){ - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - if(tn.isSource()){ - return tn; + /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */ + + private Hashtable> buildMap(ClassDescriptor cd) { + Hashtable> table=new Hashtable>(); + for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) { + EGTaskNode node=(EGTaskNode)it.next(); + if (node.getFS()!=null) { + if (!table.containsKey(node.getFS())) + table.put(node.getFS(), new HashSet()); + table.get(node.getFS()).add(node); } } - return null; + return table; } - - /*returns the nodes corresponding to the tasks - that can fire with the object in flagstate - previousflagstate*/ - private Vector findEGTaskNode(String previousflagstate, Vector nodes){ - Vector tns = new Vector(); - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - if(tn.getFSName().compareTo(previousflagstate)==0) - tns.add(tn); - } - if(tns.size() == 0) - return null; - else if (tns.size() > 1){ - for(Iterator it = tns.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - tn.setAND(); + + /* Builds map of fs -> set of fs that depend on this fs */ + + private Hashtable> buildUseMap(ClassDescriptor cd) { + Hashtable> table=new Hashtable>(); + for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) { + EGTaskNode node=(EGTaskNode)it.next(); + if (node.getFS()!=null) { + if (!table.containsKey(node.getPostFS())) + table.put(node.getPostFS(), new HashSet()); + table.get(node.getPostFS()).add(node.getFS()); } } - return tns; - } - - /*returns the executiongraph corresponding to the classname*/ - private Vector getConcernedClass(ClassDescriptor cd){ - if (executiongraph.containsKey(cd)) - return (Vector) executiongraph.get(cd); - else - return null; + return table; } - - /*Actual method used by the compiler. - It computes the analysis for every - possible flagstates of every classes*/ - public void buildPath() throws java.io.IOException { - /*Explore the taskanalysis structure*/ - System.out.println("------- ANALYSING OPTIONAL TASKS -------"); - Enumeration e=taskanalysis.flagstates.keys(); + + public void doAnalysis() { + Enumeration classit=taskanalysis.flagstates.keys(); - while (e.hasMoreElements()) { - System.out.println("\nAnalysing class :"); - processedclass=(ClassDescriptor)e.nextElement(); - classname = processedclass.getSymbol(); - Hashtable newhashtable = new Hashtable(); - optionaltaskdescriptors.put(processedclass, newhashtable); - Hashtable cdhashtable = new Hashtable(); + while (classit.hasMoreElements()) { + ClassDescriptor cd=(ClassDescriptor)classit.nextElement(); + if (!executiongraph.containsKey(cd)) + continue; + Hashtable> fstootd=new Hashtable>(); + safeexecution.put(cd, fstootd); - System.out.println("\t"+classname+ "\n"); - //get the graph result of executiongraph class - Vector nodes = getConcernedClass(processedclass); + optionaltaskdescriptors.put(cd, new Hashtable()); - if(nodes==null) { - System.out.println("Impossible to find "+classname+". Unexpected."); - continue; - } else if (nodes.size()==0) { - System.out.println("Nothing to do"); - continue; - } + Hashtable> fstoegmap=buildMap(cd); + Hashtable> fsusemap=buildUseMap(cd); - //mark the graph - EGTaskNode sourcenode = findSourceNode(nodes); + HashSet tovisit=new HashSet(); + tovisit.addAll(taskanalysis.getFlagStates(cd)); - //skip classes that don't have source nodes - if (sourcenode==null) - continue; + while(!tovisit.isEmpty()) { + FlagState fs=tovisit.iterator().next(); + tovisit.remove(fs); + if (!fstoegmap.containsKey(fs)) + continue;//This FS has no task that can trigger on it + Set nodeset=fstoegmap.get(fs); + analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit); + } + } + printTEST(); + } - doGraphMarking(sourcenode); - createDOTFile( classname ); - reducedgraph.clear(); - - Collection fses = ((Hashtable)taskanalysis.flagstates.get(processedclass)).values(); - Iterator itfses = fses.iterator(); - while (itfses.hasNext()) { - FlagState fs = (FlagState)itfses.next(); - Hashtable fsresult = new Hashtable(); - //get the tasknodes possible to execute with the flagstate before failure - HashSet tempnodes = new HashSet(); - Vector tns = new Vector(); - System.out.println("Analysing "+fs.getTextLabel()); - tns = findEGTaskNode(fs.getTextLabel(), nodes); - if(tns==null) { - System.out.println("\tNo task corresponding, terminal FS"); - continue; + public void analyzeFS(FlagState fs, Set egset, Hashtable> fstootd, Hashtable> fsusemap, HashSet tovisit) { + Hashtable> timap=new Hashtable>(); + + for(Iterator egit=egset.iterator();egit.hasNext();) { + EGTaskNode egnode=egit.next(); + Set setotd; + if (egnode.isOptional()) { + setotd=new HashSet(); + HashSet enterfsset=new HashSet(); + enterfsset.add(fs); + ClassDescriptor cd=fs.getClassDescriptor(); + OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(egnode.getTD(), egnode.getIndex(), enterfsset, new Predicate()); + if(optionaltaskdescriptors.get(cd).containsKey(newotd)) { + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); } - System.out.println("\tProcessing..."); - - //compute the result for all the nodes contained in tns. - //return the intersection of tns that are the same task and union for others. - - HashSet availabletasks = new HashSet(); - availabletasks = computeTns(tns); - - //removeDoubles(availabletasks); - - for(Iterator it = availabletasks.iterator(); it.hasNext();){ - OptionalTaskDescriptor otd = (OptionalTaskDescriptor)it.next(); - resultingFS(otd, classname); + setotd.add(newotd); + } else if (tagChange(egnode)) { + //Conservatively handle tag changes + setotd=new HashSet(); + } else if(egnode.isMultipleParams()) { + if( goodMultiple(egnode)){ + Predicate p=returnPredicate(egnode); + Set oldsetotd; + if (fstootd.containsKey(egnode.getPostFS())) + oldsetotd=fstootd.get(egnode.getPostFS()); + else + oldsetotd=new HashSet(); + setotd=new HashSet(); + for(Iterator otdit=oldsetotd.iterator();otdit.hasNext();) { + OptionalTaskDescriptor oldotd=otdit.next(); + Predicate newp=combinePredicates(oldotd.predicate, p); + OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(oldotd.td, oldotd.getIndex(), oldotd.enterflagstates, newp); + ClassDescriptor cd=fs.getClassDescriptor(); + if(optionaltaskdescriptors.get(cd).containsKey(newotd)) { + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); + } + setotd.add(newotd); + } + } else { + //Can't propagate anything + setotd=new HashSet(); } - - cdhashtable.put(fs, availabletasks); + } else { + if (fstootd.containsKey(egnode.getPostFS())) + setotd=fstootd.get(egnode.getPostFS()); + else + setotd=new HashSet(); + } + + TaskIndex ti=new TaskIndex(egnode.getTD(), egnode.getIndex()); + if (timap.containsKey(ti)) { + //AND case + timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor())); + } else { + timap.put(ti, setotd); + } + } + + //Combine all options + HashSet set=new HashSet(); + for(Iterator> it=timap.values().iterator();it.hasNext();) { + Set otdset=it.next(); + set.addAll(otdset); + } + + if (!fstootd.containsKey(fs)|| + !fstootd.get(fs).equals(set)) { + fstootd.put(fs, set); + //Requeue all flagstates that may use our updated results + if (fsusemap.containsKey(fs)) { + tovisit.addAll(fsusemap.get(fs)); } - - safeexecution.put(processedclass, cdhashtable); - } - putinoptionaltaskdescriptors(); - printTEST(); } - private void putinoptionaltaskdescriptors(){ - Enumeration e = safeexecution.keys(); - while (e.hasMoreElements()) { - ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); - optionaltaskdescriptors.get(cdtemp).clear(); - Hashtable hashtbtemp = safeexecution.get(cdtemp); - Enumeration fses = hashtbtemp.keys(); - while(fses.hasMoreElements()){ - FlagState fs = (FlagState)fses.nextElement(); - HashSet availabletasks = (HashSet)hashtbtemp.get(fs); - for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){ - OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next(); - optionaltaskdescriptors.get(cdtemp).put(otd, otd); + private HashSet createIntersection(Set A, Set B, ClassDescriptor cd){ + HashSet result = 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(otd_a.td==otd_b.td&& + otd_a.getIndex()==otd_b.getIndex()) { + HashSet newfs = new HashSet(); + newfs.addAll(otd_a.enterflagstates); + newfs.addAll(otd_b.enterflagstates); + OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, otd_b.getIndex(), newfs, combinePredicates(otd_a.predicate, otd_b.predicate)); + if(optionaltaskdescriptors.get(cd).get(newotd)!=null){ + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); + } + result.add(newotd); } } } + return result; + } + + // This method returns true if the only parameter whose flag is + // modified is the tracked one + + private boolean goodMultiple(EGTaskNode tn){ + TaskDescriptor td = tn.getTD(); + FlatMethod fm = state.getMethodFlat(td); + TempDescriptor tmp=fm.getParameter(tn.getIndex()); + + Set nodeset=fm.getNodeSet(); + + for(Iterator nodeit=nodeset.iterator();nodeit.hasNext();) { + FlatNode fn=nodeit.next(); + if (fn.kind()==FKind.FlatFlagActionNode) { + FlatFlagActionNode ffan=(FlatFlagActionNode)fn; + if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { + for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) { + TempFlagPair tfp=(TempFlagPair)it_tfp.next(); + TempDescriptor tempd = tfp.getTemp(); + if(tempd!=tmp) + return false; //return false if a taskexit modifies one of the other parameters + } + } + } + } + return true; + } + + private Predicate returnPredicate(EGTaskNode tn){ + Predicate result = new Predicate(); + TaskDescriptor td = tn.getTD(); + for(int i=0; i flaglist = new HashSet(); + flaglist.add(td.getFlag(vd)); + result.flags.put(vd, flaglist); + if (td.getTag(vd)!=null) + result.tags.put(vd, td.getTag(vd)); + } + } + return result; + } + + private Predicate combinePredicates(Predicate A, Predicate B){ + Predicate result = new Predicate(); + result.vardescriptors.addAll(A.vardescriptors); + result.flags.putAll(A.flags); + result.tags.putAll(A.tags); + Collection c = B.vardescriptors; + for(Iterator varit = c.iterator(); varit.hasNext();){//maybe change that + VarDescriptor vd = (VarDescriptor)varit.next(); + if(result.vardescriptors.contains(vd)) + System.out.println("Already in "); + else { + result.vardescriptors.add(vd); + } + } + Collection vardesc = result.vardescriptors; + for(Iterator varit = vardesc.iterator(); varit.hasNext();){ + VarDescriptor vd = (VarDescriptor)varit.next(); + HashSet bflags = B.flags.get(vd); + if( bflags == null ){ + continue; + } else { + if (result.flags.containsKey(vd)) + ((HashSet)result.flags.get(vd)).addAll(bflags); + else + result.flags.put(vd, bflags); + } + TagExpressionList btags = B.tags.get(vd); + if( btags != null ){ + if (result.tags.containsKey(vd)) + System.out.println("Tag found but there should be nothing to do because same tag"); + else + result.tags.put(vd, btags); + } + } + return result; + } + + //////////////////// + /* returns a set of the possible sets of flagstates + resulting from the execution of the optional task. + To do it with have to look for TaskExit FlatNodes + in the IR. + */ + private void resultingFS(OptionalTaskDescriptor otd){ + Stack stack = new Stack(); + HashSet result = new HashSet(); + FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td); + FlatNode fn = (FlatNode)fm; + + Stack nodestack=new Stack(); + HashSet discovered=new HashSet(); + nodestack.push(fm); + discovered.add(fm); + TempDescriptor temp=fm.getParameter(otd.getIndex()); + + //Iterating through the nodes + while(!nodestack.isEmpty()) { + FlatNode fn1 = (FlatNode) nodestack.pop(); + if (fn1.kind()==FKind.FlatFlagActionNode) { + FlatFlagActionNode ffan=(FlatFlagActionNode)fn1; + if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { + HashSet tempset = new HashSet(); + for(Iterator it_fs = otd.enterflagstates.iterator(); it_fs.hasNext();){ + FlagState fstemp = (FlagState)it_fs.next(); + Vector processed=new Vector(); + + for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) { + TempFlagPair tfp=(TempFlagPair)it_tfp.next(); + if (tfp.getTemp()==temp) + fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp)); + } + + processed.add(fstemp); + //Process clears first + + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + for (Enumeration en=oldprocess.elements();en.hasMoreElements();){ + FlagState fsworking=(FlagState)en.nextElement(); + if (!ffan.getTagChange(ttp)){ + processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag()))); + } else processed.add(fsworking); + } + } + } + //Process sets next + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + for (Enumeration en=oldprocess.elements();en.hasMoreElements();){ + FlagState fsworking=(FlagState)en.nextElement(); + if (ffan.getTagChange(ttp)){ + processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag()))); + } else processed.add(fsworking); + } + } + } + //Add to exit states + tempset.addAll(processed); + } + result.add(tempset); + continue; // avoid queueing the return node if reachable + } + } else if (fn1.kind()==FKind.FlatReturnNode) { + result.add(otd.enterflagstates); + } + + /* Queue other nodes past this one */ + for(int i=0;i 1 ){ - nexttn.setMultipleParams(); - } - } - } - - //maybe a little bug to fix - private void testIfRuntime(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - EGEdge edge = (EGEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if( ((String)nexttn.getName()).compareTo("Runtime") == 0 ) - nexttn.setAND(); - } - } - - /*That correspond to the case where it is - not possible for us to choose a path of - execution. The optional task has to be - present in all the possible executions - at this point. So we mark the node as an - AND node.*/ - private void testIfAND(EGTaskNode tn){ - Vector vtemp = new Vector(); - Vector tomark = new Vector(); - for(Iterator edges = tn.edges(); edges.hasNext();){ - EGEdge edge = (EGEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - int contains = 0; - for (Iterator it = vtemp.iterator(); it.hasNext();){ - EGTaskNode nexttn2 = (EGTaskNode)it.next(); - if (nexttn.getName()==nexttn2.getName()){ - contains = 1; - tomark.add(nexttn); - tomark.add(nexttn2); - } - } - if (contains == 0) vtemp.add(nexttn); - } - - for(Iterator it2 = tomark.iterator(); it2.hasNext();) - ((EGTaskNode)it2.next()).setAND(); - } - - //maybe little bug to fix - private void testIfNextIsSelfLoop(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - EGEdge edge = (EGEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if(nexttn.isSelfLoop()) nexttn.setAND(); - } - } - - - /*recursive method that returns a set of OptionalTaskDescriptors - The computation basically consist in returning the - intersection or union of sets depending on the nature - of the node : OR -> UNION - AND -> INTERSECTION - The method also looks for tag changes. - */ - private HashSet determineIfIsSafe(EGTaskNode tn, int depth, HashSet visited, Predicate predicate){ - Predicate temppredicate = new Predicate(); - if(tn == null) return null; - if(!tagChange(tn)){ - if(tn.isOptional()){ - HashSet temp = new HashSet(); - if( tn.isMultipleParams() ){ - if( goodMultiple(tn) ){ - temppredicate = combinePredicates(predicate, returnPredicate(tn)); - System.out.println("Good multiple, Optional "+tn.getName()); - } - else return temp; - } - else temppredicate = combinePredicates(temppredicate, predicate); - //if the tn is optional and there is no more nodes/presence of a loop - //create the OptionalTaskDescriptor and return it as a singleton. - if( !((Iterator)tn.edges()).hasNext() || tn.isSelfLoop()){ - HashSet fstemp = new HashSet(); - fstemp.add(tn.getFS()); - OptionalTaskDescriptor otd = new OptionalTaskDescriptor(tn.getTD(), fstemp, depth, temppredicate); - if(optionaltaskdescriptors.get(processedclass).get(otd)!=null){ - otd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(otd); - } - else optionaltaskdescriptors.get(processedclass).put(otd, otd); - temp.add(otd); - return temp; - } - else if(visited.contains(tn)){ - return temp; - } - //else compute the edges, create the OptionalTaskDescriptor and add it to the set. - else{ - int newdepth = depth + 1; - visited.add(tn); - HashSet newhashset = new HashSet(visited); - HashSet fstemp = new HashSet(); - fstemp.add(tn.getFS()); - OptionalTaskDescriptor otd = new OptionalTaskDescriptor(tn.getTD(), fstemp, depth, temppredicate); - if(optionaltaskdescriptors.get(processedclass).get(otd)!=null){ - otd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(otd); - } - else optionaltaskdescriptors.get(processedclass).put(otd, otd); - temp = computeEdges(tn, newdepth, newhashset, temppredicate); - temp.add(otd); - return temp; - } - } - else{ - HashSet temp = new HashSet(); - if( tn.isMultipleParams() ){ - if( goodMultiple(tn) ){ - temppredicate = combinePredicates(predicate, returnPredicate(tn)); - System.out.println("Good multiple, not Optional "+tn.getName()); - } - else{ - System.out.println("Bad multiple, not Optional "+tn.getName()); - return temp; - } - } - else temppredicate = combinePredicates(temppredicate, predicate); - //if not optional but terminal just return an empty set. - if( !((Iterator)tn.edges()).hasNext() || visited.contains(tn) || tn.isSelfLoop()){ - return temp; - } - //if not terminal return the computation of the edges. - else{ - int newdepth = depth + 1; - visited.add(tn); - HashSet newhashset = new HashSet(visited); - return computeEdges(tn, newdepth, newhashset, temppredicate); - } - } - } - //if there has been a tag change return an empty set. - else{ - HashSet temp = new HashSet(); - return temp; - } - } - - private boolean goodMultiple(EGTaskNode tn){ - TaskDescriptor td = tn.getTD(); - HashSet classes = new HashSet(); - for(int i = 0 ; i evalTaskExitNode(FlatFlagActionNode ffan,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ FlagState fstemp=fs; @@ -380,7 +374,7 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ if (flagstates.containsKey(cd)) return ((Hashtable)flagstates.get(cd)).keySet(); else - return null; + return new HashSet(); } @@ -416,7 +410,7 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ toprocess.add(fstemp); fstemp=canonicalizeFlagState(sourcenodes,fstemp); - fs.addEdge(new FEdge(fstemp,"Runtime", null)); + fs.addEdge(new FEdge(fstemp,"Runtime", null, -1)); } } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskIndex.java b/Robust/src/Analysis/TaskStateAnalysis/TaskIndex.java new file mode 100644 index 00000000..a87f31c6 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskIndex.java @@ -0,0 +1,24 @@ +package Analysis.TaskStateAnalysis; +import IR.TaskDescriptor; + +public class TaskIndex { + TaskDescriptor td; + int index; + public TaskIndex(TaskDescriptor td, int index) { + this.td=td; + this.index=index; + } + + public int hashCode() { + return td.hashCode()^index; + } + + public boolean equals(Object o) { + if (o instanceof TaskIndex) { + TaskIndex ti=(TaskIndex) o; + if (ti.index==index && ti.td==td) + return true; + } + return false; + } +} diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 6f9cea8b..7b5ad170 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -2165,7 +2165,7 @@ public class BuildCode { Predicate predicate = otd.predicate; int predicateindex = 0; //iterate through the classes concerned by the predicate - Collection c_vard = predicate.vardescriptors.values(); + Collection c_vard = predicate.vardescriptors; for(Iterator vard_it = c_vard.iterator(); vard_it.hasNext();){ VarDescriptor vard = (VarDescriptor)vard_it.next(); TypeDescriptor typed = vard.getType(); @@ -2245,57 +2245,10 @@ public class BuildCode { } output.println("};\n"); - //generate the struct for possible exitfses, appeared to be useless - /*HashSet exitfses = otd.exitfses; - int exitindex = 0; - int nbexit = exitfses.size(); - int fsnumber; - - //iterate through possible exits - int nbtotal=0; - for(Iterator exitfseshash = exitfses.iterator(); exitfseshash.hasNext();){ - HashSet temp_hashset = (HashSet)exitfseshash.next(); - fsnumber = 0 ; - output.println("int flag_EXIT"+exitindex+"_OTD"+otd.getuid()+"_"+cdtemp.getSafeSymbol()+"[]={"); - //iterate through possible FSes corresponding to the exit - for(Iterator exfses = temp_hashset.iterator(); exfses.hasNext();){ - FlagState fs = (FlagState)exfses.next(); - fsnumber++; - nbtotal++; - int flagid=0; - for(Iterator flags = fs.getFlags(); flags.hasNext();){ - FlagDescriptor flagd = (FlagDescriptor)flags.next(); - int id=1<<((Integer)flaginfo.get(flagd)).intValue(); - flagid+=id; - } - if(fsnumber!=1) output.print(","); - output.print(flagid); - //do the same for tags. - //maybe not needed because no tag changes tolerated. - } - output.println("};\n"); - - - //store that information in a struct - output.println("struct exitstates exitstates"+exitindex+"_OTD"+otd.getuid()+"_"+cdtemp.getSafeSymbol()+"={"); - output.println(fsnumber+","); - output.println("flag_EXIT"+exitindex+"_OTD"+otd.getuid()+"_"+cdtemp.getSafeSymbol()); - output.println("};\n"); - - exitindex++; - } - - //store the information concerning all exits into an array - output.println("struct exitstates * exitstatesarray_OTD"+otd.getuid()+"_"+cdtemp.getSafeSymbol()+"[]={"); - for( int j = 0; j