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" <[EMAIL PROTECTED]>
To: "Ling-hua Tseng" <[EMAIL PROTECTED]>
Cc: <gcc@gcc.gnu.org>
Sent: Thursday, August 11, 2005 6:49 PM
Subject: Re: Question of the DFA scheduler
"Ling-hua Tseng" <[EMAIL PROTECTED]> 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
