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