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
|
(* *********************************************************************)
(* *)
(* The Compcert verified compiler *)
(* *)
(* Xavier Leroy, INRIA Paris-Rocquencourt *)
(* Prashanth Mundkur, SRI International *)
(* *)
(* 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. *)
(* *)
(* The contributions by Prashanth Mundkur are reused and adapted *)
(* under the terms of a Contributor License Agreement between *)
(* SRI International and INRIA. *)
(* *)
(* *********************************************************************)
Require Import Coqlib.
Require Import AST Integers Floats.
Require Import Values Memory Globalenvs.
Require Import Op RTL.
Require Import NeedDomain.
(** Neededness analysis for RISC-V operators *)
Definition op1 (nv: nval) := nv :: nil.
Definition op2 (nv: nval) := nv :: nv :: nil.
Definition op3 (nv: nval) := nv :: nv :: nv :: nil.
Definition needs_of_condition (cond: condition): list nval := nil.
Definition needs_of_operation (op: operation) (nv: nval): list nval :=
match op with
| Omove => op1 nv
| Ointconst n => nil
| Olongconst n => nil
| Ofloatconst n => nil
| Osingleconst n => nil
| Oaddrsymbol id ofs => nil
| Oaddrstack ofs => nil
| Ocast8signed => op1 (sign_ext 8 nv)
| Ocast16signed => op1 (sign_ext 16 nv)
| Oadd => op2 (modarith nv)
| Oaddimm n => op1 (modarith nv)
| Oneg => op1 (modarith nv)
| Osub => op2 (default nv)
| Omul => op2 (modarith nv)
| Omulimm _ => op1 (modarith nv)
| Omulhs | Omulhu | Odiv | Odivu | Omod | Omodu => op2 (default nv)
| Oand => op2 (bitwise nv)
| Oandimm n => op1 (andimm nv n)
| Onand => op2 (bitwise nv)
| Onandimm n => op1 (andimm nv n)
| Oor => op2 (bitwise nv)
| Oorimm n => op1 (orimm nv n)
| Onor => op2 (bitwise nv)
| Onorimm n => op1 (orimm nv n)
| Oxor => op2 (bitwise nv)
| Oxorimm n => op1 (bitwise nv)
| Onxor => op2 (bitwise nv)
| Onxorimm n => op1 (bitwise nv)
| Onot => op1 (bitwise nv)
| Oandn => op2 (bitwise nv)
| Oandnimm n => op1 (andimm nv n)
| Oorn => op2 (bitwise nv)
| Oornimm n => op1 (orimm nv n)
| Oshl | Oshr | Oshru => op2 (default nv)
| Oshlimm n => op1 (shlimm nv n)
| Oshrimm n => op1 (shrimm nv n)
| Ororimm n => op1 (ror nv n)
| Oshruimm n => op1 (shruimm nv n)
| Oshrximm n => op1 (default nv)
| Omadd => op3 (modarith nv)
| Omaddimm n => op2 (modarith nv)
| Omakelong => op2 (default nv)
| Olowlong | Ohighlong => op1 (default nv)
| Ocast32signed => op1 (default nv)
| Ocast32unsigned => op1 (default nv)
| Oaddl => op2 (default nv)
| Oaddlimm n => op1 (default nv)
| Onegl => op1 (default nv)
| Osubl => op2 (default nv)
| Omull => op2 (default nv)
| Omullimm _ => op1 (default nv)
| Omullhs | Omullhu | Odivl | Odivlu | Omodl | Omodlu => op2 (default nv)
| Oandl => op2 (default nv)
| Oandlimm n => op1 (default nv)
| Onandl => op2 (default nv)
| Onandlimm n => op1 (default nv)
| Oorl => op2 (default nv)
| Oorlimm n => op1 (default nv)
| Onorl => op2 (default nv)
| Onorlimm n => op1 (default nv)
| Oxorl => op2 (default nv)
| Oxorlimm n => op1 (default nv)
| Onxorl => op2 (default nv)
| Onxorlimm n => op1 (default nv)
| Onotl => op1 (default nv)
| Oandnl => op2 (default nv)
| Oandnlimm n => op1 (default nv)
| Oornl => op2 (default nv)
| Oornlimm n => op1 (default nv)
| Oshll | Oshrl | Oshrlu => op2 (default nv)
| Oshllimm n => op1 (default nv)
| Oshrlimm n => op1 (default nv)
| Oshrluimm n => op1 (default nv)
| Oshrxlimm n => op1 (default nv)
| Omaddl => op3 (default nv)
| Omaddlimm n => op2 (default nv)
| Onegf | Oabsf => op1 (default nv)
| Oaddf | Osubf | Omulf | Odivf => op2 (default nv)
| Onegfs | Oabsfs => op1 (default nv)
| Oaddfs | Osubfs | Omulfs | Odivfs => op2 (default nv)
| Ofloatofsingle | Osingleoffloat => op1 (default nv)
| Ointoffloat | Ointuoffloat | Ofloatofint | Ofloatofintu => op1 (default nv)
| Olongoffloat | Olonguoffloat | Ofloatoflong | Ofloatoflongu => op1 (default nv)
| Ointofsingle | Ointuofsingle | Osingleofint | Osingleofintu => op1 (default nv)
| Olongofsingle | Olonguofsingle | Osingleoflong | Osingleoflongu => op1 (default nv)
| Ocmp c => needs_of_condition c
| Oselect | Oselectl | Oselectf | Oselectfs => op3 (default nv)
end.
Definition operation_is_redundant (op: operation) (nv: nval): bool :=
match op with
| Ocast8signed => sign_ext_redundant 8 nv
| Ocast16signed => sign_ext_redundant 16 nv
| Oandimm n => andimm_redundant nv n
| Oorimm n => orimm_redundant nv n
| _ => false
end.
Ltac InvAgree :=
match goal with
| [H: vagree_list nil _ _ |- _ ] => inv H; InvAgree
| [H: vagree_list (_::_) _ _ |- _ ] => inv H; InvAgree
| _ => idtac
end.
Ltac TrivialExists :=
match goal with
| [ |- exists v, Some ?x = Some v /\ _ ] => exists x; split; auto
| _ => idtac
end.
Section SOUNDNESS.
Variable ge: genv.
Variable sp: block.
Variables m m': mem.
Hypothesis PERM: forall b ofs k p, Mem.perm m b ofs k p -> Mem.perm m' b ofs k p.
Lemma needs_of_condition_sound:
forall cond args b args',
eval_condition cond args m = Some b ->
vagree_list args args' (needs_of_condition cond) ->
eval_condition cond args' m' = Some b.
Proof.
intros. unfold needs_of_condition in H0.
eapply default_needs_of_condition_sound; eauto.
Qed.
Lemma addl_sound:
forall v1 w1 v2 w2 x,
vagree v1 w1 (default x) -> vagree v2 w2 (default x) ->
vagree (Val.addl v1 v2) (Val.addl w1 w2) x.
Proof.
unfold default; intros.
destruct x; simpl in *; trivial.
- unfold Val.addl.
destruct v1; destruct v2; trivial; destruct Archi.ptr64; trivial.
- apply Val.addl_lessdef; trivial.
Qed.
Lemma mull_sound:
forall v1 w1 v2 w2 x,
vagree v1 w1 (default x) -> vagree v2 w2 (default x) ->
vagree (Val.mull v1 v2) (Val.mull w1 w2) x.
Proof.
unfold default; intros.
destruct x; simpl in *; trivial.
- unfold Val.mull.
destruct v1; destruct v2; trivial.
- unfold Val.mull.
destruct v1; destruct v2; trivial.
inv H. inv H0.
trivial.
Qed.
Lemma select_sound:
forall v0 w0 v1 w1 v2 w2 x,
vagree v0 w0 (default x) ->
vagree v1 w1 (default x) ->
vagree v2 w2 (default x) ->
vagree (select v0 v1 v2) (select w0 w1 w2) x.
Proof.
unfold default; intros.
destruct x; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
inv H. inv H0. inv H1. simpl.
constructor.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
inv H. inv H0. inv H1. simpl.
constructor.
Qed.
Lemma selectl_sound:
forall v0 w0 v1 w1 v2 w2 x,
vagree v0 w0 (default x) ->
vagree v1 w1 (default x) ->
vagree v2 w2 (default x) ->
vagree (selectl v0 v1 v2) (selectl w0 w1 w2) x.
Proof.
unfold default; intros.
destruct x; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
inv H. inv H0. inv H1. simpl.
constructor.
Qed.
Lemma selectf_sound:
forall v0 w0 v1 w1 v2 w2 x,
vagree v0 w0 (default x) ->
vagree v1 w1 (default x) ->
vagree v2 w2 (default x) ->
vagree (selectf v0 v1 v2) (selectf w0 w1 w2) x.
Proof.
unfold default; intros.
destruct x; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
inv H. inv H0. inv H1. simpl.
constructor.
Qed.
Lemma selectfs_sound:
forall v0 w0 v1 w1 v2 w2 x,
vagree v0 w0 (default x) ->
vagree v1 w1 (default x) ->
vagree v2 w2 (default x) ->
vagree (selectfs v0 v1 v2) (selectfs w0 w1 w2) x.
Proof.
unfold default; intros.
destruct x; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
- destruct v2; simpl; trivial.
destruct v0; simpl; trivial.
destruct v1; simpl; trivial.
inv H. inv H0. inv H1. simpl.
constructor.
Qed.
Remark default_idem: forall nv, default (default nv) = default nv.
Proof.
destruct nv; simpl; trivial.
Qed.
Lemma needs_of_operation_sound:
forall op args v nv args',
eval_operation ge (Vptr sp Ptrofs.zero) op args m = Some v ->
vagree_list args args' (needs_of_operation op nv) ->
nv <> Nothing ->
exists v',
eval_operation ge (Vptr sp Ptrofs.zero) op args' m' = Some v'
/\ vagree v v' nv.
Proof.
unfold needs_of_operation; intros; destruct op; try (eapply default_needs_of_operation_sound; eauto; fail);
simpl in *; FuncInv; InvAgree; TrivialExists.
- apply sign_ext_sound; auto. compute; auto.
- apply sign_ext_sound; auto. compute; auto.
- apply add_sound; auto.
- apply add_sound; auto with na.
- apply neg_sound; auto.
- apply mul_sound; auto.
- apply mul_sound; auto with na.
- apply and_sound; auto.
- apply andimm_sound; auto.
- apply notint_sound; apply and_sound; auto.
- apply notint_sound; apply andimm_sound; auto.
- apply or_sound; auto.
- apply orimm_sound; auto.
- apply notint_sound; apply or_sound; auto.
- apply notint_sound; apply orimm_sound; auto.
- apply xor_sound; auto.
- apply xor_sound; auto with na.
- apply notint_sound; apply xor_sound; auto.
- apply notint_sound; apply xor_sound; auto with na.
- apply notint_sound; auto.
- apply and_sound; try apply notint_sound; auto with na.
- apply andimm_sound; try apply notint_sound; auto with na.
- apply or_sound; try apply notint_sound; auto with na.
- apply orimm_sound; try apply notint_sound; auto with na.
- apply shlimm_sound; auto.
- apply shrimm_sound; auto.
- apply shruimm_sound; auto.
- apply ror_sound; auto.
(* madd *)
- apply add_sound; try apply mul_sound; auto with na; rewrite modarith_idem; assumption.
- apply add_sound; try apply mul_sound; auto with na; rewrite modarith_idem; assumption.
(* maddl *)
- apply addl_sound; trivial.
apply mull_sound; trivial.
rewrite default_idem; trivial.
rewrite default_idem; trivial.
(* select *)
- apply select_sound; trivial.
(* selectl *)
- apply selectl_sound; trivial.
(* selectf *)
- apply selectf_sound; trivial.
(* selectfs *)
- apply selectfs_sound; trivial.
Qed.
Lemma operation_is_redundant_sound:
forall op nv arg1 args v arg1' args',
operation_is_redundant op nv = true ->
eval_operation ge (Vptr sp Ptrofs.zero) op (arg1 :: args) m = Some v ->
vagree_list (arg1 :: args) (arg1' :: args') (needs_of_operation op nv) ->
vagree v arg1' nv.
Proof.
intros. destruct op; simpl in *; try discriminate; inv H1; FuncInv; subst.
- apply sign_ext_redundant_sound; auto. omega.
- apply sign_ext_redundant_sound; auto. omega.
- apply andimm_redundant_sound; auto.
- apply orimm_redundant_sound; auto.
Qed.
End SOUNDNESS.
|
