summaryrefslogtreecommitdiff
path: root/backend/CSEproof.v
blob: 6543826487115286b9c217679e7b80201f0c0696 (plain)
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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
(* *********************************************************************)
(*                                                                     *)
(*              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.     *)
(*                                                                     *)
(* *********************************************************************)

(** Correctness proof for common subexpression elimination. *)

Require Import Coqlib.
Require Import Maps.
Require Import AST.
Require Import Errors.
Require Import Integers.
Require Import Floats.
Require Import Values.
Require Import Memory.
Require Import Events.
Require Import Globalenvs.
Require Import Smallstep.
Require Import Op.
Require Import Registers.
Require Import RTL.
Require Import RTLtyping.
Require Import Kildall.
Require Import CSE.

(** * Semantic properties of value numberings *)

(** ** Well-formedness of numberings *)

(** A numbering is well-formed if all registers mentioned in equations
  are less than the ``next'' register number given in the numbering.
  This guarantees that the next register is fresh with respect to
  the equations. *)

Definition wf_rhs (next: valnum) (rh: rhs) : Prop :=
  match rh with
  | Op op vl => forall v, In v vl -> Plt v next
  | Load chunk addr vl => forall v, In v vl -> Plt v next
  end.

Definition wf_equation (next: valnum) (vr: valnum) (rh: rhs) : Prop :=
  Plt vr next /\ wf_rhs next rh.

Definition wf_numbering (n: numbering) : Prop :=
  (forall v rh,
    In (v, rh) n.(num_eqs) -> wf_equation n.(num_next) v rh)
/\
  (forall r v,
    PTree.get r n.(num_reg) = Some v -> Plt v n.(num_next)).

Lemma wf_empty_numbering:
  wf_numbering empty_numbering.
Proof.
  unfold empty_numbering; split; simpl; intros.
  elim H.
  rewrite PTree.gempty in H. congruence.
Qed.

Lemma wf_rhs_increasing:
  forall next1 next2 rh,
  Ple next1 next2 ->
  wf_rhs next1 rh -> wf_rhs next2 rh.
Proof.
  intros; destruct rh; simpl; intros; apply Plt_Ple_trans with next1; auto.
Qed.

Lemma wf_equation_increasing:
  forall next1 next2 vr rh,
  Ple next1 next2 ->
  wf_equation next1 vr rh -> wf_equation next2 vr rh.
Proof.
  intros. elim H0; intros. split. 
  apply Plt_Ple_trans with next1; auto.
  apply wf_rhs_increasing with next1; auto.
Qed.

(** We now show that all operations over numberings 
  preserve well-formedness. *)

Lemma wf_valnum_reg:
  forall n r n' v,
  wf_numbering n ->
  valnum_reg n r = (n', v) ->
  wf_numbering n' /\ Plt v n'.(num_next) /\ Ple n.(num_next) n'.(num_next).
Proof.
  intros until v. intros WF. inversion WF.
  generalize (H0 r v).
  unfold valnum_reg. destruct ((num_reg n)!r).
  intros. replace n' with n. split. auto. 
  split. apply H1. congruence. 
  apply Ple_refl.
  congruence. 
  intros. inversion H2. simpl. split.
  split; simpl; intros. 
  apply wf_equation_increasing with (num_next n). apply Ple_succ. auto. 
  rewrite PTree.gsspec in H3. destruct (peq r0 r). 
  replace v0 with (num_next n). apply Plt_succ. congruence.
  apply Plt_trans_succ; eauto. 
  split. apply Plt_succ. apply Ple_succ.
Qed.

Lemma wf_valnum_regs:
  forall rl n n' vl,
  wf_numbering n ->
  valnum_regs n rl = (n', vl) ->
  wf_numbering n' /\
  (forall v, In v vl -> Plt v n'.(num_next)) /\
  Ple n.(num_next) n'.(num_next).
Proof.
  induction rl; intros.
  simpl in H0. inversion H0. subst n'; subst vl. 
  simpl. intuition. 
  simpl in H0. 
  caseEq (valnum_reg n a). intros n1 v1 EQ1.
  caseEq (valnum_regs n1 rl). intros ns vs EQS.
  rewrite EQ1 in H0; rewrite EQS in H0; simpl in H0.
  inversion H0. subst n'; subst vl. 
  generalize (wf_valnum_reg _ _ _ _ H EQ1); intros [A1 [B1 C1]].
  generalize (IHrl _ _ _ A1 EQS); intros [As [Bs Cs]].
  split. auto.
  split. simpl; intros. elim H1; intro.
    subst v. eapply Plt_Ple_trans; eauto.
    auto.
  eapply Ple_trans; eauto.
Qed.

Lemma find_valnum_rhs_correct:
  forall rh vn eqs,
  find_valnum_rhs rh eqs = Some vn -> In (vn, rh) eqs.
Proof.
  induction eqs; simpl.
  congruence.
  case a; intros v r'. case (eq_rhs rh r'); intro.
  intro. left. congruence.
  intro. right. auto.
Qed.

Lemma wf_add_rhs:
  forall n rd rh,
  wf_numbering n ->
  wf_rhs n.(num_next) rh ->
  wf_numbering (add_rhs n rd rh).
Proof.
  intros. inversion H. unfold add_rhs. 
  caseEq (find_valnum_rhs rh n.(num_eqs)); intros.
  split; simpl. assumption. 
  intros r v0. rewrite PTree.gsspec. case (peq r rd); intros.
  inversion H4. subst v0. 
  elim (H1 v rh (find_valnum_rhs_correct _ _ _ H3)). auto.
  eauto.
  split; simpl.
  intros v rh0 [A1|A2]. inversion A1. subst rh0. 
  split. apply Plt_succ. apply wf_rhs_increasing with n.(num_next).
  apply Ple_succ. auto.
  apply wf_equation_increasing with n.(num_next). apply Ple_succ. auto.
  intros r v. rewrite PTree.gsspec. case (peq r rd); intro.
  intro. inversion H4. apply Plt_succ.
  intro. apply Plt_trans_succ. eauto. 
Qed.

Lemma wf_add_op:
  forall n rd op rs,
  wf_numbering n ->
  wf_numbering (add_op n rd op rs).
Proof.
  intros. unfold add_op. 
  case (is_move_operation op rs).
  intro r. caseEq (valnum_reg n r); intros n' v EQ.
  destruct (wf_valnum_reg _ _ _ _ H EQ) as [[A1 A2] [B C]].
  split; simpl. assumption. intros until v0. rewrite PTree.gsspec.
  case (peq r0 rd); intros. replace v0 with v. auto. congruence.
  eauto.
  caseEq (valnum_regs n rs). intros n' vl EQ. 
  generalize (wf_valnum_regs _ _ _ _ H EQ). intros [A [B C]].
  apply wf_add_rhs; auto.
Qed.

Lemma wf_add_load:
  forall n rd chunk addr rs,
  wf_numbering n ->
  wf_numbering (add_load n rd chunk addr rs).
Proof.
  intros. unfold add_load. 
  caseEq (valnum_regs n rs). intros n' vl EQ. 
  generalize (wf_valnum_regs _ _ _ _ H EQ). intros [A [B C]].
  apply wf_add_rhs; auto.
Qed.

Lemma wf_add_unknown:
  forall n rd,
  wf_numbering n ->
  wf_numbering (add_unknown n rd).
Proof.
  intros. inversion H. unfold add_unknown. constructor; simpl.
  intros. eapply wf_equation_increasing; eauto. auto with coqlib. 
  intros until v. rewrite PTree.gsspec. case (peq r rd); intros.
  inversion H2. auto with coqlib.
  apply Plt_trans_succ. eauto.
Qed.

Remark kill_eqs_in:
  forall pred v rhs eqs,
  In (v, rhs) (kill_eqs pred eqs) -> In (v, rhs) eqs /\ pred rhs = false.
Proof.
  induction eqs; simpl; intros. 
  tauto.
  destruct (pred (snd a)) as []_eqn. 
  exploit IHeqs; eauto. tauto. 
  simpl in H; destruct H. subst a. auto. exploit IHeqs; eauto. tauto. 
Qed.

Lemma wf_kill_equations:
  forall pred n, wf_numbering n -> wf_numbering (kill_equations pred n).
Proof.
  intros. inversion H. unfold kill_equations; split; simpl; intros.
  exploit kill_eqs_in; eauto. intros [A B]. auto. 
  eauto.
Qed.

Lemma wf_add_store:
  forall n chunk addr rargs rsrc,
  wf_numbering n -> wf_numbering (add_store n chunk addr rargs rsrc).
Proof.
  intros. unfold add_store. 
  destruct (valnum_regs n rargs) as [n1 vargs]_eqn.
  exploit wf_valnum_regs; eauto. intros [A [B C]].
  assert (wf_numbering (kill_equations (filter_after_store chunk addr vargs) n1)).
    apply wf_kill_equations. auto.
  destruct chunk; auto; apply wf_add_rhs; auto.
Qed.

Lemma wf_transfer:
  forall f pc n, wf_numbering n -> wf_numbering (transfer f pc n).
Proof.
  intros. unfold transfer. 
  destruct (f.(fn_code)!pc); auto.
  destruct i; auto.
  apply wf_add_op; auto.
  apply wf_add_load; auto.
  apply wf_add_store; auto.
  apply wf_empty_numbering.
  apply wf_empty_numbering.
  apply wf_add_unknown. apply wf_kill_equations; auto.
Qed.

(** As a consequence, the numberings computed by the static analysis
  are well formed. *)

Theorem wf_analyze:
  forall f approx pc, analyze f = Some approx -> wf_numbering approx!!pc.
Proof.
  unfold analyze; intros.
  eapply Solver.fixpoint_invariant with (P := wf_numbering); eauto.
  exact wf_empty_numbering.   
  exact (wf_transfer f).
Qed.

(** ** Properties of satisfiability of numberings *)

Module ValnumEq.
  Definition t := valnum.
  Definition eq := peq.
End ValnumEq.

Module VMap := EMap(ValnumEq).

Section SATISFIABILITY.

Variable ge: genv.
Variable sp: val.

(** Agremment between two mappings from value numbers to values
  up to a given value number. *)

Definition valu_agree (valu1 valu2: valnum -> val) (upto: valnum) : Prop :=
  forall v, Plt v upto -> valu2 v = valu1 v.

Lemma valu_agree_refl:
  forall valu upto, valu_agree valu valu upto.
Proof.
  intros; red; auto.
Qed.

Lemma valu_agree_trans:
  forall valu1 valu2 valu3 upto12 upto23,
  valu_agree valu1 valu2 upto12 ->
  valu_agree valu2 valu3 upto23 ->
  Ple upto12 upto23 ->
  valu_agree valu1 valu3 upto12.
Proof.
  intros; red; intros. transitivity (valu2 v).
  apply H0. apply Plt_Ple_trans with upto12; auto.
  apply H; auto.
Qed.

Lemma valu_agree_list:
  forall valu1 valu2 upto vl,
  valu_agree valu1 valu2 upto ->
  (forall v, In v vl -> Plt v upto) ->
  map valu2 vl = map valu1 vl.
Proof.
  intros. apply list_map_exten. intros. symmetry. apply H. auto.
Qed.

(** The [numbering_holds] predicate (defined in file [CSE]) is
  extensional with respect to [valu_agree]. *)

Lemma numbering_holds_exten:
  forall valu1 valu2 n rs m,
  valu_agree valu1 valu2 n.(num_next) ->
  wf_numbering n ->
  numbering_holds valu1 ge sp rs m n ->
  numbering_holds valu2 ge sp rs m n.
Proof.
  intros. inversion H0. inversion H1. split; intros.
  generalize (H2 _ _ H6). intro WFEQ.
  generalize (H4 _ _ H6). 
  unfold equation_holds; destruct rh.
  elim WFEQ; intros.
  rewrite (valu_agree_list valu1 valu2 n.(num_next)). 
  rewrite H. auto. auto. auto. exact H8. 
  elim WFEQ; intros.
  rewrite (valu_agree_list valu1 valu2 n.(num_next)). 
  rewrite H. auto. auto. auto. exact H8. 
  rewrite H. auto. eauto.
Qed.

(** [valnum_reg] and [valnum_regs] preserve the [numbering_holds] predicate.
  Moreover, it is always the case that the returned value number has
  the value of the given register in the final assignment of values to
  value numbers. *)

Lemma valnum_reg_holds:
  forall valu1 rs n r n' v m,
  wf_numbering n ->
  numbering_holds valu1 ge sp rs m n ->
  valnum_reg n r = (n', v) ->
  exists valu2,
    numbering_holds valu2 ge sp rs m n' /\
    valu2 v = rs#r /\
    valu_agree valu1 valu2 n.(num_next).
Proof.
  intros until v. unfold valnum_reg. 
  caseEq (n.(num_reg)!r).
  (* Register already has a value number *)
  intros. inversion H2. subst n'; subst v0. 
  inversion H1. 
  exists valu1. split. auto. 
  split. symmetry. auto.
  apply valu_agree_refl.
  (* Register gets a fresh value number *)
  intros. inversion H2. subst n'. subst v. inversion H1.
  set (valu2 := VMap.set n.(num_next) rs#r valu1).
  assert (AG: valu_agree valu1 valu2 n.(num_next)).
    red; intros. unfold valu2. apply VMap.gso. 
    auto with coqlib.
  destruct (numbering_holds_exten _ _ _ _ _ AG H0 H1) as [A B].
  exists valu2. 
  split. split; simpl; intros. auto. 
  unfold valu2, VMap.set, ValnumEq.eq. 
  rewrite PTree.gsspec in H5. destruct (peq r0 r).
  inv H5. rewrite peq_true. auto.
  rewrite peq_false. auto. 
  assert (Plt vn (num_next n)). inv H0. eauto. 
  red; intros; subst; eapply Plt_strict; eauto. 
  split. unfold valu2. rewrite VMap.gss. auto. 
  auto.
Qed.

Lemma valnum_regs_holds:
  forall rs rl valu1 n n' vl m,
  wf_numbering n ->
  numbering_holds valu1 ge sp rs m n ->
  valnum_regs n rl = (n', vl) ->
  exists valu2,
    numbering_holds valu2 ge sp rs m n' /\
    List.map valu2 vl = rs##rl /\
    valu_agree valu1 valu2 n.(num_next).
Proof.
  induction rl; simpl; intros.
  (* base case *)
  inversion H1; subst n'; subst vl.
  exists valu1. split. auto. split. auto. apply valu_agree_refl.
  (* inductive case *)
  caseEq (valnum_reg n a); intros n1 v1 EQ1.
  caseEq (valnum_regs n1 rl); intros ns vs EQs.
  rewrite EQ1 in H1; rewrite EQs in H1. inversion H1. subst vl; subst n'.
  generalize (valnum_reg_holds _ _ _ _ _ _ _ H H0 EQ1).
  intros [valu2 [A [B C]]].
  generalize (wf_valnum_reg _ _ _ _ H EQ1). intros [D [E F]].
  generalize (IHrl _ _ _ _ _ D A EQs). 
  intros [valu3 [P [Q R]]].
  exists valu3. 
  split. auto. 
  split. simpl. rewrite R. congruence. auto.
  eapply valu_agree_trans; eauto.
Qed.

(** A reformulation of the [equation_holds] predicate in terms
  of the value to which a right-hand side of an equation evaluates. *)

Definition rhs_evals_to
    (valu: valnum -> val) (rh: rhs) (m: mem) (v: val) : Prop :=
  match rh with
  | Op op vl => 
      eval_operation ge sp op (List.map valu vl) m = Some v
  | Load chunk addr vl =>
      exists a,
      eval_addressing ge sp addr (List.map valu vl) = Some a /\
      Mem.loadv chunk m a = Some v
  end.

Lemma equation_evals_to_holds_1:
  forall valu rh v vres m,
  rhs_evals_to valu rh m v ->
  equation_holds valu ge sp m vres rh ->
  valu vres = v.
Proof.
  intros until m. unfold rhs_evals_to, equation_holds.
  destruct rh. congruence.
  intros [a1 [A1 B1]] [a2 [A2 B2]]. congruence.
Qed.

Lemma equation_evals_to_holds_2:
  forall valu rh v vres m,
  wf_rhs vres rh ->
  rhs_evals_to valu rh m v ->
  equation_holds (VMap.set vres v valu) ge sp m vres rh.
Proof.
  intros until m. unfold wf_rhs, rhs_evals_to, equation_holds.
  rewrite VMap.gss. 
  assert (forall vl: list valnum,
            (forall v, In v vl -> Plt v vres) ->
            map (VMap.set vres v valu) vl = map valu vl).
    intros. apply list_map_exten. intros. 
    symmetry. apply VMap.gso. apply Plt_ne. auto.
  destruct rh; intros; rewrite H; auto.
Qed.

(** The numbering obtained by adding an equation [rd = rhs] is satisfiable
  in a concrete register set where [rd] is set to the value of [rhs]. *)

Lemma add_rhs_satisfiable_gen:
  forall n rh valu1 rs rd rs' m,
  wf_numbering n ->
  wf_rhs n.(num_next) rh ->
  numbering_holds valu1 ge sp rs m n ->
  rhs_evals_to valu1 rh m (rs'#rd) ->
  (forall r, r <> rd -> rs'#r = rs#r) ->
  numbering_satisfiable ge sp rs' m (add_rhs n rd rh).
Proof.
  intros. unfold add_rhs. 
  caseEq (find_valnum_rhs rh n.(num_eqs)).
  (* RHS found *)
  intros vres FINDVN. inversion H1.
  exists valu1. split; simpl; intros.
  auto. 
  rewrite PTree.gsspec in H6.
  destruct (peq r rd).
  inv H6. 
  symmetry. eapply equation_evals_to_holds_1; eauto.
  apply H4. apply find_valnum_rhs_correct. congruence.
  rewrite H3; auto.
  (* RHS not found *)
  intro FINDVN. 
  set (valu2 := VMap.set n.(num_next) (rs'#rd) valu1).
  assert (AG: valu_agree valu1 valu2 n.(num_next)).
    red; intros. unfold valu2. apply VMap.gso. 
    auto with coqlib.
  elim (numbering_holds_exten _ _ _ _ _ AG H H1); intros.
  exists valu2. split; simpl; intros.
  destruct H6. 
  inv H6. unfold valu2. eapply equation_evals_to_holds_2; eauto. auto. 
  rewrite PTree.gsspec in H6. destruct (peq r rd).
  unfold valu2. inv H6. rewrite VMap.gss. auto.
  rewrite H3; auto.
Qed.

Lemma add_rhs_satisfiable:
  forall n rh valu1 rs rd v m,
  wf_numbering n ->
  wf_rhs n.(num_next) rh ->
  numbering_holds valu1 ge sp rs m n ->
  rhs_evals_to valu1 rh m v ->
  numbering_satisfiable ge sp (rs#rd <- v) m (add_rhs n rd rh).
Proof.
  intros. eapply add_rhs_satisfiable_gen; eauto. 
  rewrite Regmap.gss; auto.
  intros. apply Regmap.gso; auto.
Qed.

(** [add_op] returns a numbering that is satisfiable in the register
  set after execution of the corresponding [Iop] instruction. *)

Lemma add_op_satisfiable:
  forall n rs op args dst v m,
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  eval_operation ge sp op rs##args m = Some v ->
  numbering_satisfiable ge sp (rs#dst <- v) m (add_op n dst op args).
Proof.
  intros. inversion H0.
  unfold add_op.
  caseEq (@is_move_operation reg op args).
  intros arg EQ. 
  destruct (is_move_operation_correct _ _ EQ) as [A B]. subst op args.
  caseEq (valnum_reg n arg). intros n1 v1 VL.
  generalize (valnum_reg_holds _ _ _ _ _ _ _ H H2 VL). intros [valu2 [A [B C]]].
  generalize (wf_valnum_reg _ _ _ _ H VL). intros [D [E F]].  
  elim A; intros. exists valu2; split; simpl; intros.
  auto. rewrite Regmap.gsspec. rewrite PTree.gsspec in H5.
  destruct (peq r dst). simpl in H1. congruence. auto.
  intro NEQ. caseEq (valnum_regs n args). intros n1 vl VRL.
  generalize (valnum_regs_holds _ _ _ _ _ _ _ H H2 VRL). intros [valu2 [A [B C]]].
  generalize (wf_valnum_regs _ _ _ _ H VRL). intros [D [E F]].
  apply add_rhs_satisfiable with valu2; auto.
  simpl. congruence. 
Qed.

(** [add_load] returns a numbering that is satisfiable in the register
  set after execution of the corresponding [Iload] instruction. *)

Lemma add_load_satisfiable:
  forall n rs chunk addr args dst a v m,
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  eval_addressing ge sp addr rs##args = Some a ->
  Mem.loadv chunk m a = Some v ->
  numbering_satisfiable ge sp (rs#dst <- v) m (add_load n dst chunk addr args).
Proof.
  intros. inversion H0.
  unfold add_load.
  caseEq (valnum_regs n args). intros n1 vl VRL.
  generalize (valnum_regs_holds _ _ _ _ _ _ _ H H3 VRL). intros [valu2 [A [B C]]].
  generalize (wf_valnum_regs _ _ _ _ H VRL). intros [D [E F]].
  apply add_rhs_satisfiable with valu2; auto.
  simpl. exists a; split; congruence. 
Qed.

(** [add_unknown] returns a numbering that is satisfiable in the
  register set after setting the target register to any value. *)

Lemma add_unknown_satisfiable:
  forall n rs dst v m,
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  numbering_satisfiable ge sp (rs#dst <- v) m (add_unknown n dst).
Proof.
  intros. destruct H0 as [valu A]. 
  set (valu' := VMap.set n.(num_next) v valu).
  assert (numbering_holds valu' ge sp rs m n). 
    eapply numbering_holds_exten; eauto.
    unfold valu'; red; intros. apply VMap.gso. auto with coqlib.
  destruct H0 as [B C].
  exists valu'; split; simpl; intros.
  eauto.
  rewrite PTree.gsspec in H0. rewrite Regmap.gsspec. 
  destruct (peq r dst). inversion H0. unfold valu'. rewrite VMap.gss; auto.
  eauto.
Qed.

(** Satisfiability of [kill_equations]. *)

Lemma kill_equations_holds:
  forall pred valu n rs m m',
  (forall v r,
   equation_holds valu ge sp m v r -> pred r = false -> equation_holds valu ge sp m' v r) ->
  numbering_holds valu ge sp rs m n ->
  numbering_holds valu ge sp rs m' (kill_equations pred n).
Proof.
  intros. destruct H0 as [A B]. red; simpl. split; intros. 
  exploit kill_eqs_in; eauto. intros [C D]. eauto. 
  auto.
Qed.

(** [kill_loads] preserves satisfiability.  Moreover, the resulting numbering
  is satisfiable in any concrete memory state. *)

Lemma kill_loads_satisfiable:
  forall n rs m m',
  numbering_satisfiable ge sp rs m n ->
  numbering_satisfiable ge sp rs m' (kill_loads n).
Proof.
  intros. destruct H as [valu A]. exists valu. eapply kill_equations_holds with (m := m); eauto.
  intros. destruct r; simpl in *. rewrite <- H. apply op_depends_on_memory_correct; auto. 
  congruence.
Qed.

(** [add_store] returns a numbering that is satisfiable in the memory state
  after execution of the corresponding [Istore] instruction. *)

Lemma add_store_satisfiable:
  forall n rs chunk addr args src a m m',
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  eval_addressing ge sp addr rs##args = Some a ->
  Mem.storev chunk m a (rs#src) = Some m' ->
  Val.has_type (rs#src) (type_of_chunk chunk) ->
  numbering_satisfiable ge sp rs m' (add_store n chunk addr args src).
Proof.
  intros. unfold add_store. destruct H0 as [valu A].
  destruct (valnum_regs n args) as [n1 vargs]_eqn.
  exploit valnum_regs_holds; eauto. intros [valu' [B [C D]]].
  exploit wf_valnum_regs; eauto. intros [U [V W]].
  set (n2 := kill_equations (filter_after_store chunk addr vargs) n1).
  assert (numbering_holds valu' ge sp rs m' n2).
    apply kill_equations_holds with (m := m); auto.
    intros. destruct r; simpl in *. 
    rewrite <- H0. apply op_depends_on_memory_correct; auto.
    destruct H0 as [a' [P Q]]. 
    destruct (eq_list_valnum vargs l); simpl in H4; try congruence. subst l.
    rewrite negb_false_iff in H4.
    exists a'; split; auto. 
    destruct a; simpl in H2; try congruence.
    destruct a'; simpl in Q; try congruence.
    simpl. rewrite <- Q. 
    rewrite C in P. eapply Mem.load_store_other; eauto.
    exploit addressing_separated_sound; eauto. intuition congruence.
  assert (N2: numbering_satisfiable ge sp rs m' n2).
    exists valu'; auto.
  set (n3 := add_rhs n2 src (Load chunk addr vargs)).
  assert (N3: Val.load_result chunk (rs#src) = rs#src -> numbering_satisfiable ge sp rs m' n3).
    intro EQ. unfold n3. apply add_rhs_satisfiable_gen with valu' rs.
    apply wf_kill_equations; auto.
    red. auto. auto.
    red. exists a; split. congruence. 
    rewrite <- EQ. destruct a; simpl in H2; try discriminate. simpl. 
    eapply Mem.load_store_same; eauto. 
    auto.
  destruct chunk; auto; apply N3. 
  simpl in H3. destruct (rs#src); auto || contradiction.
  simpl in H3. destruct (rs#src); auto || contradiction.
Qed.

(** Correctness of [reg_valnum]: if it returns a register [r],
  that register correctly maps back to the given value number. *)

Lemma reg_valnum_correct:
  forall n v r, reg_valnum n v = Some r -> n.(num_reg)!r = Some v.
Proof.
  intros until r. unfold reg_valnum. rewrite PTree.fold_spec.
  assert(forall l acc0,
    List.fold_left
     (fun (acc: option reg) (p: reg * valnum) => 
        if peq (snd p) v then Some (fst p) else acc)
     l acc0 = Some r ->
     In (r, v) l \/ acc0 = Some r).
  induction l; simpl.
  intros. tauto.
  case a; simpl; intros r1 v1 acc0 FL.
  generalize (IHl _ FL). 
  case (peq v1 v); intro. 
    subst v1. intros [A|B]. tauto. inversion B; subst r1. tauto.
    tauto.
  intro. elim (H _ _ H0); intro. 
  apply PTree.elements_complete; auto.
  discriminate.
Qed.

(** Correctness of [find_op] and [find_load]: if successful and in a
  satisfiable numbering, the returned register does contain the 
  result value of the operation or memory load. *)

Lemma find_rhs_correct:
  forall valu rs m n rh r,
  numbering_holds valu ge sp rs m n ->
  find_rhs n rh = Some r ->
  rhs_evals_to valu rh m rs#r.
Proof.
  intros until r.  intros NH. 
  unfold find_rhs. 
  caseEq (find_valnum_rhs rh n.(num_eqs)); intros.
  generalize (find_valnum_rhs_correct _ _ _ H); intro.
  generalize (reg_valnum_correct _ _ _ H0); intro.
  inversion NH. 
  generalize (H3 _ _ H1). rewrite (H4 _ _ H2). 
  destruct rh; simpl; auto.
  discriminate.
Qed.

Lemma find_op_correct:
  forall rs m n op args r,
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  find_op n op args = Some r ->
  eval_operation ge sp op rs##args m = Some rs#r.
Proof.
  intros until r. intros WF [valu NH].
  unfold find_op. caseEq (valnum_regs n args). intros n' vl VR FIND.
  generalize (valnum_regs_holds _ _ _ _ _ _ _ WF NH VR).
  intros [valu2 [NH2 [EQ AG]]].
  rewrite <- EQ. 
  change (rhs_evals_to valu2 (Op op vl) m rs#r).
  eapply find_rhs_correct; eauto.
Qed.

Lemma find_load_correct:
  forall rs m n chunk addr args r,
  wf_numbering n ->
  numbering_satisfiable ge sp rs m n ->
  find_load n chunk addr args = Some r ->
  exists a,
  eval_addressing ge sp addr rs##args = Some a /\
  Mem.loadv chunk m a = Some rs#r.
Proof.
  intros until r. intros WF [valu NH].
  unfold find_load. caseEq (valnum_regs n args). intros n' vl VR FIND.
  generalize (valnum_regs_holds _ _ _ _ _ _ _ WF NH VR).
  intros [valu2 [NH2 [EQ AG]]].
  rewrite <- EQ. 
  change (rhs_evals_to valu2 (Load chunk addr vl) m rs#r).
  eapply find_rhs_correct; eauto.
Qed.

End SATISFIABILITY.

(** The numberings associated to each instruction by the static analysis
  are inductively satisfiable, in the following sense: the numbering
  at the function entry point is satisfiable, and for any RTL execution 
  from [pc] to [pc'], satisfiability at [pc] implies 
  satisfiability at [pc']. *)

Theorem analysis_correct_1:
  forall ge sp rs m f approx pc pc' i,
  analyze f = Some approx ->
  f.(fn_code)!pc = Some i -> In pc' (successors_instr i) ->
  numbering_satisfiable ge sp rs m (transfer f pc approx!!pc) ->
  numbering_satisfiable ge sp rs m approx!!pc'.
Proof.
  intros.
  assert (Numbering.ge approx!!pc' (transfer f pc approx!!pc)).
    eapply Solver.fixpoint_solution; eauto.
    unfold successors_list, successors. rewrite PTree.gmap1.
    rewrite H0. auto.
  apply H3. auto.
Qed.

Theorem analysis_correct_entry:
  forall ge sp rs m f approx,
  analyze f = Some approx ->
  numbering_satisfiable ge sp rs m approx!!(f.(fn_entrypoint)).
Proof.
  intros. 
  replace (approx!!(f.(fn_entrypoint))) with Solver.L.top.
  apply empty_numbering_satisfiable.
  symmetry. eapply Solver.fixpoint_entry; eauto.
Qed.

(** * Semantic preservation *)

Section PRESERVATION.

Variable prog: program.
Variable tprog : program.
Hypothesis TRANSF: transf_program prog = OK tprog.
Let ge := Genv.globalenv prog.
Let tge := Genv.globalenv tprog.

Lemma symbols_preserved:
  forall (s: ident), Genv.find_symbol tge s = Genv.find_symbol ge s.
Proof (Genv.find_symbol_transf_partial transf_fundef prog TRANSF).

Lemma varinfo_preserved:
  forall b, Genv.find_var_info tge b = Genv.find_var_info ge b.
Proof (Genv.find_var_info_transf_partial transf_fundef prog TRANSF).

Lemma functions_translated:
  forall (v: val) (f: RTL.fundef),
  Genv.find_funct ge v = Some f ->
  exists tf, Genv.find_funct tge v = Some tf /\ transf_fundef f = OK tf.
Proof (Genv.find_funct_transf_partial transf_fundef prog TRANSF).

Lemma funct_ptr_translated:
  forall (b: block) (f: RTL.fundef),
  Genv.find_funct_ptr ge b = Some f ->
  exists tf, Genv.find_funct_ptr tge b = Some tf /\ transf_fundef f = OK tf.
Proof (Genv.find_funct_ptr_transf_partial transf_fundef prog TRANSF).

Lemma sig_preserved:
  forall f tf, transf_fundef f = OK tf -> funsig tf = funsig f.
Proof.
  unfold transf_fundef; intros. destruct f; monadInv H; auto.
  unfold transf_function in EQ. destruct (type_function f); try discriminate. 
  destruct (analyze f); try discriminate. inv EQ; auto. 
Qed.

Lemma find_function_translated:
  forall ros rs f,
  find_function ge ros rs = Some f ->
  exists tf, find_function tge ros rs = Some tf /\ transf_fundef f = OK tf.
Proof.
  intros until f; destruct ros; simpl.
  intro. apply functions_translated; auto.
  rewrite symbols_preserved. destruct (Genv.find_symbol ge i); intro.
  apply funct_ptr_translated; auto.
  discriminate.
Qed.

Definition transf_function' (f: function) (approxs: PMap.t numbering) : function :=
  mkfunction
    f.(fn_sig)
    f.(fn_params)
    f.(fn_stacksize)
    (transf_code approxs f.(fn_code))
    f.(fn_entrypoint).

(** The proof of semantic preservation is a simulation argument using
  diagrams of the following form:
<<
           st1 --------------- st2
            |                   |
           t|                   |t
            |                   |
            v                   v
           st1'--------------- st2'
>>
  Left: RTL execution in the original program.  Right: RTL execution in
  the optimized program.  Precondition (top) and postcondition (bottom):
  agreement between the states, including the fact that
  the numbering at [pc] (returned by the static analysis) is satisfiable.
*)

Inductive match_stackframes: list stackframe -> list stackframe -> typ -> Prop :=
  | match_stackframes_nil:
      match_stackframes nil nil Tint
  | match_stackframes_cons:
      forall res sp pc rs f approx tyenv s s' ty
           (ANALYZE: analyze f = Some approx)
           (WTF: wt_function f tyenv)
           (WTREGS: wt_regset tyenv rs)
           (TYRES: tyenv res = ty)
           (SAT: forall v m, numbering_satisfiable ge sp (rs#res <- v) m approx!!pc)
           (STACKS: match_stackframes s s' (proj_sig_res (fn_sig f))),
    match_stackframes
      (Stackframe res f sp pc rs :: s)
      (Stackframe res (transf_function' f approx) sp pc rs :: s')
      ty.

Inductive match_states: state -> state -> Prop :=
  | match_states_intro:
      forall s sp pc rs m s' f approx tyenv
             (ANALYZE: analyze f = Some approx)
             (WTF: wt_function f tyenv)
             (WTREGS: wt_regset tyenv rs)
             (SAT: numbering_satisfiable ge sp rs m approx!!pc)
             (STACKS: match_stackframes s s' (proj_sig_res (fn_sig f))),
      match_states (State s f sp pc rs m)
                   (State s' (transf_function' f approx) sp pc rs m)
  | match_states_call:
      forall s f tf args m s',
      match_stackframes s s' (proj_sig_res (funsig f)) ->
      Val.has_type_list args (sig_args (funsig f)) ->
      transf_fundef f = OK tf ->
      match_states (Callstate s f args m)
                   (Callstate s' tf args m)
  | match_states_return:
      forall s s' ty v m,
      match_stackframes s s' ty ->
      Val.has_type v ty ->
      match_states (Returnstate s v m)
                   (Returnstate s' v m).

Ltac TransfInstr :=
  match goal with
  | H1: (PTree.get ?pc ?c = Some ?instr), f: function, approx: PMap.t numbering |- _ =>
      cut ((transf_function' f approx).(fn_code)!pc = Some(transf_instr approx!!pc instr));
      [ simpl transf_instr
      | unfold transf_function', transf_code; simpl; rewrite PTree.gmap; 
        unfold option_map; rewrite H1; reflexivity ]
  end.

(** The proof of simulation is a case analysis over the transition
  in the source code. *)

Lemma transf_step_correct:
  forall s1 t s2, step ge s1 t s2 ->
  forall s1' (MS: match_states s1 s1'),
  exists s2', step tge s1' t s2' /\ match_states s2 s2'.
Proof.
  induction 1; intros; inv MS; try (TransfInstr; intro C).

  (* Inop *)
  exists (State s' (transf_function' f approx) sp pc' rs m); split.
  apply exec_Inop; auto.
  econstructor; eauto. 
  eapply analysis_correct_1; eauto. simpl; auto. 
  unfold transfer; rewrite H; auto.

  (* Iop *)
  exists (State s' (transf_function' f approx) sp pc' (rs#res <- v) m); split.
  assert (eval_operation tge sp op rs##args m = Some v).
    rewrite <- H0. apply eval_operation_preserved. exact symbols_preserved.
  destruct (is_trivial_op op) as []_eqn.
  eapply exec_Iop'; eauto. 
  destruct (find_op approx!!pc op args) as [r|]_eqn. 
  eapply exec_Iop'; eauto. simpl. 
  assert (eval_operation ge sp op rs##args m = Some rs#r).
    eapply find_op_correct; eauto.
    eapply wf_analyze; eauto.
  congruence.
  eapply exec_Iop'; eauto.
  econstructor; eauto.
  apply wt_regset_assign; auto. 
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  simpl in H0. inv H0. rewrite <- H3. apply WTREGS.
  replace (tyenv res) with (snd (type_of_operation op)).
  eapply type_of_operation_sound; eauto.
  rewrite <- H6. reflexivity.
  eapply analysis_correct_1; eauto. simpl; auto.
  unfold transfer; rewrite H. 
  eapply add_op_satisfiable; eauto. eapply wf_analyze; eauto.

  (* Iload *)
  exists (State s' (transf_function' f approx) sp pc' (rs#dst <- v) m); split.
  assert (eval_addressing tge sp addr rs##args = Some a).
    rewrite <- H0. apply eval_addressing_preserved. exact symbols_preserved.
  destruct (find_load approx!!pc chunk addr args) as [r|]_eqn.
  eapply exec_Iop'; eauto. simpl. 
  assert (exists a, eval_addressing ge sp addr rs##args = Some a
                 /\ Mem.loadv chunk m a = Some rs#r).
    eapply find_load_correct; eauto.
    eapply wf_analyze; eauto.
  destruct H3 as [a' [A B]].
  congruence.
  eapply exec_Iload'; eauto.
  econstructor; eauto.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  apply wt_regset_assign. auto. rewrite H8. eapply type_of_chunk_correct; eauto.
  eapply analysis_correct_1; eauto. simpl; auto. 
  unfold transfer; rewrite H. 
  eapply add_load_satisfiable; eauto. eapply wf_analyze; eauto.

  (* Istore *)
  exists (State s' (transf_function' f approx) sp pc' rs m'); split.
  assert (eval_addressing tge sp addr rs##args = Some a).
    rewrite <- H0. apply eval_addressing_preserved. exact symbols_preserved.
  eapply exec_Istore; eauto.
  econstructor; eauto.
  eapply analysis_correct_1; eauto. simpl; auto. 
  unfold transfer; rewrite H.
  eapply add_store_satisfiable; eauto. eapply wf_analyze; eauto.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  rewrite <- H8. auto.

  (* Icall *)
  exploit find_function_translated; eauto. intros [tf [FIND' TRANSF']]. 
  econstructor; split.
  eapply exec_Icall; eauto.
  apply sig_preserved; auto.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  econstructor; eauto. 
  econstructor; eauto. 
  intros. eapply analysis_correct_1; eauto. simpl; auto. 
  unfold transfer; rewrite H. 
  apply empty_numbering_satisfiable.
  rewrite <- H7. apply wt_regset_list; auto. 

  (* Itailcall *)
  exploit find_function_translated; eauto. intros [tf [FIND' TRANSF']]. 
  econstructor; split.
  eapply exec_Itailcall; eauto.
  apply sig_preserved; auto.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  econstructor; eauto. 
  replace (proj_sig_res (funsig fd)) with (proj_sig_res (fn_sig f)). auto. 
  unfold proj_sig_res. rewrite H6; auto.
  rewrite <- H7. apply wt_regset_list; auto.

  (* Ibuiltin *)
  econstructor; split.
  eapply exec_Ibuiltin; eauto. 
  eapply external_call_symbols_preserved; eauto.
  exact symbols_preserved. exact varinfo_preserved.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  econstructor; eauto.
  apply wt_regset_assign; auto. 
  rewrite H6. eapply external_call_well_typed; eauto. 
  eapply analysis_correct_1; eauto. simpl; auto.
  unfold transfer; rewrite H. 
  apply add_unknown_satisfiable. apply wf_kill_equations. eapply wf_analyze; eauto.
  eapply kill_loads_satisfiable; eauto. 

  (* Icond *)
  econstructor; split.
  eapply exec_Icond; eauto. 
  econstructor; eauto.
  destruct b; eapply analysis_correct_1; eauto; simpl; auto;
  unfold transfer; rewrite H; auto.

  (* Ijumptable *)
  econstructor; split.
  eapply exec_Ijumptable; eauto. 
  econstructor; eauto.
  eapply analysis_correct_1; eauto. simpl. eapply list_nth_z_in; eauto.
  unfold transfer; rewrite H; auto.

  (* Ireturn *)
  econstructor; split.
  eapply exec_Ireturn; eauto.
  econstructor; eauto.
  generalize (wt_instrs _ _ WTF pc _ H); intro WTI; inv WTI.
  unfold proj_sig_res. rewrite <- H2. destruct or; simpl; auto. 

  (* internal function *)
  monadInv H7. unfold transf_function in EQ. 
  destruct (type_function f) as [tyenv|]_eqn; try discriminate.
  destruct (analyze f) as [approx|]_eqn; inv EQ. 
  assert (WTF: wt_function f tyenv). apply type_function_correct; auto.
  econstructor; split.
  eapply exec_function_internal; eauto. 
  simpl. econstructor; eauto.
  apply wt_init_regs. inv WTF. rewrite wt_params; auto.
  apply analysis_correct_entry; auto.

  (* external function *)
  monadInv H7. 
  econstructor; split.
  eapply exec_function_external; eauto.
  eapply external_call_symbols_preserved; eauto.
  exact symbols_preserved. exact varinfo_preserved.
  econstructor; eauto.
  simpl. eapply external_call_well_typed; eauto. 

  (* return *)
  inv H3.
  econstructor; split.
  eapply exec_return; eauto.
  econstructor; eauto.
  apply wt_regset_assign; auto. 
Qed.

Lemma transf_initial_states:
  forall st1, initial_state prog st1 ->
  exists st2, initial_state tprog st2 /\ match_states st1 st2.
Proof.
  intros. inversion H. 
  exploit funct_ptr_translated; eauto. intros [tf [A B]].
  exists (Callstate nil tf nil m0); split.
  econstructor; eauto.
  eapply Genv.init_mem_transf_partial; eauto.
  replace (prog_main tprog) with (prog_main prog).
  rewrite symbols_preserved. eauto.
  symmetry. eapply transform_partial_program_main; eauto.
  rewrite <- H3. apply sig_preserved; auto.
  constructor. rewrite H3. constructor. rewrite H3. constructor. auto.
Qed.

Lemma transf_final_states:
  forall st1 st2 r, 
  match_states st1 st2 -> final_state st1 r -> final_state st2 r.
Proof.
  intros. inv H0. inv H. inv H4. constructor. 
Qed.

Theorem transf_program_correct:
  forward_simulation (RTL.semantics prog) (RTL.semantics tprog).
Proof.
  eapply forward_simulation_step.
  eexact symbols_preserved.
  eexact transf_initial_states.
  eexact transf_final_states.
  exact transf_step_correct. 
Qed.

End PRESERVATION.