循环展开（带位运算）

Question

循环展开（带位运算）

clinux-kernelbit-manipulationloop-unrolling

6

我正在编写一个针对ARM的Linux内核驱动程序，并且在中断处理程序中需要检查中断位。

bit
 0/16  End point 0 In/Out interrupt
       (very likely, while In is more likely)
 1/17  End point 1 In/Out interrupt
 ...
15/31  End point 15 In/Out interrupt

请注意一次可以设置超过一个比特。

因此，这是代码：

int i;
u32 intr = read_interrupt_register();

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_in(i);
    }
    if(unlikely(intr & (1 << (i + 16)))){
        handle_ep_out(i);
    }
}

(1 << 0)和(1 << 16)可以在编译时计算，但是(1 << i)和(1 << (i + 16))则无法。此外，在循环中会有整数比较和加法。

由于这是一个中断处理程序，必须在最短的时间内完成工作。这让我想到是否需要稍微优化一下它。

可能的方法？

1. 拆分循环，似乎没有什么区别...

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_in(i);
    }
}
for(i=17;i<32;++i){
    if(unlikely(intr & (1 << i))){
        handle_ep_out(i - 16);
    }
}

2. 是否应该使用 intr，而不是要比较的值？

/* ep0 IN */
if(likely(intr & (1 << 0))){
    handle_ep0_in();
}

/* ep0 OUT */
if(likely(intr & (1 << 16))){
    handle_ep0_out();
}

for(i=1;i<16;++i){
    intr >>= 1;
    if(unlikely(intr & 1)){
        handle_ep_in(i);
    }
}
intr >>= 1;
for(i=1;i<16;++i){
    intr >>= 1;
    if(unlikely(intr & 1)){
        handle_ep_out(i);
    }
}

3. 完全展开循环（未显示）。这将使代码有点混乱。

4. 还有其他更好的方法吗？

5. 或者编译器实际上会生成最优化的方式？

编辑：我正在寻找一种告诉gcc编译器展开特定循环的方法，但根据我的搜索似乎不可能...

- Alvin Wong

你只需要处理17个元素。手动展开它并不比你第一个示例中的代码更混乱。 - fork0

2个回答

1

我个人会选择选项5。为了可读性编写代码，并让gcc的疯狂优化级别-O3尽其所能。

我曾经看到过在那个级别生成的代码，我甚至无法理解。

除了可能展开和使用常量而不是运行时位移（如选项3），C中的任何手工优化都不太可能超越编译器本身所能做的。

我认为你会发现展开可能并不像你想象的那么混乱：

if (  likely(intr & 0x00000001)) handle_ep0_in();
if (  likely(intr & 0x00010000)) handle_ep0_out();

if (unlikely(intr & 0x00000002)) handle_ep_in(1);
if (unlikely(intr & 0x00020000)) handle_ep_out(1);

:

if (unlikely(intr & 0x00008000)) handle_ep_in(15);
if (unlikely(intr & 0x80000000)) handle_ep_out(15);

实际上，您可以使用宏使其变得更加简洁（未经测试，但您应该能够理解基本思路）：

// Since mask is a constant, "mask << 32" should be too.

# define chkintr (mask, num) \
    if (unlikely(intr & (mask      ))) handle_ep_in  (num); \
    if (unlikely(intr & (mask << 32))) handle_ep_out (num);

// Special case for high probability bit.

if (likely(intr & 0x00000001UL)) handle_ep0_in();
if (likely(intr & 0x00010000UL)) handle_ep0_out();

chkintr (0x0002UL,  1);  chkintr (0x0004UL,  2);  chkintr (0x0008UL,  3);
chkintr (0x0010UL,  4);  chkintr (0x0020UL,  5);  chkintr (0x0040UL,  6);
chkintr (0x0080UL,  7);  chkintr (0x0100UL,  8);  chkintr (0x0200UL,  9);
chkintr (0x0400UL, 10);  chkintr (0x0800UL, 11);  chkintr (0x1000UL, 12);
chkintr (0x2000UL, 13);  chkintr (0x4000UL, 14);  chkintr (0x8000UL, 15);

唯一比那更高级的是手写汇编语言，但仍有很大可能性gcc会超过你 :-)

- paxdiablo

可能我有点过度担心了，因为这并不需要太多的时间，但我仍然不想欺骗自己 :P。此外，我认为Linux内核默认使用优化级别2进行构建。 - Alvin Wong

二级优化可能已经足够了。当然，内核中已经有一些具有相当严格时间要求的东西，因此也许 -O2 就足够了。-O3 可能会使内核调试变得非常困难。最重要的建议是，在你确定这是一个问题之前，不要担心这个问题。循环和展开形式都可能已经足够快了。 - paxdiablo

好的，让我们看看是否会有更多的答案。 - Alvin Wong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nils Pipenbrinck · Accepted Answer

如果我们可以假设intr中的位数较少（通常在中断掩码中是这种情况），那么我们就可以进行一些优化，编写一个仅执行每个位一次的循环：

void handle (int intr)
{
  while (intr)
  {
    // find index of lowest bit set in intr:
    int bit_id = __builtin_ffs(intr)-1;

    // call handler:
    if (bit_id > 16)
      handle_ep_out (bit_id-16);
    else
      handle_ep_in (bit_id);

    // clear that bit
    // (I think there was a bit-hack out there to simplify this step even further)
    intr -= (1<<bit_id);
  }
}

在大多数ARM架构中，__builtin_ffs将编译成CLZ指令和其周围的一些算术运算。除了ARM7和旧核心之外，它应该适用于任何东西。

另外：在嵌入式设备上编写中断处理程序时，函数的大小对性能也有影响，因为指令必须加载到代码缓存中。精简的代码通常执行更快。如果您保存对不太可能在缓存中的内存进行内存访问，则可以接受一些开销。