From 783288d052bbcf75e250dff5018443d109c6101c Mon Sep 17 00:00:00 2001 From: xleroy Date: Wed, 23 Jul 2014 13:14:02 +0000 Subject: Merge the various $(ARCH)/$(VARIANT)/xxx.v files into $(ARCH)/xxx.v. The only platform where we have two variants is ARM, and it's easier to share the callling convention code between the two than to maintain both variants separately. git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@2540 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e --- .depend | 14 +- Makefile | 6 +- arm/Archi.v | 3 + arm/Conventions1.v | 770 +++++++++++++++++++++++++++++++++++++++++++ arm/Stacklayout.v | 132 ++++++++ arm/eabi/Conventions1.v | 509 ---------------------------- arm/eabi/Stacklayout.v | 132 -------- arm/extractionMachdep.v | 8 + arm/hardfloat/Conventions1.v | 733 ---------------------------------------- arm/hardfloat/Stacklayout.v | 132 -------- backend/Stackingproof.v | 2 +- ia32/Conventions1.v | 371 +++++++++++++++++++++ ia32/Stacklayout.v | 130 ++++++++ ia32/standard/Conventions1.v | 366 -------------------- ia32/standard/Stacklayout.v | 130 -------- powerpc/Conventions1.v | 545 ++++++++++++++++++++++++++++++ powerpc/Stacklayout.v | 134 ++++++++ powerpc/eabi/Conventions1.v | 539 ------------------------------ powerpc/eabi/Stacklayout.v | 134 -------- 19 files changed, 2103 insertions(+), 2687 deletions(-) create mode 100644 arm/Conventions1.v create mode 100644 arm/Stacklayout.v delete mode 100644 arm/eabi/Conventions1.v delete mode 100644 arm/eabi/Stacklayout.v delete mode 100644 arm/hardfloat/Conventions1.v delete mode 100644 arm/hardfloat/Stacklayout.v create mode 100644 ia32/Conventions1.v create mode 100644 ia32/Stacklayout.v delete mode 100644 ia32/standard/Conventions1.v delete mode 100644 ia32/standard/Stacklayout.v create mode 100644 powerpc/Conventions1.v create mode 100644 powerpc/Stacklayout.v delete mode 100644 powerpc/eabi/Conventions1.v delete mode 100644 powerpc/eabi/Stacklayout.v diff --git a/.depend b/.depend index 5c27a2c..87c4495 100644 --- a/.depend +++ b/.depend @@ -73,8 +73,8 @@ backend/Deadcode.vo backend/Deadcode.glob backend/Deadcode.v.beautified: backend backend/Deadcodeproof.vo backend/Deadcodeproof.glob backend/Deadcodeproof.v.beautified: backend/Deadcodeproof.v lib/Coqlib.vo common/Errors.vo lib/Maps.vo lib/IntvSets.vo common/AST.vo lib/Integers.vo lib/Floats.vo common/Values.vo common/Memory.vo common/Globalenvs.vo common/Events.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Registers.vo backend/RTL.vo lib/Lattice.vo backend/Kildall.vo backend/ValueDomain.vo backend/ValueAnalysis.vo backend/NeedDomain.vo $(ARCH)/NeedOp.vo backend/Deadcode.vo $(ARCH)/Machregs.vo $(ARCH)/Machregs.glob $(ARCH)/Machregs.v.beautified: $(ARCH)/Machregs.v lib/Coqlib.vo lib/Maps.vo common/AST.vo $(ARCH)/Op.vo backend/Locations.vo backend/Locations.glob backend/Locations.v.beautified: backend/Locations.v lib/Coqlib.vo lib/Maps.vo lib/Ordered.vo common/AST.vo common/Values.vo $(ARCH)/Machregs.vo -$(ARCH)/$(VARIANT)/Conventions1.vo $(ARCH)/$(VARIANT)/Conventions1.glob $(ARCH)/$(VARIANT)/Conventions1.v.beautified: $(ARCH)/$(VARIANT)/Conventions1.v lib/Coqlib.vo common/AST.vo common/Events.vo backend/Locations.vo -backend/Conventions.vo backend/Conventions.glob backend/Conventions.v.beautified: backend/Conventions.v lib/Coqlib.vo common/AST.vo backend/Locations.vo $(ARCH)/$(VARIANT)/Conventions1.vo +$(ARCH)/Conventions1.vo $(ARCH)/Conventions1.glob $(ARCH)/Conventions1.v.beautified: $(ARCH)/Conventions1.v lib/Coqlib.vo common/AST.vo common/Events.vo backend/Locations.vo $(ARCH)/Archi.vo +backend/Conventions.vo backend/Conventions.glob backend/Conventions.v.beautified: backend/Conventions.v lib/Coqlib.vo common/AST.vo backend/Locations.vo $(ARCH)/Conventions1.vo backend/LTL.vo backend/LTL.glob backend/LTL.v.beautified: backend/LTL.v lib/Coqlib.vo lib/Maps.vo common/AST.vo lib/Integers.vo common/Values.vo common/Events.vo common/Memory.vo common/Globalenvs.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Locations.vo backend/Conventions.vo backend/Allocation.vo backend/Allocation.glob backend/Allocation.v.beautified: backend/Allocation.v lib/FSetAVLplus.vo $(ARCH)/Archi.vo lib/Coqlib.vo lib/Ordered.vo common/Errors.vo lib/Maps.vo lib/Lattice.vo common/AST.vo lib/Integers.vo common/Memdata.vo $(ARCH)/Op.vo backend/Registers.vo backend/RTL.vo backend/Kildall.vo backend/Locations.vo backend/Conventions.vo backend/RTLtyping.vo backend/LTL.vo backend/Allocproof.vo backend/Allocproof.glob backend/Allocproof.v.beautified: backend/Allocproof.v $(ARCH)/Archi.vo lib/Coqlib.vo lib/Ordered.vo common/Errors.vo lib/Maps.vo lib/Lattice.vo common/AST.vo lib/Integers.vo common/Values.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Registers.vo backend/RTL.vo backend/RTLtyping.vo backend/Kildall.vo backend/Locations.vo backend/Conventions.vo backend/LTL.vo backend/Allocation.vo @@ -86,12 +86,12 @@ backend/Linearize.vo backend/Linearize.glob backend/Linearize.v.beautified: back backend/Linearizeproof.vo backend/Linearizeproof.glob backend/Linearizeproof.v.beautified: backend/Linearizeproof.v lib/Coqlib.vo lib/Maps.vo lib/Ordered.vo lib/Lattice.vo common/AST.vo lib/Integers.vo common/Values.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Errors.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Locations.vo backend/LTL.vo backend/Linear.vo backend/Linearize.vo backend/CleanupLabels.vo backend/CleanupLabels.glob backend/CleanupLabels.v.beautified: backend/CleanupLabels.v lib/Coqlib.vo lib/Ordered.vo backend/Linear.vo backend/CleanupLabelsproof.vo backend/CleanupLabelsproof.glob backend/CleanupLabelsproof.v.beautified: backend/CleanupLabelsproof.v lib/Coqlib.vo lib/Ordered.vo common/AST.vo lib/Integers.vo common/Values.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Locations.vo backend/Linear.vo backend/CleanupLabels.vo -backend/Mach.vo backend/Mach.glob backend/Mach.v.beautified: backend/Mach.v lib/Coqlib.vo lib/Maps.vo common/AST.vo lib/Integers.vo common/Values.vo common/Memory.vo common/Globalenvs.vo common/Events.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Locations.vo backend/Conventions.vo $(ARCH)/$(VARIANT)/Stacklayout.vo +backend/Mach.vo backend/Mach.glob backend/Mach.v.beautified: backend/Mach.v lib/Coqlib.vo lib/Maps.vo common/AST.vo lib/Integers.vo common/Values.vo common/Memory.vo common/Globalenvs.vo common/Events.vo common/Smallstep.vo $(ARCH)/Op.vo backend/Locations.vo backend/Conventions.vo $(ARCH)/Stacklayout.vo backend/Bounds.vo backend/Bounds.glob backend/Bounds.v.beautified: backend/Bounds.v lib/Coqlib.vo common/AST.vo $(ARCH)/Op.vo backend/Locations.vo backend/Linear.vo backend/Conventions.vo -$(ARCH)/$(VARIANT)/Stacklayout.vo $(ARCH)/$(VARIANT)/Stacklayout.glob $(ARCH)/$(VARIANT)/Stacklayout.v.beautified: $(ARCH)/$(VARIANT)/Stacklayout.v lib/Coqlib.vo backend/Bounds.vo -backend/Stacking.vo backend/Stacking.glob backend/Stacking.v.beautified: backend/Stacking.v lib/Coqlib.vo common/Errors.vo common/AST.vo lib/Integers.vo $(ARCH)/Op.vo backend/Locations.vo backend/Linear.vo backend/Bounds.vo backend/Mach.vo backend/Conventions.vo $(ARCH)/$(VARIANT)/Stacklayout.vo backend/Lineartyping.vo -backend/Stackingproof.vo backend/Stackingproof.glob backend/Stackingproof.v.beautified: backend/Stackingproof.v lib/Coqlib.vo common/Errors.vo common/AST.vo lib/Integers.vo common/Values.vo $(ARCH)/Op.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo backend/Locations.vo backend/LTL.vo backend/Linear.vo backend/Lineartyping.vo backend/Mach.vo backend/Bounds.vo backend/Conventions.vo $(ARCH)/$(VARIANT)/Stacklayout.vo backend/Stacking.vo -$(ARCH)/Asm.vo $(ARCH)/Asm.glob $(ARCH)/Asm.v.beautified: $(ARCH)/Asm.v lib/Coqlib.vo lib/Maps.vo common/AST.vo lib/Integers.vo lib/Floats.vo common/Values.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo backend/Locations.vo $(ARCH)/$(VARIANT)/Stacklayout.vo backend/Conventions.vo +$(ARCH)/Stacklayout.vo $(ARCH)/Stacklayout.glob $(ARCH)/Stacklayout.v.beautified: $(ARCH)/Stacklayout.v lib/Coqlib.vo backend/Bounds.vo +backend/Stacking.vo backend/Stacking.glob backend/Stacking.v.beautified: backend/Stacking.v lib/Coqlib.vo common/Errors.vo common/AST.vo lib/Integers.vo $(ARCH)/Op.vo backend/Locations.vo backend/Linear.vo backend/Bounds.vo backend/Mach.vo backend/Conventions.vo $(ARCH)/Stacklayout.vo backend/Lineartyping.vo +backend/Stackingproof.vo backend/Stackingproof.glob backend/Stackingproof.v.beautified: backend/Stackingproof.v lib/Coqlib.vo common/Errors.vo common/AST.vo lib/Integers.vo common/Values.vo $(ARCH)/Op.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo backend/Locations.vo backend/LTL.vo backend/Linear.vo backend/Lineartyping.vo backend/Mach.vo backend/Bounds.vo backend/Conventions.vo $(ARCH)/Stacklayout.vo backend/Stacking.vo +$(ARCH)/Asm.vo $(ARCH)/Asm.glob $(ARCH)/Asm.v.beautified: $(ARCH)/Asm.v lib/Coqlib.vo lib/Maps.vo common/AST.vo lib/Integers.vo lib/Floats.vo common/Values.vo common/Memory.vo common/Events.vo common/Globalenvs.vo common/Smallstep.vo backend/Locations.vo $(ARCH)/Stacklayout.vo backend/Conventions.vo $(ARCH)/Asmgen.vo $(ARCH)/Asmgen.glob $(ARCH)/Asmgen.v.beautified: $(ARCH)/Asmgen.v lib/Coqlib.vo common/Errors.vo common/AST.vo lib/Integers.vo lib/Floats.vo $(ARCH)/Op.vo backend/Locations.vo backend/Mach.vo $(ARCH)/Asm.vo backend/Asmgenproof0.vo backend/Asmgenproof0.glob backend/Asmgenproof0.v.beautified: backend/Asmgenproof0.v lib/Coqlib.vo lib/Intv.vo common/AST.vo common/Errors.vo lib/Integers.vo lib/Floats.vo common/Values.vo common/Memory.vo common/Globalenvs.vo common/Events.vo common/Smallstep.vo backend/Locations.vo backend/Mach.vo $(ARCH)/Asm.vo $(ARCH)/Asmgen.vo backend/Conventions.vo $(ARCH)/Asmgenproof1.vo $(ARCH)/Asmgenproof1.glob $(ARCH)/Asmgenproof1.v.beautified: $(ARCH)/Asmgenproof1.v lib/Coqlib.vo common/Errors.vo lib/Maps.vo common/AST.vo lib/Integers.vo lib/Floats.vo common/Values.vo common/Memory.vo common/Globalenvs.vo $(ARCH)/Op.vo backend/Locations.vo backend/Mach.vo $(ARCH)/Asm.vo $(ARCH)/Asmgen.vo backend/Conventions.vo backend/Asmgenproof0.vo diff --git a/Makefile b/Makefile index 4027a38..c533e2d 100644 --- a/Makefile +++ b/Makefile @@ -15,14 +15,13 @@ include Makefile.config -DIRS=lib common $(ARCH)/$(VARIANT) $(ARCH) backend cfrontend driver \ +DIRS=lib common $(ARCH) backend cfrontend driver \ flocq/Core flocq/Prop flocq/Calc flocq/Appli exportclight \ cparser cparser/validator RECDIRS=lib common backend cfrontend driver flocq exportclight cparser COQINCLUDES=$(foreach d, $(RECDIRS), -R $(d) -as compcert.$(d)) \ - -I $(ARCH)/$(VARIANT) -as compcert.$(ARCH).$(VARIANT) \ -I $(ARCH) -as compcert.$(ARCH) CAMLINCLUDES=$(patsubst %,-I %, $(DIRS)) -I extraction @@ -241,8 +240,7 @@ cparser/Parser.v: cparser/Parser.vy depend: $(FILES) exportclight/Clightdefs.v $(COQDEP) $^ \ - | sed -e 's|$(ARCH)/$(VARIANT)/|$$(ARCH)/$$(VARIANT)/|g' \ - -e 's|$(ARCH)/|$$(ARCH)/|g' \ + | sed -e 's|$(ARCH)/|$$(ARCH)/|g' \ > .depend install: diff --git a/arm/Archi.v b/arm/Archi.v index 5657f31..1306459 100644 --- a/arm/Archi.v +++ b/arm/Archi.v @@ -46,3 +46,6 @@ Definition choose_binop_pl_32 (s1: bool) (pl1: nan_pl 24) (s2: bool) (pl2: nan_p Global Opaque big_endian default_pl_64 choose_binop_pl_64 default_pl_32 choose_binop_pl_32. + +Inductive abi_kind := Softfloat | Hardfloat. +Parameter abi: abi_kind. diff --git a/arm/Conventions1.v b/arm/Conventions1.v new file mode 100644 index 0000000..1689c77 --- /dev/null +++ b/arm/Conventions1.v @@ -0,0 +1,770 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Function calling conventions and other conventions regarding the use of + machine registers and stack slots. *) + +Require Import Coqlib. +Require Import AST. +Require Import Events. +Require Import Locations. +Require Archi. + +(** * Classification of machine registers *) + +(** Machine registers (type [mreg] in module [Locations]) are divided in + the following groups: +- Temporaries used for spilling, reloading, and parallel move operations. +- Allocatable registers, that can be assigned to RTL pseudo-registers. + These are further divided into: +-- Callee-save registers, whose value is preserved across a function call. +-- Caller-save registers that can be modified during a function call. + + We follow the PowerPC application binary interface (ABI) in our choice + of callee- and caller-save registers. +*) + +Definition int_caller_save_regs := + R0 :: R1 :: R2 :: R3 :: R12 :: nil. + +Definition float_caller_save_regs := + F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: nil. + +Definition int_callee_save_regs := + R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: R11 :: nil. + +Definition float_callee_save_regs := + F8 :: F9 :: F10 :: F11 :: F12 :: F13 :: F14 :: F15 :: nil. + +Definition destroyed_at_call := + int_caller_save_regs ++ float_caller_save_regs. + +Definition dummy_int_reg := R0. (**r Used in [Coloring]. *) +Definition dummy_float_reg := F0. (**r Used in [Coloring]. *) + +(** The [index_int_callee_save] and [index_float_callee_save] associate + a unique positive integer to callee-save registers. This integer is + used in [Stacking] to determine where to save these registers in + the activation record if they are used by the current function. *) + +Definition index_int_callee_save (r: mreg) := + match r with + | R4 => 0 | R5 => 1 | R6 => 2 | R7 => 3 + | R8 => 4 | R9 => 5 | R10 => 6 | R11 => 7 + | _ => -1 + end. + +Definition index_float_callee_save (r: mreg) := + match r with + | F8 => 0 | F9 => 1 | F10 => 2 | F11 => 3 + | F12 => 4 | F13 => 5 | F14 => 6 | F15 => 7 + | _ => -1 + end. + +Ltac ElimOrEq := + match goal with + | |- (?x = ?y) \/ _ -> _ => + let H := fresh in + (intro H; elim H; clear H; + [intro H; rewrite <- H; clear H | ElimOrEq]) + | |- False -> _ => + let H := fresh in (intro H; contradiction) + end. + +Ltac OrEq := + match goal with + | |- (?x = ?x) \/ _ => left; reflexivity + | |- (?x = ?y) \/ _ => right; OrEq + | |- False => fail + end. + +Ltac NotOrEq := + match goal with + | |- (?x = ?y) \/ _ -> False => + let H := fresh in ( + intro H; elim H; clear H; [intro; discriminate | NotOrEq]) + | |- False -> False => + contradiction + end. + +Lemma index_int_callee_save_pos: + forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. +Qed. + +Lemma index_float_callee_save_pos: + forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. +Qed. + +Lemma index_int_callee_save_pos2: + forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. +Proof. + destruct r; simpl; intro; omegaContradiction || OrEq. +Qed. + +Lemma index_float_callee_save_pos2: + forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. +Proof. + destruct r; simpl; intro; omegaContradiction || OrEq. +Qed. + +Lemma index_int_callee_save_inj: + forall r1 r2, + In r1 int_callee_save_regs -> + In r2 int_callee_save_regs -> + r1 <> r2 -> + index_int_callee_save r1 <> index_int_callee_save r2. +Proof. + intros r1 r2. + simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; + intros; congruence. +Qed. + +Lemma index_float_callee_save_inj: + forall r1 r2, + In r1 float_callee_save_regs -> + In r2 float_callee_save_regs -> + r1 <> r2 -> + index_float_callee_save r1 <> index_float_callee_save r2. +Proof. + intros r1 r2. + simpl; ElimOrEq; ElimOrEq; unfold index_float_callee_save; + intros; congruence. +Qed. + +(** The following lemmas show that + (temporaries, destroyed at call, integer callee-save, float callee-save) + is a partition of the set of machine registers. *) + +Lemma int_float_callee_save_disjoint: + list_disjoint int_callee_save_regs float_callee_save_regs. +Proof. + red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. +Qed. + +Lemma register_classification: + forall r, + In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. +Proof. + destruct r; + try (left; simpl; OrEq); + try (right; left; simpl; OrEq); + try (right; right; simpl; OrEq). +Qed. + + +Lemma int_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r int_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma float_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r float_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma int_callee_save_type: + forall r, In r int_callee_save_regs -> mreg_type r = Tany32. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Lemma float_callee_save_type: + forall r, In r float_callee_save_regs -> mreg_type r = Tany64. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Ltac NoRepet := + match goal with + | |- list_norepet nil => + apply list_norepet_nil + | |- list_norepet (?a :: ?b) => + apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] + end. + +Lemma int_callee_save_norepet: + list_norepet int_callee_save_regs. +Proof. + unfold int_callee_save_regs; NoRepet. +Qed. + +Lemma float_callee_save_norepet: + list_norepet float_callee_save_regs. +Proof. + unfold float_callee_save_regs; NoRepet. +Qed. + +(** * Function calling conventions *) + +(** The functions in this section determine the locations (machine registers + and stack slots) used to communicate arguments and results between the + caller and the callee during function calls. These locations are functions + of the signature of the function and of the call instruction. + Agreement between the caller and the callee on the locations to use + is guaranteed by our dynamic semantics for Cminor and RTL, which demand + that the signature of the call instruction is identical to that of the + called function. + + Calling conventions are largely arbitrary: they must respect the properties + proved in this section (such as no overlapping between the locations + of function arguments), but this leaves much liberty in choosing actual + locations. *) + +(** ** Location of function result *) + +(** The result value of a function is passed back to the caller in + registers [R0] or [F0] or [R0,R1], depending on the type of the + returned value. We treat a function without result as a function + with one integer result. + + For the "softfloat" convention, results of FP types should be passed + in [R0] or [R0,R1]. This doesn't fit the CompCert register model, + so we have code in [arm/PrintAsm.ml] that inserts additional moves + to/from [F0]. *) + +Definition loc_result (s: signature) : list mreg := + match s.(sig_res) with + | None => R0 :: nil + | Some (Tint | Tany32) => R0 :: nil + | Some (Tfloat | Tsingle | Tany64) => F0 :: nil + | Some Tlong => R1 :: R0 :: nil + end. + +(** The result registers have types compatible with that given in the signature. *) + +Lemma loc_result_type: + forall sig, + subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. +Proof. + intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. +Qed. + +(** The result locations are caller-save registers *) + +Lemma loc_result_caller_save: + forall (s: signature) (r: mreg), + In r (loc_result s) -> In r destroyed_at_call. +Proof. + intros. + assert (r = R0 \/ r = R1 \/ r = F0). + unfold loc_result in H. destruct (sig_res s); [destruct t|idtac]; simpl in H; intuition. + destruct H0 as [A | [A | A]]; subst r; simpl; OrEq. +Qed. + +(** ** Location of function arguments *) + +(** For the "hardfloat" configuration, we use the following calling conventions, + adapted from the ARM EABI-HF: +- The first 4 integer arguments are passed in registers [R0] to [R3]. +- The first 2 long integer arguments are passed in an aligned pair of + two integer registers. +- The first 8 single- and double-precision float arguments are passed + in registers [F0...F7] +- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively + assigned (1 word for an integer or single argument, 2 words for a float + or a long), starting at word offset 0. + +This convention is not quite that of the ARM EABI-HF, whereas single float +arguments are passed in 32-bit float registers. Unfortunately, +this does not fit the data model of CompCert. In [PrintAsm.ml] +we insert additional code around function calls that moves +data appropriately. *) + +Definition int_param_regs := + R0 :: R1 :: R2 :: R3 :: nil. + +Definition float_param_regs := + F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: nil. + +Definition ireg_param (n: Z) : mreg := + match list_nth_z int_param_regs n with Some r => r | None => R0 end. + +Definition freg_param (n: Z) : mreg := + match list_nth_z float_param_regs n with Some r => r | None => F0 end. + +Fixpoint loc_arguments_hf + (tyl: list typ) (ir fr ofs: Z) {struct tyl} : list loc := + match tyl with + | nil => nil + | (Tint | Tany32) as ty :: tys => + if zlt ir 4 + then R (ireg_param ir) :: loc_arguments_hf tys (ir + 1) fr ofs + else S Outgoing ofs ty :: loc_arguments_hf tys ir fr (ofs + 1) + | (Tfloat | Tany64) as ty :: tys => + if zlt fr 8 + then R (freg_param fr) :: loc_arguments_hf tys ir (fr + 1) ofs + else let ofs := align ofs 2 in + S Outgoing ofs ty :: loc_arguments_hf tys ir fr (ofs + 2) + | Tsingle :: tys => + if zlt fr 8 + then R (freg_param fr) :: loc_arguments_hf tys ir (fr + 1) ofs + else S Outgoing ofs Tsingle :: loc_arguments_hf tys ir fr (ofs + 1) + | Tlong :: tys => + let ir := align ir 2 in + if zlt ir 4 + then R (ireg_param (ir + 1)) :: R (ireg_param ir) :: loc_arguments_hf tys (ir + 2) fr ofs + else let ofs := align ofs 2 in + S Outgoing (ofs + 1) Tint :: S Outgoing ofs Tint :: loc_arguments_hf tys ir fr (ofs + 2) + end. + +(** For the "softfloat" configuration, as well as for variable-argument functions + in the "hardfloat" configuration, we use the default ARM EABI (not HF) + calling conventions: +- The first 4 integer arguments are passed in registers [R0] to [R3]. +- The first 2 long integer arguments are passed in an aligned pair of + two integer registers. +- The first 2 double-precision float arguments are passed in [F0] or [F2] +- The first 4 single-precision float arguments are passed in [F0...F3] +- Integer arguments and float arguments are kept in sync so that + they can all be mapped back to [R0...R3] in [PrintAsm.ml]. +- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively + assigned (1 word for an integer or single argument, 2 words for a float + or a long), starting at word offset 0. + +This convention is not quite that of the ARM EABI, whereas every float +argument are passed in one or two integer registers. Unfortunately, +this does not fit the data model of CompCert. In [PrintAsm.ml] +we insert additional code around function calls and returns that moves +data appropriately. *) + +Fixpoint loc_arguments_sf + (tyl: list typ) (ofs: Z) {struct tyl} : list loc := + match tyl with + | nil => nil + | (Tint|Tany32) as ty :: tys => + (if zlt ofs 0 then R (ireg_param (ofs + 4)) else S Outgoing ofs ty) + :: loc_arguments_sf tys (ofs + 1) + | (Tfloat|Tany64) as ty :: tys => + let ofs := align ofs 2 in + (if zlt ofs 0 then R (freg_param (ofs + 4)) else S Outgoing ofs ty) + :: loc_arguments_sf tys (ofs + 2) + | Tsingle :: tys => + (if zlt ofs 0 then R (freg_param (ofs + 4)) else S Outgoing ofs Tsingle) + :: loc_arguments_sf tys (ofs + 1) + | Tlong :: tys => + let ofs := align ofs 2 in + (if zlt ofs 0 then R (ireg_param (ofs+1+4)) else S Outgoing (ofs+1) Tint) + :: (if zlt ofs 0 then R (ireg_param (ofs+4)) else S Outgoing ofs Tint) + :: loc_arguments_sf tys (ofs + 2) + end. + +(** [loc_arguments s] returns the list of locations where to store arguments + when calling a function with signature [s]. *) + +Definition loc_arguments (s: signature) : list loc := + match Archi.abi with + | Archi.Softfloat => + loc_arguments_sf s.(sig_args) (-4) + | Archi.Hardfloat => + if s.(sig_cc).(cc_vararg) + then loc_arguments_sf s.(sig_args) (-4) + else loc_arguments_hf s.(sig_args) 0 0 0 + end. + +(** [size_arguments s] returns the number of [Outgoing] slots used + to call a function with signature [s]. *) + +Fixpoint size_arguments_hf (tyl: list typ) (ir fr ofs: Z) {struct tyl} : Z := + match tyl with + | nil => ofs + | (Tint|Tany32) :: tys => + if zlt ir 4 + then size_arguments_hf tys (ir + 1) fr ofs + else size_arguments_hf tys ir fr (ofs + 1) + | (Tfloat|Tany64) :: tys => + if zlt fr 8 + then size_arguments_hf tys ir (fr + 1) ofs + else size_arguments_hf tys ir fr (align ofs 2 + 2) + | Tsingle :: tys => + if zlt fr 8 + then size_arguments_hf tys ir (fr + 1) ofs + else size_arguments_hf tys ir fr (ofs + 1) + | Tlong :: tys => + let ir := align ir 2 in + if zlt ir 4 + then size_arguments_hf tys (ir + 2) fr ofs + else size_arguments_hf tys ir fr (align ofs 2 + 2) + end. + +Fixpoint size_arguments_sf (tyl: list typ) (ofs: Z) {struct tyl} : Z := + match tyl with + | nil => Zmax 0 ofs + | (Tint | Tsingle | Tany32) :: tys => size_arguments_sf tys (ofs + 1) + | (Tfloat | Tlong | Tany64) :: tys => size_arguments_sf tys (align ofs 2 + 2) + end. + +Definition size_arguments (s: signature) : Z := + match Archi.abi with + | Archi.Softfloat => + size_arguments_sf s.(sig_args) (-4) + | Archi.Hardfloat => + if s.(sig_cc).(cc_vararg) + then size_arguments_sf s.(sig_args) (-4) + else size_arguments_hf s.(sig_args) 0 0 0 + end. + +(** Argument locations are either non-temporary registers or [Outgoing] + stack slots at nonnegative offsets. *) + +Definition loc_argument_acceptable (l: loc) : Prop := + match l with + | R r => In r destroyed_at_call + | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong + | _ => False + end. + +Remark ireg_param_in_params: forall n, In (ireg_param n) int_param_regs. +Proof. + unfold ireg_param; intros. + destruct (list_nth_z int_param_regs n) as [r|] eqn:NTH. + eapply list_nth_z_in; eauto. + simpl; auto. +Qed. + +Remark freg_param_in_params: forall n, In (freg_param n) float_param_regs. +Proof. + unfold freg_param; intros. + destruct (list_nth_z float_param_regs n) as [r|] eqn:NTH. + eapply list_nth_z_in; eauto. + simpl; auto. +Qed. + +Remark loc_arguments_hf_charact: + forall tyl ir fr ofs l, + In l (loc_arguments_hf tyl ir fr ofs) -> + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong + | S _ _ _ => False + end. +Proof. + assert (INCR: forall l ofs1 ofs2, + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= ofs2 /\ ty <> Tlong + | S _ _ _ => False + end -> + ofs1 <= ofs2 -> + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= ofs1 /\ ty <> Tlong + | S _ _ _ => False + end). + { + intros. destruct l; auto. destruct sl; auto. intuition omega. + } + induction tyl; simpl loc_arguments_hf; intros. + elim H. + destruct a. +- (* int *) + destruct (zlt ir 4); destruct H. + subst. left; apply ireg_param_in_params. + eapply IHtyl; eauto. + subst. split; [omega | congruence]. + eapply INCR. eapply IHtyl; eauto. omega. +- (* float *) + destruct (zlt fr 8); destruct H. + subst. right; apply freg_param_in_params. + eapply IHtyl; eauto. + subst. split. apply Zle_ge. apply align_le. omega. congruence. + eapply INCR. eapply IHtyl; eauto. + apply Zle_trans with (align ofs 2). apply align_le; omega. omega. +- (* long *) + set (ir' := align ir 2) in *. + assert (ofs <= align ofs 2) by (apply align_le; omega). + destruct (zlt ir' 4). + destruct H. subst l; left; apply ireg_param_in_params. + destruct H. subst l; left; apply ireg_param_in_params. + eapply IHtyl; eauto. + destruct H. subst l; split; [ omega | congruence ]. + destruct H. subst l; split; [ omega | congruence ]. + eapply INCR. eapply IHtyl; eauto. omega. +- (* single *) + destruct (zlt fr 8); destruct H. + subst. right; apply freg_param_in_params. + eapply IHtyl; eauto. + subst. split; [omega | congruence]. + eapply INCR. eapply IHtyl; eauto. omega. +- (* any32 *) + destruct (zlt ir 4); destruct H. + subst. left; apply ireg_param_in_params. + eapply IHtyl; eauto. + subst. split; [omega | congruence]. + eapply INCR. eapply IHtyl; eauto. omega. +- (* any64 *) + destruct (zlt fr 8); destruct H. + subst. right; apply freg_param_in_params. + eapply IHtyl; eauto. + subst. split. apply Zle_ge. apply align_le. omega. congruence. + eapply INCR. eapply IHtyl; eauto. + apply Zle_trans with (align ofs 2). apply align_le; omega. omega. +Qed. + +Remark loc_arguments_sf_charact: + forall tyl ofs l, + In l (loc_arguments_sf tyl ofs) -> + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs /\ ty <> Tlong + | S _ _ _ => False + end. +Proof. + assert (INCR: forall l ofs1 ofs2, + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs2 /\ ty <> Tlong + | S _ _ _ => False + end -> + ofs1 <= ofs2 -> + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs1 /\ ty <> Tlong + | S _ _ _ => False + end). + { + intros. destruct l; auto. destruct sl; auto. intuition xomega. + } + induction tyl; simpl loc_arguments_sf; intros. + elim H. + destruct a. +- (* int *) + destruct H. + destruct (zlt ofs 0); subst l. + left; apply ireg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +- (* float *) + set (ofs' := align ofs 2) in *. + assert (ofs <= ofs') by (apply align_le; omega). + destruct H. + destruct (zlt ofs' 0); subst l. + right; apply freg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +- (* long *) + set (ofs' := align ofs 2) in *. + assert (ofs <= ofs') by (apply align_le; omega). + destruct H. + destruct (zlt ofs' 0); subst l. + left; apply ireg_param_in_params. + split. xomega. congruence. + destruct H. + destruct (zlt ofs' 0); subst l. + left; apply ireg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +- (* single *) + destruct H. + destruct (zlt ofs 0); subst l. + right; apply freg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +- (* any32 *) + destruct H. + destruct (zlt ofs 0); subst l. + left; apply ireg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +- (* any64 *) + set (ofs' := align ofs 2) in *. + assert (ofs <= ofs') by (apply align_le; omega). + destruct H. + destruct (zlt ofs' 0); subst l. + right; apply freg_param_in_params. + split. xomega. congruence. + eapply INCR. eapply IHtyl; eauto. omega. +Qed. + +Lemma loc_arguments_acceptable: + forall (s: signature) (l: loc), + In l (loc_arguments s) -> loc_argument_acceptable l. +Proof. + unfold loc_arguments; intros. + assert (forall r, In r int_param_regs \/ In r float_param_regs -> In r destroyed_at_call). + { + intros. elim H0; simpl; ElimOrEq; OrEq. + } + assert (In l (loc_arguments_sf (sig_args s) (-4)) -> loc_argument_acceptable l). + { intros. red. exploit loc_arguments_sf_charact; eauto. destruct l; auto. } + assert (In l (loc_arguments_hf (sig_args s) 0 0 0) -> loc_argument_acceptable l). + { intros. red. exploit loc_arguments_hf_charact; eauto. destruct l; auto. } + destruct Archi.abi; [ | destruct (cc_vararg (sig_cc s)) ]; auto. +Qed. + +Hint Resolve loc_arguments_acceptable: locs. + +(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) + +Remark size_arguments_hf_above: + forall tyl ir fr ofs0, + ofs0 <= size_arguments_hf tyl ir fr ofs0. +Proof. + induction tyl; simpl; intros. + omega. + destruct a. + destruct (zlt ir 4); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. + destruct (zlt fr 8); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + set (ir' := align ir 2). + destruct (zlt ir' 4); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + destruct (zlt fr 8); eauto. + apply Zle_trans with (ofs0 + 1); eauto. omega. + destruct (zlt ir 4); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. + destruct (zlt fr 8); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. +Qed. + +Remark size_arguments_sf_above: + forall tyl ofs0, + Zmax 0 ofs0 <= size_arguments_sf tyl ofs0. +Proof. + induction tyl; simpl; intros. + omega. + destruct a; (eapply Zle_trans; [idtac|eauto]). + xomega. + assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. + assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. + xomega. + xomega. + assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. +Qed. + +Lemma size_arguments_above: + forall s, size_arguments s >= 0. +Proof. + intros; unfold size_arguments. apply Zle_ge. + assert (0 <= size_arguments_sf (sig_args s) (-4)). + { change 0 with (Zmax 0 (-4)). apply size_arguments_sf_above. } + assert (0 <= size_arguments_hf (sig_args s) 0 0 0). + { apply size_arguments_hf_above. } + destruct Archi.abi; [ | destruct (cc_vararg (sig_cc s)) ]; auto. +Qed. + +Lemma loc_arguments_hf_bounded: + forall ofs ty tyl ir fr ofs0, + In (S Outgoing ofs ty) (loc_arguments_hf tyl ir fr ofs0) -> + ofs + typesize ty <= size_arguments_hf tyl ir fr ofs0. +Proof. + induction tyl; simpl; intros. + elim H. + destruct a. +- (* int *) + destruct (zlt ir 4); destruct H. + discriminate. + eauto. + inv H. apply size_arguments_hf_above. + eauto. +- (* float *) + destruct (zlt fr 8); destruct H. + discriminate. + eauto. + inv H. apply size_arguments_hf_above. + eauto. +- (* long *) + destruct (zlt (align ir 2) 4). + destruct H. discriminate. destruct H. discriminate. eauto. + destruct H. inv H. + rewrite <- Zplus_assoc. simpl. apply size_arguments_hf_above. + destruct H. inv H. + eapply Zle_trans. 2: apply size_arguments_hf_above. simpl; omega. + eauto. +- (* float *) + destruct (zlt fr 8); destruct H. + discriminate. + eauto. + inv H. apply size_arguments_hf_above. + eauto. +- (* any32 *) + destruct (zlt ir 4); destruct H. + discriminate. + eauto. + inv H. apply size_arguments_hf_above. + eauto. +- (* any64 *) + destruct (zlt fr 8); destruct H. + discriminate. + eauto. + inv H. apply size_arguments_hf_above. + eauto. +Qed. + +Lemma loc_arguments_sf_bounded: + forall ofs ty tyl ofs0, + In (S Outgoing ofs ty) (loc_arguments_sf tyl ofs0) -> + Zmax 0 (ofs + typesize ty) <= size_arguments_sf tyl ofs0. +Proof. + induction tyl; simpl; intros. + elim H. + destruct a. +- (* int *) + destruct H. + destruct (zlt ofs0 0); inv H. apply size_arguments_sf_above. + eauto. +- (* float *) + destruct H. + destruct (zlt (align ofs0 2) 0); inv H. apply size_arguments_sf_above. + eauto. +- (* long *) + destruct H. + destruct (zlt (align ofs0 2) 0); inv H. + rewrite <- Zplus_assoc. simpl. apply size_arguments_sf_above. + destruct H. + destruct (zlt (align ofs0 2) 0); inv H. + eapply Zle_trans. 2: apply size_arguments_sf_above. simpl; xomega. + eauto. +- (* float *) + destruct H. + destruct (zlt ofs0 0); inv H. apply size_arguments_sf_above. + eauto. +- (* any32 *) + destruct H. + destruct (zlt ofs0 0); inv H. apply size_arguments_sf_above. + eauto. +- (* any64 *) + destruct H. + destruct (zlt (align ofs0 2) 0); inv H. apply size_arguments_sf_above. + eauto. +Qed. + +Lemma loc_arguments_bounded: + forall (s: signature) (ofs: Z) (ty: typ), + In (S Outgoing ofs ty) (loc_arguments s) -> + ofs + typesize ty <= size_arguments s. +Proof. + unfold loc_arguments, size_arguments; intros. + assert (In (S Outgoing ofs ty) (loc_arguments_sf (sig_args s) (-4)) -> + ofs + typesize ty <= size_arguments_sf (sig_args s) (-4)). + { intros. eapply Zle_trans. 2: eapply loc_arguments_sf_bounded; eauto. xomega. } + assert (In (S Outgoing ofs ty) (loc_arguments_hf (sig_args s) 0 0 0) -> + ofs + typesize ty <= size_arguments_hf (sig_args s) 0 0 0). + { intros. eapply loc_arguments_hf_bounded; eauto. } + destruct Archi.abi; [ | destruct (cc_vararg (sig_cc s)) ]; eauto. +Qed. + +Lemma loc_arguments_main: + loc_arguments signature_main = nil. +Proof. + unfold loc_arguments. + destruct Archi.abi; reflexivity. +Qed. diff --git a/arm/Stacklayout.v b/arm/Stacklayout.v new file mode 100644 index 0000000..7694dcf --- /dev/null +++ b/arm/Stacklayout.v @@ -0,0 +1,132 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Machine- and ABI-dependent layout information for activation records. *) + +Require Import Coqlib. +Require Import Bounds. + +(** The general shape of activation records is as follows, + from bottom (lowest offsets) to top: +- Space for outgoing arguments to function calls. +- Local stack slots. +- Saved values of integer callee-save registers used by the function. +- Saved values of float callee-save registers used by the function. +- Saved return address into caller. +- Pointer to activation record of the caller. +- Space for the stack-allocated data declared in Cminor. + +The [frame_env] compilation environment records the positions of +the boundaries between areas in the frame part. +*) + +Definition fe_ofs_arg := 0. + +Record frame_env : Type := mk_frame_env { + fe_size: Z; + fe_ofs_link: Z; + fe_ofs_retaddr: Z; + fe_ofs_local: Z; + fe_ofs_int_callee_save: Z; + fe_num_int_callee_save: Z; + fe_ofs_float_callee_save: Z; + fe_num_float_callee_save: Z; + fe_stack_data: Z +}. + +(** Computation of the frame environment from the bounds of the current + function. *) + +Definition make_env (b: bounds) := + let ol := align (4 * b.(bound_outgoing)) 8 in (* locals *) + let oics := ol + 4 * b.(bound_local) in (* integer callee-saves *) + let oendi := oics + 4 * b.(bound_int_callee_save) in + let ofcs := align oendi 8 in (* float callee-saves *) + let ora := ofcs + 8 * b.(bound_float_callee_save) in (* retaddr *) + let olink := ora + 4 in (* back link *) + let ostkdata := olink + 4 in (* stack data *) + let sz := align (ostkdata + b.(bound_stack_data)) 8 in + mk_frame_env sz olink ora ol + oics b.(bound_int_callee_save) + ofcs b.(bound_float_callee_save) + ostkdata. + +(** Separation property *) + +Remark frame_env_separated: + forall b, + let fe := make_env b in + 0 <= fe_ofs_arg + /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_local) + /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_ofs_int_callee_save) + /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) + /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_ofs_retaddr) + /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_ofs_link) + /\ fe.(fe_ofs_link) + 4 <= fe.(fe_stack_data) + /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_size). +Proof. + intros. + generalize (align_le (4 * bound_outgoing b) 8 (refl_equal)). + generalize (align_le (fe_ofs_int_callee_save fe + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). + generalize (align_le (fe_stack_data fe + b.(bound_stack_data)) 8 (refl_equal)). + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data, fe_ofs_arg. + intros. + generalize (bound_local_pos b); intro; + generalize (bound_int_callee_save_pos b); intro; + generalize (bound_float_callee_save_pos b); intro; + generalize (bound_outgoing_pos b); intro; + generalize (bound_stack_data_pos b); intro. + omega. +Qed. + +(** Alignment property *) + +Remark frame_env_aligned: + forall b, + let fe := make_env b in + (4 | fe.(fe_ofs_link)) + /\ (8 | fe.(fe_ofs_local)) + /\ (4 | fe.(fe_ofs_int_callee_save)) + /\ (8 | fe.(fe_ofs_float_callee_save)) + /\ (4 | fe.(fe_ofs_retaddr)) + /\ (8 | fe.(fe_stack_data)) + /\ (8 | fe.(fe_size)). +Proof. + intros. + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data. + set (x1 := 4 * bound_outgoing b). + assert (4 | x1). unfold x1; exists (bound_outgoing b); ring. + set (x2 := align x1 8). + assert (8 | x2). apply align_divides. omega. + set (x3 := x2 + 4 * bound_local b). + assert (4 | x3). apply Zdivide_plus_r. apply Zdivides_trans with 8; auto. exists 2; auto. + exists (bound_local b); ring. + set (x4 := align (x3 + 4 * bound_int_callee_save b) 8). + assert (8 | x4). apply align_divides. omega. + set (x5 := x4 + 8 * bound_float_callee_save b). + assert (8 | x5). apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. + assert (4 | x5). apply Zdivides_trans with 8; auto. exists 2; auto. + set (x6 := x5 + 4). + assert (4 | x6). apply Zdivide_plus_r; auto. exists 1; auto. + set (x7 := x6 + 4). + assert (8 | x7). unfold x7, x6. replace (x5 + 4 + 4) with (x5 + 8) by omega. + apply Zdivide_plus_r; auto. exists 1; auto. + set (x8 := align (x7 + bound_stack_data b) 8). + assert (8 | x8). apply align_divides. omega. + tauto. +Qed. diff --git a/arm/eabi/Conventions1.v b/arm/eabi/Conventions1.v deleted file mode 100644 index c26d29e..0000000 --- a/arm/eabi/Conventions1.v +++ /dev/null @@ -1,509 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Function calling conventions and other conventions regarding the use of - machine registers and stack slots. *) - -Require Import Coqlib. -Require Import AST. -Require Import Events. -Require Import Locations. - -(** * Classification of machine registers *) - -(** Machine registers (type [mreg] in module [Locations]) are divided in - the following groups: -- Temporaries used for spilling, reloading, and parallel move operations. -- Allocatable registers, that can be assigned to RTL pseudo-registers. - These are further divided into: --- Callee-save registers, whose value is preserved across a function call. --- Caller-save registers that can be modified during a function call. - - We follow the PowerPC application binary interface (ABI) in our choice - of callee- and caller-save registers. -*) - -Definition int_caller_save_regs := - R0 :: R1 :: R2 :: R3 :: R12 :: nil. - -Definition float_caller_save_regs := - F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: nil. - -Definition int_callee_save_regs := - R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: R11 :: nil. - -Definition float_callee_save_regs := - F8 :: F9 :: F10 :: F11 :: F12 :: F13 :: F14 :: F15 :: nil. - -Definition destroyed_at_call := - int_caller_save_regs ++ float_caller_save_regs. - -Definition dummy_int_reg := R0. (**r Used in [Coloring]. *) -Definition dummy_float_reg := F0. (**r Used in [Coloring]. *) - -(** The [index_int_callee_save] and [index_float_callee_save] associate - a unique positive integer to callee-save registers. This integer is - used in [Stacking] to determine where to save these registers in - the activation record if they are used by the current function. *) - -Definition index_int_callee_save (r: mreg) := - match r with - | R4 => 0 | R5 => 1 | R6 => 2 | R7 => 3 - | R8 => 4 | R9 => 5 | R10 => 6 | R11 => 7 - | _ => -1 - end. - -Definition index_float_callee_save (r: mreg) := - match r with - | F8 => 0 | F9 => 1 | F10 => 2 | F11 => 3 - | F12 => 4 | F13 => 5 | F14 => 6 | F15 => 7 - | _ => -1 - end. - -Ltac ElimOrEq := - match goal with - | |- (?x = ?y) \/ _ -> _ => - let H := fresh in - (intro H; elim H; clear H; - [intro H; rewrite <- H; clear H | ElimOrEq]) - | |- False -> _ => - let H := fresh in (intro H; contradiction) - end. - -Ltac OrEq := - match goal with - | |- (?x = ?x) \/ _ => left; reflexivity - | |- (?x = ?y) \/ _ => right; OrEq - | |- False => fail - end. - -Ltac NotOrEq := - match goal with - | |- (?x = ?y) \/ _ -> False => - let H := fresh in ( - intro H; elim H; clear H; [intro; discriminate | NotOrEq]) - | |- False -> False => - contradiction - end. - -Lemma index_int_callee_save_pos: - forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. -Qed. - -Lemma index_float_callee_save_pos: - forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. -Qed. - -Lemma index_int_callee_save_pos2: - forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_float_callee_save_pos2: - forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_int_callee_save_inj: - forall r1 r2, - In r1 int_callee_save_regs -> - In r2 int_callee_save_regs -> - r1 <> r2 -> - index_int_callee_save r1 <> index_int_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; - intros; congruence. -Qed. - -Lemma index_float_callee_save_inj: - forall r1 r2, - In r1 float_callee_save_regs -> - In r2 float_callee_save_regs -> - r1 <> r2 -> - index_float_callee_save r1 <> index_float_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_float_callee_save; - intros; congruence. -Qed. - -(** The following lemmas show that - (temporaries, destroyed at call, integer callee-save, float callee-save) - is a partition of the set of machine registers. *) - -Lemma int_float_callee_save_disjoint: - list_disjoint int_callee_save_regs float_callee_save_regs. -Proof. - red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. -Qed. - -Lemma register_classification: - forall r, - In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. -Proof. - destruct r; - try (left; simpl; OrEq); - try (right; left; simpl; OrEq); - try (right; right; simpl; OrEq). -Qed. - - -Lemma int_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r int_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma float_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r float_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma int_callee_save_type: - forall r, In r int_callee_save_regs -> mreg_type r = Tany32. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Lemma float_callee_save_type: - forall r, In r float_callee_save_regs -> mreg_type r = Tany64. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Ltac NoRepet := - match goal with - | |- list_norepet nil => - apply list_norepet_nil - | |- list_norepet (?a :: ?b) => - apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] - end. - -Lemma int_callee_save_norepet: - list_norepet int_callee_save_regs. -Proof. - unfold int_callee_save_regs; NoRepet. -Qed. - -Lemma float_callee_save_norepet: - list_norepet float_callee_save_regs. -Proof. - unfold float_callee_save_regs; NoRepet. -Qed. - -(** * Function calling conventions *) - -(** The functions in this section determine the locations (machine registers - and stack slots) used to communicate arguments and results between the - caller and the callee during function calls. These locations are functions - of the signature of the function and of the call instruction. - Agreement between the caller and the callee on the locations to use - is guaranteed by our dynamic semantics for Cminor and RTL, which demand - that the signature of the call instruction is identical to that of the - called function. - - Calling conventions are largely arbitrary: they must respect the properties - proved in this section (such as no overlapping between the locations - of function arguments), but this leaves much liberty in choosing actual - locations. *) - -(** ** Location of function result *) - -(** The result value of a function is passed back to the caller in - registers [R0] or [F0] or [R0,R1], depending on the type of the - returned value. We treat a function without result as a function - with one integer result. *) - -Definition loc_result (s: signature) : list mreg := - match s.(sig_res) with - | None => R0 :: nil - | Some (Tint | Tany32) => R0 :: nil - | Some (Tfloat | Tsingle | Tany64) => F0 :: nil - | Some Tlong => R1 :: R0 :: nil - end. - -(** The result registers have types compatible with that given in the signature. *) - -Lemma loc_result_type: - forall sig, - subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. -Proof. - intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. -Qed. - -(** The result locations are caller-save registers *) - -Lemma loc_result_caller_save: - forall (s: signature) (r: mreg), - In r (loc_result s) -> In r destroyed_at_call. -Proof. - intros. - assert (r = R0 \/ r = R1 \/ r = F0). - unfold loc_result in H. destruct (sig_res s); [destruct t|idtac]; simpl in H; intuition. - destruct H0 as [A | [A | A]]; subst r; simpl; OrEq. -Qed. - -(** ** Location of function arguments *) - -(** We use the following calling conventions, adapted from the ARM EABI: -- The first 4 integer arguments are passed in registers [R0] to [R3]. -- The first 2 double float arguments are passed in registers [F0] and [F2]. -- The first 4 single float arguments are passed in registers [F0] to [F3]. -- The first 2 long integer arguments are passed in an aligned pair of - two integer registers. -- Each double argument passed in a float register ``consumes'' an aligned pair - of two integer registers. -- Each single argument passed in a float register ``consumes'' an integer - register. -- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively - assigned (1 word for an integer or single argument, 2 words for a double - or a long), starting at word offset 0. - -This convention is not quite that of the ARM EABI, whereas every float -argument are passed in one or two integer registers. Unfortunately, -this does not fit the data model of CompCert. In [PrintAsm.ml] -we insert additional code around function calls and returns that moves -data appropriately. *) - -Definition ireg_param (n: Z) : mreg := - if zeq n (-4) then R0 - else if zeq n (-3) then R1 - else if zeq n (-2) then R2 - else R3. - -Definition freg_param (n: Z) : mreg := - if zeq n (-4) then F0 else F2. - -Definition sreg_param (n: Z) : mreg := - if zeq n (-4) then F0 - else if zeq n (-3) then F1 - else if zeq n (-2) then F2 - else F3. - -Fixpoint loc_arguments_rec (tyl: list typ) (ofs: Z) {struct tyl} : list loc := - match tyl with - | nil => nil - | (Tint | Tany32) as ty :: tys => - (if zle 0 ofs then S Outgoing ofs ty else R (ireg_param ofs)) - :: loc_arguments_rec tys (ofs + 1) - | (Tfloat | Tany64) as ty :: tys => - let ofs := align ofs 2 in - (if zle 0 ofs then S Outgoing ofs ty else R (freg_param ofs)) - :: loc_arguments_rec tys (ofs + 2) - | Tsingle :: tys => - (if zle 0 ofs then S Outgoing ofs Tsingle else R (sreg_param ofs)) - :: loc_arguments_rec tys (ofs + 1) - | Tlong :: tys => - let ofs := align ofs 2 in - (if zle 0 ofs then S Outgoing (ofs + 1) Tint else R (ireg_param (ofs + 1))) - :: (if zle 0 ofs then S Outgoing ofs Tint else R (ireg_param ofs)) - :: loc_arguments_rec tys (ofs + 2) - end. - -(** [loc_arguments s] returns the list of locations where to store arguments - when calling a function with signature [s]. *) - -Definition loc_arguments (s: signature) : list loc := - loc_arguments_rec s.(sig_args) (-4). - -(** [size_arguments s] returns the number of [Outgoing] slots used - to call a function with signature [s]. *) - -Fixpoint size_arguments_rec (tyl: list typ) (ofs: Z) {struct tyl} : Z := - match tyl with - | nil => ofs - | (Tint | Tsingle | Tany32) :: tys => size_arguments_rec tys (ofs + 1) - | (Tfloat | Tlong | Tany64) :: tys => size_arguments_rec tys (align ofs 2 + 2) - end. - -Definition size_arguments (s: signature) : Z := - Zmax 0 (size_arguments_rec s.(sig_args) (-4)). - -(** Argument locations are either non-temporary registers or [Outgoing] - stack slots at nonnegative offsets. *) - -Definition loc_argument_acceptable (l: loc) : Prop := - match l with - | R r => In r destroyed_at_call - | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong - | _ => False - end. - -Remark ireg_param_caller_save: - forall n, In (ireg_param n) destroyed_at_call. -Proof. - unfold ireg_param; intros. - destruct (zeq n (-4)). simpl; auto. - destruct (zeq n (-3)). simpl; auto. - destruct (zeq n (-2)); simpl; auto. -Qed. - -Remark freg_param_caller_save: - forall n, In (freg_param n) destroyed_at_call. -Proof. - unfold freg_param; intros. destruct (zeq n (-4)); simpl; OrEq. -Qed. - -Remark sreg_param_caller_save: - forall n, In (sreg_param n) destroyed_at_call. -Proof. - unfold sreg_param; intros. - destruct (zeq n (-4)). simpl; tauto. - destruct (zeq n (-3)). simpl; tauto. - destruct (zeq n (-2)); simpl; tauto. -Qed. - -Remark loc_arguments_rec_charact: - forall tyl ofs l, - In l (loc_arguments_rec tyl ofs) -> - match l with - | R r => In r destroyed_at_call - | S Outgoing ofs' ty => ofs' >= 0 /\ ofs <= ofs' /\ ty <> Tlong - | S _ _ _ => False - end. -Proof. - induction tyl; simpl loc_arguments_rec; intros. - elim H. - destruct a. -- (* Tint *) - destruct H. - subst l. destruct (zle 0 ofs). - split. omega. split. omega. congruence. - apply ireg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* Tfloat *) - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct H. - subst l. destruct (zle 0 (align ofs 2)). - split. omega. split. auto. congruence. - apply freg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* Tlong *) - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct H. - subst l. destruct (zle 0 (align ofs 2)). - split. omega. split. omega. congruence. - apply ireg_param_caller_save. - destruct H. - subst l. destruct (zle 0 (align ofs 2)). - split. omega. split. omega. congruence. - apply ireg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* Tsingle *) - destruct H. - subst l. destruct (zle 0 ofs). - split. omega. split. omega. congruence. - apply sreg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* Tany32 *) - destruct H. - subst l. destruct (zle 0 ofs). - split. omega. split. omega. congruence. - apply ireg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* Tany64 *) - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct H. - subst l. destruct (zle 0 (align ofs 2)). - split. omega. split. auto. congruence. - apply freg_param_caller_save. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -Qed. - -Lemma loc_arguments_acceptable: - forall (s: signature) (r: loc), - In r (loc_arguments s) -> loc_argument_acceptable r. -Proof. - unfold loc_arguments, loc_argument_acceptable; intros. - generalize (loc_arguments_rec_charact _ _ _ H). - destruct r; auto. - destruct sl; auto. - tauto. -Qed. -Hint Resolve loc_arguments_acceptable: locs. - -(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) - -Remark size_arguments_rec_above: - forall tyl ofs, - ofs <= size_arguments_rec tyl ofs. -Proof. - induction tyl; simpl; intros. - omega. - destruct a. - apply Zle_trans with (ofs + 1); auto; omega. - assert (ofs <= align ofs 2) by (apply align_le; omega). - apply Zle_trans with (align ofs 2 + 2); auto; omega. - assert (ofs <= align ofs 2) by (apply align_le; omega). - apply Zle_trans with (align ofs 2 + 2); auto; omega. - apply Zle_trans with (ofs + 1); auto; omega. - apply Zle_trans with (ofs + 1); auto; omega. - assert (ofs <= align ofs 2) by (apply align_le; omega). - apply Zle_trans with (align ofs 2 + 2); auto; omega. -Qed. - -Lemma size_arguments_above: - forall s, size_arguments s >= 0. -Proof. - intros; unfold size_arguments. apply Zle_ge. apply Zmax1. -Qed. - -Lemma loc_arguments_bounded: - forall (s: signature) (ofs: Z) (ty: typ), - In (S Outgoing ofs ty) (loc_arguments s) -> - ofs + typesize ty <= size_arguments s. -Proof. - intros. - assert (forall tyl ofs0, - 0 <= ofs0 -> - ofs0 <= Zmax 0 (size_arguments_rec tyl ofs0)). - { - intros. generalize (size_arguments_rec_above tyl ofs0). intros. - rewrite Zmax_spec. rewrite zlt_false. auto. omega. - } - assert (forall tyl ofs0, - In (S Outgoing ofs ty) (loc_arguments_rec tyl ofs0) -> - ofs + typesize ty <= Zmax 0 (size_arguments_rec tyl ofs0)). - { - induction tyl; simpl; intros. - elim H1. - destruct a. - - (* Tint *) - destruct H1; auto. destruct (zle 0 ofs0); inv H1. apply H0. omega. - - (* Tfloat *) - destruct H1; auto. destruct (zle 0 (align ofs0 2)); inv H1. apply H0. omega. - - (* Tlong *) - destruct H1. - destruct (zle 0 (align ofs0 2)); inv H1. - eapply Zle_trans. 2: apply H0. simpl typesize; omega. omega. - destruct H1; auto. - destruct (zle 0 (align ofs0 2)); inv H1. - eapply Zle_trans. 2: apply H0. simpl typesize; omega. omega. - - (* Tsingle *) - destruct H1; auto. destruct (zle 0 ofs0); inv H1. apply H0. omega. - - (* Tany32 *) - destruct H1; auto. destruct (zle 0 ofs0); inv H1. apply H0. omega. - - (* Tany64 *) - destruct H1; auto. destruct (zle 0 (align ofs0 2)); inv H1. apply H0. omega. - } - unfold size_arguments. apply H1. auto. -Qed. diff --git a/arm/eabi/Stacklayout.v b/arm/eabi/Stacklayout.v deleted file mode 100644 index 7694dcf..0000000 --- a/arm/eabi/Stacklayout.v +++ /dev/null @@ -1,132 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Machine- and ABI-dependent layout information for activation records. *) - -Require Import Coqlib. -Require Import Bounds. - -(** The general shape of activation records is as follows, - from bottom (lowest offsets) to top: -- Space for outgoing arguments to function calls. -- Local stack slots. -- Saved values of integer callee-save registers used by the function. -- Saved values of float callee-save registers used by the function. -- Saved return address into caller. -- Pointer to activation record of the caller. -- Space for the stack-allocated data declared in Cminor. - -The [frame_env] compilation environment records the positions of -the boundaries between areas in the frame part. -*) - -Definition fe_ofs_arg := 0. - -Record frame_env : Type := mk_frame_env { - fe_size: Z; - fe_ofs_link: Z; - fe_ofs_retaddr: Z; - fe_ofs_local: Z; - fe_ofs_int_callee_save: Z; - fe_num_int_callee_save: Z; - fe_ofs_float_callee_save: Z; - fe_num_float_callee_save: Z; - fe_stack_data: Z -}. - -(** Computation of the frame environment from the bounds of the current - function. *) - -Definition make_env (b: bounds) := - let ol := align (4 * b.(bound_outgoing)) 8 in (* locals *) - let oics := ol + 4 * b.(bound_local) in (* integer callee-saves *) - let oendi := oics + 4 * b.(bound_int_callee_save) in - let ofcs := align oendi 8 in (* float callee-saves *) - let ora := ofcs + 8 * b.(bound_float_callee_save) in (* retaddr *) - let olink := ora + 4 in (* back link *) - let ostkdata := olink + 4 in (* stack data *) - let sz := align (ostkdata + b.(bound_stack_data)) 8 in - mk_frame_env sz olink ora ol - oics b.(bound_int_callee_save) - ofcs b.(bound_float_callee_save) - ostkdata. - -(** Separation property *) - -Remark frame_env_separated: - forall b, - let fe := make_env b in - 0 <= fe_ofs_arg - /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_local) - /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_ofs_int_callee_save) - /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) - /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_ofs_retaddr) - /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_ofs_link) - /\ fe.(fe_ofs_link) + 4 <= fe.(fe_stack_data) - /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_size). -Proof. - intros. - generalize (align_le (4 * bound_outgoing b) 8 (refl_equal)). - generalize (align_le (fe_ofs_int_callee_save fe + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). - generalize (align_le (fe_stack_data fe + b.(bound_stack_data)) 8 (refl_equal)). - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data, fe_ofs_arg. - intros. - generalize (bound_local_pos b); intro; - generalize (bound_int_callee_save_pos b); intro; - generalize (bound_float_callee_save_pos b); intro; - generalize (bound_outgoing_pos b); intro; - generalize (bound_stack_data_pos b); intro. - omega. -Qed. - -(** Alignment property *) - -Remark frame_env_aligned: - forall b, - let fe := make_env b in - (4 | fe.(fe_ofs_link)) - /\ (8 | fe.(fe_ofs_local)) - /\ (4 | fe.(fe_ofs_int_callee_save)) - /\ (8 | fe.(fe_ofs_float_callee_save)) - /\ (4 | fe.(fe_ofs_retaddr)) - /\ (8 | fe.(fe_stack_data)) - /\ (8 | fe.(fe_size)). -Proof. - intros. - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data. - set (x1 := 4 * bound_outgoing b). - assert (4 | x1). unfold x1; exists (bound_outgoing b); ring. - set (x2 := align x1 8). - assert (8 | x2). apply align_divides. omega. - set (x3 := x2 + 4 * bound_local b). - assert (4 | x3). apply Zdivide_plus_r. apply Zdivides_trans with 8; auto. exists 2; auto. - exists (bound_local b); ring. - set (x4 := align (x3 + 4 * bound_int_callee_save b) 8). - assert (8 | x4). apply align_divides. omega. - set (x5 := x4 + 8 * bound_float_callee_save b). - assert (8 | x5). apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. - assert (4 | x5). apply Zdivides_trans with 8; auto. exists 2; auto. - set (x6 := x5 + 4). - assert (4 | x6). apply Zdivide_plus_r; auto. exists 1; auto. - set (x7 := x6 + 4). - assert (8 | x7). unfold x7, x6. replace (x5 + 4 + 4) with (x5 + 8) by omega. - apply Zdivide_plus_r; auto. exists 1; auto. - set (x8 := align (x7 + bound_stack_data b) 8). - assert (8 | x8). apply align_divides. omega. - tauto. -Qed. diff --git a/arm/extractionMachdep.v b/arm/extractionMachdep.v index f6e17ba..0c9b705 100644 --- a/arm/extractionMachdep.v +++ b/arm/extractionMachdep.v @@ -16,3 +16,11 @@ Extract Constant Asm.ireg_eq => "fun (x: ireg) (y: ireg) -> x = y". Extract Constant Asm.freg_eq => "fun (x: freg) (y: freg) -> x = y". Extract Constant Asm.preg_eq => "fun (x: preg) (y: preg) -> x = y". + +(* Choice of calling conventions *) +Extract Constant Archi.abi => + "begin match Configuration.variant with + | ""eabi"" -> Softfloat + | ""hardfloat"" -> Hardfloat + | _ -> assert false + end". diff --git a/arm/hardfloat/Conventions1.v b/arm/hardfloat/Conventions1.v deleted file mode 100644 index 40a761c..0000000 --- a/arm/hardfloat/Conventions1.v +++ /dev/null @@ -1,733 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Function calling conventions and other conventions regarding the use of - machine registers and stack slots. *) - -Require Import Coqlib. -Require Import AST. -Require Import Events. -Require Import Locations. - -(** * Classification of machine registers *) - -(** Machine registers (type [mreg] in module [Locations]) are divided in - the following groups: -- Temporaries used for spilling, reloading, and parallel move operations. -- Allocatable registers, that can be assigned to RTL pseudo-registers. - These are further divided into: --- Callee-save registers, whose value is preserved across a function call. --- Caller-save registers that can be modified during a function call. - - We follow the PowerPC application binary interface (ABI) in our choice - of callee- and caller-save registers. -*) - -Definition int_caller_save_regs := - R0 :: R1 :: R2 :: R3 :: R12 :: nil. - -Definition float_caller_save_regs := - F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: nil. - -Definition int_callee_save_regs := - R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: R11 :: nil. - -Definition float_callee_save_regs := - F8 :: F9 :: F10 :: F11 :: F12 :: F13 :: F14 :: F15 :: nil. - -Definition destroyed_at_call := - int_caller_save_regs ++ float_caller_save_regs. - -Definition dummy_int_reg := R0. (**r Used in [Coloring]. *) -Definition dummy_float_reg := F0. (**r Used in [Coloring]. *) - -(** The [index_int_callee_save] and [index_float_callee_save] associate - a unique positive integer to callee-save registers. This integer is - used in [Stacking] to determine where to save these registers in - the activation record if they are used by the current function. *) - -Definition index_int_callee_save (r: mreg) := - match r with - | R4 => 0 | R5 => 1 | R6 => 2 | R7 => 3 - | R8 => 4 | R9 => 5 | R10 => 6 | R11 => 7 - | _ => -1 - end. - -Definition index_float_callee_save (r: mreg) := - match r with - | F8 => 0 | F9 => 1 | F10 => 2 | F11 => 3 - | F12 => 4 | F13 => 5 | F14 => 6 | F15 => 7 - | _ => -1 - end. - -Ltac ElimOrEq := - match goal with - | |- (?x = ?y) \/ _ -> _ => - let H := fresh in - (intro H; elim H; clear H; - [intro H; rewrite <- H; clear H | ElimOrEq]) - | |- False -> _ => - let H := fresh in (intro H; contradiction) - end. - -Ltac OrEq := - match goal with - | |- (?x = ?x) \/ _ => left; reflexivity - | |- (?x = ?y) \/ _ => right; OrEq - | |- False => fail - end. - -Ltac NotOrEq := - match goal with - | |- (?x = ?y) \/ _ -> False => - let H := fresh in ( - intro H; elim H; clear H; [intro; discriminate | NotOrEq]) - | |- False -> False => - contradiction - end. - -Lemma index_int_callee_save_pos: - forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. -Qed. - -Lemma index_float_callee_save_pos: - forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. -Qed. - -Lemma index_int_callee_save_pos2: - forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_float_callee_save_pos2: - forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_int_callee_save_inj: - forall r1 r2, - In r1 int_callee_save_regs -> - In r2 int_callee_save_regs -> - r1 <> r2 -> - index_int_callee_save r1 <> index_int_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; - intros; congruence. -Qed. - -Lemma index_float_callee_save_inj: - forall r1 r2, - In r1 float_callee_save_regs -> - In r2 float_callee_save_regs -> - r1 <> r2 -> - index_float_callee_save r1 <> index_float_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_float_callee_save; - intros; congruence. -Qed. - -(** The following lemmas show that - (temporaries, destroyed at call, integer callee-save, float callee-save) - is a partition of the set of machine registers. *) - -Lemma int_float_callee_save_disjoint: - list_disjoint int_callee_save_regs float_callee_save_regs. -Proof. - red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. -Qed. - -Lemma register_classification: - forall r, - In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. -Proof. - destruct r; - try (left; simpl; OrEq); - try (right; left; simpl; OrEq); - try (right; right; simpl; OrEq). -Qed. - - -Lemma int_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r int_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma float_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r float_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma int_callee_save_type: - forall r, In r int_callee_save_regs -> mreg_type r = Tany32. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Lemma float_callee_save_type: - forall r, In r float_callee_save_regs -> mreg_type r = Tany64. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Ltac NoRepet := - match goal with - | |- list_norepet nil => - apply list_norepet_nil - | |- list_norepet (?a :: ?b) => - apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] - end. - -Lemma int_callee_save_norepet: - list_norepet int_callee_save_regs. -Proof. - unfold int_callee_save_regs; NoRepet. -Qed. - -Lemma float_callee_save_norepet: - list_norepet float_callee_save_regs. -Proof. - unfold float_callee_save_regs; NoRepet. -Qed. - -(** * Function calling conventions *) - -(** The functions in this section determine the locations (machine registers - and stack slots) used to communicate arguments and results between the - caller and the callee during function calls. These locations are functions - of the signature of the function and of the call instruction. - Agreement between the caller and the callee on the locations to use - is guaranteed by our dynamic semantics for Cminor and RTL, which demand - that the signature of the call instruction is identical to that of the - called function. - - Calling conventions are largely arbitrary: they must respect the properties - proved in this section (such as no overlapping between the locations - of function arguments), but this leaves much liberty in choosing actual - locations. *) - -(** ** Location of function result *) - -(** The result value of a function is passed back to the caller in - registers [R0] or [F0] or [R0,R1], depending on the type of the - returned value. We treat a function without result as a function - with one integer result. *) - -Definition loc_result (s: signature) : list mreg := - match s.(sig_res) with - | None => R0 :: nil - | Some (Tint | Tany32) => R0 :: nil - | Some (Tfloat | Tsingle | Tany64) => F0 :: nil - | Some Tlong => R1 :: R0 :: nil - end. - -(** The result registers have types compatible with that given in the signature. *) - -Lemma loc_result_type: - forall sig, - subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. -Proof. - intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. -Qed. - -(** The result locations are caller-save registers *) - -Lemma loc_result_caller_save: - forall (s: signature) (r: mreg), - In r (loc_result s) -> In r destroyed_at_call. -Proof. - intros. - assert (r = R0 \/ r = R1 \/ r = F0). - unfold loc_result in H. destruct (sig_res s); [destruct t|idtac]; simpl in H; intuition. - destruct H0 as [A | [A | A]]; subst r; simpl; OrEq. -Qed. - -(** ** Location of function arguments *) - -(** We use the following calling conventions, adapted from the ARM EABI-HF: -- The first 4 integer arguments are passed in registers [R0] to [R3]. -- The first 2 long integer arguments are passed in an aligned pair of - two integer registers. -- The first 8 single- and double-precision float arguments are passed - in registers [F0...F7] -- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively - assigned (1 word for an integer or single argument, 2 words for a float - or a long), starting at word offset 0. - -This convention is not quite that of the ARM EABI-HF, whereas single float -arguments are passed in 32-bit float registers. Unfortunately, -this does not fit the data model of CompCert. In [PrintAsm.ml] -we insert additional code around function calls that moves -data appropriately. *) - -Definition int_param_regs := - R0 :: R1 :: R2 :: R3 :: nil. - -Definition float_param_regs := - F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: nil. - -Definition ireg_param (n: Z) : mreg := - match list_nth_z int_param_regs n with Some r => r | None => R0 end. - -Definition freg_param (n: Z) : mreg := - match list_nth_z float_param_regs n with Some r => r | None => F0 end. - -Fixpoint loc_arguments_rec - (tyl: list typ) (ir fr ofs: Z) {struct tyl} : list loc := - match tyl with - | nil => nil - | (Tint | Tany32) as ty :: tys => - if zlt ir 4 - then R (ireg_param ir) :: loc_arguments_rec tys (ir + 1) fr ofs - else S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 1) - | (Tfloat | Tany64) as ty :: tys => - if zlt fr 8 - then R (freg_param fr) :: loc_arguments_rec tys ir (fr + 1) ofs - else let ofs := align ofs 2 in - S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 2) - | Tsingle :: tys => - if zlt fr 8 - then R (freg_param fr) :: loc_arguments_rec tys ir (fr + 1) ofs - else S Outgoing ofs Tsingle :: loc_arguments_rec tys ir fr (ofs + 1) - | Tlong :: tys => - let ir := align ir 2 in - if zlt ir 4 - then R (ireg_param (ir + 1)) :: R (ireg_param ir) :: loc_arguments_rec tys (ir + 2) fr ofs - else let ofs := align ofs 2 in - S Outgoing (ofs + 1) Tint :: S Outgoing ofs Tint :: loc_arguments_rec tys ir fr (ofs + 2) - end. - -(** For variable-argument functions, we use the default ARM EABI (not HF) - calling conventions: -- The first 4 integer arguments are passed in registers [R0] to [R3]. -- The first 2 long integer arguments are passed in an aligned pair of - two integer registers. -- The first 2 double-precision float arguments are passed in [F0] or [F2] -- The first 4 single-precision float arguments are passed in [F0...F3] -- Integer arguments and float arguments are kept in sync so that - they can all be mapped back to [R0...R3] in [PrintAsm.ml]. -- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively - assigned (1 word for an integer or single argument, 2 words for a float - or a long), starting at word offset 0. -*) - -Fixpoint loc_arguments_vararg - (tyl: list typ) (ofs: Z) {struct tyl} : list loc := - match tyl with - | nil => nil - | (Tint|Tany32) as ty :: tys => - (if zlt ofs 0 then R (ireg_param (ofs + 4)) else S Outgoing ofs ty) - :: loc_arguments_vararg tys (ofs + 1) - | (Tfloat|Tany64) as ty :: tys => - let ofs := align ofs 2 in - (if zlt ofs 0 then R (freg_param (ofs + 4)) else S Outgoing ofs ty) - :: loc_arguments_vararg tys (ofs + 2) - | Tsingle :: tys => - (if zlt ofs 0 then R (freg_param (ofs + 4)) else S Outgoing ofs Tsingle) - :: loc_arguments_vararg tys (ofs + 1) - | Tlong :: tys => - let ofs := align ofs 2 in - (if zlt ofs 0 then R (ireg_param (ofs+1+4)) else S Outgoing (ofs+1) Tint) - :: (if zlt ofs 0 then R (ireg_param (ofs+4)) else S Outgoing ofs Tint) - :: loc_arguments_vararg tys (ofs + 2) - end. - -(** [loc_arguments s] returns the list of locations where to store arguments - when calling a function with signature [s]. *) - -Definition loc_arguments (s: signature) : list loc := - if s.(sig_cc).(cc_vararg) - then loc_arguments_vararg s.(sig_args) (-4) - else loc_arguments_rec s.(sig_args) 0 0 0. - -(** [size_arguments s] returns the number of [Outgoing] slots used - to call a function with signature [s]. *) - -Fixpoint size_arguments_rec (tyl: list typ) (ir fr ofs: Z) {struct tyl} : Z := - match tyl with - | nil => ofs - | (Tint|Tany32) :: tys => - if zlt ir 4 - then size_arguments_rec tys (ir + 1) fr ofs - else size_arguments_rec tys ir fr (ofs + 1) - | (Tfloat|Tany64) :: tys => - if zlt fr 8 - then size_arguments_rec tys ir (fr + 1) ofs - else size_arguments_rec tys ir fr (align ofs 2 + 2) - | Tsingle :: tys => - if zlt fr 8 - then size_arguments_rec tys ir (fr + 1) ofs - else size_arguments_rec tys ir fr (ofs + 1) - | Tlong :: tys => - let ir := align ir 2 in - if zlt ir 4 - then size_arguments_rec tys (ir + 2) fr ofs - else size_arguments_rec tys ir fr (align ofs 2 + 2) - end. - -Fixpoint size_arguments_vararg (tyl: list typ) (ofs: Z) {struct tyl} : Z := - match tyl with - | nil => Zmax 0 ofs - | (Tint | Tsingle | Tany32) :: tys => size_arguments_vararg tys (ofs + 1) - | (Tfloat | Tlong | Tany64) :: tys => size_arguments_vararg tys (align ofs 2 + 2) - end. - -Definition size_arguments (s: signature) : Z := - if s.(sig_cc).(cc_vararg) - then size_arguments_vararg s.(sig_args) (-4) - else size_arguments_rec s.(sig_args) 0 0 0. - -(** Argument locations are either non-temporary registers or [Outgoing] - stack slots at nonnegative offsets. *) - -Definition loc_argument_acceptable (l: loc) : Prop := - match l with - | R r => In r destroyed_at_call - | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong - | _ => False - end. - -Remark ireg_param_in_params: forall n, In (ireg_param n) int_param_regs. -Proof. - unfold ireg_param; intros. - destruct (list_nth_z int_param_regs n) as [r|] eqn:NTH. - eapply list_nth_z_in; eauto. - simpl; auto. -Qed. - -Remark freg_param_in_params: forall n, In (freg_param n) float_param_regs. -Proof. - unfold freg_param; intros. - destruct (list_nth_z float_param_regs n) as [r|] eqn:NTH. - eapply list_nth_z_in; eauto. - simpl; auto. -Qed. - -Remark loc_arguments_rec_charact: - forall tyl ir fr ofs l, - In l (loc_arguments_rec tyl ir fr ofs) -> - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong - | S _ _ _ => False - end. -Proof. - assert (INCR: forall l ofs1 ofs2, - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= ofs2 /\ ty <> Tlong - | S _ _ _ => False - end -> - ofs1 <= ofs2 -> - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= ofs1 /\ ty <> Tlong - | S _ _ _ => False - end). - { - intros. destruct l; auto. destruct sl; auto. intuition omega. - } - induction tyl; simpl loc_arguments_rec; intros. - elim H. - destruct a. -- (* int *) - destruct (zlt ir 4); destruct H. - subst. left; apply ireg_param_in_params. - eapply IHtyl; eauto. - subst. split; [omega | congruence]. - eapply INCR. eapply IHtyl; eauto. omega. -- (* float *) - destruct (zlt fr 8); destruct H. - subst. right; apply freg_param_in_params. - eapply IHtyl; eauto. - subst. split. apply Zle_ge. apply align_le. omega. congruence. - eapply INCR. eapply IHtyl; eauto. - apply Zle_trans with (align ofs 2). apply align_le; omega. omega. -- (* long *) - set (ir' := align ir 2) in *. - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct (zlt ir' 4). - destruct H. subst l; left; apply ireg_param_in_params. - destruct H. subst l; left; apply ireg_param_in_params. - eapply IHtyl; eauto. - destruct H. subst l; split; [ omega | congruence ]. - destruct H. subst l; split; [ omega | congruence ]. - eapply INCR. eapply IHtyl; eauto. omega. -- (* single *) - destruct (zlt fr 8); destruct H. - subst. right; apply freg_param_in_params. - eapply IHtyl; eauto. - subst. split; [omega | congruence]. - eapply INCR. eapply IHtyl; eauto. omega. -- (* any32 *) - destruct (zlt ir 4); destruct H. - subst. left; apply ireg_param_in_params. - eapply IHtyl; eauto. - subst. split; [omega | congruence]. - eapply INCR. eapply IHtyl; eauto. omega. -- (* any64 *) - destruct (zlt fr 8); destruct H. - subst. right; apply freg_param_in_params. - eapply IHtyl; eauto. - subst. split. apply Zle_ge. apply align_le. omega. congruence. - eapply INCR. eapply IHtyl; eauto. - apply Zle_trans with (align ofs 2). apply align_le; omega. omega. -Qed. - -Remark loc_arguments_vararg_charact: - forall tyl ofs l, - In l (loc_arguments_vararg tyl ofs) -> - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs /\ ty <> Tlong - | S _ _ _ => False - end. -Proof. - assert (INCR: forall l ofs1 ofs2, - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs2 /\ ty <> Tlong - | S _ _ _ => False - end -> - ofs1 <= ofs2 -> - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= Zmax 0 ofs1 /\ ty <> Tlong - | S _ _ _ => False - end). - { - intros. destruct l; auto. destruct sl; auto. intuition xomega. - } - induction tyl; simpl loc_arguments_vararg; intros. - elim H. - destruct a. -- (* int *) - destruct H. - destruct (zlt ofs 0); subst l. - left; apply ireg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -- (* float *) - set (ofs' := align ofs 2) in *. - assert (ofs <= ofs') by (apply align_le; omega). - destruct H. - destruct (zlt ofs' 0); subst l. - right; apply freg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -- (* long *) - set (ofs' := align ofs 2) in *. - assert (ofs <= ofs') by (apply align_le; omega). - destruct H. - destruct (zlt ofs' 0); subst l. - left; apply ireg_param_in_params. - split. xomega. congruence. - destruct H. - destruct (zlt ofs' 0); subst l. - left; apply ireg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -- (* single *) - destruct H. - destruct (zlt ofs 0); subst l. - right; apply freg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -- (* any32 *) - destruct H. - destruct (zlt ofs 0); subst l. - left; apply ireg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -- (* any64 *) - set (ofs' := align ofs 2) in *. - assert (ofs <= ofs') by (apply align_le; omega). - destruct H. - destruct (zlt ofs' 0); subst l. - right; apply freg_param_in_params. - split. xomega. congruence. - eapply INCR. eapply IHtyl; eauto. omega. -Qed. - -Lemma loc_arguments_acceptable: - forall (s: signature) (l: loc), - In l (loc_arguments s) -> loc_argument_acceptable l. -Proof. - unfold loc_arguments; intros. - assert (forall r, In r int_param_regs \/ In r float_param_regs -> In r destroyed_at_call). - { - intros. elim H0; simpl; ElimOrEq; OrEq. - } - red. destruct (cc_vararg (sig_cc s)). - exploit loc_arguments_vararg_charact; eauto. - destruct l; auto. - exploit loc_arguments_rec_charact; eauto. - destruct l; auto. -Qed. - -Hint Resolve loc_arguments_acceptable: locs. - -(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) - -Remark size_arguments_rec_above: - forall tyl ir fr ofs0, - ofs0 <= size_arguments_rec tyl ir fr ofs0. -Proof. - induction tyl; simpl; intros. - omega. - destruct a. - destruct (zlt ir 4); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. - destruct (zlt fr 8); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - set (ir' := align ir 2). - destruct (zlt ir' 4); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - destruct (zlt fr 8); eauto. - apply Zle_trans with (ofs0 + 1); eauto. omega. - destruct (zlt ir 4); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. - destruct (zlt fr 8); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. -Qed. - -Remark size_arguments_vararg_above: - forall tyl ofs0, - Zmax 0 ofs0 <= size_arguments_vararg tyl ofs0. -Proof. - induction tyl; simpl; intros. - omega. - destruct a; (eapply Zle_trans; [idtac|eauto]). - xomega. - assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. - assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. - xomega. - xomega. - assert (ofs0 <= align ofs0 2) by (apply align_le; omega). xomega. -Qed. - -Lemma size_arguments_above: - forall s, size_arguments s >= 0. -Proof. - intros; unfold size_arguments. destruct (cc_vararg (sig_cc s)). - apply Zle_ge. change 0 with (Zmax 0 (-4)). apply size_arguments_vararg_above. - apply Zle_ge. apply size_arguments_rec_above. -Qed. - -Lemma loc_arguments_rec_bounded: - forall ofs ty tyl ir fr ofs0, - In (S Outgoing ofs ty) (loc_arguments_rec tyl ir fr ofs0) -> - ofs + typesize ty <= size_arguments_rec tyl ir fr ofs0. -Proof. - induction tyl; simpl; intros. - elim H. - destruct a. -- (* int *) - destruct (zlt ir 4); destruct H. - discriminate. - eauto. - inv H. apply size_arguments_rec_above. - eauto. -- (* float *) - destruct (zlt fr 8); destruct H. - discriminate. - eauto. - inv H. apply size_arguments_rec_above. - eauto. -- (* long *) - destruct (zlt (align ir 2) 4). - destruct H. discriminate. destruct H. discriminate. eauto. - destruct H. inv H. - rewrite <- Zplus_assoc. simpl. apply size_arguments_rec_above. - destruct H. inv H. - eapply Zle_trans. 2: apply size_arguments_rec_above. simpl; omega. - eauto. -- (* float *) - destruct (zlt fr 8); destruct H. - discriminate. - eauto. - inv H. apply size_arguments_rec_above. - eauto. -- (* any32 *) - destruct (zlt ir 4); destruct H. - discriminate. - eauto. - inv H. apply size_arguments_rec_above. - eauto. -- (* any64 *) - destruct (zlt fr 8); destruct H. - discriminate. - eauto. - inv H. apply size_arguments_rec_above. - eauto. -Qed. - -Lemma loc_arguments_vararg_bounded: - forall ofs ty tyl ofs0, - In (S Outgoing ofs ty) (loc_arguments_vararg tyl ofs0) -> - Zmax 0 (ofs + typesize ty) <= size_arguments_vararg tyl ofs0. -Proof. - induction tyl; simpl; intros. - elim H. - destruct a. -- (* int *) - destruct H. - destruct (zlt ofs0 0); inv H. apply size_arguments_vararg_above. - eauto. -- (* float *) - destruct H. - destruct (zlt (align ofs0 2) 0); inv H. apply size_arguments_vararg_above. - eauto. -- (* long *) - destruct H. - destruct (zlt (align ofs0 2) 0); inv H. - rewrite <- Zplus_assoc. simpl. apply size_arguments_vararg_above. - destruct H. - destruct (zlt (align ofs0 2) 0); inv H. - eapply Zle_trans. 2: apply size_arguments_vararg_above. simpl; xomega. - eauto. -- (* float *) - destruct H. - destruct (zlt ofs0 0); inv H. apply size_arguments_vararg_above. - eauto. -- (* any32 *) - destruct H. - destruct (zlt ofs0 0); inv H. apply size_arguments_vararg_above. - eauto. -- (* any64 *) - destruct H. - destruct (zlt (align ofs0 2) 0); inv H. apply size_arguments_vararg_above. - eauto. -Qed. - -Lemma loc_arguments_bounded: - forall (s: signature) (ofs: Z) (ty: typ), - In (S Outgoing ofs ty) (loc_arguments s) -> - ofs + typesize ty <= size_arguments s. -Proof. - unfold loc_arguments, size_arguments; intros. - destruct (cc_vararg (sig_cc s)). - eapply Zle_trans. 2: eapply loc_arguments_vararg_bounded; eauto. xomega. - eapply loc_arguments_rec_bounded; eauto. -Qed. diff --git a/arm/hardfloat/Stacklayout.v b/arm/hardfloat/Stacklayout.v deleted file mode 100644 index 7694dcf..0000000 --- a/arm/hardfloat/Stacklayout.v +++ /dev/null @@ -1,132 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Machine- and ABI-dependent layout information for activation records. *) - -Require Import Coqlib. -Require Import Bounds. - -(** The general shape of activation records is as follows, - from bottom (lowest offsets) to top: -- Space for outgoing arguments to function calls. -- Local stack slots. -- Saved values of integer callee-save registers used by the function. -- Saved values of float callee-save registers used by the function. -- Saved return address into caller. -- Pointer to activation record of the caller. -- Space for the stack-allocated data declared in Cminor. - -The [frame_env] compilation environment records the positions of -the boundaries between areas in the frame part. -*) - -Definition fe_ofs_arg := 0. - -Record frame_env : Type := mk_frame_env { - fe_size: Z; - fe_ofs_link: Z; - fe_ofs_retaddr: Z; - fe_ofs_local: Z; - fe_ofs_int_callee_save: Z; - fe_num_int_callee_save: Z; - fe_ofs_float_callee_save: Z; - fe_num_float_callee_save: Z; - fe_stack_data: Z -}. - -(** Computation of the frame environment from the bounds of the current - function. *) - -Definition make_env (b: bounds) := - let ol := align (4 * b.(bound_outgoing)) 8 in (* locals *) - let oics := ol + 4 * b.(bound_local) in (* integer callee-saves *) - let oendi := oics + 4 * b.(bound_int_callee_save) in - let ofcs := align oendi 8 in (* float callee-saves *) - let ora := ofcs + 8 * b.(bound_float_callee_save) in (* retaddr *) - let olink := ora + 4 in (* back link *) - let ostkdata := olink + 4 in (* stack data *) - let sz := align (ostkdata + b.(bound_stack_data)) 8 in - mk_frame_env sz olink ora ol - oics b.(bound_int_callee_save) - ofcs b.(bound_float_callee_save) - ostkdata. - -(** Separation property *) - -Remark frame_env_separated: - forall b, - let fe := make_env b in - 0 <= fe_ofs_arg - /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_local) - /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_ofs_int_callee_save) - /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) - /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_ofs_retaddr) - /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_ofs_link) - /\ fe.(fe_ofs_link) + 4 <= fe.(fe_stack_data) - /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_size). -Proof. - intros. - generalize (align_le (4 * bound_outgoing b) 8 (refl_equal)). - generalize (align_le (fe_ofs_int_callee_save fe + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). - generalize (align_le (fe_stack_data fe + b.(bound_stack_data)) 8 (refl_equal)). - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data, fe_ofs_arg. - intros. - generalize (bound_local_pos b); intro; - generalize (bound_int_callee_save_pos b); intro; - generalize (bound_float_callee_save_pos b); intro; - generalize (bound_outgoing_pos b); intro; - generalize (bound_stack_data_pos b); intro. - omega. -Qed. - -(** Alignment property *) - -Remark frame_env_aligned: - forall b, - let fe := make_env b in - (4 | fe.(fe_ofs_link)) - /\ (8 | fe.(fe_ofs_local)) - /\ (4 | fe.(fe_ofs_int_callee_save)) - /\ (8 | fe.(fe_ofs_float_callee_save)) - /\ (4 | fe.(fe_ofs_retaddr)) - /\ (8 | fe.(fe_stack_data)) - /\ (8 | fe.(fe_size)). -Proof. - intros. - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data. - set (x1 := 4 * bound_outgoing b). - assert (4 | x1). unfold x1; exists (bound_outgoing b); ring. - set (x2 := align x1 8). - assert (8 | x2). apply align_divides. omega. - set (x3 := x2 + 4 * bound_local b). - assert (4 | x3). apply Zdivide_plus_r. apply Zdivides_trans with 8; auto. exists 2; auto. - exists (bound_local b); ring. - set (x4 := align (x3 + 4 * bound_int_callee_save b) 8). - assert (8 | x4). apply align_divides. omega. - set (x5 := x4 + 8 * bound_float_callee_save b). - assert (8 | x5). apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. - assert (4 | x5). apply Zdivides_trans with 8; auto. exists 2; auto. - set (x6 := x5 + 4). - assert (4 | x6). apply Zdivide_plus_r; auto. exists 1; auto. - set (x7 := x6 + 4). - assert (8 | x7). unfold x7, x6. replace (x5 + 4 + 4) with (x5 + 8) by omega. - apply Zdivide_plus_r; auto. exists 1; auto. - set (x8 := align (x7 + bound_stack_data b) 8). - assert (8 | x8). apply align_divides. omega. - tauto. -Qed. diff --git a/backend/Stackingproof.v b/backend/Stackingproof.v index 28b155a..c25721b 100644 --- a/backend/Stackingproof.v +++ b/backend/Stackingproof.v @@ -2850,7 +2850,7 @@ Proof. intros. change (Mem.valid_block m0 b0). eapply Genv.find_symbol_not_fresh; eauto. intros. change (Mem.valid_block m0 b0). eapply Genv.find_funct_ptr_not_fresh; eauto. intros. change (Mem.valid_block m0 b0). eapply Genv.find_var_info_not_fresh; eauto. - rewrite H3. red; intros. contradiction. + rewrite H3. red; intros. rewrite loc_arguments_main in H. contradiction. unfold Locmap.init. red; intros; auto. unfold parent_locset. red; auto. Qed. diff --git a/ia32/Conventions1.v b/ia32/Conventions1.v new file mode 100644 index 0000000..ef9ab6b --- /dev/null +++ b/ia32/Conventions1.v @@ -0,0 +1,371 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Function calling conventions and other conventions regarding the use of + machine registers and stack slots. *) + +Require Import Coqlib. +Require Import AST. +Require Import Events. +Require Import Locations. + +(** * Classification of machine registers *) + +(** Machine registers (type [mreg] in module [Locations]) are divided in + the following groups: +- Callee-save registers, whose value is preserved across a function call. +- Caller-save registers that can be modified during a function call. + + We follow the x86-32 application binary interface (ABI) in our choice + of callee- and caller-save registers. +*) + +Definition int_caller_save_regs := AX :: CX :: DX :: nil. + +Definition float_caller_save_regs := X0 :: X1 :: X2 :: X3 :: X4 :: X5 :: X6 :: X7 :: nil. + +Definition int_callee_save_regs := BX :: SI :: DI :: BP :: nil. + +Definition float_callee_save_regs : list mreg := nil. + +Definition destroyed_at_call := + FP0 :: int_caller_save_regs ++ float_caller_save_regs. + +Definition dummy_int_reg := AX. (**r Used in [Regalloc]. *) +Definition dummy_float_reg := X0. (**r Used in [Regalloc]. *) + +(** The [index_int_callee_save] and [index_float_callee_save] associate + a unique positive integer to callee-save registers. This integer is + used in [Stacking] to determine where to save these registers in + the activation record if they are used by the current function. *) + +Definition index_int_callee_save (r: mreg) := + match r with + | BX => 0 | SI => 1 | DI => 2 | BP => 3 | _ => -1 + end. + +Definition index_float_callee_save (r: mreg) := -1. + +Ltac ElimOrEq := + match goal with + | |- (?x = ?y) \/ _ -> _ => + let H := fresh in + (intro H; elim H; clear H; + [intro H; rewrite <- H; clear H | ElimOrEq]) + | |- False -> _ => + let H := fresh in (intro H; contradiction) + end. + +Ltac OrEq := + match goal with + | |- (?x = ?x) \/ _ => left; reflexivity + | |- (?x = ?y) \/ _ => right; OrEq + | |- False => fail + end. + +Ltac NotOrEq := + match goal with + | |- (?x = ?y) \/ _ -> False => + let H := fresh in ( + intro H; elim H; clear H; [intro; discriminate | NotOrEq]) + | |- False -> False => + contradiction + end. + +Lemma index_int_callee_save_pos: + forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. +Qed. + +Lemma index_float_callee_save_pos: + forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. +Qed. + +Lemma index_int_callee_save_pos2: + forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. +Proof. + destruct r; simpl; intro; omegaContradiction || OrEq. +Qed. + +Lemma index_float_callee_save_pos2: + forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. +Proof. + unfold index_float_callee_save; intros. omegaContradiction. +Qed. + +Lemma index_int_callee_save_inj: + forall r1 r2, + In r1 int_callee_save_regs -> + In r2 int_callee_save_regs -> + r1 <> r2 -> + index_int_callee_save r1 <> index_int_callee_save r2. +Proof. + intros r1 r2. + simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; + intros; congruence. +Qed. + +Lemma index_float_callee_save_inj: + forall r1 r2, + In r1 float_callee_save_regs -> + In r2 float_callee_save_regs -> + r1 <> r2 -> + index_float_callee_save r1 <> index_float_callee_save r2. +Proof. + simpl; intros. contradiction. +Qed. + +(** The following lemmas show that + (destroyed at call, integer callee-save, float callee-save) + is a partition of the set of machine registers. *) + +Lemma int_float_callee_save_disjoint: + list_disjoint int_callee_save_regs float_callee_save_regs. +Proof. + red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. +Qed. + +Lemma register_classification: + forall r, + In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. +Proof. + destruct r; + try (left; simpl; OrEq); + try (right; left; simpl; OrEq); + try (right; right; simpl; OrEq). +Qed. + +Lemma int_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r int_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma float_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r float_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma int_callee_save_type: + forall r, In r int_callee_save_regs -> mreg_type r = Tany32. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Lemma float_callee_save_type: + forall r, In r float_callee_save_regs -> mreg_type r = Tany64. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Ltac NoRepet := + match goal with + | |- list_norepet nil => + apply list_norepet_nil + | |- list_norepet (?a :: ?b) => + apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] + end. + +Lemma int_callee_save_norepet: + list_norepet int_callee_save_regs. +Proof. + unfold int_callee_save_regs; NoRepet. +Qed. + +Lemma float_callee_save_norepet: + list_norepet float_callee_save_regs. +Proof. + unfold float_callee_save_regs; NoRepet. +Qed. + +(** * Function calling conventions *) + +(** The functions in this section determine the locations (machine registers + and stack slots) used to communicate arguments and results between the + caller and the callee during function calls. These locations are functions + of the signature of the function and of the call instruction. + Agreement between the caller and the callee on the locations to use + is guaranteed by our dynamic semantics for Cminor and RTL, which demand + that the signature of the call instruction is identical to that of the + called function. + + Calling conventions are largely arbitrary: they must respect the properties + proved in this section (such as no overlapping between the locations + of function arguments), but this leaves much liberty in choosing actual + locations. To ensure binary interoperability of code generated by our + compiler with libraries compiled by another compiler, we + implement the standard x86 conventions. *) + +(** ** Location of function result *) + +(** The result value of a function is passed back to the caller in + registers [AX] or [FP0], depending on the type of the returned value. + We treat a function without result as a function with one integer result. *) + +Definition loc_result (s: signature) : list mreg := + match s.(sig_res) with + | None => AX :: nil + | Some (Tint | Tany32) => AX :: nil + | Some (Tfloat | Tsingle) => FP0 :: nil + | Some Tany64 => X0 :: nil + | Some Tlong => DX :: AX :: nil + end. + +(** The result registers have types compatible with that given in the signature. *) + +Lemma loc_result_type: + forall sig, + subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. +Proof. + intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. +Qed. + +(** The result locations are caller-save registers *) + +Lemma loc_result_caller_save: + forall (s: signature) (r: mreg), + In r (loc_result s) -> In r destroyed_at_call. +Proof. + intros. + assert (r = AX \/ r = DX \/ r = FP0 \/ r = X0). + unfold loc_result in H. destruct (sig_res s) as [[]|]; simpl in H; intuition. + destruct H0 as [A | [A | [A | A]]]; subst r; simpl; OrEq. +Qed. + +(** ** Location of function arguments *) + +(** All arguments are passed on stack. (Snif.) *) + +Fixpoint loc_arguments_rec + (tyl: list typ) (ofs: Z) {struct tyl} : list loc := + match tyl with + | nil => nil + | Tint :: tys => S Outgoing ofs Tint :: loc_arguments_rec tys (ofs + 1) + | Tfloat :: tys => S Outgoing ofs Tfloat :: loc_arguments_rec tys (ofs + 2) + | Tsingle :: tys => S Outgoing ofs Tsingle :: loc_arguments_rec tys (ofs + 1) + | Tlong :: tys => S Outgoing (ofs + 1) Tint :: S Outgoing ofs Tint :: loc_arguments_rec tys (ofs + 2) + | Tany32 :: tys => S Outgoing ofs Tany32 :: loc_arguments_rec tys (ofs + 1) + | Tany64 :: tys => S Outgoing ofs Tany64 :: loc_arguments_rec tys (ofs + 2) + end. + +(** [loc_arguments s] returns the list of locations where to store arguments + when calling a function with signature [s]. *) + +Definition loc_arguments (s: signature) : list loc := + loc_arguments_rec s.(sig_args) 0. + +(** [size_arguments s] returns the number of [Outgoing] slots used + to call a function with signature [s]. *) + +Fixpoint size_arguments_rec + (tyl: list typ) (ofs: Z) {struct tyl} : Z := + match tyl with + | nil => ofs + | ty :: tys => size_arguments_rec tys (ofs + typesize ty) + end. + +Definition size_arguments (s: signature) : Z := + size_arguments_rec s.(sig_args) 0. + +(** Argument locations are either caller-save registers or [Outgoing] + stack slots at nonnegative offsets. *) + +Definition loc_argument_acceptable (l: loc) : Prop := + match l with + | R r => In r destroyed_at_call + | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong + | _ => False + end. + +Remark loc_arguments_rec_charact: + forall tyl ofs l, + In l (loc_arguments_rec tyl ofs) -> + match l with + | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong + | _ => False + end. +Proof. + induction tyl; simpl loc_arguments_rec; intros. +- destruct H. +- assert (REC: forall ofs1, In l (loc_arguments_rec tyl ofs1) -> ofs1 > ofs -> + match l with + | R _ => False + | S Local _ _ => False + | S Incoming _ _ => False + | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong + end). + { intros. exploit IHtyl; eauto. destruct l; auto. destruct sl; intuition omega +. } + destruct a; simpl in H; repeat (destruct H); + ((eapply REC; eauto; omega) || (split; [omega|congruence])). +Qed. + +Lemma loc_arguments_acceptable: + forall (s: signature) (l: loc), + In l (loc_arguments s) -> loc_argument_acceptable l. +Proof. + unfold loc_arguments; intros. + exploit loc_arguments_rec_charact; eauto. + unfold loc_argument_acceptable. + destruct l; tauto. +Qed. + +Hint Resolve loc_arguments_acceptable: locs. + +(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) + +Remark size_arguments_rec_above: + forall tyl ofs0, ofs0 <= size_arguments_rec tyl ofs0. +Proof. + induction tyl; simpl; intros. + omega. + apply Zle_trans with (ofs0 + typesize a); auto. + generalize (typesize_pos a); omega. +Qed. + +Lemma size_arguments_above: + forall s, size_arguments s >= 0. +Proof. + intros; unfold size_arguments. apply Zle_ge. + apply size_arguments_rec_above. +Qed. + +Lemma loc_arguments_bounded: + forall (s: signature) (ofs: Z) (ty: typ), + In (S Outgoing ofs ty) (loc_arguments s) -> + ofs + typesize ty <= size_arguments s. +Proof. + intros until ty. unfold loc_arguments, size_arguments. generalize (sig_args s) 0. + induction l; simpl; intros. +- contradiction. +- Ltac decomp := + match goal with + | [ H: _ \/ _ |- _ ] => destruct H; decomp + | [ H: S _ _ _ = S _ _ _ |- _ ] => inv H + | _ => idtac + end. + destruct a; simpl in H; decomp; auto; try apply size_arguments_rec_above. + simpl typesize. replace (z + 1 + 1) with (z + 2) by omega. apply size_arguments_rec_above. + simpl typesize. apply Zle_trans with (ofs + 2). omega. apply size_arguments_rec_above. +Qed. + +Lemma loc_arguments_main: + loc_arguments signature_main = nil. +Proof. + reflexivity. +Qed. diff --git a/ia32/Stacklayout.v b/ia32/Stacklayout.v new file mode 100644 index 0000000..f9d1daf --- /dev/null +++ b/ia32/Stacklayout.v @@ -0,0 +1,130 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Machine- and ABI-dependent layout information for activation records. *) + +Require Import Coqlib. +Require Import Bounds. + +(** The general shape of activation records is as follows, + from bottom (lowest offsets) to top: +- Space for outgoing arguments to function calls. +- Back link to parent frame +- Saved values of integer callee-save registers used by the function. +- Saved values of float callee-save registers used by the function. +- Local stack slots. +- Space for the stack-allocated data declared in Cminor +- Return address. + +The [frame_env] compilation environment records the positions of +the boundaries between these areas of the activation record. +*) + +Definition fe_ofs_arg := 0. + +Record frame_env : Type := mk_frame_env { + fe_size: Z; + fe_ofs_link: Z; + fe_ofs_retaddr: Z; + fe_ofs_local: Z; + fe_ofs_int_callee_save: Z; + fe_num_int_callee_save: Z; + fe_ofs_float_callee_save: Z; + fe_num_float_callee_save: Z; + fe_stack_data: Z +}. + +(** Computation of the frame environment from the bounds of the current + function. *) + +Definition make_env (b: bounds) := + let olink := 4 * b.(bound_outgoing) in (* back link *) + let oics := olink + 4 in (* integer callee-saves *) + let ofcs := align (oics + 4 * b.(bound_int_callee_save)) 8 in (* float callee-saves *) + let ol := ofcs + 8 * b.(bound_float_callee_save) in (* locals *) + let ostkdata := align (ol + 4 * b.(bound_local)) 8 in (* stack data *) + let oretaddr := align (ostkdata + b.(bound_stack_data)) 4 in (* return address *) + let sz := oretaddr + 4 in (* total size *) + mk_frame_env sz olink oretaddr + ol + oics b.(bound_int_callee_save) + ofcs b.(bound_float_callee_save) + ostkdata. + +(** Separation property *) + +Remark frame_env_separated: + forall b, + let fe := make_env b in + 0 <= fe_ofs_arg + /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_link) + /\ fe.(fe_ofs_link) + 4 <= fe.(fe_ofs_int_callee_save) + /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) + /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_ofs_local) + /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_stack_data) + /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_ofs_retaddr) + /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_size). +Proof. + intros. + generalize (align_le (fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). + generalize (align_le (fe.(fe_ofs_local) + 4 * b.(bound_local)) 8 (refl_equal _)). + generalize (align_le (fe.(fe_stack_data) + b.(bound_stack_data)) 4 (refl_equal _)). + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data, fe_ofs_arg. + intros. + generalize (bound_local_pos b); intro; + generalize (bound_int_callee_save_pos b); intro; + generalize (bound_float_callee_save_pos b); intro; + generalize (bound_outgoing_pos b); intro; + generalize (bound_stack_data_pos b); intro. + omega. +Qed. + +(** Alignment property *) + +Remark frame_env_aligned: + forall b, + let fe := make_env b in + (4 | fe.(fe_ofs_link)) + /\ (4 | fe.(fe_ofs_int_callee_save)) + /\ (8 | fe.(fe_ofs_float_callee_save)) + /\ (8 | fe.(fe_ofs_local)) + /\ (8 | fe.(fe_stack_data)) + /\ (4 | fe.(fe_ofs_retaddr)) + /\ (4 | fe.(fe_size)). +Proof. + intros. + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, + fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data. + set (x1 := 4 * bound_outgoing b). + assert (4 | x1). unfold x1; exists (bound_outgoing b); ring. + set (x2 := x1 + 4). + assert (4 | x2). unfold x2; apply Zdivide_plus_r; auto. exists 1; auto. + set (x3 := x2 + 4 * bound_int_callee_save b). + set (x4 := align x3 8). + assert (8 | x4). unfold x4. apply align_divides. omega. + set (x5 := x4 + 8 * bound_float_callee_save b). + assert (8 | x5). unfold x5; apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. + set (x6 := align (x5 + 4 * bound_local b) 8). + assert (8 | x6). unfold x6; apply align_divides; omega. + set (x7 := align (x6 + bound_stack_data b) 4). + assert (4 | x7). unfold x7; apply align_divides; omega. + set (x8 := x7 + 4). + assert (4 | x8). unfold x8; apply Zdivide_plus_r; auto. exists 1; auto. + tauto. +Qed. + diff --git a/ia32/standard/Conventions1.v b/ia32/standard/Conventions1.v deleted file mode 100644 index d1f7acd..0000000 --- a/ia32/standard/Conventions1.v +++ /dev/null @@ -1,366 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Function calling conventions and other conventions regarding the use of - machine registers and stack slots. *) - -Require Import Coqlib. -Require Import AST. -Require Import Events. -Require Import Locations. - -(** * Classification of machine registers *) - -(** Machine registers (type [mreg] in module [Locations]) are divided in - the following groups: -- Callee-save registers, whose value is preserved across a function call. -- Caller-save registers that can be modified during a function call. - - We follow the x86-32 application binary interface (ABI) in our choice - of callee- and caller-save registers. -*) - -Definition int_caller_save_regs := AX :: CX :: DX :: nil. - -Definition float_caller_save_regs := X0 :: X1 :: X2 :: X3 :: X4 :: X5 :: X6 :: X7 :: nil. - -Definition int_callee_save_regs := BX :: SI :: DI :: BP :: nil. - -Definition float_callee_save_regs : list mreg := nil. - -Definition destroyed_at_call := - FP0 :: int_caller_save_regs ++ float_caller_save_regs. - -Definition dummy_int_reg := AX. (**r Used in [Regalloc]. *) -Definition dummy_float_reg := X0. (**r Used in [Regalloc]. *) - -(** The [index_int_callee_save] and [index_float_callee_save] associate - a unique positive integer to callee-save registers. This integer is - used in [Stacking] to determine where to save these registers in - the activation record if they are used by the current function. *) - -Definition index_int_callee_save (r: mreg) := - match r with - | BX => 0 | SI => 1 | DI => 2 | BP => 3 | _ => -1 - end. - -Definition index_float_callee_save (r: mreg) := -1. - -Ltac ElimOrEq := - match goal with - | |- (?x = ?y) \/ _ -> _ => - let H := fresh in - (intro H; elim H; clear H; - [intro H; rewrite <- H; clear H | ElimOrEq]) - | |- False -> _ => - let H := fresh in (intro H; contradiction) - end. - -Ltac OrEq := - match goal with - | |- (?x = ?x) \/ _ => left; reflexivity - | |- (?x = ?y) \/ _ => right; OrEq - | |- False => fail - end. - -Ltac NotOrEq := - match goal with - | |- (?x = ?y) \/ _ -> False => - let H := fresh in ( - intro H; elim H; clear H; [intro; discriminate | NotOrEq]) - | |- False -> False => - contradiction - end. - -Lemma index_int_callee_save_pos: - forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. -Qed. - -Lemma index_float_callee_save_pos: - forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. -Qed. - -Lemma index_int_callee_save_pos2: - forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_float_callee_save_pos2: - forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. -Proof. - unfold index_float_callee_save; intros. omegaContradiction. -Qed. - -Lemma index_int_callee_save_inj: - forall r1 r2, - In r1 int_callee_save_regs -> - In r2 int_callee_save_regs -> - r1 <> r2 -> - index_int_callee_save r1 <> index_int_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; - intros; congruence. -Qed. - -Lemma index_float_callee_save_inj: - forall r1 r2, - In r1 float_callee_save_regs -> - In r2 float_callee_save_regs -> - r1 <> r2 -> - index_float_callee_save r1 <> index_float_callee_save r2. -Proof. - simpl; intros. contradiction. -Qed. - -(** The following lemmas show that - (destroyed at call, integer callee-save, float callee-save) - is a partition of the set of machine registers. *) - -Lemma int_float_callee_save_disjoint: - list_disjoint int_callee_save_regs float_callee_save_regs. -Proof. - red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. -Qed. - -Lemma register_classification: - forall r, - In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. -Proof. - destruct r; - try (left; simpl; OrEq); - try (right; left; simpl; OrEq); - try (right; right; simpl; OrEq). -Qed. - -Lemma int_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r int_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma float_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r float_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma int_callee_save_type: - forall r, In r int_callee_save_regs -> mreg_type r = Tany32. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Lemma float_callee_save_type: - forall r, In r float_callee_save_regs -> mreg_type r = Tany64. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Ltac NoRepet := - match goal with - | |- list_norepet nil => - apply list_norepet_nil - | |- list_norepet (?a :: ?b) => - apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] - end. - -Lemma int_callee_save_norepet: - list_norepet int_callee_save_regs. -Proof. - unfold int_callee_save_regs; NoRepet. -Qed. - -Lemma float_callee_save_norepet: - list_norepet float_callee_save_regs. -Proof. - unfold float_callee_save_regs; NoRepet. -Qed. - -(** * Function calling conventions *) - -(** The functions in this section determine the locations (machine registers - and stack slots) used to communicate arguments and results between the - caller and the callee during function calls. These locations are functions - of the signature of the function and of the call instruction. - Agreement between the caller and the callee on the locations to use - is guaranteed by our dynamic semantics for Cminor and RTL, which demand - that the signature of the call instruction is identical to that of the - called function. - - Calling conventions are largely arbitrary: they must respect the properties - proved in this section (such as no overlapping between the locations - of function arguments), but this leaves much liberty in choosing actual - locations. To ensure binary interoperability of code generated by our - compiler with libraries compiled by another compiler, we - implement the standard x86 conventions. *) - -(** ** Location of function result *) - -(** The result value of a function is passed back to the caller in - registers [AX] or [FP0], depending on the type of the returned value. - We treat a function without result as a function with one integer result. *) - -Definition loc_result (s: signature) : list mreg := - match s.(sig_res) with - | None => AX :: nil - | Some (Tint | Tany32) => AX :: nil - | Some (Tfloat | Tsingle) => FP0 :: nil - | Some Tany64 => X0 :: nil - | Some Tlong => DX :: AX :: nil - end. - -(** The result registers have types compatible with that given in the signature. *) - -Lemma loc_result_type: - forall sig, - subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. -Proof. - intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. -Qed. - -(** The result locations are caller-save registers *) - -Lemma loc_result_caller_save: - forall (s: signature) (r: mreg), - In r (loc_result s) -> In r destroyed_at_call. -Proof. - intros. - assert (r = AX \/ r = DX \/ r = FP0 \/ r = X0). - unfold loc_result in H. destruct (sig_res s) as [[]|]; simpl in H; intuition. - destruct H0 as [A | [A | [A | A]]]; subst r; simpl; OrEq. -Qed. - -(** ** Location of function arguments *) - -(** All arguments are passed on stack. (Snif.) *) - -Fixpoint loc_arguments_rec - (tyl: list typ) (ofs: Z) {struct tyl} : list loc := - match tyl with - | nil => nil - | Tint :: tys => S Outgoing ofs Tint :: loc_arguments_rec tys (ofs + 1) - | Tfloat :: tys => S Outgoing ofs Tfloat :: loc_arguments_rec tys (ofs + 2) - | Tsingle :: tys => S Outgoing ofs Tsingle :: loc_arguments_rec tys (ofs + 1) - | Tlong :: tys => S Outgoing (ofs + 1) Tint :: S Outgoing ofs Tint :: loc_arguments_rec tys (ofs + 2) - | Tany32 :: tys => S Outgoing ofs Tany32 :: loc_arguments_rec tys (ofs + 1) - | Tany64 :: tys => S Outgoing ofs Tany64 :: loc_arguments_rec tys (ofs + 2) - end. - -(** [loc_arguments s] returns the list of locations where to store arguments - when calling a function with signature [s]. *) - -Definition loc_arguments (s: signature) : list loc := - loc_arguments_rec s.(sig_args) 0. - -(** [size_arguments s] returns the number of [Outgoing] slots used - to call a function with signature [s]. *) - -Fixpoint size_arguments_rec - (tyl: list typ) (ofs: Z) {struct tyl} : Z := - match tyl with - | nil => ofs - | ty :: tys => size_arguments_rec tys (ofs + typesize ty) - end. - -Definition size_arguments (s: signature) : Z := - size_arguments_rec s.(sig_args) 0. - -(** Argument locations are either caller-save registers or [Outgoing] - stack slots at nonnegative offsets. *) - -Definition loc_argument_acceptable (l: loc) : Prop := - match l with - | R r => In r destroyed_at_call - | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong - | _ => False - end. - -Remark loc_arguments_rec_charact: - forall tyl ofs l, - In l (loc_arguments_rec tyl ofs) -> - match l with - | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong - | _ => False - end. -Proof. - induction tyl; simpl loc_arguments_rec; intros. -- destruct H. -- assert (REC: forall ofs1, In l (loc_arguments_rec tyl ofs1) -> ofs1 > ofs -> - match l with - | R _ => False - | S Local _ _ => False - | S Incoming _ _ => False - | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong - end). - { intros. exploit IHtyl; eauto. destruct l; auto. destruct sl; intuition omega -. } - destruct a; simpl in H; repeat (destruct H); - ((eapply REC; eauto; omega) || (split; [omega|congruence])). -Qed. - -Lemma loc_arguments_acceptable: - forall (s: signature) (l: loc), - In l (loc_arguments s) -> loc_argument_acceptable l. -Proof. - unfold loc_arguments; intros. - exploit loc_arguments_rec_charact; eauto. - unfold loc_argument_acceptable. - destruct l; tauto. -Qed. - -Hint Resolve loc_arguments_acceptable: locs. - -(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) - -Remark size_arguments_rec_above: - forall tyl ofs0, ofs0 <= size_arguments_rec tyl ofs0. -Proof. - induction tyl; simpl; intros. - omega. - apply Zle_trans with (ofs0 + typesize a); auto. - generalize (typesize_pos a); omega. -Qed. - -Lemma size_arguments_above: - forall s, size_arguments s >= 0. -Proof. - intros; unfold size_arguments. apply Zle_ge. - apply size_arguments_rec_above. -Qed. - -Lemma loc_arguments_bounded: - forall (s: signature) (ofs: Z) (ty: typ), - In (S Outgoing ofs ty) (loc_arguments s) -> - ofs + typesize ty <= size_arguments s. -Proof. - intros until ty. unfold loc_arguments, size_arguments. generalize (sig_args s) 0. - induction l; simpl; intros. -- contradiction. -- Ltac decomp := - match goal with - | [ H: _ \/ _ |- _ ] => destruct H; decomp - | [ H: S _ _ _ = S _ _ _ |- _ ] => inv H - | _ => idtac - end. - destruct a; simpl in H; decomp; auto; try apply size_arguments_rec_above. - simpl typesize. replace (z + 1 + 1) with (z + 2) by omega. apply size_arguments_rec_above. - simpl typesize. apply Zle_trans with (ofs + 2). omega. apply size_arguments_rec_above. -Qed. - diff --git a/ia32/standard/Stacklayout.v b/ia32/standard/Stacklayout.v deleted file mode 100644 index f9d1daf..0000000 --- a/ia32/standard/Stacklayout.v +++ /dev/null @@ -1,130 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Machine- and ABI-dependent layout information for activation records. *) - -Require Import Coqlib. -Require Import Bounds. - -(** The general shape of activation records is as follows, - from bottom (lowest offsets) to top: -- Space for outgoing arguments to function calls. -- Back link to parent frame -- Saved values of integer callee-save registers used by the function. -- Saved values of float callee-save registers used by the function. -- Local stack slots. -- Space for the stack-allocated data declared in Cminor -- Return address. - -The [frame_env] compilation environment records the positions of -the boundaries between these areas of the activation record. -*) - -Definition fe_ofs_arg := 0. - -Record frame_env : Type := mk_frame_env { - fe_size: Z; - fe_ofs_link: Z; - fe_ofs_retaddr: Z; - fe_ofs_local: Z; - fe_ofs_int_callee_save: Z; - fe_num_int_callee_save: Z; - fe_ofs_float_callee_save: Z; - fe_num_float_callee_save: Z; - fe_stack_data: Z -}. - -(** Computation of the frame environment from the bounds of the current - function. *) - -Definition make_env (b: bounds) := - let olink := 4 * b.(bound_outgoing) in (* back link *) - let oics := olink + 4 in (* integer callee-saves *) - let ofcs := align (oics + 4 * b.(bound_int_callee_save)) 8 in (* float callee-saves *) - let ol := ofcs + 8 * b.(bound_float_callee_save) in (* locals *) - let ostkdata := align (ol + 4 * b.(bound_local)) 8 in (* stack data *) - let oretaddr := align (ostkdata + b.(bound_stack_data)) 4 in (* return address *) - let sz := oretaddr + 4 in (* total size *) - mk_frame_env sz olink oretaddr - ol - oics b.(bound_int_callee_save) - ofcs b.(bound_float_callee_save) - ostkdata. - -(** Separation property *) - -Remark frame_env_separated: - forall b, - let fe := make_env b in - 0 <= fe_ofs_arg - /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_link) - /\ fe.(fe_ofs_link) + 4 <= fe.(fe_ofs_int_callee_save) - /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) - /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_ofs_local) - /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_stack_data) - /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_ofs_retaddr) - /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_size). -Proof. - intros. - generalize (align_le (fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). - generalize (align_le (fe.(fe_ofs_local) + 4 * b.(bound_local)) 8 (refl_equal _)). - generalize (align_le (fe.(fe_stack_data) + b.(bound_stack_data)) 4 (refl_equal _)). - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data, fe_ofs_arg. - intros. - generalize (bound_local_pos b); intro; - generalize (bound_int_callee_save_pos b); intro; - generalize (bound_float_callee_save_pos b); intro; - generalize (bound_outgoing_pos b); intro; - generalize (bound_stack_data_pos b); intro. - omega. -Qed. - -(** Alignment property *) - -Remark frame_env_aligned: - forall b, - let fe := make_env b in - (4 | fe.(fe_ofs_link)) - /\ (4 | fe.(fe_ofs_int_callee_save)) - /\ (8 | fe.(fe_ofs_float_callee_save)) - /\ (8 | fe.(fe_ofs_local)) - /\ (8 | fe.(fe_stack_data)) - /\ (4 | fe.(fe_ofs_retaddr)) - /\ (4 | fe.(fe_size)). -Proof. - intros. - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, - fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data. - set (x1 := 4 * bound_outgoing b). - assert (4 | x1). unfold x1; exists (bound_outgoing b); ring. - set (x2 := x1 + 4). - assert (4 | x2). unfold x2; apply Zdivide_plus_r; auto. exists 1; auto. - set (x3 := x2 + 4 * bound_int_callee_save b). - set (x4 := align x3 8). - assert (8 | x4). unfold x4. apply align_divides. omega. - set (x5 := x4 + 8 * bound_float_callee_save b). - assert (8 | x5). unfold x5; apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. - set (x6 := align (x5 + 4 * bound_local b) 8). - assert (8 | x6). unfold x6; apply align_divides; omega. - set (x7 := align (x6 + bound_stack_data b) 4). - assert (4 | x7). unfold x7; apply align_divides; omega. - set (x8 := x7 + 4). - assert (4 | x8). unfold x8; apply Zdivide_plus_r; auto. exists 1; auto. - tauto. -Qed. - diff --git a/powerpc/Conventions1.v b/powerpc/Conventions1.v new file mode 100644 index 0000000..7c7177e --- /dev/null +++ b/powerpc/Conventions1.v @@ -0,0 +1,545 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Function calling conventions and other conventions regarding the use of + machine registers and stack slots. *) + +Require Import Coqlib. +Require Import AST. +Require Import Events. +Require Import Locations. + +(** * Classification of machine registers *) + +(** Machine registers (type [mreg] in module [Locations]) are divided in + the following groups: +- Callee-save registers, whose value is preserved across a function call. +- Caller-save registers that can be modified during a function call. + + We follow the PowerPC/EABI application binary interface (ABI) in our choice + of callee- and caller-save registers. +*) + +Definition int_caller_save_regs := + R3 :: R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: R11 :: R12 :: nil. + +Definition float_caller_save_regs := + F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: F8 :: F9 :: F10 :: F11 :: F12 :: F13 :: nil. + +Definition int_callee_save_regs := + R31 :: R30 :: R29 :: R28 :: R27 :: R26 :: R25 :: R24 :: R23 :: + R22 :: R21 :: R20 :: R19 :: R18 :: R17 :: R16 :: R15 :: R14 :: nil. + +Definition float_callee_save_regs := + F31 :: F30 :: F29 :: F28 :: F27 :: F26 :: F25 :: F24 :: F23 :: + F22 :: F21 :: F20 :: F19 :: F18 :: F17 :: F16 :: F15 :: F14 :: nil. + +Definition destroyed_at_call := + int_caller_save_regs ++ float_caller_save_regs. + +Definition dummy_int_reg := R3. (**r Used in [Coloring]. *) +Definition dummy_float_reg := F0. (**r Used in [Coloring]. *) + +(** The [index_int_callee_save] and [index_float_callee_save] associate + a unique positive integer to callee-save registers. This integer is + used in [Stacking] to determine where to save these registers in + the activation record if they are used by the current function. *) + +Definition index_int_callee_save (r: mreg) := + match r with + | R14 => 17 | R15 => 16 | R16 => 15 | R17 => 14 + | R18 => 13 | R19 => 12 | R20 => 11 | R21 => 10 + | R22 => 9 | R23 => 8 | R24 => 7 | R25 => 6 + | R26 => 5 | R27 => 4 | R28 => 3 | R29 => 2 + | R30 => 1 | R31 => 0 | _ => -1 + end. + +Definition index_float_callee_save (r: mreg) := + match r with + | F14 => 17 | F15 => 16 | F16 => 15 | F17 => 14 + | F18 => 13 | F19 => 12 | F20 => 11 | F21 => 10 + | F22 => 9 | F23 => 8 | F24 => 7 | F25 => 6 + | F26 => 5 | F27 => 4 | F28 => 3 | F29 => 2 + | F30 => 1 | F31 => 0 | _ => -1 + end. + +Ltac ElimOrEq := + match goal with + | |- (?x = ?y) \/ _ -> _ => + let H := fresh in + (intro H; elim H; clear H; + [intro H; rewrite <- H; clear H | ElimOrEq]) + | |- False -> _ => + let H := fresh in (intro H; contradiction) + end. + +Ltac OrEq := + match goal with + | |- (?x = ?x) \/ _ => left; reflexivity + | |- (?x = ?y) \/ _ => right; OrEq + | |- False => fail + end. + +Ltac NotOrEq := + match goal with + | |- (?x = ?y) \/ _ -> False => + let H := fresh in ( + intro H; elim H; clear H; [intro; discriminate | NotOrEq]) + | |- False -> False => + contradiction + end. + +Lemma index_int_callee_save_pos: + forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. +Qed. + +Lemma index_float_callee_save_pos: + forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. +Proof. + intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. +Qed. + +Lemma index_int_callee_save_pos2: + forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. +Proof. + destruct r; simpl; intro; omegaContradiction || OrEq. +Qed. + +Lemma index_float_callee_save_pos2: + forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. +Proof. + destruct r; simpl; intro; omegaContradiction || OrEq. +Qed. + +Lemma index_int_callee_save_inj: + forall r1 r2, + In r1 int_callee_save_regs -> + In r2 int_callee_save_regs -> + r1 <> r2 -> + index_int_callee_save r1 <> index_int_callee_save r2. +Proof. + intros r1 r2. + simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; + intros; congruence. +Qed. + +Lemma index_float_callee_save_inj: + forall r1 r2, + In r1 float_callee_save_regs -> + In r2 float_callee_save_regs -> + r1 <> r2 -> + index_float_callee_save r1 <> index_float_callee_save r2. +Proof. + intros r1 r2. + simpl; ElimOrEq; ElimOrEq; unfold index_float_callee_save; + intros; congruence. +Qed. + +(** The following lemmas show that + (temporaries, destroyed at call, integer callee-save, float callee-save) + is a partition of the set of machine registers. *) + +Lemma int_float_callee_save_disjoint: + list_disjoint int_callee_save_regs float_callee_save_regs. +Proof. + red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. +Qed. + +Lemma register_classification: + forall r, + In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. +Proof. + destruct r; + try (left; simpl; OrEq); + try (right; left; simpl; OrEq); + try (right; right; simpl; OrEq). +Qed. + +Lemma int_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r int_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma float_callee_save_not_destroyed: + forall r, + In r destroyed_at_call -> In r float_callee_save_regs -> False. +Proof. + intros. revert H0 H. simpl. ElimOrEq; NotOrEq. +Qed. + +Lemma int_callee_save_type: + forall r, In r int_callee_save_regs -> mreg_type r = Tany32. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Lemma float_callee_save_type: + forall r, In r float_callee_save_regs -> mreg_type r = Tany64. +Proof. + intro. simpl; ElimOrEq; reflexivity. +Qed. + +Ltac NoRepet := + match goal with + | |- list_norepet nil => + apply list_norepet_nil + | |- list_norepet (?a :: ?b) => + apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] + end. + +Lemma int_callee_save_norepet: + list_norepet int_callee_save_regs. +Proof. + unfold int_callee_save_regs; NoRepet. +Qed. + +Lemma float_callee_save_norepet: + list_norepet float_callee_save_regs. +Proof. + unfold float_callee_save_regs; NoRepet. +Qed. + +(** * Function calling conventions *) + +(** The functions in this section determine the locations (machine registers + and stack slots) used to communicate arguments and results between the + caller and the callee during function calls. These locations are functions + of the signature of the function and of the call instruction. + Agreement between the caller and the callee on the locations to use + is guaranteed by our dynamic semantics for Cminor and RTL, which demand + that the signature of the call instruction is identical to that of the + called function. + + Calling conventions are largely arbitrary: they must respect the properties + proved in this section (such as no overlapping between the locations + of function arguments), but this leaves much liberty in choosing actual + locations. To ensure binary interoperability of code generated by our + compiler with libraries compiled by another PowerPC compiler, we + implement the standard conventions defined in the PowerPC/EABI + application binary interface. *) + +(** ** Location of function result *) + +(** The result value of a function is passed back to the caller in + registers [R3] or [F1] or [R3, R4], depending on the type of the returned value. + We treat a function without result as a function with one integer result. *) + +Definition loc_result (s: signature) : list mreg := + match s.(sig_res) with + | None => R3 :: nil + | Some (Tint | Tany32) => R3 :: nil + | Some (Tfloat | Tsingle | Tany64) => F1 :: nil + | Some Tlong => R3 :: R4 :: nil + end. + +(** The result registers have types compatible with that given in the signature. *) + +Lemma loc_result_type: + forall sig, + subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. +Proof. + intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. +Qed. + +(** The result locations are caller-save registers *) + +Lemma loc_result_caller_save: + forall (s: signature) (r: mreg), + In r (loc_result s) -> In r destroyed_at_call. +Proof. + intros. + assert (r = R3 \/ r = R4 \/ r = F1). + unfold loc_result in H. destruct (sig_res s); [destruct t|idtac]; simpl in H; intuition. + destruct H0 as [A | [A | A]]; subst r; simpl; OrEq. +Qed. + +(** ** Location of function arguments *) + +(** The PowerPC EABI states the following convention for passing arguments + to a function: +- The first 8 integer arguments are passed in registers [R3] to [R10]. +- The first 8 float arguments are passed in registers [F1] to [F8]. +- The first 4 long integer arguments are passed in register pairs [R3,R4] ... [R9,R10]. +- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively + assigned (1 word for an integer argument, 2 words for a float), + starting at word offset 0. +- No stack space is reserved for the arguments that are passed in registers. +*) + +Definition int_param_regs := + R3 :: R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: nil. +Definition float_param_regs := + F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: F8 :: nil. + +Fixpoint loc_arguments_rec + (tyl: list typ) (ir fr ofs: Z) {struct tyl} : list loc := + match tyl with + | nil => nil + | (Tint | Tany32) as ty :: tys => + match list_nth_z int_param_regs ir with + | None => + S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 1) + | Some ireg => + R ireg :: loc_arguments_rec tys (ir + 1) fr ofs + end + | (Tfloat | Tsingle | Tany64) as ty :: tys => + match list_nth_z float_param_regs fr with + | None => + let ofs := align ofs 2 in + S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 2) + | Some freg => + R freg :: loc_arguments_rec tys ir (fr + 1) ofs + end + | Tlong :: tys => + let ir := align ir 2 in + match list_nth_z int_param_regs ir, list_nth_z int_param_regs (ir + 1) with + | Some r1, Some r2 => + R r1 :: R r2 :: loc_arguments_rec tys (ir + 2) fr ofs + | _, _ => + let ofs := align ofs 2 in + S Outgoing ofs Tint :: S Outgoing (ofs + 1) Tint :: loc_arguments_rec tys ir fr (ofs + 2) + end + end. + +(** [loc_arguments s] returns the list of locations where to store arguments + when calling a function with signature [s]. *) + +Definition loc_arguments (s: signature) : list loc := + loc_arguments_rec s.(sig_args) 0 0 0. + +(** [size_arguments s] returns the number of [Outgoing] slots used + to call a function with signature [s]. *) + +Fixpoint size_arguments_rec (tyl: list typ) (ir fr ofs: Z) {struct tyl} : Z := + match tyl with + | nil => ofs + | (Tint | Tany32) :: tys => + match list_nth_z int_param_regs ir with + | None => size_arguments_rec tys ir fr (ofs + 1) + | Some ireg => size_arguments_rec tys (ir + 1) fr ofs + end + | (Tfloat | Tsingle | Tany64) :: tys => + match list_nth_z float_param_regs fr with + | None => size_arguments_rec tys ir fr (align ofs 2 + 2) + | Some freg => size_arguments_rec tys ir (fr + 1) ofs + end + | Tlong :: tys => + let ir := align ir 2 in + match list_nth_z int_param_regs ir, list_nth_z int_param_regs (ir + 1) with + | Some r1, Some r2 => size_arguments_rec tys (ir + 2) fr ofs + | _, _ => size_arguments_rec tys ir fr (align ofs 2 + 2) + end + end. + +Definition size_arguments (s: signature) : Z := + size_arguments_rec s.(sig_args) 0 0 0. + +(** A tail-call is possible for a signature if the corresponding + arguments are all passed in registers. *) + +Definition tailcall_possible (s: signature) : Prop := + forall l, In l (loc_arguments s) -> + match l with R _ => True | S _ _ _ => False end. + +(** Argument locations are either caller-save registers or [Outgoing] + stack slots at nonnegative offsets. *) + +Definition loc_argument_acceptable (l: loc) : Prop := + match l with + | R r => In r destroyed_at_call + | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong + | _ => False + end. + +Remark loc_arguments_rec_charact: + forall tyl ir fr ofs l, + In l (loc_arguments_rec tyl ir fr ofs) -> + match l with + | R r => In r int_param_regs \/ In r float_param_regs + | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong + | S _ _ _ => False + end. +Proof. +Opaque list_nth_z. + induction tyl; simpl loc_arguments_rec; intros. + elim H. + destruct a. +- (* int *) + destruct (list_nth_z int_param_regs ir) as [r|] eqn:E; destruct H. + subst. left. eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + subst. split. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. +- (* float *) + destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. + subst. right. eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + subst. split. apply Zle_ge. apply align_le. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. + assert (ofs <= align ofs 2) by (apply align_le; omega). + intuition omega. +- (* long *) + set (ir' := align ir 2) in *. + destruct (list_nth_z int_param_regs ir') as [r1|] eqn:E1. + destruct (list_nth_z int_param_regs (ir' + 1)) as [r2|] eqn:E2. + destruct H. subst; left; eapply list_nth_z_in; eauto. + destruct H. subst; left; eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + assert (ofs <= align ofs 2) by (apply align_le; omega). + destruct H. subst. split. omega. congruence. + destruct H. subst. split. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. + assert (ofs <= align ofs 2) by (apply align_le; omega). + destruct H. subst. split. omega. congruence. + destruct H. subst. split. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. +- (* single *) + destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. + subst. right. eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + subst. split. apply Zle_ge. apply align_le. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. + assert (ofs <= align ofs 2) by (apply align_le; omega). + intuition omega. +- (* any32 *) + destruct (list_nth_z int_param_regs ir) as [r|] eqn:E; destruct H. + subst. left. eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + subst. split. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. +- (* any64 *) + destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. + subst. right. eapply list_nth_z_in; eauto. + eapply IHtyl; eauto. + subst. split. apply Zle_ge. apply align_le. omega. congruence. + exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. + assert (ofs <= align ofs 2) by (apply align_le; omega). + intuition omega. +Qed. + +Lemma loc_arguments_acceptable: + forall (s: signature) (l: loc), + In l (loc_arguments s) -> loc_argument_acceptable l. +Proof. + unfold loc_arguments; intros. + generalize (loc_arguments_rec_charact _ _ _ _ _ H). + destruct l. + intro H0; elim H0; simpl; ElimOrEq; OrEq. + destruct sl; try contradiction. simpl. intuition omega. +Qed. +Hint Resolve loc_arguments_acceptable: locs. + +(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) + +Remark size_arguments_rec_above: + forall tyl ir fr ofs0, + ofs0 <= size_arguments_rec tyl ir fr ofs0. +Proof. + induction tyl; simpl; intros. + omega. + destruct a. + destruct (list_nth_z int_param_regs ir); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. + destruct (list_nth_z float_param_regs fr); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + set (ir' := align ir 2). + destruct (list_nth_z int_param_regs ir'); eauto. + destruct (list_nth_z int_param_regs (ir' + 1)); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + destruct (list_nth_z float_param_regs fr); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. + destruct (list_nth_z int_param_regs ir); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. + destruct (list_nth_z float_param_regs fr); eauto. + apply Zle_trans with (align ofs0 2). apply align_le; omega. + apply Zle_trans with (align ofs0 2 + 2); auto; omega. +Qed. + +Lemma size_arguments_above: + forall s, size_arguments s >= 0. +Proof. + intros; unfold size_arguments. apply Zle_ge. + apply size_arguments_rec_above. +Qed. + +Lemma loc_arguments_bounded: + forall (s: signature) (ofs: Z) (ty: typ), + In (S Outgoing ofs ty) (loc_arguments s) -> + ofs + typesize ty <= size_arguments s. +Proof. + intros. + assert (forall tyl ir fr ofs0, + In (S Outgoing ofs ty) (loc_arguments_rec tyl ir fr ofs0) -> + ofs + typesize ty <= size_arguments_rec tyl ir fr ofs0). +{ + induction tyl; simpl; intros. + elim H0. + destruct a. +- (* int *) + destruct (list_nth_z int_param_regs ir); destruct H0. + congruence. + eauto. + inv H0. apply size_arguments_rec_above. + eauto. +- (* float *) + destruct (list_nth_z float_param_regs fr); destruct H0. + congruence. + eauto. + inv H0. apply size_arguments_rec_above. eauto. +- (* long *) + set (ir' := align ir 2) in *. + destruct (list_nth_z int_param_regs ir'). + destruct (list_nth_z int_param_regs (ir' + 1)). + destruct H0. congruence. destruct H0. congruence. eauto. + destruct H0. inv H0. + transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. + destruct H0. inv H0. + transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. + eauto. + destruct H0. inv H0. + transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. + destruct H0. inv H0. + transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. + eauto. +- (* single *) + destruct (list_nth_z float_param_regs fr); destruct H0. + congruence. + eauto. + inv H0. transitivity (align ofs0 2 + 2). simpl; omega. apply size_arguments_rec_above. + eauto. +- (* any32 *) + destruct (list_nth_z int_param_regs ir); destruct H0. + congruence. + eauto. + inv H0. apply size_arguments_rec_above. + eauto. +- (* any64 *) + destruct (list_nth_z float_param_regs fr); destruct H0. + congruence. + eauto. + inv H0. apply size_arguments_rec_above. eauto. + } + eauto. +Qed. + +Lemma loc_arguments_main: + loc_arguments signature_main = nil. +Proof. + reflexivity. +Qed. diff --git a/powerpc/Stacklayout.v b/powerpc/Stacklayout.v new file mode 100644 index 0000000..be823c1 --- /dev/null +++ b/powerpc/Stacklayout.v @@ -0,0 +1,134 @@ +(* *********************************************************************) +(* *) +(* 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. *) +(* *) +(* *********************************************************************) + +(** Machine- and ABI-dependent layout information for activation records. *) + +Require Import Coqlib. +Require Import Bounds. + +(** In the PowerPC/EABI application binary interface, + the general shape of activation records is as follows, + from bottom (lowest offsets) to top: +- 8 reserved bytes. The first 4 bytes hold the back pointer to the + activation record of the caller. The next 4 bytes are reserved + for called functions to store their return addresses. + Since we would rather store our return address in our own + frame, we will not use these 4 bytes, and just reserve them. +- Space for outgoing arguments to function calls. +- Local stack slots. +- Saved values of integer callee-save registers used by the function. +- Saved values of float callee-save registers used by the function. +- Space for the stack-allocated data declared in Cminor. + +The [frame_env] compilation environment records the positions of +the boundaries between areas in the frame part. +*) + +Definition fe_ofs_arg := 8. + +Record frame_env : Type := mk_frame_env { + fe_size: Z; + fe_ofs_link: Z; + fe_ofs_retaddr: Z; + fe_ofs_local: Z; + fe_ofs_int_callee_save: Z; + fe_num_int_callee_save: Z; + fe_ofs_float_callee_save: Z; + fe_num_float_callee_save: Z; + fe_stack_data: Z +}. + +(** Computation of the frame environment from the bounds of the current + function. *) + +Definition make_env (b: bounds) := + let ol := align (8 + 4 * b.(bound_outgoing)) 8 in (* locals *) + let ora := ol + 4 * b.(bound_local) in (* saved return address *) + let oics := ora + 4 in (* integer callee-saves *) + let oendi := oics + 4 * b.(bound_int_callee_save) in + let ofcs := align oendi 8 in (* float callee-saves *) + let ostkdata := ofcs + 8 * b.(bound_float_callee_save) in (* stack data *) + let sz := align (ostkdata + b.(bound_stack_data)) 16 in + mk_frame_env sz 0 ora + ol + oics b.(bound_int_callee_save) + ofcs b.(bound_float_callee_save) + ostkdata. + +(** Separation property *) + +Remark frame_env_separated: + forall b, + let fe := make_env b in + 0 <= fe.(fe_ofs_link) + /\ fe.(fe_ofs_link) + 4 <= fe_ofs_arg + /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_local) + /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_ofs_retaddr) + /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_ofs_int_callee_save) + /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) + /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_stack_data) + /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_size) + /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_size). +Proof. + intros. + generalize (align_le (8 + 4 * b.(bound_outgoing)) 8 (refl_equal _)). + generalize (align_le (fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). + generalize (align_le (fe.(fe_stack_data) + b.(bound_stack_data)) 16 (refl_equal _)). + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, + fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data, fe_ofs_arg. + intros. + generalize (bound_local_pos b); intro; + generalize (bound_int_callee_save_pos b); intro; + generalize (bound_float_callee_save_pos b); intro; + generalize (bound_outgoing_pos b); intro; + generalize (bound_stack_data_pos b); intro. + omega. +Qed. + +(** Alignment property *) + +Remark frame_env_aligned: + forall b, + let fe := make_env b in + (4 | fe.(fe_ofs_link)) + /\ (8 | fe.(fe_ofs_local)) + /\ (4 | fe.(fe_ofs_int_callee_save)) + /\ (8 | fe.(fe_ofs_float_callee_save)) + /\ (4 | fe.(fe_ofs_retaddr)) + /\ (8 | fe.(fe_stack_data)) + /\ (16 | fe.(fe_size)). +Proof. + intros. + unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, + fe_ofs_local, fe_ofs_int_callee_save, + fe_num_int_callee_save, + fe_ofs_float_callee_save, fe_num_float_callee_save, + fe_stack_data. + set (x1 := align (8 + 4 * bound_outgoing b) 8). + assert (8 | x1). unfold x1; apply align_divides. omega. + set (x2 := x1 + 4 * bound_local b). + assert (4 | x2). unfold x2; apply Zdivide_plus_r; auto. + apply Zdivides_trans with 8. exists 2; auto. auto. + exists (bound_local b); ring. + set (x3 := x2 + 4). + assert (4 | x3). unfold x3; apply Zdivide_plus_r; auto. exists 1; auto. + set (x4 := align (x3 + 4 * bound_int_callee_save b) 8). + assert (8 | x4). unfold x4. apply align_divides. omega. + set (x5 := x4 + 8 * bound_float_callee_save b). + assert (8 | x5). unfold x5. apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. + set (x6 := align (x5 + bound_stack_data b) 16). + assert (16 | x6). unfold x6; apply align_divides. omega. + intuition. +Qed. diff --git a/powerpc/eabi/Conventions1.v b/powerpc/eabi/Conventions1.v deleted file mode 100644 index 866e73d..0000000 --- a/powerpc/eabi/Conventions1.v +++ /dev/null @@ -1,539 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Function calling conventions and other conventions regarding the use of - machine registers and stack slots. *) - -Require Import Coqlib. -Require Import AST. -Require Import Events. -Require Import Locations. - -(** * Classification of machine registers *) - -(** Machine registers (type [mreg] in module [Locations]) are divided in - the following groups: -- Callee-save registers, whose value is preserved across a function call. -- Caller-save registers that can be modified during a function call. - - We follow the PowerPC/EABI application binary interface (ABI) in our choice - of callee- and caller-save registers. -*) - -Definition int_caller_save_regs := - R3 :: R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: R11 :: R12 :: nil. - -Definition float_caller_save_regs := - F0 :: F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: F8 :: F9 :: F10 :: F11 :: F12 :: F13 :: nil. - -Definition int_callee_save_regs := - R31 :: R30 :: R29 :: R28 :: R27 :: R26 :: R25 :: R24 :: R23 :: - R22 :: R21 :: R20 :: R19 :: R18 :: R17 :: R16 :: R15 :: R14 :: nil. - -Definition float_callee_save_regs := - F31 :: F30 :: F29 :: F28 :: F27 :: F26 :: F25 :: F24 :: F23 :: - F22 :: F21 :: F20 :: F19 :: F18 :: F17 :: F16 :: F15 :: F14 :: nil. - -Definition destroyed_at_call := - int_caller_save_regs ++ float_caller_save_regs. - -Definition dummy_int_reg := R3. (**r Used in [Coloring]. *) -Definition dummy_float_reg := F0. (**r Used in [Coloring]. *) - -(** The [index_int_callee_save] and [index_float_callee_save] associate - a unique positive integer to callee-save registers. This integer is - used in [Stacking] to determine where to save these registers in - the activation record if they are used by the current function. *) - -Definition index_int_callee_save (r: mreg) := - match r with - | R14 => 17 | R15 => 16 | R16 => 15 | R17 => 14 - | R18 => 13 | R19 => 12 | R20 => 11 | R21 => 10 - | R22 => 9 | R23 => 8 | R24 => 7 | R25 => 6 - | R26 => 5 | R27 => 4 | R28 => 3 | R29 => 2 - | R30 => 1 | R31 => 0 | _ => -1 - end. - -Definition index_float_callee_save (r: mreg) := - match r with - | F14 => 17 | F15 => 16 | F16 => 15 | F17 => 14 - | F18 => 13 | F19 => 12 | F20 => 11 | F21 => 10 - | F22 => 9 | F23 => 8 | F24 => 7 | F25 => 6 - | F26 => 5 | F27 => 4 | F28 => 3 | F29 => 2 - | F30 => 1 | F31 => 0 | _ => -1 - end. - -Ltac ElimOrEq := - match goal with - | |- (?x = ?y) \/ _ -> _ => - let H := fresh in - (intro H; elim H; clear H; - [intro H; rewrite <- H; clear H | ElimOrEq]) - | |- False -> _ => - let H := fresh in (intro H; contradiction) - end. - -Ltac OrEq := - match goal with - | |- (?x = ?x) \/ _ => left; reflexivity - | |- (?x = ?y) \/ _ => right; OrEq - | |- False => fail - end. - -Ltac NotOrEq := - match goal with - | |- (?x = ?y) \/ _ -> False => - let H := fresh in ( - intro H; elim H; clear H; [intro; discriminate | NotOrEq]) - | |- False -> False => - contradiction - end. - -Lemma index_int_callee_save_pos: - forall r, In r int_callee_save_regs -> index_int_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_int_callee_save; omega. -Qed. - -Lemma index_float_callee_save_pos: - forall r, In r float_callee_save_regs -> index_float_callee_save r >= 0. -Proof. - intro r. simpl; ElimOrEq; unfold index_float_callee_save; omega. -Qed. - -Lemma index_int_callee_save_pos2: - forall r, index_int_callee_save r >= 0 -> In r int_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_float_callee_save_pos2: - forall r, index_float_callee_save r >= 0 -> In r float_callee_save_regs. -Proof. - destruct r; simpl; intro; omegaContradiction || OrEq. -Qed. - -Lemma index_int_callee_save_inj: - forall r1 r2, - In r1 int_callee_save_regs -> - In r2 int_callee_save_regs -> - r1 <> r2 -> - index_int_callee_save r1 <> index_int_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_int_callee_save; - intros; congruence. -Qed. - -Lemma index_float_callee_save_inj: - forall r1 r2, - In r1 float_callee_save_regs -> - In r2 float_callee_save_regs -> - r1 <> r2 -> - index_float_callee_save r1 <> index_float_callee_save r2. -Proof. - intros r1 r2. - simpl; ElimOrEq; ElimOrEq; unfold index_float_callee_save; - intros; congruence. -Qed. - -(** The following lemmas show that - (temporaries, destroyed at call, integer callee-save, float callee-save) - is a partition of the set of machine registers. *) - -Lemma int_float_callee_save_disjoint: - list_disjoint int_callee_save_regs float_callee_save_regs. -Proof. - red; intros r1 r2. simpl; ElimOrEq; ElimOrEq; discriminate. -Qed. - -Lemma register_classification: - forall r, - In r destroyed_at_call \/ In r int_callee_save_regs \/ In r float_callee_save_regs. -Proof. - destruct r; - try (left; simpl; OrEq); - try (right; left; simpl; OrEq); - try (right; right; simpl; OrEq). -Qed. - -Lemma int_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r int_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma float_callee_save_not_destroyed: - forall r, - In r destroyed_at_call -> In r float_callee_save_regs -> False. -Proof. - intros. revert H0 H. simpl. ElimOrEq; NotOrEq. -Qed. - -Lemma int_callee_save_type: - forall r, In r int_callee_save_regs -> mreg_type r = Tany32. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Lemma float_callee_save_type: - forall r, In r float_callee_save_regs -> mreg_type r = Tany64. -Proof. - intro. simpl; ElimOrEq; reflexivity. -Qed. - -Ltac NoRepet := - match goal with - | |- list_norepet nil => - apply list_norepet_nil - | |- list_norepet (?a :: ?b) => - apply list_norepet_cons; [simpl; intuition discriminate | NoRepet] - end. - -Lemma int_callee_save_norepet: - list_norepet int_callee_save_regs. -Proof. - unfold int_callee_save_regs; NoRepet. -Qed. - -Lemma float_callee_save_norepet: - list_norepet float_callee_save_regs. -Proof. - unfold float_callee_save_regs; NoRepet. -Qed. - -(** * Function calling conventions *) - -(** The functions in this section determine the locations (machine registers - and stack slots) used to communicate arguments and results between the - caller and the callee during function calls. These locations are functions - of the signature of the function and of the call instruction. - Agreement between the caller and the callee on the locations to use - is guaranteed by our dynamic semantics for Cminor and RTL, which demand - that the signature of the call instruction is identical to that of the - called function. - - Calling conventions are largely arbitrary: they must respect the properties - proved in this section (such as no overlapping between the locations - of function arguments), but this leaves much liberty in choosing actual - locations. To ensure binary interoperability of code generated by our - compiler with libraries compiled by another PowerPC compiler, we - implement the standard conventions defined in the PowerPC/EABI - application binary interface. *) - -(** ** Location of function result *) - -(** The result value of a function is passed back to the caller in - registers [R3] or [F1] or [R3, R4], depending on the type of the returned value. - We treat a function without result as a function with one integer result. *) - -Definition loc_result (s: signature) : list mreg := - match s.(sig_res) with - | None => R3 :: nil - | Some (Tint | Tany32) => R3 :: nil - | Some (Tfloat | Tsingle | Tany64) => F1 :: nil - | Some Tlong => R3 :: R4 :: nil - end. - -(** The result registers have types compatible with that given in the signature. *) - -Lemma loc_result_type: - forall sig, - subtype_list (proj_sig_res' sig) (map mreg_type (loc_result sig)) = true. -Proof. - intros. unfold proj_sig_res', loc_result. destruct (sig_res sig) as [[]|]; auto. -Qed. - -(** The result locations are caller-save registers *) - -Lemma loc_result_caller_save: - forall (s: signature) (r: mreg), - In r (loc_result s) -> In r destroyed_at_call. -Proof. - intros. - assert (r = R3 \/ r = R4 \/ r = F1). - unfold loc_result in H. destruct (sig_res s); [destruct t|idtac]; simpl in H; intuition. - destruct H0 as [A | [A | A]]; subst r; simpl; OrEq. -Qed. - -(** ** Location of function arguments *) - -(** The PowerPC EABI states the following convention for passing arguments - to a function: -- The first 8 integer arguments are passed in registers [R3] to [R10]. -- The first 8 float arguments are passed in registers [F1] to [F8]. -- The first 4 long integer arguments are passed in register pairs [R3,R4] ... [R9,R10]. -- Extra arguments are passed on the stack, in [Outgoing] slots, consecutively - assigned (1 word for an integer argument, 2 words for a float), - starting at word offset 0. -- No stack space is reserved for the arguments that are passed in registers. -*) - -Definition int_param_regs := - R3 :: R4 :: R5 :: R6 :: R7 :: R8 :: R9 :: R10 :: nil. -Definition float_param_regs := - F1 :: F2 :: F3 :: F4 :: F5 :: F6 :: F7 :: F8 :: nil. - -Fixpoint loc_arguments_rec - (tyl: list typ) (ir fr ofs: Z) {struct tyl} : list loc := - match tyl with - | nil => nil - | (Tint | Tany32) as ty :: tys => - match list_nth_z int_param_regs ir with - | None => - S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 1) - | Some ireg => - R ireg :: loc_arguments_rec tys (ir + 1) fr ofs - end - | (Tfloat | Tsingle | Tany64) as ty :: tys => - match list_nth_z float_param_regs fr with - | None => - let ofs := align ofs 2 in - S Outgoing ofs ty :: loc_arguments_rec tys ir fr (ofs + 2) - | Some freg => - R freg :: loc_arguments_rec tys ir (fr + 1) ofs - end - | Tlong :: tys => - let ir := align ir 2 in - match list_nth_z int_param_regs ir, list_nth_z int_param_regs (ir + 1) with - | Some r1, Some r2 => - R r1 :: R r2 :: loc_arguments_rec tys (ir + 2) fr ofs - | _, _ => - let ofs := align ofs 2 in - S Outgoing ofs Tint :: S Outgoing (ofs + 1) Tint :: loc_arguments_rec tys ir fr (ofs + 2) - end - end. - -(** [loc_arguments s] returns the list of locations where to store arguments - when calling a function with signature [s]. *) - -Definition loc_arguments (s: signature) : list loc := - loc_arguments_rec s.(sig_args) 0 0 0. - -(** [size_arguments s] returns the number of [Outgoing] slots used - to call a function with signature [s]. *) - -Fixpoint size_arguments_rec (tyl: list typ) (ir fr ofs: Z) {struct tyl} : Z := - match tyl with - | nil => ofs - | (Tint | Tany32) :: tys => - match list_nth_z int_param_regs ir with - | None => size_arguments_rec tys ir fr (ofs + 1) - | Some ireg => size_arguments_rec tys (ir + 1) fr ofs - end - | (Tfloat | Tsingle | Tany64) :: tys => - match list_nth_z float_param_regs fr with - | None => size_arguments_rec tys ir fr (align ofs 2 + 2) - | Some freg => size_arguments_rec tys ir (fr + 1) ofs - end - | Tlong :: tys => - let ir := align ir 2 in - match list_nth_z int_param_regs ir, list_nth_z int_param_regs (ir + 1) with - | Some r1, Some r2 => size_arguments_rec tys (ir + 2) fr ofs - | _, _ => size_arguments_rec tys ir fr (align ofs 2 + 2) - end - end. - -Definition size_arguments (s: signature) : Z := - size_arguments_rec s.(sig_args) 0 0 0. - -(** A tail-call is possible for a signature if the corresponding - arguments are all passed in registers. *) - -Definition tailcall_possible (s: signature) : Prop := - forall l, In l (loc_arguments s) -> - match l with R _ => True | S _ _ _ => False end. - -(** Argument locations are either caller-save registers or [Outgoing] - stack slots at nonnegative offsets. *) - -Definition loc_argument_acceptable (l: loc) : Prop := - match l with - | R r => In r destroyed_at_call - | S Outgoing ofs ty => ofs >= 0 /\ ty <> Tlong - | _ => False - end. - -Remark loc_arguments_rec_charact: - forall tyl ir fr ofs l, - In l (loc_arguments_rec tyl ir fr ofs) -> - match l with - | R r => In r int_param_regs \/ In r float_param_regs - | S Outgoing ofs' ty => ofs' >= ofs /\ ty <> Tlong - | S _ _ _ => False - end. -Proof. -Opaque list_nth_z. - induction tyl; simpl loc_arguments_rec; intros. - elim H. - destruct a. -- (* int *) - destruct (list_nth_z int_param_regs ir) as [r|] eqn:E; destruct H. - subst. left. eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - subst. split. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* float *) - destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. - subst. right. eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - subst. split. apply Zle_ge. apply align_le. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. - assert (ofs <= align ofs 2) by (apply align_le; omega). - intuition omega. -- (* long *) - set (ir' := align ir 2) in *. - destruct (list_nth_z int_param_regs ir') as [r1|] eqn:E1. - destruct (list_nth_z int_param_regs (ir' + 1)) as [r2|] eqn:E2. - destruct H. subst; left; eapply list_nth_z_in; eauto. - destruct H. subst; left; eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct H. subst. split. omega. congruence. - destruct H. subst. split. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. - assert (ofs <= align ofs 2) by (apply align_le; omega). - destruct H. subst. split. omega. congruence. - destruct H. subst. split. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* single *) - destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. - subst. right. eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - subst. split. apply Zle_ge. apply align_le. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. - assert (ofs <= align ofs 2) by (apply align_le; omega). - intuition omega. -- (* any32 *) - destruct (list_nth_z int_param_regs ir) as [r|] eqn:E; destruct H. - subst. left. eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - subst. split. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. intuition omega. -- (* any64 *) - destruct (list_nth_z float_param_regs fr) as [r|] eqn:E; destruct H. - subst. right. eapply list_nth_z_in; eauto. - eapply IHtyl; eauto. - subst. split. apply Zle_ge. apply align_le. omega. congruence. - exploit IHtyl; eauto. destruct l; auto. destruct sl; auto. - assert (ofs <= align ofs 2) by (apply align_le; omega). - intuition omega. -Qed. - -Lemma loc_arguments_acceptable: - forall (s: signature) (l: loc), - In l (loc_arguments s) -> loc_argument_acceptable l. -Proof. - unfold loc_arguments; intros. - generalize (loc_arguments_rec_charact _ _ _ _ _ H). - destruct l. - intro H0; elim H0; simpl; ElimOrEq; OrEq. - destruct sl; try contradiction. simpl. intuition omega. -Qed. -Hint Resolve loc_arguments_acceptable: locs. - -(** The offsets of [Outgoing] arguments are below [size_arguments s]. *) - -Remark size_arguments_rec_above: - forall tyl ir fr ofs0, - ofs0 <= size_arguments_rec tyl ir fr ofs0. -Proof. - induction tyl; simpl; intros. - omega. - destruct a. - destruct (list_nth_z int_param_regs ir); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. - destruct (list_nth_z float_param_regs fr); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - set (ir' := align ir 2). - destruct (list_nth_z int_param_regs ir'); eauto. - destruct (list_nth_z int_param_regs (ir' + 1)); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - destruct (list_nth_z float_param_regs fr); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. - destruct (list_nth_z int_param_regs ir); eauto. apply Zle_trans with (ofs0 + 1); auto; omega. - destruct (list_nth_z float_param_regs fr); eauto. - apply Zle_trans with (align ofs0 2). apply align_le; omega. - apply Zle_trans with (align ofs0 2 + 2); auto; omega. -Qed. - -Lemma size_arguments_above: - forall s, size_arguments s >= 0. -Proof. - intros; unfold size_arguments. apply Zle_ge. - apply size_arguments_rec_above. -Qed. - -Lemma loc_arguments_bounded: - forall (s: signature) (ofs: Z) (ty: typ), - In (S Outgoing ofs ty) (loc_arguments s) -> - ofs + typesize ty <= size_arguments s. -Proof. - intros. - assert (forall tyl ir fr ofs0, - In (S Outgoing ofs ty) (loc_arguments_rec tyl ir fr ofs0) -> - ofs + typesize ty <= size_arguments_rec tyl ir fr ofs0). -{ - induction tyl; simpl; intros. - elim H0. - destruct a. -- (* int *) - destruct (list_nth_z int_param_regs ir); destruct H0. - congruence. - eauto. - inv H0. apply size_arguments_rec_above. - eauto. -- (* float *) - destruct (list_nth_z float_param_regs fr); destruct H0. - congruence. - eauto. - inv H0. apply size_arguments_rec_above. eauto. -- (* long *) - set (ir' := align ir 2) in *. - destruct (list_nth_z int_param_regs ir'). - destruct (list_nth_z int_param_regs (ir' + 1)). - destruct H0. congruence. destruct H0. congruence. eauto. - destruct H0. inv H0. - transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. - destruct H0. inv H0. - transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. - eauto. - destruct H0. inv H0. - transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. - destruct H0. inv H0. - transitivity (align ofs0 2 + 2). simpl; omega. eauto. apply size_arguments_rec_above. - eauto. -- (* single *) - destruct (list_nth_z float_param_regs fr); destruct H0. - congruence. - eauto. - inv H0. transitivity (align ofs0 2 + 2). simpl; omega. apply size_arguments_rec_above. - eauto. -- (* any32 *) - destruct (list_nth_z int_param_regs ir); destruct H0. - congruence. - eauto. - inv H0. apply size_arguments_rec_above. - eauto. -- (* any64 *) - destruct (list_nth_z float_param_regs fr); destruct H0. - congruence. - eauto. - inv H0. apply size_arguments_rec_above. eauto. - } - eauto. -Qed. diff --git a/powerpc/eabi/Stacklayout.v b/powerpc/eabi/Stacklayout.v deleted file mode 100644 index be823c1..0000000 --- a/powerpc/eabi/Stacklayout.v +++ /dev/null @@ -1,134 +0,0 @@ -(* *********************************************************************) -(* *) -(* 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. *) -(* *) -(* *********************************************************************) - -(** Machine- and ABI-dependent layout information for activation records. *) - -Require Import Coqlib. -Require Import Bounds. - -(** In the PowerPC/EABI application binary interface, - the general shape of activation records is as follows, - from bottom (lowest offsets) to top: -- 8 reserved bytes. The first 4 bytes hold the back pointer to the - activation record of the caller. The next 4 bytes are reserved - for called functions to store their return addresses. - Since we would rather store our return address in our own - frame, we will not use these 4 bytes, and just reserve them. -- Space for outgoing arguments to function calls. -- Local stack slots. -- Saved values of integer callee-save registers used by the function. -- Saved values of float callee-save registers used by the function. -- Space for the stack-allocated data declared in Cminor. - -The [frame_env] compilation environment records the positions of -the boundaries between areas in the frame part. -*) - -Definition fe_ofs_arg := 8. - -Record frame_env : Type := mk_frame_env { - fe_size: Z; - fe_ofs_link: Z; - fe_ofs_retaddr: Z; - fe_ofs_local: Z; - fe_ofs_int_callee_save: Z; - fe_num_int_callee_save: Z; - fe_ofs_float_callee_save: Z; - fe_num_float_callee_save: Z; - fe_stack_data: Z -}. - -(** Computation of the frame environment from the bounds of the current - function. *) - -Definition make_env (b: bounds) := - let ol := align (8 + 4 * b.(bound_outgoing)) 8 in (* locals *) - let ora := ol + 4 * b.(bound_local) in (* saved return address *) - let oics := ora + 4 in (* integer callee-saves *) - let oendi := oics + 4 * b.(bound_int_callee_save) in - let ofcs := align oendi 8 in (* float callee-saves *) - let ostkdata := ofcs + 8 * b.(bound_float_callee_save) in (* stack data *) - let sz := align (ostkdata + b.(bound_stack_data)) 16 in - mk_frame_env sz 0 ora - ol - oics b.(bound_int_callee_save) - ofcs b.(bound_float_callee_save) - ostkdata. - -(** Separation property *) - -Remark frame_env_separated: - forall b, - let fe := make_env b in - 0 <= fe.(fe_ofs_link) - /\ fe.(fe_ofs_link) + 4 <= fe_ofs_arg - /\ fe_ofs_arg + 4 * b.(bound_outgoing) <= fe.(fe_ofs_local) - /\ fe.(fe_ofs_local) + 4 * b.(bound_local) <= fe.(fe_ofs_retaddr) - /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_ofs_int_callee_save) - /\ fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save) <= fe.(fe_ofs_float_callee_save) - /\ fe.(fe_ofs_float_callee_save) + 8 * b.(bound_float_callee_save) <= fe.(fe_stack_data) - /\ fe.(fe_stack_data) + b.(bound_stack_data) <= fe.(fe_size) - /\ fe.(fe_ofs_retaddr) + 4 <= fe.(fe_size). -Proof. - intros. - generalize (align_le (8 + 4 * b.(bound_outgoing)) 8 (refl_equal _)). - generalize (align_le (fe.(fe_ofs_int_callee_save) + 4 * b.(bound_int_callee_save)) 8 (refl_equal _)). - generalize (align_le (fe.(fe_stack_data) + b.(bound_stack_data)) 16 (refl_equal _)). - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, - fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data, fe_ofs_arg. - intros. - generalize (bound_local_pos b); intro; - generalize (bound_int_callee_save_pos b); intro; - generalize (bound_float_callee_save_pos b); intro; - generalize (bound_outgoing_pos b); intro; - generalize (bound_stack_data_pos b); intro. - omega. -Qed. - -(** Alignment property *) - -Remark frame_env_aligned: - forall b, - let fe := make_env b in - (4 | fe.(fe_ofs_link)) - /\ (8 | fe.(fe_ofs_local)) - /\ (4 | fe.(fe_ofs_int_callee_save)) - /\ (8 | fe.(fe_ofs_float_callee_save)) - /\ (4 | fe.(fe_ofs_retaddr)) - /\ (8 | fe.(fe_stack_data)) - /\ (16 | fe.(fe_size)). -Proof. - intros. - unfold fe, make_env, fe_size, fe_ofs_link, fe_ofs_retaddr, - fe_ofs_local, fe_ofs_int_callee_save, - fe_num_int_callee_save, - fe_ofs_float_callee_save, fe_num_float_callee_save, - fe_stack_data. - set (x1 := align (8 + 4 * bound_outgoing b) 8). - assert (8 | x1). unfold x1; apply align_divides. omega. - set (x2 := x1 + 4 * bound_local b). - assert (4 | x2). unfold x2; apply Zdivide_plus_r; auto. - apply Zdivides_trans with 8. exists 2; auto. auto. - exists (bound_local b); ring. - set (x3 := x2 + 4). - assert (4 | x3). unfold x3; apply Zdivide_plus_r; auto. exists 1; auto. - set (x4 := align (x3 + 4 * bound_int_callee_save b) 8). - assert (8 | x4). unfold x4. apply align_divides. omega. - set (x5 := x4 + 8 * bound_float_callee_save b). - assert (8 | x5). unfold x5. apply Zdivide_plus_r; auto. exists (bound_float_callee_save b); ring. - set (x6 := align (x5 + bound_stack_data b) 16). - assert (16 | x6). unfold x6; apply align_divides. omega. - intuition. -Qed. -- cgit v1.2.3