nsz Git - libfirm/blob - ir/be/beverify.c

   1 /*
   2  * Author:    Matthias Braun
   3  * Date:      05.05.2006
   4  * Copyright: (c) Universitaet Karlsruhe
   5  * License:   This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  * CVS-Id:    $Id$
   7  */
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #include <limits.h>
  13
  14 #include "bitset.h"
  15 #include "set.h"
  16 #include "array.h"
  17
  18 #include "irnode.h"
  19 #include "irgraph.h"
  20 #include "irgwalk.h"
  21 #include "irprintf.h"
  22 #include "irdump_t.h"
  23 #include "iredges.h"
  24
  25 #include "beverify.h"
  26 #include "belive.h"
  27 #include "besched_t.h"
  28 #include "benode_t.h"
  29
  30 static int my_values_interfere(const ir_node *a, const ir_node *b);
  31
  32 typedef struct be_verify_register_pressure_env_t_ {
  33         ir_graph                    *irg;                 /**< the irg to verify */
  34          be_lv_t                    *lv;                  /**< Liveness information. */
  35         const arch_env_t            *arch_env;            /**< an architecture environment */
  36         const arch_register_class_t *cls;                 /**< the register class to check for */
  37         int                         registers_available;  /**< number of available registers */
  38         int                         problem_found;        /**< flag indicating if a problem was found */
  39 } be_verify_register_pressure_env_t;
  40
  41 /**
  42  * Print all nodes of a pset into a file.
  43  */
  44 static void print_living_values(FILE *F, pset *live_nodes) {
  45         ir_node *node;
  46
  47         ir_fprintf(F, "\t");
  48         foreach_pset(live_nodes, node) {
  49                 ir_fprintf(F, "%+F ", node);
  50         }
  51         ir_fprintf(F, "\n");
  52 }
  53
  54 /**
  55  * Check if number of live nodes never exceeds the number of available registers.
  56  */
  57 static void verify_liveness_walker(ir_node *block, void *data) {
  58         be_verify_register_pressure_env_t *env = (be_verify_register_pressure_env_t *)data;
  59         pset    *live_nodes = pset_new_ptr_default();
  60         ir_node *irn;
  61         int pressure;
  62
  63         /* collect register pressure info, start with end of a block */
  64         be_liveness_end_of_block(env->lv, env->arch_env, env->cls, block, live_nodes);
  65
  66         pressure = pset_count(live_nodes);
  67         if(pressure > env->registers_available) {
  68                 ir_fprintf(stderr, "Verify Warning: Register pressure too high at end of block %+F(%s) (%d/%d):\n",
  69                         block, get_irg_dump_name(env->irg), pressure, env->registers_available);
  70                 print_living_values(stderr, live_nodes);
  71                 env->problem_found = 1;
  72         }
  73
  74         sched_foreach_reverse(block, irn) {
  75                 if (is_Phi(irn))
  76                         break;
  77
  78                 be_liveness_transfer(env->arch_env, env->cls, irn, live_nodes);
  79
  80                 pressure = pset_count(live_nodes);
  81
  82                 if(pressure > env->registers_available) {
  83                         ir_fprintf(stderr, "Verify Warning: Register pressure too high before node %+F in %+F(%s) (%d/%d):\n",
  84                                 irn, block, get_irg_dump_name(env->irg), pressure, env->registers_available);
  85                         print_living_values(stderr, live_nodes);
  86                         env->problem_found = 1;
  87                 }
  88         }
  89         del_pset(live_nodes);
  90 }
  91
  92 /**
  93  * Start a walk over the irg and check the register pressure.
  94  */
  95 int be_verify_register_pressure(const be_irg_t *birg, const arch_register_class_t *cls, ir_graph *irg) {
  96         be_verify_register_pressure_env_t env;
  97
  98         env.lv                  = be_liveness(irg);
  99         env.irg                 = irg;
 100         env.arch_env            = birg->main_env->arch_env;
 101         env.cls                 = cls;
 102         env.registers_available = env.cls->n_regs - be_put_ignore_regs(birg, env.cls, NULL);
 103         env.problem_found       = 0;
 104
 105         irg_block_walk_graph(irg, verify_liveness_walker, NULL, &env);
 106         be_liveness_free(env.lv);
 107
 108         return ! env.problem_found;
 109 }
 110
 111
 112
 113 //---------------------------------------------------------------------------
 114
 115
 116
 117 typedef struct be_verify_schedule_env_t_ {
 118         int      problem_found;     /**< flags indicating if there was a problem */
 119         bitset_t *scheduled;        /**< bitset of scheduled nodes */
 120         ir_graph *irg;              /**< the irg to check */
 121         const arch_env_t *arch_env; /**< the arch_env */
 122 } be_verify_schedule_env_t;
 123
 124 /**
 125  * Simple schedule checker.
 126  */
 127 static void verify_schedule_walker(ir_node *block, void *data) {
 128         be_verify_schedule_env_t *env = (be_verify_schedule_env_t*) data;
 129         ir_node *node;
 130         int non_phi_found  = 0;
 131         int cfchange_found = 0;
 132         // TODO ask arch about delay branches
 133         int delay_branches = 0;
 134         int last_timestep = INT_MIN;
 135
 136         /*
 137          * Tests for the following things:
 138          *   1. Make sure that all phi nodes are scheduled at the beginning of the block
 139          *   2. There is 1 or no control flow changing node scheduled and exactly delay_branches operations after it.
 140          *   3. No value is defined after it has been used
 141          */
 142         sched_foreach(block, node) {
 143                 int i, arity;
 144                 int timestep;
 145
 146                 // this node is scheduled
 147                 if(bitset_is_set(env->scheduled, get_irn_idx(node))) {
 148                         ir_fprintf(stderr, "Verify warning: %+F appears to be schedule twice\n");
 149                         env->problem_found = 1;
 150                 }
 151                 bitset_set(env->scheduled, get_irn_idx(node));
 152
 153                 // Check that scheduled nodes are in the correct block
 154                 if(get_nodes_block(node) != block) {
 155                         ir_fprintf(stderr, "Verify warning: %+F is in block %+F but scheduled in %+F\n", node, get_nodes_block(node), block);
 156                         env->problem_found = 1;
 157                 }
 158
 159                 // Check that timesteps are increasing
 160                 timestep = sched_get_time_step(node);
 161                 if(timestep <= last_timestep) {
 162                         ir_fprintf(stderr, "Verify warning: Schedule timestep did not increase at node %+F\n",
 163                                    node);
 164                         env->problem_found = 1;
 165                 }
 166                 last_timestep = timestep;
 167
 168                 // Check that phis come before any other node
 169                 if (is_Phi(node)) {
 170                         if (non_phi_found) {
 171                                 ir_fprintf(stderr, "Verify Warning: Phi node %+F scheduled after non-Phi nodes in block %+F (%s)\n",
 172                                         node, block, get_irg_dump_name(env->irg));
 173                                 env->problem_found = 1;
 174                         }
 175                 } else {
 176                         non_phi_found = 1;
 177                 }
 178
 179                 // Check for control flow changing nodes
 180                 if (is_cfop(node) && get_irn_opcode(node) != iro_Start) {
 181                         /* check, that only one CF operation is scheduled */
 182                         if (cfchange_found == 1) {
 183                                 ir_fprintf(stderr, "Verify Warning: More than 1 control flow changing node (%+F) scheduled in block %+F (%s)\n",
 184                                         node, block, get_irg_dump_name(env->irg));
 185                                 env->problem_found = 1;
 186                         }
 187                         cfchange_found = 1;
 188                 } else if (cfchange_found) {
 189                         // proj and keepany aren't real instructions...
 190                         if(!is_Proj(node) && !be_is_Keep(node)) {
 191                                 /* check for delay branches */
 192                                 if (delay_branches == 0) {
 193                                         ir_fprintf(stderr, "Verify Warning: Node %+F scheduled after control flow changing node (+delay branches) in block %+F (%s)\n",
 194                                                 node, block, get_irg_dump_name(env->irg));
 195                                         env->problem_found = 1;
 196                                 } else {
 197                                         delay_branches--;
 198                                 }
 199                         }
 200                 }
 201
 202                 // Check that all uses come before their definitions
 203                 if(!is_Phi(node)) {
 204                         int nodetime = sched_get_time_step(node);
 205                         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 206                                 ir_node *arg = get_irn_n(node, i);
 207                                 if(get_nodes_block(arg) != block
 208                                    || !sched_is_scheduled(arg))
 209                                         continue;
 210
 211                                 if(sched_get_time_step(arg) >= nodetime) {
 212                                         ir_fprintf(stderr, "Verify Warning: Value %+F used by %+F before it was defined in block %+F (%s)\n",
 213                                                    arg, node, block, get_irg_dump_name(env->irg));
 214                                         env->problem_found = 1;
 215                                 }
 216                         }
 217                 }
 218
 219                 // Check that no dead nodes are scheduled
 220                 if(get_irn_n_edges(node) == 0) {
 221                         ir_fprintf(stderr, "Verify warning: Node %+F is dead but scheduled in block %+F (%s)\n",
 222                                    node, block, get_irg_dump_name(env->irg));
 223                         env->problem_found = 1;
 224                 }
 225         }
 226
 227         /* check that all delay branches are filled (at least with NOPs) */
 228         if (cfchange_found && delay_branches != 0) {
 229                 ir_fprintf(stderr, "Verify warning: Not all delay slots filled after jump (%d/%d) in block %+F (%s)\n",
 230                         block, get_irg_dump_name(env->irg));
 231                 env->problem_found = 1;
 232         }
 233 }
 234
 235 static int should_be_scheduled(be_verify_schedule_env_t *env, ir_node *node) {
 236         if(is_Block(node))
 237                 return -1;
 238
 239         if(get_irn_mode(node) == mode_M) {
 240                 if(is_Proj(node))
 241                         return -1;
 242                 if(is_Phi(node) || is_Sync(node) || is_Pin(node))
 243                         return 0;
 244         }
 245         if(is_Proj(node) && get_irn_mode(node) == mode_X)
 246                 return 0;
 247         if(be_is_Keep(node) && get_irn_opcode(get_nodes_block(node)) == iro_Bad)
 248                 return 0;
 249
 250         switch(get_irn_opcode(node)) {
 251         case iro_End:
 252         case iro_NoMem:
 253         case iro_Bad:
 254         case iro_Unknown:
 255                 return 0;
 256         default:
 257                 break;
 258         }
 259
 260         if(arch_irn_get_flags(env->arch_env, node) & arch_irn_flags_ignore)
 261                 return -1;
 262
 263         return 1;
 264 }
 265
 266 static void check_schedule(ir_node *node, void *data) {
 267         be_verify_schedule_env_t *env = data;
 268         int should_be;
 269         int scheduled;
 270
 271         should_be = should_be_scheduled(env, node);
 272         if(should_be == -1)
 273                 return;
 274
 275         scheduled = bitset_is_set(env->scheduled, get_irn_idx(node)) ? 1 : 0;
 276         should_be = should_be ? 1 : 0;
 277         if(should_be != scheduled) {
 278                 ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should%s be scheduled\n",
 279                         node, get_nodes_block(node), get_irg_dump_name(env->irg), should_be ? "" : " not");
 280                 env->problem_found = 1;
 281         }
 282 }
 283
 284 /**
 285  * Start a walk over the irg and check schedule.
 286  */
 287 int be_verify_schedule(const be_irg_t *birg)
 288 {
 289         be_verify_schedule_env_t env;
 290
 291         env.problem_found = 0;
 292         env.irg           = be_get_birg_irg(birg);
 293         env.scheduled     = bitset_alloca(get_irg_last_idx(env.irg));
 294         env.arch_env      = birg->main_env->arch_env;
 295
 296         irg_block_walk_graph(env.irg, verify_schedule_walker, NULL, &env);
 297         // check if all nodes are scheduled
 298         irg_walk_graph(env.irg, check_schedule, NULL, &env);
 299
 300         return ! env.problem_found;
 301 }
 302
 303
 304
 305 //---------------------------------------------------------------------------
 306
 307
 308
 309 typedef struct _spill_t {
 310         ir_node *spill;
 311         ir_entity *ent;
 312 } spill_t;
 313
 314 typedef struct {
 315         const arch_env_t *arch_env;
 316         ir_graph *irg;
 317         set *spills;
 318         ir_node **reloads;
 319         int problem_found;
 320 } be_verify_spillslots_env_t;
 321
 322 static int cmp_spill(const void* d1, const void* d2, size_t size) {
 323         const spill_t* s1 = d1;
 324         const spill_t* s2 = d2;
 325         return s1->spill != s2->spill;
 326 }
 327
 328 static spill_t *find_spill(be_verify_spillslots_env_t *env, ir_node *node) {
 329         spill_t spill;
 330
 331         spill.spill = node;
 332         return set_find(env->spills, &spill, sizeof(spill), HASH_PTR(node));
 333 }
 334
 335 static spill_t *get_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
 336         spill_t spill, *res;
 337         int hash = HASH_PTR(node);
 338
 339         spill.spill = node;
 340         res = set_find(env->spills, &spill, sizeof(spill), hash);
 341
 342         if(res == NULL) {
 343                 spill.ent = ent;
 344                 res = set_insert(env->spills, &spill, sizeof(spill), hash);
 345         }
 346
 347         return res;
 348 }
 349
 350 static ir_node *get_memory_edge(const ir_node *node) {
 351         int i, arity;
 352         ir_node *result = NULL;
 353
 354         arity = get_irn_arity(node);
 355         for(i = arity - 1; i >= 0; --i) {
 356                 ir_node *arg = get_irn_n(node, i);
 357                 if(get_irn_mode(arg) == mode_M) {
 358                         assert(result == NULL);
 359                         result = arg;
 360                 }
 361         }
 362
 363         return result;
 364 }
 365
 366 static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent);
 367
 368 static void check_entity(be_verify_spillslots_env_t *env, ir_node *node, ir_entity *ent) {
 369         if(ent == NULL) {
 370                 ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have an entity assigned\n",
 371                            node, get_nodes_block(node), get_irg_dump_name(env->irg));
 372         }
 373 }
 374
 375 static void collect_spill(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
 376         ir_entity *spillent = arch_get_frame_entity(env->arch_env, node);
 377         check_entity(env, node, spillent);
 378         get_spill(env, node, ent);
 379
 380         if(spillent != ent) {
 381                 ir_fprintf(stderr, "Verify warning: Spill %+F has different entity than reload %+F in block %+F(%s)\n",
 382                         node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
 383                 env->problem_found = 1;
 384         }
 385 }
 386
 387 static void collect_memperm(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
 388         int i, arity;
 389         spill_t spill, *res;
 390         int hash = HASH_PTR(node);
 391         int out;
 392         ir_node* memperm;
 393         ir_entity *spillent;
 394
 395         assert(is_Proj(node));
 396
 397         memperm = get_Proj_pred(node);
 398         out = get_Proj_proj(node);
 399
 400         spillent = be_get_MemPerm_out_entity(memperm, out);
 401         check_entity(env, memperm, spillent);
 402         if(spillent != ent) {
 403                 ir_fprintf(stderr, "Verify warning: MemPerm %+F has different entity than reload %+F in block %+F(%s)\n",
 404                         node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
 405                 env->problem_found = 1;
 406         }
 407
 408         spill.spill = node;
 409         res = set_find(env->spills, &spill, sizeof(spill), hash);
 410         if(res != NULL) {
 411                 return;
 412         }
 413
 414         spill.ent = spillent;
 415         res = set_insert(env->spills, &spill, sizeof(spill), hash);
 416
 417         for(i = 0, arity = be_get_MemPerm_entity_arity(memperm); i < arity; ++i) {
 418                 ir_node* arg = get_irn_n(memperm, i + 1);
 419                 ir_entity* argent = be_get_MemPerm_in_entity(memperm, i);
 420
 421                 collect(env, arg, memperm, argent);
 422         }
 423 }
 424
 425 static void collect_memphi(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity *ent) {
 426         int i, arity;
 427         spill_t spill, *res;
 428         int hash = HASH_PTR(node);
 429
 430         assert(is_Phi(node));
 431
 432         spill.spill = node;
 433         res = set_find(env->spills, &spill, sizeof(spill), hash);
 434         if(res != NULL) {
 435                 return;
 436         }
 437
 438         spill.ent = ent;
 439         res = set_insert(env->spills, &spill, sizeof(spill), hash);
 440
 441         // is 1 of the arguments a spill?
 442         for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 443                 ir_node* arg = get_irn_n(node, i);
 444                 collect(env, arg, reload, ent);
 445         }
 446 }
 447
 448 static void collect(be_verify_spillslots_env_t *env, ir_node *node, ir_node *reload, ir_entity* ent) {
 449         if(be_is_Spill(node)) {
 450                 collect_spill(env, node, reload, ent);
 451         } else if(is_Proj(node)) {
 452                 collect_memperm(env, node, reload, ent);
 453         } else if(is_Phi(node) && get_irn_mode(node) == mode_M) {
 454                 collect_memphi(env, node, reload, ent);
 455         } else {
 456                 // Disabled for now, spills might get transformed by the backend
 457 #if 0
 458                 ir_fprintf(stderr, "Verify warning: No spill, memperm or memphi attached to node %+F found from node %+F in block %+F(%s)\n",
 459                         node, reload, get_nodes_block(node), get_irg_dump_name(env->irg));
 460                 env->problem_found = 1;
 461 #endif
 462         }
 463 }
 464
 465 /**
 466  * This walker function searches for reloads and collects all the spills
 467  * and memphis attached to them.
 468  */
 469 static void collect_spills_walker(ir_node *node, void *data) {
 470         be_verify_spillslots_env_t *env = data;
 471         const arch_env_t *arch_env = env->arch_env;
 472
 473         // @@@ ia32_classify returns classification of Proj_pred :-/
 474         if(is_Proj(node))
 475                 return;
 476
 477         if(arch_irn_class_is(arch_env, node, reload)) {
 478                 ir_node *spill = get_memory_edge(node);
 479                 ir_entity *ent;
 480
 481                 if(spill == NULL) {
 482                         ir_fprintf(stderr, "Verify warning: No spill attached to reload %+F in block %+F(%s)\n",
 483                                    node, get_nodes_block(node), get_irg_dump_name(env->irg));
 484                         env->problem_found = 1;
 485                         return;
 486                 }
 487                 ent = arch_get_frame_entity(env->arch_env, node);
 488                 check_entity(env, node, ent);
 489
 490                 collect(env, spill, node, ent);
 491                 ARR_APP1(ir_node*, env->reloads, node);
 492         }
 493 }
 494
 495 static void check_spillslot_interference(be_verify_spillslots_env_t *env) {
 496         int spillcount = set_count(env->spills);
 497         spill_t **spills = alloca(spillcount * sizeof(spills[0]));
 498         spill_t *spill;
 499         int i;
 500
 501         for(spill = set_first(env->spills), i = 0; spill != NULL; spill = set_next(env->spills), ++i) {
 502                 spills[i] = spill;
 503         }
 504
 505         for(i = 0; i < spillcount; ++i) {
 506                 spill_t *sp1 = spills[i];
 507                 int i2;
 508
 509                 for(i2 = i+1; i2 < spillcount; ++i2) {
 510                         spill_t *sp2 = spills[i2];
 511
 512                         if(sp1->ent != sp2->ent)
 513                                 continue;
 514
 515                         if(my_values_interfere(sp1->spill, sp2->spill)) {
 516                                 ir_fprintf(stderr, "Verify warning: Spillslots for %+F in block %+F(%s) and %+F in block %+F(%s) interfere\n",
 517                                         sp1->spill, get_nodes_block(sp1->spill), get_irg_dump_name(env->irg),
 518                                         sp2->spill, get_nodes_block(sp2->spill), get_irg_dump_name(env->irg));
 519                                 env->problem_found = 1;
 520                                 my_values_interfere(sp1->spill, sp2->spill);
 521                         }
 522                 }
 523         }
 524 }
 525
 526 static void check_lonely_spills(ir_node *node, void *data) {
 527         be_verify_spillslots_env_t *env = data;
 528
 529         if(be_is_Spill(node) || (is_Proj(node) && be_is_MemPerm(get_Proj_pred(node)))) {
 530                 spill_t *spill = find_spill(env, node);
 531                 if(be_is_Spill(node)) {
 532                         ir_entity *ent = arch_get_frame_entity(env->arch_env, node);
 533                         check_entity(env, node, ent);
 534                 }
 535
 536                 if(spill == NULL) {
 537                         ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) not connected to a reaload\n",
 538                                    node, get_nodes_block(node), get_irg_dump_name(env->irg));
 539                 }
 540         }
 541 }
 542
 543 int be_verify_spillslots(const arch_env_t *arch_env, ir_graph *irg)
 544 {
 545         be_verify_spillslots_env_t env;
 546
 547         env.arch_env = arch_env;
 548         env.irg = irg;
 549         env.spills = new_set(cmp_spill, 10);
 550         env.reloads = NEW_ARR_F(ir_node*, 0);
 551         env.problem_found = 0;
 552
 553         irg_walk_graph(irg, collect_spills_walker, NULL, &env);
 554         irg_walk_graph(irg, check_lonely_spills, NULL, &env);
 555
 556         check_spillslot_interference(&env);
 557
 558         DEL_ARR_F(env.reloads);
 559         del_set(env.spills);
 560
 561         return ! env.problem_found;
 562 }
 563
 564
 565
 566 //---------------------------------------------------------------------------
 567
 568
 569
 570 /**
 571  * Check, if two values interfere.
 572  * @param a The first value.
 573  * @param b The second value.
 574  * @return 1, if a and b interfere, 0 if not.
 575  */
 576 static int my_values_interfere(const ir_node *a, const ir_node *b) {
 577         const ir_edge_t *edge;
 578         ir_node *bb;
 579         int a2b = value_dominates(a, b);
 580         int b2a = value_dominates(b, a);
 581
 582         /* If there is no dominance relation, they do not interfere. */
 583         if(!a2b && !b2a)
 584                 return 0;
 585
 586         /*
 587          * Adjust a and b so, that a dominates b if
 588          * a dominates b or vice versa.
 589          */
 590         if(b2a) {
 591                 const ir_node *t = a;
 592                 a = b;
 593                 b = t;
 594         }
 595
 596         bb = get_nodes_block(b);
 597
 598         /*
 599          * Look at all usages of a.
 600          * If there's one usage of a in the block of b, then
 601          * we check, if this use is dominated by b, if that's true
 602          * a and b interfere. Note that b must strictly dominate the user,
 603          * since if b is the last user of in the block, b and a do not
 604          * interfere.
 605          * Uses of a not in b's block can be disobeyed, because the
 606          * check for a being live at the end of b's block is already
 607          * performed.
 608          */
 609         foreach_out_edge(a, edge) {
 610                 const ir_node *user = get_edge_src_irn(edge);
 611                 if(b == user)
 612                         continue;
 613
 614                 if(get_irn_opcode(user) == iro_End)
 615                         continue;
 616
 617                 // in case of phi arguments we compare with the block the value comes from
 618                 if(is_Phi(user)) {
 619                         ir_node *phiblock = get_nodes_block(user);
 620                         if(phiblock == bb)
 621                                 continue;
 622                         user = get_irn_n(phiblock, get_edge_src_pos(edge));
 623                 }
 624
 625                 if(value_dominates(b, user))
 626                         return 1;
 627         }
 628
 629         return 0;
 630 }
 631
 632
 633
 634 //---------------------------------------------------------------------------
 635
 636
 637
 638 typedef struct _be_verify_register_allocation_env_t {
 639         const arch_env_t *arch_env;
 640         ir_graph *irg;
 641         be_lv_t *lv;
 642         int problem_found;
 643 } be_verify_register_allocation_env_t;
 644
 645 static void check_register_constraints(ir_node *node, be_verify_register_allocation_env_t *env) {
 646         const arch_env_t      *arch_env = env->arch_env;
 647         const arch_register_t *reg;
 648         int                   i, arity;
 649
 650         /* verify output register */
 651         if (arch_get_irn_reg_class(arch_env, node, -1) != NULL) {
 652                 reg = arch_get_irn_register(arch_env, node);
 653                 if (reg == NULL) {
 654                         ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
 655                                         node, get_nodes_block(node), get_irg_dump_name(env->irg));
 656                         env->problem_found = 1;
 657                 }
 658                 else if (! arch_register_type_is(reg, joker) && !arch_reg_is_allocatable(arch_env, node, -1, reg)) {
 659                         ir_fprintf(stderr, "Verify warning: Register %s assigned as output of %+F not allowed (register constraint) in block %+F(%s)\n",
 660                                         reg->name, node, get_nodes_block(node), get_irg_dump_name(env->irg));
 661                         env->problem_found = 1;
 662                 }
 663         }
 664
 665         /* verify input register */
 666         arity = get_irn_arity(node);
 667         for (i = 0; i < arity; ++i) {
 668                 ir_node *pred = get_irn_n(node, i);
 669
 670                 if (is_Unknown(pred))
 671                         continue;
 672
 673                 if (is_Bad(pred)) {
 674                         ir_fprintf(stderr, "Verify warning: %+F in block %+F(%s) has Bad as input %d\n",
 675                                 node, get_nodes_block(node), get_irg_dump_name(env->irg), i);
 676                         env->problem_found = 1;
 677                         continue;
 678                 }
 679
 680                 if (arch_get_irn_reg_class(arch_env, node, i) == NULL)
 681                         continue;
 682
 683                 reg = arch_get_irn_register(arch_env, pred);
 684                 if (reg == NULL) {
 685                         ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) should have a register assigned\n",
 686                                    pred, get_nodes_block(pred), get_irg_dump_name(env->irg));
 687                         env->problem_found = 1;
 688                         continue;
 689                 }
 690                 else if (! arch_register_type_is(reg, joker) && ! arch_reg_is_allocatable(arch_env, node, i, reg)) {
 691                         ir_fprintf(stderr, "Verify warning: Register %s as input %d of %+F not allowed (register constraint) in block %+F(%s)\n",
 692                                    reg->name, i, node, get_nodes_block(node), get_irg_dump_name(env->irg));
 693                         env->problem_found = 1;
 694                 }
 695         }
 696 }
 697
 698 static void check_register_allocation(be_verify_register_allocation_env_t *env,
 699                                       const arch_register_class_t *regclass, pset *nodes) {
 700         const arch_env_t      *arch_env  = env->arch_env;
 701         const arch_register_t *reg       = NULL;
 702         int                   fail       = 0;
 703         bitset_t              *registers = bitset_alloca(arch_register_class_n_regs(regclass));
 704         ir_node               *node;
 705
 706         foreach_pset(nodes, node) {
 707                 if (arch_get_irn_reg_class(arch_env, node, -1) != regclass)
 708                         continue;
 709
 710                 reg = arch_get_irn_register(arch_env, node);
 711
 712                 /* this problem is already reported in 'check_register_constraints' */
 713                 if (! reg)
 714                         continue;
 715
 716                 if (bitset_is_set(registers, reg->index)) {
 717                         pset_break(nodes);
 718                         fail = 1;
 719                         break;
 720                 }
 721                 bitset_set(registers, reg->index);
 722         }
 723
 724         if (fail) {
 725                 ir_fprintf(stderr, "Verify warning: Register %s assigned more than once in block %+F(%s)\n",
 726                                reg->name, get_nodes_block(node), get_irg_dump_name(env->irg));
 727                 env->problem_found = 1;
 728
 729                 foreach_pset(nodes, node) {
 730                         if (arch_get_irn_register(arch_env, node) == reg) {
 731                                 ir_fprintf(stderr, "  at node %+F\n", node);
 732                         }
 733                 }
 734         }
 735 }
 736
 737 static void verify_block_register_allocation(ir_node *block, void *data) {
 738         be_verify_register_allocation_env_t *env = data;
 739         const arch_env_t *arch_env = env->arch_env;
 740         const arch_isa_t *isa = arch_env->isa;
 741         int i, nregclasses;
 742
 743         nregclasses = arch_isa_get_n_reg_class(isa);
 744         for (i = 0; i < nregclasses; ++i) {
 745                 const arch_register_class_t *regclass = arch_isa_get_reg_class(isa, i);
 746                 ir_node *node;
 747                 pset *live_nodes = pset_new_ptr_default();
 748
 749                 be_liveness_end_of_block(env->lv, env->arch_env, regclass, block, live_nodes);
 750                 check_register_allocation(env, regclass, live_nodes);
 751
 752                 sched_foreach_reverse(block, node) {
 753                         if (is_Phi(node))
 754                                 break;
 755
 756                         be_liveness_transfer(env->arch_env, regclass, node, live_nodes);
 757                         check_register_allocation(env, regclass, live_nodes);
 758                         check_register_constraints(node, env);
 759                 }
 760
 761                 del_pset(live_nodes);
 762         }
 763 }
 764
 765 int be_verify_register_allocation(const arch_env_t *arch_env, ir_graph *irg) {
 766         be_verify_register_allocation_env_t env;
 767
 768         env.arch_env = arch_env;
 769         env.irg = irg;
 770         env.lv = be_liveness(irg);
 771         env.problem_found = 0;
 772
 773         irg_block_walk_graph(irg, verify_block_register_allocation, NULL, &env);
 774
 775         be_liveness_free(env.lv);
 776
 777         return !env.problem_found;
 778 }
 779
 780
 781
 782 //---------------------------------------------------------------------------
 783
 784
 785
 786 typedef struct _verify_out_dead_nodes_env {
 787         ir_graph *irg;
 788         bitset_t *reachable;
 789         int problem_found;
 790 } verify_out_dead_nodes_env;
 791
 792 static void check_out_edges(ir_node *node, verify_out_dead_nodes_env *env) {
 793         ir_graph *irg = env->irg;
 794         const ir_edge_t* edge;
 795
 796         if(irn_visited(node))
 797                 return;
 798         mark_irn_visited(node);
 799
 800         foreach_out_edge(node, edge) {
 801                 ir_node* src = get_edge_src_irn(edge);
 802
 803                 if(!bitset_is_set(env->reachable, get_irn_idx(src)) && !is_Block(node)) {
 804                         ir_fprintf(stderr, "Verify warning: Node %+F in block %+F(%s) only reachable through out edges from %+F\n",
 805                                    src, get_nodes_block(src), get_irg_dump_name(irg), node);
 806                         env->problem_found = 1;
 807                         continue;
 808                 }
 809
 810                 check_out_edges(src, env);
 811         }
 812 }
 813
 814 static void set_reachable(ir_node *node, void* data)
 815 {
 816         bitset_t* reachable = data;
 817         bitset_set(reachable, get_irn_idx(node));
 818 }
 819
 820 int be_verify_out_edges(ir_graph *irg) {
 821         verify_out_dead_nodes_env env;
 822
 823         env.irg           = irg;
 824         env.reachable     = bitset_alloca(get_irg_last_idx(irg));
 825         env.problem_found = edges_verify(irg);
 826
 827         irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
 828         irg_walk_anchors(irg, set_reachable, NULL, env.reachable);
 829         inc_irg_visited(irg);
 830         check_out_edges(get_irg_start(irg), &env);
 831
 832         return ! env.problem_found;
 833 }