Incorrect DFA scheduling of output dependency.

[Vladimir Makarov]

Daniel Towner wrote:

> Steven, Nathan, et al.
>
>> You're not making this easy because you haven't told anything about:
>> 1) what target you're working on (apparently something that is not
>>   in the FSF GCC tree);
>> 2) what your DFA description looks like (did you tell the scheduler
>>   that those two instructions are issued in parallel?); and
>> 3) what version of GCC you are working with.
>>  
>>
> I'm working on a 16-bit DSP port of gcc, which hasn't been contributed 
> back to the mainline tree yet. The port is based on 3.4.3
>
> The DFA scheduler describes a machine which has 3 execution slots, 
> plus an additional slot for a long immediate value. I've attached my 
> DFA description below. The DFA scheduler normally ensures that 
> instructions with data dependencies are placed in different cycles. 
> Once the scheduler has completed, the first instruction for each cycle 
> is marked with a TI mode instruction. I have specialised versions of 
> asm_output_opcode and final_prescan_insn which detect the TI mode 
> labels, and arrange for the assembly output to include the VLIW 
> packing information.
>
> I have to use the machine dependent reorganisation phase to run the 
> scheduler, so that the last-jump-optimisation doesn't disturb the TI 
> mode labels applied to the first instruction in each clock cycle (as 
> per the IA64).

Yes that is right it should be the very last pass of the compiler to 
generate correct code for a VLIW processor based on the labels set up 
the scheduler.

>
>> But first look at the scheduler dumps (-dS and -dR) to see if the
>> output dependency is there, of course...
>>
> I was wrong here. The instruction sequence is actually a data 
> (read-after-write) dependency, not an output dependency 
> (write-after-write). However, the relevent portion of the scheduler 
> dump is as follows:
>
> (note 82 147 64 2 [bb 2] NOTE_INSN_BASIC_BLOCK)
>
> (insn:TI 64 82 150 2 (set (reg/v:HI 4 R4 [orig:25 rdIndex ] [25])
>        (const_int 0 [0x0])) 15 {movhi} (nil)
>    (nil))
>
> (note 150 64 133 2 NOTE_INSN_LOOP_END)
>
> (insn 133 150 135 2 (set (reg:HI 5 R5 [33])
>        (ashift:HI (reg/v:HI 4 R4 [orig:25 rdIndex ] [25])
>            (const_int 2 [0x2]))) 48 {ashlhi3} (insn_list:REG_DEP_ANTI 
> 64 (nil))
>    (expr_list:REG_EQUAL (ashift:HI (reg/v:HI 4 R4 [orig:25 rdIndex ] 
> [25])
>            (const_int 2 [0x2]))
>        (nil)))
>
> Does this state that insn 133 is anti-dependent on insn 64?

Yes, it does.  And that is wrong.

> An anti-dependency is a write following a read, but in this sequence a 
> read follows a write. The anti-dependency first appears after the 
> basic block reordering pass has been run (which is immediately before 
> the instruction scheduling pass).

The information is not enough to make a real analysis of the bug.  But I 
can guess.

Even if the dependence was added in basic block reordering pass (can not 
say more about this), it should have been removed in insn scheduling 
first.  Even if the dependence was not removed, it should have been 
changed by higher priority dependence (true dependence).  So my guess, 
your scheduler did not call sched_analyze.

Vlad

>
> If I modify TARGET_SCHED_ADJUST_COST to return 1 when an 
> anti-dependency is encountered, this results in the two instructions 
> being scheduled in different cycles (and hence, different VLIW 
> packets). For a VLIW machine however, it is legal for anti-dependent 
> instructions to be scheduled in the same cycle, so I can't use this 
> method to permanently fix the problem.
>