array: Add and use NEW_ARR_FZ().
[libfirm] / ir / ir / irgraph.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    Entry point to the representation of procedure code.
23  * @author   Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Michael Beck
24  */
25 #include "config.h"
26
27 #include <string.h>
28 #include <stddef.h>
29
30 #include "xmalloc.h"
31 #include "ircons_t.h"
32 #include "irgraph_t.h"
33 #include "irprog_t.h"
34 #include "irgraph_t.h"
35 #include "irnode_t.h"
36 #include "iropt_t.h"
37 #include "irflag_t.h"
38 #include "array.h"
39 #include "irgmod.h"
40 #include "irouts.h"
41 #include "irhooks.h"
42 #include "irtools.h"
43 #include "util.h"
44 #include "irgwalk.h"
45 #include "irbackedge_t.h"
46 #include "iredges_t.h"
47 #include "type_t.h"
48 #include "irmemory.h"
49 #include "iroptimize.h"
50 #include "irgopt.h"
51
52 #define INITIAL_IDX_IRN_MAP_SIZE 1024
53 /** Suffix that is added to every frame type. */
54 #define FRAME_TP_SUFFIX "frame_tp"
55
56 ir_graph *current_ir_graph;
57 ir_graph *get_current_ir_graph(void)
58 {
59         return current_ir_graph;
60 }
61
62 void set_current_ir_graph(ir_graph *graph)
63 {
64         current_ir_graph = graph;
65 }
66
67 /** contains the suffix for frame type names */
68 static ident *frame_type_suffix = NULL;
69
70 void firm_init_irgraph(void)
71 {
72         frame_type_suffix = new_id_from_str(FRAME_TP_SUFFIX);
73 }
74
75 /**
76  * Allocate a new IR graph.
77  * This function respects the registered graph data. The only reason for
78  * this function is, that there are two locations, where graphs are
79  * allocated (new_r_ir_graph, new_const_code_irg).
80  * @return Memory for a new graph.
81  */
82 static ir_graph *alloc_graph(void)
83 {
84         ir_graph *const res = XMALLOCZ(ir_graph);
85         res->kind = k_ir_graph;
86
87         /* initialize the idx->node map. */
88         res->idx_irn_map = NEW_ARR_FZ(ir_node*, INITIAL_IDX_IRN_MAP_SIZE);
89
90         obstack_init(&res->obst);
91
92         /* value table for global value numbering for optimizing use in iropt.c */
93         new_identities(res);
94
95         return res;
96 }
97
98 /**
99  * Frees an allocated IR graph
100  */
101 static void free_graph(ir_graph *irg)
102 {
103         for (ir_edge_kind_t i = EDGE_KIND_FIRST; i < EDGE_KIND_LAST; ++i)
104                 edges_deactivate_kind(irg, i);
105         DEL_ARR_F(irg->idx_irn_map);
106         free(irg);
107 }
108
109 void irg_set_nloc(ir_graph *res, int n_loc)
110 {
111         assert(irg_is_constrained(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION));
112
113         res->n_loc = n_loc + 1;     /* number of local variables that are never
114                                        dereferenced in this graph plus one for
115                                        the store. This is not the number of
116                                        parameters to the procedure!  */
117
118         if (res->loc_descriptions) {
119                 xfree(res->loc_descriptions);
120                 res->loc_descriptions = NULL;
121         }
122 }
123
124 ir_graph *new_r_ir_graph(ir_entity *ent, int n_loc)
125 {
126         ir_graph *res;
127         ir_node  *first_block;
128         ir_node  *start, *start_block, *initial_mem, *projX;
129
130         res = alloc_graph();
131
132         /* inform statistics here, as blocks will be already build on this graph */
133         hook_new_graph(res, ent);
134
135         /* graphs are in construction mode by default */
136         add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
137         irg_set_nloc(res, n_loc);
138
139         res->irg_pinned_state    = op_pin_state_pinned;
140         res->typeinfo_state      = ir_typeinfo_none;
141         set_irp_typeinfo_inconsistent();           /* there is a new graph with typeinfo_none. */
142         res->callee_info_state   = irg_callee_info_none;
143         res->class_cast_state    = ir_class_casts_transitive;
144         res->fp_model            = fp_model_precise;
145         res->mem_disambig_opt    = aa_opt_inherited;
146
147         /*-- Type information for the procedure of the graph --*/
148         res->ent = ent;
149         set_entity_irg(ent, res);
150
151         /*--  a class type so that it can contain "inner" methods as in Pascal. --*/
152         res->frame_type = new_type_frame();
153
154         /* the Anchor node must be created first */
155         res->anchor = new_r_Anchor(res);
156
157         /*-- Nodes needed in every graph --*/
158         set_irg_end_block(res, new_r_immBlock(res));
159         set_irg_end(res, new_r_End(res, 0, NULL));
160
161         start_block = new_r_Block_noopt(res, 0, NULL);
162         set_irg_start_block(res, start_block);
163         set_irg_no_mem     (res, new_r_NoMem(res));
164         start = new_r_Start(res);
165         set_irg_start      (res, start);
166
167         /* Proj results of start node */
168         projX                   = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
169         set_irg_initial_exec    (res, projX);
170         set_irg_frame           (res, new_r_Proj(start, mode_P_data, pn_Start_P_frame_base));
171         set_irg_args            (res, new_r_Proj(start, mode_T,      pn_Start_T_args));
172         initial_mem             = new_r_Proj(start, mode_M, pn_Start_M);
173         set_irg_initial_mem(res, initial_mem);
174
175         res->index       = get_irp_new_irg_idx();
176 #ifdef DEBUG_libfirm
177         res->graph_nr    = get_irp_new_node_nr();
178 #endif
179
180         set_r_cur_block(res, start_block);
181         set_r_store(res, initial_mem);
182
183         /*-- Make a block to start with --*/
184         first_block = new_r_Block(res, 1, &projX);
185         set_r_cur_block(res, first_block);
186
187         res->method_execution_frequency = -1.0;
188
189         return res;
190 }
191
192 ir_graph *new_ir_graph(ir_entity *ent, int n_loc)
193 {
194         ir_graph *res = new_r_ir_graph(ent, n_loc);
195         add_irp_irg(res);          /* remember this graph global. */
196         return res;
197 }
198
199 ir_graph *new_const_code_irg(void)
200 {
201         ir_graph *res = alloc_graph();
202         ir_node  *body_block;
203         ir_node  *end;
204         ir_node  *end_block;
205         ir_node  *no_mem;
206         ir_node  *projX;
207         ir_node  *start_block;
208         ir_node  *start;
209
210         /* inform statistics here, as blocks will be already build on this graph */
211         hook_new_graph(res, NULL);
212
213         res->n_loc            = 1; /* Only the memory. */
214         res->irg_pinned_state = op_pin_state_pinned;
215         res->fp_model         = fp_model_precise;
216
217         add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
218
219         /* the Anchor node must be created first */
220         res->anchor = new_r_Anchor(res);
221
222         /* -- The end block -- */
223         end_block = new_r_Block_noopt(res, 0, NULL);
224         set_irg_end_block(res, end_block);
225         end = new_r_End(res, 0, NULL);
226         set_irg_end(res, end);
227
228         /* -- The start block -- */
229         start_block = new_r_Block_noopt(res, 0, NULL);
230         set_irg_start_block(res, start_block);
231         no_mem = new_r_NoMem(res);
232         set_irg_no_mem(res, no_mem);
233         start = new_r_Start(res);
234         set_irg_start(res, start);
235
236         /* Proj results of start node */
237         set_irg_initial_mem(res, new_r_Proj(start, mode_M, pn_Start_M));
238         projX = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
239
240         body_block = new_r_Block(res, 1, &projX);
241
242         set_r_cur_block(res, body_block);
243
244         /* Set the visited flag high enough that the blocks will never be visited. */
245         set_irn_visited(body_block, -1);
246         set_Block_block_visited(body_block, -1);
247         set_Block_block_visited(start_block, -1);
248         set_irn_visited(start_block, -1);
249
250         return res;
251 }
252
253 /**
254  * Pre-Walker: Copies blocks and nodes from the original method graph
255  * to the copied graph.
256  *
257  * @param n    A node from the original method graph.
258  * @param env  The copied graph.
259  */
260 static void copy_all_nodes(ir_node *node, void *env)
261 {
262         ir_graph *irg      = (ir_graph*)env;
263         ir_node  *new_node = irn_copy_into_irg(node, irg);
264
265         set_irn_link(node, new_node);
266
267         /* fix access to entities on the stack frame */
268         if (is_Sel(new_node)) {
269                 ir_entity *ent = get_Sel_entity(new_node);
270                 ir_type   *tp  = get_entity_owner(ent);
271
272                 if (is_frame_type(tp)) {
273                         /* replace by the copied entity */
274                         ent = (ir_entity*)get_entity_link(ent);
275
276                         assert(is_entity(ent));
277                         assert(get_entity_owner(ent) == get_irg_frame_type(irg));
278                         set_Sel_entity(new_node, ent);
279                 }
280         }
281 }
282
283 /**
284  * Post-walker: Set the predecessors of the copied nodes.
285  * The copied nodes are set as link of their original nodes. The links of
286  * "irn" predecessors are the predecessors of copied node.
287  */
288 static void rewire(ir_node *irn, void *env)
289 {
290         (void) env;
291         irn_rewire_inputs(irn);
292 }
293
294 static ir_node *get_new_node(const ir_node *old_node)
295 {
296         return (ir_node*) get_irn_link(old_node);
297 }
298
299 ir_graph *create_irg_copy(ir_graph *irg)
300 {
301         ir_graph *res;
302
303         res = alloc_graph();
304
305         res->irg_pinned_state = irg->irg_pinned_state;
306         res->fp_model         = irg->fp_model;
307
308         /* clone the frame type here for safety */
309         irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
310         res->frame_type  = clone_frame_type(irg->frame_type);
311
312         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
313
314         /* copy all nodes from the graph irg to the new graph res */
315         irg_walk_anchors(irg, copy_all_nodes, rewire, res);
316
317         /* copy the Anchor node */
318         res->anchor = get_new_node(irg->anchor);
319
320         /* -- The end block -- */
321         set_irg_end_block (res, get_new_node(get_irg_end_block(irg)));
322         set_irg_end       (res, get_new_node(get_irg_end(irg)));
323
324         /* -- The start block -- */
325         set_irg_start_block(res, get_new_node(get_irg_start_block(irg)));
326         set_irg_no_mem     (res, get_new_node(get_irg_no_mem(irg)));
327         set_irg_start      (res, get_new_node(get_irg_start(irg)));
328
329         /* Proj results of start node */
330         set_irg_initial_mem(res, get_new_node(get_irg_initial_mem(irg)));
331
332         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
333         irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
334
335         return res;
336 }
337
338 void free_ir_graph(ir_graph *irg)
339 {
340         assert(is_ir_graph(irg));
341
342         remove_irp_irg(irg);
343         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
344
345         hook_free_graph(irg);
346         free_irg_outs(irg);
347         del_identities(irg);
348         if (irg->ent) {
349                 set_entity_irg(irg->ent, NULL);  /* not set in const code irg */
350         }
351
352         free_End(get_irg_end(irg));
353         obstack_free(&irg->obst, NULL);
354         if (irg->loc_descriptions)
355                 free(irg->loc_descriptions);
356         irg->kind = k_BAD;
357         free_graph(irg);
358 }
359
360 int (is_ir_graph)(const void *thing)
361 {
362         return is_ir_graph_(thing);
363 }
364
365 #ifdef DEBUG_libfirm
366 long get_irg_graph_nr(const ir_graph *irg)
367 {
368         return irg->graph_nr;
369 }
370 #else
371 long get_irg_graph_nr(const ir_graph *irg)
372 {
373         return PTR_TO_INT(irg);
374 }
375 #endif
376
377 size_t get_irg_idx(const ir_graph *irg)
378 {
379         return irg->index;
380 }
381
382 ir_node *(get_idx_irn)(const ir_graph *irg, unsigned idx)
383 {
384         return get_idx_irn_(irg, idx);
385 }
386
387 ir_node *(get_irg_start_block)(const ir_graph *irg)
388 {
389         return get_irg_start_block_(irg);
390 }
391
392 void (set_irg_start_block)(ir_graph *irg, ir_node *node)
393 {
394         set_irg_start_block_(irg, node);
395 }
396
397 ir_node *(get_irg_start)(const ir_graph *irg)
398 {
399         return get_irg_start_(irg);
400 }
401
402 void (set_irg_start)(ir_graph *irg, ir_node *node)
403 {
404         set_irg_start_(irg, node);
405 }
406
407 ir_node *(get_irg_end_block)(const ir_graph *irg)
408 {
409         return get_irg_end_block_(irg);
410 }
411
412 void (set_irg_end_block)(ir_graph *irg, ir_node *node)
413 {
414         set_irg_end_block_(irg, node);
415 }
416
417 ir_node *(get_irg_end)(const ir_graph *irg)
418 {
419         return get_irg_end_(irg);
420 }
421
422 void (set_irg_end)(ir_graph *irg, ir_node *node)
423 {
424         set_irg_end_(irg, node);
425 }
426
427 ir_node *(get_irg_initial_exec)(const ir_graph *irg)
428 {
429         return get_irg_initial_exec_(irg);
430 }
431
432 void (set_irg_initial_exec)(ir_graph *irg, ir_node *node)
433 {
434         set_irg_initial_exec_(irg, node);
435 }
436
437 ir_node *(get_irg_frame)(const ir_graph *irg)
438 {
439         return get_irg_frame_(irg);
440 }
441
442 void (set_irg_frame)(ir_graph *irg, ir_node *node)
443 {
444         set_irg_frame_(irg, node);
445 }
446
447 ir_node *(get_irg_initial_mem)(const ir_graph *irg)
448 {
449         return get_irg_initial_mem_(irg);
450 }
451
452 void (set_irg_initial_mem)(ir_graph *irg, ir_node *node)
453 {
454         set_irg_initial_mem_(irg, node);
455 }
456
457 ir_node *(get_irg_args)(const ir_graph *irg)
458 {
459         return get_irg_args_(irg);
460 }
461
462 void (set_irg_args)(ir_graph *irg, ir_node *node)
463 {
464         set_irg_args_(irg, node);
465 }
466
467 ir_node *(get_irg_no_mem)(const ir_graph *irg)
468 {
469         return get_irg_no_mem_(irg);
470 }
471
472 void (set_irg_no_mem)(ir_graph *irg, ir_node *node)
473 {
474         set_irg_no_mem_(irg, node);
475 }
476
477 ir_entity *(get_irg_entity)(const ir_graph *irg)
478 {
479         return get_irg_entity_(irg);
480 }
481
482 void (set_irg_entity)(ir_graph *irg, ir_entity *ent)
483 {
484         set_irg_entity_(irg, ent);
485 }
486
487 ir_type *(get_irg_frame_type)(ir_graph *irg)
488 {
489         return get_irg_frame_type_(irg);
490 }
491
492 void (set_irg_frame_type)(ir_graph *irg, ir_type *ftp)
493 {
494         set_irg_frame_type_(irg, ftp);
495 }
496
497 int get_irg_n_locs(ir_graph *irg)
498 {
499         return irg->n_loc - 1;
500 }
501
502 int node_is_in_irgs_storage(const ir_graph *irg, const ir_node *n)
503 {
504         /* Check whether the ir_node pointer is on the obstack.
505          * A more sophisticated check would test the "whole" ir_node. */
506         for (struct _obstack_chunk const *p = irg->obst.chunk; p; p = p->prev) {
507                 if (((char *)p->contents <= (char *)n) && ((char *)n < (char *)p->limit))
508                         return 1;
509         }
510
511         return 0;
512 }
513
514 op_pin_state (get_irg_pinned)(const ir_graph *irg)
515 {
516         return get_irg_pinned_(irg);
517 }
518
519 irg_callee_info_state (get_irg_callee_info_state)(const ir_graph *irg)
520 {
521         return get_irg_callee_info_state_(irg);
522 }
523
524 void (set_irg_callee_info_state)(ir_graph *irg, irg_callee_info_state s)
525 {
526         set_irg_callee_info_state_(irg, s);
527 }
528
529 void (set_irg_link)(ir_graph *irg, void *thing)
530 {
531         set_irg_link_(irg, thing);
532 }
533
534 void *(get_irg_link)(const ir_graph *irg)
535 {
536         return get_irg_link_(irg);
537 }
538
539 ir_visited_t (get_irg_visited)(const ir_graph *irg)
540 {
541         return get_irg_visited_(irg);
542 }
543
544 /** maximum visited flag content of all ir_graph visited fields. */
545 static ir_visited_t max_irg_visited = 0;
546
547 void set_irg_visited(ir_graph *irg, ir_visited_t visited)
548 {
549         irg->visited = visited;
550         if (irg->visited > max_irg_visited) {
551                 max_irg_visited = irg->visited;
552         }
553 }
554
555 void inc_irg_visited(ir_graph *irg)
556 {
557         ++irg->visited;
558         if (irg->visited > max_irg_visited) {
559                 max_irg_visited = irg->visited;
560         }
561 }
562
563 ir_visited_t get_max_irg_visited(void)
564 {
565         return max_irg_visited;
566 }
567
568 void set_max_irg_visited(int val)
569 {
570         max_irg_visited = val;
571 }
572
573 ir_visited_t inc_max_irg_visited(void)
574 {
575 #ifndef NDEBUG
576         size_t i;
577         for (i = 0; i < get_irp_n_irgs(); i++)
578                 assert(max_irg_visited >= get_irg_visited(get_irp_irg(i)));
579 #endif
580         return ++max_irg_visited;
581 }
582
583 ir_visited_t (get_irg_block_visited)(const ir_graph *irg)
584 {
585         return get_irg_block_visited_(irg);
586 }
587
588 void (set_irg_block_visited)(ir_graph *irg, ir_visited_t visited)
589 {
590         set_irg_block_visited_(irg, visited);
591 }
592
593 void (inc_irg_block_visited)(ir_graph *irg)
594 {
595   inc_irg_block_visited_(irg);
596 }
597
598 unsigned (get_irg_fp_model)(const ir_graph *irg)
599 {
600         return get_irg_fp_model_(irg);
601 }
602
603 void set_irg_fp_model(ir_graph *irg, unsigned model)
604 {
605         irg->fp_model = model;
606 }
607
608 void set_irg_loc_description(ir_graph *irg, int n, void *description)
609 {
610         assert(0 <= n && n < irg->n_loc);
611
612         if (! irg->loc_descriptions)
613                 irg->loc_descriptions = XMALLOCNZ(void*, irg->n_loc);
614
615         irg->loc_descriptions[n] = description;
616 }
617
618 void *get_irg_loc_description(ir_graph *irg, int n)
619 {
620         assert(0 <= n && n < irg->n_loc);
621         return irg->loc_descriptions ? irg->loc_descriptions[n] : NULL;
622 }
623
624 #ifndef NDEBUG
625 void ir_reserve_resources(ir_graph *irg, ir_resources_t resources)
626 {
627         assert((irg->reserved_resources & resources) == 0);
628         irg->reserved_resources |= resources;
629 }
630
631 void ir_free_resources(ir_graph *irg, ir_resources_t resources)
632 {
633         assert((irg->reserved_resources & resources) == resources);
634         irg->reserved_resources &= ~resources;
635 }
636
637 ir_resources_t ir_resources_reserved(const ir_graph *irg)
638 {
639         return irg->reserved_resources;
640 }
641 #endif
642
643 unsigned get_irg_last_idx(const ir_graph *irg)
644 {
645         return irg->last_node_idx;
646 }
647
648 void add_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
649 {
650         irg->constraints |= constraints;
651 }
652
653 void clear_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
654 {
655         irg->constraints &= ~constraints;
656 }
657
658 int (irg_is_constrained)(const ir_graph *irg, ir_graph_constraints_t constraints)
659 {
660         return irg_is_constrained_(irg, constraints);
661 }
662
663 void (add_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
664 {
665         add_irg_properties_(irg, props);
666 }
667
668 void (clear_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
669 {
670         clear_irg_properties_(irg, props);
671 }
672
673 int (irg_has_properties)(const ir_graph *irg, ir_graph_properties_t props)
674 {
675         return irg_has_properties_(irg, props);
676 }
677
678 typedef void (*assure_property_func)(ir_graph *irg);
679
680 void assure_irg_properties(ir_graph *irg, ir_graph_properties_t props)
681 {
682         static struct {
683                 ir_graph_properties_t property;
684                 assure_property_func  func;
685         } property_functions[] = {
686                 { IR_GRAPH_PROPERTY_ONE_RETURN,               normalize_one_return },
687                 { IR_GRAPH_PROPERTY_MANY_RETURNS,             normalize_n_returns },
688                 { IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES,        remove_critical_cf_edges },
689                 { IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE,      remove_unreachable_code },
690                 { IR_GRAPH_PROPERTY_NO_BADS,                  remove_bads },
691                 { IR_GRAPH_PROPERTY_NO_TUPLES,                remove_tuples },
692                 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE,     assure_doms },
693                 { IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE, assure_postdoms },
694                 { IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES,     assure_edges },
695                 { IR_GRAPH_PROPERTY_CONSISTENT_OUTS,          assure_irg_outs },
696                 { IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO,      assure_loopinfo },
697                 { IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE,  assure_irg_entity_usage_computed },
698                 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS, ir_compute_dominance_frontiers },
699         };
700         size_t i;
701         for (i = 0; i < ARRAY_SIZE(property_functions); ++i) {
702                 ir_graph_properties_t missing = props & ~irg->properties;
703                 if (missing & property_functions[i].property)
704                         property_functions[i].func(irg);
705         }
706         assert((props & ~irg->properties) == IR_GRAPH_PROPERTIES_NONE);
707 }
708
709 void confirm_irg_properties(ir_graph *irg, ir_graph_properties_t props)
710 {
711         clear_irg_properties(irg, ~props);
712         if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES))
713                 edges_deactivate(irg);
714         if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUTS)
715             && (irg->properties & IR_GRAPH_PROPERTY_CONSISTENT_OUTS))
716             free_irg_outs(irg);
717         if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS))
718                 ir_free_dominance_frontiers(irg);
719 }