Print this page
11972 resync smatch
@@ -17,16 +17,18 @@
#include <assert.h>
#include "parse.h"
#include "expression.h"
#include "linearize.h"
+#include "optimize.h"
#include "flow.h"
#include "target.h"
-pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
-pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
+static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
+static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
+static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to, struct symbol *from, int op, pseudo_t src);
static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym);
struct access_data;
@@ -68,32 +70,35 @@
static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos)
{
static int nr;
struct basic_block *bb = __alloc_basic_block(0);
- bb->context = -1;
bb->pos = pos;
bb->ep = ep;
bb->nr = nr++;
return bb;
}
-static struct multijmp *alloc_multijmp(struct basic_block *target, int begin, int end)
+static struct multijmp *alloc_multijmp(struct basic_block *target, long long begin, long long end)
{
struct multijmp *multijmp = __alloc_multijmp(0);
multijmp->target = target;
multijmp->begin = begin;
multijmp->end = end;
return multijmp;
}
-static inline int regno(pseudo_t n)
+const char *show_label(struct basic_block *bb)
{
- int retval = -1;
- if (n && n->type == PSEUDO_REG)
- retval = n->nr;
- return retval;
+ static int n;
+ static char buffer[4][16];
+ char *buf = buffer[3 & ++n];
+
+ if (!bb)
+ return ".L???";
+ snprintf(buf, 64, ".L%u", bb->nr);
+ return buf;
}
const char *show_pseudo(pseudo_t pseudo)
{
static int n;
@@ -109,20 +114,24 @@
switch(pseudo->type) {
case PSEUDO_SYM: {
struct symbol *sym = pseudo->sym;
struct expression *expr;
+ if (!sym) {
+ snprintf(buf, 64, "<bad symbol>");
+ break;
+ }
if (sym->bb_target) {
- snprintf(buf, 64, ".L%u", sym->bb_target->nr);
+ snprintf(buf, 64, "%s", show_label(sym->bb_target));
break;
}
if (sym->ident) {
snprintf(buf, 64, "%s", show_ident(sym->ident));
break;
}
expr = sym->initializer;
- snprintf(buf, 64, "<anon symbol:%p>", sym);
+ snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
if (expr) {
switch (expr->type) {
case EXPR_VALUE:
snprintf(buf, 64, "<symbol value: %lld>", expr->value);
break;
@@ -153,10 +162,12 @@
case PSEUDO_PHI:
i = snprintf(buf, 64, "%%phi%d", pseudo->nr);
if (pseudo->ident)
sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
break;
+ case PSEUDO_UNDEF:
+ return "UNDEF";
default:
snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
}
return buf;
}
@@ -170,33 +181,34 @@
/* Terminator */
[OP_RET] = "ret",
[OP_BR] = "br",
[OP_CBR] = "cbr",
[OP_SWITCH] = "switch",
- [OP_INVOKE] = "invoke",
[OP_COMPUTEDGOTO] = "jmp *",
- [OP_UNWIND] = "unwind",
/* Binary */
[OP_ADD] = "add",
[OP_SUB] = "sub",
- [OP_MULU] = "mulu",
- [OP_MULS] = "muls",
+ [OP_MUL] = "mul",
[OP_DIVU] = "divu",
[OP_DIVS] = "divs",
[OP_MODU] = "modu",
[OP_MODS] = "mods",
[OP_SHL] = "shl",
[OP_LSR] = "lsr",
[OP_ASR] = "asr",
+ /* Floating-point Binary */
+ [OP_FADD] = "fadd",
+ [OP_FSUB] = "fsub",
+ [OP_FMUL] = "fmul",
+ [OP_FDIV] = "fdiv",
+
/* Logical */
[OP_AND] = "and",
[OP_OR] = "or",
[OP_XOR] = "xor",
- [OP_AND_BOOL] = "and-bool",
- [OP_OR_BOOL] = "or-bool",
/* Binary comparison */
[OP_SET_EQ] = "seteq",
[OP_SET_NE] = "setne",
[OP_SET_LE] = "setle",
@@ -206,41 +218,58 @@
[OP_SET_B] = "setb",
[OP_SET_A] = "seta",
[OP_SET_BE] = "setbe",
[OP_SET_AE] = "setae",
+ /* floating-point comparison */
+ [OP_FCMP_ORD] = "fcmpord",
+ [OP_FCMP_OEQ] = "fcmpoeq",
+ [OP_FCMP_ONE] = "fcmpone",
+ [OP_FCMP_OLE] = "fcmpole",
+ [OP_FCMP_OGE] = "fcmpoge",
+ [OP_FCMP_OLT] = "fcmpolt",
+ [OP_FCMP_OGT] = "fcmpogt",
+ [OP_FCMP_UEQ] = "fcmpueq",
+ [OP_FCMP_UNE] = "fcmpune",
+ [OP_FCMP_ULE] = "fcmpule",
+ [OP_FCMP_UGE] = "fcmpuge",
+ [OP_FCMP_ULT] = "fcmpult",
+ [OP_FCMP_UGT] = "fcmpugt",
+ [OP_FCMP_UNO] = "fcmpuno",
+
/* Uni */
[OP_NOT] = "not",
[OP_NEG] = "neg",
+ [OP_FNEG] = "fneg",
/* Special three-input */
[OP_SEL] = "select",
/* Memory */
- [OP_MALLOC] = "malloc",
- [OP_FREE] = "free",
- [OP_ALLOCA] = "alloca",
[OP_LOAD] = "load",
[OP_STORE] = "store",
[OP_SETVAL] = "set",
+ [OP_SETFVAL] = "setfval",
[OP_SYMADDR] = "symaddr",
- [OP_GET_ELEMENT_PTR] = "getelem",
/* Other */
[OP_PHI] = "phi",
[OP_PHISOURCE] = "phisrc",
- [OP_CAST] = "cast",
- [OP_SCAST] = "scast",
- [OP_FPCAST] = "fpcast",
+ [OP_SEXT] = "sext",
+ [OP_ZEXT] = "zext",
+ [OP_TRUNC] = "trunc",
+ [OP_FCVTU] = "fcvtu",
+ [OP_FCVTS] = "fcvts",
+ [OP_UCVTF] = "ucvtf",
+ [OP_SCVTF] = "scvtf",
+ [OP_FCVTF] = "fcvtf",
+ [OP_UTPTR] = "utptr",
+ [OP_PTRTU] = "ptrtu",
[OP_PTRCAST] = "ptrcast",
[OP_INLINED_CALL] = "# call",
[OP_CALL] = "call",
- [OP_VANEXT] = "va_next",
- [OP_VAARG] = "va_arg",
[OP_SLICE] = "slice",
- [OP_SNOP] = "snop",
- [OP_LNOP] = "lnop",
[OP_NOP] = "nop",
[OP_DEATHNOTE] = "dead",
[OP_ASM] = "asm",
/* Sparse tagging (line numbers, context, whatever) */
@@ -305,38 +334,19 @@
if (insn->src && insn->src != VOID)
buf += sprintf(buf, "%s", show_pseudo(insn->src));
break;
case OP_CBR:
- buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
+ buf += sprintf(buf, "%s, %s, %s", show_pseudo(insn->cond), show_label(insn->bb_true), show_label(insn->bb_false));
break;
case OP_BR:
- buf += sprintf(buf, ".L%u", insn->bb_true->nr);
+ buf += sprintf(buf, "%s", show_label(insn->bb_true));
break;
- case OP_SYMADDR: {
- struct symbol *sym = insn->symbol->sym;
- buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
-
- if (!insn->bb && !sym)
- break;
- if (sym->bb_target) {
- buf += sprintf(buf, ".L%u", sym->bb_target->nr);
- break;
- }
- if (sym->ident) {
- buf += sprintf(buf, "%s", show_ident(sym->ident));
- break;
- }
- buf += sprintf(buf, "<anon symbol:%p>", sym);
- break;
- }
-
case OP_SETVAL: {
struct expression *expr = insn->val;
- struct symbol *sym;
buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
if (!expr) {
buf += sprintf(buf, "%s", "<none>");
break;
@@ -345,46 +355,49 @@
switch (expr->type) {
case EXPR_VALUE:
buf += sprintf(buf, "%lld", expr->value);
break;
case EXPR_FVALUE:
- buf += sprintf(buf, "%Lf", expr->fvalue);
+ buf += sprintf(buf, "%Le", expr->fvalue);
break;
case EXPR_STRING:
buf += sprintf(buf, "%.40s", show_string(expr->string));
break;
case EXPR_SYMBOL:
buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
break;
case EXPR_LABEL:
- sym = expr->symbol;
- if (sym->bb_target)
- buf += sprintf(buf, ".L%u", sym->bb_target->nr);
+ buf += sprintf(buf, "%s", show_label(expr->symbol->bb_target));
break;
default:
buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
}
break;
}
+ case OP_SETFVAL:
+ buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
+ buf += sprintf(buf, "%Le", insn->fvalue);
+ break;
+
case OP_SWITCH: {
struct multijmp *jmp;
buf += sprintf(buf, "%s", show_pseudo(insn->cond));
FOR_EACH_PTR(insn->multijmp_list, jmp) {
if (jmp->begin == jmp->end)
- buf += sprintf(buf, ", %d -> .L%u", jmp->begin, jmp->target->nr);
+ buf += sprintf(buf, ", %lld -> %s", jmp->begin, show_label(jmp->target));
else if (jmp->begin < jmp->end)
- buf += sprintf(buf, ", %d ... %d -> .L%u", jmp->begin, jmp->end, jmp->target->nr);
+ buf += sprintf(buf, ", %lld ... %lld -> %s", jmp->begin, jmp->end, show_label(jmp->target));
else
- buf += sprintf(buf, ", default -> .L%u", jmp->target->nr);
+ buf += sprintf(buf, ", default -> %s", show_label(jmp->target));
} END_FOR_EACH_PTR(jmp);
break;
}
case OP_COMPUTEDGOTO: {
struct multijmp *jmp;
- buf += sprintf(buf, "%s", show_pseudo(insn->target));
+ buf += sprintf(buf, "%s", show_pseudo(insn->src));
FOR_EACH_PTR(insn->multijmp_list, jmp) {
- buf += sprintf(buf, ", .L%u", jmp->target->nr);
+ buf += sprintf(buf, ", %s", show_label(jmp->target));
} END_FOR_EACH_PTR(jmp);
break;
}
case OP_PHISOURCE: {
@@ -399,19 +412,21 @@
case OP_PHI: {
pseudo_t phi;
const char *s = " <-";
buf += sprintf(buf, "%s", show_pseudo(insn->target));
FOR_EACH_PTR(insn->phi_list, phi) {
+ if (phi == VOID && !verbose)
+ continue;
buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
s = ",";
} END_FOR_EACH_PTR(phi);
break;
}
- case OP_LOAD: case OP_LNOP:
+ case OP_LOAD:
buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
break;
- case OP_STORE: case OP_SNOP:
+ case OP_STORE:
buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
break;
case OP_INLINED_CALL:
case OP_CALL: {
struct pseudo *arg;
@@ -421,20 +436,25 @@
FOR_EACH_PTR(insn->arguments, arg) {
buf += sprintf(buf, ", %s", show_pseudo(arg));
} END_FOR_EACH_PTR(arg);
break;
}
- case OP_CAST:
- case OP_SCAST:
- case OP_FPCAST:
+ case OP_SEXT: case OP_ZEXT:
+ case OP_TRUNC:
+ case OP_FCVTU: case OP_FCVTS:
+ case OP_UCVTF: case OP_SCVTF:
+ case OP_FCVTF:
+ case OP_UTPTR:
+ case OP_PTRTU:
case OP_PTRCAST:
buf += sprintf(buf, "%s <- (%d) %s",
show_pseudo(insn->target),
type_size(insn->orig_type),
show_pseudo(insn->src));
break;
case OP_BINARY ... OP_BINARY_END:
+ case OP_FPCMP ... OP_FPCMP_END:
case OP_BINCMP ... OP_BINCMP_END:
buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
break;
case OP_SEL:
@@ -445,10 +465,12 @@
case OP_SLICE:
buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
break;
case OP_NOT: case OP_NEG:
+ case OP_FNEG:
+ case OP_SYMADDR:
buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
break;
case OP_CONTEXT:
buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
@@ -481,27 +503,27 @@
void show_bb(struct basic_block *bb)
{
struct instruction *insn;
- printf(".L%u:\n", bb->nr);
+ printf("%s:\n", show_label(bb));
if (verbose) {
pseudo_t needs, defines;
printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
FOR_EACH_PTR(bb->needs, needs) {
struct instruction *def = needs->def;
if (def->opcode != OP_PHI) {
- printf(" **uses %s (from .L%u)**\n", show_pseudo(needs), def->bb->nr);
+ printf(" **uses %s (from %s)**\n", show_pseudo(needs), show_label(def->bb));
} else {
pseudo_t phi;
const char *sep = " ";
printf(" **uses %s (from", show_pseudo(needs));
FOR_EACH_PTR(def->phi_list, phi) {
if (phi == VOID)
continue;
- printf("%s(%s:.L%u)", sep, show_pseudo(phi), phi->def->bb->nr);
+ printf("%s(%s:%s)", sep, show_pseudo(phi), show_label(phi->def->bb));
sep = ", ";
} END_FOR_EACH_PTR(phi);
printf(")**\n");
}
} END_FOR_EACH_PTR(needs);
@@ -511,19 +533,19 @@
} END_FOR_EACH_PTR(defines);
if (bb->parents) {
struct basic_block *from;
FOR_EACH_PTR(bb->parents, from) {
- printf(" **from .L%u (%s:%d:%d)**\n", from->nr,
+ printf(" **from %s (%s:%d:%d)**\n", show_label(from),
stream_name(from->pos.stream), from->pos.line, from->pos.pos);
} END_FOR_EACH_PTR(from);
}
if (bb->children) {
struct basic_block *to;
FOR_EACH_PTR(bb->children, to) {
- printf(" **to .L%u (%s:%d:%d)**\n", to->nr,
+ printf(" **to %s (%s:%d:%d)**\n", show_label(to),
stream_name(to->pos.stream), to->pos.line, to->pos.pos);
} END_FOR_EACH_PTR(to);
}
}
@@ -683,11 +705,11 @@
struct instruction *select;
/* Remove the 'br' */
delete_last_instruction(&bb->insns);
- select = alloc_instruction(OP_SEL, phi_node->size);
+ select = alloc_typed_instruction(OP_SEL, phi_node->type);
select->bb = bb;
assert(br->cond);
use_pseudo(select, br->cond, &select->src1);
@@ -724,11 +746,11 @@
}
label->bb_target = bb;
return bb;
}
-static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
+static void add_branch(struct entrypoint *ep, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
{
struct basic_block *bb = ep->active;
struct instruction *br;
if (bb_reachable(bb)) {
@@ -742,11 +764,10 @@
add_bb(&bb->children, bb_false);
add_one_insn(ep, br);
}
}
-/* Dummy pseudo allocator */
pseudo_t alloc_pseudo(struct instruction *def)
{
static int nr = 0;
struct pseudo * pseudo = __alloc_pseudo(0);
pseudo->type = PSEUDO_REG;
@@ -753,19 +774,10 @@
pseudo->nr = ++nr;
pseudo->def = def;
return pseudo;
}
-static void clear_symbol_pseudos(struct entrypoint *ep)
-{
- pseudo_t pseudo;
-
- FOR_EACH_PTR(ep->accesses, pseudo) {
- pseudo->sym->pseudo = NULL;
- } END_FOR_EACH_PTR(pseudo);
-}
-
static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
{
pseudo_t pseudo;
if (!sym)
@@ -779,39 +791,43 @@
pseudo->sym = sym;
pseudo->ident = sym->ident;
sym->pseudo = pseudo;
add_pseudo(&ep->accesses, pseudo);
}
- /* Symbol pseudos have neither nr, usage nor def */
+ /* Symbol pseudos have neither nr nor def */
return pseudo;
}
-pseudo_t value_pseudo(struct symbol *type, long long val)
+pseudo_t value_pseudo(long long val)
{
#define MAX_VAL_HASH 64
static struct pseudo_list *prev[MAX_VAL_HASH];
int hash = val & (MAX_VAL_HASH-1);
struct pseudo_list **list = prev + hash;
- int size = type ? type->bit_size : value_size(val);
pseudo_t pseudo;
-
FOR_EACH_PTR(*list, pseudo) {
- if (pseudo->value == val && pseudo->size == size)
+ if (pseudo->value == val)
return pseudo;
} END_FOR_EACH_PTR(pseudo);
pseudo = __alloc_pseudo(0);
pseudo->type = PSEUDO_VAL;
pseudo->value = val;
- pseudo->size = size;
add_pseudo(list, pseudo);
/* Value pseudos have neither nr, usage nor def */
return pseudo;
}
+pseudo_t undef_pseudo(void)
+{
+ pseudo_t pseudo = __alloc_pseudo(0);
+ pseudo->type = PSEUDO_UNDEF;
+ return pseudo;
+}
+
static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
{
pseudo_t pseudo = __alloc_pseudo(0);
struct instruction *entry = ep->entry;
@@ -822,49 +838,86 @@
/* Argument pseudos have neither usage nor def */
return pseudo;
}
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
+struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type)
{
- struct instruction *insn;
- pseudo_t phi;
+ struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
+ pseudo_t phi = __alloc_pseudo(0);
static int nr = 0;
- if (!source)
- return VOID;
-
- insn = alloc_instruction(OP_PHISOURCE, size);
- phi = __alloc_pseudo(0);
phi->type = PSEUDO_PHI;
phi->nr = ++nr;
phi->def = insn;
use_pseudo(insn, pseudo, &insn->phi_src);
- insn->bb = source;
insn->target = phi;
+ return insn;
+}
+
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
+{
+ struct instruction *insn;
+
+ if (!source)
+ return VOID;
+
+ insn = alloc_phisrc(pseudo, type);
+ insn->bb = source;
add_instruction(&source->insns, insn);
- return phi;
+ return insn->target;
}
+struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident)
+{
+ struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
+ pseudo_t phi;
+
+ phi = alloc_pseudo(phi_node);
+ phi->ident = ident;
+ phi->def = phi_node;
+ phi_node->target = phi;
+ phi_node->bb = bb;
+ return phi_node;
+}
+
+void add_phi_node(struct basic_block *bb, struct instruction *phi_node)
+{
+ struct instruction *insn;
+
+ FOR_EACH_PTR(bb->insns, insn) {
+ enum opcode op = insn->opcode;
+ if (op == OP_PHI)
+ continue;
+ INSERT_CURRENT(phi_node, insn);
+ return;
+ } END_FOR_EACH_PTR(insn);
+
+ // FIXME
+ add_instruction(&bb->insns, phi_node);
+}
+
+struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var)
+{
+ struct instruction *phi_node = alloc_phi_node(bb, var, var->ident);
+ add_phi_node(bb, phi_node);
+ return phi_node;
+}
+
/*
* We carry the "access_data" structure around for any accesses,
* which simplifies things a lot. It contains all the access
* information in one place.
*/
struct access_data {
- struct symbol *result_type; // result ctype
- struct symbol *source_type; // source ctype
+ struct symbol *type; // ctype
+ struct symbol *btype; // base type of bitfields
pseudo_t address; // pseudo containing address ..
unsigned int offset; // byte offset
- struct position pos;
};
-static void finish_address_gen(struct entrypoint *ep, struct access_data *ad)
-{
-}
-
static int linearize_simple_address(struct entrypoint *ep,
struct expression *addr,
struct access_data *ad)
{
if (addr->type == EXPR_SYMBOL) {
@@ -882,11 +935,11 @@
}
ad->address = linearize_expression(ep, addr);
return 1;
}
-static struct symbol *base_type(struct symbol *sym)
+static struct symbol *bitfield_base_type(struct symbol *sym)
{
struct symbol *base = sym;
if (sym) {
if (sym->type == SYM_NODE)
@@ -903,13 +956,11 @@
{
struct symbol *ctype = expr->ctype;
if (!ctype)
return 0;
- ad->pos = expr->pos;
- ad->result_type = ctype;
- ad->source_type = base_type(ctype);
+ ad->type = ctype;
if (expr->type == EXPR_PREOP && expr->op == '*')
return linearize_simple_address(ep, expr->unop, ad);
warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
return 0;
@@ -918,57 +969,96 @@
static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
{
struct instruction *insn;
pseudo_t new;
- insn = alloc_typed_instruction(OP_LOAD, ad->source_type);
+ if (!ep->active)
+ return VOID;
+
+ insn = alloc_typed_instruction(OP_LOAD, ad->btype);
new = alloc_pseudo(insn);
insn->target = new;
insn->offset = ad->offset;
+ insn->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
use_pseudo(insn, ad->address, &insn->src);
add_one_insn(ep, insn);
return new;
}
static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
{
struct basic_block *bb = ep->active;
+ struct instruction *store;
- if (bb_reachable(bb)) {
- struct instruction *store = alloc_typed_instruction(OP_STORE, ad->source_type);
+ if (!bb)
+ return;
+
+ store = alloc_typed_instruction(OP_STORE, ad->btype);
store->offset = ad->offset;
+ store->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
use_pseudo(store, value, &store->target);
use_pseudo(store, ad->address, &store->src);
add_one_insn(ep, store);
+}
+
+static pseudo_t linearize_bitfield_insert(struct entrypoint *ep,
+ pseudo_t ori, pseudo_t val, struct symbol *ctype, struct symbol *btype)
+{
+ unsigned int shift = ctype->bit_offset;
+ unsigned int size = ctype->bit_size;
+ unsigned long long mask = ((1ULL << size) - 1);
+ unsigned long long smask= bits_mask(btype->bit_size);
+
+ val = add_cast(ep, btype, ctype, OP_ZEXT, val);
+ if (shift) {
+ val = add_binary_op(ep, btype, OP_SHL, val, value_pseudo(shift));
+ mask <<= shift;
}
+ ori = add_binary_op(ep, btype, OP_AND, ori, value_pseudo(~mask & smask));
+ val = add_binary_op(ep, btype, OP_OR, ori, val);
+
+ return val;
}
static pseudo_t linearize_store_gen(struct entrypoint *ep,
pseudo_t value,
struct access_data *ad)
{
+ struct symbol *ctype = ad->type;
+ struct symbol *btype;
pseudo_t store = value;
- if (type_size(ad->source_type) != type_size(ad->result_type)) {
- struct symbol *ctype = ad->result_type;
- unsigned int shift = ctype->bit_offset;
- unsigned int size = ctype->bit_size;
- pseudo_t orig = add_load(ep, ad);
- unsigned long long mask = (1ULL << size) - 1;
+ if (!ep->active)
+ return VOID;
- if (shift) {
- store = add_binary_op(ep, ad->source_type, OP_SHL, value, value_pseudo(ctype, shift));
- mask <<= shift;
+ btype = ad->btype = bitfield_base_type(ctype);
+ if (type_size(btype) != type_size(ctype)) {
+ pseudo_t orig = add_load(ep, ad);
+ store = linearize_bitfield_insert(ep, orig, value, ctype, btype);
}
- orig = add_binary_op(ep, ad->source_type, OP_AND, orig, value_pseudo(ctype, ~mask));
- store = add_binary_op(ep, ad->source_type, OP_OR, orig, store);
- }
add_store(ep, ad, store);
return value;
}
+static void taint_undefined_behaviour(struct instruction *insn)
+{
+ pseudo_t src2;
+
+ switch (insn->opcode) {
+ case OP_LSR:
+ case OP_ASR:
+ case OP_SHL:
+ src2 = insn->src2;
+ if (src2->type != PSEUDO_VAL)
+ break;
+ if ((unsigned long long)src2->value >= insn->size)
+ insn->tainted = 1;
+ break;
+ }
+}
+
static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
{
struct instruction *insn = alloc_typed_instruction(op, ctype);
pseudo_t target = alloc_pseudo(insn);
insn->target = target;
@@ -986,33 +1076,57 @@
insn->val = val;
add_one_insn(ep, insn);
return target;
}
+static pseudo_t add_setfval(struct entrypoint *ep, struct symbol *ctype, long double fval)
+{
+ struct instruction *insn = alloc_typed_instruction(OP_SETFVAL, ctype);
+ pseudo_t target = alloc_pseudo(insn);
+ insn->target = target;
+ insn->fvalue = fval;
+ add_one_insn(ep, insn);
+ return target;
+}
+
static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
{
struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
pseudo_t target = alloc_pseudo(insn);
insn->target = target;
- use_pseudo(insn, symbol_pseudo(ep, sym), &insn->symbol);
+ use_pseudo(insn, symbol_pseudo(ep, sym), &insn->src);
add_one_insn(ep, insn);
return target;
}
-static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
+static pseudo_t linearize_bitfield_extract(struct entrypoint *ep,
+ pseudo_t val, struct symbol *ctype, struct symbol *btype)
{
- struct symbol *ctype = ad->result_type;
- pseudo_t new = add_load(ep, ad);
+ unsigned int off = ctype->bit_offset;
- if (ctype->bit_offset) {
- pseudo_t shift = value_pseudo(ctype, ctype->bit_offset);
- pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
- new = newval;
+ if (off) {
+ pseudo_t shift = value_pseudo(off);
+ val = add_binary_op(ep, btype, OP_LSR, val, shift);
}
- if (ctype->bit_size != type_size(ad->source_type))
- new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
+ val = cast_pseudo(ep, val, btype, ctype);
+ return val;
+}
+
+static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
+{
+ struct symbol *ctype = ad->type;
+ struct symbol *btype;
+ pseudo_t new;
+
+ if (!ep->active)
+ return VOID;
+
+ btype = ad->btype = bitfield_base_type(ctype);
+ new = add_load(ep, ad);
+ if (ctype->bit_size != type_size(btype))
+ new = linearize_bitfield_extract(ep, new, ctype, btype);
return new;
}
static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
{
@@ -1020,15 +1134,13 @@
pseudo_t value;
if (!linearize_address_gen(ep, expr, &ad))
return VOID;
value = linearize_load_gen(ep, &ad);
- finish_address_gen(ep, &ad);
return value;
}
-/* FIXME: FP */
static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
{
struct access_data ad = { NULL, };
pseudo_t old, new, one;
int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
@@ -1035,28 +1147,43 @@
if (!linearize_address_gen(ep, expr->unop, &ad))
return VOID;
old = linearize_load_gen(ep, &ad);
- one = value_pseudo(expr->ctype, expr->op_value);
- new = add_binary_op(ep, expr->ctype, op, old, one);
+ op = opcode_float(op, expr->ctype);
+ if (is_float_type(expr->ctype))
+ one = add_setfval(ep, expr->ctype, expr->op_value);
+ else
+ one = value_pseudo(expr->op_value);
+ if (ad.btype != ad.type)
+ old = cast_pseudo(ep, old, ad.type, ad.btype);
+ new = add_binary_op(ep, ad.btype, op, old, one);
+ if (ad.btype != ad.type)
+ new = cast_pseudo(ep, new, ad.btype, ad.type);
linearize_store_gen(ep, new, &ad);
- finish_address_gen(ep, &ad);
return postop ? old : new;
}
-static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src)
+static pseudo_t add_unop(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t src)
{
- struct instruction *insn = alloc_typed_instruction(op, expr->ctype);
+ struct instruction *insn = alloc_typed_instruction(op, ctype);
pseudo_t new = alloc_pseudo(insn);
insn->target = new;
use_pseudo(insn, src, &insn->src1);
add_one_insn(ep, insn);
return new;
}
+static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to,
+ struct symbol *from, int op, pseudo_t src)
+{
+ pseudo_t new = add_unop(ep, to, op, src);
+ new->def->orig_type = from;
+ return new;
+}
+
static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
{
pseudo_t pre = linearize_expression(ep, expr->base);
struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
pseudo_t new = alloc_pseudo(insn);
@@ -1070,21 +1197,22 @@
}
static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
{
pseudo_t pre = linearize_expression(ep, expr->unop);
+ struct symbol *ctype = expr->ctype;
switch (expr->op) {
case '+':
return pre;
case '!': {
- pseudo_t zero = value_pseudo(expr->ctype, 0);
- return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero);
+ pseudo_t zero = value_pseudo(0);
+ return add_binary_op(ep, ctype, OP_SET_EQ, pre, zero);
}
case '~':
- return add_uniop(ep, expr, OP_NOT, pre);
+ return add_unop(ep, ctype, OP_NOT, pre);
case '-':
- return add_uniop(ep, expr, OP_NEG, pre);
+ return add_unop(ep, ctype, opcode_float(OP_NEG, ctype), pre);
}
return VOID;
}
static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
@@ -1110,53 +1238,178 @@
* Casts to pointers are "less safe" than other casts, since
* they imply type-unsafe accesses. "void *" is a special
* case, since you can't access through it anyway without another
* cast.
*/
-static struct instruction *alloc_cast_instruction(struct symbol *src, struct symbol *ctype)
+enum mtype {
+ MTYPE_UINT,
+ MTYPE_SINT,
+ MTYPE_PTR,
+ MTYPE_VPTR, // TODO: must be removed ?
+ MTYPE_FLOAT,
+ MTYPE_BAD,
+};
+
+static enum mtype get_mtype(struct symbol *s)
{
- int opcode = OP_CAST;
- struct symbol *base = ctype;
+ int sign = (s->ctype.modifiers & MOD_SIGNED) ? 1 : 0;
- if (src->ctype.modifiers & MOD_SIGNED)
- opcode = OP_SCAST;
- if (base->type == SYM_NODE)
- base = base->ctype.base_type;
- if (base->type == SYM_PTR) {
- base = base->ctype.base_type;
- if (base != &void_ctype)
- opcode = OP_PTRCAST;
- } else if (base->ctype.base_type == &fp_type)
- opcode = OP_FPCAST;
- return alloc_typed_instruction(opcode, ctype);
+retry: switch (s->type) {
+ case SYM_NODE:
+ s = s->ctype.base_type;
+ goto retry;
+ case SYM_PTR:
+ if (s->ctype.base_type == &void_ctype)
+ return MTYPE_VPTR;
+ return MTYPE_PTR;
+ case SYM_BITFIELD:
+ case SYM_RESTRICT:
+ case SYM_FOULED:
+ case SYM_ENUM:
+ s = s->ctype.base_type;
+ /* fall-through */
+ case_int:
+ return sign ? MTYPE_SINT : MTYPE_UINT;
+ case SYM_BASETYPE:
+ if (s->ctype.base_type == &fp_type)
+ return MTYPE_FLOAT;
+ if (s->ctype.base_type == &int_type)
+ goto case_int;
+ /* fall-through */
+ default:
+ return MTYPE_BAD;
+ }
}
+static int get_cast_opcode(struct symbol *dst, struct symbol *src)
+{
+ enum mtype stype = get_mtype(src);
+ enum mtype dtype = get_mtype(dst);
+
+ switch (dtype) {
+ case MTYPE_FLOAT:
+ switch (stype) {
+ case MTYPE_FLOAT:
+ if (dst->bit_size == src->bit_size)
+ return OP_NOP;
+ return OP_FCVTF;
+ case MTYPE_UINT:
+ return OP_UCVTF;
+ case MTYPE_SINT:
+ return OP_SCVTF;
+ default:
+ return OP_BADOP;
+ }
+ case MTYPE_PTR:
+ switch (stype) {
+ case MTYPE_UINT:
+ case MTYPE_SINT:
+ return OP_UTPTR;
+ case MTYPE_PTR:
+ case MTYPE_VPTR:
+ return OP_PTRCAST;
+ default:
+ return OP_BADOP;
+ }
+ case MTYPE_VPTR:
+ switch (stype) {
+ case MTYPE_PTR:
+ case MTYPE_VPTR:
+ case MTYPE_UINT:
+ stype = MTYPE_UINT;
+ /* fall through */
+ case MTYPE_SINT:
+ break;
+ default:
+ return OP_BADOP;
+ }
+ /* fall through */
+ case MTYPE_UINT:
+ case MTYPE_SINT:
+ switch (stype) {
+ case MTYPE_FLOAT:
+ return dtype == MTYPE_UINT ? OP_FCVTU : OP_FCVTS;
+ case MTYPE_PTR:
+ return OP_PTRTU;
+ case MTYPE_VPTR:
+ case MTYPE_UINT:
+ case MTYPE_SINT:
+ if (dst->bit_size ==src->bit_size)
+ return OP_NOP;
+ if (dst->bit_size < src->bit_size)
+ return OP_TRUNC;
+ return stype == MTYPE_SINT ? OP_SEXT : OP_ZEXT;
+ default:
+ return OP_BADOP;
+ }
+ /* fall through */
+ default:
+ if (src->type == SYM_NODE)
+ src = src->ctype.base_type;
+ if (dst->type == SYM_NODE)
+ dst = dst->ctype.base_type;
+ if (src == dst)
+ return OP_NOP;
+ return OP_BADOP;
+ }
+}
+
static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
{
+ const struct position pos = current_pos;
pseudo_t result;
struct instruction *insn;
+ int opcode;
if (src == VOID)
return VOID;
if (!from || !to)
return VOID;
if (from->bit_size < 0 || to->bit_size < 0)
return VOID;
- insn = alloc_cast_instruction(from, to);
+ opcode = get_cast_opcode(to, from);
+ switch (opcode) {
+ case OP_NOP:
+ return src;
+ case OP_UTPTR:
+ if (from->bit_size == to->bit_size)
+ break;
+ if (src == value_pseudo(0))
+ break;
+ if (Wint_to_pointer_cast)
+ warning(pos, "non size-preserving integer to pointer cast");
+ src = cast_pseudo(ep, src, from, size_t_ctype);
+ from = size_t_ctype;
+ break;
+ case OP_PTRTU:
+ if (from->bit_size == to->bit_size)
+ break;
+ if (Wpointer_to_int_cast)
+ warning(pos, "non size-preserving pointer to integer cast");
+ src = cast_pseudo(ep, src, from, size_t_ctype);
+ return cast_pseudo(ep, src, size_t_ctype, to);
+ case OP_BADOP:
+ return VOID;
+ default:
+ break;
+ }
+ insn = alloc_typed_instruction(opcode, to);
result = alloc_pseudo(insn);
insn->target = result;
insn->orig_type = from;
use_pseudo(insn, src, &insn->src);
add_one_insn(ep, insn);
return result;
}
-static int opcode_sign(int opcode, struct symbol *ctype)
+static int map_opcode(int opcode, struct symbol *ctype)
{
+ if (ctype && is_float_type(ctype))
+ return opcode_table[opcode].to_float;
if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
switch(opcode) {
- case OP_MULU: case OP_DIVU: case OP_MODU: case OP_LSR:
+ case OP_DIVU: case OP_MODU: case OP_LSR:
opcode++;
}
}
return opcode;
}
@@ -1164,14 +1417,23 @@
static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
{
pseudo_t zero;
int op;
+ if (!type || src == VOID)
+ return VOID;
if (is_bool_type(type))
return src;
- zero = value_pseudo(type, 0);
+ if (src->type == PSEUDO_VAL && (src->value == 0 || src->value == 1))
+ return src;
+ if (is_float_type(type)) {
+ zero = add_setfval(ep, type, 0.0);
+ op = map_opcode(OP_SET_NE, type);
+ } else {
+ zero = value_pseudo(0);
op = OP_SET_NE;
+ }
return add_binary_op(ep, &bool_ctype, op, src, zero);
}
static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
{
@@ -1196,11 +1458,11 @@
pseudo_t oldvalue = linearize_load_gen(ep, &ad);
pseudo_t dst;
static const int op_trans[] = {
[SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
[SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
- [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MULU,
+ [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
[SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
[SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
[SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
[SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
[SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
@@ -1212,16 +1474,16 @@
if (!src)
return VOID;
ctype = src->ctype;
oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
- opcode = opcode_sign(op_trans[expr->op - SPECIAL_BASE], ctype);
+ opcode = map_opcode(op_trans[expr->op - SPECIAL_BASE], ctype);
dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
+ taint_undefined_behaviour(dst->def);
value = cast_pseudo(ep, dst, ctype, expr->ctype);
}
value = linearize_store_gen(ep, value, &ad);
- finish_address_gen(ep, &ad);
return value;
}
static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
{
@@ -1230,39 +1492,29 @@
pseudo_t retval, call;
struct ctype *ctype = NULL;
struct symbol *fntype;
struct context *context;
- if (!expr->ctype) {
- warning(expr->pos, "call with no type!");
+ if (!expr->ctype)
return VOID;
- }
- FOR_EACH_PTR(expr->args, arg) {
- pseudo_t new = linearize_expression(ep, arg);
- use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
- } END_FOR_EACH_PTR(arg);
-
fn = expr->fn;
-
- if (fn->ctype)
- ctype = &fn->ctype->ctype;
-
fntype = fn->ctype;
- if (fntype) {
+ ctype = &fntype->ctype;
if (fntype->type == SYM_NODE)
fntype = fntype->ctype.base_type;
- }
- insn->fntype = fntype;
- if (fn->type == EXPR_PREOP) {
- if (fn->unop->type == EXPR_SYMBOL) {
- struct symbol *sym = fn->unop->symbol;
- if (sym->ctype.base_type->type == SYM_FN)
+ add_symbol(&insn->fntypes, fntype);
+ FOR_EACH_PTR(expr->args, arg) {
+ pseudo_t new = linearize_expression(ep, arg);
+ use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
+ add_symbol(&insn->fntypes, arg->ctype);
+ } END_FOR_EACH_PTR(arg);
+
+ if (fn->type == EXPR_PREOP && fn->op == '*' && is_func_type(fn->ctype))
fn = fn->unop;
- }
- }
+
if (fn->type == EXPR_SYMBOL) {
call = symbol_pseudo(ep, fn->symbol);
} else {
call = linearize_expression(ep, fn);
}
@@ -1302,11 +1554,11 @@
}
static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
{
pseudo_t src1, src2, dst;
- int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR_BOOL : OP_AND_BOOL;
+ int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR : OP_AND;
src1 = linearize_expression_to_bool(ep, expr->left);
src2 = linearize_expression_to_bool(ep, expr->right);
dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
if (expr->ctype != &bool_ctype)
@@ -1317,44 +1569,45 @@
static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
{
pseudo_t src1, src2, dst;
static const int opcode[] = {
['+'] = OP_ADD, ['-'] = OP_SUB,
- ['*'] = OP_MULU, ['/'] = OP_DIVU,
+ ['*'] = OP_MUL, ['/'] = OP_DIVU,
['%'] = OP_MODU, ['&'] = OP_AND,
['|'] = OP_OR, ['^'] = OP_XOR,
[SPECIAL_LEFTSHIFT] = OP_SHL,
[SPECIAL_RIGHTSHIFT] = OP_LSR,
};
int op;
src1 = linearize_expression(ep, expr->left);
src2 = linearize_expression(ep, expr->right);
- op = opcode_sign(opcode[expr->op], expr->ctype);
+ op = map_opcode(opcode[expr->op], expr->ctype);
dst = add_binary_op(ep, expr->ctype, op, src1, src2);
+ taint_undefined_behaviour(dst->def);
return dst;
}
static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
-pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
+static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
{
- pseudo_t cond, true, false, res;
+ pseudo_t cond, valt, valf, res;
struct instruction *insn;
- true = linearize_expression(ep, expr->cond_true);
- false = linearize_expression(ep, expr->cond_false);
+ valt = linearize_expression(ep, expr->cond_true);
+ valf = linearize_expression(ep, expr->cond_false);
cond = linearize_expression(ep, expr->conditional);
insn = alloc_typed_instruction(OP_SEL, expr->ctype);
if (!expr->cond_true)
- true = cond;
+ valt = cond;
use_pseudo(insn, cond, &insn->src1);
- use_pseudo(insn, true, &insn->src2);
- use_pseudo(insn, false, &insn->src3);
+ use_pseudo(insn, valt, &insn->src2);
+ use_pseudo(insn, valf, &insn->src3);
res = alloc_pseudo(insn);
insn->target = res;
add_one_insn(ep, insn);
return res;
@@ -1383,25 +1636,26 @@
struct expression *cond,
struct expression *expr_false)
{
pseudo_t src1, src2;
struct basic_block *bb_false;
- struct basic_block *merge = alloc_basic_block(ep, expr->pos);
+ struct basic_block *merge;
pseudo_t phi1, phi2;
- int size = type_size(expr->ctype);
if (!expr_false || !ep->active)
return VOID;
bb_false = alloc_basic_block(ep, expr_false->pos);
+ merge = alloc_basic_block(ep, expr->pos);
+
src1 = linearize_expression(ep, cond);
- phi1 = alloc_phi(ep->active, src1, size);
- add_branch(ep, expr, src1, merge, bb_false);
+ phi1 = alloc_phi(ep->active, src1, expr->ctype);
+ add_branch(ep, src1, merge, bb_false);
set_activeblock(ep, bb_false);
src2 = linearize_expression(ep, expr_false);
- phi2 = alloc_phi(ep->active, src2, size);
+ phi2 = alloc_phi(ep->active, src2, expr->ctype);
set_activeblock(ep, merge);
return add_join_conditional(ep, expr, phi1, phi2);
}
@@ -1411,11 +1665,10 @@
struct expression *expr_false)
{
pseudo_t src1, src2;
pseudo_t phi1, phi2;
struct basic_block *bb_true, *bb_false, *merge;
- int size = type_size(expr->ctype);
if (!cond || !expr_true || !expr_false || !ep->active)
return VOID;
bb_true = alloc_basic_block(ep, expr_true->pos);
bb_false = alloc_basic_block(ep, expr_false->pos);
@@ -1423,30 +1676,69 @@
linearize_cond_branch(ep, cond, bb_true, bb_false);
set_activeblock(ep, bb_true);
src1 = linearize_expression(ep, expr_true);
- phi1 = alloc_phi(ep->active, src1, size);
+ phi1 = alloc_phi(ep->active, src1, expr->ctype);
add_goto(ep, merge);
set_activeblock(ep, bb_false);
src2 = linearize_expression(ep, expr_false);
- phi2 = alloc_phi(ep->active, src2, size);
+ phi2 = alloc_phi(ep->active, src2, expr->ctype);
set_activeblock(ep, merge);
return add_join_conditional(ep, expr, phi1, phi2);
}
+static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *ctype,
+ struct instruction *node)
+{
+ struct basic_block *parent;
+
+ FOR_EACH_PTR(bb->parents, parent) {
+ struct instruction *br = delete_last_instruction(&parent->insns);
+ pseudo_t phi = alloc_phi(parent, src, ctype);
+ add_instruction(&parent->insns, br);
+ use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
+ } END_FOR_EACH_PTR(parent);
+}
+
static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
{
- struct expression *shortcut;
+ struct symbol *ctype = expr->ctype;
+ struct basic_block *other, *merge;
+ struct instruction *node;
+ pseudo_t src1, src2, phi2;
- shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
- shortcut->ctype = expr->ctype;
- if (expr->op == SPECIAL_LOGICAL_OR)
- return linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
- return linearize_conditional(ep, expr, expr->left, expr->right, shortcut);
+ if (!ep->active || !expr->left || !expr->right)
+ return VOID;
+
+ other = alloc_basic_block(ep, expr->right->pos);
+ merge = alloc_basic_block(ep, expr->pos);
+ node = alloc_phi_node(merge, ctype, NULL);
+
+ // LHS and its shortcut
+ if (expr->op == SPECIAL_LOGICAL_OR) {
+ linearize_cond_branch(ep, expr->left, merge, other);
+ src1 = value_pseudo(1);
+ } else {
+ linearize_cond_branch(ep, expr->left, other, merge);
+ src1 = value_pseudo(0);
+ }
+ insert_phis(merge, src1, ctype, node);
+
+ // RHS
+ set_activeblock(ep, other);
+ src2 = linearize_expression_to_bool(ep, expr->right);
+ src2 = cast_pseudo(ep, src2, &bool_ctype, ctype);
+ phi2 = alloc_phi(ep->active, src2, ctype);
+ use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2));
+
+ // join
+ set_activeblock(ep, merge);
+ add_instruction(&merge->insns, node);
+ return node->target;
}
static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
{
static const int cmpop[] = {
@@ -1458,19 +1750,19 @@
[SPECIAL_UNSIGNED_LT] = OP_SET_B,
[SPECIAL_UNSIGNED_GT] = OP_SET_A,
[SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
[SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
};
-
+ int op = opcode_float(cmpop[expr->op], expr->right->ctype);
pseudo_t src1 = linearize_expression(ep, expr->left);
pseudo_t src2 = linearize_expression(ep, expr->right);
- pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
+ pseudo_t dst = add_binary_op(ep, expr->ctype, op, src1, src2);
return dst;
}
-pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
+static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
{
pseudo_t cond;
if (!expr || !bb_reachable(ep->active))
return VOID;
@@ -1490,20 +1782,20 @@
linearize_logical_branch(ep, expr, bb_true, bb_false);
return VOID;
case EXPR_COMPARE:
cond = linearize_compare(ep, expr);
- add_branch(ep, expr, cond, bb_true, bb_false);
+ add_branch(ep, cond, bb_true, bb_false);
break;
case EXPR_PREOP:
if (expr->op == '!')
return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
/* fall through */
default: {
- cond = linearize_expression(ep, expr);
- add_branch(ep, expr, cond, bb_true, bb_false);
+ cond = linearize_expression_to_bool(ep, expr);
+ add_branch(ep, cond, bb_true, bb_false);
return VOID;
}
}
return VOID;
@@ -1534,20 +1826,10 @@
src = linearize_expression(ep, orig);
return cast_pseudo(ep, src, orig->ctype, expr->ctype);
}
-static pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
-{
- struct expression *init_expr = pos->init_expr;
-
- ad->offset = pos->init_offset;
- ad->source_type = base_type(init_expr->ctype);
- ad->result_type = init_expr->ctype;
- return linearize_initializer(ep, init_expr, ad);
-}
-
static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
{
switch (initializer->type) {
case EXPR_INITIALIZER: {
struct expression *expr;
@@ -1555,16 +1837,16 @@
linearize_initializer(ep, expr, ad);
} END_FOR_EACH_PTR(expr);
break;
}
case EXPR_POS:
- linearize_position(ep, initializer, ad);
+ ad->offset = initializer->init_offset;
+ linearize_initializer(ep, initializer->init_expr, ad);
break;
default: {
pseudo_t value = linearize_expression(ep, initializer);
- ad->source_type = base_type(initializer->ctype);
- ad->result_type = initializer->ctype;
+ ad->type = initializer->ctype;
linearize_store_gen(ep, value, ad);
return value;
}
}
@@ -1573,18 +1855,16 @@
static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
{
struct access_data ad = { NULL, };
- ad.source_type = arg;
- ad.result_type = arg;
+ ad.type = arg;
ad.address = symbol_pseudo(ep, arg);
linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
- finish_address_gen(ep, &ad);
}
-pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
+static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
{
if (!expr)
return VOID;
current_pos = expr->pos;
@@ -1592,15 +1872,19 @@
case EXPR_SYMBOL:
linearize_one_symbol(ep, expr->symbol);
return add_symbol_address(ep, expr->symbol);
case EXPR_VALUE:
- return value_pseudo(expr->ctype, expr->value);
+ return value_pseudo(expr->value);
- case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
+ case EXPR_STRING:
+ case EXPR_LABEL:
return add_setval(ep, expr->ctype, expr);
+ case EXPR_FVALUE:
+ return add_setfval(ep, expr->ctype, expr->fvalue);
+
case EXPR_STATEMENT:
return linearize_statement(ep, expr->statement);
case EXPR_CALL:
return linearize_call_expression(ep, expr);
@@ -1677,49 +1961,66 @@
// default zero initialization [6.7.9.21]
// FIXME: this init the whole aggregate while
// only the existing fields need to be initialized.
// FIXME: this init the whole aggregate even if
// all fields arelater explicitely initialized.
- struct expression *expr = sym->initializer;
- ad.pos = expr->pos;
- ad.result_type = sym;
- ad.source_type = base_type(sym);
+ ad.type = sym;
ad.address = symbol_pseudo(ep, sym);
- linearize_store_gen(ep, value_pseudo(sym, 0), &ad);
+ linearize_store_gen(ep, value_pseudo(0), &ad);
}
value = linearize_initializer(ep, sym->initializer, &ad);
- finish_address_gen(ep, &ad);
return value;
}
static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
{
pseudo_t pseudo;
struct statement *s;
- struct symbol *ret = stmt->ret;
pseudo = VOID;
FOR_EACH_PTR(stmt->stmts, s) {
pseudo = linearize_statement(ep, s);
} END_FOR_EACH_PTR(s);
- if (ret) {
- struct basic_block *bb = add_label(ep, ret);
+ return pseudo;
+}
+
+static void add_return(struct entrypoint *ep, struct basic_block *bb, struct symbol *ctype, pseudo_t src)
+{
struct instruction *phi_node = first_instruction(bb->insns);
+ pseudo_t phi;
+ if (!phi_node) {
+ phi_node = alloc_typed_instruction(OP_PHI, ctype);
+ phi_node->target = alloc_pseudo(phi_node);
+ phi_node->bb = bb;
+ add_instruction(&bb->insns, phi_node);
+ }
+ phi = alloc_phi(ep->active, src, ctype);
+ phi->ident = &return_ident;
+ use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
+}
- if (!phi_node)
- return pseudo;
+static pseudo_t linearize_fn_statement(struct entrypoint *ep, struct statement *stmt)
+{
+ struct instruction *phi_node;
+ struct basic_block *bb;
+ pseudo_t pseudo;
- if (pseudo_list_size(phi_node->phi_list)==1) {
- pseudo = first_pseudo(phi_node->phi_list);
- assert(pseudo->type == PSEUDO_PHI);
- return pseudo->def->src1;
+ pseudo = linearize_compound_statement(ep, stmt);
+ if (!is_void_type(stmt->ret)) { // non-void function
+ struct basic_block *active = ep->active;
+ if (active && !bb_terminated(active)) { // missing return
+ struct basic_block *bb_ret;
+ bb_ret = get_bound_block(ep, stmt->ret);
+ add_return(ep, bb_ret, stmt->ret, undef_pseudo());
}
- return phi_node->target;
}
-
+ bb = add_label(ep, stmt->ret);
+ phi_node = first_instruction(bb->insns);
+ if (phi_node)
+ pseudo = phi_node->target;
return pseudo;
}
static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
{
@@ -1732,33 +2033,31 @@
struct symbol *sym;
concat_symbol_list(args->declaration, &ep->syms);
FOR_EACH_PTR(args->declaration, sym) {
pseudo_t value = linearize_one_symbol(ep, sym);
- use_pseudo(insn, value, add_pseudo(&insn->arguments, value));
+ add_pseudo(&insn->arguments, value);
} END_FOR_EACH_PTR(sym);
}
- insn->target = pseudo = linearize_compound_statement(ep, stmt);
+ pseudo = linearize_fn_statement(ep, stmt);
+ insn->target = pseudo;
+
use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
bb = ep->active;
- if (bb && !bb->insns)
+ if (!bb->insns)
bb->pos = stmt->pos;
add_one_insn(ep, insn);
return pseudo;
}
static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
{
struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
struct expression *expr = stmt->expression;
- int value = 0;
- if (expr->type == EXPR_VALUE)
- value = expr->value;
-
- insn->increment = value;
+ insn->increment = get_expression_value(expr);
insn->context_expr = stmt->context;
add_one_insn(ep, insn);
return VOID;
}
@@ -1796,26 +2095,23 @@
struct asm_constraint *rule;
if (!expr || !linearize_address_gen(ep, expr, &ad))
return;
linearize_store_gen(ep, pseudo, &ad);
- finish_address_gen(ep, &ad);
rule = __alloc_asm_constraint(0);
rule->ident = ident;
rule->constraint = constraint;
use_pseudo(insn, pseudo, &rule->pseudo);
add_ptr_list(&insn->asm_rules->outputs, rule);
}
static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
{
- int state;
struct expression *expr;
struct instruction *insn;
struct asm_rules *rules;
const char *constraint;
- struct ident *ident;
insn = alloc_instruction(OP_ASM, 0);
expr = stmt->asm_string;
if (!expr || expr->type != EXPR_STRING) {
warning(stmt->pos, "expected string in inline asm");
@@ -1825,53 +2121,21 @@
rules = __alloc_asm_rules(0);
insn->asm_rules = rules;
/* Gather the inputs.. */
- state = 0;
- ident = NULL;
- constraint = NULL;
FOR_EACH_PTR(stmt->asm_inputs, expr) {
- switch (state) {
- case 0: /* Identifier */
- state = 1;
- ident = (struct ident *)expr;
- continue;
-
- case 1: /* Constraint */
- state = 2;
- constraint = expr ? expr->string->data : "";
- continue;
-
- case 2: /* Expression */
- state = 0;
- add_asm_input(ep, insn, expr, constraint, ident);
- }
+ constraint = expr->constraint ? expr->constraint->string->data : "";
+ add_asm_input(ep, insn, expr->expr, constraint, expr->name);
} END_FOR_EACH_PTR(expr);
add_one_insn(ep, insn);
/* Assign the outputs */
- state = 0;
- ident = NULL;
- constraint = NULL;
FOR_EACH_PTR(stmt->asm_outputs, expr) {
- switch (state) {
- case 0: /* Identifier */
- state = 1;
- ident = (struct ident *)expr;
- continue;
-
- case 1: /* Constraint */
- state = 2;
- constraint = expr ? expr->string->data : "";
- continue;
-
- case 2:
- state = 0;
- add_asm_output(ep, insn, expr, constraint, ident);
- }
+ constraint = expr->constraint ? expr->constraint->string->data : "";
+ add_asm_output(ep, insn, expr->expr, constraint, expr->name);
} END_FOR_EACH_PTR(expr);
return VOID;
}
@@ -1914,27 +2178,18 @@
}
static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
{
struct expression *expr = stmt->expression;
- struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target);
+ struct symbol *ret = stmt->ret_target;
+ struct basic_block *bb_return = get_bound_block(ep, ret);
struct basic_block *active;
pseudo_t src = linearize_expression(ep, expr);
active = ep->active;
- if (active && src != VOID) {
- struct instruction *phi_node = first_instruction(bb_return->insns);
- pseudo_t phi;
- if (!phi_node) {
- phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
- phi_node->target = alloc_pseudo(phi_node);
- phi_node->bb = bb_return;
- add_instruction(&bb_return->insns, phi_node);
+ if (active && !is_void_type(ret)) {
+ add_return(ep, bb_return, ret, src);
}
- phi = alloc_phi(active, src, type_size(expr->ctype));
- phi->ident = &return_ident;
- use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
- }
add_goto(ep, bb_return);
return VOID;
}
static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
@@ -1941,20 +2196,24 @@
{
struct symbol *sym;
struct instruction *switch_ins;
struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
struct basic_block *active, *default_case;
+ struct expression *expr = stmt->switch_expression;
struct multijmp *jmp;
pseudo_t pseudo;
- pseudo = linearize_expression(ep, stmt->switch_expression);
-
- active = ep->active;
- if (!bb_reachable(active))
+ if (!expr || !expr->ctype)
return VOID;
+ pseudo = linearize_expression(ep, expr);
+ active = ep->active;
+ if (!active) {
+ active = alloc_basic_block(ep, stmt->pos);
+ set_activeblock(ep, active);
+ }
- switch_ins = alloc_instruction(OP_SWITCH, 0);
+ switch_ins = alloc_typed_instruction(OP_SWITCH, expr->ctype);
use_pseudo(switch_ins, pseudo, &switch_ins->cond);
add_one_insn(ep, switch_ins);
finish_block(ep);
default_case = NULL;
@@ -1963,16 +2222,19 @@
struct basic_block *bb_case = get_bound_block(ep, sym);
if (!case_stmt->case_expression) {
default_case = bb_case;
continue;
+ } else if (case_stmt->case_expression->type != EXPR_VALUE) {
+ continue;
} else {
- int begin, end;
+ struct expression *case_to = case_stmt->case_to;
+ long long begin, end;
begin = end = case_stmt->case_expression->value;
- if (case_stmt->case_to)
- end = case_stmt->case_to->value;
+ if (case_to && case_to->type == EXPR_VALUE)
+ end = case_to->value;
if (begin > end)
jmp = alloc_multijmp(bb_case, end, begin);
else
jmp = alloc_multijmp(bb_case, begin, end);
@@ -2045,11 +2307,11 @@
set_activeblock(ep, loop_end);
return VOID;
}
-pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
+static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
{
struct basic_block *bb;
if (!stmt)
return VOID;
@@ -2122,11 +2384,11 @@
break;
}
pseudo = linearize_expression(ep, expr);
goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
- use_pseudo(goto_ins, pseudo, &goto_ins->target);
+ use_pseudo(goto_ins, pseudo, &goto_ins->src);
add_one_insn(ep, goto_ins);
FOR_EACH_PTR(stmt->target_list, sym) {
struct basic_block *bb_computed = get_bound_block(ep, sym);
struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
@@ -2182,27 +2444,34 @@
return VOID;
}
static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
{
+ struct statement *stmt = base_type->stmt;
struct entrypoint *ep;
struct basic_block *bb;
+ struct symbol *ret_type;
struct symbol *arg;
struct instruction *entry;
+ struct instruction *ret;
pseudo_t result;
int i;
- if (!base_type->stmt)
+ if (!stmt)
return NULL;
ep = alloc_entrypoint();
- bb = alloc_basic_block(ep, sym->pos);
-
ep->name = sym;
sym->ep = ep;
+ bb = alloc_basic_block(ep, sym->pos);
set_activeblock(ep, bb);
+ if (stmt->type == STMT_ASM) { // top-level asm
+ linearize_asm_statement(ep, stmt);
+ return ep;
+ }
+
entry = alloc_instruction(OP_ENTRY, 0);
add_one_insn(ep, entry);
ep->entry = entry;
concat_symbol_list(base_type->arguments, &ep->syms);
@@ -2211,72 +2480,19 @@
i = 0;
FOR_EACH_PTR(base_type->arguments, arg) {
linearize_argument(ep, arg, ++i);
} END_FOR_EACH_PTR(arg);
- result = linearize_statement(ep, base_type->stmt);
- if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
- struct symbol *ret_type = base_type->ctype.base_type;
- struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
-
+ result = linearize_fn_statement(ep, stmt);
+ ret_type = base_type->ctype.base_type;
+ ret = alloc_typed_instruction(OP_RET, ret_type);
if (type_size(ret_type) > 0)
- use_pseudo(insn, result, &insn->src);
- add_one_insn(ep, insn);
- }
+ use_pseudo(ret, result, &ret->src);
+ add_one_insn(ep, ret);
- if (fdump_linearize) {
- if (fdump_linearize == 2)
+ optimize(ep);
return ep;
- show_entry(ep);
- }
-
- /*
- * Do trivial flow simplification - branches to
- * branches, kill dead basicblocks etc
- */
- kill_unreachable_bbs(ep);
-
- /*
- * Turn symbols into pseudos
- */
- simplify_symbol_usage(ep);
-
-repeat:
- /*
- * Remove trivial instructions, and try to CSE
- * the rest.
- */
- do {
- cleanup_and_cse(ep);
- pack_basic_blocks(ep);
- } while (repeat_phase & REPEAT_CSE);
-
- kill_unreachable_bbs(ep);
- vrfy_flow(ep);
-
- /* Cleanup */
- clear_symbol_pseudos(ep);
-
- /* And track pseudo register usage */
- track_pseudo_liveness(ep);
-
- /*
- * Some flow optimizations can only effectively
- * be done when we've done liveness analysis. But
- * if they trigger, we need to start all over
- * again
- */
- if (simplify_flow(ep)) {
- clear_liveness(ep);
- goto repeat;
- }
-
- /* Finally, add deathnotes to pseudos now that we have them */
- if (dbg_dead)
- track_pseudo_death(ep);
-
- return ep;
}
struct entrypoint *linearize_symbol(struct symbol *sym)
{
struct symbol *base_type;