source: Deliverables/D2.2/8051/src/ASM/ASMCosts.ml @ 632

Last change on this file since 632 was 632, checked in by ayache, 10 years ago

Small change in ASMCosts.

File size: 4.4 KB
Line 
1
2let error_prefix = "ASMCosts"
3let warning s = prerr_endline (error_prefix ^ s)
4
5
6type instruction_nature =
7  | Goto of BitVectors.word | Branch of BitVectors.word
8  | Direct_fun_call of BitVectors.word | Return
9  | Other
10
11let inst_nature pc = function
12  | `LCALL (`ADDR16 addr16) -> Direct_fun_call addr16
13  | `ACALL (`ADDR11 addr11) ->
14    Direct_fun_call (Physical.addr16_of_addr11 pc addr11)
15  | `LJMP (`ADDR16 addr16) -> Goto addr16
16  | `AJMP (`ADDR11 addr11) -> Goto (Physical.addr16_of_addr11 pc addr11)
17  | `SJMP (`REL addr) ->
18      let _, addr = BitVectors.half_add pc (BitVectors.sign_extension addr) in
19       Goto addr
20  | `JMP idptr -> Other (* Indirect jump; precondition: every possible
21                           destination should start with its own label *)
22  | `JC addr
23  | `JNC addr
24  | `JB (_,addr)
25  | `JNB (_,addr)
26  | `JBC (_,addr)
27  | `JZ addr
28  | `JNZ addr
29  | `CJNE (_,addr)
30  | `DJNZ (_,addr) ->
31      let `REL addr = addr in
32      let _, addr = BitVectors.half_add pc (BitVectors.sign_extension addr) in
33       Branch addr
34  | `RET | `RETI -> Return
35  | _ -> Other
36
37
38let treat mem costs pc =
39  let (inst, next_pc, inst_cost) = ASMInterpret.fetch mem pc in
40(*
41  (* <DEBUG> *)
42  Printf.printf "%s%s: %s\n%!"
43    (if BitVectors.WordMap.mem pc costs then
44        BitVectors.WordMap.find pc costs ^ ": "
45     else "")
46    (BitVectors.string_of_vect pc)
47    (Pretty.pp_instruction inst) ;
48  (* </DEBUG> *)
49*)
50  let next_pcs = match inst_nature pc inst with
51    | Return -> []
52    | Goto pc -> [pc]
53    | Branch pc2 ->
54      [next_pc ; pc2]
55    | Direct_fun_call _ | Other -> [next_pc] in
56  (inst_cost, next_pcs)
57
58let compare pc1 cost1 pc2 cost2 =
59  if cost1 <> cost2 then
60    warning
61      (Printf.sprintf
62         "Warning: branching to %s has cost %d, branching to %s has cost %d"
63         "*fixme*" (* pc1 *) cost1 "*fixme*" (* pc2 *) cost2) ;
64  max cost1 cost2
65
66let block_cost mem costs pc =
67  let treat = treat mem costs in
68  let rec aux = function
69    | [] -> 0
70    | [pc] when BitVectors.WordMap.mem pc costs -> 0
71    | [pc] -> full_cost pc
72    | [pc1 ; pc2] when BitVectors.WordMap.mem pc1 costs &&
73                       BitVectors.WordMap.mem pc2 costs -> 0
74    | [pc1 ; pc2] when BitVectors.WordMap.mem pc1 costs ->
75      let cost2 = full_cost pc2 in
76      compare pc1 0 pc2 cost2
77    | [pc1 ; pc2] when BitVectors.WordMap.mem pc2 costs ->
78      let cost1 = full_cost pc1 in
79      compare pc1 cost1 pc2 0
80    | [pc1 ; pc2] ->
81      let cost1 = full_cost pc1 in
82      let cost2 = full_cost pc2 in
83      compare pc1 cost1 pc2 cost2
84    | _ -> assert false (* should be impossible: only 0, 1 or 2 following pcs *)
85  and full_cost pc =
86    let (cost, next_pcs) = treat pc in
87    cost + (aux next_pcs) in
88  full_cost pc
89
90
91let traverse_code mem p =
92  let rec aux pc code =
93    let inst,newpc,_ = ASMInterpret.fetch mem pc in
94(*
95    (* <DEBUG> *)
96    Printf.printf "Traversing %s: %s\n%!"
97      (BitVectors.string_of_vect pc) (Pretty.pp_instruction inst) ;
98    (* </DEBUG> *)
99*)
100    match code with
101      | [] -> CostLabel.Map.empty
102      | _::tl when BitVectors.WordMap.mem pc p.ASM.cost_labels ->
103        let lbl = BitVectors.WordMap.find pc p.ASM.cost_labels in
104        let cost = block_cost mem p.ASM.cost_labels pc in
105        let costs_mapping = aux newpc tl in
106        CostLabel.Map.add lbl cost costs_mapping
107      | _::tl -> aux newpc tl
108  in
109  aux (BitVectors.zero `Sixteen) p.ASM.code
110
111
112let first_cost_label mem costs =
113  let rec aux oldpc =
114    if BitVectors.WordMap.mem oldpc costs then
115      (BitVectors.WordMap.find oldpc costs, 0)
116    else
117      let (inst, pc, inst_cost) = ASMInterpret.fetch mem oldpc in
118      match inst_nature oldpc inst with
119        | Direct_fun_call pc ->
120          let (lbl, cost) = aux pc in
121          (lbl, inst_cost + cost)
122        | Return
123        | Goto _
124        | Branch _ ->
125          assert false (* no such instructions before calling main *)
126        | Other ->
127          let (lbl, cost) = aux pc in
128          (lbl, inst_cost + cost)
129  in
130  aux (BitVectors.zero `Sixteen)
131
132
133let initialize_cost mem costs costs_mapping =
134  let (lbl, cost) = first_cost_label mem costs in
135  let old_cost =
136    if CostLabel.Map.mem lbl costs_mapping then
137      CostLabel.Map.find lbl costs_mapping
138    else 0 in
139  let new_cost = old_cost + cost in
140  CostLabel.Map.add lbl new_cost costs_mapping
141
142
143let compute p =
144(*
145  (* <DEBUG> *)
146  Printf.printf "%s\n\n%!" (Pretty.print_program p) ;
147  (* </DEBUG> *)
148*)
149  let mem = ASMInterpret.load_code_memory p.ASM.code in
150  let costs_mapping = traverse_code mem p in
151  if p.ASM.has_main then initialize_cost mem p.ASM.cost_labels costs_mapping
152  else costs_mapping
Note: See TracBrowser for help on using the repository browser.