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