Оптимизация алгоритма на С, вопрос к знатокам компиляторов Опции

[singlskv]

Есть два варианта функции вычисления CRC:

Код

unsigned char code[8]={0x01,0xd0,0x5e,0x3c,0x0d,0x00,0x00,0x84};

unsigned char crc8_1(unsigned char *buff,unsigned char num)
{
    unsigned char i=0,j,tmp,data,crc=0;
    for (i=0;i<num;i++) {
        data=*buff++;
        for (j=0;j<8;j++) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

unsigned char crc8_2(unsigned char *buff,unsigned char num)
{
    unsigned char i=num,j,tmp,data,crc=0;
    for (;i>0;i--) {
        data=*buff++;
        for (j=8;j>0;j--) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

int main(int argc, char* argv[])
{
    unsigned char crc_;
    crc_=crc8_1(code,7);
    crc_=crc8_2(code,7);
    return 0;
}

Как видно из рисунка, это собственно один и тот же алгоритм.
Но, при компиляции под WinAVR(gcc), при любом уровне оптимизации, второй
вариант работает на 10-15% быстрее.
Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

[vet]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
//    6     asm("nop");
??main_0:
        nop
//    7   }
        DEC    R16
        BRNE    ??main_0

//    8   for (i=8;i;i--) {
        LDI    R16, 8
//    9     asm("nop");
??main_1:
        nop
//   10   }
        DEC    R16
        BRNE    ??main_1

//   11 }
        RET

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

Во второй функции компилятор решил задачу по-другому, но накладные расходы на цикл одинаковы в обеих функциях.

Сообщение отредактировал vet - Aug 24 2006, 10:37

[singlskv]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
   ..............................................................

Вы попробуйте два вложенных цикла, как в моем примере,
да и еще что нибудь кроме nop вставте в середину.

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

Во второй функции компилятор решил задачу по-другому, но накладные расходы на цикл одинаковы в обеих функциях.

Просимулировал Ваш код в AVR Studio.
Итого: (для семи байт)
crc8_1 986 тактов
crc8_2 774 такта
разница слегка удивила, это уже 25%.

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

[Rst7]

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

Хорошо поможет

Код

__z unsigned char crc8_2(unsigned char *buff,unsigned char num)

А циклы ОЧЕНЬ желательно делать

Код

do{}while(--var);

это помогает почти всем компиляторам и процессорам, обычно архитектура процессора позволяет изготовить нечто такое:

Код

DEC var
JUMP_IF_NZ label