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