X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeverify.c;h=331f3d749432fed40732990c6ca055028e9bd087;hb=3c3425a50a1d721b74a015c6812257e32feeac85;hp=a55114ade2ad7351803b17efdfa07f09390574a6;hpb=1a3b7d363474ab544c13093a2f0b578718d37c7a;p=libfirm diff --git a/ir/be/beverify.c b/ir/be/beverify.c index a55114ade..331f3d749 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -22,11 +22,11 @@ * @brief Various verify routines that check a scheduled graph for correctness. * @author Matthias Braun * @date 05.05.2006 - * @version $Id$ */ #include "config.h" #include +#include #include "bitset.h" #include "set.h" @@ -62,9 +62,6 @@ typedef struct be_verify_register_pressure_env_t_ { */ static void print_living_values(FILE *F, const ir_nodeset_t *live_nodes) { - ir_nodeset_iterator_t iter; - ir_node *node; - ir_fprintf(F, "\t"); foreach_ir_nodeset(live_nodes, node, iter) { ir_fprintf(F, "%+F ", node); @@ -72,6 +69,12 @@ static void print_living_values(FILE *F, const ir_nodeset_t *live_nodes) ir_fprintf(F, "\n"); } +static const char *get_irg_name(ir_graph *irg) +{ + ir_entity *entity = get_irg_entity(irg); + return get_entity_ld_name(entity); +} + /** * Check if number of live nodes never exceeds the number of available registers. */ @@ -79,7 +82,6 @@ static void verify_liveness_walker(ir_node *block, void *data) { be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data; ir_nodeset_t live_nodes; - ir_node *irn; int pressure; /* collect register pressure info, start with end of a block */ @@ -92,7 +94,7 @@ static void verify_liveness_walker(ir_node *block, void *data) pressure = ir_nodeset_size(&live_nodes); if (pressure > env->registers_available) { ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n", - block, get_irg_dump_name(env->irg), pressure, env->registers_available); + block, get_irg_name(env->irg), pressure, env->registers_available); print_living_values(stderr, &live_nodes); env->problem_found = 1; } @@ -108,7 +110,7 @@ static void verify_liveness_walker(ir_node *block, void *data) if (pressure > env->registers_available) { ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n", - irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available); + irn, block, get_irg_name(env->irg), pressure, env->registers_available); print_living_values(stderr, &live_nodes); env->problem_found = 1; assert(0); @@ -124,25 +126,21 @@ int be_verify_register_pressure(ir_graph *irg, const arch_register_class_t *cls) { be_verify_register_pressure_env_t env; - env.lv = be_liveness(irg); + env.lv = be_liveness_new(irg); env.irg = irg; env.cls = cls; env.registers_available = be_get_n_allocatable_regs(irg, cls); env.problem_found = 0; - be_liveness_assure_sets(env.lv); + be_liveness_compute_sets(env.lv); irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env); be_liveness_free(env.lv); return ! env.problem_found; } - - /*--------------------------------------------------------------------------- */ - - typedef struct be_verify_schedule_env_t_ { int problem_found; /**< flags indicating a problem */ bitset_t *scheduled; /**< bitset of scheduled nodes */ @@ -155,7 +153,6 @@ typedef struct be_verify_schedule_env_t_ { static void verify_schedule_walker(ir_node *block, void *data) { be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data; - ir_node *node; ir_node *non_phi_found = NULL; ir_node *cfchange_found = NULL; int last_timestep = INT_MIN; @@ -169,7 +166,6 @@ static void verify_schedule_walker(ir_node *block, void *data) * (except mode_X projs) */ sched_foreach(block, node) { - int i, arity; int timestep; /* this node is scheduled */ @@ -198,7 +194,7 @@ static void verify_schedule_walker(ir_node *block, void *data) if (is_Phi(node)) { if (non_phi_found != NULL) { ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes (for example %+F) in block %+F (%s)\n", - node, non_phi_found, block, get_irg_dump_name(env->irg)); + node, non_phi_found, block, get_irg_name(env->irg)); env->problem_found = 1; } } else { @@ -210,7 +206,7 @@ static void verify_schedule_walker(ir_node *block, void *data) /* check, that only one CF operation is scheduled */ if (cfchange_found != NULL) { ir_fprintf(stderr, "Verify Warning: Additional control flow changing node %+F scheduled after %+F in block %+F (%s)\n", - node, block, cfchange_found, get_irg_dump_name(env->irg)); + node, block, cfchange_found, get_irg_name(env->irg)); env->problem_found = 1; } else { cfchange_found = node; @@ -219,13 +215,15 @@ static void verify_schedule_walker(ir_node *block, void *data) /* proj and keepany aren't real instructions... */ if (!is_Proj(node) && !be_is_Keep(node)) { ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); + node, block, get_irg_name(env->irg)); env->problem_found = 1; } } /* Check that all uses come before their definitions */ if (!is_Phi(node)) { + int i; + int arity; sched_timestep_t nodetime = sched_get_time_step(node); for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node *arg = get_irn_n(node, i); @@ -235,7 +233,7 @@ static void verify_schedule_walker(ir_node *block, void *data) if (sched_get_time_step(arg) >= nodetime) { ir_fprintf(stderr, "Verify Warning: Value %+F used by %+F before it was defined in block %+F (%s)\n", - arg, node, block, get_irg_dump_name(env->irg)); + arg, node, block, get_irg_name(env->irg)); env->problem_found = 1; } } @@ -244,7 +242,7 @@ static void verify_schedule_walker(ir_node *block, void *data) /* Check that no dead nodes are scheduled */ if (get_irn_n_edges(node) == 0) { ir_fprintf(stderr, "Verify warning: Node %+F is dead but scheduled in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); + node, block, get_irg_name(env->irg)); env->problem_found = 1; } @@ -258,6 +256,7 @@ static void verify_schedule_walker(ir_node *block, void *data) prev = sched_prev(prev); while (true) { + int i; for (i = 0; i < arity; ++i) { ir_node *in = get_irn_n(node, i); in = skip_Proj(in); @@ -272,7 +271,7 @@ static void verify_schedule_walker(ir_node *block, void *data) } if (!found) { ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); + node, block, get_irg_name(env->irg)); env->problem_found = 1; } } @@ -282,12 +281,12 @@ static void verify_schedule_walker(ir_node *block, void *data) static void check_schedule(ir_node *node, void *data) { be_verify_schedule_env_t *env = (be_verify_schedule_env_t*)data; - bool should_be = !is_Proj(node) && !(arch_irn_get_flags(node) & arch_irn_flags_not_scheduled); + bool should_be = !is_Proj(node) && !(arch_get_irn_flags(node) & arch_irn_flags_not_scheduled); bool scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)); if (should_be != scheduled) { ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n", - node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not"); + node, get_nodes_block(node), get_irg_name(env->irg), should_be ? "" : " not"); env->problem_found = 1; } } @@ -342,20 +341,20 @@ static spill_t *find_spill(be_verify_spillslots_env_t *env, ir_node *node) spill_t spill; spill.spill = node; - return (spill_t*)set_find(env->spills, &spill, sizeof(spill), HASH_PTR(node)); + return set_find(spill_t, env->spills, &spill, sizeof(spill), hash_ptr(node)); } static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) { spill_t spill, *res; - int hash = HASH_PTR(node); + int hash = hash_ptr(node); spill.spill = node; - res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); + res = set_find(spill_t, env->spills, &spill, sizeof(spill), hash); if (res == NULL) { spill.ent = ent; - res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash); + res = set_insert(spill_t, env->spills, &spill, sizeof(spill), hash); } return res; @@ -384,7 +383,7 @@ static void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_e { if (ent == NULL) { ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have an entity assigned\n", - node, get_nodes_block(node), get_irg_dump_name(env->irg)); + node, get_nodes_block(node), get_irg_name(env->irg)); } } @@ -396,7 +395,7 @@ static void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_nod if (spillent != ent) { ir_fprintf(stderr, "Verify warning: Spill %+F has different entity than reload %+F in block %+F(%s)\n", - node, reload, get_nodes_block(node), get_irg_dump_name(env->irg)); + node, reload, get_nodes_block(node), get_irg_name(env->irg)); env->problem_found = 1; } } @@ -405,7 +404,7 @@ static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_n { int i, arity; spill_t spill, *res; - int hash = HASH_PTR(node); + int hash = hash_ptr(node); int out; ir_node* memperm; ir_entity *spillent; @@ -419,18 +418,18 @@ static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_n be_check_entity(env, memperm, spillent); if (spillent != ent) { ir_fprintf(stderr, "Verify warning: MemPerm %+F has different entity than reload %+F in block %+F(%s)\n", - node, reload, get_nodes_block(node), get_irg_dump_name(env->irg)); + node, reload, get_nodes_block(node), get_irg_name(env->irg)); env->problem_found = 1; } spill.spill = node; - res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); + res = set_find(spill_t, env->spills, &spill, sizeof(spill), hash); if (res != NULL) { return; } spill.ent = spillent; - res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash); + res = set_insert(spill_t, env->spills, &spill, sizeof(spill), hash); for (i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) { ir_node* arg = get_irn_n(memperm, i + 1); @@ -444,18 +443,18 @@ static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_no { int i, arity; spill_t spill, *res; - int hash = HASH_PTR(node); + int hash = hash_ptr(node); assert(is_Phi(node)); spill.spill = node; - res = (spill_t*)set_find(env->spills, &spill, sizeof(spill), hash); + res = set_find(spill_t, env->spills, &spill, sizeof(spill), hash); if (res != NULL) { return; } spill.ent = ent; - res = (spill_t*)set_insert(env->spills, &spill, sizeof(spill), hash); + res = set_insert(spill_t, env->spills, &spill, sizeof(spill), hash); /* is 1 of the arguments a spill? */ for (i = 0, arity = get_irn_arity(node); i < arity; ++i) { @@ -476,7 +475,7 @@ static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *rel /* Disabled for now, spills might get transformed by the backend */ #if 0 ir_fprintf(stderr, "Verify warning: No spill, memperm or memphi attached to node %+F found from node %+F in block %+F(%s)\n", - node, reload, get_nodes_block(node), get_irg_dump_name(env->irg)); + node, reload, get_nodes_block(node), get_irg_name(env->irg)); env->problem_found = 1; #endif } @@ -490,13 +489,13 @@ static void collect_spills_walker(ir_node *node, void *data) { be_verify_spillslots_env_t *env = (be_verify_spillslots_env_t*)data; - if (arch_irn_classify(node) & arch_irn_class_reload) { + if (be_is_Reload(node)) { ir_node *spill = get_memory_edge(node); ir_entity *ent; if (spill == NULL) { ir_fprintf(stderr, "Verify warning: No spill attached to reload %+F in block %+F(%s)\n", - node, get_nodes_block(node), get_irg_dump_name(env->irg)); + node, get_nodes_block(node), get_irg_name(env->irg)); env->problem_found = 1; return; } @@ -512,11 +511,10 @@ static void check_spillslot_interference(be_verify_spillslots_env_t *env) { int spillcount = set_count(env->spills); spill_t **spills = ALLOCAN(spill_t*, spillcount); - spill_t *spill; int i; i = 0; - foreach_set(env->spills, spill_t*, spill) { + foreach_set(env->spills, spill_t, spill) { spills[i++] = spill; } @@ -532,8 +530,8 @@ static void check_spillslot_interference(be_verify_spillslots_env_t *env) if (my_values_interfere(sp1->spill, sp2->spill)) { ir_fprintf(stderr, "Verify warning: Spillslots for %+F in block %+F(%s) and %+F in block %+F(%s) interfere\n", - sp1->spill, get_nodes_block(sp1->spill), get_irg_dump_name(env->irg), - sp2->spill, get_nodes_block(sp2->spill), get_irg_dump_name(env->irg)); + sp1->spill, get_nodes_block(sp1->spill), get_irg_name(env->irg), + sp2->spill, get_nodes_block(sp2->spill), get_irg_name(env->irg)); env->problem_found = 1; my_values_interfere(sp1->spill, sp2->spill); } @@ -553,8 +551,8 @@ static void check_lonely_spills(ir_node *node, void *data) } if (spill == NULL) { - ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) not connected to a reaload\n", - node, get_nodes_block(node), get_irg_dump_name(env->irg)); + ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) not connected to a reload\n", + node, get_nodes_block(node), get_irg_name(env->irg)); } } } @@ -593,7 +591,6 @@ int be_verify_spillslots(ir_graph *irg) */ static int my_values_interfere(const ir_node *a, const ir_node *b) { - const ir_edge_t *edge; ir_node *bb; int a2b = value_dominates(a, b); int b2a = value_dominates(b, a); @@ -655,24 +652,25 @@ static int my_values_interfere(const ir_node *a, const ir_node *b) static const arch_env_t *arch_env; static ir_graph *irg; static be_lv_t *lv; -static int problem_found; -static const arch_register_class_t *regclass; -static ir_node **registers; +static bool problem_found; +static const ir_node **registers; -static void check_output_constraints(ir_node *node) +static void check_output_constraints(const ir_node *node) { + if (arch_get_irn_reg_class(node) == NULL) + return; + /* verify output register */ - if (arch_get_irn_reg_class_out(node) == regclass) { - const arch_register_t *reg = arch_get_irn_register(node); - if (reg == NULL) { - ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n", - node, get_nodes_block(node), get_irg_dump_name(irg)); - problem_found = 1; - } else if (!(reg->type & arch_register_type_joker) && !arch_reg_out_is_allocatable(node, reg)) { - ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n", - reg->name, node, get_nodes_block(node), get_irg_dump_name(irg)); - problem_found = 1; - } + const arch_register_req_t *req = arch_get_irn_register_req(node); + const arch_register_t *reg = arch_get_irn_register(node); + if (reg == NULL) { + ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n", + node, get_nodes_block(node), get_irg_name(irg)); + problem_found = true; + } else if (!arch_reg_is_allocatable(req, reg)) { + ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n", + reg->name, node, get_nodes_block(node), get_irg_name(irg)); + problem_found = true; } } @@ -684,13 +682,13 @@ static void check_input_constraints(ir_node *node) /* verify input register */ arity = get_irn_arity(node); for (i = 0; i < arity; ++i) { - const arch_register_req_t *req = arch_get_in_register_req(node, i); + const arch_register_req_t *req = arch_get_irn_register_req_in(node, i); ir_node *pred = get_irn_n(node, i); - const arch_register_req_t *pred_req = arch_get_register_req_out(pred); + const arch_register_req_t *pred_req = arch_get_irn_register_req(pred); if (is_Bad(pred)) { ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) has Bad as input %d\n", - node, get_nodes_block(node), get_irg_dump_name(irg), i); + node, get_nodes_block(node), get_irg_name(irg), i); problem_found = 1; continue; } @@ -699,7 +697,7 @@ static void check_input_constraints(ir_node *node) if (req->width > pred_req->width) { ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) register width of value at input %d too small\n", - node, get_nodes_block(node), get_irg_dump_name(irg), i); + node, get_nodes_block(node), get_irg_name(irg), i); problem_found = 1; } @@ -707,19 +705,19 @@ static void check_input_constraints(ir_node *node) if (req->type & arch_register_req_type_aligned) { if (reg->index % req->width != 0) { ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) register allignment not fulfilled\n", - node, get_nodes_block(node), get_irg_dump_name(irg), i); + node, get_nodes_block(node), get_irg_name(irg), i); problem_found = 1; } } if (reg == NULL) { ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned (%+F input constraint)\n", - pred, get_nodes_block(pred), get_irg_dump_name(irg), node); + pred, get_nodes_block(pred), get_irg_name(irg), node); problem_found = 1; continue; - } else if (!(reg->type & arch_register_type_joker) && ! arch_reg_is_allocatable(node, i, reg)) { + } else if (!arch_reg_is_allocatable(req, reg)) { ir_fprintf(stderr, "Verify warning: Register %s as input %d of %+F not allowed (register constraint) in block %+F(%s)\n", - reg->name, i, node, get_nodes_block(node), get_irg_dump_name(irg)); + reg->name, i, node, get_nodes_block(node), get_irg_name(irg)); problem_found = 1; } } @@ -727,8 +725,6 @@ static void check_input_constraints(ir_node *node) /* phis should be NOPs at this point, which means all input regs * must be the same as the output reg */ if (is_Phi(node)) { - int i, arity; - reg = arch_get_irn_register(node); arity = get_irn_arity(node); @@ -741,135 +737,257 @@ static void check_input_constraints(ir_node *node) const char *reg_name = reg != NULL ? reg->name : "(null)"; ir_fprintf(stderr, "Verify warning: Input %d of %+F in block %+F(%s) uses register %s instead of %s\n", i, node, get_nodes_block(node), - get_irg_dump_name(irg), pred_name, reg_name); + get_irg_name(irg), pred_name, reg_name); problem_found = 1; } } } } -static void value_used(ir_node *block, ir_node *node) +static void value_used(const ir_node *block, const ir_node *node) { - const arch_register_t *reg; - ir_node *reg_node; - - if (arch_get_irn_reg_class_out(node) != regclass) - return; + const arch_register_t *reg = arch_get_irn_register(node); + const arch_register_req_t *req; + unsigned i; + unsigned idx; - reg = arch_get_irn_register(node); if (reg == NULL || reg->type & arch_register_type_virtual) return; - reg_node = registers[reg->index]; - if (reg_node != NULL && reg_node != node) { - ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s) (nodes %+F %+F)\n", - reg->name, block, get_irg_dump_name(irg), - node, reg_node); - problem_found = 1; + req = arch_get_irn_register_req(node); + assert(req->width > 0); + idx = reg->global_index; + for (i = 0; i < req->width; ++i) { + const ir_node *reg_node = registers[idx+i]; + if (reg_node != NULL && reg_node != node) { + const arch_register_t *realreg = &arch_env->registers[idx+i]; + ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s) (nodes %+F %+F)\n", + realreg->name, block, get_irg_name(irg), + node, reg_node); + problem_found = true; + } + registers[idx+i] = node; } - - registers[reg->index] = node; } -static void value_def(ir_node *node) +static void value_def(const ir_node *node) { - const arch_register_t *reg; - ir_node *reg_node; - - if (arch_get_irn_reg_class_out(node) != regclass) - return; + const arch_register_t *reg = arch_get_irn_register(node); + const arch_register_req_t *req; + unsigned idx; + unsigned i; - reg = arch_get_irn_register(node); if (reg == NULL || reg->type & arch_register_type_virtual) return; - reg_node = registers[reg->index]; + req = arch_get_irn_register_req(node); + assert(req->width > 0); + idx = reg->global_index; + for (i = 0; i < req->width; ++i) { + const ir_node *reg_node = registers[idx+i]; - if (reg_node != node) { - ir_fprintf(stderr, "Verify warning: Node %+F not registered as value for Register %s (but %+F) in block %+F(%s)\n", - node, reg->name, reg_node, get_nodes_block(node), get_irg_dump_name(irg)); - problem_found = 1; + /* a little cheat, since its so hard to remove all outedges to dead code + * in the backend. This particular case should never be a problem. */ + if (reg_node == NULL && get_irn_n_edges(node) == 0) + return; + + if (reg_node != node) { + const arch_register_t *realreg = &arch_env->registers[idx+i]; + ir_fprintf(stderr, "Verify warning: Node %+F not registered as value for Register %s (but %+F) in block %+F(%s)\n", + node, realreg->name, reg_node, get_nodes_block(node), + get_irg_name(irg)); + problem_found = true; + } + registers[idx+i] = NULL; } - registers[reg->index] = NULL; } static void verify_block_register_allocation(ir_node *block, void *data) { - int i, nregclasses; - (void) data; - - nregclasses = arch_env->n_register_classes; - for (i = 0; i < nregclasses; ++i) { - ir_node *node; - int idx, i2, n_regs; + unsigned i; + unsigned n_regs; - regclass = &arch_env->register_classes[i]; + (void) data; - assert(lv->nodes && "live sets must be computed"); + assert(lv->sets_valid && "live sets must be computed"); - n_regs = arch_register_class_n_regs(regclass); - registers = ALLOCANZ(ir_node*, n_regs); + n_regs = arch_env->n_registers; + registers = ALLOCANZ(const ir_node*, n_regs); - be_lv_foreach(lv, block, be_lv_state_end, idx) { - ir_node *node = be_lv_get_irn(lv, block, idx); - value_used(block, node); - } + be_lv_foreach(lv, block, be_lv_state_end, lv_node) { + value_used(block, lv_node); + } - sched_foreach_reverse(block, node) { - int arity; + sched_foreach_reverse(block, node) { + int arity; - if (get_irn_mode(node) == mode_T) { - const ir_edge_t *edge; - foreach_out_edge(node, edge) { - ir_node *def = get_edge_src_irn(edge); - value_def(def); - check_output_constraints(def); - } - } else { - value_def(node); - check_output_constraints(node); + if (get_irn_mode(node) == mode_T) { + foreach_out_edge(node, edge) { + ir_node *def = get_edge_src_irn(edge); + value_def(def); + check_output_constraints(def); } + } else { + value_def(node); + check_output_constraints(node); + } - check_input_constraints(node); + check_input_constraints(node); - /* process uses. (Phi inputs are no real uses) */ - if (!is_Phi(node)) { - arity = get_irn_arity(node); - for (i2 = 0; i2 < arity; ++i2) { - ir_node *use = get_irn_n(node, i2); - value_used(block, use); - } + /* process uses. (Phi inputs are no real uses) */ + if (!is_Phi(node)) { + int in; + arity = get_irn_arity(node); + for (in = 0; in < arity; ++in) { + ir_node *use = get_irn_n(node, in); + value_used(block, use); } } + } - be_lv_foreach(lv, block, be_lv_state_in, idx) { - ir_node *node = be_lv_get_irn(lv, block, idx); - value_def(node); - } + be_lv_foreach(lv, block, be_lv_state_in, lv_node) { + value_def(lv_node); + } - /* set must be empty now */ - for (i2 = 0; i2 < n_regs; ++i2) { - if (registers[i2] == NULL) - continue; + /* set must be empty now */ + for (i = 0; i < n_regs; ++i) { + if (registers[i] == NULL) + continue; - ir_fprintf(stderr, "Verify warning: Node %+F not live-in and no def found in block %+F(%s)\n", - registers[i2], block, get_irg_dump_name(irg)); - problem_found = 1; - } + ir_fprintf(stderr, "Verify warning: Node %+F not live-in and no def found in block %+F(%s)\n", + registers[i], block, get_irg_name(irg)); + problem_found = true; } } -int be_verify_register_allocation(ir_graph *new_irg) +bool be_verify_register_allocation(ir_graph *new_irg) { irg = new_irg; arch_env = be_get_irg_arch_env(irg); - lv = be_liveness(irg); - problem_found = 0; + lv = be_liveness_new(irg); + problem_found = false; - be_liveness_assure_sets(lv); + be_liveness_compute_sets(lv); irg_block_walk_graph(irg, verify_block_register_allocation, NULL, NULL); - be_liveness_free(lv); return !problem_found; } + +/*--------------------------------------------------------------------------- */ + +/** + * Walker: checks that every predecessors of a node dominates the node. + */ +static void dom_check(ir_node *irn, void *data) +{ + bool *problem_found = (bool*)data; + + if (!is_Block(irn) && irn != get_irg_end(get_irn_irg(irn))) { + int i, n; + ir_node *bl = get_nodes_block(irn); + + for (i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *op = get_irn_n(irn, i); + ir_node *def_bl = get_nodes_block(op); + ir_node *use_bl = bl; + + if (is_Phi(irn)) + use_bl = get_Block_cfgpred_block(bl, i); + + if (get_irn_opcode(use_bl) != iro_Bad + && get_irn_opcode(def_bl) != iro_Bad + && !block_dominates(def_bl, use_bl)) { + ir_fprintf(stderr, "Verify warning: %+F in %+F must dominate %+F for user %+F (%s)\n", op, def_bl, use_bl, irn, get_irg_name(get_irn_irg(op))); + *problem_found = true; + } + } + } +} + +/* Check, if the SSA dominance property is fulfilled. */ +bool be_check_dominance(ir_graph *irg) +{ + bool problem_found = false; + + assure_doms(irg); + irg_walk_graph(irg, dom_check, NULL, &problem_found); + + return !problem_found; +} + +/*--------------------------------------------------------------------------- */ + +typedef struct lv_walker_t { + be_lv_t *lv; + void *data; +} lv_walker_t; + +static const char *lv_flags_to_str(unsigned flags) +{ + static const char *states[] = { + "---", + "i--", + "-e-", + "ie-", + "--o", + "i-o", + "-eo", + "ieo" + }; + + return states[flags & 7]; +} + +static void lv_check_walker(ir_node *bl, void *data) +{ + lv_walker_t *w = (lv_walker_t*)data; + be_lv_t *lv = w->lv; + be_lv_t *fresh = (be_lv_t*)w->data; + + be_lv_info_t *curr = ir_nodehashmap_get(be_lv_info_t, &fresh->map, bl); + be_lv_info_t *fr = ir_nodehashmap_get(be_lv_info_t, &fresh->map, bl); + + if (!fr && curr && curr[0].head.n_members > 0) { + unsigned i; + + ir_fprintf(stderr, "%+F liveness should be empty but current liveness contains:\n", bl); + for (i = 0; i < curr[0].head.n_members; ++i) { + ir_fprintf(stderr, "\t%+F\n", get_idx_irn(lv->irg, curr[1 + i].node.idx)); + } + } + + else if (curr) { + unsigned n_curr = curr[0].head.n_members; + unsigned n_fresh = fr[0].head.n_members; + + unsigned i; + + if (n_curr != n_fresh) { + ir_fprintf(stderr, "%+F: liveness set sizes differ. curr %d, correct %d\n", bl, n_curr, n_fresh); + + ir_fprintf(stderr, "current:\n"); + for (i = 0; i < n_curr; ++i) { + be_lv_info_node_t *n = &curr[1 + i].node; + ir_fprintf(stderr, "%+F %u %+F %s\n", bl, i, get_idx_irn(lv->irg, n->idx), lv_flags_to_str(n->flags)); + } + + ir_fprintf(stderr, "correct:\n"); + for (i = 0; i < n_fresh; ++i) { + be_lv_info_node_t *n = &fr[1 + i].node; + ir_fprintf(stderr, "%+F %u %+F %s\n", bl, i, get_idx_irn(lv->irg, n->idx), lv_flags_to_str(n->flags)); + } + } + } +} + +void be_liveness_check(be_lv_t *lv) +{ + lv_walker_t w; + be_lv_t *fresh = be_liveness_new(lv->irg); + + w.lv = lv; + w.data = fresh; + irg_block_walk_graph(lv->irg, lv_check_walker, NULL, &w); + be_liveness_free(fresh); +}