1 (* Copyright (C) 2003-2005, HELM Team.
3 * This file is part of HELM, an Hypertextual, Electronic
4 * Library of Mathematics, developed at the Computer Science
5 * Department, University of Bologna, Italy.
7 * HELM is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
12 * HELM is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with HELM; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
26 module UM = UriManager
30 module E = CicEnvironment
31 module S = CicSubstitution
32 module DTI = DoubleTypeInference
34 module PEH = ProofEngineHelpers
35 module TC = CicTypeChecker
40 module H = ProceduralHelpers
41 module Cl = ProceduralClassify
43 (* debugging ****************************************************************)
47 (* term optimization ********************************************************)
49 let critical = ref true
56 let info st str = {st with info = st.info ^ str ^ "\n"}
58 let defined_premise = "LOCAL"
61 let name = C.Name defined_premise in
62 let ty = H.get_type "define" c v in
63 C.LetIn (name, v, ty, C.Rel 1)
66 let rec aux k n = function
67 | C.Lambda (s, v, t) when k > 0 ->
68 C.Lambda (s, v, aux (pred k) n t)
69 | C.Lambda (_, _, t) when n > 0 ->
70 aux 0 (pred n) (S.lift (-1) t)
72 Printf.eprintf "PO.clear_absts: %u %s\n" n (Pp.ppterm t);
78 let rec add_abst k = function
79 | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
80 | t when k > 0 -> assert false
81 | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
83 let rec opt_letin g st es c name v w t =
84 let name = H.mk_fresh_name true c name in
85 let entry = Some (name, C.Def (v, w)) in
87 if DTI.does_not_occur 1 t then
88 let x = S.lift (-1) t in
89 opt_proof g (info st "Optimizer: remove 1") true c x
92 | C.LetIn (nname, vv, ww, tt) when H.is_proof c v ->
93 let eentry = Some (nname, C.Def (vv, ww)) in
94 let ttw = H.get_type "opt_letin 1" (eentry :: c) tt in
95 let x = C.LetIn (nname, vv, ww,
96 C.LetIn (name, tt, ttw, S.lift_from 2 1 t))
98 opt_proof g (info st "Optimizer: swap 1") true c x
99 | v when H.is_proof c v && H.is_atomic v ->
100 let x = S.subst v t in
101 opt_proof g (info st "Optimizer: remove 5") true c x
102 (* | v when t = C.Rel 1 ->
103 g (info st "Optimizer: remove 6") v
105 g st (C.LetIn (name, v, w, t))
107 if es then opt_term g st es c v else g st v
109 if es then opt_proof g st es (entry :: c) t else g st t
111 and opt_lambda g st es c name w t =
112 let name = H.mk_fresh_name true c name in
113 let entry = Some (name, C.Decl w) in
114 let g st t = g st (C.Lambda (name, w, t)) in
115 if es then opt_proof g st es (entry :: c) t else g st t
117 and opt_appl g st es c t vs =
120 | C.LetIn (mame, vv, tyty, tt) ->
121 let vs = List.map (S.lift 1) vs in
122 let x = C.LetIn (mame, vv, tyty, C.Appl (tt :: vs)) in
123 opt_proof g (info st "Optimizer: swap 2") true c x
124 | C.Lambda (name, ww, tt) ->
125 let v, vs = List.hd vs, List.tl vs in
126 let w = H.get_type "opt_appl 1" c v in
127 let x = C.Appl (C.LetIn (name, v, w, tt) :: vs) in
128 opt_proof g (info st "Optimizer: remove 2") true c x
130 let x = C.Appl (vvs @ vs) in
131 opt_proof g (info st "Optimizer: nested application") true c x
134 let rec aux st d rvs = function
136 let x = C.Appl (t :: List.rev rvs) in
137 if d then opt_proof g st true c x else g st x
138 | v :: vs, (cc, bb) :: cs ->
139 if H.is_not_atomic v && I.S.mem 0 cc && bb then
140 aux (st info "Optimizer: anticipate 1") true
141 (define c v :: rvs) (vs, cs)
143 aux st d (v :: rvs) (vs, cs)
144 | _, [] -> assert false
148 let classes, conclusion = Cl.classify c (H.get_type "opt_appl 3" c t) in
149 let csno, vsno = List.length classes, List.length vs in
151 let vvs, vs = HEL.split_nth csno vs in
152 let x = C.Appl (define c (C.Appl (t :: vvs)) :: vs) in
153 opt_proof g (info st "Optimizer: anticipate 2") true c x
154 else match conclusion, List.rev vs with
155 | Some _, rv :: rvs when csno = vsno && H.is_not_atomic rv ->
156 let x = C.Appl (t :: List.rev rvs @ [define c rv]) in
157 opt_proof g (info st "Optimizer: anticipate 3";) true c x
158 | _ (* Some _, _ *) ->
159 g st (C.Appl (t :: vs))
161 aux false [] (vs, classes)
163 let rec aux h st prev = function
164 | C.LetIn (name, vv, tyty, tt) :: vs ->
165 let t = S.lift 1 t in
166 let prev = List.map (S.lift 1) prev in
167 let vs = List.map (S.lift 1) vs in
168 let y = C.Appl (t :: List.rev prev @ tt :: vs) in
169 let ww = H.get_type "opt_appl 2" c vv in
170 let x = C.LetIn (name, vv, ww, y) in
171 opt_proof g (info st "Optimizer: swap 3") true c x
172 | v :: vs -> aux h st (v :: prev) vs
177 if es then opt_proof g st es c t else g st t
179 let map h v (st, vs) =
180 let h st vv = h (st, vv :: vs) in opt_term h st es c v
182 if es then H.list_fold_right_cps g map vs (st, []) else g (st, vs)
184 and opt_mutcase_critical g st es c uri tyno outty arg cases =
185 let eliminator = H.get_default_eliminator c uri tyno outty in
186 let lpsno, (_, _, _, constructors) = H.get_ind_type uri tyno in
187 let ps, sort_disp = H.get_ind_parameters c arg in
188 let lps, rps = HEL.split_nth lpsno ps in
189 let rpsno = List.length rps in
190 if rpsno = 0 && sort_disp = 0 then
191 (* FG: the transformation is not possible, we fall back into the plain case *)
192 opt_mutcase_plain g st es c uri tyno outty arg cases
194 let predicate = clear_absts rpsno (1 - sort_disp) outty in
196 I.S.mem tyno (I.get_mutinds_of_uri uri t)
198 let map2 case (_, cty) =
199 let map (h, case, k) (_, premise) =
200 if h > 0 then pred h, case, k else
201 if is_recursive premise then
202 0, add_abst k case, k + 2
206 let premises, _ = PEH.split_with_whd (c, cty) in
207 let _, lifted_case, _ =
208 List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
212 let lifted_cases = List.map2 map2 cases constructors in
213 let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
214 let x = H.refine c (C.Appl args) in
215 opt_proof g (info st "Optimizer: remove 3") es c x
217 and opt_mutcase_plain g st es c uri tyno outty arg cases =
219 let g (st, ts) = g st (C.MutCase (uri, tyno, outty, v, ts)) in
220 let map h v (st, vs) =
221 let h st vv = h (st, vv :: vs) in opt_proof h st es c v
223 if es then H.list_fold_right_cps g map cases (st, []) else g (st, cases)
225 if es then opt_proof g st es c arg else g st arg
228 if !critical then opt_mutcase_critical g else opt_mutcase_plain g
230 and opt_cast g st es c t w =
231 let g st t = g (info st "Optimizer: remove 4") t in
232 if es then opt_proof g st es c t else g st t
234 and opt_other g st es c t = g st t
236 and opt_proof g st es c = function
237 | C.LetIn (name, v, ty, t) -> opt_letin g st es c name v ty t
238 | C.Lambda (name, w, t) -> opt_lambda g st es c name w t
239 | C.Appl (t :: v :: vs) -> opt_appl g st es c t (v :: vs)
240 | C.Appl [t] -> opt_proof g st es c t
241 | C.MutCase (u, n, t, v, ws) -> opt_mutcase g st es c u n t v ws
242 | C.Cast (t, w) -> opt_cast g st es c t w
243 | t -> opt_other g st es c t
245 and opt_term g st es c t =
246 if H.is_proof c t then opt_proof g st es c t else g st t
248 (* object optimization ******************************************************)
251 try opt_term g st true c bo
253 | E.Object_not_found uri ->
254 let msg = "optimize_obj: object not found: " ^ UM.string_of_uri uri in
257 let msg = "optimize_obj: " ^ Printexc.to_string e in
260 let optimize_obj = function
261 | C.Constant (name, Some bo, ty, pars, attrs) ->
262 let count_nodes = I.count_nodes ~meta:false 0 in
263 let st, c = {info = ""; dummy = ()}, [] in
264 L.time_stamp ("PO: OPTIMIZING " ^ name);
265 let nodes = Printf.sprintf "Initial nodes: %u" (count_nodes bo) in
267 Printf.eprintf "BEGIN: %s\n" name;
268 Printf.eprintf "Initial : %s\n" (Pp.ppterm bo);
269 prerr_string "Ut.pp_term : ";
270 Ut.pp_term prerr_string [] c bo; prerr_newline ()
272 let bo, ty = H.cic_bc c bo, H.cic_bc c ty in
275 Printf.eprintf "Optimized : %s\n" (Pp.ppterm bo);
276 prerr_string "Ut.pp_term : ";
277 Ut.pp_term prerr_string [] c bo; prerr_newline ()
279 (* let _ = H.get_type "opt" [] (C.Cast (bo, ty)) in *)
280 let nodes = Printf.sprintf "Optimized nodes: %u" (count_nodes bo) in
281 let st = info st nodes in
282 L.time_stamp ("PO: DONE " ^ name);
283 C.Constant (name, Some bo, ty, pars, attrs), st.info
285 wrap g (info st nodes) c bo
288 let optimize_term c bo =
289 let st = {info = ""; dummy = ()} in
290 let bo = H.cic_bc c bo in
291 let g st bo = bo, st.info in