001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2007 New York University
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019:
020: package xtc.lang.p2;
021:
022: import java.util.ArrayList;
023: import java.util.HashMap;
024: import java.util.HashSet;
025: import java.util.Iterator;
026: import java.util.List;
027: import java.util.Map;
028: import java.util.Set;
029:
030: import xtc.tree.GNode;
031: import xtc.tree.Node;
032: import xtc.tree.Visitor;
033:
034: import xtc.util.Pair;
035: import xtc.util.Runtime;
036:
037: /**
038: * A visitor to perform concurrency analysis on Overlog programs.
039: *
040: * @author Robert Soule
041: * @version $Revision: 1.7 $
042: */
043: public final class ConcurrencyAnalyzer extends Visitor {
044:
045: // =========================================================================
046:
047: public class MaterializationChecker extends Visitor {
048:
049: /**
050: * Create a new MaterializationChecker. Visits the AST
051: * to ensure that the right hand side of a rule has no
052: * more than one non-materialized tuple.
053: *
054: */
055: public MaterializationChecker() {
056: // do nothing
057: }
058:
059: /**
060: * Process the specified translation unit.
061: *
062: * @param unit The translation unit.
063: */
064: public void analyze(Node unit) {
065: dispatch(unit);
066: }
067:
068: /**
069: * Visit all nodes in the AST.
070: */
071: public void visit(final GNode n) {
072: for (Object o : n) {
073: if (o instanceof Node) {
074: dispatch((Node) o);
075: } else if (Node.isList(o)) {
076: iterate(Node.toList(o));
077: }
078: }
079: }
080:
081: public void visitRule(final GNode n) {
082: String ruleName = "unknown";
083: if ("RuleIdentifier".equals(n.getNode(0).getName())) {
084: ruleName = n.getNode(0).getString(0);
085: }
086: int numNonMaterialized = 0;
087: Node fixpointNodeStart = null;
088: // dispatch to the "actions"
089: for (Node child : n.<Node> getList(2)) {
090: if ("Tuple".equals(child.getName())) {
091: String name = child.getNode(0).getString(0);
092: if (!materialized.contains(name)) {
093: // special case for periodic
094: if (!name.equals("periodic")) {
095: fixpointNodeStart = child;
096: numNonMaterialized++;
097: }
098: }
099: }
100: }
101: if (numNonMaterialized > 1) {
102: runtime.error("Rule " + ruleName + " has "
103: + numNonMaterialized
104: + " non-materialized tuples", n);
105: } else if (numNonMaterialized != 0) {
106: fixpointInitiaters.add(fixpointNodeStart);
107: }
108: }
109: }
110:
111: // =========================================================================
112:
113: /** The runtime. */
114: protected final Runtime runtime;
115:
116: /** The names of tuples declared materialized */
117: private Set<String> materialized;
118:
119: /** The nodes that can initiate a fixpoint (i.e. events) */
120: private Set<Node> fixpointInitiaters;
121:
122: /** Map a node to the tuples involved in its fixpoint computation */
123: private Map<Node, List<Node>> closureMap;
124:
125: /** Map a node to the tuples in its read set */
126: private Map<Node, Set<Node>> readSets;
127:
128: /** Map a node to the tuples in its write set */
129: private Map<Node, Set<Node>> writeSets;
130:
131: /**
132: * Create a new Overlog analyzer.
133: *
134: * @param runtime The runtime.
135: */
136: public ConcurrencyAnalyzer(Runtime runtime) {
137: this .runtime = runtime;
138: materialized = new HashSet<String>();
139: fixpointInitiaters = new HashSet<Node>();
140: closureMap = new HashMap<Node, List<Node>>();
141: readSets = new HashMap<Node, Set<Node>>();
142: writeSets = new HashMap<Node, Set<Node>>();
143: }
144:
145: /**
146: * Process the specified translation unit.
147: *
148: * @param unit The translation unit.
149: * @return root of the AST
150: */
151: public Node analyze(Node unit) {
152: dispatch(unit);
153: new MaterializationChecker().analyze(unit);
154: unit = computeFixpoints(unit);
155: return unit;
156: }
157:
158: // =========================================================================
159:
160: /**
161: * Return the event node of a rule if the rule is an external rule.
162: * An external rule is a rule that results in a tuple being sent to
163: * a non-local node. If the rule is not an external rule, this function
164: * returns null.
165: *
166: * @param n a rule tuple node
167: * @return the event node or null
168: */
169: private Node getExternal(final Node n) {
170: // @fixme this method of recognizing external tuples only recognizes if the
171: // names have changed. It doesn't check to see if the value has been passed.
172: // i.e. tuple1(@NI, C) :- (tuple2(@SI, C), NI := SI.
173: final String eventLocation = n.getNode(1).<Node> getList(1)
174: .get(0).getNode(0).getString(0);
175: // dispatch to the "actions"
176: for (Node child : n.<Node> getList(2)) {
177: if ("Tuple".equals(child.getName())) {
178: String actionLocation = child.<Node> getList(1).get(0)
179: .getNode(0).getString(0);
180: if (!eventLocation.equals(actionLocation)) {
181: return n.getNode(1);
182: }
183: }
184: }
185: return null;
186: }
187:
188: /**
189: * Return the event node of a rule if the rule is a materialized rule.
190: * An materialized rule is a rule that results in a tuple being stored to
191: * a local node. If the rule is not an materialized rule, this function
192: * returns null.
193: *
194: * @param n a rule tuple node
195: * @return the event node or null
196: */
197: private Node getMaterialized(final Node n) {
198: final String name = n.getNode(1).getNode(0).getString(0);
199: if (!materialized.contains(name)) {
200: return null;
201: }
202: return n.getNode(1).<Node> getList(1).get(0);
203: }
204:
205: /**
206: * Modifies the root node of an Overlog AST by adding fact tuples
207: * for the read and write set of all the program's fixpoints.
208: *
209: * @param root The root node of the AST
210: * @param The modified root of the AST
211: *
212: */
213: private Node computeFixpoints(Node root) {
214: Iterator<Node> fixpointIterator = fixpointInitiaters.iterator();
215: while (fixpointIterator.hasNext()) {
216: Node node = fixpointIterator.next();
217: Set<Node> visited = new HashSet<Node>();
218: computeFixpoint(node, node, visited);
219: root = addReadSet(root, node);
220: root = addWriteSet(root, node);
221: }
222: return root;
223: }
224:
225: /**
226: * Modifies the root node of an Overlog AST by adding fact tuples
227: * for the read set of a single fixpoint.
228: *
229: * @param root The root node of the AST
230: * @param n The tuple that initiates the fixpoint
231: * @param The modified root of the AST
232: *
233: */
234: private Node addReadSet(Node root, final Node n) {
235: if (!readSets.containsKey(n)) {
236: return root;
237: }
238: Set<Node> reads = readSets.get(n);
239: for (Node read : reads) {
240: root = addReadWriteFact(root, n.getNode(0).getString(0),
241: read.getNode(0).getString(0), "R");
242: }
243: return root;
244: }
245:
246: /**
247: * Modifies the root node of an Overlog AST by adding fact tuples
248: * for the write set of a single fixpoint.
249: *
250: * @param root The root node of the AST
251: * @param n The tuple that initiates the fixpoint
252: * @param The modified root of the AST
253: *
254: */
255: private Node addWriteSet(Node root, final Node n) {
256: if (!writeSets.containsKey(n)) {
257: return root;
258: }
259: Set<Node> writes = writeSets.get(n);
260: for (Node write : writes) {
261: root = addReadWriteFact(root, n.getNode(0).getString(0),
262: write.getNode(0).getString(0), "W");
263: }
264: return root;
265: }
266:
267: /**
268: * Appends a nodes to the AST which contain information about the read write
269: * write sets of the fixpoints in this tree.
270: *
271: * @param root The root node of the AST
272: * @param fixpointName The name of the node that initiates the fixpoint
273: * @param tupleName The name of the node in the read or write set
274: * @param The type of fact being added, which is either "R" for read
275: * or "W" for write.
276: */
277: private Node addReadWriteFact(Node root, final String fixpointName,
278: final String tupleName, final String type) {
279: final Node e = GNode.create("StringConstant", fixpointName);
280: final Node a = GNode.create("StringConstant", tupleName);
281: final Node t = GNode.create("StringConstant", type);
282: Pair<Node> childList;
283: childList = new Pair<Node>(e);
284: childList.add(a);
285: childList.add(t);
286: final Node identifier = GNode.create("RuleIdentifier",
287: new String("concurrent"));
288: final Node tuple = GNode.create("Tuple", identifier, childList);
289: final Node fact = GNode.create("GenericFact", tuple);
290: root = GNode.ensureVariable(GNode.cast(root));
291: root = root.add(fact);
292: return root;
293: }
294:
295: /**
296: * Performs a depth first search to discover all nodes reachable by
297: * a fixpoint. This is a recursive function which adds to its visited
298: * set parameter.
299: *
300: * @param n The node currently being explored in the search.
301: * @param fixpointStart The node that initiates the fixpoint
302: * @param visited The set of nodes already visited in this search.
303: * When calling this function, the set should be empty.
304: *
305: */
306: private void computeFixpoint(Node n, final Node fixpointStart,
307: Set<Node> visited) {
308: if (visited.contains(n)) {
309: return;
310: }
311: visited.add(n);
312: if (!closureMap.containsKey(n)) {
313: return;
314: }
315: List<Node> rules = closureMap.get(n);
316: for (Node rule : rules) {
317: Pair<Node> actions = rule.getList(2);
318: for (Node action : actions) {
319: if ("Tuple".equals(action.getName())) {
320: if (action != fixpointStart) {
321: if (readSets.containsKey(fixpointStart)) {
322: readSets.get(fixpointStart).add(action);
323: } else {
324: Set<Node> reads = new HashSet<Node>();
325: reads.add(action);
326: readSets.put(fixpointStart, reads);
327: }
328: }
329: }
330: }
331: Node tmp = getExternal(rule);
332: if (tmp != null) {
333: if (writeSets.containsKey(fixpointStart)) {
334: writeSets.get(fixpointStart).add(rule.getNode(1));
335: } else {
336: Set<Node> writes = new HashSet<Node>();
337: writes.add(rule.getNode(1));
338: writeSets.put(fixpointStart, writes);
339: return;
340: }
341: }
342: tmp = getMaterialized(rule);
343: if (tmp != null) {
344: if (writeSets.containsKey(fixpointStart)) {
345: writeSets.get(fixpointStart).add(rule.getNode(1));
346: } else {
347: Set<Node> writes = new HashSet<Node>();
348: writes.add(rule.getNode(1));
349: writeSets.put(fixpointStart, writes);
350: return;
351: }
352: }
353: computeFixpoint(rule.getNode(1), fixpointStart, visited);
354: }
355: }
356:
357: // =========================================================================
358:
359: /**
360: * Visit all nodes in the AST.
361: */
362: public void visit(final GNode n) {
363: for (Object o : n) {
364: if (o instanceof Node) {
365: dispatch((Node) o);
366: } else if (Node.isList(o)) {
367: iterate(Node.toList(o));
368: }
369: }
370: }
371:
372: public void visitMaterialization(final GNode n) {
373: final String name = n.getNode(0).getString(0);
374: materialized.add(name);
375: }
376:
377: public void visitRule(final GNode n) {
378: // dispatch to the "actions"
379: for (Node child : n.<Node> getList(2)) {
380: dispatch(child);
381: if ("Tuple".equals(child.getName())) {
382: if (closureMap.containsKey(child)) {
383: closureMap.get(child).add(n);
384: } else {
385: List<Node> rules = new ArrayList<Node>();
386: rules.add(n);
387: closureMap.put(child, rules);
388: }
389: }
390: }
391: }
392: }
|