From da446b8ec35c1423f6300ca9f2378ace88d7fcbb Mon Sep 17 00:00:00 2001 From: wmontaz Date: Wed, 25 Jul 2007 23:23:13 +0000 Subject: [PATCH] Fix bugs. Fix unexpected results. Add predicates (new struct). --- .../TaskStateAnalysis/ExecutionGraph.java | 4 +- .../TaskStateAnalysis/SafetyAnalysis.java | 577 +++++++++++++----- Robust/src/IR/Flat/BuildCode.java | 36 ++ Robust/src/Main/Main.java | 2 +- Robust/src/Runtime/task.c | 12 +- 5 files changed, 454 insertions(+), 177 deletions(-) diff --git a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java index e38d090d..ad907054 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java +++ b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java @@ -31,11 +31,11 @@ public class ExecutionGraph { public void createExecutionGraph() throws java.io.IOException { /*Explore the taskanalysis structure*/ - + System.out.println("------- BUILDING THE EXECUTION GRAPH -------"); Enumeration e=taskanalysis.flagstates.keys(); while (e.hasMoreElements()) { - System.out.println("\nInto class :"); + System.out.println("\nBuilding class :"); ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); System.out.println("\t"+(cdtemp.getSymbol())+ "\n"); exploreGraph(cdtemp); diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java index 61433660..ff918f53 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -1,6 +1,7 @@ package Analysis.TaskStateAnalysis; import java.util.*; import IR.*; +import IR.Tree.*; import IR.Flat.*; import java.io.*; import java.io.File; @@ -11,13 +12,15 @@ import Util.Edge; public class SafetyAnalysis { private Hashtable executiongraph; - private TreeMap safeexecution; + 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 State state; - + private TaskAnalysis taskanalysis; + //private Hashtable visited; + //private static int analysisid=0; /*Structure that stores a possible optional task which would be safe to execute and @@ -28,51 +31,47 @@ public class SafetyAnalysis { public class MyOptional{ public TaskDescriptor td; public HashSet flagstates; - - protected MyOptional(TaskDescriptor td, HashSet flagstates){ + public int depth; + public HashSet exitfses; + public Predicate predicate; + + protected MyOptional(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate){ this.td = td; this.flagstates = flagstates; + this.depth = depth; + this.exitfses = new HashSet(); + this.predicate = predicate; } public boolean equal(MyOptional myo){ if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0) - if(this.flagstates.equals(myo.flagstates)) - return true; + if(this.depth == myo.depth) + if(this.flagstates.equals(myo.flagstates)) + return true; return false; } } + public class Predicate{ + public HashSet vardescriptors; + public Hashtable> flags; + public Hashtable tags; //if there is a tag change, we stop the analysis + + public Predicate(){ + this.vardescriptors = new HashSet(); + this.flags = new Hashtable(); + this.tags = new Hashtable(); + } + } + /*Constructor*/ - public SafetyAnalysis(Hashtable executiongraph, State state){ + public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis){ this.executiongraph = executiongraph; - this.safeexecution = new TreeMap(); + this.safeexecution = new Hashtable(); this.reducedgraph = new Hashtable(); this.state = state; - } - - - public void unMarkProcessed(Vector nodes){ - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - tn.unMark(); - } - } - - /*returns a hashset of tags used during the analysis */ - private HashSet createNodeTags(EGTaskNode tn){ - HashSet nodetags = new HashSet(); - String flagstate = tn.getFSName(); - String word = new String(); - StringTokenizer st = new StringTokenizer(flagstate); - while (st.hasMoreTokens()){ - word = st.nextToken(); - if (word.compareTo("Tag")==0) - nodetags.add(st.nextToken()); - } - for(Iterator it = nodetags.iterator(); it.hasNext();){ - System.out.println("nodetag :"+it.next()); - } - return nodetags; + this.taskanalysis = taskanalysis; + //this.visited = new Hashtable(); } /*finds the the source node in the execution graph*/ @@ -80,7 +79,6 @@ public class SafetyAnalysis { for(Iterator it = nodes.iterator(); it.hasNext();){ EGTaskNode tn = (EGTaskNode)it.next(); if(tn.isSource()){ - System.out.println("Found Source Node !!"); return tn; } } @@ -118,91 +116,125 @@ public class SafetyAnalysis { } return null; } - - /*Method used for debugging*/ + + /*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(); - byte[] b = new byte[100] ; - HashSet safetasks = new HashSet(); - System.out.println("Enter the Class of the object concerned :"); - int k = System.in.read(b); - classname = new String(b,0,k-1); - System.out.println("Enter the flagstate :"); - k = System.in.read(b); - String previousflagstate = new String(b,0,k-1); - - //get the graph result of executiongraph class - Vector nodes = new Vector(); - nodes = getConcernedClass( classname ); - if(nodes==null) { - System.out.println("Impossible to find "+classname+". Maybe not declared in the source code."); - return; + while (e.hasMoreElements()) { + System.out.println("\nAnalysing class :"); + ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); + classname = cdtemp.getSymbol(); + Hashtable cdhashtable = new Hashtable(); + + System.out.println("\t"+classname+ "\n"); + //get the graph result of executiongraph class + Vector nodes = new Vector(); + nodes = getConcernedClass( classname ); + if(nodes==null) { + System.out.println("Impossible to find "+classname+". Unexpected."); + continue; + } + else if(nodes.size()==0){ + System.out.println("Nothing to do"); + continue; + } + + //mark the graph + EGTaskNode sourcenode = findSourceNode(nodes); + doGraphMarking(sourcenode); + createDOTFile( classname ); + reducedgraph.clear(); + + Collection fses = ((Hashtable)taskanalysis.flagstates.get(cdtemp)).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; + } + 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();){ + MyOptional mo = (MyOptional)it.next(); + resultingFS(mo, classname); + } + + cdhashtable.put(fs, availabletasks); + } + + safeexecution.put(cdtemp, cdhashtable); + } + + printTEST(); + - //mark the graph - EGTaskNode sourcenode = findSourceNode(nodes); - doGraphMarking(sourcenode); - createDOTFile(); - //get the tasknodes possible to execute with the flagstate before failure - HashSet tempnodes = new HashSet(); - Vector tns = new Vector(); - tns = findEGTaskNode(previousflagstate, nodes); - if(tns==null) { - System.out.println("No task corresponding"); - return; - } + } + + private void printTEST(){ - //compute the result for all the nodes contained in tns. - //return the intersection. (because it is not possible to choose) - int counter = 0; - HashSet availabletasks = new HashSet(); - for(Iterator it = tns.iterator(); it.hasNext();){ - counter++; - unMarkProcessed(nodes); - EGTaskNode tn = (EGTaskNode)it.next(); - HashSet nodetags = createNodeTags(tn); - availabletasks = createUnion(determineIfIsSafe(tn, nodetags), availabletasks); - //DEBUG - System.out.println("-----------------------------"); - for(Iterator it2 = availabletasks.iterator(); it2.hasNext();){ - MyOptional mm = (MyOptional)it2.next(); - System.out.println("\t"+mm.td.getSymbol()); - System.out.println("with flags :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println("\t"+((FlagState)it3.next()).getTextLabel()); - } - resultingFS(mm, classname); - System.out.println("-----------------------------"); + Enumeration e = safeexecution.keys(); + while (e.hasMoreElements()) { + ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); + System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n"); + Hashtable hashtbtemp = safeexecution.get(cdtemp); + Enumeration fses = hashtbtemp.keys(); + while(fses.hasMoreElements()){ + FlagState fs = (FlagState)fses.nextElement(); + System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n"); + HashSet availabletasks = (HashSet)hashtbtemp.get(fs); + for(Iterator mos = availabletasks.iterator(); mos.hasNext();){ + MyOptional mm = (MyOptional)mos.next(); + System.out.println("\t\tTASK "+mm.td.getSymbol()+"\n"); + System.out.println("\t\tDepth : "+mm.depth); + System.out.println("\t\twith flags :"); + for(Iterator myfses = mm.flagstates.iterator(); myfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel()); + } + System.out.println("\t\tand exitflags :"); + for(Iterator fseshash = mm.exitfses.iterator(); fseshash.hasNext();){ + HashSet temphs = (HashSet)fseshash.next(); + System.out.println(""); + for(Iterator exfses = temphs.iterator(); exfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel()); + } + } + Predicate predicate = mm.predicate; + System.out.println("\t\tPredicate constains :"); + for(Iterator varit = predicate.vardescriptors.iterator(); varit.hasNext();){ + VarDescriptor vard = (VarDescriptor)varit.next(); + System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol()); + } + System.out.println("\t\t------------"); } - if(counter == 1) safetasks = availabletasks; - else safetasks = createIntersection(availabletasks, safetasks); - } - //DEBUG - System.out.println("----------FINAL--------------"); - for(Iterator it2 = safetasks.iterator(); it2.hasNext();){ - MyOptional mm = (MyOptional)it2.next(); - System.out.println("\t"+mm.td.getSymbol()); - System.out.println("with flags :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println("\t"+((FlagState)it3.next()).getTextLabel()); - } - resultingFS(mm, classname); - System.out.println("-----"); - } - System.out.println("----------FINAL--------------"); - } - - /*Actual method used by the compiler. - It computes the analysis for every - possible flagstates of every classes*/ - public void buildPath(Vector flagstates, ClassDescriptor cd) throws java.io.IOException { + } + } } - /*Marks the executiongraph : - -optionals - -multiple - -AND and OR nodes + -optionals + -multiple + -AND and OR nodes */ private void doGraphMarking(EGTaskNode extremity) throws java.io.IOException{ //detects if there is a loop or no more nodes to explore @@ -225,7 +257,7 @@ public class SafetyAnalysis { private void process(EGTaskNode tn){ testIfOptional(tn); - testIfSameTask(tn); + testIfAND(tn); testIfNextIsSelfLoop(tn); testIfRuntime(tn); testIfMultiple(tn); @@ -267,7 +299,7 @@ public class SafetyAnalysis { present in all the possible executions at this point. So we mark the node as an AND node.*/ - private void testIfSameTask(EGTaskNode tn){ + private void testIfAND(EGTaskNode tn){ Vector vtemp = new Vector(); Vector tomark = new Vector(); for(Iterator edges = tn.edges(); edges.hasNext();){ @@ -286,7 +318,7 @@ public class SafetyAnalysis { } for(Iterator it2 = tomark.iterator(); it2.hasNext();) - ((EGTaskNode)it2.next()).setAND(); + ((EGTaskNode)it2.next()).setAND(); } //maybe little bug to fix @@ -306,41 +338,68 @@ public class SafetyAnalysis { AND -> INTERSECTION The method also looks for tag changes. */ - private HashSet determineIfIsSafe(EGTaskNode tn, HashSet nodetags){ + private HashSet determineIfIsSafe(EGTaskNode tn, int depth, HashSet visited, Predicate predicate){ + Predicate temppredicate = new Predicate(); if(tn == null) return null; - if(!tagChange(tn, nodetags)){ + 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 MyOptional and return it as a singleton. - if( !((Iterator)tn.edges()).hasNext() || tn.isMarked() || tn.isSelfLoop()){ + if( !((Iterator)tn.edges()).hasNext() || tn.isSelfLoop()){ HashSet fstemp = new HashSet(); fstemp.add(tn.getFS()); - MyOptional mo = new MyOptional(tn.getTD(), fstemp); + MyOptional mo = new MyOptional(tn.getTD(), fstemp, depth, temppredicate); temp.add(mo); return temp; } + else if(visited.contains(tn)){ + return temp; + } //else compute the edges, create the MyOptional and add it to the set. else{ - tn.mark(); - temp = computeEdges(tn, nodetags); + int newdepth = depth + 1; + visited.add(tn); + HashSet newhashset = new HashSet(visited); HashSet fstemp = new HashSet(); fstemp.add(tn.getFS()); - MyOptional mo = new MyOptional(tn.getTD(), fstemp); + MyOptional mo = new MyOptional(tn.getTD(), fstemp, depth, temppredicate); + temp = computeEdges(tn, newdepth, newhashset, temppredicate); temp.add(mo); 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() || tn.isMarked() || tn.isSelfLoop()){ - HashSet temp = new HashSet(); + if( !((Iterator)tn.edges()).hasNext() || visited.contains(tn) || tn.isSelfLoop()){ return temp; } //if not terminal return the computation of the edges. else{ - tn.mark(); - return computeEdges(tn, nodetags); + int newdepth = depth + 1; + visited.add(tn); + HashSet newhashset = new HashSet(visited); + return computeEdges(tn, newdepth, newhashset, temppredicate); } } } @@ -350,32 +409,111 @@ public class SafetyAnalysis { return temp; } } + + private boolean goodMultiple(EGTaskNode tn){ + TaskDescriptor td = tn.getTD(); + HashSet classes = new HashSet(); + for(int i = 0 ; inumbertags>0) { if (tagptr==NULL) - goto nextloop; - else if(tagptr->type==TAGTYPE) { + goto nextloop;//that means the object has no tag but that param needs tag + else if(tagptr->type==TAGTYPE) {//one tag struct ___TagDescriptor___ * tag=(struct ___TagDescriptor___*) tagptr; for(i=0;inumbertags;i++) { //slotid is parameter->tagarray[2*i]; @@ -352,7 +352,7 @@ void flagbody(struct ___Object___ *ptr, int flag) { if (tagid!=tagptr->flag) goto nextloop; /*We don't have this tag */ } - } else { + } else {//multiple tags struct ArrayObject * ao=(struct ArrayObject *) tagptr; for(i=0;inumbertags;i++) { //slotid is parameter->tagarray[2*i]; @@ -394,7 +394,7 @@ void enqueuetasks(struct parameterwrapper *parameter, struct parameterwrapper *p struct taskdescriptor * task=parameter->task; - RuntimeHashadd(parameter->objectset, (int) ptr, (int) prevptr); + RuntimeHashadd(parameter->objectset, (int) ptr, (int) prevptr);//this add the object to parameterwrapper /* Add enqueued object to parameter vector */ taskpointerarray[parameter->slot]=ptr; @@ -428,7 +428,7 @@ void enqueuetasks(struct parameterwrapper *parameter, struct parameterwrapper *p tpd->numParameters=numiterators+1; tpd->parameterArray=RUNMALLOC(sizeof(void *)*(numiterators+1)); for(j=0;j<=numiterators;j++) - tpd->parameterArray[j]=taskpointerarray[j]; + tpd->parameterArray[j]=taskpointerarray[j];//store the actual parameters /* Enqueue task */ if (!gencontains(failedtasks, tpd)&&!gencontains(activetasks,tpd)) { @@ -605,6 +605,8 @@ void executetasks() { #endif genputtable(failedtasks,currtpd,currtpd); restorecheckpoint(currtpd->task->numParameters, currtpd->parameterArray, checkpoint, forward, reverse); + /*where we have to insert the code for optional tasks + all the pointers I need are in currtpd->parameterArray */ freeRuntimeHash(forward); freeRuntimeHash(reverse); freemalloc(); -- 2.34.1