forked from SJTU-PLV/direct-refinement-popl24-artifact
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathUnusedglobproof.v
1801 lines (1651 loc) · 62.1 KB
/
Unusedglobproof.v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
(* *********************************************************************)
(* *)
(* The Compcert verified compiler *)
(* *)
(* Xavier Leroy, INRIA Paris-Rocquencourt *)
(* *)
(* Copyright Institut National de Recherche en Informatique et en *)
(* Automatique. All rights reserved. This file is distributed *)
(* under the terms of the INRIA Non-Commercial License Agreement. *)
(* *)
(* *********************************************************************)
(** Elimination of unreferenced static definitions *)
Require Import FSets Coqlib Maps Ordered Iteration Errors.
Require Import AST Linking.
Require Import Integers Values Memory Globalenvs Events Smallstep.
Require Import Op Registers RTL.
Require Import Unusedglob.
Module ISF := FSetFacts.Facts(IS).
Module ISP := FSetProperties.Properties(IS).
(** * Relational specification of the transformation *)
(** The transformed program is obtained from the original program
by keeping only the global definitions that belong to a given
set [u] of names. *)
Record match_prog_1 (u: IS.t) (p tp: program) : Prop := {
match_prog_main:
tp.(prog_main) = p.(prog_main);
match_prog_public:
tp.(prog_public) = p.(prog_public);
match_prog_def:
forall id,
(prog_defmap tp)!id = if IS.mem id u then (prog_defmap p)!id else
option_map remove_gfun (prog_defmap p)!id;
match_prog_skel:
erase_program tp = erase_program p
}.
(** This set [u] (as "used") must be closed under references, and
contain the entry point and the public identifiers of the program. *)
Definition ref_function (f: function) (id: ident) : Prop :=
exists pc i, f.(fn_code)!pc = Some i /\ In id (ref_instruction i).
Definition ref_fundef (fd: fundef) (id: ident) : Prop :=
match fd with Internal f => ref_function f id | External ef => False end.
Definition ref_init (il: list init_data) (id: ident) : Prop :=
exists ofs, In (Init_addrof id ofs) il.
Definition ref_def (gd: globdef fundef unit) (id: ident) : Prop :=
match gd with
| Gfun fd => ref_fundef fd id
| Gvar gv => ref_init gv.(gvar_init) id
end.
Record valid_used_set (p: program) (u: IS.t) : Prop := {
used_closed: forall id gd id',
IS.In id u -> (prog_defmap p)!id = Some gd -> ref_def gd id' ->
IS.In id' u;
used_main:
IS.In p.(prog_main) u;
used_public: forall id,
In id p.(prog_public) -> IS.In id u;
used_defined: forall id,
IS.In id u -> In id (prog_defs_names p) \/ id = p.(prog_main)
}.
Definition match_prog (p tp: program) : Prop :=
exists u: IS.t, valid_used_set p u /\ match_prog_1 u p tp.
(** * Properties of the static analysis *)
(** Monotonic evolution of the workset. *)
Inductive workset_incl (w1 w2: workset) : Prop :=
workset_incl_intro:
forall (SEEN: IS.Subset w1.(w_seen) w2.(w_seen))
(TODO: List.incl w1.(w_todo) w2.(w_todo))
(TRACK: forall id, IS.In id w2.(w_seen) ->
IS.In id w1.(w_seen) \/ List.In id w2.(w_todo)),
workset_incl w1 w2.
Lemma seen_workset_incl:
forall w1 w2 id, workset_incl w1 w2 -> IS.In id w1 -> IS.In id w2.
Proof.
intros. destruct H. auto.
Qed.
Lemma workset_incl_refl: forall w, workset_incl w w.
Proof.
intros; split. red; auto. red; auto. auto.
Qed.
Lemma workset_incl_trans:
forall w1 w2 w3, workset_incl w1 w2 -> workset_incl w2 w3 -> workset_incl w1 w3.
Proof.
intros. destruct H, H0; split.
red; eauto.
red; eauto.
intros. edestruct TRACK0; eauto. edestruct TRACK; eauto.
Qed.
Lemma add_workset_incl:
forall id w, workset_incl w (add_workset id w).
Proof.
unfold add_workset; intros. destruct (IS.mem id w) eqn:MEM.
- apply workset_incl_refl.
- split; simpl.
+ red; intros. apply IS.add_2; auto.
+ red; simpl; auto.
+ intros. destruct (ident_eq id id0); auto. apply IS.add_3 in H; auto.
Qed.
Lemma addlist_workset_incl:
forall l w, workset_incl w (addlist_workset l w).
Proof.
induction l; simpl; intros.
apply workset_incl_refl.
eapply workset_incl_trans. apply add_workset_incl. eauto.
Qed.
Lemma add_ref_function_incl:
forall f w, workset_incl w (add_ref_function f w).
Proof.
unfold add_ref_function; intros. apply PTree_Properties.fold_rec.
- auto.
- apply workset_incl_refl.
- intros. apply workset_incl_trans with a; auto.
unfold add_ref_instruction. apply addlist_workset_incl.
Qed.
Lemma add_ref_globvar_incl:
forall gv w, workset_incl w (add_ref_globvar gv w).
Proof.
unfold add_ref_globvar; intros.
revert w. induction (gvar_init gv); simpl; intros.
apply workset_incl_refl.
eapply workset_incl_trans; [ | eauto ].
unfold add_ref_init_data.
destruct a; (apply workset_incl_refl || apply add_workset_incl).
Qed.
Lemma add_ref_definition_incl:
forall pm id w, workset_incl w (add_ref_definition pm id w).
Proof.
unfold add_ref_definition; intros.
destruct (pm!id) as [[[] | ? ] | ].
apply add_ref_function_incl.
apply workset_incl_refl.
apply add_ref_globvar_incl.
apply workset_incl_refl.
Qed.
Lemma initial_workset_incl:
forall p, workset_incl {| w_seen := IS.empty; w_todo := nil |} (initial_workset p).
Proof.
unfold initial_workset; intros.
eapply workset_incl_trans. 2: apply add_workset_incl.
generalize {| w_seen := IS.empty; w_todo := nil |}. induction (prog_public p); simpl; intros.
apply workset_incl_refl.
eapply workset_incl_trans. apply add_workset_incl. apply IHl.
Qed.
(** Soundness properties for functions that add identifiers to the workset *)
Lemma seen_add_workset:
forall id (w: workset), IS.In id (add_workset id w).
Proof.
unfold add_workset; intros.
destruct (IS.mem id w) eqn:MEM.
apply IS.mem_2; auto.
simpl. apply IS.add_1; auto.
Qed.
Lemma seen_addlist_workset:
forall id l (w: workset),
In id l -> IS.In id (addlist_workset l w).
Proof.
induction l; simpl; intros.
tauto.
destruct H. subst a.
eapply seen_workset_incl. apply addlist_workset_incl. apply seen_add_workset.
apply IHl; auto.
Qed.
Lemma seen_add_ref_function:
forall id f w,
ref_function f id -> IS.In id (add_ref_function f w).
Proof.
intros until w. unfold ref_function, add_ref_function. apply PTree_Properties.fold_rec; intros.
- destruct H1 as (pc & i & A & B). apply H0; auto. exists pc, i; split; auto. rewrite H; auto.
- destruct H as (pc & i & A & B). rewrite PTree.gempty in A; discriminate.
- destruct H2 as (pc & i & A & B). rewrite PTree.gsspec in A. destruct (peq pc k).
+ inv A. unfold add_ref_instruction. apply seen_addlist_workset; auto.
+ unfold add_ref_instruction. eapply seen_workset_incl. apply addlist_workset_incl.
apply H1. exists pc, i; auto.
Qed.
Lemma seen_add_ref_definition:
forall pm id gd id' w,
pm!id = Some gd -> ref_def gd id' -> IS.In id' (add_ref_definition pm id w).
Proof.
unfold add_ref_definition; intros. rewrite H. red in H0; destruct gd as [[f|ef]|gv].
apply seen_add_ref_function; auto.
contradiction.
destruct H0 as (ofs & IN).
unfold add_ref_globvar.
assert (forall l (w: workset),
IS.In id' w \/ In (Init_addrof id' ofs) l ->
IS.In id' (fold_left add_ref_init_data l w)).
{
induction l; simpl; intros.
tauto.
apply IHl. intuition auto.
left. destruct a; simpl; auto. eapply seen_workset_incl. apply add_workset_incl. auto.
subst; left; simpl. apply seen_add_workset.
}
apply H0; auto.
Qed.
Lemma seen_main_initial_workset:
forall p, IS.In p.(prog_main) (initial_workset p).
Proof.
intros. apply seen_add_workset.
Qed.
Lemma seen_public_initial_workset:
forall p id, In id p.(prog_public) -> IS.In id (initial_workset p).
Proof.
intros. unfold initial_workset. eapply seen_workset_incl. apply add_workset_incl.
assert (forall l (w: workset),
IS.In id w \/ In id l -> IS.In id (fold_left (fun w id => add_workset id w) l w)).
{
induction l; simpl; intros.
tauto.
apply IHl. intuition auto; left.
eapply seen_workset_incl. apply add_workset_incl. auto.
subst a. apply seen_add_workset.
}
apply H0. auto.
Qed.
(** * Correctness of the transformation with respect to the relational specification *)
(** Correctness of the dependency graph traversal. *)
Section ANALYSIS.
Variable p: program.
Let pm := prog_defmap p.
Definition workset_invariant (w: workset) : Prop :=
forall id gd id',
IS.In id w -> ~List.In id (w_todo w) -> pm!id = Some gd -> ref_def gd id' ->
IS.In id' w.
Definition used_set_closed (u: IS.t) : Prop :=
forall id gd id',
IS.In id u -> pm!id = Some gd -> ref_def gd id' -> IS.In id' u.
Lemma iter_step_invariant:
forall w,
workset_invariant w ->
match iter_step pm w with
| inl u => used_set_closed u
| inr w' => workset_invariant w'
end.
Proof.
unfold iter_step, workset_invariant, used_set_closed; intros.
destruct (w_todo w) as [ | id rem ]; intros.
- eapply H; eauto.
- set (w' := {| w_seen := w.(w_seen); w_todo := rem |}) in *.
destruct (add_ref_definition_incl pm id w').
destruct (ident_eq id id0).
+ subst id0. eapply seen_add_ref_definition; eauto.
+ exploit TRACK; eauto. intros [A|A].
* apply SEEN. eapply H; eauto. simpl.
assert (~ In id0 rem).
{ change rem with (w_todo w'). red; intros. elim H1; auto. }
tauto.
* contradiction.
Qed.
Theorem used_globals_sound:
forall u, used_globals p pm = Some u -> used_set_closed u.
Proof.
unfold used_globals; intros. eapply PrimIter.iterate_prop with (P := workset_invariant); eauto.
- intros. apply iter_step_invariant; auto.
- destruct (initial_workset_incl p).
red; intros. edestruct TRACK; eauto.
simpl in H4. eelim IS.empty_1; eauto.
contradiction.
Qed.
Theorem used_globals_incl:
forall u, used_globals p pm = Some u -> IS.Subset (initial_workset p) u.
Proof.
unfold used_globals; intros.
eapply PrimIter.iterate_prop with (P := fun (w: workset) => IS.Subset (initial_workset p) w); eauto.
- fold pm; unfold iter_step; intros. destruct (w_todo a) as [ | id rem ].
auto.
destruct (add_ref_definition_incl pm id {| w_seen := a; w_todo := rem |}).
red; auto.
- red; auto.
Qed.
Corollary used_globals_valid:
forall u,
used_globals p pm = Some u ->
IS.for_all (global_defined p pm) u = true ->
valid_used_set p u.
Proof.
intros. constructor.
- intros. eapply used_globals_sound; eauto.
- eapply used_globals_incl; eauto. apply seen_main_initial_workset.
- intros. eapply used_globals_incl; eauto. apply seen_public_initial_workset; auto.
- intros. apply ISF.for_all_iff in H0.
+ red in H0. apply H0 in H1. unfold global_defined in H1.
destruct pm!id as [g|] eqn:E.
* left. change id with (fst (id,g)). apply in_map. apply in_prog_defmap; auto.
* InvBooleans; auto.
+ hnf. simpl; intros; congruence.
Qed.
End ANALYSIS.
(** Properties of the elimination of unused global definitions. *)
Section TRANSFORMATION.
Variable p: program.
Variable used: IS.t.
Let add_def (m: prog_map) idg := PTree.set (fst idg) (snd idg) m.
Lemma filter_globdefs_map_1:
forall id l u m1 m2,
IS.mem id u = false ->
m1! id = option_map remove_gfun m2!id ->
(fold_left add_def (filter_globdefs u l) m1)!id =
option_map remove_gfun (fold_left add_def l m2)!id.
Proof.
induction l as [ | [id1 gd1] l]; simpl; intros.
- auto.
- destruct (IS.mem id1 u) eqn:MEM.
+ apply IHl; auto.
unfold add_def at 1 2. simpl.
rewrite ! PTree.gsspec. destruct (peq id id1).
congruence. auto.
+ apply IHl; auto. unfold add_def. simpl.
rewrite ! PTree.gsspec. destruct (peq id id1). auto. auto.
Qed.
Lemma filter_globdefs_map_2:
forall id l u m1 m2,
IS.mem id u = true ->
m1!id = m2!id ->
(fold_left add_def (filter_globdefs u l) m1)!id = (fold_left add_def l m2)!id.
Proof.
induction l as [ | [id1 gd1] l]; simpl; intros.
- auto.
- simpl.
destruct (IS.mem id1 u) eqn:MEM.
+ apply IHl; auto.
unfold filter_globdefs.
unfold add_def at 1 2. simpl.
rewrite ! PTree.gsspec. destruct (peq id id1). auto. auto.
+ apply IHl; auto. unfold add_def. simpl.
destruct (peq id id1). congruence.
rewrite !PTree.gso by congruence. auto.
Qed.
Lemma filter_globdefs_map:
forall id u defs,
(PTree_Properties.of_list (filter_globdefs u defs))! id =
if IS.mem id u then (PTree_Properties.of_list defs)!id
else option_map remove_gfun (PTree_Properties.of_list defs)!id.
Proof.
intros. unfold PTree_Properties.of_list. fold prog_map. unfold PTree.elt. fold add_def.
destruct (IS.mem id u) eqn:MEM.
- apply filter_globdefs_map_2; eauto.
- apply filter_globdefs_map_1; eauto.
Qed.
End TRANSFORMATION.
Theorem transf_program_match:
forall p tp, transform_program p = OK tp -> match_prog p tp.
Proof.
intros p tp TR.
exploit transform_skel; eauto. intro SKEL.
unfold transform_program in TR. set (pm := prog_defmap p) in *.
destruct (used_globals p pm) as [u|] eqn:U; try discriminate.
destruct (IS.for_all (global_defined p pm) u) eqn:DEF; inv TR.
exists u; split.
apply used_globals_valid; auto.
constructor; simpl; auto.
intros. unfold prog_defmap; simpl.
eapply filter_globdefs_map; eauto.
Qed.
(** * Semantic preservation *)
Require Import LanguageInterface Inject.
(** The initial memory injection inferred from global symbol tables *)
Definition init_meminj (se tse: Genv.symtbl) : meminj :=
fun b =>
match Genv.invert_symbol se b with
| Some id =>
match Genv.find_symbol tse id with
| Some b' => Some (b', 0)
| None => None
end
| None => None
end.
Section SOUNDNESS.
Variable p: program.
Variable tp: program.
Variable used: IS.t.
Hypothesis USED_VALID: valid_used_set p used.
Hypothesis TRANSF: match_prog_1 used p tp.
Variable w: inj_world.
Variable se tse: Genv.symtbl.
Definition skel := erase_program p.
Definition tskel := erase_program tp.
Hypothesis GE: inj_stbls w se tse.
Hypothesis VALID: Genv.valid_for skel se.
Lemma main_symb_pres: forall b,
Genv.find_symbol se (prog_main skel) = Some b ->
exists b', Genv.find_symbol tse (prog_main tskel) = Some b'.
Proof.
intros. inv GE. inv inj_stbls_match.
exploit mge_dom; eauto. eapply Genv.genv_symb_range; eauto.
intros [b2 INJ]. exists b2.
inv TRANSF. cbn. rewrite match_prog_main0. cbn in H.
eapply mge_symb; eauto.
Qed.
Lemma symb_incl: forall id b,
Genv.find_symbol tse id = Some b -> exists b', Genv.find_symbol se id = Some b'.
Proof.
intros. inv GE.
exploit Genv.mge_img; eauto. eapply Genv.genv_symb_range; eauto.
intros [a B]. exists a. eapply Genv.mge_symb; eauto.
Qed.
Lemma info_eq: forall b b' id,
Genv.find_symbol se id = Some b ->
Genv.find_symbol tse id = Some b' ->
Genv.find_info se b = Genv.find_info tse b'.
Proof.
intros. inv GE.
exploit Genv.mge_img; eauto. eapply Genv.genv_symb_range; eauto.
intros (a & INJ).
exploit Genv.mge_symb; eauto. intro EQ.
apply EQ in H0 as H2. setoid_rewrite H in H2. inv H2.
eapply Genv.mge_info; eauto.
Qed.
(** Hypothesis about injections in the world *)
Axiom inj_preserved : forall id b,
Genv.find_symbol tse id = Some b ->
IS.mem id used = true.
Lemma map_fst_in {A B:Type}: forall (a:A) (b:B) list,
In (a,b) list -> In a (map fst list).
Proof.
intros. induction list.
- inv H.
- inv H.
left. auto.
right. eauto.
Qed.
Lemma remove_unused_consistent: forall id gd b,
(prog_defmap skel) ! id = Some gd ->
Genv.find_symbol tse id = Some b ->
(prog_defmap tskel) ! id = Some gd.
Proof.
intros. simpl.
unfold tskel in *. unfold skel in *.
rewrite erase_program_defmap in *.
unfold option_map in *.
erewrite match_prog_def; eauto.
erewrite inj_preserved; eauto.
Qed.
Lemma remove_unused_consistent_p :forall id gd b,
(prog_defmap p) ! id = Some gd ->
Genv.find_symbol tse id = Some b ->
(prog_defmap tp) ! id = Some gd.
Proof.
intros.
generalize (erase_program_defmap p id).
rewrite H. cbn [option_map].
intros DEF.
generalize (remove_unused_consistent _ _ _ DEF H0).
intros TDEF.
unfold tskel in TDEF.
rewrite erase_program_defmap in TDEF.
unfold option_map in TDEF.
destruct ((prog_defmap tp) ! id) eqn:TDEF'; try discriminate.
inv TDEF.
inv TRANSF.
rewrite (match_prog_def0 id) in TDEF'.
destruct (IS.mem id used) eqn:MEM; try discriminate.
rewrite H in TDEF'. inv TDEF'.
reflexivity.
erewrite inj_preserved in MEM; eauto. congruence.
Qed.
(** Public symbols of source and target symbol tables are the same *)
Lemma se_public_same: forall id,
Genv.public_symbol se id = Genv.public_symbol tse id.
Proof.
intros. symmetry. inv GE. inv inj_stbls_match. eauto.
Qed.
Let ge := Genv.globalenv se p.
Let tge := Genv.globalenv tse tp.
Let pm := prog_defmap p.
Definition kept (id: ident) : Prop := IS.In id used.
Lemma kept_closed:
forall id gd id',
kept id -> pm!id = Some gd -> ref_def gd id' -> kept id'.
Proof.
intros. eapply used_closed; eauto.
Qed.
Lemma kept_main:
kept p.(prog_main).
Proof.
eapply used_main; eauto.
Qed.
Lemma kept_public:
forall id, In id p.(prog_public) -> kept id.
Proof.
intros. eapply used_public; eauto.
Qed.
(** Relating [Genv.find_symbol] operations in the original and transformed program *)
Lemma transform_find_symbol_1:
forall id b,
Genv.find_symbol ge id = Some b -> kept id -> exists b', Genv.find_symbol tge id = Some b'.
Proof.
intros.
inv USED_VALID.
generalize (used_defined0 _ H0).
destruct 1 as [IN | EQ].
- exploit prog_defmap_dom; eauto.
intros (gd & DEF).
inv TRANSF.
generalize (match_prog_def0 id).
red in H0. apply IS.mem_1 in H0. rewrite H0.
rewrite DEF.
assert (match_senv (cc_c inj) w se tse).
inv GE. constructor; eauto.
eapply match_senv_valid_for in H1; eauto.
unfold skel in H1.
rewrite match_prog_def0.
rewrite H0.
rewrite (Genv.find_def_symbol id gd H1).
intros (b' & SYM & DEF').
eauto.
- subst.
erewrite <- match_prog_main; eauto.
eapply main_symb_pres; eauto.
Qed.
Lemma symbols_inject_init_public: forall id b,
Genv.public_symbol se id = true ->
Genv.find_symbol se id = Some b ->
exists b', Genv.find_symbol tse id = Some b' /\
init_meminj se tse b = Some(b', 0).
Proof.
cbn.
intros id b PUB FND.
generalize PUB; intros PUB1.
rewrite se_public_same in PUB1.
unfold Genv.public_symbol in PUB.
destruct (Genv.find_symbol se id) as [b1|] eqn:FND1; try discriminate.
cbn in *.
inv FND.
assert (sup_In b (Genv.genv_sup se)) as INBOUND.
{
unfold Genv.find_symbol in FND1.
eapply Genv.genv_symb_range; eauto.
}
unfold Genv.public_symbol in PUB1.
destruct (Genv.find_symbol tse id) as [b1|] eqn:FND2; try discriminate.
exists b1; split; auto.
unfold init_meminj.
rewrite (Genv.find_invert_symbol _ id); auto.
rewrite FND2. auto.
Qed.
(** Injections that preserve used globals. *)
Record meminj_preserves_globals (f: meminj) : Prop := {
(** Invariants for global injections *)
symbols_inject_1: forall id b b' delta,
f b = Some(b', delta) -> Genv.find_symbol ge id = Some b ->
delta = 0 /\ Genv.find_symbol tge id = Some b';
symbols_inject_3: forall id b',
Genv.find_symbol tge id = Some b' ->
exists b, Genv.find_symbol ge id = Some b /\ f b = Some(b', 0);
symbols_inject_public: forall id b,
Genv.public_symbol se id = true ->
Genv.find_symbol ge id = Some b ->
exists b', Genv.find_symbol tge id = Some b' /\ f b = Some(b', 0);
info_inject: forall b b' delta gd,
f b = Some(b', delta) -> NMap.get _ b (Genv.genv_info ge) = Some gd ->
NMap.get _ b' (Genv.genv_info tge) = Some gd /\ delta = 0;
info_rev_inject: forall b b' delta gd,
f b = Some(b', delta) -> NMap.get _ b' (Genv.genv_info tge) = Some gd ->
NMap.get _ b (Genv.genv_info ge) = Some gd /\ delta = 0;
(** Invariants for module-local injections *)
symbols_inject_2: forall id b,
kept id -> Genv.find_symbol ge id = Some b ->
exists b', Genv.find_symbol tge id = Some b' /\ f b = Some(b', 0);
defs_inject: forall b b' delta gd,
f b = Some(b', delta) -> Genv.find_def ge b = Some gd ->
Genv.find_def tge b' = Some gd /\ delta = 0 /\
(forall id, ref_def gd id -> kept id);
}.
Remark init_meminj_eq:
forall id b b',
Genv.find_symbol ge id = Some b -> Genv.find_symbol tge id = Some b' ->
init_meminj se tse b = Some(b', 0).
Proof.
intros. unfold init_meminj. erewrite Genv.find_invert_symbol by eauto.
subst tge. cbn in H0. rewrite H0. auto.
Qed.
Remark init_meminj_invert:
forall b b' delta,
init_meminj se tse b = Some(b', delta) ->
delta = 0 /\ exists id, Genv.find_symbol ge id = Some b /\ Genv.find_symbol tge id = Some b'.
Proof.
unfold init_meminj; intros.
destruct (Genv.invert_symbol se b) as [id|] eqn:S; try discriminate.
destruct (Genv.find_symbol tse id) as [b''|] eqn:F; inv H.
split. auto. exists id. split. apply Genv.invert_find_symbol; auto. auto.
Qed.
Lemma init_meminj_preserves_globals:
meminj_preserves_globals (init_meminj se tse).
Proof.
constructor; intros.
- exploit init_meminj_invert; eauto. intros (A & id1 & B & C).
assert (id1 = id) by (eapply (Genv.genv_vars_inj ge); eauto). subst id1.
auto.
- exploit symb_incl; eauto. intros (b & F).
exists b; split; auto. eapply init_meminj_eq; eauto.
- exploit symbols_inject_init_public; eauto.
- exploit init_meminj_invert; eauto. intros (A & id & B & C).
exploit info_eq; eauto.
intros EQ.
split; auto.
cbn. unfold Genv.find_info in EQ. rewrite <- EQ.
apply H0.
- exploit init_meminj_invert; eauto. intros (A & id & B & C).
exploit info_eq; eauto.
intros EQ.
split; auto.
cbn. unfold Genv.find_info in EQ. rewrite EQ.
apply H0.
- exploit transform_find_symbol_1; eauto. intros (b' & F). exists b'; split; auto.
eapply init_meminj_eq; eauto.
- exploit init_meminj_invert; eauto. intros (A & id & B & C).
unfold tge. rewrite Genv.find_def_spec.
rewrite (Genv.find_invert_symbol tse id); auto.
unfold ge in H0. rewrite Genv.find_def_spec in H0.
destruct (Genv.invert_symbol se b) eqn:INV; try discriminate.
rewrite (Genv.find_invert_symbol se id) in INV; auto.
inv INV.
generalize (erase_program_defmap p i).
rewrite H0. cbn [option_map].
intros DEF.
generalize (remove_unused_consistent _ _ _ DEF C).
intros TDEF.
unfold tskel in TDEF.
rewrite erase_program_defmap in TDEF.
unfold option_map in TDEF.
destruct ((prog_defmap tp) ! i) eqn:TDEF'; try discriminate.
inv TDEF.
inv TRANSF.
rewrite (match_prog_def0 i) in TDEF'.
destruct (IS.mem i used) eqn:MEM; try discriminate.
rewrite H0 in TDEF'. inv TDEF'.
split; auto.
split; auto.
inv USED_VALID.
intros.
apply used_closed0 with i g; eauto.
apply IS.mem_2; auto.
erewrite inj_preserved in MEM; eauto. congruence.
Qed.
Remark inj_eq:
forall id b b',
Genv.find_symbol se id = Some b -> Genv.find_symbol tse id = Some b' ->
injw_meminj w b = Some(b', 0).
Proof.
intros.
inv GE. exploit Genv.mge_img; eauto.
eapply Genv.genv_symb_range; eauto.
intros (b1 & INJ1).
exploit Genv.mge_symb; eauto.
intro EQ. apply EQ in H0 as F'.
setoid_rewrite F' in H. inv H. eauto.
Qed.
Lemma inj_world_preserves_globals:
meminj_preserves_globals w.
Proof.
constructor.
- intros. inv GE. inv inj_stbls_match.
exploit mge_dom; eauto.
eapply Genv.genv_symb_range; eauto.
intro. subst.
exploit mge_symb; eauto.
intro EQ. apply EQ in H0.
destruct H1 as [A B]. rewrite H in B. inv B.
split; eauto.
- intros. exploit symb_incl; eauto.
intros [b0 FIND]. exists b0. split. auto.
eapply inj_eq; eauto.
- intros.
exploit symbols_inject_init_public; eauto.
intros [b' [FIND _]]. exists b'. split. auto.
eapply inj_eq; eauto.
- intros. inv GE. inv inj_stbls_match. split.
erewrite <- mge_info; eauto.
exploit mge_dom; eauto.
eapply Genv.genv_info_range; eauto.
intros [b2 INJ]. rewrite H in INJ. congruence.
- intros. inv GE. inv inj_stbls_match. split.
erewrite mge_info; eauto.
exploit mge_img; eauto. eapply Genv.genv_info_range; eauto.
intros [b1 INJ].
erewrite <- mge_info in H0. 2: apply H.
exploit mge_dom; eauto.
eapply Genv.genv_info_range; eauto.
intros [b2 INJ']. rewrite H in INJ'. congruence.
- intros.
exploit transform_find_symbol_1; eauto.
intros (b' & FIND'). exists b'. split. auto.
eapply inj_eq; eauto.
- intros.
inversion GE. inversion inj_stbls_match.
unfold ge in H0. rewrite Genv.find_def_spec in H0.
destruct (Genv.invert_symbol se b) eqn:REV1; try discriminate.
apply Genv.invert_find_symbol in REV1 as FIND1.
unfold tge. rewrite Genv.find_def_spec.
exploit mge_symb; eauto. intro FINDEQ.
apply FINDEQ in FIND1 as FIND2.
apply Genv.find_invert_symbol in FIND2 as REV2.
rewrite REV2.
exploit mge_dom; eauto. eapply Genv.genv_symb_range; eauto.
intro. subst.
exploit remove_unused_consistent_p; eauto.
intro A.
split. auto. split.
destruct H1 as [b2 INJ]. rewrite H in INJ. congruence.
destruct (IS.mem i used) eqn:MEM; try discriminate.
inv USED_VALID.
intros.
apply used_closed0 with i gd; eauto.
apply IS.mem_2; eauto.
erewrite inj_preserved in MEM; eauto. congruence.
Qed.
(* generalize init_meminj_preserves_globals.
intros PRES.
constructor.
- inv PRES. intros.
eapply symbols_inject_4; eauto.
eapply winj_consistent_1; eauto.
eapply Genv.genv_symb_range; eauto.
- inv PRES. intros.
exploit symbols_inject_5; eauto.
intros (b & FND & INIT).
exists b; split; auto.
- inv PRES. intros.
exploit symbols_inject_public0; eauto.
intros (b' & FND & INIT).
exists b'; split; auto.
- inv PRES. intros.
eapply info_inject0; eauto.
eapply winj_consistent_1; eauto.
eapply Genv.genv_info_range; eauto.
- inv PRES. intros.
exploit info_rev_inject0; eauto.
eapply winj_consistent_2; eauto.
eapply Genv.genv_info_range; eauto.
- inv PRES. intros.
exploit symbols_inject_6; eauto.
intros (b' & FND & INIT).
exists b'; split; auto.
- inv PRES. intros.
eapply defs_inject0; eauto.
eapply winj_consistent_1; eauto.
exploit Genv.genv_defs_range; eauto.
Qed.
*)
Lemma globals_symbols_inject:
forall j, meminj_preserves_globals j -> symbols_inject j ge tge.
Proof.
intros.
split; [|split;[|split]]; intros.
+ unfold ge, tge. cbn.
rewrite se_public_same. auto.
+ eapply symbols_inject_1; eauto.
+ exploit symbols_inject_public; eauto.
intros (b' & FND & INJ).
eauto.
+ unfold Genv.block_is_volatile.
destruct (NMap.get _ b1 (Genv.genv_info ge)) as [gd|] eqn:V1.
- generalize (info_inject _ H _ _ _ _ H0 V1); eauto.
intros (V2 & D). subst.
rewrite V2. auto.
- destruct (NMap.get _ b2 (Genv.genv_info tge)) as [gd2|] eqn:V2; auto.
destruct gd2; auto.
generalize (info_rev_inject _ H _ _ _ _ H0 V2).
intros (V3 & D). subst.
rewrite V1 in V3. discriminate.
Qed.
Lemma symbol_address_inject:
forall j id ofs,
meminj_preserves_globals j -> kept id ->
Val.inject j (Genv.symbol_address ge id ofs) (Genv.symbol_address tge id ofs).
Proof.
intros. unfold Genv.symbol_address. destruct (Genv.find_symbol ge id) as [b|] eqn:FS; auto.
exploit symbols_inject_2; eauto. intros (b' & TFS & INJ). rewrite TFS.
econstructor; eauto. rewrite Ptrofs.add_zero; auto.
Qed.
(** Semantic preservation *)
Definition regset_inject (f: meminj) (rs rs': regset): Prop :=
forall r, Val.inject f rs#r rs'#r.
Lemma regs_inject:
forall f rs rs', regset_inject f rs rs' -> forall l, Val.inject_list f rs##l rs'##l.
Proof.
induction l; simpl. constructor. constructor; auto.
Qed.
Lemma set_reg_inject:
forall f rs rs' r v v',
regset_inject f rs rs' -> Val.inject f v v' ->
regset_inject f (rs#r <- v) (rs'#r <- v').
Proof.
intros; red; intros. rewrite ! Regmap.gsspec. destruct (peq r0 r); auto.
Qed.
Lemma set_res_inject:
forall f rs rs' res v v',
regset_inject f rs rs' -> Val.inject f v v' ->
regset_inject f (regmap_setres res v rs) (regmap_setres res v' rs').
Proof.
intros. destruct res; auto. apply set_reg_inject; auto.
Qed.
Lemma regset_inject_incr:
forall f f' rs rs', regset_inject f rs rs' -> inject_incr f f' -> regset_inject f' rs rs'.
Proof.
intros; red; intros. apply val_inject_incr with f; auto.
Qed.
Lemma regset_undef_inject:
forall f, regset_inject f (Regmap.init Vundef) (Regmap.init Vundef).
Proof.
intros; red; intros. rewrite Regmap.gi. auto.
Qed.
Lemma init_regs_inject:
forall f args args', Val.inject_list f args args' ->
forall params,
regset_inject f (init_regs args params) (init_regs args' params).
Proof.
induction 1; intros; destruct params; simpl; try (apply regset_undef_inject).
apply set_reg_inject; auto.
Qed.
Inductive match_stacks (j: meminj):
list stackframe -> list stackframe -> sup -> sup -> Prop :=
| match_stacks_nil: forall bound tbound,
meminj_preserves_globals j ->
inj_incr w (injw j bound tbound) ->
Mem.sup_include (Genv.genv_sup ge) bound -> Mem.sup_include (Genv.genv_sup tge) tbound ->
match_stacks j nil nil bound tbound
| match_stacks_cons: forall res f sp pc rs s tsp trs ts bound tbound sps tsps
(SPS: sp = fresh_block sps)
(TSPS: tsp = fresh_block tsps)
(STACKS: match_stacks j s ts sps tsps)
(KEPT: forall id, ref_function f id -> kept id)
(SPINJ: j sp = Some(tsp, 0))
(REGINJ: regset_inject j rs trs)
(BELOW: Mem.sup_include (sup_incr sps) bound)
(TBELOW: Mem.sup_include (sup_incr tsps) tbound),
match_stacks j (Stackframe res f (Vptr sp Ptrofs.zero) pc rs :: s)
(Stackframe res f (Vptr tsp Ptrofs.zero) pc trs :: ts)
bound tbound.
Lemma match_stacks_bound1: forall j s ts sps tsps,
match_stacks j s ts sps tsps -> Mem.sup_include (Genv.genv_sup se) sps.
Proof.
induction 1; auto.
eapply Mem.sup_include_trans; eauto.
Qed.
Lemma match_stacks_bound2: forall j s ts sps tsps,
match_stacks j s ts sps tsps -> Mem.sup_include (Genv.genv_sup tse) tsps.
Proof.
induction 1; auto.
eapply Mem.sup_include_trans; eauto.
Qed.
Lemma match_stacks_incr_bound
: forall (j : meminj) s ts
(bound tbound : sup) (bound' tbound' : sup),
match_stacks j s ts bound tbound ->
Mem.sup_include bound bound' ->
Mem.sup_include tbound tbound' -> match_stacks j s ts bound' tbound'.
Proof.
intros. inv H. inv H3.
econstructor; eauto. rewrite <- H9. econstructor; eauto.
econstructor; eauto.
Qed.
Lemma match_stacks_match_stbls:
forall j s ts sp tsp,
CKLR.match_stbls inj w se tse ->
match_stacks j s ts sp tsp ->
Genv.match_stbls j se tse.
Proof.
induction 2; eauto.
generalize (CKLR.match_stbls_acc inj). cbn.
intros MONO.
repeat red in MONO.
generalize (MONO _ _ H1 se tse). intros SUB.
apply SUB.
apply H.
Qed.
Lemma match_stacks_preserves_globals:
forall j s ts bound tbound,
match_stacks j s ts bound tbound ->
meminj_preserves_globals j.
Proof.
induction 1; auto.
Qed.
Lemma meminj_preserves_globals_incr: forall j j' bound tbound,
inject_incr j j' ->
Mem.sup_include (Genv.genv_sup ge) bound ->
Mem.sup_include (Genv.genv_sup tge) tbound ->
(forall b1 b2 delta,
j b1 = None -> j' b1 = Some(b2, delta) -> ~sup_In b1 bound /\ ~ sup_In b2 tbound) ->
meminj_preserves_globals j ->
meminj_preserves_globals j'.
Proof.
intros j j' bound tbound INCR BND1 BND2 SEP PRES.
assert (SAME: forall b b' delta, sup_In b (Genv.genv_sup ge) ->
j' b = Some(b', delta) -> j b = Some(b', delta)).
{ intros. destruct (j b) as [[b1 delta1] | ] eqn: J.
exploit INCR; eauto. congruence.
exploit SEP; eauto. intros [A B].
exfalso. apply A. apply BND1; eauto. }
assert (SAME': forall b b' delta, sup_In b' (Genv.genv_sup tge) ->
j' b = Some(b', delta) -> j b = Some (b', delta)).