1 kkz 1.1.2.1 // WriteBarrierQuadPass.java, created Tue Aug 21 19:42:49 2001 by kkz
2 kkz 1.1.2.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 kkz 1.1.2.1 import harpoon.Backend.Generic.Frame;
8 kkz 1.1.2.1 import harpoon.Backend.Runtime1.Data;
9 kkz 1.1.2.1 import harpoon.ClassFile.HClass;
10 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
11 kkz 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
12 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
13 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
14 kkz 1.1.2.1 import harpoon.ClassFile.Linker;
15 kkz 1.1.2.3 import harpoon.IR.Quads.ASET;
16 kkz 1.1.2.1 import harpoon.IR.Quads.CALL;
17 kkz 1.1.2.1 import harpoon.IR.Quads.Code;
18 kkz 1.1.2.1 import harpoon.IR.Quads.CONST;
19 kkz 1.1.2.1 import harpoon.IR.Quads.Code;
20 kkz 1.1.2.1 import harpoon.IR.Quads.Edge;
21 kkz 1.1.2.1 import harpoon.IR.Quads.FOOTER;
22 kkz 1.1.2.1 import harpoon.IR.Quads.GET;
23 kkz 1.1.2.1 import harpoon.IR.Quads.HEADER;
24 kkz 1.1.2.1 import harpoon.IR.Quads.Quad;
25 kkz 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
26 kkz 1.1.2.3 import harpoon.IR.Quads.QuadKind;
27 kkz 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
28 kkz 1.1.2.1 import harpoon.IR.Quads.SET;
29 kkz 1.1.2.1 import harpoon.IR.Quads.THROW;
30 kkz 1.1.2.1 import harpoon.IR.Quads.Code;
31 kkz 1.1.2.1 import harpoon.Temp.Temp;
32 kkz 1.1.2.1 import harpoon.Temp.TempFactory;
33 kkz 1.1.2.6 import harpoon.Util.Tuple;
34 kkz 1.1.2.1 import harpoon.Util.Util;
35 kkz 1.1.2.1
36 kkz 1.1.2.2 import java.io.PrintStream;
37 kkz 1.1.2.4 import java.util.Collections;
38 kkz 1.1.2.3 import java.util.HashSet;
39 kkz 1.1.2.3 import java.util.Iterator;
40 kkz 1.1.2.6 import java.util.Map;
41 kkz 1.1.2.3 import java.util.Set;
42 kkz 1.1.2.2
43 kkz 1.4 import java.util.HashMap;
44 cananian 1.8 import net.cscott.jutil.WorkSet;
45 kkz 1.4 import harpoon.IR.Quads.RETURN;
46 kkz 1.4 import harpoon.IR.Quads.AGET;
47 kkz 1.4 import harpoon.IR.Quads.ANEW;
48 kkz 1.4 import harpoon.IR.Quads.NEW;
49 kkz 1.4
50 kkz 1.4
51 kkz 1.1.2.1 /**
52 kkz 1.1.2.1 * <code>WriteBarrierQuadPass</code> takes code in Quad form and
53 kkz 1.1.2.1 * inserts a fake call to a write barrier that is later replaced with
54 kkz 1.1.2.1 * a real implementation in <code>WriteBarrierTreePass</code>.
55 kkz 1.1.2.1 *
56 kkz 1.1.2.1 * When used without <code>WriteBarrierTreePass</code> and in
57 kkz 1.1.2.1 * combination with the mark-and-sweep collector, reports statistics
58 kkz 1.1.2.1 * about the number of times the write-barrier is called.
59 kkz 1.1.2.1 *
60 kkz 1.1.2.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
61 cananian 1.8 * @version $Id: WriteBarrierQuadPass.java,v 1.8 2004/02/08 01:53:11 cananian Exp $
62 kkz 1.1.2.1 */
63 kkz 1.1.2.1 public class WriteBarrierQuadPass extends
64 kkz 1.1.2.1 harpoon.Analysis.Transformation.MethodMutator {
65 kkz 1.1.2.4
66 kkz 1.1.2.5 private final ClassHierarchy ch;
67 kkz 1.1.2.4 private final boolean optimize;
68 kkz 1.1.2.4 private final MRAFactory mraf;
69 kkz 1.1.2.4 private final HMethod arraySC;
70 kkz 1.1.2.4 private final HMethod fieldSC;
71 kkz 1.1.2.4 private final HClass JLT;
72 kkz 1.1.2.4 private final HClass JLRF;
73 kkz 1.1.2.1 private WriteBarrierStats wbs;
74 kkz 1.1.2.1
75 kkz 1.1.2.4 /** Creates a <code>WriteBarrierQuadPass</code>.
76 kkz 1.1.2.4 * Write barrier removal performed if optimize is true.
77 kkz 1.1.2.4 */
78 kkz 1.1.2.4 public WriteBarrierQuadPass(ClassHierarchy ch,
79 kkz 1.1.2.4 HCodeFactory parent,
80 kkz 1.1.2.4 Linker linker,
81 kkz 1.1.2.5 String resourceName,
82 kkz 1.1.2.7 int optLevel) {
83 kkz 1.1.2.1 super(parent);
84 kkz 1.1.2.5 this.ch = ch;
85 kkz 1.1.2.1 this.JLT = linker.forName("java.lang.Throwable");
86 kkz 1.1.2.1 HClass WB = linker.forName("harpoon.Runtime.PreciseGC.WriteBarrier");
87 kkz 1.1.2.1 HClass JLO = linker.forName("java.lang.Object");
88 kkz 1.1.2.1 this.JLRF = linker.forName("java.lang.reflect.Field");
89 kkz 1.1.2.1 this.arraySC = WB.getMethod("asc", new HClass[]
90 kkz 1.1.2.1 { JLO, HClass.Int, JLO, HClass.Int });
91 kkz 1.1.2.1 this.fieldSC = WB.getMethod("fsc", new HClass[]
92 kkz 1.1.2.1 { JLO, JLRF, JLO, HClass.Int });
93 kkz 1.1.2.7 this.optimize = (optLevel != 0);
94 kkz 1.1.2.7 System.out.print("MRA analysis time = ");
95 kkz 1.7 // for timing reasons, first force passes to run
96 kkz 1.7 for(Iterator it = ch.callableMethods().iterator(); it.hasNext(); )
97 kkz 1.7 parent.convert((HMethod)it.next());
98 kkz 1.1.2.6 long start_time = System.currentTimeMillis();
99 kkz 1.1.2.7 this.mraf = optimize ?
100 kkz 1.1.2.7 new MRAFactory(ch, parent, linker, resourceName, optLevel): null;
101 kkz 1.1.2.7 System.out.println(System.currentTimeMillis()-start_time);
102 kkz 1.1.2.1 }
103 kkz 1.1.2.1
104 kkz 1.1.2.1 protected HCode mutateHCode(HCodeAndMaps input) {
105 kkz 1.1.2.1 Code hc = (Code)input.hcode();
106 kkz 1.1.2.5 String cls_str = hc.getMethod().getDeclaringClass().getName();
107 kkz 1.1.2.1 // we should not have to update derivation information
108 cananian 1.3.2.1 assert hc.getDerivation() == null;
109 kkz 1.1.2.3 // create a set of SETs and ASETs that can be ignored
110 kkz 1.1.2.3 Set ignore = new HashSet();
111 kkz 1.1.2.4 if (optimize) {
112 kkz 1.1.2.4 // first, run the MRA an the code
113 kkz 1.1.2.4 MRA mra = mraf.mra(hc);
114 kkz 1.1.2.4 // MRA mra = new MRA(hc, safeSet);
115 kkz 1.1.2.4 for (Iterator it = hc.getElementsI(); it.hasNext(); ) {
116 kkz 1.1.2.4 Quad q = (Quad)it.next();
117 kkz 1.1.2.6 Tuple mra_before = mra.mra_before(q);
118 kkz 1.1.2.4 if (q.kind() == QuadKind.ASET) {
119 kkz 1.1.2.5 // ASETs only know whether the component type is
120 kkz 1.1.2.5 // an object, and not the specific type of the
121 kkz 1.1.2.5 // array, so we can only do an ignore if the
122 kkz 1.1.2.5 // exception set is empty, unless we want to do
123 kkz 1.1.2.5 // more analysis to determine the type of the array.
124 kkz 1.1.2.6 Map m = (Map) mra_before.proj(0);
125 kkz 1.1.2.6 Set s = (Set) mra_before.proj(1);
126 kkz 1.1.2.6 if (m.containsKey(((ASET)q).objectref()) && s.isEmpty()) {
127 kkz 1.1.2.4 ignore.add(q);
128 kkz 1.1.2.5 }
129 kkz 1.1.2.4 } else if (q.kind() == QuadKind.SET) {
130 kkz 1.1.2.6 Map m = (Map) mra_before.proj(0);
131 kkz 1.1.2.6 Set s = (Set) mra_before.proj(1);
132 kkz 1.1.2.6 if (m.containsKey(((SET)q).objectref())) {
133 kkz 1.1.2.5 // add first, remove later if problems
134 kkz 1.1.2.4 ignore.add(q);
135 kkz 1.1.2.5 HClass type = ((SET)q).field().getType();
136 kkz 1.1.2.6 for (Iterator cls = s.iterator(); cls.hasNext(); ) {
137 kkz 1.1.2.5 if (ch.parents((HClass)cls.next()).
138 kkz 1.1.2.5 contains(type)) {
139 kkz 1.4 ignore.remove(q);
140 kkz 1.1.2.5 break;
141 kkz 1.1.2.5 }
142 kkz 1.1.2.5 }
143 kkz 1.1.2.5 }
144 kkz 1.1.2.4 }
145 kkz 1.1.2.3 }
146 kkz 1.1.2.3 }
147 kkz 1.1.2.4 // freeze our results
148 kkz 1.1.2.4 ignore = Collections.unmodifiableSet(ignore);
149 kkz 1.1.2.1 //hc.print(new java.io.PrintWriter(System.out), null);
150 kkz 1.1.2.1 HEADER header = (HEADER) hc.getRootElement();
151 kkz 1.1.2.1 FOOTER footer = (FOOTER) header.footer();
152 kkz 1.4 // BIT EXPERIMENT
153 kkz 1.4 // QuadVisitor qv = new WriteBarrierVisitor(footer, Collections.EMPTY_SET);
154 kkz 1.1.2.3 QuadVisitor qv = new WriteBarrierVisitor(footer, ignore);
155 kkz 1.1.2.1 // we put all elements in array to avoid screwing up the
156 kkz 1.1.2.1 // iterator as we mutate the quad graph in-place.
157 kkz 1.1.2.1 Quad[] allquads = (Quad[]) hc.getElements();
158 kkz 1.1.2.1 for (int i=0; i<allquads.length; i++)
159 kkz 1.1.2.1 allquads[i].accept(qv);
160 kkz 1.1.2.1 // yay, done!
161 kkz 1.4
162 kkz 1.4 // BIT EXPERIMENT BEGIN
163 kkz 1.7 // MartinVisitor mv = new MartinVisitor(ignore);
164 kkz 1.7 // mv.doAnalysis((Quad)hc.getRootElement());
165 kkz 1.4 // BIT EXPERIMENT END
166 kkz 1.1.2.1 return hc;
167 kkz 1.1.2.1 }
168 kkz 1.1.2.1
169 kkz 1.1.2.1 /** Code factory for post pass. Emits data needed for gathering
170 kkz 1.1.2.1 * write barrier statistics. This pass needs to be run before
171 kkz 1.1.2.1 * the pass returned by <code>treeCodeFactory</code> to have
172 kkz 1.1.2.1 * any effect.
173 kkz 1.1.2.1 */
174 kkz 1.7 /*
175 kkz 1.1.2.1 public HCodeFactory statsCodeFactory(Frame f, HCodeFactory hcf,
176 kkz 1.1.2.2 ClassHierarchy ch,
177 kkz 1.1.2.2 PrintStream out) {
178 kkz 1.1.2.2 this.wbs = new WriteBarrierStats(f, hcf, ch, arraySC, fieldSC, out);
179 kkz 1.1.2.1 return wbs.codeFactory();
180 kkz 1.1.2.1 }
181 kkz 1.7 */
182 kkz 1.1.2.1 /** <code>Data</code> for gathering statistics on write barriers.
183 kkz 1.1.2.1 * Needs the results of the pass returned by
184 kkz 1.1.2.1 * <code>statsCodeFactory</code>.
185 kkz 1.1.2.1 */
186 kkz 1.7 /*
187 kkz 1.1.2.1 public Data getData(HClass hc, Frame f) {
188 kkz 1.1.2.1 // must have run statsCodeFactory first
189 cananian 1.3.2.1 assert wbs != null;
190 kkz 1.1.2.1 return new WriteBarrierData(hc, f, wbs.getCount());
191 kkz 1.1.2.1 }
192 kkz 1.7 */
193 kkz 1.4
194 kkz 1.4 // BIT EXPERIMENT
195 kkz 1.4 private class MartinVisitor {
196 kkz 1.4 private final Set ignore;
197 kkz 1.4 private HashMap map;
198 kkz 1.4
199 kkz 1.4 MartinVisitor(Set ignore) {
200 kkz 1.4 this.ignore=ignore;
201 kkz 1.4 this.map=new HashMap();
202 kkz 1.4 }
203 kkz 1.4
204 kkz 1.4 public void doAnalysis(Quad header) {
205 kkz 1.4 WorkSet quadstolookat=new WorkSet();
206 kkz 1.4 WorkSet newstatements=new WorkSet();
207 kkz 1.4 quadstolookat.add(header);
208 kkz 1.4 while(!quadstolookat.isEmpty()) {
209 cananian 1.8 Quad q=(Quad)quadstolookat.removeLast();
210 kkz 1.4 if (isremovedSet(q)) {
211 kkz 1.4 if (!map.containsKey(q)) {
212 kkz 1.4 WorkSet ws=new WorkSet();
213 kkz 1.4 ws.add(q);
214 kkz 1.4 map.put(q,ws);
215 kkz 1.4 for(int i=0;i<q.nextLength();i++)
216 kkz 1.4 quadstolookat.add(q.next(i));
217 kkz 1.4 }
218 kkz 1.4 } else if (mightCauseNewObject(q)) {
219 kkz 1.4 if (!map.containsKey(q)) {
220 kkz 1.4 WorkSet ws=new WorkSet();
221 kkz 1.4 map.put(q,ws);
222 kkz 1.4 for(int i=0;i<q.nextLength();i++)
223 kkz 1.4 quadstolookat.add(q.next(i));
224 kkz 1.4 newstatements.add(q);
225 kkz 1.4 }
226 kkz 1.4 } else {
227 kkz 1.4 if (!map.containsKey(q)) {
228 kkz 1.4 WorkSet ws=new WorkSet();
229 kkz 1.4 for(int i=0;i<q.prevLength();i++)
230 kkz 1.4 if (map.containsKey(q.prev(i))) {
231 kkz 1.4 WorkSet prevset=(WorkSet)map.get(q.prev(i));
232 kkz 1.4 ws.addAll(prevset);
233 kkz 1.4 }
234 kkz 1.4 map.put(q,ws);
235 kkz 1.4 for(int i=0;i<q.nextLength();i++)
236 kkz 1.4 quadstolookat.add(q.next(i));
237 kkz 1.4 } else {
238 kkz 1.4 WorkSet ws=new WorkSet();
239 kkz 1.4 for(int i=0;i<q.prevLength();i++)
240 kkz 1.4 if (map.containsKey(q.prev(i))) {
241 kkz 1.4 WorkSet prevset=(WorkSet)map.get(q.prev(i));
242 kkz 1.4 ws.addAll(prevset);
243 kkz 1.4 }
244 kkz 1.4 WorkSet oldset=(WorkSet) map.get(q);
245 kkz 1.4 if (ws.size()>oldset.size()) {
246 kkz 1.4 map.put(q,ws);
247 kkz 1.4 for(int i=0;i<q.nextLength();i++)
248 kkz 1.4 quadstolookat.add(q.next(i));
249 kkz 1.4 }
250 kkz 1.4 }
251 kkz 1.4 }
252 kkz 1.4 }
253 kkz 1.4 //cycle through each newstatements
254 kkz 1.4 WorkSet assigns=new WorkSet();
255 kkz 1.4 while(!newstatements.isEmpty()) {
256 kkz 1.4 Quad q=(Quad)newstatements.pop();
257 kkz 1.4 for(int i=0;i<q.prevLength();i++)
258 kkz 1.4 if (map.containsKey(q.prev(i))) {
259 kkz 1.4 WorkSet prevset=(WorkSet)map.get(q.prev(i));
260 kkz 1.4 assigns.addAll(prevset);
261 kkz 1.4 } else System.out.println("ERROR: "+q+" "+i+" "+q.prev(i)+ " in hacked analysis");
262 kkz 1.4 }
263 kkz 1.4 while(!assigns.isEmpty()) {
264 kkz 1.4 Quad q=(Quad)assigns.pop();
265 kkz 1.4 System.out.println("Adding overhead to: "+q);
266 kkz 1.4 if (q instanceof SET) {
267 kkz 1.4 SET s=(SET)q;
268 kkz 1.4 Temp t=new Temp(q.getFactory().tempFactory());
269 kkz 1.4 GET g=new GET(q.getFactory(), q, t, s.field(), s.objectref());
270 kkz 1.4 SET ns=new SET(q.getFactory(), q, s.field(), s.objectref(),t);
271 kkz 1.4 Quad.addEdge(ns,0,s.next(0),s.nextEdge(0).which_pred());
272 kkz 1.4 Quad.addEdge(g,0,ns,0);
273 kkz 1.4 Quad.addEdge(s,0,g,0);
274 kkz 1.4 } else if (q instanceof ASET) {
275 kkz 1.4 ASET s=(ASET)q;
276 kkz 1.4 Temp t=new Temp(q.getFactory().tempFactory());
277 kkz 1.4 AGET ag=new AGET(q.getFactory(), q, t, s.objectref(),s.index(),s.type());
278 kkz 1.4 ASET ans=new ASET(q.getFactory(), q, s.objectref(), s.index(), t, s.type());
279 kkz 1.4
280 kkz 1.4 Quad.addEdge(ans,0,s.next(0),s.nextEdge(0).which_pred());
281 kkz 1.4 Quad.addEdge(ag,0,ans,0);
282 kkz 1.4 Quad.addEdge(s,0,ag,0);
283 kkz 1.4 } else {
284 kkz 1.4 System.out.println("ERROR: "+q+" in hacked analysis");
285 kkz 1.4 }
286 kkz 1.4 }
287 kkz 1.4 }
288 kkz 1.4
289 kkz 1.4 public boolean isremovedSet(Quad q) {
290 kkz 1.4 if (q instanceof ASET) {
291 kkz 1.4 ASET as = (ASET)q;
292 kkz 1.4 return (!as.type().isPrimitive() && ignore.contains(as));
293 kkz 1.4 } else if (q instanceof SET) {
294 kkz 1.4 SET s = (SET)q;
295 kkz 1.4 return (!s.isStatic() && !s.field().getType().isPrimitive() &&
296 kkz 1.4 ignore.contains(s));
297 kkz 1.4 } else return false;
298 kkz 1.4 }
299 kkz 1.4 public boolean mightCauseNewObject(Quad q) {
300 kkz 1.4 return ((q instanceof NEW)||
301 kkz 1.4 (q instanceof THROW)||
302 kkz 1.4 (q instanceof ANEW)||
303 kkz 1.4 (q instanceof RETURN));
304 kkz 1.4 }
305 kkz 1.4
306 kkz 1.4 }
307 kkz 1.4
308 kkz 1.1.2.1
309 kkz 1.1.2.3 private class WriteBarrierVisitor extends QuadVisitor {
310 kkz 1.1.2.3 private FOOTER footer;
311 kkz 1.1.2.3 private final Set ignore;
312 kkz 1.1.2.3
313 kkz 1.1.2.3 /** Creates a <code>WriteBarrierVisitor</code>. */
314 kkz 1.1.2.3 WriteBarrierVisitor(FOOTER footer, Set ignore) {
315 kkz 1.1.2.1 this.footer = footer;
316 kkz 1.1.2.3 this.ignore = ignore;
317 kkz 1.1.2.1 }
318 kkz 1.1.2.3
319 kkz 1.1.2.1 public void visit(Quad q) { /* do nothing */ }
320 kkz 1.1.2.1 public void visit(ASET q) {
321 kkz 1.1.2.3 // we are interested only in arrays containing pointers
322 kkz 1.1.2.3 // we can ignore ASETs where the array is the mra object
323 kkz 1.1.2.3 if (!q.type().isPrimitive() && !ignore.contains(q)) {
324 kkz 1.1.2.1 QuadFactory qf = (QuadFactory)q.getFactory();
325 kkz 1.1.2.1 TempFactory tf = qf.tempFactory();
326 kkz 1.1.2.1 // create Temps
327 kkz 1.1.2.1 Temp retex = new Temp(tf, "wbex");
328 kkz 1.1.2.1 Temp id = new Temp(tf, "wbid");
329 kkz 1.1.2.1 // create needed Quads
330 kkz 1.1.2.1 CONST idc = new CONST(qf, q, id, new Integer(0), HClass.Int);
331 kkz 1.1.2.1 CALL call = new CALL(qf, q, arraySC,
332 kkz 1.1.2.1 new Temp[] { q.objectref(), q.index(),
333 kkz 1.1.2.1 q.src(), id },
334 kkz 1.1.2.1 null, retex, false, false, new Temp[0]);
335 kkz 1.1.2.1 THROW thr = new THROW(qf, q, retex);
336 kkz 1.1.2.1 // add CONST and CALL before ASET
337 kkz 1.1.2.1 splice(idc, q.prevEdge(0));
338 kkz 1.1.2.1 splice(call, q.prevEdge(0));
339 kkz 1.1.2.1 // add THROW after CALL
340 kkz 1.1.2.1 Quad.addEdge(call, 1, thr, 0);
341 kkz 1.1.2.1 footer = footer.attach(thr, 0);
342 kkz 1.1.2.1 }
343 kkz 1.1.2.1 }
344 kkz 1.1.2.1 public void visit(SET q) {
345 kkz 1.1.2.1 // we are interested only in non-static fields containing pointers
346 kkz 1.1.2.3 // we can ignore SETs where the object is the mra object
347 kkz 1.1.2.3 if (!q.isStatic() && !q.field().getType().isPrimitive() &&
348 kkz 1.1.2.3 !ignore.contains(q)) {
349 kkz 1.1.2.1 QuadFactory qf = (QuadFactory)q.getFactory();
350 kkz 1.1.2.1 TempFactory tf = qf.tempFactory();
351 kkz 1.1.2.1 // create needed Temps
352 kkz 1.1.2.1 Temp field = new Temp(tf, "wbfield");
353 kkz 1.1.2.1 Temp retex = new Temp(tf, "wbex");
354 kkz 1.1.2.1 Temp id = new Temp(tf, "wbid");
355 kkz 1.1.2.1 // create needed Quads
356 kkz 1.1.2.1 CONST idc = new CONST(qf, q, id, new Integer(0), HClass.Int);
357 kkz 1.1.2.1 CONST fieldc = new CONST(qf, q, field, q.field(), JLRF);
358 kkz 1.1.2.1 CALL call = new CALL(qf, q, fieldSC,
359 kkz 1.1.2.1 new Temp[] { q.objectref(), field,
360 kkz 1.1.2.1 q.src(), id },
361 kkz 1.1.2.1 null, retex, false, false, new Temp[0]);
362 kkz 1.1.2.1 THROW thr = new THROW(qf, q, retex);
363 kkz 1.1.2.1 // add CONSTs and CALL before SET
364 kkz 1.1.2.1 splice(idc, q.prevEdge(0));
365 kkz 1.1.2.1 splice(fieldc, q.prevEdge(0));
366 kkz 1.1.2.1 splice(call, q.prevEdge(0));
367 kkz 1.1.2.1 // add THROW after CALL
368 kkz 1.1.2.1 Quad.addEdge(call, 1, thr, 0);
369 kkz 1.1.2.1 footer = footer.attach(thr, 0);
370 kkz 1.1.2.1 }
371 kkz 1.1.2.1 }
372 kkz 1.1.2.1 /** inserts the given Quad on the given Edge */
373 kkz 1.1.2.1 private void splice(Quad q, Edge e) {
374 kkz 1.1.2.1 Quad.addEdge((Quad)e.from(), e.which_succ(), q, 0);
375 kkz 1.1.2.1 Quad.addEdge(q, 0, (Quad)e.to(), e.which_pred());
376 kkz 1.1.2.1 }
377 kkz 1.1.2.1 }
378 cananian 1.2 }