Инструкции ветвления в компьютерных программах

Введение

Инструкция в компьютерной программе

Ветвление – это инструкция в компьютерной программе, которая может заставить компьютер начать выполнять другую последовательность инструкций и, таким образом, отклониться от своего стандартного поведения, заключающегося в последовательном выполнении инструкций. Ветвление (или переход, ветвящаяся инструкция) также может означать сам процесс переключения выполнения на другую последовательность инструкций в результате выполнения инструкции ветвления. Инструкции ветвления используются для реализации управления потоком выполнения в программных циклах и условных операторах (то есть, для выполнения определенной последовательности инструкций только при выполнении определенных условий). Инструкция ветвления может быть безусловной, которая всегда приводит к переходу, или условной, которая может или не может привести к переходу в зависимости от определенного условия. Кроме того, в зависимости от способа указания адреса новой последовательности инструкций (адреса "цели"), инструкция ветвления обычно классифицируется как прямая, косвенная или относительная, то есть инструкция содержит адрес цели, указывает, где находится адрес цели (например, в регистре или ячейке памяти), или указывает разницу между текущим и целевым адресами.

Реализация

Инструкции ветвления могут изменять содержимое счетчика программ процессора (или ПК) (или указателя инструкций на микропроцессорах Intel). ПК хранит адрес памяти следующей машинной инструкции, которая должна быть извлечена и выполнена. Следовательно, ветвление, если оно выполнено, заставляет процессор выполнять код с нового адреса памяти, изменяя логику программы в соответствии с алгоритмом, запланированным программистом. Одним из видов ветвления на машинном уровне является инструкция перехода (jump). Они могут приводить к загрузке или изменению ПК новым значением, отличным от обычного (когда ПК увеличивается после текущей инструкции, чтобы указать на следующую инструкцию). Переходы обычно имеют безусловные и условные формы, причем последние могут быть выполнены или не выполнены (ПК изменяется или нет) в зависимости от определенного условия. Второй тип ветвления на машинном уровне — это инструкция вызова подпрограммы, используемая для реализации подпрограмм. Как и инструкции перехода, вызовы могут изменять или не изменять ПК в соответствии с кодами состояния, однако дополнительно адрес возврата сохраняется в безопасном месте в памяти (обычно в структуре данных, находящейся в памяти, называемой стеком). После завершения подпрограммы этот адрес возврата восстанавливается в ПК, и выполнение программы возобновляется с инструкции, следующей за инструкцией вызова. Третий тип ветвления на машинном уровне — это инструкция возврата. Она извлекает адрес возврата из стека и загружает его в регистр ПК, тем самым возвращая управление вызывающей процедуре. Инструкции возврата также могут выполняться условно. Данное описание относится к обычной практике, однако машинный программист обладает значительными возможностями для манипулирования адресом возврата в стеке и, следовательно, для перенаправления выполнения программы различными способами. В зависимости от процессора, инструкции перехода и вызова могут изменять содержимое регистра ПК различными способами. Может быть загружен абсолютный адрес, или к текущему содержимому ПК может быть добавлено или вычтено некоторое значение (или смещение), делая адрес назначения относительным текущему положению в программе. Источник значения смещения может быть различным, например, непосредственное значение, встроенное в инструкцию, содержимое регистра процессора или ячейки памяти, или содержимое некоторой ячейки, к которому добавлено индексное значение. Термин "ветвление" также может использоваться применительно к программам на языках программирования высокого уровня. В этих языках ветвления обычно принимают форму условных операторов различных видов, которые заключают в себе последовательность инструкций, которая будет выполнена, если условия выполнены. Безусловные инструкции ветвления, такие как GOTO, используются для безусловного перехода к другой последовательности инструкций. Если алгоритму требуется условное ветвление, вызову подпрограммы GOTO (или GOSUB) предшествует оператор IF THEN, определяющий условие(я). Все языки программирования высокого уровня поддерживают алгоритмы, которые могут повторно использовать код в виде цикла — структуры управления, которая повторяет последовательность инструкций до тех пор, пока не будет выполнено некоторое условие, вызывающее завершение цикла. Циклы также квалифицируются как инструкции ветвления. На машинном уровне циклы реализуются как обычные условные переходы, перенаправляющие выполнение на повторяющийся код. В процессорах с регистром флагов более ранняя инструкция устанавливает условие в регистре флагов. Эта инструкция может быть арифметической или логической. Она часто находится рядом с ветвлением, хотя и не обязательно непосредственно перед ним. Затем сохраненное условие используется в ветвлении, например, "перейти, если установлен флаг переполнения". Эта временная информация часто хранится в регистре флагов, но также может находиться в другом месте. Конструкция регистра флагов проста в более медленных и простых компьютерах. В быстрых компьютерах регистр флагов может стать узким местом, поскольку инструкции, которые могли бы выполняться параллельно (в нескольких вычислительных блоках), должны устанавливать биты флага в определенной последовательности. Существуют также машины (или отдельные инструкции), где условие может быть проверено самой инструкцией перехода, например, "перейти к <метка>, если регистр X отрицателен". В простых компьютерных конструкциях ветвления с сравнением выполняют больше арифметических операций и потребляют больше энергии, чем ветвления с использованием регистра флагов. В быстрых компьютерных конструкциях ветвления с сравнением могут выполняться быстрее, чем ветвления с использованием регистра флагов, поскольку ветвления с сравнением могут обращаться к регистрам с большей степенью параллелизма, используя те же механизмы ЦП, что и вычисления. Некоторые ранние и простые архитектуры ЦП, которые до сих пор встречаются в микроконтроллерах, могут не реализовывать условный переход, а вместо этого только операцию "пропустить следующую инструкцию" при выполнении условия. Условный переход или вызов, таким образом, реализуется как условный пропуск безусловной инструкции перехода или вызова.

Branch instructions can alter the contents of the CPU's Program Counter (or PC) (or Instruction Pointer on Intel microprocessors). The PC maintains the memory address of the next machine instruction to be fetched and executed. Therefore, a branch, if executed, causes the CPU to execute code from a new memory address, changing the program logic according to the algorithm planned by the programmer. One type of machine level branch is the jump instruction. These may or may not result in the PC being loaded or modified with some new, different value other than what it ordinarily would have been (being incremented past the current instruction to point to the following, next instruction). Jumps typically have unconditional and conditional forms where the latter may be taken or not taken (the PC is modified or not) depending on some condition. The second type of machine level branch is the call instruction which is used to implement subroutines. Like jump instructions, calls may or may not modify the PC according to condition codes, however, additionally a return address is saved in a secure place in memory (usually in a memory resident data structure called a stack). Upon completion of the subroutine, this return address is restored to the PC, and so program execution resumes with the instruction following the call instruction. The third type of machine level branch is the return instruction. This "pops" a return address off the stack and loads it into the PC register, thus returning control to the calling routine. Return instructions may also be conditionally executed. This description pertains to ordinary practice; however, the machine programmer has considerable powers to manipulate the return address on the stack, and so redirect program execution in any number of different ways. Depending on the processor, jump and call instructions may alter the contents of the PC register in different ways. An absolute address may be loaded, or the current contents of the PC may have some value (or displacement) added or subtracted from its current value, making the destination address relative to the current place in the program. The source of the displacement value may vary, such as an immediate value embedded within the instruction, or the contents of a processor register or memory location, or the contents of some location added to an index value. The term branch can also be used when referring to programs in high level programming languages. In these branches usually take the form of conditional statements of various forms that encapsulate the instruction sequence that will be executed if the conditions are satisfied. Unconditional branch instructions such as GOTO are used to unconditionally jump to a different instruction sequence. If the algorithm requires a conditional branch, the GOTO (or GOSUB subroutine call) is preceded by an IF THEN statement specifying the condition(s). All high level languages support algorithms that can re use code as a loop, a control structure that repeats a sequence of instructions until some condition is satisfied that causes the loop to terminate. Loops also qualify as branch instructions. At the machine level, loops are implemented as ordinary conditional jumps that redirect execution to repeating code. In CPUs with flag registers, an earlier instruction sets a condition in the flag register. The earlier instruction may be arithmetic, or a logic instruction. It is often close to the branch, though not necessarily the instruction immediately before the branch. The stored condition is then used in a branch such as jump if overflow flag set. This temporary information is often stored in a flag register but may also be located elsewhere. A flag register design is simple in slower, simple computers. In fast computers a flag register can place a bottleneck on speed, because instructions that could otherwise operate in parallel (in several execution units) need to set the flag bits in a particular sequence. There are also machines (or particular instructions) where the condition may be checked by the jump instruction itself, such as branch <label> if register X negative. In simple computer designs, comparison branches execute more arithmetic and can use more power than flag register branches. In fast computer designs comparison branches can run faster than flag register branches, because comparison branches can access the registers with more parallelism, using the same CPU mechanisms as a calculation. Some early and simple CPU architectures, still found in microcontrollers, may not implement a conditional jump, but rather only a conditional "skip the next instruction" operation. A conditional jump or call is thus implemented as a conditional skip of an unconditional jump or call instruction.

Проблемы с выполнением инструкций филиала

Для достижения высокой производительности современные процессоры используют конвейерную обработку. Они состоят из нескольких блоков, каждый из которых частично обрабатывает инструкцию, передает результаты следующему блоку конвейера и приступает к обработке следующей инструкции программы. Такая архитектура предполагает выполнение инструкций в строго определенной, неизменной последовательности. Инструкции условного перехода нарушают предсказуемость этой последовательности. Поэтому условные переходы могут приводить к "остановкам" конвейера, когда его приходится перезапускать с другой части программы.

Улучшение производительности за счет сокращения количества рабочих мест в филиалах

Несколько методов повышают скорость за счет уменьшения простоев, вызванных условными переходами.

Подсказки по прогнозированию ветвей

Исторически, прогнозирование переходов основывалось на статистических данных, которые использовались для оптимизации кода. Программист компилировал тестовую версию программы и запускал её с тестовыми данными. Тестовый код подсчитывал, как фактически выполнялись переходы. Статистические данные, полученные из тестового кода, затем использовались компилятором для оптимизации переходов в релизной версии кода. Оптимизация обеспечивала, чтобы наиболее быстрое направление перехода (выполненный или не выполненный) всегда соответствовало наиболее частому пути управления потоком. Для этого процессоры должны быть спроектированы с (или, по крайней мере, иметь) предсказуемым временем выполнения переходов. Некоторые процессоры имеют наборы инструкций (например, Power ISA), которые были разработаны с поддержкой "подсказок переходов", позволяющих компилятору сообщать процессору, как должен выполняться каждый переход. Проблема программного прогнозирования переходов заключается в том, что оно требует сложного процесса разработки программного обеспечения.

Предсказатели аппаратных ветвей

Чтобы запустить любое программное обеспечение, аппаратные предсказатели ветвлений перенесли статистические данные в электронные схемы. Предсказатели ветвлений – это компоненты процессора, которые предсказывают исход условного перехода. Затем логика процессора делает ставку на это предсказание, начиная выполнять предполагаемую последовательность инструкций. Простым примером схемы аппаратного предсказания ветвлений является предположение, что все обратные ветвления (то есть переходы к меньшему счетчику команд) выполняются (поскольку они обычно являются частью цикла), а все прямые ветвления (к большему счетчику команд) не выполняются (поскольку они выходят из цикла). Более совершенные предсказатели ветвлений разрабатываются и статистически проверяются путем моделирования их работы на различных тестовых программах. Хорошие предсказатели обычно учитывают результаты предыдущих выполнений ветвлений. Более быстрые и дорогие компьютеры могут работать быстрее, инвестируя в более совершенные электронные схемы предсказания ветвлений. В процессоре с аппаратным предсказанием ветвлений, подсказки ветвлений позволяют более точному предсказанию ветвлений, выполняемому компилятором, переопределять более простое аппаратное предсказание.

Код без отраслей

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

Слот задержки

Другой метод — это слот задержки ветвления. В этом подходе как минимум одна инструкция, следующая за ветвлением, всегда выполняется, за некоторыми исключениями, такими как инструкция ветвления "вероятно/невероятно" в устаревшей архитектуре MIPS. Таким образом, компьютер может использовать эту инструкцию для выполнения полезной работы, независимо от того, произойдет ли остановка конвейера. Этот подход исторически был популярен в RISC-компьютерах. В семействе совместимых процессоров он усложняет конструкцию многоцикловых процессоров (без конвейера), более быстрых процессоров с конвейерами большей, чем ожидалось, длины, и суперскалярных процессоров (которые могут выполнять инструкции вне порядка).