diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | flow.c | 783 | ||||
| -rw-r--r-- | flow.h | 8 | ||||
| -rw-r--r-- | lib.h | 4 | ||||
| -rw-r--r-- | linearize.c | 776 | ||||
| -rw-r--r-- | linearize.h | 4 |
6 files changed, 806 insertions, 774 deletions
@@ -9,11 +9,11 @@ PREFIX=$(HOME) PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \ - linearize.h bitmap.h ident-list.h compat.h + linearize.h bitmap.h ident-list.h compat.h flow.h LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \ expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \ - sort.o compat-$(OS).o + sort.o flow.o compat-$(OS).o LIB_FILE= sparse.a LIBS=$(LIB_FILE) @@ -71,6 +71,7 @@ show-parse.o: $(LIB_H) symbol.o: $(LIB_H) expand.o: $(LIB_H) linearize.o: $(LIB_H) +flow.o: $(LIB_H) sort.o: $(LIB_H) inline.o: $(LIB_H) target.o: $(LIB_H) @@ -0,0 +1,783 @@ +/* + * Flow - walk the linearized flowgraph, simplifying it as we + * go along. + * + * Copyright (C) 2004 Linus Torvalds + */ + +#include <string.h> +#include <stdarg.h> +#include <stdlib.h> +#include <stdio.h> +#include <stddef.h> + +#include "parse.h" +#include "expression.h" +#include "linearize.h" + +static unsigned long bb_generation; + +/* + * Dammit, if we have a phi-node followed by a conditional + * branch on that phi-node, we should damn well be able to + * do something about the source. Maybe. + */ +static void rewrite_branch(struct basic_block *bb, + struct basic_block **ptr, + struct basic_block *old, + struct basic_block *new) +{ + struct basic_block *tmp; + + if (*ptr != old) + return; + + *ptr = new; + FOR_EACH_PTR(new->parents, tmp) { + if (tmp == old) + *THIS_ADDRESS(tmp) = bb; + } END_FOR_EACH_PTR(tmp); + + FOR_EACH_PTR(bb->children, tmp) { + if (tmp == old) + *THIS_ADDRESS(tmp) = new; + } END_FOR_EACH_PTR(tmp); +} + +/* + * Return the known truth value of a pseudo, or -1 if + * it's not known. + */ +static int pseudo_truth_value(pseudo_t pseudo) +{ + switch (pseudo->type) { + case PSEUDO_VAL: + return !!pseudo->value; + + case PSEUDO_REG: { + struct instruction *insn = pseudo->def; + if (insn->opcode == OP_SETVAL && insn->target == pseudo) { + struct expression *expr = insn->val; + + /* A symbol address is always considered true.. */ + if (!expr) + return 1; + if (expr->type == EXPR_VALUE) + return !!expr->value; + } + } + /* Fall through */ + default: + return -1; + } +} + + +static void try_to_simplify_bb(struct entrypoint *ep, struct basic_block *bb, + struct instruction *first, struct instruction *second) +{ + struct phi *phi; + + FOR_EACH_PTR(first->phi_list, phi) { + struct basic_block *source = phi->source, *target; + pseudo_t pseudo = phi->pseudo; + struct instruction *br; + int true; + + if (!pseudo || !source) + continue; + br = last_instruction(source->insns); + if (!br) + continue; + if (br->opcode != OP_BR) + continue; + + true = pseudo_truth_value(pseudo); + if (true < 0) + continue; + target = true ? second->bb_true : second->bb_false; + rewrite_branch(source, &br->bb_true, bb, target); + rewrite_branch(source, &br->bb_false, bb, target); + } END_FOR_EACH_PTR(phi); +} + +static inline int linearize_insn_list(struct instruction_list *list, struct instruction **arr, int nr) +{ + return linearize_ptr_list((struct ptr_list *)list, (void **)arr, nr); +} + +void simplify_phi_nodes(struct entrypoint *ep) +{ + struct basic_block *bb; + + FOR_EACH_PTR(ep->bbs, bb) { + struct instruction *insns[2], *first, *second; + + if (linearize_insn_list(bb->insns, insns, 2) < 2) + continue; + + first = insns[0]; + second = insns[1]; + + if (first->opcode != OP_PHI) + continue; + if (second->opcode != OP_BR) + continue; + if (first->target != second->cond) + continue; + try_to_simplify_bb(ep, bb, first, second); + } END_FOR_EACH_PTR(bb); +} + +static inline void concat_user_list(struct pseudo_ptr_list *src, struct pseudo_ptr_list **dst) +{ + concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst); +} + +static void convert_load_insn(struct instruction *insn, pseudo_t src) +{ + pseudo_t target, *usep; + + /* + * Go through the "insn->users" list and replace them all.. + */ + target = insn->target; + FOR_EACH_PTR(target->users, usep) { + *usep = src; + } END_FOR_EACH_PTR(usep); + concat_user_list(target->users, &src->users); + + /* Turn the load into a no-op */ + insn->opcode = OP_LNOP; +} + +static int overlapping_memop(struct instruction *a, struct instruction *b) +{ + unsigned int a_start = (a->offset << 3) + a->type->bit_offset; + unsigned int b_start = (b->offset << 3) + b->type->bit_offset; + unsigned int a_size = a->type->bit_size; + unsigned int b_size = b->type->bit_size; + + if (a_size + a_start <= b_start) + return 0; + if (b_size + b_start <= a_start) + return 0; + return 1; +} + +static inline int same_memop(struct instruction *a, struct instruction *b) +{ + return a->offset == b->offset && + a->type->bit_size == b->type->bit_size && + a->type->bit_offset == b->type->bit_offset; +} + +/* + * Return 1 if "one" dominates the access to 'pseudo' + * in insn. + * + * Return 0 if it doesn't, and -1 if you don't know. + */ +static int dominates(pseudo_t pseudo, struct instruction *insn, + struct instruction *one, int local) +{ + int opcode = one->opcode; + + if (opcode == OP_CALL) + return local ? 0 : -1; + if (opcode != OP_LOAD && opcode != OP_STORE) + return 0; + if (one->src != pseudo) { + if (local) + return 0; + /* We don't think two explicitly different symbols ever alias */ + if (one->src->type == PSEUDO_SYM) + return 0; + /* We could try to do some alias analysis here */ + return -1; + } + if (!same_memop(insn, one)) { + if (one->opcode == OP_LOAD) + return 0; + if (!overlapping_memop(insn, one)) + return 0; + return -1; + } + return 1; +} + +static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn, + struct basic_block *bb, unsigned long generation, struct phi_list **dominators, + int local, int loads) +{ + struct basic_block *parent; + + if (bb_list_size(bb->parents) > 1) + loads = 0; + FOR_EACH_PTR(bb->parents, parent) { + struct instruction *one; + struct phi *phi; + + FOR_EACH_PTR_REVERSE(parent->insns, one) { + int dominance; + if (one == insn) + goto no_dominance; + dominance = dominates(pseudo, insn, one, local); + if (dominance < 0) { + if (one->opcode == OP_LOAD) + continue; + return 0; + } + if (!dominance) + continue; + if (one->opcode == OP_LOAD && !loads) + continue; + goto found_dominator; + } END_FOR_EACH_PTR_REVERSE(one); +no_dominance: + if (parent->generation == generation) + continue; + parent->generation = generation; + + if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads)) + return 0; + continue; + +found_dominator: + phi = alloc_phi(parent, one->target); + add_phi(dominators, phi); + } END_FOR_EACH_PTR(parent); + return 1; +} + +/* + * We should probably sort the phi list just to make it easier to compare + * later for equality. + */ +static void rewrite_load_instruction(struct instruction *insn, struct phi_list *dominators) +{ + struct phi *phi, *first; + pseudo_t new; + + first = NULL; + FOR_EACH_PTR(dominators, phi) { + if (!first) { + first = phi; + continue; + } + if (first->pseudo == phi->pseudo && + first->source == phi->source) { + phi->source = NULL; + continue; + } + goto complex_phi; + } END_FOR_EACH_PTR(phi); + + first->source = NULL; /* Mark it as not used */ + convert_load_insn(insn, first->pseudo); + return; + +complex_phi: + new = alloc_pseudo(insn); + convert_load_insn(insn, new); + + /* + * FIXME! This is dubious. We should probably allocate a new + * instruction instead of re-using the OP_LOAD instruction. + * Re-use of the instruction makes the usage list suspect. + * + * It should be ok, because the only usage of the OP_LOAD + * is the symbol pseudo, and we should never follow that + * list _except_ for exactly the dominant instruction list + * generation (and then we always check the opcode). + */ + insn->opcode = OP_PHI; + insn->target = new; + insn->phi_list = dominators; + new->def = insn; +} + +static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn, + unsigned long generation, int local) +{ + struct basic_block *bb = insn->bb; + struct instruction *one, *dom = NULL; + struct phi_list *dominators; + int partial; + + /* Unreachable load? Undo it */ + if (!bb) { + insn->opcode = OP_LNOP; + return 1; + } + + partial = 0; + FOR_EACH_PTR(bb->insns, one) { + int dominance; + if (one == insn) + goto found; + dominance = dominates(pseudo, insn, one, local); + if (dominance < 0) { + /* Ignore partial load dominators */ + if (one->opcode == OP_LOAD) + continue; + dom = NULL; + partial = 1; + continue; + } + if (!dominance) + continue; + dom = one; + partial = 0; + } END_FOR_EACH_PTR(one); + /* Whaa? */ + warning(pseudo->sym->pos, "unable to find symbol read"); + return 0; +found: + if (partial) + return 0; + + if (dom) { + if (dom->opcode == OP_LOAD) + find_dominating_stores(pseudo, dom, ++bb_generation, local); + convert_load_insn(insn, dom->target); + return 1; + } + + /* Ok, go find the parents */ + bb->generation = generation; + + dominators = NULL; + if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1)) + return 0; + + /* This happens with initial assignments to structures etc.. */ + if (!dominators) { + if (!local) + return 0; + convert_load_insn(insn, value_pseudo(0)); + return 1; + } + + /* + * If we find just one dominating instruction, we + * can turn it into a direct thing. Otherwise we'll + * have to turn the load into a phi-node of the + * dominators. + */ + rewrite_load_instruction(insn, dominators); + return 1; +} + +/* Kill a pseudo that is dead on exit from the bb */ +static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local) +{ + struct instruction *insn; + struct basic_block *parent; + + if (bb->generation == generation) + return; + bb->generation = generation; + FOR_EACH_PTR_REVERSE(bb->insns, insn) { + int opcode = insn->opcode; + + if (opcode != OP_LOAD && opcode != OP_STORE) { + if (local) + continue; + if (opcode == OP_CALL) + return; + continue; + } + if (insn->src == pseudo) { + if (opcode == OP_LOAD) + return; + insn->opcode = OP_SNOP; + continue; + } + if (local) + continue; + if (insn->src->type != PSEUDO_SYM) + return; + } END_FOR_EACH_PTR_REVERSE(insn); + + FOR_EACH_PTR(bb->parents, parent) { + struct basic_block *child; + FOR_EACH_PTR(parent->children, child) { + if (child && child != bb) + return; + } END_FOR_EACH_PTR(child); + kill_dead_stores(pseudo, generation, parent, local); + } END_FOR_EACH_PTR(parent); +} + +/* + * This should see if the "insn" trivially dominates some previous store, and kill the + * store if unnecessary. + */ +static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn, + unsigned long generation, struct basic_block *bb, int local, int found) +{ + struct instruction *one; + struct basic_block *parent; + + if (bb->generation == generation) + return; + bb->generation = generation; + FOR_EACH_PTR_REVERSE(bb->insns, one) { + int dominance; + if (!found) { + if (one != insn) + continue; + found = 1; + continue; + } + dominance = dominates(pseudo, insn, one, local); + if (!dominance) + continue; + if (dominance < 0) + return; + if (one->opcode == OP_LOAD) + return; + one->opcode = OP_SNOP; + } END_FOR_EACH_PTR_REVERSE(one); + + if (!found) { + warning(bb->pos, "Unable to find instruction"); + return; + } + + FOR_EACH_PTR(bb->parents, parent) { + struct basic_block *child; + FOR_EACH_PTR(parent->children, child) { + if (child && child != bb) + return; + } END_FOR_EACH_PTR(child); + kill_dominated_stores(pseudo, insn, generation, parent, local, found); + } END_FOR_EACH_PTR(parent); +} + +static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) +{ + pseudo_t pseudo, src, *pp; + struct instruction *def; + unsigned long mod; + int all; + + /* Never used as a symbol? */ + pseudo = sym->pseudo; + if (!pseudo) + return; + + /* We don't do coverage analysis of volatiles.. */ + if (sym->ctype.modifiers & MOD_VOLATILE) + return; + + /* ..and symbols with external visibility need more care */ + mod = sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE); + if (mod) + goto external_visibility; + + def = NULL; + FOR_EACH_PTR(pseudo->users, pp) { + /* We know that the symbol-pseudo use is the "src" in the instruction */ + struct instruction *insn = container(pp, struct instruction, src); + + switch (insn->opcode) { + case OP_STORE: + if (def) + goto multi_def; + def = insn; + break; + case OP_LOAD: + break; + default: + warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); + } + if (insn->offset) + goto complex_def; + } END_FOR_EACH_PTR(pp); + + /* + * Goodie, we have a single store (if even that) in the whole + * thing. Replace all loads with moves from the pseudo, + * replace the store with a def. + */ + src = VOID; + if (def) { + src = def->target; + + /* Turn the store into a no-op */ + def->opcode = OP_SNOP; + } + FOR_EACH_PTR(pseudo->users, pp) { + struct instruction *insn = container(pp, struct instruction, src); + if (insn->opcode == OP_LOAD) + convert_load_insn(insn, src); + } END_FOR_EACH_PTR(pp); + return; + +multi_def: +complex_def: +external_visibility: + all = 1; + FOR_EACH_PTR_REVERSE(pseudo->users, pp) { + struct instruction *insn = container(pp, struct instruction, src); + if (insn->opcode == OP_LOAD) + all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod); + } END_FOR_EACH_PTR_REVERSE(pp); + + /* If we converted all the loads, remove the stores. They are dead */ + if (all && !mod) { + FOR_EACH_PTR(pseudo->users, pp) { + struct instruction *insn = container(pp, struct instruction, src); + if (insn->opcode == OP_STORE) + insn->opcode = OP_SNOP; + } END_FOR_EACH_PTR(pp); + } else { + /* + * If we couldn't take the shortcut, see if we can at least kill some + * of them.. + */ + FOR_EACH_PTR(pseudo->users, pp) { + struct instruction *insn = container(pp, struct instruction, src); + if (insn->opcode == OP_STORE) + kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0); + } END_FOR_EACH_PTR(pp); + + if (!(mod & (MOD_EXTERN | MOD_STATIC))) { + struct basic_block *bb; + FOR_EACH_PTR(ep->bbs, bb) { + if (!bb->children) + kill_dead_stores(pseudo, ++bb_generation, bb, !mod); + } END_FOR_EACH_PTR(bb); + } + } + + return; +} + +void simplify_symbol_usage(struct entrypoint *ep) +{ + struct symbol *sym; + + FOR_EACH_PTR(ep->accesses, sym) { + simplify_one_symbol(ep, sym); + sym->pseudo = NULL; + } END_FOR_EACH_PTR(sym); +} + +static void mark_bb_reachable(struct basic_block *bb, unsigned long generation) +{ + struct basic_block *child; + + if (bb->generation == generation) + return; + bb->generation = generation; + FOR_EACH_PTR(bb->children, child) { + mark_bb_reachable(child, generation); + } END_FOR_EACH_PTR(child); +} + +static void kill_bb(struct basic_block *bb) +{ + bb->insns = NULL; + bb->children = NULL; + bb->parents = NULL; +} + +static void kill_unreachable_bbs(struct entrypoint *ep) +{ + struct basic_block *bb; + unsigned long generation = ++bb_generation; + + mark_bb_reachable(ep->entry, generation); + FOR_EACH_PTR(ep->bbs, bb) { + struct phi *phi; + if (bb->generation == generation) + continue; + FOR_EACH_PTR(bb->phinodes, phi) { + phi->pseudo = VOID; + phi->source = NULL; + } END_FOR_EACH_PTR(phi); + + /* Mark it as being dead */ + kill_bb(bb); + } END_FOR_EACH_PTR(bb); +} + +static void try_to_replace(struct basic_block *bb, struct basic_block **target, + struct basic_block *old, struct basic_block *new) +{ + if (*target == old) { + *target = new; + /* FIXME!! Fix child information */ + warning(bb->pos, "changed child from %p to %p", old, new); + } +} + +static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new) +{ + struct instruction *insn = last_instruction(bb->insns); + + if (!insn) + return 0; + switch (insn->opcode) { + case OP_BR: + rewrite_branch(bb, &insn->bb_true, old, new); + rewrite_branch(bb, &insn->bb_false, old, new); + return 1; + case OP_SWITCH: { + struct multijmp *jmp; + FOR_EACH_PTR(insn->multijmp_list, jmp) { + rewrite_branch(bb, &jmp->target, old, new); + } END_FOR_EACH_PTR(jmp); + return 1; + } + default: + return 0; + } +} + +static int rewrite_branch_bb(struct basic_block *bb, struct instruction *br) +{ + int success; + struct basic_block *parent; + struct basic_block *target = br->bb_true; + struct basic_block *false = br->bb_false; + + if (target && false) { + pseudo_t cond = br->cond; + if (cond->type != PSEUDO_VAL) + return 0; + target = cond->value ? target : false; + } + + success = 1; + target = target ? : false; + FOR_EACH_PTR(bb->parents, parent) { + if (!rewrite_parent_branch(parent, bb, target)) + success = 0; + } END_FOR_EACH_PTR(parent); + return success; +} + +/* + * FIXME! This knows _way_ too much about list internals + */ +static void set_list(struct basic_block_list *p, struct basic_block *child) +{ + struct ptr_list *list = (void *)p; + list->prev = list; + list->next = list; + list->nr = 1; + list->list[0] = child; +} + +static void simplify_one_switch(struct basic_block *bb, + long long val, + struct multijmp_list *list, + struct instruction *p) +{ + struct multijmp *jmp; + + FOR_EACH_PTR(list, jmp) { + /* Default case */ + if (jmp->begin > jmp->end) + goto found; + if (val >= jmp->begin && val <= jmp->end) + goto found; + } END_FOR_EACH_PTR(jmp); + warning(bb->pos, "Impossible case statement"); + return; + +found: + p->opcode = OP_BR; + p->cond = NULL; + p->bb_false = NULL; + p->bb_true = jmp->target; + set_list(bb->children, jmp->target); +} + +static void simplify_switch(struct entrypoint *ep) +{ + struct instruction *insn; + + FOR_EACH_PTR(ep->switches, insn) { + pseudo_t pseudo = insn->target; + if (pseudo->type == PSEUDO_VAL) + simplify_one_switch(insn->bb, pseudo->value, insn->multijmp_list, insn); + } END_FOR_EACH_PTR(insn); +} + +void pack_basic_blocks(struct entrypoint *ep) +{ + struct basic_block *bb; + + simplify_switch(ep); + + kill_unreachable_bbs(ep); + + /* See if we can merge a bb into another one.. */ + FOR_EACH_PTR(ep->bbs, bb) { + struct instruction *first; + struct basic_block *parent, *child; + + if (!bb_reachable(bb)) + continue; + /* + * If this block has a phi-node associated with it, + */ + if (bb->phinodes) + continue; + + /* + * Just a branch? + */ + first = first_instruction(bb->insns); + if (first && first->opcode == OP_BR) { + if (rewrite_branch_bb(bb, first)) { + kill_bb(bb); + continue; + } + } + + if (ep->entry == bb) + continue; + + /* + * See if we only have one parent.. + */ + if (bb_list_size(bb->parents) != 1) + continue; + parent = first_basic_block(bb->parents); + if (parent == bb) + continue; + + /* + * Goodie. See if the parent can merge.. + */ + FOR_EACH_PTR(parent->children, child) { + if (child != bb) + goto no_merge; + } END_FOR_EACH_PTR(child); + + parent->children = bb->children; + FOR_EACH_PTR(bb->children, child) { + struct basic_block *p; + FOR_EACH_PTR(child->parents, p) { + if (p != bb) + continue; + *THIS_ADDRESS(p) = parent; + } END_FOR_EACH_PTR(p); + } END_FOR_EACH_PTR(child); + + delete_last_instruction(&parent->insns); + concat_instruction_list(bb->insns, &parent->insns); + kill_bb(bb); + + no_merge: + /* nothing to do */; + } END_FOR_EACH_PTR(bb); +} + + @@ -0,0 +1,8 @@ +#ifndef FLOW_H +#define FLOW_H + +extern void simplify_symbol_usage(struct entrypoint *ep); +extern void simplify_phi_nodes(struct entrypoint *ep); +extern void pack_basic_blocks(struct entrypoint *ep); + +#endif @@ -2,6 +2,7 @@ #define LIB_H #include <stdlib.h> +#include <stddef.h> /* * Basic helper routine descriptions for 'sparse'. @@ -15,6 +16,9 @@ #include "compat.h" +#define container(ptr, type, member) \ + (type *)((void *)(ptr) - offsetof(type, member)) + extern unsigned int hexval(unsigned int c); struct position { diff --git a/linearize.c b/linearize.c index ac4f8fa7..e0232dfd 100644 --- a/linearize.c +++ b/linearize.c @@ -14,11 +14,11 @@ #include <stdarg.h> #include <stdlib.h> #include <stdio.h> -#include <stddef.h> #include "parse.h" #include "expression.h" #include "linearize.h" +#include "flow.h" pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt); pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr); @@ -33,8 +33,6 @@ pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initial struct pseudo void_pseudo = {}; -unsigned long bb_generation; - static struct instruction *alloc_instruction(int opcode, struct symbol *type) { struct instruction * insn = __alloc_instruction(0); @@ -45,7 +43,6 @@ static struct instruction *alloc_instruction(int opcode, struct symbol *type) static struct entrypoint *alloc_entrypoint(void) { - bb_generation = 0; return __alloc_entrypoint(0); } @@ -78,7 +75,7 @@ static inline void use_pseudo(pseudo_t p, pseudo_t *pp) add_pseudo_ptr(pp, &p->users); } -static struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo) +struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo) { struct phi *phi = __alloc_phi(0); phi->source = source; @@ -386,9 +383,6 @@ static void show_bb(struct basic_block *bb) printf("\n"); } -#define container(ptr, type, member) \ - (type *)((void *)(ptr) - offsetof(type, member)) - static void show_symbol_usage(pseudo_t pseudo) { if (pseudo) { @@ -539,7 +533,7 @@ static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t } /* Dummy pseudo allocator */ -static pseudo_t alloc_pseudo(struct instruction *def) +pseudo_t alloc_pseudo(struct instruction *def) { static int nr = 0; struct pseudo * pseudo = __alloc_pseudo(0); @@ -565,7 +559,7 @@ static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym) return pseudo; } -static pseudo_t value_pseudo(long long val) +pseudo_t value_pseudo(long long val) { #define MAX_VAL_HASH 64 static struct pseudo_list *prev[MAX_VAL_HASH]; @@ -1585,768 +1579,6 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt) return VOID; } -/* - * Dammit, if we have a phi-node followed by a conditional - * branch on that phi-node, we should damn well be able to - * do something about the source. Maybe. - */ -static void rewrite_branch(struct basic_block *bb, - struct basic_block **ptr, - struct basic_block *old, - struct basic_block *new) -{ - struct basic_block *tmp; - - if (*ptr != old) - return; - - *ptr = new; - FOR_EACH_PTR(new->parents, tmp) { - if (tmp == old) - *THIS_ADDRESS(tmp) = bb; - } END_FOR_EACH_PTR(tmp); - - FOR_EACH_PTR(bb->children, tmp) { - if (tmp == old) - *THIS_ADDRESS(tmp) = new; - } END_FOR_EACH_PTR(tmp); -} - -/* - * Return the known truth value of a pseudo, or -1 if - * it's not known. - */ -static int pseudo_truth_value(pseudo_t pseudo) -{ - switch (pseudo->type) { - case PSEUDO_VAL: - return !!pseudo->value; - - case PSEUDO_REG: { - struct instruction *insn = pseudo->def; - if (insn->opcode == OP_SETVAL && insn->target == pseudo) { - struct expression *expr = insn->val; - - /* A symbol address is always considered true.. */ - if (!expr) - return 1; - if (expr->type == EXPR_VALUE) - return !!expr->value; - } - } - /* Fall through */ - default: - return -1; - } -} - - -static void try_to_simplify_bb(struct entrypoint *ep, struct basic_block *bb, - struct instruction *first, struct instruction *second) -{ - struct phi *phi; - - FOR_EACH_PTR(first->phi_list, phi) { - struct basic_block *source = phi->source, *target; - pseudo_t pseudo = phi->pseudo; - struct instruction *br; - int true; - - if (!pseudo || !source) - continue; - br = last_instruction(source->insns); - if (!br) - continue; - if (br->opcode != OP_BR) - continue; - - true = pseudo_truth_value(pseudo); - if (true < 0) - continue; - target = true ? second->bb_true : second->bb_false; - rewrite_branch(source, &br->bb_true, bb, target); - rewrite_branch(source, &br->bb_false, bb, target); - } END_FOR_EACH_PTR(phi); -} - -static inline int linearize_insn_list(struct instruction_list *list, struct instruction **arr, int nr) -{ - return linearize_ptr_list((struct ptr_list *)list, (void **)arr, nr); -} - -static void simplify_phi_nodes(struct entrypoint *ep) -{ - struct basic_block *bb; - - FOR_EACH_PTR(ep->bbs, bb) { - struct instruction *insns[2], *first, *second; - - if (linearize_insn_list(bb->insns, insns, 2) < 2) - continue; - - first = insns[0]; - second = insns[1]; - - if (first->opcode != OP_PHI) - continue; - if (second->opcode != OP_BR) - continue; - if (first->target != second->cond) - continue; - try_to_simplify_bb(ep, bb, first, second); - } END_FOR_EACH_PTR(bb); -} - -static inline void concat_user_list(struct pseudo_ptr_list *src, struct pseudo_ptr_list **dst) -{ - concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst); -} - -static void convert_load_insn(struct instruction *insn, pseudo_t src) -{ - pseudo_t target, *usep; - - /* - * Go through the "insn->users" list and replace them all.. - */ - target = insn->target; - FOR_EACH_PTR(target->users, usep) { - *usep = src; - } END_FOR_EACH_PTR(usep); - concat_user_list(target->users, &src->users); - - /* Turn the load into a no-op */ - insn->opcode = OP_LNOP; -} - -static int overlapping_memop(struct instruction *a, struct instruction *b) -{ - unsigned int a_start = (a->offset << 3) + a->type->bit_offset; - unsigned int b_start = (b->offset << 3) + b->type->bit_offset; - unsigned int a_size = a->type->bit_size; - unsigned int b_size = b->type->bit_size; - - if (a_size + a_start <= b_start) - return 0; - if (b_size + b_start <= a_start) - return 0; - return 1; -} - -static inline int same_memop(struct instruction *a, struct instruction *b) -{ - return a->offset == b->offset && - a->type->bit_size == b->type->bit_size && - a->type->bit_offset == b->type->bit_offset; -} - -/* - * Return 1 if "one" dominates the access to 'pseudo' - * in insn. - * - * Return 0 if it doesn't, and -1 if you don't know. - */ -static int dominates(pseudo_t pseudo, struct instruction *insn, - struct instruction *one, int local) -{ - int opcode = one->opcode; - - if (opcode == OP_CALL) - return local ? 0 : -1; - if (opcode != OP_LOAD && opcode != OP_STORE) - return 0; - if (one->src != pseudo) { - if (local) - return 0; - /* We don't think two explicitly different symbols ever alias */ - if (one->src->type == PSEUDO_SYM) - return 0; - /* We could try to do some alias analysis here */ - return -1; - } - if (!same_memop(insn, one)) { - if (one->opcode == OP_LOAD) - return 0; - if (!overlapping_memop(insn, one)) - return 0; - return -1; - } - return 1; -} - -static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn, - struct basic_block *bb, unsigned long generation, struct phi_list **dominators, - int local, int loads) -{ - struct basic_block *parent; - - if (bb_list_size(bb->parents) > 1) - loads = 0; - FOR_EACH_PTR(bb->parents, parent) { - struct instruction *one; - struct phi *phi; - - FOR_EACH_PTR_REVERSE(parent->insns, one) { - int dominance; - if (one == insn) - goto no_dominance; - dominance = dominates(pseudo, insn, one, local); - if (dominance < 0) { - if (one->opcode == OP_LOAD) - continue; - return 0; - } - if (!dominance) - continue; - if (one->opcode == OP_LOAD && !loads) - continue; - goto found_dominator; - } END_FOR_EACH_PTR_REVERSE(one); -no_dominance: - if (parent->generation == generation) - continue; - parent->generation = generation; - - if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads)) - return 0; - continue; - -found_dominator: - phi = alloc_phi(parent, one->target); - add_phi(dominators, phi); - } END_FOR_EACH_PTR(parent); - return 1; -} - -/* - * We should probably sort the phi list just to make it easier to compare - * later for equality. - */ -static void rewrite_load_instruction(struct instruction *insn, struct phi_list *dominators) -{ - struct phi *phi, *first; - pseudo_t new; - - first = NULL; - FOR_EACH_PTR(dominators, phi) { - if (!first) { - first = phi; - continue; - } - if (first->pseudo == phi->pseudo && - first->source == phi->source) { - phi->source = NULL; - continue; - } - goto complex_phi; - } END_FOR_EACH_PTR(phi); - - first->source = NULL; /* Mark it as not used */ - convert_load_insn(insn, first->pseudo); - return; - -complex_phi: - new = alloc_pseudo(insn); - convert_load_insn(insn, new); - - /* - * FIXME! This is dubious. We should probably allocate a new - * instruction instead of re-using the OP_LOAD instruction. - * Re-use of the instruction makes the usage list suspect. - * - * It should be ok, because the only usage of the OP_LOAD - * is the symbol pseudo, and we should never follow that - * list _except_ for exactly the dominant instruction list - * generation (and then we always check the opcode). - */ - insn->opcode = OP_PHI; - insn->target = new; - insn->phi_list = dominators; - new->def = insn; -} - -static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn, - unsigned long generation, int local) -{ - struct basic_block *bb = insn->bb; - struct instruction *one, *dom = NULL; - struct phi_list *dominators; - int partial; - - /* Unreachable load? Undo it */ - if (!bb) { - insn->opcode = OP_LNOP; - return 1; - } - - partial = 0; - FOR_EACH_PTR(bb->insns, one) { - int dominance; - if (one == insn) - goto found; - dominance = dominates(pseudo, insn, one, local); - if (dominance < 0) { - /* Ignore partial load dominators */ - if (one->opcode == OP_LOAD) - continue; - dom = NULL; - partial = 1; - continue; - } - if (!dominance) - continue; - dom = one; - partial = 0; - } END_FOR_EACH_PTR(one); - /* Whaa? */ - warning(pseudo->sym->pos, "unable to find symbol read"); - return 0; -found: - if (partial) - return 0; - - if (dom) { - if (dom->opcode == OP_LOAD) - find_dominating_stores(pseudo, dom, ++bb_generation, local); - convert_load_insn(insn, dom->target); - return 1; - } - - /* Ok, go find the parents */ - bb->generation = generation; - - dominators = NULL; - if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1)) - return 0; - - /* This happens with initial assignments to structures etc.. */ - if (!dominators) { - if (!local) - return 0; - convert_load_insn(insn, value_pseudo(0)); - return 1; - } - - /* - * If we find just one dominating instruction, we - * can turn it into a direct thing. Otherwise we'll - * have to turn the load into a phi-node of the - * dominators. - */ - rewrite_load_instruction(insn, dominators); - return 1; -} - -/* Kill a pseudo that is dead on exit from the bb */ -static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local) -{ - struct instruction *insn; - struct basic_block *parent; - - if (bb->generation == generation) - return; - bb->generation = generation; - FOR_EACH_PTR_REVERSE(bb->insns, insn) { - int opcode = insn->opcode; - - if (opcode != OP_LOAD && opcode != OP_STORE) { - if (local) - continue; - if (opcode == OP_CALL) - return; - continue; - } - if (insn->src == pseudo) { - if (opcode == OP_LOAD) - return; - insn->opcode = OP_SNOP; - continue; - } - if (local) - continue; - if (insn->src->type != PSEUDO_SYM) - return; - } END_FOR_EACH_PTR_REVERSE(insn); - - FOR_EACH_PTR(bb->parents, parent) { - struct basic_block *child; - FOR_EACH_PTR(parent->children, child) { - if (child && child != bb) - return; - } END_FOR_EACH_PTR(child); - kill_dead_stores(pseudo, generation, parent, local); - } END_FOR_EACH_PTR(parent); -} - -/* - * This should see if the "insn" trivially dominates some previous store, and kill the - * store if unnecessary. - */ -static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn, - unsigned long generation, struct basic_block *bb, int local, int found) -{ - struct instruction *one; - struct basic_block *parent; - - if (bb->generation == generation) - return; - bb->generation = generation; - FOR_EACH_PTR_REVERSE(bb->insns, one) { - int dominance; - if (!found) { - if (one != insn) - continue; - found = 1; - continue; - } - dominance = dominates(pseudo, insn, one, local); - if (!dominance) - continue; - if (dominance < 0) - return; - if (one->opcode == OP_LOAD) - return; - one->opcode = OP_SNOP; - } END_FOR_EACH_PTR_REVERSE(one); - - if (!found) { - warning(bb->pos, "Unable to find instruction"); - return; - } - - FOR_EACH_PTR(bb->parents, parent) { - struct basic_block *child; - FOR_EACH_PTR(parent->children, child) { - if (child && child != bb) - return; - } END_FOR_EACH_PTR(child); - kill_dominated_stores(pseudo, insn, generation, parent, local, found); - } END_FOR_EACH_PTR(parent); -} - -static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) -{ - pseudo_t pseudo, src, *pp; - struct instruction *def; - unsigned long mod; - int all; - - /* Never used as a symbol? */ - pseudo = sym->pseudo; - if (!pseudo) - return; - - /* We don't do coverage analysis of volatiles.. */ - if (sym->ctype.modifiers & MOD_VOLATILE) - return; - - /* ..and symbols with external visibility need more care */ - mod = sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE); - if (mod) - goto external_visibility; - - def = NULL; - FOR_EACH_PTR(pseudo->users, pp) { - /* We know that the symbol-pseudo use is the "src" in the instruction */ - struct instruction *insn = container(pp, struct instruction, src); - - switch (insn->opcode) { - case OP_STORE: - if (def) - goto multi_def; - def = insn; - break; - case OP_LOAD: - break; - default: - warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); - } - if (insn->offset) - goto complex_def; - } END_FOR_EACH_PTR(pp); - - /* - * Goodie, we have a single store (if even that) in the whole - * thing. Replace all loads with moves from the pseudo, - * replace the store with a def. - */ - src = VOID; - if (def) { - src = def->target; - - /* Turn the store into a no-op */ - def->opcode = OP_SNOP; - } - FOR_EACH_PTR(pseudo->users, pp) { - struct instruction *insn = container(pp, struct instruction, src); - if (insn->opcode == OP_LOAD) - convert_load_insn(insn, src); - } END_FOR_EACH_PTR(pp); - return; - -multi_def: -complex_def: -external_visibility: - all = 1; - FOR_EACH_PTR_REVERSE(pseudo->users, pp) { - struct instruction *insn = container(pp, struct instruction, src); - if (insn->opcode == OP_LOAD) - all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod); - } END_FOR_EACH_PTR_REVERSE(pp); - - /* If we converted all the loads, remove the stores. They are dead */ - if (all && !mod) { - FOR_EACH_PTR(pseudo->users, pp) { - struct instruction *insn = container(pp, struct instruction, src); - if (insn->opcode == OP_STORE) - insn->opcode = OP_SNOP; - } END_FOR_EACH_PTR(pp); - } else { - /* - * If we couldn't take the shortcut, see if we can at least kill some - * of them.. - */ - FOR_EACH_PTR(pseudo->users, pp) { - struct instruction *insn = container(pp, struct instruction, src); - if (insn->opcode == OP_STORE) - kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0); - } END_FOR_EACH_PTR(pp); - - if (!(mod & (MOD_EXTERN | MOD_STATIC))) { - struct basic_block *bb; - FOR_EACH_PTR(ep->bbs, bb) { - if (!bb->children) - kill_dead_stores(pseudo, ++bb_generation, bb, !mod); - } END_FOR_EACH_PTR(bb); - } - } - - return; -} - -static void simplify_symbol_usage(struct entrypoint *ep) -{ - struct symbol *sym; - FOR_EACH_PTR(ep->accesses, sym) { - simplify_one_symbol(ep, sym); - sym->pseudo = NULL; - } END_FOR_EACH_PTR(sym); -} - -static void mark_bb_reachable(struct basic_block *bb, unsigned long generation) -{ - struct basic_block *child; - - if (bb->generation == generation) - return; - bb->generation = generation; - FOR_EACH_PTR(bb->children, child) { - mark_bb_reachable(child, generation); - } END_FOR_EACH_PTR(child); -} - -static void kill_bb(struct basic_block *bb) -{ - bb->insns = NULL; - bb->children = NULL; - bb->parents = NULL; -} - -static void kill_unreachable_bbs(struct entrypoint *ep) -{ - struct basic_block *bb; - unsigned long generation = ++bb_generation; - - mark_bb_reachable(ep->entry, generation); - FOR_EACH_PTR(ep->bbs, bb) { - struct phi *phi; - if (bb->generation == generation) - continue; - FOR_EACH_PTR(bb->phinodes, phi) { - phi->pseudo = VOID; - phi->source = NULL; - } END_FOR_EACH_PTR(phi); - - /* Mark it as being dead */ - kill_bb(bb); - } END_FOR_EACH_PTR(bb); -} - -static void try_to_replace(struct basic_block *bb, struct basic_block **target, - struct basic_block *old, struct basic_block *new) -{ - if (*target == old) { - *target = new; - /* FIXME!! Fix child information */ - warning(bb->pos, "changed child from %p to %p", old, new); - } -} - -static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new) -{ - struct instruction *insn = last_instruction(bb->insns); - - if (!insn) - return 0; - switch (insn->opcode) { - case OP_BR: - rewrite_branch(bb, &insn->bb_true, old, new); - rewrite_branch(bb, &insn->bb_false, old, new); - return 1; - case OP_SWITCH: { - struct multijmp *jmp; - FOR_EACH_PTR(insn->multijmp_list, jmp) { - rewrite_branch(bb, &jmp->target, old, new); - } END_FOR_EACH_PTR(jmp); - return 1; - } - default: - return 0; - } -} - -static int rewrite_branch_bb(struct basic_block *bb, struct instruction *br) -{ - int success; - struct basic_block *parent; - struct basic_block *target = br->bb_true; - struct basic_block *false = br->bb_false; - - if (target && false) { - pseudo_t cond = br->cond; - if (cond->type != PSEUDO_VAL) - return 0; - target = cond->value ? target : false; - } - - success = 1; - target = target ? : false; - FOR_EACH_PTR(bb->parents, parent) { - if (!rewrite_parent_branch(parent, bb, target)) - success = 0; - } END_FOR_EACH_PTR(parent); - return success; -} - -/* - * FIXME! This knows _way_ too much about list internals - */ -static void set_list(struct basic_block_list *p, struct basic_block *child) -{ - struct ptr_list *list = (void *)p; - list->prev = list; - list->next = list; - list->nr = 1; - list->list[0] = child; -} - -static void simplify_one_switch(struct basic_block *bb, - long long val, - struct multijmp_list *list, - struct instruction *p) -{ - struct multijmp *jmp; - - FOR_EACH_PTR(list, jmp) { - /* Default case */ - if (jmp->begin > jmp->end) - goto found; - if (val >= jmp->begin && val <= jmp->end) - goto found; - } END_FOR_EACH_PTR(jmp); - warning(bb->pos, "Impossible case statement"); - return; - -found: - p->opcode = OP_BR; - p->cond = NULL; - p->bb_false = NULL; - p->bb_true = jmp->target; - set_list(bb->children, jmp->target); -} - -static void simplify_switch(struct entrypoint *ep) -{ - struct instruction *insn; - - FOR_EACH_PTR(ep->switches, insn) { - pseudo_t pseudo = insn->target; - if (pseudo->type == PSEUDO_VAL) - simplify_one_switch(insn->bb, pseudo->value, insn->multijmp_list, insn); - } END_FOR_EACH_PTR(insn); -} - -static void pack_basic_blocks(struct entrypoint *ep) -{ - struct basic_block *bb; - - simplify_switch(ep); - - kill_unreachable_bbs(ep); - - /* See if we can merge a bb into another one.. */ - FOR_EACH_PTR(ep->bbs, bb) { - struct instruction *first; - struct basic_block *parent, *child; - - if (!bb_reachable(bb)) - continue; - /* - * If this block has a phi-node associated with it, - */ - if (bb->phinodes) - continue; - - /* - * Just a branch? - */ - first = first_instruction(bb->insns); - if (first && first->opcode == OP_BR) { - if (rewrite_branch_bb(bb, first)) { - kill_bb(bb); - continue; - } - } - - if (ep->entry == bb) - continue; - - /* - * See if we only have one parent.. - */ - if (bb_list_size(bb->parents) != 1) - continue; - parent = first_basic_block(bb->parents); - if (parent == bb) - continue; - - /* - * Goodie. See if the parent can merge.. - */ - FOR_EACH_PTR(parent->children, child) { - if (child != bb) - goto no_merge; - } END_FOR_EACH_PTR(child); - - parent->children = bb->children; - FOR_EACH_PTR(bb->children, child) { - struct basic_block *p; - FOR_EACH_PTR(child->parents, p) { - if (p != bb) - continue; - *THIS_ADDRESS(p) = parent; - } END_FOR_EACH_PTR(p); - } END_FOR_EACH_PTR(child); - - delete_last_instruction(&parent->insns); - concat_instruction_list(bb->insns, &parent->insns); - kill_bb(bb); - - no_merge: - /* nothing to do */; - } END_FOR_EACH_PTR(bb); -} - struct entrypoint *linearize_symbol(struct symbol *sym) { struct symbol *base_type; diff --git a/linearize.h b/linearize.h index 77723872..b6d8c6a6 100644 --- a/linearize.h +++ b/linearize.h @@ -233,6 +233,10 @@ struct entrypoint { struct basic_block *entry; }; +struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo); +pseudo_t alloc_pseudo(struct instruction *def); +pseudo_t value_pseudo(long long val); + struct entrypoint *linearize_symbol(struct symbol *sym); void show_entry(struct entrypoint *ep); |