Conditional instructions in the ARM1 processor, reverse engineered

By carefully examining the layout of the ARM1 processor, it can be reverse engineered. This article describes the interesting circuit used for conditional instructions: this circuit is marked in red on the die photo below. Unlike most processors, the ARM executes every instruction conditionally. Each instruction specifies a condition and is only executed if the condition is satisfied. For every instruction, the condition circuit reads the condition from the instruction register (blue), evaluates the condition flags (purple), and informs the control logic (yellow) if the instruction should be executed or skipped.

The ARM1 processor chip showing the condition evaluation circuit (red) and the main components it interacts with. Original photo courtesy of Computer History Museum.

The ARM1 processor chip showing the condition evaluation circuit (red) and the main components it interacts with. Original photo courtesy of Computer History Museum.

Why care about the ARM1 chip? It is the highly-influential ancestor of the extremely popular ARM processor. The ARM1 processor got off to a slow start in 1985 but now ARM processors are now sold by the tens of billions; your smart phone probably runs on ARM. This article is part of my series on reverse engineering the ARM1; start with my first article for an overview of the chip.

What are conditional instructions?

A key part of any computer is the ability of a program to change what it is doing based on various conditions. Most computers provide conditional branch instructions, which cause execution to jump to a different part of the program based on various condition flags. For example, consider the code if (x == 0) { do_something }. Compiled to assembly code, this first tests the value of variable x and sets the Zero flag if x is 0. Next, a conditional branch instruction jump over the do_something code if the Zero flag is not set.

The ARM processor takes conditionals much further than other processors: every instruction becomes a conditional instruction. Every instruction includes one of 16 conditions and the instruction is only executed if the condition is true; otherwise the instruction is skipped. (This is also known as predication.) The motivation is to avoid inefficient jumping around in the code.

The ARM manual excerpt below shows how four bits in each 32-bit instruction specify one of 16 conditions. Most of the conditions are straightforward, checking if values are equal, negative, higher, and so forth. Most instructions will use the «always» condition, which simply means the instruction always executes. The opposite «never» condition is not highly useful — an instruction with that condition never executes — but it can be used for a NOP, patching code, or adjusting timing of an instruction sequence.

Every instruction in the ARM processor has one of 16 conditions specified. The instruction is executed only if the condition is satisfied.

Every instruction in the ARM processor has one of 16 conditions specified. The instruction is executed only if the condition is satisfied.

Studying the different conditions reveals much of how the condition circuit works. It is based on four condition flags. The zero (Z) flag is set if a value is zero. The negative (N) flag is set if a value is negative. The carry (C) flag is set if there is a carry or borrow from addition or subtraction. The overflow (V) flag is set if there is an overflow during signed arithmetic (details).

The top three bits of the instruction select one of eight conditions, as highlighted in yellow. The fourth bit selects the condition or its opposite (blue). If the fourth bit is 0, the condition must be true; if the fourth bit is 1, the condition must be false.

Implementation of the circuit

The implementation of the conditional logic circuit matches the above description. First, the eight conditions are generated from the four flags. One of the conditions is selected based on the three instruction bits. If the fourth instruction bit is set, the condition is flipped. The result is 1 if the condition is satisfied, and 0 if the condition is not satisfied. One unexpected part of the circuit is that an undefined instruction or and interrupt causes the condition to be cleared, preventing execution of the instruction. The resulting condition signal output is connected to a control part of the chip, where it causes the instruction to be executed or not, as desired.

The condition code evaluation circuit from the ARM1 processor.

The condition code evaluation circuit from the ARM1 processor.

The diagram above shows the condition code circuit of the chip as it appears in the simulator; this is a zoomed-in version of the red rectangle indicated on the die earlier. The chip consists of multiple layers, indicated by different colors. Transistors appear as red or blue regions. NMOS transistors are red; they turn on with a 1 input and can pull their output low. PMOS transistors (blue) are complementary; they turn on with a 0 input and can pull their output high. Physically above the transistors is the polysilicon wiring layer (green). When polysilicon crosses a transistor it forms the gate (yellow) that controls the transistor. Finally, two layers of metal wiring (gray) are above the polysilicon.

The circuit is arranged in columns. The first column of transistors forms the logic gates to generate the conditions from the flag values. The next column is the multiplexer, a circuit that takes the eight input conditions and selects one. The rightmost column contains 8 NAND gates that decode the three instruction bits into 8 control lines. Each line is fed into the multiplexer to select the corresponding condition. At the right is the wiring for the 3 instruction bits and their complements. A few miscellaneous gates are at the bottom of the multiplexer and decoder columns. These include inverters to complement the instruction bits.

The condition generation gates

The diagram below zooms in on the left third of the circuit above. This part of the circuit uses standard CMOS logic gates to computes the conditions from the flags. Each gate is built from NMOS (red) and PMOS (blue) transistors in a horizontal strip. Comparing the text description of conditions from the manual with the logic shows how the conditions are generated. For instance, the HI (unsigned higher) condition requires flags «C set and Z clear». The top three gates generate this condition. The GE (greater than or equal) condition is more complex, requiring flags «N set and V set, or N clear and V clear». The next two gates compute this value. (Due to the way CMOS gates are constructed, an OR-NAND gate is constructed as a single gate.) Likewise, the other conditions are generated. The AL (always) condition is simply a 1, and doesn’t require any circuitry. The conditions are fed into the multiplexer, which will be discussed below.

The output coming back from the multiplexer is the selected condition, labeled «cond» below. The NAND and OR-NAND gates flip the condition if instruction register bit 28 (ireg28) is set. This implements the eight opposite conditions. The result is labeled «ok», indicating the overall condition is satisfied. The final three gates block instruction execution for an interrupt or undefined instruction.

Gates in the ARM1 processor generate the various conditionals from the flag values.

Gates in the ARM1 processor generate the various conditionals from the flag values.

One thing I’d like to emphasize about the ARM1 is that its layout is very orderly and non-optimized. While it may appear chaotic, the gates are arranged by combining relatively fixed blocks («standard cells») and wiring them together. Each gate forms a strip and the gates are stacked together in columns. The polysilicon and metal layers connect the gates as necessary.

The layout of the ARM1 chip is a consequence of the VLSI Technology chip design software used to create it. The resulting layout is simple, but doesn’t use space very efficiently. Since the ARM1 uses very few transistors for its time, the designers weren’t worried about optimizing the layout. In contrast, earlier chips such as the Z-80 were hand-drawn, with each transistor and wire carefully shaped to use the minimum space possible. The diagram below shows a small part of the Z-80 processor layout, showing the extremely irregular but dense arrangement of the chip. The transistors are not arranged in rows as in the ARM1 above, but fit together to use all the available space.

A detail of the Z-80 processor layout, showing the complex hand-drawn layout. Each transistor and wire is carefully shaped to minimize the chip's size.

A detail of the Z-80 processor layout, showing the complex hand-drawn layout. Each transistor and wire is carefully shaped to minimize the chip’s size.

The multiplexer and decoders

Selecting the desired condition out of the eight possibilities is the job of a circuit called the multiplexer. The multiplexer takes 8 inputs (the conditions) and 8 control signals (based on the instruction) and selects the desired condition. To the right of the multiplexer, 8 NAND gates generate the 8 control signals by decoding the three instruction bits. Each gate simply looks at three bit values and outputs a 0 if the bits select that condition. For instance, if the first two bits are 0 and the third is 1, the gate for condition 1 outputs a 0, selecting that condition in the multiplexer. The animation below shows the circuit as the instruction bits cycle through the eight conditions. You can see the activated condition moving downwards through the circuit.

Animation of the multiplexer in the ARM1 condition code evaluation circuit.

Animation of the multiplexer in the ARM1 condition code evaluation circuit.

While a multiplexer can be built from standard logic gates, the ARM1 multiplexer is built from a different type of circuitry called transmission gates (which the ARM1 also uses in its bit counter). A multiplexer built from transmission gates is more compact and faster than one built from standard logic (NAND gates). One feature of CMOS is that by combining an NMOS transistor and a PMOS transistor in parallel, a transmission gate switch can be built. Feeding 1 into the NMOS gate and 0 into the PMOS gate turns on both transistors and they pass their input through. With the opposite gate values, both transistors turn off and the switch opens. The multiplexer is built from 8 of these CMOS switches. Each condition input feeds into one switch, and the switch outputs are connected together. One switch is turned on at a time, selecting the corresponding input as the output value.

The diagram below shows the schematic of the multiplexer as well as its physical layout on the chip. Only the first three segments of the eight are shown; the remainder are similar. Each input is connected to two transistors forming a CMOS switch. Because the NMOS and PMOS gates require opposite signals, the multiplexer has an inverter for each control signal. Each inverter also consists of two transistors, but wired differently from the switch.

Schematic of the multiplexer inside the ARM1 processor's condition code evaluation circuit.Diagram of the multiplexer inside the ARM1 processor's condition code evaluation circuit.

Schematic and diagram of the multiplexer inside the ARM1 processor’s condition code evaluation circuit.

Working together the decode circuit, inverters, and CMOS switches form the multiplexer that selects the desired condition from the eight choices. The logic described earlier allows this condition to be flipped, for a total of 16 possible conditions.

Conclusion

One unusual feature of the ARM instruction set is that every instruction has a condition associated with it and is only executed if the condition is true. The ARM1 chip is simple enough that the condition circuitry on the chip can be examined and understood at the transistor and gate level. Now that you’ve seen the internals of the condition logic, you can use the Visual ARM1 simulator to see the circuit in action. While the ARM1 may seem like a historical artifact of the 1980s, ARM processors power most smartphones, so there’s probably a similar circuit controlling your phone right now.

Реклама

SSE4 — CPU instruction set used in the Intel Core microarchitecture and AMD

SSE4 — набор команд микроархитектуры Intel Core

SSE4 состоит из 54 инструкций, 47 из них относят к SSE4.1 (они есть в процессорах Penryn). Полный набор команд (SSE4.1 и SSE4.2, то есть 47 + оставшиеся 7 команд) доступен в процессорах Intel с микроархитектурой Nehalem, которые были выпущены в середине ноября 2008 года и более поздних редакциях. Ни одна из SSE4 инструкций не работает с 64-х битными mmx регистрами (только со 128-ми битными xmm0-15).

Компилятор языка Си от Intel начиная с версии 10 генерирует инструкции SSE4 при задании опции -QxS. Компилятор Sun Studio от Sun Microsystems с версии 12 update 1 генерирует инструкции SSE4 с помощью опций -xarch=sse4_1 (SSE4.1) и -xarch=sse4_2 (SSE4.2). Компилятор GCC поддерживает SSE4.1 и SSE4.2 с версии 4.3, опции -msse4.1 и -msse4.2, или -msse4, включающая оба варианта.

Инструкции SSE4.1
Ускорение видео

  • MPSADBW xmm1, xmm2/m128, imm8 — (Multiple Packed Sums of Absolute Difference)
    • Input — { A0, A1,… A14 }, { B0, B1,… B15 }, Shiftmode
    • Output — { SAD0, SAD1, SAD2,… SAD7 }

Вычисление восьми сумм абсолютных значений разностей (SAD) смещённых 4-х байтных беззнаковых групп. Расположение операндов для 16-ти битных SAD определяется 3-мя битами непосредственного аргумента imm8.

s1 = imm8[2]*4
s2 = imm8[1:0]*4
SAD0 = |A(s1+0)-B(s2+0)| + |A(s1+1)-B(s2+1)| + |A(s1+2)-B(s2+2)| + |A(s1+3)-B(s2+3)|
SAD1 = |A(s1+1)-B(s2+0)| + |A(s1+2)-B(s2+1)| + |A(s1+3)-B(s2+2)| + |A(s1+4)-B(s2+3)|
SAD2 = |A(s1+2)-B(s2+0)| + |A(s1+3)-B(s2+1)| + |A(s1+4)-B(s2+2)| + |A(s1+5)-B(s2+3)|
...
SAD7 = |A(s1+7)-B(s2+0)| + |A(s1+8)-B(s2+1)| + |A(s1+9)-B(s2+2)| + |A(s1+10)-B(s2+3)|
  • PHMINPOSUW xmm1, xmm2/m128 — (Packed Horizontal Word Minimum)
    • Input — { A0, A1,… A7 }
    • Output — { MinVal, MinPos, 0, 0… }

Поиск среди 16-ти битных беззнаковых полей A0…A7 такого, который имеет минимальное значение (и позицию с меньшим номером, если таких полей несколько). Возвращается 16-ти битное значение и его позиция.

  • PMOV{SX,ZX}{B,W,D} xmm1, xmm2/m{64,32,16} — (Packed Move with Sign/Zero Extend)

Группа из 12-ти инструкций для расширения формата упакованных полей. Упакованные 8, 16, или 32-х битные поля из младшей части аргумента расширяются (со знаком или без) в 16, 32 или 64-х битные поля результата.

Входной формат Результирующий
формат
8 бит 16 бит 32 бита
PMOVSXBW 16 бит
PMOVZXBW
PMOVSXBD PMOVSXWD 32 бита
PMOVZXBD PMOVZXWD
PMOVSXBQ PMOVSXWQ PMOVSXDQ 64 бита
PMOVZXBQ PMOVZXWQ PMOVZXDQ

Векторные примитивы

  • P{MIN,MAX}{SB,UW,SD,UD} xmm1, xmm2/m128 — (Minimum/Maximum of Packed Signed/Unsigned Byte/Word/DWord Integers)

Каждое поле результата есть минимальное/максимальное значение соответствующих полей двух аргументов. Байтовые поля рассматриваются только как числа со знаком, 16-ти битные — только как числа без знака. Для 32-х битных упакованных полей предусмотрен вариант как со знаком, так и без.

  • PMULDQ xmm1, xmm2/m128 — (Multiply Packed Signed Dword Integers)
    • Input — { A0, A1, A2, A3 }, { B0, B1, B2, B3 }
    • Output — { A0*B0, A2*B2 }
      Перемножение 32-х битных полей со знаком с выдачей полных 64-х бит результата (две операции умножения над 0 и 2 полями аргументов).
  • PMULLD xmm1, xmm2/m128 — (Multiply Packed Signed Dword Integers and Store Low Result)
    • Input — { A0, A1, A2, A3 }, { B0, B1, B2, B3 }
    • Output — { low32(A0*B0), low32(A1*B1), low32(A2*B2), low32(A3*B3)
      Перемножение 32-х битных полей со знаком с выдачей младших 32-х бит результатов (четыре операции умножения над всеми полями аргументов).
  • PACKUSDW xmm1, xmm2/m128 — (Pack with Unsigned Saturation)
    Упаковка 32-х битных полей со знаком в 16-ти битные поля без знака с насыщением.
  • PCMPEQQ xmm1, xmm2/m128 — (Compare Packed Qword Data for Equal)
    Проверка 64-х битных полей на равенство и выдача 64-х битных масок.

    ставки/извлечения

    • INSERTPS xmm1, xmm2/m32, imm8 — (Insert Packed Single Precision Floating-Point Value)

    Вставка 32-х битного поля из xmm2 (возможно выбрать любой из 4 полей этого регистра) или из 32-х битной ячейки памяти в произвольное поле результата. Кроме того, для каждого из полей результата можно задать сброс его в +0.0.

    • EXTRACTPS r/m32, xmm, imm8 — (Extract Packed Single Precision Floating-Point Value)

    Извлечение 32-х битного поля из xmm регистра, номер поля указывается в младших 2 битах imm8. Если в качестве результата указан 64-х битный регистр, то его старшие 32 бита сбрасываются (расширение без знака).

    • PINSR{B,D,Q} xmm, r/m*, imm8 — (Insert Byte/Dword/Qword)

    Вставка 8, 32, или 64-х битного значения в указанное поле xmm регистра (остальные поля не изменяются).

    • PEXTR{B,W,D,Q} r/m*, xmm, imm8 — (Extract Byte/Word/Dword/Qword)

    Извлечение 8, 16, 32, 64 битного поля из указанного в imm8 поля xmm регистра. Если в качестве результата указан регистр, то его старшая часть сбрасывается (расширение без знака).

    Скалярное умножение векторов

    • DPPS xmm1, xmm2/m128, imm8 — (Dot Product of Packed Single Precision Floating-Point Values)
    • DPPD xmm1, xmm2/m128, imm8 — (Dot Product of Packed Double Precision Floating-Point Values)

    Скалярное умножение векторов (dot product) 32/64 битных полей. Посредством битовой маски в imm8 указывается, какие произведения полей должны суммироваться и что следует прописать в каждое поле результата: сумму указанных произведений или +0.0.

    Смешивания

    • BLENDV{PS,PD} xmm1, xmm2/m128, <xmm0> — (Variable Blend Packed Single/Double Precision Floating-Point Values)

    Выбор каждого 32/64-битного поля результата осуществляется в зависимости от знака такого же поля в неявном аргументе xmm0: либо из первого, либо из второго аргумента.

    • BLEND{PS,PD} xmm1, xmm2/m128, imm8 — (Blend Packed Single/Double Precision Floating-Point Values)

    Битовая маска (4 или 2 бита) в imm8 указывает из какого аргумента следует взять каждое 32/64-битное поле результата.

    • PBLENDVB xmm1, xmm2/m128, <xmm0> — (Variable Blend Packed Bytes)

    Выбор каждого байтового поля результата осуществляется в зависимости от знака байта такого же поля в неявном аргументе xmm0: либо из первого, либо из второго аргумента.

    • PBLENDW xmm1, xmm2/m128, imm8 — (Blend Packed Words)

    Битовая маска (8 бит) в imm8 указывает из какого аргумента следует взять каждое 16-битное поле результата.

    Проверки бит

    • PTEST xmm1, xmm2/m128 — (Logical Compare)

    Установить флаг ZF, если только в xmm2/m128 все биты помеченные маской из xmm1 равны нулю. Если все не помеченные биты равны нулю, то установить флаг CF. Остальные флаги (AF, OF, PF, SF) всегда сбрасываются. Инструкция не модифицирует xmm1.

    Округления

    • ROUND{PS, PD} xmm1, xmm2/m128, imm8 — (Round Packed Single/Double Precision Floating-Point Values)

    Округление всех 32/64-х битных полей. Режим округления (4 варианта) выбирается либо из MXCSR.RC, либо задаётся непосредственно в imm8. Также можно подавить генерацию исключения потери точности.

    • ROUND{SS, SD} xmm1, xmm2/m128, imm8 — (Round Scalar Single/Double Precision Floating-Point Values)

    Округление только младшего 32/64-х битного поля (остальные биты остаются неизменными).

    Чтение WC памяти

    • MOVNTDQA xmm1, m128 — (Load Double Quadword Non-Temporal Aligned Hint)

    Операция чтения, позволяющая ускорить (до 7.5 раз) работу с write-combining областями памяти.

    Новые инструкции SSE4.2

    Обработка строк

    Эти инструкции выполняют арифметические сравнения между всеми возможными парами полей (64 или 256 сравнений!) из обеих строк, заданных содержимым xmm1 и xmm2/m128. Затем булевые результаты сравнений обрабатываются для получения нужных результатов. Непосредственный аргумент imm8 управляет размером (байтовые или unicode строки, до 16/8 элементов каждая), знаковостью полей (элементов строк), типом сравнения и интерпретацией результатов.

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

    Все они оказывают влияние на флаги процессора: SF устанавливается если в xmm1 не полная строка, ZF — если в xmm2/m128 не полная строка, CF — если результат не нулевой, OF — если младший бит результата не нулевой. Флаги AF и PF сбрасываются.

    • PCMPESTRI <ecx>, xmm1, xmm2/m128, <eax>, <edx>, imm8 — ()

    Явное задание размера строк в <eax>, <edx> (берётся абсолютная величина регистров с насыщение до 8/16, в зависимости от размера элементов строк. Результат в регистре ecx.

    • PCMPESTRM <xmm0>, xmm1, xmm2/m128, <eax>, <edx>, imm8 — ()

    Явное задание размера строк в <eax>, <edx> (берётся абсолютная величина регистров с насыщение до 8/16, в зависимости от размера элементов строк. Результат в регистре xmm0.

    • PCMPISTRI <ecx>, xmm1, xmm2/m128, imm8 — ()

    Неявное задание размера строк (производится поиск нулевых элементов к каждой из строк). Результат в регистре ecx.

    • PCMPISTRM <xmm0>, xmm1, xmm2/m128, imm8 — ()

    Неявное задание размера строк (производится поиск нулевых элементов к каждой из строк). Результат в регистре xmm0.

    Подсчет CRC32

    • CRC32 r32, r/m* — (Подсчет CRC32)

    Накопление значения CRC-32C (другие обозначения CRC-32/ISCSI CRC-32/CASTAGNOLI) для 8, 16, 32 или 64 битного аргумента (используется полином 0x1EDC6F41).

    Подсчет популяции единичных битов

    • POPCNT r, r/m* — (Return the Count of Number of Bits Set to 1)

    Подсчет числа единичных битов. Три варианта инструкции: для 16, 32 и 64-х битных регистров. Также присутствует в SSE4A от AMD.

    Векторные примитивы

    • PCMPGTQ xmm1, xmm2/m128 — (Compare Packed Qword Data for Greater Than)

    Проверка 64-х битных полей на «больше чем» и выдача 64-х битных масок.

    SSE4a

    Набор инструкций SSE4a был введен компанией AMD в процессоры на архитектуре Barcelona. Это расширение не доступно в процессорах Intel. Поддержка определяется через CPUID.80000001H:ECX.SSE4A[Bit 6] флаг.

    Инструкция Описание
    LZCNT/POPCNT Подсчет числа нулевых/единичных битов.
    EXTRQ/INSERTQ Комбинированные инструкции маскирования и сдвига
    MOVNTSD/MOVNTSS Скалярные инструкции потоковой записи

    AMD