1 package Analysis.OoOJava;
3 import java.util.HashSet;
4 import java.util.Hashtable;
5 import java.util.Iterator;
6 import java.util.LinkedList;
8 import java.util.Stack;
9 import java.util.Map.Entry;
11 import Analysis.CallGraph.CallGraph;
12 import IR.MethodDescriptor;
16 import IR.Flat.FlatMethod;
17 import IR.Flat.FlatNode;
18 import IR.Flat.FlatSESEEnterNode;
19 import IR.Flat.FlatSESEExitNode;
21 public class RBlockStatusAnalysis {
27 RBlockRelationAnalysis rra;
29 // per method-per node-rblock stacks
30 protected Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>> fm2statusmap;
32 public RBlockStatusAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph,
33 RBlockRelationAnalysis rra) {
35 this.typeUtil = typeUtil;
36 this.callGraph = callGraph;
40 new Hashtable<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>>();
42 MethodDescriptor mdSourceEntry = typeUtil.getMain();
43 FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
45 // add all methods transitively reachable from the
46 // source's main to set for analysis
47 Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
49 descriptorsToAnalyze.add(mdSourceEntry);
51 analyzeMethods(descriptorsToAnalyze);
53 // analyzeMethodsDebug(descriptorsToAnalyze);
56 protected void analyzeMethods(Set<MethodDescriptor> descriptorsToAnalyze) {
58 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
59 while (mdItr.hasNext()) {
60 FlatMethod fm = state.getMethodFlat(mdItr.next());
62 Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
63 computeRBlockStatus(fm);
65 fm2statusmap.put(fm, fn2seseStatus);
69 public Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> computeRBlockStatus(
72 Hashtable<FlatNode, Stack<FlatSESEEnterNode>> seseStacks =
73 new Hashtable<FlatNode, Stack<FlatSESEEnterNode>>();
75 Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
76 new Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>();
78 LinkedList<FlatNode> flatNodesToVisit = new LinkedList<FlatNode>();
79 flatNodesToVisit.add(fm);
81 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
82 seseStacks.put(fm, seseStackFirst);
84 while (!flatNodesToVisit.isEmpty()) {
85 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
86 FlatNode fn = fnItr.next();
88 Hashtable<FlatSESEEnterNode, Boolean> prevResult = fn2seseStatus.get(fn);
90 Hashtable<FlatSESEEnterNode, Boolean> currentResult =
91 new Hashtable<FlatSESEEnterNode, Boolean>();
93 for (int i = 0; i < fn.numPrev(); i++) {
94 FlatNode prevFlatNode = fn.getPrev(i);
95 Hashtable<FlatSESEEnterNode, Boolean> incoming = fn2seseStatus.get(prevFlatNode);
96 if (incoming != null) {
97 merge(currentResult, incoming);
101 flatNodesToVisit.remove(fn);
103 nodeActions(fn, fm, currentResult);
105 // if we have a new result, schedule forward nodes for
107 if (prevResult == null || !currentResult.equals(prevResult)) {
108 fn2seseStatus.put(fn, currentResult);
109 for (int i = 0; i < fn.numNext(); i++) {
110 FlatNode nn = fn.getNext(i);
111 flatNodesToVisit.addFirst(nn);
116 return fn2seseStatus;
119 private void merge(Hashtable<FlatSESEEnterNode, Boolean> current,
120 Hashtable<FlatSESEEnterNode, Boolean> incoming) {
122 Iterator inIter = incoming.entrySet().iterator();
123 while (inIter.hasNext()) {
124 Entry inEntry = (Entry) inIter.next();
125 FlatSESEEnterNode seseContaining = (FlatSESEEnterNode) inEntry.getKey();
126 Boolean isAfter = (Boolean) inEntry.getValue();
128 Boolean currentIsAfter = current.get(seseContaining);
129 if (currentIsAfter == null || currentIsAfter == Boolean.FALSE) {
130 current.put(seseContaining, isAfter);
136 public boolean isInCriticalRegion(FlatMethod fmContaining, FlatNode fn) {
137 FlatSESEEnterNode seseContaining = rra.getRBlockStacks(fmContaining, fn).peek();
138 Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> statusMap =
139 fm2statusmap.get(fmContaining);
140 Hashtable<FlatSESEEnterNode, Boolean> status = statusMap.get(fn);
142 if(status.get(seseContaining).booleanValue()==true){
143 System.out.println(fn+" is in the critical region in according to "+seseContaining);
146 return status.get(seseContaining).booleanValue();
149 protected void nodeActions(FlatNode fn, FlatMethod fm,
150 Hashtable<FlatSESEEnterNode, Boolean> status) {
153 case FKind.FlatSESEExitNode: {
154 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
155 FlatSESEEnterNode fsen = fsexn.getFlatEnter();
156 if (fsen.getParent() != null) {
157 status.put(fsen.getParent(), Boolean.TRUE);
163 if (!(fn instanceof FlatMethod)) {
164 Stack<FlatSESEEnterNode> seseStack = rra.getRBlockStacks(fm, fn);
165 if (!seseStack.isEmpty()) {
166 FlatSESEEnterNode currentParent = seseStack.peek();
167 if (!status.containsKey(currentParent)) {
168 status.put(currentParent, Boolean.FALSE);
182 protected void analyzeMethodsDebug(Set<MethodDescriptor> descriptorsToAnalyze) {
184 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
185 while (mdItr.hasNext()) {
186 FlatMethod fm = state.getMethodFlat(mdItr.next());
192 protected void printStatusMap(FlatMethod fm) {
194 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
195 flatNodesToVisit.add(fm);
197 Set<FlatNode> visited = new HashSet<FlatNode>();
199 while (!flatNodesToVisit.isEmpty()) {
200 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
201 FlatNode fn = fnItr.next();
203 flatNodesToVisit.remove(fn);
206 System.out.println("------------------");
207 System.out.println("fn=" + fn);
208 System.out.println(fm2statusmap.get(fm).get(fn));
210 for (int i = 0; i < fn.numNext(); i++) {
211 FlatNode nn = fn.getNext(i);
213 if (!visited.contains(nn)) {
214 flatNodesToVisit.add(nn);