Hello,
I have found an interesting bug when increasing the pressure on the register
allocator after some modifications in use-def (namely marking MUL as defining
EAX and EDX on x86).
I have an interval (actually, a split-out part of an interval) that gets no
register allocated.
Here is the regalloc trace :
Liveness:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
14: --------------- (start: 10, end: 15)
13: --------------- (start: 10, end: 15)
12: ********************************* (start: 4, end: 15)
11: *************************** (start: 6, end: 15)
10: --------------- (start: 10, end: 15)
9: ------------------ (start: 9, end: 15)
8: ************************************ (start: 3, end: 15)
7: *************************************** (start: 2, end: 15)
6: ****************************************** (start: 1, end: 15)
5: ********************************************* (start: 0, end: 15)
4: --------------- (start: 10, end: 15)
3: (empty)
2: --------------- (start: 10, end: 15)
1: (empty)
0: (empty)
found with i=0
Register Allocation:
14 (pos: 10-15): EDX fixed no spill no reload
13 (pos: 10-15): EAX fixed no spill no reload
12 (pos: 4-10): EDX non-fixed spill no reload
12 (pos: 10-15): EBX non-fixed no spill reload
11 (pos: 6- 9): EAX non-fixed spill no reload
11 (pos: 9-15): <unassigned> non-fixed no spill reload
10 (pos: 10-15): EDX fixed no spill no reload
9 (pos: 9-15): EAX fixed no spill no reload
8 (pos: 3-15): EDI non-fixed no spill no reload
7 (pos: 2-15): ESI non-fixed no spill no reload
6 (pos: 1-10): EBX non-fixed spill no reload
6 (pos: 10-15): EBX non-fixed no spill no reload
5 (pos: 0-15): ECX non-fixed no spill no reload
4 (pos: 10-15): EDX fixed no spill no reload
3 (pos: -1- 0): ECX fixed no spill no reload
2 (pos: 10-15): EAX fixed no spill no reload
1 (pos: -1- 0): ESP fixed no spill no reload
0 (pos: -1- 0): EBP fixed no spill no reload
As you can see, interval 11 is split, the first part correctly marked as
spilled at the end, the second part correctly marked as reloaded in the
beginning, but the second part gets no register allocated.
How is this possible? Whenever we split an interval (reminder: we implement
Wimmer's thesis, 2004 algorithm), we add the split child to the unhandled list,
which is sorted by ascending start position.
And here comes the interesting part: the algorithm relies on browsing this
unhandled list. We do it using "list_for_each_entry_safe(current, tmp,
&unhandled, interval_node)".
_safe is safe for deletion of the current list element - it does this by
preloading the next element before iterating on the current one. One side
effect is that if the iteration on the current element modifies its successor,
the _safe iterator will *not* properly pick it up.
As a result our interval is not considered by the register allocator, which is
I believe why it gets no register allocated.
How did I prove that the successor was getting modified (if you modify elements
further away in the list everything goes fine)?
Here is a piece of patch that traces the position of insertion into the list
when spilling an interval:
/* Inserts to a list of intervals sorted by
increasing start position. */ +int outp = 0;
static void
insert_to_list(struct live_interval *interval, struct list_head *interval_list)
{
@@ -110,11 +111,15 @@ insert_to_list(struct live_interval *interval, struct
list_head *interval_list)
* If we find an existing interval, that starts _after_ the
* new interval, add ours before that.
*/
+ int i = 0;
list_for_each_entry(this, interval_list, interval_node) {
if (interval->range.start < this->range.start) {
list_add_tail(&interval->interval_node,
&this->interval_node);
+ if(outp)
+ printf("found with i=%d\n",i);
return;
}
+ i++;
}
/*
@@ -298,7 +303,9 @@ static void try_to_allocate_free_reg(struct live_interval
*current, */
new = split_interval_at(current, free_until_pos[reg]);
mark_need_reload(new, current);
+ outp=1;
insert_to_list(new, unhandled);
+ outp=0;
current->reg = reg;
current->need_spill = 1;
}
The output I get?
"found with i=0"
The solution I have in mind is to avoid using the _safe iterator, but simply
pick the head of the unhandled list at every iteration.
I am sending this explanation because it is important so my next patch is well
understood.
--
Greetings,
A.H.
------------------------------------------------------------------------------
This SF.net email is sponsored by:
High Quality Requirements in a Collaborative Environment.
Download a free trial of Rational Requirements Composer Now!
http://p.sf.net/sfu/www-ibm-com
_______________________________________________
Jatovm-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
