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