?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Rename asm-volatile to better describe what it tests
[smatch.git] / dissect.c
blob9dc3df9408be901da6a69eea740bccd8047ea335
1 /*
2 * sparse/dissect.c
3 *
4 * Started by Oleg Nesterov <oleg@tv-sign.ru>
5 *
6 * Licensed under the Open Software License version 1.1
7 */
8
9 #include "dissect.h"
10
11 #define U_VOID 0x00
12 #define U_SELF ((1 << U_SHIFT) - 1)
13 #define U_MASK (U_R_VAL | U_W_VAL | U_R_AOF)
14
15 #define DO_LIST(l__, p__, expr__) \
16 do { \
17 typeof(l__->list[0]) p__; \
18 FOR_EACH_PTR(l__, p__) \
19 expr__; \
20 END_FOR_EACH_PTR(p__); \
21 } while (0)
22
23 #define DO_2_LIST(l1__,l2__, p1__,p2__, expr__) \
24 do { \
25 typeof(l1__->list[0]) p1__; \
26 typeof(l2__->list[0]) p2__; \
27 PREPARE_PTR_LIST(l1__, p1__); \
28 FOR_EACH_PTR(l2__, p2__) \
29 expr__; \
30 NEXT_PTR_LIST(p1__); \
31 END_FOR_EACH_PTR(p2__); \
32 FINISH_PTR_LIST(p1__); \
33 } while (0)
34
35
36 typedef unsigned usage_t;
37
38 static struct reporter *reporter;
39 static struct symbol *return_type;
40
41 static void do_sym_list(struct symbol_list *list);
42
43 static struct symbol
44 *base_type(struct symbol *sym),
45 *do_initializer(struct symbol *type, struct expression *expr),
46 *do_expression(usage_t mode, struct expression *expr),
47 *do_statement(usage_t mode, struct statement *stmt);
48
49 static inline int is_ptr(struct symbol *type)
50 {
51 return type->type == SYM_PTR || type->type == SYM_ARRAY;
52 }
53
54 static inline usage_t u_rval(usage_t mode)
55 {
56 return mode & (U_R_VAL | (U_MASK << U_SHIFT))
57 ? U_R_VAL : 0;
58 }
59
60 static inline usage_t u_addr(usage_t mode)
61 {
62 return mode = mode & U_MASK
63 ? U_R_AOF | (mode & U_W_AOF) : 0;
64 }
65
66 static usage_t u_lval(struct symbol *type)
67 {
68 int wptr = is_ptr(type) && !(type->ctype.modifiers & MOD_CONST);
69 return wptr || type == &bad_ctype
70 ? U_W_AOF | U_R_VAL : U_R_VAL;
71 }
72
73 static usage_t fix_mode(struct symbol *type, usage_t mode)
74 {
75 mode &= (U_SELF | (U_SELF << U_SHIFT));
76
77 switch (type->type) {
78 case SYM_BASETYPE:
79 if (!type->ctype.base_type)
80 break;
81 case SYM_ENUM:
82 case SYM_BITFIELD:
83 if (mode & U_MASK)
84 mode &= U_SELF;
85 default:
86
87 break; case SYM_FN:
88 if (mode & U_R_VAL)
89 mode |= U_R_AOF;
90 mode &= ~(U_R_VAL | U_W_AOF);
91
92 break; case SYM_ARRAY:
93 if (mode & (U_MASK << U_SHIFT))
94 mode >>= U_SHIFT;
95 else if (mode != U_W_VAL)
96 mode = u_addr(mode);
97 }
98
99 if (!(mode & U_R_AOF))
100 mode &= ~U_W_AOF;
101
102 return mode;
103 }
104
105 static inline struct symbol *no_member(struct ident *name)
106 {
107 static struct symbol sym = {
108 .type = SYM_BAD,
109 };
110
111 sym.ctype.base_type = &bad_ctype;
112 sym.ident = name;
113
114 return &sym;
115 }
116
117 static struct symbol *report_member(mode_t mode, struct position *pos,
118 struct symbol *type, struct symbol *mem)
119 {
120 struct symbol *ret = mem->ctype.base_type;
121
122 if (reporter->r_member)
123 reporter->r_member(fix_mode(ret, mode), pos, type, mem);
124
125 return ret;
126 }
127
128 static void report_implicit(usage_t mode, struct position *pos, struct symbol *type)
129 {
130 if (type->type != SYM_STRUCT && type->type != SYM_UNION)
131 return;
132
133 if (!reporter->r_member)
134 return;
135
136 if (type->ident != NULL)
137 reporter->r_member(mode, pos, type, NULL);
138
139 DO_LIST(type->symbol_list, mem,
140 report_implicit(mode, pos, base_type(mem)));
141 }
142
143 static inline struct symbol *expr_symbol(struct expression *expr)
144 {
145 struct symbol *sym = expr->symbol;
146
147 if (!sym) {
148 sym = lookup_symbol(expr->symbol_name, NS_SYMBOL);
149
150 if (!sym) {
151 sym = alloc_symbol(expr->pos, SYM_BAD);
152 bind_symbol(sym, expr->symbol_name, NS_SYMBOL);
153 sym->ctype.modifiers = MOD_EXTERN;
154 }
155 }
156
157 if (!sym->ctype.base_type)
158 sym->ctype.base_type = &bad_ctype;
159
160 return sym;
161 }
162
163 static struct symbol *report_symbol(usage_t mode, struct expression *expr)
164 {
165 struct symbol *sym = expr_symbol(expr);
166 struct symbol *ret = base_type(sym);
167
168 if (0 && ret->type == SYM_ENUM)
169 return report_member(mode, &expr->pos, ret, expr->symbol);
170
171 if (reporter->r_symbol)
172 reporter->r_symbol(fix_mode(ret, mode), &expr->pos, sym);
173
174 return ret;
175 }
176
177 static inline struct ident *mk_name(struct ident *root, struct ident *node)
178 {
179 char name[256];
180
181 snprintf(name, sizeof(name), "%.*s:%.*s",
182 root ? root->len : 0, root ? root->name : "",
183 node ? node->len : 0, node ? node->name : "");
184
185 return built_in_ident(name);
186 }
187
188 static void examine_sym_node(struct symbol *node, struct ident *root)
189 {
190 struct symbol *base;
191 struct ident *name;
192
193 if (node->examined)
194 return;
195
196 node->examined = 1;
197 name = node->ident;
198
199 while ((base = node->ctype.base_type) != NULL)
200 switch (base->type) {
201 case SYM_TYPEOF:
202 node->ctype.base_type =
203 do_expression(U_VOID, base->initializer);
204 break;
205
206 case SYM_ARRAY:
207 do_expression(U_R_VAL, base->array_size);
208 case SYM_PTR: case SYM_FN:
209 node = base;
210 break;
211
212 case SYM_STRUCT: case SYM_UNION: //case SYM_ENUM:
213 if (base->evaluated)
214 return;
215 if (!base->symbol_list)
216 return;
217 base->evaluated = 1;
218
219 if (!base->ident && name)
220 base->ident = mk_name(root, name);
221 if (base->ident && reporter->r_symdef)
222 reporter->r_symdef(base);
223 DO_LIST(base->symbol_list, mem,
224 examine_sym_node(mem, base->ident ?: root));
225 default:
226 return;
227 }
228 }
229
230 static struct symbol *base_type(struct symbol *sym)
231 {
232 if (!sym)
233 return &bad_ctype;
234
235 if (sym->type == SYM_NODE)
236 examine_sym_node(sym, NULL);
237
238 return sym->ctype.base_type // builtin_fn_type
239 ?: &bad_ctype;
240 }
241
242 static struct symbol *__lookup_member(struct symbol *type, struct ident *name, int *p_addr)
243 {
244 struct symbol *node;
245 int addr = 0;
246
247 FOR_EACH_PTR(type->symbol_list, node)
248 if (!name) {
249 if (addr == *p_addr)
250 return node;
251 }
252 else if (node->ident == NULL) {
253 node = __lookup_member(node->ctype.base_type, name, NULL);
254 if (node)
255 goto found;
256 }
257 else if (node->ident == name) {
258 found:
259 if (p_addr)
260 *p_addr = addr;
261 return node;
262 }
263 addr++;
264 END_FOR_EACH_PTR(node);
265
266 return NULL;
267 }
268
269 static struct symbol *lookup_member(struct symbol *type, struct ident *name, int *addr)
270 {
271 return __lookup_member(type, name, addr)
272 ?: no_member(name);
273 }
274
275 static struct expression *peek_preop(struct expression *expr, int op)
276 {
277 do {
278 if (expr->type != EXPR_PREOP)
279 break;
280 if (expr->op == op)
281 return expr->unop;
282 if (expr->op == '(')
283 expr = expr->unop;
284 else
285 break;
286 } while (expr);
287
288 return NULL;
289 }
290
291 static struct symbol *do_expression(usage_t mode, struct expression *expr)
292 {
293 struct symbol *ret = &int_ctype;
294
295 again:
296 if (expr) switch (expr->type) {
297 default:
298 warning(expr->pos, "bad expr->type: %d", expr->type);
299
300 case EXPR_TYPE: // [struct T]; Why ???
301 case EXPR_VALUE:
302 case EXPR_FVALUE:
303
304 break; case EXPR_LABEL:
305 ret = &label_ctype;
306
307 break; case EXPR_STRING:
308 ret = &string_ctype;
309
310 break; case EXPR_STATEMENT:
311 ret = do_statement(mode, expr->statement);
312
313 break; case EXPR_SIZEOF: case EXPR_ALIGNOF: case EXPR_PTRSIZEOF:
314 do_expression(U_VOID, expr->cast_expression);
315
316 break; case EXPR_COMMA:
317 do_expression(U_VOID, expr->left);
318 ret = do_expression(mode, expr->right);
319
320 break; case EXPR_CAST: //case EXPR_IMPLIED_CAST:
321 ret = base_type(expr->cast_type);
322 do_initializer(ret, expr->cast_expression);
323
324 break; case EXPR_COMPARE: case EXPR_LOGICAL:
325 mode = u_rval(mode);
326 do_expression(mode, expr->left);
327 do_expression(mode, expr->right);
328
329 break; case EXPR_CONDITIONAL: //case EXPR_SELECT:
330 do_expression(expr->cond_true
331 ? U_R_VAL : U_R_VAL | mode,
332 expr->conditional);
333 ret = do_expression(mode, expr->cond_true);
334 ret = do_expression(mode, expr->cond_false);
335
336 break; case EXPR_CALL:
337 ret = do_expression(U_R_PTR, expr->fn);
338 if (is_ptr(ret))
339 ret = ret->ctype.base_type;
340 DO_2_LIST(ret->arguments, expr->args, arg, val,
341 do_expression(u_lval(base_type(arg)), val));
342 ret = ret->type == SYM_FN ? base_type(ret)
343 : &bad_ctype;
344
345 break; case EXPR_ASSIGNMENT:
346 mode |= U_W_VAL | U_R_VAL;
347 if (expr->op == '=')
348 mode &= ~U_R_VAL;
349 ret = do_expression(mode, expr->left);
350 report_implicit(mode, &expr->pos, ret);
351 mode = expr->op == '='
352 ? u_lval(ret) : U_R_VAL;
353 do_expression(mode, expr->right);
354
355 break; case EXPR_BINOP: {
356 struct symbol *l, *r;
357 mode |= u_rval(mode);
358 l = do_expression(mode, expr->left);
359 r = do_expression(mode, expr->right);
360 if (expr->op != '+' && expr->op != '-')
361 ;
362 else if (!is_ptr_type(r))
363 ret = l;
364 else if (!is_ptr_type(l))
365 ret = r;
366 }
367
368 break; case EXPR_PREOP: case EXPR_POSTOP: {
369 struct expression *unop = expr->unop;
370
371 switch (expr->op) {
372 case SPECIAL_INCREMENT:
373 case SPECIAL_DECREMENT:
374 mode |= U_W_VAL | U_R_VAL;
375 default:
376 mode |= u_rval(mode);
377 case '(':
378 ret = do_expression(mode, unop);
379
380 break; case '&':
381 if ((expr = peek_preop(unop, '*')))
382 goto again;
383 ret = alloc_symbol(unop->pos, SYM_PTR);
384 ret->ctype.base_type =
385 do_expression(u_addr(mode), unop);
386
387 break; case '*':
388 if ((expr = peek_preop(unop, '&')))
389 goto again;
390 if (mode & (U_MASK << U_SHIFT))
391 mode |= U_R_VAL;
392 mode <<= U_SHIFT;
393 if (mode & (U_R_AOF << U_SHIFT))
394 mode |= U_R_VAL;
395 if (mode & (U_W_VAL << U_SHIFT))
396 mode |= U_W_AOF;
397 ret = do_expression(mode, unop);
398 ret = is_ptr(ret) ? base_type(ret)
399 : &bad_ctype;
400 }
401 }
402
403 break; case EXPR_DEREF: {
404 struct symbol *p_type;
405 usage_t p_mode;
406
407 p_mode = mode & U_SELF;
408 if (!(mode & U_MASK) && (mode & (U_MASK << U_SHIFT)))
409 p_mode = U_R_VAL;
410 p_type = do_expression(p_mode, expr->deref);
411
412 ret = report_member(mode, &expr->pos, p_type,
413 lookup_member(p_type, expr->member, NULL));
414 }
415
416 break; case EXPR_SYMBOL:
417 ret = report_symbol(mode, expr);
418 }
419
420 return ret;
421 }
422
423 static void do_asm_xputs(usage_t mode, struct expression_list *xputs)
424 {
425 int nr = 0;
426
427 DO_LIST(xputs, expr,
428 if (++nr % 3 == 0)
429 do_expression(U_W_AOF | mode, expr));
430 }
431
432 static struct symbol *do_statement(usage_t mode, struct statement *stmt)
433 {
434 struct symbol *ret = &void_ctype;
435
436 if (stmt) switch (stmt->type) {
437 default:
438 warning(stmt->pos, "bad stmt->type: %d", stmt->type);
439
440 case STMT_NONE:
441 case STMT_RANGE:
442 case STMT_CONTEXT:
443
444 break; case STMT_DECLARATION:
445 do_sym_list(stmt->declaration);
446
447 break; case STMT_EXPRESSION:
448 ret = do_expression(mode, stmt->expression);
449
450 break; case STMT_RETURN:
451 do_expression(u_lval(return_type), stmt->expression);
452
453 break; case STMT_ASM:
454 do_expression(U_R_VAL, stmt->asm_string);
455 do_asm_xputs(U_W_VAL, stmt->asm_outputs);
456 do_asm_xputs(U_R_VAL, stmt->asm_inputs);
457
458 break; case STMT_COMPOUND: {
459 int count;
460
461 count = statement_list_size(stmt->stmts);
462 DO_LIST(stmt->stmts, st,
463 ret = do_statement(--count ? U_VOID : mode, st));
464 }
465
466 break; case STMT_ITERATOR:
467 do_sym_list(stmt->iterator_syms);
468 do_statement(U_VOID, stmt->iterator_pre_statement);
469 do_expression(U_R_VAL, stmt->iterator_pre_condition);
470 do_statement(U_VOID, stmt->iterator_post_statement);
471 do_statement(U_VOID, stmt->iterator_statement);
472 do_expression(U_R_VAL, stmt->iterator_post_condition);
473
474 break; case STMT_IF:
475 do_expression(U_R_VAL, stmt->if_conditional);
476 do_statement(U_VOID, stmt->if_true);
477 do_statement(U_VOID, stmt->if_false);
478
479 break; case STMT_SWITCH:
480 do_expression(U_R_VAL, stmt->switch_expression);
481 do_statement(U_VOID, stmt->switch_statement);
482
483 break; case STMT_CASE:
484 do_expression(U_R_VAL, stmt->case_expression);
485 do_expression(U_R_VAL, stmt->case_to);
486 do_statement(U_VOID, stmt->case_statement);
487
488 break; case STMT_GOTO:
489 do_expression(U_R_PTR, stmt->goto_expression);
490
491 break; case STMT_LABEL:
492 do_statement(mode, stmt->label_statement);
493
494 }
495
496 return ret;
497 }
498
499 static struct symbol *do_initializer(struct symbol *type, struct expression *expr)
500 {
501 struct symbol *m_type;
502 struct expression *m_expr;
503 int m_addr;
504
505 if (expr) switch (expr->type) {
506 default:
507 do_expression(u_lval(type), expr);
508
509 break; case EXPR_INDEX:
510 do_initializer(base_type(type), expr->idx_expression);
511
512 break; case EXPR_INITIALIZER:
513 m_addr = 0;
514 FOR_EACH_PTR(expr->expr_list, m_expr)
515 if (type->type == SYM_ARRAY) {
516 m_type = base_type(type);
517 if (m_expr->type == EXPR_INDEX)
518 m_expr = m_expr->idx_expression;
519 } else {
520 struct position *pos = &m_expr->pos;
521 struct ident *m_name = NULL;
522
523 if (m_expr->type == EXPR_IDENTIFIER) {
524 m_name = m_expr->expr_ident;
525 m_expr = m_expr->ident_expression;
526 }
527
528 m_type = report_member(U_W_VAL, pos, type,
529 lookup_member(type, m_name, &m_addr));
530 if (m_expr->type != EXPR_INITIALIZER)
531 report_implicit(U_W_VAL, pos, m_type);
532 }
533 do_initializer(m_type, m_expr);
534 m_addr++;
535 END_FOR_EACH_PTR(m_expr);
536 }
537
538 return type;
539 }
540
541 static inline struct symbol *do_symbol(struct symbol *sym)
542 {
543 struct symbol *type;
544
545 type = base_type(sym);
546
547 if (reporter->r_symdef)
548 reporter->r_symdef(sym);
549
550 switch (type->type) {
551 default:
552 if (!sym->initializer)
553 break;
554 if (reporter->r_symbol)
555 reporter->r_symbol(U_W_VAL, &sym->pos, sym);
556 do_initializer(type, sym->initializer);
557
558 break; case SYM_FN:
559 do_sym_list(type->arguments);
560 return_type = base_type(type);
561 do_statement(U_VOID, sym->ctype.modifiers & MOD_INLINE
562 ? type->inline_stmt
563 : type->stmt);
564 }
565
566 return type;
567 }
568
569 static void do_sym_list(struct symbol_list *list)
570 {
571 DO_LIST(list, sym, do_symbol(sym));
572 }
573
574 void dissect(struct symbol_list *list, struct reporter *rep)
575 {
576 reporter = rep;
577 do_sym_list(list);
578 }
Static analysis for C