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