Ветвь — это инструкция в компьютерной программе , которая может заставить компьютер начать выполнение другой последовательности команд и, таким образом, отклониться от поведения по умолчанию при выполнении инструкций по порядку . [a] Ветвь (или ветвление , разветвленный ) также может относиться к действию переключения выполнения на другую последовательность команд в результате выполнения команды ветвления. Инструкции ветвления используются для реализации потока управления в программных циклах и условных выражениях (т. е. выполнение определенной последовательности инструкций только при выполнении определенных условий).
Инструкция ветвления может быть либо безусловной ветвью , которая всегда приводит к ветвлению, либо условной ветвью , которая может вызывать или не вызывать ветвление в зависимости от некоторого условия. Кроме того, в зависимости от того, как она определяет адрес новой последовательности команд («целевой» адрес), команда ветвления обычно классифицируется как прямая , косвенная или относительная , что означает, что инструкция содержит целевой адрес или указывает, где находится целевой адрес. адрес должен быть найден (например, регистр или ячейка памяти), или он определяет разницу между текущим и целевым адресами.
Инструкции перехода могут изменить содержимое счетчика программ ЦП ( или ПК) (или указателя инструкций на микропроцессорах Intel). ПК сохраняет адрес памяти следующей машинной инструкции, которая должна быть выбрана и выполнена. Таким образом, ветвь, если она выполняется, заставляет ЦП выполнять код с нового адреса памяти, изменяя логику программы в соответствии с алгоритмом, запланированным программистом.
Одним из типов ветвей машинного уровня является инструкция перехода . Это может привести или не привести к загрузке или изменению ПК с каким-то новым, отличным от того значением, которое оно обычно было бы (увеличенное после текущей инструкции, чтобы указать на следующую, следующую инструкцию). Прыжки обычно имеют безусловную и условную формы, причем последний может быть выполнен или не выполнен (модифицирован ПК или нет) в зависимости от какого-либо условия.
Второй тип ветвей машинного уровня — это инструкция вызова , которая используется для реализации подпрограмм . Подобно инструкциям перехода, вызовы могут изменять или не изменять ПК в соответствии с кодами условий, однако дополнительно адрес возврата сохраняется в безопасном месте в памяти (обычно в резидентной структуре данных памяти, называемой стеком ) . По завершении подпрограммы этот адрес возврата восстанавливается в ПК, и поэтому выполнение программы возобновляется с инструкции, следующей за командой вызова.
Третий тип ветвления машинного уровня — это инструкция возврата . Это «выталкивает» адрес возврата из стека и загружает его в регистр ПК, тем самым возвращая управление вызывающей программе. Инструкции возврата также могут выполняться условно. Это описание относится к обычной практике; однако машинный программист обладает значительными полномочиями манипулировать адресом возврата в стеке и, таким образом, перенаправлять выполнение программы любым количеством различных способов.
В зависимости от процессора инструкции перехода и вызова могут изменять содержимое регистра ПК по-разному. Может быть загружен абсолютный адрес, или к текущему содержимому ПК может быть добавлено или вычтено некоторое значение (или смещение) из его текущего значения, что делает адрес назначения относительно текущего места в программе. Источник значения смещения может варьироваться, например, непосредственное значение, встроенное в инструкцию, или содержимое регистра процессора или ячейки памяти, или содержимое некоторой ячейки, добавленной к значению индекса.
Термин « ветвь» также можно использовать применительно к программам на языках программирования высокого уровня . В этих ветвях обычно принимают форму условные операторы различной формы, инкапсулирующие последовательность команд, которая будет выполнена, если условия будут выполнены. Инструкции безусловного перехода, такие как GOTO , используются для безусловного перехода к другой последовательности команд. Если алгоритм требует условного перехода, вызову функции GOTO (или GOSUB) предшествует оператор IF-THEN, определяющий условие(я). Все языки высокого уровня поддерживают алгоритмы, которые могут повторно использовать код в виде цикла — структуры управления, которая повторяет последовательность инструкций до тех пор, пока не будет выполнено какое-либо условие, приводящее к завершению цикла. Циклы также считаются инструкциями ветвления. На машинном уровне циклы реализованы как обычные условные переходы, перенаправляющие выполнение на повторяющийся код.
В процессорах с регистрами флагов более ранняя инструкция устанавливает условие в регистре флагов. Предыдущая инструкция может быть арифметической или логической инструкцией. Часто она находится рядом с ветвью, хотя не обязательно это инструкция непосредственно перед ветвью. Сохраненное условие затем используется в такой ветви, как прыжок, если установлен флаг переполнения . Эта временная информация часто хранится в регистре флагов, но может также находиться в другом месте. Конструкция регистра флагов проста на более медленных и простых компьютерах. В быстрых компьютерах регистр флагов может стать узким местом в скорости, поскольку инструкции, которые в противном случае могли бы работать параллельно (в нескольких исполнительных модулях ), должны устанавливать биты флагов в определенной последовательности.
Существуют также машины (или отдельные инструкции), в которых условие может быть проверено самой инструкцией перехода, например, переход <label>, если регистр X отрицательный . В простых компьютерных конструкциях ветви сравнения выполняют больше арифметических операций и могут использовать больше энергии, чем ветви регистров флагов. В конструкциях быстрых компьютеров ветви сравнения могут работать быстрее, чем ветви регистров флагов, поскольку ветви сравнения могут получать доступ к регистрам с большим параллелизмом, используя те же механизмы ЦП, что и при расчете.
Некоторые ранние и простые архитектуры ЦП, которые все еще встречаются в микроконтроллерах, могут не реализовывать условный переход, а только условную операцию «пропустить следующую инструкцию». Таким образом, условный переход или вызов реализуется как условный пропуск инструкции безусловного перехода или вызова.
В зависимости от архитектуры компьютера мнемоника ассемблерного языка для инструкции перехода обычно представляет собой некую сокращенную форму слова « переход» или « ветвь слова », часто вместе с другими информативными буквами (или дополнительным параметром), представляющими условие. Иногда включаются и другие детали, такие как диапазон перехода (размер смещения) или специальный режим адресации, который следует использовать для определения фактического эффективного смещения.
В этой таблице перечислены инструкции ветвления или перехода на машинном уровне, встречающиеся в нескольких известных архитектурах:
* x86, PDP-11, VAX и некоторые другие устанавливают флаг переноса, чтобы сигнализировать о заимствовании , и сбрасывают флаг переноса, чтобы сигнализировать об отсутствии заимствования . ARM, 6502 , PIC и некоторые другие делают противоположное для операций вычитания. Эта инвертированная функция флага переноса для определенных инструкций отмечена ( * ), то есть в некоторых частях таблицы заимствование= не перенос , но, если не указано иное, заимствование≡перенос. Однако большинство архитектур обрабатывают аддитивные операции одинаково.
Для достижения высокой производительности современные процессоры имеют конвейерную обработку . Они состоят из нескольких частей, каждая из которых частично обрабатывает инструкцию, передает свои результаты на следующий этап конвейера и начинает работать над следующей инструкцией в программе. Эта конструкция предполагает, что инструкции будут выполняться в определенной неизменной последовательности. Инструкции условного перехода делают невозможным узнать эту последовательность. Таким образом, условные переходы могут вызывать «остановки», при которых конвейер приходится перезапускать в другой части программы.
Некоторые методы повышают скорость за счет уменьшения задержек при выполнении условных ветвей.
Исторически сложилось так, что предсказание ветвей брало статистику и использовало ее результат для оптимизации кода. Программист компилировал тестовую версию программы и запускал ее с тестовыми данными. Тестовый код подсчитывал, как на самом деле были взяты ветки. Статистика тестового кода затем использовалась компилятором для оптимизации ветвей выпущенного кода. Оптимизация должна обеспечить, чтобы самое быстрое направление ветвления (выбранное или нет) всегда было наиболее часто используемым путем потока управления. Чтобы обеспечить это, процессоры должны быть спроектированы с (или, по крайней мере, иметь) предсказуемое время перехода. Некоторые процессоры имеют наборы инструкций (например, Power ISA ), которые были разработаны с «подсказками ветвей», чтобы компилятор мог сообщать процессору, как следует использовать каждую ветвь.
Проблема с прогнозированием ветвей программного обеспечения заключается в том, что он требует сложного процесса разработки программного обеспечения.
Для запуска любого программного обеспечения предсказатели аппаратного обеспечения переносили статистику в электронику. Предикторы ветвей — это части процессора, которые угадывают результат условного ветвления. Затем логика процессора делает ставку на предположение, начиная выполнять ожидаемый поток команд. Примером простой аппаратной схемы прогнозирования ветвей является предположение, что все обратные переходы (т. е. к меньшему программному счетчику) выполняются (поскольку они являются частью цикла), а все прямые переходы (к большему программному счетчику) не выполняются. (потому что они оставляют петлю). Лучшие предсказатели ветвей разрабатываются и проверяются статистически путем их моделирования в различных тестовых программах. Хорошие предсказатели обычно подсчитывают результаты предыдущих выполнений ветки. Более быстрые и дорогие компьютеры смогут работать быстрее, если инвестировать в лучшую электронику для прогнозирования ветвлений. В ЦП с аппаратным предсказанием ветвей подсказки ветвей позволяют предположительно лучшему предсказанию ветвей компилятора переопределять более упрощенное предсказание ветвей аппаратного обеспечения.
Некоторая логика может быть написана без ветвей или с меньшим количеством ветвей. Часто вместо ветвей можно использовать побитовые операции , условные ходы или другие предсказывания . [1] [2] Фактически, код без ветвей является обязательным для криптографии из-за атак по времени . [3]
Другой метод — слот задержки ветвления . В этом подходе всегда выполняется по крайней мере одна инструкция, следующая за ветвью, за некоторыми исключениями, такими как устаревшая инструкция вероятного/маловероятного перехода в архитектуре MIPS . Таким образом, компьютер может использовать эту инструкцию для выполнения полезной работы независимо от того, зависает ли его конвейер. Этот подход исторически был популярен в компьютерах RISC . В семействе совместимых процессоров он усложняет многоцикловые процессоры (без конвейера), более быстрые процессоры с более длинными, чем ожидалось, конвейерами и суперскалярные процессоры (которые могут выполнять инструкции не по порядку).