Реализация проверки границ цикла через прерывание переполнения

Question

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

Итак, предположим, что у вас есть массив, например int[32]и вы хотите повторить это. Что вы можете сделать сейчас, чтобы избежать проверки границ при каждом запуске цикла, так это зарегистрировать обработчик прерывания для прерывания переполнения и присвоить регистру значениеMAX - 32. Этот регистр увеличивается при каждой итерации цикла, и последняя итерация запускает переполнение, т.е. запускает обработчик прерывания. Предположим, что обработчик прерывания может увеличить счетчик программы исходной функции, этот механизм можно использовать, чтобы избежать проверки границ.

Так что код вроде

for (int i = 0; i < array.length; i++) {
  // do something
}

может быть реализован как

// setup interrupt somehow
SOME_REGISTER = MAX - array.length;
while (true) {
  // do something
  SOME_REGISTER++;
}

Я не знаю, выполнимо ли это, но я слышал, что Java делает что-то подобное, чтобы избежать нулевых проверок в сгенерированном во время выполнения коде. Как вы думаете, это выполнимо, или это когда-либо рассматривалось / опробовалось какой-либо языковой средой?

Answer 1

Исключение происходит очень медленно; массив должен быть огромным, чтобы компенсировать дополнительную стоимость выхода из цикла из-за сбоя, даже если вы можете сохранить инструкцию внутри цикла.

Вероятно, вы читали о проверке границ массивов на 64-битном оборудовании с использованием аппаратной защиты памяти: завершение массивов в конце виртуальной страницы и оставление следующей страницы несопоставленной. ВМ перехватывает SIGSEGV и доставляет исключение гостевому коду, если когда-либо происходит исключение вне пределов. Это устраняет необходимость проверки границ для случайного доступа, а не в цикле.

Этот метод вызывает ошибку неверной страницы (segfault) только тогда, когда гостевой код фактически принимает исключение границ массива, а не в обычном случае выхода из цикла над массивом.

---

Давайте посмотрим, как ваша идея (не) будет работать:

Я думаю, вы говорите о MIPS, где есть addiинструкция, которая ловит подписанное переполнение. (Вместо нормальногоaddiu который выполняет сложение без условной ловушки).

Большинство других ISA не имеют эффективного способа устранения подписанного переполнения. x86 имеетinto (установлено прерывание OF), но это отдельная инструкция от addкоторые могут устанавливать флаги. Вы также можете использовать условную ветвь вместо того, чтобы вызывать исключение и перехватывать его. Или просто используйтеdec ecx / jnz как счетчик цикла, или подсчитайте отрицательный индекс до нуля и индекс от конца массива.

Я думаю, что для MIPS потребуется дополнительная addi внутри цикла для выделенного счетчика: единственный режим адресации MIPS -reg+16_bit_constant.

Итак, если вы хотите перебрать массив, вам нужно приращение указателя, иначе вам понадобится дополнительный add tmp, base, index внутри петли.

Циклу нужна инструкция перехода или перехода внизу, и он может быть условным переходом практически без дополнительных затрат. Итак, в MIPS вы должны вычислить конец массива вне цикла, а затем написать обычный цикл, например

    addu   $t5, $t0, $t4     ; t5 = int *endp = start + byte_length
.loop:                       ; do{
    addiu  $t0, $t0, 4         ;  p++
    lw     $t1, ($t0)          ; *p
    ...
    bne    $t0, $t5, .loop    ; }while(p != endp)

Внутри цикла нет ненужных инструкций. Любую проверку границ массива можно выполнить вне цикла, проверив, чтоendp не более чем на один за концом массива.

(На современных x86 cmp/jneработает аналогично, декодируя до единственного мупа сравнения и перехода. Многие другие ISA имеют инструкции декремента и перехода или аналогичные инструкции, которые позволяют условиям цикла счетчика иметь только одну служебную инструкцию.)

i < array.length поскольку условие цикла - это не просто проверка границ массива.

Как я сказал выше, в простом цикле, который повторяет arr[i], вы выводите контрольную границу из цикла, чтобы она оставалась эффективной.