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 pseudo_t
linearize_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
);
33 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*);
34 static pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*);
35 static pseudo_t
cast_pseudo(struct entrypoint
*ep
, pseudo_t src
, struct symbol
*from
, struct symbol
*to
);
37 struct pseudo void_pseudo
= {};
39 static struct position current_pos
;
41 ALLOCATOR(pseudo_user
, "pseudo_user");
43 static struct instruction
*alloc_instruction(int opcode
, int size
)
45 struct instruction
* insn
= __alloc_instruction(0);
46 insn
->opcode
= opcode
;
48 insn
->pos
= current_pos
;
52 static inline int type_size(struct symbol
*type
)
54 return type
? type
->bit_size
> 0 ? type
->bit_size
: 0 : 0;
57 static struct instruction
*alloc_typed_instruction(int opcode
, struct symbol
*type
)
59 struct instruction
*insn
= alloc_instruction(opcode
, type_size(type
));
64 static struct entrypoint
*alloc_entrypoint(void)
66 return __alloc_entrypoint(0);
69 static struct basic_block
*alloc_basic_block(struct entrypoint
*ep
, struct position pos
)
72 struct basic_block
*bb
= __alloc_basic_block(0);
80 static struct multijmp
*alloc_multijmp(struct basic_block
*target
, int begin
, int end
)
82 struct multijmp
*multijmp
= __alloc_multijmp(0);
83 multijmp
->target
= target
;
84 multijmp
->begin
= begin
;
89 static inline int regno(pseudo_t n
)
92 if (n
&& n
->type
== PSEUDO_REG
)
97 const char *show_pseudo(pseudo_t pseudo
)
100 static char buffer
[4][64];
108 buf
= buffer
[3 & ++n
];
109 switch(pseudo
->type
) {
111 struct symbol
*sym
= pseudo
->sym
;
112 struct expression
*expr
;
114 if (sym
->bb_target
) {
115 snprintf(buf
, 64, ".L%u", sym
->bb_target
->nr
);
119 snprintf(buf
, 64, "%s", show_ident(sym
->ident
));
122 expr
= sym
->initializer
;
123 snprintf(buf
, 64, "<anon symbol:%p>", sym
);
125 switch (expr
->type
) {
127 snprintf(buf
, 64, "<symbol value: %lld>", expr
->value
);
130 return show_string(expr
->string
);
138 i
= snprintf(buf
, 64, "%%r%d", pseudo
->nr
);
140 sprintf(buf
+i
, "(%s)", show_ident(pseudo
->ident
));
143 long long value
= pseudo
->value
;
144 if (value
> 1000 || value
< -1000)
145 snprintf(buf
, 64, "$%#llx", value
);
147 snprintf(buf
, 64, "$%lld", value
);
151 snprintf(buf
, 64, "%%arg%d", pseudo
->nr
);
154 i
= snprintf(buf
, 64, "%%phi%d", pseudo
->nr
);
156 sprintf(buf
+i
, "(%s)", show_ident(pseudo
->ident
));
159 snprintf(buf
, 64, "<bad pseudo type %d>", pseudo
->type
);
164 static const char *opcodes
[] = {
165 [OP_BADOP
] = "bad_op",
168 [OP_ENTRY
] = "<entry-point>",
174 [OP_SWITCH
] = "switch",
175 [OP_INVOKE
] = "invoke",
176 [OP_COMPUTEDGOTO
] = "jmp *",
177 [OP_UNWIND
] = "unwind",
196 [OP_AND_BOOL
] = "and-bool",
197 [OP_OR_BOOL
] = "or-bool",
199 /* Binary comparison */
200 [OP_SET_EQ
] = "seteq",
201 [OP_SET_NE
] = "setne",
202 [OP_SET_LE
] = "setle",
203 [OP_SET_GE
] = "setge",
204 [OP_SET_LT
] = "setlt",
205 [OP_SET_GT
] = "setgt",
208 [OP_SET_BE
] = "setbe",
209 [OP_SET_AE
] = "setae",
215 /* Special three-input */
219 [OP_MALLOC
] = "malloc",
221 [OP_ALLOCA
] = "alloca",
223 [OP_STORE
] = "store",
225 [OP_SYMADDR
] = "symaddr",
226 [OP_GET_ELEMENT_PTR
] = "getelem",
230 [OP_PHISOURCE
] = "phisrc",
232 [OP_SCAST
] = "scast",
233 [OP_FPCAST
] = "fpcast",
234 [OP_PTRCAST
] = "ptrcast",
235 [OP_INLINED_CALL
] = "# call",
237 [OP_VANEXT
] = "va_next",
238 [OP_VAARG
] = "va_arg",
239 [OP_SLICE
] = "slice",
243 [OP_DEATHNOTE
] = "dead",
246 /* Sparse tagging (line numbers, context, whatever) */
247 [OP_CONTEXT
] = "context",
248 [OP_RANGE
] = "range-check",
253 static char *show_asm_constraints(char *buf
, const char *sep
, struct asm_constraint_list
*list
)
255 struct asm_constraint
*entry
;
257 FOR_EACH_PTR(list
, entry
) {
258 buf
+= sprintf(buf
, "%s\"%s\"", sep
, entry
->constraint
);
260 buf
+= sprintf(buf
, " (%s)", show_pseudo(entry
->pseudo
));
262 buf
+= sprintf(buf
, " [%s]", show_ident(entry
->ident
));
264 } END_FOR_EACH_PTR(entry
);
268 static char *show_asm(char *buf
, struct instruction
*insn
)
270 struct asm_rules
*rules
= insn
->asm_rules
;
272 buf
+= sprintf(buf
, "\"%s\"", insn
->string
);
273 buf
= show_asm_constraints(buf
, "\n\t\tout: ", rules
->outputs
);
274 buf
= show_asm_constraints(buf
, "\n\t\tin: ", rules
->inputs
);
275 buf
= show_asm_constraints(buf
, "\n\t\tclobber: ", rules
->clobbers
);
279 const char *show_instruction(struct instruction
*insn
)
281 int opcode
= insn
->opcode
;
282 static char buffer
[4096];
287 buf
+= sprintf(buf
, "# ");
289 if (opcode
< ARRAY_SIZE(opcodes
)) {
290 const char *op
= opcodes
[opcode
];
292 buf
+= sprintf(buf
, "opcode:%d", opcode
);
294 buf
+= sprintf(buf
, "%s", op
);
296 buf
+= sprintf(buf
, ".%d", insn
->size
);
297 memset(buf
, ' ', 20);
301 if (buf
< buffer
+ 12)
305 if (insn
->src
&& insn
->src
!= VOID
)
306 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->src
));
310 buf
+= sprintf(buf
, "%s, .L%u, .L%u", show_pseudo(insn
->cond
), insn
->bb_true
->nr
, insn
->bb_false
->nr
);
314 buf
+= sprintf(buf
, ".L%u", insn
->bb_true
->nr
);
318 struct symbol
*sym
= insn
->symbol
->sym
;
319 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
321 if (!insn
->bb
&& !sym
)
323 if (sym
->bb_target
) {
324 buf
+= sprintf(buf
, ".L%u", sym
->bb_target
->nr
);
328 buf
+= sprintf(buf
, "%s", show_ident(sym
->ident
));
331 buf
+= sprintf(buf
, "<anon symbol:%p>", sym
);
336 struct expression
*expr
= insn
->val
;
337 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
340 buf
+= sprintf(buf
, "%s", "<none>");
344 switch (expr
->type
) {
346 buf
+= sprintf(buf
, "%lld", expr
->value
);
349 buf
+= sprintf(buf
, "%Lf", expr
->fvalue
);
352 buf
+= sprintf(buf
, "%.40s", show_string(expr
->string
));
355 buf
+= sprintf(buf
, "%s", show_ident(expr
->symbol
->ident
));
358 buf
+= sprintf(buf
, ".L%u", expr
->symbol
->bb_target
->nr
);
361 buf
+= sprintf(buf
, "SETVAL EXPR TYPE %d", expr
->type
);
366 struct multijmp
*jmp
;
367 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->cond
));
368 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
369 if (jmp
->begin
== jmp
->end
)
370 buf
+= sprintf(buf
, ", %d -> .L%u", jmp
->begin
, jmp
->target
->nr
);
371 else if (jmp
->begin
< jmp
->end
)
372 buf
+= sprintf(buf
, ", %d ... %d -> .L%u", jmp
->begin
, jmp
->end
, jmp
->target
->nr
);
374 buf
+= sprintf(buf
, ", default -> .L%u", jmp
->target
->nr
);
375 } END_FOR_EACH_PTR(jmp
);
378 case OP_COMPUTEDGOTO
: {
379 struct multijmp
*jmp
;
380 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
381 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
382 buf
+= sprintf(buf
, ", .L%u", jmp
->target
->nr
);
383 } END_FOR_EACH_PTR(jmp
);
388 struct instruction
*phi
;
389 buf
+= sprintf(buf
, "%s <- %s ", show_pseudo(insn
->target
), show_pseudo(insn
->phi_src
));
390 FOR_EACH_PTR(insn
->phi_users
, phi
) {
391 buf
+= sprintf(buf
, " (%s)", show_pseudo(phi
->target
));
392 } END_FOR_EACH_PTR(phi
);
398 const char *s
= " <-";
399 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
400 FOR_EACH_PTR(insn
->phi_list
, phi
) {
401 buf
+= sprintf(buf
, "%s %s", s
, show_pseudo(phi
));
403 } END_FOR_EACH_PTR(phi
);
406 case OP_LOAD
: case OP_LNOP
:
407 buf
+= sprintf(buf
, "%s <- %d[%s]", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
409 case OP_STORE
: case OP_SNOP
:
410 buf
+= sprintf(buf
, "%s -> %d[%s]", show_pseudo(insn
->target
), insn
->offset
, show_pseudo(insn
->src
));
412 case OP_INLINED_CALL
:
415 if (insn
->target
&& insn
->target
!= VOID
)
416 buf
+= sprintf(buf
, "%s <- ", show_pseudo(insn
->target
));
417 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->func
));
418 FOR_EACH_PTR(insn
->arguments
, arg
) {
419 buf
+= sprintf(buf
, ", %s", show_pseudo(arg
));
420 } END_FOR_EACH_PTR(arg
);
427 buf
+= sprintf(buf
, "%s <- (%d) %s",
428 show_pseudo(insn
->target
),
429 type_size(insn
->orig_type
),
430 show_pseudo(insn
->src
));
432 case OP_BINARY
... OP_BINARY_END
:
433 case OP_BINCMP
... OP_BINCMP_END
:
434 buf
+= sprintf(buf
, "%s <- %s, %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
), show_pseudo(insn
->src2
));
438 buf
+= sprintf(buf
, "%s <- %s, %s, %s", show_pseudo(insn
->target
),
439 show_pseudo(insn
->src1
), show_pseudo(insn
->src2
), show_pseudo(insn
->src3
));
443 buf
+= sprintf(buf
, "%s <- %s, %d, %d", show_pseudo(insn
->target
), show_pseudo(insn
->base
), insn
->from
, insn
->len
);
446 case OP_NOT
: case OP_NEG
:
447 buf
+= sprintf(buf
, "%s <- %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
));
451 buf
+= sprintf(buf
, "%s%d", insn
->check
? "check: " : "", insn
->increment
);
454 buf
+= sprintf(buf
, "%s between %s..%s", show_pseudo(insn
->src1
), show_pseudo(insn
->src2
), show_pseudo(insn
->src3
));
457 buf
+= sprintf(buf
, "%s <- %s", show_pseudo(insn
->target
), show_pseudo(insn
->src1
));
460 buf
+= sprintf(buf
, "%s", show_pseudo(insn
->target
));
463 buf
= show_asm(buf
, insn
);
466 buf
+= sprintf(buf
, "%s <- %s", show_pseudo(insn
->target
), show_pseudo(insn
->src
));
472 if (buf
>= buffer
+ sizeof(buffer
))
473 die("instruction buffer overflowed %td\n", buf
- buffer
);
474 do { --buf
; } while (*buf
== ' ');
479 void show_bb(struct basic_block
*bb
)
481 struct instruction
*insn
;
483 printf(".L%u:\n", bb
->nr
);
485 pseudo_t needs
, defines
;
486 printf("%s:%d\n", stream_name(bb
->pos
.stream
), bb
->pos
.line
);
488 FOR_EACH_PTR(bb
->needs
, needs
) {
489 struct instruction
*def
= needs
->def
;
490 if (def
->opcode
!= OP_PHI
) {
491 printf(" **uses %s (from .L%u)**\n", show_pseudo(needs
), def
->bb
->nr
);
494 const char *sep
= " ";
495 printf(" **uses %s (from", show_pseudo(needs
));
496 FOR_EACH_PTR(def
->phi_list
, phi
) {
499 printf("%s(%s:.L%u)", sep
, show_pseudo(phi
), phi
->def
->bb
->nr
);
501 } END_FOR_EACH_PTR(phi
);
504 } END_FOR_EACH_PTR(needs
);
506 FOR_EACH_PTR(bb
->defines
, defines
) {
507 printf(" **defines %s **\n", show_pseudo(defines
));
508 } END_FOR_EACH_PTR(defines
);
511 struct basic_block
*from
;
512 FOR_EACH_PTR(bb
->parents
, from
) {
513 printf(" **from .L%u (%s:%d:%d)**\n", from
->nr
,
514 stream_name(from
->pos
.stream
), from
->pos
.line
, from
->pos
.pos
);
515 } END_FOR_EACH_PTR(from
);
519 struct basic_block
*to
;
520 FOR_EACH_PTR(bb
->children
, to
) {
521 printf(" **to .L%u (%s:%d:%d)**\n", to
->nr
,
522 stream_name(to
->pos
.stream
), to
->pos
.line
, to
->pos
.pos
);
523 } END_FOR_EACH_PTR(to
);
527 FOR_EACH_PTR(bb
->insns
, insn
) {
528 if (!insn
->bb
&& verbose
< 2)
530 printf("\t%s\n", show_instruction(insn
));
531 } END_FOR_EACH_PTR(insn
);
532 if (!bb_terminated(bb
))
536 static void show_symbol_usage(pseudo_t pseudo
)
538 struct pseudo_user
*pu
;
541 FOR_EACH_PTR(pseudo
->users
, pu
) {
542 printf("\t%s\n", show_instruction(pu
->insn
));
543 } END_FOR_EACH_PTR(pu
);
547 void show_entry(struct entrypoint
*ep
)
550 struct basic_block
*bb
;
552 printf("%s:\n", show_ident(ep
->name
->ident
));
555 printf("ep %p: %s\n", ep
, show_ident(ep
->name
->ident
));
557 FOR_EACH_PTR(ep
->syms
, sym
) {
560 if (!sym
->pseudo
->users
)
562 printf(" sym: %p %s\n", sym
, show_ident(sym
->ident
));
563 if (sym
->ctype
.modifiers
& (MOD_EXTERN
| MOD_STATIC
| MOD_ADDRESSABLE
))
564 printf("\texternal visibility\n");
565 show_symbol_usage(sym
->pseudo
);
566 } END_FOR_EACH_PTR(sym
);
571 FOR_EACH_PTR(ep
->bbs
, bb
) {
574 if (!bb
->parents
&& !bb
->children
&& !bb
->insns
&& verbose
< 2)
578 } END_FOR_EACH_PTR(bb
);
583 static void bind_label(struct symbol
*label
, struct basic_block
*bb
, struct position pos
)
585 if (label
->bb_target
)
586 warning(pos
, "label '%s' already bound", show_ident(label
->ident
));
587 label
->bb_target
= bb
;
590 static struct basic_block
* get_bound_block(struct entrypoint
*ep
, struct symbol
*label
)
592 struct basic_block
*bb
= label
->bb_target
;
595 bb
= alloc_basic_block(ep
, label
->pos
);
596 label
->bb_target
= bb
;
601 static void finish_block(struct entrypoint
*ep
)
603 struct basic_block
*src
= ep
->active
;
604 if (bb_reachable(src
))
608 static void add_goto(struct entrypoint
*ep
, struct basic_block
*dst
)
610 struct basic_block
*src
= ep
->active
;
611 if (bb_reachable(src
)) {
612 struct instruction
*br
= alloc_instruction(OP_BR
, 0);
614 add_bb(&dst
->parents
, src
);
615 add_bb(&src
->children
, dst
);
617 add_instruction(&src
->insns
, br
);
622 static void add_one_insn(struct entrypoint
*ep
, struct instruction
*insn
)
624 struct basic_block
*bb
= ep
->active
;
626 if (bb_reachable(bb
)) {
628 add_instruction(&bb
->insns
, insn
);
632 static void set_activeblock(struct entrypoint
*ep
, struct basic_block
*bb
)
634 if (!bb_terminated(ep
->active
))
638 if (bb_reachable(bb
))
639 add_bb(&ep
->bbs
, bb
);
642 static void remove_parent(struct basic_block
*child
, struct basic_block
*parent
)
644 remove_bb_from_list(&child
->parents
, parent
, 1);
646 repeat_phase
|= REPEAT_CFG_CLEANUP
;
649 /* Change a "switch" or a conditional branch into a branch */
650 void insert_branch(struct basic_block
*bb
, struct instruction
*jmp
, struct basic_block
*target
)
652 struct instruction
*br
, *old
;
653 struct basic_block
*child
;
655 /* Remove the switch */
656 old
= delete_last_instruction(&bb
->insns
);
658 kill_instruction(old
);
660 br
= alloc_instruction(OP_BR
, 0);
662 br
->bb_true
= target
;
663 add_instruction(&bb
->insns
, br
);
665 FOR_EACH_PTR(bb
->children
, child
) {
666 if (child
== target
) {
667 target
= NULL
; /* Trigger just once */
670 DELETE_CURRENT_PTR(child
);
671 remove_parent(child
, bb
);
672 } END_FOR_EACH_PTR(child
);
673 PACK_PTR_LIST(&bb
->children
);
677 void insert_select(struct basic_block
*bb
, struct instruction
*br
, struct instruction
*phi_node
, pseudo_t if_true
, pseudo_t if_false
)
680 struct instruction
*select
;
682 /* Remove the 'br' */
683 delete_last_instruction(&bb
->insns
);
685 select
= alloc_instruction(OP_SEL
, phi_node
->size
);
689 use_pseudo(select
, br
->cond
, &select
->src1
);
691 target
= phi_node
->target
;
692 assert(target
->def
== phi_node
);
693 select
->target
= target
;
694 target
->def
= select
;
696 use_pseudo(select
, if_true
, &select
->src2
);
697 use_pseudo(select
, if_false
, &select
->src3
);
699 add_instruction(&bb
->insns
, select
);
700 add_instruction(&bb
->insns
, br
);
703 static inline int bb_empty(struct basic_block
*bb
)
708 /* Add a label to the currently active block, return new active block */
709 static struct basic_block
* add_label(struct entrypoint
*ep
, struct symbol
*label
)
711 struct basic_block
*bb
= label
->bb_target
;
714 set_activeblock(ep
, bb
);
718 if (!bb_reachable(bb
) || !bb_empty(bb
)) {
719 bb
= alloc_basic_block(ep
, label
->pos
);
720 set_activeblock(ep
, bb
);
722 label
->bb_target
= bb
;
726 static void add_branch(struct entrypoint
*ep
, struct expression
*expr
, pseudo_t cond
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
728 struct basic_block
*bb
= ep
->active
;
729 struct instruction
*br
;
731 if (bb_reachable(bb
)) {
732 br
= alloc_instruction(OP_CBR
, 0);
733 use_pseudo(br
, cond
, &br
->cond
);
734 br
->bb_true
= bb_true
;
735 br
->bb_false
= bb_false
;
736 add_bb(&bb_true
->parents
, bb
);
737 add_bb(&bb_false
->parents
, bb
);
738 add_bb(&bb
->children
, bb_true
);
739 add_bb(&bb
->children
, bb_false
);
740 add_one_insn(ep
, br
);
744 /* Dummy pseudo allocator */
745 pseudo_t
alloc_pseudo(struct instruction
*def
)
748 struct pseudo
* pseudo
= __alloc_pseudo(0);
749 pseudo
->type
= PSEUDO_REG
;
755 static void clear_symbol_pseudos(struct entrypoint
*ep
)
759 FOR_EACH_PTR(ep
->accesses
, pseudo
) {
760 pseudo
->sym
->pseudo
= NULL
;
761 } END_FOR_EACH_PTR(pseudo
);
764 static pseudo_t
symbol_pseudo(struct entrypoint
*ep
, struct symbol
*sym
)
771 pseudo
= sym
->pseudo
;
773 pseudo
= __alloc_pseudo(0);
775 pseudo
->type
= PSEUDO_SYM
;
777 pseudo
->ident
= sym
->ident
;
778 sym
->pseudo
= pseudo
;
779 add_pseudo(&ep
->accesses
, pseudo
);
781 /* Symbol pseudos have neither nr, usage nor def */
785 pseudo_t
value_pseudo(long long val
)
787 #define MAX_VAL_HASH 64
788 static struct pseudo_list
*prev
[MAX_VAL_HASH
];
789 int hash
= val
& (MAX_VAL_HASH
-1);
790 struct pseudo_list
**list
= prev
+ hash
;
793 FOR_EACH_PTR(*list
, pseudo
) {
794 if (pseudo
->value
== val
)
796 } END_FOR_EACH_PTR(pseudo
);
798 pseudo
= __alloc_pseudo(0);
799 pseudo
->type
= PSEUDO_VAL
;
801 add_pseudo(list
, pseudo
);
803 /* Value pseudos have neither nr, usage nor def */
807 static pseudo_t
argument_pseudo(struct entrypoint
*ep
, int nr
)
809 pseudo_t pseudo
= __alloc_pseudo(0);
810 struct instruction
*entry
= ep
->entry
;
812 pseudo
->type
= PSEUDO_ARG
;
815 add_pseudo(&entry
->arg_list
, pseudo
);
817 /* Argument pseudos have neither usage nor def */
821 pseudo_t
alloc_phi(struct basic_block
*source
, pseudo_t pseudo
, int size
)
823 struct instruction
*insn
;
830 insn
= alloc_instruction(OP_PHISOURCE
, size
);
831 phi
= __alloc_pseudo(0);
832 phi
->type
= PSEUDO_PHI
;
836 use_pseudo(insn
, pseudo
, &insn
->phi_src
);
839 add_instruction(&source
->insns
, insn
);
844 * We carry the "access_data" structure around for any accesses,
845 * which simplifies things a lot. It contains all the access
846 * information in one place.
849 struct symbol
*result_type
; // result ctype
850 struct symbol
*source_type
; // source ctype
851 pseudo_t address
; // pseudo containing address ..
852 unsigned int offset
; // byte offset
856 static void finish_address_gen(struct entrypoint
*ep
, struct access_data
*ad
)
860 static int linearize_simple_address(struct entrypoint
*ep
,
861 struct expression
*addr
,
862 struct access_data
*ad
)
864 if (addr
->type
== EXPR_SYMBOL
) {
865 linearize_one_symbol(ep
, addr
->symbol
);
866 ad
->address
= symbol_pseudo(ep
, addr
->symbol
);
869 if (addr
->type
== EXPR_BINOP
) {
870 if (addr
->right
->type
== EXPR_VALUE
) {
871 if (addr
->op
== '+') {
872 ad
->offset
+= get_expression_value(addr
->right
);
873 return linearize_simple_address(ep
, addr
->left
, ad
);
877 ad
->address
= linearize_expression(ep
, addr
);
881 static struct symbol
*base_type(struct symbol
*sym
)
883 struct symbol
*base
= sym
;
886 if (sym
->type
== SYM_NODE
)
887 base
= base
->ctype
.base_type
;
888 if (base
->type
== SYM_BITFIELD
)
889 return base
->ctype
.base_type
;
894 static int linearize_address_gen(struct entrypoint
*ep
,
895 struct expression
*expr
,
896 struct access_data
*ad
)
898 struct symbol
*ctype
= expr
->ctype
;
903 ad
->result_type
= ctype
;
904 ad
->source_type
= base_type(ctype
);
905 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '*')
906 return linearize_simple_address(ep
, expr
->unop
, ad
);
908 warning(expr
->pos
, "generating address of non-lvalue (%d)", expr
->type
);
912 static pseudo_t
add_load(struct entrypoint
*ep
, struct access_data
*ad
)
914 struct instruction
*insn
;
917 insn
= alloc_typed_instruction(OP_LOAD
, ad
->source_type
);
918 new = alloc_pseudo(insn
);
921 insn
->offset
= ad
->offset
;
922 use_pseudo(insn
, ad
->address
, &insn
->src
);
923 add_one_insn(ep
, insn
);
927 static void add_store(struct entrypoint
*ep
, struct access_data
*ad
, pseudo_t value
)
929 struct basic_block
*bb
= ep
->active
;
931 if (bb_reachable(bb
)) {
932 struct instruction
*store
= alloc_typed_instruction(OP_STORE
, ad
->source_type
);
933 store
->offset
= ad
->offset
;
934 use_pseudo(store
, value
, &store
->target
);
935 use_pseudo(store
, ad
->address
, &store
->src
);
936 add_one_insn(ep
, store
);
940 static pseudo_t
linearize_store_gen(struct entrypoint
*ep
,
942 struct access_data
*ad
)
944 pseudo_t store
= value
;
946 if (type_size(ad
->source_type
) != type_size(ad
->result_type
)) {
947 struct symbol
*ctype
= ad
->result_type
;
948 unsigned int shift
= ctype
->bit_offset
;
949 unsigned int size
= ctype
->bit_size
;
950 pseudo_t orig
= add_load(ep
, ad
);
951 unsigned long long mask
= (1ULL << size
) - 1;
954 store
= add_binary_op(ep
, ad
->source_type
, OP_SHL
, value
, value_pseudo(shift
));
957 orig
= add_binary_op(ep
, ad
->source_type
, OP_AND
, orig
, value_pseudo(~mask
));
958 store
= add_binary_op(ep
, ad
->source_type
, OP_OR
, orig
, store
);
960 add_store(ep
, ad
, store
);
964 static pseudo_t
add_binary_op(struct entrypoint
*ep
, struct symbol
*ctype
, int op
, pseudo_t left
, pseudo_t right
)
966 struct instruction
*insn
= alloc_typed_instruction(op
, ctype
);
967 pseudo_t target
= alloc_pseudo(insn
);
968 insn
->target
= target
;
969 use_pseudo(insn
, left
, &insn
->src1
);
970 use_pseudo(insn
, right
, &insn
->src2
);
971 add_one_insn(ep
, insn
);
975 static pseudo_t
add_setval(struct entrypoint
*ep
, struct symbol
*ctype
, struct expression
*val
)
977 struct instruction
*insn
= alloc_typed_instruction(OP_SETVAL
, ctype
);
978 pseudo_t target
= alloc_pseudo(insn
);
979 insn
->target
= target
;
981 add_one_insn(ep
, insn
);
985 static pseudo_t
add_symbol_address(struct entrypoint
*ep
, struct symbol
*sym
)
987 struct instruction
*insn
= alloc_instruction(OP_SYMADDR
, bits_in_pointer
);
988 pseudo_t target
= alloc_pseudo(insn
);
990 insn
->target
= target
;
991 use_pseudo(insn
, symbol_pseudo(ep
, sym
), &insn
->symbol
);
992 add_one_insn(ep
, insn
);
996 static pseudo_t
linearize_load_gen(struct entrypoint
*ep
, struct access_data
*ad
)
998 struct symbol
*ctype
= ad
->result_type
;
999 pseudo_t
new = add_load(ep
, ad
);
1001 if (ctype
->bit_offset
) {
1002 pseudo_t shift
= value_pseudo(ctype
->bit_offset
);
1003 pseudo_t newval
= add_binary_op(ep
, ad
->source_type
, OP_LSR
, new, shift
);
1006 if (ctype
->bit_size
!= type_size(ad
->source_type
))
1007 new = cast_pseudo(ep
, new, ad
->source_type
, ad
->result_type
);
1011 static pseudo_t
linearize_access(struct entrypoint
*ep
, struct expression
*expr
)
1013 struct access_data ad
= { NULL
, };
1016 if (!linearize_address_gen(ep
, expr
, &ad
))
1018 value
= linearize_load_gen(ep
, &ad
);
1019 finish_address_gen(ep
, &ad
);
1024 static pseudo_t
linearize_inc_dec(struct entrypoint
*ep
, struct expression
*expr
, int postop
)
1026 struct access_data ad
= { NULL
, };
1027 pseudo_t old
, new, one
;
1028 int op
= expr
->op
== SPECIAL_INCREMENT
? OP_ADD
: OP_SUB
;
1030 if (!linearize_address_gen(ep
, expr
->unop
, &ad
))
1033 old
= linearize_load_gen(ep
, &ad
);
1034 one
= value_pseudo(expr
->op_value
);
1035 new = add_binary_op(ep
, expr
->ctype
, op
, old
, one
);
1036 linearize_store_gen(ep
, new, &ad
);
1037 finish_address_gen(ep
, &ad
);
1038 return postop
? old
: new;
1041 static pseudo_t
add_uniop(struct entrypoint
*ep
, struct expression
*expr
, int op
, pseudo_t src
)
1043 struct instruction
*insn
= alloc_typed_instruction(op
, expr
->ctype
);
1044 pseudo_t
new = alloc_pseudo(insn
);
1047 use_pseudo(insn
, src
, &insn
->src1
);
1048 add_one_insn(ep
, insn
);
1052 static pseudo_t
linearize_slice(struct entrypoint
*ep
, struct expression
*expr
)
1054 pseudo_t pre
= linearize_expression(ep
, expr
->base
);
1055 struct instruction
*insn
= alloc_typed_instruction(OP_SLICE
, expr
->ctype
);
1056 pseudo_t
new = alloc_pseudo(insn
);
1059 insn
->from
= expr
->r_bitpos
;
1060 insn
->len
= expr
->r_nrbits
;
1061 use_pseudo(insn
, pre
, &insn
->base
);
1062 add_one_insn(ep
, insn
);
1066 static pseudo_t
linearize_regular_preop(struct entrypoint
*ep
, struct expression
*expr
)
1068 pseudo_t pre
= linearize_expression(ep
, expr
->unop
);
1073 pseudo_t zero
= value_pseudo(0);
1074 return add_binary_op(ep
, expr
->ctype
, OP_SET_EQ
, pre
, zero
);
1077 return add_uniop(ep
, expr
, OP_NOT
, pre
);
1079 return add_uniop(ep
, expr
, OP_NEG
, pre
);
1084 static pseudo_t
linearize_preop(struct entrypoint
*ep
, struct expression
*expr
)
1087 * '*' is an lvalue access, and is fundamentally different
1088 * from an arithmetic operation. Maybe it should have an
1089 * expression type of its own..
1091 if (expr
->op
== '*')
1092 return linearize_access(ep
, expr
);
1093 if (expr
->op
== SPECIAL_INCREMENT
|| expr
->op
== SPECIAL_DECREMENT
)
1094 return linearize_inc_dec(ep
, expr
, 0);
1095 return linearize_regular_preop(ep
, expr
);
1098 static pseudo_t
linearize_postop(struct entrypoint
*ep
, struct expression
*expr
)
1100 return linearize_inc_dec(ep
, expr
, 1);
1104 * Casts to pointers are "less safe" than other casts, since
1105 * they imply type-unsafe accesses. "void *" is a special
1106 * case, since you can't access through it anyway without another
1109 static struct instruction
*alloc_cast_instruction(struct symbol
*src
, struct symbol
*ctype
)
1111 int opcode
= OP_CAST
;
1112 struct symbol
*base
= ctype
;
1114 if (src
->ctype
.modifiers
& MOD_SIGNED
)
1116 if (base
->type
== SYM_NODE
)
1117 base
= base
->ctype
.base_type
;
1118 if (base
->type
== SYM_PTR
) {
1119 base
= base
->ctype
.base_type
;
1120 if (base
!= &void_ctype
)
1121 opcode
= OP_PTRCAST
;
1122 } else if (base
->ctype
.base_type
== &fp_type
)
1124 return alloc_typed_instruction(opcode
, ctype
);
1127 static pseudo_t
cast_pseudo(struct entrypoint
*ep
, pseudo_t src
, struct symbol
*from
, struct symbol
*to
)
1130 struct instruction
*insn
;
1136 if (from
->bit_size
< 0 || to
->bit_size
< 0)
1138 insn
= alloc_cast_instruction(from
, to
);
1139 result
= alloc_pseudo(insn
);
1140 insn
->target
= result
;
1141 insn
->orig_type
= from
;
1142 use_pseudo(insn
, src
, &insn
->src
);
1143 add_one_insn(ep
, insn
);
1147 static int opcode_sign(int opcode
, struct symbol
*ctype
)
1149 if (ctype
&& (ctype
->ctype
.modifiers
& MOD_SIGNED
)) {
1151 case OP_MULU
: case OP_DIVU
: case OP_MODU
: case OP_LSR
:
1158 static inline pseudo_t
add_convert_to_bool(struct entrypoint
*ep
, pseudo_t src
, struct symbol
*type
)
1163 if (is_bool_type(type
))
1165 zero
= value_pseudo(0);
1167 return add_binary_op(ep
, &bool_ctype
, op
, src
, zero
);
1170 static pseudo_t
linearize_expression_to_bool(struct entrypoint
*ep
, struct expression
*expr
)
1173 dst
= linearize_expression(ep
, expr
);
1174 dst
= add_convert_to_bool(ep
, dst
, expr
->ctype
);
1178 static pseudo_t
linearize_assignment(struct entrypoint
*ep
, struct expression
*expr
)
1180 struct access_data ad
= { NULL
, };
1181 struct expression
*target
= expr
->left
;
1182 struct expression
*src
= expr
->right
;
1183 struct symbol
*ctype
;
1186 value
= linearize_expression(ep
, src
);
1187 if (!target
|| !linearize_address_gen(ep
, target
, &ad
))
1189 if (expr
->op
!= '=') {
1190 pseudo_t oldvalue
= linearize_load_gen(ep
, &ad
);
1192 static const int op_trans
[] = {
1193 [SPECIAL_ADD_ASSIGN
- SPECIAL_BASE
] = OP_ADD
,
1194 [SPECIAL_SUB_ASSIGN
- SPECIAL_BASE
] = OP_SUB
,
1195 [SPECIAL_MUL_ASSIGN
- SPECIAL_BASE
] = OP_MULU
,
1196 [SPECIAL_DIV_ASSIGN
- SPECIAL_BASE
] = OP_DIVU
,
1197 [SPECIAL_MOD_ASSIGN
- SPECIAL_BASE
] = OP_MODU
,
1198 [SPECIAL_SHL_ASSIGN
- SPECIAL_BASE
] = OP_SHL
,
1199 [SPECIAL_SHR_ASSIGN
- SPECIAL_BASE
] = OP_LSR
,
1200 [SPECIAL_AND_ASSIGN
- SPECIAL_BASE
] = OP_AND
,
1201 [SPECIAL_OR_ASSIGN
- SPECIAL_BASE
] = OP_OR
,
1202 [SPECIAL_XOR_ASSIGN
- SPECIAL_BASE
] = OP_XOR
1210 oldvalue
= cast_pseudo(ep
, oldvalue
, target
->ctype
, ctype
);
1211 opcode
= opcode_sign(op_trans
[expr
->op
- SPECIAL_BASE
], ctype
);
1212 dst
= add_binary_op(ep
, ctype
, opcode
, oldvalue
, value
);
1213 value
= cast_pseudo(ep
, dst
, ctype
, expr
->ctype
);
1215 value
= linearize_store_gen(ep
, value
, &ad
);
1216 finish_address_gen(ep
, &ad
);
1220 static pseudo_t
linearize_call_expression(struct entrypoint
*ep
, struct expression
*expr
)
1222 struct expression
*arg
, *fn
;
1223 struct instruction
*insn
= alloc_typed_instruction(OP_CALL
, expr
->ctype
);
1224 pseudo_t retval
, call
;
1225 struct ctype
*ctype
= NULL
;
1226 struct symbol
*fntype
;
1227 struct context
*context
;
1230 warning(expr
->pos
, "call with no type!");
1234 FOR_EACH_PTR(expr
->args
, arg
) {
1235 pseudo_t
new = linearize_expression(ep
, arg
);
1236 use_pseudo(insn
, new, add_pseudo(&insn
->arguments
, new));
1237 } END_FOR_EACH_PTR(arg
);
1242 ctype
= &fn
->ctype
->ctype
;
1246 if (fntype
->type
== SYM_NODE
)
1247 fntype
= fntype
->ctype
.base_type
;
1249 insn
->fntype
= fntype
;
1251 if (fn
->type
== EXPR_PREOP
) {
1252 if (fn
->unop
->type
== EXPR_SYMBOL
) {
1253 struct symbol
*sym
= fn
->unop
->symbol
;
1254 if (sym
->ctype
.base_type
->type
== SYM_FN
)
1258 if (fn
->type
== EXPR_SYMBOL
) {
1259 call
= symbol_pseudo(ep
, fn
->symbol
);
1261 call
= linearize_expression(ep
, fn
);
1263 use_pseudo(insn
, call
, &insn
->func
);
1265 if (expr
->ctype
!= &void_ctype
)
1266 retval
= alloc_pseudo(insn
);
1267 insn
->target
= retval
;
1268 add_one_insn(ep
, insn
);
1271 FOR_EACH_PTR(ctype
->contexts
, context
) {
1272 int in
= context
->in
;
1273 int out
= context
->out
;
1284 context_diff
= out
- in
;
1285 if (check
|| context_diff
) {
1286 insn
= alloc_instruction(OP_CONTEXT
, 0);
1287 insn
->increment
= context_diff
;
1288 insn
->check
= check
;
1289 insn
->context_expr
= context
->context
;
1290 add_one_insn(ep
, insn
);
1292 } END_FOR_EACH_PTR(context
);
1298 static pseudo_t
linearize_binop_bool(struct entrypoint
*ep
, struct expression
*expr
)
1300 pseudo_t src1
, src2
, dst
;
1301 int op
= (expr
->op
== SPECIAL_LOGICAL_OR
) ? OP_OR_BOOL
: OP_AND_BOOL
;
1303 src1
= linearize_expression_to_bool(ep
, expr
->left
);
1304 src2
= linearize_expression_to_bool(ep
, expr
->right
);
1305 dst
= add_binary_op(ep
, &bool_ctype
, op
, src1
, src2
);
1306 if (expr
->ctype
!= &bool_ctype
)
1307 dst
= cast_pseudo(ep
, dst
, &bool_ctype
, expr
->ctype
);
1311 static pseudo_t
linearize_binop(struct entrypoint
*ep
, struct expression
*expr
)
1313 pseudo_t src1
, src2
, dst
;
1314 static const int opcode
[] = {
1315 ['+'] = OP_ADD
, ['-'] = OP_SUB
,
1316 ['*'] = OP_MULU
, ['/'] = OP_DIVU
,
1317 ['%'] = OP_MODU
, ['&'] = OP_AND
,
1318 ['|'] = OP_OR
, ['^'] = OP_XOR
,
1319 [SPECIAL_LEFTSHIFT
] = OP_SHL
,
1320 [SPECIAL_RIGHTSHIFT
] = OP_LSR
,
1324 src1
= linearize_expression(ep
, expr
->left
);
1325 src2
= linearize_expression(ep
, expr
->right
);
1326 op
= opcode_sign(opcode
[expr
->op
], expr
->ctype
);
1327 dst
= add_binary_op(ep
, expr
->ctype
, op
, src1
, src2
);
1331 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
1333 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
);
1335 static pseudo_t
linearize_select(struct entrypoint
*ep
, struct expression
*expr
)
1337 pseudo_t cond
, true, false, res
;
1338 struct instruction
*insn
;
1340 true = linearize_expression(ep
, expr
->cond_true
);
1341 false = linearize_expression(ep
, expr
->cond_false
);
1342 cond
= linearize_expression(ep
, expr
->conditional
);
1344 insn
= alloc_typed_instruction(OP_SEL
, expr
->ctype
);
1345 if (!expr
->cond_true
)
1347 use_pseudo(insn
, cond
, &insn
->src1
);
1348 use_pseudo(insn
, true, &insn
->src2
);
1349 use_pseudo(insn
, false, &insn
->src3
);
1351 res
= alloc_pseudo(insn
);
1353 add_one_insn(ep
, insn
);
1357 static pseudo_t
add_join_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1358 pseudo_t phi1
, pseudo_t phi2
)
1361 struct instruction
*phi_node
;
1368 phi_node
= alloc_typed_instruction(OP_PHI
, expr
->ctype
);
1369 use_pseudo(phi_node
, phi1
, add_pseudo(&phi_node
->phi_list
, phi1
));
1370 use_pseudo(phi_node
, phi2
, add_pseudo(&phi_node
->phi_list
, phi2
));
1371 phi_node
->target
= target
= alloc_pseudo(phi_node
);
1372 add_one_insn(ep
, phi_node
);
1376 static pseudo_t
linearize_short_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1377 struct expression
*cond
,
1378 struct expression
*expr_false
)
1380 pseudo_t src1
, src2
;
1381 struct basic_block
*bb_false
;
1382 struct basic_block
*merge
= alloc_basic_block(ep
, expr
->pos
);
1383 pseudo_t phi1
, phi2
;
1384 int size
= type_size(expr
->ctype
);
1386 if (!expr_false
|| !ep
->active
)
1389 bb_false
= alloc_basic_block(ep
, expr_false
->pos
);
1390 src1
= linearize_expression(ep
, cond
);
1391 phi1
= alloc_phi(ep
->active
, src1
, size
);
1392 add_branch(ep
, expr
, src1
, merge
, bb_false
);
1394 set_activeblock(ep
, bb_false
);
1395 src2
= linearize_expression(ep
, expr_false
);
1396 phi2
= alloc_phi(ep
->active
, src2
, size
);
1397 set_activeblock(ep
, merge
);
1399 return add_join_conditional(ep
, expr
, phi1
, phi2
);
1402 static pseudo_t
linearize_conditional(struct entrypoint
*ep
, struct expression
*expr
,
1403 struct expression
*cond
,
1404 struct expression
*expr_true
,
1405 struct expression
*expr_false
)
1407 pseudo_t src1
, src2
;
1408 pseudo_t phi1
, phi2
;
1409 struct basic_block
*bb_true
, *bb_false
, *merge
;
1410 int size
= type_size(expr
->ctype
);
1412 if (!cond
|| !expr_true
|| !expr_false
|| !ep
->active
)
1414 bb_true
= alloc_basic_block(ep
, expr_true
->pos
);
1415 bb_false
= alloc_basic_block(ep
, expr_false
->pos
);
1416 merge
= alloc_basic_block(ep
, expr
->pos
);
1418 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
1420 set_activeblock(ep
, bb_true
);
1421 src1
= linearize_expression(ep
, expr_true
);
1422 phi1
= alloc_phi(ep
->active
, src1
, size
);
1423 add_goto(ep
, merge
);
1425 set_activeblock(ep
, bb_false
);
1426 src2
= linearize_expression(ep
, expr_false
);
1427 phi2
= alloc_phi(ep
->active
, src2
, size
);
1428 set_activeblock(ep
, merge
);
1430 return add_join_conditional(ep
, expr
, phi1
, phi2
);
1433 static pseudo_t
linearize_logical(struct entrypoint
*ep
, struct expression
*expr
)
1435 struct expression
*shortcut
;
1437 shortcut
= alloc_const_expression(expr
->pos
, expr
->op
== SPECIAL_LOGICAL_OR
);
1438 shortcut
->ctype
= expr
->ctype
;
1439 if (expr
->op
== SPECIAL_LOGICAL_OR
)
1440 return linearize_conditional(ep
, expr
, expr
->left
, shortcut
, expr
->right
);
1441 return linearize_conditional(ep
, expr
, expr
->left
, expr
->right
, shortcut
);
1444 static pseudo_t
linearize_compare(struct entrypoint
*ep
, struct expression
*expr
)
1446 static const int cmpop
[] = {
1447 ['>'] = OP_SET_GT
, ['<'] = OP_SET_LT
,
1448 [SPECIAL_EQUAL
] = OP_SET_EQ
,
1449 [SPECIAL_NOTEQUAL
] = OP_SET_NE
,
1450 [SPECIAL_GTE
] = OP_SET_GE
,
1451 [SPECIAL_LTE
] = OP_SET_LE
,
1452 [SPECIAL_UNSIGNED_LT
] = OP_SET_B
,
1453 [SPECIAL_UNSIGNED_GT
] = OP_SET_A
,
1454 [SPECIAL_UNSIGNED_LTE
] = OP_SET_BE
,
1455 [SPECIAL_UNSIGNED_GTE
] = OP_SET_AE
,
1458 pseudo_t src1
= linearize_expression(ep
, expr
->left
);
1459 pseudo_t src2
= linearize_expression(ep
, expr
->right
);
1460 pseudo_t dst
= add_binary_op(ep
, expr
->ctype
, cmpop
[expr
->op
], src1
, src2
);
1465 pseudo_t
linearize_cond_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1469 if (!expr
|| !bb_reachable(ep
->active
))
1472 switch (expr
->type
) {
1476 add_goto(ep
, expr
->value
? bb_true
: bb_false
);
1480 add_goto(ep
, expr
->fvalue
? bb_true
: bb_false
);
1484 linearize_logical_branch(ep
, expr
, bb_true
, bb_false
);
1488 cond
= linearize_compare(ep
, expr
);
1489 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1493 if (expr
->op
== '!')
1494 return linearize_cond_branch(ep
, expr
->unop
, bb_false
, bb_true
);
1497 cond
= linearize_expression(ep
, expr
);
1498 add_branch(ep
, expr
, cond
, bb_true
, bb_false
);
1508 static pseudo_t
linearize_logical_branch(struct entrypoint
*ep
, struct expression
*expr
, struct basic_block
*bb_true
, struct basic_block
*bb_false
)
1510 struct basic_block
*next
= alloc_basic_block(ep
, expr
->pos
);
1512 if (expr
->op
== SPECIAL_LOGICAL_OR
)
1513 linearize_cond_branch(ep
, expr
->left
, bb_true
, next
);
1515 linearize_cond_branch(ep
, expr
->left
, next
, bb_false
);
1516 set_activeblock(ep
, next
);
1517 linearize_cond_branch(ep
, expr
->right
, bb_true
, bb_false
);
1521 static pseudo_t
linearize_cast(struct entrypoint
*ep
, struct expression
*expr
)
1524 struct expression
*orig
= expr
->cast_expression
;
1529 src
= linearize_expression(ep
, orig
);
1530 return cast_pseudo(ep
, src
, orig
->ctype
, expr
->ctype
);
1533 static pseudo_t
linearize_position(struct entrypoint
*ep
, struct expression
*pos
, struct access_data
*ad
)
1535 struct expression
*init_expr
= pos
->init_expr
;
1537 ad
->offset
= pos
->init_offset
;
1538 ad
->source_type
= base_type(init_expr
->ctype
);
1539 ad
->result_type
= init_expr
->ctype
;
1540 return linearize_initializer(ep
, init_expr
, ad
);
1543 static pseudo_t
linearize_initializer(struct entrypoint
*ep
, struct expression
*initializer
, struct access_data
*ad
)
1545 switch (initializer
->type
) {
1546 case EXPR_INITIALIZER
: {
1547 struct expression
*expr
;
1548 FOR_EACH_PTR(initializer
->expr_list
, expr
) {
1549 linearize_initializer(ep
, expr
, ad
);
1550 } END_FOR_EACH_PTR(expr
);
1554 linearize_position(ep
, initializer
, ad
);
1557 pseudo_t value
= linearize_expression(ep
, initializer
);
1558 ad
->source_type
= base_type(initializer
->ctype
);
1559 ad
->result_type
= initializer
->ctype
;
1560 linearize_store_gen(ep
, value
, ad
);
1568 static void linearize_argument(struct entrypoint
*ep
, struct symbol
*arg
, int nr
)
1570 struct access_data ad
= { NULL
, };
1572 ad
.source_type
= arg
;
1573 ad
.result_type
= arg
;
1574 ad
.address
= symbol_pseudo(ep
, arg
);
1575 linearize_store_gen(ep
, argument_pseudo(ep
, nr
), &ad
);
1576 finish_address_gen(ep
, &ad
);
1579 pseudo_t
linearize_expression(struct entrypoint
*ep
, struct expression
*expr
)
1584 current_pos
= expr
->pos
;
1585 switch (expr
->type
) {
1587 linearize_one_symbol(ep
, expr
->symbol
);
1588 return add_symbol_address(ep
, expr
->symbol
);
1591 return value_pseudo(expr
->value
);
1593 case EXPR_STRING
: case EXPR_FVALUE
: case EXPR_LABEL
:
1594 return add_setval(ep
, expr
->ctype
, expr
);
1596 case EXPR_STATEMENT
:
1597 return linearize_statement(ep
, expr
->statement
);
1600 return linearize_call_expression(ep
, expr
);
1603 if (expr
->op
== SPECIAL_LOGICAL_AND
|| expr
->op
== SPECIAL_LOGICAL_OR
)
1604 return linearize_binop_bool(ep
, expr
);
1605 return linearize_binop(ep
, expr
);
1608 return linearize_logical(ep
, expr
);
1611 return linearize_compare(ep
, expr
);
1614 return linearize_select(ep
, expr
);
1616 case EXPR_CONDITIONAL
:
1617 if (!expr
->cond_true
)
1618 return linearize_short_conditional(ep
, expr
, expr
->conditional
, expr
->cond_false
);
1620 return linearize_conditional(ep
, expr
, expr
->conditional
,
1621 expr
->cond_true
, expr
->cond_false
);
1624 linearize_expression(ep
, expr
->left
);
1625 return linearize_expression(ep
, expr
->right
);
1627 case EXPR_ASSIGNMENT
:
1628 return linearize_assignment(ep
, expr
);
1631 return linearize_preop(ep
, expr
);
1634 return linearize_postop(ep
, expr
);
1637 case EXPR_FORCE_CAST
:
1638 case EXPR_IMPLIED_CAST
:
1639 return linearize_cast(ep
, expr
);
1642 return linearize_slice(ep
, expr
);
1644 case EXPR_INITIALIZER
:
1646 warning(expr
->pos
, "unexpected initializer expression (%d %d)", expr
->type
, expr
->op
);
1649 warning(expr
->pos
, "unknown expression (%d %d)", expr
->type
, expr
->op
);
1655 static pseudo_t
linearize_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
)
1657 struct access_data ad
= { NULL
, };
1660 if (!sym
|| !sym
->initializer
|| sym
->initialized
)
1663 /* We need to output these puppies some day too.. */
1664 if (sym
->ctype
.modifiers
& (MOD_STATIC
| MOD_TOPLEVEL
))
1667 sym
->initialized
= 1;
1668 ad
.address
= symbol_pseudo(ep
, sym
);
1670 if (sym
->initializer
&& !is_scalar_type(sym
)) {
1671 // default zero initialization [6.7.9.21]
1672 // FIXME: this init the whole aggregate while
1673 // only the existing fields need to be initialized.
1674 // FIXME: this init the whole aggregate even if
1675 // all fields arelater explicitely initialized.
1676 struct expression
*expr
= sym
->initializer
;
1678 ad
.result_type
= sym
;
1679 ad
.source_type
= base_type(sym
);
1680 ad
.address
= symbol_pseudo(ep
, sym
);
1681 linearize_store_gen(ep
, value_pseudo(0), &ad
);
1684 value
= linearize_initializer(ep
, sym
->initializer
, &ad
);
1685 finish_address_gen(ep
, &ad
);
1689 static pseudo_t
linearize_compound_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1692 struct statement
*s
;
1693 struct symbol
*ret
= stmt
->ret
;
1696 FOR_EACH_PTR(stmt
->stmts
, s
) {
1697 pseudo
= linearize_statement(ep
, s
);
1698 } END_FOR_EACH_PTR(s
);
1701 struct basic_block
*bb
= add_label(ep
, ret
);
1702 struct instruction
*phi_node
= first_instruction(bb
->insns
);
1707 if (pseudo_list_size(phi_node
->phi_list
)==1) {
1708 pseudo
= first_pseudo(phi_node
->phi_list
);
1709 assert(pseudo
->type
== PSEUDO_PHI
);
1710 return pseudo
->def
->src1
;
1712 return phi_node
->target
;
1718 static pseudo_t
linearize_inlined_call(struct entrypoint
*ep
, struct statement
*stmt
)
1720 struct instruction
*insn
= alloc_instruction(OP_INLINED_CALL
, 0);
1721 struct statement
*args
= stmt
->args
;
1722 struct basic_block
*bb
;
1728 concat_symbol_list(args
->declaration
, &ep
->syms
);
1729 FOR_EACH_PTR(args
->declaration
, sym
) {
1730 pseudo_t value
= linearize_one_symbol(ep
, sym
);
1731 use_pseudo(insn
, value
, add_pseudo(&insn
->arguments
, value
));
1732 } END_FOR_EACH_PTR(sym
);
1735 insn
->target
= pseudo
= linearize_compound_statement(ep
, stmt
);
1736 use_pseudo(insn
, symbol_pseudo(ep
, stmt
->inline_fn
), &insn
->func
);
1738 if (bb
&& !bb
->insns
)
1739 bb
->pos
= stmt
->pos
;
1740 add_one_insn(ep
, insn
);
1744 static pseudo_t
linearize_context(struct entrypoint
*ep
, struct statement
*stmt
)
1746 struct instruction
*insn
= alloc_instruction(OP_CONTEXT
, 0);
1747 struct expression
*expr
= stmt
->expression
;
1750 if (expr
->type
== EXPR_VALUE
)
1751 value
= expr
->value
;
1753 insn
->increment
= value
;
1754 insn
->context_expr
= stmt
->context
;
1755 add_one_insn(ep
, insn
);
1759 static pseudo_t
linearize_range(struct entrypoint
*ep
, struct statement
*stmt
)
1761 struct instruction
*insn
= alloc_instruction(OP_RANGE
, 0);
1763 use_pseudo(insn
, linearize_expression(ep
, stmt
->range_expression
), &insn
->src1
);
1764 use_pseudo(insn
, linearize_expression(ep
, stmt
->range_low
), &insn
->src2
);
1765 use_pseudo(insn
, linearize_expression(ep
, stmt
->range_high
), &insn
->src3
);
1766 add_one_insn(ep
, insn
);
1770 ALLOCATOR(asm_rules
, "asm rules");
1771 ALLOCATOR(asm_constraint
, "asm constraints");
1773 static void add_asm_input(struct entrypoint
*ep
, struct instruction
*insn
, struct expression
*expr
,
1774 const char *constraint
, const struct ident
*ident
)
1776 pseudo_t pseudo
= linearize_expression(ep
, expr
);
1777 struct asm_constraint
*rule
= __alloc_asm_constraint(0);
1779 rule
->ident
= ident
;
1780 rule
->constraint
= constraint
;
1781 use_pseudo(insn
, pseudo
, &rule
->pseudo
);
1782 add_ptr_list(&insn
->asm_rules
->inputs
, rule
);
1785 static void add_asm_output(struct entrypoint
*ep
, struct instruction
*insn
, struct expression
*expr
,
1786 const char *constraint
, const struct ident
*ident
)
1788 struct access_data ad
= { NULL
, };
1789 pseudo_t pseudo
= alloc_pseudo(insn
);
1790 struct asm_constraint
*rule
;
1792 if (!expr
|| !linearize_address_gen(ep
, expr
, &ad
))
1794 linearize_store_gen(ep
, pseudo
, &ad
);
1795 finish_address_gen(ep
, &ad
);
1796 rule
= __alloc_asm_constraint(0);
1797 rule
->ident
= ident
;
1798 rule
->constraint
= constraint
;
1799 use_pseudo(insn
, pseudo
, &rule
->pseudo
);
1800 add_ptr_list(&insn
->asm_rules
->outputs
, rule
);
1803 static pseudo_t
linearize_asm_statement(struct entrypoint
*ep
, struct statement
*stmt
)
1806 struct expression
*expr
;
1807 struct instruction
*insn
;
1808 struct asm_rules
*rules
;
1809 const char *constraint
;
1810 struct ident
*ident
;
1812 insn
= alloc_instruction(OP_ASM
, 0);
1813 expr
= stmt
->asm_string
;
1814 if (!expr
|| expr
->type
!= EXPR_STRING
) {
1815 warning(stmt
->pos
, "expected string in inline asm");
1818 insn
->string
= expr
->string
->data
;
1820 rules
= __alloc_asm_rules(0);
1821 insn
->asm_rules
= rules
;
1823 /* Gather the inputs.. */
1827 FOR_EACH_PTR(stmt
->asm_inputs
, expr
) {
1829 case 0: /* Identifier */
1831 ident
= (struct ident
*)expr
;
1834 case 1: /* Constraint */
1836 constraint
= expr
? expr
->string
->data
: "";
1839 case 2: /* Expression */
1841 add_asm_input(ep
, insn
, expr
, constraint
, ident
);
1843 } END_FOR_EACH_PTR(expr
);
1845 add_one_insn(ep
, insn
);
1847 /* Assign the outputs */
1851 FOR_EACH_PTR(stmt
->asm_outputs
, expr
) {
1853 case 0: /* Identifier */
1855 ident
= (struct ident
*)expr
;
1858 case 1: /* Constraint */
1860 constraint
= expr
? expr
->string
->data
: "";
1865 add_asm_output(ep
, insn
, expr
, constraint
, ident
);
1867 } END_FOR_EACH_PTR(expr
);
1872 static int multijmp_cmp(const void *_a
, const void *_b
)
1874 const struct multijmp
*a
= _a
;
1875 const struct multijmp
*b
= _b
;
1878 if (a
->begin
> a
->end
) {
1879 if (b
->begin
> b
->end
)
1883 if (b
->begin
> b
->end
)
1885 if (a
->begin
== b
->begin
) {
1886 if (a
->end
== b
->end
)
1888 return (a
->end
< b
->end
) ? -1 : 1;
1890 return a
->begin
< b
->begin
? -1 : 1;
1893 static void sort_switch_cases(struct instruction
*insn
)
1895 sort_list((struct ptr_list
**)&insn
->multijmp_list
, multijmp_cmp
);
1898 static pseudo_t
linearize_declaration(struct entrypoint
*ep
, struct statement
*stmt
)
1902 concat_symbol_list(stmt
->declaration
, &ep
->syms
);
1904 FOR_EACH_PTR(stmt
->declaration
, sym
) {
1905 linearize_one_symbol(ep
, sym
);
1906 } END_FOR_EACH_PTR(sym
);
1910 static pseudo_t
linearize_return(struct entrypoint
*ep
, struct statement
*stmt
)
1912 struct expression
*expr
= stmt
->expression
;
1913 struct basic_block
*bb_return
= get_bound_block(ep
, stmt
->ret_target
);
1914 struct basic_block
*active
;
1915 pseudo_t src
= linearize_expression(ep
, expr
);
1916 active
= ep
->active
;
1917 if (active
&& src
!= VOID
) {
1918 struct instruction
*phi_node
= first_instruction(bb_return
->insns
);
1921 phi_node
= alloc_typed_instruction(OP_PHI
, expr
->ctype
);
1922 phi_node
->target
= alloc_pseudo(phi_node
);
1923 phi_node
->bb
= bb_return
;
1924 add_instruction(&bb_return
->insns
, phi_node
);
1926 phi
= alloc_phi(active
, src
, type_size(expr
->ctype
));
1927 phi
->ident
= &return_ident
;
1928 use_pseudo(phi_node
, phi
, add_pseudo(&phi_node
->phi_list
, phi
));
1930 add_goto(ep
, bb_return
);
1934 static pseudo_t
linearize_switch(struct entrypoint
*ep
, struct statement
*stmt
)
1937 struct instruction
*switch_ins
;
1938 struct basic_block
*switch_end
= alloc_basic_block(ep
, stmt
->pos
);
1939 struct basic_block
*active
, *default_case
;
1940 struct multijmp
*jmp
;
1943 pseudo
= linearize_expression(ep
, stmt
->switch_expression
);
1945 active
= ep
->active
;
1946 if (!bb_reachable(active
))
1949 switch_ins
= alloc_instruction(OP_SWITCH
, 0);
1950 use_pseudo(switch_ins
, pseudo
, &switch_ins
->cond
);
1951 add_one_insn(ep
, switch_ins
);
1954 default_case
= NULL
;
1955 FOR_EACH_PTR(stmt
->switch_case
->symbol_list
, sym
) {
1956 struct statement
*case_stmt
= sym
->stmt
;
1957 struct basic_block
*bb_case
= get_bound_block(ep
, sym
);
1959 if (!case_stmt
->case_expression
) {
1960 default_case
= bb_case
;
1965 begin
= end
= case_stmt
->case_expression
->value
;
1966 if (case_stmt
->case_to
)
1967 end
= case_stmt
->case_to
->value
;
1969 jmp
= alloc_multijmp(bb_case
, end
, begin
);
1971 jmp
= alloc_multijmp(bb_case
, begin
, end
);
1974 add_multijmp(&switch_ins
->multijmp_list
, jmp
);
1975 add_bb(&bb_case
->parents
, active
);
1976 add_bb(&active
->children
, bb_case
);
1977 } END_FOR_EACH_PTR(sym
);
1979 bind_label(stmt
->switch_break
, switch_end
, stmt
->pos
);
1981 /* And linearize the actual statement */
1982 linearize_statement(ep
, stmt
->switch_statement
);
1983 set_activeblock(ep
, switch_end
);
1986 default_case
= switch_end
;
1988 jmp
= alloc_multijmp(default_case
, 1, 0);
1989 add_multijmp(&switch_ins
->multijmp_list
, jmp
);
1990 add_bb(&default_case
->parents
, active
);
1991 add_bb(&active
->children
, default_case
);
1992 sort_switch_cases(switch_ins
);
1997 static pseudo_t
linearize_iterator(struct entrypoint
*ep
, struct statement
*stmt
)
1999 struct statement
*pre_statement
= stmt
->iterator_pre_statement
;
2000 struct expression
*pre_condition
= stmt
->iterator_pre_condition
;
2001 struct statement
*statement
= stmt
->iterator_statement
;
2002 struct statement
*post_statement
= stmt
->iterator_post_statement
;
2003 struct expression
*post_condition
= stmt
->iterator_post_condition
;
2004 struct basic_block
*loop_top
, *loop_body
, *loop_continue
, *loop_end
;
2007 FOR_EACH_PTR(stmt
->iterator_syms
, sym
) {
2008 linearize_one_symbol(ep
, sym
);
2009 } END_FOR_EACH_PTR(sym
);
2010 concat_symbol_list(stmt
->iterator_syms
, &ep
->syms
);
2011 linearize_statement(ep
, pre_statement
);
2013 loop_body
= loop_top
= alloc_basic_block(ep
, stmt
->pos
);
2014 loop_continue
= alloc_basic_block(ep
, stmt
->pos
);
2015 loop_end
= alloc_basic_block(ep
, stmt
->pos
);
2017 /* An empty post-condition means that it's the same as the pre-condition */
2018 if (!post_condition
) {
2019 loop_top
= alloc_basic_block(ep
, stmt
->pos
);
2020 set_activeblock(ep
, loop_top
);
2024 linearize_cond_branch(ep
, pre_condition
, loop_body
, loop_end
);
2026 bind_label(stmt
->iterator_continue
, loop_continue
, stmt
->pos
);
2027 bind_label(stmt
->iterator_break
, loop_end
, stmt
->pos
);
2029 set_activeblock(ep
, loop_body
);
2030 linearize_statement(ep
, statement
);
2031 add_goto(ep
, loop_continue
);
2033 set_activeblock(ep
, loop_continue
);
2034 linearize_statement(ep
, post_statement
);
2035 if (!post_condition
)
2036 add_goto(ep
, loop_top
);
2038 linearize_cond_branch(ep
, post_condition
, loop_top
, loop_end
);
2039 set_activeblock(ep
, loop_end
);
2044 pseudo_t
linearize_statement(struct entrypoint
*ep
, struct statement
*stmt
)
2046 struct basic_block
*bb
;
2052 if (bb
&& !bb
->insns
)
2053 bb
->pos
= stmt
->pos
;
2054 current_pos
= stmt
->pos
;
2056 switch (stmt
->type
) {
2060 case STMT_DECLARATION
:
2061 return linearize_declaration(ep
, stmt
);
2064 return linearize_context(ep
, stmt
);
2067 return linearize_range(ep
, stmt
);
2069 case STMT_EXPRESSION
:
2070 return linearize_expression(ep
, stmt
->expression
);
2073 return linearize_asm_statement(ep
, stmt
);
2076 return linearize_return(ep
, stmt
);
2079 add_label(ep
, stmt
->case_label
);
2080 linearize_statement(ep
, stmt
->case_statement
);
2085 struct symbol
*label
= stmt
->label_identifier
;
2088 add_label(ep
, label
);
2090 return linearize_statement(ep
, stmt
->label_statement
);
2095 struct expression
*expr
;
2096 struct instruction
*goto_ins
;
2097 struct basic_block
*active
;
2100 active
= ep
->active
;
2101 if (!bb_reachable(active
))
2104 if (stmt
->goto_label
) {
2105 add_goto(ep
, get_bound_block(ep
, stmt
->goto_label
));
2109 expr
= stmt
->goto_expression
;
2113 /* This can happen as part of simplification */
2114 if (expr
->type
== EXPR_LABEL
) {
2115 add_goto(ep
, get_bound_block(ep
, expr
->label_symbol
));
2119 pseudo
= linearize_expression(ep
, expr
);
2120 goto_ins
= alloc_instruction(OP_COMPUTEDGOTO
, 0);
2121 use_pseudo(goto_ins
, pseudo
, &goto_ins
->target
);
2122 add_one_insn(ep
, goto_ins
);
2124 FOR_EACH_PTR(stmt
->target_list
, sym
) {
2125 struct basic_block
*bb_computed
= get_bound_block(ep
, sym
);
2126 struct multijmp
*jmp
= alloc_multijmp(bb_computed
, 1, 0);
2127 add_multijmp(&goto_ins
->multijmp_list
, jmp
);
2128 add_bb(&bb_computed
->parents
, ep
->active
);
2129 add_bb(&active
->children
, bb_computed
);
2130 } END_FOR_EACH_PTR(sym
);
2137 if (stmt
->inline_fn
)
2138 return linearize_inlined_call(ep
, stmt
);
2139 return linearize_compound_statement(ep
, stmt
);
2142 * This could take 'likely/unlikely' into account, and
2143 * switch the arms around appropriately..
2146 struct basic_block
*bb_true
, *bb_false
, *endif
;
2147 struct expression
*cond
= stmt
->if_conditional
;
2149 bb_true
= alloc_basic_block(ep
, stmt
->pos
);
2150 bb_false
= endif
= alloc_basic_block(ep
, stmt
->pos
);
2152 linearize_cond_branch(ep
, cond
, bb_true
, bb_false
);
2154 set_activeblock(ep
, bb_true
);
2155 linearize_statement(ep
, stmt
->if_true
);
2157 if (stmt
->if_false
) {
2158 endif
= alloc_basic_block(ep
, stmt
->pos
);
2159 add_goto(ep
, endif
);
2160 set_activeblock(ep
, bb_false
);
2161 linearize_statement(ep
, stmt
->if_false
);
2163 set_activeblock(ep
, endif
);
2168 return linearize_switch(ep
, stmt
);
2171 return linearize_iterator(ep
, stmt
);
2179 static struct entrypoint
*linearize_fn(struct symbol
*sym
, struct symbol
*base_type
)
2181 struct entrypoint
*ep
;
2182 struct basic_block
*bb
;
2184 struct instruction
*entry
;
2188 if (!base_type
->stmt
)
2191 ep
= alloc_entrypoint();
2192 bb
= alloc_basic_block(ep
, sym
->pos
);
2196 set_activeblock(ep
, bb
);
2198 entry
= alloc_instruction(OP_ENTRY
, 0);
2199 add_one_insn(ep
, entry
);
2202 concat_symbol_list(base_type
->arguments
, &ep
->syms
);
2204 /* FIXME!! We should do something else about varargs.. */
2206 FOR_EACH_PTR(base_type
->arguments
, arg
) {
2207 linearize_argument(ep
, arg
, ++i
);
2208 } END_FOR_EACH_PTR(arg
);
2210 result
= linearize_statement(ep
, base_type
->stmt
);
2211 if (bb_reachable(ep
->active
) && !bb_terminated(ep
->active
)) {
2212 struct symbol
*ret_type
= base_type
->ctype
.base_type
;
2213 struct instruction
*insn
= alloc_typed_instruction(OP_RET
, ret_type
);
2215 if (type_size(ret_type
) > 0)
2216 use_pseudo(insn
, result
, &insn
->src
);
2217 add_one_insn(ep
, insn
);
2220 if (fdump_linearize
) {
2221 if (fdump_linearize
== 2)
2227 * Do trivial flow simplification - branches to
2228 * branches, kill dead basicblocks etc
2230 kill_unreachable_bbs(ep
);
2233 * Turn symbols into pseudos
2235 simplify_symbol_usage(ep
);
2239 * Remove trivial instructions, and try to CSE
2243 cleanup_and_cse(ep
);
2244 pack_basic_blocks(ep
);
2245 } while (repeat_phase
& REPEAT_CSE
);
2247 kill_unreachable_bbs(ep
);
2251 clear_symbol_pseudos(ep
);
2253 /* And track pseudo register usage */
2254 track_pseudo_liveness(ep
);
2257 * Some flow optimizations can only effectively
2258 * be done when we've done liveness analysis. But
2259 * if they trigger, we need to start all over
2262 if (simplify_flow(ep
)) {
2267 /* Finally, add deathnotes to pseudos now that we have them */
2269 track_pseudo_death(ep
);
2274 struct entrypoint
*linearize_symbol(struct symbol
*sym
)
2276 struct symbol
*base_type
;
2280 current_pos
= sym
->pos
;
2281 base_type
= sym
->ctype
.base_type
;
2284 if (base_type
->type
== SYM_FN
)
2285 return linearize_fn(sym
, base_type
);