1
2
3
4 package net.sf.bddbddb;
5
6 import java.util.Collection;
7 import java.util.Iterator;
8 import java.util.LinkedList;
9 import java.util.List;
10 import java.util.Map;
11 import jwutil.collections.GenericMultiMap;
12 import jwutil.collections.HashWorklist;
13 import jwutil.collections.MultiMap;
14 import jwutil.collections.Pair;
15 import jwutil.graphs.SCComponent;
16 import net.sf.bddbddb.Stratify.PDGRuleNode;
17
18 /***
19 * IterationFlowGraph
20 *
21 * @author mcarbin
22 * @version $Id: IterationFlowGraph.java 558 2005-05-23 21:10:31Z joewhaley $
23 */
24 public class IterationFlowGraph {
25 IterationList iterationElements;
26 Map innerSccs;
27 List strata, rules, loops;
28 MultiMap containedBy;
29 MultiMap dependencies;
30
31 public IterationFlowGraph(List rules, Stratify strat) {
32 this(rules, strat.strata, strat.innerSccs);
33 }
34
35 public IterationFlowGraph(List rules, List strata, Map innerSccs) {
36 this.strata = strata;
37 this.innerSccs = innerSccs;
38 this.rules = rules;
39 dependencies = new GenericMultiMap();
40 loops = new LinkedList();
41 iterationElements = new IterationList(false);
42 containedBy = new GenericMultiMap();
43 constructStrataLoops();
44 constructDependencies();
45 }
46
47 private void constructStrataLoops() {
48 int k = 0;
49 for (Iterator it = strata.iterator(); it.hasNext(); ) {
50 List stratum = (List) it.next();
51 IterationList loop = buildIterationList(stratum, false);
52 iterationElements.addElement(loop);
53 }
54 }
55
56 private void constructDependencies() {
57 constructRuleDependencies();
58 constructListDependencies(iterationElements);
59 }
60
61 private void constructRuleDependencies() {
62 InferenceRule.DependenceNavigator depNav = new InferenceRule.DependenceNavigator(rules);
63 HashWorklist w = new HashWorklist(true);
64 for (Iterator it = rules.iterator(); it.hasNext();) {
65 Object rule = it.next();
66 w.add(new Pair(rule, rule));
67 }
68
69 while (!w.isEmpty()) {
70 Pair pair = (Pair) w.pull();
71 Object link = pair.get(0);
72 Object initRule = pair.get(1);
73 Collection usedRelations = depNav.prev(link);
74 for (Iterator it2 = usedRelations.iterator(); it2.hasNext();) {
75 Collection definingRules = depNav.prev(it2.next());
76 for (Iterator it3 = definingRules.iterator(); it3.hasNext();) {
77 Object o = it3.next();
78 dependencies.add(initRule, o);
79 w.add(new Pair(o, initRule));
80 }
81 }
82 }
83 }
84
85 private void constructListDependencies(IterationList list) {
86 for (Iterator it = list.iterator(); it.hasNext();) {
87 IterationElement elem = (IterationElement) it.next();
88 if (elem instanceof InferenceRule) {
89 Collection ruleDepends = dependencies.getValues(elem);
90 for (Iterator it2 = ruleDepends.iterator(); it2.hasNext();) {
91 IterationElement elem2 = (IterationElement) it2.next();
92
93 }
94 } else if (elem instanceof IterationList) {
95 constructListDependencies((IterationList) elem);
96 Collection listDepends = dependencies.getValues(elem);
97 for (Iterator it2 = listDepends.iterator(); it2.hasNext();) {
98 IterationElement elem2 = (IterationElement) it2.next();
99
100 }
101 }
102 }
103 }
104
105 IterationList buildIterationList(List sccList, boolean isLoop) {
106 IterationList list = new IterationList(isLoop);
107 for (Iterator a = sccList.iterator(); a.hasNext(); ) {
108 SCComponent scc = (SCComponent) a.next();
109 List c = (List) innerSccs.get(scc);
110 if (c == null || c.isEmpty()) {
111 IterationList list2;
112 if (!isLoop && scc.isLoop()) {
113 list2 = new IterationList(true);
114 list.addElement(list2);
115 } else {
116 list2 = list;
117 }
118 for (Iterator it = scc.nodeSet().iterator(); it.hasNext(); ) {
119 Object o = it.next();
120 if (o instanceof PDGRuleNode) {
121 InferenceRule r = ((PDGRuleNode)o).rule;
122 if (r != null) {
123 list2.addElement(r);
124 containedBy.add(r, list2);
125 if (list != list2)
126 containedBy.add(r, list);
127 }
128 }
129 }
130 } else {
131 IterationList childLoop = buildIterationList(c, scc.isLoop());
132 list.addElement(childLoop);
133 Collection childElems = childLoop.getAllNestedElements();
134 for (Iterator it2 = childElems.iterator(); it2.hasNext();) {
135 containedBy.add(it2.next(), list);
136 }
137 }
138 }
139 return list;
140 }
141
142 public String toString() {
143 return iterationElements.toString();
144 }
145
146 public boolean dependsOn(IterationElement e1, IterationElement e2) {
147 return dependencies.getValues(e1).contains(e2);
148 }
149
150 public IterationList getIterationList() {
151 return iterationElements;
152 }
153
154 public IterationList expand() {
155 if (iterationElements.isLoop()) {
156 IterationList unrolled = iterationElements.unroll();
157 iterationElements.expandInLoop();
158 unrolled.elements.add(iterationElements);
159 iterationElements = unrolled;
160 } else {
161 iterationElements.expand(true);
162 }
163 return iterationElements;
164 }
165
166 /***
167 * @return Returns the loops.
168 */
169 public List getLoops() {
170 return loops;
171 }
172
173 public IterationElement getIterationElement(String s) {
174 return iterationElements.getElement(s);
175 }
176 }