nsz Git - libfirm/blob - ir/ir/irverify.c

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Check irnodes for correctness.
  23  * @author   Christian Schaefer, Goetz Lindenmaier, Till Riedel, Michael Beck
  24  * @version  $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "irprog.h"
  29 #include "irop_t.h"
  30 #include "irgraph_t.h"
  31 #include "irverify_t.h"
  32 #include "irgwalk.h"
  33 #include "irdump.h"
  34 #include "irdom_t.h"
  35 #include "irprintf.h"
  36 #include "irouts.h"
  37 #include "irflag_t.h"
  38 #include "irpass_t.h"
  39 #include "irnodeset.h"
  40
  41 /** if this flag is set, verify entity types in Load & Store nodes */
  42 static int verify_entities = 0;
  43
  44 const char *firm_verify_failure_msg;
  45
  46 /* enable verification of Load/Store entities */
  47 void verify_enable_entity_tests(int enable)
  48 {
  49         verify_entities = enable;
  50 }
  51
  52 #ifndef NDEBUG
  53
  54 /**
  55  * little helper for NULL modes
  56  */
  57 static const char *get_mode_name_ex(ir_mode *mode)
  58 {
  59         if (! mode)
  60                 return "<no mode>";
  61         return get_mode_name(mode);
  62 }
  63
  64 /** the last IRG, on which a verification error was found */
  65 static ir_graph *last_irg_error = NULL;
  66
  67 /**
  68  * print the name of the entity of an verification failure
  69  *
  70  * @param node  the node caused the failure
  71  */
  72 static void show_entity_failure(ir_node *node)
  73 {
  74         ir_graph *irg = get_irn_irg(node);
  75
  76         if (last_irg_error == irg)
  77                 return;
  78
  79         last_irg_error = irg;
  80
  81         if (irg == get_const_code_irg()) {
  82                 fprintf(stderr, "\nFIRM: irn_verify_irg() <of CONST_CODE_IRG> failed\n");
  83         } else {
  84                 ir_entity *ent = get_irg_entity(irg);
  85
  86                 if (ent) {
  87                         ir_type *ent_type = get_entity_owner(ent);
  88
  89                         if (ent_type) {
  90                                 ir_fprintf(stderr, "\nFIRM: irn_verify_irg() %+F::%s failed\n",
  91                                            ent_type, get_entity_name(ent));
  92                         } else {
  93                                 fprintf(stderr, "\nFIRM: irn_verify_irg() <NULL>::%s failed\n", get_entity_name(ent));
  94                         }
  95                 } else {
  96                         fprintf(stderr, "\nFIRM: irn_verify_irg() <IRG %p> failed\n", (void *)irg);
  97                 }
  98         }
  99 }
 100
 101 static const char *get_irn_modename(const ir_node *node)
 102 {
 103         ir_mode *mode = get_irn_mode(node);
 104         return get_mode_name(mode);
 105 }
 106
 107 /**
 108  * Prints a failure for a Node
 109  */
 110 static void show_node_failure(ir_node *n)
 111 {
 112         show_entity_failure(n);
 113         fprintf(stderr, "  node %ld %s%s\n" ,
 114                 get_irn_node_nr(n),
 115                 get_irn_opname(n), get_irn_modename(n)
 116         );
 117 }
 118
 119 /**
 120  * Prints a failure message for a binop
 121  */
 122 static void show_binop_failure(ir_node *n, const char *text)
 123 {
 124         ir_node *left  = get_binop_left(n);
 125         ir_node *right = get_binop_right(n);
 126
 127         show_entity_failure(n);
 128         fprintf(stderr, "  node %ld %s%s(%s%s, %s%s) did not match (%s)\n",
 129                 get_irn_node_nr(n),
 130                 get_irn_opname(n), get_irn_modename(n),
 131                 get_irn_opname(left), get_irn_modename(left),
 132                 get_irn_opname(right), get_irn_modename(right),
 133                 text);
 134 }
 135
 136 /**
 137  * Prints a failure message for an unop
 138  */
 139 static void show_unop_failure(ir_node *n, const char *text)
 140 {
 141         ir_node *op  = get_unop_op(n);
 142
 143         show_entity_failure(n);
 144         fprintf(stderr, "  node %ld %s%s(%s%s) did not match (%s)\n",
 145                 get_irn_node_nr(n),
 146                 get_irn_opname(n), get_irn_modename(n),
 147                 get_irn_opname(op), get_irn_modename(op),
 148                 text);
 149 }
 150
 151 /**
 152  * Prints a failure message for an op with 3 operands
 153  */
 154 static void show_triop_failure(ir_node *n, const char *text)
 155 {
 156         ir_node *op0  = get_irn_n(n, 0);
 157         ir_node *op1  = get_irn_n(n, 1);
 158         ir_node *op2  = get_irn_n(n, 2);
 159
 160         show_entity_failure(n);
 161         fprintf(stderr, "  of node %ld %s%s(%s%s, %s%s, %s%s) did not match (%s)\n",
 162                 get_irn_node_nr(n),
 163                 get_irn_opname(n), get_irn_modename(n),
 164                 get_irn_opname(op0), get_irn_modename(op0),
 165                 get_irn_opname(op1), get_irn_modename(op1),
 166                 get_irn_opname(op2), get_irn_modename(op2),
 167                 text);
 168 }
 169
 170 /**
 171  * Prints a failure message for a proj
 172  */
 173 static void show_proj_failure(ir_node *n)
 174 {
 175         ir_node *op  = get_Proj_pred(n);
 176         int proj     = get_Proj_proj(n);
 177
 178         show_entity_failure(n);
 179         fprintf(stderr, "  node %ld %s%s %d(%s%s) failed\n" ,
 180                 get_irn_node_nr(n),
 181                 get_irn_opname(n), get_irn_modename(n), proj,
 182                 get_irn_opname(op), get_irn_modename(op));
 183 }
 184
 185 /**
 186  * Prints a failure message for a proj from Start
 187  */
 188 static void show_proj_mode_failure(ir_node *n, ir_type *ty)
 189 {
 190         long proj  = get_Proj_proj(n);
 191         ir_mode *m = get_type_mode(ty);
 192         char type_name[256];
 193         ir_print_type(type_name, sizeof(type_name), ty);
 194
 195         show_entity_failure(n);
 196         fprintf(stderr, "  Proj %ld mode %s proj %ld (type %s mode %s) failed\n" ,
 197                 get_irn_node_nr(n),
 198                 get_irn_modename(n),
 199                 proj,
 200                 type_name,
 201                 get_mode_name_ex(m));
 202 }
 203
 204 /**
 205  * Prints a failure message for a proj
 206  */
 207 static void show_proj_failure_ent(ir_node *n, ir_entity *ent)
 208 {
 209         ir_node *op  = get_Proj_pred(n);
 210         int proj     = get_Proj_proj(n);
 211         ir_mode *m   = get_type_mode(get_entity_type(ent));
 212         char type_name[256];
 213         ir_print_type(type_name, sizeof(type_name), get_entity_type(ent));
 214
 215         show_entity_failure(n);
 216         fprintf(stderr, "  node %ld %s%s %d(%s%s) entity %s(type %s mode %s)failed\n" ,
 217                 get_irn_node_nr(n),
 218                 get_irn_opname(n), get_irn_modename(n), proj,
 219                 get_irn_opname(op), get_irn_modename(op),
 220                 get_entity_name(ent), type_name,
 221                 get_mode_name_ex(m));
 222 }
 223
 224 /**
 225  * Show a node and a graph
 226  */
 227 static void show_node_on_graph(ir_graph *irg, ir_node *n)
 228 {
 229         ir_fprintf(stderr, "\nFIRM: irn_verify_irg() of %+F, node %+F\n", irg, n);
 230 }
 231
 232 /**
 233  * Show call parameters
 234  */
 235 static void show_call_param(ir_node *n, ir_type *mt)
 236 {
 237         size_t i;
 238         char type_name[256];
 239         ir_print_type(type_name, sizeof(type_name), mt);
 240
 241         show_entity_failure(n);
 242         fprintf(stderr, "  Call type-check failed: %s(", type_name);
 243         for (i = 0; i < get_method_n_params(mt); ++i) {
 244                 fprintf(stderr, "%s ", get_mode_name_ex(get_type_mode(get_method_param_type(mt, i))));
 245         }
 246         fprintf(stderr, ") != CALL(");
 247
 248         for (i = 0; i < get_Call_n_params(n); ++i) {
 249                 fprintf(stderr, "%s ", get_mode_name_ex(get_irn_mode(get_Call_param(n, i))));
 250         }
 251         fprintf(stderr, ")\n");
 252 }
 253
 254 /**
 255  * Show return modes
 256  */
 257 static void show_return_modes(ir_graph *irg, ir_node *n, ir_type *mt, int i)
 258 {
 259         ir_entity *ent = get_irg_entity(irg);
 260
 261         show_entity_failure(n);
 262         fprintf(stderr, "  Return node %ld in entity \"%s\" mode %s different from type mode %s\n",
 263                 get_irn_node_nr(n), get_entity_name(ent),
 264                 get_mode_name_ex(get_irn_mode(get_Return_res(n, i))),
 265                 get_mode_name_ex(get_type_mode(get_method_res_type(mt, i)))
 266         );
 267 }
 268
 269 /**
 270  * Show return number of results
 271  */
 272 static void show_return_nres(ir_graph *irg, ir_node *n, ir_type *mt)
 273 {
 274         ir_entity *ent = get_irg_entity(irg);
 275
 276         show_entity_failure(n);
 277         fprintf(stderr, "  Return node %ld in entity \"%s\" has %lu results different from type %lu\n",
 278                 get_irn_node_nr(n), get_entity_name(ent),
 279                 (unsigned long) get_Return_n_ress(n),
 280                 (unsigned long) get_method_n_ress(mt));
 281 }
 282
 283 /**
 284  * Show Phi input
 285  */
 286 static void show_phi_failure(ir_node *phi, ir_node *pred, int pos)
 287 {
 288         (void) pos;
 289         show_entity_failure(phi);
 290         fprintf(stderr, "  Phi node %ld has mode %s different from predeccessor node %ld mode %s\n",
 291                 get_irn_node_nr(phi), get_mode_name_ex(get_irn_mode(phi)),
 292                 get_irn_node_nr(pred), get_mode_name_ex(get_irn_mode(pred)));
 293 }
 294
 295 /**
 296  * Show Phi inputs
 297  */
 298 static void show_phi_inputs(ir_node *phi, ir_node *block)
 299 {
 300         show_entity_failure(phi);
 301         fprintf(stderr, "  Phi node %ld has %d inputs, its Block %ld has %d\n",
 302                 get_irn_node_nr(phi),   get_irn_arity(phi),
 303                 get_irn_node_nr(block), get_irn_arity(block));
 304 }
 305
 306 #endif /* #ifndef NDEBUG */
 307
 308 /**
 309  * If the address is Sel or SymConst, return the entity.
 310  *
 311  * @param ptr  the node representing the address
 312  */
 313 static ir_entity *get_ptr_entity(ir_node *ptr)
 314 {
 315         if (is_Sel(ptr)) {
 316                 return get_Sel_entity(ptr);
 317         } else if (is_SymConst_addr_ent(ptr)) {
 318                 return get_SymConst_entity(ptr);
 319         }
 320         return NULL;
 321 }
 322
 323 /**
 324  * verify a Proj(Start) node
 325  */
 326 static int verify_node_Proj_Start(ir_node *n, ir_node *p)
 327 {
 328         ir_mode *mode = get_irn_mode(p);
 329         long proj     = get_Proj_proj(p);
 330         (void) n;
 331
 332         ASSERT_AND_RET_DBG(
 333                 (
 334                         (proj == pn_Start_X_initial_exec && mode == mode_X) ||
 335                         (proj == pn_Start_M              && mode == mode_M) ||
 336                         (proj == pn_Start_P_frame_base   && mode_is_reference(mode)) ||
 337                         (proj == pn_Start_T_args         && mode == mode_T)
 338                 ),
 339                 "wrong Proj from Start", 0,
 340                 show_proj_failure(p);
 341         );
 342         return 1;
 343 }
 344
 345 /**
 346  * verify a Proj(Cond) node
 347  */
 348 static int verify_node_Proj_Cond(ir_node *pred, ir_node *p)
 349 {
 350         ir_mode *mode = get_irn_mode(p);
 351         long proj     = get_Proj_proj(p);
 352
 353         ASSERT_AND_RET_DBG(
 354                 (
 355                         (proj >= 0 && mode == mode_X && get_irn_mode(get_Cond_selector(pred)) == mode_b) ||   /* compare */
 356                         (mode == mode_X && mode_is_int(get_irn_mode(get_Cond_selector(pred)))) ||             /* switch */
 357                         is_Bad(get_Cond_selector(pred))                                                       /* rare */
 358                 ),
 359                 "wrong Proj from Cond", 0,
 360                 show_proj_failure(p);
 361         );
 362         return 1;
 363 }
 364
 365 /**
 366  * verify a Proj(Raise) node
 367  */
 368 static int verify_node_Proj_Raise(ir_node *n, ir_node *p)
 369 {
 370         ir_mode *mode = get_irn_mode(p);
 371         long proj     = get_Proj_proj(p);
 372         (void) n;
 373
 374         ASSERT_AND_RET_DBG(
 375                 ((proj == pn_Raise_X && mode == mode_X) || (proj == pn_Raise_M && mode == mode_M)),
 376                 "wrong Proj from Raise", 0,
 377                 show_proj_failure(p);
 378         );
 379         return 1;
 380 }
 381
 382 /**
 383  * verify a Proj(InstOf) node
 384  */
 385 static int verify_node_Proj_InstOf(ir_node *n, ir_node *p)
 386 {
 387         ir_mode *mode = get_irn_mode(p);
 388         long proj     = get_Proj_proj(p);
 389         (void) n;
 390
 391         ASSERT_AND_RET_DBG(
 392                 (
 393                         (proj == pn_InstOf_M         && mode == mode_M) ||
 394                         (proj == pn_InstOf_X_regular && mode == mode_X) ||
 395                         (proj == pn_InstOf_X_except  && mode == mode_X) ||
 396                         (proj == pn_InstOf_res       && mode_is_reference(mode))
 397                 ),
 398                 "wrong Proj from InstOf", 0,
 399                 show_proj_failure(p);
 400         );
 401         return 1;
 402 }
 403
 404 /**
 405  * verify a Proj(Call) node
 406  */
 407 static int verify_node_Proj_Call(ir_node *n, ir_node *p)
 408 {
 409         ir_mode *mode = get_irn_mode(p);
 410         long proj     = get_Proj_proj(p);
 411
 412         ASSERT_AND_RET_DBG(
 413                 (
 414                         (proj == pn_Call_M                && mode == mode_M) ||
 415                         (proj == pn_Call_X_regular        && mode == mode_X) ||
 416                         (proj == pn_Call_X_except         && mode == mode_X) ||
 417                         (proj == pn_Call_T_result         && mode == mode_T)
 418                 ),
 419                 "wrong Proj from Call", 0,
 420                 show_proj_failure(p);
 421         );
 422         /* if we have exception flow, we must have a real Memory input */
 423         if (proj == pn_Call_X_regular)
 424                 ASSERT_AND_RET(
 425                         !is_NoMem(get_Call_mem(n)),
 426                         "Regular Proj from FunctionCall", 0);
 427         else if (proj == pn_Call_X_except)
 428                 ASSERT_AND_RET(
 429                         !is_NoMem(get_Call_mem(n)),
 430                         "Exception Proj from FunctionCall", 0);
 431         return 1;
 432 }
 433
 434 /**
 435  * verify a Proj(Div) node
 436  */
 437 static int verify_node_Proj_Div(ir_node *n, ir_node *p)
 438 {
 439         ir_mode *mode = get_irn_mode(p);
 440         long proj     = get_Proj_proj(p);
 441
 442         ASSERT_AND_RET_DBG(
 443                 (
 444                         (proj == pn_Div_M         && mode == mode_M) ||
 445                         (proj == pn_Div_X_regular && mode == mode_X) ||
 446                         (proj == pn_Div_X_except  && mode == mode_X) ||
 447                         (proj == pn_Div_res       && mode_is_data(mode) && mode == get_Div_resmode(n))
 448                 ),
 449                 "wrong Proj from Div", 0,
 450                 show_proj_failure(p);
 451         );
 452         if (proj == pn_Div_X_regular)
 453                 ASSERT_AND_RET(
 454                         get_irn_pinned(n) == op_pin_state_pinned,
 455                         "Regular Proj from unpinned Div", 0);
 456         else if (proj == pn_Div_X_except)
 457                 ASSERT_AND_RET(
 458                         get_irn_pinned(n) == op_pin_state_pinned,
 459                         "Exception Proj from unpinned Div", 0);
 460         else if (proj == pn_Div_M)
 461                 ASSERT_AND_RET(
 462                         get_irn_pinned(n) == op_pin_state_pinned,
 463                         "Memory Proj from unpinned Div", 0);
 464         return 1;
 465 }
 466
 467 /**
 468  * verify a Proj(Mod) node
 469  */
 470 static int verify_node_Proj_Mod(ir_node *n, ir_node *p)
 471 {
 472         ir_mode *mode = get_irn_mode(p);
 473         long proj     = get_Proj_proj(p);
 474
 475         ASSERT_AND_RET_DBG(
 476                 (
 477                         (proj == pn_Mod_M         && mode == mode_M) ||
 478                         (proj == pn_Mod_X_regular && mode == mode_X) ||
 479                         (proj == pn_Mod_X_except  && mode == mode_X) ||
 480                         (proj == pn_Mod_res       && mode == get_Mod_resmode(n))
 481                 ),
 482                 "wrong Proj from Mod", 0,
 483                 show_proj_failure(p);
 484         );
 485         if (proj == pn_Mod_X_regular)
 486                 ASSERT_AND_RET(
 487                         get_irn_pinned(n) == op_pin_state_pinned,
 488                         "Regular Proj from unpinned Mod", 0);
 489         else if (proj == pn_Mod_X_except)
 490                 ASSERT_AND_RET(
 491                         get_irn_pinned(n) == op_pin_state_pinned,
 492                         "Exception Proj from unpinned Mod", 0);
 493         else if (proj == pn_Mod_M)
 494                 ASSERT_AND_RET(
 495                         get_irn_pinned(n) == op_pin_state_pinned,
 496                         "Memory Proj from unpinned Div", 0);
 497         return 1;
 498 }
 499
 500 /**
 501  * verify a Proj(Load) node
 502  */
 503 static int verify_node_Proj_Load(ir_node *n, ir_node *p)
 504 {
 505         ir_mode *mode = get_irn_mode(p);
 506         long proj     = get_Proj_proj(p);
 507
 508         if (proj == pn_Load_res) {
 509                 ir_node   *ptr = get_Load_ptr(n);
 510                 ir_entity *ent = get_ptr_entity(ptr);
 511                 ir_graph  *irg = get_irn_irg(n);
 512
 513                 if (verify_entities && ent && get_irg_phase_state(irg) == phase_high) {
 514                         /* do NOT check this for lowered phases, see comment on Store */
 515                         ASSERT_AND_RET_DBG(
 516                                 (mode == get_type_mode(get_entity_type(ent))),
 517                                 "wrong data Proj from Load, entity type_mode failed", 0,
 518                                 show_proj_failure_ent(p, ent);
 519                         );
 520                 }
 521                 else {
 522                         ASSERT_AND_RET_DBG(
 523                                 mode_is_data(mode) && mode == get_Load_mode(n),
 524                                 "wrong data Proj from Load", 0,
 525                                 show_proj_failure(p);
 526                         );
 527                 }
 528         }
 529         else {
 530                 ASSERT_AND_RET_DBG(
 531                         (
 532                                 (proj == pn_Load_M         && mode == mode_M) ||
 533                                 (proj == pn_Load_X_regular && mode == mode_X) ||
 534                                 (proj == pn_Load_X_except  && mode == mode_X)
 535                         ),
 536                         "wrong Proj from Load", 0,
 537                         show_proj_failure(p);
 538                 );
 539         }
 540         if (proj == pn_Load_X_regular) {
 541                 ASSERT_AND_RET(
 542                         get_irn_pinned(n) == op_pin_state_pinned,
 543                         "Regular Proj from unpinned Load", 0);
 544         } else if (proj == pn_Load_X_except) {
 545                 ASSERT_AND_RET(
 546                         get_irn_pinned(n) == op_pin_state_pinned,
 547                         "Exception Proj from unpinned Load", 0);
 548         }
 549         return 1;
 550 }
 551
 552 /**
 553  * verify a Proj(Store) node
 554  */
 555 static int verify_node_Proj_Store(ir_node *n, ir_node *p)
 556 {
 557         ir_mode *mode = get_irn_mode(p);
 558         long proj     = get_Proj_proj(p);
 559
 560         ASSERT_AND_RET_DBG(
 561                 (
 562                         (proj == pn_Store_M         && mode == mode_M) ||
 563                         (proj == pn_Store_X_regular && mode == mode_X) ||
 564                         (proj == pn_Store_X_except  && mode == mode_X)
 565                 ),
 566                 "wrong Proj from Store", 0,
 567                 show_proj_failure(p);
 568         );
 569         if (proj == pn_Store_X_regular) {
 570                 ASSERT_AND_RET(
 571                         get_irn_pinned(n) == op_pin_state_pinned,
 572                         "Regular Proj from unpinned Store", 0);
 573         } else if (proj == pn_Store_X_except) {
 574                 ASSERT_AND_RET(
 575                         get_irn_pinned(n) == op_pin_state_pinned,
 576                         "Exception Proj from unpinned Store", 0);
 577         }
 578         return 1;
 579 }
 580
 581 /**
 582  * verify a Proj(Alloc) node
 583  */
 584 static int verify_node_Proj_Alloc(ir_node *n, ir_node *p)
 585 {
 586         ir_mode *mode = get_irn_mode(p);
 587         long proj     = get_Proj_proj(p);
 588         (void) n;
 589
 590         ASSERT_AND_RET_DBG(
 591                 (
 592                         (proj == pn_Alloc_M         && mode == mode_M) ||
 593                         (proj == pn_Alloc_X_regular && mode == mode_X) ||
 594                         (proj == pn_Alloc_X_except  && mode == mode_X) ||
 595                         (proj == pn_Alloc_res       && mode_is_reference(mode))
 596                 ),
 597                 "wrong Proj from Alloc", 0,
 598                 show_proj_failure(p);
 599         );
 600         return 1;
 601 }
 602
 603 /**
 604  * verify a Proj(Proj) node
 605  */
 606 static int verify_node_Proj_Proj(ir_node *pred, ir_node *p)
 607 {
 608         ir_mode *mode = get_irn_mode(p);
 609         long proj     = get_Proj_proj(p);
 610         long nr       = get_Proj_proj(pred);
 611         ir_type *mt; /* A method type */
 612
 613         pred = skip_Id(get_Proj_pred(pred));
 614         ASSERT_AND_RET((get_irn_mode(pred) == mode_T), "Proj from something not a tuple", 0);
 615
 616         switch (get_irn_opcode(pred)) {
 617         case iro_Start:
 618                 mt = get_entity_type(get_irg_entity(get_irn_irg(pred)));
 619
 620                 if (nr == pn_Start_T_args) {
 621                         ASSERT_AND_RET(
 622                                 (proj >= 0 && mode_is_datab(mode)),
 623                                 "wrong Proj from Proj from Start", 0);
 624                         ASSERT_AND_RET(
 625                                 (proj < (int)get_method_n_params(mt)),
 626                                 "More Projs for args than args in type", 0
 627                                 );
 628                         if ((mode_is_reference(mode)) && is_compound_type(get_method_param_type(mt, proj)))
 629                                 /* value argument */ break;
 630
 631                         if (get_irg_phase_state(get_irn_irg(pred)) != phase_backend) {
 632                                 ASSERT_AND_RET_DBG(
 633                                                 (mode == get_type_mode(get_method_param_type(mt, proj))),
 634                                                 "Mode of Proj from Start doesn't match mode of param type.", 0,
 635                                                 show_proj_mode_failure(p, get_method_param_type(mt, proj));
 636                                                 );
 637                         }
 638                 }
 639                 break;
 640
 641         case iro_Call:
 642                 {
 643                         ASSERT_AND_RET(
 644                                 (proj >= 0 && mode_is_datab(mode)),
 645                                 "wrong Proj from Proj from Call", 0);
 646                         mt = get_Call_type(pred);
 647                         ASSERT_AND_RET(mt == get_unknown_type() || is_Method_type(mt),
 648                                         "wrong call type on call", 0);
 649                         ASSERT_AND_RET(
 650                                 (proj < (int)get_method_n_ress(mt)),
 651                                 "More Projs for results than results in type.", 0);
 652                         if ((mode_is_reference(mode)) && is_compound_type(get_method_res_type(mt, proj)))
 653                                 /* value result */ break;
 654
 655                                 ASSERT_AND_RET(
 656                                 (mode == get_type_mode(get_method_res_type(mt, proj))),
 657                                 "Mode of Proj from Call doesn't match mode of result type.", 0);
 658                 }
 659                 break;
 660
 661         case iro_Tuple:
 662                 /* We don't test */
 663                 break;
 664
 665         case iro_Bad:
 666                 /* hmm, optimization did not remove it */
 667                 break;
 668
 669         default:
 670                 /* ASSERT_AND_RET(0, "Unknown opcode", 0); */
 671                 break;
 672         }
 673         return 1;
 674 }
 675
 676 /**
 677  * verify a Proj(Tuple) node
 678  */
 679 static int verify_node_Proj_Tuple(ir_node *n, ir_node *p)
 680 {
 681         (void) n;
 682         (void) p;
 683         /* We don't test */
 684         return 1;
 685 }
 686
 687 /**
 688  * verify a Proj(CopyB) node
 689  */
 690 static int verify_node_Proj_CopyB(ir_node *n, ir_node *p)
 691 {
 692         ir_mode *mode = get_irn_mode(p);
 693         long proj     = get_Proj_proj(p);
 694
 695         ASSERT_AND_RET_DBG(
 696                 (
 697                         (proj == pn_CopyB_M         && mode == mode_M) ||
 698                         (proj == pn_CopyB_X_regular && mode == mode_X) ||
 699                         (proj == pn_CopyB_X_except  && mode == mode_X)
 700                 ),
 701                 "wrong Proj from CopyB", 0,
 702                 show_proj_failure(p);
 703         );
 704         if (proj == pn_CopyB_X_regular)
 705                 ASSERT_AND_RET(
 706                         get_irn_pinned(n) == op_pin_state_pinned,
 707                         "Regular Proj from unpinned CopyB", 0);
 708         else if (proj == pn_CopyB_X_except)
 709                 ASSERT_AND_RET(
 710                         get_irn_pinned(n) == op_pin_state_pinned,
 711                         "Exception Proj from unpinned CopyB", 0);
 712         return 1;
 713 }
 714
 715 /**
 716  * verify a Proj(Bound) node
 717  */
 718 static int verify_node_Proj_Bound(ir_node *n, ir_node *p)
 719 {
 720         ir_mode *mode = get_irn_mode(p);
 721         long proj     = get_Proj_proj(p);
 722
 723         /* ignore Bound checks of Bad */
 724         if (is_Bad(get_Bound_index(n)))
 725                 return 1;
 726         ASSERT_AND_RET_DBG(
 727                 (
 728                         (proj == pn_Bound_M         && mode == mode_M) ||
 729                         (proj == pn_Bound_X_regular && mode == mode_X) ||
 730                         (proj == pn_Bound_X_except  && mode == mode_X) ||
 731                         (proj == pn_Bound_res       && mode == get_irn_mode(get_Bound_index(n)))
 732                 ),
 733                 "wrong Proj from Bound", 0,
 734                 show_proj_failure(p);
 735         );
 736         return 1;
 737 }
 738
 739 /**
 740  * verify a Proj node
 741  */
 742 static int verify_node_Proj(ir_node *p, ir_graph *irg)
 743 {
 744         ir_node *pred;
 745         ir_op *op;
 746
 747         pred = skip_Id(get_Proj_pred(p));
 748         ASSERT_AND_RET(get_irn_mode(pred) == mode_T, "mode of a 'projed' node is not Tuple", 0);
 749         ASSERT_AND_RET(get_irg_pinned(irg) == op_pin_state_floats || get_nodes_block(pred) == get_nodes_block(p), "Proj must be in same block as its predecessor", 0);
 750
 751         op = get_irn_op(pred);
 752
 753         if (op->ops.verify_proj_node)
 754                 return op->ops.verify_proj_node(pred, p);
 755
 756         /* all went ok */
 757         return 1;
 758 }
 759
 760 /**
 761  * verify a Block node
 762  */
 763 static int verify_node_Block(ir_node *n, ir_graph *irg)
 764 {
 765         int i;
 766
 767         for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
 768                 ir_node *pred = get_Block_cfgpred(n, i);
 769                 ASSERT_AND_RET(
 770                         is_Bad(pred) || (get_irn_mode(pred) == mode_X),
 771                         "Block node must have a mode_X predecessor", 0);
 772                 ASSERT_AND_RET(is_cfop(skip_Proj(skip_Tuple(pred))), "Block predecessor must be a cfop", 0);
 773         }
 774
 775         if (n == get_irg_start_block(irg)) {
 776                 ASSERT_AND_RET(get_Block_n_cfgpreds(n) == 0, "Start Block node", 0);
 777         }
 778
 779         if (n == get_irg_end_block(irg) && get_irg_phase_state(irg) != phase_backend) {
 780                 /* End block may only have Return, Raise or fragile ops as preds. */
 781                 for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
 782                         ir_node *pred =  skip_Proj(get_Block_cfgpred(n, i));
 783                         if (is_Proj(pred) || is_Tuple(pred))
 784                                 break;   /*  We can not test properly.  How many tuples are there? */
 785                         ASSERT_AND_RET(
 786                                 (
 787                                         is_Return(pred) ||
 788                                         is_Bad(pred)    ||
 789                                         is_Raise(pred)  ||
 790                                         is_fragile_op(pred)
 791                                 ),
 792                                 "End Block node", 0);
 793                 }
 794         }
 795         /*  irg attr must == graph we are in. */
 796         ASSERT_AND_RET(((get_irn_irg(n) && get_irn_irg(n) == irg)), "Block node has wrong irg attribute", 0);
 797         return 1;
 798 }
 799
 800 /**
 801  * verify a Start node
 802  */
 803 static int verify_node_Start(ir_node *n, ir_graph *irg)
 804 {
 805         ir_mode *mymode = get_irn_mode(n);
 806         (void) irg;
 807
 808         ASSERT_AND_RET(
 809                 /* Start: BB --> X x M x ref x data1 x ... x datan x ref */
 810                 mymode == mode_T, "Start node", 0
 811                 );
 812         return 1;
 813 }
 814
 815 /**
 816  * verify a Jmp node
 817  */
 818 static int verify_node_Jmp(ir_node *n, ir_graph *irg)
 819 {
 820         ir_mode *mymode = get_irn_mode(n);
 821         (void) irg;
 822
 823         ASSERT_AND_RET(
 824                 /* Jmp: BB --> X */
 825                 mymode == mode_X, "Jmp node", 0
 826         );
 827         return 1;
 828 }
 829
 830 /**
 831  * verify an IJmp node
 832  */
 833 static int verify_node_IJmp(ir_node *n, ir_graph *irg)
 834 {
 835         ir_mode *mymode  = get_irn_mode(n);
 836         ir_mode *op1mode = get_irn_mode(get_IJmp_target(n));
 837         (void) irg;
 838
 839         ASSERT_AND_RET(
 840                 /* IJmp: BB x ref --> X */
 841                 mymode == mode_X && mode_is_reference(op1mode), "IJmp node", 0
 842         );
 843         return 1;
 844 }
 845
 846 /**
 847  * verify a Cond node
 848  */
 849 static int verify_node_Cond(ir_node *n, ir_graph *irg)
 850 {
 851         ir_mode *mymode  = get_irn_mode(n);
 852         ir_mode *op1mode = get_irn_mode(get_Cond_selector(n));
 853         (void) irg;
 854
 855         ASSERT_AND_RET(
 856                 /* Cond: BB x b --> X x X */
 857                 (op1mode == mode_b ||
 858                 /* Cond: BB x int --> X^n */
 859                 mode_is_int(op1mode) ),  "Cond node", 0
 860                 );
 861         ASSERT_AND_RET(mymode == mode_T, "Cond mode is not a tuple", 0);
 862
 863         return 1;
 864 }
 865
 866 /**
 867  * verify a Return node
 868  */
 869 static int verify_node_Return(ir_node *n, ir_graph *irg)
 870 {
 871         int i;
 872         ir_mode *mymode   = get_irn_mode(n);
 873         ir_mode *mem_mode = get_irn_mode(get_Return_mem(n));
 874         ir_type *mt;
 875
 876         /* Return: BB x M x data1 x ... x datan --> X */
 877
 878         ASSERT_AND_RET( mem_mode == mode_M, "Return node", 0 );  /* operand M */
 879
 880         for (i = get_Return_n_ress(n) - 1; i >= 0; --i) {
 881                 ASSERT_AND_RET( mode_is_datab(get_irn_mode(get_Return_res(n, i))), "Return node", 0 );  /* operand datai */
 882         }
 883         ASSERT_AND_RET( mymode == mode_X, "Result X", 0 );   /* result X */
 884         /* Compare returned results with result types of method type */
 885         mt = get_entity_type(get_irg_entity(irg));
 886         ASSERT_AND_RET_DBG(get_Return_n_ress(n) == get_method_n_ress(mt),
 887                 "Number of results for Return doesn't match number of results in type.", 0,
 888                 show_return_nres(irg, n, mt););
 889         for (i = get_Return_n_ress(n) - 1; i >= 0; --i) {
 890                 ir_type *res_type = get_method_res_type(mt, i);
 891
 892                 if (get_irg_phase_state(irg) != phase_backend) {
 893                         if (is_atomic_type(res_type)) {
 894                                 ASSERT_AND_RET_DBG(
 895                                         get_irn_mode(get_Return_res(n, i)) == get_type_mode(res_type),
 896                                         "Mode of result for Return doesn't match mode of result type.", 0,
 897                                         show_return_modes(irg, n, mt, i);
 898                                 );
 899                         } else {
 900                                 ASSERT_AND_RET_DBG(
 901                                         mode_is_reference(get_irn_mode(get_Return_res(n, i))),
 902                                         "Mode of result for Return doesn't match mode of result type.", 0,
 903                                         show_return_modes(irg, n, mt, i);
 904                                 );
 905                         }
 906                 }
 907         }
 908         return 1;
 909 }
 910
 911 /**
 912  * verify a Raise node
 913  */
 914 static int verify_node_Raise(ir_node *n, ir_graph *irg)
 915 {
 916         ir_mode *mymode  = get_irn_mode(n);
 917         ir_mode *op1mode = get_irn_mode(get_Raise_mem(n));
 918         ir_mode *op2mode = get_irn_mode(get_Raise_exo_ptr(n));
 919         (void) irg;
 920
 921         ASSERT_AND_RET(
 922                 /* Sel: BB x M x ref --> X x M */
 923                 op1mode == mode_M && mode_is_reference(op2mode) &&
 924                 mymode == mode_T, "Raise node", 0
 925         );
 926         return 1;
 927 }
 928
 929 /**
 930  * verify a Const node
 931  */
 932 static int verify_node_Const(ir_node *n, ir_graph *irg)
 933 {
 934         ir_mode *mymode = get_irn_mode(n);
 935         (void) irg;
 936
 937         ASSERT_AND_RET(
 938                 /* Const: BB --> data */
 939                 (mode_is_data(mymode) ||
 940                 mymode == mode_b)      /* we want boolean constants for static evaluation */
 941                 ,"Const node", 0       /* of Cmp. */
 942         );
 943         ASSERT_AND_RET(
 944                 /* the modes of the constant and teh tarval must match */
 945                 mymode == get_tarval_mode(get_Const_tarval(n)),
 946                 "Const node, tarval and node mode mismatch", 0
 947         );
 948         return 1;
 949 }
 950
 951 /**
 952  * verify a SymConst node
 953  */
 954 static int verify_node_SymConst(ir_node *n, ir_graph *irg)
 955 {
 956         ir_mode *mymode = get_irn_mode(n);
 957         (void) irg;
 958
 959         ASSERT_AND_RET(
 960                 /* SymConst: BB --> int*/
 961                 (mode_is_int(mymode) ||
 962                 /* SymConst: BB --> ref */
 963                 mode_is_reference(mymode))
 964                 ,"SymConst node", 0);
 965         return 1;
 966 }
 967
 968 /**
 969  * verify a Sel node
 970  */
 971 static int verify_node_Sel(ir_node *n, ir_graph *irg)
 972 {
 973         int i;
 974         ir_mode *mymode  = get_irn_mode(n);
 975         ir_mode *op1mode = get_irn_mode(get_Sel_mem(n));
 976         ir_mode *op2mode = get_irn_mode(get_Sel_ptr(n));
 977         ir_entity *ent;
 978         (void) irg;
 979
 980         ASSERT_AND_RET_DBG(
 981                 /* Sel: BB x M x ref x int^n --> ref */
 982                 (op1mode == mode_M && op2mode == mymode && mode_is_reference(mymode)),
 983                 "Sel node", 0, show_node_failure(n)
 984         );
 985
 986         for (i = get_Sel_n_indexs(n) - 1; i >= 0; --i) {
 987                 ASSERT_AND_RET_DBG(mode_is_int(get_irn_mode(get_Sel_index(n, i))), "Sel node", 0, show_node_failure(n));
 988         }
 989         ent = get_Sel_entity(n);
 990         ASSERT_AND_RET_DBG(ent, "Sel node with empty entity", 0, show_node_failure(n));
 991         return 1;
 992 }
 993
 994 /**
 995  * verify an InstOf node
 996  */
 997 static int verify_node_InstOf(ir_node *n, ir_graph *irg)
 998 {
 999         ir_mode *mymode  = get_irn_mode(n);
1000         ir_mode *op1mode = get_irn_mode(get_InstOf_obj(n));
1001         (void) irg;
1002
1003         ASSERT_AND_RET(mode_T == mymode, "mode of Instof is not a tuple", 0);
1004         ASSERT_AND_RET(mode_is_data(op1mode), "Instof not on data", 0);
1005         return 1;
1006 }
1007
1008 /**
1009  * Check if the pinned state is right.
1010  */
1011 static int verify_right_pinned(ir_node *n)
1012 {
1013         ir_node *mem;
1014
1015         if (get_irn_pinned(n) == op_pin_state_pinned)
1016                 return 1;
1017         mem = get_Call_mem(n);
1018
1019         /* if it's not pinned, its memory predecessor must be NoMem or Pin */
1020         if (is_NoMem(mem) || is_Pin(mem))
1021                 return 1;
1022         return 0;
1023 }
1024
1025 /**
1026  * verify a Call node
1027  */
1028 static int verify_node_Call(ir_node *n, ir_graph *irg)
1029 {
1030         ir_mode *mymode  = get_irn_mode(n);
1031         ir_mode *op1mode = get_irn_mode(get_Call_mem(n));
1032         ir_mode *op2mode = get_irn_mode(get_Call_ptr(n));
1033         ir_type *mt;
1034         size_t i;
1035         size_t n_params;
1036         (void) irg;
1037
1038         /* Call: BB x M x ref x data1 x ... x datan
1039         --> M x datan+1 x ... x data n+m */
1040         ASSERT_AND_RET( op1mode == mode_M && mode_is_reference(op2mode), "Call node", 0 );  /* operand M x ref */
1041
1042         /* NoMem nodes are only allowed as memory input if the Call is NOT pinned */
1043         ASSERT_AND_RET(verify_right_pinned(n),"Call node with wrong memory input", 0 );
1044
1045         mt = get_Call_type(n);
1046         if (get_unknown_type() == mt) {
1047                 return 1;
1048         }
1049
1050         n_params = get_Call_n_params(n);
1051         for (i = 0; i < n_params; ++i) {
1052                 ASSERT_AND_RET( mode_is_datab(get_irn_mode(get_Call_param(n, i))), "Call node", 0 );  /* operand datai */
1053         }
1054
1055         ASSERT_AND_RET( mymode == mode_T, "Call result not a tuple", 0 );   /* result T */
1056         /* Compare arguments of node with those of type */
1057
1058         if (get_method_variadicity(mt) == variadicity_variadic) {
1059                 ASSERT_AND_RET_DBG(
1060                         get_Call_n_params(n) >= get_method_n_params(mt),
1061                         "Number of args for Call doesn't match number of args in variadic type.",
1062                         0,
1063                         ir_fprintf(stderr, "Call %+F has %d params, type %d\n",
1064                         n, get_Call_n_params(n), get_method_n_params(mt));
1065                 );
1066         } else {
1067                 ASSERT_AND_RET_DBG(
1068                         get_Call_n_params(n) == get_method_n_params(mt),
1069                         "Number of args for Call doesn't match number of args in non variadic type.",
1070                         0,
1071                         ir_fprintf(stderr, "Call %+F has %d params, type %d\n",
1072                         n, get_Call_n_params(n), get_method_n_params(mt));
1073                 );
1074         }
1075
1076         for (i = 0; i < get_method_n_params(mt); i++) {
1077                 ir_type *t = get_method_param_type(mt, i);
1078
1079                 if (get_irg_phase_state(irg) != phase_backend) {
1080                         if (is_atomic_type(t)) {
1081                                 ASSERT_AND_RET_DBG(
1082                                         get_irn_mode(get_Call_param(n, i)) == get_type_mode(t),
1083                                         "Mode of arg for Call doesn't match mode of arg type.", 0,
1084                                         show_call_param(n, mt);
1085                                 );
1086                         } else {
1087                                 /* call with a compound type, mode must be reference */
1088                                 ASSERT_AND_RET_DBG(
1089                                         mode_is_reference(get_irn_mode(get_Call_param(n, i))),
1090                                         "Mode of arg for Call doesn't match mode of arg type.", 0,
1091                                         show_call_param(n, mt);
1092                                 );
1093                         }
1094                 }
1095         }
1096
1097 #if 0
1098         if (Call_has_callees(n)) {
1099                 for (i = 0; i < get_Call_n_callees(n); i++) {
1100                         ASSERT_AND_RET(is_entity(get_Call_callee(n, i)), "callee array must contain entities.", 0);
1101                 }
1102         }
1103 #endif
1104         return 1;
1105 }
1106
1107 /**
1108  * verify an Add node
1109  */
1110 static int verify_node_Add(ir_node *n, ir_graph *irg)
1111 {
1112         ir_mode *mymode  = get_irn_mode(n);
1113         ir_mode *op1mode = get_irn_mode(get_Add_left(n));
1114         ir_mode *op2mode = get_irn_mode(get_Add_right(n));
1115         (void) irg;
1116
1117         ASSERT_AND_RET_DBG(
1118                 (
1119                         /* common Add: BB x numP x numP --> numP */
1120                         (op1mode == mymode && op2mode == op1mode && mode_is_data(mymode)) ||
1121                         /* Pointer Add: BB x ref x int --> ref */
1122                         (mode_is_reference(op1mode) && mode_is_int(op2mode) && op1mode == mymode) ||
1123                         /* Pointer Add: BB x int x ref --> ref */
1124                         (mode_is_int(op1mode) && op2mode == mymode && mode_is_reference(mymode))
1125                 ),
1126                 "Add node", 0,
1127                 show_binop_failure(n, "/* common Add: BB x numP x numP --> numP */ |\n"
1128                         "/* Pointer Add: BB x ref x int --> ref */   |\n"
1129                         "/* Pointer Add: BB x int x ref --> ref */");
1130         );
1131         return 1;
1132 }
1133
1134 /**
1135  * verify a Sub node
1136  */
1137 static int verify_node_Sub(ir_node *n, ir_graph *irg)
1138 {
1139         ir_mode *mymode  = get_irn_mode(n);
1140         ir_mode *op1mode = get_irn_mode(get_Sub_left(n));
1141         ir_mode *op2mode = get_irn_mode(get_Sub_right(n));
1142         (void) irg;
1143
1144         ASSERT_AND_RET_DBG(
1145                 (
1146                         /* common Sub: BB x numP x numP --> numP */
1147                         (mymode ==op1mode && mymode == op2mode && mode_is_data(op1mode)) ||
1148                         /* Pointer Sub: BB x ref x int --> ref */
1149                         (op1mode == mymode && mode_is_int(op2mode) && mode_is_reference(mymode)) ||
1150                         /* Pointer Sub: BB x ref x ref --> int */
1151                         (op1mode == op2mode && mode_is_reference(op2mode) && mode_is_int(mymode))
1152                 ),
1153                 "Sub node", 0,
1154                 show_binop_failure(n, "/* common Sub: BB x numP x numP --> numP */ |\n"
1155                         "/* Pointer Sub: BB x ref x int --> ref */   |\n"
1156                         "/* Pointer Sub: BB x ref x ref --> int */" );
1157                 );
1158         return 1;
1159 }
1160
1161 /**
1162  * verify a Minus node
1163  */
1164 static int verify_node_Minus(ir_node *n, ir_graph *irg)
1165 {
1166         ir_mode *mymode  = get_irn_mode(n);
1167         ir_mode *op1mode = get_irn_mode(get_Minus_op(n));
1168         (void) irg;
1169
1170         ASSERT_AND_RET_DBG(
1171                 /* Minus: BB x num --> num */
1172                 op1mode == mymode && mode_is_num(op1mode), "Minus node", 0,
1173                 show_unop_failure(n , "/* Minus: BB x num --> num */");
1174         );
1175         return 1;
1176 }
1177
1178 /**
1179  * verify a Mul node
1180  */
1181 static int verify_node_Mul(ir_node *n, ir_graph *irg)
1182 {
1183         ir_mode *mymode  = get_irn_mode(n);
1184         ir_mode *op1mode = get_irn_mode(get_Mul_left(n));
1185         ir_mode *op2mode = get_irn_mode(get_Mul_right(n));
1186         (void) irg;
1187
1188         ASSERT_AND_RET_DBG(
1189                 (
1190                         /* Mul: BB x int_n x int_n --> int_n|int_2n */
1191                         (mode_is_int(op1mode)   && op2mode == op1mode && mode_is_int(mymode) &&
1192                          (op1mode == mymode || get_mode_size_bits(op1mode) * 2 == get_mode_size_bits(mymode))) ||
1193                         /* Mul: BB x float x float --> float */
1194                         (mode_is_float(op1mode) && op2mode == op1mode && mymode == op1mode)
1195                 ),
1196                 "Mul node",0,
1197                 show_binop_failure(n, "/* Mul: BB x int_n x int_n --> int_n|int_2n */ |\n"
1198                 "/* Mul: BB x float x float --> float */");
1199         );
1200         return 1;
1201 }
1202
1203 /**
1204  * verify a Mulh node
1205  */
1206 static int verify_node_Mulh(ir_node *n, ir_graph *irg)
1207 {
1208         ir_mode *mymode  = get_irn_mode(n);
1209         ir_mode *op1mode = get_irn_mode(get_Mulh_left(n));
1210         ir_mode *op2mode = get_irn_mode(get_Mulh_right(n));
1211         (void) irg;
1212
1213         ASSERT_AND_RET_DBG(
1214                 (
1215                         /* Mulh: BB x int x int --> int */
1216                         (mode_is_int(op1mode) && op2mode == op1mode && op1mode == mymode)
1217                 ),
1218                 "Mulh node",0,
1219                 show_binop_failure(n, "/* Mulh: BB x int x int --> int */");
1220         );
1221         return 1;
1222 }
1223
1224 /**
1225  * verify a Div node
1226  */
1227 static int verify_node_Div(ir_node *n, ir_graph *irg)
1228 {
1229         ir_mode *mymode  = get_irn_mode(n);
1230         ir_mode *op1mode = get_irn_mode(get_Div_mem(n));
1231         ir_mode *op2mode = get_irn_mode(get_Div_left(n));
1232         ir_mode *op3mode = get_irn_mode(get_Div_right(n));
1233         (void) irg;
1234
1235         ASSERT_AND_RET(
1236                 /* Div: BB x M x data x data --> M x X x data */
1237                 op1mode == mode_M &&
1238                 op2mode == op3mode &&
1239                 mode_is_data(op2mode) &&
1240                 mymode == mode_T,
1241                 "Div node", 0
1242                 );
1243         return 1;
1244 }
1245
1246 /**
1247  * verify a Mod node
1248  */
1249 static int verify_node_Mod(ir_node *n, ir_graph *irg)
1250 {
1251         ir_mode *mymode  = get_irn_mode(n);
1252         ir_mode *op1mode = get_irn_mode(get_Mod_mem(n));
1253         ir_mode *op2mode = get_irn_mode(get_Mod_left(n));
1254         ir_mode *op3mode = get_irn_mode(get_Mod_right(n));
1255         (void) irg;
1256
1257         ASSERT_AND_RET(
1258                 /* Mod: BB x M x int x int --> M x X x int */
1259                 op1mode == mode_M &&
1260                 op2mode == op3mode &&
1261                 mode_is_int(op2mode) &&
1262                 mymode == mode_T,
1263                 "Mod node", 0
1264                 );
1265         return 1;
1266 }
1267
1268 /**
1269  * verify a logical And, Or, Eor node
1270  */
1271 static int verify_node_Logic(ir_node *n, ir_graph *irg)
1272 {
1273         ir_mode *mymode  = get_irn_mode(n);
1274         ir_mode *op1mode = get_irn_mode(get_binop_left(n));
1275         ir_mode *op2mode = get_irn_mode(get_binop_right(n));
1276         (void) irg;
1277
1278         ASSERT_AND_RET_DBG(
1279                 /* And or Or or Eor: BB x int x int --> int */
1280                 (mode_is_int(mymode) || mode_is_reference(mymode) || mymode == mode_b) &&
1281                 op2mode == op1mode &&
1282                 mymode == op2mode,
1283                 "And, Or or Eor node", 0,
1284                 show_binop_failure(n, "/* And or Or or Eor: BB x int x int --> int */");
1285         );
1286         return 1;
1287 }
1288
1289 #define verify_node_And   verify_node_Logic
1290 #define verify_node_Or    verify_node_Logic
1291 #define verify_node_Eor   verify_node_Logic
1292
1293 /**
1294  * verify a Not node
1295  */
1296 static int verify_node_Not(ir_node *n, ir_graph *irg)
1297 {
1298         ir_mode *mymode  = get_irn_mode(n);
1299         ir_mode *op1mode = get_irn_mode(get_Not_op(n));
1300         (void) irg;
1301
1302         ASSERT_AND_RET_DBG(
1303                 /* Not: BB x int --> int */
1304                 (mode_is_int(mymode) || mymode == mode_b) &&
1305                 mymode == op1mode,
1306                 "Not node", 0,
1307                 show_unop_failure(n, "/* Not: BB x int --> int */");
1308         );
1309         return 1;
1310 }
1311
1312 /**
1313  * verify a Cmp node
1314  */
1315 static int verify_node_Cmp(ir_node *n, ir_graph *irg)
1316 {
1317         ir_mode *mymode  = get_irn_mode(n);
1318         ir_mode *op1mode = get_irn_mode(get_Cmp_left(n));
1319         ir_mode *op2mode = get_irn_mode(get_Cmp_right(n));
1320         (void) irg;
1321
1322         ASSERT_AND_RET_DBG(
1323                 /* Cmp: BB x datab x datab --> b16 */
1324                 mode_is_datab(op1mode) &&
1325                 op2mode == op1mode &&
1326                 mymode == mode_b,
1327                 "Cmp node", 0,
1328                 show_binop_failure(n, "/* Cmp: BB x datab x datab --> b16 */");
1329         );
1330         return 1;
1331 }
1332
1333 /**
1334  * verify a Shift node
1335  */
1336 static int verify_node_Shift(ir_node *n, ir_graph *irg)
1337 {
1338         ir_mode *mymode  = get_irn_mode(n);
1339         ir_mode *op1mode = get_irn_mode(get_binop_left(n));
1340         ir_mode *op2mode = get_irn_mode(get_binop_right(n));
1341         (void) irg;
1342
1343         ASSERT_AND_RET_DBG(
1344                 /* Shl, Shr or Shrs: BB x int x int_u --> int */
1345                 mode_is_int(op1mode) &&
1346                 mode_is_int(op2mode) &&
1347                 !mode_is_signed(op2mode) &&
1348                 mymode == op1mode,
1349                 "Shl, Shr or Shrs node", 0,
1350                 show_binop_failure(n, "/* Shl, Shr or Shrs: BB x int x int_u --> int */");
1351         );
1352         return 1;
1353 }
1354
1355 #define verify_node_Shl   verify_node_Shift
1356 #define verify_node_Shr   verify_node_Shift
1357 #define verify_node_Shrs  verify_node_Shift
1358
1359 /**
1360  * verify a Rotl node
1361  */
1362 static int verify_node_Rotl(ir_node *n, ir_graph *irg)
1363 {
1364         ir_mode *mymode  = get_irn_mode(n);
1365         ir_mode *op1mode = get_irn_mode(get_Rotl_left(n));
1366         ir_mode *op2mode = get_irn_mode(get_Rotl_right(n));
1367         (void) irg;
1368
1369         ASSERT_AND_RET_DBG(
1370                 /* Rotl: BB x int x int --> int */
1371                 mode_is_int(op1mode) &&
1372                 mode_is_int(op2mode) &&
1373                 mymode == op1mode,
1374                 "Rotl node", 0,
1375                 show_binop_failure(n, "/* Rotl: BB x int x int --> int */");
1376         );
1377         return 1;
1378 }
1379
1380 /**
1381  * verify a Conv node
1382  */
1383 static int verify_node_Conv(ir_node *n, ir_graph *irg)
1384 {
1385         ir_mode *mymode  = get_irn_mode(n);
1386         ir_mode *op1mode = get_irn_mode(get_Conv_op(n));
1387         (void) irg;
1388
1389         ASSERT_AND_RET_DBG(
1390                 is_irg_state(irg, IR_GRAPH_STATE_BCONV_ALLOWED) ||
1391                 (mode_is_datab(op1mode) && mode_is_data(mymode)),
1392                 "Conv node", 0,
1393                 show_unop_failure(n, "/* Conv: BB x datab --> data */");
1394         );
1395         return 1;
1396 }
1397
1398 /**
1399  * verify a Cast node
1400  */
1401 static int verify_node_Cast(ir_node *n, ir_graph *irg)
1402 {
1403         ir_mode *mymode  = get_irn_mode(n);
1404         ir_mode *op1mode = get_irn_mode(get_Cast_op(n));
1405         (void) irg;
1406
1407         ASSERT_AND_RET_DBG(
1408                 /* Conv: BB x datab1 --> datab2 */
1409                 mode_is_data(op1mode) && op1mode == mymode,
1410                 "Cast node", 0,
1411                 show_unop_failure(n, "/* Conv: BB x datab1 --> datab2 */");
1412         );
1413         return 1;
1414 }
1415
1416 /**
1417  * verify a Phi node
1418  */
1419 static int verify_node_Phi(ir_node *n, ir_graph *irg)
1420 {
1421         ir_mode *mymode = get_irn_mode(n);
1422         ir_node *block  = get_nodes_block(n);
1423         int i;
1424         (void) irg;
1425
1426         /* a Phi node MUST have the same number of inputs as its block
1427          * Exception is a phi with 0 inputs which is used when (re)constructing the
1428          * SSA form */
1429         if (! is_Bad(block) && get_irg_phase_state(get_irn_irg(n)) != phase_building && get_irn_arity(n) > 0) {
1430                 ASSERT_AND_RET_DBG(
1431                         get_irn_arity(n) == get_irn_arity(block),
1432                         "wrong number of inputs in Phi node", 0,
1433                         show_phi_inputs(n, block);
1434                 );
1435         }
1436
1437         /* Phi: BB x dataM^n --> dataM */
1438         for (i = get_Phi_n_preds(n) - 1; i >= 0; --i) {
1439                 ir_node *pred = get_Phi_pred(n, i);
1440                 if (!is_Bad(pred)) {
1441                         ASSERT_AND_RET_DBG(
1442                                 get_irn_mode(pred) == mymode,
1443                                 "Phi node", 0,
1444                                 show_phi_failure(n, pred, i);
1445                         );
1446                 }
1447         }
1448         ASSERT_AND_RET(mode_is_dataM(mymode) || mymode == mode_b, "Phi node", 0 );
1449
1450         if (mymode == mode_M) {
1451                 for (i = get_Phi_n_preds(n) - 1; i >= 0; --i) {
1452                         int j;
1453                         ir_node *pred_i = get_Phi_pred(n, i);
1454
1455                         if (is_Bad(pred_i))
1456                                 continue;
1457                         for (j = i - 1; j >= 0; --j) {
1458                                 ir_node *pred_j = get_Phi_pred(n, j);
1459
1460                                 if (is_Bad(pred_j))
1461                                         continue;
1462 #if 0
1463                                 /* currently this checks fails for blocks with exception
1464                                    outputs (and these are NOT basic blocks).  So it is disabled yet. */
1465                                 ASSERT_AND_RET_DBG(
1466                                         (pred_i == pred_j) || (get_irn_n(pred_i, -1) != get_irn_n(pred_j, -1)),
1467                                         "At least two different PhiM predecessors are in the same block",
1468                                         0,
1469                                         ir_printf("%+F and %+F of %+F are in %+F\n", pred_i, pred_j, n, get_irn_n(pred_i, -1))
1470                                 );
1471 #endif
1472                         }
1473                 }
1474         }
1475         return 1;
1476 }
1477
1478 /**
1479  * verify a Load node
1480  */
1481 static int verify_node_Load(ir_node *n, ir_graph *irg)
1482 {
1483         ir_mode *mymode  = get_irn_mode(n);
1484         ir_mode *op1mode = get_irn_mode(get_Load_mem(n));
1485         ir_mode *op2mode = get_irn_mode(get_Load_ptr(n));
1486
1487         ASSERT_AND_RET(op1mode == mode_M, "Load node", 0);
1488         if (get_irg_phase_state(irg) != phase_backend) {
1489                 ASSERT_AND_RET(mode_is_reference(op2mode), "Load node", 0 );
1490         }
1491         ASSERT_AND_RET( mymode == mode_T, "Load node", 0 );
1492
1493         /*
1494          * jack's gen_add_firm_code:simpleSel seems to build Load (Load
1495          * (Proj (Proj))) sometimes ...
1496
1497          * interprete.c:ai_eval seems to assume that this happens, too
1498
1499          * obset.c:get_abstval_any can't deal with this if the load has
1500          * mode_T
1501          *
1502           {
1503           ir_entity *ent = hunt_for_entity (get_Load_ptr (n), n);
1504           assert ((NULL != ent) || (mymode != mode_T));
1505           }
1506          */
1507
1508         return 1;
1509 }
1510
1511 /**
1512  * verify a Store node
1513  */
1514 static int verify_node_Store(ir_node *n, ir_graph *irg)
1515 {
1516         ir_entity *target;
1517
1518         ir_mode *mymode  = get_irn_mode(n);
1519         ir_mode *op1mode = get_irn_mode(get_Store_mem(n));
1520         ir_mode *op2mode = get_irn_mode(get_Store_ptr(n));
1521         ir_mode *op3mode = get_irn_mode(get_Store_value(n));
1522
1523         ASSERT_AND_RET(op1mode == mode_M && mode_is_datab(op3mode), "Store node", 0 );
1524         if (get_irg_phase_state(irg) != phase_backend) {
1525                 ASSERT_AND_RET(mode_is_reference(op2mode), "Store node", 0 );
1526         }
1527         ASSERT_AND_RET(mymode == mode_T, "Store node", 0);
1528
1529         target = get_ptr_entity(get_Store_ptr(n));
1530         if (verify_entities && target && get_irg_phase_state(irg) == phase_high) {
1531                 /*
1532                  * If lowered code, any Sels that add 0 may be removed, causing
1533                  * an direct access to entities of array or compound type.
1534                  * Prevent this by checking the phase.
1535                  */
1536                 ASSERT_AND_RET( op3mode == get_type_mode(get_entity_type(target)),
1537                         "Store node", 0);
1538         }
1539
1540         return 1;
1541 }
1542
1543 /**
1544  * verify an Alloc node
1545  */
1546 static int verify_node_Alloc(ir_node *n, ir_graph *irg)
1547 {
1548         ir_mode *mymode  = get_irn_mode(n);
1549         ir_mode *op1mode = get_irn_mode(get_Alloc_mem(n));
1550         ir_mode *op2mode = get_irn_mode(get_Alloc_count(n));
1551         (void) irg;
1552
1553         ASSERT_AND_RET_DBG(
1554                 /* Alloc: BB x M x int_u --> M x X x ref */
1555                 op1mode == mode_M &&
1556                 mode_is_int(op2mode) &&
1557                 !mode_is_signed(op2mode) &&
1558                 mymode == mode_T,
1559                 "Alloc node", 0,
1560                 show_node_failure(n);
1561         );
1562         return 1;
1563 }
1564
1565 /**
1566  * verify a Free node
1567  */
1568 static int verify_node_Free(ir_node *n, ir_graph *irg)
1569 {
1570         ir_mode *mymode  = get_irn_mode(n);
1571         ir_mode *op1mode = get_irn_mode(get_Free_mem(n));
1572         ir_mode *op2mode = get_irn_mode(get_Free_ptr(n));
1573         ir_mode *op3mode = get_irn_mode(get_Free_size(n));
1574         (void) irg;
1575
1576         ASSERT_AND_RET_DBG(
1577                 /* Free: BB x M x ref x int_u --> M */
1578                 op1mode == mode_M && mode_is_reference(op2mode) &&
1579                 mode_is_int(op3mode) &&
1580                 !mode_is_signed(op3mode) &&
1581                 mymode == mode_M,
1582                 "Free node", 0,
1583                 show_triop_failure(n, "/* Free: BB x M x ref x int_u --> M */");
1584         );
1585         return 1;
1586 }
1587
1588 /**
1589  * verify a Sync node
1590  */
1591 static int verify_node_Sync(ir_node *n, ir_graph *irg)
1592 {
1593         int i;
1594         ir_mode *mymode  = get_irn_mode(n);
1595         (void) irg;
1596
1597         /* Sync: BB x M^n --> M */
1598         for (i = get_Sync_n_preds(n) - 1; i >= 0; --i) {
1599                 ASSERT_AND_RET( get_irn_mode(get_Sync_pred(n, i)) == mode_M, "Sync node", 0 );
1600         };
1601         ASSERT_AND_RET( mymode == mode_M, "Sync node", 0 );
1602         return 1;
1603 }
1604
1605 /**
1606  * verify a Confirm node
1607  */
1608 static int verify_node_Confirm(ir_node *n, ir_graph *irg)
1609 {
1610         ir_mode *mymode  = get_irn_mode(n);
1611         ir_mode *op1mode = get_irn_mode(get_Confirm_value(n));
1612         ir_mode *op2mode = get_irn_mode(get_Confirm_bound(n));
1613         (void) irg;
1614
1615         ASSERT_AND_RET_DBG(
1616                 /* Confirm: BB x T x T --> T */
1617                 op1mode == mymode &&
1618                 op2mode == mymode,
1619                 "Confirm node", 0,
1620                 show_binop_failure(n, "/* Confirm: BB x T x T --> T */");
1621         );
1622         return 1;
1623 }
1624
1625 /**
1626  * verify a Mux node
1627  */
1628 static int verify_node_Mux(ir_node *n, ir_graph *irg)
1629 {
1630         ir_mode *mymode  = get_irn_mode(n);
1631         ir_mode *op1mode = get_irn_mode(get_Mux_sel(n));
1632         ir_mode *op2mode = get_irn_mode(get_Mux_true(n));
1633         ir_mode *op3mode = get_irn_mode(get_Mux_false(n));
1634         (void) irg;
1635
1636         ASSERT_AND_RET(
1637                 /* Mux: BB x b x datab x datab --> datab */
1638                 op1mode == mode_b &&
1639                 op2mode == mymode &&
1640                 op3mode == mymode &&
1641                 mode_is_datab(mymode),
1642                 "Mux node", 0
1643                 );
1644         return 1;
1645 }
1646
1647 /**
1648  * verify a CopyB node
1649  */
1650 static int verify_node_CopyB(ir_node *n, ir_graph *irg)
1651 {
1652         ir_mode *mymode  = get_irn_mode(n);
1653         ir_mode *op1mode = get_irn_mode(get_CopyB_mem(n));
1654         ir_mode *op2mode = get_irn_mode(get_CopyB_dst(n));
1655         ir_mode *op3mode = get_irn_mode(get_CopyB_src(n));
1656         ir_type *t = get_CopyB_type(n);
1657
1658         /* CopyB: BB x M x ref x ref --> M x X */
1659         ASSERT_AND_RET(mymode == mode_T && op1mode == mode_M, "CopyB node", 0);
1660         if (get_irg_phase_state(irg) != phase_backend) {
1661                 ASSERT_AND_RET(mode_is_reference(op2mode) && mode_is_reference(op3mode),
1662                         "CopyB node", 0 );
1663         }
1664
1665         ASSERT_AND_RET(
1666                 is_compound_type(t) || is_Array_type(t),
1667                 "CopyB node should copy compound types only", 0 );
1668
1669         /* NoMem nodes are only allowed as memory input if the CopyB is NOT pinned.
1670            This should happen RARELY, as CopyB COPIES MEMORY */
1671         ASSERT_AND_RET(verify_right_pinned(n), "CopyB node with wrong memory input", 0 );
1672         return 1;
1673 }
1674
1675 /**
1676  * verify a Bound node
1677  */
1678 static int verify_node_Bound(ir_node *n, ir_graph *irg)
1679 {
1680         ir_mode *mymode  = get_irn_mode(n);
1681         ir_mode *op1mode = get_irn_mode(get_Bound_mem(n));
1682         ir_mode *op2mode = get_irn_mode(get_Bound_index(n));
1683         ir_mode *op3mode = get_irn_mode(get_Bound_lower(n));
1684         ir_mode *op4mode = get_irn_mode(get_Bound_upper(n));
1685         (void) irg;
1686
1687         /* Bound: BB x M x int x int x int --> M x X */
1688         ASSERT_AND_RET(
1689                 mymode == mode_T &&
1690                 op1mode == mode_M &&
1691                 op2mode == op3mode &&
1692                 op3mode == op4mode &&
1693                 mode_is_int(op3mode),
1694                 "Bound node", 0 );
1695         return 1;
1696 }
1697
1698 /**
1699  * Check dominance.
1700  * For each usage of a node, it is checked, if the block of the
1701  * node dominates the block of the usage (for phis: the predecessor
1702  * block of the phi for the corresponding edge).
1703  *
1704  * @return non-zero on success, 0 on dominance error
1705  */
1706 static int check_dominance_for_node(ir_node *use)
1707 {
1708         /* This won't work for blocks and the end node */
1709         if (!is_Block(use) && !is_End(use) && !is_Anchor(use)) {
1710                 int i;
1711                 ir_node *bl = get_nodes_block(use);
1712
1713                 for (i = get_irn_arity(use) - 1; i >= 0; --i) {
1714                         ir_node  *def    = get_irn_n(use, i);
1715                         ir_node  *def_bl = get_nodes_block(def);
1716                         ir_node  *use_bl = bl;
1717                         ir_graph *irg;
1718
1719                         /* we have no dominance relation for unreachable blocks, so we can't
1720                          * check the dominance property there */
1721                         if (!is_Block(def_bl) || get_Block_dom_depth(def_bl) == -1)
1722                                 continue;
1723
1724                         if (is_Phi(use)) {
1725                                 if (is_Bad(def))
1726                                         continue;
1727                                 use_bl = get_Block_cfgpred_block(bl, i);
1728                         }
1729
1730                         if (!is_Block(use_bl) || get_Block_dom_depth(use_bl) == -1)
1731                                 continue;
1732
1733                         irg = get_irn_irg(use);
1734                         ASSERT_AND_RET_DBG(
1735                                 block_dominates(def_bl, use_bl),
1736                                 "the definition of a value used violates the dominance property", 0,
1737                                 ir_fprintf(stderr,
1738                                 "graph %+F: %+F of %+F must dominate %+F of user %+F input %d\n",
1739                                 irg, def_bl, def, use_bl, use, i
1740                                 );
1741                         );
1742                 }
1743         }
1744         return 1;
1745 }
1746
1747 /* Tests the modes of n and its predecessors. */
1748 int irn_verify_irg(ir_node *n, ir_graph *irg)
1749 {
1750         ir_op *op;
1751
1752         if (!get_node_verification_mode())
1753                 return 1;
1754
1755         /*
1756          * do NOT check placement in interprocedural view, as we don't always
1757          * know the "right" graph ...
1758          */
1759
1760 #ifndef NDEBUG
1761         /* this is an expensive check for large graphs (it has a quadratic
1762          * runtime but with a small constant); so do NOT run it in release mode
1763          */
1764         ASSERT_AND_RET_DBG(
1765                 node_is_in_irgs_storage(irg, n),
1766                 "Node is not stored on proper IR graph!", 0,
1767                 show_node_on_graph(irg, n);
1768         );
1769 #endif
1770         assert(get_irn_irg(n) == irg);
1771         {
1772                 unsigned idx           = get_irn_idx(n);
1773                 ir_node *node_from_map = get_idx_irn(irg, idx);
1774                 ASSERT_AND_RET_DBG(node_from_map == n, "Node index and index map entry differ", 0,
1775                         ir_printf("node %+F node in map %+F(%p)\n", n, node_from_map, node_from_map));
1776         }
1777
1778         op = get_irn_op(n);
1779
1780         if (_get_op_pinned(op) >= op_pin_state_exc_pinned) {
1781                 op_pin_state state = get_irn_pinned(n);
1782                 ASSERT_AND_RET_DBG(
1783                         state == op_pin_state_floats ||
1784                         state == op_pin_state_pinned,
1785                         "invalid pin state", 0,
1786                         ir_printf("node %+F", n));
1787         } else if (!is_Block(n) && is_irn_pinned_in_irg(n)
1788                    && !is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK)) {
1789                 ASSERT_AND_RET_DBG(is_Block(get_nodes_block(n)) || is_Anchor(n),
1790                                 "block input is not a block", 0,
1791                                 ir_printf("node %+F", n));
1792         }
1793
1794         /* We don't want to test nodes whose predecessors are Bad,
1795            as we would have to special case that for each operation. */
1796         if (op != op_Phi && op != op_Block) {
1797                 int i;
1798                 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
1799                         if (is_Bad(get_irn_n(n, i)))
1800                                 return 1;
1801                 }
1802         }
1803
1804         if (op->ops.verify_node)
1805                 return op->ops.verify_node(n, irg);
1806
1807         /* All went ok */
1808         return 1;
1809 }
1810
1811 int irn_verify(ir_node *n)
1812 {
1813 #ifdef DEBUG_libfirm
1814         return irn_verify_irg(n, get_irn_irg(n));
1815 #else
1816         (void)n;
1817         return 1;
1818 #endif
1819 }
1820
1821 /*-----------------------------------------------------------------*/
1822 /* Verify the whole graph.                                         */
1823 /*-----------------------------------------------------------------*/
1824
1825 #ifdef DEBUG_libfirm
1826 /**
1827  * Walker to check every node
1828  */
1829 static void verify_wrap(ir_node *node, void *env)
1830 {
1831         int *res = (int*)env;
1832         *res = irn_verify_irg(node, get_irn_irg(node));
1833 }
1834
1835 /**
1836  * Walker to check every node including SSA property.
1837  * Only called if dominance info is available.
1838  */
1839 static void verify_wrap_ssa(ir_node *node, void *env)
1840 {
1841         int *res = (int*)env;
1842
1843         *res = irn_verify_irg(node, get_irn_irg(node));
1844         if (*res) {
1845                 *res = check_dominance_for_node(node);
1846         }
1847 }
1848
1849 #endif /* DEBUG_libfirm */
1850
1851 typedef struct check_cfg_env_t {
1852         pmap *branch_nodes; /**< map blocks to their branching nodes,
1853                                  map mode_X nodes to the blocks they branch to */
1854         int   res;
1855         ir_nodeset_t ignore_nodes;
1856         ir_nodeset_t kept_nodes;
1857         ir_nodeset_t true_projs;
1858         ir_nodeset_t false_projs;
1859 } check_cfg_env_t;
1860
1861 static int check_cfg_node(ir_node *node, check_cfg_env_t *env)
1862 {
1863         pmap    *branch_nodes = env->branch_nodes;
1864         ir_mode *mode         = get_irn_mode(node);
1865
1866         if (ir_nodeset_contains(&env->ignore_nodes, node))
1867                 return 1;
1868
1869         if (mode == mode_X) {
1870                 ir_node *block         = get_nodes_block(node);
1871                 ir_node *former_branch = pmap_get(branch_nodes, block);
1872                 ir_node *skipped       = skip_Tuple(node);
1873                 ir_node *branch        = skipped;
1874
1875                 if (is_Proj(branch)) {
1876                         branch = skip_Proj(branch);
1877                 }
1878
1879                 ASSERT_AND_RET_DBG(former_branch == NULL || former_branch == branch,
1880                                    "Multiple branching nodes in a block", 0,
1881                                    ir_printf("nodes %+F,%+F in block %+F\n",
1882                                              node, former_branch, block));
1883                 pmap_insert(branch_nodes, block, branch);
1884
1885                 if (is_Cond(branch)) {
1886                         long pn = get_Proj_proj(skipped);
1887                         if (get_irn_mode(get_Cond_selector(branch)) == mode_b) {
1888                                 if (pn == pn_Cond_true)
1889                                         ir_nodeset_insert(&env->true_projs, branch);
1890                                 if (pn == pn_Cond_false)
1891                                         ir_nodeset_insert(&env->false_projs, branch);
1892                         } else {
1893                                 int default_pn = get_Cond_default_proj(branch);
1894                                 if (pn == default_pn)
1895                                         ir_nodeset_insert(&env->true_projs, branch);
1896                         }
1897                 }
1898         } else if (is_Block(node)) {
1899                 int n_cfgpreds = get_Block_n_cfgpreds(node);
1900                 int i;
1901
1902                 for (i = 0; i < n_cfgpreds; ++i) {
1903                         ir_node *branch = get_Block_cfgpred(node, i);
1904                         ir_node *former_dest;
1905                         if (is_Bad(branch))
1906                                 continue;
1907                         former_dest = pmap_get(branch_nodes, branch);
1908                         ASSERT_AND_RET_DBG(former_dest==NULL || is_unknown_jump(skip_Proj(branch)),
1909                                            "Multiple users on mode_X node", 0,
1910                                            ir_printf("node %+F\n", node));
1911                         pmap_insert(branch_nodes, branch, node);
1912                 }
1913         } else if (is_Tuple(node)) {
1914                 int arity = get_irn_arity(node);
1915                 int i;
1916
1917                 for (i = 0; i < arity; ++i) {
1918                         ir_node *in = get_irn_n(node, i);
1919                         ir_nodeset_insert(&env->ignore_nodes, in);
1920                 }
1921         }
1922
1923         return 1;
1924 }
1925
1926 static void check_cfg_walk_func(ir_node *node, void *data)
1927 {
1928         check_cfg_env_t *env = (check_cfg_env_t*)data;
1929         int              res = check_cfg_node(node, env);
1930         env->res &= res;
1931 }
1932
1933 static int verify_block_branch(ir_node *block, check_cfg_env_t *env)
1934 {
1935         ir_node *branch = pmap_get(env->branch_nodes, block);
1936         ASSERT_AND_RET_DBG(branch != NULL || ir_nodeset_contains(&env->kept_nodes, block),
1937                            "block contains no cfop", 0,
1938                            ir_printf("block %+F\n", block));
1939         return 1;
1940 }
1941
1942 static int verify_cond_projs(ir_node *cond, check_cfg_env_t *env)
1943 {
1944         if (get_irn_mode(get_Cond_selector(cond)) == mode_b) {
1945                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->true_projs, cond),
1946                                                    "Cond node lacks true proj", 0,
1947                                                    ir_printf("Cond %+F\n", cond));
1948                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->false_projs, cond),
1949                                                    "Cond node lacks false proj", 0,
1950                                                    ir_printf("Cond %+F\n", cond));
1951         } else {
1952                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->true_projs, cond),
1953                                    "Cond node lacks default Proj", 0,
1954                                    ir_printf("Cond %+F\n", cond));
1955         }
1956         return 1;
1957 }
1958
1959 static void assert_branch(ir_node *node, void *data)
1960 {
1961         check_cfg_env_t *env = (check_cfg_env_t*)data;
1962         if (is_Block(node)) {
1963                 env->res &= verify_block_branch(node, env);
1964         } else if (is_Cond(node)) {
1965                 env->res &= verify_cond_projs(node, env);
1966         }
1967 }
1968
1969 /**
1970  * Checks CFG well-formedness
1971  */
1972 static int check_cfg(ir_graph *irg)
1973 {
1974         check_cfg_env_t env;
1975         env.branch_nodes = pmap_create(); /**< map blocks to branch nodes */
1976         env.res          = 1;
1977         ir_nodeset_init(&env.ignore_nodes);
1978         ir_nodeset_init(&env.true_projs);
1979         ir_nodeset_init(&env.false_projs);
1980
1981         /* note that we do not use irg_walk_block because it will miss these
1982          * invalid blocks without a jump instruction which we want to detect
1983          * here */
1984         irg_walk_graph(irg, check_cfg_walk_func, NULL, &env);
1985         ir_nodeset_destroy(&env.ignore_nodes);
1986
1987         ir_nodeset_init(&env.kept_nodes);
1988         {
1989                 ir_node *end   = get_irg_end(irg);
1990                 int      arity = get_irn_arity(end);
1991                 int      i;
1992                 for (i = 0; i < arity; ++i) {
1993                         ir_node *n = get_irn_n(end, i);
1994                         ir_nodeset_insert(&env.kept_nodes, n);
1995                 }
1996         }
1997         irg_walk_graph(irg, assert_branch, NULL, &env);
1998
1999         ir_nodeset_destroy(&env.false_projs);
2000         ir_nodeset_destroy(&env.true_projs);
2001         ir_nodeset_destroy(&env.kept_nodes);
2002         pmap_destroy(env.branch_nodes);
2003         return env.res;
2004 }
2005
2006 /*
2007  * Calls irn_verify for each node in irg.
2008  * Graph must be in state "op_pin_state_pinned".
2009  * If dominance info is available, check the SSA property.
2010  */
2011 int irg_verify(ir_graph *irg, unsigned flags)
2012 {
2013         int res = 1;
2014 #ifdef DEBUG_libfirm
2015         int pinned = get_irg_pinned(irg) == op_pin_state_pinned;
2016
2017 #ifndef NDEBUG
2018         last_irg_error = NULL;
2019 #endif /* NDEBUG */
2020
2021         if (!check_cfg(irg))
2022                 res = 0;
2023
2024         if (res == 1 && (flags & VERIFY_ENFORCE_SSA) && pinned)
2025                 compute_doms(irg);
2026
2027         irg_walk_anchors(
2028                 irg,
2029                 pinned && get_irg_dom_state(irg) == dom_consistent
2030                         ? verify_wrap_ssa : verify_wrap,
2031                 NULL,
2032                 &res
2033         );
2034
2035         if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT && ! res) {
2036                 ir_entity *ent = get_irg_entity(irg);
2037
2038                 if (ent)
2039                         fprintf(stderr, "irg_verify: Verifying graph %s failed\n", get_entity_name(ent));
2040                 else
2041                         fprintf(stderr, "irg_verify: Verifying graph %p failed\n", (void *)irg);
2042         }
2043
2044 #else
2045         (void)irg;
2046         (void)flags;
2047 #endif /* DEBUG_libfirm */
2048
2049         return res;
2050 }
2051
2052 typedef struct pass_t {
2053         ir_graph_pass_t pass;
2054         unsigned        flags;
2055 } pass_t;
2056
2057 /**
2058  * Wrapper to irg_verify to be run as an ir_graph pass.
2059  */
2060 static int irg_verify_wrapper(ir_graph *irg, void *context)
2061 {
2062         pass_t *pass = (pass_t*)context;
2063         irg_verify(irg, pass->flags);
2064         /* do NOT rerun the pass if verify is ok :-) */
2065         return 0;
2066 }
2067
2068 /* Creates an ir_graph pass for irg_verify(). */
2069 ir_graph_pass_t *irg_verify_pass(const char *name, unsigned flags)
2070 {
2071         pass_t *pass = XMALLOCZ(pass_t);
2072
2073         def_graph_pass_constructor(
2074                 &pass->pass, name ? name : "irg_verify", irg_verify_wrapper);
2075
2076         /* neither dump for verify */
2077         pass->pass.dump_irg   = (DUMP_ON_IRG_FUNC)ir_prog_no_dump;
2078         pass->pass.verify_irg = (RUN_ON_IRG_FUNC)ir_prog_no_verify;
2079
2080         pass->flags = flags;
2081         return &pass->pass;
2082 }
2083
2084 /* create a verify pass */
2085 int irn_verify_irg_dump(ir_node *n, ir_graph *irg, const char **bad_string)
2086 {
2087         int res;
2088         firm_verification_t old = get_node_verification_mode();
2089
2090         firm_verify_failure_msg = NULL;
2091         do_node_verification(FIRM_VERIFICATION_ERROR_ONLY);
2092         res = irn_verify_irg(n, irg);
2093         if (res && get_irg_dom_state(irg) == dom_consistent &&
2094             get_irg_pinned(irg) == op_pin_state_pinned)
2095                 res = check_dominance_for_node(n);
2096         do_node_verification(old);
2097         *bad_string = firm_verify_failure_msg;
2098
2099         return res;
2100 }
2101
2102 typedef struct verify_bad_env_t {
2103         int flags;
2104         int res;
2105 } verify_bad_env_t;
2106
2107 /**
2108  * Pre-Walker: check Bad predecessors of node.
2109  */
2110 static void check_bads(ir_node *node, void *env)
2111 {
2112         verify_bad_env_t *venv = (verify_bad_env_t*)env;
2113         int i, arity = get_irn_arity(node);
2114         ir_graph *irg = get_irn_irg(node);
2115
2116         if (is_Block(node)) {
2117                 if ((venv->flags & BAD_CF) == 0) {
2118
2119                         /* check for Bad Block predecessor */
2120                         for (i = 0; i < arity; ++i) {
2121                                 ir_node *pred = get_irn_n(node, i);
2122
2123                                 if (is_Bad(pred)) {
2124                                         venv->res |= BAD_CF;
2125
2126                                         if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2127                                                 fprintf(stderr, "irg_verify_bads: Block %ld has Bad predecessor\n", get_irn_node_nr(node));
2128                                         }
2129                                         if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2130                                                 dump_ir_graph(irg, "-assert");
2131                                                 assert(0 && "Bad CF detected");
2132                                         }
2133                                 }
2134                         }
2135                 }
2136         } else {
2137                 if ((venv->flags & BAD_BLOCK) == 0) {
2138
2139                         /* check for Bad Block */
2140                         if (is_Bad(get_nodes_block(node))) {
2141                                 venv->res |= BAD_BLOCK;
2142
2143                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2144                                         fprintf(stderr, "irg_verify_bads: node %ld has Bad Block\n", get_irn_node_nr(node));
2145                                 }
2146                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2147                                         dump_ir_graph(irg, "-assert");
2148                                         assert(0 && "Bad CF detected");
2149                                 }
2150                         }
2151                 }
2152
2153                 if ((venv->flags & TUPLE) == 0) {
2154                         if (is_Tuple(node)) {
2155                                 venv->res |= TUPLE;
2156
2157                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2158                                         fprintf(stderr, "irg_verify_bads: node %ld is a Tuple\n", get_irn_node_nr(node));
2159                                 }
2160                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2161                                         dump_ir_graph(irg, "-assert");
2162                                         assert(0 && "Tuple detected");
2163                                 }
2164                         }
2165                 }
2166
2167                 for (i = 0; i < arity; ++i) {
2168                         ir_node *pred = get_irn_n(node, i);
2169
2170                         if (is_Bad(pred)) {
2171                                 /* check for Phi with Bad inputs */
2172                                 if (is_Phi(node) && !is_Bad(get_nodes_block(node)) && is_Bad(get_irn_n(get_nodes_block(node), i))) {
2173                                         if (venv->flags & BAD_CF)
2174                                                 continue;
2175                                         else {
2176                                                 venv->res |= BAD_CF;
2177
2178                                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2179                                                         fprintf(stderr, "irg_verify_bads: Phi %ld has Bad Input\n", get_irn_node_nr(node));
2180                                                 }
2181                                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2182                                                         dump_ir_graph(irg, "-assert");
2183                                                         assert(0 && "Bad CF detected");
2184                                                 }
2185                                         }
2186                                 }
2187
2188                                 /* Bad node input */
2189                                 if ((venv->flags & BAD_DF) == 0) {
2190                                         venv->res |= BAD_DF;
2191
2192                                         if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2193                                                 fprintf(stderr, "irg_verify_bads: node %ld has Bad Input\n", get_irn_node_nr(node));
2194                                         }
2195                                         if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2196                                                 dump_ir_graph(irg, "-assert");
2197                                                 assert(0 && "Bad NON-CF detected");
2198                                         }
2199                                 }
2200                         }
2201                 }
2202         }
2203 }
2204
2205 /*
2206  * verify occurrence of bad nodes
2207  */
2208 int irg_verify_bads(ir_graph *irg, int flags)
2209 {
2210         verify_bad_env_t env;
2211
2212         env.flags = flags;
2213         env.res   = 0;
2214
2215         irg_walk_graph(irg, check_bads, NULL, &env);
2216
2217         return env.res;
2218 }
2219
2220 /*
2221  * set the default verify operation
2222  */
2223 void firm_set_default_verifier(unsigned code, ir_op_ops *ops)
2224 {
2225 #define CASE(a)                           \
2226    case iro_##a:                          \
2227      ops->verify_node  = verify_node_##a; \
2228      break
2229
2230         switch (code) {
2231         CASE(Proj);
2232         CASE(Block);
2233         CASE(Start);
2234         CASE(Jmp);
2235         CASE(IJmp);
2236         CASE(Cond);
2237         CASE(Return);
2238         CASE(Raise);
2239         CASE(Const);
2240         CASE(SymConst);
2241         CASE(Sel);
2242         CASE(InstOf);
2243         CASE(Call);
2244         CASE(Add);
2245         CASE(Sub);
2246         CASE(Minus);
2247         CASE(Mul);
2248         CASE(Mulh);
2249         CASE(Div);
2250         CASE(Mod);
2251         CASE(And);
2252         CASE(Or);
2253         CASE(Eor);
2254         CASE(Not);
2255         CASE(Cmp);
2256         CASE(Shl);
2257         CASE(Shr);
2258         CASE(Shrs);
2259         CASE(Rotl);
2260         CASE(Conv);
2261         CASE(Cast);
2262         CASE(Phi);
2263         CASE(Load);
2264         CASE(Store);
2265         CASE(Alloc);
2266         CASE(Free);
2267         CASE(Sync);
2268         CASE(Confirm);
2269         CASE(Mux);
2270         CASE(CopyB);
2271         CASE(Bound);
2272         default:
2273                 /* leave NULL */;
2274         }
2275 #undef CASE
2276
2277 #define CASE(a)                          \
2278    case iro_##a:                         \
2279      ops->verify_proj_node  = verify_node_Proj_##a; \
2280      break
2281
2282         switch (code) {
2283         CASE(Start);
2284         CASE(Cond);
2285         CASE(Raise);
2286         CASE(InstOf);
2287         CASE(Call);
2288         CASE(Div);
2289         CASE(Mod);
2290         CASE(Load);
2291         CASE(Store);
2292         CASE(Alloc);
2293         CASE(Proj);
2294         CASE(Tuple);
2295         CASE(CopyB);
2296         CASE(Bound);
2297         default:
2298                 /* leave NULL */;
2299         }
2300 #undef CASE
2301 }