优化循环

循环是大多数程序中常用的结构。 因为循环通常要消耗大量的执行时间，因此有必要对时间要求严格的循环加以注意。

循环终止
如果在编写时未加注意，循环终止条件会造成显著的开销。 请尽可能：

始终编写计数递减到零的循环并使用简单终止条件

始终使用 unsigned int 类型的计数器，并且测试不等于零。

Table 5.1 显示了一个计算 n! 例程的两个示例执行，用于说明循环终止的开销。第一个执行使用递增循环计算 n!，第二个例程使用递减循环计算 n!。

Table 5.1. 递增和递减循环的 C 代码

递增循环 递减循环
int fact1(int n)
{
    int i, fact = 1;
    for (i = 1; i <= n; i++)
        fact *= i;
    return (fact);
}
int fact2(int n)
{
    unsigned int i, fact = 1;
    for (i = n; i != 0; i--)
        fact *= i;
    return (fact);
}




Table 5.2 是编译器为Table 5.1 中的每个示例实现生成的机器代码的反汇编，其中，两个示例实现的 C 代码均使用选项 -O2 -Otime 进行了编译。

Table 5.2. 递增和递减循环的 C 反汇编

递增循环 递减循环
fact1 PROC
    MOV      r2, r0
    MOV      r0, #1
    CMP      r2, #1
    MOV      r1, r0
    BXLT     lr
|L1.20|
    MUL      r0, r1, r0
    ADD      r1, r1, #1
    CMP      r1, r2
    BLE      |L1.20|
    BX       lr
    ENDP
fact2 PROC
    MOVS     r1, r0
    MOV      r0, #1
    BXEQ     lr
|L1.12|
    MUL      r0, r1, r0
    SUBS     r1, r1, #1
    BNE      |L1.12|
    BX       lr
ENDP




比较Table 5.2 的反汇编，可以看到，递增循环反汇编中有 ADD/CMP 指令对，而在递减循环反汇编中，则是一条 SUBS 指令。这是因为可以通过优化来去除与零的比较。

除了能节省循环中的指令外，变量 n 在循环中不需要保存，因此在递减循环反汇编中还节省了寄存器的使用。这有利于寄存器分配。

这种将循环计数器初始化为迭代所需的数字然后递减到零的技巧，也可以应用于 while 和 do 语句。

循环展开
展开小的循环虽然可以获得较高的性能，但缺点是会增加代码大小。 展开循环后，对循环计数器的更新次数减少，从而执行跳转的次数减少。如果循环只迭代数次，则可以完全展开，从而完全消除循环的开销。 ARM 编译器在使用 -O3 -Otime 时自动展开循环。否则，任何展开均必须在源代码中执行。

Note
手动展开循环可能会妨碍循环的自动重新展开和编译器的其他循环优化。

使用Table 5.3 中演示的两个示例例程可以说明循环展开的优缺点。两个例程均通过提取最低位并计数来高效测试单个位，在此之后将位移出。

第一个执行使用循环来对位计数。 第二个例程是第一个展开四次并通过将 n 的四次移位组合为一次优化后的结果。展开通常会提供新的优化机会。

Table 5.3. 未展开和展开的位计数循环的 C 代码

位计数循环 展开的位计数循环
int countbit1(unsigned int n)
{
    int bits = 0;
    while (n != 0)
    {
        if (n & 1) bits++;
        n >>= 1;
    }
    return bits;
}
int countbit2(unsigned int n)
{
    int bits = 0;
    while (n != 0)
    {
        if (n & 1) bits++;
        if (n & 2) bits++;
        if (n & 4) bits++;
        if (n & 8) bits++;
        n >>= 4;
    }
    return bits;
}




Table 5.4 是编译器为Table 5.3 中的每个示例实现生成的机器代码的反汇编，其中，每个实现的 C 代码均使用选项 -O2 进行了编译。

Table 5.4. 未展开和展开的位计数循环的反汇编

位计数循环 展开的位计数循环
countbit1 PROC
    MOV      r1, #0
    B        |L1.20|
|L1.8|
    TST      r0, #1
    ADDNE    r1, r1, #1
    LSR      r0, r0, #1
|L1.20|
    CMP      r0, #0
    BNE      |L1.8|
    MOV      r0, r1
    BX       lr
ENDP
countbit2 PROC
    MOV      r1, r0
    MOV      r0, #0
    B        |L1.48|
|L1.12|
    TST      r1, #1
    ADDNE    r0, r0, #1
    TST      r1, #2
    ADDNE    r0, r0, #1
    TST      r1, #4
    ADDNE    r0, r0, #1
    TST      r1, #8
    ADDNE    r0, r0, #1
    LSR      r1, r1, #4
|L1.48|
    CMP      r1, #0
    BNE      |L1.12|
    BX       lr
ENDP




在 ARM7 上，在左列所示的位计数循环的反汇编中，检查单个位要占用六个周期。 代码的大小仅为九个指令。 位计数循环的展开版本一次检查四位，平均每一位只占用三个周期。不过，开销是代码大小较大，有十五条指令。

Copyright &copy; 2002-2009 ARM Limited. All rights reserved. ARM DUI 0205IC
Non-Confidential, Unrestricted Access

受教了

路过。。。。。。。。