Re: K6 and decoding bottleneck

[Jan Hubicka <hubicka at atrey dot karlin dot mff dot cuni dot cz>]

> 
> Intel recommends scheduling for the instruction decoder on the PPro /
> Pentium II in addition to scheduling for the execution units.  The i386
> scheduling changes I played in January attempted to do this and it did
> seem to help.
> 

> 
> I suggest to add one or more function units for the decoder, and add
> appropriate usages of this unit / these units.  If there is a common
> minimum latency between decoding and execution, you can just ignore this
> common latency.  It only makes a difference when the pipelines need to
> be refilled, i.e. when taking mispredicted branches, and the scheduler
> doesn't take these into account anyways.
Well, this is actually not true for K6 where on-chip scheduler can get
empty very easily in the middle of large basic block too.

Defining of function units for decoder was one of the first
thinks I've tried. I think this sollution has two main drawbacks:
1) define_funtion_unit is generally not very good for defining
rules like "this type of instructions can go to both decoders,
and this type can be decoded only by first and second is blocked".
There is no way to block second copy of decoder unit or specify
that given insn should be executed in one of this units.
(This should be solved in future IMO, because many architectures
 have this behaviour)

In PentiumPro patches you define all times multipled by three
and decoding is approximaed in following way:

! 
! (define_function_unit "decoder" 1 0
!  (and (eq_attr "uop" "complex") (eq_attr "cpu" "pentiumpro"))
!  3 3)
! 
! (define_function_unit "decoder" 1 0
!  (and (eq_attr "uop" "multiple") (eq_attr "cpu" "pentiumpro"))
!  3 3 [(eq_attr "uop" "!single")])
! 
! (define_function_unit "decoder" 1 0
!  (and (eq_attr "uop" "single") (eq_attr "cpu" "pentiumpro"))
!  3 0)
 
I've also tried this solution, it helps, but also has some problems.
It forces scheduler to put "single" insns together.
But I think it stress it bit too much, because it don't know
that after group of three "single" insns it is OK to use 
"complex".

This should be solved by extending define_function_unit syntax
to let define rules saying, that given insn executes eigther in
one or other unit. I would like to implement this in future, because
I've seed similar behaviour at many CPUs (Pentium, PentiumPro, K6, M-II
and UltraSparc)

2) Even if this problem is solved, scheduler will not
be interested in grouping insns using single unit (lets say fp),
because it will think that it is not neccesary, since fp unit can't
accept multiple insns at given cycle.

This idea should be extended. Scheduler really ought to know the fact,
that decoding is independent at execution. Imagine simple basic block
with one long decodable instruction and multiple simple instructions.
Scheduler should be clever and schedule multiple of simple instrucitons
first to fill on-chip scheduler. Then while decoding of the long instruction,
other units will be busy by executing insns that accumulated in the scheduler.

This technique seems to be very usefull on K6. I am able to get large
speedups by hand-scheduling in this way, so I've tried to implement this.
Maybe PentiumPro isn't so good target for such optimization, because it's
instruction type is determinted mainly by number of micro-insns instruction
generate. On K6 some instructions (like multiply) generates single Risc86
instruction, but they are vector decoded so they needs two cycles to decode
(time usually required for four simple instructions). And thats big problem.
But I believe such optimization should have some good effect for PentiumPro
so I will try to make my code more generic.

I am not sure, if my implementation is right way to go (if someone have
idea how to describe this better using define_function_units or by some
other better way, please stop me now!)

My implementation currently use k6decode attribute:

; K6 decoding parameters. Instruction should be short, long or vector.
; Decoder should decode two short instructions per cycle, so we should try
; to pair them. Shortfirst type is used for insns that behaves as short,
; but must be first in the pair.

; Decoding seems to be serious bottleneck for AMD CPUs so
; pairing should help a lot.

(define_attr "k6decode"
  "shortfirst,short,long,vector"
  (cond [(and (eq_attr "type" "mov,extend")
              (and (eq_attr "opcode" "mov")
	           (and (match_operand:QI 0 "memory_operand" "")
	                (match_operand:QI 1 "immediate_operand" ""))))
	 (const_string "long")

         (and (eq_attr "type" "fpload")
	      (match_operand:XF 0 "memory_operand" ""))
	 (const_string "vector")

         (eq_attr "type" "fpload,fpstore,fld,fpop,fpfast,fpdiv,fpmul,fsqrt,ftrigon")
	 (const_string "shortfirst")

         (eq_attr "type" "lea,mov,extend,compare")
	 (if_then_else (eq_attr "prefix" "true")
		       (const_string "long")
		       (const_string "short"))

         (and (eq_attr "type" "test")
	      (and (match_operand:QI 0 "memory_operand" "")
	           (match_operand:QI 1 "register_operand" "")))
	 (const_string "vector")

         (and (eq_attr "type" "test")
	      (ior (match_operand:QI 0 "immediate_operand" "")
	           (match_operand:QI 1 "immediate_operand" "")))
	 (const_string "long")

	 (and (eq_attr "type" "shift")
	      (eq_attr "memory" "none"))
	 (if_then_else (eq_attr "prefix" "true")
		       (const_string "long")
		       (const_string "short"))

	 (and (eq_attr "type" "alu,pop,push,test")
	      (eq_attr "memory" "load,store,none"))
	 (if_then_else (eq_attr "prefix" "true")
		       (const_string "long")
		       (const_string "short"))

	 (and (eq_attr "type" "alu,pop,push")
	      (eq_attr "memory" "both"))
	 (const_string "long")]
	(const_string "vector")))
(pentiumPro seems to have exactly same system, except the lack of vector
 decoded instrucitons and that short decodable should be decoded three
 instead of two at a time, so this should not be big problem to modify
 for PPro)


I've modified ADJUST_PRIORITY macro to increase priority of simple
instructions and added MD_SCHED macroe. MD_SCHED reorder counts number
of cycles required to decode given code. When called for gived group,
it takes time (cpu_clocks - decode_clocks). Counts number of vector,
long and short decodable isntructions in given category and then decides
what kind of instructions it will schedule (it preffers vector decodable,
long decodable and rest is filled by short decodable). Algorithm is exactly
following:


  /* Avoid massive reordering of vector decode insns. */
  if (!tmplastpair && tmpdecodecycles > clocks - 2 && get_attr_k6decode (ready[this_insn]) == K6DECODE_VECTOR && clocks > 3)
    return 0;

  if (sched_verbose)
    fprintf (dump, ";;\tK6 Last Pair: %i Time available: %i ", lastpair, clocks - tmpdecodecycles);

  nscheduled = 0;
  getcount[0] = getcount[1] = getcount[2] = getcount[3] = 0;

  if (tmplastpair && count[K6DECODE_SHORT] > getcount[K6DECODE_SHORT])
    getcount[K6DECODE_SHORT]++, tmplastpair = 0, nscheduled++;

  while (tmpdecodecycles + 1 < clocks
	 && count[K6DECODE_VECTOR] > getcount[K6DECODE_VECTOR])
    tmplastpair = 0, getcount[K6DECODE_VECTOR]++, nscheduled++, tmpdecodecycles += 2;

  while (tmpdecodecycles + (nscheduled || clocks > 3 ? 0 : 1) < clocks
	 && count[K6DECODE_LONG] > getcount[K6DECODE_LONG])
    tmplastpair = 0, getcount[K6DECODE_LONG]++, nscheduled++, tmpdecodecycles++;


Then it keeps the order of insns just yanks out the instructions that
are not in selected counts, and pairs the short decodable insn. It also
keep information if previous group overed by inpaired short decodable
insn and use it.

This implementation seems to bring quite consistent speedup at K6.
I would love to try it at PPro too, but I don't have any available,
so I would be really excited, if someone tries this for me
(I modify my implementation for PPro this weekend).

I would also welcome all ideas and comments :)

Honza