11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Flow - walk the linearized flowgraph, simplifying it as we
31f5207b7SJohn Levon * go along.
41f5207b7SJohn Levon *
51f5207b7SJohn Levon * Copyright (C) 2004 Linus Torvalds
61f5207b7SJohn Levon */
71f5207b7SJohn Levon
81f5207b7SJohn Levon #include <string.h>
91f5207b7SJohn Levon #include <stdarg.h>
101f5207b7SJohn Levon #include <stdlib.h>
111f5207b7SJohn Levon #include <stdio.h>
121f5207b7SJohn Levon #include <stddef.h>
131f5207b7SJohn Levon #include <assert.h>
141f5207b7SJohn Levon
151f5207b7SJohn Levon #include "parse.h"
161f5207b7SJohn Levon #include "expression.h"
171f5207b7SJohn Levon #include "linearize.h"
181f5207b7SJohn Levon #include "flow.h"
191f5207b7SJohn Levon #include "target.h"
201f5207b7SJohn Levon
211f5207b7SJohn Levon unsigned long bb_generation;
221f5207b7SJohn Levon
231f5207b7SJohn Levon /*
241f5207b7SJohn Levon * Dammit, if we have a phi-node followed by a conditional
251f5207b7SJohn Levon * branch on that phi-node, we should damn well be able to
261f5207b7SJohn Levon * do something about the source. Maybe.
271f5207b7SJohn Levon */
rewrite_branch(struct basic_block * bb,struct basic_block ** ptr,struct basic_block * old,struct basic_block * new)281f5207b7SJohn Levon static int rewrite_branch(struct basic_block *bb,
291f5207b7SJohn Levon struct basic_block **ptr,
301f5207b7SJohn Levon struct basic_block *old,
311f5207b7SJohn Levon struct basic_block *new)
321f5207b7SJohn Levon {
331f5207b7SJohn Levon if (*ptr != old || new == old || !bb->ep)
341f5207b7SJohn Levon return 0;
351f5207b7SJohn Levon
361f5207b7SJohn Levon /* We might find new if-conversions or non-dominating CSEs */
371f5207b7SJohn Levon /* we may also create new dead cycles */
381f5207b7SJohn Levon repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP;
391f5207b7SJohn Levon *ptr = new;
401f5207b7SJohn Levon replace_bb_in_list(&bb->children, old, new, 1);
411f5207b7SJohn Levon remove_bb_from_list(&old->parents, bb, 1);
421f5207b7SJohn Levon add_bb(&new->parents, bb);
431f5207b7SJohn Levon return 1;
441f5207b7SJohn Levon }
451f5207b7SJohn Levon
461f5207b7SJohn Levon /*
471f5207b7SJohn Levon * Return the known truth value of a pseudo, or -1 if
481f5207b7SJohn Levon * it's not known.
491f5207b7SJohn Levon */
pseudo_truth_value(pseudo_t pseudo)501f5207b7SJohn Levon static int pseudo_truth_value(pseudo_t pseudo)
511f5207b7SJohn Levon {
521f5207b7SJohn Levon switch (pseudo->type) {
531f5207b7SJohn Levon case PSEUDO_VAL:
541f5207b7SJohn Levon return !!pseudo->value;
551f5207b7SJohn Levon
561f5207b7SJohn Levon case PSEUDO_REG: {
571f5207b7SJohn Levon struct instruction *insn = pseudo->def;
581f5207b7SJohn Levon
591f5207b7SJohn Levon /* A symbol address is always considered true.. */
601f5207b7SJohn Levon if (insn->opcode == OP_SYMADDR && insn->target == pseudo)
611f5207b7SJohn Levon return 1;
621f5207b7SJohn Levon }
631f5207b7SJohn Levon /* Fall through */
641f5207b7SJohn Levon default:
651f5207b7SJohn Levon return -1;
661f5207b7SJohn Levon }
671f5207b7SJohn Levon }
681f5207b7SJohn Levon
691f5207b7SJohn Levon /*
701f5207b7SJohn Levon * Does a basic block depend on the pseudos that "src" defines?
711f5207b7SJohn Levon */
bb_depends_on(struct basic_block * target,struct basic_block * src)721f5207b7SJohn Levon static int bb_depends_on(struct basic_block *target, struct basic_block *src)
731f5207b7SJohn Levon {
741f5207b7SJohn Levon pseudo_t pseudo;
751f5207b7SJohn Levon
761f5207b7SJohn Levon FOR_EACH_PTR(src->defines, pseudo) {
771f5207b7SJohn Levon if (pseudo_in_list(target->needs, pseudo))
781f5207b7SJohn Levon return 1;
791f5207b7SJohn Levon } END_FOR_EACH_PTR(pseudo);
801f5207b7SJohn Levon return 0;
811f5207b7SJohn Levon }
821f5207b7SJohn Levon
831f5207b7SJohn Levon /*
841f5207b7SJohn Levon * This really should be handled by bb_depends_on()
851f5207b7SJohn Levon * which efficiently check the dependence using the
861f5207b7SJohn Levon * defines - needs liveness info. Problem is that
871f5207b7SJohn Levon * there is no liveness done on OP_PHI & OP_PHISRC.
881f5207b7SJohn Levon *
891f5207b7SJohn Levon * This function add the missing dependency checks.
901f5207b7SJohn Levon */
bb_depends_on_phi(struct basic_block * target,struct basic_block * src)911f5207b7SJohn Levon static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src)
921f5207b7SJohn Levon {
931f5207b7SJohn Levon struct instruction *insn;
941f5207b7SJohn Levon FOR_EACH_PTR(src->insns, insn) {
951f5207b7SJohn Levon if (!insn->bb)
961f5207b7SJohn Levon continue;
971f5207b7SJohn Levon if (insn->opcode != OP_PHI)
981f5207b7SJohn Levon continue;
991f5207b7SJohn Levon if (pseudo_in_list(target->needs, insn->target))
1001f5207b7SJohn Levon return 1;
1011f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
1021f5207b7SJohn Levon return 0;
1031f5207b7SJohn Levon }
1041f5207b7SJohn Levon
1051f5207b7SJohn Levon /*
1061f5207b7SJohn Levon * When we reach here, we have:
1071f5207b7SJohn Levon * - a basic block that ends in a conditional branch and
1081f5207b7SJohn Levon * that has no side effects apart from the pseudos it
1091f5207b7SJohn Levon * may change.
1101f5207b7SJohn Levon * - the phi-node that the conditional branch depends on
1111f5207b7SJohn Levon * - full pseudo liveness information
1121f5207b7SJohn Levon *
1131f5207b7SJohn Levon * We need to check if any of the _sources_ of the phi-node
1141f5207b7SJohn Levon * may be constant, and not actually need this block at all.
1151f5207b7SJohn Levon */
try_to_simplify_bb(struct basic_block * bb,struct instruction * first,struct instruction * second)1161f5207b7SJohn Levon static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second)
1171f5207b7SJohn Levon {
1181f5207b7SJohn Levon int changed = 0;
1191f5207b7SJohn Levon pseudo_t phi;
1201f5207b7SJohn Levon int bogus;
1211f5207b7SJohn Levon
1221f5207b7SJohn Levon /*
1231f5207b7SJohn Levon * This a due to improper dominance tracking during
1241f5207b7SJohn Levon * simplify_symbol_usage()/conversion to SSA form.
1251f5207b7SJohn Levon * No sane simplification can be done when we have this.
1261f5207b7SJohn Levon */
1271f5207b7SJohn Levon bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list);
1281f5207b7SJohn Levon
1291f5207b7SJohn Levon FOR_EACH_PTR(first->phi_list, phi) {
1301f5207b7SJohn Levon struct instruction *def = phi->def;
1311f5207b7SJohn Levon struct basic_block *source, *target;
1321f5207b7SJohn Levon pseudo_t pseudo;
1331f5207b7SJohn Levon struct instruction *br;
134*c85f09ccSJohn Levon int cond;
1351f5207b7SJohn Levon
1361f5207b7SJohn Levon if (!def)
1371f5207b7SJohn Levon continue;
1381f5207b7SJohn Levon source = def->bb;
1391f5207b7SJohn Levon pseudo = def->src1;
1401f5207b7SJohn Levon if (!pseudo || !source)
1411f5207b7SJohn Levon continue;
1421f5207b7SJohn Levon br = last_instruction(source->insns);
1431f5207b7SJohn Levon if (!br)
1441f5207b7SJohn Levon continue;
1451f5207b7SJohn Levon if (br->opcode != OP_CBR && br->opcode != OP_BR)
1461f5207b7SJohn Levon continue;
147*c85f09ccSJohn Levon cond = pseudo_truth_value(pseudo);
148*c85f09ccSJohn Levon if (cond < 0)
1491f5207b7SJohn Levon continue;
150*c85f09ccSJohn Levon target = cond ? second->bb_true : second->bb_false;
1511f5207b7SJohn Levon if (bb_depends_on(target, bb))
1521f5207b7SJohn Levon continue;
1531f5207b7SJohn Levon if (bb_depends_on_phi(target, bb))
1541f5207b7SJohn Levon continue;
1551f5207b7SJohn Levon changed |= rewrite_branch(source, &br->bb_true, bb, target);
1561f5207b7SJohn Levon changed |= rewrite_branch(source, &br->bb_false, bb, target);
1571f5207b7SJohn Levon if (changed && !bogus)
1581f5207b7SJohn Levon kill_use(THIS_ADDRESS(phi));
1591f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
1601f5207b7SJohn Levon return changed;
1611f5207b7SJohn Levon }
1621f5207b7SJohn Levon
bb_has_side_effects(struct basic_block * bb)1631f5207b7SJohn Levon static int bb_has_side_effects(struct basic_block *bb)
1641f5207b7SJohn Levon {
1651f5207b7SJohn Levon struct instruction *insn;
1661f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
167*c85f09ccSJohn Levon if (!insn->bb)
168*c85f09ccSJohn Levon continue;
1691f5207b7SJohn Levon switch (insn->opcode) {
1701f5207b7SJohn Levon case OP_CALL:
1711f5207b7SJohn Levon /* FIXME! This should take "const" etc into account */
1721f5207b7SJohn Levon return 1;
1731f5207b7SJohn Levon
174*c85f09ccSJohn Levon case OP_LOAD:
175*c85f09ccSJohn Levon if (!insn->type)
176*c85f09ccSJohn Levon return 1;
177*c85f09ccSJohn Levon if (insn->is_volatile)
178*c85f09ccSJohn Levon return 1;
179*c85f09ccSJohn Levon continue;
180*c85f09ccSJohn Levon
1811f5207b7SJohn Levon case OP_STORE:
1821f5207b7SJohn Levon case OP_CONTEXT:
1831f5207b7SJohn Levon return 1;
1841f5207b7SJohn Levon
1851f5207b7SJohn Levon case OP_ASM:
1861f5207b7SJohn Levon /* FIXME! This should take "volatile" etc into account */
1871f5207b7SJohn Levon return 1;
1881f5207b7SJohn Levon
1891f5207b7SJohn Levon default:
1901f5207b7SJohn Levon continue;
1911f5207b7SJohn Levon }
1921f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
1931f5207b7SJohn Levon return 0;
1941f5207b7SJohn Levon }
1951f5207b7SJohn Levon
simplify_phi_branch(struct basic_block * bb,struct instruction * br)1961f5207b7SJohn Levon static int simplify_phi_branch(struct basic_block *bb, struct instruction *br)
1971f5207b7SJohn Levon {
1981f5207b7SJohn Levon pseudo_t cond = br->cond;
1991f5207b7SJohn Levon struct instruction *def;
2001f5207b7SJohn Levon
2011f5207b7SJohn Levon if (cond->type != PSEUDO_REG)
2021f5207b7SJohn Levon return 0;
2031f5207b7SJohn Levon def = cond->def;
2041f5207b7SJohn Levon if (def->bb != bb || def->opcode != OP_PHI)
2051f5207b7SJohn Levon return 0;
2061f5207b7SJohn Levon if (bb_has_side_effects(bb))
2071f5207b7SJohn Levon return 0;
2081f5207b7SJohn Levon return try_to_simplify_bb(bb, def, br);
2091f5207b7SJohn Levon }
2101f5207b7SJohn Levon
simplify_branch_branch(struct basic_block * bb,struct instruction * br,struct basic_block ** target_p,int bb_true)2111f5207b7SJohn Levon static int simplify_branch_branch(struct basic_block *bb, struct instruction *br,
212*c85f09ccSJohn Levon struct basic_block **target_p, int bb_true)
2131f5207b7SJohn Levon {
2141f5207b7SJohn Levon struct basic_block *target = *target_p, *final;
2151f5207b7SJohn Levon struct instruction *insn;
2161f5207b7SJohn Levon int retval;
2171f5207b7SJohn Levon
2181f5207b7SJohn Levon if (target == bb)
2191f5207b7SJohn Levon return 0;
2201f5207b7SJohn Levon insn = last_instruction(target->insns);
2211f5207b7SJohn Levon if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond)
2221f5207b7SJohn Levon return 0;
2231f5207b7SJohn Levon /*
2241f5207b7SJohn Levon * Ahhah! We've found a branch to a branch on the same conditional!
2251f5207b7SJohn Levon * Now we just need to see if we can rewrite the branch..
2261f5207b7SJohn Levon */
2271f5207b7SJohn Levon retval = 0;
228*c85f09ccSJohn Levon final = bb_true ? insn->bb_true : insn->bb_false;
2291f5207b7SJohn Levon if (bb_has_side_effects(target))
2301f5207b7SJohn Levon goto try_to_rewrite_target;
2311f5207b7SJohn Levon if (bb_depends_on(final, target))
2321f5207b7SJohn Levon goto try_to_rewrite_target;
2331f5207b7SJohn Levon if (bb_depends_on_phi(final, target))
2341f5207b7SJohn Levon return 0;
2351f5207b7SJohn Levon return rewrite_branch(bb, target_p, target, final);
2361f5207b7SJohn Levon
2371f5207b7SJohn Levon try_to_rewrite_target:
2381f5207b7SJohn Levon /*
2391f5207b7SJohn Levon * If we're the only parent, at least we can rewrite the
2401f5207b7SJohn Levon * now-known second branch.
2411f5207b7SJohn Levon */
2421f5207b7SJohn Levon if (bb_list_size(target->parents) != 1)
2431f5207b7SJohn Levon return retval;
2441f5207b7SJohn Levon insert_branch(target, insn, final);
2451f5207b7SJohn Levon return 1;
2461f5207b7SJohn Levon }
2471f5207b7SJohn Levon
simplify_one_branch(struct basic_block * bb,struct instruction * br)2481f5207b7SJohn Levon static int simplify_one_branch(struct basic_block *bb, struct instruction *br)
2491f5207b7SJohn Levon {
2501f5207b7SJohn Levon if (simplify_phi_branch(bb, br))
2511f5207b7SJohn Levon return 1;
2521f5207b7SJohn Levon return simplify_branch_branch(bb, br, &br->bb_true, 1) |
2531f5207b7SJohn Levon simplify_branch_branch(bb, br, &br->bb_false, 0);
2541f5207b7SJohn Levon }
2551f5207b7SJohn Levon
simplify_branch_nodes(struct entrypoint * ep)2561f5207b7SJohn Levon static int simplify_branch_nodes(struct entrypoint *ep)
2571f5207b7SJohn Levon {
2581f5207b7SJohn Levon int changed = 0;
2591f5207b7SJohn Levon struct basic_block *bb;
2601f5207b7SJohn Levon
2611f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
2621f5207b7SJohn Levon struct instruction *br = last_instruction(bb->insns);
2631f5207b7SJohn Levon
2641f5207b7SJohn Levon if (!br || br->opcode != OP_CBR)
2651f5207b7SJohn Levon continue;
2661f5207b7SJohn Levon changed |= simplify_one_branch(bb, br);
2671f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
2681f5207b7SJohn Levon return changed;
2691f5207b7SJohn Levon }
2701f5207b7SJohn Levon
2711f5207b7SJohn Levon /*
2721f5207b7SJohn Levon * This is called late - when we have intra-bb liveness information..
2731f5207b7SJohn Levon */
simplify_flow(struct entrypoint * ep)2741f5207b7SJohn Levon int simplify_flow(struct entrypoint *ep)
2751f5207b7SJohn Levon {
2761f5207b7SJohn Levon return simplify_branch_nodes(ep);
2771f5207b7SJohn Levon }
2781f5207b7SJohn Levon
concat_user_list(struct pseudo_user_list * src,struct pseudo_user_list ** dst)2791f5207b7SJohn Levon static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst)
2801f5207b7SJohn Levon {
281*c85f09ccSJohn Levon copy_ptr_list((struct ptr_list **)dst, (struct ptr_list *)src);
2821f5207b7SJohn Levon }
2831f5207b7SJohn Levon
convert_instruction_target(struct instruction * insn,pseudo_t src)2841f5207b7SJohn Levon void convert_instruction_target(struct instruction *insn, pseudo_t src)
2851f5207b7SJohn Levon {
2861f5207b7SJohn Levon pseudo_t target;
2871f5207b7SJohn Levon struct pseudo_user *pu;
2881f5207b7SJohn Levon /*
2891f5207b7SJohn Levon * Go through the "insn->users" list and replace them all..
2901f5207b7SJohn Levon */
2911f5207b7SJohn Levon target = insn->target;
2921f5207b7SJohn Levon if (target == src)
2931f5207b7SJohn Levon return;
2941f5207b7SJohn Levon FOR_EACH_PTR(target->users, pu) {
2951f5207b7SJohn Levon if (*pu->userp != VOID) {
2961f5207b7SJohn Levon assert(*pu->userp == target);
2971f5207b7SJohn Levon *pu->userp = src;
2981f5207b7SJohn Levon }
2991f5207b7SJohn Levon } END_FOR_EACH_PTR(pu);
3001f5207b7SJohn Levon if (has_use_list(src))
3011f5207b7SJohn Levon concat_user_list(target->users, &src->users);
3021f5207b7SJohn Levon target->users = NULL;
3031f5207b7SJohn Levon }
3041f5207b7SJohn Levon
convert_load_instruction(struct instruction * insn,pseudo_t src)3051f5207b7SJohn Levon void convert_load_instruction(struct instruction *insn, pseudo_t src)
3061f5207b7SJohn Levon {
3071f5207b7SJohn Levon convert_instruction_target(insn, src);
308*c85f09ccSJohn Levon kill_instruction(insn);
309*c85f09ccSJohn Levon repeat_phase |= REPEAT_SYMBOL_CLEANUP;
3101f5207b7SJohn Levon }
3111f5207b7SJohn Levon
overlapping_memop(struct instruction * a,struct instruction * b)3121f5207b7SJohn Levon static int overlapping_memop(struct instruction *a, struct instruction *b)
3131f5207b7SJohn Levon {
3141f5207b7SJohn Levon unsigned int a_start = bytes_to_bits(a->offset);
3151f5207b7SJohn Levon unsigned int b_start = bytes_to_bits(b->offset);
3161f5207b7SJohn Levon unsigned int a_size = a->size;
3171f5207b7SJohn Levon unsigned int b_size = b->size;
3181f5207b7SJohn Levon
3191f5207b7SJohn Levon if (a_size + a_start <= b_start)
3201f5207b7SJohn Levon return 0;
3211f5207b7SJohn Levon if (b_size + b_start <= a_start)
3221f5207b7SJohn Levon return 0;
3231f5207b7SJohn Levon return 1;
3241f5207b7SJohn Levon }
3251f5207b7SJohn Levon
same_memop(struct instruction * a,struct instruction * b)3261f5207b7SJohn Levon static inline int same_memop(struct instruction *a, struct instruction *b)
3271f5207b7SJohn Levon {
3281f5207b7SJohn Levon return a->offset == b->offset && a->size == b->size;
3291f5207b7SJohn Levon }
3301f5207b7SJohn Levon
distinct_symbols(pseudo_t a,pseudo_t b)3311f5207b7SJohn Levon static inline int distinct_symbols(pseudo_t a, pseudo_t b)
3321f5207b7SJohn Levon {
3331f5207b7SJohn Levon if (a->type != PSEUDO_SYM)
3341f5207b7SJohn Levon return 0;
3351f5207b7SJohn Levon if (b->type != PSEUDO_SYM)
3361f5207b7SJohn Levon return 0;
3371f5207b7SJohn Levon return a->sym != b->sym;
3381f5207b7SJohn Levon }
3391f5207b7SJohn Levon
3401f5207b7SJohn Levon /*
3411f5207b7SJohn Levon * Return 1 if "dom" dominates the access to "pseudo"
3421f5207b7SJohn Levon * in "insn".
3431f5207b7SJohn Levon *
3441f5207b7SJohn Levon * Return 0 if it doesn't, and -1 if you don't know.
3451f5207b7SJohn Levon */
dominates(pseudo_t pseudo,struct instruction * insn,struct instruction * dom,int local)3461f5207b7SJohn Levon int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local)
3471f5207b7SJohn Levon {
3481f5207b7SJohn Levon int opcode = dom->opcode;
3491f5207b7SJohn Levon
3501f5207b7SJohn Levon if (opcode == OP_CALL || opcode == OP_ENTRY)
3511f5207b7SJohn Levon return local ? 0 : -1;
3521f5207b7SJohn Levon if (opcode != OP_LOAD && opcode != OP_STORE)
3531f5207b7SJohn Levon return 0;
3541f5207b7SJohn Levon if (dom->src != pseudo) {
3551f5207b7SJohn Levon if (local)
3561f5207b7SJohn Levon return 0;
3571f5207b7SJohn Levon /* We don't think two explicitly different symbols ever alias */
3581f5207b7SJohn Levon if (distinct_symbols(insn->src, dom->src))
3591f5207b7SJohn Levon return 0;
3601f5207b7SJohn Levon /* We could try to do some alias analysis here */
3611f5207b7SJohn Levon return -1;
3621f5207b7SJohn Levon }
3631f5207b7SJohn Levon if (!same_memop(insn, dom)) {
3641f5207b7SJohn Levon if (dom->opcode == OP_LOAD)
3651f5207b7SJohn Levon return 0;
3661f5207b7SJohn Levon if (!overlapping_memop(insn, dom))
3671f5207b7SJohn Levon return 0;
3681f5207b7SJohn Levon return -1;
3691f5207b7SJohn Levon }
3701f5207b7SJohn Levon return 1;
3711f5207b7SJohn Levon }
3721f5207b7SJohn Levon
3731f5207b7SJohn Levon /*
3741f5207b7SJohn Levon * We should probably sort the phi list just to make it easier to compare
3751f5207b7SJohn Levon * later for equality.
3761f5207b7SJohn Levon */
rewrite_load_instruction(struct instruction * insn,struct pseudo_list * dominators)3771f5207b7SJohn Levon void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
3781f5207b7SJohn Levon {
3791f5207b7SJohn Levon pseudo_t new, phi;
3801f5207b7SJohn Levon
3811f5207b7SJohn Levon /*
3821f5207b7SJohn Levon * Check for somewhat common case of duplicate
3831f5207b7SJohn Levon * phi nodes.
3841f5207b7SJohn Levon */
385*c85f09ccSJohn Levon new = first_pseudo(dominators)->def->phi_src;
3861f5207b7SJohn Levon FOR_EACH_PTR(dominators, phi) {
387*c85f09ccSJohn Levon if (new != phi->def->phi_src)
3881f5207b7SJohn Levon goto complex_phi;
3891f5207b7SJohn Levon new->ident = new->ident ? : phi->ident;
3901f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
3911f5207b7SJohn Levon
3921f5207b7SJohn Levon /*
3931f5207b7SJohn Levon * All the same pseudo - mark the phi-nodes unused
3941f5207b7SJohn Levon * and convert the load into a LNOP and replace the
3951f5207b7SJohn Levon * pseudo.
3961f5207b7SJohn Levon */
397*c85f09ccSJohn Levon convert_load_instruction(insn, new);
3981f5207b7SJohn Levon FOR_EACH_PTR(dominators, phi) {
3991f5207b7SJohn Levon kill_instruction(phi->def);
4001f5207b7SJohn Levon } END_FOR_EACH_PTR(phi);
401*c85f09ccSJohn Levon goto end;
4021f5207b7SJohn Levon
4031f5207b7SJohn Levon complex_phi:
4041f5207b7SJohn Levon /* We leave symbol pseudos with a bogus usage list here */
4051f5207b7SJohn Levon if (insn->src->type != PSEUDO_SYM)
4061f5207b7SJohn Levon kill_use(&insn->src);
4071f5207b7SJohn Levon insn->opcode = OP_PHI;
4081f5207b7SJohn Levon insn->phi_list = dominators;
4091f5207b7SJohn Levon
410*c85f09ccSJohn Levon end:
411*c85f09ccSJohn Levon repeat_phase |= REPEAT_SYMBOL_CLEANUP;
4121f5207b7SJohn Levon }
4131f5207b7SJohn Levon
4141f5207b7SJohn Levon /* Kill a pseudo that is dead on exit from the bb */
415*c85f09ccSJohn Levon // The context is:
416*c85f09ccSJohn Levon // * the variable is not global but may have its address used (local/non-local)
417*c85f09ccSJohn Levon // * the stores are only needed by others functions which would do some
418*c85f09ccSJohn Levon // loads via the escaped address
419*c85f09ccSJohn Levon // We start by the terminating BB (normal exit BB + no-return/unreachable)
420*c85f09ccSJohn Levon // We walkup the BB' intruction backward
421*c85f09ccSJohn Levon // * we're only concerned by loads, stores & calls
422*c85f09ccSJohn Levon // * if we reach a call -> we have to stop if var is non-local
423*c85f09ccSJohn Levon // * if we reach a load of our var -> we have to stop
424*c85f09ccSJohn Levon // * if we reach a store of our var -> we can kill it, it's dead
425*c85f09ccSJohn Levon // * we can ignore other stores & loads if the var is local
426*c85f09ccSJohn Levon // * if we reach another store or load done via non-symbol access
427*c85f09ccSJohn Levon // (so done via some address calculation) -> we have to stop
428*c85f09ccSJohn Levon // If we reach the top of the BB we can recurse into the parents BBs.
kill_dead_stores_bb(pseudo_t pseudo,unsigned long generation,struct basic_block * bb,int local)429*c85f09ccSJohn Levon static void kill_dead_stores_bb(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
4301f5207b7SJohn Levon {
4311f5207b7SJohn Levon struct instruction *insn;
4321f5207b7SJohn Levon struct basic_block *parent;
4331f5207b7SJohn Levon
4341f5207b7SJohn Levon if (bb->generation == generation)
4351f5207b7SJohn Levon return;
4361f5207b7SJohn Levon bb->generation = generation;
4371f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(bb->insns, insn) {
438*c85f09ccSJohn Levon if (!insn->bb)
4391f5207b7SJohn Levon continue;
440*c85f09ccSJohn Levon switch (insn->opcode) {
441*c85f09ccSJohn Levon case OP_LOAD:
442*c85f09ccSJohn Levon if (insn->src == pseudo)
4431f5207b7SJohn Levon return;
444*c85f09ccSJohn Levon break;
445*c85f09ccSJohn Levon case OP_STORE:
446*c85f09ccSJohn Levon if (insn->src == pseudo) {
447*c85f09ccSJohn Levon kill_instruction_force(insn);
448*c85f09ccSJohn Levon continue;
449*c85f09ccSJohn Levon }
450*c85f09ccSJohn Levon break;
451*c85f09ccSJohn Levon case OP_CALL:
452*c85f09ccSJohn Levon if (!local)
453*c85f09ccSJohn Levon return;
454*c85f09ccSJohn Levon default:
4551f5207b7SJohn Levon continue;
4561f5207b7SJohn Levon }
457*c85f09ccSJohn Levon if (!local && insn->src->type != PSEUDO_SYM)
4581f5207b7SJohn Levon return;
4591f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(insn);
4601f5207b7SJohn Levon
4611f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) {
462*c85f09ccSJohn Levon if (bb_list_size(parent->children) > 1)
4631f5207b7SJohn Levon continue;
464*c85f09ccSJohn Levon kill_dead_stores_bb(pseudo, generation, parent, local);
4651f5207b7SJohn Levon } END_FOR_EACH_PTR(parent);
4661f5207b7SJohn Levon }
4671f5207b7SJohn Levon
check_access(struct instruction * insn)4681f5207b7SJohn Levon void check_access(struct instruction *insn)
4691f5207b7SJohn Levon {
4701f5207b7SJohn Levon pseudo_t pseudo = insn->src;
4711f5207b7SJohn Levon
4721f5207b7SJohn Levon if (insn->bb && pseudo->type == PSEUDO_SYM) {
4731f5207b7SJohn Levon int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size;
4741f5207b7SJohn Levon struct symbol *sym = pseudo->sym;
4751f5207b7SJohn Levon
476*c85f09ccSJohn Levon if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size)) {
477*c85f09ccSJohn Levon if (insn->tainted)
478*c85f09ccSJohn Levon return;
4791f5207b7SJohn Levon warning(insn->pos, "invalid access %s '%s' (%d %d)",
4801f5207b7SJohn Levon offset < 0 ? "below" : "past the end of",
4811f5207b7SJohn Levon show_ident(sym->ident), offset,
4821f5207b7SJohn Levon bits_to_bytes(sym->bit_size));
483*c85f09ccSJohn Levon insn->tainted = 1;
484*c85f09ccSJohn Levon }
4851f5207b7SJohn Levon }
4861f5207b7SJohn Levon }
4871f5207b7SJohn Levon
first_user(pseudo_t p)488*c85f09ccSJohn Levon static struct pseudo_user *first_user(pseudo_t p)
4891f5207b7SJohn Levon {
4901f5207b7SJohn Levon struct pseudo_user *pu;
491*c85f09ccSJohn Levon FOR_EACH_PTR(p->users, pu) {
492*c85f09ccSJohn Levon if (!pu)
4931f5207b7SJohn Levon continue;
494*c85f09ccSJohn Levon return pu;
4951f5207b7SJohn Levon } END_FOR_EACH_PTR(pu);
496*c85f09ccSJohn Levon return NULL;
497*c85f09ccSJohn Levon }
4981f5207b7SJohn Levon
kill_dead_stores(struct entrypoint * ep,pseudo_t addr,int local)499*c85f09ccSJohn Levon void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local)
500*c85f09ccSJohn Levon {
501*c85f09ccSJohn Levon unsigned long generation;
502*c85f09ccSJohn Levon struct basic_block *bb;
503*c85f09ccSJohn Levon
504*c85f09ccSJohn Levon switch (pseudo_user_list_size(addr->users)) {
505*c85f09ccSJohn Levon case 0:
506*c85f09ccSJohn Levon return;
507*c85f09ccSJohn Levon case 1:
508*c85f09ccSJohn Levon if (local) {
509*c85f09ccSJohn Levon struct pseudo_user *pu = first_user(addr);
5101f5207b7SJohn Levon struct instruction *insn = pu->insn;
511*c85f09ccSJohn Levon if (insn->opcode == OP_STORE) {
512*c85f09ccSJohn Levon kill_instruction_force(insn);
513*c85f09ccSJohn Levon return;
514*c85f09ccSJohn Levon }
5151f5207b7SJohn Levon }
516*c85f09ccSJohn Levon default:
517*c85f09ccSJohn Levon break;
5181f5207b7SJohn Levon }
5191f5207b7SJohn Levon
520*c85f09ccSJohn Levon generation = ++bb_generation;
521*c85f09ccSJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
522*c85f09ccSJohn Levon if (bb->children)
523*c85f09ccSJohn Levon continue;
524*c85f09ccSJohn Levon kill_dead_stores_bb(addr, generation, bb, local);
525*c85f09ccSJohn Levon } END_FOR_EACH_PTR(bb);
5261f5207b7SJohn Levon }
5271f5207b7SJohn Levon
mark_bb_reachable(struct basic_block * bb,unsigned long generation)5281f5207b7SJohn Levon static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
5291f5207b7SJohn Levon {
5301f5207b7SJohn Levon struct basic_block *child;
5311f5207b7SJohn Levon
5321f5207b7SJohn Levon if (bb->generation == generation)
5331f5207b7SJohn Levon return;
5341f5207b7SJohn Levon bb->generation = generation;
5351f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) {
5361f5207b7SJohn Levon mark_bb_reachable(child, generation);
5371f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
5381f5207b7SJohn Levon }
5391f5207b7SJohn Levon
kill_defs(struct instruction * insn)5401f5207b7SJohn Levon static void kill_defs(struct instruction *insn)
5411f5207b7SJohn Levon {
5421f5207b7SJohn Levon pseudo_t target = insn->target;
5431f5207b7SJohn Levon
5441f5207b7SJohn Levon if (!has_use_list(target))
5451f5207b7SJohn Levon return;
5461f5207b7SJohn Levon if (target->def != insn)
5471f5207b7SJohn Levon return;
5481f5207b7SJohn Levon
5491f5207b7SJohn Levon convert_instruction_target(insn, VOID);
5501f5207b7SJohn Levon }
5511f5207b7SJohn Levon
kill_bb(struct basic_block * bb)5521f5207b7SJohn Levon void kill_bb(struct basic_block *bb)
5531f5207b7SJohn Levon {
5541f5207b7SJohn Levon struct instruction *insn;
5551f5207b7SJohn Levon struct basic_block *child, *parent;
5561f5207b7SJohn Levon
5571f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
558*c85f09ccSJohn Levon if (!insn->bb)
559*c85f09ccSJohn Levon continue;
5601f5207b7SJohn Levon kill_instruction_force(insn);
5611f5207b7SJohn Levon kill_defs(insn);
5621f5207b7SJohn Levon /*
5631f5207b7SJohn Levon * We kill unreachable instructions even if they
5641f5207b7SJohn Levon * otherwise aren't "killable" (e.g. volatile loads)
5651f5207b7SJohn Levon */
5661f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
5671f5207b7SJohn Levon bb->insns = NULL;
5681f5207b7SJohn Levon
5691f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) {
5701f5207b7SJohn Levon remove_bb_from_list(&child->parents, bb, 0);
5711f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
5721f5207b7SJohn Levon bb->children = NULL;
5731f5207b7SJohn Levon
5741f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) {
5751f5207b7SJohn Levon remove_bb_from_list(&parent->children, bb, 0);
5761f5207b7SJohn Levon } END_FOR_EACH_PTR(parent);
5771f5207b7SJohn Levon bb->parents = NULL;
5781f5207b7SJohn Levon }
5791f5207b7SJohn Levon
kill_unreachable_bbs(struct entrypoint * ep)5801f5207b7SJohn Levon void kill_unreachable_bbs(struct entrypoint *ep)
5811f5207b7SJohn Levon {
5821f5207b7SJohn Levon struct basic_block *bb;
5831f5207b7SJohn Levon unsigned long generation = ++bb_generation;
5841f5207b7SJohn Levon
5851f5207b7SJohn Levon mark_bb_reachable(ep->entry->bb, generation);
5861f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
5871f5207b7SJohn Levon if (bb->generation == generation)
5881f5207b7SJohn Levon continue;
5891f5207b7SJohn Levon /* Mark it as being dead */
5901f5207b7SJohn Levon kill_bb(bb);
5911f5207b7SJohn Levon bb->ep = NULL;
5921f5207b7SJohn Levon DELETE_CURRENT_PTR(bb);
5931f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
5941f5207b7SJohn Levon PACK_PTR_LIST(&ep->bbs);
5951f5207b7SJohn Levon }
5961f5207b7SJohn Levon
rewrite_parent_branch(struct basic_block * bb,struct basic_block * old,struct basic_block * new)5971f5207b7SJohn Levon static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
5981f5207b7SJohn Levon {
5991f5207b7SJohn Levon int changed = 0;
6001f5207b7SJohn Levon struct instruction *insn = last_instruction(bb->insns);
6011f5207b7SJohn Levon
6021f5207b7SJohn Levon if (!insn)
6031f5207b7SJohn Levon return 0;
6041f5207b7SJohn Levon
6051f5207b7SJohn Levon /* Infinite loops: let's not "optimize" them.. */
6061f5207b7SJohn Levon if (old == new)
6071f5207b7SJohn Levon return 0;
6081f5207b7SJohn Levon
6091f5207b7SJohn Levon switch (insn->opcode) {
6101f5207b7SJohn Levon case OP_CBR:
6111f5207b7SJohn Levon changed |= rewrite_branch(bb, &insn->bb_false, old, new);
6121f5207b7SJohn Levon /* fall through */
6131f5207b7SJohn Levon case OP_BR:
6141f5207b7SJohn Levon changed |= rewrite_branch(bb, &insn->bb_true, old, new);
6151f5207b7SJohn Levon assert(changed);
6161f5207b7SJohn Levon return changed;
6171f5207b7SJohn Levon case OP_SWITCH: {
6181f5207b7SJohn Levon struct multijmp *jmp;
6191f5207b7SJohn Levon FOR_EACH_PTR(insn->multijmp_list, jmp) {
6201f5207b7SJohn Levon changed |= rewrite_branch(bb, &jmp->target, old, new);
6211f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp);
6221f5207b7SJohn Levon assert(changed);
6231f5207b7SJohn Levon return changed;
6241f5207b7SJohn Levon }
6251f5207b7SJohn Levon default:
6261f5207b7SJohn Levon return 0;
6271f5207b7SJohn Levon }
6281f5207b7SJohn Levon }
6291f5207b7SJohn Levon
rewrite_branch_bb(struct basic_block * bb,struct instruction * br)6301f5207b7SJohn Levon static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br)
6311f5207b7SJohn Levon {
6321f5207b7SJohn Levon struct basic_block *parent;
6331f5207b7SJohn Levon struct basic_block *target = br->bb_true;
6341f5207b7SJohn Levon
6351f5207b7SJohn Levon if (br->opcode == OP_CBR) {
6361f5207b7SJohn Levon pseudo_t cond = br->cond;
6371f5207b7SJohn Levon if (cond->type != PSEUDO_VAL)
6381f5207b7SJohn Levon return NULL;
639*c85f09ccSJohn Levon target = cond->value ? target : br->bb_false;
6401f5207b7SJohn Levon }
6411f5207b7SJohn Levon
6421f5207b7SJohn Levon /*
6431f5207b7SJohn Levon * We can't do FOR_EACH_PTR() here, because the parent list
6441f5207b7SJohn Levon * may change when we rewrite the parent.
6451f5207b7SJohn Levon */
6461f5207b7SJohn Levon while ((parent = first_basic_block(bb->parents)) != NULL) {
6471f5207b7SJohn Levon if (!rewrite_parent_branch(parent, bb, target))
6481f5207b7SJohn Levon return NULL;
6491f5207b7SJohn Levon }
6501f5207b7SJohn Levon return target;
6511f5207b7SJohn Levon }
6521f5207b7SJohn Levon
vrfy_bb_in_list(struct basic_block * bb,struct basic_block_list * list)6531f5207b7SJohn Levon static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list)
6541f5207b7SJohn Levon {
6551f5207b7SJohn Levon if (bb) {
6561f5207b7SJohn Levon struct basic_block *tmp;
6571f5207b7SJohn Levon int no_bb_in_list = 0;
6581f5207b7SJohn Levon
6591f5207b7SJohn Levon FOR_EACH_PTR(list, tmp) {
6601f5207b7SJohn Levon if (bb == tmp)
6611f5207b7SJohn Levon return;
6621f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
6631f5207b7SJohn Levon assert(no_bb_in_list);
6641f5207b7SJohn Levon }
6651f5207b7SJohn Levon }
6661f5207b7SJohn Levon
vrfy_parents(struct basic_block * bb)6671f5207b7SJohn Levon static void vrfy_parents(struct basic_block *bb)
6681f5207b7SJohn Levon {
6691f5207b7SJohn Levon struct basic_block *tmp;
6701f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, tmp) {
6711f5207b7SJohn Levon vrfy_bb_in_list(bb, tmp->children);
6721f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
6731f5207b7SJohn Levon }
6741f5207b7SJohn Levon
vrfy_children(struct basic_block * bb)6751f5207b7SJohn Levon static void vrfy_children(struct basic_block *bb)
6761f5207b7SJohn Levon {
6771f5207b7SJohn Levon struct basic_block *tmp;
6781f5207b7SJohn Levon struct instruction *br = last_instruction(bb->insns);
6791f5207b7SJohn Levon
6801f5207b7SJohn Levon if (!br) {
6811f5207b7SJohn Levon assert(!bb->children);
6821f5207b7SJohn Levon return;
6831f5207b7SJohn Levon }
6841f5207b7SJohn Levon switch (br->opcode) {
6851f5207b7SJohn Levon struct multijmp *jmp;
6861f5207b7SJohn Levon case OP_CBR:
6871f5207b7SJohn Levon vrfy_bb_in_list(br->bb_false, bb->children);
6881f5207b7SJohn Levon /* fall through */
6891f5207b7SJohn Levon case OP_BR:
6901f5207b7SJohn Levon vrfy_bb_in_list(br->bb_true, bb->children);
6911f5207b7SJohn Levon break;
6921f5207b7SJohn Levon case OP_SWITCH:
6931f5207b7SJohn Levon case OP_COMPUTEDGOTO:
6941f5207b7SJohn Levon FOR_EACH_PTR(br->multijmp_list, jmp) {
6951f5207b7SJohn Levon vrfy_bb_in_list(jmp->target, bb->children);
6961f5207b7SJohn Levon } END_FOR_EACH_PTR(jmp);
6971f5207b7SJohn Levon break;
6981f5207b7SJohn Levon default:
6991f5207b7SJohn Levon break;
7001f5207b7SJohn Levon }
7011f5207b7SJohn Levon
7021f5207b7SJohn Levon FOR_EACH_PTR(bb->children, tmp) {
7031f5207b7SJohn Levon vrfy_bb_in_list(bb, tmp->parents);
7041f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
7051f5207b7SJohn Levon }
7061f5207b7SJohn Levon
vrfy_bb_flow(struct basic_block * bb)7071f5207b7SJohn Levon static void vrfy_bb_flow(struct basic_block *bb)
7081f5207b7SJohn Levon {
7091f5207b7SJohn Levon vrfy_children(bb);
7101f5207b7SJohn Levon vrfy_parents(bb);
7111f5207b7SJohn Levon }
7121f5207b7SJohn Levon
vrfy_flow(struct entrypoint * ep)7131f5207b7SJohn Levon void vrfy_flow(struct entrypoint *ep)
7141f5207b7SJohn Levon {
7151f5207b7SJohn Levon struct basic_block *bb;
7161f5207b7SJohn Levon struct basic_block *entry = ep->entry->bb;
7171f5207b7SJohn Levon
7181f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
7191f5207b7SJohn Levon if (bb == entry)
7201f5207b7SJohn Levon entry = NULL;
7211f5207b7SJohn Levon vrfy_bb_flow(bb);
7221f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
7231f5207b7SJohn Levon assert(!entry);
7241f5207b7SJohn Levon }
7251f5207b7SJohn Levon
pack_basic_blocks(struct entrypoint * ep)7261f5207b7SJohn Levon void pack_basic_blocks(struct entrypoint *ep)
7271f5207b7SJohn Levon {
7281f5207b7SJohn Levon struct basic_block *bb;
7291f5207b7SJohn Levon
7301f5207b7SJohn Levon /* See if we can merge a bb into another one.. */
7311f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
7321f5207b7SJohn Levon struct instruction *first, *insn;
7331f5207b7SJohn Levon struct basic_block *parent, *child, *last;
7341f5207b7SJohn Levon
7351f5207b7SJohn Levon if (!bb_reachable(bb))
7361f5207b7SJohn Levon continue;
7371f5207b7SJohn Levon
7381f5207b7SJohn Levon /*
7391f5207b7SJohn Levon * Just a branch?
7401f5207b7SJohn Levon */
7411f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, first) {
7421f5207b7SJohn Levon if (!first->bb)
7431f5207b7SJohn Levon continue;
7441f5207b7SJohn Levon switch (first->opcode) {
745*c85f09ccSJohn Levon case OP_NOP:
746*c85f09ccSJohn Levon case OP_INLINED_CALL:
7471f5207b7SJohn Levon continue;
7481f5207b7SJohn Levon case OP_CBR:
7491f5207b7SJohn Levon case OP_BR: {
7501f5207b7SJohn Levon struct basic_block *replace;
7511f5207b7SJohn Levon replace = rewrite_branch_bb(bb, first);
7521f5207b7SJohn Levon if (replace) {
7531f5207b7SJohn Levon kill_bb(bb);
7541f5207b7SJohn Levon goto no_merge;
7551f5207b7SJohn Levon }
7561f5207b7SJohn Levon }
7571f5207b7SJohn Levon /* fallthrough */
7581f5207b7SJohn Levon default:
7591f5207b7SJohn Levon goto out;
7601f5207b7SJohn Levon }
7611f5207b7SJohn Levon } END_FOR_EACH_PTR(first);
7621f5207b7SJohn Levon
7631f5207b7SJohn Levon out:
7641f5207b7SJohn Levon /*
7651f5207b7SJohn Levon * See if we only have one parent..
7661f5207b7SJohn Levon */
7671f5207b7SJohn Levon last = NULL;
7681f5207b7SJohn Levon FOR_EACH_PTR(bb->parents, parent) {
7691f5207b7SJohn Levon if (last) {
7701f5207b7SJohn Levon if (last != parent)
7711f5207b7SJohn Levon goto no_merge;
7721f5207b7SJohn Levon continue;
7731f5207b7SJohn Levon }
7741f5207b7SJohn Levon last = parent;
7751f5207b7SJohn Levon } END_FOR_EACH_PTR(parent);
7761f5207b7SJohn Levon
7771f5207b7SJohn Levon parent = last;
7781f5207b7SJohn Levon if (!parent || parent == bb)
7791f5207b7SJohn Levon continue;
7801f5207b7SJohn Levon
7811f5207b7SJohn Levon /*
7821f5207b7SJohn Levon * Goodie. See if the parent can merge..
7831f5207b7SJohn Levon */
7841f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) {
7851f5207b7SJohn Levon if (child != bb)
7861f5207b7SJohn Levon goto no_merge;
7871f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
7881f5207b7SJohn Levon
7891f5207b7SJohn Levon /*
7901f5207b7SJohn Levon * Merge the two.
7911f5207b7SJohn Levon */
792*c85f09ccSJohn Levon repeat_phase |= REPEAT_CFG_CLEANUP;
7931f5207b7SJohn Levon
7941f5207b7SJohn Levon parent->children = bb->children;
7951f5207b7SJohn Levon bb->children = NULL;
7961f5207b7SJohn Levon bb->parents = NULL;
7971f5207b7SJohn Levon
7981f5207b7SJohn Levon FOR_EACH_PTR(parent->children, child) {
7991f5207b7SJohn Levon replace_bb_in_list(&child->parents, bb, parent, 0);
8001f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
8011f5207b7SJohn Levon
8021f5207b7SJohn Levon kill_instruction(delete_last_instruction(&parent->insns));
8031f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
804*c85f09ccSJohn Levon if (!insn->bb)
805*c85f09ccSJohn Levon continue;
806*c85f09ccSJohn Levon assert(insn->bb == bb);
807*c85f09ccSJohn Levon insn->bb = parent;
8081f5207b7SJohn Levon add_instruction(&parent->insns, insn);
8091f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
8101f5207b7SJohn Levon bb->insns = NULL;
8111f5207b7SJohn Levon
8121f5207b7SJohn Levon no_merge:
8131f5207b7SJohn Levon /* nothing to do */;
8141f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
8151f5207b7SJohn Levon }
8161f5207b7SJohn Levon
8171f5207b7SJohn Levon
818