通过溢出中断实现循环边界检查

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 正在做类似的事情以避免在运行time 生成的代码中进行空检查。你认为这可行吗？或者这是否曾经被任何语言 considered/tried 淘汰运行time？

Answer 1

异常处理很慢;数组必须巨大才能分摊因错误而离开循环的额外成本，即使您可以在循环内保存一条指令。

您可能读到的内容是：使数组在虚拟页面的末尾结束，并且不映射下一页。如果发生越界异常，VM 会捕获 SIGSEGV 并向来宾代码传递异常。 这消除了对随机访问而不是循环访问的边界检查的需要。

此技术只会在访客代码实际发生数组边界异常时导致无效页面错误（段错误），不会正常情况下退出遍历一个数组。

让我们看看你的想法如何（不）起作用：

我认为您是在谈论 MIPS，其中有一条 addi 指令会捕获有符号溢出。（而不是在没有条件陷阱的情况下进行加法的正常 addiu）。

大多数其他 ISA 没有任何有效的方法来解决签名溢出问题。 x86 具有 into（设置了 OF 中断），但这是与可能设置标志的 add 不同的指令。您不妨使用条件分支而不是引发异常并捕获它。或者只使用 dec ecx / jnz 作为循环计数器，或者将负索引向上计数为零，并从数组末尾开始索引。

我认为 MIPS 需要一个额外的 addi inside 专用计数器循环：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 等效地工作，解码为单个比较和分支 uop。许多其他 ISA 具有递减和分支或类似指令，允许计数器循环条件仅具有一条指令的开销。)

i < array.length 因为循环条件不仅仅是数组边界检查。

正如我上面所说，在一个迭代 arr[i] 的简单循环中，您将边界检查提升到循环之外以保持其效率。

通过溢出中断实现循环边界检查

Implementing loop bounds check via overflow interrupt

arrays

assembly

runtime

interrupt

bounds-check-elimination

让我们看看你的想法如何（不）起作用：