2 * Copyright (C) 2009 Nicolai Haehnle.
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial
16 * portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
21 * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 #include "radeon_program_pair.h"
32 #include "radeon_compiler.h"
33 #include "radeon_dataflow.h"
38 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)
41 struct live_intervals
{
44 struct live_intervals
* Next
;
47 struct register_info
{
48 struct live_intervals Live
;
51 unsigned int Allocated
:1;
53 unsigned int Index
:RC_REGISTER_INDEX_BITS
;
56 struct hardware_register
{
57 struct live_intervals
* Used
;
60 struct regalloc_state
{
61 struct radeon_compiler
* C
;
63 struct register_info Input
[RC_REGISTER_MAX_INDEX
];
64 struct register_info Temporary
[RC_REGISTER_MAX_INDEX
];
66 struct hardware_register
* HwTemporary
;
67 unsigned int NumHwTemporaries
;
70 static void print_live_intervals(struct live_intervals
* src
)
78 DBG("(%i,%i)", src
->Start
, src
->End
);
83 static void add_live_intervals(struct regalloc_state
* s
,
84 struct live_intervals
** dst
, struct live_intervals
* src
)
86 struct live_intervals
** dst_backup
= dst
;
89 DBG("add_live_intervals: ");
90 print_live_intervals(*dst
);
92 print_live_intervals(src
);
97 if (*dst
&& (*dst
)->End
< src
->Start
) {
99 } else if (!*dst
|| (*dst
)->Start
> src
->End
) {
100 struct live_intervals
* li
= memory_pool_malloc(&s
->C
->Pool
, sizeof(*li
));
101 li
->Start
= src
->Start
;
107 if (src
->End
> (*dst
)->End
)
108 (*dst
)->End
= src
->End
;
109 if (src
->Start
< (*dst
)->Start
)
110 (*dst
)->Start
= src
->Start
;
117 print_live_intervals(*dst_backup
);
122 static int overlap_live_intervals(struct live_intervals
* dst
, struct live_intervals
* src
)
125 DBG("overlap_live_intervals: ");
126 print_live_intervals(dst
);
128 print_live_intervals(src
);
133 if (dst
->End
<= src
->Start
) {
135 } else if (dst
->End
<= src
->End
) {
138 } else if (dst
->Start
< src
->End
) {
146 DBG(" no overlap\n");
151 static int try_add_live_intervals(struct regalloc_state
* s
,
152 struct live_intervals
** dst
, struct live_intervals
* src
)
154 if (overlap_live_intervals(*dst
, src
))
157 add_live_intervals(s
, dst
, src
);
161 static void scan_callback(void * data
, struct rc_instruction
* inst
,
162 rc_register_file file
, unsigned int index
, unsigned int mask
)
164 struct regalloc_state
* s
= data
;
165 struct register_info
* reg
;
167 if (file
== RC_FILE_TEMPORARY
)
168 reg
= &s
->Temporary
[index
];
169 else if (file
== RC_FILE_INPUT
)
170 reg
= &s
->Input
[index
];
176 if (file
== RC_FILE_INPUT
)
177 reg
->Live
.Start
= -1;
179 reg
->Live
.Start
= inst
->IP
;
180 reg
->Live
.End
= inst
->IP
;
182 if (inst
->IP
> reg
->Live
.End
)
183 reg
->Live
.End
= inst
->IP
;
187 static void compute_live_intervals(struct regalloc_state
* s
)
189 rc_recompute_ips(s
->C
);
191 for(struct rc_instruction
* inst
= s
->C
->Program
.Instructions
.Next
;
192 inst
!= &s
->C
->Program
.Instructions
;
194 rc_for_all_reads_mask(inst
, scan_callback
, s
);
195 rc_for_all_writes_mask(inst
, scan_callback
, s
);
199 static void remap_register(void * data
, struct rc_instruction
* inst
,
200 rc_register_file
* file
, unsigned int * index
)
202 struct regalloc_state
* s
= data
;
203 const struct register_info
* reg
;
205 if (*file
== RC_FILE_TEMPORARY
)
206 reg
= &s
->Temporary
[*index
];
207 else if (*file
== RC_FILE_INPUT
)
208 reg
= &s
->Input
[*index
];
212 if (reg
->Allocated
) {
218 static void do_regalloc(struct regalloc_state
* s
)
220 /* Simple and stupid greedy register allocation */
221 for(unsigned int index
= 0; index
< RC_REGISTER_MAX_INDEX
; ++index
) {
222 struct register_info
* reg
= &s
->Temporary
[index
];
227 for(unsigned int hwreg
= 0; hwreg
< s
->NumHwTemporaries
; ++hwreg
) {
228 if (try_add_live_intervals(s
, &s
->HwTemporary
[hwreg
].Used
, ®
->Live
)) {
230 reg
->File
= RC_FILE_TEMPORARY
;
236 rc_error(s
->C
, "Ran out of hardware temporaries\n");
242 /* Rewrite all instructions based on the translation table we built */
243 for(struct rc_instruction
* inst
= s
->C
->Program
.Instructions
.Next
;
244 inst
!= &s
->C
->Program
.Instructions
;
246 rc_remap_registers(inst
, &remap_register
, s
);
250 static void alloc_input(void * data
, unsigned int input
, unsigned int hwreg
)
252 struct regalloc_state
* s
= data
;
254 if (!s
->Input
[input
].Used
)
257 add_live_intervals(s
, &s
->HwTemporary
[hwreg
].Used
, &s
->Input
[input
].Live
);
259 s
->Input
[input
].Allocated
= 1;
260 s
->Input
[input
].File
= RC_FILE_TEMPORARY
;
261 s
->Input
[input
].Index
= hwreg
;
265 void rc_pair_regalloc(struct r300_fragment_program_compiler
*c
, unsigned maxtemps
)
267 struct regalloc_state s
;
269 memset(&s
, 0, sizeof(s
));
271 s
.NumHwTemporaries
= maxtemps
;
272 s
.HwTemporary
= memory_pool_malloc(&s
.C
->Pool
, maxtemps
*sizeof(struct hardware_register
));
273 memset(s
.HwTemporary
, 0, maxtemps
*sizeof(struct hardware_register
));
275 compute_live_intervals(&s
);
277 c
->AllocateHwInputs(c
, &alloc_input
, &s
);