灵活的第二操作数

ARM加法指令中的立即数

最近在写编译器的时候，生成形如add sp, sp, #imm的arm汇编指令的时候经常报出立即数错误，然后查阅资料学习了一下。分享一下学习心得。

首先，arm中有这样一种指令：ADD Rd, Rn, #imm12，这种指令里面，可以使用12位的立即数，立即数范围为0-4095，但是，这种指令在arm状态下是不可用的，在Thumb状态下才可用。

在arm状态下，如果想加减一个立即数，使用的是这样的指令：ADD{S} Rd, Rn, Operand2。这里我们就需要关注一下arm中的第二操作数作为立即数时候能表示的范围。

灵活的第二操作数

上述说到的第二操作数在arm中的用法比较灵活，它可以作为：

• 立即数
• 寄存器
• 寄存器移位

这里我们重点说明第二操作数做立即数时候的表示机制和表示范围。

首先，第二操作数有12位，因此我们不难想到按照传统的表示方法，它最多也就表示0-4095的立即数。而为了进一步扩大第二操作数能表示的立即数范围，arm对其中的立即数的存储格式进行了改动。这12位的格式如下图所示。由4位的位移和8位的立即数组成。这里我们定义”>>”符号为循环右移，那么这12位实际表示的立即数就是$immediate>>(2*rotate)$

上述表达式比较书面的描述就是立即数是由一个8位的常数循环右移偶数位得到的。这里我们考虑这样设计的原因，rotate域为4位，那么它表示的范围为0-15，乘2之后可以表示0-30中的偶数，这也就是为什么是循环右移偶数位。同时，8位立即数最多可以循环右移30位，这就使得立即数能够表示的范围大大增加了(这里的范围不是指能表示的立即数的个数，而是大小)，不再只局限于0-4095了。但是我们进行思考，其实这种方式能够表示的立即数的个数是$2^8*2^4=2^{12}$，还是没变，只是能够表示更大的立即数了。

虽然可以表示更大的立即数了，但是显然，有些立即数是无法使用这个格式来表示的，那么如何判断一个立即数可以使用这种格式来合法的表示就成了我们写编译器的人的一个要解决的问题。我看网上有比较奇怪的方法来判断一个立即数可不可以被合法的表示。这里我们用比较简单的方法，下面我提出两种比较简单的方法来判断一个立即数是否可以用上述这种12位的方式来表示。

判断方法一

既然立即数是由8位立即数循环右移偶数位得到的，那么我们倒过来，对于一个立即数，我们将他循环左移偶数位，如果结果能够用8位来表示，那么表示这个立即数可以被合法表示。

代码如下：

bool isLegalImm(int imm)
{
    // 这里为啥要强制类型转换嘞，因为下边要用到右移，而对于有符号数右移，如果是负数，算数右移会在前边补1。
    // 无符号数右移就是逻辑右移
    unsigned int num = (unsigned int)imm;
    // 思路就是每次循环左移两位，看看结果是否可以用8位来表示了。
    for (int i = 0; i < 16; i++)
    {
        if (num <= 0xff)
        {
            return true;
        }
        num = ((num << 2) | (num >> 30));
    }
    return false;
}

(代码不保证对哦，但是思路应该没问题)

判断方法二

上边已经提到了，就算用arm里这种比较创新的表示方法，最多也就是表示$2^{12}$个立即数，一个立即数4个字节，那么存储所有合法立即数需要$2^{14}=16384$个字节，大约16KB的内存，如果我们内存资源不是很紧张的话，这里我们完全可以提前把所有能够合法表示的立即数给计算出来，存储到哈希表里，查的时候就会比较快。再次体现了空间和时间上的tradeoff。

这种方法就不写代码了，比较简单。可以用C++里的map很方便的实现。