/* * Copyright (C) 2004 Linus Torvalds */ /// // Flow simplification // ------------------- #include #include #include #include #include #include #include "parse.h" #include "expression.h" #include "linearize.h" #include "simplify.h" #include "flow.h" #include "target.h" unsigned long bb_generation; /// // remove phi-sources from a removed edge // // :note: It's possible to have several edges between the same BBs. // It's common with switches but it's also possible with branches. // This function will only remove a single phi-source per edge. int remove_phisources(struct basic_block *par, struct basic_block *old) { struct instruction *insn; int changed = 0; FOR_EACH_PTR(old->insns, insn) { pseudo_t phi; if (!insn->bb) continue; if (insn->opcode != OP_PHI) return changed; // found a phi-node in the target BB, // now look after its phi-sources. FOR_EACH_PTR(insn->phi_list, phi) { struct instruction *phisrc = phi->def; if (phi == VOID) continue; assert(phisrc->phi_node == insn); if (phisrc->bb != par) continue; // found a phi-source corresponding to this edge: // remove it but avoid the recursive killing. REPLACE_CURRENT_PTR(phi, VOID); remove_use(&phisrc->src); phisrc->bb = NULL; changed |= REPEAT_CSE; // Only the first one must be removed. goto next; } END_FOR_EACH_PTR(phi); next: ; } END_FOR_EACH_PTR(insn); return changed; } /// // remove all phisources but the one corresponding to the given target static int remove_other_phisources(struct basic_block *bb, struct multijmp_list *list, struct basic_block *target) { struct multijmp *jmp; int changed = 0; FOR_EACH_PTR(list, jmp) { if (jmp->target == target) { target = NULL; continue; } changed |= remove_phisources(bb, jmp->target); } END_FOR_EACH_PTR(jmp); return changed; } /* * 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 int rewrite_branch(struct basic_block *bb, struct basic_block **ptr, struct basic_block *old, struct basic_block *new) { if (*ptr != old || new == old || !bb->ep) return 0; /* We might find new if-conversions or non-dominating CSEs */ /* we may also create new dead cycles */ repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP; *ptr = new; replace_bb_in_list(&bb->children, old, new, 1); remove_bb_from_list(&old->parents, bb, 1); add_bb(&new->parents, bb); return 1; } /* * 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; /* A symbol address is always considered true.. */ if (insn->opcode == OP_SYMADDR && insn->target == pseudo) return 1; } /* Fall through */ default: return -1; } } /* * Does a basic block depend on the pseudos that "src" defines? */ static int bb_depends_on(struct basic_block *target, struct basic_block *src) { pseudo_t pseudo; FOR_EACH_PTR(src->defines, pseudo) { if (pseudo_in_list(target->needs, pseudo)) return 1; } END_FOR_EACH_PTR(pseudo); return 0; } /* * This really should be handled by bb_depends_on() * which efficiently check the dependence using the * defines - needs liveness info. Problem is that * there is no liveness done on OP_PHI & OP_PHISRC. * * This function add the missing dependency checks. */ static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src) { struct instruction *insn; FOR_EACH_PTR(src->insns, insn) { if (!insn->bb) continue; if (insn->opcode != OP_PHI) continue; if (pseudo_in_list(target->needs, insn->target)) return 1; } END_FOR_EACH_PTR(insn); return 0; } /// // does the BB contains ignorable instructions but a final branch? // :note: something could be done for phi-sources but ... we'll see. static bool bb_is_forwarder(struct basic_block *bb) { struct instruction *insn; FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; switch (insn->opcode) { case OP_NOP: case OP_INLINED_CALL: continue; case OP_CBR: case OP_BR: return true; default: goto out; } } END_FOR_EACH_PTR(insn); out: return false; } /// // check if the sources of a phi-node match with the parent BBs static bool phi_check(struct instruction *node) { struct basic_block *bb; pseudo_t phi; PREPARE_PTR_LIST(node->bb->parents, bb); FOR_EACH_PTR(node->phi_list, phi) { if (phi == VOID || !phi->def) continue; if (phi->def->bb != bb) return false; NEXT_PTR_LIST(bb); } END_FOR_EACH_PTR(phi); if (bb) return false; FINISH_PTR_LIST(bb); return true; } /* * When we reach here, we have: * - a basic block that ends in a conditional branch and * that has no side effects apart from the pseudos it * may change. * - the phi-node that the conditional branch depends on * - full pseudo liveness information * * We need to check if any of the _sources_ of the phi-node * may be constant, and not actually need this block at all. */ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second) { int changed = 0; pseudo_t phi; int bogus; /* * This a due to improper dominance tracking during * simplify_symbol_usage()/conversion to SSA form. * No sane simplification can be done when we have this. */ bogus = !phi_check(first); FOR_EACH_PTR(first->phi_list, phi) { struct instruction *def = phi->def; struct basic_block *source, *target; pseudo_t pseudo; struct instruction *br; int cond; if (!def) continue; source = def->bb; pseudo = def->src1; if (!pseudo || !source) continue; br = last_instruction(source->insns); if (!br) continue; if (br->opcode != OP_CBR && br->opcode != OP_BR) continue; cond = pseudo_truth_value(pseudo); if (cond < 0) continue; target = cond ? second->bb_true : second->bb_false; if (bb_depends_on(target, bb)) continue; if (bb_depends_on_phi(target, bb)) continue; changed |= rewrite_branch(source, &br->bb_true, bb, target); changed |= rewrite_branch(source, &br->bb_false, bb, target); if (changed && !bogus) kill_use(THIS_ADDRESS(phi)); } END_FOR_EACH_PTR(phi); return changed; } static int bb_has_side_effects(struct basic_block *bb) { struct instruction *insn; FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; switch (insn->opcode) { case OP_CALL: /* FIXME! This should take "const" etc into account */ return 1; case OP_LOAD: if (!insn->type) return 1; if (insn->is_volatile) return 1; continue; case OP_STORE: case OP_CONTEXT: return 1; case OP_ASM: /* FIXME! This should take "volatile" etc into account */ return 1; default: continue; } } END_FOR_EACH_PTR(insn); return 0; } static int simplify_phi_branch(struct basic_block *bb, struct instruction *br) { pseudo_t cond = br->cond; struct instruction *def; if (cond->type != PSEUDO_REG) return 0; def = cond->def; if (def->bb != bb || def->opcode != OP_PHI) return 0; if (bb_has_side_effects(bb)) return 0; return try_to_simplify_bb(bb, def, br); } static int simplify_branch_branch(struct basic_block *bb, struct instruction *br, struct basic_block **target_p, int bb_true) { struct basic_block *target = *target_p, *final; struct instruction *insn; int retval; if (target == bb) return 0; insn = last_instruction(target->insns); if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond) return 0; /* * Ahhah! We've found a branch to a branch on the same conditional! * Now we just need to see if we can rewrite the branch.. */ retval = 0; final = bb_true ? insn->bb_true : insn->bb_false; if (bb_has_side_effects(target)) goto try_to_rewrite_target; if (bb_depends_on(final, target)) goto try_to_rewrite_target; if (bb_depends_on_phi(final, target)) return 0; return rewrite_branch(bb, target_p, target, final); try_to_rewrite_target: /* * If we're the only parent, at least we can rewrite the * now-known second branch. */ if (bb_list_size(target->parents) != 1) return retval; convert_to_jump(insn, final); return 1; } static int simplify_one_branch(struct basic_block *bb, struct instruction *br) { if (simplify_phi_branch(bb, br)) return 1; return simplify_branch_branch(bb, br, &br->bb_true, 1) | simplify_branch_branch(bb, br, &br->bb_false, 0); } static int simplify_branch_nodes(struct entrypoint *ep) { int changed = 0; struct basic_block *bb; FOR_EACH_PTR(ep->bbs, bb) { struct instruction *br = last_instruction(bb->insns); if (!br || br->opcode != OP_CBR) continue; changed |= simplify_one_branch(bb, br); } END_FOR_EACH_PTR(bb); return changed; } /* * This is called late - when we have intra-bb liveness information.. */ int simplify_flow(struct entrypoint *ep) { return simplify_branch_nodes(ep); } static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst) { copy_ptr_list((struct ptr_list **)dst, (struct ptr_list *)src); } void convert_instruction_target(struct instruction *insn, pseudo_t src) { pseudo_t target; struct pseudo_user *pu; /* * Go through the "insn->users" list and replace them all.. */ target = insn->target; if (target == src) return; FOR_EACH_PTR(target->users, pu) { if (*pu->userp != VOID) { assert(*pu->userp == target); *pu->userp = src; } } END_FOR_EACH_PTR(pu); if (has_use_list(src)) concat_user_list(target->users, &src->users); target->users = NULL; } static int overlapping_memop(struct instruction *a, struct instruction *b) { unsigned int a_start = bytes_to_bits(a->offset); unsigned int b_start = bytes_to_bits(b->offset); unsigned int a_size = a->size; unsigned int b_size = b->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->size == b->size; } static inline int distinct_symbols(pseudo_t a, pseudo_t b) { if (a->type != PSEUDO_SYM) return 0; if (b->type != PSEUDO_SYM) return 0; return a->sym != b->sym; } /* * Return 1 if "dom" dominates the access to "pseudo" * in "insn". * * Return 0 if it doesn't, and -1 if you don't know. */ int dominates(struct instruction *insn, struct instruction *dom, int local) { switch (dom->opcode) { case OP_CALL: case OP_ENTRY: return local ? 0 : -1; case OP_LOAD: case OP_STORE: break; case OP_ASM: if (dom->clobber_memory) return -1; if (dom->output_memory) return -1; return 0; default: return 0; } if (dom->src != insn->src) { if (local) return 0; /* We don't think two explicitly different symbols ever alias */ if (distinct_symbols(insn->src, dom->src)) return 0; /* We could try to do some alias analysis here */ return -1; } if (!same_memop(insn, dom)) { if (!overlapping_memop(insn, dom)) return 0; return -1; } return 1; } /* Kill a pseudo that is dead on exit from the bb */ // The context is: // * the variable is not global but may have its address used (local/non-local) // * the stores are only needed by others functions which would do some // loads via the escaped address // We start by the terminating BB (normal exit BB + no-return/unreachable) // We walkup the BB' intruction backward // * we're only concerned by loads, stores & calls // * if we reach a call -> we have to stop if var is non-local // * if we reach a load of our var -> we have to stop // * if we reach a store of our var -> we can kill it, it's dead // * we can ignore other stores & loads if the var is local // * if we reach another store or load done via non-symbol access // (so done via some address calculation) -> we have to stop // If we reach the top of the BB we can recurse into the parents BBs. static void kill_dead_stores_bb(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) { if (!insn->bb) continue; switch (insn->opcode) { case OP_LOAD: if (insn->src == pseudo) return; break; case OP_STORE: if (insn->src == pseudo) { kill_instruction_force(insn); continue; } break; case OP_CALL: if (!local) return; default: continue; } if (!local && insn->src->type != PSEUDO_SYM) return; } END_FOR_EACH_PTR_REVERSE(insn); FOR_EACH_PTR(bb->parents, parent) { if (bb_list_size(parent->children) > 1) continue; kill_dead_stores_bb(pseudo, generation, parent, local); } END_FOR_EACH_PTR(parent); } void check_access(struct instruction *insn) { pseudo_t pseudo = insn->src; if (insn->bb && pseudo->type == PSEUDO_SYM) { int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size; struct symbol *sym = pseudo->sym; if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size)) { if (insn->tainted) return; warning(insn->pos, "invalid access %s '%s' (%d %d)", offset < 0 ? "below" : "past the end of", show_ident(sym->ident), offset, bits_to_bytes(sym->bit_size)); insn->tainted = 1; } } } static struct pseudo_user *first_user(pseudo_t p) { struct pseudo_user *pu; FOR_EACH_PTR(p->users, pu) { if (!pu) continue; return pu; } END_FOR_EACH_PTR(pu); return NULL; } void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local) { unsigned long generation; struct basic_block *bb; switch (pseudo_user_list_size(addr->users)) { case 0: return; case 1: if (local) { struct pseudo_user *pu = first_user(addr); struct instruction *insn = pu->insn; if (insn->opcode == OP_STORE) { kill_instruction_force(insn); return; } } default: break; } generation = ++bb_generation; FOR_EACH_PTR(ep->bbs, bb) { if (bb->children) continue; kill_dead_stores_bb(addr, generation, bb, local); } END_FOR_EACH_PTR(bb); } 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_defs(struct instruction *insn) { pseudo_t target = insn->target; if (!has_use_list(target)) return; if (target->def != insn) return; convert_instruction_target(insn, VOID); } void kill_bb(struct basic_block *bb) { struct instruction *insn; struct basic_block *child, *parent; FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; kill_instruction_force(insn); kill_defs(insn); /* * We kill unreachable instructions even if they * otherwise aren't "killable" (e.g. volatile loads) */ } END_FOR_EACH_PTR(insn); bb->insns = NULL; FOR_EACH_PTR(bb->children, child) { remove_bb_from_list(&child->parents, bb, 0); } END_FOR_EACH_PTR(child); bb->children = NULL; FOR_EACH_PTR(bb->parents, parent) { remove_bb_from_list(&parent->children, bb, 0); } END_FOR_EACH_PTR(parent); bb->parents = NULL; } void kill_unreachable_bbs(struct entrypoint *ep) { struct basic_block *bb; unsigned long generation = ++bb_generation; mark_bb_reachable(ep->entry->bb, generation); FOR_EACH_PTR(ep->bbs, bb) { if (bb->generation == generation) continue; /* Mark it as being dead */ kill_bb(bb); bb->ep = NULL; DELETE_CURRENT_PTR(bb); } END_FOR_EACH_PTR(bb); PACK_PTR_LIST(&ep->bbs); } static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new) { int changed = 0; struct instruction *insn = last_instruction(bb->insns); if (!insn) return 0; /* Infinite loops: let's not "optimize" them.. */ if (old == new) return 0; switch (insn->opcode) { case OP_CBR: changed |= rewrite_branch(bb, &insn->bb_false, old, new); /* fall through */ case OP_BR: changed |= rewrite_branch(bb, &insn->bb_true, old, new); assert(changed); return changed; case OP_SWITCH: { struct multijmp *jmp; FOR_EACH_PTR(insn->multijmp_list, jmp) { changed |= rewrite_branch(bb, &jmp->target, old, new); } END_FOR_EACH_PTR(jmp); assert(changed); return changed; } default: return 0; } } static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br) { struct basic_block *parent; struct basic_block *target = br->bb_true; if (br->opcode == OP_CBR) { pseudo_t cond = br->cond; if (cond->type != PSEUDO_VAL) return NULL; target = cond->value ? target : br->bb_false; } /* * We can't do FOR_EACH_PTR() here, because the parent list * may change when we rewrite the parent. */ while ((parent = first_basic_block(bb->parents)) != NULL) { if (!rewrite_parent_branch(parent, bb, target)) return NULL; } return target; } static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list) { if (bb) { struct basic_block *tmp; int no_bb_in_list = 0; FOR_EACH_PTR(list, tmp) { if (bb == tmp) return; } END_FOR_EACH_PTR(tmp); assert(no_bb_in_list); } } static void vrfy_parents(struct basic_block *bb) { struct basic_block *tmp; FOR_EACH_PTR(bb->parents, tmp) { vrfy_bb_in_list(bb, tmp->children); } END_FOR_EACH_PTR(tmp); } static void vrfy_children(struct basic_block *bb) { struct basic_block *tmp; struct instruction *br = last_instruction(bb->insns); if (!br) { assert(!bb->children); return; } switch (br->opcode) { struct multijmp *jmp; case OP_CBR: vrfy_bb_in_list(br->bb_false, bb->children); /* fall through */ case OP_BR: vrfy_bb_in_list(br->bb_true, bb->children); break; case OP_SWITCH: case OP_COMPUTEDGOTO: FOR_EACH_PTR(br->multijmp_list, jmp) { vrfy_bb_in_list(jmp->target, bb->children); } END_FOR_EACH_PTR(jmp); break; default: break; } FOR_EACH_PTR(bb->children, tmp) { vrfy_bb_in_list(bb, tmp->parents); } END_FOR_EACH_PTR(tmp); } static void vrfy_bb_flow(struct basic_block *bb) { vrfy_children(bb); vrfy_parents(bb); } void vrfy_flow(struct entrypoint *ep) { struct basic_block *bb; struct basic_block *entry = ep->entry->bb; FOR_EACH_PTR(ep->bbs, bb) { if (bb == entry) entry = NULL; vrfy_bb_flow(bb); } END_FOR_EACH_PTR(bb); assert(!entry); } /// // change a switch or a conditional branch into a branch int convert_to_jump(struct instruction *insn, struct basic_block *target) { struct basic_block *bb = insn->bb; struct basic_block *child; int changed = REPEAT_CSE; switch (insn->opcode) { case OP_CBR: changed |= remove_phisources(insn->bb, insn->bb_true == target ? insn->bb_false : insn->bb_true); break; case OP_SWITCH: changed |= remove_other_phisources(insn->bb, insn->multijmp_list, target); break; } kill_use(&insn->cond); insn->bb_true = target; insn->bb_false = NULL; insn->cond = NULL; insn->size = 0; insn->opcode = OP_BR; FOR_EACH_PTR(bb->children, child) { if (child == target) { target = NULL; // leave first occurence continue; } DELETE_CURRENT_PTR(child); remove_bb_from_list(&child->parents, bb, 1); changed |= REPEAT_CFG_CLEANUP; } END_FOR_EACH_PTR(child); PACK_PTR_LIST(&bb->children); repeat_phase |= changed; return changed; } static int retarget_parents(struct basic_block *bb, struct basic_block *target) { struct basic_block *parent; /* * We can't do FOR_EACH_PTR() here, because the parent list * may change when we rewrite the parent. */ while ((parent = first_basic_block(bb->parents))) { if (!rewrite_parent_branch(parent, bb, target)) return 0; } kill_bb(bb); return REPEAT_CFG_CLEANUP; } static void remove_merging_phisrc(struct instruction *insn, struct basic_block *bot) { struct instruction *node = insn->phi_node; pseudo_t phi; if (!node) { kill_instruction(insn); return; } FOR_EACH_PTR(node->phi_list, phi) { struct instruction *phisrc; if (phi == VOID) continue; phisrc = phi->def; if (phisrc->bb == bot) { kill_instruction(insn); return; } } END_FOR_EACH_PTR(phi); } static void remove_merging_phi(struct basic_block *top, struct instruction *insn) { pseudo_t phi; FOR_EACH_PTR(insn->phi_list, phi) { struct instruction *def; if (phi == VOID) continue; def = phi->def; if (def->bb != top) continue; convert_instruction_target(insn, def->src); kill_instruction(def); kill_instruction(insn); } END_FOR_EACH_PTR(phi); } /// // merge two BBs // @top: the first BB to be merged // @bot: the second BB to be merged static int merge_bb(struct basic_block *top, struct basic_block *bot) { struct instruction *insn; struct basic_block *bb; if (top == bot) return 0; top->children = bot->children; bot->children = NULL; bot->parents = NULL; FOR_EACH_PTR(top->children, bb) { replace_bb_in_list(&bb->parents, bot, top, 1); } END_FOR_EACH_PTR(bb); FOR_EACH_PTR(top->insns, insn) { if (!insn->bb) continue; if (insn->opcode != OP_PHISOURCE) continue; remove_merging_phisrc(insn, bot); } END_FOR_EACH_PTR(insn); kill_instruction(delete_last_instruction(&top->insns)); FOR_EACH_PTR(bot->insns, insn) { if (!insn->bb) continue; assert(insn->bb == bot); switch (insn->opcode) { case OP_PHI: remove_merging_phi(top, insn); continue; } insn->bb = top; add_instruction(&top->insns, insn); } END_FOR_EACH_PTR(insn); bot->insns = NULL; bot->ep = NULL; return REPEAT_CFG_CLEANUP; } /// // early simplification of the CFG // Three things are done here: // # inactive BB are removed // # branches to a 'forwarder' BB are redirected to the forwardee. // # merge single-child/single-parent BBs. int simplify_cfg_early(struct entrypoint *ep) { struct basic_block *bb; int changed = 0; FOR_EACH_PTR_REVERSE(ep->bbs, bb) { struct instruction *insn; struct basic_block *tgt; if (!bb->ep) { DELETE_CURRENT_PTR(bb); changed = REPEAT_CFG_CLEANUP; continue; } insn = last_instruction(bb->insns); if (!insn) continue; switch (insn->opcode) { case OP_BR: tgt = insn->bb_true; if (bb_is_forwarder(bb)) changed |= retarget_parents(bb, tgt); else if (bb_list_size(tgt->parents) == 1) changed |= merge_bb(bb, tgt); break; } } END_FOR_EACH_PTR_REVERSE(bb); return changed; } void pack_basic_blocks(struct entrypoint *ep) { struct basic_block *bb; /* See if we can merge a bb into another one.. */ FOR_EACH_PTR(ep->bbs, bb) { struct instruction *first; struct basic_block *parent, *child, *last; if (!bb_reachable(bb)) continue; /* * Just a branch? */ FOR_EACH_PTR(bb->insns, first) { if (!first->bb) continue; switch (first->opcode) { case OP_NOP: case OP_INLINED_CALL: continue; case OP_CBR: case OP_BR: { struct basic_block *replace; replace = rewrite_branch_bb(bb, first); if (replace) { kill_bb(bb); goto no_merge; } } /* fallthrough */ default: goto out; } } END_FOR_EACH_PTR(first); out: /* * See if we only have one parent.. */ last = NULL; FOR_EACH_PTR(bb->parents, parent) { if (last) { if (last != parent) goto no_merge; continue; } last = parent; } END_FOR_EACH_PTR(parent); parent = last; if (!parent || 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); repeat_phase |= merge_bb(parent, bb); no_merge: /* nothing to do */; } END_FOR_EACH_PTR(bb); }