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

Maxim Kuvyrkov mkuvyrkov@ispras.ru
Wed Aug 2 14:18:00 GMT 2006


Daniel Berlin wrote:
> 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

If fix for the 4.2 release is needed, then, IMHO, it should be 
double-linked LOG_LINKS.  During stage1 I'll write (hope so :) better 
dependency handling for the scheduler.

--
Maxim



More information about the Gcc-patches mailing list