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

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