1 /* neatcc global register allocation */
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
)) {
17 if (oc
== (O_ST
| O_LOC
)) {
25 /* local live region */
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
)
47 for (i
= 0; i
< rgn_n
; i
++) {
48 if (rgn
[i
].loc
== loc
&& rgn
[i
].beg
< end
&& rgn
[i
].end
> beg
) {
57 for (i
= 0; i
< rgn_n
; i
++)
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]));
74 /* return nonzero if register reg is free from beg till end */
75 static int rgn_available(long beg
, long end
, int reg
)
78 for (i
= 0; i
< rgn_n
; i
++)
79 if (rgn
[i
].reg
== reg
)
80 if (rgn
[i
].beg
< end
&& rgn
[i
].end
> beg
)
85 static long reg_region(struct ic
*ic
, long ic_n
, long loc
, long pos
,
86 long *beg
, long *end
, char *mark
)
90 for (; pos
>= 0; pos
--) {
98 if (IC_LST(ic
, pos
) == loc
)
100 if (IC_LLD(ic
, pos
) == loc
)
104 cnt
+= reg_region(ic
, ic_n
, loc
, dst
, beg
, end
, mark
);
107 if (pos
> 0 && ic
[pos
- 1].op
& O_JMP
)
113 /* compute local's live regions */
114 static void reg_regions(struct ic
*ic
, long ic_n
, long loc
)
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
]) {
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);
135 /* number of times a local is accessed */
136 static long reg_loccnt(struct ic
*ic
, long ic_n
, long loc
)
140 for (i
= 0; i
< ic_n
; i
++)
141 if (IC_LLD(ic
, i
) == loc
|| IC_LST(ic
, i
) == loc
)
146 /* perform global register allocation */
147 static void reg_glob(int leaf
)
152 int regs_max
= MIN(N_TMPS
>> 1, 4);
153 long regs_mask
= leaf
? R_TMPS
: R_PERM
;
155 for (i
= leaf
? 1 : 3; i
< N_TMPS
&& regs_n
< regs_max
; i
++)
156 if ((1 << i
) & regs_mask
)
158 srt
= malloc(rgn_n
* sizeof(srt
[0]));
160 for (i
= 0; i
< rgn_n
; i
++) {
161 for (j
= i
- 1; j
>= 0 && rgn
[i
].cnt
> rgn
[srt
[j
]].cnt
; j
--)
165 /* allocating registers */
166 for (i
= 0; i
< rgn_n
; 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
])
173 if (leaf
&& loc
< N_ARGS
&& beg
== 0 &&
174 rgn_available(beg
, end
, argregs
[loc
])) {
175 rgn
[r
].reg
= argregs
[loc
];
178 for (j
= 0; j
< regs_n
; j
++)
179 if (rgn_available(beg
, end
, regs
[j
]))
182 rgn
[r
].reg
= regs
[j
];
187 void reg_init(struct ic
*ic
, long ic_n
)
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
)
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
))
205 if (oc
== (O_LD
| O_LOC
) || oc
== (O_ST
| O_LOC
)) {
206 int sz
= T_SZ(O_T(ic
[i
].op
));
209 if (off
|| sz
< 2 || sz
!= loc_sz
[loc
])
212 if (oc
== (O_MOV
| O_LOC
))
216 for (i
= 0; i
< ic_n
; i
++)
217 if (ic
[i
].op
& O_CALL
)
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
++)
223 for (i
= 0; i
< ic_n
; i
++)
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
));
244 for (i
= 0; i
< rgn_n
; i
++)
246 ret
|= 1 << rgn
[i
].reg
;
250 /* return the allocated register of local loc */
251 int reg_lmap(long c
, long loc
)
254 for (i
= 0; i
< rgn_n
; i
++)
255 if (rgn
[i
].loc
== loc
)
256 if (rgn
[i
].beg
<= c
&& rgn
[i
].end
> c
)
261 /* return the local to which register reg is allocated */
262 int reg_rmap(long c
, long reg
)
265 for (i
= 0; i
< rgn_n
; i
++)
266 if (rgn
[i
].reg
== reg
)
267 if (rgn
[i
].beg
<= c
&& rgn
[i
].end
> c
)
285 int reg_safe(long loc
)
287 return loc
< loc_n
&& !loc_ptr
[loc
];