Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Invariant.v

Campaign 3's run-level evidence invariant, stated (docs/rocq.md, The evidence invariant over runs): what holds at each point of a frame of Machine R (Machine.v), and the lemmas each kind of step needs. Persistence.v proves that every step keeps it.

The invariant (inv) says that the running frame, unless a check_ahead doomed it, is at a point where the facts the evidence pass computed for that point hold (point_ok), and that every waiting caller has no fact (parked). It also says that each live fact's pointer has a single definition whose site dominates the point (live_dom), so that the reuse forms may read that pointer's definition.

From Stdlib Require Import String ZArith List Bool Lia
From Nanofil Require Import Term Maps Syntax Cfg Values Memory Runtime Ops Semantics Machine Validate Dominance Sites Coverage Evidence Walk Steps
Import ListNotations
Open Scope Z_scope

The live facts' pointers dominate

A fact names the pointer its check was of. The reuse forms read that pointer's single definition, so they need it to dominate the point where the fact is live (live_dom). This is a property of the pass alone, block by block: a check's pointer is an operand the check uses (definitions_dominate/3), and a fact that reaches a block's entry over every incoming edge has a pointer dominating each reachable predecessor's end, so the entry too (dom_meet).

A function f of a checked_module md is valid in the ways the proofs use: it has a first block, its dominator intervals (block_intervals) are its fn_doms, its block labels are distinct, and its definitions dominate their uses (definitions_dominate/3).

36Lemma func_facts
∀ md f
∃b0 rest, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true
Explore proof 15 tactics

Initial goal

⊢
∀md : module f : func, checked_modulemd → InIFuncf md → ∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

unfold checked_module , valid

⊢
∀ md : module f : func  ,
existsb
λ it : item  ⇒
match it with
⇒
true
_
⇒
false
md
→
None
else
=
Sometrue
∧
module_checkedmd = true
→
InIFuncf md → ∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

intros md f Hv _ Hin

md :
f :
Hv :
existsb
λ it : item  ⇒
match it with
⇒
true
_
⇒
false
md
→
None
else
=
Sometrue
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

destruct existsb_ md ; discriminate Hv |

md :
f :
Hv :
Somevalid_itemsmd = Sometrue
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

injection Hv as Hv

md :
f :
Hv :
valid_itemsmd = true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

unfold valid_items in Hv

md :
f :
Hv :
&&
forallb
λ it : item  ⇒
match it with
⇒
true
IDatan lk al its
⇒
valid_datamd n lk al its
IAliasn lk t
⇒
valid_aliasmd n lk t
md
=
true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

apply andb_true_iff in Hv as _ Hv

md :
f :
Hv :
forallb
λ it : item  ⇒
match it with
⇒
true
IDatan lk al its
⇒
valid_datamd n lk al its
IAliasn lk t
⇒
valid_aliasmd n lk t
md
=
true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

rewrite forallb_forall in Hv

md :
f :
Hv :
∀ x : item  ,
Inx md
→
match x with
⇒
true
IDatan lk al its
⇒
valid_datamd n lk al its
IAliasn lk t
⇒
valid_aliasmd n lk t
=
true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

specialize Hv_ Hin

md :
f :
Hv :
match IFuncf with
⇒
true
IDatan lk al its
⇒
valid_datamd n lk al its
IAliasn lk t
⇒
valid_aliasmd n lk t
=
true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

simpl in Hv

md :
f :
Hv :
valid_funcmd f = true
Hin :
InIFuncf md
⊢
∃b0 : block rest : listblock, fn_blocksf = b0 :: rest ∧ block_intervalsb0 :: rest = Somefn_domsf ∧ no_dupsmapb_label fn_blocksf = true ∧ definitions_dominatef fn_domsf = true

unfold valid_func , fn_doms in *

md :
f :
Hv :
match fn_blocksf with
[ ]
⇒
false
entry :: l
⇒
match block_intervalsentry :: l with
Somedoms
⇒
match fn_linkagef with
TAtom"weak" | TAtom"export" | TAtom"local"
⇒
true
_
⇒
false
&&
match fn_retf with
⇒
true
⇒
Datatypes.lengthks =? 2%nat && forallbλk : class ⇒ existsbclass_eqbk L; P; Single; Double ks
&&
&&
&&
&&
negbexistsbλb : block ⇒ memb_labelentry succ_labelsb_jumpb fn_blocksf
&&
&&
&&
&&
&&
negbmodule_checkedmd || stage_funcmd f doms
None
⇒
false
=
true
Hin :
InIFuncf md
⊢
∃ b0 : block rest : listblock  ,
fn_blocksf = b0 :: rest
∧
block_intervalsb0 :: rest
=
Some
Somedoms
⇒
doms
None
⇒
∧
∧
Somedoms
⇒
doms
None
⇒
=
true

destruct fn_blocksf as | b0 bs eqn: Eb ; discriminate Hv |

md :
f :
b0 :
bs :
listblock
Eb :
fn_blocksf = b0 :: bs
Hv :
match block_intervalsb0 :: bs with
Somedoms
⇒
match fn_linkagef with
TAtom"weak" | TAtom"export" | TAtom"local"
⇒
true
_
⇒
false
&&
match fn_retf with
⇒
true
⇒
Datatypes.lengthks =? 2%nat && forallbλk : class ⇒ existsbclass_eqbk L; P; Single; Double ks
&&
&&
no_dupsmapb_label b0 :: bs
&&
&&
negbexistsbλb : block ⇒ memb_labelb0 succ_labelsb_jumpb b0 :: bs
&&
&&
&&
&&
forallbvalid_blockmd f temp_defsf b0 :: bs
&&
negbmodule_checkedmd || stage_funcmd f doms
None
⇒
false
=
true
Hin :
InIFuncf md
⊢
∃ b1 : block rest : listblock  ,
b0 :: bs = b1 :: rest
∧
block_intervalsb1 :: rest
=
Some
match block_intervalsb0 :: bs with
Somedoms
⇒
doms
None
⇒
∧
no_dupsmapb_label b0 :: bs = true
∧
match block_intervalsb0 :: bs with
Somedoms
⇒
doms
None
⇒
=
true

destruct block_intervalsb0 :: bs as doms | eqn: Ed ; | discriminate Hv

md :
f :
b0 :
bs :
listblock
Eb :
fn_blocksf = b0 :: bs
doms :
nmapZ × Z
Ed :
block_intervalsb0 :: bs = Somedoms
Hv :
match fn_linkagef with
TAtom"weak" | TAtom"export" | TAtom"local"
⇒
true
_
⇒
false
&&
match fn_retf with
⇒
true
⇒
Datatypes.lengthks =? 2%nat && forallbλk : class ⇒ existsbclass_eqbk L; P; Single; Double ks
&&
&&
no_dupsmapb_label b0 :: bs
&&
&&
negbexistsbλb : block ⇒ memb_labelb0 succ_labelsb_jumpb b0 :: bs
&&
&&
&&
&&
forallbvalid_blockmd f temp_defsf b0 :: bs
&&
negbmodule_checkedmd || stage_funcmd f doms
=
true
Hin :
InIFuncf md
⊢
∃b1 : block rest : listblock, b0 :: bs = b1 :: rest ∧ block_intervalsb1 :: rest = Somedoms ∧ no_dupsmapb_label b0 :: bs = true ∧ definitions_dominatef doms = true

repeat match goal withHb : _ && _ = true |- _⇒apply andb_true_iff in Hb as ? ?end

md :
f :
b0 :
bs :
listblock
Eb :
fn_blocksf = b0 :: bs
doms :
nmapZ × Z
Ed :
block_intervalsb0 :: bs = Somedoms
H :
match fn_linkagef with
TAtom"weak" | TAtom"export" | TAtom"local"
⇒
true
_
⇒
false
=
true
H9 :
match fn_retf with
⇒
true
⇒
Datatypes.lengthks =? 2%nat && forallbλk : class ⇒ existsbclass_eqbk L; P; Single; Double ks
=
true
H8 :
negbextended_crossesf = true
H7 :
no_dupsmapb_label b0 :: bs = true
H5 :
negbexistsbλb : block ⇒ memb_labelb0 succ_labelsb_jumpb b0 :: bs = true
H4 :
H3 :
definitions_dominatef doms = true
H2 :
valid_localsf = true
H1 :
forallbvalid_blockmd f temp_defsf b0 :: bs = true
H0 :
negbmodule_checkedmd || stage_funcmd f doms = true
Hin :
InIFuncf md
⊢
∃b1 : block rest : listblock, b0 :: bs = b1 :: rest ∧ block_intervalsb1 :: rest = Somedoms ∧ no_dupsmapb_label b0 :: bs = true ∧ definitions_dominatef doms = true

exists b0, bs

md :
f :
b0 :
bs :
listblock
Eb :
fn_blocksf = b0 :: bs
doms :
nmapZ × Z
Ed :
block_intervalsb0 :: bs = Somedoms
H :
match fn_linkagef with
TAtom"weak" | TAtom"export" | TAtom"local"
⇒
true
_
⇒
false
=
true
H9 :
match fn_retf with
⇒
true
⇒
Datatypes.lengthks =? 2%nat && forallbλk : class ⇒ existsbclass_eqbk L; P; Single; Double ks
=
true
H8 :
negbextended_crossesf = true
H7 :
no_dupsmapb_label b0 :: bs = true
H5 :
negbexistsbλb : block ⇒ memb_labelb0 succ_labelsb_jumpb b0 :: bs = true
H4 :
H3 :
definitions_dominatef doms = true
H2 :
valid_localsf = true
H1 :
forallbvalid_blockmd f temp_defsf b0 :: bs = true
H0 :
negbmodule_checkedmd || stage_funcmd f doms = true
Hin :
InIFuncf md
⊢
b0 :: bs = b0 :: bs ∧ block_intervalsb0 :: bs = Somedoms ∧ no_dupsmapb_label b0 :: bs = true ∧ definitions_dominatef doms = true

auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros md f Hv _ Hin
destruct existsb_ md ; discriminate Hv |
injection Hv as Hv
unfold valid_items in Hv
apply andb_true_iff in Hv as _ Hv
rewrite forallb_forall in Hv
specialize Hv_ Hin
simpl in Hv
unfold valid_func , fn_doms in *
destruct fn_blocksf as | b0 bs eqn: Eb ; discriminate Hv |
destruct block_intervalsb0 :: bs as doms | eqn: Ed ; | discriminate Hv
repeat match goal withHb : _ && _ = true |- _⇒apply andb_true_iff in Hb as ? ?end
exists b0, bs
auto

Where the labels of the blocks bs are distinct, the block find_block finds for l is the only block of bs labelled l.

53Lemma find_block_unique
∀ bs l b b′
no_dupsmapb_label bs = true
find_blockl bs = Someb
Inb′ bs
b_labelb′ = l
b′ = b
Explore proof 14 tactics

Initial goal

⊢
∀bs : listblock l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b

induction bs as | b0 bs IH ; simpl ; intros l b b′ Hnd Hf Hin Hl ; discriminate Hf |

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hnd :
negbmemb_labelb0 mapb_label bs && no_dupsmapb_label bs = true
Hf :
→
Someb0
else
=
Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

apply andb_true_iff in Hnd as Hn Hnd

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
Hf :
→
Someb0
else
=
Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

destruct name_eqbb_labelb0 l eqn: E

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = true
Hf :
Someb0 = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b
focused goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

–injection Hf as ←

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = true
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b0
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

apply name_eqb_true in E

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b0
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

destruct Hin as → | Hin ; reflexivity |

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b0
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

exfalso

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
⊢
False
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

apply negb_true_iff in Hn

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
memb_labelb0 mapb_label bs = false
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
⊢
False
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

pose proof mem_false_ _ Hn b_labelb′ in_map_ _ _ Hin as Hne

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
memb_labelb0 mapb_label bs = false
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
Hne :
name_eqbb_labelb0 b_labelb′ = false
⊢
False
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

rewrite E , Hl in Hne

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
memb_labelb0 mapb_label bs = false
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
Hne :
name_eqbl l = false
⊢
False
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

apply name_eqb_false in Hne

2 open

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b′ :
Hn :
memb_labelb0 mapb_label bs = false
Hnd :
no_dupsmapb_label bs = true
E :
b_labelb0 = l
Hin :
Inb′ bs
Hl :
b_labelb′ = l
Hne :
l ≠ l
⊢
False
deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

exact Hneeq_refl

deferred goal
b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
b0 = b′ ∨ Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

–destruct Hin as → | Hin ; rewrite Hl in E ; apply name_eqb_false in E ; contradiction |

b0 :
bs :
listblock
IH :
∀l : name b b′ : block, no_dupsmapb_label bs = true → find_blockl bs = Someb → Inb′ bs → b_labelb′ = l → b′ = b
l :
b, b′ :
Hn :
negbmemb_labelb0 mapb_label bs = true
Hnd :
no_dupsmapb_label bs = true
E :
name_eqbb_labelb0 l = false
Hf :
find_blockl bs = Someb
Hin :
Inb′ bs
Hl :
b_labelb′ = l
⊢
b′ = b

exact IH_ _ _ Hnd Hf Hin Hl

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
induction bs as | b0 bs IH ; simpl ; intros l b b′ Hnd Hf Hin Hl ; discriminate Hf |
apply andb_true_iff in Hnd as Hn Hnd
destruct name_eqbb_labelb0 l eqn: E
–injection Hf as ←
apply name_eqb_true in E
destruct Hin as → | Hin ; reflexivity |
exfalso
apply negb_true_iff in Hn
pose proof mem_false_ _ Hn b_labelb′ in_map_ _ _ Hin as Hne
rewrite E , Hl in Hne
apply name_eqb_false in Hne
exact Hneeq_refl
–destruct Hin as → | Hin ; rewrite Hl in E ; apply name_eqb_false in E ; contradiction |
exact IH_ _ _ Hnd Hf Hin Hl

Where dropping k elements of l leaves x before rest, x is l's element at k, dropping k + 1 leaves rest, and k is below l's length.

68Lemma skipn_cons
∀ A : Type k l : listA x rest
skipnk l = x :: rest
nth_errorl k = Somex ∧ skipnSk l = rest ∧ Sk ≤ lengthl%nat
Explore proof 8 tactics

Initial goal

⊢
∀A : Type k : nat l : listA x : A rest : listA, skipnk l = x :: rest → nth_errorl k = Somex ∧ skipnSk l = rest ∧ Sk ≤ Datatypes.lengthl%nat

intros A k

A :
Type
k :
nat
⊢
∀l : listA x : A rest : listA, skipnk l = x :: rest → nth_errorl k = Somex ∧ skipnSk l = rest ∧ Sk ≤ Datatypes.lengthl%nat

induction k as | k IH ; intros l x rest H ; destruct l as | y l ; simpl in * ; try discriminate H

2 open

A :
Type
y :
A
l :
listA
x :
A
rest :
listA
H :
y :: l = x :: rest
⊢
Somey = Somex ∧ l = rest ∧ 1 ≤ SDatatypes.lengthl%nat
focused goal
A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
⊢
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

–injection H as → →

2 open

A :
Type
x :
A
rest :
listA
⊢
Somex = Somex ∧ rest = rest ∧ 1 ≤ SDatatypes.lengthrest%nat
deferred goal
A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
⊢
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

split ; reflexivity |

2 open

A :
Type
x :
A
rest :
listA
⊢
rest = rest ∧ 1 ≤ SDatatypes.lengthrest%nat
deferred goal
A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
⊢
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

split ; reflexivity | lia

deferred goal
A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
⊢
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

–destruct IH_ _ _ H as H1 & H2 & H3

A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
H1 :
nth_errorl k = Somex
H2 :
match l with
[ ]
⇒
[ ]
_ :: l
⇒
skipnk l
=
rest
H3 :
Sk ≤ Datatypes.lengthl%nat
⊢
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

split ; exact H1 |

A :
Type
k :
nat
IH :
∀ l : listA x : A rest : listA  ,
skipnk l = x :: rest
→
nth_errorl k = Somex
∧
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
Sk ≤ Datatypes.lengthl%nat
y :
A
l :
listA
x :
A
rest :
listA
H :
skipnk l = x :: rest
H1 :
nth_errorl k = Somex
H2 :
match l with
[ ]
⇒
[ ]
_ :: l
⇒
skipnk l
=
rest
H3 :
Sk ≤ Datatypes.lengthl%nat
⊢
match l with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
=
rest
∧
SSk ≤ SDatatypes.lengthl%nat

split ; exact H2 | lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros A k
induction k as | k IH ; intros l x rest H ; destruct l as | y l ; simpl in * ; try discriminate H
–injection H as → →
split ; reflexivity |
split ; reflexivity | lia
–destruct IH_ _ _ H as H1 & H2 & H3
split ; exact H1 |
split ; exact H2 | lia

A temporary among the values vs is among their temporaries (value_temps).

78Lemma value_temps_in
∀ vs a
InTmpa vs
Explore proof 5 tactics

Initial goal

⊢
∀vs : listvalue a : name, InTmpa vs → Ina value_tempsvs

intros vs a H

vs :
listvalue
a :
H :
InTmpa vs
⊢

unfold value_temps

vs :
listvalue
a :
H :
InTmpa vs
⊢
Ina
flat_map
λ v : value  ⇒
match v with
⇒
n
_
⇒
[ ]
vs

apply in_flat_map

vs :
listvalue
a :
H :
InTmpa vs
⊢
∃ x : value  ,
Inx vs
∧
Ina
match x with
⇒
n
_
⇒
[ ]

exists Tmpa

vs :
listvalue
a :
H :
InTmpa vs
⊢
InTmpa vs ∧ Ina a

split ; exact H | left ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros vs a H
apply in_flat_map
exists Tmpa
split ; exact H | left ; reflexivity

The single definition of each live fact's pointer (its P, where P is a temporary y with one definition) is at a site that dominates index k of block l of f (dominating).

84Definition facts_dominatef : func l : name k : Z live : listfact : Prop ≔
∀fa y, Infa live → f_pfa = Tmpy → once_hassingle_definitionsf y = true → dominatingf l k y

The same, where block l is reachable: what the reuse forms need of the live facts at index k of l.

90Definition live_domf : func l : name k : nat live : listfact : Prop ≔
is_reachablefn_domsf l = true → facts_dominatef l Z.of_natk live

A site that dominates index k of block l dominates every later index k' of l.

95Lemma site_dominates_mono
∀ doms l k k′ s
k ≤ k′
site_dominatesdoms l k s = true
site_dominatesdoms l k′ s = true
Explore proof 2 tactics

Initial goal

⊢
∀doms : nmapZ × Z l : name k k′ : Z s : site, k ≤ k′ → site_dominatesdoms l k s = true → site_dominatesdoms l k′ s = true

intros doms l k k′ | d j Hk H ; simpl in * ; reflexivity |

doms :
nmapZ × Z
l :
k, k′ :
Z
d :
j :
Z
Hk :
k ≤ k′
H :
→
j <? k
else
dominatesdoms d l
=
true
⊢
→
j <? k′
else
dominatesdoms d l
=
true

destruct name_eqbd l ; apply Z.ltb_lt in H ; apply Z.ltb_lt ; lia | exact H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros doms l k k′ | d j Hk H ; simpl in * ; reflexivity |
destruct name_eqbd l ; apply Z.ltb_lt in H ; apply Z.ltb_lt ; lia | exact H

So live facts that dominate index k of a block dominate every later index of it.

104Lemma live_dom_mono
∀ f l k k′ live
k ≤ k′%nat
live_domf l k live
live_domf l k′ live
Explore proof 7 tactics

Initial goal

⊢
∀f : func l : name k k′ : nat live : listfact, k ≤ k′%nat → live_domf l k live → live_domf l k′ live

intros f l k k′ live Hk H Hr fa y Hfa Hy Ho

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
⊢
dominatingf l Z.of_natk′ y

destruct HHr fa y Hfa Hy Ho as s & D & H1 & H2 & H3

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
s :
D :
H1 :
H2 :
Iny, s, D def_positionsf
H3 :
site_dominatesfn_domsf l Z.of_natk s = true
⊢
dominatingf l Z.of_natk′ y

exists s, D

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
s :
D :
H1 :
H2 :
Iny, s, D def_positionsf
H3 :
site_dominatesfn_domsf l Z.of_natk s = true
⊢
lookupy single_definitionsf = SomeD ∧ Iny, s, D def_positionsf ∧ site_dominatesfn_domsf l Z.of_natk′ s = true

split ; exact H1 |

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
s :
D :
H1 :
H2 :
Iny, s, D def_positionsf
H3 :
site_dominatesfn_domsf l Z.of_natk s = true
⊢
Iny, s, D def_positionsf ∧ site_dominatesfn_domsf l Z.of_natk′ s = true

split ; exact H2 |

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
s :
D :
H1 :
H2 :
Iny, s, D def_positionsf
H3 :
site_dominatesfn_domsf l Z.of_natk s = true
⊢
site_dominatesfn_domsf l Z.of_natk′ s = true

eapply site_dominates_mono ; | exact H3

f :
l :
k, k′ :
nat
live :
listfact
Hk :
k ≤ k′%nat
H :
live_domf l k live
Hr :
fa :
y :
Hfa :
Infa live
Hy :
f_pfa = Tmpy
s :
D :
H1 :
H2 :
Iny, s, D def_positionsf
H3 :
site_dominatesfn_domsf l Z.of_natk s = true
⊢
Z.of_natk ≤ Z.of_natk′

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros f l k k′ live Hk H Hr fa y Hfa Hy Ho
destruct HHr fa y Hfa Hy Ho as s & D & H1 & H2 & H3
exists s, D
split ; exact H1 |
split ; exact H2 |
eapply site_dominates_mono ; | exact H3
lia

The empty list of facts dominates every point.

111Lemma live_dom_nil
∀ f l k
live_domf l k [ ]
Explore proof 1 tactics

Initial goal

⊢
∀f : func l : name k : nat, live_domf l k [ ]

intros f l k _ fa y

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros f l k _ fa y

kill d keeps only facts it was given.

115Lemma kill_incl
∀ d fs fa
Infa killd fs
Infa fs
Explore proof 4 tactics

Initial goal

⊢
∀d : name fs : listfact fa : fact, Infa killd fs → Infa fs

unfold kill

⊢
∀d : name fs : listfact fa : fact, Infa filterλf : fact ⇒ negbname_eqbf_qf d || value_eqbf_pf Tmpd fs → Infa fs

intros d fs fa H

d :
fs :
listfact
fa :
H :
Infa filterλf : fact ⇒ negbname_eqbf_qf d || value_eqbf_pf Tmpd fs
⊢
Infa fs

apply filter_In in H

d :
fs :
listfact
fa :
H :
Infa fs ∧ negbname_eqbf_qfa d || value_eqbf_pfa Tmpd = true
⊢
Infa fs

exact proj1H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
unfold kill
intros d fs fa H
apply filter_In in H
exact proj1H

evidence_after keeps only facts it was given.

119Lemma evidence_after_incl
∀ i fs fa
Infa fs
Explore proof 4 tactics

Initial goal

⊢
∀i : inst fs : listfact fa : fact, Infa evidence_afteri fs → Infa fs

unfold evidence_after

⊢
∀ i : inst fs : listfact fa : fact  ,
Infa
→
match inst_def_firsti with
Somed
⇒
killd fs
None
⇒
fs
else
[ ]
→
Infa fs

intros i fs fa H

i :
fs :
listfact
fa :
H :
Infa
→
match inst_def_firsti with
Somed
⇒
killd fs
None
⇒
fs
else
[ ]
⊢
Infa fs

destruct evidence_preservingi ; | destruct H

i :
fs :
listfact
fa :
H :
Infa
match inst_def_firsti with
Somed
⇒
killd fs
None
⇒
fs
⊢
Infa fs

destruct inst_def_firsti ; exact kill_incl_ _ _ H | exact H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros i fs fa H
destruct evidence_preservingi ; | destruct H
destruct inst_def_firsti ; exact kill_incl_ _ _ H | exact H

The fact a check-like instruction i adds (check_fact) is of a pointer y that i uses.

128Lemma check_fact_uses
∀ i fa y
check_facti = Somefa
f_pfa = Tmpy
Explore proof 3 tactics

Initial goal

⊢
∀i : inst fa : fact y : name, check_facti = Somefa → f_pfa = Tmpy → Iny inst_usesi

intros i fa y H Hy

i :
fa :
y :
H :
check_facti = Somefa
Hy :
f_pfa = Tmpy
⊢

destruct i as q k o args | | | | | | | ; try discriminate H

q :
o :
args :
listvalue
fa :
y :
H :
check_factLetq k o args = Somefa
Hy :
f_pfa = Tmpy
⊢
Iny inst_usesLetq k o args

destruct k , o ; try discriminate H ; destruct args as | a1 | a2 | a3 | a4 args ; simpl in H ; try discriminate H ; injection H as ← ; simpl in Hy ; subst ; apply value_temps_in ; simpl ; auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros i fa y H Hy
destruct i as q k o args | | | | | | | ; try discriminate H
destruct k , o ; try discriminate H ; destruct args as | a1 | a2 | a3 | a4 args ; simpl in H ; try discriminate H ; injection H as ← ; simpl in Hy ; subst ; apply value_temps_in ; simpl ; auto

One step of the pass (checked_inst_rest) takes one instruction, or a check and its access, and keeps only facts it had or the check's own.

139Lemma pass_live_after
∀ s i rest live rest′ live′
checked_inst_rests i rest live = Somerest′, live′
rest′ = rest ∨ ∃a, rest = a :: rest′ ∧ ∀fa, Infa live′ → Infa live ∨ check_facti = Somefa
Explore proof 31 tactics

Initial goal

⊢
∀s : src i : inst rest : listinst live : listfact rest′ : listinst live′ : listfact, checked_inst_rests i rest live = Somerest′, live′ → rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ check_facti = Somefa

intros s i rest live rest′ live′ Hc

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ check_facti = Somefa

destruct check_facti as fa0 | eqn: Hf

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
fa0 :
Hf :
check_facti = Somefa0
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ Somefa0 = Somefa
focused goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

–destruct access_fact_some_ _ Hf as fb Hg

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
fa0 :
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ Somefa0 = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct checked_inst_rest_check_ _ _ _ _ _ _ _ Hf Hg Hc as access & → & _ & →

2 open

s :
i :
live :
listfact
rest′ :
listinst
access :
fa0 :
Hc :
checked_inst_rests i access :: rest′ live = Somerest′, evidence_afteraccess fa0 :: evidence_afteri live
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
⊢
rest′ = access :: rest′ ∨ ∃a : inst, access :: rest′ = a :: rest′ ∧ ∀fa : fact, Infa evidence_afteraccess fa0 :: evidence_afteri live → Infa live ∨ Somefa0 = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

split ; right ; eauto |

2 open

s :
i :
live :
listfact
rest′ :
listinst
access :
fa0 :
Hc :
checked_inst_rests i access :: rest′ live = Somerest′, evidence_afteraccess fa0 :: evidence_afteri live
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
⊢
∀fa : fact, Infa evidence_afteraccess fa0 :: evidence_afteri live → Infa live ∨ Somefa0 = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

intros fa Hfa

2 open

s :
i :
live :
listfact
rest′ :
listinst
access :
fa0 :
Hc :
checked_inst_rests i access :: rest′ live = Somerest′, evidence_afteraccess fa0 :: evidence_afteri live
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
fa :
Hfa :
Infa evidence_afteraccess fa0 :: evidence_afteri live
⊢
Infa live ∨ Somefa0 = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

apply evidence_after_incl in Hfa as ← | Hfa ; right ; reflexivity |

2 open

s :
i :
live :
listfact
rest′ :
listinst
access :
fa0 :
Hc :
checked_inst_rests i access :: rest′ live = Somerest′, evidence_afteraccess fa0 :: evidence_afteri live
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
fa :
Hfa :
Infa evidence_afteri live
⊢
Infa live ∨ Somefa0 = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

left

2 open

s :
i :
live :
listfact
rest′ :
listinst
access :
fa0 :
Hc :
checked_inst_rests i access :: rest′ live = Somerest′, evidence_afteraccess fa0 :: evidence_afteri live
Hf :
check_facti = Somefa0
fb :
Hg :
access_facti = Somefb
fa :
Hfa :
Infa evidence_afteri live
⊢
Infa live
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

exact evidence_after_incl_ _ _ Hfa

deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

–destruct is_check_locali eqn: Hcl

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
focused goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

+destruct i as q k o args | | | | | | | ; try discriminate Hcl

2 open

s :
q :
o :
args :
listvalue
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests Letq k o args rest live = Somerest′, live′
Hf :
check_factLetq k o args = None
Hcl :
is_check_localLetq k o args = true
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct k ; try discriminate Hcl ; destruct o ; try discriminate Hcl ; destruct args ; try discriminate Hcl

2 open

s :
q, x :
off, bytes :
Z
align :
Z
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests Letq A CheckLocalx off bytes r align [ ] rest live = Somerest′, live′
Hf :
check_factLetq A CheckLocalx off bytes r align [ ] = None
Hcl :
is_check_localLetq A CheckLocalx off bytes r align [ ] = true
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct checked_inst_rest_local_cov_ _ _ _ _ _ _ _ _ _ _ Hc as access & → & _ & →

2 open

s :
q, x :
off, bytes :
Z
align :
Z
live :
listfact
rest′ :
listinst
access :
Hc :
checked_inst_rests Letq A CheckLocalx off bytes r align [ ] access :: rest′ live = Somerest′, evidence_afteraccess killq live
Hf :
check_factLetq A CheckLocalx off bytes r align [ ] = None
Hcl :
is_check_localLetq A CheckLocalx off bytes r align [ ] = true
⊢
rest′ = access :: rest′ ∨ ∃a : inst, access :: rest′ = a :: rest′ ∧ ∀fa : fact, Infa evidence_afteraccess killq live → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

split ; right ; eauto |

2 open

s :
q, x :
off, bytes :
Z
align :
Z
live :
listfact
rest′ :
listinst
access :
Hc :
checked_inst_rests Letq A CheckLocalx off bytes r align [ ] access :: rest′ live = Somerest′, evidence_afteraccess killq live
Hf :
check_factLetq A CheckLocalx off bytes r align [ ] = None
Hcl :
is_check_localLetq A CheckLocalx off bytes r align [ ] = true
⊢
∀fa : fact, Infa evidence_afteraccess killq live → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

intros fa Hfa

2 open

s :
q, x :
off, bytes :
Z
align :
Z
live :
listfact
rest′ :
listinst
access :
Hc :
checked_inst_rests Letq A CheckLocalx off bytes r align [ ] access :: rest′ live = Somerest′, evidence_afteraccess killq live
Hf :
check_factLetq A CheckLocalx off bytes r align [ ] = None
Hcl :
is_check_localLetq A CheckLocalx off bytes r align [ ] = true
fa :
Hfa :
Infa evidence_afteraccess killq live
⊢
Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

left

2 open

s :
q, x :
off, bytes :
Z
align :
Z
live :
listfact
rest′ :
listinst
access :
Hc :
checked_inst_rests Letq A CheckLocalx off bytes r align [ ] access :: rest′ live = Somerest′, evidence_afteraccess killq live
Hf :
check_factLetq A CheckLocalx off bytes r align [ ] = None
Hcl :
is_check_localLetq A CheckLocalx off bytes r align [ ] = true
fa :
Hfa :
Infa evidence_afteraccess killq live
⊢
Infa live
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

exact kill_incl_ _ _ evidence_after_incl_ _ _ Hfa

deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

+destruct is_check_functioni eqn: Hcf

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
focused goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

∗destruct i as q k o args | | | | | | | ; try discriminate Hcf

2 open

s :
q :
o :
args :
listvalue
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests Letq k o args rest live = Somerest′, live′
Hf :
check_factLetq k o args = None
Hcl :
is_check_localLetq k o args = false
Hcf :
is_check_functionLetq k o args = true
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct k ; try discriminate Hcf ; destruct o ; try discriminate Hcf

2 open

s :
q :
args :
listvalue
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests Letq F CheckFunction args rest live = Somerest′, live′
Hf :
Hcl :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct checked_inst_rest_function_rest_ _ _ _ _ _ _ Hc as → & r & cargs & →

2 open

s :
q :
args :
listvalue
live :
listfact
rest′ :
listinst
cargs :
listarg
Hc :
checked_inst_rests Letq F CheckFunction args RawCallr Tmpq cargs :: rest′ live = Somerest′, [ ]
Hf :
Hcl :
⊢
rest′ = RawCallr Tmpq cargs :: rest′ ∨ ∃a : inst, RawCallr Tmpq cargs :: rest′ = a :: rest′ ∧ ∀fa : fact, Infa [ ] → Infa live ∨ None = Somefa
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

split ; right ; eauto | intros fa

deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

∗assert Hs′ : pass_speciali = false

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
⊢
pass_speciali = false
focused goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

{destruct pass_speciali eqn: Hp ; | reflexivity

2 open

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hp :
pass_speciali = true
⊢
true = false
deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct pass_special_cases_ Hp Hf as E | E ; congruence

deferred goal
s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

rewrite checked_inst_rest_generic_ _ _ _ Hs′ in Hc

s :
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hc :
generic_rests i rest live = Somerest′, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
⊢
rest′ = rest ∨ ∃a : inst, rest = a :: rest′ ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

destruct generic_rest_shape_ _ _ _ _ _ Hc as → & Hlive & _

s :
i :
rest :
listinst
live, live′ :
listfact
Hc :
generic_rests i rest live = Somerest, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
Hlive :
live′ = evidence_afteri live ∨ ∃d g : name, i = Letd P Copy Globalg ∧ live′ = killd live
⊢
rest = rest ∨ ∃a : inst, rest = a :: rest ∧ ∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

split ; left ; reflexivity |

s :
i :
rest :
listinst
live, live′ :
listfact
Hc :
generic_rests i rest live = Somerest, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
Hlive :
live′ = evidence_afteri live ∨ ∃d g : name, i = Letd P Copy Globalg ∧ live′ = killd live
⊢
∀fa : fact, Infa live′ → Infa live ∨ None = Somefa

intros fa Hfa

s :
i :
rest :
listinst
live, live′ :
listfact
Hc :
generic_rests i rest live = Somerest, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
Hlive :
live′ = evidence_afteri live ∨ ∃d g : name, i = Letd P Copy Globalg ∧ live′ = killd live
fa :
Hfa :
Infa live′
⊢
Infa live ∨ None = Somefa

left

s :
i :
rest :
listinst
live, live′ :
listfact
Hc :
generic_rests i rest live = Somerest, live′
Hf :
check_facti = None
Hcl :
is_check_locali = false
Hcf :
Hs′ :
pass_speciali = false
Hlive :
live′ = evidence_afteri live ∨ ∃d g : name, i = Letd P Copy Globalg ∧ live′ = killd live
fa :
Hfa :
Infa live′
⊢
Infa live

destruct Hlive as → | d & g & _ & → ; exact evidence_after_incl_ _ _ Hfa | exact kill_incl_ _ _ Hfa

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros s i rest live rest′ live′ Hc
destruct check_facti as fa0 | eqn: Hf
–destruct access_fact_some_ _ Hf as fb Hg
destruct checked_inst_rest_check_ _ _ _ _ _ _ _ Hf Hg Hc as access & → & _ & →
split ; right ; eauto |
intros fa Hfa
apply evidence_after_incl in Hfa as ← | Hfa ; right ; reflexivity |
left
exact evidence_after_incl_ _ _ Hfa
–destruct is_check_locali eqn: Hcl
+destruct i as q k o args | | | | | | | ; try discriminate Hcl
destruct k ; try discriminate Hcl ; destruct o ; try discriminate Hcl ; destruct args ; try discriminate Hcl
destruct checked_inst_rest_local_cov_ _ _ _ _ _ _ _ _ _ _ Hc as access & → & _ & →
split ; right ; eauto |
intros fa Hfa
left
exact kill_incl_ _ _ evidence_after_incl_ _ _ Hfa
+destruct is_check_functioni eqn: Hcf
∗destruct i as q k o args | | | | | | | ; try discriminate Hcf
destruct k ; try discriminate Hcf ; destruct o ; try discriminate Hcf
destruct checked_inst_rest_function_rest_ _ _ _ _ _ _ Hc as → & r & cargs & →
split ; right ; eauto | intros fa
∗assert Hs′ : pass_speciali = false
{destruct pass_speciali eqn: Hp ; | reflexivity
destruct pass_special_cases_ Hp Hf as E | E ; congruence
rewrite checked_inst_rest_generic_ _ _ _ Hs′ in Hc
destruct generic_rest_shape_ _ _ _ _ _ Hc as → & Hlive & _
split ; left ; reflexivity |
intros fa Hfa
left
destruct Hlive as → | d & g & _ & → ; exact evidence_after_incl_ _ _ Hfa | exact kill_incl_ _ _ Hfa

In a block b of a function f of a checked module md, where the facts before the pass's step at index k dominate k, the facts after it dominate index k + 1: a check's own fact is of an operand it uses, whose single definition dominates it (use_dominated).

174Lemma pass_step_dom
∀ md f b k i rest live rest′ live′
InIFuncf md
nth_errorb_instsb k = Somei
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
live_domf b_labelb k live
live_domf b_labelb Sk live′
Explore proof 12 tactics

Initial goal

⊢
∀md : module f : func b : block k : nat i : inst rest : listinst live : listfact rest′ : listinst live′ : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → nth_errorb_instsb k = Somei → checked_inst_restfn_srcmd f i rest live = Somerest′, live′ → live_domf b_labelb k live → live_domf b_labelb Sk live′

intros md f b k i rest live rest′ live′ Hmd Hin Hb Hk Hc H Hr fa y Hfa Hy Ho

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
⊢
dominatingf b_labelb Z.of_natSk y

destruct proj2pass_live_after_ _ _ _ _ _ Hc fa Hfa as Hl | Hf

2 open

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
Hl :
Infa live
⊢
dominatingf b_labelb Z.of_natSk y
focused goal
md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
Hf :
check_facti = Somefa
⊢
dominatingf b_labelb Z.of_natSk y

–exact live_dom_mono_ _ _ _ _ le_S_ _ le_nk H Hr fa y Hl Hy Ho

deferred goal
md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
Hf :
check_facti = Somefa
⊢
dominatingf b_labelb Z.of_natSk y

–destruct func_facts_ _ Hmd Hin as _ & _ & _ & _ & _ & Hdd

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
Hf :
check_facti = Somefa
⊢
dominatingf b_labelb Z.of_natSk y

unfold once_has in Ho

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
Ho :
Some_
⇒
true
None
⇒
false
=
true
Hf :
check_facti = Somefa
⊢
dominatingf b_labelb Z.of_natSk y

destruct lookupy single_definitionsf as D | eqn: Ey ; | discriminate Ho

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
⊢
dominatingf b_labelb Z.of_natSk y

destruct use_dominated_ _ _ _ _ _ _ Hdd Hb Hr Hk check_fact_uses_ _ _ Hf Hy Ey as s & Hs & Hsd

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
s :
Hs :
Iny, s, D def_positionsf
Hsd :
site_dominatesfn_domsf b_labelb Z.of_natk s = true
⊢
dominatingf b_labelb Z.of_natSk y

exists s, D

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
s :
Hs :
Iny, s, D def_positionsf
Hsd :
site_dominatesfn_domsf b_labelb Z.of_natk s = true
⊢
lookupy single_definitionsf = SomeD ∧ Iny, s, D def_positionsf ∧ site_dominatesfn_domsf b_labelb Z.of_natSk s = true

split ; exact Ey |

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
s :
Hs :
Iny, s, D def_positionsf
Hsd :
site_dominatesfn_domsf b_labelb Z.of_natk s = true
⊢
Iny, s, D def_positionsf ∧ site_dominatesfn_domsf b_labelb Z.of_natSk s = true

split ; exact Hs |

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
s :
Hs :
Iny, s, D def_positionsf
Hsd :
site_dominatesfn_domsf b_labelb Z.of_natk s = true
⊢
site_dominatesfn_domsf b_labelb Z.of_natSk s = true

eapply site_dominates_mono ; | exact Hsd

md :
f :
k :
nat
i :
rest :
listinst
live :
listfact
rest′ :
listinst
live′ :
listfact
Hin :
InIFuncf md
Hb :
Hk :
nth_errorb_instsb k = Somei
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
H :
live_domf b_labelb k live
fa :
y :
Hfa :
Infa live′
Hy :
f_pfa = Tmpy
D :
Ey :
Ho :
true = true
Hf :
check_facti = Somefa
s :
Hs :
Iny, s, D def_positionsf
Hsd :
site_dominatesfn_domsf b_labelb Z.of_natk s = true
⊢
Z.of_natk ≤ Z.of_natSk

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros md f b k i rest live rest′ live′ Hmd Hin Hb Hk Hc H Hr fa y Hfa Hy Ho
destruct proj2pass_live_after_ _ _ _ _ _ Hc fa Hfa as Hl | Hf
–exact live_dom_mono_ _ _ _ _ le_S_ _ le_nk H Hr fa y Hl Hy Ho
–destruct func_facts_ _ Hmd Hin as _ & _ & _ & _ & _ & Hdd
unfold once_has in Ho
destruct lookupy single_definitionsf as D | eqn: Ey ; | discriminate Ho
destruct use_dominated_ _ _ _ _ _ _ Hdd Hb Hr Hk check_fact_uses_ _ _ Hf Hy Ey as s & Hs & Hsd
exists s, D
split ; exact Ey |
split ; exact Hs |
eapply site_dominates_mono ; | exact Hsd
lia

The pass's facts at a block's end (checked_insts walking the block from index k) dominate the end, where those it started with dominated k.

192Lemma walk_dom
∀ md f b n k is live out
InIFuncf md
is = skipnk b_instsb
k ≤ lengthb_instsb%nat
live_domf b_labelb k live
checked_instsfn_srcmd f n is live = Someout
live_domf b_labelb lengthb_instsb out
Explore proof 10 tactics

Initial goal

⊢
∀md : module f : func b : block n k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out

intros md f b n

md :
f :
n :
nat
⊢
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out

induction n as | n IH ; intros k is live out Hmd Hin Hb Hs Hk H Hc ; destruct is as | i rest ; cbn [ checked_insts ] in Hc ; injection Hc as ← ; exact live_dom_mono_ _ _ _ _ Hk H | ; discriminate Hc |

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
Hc :
let* rl ≔ checked_inst_restfn_srcmd f i rest live in
checked_instsfn_srcmd f n fstrl sndrl
=
Someout
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

destruct checked_inst_rest_ i rest live as rest′ live′ | eqn: Ec ; | discriminate Hc

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
rest′ :
listinst
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n fstrest′, live′ sndrest′, live′ = Someout
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

simpl in Hc

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
rest′ :
listinst
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

destruct skipn_cons_ _ _ _ _ eq_symHs as Hki & Hrest & Hlen

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
rest′ :
listinst
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = rest
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hb Hki Ec H as H1

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
rest′ :
listinst
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = rest
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
H1 :
live_domf b_labelb Sk live′
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

destruct proj1pass_live_after_ _ _ _ _ _ Ec as → | a & →

2 open

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
rest :
listinst
live, out :
listfact
Hin :
InIFuncf md
Hb :
Hs :
i :: rest = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
live′ :
listfact
Hc :
checked_instsfn_srcmd f n rest live′ = Someout
Ec :
checked_inst_restfn_srcmd f i rest live = Somerest, live′
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = rest
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
H1 :
live_domf b_labelb Sk live′
⊢
live_domf b_labelb Datatypes.lengthb_instsb out
focused goal
md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
live, out :
listfact
Hin :
InIFuncf md
Hb :
rest′ :
listinst
a :
Hs :
i :: a :: rest′ = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i a :: rest′ live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = a :: rest′
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
H1 :
live_domf b_labelb Sk live′
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

–exact IH_ _ _ _ Hmd Hin Hb eq_symHrest Hlen H1 Hc

deferred goal
md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
live, out :
listfact
Hin :
InIFuncf md
Hb :
rest′ :
listinst
a :
Hs :
i :: a :: rest′ = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i a :: rest′ live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = a :: rest′
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
H1 :
live_domf b_labelb Sk live′
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

–destruct skipn_cons_ _ _ _ _ Hrest as _ & Hrest′ & Hlen′

md :
f :
n :
nat
IH :
∀k : nat is : listinst live out : listfact, checked_modulemd → InIFuncf md → Inb fn_blocksf → is = skipnk b_instsb → k ≤ Datatypes.lengthb_instsb%nat → live_domf b_labelb k live → checked_instsfn_srcmd f n is live = Someout → live_domf b_labelb Datatypes.lengthb_instsb out
k :
nat
i :
live, out :
listfact
Hin :
InIFuncf md
Hb :
rest′ :
listinst
a :
Hs :
i :: a :: rest′ = skipnk b_instsb
Hk :
k ≤ Datatypes.lengthb_instsb%nat
H :
live_domf b_labelb k live
live′ :
listfact
Ec :
checked_inst_restfn_srcmd f i a :: rest′ live = Somerest′, live′
Hc :
checked_instsfn_srcmd f n rest′ live′ = Someout
Hki :
nth_errorb_instsb k = Somei
Hrest :
skipnSk b_instsb = a :: rest′
Hlen :
Sk ≤ Datatypes.lengthb_instsb%nat
H1 :
live_domf b_labelb Sk live′
Hrest′ :
skipnSSk b_instsb = rest′
Hlen′ :
SSk ≤ Datatypes.lengthb_instsb%nat
⊢
live_domf b_labelb Datatypes.lengthb_instsb out

exact IH_ _ _ _ Hmd Hin Hb eq_symHrest′ Hlen′ live_dom_mono_ _ _ _ _ le_S_ _ le_n_ H1 Hc

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros md f b n
induction n as | n IH ; intros k is live out Hmd Hin Hb Hs Hk H Hc ; destruct is as | i rest ; cbn [ checked_insts ] in Hc ; injection Hc as ← ; exact live_dom_mono_ _ _ _ _ Hk H | ; discriminate Hc |
destruct checked_inst_rest_ i rest live as rest′ live′ | eqn: Ec ; | discriminate Hc
simpl in Hc
destruct skipn_cons_ _ _ _ _ eq_symHs as Hki & Hrest & Hlen
pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hb Hki Ec H as H1
destruct proj1pass_live_after_ _ _ _ _ _ Ec as → | a & →
–exact IH_ _ _ _ Hmd Hin Hb eq_symHrest Hlen H1 Hc
–destruct skipn_cons_ _ _ _ _ Hrest as _ & Hrest′ & Hlen′
exact IH_ _ _ _ Hmd Hin Hb eq_symHrest′ Hlen′ live_dom_mono_ _ _ _ _ le_S_ _ le_n_ H1 Hc

Each block's exit facts, in the map ex from labels to the facts at their end, dominate its end.

213Definition exits_domf : func ex : listname × listfact : Prop ≔
∀bp out, Inbp fn_blocksf → lookupb_labelbp ex = Someout → live_domf b_labelbp lengthb_instsbp out

Each successor label of a jump j is the label of one of its targets (jump_targets).

219Lemma jump_succs_target
∀ j s
∃t, Int jump_targetsj ∧ edge_labelt = s
Explore proof 5 tactics

Initial goal

⊢
∀j : jump s : name, Ins jump_succsj → ∃t : target, Int jump_targetsj ∧ edge_labelt = s

intros t | v t1 t2 | v | vs | | s H ; simpl in H ; try contradiction

2 open

s :
H :
edge_labelt = s ∨ False
⊢
∃t0 : target, Int0 jump_targetsJGotot ∧ edge_labelt0 = s
focused goal
t1, t2 :
s :
H :
edge_labelt1 = s ∨ edge_labelt2 = s ∨ False
⊢
∃t : target, Int jump_targetsJBranchv t1 t2 ∧ edge_labelt = s

–destruct H as ← |

2 open

⊢
∃t0 : target, Int0 jump_targetsJGotot ∧ edge_labelt0 = edge_labelt
deferred goal
t1, t2 :
s :
H :
edge_labelt1 = s ∨ edge_labelt2 = s ∨ False
⊢
∃t : target, Int jump_targetsJBranchv t1 t2 ∧ edge_labelt = s

exists t

2 open

deferred goal
t1, t2 :
s :
H :
edge_labelt1 = s ∨ edge_labelt2 = s ∨ False
⊢
∃t : target, Int jump_targetsJBranchv t1 t2 ∧ edge_labelt = s

split ; left | ; reflexivity

deferred goal
t1, t2 :
s :
H :
edge_labelt1 = s ∨ edge_labelt2 = s ∨ False
⊢
∃t : target, Int jump_targetsJBranchv t1 t2 ∧ edge_labelt = s

–destruct H as ← | ← | ; exists t1 | exists t2 ; simpl ; auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros t | v t1 t2 | v | vs | | s H ; simpl in H ; try contradiction
–destruct H as ← |
exists t
split ; left | ; reflexivity
–destruct H as ← | ← | ; exists t1 | exists t2 ; simpl ; auto

Where every block's exit facts dominate its end, the pass's entry facts of a block b (entry_live) dominate its entry: a fact that reaches b over every incoming edge has a pointer whose definition dominates each reachable predecessor's end, so b's entry too (dom_meet). The entry block has no incoming edge and no fact.

231Lemma entry_dom
∀ md f ex b
Proof 45 steps Qed
intros md f ex b Hmd Hin Hb Hex Hr fa y Hfa Hy Ho
destruct func_facts_ _ Hmd Hin as b0 & rest & Eb & Hdoms & Hnd & _
destruct module_func_ _ Hmd Hin as _ & b0′ & bs′ & Eb′ & Hnoin & _
rewrite Eb in Eb'
injection Eb' as ← ←
unfold entry_live in Hfa
apply entry_kill_in in Hfa as Hfa _
destruct name_eqbb_labelb b_labelb0 eqn: E0
{apply name_eqb_true in E0
rewrite E0 , incoming_nilfn_blocksf b_labelb0 in Hfa ; destruct Hfa |
exact Hnoin
apply name_eqb_false in E0
unfold once_has in Ho
destruct lookupy single_definitionsf as D | eqn: Ey ; | discriminate Ho
destruct once_position_ _ _ Ey as s0 & Hs0 & Huniq
exists s0, D
split ; exact Ey |
split ; exact Hs0 |
destruct s0 as | d j ; reflexivity |
simpl
rewrite Eb in Hnd
assert Hpre : ∀p, edgeb0 :: rest p b_labelb → is_reachablefn_domsf p = true → dominatesfn_domsf d p = true
{intros p bp & Hbp & Hpl & Hsj Hrp
rewrite <- Eb in Hbp
destruct jump_succs_target_ _ Hsj as t & Ht & Htl
pose proof incoming_in_ _ _ Hbp Ht as Hinc
rewrite Htl in Hinc
pose proof evidence_meet_in_ _ _ Hfa in_mapedge_setex _ _ Hinc as Hset
unfold edge_set in Hset
simpl in Hset
destruct is_pollt ; destruct Hset |
destruct lookupb_labelbp ex as fs | eqn: Ex ; | destruct Hset
destruct Hexbp fs Hbp Ex ltac:rewrite Hpl ; exact Hrp fa y Hset Hy ltac:unfold once_has ; rewrite Ey ; reflexivity as s & D′ & Ey′ & Hs & Hsd
rewrite Ey in Ey'
injection Ey' as ←
destruct Huniq_ _ Hs as → _
rewrite Hpl in Hsd
simpl in Hsd
destruct name_eqbd p eqn: Edp ; | exact Hsd
apply name_eqb_true in Edp
rewrite Edp
exact dominates_refl_ _ _ Hdoms _ Hrp
destruct dom_meet_ _ _ Hdoms _ _ Hnd Hr E0 Hpre as Hd Hne
rewrite proj2name_eqb_false_ _ Hne
exact Hd

Every block's exit facts, as the pass computes them for f (pass_exits), dominate its end.

268Lemma pass_exits_dom
∀ md f E
Proof 34 steps Qed
intros md f E Hmd Hin HE
unfold pass_exits in HE
destruct func_facts_ _ Hmd Hin as _ & _ & _ & _ & Hnd & _
assert G : ∀bs ex, ∀b, Inb bs → Inb fn_blocksf → fold_leftpass_blockfn_srcmd f f bs Someex = SomeE → exits_domf ex → exits_domf E
{induction bs as | b bs IH ; cbn [ fold_left ] ; intros ex Hbs H Hex ; injection H as ← ; exact Hex |
rewrite pass_block_some in H
destruct checked_insts_ _ _ entry_livef ex b as out | eqn: Ec ; | rewrite pass_fold_none in H ; discriminate H
apply IH_ λb′ Hb′ ⇒ Hbsb′ or_introrHb′ H
pose proof Hbsb or_introleq_refl as Hb
intros bp out′ Hbp Hl
rewrite lookup_put in Hl
destruct name_eqbb_labelbp b_labelb eqn: El
–injection Hl as ←
apply name_eqb_true in El
assert Hf : find_blockb_labelb fn_blocksf = Someb
{clear - Hnd Hb
induction fn_blocksf as | b1 bs1 IHb ; destruct Hb |
simpl in *
apply andb_true_iff in Hnd as Hn Hnd
destruct name_eqbb_labelb1 b_labelb eqn: E
–destruct Hb as → | Hb ; reflexivity |
exfalso
apply negb_true_iff in Hn
pose proof mem_false_ _ Hn b_labelb in_map_ _ _ Hb as Hne
apply name_eqb_true in E
rewrite E , name_eqb_refl in Hne
discriminate Hne
–destruct Hb as → | Hb ; rewrite name_eqb_refl in E ; discriminate E | exact IHbHnd Hb
rewrite find_block_unique_ _ _ _ Hnd Hf Hbp El
exact walk_dom_ _ _ _ 0 _ _ _ Hmd Hin Hb eq_refl Nat.le_0_l_ entry_dom_ _ _ _ Hmd Hin Hb Hex Ec
–exact Hex_ _ Hbp Hl
apply G_ _ λb Hb ⇒ Hb HE
intros bp out _ Hl
discriminate Hl

The invariant, frame by frame

The invariant over the configurations of Machine R, for any runtime R.

299Module Invariant R : Runtime
301Module RM ≔ Machine R
Import RM

The edge a jump j takes (taken_target) is one of its targets.

305Lemma taken_target_in
∀ ge fr j t
taken_targetge fr j = Somet
Explore proof 9 tactics

Initial goal

⊢
∀ge : genv fr : frame j : jump t : target, taken_targetge fr j = Somet → Int jump_targetsj

unfold taken_target

⊢
∀ ge : genv fr : frame j : jump t : target  ,
match j with
⇒
Somet0
JBranchv t1 t2
⇒
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
_
⇒
None
=
Somet
→

intros ge fr j t H

ge :
fr :
j :
H :
match j with
⇒
Somet
JBranchv t1 t2
⇒
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
_
⇒
None
=
Somet
⊢

destruct j ; try discriminate H

2 open

ge :
fr :
t0, t :
H :
Somet0 = Somet
focused goal
ge :
fr :
t1, t2, t :
H :
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
=
Somet
⊢

–injection H as ←

2 open

ge :
fr :
t0 :
deferred goal
ge :
fr :
t1, t2, t :
H :
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
=
Somet
⊢

left

2 open

ge :
fr :
t0 :
⊢
t0 = t0
deferred goal
ge :
fr :
t1, t2, t :
H :
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
=
Somet
⊢

reflexivity

deferred goal
ge :
fr :
t1, t2, t :
H :
match value_xge fr_envfr W v with
SomeWIntn
⇒
Some
n =? 0
→
t2
else
t1
_
⇒
None
=
Somet
⊢

–destruct value_x_ _ _ _ as n | | | ; try discriminate H

ge :
fr :
t1, t2, t :
n :
Z
H :
Some
n =? 0
→
t2
else
t1
=
Somet
⊢

injection H as ←

ge :
fr :
t1, t2 :
n :
Z
⊢
In
n =? 0
→
t2
else
t1

destruct n =? 0 ; simpl ; auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge fr j t H
destruct j ; try discriminate H
–injection H as ←
left
reflexivity
–destruct value_x_ _ _ _ as n | | | ; try discriminate H
injection H as ←
destruct n =? 0 ; simpl ; auto

An edge step along t from the block from that continues moves the frame to the entry of t's label, entered from from, with memory and fuel unchanged; and the frame is not doomed, or the edge does not poll.

317Lemma edge_step_next'
∀ c from t c′
edge_stepc from t = Nextc′
c′ = continue_atc with_pointc_framec Enteredge_labelt Somefrom c_memc c_fuelc ∧ fr_doomedc_framec = None ∨ is_pollt = false
Explore proof 3 tactics

Initial goal

⊢
∀c : config from : name t : target c′ : config, edge_stepc from t = Nextc′ → c′ = continue_atc with_pointc_framec Enteredge_labelt Somefrom c_memc c_fuelc ∧ fr_doomedc_framec = None ∨ is_pollt = false

unfold edge_step

⊢
∀ c : config from : name t : target c′ : config  ,

intros c from t c′ H

⊢
c′ = continue_atc with_pointc_framec Enteredge_labelt Somefrom c_memc c_fuelc ∧ fr_doomedc_framec = None ∨ is_pollt = false

destruct t , fr_doomedc_framec ; try discriminate H ; injection H as ← ; auto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
unfold edge_step
intros c from t c′ H
destruct t , fr_doomedc_framec ; try discriminate H ; injection H as ← ; auto

A jump at the end of block l takes an edge, the one taken_target names, or returns from a frame that is not doomed.

328Lemma jump_step_next
∀ ge c l j c′
jump_stepge c l j = Nextc′
∃t, taken_targetge c_framec j = Somet ∧ c′ = continue_atc with_pointc_framec Enteredge_labelt Somel c_memc c_fuelc ∨ fr_doomedc_framec = None ∧ ∃o, return_stepc o = Nextc′
Proof 33 steps Qed
intros ge c l j c′ H
unfold jump_step in H
destruct j as t | v t1 t2 | v | vs | |
–left
exists t
split ; reflexivity |
assert H′ : edge_stepc l t = Nextc' by destruct fr_doomedc_framec ; exact H
exact proj1edge_step_next'_ _ _ _ H'
–left
assert H′ : or_stuck"branch" let* x ≔ value_xge fr_envc_framec W v in match x with WIntn ⇒ Someedge_stepc l if n =? 0 then t2 else t1 | _ ⇒ None end = Nextc' by destruct fr_doomedc_framec ; exact H
apply or_stuck_next in H'
destruct value_xge fr_envc_framec W v as n | | | ; try discriminate H'
injection H' as H′
eexists
split ; reflexivity |
exact proj1edge_step_next'_ _ _ _ H'
–destruct fr_doomedc_framec eqn: Ew ; discriminate H |
right
split ; reflexivity |
apply or_stuck_next in H
destruct fn_ret_ ; try discriminate H
destruct value_x_ _ _ _ ; injection H as H ; eauto | discriminate H
–destruct fr_doomedc_framec eqn: Ew ; discriminate H |
right
split ; reflexivity |
apply or_stuck_next in H
destruct fn_ret_ ; try discriminate H
destruct map2_option_ _ _ ; injection H as H ; eauto | discriminate H
–destruct fr_doomedc_framec eqn: Ew ; discriminate H |
right
eauto
–destruct fr_doomedc_framec ; discriminate H

What holds where

at_pos says where the pass is in a block and what holds there: between two of the pass's steps, the live facts the next instruction relies on (and, at the block's end, the facts the next unpolled edge carries); or between a check and the access the pass took with it, the fact that covers the access (pair_claim). A check_function's raw call needs no fact but its function check.

At a block's end, before its jump j: if the edge j takes does not poll, the facts live hold. A poll edge carries no fact, since the runtime may act there.

371Definition jump_claimge : genv m : Memory.mem fr : frame j : jump live : listfact : Prop ≔
∀t, taken_targetge fr j = Somet → is_pollt = false → facts_holdge m fr_envfr live

Between a check and the access the pass took with it: the fact fb that covers the access (covered_access) holds, with the facts pre the pass kept with it, and live' is what evidence_after keeps of pre across the access; or, after a check_function, the access is a raw call through q whose pointer p passed its function check (function_check_res), and the pass keeps no fact.

380Definition pair_claimge : genv m : Memory.mem fr : frame access : inst live′ : listfact : Prop ≔
∃fb pre, covered_accessaccess f_qfb f_lofb f_hifb f_rfb f_alfb = true ∧ live′ = evidence_afteraccess pre ∧ facts_holdge m fr_envfr fb :: pre ∨ live′ = [ ] ∧ ∃r q args p, access = RawCallr Tmpq args ∧ lookupq fr_envfr = SomeWPtrp ∧ function_check_resge p = Someok

Where the pass is in the instructions is of block l of f, and what holds there, with out the pass's exit facts of the block. Either it is between two of its steps, with facts live that the pass walks to out (walks), that dominate index k (live_dom), and that hold if the next instruction relies on them (relies) or, at the block's end, as the jump carries them (jump_claim); or it is between a check and the access it took with it (pair_claim).

393Definition at_posge : genv s : src m : Memory.mem fr : frame is : listinst j : jump out : listfact f : func l : name k : nat : Prop ≔
∃ live  ,
walkss is live out
∧
live_domf l k live
∧
match is with
i :: _
⇒
reliess i = true → facts_holdge m fr_envfr live
[ ]
⇒
jump_claimge m fr j live
∨
∃access rest′ live′, is = access :: rest′ ∧ walkss rest′ live′ out ∧ live_domf l Sk live′ ∧ pair_claimge m fr access live′

What holds at the point of the frame fr in memory m, for its function f of the module md: at a snapshot, or at the entry entered from no block, the point is f's entry; at a block's entry from the block p, the edge is one of p's and, unless it polls, p's exit facts hold; within a block, at_pos, with the exit facts E the pass computes (pass_exits).

409Definition point_okge : genv md : module m : Memory.mem fr : frame : Prop ≔
let f ≔ fr_fnfr in
∃ E  ,
pass_exitsfn_srcmd f f = SomeE
∧
match fr_atfr with
⇒
entry_labelf = Somel
Enterl None
⇒
entry_labelf = Somel
Enterl Somep
⇒
∃bp t, find_blockp fn_blocksf = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Execl is j
⇒
∃b out k, find_blockl fn_blocksf = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd f m fr is j out f l k

Every named local the frame has allocated lies above address 0: a check_local's fact needs its address not to wrap.

426Definition locals_posfr : frame : Prop ≔
∀x base, lookupx fr_localsfr = SomeSomebase → 0 < base

The running frame fr: it runs a function of the module md, its locals lie above 0 (locals_pos), and it is point_ok unless a check_ahead doomed it.

432Definition frame_okge : genv md : module m : Memory.mem fr : frame : Prop ≔
InIFuncfr_fnfr md ∧ locals_posfr ∧ fr_doomedfr ≠ None ∨ point_okge md m fr

A waiting caller fr: it runs a function of md, its locals lie above 0, it is not doomed, and it waits just after its call, inside a block whose rest the pass walks from no fact at all: a call ends every fact.

439Definition parkedmd : module fr : frame : Prop ≔
InIFuncfr_fnfr md ∧ locals_posfr ∧ fr_doomedfr = None ∧ ∃E l rest j b out k, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ fr_atfr = Execl rest j ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ rest = skipnk b_instsb ∧ walksfn_srcmd fr_fnfr rest [ ] out

The invariant of a machine state st: the running frame is frame_ok, and every waiting caller is parked.

448Definition invge : genv md : module st : mstate : Prop ≔
frame_okge md c_memfstst c_framefstst ∧ Forallλfp ⇒ parkedmd fstfp c_callersfstst

The runtime's action at a safepoint changes no region where it comes just before an instruction i that the pass relies on facts across (relies). Every runtime satisfies it (spares_any): no region changes at a safepoint. It was kept a hypothesis while the safepoint stood for signal handlers too, since natively a pointer store whose aux must be allocated exits to the runtime, where a handler the program installed may free the checked object (docs/rocq.md, The evidence invariant over runs).

460Definition sparesge : genv md : module : Prop ≔
∀c s s′ m′, safepoint_duege c = true → R.safepoints c_memc s′ m′ → ∀l i rest j, fr_atc_framec = Execl i :: rest j → reliesfn_srcmd fr_fnc_framec i = true → m_regionsm′ = m_regionsc_memc

Every runtime spares every module's facts: the collector changes no region at a safepoint (R.collector_live).

468Lemma spares_any
∀ ge md
sparesge md
Explore proof 2 tactics

Initial goal

⊢
∀ge : genv md : module, sparesge md

intros ge md c s s′ m′ _ Hsp _ _ _ _ _ _

ge :
md :
s, s′ :
R.state
m′ :
Memory.mem
Hsp :
R.safepoints c_memc s′ m′

exact R.collector_live_ _ _ _ Hsp

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md c s s′ m′ _ Hsp _ _ _ _ _ _
exact R.collector_live_ _ _ _ Hsp

The empty list of facts holds.

472Lemma facts_hold_nil
∀ ge m e
facts_holdge m e [ ]
Explore proof 1 tactics

Initial goal

⊢
∀ge : genv m : Memory.mem e : env, facts_holdge m e [ ]

intros ge m e fa

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge m e fa

Where the facts after a step hold, whatever comes next may rely on them.

477Lemma at_pos_between
∀ ge s m fr is j live out f l k
walkss is live out
live_domf l k live
facts_holdge m fr_envfr live
at_posge s m fr is j out f l k
Explore proof 6 tactics

Initial goal

⊢
∀ge : genv s : src m : Memory.mem fr : frame is : listinst j : jump live out : listfact f : func l : name k : nat, walkss is live out → live_domf l k live → facts_holdge m fr_envfr live → at_posge s m fr is j out f l k

intros ge s m fr is j live out f l k Hw Hd Hl

ge :
s :
m :
Memory.mem
fr :
is :
listinst
j :
live, out :
listfact
f :
l :
k :
nat
Hw :
walkss is live out
Hd :
live_domf l k live
Hl :
facts_holdge m fr_envfr live
⊢
at_posge s m fr is j out f l k

left

ge :
s :
m :
Memory.mem
fr :
is :
listinst
j :
live, out :
listfact
f :
l :
k :
nat
Hw :
walkss is live out
Hd :
live_domf l k live
Hl :
facts_holdge m fr_envfr live
⊢
∃ live0 : listfact  ,
walkss is live0 out
∧
live_domf l k live0
∧
match is with
[ ]
⇒
jump_claimge m fr j live0
i :: _
⇒
reliess i = true → facts_holdge m fr_envfr live0

exists live

ge :
s :
m :
Memory.mem
fr :
is :
listinst
j :
live, out :
listfact
f :
l :
k :
nat
Hw :
walkss is live out
Hd :
live_domf l k live
Hl :
facts_holdge m fr_envfr live
⊢
walkss is live out
∧
live_domf l k live
∧
match is with
[ ]
⇒
jump_claimge m fr j live
i :: _
⇒
reliess i = true → facts_holdge m fr_envfr live

split ; exact Hw |

ge :
s :
m :
Memory.mem
fr :
is :
listinst
j :
live, out :
listfact
f :
l :
k :
nat
Hw :
walkss is live out
Hd :
live_domf l k live
Hl :
facts_holdge m fr_envfr live
⊢
live_domf l k live
∧
match is with
[ ]
⇒
jump_claimge m fr j live
i :: _
⇒
reliess i = true → facts_holdge m fr_envfr live

split ; exact Hd |

ge :
s :
m :
Memory.mem
fr :
is :
listinst
j :
live, out :
listfact
f :
l :
k :
nat
Hw :
walkss is live out
Hd :
live_domf l k live
Hl :
facts_holdge m fr_envfr live
⊢
match is with
[ ]
⇒
jump_claimge m fr j live
i :: _
⇒
reliess i = true → facts_holdge m fr_envfr live

destruct is ; intros t _ _ ; exact Hl | intros _ ; exact Hl

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge s m fr is j live out f l k Hw Hd Hl
left
exists live
split ; exact Hw |
split ; exact Hd |
destruct is ; intros t _ _ ; exact Hl | intros _ ; exact Hl

A parked caller, resumed with any environment e (the call's result bound) in any memory m, is frame_ok.

486Lemma parked_resume
∀ ge md m fr e
parkedmd fr
Explore proof 14 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem fr : frame e : env, parkedmd fr → frame_okge md m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr

intros ge md m fr e Hin & Hpos & Hd & E & l & rest & j & b & out & k & HE & Ha & Hb & Hout & Hj & Hk & Hw

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
frame_okge md m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr

split ; exact Hin |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
locals_posfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr ∧ fr_doomedfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr ≠ None ∨ point_okge md m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr

split ; exact Hpos |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
fr_doomedfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr ≠ None ∨ point_okge md m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr

right

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
point_okge md m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr

exists E

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
pass_exitsfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = SomeE
∧
match fr_atfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E = Someout0 ∧ facts_holdge m fr_envfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Somel0
Execl0 is j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Someb0 ∧ lookupl0 E = Someout0 ∧ j0 = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr is j0 out0 fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr l0 k0

split ; exact HE |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
match fr_atfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E = Someout0 ∧ facts_holdge m fr_envfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Somel0
Execl0 is j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr = Someb0 ∧ lookupl0 E = Someout0 ∧ j0 = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr is j0 out0 fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr l0 k0

simpl

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
match fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E = Someout0 ∧ facts_holdge m e out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr = Somel0
Execl0 is j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr = Someb0 ∧ lookupl0 E = Someout0 ∧ j0 = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ fr_atfr is j0 out0 fr_fnfr l0 k0

rewrite Ha

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
∃b0 : block out0 : listfact k0 : nat, find_blockl fn_blocksfr_fnfr = Someb0 ∧ lookupl E = Someout0 ∧ j = b_jumpb0 ∧ rest = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out0 fr_fnfr l k0

exists b, out, k

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ rest = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out fr_fnfr l k

split ; exact Hb |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
lookupl E = Someout ∧ j = b_jumpb ∧ rest = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out fr_fnfr l k

split ; exact Hout |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
j = b_jumpb ∧ rest = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out fr_fnfr l k

split ; exact Hj |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
rest = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out fr_fnfr l k

split ; exact Hk |

ge :
md :
m :
Memory.mem
fr :
e :
Hin :
InIFuncfr_fnfr md
Hpos :
Hd :
fr_doomedfr = None
E :
listname × listfact
l :
rest :
listinst
j :
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl rest j
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
rest = skipnk b_instsb
Hw :
walksfn_srcmd fr_fnfr rest [ ] out
⊢
at_posge fn_srcmd fr_fnfr m fr_fn ≔ fr_fnfr; fr_env ≔ e; fr_locals ≔ fr_localsfr; fr_doomed ≔ fr_doomedfr; fr_at ≔ Execl rest j rest j out fr_fnfr l k

eapply at_pos_between ; exact Hw | apply live_dom_nil | apply facts_hold_nil

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m fr e Hin & Hpos & Hd & E & l & rest & j & b & out & k & HE & Ha & Hb & Hout & Hj & Hk & Hw
split ; exact Hin |
split ; exact Hpos |
right
exists E
split ; exact HE |
simpl
rewrite Ha
exists b, out, k
split ; exact Hb |
split ; exact Hout |
split ; exact Hj |
split ; exact Hk |
eapply at_pos_between ; exact Hw | apply live_dom_nil | apply facts_hold_nil

A callee g of a checked module, its frame fr made by call_frame from the arguments xs, starts at its entry, frame_ok.

497Lemma call_frame_ok
∀ ge md m g xs fr
InIFuncg md
call_frameg xs = Somefr
frame_okge md m fr
Explore proof 15 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem g : func xs : listword fr : frame, checked_modulemd → InIFuncg md → call_frameg xs = Somefr → frame_okge md m fr

intros ge md m g xs fr Hmd Hin H

ge :
md :
m :
Memory.mem
g :
xs :
listword
fr :
Hin :
InIFuncg md
H :
call_frameg xs = Somefr
⊢
frame_okge md m fr

unfold call_frame in H

ge :
md :
m :
Memory.mem
g :
xs :
listword
fr :
Hin :
InIFuncg md
H :
Datatypes.lengthxs <? Datatypes.lengthfn_paramsg%nat
→
None
else
match fn_blocksg with
[ ]
⇒
None
b :: _
⇒
Somefr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs : name × Z ⇒ fstxs, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None
=
Somefr
⊢
frame_okge md m fr

destruct lengthxs <? lengthfn_paramsg%nat ; discriminate H |

ge :
md :
m :
Memory.mem
g :
xs :
listword
fr :
Hin :
InIFuncg md
H :
match fn_blocksg with
[ ]
⇒
None
b :: _
⇒
Somefr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs : name × Z ⇒ fstxs, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None
=
Somefr
⊢
frame_okge md m fr

destruct module_func_ _ Hmd Hin as _ & _ & E & HE

ge :
md :
m :
Memory.mem
g :
xs :
listword
fr :
Hin :
InIFuncg md
H :
match fn_blocksg with
[ ]
⇒
None
b :: _
⇒
Somefr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs : name × Z ⇒ fstxs, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None
=
Somefr
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
frame_okge md m fr

destruct fn_blocksg as | b bs eqn: Eb ; discriminate H |

ge :
md :
m :
Memory.mem
g :
xs :
listword
fr :
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
H :
Somefr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs : name × Z ⇒ fstxs, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somefr
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
frame_okge md m fr

injection H as ←

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
frame_okge md m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None

split ; exact Hin |

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
locals_posfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None ∧ fr_doomedfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None ≠ None ∨ point_okge md m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None

split ; intros x base Hx ; exfalso ; exact lookup_unallocated_ _ _ Hx |

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
fr_doomedfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None ≠ None ∨ point_okge md m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None

right

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
point_okge md m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None

exists E

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
pass_exitsfn_srcmd fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = SomeE
∧
match fr_atfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
⇒
entry_labelfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs1 : name × Z ⇒ fstxs1, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somel
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None out
Enterl None
⇒
entry_labelfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somel
Execl is j
⇒
∃b0 : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Someb0 ∧ lookupl E = Someout ∧ j = b_jumpb0 ∧ is = skipnk b_instsb0 ∧ at_posge fn_srcmd fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None is j out fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None l k

split ; exact HE |

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
match fr_atfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
⇒
entry_labelfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs1 : name × Z ⇒ fstxs1, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somel
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None out
Enterl None
⇒
entry_labelfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somel
Execl is j
⇒
∃b0 : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Someb0 ∧ lookupl E = Someout ∧ j = b_jumpb0 ∧ is = skipnk b_instsb0 ∧ at_posge fn_srcmd fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None is j out fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None l k

unfold entry_label

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
match fr_atfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
⇒
match fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs1 : name × Z ⇒ fstxs1, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
[ ]
⇒
None
b0 :: _
⇒
Someb_labelb0
=
Somel
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None out
Enterl None
⇒
match fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
[ ]
⇒
None
b0 :: _
⇒
Someb_labelb0
=
Somel
Execl is j
⇒
∃b0 : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None = Someb0 ∧ lookupl E = Someout ∧ j = b_jumpb0 ∧ is = skipnk b_instsb0 ∧ at_posge fn_srcmd fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None is j out fr_fnfr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None l k

simpl

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
match if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksg = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ] out
Snapshot_ l | Enterl None
⇒
match fn_blocksg with
[ ]
⇒
None
b0 :: _
⇒
Someb_labelb0
=
Somel
Execl is j
⇒
∃b0 : block out : listfact k : nat, find_blockl fn_blocksg = Someb0 ∧ lookupl E = Someout ∧ j = b_jumpb0 ∧ is = skipnk b_instsb0 ∧ at_posge fn_srcmd g m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None is j out g l k

rewrite Eb

ge :
md :
m :
Memory.mem
g :
xs :
listword
Hin :
InIFuncg md
bs :
listblock
Eb :
fn_blocksg = b :: bs
E :
listname × listfact
HE :
pass_exitsfn_srcmd g g = SomeE
⊢
match if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None with
Enterl Somep
⇒
∃bp : block t : target, find_blockp b :: bs = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ] out
Snapshot_ l | Enterl None
⇒
Someb_labelb = Somel
Execl is j
⇒
∃b0 : block out : listfact k : nat, find_blockl b :: bs = Someb0 ∧ lookupl E = Someout ∧ j = b_jumpb0 ∧ is = skipnk b_instsb0 ∧ at_posge fn_srcmd g m fr_fn ≔ g; fr_env ≔ fold_leftλe : listname × word px : class × name × word ⇒ putsndfstpx sndpx e combinefn_paramsg firstnDatatypes.lengthfn_paramsg xs [ ]; fr_locals ≔ mapλxs0 : name × Z ⇒ fstxs0, None local_objectsg; fr_doomed ≔ None; fr_at ≔ if variadic_funcg then Snapshotxs b_labelb else Enterb_labelb None is j out g l k

destruct variadic_funcg ; reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m g xs fr Hmd Hin H
unfold call_frame in H
destruct lengthxs <? lengthfn_paramsg%nat ; discriminate H |
destruct module_func_ _ Hmd Hin as _ & _ & E & HE
destruct fn_blocksg as | b bs eqn: Eb ; discriminate H |
injection H as ←
split ; exact Hin |
split ; intros x base Hx ; exfalso ; exact lookup_unallocated_ _ _ Hx |
right
exists E
split ; exact HE |
simpl
rewrite Eb
destruct variadic_funcg ; reflexivity

An instruction i the pass took, that continues, leaves the pass's next position true: the facts after it, or the fact that covers the access the pass took with it (pair_claim). The facts before i need to hold only if the pass relies on them (relies).

513Lemma pass_step
∀ ge s fr m i rest live rest′ live′ e1 l1 m1 fr1
reliess i = true → facts_holdge m fr_envfr live
checked_inst_rests i rest live = Somerest′, live′
inst_stepge fr m i = SomeIContinuee1 l1 m1
fr_envfr1 = e1
rest′ = rest ∧ facts_holdge m1 e1 live′ ∨ ∃access, rest = access :: rest′ ∧ pair_claimge m1 fr1 access live′
Proof 67 steps Qed
intros ge s fr m i rest live rest′ live′ e1 l1 m1 fr1 Hfit Hpos Hl Hc Hs He
destruct check_facti as fa | eqn: Hf
–assert Hr : reliess i = true by unfold relies ; rewrite check_fact_preserving_ _ Hf ; reflexivity
specialize HlHr
assert ∃fb, access_facti = Somefb as fb Hg by eapply access_fact_some ; eauto
destruct checked_inst_rest_check_ _ _ _ _ _ _ _ Hf Hg Hc as access & → & Hu & →
destruct check_like_holds_ _ _ _ _ _ _ _ _ Hf Hg Hs as Ha Hb
right
exists access
split ; reflexivity |
left
exists fb, fa :: evidence_afteri live
apply andb_true_iff in Hu as Hcov _
split ; exact Hcov |
split ; reflexivity |
rewrite He
apply facts_hold_cons ; exact Hb |
apply facts_hold_cons ; exact Ha |
eapply evidence_after_holds ; eauto
–destruct is_check_locali eqn: Hcl
+destruct i as q k o args | | | | | | | ; try discriminate Hcl
destruct k ; try discriminate Hcl ; destruct o ; try discriminate Hcl ; destruct args ; try discriminate Hcl
specialize Hleq_refl
destruct checked_inst_rest_local_cov_ _ _ _ _ _ _ _ _ _ _ Hc as access & → & Hcov & →
destruct check_local_fact_ _ _ _ _ _ _ _ _ _ _ _ _ Hfit Hpos Hcov Hs as → & Hag & Hq
destruct let_step_ _ _ _ _ _ _ _ _ _ Hs as Hreg _
right
exists access
split ; reflexivity |
left
exists mkFactq Tmpq 0 bytes r align, killq live
split ; exact Hcov |
split ; reflexivity |
rewrite He
apply facts_hold_cons ; exact Hq |
eapply facts_hold_kill ; reflexivity | exact Hag | exact Hl
+destruct is_check_functioni eqn: Hcf
∗destruct i as q k o args | | | | | | | ; try discriminate Hcf
destruct k ; try discriminate Hcf ; destruct o ; try discriminate Hcf
destruct checked_inst_rest_function_rest_ _ _ _ _ _ _ Hc as → & r & cargs & →
destruct check_function_step_ _ _ _ _ _ _ _ Hs as p & Hp & →
right
eexists
split ; reflexivity |
right
split ; reflexivity |
exists r, q, cargs, p
split ; reflexivity |
split ; | exact Hp
rewrite He
∗assert Hs′ : pass_speciali = false
{destruct pass_speciali eqn: Hp ; | reflexivity
destruct pass_special_cases_ Hp Hf as E | E ; congruence
left
rewrite checked_inst_rest_generic_ _ _ _ Hs' in Hc
destruct generic_rest_shape_ _ _ _ _ _ Hc as → & Hlive & _
split ; reflexivity |
destruct reliess i eqn: Hr
--specialize Hleq_refl
destruct Hlive as → | d & g & → & →
++eapply evidence_after_holds ; eauto
++destruct let_step_ _ _ _ _ _ _ _ _ _ Hs as Hreg Hag
eapply facts_hold_kill ; eauto
--rewrite <- checked_inst_rest_generic_ _ _ _ Hs' in Hc
rewrite relies_false_ _ _ _ _ _ Hr Hc

The access the pass took with its check, if it continues, leaves the facts the pass has after it.

568Lemma pair_continue
∀ ge m fr access live′ e1 l1 m1
pair_claimge m fr access live′
inst_stepge fr m access = SomeIContinuee1 l1 m1
facts_holdge m1 e1 live′
Explore proof 6 tactics

Initial goal

⊢
∀ge : genv m : Memory.mem fr : frame access : inst live′ : listfact e1 : env l1 : listname × optionZ m1 : Memory.mem, pair_claimge m fr access live′ → inst_stepge fr m access = SomeIContinuee1 l1 m1 → facts_holdge m1 e1 live′

intros ge m fr access live′ e1 l1 m1 fb & pre & _ & → & Hh | → & _ Hs ; | apply facts_hold_nil

ge :
m :
Memory.mem
fr :
access :
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fb :
pre :
listfact
Hh :
facts_holdge m fr_envfr fb :: pre
Hs :
inst_stepge fr m access = SomeIContinuee1 l1 m1
⊢
facts_holdge m1 e1 evidence_afteraccess pre

eapply evidence_after_holds ; | exact Hs

ge :
m :
Memory.mem
fr :
access :
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fb :
pre :
listfact
Hh :
facts_holdge m fr_envfr fb :: pre
Hs :
inst_stepge fr m access = SomeIContinuee1 l1 m1
⊢
facts_holdge m fr_envfr pre

intros fa Hin

ge :
m :
Memory.mem
fr :
access :
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fb :
pre :
listfact
Hh :
facts_holdge m fr_envfr fb :: pre
Hs :
inst_stepge fr m access = SomeIContinuee1 l1 m1
fa :
Hin :
Infa pre
⊢

apply Hh

ge :
m :
Memory.mem
fr :
access :
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fb :
pre :
listfact
Hh :
facts_holdge m fr_envfr fb :: pre
Hs :
inst_stepge fr m access = SomeIContinuee1 l1 m1
fa :
Hin :
Infa pre
⊢
Infa fb :: pre

right

ge :
m :
Memory.mem
fr :
access :
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fb :
pre :
listfact
Hh :
facts_holdge m fr_envfr fb :: pre
Hs :
inst_stepge fr m access = SomeIContinuee1 l1 m1
fa :
Hin :
Infa pre
⊢
Infa pre

exact Hin

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge m fr access live′ e1 l1 m1 fb & pre & _ & → & Hh | → & _ Hs ; | apply facts_hold_nil
eapply evidence_after_holds ; | exact Hs
intros fa Hin
apply Hh
right
exact Hin

Where the instruction i at the pass's position, index k of block b, continues with environment e1 and memory m1, the next position, at index k + 1, holds of any frame fr1 with environment e1.

579Lemma at_pos_continue
∀ ge md m fr i rest j out e1 l1 m1 fr1 f l b k
InIFuncf md
i :: rest = skipnk b_instsb
at_posge fn_srcmd f m fr i :: rest j out f l k
inst_stepge fr m i = SomeIContinuee1 l1 m1
fr_envfr1 = e1
at_posge fn_srcmd f m1 fr1 rest j out f l Sk
Explore proof 18 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem fr : frame i : inst rest : listinst j : jump out : listfact e1 : env l1 : listname × optionZ m1 : Memory.mem fr1 : frame f : func l : name b : block k : nat, checked_modulemd → InIFuncf md → find_blockl fn_blocksf = Someb → i :: rest = skipnk b_instsb → objects_fitm_regionsm → locals_posfr → at_posge fn_srcmd f m fr i :: rest j out f l k → inst_stepge fr m i = SomeIContinuee1 l1 m1 → fr_envfr1 = e1 → at_posge fn_srcmd f m1 fr1 rest j out f l Sk

intros ge md m fr i rest j out e1 l1 m1 fr1 f l b k Hmd Hin Hb Hk Hfit Hpos Hat Hs He

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
l :
k :
nat
Hin :
InIFuncf md
Hb :
Hk :
i :: rest = skipnk b_instsb
Hpos :
Hat :
at_posge fn_srcmd f m fr i :: rest j out f l k
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
⊢
at_posge fn_srcmd f m1 fr1 rest j out f l Sk

destruct find_block_in_ _ _ Hb as Hbin ←

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
Hat :
at_posge fn_srcmd f m fr i :: rest j out f b_labelb k
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

destruct skipn_cons_ _ _ _ _ eq_symHk as Hki & _ & _

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
Hat :
at_posge fn_srcmd f m fr i :: rest j out f b_labelb k
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

destruct Hat as live & Hw & Hd & Hl | access & rest′ & live′ & E & Hw & Hd & Hp

2 open

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: rest live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk
focused goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′

2 open

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: rest live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hbin Hki Hc Hd as Hd′

2 open

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: rest live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

destruct pass_step_ _ _ _ _ _ _ _ _ _ _ _ _ Hfit Hpos Hl Hc Hs He as → & Hh | access & → & Hp

3 open

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: rest live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hw′ :
walksfn_srcmd f rest live′ out
Hc :
checked_inst_restfn_srcmd f i rest live = Somerest, live′
Hd′ :
live_domf b_labelb Sk live′
Hh :
facts_holdge m1 e1 live′
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk
focused goal
ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
at_posge fn_srcmd f m1 fr1 access :: rest′ j out f b_labelb Sk
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

+eapply at_pos_between ; exact Hw′ | exact Hd′ | rewrite He ; exact Hh

2 open

deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
at_posge fn_srcmd f m1 fr1 access :: rest′ j out f b_labelb Sk
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

+right

2 open

ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
∃access0 : inst rest'0 : listinst live'0 : listfact, access :: rest′ = access0 :: rest'0 ∧ walksfn_srcmd f rest'0 live'0 out ∧ live_domf b_labelb SSk live'0 ∧ pair_claimge m1 fr1 access0 live'0
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

exists access, rest′, live′

2 open

ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
access :: rest′ = access :: rest′ ∧ walksfn_srcmd f rest′ live′ out ∧ live_domf b_labelb SSk live′ ∧ pair_claimge m1 fr1 access live′
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

split ; reflexivity |

2 open

ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
walksfn_srcmd f rest′ live′ out ∧ live_domf b_labelb SSk live′ ∧ pair_claimge m1 fr1 access live′
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

split ; exact Hw′ |

2 open

ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
live_domf b_labelb SSk live′ ∧ pair_claimge m1 fr1 access live′
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

split ; exact live_dom_mono_ _ _ _ _ le_S_ _ le_n_ Hd′ |

2 open

ge :
md :
m :
Memory.mem
fr :
i :
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
rest′ :
listinst
access :
Hk :
i :: access :: rest′ = skipnk b_instsb
Hpos :
live :
listfact
Hw :
walksfn_srcmd f i :: access :: rest′ live out
Hd :
live_domf b_labelb k live
Hl :
reliesfn_srcmd f i = true → facts_holdge m fr_envfr live
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
live′ :
listfact
Hc :
checked_inst_restfn_srcmd f i access :: rest′ live = Somerest′, live′
Hw′ :
walksfn_srcmd f rest′ live′ out
Hd′ :
live_domf b_labelb Sk live′
Hp :
pair_claimge m1 fr1 access live′
⊢
pair_claimge m1 fr1 access live′
deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

exact Hp

deferred goal
ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walksfn_srcmd f rest′ live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr access live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

–injection E as ← ←

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live′ :
listfact
Hw :
walksfn_srcmd f rest live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr i live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
at_posge fn_srcmd f m1 fr1 rest j out f b_labelb Sk

eapply at_pos_between ; exact Hw | exact Hd |

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live′ :
listfact
Hw :
walksfn_srcmd f rest live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr i live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
facts_holdge m1 fr_envfr1 live′

rewrite He

ge :
md :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
e1 :
l1 :
listname × optionZ
m1 :
Memory.mem
fr1 :
f :
k :
nat
Hin :
InIFuncf md
Hk :
i :: rest = skipnk b_instsb
Hpos :
live′ :
listfact
Hw :
walksfn_srcmd f rest live′ out
Hd :
live_domf b_labelb Sk live′
Hp :
pair_claimge m fr i live′
Hs :
inst_stepge fr m i = SomeIContinuee1 l1 m1
He :
fr_envfr1 = e1
Hbin :
Hki :
nth_errorb_instsb k = Somei
⊢
facts_holdge m1 e1 live′

eapply pair_continue ; eauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m fr i rest j out e1 l1 m1 fr1 f l b k Hmd Hin Hb Hk Hfit Hpos Hat Hs He
destruct find_block_in_ _ _ Hb as Hbin ←
destruct skipn_cons_ _ _ _ _ eq_symHk as Hki & _ & _
destruct Hat as live & Hw & Hd & Hl | access & rest′ & live′ & E & Hw & Hd & Hp
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′
pose proof pass_step_dom_ _ _ _ _ _ _ _ _ Hmd Hin Hbin Hki Hc Hd as Hd′
destruct pass_step_ _ _ _ _ _ _ _ _ _ _ _ _ Hfit Hpos Hl Hc Hs He as → & Hh | access & → & Hp
+eapply at_pos_between ; exact Hw′ | exact Hd′ | rewrite He ; exact Hh
+right
exists access, rest′, live′
split ; reflexivity |
split ; exact Hw′ |
split ; exact live_dom_mono_ _ _ _ _ le_S_ _ le_n_ Hd′ |
exact Hp
–injection E as ← ←
eapply at_pos_between ; exact Hw | exact Hd |
rewrite He
eapply pair_continue ; eauto

After an instruction the pass relies on nothing for, and that is not a check_function, the pass goes on with no facts.

604Lemma walks_after
∀ ge s m fr i rest j out f l k
at_posge s m fr i :: rest j out f l k
reliess i = false
walkss rest [ ] out
Explore proof 10 tactics

Initial goal

⊢
∀ge : genv s : src m : Memory.mem fr : frame i : inst rest : listinst j : jump out : listfact f : func l : name k : nat, at_posge s m fr i :: rest j out f l k → reliess i = false → is_check_functioni = false → walkss rest [ ] out

intros ge s m fr i rest j out f l k Hat Hr Hcf

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
Hat :
at_posge s m fr i :: rest j out f l k
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

destruct Hat as live & Hw & _ | access & rest′ & live′ & E & Hw & _ & Hp

2 open

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
live :
listfact
Hw :
walkss i :: rest live out
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out
focused goal
ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walkss rest′ live′ out
Hp :
pair_claimge m fr access live′
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′

2 open

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
live :
listfact
Hw :
walkss i :: rest live out
Hr :
reliess i = false
Hcf :
rest′ :
listinst
live′ :
listfact
Hc :
checked_inst_rests i rest live = Somerest′, live′
Hw′ :
walkss rest′ live′ out
⊢
walkss rest [ ] out
deferred goal
ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walkss rest′ live′ out
Hp :
pair_claimge m fr access live′
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

destruct relies_false_rest_ _ _ _ _ _ Hr Hcf Hc as → →

2 open

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
live :
listfact
Hw :
walkss i :: rest live out
Hr :
reliess i = false
Hcf :
Hc :
checked_inst_rests i rest live = Somerest, [ ]
Hw′ :
walkss rest [ ] out
⊢
walkss rest [ ] out
deferred goal
ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walkss rest′ live′ out
Hp :
pair_claimge m fr access live′
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

exact Hw′

deferred goal
ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
access :
rest′ :
listinst
live′ :
listfact
E :
i :: rest = access :: rest′
Hw :
walkss rest′ live′ out
Hp :
pair_claimge m fr access live′
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

–injection E as ← ←

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
live′ :
listfact
Hw :
walkss rest live′ out
Hp :
pair_claimge m fr i live′
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

destruct Hp as fb & pre & _ & → & _ | → & _ ; | exact Hw

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
pre :
listfact
Hw :
walkss rest evidence_afteri pre out
fb :
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

unfold evidence_after in Hw

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
pre :
listfact
Hw :
walkss rest
→
match inst_def_firsti with
Somed
⇒
killd pre
None
⇒
pre
else
[ ]
out
fb :
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

rewrite relies_preserving_ _ Hr in Hw

ge :
s :
m :
Memory.mem
fr :
i :
rest :
listinst
j :
out :
listfact
f :
l :
k :
nat
pre :
listfact
Hw :
walkss rest [ ] out
fb :
Hr :
reliess i = false
Hcf :
⊢
walkss rest [ ] out

exact Hw

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge s m fr i rest j out f l k Hat Hr Hcf
destruct Hat as live & Hw & _ | access & rest′ & live′ & E & Hw & _ & Hp
–destruct walks_cons_ _ _ _ _ Hw as rest′ & live′ & Hc & Hw′
destruct relies_false_rest_ _ _ _ _ _ Hr Hcf Hc as → →
exact Hw′
–injection E as ← ←
destruct Hp as fb & pre & _ & → & _ | → & _ ; | exact Hw
unfold evidence_after in Hw
rewrite relies_preserving_ _ Hr in Hw
exact Hw

Reading and making point_ok

point_ok of a frame inside block l, from at_pos at its instructions is, the suffix of the block from index k.

621Lemma point_ok_exec
∀ ge md m fr l is j E b out k
fr_atfr = Execl is j
lookupl E = Someout
j = b_jumpb
is = skipnk b_instsb
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
point_okge md m fr
Explore proof 7 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem fr : frame l : name is : listinst j : jump E : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE → fr_atfr = Execl is j → find_blockl fn_blocksfr_fnfr = Someb → lookupl E = Someout → j = b_jumpb → is = skipnk b_instsb → at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k → point_okge md m fr

intros ge md m fr l is j E b out k HE Ha Hb Ho Hj Hk Hat

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
point_okge md m fr

unfold point_ok

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
∃ E0 : listname × listfact  ,
pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0
∧
match fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E0 = Someout0 ∧ facts_holdge m fr_envfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr = Somel0
Execl0 is0 j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ is0 = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is0 j0 out0 fr_fnfr l0 k0

cbv zeta

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
∃ E0 : listname × listfact  ,
pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0
∧
match fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E0 = Someout0 ∧ facts_holdge m fr_envfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr = Somel0
Execl0 is0 j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ is0 = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is0 j0 out0 fr_fnfr l0 k0

exists E

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
∧
match fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E = Someout0 ∧ facts_holdge m fr_envfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr = Somel0
Execl0 is0 j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr = Someb0 ∧ lookupl0 E = Someout0 ∧ j0 = b_jumpb0 ∧ is0 = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is0 j0 out0 fr_fnfr l0 k0

split ; exact HE |

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
match fr_atfr with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out0 : listfact, lookupp E = Someout0 ∧ facts_holdge m fr_envfr out0
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr = Somel0
Execl0 is0 j0
⇒
∃b0 : block out0 : listfact k0 : nat, find_blockl0 fn_blocksfr_fnfr = Someb0 ∧ lookupl0 E = Someout0 ∧ j0 = b_jumpb0 ∧ is0 = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is0 j0 out0 fr_fnfr l0 k0

rewrite Ha

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
out :
listfact
k :
nat
HE :
Ha :
fr_atfr = Execl is j
Hb :
Ho :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
is = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
⊢
∃b0 : block out0 : listfact k0 : nat, find_blockl fn_blocksfr_fnfr = Someb0 ∧ lookupl E = Someout0 ∧ j = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is j out0 fr_fnfr l k0

eauto 8

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m fr l is j E b out k HE Ha Hb Ho Hj Hk Hat
unfold point_ok
cbv zeta
exists E
split ; exact HE |
rewrite Ha
eauto 8

Conversely, point_ok of a frame inside block l gives the block b, the pass's exit facts, the index k of its point, and at_pos.

633Lemma point_ok_exec_inv
∀ ge md m fr l is j
point_okge md m fr
fr_atfr = Execl is j
∃E b out k, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Explore proof 7 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem fr : frame l : name is : listinst j : jump, point_okge md m fr → fr_atfr = Execl is j → ∃E : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

intros ge md m fr l is j H Ha

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
H :
point_okge md m fr
Ha :
fr_atfr = Execl is j
⊢
∃E : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

unfold point_ok in H

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
H :
∃ E : listname × listfact  ,
∧
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Execl is j
⊢
∃E : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

cbv zeta in H

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
H :
∃ E : listname × listfact  ,
∧
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Execl is j
⊢
∃E : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

destruct H as E & HE & H

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
HE :
H :
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Execl is j
⊢
∃E0 : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0 ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E0 = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

rewrite Ha in H

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
HE :
H :
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Execl is j
⊢
∃E0 : listname × listfact b : block out : listfact k : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0 ∧ find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E0 = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k

destruct H as b & out & k & ?

ge :
md :
m :
Memory.mem
fr :
l :
is :
listinst
j :
E :
listname × listfact
HE :
out :
listfact
k :
nat
H :
find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Execl is j
⊢
∃E0 : listname × listfact b0 : block out0 : listfact k0 : nat, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0 ∧ find_blockl fn_blocksfr_fnfr = Someb0 ∧ lookupl E0 = Someout0 ∧ j = b_jumpb0 ∧ is = skipnk0 b_instsb0 ∧ at_posge fn_srcmd fr_fnfr m fr is j out0 fr_fnfr l k0

eauto 10

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m fr l is j H Ha
unfold point_ok in H
cbv zeta in H
destruct H as E & HE & H
rewrite Ha in H
destruct H as b & out & k & ?
eauto 10

A running frame that is not doomed, at a call, can wait after it with no fact, whatever the call does: it is parked there.

645Lemma call_parked
∀ ge md m fr l r callee args rest j
frame_okge md m fr
fr_doomedfr = None
fr_atfr = Execl Callr callee args :: rest j
parkedmd mkFramefr_fnfr fr_envfr fr_localsfr None Execl rest j
Explore proof 12 tactics

Initial goal

⊢
∀ge : genv md : module m : Memory.mem fr : frame l : name r : call_result callee : value args : listarg rest : listinst j : jump, frame_okge md m fr → fr_doomedfr = None → fr_atfr = Execl Callr callee args :: rest j → parkedmd fr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j

intros ge md m fr l r callee args rest j Hin & Hpos & Hpt Hd Ha

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hpt :
fr_doomedfr ≠ None ∨ point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
⊢
parkedmd fr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j

destruct Hpt as Hd0 | Hp ; congruence |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
⊢
parkedmd fr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j

destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Hout & Hj & Hk & Hat

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
⊢
parkedmd fr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j

destruct skipn_cons_ _ _ _ _ eq_symHk as _ & Hrest & _

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
parkedmd fr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j

split ; exact Hin |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
locals_posfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j ∧ fr_doomedfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = None ∧ ∃E0 : listname × listfact l0 : name rest0 : listinst j0 : jump b0 : block out0 : listfact k0 : nat, pass_exitsfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = SomeE0 ∧ fr_atfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Execl0 rest0 j0 ∧ find_blockl0 fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ rest0 = skipnk0 b_instsb0 ∧ walksfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j rest0 [ ] out0

split ; exact Hpos |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
fr_doomedfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = None ∧ ∃E0 : listname × listfact l0 : name rest0 : listinst j0 : jump b0 : block out0 : listfact k0 : nat, pass_exitsfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = SomeE0 ∧ fr_atfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Execl0 rest0 j0 ∧ find_blockl0 fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ rest0 = skipnk0 b_instsb0 ∧ walksfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j rest0 [ ] out0

split ; reflexivity |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
∃E0 : listname × listfact l0 : name rest0 : listinst j0 : jump b0 : block out0 : listfact k0 : nat, pass_exitsfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = SomeE0 ∧ fr_atfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Execl0 rest0 j0 ∧ find_blockl0 fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Someb0 ∧ lookupl0 E0 = Someout0 ∧ j0 = b_jumpb0 ∧ rest0 = skipnk0 b_instsb0 ∧ walksfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j rest0 [ ] out0

exists E, l, rest, j, b, out, Sk

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
pass_exitsfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = SomeE ∧ fr_atfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Execl rest j ∧ find_blockl fn_blocksfr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ rest = skipnSk b_instsb ∧ walksfn_srcmd fr_fnfr_fn ≔ fr_fnfr; fr_env ≔ fr_envfr; fr_locals ≔ fr_localsfr; fr_doomed ≔ None; fr_at ≔ Execl rest j rest [ ] out

simpl

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
∧
Execl rest j = Execl rest j
∧
∧
lookupl E = Someout
∧
j = b_jumpb
∧
rest
=
match b_instsb with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
∧
walksfn_srcmd fr_fnfr rest [ ] out

repeat split ; assumption || reflexivity |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
rest
=
match b_instsb with
[ ]
⇒
[ ]
_ :: l0
⇒
skipnk l0
∧
walksfn_srcmd fr_fnfr rest [ ] out

split ; symmetry ; exact Hrest |

ge :
md :
m :
Memory.mem
fr :
l :
callee :
args :
listarg
rest :
listinst
j :
Hin :
InIFuncfr_fnfr md
Hpos :
Hp :
point_okge md m fr
Hd :
fr_doomedfr = None
Ha :
fr_atfr = Execl Callr callee args :: rest j
E :
listname × listfact
out :
listfact
k :
nat
HE :
Hb :
Hout :
lookupl E = Someout
Hj :
j = b_jumpb
Hk :
Callr callee args :: rest = skipnk b_instsb
Hat :
at_posge fn_srcmd fr_fnfr m fr Callr callee args :: rest j out fr_fnfr l k
Hrest :
skipnSk b_instsb = rest
⊢
walksfn_srcmd fr_fnfr rest [ ] out

eapply walks_after ; exact Hat | reflexivity | reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m fr l r callee args rest j Hin & Hpos & Hpt Hd Ha
destruct Hpt as Hd0 | Hp ; congruence |
destruct point_ok_exec_inv_ _ _ _ _ _ _ Hp Ha as E & b & out & k & HE & Hb & Hout & Hj & Hk & Hat
destruct skipn_cons_ _ _ _ _ eq_symHk as _ & Hrest & _
split ; exact Hin |
split ; exact Hpos |
split ; reflexivity |
exists E, l, rest, j, b, out, Sk
simpl
repeat split ; assumption || reflexivity |
split ; symmetry ; exact Hrest |
eapply walks_after ; exact Hat | reflexivity | reflexivity

A frame fr' of the same function, at the entry of the entry block l from no block, is point_ok in any memory where fr, at the snapshot that leads to l or at l itself, was: a function's entry is where its snapshot leads.

663Lemma point_ok_entry
∀ ge md m m′ fr fr′ xs l
point_okge md m fr
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
fr_fnfr′ = fr_fnfr
fr_atfr′ = Enterl None
point_okge md m′ fr′
Explore proof 8 tactics

Initial goal

⊢
∀ge : genv md : module m m′ : Memory.mem fr fr′ : frame xs : listword l : name, point_okge md m fr → fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None → fr_fnfr′ = fr_fnfr → fr_atfr′ = Enterl None → point_okge md m′ fr′

intros ge md m m′ fr fr′ xs l H Ha Hf Ha′

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
H :
point_okge md m fr
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
point_okge md m′ fr′

unfold point_ok in *

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
H :
∃ E : listname × listfact  ,
∧
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
∃ E : listname × listfact  ,
pass_exitsfn_srcmd fr_fnfr′ fr_fnfr′ = SomeE
∧
match fr_atfr′ with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr′ = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m′ fr_envfr′ out
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr′ = Somel0
Execl0 is j
⇒
∃b : block out : listfact k : nat, find_blockl0 fn_blocksfr_fnfr′ = Someb ∧ lookupl0 E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr′ m′ fr′ is j out fr_fnfr′ l0 k

cbv zeta in *

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
H :
∃ E : listname × listfact  ,
∧
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
∃ E : listname × listfact  ,
pass_exitsfn_srcmd fr_fnfr′ fr_fnfr′ = SomeE
∧
match fr_atfr′ with
Enterl0 Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr′ = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l0 ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m′ fr_envfr′ out
Snapshot_ l0 | Enterl0 None
⇒
entry_labelfr_fnfr′ = Somel0
Execl0 is j
⇒
∃b : block out : listfact k : nat, find_blockl0 fn_blocksfr_fnfr′ = Someb ∧ lookupl0 E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr′ m′ fr′ is j out fr_fnfr′ l0 k

rewrite Hf , Ha′

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
H :
∃ E : listname × listfact  ,
∧
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
∃E : listname × listfact, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ entry_labelfr_fnfr = Somel

destruct H as E & HE & H

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
E :
listname × listfact
HE :
H :
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
∃E0 : listname × listfact, pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE0 ∧ entry_labelfr_fnfr = Somel

exists E

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
E :
listname × listfact
HE :
H :
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
pass_exitsfn_srcmd fr_fnfr fr_fnfr = SomeE ∧ entry_labelfr_fnfr = Somel

split ; exact HE |

ge :
md :
m, m′ :
Memory.mem
fr, fr′ :
xs :
listword
l :
E :
listname × listfact
HE :
H :
match fr_atfr with
Enterl Somep
⇒
∃bp : block t : target, find_blockp fn_blocksfr_fnfr = Somebp ∧ Int jump_targetsb_jumpbp ∧ edge_labelt = l ∧ is_pollt = true ∨ ∃out : listfact, lookupp E = Someout ∧ facts_holdge m fr_envfr out
Snapshot_ l | Enterl None
⇒
entry_labelfr_fnfr = Somel
Execl is j
⇒
∃b : block out : listfact k : nat, find_blockl fn_blocksfr_fnfr = Someb ∧ lookupl E = Someout ∧ j = b_jumpb ∧ is = skipnk b_instsb ∧ at_posge fn_srcmd fr_fnfr m fr is j out fr_fnfr l k
Ha :
fr_atfr = Snapshotxs l ∨ fr_atfr = Enterl None
Hf :
fr_fnfr′ = fr_fnfr
Ha′ :
fr_atfr′ = Enterl None
⊢
entry_labelfr_fnfr = Somel

destruct Ha as Ha | Ha ; rewrite Ha in H ; exact H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md m m′ fr fr′ xs l H Ha Hf Ha′
unfold point_ok in *
cbv zeta in *
rewrite Hf , Ha′
destruct H as E & HE & H
exists E
split ; exact HE |
destruct Ha as Ha | Ha ; rewrite Ha in H ; exact H

Nothing is found in an empty map.

673Lemma lookup_nil_none
∀ A : Type n
@lookupA n [ ] = None
Explore proof 1 tactics

Initial goal

⊢
∀A : Type n : name, lookupn [ ] = None

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
reflexivity

Entering a block l of a checked module's function, from point_ok, the pass's entry facts hold once the phis have run, and their pointers dominate the entry (entry_dom): the frame after the step is point_ok.

680Lemma enter_point_ok
∀ ge md c c′ l from
point_okge md c_memc′ c_framec′
Proof 46 steps Qed
intros ge md c c′ l from Hmd Hin Ha Hs H
destruct step_enter_ _ _ _ _ Ha Hs as b & e & Hb & Hp & →
unfold point_ok in H
cbv zeta in H
destruct H as E & HE & Hpt
rewrite Ha in Hpt
set f := fr_fnc_framec in *
destruct module_func_ _ Hmd Hin as Hd & b0 & bs & Eb & Hnoin & _
pose proof find_block_in_ _ _ Hb as Hbin Hbl
destruct pass_fold_ _ _ _ _ HE Hd λb _ ⇒ lookup_nil_none_ b_labelb b Hbin as exits & out & Hsub & Hout & Hc
eapply point_ok_exec with b := b out := out k := 0%nat ; simpl ; exact HE | reflexivity | exact Hb | rewrite <- Hbl ; exact Hout | reflexivity | reflexivity |
eapply at_pos_between ; exists Slengthb_instsb ; exact Hc | |
{rewrite <- Hbl
apply entry_dommd ; exact Hmd | exact Hin | exact Hbin |
intros bp o Hbp Ho
apply pass_exits_dom_ _ _ Hmd Hin HE _ _ Hbp
exact Hsub_ _ Ho
simpl
unfold entry_live
destruct from as p |
–eapply phis_facts_hold ; exact Hp |
intros fa Hfa
destruct Hpt as bp & t & Hbp & Ht & Hl & Hpoll
destruct find_block_in_ _ _ Hbp as Hbpin Hbpl
assert Hset : Inedge_setexits p, is_pollt mapedge_setexits incomingfn_blocksf b_labelb
{apply in_map
rewrite Hbl , <- Hl , <- Hbpl
apply incoming_in ; assumption
pose proof evidence_meet_in_ _ _ Hfa Hset as Hfa′
unfold edge_set in Hfa'
simpl in Hfa'
destruct is_pollt eqn: Ep ; destruct Hfa' |
destruct lookupp exits as fs | eqn: Ex ; | destruct Hfa'
destruct Hpoll as Hpoll | out′ & Ho′ & Hh ; discriminate Hpoll |
rewrite Hsub_ _ Ex in Ho'
injection Ho' as ←
exact Hhfa Hfa'
–intros fa Hfa
exfalso
unfold entry_label in Hpt
rewrite Eb in Hpt
injection Hpt as Hl0
rewrite Hbl , incoming_nilfn_blocksf l in Hfa ; destruct entry_kill_in_ _ _ Hfa as _ |
rewrite <- Hl0
rewrite Eb in Hnoin |- *
exact Hnoin