3

嗯，不完全是。我有更多的功能数据结构问题。

假设我想对 CPU 的执行进行建模。我有一些改变 CPU 状态的指令（比如说它是一个基于堆栈的 cpu。只有跳转有操作数......或其他），一些构成程序的指令列表和标签。跳转是通过引用某个标签而不是某个偏移量来完成的。我如何表示这一点？

如果我有一个看起来像 的程序，[Label "foo", Add, Add, Mult, Label "bar", Jnz "foo"]当我点击 时Jnz "foo"，我需要前后搜索标签“foo”以继续执行。这似乎有点傻。我想我应该能够有一个更好的数据结构，允许快速跳转到标签。现在，我会任意说我不想存储偏移量。假设 CPU 允许自修改代码或类似的东西。我应该如何修补代码，同时确保引用仍然指向代码的当前版本？

我喜欢拉链的想法。我只是不知道在 O(1) 时间内让拉链跳转到预定义位置的想法是否有意义

4

2 回答 2

2

一个答案（但我不确定这是你想要的）是做 LLVM 所做的并将代码存储为BasicBlocks. 在这个系统中，每个块都是一段代码，只能从头开始输入。最后一条指令必须是跳转到另一个块。然后你的标签，而不是在指令列表中，被附加到基本块上。一个程序可能看起来像：

newtype Lable = [Char]
data Code = Data.Map Label [Instruction]

当您点击跳转指令时，您只需lookup将其阻挡在地图中并继续前进。

如果您的目标是优化代码（这也是 LLVM 使用它的原因），这具有一些真正的优势，但它确实打破了将代码简单地表示为指令列表的模式。

另一方面，我想不出任何在程序代码中包含标签的 CPU 或计算模型。在汇编中，它们只是描述下一行代码的固定偏移量的一种方便方式。它们不会出现在输出中，如果代码在运行时可修改，则jmp也需要修改指令。

于 2013-05-29T16:15:45.917 回答
1

我建议像

import Data.Map as M
data Code = Code { instructions :: [Instruction], labels :: M.Map String [Instruction] }

其中标签映射的值与指令列表共享。您可以将标签保留在指令流中并执行类似的操作

mkCode is = Code is (scan is)
              where scan [] = M.empty
                    scan (Label l:js) = M.insert l js (scan js)
                    scan (_:js) = (scan js)

建立适当的代码值。

注意Data.Map实现二叉搜索树。如果你想要一个哈希表，有Data.Hashtable.

于 2013-05-29T02:07:14.880 回答