Re: Question of the DFA scheduler

["Ling-hua Tseng" <uranus at it dot muds dot net>]

I figured out that the insn_latency(insn1, insn2) is always returning a constant value in any states
(i.e., it's a static value, not be determined dynamically).
It seems to cost much time complexity if I impelemented the `nop inserting' in the reorg pass.
Because the `nop inserting' algorithm may be writtern as the following pseudo code:
   if(LOG_LINK(insn) is not empty) {
       foreach (dep_insn in LOG_LINK(insn)) {
           if(dep type is not true dependency) continue;
           stalls = insn_latency(dep_insn, insn);
           count =  the distance between insn and dep_insn;
           if(stalls > count) emit (stalls - count - 1) NOPs before insn;
       }
   }
The time complexity of this algorithm is O(n sqaure) and maybe highly increasing the compilation time.
Are there any better solution for the nop inserting?

Thanks a lot.

----- Original Message ----- 
From: "Richard Sandiford" <richard@codesourcery.com>
To: "Ling-hua Tseng" <uranus@it.muds.net>
Cc: <gcc@gcc.gnu.org>
Sent: Thursday, August 11, 2005 6:49 PM
Subject: Re: Question of the DFA scheduler


> "Ling-hua Tseng" <uranus@it.muds.net> writes:
> > The destination operand of the `sub' instruction, d0, will be written
> > back in the 4th cycle, and the instruction `max' will use it as source
> > operand (i.e., there is a true data dependency).
> >
> > I figured out that the state_transition() returns -1 when I issuing
> > the `max' instruction, and I figured out it only returns > 0 when
> > "hardware structural hazard" occured.
>
> Right.  state_transition just checks for unit hazards, not data hazards.
>
> Instruction dependencies are detected by sched-deps.c and stored in the
> instructions' LOG_LINKS.  insn_latency (in insn-attrtab.c) gives the
> latency for two dependent instructions.
>
> Richard