Add proper linearization of switch statements.
[smatch.git] / linearize.c
blobc2637c53c44fce378dcb83cd76ece1fd36010595
1 /*
2 * Linearize - walk the statement tree (but _not_ the expressions)
3 * to generate a linear version of it and the basic blocks.
5 * NOTE! We're not interested in the actual sub-expressions yet,
6 * even though they can generate conditional branches and
7 * subroutine calls. That's all "local" behaviour.
9 * Copyright (C) 2004 Linus Torvalds
12 #include <string.h>
13 #include <stdarg.h>
14 #include <stdlib.h>
15 #include <stdio.h>
17 #include "parse.h"
18 #include "expression.h"
19 #include "linearize.h"
21 static struct entrypoint *alloc_entrypoint(void)
23 return __alloc_entrypoint(0);
26 static struct basic_block *alloc_basic_block(void)
28 return __alloc_basic_block(0);
31 static void show_bb(struct basic_block *bb)
33 struct statement *stmt;
35 printf("bb: %p\n", bb);
36 FOR_EACH_PTR(bb->stmts, stmt) {
37 show_statement(stmt);
38 } END_FOR_EACH_PTR;
40 if (bb->next) {
41 printf("\tgoto\t\t.L%p\n", bb->next->bb_target);
42 } else {
43 printf("\tEND\n");
45 printf("\n");
48 static void show_entry(struct entrypoint *ep)
50 struct symbol *sym;
51 struct basic_block *bb;
53 printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
55 FOR_EACH_PTR(ep->syms, sym) {
56 printf(" sym: %p %s\n", sym, show_ident(sym->ident));
57 } END_FOR_EACH_PTR;
59 printf("\n");
61 FOR_EACH_PTR(ep->bbs, bb) {
62 show_bb(bb);
63 } END_FOR_EACH_PTR;
65 printf("\n");
68 static struct basic_block * new_basic_block(struct basic_block_list **bbs)
70 struct basic_block *bb = alloc_basic_block();
71 add_bb(bbs, bb);
72 return bb;
75 static struct basic_block * linearize_statement(struct symbol_list **syms,
76 struct basic_block_list **bbs,
77 struct basic_block *bb,
78 struct statement *stmt)
80 if (!stmt)
81 return bb;
83 switch (stmt->type) {
84 case STMT_NONE:
85 break;
87 case STMT_ASM:
88 case STMT_EXPRESSION:
89 add_statement(&bb->stmts, stmt);
90 break;
92 case STMT_RETURN:
93 add_statement(&bb->stmts, stmt);
94 bb = new_basic_block(bbs);
95 break;
97 case STMT_CASE: {
98 struct basic_block *new_bb = new_basic_block(bbs);
99 struct symbol *sym = stmt->case_label;
101 bb->next = sym;
102 sym->bb_target = new_bb;
104 bb = linearize_statement(syms, bbs, new_bb, stmt->case_statement);
105 break;
108 case STMT_LABEL: {
109 struct basic_block *new_bb = new_basic_block(bbs);
110 struct symbol *sym = stmt->label_identifier;
112 bb->next = sym;
113 sym->bb_target = new_bb;
115 bb = linearize_statement(syms, bbs, new_bb, stmt->label_statement);
116 break;
119 case STMT_GOTO: {
120 struct basic_block *new_bb = new_basic_block(bbs);
121 struct symbol *sym = stmt->goto_label;
123 bb->next = sym;
124 bb = new_bb;
125 break;
128 case STMT_COMPOUND: {
129 struct statement *s;
130 concat_symbol_list(stmt->syms, syms);
131 FOR_EACH_PTR(stmt->stmts, s) {
132 bb = linearize_statement(syms, bbs, bb, s);
133 } END_FOR_EACH_PTR;
134 break;
138 * This could take 'likely/unlikely' into account, and
139 * switch the arms around appropriately..
141 case STMT_IF: {
142 struct symbol *target = alloc_symbol(stmt->pos, SYM_LABEL);
143 struct statement *goto_bb = alloc_statement(stmt->pos, STMT_CONDFALSE);
144 struct basic_block *last_bb;
146 add_statement(&bb->stmts, goto_bb);
147 last_bb = new_basic_block(bbs);
149 goto_bb->bb_conditional = stmt->if_conditional;
150 goto_bb->bb_target = target;
152 bb = linearize_statement(syms, bbs, bb, stmt->if_true);
153 bb->next = target;
154 target->bb_target = last_bb;
156 if (stmt->if_false) {
157 struct symbol *else_target = alloc_symbol(stmt->pos, SYM_LABEL);
158 struct basic_block *else_bb = new_basic_block(bbs);
160 else_target->bb_target = else_bb;
161 else_bb = linearize_statement(syms, bbs, else_bb, stmt->if_false);
162 goto_bb->bb_target = else_target;
163 else_bb->next = target;
166 bb = last_bb;
167 break;
170 case STMT_SWITCH: {
171 struct symbol *sym;
172 struct statement *switch_value;
174 /* Create the "head node" */
175 switch_value = alloc_statement(stmt->pos, STMT_MULTIVALUE);
176 switch_value->expression = stmt->switch_expression;
177 add_statement(&bb->stmts, switch_value);
179 /* Create all the sub-jumps */
180 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
181 struct statement *case_stmt = sym->stmt;
182 struct statement *sw_bb = alloc_statement(case_stmt->pos, STMT_MULTIJMP);
183 sw_bb->multi_from = case_stmt->case_expression;
184 sw_bb->multi_to = case_stmt->case_to;
185 sw_bb->multi_target = sym;
186 add_statement(&bb->stmts, sw_bb);
187 } END_FOR_EACH_PTR;
189 /* And linearize the actual statement */
190 bb = linearize_statement(syms, bbs, new_basic_block(bbs), stmt->switch_statement);
192 /* ..then tie it all together at the end.. */
193 bb->next = stmt->switch_break;
194 bb = new_basic_block(bbs);
195 stmt->switch_break->bb_target = bb;
197 break;
200 case STMT_ITERATOR: {
201 struct statement *pre_statement = stmt->iterator_pre_statement;
202 struct expression *pre_condition = stmt->iterator_pre_condition;
203 struct statement *statement = stmt->iterator_statement;
204 struct statement *post_statement = stmt->iterator_post_statement;
205 struct expression *post_condition = stmt->iterator_post_condition;
206 struct symbol *loop_top = NULL, *loop_bottom = NULL;
208 concat_symbol_list(stmt->iterator_syms, syms);
209 bb = linearize_statement(syms, bbs, bb, pre_statement);
210 if (pre_condition) {
211 if (pre_condition->type == EXPR_VALUE) {
212 if (!pre_condition->value) {
213 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
214 bb->next = loop_bottom;
215 bb = new_basic_block(bbs);
217 } else {
218 struct statement *pre_cond = alloc_statement(stmt->pos, STMT_CONDFALSE);
219 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
220 pre_cond->bb_conditional = pre_condition;
221 pre_cond->bb_target = loop_bottom;
222 add_statement(&bb->stmts, pre_cond);
226 if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
227 struct basic_block *loop = new_basic_block(bbs);
228 loop_top = alloc_symbol(stmt->pos, SYM_LABEL);
229 loop_top->bb_target = loop;
230 bb->next = loop_top;
231 bb = loop;
234 bb = linearize_statement(syms, bbs, bb, statement);
236 if (stmt->iterator_continue->used) {
237 struct basic_block *cont = new_basic_block(bbs);
238 stmt->iterator_continue->bb_target = cont;
239 bb->next = stmt->iterator_continue;
240 bb = cont;
243 bb = linearize_statement(syms, bbs, bb, post_statement);
245 if (!post_condition) {
246 bb->next = loop_top;
247 } else {
248 if (post_condition->type != EXPR_VALUE || post_condition->value) {
249 struct statement *post_cond = alloc_statement(stmt->pos, STMT_CONDTRUE);
250 post_cond->bb_conditional = post_condition;
251 post_cond->bb_target = loop_top;
252 add_statement(&bb->stmts, post_cond);
256 if (stmt->iterator_break->used) {
257 struct basic_block *brk = new_basic_block(bbs);
258 stmt->iterator_break->bb_target = brk;
259 bb->next = stmt->iterator_break;
260 bb = brk;
262 break;
265 default:
266 break;
268 return bb;
271 void linearize_symbol(struct symbol *sym)
273 struct symbol *base_type;
275 if (!sym)
276 return;
277 base_type = sym->ctype.base_type;
278 if (!base_type)
279 return;
280 if (base_type->type == SYM_FN) {
281 if (base_type->stmt) {
282 struct entrypoint *ep = alloc_entrypoint();
283 struct basic_block *bb;
285 ep->name = sym;
286 bb = new_basic_block(&ep->bbs);
287 concat_symbol_list(base_type->arguments, &ep->syms);
288 linearize_statement(&ep->syms, &ep->bbs, bb, base_type->stmt);
289 show_entry(ep);