问题标签 [register-allocation]

我遇到过“寄存器重新加载”这个术语，但我在网上找不到任何关于它的信息，除了它与寄存器溢出有关。我想我知道什么是溢出（当编译器的实时值多于可用的寄存器时，它必须将其中一些存储在内存中），但什么是重新加载？

目前我正在使用一个简单的代码生成器来输出类似汇编的语言。

背景：

我已经在使用寄存器分配器的一部分，但现在我需要处理诸如mul/之类的指令div，它有固定的寄存器作为输入：eax/ebx我不知道如何处理它，所以我正在寻找其他实现方式可以。我试过tcc。虽然代码很小，但我觉得有点难以理解。

注意：我的目标是 C/C++，因为它是我更熟悉的语言，但任何语言的实现都非常受欢迎。

我从来没有在汇编中写过任何长程序。但从我肤浅的经验来看，它似乎并不像人们想象的那么难。

我唯一不能完全理解的是：如何实际执行寄存器分配？虽然在 x86 中没有太多空间，但 x64 和 RISC 设计（AVR、ARM）为您提供了大量的寄存器。

汇编程序员如何选择哪些变量应该保留在寄存器中，何时将它们从/传输到内存，最后，他们如何跟踪每个变量？

当我gcc -O2用来优化我的程序时，gcc 会改变寄存器 RBP 的值。但我想将其保留为 FRAME BASE REGISTER，如何做到这一点？

与以下问题不同：GCC：禁止使用某些寄存器

我正在尝试使用 x86 进行简单的寄存器分配。我正在使用线性寄存器分配器，但我对一些我没有找到相关信息的简单事情有一些疑问。

对于这个简单的代码，忽略常量传播，g++ 和 msvc 生成类似的代码，将所有临时对象推送到堆栈上，然后仅将 eax、ebx 等用于 ALU 操作。Clang 使用 O0 生成以下代码。

很明显，所有临时对象都在堆栈上。所以我的问题是基于同样的事情。在任何时候，如果 eax/ebx 等中用于 add/mul/div 操作等的任何内容的生命周期都超过 1 条指令。也就是说，是否应该将任何生存范围间隔的值存储在这些寄存器中，或者是否应该在寄存器分配完成并将它们的值推送到临时对象后立即将它们逐出？

或者我们可以在遇到下一条 ALU 指令之前使用其中的一些寄存器，并在必要时进行延迟推入堆栈？

我的问题是，我应该使用什么算法来实现 translate根据以下 Python 示例工作的函数：

这是与在我拥有的编译器中生成最佳代码相关的问题的概括。该算法是我所追求的，因此解决方案不一定必须在 Python 中。在“现实”中，变量（'x'和'y'上面'z'的）是机器寄存器和字符串索引堆栈位置。

从示例中可以看出，该算法是关于使用最少的步骤将字符串从一个字符序列转换为另一个字符序列。需要注意的是，只有三种可能的操作可供选择：

1. 将字符串向左或向右移动 N 步。如果它向右移动，则引入的新索引将填充 ?字符。例如('S', 2)——将字符串向右移动两个索引。
2. 将索引处的字符读入变量。?如果字符串中有任何字符，则不能执行此操作。例如 ('R', 4, 'q')- 读取索引 4 处的字符并将其存储在变量中q。
3. 将变量中的字符写入目标字符串的索引。索引必须在范围内。例如——将字符写入字符串索引 0 处('W', 1, 'q')的变量中。q

这是实现这些操作的简单 Python 代码，以及如何手动执行从abto转换的示例：bab

这一系列步骤将对应于解决方案 [('R', 1, 'x'), ('S', 1), ('W', 0, 'x')]。

我觉得这个问题与编辑距离之间有一些相似之处，但我无法弄清楚。那你能帮我 写translate算法吗？

如果这个问题描述不够清楚，我会添加更多示例，但我希望如此。

在谈论寄存器分配时，关于编译的文本（例如，Cooper 的 Engineering a Compiler）经常提到存储在寄存器中的值需要是“安全的”——否则它们应该存储在内存中。

是什么使值不安全地保存在寄存器中？

编辑：书中的上下文：

“在内存到内存的模型中，分配器必须确定哪些值可以安全地保存在寄存器中——也就是说，哪些值是明确的。”

我能找到的信息最丰富的提及是“寄存器提升使用指针值的数据流分析来确定基于指针的值何时可以在整个循环嵌套中安全地保存在寄存器中，并重写代码以便将值保存在一个新引入的临时变量。”

所以要澄清这个问题：为什么指针值存储在寄存器中是不安全的，这是唯一一个值不能安全存储在寄存器中的情况吗？

我正在完成我的本科课程项目，包括对寄存器分配算法的实验分析。对于这个任务，我使用了 LLVM 项目中的工具集。

但是，我已经阅读了 LLVM 项目的文档，但还没有找到将拼图拼凑在一起的方法。到目前为止我知道：

• 由于通行证可以让他们参与 LLVM，并且知道我必须实施 MachineFunctionPass pass。
• 我按照一些建议来查看基本分配器代码，但不太了解。

我打算实现的分配器是基于图形着色启发式的，因为我很清楚这种方法的操作理论。

所以我寻找的是某种“如何”，一组定义的步骤来实现这种分配器。这听起来像是粗心大意，但我必须在大约六个月内完成工作，我有点困惑。

如果有人可以给我一些指导或参考任何支持材料（除了自己的文档），我将不胜感激。

我的英语可能有点不对，我是巴西学生。

我有几个关于寄存器分配的问题，特别是脏/干净/可重新实现的值。据我了解：脏值必须在使用前溢出并恢复；干净的值来自内存加载，只需从内存中恢复；并且可重新实现的值来自恒定负载，只需通过加载常量来恢复。我的问题是：

1）很容易确定一个值是否干净，但是我们如何确定它是从哪个内存位置加载的呢？我们知道哪个寄存器保存了内存位置，但该寄存器中的值可能会改变。我们是否仅将从固定位置或可重新实现的位置加载的东西视为干净的东西？

2）当然，商店可以弄脏一个干净的价值。如果 r0 是从内存位置 1024 加载的，并且我们刚刚存储到 1024，那么 r0 现在是脏的。更糟糕的是，那些我们没有溢出的寄存器呢，因为它们保持干净的值，现在被覆盖了？类似于以下序列。

1. 将内存 1024 中的值加载到 r0 中。
2. 用完物理寄存器，决定溢出 r0。由于它是干净的，我们不需要插入溢出代码。
3. 将值从 r1 存储到内存
4. 尝试恢复r0，但是现在内存中的值已经改变了。

我编写了一个简单的虚拟机，其中包含操作堆栈的指令，将堆栈值存储到寄存器中，将寄存器值加载到堆栈中，将值从寄存器移动到寄存器并设置寄存器值......我正在尝试编写一种非常简单的语言编译成这个 VM 字节码，我没有执行任何从地址跳转到地址的指令，但我觉得 VM 有足够的能力生成用于存储变量值的字节码。

虚拟机有 7 个寄存器：a、b、x、y、z、j 和 i。但是，如果我有 12 个包含简单整数的变量，我将如何将它们中的每一个存储在寄存器中？

我以前读过这个，很多时候人们都在谈论寄存器分配——我不知道如何在代码中实现它。我不确定我将如何开始，并且注册分配器似乎非常复杂。

我可以查看或尝试实现任何（真的）简单的寄存器分配器吗？任何人都可以为我简化解释，以便我可以尝试实施吗？

谢谢。