rocq/theories/Single.v
Campaign 3's single-definition invariant over runs (docs/formal.md, Campaign 3; docs/rocq.md, The single-definition invariant).
The reuse forms' rules read relations between the values of names that have one definition each: a flight and its base, a proof and the pointer it checked, a span test or a limit and the pointer it read. Such a relation holds at a point of a run only where the name's definition dominates the point, and only while the definition's operands hold the values it read. This file states that for every frame of every run (sinv), and proves that every machine step keeps it (mreachable_sinv).
At a frame's point, each single definition whose site dominates the point replays (replays): the name holds what its instruction made in some earlier frame and memory, that frame agrees with the current environment on the instruction's single-definition operands, and the current memory persists from the memory the instruction left (Identity.v), which lay in the address space. A check that passed then passes again or traps; a flight's capability is its lower donor's.
Decisions
| Decision | Why |
|---|---|
| the relation is the instruction's own step, replayed | one statement covers every op; each reuse form reads off what it needs from inst_step |
| the operands a replay fixes are the single definitions | no_use_redefined (Sites.v) keeps exactly those; a name defined twice may change, and no reuse rule follows one |
a call and an alloc do not replay | their step is not one that continues; no reuse rule reads through them |
| a doomed frame claims nothing | its check_ahead did not pass; a doomed frame never returns to a caller or calls one |
| memory is handled once, for every step | each step's memory persists (mstep_persists), so the step lemmas carry frames and a replay's memory follows by scope_mem |
a replay keeps that the memory it left fit the address space (objects_fit) | the object of a check that passed then ended below 2^48; once the object is freed, the current memory no longer says where it ended |
free keeps identities by Runtime.v's axiom free_keeps_ids | mbrock's decision (docs/rocq.md, Identities persist) |
The invariant
The instructions a replay speaks of: a let that is not an alloc, and a flight. Their step continues and defines a name; a call's or an allocation's does not continue with a value, and no reuse rule reads through one.
The name n, defined by the instruction i, replays in the environment e and memory m: in some earlier frame fr0 and memory m0, i's step continued and gave n the value it has in e; fr0 agrees with e on i's single-definition operands (once being the function's single_definitions); and m persists from the memory m1 the step left, whose objects fit the address space (objects_fit).
The block and index of the point pt of f, as site_dominates/4 reads them: a block's entry is before its phis, at index -1; a snapshot has none.
At the point of the frame fr, each replayable single definition (the name n, defined by i at the site s) whose site dominates the point satisfies the property rp in fr's environment and the memory m. scope_holds takes replays for rp; scope_plain a weaker one.
At the point of the frame fr, each replayable single definition whose site dominates the point replays in fr's environment and the memory m: fr holds its scope.
The frame fr runs a function of the module md, at a point of a reachable block: a snapshot that leads to the entry, a block's entry (from no block only at the function's entry), or a suffix of a block's instructions before its jump.
The names a call's result r defines.
The frame fr is just after a call or raw call whose result is the pending result pd's: it waits for its callee to return.
The running frame fr is shaped and, unless doomed, holds its scope in the memory m.
Sites
Explore proof 12 tactics
Initial goal
intros f n s i H
unfold def_positions in H
apply in_app_or in H as H | H
2 open–apply in_map_iff in H as p & E & _
2 opendiscriminate E
–apply in_flat_map in H as b & _ & H
unfold block_positions in H
apply in_app_or in H as H | H
2 open+apply in_map_iff in H as d′ k′ pairs & E & _
2 opendiscriminate E
+destruct inst_positions_in_ _ _ _ _ _ H as k & i′ & _ & → & _
eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
One step on in a block: what dominates index k+1 is index k's instruction, or dominates index k.
Explore proof 13 tactics
Initial goal
intros doms l k s H
destruct s as | d j ; right ; reflexivity |
simpl in *
destruct name_eqbd l eqn: E ; | right ; exact H
apply Z.ltb_lt in H
destruct Z.eq_decj k as → | Hne
2 open–left
2 openapply name_eqb_true in E
2 opensubst
2 openreflexivity
–right
apply Z.ltb_lt
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction's site dominates a block's first instruction where it dominates the block's entry.
Explore proof 5 tactics
Initial goal
intros f doms l n s i Hp H
destruct dinst_site_ _ _ _ Hp as d & j & →
destruct position_inst_ _ _ _ _ Hp as b & kk & _ & _ & _ & → & _
simpl in *
destruct name_eqbd l ; apply Z.ltb_lt in H ; lia | exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Across an edge from a reachable block p: what dominates the entry of s dominated the end of p.
Explore proof 21 tactics
Initial goal
intros f b0 rest doms bp l n s i Hf Hd Hnd Hbp Hr Hl Hp H
destruct dinst_site_ _ _ _ Hp as d & j & →
destruct position_inst_ _ _ _ _ Hp as b & kk & Hb & Hlb & Hk & → & _
simpl in *
destruct name_eqbd l eqn: Edl ; apply Z.ltb_lt in H ; lia |
assert He : edgeb0 :: rest b_labelbp l
2 openfocused goal
{exists bp
2 opendeferred goal
rewrite <- Hf
2 opendeferred goal
split ; exact proj1find_block_in_ _ _ Hbp | auto
deferred goal
rewrite Hf in Hnd
destruct dom_edge_ _ _ Hd _ _ _ Hnd Hr He H as E | Hdp
2 openfocused goal
–subst d
2 opendeferred goal
apply name_eqb_false in Edl
2 opendeferred goal
contradiction
deferred goal
–destruct name_eqbd b_labelbp eqn: E ; | exact Hdp
apply name_eqb_true in E
rewrite <- Hf in Hnd
rewrite find_block_unique_ _ _ _ Hnd Hbp Hb eq_transHlb E in Hk
assert Hlt : kk < lengthb_instsbp%nat by apply nth_error_Some ; rewrite Hk ; discriminate
apply Z.ltb_lt
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
What a step changes in the environment
Putting d leaves the value of every name a not among d :: ds.
Explore proof 9 tactics
Initial goal
intros A a d v ds e H
rewrite lookup_put
destruct name_eqba d eqn: E ; | reflexivity
apply name_eqb_true in E
subst
exfalso
apply H
left
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction that continues changes only the names it defines (inst_temp_defs).
Explore proof 4 tactics
Initial goal
intros ge fr m i e1 l1 m1 H a Ha
destruct i
9 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
1: destruct special_leto eqn: Es ; destruct o ; try discriminate Es | rewrite inst_step_let_ _ _ _ _ _ _ Es in H
12 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
all: simpl in Ha ; unfold inst_step , external_call , bind_res , store_out in H ; cases H ; inversion H ; subst ; first reflexivity | exact lookup_put_not_ _ _ _ [ ] _ Ha
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An allocation's continuation changes only the names it defines.
Explore proof 5 tactics
Initial goal
intros ge fr m i q k H base a Ha
destruct i
9 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
1: destruct special_leto eqn: Es ; destruct o ; try discriminate Es | rewrite inst_step_let_ _ _ _ _ _ _ Es in H
12 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
all: simpl in Ha ; unfold inst_step , external_call , bind_res , store_out in H ; cases H ; inversion H ; subst
2 openfocused goal
all: first
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A fold of environment updates that starts from failure fails.
Explore proof 2 tactics
Initial goal
intros A g xs
induction xs ; simpl ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A fold of puts changes only the names it puts.
Explore proof 14 tactics
Initial goal
intros A key g xs a Hg
induction xs as | x xs IH ; simpl ; intros Ha e0 e H
2 openfocused goal
–injection H as ←
2 opendeferred goal
reflexivity
deferred goal
–destruct ge0 x as e1 | eqn: E ; | rewrite fold_env_none in H ; discriminate H
rewrite IHλHin ⇒ Haor_introrHin _ _ H
rewrite Hg_ _ _ E
destruct name_eqba keyx eqn: Ek ; | reflexivity
apply name_eqb_true in Ek
subst
exfalso
apply Ha
left
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The name a phi defines.
Putting d leaves the value of every other name a.
Explore proof 4 tactics
Initial goal
intros A a d v e H
apply lookup_put_not_ _ _ _ [ ]
intros E |
exact Heq_symE
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A block's phis change only the names they define.
Explore proof 19 tactics
Initial goal
intros ge phis from e0 e a H Ha
unfold phis_env in H
destruct from as pred | ; | destruct phis ; injection H as ← ; reflexivity | discriminate H
assert G : ∀ps acc e′, ¬Ina mapphi_name ps → ∀ea, acc = Someea → lookupa ea = lookupa e0 → fold_leftλacc ph ⇒ let* e ≔ acc in match ph with Phid k pairs ⇒ let* v ≔ lookuppred pairs in let* x ≔ value_xge e0 k v in Someputd x e end ps acc = Somee′ → lookupa e′ = lookupa e0
2 open{intros ps
2 openinduction ps as | d k pairs ps IH ; intros acc e1 Hn Hacc Hf ; simpl in Hf
3 open–exact Hacc_ Hf
2 open–eapply IH_ e1 λHin ⇒ Hnor_introrHin ; | exact Hf
2 openintros ea Ea
2 opendestruct acc as eb | ; | discriminate Ea
2 opensimpl in Ea
2 opendestruct lookuppred pairs as v | ; | discriminate Ea
2 opensimpl in Ea
2 opendestruct value_xge e0 k v ; | discriminate Ea
2 opensimpl in Ea
2 openinjection Ea as ←
2 openrewrite lookup_put_ne by intros → ; apply Hn ; left ; reflexivity
2 openexact Hacc_ eq_refl
apply Gphis Somee0 e Ha ; intros ea E ; injection E as ← ; reflexivity | exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call's result changes only the names it defines.
Explore proof 29 tactics
Initial goal
intros r o e e′ a H Ha
unfold returned_env in H
destruct o as x | xs | | | | | | ; destruct r as | d k | rs ; try discriminate H ; try injection H as ← ; reflexivity
2 openfocused goal
–destruct word_at_classk x ; | discriminate H
2 opendeferred goal
injection H as ←
2 opendeferred goal
apply lookup_put_ne
2 opendeferred goal
intros →
2 opendeferred goal
apply Ha
2 opendeferred goal
left
2 opendeferred goal
reflexivity
deferred goal
–destruct negb_ ; discriminate H |
assert G : ∀ps acc e′, ∀p, Inp ps → Infstfstp mapfst rs → ∀ea, acc = Someea → lookupa ea = lookupa e → fold_leftλacc rx ⇒ let* e ≔ acc in let* y ≔ word_at_classsndfstrx sndrx in Someputfstfstrx y e ps acc = Somee′ → lookupa e′ = lookupa e
2 openfocused goal
{intros ps
2 opendeferred goal
induction ps as | p ps IH ; intros acc e1 Hps Hacc Hf ; simpl in Hf
3 openfocused goal
deferred goal
–exact Hacc_ Hf
2 opendeferred goal
deferred goal
–eapply IH_ e1 λq Hq ⇒ Hpsq or_introrHq ; | exact Hf
2 opendeferred goal
intros ea Ea
2 opendeferred goal
destruct acc as eb | ; | discriminate Ea
2 opendeferred goal
simpl in Ea
2 opendeferred goal
destruct word_at_class_ _ ; | discriminate Ea
2 opendeferred goal
simpl in Ea
2 opendeferred goal
injection Ea as ←
2 opendeferred goal
rewrite lookup_put_ne by intros E ; apply Ha ; rewrite E ; exact Hpsp or_introleq_refl
2 opendeferred goal
exact Hacc_ eq_refl
deferred goal
apply Gcombiners xs Somee e′ ; | intros ea E ; injection E as ← ; reflexivity | exact H
intros n k y Hp
apply in_map_iff
exists n, k
split ; reflexivity | exact in_combine_l_ _ _ _ Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call's result names are the names it defines.
Explore proof 2 tactics
Initial goal
intros r cl args
destruct r ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
So are a raw call's.
Explore proof 2 tactics
Initial goal
intros r cl args
destruct r ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call's pending result is the call's.
Explore proof 4 tactics
Initial goal
intros ge fr m i g xs pd H
destruct i
9 openfocused goal
focused goal
focused goal
focused goal
focused goal
1: destruct special_leto eqn: Es ; destruct o ; try discriminate Es | rewrite inst_step_let_ _ _ _ _ _ _ Es in H
12 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
all: unfold inst_step , external_call , bind_res , store_out in H ; cases H ; inversion H ; subst ; simpl ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Points
Where dropping k elements of l, with k at most l's length, leaves nothing, k is l's length.
Explore proof 5 tactics
Initial goal
intros A k l H Hk
pose proof length_skipnk l as E
rewrite H in E
simpl in E
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The point k instructions into a block is at index k.
Explore proof 6 tactics
Initial goal
intros f l b k j Hb Hk
simpl
rewrite Hb , length_skipn
f_equal
f_equal
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Nothing is in scope at a function's entry.
Explore proof 12 tactics
Initial goal
intros md f l n s i Hmd Hin He Hp
destruct func_facts_ _ Hmd Hin as b0 & rest & Hf & Hd & _ & _
unfold entry_label in He
rewrite Hf in He
injection He as ←
destruct dinst_site_ _ _ _ Hp as d & j & →
destruct position_inst_ _ _ _ _ Hp as b & kk & _ & _ & _ & → & _
simpl
destruct name_eqbd b_labelb0 eqn: E ; apply Z.ltb_ge ; lia |
destruct dominatesfn_domsf d b_labelb0 eqn: Ed ; | reflexivity
rewrite dom_entry_top_ _ _ Hd _ Ed , name_eqb_refl in E
discriminate E
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A single definition's relation survives a step
A replay holds of any environment e' that agrees with e on the name n and its single-definition operands, in any memory m' that persists from m.
Explore proof 6 tactics
Initial goal
intros ge once e e′ m m′ n i fr0 & m0 & e1 & l1 & m1 & Hs & Hn & Ha & Hp & Hfit Hn′ Ha′ Hp′
exists fr0, m0, e1, l1, m1
split ; exact Hs |
split ; congruence |
split ; intros a Hu Ho ; rewrite Ha′_ Hu Ho ; exact Ha_ Hu Ho |
exact conjpersists_trans_ _ _ Hp Hp′ Hfit
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The property rp of a name survives what replays_change allows: an environment that keeps the name and its single-definition operands, and a memory that persists. The scope lemmas hold of any such rp.
A frame's scope of a property rp that moves holds in any memory m' that persists from m.
Explore proof 2 tactics
Initial goal
intros rp fr m m′ Hmv H Hp l k n s i Hpt Hn Hr Hpos Hsd
exact Hmv_ _ _ _ _ _ _ H_ _ _ _ _ Hpt Hn Hr Hpos Hsd eq_refl λ_ _ _ ⇒ eq_refl Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
So scope_holds holds in any memory that persists.
Explore proof 2 tactics
Initial goal
intros ge
exact λfr m m′ ⇒ scope_with_mem_ fr m m′ replays_changege
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The instruction i is not a check_ahead, whose result a doomed frame holds though its check did not pass.
Each single definition in scope at fr's point that is not a check_ahead replays. Guard chains, offset intervals and pointer distances read only such definitions.
A frame that holds its scope holds its plain scope.
Explore proof 2 tactics
Initial goal
intros ge fr m H l k n s i Hpt Hn Hr Hpos Hsd _
exact H_ _ _ _ _ Hpt Hn Hr Hpos Hsd
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The names X defined at index k of a reachable block l change neither a single definition n in scope there nor its single-definition operands: where the environment e' differs from e only on X, both read the same values. This rests on no_use_redefined.
Explore proof 18 tactics
Initial goal
intros f b0 rest l k X n s i e e′ Hf Hd Hdd Hr HX He Hn Hp Hs
split
2 openfocused goal
–apply He
2 opendeferred goal
intros Hin
2 opendeferred goal
destruct HX_ Hin as D HD
2 opendeferred goal
destruct once_position_ _ _ Hn as s0 & _ & Hu
2 opendeferred goal
destruct Hu_ _ HD as E1 _
2 opendeferred goal
destruct Hu_ _ Hp as E2 _
2 opendeferred goal
rewrite E2 , <- E1 in Hs
2 opendeferred goal
simpl in Hs
2 opendeferred goal
rewrite name_eqb_refl , Z.ltb_irrefl in Hs
2 opendeferred goal
discriminate Hs
deferred goal
–intros a Hu Ho
apply He
intros Hin
destruct HX_ Hin as D HD
destruct dinst_site_ _ _ _ Hp as d & j & →
exact no_use_redefined_ _ _ _ _ _ _ _ _ _ _ D Hf Hd Hdd Hn Hp Hr Hs HD Ho Hu
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction defines its names at its own index.
Explore proof 4 tactics
Initial goal
intros f b k i Hb Hk x Hx
apply in_map_iff in Hx as dk & ← & Hdk
exists DInsti
exact inst_position_ _ _ _ _ Hb Hk Hdk
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A block's phis define their names before its first instruction.
Explore proof 4 tactics
Initial goal
intros f b Hb x Hx
apply in_map_iff in Hx as d k pairs & ← & Hph
exists DPhiPhid k pairs
exact phi_position_ _ _ _ _ Hb Hph
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An instruction's single-definition operand is not one of the names it defines.
Explore proof 12 tactics
Initial goal
intros f b0 rest b k i a Hf Hd Hdd Hb Hr Hk Hu Ho Hin
unfold once_has in Ho
destruct lookupa single_definitionsf as D | eqn: Ea ; | discriminate Ho
destruct use_dominated_ _ _ _ _ _ _ Hdd Hb Hr Hk Hu Ea as s & Hs & Hsd
destruct inst_defs_here_ _ _ _ Hb Hk _ Hin as D′ HD′
destruct once_position_ _ _ Ea as s0 & _ & Hun
destruct Hun_ _ Hs as → _
destruct Hun_ _ HD′ as E _
rewrite <- E in Hsd
simpl in Hsd
rewrite name_eqb_refl , Z.ltb_irrefl in Hsd
discriminate Hsd
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Scope along a block
A shaped frame inside block l: its function is the module's, l is reachable, and its instructions are the suffix of l's block b from an index k, before b's jump.
Explore proof 5 tactics
The instruction at index k of block l is i.
Explore proof 7 tactics
Initial goal
intros md f l b k s n i′ Hmd Hin Hb Hp →
destruct func_facts_ _ Hmd Hin as _ & _ & _ & _ & Hnd & _
destruct position_inst_ _ _ _ _ Hp as b′ & kk & Hb′ & Hl & Hk & Ej & _
rewrite find_block_unique_ _ _ _ Hnd Hb Hb′ Hl in Hk
apply Nat2Z.inj in Ej
subst
exact Hk
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
From index k to k + 1 of block l, over the instruction i at k: where the next frame fr' differs from fr only on i's names and memory persists from m to m', a scope of a property rp that moves holds at fr' if it held at fr, provided i's own name satisfies rp when i is replayable.
Explore proof 16 tactics
Initial goal
intros rp md fr fr′ m m′ l b k i Hmv Hmd Hin Hf′ Hr Hb Hk Hpt0 Hpt1 He Hp Hself Hold l′ k′ n s i′ Hpt Hn Hrp Hpos Hsd
rewrite Hf′ in *
rewrite Hpt1 in Hpt
injection Hpt as ← ←
assert Hsd1 : site_dominatesfn_domsfr_fnfr l Z.of_natk + 1 s = true by rewrite <- Hsd ; f_equal ; lia
clear Hsd
destruct site_next_ _ _ _ Hsd1 as Es | Hsd0
2 openfocused goal
–pose proof site_inst_ _ _ _ _ _ _ _ Hmd Hin Hb Hpos Es as Hk′
2 opendeferred goal
rewrite Hk in Hk′
2 opendeferred goal
injection Hk′ as ←
2 opendeferred goal
exact Hself_ Hrp Hn
deferred goal
–destruct func_facts_ _ Hmd Hin as b0 & rest & Hf & Hd & _ & Hdd
destruct find_block_in_ _ _ Hb as Hbin Hl
assert HX : ∀x, Inx mapfst inst_temp_defsi → ∃D, Inx, SAtl Z.of_natk, D def_positionsfr_fnfr by intros x Hx ; rewrite <- Hl ; exact inst_defs_here_ _ _ _ Hbin Hk _ Hx
destruct scope_moves_ _ _ _ _ _ _ _ _ _ _ Hf Hd Hdd Hr HX He Hn Hpos Hsd0 as Hn′ Ha′
exact Hmv_ _ _ _ _ _ _ Hold_ _ _ _ _ Hpt0 Hn Hrp Hpos Hsd0 Hn′ Ha′ Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
scope_step_with for replays: the step lemma of scope_holds.
Explore proof 2 tactics
Initial goal
intros ge md fr fr′ m m′ l b k i
exact scope_step_withreplaysge md fr fr′ m m′ l b k i replays_changege
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Just after the instruction i at index k, whose own names do not replay (a call, an allocation), a frame whose environment changed only on i's names keeps the scope it had there, in a memory that persists.
Explore proof 16 tactics
Initial goal
intros ge md fr fr′ m m′ l b k i Hmd Hin Hf′ Ha′ Hr Hb Hk Hrp Hpt0 He Hp Hold l′ k′ n s i′ Hpt Hn Hrp′ Hpos Hsd
rewrite Hf′ in *
rewrite Ha′ , Hpt0 in Hpt
injection Hpt as ← ←
assert Hsd1 : site_dominatesfn_domsfr_fnfr l Z.of_natk + 1 s = true by rewrite <- Hsd ; f_equal ; lia
destruct site_next_ _ _ _ Hsd1 as Es | Hsd0
2 openfocused goal
–pose proof site_inst_ _ _ _ _ _ _ _ Hmd Hin Hb Hpos Es as Hk′
2 opendeferred goal
rewrite Hk in Hk′
2 opendeferred goal
injection Hk′ as ←
2 opendeferred goal
rewrite Hrp in Hrp′
2 opendeferred goal
discriminate Hrp′
deferred goal
–destruct func_facts_ _ Hmd Hin as b0 & rest & Hf & Hd & _ & Hdd
destruct find_block_in_ _ _ Hb as Hbin Hl
assert HX : ∀x, Inx mapfst inst_temp_defsi → ∃D, Inx, SAtl Z.of_natk, D def_positionsfr_fnfr by intros x Hx ; rewrite <- Hl ; exact inst_defs_here_ _ _ _ Hbin Hk _ Hx
destruct scope_moves_ _ _ _ _ _ _ _ _ _ _ Hf Hd Hdd Hr HX He Hn Hpos Hsd0 as Hn′ Ha′′
exact replays_change_ _ _ _ _ _ _ _ Hold_ _ _ _ _ Hpt0 Hn Hrp′ Hpos Hsd Hn′ Ha′′ Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Frames a step makes
What a jump can take is among the block's successors.
Explore proof 2 tactics
Initial goal
intros j t H
destruct j ; simpl in * ; intuition subst ; simpl ; auto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A call's new frame is not doomed, at its function's entry.
Explore proof 12 tactics
Initial goal
intros g xs fr H
unfold call_frame in H
destruct lengthxs <? lengthfn_paramsg%nat ; discriminate H |
unfold entry_label
destruct fn_blocksg as | b bs ; discriminate H |
injection H as ←
simpl
split ; reflexivity |
split ; reflexivity |
exists b_labelb
split ; reflexivity |
destruct variadic_funcg ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Explore proof 17 tactics
Initial goal
intros ge md fr m l Hmd Hin He Ha
destruct func_facts_ _ Hmd Hin as b0 & rest & Hf & Hd & _ & _
assert Hr : is_reachablefn_domsfr_fnfr l = true
2 openfocused goal
{unfold entry_label in He
2 opendeferred goal
rewrite Hf in He
2 opendeferred goal
injection He as ←
2 opendeferred goal
exact dom_entry_ _ _ Hd
deferred goal
split
2 openfocused goal
–unfold shaped
2 opendeferred goal
cbv zeta
2 opendeferred goal
split ; exact Hin |
2 opendeferred goal
destruct Ha as Ha | ys & Ha ; rewrite Ha ; split ; exact Hr | intros _ ; exact He | exact He
deferred goal
–intros l′ k n s i Hpt Hn Hrp Hpos Hsd
destruct Ha as Ha | ys & Ha ; rewrite Ha in Hpt ; simpl in Hpt ; | discriminate Hpt
injection Hpt as ← ←
rewrite scope_entry_ _ _ _ _ _ Hmd Hin He Hpos in Hsd
discriminate Hsd
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A return resumes the waiting caller at its point, with the call's result in its environment.
Explore proof 10 tactics
Initial goal
unfold return_step
intros c o c′ H
apply or_stuck_next in H
destruct invalidate_locals_ _ as m | ; | discriminate H
destruct c_callersc as | caller pd callers ; discriminate H |
destruct match pd_convpd with None ⇒ Someo Somecw, kw ⇒ converted_outcomecw kw o end as o′ | ; | discriminate H
destruct returned_env_ _ _ as e | eqn: Ee ; | discriminate H
injection H as ←
simpl
eauto 10
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A caller that waits resumes with its scope, in a memory that persists, the call's result names being the only ones that changed.
Explore proof 12 tactics
Initial goal
intros ge md fr e m m′ pd Hmd Hsh l & rest & j & b & k & ci & Ha & Hb & Hk & Hrest & Hci He Hp Hold
unfold shaped in Hsh
cbv zeta in Hsh
rewrite Ha in Hsh
destruct Hsh as Hin & Hr & _
assert Hlen : Sk ≤ lengthb_instsb%nat by apply nth_error_Some ; rewrite Hk ; discriminate
refine scope_after_ _ fr mkFramefr_fnfr e fr_localsfr fr_doomedfr fr_atfr _ _ _ _ _ ci Hmd Hin eq_refl eq_refl Hr Hb Hk _ _ _ Hp Hold
3 openfocused goal
focused goal
–destruct Hci as cl & args & → | cl & args & → ; reflexivity
2 opendeferred goal
deferred goal
–rewrite Ha , Hrest
2 opendeferred goal
exact point_site_exec_ _ _ _ _ Hb Hlen
deferred goal
–simpl
destruct Hci as cl & args & → | cl & args & → ; rewrite call_defs | rewrite raw_call_defs ; exact He
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Waiting callers keep their scope in a memory that persists.
Explore proof 4 tactics
Initial goal
intros ge md cs m m′ H Hp
eapply Forall_impl ; | exact H
intros fp Hs & Hd & Hw & Hsc
exact conjHs conjHd conjHw scope_mem_ _ _ _ Hsc Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The running frame keeps its scope in a memory that persists.
Explore proof 3 tactics
Initial goal
intros ge md fr m m′ Hs Hsc Hp
split ; exact Hs |
destruct Hsc as Hd | Hsc ; left ; exact Hd | right ; exact scope_mem_ _ _ _ Hsc Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
After an instruction, the frame is doomed, or it was not doomed and the instruction's result is its own.
Explore proof 6 tactics
Initial goal
intros ge fr m i out od H
destruct fr_doomedfr as w | eqn: Ew
2 open–left
2 openassert Hnd : fr_doomedfr ≠ None by rewrite Ew ; discriminate
2 openexact proj1doomed_result_doomed_ _ _ _ _ _ Hnd H
–destruct doomed_result_fresh_ _ _ _ _ _ Ew H as → | e & w & → ; right ; auto | left ; simpl ; discriminate
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Every step keeps the invariant
Explore proof 9 tactics
Initial goal
intros ge md c c′ xs l Hmd Ha Hs Hp Hsh _ Hcall
destruct step_snapshot_ _ _ _ _ Ha Hs as Hc & Hf & _ & _ & Ha′
unfold shaped in Hsh
cbv zeta in Hsh
rewrite Ha in Hsh
destruct Hsh as Hin He
rewrite <- Hf in Hin , He
destruct at_entryge _ _ c_memc′ _ Hmd Hin He or_introlHa′ as Hsh′ Hsc′
split ; split ; exact Hsh′ | right ; exact Hsc′ | rewrite Hc ; exact callers_mem_ _ _ _ _ Hcall Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Entering a block keeps sinv: its phis define their names at index -1, and its first instruction is at index 0.
Proof 29 steps Qed
A jump keeps sinv: it takes an edge, to the entry of a block whose dominators dominated the jump (site_edge); or it returns to a waiting caller, which resumes with its scope (scope_return).
Proof 41 steps Qed
An instruction keeps sinv: it continues, and its own name replays from where it ran; or it calls, the callee starting with nothing in scope and the caller waiting.
Proof 71 steps Qed
A step that allocates nothing keeps sinv, where memory persists across it and fits the address space after it.
Explore proof 6 tactics
Initial goal
intros ge md c c′ Hge Hmd Hs Hp Hfit H
destruct fr_atc_framec as xs l | l from | l | i rest j eqn: Ha
4 openfocused goal
focused goal
–exact next_sinv_snapshot_ _ _ _ _ _ Hmd Ha Hs Hp H
3 opendeferred goal
deferred goal
–exact next_sinv_enter_ _ _ _ _ _ Hmd Ha Hs Hp H
2 opendeferred goal
–exact next_sinv_jump_ _ _ _ _ _ Hmd Ha Hs Hp H
–exact next_sinv_inst_ _ _ _ _ _ _ _ Hge Hmd Ha Hs Hp Hfit H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An allocation keeps sinv: it defines names that do not replay, and memory persists across it.
Proof 49 steps Qed
Explore proof 2 tactics
Initial goal
intros ge md c m′ Hp Hrun Hcall
exact conjrunning_mem_ _ _ _ _ Hrun Hp callers_mem_ _ _ _ _ Hcall Hp
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Every machine step from a ready state keeps sinv, where the genv's free is R's, so keeps identities (mstep_persists).
Explore proof 7 tactics
Initial goal
intros ge md st st′ Hge Hmd Hfree Hr Hs H
pose proof mstep_persists_ _ _ Hfree Hr Hs as Hp
pose proof R.address_space_ _ mstep_ready_ _ _ Hfree Hs Hr as Hfit
destruct Hs as c c′ s E | c q k s base s′ E He Hal | c s s′ m′ Hd Hact ; simpl in *
3 openfocused goal
focused goal
–exact next_sinv_ _ _ _ Hge Hmd E Hp Hfit H
2 opendeferred goal
deferred goal
–exact fresh_sinv_ _ _ _ _ base Hmd E Hp H
deferred goal
–exact mem_sinv_ _ _ _ Hp H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
From a ready start where it holds, sinv holds in every state a run reaches.
Explore proof 4 tactics
Initial goal
intros ge md st st′ Hge Hmd Hfree H
induction H as st st′ Hs | st | st1 st2 st3 H12 IH1 H23 IH2 ; intros Hr Hi ; auto
2 openfocused goal
–eapply mstep_sinv ; eauto
deferred goal
–apply IH2 ; exact mreachable_ready_ _ _ Hfree H12 Hr | exact IH1Hr Hi
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
sinv holds where a run starts: at the entry of a checked module's function, with no caller.
Explore proof 5 tactics
Initial goal
intros ge md f xs fr m fuel Hmd Hin Hc
destruct call_frame_entry_ _ _ Hc as Hf & _ & l & He & Ha
rewrite <- Hf in Hin , He
destruct at_entryge md fr m l Hmd Hin He Ha as Hsh Hsc
split ; split ; exact Hsh | right ; exact Hsc | constructor
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
In every state of a run of a checked module's function that starts ready, sinv holds.
Explore proof 2 tactics
Initial goal
intros ge md f xs fr m fuel s0 st Hmd Hge Hfree Hin Hcf H0 Hreach
exact mreachable_sinv_ _ _ _ Hge Hmd Hfree Hreach H0 start_sinv_ _ _ _ _ _ _ Hmd Hin Hcf
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The interpreter's runtime
The same for the interpreter's runtime.
Under the interpreter's runtime, whose free keeps identities, sinv needs no hypothesis but a ready start.
Explore proof 2 tactics
Initial goal
intros md globals f xs fr m fuel s0 st ge Hmd Hin Hcf H0 Hreach
exact InterpSingle.run_sinvge md f xs fr m fuel s0 st Hmd eq_refl eq_refl Hin Hcf H0 Hreach
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.