1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
(* *********************************************************************)
(* *)
(* 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. *)
(* *)
(* *********************************************************************)
open LTL
open Maps
let debug_flag = ref false
let debug fmt =
if !debug_flag then Printf.eprintf fmt
else Printf.ifprintf stderr fmt
(* Trivial enumeration, in decreasing order of PC *)
(***
let enumerate_aux f reach =
positive_rec
Coq_nil
(fun pc nodes ->
if PMap.get pc reach
then Coq_cons (pc, nodes)
else nodes)
f.fn_nextpc
***)
(* More clever enumeration that flattens basic blocks *)
open Camlcoq
module IntSet = Set.Make(struct type t = int let compare = compare end)
(* Determine join points: reachable nodes that have > 1 predecessor *)
let join_points f =
let reached = ref IntSet.empty in
let reached_twice = ref IntSet.empty in
let rec traverse pc =
let npc = P.to_int pc in
if IntSet.mem npc !reached then begin
if not (IntSet.mem npc !reached_twice) then
reached_twice := IntSet.add npc !reached_twice
end else begin
reached := IntSet.add npc !reached;
match PTree.get pc f.fn_code with
| None -> ()
| Some b -> traverse_succs (successors_block b)
end
and traverse_succs = function
| [] -> ()
| [pc] -> traverse pc
| pc :: l -> traverse pc; traverse_succs l
in traverse f.fn_entrypoint; !reached_twice
(* Cut into reachable basic blocks, annotated with the min value of the PC *)
let basic_blocks f joins =
let blocks = ref [] in
let visited = ref IntSet.empty in
(* start_block:
pc is the function entry point
or a join point
or the successor of a conditional test *)
let rec start_block pc =
let npc = P.to_int pc in
if not (IntSet.mem npc !visited) then begin
visited := IntSet.add npc !visited;
in_block [] max_int pc
end
(* in_block: add pc to block and check successors *)
and in_block blk minpc pc =
let npc = P.to_int pc in
let blk = pc :: blk in
let minpc = min npc minpc in
match PTree.get pc f.fn_code with
| None -> assert false
| Some b ->
let rec do_instr_list = function
| [] -> assert false
| Lbranch s :: _ -> next_in_block blk minpc s
| Ltailcall (sig0, ros) :: _ -> end_block blk minpc
| Lcond (cond, args, ifso, ifnot, _) :: _ ->
end_block blk minpc; start_block ifso; start_block ifnot
| Ljumptable(arg, tbl) :: _ ->
end_block blk minpc; List.iter start_block tbl
| Lreturn :: _ -> end_block blk minpc
| instr :: b' -> do_instr_list b' in
do_instr_list b
(* next_in_block: check if join point and either extend block
or start block *)
and next_in_block blk minpc pc =
let npc = P.to_int pc in
if IntSet.mem npc joins
then (end_block blk minpc; start_block pc)
else in_block blk minpc pc
(* end_block: record block that we just discovered *)
and end_block blk minpc =
blocks := (minpc, List.rev blk) :: !blocks
in
start_block f.fn_entrypoint; !blocks
(* Flatten basic blocks in decreasing order of minpc *)
let flatten_blocks blks =
let cmp_minpc (mpc1, _) (mpc2, _) =
if mpc1 = mpc2 then 0 else if mpc1 > mpc2 then -1 else 1
in
List.flatten (List.map snd (List.sort cmp_minpc blks))
(* Build the enumeration *)
let enumerate_aux_flat f reach =
flatten_blocks (basic_blocks f (join_points f))
(**
* Alternate enumeration based on traces as identified by Duplicate.v
*
* This is a slight alteration to the above heuristic, ensuring that any
* superblock will be contiguous in memory, while still following the original
* heuristic
*
* Slight change: instead of taking the minimum pc of the superblock, we just take
* the pc of the first block.
* (experimentally this leads to slightly better performance..)
*)
let super_blocks f joins =
let blocks = ref [] in
let visited = ref IntSet.empty in
(* start_block:
pc is the function entry point
or a join point
or the successor of a conditional test *)
let rec start_block pc =
let npc = P.to_int pc in
if not (IntSet.mem npc !visited) then begin
visited := IntSet.add npc !visited;
in_block [] npc pc
end
(* in_block: add pc to block and check successors *)
and in_block blk minpc pc =
let blk = pc :: blk in
match PTree.get pc f.fn_code with
| None -> assert false
| Some b ->
let rec do_instr_list = function
| [] -> assert false
| Lbranch s :: _ -> next_in_block blk minpc s
| Ltailcall (sig0, ros) :: _ -> end_block blk minpc
| Lcond (cond, args, ifso, ifnot, pred) :: _ -> begin
match pred with
| None -> (end_block blk minpc; start_block ifso; start_block ifnot)
| Some true -> (next_in_block blk minpc ifso; start_block ifnot)
| Some false -> (next_in_block blk minpc ifnot; start_block ifso)
end
| Ljumptable(arg, tbl) :: _ ->
end_block blk minpc; List.iter start_block tbl
| Lreturn :: _ -> end_block blk minpc
| instr :: b' -> do_instr_list b' in
do_instr_list b
(* next_in_block: check if join point and either extend block
or start block *)
and next_in_block blk minpc pc =
let npc = P.to_int pc in
if IntSet.mem npc joins
then (end_block blk minpc; start_block pc)
else in_block blk minpc pc
(* end_block: record block that we just discovered *)
and end_block blk minpc =
blocks := (minpc, List.rev blk) :: !blocks
in
start_block f.fn_entrypoint; !blocks
(* Build the enumeration *)
let enumerate_aux_sb f reach =
flatten_blocks (super_blocks f (join_points f))
let enumerate_aux f reach =
if !Clflags.option_ftracelinearize then enumerate_aux_sb f reach
else enumerate_aux_flat f reach
|
