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
20 #include "expression.h"
21 #include "linearize.h"
25 pseudo_t
linearize_statement(struct entrypoint
*ep
, struct statement
*stmt
);
26 pseudo_t
linearize_expression(struct entrypoint
*ep
, struct expression
*expr
);
28 static pseudo_t
add_binary_op(struct entrypoint
*ep
, struct symbol
*ctype
, int op
, pseudo_t left
, pseudo_t right
);
29 static pseudo_t
add_setval(struct entrypoint
*ep
, struct symbol
*ctype
, struct expression
*val
);
30 static void linearize_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
);
33 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*);
34 pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*);
36 struct pseudo void_pseudo
= {};
38 static struct position current_pos
;
40 static struct instruction
*alloc_instruction(int opcode
, int size
)
42 struct instruction
* insn
= __alloc_instruction(0);
43 insn
->opcode
= opcode
;
45 insn
->pos
= current_pos
;
49 static inline int type_size(struct symbol
*type
)
51 return type
? type
->bit_size
> 0 ? type
->bit_size
: 0 : 0;
54 static struct instruction
*alloc_typed_instruction(int opcode
, struct symbol
*type
)
56 return alloc_instruction(opcode
, type_size(type
));
59 static struct entrypoint
*alloc_entrypoint(void)
61 return __alloc_entrypoint(0);
64 static struct basic_block
*alloc_basic_block(struct entrypoint
*ep
, struct position pos
)
66 struct basic_block
*bb
= __alloc_basic_block(0);
73 static struct multijmp
* alloc_multijmp(struct basic_block
*target
, int begin
, int end
)
75 struct multijmp
*multijmp
= __alloc_multijmp(0);
76 multijmp
->target
= target
;
77 multijmp
->begin
= begin
;
82 static inline int regno(pseudo_t n
)
85 if (n
&& n
->type
== PSEUDO_REG
)
90 const char *show_pseudo(pseudo_t pseudo
)
93 static char buffer
[4][64];
101 buf
= buffer
[3 & ++n
];
102 switch(pseudo
->type
) {
104 struct symbol
*sym
= pseudo
->sym
;
105 struct expression
*expr
;
107 if (sym
->bb_target
) {
108 snprintf(buf
, 64, ".L%p", sym
->bb_target
);
112 snprintf(buf
, 64, "%s", show_ident(sym
->ident
));
115 expr
= sym
->initializer
;
116 snprintf(buf
, 64, "<anon symbol:%p>", sym
);
117 switch (expr
->type
) {
119 snprintf(buf
, 64, "<symbol value: %lld>", expr
->value
);
122 return show_string(expr
->string
);
129 i
= snprintf(buf
, 64, "%%r%d", pseudo
->nr
);
131 sprintf(buf
+i
, "(%s)", show_ident(pseudo
->ident
));
134 long long value
= pseudo
->value
;
135 if (value
> 1000 || value
< -1000)
136 snprintf(buf
, 64, "$%#llx", value
);
138 snprintf(buf
, 64, "$%lld", value
);
142 snprintf(buf
, 64, "%%arg%d", pseudo
->nr
);
145 i
= snprintf(buf
, 64, "%%phi%d", pseudo
->nr
);
147 sprintf(buf
+i
, "(%s)", show_ident(pseudo
->ident
));
150 snprintf(buf
, 64, "<bad pseudo type %d>", pseudo
->type
);
155 static const char* opcodes
[] = {
156 [OP_BADOP
] = "bad_op",
159 [OP_ENTRY
] = "<entry-point>",
164 [OP_SWITCH
] = "switch",
165 [OP_INVOKE
] = "invoke",
166 [OP_COMPUTEDGOTO
] = "jmp *",
167 [OP_UNWIND
] = "unwind",
186 [OP_AND_BOOL
] = "and-bool",
187 [OP_OR_BOOL
] = "or-bool",
189 /* Binary comparison */
190 [OP_SET_EQ
] = "seteq",
191 [OP_SET_NE
] = "setne",
192 [OP_SET_LE
] = "setle",
193 [OP_SET_GE
] = "setge",
194 [OP_SET_LT
] = "setlt",
195 [OP_SET_GT
] = "setgt",
198 [OP_SET_BE
] = "setbe",
199 [OP_SET_AE
] = "setae",
205 /* Special three-input */
209 [OP_MALLOC
] = "malloc",
211 [OP_ALLOCA
] = "alloca",
213 [OP_STORE
] = "store",
215 [OP_SYMADDR
] = "symaddr",
216 [OP_GET_ELEMENT_PTR
] = "getelem",
220 [OP_PHISOURCE
] = "phisrc",
222 [OP_SCAST
] = "scast",
223 [OP_FPCAST
] = "fpcast",
224 [OP_PTRCAST
] = "ptrcast",
226 [OP_VANEXT
] = "va_next",
227 [OP_VAARG
] = "va_arg",
228 [OP_SLICE
] = "slice",
232 [OP_DEATHNOTE
] = "dead",
235 /* Sparse tagging (line numbers, context, whatever) */
236 [OP_CONTEXT
] = "context",
237 [OP_RANGE
] = "range-check",
240 static char *show_asm_constraints(char *buf
, const char *sep
, struct asm_constraint_list
*list
)
242 struct asm_constraint
*entry
;
244 FOR_EACH_PTR(list
, entry
) {
245 buf
+= sprintf(buf
, "%s\"%s\"", sep
, entry
->constraint
);
247 buf
+= sprintf(buf
, " (%s)", show_pseudo(entry
->pseudo
));
249 buf
+= sprintf(buf
, " [%s]", show_ident(entry
->ident
));
251 } END_FOR_EACH_PTR(entry
);
255 static char *show_asm(char *buf
, struct instruction
*insn
)
257 struct asm_rules
*rules
= insn
->asm_rules
;
259 buf
+= sprintf(buf
, "\"%s\"", insn
->string
);
260 buf
= show_asm_constraints(buf
, "\n\t\tout: ", rules
->outputs
);
261 buf
= show_asm_constraints(buf
, "\n\t\tin: ", rules
->inputs
);
262 buf
= show_asm_constraints(buf
, "\n\t\tclobber: ", rules
->clobbers
);
266 const char *show_instruction(struct instruction
*insn
)
268 int opcode
= insn
->opcode
;
269 static char buffer
[1024];
274 buf
+= sprintf(buf
, "# ");
276 if (opcode
< sizeof(opcodes
)/sizeof(char *)) {
277 const char *op
= opcodes
[opcode
];
279 buf
+= sprintf(buf
, "opcode:%d", opcode
);
281 buf
+= sprintf(buf
, "%s", op
);
283 buf
+= sprintf(buf
, ".%d", insn
->size
);
284 memset(buf
, ' ', 20);
288 if (buf
< buffer
+ 12)
292 if (insn
->src
&& insn
->src
!= VOID
)
293 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->src
));
296 if (insn
->bb_true
&& insn
->bb_false
) {
297 buf
+= sprintf(buf
, "%s, .L%p, .L%p", show_pseudo(insn
->cond
), insn
->bb_true
, insn
->bb_false
);
300 buf
+= sprintf(buf
, ".L%p", insn
->bb_true
? insn
->bb_true
: insn
->bb_false
);
304 struct symbol
*sym
= insn
->symbol
->sym
;
305 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
307 if (sym
->bb_target
) {
308 buf
+= sprintf(buf
, ".L%p", sym
->bb_target
);
312 buf
+= sprintf(buf
, "%s", show_ident(sym
->ident
));
315 buf
+= sprintf(buf
, "<anon symbol:%p>", sym
);
320 struct expression
*expr
= insn
->val
;
321 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
324 buf
+= sprintf(buf
, "%s", "<none>");
328 switch (expr
->type
) {
330 buf
+= sprintf(buf
, "%lld", expr
->value
);
333 buf
+= sprintf(buf
, "%Lf", expr
->fvalue
);
336 buf
+= sprintf(buf
, "%.40s", show_string(expr
->string
));
339 buf
+= sprintf(buf
, "%s", show_ident(expr
->symbol
->ident
));
342 buf
+= sprintf(buf
, ".L%p", expr
->symbol
->bb_target
);
345 buf
+= sprintf(buf
, "SETVAL EXPR TYPE %d", expr
->type
);
350 struct multijmp
*jmp
;
351 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
352 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
353 if (jmp
->begin
== jmp
->end
)
354 buf
+= sprintf(buf
, ", %d -> .L%p", jmp
->begin
, jmp
->target
);
355 else if (jmp
->begin
< jmp
->end
)
356 buf
+= sprintf(buf
, ", %d ... %d -> .L%p", jmp
->begin
, jmp
->end
, jmp
->target
);
358 buf
+= sprintf(buf
, ", default -> .L%p", jmp
->target
);
359 } END_FOR_EACH_PTR(jmp
);
362 case OP_COMPUTEDGOTO
: {
363 struct multijmp
*jmp
;
364 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
365 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
366 buf
+= sprintf(buf
, ", .L%p", jmp
->target
);
367 } END_FOR_EACH_PTR(jmp
);
372 struct instruction
*phi
;
373 buf
+= sprintf(buf
, "%s <- %s ", show_pseudo(insn
->target
), show_pseudo(insn
->phi_src
));
374 FOR_EACH_PTR(insn
->phi_users
, phi
) {
375 buf
+= sprintf(buf
, " (%s)", show_pseudo(phi
->target
));
376 } END_FOR_EACH_PTR(phi
);
382 const char *s
= " <-";
383 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
384 FOR_EACH_PTR(insn
->phi_list
, phi
) {
385 buf
+= sprintf(buf
, "%s %s", s
, show_pseudo(phi
));
387 } END_FOR_EACH_PTR(phi
);
390 case OP_LOAD
: case OP_LNOP
:
391 buf
+= sprintf(buf
, "%s <- %d[%s]", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
393 case OP_STORE
: case OP_SNOP
:
394 buf
+= sprintf(buf
, "%s -> %d[%s]", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
398 if (insn
->target
&& insn
->target
!= VOID
)
399 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
400 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->func
));
401 FOR_EACH_PTR(insn
->arguments
, arg
) {
402 buf
+= sprintf(buf
, ", %s", show_pseudo(arg
));
403 } END_FOR_EACH_PTR(arg
);
410 buf
+= sprintf(buf
, "%s <- (%d) %s",
411 show_pseudo(insn
->target
),
412 type_size(insn
->orig_type
),
413 show_pseudo(insn
->src
));
415 case OP_BINARY
... OP_BINARY_END
:
416 case OP_BINCMP
... OP_BINCMP_END
:
417 buf
+= sprintf(buf
, "%s <- %s, %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
), show_pseudo(insn
->src2
));
421 buf
+= sprintf(buf
, "%s <- %s, %s, %s", show_pseudo(insn
->target
),
422 show_pseudo(insn
->src1
), show_pseudo(insn
->src2
), show_pseudo(insn
->src3
));
426 buf
+= sprintf(buf
, "%s <- %s, %d, %d", show_pseudo(insn
->target
), show_pseudo(insn
->base
), insn
->from
, insn
->len
);
429 case OP_NOT
: case OP_NEG
:
430 buf
+= sprintf(buf
, "%s <- %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
));
434 buf
+= sprintf(buf
, "%s%d", insn
->check
? "check: " : "", insn
->increment
);
437 buf
+= sprintf(buf
, "%s between %s..%s", show_pseudo(insn
->src1
), show_pseudo(insn
->src2
), show_pseudo(insn
->src3
));
440 buf
+= sprintf(buf
, "%s <- %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
));
443 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
446 buf
= show_asm(buf
, insn
);
451 do { --buf
; } while (*buf
== ' ');
456 void show_bb(struct basic_block
*bb
)
458 struct instruction
*insn
;
460 printf(".L%p:\n", bb
);
462 pseudo_t needs
, defines
;
463 printf("%s:%d\n", stream_name(bb
->pos
.stream
), bb
->pos
.line
);
465 FOR_EACH_PTR(bb
->needs
, needs
) {
466 struct instruction
*def
= needs
->def
;
467 if (def
->opcode
!= OP_PHI
) {
468 printf(" **uses %s (from .L%p)**\n", show_pseudo(needs
), def
->bb
);
471 const char *sep
= " ";
472 printf(" **uses %s (from", show_pseudo(needs
));
473 FOR_EACH_PTR(def
->phi_list
, phi
) {
476 printf("%s(%s:.L%p)", sep
, show_pseudo(phi
), phi
->def
->bb
);
478 } END_FOR_EACH_PTR(phi
);
481 } END_FOR_EACH_PTR(needs
);
483 FOR_EACH_PTR(bb
->defines
, defines
) {
484 printf(" **defines %s **\n", show_pseudo(defines
));
485 } END_FOR_EACH_PTR(defines
);
488 struct basic_block
*from
;
489 FOR_EACH_PTR(bb
->parents
, from
) {
490 printf(" **from %p (%s:%d:%d)**\n", from
,
491 stream_name(from
->pos
.stream
), from
->pos
.line
, from
->pos
.pos
);
492 } END_FOR_EACH_PTR(from
);
496 struct basic_block
*to
;
497 FOR_EACH_PTR(bb
->children
, to
) {
498 printf(" **to %p (%s:%d:%d)**\n", to
,
499 stream_name(to
->pos
.stream
), to
->pos
.line
, to
->pos
.pos
);
500 } END_FOR_EACH_PTR(to
);
504 FOR_EACH_PTR(bb
->insns
, insn
) {
505 if (!insn
->bb
&& verbose
< 2)
507 printf("\t%s\n", show_instruction(insn
));
508 } END_FOR_EACH_PTR(insn
);
509 if (!bb_terminated(bb
))
513 static void show_symbol_usage(pseudo_t pseudo
)
517 FOR_EACH_PTR(pseudo
->users
, pp
) {
518 struct instruction
*insn
= container(pp
, struct instruction
, src
);
519 printf("\t%s\n", show_instruction(insn
));
520 } END_FOR_EACH_PTR(pp
);
524 void show_entry(struct entrypoint
*ep
)
527 struct basic_block
*bb
;
529 printf("%s:\n", show_ident(ep
->name
->ident
));
532 printf("ep %p: %s\n", ep
, show_ident(ep
->name
->ident
));
534 FOR_EACH_PTR(ep
->syms
, sym
) {
537 if (!sym
->pseudo
->users
)
539 printf(" sym: %p %s\n", sym
, show_ident(sym
->ident
));
540 if (sym
->ctype
.modifiers
& (MOD_EXTERN
| MOD_STATIC
| MOD_ADDRESSABLE
))
541 printf("\texternal visibility\n");
542 show_symbol_usage(sym
->pseudo
);
543 } END_FOR_EACH_PTR(sym
);
548 FOR_EACH_PTR(ep
->bbs
, bb
) {
551 if (!bb
->parents
&& !bb
->children
&& !bb
->insns
&& verbose
< 2)
555 } END_FOR_EACH_PTR(bb
);
560 static void bind_label(struct symbol
*label
, struct basic_block
*bb
, struct position pos
)
562 if (label
->bb_target
)
563 warning(pos
, "label '%s' already bound", show_ident(label
->ident
));
564 label
->bb_target
= bb
;
567 static struct basic_block
* get_bound_block(struct entrypoint
*ep
, struct symbol
*label
)
569 struct basic_block
*bb
= label
->bb_target
;
572 bb
= alloc_basic_block(ep
, label
->pos
);
573 label
->bb_target
= bb
;
578 static void finish_block(struct entrypoint
*ep
)
580 struct basic_block
*src
= ep
->active
;
581 if (bb_reachable(src
))
585 static void add_goto(struct entrypoint
*ep
, struct basic_block
*dst
)
587 struct basic_block
*src
= ep
->active
;
588 if (bb_reachable(src
)) {
589 struct instruction
*br
= alloc_instruction(OP_BR
, 0);
591 add_bb(&dst
->parents
, src
);
592 add_bb(&src
->children
, dst
);
594 add_instruction(&src
->insns
, br
);
599 static void add_one_insn(struct entrypoint
*ep
, struct instruction
*insn
)
601 struct basic_block
*bb
= ep
->active
;
603 if (bb_reachable(bb
)) {
605 add_instruction(&bb
->insns
, insn
);
609 static void set_activeblock(struct entrypoint
*ep
, struct basic_block
*bb
)
611 if (!bb_terminated(ep
->active
))
615 if (bb_reachable(bb
))
616 add_bb(&ep
->bbs
, bb
);
619 static void remove_parent(struct basic_block
*child
, struct basic_block
*parent
)
621 remove_bb_from_list(&child
->parents
, parent
, 1);
626 /* Change a "switch" into a branch */
627 void insert_branch(struct basic_block
*bb
, struct instruction
*jmp
, struct basic_block
*target
)
629 struct instruction
*br
, *old
;
630 struct basic_block
*child
;
632 /* Remove the switch */
633 old
= delete_last_instruction(&bb
->insns
);
636 br
= alloc_instruction(OP_BR
, 0);
638 br
->bb_true
= target
;
639 add_instruction(&bb
->insns
, br
);
641 FOR_EACH_PTR(bb
->children
, child
) {
642 if (child
== target
) {
643 target
= NULL
; /* Trigger just once */
646 DELETE_CURRENT_PTR(child
);
647 remove_parent(child
, bb
);
648 } END_FOR_EACH_PTR(child
);
649 PACK_PTR_LIST(&bb
->children
);
653 void insert_select(struct basic_block
*bb
, struct instruction
*br
, struct instruction
*phi_node
, pseudo_t
true, pseudo_t
false)
656 struct instruction
*select
;
658 /* Remove the 'br' */
659 delete_last_instruction(&bb
->insns
);
661 select
= alloc_instruction(OP_SEL
, phi_node
->size
);
665 use_pseudo(br
->cond
, &select
->src1
);
667 target
= phi_node
->target
;
668 assert(target
->def
== phi_node
);
669 select
->target
= target
;
670 target
->def
= select
;
672 use_pseudo(true, &select
->src2
);
673 use_pseudo(false, &select
->src3
);
675 add_instruction(&bb
->insns
, select
);
676 add_instruction(&bb
->insns
, br
);
679 static inline int bb_empty(struct basic_block
*bb
)
684 /* Add a label to the currently active block, return new active block */
685 static struct basic_block
* add_label(struct entrypoint
*ep
, struct symbol
*label
)
687 struct basic_block
*bb
= label
->bb_target
;
690 set_activeblock(ep
, bb
);
694 if (!bb_reachable(bb
) || !bb_empty(bb
)) {
695 bb
= alloc_basic_block(ep
, label
->pos
);
696 set_activeblock(ep
, bb
);
698 label
->bb_target
= bb
;
702 static void add_branch(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t cond
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
704 struct basic_block
*bb
= ep
->active
;
705 struct instruction
*br
;
707 if (bb_reachable(bb
)) {
708 br
= alloc_instruction(OP_BR
, 0);
709 use_pseudo(cond
, &br
->cond
);
710 br
->bb_true
= bb_true
;
711 br
->bb_false
= bb_false
;
712 add_bb(&bb_true
->parents
, bb
);
713 add_bb(&bb_false
->parents
, bb
);
714 add_bb(&bb
->children
, bb_true
);
715 add_bb(&bb
->children
, bb_false
);
716 add_one_insn(ep
, br
);
720 /* Dummy pseudo allocator */
721 pseudo_t
alloc_pseudo(struct instruction
*def
)
724 struct pseudo
* pseudo
= __alloc_pseudo(0);
725 pseudo
->type
= PSEUDO_REG
;
731 static void clear_symbol_pseudos(struct entrypoint
*ep
)
735 FOR_EACH_PTR(ep
->accesses
, sym
) {
737 } END_FOR_EACH_PTR(sym
);
740 static pseudo_t
symbol_pseudo(struct entrypoint
*ep
, struct symbol
*sym
)
747 pseudo
= sym
->pseudo
;
749 pseudo
= __alloc_pseudo(0);
751 pseudo
->type
= PSEUDO_SYM
;
753 pseudo
->ident
= sym
->ident
;
754 sym
->pseudo
= pseudo
;
755 add_symbol(&ep
->accesses
, sym
);
757 /* Symbol pseudos have neither nr, usage nor def */
761 pseudo_t
value_pseudo(long long val
)
763 #define MAX_VAL_HASH 64
764 static struct pseudo_list
*prev
[MAX_VAL_HASH
];
765 int hash
= val
& (MAX_VAL_HASH
-1);
766 struct pseudo_list
**list
= prev
+ hash
;
769 FOR_EACH_PTR(*list
, pseudo
) {
770 if (pseudo
->value
== val
)
772 } END_FOR_EACH_PTR(pseudo
);
774 pseudo
= __alloc_pseudo(0);
775 pseudo
->type
= PSEUDO_VAL
;
777 add_pseudo(list
, pseudo
);
779 /* Value pseudos have neither nr, usage nor def */
783 static pseudo_t
argument_pseudo(struct entrypoint
*ep
, int nr
)
785 pseudo_t pseudo
= __alloc_pseudo(0);
786 struct instruction
*entry
= ep
->entry
;
788 pseudo
->type
= PSEUDO_ARG
;
791 add_pseudo(&entry
->arg_list
, pseudo
);
793 /* Argument pseudos have neither usage nor def */
797 pseudo_t
alloc_phi(struct basic_block
*source
, pseudo_t pseudo
, int size
)
799 struct instruction
*insn
= alloc_instruction(OP_PHISOURCE
, size
);
800 pseudo_t phi
= __alloc_pseudo(0);
803 phi
->type
= PSEUDO_PHI
;
807 use_pseudo(pseudo
, &insn
->phi_src
);
810 add_instruction(&source
->insns
, insn
);
815 * We carry the "access_data" structure around for any accesses,
816 * which simplifies things a lot. It contains all the access
817 * information in one place.
820 struct symbol
*result_type
; // result ctype
821 struct symbol
*source_type
; // source ctype
822 pseudo_t address
; // pseudo containing address ..
823 pseudo_t origval
; // pseudo for original value ..
824 unsigned int offset
, alignment
; // byte offset
825 unsigned int bit_size
, bit_offset
; // which bits
829 static void finish_address_gen(struct entrypoint
*ep
, struct access_data
*ad
)
833 static int linearize_simple_address(struct entrypoint
*ep
,
834 struct expression
*addr
,
835 struct access_data
*ad
)
837 if (addr
->type
== EXPR_SYMBOL
) {
838 linearize_one_symbol(ep
, addr
->symbol
);
839 ad
->address
= symbol_pseudo(ep
, addr
->symbol
);
842 if (addr
->type
== EXPR_BINOP
) {
843 if (addr
->right
->type
== EXPR_VALUE
) {
844 if (addr
->op
== '+') {
845 ad
->offset
+= get_expression_value(addr
->right
);
846 return linearize_simple_address(ep
, addr
->left
, ad
);
850 ad
->address
= linearize_expression(ep
, addr
);
854 static struct symbol
*base_type(struct symbol
*sym
)
856 struct symbol
*base
= sym
;
859 if (sym
->type
== SYM_NODE
)
860 base
= base
->ctype
.base_type
;
861 if (base
->type
== SYM_BITFIELD
)
862 return base
->ctype
.base_type
;
867 static int linearize_address_gen(struct entrypoint
*ep
,
868 struct expression
*expr
,
869 struct access_data
*ad
)
871 struct symbol
*ctype
= expr
->ctype
;
876 ad
->result_type
= ctype
;
877 ad
->source_type
= base_type(ctype
);
878 ad
->bit_size
= ctype
->bit_size
;
879 ad
->alignment
= ctype
->ctype
.alignment
;
880 ad
->bit_offset
= ctype
->bit_offset
;
881 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
882 return linearize_simple_address(ep
, expr
->unop
, ad
);
884 warning(expr
->pos
, "generating address of non-lvalue (%d)", expr
->type
);
888 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*ad
)
890 struct instruction
*insn
;
897 insn
= alloc_typed_instruction(OP_LOAD
, ad
->source_type
);
898 new = alloc_pseudo(insn
);
902 insn
->offset
= ad
->offset
;
903 use_pseudo(ad
->address
, &insn
->src
);
904 add_one_insn(ep
, insn
);
908 static void add_store(struct entrypoint
*ep
, struct access_data
*ad
, pseudo_t value
)
910 struct basic_block
*bb
= ep
->active
;
912 if (bb_reachable(bb
)) {
913 struct instruction
*store
= alloc_typed_instruction(OP_STORE
, ad
->source_type
);
914 store
->offset
= ad
->offset
;
915 use_pseudo(value
, &store
->target
);
916 use_pseudo(ad
->address
, &store
->src
);
917 add_one_insn(ep
, store
);
921 static pseudo_t
linearize_store_gen(struct entrypoint
*ep
,
923 struct access_data
*ad
)
925 pseudo_t store
= value
;
927 if (type_size(ad
->source_type
) != type_size(ad
->result_type
)) {
928 pseudo_t orig
= add_load(ep
, ad
);
929 int shift
= ad
->bit_offset
;
930 unsigned long long mask
= (1ULL << ad
->bit_size
)-1;
933 store
= add_binary_op(ep
, ad
->source_type
, OP_SHL
, value
, value_pseudo(shift
));
936 orig
= add_binary_op(ep
, ad
->source_type
, OP_AND
, orig
, value_pseudo(~mask
));
937 store
= add_binary_op(ep
, ad
->source_type
, OP_OR
, orig
, store
);
939 add_store(ep
, ad
, store
);
943 static pseudo_t
add_binary_op(struct entrypoint
*ep
, struct symbol
*ctype
, int op
, pseudo_t left
, pseudo_t right
)
945 struct instruction
*insn
= alloc_typed_instruction(op
, ctype
);
946 pseudo_t target
= alloc_pseudo(insn
);
947 insn
->target
= target
;
948 use_pseudo(left
, &insn
->src1
);
949 use_pseudo(right
, &insn
->src2
);
950 add_one_insn(ep
, insn
);
954 static pseudo_t
add_setval(struct entrypoint
*ep
, struct symbol
*ctype
, struct expression
*val
)
956 struct instruction
*insn
= alloc_typed_instruction(OP_SETVAL
, ctype
);
957 pseudo_t target
= alloc_pseudo(insn
);
958 insn
->target
= target
;
960 add_one_insn(ep
, insn
);
964 static pseudo_t
add_symbol_address(struct entrypoint
*ep
, struct symbol
*sym
)
966 struct instruction
*insn
= alloc_instruction(OP_SYMADDR
, bits_in_pointer
);
967 pseudo_t target
= alloc_pseudo(insn
);
969 insn
->target
= target
;
970 use_pseudo(symbol_pseudo(ep
, sym
), &insn
->symbol
);
971 add_one_insn(ep
, insn
);
975 static pseudo_t
linearize_load_gen(struct entrypoint
*ep
, struct access_data
*ad
)
977 pseudo_t
new = add_load(ep
, ad
);
979 if (ad
->bit_offset
) {
980 pseudo_t shift
= value_pseudo(ad
->bit_offset
);
981 pseudo_t newval
= add_binary_op(ep
, ad
->source_type
, OP_LSR
, new, shift
);
988 static pseudo_t
linearize_access(struct entrypoint
*ep
, struct expression
*expr
)
990 struct access_data ad
= { NULL
, };
993 if (!linearize_address_gen(ep
, expr
, &ad
))
995 value
= linearize_load_gen(ep
, &ad
);
996 finish_address_gen(ep
, &ad
);
1001 static pseudo_t
linearize_inc_dec(struct entrypoint
*ep
, struct expression
*expr
, int postop
)
1003 struct access_data ad
= { NULL
, };
1004 pseudo_t old
, new, one
;
1005 int op
= expr
->op
== SPECIAL_INCREMENT
? OP_ADD
: OP_SUB
;
1007 if (!linearize_address_gen(ep
, expr
->unop
, &ad
))
1010 old
= linearize_load_gen(ep
, &ad
);
1011 one
= value_pseudo(expr
->op_value
);
1012 new = add_binary_op(ep
, expr
->ctype
, op
, old
, one
);
1013 linearize_store_gen(ep
, new, &ad
);
1014 finish_address_gen(ep
, &ad
);
1015 return postop
? old
: new;
1018 static pseudo_t
add_uniop(struct entrypoint
*ep
, struct expression
*expr
, int op
, pseudo_t src
)
1020 struct instruction
*insn
= alloc_typed_instruction(op
, expr
->ctype
);
1021 pseudo_t
new = alloc_pseudo(insn
);
1024 use_pseudo(src
, &insn
->src1
);
1025 add_one_insn(ep
, insn
);
1029 static pseudo_t
linearize_slice(struct entrypoint
*ep
, struct expression
*expr
)
1031 pseudo_t pre
= linearize_expression(ep
, expr
->base
);
1032 struct instruction
*insn
= alloc_typed_instruction(OP_SLICE
, expr
->ctype
);
1033 pseudo_t
new = alloc_pseudo(insn
);
1036 insn
->from
= expr
->r_bitpos
;
1037 insn
->len
= expr
->r_nrbits
;
1038 use_pseudo(pre
, &insn
->base
);
1039 add_one_insn(ep
, insn
);
1043 static pseudo_t
linearize_regular_preop(struct entrypoint
*ep
, struct expression
*expr
)
1045 pseudo_t pre
= linearize_expression(ep
, expr
->unop
);
1050 pseudo_t zero
= value_pseudo(0);
1051 return add_binary_op(ep
, expr
->unop
->ctype
, OP_SET_EQ
, pre
, zero
);
1054 return add_uniop(ep
, expr
, OP_NOT
, pre
);
1056 return add_uniop(ep
, expr
, OP_NEG
, pre
);
1061 static pseudo_t
linearize_preop(struct entrypoint
*ep
, struct expression
*expr
)
1064 * '*' is an lvalue access, and is fundamentally different
1065 * from an arithmetic operation. Maybe it should have an
1066 * expression type of its own..
1068 if (expr
->op
== '*')
1069 return linearize_access(ep
, expr
);
1070 if (expr
->op
== SPECIAL_INCREMENT
|| expr
->op
== SPECIAL_DECREMENT
)
1071 return linearize_inc_dec(ep
, expr
, 0);
1072 return linearize_regular_preop(ep
, expr
);
1075 static pseudo_t
linearize_postop(struct entrypoint
*ep
, struct expression
*expr
)
1077 return linearize_inc_dec(ep
, expr
, 1);
1081 * Casts to pointers are "less safe" than other casts, since
1082 * they imply type-unsafe accesses. "void *" is a special
1083 * case, since you can't access through it anyway without another
1086 static struct instruction
*alloc_cast_instruction(struct symbol
*ctype
)
1088 int opcode
= OP_CAST
;
1089 struct symbol
*base
= ctype
;
1091 if (base
->ctype
.modifiers
& MOD_SIGNED
)
1093 if (base
->type
== SYM_NODE
)
1094 base
= base
->ctype
.base_type
;
1095 if (base
->type
== SYM_PTR
) {
1096 base
= base
->ctype
.base_type
;
1097 if (base
!= &void_ctype
)
1098 opcode
= OP_PTRCAST
;
1100 if (base
->ctype
.base_type
== &fp_type
)
1102 return alloc_typed_instruction(opcode
, ctype
);
1105 static pseudo_t
cast_pseudo(struct entrypoint
*ep
, pseudo_t src
, struct symbol
*from
, struct symbol
*to
)
1108 struct instruction
*insn
;
1114 if (from
->bit_size
< 0 || to
->bit_size
< 0)
1116 insn
= alloc_cast_instruction(to
);
1117 result
= alloc_pseudo(insn
);
1118 insn
->target
= result
;
1119 insn
->orig_type
= from
;
1120 use_pseudo(src
, &insn
->src
);
1121 add_one_insn(ep
, insn
);
1125 static int opcode_sign(int opcode
, struct symbol
*ctype
)
1127 if (ctype
&& (ctype
->ctype
.modifiers
& MOD_SIGNED
)) {
1129 case OP_MULU
: case OP_DIVU
: case OP_MODU
: case OP_LSR
:
1136 static pseudo_t
linearize_assignment(struct entrypoint
*ep
, struct expression
*expr
)
1138 struct access_data ad
= { NULL
, };
1139 struct expression
*target
= expr
->left
;
1140 struct expression
*src
= expr
->right
;
1143 value
= linearize_expression(ep
, src
);
1144 if (!target
|| !linearize_address_gen(ep
, target
, &ad
))
1146 if (expr
->op
!= '=') {
1147 pseudo_t oldvalue
= linearize_load_gen(ep
, &ad
);
1149 static const int op_trans
[] = {
1150 [SPECIAL_ADD_ASSIGN
- SPECIAL_BASE
] = OP_ADD
,
1151 [SPECIAL_SUB_ASSIGN
- SPECIAL_BASE
] = OP_SUB
,
1152 [SPECIAL_MUL_ASSIGN
- SPECIAL_BASE
] = OP_MULU
,
1153 [SPECIAL_DIV_ASSIGN
- SPECIAL_BASE
] = OP_DIVU
,
1154 [SPECIAL_MOD_ASSIGN
- SPECIAL_BASE
] = OP_MODU
,
1155 [SPECIAL_SHL_ASSIGN
- SPECIAL_BASE
] = OP_SHL
,
1156 [SPECIAL_SHR_ASSIGN
- SPECIAL_BASE
] = OP_LSR
,
1157 [SPECIAL_AND_ASSIGN
- SPECIAL_BASE
] = OP_AND
,
1158 [SPECIAL_OR_ASSIGN
- SPECIAL_BASE
] = OP_OR
,
1159 [SPECIAL_XOR_ASSIGN
- SPECIAL_BASE
] = OP_XOR
1163 oldvalue
= cast_pseudo(ep
, oldvalue
, src
->ctype
, expr
->ctype
);
1164 opcode
= opcode_sign(op_trans
[expr
->op
- SPECIAL_BASE
], src
->ctype
);
1165 dst
= add_binary_op(ep
, src
->ctype
, opcode
, oldvalue
, value
);
1166 value
= cast_pseudo(ep
, dst
, expr
->ctype
, src
->ctype
);
1168 value
= linearize_store_gen(ep
, value
, &ad
);
1169 finish_address_gen(ep
, &ad
);
1173 static pseudo_t
linearize_call_expression(struct entrypoint
*ep
, struct expression
*expr
)
1175 struct expression
*arg
, *fn
;
1176 struct instruction
*insn
= alloc_typed_instruction(OP_CALL
, expr
->ctype
);
1177 pseudo_t retval
, call
;
1178 int context_diff
, check
;
1181 warning(expr
->pos
, "call with no type!");
1185 FOR_EACH_PTR(expr
->args
, arg
) {
1186 pseudo_t
new = linearize_expression(ep
, arg
);
1187 use_pseudo(new, add_pseudo(&insn
->arguments
, new));
1188 } END_FOR_EACH_PTR(arg
);
1195 int in
= fn
->ctype
->ctype
.in_context
;
1196 int out
= fn
->ctype
->ctype
.out_context
;
1205 context_diff
= out
- in
;
1208 if (fn
->type
== EXPR_PREOP
) {
1209 if (fn
->unop
->type
== EXPR_SYMBOL
) {
1210 struct symbol
*sym
= fn
->unop
->symbol
;
1211 if (sym
->ctype
.base_type
->type
== SYM_FN
)
1215 if (fn
->type
== EXPR_SYMBOL
) {
1216 call
= symbol_pseudo(ep
, fn
->symbol
);
1218 call
= linearize_expression(ep
, fn
);
1220 use_pseudo(call
, &insn
->func
);
1222 if (expr
->ctype
!= &void_ctype
)
1223 retval
= alloc_pseudo(insn
);
1224 insn
->target
= retval
;
1225 add_one_insn(ep
, insn
);
1227 if (check
|| context_diff
) {
1228 insn
= alloc_instruction(OP_CONTEXT
, 0);
1229 insn
->increment
= context_diff
;
1230 insn
->check
= check
;
1231 add_one_insn(ep
, insn
);
1237 static pseudo_t
linearize_binop(struct entrypoint
*ep
, struct expression
*expr
)
1239 pseudo_t src1
, src2
, dst
;
1240 static const int opcode
[] = {
1241 ['+'] = OP_ADD
, ['-'] = OP_SUB
,
1242 ['*'] = OP_MULU
, ['/'] = OP_DIVU
,
1243 ['%'] = OP_MODU
, ['&'] = OP_AND
,
1244 ['|'] = OP_OR
, ['^'] = OP_XOR
,
1245 [SPECIAL_LEFTSHIFT
] = OP_SHL
,
1246 [SPECIAL_RIGHTSHIFT
] = OP_LSR
,
1247 [SPECIAL_LOGICAL_AND
] = OP_AND_BOOL
,
1248 [SPECIAL_LOGICAL_OR
] = OP_OR_BOOL
,
1252 src1
= linearize_expression(ep
, expr
->left
);
1253 src2
= linearize_expression(ep
, expr
->right
);
1254 op
= opcode_sign(opcode
[expr
->op
], expr
->ctype
);
1255 dst
= add_binary_op(ep
, expr
->ctype
, op
, src1
, src2
);
1259 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
1261 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
1263 static pseudo_t
linearize_select(struct entrypoint
*ep
, struct expression
*expr
)
1265 pseudo_t cond
, true, false, res
;
1266 struct instruction
*insn
;
1268 true = linearize_expression(ep
, expr
->cond_true
);
1269 false = linearize_expression(ep
, expr
->cond_false
);
1270 cond
= linearize_expression(ep
, expr
->conditional
);
1272 insn
= alloc_typed_instruction(OP_SEL
, expr
->ctype
);
1273 if (!expr
->cond_true
)
1275 use_pseudo(cond
, &insn
->src1
);
1276 use_pseudo(true, &insn
->src2
);
1277 use_pseudo(false, &insn
->src3
);
1279 res
= alloc_pseudo(insn
);
1281 add_one_insn(ep
, insn
);
1285 static pseudo_t
add_join_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1286 pseudo_t phi1
, pseudo_t phi2
)
1289 struct instruction
*phi_node
;
1296 phi_node
= alloc_typed_instruction(OP_PHI
, expr
->ctype
);
1297 use_pseudo(phi1
, add_pseudo(&phi_node
->phi_list
, phi1
));
1298 use_pseudo(phi2
, add_pseudo(&phi_node
->phi_list
, phi2
));
1299 phi_node
->target
= target
= alloc_pseudo(phi_node
);
1300 add_one_insn(ep
, phi_node
);
1304 static pseudo_t
linearize_short_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1305 struct expression
*cond
,
1306 struct expression
*expr_false
)
1308 pseudo_t src1
, src2
;
1309 struct basic_block
*bb_false
= alloc_basic_block(ep
, expr_false
->pos
);
1310 struct basic_block
*merge
= alloc_basic_block(ep
, expr
->pos
);
1311 pseudo_t phi1
, phi2
;
1312 int size
= type_size(expr
->ctype
);
1314 src1
= linearize_expression(ep
, cond
);
1315 phi1
= alloc_phi(ep
->active
, src1
, size
);
1316 add_branch(ep
, expr
, src1
, merge
, bb_false
);
1318 set_activeblock(ep
, bb_false
);
1319 src2
= linearize_expression(ep
, expr_false
);
1320 phi2
= alloc_phi(ep
->active
, src2
, size
);
1321 set_activeblock(ep
, merge
);
1323 return add_join_conditional(ep
, expr
, phi1
, phi2
);
1326 static pseudo_t
linearize_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1327 struct expression
*cond
,
1328 struct expression
*expr_true
,
1329 struct expression
*expr_false
)
1331 pseudo_t src1
, src2
;
1332 pseudo_t phi1
, phi2
;
1333 struct basic_block
*bb_true
= alloc_basic_block(ep
, expr_true
->pos
);
1334 struct basic_block
*bb_false
= alloc_basic_block(ep
, expr_false
->pos
);
1335 struct basic_block
*merge
= alloc_basic_block(ep
, expr
->pos
);
1336 int size
= type_size(expr
->ctype
);
1338 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
1340 set_activeblock(ep
, bb_true
);
1341 src1
= linearize_expression(ep
, expr_true
);
1342 phi1
= alloc_phi(ep
->active
, src1
, size
);
1343 add_goto(ep
, merge
);
1345 set_activeblock(ep
, bb_false
);
1346 src2
= linearize_expression(ep
, expr_false
);
1347 phi2
= alloc_phi(ep
->active
, src2
, size
);
1348 set_activeblock(ep
, merge
);
1350 return add_join_conditional(ep
, expr
, phi1
, phi2
);
1353 static pseudo_t
linearize_logical(struct entrypoint
*ep
, struct expression
*expr
)
1355 struct expression
*shortcut
;
1357 shortcut
= alloc_const_expression(expr
->pos
, expr
->op
== SPECIAL_LOGICAL_OR
);
1358 shortcut
->ctype
= expr
->ctype
;
1359 return linearize_conditional(ep
, expr
, expr
->left
, shortcut
, expr
->right
);
1362 static pseudo_t
linearize_compare(struct entrypoint
*ep
, struct expression
*expr
)
1364 static const int cmpop
[] = {
1365 ['>'] = OP_SET_GT
, ['<'] = OP_SET_LT
,
1366 [SPECIAL_EQUAL
] = OP_SET_EQ
,
1367 [SPECIAL_NOTEQUAL
] = OP_SET_NE
,
1368 [SPECIAL_GTE
] = OP_SET_GE
,
1369 [SPECIAL_LTE
] = OP_SET_LE
,
1370 [SPECIAL_UNSIGNED_LT
] = OP_SET_B
,
1371 [SPECIAL_UNSIGNED_GT
] = OP_SET_A
,
1372 [SPECIAL_UNSIGNED_LTE
] = OP_SET_BE
,
1373 [SPECIAL_UNSIGNED_GTE
] = OP_SET_AE
,
1376 pseudo_t src1
= linearize_expression(ep
, expr
->left
);
1377 pseudo_t src2
= linearize_expression(ep
, expr
->right
);
1378 pseudo_t dst
= add_binary_op(ep
, expr
->left
->ctype
, cmpop
[expr
->op
], src1
, src2
);
1383 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1387 if (!expr
|| !bb_reachable(ep
->active
))
1390 switch (expr
->type
) {
1394 add_goto(ep
, expr
->value
? bb_true
: bb_false
);
1398 add_goto(ep
, expr
->fvalue
? bb_true
: bb_false
);
1402 linearize_logical_branch(ep
, expr
, bb_true
, bb_false
);
1406 cond
= linearize_compare(ep
, expr
);
1407 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1411 if (expr
->op
== '!')
1412 return linearize_cond_branch(ep
, expr
->unop
, bb_false
, bb_true
);
1415 cond
= linearize_expression(ep
, expr
);
1416 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1426 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1428 struct basic_block
*next
= alloc_basic_block(ep
, expr
->pos
);
1430 if (expr
->op
== SPECIAL_LOGICAL_OR
)
1431 linearize_cond_branch(ep
, expr
->left
, bb_true
, next
);
1433 linearize_cond_branch(ep
, expr
->left
, next
, bb_false
);
1434 set_activeblock(ep
, next
);
1435 linearize_cond_branch(ep
, expr
->right
, bb_true
, bb_false
);
1439 pseudo_t
linearize_cast(struct entrypoint
*ep
, struct expression
*expr
)
1442 struct expression
*orig
= expr
->cast_expression
;
1444 src
= linearize_expression(ep
, orig
);
1445 return cast_pseudo(ep
, src
, orig
->ctype
, expr
->ctype
);
1448 pseudo_t
linearize_position(struct entrypoint
*ep
, struct expression
*pos
, struct access_data
*ad
)
1450 struct expression
*init_expr
= pos
->init_expr
;
1452 ad
->offset
= pos
->init_offset
;
1453 ad
->source_type
= base_type(init_expr
->ctype
);
1454 ad
->result_type
= init_expr
->ctype
;
1455 return linearize_initializer(ep
, init_expr
, ad
);
1458 pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*ad
)
1460 switch (initializer
->type
) {
1461 case EXPR_INITIALIZER
: {
1462 struct expression
*expr
;
1463 FOR_EACH_PTR(initializer
->expr_list
, expr
) {
1464 linearize_initializer(ep
, expr
, ad
);
1465 } END_FOR_EACH_PTR(expr
);
1469 linearize_position(ep
, initializer
, ad
);
1472 pseudo_t value
= linearize_expression(ep
, initializer
);
1473 ad
->source_type
= base_type(initializer
->ctype
);
1474 ad
->result_type
= initializer
->ctype
;
1475 linearize_store_gen(ep
, value
, ad
);
1482 void linearize_argument(struct entrypoint
*ep
, struct symbol
*arg
, int nr
)
1484 struct access_data ad
= { NULL
, };
1486 ad
.source_type
= arg
;
1487 ad
.result_type
= arg
;
1488 ad
.address
= symbol_pseudo(ep
, arg
);
1489 linearize_store_gen(ep
, argument_pseudo(ep
, nr
), &ad
);
1490 finish_address_gen(ep
, &ad
);
1493 pseudo_t
linearize_expression(struct entrypoint
*ep
, struct expression
*expr
)
1498 current_pos
= expr
->pos
;
1499 switch (expr
->type
) {
1501 linearize_one_symbol(ep
, expr
->symbol
);
1502 return add_symbol_address(ep
, expr
->symbol
);
1505 return value_pseudo(expr
->value
);
1507 case EXPR_STRING
: case EXPR_FVALUE
: case EXPR_LABEL
:
1508 return add_setval(ep
, expr
->ctype
, expr
);
1510 case EXPR_STATEMENT
:
1511 return linearize_statement(ep
, expr
->statement
);
1514 return linearize_call_expression(ep
, expr
);
1517 return linearize_binop(ep
, expr
);
1520 return linearize_logical(ep
, expr
);
1523 return linearize_compare(ep
, expr
);
1526 return linearize_select(ep
, expr
);
1528 case EXPR_CONDITIONAL
:
1529 if (!expr
->cond_true
)
1530 return linearize_short_conditional(ep
, expr
, expr
->conditional
, expr
->cond_false
);
1532 return linearize_conditional(ep
, expr
, expr
->conditional
,
1533 expr
->cond_true
, expr
->cond_false
);
1536 linearize_expression(ep
, expr
->left
);
1537 return linearize_expression(ep
, expr
->right
);
1539 case EXPR_ASSIGNMENT
:
1540 return linearize_assignment(ep
, expr
);
1543 return linearize_preop(ep
, expr
);
1546 return linearize_postop(ep
, expr
);
1549 case EXPR_IMPLIED_CAST
:
1550 return linearize_cast(ep
, expr
);
1553 return linearize_slice(ep
, expr
);
1555 case EXPR_INITIALIZER
:
1557 warning(expr
->pos
, "unexpected initializer expression (%d %d)", expr
->type
, expr
->op
);
1560 warning(expr
->pos
, "unknown expression (%d %d)", expr
->type
, expr
->op
);
1566 static void linearize_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
)
1568 struct access_data ad
= { NULL
, };
1570 if (!sym
|| !sym
->initializer
|| sym
->initialized
)
1573 /* We need to output these puppies some day too.. */
1574 if (sym
->ctype
.modifiers
& (MOD_STATIC
| MOD_TOPLEVEL
))
1577 sym
->initialized
= 1;
1578 ad
.address
= symbol_pseudo(ep
, sym
);
1579 linearize_initializer(ep
, sym
->initializer
, &ad
);
1580 finish_address_gen(ep
, &ad
);
1583 static pseudo_t
linearize_compound_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1586 struct statement
*s
;
1588 struct symbol
*ret
= stmt
->ret
;
1590 concat_symbol_list(stmt
->syms
, &ep
->syms
);
1592 FOR_EACH_PTR(stmt
->syms
, sym
) {
1593 linearize_one_symbol(ep
, sym
);
1594 } END_FOR_EACH_PTR(sym
);
1597 FOR_EACH_PTR(stmt
->stmts
, s
) {
1598 pseudo
= linearize_statement(ep
, s
);
1599 } END_FOR_EACH_PTR(s
);
1602 struct basic_block
*bb
= add_label(ep
, ret
);
1603 struct instruction
*phi_node
= first_instruction(bb
->insns
);
1608 if (pseudo_list_size(phi_node
->phi_list
)==1) {
1609 pseudo
= first_pseudo(phi_node
->phi_list
);
1610 assert(pseudo
->type
== PSEUDO_PHI
);
1611 return pseudo
->def
->src1
;
1613 return phi_node
->target
;
1618 pseudo_t
linearize_context(struct entrypoint
*ep
, struct statement
*stmt
)
1620 struct instruction
*insn
= alloc_instruction(OP_CONTEXT
, 0);
1621 struct expression
*expr
= stmt
->expression
;
1624 if (expr
->type
== EXPR_VALUE
)
1625 value
= expr
->value
;
1627 insn
->increment
= value
;
1628 add_one_insn(ep
, insn
);
1632 pseudo_t
linearize_range(struct entrypoint
*ep
, struct statement
*stmt
)
1634 struct instruction
*insn
= alloc_instruction(OP_RANGE
, 0);
1636 use_pseudo(linearize_expression(ep
, stmt
->range_expression
), &insn
->src1
);
1637 use_pseudo(linearize_expression(ep
, stmt
->range_low
), &insn
->src2
);
1638 use_pseudo(linearize_expression(ep
, stmt
->range_high
), &insn
->src3
);
1639 add_one_insn(ep
, insn
);
1643 ALLOCATOR(asm_rules
, "asm rules");
1644 ALLOCATOR(asm_constraint
, "asm constraints");
1646 static void add_asm_input(struct entrypoint
*ep
, struct instruction
*insn
, struct expression
*expr
,
1647 const char *constraint
, const struct ident
*ident
)
1649 pseudo_t pseudo
= linearize_expression(ep
, expr
);
1650 struct asm_constraint
*rule
= __alloc_asm_constraint(0);
1652 rule
->ident
= ident
;
1653 rule
->constraint
= constraint
;
1654 use_pseudo(pseudo
, &rule
->pseudo
);
1655 add_ptr_list(&insn
->asm_rules
->inputs
, rule
);
1658 static void add_asm_output(struct entrypoint
*ep
, struct instruction
*insn
, struct expression
*expr
,
1659 const char *constraint
, const struct ident
*ident
)
1661 struct access_data ad
= { NULL
, };
1662 pseudo_t pseudo
= alloc_pseudo(insn
);
1663 struct asm_constraint
*rule
;
1665 if (!linearize_address_gen(ep
, expr
, &ad
))
1667 linearize_store_gen(ep
, pseudo
, &ad
);
1668 finish_address_gen(ep
, &ad
);
1669 rule
= __alloc_asm_constraint(0);
1670 rule
->ident
= ident
;
1671 rule
->constraint
= constraint
;
1672 use_pseudo(pseudo
, &rule
->pseudo
);
1673 add_ptr_list(&insn
->asm_rules
->outputs
, rule
);
1676 pseudo_t
linearize_asm_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1679 struct expression
*expr
;
1680 struct instruction
*insn
;
1681 struct asm_rules
*rules
;
1682 const char *constraint
;
1683 struct ident
*ident
;
1685 insn
= alloc_instruction(OP_ASM
, 0);
1686 expr
= stmt
->asm_string
;
1687 if (!expr
|| expr
->type
!= EXPR_STRING
) {
1688 warning(stmt
->pos
, "expected string in inline asm");
1691 insn
->string
= expr
->string
->data
;
1693 rules
= __alloc_asm_rules(0);
1694 insn
->asm_rules
= rules
;
1696 /* Gather the inputs.. */
1700 FOR_EACH_PTR(stmt
->asm_inputs
, expr
) {
1702 case 0: /* Identifier */
1704 ident
= (struct ident
*)expr
;
1707 case 1: /* Constraint */
1709 constraint
= expr
? expr
->string
->data
: "";
1712 case 2: /* Expression */
1714 add_asm_input(ep
, insn
, expr
, constraint
, ident
);
1716 } END_FOR_EACH_PTR(expr
);
1718 add_one_insn(ep
, insn
);
1720 /* Assign the outputs */
1724 FOR_EACH_PTR(stmt
->asm_outputs
, expr
) {
1726 case 0: /* Identifier */
1728 ident
= (struct ident
*)expr
;
1731 case 1: /* Constraint */
1733 constraint
= expr
->string
->data
;
1738 add_asm_output(ep
, insn
, expr
, constraint
, ident
);
1740 } END_FOR_EACH_PTR(expr
);
1745 static int multijmp_cmp(const void *_a
, const void *_b
)
1747 const struct multijmp
*a
= _a
;
1748 const struct multijmp
*b
= _b
;
1751 if (a
->begin
> a
->end
) {
1752 if (b
->begin
> b
->end
)
1756 if (b
->begin
> b
->end
)
1758 if (a
->begin
== b
->begin
) {
1759 if (a
->end
== b
->end
)
1761 return (a
->end
< b
->end
) ? -1 : 1;
1763 return a
->begin
< b
->begin
? -1 : 1;
1766 static void sort_switch_cases(struct instruction
*insn
)
1768 sort_list((struct ptr_list
**)&insn
->multijmp_list
, multijmp_cmp
);
1771 pseudo_t
linearize_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1773 struct basic_block
*bb
;
1779 if (bb
&& !bb
->insns
)
1780 bb
->pos
= stmt
->pos
;
1781 current_pos
= stmt
->pos
;
1783 switch (stmt
->type
) {
1788 return linearize_context(ep
, stmt
);
1791 return linearize_range(ep
, stmt
);
1793 case STMT_EXPRESSION
:
1794 return linearize_expression(ep
, stmt
->expression
);
1797 return linearize_asm_statement(ep
, stmt
);
1800 struct expression
*expr
= stmt
->expression
;
1801 struct basic_block
*bb_return
= get_bound_block(ep
, stmt
->ret_target
);
1802 struct basic_block
*active
;
1803 pseudo_t src
= linearize_expression(ep
, expr
);
1804 active
= ep
->active
;
1805 if (active
&& src
!= &void_pseudo
) {
1806 struct instruction
*phi_node
= first_instruction(bb_return
->insns
);
1809 phi_node
= alloc_typed_instruction(OP_PHI
, expr
->ctype
);
1810 phi_node
->target
= alloc_pseudo(phi_node
);
1811 phi_node
->bb
= bb_return
;
1812 add_instruction(&bb_return
->insns
, phi_node
);
1814 phi
= alloc_phi(active
, src
, type_size(expr
->ctype
));
1815 phi
->ident
= &return_ident
;
1816 use_pseudo(phi
, add_pseudo(&phi_node
->phi_list
, phi
));
1818 add_goto(ep
, bb_return
);
1823 add_label(ep
, stmt
->case_label
);
1824 linearize_statement(ep
, stmt
->case_statement
);
1829 struct symbol
*label
= stmt
->label_identifier
;
1832 add_label(ep
, label
);
1833 linearize_statement(ep
, stmt
->label_statement
);
1840 struct expression
*expr
;
1841 struct instruction
*goto_ins
;
1842 struct basic_block
*active
;
1845 active
= ep
->active
;
1846 if (!bb_reachable(active
))
1849 if (stmt
->goto_label
) {
1850 add_goto(ep
, get_bound_block(ep
, stmt
->goto_label
));
1854 expr
= stmt
->goto_expression
;
1858 /* This can happen as part of simplification */
1859 if (expr
->type
== EXPR_LABEL
) {
1860 add_goto(ep
, get_bound_block(ep
, expr
->label_symbol
));
1864 pseudo
= linearize_expression(ep
, expr
);
1865 goto_ins
= alloc_instruction(OP_COMPUTEDGOTO
, 0);
1866 use_pseudo(pseudo
, &goto_ins
->target
);
1867 add_one_insn(ep
, goto_ins
);
1869 FOR_EACH_PTR(stmt
->target_list
, sym
) {
1870 struct basic_block
*bb_computed
= get_bound_block(ep
, sym
);
1871 struct multijmp
*jmp
= alloc_multijmp(bb_computed
, 1, 0);
1872 add_multijmp(&goto_ins
->multijmp_list
, jmp
);
1873 add_bb(&bb_computed
->parents
, ep
->active
);
1874 add_bb(&active
->children
, bb_computed
);
1875 } END_FOR_EACH_PTR(sym
);
1882 return linearize_compound_statement(ep
, stmt
);
1885 * This could take 'likely/unlikely' into account, and
1886 * switch the arms around appropriately..
1889 struct basic_block
*bb_true
, *bb_false
, *endif
;
1890 struct expression
*cond
= stmt
->if_conditional
;
1892 bb_true
= alloc_basic_block(ep
, stmt
->pos
);
1893 bb_false
= endif
= alloc_basic_block(ep
, stmt
->pos
);
1895 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
1897 set_activeblock(ep
, bb_true
);
1898 linearize_statement(ep
, stmt
->if_true
);
1900 if (stmt
->if_false
) {
1901 endif
= alloc_basic_block(ep
, stmt
->pos
);
1902 add_goto(ep
, endif
);
1903 set_activeblock(ep
, bb_false
);
1904 linearize_statement(ep
, stmt
->if_false
);
1906 set_activeblock(ep
, endif
);
1912 struct instruction
*switch_ins
;
1913 struct basic_block
*switch_end
= alloc_basic_block(ep
, stmt
->pos
);
1914 struct basic_block
*active
, *default_case
;
1915 struct multijmp
*jmp
;
1918 pseudo
= linearize_expression(ep
, stmt
->switch_expression
);
1920 active
= ep
->active
;
1921 if (!bb_reachable(active
))
1924 switch_ins
= alloc_instruction(OP_SWITCH
, 0);
1925 use_pseudo(pseudo
, &switch_ins
->cond
);
1926 add_one_insn(ep
, switch_ins
);
1929 default_case
= NULL
;
1930 FOR_EACH_PTR(stmt
->switch_case
->symbol_list
, sym
) {
1931 struct statement
*case_stmt
= sym
->stmt
;
1932 struct basic_block
*bb_case
= get_bound_block(ep
, sym
);
1934 if (!case_stmt
->case_expression
) {
1935 default_case
= bb_case
;
1940 begin
= end
= case_stmt
->case_expression
->value
;
1941 if (case_stmt
->case_to
)
1942 end
= case_stmt
->case_to
->value
;
1944 jmp
= alloc_multijmp(bb_case
, end
, begin
);
1946 jmp
= alloc_multijmp(bb_case
, begin
, end
);
1949 add_multijmp(&switch_ins
->multijmp_list
, jmp
);
1950 add_bb(&bb_case
->parents
, active
);
1951 add_bb(&active
->children
, bb_case
);
1952 } END_FOR_EACH_PTR(sym
);
1954 bind_label(stmt
->switch_break
, switch_end
, stmt
->pos
);
1956 /* And linearize the actual statement */
1957 linearize_statement(ep
, stmt
->switch_statement
);
1958 set_activeblock(ep
, switch_end
);
1961 default_case
= switch_end
;
1963 jmp
= alloc_multijmp(default_case
, 1, 0);
1964 add_multijmp(&switch_ins
->multijmp_list
, jmp
);
1965 add_bb(&default_case
->parents
, active
);
1966 add_bb(&active
->children
, default_case
);
1967 sort_switch_cases(switch_ins
);
1972 case STMT_ITERATOR
: {
1973 struct statement
*pre_statement
= stmt
->iterator_pre_statement
;
1974 struct expression
*pre_condition
= stmt
->iterator_pre_condition
;
1975 struct statement
*statement
= stmt
->iterator_statement
;
1976 struct statement
*post_statement
= stmt
->iterator_post_statement
;
1977 struct expression
*post_condition
= stmt
->iterator_post_condition
;
1978 struct basic_block
*loop_top
, *loop_body
, *loop_continue
, *loop_end
;
1980 concat_symbol_list(stmt
->iterator_syms
, &ep
->syms
);
1981 linearize_statement(ep
, pre_statement
);
1983 loop_body
= loop_top
= alloc_basic_block(ep
, stmt
->pos
);
1984 loop_continue
= alloc_basic_block(ep
, stmt
->pos
);
1985 loop_end
= alloc_basic_block(ep
, stmt
->pos
);
1987 if (pre_condition
== post_condition
) {
1988 loop_top
= alloc_basic_block(ep
, stmt
->pos
);
1989 set_activeblock(ep
, loop_top
);
1993 linearize_cond_branch(ep
, pre_condition
, loop_body
, loop_end
);
1995 bind_label(stmt
->iterator_continue
, loop_continue
, stmt
->pos
);
1996 bind_label(stmt
->iterator_break
, loop_end
, stmt
->pos
);
1998 set_activeblock(ep
, loop_body
);
1999 linearize_statement(ep
, statement
);
2000 add_goto(ep
, loop_continue
);
2002 set_activeblock(ep
, loop_continue
);
2003 linearize_statement(ep
, post_statement
);
2004 if (!post_condition
|| pre_condition
== post_condition
)
2005 add_goto(ep
, loop_top
);
2007 linearize_cond_branch(ep
, post_condition
, loop_top
, loop_end
);
2008 set_activeblock(ep
, loop_end
);
2018 static struct entrypoint
*linearize_fn(struct symbol
*sym
, struct symbol
*base_type
)
2020 struct entrypoint
*ep
;
2021 struct basic_block
*bb
;
2023 struct instruction
*entry
;
2027 if (!base_type
->stmt
)
2030 ep
= alloc_entrypoint();
2031 bb
= alloc_basic_block(ep
, sym
->pos
);
2034 set_activeblock(ep
, bb
);
2036 entry
= alloc_instruction(OP_ENTRY
, 0);
2037 add_one_insn(ep
, entry
);
2040 concat_symbol_list(base_type
->arguments
, &ep
->syms
);
2042 /* FIXME!! We should do something else about varargs.. */
2044 FOR_EACH_PTR(base_type
->arguments
, arg
) {
2045 linearize_argument(ep
, arg
, ++i
);
2046 } END_FOR_EACH_PTR(arg
);
2048 result
= linearize_statement(ep
, base_type
->stmt
);
2049 if (bb_reachable(ep
->active
) && !bb_terminated(ep
->active
)) {
2050 struct symbol
*ret_type
= base_type
->ctype
.base_type
;
2051 struct instruction
*insn
= alloc_typed_instruction(OP_RET
, ret_type
);
2053 if (type_size(ret_type
) > 0)
2054 use_pseudo(result
, &insn
->src
);
2055 add_one_insn(ep
, insn
);
2059 * Do trivial flow simplification - branches to
2060 * branches, kill dead basicblocks etc
2062 kill_unreachable_bbs(ep
);
2065 * Turn symbols into pseudos
2067 simplify_symbol_usage(ep
);
2071 * Remove trivial instructions, and try to CSE
2075 cleanup_and_cse(ep
);
2076 pack_basic_blocks(ep
);
2077 } while (repeat_phase
& REPEAT_CSE
);
2079 kill_unreachable_bbs(ep
);
2083 clear_symbol_pseudos(ep
);
2085 /* And track pseudo register usage */
2086 track_pseudo_liveness(ep
);
2089 * Some flow optimizations can only effectively
2090 * be done when we've done liveness analysis. But
2091 * if they trigger, we need to start all over
2094 if (simplify_flow(ep
)) {
2099 /* Finally, add deathnotes to pseudos now that we have them */
2100 track_pseudo_death(ep
);
2105 struct entrypoint
*linearize_symbol(struct symbol
*sym
)
2107 struct symbol
*base_type
;
2111 current_pos
= sym
->pos
;
2112 base_type
= sym
->ctype
.base_type
;
2115 if (base_type
->type
== SYM_FN
)
2116 return linearize_fn(sym
, base_type
);