2 * linear-scan.c: linbear scan register allocation
5 * Dietmar Maurer (dietmar@ximian.com)
6 * Miguel de Icaza (miguel@ximian.com)
8 * (C) 2001 Ximian, Inc.
17 //#define MNAME "nest_test"
20 #define DEGUG_LIVENESS
25 mono_bitset_mp_new (MonoMemPool
*mp
, guint32 max_size
)
27 int size
= mono_bitset_alloc_size (max_size
, 0);
30 mem
= mono_mempool_alloc0 (mp
, size
);
31 return mono_bitset_mem_new (mem
, max_size
, MONO_BITSET_DONT_FREE
);
35 mono_bitset_print (MonoBitSet
*set
)
40 for (i
= 0; i
< mono_bitset_size (set
); i
++) {
42 if (mono_bitset_test (set
, i
))
50 mono_update_live_range (MonoFlowGraph
*cfg
, int varnum
, int block_num
, int tree_pos
)
52 MonoVarInfo
*vi
= &g_array_index (cfg
->varinfo
, MonoVarInfo
, varnum
);
53 guint32 abs_pos
= (block_num
<< 16) | tree_pos
;
55 if (vi
->range
.first_use
.abs_pos
> abs_pos
)
56 vi
->range
.first_use
.abs_pos
= abs_pos
;
58 if (vi
->range
.last_use
.abs_pos
< abs_pos
)
59 vi
->range
.last_use
.abs_pos
= abs_pos
;
63 mono_update_live_info (MonoFlowGraph
*cfg
)
67 for (i
= 0; i
< cfg
->block_count
; i
++) {
68 MonoBBlock
*bb
= &cfg
->bblocks
[i
];
70 for (j
= cfg
->varinfo
->len
- 1; j
> 0; j
--) {
72 if (mono_bitset_test (bb
->live_in_set
, j
))
73 mono_update_live_range (cfg
, j
, bb
->num
, 0);
75 if (mono_bitset_test (bb
->live_out_set
, j
))
76 mono_update_live_range (cfg
, j
, bb
->num
, bb
->forest
->len
);
82 mono_update_gen_set (MonoFlowGraph
*cfg
, MonoBBlock
*bb
, MBTree
*tree
,
83 int tnum
, MonoBitSet
*set
)
87 case MB_TERM_REMOTE_STIND_I1
:
88 case MB_TERM_REMOTE_STIND_I2
:
89 case MB_TERM_REMOTE_STIND_I4
:
90 case MB_TERM_REMOTE_STIND_I8
:
91 case MB_TERM_REMOTE_STIND_R4
:
92 case MB_TERM_REMOTE_STIND_R8
:
93 case MB_TERM_REMOTE_STIND_OBJ
:
94 case MB_TERM_STIND_I1
:
95 case MB_TERM_STIND_I2
:
96 case MB_TERM_STIND_I4
:
97 case MB_TERM_STIND_I8
:
98 case MB_TERM_STIND_R4
:
99 case MB_TERM_STIND_R8
:
100 case MB_TERM_STIND_OBJ
:
101 if (tree
->left
->op
!= MB_TERM_ADDR_L
)
102 mono_update_gen_set (cfg
, bb
, tree
->left
, tnum
, set
);
104 mono_update_live_range (cfg
, tree
->left
->data
.i
,
108 mono_update_gen_set (cfg
, bb
, tree
->left
, tnum
, set
);
114 mono_update_gen_set (cfg
, bb
, tree
->right
, tnum
, set
);
116 if (tree
->op
== MB_TERM_ADDR_L
) {
117 mono_update_live_range (cfg
, tree
->data
.i
, bb
->num
, tnum
);
118 mono_bitset_set (set
, tree
->data
.i
);
123 mono_analyze_liveness (MonoFlowGraph
*cfg
)
125 MonoBitSet
*old_live_in_set
, *old_live_out_set
;
128 int i
, j
, max_vars
= cfg
->varinfo
->len
;
130 #ifdef DEGUG_LIVENESS
131 int debug
= !strcmp (cfg
->method
->name
, MNAME
);
133 printf ("LIVENLESS %s.%s:%s\n", cfg
->method
->klass
->name_space
,
134 cfg
->method
->klass
->name
, cfg
->method
->name
);
137 old_live_in_set
= mono_bitset_new (max_vars
, 0);
138 old_live_out_set
= mono_bitset_new (max_vars
, 0);
140 for (i
= 0; i
< cfg
->block_count
; i
++) {
141 MonoBBlock
*bb
= &cfg
->bblocks
[i
];
143 bb
->gen_set
= mono_bitset_mp_new (cfg
->mp
, max_vars
);
144 bb
->kill_set
= mono_bitset_mp_new (cfg
->mp
, max_vars
);
145 bb
->live_in_set
= mono_bitset_mp_new (cfg
->mp
, max_vars
);
146 bb
->live_out_set
= mono_bitset_mp_new (cfg
->mp
, max_vars
);
148 for (j
= 0; j
< bb
->forest
->len
; j
++) {
149 MBTree
*t1
= (MBTree
*) g_ptr_array_index (bb
->forest
, j
);
151 mono_bitset_clear_all (old_live_in_set
);
152 mono_update_gen_set (cfg
, bb
, t1
, j
, old_live_in_set
);
153 mono_bitset_sub (old_live_in_set
, bb
->kill_set
);
154 mono_bitset_union (bb
->gen_set
, old_live_in_set
);
157 case MB_TERM_REMOTE_STIND_I1
:
158 case MB_TERM_REMOTE_STIND_I2
:
159 case MB_TERM_REMOTE_STIND_I4
:
160 case MB_TERM_REMOTE_STIND_I8
:
161 case MB_TERM_REMOTE_STIND_R4
:
162 case MB_TERM_REMOTE_STIND_R8
:
163 case MB_TERM_REMOTE_STIND_OBJ
:
164 case MB_TERM_STIND_I1
:
165 case MB_TERM_STIND_I2
:
166 case MB_TERM_STIND_I4
:
167 case MB_TERM_STIND_I8
:
168 case MB_TERM_STIND_R4
:
169 case MB_TERM_STIND_R8
:
170 case MB_TERM_STIND_OBJ
:
171 if (t1
->left
->op
== MB_TERM_ADDR_L
)
172 mono_bitset_set (bb
->kill_set
, t1
->left
->data
.i
);
177 #ifdef DEGUG_LIVENESS
179 printf ("BLOCK %d (", bb
->num
);
180 for (l
= bb
->succ
; l
; l
= l
->next
) {
181 MonoBBlock
*t
= (MonoBBlock
*)l
->data
;
182 printf ("%d, ", t
->num
);
185 printf ("GEN %d: ", i
); mono_bitset_print (bb
->gen_set
); printf ("\n");
186 printf ("KILL %d: ", i
); mono_bitset_print (bb
->kill_set
); printf ("\n");
194 for (i
= cfg
->block_count
- 1; i
>= 0; i
--) {
195 MonoBBlock
*bb
= &cfg
->bblocks
[i
];
197 mono_bitset_copyto (bb
->live_in_set
, old_live_in_set
);
198 mono_bitset_copyto (bb
->live_out_set
, old_live_out_set
);
200 mono_bitset_copyto (bb
->live_out_set
, bb
->live_in_set
);
201 mono_bitset_sub (bb
->live_in_set
, bb
->kill_set
);
202 mono_bitset_union (bb
->live_in_set
, bb
->gen_set
);
204 mono_bitset_clear_all (bb
->live_out_set
);
206 for (l
= bb
->succ
; l
; l
= l
->next
) {
207 MonoBBlock
*t
= (MonoBBlock
*)l
->data
;
208 mono_bitset_union (bb
->live_out_set
, t
->live_in_set
);
211 if (!(mono_bitset_equal (old_live_in_set
, bb
->live_in_set
) &&
212 mono_bitset_equal (old_live_out_set
, bb
->live_out_set
)))
218 mono_bitset_free (old_live_in_set
);
219 mono_bitset_free (old_live_out_set
);
222 #ifdef DEGUG_LIVENESS
224 for (i
= 0; i
< cfg
->block_count
; i
++) {
225 MonoBBlock
*bb
= &cfg
->bblocks
[i
];
227 printf ("LIVE IN %d: ", i
);
228 mono_bitset_print (bb
->live_in_set
);
230 printf ("LIVE OUT %d: ", i
);
231 mono_bitset_print (bb
->live_out_set
);
239 mono_varlist_insert_sorted (GList
*list
, MonoVarInfo
*vi
, gboolean sort_end
)
244 return g_list_prepend (NULL
, vi
);
246 for (l
= list
; l
; l
= l
->next
) {
247 MonoVarInfo
*v
= (MonoVarInfo
*)l
->data
;
250 if (vi
->range
.last_use
.abs_pos
<= v
->range
.last_use
.abs_pos
) {
251 list
= g_list_insert_before (list
, l
, vi
);
255 if (vi
->range
.first_use
.abs_pos
<= v
->range
.first_use
.abs_pos
) {
256 list
= g_list_insert_before (list
, l
, vi
);
262 list
= g_list_append (list
, vi
);
268 mono_linear_scan (MonoFlowGraph
*cfg
, guint32
*used_mask
)
270 GList
*l
, *ranges
= NULL
;
271 GList
*active
= NULL
;
276 MonoMethod
*m
= cfg
->method
;
277 int debug
= !strcmp (cfg
->method
->name
, MNAME
);
280 printf ("VARINFO for %s.%s:%s\n", m
->klass
->name_space
, m
->klass
->name
, m
->name
);
283 mono_analyze_liveness (cfg
);
284 mono_update_live_info (cfg
);
286 for (i
= 1; i
< cfg
->varinfo
->len
; i
++) {
287 MonoVarInfo
*vi
= &g_array_index (cfg
->varinfo
, MonoVarInfo
, i
);
290 if (vi
->range
.first_use
.abs_pos
> vi
->range
.last_use
.abs_pos
)
293 /* we can only allocate 32 bit values */
294 if (vi
->isvolatile
|| (vi
->type
!= VAL_I32
&& vi
->type
!= VAL_POINTER
))
297 ranges
= mono_varlist_insert_sorted (ranges
, vi
, FALSE
);
303 for (l
= ranges
; l
; l
= l
->next
) {
304 MonoVarInfo
*vi
= (MonoVarInfo
*)l
->data
;
306 printf ("VAR %d %08x %08x\n", vi
->varnum
, vi
->range
.first_use
.abs_pos
,
307 vi
->range
.last_use
.abs_pos
);
312 /* we can use 2 registers for global allocation */
313 regs
= g_list_prepend (regs
, (gpointer
)X86_EBX
);
314 regs
= g_list_prepend (regs
, (gpointer
)X86_ESI
);
316 max_regs
= g_list_length (regs
);
320 for (l
= ranges
; l
; l
= l
->next
) {
321 MonoVarInfo
*vi
= (MonoVarInfo
*)l
->data
;
325 printf ("START %2d %08x %08x\n", vi
->varnum
, vi
->range
.first_use
.abs_pos
,
326 vi
->range
.last_use
.abs_pos
);
328 /* expire old intervals in active */
330 MonoVarInfo
*v
= (MonoVarInfo
*)active
->data
;
332 if (v
->range
.last_use
.abs_pos
>= vi
->range
.first_use
.abs_pos
)
337 printf ("EXPIR %2d %08x %08x\n", v
->varnum
,
338 v
->range
.first_use
.abs_pos
, v
->range
.last_use
.abs_pos
);
340 active
= g_list_remove_link (active
, active
);
341 regs
= g_list_prepend (regs
, (gpointer
)v
->reg
);
344 if (active
&& g_list_length (active
) == max_regs
) {
347 GList
*a
= g_list_nth (active
, max_regs
- 1);
348 MonoVarInfo
*v
= (MonoVarInfo
*)a
->data
;
350 if (v
->range
.last_use
.abs_pos
> vi
->range
.last_use
.abs_pos
) {
353 active
= g_list_remove_link (active
, a
);
354 active
= mono_varlist_insert_sorted (active
, vi
, TRUE
);
357 printf ("SPILL0 %2d %08x %08x\n", v
->varnum
,
358 v
->range
.first_use
.abs_pos
, v
->range
.last_use
.abs_pos
);
363 printf ("SPILL1 %2d %08x %08x\n", vi
->varnum
,
364 vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
369 /* assign register */
373 vi
->reg
= (int)regs
->data
;
375 *used_mask
|= 1 << vi
->reg
;
377 regs
= g_list_remove_link (regs
, regs
);
381 printf ("ADD %2d %08x %08x\n", vi
->varnum
,
382 vi
->range
.first_use
.abs_pos
, vi
->range
.last_use
.abs_pos
);
384 active
= mono_varlist_insert_sorted (active
, vi
, TRUE
);
391 for (a
= active
; a
; a
= a
->next
) {
392 MonoVarInfo
*v
= (MonoVarInfo
*)a
->data
;
394 printf ("ACT %2d %08x %08x %d\n", v
->varnum
,
395 v
->range
.first_use
.abs_pos
, v
->range
.last_use
.abs_pos
, v
->reg
);
403 g_list_free (active
);
404 g_list_free (ranges
);