Re: Patch: Support IA-64 speculation [4/5]

[Daniel Berlin <dberlin at dberlin dot org>]

Jan Hubicka wrote:
>> Jan Hubicka wrote:
>>>> Jan Hubicka wrote:
>>>>>> Hi!
>>>>>>
>>>>>> Before my patch the scheduler needed only the number of remaining 
>>>>>> dependencies, hence it didn't actually removed anything from the 
>>>>>> LOG_LINKS.  My patch, on the contrary, has to analyze remaining 
>>>>>> dependences and keep the list of them updated - that is what this 
>>>>>> function do - finding the link between two instructions and moving it 
>>>>> >from the one list to another.  Arguments (NEXT and INSN) come from the 
>>>>>> level up, which is walking through the INSN_DEPEND list of the INSN. 
>>>>>> This list basically has the same length as LOG_LINKS (here is quadratic 
>>>>>> behavior) and contains instructions, which depend upon this one.
>>>>>>
>>>>>> I think the best way to solve this problem is to store in the nodes of 
>>>>>> INSN_DEPEND list pointers to the corresponding nodes of the LOG_LINKS 
>>>>>> so that we won't have to walk through the entire LOG_LINKS searching 
>>>>>> for the right node.  This change will be small and affect only two 
>>>>>> places in scheduler:
>>>>>> 1. creation of the INSN_DEPEND lists.
>>>>>> 2. the above function.
>>>>>>
>>>>>> If this fix looks OK to you, please let me know and I'll write (and 
>>>>>> post) the patch.
>>>>> Yes, it seems fine to me, but how are you going to remove the item from
>>>>> LOG_LINKS effectivly then? (it is single linked list).
>>>>> I guess it is possible to deffer the actual removal for time you are
>>>>> processing dependencies of the next instruction or something...
>>>> I will use the standard trick: swap the data between the current node 
>>>> and the next one and remove the next.  To handle the last node we also 
>>>> need to track the end of the LOG_LINKS for each insn - that's not too 
>>>> difficult.
>>> Won't it invalidate the log links pointers in INSN_DEPEND lists?
>> You're right.  Then we need to make LOG_LINKS bi-directional.A
> 
> That would probably work, but other problem is that large linked lists
> are also memory hoghs.  In fact they consume 193MB, 57% of overall
> memory (it is the gen_rtx_fmt_ue)

If you are going to go this far, it seems to me that we should just make
a real, regular (IE not rtl), linked list and keep it on the side (or
attach it to the insn somehow), instead of propagating the hack that is
log links, and making them bigger.

Nothing uses the scheduler's log links but the scheduler, AFAIK, so this
shouldn't be too bad.

--Dan