Почему ARM gcc вызывает __udivsi3 при делении на константу?

В Cortex-M0 отсутствуют инструкции для выполнения 32x32- ›64-битного умножения. Поскольку num является беззнаковой 16-битной величиной, умножение его на 9363 и сдвиг вправо на 16 даст правильный результат во всех случаях, но - вероятно, поскольку uint16_t будет повышен до int перед умножением, gcc не включает такие оптимизации.

Из того, что я наблюдал, gcc, как правило, плохо справляется с оптимизацией для Cortex-M0, не используя некоторые простые оптимизации, которые были бы подходящими для этой платформы, но иногда использует оптимизацию, которая не подходит. Учитывая что-то вроде

void test1(uint8_t *p)
{
    for (int i=0; i<32; i++)
        p[i] = (p[i]*9363) >> 16; // Divide by 7
}

gcc генерирует нормальный код для Cortex-M0 в -O2, но если бы умножение было заменено добавлением, компилятор сгенерировал бы код, который перезагружает константу 9363 на каждой итерации цикла. При использовании сложения, даже если код был изменен на:

void test2(uint16_t *p)
{
    register unsigned u9363 = 9363;
    for (int i=0; i<32; i++)
        p[i] = (p[i]+u9363) >> 16;
}

gcc по-прежнему будет загружать константу в цикл. Иногда оптимизация gcc также может иметь неожиданные поведенческие последствия. Например, можно было ожидать, что на такой платформе, как Cortex-M0, будет вызвано что-то вроде:

unsigned short test(register unsigned short *p)
{
    register unsigned short temp = *p;
    return temp - (temp >> 15);
}    

в то время как прерывание изменяет содержимое *p, может привести к поведению, согласованному со старым или новым значением. Стандарт не требует такой обработки, но большинство реализаций, предназначенных для задач встроенного программирования, будут предлагать более строгие гарантии, чем то, что требует Стандарт. Если старое или новое значение будут одинаково приемлемыми, разрешение компилятору использовать то, что более удобно, может позволить получить более эффективный код, чем использование volatile. Однако, как это случилось, оптимизированный код из gcc заменит два использования temp отдельными загрузками *p.

Если вы используете gcc с Cortex-M0 и вас не беспокоит производительность или возможность удивительного поведения, возьмите за привычку проверять вывод компилятора. Для некоторых видов циклов, возможно, стоит подумать о тестировании -O0. Если в коде надлежащим образом используется ключевое слово register, его производительность иногда может превзойти производительность идентичного кода, обработанного с помощью -O2.

Расширение ответа суперкота.

Накормите это:

unsigned short fun ( unsigned short x )
{
    return(x/7);
}

к чему-то с большим умножением:

00000000 <fun>:
   0:   e59f1010    ldr r1, [pc, #16]   ; 18 <fun+0x18>
   4:   e0832190    umull   r2, r3, r0, r1
   8:   e0400003    sub r0, r0, r3
   c:   e08300a0    add r0, r3, r0, lsr #1
  10:   e1a00120    lsr r0, r0, #2
  14:   e12fff1e    bx  lr
  18:   24924925    .word   0x24924925
  

1/7 в двоичном формате (длинное деление):

     0.001001001001001
 111)1.000000
       111 
      ==== 
         1000
          111
          ===
            1
            
        
0.001001001001001001001001001001
0.0010 0100 1001 0010 0100 1001 001001
0x2492492492...
0x24924925>>32  (rounded up)

Чтобы это работало, вам нужен 64-битный результат, вы берете верхнюю половину и вносите некоторые изменения, например:

7 * 0x24924925 = 0x100000003

и вы берете верхние 32 бита (не совсем так просто, но для этого значения вы можете видеть, что он работает).

Умножение варианта all thumbs составляет 32 бита = 32 бита * 32 бита, поэтому результат будет 0x00000003, и это не сработает.

Итак, 0x24924, который мы можем сделать 0x2493, как это сделал supercat, или 0x2492.

Теперь мы можем использовать умножение 32x32 = 32 бит:

0x2492 * 7 = 0x0FFFE
0x2493 * 7 = 0x10005

Давайте пробежимся с тем, что побольше:

0x100000000/0x2493 = a number greater than 65536. so that is fine.

но:

0x3335 * 0x2493 = 0x0750DB6F
0x3336 * 0x2493 = 0x07510002
0x3335 / 7 = 0x750
0x3336 / 7 = 0x750

Так что вы можете продвинуться только с таким подходом.

Если следовать модели кода руки:

for(ra=0;ra<0x10000;ra++)
{
    rb=0x2493*ra;
    rd=rb>>16;
    rb=ra-rd;
    rb=rd+(rb>>1);
    rb>>=2;
    rc=ra/7;
    printf("0x%X 0x%X 0x%X \n",ra,rb,rc);
    if(rb!=rc) break;
}

Затем он работает от 0x0000 до 0xFFFF, поэтому вы можете написать asm для этого (обратите внимание, что это должно быть 0x2493, а не 0x2492).

Если вы знаете, что операнд не превышает определенного значения, вы можете использовать больше битов 1/7 для умножения.

В любом случае, когда компилятор не выполняет эту оптимизацию за вас, у вас все еще есть шанс.

Теперь, когда я думаю об этом, я сталкивался с этим раньше, и теперь это имеет смысл. Но у меня была полноразмерная рука, и я вызвал подпрограмму, которую я скомпилировал в режиме руки (другой код был в режиме большого пальца), и имел оператор switch в основном, если знаменатель = 1, то результат = x / 1; если знаменатель = 2, то результат = x / 2 и так далее. А затем он отказался от функции gcclib и сгенерировал умножение 1 / x. (У меня было 3 или 4 разных константы для деления):

unsigned short udiv7 ( unsigned short x )
{
    unsigned int r0;
    unsigned int r3;
    
    r0=x;
    r3=0x2493*r0;
    r3>>=16;
    r0=r0-r3;
    r0=r3+(r0>>1);
    r0>>=2;
    return(r0);
}

Предполагая, что я не сделал ошибок:

00000000 <udiv7>:
   0:   4b04        ldr r3, [pc, #16]   ; (14 <udiv7+0x14>)
   2:   4343        muls    r3, r0
   4:   0c1b        lsrs    r3, r3, #16
   6:   1ac0        subs    r0, r0, r3
   8:   0840        lsrs    r0, r0, #1
   a:   18c0        adds    r0, r0, r3
   c:   0883        lsrs    r3, r0, #2
   e:   b298        uxth    r0, r3
  10:   4770        bx  lr
  12:   46c0        nop         ; (mov r8, r8)
  14:   00002493    .word   0x00002493

Это должно быть быстрее, чем обычная процедура библиотеки деления.

Редактировать

Думаю, я вижу, что Supercat сделал с работающим решением:

((i*37449 + 16384u) >> 18)

У нас есть это как 1/7 дробь:

0.001001001001001001001001001001

но мы можем сделать только умножение 32 = 32x32 бит. Начальные нули дают нам некоторую передышку, которой мы могли бы воспользоваться. Поэтому вместо 0x2492 / 0x2493 мы можем попробовать:

1001001001001001
0x9249
0x9249*0xFFFF = 0x92486db7

И пока не переполнится:

    rb=((ra*0x9249) >> 18);

сам по себе он не работает при 7 * 0x9249 = 0x3FFFF, 0x3FFFF ›› 18 равно нулю, а не 1.

Так что, может быть

    rb=((ra*0x924A) >> 18);

что не удается:

    0xAAAD 0x1862 0x1861 

Так что насчет:

    rb=((ra*0x9249 + 0x8000) >> 18);

и это работает.

А что насчет суперкотов?

    rb=((ra*0x9249 + 0x4000) >> 18);

и это работает чисто для всех значений от 0x0000 до 0xFFFF:

    rb=((ra*0x9249 + 0x2000) >> 18);

и здесь это не работает:

0xE007 0x2000 0x2001 

Итак, есть несколько эффективных решений.

unsigned short udiv7 ( unsigned short x )
{
    unsigned int ret;
    ret=x;
    ret=((ret*0x9249 + 0x4000) >> 18);
    return(ret);
}
00000000 <udiv7>:
   0:   4b03        ldr r3, [pc, #12]   ; (10 <udiv7+0x10>)
   2:   4358        muls    r0, r3
   4:   2380        movs    r3, #128    ; 0x80
   6:   01db        lsls    r3, r3, #7
   8:   469c        mov ip, r3
   a:   4460        add r0, ip
   c:   0c80        lsrs    r0, r0, #18
   e:   4770        bx  lr
  10:   00009249    .word   0x00009249

Редактировать

Что касается вопроса "почему", это не вопрос переполнения стека; если вы хотите узнать, почему gcc этого не делает, спросите авторов этого кода. Все, что мы можем сделать, это предположить здесь, и предположение состоит в том, что они, возможно, решили не делать этого из-за количества инструкций, или они, возможно, решили не делать этого, потому что у них есть алгоритм, который заявляет, что это не 64 = 32x32 битное умножение, тогда выполните не беспокоить.

Опять же, вопрос «почему» не является вопросом переполнения стека, поэтому, возможно, нам следует просто закрыть этот вопрос и удалить все ответы.

Я обнаружил, что это было невероятно познавательным (если вы знаете / понимаете, о чем говорилось).

Другой ПОЧЕМУ? вопрос в том, почему gcc сделал это так, как они это сделали, когда они могли сделать это так же, как supercat или я?

Компилятор может переупорядочивать целочисленные выражения только в том случае, если он знает, что результат будет правильным для любого ввода, разрешенного языком.

Поскольку 7 является простым числом с 2, невозможно разделить любой ввод на семь с помощью умножения и сдвига.

Если вы знаете, что это возможно для ввода, который вы собираетесь предоставить, вам придется сделать это самостоятельно, используя операторы умножения и сдвига.

В зависимости от размера ввода вам нужно будет выбрать, на сколько сдвинуть, чтобы вывод был правильным (или, по крайней мере, достаточно хорошим для вашего приложения) и чтобы промежуточное не переполнялось. Компилятор не имеет возможности узнать, что достаточно точно для вашего приложения или каков будет ваш максимальный ввод. Если он позволяет вводить до максимального значения типа, то каждое умножение будет переполняться.

В общем, GCC будет выполнять деление с использованием сдвига только в том случае, если делитель не является взаимно простым с 2, то есть если он является степенью двойки.