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

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