+ private void makeConflictGraph(FlatMethod fm) {
+
+ Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add(fm);
+
+ Set<FlatNode> visited = new HashSet<FlatNode>();
+
+ while (!flatNodesToVisit.isEmpty()) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove(fn);
+ visited.add(fn);
+
+ Stack<FlatSESEEnterNode> seseStack = rblockRel.getRBlockStacks(fm, fn);
+ assert seseStack != null;
+
+ if (!seseStack.isEmpty()) {
+
+ // Add Stall Node of current program statement
+
+ ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
+ if (conflictGraph == null) {
+ conflictGraph = new ConflictGraph();
+ }
+
+ conflictGraph_nodeAction(fn, seseStack.peek());
+
+ }
+
+ // 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 conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
+
+ switch (fn.kind()) {
+
+ case FKind.FlatSESEEnterNode: {
+
+ FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
+
+ if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
+ Set<TempDescriptor> invar_set = fsen.getInVarSet();
+ ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
+ if (conflictGraph == null) {
+ conflictGraph = new ConflictGraph();
+ }
+
+ // collects effects set
+ EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
+ Iterator iter=effectsAnalysis.iteratorTaintEffectPairs();
+ while(iter.hasNext()){
+ Entry entry=(Entry)iter.next();
+ Taint taint=(Taint)entry.getKey();
+ Set<Effect> effects=(Set<Effect>)entry.getValue();
+ if(taint.getSESE().equals(currentSESE)){
+ Iterator<Effect> eIter=effects.iterator();
+ while (eIter.hasNext()) {
+ Effect effect = eIter.next();
+ if (taint.getSESE().equals(currentSESE)) {
+ conflictGraph.addLiveInNodeEffect(taint, effect);
+ }
+ }
+ }
+
+ }
+
+ if (conflictGraph.id2cn.size() > 0) {
+ sese2conflictGraph.put(currentSESE.getParent(), conflictGraph);
+ }
+ }
+ }
+ break;
+ }
+
+ }
+
+ private void calculateConflicts() {
+ // decide fine-grain edge or coarse-grain edge among all vertexes by
+ // pair-wise comparison
+
+ Iterator<FlatNode> seseIter = sese2conflictGraph.keySet().iterator();
+ while (seseIter.hasNext()) {
+ FlatNode sese = seseIter.next();
+ ConflictGraph conflictGraph = sese2conflictGraph.get(sese);
+ conflictGraph.analyzeConflicts();
+ sese2conflictGraph.put(sese, conflictGraph);
+ }
+ }
+
+ private void writeConflictGraph() {
+ Enumeration<FlatNode> keyEnum = sese2conflictGraph.keys();
+ while (keyEnum.hasMoreElements()) {
+ FlatNode key = (FlatNode) keyEnum.nextElement();
+ ConflictGraph cg = sese2conflictGraph.get(key);
+ try {
+ if (cg.hasConflictEdge()) {
+ cg.writeGraph("ConflictGraphFor" + key, false);
+ }
+ } catch (IOException e) {
+ System.out.println("Error writing");
+ System.exit(0);
+ }
+ }
+ }
+
+ private void synthesizeLocks() {
+ Set<Entry<FlatNode, ConflictGraph>> graphEntrySet = sese2conflictGraph.entrySet();
+ for (Iterator iterator = graphEntrySet.iterator(); iterator.hasNext();) {
+ Entry<FlatNode, ConflictGraph> graphEntry = (Entry<FlatNode, ConflictGraph>) iterator.next();
+ FlatNode sese = graphEntry.getKey();
+ ConflictGraph conflictGraph = graphEntry.getValue();
+ calculateCovering(conflictGraph);
+ }
+ }
+
+ private void calculateCovering(ConflictGraph conflictGraph) {
+ uniqueLockSetId = 0; // reset lock counter for every new conflict graph
+ HashSet<ConflictEdge> fineToCover = new HashSet<ConflictEdge>();
+ HashSet<ConflictEdge> coarseToCover = new HashSet<ConflictEdge>();
+ HashSet<SESELock> lockSet = new HashSet<SESELock>();
+
+ Set<ConflictEdge> tempCover = conflictGraph.getEdgeSet();
+ for (Iterator iterator = tempCover.iterator(); iterator.hasNext();) {
+ ConflictEdge conflictEdge = (ConflictEdge) iterator.next();
+ if (conflictEdge.isCoarseEdge()) {
+ coarseToCover.add(conflictEdge);
+ } else {
+ fineToCover.add(conflictEdge);
+ }
+ }
+
+ HashSet<ConflictEdge> toCover = new HashSet<ConflictEdge>();
+ toCover.addAll(fineToCover);
+ toCover.addAll(coarseToCover);
+
+ while (!toCover.isEmpty()) {
+
+ SESELock seseLock = new SESELock();
+ seseLock.setID(uniqueLockSetId++);
+
+ boolean changed;
+
+ do { // fine-grained edge
+
+ changed = false;
+
+ for (Iterator iterator = fineToCover.iterator(); iterator.hasNext();) {
+
+ int type;
+ ConflictEdge edge = (ConflictEdge) iterator.next();
+ if (seseLock.getConflictNodeSet().size() == 0) {
+ // initial setup
+ if (seseLock.isWriteNode(edge.getVertexU())) {
+ // mark as fine_write
+ if (edge.getVertexU().isStallSiteNode()) {
+ type = ConflictNode.PARENT_WRITE;
+ } else {
+ type = ConflictNode.FINE_WRITE;
+ }
+ seseLock.addConflictNode(edge.getVertexU(), type);
+ } else {
+ // mark as fine_read
+ if (edge.getVertexU().isStallSiteNode()) {
+ type = ConflictNode.PARENT_READ;
+ } else {
+ type = ConflictNode.FINE_READ;
+ }
+ seseLock.addConflictNode(edge.getVertexU(), type);
+ }
+ if (edge.getVertexV() != edge.getVertexU()) {
+ if (seseLock.isWriteNode(edge.getVertexV())) {
+ // mark as fine_write
+ if (edge.getVertexV().isStallSiteNode()) {
+ type = ConflictNode.PARENT_WRITE;
+ } else {
+ type = ConflictNode.FINE_WRITE;
+ }
+ seseLock.addConflictNode(edge.getVertexV(), type);
+ } else {
+ // mark as fine_read
+ if (edge.getVertexV().isStallSiteNode()) {
+ type = ConflictNode.PARENT_READ;
+ } else {
+ type = ConflictNode.FINE_READ;
+ }
+ seseLock.addConflictNode(edge.getVertexV(), type);
+ }
+ }
+ changed = true;
+ seseLock.addConflictEdge(edge);
+ fineToCover.remove(edge);
+ break;// exit iterator loop
+ }// end of initial setup
+
+ ConflictNode newNode;
+ if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
+ // new node has a fine-grained edge to all current node
+ // If there is a coarse grained edge where need a fine edge, it's
+ // okay to add the node
+ // but the edge must remain uncovered.
+
+ changed = true;
+
+ if (seseLock.isWriteNode(newNode)) {
+ if (newNode.isStallSiteNode()) {
+ type = ConflictNode.PARENT_WRITE;
+ } else {
+ type = ConflictNode.FINE_WRITE;
+ }
+ seseLock.setNodeType(newNode, type);
+ } else {
+ if (newNode.isStallSiteNode()) {
+ type = ConflictNode.PARENT_READ;
+ } else {
+ type = ConflictNode.FINE_READ;
+ }
+ seseLock.setNodeType(newNode, type);
+ }
+
+ seseLock.addEdge(edge);
+ Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
+ for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
+ ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
+
+ // mark all fine edges between new node and nodes in the group as
+ // covered
+ if (!conflictEdge.getVertexU().equals(newNode)) {
+ if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
+ changed = true;
+ seseLock.addConflictEdge(conflictEdge);
+ fineToCover.remove(conflictEdge);
+ }
+ } else if (!conflictEdge.getVertexV().equals(newNode)) {
+ if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
+ changed = true;
+ seseLock.addConflictEdge(conflictEdge);
+ fineToCover.remove(conflictEdge);
+ }
+ }
+
+ }
+
+ break;// exit iterator loop
+ }
+ }
+
+ } while (changed);
+ do { // coarse
+ changed = false;
+ int type;
+ for (Iterator iterator = coarseToCover.iterator(); iterator.hasNext();) {
+
+ ConflictEdge edge = (ConflictEdge) iterator.next();
+
+ if (seseLock.getConflictNodeSet().size() == 0) {
+ // initial setup
+ if (seseLock.hasSelfCoarseEdge(edge.getVertexU())) {
+ // node has a coarse-grained edge with itself
+ if (!(edge.getVertexU().isStallSiteNode())) {
+ // and it is not parent
+ type = ConflictNode.SCC;
+ } else {
+ type = ConflictNode.PARENT_COARSE;
+ }
+ seseLock.addConflictNode(edge.getVertexU(), type);
+ } else {
+ if (edge.getVertexU().isStallSiteNode()) {
+ type = ConflictNode.PARENT_COARSE;
+ } else {
+ type = ConflictNode.COARSE;
+ }
+ seseLock.addConflictNode(edge.getVertexU(), type);
+ }
+ if (seseLock.hasSelfCoarseEdge(edge.getVertexV())) {
+ // node has a coarse-grained edge with itself
+ if (!(edge.getVertexV().isStallSiteNode())) {
+ // and it is not parent
+ type = ConflictNode.SCC;
+ } else {
+ type = ConflictNode.PARENT_COARSE;
+ }
+ seseLock.addConflictNode(edge.getVertexV(), type);
+ } else {
+ if (edge.getVertexV().isStallSiteNode()) {
+ type = ConflictNode.PARENT_COARSE;
+ } else {
+ type = ConflictNode.COARSE;
+ }
+ seseLock.addConflictNode(edge.getVertexV(), type);
+ }
+ changed = true;
+ coarseToCover.remove(edge);
+ seseLock.addConflictEdge(edge);
+ break;// exit iterator loop
+ }// end of initial setup
+
+ ConflictNode newNode;
+ if ((newNode = seseLock.getNewNodeConnectedWithGroup(edge)) != null) {
+ // new node has a coarse-grained edge to all fine-read, fine-write,
+ // parent
+ changed = true;
+
+ if (seseLock.hasSelfCoarseEdge(newNode)) {
+ // SCC
+ if (newNode.isStallSiteNode()) {
+ type = ConflictNode.PARENT_COARSE;
+ } else {
+ type = ConflictNode.SCC;
+ }
+ seseLock.setNodeType(newNode, type);
+ } else {
+ if (newNode.isStallSiteNode()) {
+ type = ConflictNode.PARENT_COARSE;
+ } else {
+ type = ConflictNode.COARSE;
+ }
+ seseLock.setNodeType(newNode, type);
+ }
+
+ seseLock.addEdge(edge);
+ Set<ConflictEdge> edgeSet = newNode.getEdgeSet();
+ for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) {
+ ConflictEdge conflictEdge = (ConflictEdge) iterator2.next();
+ // mark all coarse edges between new node and nodes in the group
+ // as covered
+ if (!conflictEdge.getVertexU().equals(newNode)) {
+ if (seseLock.containsConflictNode(conflictEdge.getVertexU())) {
+ changed = true;
+ seseLock.addConflictEdge(conflictEdge);
+ coarseToCover.remove(conflictEdge);
+ }
+ } else if (!conflictEdge.getVertexV().equals(newNode)) {
+ if (seseLock.containsConflictNode(conflictEdge.getVertexV())) {
+ changed = true;
+ seseLock.addConflictEdge(conflictEdge);
+ coarseToCover.remove(conflictEdge);
+ }
+ }
+
+ }
+ break;// exit iterator loop
+ }
+
+ }
+
+ } while (changed);
+ lockSet.add(seseLock);
+
+ toCover.clear();
+ toCover.addAll(fineToCover);
+ toCover.addAll(coarseToCover);
+
+ }
+
+ conflictGraph2SESELock.put(conflictGraph, lockSet);
+ }
+