2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Entry point to the representation of procedure code.
9 * @author Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Michael Beck
18 #include "irgraph_t.h"
20 #include "irgraph_t.h"
31 #include "irbackedge_t.h"
32 #include "iredges_t.h"
35 #include "iroptimize.h"
38 #define INITIAL_IDX_IRN_MAP_SIZE 1024
39 /** Suffix that is added to every frame type. */
40 #define FRAME_TP_SUFFIX "frame_tp"
42 ir_graph *current_ir_graph;
43 ir_graph *get_current_ir_graph(void)
45 return current_ir_graph;
48 void set_current_ir_graph(ir_graph *graph)
50 current_ir_graph = graph;
53 /** contains the suffix for frame type names */
54 static ident *frame_type_suffix = NULL;
56 void firm_init_irgraph(void)
58 frame_type_suffix = new_id_from_str(FRAME_TP_SUFFIX);
62 * Allocate a new IR graph.
63 * This function respects the registered graph data. The only reason for
64 * this function is, that there are two locations, where graphs are
65 * allocated (new_r_ir_graph, new_const_code_irg).
66 * @return Memory for a new graph.
68 static ir_graph *alloc_graph(void)
70 ir_graph *const res = XMALLOCZ(ir_graph);
71 res->kind = k_ir_graph;
73 /* initialize the idx->node map. */
74 res->idx_irn_map = NEW_ARR_FZ(ir_node*, INITIAL_IDX_IRN_MAP_SIZE);
76 obstack_init(&res->obst);
78 /* value table for global value numbering for optimizing use in iropt.c */
85 * Frees an allocated IR graph
87 static void free_graph(ir_graph *irg)
89 for (ir_edge_kind_t i = EDGE_KIND_FIRST; i < EDGE_KIND_LAST; ++i)
90 edges_deactivate_kind(irg, i);
91 DEL_ARR_F(irg->idx_irn_map);
95 void irg_set_nloc(ir_graph *res, int n_loc)
97 assert(irg_is_constrained(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION));
99 res->n_loc = n_loc + 1; /* number of local variables that are never
100 dereferenced in this graph plus one for
101 the store. This is not the number of
102 parameters to the procedure! */
104 if (res->loc_descriptions) {
105 xfree(res->loc_descriptions);
106 res->loc_descriptions = NULL;
110 ir_graph *new_r_ir_graph(ir_entity *ent, int n_loc)
113 ir_node *first_block;
114 ir_node *start, *start_block, *initial_mem, *projX;
118 /* inform statistics here, as blocks will be already build on this graph */
119 hook_new_graph(res, ent);
121 /* graphs are in construction mode by default */
122 add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
123 irg_set_nloc(res, n_loc);
125 res->irg_pinned_state = op_pin_state_pinned;
126 res->typeinfo_state = ir_typeinfo_none;
127 set_irp_typeinfo_inconsistent(); /* there is a new graph with typeinfo_none. */
128 res->callee_info_state = irg_callee_info_none;
129 res->fp_model = fp_model_precise;
130 res->mem_disambig_opt = aa_opt_inherited;
132 /*-- Type information for the procedure of the graph --*/
134 set_entity_irg(ent, res);
136 /*-- a class type so that it can contain "inner" methods as in Pascal. --*/
137 res->frame_type = new_type_frame();
139 /* the Anchor node must be created first */
140 res->anchor = new_r_Anchor(res);
142 /*-- Nodes needed in every graph --*/
143 set_irg_end_block(res, new_r_immBlock(res));
144 set_irg_end(res, new_r_End(res, 0, NULL));
146 start_block = new_r_Block_noopt(res, 0, NULL);
147 set_irg_start_block(res, start_block);
148 set_irg_no_mem (res, new_r_NoMem(res));
149 start = new_r_Start(res);
150 set_irg_start (res, start);
152 /* Proj results of start node */
153 projX = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
154 set_irg_initial_exec (res, projX);
155 set_irg_frame (res, new_r_Proj(start, mode_P_data, pn_Start_P_frame_base));
156 set_irg_args (res, new_r_Proj(start, mode_T, pn_Start_T_args));
157 initial_mem = new_r_Proj(start, mode_M, pn_Start_M);
158 set_irg_initial_mem(res, initial_mem);
160 res->index = get_irp_new_irg_idx();
162 res->graph_nr = get_irp_new_node_nr();
165 set_r_cur_block(res, start_block);
166 set_r_store(res, initial_mem);
168 /*-- Make a block to start with --*/
169 first_block = new_r_Block(res, 1, &projX);
170 set_r_cur_block(res, first_block);
172 res->method_execution_frequency = -1.0;
177 ir_graph *new_ir_graph(ir_entity *ent, int n_loc)
179 ir_graph *res = new_r_ir_graph(ent, n_loc);
180 add_irp_irg(res); /* remember this graph global. */
184 ir_graph *new_const_code_irg(void)
186 ir_graph *res = alloc_graph();
192 ir_node *start_block;
195 /* inform statistics here, as blocks will be already build on this graph */
196 hook_new_graph(res, NULL);
198 res->n_loc = 1; /* Only the memory. */
199 res->irg_pinned_state = op_pin_state_pinned;
200 res->fp_model = fp_model_precise;
202 add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
204 /* the Anchor node must be created first */
205 res->anchor = new_r_Anchor(res);
207 /* -- The end block -- */
208 end_block = new_r_Block_noopt(res, 0, NULL);
209 set_irg_end_block(res, end_block);
210 end = new_r_End(res, 0, NULL);
211 set_irg_end(res, end);
213 /* -- The start block -- */
214 start_block = new_r_Block_noopt(res, 0, NULL);
215 set_irg_start_block(res, start_block);
216 no_mem = new_r_NoMem(res);
217 set_irg_no_mem(res, no_mem);
218 start = new_r_Start(res);
219 set_irg_start(res, start);
221 /* Proj results of start node */
222 set_irg_initial_mem(res, new_r_Proj(start, mode_M, pn_Start_M));
223 projX = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
225 body_block = new_r_Block(res, 1, &projX);
227 set_r_cur_block(res, body_block);
229 /* Set the visited flag high enough that the blocks will never be visited. */
230 set_irn_visited(body_block, -1);
231 set_Block_block_visited(body_block, -1);
232 set_Block_block_visited(start_block, -1);
233 set_irn_visited(start_block, -1);
239 * Pre-Walker: Copies blocks and nodes from the original method graph
240 * to the copied graph.
242 * @param n A node from the original method graph.
243 * @param env The copied graph.
245 static void copy_all_nodes(ir_node *node, void *env)
247 ir_graph *irg = (ir_graph*)env;
248 ir_node *new_node = irn_copy_into_irg(node, irg);
250 set_irn_link(node, new_node);
252 /* fix access to entities on the stack frame */
253 if (is_Sel(new_node)) {
254 ir_entity *ent = get_Sel_entity(new_node);
255 ir_type *tp = get_entity_owner(ent);
257 if (is_frame_type(tp)) {
258 /* replace by the copied entity */
259 ent = (ir_entity*)get_entity_link(ent);
261 assert(is_entity(ent));
262 assert(get_entity_owner(ent) == get_irg_frame_type(irg));
263 set_Sel_entity(new_node, ent);
269 * Post-walker: Set the predecessors of the copied nodes.
270 * The copied nodes are set as link of their original nodes. The links of
271 * "irn" predecessors are the predecessors of copied node.
273 static void rewire(ir_node *irn, void *env)
276 irn_rewire_inputs(irn);
279 static ir_node *get_new_node(const ir_node *old_node)
281 return (ir_node*) get_irn_link(old_node);
284 ir_graph *create_irg_copy(ir_graph *irg)
290 res->irg_pinned_state = irg->irg_pinned_state;
291 res->fp_model = irg->fp_model;
293 /* clone the frame type here for safety */
294 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
295 res->frame_type = clone_frame_type(irg->frame_type);
297 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
299 /* copy all nodes from the graph irg to the new graph res */
300 irg_walk_anchors(irg, copy_all_nodes, rewire, res);
302 /* copy the Anchor node */
303 res->anchor = get_new_node(irg->anchor);
305 /* -- The end block -- */
306 set_irg_end_block (res, get_new_node(get_irg_end_block(irg)));
307 set_irg_end (res, get_new_node(get_irg_end(irg)));
309 /* -- The start block -- */
310 set_irg_start_block(res, get_new_node(get_irg_start_block(irg)));
311 set_irg_no_mem (res, get_new_node(get_irg_no_mem(irg)));
312 set_irg_start (res, get_new_node(get_irg_start(irg)));
314 /* Proj results of start node */
315 set_irg_initial_mem(res, get_new_node(get_irg_initial_mem(irg)));
317 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
318 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
323 void free_ir_graph(ir_graph *irg)
325 assert(is_ir_graph(irg));
328 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
330 hook_free_graph(irg);
334 set_entity_irg(irg->ent, NULL); /* not set in const code irg */
337 free_End(get_irg_end(irg));
338 obstack_free(&irg->obst, NULL);
339 if (irg->loc_descriptions)
340 free(irg->loc_descriptions);
345 int (is_ir_graph)(const void *thing)
347 return is_ir_graph_(thing);
351 long get_irg_graph_nr(const ir_graph *irg)
353 return irg->graph_nr;
356 long get_irg_graph_nr(const ir_graph *irg)
358 return PTR_TO_INT(irg);
362 size_t get_irg_idx(const ir_graph *irg)
367 ir_node *(get_idx_irn)(const ir_graph *irg, unsigned idx)
369 return get_idx_irn_(irg, idx);
372 ir_node *(get_irg_start_block)(const ir_graph *irg)
374 return get_irg_start_block_(irg);
377 void (set_irg_start_block)(ir_graph *irg, ir_node *node)
379 set_irg_start_block_(irg, node);
382 ir_node *(get_irg_start)(const ir_graph *irg)
384 return get_irg_start_(irg);
387 void (set_irg_start)(ir_graph *irg, ir_node *node)
389 set_irg_start_(irg, node);
392 ir_node *(get_irg_end_block)(const ir_graph *irg)
394 return get_irg_end_block_(irg);
397 void (set_irg_end_block)(ir_graph *irg, ir_node *node)
399 set_irg_end_block_(irg, node);
402 ir_node *(get_irg_end)(const ir_graph *irg)
404 return get_irg_end_(irg);
407 void (set_irg_end)(ir_graph *irg, ir_node *node)
409 set_irg_end_(irg, node);
412 ir_node *(get_irg_initial_exec)(const ir_graph *irg)
414 return get_irg_initial_exec_(irg);
417 void (set_irg_initial_exec)(ir_graph *irg, ir_node *node)
419 set_irg_initial_exec_(irg, node);
422 ir_node *(get_irg_frame)(const ir_graph *irg)
424 return get_irg_frame_(irg);
427 void (set_irg_frame)(ir_graph *irg, ir_node *node)
429 set_irg_frame_(irg, node);
432 ir_node *(get_irg_initial_mem)(const ir_graph *irg)
434 return get_irg_initial_mem_(irg);
437 void (set_irg_initial_mem)(ir_graph *irg, ir_node *node)
439 set_irg_initial_mem_(irg, node);
442 ir_node *(get_irg_args)(const ir_graph *irg)
444 return get_irg_args_(irg);
447 void (set_irg_args)(ir_graph *irg, ir_node *node)
449 set_irg_args_(irg, node);
452 ir_node *(get_irg_no_mem)(const ir_graph *irg)
454 return get_irg_no_mem_(irg);
457 void (set_irg_no_mem)(ir_graph *irg, ir_node *node)
459 set_irg_no_mem_(irg, node);
462 ir_entity *(get_irg_entity)(const ir_graph *irg)
464 return get_irg_entity_(irg);
467 void (set_irg_entity)(ir_graph *irg, ir_entity *ent)
469 set_irg_entity_(irg, ent);
472 ir_type *(get_irg_frame_type)(ir_graph *irg)
474 return get_irg_frame_type_(irg);
477 void (set_irg_frame_type)(ir_graph *irg, ir_type *ftp)
479 set_irg_frame_type_(irg, ftp);
482 int get_irg_n_locs(ir_graph *irg)
484 return irg->n_loc - 1;
487 int node_is_in_irgs_storage(const ir_graph *irg, const ir_node *n)
489 /* Check whether the ir_node pointer is on the obstack.
490 * A more sophisticated check would test the "whole" ir_node. */
491 for (struct _obstack_chunk const *p = irg->obst.chunk; p; p = p->prev) {
492 if (((char *)p->contents <= (char *)n) && ((char *)n < (char *)p->limit))
499 op_pin_state (get_irg_pinned)(const ir_graph *irg)
501 return get_irg_pinned_(irg);
504 irg_callee_info_state (get_irg_callee_info_state)(const ir_graph *irg)
506 return get_irg_callee_info_state_(irg);
509 void (set_irg_callee_info_state)(ir_graph *irg, irg_callee_info_state s)
511 set_irg_callee_info_state_(irg, s);
514 void (set_irg_link)(ir_graph *irg, void *thing)
516 set_irg_link_(irg, thing);
519 void *(get_irg_link)(const ir_graph *irg)
521 return get_irg_link_(irg);
524 ir_visited_t (get_irg_visited)(const ir_graph *irg)
526 return get_irg_visited_(irg);
529 /** maximum visited flag content of all ir_graph visited fields. */
530 static ir_visited_t max_irg_visited = 0;
532 void set_irg_visited(ir_graph *irg, ir_visited_t visited)
534 irg->visited = visited;
535 if (irg->visited > max_irg_visited) {
536 max_irg_visited = irg->visited;
540 void inc_irg_visited(ir_graph *irg)
543 if (irg->visited > max_irg_visited) {
544 max_irg_visited = irg->visited;
548 ir_visited_t get_max_irg_visited(void)
550 return max_irg_visited;
553 void set_max_irg_visited(int val)
555 max_irg_visited = val;
558 ir_visited_t inc_max_irg_visited(void)
562 for (i = 0; i < get_irp_n_irgs(); i++)
563 assert(max_irg_visited >= get_irg_visited(get_irp_irg(i)));
565 return ++max_irg_visited;
568 ir_visited_t (get_irg_block_visited)(const ir_graph *irg)
570 return get_irg_block_visited_(irg);
573 void (set_irg_block_visited)(ir_graph *irg, ir_visited_t visited)
575 set_irg_block_visited_(irg, visited);
578 void (inc_irg_block_visited)(ir_graph *irg)
580 inc_irg_block_visited_(irg);
583 unsigned (get_irg_fp_model)(const ir_graph *irg)
585 return get_irg_fp_model_(irg);
588 void set_irg_fp_model(ir_graph *irg, unsigned model)
590 irg->fp_model = model;
593 void set_irg_loc_description(ir_graph *irg, int n, void *description)
595 assert(0 <= n && n < irg->n_loc);
597 if (! irg->loc_descriptions)
598 irg->loc_descriptions = XMALLOCNZ(void*, irg->n_loc);
600 irg->loc_descriptions[n] = description;
603 void *get_irg_loc_description(ir_graph *irg, int n)
605 assert(0 <= n && n < irg->n_loc);
606 return irg->loc_descriptions ? irg->loc_descriptions[n] : NULL;
610 void ir_reserve_resources(ir_graph *irg, ir_resources_t resources)
612 assert((irg->reserved_resources & resources) == 0);
613 irg->reserved_resources |= resources;
616 void ir_free_resources(ir_graph *irg, ir_resources_t resources)
618 assert((irg->reserved_resources & resources) == resources);
619 irg->reserved_resources &= ~resources;
622 ir_resources_t ir_resources_reserved(const ir_graph *irg)
624 return irg->reserved_resources;
628 unsigned get_irg_last_idx(const ir_graph *irg)
630 return irg->last_node_idx;
633 void add_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
635 irg->constraints |= constraints;
638 void clear_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
640 irg->constraints &= ~constraints;
643 int (irg_is_constrained)(const ir_graph *irg, ir_graph_constraints_t constraints)
645 return irg_is_constrained_(irg, constraints);
648 void (add_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
650 add_irg_properties_(irg, props);
653 void (clear_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
655 clear_irg_properties_(irg, props);
658 int (irg_has_properties)(const ir_graph *irg, ir_graph_properties_t props)
660 return irg_has_properties_(irg, props);
663 typedef void (*assure_property_func)(ir_graph *irg);
665 void assure_irg_properties(ir_graph *irg, ir_graph_properties_t props)
668 ir_graph_properties_t property;
669 assure_property_func func;
670 } property_functions[] = {
671 { IR_GRAPH_PROPERTY_ONE_RETURN, normalize_one_return },
672 { IR_GRAPH_PROPERTY_MANY_RETURNS, normalize_n_returns },
673 { IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES, remove_critical_cf_edges },
674 { IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE, remove_unreachable_code },
675 { IR_GRAPH_PROPERTY_NO_BADS, remove_bads },
676 { IR_GRAPH_PROPERTY_NO_TUPLES, remove_tuples },
677 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE, assure_doms },
678 { IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE, assure_postdoms },
679 { IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES, assure_edges },
680 { IR_GRAPH_PROPERTY_CONSISTENT_OUTS, assure_irg_outs },
681 { IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO, assure_loopinfo },
682 { IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE, assure_irg_entity_usage_computed },
683 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS, ir_compute_dominance_frontiers },
686 for (i = 0; i < ARRAY_SIZE(property_functions); ++i) {
687 ir_graph_properties_t missing = props & ~irg->properties;
688 if (missing & property_functions[i].property)
689 property_functions[i].func(irg);
691 assert((props & ~irg->properties) == IR_GRAPH_PROPERTIES_NONE);
694 void confirm_irg_properties(ir_graph *irg, ir_graph_properties_t props)
696 clear_irg_properties(irg, ~props);
697 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES))
698 edges_deactivate(irg);
699 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUTS)
700 && (irg->properties & IR_GRAPH_PROPERTY_CONSISTENT_OUTS))
702 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS))
703 ir_free_dominance_frontiers(irg);