Remove extra dash from assert graph filenames.
[libfirm] / 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(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(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(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(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(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(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(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(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(ir_graph *irg, 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(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(ir_graph *irg, ir_node *n, ir_type *mt, int i)
258 {
259         ir_entity *ent = get_irg_entity(irg);
260
261         show_entity_failure(n);
262         fprintf(stderr, "  Return node %ld in entity \"%s\" mode %s different from type mode %s\n",
263                 get_irn_node_nr(n), get_entity_name(ent),
264                 get_mode_name_ex(get_irn_mode(get_Return_res(n, i))),
265                 get_mode_name_ex(get_type_mode(get_method_res_type(mt, i)))
266         );
267 }
268
269 /**
270  * Show return number of results
271  */
272 static void show_return_nres(ir_graph *irg, ir_node *n, ir_type *mt)
273 {
274         ir_entity *ent = get_irg_entity(irg);
275
276         show_entity_failure(n);
277         fprintf(stderr, "  Return node %ld in entity \"%s\" has %lu results different from type %lu\n",
278                 get_irn_node_nr(n), get_entity_name(ent),
279                 (unsigned long) get_Return_n_ress(n),
280                 (unsigned long) get_method_n_ress(mt));
281 }
282
283 /**
284  * Show Phi input
285  */
286 static void show_phi_failure(ir_node *phi, ir_node *pred, int pos)
287 {
288         (void) pos;
289         show_entity_failure(phi);
290         fprintf(stderr, "  Phi node %ld has mode %s different from predeccessor node %ld mode %s\n",
291                 get_irn_node_nr(phi), get_mode_name_ex(get_irn_mode(phi)),
292                 get_irn_node_nr(pred), get_mode_name_ex(get_irn_mode(pred)));
293 }
294
295 /**
296  * Show Phi inputs
297  */
298 static void show_phi_inputs(ir_node *phi, ir_node *block)
299 {
300         show_entity_failure(phi);
301         fprintf(stderr, "  Phi node %ld has %d inputs, its Block %ld has %d\n",
302                 get_irn_node_nr(phi),   get_irn_arity(phi),
303                 get_irn_node_nr(block), get_irn_arity(block));
304 }
305
306 #endif /* #ifndef NDEBUG */
307
308 /**
309  * If the address is Sel or SymConst, return the entity.
310  *
311  * @param ptr  the node representing the address
312  */
313 static ir_entity *get_ptr_entity(ir_node *ptr)
314 {
315         if (is_Sel(ptr)) {
316                 return get_Sel_entity(ptr);
317         } else if (is_SymConst_addr_ent(ptr)) {
318                 return get_SymConst_entity(ptr);
319         }
320         return NULL;
321 }
322
323 /**
324  * verify a Proj(Start) node
325  */
326 static int verify_node_Proj_Start(ir_node *n, ir_node *p)
327 {
328         ir_mode *mode = get_irn_mode(p);
329         long proj     = get_Proj_proj(p);
330         (void) n;
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(ir_node *pred, ir_node *p)
349 {
350         ir_mode *mode = get_irn_mode(p);
351         long proj     = get_Proj_proj(p);
352
353         ASSERT_AND_RET_DBG(
354                 (
355                         (proj >= 0 && mode == mode_X && get_irn_mode(get_Cond_selector(pred)) == mode_b) ||   /* compare */
356                         (mode == mode_X && mode_is_int(get_irn_mode(get_Cond_selector(pred))))                /* switch */
357                 ),
358                 "wrong Proj from Cond", 0,
359                 show_proj_failure(p);
360         );
361         return 1;
362 }
363
364 /**
365  * verify a Proj(Raise) node
366  */
367 static int verify_node_Proj_Raise(ir_node *n, ir_node *p)
368 {
369         ir_mode *mode = get_irn_mode(p);
370         long proj     = get_Proj_proj(p);
371         (void) n;
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(ir_node *n, ir_node *p)
385 {
386         ir_mode *mode = get_irn_mode(p);
387         long proj     = get_Proj_proj(p);
388         (void) n;
389
390         ASSERT_AND_RET_DBG(
391                 (
392                         (proj == pn_InstOf_M         && mode == mode_M) ||
393                         (proj == pn_InstOf_X_regular && mode == mode_X) ||
394                         (proj == pn_InstOf_X_except  && mode == mode_X) ||
395                         (proj == pn_InstOf_res       && mode_is_reference(mode))
396                 ),
397                 "wrong Proj from InstOf", 0,
398                 show_proj_failure(p);
399         );
400         return 1;
401 }
402
403 /**
404  * verify a Proj(Call) node
405  */
406 static int verify_node_Proj_Call(ir_node *n, ir_node *p)
407 {
408         ir_mode *mode = get_irn_mode(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(ir_node *n, ir_node *p)
437 {
438         ir_mode *mode = get_irn_mode(p);
439         long proj     = get_Proj_proj(p);
440
441         ASSERT_AND_RET_DBG(
442                 (
443                         (proj == pn_Div_M         && mode == mode_M) ||
444                         (proj == pn_Div_X_regular && mode == mode_X) ||
445                         (proj == pn_Div_X_except  && mode == mode_X) ||
446                         (proj == pn_Div_res       && mode_is_data(mode) && mode == get_Div_resmode(n))
447                 ),
448                 "wrong Proj from Div", 0,
449                 show_proj_failure(p);
450         );
451         if (proj == pn_Div_X_regular)
452                 ASSERT_AND_RET(
453                         get_irn_pinned(n) == op_pin_state_pinned,
454                         "Regular Proj from unpinned Div", 0);
455         else if (proj == pn_Div_X_except)
456                 ASSERT_AND_RET(
457                         get_irn_pinned(n) == op_pin_state_pinned,
458                         "Exception Proj from unpinned Div", 0);
459         else if (proj == pn_Div_M)
460                 ASSERT_AND_RET(
461                         get_irn_pinned(n) == op_pin_state_pinned,
462                         "Memory Proj from unpinned Div", 0);
463         return 1;
464 }
465
466 /**
467  * verify a Proj(Mod) node
468  */
469 static int verify_node_Proj_Mod(ir_node *n, ir_node *p)
470 {
471         ir_mode *mode = get_irn_mode(p);
472         long proj     = get_Proj_proj(p);
473
474         ASSERT_AND_RET_DBG(
475                 (
476                         (proj == pn_Mod_M         && mode == mode_M) ||
477                         (proj == pn_Mod_X_regular && mode == mode_X) ||
478                         (proj == pn_Mod_X_except  && mode == mode_X) ||
479                         (proj == pn_Mod_res       && mode == get_Mod_resmode(n))
480                 ),
481                 "wrong Proj from Mod", 0,
482                 show_proj_failure(p);
483         );
484         if (proj == pn_Mod_X_regular)
485                 ASSERT_AND_RET(
486                         get_irn_pinned(n) == op_pin_state_pinned,
487                         "Regular Proj from unpinned Mod", 0);
488         else if (proj == pn_Mod_X_except)
489                 ASSERT_AND_RET(
490                         get_irn_pinned(n) == op_pin_state_pinned,
491                         "Exception Proj from unpinned Mod", 0);
492         else if (proj == pn_Mod_M)
493                 ASSERT_AND_RET(
494                         get_irn_pinned(n) == op_pin_state_pinned,
495                         "Memory Proj from unpinned Div", 0);
496         return 1;
497 }
498
499 /**
500  * verify a Proj(Load) node
501  */
502 static int verify_node_Proj_Load(ir_node *n, ir_node *p)
503 {
504         ir_mode *mode = get_irn_mode(p);
505         long proj     = get_Proj_proj(p);
506
507         if (proj == pn_Load_res) {
508                 ir_node   *ptr = get_Load_ptr(n);
509                 ir_entity *ent = get_ptr_entity(ptr);
510                 ir_graph  *irg = get_irn_irg(n);
511
512                 if (verify_entities && ent && get_irg_phase_state(irg) == phase_high) {
513                         /* do NOT check this for lowered phases, see comment on Store */
514                         ASSERT_AND_RET_DBG(
515                                 (mode == get_type_mode(get_entity_type(ent))),
516                                 "wrong data Proj from Load, entity type_mode failed", 0,
517                                 show_proj_failure_ent(p, ent);
518                         );
519                 }
520                 else {
521                         ASSERT_AND_RET_DBG(
522                                 mode_is_data(mode) && mode == get_Load_mode(n),
523                                 "wrong data Proj from Load", 0,
524                                 show_proj_failure(p);
525                         );
526                 }
527         }
528         else {
529                 ASSERT_AND_RET_DBG(
530                         (
531                                 (proj == pn_Load_M         && mode == mode_M) ||
532                                 (proj == pn_Load_X_regular && mode == mode_X) ||
533                                 (proj == pn_Load_X_except  && mode == mode_X)
534                         ),
535                         "wrong Proj from Load", 0,
536                         show_proj_failure(p);
537                 );
538         }
539         if (proj == pn_Load_X_regular) {
540                 ASSERT_AND_RET(
541                         get_irn_pinned(n) == op_pin_state_pinned,
542                         "Regular Proj from unpinned Load", 0);
543         } else if (proj == pn_Load_X_except) {
544                 ASSERT_AND_RET(
545                         get_irn_pinned(n) == op_pin_state_pinned,
546                         "Exception Proj from unpinned Load", 0);
547         }
548         return 1;
549 }
550
551 /**
552  * verify a Proj(Store) node
553  */
554 static int verify_node_Proj_Store(ir_node *n, ir_node *p)
555 {
556         ir_mode *mode = get_irn_mode(p);
557         long proj     = get_Proj_proj(p);
558
559         ASSERT_AND_RET_DBG(
560                 (
561                         (proj == pn_Store_M         && mode == mode_M) ||
562                         (proj == pn_Store_X_regular && mode == mode_X) ||
563                         (proj == pn_Store_X_except  && mode == mode_X)
564                 ),
565                 "wrong Proj from Store", 0,
566                 show_proj_failure(p);
567         );
568         if (proj == pn_Store_X_regular) {
569                 ASSERT_AND_RET(
570                         get_irn_pinned(n) == op_pin_state_pinned,
571                         "Regular Proj from unpinned Store", 0);
572         } else if (proj == pn_Store_X_except) {
573                 ASSERT_AND_RET(
574                         get_irn_pinned(n) == op_pin_state_pinned,
575                         "Exception Proj from unpinned Store", 0);
576         }
577         return 1;
578 }
579
580 /**
581  * verify a Proj(Alloc) node
582  */
583 static int verify_node_Proj_Alloc(ir_node *n, ir_node *p)
584 {
585         ir_mode *mode = get_irn_mode(p);
586         long proj     = get_Proj_proj(p);
587         (void) n;
588
589         ASSERT_AND_RET_DBG(
590                 (
591                         (proj == pn_Alloc_M         && mode == mode_M) ||
592                         (proj == pn_Alloc_X_regular && mode == mode_X) ||
593                         (proj == pn_Alloc_X_except  && mode == mode_X) ||
594                         (proj == pn_Alloc_res       && mode_is_reference(mode))
595                 ),
596                 "wrong Proj from Alloc", 0,
597                 show_proj_failure(p);
598         );
599         return 1;
600 }
601
602 /**
603  * verify a Proj(Proj) node
604  */
605 static int verify_node_Proj_Proj(ir_node *pred, ir_node *p)
606 {
607         ir_mode *mode = get_irn_mode(p);
608         long proj     = get_Proj_proj(p);
609         long nr       = get_Proj_proj(pred);
610         ir_type *mt; /* A method type */
611
612         pred = skip_Id(get_Proj_pred(pred));
613         ASSERT_AND_RET((get_irn_mode(pred) == mode_T), "Proj from something not a tuple", 0);
614
615         switch (get_irn_opcode(pred)) {
616         case iro_Start:
617                 mt = get_entity_type(get_irg_entity(get_irn_irg(pred)));
618
619                 if (nr == pn_Start_T_args) {
620                         ASSERT_AND_RET(
621                                 (proj >= 0 && mode_is_datab(mode)),
622                                 "wrong Proj from Proj from Start", 0);
623                         ASSERT_AND_RET(
624                                 (proj < (int)get_method_n_params(mt)),
625                                 "More Projs for args than args in type", 0
626                                 );
627                         if ((mode_is_reference(mode)) && is_compound_type(get_method_param_type(mt, proj)))
628                                 /* value argument */ break;
629
630                         if (get_irg_phase_state(get_irn_irg(pred)) != phase_backend) {
631                                 ASSERT_AND_RET_DBG(
632                                                 (mode == get_type_mode(get_method_param_type(mt, proj))),
633                                                 "Mode of Proj from Start doesn't match mode of param type.", 0,
634                                                 show_proj_mode_failure(p, get_method_param_type(mt, proj));
635                                                 );
636                         }
637                 }
638                 break;
639
640         case iro_Call:
641                 {
642                         ASSERT_AND_RET(
643                                 (proj >= 0 && mode_is_datab(mode)),
644                                 "wrong Proj from Proj from Call", 0);
645                         mt = get_Call_type(pred);
646                         ASSERT_AND_RET(mt == get_unknown_type() || is_Method_type(mt),
647                                         "wrong call type on call", 0);
648                         ASSERT_AND_RET(
649                                 (proj < (int)get_method_n_ress(mt)),
650                                 "More Projs for results than results in type.", 0);
651                         if ((mode_is_reference(mode)) && is_compound_type(get_method_res_type(mt, proj)))
652                                 /* value result */ break;
653
654                                 ASSERT_AND_RET(
655                                 (mode == get_type_mode(get_method_res_type(mt, proj))),
656                                 "Mode of Proj from Call doesn't match mode of result type.", 0);
657                 }
658                 break;
659
660         case iro_Tuple:
661                 /* We don't test */
662                 break;
663
664         default:
665                 /* ASSERT_AND_RET(0, "Unknown opcode", 0); */
666                 break;
667         }
668         return 1;
669 }
670
671 /**
672  * verify a Proj(Tuple) node
673  */
674 static int verify_node_Proj_Tuple(ir_node *n, ir_node *p)
675 {
676         (void) n;
677         (void) p;
678         /* We don't test */
679         return 1;
680 }
681
682 /**
683  * verify a Proj(CopyB) node
684  */
685 static int verify_node_Proj_CopyB(ir_node *n, ir_node *p)
686 {
687         ir_mode *mode = get_irn_mode(p);
688         long proj     = get_Proj_proj(p);
689
690         ASSERT_AND_RET_DBG(
691                 (
692                         (proj == pn_CopyB_M         && mode == mode_M) ||
693                         (proj == pn_CopyB_X_regular && mode == mode_X) ||
694                         (proj == pn_CopyB_X_except  && mode == mode_X)
695                 ),
696                 "wrong Proj from CopyB", 0,
697                 show_proj_failure(p);
698         );
699         if (proj == pn_CopyB_X_regular)
700                 ASSERT_AND_RET(
701                         get_irn_pinned(n) == op_pin_state_pinned,
702                         "Regular Proj from unpinned CopyB", 0);
703         else if (proj == pn_CopyB_X_except)
704                 ASSERT_AND_RET(
705                         get_irn_pinned(n) == op_pin_state_pinned,
706                         "Exception Proj from unpinned CopyB", 0);
707         return 1;
708 }
709
710 /**
711  * verify a Proj(Bound) node
712  */
713 static int verify_node_Proj_Bound(ir_node *n, ir_node *p)
714 {
715         ir_mode *mode = get_irn_mode(p);
716         long proj     = get_Proj_proj(p);
717
718         ASSERT_AND_RET_DBG(
719                 (
720                         (proj == pn_Bound_M         && mode == mode_M) ||
721                         (proj == pn_Bound_X_regular && mode == mode_X) ||
722                         (proj == pn_Bound_X_except  && mode == mode_X) ||
723                         (proj == pn_Bound_res       && mode == get_irn_mode(get_Bound_index(n)))
724                 ),
725                 "wrong Proj from Bound", 0,
726                 show_proj_failure(p);
727         );
728         return 1;
729 }
730
731 /**
732  * verify a Proj node
733  */
734 static int verify_node_Proj(ir_node *p, ir_graph *irg)
735 {
736         ir_node *pred;
737         ir_op *op;
738
739         pred = skip_Id(get_Proj_pred(p));
740         ASSERT_AND_RET(get_irn_mode(pred) == mode_T, "mode of a 'projed' node is not Tuple", 0);
741         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);
742
743         op = get_irn_op(pred);
744
745         if (op->ops.verify_proj_node)
746                 return op->ops.verify_proj_node(pred, p);
747
748         /* all went ok */
749         return 1;
750 }
751
752 /**
753  * verify a Block node
754  */
755 static int verify_node_Block(ir_node *n, ir_graph *irg)
756 {
757         int i;
758
759         for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
760                 ir_node *pred = get_Block_cfgpred(n, i);
761                 ASSERT_AND_RET(get_irn_mode(pred) == mode_X,
762                         "Block node must have a mode_X predecessor", 0);
763                 ASSERT_AND_RET(is_cfop(skip_Proj(skip_Tuple(pred))), "Block predecessor must be a cfop", 0);
764         }
765
766         if (n == get_irg_start_block(irg)) {
767                 ASSERT_AND_RET(get_Block_n_cfgpreds(n) == 0, "Start Block node", 0);
768         }
769
770         if (n == get_irg_end_block(irg) && get_irg_phase_state(irg) != phase_backend) {
771                 /* End block may only have Return, Raise or fragile ops as preds. */
772                 for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
773                         ir_node *pred =  skip_Proj(get_Block_cfgpred(n, i));
774                         if (is_Proj(pred) || is_Tuple(pred))
775                                 break;   /*  We can not test properly.  How many tuples are there? */
776                         ASSERT_AND_RET(
777                                 (
778                                         is_Return(pred) ||
779                                         is_Bad(pred)    ||
780                                         is_Raise(pred)  ||
781                                         is_fragile_op(pred)
782                                 ),
783                                 "End Block node", 0);
784                 }
785         }
786         /*  irg attr must == graph we are in. */
787         ASSERT_AND_RET(((get_irn_irg(n) && get_irn_irg(n) == irg)), "Block node has wrong irg attribute", 0);
788         return 1;
789 }
790
791 /**
792  * verify a Start node
793  */
794 static int verify_node_Start(ir_node *n, ir_graph *irg)
795 {
796         ir_mode *mymode = get_irn_mode(n);
797         (void) irg;
798
799         ASSERT_AND_RET(
800                 /* Start: BB --> X x M x ref x data1 x ... x datan x ref */
801                 mymode == mode_T, "Start node", 0
802                 );
803         return 1;
804 }
805
806 /**
807  * verify a Jmp node
808  */
809 static int verify_node_Jmp(ir_node *n, ir_graph *irg)
810 {
811         ir_mode *mymode = get_irn_mode(n);
812         (void) irg;
813
814         ASSERT_AND_RET(
815                 /* Jmp: BB --> X */
816                 mymode == mode_X, "Jmp node", 0
817         );
818         return 1;
819 }
820
821 /**
822  * verify an IJmp node
823  */
824 static int verify_node_IJmp(ir_node *n, ir_graph *irg)
825 {
826         ir_mode *mymode  = get_irn_mode(n);
827         ir_mode *op1mode = get_irn_mode(get_IJmp_target(n));
828         (void) irg;
829
830         ASSERT_AND_RET(
831                 /* IJmp: BB x ref --> X */
832                 mymode == mode_X && mode_is_reference(op1mode), "IJmp node", 0
833         );
834         return 1;
835 }
836
837 /**
838  * verify a Cond node
839  */
840 static int verify_node_Cond(ir_node *n, ir_graph *irg)
841 {
842         ir_mode *mymode  = get_irn_mode(n);
843         ir_mode *op1mode = get_irn_mode(get_Cond_selector(n));
844         (void) irg;
845
846         ASSERT_AND_RET(
847                 /* Cond: BB x b --> X x X */
848                 (op1mode == mode_b ||
849                 /* Cond: BB x int --> X^n */
850                 mode_is_int(op1mode) ),  "Cond node", 0
851                 );
852         ASSERT_AND_RET(mymode == mode_T, "Cond mode is not a tuple", 0);
853
854         return 1;
855 }
856
857 /**
858  * verify a Return node
859  */
860 static int verify_node_Return(ir_node *n, ir_graph *irg)
861 {
862         int i;
863         ir_mode *mymode   = get_irn_mode(n);
864         ir_mode *mem_mode = get_irn_mode(get_Return_mem(n));
865         ir_type *mt;
866
867         /* Return: BB x M x data1 x ... x datan --> X */
868
869         ASSERT_AND_RET( mem_mode == mode_M, "Return node", 0 );  /* operand M */
870
871         for (i = get_Return_n_ress(n) - 1; i >= 0; --i) {
872                 ASSERT_AND_RET( mode_is_datab(get_irn_mode(get_Return_res(n, i))), "Return node", 0 );  /* operand datai */
873         }
874         ASSERT_AND_RET( mymode == mode_X, "Result X", 0 );   /* result X */
875         /* Compare returned results with result types of method type */
876         mt = get_entity_type(get_irg_entity(irg));
877         ASSERT_AND_RET_DBG(get_Return_n_ress(n) == get_method_n_ress(mt),
878                 "Number of results for Return doesn't match number of results in type.", 0,
879                 show_return_nres(irg, n, mt););
880         for (i = get_Return_n_ress(n) - 1; i >= 0; --i) {
881                 ir_type *res_type = get_method_res_type(mt, i);
882
883                 if (get_irg_phase_state(irg) != phase_backend) {
884                         if (is_atomic_type(res_type)) {
885                                 ASSERT_AND_RET_DBG(
886                                         get_irn_mode(get_Return_res(n, i)) == get_type_mode(res_type),
887                                         "Mode of result for Return doesn't match mode of result type.", 0,
888                                         show_return_modes(irg, n, mt, i);
889                                 );
890                         } else {
891                                 ASSERT_AND_RET_DBG(
892                                         mode_is_reference(get_irn_mode(get_Return_res(n, i))),
893                                         "Mode of result for Return doesn't match mode of result type.", 0,
894                                         show_return_modes(irg, n, mt, i);
895                                 );
896                         }
897                 }
898         }
899         return 1;
900 }
901
902 /**
903  * verify a Raise node
904  */
905 static int verify_node_Raise(ir_node *n, ir_graph *irg)
906 {
907         ir_mode *mymode  = get_irn_mode(n);
908         ir_mode *op1mode = get_irn_mode(get_Raise_mem(n));
909         ir_mode *op2mode = get_irn_mode(get_Raise_exo_ptr(n));
910         (void) irg;
911
912         ASSERT_AND_RET(
913                 /* Sel: BB x M x ref --> X x M */
914                 op1mode == mode_M && mode_is_reference(op2mode) &&
915                 mymode == mode_T, "Raise node", 0
916         );
917         return 1;
918 }
919
920 /**
921  * verify a Const node
922  */
923 static int verify_node_Const(ir_node *n, ir_graph *irg)
924 {
925         ir_mode *mymode = get_irn_mode(n);
926         (void) irg;
927
928         ASSERT_AND_RET(
929                 /* Const: BB --> data */
930                 (mode_is_data(mymode) ||
931                 mymode == mode_b)      /* we want boolean constants for static evaluation */
932                 ,"Const node", 0       /* of Cmp. */
933         );
934         ASSERT_AND_RET(
935                 /* the modes of the constant and teh tarval must match */
936                 mymode == get_tarval_mode(get_Const_tarval(n)),
937                 "Const node, tarval and node mode mismatch", 0
938         );
939         return 1;
940 }
941
942 /**
943  * verify a SymConst node
944  */
945 static int verify_node_SymConst(ir_node *n, ir_graph *irg)
946 {
947         ir_mode *mymode = get_irn_mode(n);
948         (void) irg;
949
950         ASSERT_AND_RET(
951                 /* SymConst: BB --> int*/
952                 (mode_is_int(mymode) ||
953                 /* SymConst: BB --> ref */
954                 mode_is_reference(mymode))
955                 ,"SymConst node", 0);
956         return 1;
957 }
958
959 /**
960  * verify a Sel node
961  */
962 static int verify_node_Sel(ir_node *n, ir_graph *irg)
963 {
964         int i;
965         ir_mode *mymode  = get_irn_mode(n);
966         ir_mode *op1mode = get_irn_mode(get_Sel_mem(n));
967         ir_mode *op2mode = get_irn_mode(get_Sel_ptr(n));
968         ir_entity *ent;
969         (void) irg;
970
971         ASSERT_AND_RET_DBG(
972                 /* Sel: BB x M x ref x int^n --> ref */
973                 (op1mode == mode_M && op2mode == mymode && mode_is_reference(mymode)),
974                 "Sel node", 0, show_node_failure(n)
975         );
976
977         for (i = get_Sel_n_indexs(n) - 1; i >= 0; --i) {
978                 ASSERT_AND_RET_DBG(mode_is_int(get_irn_mode(get_Sel_index(n, i))), "Sel node", 0, show_node_failure(n));
979         }
980         ent = get_Sel_entity(n);
981         ASSERT_AND_RET_DBG(ent, "Sel node with empty entity", 0, show_node_failure(n));
982         return 1;
983 }
984
985 /**
986  * verify an InstOf node
987  */
988 static int verify_node_InstOf(ir_node *n, ir_graph *irg)
989 {
990         ir_mode *mymode  = get_irn_mode(n);
991         ir_mode *op1mode = get_irn_mode(get_InstOf_obj(n));
992         (void) irg;
993
994         ASSERT_AND_RET(mode_T == mymode, "mode of Instof is not a tuple", 0);
995         ASSERT_AND_RET(mode_is_data(op1mode), "Instof not on data", 0);
996         return 1;
997 }
998
999 /**
1000  * Check if the pinned state is right.
1001  */
1002 static int verify_right_pinned(ir_node *n)
1003 {
1004         ir_node *mem;
1005
1006         if (get_irn_pinned(n) == op_pin_state_pinned)
1007                 return 1;
1008         mem = get_Call_mem(n);
1009
1010         /* if it's not pinned, its memory predecessor must be NoMem or Pin */
1011         if (is_NoMem(mem) || is_Pin(mem))
1012                 return 1;
1013         return 0;
1014 }
1015
1016 /**
1017  * verify a Call node
1018  */
1019 static int verify_node_Call(ir_node *n, ir_graph *irg)
1020 {
1021         ir_mode *mymode  = get_irn_mode(n);
1022         ir_mode *op1mode = get_irn_mode(get_Call_mem(n));
1023         ir_mode *op2mode = get_irn_mode(get_Call_ptr(n));
1024         ir_type *mt;
1025         size_t i;
1026         size_t n_params;
1027         (void) irg;
1028
1029         /* Call: BB x M x ref x data1 x ... x datan
1030         --> M x datan+1 x ... x data n+m */
1031         ASSERT_AND_RET( op1mode == mode_M && mode_is_reference(op2mode), "Call node", 0 );  /* operand M x ref */
1032
1033         /* NoMem nodes are only allowed as memory input if the Call is NOT pinned */
1034         ASSERT_AND_RET(verify_right_pinned(n),"Call node with wrong memory input", 0 );
1035
1036         mt = get_Call_type(n);
1037         if (get_unknown_type() == mt) {
1038                 return 1;
1039         }
1040
1041         n_params = get_Call_n_params(n);
1042         for (i = 0; i < n_params; ++i) {
1043                 ASSERT_AND_RET( mode_is_datab(get_irn_mode(get_Call_param(n, i))), "Call node", 0 );  /* operand datai */
1044         }
1045
1046         ASSERT_AND_RET( mymode == mode_T, "Call result not a tuple", 0 );   /* result T */
1047         /* Compare arguments of node with those of type */
1048
1049         if (get_method_variadicity(mt) == variadicity_variadic) {
1050                 ASSERT_AND_RET_DBG(
1051                         get_Call_n_params(n) >= get_method_n_params(mt),
1052                         "Number of args for Call doesn't match number of args in variadic type.",
1053                         0,
1054                         ir_fprintf(stderr, "Call %+F has %d params, type %d\n",
1055                         n, get_Call_n_params(n), get_method_n_params(mt));
1056                 );
1057         } else {
1058                 ASSERT_AND_RET_DBG(
1059                         get_Call_n_params(n) == get_method_n_params(mt),
1060                         "Number of args for Call doesn't match number of args in non variadic type.",
1061                         0,
1062                         ir_fprintf(stderr, "Call %+F has %d params, type %d\n",
1063                         n, get_Call_n_params(n), get_method_n_params(mt));
1064                 );
1065         }
1066
1067         for (i = 0; i < get_method_n_params(mt); i++) {
1068                 ir_type *t = get_method_param_type(mt, i);
1069
1070                 if (get_irg_phase_state(irg) != phase_backend) {
1071                         if (is_atomic_type(t)) {
1072                                 ASSERT_AND_RET_DBG(
1073                                         get_irn_mode(get_Call_param(n, i)) == get_type_mode(t),
1074                                         "Mode of arg for Call doesn't match mode of arg type.", 0,
1075                                         show_call_param(n, mt);
1076                                 );
1077                         } else {
1078                                 /* call with a compound type, mode must be reference */
1079                                 ASSERT_AND_RET_DBG(
1080                                         mode_is_reference(get_irn_mode(get_Call_param(n, i))),
1081                                         "Mode of arg for Call doesn't match mode of arg type.", 0,
1082                                         show_call_param(n, mt);
1083                                 );
1084                         }
1085                 }
1086         }
1087
1088 #if 0
1089         if (Call_has_callees(n)) {
1090                 for (i = 0; i < get_Call_n_callees(n); i++) {
1091                         ASSERT_AND_RET(is_entity(get_Call_callee(n, i)), "callee array must contain entities.", 0);
1092                 }
1093         }
1094 #endif
1095         return 1;
1096 }
1097
1098 /**
1099  * verify an Add node
1100  */
1101 static int verify_node_Add(ir_node *n, ir_graph *irg)
1102 {
1103         ir_mode *mymode  = get_irn_mode(n);
1104         ir_mode *op1mode = get_irn_mode(get_Add_left(n));
1105         ir_mode *op2mode = get_irn_mode(get_Add_right(n));
1106         (void) irg;
1107
1108         ASSERT_AND_RET_DBG(
1109                 (
1110                         /* common Add: BB x numP x numP --> numP */
1111                         (op1mode == mymode && op2mode == op1mode && mode_is_data(mymode)) ||
1112                         /* Pointer Add: BB x ref x int --> ref */
1113                         (mode_is_reference(op1mode) && mode_is_int(op2mode) && op1mode == mymode) ||
1114                         /* Pointer Add: BB x int x ref --> ref */
1115                         (mode_is_int(op1mode) && op2mode == mymode && mode_is_reference(mymode))
1116                 ),
1117                 "Add node", 0,
1118                 show_binop_failure(n, "/* common Add: BB x numP x numP --> numP */ |\n"
1119                         "/* Pointer Add: BB x ref x int --> ref */   |\n"
1120                         "/* Pointer Add: BB x int x ref --> ref */");
1121         );
1122         return 1;
1123 }
1124
1125 /**
1126  * verify a Sub node
1127  */
1128 static int verify_node_Sub(ir_node *n, ir_graph *irg)
1129 {
1130         ir_mode *mymode  = get_irn_mode(n);
1131         ir_mode *op1mode = get_irn_mode(get_Sub_left(n));
1132         ir_mode *op2mode = get_irn_mode(get_Sub_right(n));
1133         (void) irg;
1134
1135         ASSERT_AND_RET_DBG(
1136                 (
1137                         /* common Sub: BB x numP x numP --> numP */
1138                         (mymode ==op1mode && mymode == op2mode && mode_is_data(op1mode)) ||
1139                         /* Pointer Sub: BB x ref x int --> ref */
1140                         (op1mode == mymode && mode_is_int(op2mode) && mode_is_reference(mymode)) ||
1141                         /* Pointer Sub: BB x ref x ref --> int */
1142                         (op1mode == op2mode && mode_is_reference(op2mode) && mode_is_int(mymode))
1143                 ),
1144                 "Sub node", 0,
1145                 show_binop_failure(n, "/* common Sub: BB x numP x numP --> numP */ |\n"
1146                         "/* Pointer Sub: BB x ref x int --> ref */   |\n"
1147                         "/* Pointer Sub: BB x ref x ref --> int */" );
1148                 );
1149         return 1;
1150 }
1151
1152 /**
1153  * verify a Minus node
1154  */
1155 static int verify_node_Minus(ir_node *n, ir_graph *irg)
1156 {
1157         ir_mode *mymode  = get_irn_mode(n);
1158         ir_mode *op1mode = get_irn_mode(get_Minus_op(n));
1159         (void) irg;
1160
1161         ASSERT_AND_RET_DBG(
1162                 /* Minus: BB x num --> num */
1163                 op1mode == mymode && mode_is_num(op1mode), "Minus node", 0,
1164                 show_unop_failure(n , "/* Minus: BB x num --> num */");
1165         );
1166         return 1;
1167 }
1168
1169 /**
1170  * verify a Mul node
1171  */
1172 static int verify_node_Mul(ir_node *n, ir_graph *irg)
1173 {
1174         ir_mode *mymode  = get_irn_mode(n);
1175         ir_mode *op1mode = get_irn_mode(get_Mul_left(n));
1176         ir_mode *op2mode = get_irn_mode(get_Mul_right(n));
1177         (void) irg;
1178
1179         ASSERT_AND_RET_DBG(
1180                 (
1181                         /* Mul: BB x int_n x int_n --> int_n|int_2n */
1182                         (mode_is_int(op1mode)   && op2mode == op1mode && mode_is_int(mymode) &&
1183                          (op1mode == mymode || get_mode_size_bits(op1mode) * 2 == get_mode_size_bits(mymode))) ||
1184                         /* Mul: BB x float x float --> float */
1185                         (mode_is_float(op1mode) && op2mode == op1mode && mymode == op1mode)
1186                 ),
1187                 "Mul node",0,
1188                 show_binop_failure(n, "/* Mul: BB x int_n x int_n --> int_n|int_2n */ |\n"
1189                 "/* Mul: BB x float x float --> float */");
1190         );
1191         return 1;
1192 }
1193
1194 /**
1195  * verify a Mulh node
1196  */
1197 static int verify_node_Mulh(ir_node *n, ir_graph *irg)
1198 {
1199         ir_mode *mymode  = get_irn_mode(n);
1200         ir_mode *op1mode = get_irn_mode(get_Mulh_left(n));
1201         ir_mode *op2mode = get_irn_mode(get_Mulh_right(n));
1202         (void) irg;
1203
1204         ASSERT_AND_RET_DBG(
1205                 (
1206                         /* Mulh: BB x int x int --> int */
1207                         (mode_is_int(op1mode) && op2mode == op1mode && op1mode == mymode)
1208                 ),
1209                 "Mulh node",0,
1210                 show_binop_failure(n, "/* Mulh: BB x int x int --> int */");
1211         );
1212         return 1;
1213 }
1214
1215 /**
1216  * verify a Div node
1217  */
1218 static int verify_node_Div(ir_node *n, ir_graph *irg)
1219 {
1220         ir_mode *mymode  = get_irn_mode(n);
1221         ir_mode *op1mode = get_irn_mode(get_Div_mem(n));
1222         ir_mode *op2mode = get_irn_mode(get_Div_left(n));
1223         ir_mode *op3mode = get_irn_mode(get_Div_right(n));
1224         (void) irg;
1225
1226         ASSERT_AND_RET(
1227                 /* Div: BB x M x data x data --> M x X x data */
1228                 op1mode == mode_M &&
1229                 op2mode == op3mode &&
1230                 mode_is_data(op2mode) &&
1231                 mymode == mode_T,
1232                 "Div node", 0
1233                 );
1234         return 1;
1235 }
1236
1237 /**
1238  * verify a Mod node
1239  */
1240 static int verify_node_Mod(ir_node *n, ir_graph *irg)
1241 {
1242         ir_mode *mymode  = get_irn_mode(n);
1243         ir_mode *op1mode = get_irn_mode(get_Mod_mem(n));
1244         ir_mode *op2mode = get_irn_mode(get_Mod_left(n));
1245         ir_mode *op3mode = get_irn_mode(get_Mod_right(n));
1246         (void) irg;
1247
1248         ASSERT_AND_RET(
1249                 /* Mod: BB x M x int x int --> M x X x int */
1250                 op1mode == mode_M &&
1251                 op2mode == op3mode &&
1252                 mode_is_int(op2mode) &&
1253                 mymode == mode_T,
1254                 "Mod node", 0
1255                 );
1256         return 1;
1257 }
1258
1259 /**
1260  * verify a logical And, Or, Eor node
1261  */
1262 static int verify_node_Logic(ir_node *n, ir_graph *irg)
1263 {
1264         ir_mode *mymode  = get_irn_mode(n);
1265         ir_mode *op1mode = get_irn_mode(get_binop_left(n));
1266         ir_mode *op2mode = get_irn_mode(get_binop_right(n));
1267         (void) irg;
1268
1269         ASSERT_AND_RET_DBG(
1270                 /* And or Or or Eor: BB x int x int --> int */
1271                 (mode_is_int(mymode) || mode_is_reference(mymode) || mymode == mode_b) &&
1272                 op2mode == op1mode &&
1273                 mymode == op2mode,
1274                 "And, Or or Eor node", 0,
1275                 show_binop_failure(n, "/* And or Or or Eor: BB x int x int --> int */");
1276         );
1277         return 1;
1278 }
1279
1280 #define verify_node_And   verify_node_Logic
1281 #define verify_node_Or    verify_node_Logic
1282 #define verify_node_Eor   verify_node_Logic
1283
1284 /**
1285  * verify a Not node
1286  */
1287 static int verify_node_Not(ir_node *n, ir_graph *irg)
1288 {
1289         ir_mode *mymode  = get_irn_mode(n);
1290         ir_mode *op1mode = get_irn_mode(get_Not_op(n));
1291         (void) irg;
1292
1293         ASSERT_AND_RET_DBG(
1294                 /* Not: BB x int --> int */
1295                 (mode_is_int(mymode) || mymode == mode_b) &&
1296                 mymode == op1mode,
1297                 "Not node", 0,
1298                 show_unop_failure(n, "/* Not: BB x int --> int */");
1299         );
1300         return 1;
1301 }
1302
1303 /**
1304  * verify a Cmp node
1305  */
1306 static int verify_node_Cmp(ir_node *n, ir_graph *irg)
1307 {
1308         ir_mode *mymode  = get_irn_mode(n);
1309         ir_mode *op1mode = get_irn_mode(get_Cmp_left(n));
1310         ir_mode *op2mode = get_irn_mode(get_Cmp_right(n));
1311         (void) irg;
1312
1313         ASSERT_AND_RET_DBG(
1314                 /* Cmp: BB x datab x datab --> b16 */
1315                 mode_is_datab(op1mode) &&
1316                 op2mode == op1mode &&
1317                 mymode == mode_b,
1318                 "Cmp node", 0,
1319                 show_binop_failure(n, "/* Cmp: BB x datab x datab --> b16 */");
1320         );
1321         return 1;
1322 }
1323
1324 /**
1325  * verify a Shift node
1326  */
1327 static int verify_node_Shift(ir_node *n, ir_graph *irg)
1328 {
1329         ir_mode *mymode  = get_irn_mode(n);
1330         ir_mode *op1mode = get_irn_mode(get_binop_left(n));
1331         ir_mode *op2mode = get_irn_mode(get_binop_right(n));
1332         (void) irg;
1333
1334         ASSERT_AND_RET_DBG(
1335                 /* Shl, Shr or Shrs: BB x int x int_u --> int */
1336                 mode_is_int(op1mode) &&
1337                 mode_is_int(op2mode) &&
1338                 !mode_is_signed(op2mode) &&
1339                 mymode == op1mode,
1340                 "Shl, Shr or Shrs node", 0,
1341                 show_binop_failure(n, "/* Shl, Shr or Shrs: BB x int x int_u --> int */");
1342         );
1343         return 1;
1344 }
1345
1346 #define verify_node_Shl   verify_node_Shift
1347 #define verify_node_Shr   verify_node_Shift
1348 #define verify_node_Shrs  verify_node_Shift
1349
1350 /**
1351  * verify a Rotl node
1352  */
1353 static int verify_node_Rotl(ir_node *n, ir_graph *irg)
1354 {
1355         ir_mode *mymode  = get_irn_mode(n);
1356         ir_mode *op1mode = get_irn_mode(get_Rotl_left(n));
1357         ir_mode *op2mode = get_irn_mode(get_Rotl_right(n));
1358         (void) irg;
1359
1360         ASSERT_AND_RET_DBG(
1361                 /* Rotl: BB x int x int --> int */
1362                 mode_is_int(op1mode) &&
1363                 mode_is_int(op2mode) &&
1364                 mymode == op1mode,
1365                 "Rotl node", 0,
1366                 show_binop_failure(n, "/* Rotl: BB x int x int --> int */");
1367         );
1368         return 1;
1369 }
1370
1371 /**
1372  * verify a Conv node
1373  */
1374 static int verify_node_Conv(ir_node *n, ir_graph *irg)
1375 {
1376         ir_mode *mymode  = get_irn_mode(n);
1377         ir_mode *op1mode = get_irn_mode(get_Conv_op(n));
1378         (void) irg;
1379
1380         ASSERT_AND_RET_DBG(
1381                 is_irg_state(irg, IR_GRAPH_STATE_BCONV_ALLOWED) ||
1382                 (mode_is_datab(op1mode) && mode_is_data(mymode)),
1383                 "Conv node", 0,
1384                 show_unop_failure(n, "/* Conv: BB x datab --> data */");
1385         );
1386         return 1;
1387 }
1388
1389 /**
1390  * verify a Cast node
1391  */
1392 static int verify_node_Cast(ir_node *n, ir_graph *irg)
1393 {
1394         ir_mode *mymode  = get_irn_mode(n);
1395         ir_mode *op1mode = get_irn_mode(get_Cast_op(n));
1396         (void) irg;
1397
1398         ASSERT_AND_RET_DBG(
1399                 /* Conv: BB x datab1 --> datab2 */
1400                 mode_is_data(op1mode) && op1mode == mymode,
1401                 "Cast node", 0,
1402                 show_unop_failure(n, "/* Conv: BB x datab1 --> datab2 */");
1403         );
1404         return 1;
1405 }
1406
1407 /**
1408  * verify a Phi node
1409  */
1410 static int verify_node_Phi(ir_node *n, ir_graph *irg)
1411 {
1412         ir_mode *mymode = get_irn_mode(n);
1413         ir_node *block  = get_nodes_block(n);
1414         int i;
1415         (void) irg;
1416
1417         /* a Phi node MUST have the same number of inputs as its block
1418          * Exception is a phi with 0 inputs which is used when (re)constructing the
1419          * SSA form */
1420         if (! is_Bad(block) && get_irg_phase_state(get_irn_irg(n)) != phase_building && get_irn_arity(n) > 0) {
1421                 ASSERT_AND_RET_DBG(
1422                         get_irn_arity(n) == get_irn_arity(block),
1423                         "wrong number of inputs in Phi node", 0,
1424                         show_phi_inputs(n, block);
1425                 );
1426         }
1427
1428         /* Phi: BB x dataM^n --> dataM */
1429         for (i = get_Phi_n_preds(n) - 1; i >= 0; --i) {
1430                 ir_node *pred = get_Phi_pred(n, i);
1431                 ASSERT_AND_RET_DBG(get_irn_mode(pred) == mymode,
1432                                    "Phi node", 0, show_phi_failure(n, pred, i);
1433                 );
1434         }
1435         ASSERT_AND_RET(mode_is_dataM(mymode) || mymode == mode_b, "Phi node", 0 );
1436
1437 #if 0
1438         if (mymode == mode_M) {
1439                 for (i = get_Phi_n_preds(n) - 1; i >= 0; --i) {
1440                         int j;
1441                         ir_node *pred_i = get_Phi_pred(n, i);
1442
1443                         for (j = i - 1; j >= 0; --j) {
1444                                 ir_node *pred_j = get_Phi_pred(n, j);
1445
1446                                 /* currently this checks fails for blocks with exception
1447                                    outputs (and these are NOT basic blocks).  So it is disabled yet. */
1448                                 ASSERT_AND_RET_DBG(
1449                                         (pred_i == pred_j) || (get_irn_n(pred_i, -1) != get_irn_n(pred_j, -1)),
1450                                         "At least two different PhiM predecessors are in the same block",
1451                                         0,
1452                                         ir_printf("%+F and %+F of %+F are in %+F\n", pred_i, pred_j, n, get_irn_n(pred_i, -1))
1453                                 );
1454                         }
1455                 }
1456         }
1457 #endif
1458         return 1;
1459 }
1460
1461 /**
1462  * verify a Load node
1463  */
1464 static int verify_node_Load(ir_node *n, ir_graph *irg)
1465 {
1466         ir_mode *mymode  = get_irn_mode(n);
1467         ir_mode *op1mode = get_irn_mode(get_Load_mem(n));
1468         ir_mode *op2mode = get_irn_mode(get_Load_ptr(n));
1469
1470         ASSERT_AND_RET(op1mode == mode_M, "Load node", 0);
1471         if (get_irg_phase_state(irg) != phase_backend) {
1472                 ASSERT_AND_RET(mode_is_reference(op2mode), "Load node", 0 );
1473         }
1474         ASSERT_AND_RET( mymode == mode_T, "Load node", 0 );
1475
1476         /*
1477          * jack's gen_add_firm_code:simpleSel seems to build Load (Load
1478          * (Proj (Proj))) sometimes ...
1479
1480          * interprete.c:ai_eval seems to assume that this happens, too
1481
1482          * obset.c:get_abstval_any can't deal with this if the load has
1483          * mode_T
1484          *
1485           {
1486           ir_entity *ent = hunt_for_entity (get_Load_ptr (n), n);
1487           assert ((NULL != ent) || (mymode != mode_T));
1488           }
1489          */
1490
1491         return 1;
1492 }
1493
1494 /**
1495  * verify a Store node
1496  */
1497 static int verify_node_Store(ir_node *n, ir_graph *irg)
1498 {
1499         ir_entity *target;
1500
1501         ir_mode *mymode  = get_irn_mode(n);
1502         ir_mode *op1mode = get_irn_mode(get_Store_mem(n));
1503         ir_mode *op2mode = get_irn_mode(get_Store_ptr(n));
1504         ir_mode *op3mode = get_irn_mode(get_Store_value(n));
1505
1506         ASSERT_AND_RET(op1mode == mode_M && mode_is_datab(op3mode), "Store node", 0 );
1507         if (get_irg_phase_state(irg) != phase_backend) {
1508                 ASSERT_AND_RET(mode_is_reference(op2mode), "Store node", 0 );
1509         }
1510         ASSERT_AND_RET(mymode == mode_T, "Store node", 0);
1511
1512         target = get_ptr_entity(get_Store_ptr(n));
1513         if (verify_entities && target && get_irg_phase_state(irg) == phase_high) {
1514                 /*
1515                  * If lowered code, any Sels that add 0 may be removed, causing
1516                  * an direct access to entities of array or compound type.
1517                  * Prevent this by checking the phase.
1518                  */
1519                 ASSERT_AND_RET( op3mode == get_type_mode(get_entity_type(target)),
1520                         "Store node", 0);
1521         }
1522
1523         return 1;
1524 }
1525
1526 /**
1527  * verify an Alloc node
1528  */
1529 static int verify_node_Alloc(ir_node *n, ir_graph *irg)
1530 {
1531         ir_mode *mymode  = get_irn_mode(n);
1532         ir_mode *op1mode = get_irn_mode(get_Alloc_mem(n));
1533         ir_mode *op2mode = get_irn_mode(get_Alloc_count(n));
1534         (void) irg;
1535
1536         ASSERT_AND_RET_DBG(
1537                 /* Alloc: BB x M x int_u --> M x X x ref */
1538                 op1mode == mode_M &&
1539                 mode_is_int(op2mode) &&
1540                 !mode_is_signed(op2mode) &&
1541                 mymode == mode_T,
1542                 "Alloc node", 0,
1543                 show_node_failure(n);
1544         );
1545         return 1;
1546 }
1547
1548 /**
1549  * verify a Free node
1550  */
1551 static int verify_node_Free(ir_node *n, ir_graph *irg)
1552 {
1553         ir_mode *mymode  = get_irn_mode(n);
1554         ir_mode *op1mode = get_irn_mode(get_Free_mem(n));
1555         ir_mode *op2mode = get_irn_mode(get_Free_ptr(n));
1556         ir_mode *op3mode = get_irn_mode(get_Free_size(n));
1557         (void) irg;
1558
1559         ASSERT_AND_RET_DBG(
1560                 /* Free: BB x M x ref x int_u --> M */
1561                 op1mode == mode_M && mode_is_reference(op2mode) &&
1562                 mode_is_int(op3mode) &&
1563                 !mode_is_signed(op3mode) &&
1564                 mymode == mode_M,
1565                 "Free node", 0,
1566                 show_triop_failure(n, "/* Free: BB x M x ref x int_u --> M */");
1567         );
1568         return 1;
1569 }
1570
1571 /**
1572  * verify a Sync node
1573  */
1574 static int verify_node_Sync(ir_node *n, ir_graph *irg)
1575 {
1576         int i;
1577         ir_mode *mymode  = get_irn_mode(n);
1578         (void) irg;
1579
1580         /* Sync: BB x M^n --> M */
1581         for (i = get_Sync_n_preds(n) - 1; i >= 0; --i) {
1582                 ASSERT_AND_RET( get_irn_mode(get_Sync_pred(n, i)) == mode_M, "Sync node", 0 );
1583         };
1584         ASSERT_AND_RET( mymode == mode_M, "Sync node", 0 );
1585         return 1;
1586 }
1587
1588 /**
1589  * verify a Confirm node
1590  */
1591 static int verify_node_Confirm(ir_node *n, ir_graph *irg)
1592 {
1593         ir_mode *mymode  = get_irn_mode(n);
1594         ir_mode *op1mode = get_irn_mode(get_Confirm_value(n));
1595         ir_mode *op2mode = get_irn_mode(get_Confirm_bound(n));
1596         (void) irg;
1597
1598         ASSERT_AND_RET_DBG(
1599                 /* Confirm: BB x T x T --> T */
1600                 op1mode == mymode &&
1601                 op2mode == mymode,
1602                 "Confirm node", 0,
1603                 show_binop_failure(n, "/* Confirm: BB x T x T --> T */");
1604         );
1605         return 1;
1606 }
1607
1608 /**
1609  * verify a Mux node
1610  */
1611 static int verify_node_Mux(ir_node *n, ir_graph *irg)
1612 {
1613         ir_mode *mymode  = get_irn_mode(n);
1614         ir_mode *op1mode = get_irn_mode(get_Mux_sel(n));
1615         ir_mode *op2mode = get_irn_mode(get_Mux_true(n));
1616         ir_mode *op3mode = get_irn_mode(get_Mux_false(n));
1617         (void) irg;
1618
1619         ASSERT_AND_RET(
1620                 /* Mux: BB x b x datab x datab --> datab */
1621                 op1mode == mode_b &&
1622                 op2mode == mymode &&
1623                 op3mode == mymode &&
1624                 mode_is_datab(mymode),
1625                 "Mux node", 0
1626                 );
1627         return 1;
1628 }
1629
1630 /**
1631  * verify a CopyB node
1632  */
1633 static int verify_node_CopyB(ir_node *n, ir_graph *irg)
1634 {
1635         ir_mode *mymode  = get_irn_mode(n);
1636         ir_mode *op1mode = get_irn_mode(get_CopyB_mem(n));
1637         ir_mode *op2mode = get_irn_mode(get_CopyB_dst(n));
1638         ir_mode *op3mode = get_irn_mode(get_CopyB_src(n));
1639         ir_type *t = get_CopyB_type(n);
1640
1641         /* CopyB: BB x M x ref x ref --> M x X */
1642         ASSERT_AND_RET(mymode == mode_T && op1mode == mode_M, "CopyB node", 0);
1643         if (get_irg_phase_state(irg) != phase_backend) {
1644                 ASSERT_AND_RET(mode_is_reference(op2mode) && mode_is_reference(op3mode),
1645                         "CopyB node", 0 );
1646         }
1647
1648         ASSERT_AND_RET(
1649                 is_compound_type(t) || is_Array_type(t),
1650                 "CopyB node should copy compound types only", 0 );
1651
1652         /* NoMem nodes are only allowed as memory input if the CopyB is NOT pinned.
1653            This should happen RARELY, as CopyB COPIES MEMORY */
1654         ASSERT_AND_RET(verify_right_pinned(n), "CopyB node with wrong memory input", 0 );
1655         return 1;
1656 }
1657
1658 /**
1659  * verify a Bound node
1660  */
1661 static int verify_node_Bound(ir_node *n, ir_graph *irg)
1662 {
1663         ir_mode *mymode  = get_irn_mode(n);
1664         ir_mode *op1mode = get_irn_mode(get_Bound_mem(n));
1665         ir_mode *op2mode = get_irn_mode(get_Bound_index(n));
1666         ir_mode *op3mode = get_irn_mode(get_Bound_lower(n));
1667         ir_mode *op4mode = get_irn_mode(get_Bound_upper(n));
1668         (void) irg;
1669
1670         /* Bound: BB x M x int x int x int --> M x X */
1671         ASSERT_AND_RET(
1672                 mymode == mode_T &&
1673                 op1mode == mode_M &&
1674                 op2mode == op3mode &&
1675                 op3mode == op4mode &&
1676                 mode_is_int(op3mode),
1677                 "Bound node", 0 );
1678         return 1;
1679 }
1680
1681 /**
1682  * Check dominance.
1683  * For each usage of a node, it is checked, if the block of the
1684  * node dominates the block of the usage (for phis: the predecessor
1685  * block of the phi for the corresponding edge).
1686  *
1687  * @return non-zero on success, 0 on dominance error
1688  */
1689 static int check_dominance_for_node(ir_node *use)
1690 {
1691         /* This won't work for blocks and the end node */
1692         if (!is_Block(use) && !is_End(use) && !is_Anchor(use)) {
1693                 int i;
1694                 ir_node *bl = get_nodes_block(use);
1695
1696                 for (i = get_irn_arity(use) - 1; i >= 0; --i) {
1697                         ir_node  *def    = get_irn_n(use, i);
1698                         ir_node  *def_bl = get_nodes_block(def);
1699                         ir_node  *use_bl = bl;
1700                         ir_graph *irg;
1701
1702                         /* we have no dominance relation for unreachable blocks, so we can't
1703                          * check the dominance property there */
1704                         if (!is_Block(def_bl) || get_Block_dom_depth(def_bl) == -1)
1705                                 continue;
1706
1707                         if (is_Phi(use)) {
1708                                 if (is_Bad(def))
1709                                         continue;
1710                                 use_bl = get_Block_cfgpred_block(bl, i);
1711                         }
1712
1713                         if (!is_Block(use_bl) || get_Block_dom_depth(use_bl) == -1)
1714                                 continue;
1715
1716                         irg = get_irn_irg(use);
1717                         ASSERT_AND_RET_DBG(
1718                                 block_dominates(def_bl, use_bl),
1719                                 "the definition of a value used violates the dominance property", 0,
1720                                 ir_fprintf(stderr,
1721                                 "graph %+F: %+F of %+F must dominate %+F of user %+F input %d\n",
1722                                 irg, def_bl, def, use_bl, use, i
1723                                 );
1724                         );
1725                 }
1726         }
1727         return 1;
1728 }
1729
1730 /* Tests the modes of n and its predecessors. */
1731 int irn_verify_irg(ir_node *n, ir_graph *irg)
1732 {
1733         ir_op *op;
1734
1735         if (!get_node_verification_mode())
1736                 return 1;
1737
1738         /*
1739          * do NOT check placement in interprocedural view, as we don't always
1740          * know the "right" graph ...
1741          */
1742
1743 #ifndef NDEBUG
1744         /* this is an expensive check for large graphs (it has a quadratic
1745          * runtime but with a small constant); so do NOT run it in release mode
1746          */
1747         ASSERT_AND_RET_DBG(
1748                 node_is_in_irgs_storage(irg, n),
1749                 "Node is not stored on proper IR graph!", 0,
1750                 show_node_on_graph(irg, n);
1751         );
1752 #endif
1753         assert(get_irn_irg(n) == irg);
1754         {
1755                 unsigned idx           = get_irn_idx(n);
1756                 ir_node *node_from_map = get_idx_irn(irg, idx);
1757                 ASSERT_AND_RET_DBG(node_from_map == n, "Node index and index map entry differ", 0,
1758                         ir_printf("node %+F node in map %+F(%p)\n", n, node_from_map, node_from_map));
1759         }
1760
1761         op = get_irn_op(n);
1762
1763         if (_get_op_pinned(op) >= op_pin_state_exc_pinned) {
1764                 op_pin_state state = get_irn_pinned(n);
1765                 ASSERT_AND_RET_DBG(
1766                         state == op_pin_state_floats ||
1767                         state == op_pin_state_pinned,
1768                         "invalid pin state", 0,
1769                         ir_printf("node %+F", n));
1770         } else if (!is_Block(n) && is_irn_pinned_in_irg(n)
1771                    && !is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK)) {
1772                 ASSERT_AND_RET_DBG(is_Block(get_nodes_block(n)) || is_Anchor(n),
1773                                 "block input is not a block", 0,
1774                                 ir_printf("node %+F", n));
1775         }
1776
1777         if (op->ops.verify_node)
1778                 return op->ops.verify_node(n, irg);
1779
1780         /* All went ok */
1781         return 1;
1782 }
1783
1784 int irn_verify(ir_node *n)
1785 {
1786 #ifdef DEBUG_libfirm
1787         return irn_verify_irg(n, get_irn_irg(n));
1788 #else
1789         (void)n;
1790         return 1;
1791 #endif
1792 }
1793
1794 /*-----------------------------------------------------------------*/
1795 /* Verify the whole graph.                                         */
1796 /*-----------------------------------------------------------------*/
1797
1798 #ifdef DEBUG_libfirm
1799 /**
1800  * Walker to check every node
1801  */
1802 static void verify_wrap(ir_node *node, void *env)
1803 {
1804         int *res = (int*)env;
1805         *res = irn_verify_irg(node, get_irn_irg(node));
1806 }
1807
1808 /**
1809  * Walker to check every node including SSA property.
1810  * Only called if dominance info is available.
1811  */
1812 static void verify_wrap_ssa(ir_node *node, void *env)
1813 {
1814         int *res = (int*)env;
1815
1816         *res = irn_verify_irg(node, get_irn_irg(node));
1817         if (*res) {
1818                 *res = check_dominance_for_node(node);
1819         }
1820 }
1821
1822 #endif /* DEBUG_libfirm */
1823
1824 typedef struct check_cfg_env_t {
1825         pmap *branch_nodes; /**< map blocks to their branching nodes,
1826                                  map mode_X nodes to the blocks they branch to */
1827         int   res;
1828         ir_nodeset_t reachable_blocks;
1829         ir_nodeset_t kept_nodes;
1830         ir_nodeset_t true_projs;
1831         ir_nodeset_t false_projs;
1832 } check_cfg_env_t;
1833
1834 static int check_block_cfg(ir_node *block, check_cfg_env_t *env)
1835 {
1836         pmap *branch_nodes;
1837         int   n_cfgpreds;
1838         int   i;
1839
1840         ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->reachable_blocks, block),
1841                            "Block is not reachable by blockwalker (endless loop with no kept block?)", 0,
1842                            ir_printf("block %+F\n", block));
1843
1844         n_cfgpreds   = get_Block_n_cfgpreds(block);
1845         branch_nodes = env->branch_nodes;
1846         for (i = 0; i < n_cfgpreds; ++i) {
1847                 /* check that each mode_X node is only connected
1848                  * to 1 user */
1849                 ir_node *branch = get_Block_cfgpred(block, i);
1850                 ir_node *former_dest;
1851                 ir_node *former_branch;
1852                 ir_node *branch_proj;
1853                 ir_node *branch_block;
1854                 branch = skip_Tuple(branch);
1855                 if (is_Bad(branch))
1856                         continue;
1857                 former_dest = pmap_get(branch_nodes, branch);
1858                 ASSERT_AND_RET_DBG(former_dest==NULL || is_unknown_jump(skip_Proj(branch)),
1859                                                    "Multiple users on mode_X node", 0,
1860                                                    ir_printf("node %+F\n", branch));
1861                 pmap_insert(branch_nodes, branch, block);
1862
1863                 /* check that there's only 1 branching instruction in each block */
1864                 branch_block = get_nodes_block(branch);
1865                 branch_proj  = branch;
1866                 if (is_Proj(branch)) {
1867                         branch = skip_Proj(branch);
1868                 }
1869                 former_branch = pmap_get(branch_nodes, branch_block);
1870
1871                 ASSERT_AND_RET_DBG(former_branch == NULL || former_branch == branch,
1872                                                    "Multiple branching nodes in a block", 0,
1873                                                    ir_printf("nodes %+F,%+F in block %+F\n",
1874                                                                          branch, former_branch, branch_block));
1875                 pmap_insert(branch_nodes, branch_block, branch);
1876
1877                 if (is_Cond(branch)) {
1878                         long pn = get_Proj_proj(branch_proj);
1879                         if (get_irn_mode(get_Cond_selector(branch)) == mode_b) {
1880                                 if (pn == pn_Cond_true)
1881                                         ir_nodeset_insert(&env->true_projs, branch);
1882                                 if (pn == pn_Cond_false)
1883                                         ir_nodeset_insert(&env->false_projs, branch);
1884                         } else {
1885                                 int default_pn = get_Cond_default_proj(branch);
1886                                 if (pn == default_pn)
1887                                         ir_nodeset_insert(&env->true_projs, branch);
1888                         }
1889                 }
1890         }
1891
1892         return 1;
1893 }
1894
1895 static void check_cfg_walk_func(ir_node *node, void *data)
1896 {
1897         check_cfg_env_t *env = (check_cfg_env_t*)data;
1898         if (!is_Block(node))
1899                 return;
1900         env->res &= check_block_cfg(node, env);
1901 }
1902
1903 static int verify_block_branch(ir_node *block, check_cfg_env_t *env)
1904 {
1905         ir_node *branch = pmap_get(env->branch_nodes, block);
1906         ASSERT_AND_RET_DBG(branch != NULL
1907                            || ir_nodeset_contains(&env->kept_nodes, block)
1908                            || block == get_irg_end_block(get_irn_irg(block)),
1909                            "block contains no cfop", 0,
1910                            ir_printf("block %+F\n", block));
1911         return 1;
1912 }
1913
1914 static int verify_cond_projs(ir_node *cond, check_cfg_env_t *env)
1915 {
1916         if (get_irn_mode(get_Cond_selector(cond)) == mode_b) {
1917                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->true_projs, cond),
1918                                                    "Cond node lacks true proj", 0,
1919                                                    ir_printf("Cond %+F\n", cond));
1920                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->false_projs, cond),
1921                                                    "Cond node lacks false proj", 0,
1922                                                    ir_printf("Cond %+F\n", cond));
1923         } else {
1924                 ASSERT_AND_RET_DBG(ir_nodeset_contains(&env->true_projs, cond),
1925                                    "Cond node lacks default Proj", 0,
1926                                    ir_printf("Cond %+F\n", cond));
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 (!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 && get_irg_dom_state(irg) == dom_consistent
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(ir_node *n, ir_graph *irg, const char **bad_string)
2067 {
2068         int res;
2069         firm_verification_t old = get_node_verification_mode();
2070
2071         firm_verify_failure_msg = NULL;
2072         do_node_verification(FIRM_VERIFICATION_ERROR_ONLY);
2073         res = irn_verify_irg(n, irg);
2074         if (res && get_irg_dom_state(irg) == dom_consistent &&
2075             get_irg_pinned(irg) == op_pin_state_pinned)
2076                 res = check_dominance_for_node(n);
2077         do_node_verification(old);
2078         *bad_string = firm_verify_failure_msg;
2079
2080         return res;
2081 }
2082
2083 typedef struct verify_bad_env_t {
2084         int flags;
2085         int res;
2086 } verify_bad_env_t;
2087
2088 /**
2089  * Pre-Walker: check Bad predecessors of node.
2090  */
2091 static void check_bads(ir_node *node, void *env)
2092 {
2093         verify_bad_env_t *venv = (verify_bad_env_t*)env;
2094         int i, arity = get_irn_arity(node);
2095         ir_graph *irg = get_irn_irg(node);
2096
2097         if (is_Block(node)) {
2098                 if ((venv->flags & BAD_CF) == 0) {
2099
2100                         /* check for Bad Block predecessor */
2101                         for (i = 0; i < arity; ++i) {
2102                                 ir_node *pred = get_irn_n(node, i);
2103
2104                                 if (is_Bad(pred)) {
2105                                         venv->res |= BAD_CF;
2106
2107                                         if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2108                                                 fprintf(stderr, "irg_verify_bads: Block %ld has Bad predecessor\n", get_irn_node_nr(node));
2109                                         }
2110                                         if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2111                                                 dump_ir_graph(irg, "assert");
2112                                                 assert(0 && "Bad CF detected");
2113                                         }
2114                                 }
2115                         }
2116                 }
2117         } else {
2118                 if ((venv->flags & BAD_BLOCK) == 0) {
2119
2120                         /* check for Bad Block */
2121                         if (is_Bad(get_nodes_block(node))) {
2122                                 venv->res |= BAD_BLOCK;
2123
2124                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2125                                         fprintf(stderr, "irg_verify_bads: node %ld has Bad Block\n", get_irn_node_nr(node));
2126                                 }
2127                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2128                                         dump_ir_graph(irg, "assert");
2129                                         assert(0 && "Bad CF detected");
2130                                 }
2131                         }
2132                 }
2133
2134                 if ((venv->flags & TUPLE) == 0) {
2135                         if (is_Tuple(node)) {
2136                                 venv->res |= TUPLE;
2137
2138                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2139                                         fprintf(stderr, "irg_verify_bads: node %ld is a Tuple\n", get_irn_node_nr(node));
2140                                 }
2141                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2142                                         dump_ir_graph(irg, "assert");
2143                                         assert(0 && "Tuple detected");
2144                                 }
2145                         }
2146                 }
2147
2148                 for (i = 0; i < arity; ++i) {
2149                         ir_node *pred = get_irn_n(node, i);
2150
2151                         if (is_Bad(pred)) {
2152                                 /* check for Phi with Bad inputs */
2153                                 if (is_Phi(node) && !is_Bad(get_nodes_block(node)) && is_Bad(get_irn_n(get_nodes_block(node), i))) {
2154                                         if (venv->flags & BAD_CF)
2155                                                 continue;
2156                                         else {
2157                                                 venv->res |= BAD_CF;
2158
2159                                                 if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2160                                                         fprintf(stderr, "irg_verify_bads: Phi %ld has Bad Input\n", get_irn_node_nr(node));
2161                                                 }
2162                                                 if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2163                                                         dump_ir_graph(irg, "assert");
2164                                                         assert(0 && "Bad CF detected");
2165                                                 }
2166                                         }
2167                                 }
2168
2169                                 /* Bad node input */
2170                                 if ((venv->flags & BAD_DF) == 0) {
2171                                         venv->res |= BAD_DF;
2172
2173                                         if (get_node_verification_mode() == FIRM_VERIFICATION_REPORT) {
2174                                                 fprintf(stderr, "irg_verify_bads: node %ld has Bad Input\n", get_irn_node_nr(node));
2175                                         }
2176                                         if (get_node_verification_mode() == FIRM_VERIFICATION_ON) {
2177                                                 dump_ir_graph(irg, "assert");
2178                                                 assert(0 && "Bad NON-CF detected");
2179                                         }
2180                                 }
2181                         }
2182                 }
2183         }
2184 }
2185
2186 /*
2187  * verify occurrence of bad nodes
2188  */
2189 int irg_verify_bads(ir_graph *irg, int flags)
2190 {
2191         verify_bad_env_t env;
2192
2193         env.flags = flags;
2194         env.res   = 0;
2195
2196         irg_walk_graph(irg, check_bads, NULL, &env);
2197
2198         return env.res;
2199 }
2200
2201 /*
2202  * set the default verify operation
2203  */
2204 void firm_set_default_verifier(unsigned code, ir_op_ops *ops)
2205 {
2206 #define CASE(a)                           \
2207    case iro_##a:                          \
2208      ops->verify_node  = verify_node_##a; \
2209      break
2210
2211         switch (code) {
2212         CASE(Proj);
2213         CASE(Block);
2214         CASE(Start);
2215         CASE(Jmp);
2216         CASE(IJmp);
2217         CASE(Cond);
2218         CASE(Return);
2219         CASE(Raise);
2220         CASE(Const);
2221         CASE(SymConst);
2222         CASE(Sel);
2223         CASE(InstOf);
2224         CASE(Call);
2225         CASE(Add);
2226         CASE(Sub);
2227         CASE(Minus);
2228         CASE(Mul);
2229         CASE(Mulh);
2230         CASE(Div);
2231         CASE(Mod);
2232         CASE(And);
2233         CASE(Or);
2234         CASE(Eor);
2235         CASE(Not);
2236         CASE(Cmp);
2237         CASE(Shl);
2238         CASE(Shr);
2239         CASE(Shrs);
2240         CASE(Rotl);
2241         CASE(Conv);
2242         CASE(Cast);
2243         CASE(Phi);
2244         CASE(Load);
2245         CASE(Store);
2246         CASE(Alloc);
2247         CASE(Free);
2248         CASE(Sync);
2249         CASE(Confirm);
2250         CASE(Mux);
2251         CASE(CopyB);
2252         CASE(Bound);
2253         default:
2254                 /* leave NULL */;
2255         }
2256 #undef CASE
2257
2258 #define CASE(a)                          \
2259    case iro_##a:                         \
2260      ops->verify_proj_node  = verify_node_Proj_##a; \
2261      break
2262
2263         switch (code) {
2264         CASE(Start);
2265         CASE(Cond);
2266         CASE(Raise);
2267         CASE(InstOf);
2268         CASE(Call);
2269         CASE(Div);
2270         CASE(Mod);
2271         CASE(Load);
2272         CASE(Store);
2273         CASE(Alloc);
2274         CASE(Proj);
2275         CASE(Tuple);
2276         CASE(CopyB);
2277         CASE(Bound);
2278         default:
2279                 /* leave NULL */;
2280         }
2281 #undef CASE
2282 }