This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

Daniel Berlin wrote:
Jan Hubicka wrote:
Jan Hubicka wrote:
Jan Hubicka wrote:

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.


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]