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
10 * Copyright (C) 2004 Christopher Li
19 #include "expression.h"
20 #include "linearize.h"
22 pseudo_t
linearize_statement(struct entrypoint
*ep
, struct statement
*stmt
);
23 pseudo_t
linearize_expression(struct entrypoint
*ep
, struct expression
*expr
);
25 static void add_setcc(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t val
);
26 static pseudo_t
add_binary_op(struct entrypoint
*ep
, struct symbol
*ctype
, int op
, pseudo_t left
, pseudo_t right
);
27 static pseudo_t
add_setval(struct entrypoint
*ep
, struct symbol
*ctype
, struct expression
*val
);
30 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*);
31 pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*);
33 struct pseudo void_pseudo
= {};
35 static struct instruction
*alloc_instruction(int opcode
, struct symbol
*type
)
37 struct instruction
* insn
= __alloc_instruction(0);
39 insn
->opcode
= opcode
;
43 static struct entrypoint
*alloc_entrypoint(void)
45 return __alloc_entrypoint(0);
48 static struct basic_block
*alloc_basic_block(struct position pos
)
50 struct basic_block
*bb
= __alloc_basic_block(0);
56 static struct multijmp
* alloc_multijmp(struct basic_block
*target
, int begin
, int end
)
58 struct multijmp
*multijmp
= __alloc_multijmp(0);
59 multijmp
->target
= target
;
60 multijmp
->begin
= begin
;
65 static struct phi
* alloc_phi(struct basic_block
*source
, pseudo_t pseudo
)
67 struct phi
*phi
= __alloc_phi(0);
73 static inline int regno(pseudo_t n
)
76 if (n
&& n
->type
== PSEUDO_REG
)
81 static const char *show_pseudo(pseudo_t pseudo
)
84 static char buffer
[4][64];
91 buf
= buffer
[3 & ++n
];
92 switch(pseudo
->type
) {
94 struct symbol
*sym
= pseudo
->sym
;
95 struct expression
*expr
;
98 snprintf(buf
, 64, ".L%p", sym
->bb_target
);
102 snprintf(buf
, 64, "%s", show_ident(sym
->ident
));
105 expr
= sym
->initializer
;
107 snprintf(buf
, 64, "<anon sym: %d>", pseudo
->nr
);
110 switch (expr
->type
) {
112 snprintf(buf
, 64, "<symbol value: %lld>", expr
->value
);
115 return show_string(expr
->string
);
117 snprintf(buf
, 64, "<symbol expression: %d>", pseudo
->nr
);
122 snprintf(buf
, 64, "%%r%d", pseudo
->nr
);
125 snprintf(buf
, 64, "$%lld", pseudo
->value
);
128 snprintf(buf
, 64, "%%arg%d", pseudo
->nr
);
131 snprintf(buf
, 64, "<bad pseudo type %d>", pseudo
->type
);
136 static void show_instruction(struct instruction
*insn
)
138 int op
= insn
->opcode
;
142 printf("\tAIEEE! (%s <- %s)\n", show_pseudo(insn
->target
), show_pseudo(insn
->src
));
145 if (insn
->type
&& insn
->type
!= &void_ctype
)
146 printf("\tret %s\n", show_pseudo(insn
->src
));
151 if (insn
->bb_true
&& insn
->bb_false
) {
152 printf("\tbr\t%s, .L%p, .L%p\n", show_pseudo(insn
->cond
), insn
->bb_true
, insn
->bb_false
);
155 printf("\tbr\t.L%p\n", insn
->bb_true
? insn
->bb_true
: insn
->bb_false
);
159 struct expression
*expr
= insn
->val
;
160 struct symbol
*sym
= insn
->symbol
;
161 int target
= regno(insn
->target
);
164 if (sym
->bb_target
) {
165 printf("\t%%r%d <- .L%p\n", target
, sym
->bb_target
);
169 printf("\t%%r%d <- %s\n", target
, show_ident(sym
->ident
));
172 expr
= sym
->initializer
;
174 printf("\t%%r%d <- %s\n", target
, "anon symbol");
180 printf("\t%%r%d <- %s\n", target
, "<none>");
184 switch (expr
->type
) {
186 printf("\t%%r%d <- %lld\n", target
, expr
->value
);
189 printf("\t%%r%d <- %Lf\n", target
, expr
->fvalue
);
192 printf("\t%%r%d <- %s\n", target
, show_string(expr
->string
));
195 printf("\t%%r%d <- %s\n", target
, show_ident(expr
->symbol
->ident
));
198 printf("\t%%r%d <- .L%p\n", target
, expr
->symbol
->bb_target
);
201 printf("\t%%r%d <- SETVAL EXPR TYPE %d\n", target
, expr
->type
);
206 struct multijmp
*jmp
;
207 printf("\tswitch %s", show_pseudo(insn
->cond
));
208 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
209 if (jmp
->begin
== jmp
->end
)
210 printf(", %d -> .L%p", jmp
->begin
, jmp
->target
);
211 else if (jmp
->begin
< jmp
->end
)
212 printf(", %d ... %d -> .L%p", jmp
->begin
, jmp
->end
, jmp
->target
);
214 printf(", default -> .L%p\n", jmp
->target
);
215 } END_FOR_EACH_PTR(jmp
);
219 case OP_COMPUTEDGOTO
: {
220 struct multijmp
*jmp
;
221 printf("\tjmp *%s", show_pseudo(insn
->target
));
222 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
223 printf(", .L%p", jmp
->target
);
224 } END_FOR_EACH_PTR(jmp
);
232 printf("\t%s <- phi", show_pseudo(insn
->target
));
233 FOR_EACH_PTR(insn
->phi_list
, phi
) {
234 printf("%s(%s, .L%p)", s
, show_pseudo(phi
->pseudo
), phi
->source
);
236 } END_FOR_EACH_PTR(phi
);
241 printf("\tload %s <- %d[%s]\n", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
244 printf("\tstore %s -> %d[%s]\n", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
248 printf("\t%s <- CALL %s", show_pseudo(insn
->target
), show_pseudo(insn
->func
));
249 FOR_EACH_PTR(insn
->arguments
, arg
) {
250 printf(", %s", show_pseudo(arg
));
251 } END_FOR_EACH_PTR(arg
);
256 printf("\t%%r%d <- CAST(%d->%d) %s\n",
258 insn
->orig_type
->bit_size
, insn
->type
->bit_size
,
259 show_pseudo(insn
->src
));
261 case OP_BINARY
... OP_BINARY_END
: {
262 static const char *opname
[] = {
263 [OP_ADD
- OP_BINARY
] = "add", [OP_SUB
- OP_BINARY
] = "sub",
264 [OP_MUL
- OP_BINARY
] = "mul", [OP_DIV
- OP_BINARY
] = "div",
265 [OP_MOD
- OP_BINARY
] = "mod", [OP_AND
- OP_BINARY
] = "and",
266 [OP_OR
- OP_BINARY
] = "or", [OP_XOR
- OP_BINARY
] = "xor",
267 [OP_SHL
- OP_BINARY
] = "shl", [OP_SHR
- OP_BINARY
] = "shr",
268 [OP_AND_BOOL
- OP_BINARY
] = "and-bool",
269 [OP_OR_BOOL
- OP_BINARY
] = "or-bool",
270 [OP_SEL
- OP_BINARY
] = "select",
272 printf("\t%%r%d <- %s %s, %s\n",
274 opname
[op
- OP_BINARY
], show_pseudo(insn
->src1
), show_pseudo(insn
->src2
));
279 printf("\t%%r%d <- slice %s, %d, %d\n",
281 show_pseudo(insn
->base
), insn
->from
, insn
->len
);
284 case OP_BINCMP
... OP_BINCMP_END
: {
285 static const char *opname
[] = {
286 [OP_SET_EQ
- OP_BINCMP
] = "seteq",
287 [OP_SET_NE
- OP_BINCMP
] = "setne",
288 [OP_SET_LE
- OP_BINCMP
] = "setle",
289 [OP_SET_GE
- OP_BINCMP
] = "setge",
290 [OP_SET_LT
- OP_BINCMP
] = "setlt",
291 [OP_SET_GT
- OP_BINCMP
] = "setgt",
292 [OP_SET_BE
- OP_BINCMP
] = "setbe",
293 [OP_SET_AE
- OP_BINCMP
] = "setae",
294 [OP_SET_A
- OP_BINCMP
] = "seta",
295 [OP_SET_B
- OP_BINCMP
] = "setb",
297 printf("\t%%r%d <- %s %s, %s\n",
299 opname
[op
- OP_BINCMP
], show_pseudo(insn
->src1
), show_pseudo(insn
->src2
));
304 printf("\t%%r%d <- %s\n",
305 regno(insn
->target
), show_pseudo(insn
->src
));
307 case OP_NOT
: case OP_NEG
:
308 printf("\t%%r%d <- %s %s\n",
310 op
== OP_NOT
? "not" : "neg", show_pseudo(insn
->src1
));
313 printf("\tsetcc %s\n", show_pseudo(insn
->src
));
316 printf("\tcontext %d\n", insn
->increment
);
319 printf("\tdeathnote %%r%d\n", regno(insn
->target
));
322 printf("\top %d ???\n", op
);
326 static void show_bb(struct basic_block
*bb
)
328 struct instruction
*insn
;
330 printf("bb: %p\n", bb
);
331 printf(" %s:%d:%d\n", input_streams
[bb
->pos
.stream
].name
, bb
->pos
.line
,bb
->pos
.pos
);
333 struct basic_block
*from
;
334 FOR_EACH_PTR(bb
->parents
, from
) {
335 printf(" **from %p (%s:%d:%d)**\n", from
,
336 input_streams
[from
->pos
.stream
].name
, from
->pos
.line
, from
->pos
.pos
);
337 } END_FOR_EACH_PTR(from
);
339 FOR_EACH_PTR(bb
->insns
, insn
) {
340 show_instruction(insn
);
341 } END_FOR_EACH_PTR(insn
);
342 if (!bb_terminated(bb
))
347 static void show_uses(pseudo_t pseudo
)
349 if (pseudo
&& pseudo
->users
) {
350 struct instruction
*use
;
351 FOR_EACH_PTR(pseudo
->users
, use
) {
352 show_instruction(use
);
353 } END_FOR_EACH_PTR(use
);
357 void show_entry(struct entrypoint
*ep
)
360 struct basic_block
*bb
;
362 printf("ep %p: %s\n", ep
, show_ident(ep
->name
->ident
));
364 FOR_EACH_PTR(ep
->syms
, sym
) {
365 printf(" sym: %p %s\n", sym
, show_ident(sym
->ident
));
366 if (sym
->ctype
.modifiers
& (MOD_EXTERN
| MOD_STATIC
| MOD_ADDRESSABLE
))
367 printf("\texternal visibility\n");
368 show_uses(sym
->pseudo
);
369 } END_FOR_EACH_PTR(sym
);
373 FOR_EACH_PTR(ep
->bbs
, bb
) {
377 } END_FOR_EACH_PTR(bb
);
382 static void bind_label(struct symbol
*label
, struct basic_block
*bb
, struct position pos
)
384 if (label
->bb_target
)
385 warning(pos
, "label '%s' already bound", show_ident(label
->ident
));
386 label
->bb_target
= bb
;
389 static struct basic_block
* get_bound_block(struct entrypoint
*ep
, struct symbol
*label
)
391 struct basic_block
*bb
= label
->bb_target
;
394 label
->bb_target
= bb
= alloc_basic_block(label
->pos
);
395 bb
->flags
|= BB_REACHABLE
;
400 static void finish_block(struct entrypoint
*ep
)
402 struct basic_block
*src
= ep
->active
;
403 if (bb_reachable(src
))
407 static void add_goto(struct entrypoint
*ep
, struct basic_block
*dst
)
409 struct basic_block
*src
= ep
->active
;
410 if (bb_reachable(src
)) {
411 struct instruction
*br
= alloc_instruction(OP_BR
, NULL
);
413 add_bb(&dst
->parents
, src
);
414 add_instruction(&src
->insns
, br
);
419 static inline void use_pseudo(struct instruction
*insn
, pseudo_t pseudo
)
421 if (pseudo
&& pseudo
->type
!= PSEUDO_VOID
)
422 add_instruction(&pseudo
->users
, insn
);
425 static void add_deathnote(struct entrypoint
*ep
, pseudo_t pseudo
)
427 if (pseudo
&& pseudo
->type
== PSEUDO_REG
) {
428 struct basic_block
*bb
= ep
->active
;
429 if (!--pseudo
->usage
&& bb_reachable(bb
)) {
430 struct instruction
*dead
= alloc_instruction(OP_DEAD
, NULL
);
431 dead
->target
= pseudo
;
432 add_instruction(&bb
->insns
, dead
);
437 static void add_one_insn(struct entrypoint
*ep
, struct instruction
*insn
)
439 struct basic_block
*bb
= ep
->active
;
441 if (bb_reachable(bb
))
442 add_instruction(&bb
->insns
, insn
);
445 static void set_activeblock(struct entrypoint
*ep
, struct basic_block
*bb
)
447 if (!bb_terminated(ep
->active
))
451 if (bb_reachable(bb
))
452 add_bb(&ep
->bbs
, bb
);
455 static void add_setcc(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t val
)
457 struct basic_block
*bb
= ep
->active
;
459 if (bb_reachable(bb
)) {
460 struct instruction
*cc
= alloc_instruction(OP_SETCC
, &bool_ctype
);
463 add_one_insn(ep
, cc
);
467 static void add_branch(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t cond
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
469 struct basic_block
*bb
= ep
->active
;
470 struct instruction
*br
;
472 if (bb_reachable(bb
)) {
473 br
= alloc_instruction(OP_BR
, expr
->ctype
);
475 use_pseudo(br
, cond
);
476 br
->bb_true
= bb_true
;
477 br
->bb_false
= bb_false
;
478 add_bb(&bb_true
->parents
, bb
);
479 add_bb(&bb_false
->parents
, bb
);
480 add_one_insn(ep
, br
);
484 /* Dummy pseudo allocator */
485 static pseudo_t
alloc_pseudo(struct instruction
*def
)
488 struct pseudo
* pseudo
= __alloc_pseudo(0);
489 pseudo
->type
= PSEUDO_REG
;
496 static pseudo_t
symbol_pseudo(struct symbol
*sym
)
498 pseudo_t pseudo
= sym
->pseudo
;
501 pseudo
= __alloc_pseudo(0);
502 pseudo
->type
= PSEUDO_SYM
;
504 sym
->pseudo
= pseudo
;
506 /* Symbol pseudos have neither nr, usage nor def */
510 static pseudo_t
value_pseudo(long long val
)
512 pseudo_t pseudo
= __alloc_pseudo(0);
513 pseudo
->type
= PSEUDO_VAL
;
515 /* Value pseudos have neither nr, usage nor def */
519 static pseudo_t
argument_pseudo(int nr
)
521 pseudo_t pseudo
= __alloc_pseudo(0);
522 pseudo
->type
= PSEUDO_ARG
;
524 /* Argument pseudos have neither usage nor def */
529 * We carry the "access_data" structure around for any accesses,
530 * which simplifies things a lot. It contains all the access
531 * information in one place.
534 struct symbol
*ctype
;
535 pseudo_t address
; // pseudo containing address ..
536 pseudo_t origval
; // pseudo for original value ..
537 unsigned int offset
, alignment
; // byte offset
538 unsigned int bit_size
, bit_offset
; // which bits
542 static void finish_address_gen(struct entrypoint
*ep
, struct access_data
*ad
)
544 if (ad
->address
&& ad
->address
!= VOID
)
545 add_deathnote(ep
, ad
->address
);
548 static int linearize_simple_address(struct entrypoint
*ep
,
549 struct expression
*addr
,
550 struct access_data
*ad
)
552 if (addr
->type
== EXPR_SYMBOL
) {
553 ad
->address
= symbol_pseudo(addr
->symbol
);
556 if (addr
->type
== EXPR_BINOP
) {
557 if (addr
->right
->type
== EXPR_VALUE
) {
558 if (addr
->op
== '+') {
559 ad
->offset
+= get_expression_value(addr
->right
);
560 return linearize_simple_address(ep
, addr
->left
, ad
);
564 ad
->address
= linearize_expression(ep
, addr
);
568 static int linearize_address_gen(struct entrypoint
*ep
,
569 struct expression
*expr
,
570 struct access_data
*ad
)
572 struct symbol
*ctype
= expr
->ctype
;
578 ad
->bit_size
= ctype
->bit_size
;
579 ad
->alignment
= ctype
->ctype
.alignment
;
580 ad
->bit_offset
= ctype
->bit_offset
;
581 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
582 return linearize_simple_address(ep
, expr
->unop
, ad
);
584 warning(expr
->pos
, "generating address of non-lvalue (%d)", expr
->type
);
588 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*ad
)
590 struct instruction
*insn
;
599 insn
= alloc_instruction(OP_LOAD
, ad
->ctype
);
600 new = alloc_pseudo(insn
);
604 insn
->src
= ad
->address
;
605 insn
->offset
= ad
->offset
;
606 use_pseudo(insn
, ad
->address
);
607 add_one_insn(ep
, insn
);
611 static void add_store(struct entrypoint
*ep
, struct access_data
*ad
, pseudo_t value
)
613 struct basic_block
*bb
= ep
->active
;
615 if (bb_reachable(bb
)) {
616 struct instruction
*store
= alloc_instruction(OP_STORE
, ad
->ctype
);
617 store
->target
= value
;
618 store
->src
= ad
->address
;
619 store
->offset
= ad
->offset
;
620 use_pseudo(store
, value
);
621 use_pseudo(store
, ad
->address
);
622 add_one_insn(ep
, store
);
626 /* Target-dependent, really.. */
627 #define OFFSET_ALIGN 8
630 static pseudo_t
linearize_store_gen(struct entrypoint
*ep
,
632 struct access_data
*ad
)
635 pseudo_t shifted
, ormask
, orig
, value_mask
, newval
;
637 /* Bogus tests, but you get the idea.. */
638 if (ad
->bit_offset
& (OFFSET_ALIGN
-1))
640 if (ad
->bit_size
& (OFFSET_ALIGN
-1))
642 if (MUST_ALIGN
&& ((ad
->bit_size
>> 3) & (ad
->alignment
-1)))
645 add_store(ep
, ad
, value
);
649 mask
= ((1<<ad
->bit_size
)-1) << ad
->bit_offset
;
651 if (ad
->bit_offset
) {
653 shift
= value_pseudo(ad
->bit_offset
);
654 shifted
= add_binary_op(ep
, ad
->ctype
, OP_SHL
, value
, shift
);
655 add_deathnote(ep
, shift
);
657 orig
= add_load(ep
, ad
);
658 ormask
= value_pseudo(mask
);
659 value_mask
= add_binary_op(ep
, ad
->ctype
, OP_AND
, shifted
, ormask
);
660 add_deathnote(ep
, ormask
);
661 if (shifted
!= value
)
662 add_deathnote(ep
, shifted
);
663 newval
= add_binary_op(ep
, ad
->ctype
, OP_OR
, orig
, value_mask
);
664 add_deathnote(ep
, orig
);
665 add_deathnote(ep
, value_mask
);
667 add_store(ep
, ad
, newval
);
668 add_deathnote(ep
, newval
);
672 static pseudo_t
add_binary_op(struct entrypoint
*ep
, struct symbol
*ctype
, int op
, pseudo_t left
, pseudo_t right
)
674 struct instruction
*insn
= alloc_instruction(op
, ctype
);
675 pseudo_t target
= alloc_pseudo(insn
);
676 insn
->target
= target
;
679 use_pseudo(insn
, left
);
680 use_pseudo(insn
, right
);
681 add_one_insn(ep
, insn
);
685 static pseudo_t
add_setval(struct entrypoint
*ep
, struct symbol
*ctype
, struct expression
*val
)
687 struct instruction
*insn
= alloc_instruction(OP_SETVAL
, ctype
);
688 pseudo_t target
= alloc_pseudo(insn
);
689 insn
->target
= target
;
692 insn
->symbol
= ctype
;
693 add_one_insn(ep
, insn
);
697 static pseudo_t
linearize_load_gen(struct entrypoint
*ep
, struct access_data
*ad
)
699 pseudo_t
new = add_load(ep
, ad
);
701 if (ad
->bit_offset
) {
702 pseudo_t shift
= value_pseudo(ad
->bit_offset
);
703 pseudo_t newval
= add_binary_op(ep
, ad
->ctype
, OP_SHR
, new, shift
);
704 add_deathnote(ep
, new);
705 add_deathnote(ep
, shift
);
712 static pseudo_t
linearize_access(struct entrypoint
*ep
, struct expression
*expr
)
714 struct access_data ad
= { NULL
, };
717 if (!linearize_address_gen(ep
, expr
, &ad
))
719 value
= linearize_load_gen(ep
, &ad
);
720 finish_address_gen(ep
, &ad
);
725 static pseudo_t
linearize_inc_dec(struct entrypoint
*ep
, struct expression
*expr
, int postop
)
727 struct access_data ad
= { NULL
, };
728 pseudo_t old
, new, one
;
729 int op
= expr
->op
== SPECIAL_INCREMENT
? OP_ADD
: OP_SUB
;
731 if (!linearize_address_gen(ep
, expr
->unop
, &ad
))
734 old
= linearize_load_gen(ep
, &ad
);
735 one
= value_pseudo(1);
736 new = add_binary_op(ep
, expr
->ctype
, op
, old
, one
);
737 linearize_store_gen(ep
, new, &ad
);
738 finish_address_gen(ep
, &ad
);
740 add_deathnote(ep
, new);
743 add_deathnote(ep
, old
);
747 static pseudo_t
add_uniop(struct entrypoint
*ep
, struct expression
*expr
, int op
, pseudo_t src
)
749 struct instruction
*insn
= alloc_instruction(op
, expr
->ctype
);
750 pseudo_t
new = alloc_pseudo(insn
);
754 use_pseudo(insn
, src
);
755 add_one_insn(ep
, insn
);
756 add_deathnote(ep
, src
);
760 static pseudo_t
linearize_slice(struct entrypoint
*ep
, struct expression
*expr
)
762 pseudo_t pre
= linearize_expression(ep
, expr
->base
);
763 struct instruction
*insn
= alloc_instruction(OP_SLICE
, expr
->ctype
);
764 pseudo_t
new = alloc_pseudo(insn
);
768 insn
->from
= expr
->r_bitpos
;
769 insn
->len
= expr
->r_nrbits
;
770 use_pseudo(insn
, pre
);
771 add_one_insn(ep
, insn
);
772 add_deathnote(ep
, pre
);
776 static pseudo_t
linearize_regular_preop(struct entrypoint
*ep
, struct expression
*expr
)
778 pseudo_t pre
= linearize_expression(ep
, expr
->unop
);
783 pseudo_t zero
= value_pseudo(0);
784 return add_binary_op(ep
, expr
->ctype
, OP_SET_EQ
, pre
, zero
);
787 return add_uniop(ep
, expr
, OP_NOT
, pre
);
789 return add_uniop(ep
, expr
, OP_NEG
, pre
);
794 static pseudo_t
linearize_preop(struct entrypoint
*ep
, struct expression
*expr
)
797 * '*' is an lvalue access, and is fundamentally different
798 * from an arithmetic operation. Maybe it should have an
799 * expression type of its own..
802 return linearize_access(ep
, expr
);
803 if (expr
->op
== SPECIAL_INCREMENT
|| expr
->op
== SPECIAL_DECREMENT
)
804 return linearize_inc_dec(ep
, expr
, 0);
805 return linearize_regular_preop(ep
, expr
);
808 static pseudo_t
linearize_postop(struct entrypoint
*ep
, struct expression
*expr
)
810 return linearize_inc_dec(ep
, expr
, 1);
813 static pseudo_t
linearize_assignment(struct entrypoint
*ep
, struct expression
*expr
)
815 struct access_data ad
= { NULL
, };
816 struct expression
*target
= expr
->left
;
819 value
= linearize_expression(ep
, expr
->right
);
820 if (!linearize_address_gen(ep
, target
, &ad
))
822 if (expr
->op
!= '=') {
823 pseudo_t oldvalue
= linearize_load_gen(ep
, &ad
);
825 static const int op_trans
[] = {
826 [SPECIAL_ADD_ASSIGN
- SPECIAL_BASE
] = OP_ADD
,
827 [SPECIAL_SUB_ASSIGN
- SPECIAL_BASE
] = OP_SUB
,
828 [SPECIAL_MUL_ASSIGN
- SPECIAL_BASE
] = OP_MUL
,
829 [SPECIAL_DIV_ASSIGN
- SPECIAL_BASE
] = OP_DIV
,
830 [SPECIAL_MOD_ASSIGN
- SPECIAL_BASE
] = OP_MOD
,
831 [SPECIAL_SHL_ASSIGN
- SPECIAL_BASE
] = OP_SHL
,
832 [SPECIAL_SHR_ASSIGN
- SPECIAL_BASE
] = OP_SHR
,
833 [SPECIAL_AND_ASSIGN
- SPECIAL_BASE
] = OP_AND
,
834 [SPECIAL_OR_ASSIGN
- SPECIAL_BASE
] = OP_OR
,
835 [SPECIAL_XOR_ASSIGN
- SPECIAL_BASE
] = OP_XOR
837 dst
= add_binary_op(ep
, expr
->ctype
, op_trans
[expr
->op
- SPECIAL_BASE
], oldvalue
, value
);
838 add_deathnote(ep
, oldvalue
);
839 add_deathnote(ep
, value
);
842 value
= linearize_store_gen(ep
, value
, &ad
);
843 finish_address_gen(ep
, &ad
);
847 static pseudo_t
linearize_call_expression(struct entrypoint
*ep
, struct expression
*expr
)
849 struct expression
*arg
, *fn
;
850 struct instruction
*insn
= alloc_instruction(OP_CALL
, expr
->ctype
);
855 warning(expr
->pos
, "call with no type!");
859 FOR_EACH_PTR(expr
->args
, arg
) {
860 pseudo_t
new = linearize_expression(ep
, arg
);
861 add_pseudo(&insn
->arguments
, new);
862 use_pseudo(insn
, new);
863 } END_FOR_EACH_PTR(arg
);
869 int in
= fn
->ctype
->ctype
.in_context
;
870 int out
= fn
->ctype
->ctype
.out_context
;
871 if (in
< 0 || out
< 0)
873 context_diff
= out
- in
;
876 if (fn
->type
== EXPR_PREOP
) {
877 if (fn
->unop
->type
== EXPR_SYMBOL
) {
878 struct symbol
*sym
= fn
->unop
->symbol
;
879 if (sym
->ctype
.base_type
->type
== SYM_FN
)
883 if (fn
->type
== EXPR_SYMBOL
) {
884 insn
->func
= symbol_pseudo(fn
->symbol
);
886 insn
->func
= linearize_expression(ep
, fn
);
888 use_pseudo(insn
, insn
->func
);
890 if (expr
->ctype
!= &void_ctype
)
891 retval
= alloc_pseudo(insn
);
892 insn
->target
= retval
;
893 add_one_insn(ep
, insn
);
896 insn
= alloc_instruction(OP_CONTEXT
, &void_ctype
);
897 insn
->increment
= context_diff
;
898 add_one_insn(ep
, insn
);
904 static pseudo_t
linearize_binop(struct entrypoint
*ep
, struct expression
*expr
)
906 pseudo_t src1
, src2
, dst
;
907 static const int opcode
[] = {
908 ['+'] = OP_ADD
, ['-'] = OP_SUB
,
909 ['*'] = OP_MUL
, ['/'] = OP_DIV
,
910 ['%'] = OP_MOD
, ['&'] = OP_AND
,
911 ['|'] = OP_OR
, ['^'] = OP_XOR
,
912 [SPECIAL_LEFTSHIFT
] = OP_SHL
,
913 [SPECIAL_RIGHTSHIFT
] = OP_SHR
,
914 [SPECIAL_LOGICAL_AND
] = OP_AND_BOOL
,
915 [SPECIAL_LOGICAL_OR
] = OP_OR_BOOL
,
918 src1
= linearize_expression(ep
, expr
->left
);
919 src2
= linearize_expression(ep
, expr
->right
);
920 dst
= add_binary_op(ep
, expr
->ctype
, opcode
[expr
->op
], src1
, src2
);
921 add_deathnote(ep
, src1
);
922 add_deathnote(ep
, src2
);
926 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
928 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
930 static pseudo_t
linearize_select(struct entrypoint
*ep
, struct expression
*expr
)
932 pseudo_t cond
, true, false, res
;
934 true = linearize_expression(ep
, expr
->cond_true
);
935 false = linearize_expression(ep
, expr
->cond_false
);
936 cond
= linearize_expression(ep
, expr
->conditional
);
938 add_setcc(ep
, expr
, cond
);
940 add_deathnote(ep
, cond
);
943 res
= add_binary_op(ep
, expr
->ctype
, OP_SEL
, true, false);
944 add_deathnote(ep
, true);
945 add_deathnote(ep
, false);
949 static pseudo_t
copy_pseudo(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t src
)
951 struct basic_block
*bb
= ep
->active
;
953 if (src
->type
!= PSEUDO_REG
)
956 if (bb_reachable(bb
)) {
957 struct instruction
*new = alloc_instruction(OP_MOV
, expr
->ctype
);
958 pseudo_t dst
= alloc_pseudo(src
->def
);
961 use_pseudo(new, src
);
962 add_instruction(&bb
->insns
, new);
968 static pseudo_t
add_join_conditional(struct entrypoint
*ep
, struct expression
*expr
,
969 pseudo_t src1
, struct basic_block
*bb1
,
970 pseudo_t src2
, struct basic_block
*bb2
)
973 struct instruction
*phi_node
;
975 if (src1
== VOID
|| !bb_reachable(bb1
))
977 if (src2
== VOID
|| !bb_reachable(bb2
))
979 phi_node
= alloc_instruction(OP_PHI
, expr
->ctype
);
980 add_phi(&phi_node
->phi_list
, alloc_phi(bb1
, src1
));
981 add_phi(&phi_node
->phi_list
, alloc_phi(bb2
, src2
));
982 phi_node
->target
= target
= alloc_pseudo(phi_node
);
983 use_pseudo(phi_node
, src1
);
984 use_pseudo(phi_node
, src2
);
985 add_one_insn(ep
, phi_node
);
989 static pseudo_t
linearize_short_conditional(struct entrypoint
*ep
, struct expression
*expr
,
990 struct expression
*cond
,
991 struct expression
*expr_false
)
993 pseudo_t tst
, src1
, src2
;
994 struct basic_block
*bb_true
;
995 struct basic_block
*bb_false
= alloc_basic_block(expr_false
->pos
);
996 struct basic_block
*merge
= alloc_basic_block(expr
->pos
);
998 tst
= linearize_expression(ep
, cond
);
999 src1
= copy_pseudo(ep
, expr
, tst
);
1000 bb_true
= ep
->active
;
1001 add_branch(ep
, expr
, tst
, merge
, bb_false
);
1003 set_activeblock(ep
, bb_false
);
1004 src2
= linearize_expression(ep
, expr_false
);
1005 bb_false
= ep
->active
;
1006 set_activeblock(ep
, merge
);
1008 return add_join_conditional(ep
, expr
, src1
, bb_true
, src2
, bb_false
);
1011 static pseudo_t
linearize_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1012 struct expression
*cond
,
1013 struct expression
*expr_true
,
1014 struct expression
*expr_false
)
1016 pseudo_t src1
, src2
;
1017 struct basic_block
*bb_true
= alloc_basic_block(expr_true
->pos
);
1018 struct basic_block
*bb_false
= alloc_basic_block(expr_false
->pos
);
1019 struct basic_block
*merge
= alloc_basic_block(expr
->pos
);
1021 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
1023 set_activeblock(ep
, bb_true
);
1024 src1
= linearize_expression(ep
, expr_true
);
1025 bb_true
= ep
->active
;
1026 add_goto(ep
, merge
);
1028 set_activeblock(ep
, bb_false
);
1029 src2
= linearize_expression(ep
, expr_false
);
1030 bb_false
= ep
->active
;
1031 set_activeblock(ep
, merge
);
1033 return add_join_conditional(ep
, expr
, src1
, bb_true
, src2
, bb_false
);
1036 static pseudo_t
linearize_logical(struct entrypoint
*ep
, struct expression
*expr
)
1038 struct expression
*shortcut
;
1040 shortcut
= alloc_const_expression(expr
->pos
, expr
->op
== SPECIAL_LOGICAL_OR
);
1041 shortcut
->ctype
= expr
->ctype
;
1042 return linearize_conditional(ep
, expr
, expr
->left
, shortcut
, expr
->right
);
1045 static pseudo_t
linearize_compare(struct entrypoint
*ep
, struct expression
*expr
)
1047 static const int cmpop
[] = {
1048 ['>'] = OP_SET_GT
, ['<'] = OP_SET_LT
,
1049 [SPECIAL_EQUAL
] = OP_SET_EQ
,
1050 [SPECIAL_NOTEQUAL
] = OP_SET_NE
,
1051 [SPECIAL_GTE
] = OP_SET_GE
,
1052 [SPECIAL_LTE
] = OP_SET_LE
,
1053 [SPECIAL_UNSIGNED_LT
] = OP_SET_B
,
1054 [SPECIAL_UNSIGNED_GT
] = OP_SET_A
,
1055 [SPECIAL_UNSIGNED_LTE
] = OP_SET_BE
,
1056 [SPECIAL_UNSIGNED_GTE
] = OP_SET_AE
,
1059 pseudo_t src1
= linearize_expression(ep
, expr
->left
);
1060 pseudo_t src2
= linearize_expression(ep
, expr
->right
);
1061 pseudo_t dst
= add_binary_op(ep
, expr
->ctype
, cmpop
[expr
->op
], src1
, src2
);
1062 add_deathnote(ep
, src1
);
1063 add_deathnote(ep
, src2
);
1068 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1072 if (!expr
|| !bb_reachable(ep
->active
))
1075 switch (expr
->type
) {
1079 add_goto(ep
, expr
->value
? bb_true
: bb_false
);
1083 add_goto(ep
, expr
->fvalue
? bb_true
: bb_false
);
1087 linearize_logical_branch(ep
, expr
, bb_true
, bb_false
);
1091 cond
= linearize_compare(ep
, expr
);
1092 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1096 if (expr
->op
== '!')
1097 return linearize_cond_branch(ep
, expr
->unop
, bb_false
, bb_true
);
1100 cond
= linearize_expression(ep
, expr
);
1101 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1111 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1113 struct basic_block
*next
= alloc_basic_block(expr
->pos
);
1115 if (expr
->op
== SPECIAL_LOGICAL_OR
)
1116 linearize_cond_branch(ep
, expr
->left
, bb_true
, next
);
1118 linearize_cond_branch(ep
, expr
->left
, next
, bb_false
);
1119 set_activeblock(ep
, next
);
1120 linearize_cond_branch(ep
, expr
->right
, bb_true
, bb_false
);
1124 pseudo_t
linearize_cast(struct entrypoint
*ep
, struct expression
*expr
)
1126 pseudo_t src
, result
;
1127 struct instruction
*insn
;
1129 src
= linearize_expression(ep
, expr
->cast_expression
);
1132 if (expr
->ctype
->bit_size
< 0) {
1133 add_deathnote(ep
, src
);
1136 insn
= alloc_instruction(OP_CAST
, expr
->ctype
);
1137 result
= alloc_pseudo(insn
);
1138 insn
->target
= result
;
1140 insn
->orig_type
= expr
->cast_expression
->ctype
;
1141 use_pseudo(insn
, src
);
1142 add_one_insn(ep
, insn
);
1143 add_deathnote(ep
, src
);
1147 pseudo_t
linearize_position(struct entrypoint
*ep
, struct expression
*pos
, struct access_data
*ad
)
1149 struct expression
*init_expr
= pos
->init_expr
;
1150 pseudo_t value
= linearize_expression(ep
, init_expr
);
1152 ad
->offset
= pos
->init_offset
;
1153 linearize_store_gen(ep
, value
, ad
);
1154 add_deathnote(ep
, value
);
1158 pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*ad
)
1160 switch (initializer
->type
) {
1161 case EXPR_INITIALIZER
: {
1162 struct expression
*expr
;
1163 FOR_EACH_PTR(initializer
->expr_list
, expr
) {
1164 linearize_initializer(ep
, expr
, ad
);
1165 } END_FOR_EACH_PTR(expr
);
1169 linearize_position(ep
, initializer
, ad
);
1172 pseudo_t value
= linearize_expression(ep
, initializer
);
1173 linearize_store_gen(ep
, value
, ad
);
1174 add_deathnote(ep
, value
);
1181 void linearize_argument(struct entrypoint
*ep
, struct symbol
*arg
, int nr
)
1183 struct access_data ad
= { NULL
, };
1185 ad
.address
= symbol_pseudo(arg
);
1186 linearize_store_gen(ep
, argument_pseudo(nr
), &ad
);
1187 finish_address_gen(ep
, &ad
);
1190 pseudo_t
linearize_expression(struct entrypoint
*ep
, struct expression
*expr
)
1195 switch (expr
->type
) {
1197 return add_setval(ep
, expr
->symbol
, NULL
);
1200 return value_pseudo(expr
->value
);
1202 case EXPR_STRING
: case EXPR_FVALUE
: case EXPR_LABEL
:
1203 return add_setval(ep
, expr
->ctype
, expr
);
1205 case EXPR_STATEMENT
:
1206 return linearize_statement(ep
, expr
->statement
);
1209 return linearize_call_expression(ep
, expr
);
1212 return linearize_binop(ep
, expr
);
1215 return linearize_logical(ep
, expr
);
1218 return linearize_compare(ep
, expr
);
1221 return linearize_select(ep
, expr
);
1223 case EXPR_CONDITIONAL
:
1224 if (!expr
->cond_true
)
1225 return linearize_short_conditional(ep
, expr
, expr
->conditional
, expr
->cond_false
);
1227 return linearize_conditional(ep
, expr
, expr
->conditional
,
1228 expr
->cond_true
, expr
->cond_false
);
1231 pseudo_t left
= linearize_expression(ep
, expr
->left
);
1232 add_deathnote(ep
, left
);
1233 return linearize_expression(ep
, expr
->right
);
1236 case EXPR_ASSIGNMENT
:
1237 return linearize_assignment(ep
, expr
);
1240 return linearize_preop(ep
, expr
);
1243 return linearize_postop(ep
, expr
);
1246 case EXPR_IMPLIED_CAST
:
1247 return linearize_cast(ep
, expr
);
1250 return linearize_slice(ep
, expr
);
1252 case EXPR_INITIALIZER
:
1254 warning(expr
->pos
, "unexpected initializer expression (%d %d)", expr
->type
, expr
->op
);
1257 warning(expr
->pos
, "unknown expression (%d %d)", expr
->type
, expr
->op
);
1263 static void linearize_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
)
1265 struct access_data ad
= { NULL
, };
1267 if (!sym
->initializer
)
1270 ad
.address
= symbol_pseudo(sym
);
1271 linearize_initializer(ep
, sym
->initializer
, &ad
);
1272 finish_address_gen(ep
, &ad
);
1275 static pseudo_t
linearize_compound_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1278 struct statement
*s
;
1280 struct symbol
*ret
= stmt
->ret
;
1282 concat_symbol_list(stmt
->syms
, &ep
->syms
);
1285 ret
->bb_target
= alloc_basic_block(stmt
->pos
);
1287 FOR_EACH_PTR(stmt
->syms
, sym
) {
1288 linearize_one_symbol(ep
, sym
);
1289 } END_FOR_EACH_PTR(sym
);
1292 FOR_EACH_PTR(stmt
->stmts
, s
) {
1293 add_deathnote(ep
, pseudo
);
1294 pseudo
= linearize_statement(ep
, s
);
1295 } END_FOR_EACH_PTR(s
);
1298 struct basic_block
*bb
= ret
->bb_target
;
1299 struct instruction
*phi
= first_instruction(bb
->insns
);
1304 set_activeblock(ep
, bb
);
1305 if (phi_list_size(phi
->phi_list
)==1) {
1306 pseudo
= first_phi(phi
->phi_list
)->pseudo
;
1307 delete_last_instruction(&bb
->insns
);
1316 pseudo_t
linearize_internal(struct entrypoint
*ep
, struct statement
*stmt
)
1318 struct instruction
*insn
= alloc_instruction(OP_CONTEXT
, &void_ctype
);
1319 struct expression
*expr
= stmt
->expression
;
1322 if (expr
->type
== EXPR_VALUE
)
1323 value
= expr
->value
;
1325 insn
->increment
= value
;
1326 add_one_insn(ep
, insn
);
1330 pseudo_t
linearize_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1335 switch (stmt
->type
) {
1340 return linearize_internal(ep
, stmt
);
1342 case STMT_EXPRESSION
:
1343 return linearize_expression(ep
, stmt
->expression
);
1350 struct expression
*expr
= stmt
->expression
;
1351 struct basic_block
*bb_return
= stmt
->ret_target
->bb_target
;
1352 struct basic_block
*active
;
1353 pseudo_t src
= linearize_expression(ep
, expr
);
1354 active
= ep
->active
;
1355 add_goto(ep
, bb_return
);
1356 if (active
&& src
!= &void_pseudo
) {
1357 struct instruction
*phi_node
= first_instruction(bb_return
->insns
);
1359 phi_node
= alloc_instruction(OP_PHI
, expr
->ctype
);
1360 phi_node
->target
= alloc_pseudo(phi_node
);
1361 add_instruction(&bb_return
->insns
, phi_node
);
1363 use_pseudo(phi_node
, src
);
1364 add_phi(&phi_node
->phi_list
, alloc_phi(active
, src
));
1370 struct basic_block
*bb
= get_bound_block(ep
, stmt
->case_label
);
1371 set_activeblock(ep
, bb
);
1372 linearize_statement(ep
, stmt
->case_statement
);
1377 struct symbol
*label
= stmt
->label_identifier
;
1378 struct basic_block
*bb
;
1381 bb
= get_bound_block(ep
, stmt
->label_identifier
);
1382 set_activeblock(ep
, bb
);
1383 linearize_statement(ep
, stmt
->label_statement
);
1390 struct expression
*expr
;
1391 struct instruction
*goto_ins
;
1394 if (stmt
->goto_label
) {
1395 add_goto(ep
, get_bound_block(ep
, stmt
->goto_label
));
1399 expr
= stmt
->goto_expression
;
1403 /* This can happen as part of simplification */
1404 if (expr
->type
== EXPR_LABEL
) {
1405 add_goto(ep
, get_bound_block(ep
, expr
->label_symbol
));
1409 pseudo
= linearize_expression(ep
, expr
);
1410 goto_ins
= alloc_instruction(OP_COMPUTEDGOTO
, NULL
);
1411 use_pseudo(goto_ins
, pseudo
);
1412 add_one_insn(ep
, goto_ins
);
1413 goto_ins
->target
= pseudo
;
1415 FOR_EACH_PTR(stmt
->target_list
, sym
) {
1416 struct basic_block
*bb_computed
= get_bound_block(ep
, sym
);
1417 struct multijmp
*jmp
= alloc_multijmp(bb_computed
, 1, 0);
1418 add_multijmp(&goto_ins
->multijmp_list
, jmp
);
1419 add_bb(&bb_computed
->parents
, ep
->active
);
1420 } END_FOR_EACH_PTR(sym
);
1427 return linearize_compound_statement(ep
, stmt
);
1430 * This could take 'likely/unlikely' into account, and
1431 * switch the arms around appropriately..
1434 struct basic_block
*bb_true
, *bb_false
, *endif
;
1435 struct expression
*cond
= stmt
->if_conditional
;
1437 bb_true
= alloc_basic_block(stmt
->pos
);
1438 bb_false
= endif
= alloc_basic_block(stmt
->pos
);
1440 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
1442 set_activeblock(ep
, bb_true
);
1443 linearize_statement(ep
, stmt
->if_true
);
1445 if (stmt
->if_false
) {
1446 endif
= alloc_basic_block(stmt
->pos
);
1447 add_goto(ep
, endif
);
1448 set_activeblock(ep
, bb_false
);
1449 linearize_statement(ep
, stmt
->if_false
);
1451 set_activeblock(ep
, endif
);
1457 struct instruction
*switch_ins
;
1458 struct basic_block
*switch_end
= alloc_basic_block(stmt
->pos
);
1461 pseudo
= linearize_expression(ep
, stmt
->switch_expression
);
1462 switch_ins
= alloc_instruction(OP_SWITCH
, NULL
);
1463 switch_ins
->cond
= pseudo
;
1464 use_pseudo(switch_ins
, pseudo
);
1465 add_one_insn(ep
, switch_ins
);
1467 FOR_EACH_PTR(stmt
->switch_case
->symbol_list
, sym
) {
1468 struct statement
*case_stmt
= sym
->stmt
;
1469 struct basic_block
*bb_case
= get_bound_block(ep
, sym
);
1470 struct multijmp
*jmp
;
1472 if (!case_stmt
->case_expression
) {
1473 jmp
= alloc_multijmp(bb_case
, 1, 0);
1477 begin
= end
= case_stmt
->case_expression
->value
;
1478 if (case_stmt
->case_to
)
1479 end
= case_stmt
->case_to
->value
;
1481 jmp
= alloc_multijmp(bb_case
, end
, begin
);
1483 jmp
= alloc_multijmp(bb_case
, begin
, end
);
1486 add_multijmp(&switch_ins
->multijmp_list
, jmp
);
1487 add_bb(&bb_case
->parents
, ep
->active
);
1488 } END_FOR_EACH_PTR(sym
);
1490 bind_label(stmt
->switch_break
, switch_end
, stmt
->pos
);
1492 /* And linearize the actual statement */
1493 linearize_statement(ep
, stmt
->switch_statement
);
1494 set_activeblock(ep
, switch_end
);
1499 case STMT_ITERATOR
: {
1500 struct statement
*pre_statement
= stmt
->iterator_pre_statement
;
1501 struct expression
*pre_condition
= stmt
->iterator_pre_condition
;
1502 struct statement
*statement
= stmt
->iterator_statement
;
1503 struct statement
*post_statement
= stmt
->iterator_post_statement
;
1504 struct expression
*post_condition
= stmt
->iterator_post_condition
;
1505 struct basic_block
*loop_top
, *loop_body
, *loop_continue
, *loop_end
;
1507 concat_symbol_list(stmt
->iterator_syms
, &ep
->syms
);
1508 linearize_statement(ep
, pre_statement
);
1510 loop_body
= loop_top
= alloc_basic_block(stmt
->pos
);
1511 loop_continue
= alloc_basic_block(stmt
->pos
);
1512 loop_end
= alloc_basic_block(stmt
->pos
);
1514 if (pre_condition
== post_condition
) {
1515 loop_top
= alloc_basic_block(stmt
->pos
);
1516 loop_top
->flags
|= BB_REACHABLE
;
1517 set_activeblock(ep
, loop_top
);
1520 loop_top
->flags
|= BB_REACHABLE
;
1522 linearize_cond_branch(ep
, pre_condition
, loop_body
, loop_end
);
1524 bind_label(stmt
->iterator_continue
, loop_continue
, stmt
->pos
);
1525 bind_label(stmt
->iterator_break
, loop_end
, stmt
->pos
);
1527 set_activeblock(ep
, loop_body
);
1528 linearize_statement(ep
, statement
);
1529 add_goto(ep
, loop_continue
);
1531 if (post_condition
) {
1532 set_activeblock(ep
, loop_continue
);
1533 linearize_statement(ep
, post_statement
);
1534 if (pre_condition
== post_condition
)
1535 add_goto(ep
, loop_top
);
1537 linearize_cond_branch(ep
, post_condition
, loop_top
, loop_end
);
1540 set_activeblock(ep
, loop_end
);
1550 void mark_bb_reachable(struct basic_block
*bb
)
1552 struct basic_block
*child
;
1553 struct terminator_iterator term
;
1554 struct basic_block_list
*bbstack
= NULL
;
1556 if (!bb
|| bb
->flags
& BB_REACHABLE
)
1559 add_bb(&bbstack
, bb
);
1561 bb
= delete_last_basic_block(&bbstack
);
1562 if (bb
->flags
& BB_REACHABLE
)
1564 bb
->flags
|= BB_REACHABLE
;
1565 init_terminator_iterator(last_instruction(bb
->insns
), &term
);
1566 while ((child
=next_terminator_bb(&term
)) != NULL
) {
1567 if (!(child
->flags
& BB_REACHABLE
))
1568 add_bb(&bbstack
, child
);
1573 void remove_unreachable_bbs(struct entrypoint
*ep
)
1575 struct basic_block
*bb
, *child
;
1576 struct terminator_iterator term
;
1578 FOR_EACH_PTR(ep
->bbs
, bb
) {
1579 bb
->flags
&= ~BB_REACHABLE
;
1580 } END_FOR_EACH_PTR(bb
);
1582 mark_bb_reachable(ep
->entry
);
1583 FOR_EACH_PTR(ep
->bbs
, bb
) {
1584 if (bb
->flags
& BB_REACHABLE
)
1586 init_terminator_iterator(last_instruction(bb
->insns
), &term
);
1587 while ((child
=next_terminator_bb(&term
)) != NULL
)
1588 replace_basic_block_list(child
->parents
, bb
, NULL
);
1589 DELETE_CURRENT_PTR(bb
);
1590 }END_FOR_EACH_PTR(bb
);
1593 void pack_basic_blocks(struct entrypoint
*ep
)
1595 struct basic_block
*bb
;
1597 remove_unreachable_bbs(ep
);
1598 FOR_EACH_PTR(ep
->bbs
, bb
) {
1599 struct terminator_iterator term
;
1600 struct instruction
*jmp
;
1601 struct basic_block
*target
, *sibling
, *parent
;
1604 if (!is_branch_goto(jmp
=last_instruction(bb
->insns
)))
1607 target
= jmp
->bb_true
? jmp
->bb_true
: jmp
->bb_false
;
1610 parents
= bb_list_size(target
->parents
);
1611 if (target
== ep
->entry
)
1613 if (parents
!= 1 && jmp
!= first_instruction(bb
->insns
))
1616 /* Transfer the parents' terminator to target directly. */
1617 replace_basic_block_list(target
->parents
, bb
, NULL
);
1618 FOR_EACH_PTR(bb
->parents
, parent
) {
1619 init_terminator_iterator(last_instruction(parent
->insns
), &term
);
1620 while ((sibling
=next_terminator_bb(&term
)) != NULL
) {
1621 if (sibling
== bb
) {
1622 replace_terminator_bb(&term
, target
);
1623 add_bb(&target
->parents
, parent
);
1626 } END_FOR_EACH_PTR(parent
);
1628 /* Move the instructions to the target block. */
1629 delete_last_instruction(&bb
->insns
);
1631 concat_instruction_list(target
->insns
, &bb
->insns
);
1632 free_instruction_list(&target
->insns
);
1633 target
->insns
= bb
->insns
;
1635 if (bb
== ep
->entry
)
1637 DELETE_CURRENT_PTR(bb
);
1638 }END_FOR_EACH_PTR(bb
);
1642 * Dammit, if we have a phi-node followed by a conditional
1643 * branch on that phi-node, we should damn well be able to
1644 * do something about the source. Maybe.
1646 static void rewrite_branch(struct basic_block
*bb
,
1647 struct basic_block
**ptr
,
1648 struct basic_block
*old
,
1649 struct basic_block
*new)
1652 add_bb(&new->parents
, bb
);
1654 * FIXME!!! We should probably also remove bb from "old->parents",
1655 * but we need to be careful that bb isn't a parent some other way.
1660 * Return the known truth value of a pseudo, or -1 if
1663 static int pseudo_truth_value(pseudo_t pseudo
)
1665 switch (pseudo
->type
) {
1667 return !!pseudo
->value
;
1670 struct instruction
*insn
= pseudo
->def
;
1671 if (insn
->opcode
== OP_SETVAL
&& insn
->target
== pseudo
) {
1672 struct expression
*expr
= insn
->val
;
1674 /* A symbol address is always considered true.. */
1677 if (expr
->type
== EXPR_VALUE
)
1678 return !!expr
->value
;
1688 static void try_to_simplify_bb(struct entrypoint
*ep
, struct basic_block
*bb
,
1689 struct instruction
*first
, struct instruction
*second
)
1693 FOR_EACH_PTR(first
->phi_list
, phi
) {
1694 struct basic_block
*source
= phi
->source
, *target
;
1695 pseudo_t pseudo
= phi
->pseudo
;
1696 struct instruction
*br
;
1699 br
= last_instruction(source
->insns
);
1702 if (br
->opcode
!= OP_BR
)
1705 true = pseudo_truth_value(pseudo
);
1708 target
= true ? second
->bb_true
: second
->bb_false
;
1709 if (br
->bb_true
== bb
)
1710 rewrite_branch(source
, &br
->bb_true
, bb
, target
);
1711 if (br
->bb_false
== bb
)
1712 rewrite_branch(source
, &br
->bb_false
, bb
, target
);
1713 } END_FOR_EACH_PTR(phi
);
1716 static inline int linearize_insn_list(struct instruction_list
*list
, struct instruction
**arr
, int nr
)
1718 return linearize_ptr_list((struct ptr_list
*)list
, (void **)arr
, nr
);
1721 static void simplify_phi_nodes(struct entrypoint
*ep
)
1723 struct basic_block
*bb
;
1725 FOR_EACH_PTR(ep
->bbs
, bb
) {
1726 struct instruction
*insns
[2], *first
, *second
;
1728 if (linearize_insn_list(bb
->insns
, insns
, 2) < 2)
1734 if (first
->opcode
!= OP_PHI
)
1736 if (second
->opcode
!= OP_BR
)
1738 if (first
->target
!= second
->cond
)
1740 try_to_simplify_bb(ep
, bb
, first
, second
);
1741 } END_FOR_EACH_PTR(bb
);
1744 static void create_phi_copy(struct basic_block
*bb
, struct instruction
*phi
,
1745 pseudo_t src
, pseudo_t dst
)
1747 struct instruction
*insn
= last_instruction(bb
->insns
);
1748 struct instruction
*new = alloc_instruction(OP_MOV
, phi
->type
);
1750 delete_last_instruction(&bb
->insns
);
1753 use_pseudo(new, src
);
1754 add_instruction(&bb
->insns
, new);
1756 if (src
->type
== PSEUDO_REG
) {
1757 struct instruction
*dead
= alloc_instruction(OP_DEAD
, NULL
);
1759 add_instruction(&bb
->insns
, dead
);
1762 /* And add back the last instruction */
1763 add_instruction(&bb
->insns
, insn
);
1766 static void remove_one_phi_node(struct entrypoint
*ep
,
1767 struct basic_block
*bb
,
1768 struct instruction
*insn
)
1771 pseudo_t target
= insn
->target
;
1773 FOR_EACH_PTR(insn
->phi_list
, node
) {
1774 create_phi_copy(node
->source
, insn
, node
->pseudo
, target
);
1775 } END_FOR_EACH_PTR(node
);
1778 static void remove_phi_nodes(struct entrypoint
*ep
)
1780 struct basic_block
*bb
;
1781 FOR_EACH_PTR(ep
->bbs
, bb
) {
1782 struct instruction
*insn
= first_instruction(bb
->insns
);
1783 if (insn
&& insn
->opcode
== OP_PHI
)
1784 remove_one_phi_node(ep
, bb
, insn
);
1785 } END_FOR_EACH_PTR(bb
);
1788 struct entrypoint
*linearize_symbol(struct symbol
*sym
)
1790 struct symbol
*base_type
;
1791 struct entrypoint
*ret_ep
= NULL
;
1795 base_type
= sym
->ctype
.base_type
;
1798 if (base_type
->type
== SYM_FN
) {
1799 if (base_type
->stmt
) {
1800 struct entrypoint
*ep
= alloc_entrypoint();
1801 struct basic_block
*bb
= alloc_basic_block(sym
->pos
);
1808 bb
->flags
|= BB_REACHABLE
;
1809 set_activeblock(ep
, bb
);
1810 concat_symbol_list(base_type
->arguments
, &ep
->syms
);
1812 /* FIXME!! We should do something else about varargs.. */
1814 FOR_EACH_PTR(base_type
->arguments
, arg
) {
1815 linearize_argument(ep
, arg
, ++i
);
1816 } END_FOR_EACH_PTR(arg
);
1818 result
= linearize_statement(ep
, base_type
->stmt
);
1819 if (bb_reachable(ep
->active
) && !bb_terminated(ep
->active
)) {
1820 struct symbol
*ret_type
= base_type
->ctype
.base_type
;
1821 struct instruction
*insn
= alloc_instruction(OP_RET
, ret_type
);
1824 use_pseudo(insn
, result
);
1825 add_one_insn(ep
, insn
);
1829 * Questionable conditional branch simplification.
1830 * This short-circuits branches to conditional branches,
1831 * and leaves the phi-nodes "dangling" in the old
1832 * basic block - the nodes are no longer attached to
1833 * where the uses are. But it can still be considered
1834 * SSA if you just look at it sideways..
1836 simplify_phi_nodes(ep
);
1839 * WARNING!! The removal of phi nodes will make the
1840 * tree no longer valid SSA format. We do it here
1841 * to make the linearized code look more like real
1842 * assembly code, but we should do all the SSA-based
1843 * optimizations (CSE etc) _before_ this point.
1845 remove_phi_nodes(ep
);
1847 pack_basic_blocks(ep
);