diff options
| -rw-r--r-- | Documentation/IR.rst | 2 | ||||
| -rw-r--r-- | builtin.c | 73 | ||||
| -rw-r--r-- | evaluate.c | 3 | ||||
| -rw-r--r-- | expression.h | 2 | ||||
| -rw-r--r-- | flow.c | 17 | ||||
| -rw-r--r-- | linearize.c | 69 | ||||
| -rw-r--r-- | linearize.h | 7 | ||||
| -rw-r--r-- | liveness.c | 7 | ||||
| -rw-r--r-- | pre-process.c | 6 | ||||
| -rw-r--r-- | ptrlist.c | 10 | ||||
| -rw-r--r-- | ptrlist.h | 24 | ||||
| -rw-r--r-- | show-parse.c | 2 | ||||
| -rw-r--r-- | simplify.c | 6 | ||||
| -rw-r--r-- | sparse.c | 13 | ||||
| -rw-r--r-- | validation/builtin-objsize-dyn.c | 22 | ||||
| -rw-r--r-- | validation/builtin-objsize0.c | 25 | ||||
| -rw-r--r-- | validation/builtin-objsize1.c | 21 | ||||
| -rw-r--r-- | validation/eval/assign-restricted-ok.c | 22 | ||||
| -rw-r--r-- | validation/linear/asm-out0.c | 25 | ||||
| -rw-r--r-- | validation/mem2reg/asm-reload0.c | 14 |
20 files changed, 304 insertions, 66 deletions
diff --git a/Documentation/IR.rst b/Documentation/IR.rst index 0cc90ec0..d41bce87 100644 --- a/Documentation/IR.rst +++ b/Documentation/IR.rst @@ -408,7 +408,7 @@ Others Extract a "slice" from an aggregate. * .base: (pseudo_t) aggregate (alias .src) - * .from, .len: offet & size of the "slice" within the aggregate + * .from: offset of the "slice" within the aggregate * .target: result * .type: type of .target @@ -454,6 +454,77 @@ static struct symbol_op atomic_op = { }; +/// +// expand __builtin_object_size() +// +// :note: type 1 and type 3 are not supported because the +// needed information isn't available after evaluation. +static int expand_object_size(struct expression *expr, int cost) +{ + struct expression *arg = first_expression(expr->args); + int type = get_expression_value_silent(ptr_list_nth(expr->args, 1)); + unsigned long val = -1, off = 0; + + while (arg) { + switch (arg->type) { + case EXPR_IMPLIED_CAST: + case EXPR_CAST: + // ignore those + arg = arg->cast_expression; + continue; + case EXPR_BINOP: + // a constant add is (maybe) an offset + if (!arg->right || arg->op != '+' || arg->right->type != EXPR_VALUE) + break; + off += arg->right->value; + arg = arg->left; + continue; + case EXPR_PREOP: + // a deref is just intermediate variable + // and so the offset needs to be zeroed. + if (arg->op == '*') { + arg = arg->unop; + off = 0; + switch (arg->type) { + case EXPR_SYMBOL: + arg = arg->symbol->initializer; + continue; + default: + break; + } + } + break; + case EXPR_SYMBOL: + // the symbol we're looking after + val = bits_to_bytes(arg->symbol->bit_size); + break; + case EXPR_CALL: + // use alloc_size() attribute but only after linearization. + return UNSAFE; + default: + break; + } + break; + } + + if (val == -1) + val = (type & 2) ? 0 : val; + else if (type & 1) + return UNSAFE; + else + val -= off; + + expr->flags |= CEF_SET_ICE; + expr->type = EXPR_VALUE; + expr->value = val; + expr->taint = 0; + return 0; +} + +static struct symbol_op object_size_op = { + .expand = expand_object_size, +}; + /* * Builtin functions */ @@ -598,7 +669,7 @@ static const struct builtin_fn builtins_common[] = { { "__builtin_nan", &double_ctype, 0, { &const_string_ctype }}, { "__builtin_nanf", &float_ctype, 0, { &const_string_ctype }}, { "__builtin_nanl", &ldouble_ctype, 0, { &const_string_ctype }}, - { "__builtin_object_size", size_t_ctype, 0, { &const_ptr_ctype, &int_ctype }}, + { "__builtin_object_size", size_t_ctype, 0, { &const_ptr_ctype, &int_ctype }, .op = &object_size_op}, { "__builtin_parity", &int_ctype, 0, { &uint_ctype }, .op = &parity_op }, { "__builtin_parityl", &int_ctype, 0, { &ulong_ctype }, .op = &parity_op }, { "__builtin_parityll", &int_ctype, 0, { &ullong_ctype }, .op = &parity_op }, @@ -1442,7 +1442,7 @@ static int check_assignment_types(struct symbol *target, struct expression **rp, if (sclass & TYPE_FOULED && unfoul(s) == t) goto Cast; if (!restricted_value(*rp, target)) - return 1; + goto Cast; if (s == t) return 1; } else if (!(sclass & TYPE_RESTRICT)) @@ -2170,7 +2170,6 @@ static struct symbol *evaluate_member_dereference(struct expression *expr) } expr->r_bitpos += bytes_to_bits(offset); expr->type = EXPR_SLICE; - expr->r_nrbits = member->bit_size; expr->r_bitpos += member->bit_offset; expr->ctype = member; return member; diff --git a/expression.h b/expression.h index 3e9e9d85..f733c076 100644 --- a/expression.h +++ b/expression.h @@ -206,7 +206,7 @@ struct expression { // EXPR_SLICE struct /* slice */ { struct expression *base; - unsigned r_bitpos, r_nrbits; + unsigned r_bitpos; }; // EXPR_CAST, EXPR_FORCE_CAST, EXPR_IMPLIED_CAST, // EXPR_SIZEOF, EXPR_ALIGNOF and EXPR_PTRSIZEOF @@ -471,12 +471,21 @@ static inline int distinct_symbols(pseudo_t a, pseudo_t b) */ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local) { - int opcode = dom->opcode; - - if (opcode == OP_CALL || opcode == OP_ENTRY) + switch (dom->opcode) { + case OP_CALL: case OP_ENTRY: return local ? 0 : -1; - if (opcode != OP_LOAD && opcode != OP_STORE) + case OP_LOAD: case OP_STORE: + break; + case OP_ASM: + if (dom->clobber_memory) + return -1; + if (dom->output_memory) + return -1; + return 0; + default: return 0; + } + if (dom->src != pseudo) { if (local) return 0; diff --git a/linearize.c b/linearize.c index c1aeb159..7248fa56 100644 --- a/linearize.c +++ b/linearize.c @@ -466,7 +466,7 @@ const char *show_instruction(struct instruction *insn) break; case OP_SLICE: - buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len); + buf += sprintf(buf, "%s <- (%d) %s, %d", show_pseudo(insn->target), type_size(insn->orig_type), show_pseudo(insn->src), insn->from); break; case OP_NOT: case OP_NEG: @@ -1235,8 +1235,8 @@ static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr) insn->target = new; insn->from = expr->r_bitpos; - insn->len = expr->r_nrbits; - use_pseudo(insn, pre, &insn->base); + insn->orig_type = expr->base->ctype; + use_pseudo(insn, pre, &insn->src); add_one_insn(ep, insn); return new; } @@ -2123,43 +2123,55 @@ static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt) ALLOCATOR(asm_rules, "asm rules"); ALLOCATOR(asm_constraint, "asm constraints"); -static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct asm_operand *op) +static void add_asm_rule(struct instruction *insn, struct asm_constraint_list **list, struct asm_operand *op, pseudo_t pseudo) { - pseudo_t pseudo = linearize_expression(ep, op->expr); struct asm_constraint *rule = __alloc_asm_constraint(0); - + rule->is_memory = op->is_memory; rule->ident = op->name; rule->constraint = op->constraint ? op->constraint->string->data : ""; use_pseudo(insn, pseudo, &rule->pseudo); - add_ptr_list(&insn->asm_rules->inputs, rule); + add_ptr_list(list, rule); +} + +static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct asm_operand *op) +{ + pseudo_t pseudo = linearize_expression(ep, op->expr); + + add_asm_rule(insn, &insn->asm_rules->inputs, op, pseudo); +} + +static void add_asm_output_address(struct entrypoint *ep, struct instruction *insn, struct asm_operand *op) +{ + pseudo_t pseudo; + + if (!op->is_memory) + return; + + pseudo = linearize_expression(ep, op->expr); + add_asm_rule(insn, &insn->asm_rules->outputs, op, pseudo); + insn->output_memory = 1; } static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct asm_operand *op) { struct access_data ad = { NULL, }; pseudo_t pseudo; - struct asm_constraint *rule; - if (op->is_memory) { - pseudo = linearize_expression(ep, op->expr); - } else { - if (!linearize_address_gen(ep, op->expr, &ad)) - return; - pseudo = alloc_pseudo(insn); - linearize_store_gen(ep, pseudo, &ad); - } - rule = __alloc_asm_constraint(0); - rule->is_memory = op->is_memory; - rule->ident = op->name; - rule->constraint = op->constraint ? op->constraint->string->data : ""; - use_pseudo(insn, pseudo, &rule->pseudo); - add_ptr_list(&insn->asm_rules->outputs, rule); + if (op->is_memory) + return; + + if (!linearize_address_gen(ep, op->expr, &ad)) + return; + pseudo = alloc_pseudo(insn); + linearize_store_gen(ep, pseudo, &ad); + + add_asm_rule(insn, &insn->asm_rules->outputs, op, pseudo); } static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt) { struct instruction *insn; - struct expression *expr; + struct expression *expr, *clob; struct asm_rules *rules; struct asm_operand *op; @@ -2179,6 +2191,11 @@ static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement add_asm_input(ep, insn, op); } END_FOR_EACH_PTR(op); + /* ... and the addresses for memory outputs */ + FOR_EACH_PTR(stmt->asm_outputs, op) { + add_asm_output_address(ep, insn, op); + } END_FOR_EACH_PTR(op); + add_one_insn(ep, insn); /* Assign the outputs */ @@ -2186,6 +2203,12 @@ static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement add_asm_output(ep, insn, op); } END_FOR_EACH_PTR(op); + /* and finally, look if it clobbers memory */ + FOR_EACH_PTR(stmt->asm_clobbers, clob) { + if (!strcmp(clob->string->data, "memory")) + insn->clobber_memory = 1; + } END_FOR_EACH_PTR(clob); + return VOID; } diff --git a/linearize.h b/linearize.h index 18f1d80f..7909b01f 100644 --- a/linearize.h +++ b/linearize.h @@ -113,6 +113,7 @@ struct instruction { }; struct /* unops */ { pseudo_t src; + unsigned from; /* slice */ struct symbol *orig_type; /* casts */ }; struct /* memops */ { @@ -127,10 +128,6 @@ struct instruction { pseudo_t _src1, _src2; // alias .src[12] struct symbol *itype; // input operands' type }; - struct /* slice */ { - pseudo_t base; - unsigned from, len; - }; struct /* setval */ { struct expression *val; }; @@ -150,6 +147,8 @@ struct instruction { struct /* asm */ { const char *string; struct asm_rules *asm_rules; + unsigned int clobber_memory:1; + unsigned int output_memory:1; }; }; }; @@ -76,7 +76,8 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction * /* Uni */ case OP_UNOP ... OP_UNOP_END: case OP_SYMADDR: - USES(src1); DEFINES(target); + case OP_SLICE: + USES(src); DEFINES(target); break; case OP_SEL: @@ -121,10 +122,6 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction * } END_FOR_EACH_PTR(pseudo); break; - case OP_SLICE: - USES(base); DEFINES(target); - break; - case OP_ASM: asm_liveness(bb, insn, def, use); break; diff --git a/pre-process.c b/pre-process.c index 7a1478f6..3fb25082 100644 --- a/pre-process.c +++ b/pre-process.c @@ -884,6 +884,12 @@ static void set_stream_include_path(struct stream *stream) memcpy(m, stream->name, len); m[len] = 0; path = m; + /* normalize this path */ + while (path[0] == '.' && path[1] == '/') { + path += 2; + while (path[0] == '/') + path++; + } } stream->path = path; } @@ -154,10 +154,10 @@ void *ptr_list_nth_entry(struct ptr_list *list, unsigned int idx) // @head: the list to be linearized // @arr: a ``void*`` array to fill with @head's entries // @max: the maximum number of entries to store into @arr -// @return: the number of entries linearized. +// @return: the number of entries in the list. // // Linearize the entries of a list up to a total of @max, -// and return the nr of entries linearized. +// and return the number of entries in the list. // // The array to linearize into (@arr) should really // be ``void *x[]``, but we want to let people fill in any kind @@ -170,14 +170,14 @@ int linearize_ptr_list(struct ptr_list *head, void **arr, int max) do { int i = list->nr; + nr += i; + if (max == 0) + continue; if (i > max) i = max; memcpy(arr, list->list, i*sizeof(void *)); arr += i; - nr += i; max -= i; - if (!max) - break; } while ((list = list->next) != head); } return nr; @@ -12,7 +12,7 @@ /* Silly type-safety check ;) */ #define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0]) -#define TYPEOF(head) __typeof__(&(head)->list[0]) +#define PTRLIST_TYPE(head) __typeof__((head)->list[0]) #define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0])) #define LIST_NODE_NR (13) @@ -67,12 +67,28 @@ extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long); (__typeof__(&(ptr))) __add_ptr_list_tag(head, ptr, tag);\ }) +#define pop_ptr_list(l) ({ \ + PTRLIST_TYPE(*(l)) ptr; \ + ptr = delete_ptr_list_last((struct ptr_list**)(l)); \ + ptr; \ + }) + extern void __free_ptr_list(struct ptr_list **); #define free_ptr_list(list) do { \ VRFY_PTR_LIST(*(list)); \ __free_ptr_list((struct ptr_list **)(list)); \ } while (0) +#define ptr_list_nth(lst, nth) ({ \ + struct ptr_list* head = (struct ptr_list*)(lst); \ + (PTRLIST_TYPE(lst)) ptr_list_nth_entry(head, nth);\ + }) + +#define ptr_list_to_array(list, array, size) ({ \ + struct ptr_list* head = (struct ptr_list*)(list); \ + CHECK_TYPE(list, *array); \ + linearize_ptr_list(head, (void**)array, size); \ + }) //////////////////////////////////////////////////////////////////////// // API @@ -247,7 +263,7 @@ extern void __free_ptr_list(struct ptr_list **); extern void split_ptr_list_head(struct ptr_list *); #define DO_INSERT_CURRENT(new, __head, __list, __nr) do { \ - TYPEOF(__head) __this, __last; \ + PTRLIST_TYPE(__head) *__this, *__last; \ if (__list->nr == LIST_NODE_NR) { \ split_ptr_list_head((struct ptr_list*)__list); \ if (__nr >= __list->nr) { \ @@ -266,8 +282,8 @@ extern void split_ptr_list_head(struct ptr_list *); } while (0) #define DO_DELETE_CURRENT(__head, __list, __nr) do { \ - TYPEOF(__head) __this = __list->list + __nr; \ - TYPEOF(__head) __last = __list->list + __list->nr - 1; \ + PTRLIST_TYPE(__head) *__this = __list->list + __nr; \ + PTRLIST_TYPE(__head) *__last = __list->list + __list->nr - 1; \ while (__this < __last) { \ __this[0] = __this[1]; \ __this++; \ diff --git a/show-parse.c b/show-parse.c index 3ab8ec8f..e2fc18bb 100644 --- a/show-parse.c +++ b/show-parse.c @@ -819,7 +819,7 @@ static int show_slice(struct expression *expr) { int target = show_expression(expr->base); int new = new_pseudo(); - printf("\tslice.%d\t\tv%d,v%d,%d\n", expr->r_nrbits, target, new, expr->r_bitpos); + printf("\tslice.%d\t\tv%d,v%d,%d\n", expr->ctype->bit_size, target, new, expr->r_bitpos); return new; } @@ -83,7 +83,7 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud // number of element, a positive number if there was // more than expected and a negative one if less. // -// :note: we can't reuse a function like linearize_ptr_list() +// :note: we can't reuse ptr_list_to_array() for the phi-sources // because any VOIDs in the phi-list must be ignored here // as in this context they mean 'entry has been removed'. static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn) @@ -108,7 +108,7 @@ static int get_phisources(struct instruction *sources[], int nbr, struct instruc static int if_convert_phi(struct instruction *insn) { struct instruction *array[2]; - struct basic_block *parents[3]; + struct basic_block *parents[2]; struct basic_block *bb, *bb1, *bb2, *source; struct instruction *br; pseudo_t p1, p2; @@ -116,7 +116,7 @@ static int if_convert_phi(struct instruction *insn) bb = insn->bb; if (get_phisources(array, 2, insn)) return 0; - if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2) + if (ptr_list_to_array(bb->parents, parents, 2) != 2) return 0; p1 = array[0]->phi_src; bb1 = array[0]->bb; @@ -163,20 +163,9 @@ static void check_byte_count(struct instruction *insn, pseudo_t count) /* OK, we could try to do the range analysis here */ } -static pseudo_t argument(struct instruction *call, unsigned int argno) -{ - pseudo_t args[8]; - struct ptr_list *arg_list = (struct ptr_list *) call->arguments; - - argno--; - if (linearize_ptr_list(arg_list, (void *)args, 8) > argno) - return args[argno]; - return NULL; -} - static void check_memset(struct instruction *insn) { - check_byte_count(insn, argument(insn, 3)); + check_byte_count(insn, ptr_list_nth(insn->arguments, 3)); } #define check_memcpy check_memset diff --git a/validation/builtin-objsize-dyn.c b/validation/builtin-objsize-dyn.c new file mode 100644 index 00000000..276c9204 --- /dev/null +++ b/validation/builtin-objsize-dyn.c @@ -0,0 +1,22 @@ +void *alloc(unsigned long)__attribute__((alloc_size(1))); + +_Bool sta(void) +{ + void *ptr = alloc(4); + return __builtin_object_size(ptr, 0) == 4; +} + +_Bool dyn(unsigned long n) +{ + void *ptr = alloc(n); + return __builtin_object_size(ptr, 0) == n; +} + +/* + * check-name: builtin-objsize-dyn + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/builtin-objsize0.c b/validation/builtin-objsize0.c new file mode 100644 index 00000000..9aab2ddd --- /dev/null +++ b/validation/builtin-objsize0.c @@ -0,0 +1,25 @@ +#define bos(O, T) __builtin_object_size(O, T) + +struct s { + char arr[8]; + __INT32_TYPE__ i; + __INT32_TYPE__ padding; +}; + +static struct s s; +static char *p = &s.arr[1]; +static int *q = &s.i; + +int obj_int0(void) { return bos(&s.i, 0) == 8; } +int obj_arr0(void) { return bos(&s.arr[1], 0) == 15; } + +int ptr_int(struct s *p) { return bos(&p->i, 0) == -1; } +int ptr_arr(struct s *p) { return bos(&p->arr[1], 0) == -1; } + +/* + * check-name: builtin-objsize0 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/builtin-objsize1.c b/validation/builtin-objsize1.c new file mode 100644 index 00000000..1f285fc5 --- /dev/null +++ b/validation/builtin-objsize1.c @@ -0,0 +1,21 @@ +#define bos(O, T) __builtin_object_size(O, T) + +struct s { + char arr[8]; + __INT32_TYPE__ i; + __INT32_TYPE__ padding; +}; + +static struct s s; + +int obj_int1(void) { return bos(&s.i, 1) == 4; } +int obj_arr1(void) { return bos(&s.arr[1], 1) == 7; } + +/* + * check-name: builtin-objsize1 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/eval/assign-restricted-ok.c b/validation/eval/assign-restricted-ok.c new file mode 100644 index 00000000..df94d8c9 --- /dev/null +++ b/validation/eval/assign-restricted-ok.c @@ -0,0 +1,22 @@ +#ifdef __CHECKER__ +#define __bitwise __attribute__((bitwise)) +#else +#define __bitwise +#endif + +typedef __INT16_TYPE__ __bitwise __be16; + +static __be16 foo(void) +{ + __be16 val = 0; + return val; +} + +/* + * check-name: assign-restricted-ok + * check-command: test-linearize -fdump-ir $file + * + * check-output-ignore + * check-output-contains: store\\.16 + * check-output-excludes: store\\.32 + */ diff --git a/validation/linear/asm-out0.c b/validation/linear/asm-out0.c new file mode 100644 index 00000000..8b0907b3 --- /dev/null +++ b/validation/linear/asm-out0.c @@ -0,0 +1,25 @@ +static void asm_out0(void) +{ + int mem; + asm volatile ("[%1] <= 0" : "=m" (mem)); +} + +/* + * check-name: asm-out0 + * check-command: test-linearize -m64 -fdump-ir $file + * + * check-output-start +asm_out0: +.L0: + <entry-point> + symaddr.64 %r1 <- mem + asm "[%1] <= 0" + out: "=m" (%r1) + br .L1 + +.L1: + ret + + + * check-output-end + */ diff --git a/validation/mem2reg/asm-reload0.c b/validation/mem2reg/asm-reload0.c new file mode 100644 index 00000000..ce1829e0 --- /dev/null +++ b/validation/mem2reg/asm-reload0.c @@ -0,0 +1,14 @@ +static int asm_reload(void) +{ + int mem = 0; + asm volatile ("[%1] <= 1" : "=m" (mem)); + return mem; +} + +/* + * check-name: asm-reload0 + * check-command: test-linearize $file + * + * check-output-ignore + * check-output-contains: load\\. + */ |