Relocation of real-RAM programs
DefinitionPNormRegLib_RelocConsider programs of the real RAM PNormReg_Machine. Fix parameters : a code offset , a register offset , a pointer offset , a base pointer register , a scratch pointer register and an exit label . The relocated copy of a program replaces each instruction by a pair :
- a memory access through pointer (real or integer, load or store) becomes , followed by the same access through ;
- a jump to position becomes the no-op , followed by the jump to ;
haltbecomes the no-op, followed by an unconditional jump to ;- every other instruction becomes the no-op, followed by the same instruction.
Throughout, real registers are renamed and pointer registers . Instruction of sits at positions and of .
A program embeds at offset if for every position of . An instruction is within the bounds if its real register indices are below and its pointer register indices below , and uses indices below if all its instructions are.
A relocated copy runs inside a larger program with its own registers, its own memory region (virtual address is real address , with set at run time) and a return point. Programs that are only known to exist can therefore be composed. Every step of costs exactly two steps of the copy, so time bounds transfer exactly.
Formalization Note. The no-op before a jump makes the taken and the untaken branch cost two steps each. accept and reject become the no-op followed by themselves; the machine is stuck at them in both programs.
import Mathlib
import Definitions.Def_PNormReg_Machine
namespace PNormRegLib
open PNormReg SmaleNinth
/-- Parameters of a relocated copy: code offset, register and pointer renaming offsets, the pointer
register holding the memory base, a scratch pointer register, and the exit label. -/
structure RelocParams where
/-- Position in the host program where the relocated copy starts. -/
cOff : ℕ
/-- Real register `i` of the copied program becomes register `roff + i`. -/
roff : ℕ
/-- Pointer register `q` of the copied program becomes pointer register `qoff + q`. -/
qoff : ℕ
/-- Pointer register holding the memory base: virtual address `z` is real address `base + z`. -/
base : ℕ
/-- Scratch pointer register for computed addresses. -/
tmp : ℕ
/-- Position in the host program to which the copied `halt` jumps. -/
exit : ℕ
namespace RelocParams
/-- `p[tmp] := p[tmp]`, a one-step no-op. -/
def noop (p : RelocParams) : Instr := .core (.pcopy p.tmp p.tmp)
/-- Each instruction becomes exactly two: a preparation (a no-op, or `tmp := q + base` before a
memory access) and the renamed instruction (jumps retargeted, accesses through `tmp`, `halt` turned
into a jump to `exit`). -/
def pair (p : RelocParams) : Instr → Instr × Instr
| .core (.const d c) => (p.noop, .core (.const (p.roff + d) c))
| .core (.add d i j) => (p.noop, .core (.add (p.roff + d) (p.roff + i) (p.roff + j)))
| .core (.sub d i j) => (p.noop, .core (.sub (p.roff + d) (p.roff + i) (p.roff + j)))
| .core (.mul d i j) => (p.noop, .core (.mul (p.roff + d) (p.roff + i) (p.roff + j)))
| .core (.div d i j) => (p.noop, .core (.div (p.roff + d) (p.roff + i) (p.roff + j)))
| .core (.load d q) => (.pointerAdd p.tmp (p.qoff + q) p.base, .core (.load (p.roff + d) p.tmp))
| .core (.store q i) => (.pointerAdd p.tmp (p.qoff + q) p.base, .core (.store p.tmp (p.roff + i)))
| .core (.pset q c) => (p.noop, .core (.pset (p.qoff + q) c))
| .core (.pcopy q q') => (p.noop, .core (.pcopy (p.qoff + q) (p.qoff + q')))
| .core (.pinc q) => (p.noop, .core (.pinc (p.qoff + q)))
| .core (.pdec q) => (p.noop, .core (.pdec (p.qoff + q)))
| .core (.jle i t) => (p.noop, .core (.jle (p.roff + i) (p.cOff + 2 * t)))
| .core (.pjle q q' t) => (p.noop, .core (.pjle (p.qoff + q) (p.qoff + q') (p.cOff + 2 * t)))
| .core .accept => (p.noop, .core .accept)
| .core .reject => (p.noop, .core .reject)
| .pointerAdd d a b => (p.noop, .pointerAdd (p.qoff + d) (p.qoff + a) (p.qoff + b))
| .pointerSub d a b => (p.noop, .pointerSub (p.qoff + d) (p.qoff + a) (p.qoff + b))
| .integerLoad d a => (.pointerAdd p.tmp (p.qoff + a) p.base, .integerLoad (p.qoff + d) p.tmp)
| .integerStore a b => (.pointerAdd p.tmp (p.qoff + a) p.base, .integerStore p.tmp (p.qoff + b))
| .pointerReal d a => (p.noop, .pointerReal (p.roff + d) (p.qoff + a))
| .sqrt d a => (p.noop, .sqrt (p.roff + d) (p.roff + a))
| .rpow d a b => (p.noop, .rpow (p.roff + d) (p.roff + a) (p.roff + b))
| .coin d => (p.noop, .coin (p.roff + d))
| .halt => (p.noop, .core (.pjle p.tmp p.tmp p.exit))
end RelocParams
/-- The relocated program: instruction `i` of `P` sits at positions `2i, 2i+1`. -/
def reloc (p : RelocParams) (P : Program) : Program :=
P.flatMap fun ins => [(p.pair ins).1, (p.pair ins).2]
/-- `B` occurs in `Q` starting at position `off`. -/
def Embeds (Q B : Program) (off : ℕ) : Prop := ∀ i x, B[i]? = some x → Q[off + i]? = some x
/-- Register indices of `ins` are below `nR` and pointer indices below `nQ`. -/
def InstrOK (nR nQ : ℕ) : Instr → Prop
| .core (.const d _) => d < nR
| .core (.add d i j) | .core (.sub d i j) | .core (.mul d i j) | .core (.div d i j) =>
d < nR ∧ i < nR ∧ j < nR
| .core (.load d q) => d < nR ∧ q < nQ
| .core (.store q i) => q < nQ ∧ i < nR
| .core (.pset q _) => q < nQ
| .core (.pcopy q q') => q < nQ ∧ q' < nQ
| .core (.pinc q) | .core (.pdec q) => q < nQ
| .core (.jle i _) => i < nR
| .core (.pjle q q' _) => q < nQ ∧ q' < nQ
| .core .accept | .core .reject => True
| .pointerAdd d a b | .pointerSub d a b => d < nQ ∧ a < nQ ∧ b < nQ
| .integerLoad d a => d < nQ ∧ a < nQ
| .integerStore a b => a < nQ ∧ b < nQ
| .pointerReal d a => d < nR ∧ a < nQ
| .sqrt d a => d < nR ∧ a < nR
| .rpow d a b => d < nR ∧ a < nR ∧ b < nR
| .coin d => d < nR
| .halt => True
/-- Every instruction of `P` uses register indices below `nR` and pointer indices below `nQ`. -/
def UsesBelow (P : Program) (nR nQ : ℕ) : Prop := ∀ ins ∈ P, InstrOK nR nQ ins
end PNormRegLib