Print this page
11972 resync smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/linearize.h
+++ new/usr/src/tools/smatch/src/linearize.h
1 1 #ifndef LINEARIZE_H
2 2 #define LINEARIZE_H
3 3
4 4 #include "lib.h"
5 5 #include "allocate.h"
6 6 #include "token.h"
7 +#include "opcode.h"
7 8 #include "parse.h"
8 9 #include "symbol.h"
10 +#include "ptrmap.h"
9 11
10 12 struct instruction;
11 -DECLARE_PTR_LIST(pseudo_ptr_list, pseudo_t);
12 13
13 14 struct pseudo_user {
14 15 struct instruction *insn;
15 16 pseudo_t *userp;
16 17 };
17 18
18 19 DECLARE_ALLOCATOR(pseudo_user);
19 20 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
21 +DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
20 22
21 23
22 24 enum pseudo_type {
23 25 PSEUDO_VOID,
26 + PSEUDO_UNDEF,
24 27 PSEUDO_REG,
25 28 PSEUDO_SYM,
26 29 PSEUDO_VAL,
27 30 PSEUDO_ARG,
28 31 PSEUDO_PHI,
29 32 };
30 33
31 34 struct pseudo {
32 35 int nr;
33 - int size:16; /* OP_SETVAL only */
34 - enum pseudo_type type:8;
36 + enum pseudo_type type;
35 37 struct pseudo_user_list *users;
36 38 struct ident *ident;
37 39 union {
38 40 struct symbol *sym;
39 41 struct instruction *def;
40 42 long long value;
41 43 };
42 44 void *priv;
43 45 };
44 46
45 47 extern struct pseudo void_pseudo;
46 48
47 49 #define VOID (&void_pseudo)
48 50
51 +static inline bool is_zero(pseudo_t pseudo)
52 +{
53 + return pseudo->type == PSEUDO_VAL && pseudo->value == 0;
54 +}
55 +
56 +static inline bool is_nonzero(pseudo_t pseudo)
57 +{
58 + return pseudo->type == PSEUDO_VAL && pseudo->value != 0;
59 +}
60 +
61 +
49 62 struct multijmp {
50 63 struct basic_block *target;
51 - int begin, end;
64 + long long begin, end;
52 65 };
53 66
54 67 struct asm_constraint {
55 68 pseudo_t pseudo;
56 69 const char *constraint;
57 70 const struct ident *ident;
58 71 };
59 72
60 73 DECLARE_ALLOCATOR(asm_constraint);
61 74 DECLARE_PTR_LIST(asm_constraint_list, struct asm_constraint);
62 75
63 76 struct asm_rules {
64 77 struct asm_constraint_list *inputs;
65 78 struct asm_constraint_list *outputs;
66 79 struct asm_constraint_list *clobbers;
67 80 };
68 81
69 82 DECLARE_ALLOCATOR(asm_rules);
70 83
71 84 struct instruction {
72 - unsigned opcode:8,
85 + unsigned opcode:7,
86 + tainted:1,
73 87 size:24;
74 88 struct basic_block *bb;
75 89 struct position pos;
76 90 struct symbol *type;
91 + pseudo_t target;
77 92 union {
78 - pseudo_t target;
79 - pseudo_t cond; /* for branch and switch */
80 - };
81 - union {
82 93 struct /* entrypoint */ {
83 94 struct pseudo_list *arg_list;
84 95 };
85 96 struct /* branch */ {
97 + pseudo_t cond;
86 98 struct basic_block *bb_true, *bb_false;
87 99 };
88 100 struct /* switch */ {
101 + pseudo_t _cond;
89 102 struct multijmp_list *multijmp_list;
90 103 };
91 104 struct /* phi_node */ {
105 + pseudo_t phi_var; // used for SSA conversion
92 106 struct pseudo_list *phi_list;
107 + unsigned int used:1;
93 108 };
94 109 struct /* phi source */ {
95 110 pseudo_t phi_src;
96 111 struct instruction_list *phi_users;
97 112 };
98 113 struct /* unops */ {
99 114 pseudo_t src;
100 115 struct symbol *orig_type; /* casts */
101 - unsigned int offset; /* memops */
102 116 };
117 + struct /* memops */ {
118 + pseudo_t addr; /* alias .src */
119 + unsigned int offset;
120 + unsigned int is_volatile:1;
121 + };
103 122 struct /* binops and sel */ {
104 123 pseudo_t src1, src2, src3;
105 124 };
106 125 struct /* slice */ {
107 126 pseudo_t base;
108 127 unsigned from, len;
109 128 };
110 129 struct /* setval */ {
111 - pseudo_t symbol; /* Subtle: same offset as "src" !! */
112 130 struct expression *val;
113 131 };
132 + struct /* setfval */ {
133 + long double fvalue;
134 + };
114 135 struct /* call */ {
115 136 pseudo_t func;
116 137 struct pseudo_list *arguments;
117 - struct symbol *fntype;
138 + struct symbol_list *fntypes;
118 139 };
119 140 struct /* context */ {
120 141 int increment;
121 142 int check;
122 143 struct expression *context_expr;
123 144 };
124 145 struct /* asm */ {
125 146 const char *string;
126 147 struct asm_rules *asm_rules;
127 148 };
128 149 };
129 150 };
130 151
131 -enum opcode {
132 - OP_BADOP,
133 -
134 - /* Entry */
135 - OP_ENTRY,
136 -
137 - /* Terminator */
138 - OP_TERMINATOR,
139 - OP_RET = OP_TERMINATOR,
140 - OP_BR,
141 - OP_CBR,
142 - OP_SWITCH,
143 - OP_INVOKE,
144 - OP_COMPUTEDGOTO,
145 - OP_UNWIND,
146 - OP_TERMINATOR_END = OP_UNWIND,
147 -
148 - /* Binary */
149 - OP_BINARY,
150 - OP_ADD = OP_BINARY,
151 - OP_SUB,
152 - OP_MULU, OP_MULS,
153 - OP_DIVU, OP_DIVS,
154 - OP_MODU, OP_MODS,
155 - OP_SHL,
156 - OP_LSR, OP_ASR,
157 -
158 - /* Logical */
159 - OP_AND,
160 - OP_OR,
161 - OP_XOR,
162 - OP_AND_BOOL,
163 - OP_OR_BOOL,
164 - OP_BINARY_END = OP_OR_BOOL,
165 -
166 - /* Binary comparison */
167 - OP_BINCMP,
168 - OP_SET_EQ = OP_BINCMP,
169 - OP_SET_NE,
170 - OP_SET_LE,
171 - OP_SET_GE,
172 - OP_SET_LT,
173 - OP_SET_GT,
174 - OP_SET_B,
175 - OP_SET_A,
176 - OP_SET_BE,
177 - OP_SET_AE,
178 - OP_BINCMP_END = OP_SET_AE,
179 -
180 - /* Uni */
181 - OP_NOT,
182 - OP_NEG,
183 -
184 - /* Select - three input values */
185 - OP_SEL,
186 -
187 - /* Memory */
188 - OP_MALLOC,
189 - OP_FREE,
190 - OP_ALLOCA,
191 - OP_LOAD,
192 - OP_STORE,
193 - OP_SETVAL,
194 - OP_SYMADDR,
195 - OP_GET_ELEMENT_PTR,
196 -
197 - /* Other */
198 - OP_PHI,
199 - OP_PHISOURCE,
200 - OP_CAST,
201 - OP_SCAST,
202 - OP_FPCAST,
203 - OP_PTRCAST,
204 - OP_INLINED_CALL,
205 - OP_CALL,
206 - OP_VANEXT,
207 - OP_VAARG,
208 - OP_SLICE,
209 - OP_SNOP,
210 - OP_LNOP,
211 - OP_NOP,
212 - OP_DEATHNOTE,
213 - OP_ASM,
214 -
215 - /* Sparse tagging (line numbers, context, whatever) */
216 - OP_CONTEXT,
217 - OP_RANGE,
218 -
219 - /* Needed to translate SSA back to normal form */
220 - OP_COPY,
221 -};
222 -
223 152 struct basic_block_list;
224 153 struct instruction_list;
225 154
226 155 struct basic_block {
227 156 struct position pos;
228 157 unsigned long generation;
229 - int context;
158 + union {
159 + int context;
160 + int postorder_nr; /* postorder number */
161 + int dom_level; /* level in the dominance tree */
162 + };
230 163 struct entrypoint *ep;
231 164 struct basic_block_list *parents; /* sources */
232 165 struct basic_block_list *children; /* destinations */
233 166 struct instruction_list *insns; /* Linear list of instructions */
167 + struct basic_block *idom; /* link to the immediate dominator */
168 + struct basic_block_list *doms; /* list of BB idominated by this one */
169 + struct phi_map *phi_map;
234 170 struct pseudo_list *needs, *defines;
235 171 union {
236 172 unsigned int nr; /* unique id for label's names */
237 173 void *priv;
238 174 };
239 175 };
240 176
241 177
178 +//
179 +// return the opcode of the instruction defining ``SRC`` if existing
180 +// and OP_BADOP if not. It also assigns the defining instruction
181 +// to ``DEF``.
182 +#define DEF_OPCODE(DEF, SRC) \
183 + (((SRC)->type == PSEUDO_REG && (DEF = (SRC)->def)) ? DEF->opcode : OP_BADOP)
184 +
185 +
242 186 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
243 187 {
244 188 add_ptr_list(list, bb);
245 189 }
246 190
247 191 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
248 192 {
249 193 add_ptr_list(list, insn);
250 194 }
251 195
252 196 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
253 197 {
254 198 add_ptr_list(list, multijmp);
255 199 }
256 200
|
↓ open down ↓ |
5 lines elided |
↑ open up ↑ |
257 201 static inline pseudo_t *add_pseudo(struct pseudo_list **list, pseudo_t pseudo)
258 202 {
259 203 return add_ptr_list(list, pseudo);
260 204 }
261 205
262 206 static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
263 207 {
264 208 return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
265 209 }
266 210
211 +static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
212 +{
213 + return lookup_ptr_list_entry((struct ptr_list *)list, pseudo);
214 +}
215 +
267 216 static inline int bb_terminated(struct basic_block *bb)
268 217 {
269 218 struct instruction *insn;
270 219 if (!bb)
271 220 return 0;
272 221 insn = last_instruction(bb->insns);
273 222 return insn && insn->opcode >= OP_TERMINATOR
274 223 && insn->opcode <= OP_TERMINATOR_END;
275 224 }
276 225
277 226 static inline int bb_reachable(struct basic_block *bb)
278 227 {
279 228 return bb != NULL;
280 229 }
281 230
282 -static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list)
231 +static inline int lookup_bb(struct basic_block_list *list, struct basic_block *bb)
283 232 {
284 - add_ptr_list(list, ptr);
233 + return lookup_ptr_list_entry((struct ptr_list *)list, bb);
285 234 }
286 235
236 +
287 237 static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_user_list **list)
288 238 {
289 239 add_ptr_list(list, user);
290 240 }
291 241
292 242 static inline int has_use_list(pseudo_t p)
293 243 {
294 - return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
244 + return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL);
295 245 }
296 246
247 +static inline int pseudo_user_list_size(struct pseudo_user_list *list)
248 +{
249 + return ptr_list_size((struct ptr_list *)list);
250 +}
251 +
252 +static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
253 +{
254 + return ptr_list_empty((struct ptr_list *)list);
255 +}
256 +
257 +static inline int has_users(pseudo_t p)
258 +{
259 + return !pseudo_user_list_empty(p->users);
260 +}
261 +
262 +static inline bool multi_users(pseudo_t p)
263 +{
264 + return ptr_list_multiple((struct ptr_list *)(p->users));
265 +}
266 +
267 +static inline int nbr_users(pseudo_t p)
268 +{
269 + return pseudo_user_list_size(p->users);
270 +}
271 +
297 272 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
298 273 {
299 274 struct pseudo_user *user = __alloc_pseudo_user(0);
300 275 user->userp = pp;
301 276 user->insn = insn;
302 277 return user;
303 278 }
304 279
305 280 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
306 281 {
307 282 *pp = p;
308 283 if (has_use_list(p))
309 284 add_pseudo_user_ptr(alloc_pseudo_user(insn, pp), &p->users);
310 285 }
311 286
312 287 static inline void remove_bb_from_list(struct basic_block_list **list, struct basic_block *entry, int count)
313 288 {
314 289 delete_ptr_list_entry((struct ptr_list **)list, entry, count);
315 290 }
316 291
317 292 static inline void replace_bb_in_list(struct basic_block_list **list,
318 293 struct basic_block *old, struct basic_block *new, int count)
319 294 {
|
↓ open down ↓ |
13 lines elided |
↑ open up ↑ |
320 295 replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
321 296 }
322 297
323 298 struct entrypoint {
324 299 struct symbol *name;
325 300 struct symbol_list *syms;
326 301 struct pseudo_list *accesses;
327 302 struct basic_block_list *bbs;
328 303 struct basic_block *active;
329 304 struct instruction *entry;
305 + unsigned int dom_levels; /* max levels in the dom tree */
330 306 };
331 307
332 308 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
333 309 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
334 310
335 -pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
311 +struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
312 +struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
313 +struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var);
314 +void add_phi_node(struct basic_block *bb, struct instruction *phi_node);
315 +
316 +pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
336 317 pseudo_t alloc_pseudo(struct instruction *def);
337 -pseudo_t value_pseudo(struct symbol *type, long long val);
338 -unsigned int value_size(long long value);
318 +pseudo_t value_pseudo(long long val);
319 +pseudo_t undef_pseudo(void);
339 320
340 321 struct entrypoint *linearize_symbol(struct symbol *sym);
341 322 int unssa(struct entrypoint *ep);
342 323 void show_entry(struct entrypoint *ep);
343 324 const char *show_pseudo(pseudo_t pseudo);
344 325 void show_bb(struct basic_block *bb);
345 326 const char *show_instruction(struct instruction *insn);
327 +const char *show_label(struct basic_block *bb);
346 328
347 329 #endif /* LINEARIZE_H */
348 330
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX