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
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
) {
41 printf("\tgoto .L%p\n", bb
->next
->bb_target
);
43 printf("\tdefault return\n");
48 static void show_entry(struct entrypoint
*ep
)
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
));
61 FOR_EACH_PTR(ep
->bbs
, bb
) {
68 static struct basic_block
* new_basic_block(struct basic_block_list
**bbs
)
70 struct basic_block
*bb
= alloc_basic_block();
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
)
89 add_statement(&bb
->stmts
, stmt
);
93 add_statement(&bb
->stmts
, stmt
);
94 bb
= new_basic_block(bbs
);
99 struct basic_block
*new_bb
= new_basic_block(bbs
);
100 struct symbol
*sym
= stmt
->label_identifier
;
103 sym
->bb_target
= new_bb
;
105 bb
= linearize_statement(syms
, bbs
, new_bb
, stmt
->label_statement
);
110 struct basic_block
*new_bb
= new_basic_block(bbs
);
111 struct symbol
*sym
= stmt
->goto_label
;
118 case STMT_COMPOUND
: {
120 concat_symbol_list(stmt
->syms
, syms
);
121 FOR_EACH_PTR(stmt
->stmts
, s
) {
122 bb
= linearize_statement(syms
, bbs
, bb
, s
);
128 * This could take 'likely/unlikely' into account, and
129 * switch the arms around appropriately..
132 struct symbol
*target
= alloc_symbol(stmt
->pos
, SYM_LABEL
);
133 struct statement
*goto_bb
= alloc_statement(stmt
->pos
, STMT_CONDFALSE
);
134 struct basic_block
*last_bb
;
136 add_statement(&bb
->stmts
, goto_bb
);
137 last_bb
= new_basic_block(bbs
);
139 goto_bb
->bb_conditional
= stmt
->if_conditional
;
140 goto_bb
->bb_target
= target
;
142 bb
= linearize_statement(syms
, bbs
, bb
, stmt
->if_true
);
144 target
->bb_target
= last_bb
;
146 if (stmt
->if_false
) {
147 struct symbol
*else_target
= alloc_symbol(stmt
->pos
, SYM_LABEL
);
148 struct basic_block
*else_bb
= new_basic_block(bbs
);
150 else_target
->bb_target
= else_bb
;
151 else_bb
= linearize_statement(syms
, bbs
, else_bb
, stmt
->if_false
);
152 goto_bb
->bb_target
= else_target
;
153 else_bb
->next
= target
;
161 add_statement(&bb
->stmts
, stmt
);
162 bb
= new_basic_block(bbs
);
165 case STMT_ITERATOR
: {
166 struct statement
*pre_statement
= stmt
->iterator_pre_statement
;
167 struct expression
*pre_condition
= stmt
->iterator_pre_condition
;
168 struct statement
*statement
= stmt
->iterator_statement
;
169 struct statement
*post_statement
= stmt
->iterator_post_statement
;
170 struct expression
*post_condition
= stmt
->iterator_post_condition
;
171 struct symbol
*loop_top
= NULL
, *loop_bottom
= NULL
;
173 concat_symbol_list(stmt
->iterator_syms
, syms
);
174 bb
= linearize_statement(syms
, bbs
, bb
, pre_statement
);
176 if (pre_condition
->type
== EXPR_VALUE
) {
177 if (!pre_condition
->value
) {
178 loop_bottom
= alloc_symbol(stmt
->pos
, SYM_LABEL
);
179 bb
->next
= loop_bottom
;
180 bb
= new_basic_block(bbs
);
183 struct statement
*pre_cond
= alloc_statement(stmt
->pos
, STMT_CONDFALSE
);
184 loop_bottom
= alloc_symbol(stmt
->pos
, SYM_LABEL
);
185 pre_cond
->bb_conditional
= pre_condition
;
186 pre_cond
->bb_target
= loop_bottom
;
187 add_statement(&bb
->stmts
, pre_cond
);
191 if (!post_condition
|| post_condition
->type
!= EXPR_VALUE
|| post_condition
->value
) {
192 struct basic_block
*loop
= new_basic_block(bbs
);
193 loop_top
= alloc_symbol(stmt
->pos
, SYM_LABEL
);
194 loop_top
->bb_target
= loop
;
199 bb
= linearize_statement(syms
, bbs
, bb
, statement
);
201 if (stmt
->iterator_continue
->used
) {
202 struct basic_block
*cont
= new_basic_block(bbs
);
203 stmt
->iterator_continue
->bb_target
= cont
;
204 bb
->next
= stmt
->iterator_continue
;
208 bb
= linearize_statement(syms
, bbs
, bb
, post_statement
);
210 if (!post_condition
) {
213 if (post_condition
->type
!= EXPR_VALUE
|| post_condition
->value
) {
214 struct statement
*post_cond
= alloc_statement(stmt
->pos
, STMT_CONDTRUE
);
215 post_cond
->bb_conditional
= post_condition
;
216 post_cond
->bb_target
= loop_top
;
217 add_statement(&bb
->stmts
, post_cond
);
221 if (stmt
->iterator_break
->used
) {
222 struct basic_block
*brk
= new_basic_block(bbs
);
223 stmt
->iterator_break
->bb_target
= brk
;
224 bb
->next
= stmt
->iterator_break
;
236 void linearize_symbol(struct symbol
*sym
)
238 struct symbol
*base_type
;
242 base_type
= sym
->ctype
.base_type
;
245 if (base_type
->type
== SYM_FN
) {
246 if (base_type
->stmt
) {
247 struct entrypoint
*ep
= alloc_entrypoint();
248 struct basic_block
*bb
;
251 bb
= new_basic_block(&ep
->bbs
);
252 concat_symbol_list(base_type
->arguments
, &ep
->syms
);
253 linearize_statement(&ep
->syms
, &ep
->bbs
, bb
, base_type
->stmt
);