Сегодня я бы хотел поговорить о недооценённой особенности архитектуры набора команд AArch64. На неё часто не обращают внимания, но её активно используют компиляторы. Это хорошая короткая история о том, как Arm стал лучше и «ещё более CISC» с точки зрения условных пересылок. История csinc заслуживает подобной статьи.

Вероятно, вы слышали про cmov

Когда в литературе говорится об условных пересылках, то обычно упоминается команда x86 cmov. Это удобная функция, позволяющая повысить производительность при низкоуровневой оптимизации. Допустим, при объединении двух массивов можно сравнивать числа и выбирать одно из них в зависимости от значения команд сравнения (а точнее флагов):

while ((pos1 < size1) & (pos2 < size2)) {
    v1 = input1[pos1];
    v2 = input2[pos2];
    output_buffer[pos++] = (v1 <= v2) ? v1 : v2;
    pos1 = (v1 <= v2) ? pos1 + 1 : pos1;
    pos2 = (v1 >= v2) ? pos2 + 1 : pos2;
}

cmpl %r14d, %ebp   # определяем, какое из них меньше, задаём CF
setbe %bl          # присваиваем CF  %bl, если оно меньше
cmovbl %ebp, %r14d # копируем ebp в r14d, если флаг CF установлен

Если ветвления непредсказуемы, например в случае объединения двух массивов случайных целых чисел, команды условной пересылки обеспечивают существенное ускорение по сравнению с версией с ветвлением, потому что избавляют от траты времени, вызванной ошибочным прогнозированием ветвления. Об этом много писал Дэниел Лемайр. С этим связано множество разработок, в том числе Agner Fog, cmov vs branch profile guided optimizations. Команды условной пересылки — очень важная область современного ПО и, скорее всего, во всех запускаемых вами программах они есть.

А как насчёт Arm?

AArch64 не стал исключением в этой сфере, у него тоже есть команды условной пересылки. Ближайшим аналогом условной пересылки можно считать csel, что расшифровывается как conditional select. В нём почти отсутствуют отличия от cmov, за исключением того, что нужно напрямую указывать, какое условие необходимо проверять и регистр назначения (при cmov регистр назначения не меняется, если условие не соблюдено). На мой взгляд, эта запись чуть более понятна:

csel Xd, Xn, Xm, cond

Когда я изучал структуру этой команды в руководстве по оптимизации, я заметил семейство команд, включающее в себя различные её вариации:

Меня заинтриговало существование других разновидностей, потому что они предоставляют компиляторам и разработчикам больше возможностей для написания ПО. Например, csinc Xd, Xa, Xb, cond (conditional select increase) означает, что если условие выполняется, то Xd = Xb + 1, в противном случаеXd = Xa. Например, в случае объединения двух массивов строка:

pos1 = (v1 <= v2) ? pos1 + 1 : pos1;

может скомпилироваться в следующее:

csinc X0, X0, X0, #condition_of_v1_less_equal_v2

где X0 — это регистр для pos1.

csneg, csinv схожи по действию и обозначают условное вычитание и инверсию.

Например, clang распознаёт эту последовательность, а GCC — нет.

Где это ещё может пригодится?

Как ни странно, при сжатии! Возможно, вы слышали о Snappy — старой библиотеке сжатия Google, которую намного превзошла LZ4. В случае x86 разница в скорости (даже для самой новой версии clang) достаточно велика. Например, на моём сервере Intel Xeon (2,00 ГГц) скорость распаковки для LZ4 составляет 2721 МБ/с, а для Snappy — 2172 МБ/с, то есть разрыв между ними около 25%.

Чтобы Snappy достигла такого уровня распаковки, разработчики должны писать код так, чтобы обеспечить генерацию кода cmov:

SNAPPY_ATTRIBUTE_ALWAYS_INLINE
inline size_t AdvanceToNextTagX86Optimized(const uint8_t** ip_p, size_t* tag) {
  const uint8_t*& ip = *ip_p;
  // Эта часть очень важна для производительности цикла распаковки.
  // Задержки итерации фундаментально ограничены
  // следующей цепочкой данных в ip.
  // ip -> c = Load(ip) -> ip1 = ip + 1 + (c & 3) -> ip = ip1 or ip2
  //                       ip2 = ip + 2 + (c >> 2)
  // Это составляет 8 тактов.
  // 5 (load) + 1 (c & 3) + 1 (lea ip1, [ip + (c & 3) + 1]) + 1 (cmov)
  size_t literal_len = *tag >> 2;
  size_t tag_type = *tag;
  bool is_literal;
#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
  // TODO clang упускает, что (c & 3) корректно задаёт
  // флаг нуля.
  asm("and $3, %k[tag_type]\n\t"
      : [tag_type] "+r"(tag_type), "=@ccz"(is_literal)
      :: "cc");
#else
  tag_type &= 3;
  is_literal = (tag_type == 0);
#endif
  // TODO
  // Это очень тонкий код. Если мы сначала загружаем значения, а затем выполняем cmov, то 
  // задержка будет меньше, чем при cmov ip с последующей загрузкой. Однако clang переместит
  // загрузки в фазе оптимизации; volatile предотвращает это преобразование.
  // Обратите внимание, что у нас достаточно мусорных (slop) байтов (64), чтобы загрузки всегда были валидными.
  size_t tag_literal =
      static_cast<const volatile uint8_t*>(ip)[1 + literal_len];
  size_t tag_copy = static_cast<const volatile uint8_t*>(ip)[tag_type];
  *tag = is_literal ? tag_literal : tag_copy;
  const uint8_t* ip_copy = ip + 1 + tag_type;
  const uint8_t* ip_literal = ip + 2 + literal_len;
  ip = is_literal ? ip_literal : ip_copy;
#if defined(__GNUC__) && defined(__x86_64__)
  // TODO Clang "оптимизирует" дополнение нулями (совершенно незатратная
  // операция); это означает, что после cmov tag он создаёт ещё один movzb
  // tag, byte(tag). Это очень важно, потому что команды находятся в основной цепочке. Этот фиктивный
  // asm убеждает clang выполнять дополнение нулями при load (это выполняется автоматически),
  // устраняя затратную movzb.
  asm("" ::"r"(tag_copy));
#endif
  return tag_type;
}

В Arm команда csinc используется из-за природы формата:

Если объяснять вкратце, последние два бита байта, открывающие блок, имеют команду о том, что делать и какую память копировать: 00 копирует данные len-1. При тщательной оптимизации условных пересылок мы можем сэкономить на прибавлении этого +1 с помощью csinc:

На инстансах Google T2A я получил скорость распаковки 3048 МБ/с для LZ4 и 2839 МБ/с для Snappy, то есть разницу всего в 7%. Если бы я включил LZ4_FAST_DEC_LOOP, то получил бы 3233 МБ/с , что всё равно составляет разницу в 13% gap, но не в 25%, как при исполнении x86.

Итак, команды условного выбора Arm заслуживают внимания:

1. csel, csinc и их разновидности имеют ту же задержку и производительность, то есть они столь же малозатратны, как обычная  csel почти на всех современных процессорах Arm, и в том числе на Apple M1, M2.

2. Компиляторы узнают их (по моему опыту, clang справляется с этим лучше, чем GCC, см. выше), при этом не нужно делать ничего особенного, просто следует учитывать, что некоторые форматы работают на Arm лучше, чем на x86.

Подведём итог: вопреки мнению об архитектурах набора команд x86 и Arm при обсуждении CISC и RISC, Arm имеет удивительные возможности условных команд, которые более гибки, чем обсуждаемые традиционно.