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