 | Эта статья требует дополнительных ссылок для проверки . ( июнь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
| Машинный код |
|---|
| Общие понятия |
| инструкции |
Филиал является инструкцией в компьютерной программе , которая может вызвать компьютер , чтобы начать выполнение другой последовательности команд и , таким образом , отклоняться от своего поведения выполнения команд в порядке по умолчанию. [a] Ветвь (или ветвление , разветвление ) также может относиться к действию переключения выполнения на другую последовательность команд в результате выполнения команды ветвления. Инструкции ветвления используются для реализации потока управления в программных циклах и условных выражениях (т. Е. Выполнение определенной последовательности инструкций только при соблюдении определенных условий).
Инструкция ветвления может быть либо безусловным ветвлением , которое всегда приводит к ветвлению, либо условным ветвлением , которое может или не может вызывать ветвление в зависимости от некоторого условия. Кроме того, в зависимости от того, как он определяет адрес новой последовательности инструкций («целевой» адрес), инструкция ветвления обычно классифицируется как прямая , косвенная или относительная , что означает, что инструкция содержит целевой адрес или указывает, где находится целевой адрес должен быть найден (например, регистр или место в памяти), или он определяет разницу между текущим и целевым адресами.
Реализация [ править ]
Механически команда перехода может изменить счетчик программ (ПК) ЦП . Счетчик программ хранит адрес памяти следующей инструкции, которая должна быть выполнена. Следовательно, ветвь может заставить ЦП начать выборку своих инструкций из другой последовательности ячеек памяти.
Когда ветвь принимаются , счетчик программы КП устанавливаются на аргумент инструкции перехода. Таким образом, следующая инструкция становится инструкцией по этому адресу в памяти . Следовательно, поток управления меняется.
Когда ветвь не занята , счетчик программы ЦП не изменяется. Следовательно, следующая выполняемая инструкция - это инструкция после инструкции ветвления. Следовательно, поток управления не изменился.
Термин ветвь может использоваться при ссылке на программы на языках высокого уровня, а также на программы, написанные на машинном коде или языке ассемблера . В языках программирования высокого уровня ветви обычно принимают форму условных операторов различных форм, которые инкапсулируют последовательность инструкций, которая будет выполняться при выполнении условий. Инструкции безусловного перехода, такие как GOTO , используются для безусловного «перехода» к другой последовательности команд (начала выполнения).
Инструкции ветвления машинного уровня иногда называют инструкциями перехода . Инструкции перехода на машинный уровень обычно имеют безусловную и условную формы, причем последние могут быть приняты или не приняты в зависимости от некоторых условий. Обычно существует различные формы для одностороннего скачет, часто называемый прыжок и подпрограммы вызовы , известные как вызов , который автоматически сохранить полученный адрес в качестве адреса возврата в стеке, что позволяет один подпрограмму, которая вызывается из нескольких мест в коде.
В процессорах с регистрами флагов более ранняя инструкция устанавливает условие в регистре флагов. Более ранняя инструкция может быть арифметической или логической . Часто это близко к ветке, хотя не обязательно к инструкции непосредственно перед ветвью. Сохраненное условие затем используется в ветви, такой как переход, если установлен флаг переполнения . Эта временная информация часто хранится в регистре флагов, но может также находиться в другом месте. Конструкция регистра флага проста на более медленных и простых компьютерах. В быстрых компьютерах регистр флага может стать узким местом для скорости, потому что инструкции, которые в противном случае могли бы работать параллельно (в нескольких исполнительных модулях ), должны устанавливать биты флагов в определенной последовательности.
Существуют также машины (или конкретные инструкции), где условие может быть проверено самой инструкцией перехода, например, ветвь <метка>, если регистр X отрицательный . В простых компьютерных схемах ветви сравнения выполняют больше арифметических операций и могут потреблять больше энергии, чем ветви регистров флагов. В быстрых компьютерных проектах ветви сравнения могут работать быстрее, чем ветви регистров флагов, потому что ветви сравнения могут обращаться к регистрам с большим параллелизмом, используя те же механизмы процессора, что и вычисления.
Некоторые ранние и простые архитектуры ЦП, все еще встречающиеся в микроконтроллерах, могут не реализовывать условный переход, а только условную операцию «пропустить следующую инструкцию». Таким образом, условный переход или вызов реализуется как условный пропуск инструкции безусловного перехода или вызова.
Примеры [ править ]
В зависимости от архитектуры компьютера , то язык ассемблера мнемоник для команды перехода , как правило , некоторая сокращенная форма слова скачки или слов ветви , часто вместе с другими информационными письмами (или дополнительным параметром) , представляющих состоянием. Иногда включаются и другие детали, такие как диапазон перехода (размер смещения) или специальный режим адресации, который следует использовать для определения фактического эффективного смещения.
В этой таблице перечислены инструкции перехода или перехода на машинном уровне, встречающиеся в нескольких хорошо известных архитектурах:
| состояние или результат | x86 | ПДП-11, ВАКС | ARM (частично 6502) | уравнение |
|---|---|---|---|---|
| ноль (подразумевает равное для sub / cmp) | JZ; JNZ | БЫТЬ Q; BNE | БЫТЬ Q; BNE | нуль; не ноль |
| отрицательный (N), знак (S) или минус (M) | JS; JNS | ИМТ; BPL | ИМТ; BPL | отрицательный; не отрицательный |
| арифметическое переполнение (флаг называется O или V) | ДЖО; JNO | БВС; BVC | БВС; BVC | перелив; не переполняться |
| переносить (от add, cmp, shift и т. д.) | JC; JNC | BCS; BCC | BCS; BCC | нести; не носить |
| беззнаковый снизу (нижний) | JB | BLO | BLO * | одолжить |
| без знака ниже или равно (ниже или равно) | JBE | BLOS | BLS * | одолжить или ноль |
| беззнаковый выше или равный (выше или такой же) | JAE | BHIS | BHS * | не брать в долг |
| беззнаковый выше (выше) | JA | BHI | BHI * | не брать в долг и не ноль |
| подписано меньше чем | JL | BLT | BLT | знак ≠ переполнение |
| со знаком меньше или равно | JLE | BLE | BLE | (знак ≠ переполнение) или ноль |
| со знаком больше или равно | JGE | BGE | BGE | знак = переполнение |
| подписано больше чем | JG | BGT | BGT | (знак = переполнение), а не ноль |
* x86, PDP-11, VAX и некоторые другие устанавливают флаг переноса, чтобы сигнализировать о заимствовании, и сбрасывают флаг переноса, чтобы сигнализировать об отсутствии заимствования . ARM, 6502 , PIC и некоторые другие делают противоположное для операций вычитания. Эта инвертированная функция флага переноса для определенных инструкций отмечена ( * ), то есть заимствовать = не переносить в некоторых частях таблицы, но, если не указано иное, заимствовать≡ переносить. Однако аддитивные операции продолжения обрабатываются одинаково в большинстве архитектур.
Проблемы с производительностью с инструкциями веток [ править ]
Для достижения высокой производительности современные процессоры конвейерные . Они состоят из нескольких частей, каждая из которых частично обрабатывает инструкцию, передает свои результаты следующему этапу конвейера и начинает работу над следующей инструкцией в программе. Этот дизайн предполагает, что инструкции будут выполняться в определенной неизменной последовательности. Инструкции условного перехода делают невозможным знание этой последовательности. Таким образом, условные переходы могут вызывать «сбои», при которых конвейер должен быть перезапущен в другой части программы.
Повышение производительности за счет уменьшения киосков в филиалах [ править ]
Некоторые методы повышают скорость за счет уменьшения задержек из условных ветвей.
Подсказки предсказания ветвления [ править ]
Исторически прогнозирование ветвлений основывалось на статистических данных и использовало результат для оптимизации кода. Программист скомпилирует тестовую версию программы и запустит ее с тестовыми данными. В тестовом коде учитывалось, как на самом деле были взяты ветви. Статистические данные из тестового кода затем использовались компилятором для оптимизации ветвей выпущенного кода. Оптимизация будет обеспечивать, чтобы самое быстрое направление ветвления (принятое или нет) всегда было наиболее часто используемым путем потока управления. Чтобы разрешить это, процессоры должны быть спроектированы (или, по крайней мере, иметь) предсказуемую синхронизацию ветвления. Некоторые процессоры имеют наборы инструкций (например, Power ISA ), которые были разработаны с использованием «подсказок ветвлений», чтобы компилятор мог сообщить процессору, как следует выполнять каждую ветвь.
Проблема с прогнозированием ветвления программного обеспечения заключается в том, что он требует сложного процесса разработки программного обеспечения.
Предикторы аппаратного перехода [ править ]
Для запуска любого программного обеспечения предикторы ветвления оборудованияпереместил статистику в электронику. Предикторы перехода - это части процессора, которые угадывают результат условного перехода. Затем логика процессора делает ставку на предположение, начиная выполнять ожидаемый поток инструкций. Пример простой схемы аппаратного прогнозирования ветвлений - предположить, что все обратные ветки (то есть к меньшему программному счетчику) взяты (потому что они являются частью цикла), а все прямые ветвления (к большему счетчику программ) не берутся. (потому что они оставляют петлю). Лучшие предикторы ветвлений разрабатываются и проверяются статистически путем их моделирования в различных тестовых программах. Хорошие предикторы обычно подсчитывают результаты предыдущих выполнений ветки. Тогда более быстрые и дорогие компьютеры могут работать быстрее, если вложить средства в лучшую электронику для прогнозирования ветвлений.В ЦП с аппаратным предсказанием ветвления подсказки ветвлений позволяют предположительно лучшему предсказанию ветвления компилятора перекрывать более упрощенное аппаратное предсказание ветвления.
Код без ответвлений [ править ]
Некоторая логика может быть написана без ветвей или с меньшим количеством ветвей. Часто вместо ветвлений можно использовать побитовые операции , условные перемещения или другое предсказание . [1] [2] Фактически, код без ветвей является обязательным условием для криптографии из-за временных атак . [3]
Слот задержки [ править ]
Другой способ - слот задержки перехода . В этом подходе всегда выполняется одна инструкция после перехода. Следовательно, компьютер может использовать эту инструкцию для выполнения полезной работы независимо от того, остановился ли его конвейер. Этот подход был исторически популярен в компьютерах RISC . В семействе совместимых процессоров он усложняет многоцикловые процессоры (без конвейера), более быстрые процессоры с более длинными, чем ожидалось, конвейерами и суперскалярные процессоры (которые могут выполнять инструкции не по порядку).
См. Также [ править ]
- Слот задержки перехода
- Предикация ветвления
- Таблица ответвлений
- Условный (программирование)
- Поток управления
- Косвенная ветвь
- Счетчик команд
- Подпрограмма
- Код спагетти
Заметки [ править ]
- ^ По крайней мере, концептуально; см. внеочередное исполнение .
Ссылки [ править ]
- ^ Кнут, Дональд (2008). Искусство программирования . Том 4, Пре-глава 1А (Редакция 6-го изд.). С. 48–49.
|volume=имеет дополнительный текст ( справка ) - ^ «Избегая ветвей» . Вики по шахматному программированию .
- ^ «Постоянная криптография» . BearSSL .
Внешние ссылки [ править ]
- Бесплатная документация по IA-32 и x86-64 , предоставленная Intel
- FAQ по PDP-11
- Набор инструкций ARM
