X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeverify.c;h=7cf226b9b8eaaab54e0e258c26961a5d422ffcbc;hb=9276447aec4972df060349e162f583c4898dfec8;hp=21e1a1769bfcf8d1088dfd7f4a0000faa239af28;hpb=657d38c542f0a034a737b8fa58637151cfa7b4ad;p=libfirm diff --git a/ir/be/beverify.c b/ir/be/beverify.c index 21e1a1769..7cf226b9b 100644 --- a/ir/be/beverify.c +++ b/ir/be/beverify.c @@ -1,14 +1,35 @@ /* - * 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" #endif +#include + #include "bitset.h" #include "set.h" #include "array.h" @@ -24,6 +45,8 @@ #include "belive.h" #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); @@ -90,7 +113,9 @@ static void verify_liveness_walker(ir_node *block, void *data) { /** * Start a walk over the irg and check the register pressure. */ -int be_verify_register_pressure(const be_irg_t *birg, const arch_register_class_t *cls, ir_graph *irg) { +int be_verify_register_pressure(const be_irg_t *birg, + const arch_register_class_t *cls, + ir_graph *irg) { be_verify_register_pressure_env_t env; env.lv = be_liveness(irg); @@ -106,9 +131,17 @@ int be_verify_register_pressure(const be_irg_t *birg, const arch_register_class_ return ! env.problem_found; } + + +//--------------------------------------------------------------------------- + + + typedef struct be_verify_schedule_env_t_ { - int problem_found; /**< flags indicating if there was a problem */ - ir_graph *irg; /**< the irg to check */ + int problem_found; /**< flags indicating if there was a problem */ + bitset_t *scheduled; /**< bitset of scheduled nodes */ + ir_graph *irg; /**< the irg to check */ + const arch_env_t *arch_env; /**< the arch_env */ } be_verify_schedule_env_t; /** @@ -121,6 +154,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { int cfchange_found = 0; // TODO ask arch about delay branches int delay_branches = 0; + int last_timestep = INT_MIN; /* * Tests for the following things: @@ -130,8 +164,31 @@ static void verify_schedule_walker(ir_node *block, void *data) { */ sched_foreach(block, node) { int i, arity; + int timestep; + + // 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 + 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 + timestep = sched_get_time_step(node); + if(timestep <= last_timestep) { + ir_fprintf(stderr, "Verify warning: Schedule timestep did not increase at node %+F\n", + node); + env->problem_found = 1; + } + last_timestep = timestep; - // 1. Check for phis + // 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", @@ -142,7 +199,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { non_phi_found = 1; } - // 2. 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) { @@ -165,7 +222,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // 3. Check for uses + // 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) { @@ -182,7 +239,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } - // 4. check for dead nodes + // 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)); @@ -198,7 +255,7 @@ static void verify_schedule_walker(ir_node *block, void *data) { } } -static int should_be_scheduled(ir_node *node) { +static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) { if(is_Block(node)) return -1; @@ -217,23 +274,30 @@ static int should_be_scheduled(ir_node *node) { case iro_End: case iro_NoMem: case iro_Bad: + case iro_Unknown: return 0; default: break; } + if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore) + return -1; + return 1; } static void check_schedule(ir_node *node, void *data) { be_verify_schedule_env_t *env = data; int should_be; + int scheduled; - should_be = should_be_scheduled(node); + should_be = should_be_scheduled(env, node); if(should_be == -1) return; - if(should_be ? !sched_is_scheduled(node) : sched_is_scheduled(node)) { + scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0; + should_be = should_be ? 1 : 0; + 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"); env->problem_found = 1; @@ -243,16 +307,18 @@ static void check_schedule(ir_node *node, void *data) { /** * Start a walk over the irg and check schedule. */ -int be_verify_schedule(ir_graph *irg) +int be_verify_schedule(const be_irg_t *birg) { be_verify_schedule_env_t env; env.problem_found = 0; - env.irg = irg; + env.irg = be_get_birg_irg(birg); + env.scheduled = bitset_alloca(get_irg_last_idx(env.irg)); + env.arch_env = birg->main_env->arch_env; - irg_block_walk_graph(irg, verify_schedule_walker, NULL, &env); + irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env); // check if all nodes are scheduled - irg_walk_graph(irg, check_schedule, NULL, &env); + irg_walk_graph(env.irg, check_schedule, NULL, &env); return ! env.problem_found; } @@ -265,7 +331,7 @@ int be_verify_schedule(ir_graph *irg) typedef struct _spill_t { ir_node *spill; - entity *ent; + ir_entity *ent; } spill_t; typedef struct { @@ -289,7 +355,7 @@ static spill_t *find_spill(be_verify_spillslots_env_t *env, ir_node *node) { return set_find(env->spills, &spill, sizeof(spill), HASH_PTR(node)); } -static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, entity *ent) { +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); @@ -320,17 +386,17 @@ 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, 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, entity *ent) { +static void 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, entity* ent) { - entity *spillent = arch_get_frame_entity(env->arch_env, node); +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); get_spill(env, node, ent); @@ -341,13 +407,13 @@ static void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_nod } } -static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, entity* ent) { +static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) { int i, arity; spill_t spill, *res; int hash = HASH_PTR(node); int out; ir_node* memperm; - entity *spillent; + ir_entity *spillent; assert(is_Proj(node)); @@ -373,13 +439,13 @@ static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_n for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) { ir_node* arg = get_irn_n(memperm, i + 1); - entity* argent = be_get_MemPerm_in_entity(memperm, i); + ir_entity* argent = be_get_MemPerm_in_entity(memperm, i); collect(env, arg, memperm, argent); } } -static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, entity *ent) { +static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) { int i, arity; spill_t spill, *res; int hash = HASH_PTR(node); @@ -402,7 +468,7 @@ static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_no } } -static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, entity* ent) { +static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) { if(be_is_Spill(node)) { collect_spill(env, node, reload, ent); } else if(is_Proj(node)) { @@ -410,9 +476,12 @@ 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 +#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)); env->problem_found = 1; +#endif } } @@ -430,7 +499,7 @@ static void collect_spills_walker(ir_node *node, void *data) { if(arch_irn_class_is(arch_env, node, reload)) { ir_node *spill = get_memory_edge(node); - entity *ent; + ir_entity *ent; if(spill == NULL) { ir_fprintf(stderr, "Verify warning: No spill attached to reload %+F in block %+F(%s)\n", @@ -483,7 +552,7 @@ static void check_lonely_spills(ir_node *node, void *data) { if(be_is_Spill(node) || (is_Proj(node) && be_is_MemPerm(get_Proj_pred(node)))) { spill_t *spill = find_spill(env, node); if(be_is_Spill(node)) { - entity *ent = arch_get_frame_entity(env->arch_env, node); + ir_entity *ent = arch_get_frame_entity(env->arch_env, node); check_entity(env, node, ent); } @@ -597,39 +666,51 @@ typedef struct _be_verify_register_allocation_env_t { } 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; + const arch_env_t *arch_env = env->arch_env; const arch_register_t *reg; - int i, arity; + int i, arity; - if(arch_get_irn_reg_class(arch_env, node, -1) != NULL) { + /* verify output register */ + if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) { reg = arch_get_irn_register(arch_env, node); - if(reg == NULL) { + 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; } - if(reg != NULL && !arch_reg_is_allocatable(arch_env, node, -1, reg)) { + 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; } } + /* verify input register */ arity = get_irn_arity(node); - for(i = 0; i < arity; ++i) { + for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(node, i); - if(arch_get_irn_reg_class(arch_env, node, i) == NULL) + if (is_Unknown(pred)) + continue; + + 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; + continue; + } + + if (arch_get_irn_reg_class(arch_env, node, i) == NULL) continue; reg = arch_get_irn_register(arch_env, pred); - if(reg == NULL) { + 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; continue; } - if(!arch_reg_is_allocatable(arch_env, node, i, reg)) { + 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; @@ -639,25 +720,30 @@ 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_env_t *arch_env = env->arch_env; - ir_node *node; - const arch_register_t *reg = NULL; - int fail = 0; - - bitset_t *registers = bitset_alloca(arch_register_class_n_regs(regclass)); + 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) + if (arch_get_irn_reg_class(arch_env, node, -1) != regclass) continue; reg = arch_get_irn_register(arch_env, node); - if(bitset_is_set(registers, reg->index)) { + + /* this problem is already reported in 'check_register_constraints' */ + if (! reg) + continue; + + if (bitset_is_set(registers, reg->index)) { pset_break(nodes); fail = 1; break; } 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)); @@ -723,27 +809,28 @@ int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) { typedef struct _verify_out_dead_nodes_env { ir_graph *irg; bitset_t *reachable; - bitset_t *visited; int problem_found; } verify_out_dead_nodes_env; static void check_out_edges(ir_node *node, verify_out_dead_nodes_env *env) { + ir_graph *irg = env->irg; const ir_edge_t* edge; + if(irn_visited(node)) + return; + mark_irn_visited(node); + foreach_out_edge(node, edge) { ir_node* src = get_edge_src_irn(edge); - if(!bitset_is_set(env->reachable, get_irn_idx(src))) { + if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) { 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(env->irg), node); + src, get_nodes_block(src), get_irg_dump_name(irg), node); env->problem_found = 1; + continue; } - if(!bitset_is_set(env->visited, get_irn_idx(src))) { - bitset_set(env->visited, get_irn_idx(src)); - if(!is_Block(src)) - check_out_edges(src, env); - } + check_out_edges(src, env); } } @@ -755,13 +842,15 @@ static void set_reachable(ir_node *node, void* data) int be_verify_out_edges(ir_graph *irg) { verify_out_dead_nodes_env env; - env.irg = irg; - env.reachable = bitset_alloca(get_irg_last_idx(irg)); - env.visited = bitset_alloca(get_irg_last_idx(irg)); - env.problem_found = 0; - irg_walk_graph(irg, set_reachable, NULL, env.reachable); + env.irg = irg; + env.reachable = bitset_alloca(get_irg_last_idx(irg)); + env.problem_found = edges_verify(irg); + + irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable); + irg_walk_anchors(irg, set_reachable, NULL, env.reachable); + inc_irg_visited(irg); check_out_edges(get_irg_start(irg), &env); - return !env.problem_found; + return ! env.problem_found; }