Merge of the nonstrict-ops branch:

- Most RTL operators now evaluate to Some Vundef instead of None
  when undefined behavior occurs.
- More aggressive instruction selection.
- "Bertotization" of pattern-matchings now implemented by a proper preprocessor.
- Cast optimization moved to cfrontend/Cminorgen; removed backend/CastOptim.


git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@1790 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e

1 files changed, 277 insertions, 0 deletions

diff --git a/powerpc/ConstpropOp.vp b/powerpc/ConstpropOp.vp
new file mode 100644
index 00000000..22e89e31
--- /dev/null
+++ b/powerpc/ConstpropOp.vp
@@ -0,0 +1,277 @@
+(* *********************************************************************)
+(*                                                                     *)
+(*              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.     *)
+(*                                                                     *)
+(* *********************************************************************)
+
+(** Static analysis and strength reduction for operators 
+  and conditions.  This is the machine-dependent part of [Constprop]. *)
+
+Require Import Coqlib.
+Require Import AST.
+Require Import Integers.
+Require Import Floats.
+Require Import Values.
+Require Import Op.
+Require Import Registers.
+
+(** * Static analysis *)
+
+(** To each pseudo-register at each program point, the static analysis 
+  associates a compile-time approximation taken from the following set. *)
+
+Inductive approx : Type :=
+  | Novalue: approx      (** No value possible, code is unreachable. *)
+  | Unknown: approx      (** All values are possible,
+                             no compile-time information is available. *)
+  | I: int -> approx     (** A known integer value. *)
+  | F: float -> approx   (** A known floating-point value. *)
+  | G: ident -> int -> approx
+                         (** The value is the address of the given global
+                             symbol plus the given integer offset. *)
+  | S: int -> approx.    (** The value is the stack pointer plus the offset. *)
+
+(** We now define the abstract interpretations of conditions and operators
+  over this set of approximations.  For instance, the abstract interpretation
+  of the operator [Oaddf] applied to two expressions [a] and [b] is
+  [F(Float.add f g)] if [a] and [b] have static approximations [Vfloat f]
+  and [Vfloat g] respectively, and [Unknown] otherwise.
+
+  The static approximations are defined by large pattern-matchings over
+  the approximations of the results.  We write these matchings in the
+  indirect style described in file [SelectOp] to avoid excessive
+  duplication of cases in proofs. *)
+
+Nondetfunction eval_static_condition (cond: condition) (vl: list approx) :=
+  match cond, vl with
+  | Ccomp c, I n1 :: I n2 :: nil => Some(Int.cmp c n1 n2)
+  | Ccompu c, I n1 :: I n2 :: nil => Some(Int.cmpu c n1 n2)
+  | Ccompimm c n, I n1 :: nil => Some(Int.cmp c n1 n)
+  | Ccompuimm c n, I n1 :: nil => Some(Int.cmpu c n1 n)
+  | Ccompf c, F n1 :: F n2 :: nil => Some(Float.cmp c n1 n2)
+  | Cnotcompf c, F n1 :: F n2 :: nil => Some(negb(Float.cmp c n1 n2))
+  | Cmaskzero n, I n1 :: nil => Some(Int.eq (Int.and n1 n) Int.zero)
+  | Cmasknotzero n, I n1::nil => Some(negb(Int.eq (Int.and n1 n) Int.zero))
+  | _, _ => None
+  end.
+
+Definition eval_static_condition_val (cond: condition) (vl: list approx) :=
+  match eval_static_condition cond vl with
+  | None => Unknown
+  | Some b => I(if b then Int.one else Int.zero)
+  end.
+
+Definition eval_static_intoffloat (f: float) :=
+  match Float.intoffloat f with Some x => I x | None => Unknown end.
+
+Nondetfunction eval_static_operation (op: operation) (vl: list approx) :=
+  match op, vl with
+  | Omove, v1::nil => v1
+  | Ointconst n, nil => I n
+  | Ofloatconst n, nil => F n
+  | Oaddrsymbol s n, nil => G s n
+  | Oaddrstack n, nil => S n
+  | Ocast8signed, I n1 :: nil => I(Int.sign_ext 8 n1)
+  | Ocast16signed, I n1 :: nil => I(Int.sign_ext 16 n1)
+  | Oadd, I n1 :: I n2 :: nil => I(Int.add n1 n2)
+  | Oadd, G s1 n1 :: I n2 :: nil => G s1 (Int.add n1 n2)
+  | Oadd, I n1 :: G s2 n2 :: nil => G s2 (Int.add n1 n2)
+  | Oadd, S n1 :: I n2 :: nil => S (Int.add n1 n2)
+  | Oadd, I n1 :: S n2 :: nil => S (Int.add n1 n2)
+  | Oaddimm n, I n1 :: nil => I (Int.add n1 n)
+  | Oaddimm n, G s1 n1 :: nil => G s1 (Int.add n1 n)
+  | Oaddimm n, S n1 :: nil => S (Int.add n1 n)
+  | Osub, I n1 :: I n2 :: nil => I(Int.sub n1 n2)
+  | Osub, G s1 n1 :: I n2 :: nil => G s1 (Int.sub n1 n2)
+  | Osub, S n1 :: I n2 :: nil => S (Int.sub n1 n2)
+  | Osubimm n, I n1 :: nil => I (Int.sub n n1)
+  | Omul, I n1 :: I n2 :: nil => I(Int.mul n1 n2)
+  | Omulimm n, I n1 :: nil => I(Int.mul n1 n)
+  | Odiv, I n1 :: I n2 :: nil => if Int.eq n2 Int.zero then Unknown else I(Int.divs n1 n2)
+  | Odivu, I n1 :: I n2 :: nil => if Int.eq n2 Int.zero then Unknown else I(Int.divu n1 n2)
+  | Oand, I n1 :: I n2 :: nil => I(Int.and n1 n2)
+  | Oandimm n, I n1 :: nil => I(Int.and n1 n)
+  | Oor, I n1 :: I n2 :: nil => I(Int.or n1 n2)
+  | Oorimm n, I n1 :: nil => I(Int.or n1 n)
+  | Oxor, I n1 :: I n2 :: nil => I(Int.xor n1 n2)
+  | Oxorimm n, I n1 :: nil => I(Int.xor n1 n)
+  | Onand, I n1 :: I n2 :: nil => I(Int.xor (Int.and n1 n2) Int.mone)
+  | Onor, I n1 :: I n2 :: nil => I(Int.xor (Int.or n1 n2) Int.mone)
+  | Onxor, I n1 :: I n2 :: nil => I(Int.xor (Int.xor n1 n2) Int.mone)
+  | Oshl, I n1 :: I n2 :: nil => if Int.ltu n2 Int.iwordsize then I(Int.shl n1 n2) else Unknown
+  | Oshr, I n1 :: I n2 :: nil => if Int.ltu n2 Int.iwordsize then I(Int.shr n1 n2) else Unknown
+  | Oshrimm n, I n1 :: nil => if Int.ltu n Int.iwordsize then I(Int.shr n1 n) else Unknown
+  | Oshrximm n, I n1 :: nil => if Int.ltu n (Int.repr 31) then I(Int.shrx n1 n) else Unknown
+  | Oshru, I n1 :: I n2 :: nil => if Int.ltu n2 Int.iwordsize then I(Int.shru n1 n2) else Unknown
+  | Orolm amount mask, I n1 :: nil => I(Int.rolm n1 amount mask)
+  | Oroli amount mask, I n1 :: I n2 :: nil => I(Int.or (Int.and n1 (Int.not mask)) (Int.rolm n2 amount mask))
+  | Onegf, F n1 :: nil => F(Float.neg n1)
+  | Oabsf, F n1 :: nil => F(Float.abs n1)
+  | Oaddf, F n1 :: F n2 :: nil => F(Float.add n1 n2)
+  | Osubf, F n1 :: F n2 :: nil => F(Float.sub n1 n2)
+  | Omulf, F n1 :: F n2 :: nil => F(Float.mul n1 n2)
+  | Odivf, F n1 :: F n2 :: nil => F(Float.div n1 n2)
+  | Omuladdf, F n1 :: F n2 :: F n3 :: nil => F(Float.add (Float.mul n1 n2) n3)
+  | Omulsubf, F n1 :: F n2 :: F n3 :: nil => F(Float.sub (Float.mul n1 n2) n3)
+  | Osingleoffloat, F n1 :: nil => F(Float.singleoffloat n1)
+  | Ointoffloat, F n1 :: nil => eval_static_intoffloat n1
+  | Ofloatofwords, I n1 :: I n2 :: nil => F(Float.from_words n1 n2)
+  | Ocmp c, vl => eval_static_condition_val c vl
+  | _, _ => Unknown
+  end.
+
+(** * Operator strength reduction *)
+
+(** We now define auxiliary functions for strength reduction of
+  operators and addressing modes: replacing an operator with a cheaper
+  one if some of its arguments are statically known.  These are again
+  large pattern-matchings expressed in indirect style. *)
+
+Section STRENGTH_REDUCTION.
+
+Nondetfunction cond_strength_reduction 
+              (cond: condition) (args: list reg) (vl: list approx) :=
+  match cond, args, vl with
+  | Ccomp c, r1 :: r2 :: nil, I n1 :: v2 :: nil =>
+      (Ccompimm (swap_comparison c) n1, r2 :: nil)
+  | Ccomp c, r1 :: r2 :: nil, v1 :: I n2 :: nil =>
+      (Ccompimm c n2, r1 :: nil)
+  | Ccompu c, r1 :: r2 :: nil, I n1 :: v2 :: nil =>
+      (Ccompuimm (swap_comparison c) n1, r2 :: nil)
+  | Ccompu c, r1 :: r2 :: nil, v1 :: I n2 :: nil =>
+      (Ccompuimm c n2, r1 :: nil)
+  | _, _, _ => 
+      (cond, args)
+  end.
+
+Definition make_addimm (n: int) (r: reg) :=
+  if Int.eq n Int.zero
+  then (Omove, r :: nil)
+  else (Oaddimm n, r :: nil).
+
+Definition make_shlimm (n: int) (r1 r2: reg) :=
+  if Int.eq n Int.zero then
+    (Omove, r1 :: nil)
+  else if Int.ltu n Int.iwordsize then
+    (Orolm n (Int.shl Int.mone n), r1 :: nil)
+  else
+    (Oshl, r1 :: r2 :: nil).
+
+Definition make_shrimm (n: int) (r1 r2: reg) :=
+  if Int.eq n Int.zero then
+    (Omove, r1 :: nil)
+  else if Int.ltu n Int.iwordsize then
+    (Oshrimm n, r1 :: nil)
+  else
+    (Oshr, r1 :: r2 :: nil).
+
+Definition make_shruimm (n: int) (r1 r2: reg) :=
+  if Int.eq n Int.zero then
+    (Omove, r1 :: nil)
+  else if Int.ltu n Int.iwordsize then
+    (Orolm (Int.sub Int.iwordsize n) (Int.shru Int.mone n), r1 :: nil)
+  else
+    (Oshru, r1 :: r2 :: nil).
+
+Definition make_mulimm (n: int) (r1 r2: reg) :=
+  if Int.eq n Int.zero then
+    (Ointconst Int.zero, nil)
+  else if Int.eq n Int.one then
+    (Omove, r1 :: nil)
+  else
+    match Int.is_power2 n with
+    | Some l => (Orolm l (Int.shl Int.mone l), r1 :: nil)
+    | None => (Omulimm n, r1 :: nil)
+    end.
+
+Definition make_divimm (n: int) (r1 r2: reg) :=
+  match Int.is_power2 n with
+  | Some l => if Int.ltu l (Int.repr 31)
+              then (Oshrximm l, r1 :: nil)
+              else (Odiv, r1 :: r2 :: nil)
+  | None   => (Odiv, r1 :: r2 :: nil)
+  end.
+
+Definition make_divuimm (n: int) (r1 r2: reg) :=
+  match Int.is_power2 n with
+  | Some l => (Orolm (Int.sub Int.iwordsize l) (Int.shru Int.mone l), r1 :: nil)
+  | None   => (Odivu, r1 :: r2 :: nil)
+  end.
+
+Definition make_andimm (n: int) (r: reg) :=
+  if Int.eq n Int.zero
+  then (Ointconst Int.zero, nil)
+  else if Int.eq n Int.mone then (Omove, r :: nil)
+  else (Oandimm n, r :: nil).
+
+Definition make_orimm (n: int) (r: reg) :=
+  if Int.eq n Int.zero then (Omove, r :: nil)
+  else if Int.eq n Int.mone then (Ointconst Int.mone, nil)
+  else (Oorimm n, r :: nil).
+
+Definition make_xorimm (n: int) (r: reg) :=
+  if Int.eq n Int.zero
+  then (Omove, r :: nil)
+  else (Oxorimm n, r :: nil).
+
+Nondetfunction op_strength_reduction 
+              (op: operation) (args: list reg) (vl: list approx) :=
+  match op, args, vl with
+  | Oadd, r1 :: r2 :: nil, I n1 :: v2 :: nil => make_addimm n1 r2
+  | Oadd, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_addimm n2 r1
+  | Osub, r1 :: r2 :: nil, I n1 :: v2 :: nil => (Osubimm n1, r2 :: nil)
+  | Osub, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_addimm (Int.neg n2) r1
+  | Omul, r1 :: r2 :: nil, I n1 :: v2 :: nil => make_mulimm n1 r2 r1
+  | Omul, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_mulimm n2 r1 r2
+  | Odiv, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_divimm n2 r1 r2
+  | Odivu, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_divuimm n2 r1 r2
+  | Oand, r1 :: r2 :: nil, I n1 :: v2 :: nil => make_andimm n1 r2
+  | Oand, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_andimm n2 r1
+  | Oor, r1 :: r2 :: nil, I n1 :: v2 :: nil => make_orimm n1 r2
+  | Oor, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_orimm n2 r1
+  | Oxor, r1 :: r2 :: nil, I n1 :: v2 :: nil => make_xorimm n1 r2
+  | Oxor, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_xorimm n2 r1
+  | Oshl, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_shlimm n2 r1 r2
+  | Oshr, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_shrimm n2 r1 r2
+  | Oshru, r1 :: r2 :: nil, v1 :: I n2 :: nil => make_shruimm n2 r1 r2
+  | Ocmp c, args, vl =>
+      let (c', args') := cond_strength_reduction c args vl in (Ocmp c', args')
+  | _, _, _ => (op, args)
+  end.
+
+Nondetfunction addr_strength_reduction
+                (addr: addressing) (args: list reg) (vl: list approx) :=
+  match addr, args, vl with
+  | Aindexed2, r1 :: r2 :: nil, G symb n1 :: I n2 :: nil =>
+      (Aglobal symb (Int.add n1 n2), nil)
+  | Aindexed2, r1 :: r2 :: nil, I n1 :: G symb n2 :: nil =>
+      (Aglobal symb (Int.add n1 n2), nil)
+  | Aindexed2, r1 :: r2 :: nil, S n1 :: I n2 :: nil =>
+      (Ainstack (Int.add n1 n2), nil)
+  | Aindexed2, r1 :: r2 :: nil, I n1 :: S n2 :: nil =>
+      (Ainstack (Int.add n1 n2), nil)
+  | Aindexed2, r1 :: r2 :: nil, G symb n1 :: v2 :: nil =>
+      (Abased symb n1, r2 :: nil)
+  | Aindexed2, r1 :: r2 :: nil, v1 :: G symb n2 :: nil =>
+      (Abased symb n2, r1 :: nil)
+  | Aindexed2, r1 :: r2 :: nil, I n1 :: v2 :: nil =>
+      (Aindexed n1, r2 :: nil)
+  | Aindexed2, r1 :: r2 :: nil, v1 :: I n2 :: nil =>
+      (Aindexed n2, r1 :: nil)
+  | Abased symb ofs, r1 :: nil, I n1 :: nil =>
+      (Aglobal symb (Int.add ofs n1), nil)
+  | Aindexed n, r1 :: nil, G symb n1 :: nil =>
+      (Aglobal symb (Int.add n1 n), nil)
+  | Aindexed n, r1 :: nil, S n1 :: nil =>
+      (Ainstack (Int.add n1 n), nil)
+  | _, _, _ =>
+      (addr, args)
+  end.
+
+End STRENGTH_REDUCTION.