没有间接寻址是否可以实现子程序？

Question

我正在研究 Deitel 的书 C how to program 中的 Simple-Compiler 项目。它的主要目标是为称为 SIMPLE 的高级语言生成编译器，相关的机器语言称为 SIMPLETRON。

我已经完成了这个编译器的一些基本功能，但现在遇到了一个增强的要求——实现 gosub 和 return（子程序特性）用于 SIMPLE 语言。

这里的主要障碍是 SIMPLETRON 不支持间接寻址，这意味着使用堆栈来 returning 子程序地址的策略不起作用。在这种情况下，是否有可能以某种方式使子程序工作？

PS: 我搜索了这个问题，发现了一个相关的问题here。似乎自修改代码可能是答案，但我没有找到具体的解决方案，所以我仍然提出这个问题。 此外，我认为必须扩展 SIMPLETRON 的机器指令才能使自修改代码在这里工作，对吗？

Background information for SIMPLETRON machine language:

It includes only one accumulator as register.

All supported machine instructions as below:

Input/output operations

#define READ 10: Read a word from the terminal into memory and with an operand as the memory address.

#define WRITE 11: Write a word from memory to the terminal and with an operand as the memory address.

Load/store operations

#define LOAD 20: Load a word from memory into the accumulator and with an operand as the memory address.

#define STORE 21: Store a word from the accumulator into memory and with an operand as the memory address.

Arithmetic operations

#define ADD 30: Add a word from memory to the word in the accumulator (leave result in accumulator) and with an operand as the memory address.

#define SUBTRACT 31: Subtract a word ...

#define DIVIDE 32: Divide a word ...

#define MULTIPLY 33: Multiply a word ...

Transfer of control operations

#define BRANCH 40: Branch and with an operand as the code location.

#define BRANCHNEG 41: Branch if the accumulator is negative and with an operand as the code location.

#define BRANCHZERO 42: Branch if the accumulator is zero and with an operand as the code location.

#define HALT 43: End the program. No operand.

Answer 1

我不熟悉 SIMPLE 或 SIMPLETRON，但总的来说我至少能想到 3 种方法。

自修改代码

在每个子程序的末尾都有一条BRANCH 0指令，在此之前，代码将return地址加载到累加器中，并将其STORE加载到代码本身中，因此有效地形成 BRANCH <dynamic> 指令。
潜在来电者的静态列表

如果 SIMPLE 没有间接调用（即每个 gosub 都针对一个静态已知的子例程），那么编译器会知道每个子例程的可能调用者列表。然后它可以让每个调用传递一个唯一的参数（例如在累加器中），子例程可以测试它（伪代码）：
```
SUBROUTINE:
...
if (arg == 0)
    branch CALLER_1;
if (arg == 1)
    branch CALLER_2;
if (arg == 2)
    branch CALLER_3;
```
内联

如果 SIMPLE 不允许递归子程序，则根本不需要在机器代码级别实现调用。只需将每个子例程完全内联到其调用者中即可。

Answer 2

虽然无法从 SIMPLE 指令集中获取当前指令的位置，但汇编器可以跟踪指令位置以生成等同于 return 的指令。

汇编程序会生成一个分支到程序映像中的寻址指令，用作 return 指令，然后为了实现调用，它会生成代码来加载 "return instruction" 并存储它在分支到该子例程之前的子例程结束处。 "call" 的每个实例都需要程序映像中的 "return instruction" 实例。你可能想预留一个范围的变量内存来存储这些 "return instructions".

示例 "code" 使用包含 return 指令标签作为参数的调用：

        call    sub1, sub1r
        ; ...
sub1:   ; ...
sub1r:  b       0              ;this is the return instruction

另一个选项类似于 MASM PROC 和 ENDP，其中 ENDP 将包含 return 指令。 call 指令将假定 endp 方向包含要修改的分支，并且标签将与相应的 proc 指令相同。

        call    sub1
        ; ...

sub1    proc                   ;subroutine entry point
        ; ...
sub1    endp                   ;subroutine end point, "return" stored here

这里的问题是累加器会被 "call" 破坏（但不受 "return" 的影响）。如果需要，子程序参数可以存储为变量，也许使用汇编程序指令进行标记：

sub1    parm1                  ;parameter 1 for sub1
        ;....
        load    sub1.parm1     ;load sub1 parameter 1

Answer 3

是的，您可以做到这一点，甚至是合理的，无需自修改代码。

你把你的 return 地址变成了一个巨大的案例陈述。秘诀在于理解 "return address" 只是一种方式回到通话点，那个记忆只是一个巨大的命名位置数组。

假设我有一个程序有很多逻辑调用位置，指令通话后标记为：

     CALL    S
 : ...
     ...
     CALL    T
 : ...
     ...
     CALL    U
 : ...

我们需要用我们的机器可以实现的东西替换 CALL。我们也暂时假设在任何时刻只有一个子程序调用处于活动状态。

那么重要的是，在子程序完成后，控制 returns到点后调用。

您可以通过编写以下 SIMPLETRON 代码（我正在编写语法）来实现这一点。按照惯例，我假设我有一堆内存位置 K1、K2、...，其中包含常量 1、2、.. 等，我需要多少常量。

 K1:  1
 K2:  2
 K3:  3
    ...
    LOAD   K1
    JMP    S
  : ...
     ...
    LOAD   K2
    JMP    T
  : ...
     ...
    LOAD   K3
    JMP    U
  :....

  S:  STORE RETURNID
     ...
     JMP  RETURN

  T:  STORE RETURNID
     ...
     JMP  RETURN

   U: STORE RETURNID
     ...
     JMP   RETURN

  RETURN:  LOAD RETURNID
     SUB    K1
     JE     
     LOAD   RETURNID
     SUB    K2
     JE     
     LOAD   RETURNID
     SUB    K3
     JE     
     JMP    *     ; bad return address, just hang

本质上，每个调用站点都记录了一个该调用站点唯一的常量 (RETURNID)，"RETURN" 逻辑使用该唯一 ID 计算出 return 点。如果你有很多子程序，return 逻辑代码可能会很长，但是嘿，这是一个玩具机器，我们对效率不那么感兴趣。您总是可以将 return 逻辑变成二叉决策树；然后代码可能很长，但只需要 log2(callcount) 来决定如何返回，实际上并不是那么糟糕。

让我们放宽对任何时刻只有一个子程序处于活动状态的假设。您可以为每个子例程定义一个RETURNID，但仍然使用相同的RETURN代码。有了这个想法，任何子程序都可以调用任何其他子程序。显然这些例程是不可重入的，所以它们在任何调用链中都不能被调用超过一次。

我们可以使用相同的想法来实现 return 堆栈。诀窍是认识到堆栈仅仅是一组内存位置，地址解码器可以挑选出堆栈的成员。所以，让我们实施 PUSH 和 POP 指令作为子程序。我们改变我们的调用约定使调用者记录 RETURNID，使累加器空闲传递一个值：

        LOAD   K1
        STORE  PUSHRETURNID
        LOAD   valuetopush
        JMP    PUSH
     :
        LOAD   K2
        STORE  POPRETURNID
        JMP    POP
     :...

     TEMP:
     STACKINDEX: 0   ; incremented to 1 on first use
     STACK1:  0      ; 1st stack location
     ...
     STACKN:  0

     PUSH:  STORE TEMP   ; save value to push
         LOAD PUSHRETURNID ; do this here once instead of in every exit
         STORE RETURNID
         LOAD STACKINDEX   ; add 1 to SP here, once, instead of in every exit
         ADD  K1
         STORE STACKINDEX
         SUB  K1
         JE   STORETEMPSTACK1
         LOAD STACKINDEX
         SUB  K2
         JE   STORETEMPSTACK2
         ...
         LOAD STACKINDEX
          SUB  Kn
         JE   STORETEMPSTACKn
         JMP   *           ; stack overflow

   STORETEMPSTACK1:
         LOAD   TEMP
         STORE  STACK1
         JMP    RETURN

   STORETEMPSTACK2:
         LOAD   TEMP
         STORE  STACK2
         JMP    RETURN

         ...

       POP:  LOAD   STACKINDEX
         SUB    K1        ; decrement SP here once, rather than in every exit
         STORE  STACKINDEX
         LOAD   STACKINDEX
         SUB    K0
         JE     LOADSTACK1   
         LOAD   STACKINDEX
         SUB    K1
         JE     LOADSTACK2
         ...
    LOADSTACKn:
         LOAD   STACKn
         JMP    POPRETURN

    LOADSTACK1:
         LOAD   STACK1
         JMP    RETURNFROMPOP

    LOADSTACK2:
         LOAD   STACK2
         JMP    RETURNFROMPOP

    RETURNFROMPOP: STORE TEMP
         LOAD   POPRETURNID
         SUB    K1
         JE     RETURNFROMPOP1
         LOAD   POPRETURNID
         SUB    K2
         JE     RETURNFROMPOP2
         ...

    RETURNFROMPOP1:  LOAD TEMP
         JMP    

    RETURNFROMPOP2:  LOAD TEMP
         JMP

请注意，我们需要 RETURN 来处理没有值的 return，以及 RETURNFROMPOP，它处理来自 POP 子例程 return 的 [=42] =]和一个值。

所以这些看起来很笨拙，但我们现在可以实现下推堆栈固定但任意大的深度。如果我们再次从堆栈位置和 returnID 检查中创建二叉决策树，运行时成本只是 stacks/call 计数大小的对数，这实际上相当不错。

好的，现在我们有了通用的 PUSH 和 POP 子程序。现在我们可以进行将 return 地址存储在堆栈上的调用：

        LOAD  K1   ; indicate return point
        STORE PUSHRETURNID
        LOAD  K2   ; call stack return point
        JMP   PUSH
     : LOAD argument  ; a value to pass to the subroutine
         JMP  RECURSIVESUBROUTINEX
        ; returns here with subroutine result in accumulator
     :

   RECURSIVESUBROUTINEX:
        ...compute on accumulator...
        LOAD  K3   ; indicate return point
        STORE PUSHRETURNID
        LOAD  K4   ; call stack return point
        JMP   PUSH
     : LOAD  ...  ; some revised argument
         JMP  RECURSIVESUBROUTINEX
     : ; return here with accumulator containing result
         STORE  RECURSIVESUBROUTINERESULT
         LOAD K5
         STORE POPRETURNID
         JMP   POP
     : ; accumulator contains return ID
         STORE  POPRETURNID
         LOAD  RECURSIVESUBROUTINERESULT
         JMP   RETURNFROMPOP

就是这样。现在你有了一个带有堆栈的完全递归子程序调用，没有（好吧，伪造的）间接寻址。

我不想手动对这台机器进行编程，因为构建 RETURN 例程对于编码和保持正确来说是一件非常头疼的事情。但是编译器会非常乐意制造所有这些东西。

没有间接寻址是否可以实现子程序？

Is it possible to realize subroutine without indirect addressing?

c

compiler-construction

subroutine