X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeverify.c;h=730325d4b7b953ef297dc1645fe53ab42e45c83c;hb=bd31a5350ce9e110c058b4ad2223d460c9eb5c4e;hp=2368a9a5389c8ee220b83a2067d9e5a5bb6a3ac3;hpb=205396c4f4f5abe7abd6dc2350c8c398a7623afc;p=libfirm diff --git a/ir/be/beverify.c b/ir/be/beverify.c index 2368a9a53..730325d4b 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -1,9 +1,28 @@ /* - * Author: Matthias Braun - * Date: 05.05.2006 - * Copyright: (c) Universitaet Karlsruhe - * License: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - * CVS-Id: $Id$ + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief Various verify routines that check a scheduled graph for correctness. + * @author Matthias Braun + * @date 05.05.2006 + * @version $Id$ */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -27,6 +46,7 @@ #include "besched_t.h" #include "benode_t.h" #include "beirg_t.h" +#include "beintlive_t.h" static int my_values_interfere(const ir_node *a, const ir_node *b); @@ -42,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"); @@ -57,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; } @@ -76,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); } /** @@ -98,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); @@ -113,7 +141,7 @@ int be_verify_register_pressure(const be_irg_t *birg, -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -132,7 +160,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { ir_node *node; int non_phi_found = 0; 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; @@ -141,25 +169,27 @@ static void verify_schedule_walker(ir_node *block, void *data) { * 1. Make sure that all phi nodes are scheduled at the beginning of the block * 2. There is 1 or no control flow changing node scheduled and exactly delay_branches operations after it. * 3. No value is defined after it has been used + * 4. mode_T nodes have all projs scheduled behind them followed by Keeps + * (except mode_X projs) */ sched_foreach(block, node) { 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", @@ -168,7 +198,7 @@ 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", @@ -179,7 +209,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { non_phi_found = 1; } - // 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) { @@ -189,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) { @@ -202,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) { @@ -219,12 +249,31 @@ 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; } + + 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); + for(i = 0; i < arity; ++i) { + ir_node *in = get_irn_n(node, i); + in = skip_Proj(in); + if(in == prev) + problem = 0; + } + 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; + } + } } /* check that all delay branches are filled (at least with NOPs) */ @@ -241,12 +290,20 @@ static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) { if(get_irn_mode(node) == mode_M) { if(is_Proj(node)) - return -1; + return 0; if(is_Phi(node) || is_Sync(node) || is_Pin(node)) return 0; } - if(is_Proj(node) && get_irn_mode(node) == mode_X) +#ifdef SCHEDULE_PROJS + if(is_Proj(node)) { + if(get_irn_mode(node) == mode_X) + return 0; + return should_be_scheduled(env, get_Proj_pred(node)); + } +#else + if(is_Proj(node)) return 0; +#endif if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad) return 0; @@ -297,7 +354,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; @@ -305,7 +362,7 @@ int be_verify_schedule(const be_irg_t *birg) -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -325,6 +382,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; } @@ -366,18 +425,21 @@ static ir_node *get_memory_edge(const ir_node *node) { return result; } -static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent); +static +void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent); -static void check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) { +static +void be_check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) { 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)); } } -static void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) { +static +void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) { ir_entity *spillent = arch_get_frame_entity(env->arch_env, node); - check_entity(env, node, spillent); + be_check_entity(env, node, spillent); get_spill(env, node, ent); if(spillent != ent) { @@ -401,7 +463,7 @@ static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_n out = get_Proj_proj(node); spillent = be_get_MemPerm_out_entity(memperm, out); - check_entity(env, memperm, spillent); + 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)); @@ -441,7 +503,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); @@ -456,7 +518,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)); @@ -473,7 +535,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; @@ -488,7 +550,7 @@ static void collect_spills_walker(ir_node *node, void *data) { return; } ent = arch_get_frame_entity(env->arch_env, node); - check_entity(env, node, ent); + be_check_entity(env, node, ent); collect(env, spill, node, ent); ARR_APP1(ir_node*, env->reloads, node); @@ -533,7 +595,7 @@ static void check_lonely_spills(ir_node *node, void *data) { spill_t *spill = find_spill(env, node); if(be_is_Spill(node)) { ir_entity *ent = arch_get_frame_entity(env->arch_env, node); - check_entity(env, node, ent); + be_check_entity(env, node, ent); } if(spill == NULL) { @@ -566,7 +628,7 @@ int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg) -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -617,7 +679,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) @@ -634,7 +696,7 @@ static int my_values_interfere(const ir_node *a, const ir_node *b) { -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -645,7 +707,9 @@ typedef struct _be_verify_register_allocation_env_t { int problem_found; } be_verify_register_allocation_env_t; -static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) { +static void check_register_constraints(ir_node *node, + be_verify_register_allocation_env_t *env) +{ const arch_env_t *arch_env = env->arch_env; const arch_register_t *reg; int i, arity; @@ -685,8 +749,8 @@ 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)); + 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(env->irg), node); env->problem_found = 1; continue; } @@ -699,14 +763,17 @@ static void check_register_constraints(ir_node *node, be_verify_register_allocat } static void check_register_allocation(be_verify_register_allocation_env_t *env, - const arch_register_class_t *regclass, pset *nodes) { + const arch_register_class_t *regclass, + ir_nodeset_t *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; + ir_nodeset_iterator_t iter; - foreach_pset(nodes, node) { + foreach_ir_nodeset(nodes, node, iter) { if (arch_get_irn_reg_class(arch_env, node, -1) != regclass) continue; @@ -717,7 +784,6 @@ static void check_register_allocation(be_verify_register_allocation_env_t *env, continue; if (bitset_is_set(registers, reg->index)) { - pset_break(nodes); fail = 1; break; } @@ -729,7 +795,7 @@ static void check_register_allocation(be_verify_register_allocation_env_t *env, reg->name, get_nodes_block(node), get_irg_dump_name(env->irg)); env->problem_found = 1; - foreach_pset(nodes, node) { + foreach_ir_nodeset(nodes, node, iter) { if (arch_get_irn_register(arch_env, node) == reg) { ir_fprintf(stderr, " at node %+F\n", node); } @@ -747,33 +813,37 @@ static void verify_block_register_allocation(ir_node *block, void *data) { 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_nodeset_t live_nodes; + + ir_nodeset_init(&live_nodes); - be_liveness_end_of_block(env->lv, env->arch_env, regclass, block, live_nodes); - check_register_allocation(env, regclass, live_nodes); + be_liveness_end_of_block(env->lv, env->arch_env, regclass, block, + &live_nodes); + check_register_allocation(env, regclass, &live_nodes); sched_foreach_reverse(block, node) { if (is_Phi(node)) break; - be_liveness_transfer(env->arch_env, regclass, node, live_nodes); - check_register_allocation(env, regclass, live_nodes); + be_liveness_transfer(env->arch_env, regclass, node, &live_nodes); + check_register_allocation(env, regclass, &live_nodes); check_register_constraints(node, env); } - del_pset(live_nodes); + ir_nodeset_destroy(&live_nodes); } } -int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) { +int be_verify_register_allocation(const be_irg_t *birg) { be_verify_register_allocation_env_t env; - env.arch_env = arch_env; - env.irg = irg; - env.lv = be_liveness(irg); + env.arch_env = be_get_birg_arch_env(birg); + env.irg = be_get_birg_irg(birg); + env.lv = be_liveness(birg); env.problem_found = 0; - irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env); + be_liveness_assure_sets(env.lv); + irg_block_walk_graph(env.irg, verify_block_register_allocation, NULL, &env); be_liveness_free(env.lv); @@ -782,7 +852,7 @@ int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) { -//--------------------------------------------------------------------------- +/*--------------------------------------------------------------------------- */ @@ -800,10 +870,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;