11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Linearize - walk the statement tree (but _not_ the expressions)
31f5207b7SJohn Levon * to generate a linear version of it and the basic blocks.
41f5207b7SJohn Levon *
51f5207b7SJohn Levon * NOTE! We're not interested in the actual sub-expressions yet,
61f5207b7SJohn Levon * even though they can generate conditional branches and
71f5207b7SJohn Levon * subroutine calls. That's all "local" behaviour.
81f5207b7SJohn Levon *
91f5207b7SJohn Levon * Copyright (C) 2004 Linus Torvalds
101f5207b7SJohn Levon * Copyright (C) 2004 Christopher Li
111f5207b7SJohn Levon */
121f5207b7SJohn Levon
131f5207b7SJohn Levon #include <string.h>
141f5207b7SJohn Levon #include <stdarg.h>
151f5207b7SJohn Levon #include <stdlib.h>
161f5207b7SJohn Levon #include <stdio.h>
171f5207b7SJohn Levon #include <assert.h>
181f5207b7SJohn Levon
191f5207b7SJohn Levon #include "parse.h"
201f5207b7SJohn Levon #include "expression.h"
211f5207b7SJohn Levon #include "linearize.h"
22*c85f09ccSJohn Levon #include "optimize.h"
231f5207b7SJohn Levon #include "flow.h"
241f5207b7SJohn Levon #include "target.h"
251f5207b7SJohn Levon
26*c85f09ccSJohn Levon static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
27*c85f09ccSJohn Levon static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
281f5207b7SJohn Levon
29*c85f09ccSJohn Levon static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to, struct symbol *from, int op, pseudo_t src);
301f5207b7SJohn Levon static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
311f5207b7SJohn Levon static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
321f5207b7SJohn Levon static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym);
331f5207b7SJohn Levon
341f5207b7SJohn Levon struct access_data;
351f5207b7SJohn Levon static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
361f5207b7SJohn Levon static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
371f5207b7SJohn Levon static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to);
381f5207b7SJohn Levon
391f5207b7SJohn Levon struct pseudo void_pseudo = {};
401f5207b7SJohn Levon
411f5207b7SJohn Levon static struct position current_pos;
421f5207b7SJohn Levon
431f5207b7SJohn Levon ALLOCATOR(pseudo_user, "pseudo_user");
441f5207b7SJohn Levon
alloc_instruction(int opcode,int size)451f5207b7SJohn Levon static struct instruction *alloc_instruction(int opcode, int size)
461f5207b7SJohn Levon {
471f5207b7SJohn Levon struct instruction * insn = __alloc_instruction(0);
481f5207b7SJohn Levon insn->opcode = opcode;
491f5207b7SJohn Levon insn->size = size;
501f5207b7SJohn Levon insn->pos = current_pos;
511f5207b7SJohn Levon return insn;
521f5207b7SJohn Levon }
531f5207b7SJohn Levon
type_size(struct symbol * type)541f5207b7SJohn Levon static inline int type_size(struct symbol *type)
551f5207b7SJohn Levon {
561f5207b7SJohn Levon return type ? type->bit_size > 0 ? type->bit_size : 0 : 0;
571f5207b7SJohn Levon }
581f5207b7SJohn Levon
alloc_typed_instruction(int opcode,struct symbol * type)591f5207b7SJohn Levon static struct instruction *alloc_typed_instruction(int opcode, struct symbol *type)
601f5207b7SJohn Levon {
611f5207b7SJohn Levon struct instruction *insn = alloc_instruction(opcode, type_size(type));
621f5207b7SJohn Levon insn->type = type;
631f5207b7SJohn Levon return insn;
641f5207b7SJohn Levon }
651f5207b7SJohn Levon
alloc_entrypoint(void)661f5207b7SJohn Levon static struct entrypoint *alloc_entrypoint(void)
671f5207b7SJohn Levon {
681f5207b7SJohn Levon return __alloc_entrypoint(0);
691f5207b7SJohn Levon }
701f5207b7SJohn Levon
alloc_basic_block(struct entrypoint * ep,struct position pos)711f5207b7SJohn Levon static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos)
721f5207b7SJohn Levon {
731f5207b7SJohn Levon static int nr;
741f5207b7SJohn Levon struct basic_block *bb = __alloc_basic_block(0);
751f5207b7SJohn Levon bb->pos = pos;
761f5207b7SJohn Levon bb->ep = ep;
771f5207b7SJohn Levon bb->nr = nr++;
781f5207b7SJohn Levon return bb;
791f5207b7SJohn Levon }
801f5207b7SJohn Levon
alloc_multijmp(struct basic_block * target,long long begin,long long end)81*c85f09ccSJohn Levon static struct multijmp *alloc_multijmp(struct basic_block *target, long long begin, long long end)
821f5207b7SJohn Levon {
831f5207b7SJohn Levon struct multijmp *multijmp = __alloc_multijmp(0);
841f5207b7SJohn Levon multijmp->target = target;
851f5207b7SJohn Levon multijmp->begin = begin;
861f5207b7SJohn Levon multijmp->end = end;
871f5207b7SJohn Levon return multijmp;
881f5207b7SJohn Levon }
891f5207b7SJohn Levon
show_label(struct basic_block * bb)90*c85f09ccSJohn Levon const char *show_label(struct basic_block *bb)
911f5207b7SJohn Levon {
92*c85f09ccSJohn Levon static int n;
93*c85f09ccSJohn Levon static char buffer[4][16];
94*c85f09ccSJohn Levon char *buf = buffer[3 & ++n];
95*c85f09ccSJohn Levon
96*c85f09ccSJohn Levon if (!bb)
97*c85f09ccSJohn Levon return ".L???";
98*c85f09ccSJohn Levon snprintf(buf, 64, ".L%u", bb->nr);
99*c85f09ccSJohn Levon return buf;
1001f5207b7SJohn Levon }
1011f5207b7SJohn Levon
show_pseudo(pseudo_t pseudo)1021f5207b7SJohn Levon const char *show_pseudo(pseudo_t pseudo)
1031f5207b7SJohn Levon {
1041f5207b7SJohn Levon static int n;
1051f5207b7SJohn Levon static char buffer[4][64];
1061f5207b7SJohn Levon char *buf;
1071f5207b7SJohn Levon int i;
1081f5207b7SJohn Levon
1091f5207b7SJohn Levon if (!pseudo)
1101f5207b7SJohn Levon return "no pseudo";
1111f5207b7SJohn Levon if (pseudo == VOID)
1121f5207b7SJohn Levon return "VOID";
1131f5207b7SJohn Levon buf = buffer[3 & ++n];
1141f5207b7SJohn Levon switch(pseudo->type) {
1151f5207b7SJohn Levon case PSEUDO_SYM: {
1161f5207b7SJohn Levon struct symbol *sym = pseudo->sym;
1171f5207b7SJohn Levon struct expression *expr;
1181f5207b7SJohn Levon
119*c85f09ccSJohn Levon if (!sym) {
120*c85f09ccSJohn Levon snprintf(buf, 64, "<bad symbol>");
121*c85f09ccSJohn Levon break;
122*c85f09ccSJohn Levon }
1231f5207b7SJohn Levon if (sym->bb_target) {
124*c85f09ccSJohn Levon snprintf(buf, 64, "%s", show_label(sym->bb_target));
1251f5207b7SJohn Levon break;
1261f5207b7SJohn Levon }
1271f5207b7SJohn Levon if (sym->ident) {
1281f5207b7SJohn Levon snprintf(buf, 64, "%s", show_ident(sym->ident));
1291f5207b7SJohn Levon break;
1301f5207b7SJohn Levon }
1311f5207b7SJohn Levon expr = sym->initializer;
132*c85f09ccSJohn Levon snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
1331f5207b7SJohn Levon if (expr) {
1341f5207b7SJohn Levon switch (expr->type) {
1351f5207b7SJohn Levon case EXPR_VALUE:
1361f5207b7SJohn Levon snprintf(buf, 64, "<symbol value: %lld>", expr->value);
1371f5207b7SJohn Levon break;
1381f5207b7SJohn Levon case EXPR_STRING:
1391f5207b7SJohn Levon return show_string(expr->string);
1401f5207b7SJohn Levon default:
1411f5207b7SJohn Levon break;
1421f5207b7SJohn Levon }
1431f5207b7SJohn Levon }
1441f5207b7SJohn Levon break;
1451f5207b7SJohn Levon }
1461f5207b7SJohn Levon case PSEUDO_REG:
1471f5207b7SJohn Levon i = snprintf(buf, 64, "%%r%d", pseudo->nr);
1481f5207b7SJohn Levon if (pseudo->ident)
1491f5207b7SJohn Levon sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
1501f5207b7SJohn Levon break;
1511f5207b7SJohn Levon case PSEUDO_VAL: {
1521f5207b7SJohn Levon long long value = pseudo->value;
1531f5207b7SJohn Levon if (value > 1000 || value < -1000)
1541f5207b7SJohn Levon snprintf(buf, 64, "$%#llx", value);
1551f5207b7SJohn Levon else
1561f5207b7SJohn Levon snprintf(buf, 64, "$%lld", value);
1571f5207b7SJohn Levon break;
1581f5207b7SJohn Levon }
1591f5207b7SJohn Levon case PSEUDO_ARG:
1601f5207b7SJohn Levon snprintf(buf, 64, "%%arg%d", pseudo->nr);
1611f5207b7SJohn Levon break;
1621f5207b7SJohn Levon case PSEUDO_PHI:
1631f5207b7SJohn Levon i = snprintf(buf, 64, "%%phi%d", pseudo->nr);
1641f5207b7SJohn Levon if (pseudo->ident)
1651f5207b7SJohn Levon sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
1661f5207b7SJohn Levon break;
167*c85f09ccSJohn Levon case PSEUDO_UNDEF:
168*c85f09ccSJohn Levon return "UNDEF";
1691f5207b7SJohn Levon default:
1701f5207b7SJohn Levon snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
1711f5207b7SJohn Levon }
1721f5207b7SJohn Levon return buf;
1731f5207b7SJohn Levon }
1741f5207b7SJohn Levon
1751f5207b7SJohn Levon static const char *opcodes[] = {
1761f5207b7SJohn Levon [OP_BADOP] = "bad_op",
1771f5207b7SJohn Levon
1781f5207b7SJohn Levon /* Fn entrypoint */
1791f5207b7SJohn Levon [OP_ENTRY] = "<entry-point>",
1801f5207b7SJohn Levon
1811f5207b7SJohn Levon /* Terminator */
1821f5207b7SJohn Levon [OP_RET] = "ret",
1831f5207b7SJohn Levon [OP_BR] = "br",
1841f5207b7SJohn Levon [OP_CBR] = "cbr",
1851f5207b7SJohn Levon [OP_SWITCH] = "switch",
1861f5207b7SJohn Levon [OP_COMPUTEDGOTO] = "jmp *",
1871f5207b7SJohn Levon
1881f5207b7SJohn Levon /* Binary */
1891f5207b7SJohn Levon [OP_ADD] = "add",
1901f5207b7SJohn Levon [OP_SUB] = "sub",
191*c85f09ccSJohn Levon [OP_MUL] = "mul",
1921f5207b7SJohn Levon [OP_DIVU] = "divu",
1931f5207b7SJohn Levon [OP_DIVS] = "divs",
1941f5207b7SJohn Levon [OP_MODU] = "modu",
1951f5207b7SJohn Levon [OP_MODS] = "mods",
1961f5207b7SJohn Levon [OP_SHL] = "shl",
1971f5207b7SJohn Levon [OP_LSR] = "lsr",
1981f5207b7SJohn Levon [OP_ASR] = "asr",
1991f5207b7SJohn Levon
200*c85f09ccSJohn Levon /* Floating-point Binary */
201*c85f09ccSJohn Levon [OP_FADD] = "fadd",
202*c85f09ccSJohn Levon [OP_FSUB] = "fsub",
203*c85f09ccSJohn Levon [OP_FMUL] = "fmul",
204*c85f09ccSJohn Levon [OP_FDIV] = "fdiv",
205*c85f09ccSJohn Levon
2061f5207b7SJohn Levon /* Logical */
2071f5207b7SJohn Levon [OP_AND] = "and",
2081f5207b7SJohn Levon [OP_OR] = "or",
2091f5207b7SJohn Levon [OP_XOR] = "xor",
2101f5207b7SJohn Levon
2111f5207b7SJohn Levon /* Binary comparison */
2121f5207b7SJohn Levon [OP_SET_EQ] = "seteq",
2131f5207b7SJohn Levon [OP_SET_NE] = "setne",
2141f5207b7SJohn Levon [OP_SET_LE] = "setle",
2151f5207b7SJohn Levon [OP_SET_GE] = "setge",
2161f5207b7SJohn Levon [OP_SET_LT] = "setlt",
2171f5207b7SJohn Levon [OP_SET_GT] = "setgt",
2181f5207b7SJohn Levon [OP_SET_B] = "setb",
2191f5207b7SJohn Levon [OP_SET_A] = "seta",
2201f5207b7SJohn Levon [OP_SET_BE] = "setbe",
2211f5207b7SJohn Levon [OP_SET_AE] = "setae",
2221f5207b7SJohn Levon
223*c85f09ccSJohn Levon /* floating-point comparison */
224*c85f09ccSJohn Levon [OP_FCMP_ORD] = "fcmpord",
225*c85f09ccSJohn Levon [OP_FCMP_OEQ] = "fcmpoeq",
226*c85f09ccSJohn Levon [OP_FCMP_ONE] = "fcmpone",
227*c85f09ccSJohn Levon [OP_FCMP_OLE] = "fcmpole",
228*c85f09ccSJohn Levon [OP_FCMP_OGE] = "fcmpoge",
229*c85f09ccSJohn Levon [OP_FCMP_OLT] = "fcmpolt",
230*c85f09ccSJohn Levon [OP_FCMP_OGT] = "fcmpogt",
231*c85f09ccSJohn Levon [OP_FCMP_UEQ] = "fcmpueq",
232*c85f09ccSJohn Levon [OP_FCMP_UNE] = "fcmpune",
233*c85f09ccSJohn Levon [OP_FCMP_ULE] = "fcmpule",
234*c85f09ccSJohn Levon [OP_FCMP_UGE] = "fcmpuge",
235*c85f09ccSJohn Levon [OP_FCMP_ULT] = "fcmpult",
236*c85f09ccSJohn Levon [OP_FCMP_UGT] = "fcmpugt",
237*c85f09ccSJohn Levon [OP_FCMP_UNO] = "fcmpuno",
238*c85f09ccSJohn Levon
2391f5207b7SJohn Levon /* Uni */
2401f5207b7SJohn Levon [OP_NOT] = "not",
2411f5207b7SJohn Levon [OP_NEG] = "neg",
242*c85f09ccSJohn Levon [OP_FNEG] = "fneg",
2431f5207b7SJohn Levon
2441f5207b7SJohn Levon /* Special three-input */
2451f5207b7SJohn Levon [OP_SEL] = "select",
2461f5207b7SJohn Levon
2471f5207b7SJohn Levon /* Memory */
2481f5207b7SJohn Levon [OP_LOAD] = "load",
2491f5207b7SJohn Levon [OP_STORE] = "store",
2501f5207b7SJohn Levon [OP_SETVAL] = "set",
251*c85f09ccSJohn Levon [OP_SETFVAL] = "setfval",
2521f5207b7SJohn Levon [OP_SYMADDR] = "symaddr",
2531f5207b7SJohn Levon
2541f5207b7SJohn Levon /* Other */
2551f5207b7SJohn Levon [OP_PHI] = "phi",
2561f5207b7SJohn Levon [OP_PHISOURCE] = "phisrc",
257*c85f09ccSJohn Levon [OP_SEXT] = "sext",
258*c85f09ccSJohn Levon [OP_ZEXT] = "zext",
259*c85f09ccSJohn Levon [OP_TRUNC] = "trunc",
260*c85f09ccSJohn Levon [OP_FCVTU] = "fcvtu",
261*c85f09ccSJohn Levon [OP_FCVTS] = "fcvts",
262*c85f09ccSJohn Levon [OP_UCVTF] = "ucvtf",
263*c85f09ccSJohn Levon [OP_SCVTF] = "scvtf",
264*c85f09ccSJohn Levon [OP_FCVTF] = "fcvtf",
265*c85f09ccSJohn Levon [OP_UTPTR] = "utptr",
266*c85f09ccSJohn Levon [OP_PTRTU] = "ptrtu",
2671f5207b7SJohn Levon [OP_PTRCAST] = "ptrcast",
2681f5207b7SJohn Levon [OP_INLINED_CALL] = "# call",
2691f5207b7SJohn Levon [OP_CALL] = "call",
2701f5207b7SJohn Levon [OP_SLICE] = "slice",
2711f5207b7SJohn Levon [OP_NOP] = "nop",
2721f5207b7SJohn Levon [OP_DEATHNOTE] = "dead",
2731f5207b7SJohn Levon [OP_ASM] = "asm",
2741f5207b7SJohn Levon
2751f5207b7SJohn Levon /* Sparse tagging (line numbers, context, whatever) */
2761f5207b7SJohn Levon [OP_CONTEXT] = "context",
2771f5207b7SJohn Levon [OP_RANGE] = "range-check",
2781f5207b7SJohn Levon
2791f5207b7SJohn Levon [OP_COPY] = "copy",
2801f5207b7SJohn Levon };
2811f5207b7SJohn Levon
show_asm_constraints(char * buf,const char * sep,struct asm_constraint_list * list)2821f5207b7SJohn Levon static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list)
2831f5207b7SJohn Levon {
2841f5207b7SJohn Levon struct asm_constraint *entry;
2851f5207b7SJohn Levon
2861f5207b7SJohn Levon FOR_EACH_PTR(list, entry) {
2871f5207b7SJohn Levon buf += sprintf(buf, "%s\"%s\"", sep, entry->constraint);
2881f5207b7SJohn Levon if (entry->pseudo)
2891f5207b7SJohn Levon buf += sprintf(buf, " (%s)", show_pseudo(entry->pseudo));
2901f5207b7SJohn Levon if (entry->ident)
2911f5207b7SJohn Levon buf += sprintf(buf, " [%s]", show_ident(entry->ident));
2921f5207b7SJohn Levon sep = ", ";
2931f5207b7SJohn Levon } END_FOR_EACH_PTR(entry);
2941f5207b7SJohn Levon return buf;
2951f5207b7SJohn Levon }
2961f5207b7SJohn Levon
show_asm(char * buf,struct instruction * insn)2971f5207b7SJohn Levon static char *show_asm(char *buf, struct instruction *insn)
2981f5207b7SJohn Levon {
2991f5207b7SJohn Levon struct asm_rules *rules = insn->asm_rules;
3001f5207b7SJohn Levon
3011f5207b7SJohn Levon buf += sprintf(buf, "\"%s\"", insn->string);
3021f5207b7SJohn Levon buf = show_asm_constraints(buf, "\n\t\tout: ", rules->outputs);
3031f5207b7SJohn Levon buf = show_asm_constraints(buf, "\n\t\tin: ", rules->inputs);
3041f5207b7SJohn Levon buf = show_asm_constraints(buf, "\n\t\tclobber: ", rules->clobbers);
3051f5207b7SJohn Levon return buf;
3061f5207b7SJohn Levon }
3071f5207b7SJohn Levon
show_instruction(struct instruction * insn)3081f5207b7SJohn Levon const char *show_instruction(struct instruction *insn)
3091f5207b7SJohn Levon {
3101f5207b7SJohn Levon int opcode = insn->opcode;
3111f5207b7SJohn Levon static char buffer[4096];
3121f5207b7SJohn Levon char *buf;
3131f5207b7SJohn Levon
3141f5207b7SJohn Levon buf = buffer;
3151f5207b7SJohn Levon if (!insn->bb)
3161f5207b7SJohn Levon buf += sprintf(buf, "# ");
3171f5207b7SJohn Levon
3181f5207b7SJohn Levon if (opcode < ARRAY_SIZE(opcodes)) {
3191f5207b7SJohn Levon const char *op = opcodes[opcode];
3201f5207b7SJohn Levon if (!op)
3211f5207b7SJohn Levon buf += sprintf(buf, "opcode:%d", opcode);
3221f5207b7SJohn Levon else
3231f5207b7SJohn Levon buf += sprintf(buf, "%s", op);
3241f5207b7SJohn Levon if (insn->size)
3251f5207b7SJohn Levon buf += sprintf(buf, ".%d", insn->size);
3261f5207b7SJohn Levon memset(buf, ' ', 20);
3271f5207b7SJohn Levon buf++;
3281f5207b7SJohn Levon }
3291f5207b7SJohn Levon
3301f5207b7SJohn Levon if (buf < buffer + 12)
3311f5207b7SJohn Levon buf = buffer + 12;
3321f5207b7SJohn Levon switch (opcode) {
3331f5207b7SJohn Levon case OP_RET:
3341f5207b7SJohn Levon if (insn->src && insn->src != VOID)
3351f5207b7SJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->src));
3361f5207b7SJohn Levon break;
3371f5207b7SJohn Levon
3381f5207b7SJohn Levon case OP_CBR:
339*c85f09ccSJohn Levon buf += sprintf(buf, "%s, %s, %s", show_pseudo(insn->cond), show_label(insn->bb_true), show_label(insn->bb_false));
3401f5207b7SJohn Levon break;
3411f5207b7SJohn Levon
3421f5207b7SJohn Levon case OP_BR:
343*c85f09ccSJohn Levon buf += sprintf(buf, "%s", show_label(insn->bb_true));
3441f5207b7SJohn Levon break;
3451f5207b7SJohn Levon
3461f5207b7SJohn Levon case OP_SETVAL: {
3471f5207b7SJohn Levon struct expression *expr = insn->val;
3481f5207b7SJohn Levon buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
3491f5207b7SJohn Levon
3501f5207b7SJohn Levon if (!expr) {
3511f5207b7SJohn Levon buf += sprintf(buf, "%s", "<none>");
3521f5207b7SJohn Levon break;
3531f5207b7SJohn Levon }
3541f5207b7SJohn Levon
3551f5207b7SJohn Levon switch (expr->type) {
3561f5207b7SJohn Levon case EXPR_VALUE:
3571f5207b7SJohn Levon buf += sprintf(buf, "%lld", expr->value);
3581f5207b7SJohn Levon break;
3591f5207b7SJohn Levon case EXPR_FVALUE:
360*c85f09ccSJohn Levon buf += sprintf(buf, "%Le", expr->fvalue);
3611f5207b7SJohn Levon break;
3621f5207b7SJohn Levon case EXPR_STRING:
3631f5207b7SJohn Levon buf += sprintf(buf, "%.40s", show_string(expr->string));
3641f5207b7SJohn Levon break;
3651f5207b7SJohn Levon case EXPR_SYMBOL:
3661f5207b7SJohn Levon buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
3671f5207b7SJohn Levon break;
3681f5207b7SJohn Levon case EXPR_LABEL:
369*c85f09ccSJohn Levon buf += sprintf(buf, "%s", show_label(expr->symbol->bb_target));
3701f5207b7SJohn Levon break;
3711f5207b7SJohn Levon default:
3721f5207b7SJohn Levon buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
3731f5207b7SJohn Levon }
3741f5207b7SJohn Levon break;
3751f5207b7SJohn Levon }
376*c85f09ccSJohn Levon case OP_SETFVAL:
377*c85f09ccSJohn Levon buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
378*c85f09ccSJohn Levon buf += sprintf(buf, "%Le", insn->fvalue);
379*c85f09ccSJohn Levon break;
380*c85f09ccSJohn Levon
3811f5207b7SJohn Levon case OP_SWITCH: {
3821f5207b7SJohn Levon struct multijmp *jmp;
3831f5207b7SJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->cond));
3841f5207b7SJohn Levon FOR_EACH_PTR(insn->multijmp_list, jmp) {
3851f5207b7SJohn Levon if (jmp->begin == jmp->end)
386*c85f09ccSJohn Levon buf += sprintf(buf, ", %lld -> %s", jmp->begin, show_label(jmp->target));
3871f5207b7SJohn Levon else if (jmp->begin < jmp->end)
388*c85f09ccSJohn Levon buf += sprintf(buf, ", %lld ... %lld -> %s", jmp->begin, jmp->end, show_label(jmp->target));
3891f5207b7SJohn Levon else
390*c85f09ccSJohn Levon buf += sprintf(buf, ", default -> %s", show_label(jmp->target));
3911f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp);
3921f5207b7SJohn Levon break;
3931f5207b7SJohn Levon }
3941f5207b7SJohn Levon case OP_COMPUTEDGOTO: {
3951f5207b7SJohn Levon struct multijmp *jmp;
396*c85f09ccSJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->src));
3971f5207b7SJohn Levon FOR_EACH_PTR(insn->multijmp_list, jmp) {
398*c85f09ccSJohn Levon buf += sprintf(buf, ", %s", show_label(jmp->target));
3991f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp);
4001f5207b7SJohn Levon break;
4011f5207b7SJohn Levon }
4021f5207b7SJohn Levon
4031f5207b7SJohn Levon case OP_PHISOURCE: {
4041f5207b7SJohn Levon struct instruction *phi;
4051f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src));
4061f5207b7SJohn Levon FOR_EACH_PTR(insn->phi_users, phi) {
4071f5207b7SJohn Levon buf += sprintf(buf, " (%s)", show_pseudo(phi->target));
4081f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
4091f5207b7SJohn Levon break;
4101f5207b7SJohn Levon }
4111f5207b7SJohn Levon
4121f5207b7SJohn Levon case OP_PHI: {
4131f5207b7SJohn Levon pseudo_t phi;
4141f5207b7SJohn Levon const char *s = " <-";
4151f5207b7SJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->target));
4161f5207b7SJohn Levon FOR_EACH_PTR(insn->phi_list, phi) {
417*c85f09ccSJohn Levon if (phi == VOID && !verbose)
418*c85f09ccSJohn Levon continue;
4191f5207b7SJohn Levon buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
4201f5207b7SJohn Levon s = ",";
4211f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
4221f5207b7SJohn Levon break;
4231f5207b7SJohn Levon }
424*c85f09ccSJohn Levon case OP_LOAD:
4251f5207b7SJohn Levon buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
4261f5207b7SJohn Levon break;
427*c85f09ccSJohn Levon case OP_STORE:
4281f5207b7SJohn Levon buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
4291f5207b7SJohn Levon break;
4301f5207b7SJohn Levon case OP_INLINED_CALL:
4311f5207b7SJohn Levon case OP_CALL: {
4321f5207b7SJohn Levon struct pseudo *arg;
4331f5207b7SJohn Levon if (insn->target && insn->target != VOID)
4341f5207b7SJohn Levon buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
4351f5207b7SJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->func));
4361f5207b7SJohn Levon FOR_EACH_PTR(insn->arguments, arg) {
4371f5207b7SJohn Levon buf += sprintf(buf, ", %s", show_pseudo(arg));
4381f5207b7SJohn Levon } END_FOR_EACH_PTR(arg);
4391f5207b7SJohn Levon break;
4401f5207b7SJohn Levon }
441*c85f09ccSJohn Levon case OP_SEXT: case OP_ZEXT:
442*c85f09ccSJohn Levon case OP_TRUNC:
443*c85f09ccSJohn Levon case OP_FCVTU: case OP_FCVTS:
444*c85f09ccSJohn Levon case OP_UCVTF: case OP_SCVTF:
445*c85f09ccSJohn Levon case OP_FCVTF:
446*c85f09ccSJohn Levon case OP_UTPTR:
447*c85f09ccSJohn Levon case OP_PTRTU:
4481f5207b7SJohn Levon case OP_PTRCAST:
4491f5207b7SJohn Levon buf += sprintf(buf, "%s <- (%d) %s",
4501f5207b7SJohn Levon show_pseudo(insn->target),
4511f5207b7SJohn Levon type_size(insn->orig_type),
4521f5207b7SJohn Levon show_pseudo(insn->src));
4531f5207b7SJohn Levon break;
4541f5207b7SJohn Levon case OP_BINARY ... OP_BINARY_END:
455*c85f09ccSJohn Levon case OP_FPCMP ... OP_FPCMP_END:
4561f5207b7SJohn Levon case OP_BINCMP ... OP_BINCMP_END:
4571f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
4581f5207b7SJohn Levon break;
4591f5207b7SJohn Levon
4601f5207b7SJohn Levon case OP_SEL:
4611f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target),
4621f5207b7SJohn Levon show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
4631f5207b7SJohn Levon break;
4641f5207b7SJohn Levon
4651f5207b7SJohn Levon case OP_SLICE:
4661f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
4671f5207b7SJohn Levon break;
4681f5207b7SJohn Levon
4691f5207b7SJohn Levon case OP_NOT: case OP_NEG:
470*c85f09ccSJohn Levon case OP_FNEG:
471*c85f09ccSJohn Levon case OP_SYMADDR:
4721f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
4731f5207b7SJohn Levon break;
4741f5207b7SJohn Levon
4751f5207b7SJohn Levon case OP_CONTEXT:
4761f5207b7SJohn Levon buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
4771f5207b7SJohn Levon break;
4781f5207b7SJohn Levon case OP_RANGE:
4791f5207b7SJohn Levon buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
4801f5207b7SJohn Levon break;
4811f5207b7SJohn Levon case OP_NOP:
4821f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
4831f5207b7SJohn Levon break;
4841f5207b7SJohn Levon case OP_DEATHNOTE:
4851f5207b7SJohn Levon buf += sprintf(buf, "%s", show_pseudo(insn->target));
4861f5207b7SJohn Levon break;
4871f5207b7SJohn Levon case OP_ASM:
4881f5207b7SJohn Levon buf = show_asm(buf, insn);
4891f5207b7SJohn Levon break;
4901f5207b7SJohn Levon case OP_COPY:
4911f5207b7SJohn Levon buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src));
4921f5207b7SJohn Levon break;
4931f5207b7SJohn Levon default:
4941f5207b7SJohn Levon break;
4951f5207b7SJohn Levon }
4961f5207b7SJohn Levon
4971f5207b7SJohn Levon if (buf >= buffer + sizeof(buffer))
4981f5207b7SJohn Levon die("instruction buffer overflowed %td\n", buf - buffer);
4991f5207b7SJohn Levon do { --buf; } while (*buf == ' ');
5001f5207b7SJohn Levon *++buf = 0;
5011f5207b7SJohn Levon return buffer;
5021f5207b7SJohn Levon }
5031f5207b7SJohn Levon
show_bb(struct basic_block * bb)5041f5207b7SJohn Levon void show_bb(struct basic_block *bb)
5051f5207b7SJohn Levon {
5061f5207b7SJohn Levon struct instruction *insn;
5071f5207b7SJohn Levon
508*c85f09ccSJohn Levon printf("%s:\n", show_label(bb));
5091f5207b7SJohn Levon if (verbose) {
5101f5207b7SJohn Levon pseudo_t needs, defines;
5111f5207b7SJohn Levon printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
5121f5207b7SJohn Levon
5131f5207b7SJohn Levon FOR_EACH_PTR(bb->needs, needs) {
5141f5207b7SJohn Levon struct instruction *def = needs->def;
5151f5207b7SJohn Levon if (def->opcode != OP_PHI) {
516*c85f09ccSJohn Levon printf(" **uses %s (from %s)**\n", show_pseudo(needs), show_label(def->bb));
5171f5207b7SJohn Levon } else {
5181f5207b7SJohn Levon pseudo_t phi;
5191f5207b7SJohn Levon const char *sep = " ";
5201f5207b7SJohn Levon printf(" **uses %s (from", show_pseudo(needs));
5211f5207b7SJohn Levon FOR_EACH_PTR(def->phi_list, phi) {
5221f5207b7SJohn Levon if (phi == VOID)
5231f5207b7SJohn Levon continue;
524*c85f09ccSJohn Levon printf("%s(%s:%s)", sep, show_pseudo(phi), show_label(phi->def->bb));
5251f5207b7SJohn Levon sep = ", ";
5261f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
5271f5207b7SJohn Levon printf(")**\n");
5281f5207b7SJohn Levon }
5291f5207b7SJohn Levon } END_FOR_EACH_PTR(needs);
5301f5207b7SJohn Levon
5311f5207b7SJohn Levon FOR_EACH_PTR(bb->defines, defines) {
5321f5207b7SJohn Levon printf(" **defines %s **\n", show_pseudo(defines));
5331f5207b7SJohn Levon } END_FOR_EACH_PTR(defines);
5341f5207b7SJohn Levon
5351f5207b7SJohn Levon if (bb->parents) {
5361f5207b7SJohn Levon struct basic_block *from;
5371f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, from) {
538*c85f09ccSJohn Levon printf(" **from %s (%s:%d:%d)**\n", show_label(from),
5391f5207b7SJohn Levon stream_name(from->pos.stream), from->pos.line, from->pos.pos);
5401f5207b7SJohn Levon } END_FOR_EACH_PTR(from);
5411f5207b7SJohn Levon }
5421f5207b7SJohn Levon
5431f5207b7SJohn Levon if (bb->children) {
5441f5207b7SJohn Levon struct basic_block *to;
5451f5207b7SJohn Levon FOR_EACH_PTR(bb->children, to) {
546*c85f09ccSJohn Levon printf(" **to %s (%s:%d:%d)**\n", show_label(to),
5471f5207b7SJohn Levon stream_name(to->pos.stream), to->pos.line, to->pos.pos);
5481f5207b7SJohn Levon } END_FOR_EACH_PTR(to);
5491f5207b7SJohn Levon }
5501f5207b7SJohn Levon }
5511f5207b7SJohn Levon
5521f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
5531f5207b7SJohn Levon if (!insn->bb && verbose < 2)
5541f5207b7SJohn Levon continue;
5551f5207b7SJohn Levon printf("\t%s\n", show_instruction(insn));
5561f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
5571f5207b7SJohn Levon if (!bb_terminated(bb))
5581f5207b7SJohn Levon printf("\tEND\n");
5591f5207b7SJohn Levon }
5601f5207b7SJohn Levon
show_symbol_usage(pseudo_t pseudo)5611f5207b7SJohn Levon static void show_symbol_usage(pseudo_t pseudo)
5621f5207b7SJohn Levon {
5631f5207b7SJohn Levon struct pseudo_user *pu;
5641f5207b7SJohn Levon
5651f5207b7SJohn Levon if (pseudo) {
5661f5207b7SJohn Levon FOR_EACH_PTR(pseudo->users, pu) {
5671f5207b7SJohn Levon printf("\t%s\n", show_instruction(pu->insn));
5681f5207b7SJohn Levon } END_FOR_EACH_PTR(pu);
5691f5207b7SJohn Levon }
5701f5207b7SJohn Levon }
5711f5207b7SJohn Levon
show_entry(struct entrypoint * ep)5721f5207b7SJohn Levon void show_entry(struct entrypoint *ep)
5731f5207b7SJohn Levon {
5741f5207b7SJohn Levon struct symbol *sym;
5751f5207b7SJohn Levon struct basic_block *bb;
5761f5207b7SJohn Levon
5771f5207b7SJohn Levon printf("%s:\n", show_ident(ep->name->ident));
5781f5207b7SJohn Levon
5791f5207b7SJohn Levon if (verbose) {
5801f5207b7SJohn Levon printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
5811f5207b7SJohn Levon
5821f5207b7SJohn Levon FOR_EACH_PTR(ep->syms, sym) {
5831f5207b7SJohn Levon if (!sym->pseudo)
5841f5207b7SJohn Levon continue;
5851f5207b7SJohn Levon if (!sym->pseudo->users)
5861f5207b7SJohn Levon continue;
5871f5207b7SJohn Levon printf(" sym: %p %s\n", sym, show_ident(sym->ident));
5881f5207b7SJohn Levon if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE))
5891f5207b7SJohn Levon printf("\texternal visibility\n");
5901f5207b7SJohn Levon show_symbol_usage(sym->pseudo);
5911f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
5921f5207b7SJohn Levon
5931f5207b7SJohn Levon printf("\n");
5941f5207b7SJohn Levon }
5951f5207b7SJohn Levon
5961f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
5971f5207b7SJohn Levon if (!bb)
5981f5207b7SJohn Levon continue;
5991f5207b7SJohn Levon if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
6001f5207b7SJohn Levon continue;
6011f5207b7SJohn Levon show_bb(bb);
6021f5207b7SJohn Levon printf("\n");
6031f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
6041f5207b7SJohn Levon
6051f5207b7SJohn Levon printf("\n");
6061f5207b7SJohn Levon }
6071f5207b7SJohn Levon
bind_label(struct symbol * label,struct basic_block * bb,struct position pos)6081f5207b7SJohn Levon static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
6091f5207b7SJohn Levon {
6101f5207b7SJohn Levon if (label->bb_target)
6111f5207b7SJohn Levon warning(pos, "label '%s' already bound", show_ident(label->ident));
6121f5207b7SJohn Levon label->bb_target = bb;
6131f5207b7SJohn Levon }
6141f5207b7SJohn Levon
get_bound_block(struct entrypoint * ep,struct symbol * label)6151f5207b7SJohn Levon static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
6161f5207b7SJohn Levon {
6171f5207b7SJohn Levon struct basic_block *bb = label->bb_target;
6181f5207b7SJohn Levon
6191f5207b7SJohn Levon if (!bb) {
6201f5207b7SJohn Levon bb = alloc_basic_block(ep, label->pos);
6211f5207b7SJohn Levon label->bb_target = bb;
6221f5207b7SJohn Levon }
6231f5207b7SJohn Levon return bb;
6241f5207b7SJohn Levon }
6251f5207b7SJohn Levon
finish_block(struct entrypoint * ep)6261f5207b7SJohn Levon static void finish_block(struct entrypoint *ep)
6271f5207b7SJohn Levon {
6281f5207b7SJohn Levon struct basic_block *src = ep->active;
6291f5207b7SJohn Levon if (bb_reachable(src))
6301f5207b7SJohn Levon ep->active = NULL;
6311f5207b7SJohn Levon }
6321f5207b7SJohn Levon
add_goto(struct entrypoint * ep,struct basic_block * dst)6331f5207b7SJohn Levon static void add_goto(struct entrypoint *ep, struct basic_block *dst)
6341f5207b7SJohn Levon {
6351f5207b7SJohn Levon struct basic_block *src = ep->active;
6361f5207b7SJohn Levon if (bb_reachable(src)) {
6371f5207b7SJohn Levon struct instruction *br = alloc_instruction(OP_BR, 0);
6381f5207b7SJohn Levon br->bb_true = dst;
6391f5207b7SJohn Levon add_bb(&dst->parents, src);
6401f5207b7SJohn Levon add_bb(&src->children, dst);
6411f5207b7SJohn Levon br->bb = src;
6421f5207b7SJohn Levon add_instruction(&src->insns, br);
6431f5207b7SJohn Levon ep->active = NULL;
6441f5207b7SJohn Levon }
6451f5207b7SJohn Levon }
6461f5207b7SJohn Levon
add_one_insn(struct entrypoint * ep,struct instruction * insn)6471f5207b7SJohn Levon static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
6481f5207b7SJohn Levon {
6491f5207b7SJohn Levon struct basic_block *bb = ep->active;
6501f5207b7SJohn Levon
6511f5207b7SJohn Levon if (bb_reachable(bb)) {
6521f5207b7SJohn Levon insn->bb = bb;
6531f5207b7SJohn Levon add_instruction(&bb->insns, insn);
6541f5207b7SJohn Levon }
6551f5207b7SJohn Levon }
6561f5207b7SJohn Levon
set_activeblock(struct entrypoint * ep,struct basic_block * bb)6571f5207b7SJohn Levon static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
6581f5207b7SJohn Levon {
6591f5207b7SJohn Levon if (!bb_terminated(ep->active))
6601f5207b7SJohn Levon add_goto(ep, bb);
6611f5207b7SJohn Levon
6621f5207b7SJohn Levon ep->active = bb;
6631f5207b7SJohn Levon if (bb_reachable(bb))
6641f5207b7SJohn Levon add_bb(&ep->bbs, bb);
6651f5207b7SJohn Levon }
6661f5207b7SJohn Levon
remove_parent(struct basic_block * child,struct basic_block * parent)6671f5207b7SJohn Levon static void remove_parent(struct basic_block *child, struct basic_block *parent)
6681f5207b7SJohn Levon {
6691f5207b7SJohn Levon remove_bb_from_list(&child->parents, parent, 1);
6701f5207b7SJohn Levon if (!child->parents)
6711f5207b7SJohn Levon repeat_phase |= REPEAT_CFG_CLEANUP;
6721f5207b7SJohn Levon }
6731f5207b7SJohn Levon
6741f5207b7SJohn Levon /* Change a "switch" or a conditional branch into a branch */
insert_branch(struct basic_block * bb,struct instruction * jmp,struct basic_block * target)6751f5207b7SJohn Levon void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target)
6761f5207b7SJohn Levon {
6771f5207b7SJohn Levon struct instruction *br, *old;
6781f5207b7SJohn Levon struct basic_block *child;
6791f5207b7SJohn Levon
6801f5207b7SJohn Levon /* Remove the switch */
6811f5207b7SJohn Levon old = delete_last_instruction(&bb->insns);
6821f5207b7SJohn Levon assert(old == jmp);
6831f5207b7SJohn Levon kill_instruction(old);
6841f5207b7SJohn Levon
6851f5207b7SJohn Levon br = alloc_instruction(OP_BR, 0);
6861f5207b7SJohn Levon br->bb = bb;
6871f5207b7SJohn Levon br->bb_true = target;
6881f5207b7SJohn Levon add_instruction(&bb->insns, br);
6891f5207b7SJohn Levon
6901f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) {
6911f5207b7SJohn Levon if (child == target) {
6921f5207b7SJohn Levon target = NULL; /* Trigger just once */
6931f5207b7SJohn Levon continue;
6941f5207b7SJohn Levon }
6951f5207b7SJohn Levon DELETE_CURRENT_PTR(child);
6961f5207b7SJohn Levon remove_parent(child, bb);
6971f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
6981f5207b7SJohn Levon PACK_PTR_LIST(&bb->children);
6991f5207b7SJohn Levon }
7001f5207b7SJohn Levon
7011f5207b7SJohn Levon
insert_select(struct basic_block * bb,struct instruction * br,struct instruction * phi_node,pseudo_t if_true,pseudo_t if_false)7021f5207b7SJohn Levon void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false)
7031f5207b7SJohn Levon {
7041f5207b7SJohn Levon pseudo_t target;
7051f5207b7SJohn Levon struct instruction *select;
7061f5207b7SJohn Levon
7071f5207b7SJohn Levon /* Remove the 'br' */
7081f5207b7SJohn Levon delete_last_instruction(&bb->insns);
7091f5207b7SJohn Levon
710*c85f09ccSJohn Levon select = alloc_typed_instruction(OP_SEL, phi_node->type);
7111f5207b7SJohn Levon select->bb = bb;
7121f5207b7SJohn Levon
7131f5207b7SJohn Levon assert(br->cond);
7141f5207b7SJohn Levon use_pseudo(select, br->cond, &select->src1);
7151f5207b7SJohn Levon
7161f5207b7SJohn Levon target = phi_node->target;
7171f5207b7SJohn Levon assert(target->def == phi_node);
7181f5207b7SJohn Levon select->target = target;
7191f5207b7SJohn Levon target->def = select;
7201f5207b7SJohn Levon
7211f5207b7SJohn Levon use_pseudo(select, if_true, &select->src2);
7221f5207b7SJohn Levon use_pseudo(select, if_false, &select->src3);
7231f5207b7SJohn Levon
7241f5207b7SJohn Levon add_instruction(&bb->insns, select);
7251f5207b7SJohn Levon add_instruction(&bb->insns, br);
7261f5207b7SJohn Levon }
7271f5207b7SJohn Levon
bb_empty(struct basic_block * bb)7281f5207b7SJohn Levon static inline int bb_empty(struct basic_block *bb)
7291f5207b7SJohn Levon {
7301f5207b7SJohn Levon return !bb->insns;
7311f5207b7SJohn Levon }
7321f5207b7SJohn Levon
7331f5207b7SJohn Levon /* Add a label to the currently active block, return new active block */
add_label(struct entrypoint * ep,struct symbol * label)7341f5207b7SJohn Levon static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label)
7351f5207b7SJohn Levon {
7361f5207b7SJohn Levon struct basic_block *bb = label->bb_target;
7371f5207b7SJohn Levon
7381f5207b7SJohn Levon if (bb) {
7391f5207b7SJohn Levon set_activeblock(ep, bb);
7401f5207b7SJohn Levon return bb;
7411f5207b7SJohn Levon }
7421f5207b7SJohn Levon bb = ep->active;
7431f5207b7SJohn Levon if (!bb_reachable(bb) || !bb_empty(bb)) {
7441f5207b7SJohn Levon bb = alloc_basic_block(ep, label->pos);
7451f5207b7SJohn Levon set_activeblock(ep, bb);
7461f5207b7SJohn Levon }
7471f5207b7SJohn Levon label->bb_target = bb;
7481f5207b7SJohn Levon return bb;
7491f5207b7SJohn Levon }
7501f5207b7SJohn Levon
add_branch(struct entrypoint * ep,pseudo_t cond,struct basic_block * bb_true,struct basic_block * bb_false)751*c85f09ccSJohn Levon static void add_branch(struct entrypoint *ep, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
7521f5207b7SJohn Levon {
7531f5207b7SJohn Levon struct basic_block *bb = ep->active;
7541f5207b7SJohn Levon struct instruction *br;
7551f5207b7SJohn Levon
7561f5207b7SJohn Levon if (bb_reachable(bb)) {
7571f5207b7SJohn Levon br = alloc_instruction(OP_CBR, 0);
7581f5207b7SJohn Levon use_pseudo(br, cond, &br->cond);
7591f5207b7SJohn Levon br->bb_true = bb_true;
7601f5207b7SJohn Levon br->bb_false = bb_false;
7611f5207b7SJohn Levon add_bb(&bb_true->parents, bb);
7621f5207b7SJohn Levon add_bb(&bb_false->parents, bb);
7631f5207b7SJohn Levon add_bb(&bb->children, bb_true);
7641f5207b7SJohn Levon add_bb(&bb->children, bb_false);
7651f5207b7SJohn Levon add_one_insn(ep, br);
7661f5207b7SJohn Levon }
7671f5207b7SJohn Levon }
7681f5207b7SJohn Levon
alloc_pseudo(struct instruction * def)7691f5207b7SJohn Levon pseudo_t alloc_pseudo(struct instruction *def)
7701f5207b7SJohn Levon {
7711f5207b7SJohn Levon static int nr = 0;
7721f5207b7SJohn Levon struct pseudo * pseudo = __alloc_pseudo(0);
7731f5207b7SJohn Levon pseudo->type = PSEUDO_REG;
7741f5207b7SJohn Levon pseudo->nr = ++nr;
7751f5207b7SJohn Levon pseudo->def = def;
7761f5207b7SJohn Levon return pseudo;
7771f5207b7SJohn Levon }
7781f5207b7SJohn Levon
symbol_pseudo(struct entrypoint * ep,struct symbol * sym)7791f5207b7SJohn Levon static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
7801f5207b7SJohn Levon {
7811f5207b7SJohn Levon pseudo_t pseudo;
7821f5207b7SJohn Levon
7831f5207b7SJohn Levon if (!sym)
7841f5207b7SJohn Levon return VOID;
7851f5207b7SJohn Levon
7861f5207b7SJohn Levon pseudo = sym->pseudo;
7871f5207b7SJohn Levon if (!pseudo) {
7881f5207b7SJohn Levon pseudo = __alloc_pseudo(0);
7891f5207b7SJohn Levon pseudo->nr = -1;
7901f5207b7SJohn Levon pseudo->type = PSEUDO_SYM;
7911f5207b7SJohn Levon pseudo->sym = sym;
7921f5207b7SJohn Levon pseudo->ident = sym->ident;
7931f5207b7SJohn Levon sym->pseudo = pseudo;
7941f5207b7SJohn Levon add_pseudo(&ep->accesses, pseudo);
7951f5207b7SJohn Levon }
796*c85f09ccSJohn Levon /* Symbol pseudos have neither nr nor def */
7971f5207b7SJohn Levon return pseudo;
7981f5207b7SJohn Levon }
7991f5207b7SJohn Levon
value_pseudo(long long val)800*c85f09ccSJohn Levon pseudo_t value_pseudo(long long val)
8011f5207b7SJohn Levon {
8021f5207b7SJohn Levon #define MAX_VAL_HASH 64
8031f5207b7SJohn Levon static struct pseudo_list *prev[MAX_VAL_HASH];
8041f5207b7SJohn Levon int hash = val & (MAX_VAL_HASH-1);
8051f5207b7SJohn Levon struct pseudo_list **list = prev + hash;
8061f5207b7SJohn Levon pseudo_t pseudo;
8071f5207b7SJohn Levon
8081f5207b7SJohn Levon FOR_EACH_PTR(*list, pseudo) {
809*c85f09ccSJohn Levon if (pseudo->value == val)
8101f5207b7SJohn Levon return pseudo;
8111f5207b7SJohn Levon } END_FOR_EACH_PTR(pseudo);
8121f5207b7SJohn Levon
8131f5207b7SJohn Levon pseudo = __alloc_pseudo(0);
8141f5207b7SJohn Levon pseudo->type = PSEUDO_VAL;
8151f5207b7SJohn Levon pseudo->value = val;
8161f5207b7SJohn Levon add_pseudo(list, pseudo);
8171f5207b7SJohn Levon
8181f5207b7SJohn Levon /* Value pseudos have neither nr, usage nor def */
8191f5207b7SJohn Levon return pseudo;
8201f5207b7SJohn Levon }
8211f5207b7SJohn Levon
undef_pseudo(void)822*c85f09ccSJohn Levon pseudo_t undef_pseudo(void)
823*c85f09ccSJohn Levon {
824*c85f09ccSJohn Levon pseudo_t pseudo = __alloc_pseudo(0);
825*c85f09ccSJohn Levon pseudo->type = PSEUDO_UNDEF;
826*c85f09ccSJohn Levon return pseudo;
827*c85f09ccSJohn Levon }
828*c85f09ccSJohn Levon
argument_pseudo(struct entrypoint * ep,int nr)8291f5207b7SJohn Levon static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
8301f5207b7SJohn Levon {
8311f5207b7SJohn Levon pseudo_t pseudo = __alloc_pseudo(0);
8321f5207b7SJohn Levon struct instruction *entry = ep->entry;
8331f5207b7SJohn Levon
8341f5207b7SJohn Levon pseudo->type = PSEUDO_ARG;
8351f5207b7SJohn Levon pseudo->nr = nr;
8361f5207b7SJohn Levon pseudo->def = entry;
8371f5207b7SJohn Levon add_pseudo(&entry->arg_list, pseudo);
8381f5207b7SJohn Levon
8391f5207b7SJohn Levon /* Argument pseudos have neither usage nor def */
8401f5207b7SJohn Levon return pseudo;
8411f5207b7SJohn Levon }
8421f5207b7SJohn Levon
alloc_phisrc(pseudo_t pseudo,struct symbol * type)843*c85f09ccSJohn Levon struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type)
8441f5207b7SJohn Levon {
845*c85f09ccSJohn Levon struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
846*c85f09ccSJohn Levon pseudo_t phi = __alloc_pseudo(0);
8471f5207b7SJohn Levon static int nr = 0;
8481f5207b7SJohn Levon
8491f5207b7SJohn Levon phi->type = PSEUDO_PHI;
8501f5207b7SJohn Levon phi->nr = ++nr;
8511f5207b7SJohn Levon phi->def = insn;
8521f5207b7SJohn Levon
8531f5207b7SJohn Levon use_pseudo(insn, pseudo, &insn->phi_src);
8541f5207b7SJohn Levon insn->target = phi;
855*c85f09ccSJohn Levon return insn;
856*c85f09ccSJohn Levon }
857*c85f09ccSJohn Levon
alloc_phi(struct basic_block * source,pseudo_t pseudo,struct symbol * type)858*c85f09ccSJohn Levon pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
859*c85f09ccSJohn Levon {
860*c85f09ccSJohn Levon struct instruction *insn;
861*c85f09ccSJohn Levon
862*c85f09ccSJohn Levon if (!source)
863*c85f09ccSJohn Levon return VOID;
864*c85f09ccSJohn Levon
865*c85f09ccSJohn Levon insn = alloc_phisrc(pseudo, type);
866*c85f09ccSJohn Levon insn->bb = source;
8671f5207b7SJohn Levon add_instruction(&source->insns, insn);
868*c85f09ccSJohn Levon return insn->target;
869*c85f09ccSJohn Levon }
870*c85f09ccSJohn Levon
alloc_phi_node(struct basic_block * bb,struct symbol * type,struct ident * ident)871*c85f09ccSJohn Levon struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident)
872*c85f09ccSJohn Levon {
873*c85f09ccSJohn Levon struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
874*c85f09ccSJohn Levon pseudo_t phi;
875*c85f09ccSJohn Levon
876*c85f09ccSJohn Levon phi = alloc_pseudo(phi_node);
877*c85f09ccSJohn Levon phi->ident = ident;
878*c85f09ccSJohn Levon phi->def = phi_node;
879*c85f09ccSJohn Levon phi_node->target = phi;
880*c85f09ccSJohn Levon phi_node->bb = bb;
881*c85f09ccSJohn Levon return phi_node;
882*c85f09ccSJohn Levon }
883*c85f09ccSJohn Levon
add_phi_node(struct basic_block * bb,struct instruction * phi_node)884*c85f09ccSJohn Levon void add_phi_node(struct basic_block *bb, struct instruction *phi_node)
885*c85f09ccSJohn Levon {
886*c85f09ccSJohn Levon struct instruction *insn;
887*c85f09ccSJohn Levon
888*c85f09ccSJohn Levon FOR_EACH_PTR(bb->insns, insn) {
889*c85f09ccSJohn Levon enum opcode op = insn->opcode;
890*c85f09ccSJohn Levon if (op == OP_PHI)
891*c85f09ccSJohn Levon continue;
892*c85f09ccSJohn Levon INSERT_CURRENT(phi_node, insn);
893*c85f09ccSJohn Levon return;
894*c85f09ccSJohn Levon } END_FOR_EACH_PTR(insn);
895*c85f09ccSJohn Levon
896*c85f09ccSJohn Levon // FIXME
897*c85f09ccSJohn Levon add_instruction(&bb->insns, phi_node);
898*c85f09ccSJohn Levon }
899*c85f09ccSJohn Levon
insert_phi_node(struct basic_block * bb,struct symbol * var)900*c85f09ccSJohn Levon struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var)
901*c85f09ccSJohn Levon {
902*c85f09ccSJohn Levon struct instruction *phi_node = alloc_phi_node(bb, var, var->ident);
903*c85f09ccSJohn Levon add_phi_node(bb, phi_node);
904*c85f09ccSJohn Levon return phi_node;
9051f5207b7SJohn Levon }
9061f5207b7SJohn Levon
9071f5207b7SJohn Levon /*
9081f5207b7SJohn Levon * We carry the "access_data" structure around for any accesses,
9091f5207b7SJohn Levon * which simplifies things a lot. It contains all the access
9101f5207b7SJohn Levon * information in one place.
9111f5207b7SJohn Levon */
9121f5207b7SJohn Levon struct access_data {
913*c85f09ccSJohn Levon struct symbol *type; // ctype
914*c85f09ccSJohn Levon struct symbol *btype; // base type of bitfields
9151f5207b7SJohn Levon pseudo_t address; // pseudo containing address ..
9161f5207b7SJohn Levon unsigned int offset; // byte offset
9171f5207b7SJohn Levon };
9181f5207b7SJohn Levon
linearize_simple_address(struct entrypoint * ep,struct expression * addr,struct access_data * ad)9191f5207b7SJohn Levon static int linearize_simple_address(struct entrypoint *ep,
9201f5207b7SJohn Levon struct expression *addr,
9211f5207b7SJohn Levon struct access_data *ad)
9221f5207b7SJohn Levon {
9231f5207b7SJohn Levon if (addr->type == EXPR_SYMBOL) {
9241f5207b7SJohn Levon linearize_one_symbol(ep, addr->symbol);
9251f5207b7SJohn Levon ad->address = symbol_pseudo(ep, addr->symbol);
9261f5207b7SJohn Levon return 1;
9271f5207b7SJohn Levon }
9281f5207b7SJohn Levon if (addr->type == EXPR_BINOP) {
9291f5207b7SJohn Levon if (addr->right->type == EXPR_VALUE) {
9301f5207b7SJohn Levon if (addr->op == '+') {
9311f5207b7SJohn Levon ad->offset += get_expression_value(addr->right);
9321f5207b7SJohn Levon return linearize_simple_address(ep, addr->left, ad);
9331f5207b7SJohn Levon }
9341f5207b7SJohn Levon }
9351f5207b7SJohn Levon }
9361f5207b7SJohn Levon ad->address = linearize_expression(ep, addr);
9371f5207b7SJohn Levon return 1;
9381f5207b7SJohn Levon }
9391f5207b7SJohn Levon
bitfield_base_type(struct symbol * sym)940*c85f09ccSJohn Levon static struct symbol *bitfield_base_type(struct symbol *sym)
9411f5207b7SJohn Levon {
9421f5207b7SJohn Levon struct symbol *base = sym;
9431f5207b7SJohn Levon
9441f5207b7SJohn Levon if (sym) {
9451f5207b7SJohn Levon if (sym->type == SYM_NODE)
9461f5207b7SJohn Levon base = base->ctype.base_type;
9471f5207b7SJohn Levon if (base->type == SYM_BITFIELD)
9481f5207b7SJohn Levon return base->ctype.base_type;
9491f5207b7SJohn Levon }
9501f5207b7SJohn Levon return sym;
9511f5207b7SJohn Levon }
9521f5207b7SJohn Levon
linearize_address_gen(struct entrypoint * ep,struct expression * expr,struct access_data * ad)9531f5207b7SJohn Levon static int linearize_address_gen(struct entrypoint *ep,
9541f5207b7SJohn Levon struct expression *expr,
9551f5207b7SJohn Levon struct access_data *ad)
9561f5207b7SJohn Levon {
9571f5207b7SJohn Levon struct symbol *ctype = expr->ctype;
9581f5207b7SJohn Levon
9591f5207b7SJohn Levon if (!ctype)
9601f5207b7SJohn Levon return 0;
961*c85f09ccSJohn Levon ad->type = ctype;
9621f5207b7SJohn Levon if (expr->type == EXPR_PREOP && expr->op == '*')
9631f5207b7SJohn Levon return linearize_simple_address(ep, expr->unop, ad);
9641f5207b7SJohn Levon
9651f5207b7SJohn Levon warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
9661f5207b7SJohn Levon return 0;
9671f5207b7SJohn Levon }
9681f5207b7SJohn Levon
add_load(struct entrypoint * ep,struct access_data * ad)9691f5207b7SJohn Levon static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
9701f5207b7SJohn Levon {
9711f5207b7SJohn Levon struct instruction *insn;
9721f5207b7SJohn Levon pseudo_t new;
9731f5207b7SJohn Levon
974*c85f09ccSJohn Levon if (!ep->active)
975*c85f09ccSJohn Levon return VOID;
976*c85f09ccSJohn Levon
977*c85f09ccSJohn Levon insn = alloc_typed_instruction(OP_LOAD, ad->btype);
9781f5207b7SJohn Levon new = alloc_pseudo(insn);
9791f5207b7SJohn Levon
9801f5207b7SJohn Levon insn->target = new;
9811f5207b7SJohn Levon insn->offset = ad->offset;
982*c85f09ccSJohn Levon insn->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
9831f5207b7SJohn Levon use_pseudo(insn, ad->address, &insn->src);
9841f5207b7SJohn Levon add_one_insn(ep, insn);
9851f5207b7SJohn Levon return new;
9861f5207b7SJohn Levon }
9871f5207b7SJohn Levon
add_store(struct entrypoint * ep,struct access_data * ad,pseudo_t value)9881f5207b7SJohn Levon static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
9891f5207b7SJohn Levon {
9901f5207b7SJohn Levon struct basic_block *bb = ep->active;
991*c85f09ccSJohn Levon struct instruction *store;
9921f5207b7SJohn Levon
993*c85f09ccSJohn Levon if (!bb)
994*c85f09ccSJohn Levon return;
995*c85f09ccSJohn Levon
996*c85f09ccSJohn Levon store = alloc_typed_instruction(OP_STORE, ad->btype);
997*c85f09ccSJohn Levon store->offset = ad->offset;
998*c85f09ccSJohn Levon store->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
999*c85f09ccSJohn Levon use_pseudo(store, value, &store->target);
1000*c85f09ccSJohn Levon use_pseudo(store, ad->address, &store->src);
1001*c85f09ccSJohn Levon add_one_insn(ep, store);
1002*c85f09ccSJohn Levon }
1003*c85f09ccSJohn Levon
linearize_bitfield_insert(struct entrypoint * ep,pseudo_t ori,pseudo_t val,struct symbol * ctype,struct symbol * btype)1004*c85f09ccSJohn Levon static pseudo_t linearize_bitfield_insert(struct entrypoint *ep,
1005*c85f09ccSJohn Levon pseudo_t ori, pseudo_t val, struct symbol *ctype, struct symbol *btype)
1006*c85f09ccSJohn Levon {
1007*c85f09ccSJohn Levon unsigned int shift = ctype->bit_offset;
1008*c85f09ccSJohn Levon unsigned int size = ctype->bit_size;
1009*c85f09ccSJohn Levon unsigned long long mask = ((1ULL << size) - 1);
1010*c85f09ccSJohn Levon unsigned long long smask= bits_mask(btype->bit_size);
1011*c85f09ccSJohn Levon
1012*c85f09ccSJohn Levon val = add_cast(ep, btype, ctype, OP_ZEXT, val);
1013*c85f09ccSJohn Levon if (shift) {
1014*c85f09ccSJohn Levon val = add_binary_op(ep, btype, OP_SHL, val, value_pseudo(shift));
1015*c85f09ccSJohn Levon mask <<= shift;
10161f5207b7SJohn Levon }
1017*c85f09ccSJohn Levon ori = add_binary_op(ep, btype, OP_AND, ori, value_pseudo(~mask & smask));
1018*c85f09ccSJohn Levon val = add_binary_op(ep, btype, OP_OR, ori, val);
1019*c85f09ccSJohn Levon
1020*c85f09ccSJohn Levon return val;
10211f5207b7SJohn Levon }
10221f5207b7SJohn Levon
linearize_store_gen(struct entrypoint * ep,pseudo_t value,struct access_data * ad)10231f5207b7SJohn Levon static pseudo_t linearize_store_gen(struct entrypoint *ep,
10241f5207b7SJohn Levon pseudo_t value,
10251f5207b7SJohn Levon struct access_data *ad)
10261f5207b7SJohn Levon {
1027*c85f09ccSJohn Levon struct symbol *ctype = ad->type;
1028*c85f09ccSJohn Levon struct symbol *btype;
10291f5207b7SJohn Levon pseudo_t store = value;
10301f5207b7SJohn Levon
1031*c85f09ccSJohn Levon if (!ep->active)
1032*c85f09ccSJohn Levon return VOID;
10331f5207b7SJohn Levon
1034*c85f09ccSJohn Levon btype = ad->btype = bitfield_base_type(ctype);
1035*c85f09ccSJohn Levon if (type_size(btype) != type_size(ctype)) {
1036*c85f09ccSJohn Levon pseudo_t orig = add_load(ep, ad);
1037*c85f09ccSJohn Levon store = linearize_bitfield_insert(ep, orig, value, ctype, btype);
10381f5207b7SJohn Levon }
10391f5207b7SJohn Levon add_store(ep, ad, store);
10401f5207b7SJohn Levon return value;
10411f5207b7SJohn Levon }
10421f5207b7SJohn Levon
taint_undefined_behaviour(struct instruction * insn)1043*c85f09ccSJohn Levon static void taint_undefined_behaviour(struct instruction *insn)
1044*c85f09ccSJohn Levon {
1045*c85f09ccSJohn Levon pseudo_t src2;
1046*c85f09ccSJohn Levon
1047*c85f09ccSJohn Levon switch (insn->opcode) {
1048*c85f09ccSJohn Levon case OP_LSR:
1049*c85f09ccSJohn Levon case OP_ASR:
1050*c85f09ccSJohn Levon case OP_SHL:
1051*c85f09ccSJohn Levon src2 = insn->src2;
1052*c85f09ccSJohn Levon if (src2->type != PSEUDO_VAL)
1053*c85f09ccSJohn Levon break;
1054*c85f09ccSJohn Levon if ((unsigned long long)src2->value >= insn->size)
1055*c85f09ccSJohn Levon insn->tainted = 1;
1056*c85f09ccSJohn Levon break;
1057*c85f09ccSJohn Levon }
1058*c85f09ccSJohn Levon }
1059*c85f09ccSJohn Levon
add_binary_op(struct entrypoint * ep,struct symbol * ctype,int op,pseudo_t left,pseudo_t right)10601f5207b7SJohn Levon static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
10611f5207b7SJohn Levon {
10621f5207b7SJohn Levon struct instruction *insn = alloc_typed_instruction(op, ctype);
10631f5207b7SJohn Levon pseudo_t target = alloc_pseudo(insn);
10641f5207b7SJohn Levon insn->target = target;
10651f5207b7SJohn Levon use_pseudo(insn, left, &insn->src1);
10661f5207b7SJohn Levon use_pseudo(insn, right, &insn->src2);
10671f5207b7SJohn Levon add_one_insn(ep, insn);
10681f5207b7SJohn Levon return target;
10691f5207b7SJohn Levon }
10701f5207b7SJohn Levon
add_setval(struct entrypoint * ep,struct symbol * ctype,struct expression * val)10711f5207b7SJohn Levon static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
10721f5207b7SJohn Levon {
10731f5207b7SJohn Levon struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype);
10741f5207b7SJohn Levon pseudo_t target = alloc_pseudo(insn);
10751f5207b7SJohn Levon insn->target = target;
10761f5207b7SJohn Levon insn->val = val;
10771f5207b7SJohn Levon add_one_insn(ep, insn);
10781f5207b7SJohn Levon return target;
10791f5207b7SJohn Levon }
10801f5207b7SJohn Levon
add_setfval(struct entrypoint * ep,struct symbol * ctype,long double fval)1081*c85f09ccSJohn Levon static pseudo_t add_setfval(struct entrypoint *ep, struct symbol *ctype, long double fval)
1082*c85f09ccSJohn Levon {
1083*c85f09ccSJohn Levon struct instruction *insn = alloc_typed_instruction(OP_SETFVAL, ctype);
1084*c85f09ccSJohn Levon pseudo_t target = alloc_pseudo(insn);
1085*c85f09ccSJohn Levon insn->target = target;
1086*c85f09ccSJohn Levon insn->fvalue = fval;
1087*c85f09ccSJohn Levon add_one_insn(ep, insn);
1088*c85f09ccSJohn Levon return target;
1089*c85f09ccSJohn Levon }
1090*c85f09ccSJohn Levon
add_symbol_address(struct entrypoint * ep,struct symbol * sym)10911f5207b7SJohn Levon static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
10921f5207b7SJohn Levon {
10931f5207b7SJohn Levon struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
10941f5207b7SJohn Levon pseudo_t target = alloc_pseudo(insn);
10951f5207b7SJohn Levon
10961f5207b7SJohn Levon insn->target = target;
1097*c85f09ccSJohn Levon use_pseudo(insn, symbol_pseudo(ep, sym), &insn->src);
10981f5207b7SJohn Levon add_one_insn(ep, insn);
10991f5207b7SJohn Levon return target;
11001f5207b7SJohn Levon }
11011f5207b7SJohn Levon
linearize_bitfield_extract(struct entrypoint * ep,pseudo_t val,struct symbol * ctype,struct symbol * btype)1102*c85f09ccSJohn Levon static pseudo_t linearize_bitfield_extract(struct entrypoint *ep,
1103*c85f09ccSJohn Levon pseudo_t val, struct symbol *ctype, struct symbol *btype)
11041f5207b7SJohn Levon {
1105*c85f09ccSJohn Levon unsigned int off = ctype->bit_offset;
11061f5207b7SJohn Levon
1107*c85f09ccSJohn Levon if (off) {
1108*c85f09ccSJohn Levon pseudo_t shift = value_pseudo(off);
1109*c85f09ccSJohn Levon val = add_binary_op(ep, btype, OP_LSR, val, shift);
11101f5207b7SJohn Levon }
1111*c85f09ccSJohn Levon val = cast_pseudo(ep, val, btype, ctype);
1112*c85f09ccSJohn Levon return val;
1113*c85f09ccSJohn Levon }
1114*c85f09ccSJohn Levon
linearize_load_gen(struct entrypoint * ep,struct access_data * ad)1115*c85f09ccSJohn Levon static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
1116*c85f09ccSJohn Levon {
1117*c85f09ccSJohn Levon struct symbol *ctype = ad->type;
1118*c85f09ccSJohn Levon struct symbol *btype;
1119*c85f09ccSJohn Levon pseudo_t new;
1120*c85f09ccSJohn Levon
1121*c85f09ccSJohn Levon if (!ep->active)
1122*c85f09ccSJohn Levon return VOID;
1123*c85f09ccSJohn Levon
1124*c85f09ccSJohn Levon btype = ad->btype = bitfield_base_type(ctype);
1125*c85f09ccSJohn Levon new = add_load(ep, ad);
1126*c85f09ccSJohn Levon if (ctype->bit_size != type_size(btype))
1127*c85f09ccSJohn Levon new = linearize_bitfield_extract(ep, new, ctype, btype);
11281f5207b7SJohn Levon return new;
11291f5207b7SJohn Levon }
11301f5207b7SJohn Levon
linearize_access(struct entrypoint * ep,struct expression * expr)11311f5207b7SJohn Levon static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
11321f5207b7SJohn Levon {
11331f5207b7SJohn Levon struct access_data ad = { NULL, };
11341f5207b7SJohn Levon pseudo_t value;
11351f5207b7SJohn Levon
11361f5207b7SJohn Levon if (!linearize_address_gen(ep, expr, &ad))
11371f5207b7SJohn Levon return VOID;
11381f5207b7SJohn Levon value = linearize_load_gen(ep, &ad);
11391f5207b7SJohn Levon return value;
11401f5207b7SJohn Levon }
11411f5207b7SJohn Levon
linearize_inc_dec(struct entrypoint * ep,struct expression * expr,int postop)11421f5207b7SJohn Levon static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
11431f5207b7SJohn Levon {
11441f5207b7SJohn Levon struct access_data ad = { NULL, };
1145*c85f09ccSJohn Levon pseudo_t old, new, one;
11461f5207b7SJohn Levon int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
11471f5207b7SJohn Levon
11481f5207b7SJohn Levon if (!linearize_address_gen(ep, expr->unop, &ad))
11491f5207b7SJohn Levon return VOID;
11501f5207b7SJohn Levon
11511f5207b7SJohn Levon old = linearize_load_gen(ep, &ad);
1152*c85f09ccSJohn Levon op = opcode_float(op, expr->ctype);
1153*c85f09ccSJohn Levon if (is_float_type(expr->ctype))
1154*c85f09ccSJohn Levon one = add_setfval(ep, expr->ctype, expr->op_value);
1155*c85f09ccSJohn Levon else
1156*c85f09ccSJohn Levon one = value_pseudo(expr->op_value);
1157*c85f09ccSJohn Levon if (ad.btype != ad.type)
1158*c85f09ccSJohn Levon old = cast_pseudo(ep, old, ad.type, ad.btype);
1159*c85f09ccSJohn Levon new = add_binary_op(ep, ad.btype, op, old, one);
1160*c85f09ccSJohn Levon if (ad.btype != ad.type)
1161*c85f09ccSJohn Levon new = cast_pseudo(ep, new, ad.btype, ad.type);
11621f5207b7SJohn Levon linearize_store_gen(ep, new, &ad);
11631f5207b7SJohn Levon return postop ? old : new;
11641f5207b7SJohn Levon }
11651f5207b7SJohn Levon
add_unop(struct entrypoint * ep,struct symbol * ctype,int op,pseudo_t src)1166*c85f09ccSJohn Levon static pseudo_t add_unop(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t src)
11671f5207b7SJohn Levon {
1168*c85f09ccSJohn Levon struct instruction *insn = alloc_typed_instruction(op, ctype);
11691f5207b7SJohn Levon pseudo_t new = alloc_pseudo(insn);
11701f5207b7SJohn Levon
11711f5207b7SJohn Levon insn->target = new;
11721f5207b7SJohn Levon use_pseudo(insn, src, &insn->src1);
11731f5207b7SJohn Levon add_one_insn(ep, insn);
11741f5207b7SJohn Levon return new;
11751f5207b7SJohn Levon }
11761f5207b7SJohn Levon
add_cast(struct entrypoint * ep,struct symbol * to,struct symbol * from,int op,pseudo_t src)1177*c85f09ccSJohn Levon static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to,
1178*c85f09ccSJohn Levon struct symbol *from, int op, pseudo_t src)
1179*c85f09ccSJohn Levon {
1180*c85f09ccSJohn Levon pseudo_t new = add_unop(ep, to, op, src);
1181*c85f09ccSJohn Levon new->def->orig_type = from;
1182*c85f09ccSJohn Levon return new;
1183*c85f09ccSJohn Levon }
1184*c85f09ccSJohn Levon
linearize_slice(struct entrypoint * ep,struct expression * expr)11851f5207b7SJohn Levon static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
11861f5207b7SJohn Levon {
11871f5207b7SJohn Levon pseudo_t pre = linearize_expression(ep, expr->base);
11881f5207b7SJohn Levon struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
11891f5207b7SJohn Levon pseudo_t new = alloc_pseudo(insn);
11901f5207b7SJohn Levon
11911f5207b7SJohn Levon insn->target = new;
11921f5207b7SJohn Levon insn->from = expr->r_bitpos;
11931f5207b7SJohn Levon insn->len = expr->r_nrbits;
11941f5207b7SJohn Levon use_pseudo(insn, pre, &insn->base);
11951f5207b7SJohn Levon add_one_insn(ep, insn);
11961f5207b7SJohn Levon return new;
11971f5207b7SJohn Levon }
11981f5207b7SJohn Levon
linearize_regular_preop(struct entrypoint * ep,struct expression * expr)11991f5207b7SJohn Levon static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
12001f5207b7SJohn Levon {
12011f5207b7SJohn Levon pseudo_t pre = linearize_expression(ep, expr->unop);
1202*c85f09ccSJohn Levon struct symbol *ctype = expr->ctype;
12031f5207b7SJohn Levon switch (expr->op) {
12041f5207b7SJohn Levon case '+':
12051f5207b7SJohn Levon return pre;
12061f5207b7SJohn Levon case '!': {
1207*c85f09ccSJohn Levon pseudo_t zero = value_pseudo(0);
1208*c85f09ccSJohn Levon return add_binary_op(ep, ctype, OP_SET_EQ, pre, zero);
12091f5207b7SJohn Levon }
12101f5207b7SJohn Levon case '~':
1211*c85f09ccSJohn Levon return add_unop(ep, ctype, OP_NOT, pre);
12121f5207b7SJohn Levon case '-':
1213*c85f09ccSJohn Levon return add_unop(ep, ctype, opcode_float(OP_NEG, ctype), pre);
12141f5207b7SJohn Levon }
12151f5207b7SJohn Levon return VOID;
12161f5207b7SJohn Levon }
12171f5207b7SJohn Levon
linearize_preop(struct entrypoint * ep,struct expression * expr)12181f5207b7SJohn Levon static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
12191f5207b7SJohn Levon {
12201f5207b7SJohn Levon /*
12211f5207b7SJohn Levon * '*' is an lvalue access, and is fundamentally different
12221f5207b7SJohn Levon * from an arithmetic operation. Maybe it should have an
12231f5207b7SJohn Levon * expression type of its own..
12241f5207b7SJohn Levon */
12251f5207b7SJohn Levon if (expr->op == '*')
12261f5207b7SJohn Levon return linearize_access(ep, expr);
12271f5207b7SJohn Levon if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
12281f5207b7SJohn Levon return linearize_inc_dec(ep, expr, 0);
12291f5207b7SJohn Levon return linearize_regular_preop(ep, expr);
12301f5207b7SJohn Levon }
12311f5207b7SJohn Levon
linearize_postop(struct entrypoint * ep,struct expression * expr)12321f5207b7SJohn Levon static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
12331f5207b7SJohn Levon {
12341f5207b7SJohn Levon return linearize_inc_dec(ep, expr, 1);
12351f5207b7SJohn Levon }
12361f5207b7SJohn Levon
12371f5207b7SJohn Levon /*
12381f5207b7SJohn Levon * Casts to pointers are "less safe" than other casts, since
12391f5207b7SJohn Levon * they imply type-unsafe accesses. "void *" is a special
12401f5207b7SJohn Levon * case, since you can't access through it anyway without another
12411f5207b7SJohn Levon * cast.
12421f5207b7SJohn Levon */
1243*c85f09ccSJohn Levon enum mtype {
1244*c85f09ccSJohn Levon MTYPE_UINT,
1245*c85f09ccSJohn Levon MTYPE_SINT,
1246*c85f09ccSJohn Levon MTYPE_PTR,
1247*c85f09ccSJohn Levon MTYPE_VPTR, // TODO: must be removed ?
1248*c85f09ccSJohn Levon MTYPE_FLOAT,
1249*c85f09ccSJohn Levon MTYPE_BAD,
1250*c85f09ccSJohn Levon };
1251*c85f09ccSJohn Levon
get_mtype(struct symbol * s)1252*c85f09ccSJohn Levon static enum mtype get_mtype(struct symbol *s)
1253*c85f09ccSJohn Levon {
1254*c85f09ccSJohn Levon int sign = (s->ctype.modifiers & MOD_SIGNED) ? 1 : 0;
1255*c85f09ccSJohn Levon
1256*c85f09ccSJohn Levon retry: switch (s->type) {
1257*c85f09ccSJohn Levon case SYM_NODE:
1258*c85f09ccSJohn Levon s = s->ctype.base_type;
1259*c85f09ccSJohn Levon goto retry;
1260*c85f09ccSJohn Levon case SYM_PTR:
1261*c85f09ccSJohn Levon if (s->ctype.base_type == &void_ctype)
1262*c85f09ccSJohn Levon return MTYPE_VPTR;
1263*c85f09ccSJohn Levon return MTYPE_PTR;
1264*c85f09ccSJohn Levon case SYM_BITFIELD:
1265*c85f09ccSJohn Levon case SYM_RESTRICT:
1266*c85f09ccSJohn Levon case SYM_FOULED:
1267*c85f09ccSJohn Levon case SYM_ENUM:
1268*c85f09ccSJohn Levon s = s->ctype.base_type;
1269*c85f09ccSJohn Levon /* fall-through */
1270*c85f09ccSJohn Levon case_int:
1271*c85f09ccSJohn Levon return sign ? MTYPE_SINT : MTYPE_UINT;
1272*c85f09ccSJohn Levon case SYM_BASETYPE:
1273*c85f09ccSJohn Levon if (s->ctype.base_type == &fp_type)
1274*c85f09ccSJohn Levon return MTYPE_FLOAT;
1275*c85f09ccSJohn Levon if (s->ctype.base_type == &int_type)
1276*c85f09ccSJohn Levon goto case_int;
1277*c85f09ccSJohn Levon /* fall-through */
1278*c85f09ccSJohn Levon default:
1279*c85f09ccSJohn Levon return MTYPE_BAD;
1280*c85f09ccSJohn Levon }
1281*c85f09ccSJohn Levon }
1282*c85f09ccSJohn Levon
get_cast_opcode(struct symbol * dst,struct symbol * src)1283*c85f09ccSJohn Levon static int get_cast_opcode(struct symbol *dst, struct symbol *src)
12841f5207b7SJohn Levon {
1285*c85f09ccSJohn Levon enum mtype stype = get_mtype(src);
1286*c85f09ccSJohn Levon enum mtype dtype = get_mtype(dst);
12871f5207b7SJohn Levon
1288*c85f09ccSJohn Levon switch (dtype) {
1289*c85f09ccSJohn Levon case MTYPE_FLOAT:
1290*c85f09ccSJohn Levon switch (stype) {
1291*c85f09ccSJohn Levon case MTYPE_FLOAT:
1292*c85f09ccSJohn Levon if (dst->bit_size == src->bit_size)
1293*c85f09ccSJohn Levon return OP_NOP;
1294*c85f09ccSJohn Levon return OP_FCVTF;
1295*c85f09ccSJohn Levon case MTYPE_UINT:
1296*c85f09ccSJohn Levon return OP_UCVTF;
1297*c85f09ccSJohn Levon case MTYPE_SINT:
1298*c85f09ccSJohn Levon return OP_SCVTF;
1299*c85f09ccSJohn Levon default:
1300*c85f09ccSJohn Levon return OP_BADOP;
1301*c85f09ccSJohn Levon }
1302*c85f09ccSJohn Levon case MTYPE_PTR:
1303*c85f09ccSJohn Levon switch (stype) {
1304*c85f09ccSJohn Levon case MTYPE_UINT:
1305*c85f09ccSJohn Levon case MTYPE_SINT:
1306*c85f09ccSJohn Levon return OP_UTPTR;
1307*c85f09ccSJohn Levon case MTYPE_PTR:
1308*c85f09ccSJohn Levon case MTYPE_VPTR:
1309*c85f09ccSJohn Levon return OP_PTRCAST;
1310*c85f09ccSJohn Levon default:
1311*c85f09ccSJohn Levon return OP_BADOP;
1312*c85f09ccSJohn Levon }
1313*c85f09ccSJohn Levon case MTYPE_VPTR:
1314*c85f09ccSJohn Levon switch (stype) {
1315*c85f09ccSJohn Levon case MTYPE_PTR:
1316*c85f09ccSJohn Levon case MTYPE_VPTR:
1317*c85f09ccSJohn Levon case MTYPE_UINT:
1318*c85f09ccSJohn Levon stype = MTYPE_UINT;
1319*c85f09ccSJohn Levon /* fall through */
1320*c85f09ccSJohn Levon case MTYPE_SINT:
1321*c85f09ccSJohn Levon break;
1322*c85f09ccSJohn Levon default:
1323*c85f09ccSJohn Levon return OP_BADOP;
1324*c85f09ccSJohn Levon }
1325*c85f09ccSJohn Levon /* fall through */
1326*c85f09ccSJohn Levon case MTYPE_UINT:
1327*c85f09ccSJohn Levon case MTYPE_SINT:
1328*c85f09ccSJohn Levon switch (stype) {
1329*c85f09ccSJohn Levon case MTYPE_FLOAT:
1330*c85f09ccSJohn Levon return dtype == MTYPE_UINT ? OP_FCVTU : OP_FCVTS;
1331*c85f09ccSJohn Levon case MTYPE_PTR:
1332*c85f09ccSJohn Levon return OP_PTRTU;
1333*c85f09ccSJohn Levon case MTYPE_VPTR:
1334*c85f09ccSJohn Levon case MTYPE_UINT:
1335*c85f09ccSJohn Levon case MTYPE_SINT:
1336*c85f09ccSJohn Levon if (dst->bit_size ==src->bit_size)
1337*c85f09ccSJohn Levon return OP_NOP;
1338*c85f09ccSJohn Levon if (dst->bit_size < src->bit_size)
1339*c85f09ccSJohn Levon return OP_TRUNC;
1340*c85f09ccSJohn Levon return stype == MTYPE_SINT ? OP_SEXT : OP_ZEXT;
1341*c85f09ccSJohn Levon default:
1342*c85f09ccSJohn Levon return OP_BADOP;
1343*c85f09ccSJohn Levon }
1344*c85f09ccSJohn Levon /* fall through */
1345*c85f09ccSJohn Levon default:
1346*c85f09ccSJohn Levon if (src->type == SYM_NODE)
1347*c85f09ccSJohn Levon src = src->ctype.base_type;
1348*c85f09ccSJohn Levon if (dst->type == SYM_NODE)
1349*c85f09ccSJohn Levon dst = dst->ctype.base_type;
1350*c85f09ccSJohn Levon if (src == dst)
1351*c85f09ccSJohn Levon return OP_NOP;
1352*c85f09ccSJohn Levon return OP_BADOP;
1353*c85f09ccSJohn Levon }
13541f5207b7SJohn Levon }
13551f5207b7SJohn Levon
cast_pseudo(struct entrypoint * ep,pseudo_t src,struct symbol * from,struct symbol * to)13561f5207b7SJohn Levon static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
13571f5207b7SJohn Levon {
1358*c85f09ccSJohn Levon const struct position pos = current_pos;
13591f5207b7SJohn Levon pseudo_t result;
13601f5207b7SJohn Levon struct instruction *insn;
1361*c85f09ccSJohn Levon int opcode;
13621f5207b7SJohn Levon
13631f5207b7SJohn Levon if (src == VOID)
13641f5207b7SJohn Levon return VOID;
13651f5207b7SJohn Levon if (!from || !to)
13661f5207b7SJohn Levon return VOID;
13671f5207b7SJohn Levon if (from->bit_size < 0 || to->bit_size < 0)
13681f5207b7SJohn Levon return VOID;
1369*c85f09ccSJohn Levon opcode = get_cast_opcode(to, from);
1370*c85f09ccSJohn Levon switch (opcode) {
1371*c85f09ccSJohn Levon case OP_NOP:
1372*c85f09ccSJohn Levon return src;
1373*c85f09ccSJohn Levon case OP_UTPTR:
1374*c85f09ccSJohn Levon if (from->bit_size == to->bit_size)
1375*c85f09ccSJohn Levon break;
1376*c85f09ccSJohn Levon if (src == value_pseudo(0))
1377*c85f09ccSJohn Levon break;
1378*c85f09ccSJohn Levon if (Wint_to_pointer_cast)
1379*c85f09ccSJohn Levon warning(pos, "non size-preserving integer to pointer cast");
1380*c85f09ccSJohn Levon src = cast_pseudo(ep, src, from, size_t_ctype);
1381*c85f09ccSJohn Levon from = size_t_ctype;
1382*c85f09ccSJohn Levon break;
1383*c85f09ccSJohn Levon case OP_PTRTU:
1384*c85f09ccSJohn Levon if (from->bit_size == to->bit_size)
1385*c85f09ccSJohn Levon break;
1386*c85f09ccSJohn Levon if (Wpointer_to_int_cast)
1387*c85f09ccSJohn Levon warning(pos, "non size-preserving pointer to integer cast");
1388*c85f09ccSJohn Levon src = cast_pseudo(ep, src, from, size_t_ctype);
1389*c85f09ccSJohn Levon return cast_pseudo(ep, src, size_t_ctype, to);
1390*c85f09ccSJohn Levon case OP_BADOP:
1391*c85f09ccSJohn Levon return VOID;
1392*c85f09ccSJohn Levon default:
1393*c85f09ccSJohn Levon break;
1394*c85f09ccSJohn Levon }
1395*c85f09ccSJohn Levon insn = alloc_typed_instruction(opcode, to);
13961f5207b7SJohn Levon result = alloc_pseudo(insn);
13971f5207b7SJohn Levon insn->target = result;
13981f5207b7SJohn Levon insn->orig_type = from;
13991f5207b7SJohn Levon use_pseudo(insn, src, &insn->src);
14001f5207b7SJohn Levon add_one_insn(ep, insn);
14011f5207b7SJohn Levon return result;
14021f5207b7SJohn Levon }
14031f5207b7SJohn Levon
map_opcode(int opcode,struct symbol * ctype)1404*c85f09ccSJohn Levon static int map_opcode(int opcode, struct symbol *ctype)
14051f5207b7SJohn Levon {
1406*c85f09ccSJohn Levon if (ctype && is_float_type(ctype))
1407*c85f09ccSJohn Levon return opcode_table[opcode].to_float;
14081f5207b7SJohn Levon if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
14091f5207b7SJohn Levon switch(opcode) {
1410*c85f09ccSJohn Levon case OP_DIVU: case OP_MODU: case OP_LSR:
14111f5207b7SJohn Levon opcode++;
14121f5207b7SJohn Levon }
14131f5207b7SJohn Levon }
14141f5207b7SJohn Levon return opcode;
14151f5207b7SJohn Levon }
14161f5207b7SJohn Levon
add_convert_to_bool(struct entrypoint * ep,pseudo_t src,struct symbol * type)14171f5207b7SJohn Levon static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
14181f5207b7SJohn Levon {
14191f5207b7SJohn Levon pseudo_t zero;
14201f5207b7SJohn Levon int op;
14211f5207b7SJohn Levon
1422*c85f09ccSJohn Levon if (!type || src == VOID)
1423*c85f09ccSJohn Levon return VOID;
14241f5207b7SJohn Levon if (is_bool_type(type))
14251f5207b7SJohn Levon return src;
1426*c85f09ccSJohn Levon if (src->type == PSEUDO_VAL && (src->value == 0 || src->value == 1))
1427*c85f09ccSJohn Levon return src;
1428*c85f09ccSJohn Levon if (is_float_type(type)) {
1429*c85f09ccSJohn Levon zero = add_setfval(ep, type, 0.0);
1430*c85f09ccSJohn Levon op = map_opcode(OP_SET_NE, type);
1431*c85f09ccSJohn Levon } else {
1432*c85f09ccSJohn Levon zero = value_pseudo(0);
1433*c85f09ccSJohn Levon op = OP_SET_NE;
1434*c85f09ccSJohn Levon }
14351f5207b7SJohn Levon return add_binary_op(ep, &bool_ctype, op, src, zero);
14361f5207b7SJohn Levon }
14371f5207b7SJohn Levon
linearize_expression_to_bool(struct entrypoint * ep,struct expression * expr)14381f5207b7SJohn Levon static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
14391f5207b7SJohn Levon {
14401f5207b7SJohn Levon pseudo_t dst;
14411f5207b7SJohn Levon dst = linearize_expression(ep, expr);
14421f5207b7SJohn Levon dst = add_convert_to_bool(ep, dst, expr->ctype);
14431f5207b7SJohn Levon return dst;
14441f5207b7SJohn Levon }
14451f5207b7SJohn Levon
linearize_assignment(struct entrypoint * ep,struct expression * expr)14461f5207b7SJohn Levon static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
14471f5207b7SJohn Levon {
14481f5207b7SJohn Levon struct access_data ad = { NULL, };
14491f5207b7SJohn Levon struct expression *target = expr->left;
14501f5207b7SJohn Levon struct expression *src = expr->right;
14511f5207b7SJohn Levon struct symbol *ctype;
14521f5207b7SJohn Levon pseudo_t value;
14531f5207b7SJohn Levon
14541f5207b7SJohn Levon value = linearize_expression(ep, src);
14551f5207b7SJohn Levon if (!target || !linearize_address_gen(ep, target, &ad))
14561f5207b7SJohn Levon return value;
14571f5207b7SJohn Levon if (expr->op != '=') {
14581f5207b7SJohn Levon pseudo_t oldvalue = linearize_load_gen(ep, &ad);
14591f5207b7SJohn Levon pseudo_t dst;
14601f5207b7SJohn Levon static const int op_trans[] = {
14611f5207b7SJohn Levon [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
14621f5207b7SJohn Levon [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
1463*c85f09ccSJohn Levon [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
14641f5207b7SJohn Levon [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
14651f5207b7SJohn Levon [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
14661f5207b7SJohn Levon [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
14671f5207b7SJohn Levon [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
14681f5207b7SJohn Levon [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
14691f5207b7SJohn Levon [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
14701f5207b7SJohn Levon [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
14711f5207b7SJohn Levon };
14721f5207b7SJohn Levon int opcode;
14731f5207b7SJohn Levon
14741f5207b7SJohn Levon if (!src)
14751f5207b7SJohn Levon return VOID;
14761f5207b7SJohn Levon
14771f5207b7SJohn Levon ctype = src->ctype;
14781f5207b7SJohn Levon oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
1479*c85f09ccSJohn Levon opcode = map_opcode(op_trans[expr->op - SPECIAL_BASE], ctype);
14801f5207b7SJohn Levon dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
1481*c85f09ccSJohn Levon taint_undefined_behaviour(dst->def);
14821f5207b7SJohn Levon value = cast_pseudo(ep, dst, ctype, expr->ctype);
14831f5207b7SJohn Levon }
14841f5207b7SJohn Levon value = linearize_store_gen(ep, value, &ad);
14851f5207b7SJohn Levon return value;
14861f5207b7SJohn Levon }
14871f5207b7SJohn Levon
linearize_call_expression(struct entrypoint * ep,struct expression * expr)14881f5207b7SJohn Levon static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
14891f5207b7SJohn Levon {
14901f5207b7SJohn Levon struct expression *arg, *fn;
14911f5207b7SJohn Levon struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
14921f5207b7SJohn Levon pseudo_t retval, call;
14931f5207b7SJohn Levon struct ctype *ctype = NULL;
14941f5207b7SJohn Levon struct symbol *fntype;
14951f5207b7SJohn Levon struct context *context;
14961f5207b7SJohn Levon
1497*c85f09ccSJohn Levon if (!expr->ctype)
14981f5207b7SJohn Levon return VOID;
14991f5207b7SJohn Levon
1500*c85f09ccSJohn Levon fn = expr->fn;
1501*c85f09ccSJohn Levon fntype = fn->ctype;
1502*c85f09ccSJohn Levon ctype = &fntype->ctype;
1503*c85f09ccSJohn Levon if (fntype->type == SYM_NODE)
1504*c85f09ccSJohn Levon fntype = fntype->ctype.base_type;
1505*c85f09ccSJohn Levon
1506*c85f09ccSJohn Levon add_symbol(&insn->fntypes, fntype);
15071f5207b7SJohn Levon FOR_EACH_PTR(expr->args, arg) {
15081f5207b7SJohn Levon pseudo_t new = linearize_expression(ep, arg);
15091f5207b7SJohn Levon use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
1510*c85f09ccSJohn Levon add_symbol(&insn->fntypes, arg->ctype);
15111f5207b7SJohn Levon } END_FOR_EACH_PTR(arg);
15121f5207b7SJohn Levon
1513*c85f09ccSJohn Levon if (fn->type == EXPR_PREOP && fn->op == '*' && is_func_type(fn->ctype))
1514*c85f09ccSJohn Levon fn = fn->unop;
15151f5207b7SJohn Levon
15161f5207b7SJohn Levon if (fn->type == EXPR_SYMBOL) {
15171f5207b7SJohn Levon call = symbol_pseudo(ep, fn->symbol);
15181f5207b7SJohn Levon } else {
15191f5207b7SJohn Levon call = linearize_expression(ep, fn);
15201f5207b7SJohn Levon }
15211f5207b7SJohn Levon use_pseudo(insn, call, &insn->func);
15221f5207b7SJohn Levon retval = VOID;
15231f5207b7SJohn Levon if (expr->ctype != &void_ctype)
15241f5207b7SJohn Levon retval = alloc_pseudo(insn);
15251f5207b7SJohn Levon insn->target = retval;
15261f5207b7SJohn Levon add_one_insn(ep, insn);
15271f5207b7SJohn Levon
15281f5207b7SJohn Levon if (ctype) {
15291f5207b7SJohn Levon FOR_EACH_PTR(ctype->contexts, context) {
15301f5207b7SJohn Levon int in = context->in;
15311f5207b7SJohn Levon int out = context->out;
15321f5207b7SJohn Levon int check = 0;
15331f5207b7SJohn Levon int context_diff;
15341f5207b7SJohn Levon if (in < 0) {
15351f5207b7SJohn Levon check = 1;
15361f5207b7SJohn Levon in = 0;
15371f5207b7SJohn Levon }
15381f5207b7SJohn Levon if (out < 0) {
15391f5207b7SJohn Levon check = 0;
15401f5207b7SJohn Levon out = 0;
15411f5207b7SJohn Levon }
15421f5207b7SJohn Levon context_diff = out - in;
15431f5207b7SJohn Levon if (check || context_diff) {
15441f5207b7SJohn Levon insn = alloc_instruction(OP_CONTEXT, 0);
15451f5207b7SJohn Levon insn->increment = context_diff;
15461f5207b7SJohn Levon insn->check = check;
15471f5207b7SJohn Levon insn->context_expr = context->context;
15481f5207b7SJohn Levon add_one_insn(ep, insn);
15491f5207b7SJohn Levon }
15501f5207b7SJohn Levon } END_FOR_EACH_PTR(context);
15511f5207b7SJohn Levon }
15521f5207b7SJohn Levon
15531f5207b7SJohn Levon return retval;
15541f5207b7SJohn Levon }
15551f5207b7SJohn Levon
linearize_binop_bool(struct entrypoint * ep,struct expression * expr)15561f5207b7SJohn Levon static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
15571f5207b7SJohn Levon {
15581f5207b7SJohn Levon pseudo_t src1, src2, dst;
1559*c85f09ccSJohn Levon int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR : OP_AND;
15601f5207b7SJohn Levon
15611f5207b7SJohn Levon src1 = linearize_expression_to_bool(ep, expr->left);
15621f5207b7SJohn Levon src2 = linearize_expression_to_bool(ep, expr->right);
15631f5207b7SJohn Levon dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
15641f5207b7SJohn Levon if (expr->ctype != &bool_ctype)
15651f5207b7SJohn Levon dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype);
15661f5207b7SJohn Levon return dst;
15671f5207b7SJohn Levon }
15681f5207b7SJohn Levon
linearize_binop(struct entrypoint * ep,struct expression * expr)15691f5207b7SJohn Levon static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
15701f5207b7SJohn Levon {
15711f5207b7SJohn Levon pseudo_t src1, src2, dst;
15721f5207b7SJohn Levon static const int opcode[] = {
15731f5207b7SJohn Levon ['+'] = OP_ADD, ['-'] = OP_SUB,
1574*c85f09ccSJohn Levon ['*'] = OP_MUL, ['/'] = OP_DIVU,
15751f5207b7SJohn Levon ['%'] = OP_MODU, ['&'] = OP_AND,
15761f5207b7SJohn Levon ['|'] = OP_OR, ['^'] = OP_XOR,
15771f5207b7SJohn Levon [SPECIAL_LEFTSHIFT] = OP_SHL,
15781f5207b7SJohn Levon [SPECIAL_RIGHTSHIFT] = OP_LSR,
15791f5207b7SJohn Levon };
15801f5207b7SJohn Levon int op;
15811f5207b7SJohn Levon
15821f5207b7SJohn Levon src1 = linearize_expression(ep, expr->left);
15831f5207b7SJohn Levon src2 = linearize_expression(ep, expr->right);
1584*c85f09ccSJohn Levon op = map_opcode(opcode[expr->op], expr->ctype);
15851f5207b7SJohn Levon dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1586*c85f09ccSJohn Levon taint_undefined_behaviour(dst->def);
15871f5207b7SJohn Levon return dst;
15881f5207b7SJohn Levon }
15891f5207b7SJohn Levon
15901f5207b7SJohn Levon static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
15911f5207b7SJohn Levon
1592*c85f09ccSJohn Levon static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
15931f5207b7SJohn Levon
linearize_select(struct entrypoint * ep,struct expression * expr)15941f5207b7SJohn Levon static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
15951f5207b7SJohn Levon {
1596*c85f09ccSJohn Levon pseudo_t cond, valt, valf, res;
15971f5207b7SJohn Levon struct instruction *insn;
15981f5207b7SJohn Levon
1599*c85f09ccSJohn Levon valt = linearize_expression(ep, expr->cond_true);
1600*c85f09ccSJohn Levon valf = linearize_expression(ep, expr->cond_false);
16011f5207b7SJohn Levon cond = linearize_expression(ep, expr->conditional);
16021f5207b7SJohn Levon
16031f5207b7SJohn Levon insn = alloc_typed_instruction(OP_SEL, expr->ctype);
16041f5207b7SJohn Levon if (!expr->cond_true)
1605*c85f09ccSJohn Levon valt = cond;
16061f5207b7SJohn Levon use_pseudo(insn, cond, &insn->src1);
1607*c85f09ccSJohn Levon use_pseudo(insn, valt, &insn->src2);
1608*c85f09ccSJohn Levon use_pseudo(insn, valf, &insn->src3);
16091f5207b7SJohn Levon
16101f5207b7SJohn Levon res = alloc_pseudo(insn);
16111f5207b7SJohn Levon insn->target = res;
16121f5207b7SJohn Levon add_one_insn(ep, insn);
16131f5207b7SJohn Levon return res;
16141f5207b7SJohn Levon }
16151f5207b7SJohn Levon
add_join_conditional(struct entrypoint * ep,struct expression * expr,pseudo_t phi1,pseudo_t phi2)16161f5207b7SJohn Levon static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
16171f5207b7SJohn Levon pseudo_t phi1, pseudo_t phi2)
16181f5207b7SJohn Levon {
16191f5207b7SJohn Levon pseudo_t target;
16201f5207b7SJohn Levon struct instruction *phi_node;
16211f5207b7SJohn Levon
16221f5207b7SJohn Levon if (phi1 == VOID)
16231f5207b7SJohn Levon return phi2;
16241f5207b7SJohn Levon if (phi2 == VOID)
16251f5207b7SJohn Levon return phi1;
16261f5207b7SJohn Levon
16271f5207b7SJohn Levon phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
16281f5207b7SJohn Levon use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1));
16291f5207b7SJohn Levon use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2));
16301f5207b7SJohn Levon phi_node->target = target = alloc_pseudo(phi_node);
16311f5207b7SJohn Levon add_one_insn(ep, phi_node);
16321f5207b7SJohn Levon return target;
16331f5207b7SJohn Levon }
16341f5207b7SJohn Levon
linearize_short_conditional(struct entrypoint * ep,struct expression * expr,struct expression * cond,struct expression * expr_false)16351f5207b7SJohn Levon static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
16361f5207b7SJohn Levon struct expression *cond,
16371f5207b7SJohn Levon struct expression *expr_false)
16381f5207b7SJohn Levon {
16391f5207b7SJohn Levon pseudo_t src1, src2;
16401f5207b7SJohn Levon struct basic_block *bb_false;
1641*c85f09ccSJohn Levon struct basic_block *merge;
16421f5207b7SJohn Levon pseudo_t phi1, phi2;
16431f5207b7SJohn Levon
16441f5207b7SJohn Levon if (!expr_false || !ep->active)
16451f5207b7SJohn Levon return VOID;
16461f5207b7SJohn Levon
16471f5207b7SJohn Levon bb_false = alloc_basic_block(ep, expr_false->pos);
1648*c85f09ccSJohn Levon merge = alloc_basic_block(ep, expr->pos);
1649*c85f09ccSJohn Levon
16501f5207b7SJohn Levon src1 = linearize_expression(ep, cond);
1651*c85f09ccSJohn Levon phi1 = alloc_phi(ep->active, src1, expr->ctype);
1652*c85f09ccSJohn Levon add_branch(ep, src1, merge, bb_false);
16531f5207b7SJohn Levon
16541f5207b7SJohn Levon set_activeblock(ep, bb_false);
16551f5207b7SJohn Levon src2 = linearize_expression(ep, expr_false);
1656*c85f09ccSJohn Levon phi2 = alloc_phi(ep->active, src2, expr->ctype);
16571f5207b7SJohn Levon set_activeblock(ep, merge);
16581f5207b7SJohn Levon
16591f5207b7SJohn Levon return add_join_conditional(ep, expr, phi1, phi2);
16601f5207b7SJohn Levon }
16611f5207b7SJohn Levon
linearize_conditional(struct entrypoint * ep,struct expression * expr,struct expression * cond,struct expression * expr_true,struct expression * expr_false)16621f5207b7SJohn Levon static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
16631f5207b7SJohn Levon struct expression *cond,
16641f5207b7SJohn Levon struct expression *expr_true,
16651f5207b7SJohn Levon struct expression *expr_false)
16661f5207b7SJohn Levon {
16671f5207b7SJohn Levon pseudo_t src1, src2;
16681f5207b7SJohn Levon pseudo_t phi1, phi2;
16691f5207b7SJohn Levon struct basic_block *bb_true, *bb_false, *merge;
16701f5207b7SJohn Levon
16711f5207b7SJohn Levon if (!cond || !expr_true || !expr_false || !ep->active)
16721f5207b7SJohn Levon return VOID;
16731f5207b7SJohn Levon bb_true = alloc_basic_block(ep, expr_true->pos);
16741f5207b7SJohn Levon bb_false = alloc_basic_block(ep, expr_false->pos);
16751f5207b7SJohn Levon merge = alloc_basic_block(ep, expr->pos);
16761f5207b7SJohn Levon
16771f5207b7SJohn Levon linearize_cond_branch(ep, cond, bb_true, bb_false);
16781f5207b7SJohn Levon
16791f5207b7SJohn Levon set_activeblock(ep, bb_true);
16801f5207b7SJohn Levon src1 = linearize_expression(ep, expr_true);
1681*c85f09ccSJohn Levon phi1 = alloc_phi(ep->active, src1, expr->ctype);
16821f5207b7SJohn Levon add_goto(ep, merge);
16831f5207b7SJohn Levon
16841f5207b7SJohn Levon set_activeblock(ep, bb_false);
16851f5207b7SJohn Levon src2 = linearize_expression(ep, expr_false);
1686*c85f09ccSJohn Levon phi2 = alloc_phi(ep->active, src2, expr->ctype);
16871f5207b7SJohn Levon set_activeblock(ep, merge);
16881f5207b7SJohn Levon
16891f5207b7SJohn Levon return add_join_conditional(ep, expr, phi1, phi2);
16901f5207b7SJohn Levon }
16911f5207b7SJohn Levon
insert_phis(struct basic_block * bb,pseudo_t src,struct symbol * ctype,struct instruction * node)1692*c85f09ccSJohn Levon static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *ctype,
1693*c85f09ccSJohn Levon struct instruction *node)
1694*c85f09ccSJohn Levon {
1695*c85f09ccSJohn Levon struct basic_block *parent;
1696*c85f09ccSJohn Levon
1697*c85f09ccSJohn Levon FOR_EACH_PTR(bb->parents, parent) {
1698*c85f09ccSJohn Levon struct instruction *br = delete_last_instruction(&parent->insns);
1699*c85f09ccSJohn Levon pseudo_t phi = alloc_phi(parent, src, ctype);
1700*c85f09ccSJohn Levon add_instruction(&parent->insns, br);
1701*c85f09ccSJohn Levon use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
1702*c85f09ccSJohn Levon } END_FOR_EACH_PTR(parent);
1703*c85f09ccSJohn Levon }
1704*c85f09ccSJohn Levon
linearize_logical(struct entrypoint * ep,struct expression * expr)17051f5207b7SJohn Levon static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
17061f5207b7SJohn Levon {
1707*c85f09ccSJohn Levon struct symbol *ctype = expr->ctype;
1708*c85f09ccSJohn Levon struct basic_block *other, *merge;
1709*c85f09ccSJohn Levon struct instruction *node;
1710*c85f09ccSJohn Levon pseudo_t src1, src2, phi2;
17111f5207b7SJohn Levon
1712*c85f09ccSJohn Levon if (!ep->active || !expr->left || !expr->right)
1713*c85f09ccSJohn Levon return VOID;
1714*c85f09ccSJohn Levon
1715*c85f09ccSJohn Levon other = alloc_basic_block(ep, expr->right->pos);
1716*c85f09ccSJohn Levon merge = alloc_basic_block(ep, expr->pos);
1717*c85f09ccSJohn Levon node = alloc_phi_node(merge, ctype, NULL);
1718*c85f09ccSJohn Levon
1719*c85f09ccSJohn Levon // LHS and its shortcut
1720*c85f09ccSJohn Levon if (expr->op == SPECIAL_LOGICAL_OR) {
1721*c85f09ccSJohn Levon linearize_cond_branch(ep, expr->left, merge, other);
1722*c85f09ccSJohn Levon src1 = value_pseudo(1);
1723*c85f09ccSJohn Levon } else {
1724*c85f09ccSJohn Levon linearize_cond_branch(ep, expr->left, other, merge);
1725*c85f09ccSJohn Levon src1 = value_pseudo(0);
1726*c85f09ccSJohn Levon }
1727*c85f09ccSJohn Levon insert_phis(merge, src1, ctype, node);
1728*c85f09ccSJohn Levon
1729*c85f09ccSJohn Levon // RHS
1730*c85f09ccSJohn Levon set_activeblock(ep, other);
1731*c85f09ccSJohn Levon src2 = linearize_expression_to_bool(ep, expr->right);
1732*c85f09ccSJohn Levon src2 = cast_pseudo(ep, src2, &bool_ctype, ctype);
1733*c85f09ccSJohn Levon phi2 = alloc_phi(ep->active, src2, ctype);
1734*c85f09ccSJohn Levon use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2));
1735*c85f09ccSJohn Levon
1736*c85f09ccSJohn Levon // join
1737*c85f09ccSJohn Levon set_activeblock(ep, merge);
1738*c85f09ccSJohn Levon add_instruction(&merge->insns, node);
1739*c85f09ccSJohn Levon return node->target;
17401f5207b7SJohn Levon }
17411f5207b7SJohn Levon
linearize_compare(struct entrypoint * ep,struct expression * expr)17421f5207b7SJohn Levon static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
17431f5207b7SJohn Levon {
17441f5207b7SJohn Levon static const int cmpop[] = {
17451f5207b7SJohn Levon ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
17461f5207b7SJohn Levon [SPECIAL_EQUAL] = OP_SET_EQ,
17471f5207b7SJohn Levon [SPECIAL_NOTEQUAL] = OP_SET_NE,
17481f5207b7SJohn Levon [SPECIAL_GTE] = OP_SET_GE,
17491f5207b7SJohn Levon [SPECIAL_LTE] = OP_SET_LE,
17501f5207b7SJohn Levon [SPECIAL_UNSIGNED_LT] = OP_SET_B,
17511f5207b7SJohn Levon [SPECIAL_UNSIGNED_GT] = OP_SET_A,
17521f5207b7SJohn Levon [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
17531f5207b7SJohn Levon [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
17541f5207b7SJohn Levon };
1755*c85f09ccSJohn Levon int op = opcode_float(cmpop[expr->op], expr->right->ctype);
17561f5207b7SJohn Levon pseudo_t src1 = linearize_expression(ep, expr->left);
17571f5207b7SJohn Levon pseudo_t src2 = linearize_expression(ep, expr->right);
1758*c85f09ccSJohn Levon pseudo_t dst = add_binary_op(ep, expr->ctype, op, src1, src2);
17591f5207b7SJohn Levon return dst;
17601f5207b7SJohn Levon }
17611f5207b7SJohn Levon
17621f5207b7SJohn Levon
linearize_cond_branch(struct entrypoint * ep,struct expression * expr,struct basic_block * bb_true,struct basic_block * bb_false)1763*c85f09ccSJohn Levon static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
17641f5207b7SJohn Levon {
17651f5207b7SJohn Levon pseudo_t cond;
17661f5207b7SJohn Levon
17671f5207b7SJohn Levon if (!expr || !bb_reachable(ep->active))
17681f5207b7SJohn Levon return VOID;
17691f5207b7SJohn Levon
17701f5207b7SJohn Levon switch (expr->type) {
17711f5207b7SJohn Levon
17721f5207b7SJohn Levon case EXPR_STRING:
17731f5207b7SJohn Levon case EXPR_VALUE:
17741f5207b7SJohn Levon add_goto(ep, expr->value ? bb_true : bb_false);
17751f5207b7SJohn Levon return VOID;
17761f5207b7SJohn Levon
17771f5207b7SJohn Levon case EXPR_FVALUE:
17781f5207b7SJohn Levon add_goto(ep, expr->fvalue ? bb_true : bb_false);
17791f5207b7SJohn Levon return VOID;
17801f5207b7SJohn Levon
17811f5207b7SJohn Levon case EXPR_LOGICAL:
17821f5207b7SJohn Levon linearize_logical_branch(ep, expr, bb_true, bb_false);
17831f5207b7SJohn Levon return VOID;
17841f5207b7SJohn Levon
17851f5207b7SJohn Levon case EXPR_COMPARE:
17861f5207b7SJohn Levon cond = linearize_compare(ep, expr);
1787*c85f09ccSJohn Levon add_branch(ep, cond, bb_true, bb_false);
17881f5207b7SJohn Levon break;
17891f5207b7SJohn Levon
17901f5207b7SJohn Levon case EXPR_PREOP:
17911f5207b7SJohn Levon if (expr->op == '!')
17921f5207b7SJohn Levon return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
17931f5207b7SJohn Levon /* fall through */
17941f5207b7SJohn Levon default: {
1795*c85f09ccSJohn Levon cond = linearize_expression_to_bool(ep, expr);
1796*c85f09ccSJohn Levon add_branch(ep, cond, bb_true, bb_false);
17971f5207b7SJohn Levon
17981f5207b7SJohn Levon return VOID;
17991f5207b7SJohn Levon }
18001f5207b7SJohn Levon }
18011f5207b7SJohn Levon return VOID;
18021f5207b7SJohn Levon }
18031f5207b7SJohn Levon
18041f5207b7SJohn Levon
18051f5207b7SJohn Levon
linearize_logical_branch(struct entrypoint * ep,struct expression * expr,struct basic_block * bb_true,struct basic_block * bb_false)18061f5207b7SJohn Levon static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
18071f5207b7SJohn Levon {
18081f5207b7SJohn Levon struct basic_block *next = alloc_basic_block(ep, expr->pos);
18091f5207b7SJohn Levon
18101f5207b7SJohn Levon if (expr->op == SPECIAL_LOGICAL_OR)
18111f5207b7SJohn Levon linearize_cond_branch(ep, expr->left, bb_true, next);
18121f5207b7SJohn Levon else
18131f5207b7SJohn Levon linearize_cond_branch(ep, expr->left, next, bb_false);
18141f5207b7SJohn Levon set_activeblock(ep, next);
18151f5207b7SJohn Levon linearize_cond_branch(ep, expr->right, bb_true, bb_false);
18161f5207b7SJohn Levon return VOID;
18171f5207b7SJohn Levon }
18181f5207b7SJohn Levon
linearize_cast(struct entrypoint * ep,struct expression * expr)18191f5207b7SJohn Levon static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
18201f5207b7SJohn Levon {
18211f5207b7SJohn Levon pseudo_t src;
18221f5207b7SJohn Levon struct expression *orig = expr->cast_expression;
18231f5207b7SJohn Levon
18241f5207b7SJohn Levon if (!orig)
18251f5207b7SJohn Levon return VOID;
18261f5207b7SJohn Levon
18271f5207b7SJohn Levon src = linearize_expression(ep, orig);
18281f5207b7SJohn Levon return cast_pseudo(ep, src, orig->ctype, expr->ctype);
18291f5207b7SJohn Levon }
18301f5207b7SJohn Levon
linearize_initializer(struct entrypoint * ep,struct expression * initializer,struct access_data * ad)18311f5207b7SJohn Levon static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
18321f5207b7SJohn Levon {
18331f5207b7SJohn Levon switch (initializer->type) {
18341f5207b7SJohn Levon case EXPR_INITIALIZER: {
18351f5207b7SJohn Levon struct expression *expr;
18361f5207b7SJohn Levon FOR_EACH_PTR(initializer->expr_list, expr) {
18371f5207b7SJohn Levon linearize_initializer(ep, expr, ad);
18381f5207b7SJohn Levon } END_FOR_EACH_PTR(expr);
18391f5207b7SJohn Levon break;
18401f5207b7SJohn Levon }
18411f5207b7SJohn Levon case EXPR_POS:
1842*c85f09ccSJohn Levon ad->offset = initializer->init_offset;
1843*c85f09ccSJohn Levon linearize_initializer(ep, initializer->init_expr, ad);
18441f5207b7SJohn Levon break;
18451f5207b7SJohn Levon default: {
18461f5207b7SJohn Levon pseudo_t value = linearize_expression(ep, initializer);
1847*c85f09ccSJohn Levon ad->type = initializer->ctype;
18481f5207b7SJohn Levon linearize_store_gen(ep, value, ad);
18491f5207b7SJohn Levon return value;
18501f5207b7SJohn Levon }
18511f5207b7SJohn Levon }
18521f5207b7SJohn Levon
18531f5207b7SJohn Levon return VOID;
18541f5207b7SJohn Levon }
18551f5207b7SJohn Levon
linearize_argument(struct entrypoint * ep,struct symbol * arg,int nr)18561f5207b7SJohn Levon static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
18571f5207b7SJohn Levon {
18581f5207b7SJohn Levon struct access_data ad = { NULL, };
18591f5207b7SJohn Levon
1860*c85f09ccSJohn Levon ad.type = arg;
18611f5207b7SJohn Levon ad.address = symbol_pseudo(ep, arg);
18621f5207b7SJohn Levon linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
18631f5207b7SJohn Levon }
18641f5207b7SJohn Levon
linearize_expression(struct entrypoint * ep,struct expression * expr)1865*c85f09ccSJohn Levon static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
18661f5207b7SJohn Levon {
18671f5207b7SJohn Levon if (!expr)
18681f5207b7SJohn Levon return VOID;
18691f5207b7SJohn Levon
18701f5207b7SJohn Levon current_pos = expr->pos;
18711f5207b7SJohn Levon switch (expr->type) {
18721f5207b7SJohn Levon case EXPR_SYMBOL:
18731f5207b7SJohn Levon linearize_one_symbol(ep, expr->symbol);
18741f5207b7SJohn Levon return add_symbol_address(ep, expr->symbol);
18751f5207b7SJohn Levon
18761f5207b7SJohn Levon case EXPR_VALUE:
1877*c85f09ccSJohn Levon return value_pseudo(expr->value);
18781f5207b7SJohn Levon
1879*c85f09ccSJohn Levon case EXPR_STRING:
1880*c85f09ccSJohn Levon case EXPR_LABEL:
18811f5207b7SJohn Levon return add_setval(ep, expr->ctype, expr);
18821f5207b7SJohn Levon
1883*c85f09ccSJohn Levon case EXPR_FVALUE:
1884*c85f09ccSJohn Levon return add_setfval(ep, expr->ctype, expr->fvalue);
1885*c85f09ccSJohn Levon
18861f5207b7SJohn Levon case EXPR_STATEMENT:
18871f5207b7SJohn Levon return linearize_statement(ep, expr->statement);
18881f5207b7SJohn Levon
18891f5207b7SJohn Levon case EXPR_CALL:
18901f5207b7SJohn Levon return linearize_call_expression(ep, expr);
18911f5207b7SJohn Levon
18921f5207b7SJohn Levon case EXPR_BINOP:
18931f5207b7SJohn Levon if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR)
18941f5207b7SJohn Levon return linearize_binop_bool(ep, expr);
18951f5207b7SJohn Levon return linearize_binop(ep, expr);
18961f5207b7SJohn Levon
18971f5207b7SJohn Levon case EXPR_LOGICAL:
18981f5207b7SJohn Levon return linearize_logical(ep, expr);
18991f5207b7SJohn Levon
19001f5207b7SJohn Levon case EXPR_COMPARE:
19011f5207b7SJohn Levon return linearize_compare(ep, expr);
19021f5207b7SJohn Levon
19031f5207b7SJohn Levon case EXPR_SELECT:
19041f5207b7SJohn Levon return linearize_select(ep, expr);
19051f5207b7SJohn Levon
19061f5207b7SJohn Levon case EXPR_CONDITIONAL:
19071f5207b7SJohn Levon if (!expr->cond_true)
19081f5207b7SJohn Levon return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
19091f5207b7SJohn Levon
19101f5207b7SJohn Levon return linearize_conditional(ep, expr, expr->conditional,
19111f5207b7SJohn Levon expr->cond_true, expr->cond_false);
19121f5207b7SJohn Levon
19131f5207b7SJohn Levon case EXPR_COMMA:
19141f5207b7SJohn Levon linearize_expression(ep, expr->left);
19151f5207b7SJohn Levon return linearize_expression(ep, expr->right);
19161f5207b7SJohn Levon
19171f5207b7SJohn Levon case EXPR_ASSIGNMENT:
19181f5207b7SJohn Levon return linearize_assignment(ep, expr);
19191f5207b7SJohn Levon
19201f5207b7SJohn Levon case EXPR_PREOP:
19211f5207b7SJohn Levon return linearize_preop(ep, expr);
19221f5207b7SJohn Levon
19231f5207b7SJohn Levon case EXPR_POSTOP:
19241f5207b7SJohn Levon return linearize_postop(ep, expr);
19251f5207b7SJohn Levon
19261f5207b7SJohn Levon case EXPR_CAST:
19271f5207b7SJohn Levon case EXPR_FORCE_CAST:
19281f5207b7SJohn Levon case EXPR_IMPLIED_CAST:
19291f5207b7SJohn Levon return linearize_cast(ep, expr);
19301f5207b7SJohn Levon
19311f5207b7SJohn Levon case EXPR_SLICE:
19321f5207b7SJohn Levon return linearize_slice(ep, expr);
19331f5207b7SJohn Levon
19341f5207b7SJohn Levon case EXPR_INITIALIZER:
19351f5207b7SJohn Levon case EXPR_POS:
19361f5207b7SJohn Levon warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
19371f5207b7SJohn Levon return VOID;
19381f5207b7SJohn Levon default:
19391f5207b7SJohn Levon warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
19401f5207b7SJohn Levon return VOID;
19411f5207b7SJohn Levon }
19421f5207b7SJohn Levon return VOID;
19431f5207b7SJohn Levon }
19441f5207b7SJohn Levon
linearize_one_symbol(struct entrypoint * ep,struct symbol * sym)19451f5207b7SJohn Levon static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
19461f5207b7SJohn Levon {
19471f5207b7SJohn Levon struct access_data ad = { NULL, };
19481f5207b7SJohn Levon pseudo_t value;
19491f5207b7SJohn Levon
19501f5207b7SJohn Levon if (!sym || !sym->initializer || sym->initialized)
19511f5207b7SJohn Levon return VOID;
19521f5207b7SJohn Levon
19531f5207b7SJohn Levon /* We need to output these puppies some day too.. */
19541f5207b7SJohn Levon if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
19551f5207b7SJohn Levon return VOID;
19561f5207b7SJohn Levon
19571f5207b7SJohn Levon sym->initialized = 1;
19581f5207b7SJohn Levon ad.address = symbol_pseudo(ep, sym);
19591f5207b7SJohn Levon
19601f5207b7SJohn Levon if (sym->initializer && !is_scalar_type(sym)) {
19611f5207b7SJohn Levon // default zero initialization [6.7.9.21]
19621f5207b7SJohn Levon // FIXME: this init the whole aggregate while
19631f5207b7SJohn Levon // only the existing fields need to be initialized.
19641f5207b7SJohn Levon // FIXME: this init the whole aggregate even if
19651f5207b7SJohn Levon // all fields arelater explicitely initialized.
1966*c85f09ccSJohn Levon ad.type = sym;
19671f5207b7SJohn Levon ad.address = symbol_pseudo(ep, sym);
1968*c85f09ccSJohn Levon linearize_store_gen(ep, value_pseudo(0), &ad);
19691f5207b7SJohn Levon }
19701f5207b7SJohn Levon
19711f5207b7SJohn Levon value = linearize_initializer(ep, sym->initializer, &ad);
19721f5207b7SJohn Levon return value;
19731f5207b7SJohn Levon }
19741f5207b7SJohn Levon
linearize_compound_statement(struct entrypoint * ep,struct statement * stmt)19751f5207b7SJohn Levon static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
19761f5207b7SJohn Levon {
19771f5207b7SJohn Levon pseudo_t pseudo;
19781f5207b7SJohn Levon struct statement *s;
19791f5207b7SJohn Levon
19801f5207b7SJohn Levon pseudo = VOID;
19811f5207b7SJohn Levon FOR_EACH_PTR(stmt->stmts, s) {
19821f5207b7SJohn Levon pseudo = linearize_statement(ep, s);
19831f5207b7SJohn Levon } END_FOR_EACH_PTR(s);
19841f5207b7SJohn Levon
1985*c85f09ccSJohn Levon return pseudo;
1986*c85f09ccSJohn Levon }
19871f5207b7SJohn Levon
add_return(struct entrypoint * ep,struct basic_block * bb,struct symbol * ctype,pseudo_t src)1988*c85f09ccSJohn Levon static void add_return(struct entrypoint *ep, struct basic_block *bb, struct symbol *ctype, pseudo_t src)
1989*c85f09ccSJohn Levon {
1990*c85f09ccSJohn Levon struct instruction *phi_node = first_instruction(bb->insns);
1991*c85f09ccSJohn Levon pseudo_t phi;
1992*c85f09ccSJohn Levon if (!phi_node) {
1993*c85f09ccSJohn Levon phi_node = alloc_typed_instruction(OP_PHI, ctype);
1994*c85f09ccSJohn Levon phi_node->target = alloc_pseudo(phi_node);
1995*c85f09ccSJohn Levon phi_node->bb = bb;
1996*c85f09ccSJohn Levon add_instruction(&bb->insns, phi_node);
1997*c85f09ccSJohn Levon }
1998*c85f09ccSJohn Levon phi = alloc_phi(ep->active, src, ctype);
1999*c85f09ccSJohn Levon phi->ident = &return_ident;
2000*c85f09ccSJohn Levon use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
2001*c85f09ccSJohn Levon }
2002*c85f09ccSJohn Levon
linearize_fn_statement(struct entrypoint * ep,struct statement * stmt)2003*c85f09ccSJohn Levon static pseudo_t linearize_fn_statement(struct entrypoint *ep, struct statement *stmt)
2004*c85f09ccSJohn Levon {
2005*c85f09ccSJohn Levon struct instruction *phi_node;
2006*c85f09ccSJohn Levon struct basic_block *bb;
2007*c85f09ccSJohn Levon pseudo_t pseudo;
20081f5207b7SJohn Levon
2009*c85f09ccSJohn Levon pseudo = linearize_compound_statement(ep, stmt);
2010*c85f09ccSJohn Levon if (!is_void_type(stmt->ret)) { // non-void function
2011*c85f09ccSJohn Levon struct basic_block *active = ep->active;
2012*c85f09ccSJohn Levon if (active && !bb_terminated(active)) { // missing return
2013*c85f09ccSJohn Levon struct basic_block *bb_ret;
2014*c85f09ccSJohn Levon bb_ret = get_bound_block(ep, stmt->ret);
2015*c85f09ccSJohn Levon add_return(ep, bb_ret, stmt->ret, undef_pseudo());
20161f5207b7SJohn Levon }
20171f5207b7SJohn Levon }
2018*c85f09ccSJohn Levon bb = add_label(ep, stmt->ret);
2019*c85f09ccSJohn Levon phi_node = first_instruction(bb->insns);
2020*c85f09ccSJohn Levon if (phi_node)
2021*c85f09ccSJohn Levon pseudo = phi_node->target;
20221f5207b7SJohn Levon return pseudo;
20231f5207b7SJohn Levon }
20241f5207b7SJohn Levon
linearize_inlined_call(struct entrypoint * ep,struct statement * stmt)20251f5207b7SJohn Levon static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
20261f5207b7SJohn Levon {
20271f5207b7SJohn Levon struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0);
20281f5207b7SJohn Levon struct statement *args = stmt->args;
20291f5207b7SJohn Levon struct basic_block *bb;
20301f5207b7SJohn Levon pseudo_t pseudo;
20311f5207b7SJohn Levon
20321f5207b7SJohn Levon if (args) {
20331f5207b7SJohn Levon struct symbol *sym;
20341f5207b7SJohn Levon
20351f5207b7SJohn Levon concat_symbol_list(args->declaration, &ep->syms);
20361f5207b7SJohn Levon FOR_EACH_PTR(args->declaration, sym) {
20371f5207b7SJohn Levon pseudo_t value = linearize_one_symbol(ep, sym);
2038*c85f09ccSJohn Levon add_pseudo(&insn->arguments, value);
20391f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
20401f5207b7SJohn Levon }
20411f5207b7SJohn Levon
2042*c85f09ccSJohn Levon pseudo = linearize_fn_statement(ep, stmt);
2043*c85f09ccSJohn Levon insn->target = pseudo;
2044*c85f09ccSJohn Levon
20451f5207b7SJohn Levon use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
20461f5207b7SJohn Levon bb = ep->active;
2047*c85f09ccSJohn Levon if (!bb->insns)
20481f5207b7SJohn Levon bb->pos = stmt->pos;
20491f5207b7SJohn Levon add_one_insn(ep, insn);
20501f5207b7SJohn Levon return pseudo;
20511f5207b7SJohn Levon }
20521f5207b7SJohn Levon
linearize_context(struct entrypoint * ep,struct statement * stmt)20531f5207b7SJohn Levon static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
20541f5207b7SJohn Levon {
20551f5207b7SJohn Levon struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
20561f5207b7SJohn Levon struct expression *expr = stmt->expression;
20571f5207b7SJohn Levon
2058*c85f09ccSJohn Levon insn->increment = get_expression_value(expr);
20591f5207b7SJohn Levon insn->context_expr = stmt->context;
20601f5207b7SJohn Levon add_one_insn(ep, insn);
20611f5207b7SJohn Levon return VOID;
20621f5207b7SJohn Levon }
20631f5207b7SJohn Levon
linearize_range(struct entrypoint * ep,struct statement * stmt)20641f5207b7SJohn Levon static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
20651f5207b7SJohn Levon {
20661f5207b7SJohn Levon struct instruction *insn = alloc_instruction(OP_RANGE, 0);
20671f5207b7SJohn Levon
20681f5207b7SJohn Levon use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1);
20691f5207b7SJohn Levon use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2);
20701f5207b7SJohn Levon use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3);
20711f5207b7SJohn Levon add_one_insn(ep, insn);
20721f5207b7SJohn Levon return VOID;
20731f5207b7SJohn Levon }
20741f5207b7SJohn Levon
20751f5207b7SJohn Levon ALLOCATOR(asm_rules, "asm rules");
20761f5207b7SJohn Levon ALLOCATOR(asm_constraint, "asm constraints");
20771f5207b7SJohn Levon
add_asm_input(struct entrypoint * ep,struct instruction * insn,struct expression * expr,const char * constraint,const struct ident * ident)20781f5207b7SJohn Levon static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
20791f5207b7SJohn Levon const char *constraint, const struct ident *ident)
20801f5207b7SJohn Levon {
20811f5207b7SJohn Levon pseudo_t pseudo = linearize_expression(ep, expr);
20821f5207b7SJohn Levon struct asm_constraint *rule = __alloc_asm_constraint(0);
20831f5207b7SJohn Levon
20841f5207b7SJohn Levon rule->ident = ident;
20851f5207b7SJohn Levon rule->constraint = constraint;
20861f5207b7SJohn Levon use_pseudo(insn, pseudo, &rule->pseudo);
20871f5207b7SJohn Levon add_ptr_list(&insn->asm_rules->inputs, rule);
20881f5207b7SJohn Levon }
20891f5207b7SJohn Levon
add_asm_output(struct entrypoint * ep,struct instruction * insn,struct expression * expr,const char * constraint,const struct ident * ident)20901f5207b7SJohn Levon static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
20911f5207b7SJohn Levon const char *constraint, const struct ident *ident)
20921f5207b7SJohn Levon {
20931f5207b7SJohn Levon struct access_data ad = { NULL, };
20941f5207b7SJohn Levon pseudo_t pseudo = alloc_pseudo(insn);
20951f5207b7SJohn Levon struct asm_constraint *rule;
20961f5207b7SJohn Levon
20971f5207b7SJohn Levon if (!expr || !linearize_address_gen(ep, expr, &ad))
20981f5207b7SJohn Levon return;
20991f5207b7SJohn Levon linearize_store_gen(ep, pseudo, &ad);
21001f5207b7SJohn Levon rule = __alloc_asm_constraint(0);
21011f5207b7SJohn Levon rule->ident = ident;
21021f5207b7SJohn Levon rule->constraint = constraint;
21031f5207b7SJohn Levon use_pseudo(insn, pseudo, &rule->pseudo);
21041f5207b7SJohn Levon add_ptr_list(&insn->asm_rules->outputs, rule);
21051f5207b7SJohn Levon }
21061f5207b7SJohn Levon
linearize_asm_statement(struct entrypoint * ep,struct statement * stmt)21071f5207b7SJohn Levon static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
21081f5207b7SJohn Levon {
21091f5207b7SJohn Levon struct expression *expr;
21101f5207b7SJohn Levon struct instruction *insn;
21111f5207b7SJohn Levon struct asm_rules *rules;
21121f5207b7SJohn Levon const char *constraint;
21131f5207b7SJohn Levon
21141f5207b7SJohn Levon insn = alloc_instruction(OP_ASM, 0);
21151f5207b7SJohn Levon expr = stmt->asm_string;
21161f5207b7SJohn Levon if (!expr || expr->type != EXPR_STRING) {
21171f5207b7SJohn Levon warning(stmt->pos, "expected string in inline asm");
21181f5207b7SJohn Levon return VOID;
21191f5207b7SJohn Levon }
21201f5207b7SJohn Levon insn->string = expr->string->data;
21211f5207b7SJohn Levon
21221f5207b7SJohn Levon rules = __alloc_asm_rules(0);
21231f5207b7SJohn Levon insn->asm_rules = rules;
21241f5207b7SJohn Levon
21251f5207b7SJohn Levon /* Gather the inputs.. */
21261f5207b7SJohn Levon FOR_EACH_PTR(stmt->asm_inputs, expr) {
2127*c85f09ccSJohn Levon constraint = expr->constraint ? expr->constraint->string->data : "";
2128*c85f09ccSJohn Levon add_asm_input(ep, insn, expr->expr, constraint, expr->name);
21291f5207b7SJohn Levon } END_FOR_EACH_PTR(expr);
21301f5207b7SJohn Levon
21311f5207b7SJohn Levon add_one_insn(ep, insn);
21321f5207b7SJohn Levon
21331f5207b7SJohn Levon /* Assign the outputs */
21341f5207b7SJohn Levon FOR_EACH_PTR(stmt->asm_outputs, expr) {
2135*c85f09ccSJohn Levon constraint = expr->constraint ? expr->constraint->string->data : "";
2136*c85f09ccSJohn Levon add_asm_output(ep, insn, expr->expr, constraint, expr->name);
21371f5207b7SJohn Levon } END_FOR_EACH_PTR(expr);
21381f5207b7SJohn Levon
21391f5207b7SJohn Levon return VOID;
21401f5207b7SJohn Levon }
21411f5207b7SJohn Levon
multijmp_cmp(const void * _a,const void * _b)21421f5207b7SJohn Levon static int multijmp_cmp(const void *_a, const void *_b)
21431f5207b7SJohn Levon {
21441f5207b7SJohn Levon const struct multijmp *a = _a;
21451f5207b7SJohn Levon const struct multijmp *b = _b;
21461f5207b7SJohn Levon
21471f5207b7SJohn Levon // "default" case?
21481f5207b7SJohn Levon if (a->begin > a->end) {
21491f5207b7SJohn Levon if (b->begin > b->end)
21501f5207b7SJohn Levon return 0;
21511f5207b7SJohn Levon return 1;
21521f5207b7SJohn Levon }
21531f5207b7SJohn Levon if (b->begin > b->end)
21541f5207b7SJohn Levon return -1;
21551f5207b7SJohn Levon if (a->begin == b->begin) {
21561f5207b7SJohn Levon if (a->end == b->end)
21571f5207b7SJohn Levon return 0;
21581f5207b7SJohn Levon return (a->end < b->end) ? -1 : 1;
21591f5207b7SJohn Levon }
21601f5207b7SJohn Levon return a->begin < b->begin ? -1 : 1;
21611f5207b7SJohn Levon }
21621f5207b7SJohn Levon
sort_switch_cases(struct instruction * insn)21631f5207b7SJohn Levon static void sort_switch_cases(struct instruction *insn)
21641f5207b7SJohn Levon {
21651f5207b7SJohn Levon sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
21661f5207b7SJohn Levon }
21671f5207b7SJohn Levon
linearize_declaration(struct entrypoint * ep,struct statement * stmt)21681f5207b7SJohn Levon static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt)
21691f5207b7SJohn Levon {
21701f5207b7SJohn Levon struct symbol *sym;
21711f5207b7SJohn Levon
21721f5207b7SJohn Levon concat_symbol_list(stmt->declaration, &ep->syms);
21731f5207b7SJohn Levon
21741f5207b7SJohn Levon FOR_EACH_PTR(stmt->declaration, sym) {
21751f5207b7SJohn Levon linearize_one_symbol(ep, sym);
21761f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
21771f5207b7SJohn Levon return VOID;
21781f5207b7SJohn Levon }
21791f5207b7SJohn Levon
linearize_return(struct entrypoint * ep,struct statement * stmt)21801f5207b7SJohn Levon static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
21811f5207b7SJohn Levon {
21821f5207b7SJohn Levon struct expression *expr = stmt->expression;
2183*c85f09ccSJohn Levon struct symbol *ret = stmt->ret_target;
2184*c85f09ccSJohn Levon struct basic_block *bb_return = get_bound_block(ep, ret);
21851f5207b7SJohn Levon struct basic_block *active;
21861f5207b7SJohn Levon pseudo_t src = linearize_expression(ep, expr);
21871f5207b7SJohn Levon active = ep->active;
2188*c85f09ccSJohn Levon if (active && !is_void_type(ret)) {
2189*c85f09ccSJohn Levon add_return(ep, bb_return, ret, src);
21901f5207b7SJohn Levon }
21911f5207b7SJohn Levon add_goto(ep, bb_return);
21921f5207b7SJohn Levon return VOID;
21931f5207b7SJohn Levon }
21941f5207b7SJohn Levon
linearize_switch(struct entrypoint * ep,struct statement * stmt)21951f5207b7SJohn Levon static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
21961f5207b7SJohn Levon {
21971f5207b7SJohn Levon struct symbol *sym;
21981f5207b7SJohn Levon struct instruction *switch_ins;
21991f5207b7SJohn Levon struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
22001f5207b7SJohn Levon struct basic_block *active, *default_case;
2201*c85f09ccSJohn Levon struct expression *expr = stmt->switch_expression;
22021f5207b7SJohn Levon struct multijmp *jmp;
22031f5207b7SJohn Levon pseudo_t pseudo;
22041f5207b7SJohn Levon
2205*c85f09ccSJohn Levon if (!expr || !expr->ctype)
22061f5207b7SJohn Levon return VOID;
2207*c85f09ccSJohn Levon pseudo = linearize_expression(ep, expr);
2208*c85f09ccSJohn Levon active = ep->active;
2209*c85f09ccSJohn Levon if (!active) {
2210*c85f09ccSJohn Levon active = alloc_basic_block(ep, stmt->pos);
2211*c85f09ccSJohn Levon set_activeblock(ep, active);
2212*c85f09ccSJohn Levon }
22131f5207b7SJohn Levon
2214*c85f09ccSJohn Levon switch_ins = alloc_typed_instruction(OP_SWITCH, expr->ctype);
22151f5207b7SJohn Levon use_pseudo(switch_ins, pseudo, &switch_ins->cond);
22161f5207b7SJohn Levon add_one_insn(ep, switch_ins);
22171f5207b7SJohn Levon finish_block(ep);
22181f5207b7SJohn Levon
22191f5207b7SJohn Levon default_case = NULL;
22201f5207b7SJohn Levon FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
22211f5207b7SJohn Levon struct statement *case_stmt = sym->stmt;
22221f5207b7SJohn Levon struct basic_block *bb_case = get_bound_block(ep, sym);
22231f5207b7SJohn Levon
22241f5207b7SJohn Levon if (!case_stmt->case_expression) {
22251f5207b7SJohn Levon default_case = bb_case;
22261f5207b7SJohn Levon continue;
2227*c85f09ccSJohn Levon } else if (case_stmt->case_expression->type != EXPR_VALUE) {
2228*c85f09ccSJohn Levon continue;
22291f5207b7SJohn Levon } else {
2230*c85f09ccSJohn Levon struct expression *case_to = case_stmt->case_to;
2231*c85f09ccSJohn Levon long long begin, end;
22321f5207b7SJohn Levon
22331f5207b7SJohn Levon begin = end = case_stmt->case_expression->value;
2234*c85f09ccSJohn Levon if (case_to && case_to->type == EXPR_VALUE)
2235*c85f09ccSJohn Levon end = case_to->value;
22361f5207b7SJohn Levon if (begin > end)
22371f5207b7SJohn Levon jmp = alloc_multijmp(bb_case, end, begin);
22381f5207b7SJohn Levon else
22391f5207b7SJohn Levon jmp = alloc_multijmp(bb_case, begin, end);
22401f5207b7SJohn Levon
22411f5207b7SJohn Levon }
22421f5207b7SJohn Levon add_multijmp(&switch_ins->multijmp_list, jmp);
22431f5207b7SJohn Levon add_bb(&bb_case->parents, active);
22441f5207b7SJohn Levon add_bb(&active->children, bb_case);
22451f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
22461f5207b7SJohn Levon
22471f5207b7SJohn Levon bind_label(stmt->switch_break, switch_end, stmt->pos);
22481f5207b7SJohn Levon
22491f5207b7SJohn Levon /* And linearize the actual statement */
22501f5207b7SJohn Levon linearize_statement(ep, stmt->switch_statement);
22511f5207b7SJohn Levon set_activeblock(ep, switch_end);
22521f5207b7SJohn Levon
22531f5207b7SJohn Levon if (!default_case)
22541f5207b7SJohn Levon default_case = switch_end;
22551f5207b7SJohn Levon
22561f5207b7SJohn Levon jmp = alloc_multijmp(default_case, 1, 0);
22571f5207b7SJohn Levon add_multijmp(&switch_ins->multijmp_list, jmp);
22581f5207b7SJohn Levon add_bb(&default_case->parents, active);
22591f5207b7SJohn Levon add_bb(&active->children, default_case);
22601f5207b7SJohn Levon sort_switch_cases(switch_ins);
22611f5207b7SJohn Levon
22621f5207b7SJohn Levon return VOID;
22631f5207b7SJohn Levon }
22641f5207b7SJohn Levon
linearize_iterator(struct entrypoint * ep,struct statement * stmt)22651f5207b7SJohn Levon static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt)
22661f5207b7SJohn Levon {
22671f5207b7SJohn Levon struct statement *pre_statement = stmt->iterator_pre_statement;
22681f5207b7SJohn Levon struct expression *pre_condition = stmt->iterator_pre_condition;
22691f5207b7SJohn Levon struct statement *statement = stmt->iterator_statement;
22701f5207b7SJohn Levon struct statement *post_statement = stmt->iterator_post_statement;
22711f5207b7SJohn Levon struct expression *post_condition = stmt->iterator_post_condition;
22721f5207b7SJohn Levon struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
22731f5207b7SJohn Levon struct symbol *sym;
22741f5207b7SJohn Levon
22751f5207b7SJohn Levon FOR_EACH_PTR(stmt->iterator_syms, sym) {
22761f5207b7SJohn Levon linearize_one_symbol(ep, sym);
22771f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
22781f5207b7SJohn Levon concat_symbol_list(stmt->iterator_syms, &ep->syms);
22791f5207b7SJohn Levon linearize_statement(ep, pre_statement);
22801f5207b7SJohn Levon
22811f5207b7SJohn Levon loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
22821f5207b7SJohn Levon loop_continue = alloc_basic_block(ep, stmt->pos);
22831f5207b7SJohn Levon loop_end = alloc_basic_block(ep, stmt->pos);
22841f5207b7SJohn Levon
22851f5207b7SJohn Levon /* An empty post-condition means that it's the same as the pre-condition */
22861f5207b7SJohn Levon if (!post_condition) {
22871f5207b7SJohn Levon loop_top = alloc_basic_block(ep, stmt->pos);
22881f5207b7SJohn Levon set_activeblock(ep, loop_top);
22891f5207b7SJohn Levon }
22901f5207b7SJohn Levon
22911f5207b7SJohn Levon if (pre_condition)
22921f5207b7SJohn Levon linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
22931f5207b7SJohn Levon
22941f5207b7SJohn Levon bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
22951f5207b7SJohn Levon bind_label(stmt->iterator_break, loop_end, stmt->pos);
22961f5207b7SJohn Levon
22971f5207b7SJohn Levon set_activeblock(ep, loop_body);
22981f5207b7SJohn Levon linearize_statement(ep, statement);
22991f5207b7SJohn Levon add_goto(ep, loop_continue);
23001f5207b7SJohn Levon
23011f5207b7SJohn Levon set_activeblock(ep, loop_continue);
23021f5207b7SJohn Levon linearize_statement(ep, post_statement);
23031f5207b7SJohn Levon if (!post_condition)
23041f5207b7SJohn Levon add_goto(ep, loop_top);
23051f5207b7SJohn Levon else
23061f5207b7SJohn Levon linearize_cond_branch(ep, post_condition, loop_top, loop_end);
23071f5207b7SJohn Levon set_activeblock(ep, loop_end);
23081f5207b7SJohn Levon
23091f5207b7SJohn Levon return VOID;
23101f5207b7SJohn Levon }
23111f5207b7SJohn Levon
linearize_statement(struct entrypoint * ep,struct statement * stmt)2312*c85f09ccSJohn Levon static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
23131f5207b7SJohn Levon {
23141f5207b7SJohn Levon struct basic_block *bb;
23151f5207b7SJohn Levon
23161f5207b7SJohn Levon if (!stmt)
23171f5207b7SJohn Levon return VOID;
23181f5207b7SJohn Levon
23191f5207b7SJohn Levon bb = ep->active;
23201f5207b7SJohn Levon if (bb && !bb->insns)
23211f5207b7SJohn Levon bb->pos = stmt->pos;
23221f5207b7SJohn Levon current_pos = stmt->pos;
23231f5207b7SJohn Levon
23241f5207b7SJohn Levon switch (stmt->type) {
23251f5207b7SJohn Levon case STMT_NONE:
23261f5207b7SJohn Levon break;
23271f5207b7SJohn Levon
23281f5207b7SJohn Levon case STMT_DECLARATION:
23291f5207b7SJohn Levon return linearize_declaration(ep, stmt);
23301f5207b7SJohn Levon
23311f5207b7SJohn Levon case STMT_CONTEXT:
23321f5207b7SJohn Levon return linearize_context(ep, stmt);
23331f5207b7SJohn Levon
23341f5207b7SJohn Levon case STMT_RANGE:
23351f5207b7SJohn Levon return linearize_range(ep, stmt);
23361f5207b7SJohn Levon
23371f5207b7SJohn Levon case STMT_EXPRESSION:
23381f5207b7SJohn Levon return linearize_expression(ep, stmt->expression);
23391f5207b7SJohn Levon
23401f5207b7SJohn Levon case STMT_ASM:
23411f5207b7SJohn Levon return linearize_asm_statement(ep, stmt);
23421f5207b7SJohn Levon
23431f5207b7SJohn Levon case STMT_RETURN:
23441f5207b7SJohn Levon return linearize_return(ep, stmt);
23451f5207b7SJohn Levon
23461f5207b7SJohn Levon case STMT_CASE: {
23471f5207b7SJohn Levon add_label(ep, stmt->case_label);
23481f5207b7SJohn Levon linearize_statement(ep, stmt->case_statement);
23491f5207b7SJohn Levon break;
23501f5207b7SJohn Levon }
23511f5207b7SJohn Levon
23521f5207b7SJohn Levon case STMT_LABEL: {
23531f5207b7SJohn Levon struct symbol *label = stmt->label_identifier;
23541f5207b7SJohn Levon
23551f5207b7SJohn Levon if (label->used) {
23561f5207b7SJohn Levon add_label(ep, label);
23571f5207b7SJohn Levon }
23581f5207b7SJohn Levon return linearize_statement(ep, stmt->label_statement);
23591f5207b7SJohn Levon }
23601f5207b7SJohn Levon
23611f5207b7SJohn Levon case STMT_GOTO: {
23621f5207b7SJohn Levon struct symbol *sym;
23631f5207b7SJohn Levon struct expression *expr;
23641f5207b7SJohn Levon struct instruction *goto_ins;
23651f5207b7SJohn Levon struct basic_block *active;
23661f5207b7SJohn Levon pseudo_t pseudo;
23671f5207b7SJohn Levon
23681f5207b7SJohn Levon active = ep->active;
23691f5207b7SJohn Levon if (!bb_reachable(active))
23701f5207b7SJohn Levon break;
23711f5207b7SJohn Levon
23721f5207b7SJohn Levon if (stmt->goto_label) {
23731f5207b7SJohn Levon add_goto(ep, get_bound_block(ep, stmt->goto_label));
23741f5207b7SJohn Levon break;
23751f5207b7SJohn Levon }
23761f5207b7SJohn Levon
23771f5207b7SJohn Levon expr = stmt->goto_expression;
23781f5207b7SJohn Levon if (!expr)
23791f5207b7SJohn Levon break;
23801f5207b7SJohn Levon
23811f5207b7SJohn Levon /* This can happen as part of simplification */
23821f5207b7SJohn Levon if (expr->type == EXPR_LABEL) {
23831f5207b7SJohn Levon add_goto(ep, get_bound_block(ep, expr->label_symbol));
23841f5207b7SJohn Levon break;
23851f5207b7SJohn Levon }
23861f5207b7SJohn Levon
23871f5207b7SJohn Levon pseudo = linearize_expression(ep, expr);
23881f5207b7SJohn Levon goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
2389*c85f09ccSJohn Levon use_pseudo(goto_ins, pseudo, &goto_ins->src);
23901f5207b7SJohn Levon add_one_insn(ep, goto_ins);
23911f5207b7SJohn Levon
23921f5207b7SJohn Levon FOR_EACH_PTR(stmt->target_list, sym) {
23931f5207b7SJohn Levon struct basic_block *bb_computed = get_bound_block(ep, sym);
23941f5207b7SJohn Levon struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
23951f5207b7SJohn Levon add_multijmp(&goto_ins->multijmp_list, jmp);
23961f5207b7SJohn Levon add_bb(&bb_computed->parents, ep->active);
23971f5207b7SJohn Levon add_bb(&active->children, bb_computed);
23981f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
23991f5207b7SJohn Levon
24001f5207b7SJohn Levon finish_block(ep);
24011f5207b7SJohn Levon break;
24021f5207b7SJohn Levon }
24031f5207b7SJohn Levon
24041f5207b7SJohn Levon case STMT_COMPOUND:
24051f5207b7SJohn Levon if (stmt->inline_fn)
24061f5207b7SJohn Levon return linearize_inlined_call(ep, stmt);
24071f5207b7SJohn Levon return linearize_compound_statement(ep, stmt);
24081f5207b7SJohn Levon
24091f5207b7SJohn Levon /*
24101f5207b7SJohn Levon * This could take 'likely/unlikely' into account, and
24111f5207b7SJohn Levon * switch the arms around appropriately..
24121f5207b7SJohn Levon */
24131f5207b7SJohn Levon case STMT_IF: {
24141f5207b7SJohn Levon struct basic_block *bb_true, *bb_false, *endif;
24151f5207b7SJohn Levon struct expression *cond = stmt->if_conditional;
24161f5207b7SJohn Levon
24171f5207b7SJohn Levon bb_true = alloc_basic_block(ep, stmt->pos);
24181f5207b7SJohn Levon bb_false = endif = alloc_basic_block(ep, stmt->pos);
24191f5207b7SJohn Levon
24201f5207b7SJohn Levon linearize_cond_branch(ep, cond, bb_true, bb_false);
24211f5207b7SJohn Levon
24221f5207b7SJohn Levon set_activeblock(ep, bb_true);
24231f5207b7SJohn Levon linearize_statement(ep, stmt->if_true);
24241f5207b7SJohn Levon
24251f5207b7SJohn Levon if (stmt->if_false) {
24261f5207b7SJohn Levon endif = alloc_basic_block(ep, stmt->pos);
24271f5207b7SJohn Levon add_goto(ep, endif);
24281f5207b7SJohn Levon set_activeblock(ep, bb_false);
24291f5207b7SJohn Levon linearize_statement(ep, stmt->if_false);
24301f5207b7SJohn Levon }
24311f5207b7SJohn Levon set_activeblock(ep, endif);
24321f5207b7SJohn Levon break;
24331f5207b7SJohn Levon }
24341f5207b7SJohn Levon
24351f5207b7SJohn Levon case STMT_SWITCH:
24361f5207b7SJohn Levon return linearize_switch(ep, stmt);
24371f5207b7SJohn Levon
24381f5207b7SJohn Levon case STMT_ITERATOR:
24391f5207b7SJohn Levon return linearize_iterator(ep, stmt);
24401f5207b7SJohn Levon
24411f5207b7SJohn Levon default:
24421f5207b7SJohn Levon break;
24431f5207b7SJohn Levon }
24441f5207b7SJohn Levon return VOID;
24451f5207b7SJohn Levon }
24461f5207b7SJohn Levon
linearize_fn(struct symbol * sym,struct symbol * base_type)24471f5207b7SJohn Levon static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
24481f5207b7SJohn Levon {
2449*c85f09ccSJohn Levon struct statement *stmt = base_type->stmt;
24501f5207b7SJohn Levon struct entrypoint *ep;
24511f5207b7SJohn Levon struct basic_block *bb;
2452*c85f09ccSJohn Levon struct symbol *ret_type;
24531f5207b7SJohn Levon struct symbol *arg;
24541f5207b7SJohn Levon struct instruction *entry;
2455*c85f09ccSJohn Levon struct instruction *ret;
24561f5207b7SJohn Levon pseudo_t result;
24571f5207b7SJohn Levon int i;
24581f5207b7SJohn Levon
2459*c85f09ccSJohn Levon if (!stmt)
24601f5207b7SJohn Levon return NULL;
24611f5207b7SJohn Levon
24621f5207b7SJohn Levon ep = alloc_entrypoint();
24631f5207b7SJohn Levon ep->name = sym;
24641f5207b7SJohn Levon sym->ep = ep;
2465*c85f09ccSJohn Levon bb = alloc_basic_block(ep, sym->pos);
24661f5207b7SJohn Levon set_activeblock(ep, bb);
24671f5207b7SJohn Levon
2468*c85f09ccSJohn Levon if (stmt->type == STMT_ASM) { // top-level asm
2469*c85f09ccSJohn Levon linearize_asm_statement(ep, stmt);
2470*c85f09ccSJohn Levon return ep;
2471*c85f09ccSJohn Levon }
2472*c85f09ccSJohn Levon
24731f5207b7SJohn Levon entry = alloc_instruction(OP_ENTRY, 0);
24741f5207b7SJohn Levon add_one_insn(ep, entry);
24751f5207b7SJohn Levon ep->entry = entry;
24761f5207b7SJohn Levon
24771f5207b7SJohn Levon concat_symbol_list(base_type->arguments, &ep->syms);
24781f5207b7SJohn Levon
24791f5207b7SJohn Levon /* FIXME!! We should do something else about varargs.. */
24801f5207b7SJohn Levon i = 0;
24811f5207b7SJohn Levon FOR_EACH_PTR(base_type->arguments, arg) {
24821f5207b7SJohn Levon linearize_argument(ep, arg, ++i);
24831f5207b7SJohn Levon } END_FOR_EACH_PTR(arg);
24841f5207b7SJohn Levon
2485*c85f09ccSJohn Levon result = linearize_fn_statement(ep, stmt);
2486*c85f09ccSJohn Levon ret_type = base_type->ctype.base_type;
2487*c85f09ccSJohn Levon ret = alloc_typed_instruction(OP_RET, ret_type);
2488*c85f09ccSJohn Levon if (type_size(ret_type) > 0)
2489*c85f09ccSJohn Levon use_pseudo(ret, result, &ret->src);
2490*c85f09ccSJohn Levon add_one_insn(ep, ret);
24911f5207b7SJohn Levon
2492*c85f09ccSJohn Levon optimize(ep);
24931f5207b7SJohn Levon return ep;
24941f5207b7SJohn Levon }
24951f5207b7SJohn Levon
linearize_symbol(struct symbol * sym)24961f5207b7SJohn Levon struct entrypoint *linearize_symbol(struct symbol *sym)
24971f5207b7SJohn Levon {
24981f5207b7SJohn Levon struct symbol *base_type;
24991f5207b7SJohn Levon
25001f5207b7SJohn Levon if (!sym)
25011f5207b7SJohn Levon return NULL;
25021f5207b7SJohn Levon current_pos = sym->pos;
25031f5207b7SJohn Levon base_type = sym->ctype.base_type;
25041f5207b7SJohn Levon if (!base_type)
25051f5207b7SJohn Levon return NULL;
25061f5207b7SJohn Levon if (base_type->type == SYM_FN)
25071f5207b7SJohn Levon return linearize_fn(sym, base_type);
25081f5207b7SJohn Levon return NULL;
25091f5207b7SJohn Levon }
2510