int: load with immediate only if supported by the architecture
[neatcc.git] / reg.c
blob309fd51f0c1fc7731b7d9f5a4bf62726683f3d6b
1 /* neatcc global register allocation */
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include "ncc.h"
6 #define IC_LLD(ic, i) (O_C((ic)[i].op) == (O_LD | O_LOC) ? (ic)[i].a1 : -1)
7 #define IC_LST(ic, i) (O_C((ic)[i].op) == (O_ST | O_LOC) ? (ic)[i].a2 : -1)
9 static int ic_loc(struct ic *ic, long iv, long *loc, long *off)
11 long oc = O_C(ic[iv].op);
12 if (oc == (O_LD | O_LOC) || oc == (O_MOV | O_LOC)) {
13 *loc = ic[iv].a1;
14 *off = ic[iv].a2;
15 return 0;
17 if (oc == (O_ST | O_LOC)) {
18 *loc = ic[iv].a2;
19 *off = ic[iv].a3;
20 return 0;
22 return 1;
25 /* local live region */
26 struct rgn {
27 long loc; /* local number */
28 long beg; /* region start (instruction number) */
29 long end; /* region end */
30 long cnt; /* number of accesses */
31 int reg; /* register allocated to this region */
34 static struct rgn *rgn; /* live regions */
35 static int rgn_n; /* number of entries in rgn[] */
36 static int rgn_sz; /* size of rgn[] */
38 static int *loc_ptr; /* if the address of locals is accessed */
39 static int loc_n; /* number of locals */
41 static long *dst_head; /* lists of jumps to each instruction */
42 static long *dst_next; /* next entries in dst_head[] lists */
44 static void rgn_add(long loc, long beg, long end, long cnt)
46 int i;
47 for (i = 0; i < rgn_n; i++) {
48 if (rgn[i].loc == loc && rgn[i].beg < end && rgn[i].end > beg) {
49 if (beg > rgn[i].beg)
50 beg = rgn[i].beg;
51 if (end < rgn[i].end)
52 end = rgn[i].end;
53 cnt += rgn[i].cnt;
54 rgn[i].loc = -1;
57 for (i = 0; i < rgn_n; i++)
58 if (rgn[i].loc < 0)
59 break;
60 if (i == rgn_n) {
61 if (rgn_n >= rgn_sz) {
62 rgn_sz = MAX(16, rgn_sz * 2);
63 rgn = mextend(rgn, rgn_n, rgn_sz, sizeof(rgn[0]));
65 rgn_n++;
67 rgn[i].loc = loc;
68 rgn[i].beg = beg;
69 rgn[i].end = end;
70 rgn[i].cnt = cnt;
71 rgn[i].reg = -1;
74 /* return nonzero if register reg is free from beg till end */
75 static int rgn_available(long beg, long end, int reg)
77 int i;
78 for (i = 0; i < rgn_n; i++)
79 if (rgn[i].reg == reg)
80 if (rgn[i].beg < end && rgn[i].end > beg)
81 return 0;
82 return 1;
85 static long reg_region(struct ic *ic, long ic_n, long loc, long pos,
86 long *beg, long *end, char *mark)
88 long cnt = 0;
89 long dst;
90 for (; pos >= 0; pos--) {
91 if (pos < *beg)
92 *beg = pos;
93 if (pos + 1 > *end)
94 *end = pos + 1;
95 if (mark[pos])
96 break;
97 mark[pos] = 1;
98 if (IC_LST(ic, pos) == loc)
99 break;
100 if (IC_LLD(ic, pos) == loc)
101 cnt++;
102 dst = dst_head[pos];
103 while (dst >= 0) {
104 cnt += reg_region(ic, ic_n, loc, dst, beg, end, mark);
105 dst = dst_next[dst];
107 if (pos > 0 && ic[pos - 1].op & O_JMP)
108 break;
110 return cnt;
113 /* compute local's live regions */
114 static void reg_regions(struct ic *ic, long ic_n, long loc)
116 char *mark;
117 long beg, end;
118 long cnt;
119 long i;
120 mark = calloc(ic_n, sizeof(mark[0]));
121 for (i = 0; i < ic_n; i++) {
122 if (IC_LLD(ic, i) == loc && !mark[i]) {
123 beg = i;
124 end = i + 1;
125 cnt = reg_region(ic, ic_n, loc, i, &beg, &end, mark);
126 rgn_add(loc, beg, end, cnt);
129 for (i = 0; i < ic_n; i++)
130 if (IC_LST(ic, i) == loc && !mark[i])
131 rgn_add(loc, i, i + 1, 1);
132 free(mark);
135 /* number of times a local is accessed */
136 static long reg_loccnt(struct ic *ic, long ic_n, long loc)
138 long cnt = 0;
139 long i;
140 for (i = 0; i < ic_n; i++)
141 if (IC_LLD(ic, i) == loc || IC_LST(ic, i) == loc)
142 cnt++;
143 return cnt;
146 /* perform global register allocation */
147 static void reg_glob(int leaf)
149 int *srt;
150 int regs[N_REGS];
151 int i, j;
152 int regs_max = MIN(N_TMPS >> 1, 4);
153 long regs_mask = leaf ? R_TMPS : R_PERM;
154 int regs_n = 0;
155 for (i = leaf ? 1 : 3; i < N_TMPS && regs_n < regs_max; i++)
156 if ((1 << i) & regs_mask)
157 regs[regs_n++] = i;
158 srt = malloc(rgn_n * sizeof(srt[0]));
159 /* sorting locals */
160 for (i = 0; i < rgn_n; i++) {
161 for (j = i - 1; j >= 0 && rgn[i].cnt > rgn[srt[j]].cnt; j--)
162 srt[j + 1] = srt[j];
163 srt[j + 1] = i;
165 /* allocating registers */
166 for (i = 0; i < rgn_n; i++) {
167 int r = srt[i];
168 long loc = rgn[r].loc;
169 long beg = rgn[r].beg;
170 long end = rgn[r].end;
171 if (loc < 0 || loc_ptr[loc])
172 continue;
173 if (leaf && loc < N_ARGS && beg == 0 &&
174 rgn_available(beg, end, argregs[loc])) {
175 rgn[r].reg = argregs[loc];
176 continue;
178 for (j = 0; j < regs_n; j++)
179 if (rgn_available(beg, end, regs[j]))
180 break;
181 if (j < regs_n)
182 rgn[r].reg = regs[j];
184 free(srt);
187 void reg_init(struct ic *ic, long ic_n)
189 long loc, off;
190 int *loc_sz;
191 int leaf = 1;
192 long i;
193 for (i = 0; i < ic_n; i++)
194 if (ic[i].op & O_LOC && !ic_loc(ic, i, &loc, &off))
195 if (loc + 1 >= loc_n)
196 loc_n = loc + 1;
197 loc_ptr = calloc(loc_n, sizeof(loc_ptr[0]));
198 loc_sz = calloc(loc_n, sizeof(loc_sz[0]));
199 for (i = 0; i < loc_n; i++)
200 loc_ptr[i] = !opt(1);
201 for (i = 0; i < ic_n; i++) {
202 long oc = O_C(ic[i].op);
203 if (ic_loc(ic, i, &loc, &off))
204 continue;
205 if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) {
206 int sz = T_SZ(O_T(ic[i].op));
207 if (!loc_sz[loc])
208 loc_sz[loc] = sz;
209 if (off || sz < 2 || sz != loc_sz[loc])
210 loc_ptr[loc]++;
212 if (oc == (O_MOV | O_LOC))
213 loc_ptr[loc]++;
215 free(loc_sz);
216 for (i = 0; i < ic_n; i++)
217 if (ic[i].op & O_CALL)
218 leaf = 0;
219 dst_head = malloc(ic_n * sizeof(dst_head[0]));
220 dst_next = malloc(ic_n * sizeof(dst_next[0]));
221 for (i = 0; i < ic_n; i++)
222 dst_head[i] = -1;
223 for (i = 0; i < ic_n; i++)
224 dst_next[i] = -1;
225 for (i = 0; i < ic_n; i++) {
226 if (ic[i].op & O_JXX) {
227 dst_next[i] = dst_head[ic[i].a3];
228 dst_head[ic[i].a3] = i;
231 for (i = 0; i < loc_n; i++) {
232 if (!loc_ptr[i] && opt(2))
233 reg_regions(ic, ic_n, i);
234 if (!loc_ptr[i] && !opt(2))
235 rgn_add(i, 0, ic_n, reg_loccnt(ic, ic_n, i));
237 reg_glob(leaf);
240 long reg_mask(void)
242 long ret = 0;
243 int i;
244 for (i = 0; i < rgn_n; i++)
245 if (rgn[i].reg >= 0)
246 ret |= 1 << rgn[i].reg;
247 return ret;
250 /* return the allocated register of local loc */
251 int reg_lmap(long c, long loc)
253 int i;
254 for (i = 0; i < rgn_n; i++)
255 if (rgn[i].loc == loc)
256 if (rgn[i].beg <= c && rgn[i].end > c)
257 return rgn[i].reg;
258 return -1;
261 /* return the local to which register reg is allocated */
262 int reg_rmap(long c, long reg)
264 int i;
265 for (i = 0; i < rgn_n; i++)
266 if (rgn[i].reg == reg)
267 if (rgn[i].beg <= c && rgn[i].end > c)
268 return rgn[i].loc;
269 return -1;
272 void reg_done(void)
274 free(dst_head);
275 free(dst_next);
276 free(loc_ptr);
277 free(rgn);
278 loc_ptr = NULL;
279 rgn = NULL;
280 rgn_sz = 0;
281 rgn_n = 0;
282 loc_n = 0;
285 int reg_safe(long loc)
287 return loc < loc_n && !loc_ptr[loc];