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