[LLVMdev] LLVM x86 Code Generator discards Instruction-level Parallelism

[Evan Cheng]

The default x86 scheduler schedules to reduce register pressure since that's the primary concern for most code. list-ilp scheduler is designed to address the kind of issue you described but it's not quite done yet. Please file a bug and attach your microbenchmark.

Evan

On Nov 3, 2010, at 11:34 AM, Andrew R Kerr wrote:

> Dear LLVMdev,
> 
> I've noticed an unusual behavior of the LLVM x86 code generator (with default options)
> that results in nearly a 4x slow-down in floating-point throughput for my microbenchmark.
> 
> I've written a compute-intensive microbenchmark to approach theoretical peak
> throughput of the target processor by issuing a large number of independent
> floating-point multiplies. The distance between dependent instructions is at
> least four instructions to match the latency of the floating-point functional
> unit in my Intel Core2 Quad (Q9550 at 2.83 GHz).
> 
> The microbenchmark itself replicates the following block 512 times:
> 
> .
> .
> {
>  p1 = p1 * a;
>  p2 = p2 * b;
>  p3 = p3 * c;
>  p4 = p4 * d;
> }
> .
> .
> 
> Compiling with NVCC, Ocelot, and LLVM, I can confirm the interleaved instruction
> schedule with a four-instruction reuse distance. An excerpt follows:
> 
>  .
>  .
>  %r1500 = fmul float %r1496, %r24  ; compute %1500
>  %r1501 = fmul float %r1497, %r23
>  %r1502 = fmul float %r1498, %r22
>  %r1503 = fmul float %r1499, %r21
> 
>  %r1504 = fmul float %r1500, %r24  ; first use of %1500
>  %r1505 = fmul float %r1501, %r23
>  %r1506 = fmul float %r1502, %r22
>  %r1507 = fmul float %r1503, %r21
> 
>  %r1508 = fmul float %r1504, %r24  ; first use of %1504
>  .
>  .
> 
> The JIT compiler, however, seems to break the interleaving of independent instructions
> and issues a long sequence of instructions with back-to-back dependencies. It is as if
> all p1 = .. expressions are collected at once followed by all p2 = .. expressions and so
> forth.
> 
> p1 = p1 * a
> p1 = p1 * a
> .
> .
> 
> p2 = p2 * b
> p2 = p2 * b
> .
> .
> 
> p3 = p3 * c
> p3 = p3 * c
> .
> .
> 
> An actual excerpt of the generated x86 assembly follows:
> 
>  mulss        %xmm8, %xmm10
>  mulss        %xmm8, %xmm10
>  .
>  . repeated 512 times
>  .
> 
>  mulss        %xmm7, %xmm9
>  mulss        %xmm7, %xmm9
>  .
>  . repeated 512 times
>  .
> 
>  mulss        %xmm6, %xmm3
>  mulss        %xmm6, %xmm3
>  .
>  . repeated 512 times
>  .
> 
> Since p1, p2, p3, and p4 are all independent, this reordering is correct. This would have
> the possible advantage of reducing live ranges of values. However, in this microbenchmark,
> the number of live values is eight single-precision floats - well within SSE's sixteen
> architectural registers.
> 
> Moreover, the pipeline latency is four cycles meaning back-to-back instructions with true
> dependencies cannot issue immediately. The benchmark was intentionally written to avoid this
> hazard but LLVM's code generator seems to ignore that when it schedules instructions.
> 
> When I run this benchmark on my 2.83 GHz CPU, I observe the following performance results:
> 
>  1 threads       0.648891 GFLOP/s
>  2 threads       1.489049 GFLOP/s
>  3 threads       2.209838 GFLOP/s
>  4 threads       2.940443 GFLOP/s
> 
> When I rewrite the generated assembly by hand to exhibit the same interleaving as in the
> LLVM IR form
> 
>  .
>  .
>  mulss        %xmm8, %xmm10
>  mulss        %xmm7, %xmm9
>  mulss        %xmm6, %xmm3
>  mulss        %xmm5, %xmm11
> 
>  mulss        %xmm8, %xmm10
>  mulss        %xmm7, %xmm9
>  mulss        %xmm6, %xmm3
>  mulss        %xmm5, %xmm11
> 
>  mulss        %xmm8, %xmm10
>  mulss        %xmm7, %xmm9
>  .
>  .
> 
> observed performance increases by nearly a factor of four:
> 
>  1 threads       2.067118 GFLOP/s
>  2 threads       5.569419 GFLOP/s
>  3 threads       8.285519 GFLOP/s
>  4 threads       10.81742 GFLOP/s
> 
> I show similar results with packed single-precision floating point SIMD instructions. The
> LLVM-generated machine code is nearly 4x slower than the interleaved schedule 'suggested' by
> the LLVM IR input.
> 
>  Vectorized - No instruction interleaving - back-to-back dependencies
>    (issued by LLVM code generator)
> 
>  1 threads        1.540621 GFLOP/s
>  2 threads        5.900833 GFLOP/s
>  3 threads        8.755953 GFLOP/s
>  4 threads        11.257122 GFLOP/s
> 
>  Vectorized - Interleaved - stride-4 reuse distance
>    (hand-modified to interleave instructions)
> 
>  1 threads       3.157255 GFLOP/s
>  2 threads       22.104369 GFLOP/s
>  3 threads       32.300111 GFLOP/s
>  4 threads       39.112162 GFLOP/s
> 
> It is worth noting that 39.1 GFLOP/s is approaching the theoretical limits of the processor
> (stated to be 45.25 GFLOP/s single-precision).
> 
> I've used the llc utility to test various pre-register-allocation instruction schedulers
> with the following results:
> 
>  -pre-RA-sched
>    =default         - discards ILP
>    =list-burr       - discards ILP
>    =list-tdrr       - crashes during code generation
> 
>    =source          - preserves interleaved instruction ordering and ILP
> 
>    =list-hybrid     - discards ILP
>    =list-ilp        - discards ILP
>    =list-td         - crashes during code generation
>    =fast            - discards ILP
> 
> Can you comment?
> 
> -- 
> Andrew Kerr
> arkerr at gatech.edu
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev