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

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