assembly - 注册使用情况跟踪x86

Question

我有一个应用程序的汇编指令列表，我想知道哪些寄存器可以自由使用，哪些寄存器在列表的任何索引处都在使用。

我如何知道何时使用寄存器以及何时释放寄存器(可以再次使用)？我的目标是找到真正免费的寄存器。

这是我解决问题的假设，由于我对组装的了解有限，这听起来可能很愚蠢。

术语:读(源)，写(目标)

将每个指令的所有指令标记为WRITES TO或READS FROM(将http://ref.x86asm.net/coder32.html用于所有信息as described here)。

跟踪所有对寄存器的读写操作，并找出何时可以免费使用。例:

寄存器X由5处的指令写入。

正在通过8处的指令读取寄存器X。

寄存器X由15处的指令写入。

然后我可以说寄存器X在8-15之间没有被读取，而在15处没有被重新分配。这意味着它在指令8和15之间是空闲的，但在5-8之间却很忙。

它解决了问题还是有意义？我也欢迎其他解决方案。

评论后更新:

我看到JMPS /调用/条件移动将所有这些混乱了。只是为了确保安全(安全=空闲寄存器实际上是免费的)，该怎么做呢？当我看到每个跳转/调用/有条件的移动到外面时，我都会以悲观的态度将所有寄存器标记为“正在读取”哈罗德描述的假设。我相信在那种情况下，我会得到更安全的结果，即使由于大多数时候寄存器处于繁忙状态也不是一件好事。您是否能够同意我的结果将是安全的？

说明:

的指令为1:写入寄存器X。

的3指令:有条件的JMP / MOV / CALL。

在5处的指令:写入寄存器X。

在8处的指令:从寄存器X读取。

在15处的指令:写入寄存器X。

结果:

1-3之间:由于我将3以外的重定位计数为READ，所以寄存器X很忙。

3-5之间:寄存器X是免费的，因为不再读取。

在5-8之间:由于在8处有读操作，寄存器X忙。

在8-15之间:寄存器X是免费的。

更新2

我将应用程序分成几个基本块，其中每个块代表跳转(也是有条件的)，调用和返回之间的一小段代码。 jump语句将在该块的末尾。然后，假设开始时所有寄存器都在使用中，我将分析每个模块。我可能会错过很多免费的寄存器，但是当我得到一个免费的寄存器时，我会知道一个寄存器是一个真正的免费寄存器=)

更新3

我仍在尝试根据反馈改进解决方案(感谢harold)。

我已经阅读了 Activity 性分析，据我所知，建议从应用程序结束到开始进行分析。但是我不知道应用程序的结束在编译后的程序集中，正如下面的注释中提到的暂停问题一样，因此我将以其他方式处理将来的分支。

按照说明标记所有说明。读=源，写=目标。有条件的移动被视为对源的读取和对目标的写入。

将所有指令分成块。使用任何有条件或直接分支出口对其进行拆分。

将所有块彼此链接，每个块都有may_continue_with容器，该容器保存指向可能继续的分支的指针。

询问一个块，该寄存器X是否在A索引处空闲。块检查索引A之后对寄存器X的首次访问是否是读或写操作。首先，它检查自己的指令，如果找不到对寄存器进行任何操作的指令，则会向以后的分支询问相同的问题。 ( future 分支进一步询问它们是否也没有访问寄存器X的指令)。该块返回:

假(如果将来的任何分支机构具有读取访问权)

是，如果所有将来的分支都首先具有写访问权限(仅一个分支是不够的，因为我们不知道将执行哪个分支)。

Answer 1

第1步很容易，实际上需要完成很多工作(需要解析x86机器代码)，有些库可能对此有所帮助。

由于控制流程的原因，第2步并不像听起来那样容易。在控制流简单的假设下， Activity 性分析是一个众所周知的问题。在这种情况下，还有一些其他问题。

可以调用尚未确定其输入寄存器的过程。这主要是由于订购不当，深度优先处理程序减少了问题。但是由于(相互)递归，过程的顺序不一定一定不会出现此问题。您可以进行过程间活跃度分析来解决此问题。

可能会调用未知过程(虚拟方法或通过函数指针的显式调用)。我认为除了做出最大程度的悲观假设外，您无能为力。

即使是过程内控制流也可能是不可预测的，例如，将switch编译到跳转表时。实际上，不能保证变量跳转首先是过程间的，您可能可以大体上以为是。。我真的不知道该怎么办。

I'll then analyze the each block assuming that all of the registers are in use at the start.

这是一个巨大的浪费，只需执行适当的 liveness analysis即可轻松避免。