import Util.Edge;
public class SafetyAnalysis {
- private Hashtable executiongraph;
- private Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> safeexecution; //to use to build code
- private State state;
- private TaskAnalysis taskanalysis;
- private Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> optionaltaskdescriptors;
- private Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>> fstotimap;
-
- private ClassDescriptor processedclass;
-
- public Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> getResult() {
- return safeexecution;
+ private Hashtable executiongraph;
+ private Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> safeexecution; //to use to build code
+ private State state;
+ private TaskAnalysis taskanalysis;
+ private Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> optionaltaskdescriptors;
+ private Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>> fstotimap;
+
+ private ClassDescriptor processedclass;
+
+ public Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> getResult() {
+ return safeexecution;
+ }
+
+ public Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> 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*/
+
+ /*Constructor*/
+ public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis) {
+ this.executiongraph = executiongraph;
+ this.safeexecution = new Hashtable();
+ this.state = state;
+ this.taskanalysis = taskanalysis;
+ this.optionaltaskdescriptors = new Hashtable();
+ this.fstotimap=new Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>>();
+ }
+
+ /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */
+
+ private Hashtable<FlagState, Set<EGTaskNode>> buildMap(ClassDescriptor cd) {
+ Hashtable<FlagState, Set<EGTaskNode>> table=new Hashtable<FlagState, Set<EGTaskNode>>();
+ 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<EGTaskNode>());
+ table.get(node.getFS()).add(node);
+ }
}
+ return table;
+ }
+
+
+ public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskDescriptor td, int index) {
+ return fstotimap.get(fs).get(new TaskIndex(td, index));
+ }
+
+ public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskIndex ti) {
+ return fstotimap.get(fs).get(ti);
+ }
+
+ public Set<TaskIndex> getTaskIndex(FlagState fs) {
+ return fstotimap.get(fs).keySet();
+ }
- public Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> getOptionalTaskDescriptors() {
- return optionaltaskdescriptors;
+
+ /* Builds map of fs -> set of fs that depend on this fs */
+
+ private Hashtable<FlagState, Set<FlagState>> buildUseMap(ClassDescriptor cd) {
+ Hashtable<FlagState, Set<FlagState>> table=new Hashtable<FlagState, Set<FlagState>>();
+ 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<FlagState>());
+ table.get(node.getPostFS()).add(node.getFS());
+ }
}
+ return table;
+ }
+
+ public void doAnalysis() {
+ Enumeration classit=taskanalysis.flagstates.keys();
+
+ while (classit.hasMoreElements()) {
+ ClassDescriptor cd=(ClassDescriptor)classit.nextElement();
+ if (!executiongraph.containsKey(cd))
+ continue;
+ Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd=new Hashtable<FlagState, Set<OptionalTaskDescriptor>>();
+ safeexecution.put(cd, fstootd);
+
+ optionaltaskdescriptors.put(cd, new Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>());
+
+ Hashtable<FlagState, Set<EGTaskNode>> fstoegmap=buildMap(cd);
+ Hashtable<FlagState, Set<FlagState>> fsusemap=buildUseMap(cd);
- /* 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) {
- this.executiongraph = executiongraph;
- this.safeexecution = new Hashtable();
- this.state = state;
- this.taskanalysis = taskanalysis;
- this.optionaltaskdescriptors = new Hashtable();
- this.fstotimap=new Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>>();
+ HashSet<FlagState> tovisit=new HashSet<FlagState>();
+ tovisit.addAll(taskanalysis.getFlagStates(cd));
+
+ 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<EGTaskNode> nodeset=fstoegmap.get(fs);
+ analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit);
+ }
}
-
- /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */
-
- private Hashtable<FlagState, Set<EGTaskNode>> buildMap(ClassDescriptor cd) {
- Hashtable<FlagState, Set<EGTaskNode>> table=new Hashtable<FlagState, Set<EGTaskNode>>();
- 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<EGTaskNode>());
- table.get(node.getFS()).add(node);
+ printTEST();
+ }
+
+ public void analyzeFS(FlagState fs, Set<EGTaskNode> egset, Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd, Hashtable<FlagState, Set<FlagState>> fsusemap, HashSet<FlagState> tovisit) {
+ Hashtable<TaskIndex, Set<OptionalTaskDescriptor>> timap=new Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>();
+ Set<TaskIndex> tiselfloops=new HashSet<TaskIndex>();
+
+ for(Iterator<EGTaskNode> egit=egset.iterator(); egit.hasNext();) {
+ EGTaskNode egnode=egit.next();
+ Set<OptionalTaskDescriptor> setotd;
+ if (egnode.isOptional()) {
+ setotd=new HashSet<OptionalTaskDescriptor>();
+ HashSet<FlagState> enterfsset=new HashSet<FlagState>();
+ 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);
+ }
+ setotd.add(newotd);
+ } else if (tagChange(egnode)) {
+ //Conservatively handle tag changes
+ setotd=new HashSet<OptionalTaskDescriptor>();
+ } else if(egnode.isMultipleParams()) {
+ if( goodMultiple(egnode)){
+ Predicate p=returnPredicate(egnode);
+ Set<OptionalTaskDescriptor> oldsetotd;
+ if (fstootd.containsKey(egnode.getPostFS()))
+ oldsetotd=fstootd.get(egnode.getPostFS());
+ else
+ oldsetotd=new HashSet<OptionalTaskDescriptor>();
+ setotd=new HashSet<OptionalTaskDescriptor>();
+ for(Iterator<OptionalTaskDescriptor> 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<OptionalTaskDescriptor>();
}
- return table;
+ } else {
+ if (fstootd.containsKey(egnode.getPostFS()))
+ setotd=fstootd.get(egnode.getPostFS());
+ else
+ setotd=new HashSet<OptionalTaskDescriptor>();
+ }
+ TaskIndex ti=egnode.isRuntime() ? new TaskIndex() : new TaskIndex(egnode.getTD(), egnode.getIndex());
+ if (!ti.runtime) {
+ //runtime edges don't do anything...don't have to take
+ //them, can't predict when we can.
+ if (state.selfloops.contains(egnode.getTD().getSymbol())) {
+ System.out.println("Self loop for: "+egnode.getTD()+" "+egnode.getIndex());
+ if (timap.containsKey(ti)) {
+ if (egnode.getPostFS()!=fs) {
+ if (tiselfloops.contains(ti)) {
+ //dump old self loop
+ timap.put(ti, setotd);
+ tiselfloops.remove(ti);
+ } else {
+ //standard and case
+ timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
+ }
+ }
+ } else {
+ //mark as self loop
+ timap.put(ti, setotd);
+ if (egnode.getPostFS()==fs) {
+ tiselfloops.add(ti);
+ }
+ }
+ } else if (timap.containsKey(ti)) {
+ //AND case
+ timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
+ } else {
+ timap.put(ti, setotd);
+ }
+ }
}
-
- public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskDescriptor td, int index) {
- return fstotimap.get(fs).get(new TaskIndex(td, index));
+ //Combine all options
+ HashSet<OptionalTaskDescriptor> set=new HashSet<OptionalTaskDescriptor>();
+ for(Iterator<Set<OptionalTaskDescriptor>> it=timap.values().iterator(); it.hasNext();) {
+ Set<OptionalTaskDescriptor> otdset=it.next();
+ set.addAll(otdset);
}
- public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskIndex ti) {
- return fstotimap.get(fs).get(ti);
+ 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));
+ }
}
+ fstotimap.put(fs, timap);
+ }
- public Set<TaskIndex> getTaskIndex(FlagState fs) {
- return fstotimap.get(fs).keySet();
+ 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
- /* Builds map of fs -> set of fs that depend on this fs */
+ private boolean goodMultiple(EGTaskNode tn) {
+ TaskDescriptor td = tn.getTD();
+ FlatMethod fm = state.getMethodFlat(td);
+ TempDescriptor tmp=fm.getParameter(tn.getIndex());
- private Hashtable<FlagState, Set<FlagState>> buildUseMap(ClassDescriptor cd) {
- Hashtable<FlagState, Set<FlagState>> table=new Hashtable<FlagState, Set<FlagState>>();
- 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<FlagState>());
- table.get(node.getPostFS()).add(node.getFS());
- }
+ Set<FlatNode> nodeset=fm.getNodeSet();
+
+ for(Iterator<FlatNode> 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 table;
+ }
}
+ return true;
+ }
- public void doAnalysis() {
- Enumeration classit=taskanalysis.flagstates.keys();
-
- while (classit.hasMoreElements()) {
- ClassDescriptor cd=(ClassDescriptor)classit.nextElement();
- if (!executiongraph.containsKey(cd))
- continue;
- Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd=new Hashtable<FlagState, Set<OptionalTaskDescriptor>>();
- safeexecution.put(cd, fstootd);
-
- optionaltaskdescriptors.put(cd, new Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>());
-
- Hashtable<FlagState, Set<EGTaskNode>> fstoegmap=buildMap(cd);
- Hashtable<FlagState, Set<FlagState>> fsusemap=buildUseMap(cd);
-
- HashSet<FlagState> tovisit=new HashSet<FlagState>();
- tovisit.addAll(taskanalysis.getFlagStates(cd));
-
- 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<EGTaskNode> nodeset=fstoegmap.get(fs);
- analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit);
- }
- }
- printTEST();
+ private Predicate returnPredicate(EGTaskNode tn) {
+ Predicate result = new Predicate();
+ TaskDescriptor td = tn.getTD();
+ for(int i=0; i<td.numParameters(); i++) {
+ if(i!=tn.getIndex()) {
+ VarDescriptor vd = td.getParameter(i);
+ result.vardescriptors.add(vd);
+ HashSet<FlagExpressionNode> flaglist = new HashSet<FlagExpressionNode>();
+ flaglist.add(td.getFlag(vd));
+ result.flags.put(vd, flaglist);
+ if (td.getTag(vd)!=null)
+ result.tags.put(vd, td.getTag(vd));
+ }
}
+ return result;
+ }
- public void analyzeFS(FlagState fs, Set<EGTaskNode> egset, Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd, Hashtable<FlagState, Set<FlagState>> fsusemap, HashSet<FlagState> tovisit) {
- Hashtable<TaskIndex, Set<OptionalTaskDescriptor>> timap=new Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>();
- Set<TaskIndex> tiselfloops=new HashSet<TaskIndex>();
-
- for(Iterator<EGTaskNode> egit=egset.iterator();egit.hasNext();) {
- EGTaskNode egnode=egit.next();
- Set<OptionalTaskDescriptor> setotd;
- if (egnode.isOptional()) {
- setotd=new HashSet<OptionalTaskDescriptor>();
- HashSet<FlagState> enterfsset=new HashSet<FlagState>();
- 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);
- }
- setotd.add(newotd);
- } else if (tagChange(egnode)) {
- //Conservatively handle tag changes
- setotd=new HashSet<OptionalTaskDescriptor>();
- } else if(egnode.isMultipleParams()) {
- if( goodMultiple(egnode)){
- Predicate p=returnPredicate(egnode);
- Set<OptionalTaskDescriptor> oldsetotd;
- if (fstootd.containsKey(egnode.getPostFS()))
- oldsetotd=fstootd.get(egnode.getPostFS());
- else
- oldsetotd=new HashSet<OptionalTaskDescriptor>();
- setotd=new HashSet<OptionalTaskDescriptor>();
- for(Iterator<OptionalTaskDescriptor> 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<OptionalTaskDescriptor>();
- }
- } else {
- if (fstootd.containsKey(egnode.getPostFS()))
- setotd=fstootd.get(egnode.getPostFS());
- else
- setotd=new HashSet<OptionalTaskDescriptor>();
- }
- TaskIndex ti=egnode.isRuntime()?new TaskIndex():new TaskIndex(egnode.getTD(), egnode.getIndex());
- if (!ti.runtime) {
- //runtime edges don't do anything...don't have to take
- //them, can't predict when we can.
- if (state.selfloops.contains(egnode.getTD().getSymbol())) {
- System.out.println("Self loop for: "+egnode.getTD()+" "+egnode.getIndex());
- if (timap.containsKey(ti)) {
- if (egnode.getPostFS()!=fs) {
- if (tiselfloops.contains(ti)) {
- //dump old self loop
- timap.put(ti, setotd);
- tiselfloops.remove(ti);
- } else {
- //standard and case
- timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
- }
- }
- } else {
- //mark as self loop
- timap.put(ti, setotd);
- if (egnode.getPostFS()==fs) {
- tiselfloops.add(ti);
- }
- }
- } else if (timap.containsKey(ti)) {
- //AND case
- timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
- } else {
- timap.put(ti, setotd);
- }
- }
- }
+ 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;
+ }
- //Combine all options
- HashSet<OptionalTaskDescriptor> set=new HashSet<OptionalTaskDescriptor>();
- for(Iterator<Set<OptionalTaskDescriptor>> it=timap.values().iterator();it.hasNext();) {
- Set<OptionalTaskDescriptor> otdset=it.next();
- set.addAll(otdset);
- }
+ ////////////////////
+ /* 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<FlagState> processed=new Vector<FlagState>();
- 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));
+ 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));
}
- }
- fstotimap.put(fs, timap);
- }
- 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);
+ 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<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ 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);
}
+ }
}
- }
- 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<FlatNode> nodeset=fm.getNodeSet();
-
- for(Iterator<FlatNode> 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
- }
+ //Process sets next
+ for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext();) {
+ TempTagPair ttp=(TempTagPair)it_ttp.next();
+
+ if (temp==ttp.getTemp()) {
+ Vector<FlagState> oldprocess=processed;
+ processed=new Vector<FlagState>();
+
+ 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
}
- return true;
- }
-
- private Predicate returnPredicate(EGTaskNode tn){
- Predicate result = new Predicate();
- TaskDescriptor td = tn.getTD();
- for(int i=0; i<td.numParameters(); i++) {
- if(i!=tn.getIndex()) {
- VarDescriptor vd = td.getParameter(i);
- result.vardescriptors.add(vd);
- HashSet<FlagExpressionNode> flaglist = new HashSet<FlagExpressionNode>();
- flaglist.add(td.getFlag(vd));
- result.flags.put(vd, flaglist);
- if (td.getTag(vd)!=null)
- result.tags.put(vd, td.getTag(vd));
- }
+ } else if (fn1.kind()==FKind.FlatReturnNode) {
+ result.add(otd.enterflagstates);
+ }
+
+ /* Queue other nodes past this one */
+ for(int i=0; i<fn1.numNext(); i++) {
+ FlatNode fnext=fn1.getNext(i);
+ if (!discovered.contains(fnext)) {
+ discovered.add(fnext);
+ nodestack.push(fnext);
}
- 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);
+ otd.exitfses=result;
+ }
+
+ private void printTEST() {
+ 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 otd_it = availabletasks.iterator(); otd_it.hasNext();){
+ OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
+ System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
+ System.out.println("\t\twith flags :");
+ for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
+ System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
+ }
+ System.out.println("\t\tand exitflags :");
+ for(Iterator fseshash = otd.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 = otd.predicate;
+ System.out.println("\t\tPredicate constraints :");
+ Collection c = predicate.vardescriptors;
+ for(Iterator varit = c.iterator(); varit.hasNext();){
+ VarDescriptor vard = (VarDescriptor)varit.next();
+ System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
+ }
+ System.out.println("\t\t------------");
}
- 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);
- }
+ }
+
+ System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
+ Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
+ for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){
+ OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
+ System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
+ System.out.println("\t\twith flags :");
+ for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
+ System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
}
- return result;
- }
+ System.out.println("\t\tand exitflags :");
+ for(Iterator fseshash = otd.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 = otd.predicate;
+ System.out.println("\t\tPredicate contains :");
+ Collection c = predicate.vardescriptors;
+ for(Iterator varit = c.iterator(); varit.hasNext();){
+ VarDescriptor vard = (VarDescriptor)varit.next();
+ System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
+ HashSet temphash = predicate.flags.get(vard.getName());
+ if(temphash == null) System.out.println("null hashset");
+ else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
- ////////////////////
- /* 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<FlagState> processed=new Vector<FlagState>();
-
- 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<FlagState> oldprocess=processed;
- processed=new Vector<FlagState>();
-
- 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<FlagState> oldprocess=processed;
- processed=new Vector<FlagState>();
-
- 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<fn1.numNext();i++) {
- FlatNode fnext=fn1.getNext(i);
- if (!discovered.contains(fnext)) {
- discovered.add(fnext);
- nodestack.push(fnext);
- }
- }
}
- otd.exitfses=result;
+ System.out.println("\t\t------------");
+ }
}
+ }
- private void printTEST(){
- 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 otd_it = availabletasks.iterator(); otd_it.hasNext();){
- OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
- System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
- System.out.println("\t\twith flags :");
- for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
- System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
- }
- System.out.println("\t\tand exitflags :");
- for(Iterator fseshash = otd.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 = otd.predicate;
- System.out.println("\t\tPredicate constraints :");
- Collection c = predicate.vardescriptors;
- for(Iterator varit = c.iterator(); varit.hasNext();){
- VarDescriptor vard = (VarDescriptor)varit.next();
- System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
- }
- System.out.println("\t\t------------");
- }
- }
-
- System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
- Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
- for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){
- OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
- System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
- System.out.println("\t\twith flags :");
- for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
- System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
- }
- System.out.println("\t\tand exitflags :");
- for(Iterator fseshash = otd.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 = otd.predicate;
- System.out.println("\t\tPredicate contains :");
- Collection c = predicate.vardescriptors;
- for(Iterator varit = c.iterator(); varit.hasNext();){
- VarDescriptor vard = (VarDescriptor)varit.next();
- System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
- HashSet temphash = predicate.flags.get(vard.getName());
- if(temphash == null) System.out.println("null hashset");
- else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
-
- }
- System.out.println("\t\t------------");
- }
+ /*check if there has been a tag Change*/
+ private boolean tagChange(EGTaskNode tn) {
+ if(tn.getTD() == null) return false; //to be fixed
+ FlatMethod fm = state.getMethodFlat(tn.getTD());
+ FlatNode fn = (FlatNode)fm;
+
+ Stack nodestack=new Stack();
+ HashSet discovered=new HashSet();
+ nodestack.push(fm);
+ discovered.add(fm);
+
+ //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) {
+ Iterator it_ttp=ffan.getTempTagPairs();
+ if(it_ttp.hasNext()){
+ System.out.println("Tag change detected in Task "+tn.getName());
+ return true;
+ } else continue; // avoid queueing the return node if reachable
}
- }
-
- /*check if there has been a tag Change*/
- private boolean tagChange(EGTaskNode tn){
- if(tn.getTD() == null) return false;//to be fixed
- FlatMethod fm = state.getMethodFlat(tn.getTD());
- FlatNode fn = (FlatNode)fm;
-
- Stack nodestack=new Stack();
- HashSet discovered=new HashSet();
- nodestack.push(fm);
- discovered.add(fm);
-
- //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) {
- Iterator it_ttp=ffan.getTempTagPairs();
- if(it_ttp.hasNext()){
- System.out.println("Tag change detected in Task "+tn.getName());
- return true;
- }
- else continue; // avoid queueing the return node if reachable
- }
- }
-
- /* Queue other nodes past this one */
- for(int i=0;i<fn1.numNext();i++) {
- FlatNode fnext=fn1.getNext(i);
- if (!discovered.contains(fnext)) {
- discovered.add(fnext);
- nodestack.push(fnext);
- }
- }
+ }
+
+ /* Queue other nodes past this one */
+ for(int i=0; i<fn1.numNext(); i++) {
+ FlatNode fnext=fn1.getNext(i);
+ if (!discovered.contains(fnext)) {
+ discovered.add(fnext);
+ nodestack.push(fnext);
}
- return false;
+ }
}
+ return false;
+ }
- /////////DEBUG
- /*Thoose two tasks create the dot file named markedgraph.dot */
-
- private void createDOTFile(String classname, Collection v) throws java.io.IOException {
- java.io.PrintWriter output;
- File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
- FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
- output = new java.io.PrintWriter(dotstream, true);
- output.println("digraph dotvisitor {");
- output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
- output.println("\tedge [fontsize=6];");
- traverse(output, v);
- output.println("}\n");
- }
-
- private void traverse(java.io.PrintWriter output, Collection v) {
- EGTaskNode tn;
-
- for(Iterator it1 = v.iterator(); it1.hasNext();){
- tn = (EGTaskNode)it1.next();
- output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
- if (tn.isOptional()){
- if (tn.isMultipleParams())
- output.println(", shape = tripleoctagon");
- else
- output.println(", shape=doubleoctagon");
- } else if (tn.isMultipleParams())
- output.println(", shape=octagon");
- output.println("];");
-
- for(Iterator it2 = tn.edges();it2.hasNext();){
- EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
- output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");
- }
- }
+ /////////DEBUG
+ /*Thoose two tasks create the dot file named markedgraph.dot */
+
+ private void createDOTFile(String classname, Collection v) throws java.io.IOException {
+ java.io.PrintWriter output;
+ File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
+ FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
+ output = new java.io.PrintWriter(dotstream, true);
+ output.println("digraph dotvisitor {");
+ output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
+ output.println("\tedge [fontsize=6];");
+ traverse(output, v);
+ output.println("}\n");
+ }
+
+ private void traverse(java.io.PrintWriter output, Collection v) {
+ EGTaskNode tn;
+
+ for(Iterator it1 = v.iterator(); it1.hasNext();){
+ tn = (EGTaskNode)it1.next();
+ output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
+ if (tn.isOptional()){
+ if (tn.isMultipleParams())
+ output.println(", shape = tripleoctagon");
+ else
+ output.println(", shape=doubleoctagon");
+ } else if (tn.isMultipleParams())
+ output.println(", shape=octagon");
+ output.println("];");
+
+ for(Iterator it2 = tn.edges(); it2.hasNext();){
+ EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
+ output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");
+ }
}
+ }
}
projects / IRC.git / blobdiff