sysprog21 / shecc

A self-hosting and educational C optimizing compiler
BSD 2-Clause "Simplified" License
1.11k stars 118 forks source link

Enhance the implementation of division emulation in the Arm backend #135

Closed DrXiao closed 3 months ago

DrXiao commented 3 months ago

Currently, the division emulation in the Arm backend has two potential issues to be resolved:

  1. Enhance code reusability: There are only 2 instructions different for div/mod emulation, and it can be refined to reuse the same code.
        /* Obtain absolute values of dividend and divisor */
        emit(__srl_amt(__AL, 0, arith_rs, __r8, rn, 31));
        emit(__add_r(__AL, rn, rn, __r8));
        emit(__eor_r(__AL, rn, rn, __r8));
        emit(__srl_amt(__AL, 0, arith_rs, __r9, rm, 31));
        emit(__add_r(__AL, rm, rm, __r9));
        emit(__eor_r(__AL, rm, rm, __r9));
    -   emit(__eor_r(__AL, __r10, __r8, __r9));
    +   emit(__mov_r(__AL, __r10, __r8));
        /* ... */
    -   emit(__mov_r(__AL, rd, __r9));
    -   /* Handle the correct sign for quotient */
    +   emit(__mov_r(__AL, rd, rn));
    +   /* Handle the correct sign for remainder */
        emit(__cmp_i(__AL, __r10, 0));
        emit(__rsb_i(__NE, rd, 0, rd));
  2. There has another potential issue for the current implementation: the dividend and divisor will lose after the emulation.

    If observing the implementation, rn and rm, which storing the dividend and divisor, will be shifted to complete the emulation, and the original value will lost at the end. But, for example, an executable compiled by shecc may has the following instruction sequence:

    • with +m option (use hardware div/mod instruction)
      .....
      .....
      div r2, r0, r1 
      ldr r3, r0           ; Load a word by r0 (the dividend).
      .....
    • without +m option (use div/mod emulation)

    .... asr r8, r0, #31 add r8, r8, r0 eor r8, r8, r0 ..... ..... cmp sl #0 rsbne r2, r2, #0 ldr r3, r0 ; Load a word by r0 (the dividend). ...... ; But r0 becomes no meaning because the emulation. ......

    
    After a division, the subsequent insturction(s) may use the register storing the dividend (or divisor) to perform the operation. With hardware instruction support, it will have no any problem. However, it may be failed for the subsequent instruction(s) because `rn` and `rm` become no meaning after the emulation.
    
    Therefore, the implementation should be improved to restore the dividend and divisor after the emulation.