select rotate ops 32-bit

3 files changed, 74 insertions, 2 deletions

diff --git a/mppa_k1c/SelectOp.v b/mppa_k1c/SelectOp.v
index c42f0340..fb7f476f 100644
--- a/mppa_k1c/SelectOp.v
+++ b/mppa_k1c/SelectOp.v
@@ -591,12 +591,26 @@ Definition orimm (n1: int) (e2: expr) :=
   end.
 
 
+Definition same_expr_pure (e1 e2: expr) :=
+  match e1, e2 with
+  | Evar v1, Evar v2 => if ident_eq v1 v2 then true else false
+  | _, _ => false
+  end.
+
 (** Original definition:
 <<
 Nondetfunction or (e1: expr) (e2: expr) :=
   match e1, e2 with
   | Eop (Ointconst n1) Enil, t2 => orimm n1 t2
   | t1, Eop (Ointconst n2) Enil => orimm n2 t1
+  | Eop (Oshlimm n1) (t1:::Enil), Eop (Oshruimm n2) (t2:::Enil) =>
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2
+      then Eop (Ororimm n2) (t1:::Enil)
+      else Eop Oor (e1:::e2:::Enil)
+  | Eop (Oshruimm n2) (t2:::Enil), Eop (Oshlimm n1) (t1:::Enil) =>
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2
+      then Eop (Ororimm n2) (t1:::Enil)
+      else Eop Oor (e1:::e2:::Enil)
   | _, _ => Eop Oor (e1:::e2:::Enil)
   end.
 >>
@@ -605,12 +619,16 @@ Nondetfunction or (e1: expr) (e2: expr) :=
 Inductive or_cases: forall (e1: expr) (e2: expr), Type :=
   | or_case1: forall n1 t2, or_cases (Eop (Ointconst n1) Enil) (t2)
   | or_case2: forall t1 n2, or_cases (t1) (Eop (Ointconst n2) Enil)
+  | or_case3: forall n1 t1 n2 t2, or_cases (Eop (Oshlimm n1) (t1:::Enil)) (Eop (Oshruimm n2) (t2:::Enil))
+  | or_case4: forall n2 t2 n1 t1, or_cases (Eop (Oshruimm n2) (t2:::Enil)) (Eop (Oshlimm n1) (t1:::Enil))
   | or_default: forall (e1: expr) (e2: expr), or_cases e1 e2.
 
 Definition or_match (e1: expr) (e2: expr) :=
   match e1 as zz1, e2 as zz2 return or_cases zz1 zz2 with
   | Eop (Ointconst n1) Enil, t2 => or_case1 n1 t2
   | t1, Eop (Ointconst n2) Enil => or_case2 t1 n2
+  | Eop (Oshlimm n1) (t1:::Enil), Eop (Oshruimm n2) (t2:::Enil) => or_case3 n1 t1 n2 t2
+  | Eop (Oshruimm n2) (t2:::Enil), Eop (Oshlimm n1) (t1:::Enil) => or_case4 n2 t2 n1 t1
   | e1, e2 => or_default e1 e2
   end.
 
@@ -620,6 +638,10 @@ Definition or (e1: expr) (e2: expr) :=
       orimm n1 t2
   | or_case2 t1 n2 => (* t1, Eop (Ointconst n2) Enil *) 
       orimm n2 t1
+  | or_case3 n1 t1 n2 t2 => (* Eop (Oshlimm n1) (t1:::Enil), Eop (Oshruimm n2) (t2:::Enil) *) 
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2 then Eop (Ororimm n2) (t1:::Enil) else Eop Oor (e1:::e2:::Enil)
+  | or_case4 n2 t2 n1 t1 => (* Eop (Oshruimm n2) (t2:::Enil), Eop (Oshlimm n1) (t1:::Enil) *) 
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2 then Eop (Ororimm n2) (t1:::Enil) else Eop Oor (e1:::e2:::Enil)
   | or_default e1 e2 =>
       Eop Oor (e1:::e2:::Enil)
   end.
diff --git a/mppa_k1c/SelectOp.vp b/mppa_k1c/SelectOp.vp
index bb8af2ed..14753871 100644
--- a/mppa_k1c/SelectOp.vp
+++ b/mppa_k1c/SelectOp.vp
@@ -235,10 +235,24 @@ Nondetfunction orimm (n1: int) (e2: expr) :=
        | _ => Eop (Oorimm n1) (e2:::Enil)
   end.
 
+Definition same_expr_pure (e1 e2: expr) :=
+  match e1, e2 with
+  | Evar v1, Evar v2 => if ident_eq v1 v2 then true else false
+  | _, _ => false
+  end.
+
 Nondetfunction or (e1: expr) (e2: expr) :=
   match e1, e2 with
   | Eop (Ointconst n1) Enil, t2 => orimm n1 t2
   | t1, Eop (Ointconst n2) Enil => orimm n2 t1
+  | Eop (Oshlimm n1) (t1:::Enil), Eop (Oshruimm n2) (t2:::Enil) =>
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2
+      then Eop (Ororimm n2) (t1:::Enil)
+      else Eop Oor (e1:::e2:::Enil)
+  | Eop (Oshruimm n2) (t2:::Enil), Eop (Oshlimm n1) (t1:::Enil) =>
+      if Int.eq (Int.add n1 n2) Int.iwordsize && same_expr_pure t1 t2
+      then Eop (Ororimm n2) (t1:::Enil)
+      else Eop Oor (e1:::e2:::Enil)
   | _, _ => Eop Oor (e1:::e2:::Enil)
   end.
 
diff --git a/mppa_k1c/SelectOpproof.v b/mppa_k1c/SelectOpproof.v
index e7577fb5..c5f05dcf 100644
--- a/mppa_k1c/SelectOpproof.v
+++ b/mppa_k1c/SelectOpproof.v
@@ -452,12 +452,48 @@ Proof.
   - TrivialExists.
 Qed.
 
+
+Remark eval_same_expr:
+  forall a1 a2 le v1 v2,
+  same_expr_pure a1 a2 = true ->
+  eval_expr ge sp e m le a1 v1 ->
+  eval_expr ge sp e m le a2 v2 ->
+  a1 = a2 /\ v1 = v2.
+Proof.
+  intros until v2.
+  destruct a1; simpl; try (intros; discriminate).
+  destruct a2; simpl; try (intros; discriminate).
+  case (ident_eq i i0); intros.
+  subst i0. inversion H0. inversion H1. split. auto. congruence.
+  discriminate.
+Qed.
+
 Theorem eval_or: binary_constructor_sound or Val.or.
 Proof.
-  red; intros until y; unfold or; case (or_match a b); intros; InvEval.
+  unfold or; red; intros.
+  assert (DEFAULT: exists v, eval_expr ge sp e m le (Eop Oor (a:::b:::Enil)) v /\ Val.lessdef (Val.or x y) v) by TrivialExists.
+  assert (ROR: forall v n1 n2,
+    Int.add n1 n2 = Int.iwordsize ->
+    Val.lessdef (Val.or (Val.shl v (Vint n1)) (Val.shru v (Vint n2)))
+                (Val.ror v (Vint n2))).
+  { intros. destruct v; simpl; auto.
+    destruct (Int.ltu n1 Int.iwordsize) eqn:N1; auto.
+    destruct (Int.ltu n2 Int.iwordsize) eqn:N2; auto.
+    simpl. rewrite <- Int.or_ror; auto. }
+  
+  destruct (or_match a b); InvEval.
+  
   - rewrite Val.or_commut. apply eval_orimm; auto.
   - apply eval_orimm; auto.
-  - TrivialExists.
+  - predSpec Int.eq Int.eq_spec (Int.add n1 n2) Int.iwordsize; auto.
+    destruct (same_expr_pure t1 t2) eqn:?; auto.
+    InvEval. exploit eval_same_expr; eauto. intros [EQ1 EQ2]; subst.
+    exists (Val.ror v0 (Vint n2)); split. EvalOp. apply ROR; auto.
+  - predSpec Int.eq Int.eq_spec (Int.add n1 n2) Int.iwordsize; auto.
+    destruct (same_expr_pure t1 t2) eqn:?; auto.
+    InvEval. exploit eval_same_expr; eauto. intros [EQ1 EQ2]; subst.
+    exists (Val.ror v1 (Vint n2)); split. EvalOp. rewrite Val.or_commut. apply ROR; auto.
+  - apply DEFAULT.
 Qed.
 
 Theorem eval_xorimm: