2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Entry point to the representation of procedure code.
23 * @author Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Michael Beck
32 #include "irgraph_t.h"
34 #include "irgraph_t.h"
45 #include "irbackedge_t.h"
46 #include "iredges_t.h"
49 #include "iroptimize.h"
52 #define INITIAL_IDX_IRN_MAP_SIZE 1024
53 /** Suffix that is added to every frame type. */
54 #define FRAME_TP_SUFFIX "frame_tp"
56 ir_graph *current_ir_graph;
57 ir_graph *get_current_ir_graph(void)
59 return current_ir_graph;
62 void set_current_ir_graph(ir_graph *graph)
64 current_ir_graph = graph;
67 /** contains the suffix for frame type names */
68 static ident *frame_type_suffix = NULL;
70 void firm_init_irgraph(void)
72 frame_type_suffix = new_id_from_str(FRAME_TP_SUFFIX);
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.
82 static ir_graph *alloc_graph(void)
84 ir_graph *const res = XMALLOCZ(ir_graph);
85 res->kind = k_ir_graph;
87 /* initialize the idx->node map. */
88 res->idx_irn_map = NEW_ARR_FZ(ir_node*, INITIAL_IDX_IRN_MAP_SIZE);
90 obstack_init(&res->obst);
92 /* value table for global value numbering for optimizing use in iropt.c */
99 * Frees an allocated IR graph
101 static void free_graph(ir_graph *irg)
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);
109 void irg_set_nloc(ir_graph *res, int n_loc)
111 assert(irg_is_constrained(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION));
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! */
118 if (res->loc_descriptions) {
119 xfree(res->loc_descriptions);
120 res->loc_descriptions = NULL;
124 ir_graph *new_r_ir_graph(ir_entity *ent, int n_loc)
127 ir_node *first_block;
128 ir_node *start, *start_block, *initial_mem, *projX;
132 /* inform statistics here, as blocks will be already build on this graph */
133 hook_new_graph(res, ent);
135 /* graphs are in construction mode by default */
136 add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
137 irg_set_nloc(res, n_loc);
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->fp_model = fp_model_precise;
144 res->mem_disambig_opt = aa_opt_inherited;
146 /*-- Type information for the procedure of the graph --*/
148 set_entity_irg(ent, res);
150 /*-- a class type so that it can contain "inner" methods as in Pascal. --*/
151 res->frame_type = new_type_frame();
153 /* the Anchor node must be created first */
154 res->anchor = new_r_Anchor(res);
156 /*-- Nodes needed in every graph --*/
157 set_irg_end_block(res, new_r_immBlock(res));
158 set_irg_end(res, new_r_End(res, 0, NULL));
160 start_block = new_r_Block_noopt(res, 0, NULL);
161 set_irg_start_block(res, start_block);
162 set_irg_no_mem (res, new_r_NoMem(res));
163 start = new_r_Start(res);
164 set_irg_start (res, start);
166 /* Proj results of start node */
167 projX = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
168 set_irg_initial_exec (res, projX);
169 set_irg_frame (res, new_r_Proj(start, mode_P_data, pn_Start_P_frame_base));
170 set_irg_args (res, new_r_Proj(start, mode_T, pn_Start_T_args));
171 initial_mem = new_r_Proj(start, mode_M, pn_Start_M);
172 set_irg_initial_mem(res, initial_mem);
174 res->index = get_irp_new_irg_idx();
176 res->graph_nr = get_irp_new_node_nr();
179 set_r_cur_block(res, start_block);
180 set_r_store(res, initial_mem);
182 /*-- Make a block to start with --*/
183 first_block = new_r_Block(res, 1, &projX);
184 set_r_cur_block(res, first_block);
186 res->method_execution_frequency = -1.0;
191 ir_graph *new_ir_graph(ir_entity *ent, int n_loc)
193 ir_graph *res = new_r_ir_graph(ent, n_loc);
194 add_irp_irg(res); /* remember this graph global. */
198 ir_graph *new_const_code_irg(void)
200 ir_graph *res = alloc_graph();
206 ir_node *start_block;
209 /* inform statistics here, as blocks will be already build on this graph */
210 hook_new_graph(res, NULL);
212 res->n_loc = 1; /* Only the memory. */
213 res->irg_pinned_state = op_pin_state_pinned;
214 res->fp_model = fp_model_precise;
216 add_irg_constraints(res, IR_GRAPH_CONSTRAINT_CONSTRUCTION);
218 /* the Anchor node must be created first */
219 res->anchor = new_r_Anchor(res);
221 /* -- The end block -- */
222 end_block = new_r_Block_noopt(res, 0, NULL);
223 set_irg_end_block(res, end_block);
224 end = new_r_End(res, 0, NULL);
225 set_irg_end(res, end);
227 /* -- The start block -- */
228 start_block = new_r_Block_noopt(res, 0, NULL);
229 set_irg_start_block(res, start_block);
230 no_mem = new_r_NoMem(res);
231 set_irg_no_mem(res, no_mem);
232 start = new_r_Start(res);
233 set_irg_start(res, start);
235 /* Proj results of start node */
236 set_irg_initial_mem(res, new_r_Proj(start, mode_M, pn_Start_M));
237 projX = new_r_Proj(start, mode_X, pn_Start_X_initial_exec);
239 body_block = new_r_Block(res, 1, &projX);
241 set_r_cur_block(res, body_block);
243 /* Set the visited flag high enough that the blocks will never be visited. */
244 set_irn_visited(body_block, -1);
245 set_Block_block_visited(body_block, -1);
246 set_Block_block_visited(start_block, -1);
247 set_irn_visited(start_block, -1);
253 * Pre-Walker: Copies blocks and nodes from the original method graph
254 * to the copied graph.
256 * @param n A node from the original method graph.
257 * @param env The copied graph.
259 static void copy_all_nodes(ir_node *node, void *env)
261 ir_graph *irg = (ir_graph*)env;
262 ir_node *new_node = irn_copy_into_irg(node, irg);
264 set_irn_link(node, new_node);
266 /* fix access to entities on the stack frame */
267 if (is_Sel(new_node)) {
268 ir_entity *ent = get_Sel_entity(new_node);
269 ir_type *tp = get_entity_owner(ent);
271 if (is_frame_type(tp)) {
272 /* replace by the copied entity */
273 ent = (ir_entity*)get_entity_link(ent);
275 assert(is_entity(ent));
276 assert(get_entity_owner(ent) == get_irg_frame_type(irg));
277 set_Sel_entity(new_node, ent);
283 * Post-walker: Set the predecessors of the copied nodes.
284 * The copied nodes are set as link of their original nodes. The links of
285 * "irn" predecessors are the predecessors of copied node.
287 static void rewire(ir_node *irn, void *env)
290 irn_rewire_inputs(irn);
293 static ir_node *get_new_node(const ir_node *old_node)
295 return (ir_node*) get_irn_link(old_node);
298 ir_graph *create_irg_copy(ir_graph *irg)
304 res->irg_pinned_state = irg->irg_pinned_state;
305 res->fp_model = irg->fp_model;
307 /* clone the frame type here for safety */
308 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
309 res->frame_type = clone_frame_type(irg->frame_type);
311 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
313 /* copy all nodes from the graph irg to the new graph res */
314 irg_walk_anchors(irg, copy_all_nodes, rewire, res);
316 /* copy the Anchor node */
317 res->anchor = get_new_node(irg->anchor);
319 /* -- The end block -- */
320 set_irg_end_block (res, get_new_node(get_irg_end_block(irg)));
321 set_irg_end (res, get_new_node(get_irg_end(irg)));
323 /* -- The start block -- */
324 set_irg_start_block(res, get_new_node(get_irg_start_block(irg)));
325 set_irg_no_mem (res, get_new_node(get_irg_no_mem(irg)));
326 set_irg_start (res, get_new_node(get_irg_start(irg)));
328 /* Proj results of start node */
329 set_irg_initial_mem(res, get_new_node(get_irg_initial_mem(irg)));
331 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
332 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
337 void free_ir_graph(ir_graph *irg)
339 assert(is_ir_graph(irg));
342 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
344 hook_free_graph(irg);
348 set_entity_irg(irg->ent, NULL); /* not set in const code irg */
351 free_End(get_irg_end(irg));
352 obstack_free(&irg->obst, NULL);
353 if (irg->loc_descriptions)
354 free(irg->loc_descriptions);
359 int (is_ir_graph)(const void *thing)
361 return is_ir_graph_(thing);
365 long get_irg_graph_nr(const ir_graph *irg)
367 return irg->graph_nr;
370 long get_irg_graph_nr(const ir_graph *irg)
372 return PTR_TO_INT(irg);
376 size_t get_irg_idx(const ir_graph *irg)
381 ir_node *(get_idx_irn)(const ir_graph *irg, unsigned idx)
383 return get_idx_irn_(irg, idx);
386 ir_node *(get_irg_start_block)(const ir_graph *irg)
388 return get_irg_start_block_(irg);
391 void (set_irg_start_block)(ir_graph *irg, ir_node *node)
393 set_irg_start_block_(irg, node);
396 ir_node *(get_irg_start)(const ir_graph *irg)
398 return get_irg_start_(irg);
401 void (set_irg_start)(ir_graph *irg, ir_node *node)
403 set_irg_start_(irg, node);
406 ir_node *(get_irg_end_block)(const ir_graph *irg)
408 return get_irg_end_block_(irg);
411 void (set_irg_end_block)(ir_graph *irg, ir_node *node)
413 set_irg_end_block_(irg, node);
416 ir_node *(get_irg_end)(const ir_graph *irg)
418 return get_irg_end_(irg);
421 void (set_irg_end)(ir_graph *irg, ir_node *node)
423 set_irg_end_(irg, node);
426 ir_node *(get_irg_initial_exec)(const ir_graph *irg)
428 return get_irg_initial_exec_(irg);
431 void (set_irg_initial_exec)(ir_graph *irg, ir_node *node)
433 set_irg_initial_exec_(irg, node);
436 ir_node *(get_irg_frame)(const ir_graph *irg)
438 return get_irg_frame_(irg);
441 void (set_irg_frame)(ir_graph *irg, ir_node *node)
443 set_irg_frame_(irg, node);
446 ir_node *(get_irg_initial_mem)(const ir_graph *irg)
448 return get_irg_initial_mem_(irg);
451 void (set_irg_initial_mem)(ir_graph *irg, ir_node *node)
453 set_irg_initial_mem_(irg, node);
456 ir_node *(get_irg_args)(const ir_graph *irg)
458 return get_irg_args_(irg);
461 void (set_irg_args)(ir_graph *irg, ir_node *node)
463 set_irg_args_(irg, node);
466 ir_node *(get_irg_no_mem)(const ir_graph *irg)
468 return get_irg_no_mem_(irg);
471 void (set_irg_no_mem)(ir_graph *irg, ir_node *node)
473 set_irg_no_mem_(irg, node);
476 ir_entity *(get_irg_entity)(const ir_graph *irg)
478 return get_irg_entity_(irg);
481 void (set_irg_entity)(ir_graph *irg, ir_entity *ent)
483 set_irg_entity_(irg, ent);
486 ir_type *(get_irg_frame_type)(ir_graph *irg)
488 return get_irg_frame_type_(irg);
491 void (set_irg_frame_type)(ir_graph *irg, ir_type *ftp)
493 set_irg_frame_type_(irg, ftp);
496 int get_irg_n_locs(ir_graph *irg)
498 return irg->n_loc - 1;
501 int node_is_in_irgs_storage(const ir_graph *irg, const ir_node *n)
503 /* Check whether the ir_node pointer is on the obstack.
504 * A more sophisticated check would test the "whole" ir_node. */
505 for (struct _obstack_chunk const *p = irg->obst.chunk; p; p = p->prev) {
506 if (((char *)p->contents <= (char *)n) && ((char *)n < (char *)p->limit))
513 op_pin_state (get_irg_pinned)(const ir_graph *irg)
515 return get_irg_pinned_(irg);
518 irg_callee_info_state (get_irg_callee_info_state)(const ir_graph *irg)
520 return get_irg_callee_info_state_(irg);
523 void (set_irg_callee_info_state)(ir_graph *irg, irg_callee_info_state s)
525 set_irg_callee_info_state_(irg, s);
528 void (set_irg_link)(ir_graph *irg, void *thing)
530 set_irg_link_(irg, thing);
533 void *(get_irg_link)(const ir_graph *irg)
535 return get_irg_link_(irg);
538 ir_visited_t (get_irg_visited)(const ir_graph *irg)
540 return get_irg_visited_(irg);
543 /** maximum visited flag content of all ir_graph visited fields. */
544 static ir_visited_t max_irg_visited = 0;
546 void set_irg_visited(ir_graph *irg, ir_visited_t visited)
548 irg->visited = visited;
549 if (irg->visited > max_irg_visited) {
550 max_irg_visited = irg->visited;
554 void inc_irg_visited(ir_graph *irg)
557 if (irg->visited > max_irg_visited) {
558 max_irg_visited = irg->visited;
562 ir_visited_t get_max_irg_visited(void)
564 return max_irg_visited;
567 void set_max_irg_visited(int val)
569 max_irg_visited = val;
572 ir_visited_t inc_max_irg_visited(void)
576 for (i = 0; i < get_irp_n_irgs(); i++)
577 assert(max_irg_visited >= get_irg_visited(get_irp_irg(i)));
579 return ++max_irg_visited;
582 ir_visited_t (get_irg_block_visited)(const ir_graph *irg)
584 return get_irg_block_visited_(irg);
587 void (set_irg_block_visited)(ir_graph *irg, ir_visited_t visited)
589 set_irg_block_visited_(irg, visited);
592 void (inc_irg_block_visited)(ir_graph *irg)
594 inc_irg_block_visited_(irg);
597 unsigned (get_irg_fp_model)(const ir_graph *irg)
599 return get_irg_fp_model_(irg);
602 void set_irg_fp_model(ir_graph *irg, unsigned model)
604 irg->fp_model = model;
607 void set_irg_loc_description(ir_graph *irg, int n, void *description)
609 assert(0 <= n && n < irg->n_loc);
611 if (! irg->loc_descriptions)
612 irg->loc_descriptions = XMALLOCNZ(void*, irg->n_loc);
614 irg->loc_descriptions[n] = description;
617 void *get_irg_loc_description(ir_graph *irg, int n)
619 assert(0 <= n && n < irg->n_loc);
620 return irg->loc_descriptions ? irg->loc_descriptions[n] : NULL;
624 void ir_reserve_resources(ir_graph *irg, ir_resources_t resources)
626 assert((irg->reserved_resources & resources) == 0);
627 irg->reserved_resources |= resources;
630 void ir_free_resources(ir_graph *irg, ir_resources_t resources)
632 assert((irg->reserved_resources & resources) == resources);
633 irg->reserved_resources &= ~resources;
636 ir_resources_t ir_resources_reserved(const ir_graph *irg)
638 return irg->reserved_resources;
642 unsigned get_irg_last_idx(const ir_graph *irg)
644 return irg->last_node_idx;
647 void add_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
649 irg->constraints |= constraints;
652 void clear_irg_constraints(ir_graph *irg, ir_graph_constraints_t constraints)
654 irg->constraints &= ~constraints;
657 int (irg_is_constrained)(const ir_graph *irg, ir_graph_constraints_t constraints)
659 return irg_is_constrained_(irg, constraints);
662 void (add_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
664 add_irg_properties_(irg, props);
667 void (clear_irg_properties)(ir_graph *irg, ir_graph_properties_t props)
669 clear_irg_properties_(irg, props);
672 int (irg_has_properties)(const ir_graph *irg, ir_graph_properties_t props)
674 return irg_has_properties_(irg, props);
677 typedef void (*assure_property_func)(ir_graph *irg);
679 void assure_irg_properties(ir_graph *irg, ir_graph_properties_t props)
682 ir_graph_properties_t property;
683 assure_property_func func;
684 } property_functions[] = {
685 { IR_GRAPH_PROPERTY_ONE_RETURN, normalize_one_return },
686 { IR_GRAPH_PROPERTY_MANY_RETURNS, normalize_n_returns },
687 { IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES, remove_critical_cf_edges },
688 { IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE, remove_unreachable_code },
689 { IR_GRAPH_PROPERTY_NO_BADS, remove_bads },
690 { IR_GRAPH_PROPERTY_NO_TUPLES, remove_tuples },
691 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE, assure_doms },
692 { IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE, assure_postdoms },
693 { IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES, assure_edges },
694 { IR_GRAPH_PROPERTY_CONSISTENT_OUTS, assure_irg_outs },
695 { IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO, assure_loopinfo },
696 { IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE, assure_irg_entity_usage_computed },
697 { IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS, ir_compute_dominance_frontiers },
700 for (i = 0; i < ARRAY_SIZE(property_functions); ++i) {
701 ir_graph_properties_t missing = props & ~irg->properties;
702 if (missing & property_functions[i].property)
703 property_functions[i].func(irg);
705 assert((props & ~irg->properties) == IR_GRAPH_PROPERTIES_NONE);
708 void confirm_irg_properties(ir_graph *irg, ir_graph_properties_t props)
710 clear_irg_properties(irg, ~props);
711 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES))
712 edges_deactivate(irg);
713 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_OUTS)
714 && (irg->properties & IR_GRAPH_PROPERTY_CONSISTENT_OUTS))
716 if (! (props & IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE_FRONTIERS))
717 ir_free_dominance_frontiers(irg);