From ab2c711b8532bed3425f970eee9e013c462ab790 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 15 Apr 2011 22:36:17 +0000 Subject: [PATCH] changes. --- .../SSJava/DefinitelyWrittenCheck.java | 346 ++++++++++++++++++ Robust/src/Analysis/SSJava/FlowDownCheck.java | 37 +- .../src/Analysis/SSJava/SSJavaAnalysis.java | 11 +- Robust/src/IR/State.java | 2 +- Robust/src/IR/Tree/BuildIR.java | 8 + Robust/src/Main/Main.java | 14 +- 6 files changed, 393 insertions(+), 25 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java new file mode 100644 index 00000000..8f743a8a --- /dev/null +++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java @@ -0,0 +1,346 @@ +package Analysis.SSJava; + +import java.util.HashSet; +import java.util.Hashtable; +import java.util.Iterator; +import java.util.Set; + +import Analysis.Loops.LoopFinder; +import Analysis.Loops.Loops; +import IR.ClassDescriptor; +import IR.FieldDescriptor; +import IR.MethodDescriptor; +import IR.Operation; +import IR.State; +import IR.SymbolTable; +import IR.Flat.FKind; +import IR.Flat.FlatFieldNode; +import IR.Flat.FlatLiteralNode; +import IR.Flat.FlatMethod; +import IR.Flat.FlatNode; +import IR.Flat.FlatOpNode; +import IR.Flat.TempDescriptor; + +public class DefinitelyWrittenCheck { + + static State state; + HashSet toanalyze; + + // maintains analysis results in the form of > + private Hashtable>> definitelyWrittenResults; + + public DefinitelyWrittenCheck(State state) { + this.state = state; + this.toanalyze = new HashSet(); + this.definitelyWrittenResults = + new Hashtable>>(); + } + + public void definitelyWrittenCheck() { + + // creating map + SymbolTable classtable = state.getClassSymbolTable(); + toanalyze.addAll(classtable.getValueSet()); + toanalyze.addAll(state.getTaskSymbolTable().getValueSet()); + while (!toanalyze.isEmpty()) { + Object obj = toanalyze.iterator().next(); + ClassDescriptor cd = (ClassDescriptor) obj; + toanalyze.remove(cd); + if (cd.isClassLibrary()) { + // doesn't care about class libraries now + continue; + } + for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { + MethodDescriptor md = (MethodDescriptor) method_it.next(); + FlatMethod fm = state.getMethodFlat(md); + + LoopFinder loopFinder = new LoopFinder(fm); + Loops loops = loopFinder.getRootloop(fm); + Set loopSet = loops.nestedLoops(); + + for (Iterator iterator = loopSet.iterator(); iterator.hasNext();) { + Loops rootLoops = (Loops) iterator.next(); + Set loopEntranceSet = rootLoops.loopEntrances(); + for (Iterator iterator2 = loopEntranceSet.iterator(); iterator2.hasNext();) { + FlatNode loopEnter = (FlatNode) iterator2.next(); + definitelyWrittenForward(loopEnter); + } + } + } + } + + // check if there is a read statement with flag=TRUE + toanalyze.addAll(classtable.getValueSet()); + toanalyze.addAll(state.getTaskSymbolTable().getValueSet()); + while (!toanalyze.isEmpty()) { + Object obj = toanalyze.iterator().next(); + ClassDescriptor cd = (ClassDescriptor) obj; + toanalyze.remove(cd); + if (cd.isClassLibrary()) { + // doesn't care about class libraries now + continue; + } + for (Iterator method_it = cd.getMethods(); method_it.hasNext();) { + MethodDescriptor md = (MethodDescriptor) method_it.next(); + FlatMethod fm = state.getMethodFlat(md); + try { + checkMethodBody(fm); + } catch (Error e) { + System.out.println("Error in " + md); + throw e; + } + } + } + + } + + private void checkMethodBody(FlatMethod fm) { + + Set flatNodesToVisit = new HashSet(); + Set visited = new HashSet(); + flatNodesToVisit.add(fm); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + visited.add(fn); + flatNodesToVisit.remove(fn); + + checkMethodBody_nodeAction(fn); + + // if a new result, schedule forward nodes for analysis + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); + } + } + } + + } + + private void checkMethodBody_nodeAction(FlatNode fn) { + + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + switch (fn.kind()) { + + case FKind.FlatOpNode: { + + FlatOpNode fon = (FlatOpNode) fn; + if (fon.getOp().getOp() == Operation.ASSIGN) { + lhs = fon.getDest(); + rhs = fon.getLeft(); + // read(rhs) + Hashtable> map = + definitelyWrittenResults.get(fn); + if (map != null) { + if (map.get(rhs).get(fn).booleanValue()) { + throw new Error("variable " + rhs + + " was not overwritten in-between the same read statement by the out-most loop."); + } + } + + } + + } + break; + + case FKind.FlatFieldNode: { + + FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); + rhs = ffn.getSrc(); + fld = ffn.getField(); + + } + break; + + case FKind.FlatElementNode: { + + } + break; + + case FKind.FlatSetFieldNode: { + } + break; + + case FKind.FlatSetElementNode: { + + } + break; + + case FKind.FlatCall: { + + } + break; + + } + + } + + private void definitelyWrittenForward(FlatNode entrance) { + + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(entrance); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + + Hashtable> prev = + definitelyWrittenResults.get(fn); + + Hashtable> curr = + new Hashtable>(); + for (int i = 0; i < fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + Hashtable> dwIn = + definitelyWrittenResults.get(nn); + if (dwIn != null) { + mergeResults(curr, dwIn); + } + } + + definitelyWritten_nodeActions(fn, curr, entrance); + + // if a new result, schedule forward nodes for analysis + if (!curr.equals(prev)) { + definitelyWrittenResults.put(fn, curr); + + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + flatNodesToVisit.add(nn); + } + } + } + } + + private void mergeResults(Hashtable> curr, + Hashtable> in) { + + Set inKeySet = in.keySet(); + for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) { + TempDescriptor inKey = (TempDescriptor) iterator.next(); + Hashtable inPair = in.get(inKey); + + Set pairKeySet = inPair.keySet(); + for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) { + FlatNode pairKey = (FlatNode) iterator2.next(); + Boolean inFlag = inPair.get(pairKey); + + Hashtable currPair = curr.get(inKey); + if (currPair == null) { + currPair = new Hashtable(); + curr.put(inKey, currPair); + } + + Boolean currFlag = currPair.get(pairKey); + // by default, flag is set by false + if (currFlag == null) { + currFlag = Boolean.FALSE; + } + currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue()); + currPair.put(pairKey, currFlag); + } + + } + + } + + private void definitelyWritten_nodeActions(FlatNode fn, + Hashtable> curr, FlatNode entrance) { + + if (fn == entrance) { + + Set keySet = curr.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + TempDescriptor key = (TempDescriptor) iterator.next(); + Hashtable pair = curr.get(key); + if (pair != null) { + Set pairKeySet = pair.keySet(); + for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) { + FlatNode pairKey = (FlatNode) iterator2.next(); + pair.put(pairKey, Boolean.TRUE); + } + } + } + + } else { + TempDescriptor lhs; + TempDescriptor rhs; + FieldDescriptor fld; + + switch (fn.kind()) { + + case FKind.FlatOpNode: { + + FlatOpNode fon = (FlatOpNode) fn; + lhs = fon.getDest(); + if (fon.getOp().getOp() == Operation.ASSIGN) { + rhs = fon.getLeft(); + + // read(rhs) + Hashtable gen = curr.get(rhs); + if (gen == null) { + gen = new Hashtable(); + curr.put(rhs, gen); + } + + Boolean currentStatus = gen.get(fn); + if (currentStatus == null) { + gen.put(fn, Boolean.FALSE); + } + } + // write(lhs) + curr.put(lhs, new Hashtable()); + + } + break; + + case FKind.FlatLiteralNode: { + FlatLiteralNode fln = (FlatLiteralNode) fn; + lhs = fln.getDst(); + + // write(lhs) + curr.put(lhs, new Hashtable()); + + } + break; + + case FKind.FlatFieldNode: { + + FlatFieldNode ffn = (FlatFieldNode) fn; + lhs = ffn.getDst(); + rhs = ffn.getSrc(); + fld = ffn.getField(); + + } + break; + + case FKind.FlatElementNode: { + + } + break; + + case FKind.FlatSetFieldNode: { + } + break; + + case FKind.FlatSetElementNode: { + + } + break; + + case FKind.FlatCall: { + + } + break; + + } + } + + } + +} diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index ac4899c5..4fbcf36f 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -25,7 +25,6 @@ import IR.Tree.AssignmentNode; import IR.Tree.BlockExpressionNode; import IR.Tree.BlockNode; import IR.Tree.BlockStatementNode; -import IR.Tree.ContinueBreakNode; import IR.Tree.CreateObjectNode; import IR.Tree.DeclarationNode; import IR.Tree.ExpressionNode; @@ -46,10 +45,9 @@ public class FlowDownCheck { static State state; HashSet toanalyze; Hashtable td2loc; // mapping from 'type descriptor' - // to 'location' + // to 'location' Hashtable id2cd; // mapping from 'locID' to 'class - - // descriptor' + // descriptor' public FlowDownCheck(State state) { this.state = state; @@ -329,11 +327,8 @@ public class FlowDownCheck { condLoc = checkLocationFromExpressionNode(md, nametable, isn.getCondition(), condLoc); glbInputSet.add(condLoc); - System.out.println(isn.getCondition().printNode(0) + ":::condLoc=" + condLoc); - CompositeLocation locTrueBlock = checkLocationFromBlockNode(md, nametable, isn.getTrueBlock()); glbInputSet.add(locTrueBlock); - System.out.println(isn.getTrueBlock().printNode(0) + ":::trueLoc=" + locTrueBlock); // here, the location of conditional block should be higher than the // location of true/false blocks @@ -702,7 +697,7 @@ public class FlowDownCheck { private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, CompositeLocation loc) { - ClassDescriptor localCD = md.getClassDesc(); + ClassDescriptor cd = md.getClassDesc(); boolean postinc = true; if (an.getOperation().getBaseOp() == null @@ -711,16 +706,27 @@ public class FlowDownCheck { postinc = false; CompositeLocation destLocation = - checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(localCD)); + checkLocationFromExpressionNode(md, nametable, an.getDest(), new CompositeLocation(cd)); - CompositeLocation srcLocation = new CompositeLocation(localCD); + CompositeLocation srcLocation = new CompositeLocation(cd); if (!postinc) { - srcLocation = new CompositeLocation(localCD); + srcLocation = new CompositeLocation(cd); srcLocation = checkLocationFromExpressionNode(md, nametable, an.getSrc(), srcLocation); - if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, localCD)) { + + if (!CompositeLattice.isGreaterThan(srcLocation, destLocation, cd)) { throw new Error("The value flow from " + srcLocation + " to " + destLocation + " does not respect location hierarchy on the assignment " + an.printNode(0)); } + } else { + destLocation = + srcLocation = checkLocationFromExpressionNode(md, nametable, an.getDest(), srcLocation); + + if (!((Set) state.getCd2LocationPropertyMap().get(cd)).contains(destLocation + .getLocation(cd).getLocIdentifier())) { + throw new Error("Location " + destLocation + " is not allowed to have spinning values at " + + cd.getSourceFileName() + ":" + an.getNumLine()); + } + } return destLocation; @@ -995,6 +1001,13 @@ public class FlowDownCheck { if (priorityLoc1.getLocIdentifier().equals(priorityLoc2.getLocIdentifier())) { // have the same level of local hierarchy + + if (((Set) state.getCd2LocationPropertyMap().get(cd)).contains(priorityLoc1 + .getLocIdentifier())) { + // this location can be spinning + return ComparisonResult.GREATER; + } + } else if (locationOrder.isGreaterThan(priorityLoc1.getLocIdentifier(), priorityLoc2.getLocIdentifier())) { // if priority loc of compLoc1 is higher than compLoc2 diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 68065bf8..c77d4911 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -1,23 +1,24 @@ package Analysis.SSJava; -import java.util.HashSet; - import IR.State; public class SSJavaAnalysis { public static final String DELTA = "delta"; State state; - HashSet toanalyze; public SSJavaAnalysis(State state) { this.state = state; } - public void doCheck() { + public void doFlowDownCheck() { FlowDownCheck checker = new FlowDownCheck(state); checker.flowDownCheck(); - // doMoreAnalysis(); + } + + public void doLoopCheck() { + DefinitelyWrittenCheck checker = new DefinitelyWrittenCheck(state); + checker.definitelyWrittenCheck(); } } diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 93072f1a..6f4f8694 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -365,7 +365,7 @@ public class State { } public Hashtable getCd2LocationPropertyMap(){ - return cd2locationOrderMap; + return cd2locationPropertyMap; } } diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java index 2f0277a1..5014d877 100644 --- a/Robust/src/IR/Tree/BuildIR.java +++ b/Robust/src/IR/Tree/BuildIR.java @@ -522,6 +522,14 @@ public void parseInitializers(ClassDescriptor cn){ } } if(spinLocSet.size()>0){ + //checking if location is actually defined in the hierarchy + for (Iterator iterator = spinLocSet.iterator(); iterator.hasNext();) { + String locID = (String) iterator.next(); + if(!locOrder.containsKey(locID)){ + throw new Error("Error: The spinning location '"+ + locID + "' is not defined in the hierarchy of the class '"+cd +"'."); + } + } state.addLocationPropertySet(cd, spinLocSet); } state.addLocationOrder(cd, locOrder); diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index ba31b33f..d487f99a 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -441,13 +441,6 @@ public class Main { tu.createFullTable(); State.logEvent("Done Creating TypeUtil"); - // SSJava - if(state.SSJAVA){ - ssjava.doCheck(); - } - - - BuildFlat bf=new BuildFlat(state,tu); bf.buildFlat(); State.logEvent("Done Building Flat"); @@ -470,6 +463,13 @@ public class Main { } CallGraph callgraph=state.TASK?new CallGraph(state, tu):new JavaCallGraph(state, tu); + + // SSJava + if(state.SSJAVA){ + ssjava.doFlowDownCheck(); + ssjava.doLoopCheck(); + State.logEvent("Done SSJava Checking"); + } if (state.OPTIMIZE) { CopyPropagation cp=new CopyPropagation(); -- 2.34.1