1 cananian 1.1.2.1 // DefaultAllocationStrategy.java, created Fri Feb 12 3:01:41 1999 by duncan
2 cananian 1.1.2.1 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Interpret.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
7 cananian 1.1.2.1 import harpoon.IR.Tree.BINOP;
8 cananian 1.1.2.1 import harpoon.IR.Tree.Bop;
9 cananian 1.1.2.1 import harpoon.IR.Tree.CJUMP;
10 cananian 1.1.2.1 import harpoon.IR.Tree.CONST;
11 cananian 1.1.2.1 import harpoon.IR.Tree.ESEQ;
12 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
13 cananian 1.1.2.1 import harpoon.IR.Tree.JUMP;
14 cananian 1.1.2.1 import harpoon.IR.Tree.LABEL;
15 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
16 cananian 1.1.2.1 import harpoon.IR.Tree.NAME;
17 cananian 1.1.2.1 import harpoon.IR.Tree.NATIVECALL;
18 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
19 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
20 cananian 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
21 cananian 1.1.2.1 import harpoon.IR.Tree.Type;
22 cananian 1.1.2.1 import harpoon.Temp.Label;
23 cananian 1.1.2.1 import harpoon.Temp.Temp;
24 cananian 1.1.2.1
25 cananian 1.1.2.1 import java.util.Arrays;
26 cananian 1.1.2.1 import java.util.List;
27 cananian 1.1.2.1
28 cananian 1.1.2.1 /**
29 cananian 1.1.2.1 * A simple-minded version of Appel's fast-allocation strategy
30 cananian 1.1.2.1 *
31 cananian 1.1.2.1 * @author Duncan Bryce <duncan@lcs.mit.edu>
32 cananian 1.2 * @version $Id: DefaultAllocationStrategy.java,v 1.2 2002/02/25 21:05:50 cananian Exp $
33 cananian 1.1.2.1 */
34 cananian 1.1.2.2 class DefaultAllocationStrategy implements AllocationStrategy {
35 cananian 1.1.2.1
36 cananian 1.1.2.1 private AllocationInfo info;
37 cananian 1.1.2.1
38 cananian 1.1.2.1 public DefaultAllocationStrategy(AllocationInfo info) {
39 cananian 1.1.2.1 this.info = info;
40 cananian 1.1.2.1 }
41 cananian 1.1.2.1
42 cananian 1.1.2.1 /**
43 cananian 1.1.2.1 * Returns a <code>Stm</code> object which allocates a block of memory
44 cananian 1.1.2.1 * of the specified size.
45 cananian 1.1.2.1 */
46 cananian 1.1.2.1 public Exp memAlloc(Exp size)
47 cananian 1.1.2.1 {
48 cananian 1.1.2.1 LABEL l0, l1, l2, l3, l4;
49 cananian 1.1.2.1 NAME gc, exit_oom;
50 cananian 1.1.2.1 TEMP triedGC; // INT type
51 cananian 1.1.2.1 TEMP memLimit, newMemPtr, nextPtr, resultPtr, tmp;
52 cananian 1.1.2.1 HCodeElement src = size;
53 cananian 1.1.2.1 TreeFactory tf = size.getFactory();
54 cananian 1.1.2.1 Stm[] stms;
55 cananian 1.1.2.1
56 cananian 1.1.2.1 triedGC = new TEMP(tf,src,Type.INT, new Temp(tf.tempFactory()));
57 cananian 1.1.2.1 nextPtr = new TEMP(tf,src,Type.POINTER, info.getNextPtr());
58 cananian 1.1.2.1 memLimit = new TEMP(tf,src,Type.POINTER, info.getMemLimit());
59 cananian 1.1.2.1 newMemPtr = new TEMP(tf,src,Type.POINTER, new Temp(tf.tempFactory()));
60 cananian 1.1.2.1 resultPtr = new TEMP(tf,src,Type.POINTER, new Temp(tf.tempFactory()));
61 cananian 1.1.2.1 tmp = new TEMP(tf,src,Type.POINTER, new Temp(tf.tempFactory()));
62 cananian 1.1.2.1
63 cananian 1.1.2.1 l0 = new LABEL(tf, src, new Label(), false);
64 cananian 1.1.2.1 l1 = new LABEL(tf, src, new Label(), false);
65 cananian 1.1.2.1 l2 = new LABEL(tf, src, new Label(), false);
66 cananian 1.1.2.1 l3 = new LABEL(tf, src, new Label(), false);
67 cananian 1.1.2.1 l4 = new LABEL(tf, src, new Label(), false);
68 cananian 1.1.2.1 gc = new NAME(tf, src, info.GC());
69 cananian 1.1.2.1 exit_oom = new NAME(tf, src, info.exitOutOfMemory());
70 cananian 1.1.2.1
71 cananian 1.1.2.1 stms = new Stm[] {
72 cananian 1.1.2.1 // triedGC <-- 0;
73 cananian 1.1.2.1 new MOVE(tf, src, triedGC, new CONST(tf, src, (int)0)),
74 cananian 1.1.2.1
75 cananian 1.1.2.1 // newMemPtr <-- info.next_ptr() + size
76 cananian 1.1.2.1 new MOVE
77 cananian 1.1.2.1 (tf, src, newMemPtr,
78 cananian 1.1.2.1 new BINOP
79 cananian 1.1.2.1 (tf, src, Type.POINTER, Bop.ADD,
80 cananian 1.1.2.1 nextPtr,
81 cananian 1.1.2.1 size)),
82 cananian 1.1.2.1
83 cananian 1.1.2.1 // LABEL 0
84 cananian 1.1.2.1 l0,
85 cananian 1.1.2.1
86 cananian 1.1.2.1 // Is (limit > next + N) ?
87 cananian 1.1.2.1 new CJUMP
88 cananian 1.1.2.1 (tf, src,
89 cananian 1.1.2.1 new BINOP
90 cananian 1.1.2.1 (tf, src, Type.POINTER, Bop.CMPGT,
91 cananian 1.1.2.1 memLimit,
92 cananian 1.1.2.1 newMemPtr),
93 cananian 1.1.2.1 l1.label, // There's enough space
94 cananian 1.1.2.1 l2.label), // Not enough space!
95 cananian 1.1.2.1
96 cananian 1.1.2.1
97 cananian 1.1.2.1 // LABEL 2
98 cananian 1.1.2.1 l2,
99 cananian 1.1.2.1
100 cananian 1.1.2.1 // (limit > next + N) == FALSE.
101 cananian 1.1.2.1 // If (triedGC!=0), then perform garbage collection and try again.
102 cananian 1.1.2.1 // Otherwise, we're out of memory.
103 cananian 1.1.2.1 new CJUMP
104 cananian 1.1.2.1 (tf, src, triedGC,
105 cananian 1.1.2.1 l3.label, // If tried GC already, out of mem
106 cananian 1.1.2.1 l4.label), // If mem alloc fails, call GC
107 cananian 1.1.2.1
108 cananian 1.1.2.1 // LABEL 3
109 cananian 1.1.2.1 l3,
110 cananian 1.1.2.1
111 cananian 1.1.2.1 // Throw OutOfMemoryError
112 cananian 1.1.2.1 new NATIVECALL(tf, src, tmp, exit_oom, null),
113 cananian 1.1.2.1
114 cananian 1.1.2.1 // LABEL 4
115 cananian 1.1.2.1 l4,
116 cananian 1.1.2.1
117 cananian 1.1.2.1 // triedGC <-- 1
118 cananian 1.1.2.1 new MOVE(tf, src, triedGC, new CONST(tf, src, 1)),
119 cananian 1.1.2.1
120 cananian 1.1.2.1 // call the garbage collector
121 cananian 1.1.2.1 new NATIVECALL(tf, src, tmp, gc, null),
122 cananian 1.1.2.1
123 cananian 1.1.2.1 // try to allocate memory again
124 cananian 1.1.2.1 new JUMP(tf, src, l0.label),
125 cananian 1.1.2.1
126 cananian 1.1.2.1 // LABEL 1
127 cananian 1.1.2.1 l1,
128 cananian 1.1.2.1
129 cananian 1.1.2.1 // There is enough memory to allocate.
130 cananian 1.1.2.1 // Increment the "next" ptr, and MOVE the result to a useful
131 cananian 1.1.2.1 // place
132 cananian 1.1.2.1 //
133 cananian 1.1.2.1 new MOVE(tf, src, resultPtr, nextPtr),
134 cananian 1.1.2.1 new MOVE(tf, src, nextPtr, newMemPtr)
135 cananian 1.1.2.1 };
136 cananian 1.1.2.1
137 cananian 1.1.2.1 // Combine the Stm objects into one ESEQ object, and return it.
138 cananian 1.1.2.1 //
139 cananian 1.1.2.1 return new ESEQ(tf, src, Stm.toStm(Arrays.asList(stms)), resultPtr);
140 cananian 1.1.2.1 }
141 cananian 1.1.2.1
142 cananian 1.2 }