11 public UpdateNode(Rule r) {
13 bindings=new Vector();
14 binding=new Hashtable();
18 public Rule getRule() {
22 public String toString() {
24 for(int i=0;i<bindings.size();i++)
25 st+=bindings.get(i).toString()+"\n";
26 st+="---------------------\n";
27 for(int i=0;i<updates.size();i++)
28 st+=updates.get(i).toString()+"\n";
32 public void addBindings(Vector v) {
33 for (int i=0;i<v.size();i++) {
34 addBinding((Binding)v.get(i));
38 public boolean checkupdates() {
39 if (!checkconflicts()) /* Do we have conflicting concrete updates */
41 if (computeordering()) /* Ordering exists */
46 private boolean computeordering() {
47 /* Build dependency graph between updates */
48 HashSet graph=new HashSet();
49 Hashtable mapping=new Hashtable();
50 for(int i=0;i<updates.size();i++) {
51 Updates u=(Updates)updates.get(i);
52 GraphNode gn=new GraphNode(String.valueOf(i),u);
56 for(int i=0;i<updates.size();i++) {
57 Updates u1=(Updates)updates.get(i);
60 for(int j=0;j<updates.size();j++) {
61 Updates u2=(Updates)updates.get(j);
64 Descriptor d=u1.getDescriptor();
65 if (u2.getRightExpr().usesDescriptor(d)) {
66 /* Add edge for dependency */
67 GraphNode gn1=(GraphNode) mapping.get(u1);
68 GraphNode gn2=(GraphNode) mapping.get(u2);
69 GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
75 if (!GraphNode.DFS.depthFirstSearch(graph)) /* DFS & check for acyclicity */
78 TreeSet topologicalsort = new TreeSet(new Comparator() {
79 public boolean equals(Object obj) { return false; }
80 public int compare(Object o1, Object o2) {
81 GraphNode g1 = (GraphNode) o1;
82 GraphNode g2 = (GraphNode) o2;
83 return g2.getFinishingTime() - g1.getFinishingTime();
86 topologicalsort.addAll(graph);
87 Vector sortedvector=new Vector();
88 for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
89 GraphNode gn=(GraphNode)sort.next();
90 sortedvector.add(gn.getOwner());
92 updates=sortedvector; //replace updates with the sorted array
96 private boolean checkconflicts() {
97 Set toremove=new HashSet();
98 for(int i=0;i<updates.size();i++) {
99 Updates u1=(Updates)updates.get(i);
100 for(int j=0;j<updates.size();j++) {
101 Updates u2=(Updates)updates.get(j);
104 if (u1.isAbstract()||u2.isAbstract())
105 continue; /* Abstract updates are already accounted for by graph */
106 if (u1.getDescriptor()!=u2.getDescriptor())
107 continue; /* No interference - different descriptors */
109 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
110 (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
111 continue; /* Can be satisfied simultaneously */
113 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
114 (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
116 if ((u1.getOpcode()==u2.getOpcode())&&
117 u1.isExpr()&&u2.isExpr()&&
118 u1.getRightExpr().equals(null, u2.getRightExpr())) {
119 /*We'll remove the second occurence*/
127 /* Handle = or != NULL */
128 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
129 ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
130 (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
131 ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
132 if (u1.getOpcode()==Opcode.NE)
139 /* Handle = and != to different constants */
140 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
141 ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
142 (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
143 (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
144 !u1.getRightExpr().equals(u2.getRightExpr())) {
145 if (u1.getOpcode()==Opcode.NE)
152 /* Compatible operations < & <= */
153 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
154 ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
157 /* Compatible operations > & >= */
158 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
159 ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
164 /* Equality & Comparisons */
167 return false; /* They interfere */
170 updates.removeAll(toremove);
174 public void addBinding(Binding b) {
176 binding.put(b.getVar(),b);
179 public Binding getBinding(VarDescriptor vd) {
180 if (binding.containsKey(vd))
181 return (Binding)binding.get(vd);
186 public void addUpdate(Updates u) {
190 public int numUpdates() {
191 return updates.size();
193 public Updates getUpdate(int i) {
194 return (Updates)updates.get(i);
196 public void generate(CodeWriter cr, boolean removal, String slot0, String slot1) {
198 generate_bindings(cr, slot0,slot1);
199 for(int i=0;i<updates.size();i++) {
200 Updates u=(Updates)updates.get(i);
201 VarDescriptor right=VarDescriptor.makeNew("right");
202 if (u.getType()==Updates.ABSTRACT)
203 throw new Error("Abstract update not implemented");
205 switch(u.getType()) {
207 u.getRightExpr().generate(cr,right);
209 case Updates.POSITION:
210 if (u.getRightPos()==0)
211 cr.outputline("int "+right.getSafeSymbol()+"="+slot0+";");
212 else if (u.getRightPos()==1)
213 cr.outputline("int "+right.getSafeSymbol()+"="+slot1+";");
214 else throw new Error("Error w/ Position");
219 VarDescriptor left=VarDescriptor.makeNew("left");
220 u.getLeftExpr().generate(cr,left);
221 Opcode op=u.getOpcode();
222 cr.outputline("if (!("+left.getSafeSymbol()+op+right.getSafeSymbol()+"))");
226 cr.outputline(right.getSafeSymbol()+"++;");
227 else if (op==Opcode.GE)
229 else if (op==Opcode.EQ)
231 else if (op==Opcode.NE)
232 cr.outputline(right.getSafeSymbol()+"++;");
233 else if (op==Opcode.LT)
234 cr.outputline(right.getSafeSymbol()+"--;");
235 else if (op==Opcode.LE)
237 else throw new Error();
239 VarDescriptor vd=((VarExpr)u.getLeftExpr()).getVar();
240 cr.outputline(vd.getSafeSymbol()+"="+right.getSafeSymbol()+";");
241 } else if (u.isField()) {
243 Expr subexpr=((DotExpr)u.getLeftExpr()).getExpr();
244 Expr intindex=((DotExpr)u.getLeftExpr()).getIndex();
245 VarDescriptor subvd=VarDescriptor.makeNew("subexpr");
246 VarDescriptor indexvd=VarDescriptor.makeNew("index");
247 subexpr.generate(cr,subvd);
249 intindex.generate(cr,indexvd);
250 FieldDescriptor fd=(FieldDescriptor)u.getDescriptor();
251 StructureTypeDescriptor std=(StructureTypeDescriptor)subexpr.getType();
252 if (fd instanceof ArrayDescriptor) {
253 fd = ((ArrayDescriptor) fd).getField();
256 Expr offsetbits = std.getOffsetExpr(fd);
257 if (intindex != null) {
258 Expr basesize = fd.getBaseSizeExpr();
259 offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
261 Expr offsetbytes = new OpExpr(Opcode.SHR, offsetbits,new IntegerLiteralExpr(3));
262 Expr byteaddress=new OpExpr(Opcode.ADD, offsetbytes, subexpr);
263 VarDescriptor addr=VarDescriptor.makeNew("byteaddress");
264 byteaddress.generate(cr,addr);
266 if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
267 ReservedTypeDescriptor rtd=(ReservedTypeDescriptor)fd.getType();
268 if (rtd==ReservedTypeDescriptor.INT) {
269 cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
270 } else if (rtd==ReservedTypeDescriptor.SHORT) {
271 cr.outputline("*((short *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
272 } else if (rtd==ReservedTypeDescriptor.BYTE) {
273 cr.outputline("*((char *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
274 } else if (rtd==ReservedTypeDescriptor.BIT) {
275 Expr tmp = new OpExpr(Opcode.SHL, offsetbytes, new IntegerLiteralExpr(3));
276 Expr offset=new OpExpr(Opcode.SUB, offsetbits, tmp);
277 Expr mask=new OpExpr(Opcode.SHR, new IntegerLiteralExpr(1), offset);
278 VarDescriptor maskvar=VarDescriptor.makeNew("mask");
279 mask.generate(cr,maskvar);
280 cr.outputline("*((char *) "+addr.getSafeSymbol()+")|="+maskvar.getSafeSymbol()+";");
281 cr.outputline("if (!"+right.getSafeSymbol()+")");
282 cr.outputline("*((char *) "+addr.getSafeSymbol()+")^="+maskvar.getSafeSymbol()+";");
283 } else throw new Error();
286 cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
293 private int bitmask(int bits) {
296 for (int i = 0; i < bits; i++) {
304 private void generate_bindings(CodeWriter cr, String slot0, String slot1) {
305 for(int i=0;i<bindings.size();i++) {
306 Binding b=(Binding)bindings.get(i);
308 throw new Error("Search not implemented for bindings");
309 VarDescriptor vd=b.getVar();
310 switch(b.getPosition()) {
312 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot0+";");
315 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot1+";");
318 throw new Error("Slot >1 doesn't exist.");