X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeverify.c;h=27913cd9f9e689879ffab44af87a080dbab42533;hb=8d07d17eb2ade0b6b4aef0ebd68d6af3cc368b06;hp=7fa7d4e1ad7268f7dca651e81cf9d36a218ad597;hpb=d287370d1c47c10de2b94c7d51968d065bf8d300;p=libfirm diff --git a/ir/be/beverify.c b/ir/be/beverify.c index 7fa7d4e1a..27913cd9f 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -62,11 +62,12 @@ typedef struct be_verify_register_pressure_env_t_ { /** * Print all nodes of a pset into a file. */ -static void print_living_values(FILE *F, pset *live_nodes) { +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_pset(live_nodes, node) { + foreach_ir_nodeset(live_nodes, node, iter) { ir_fprintf(F, "%+F ", node); } ir_fprintf(F, "\n"); @@ -77,18 +78,22 @@ static void print_living_values(FILE *F, pset *live_nodes) { */ static void verify_liveness_walker(ir_node *block, void *data) { be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data; - pset *live_nodes = pset_new_ptr_default(); + ir_nodeset_t live_nodes; ir_node *irn; int pressure; /* collect register pressure info, start with end of a block */ - be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, live_nodes); + // ir_fprintf(stderr, "liveness check %+F\n", block); + ir_nodeset_init(&live_nodes); + be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, + &live_nodes); - pressure = pset_count(live_nodes); + // print_living_values(stderr, &live_nodes); + 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); - print_living_values(stderr, live_nodes); + print_living_values(stderr, &live_nodes); env->problem_found = 1; } @@ -96,18 +101,20 @@ static void verify_liveness_walker(ir_node *block, void *data) { if (is_Phi(irn)) break; - be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes); + // print_living_values(stderr, &live_nodes); + be_liveness_transfer(env->arch_env, env->cls, irn, &live_nodes); - pressure = pset_count(live_nodes); + pressure = ir_nodeset_size(&live_nodes); 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); - print_living_values(stderr, live_nodes); + print_living_values(stderr, &live_nodes); env->problem_found = 1; + assert(0); } } - del_pset(live_nodes); + ir_nodeset_destroy(&live_nodes); } /** @@ -118,13 +125,14 @@ int be_verify_register_pressure(const be_irg_t *birg, ir_graph *irg) { be_verify_register_pressure_env_t env; - env.lv = be_liveness(irg); + env.lv = be_liveness(birg); env.irg = irg; env.arch_env = birg->main_env->arch_env; env.cls = cls; env.registers_available = env.cls->n_regs - be_put_ignore_regs(birg, env.cls, NULL); env.problem_found = 0; + be_liveness_assure_sets(env.lv); irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env); be_liveness_free(env.lv); @@ -133,7 +141,7 @@ int be_verify_register_pressure(const be_irg_t *birg, -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -150,13 +158,11 @@ 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; - int non_phi_found = 0; + ir_node *non_phi_found = NULL; int cfchange_found = 0; - // TODO ask arch about delay branches + /* TODO ask arch about delay branches */ int delay_branches = 0; int last_timestep = INT_MIN; - ir_node *proj_keep_node = NULL; - int proj_keep_mode = 0; /* * Tests for the following things: @@ -170,20 +176,20 @@ static void verify_schedule_walker(ir_node *block, void *data) { int i, arity; int timestep; - // this node is scheduled + /* this node is scheduled */ if(bitset_is_set(env->scheduled, get_irn_idx(node))) { ir_fprintf(stderr, "Verify warning: %+F appears to be schedule twice\n"); env->problem_found = 1; } bitset_set(env->scheduled, get_irn_idx(node)); - // Check that scheduled nodes are in the correct block + /* Check that scheduled nodes are in the correct block */ if(get_nodes_block(node) != block) { ir_fprintf(stderr, "Verify warning: %+F is in block %+F but scheduled in %+F\n", node, get_nodes_block(node), block); env->problem_found = 1; } - // Check that timesteps are increasing + /* Check that timesteps are increasing */ timestep = sched_get_time_step(node); if(timestep <= last_timestep) { ir_fprintf(stderr, "Verify warning: Schedule timestep did not increase at node %+F\n", @@ -192,18 +198,18 @@ static void verify_schedule_walker(ir_node *block, void *data) { } last_timestep = timestep; - // Check that phis come before any other node + /* Check that phis come before any other node */ if (is_Phi(node)) { - if (non_phi_found) { - ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); + 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)); env->problem_found = 1; } } else { - non_phi_found = 1; + non_phi_found = node; } - // Check for control flow changing nodes + /* Check for control flow changing nodes */ if (is_cfop(node) && get_irn_opcode(node) != iro_Start) { /* check, that only one CF operation is scheduled */ if (cfchange_found == 1) { @@ -213,7 +219,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } cfchange_found = 1; } else if (cfchange_found) { - // proj and keepany aren't real instructions... + /* proj and keepany aren't real instructions... */ if(!is_Proj(node) && !be_is_Keep(node)) { /* check for delay branches */ if (delay_branches == 0) { @@ -226,7 +232,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // Check that all uses come before their definitions + /* Check that all uses come before their definitions */ if(!is_Phi(node)) { int nodetime = sched_get_time_step(node); for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { @@ -243,63 +249,32 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // Check that no dead nodes are scheduled + /* 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)); env->problem_found = 1; } - // check that all projs/keeps are behind their nodes - if(proj_keep_mode == 0) { - if(is_Proj(node)) { - proj_keep_mode = 1; - proj_keep_node = get_Proj_pred(node); - if(get_Proj_pred(node) != sched_prev(node)) { - ir_fprintf(stderr, "Proj %+F not scheduled after by its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); - env->problem_found = 1; - } - } else if(be_is_Keep(node)) { - proj_keep_mode = 2; - proj_keep_node = get_irn_n(node, 0); - if(proj_keep_node != sched_prev(node)) { - ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); - env->problem_found = 1; - } - - } - } else if(proj_keep_mode == 1) { - if(is_Proj(node)) { - if(get_Proj_pred(node) != proj_keep_node) { - ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); - env->problem_found = 1; - } - } else if(be_is_Keep(node)) { - ir_node *pred = get_irn_n(node, 0); - if(skip_Proj_const(pred) != proj_keep_node) { - ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); - env->problem_found = 1; - } else { - proj_keep_mode = 2; - } - } else { - proj_keep_mode = 0; - proj_keep_node = NULL; + if(be_is_Keep(node)) { + /* at least 1 of the keep arguments has to be it schedule + * predecessor */ + int arity = get_irn_arity(node); + int problem = 1; + ir_node *prev = sched_prev(node); + while(be_is_Keep(prev)) + prev = sched_prev(prev); + + for(i = 0; i < arity; ++i) { + ir_node *in = get_irn_n(node, i); + in = skip_Proj(in); + if(in == prev) + problem = 0; } - } else if(proj_keep_mode == 2) { - if(be_is_Keep(skip_Proj_const(node))) { - if(get_irn_n(node, 0) != proj_keep_node) { - ir_fprintf(stderr, "Proj %+F not scheduled after its pred node in block %+F (%s)\n", - node, block, get_irg_dump_name(env->irg)); - env->problem_found = 1; - } - } else { - proj_keep_mode = 0; - proj_keep_node = NULL; + if(problem) { + ir_fprintf(stderr, "%+F not scheduled after its pred node in block %+F (%s)\n", + node, block, get_irg_dump_name(env->irg)); + env->problem_found = 1; } } } @@ -316,17 +291,13 @@ static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) { if(is_Block(node)) return -1; + if(is_Proj(node)) + return 0; + if(get_irn_mode(node) == mode_M) { - if(is_Proj(node)) - return -1; if(is_Phi(node) || is_Sync(node) || is_Pin(node)) return 0; } - if(is_Proj(node)) { - if(get_irn_mode(node) == mode_X) - return 0; - return should_be_scheduled(env, get_Proj_pred(node)); - } if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad) return 0; @@ -377,7 +348,7 @@ int be_verify_schedule(const be_irg_t *birg) env.arch_env = birg->main_env->arch_env; irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env); - // check if all nodes are scheduled + /* check if all nodes are scheduled */ irg_walk_graph(env.irg, check_schedule, NULL, &env); return ! env.problem_found; @@ -385,7 +356,7 @@ int be_verify_schedule(const be_irg_t *birg) -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -405,6 +376,8 @@ typedef struct { static int cmp_spill(const void* d1, const void* d2, size_t size) { const spill_t* s1 = d1; const spill_t* s2 = d2; + (void) size; + return s1->spill != s2->spill; } @@ -524,7 +497,7 @@ static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_no spill.ent = ent; res = set_insert(env->spills, &spill, sizeof(spill), hash); - // is 1 of the arguments a spill? + /* is 1 of the arguments a spill? */ for(i = 0, arity = get_irn_arity(node); i < arity; ++i) { ir_node* arg = get_irn_n(node, i); collect(env, arg, reload, ent); @@ -539,7 +512,7 @@ static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *rel } else if(is_Phi(node) && get_irn_mode(node) == mode_M) { collect_memphi(env, node, reload, ent); } else { - // Disabled for now, spills might get transformed by the backend + /* 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)); @@ -556,7 +529,7 @@ static void collect_spills_walker(ir_node *node, void *data) { be_verify_spillslots_env_t *env = data; const arch_env_t *arch_env = env->arch_env; - // @@@ ia32_classify returns classification of Proj_pred :-/ + /* @@@ ia32_classify returns classification of Proj_pred :-/ */ if(is_Proj(node)) return; @@ -649,7 +622,7 @@ int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg) -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -700,7 +673,7 @@ static int my_values_interfere(const ir_node *a, const ir_node *b) { if(get_irn_opcode(user) == iro_End) continue; - // in case of phi arguments we compare with the block the value comes from + /* in case of phi arguments we compare with the block the value comes from */ if(is_Phi(user)) { ir_node *phiblock = get_nodes_block(user); if(phiblock == bb) @@ -717,19 +690,17 @@ 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; -typedef struct _be_verify_register_allocation_env_t { - const arch_env_t *arch_env; - ir_graph *irg; - be_lv_t *lv; - int problem_found; -} be_verify_register_allocation_env_t; - -static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) { - const arch_env_t *arch_env = env->arch_env; +static void check_register_constraints(ir_node *node) +{ const arch_register_t *reg; int i, arity; @@ -738,13 +709,12 @@ static void check_register_constraints(ir_node *node, be_verify_register_allocat reg = arch_get_irn_register(arch_env, 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(env->irg)); - env->problem_found = 1; - } - else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) { + node, get_nodes_block(node), get_irg_dump_name(irg)); + problem_found = 1; + } else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, 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(env->irg)); - env->problem_found = 1; + reg->name, node, get_nodes_block(node), get_irg_dump_name(irg)); + problem_found = 1; } } @@ -758,8 +728,8 @@ static void check_register_constraints(ir_node *node, be_verify_register_allocat 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(env->irg), i); - env->problem_found = 1; + node, get_nodes_block(node), get_irg_dump_name(irg), i); + problem_found = 1; continue; } @@ -768,104 +738,165 @@ static void check_register_constraints(ir_node *node, be_verify_register_allocat reg = arch_get_irn_register(arch_env, pred); if (reg == NULL) { - ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n", - pred, get_nodes_block(pred), get_irg_dump_name(env->irg)); - env->problem_found = 1; + 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); + problem_found = 1; continue; } else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, 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(env->irg)); - env->problem_found = 1; + reg->name, i, node, get_nodes_block(node), get_irg_dump_name(irg)); + problem_found = 1; } } -} - -static void check_register_allocation(be_verify_register_allocation_env_t *env, - const arch_register_class_t *regclass, pset *nodes) { - const arch_env_t *arch_env = env->arch_env; - const arch_register_t *reg = NULL; - int fail = 0; - bitset_t *registers = bitset_alloca(arch_register_class_n_regs(regclass)); - ir_node *node; - foreach_pset(nodes, node) { - if (arch_get_irn_reg_class(arch_env, node, -1) != regclass) - continue; + /* 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(arch_env, node); - /* this problem is already reported in 'check_register_constraints' */ - if (! reg) - continue; + arity = get_irn_arity(node); + for (i = 0; i < arity; ++i) { + ir_node *pred = get_Phi_pred(node, i); + const arch_register_t *pred_reg = arch_get_irn_register(arch_env, pred); - if (bitset_is_set(registers, reg->index)) { - pset_break(nodes); - fail = 1; - break; + if (reg != pred_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)); + problem_found = 1; + } } - bitset_set(registers, reg->index); } +} - if (fail) { - ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s)\n", - reg->name, get_nodes_block(node), get_irg_dump_name(env->irg)); - env->problem_found = 1; +static void value_used(ir_node *node) { + const arch_register_t *reg; + ir_node *reg_node; - foreach_pset(nodes, node) { - if (arch_get_irn_register(arch_env, node) == reg) { - ir_fprintf(stderr, " at node %+F\n", node); - } - } + if (arch_get_irn_reg_class(arch_env, node, -1) != regclass) + return; + + reg = arch_get_irn_register(arch_env, node); + if (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, get_nodes_block(node), get_irg_dump_name(irg), + node, reg_node); + problem_found = 1; + } + + registers[reg->index] = node; +} + +static void value_def(ir_node *node) +{ + const arch_register_t *reg; + ir_node *reg_node; + + if (arch_get_irn_reg_class(arch_env, node, -1) != regclass) + return; + + reg = arch_get_irn_register(arch_env, node); + if (reg->type & arch_register_type_virtual) + return; + + reg_node = registers[reg->index]; + + 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; } + registers[reg->index] = NULL; } static void verify_block_register_allocation(ir_node *block, void *data) { - be_verify_register_allocation_env_t *env = data; - const arch_env_t *arch_env = env->arch_env; - const arch_isa_t *isa = arch_env->isa; int i, nregclasses; + (void) data; - nregclasses = arch_isa_get_n_reg_class(isa); + nregclasses = arch_env_get_n_reg_class(arch_env); for (i = 0; i < nregclasses; ++i) { - const arch_register_class_t *regclass = arch_isa_get_reg_class(isa, i); - ir_node *node; - pset *live_nodes = pset_new_ptr_default(); + ir_node *node; + int i2; + + regclass = arch_env_get_reg_class(arch_env, i); + + int i; + + assert(lv->nodes && "live sets must be computed"); - be_liveness_end_of_block(env->lv, env->arch_env, regclass, block, live_nodes); - check_register_allocation(env, regclass, live_nodes); + int n_regs = arch_register_class_n_regs(regclass); + registers = alloca(n_regs * sizeof(registers[0])); + memset(registers, 0, n_regs * sizeof(registers[0])); + + be_lv_foreach(lv, block, be_lv_state_end, i) { + ir_node *node = be_lv_get_irn(lv, block, i); + value_used(node); + } 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); + } + } else { + value_def(node); + } + + check_register_constraints(node); if (is_Phi(node)) - break; + continue; + + arity = get_irn_arity(node); + for (i2 = 0; i2 < arity; ++i2) { + ir_node *use = get_irn_n(node, i2); + value_used(use); + } + } - be_liveness_transfer(env->arch_env, regclass, node, live_nodes); - check_register_allocation(env, regclass, live_nodes); - check_register_constraints(node, env); + be_lv_foreach(lv, block, be_lv_state_in, i) { + ir_node *node = be_lv_get_irn(lv, block, i); + value_def(node); } - del_pset(live_nodes); + /* set must be empty now */ + for (i2 = 0; i2 < n_regs; ++i2) { + if (registers[i2] == 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; + } } } -int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) { - be_verify_register_allocation_env_t env; +int be_verify_register_allocation(const be_irg_t *birg) { + arch_env = be_get_birg_arch_env(birg); + irg = be_get_birg_irg(birg); + lv = be_liveness(birg); + problem_found = 0; - env.arch_env = arch_env; - env.irg = irg; - env.lv = be_liveness(irg); - env.problem_found = 0; + be_liveness_assure_sets(lv); + irg_block_walk_graph(irg, verify_block_register_allocation, NULL, NULL); - irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env); + be_liveness_free(lv); - be_liveness_free(env.lv); - - return !env.problem_found; + return !problem_found; } -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -883,10 +914,14 @@ static void check_out_edges(ir_node *node, verify_out_dead_nodes_env *env) { return; mark_irn_visited(node); + /* we find too many (uncritical) dead nodes in block out edges */ + if(is_Block(node)) + return; + foreach_out_edge(node, edge) { ir_node* src = get_edge_src_irn(edge); - if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) { + if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(src)) { ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) only reachable through out edges from %+F\n", src, get_nodes_block(src), get_irg_dump_name(irg), node); env->problem_found = 1;