4 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
6 * This file is part of libFirm.
8 * This file may be distributed and/or modified under the terms of the
9 * GNU General Public License version 2 as published by the Free Software
10 * Foundation and appearing in the file LICENSE.GPL included in the
11 * packaging of this file.
13 * Licensees holding valid libFirm Professional Edition licenses may use
14 * this file in accordance with the libFirm Commercial License.
15 * Agreement provided with the Software.
17 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
18 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * @brief Main Implementation of PTO
26 * @date Sat Nov 13 19:35:27 CET 2004
34 pto_comp: Main Implementation of PTO
37 # include <string.h> /* for memset */
39 # include "pto_comp.h"
40 # include "pto_util.h"
41 # include "pto_name.h"
45 # include "irnode_t.h"
46 # include "irprog_t.h"
48 # include "irmemwalk.h"
50 # include "pto_debug.h"
51 # include "pto_init.h"
59 /* Local Data Types: */
60 typedef struct pto_env_str {
61 struct pto_env_str *enc_env;
68 /* Local Variables: */
73 /* Local Prototypes: */
74 static pto_t *get_pto (ir_node*, pto_env_t*);
75 static void pto_call (ir_graph*, ir_node*, pto_env_t*);
76 static void pto_raise (ir_node*, pto_env_t*);
77 static void pto_load (ir_node*, pto_env_t*);
78 static void pto_store (ir_node*, pto_env_t*);
79 static void pto_method (ir_node*, pto_env_t*);
80 static void pto_end_block (ir_node*, pto_env_t*);
82 /* ===================================================
84 =================================================== */
85 /* Add values of the actual arguments to the formal arguments */
86 static int add_graph_args (ir_graph *graph, ir_node *call, pto_env_t *env)
89 ir_type *meth = get_entity_type (get_irg_entity (graph));
90 ir_node **args = get_irg_proj_args (graph);
93 assert(op_Call == get_irn_op(call));
95 n_args = get_Call_n_params (call);
97 DBGPRINT (1, (stdout, "%s: args of %s[%li] -> 0x%08x\n",
99 OPNAME (call), OPNUM (call), (int) graph));
101 for (i = 0; i < n_args; i ++) {
102 if (NULL != args [i]) {
103 if (mode_P == get_type_mode (get_method_param_type (meth, i))) {
104 ir_node *call_arg = get_Call_param (call, i);
105 pto_t *arg_pto = get_pto (call_arg, env);
106 pto_t *frm_pto = get_node_pto (args [i]);
111 change |= qset_insert_all (frm_pto->values, arg_pto->values);
113 DBGPRINT (2, (stdout, "%s: arg [%i]: -> %s[%li] (%i) -> %s[%li] (%i)\n",
116 OPNAME (call_arg), OPNUM (call_arg),
118 OPNAME (args [i]), OPNUM (args [i]),
119 frm_pto->values->id));
127 /* Transfer the actual arguments to the formal arguments */
128 static void set_graph_args (ir_graph *graph, ir_node *call, pto_env_t *env)
130 ir_type *meth = get_entity_type (get_irg_entity (graph));
131 ir_node **args = get_irg_proj_args (graph);
134 assert (op_Call == get_irn_op(call));
136 n_args = get_Call_n_params (call);
138 for (i = 0; i < n_args; i ++) {
139 if (NULL != args [i]) {
140 if (mode_P == get_type_mode (get_method_param_type (meth, i))) {
141 ir_node *call_arg = get_Call_param (call, i);
142 pto_t *pto = get_pto (call_arg, env);
144 set_node_pto (args [i], pto);
146 DBGPRINT (1, (stdout, "%s: arg [%i]: %s[%li] -> %s[%li] (%i)\n",
149 OPNAME (call_arg), OPNUM (call_arg),
150 OPNAME (args [i]), OPNUM (args [i]),
157 /* Transfer the graph's result to the call */
158 static int set_graph_result (ir_graph *graph, ir_node *call)
160 ir_type *tp = get_entity_type (get_irg_entity (graph));
162 pto_t *ret_pto, *call_pto;
165 if (0 == get_method_n_ress (tp)) {
169 tp = get_method_res_type (tp, 0);
171 if (mode_P != get_type_mode (tp)) {
172 set_node_pto (call, NULL);
177 end_block = get_irg_end_block (graph);
178 ret_pto = get_node_pto (end_block);
180 call_pto = get_node_pto (call);
184 DBGPRINT (1, (stdout, "%s: before change args\n", __FUNCTION__));
185 DBGEXE (1, pto_print_pto (end_block));
186 DBGEXE (1, pto_print_pto (call));
188 change = qset_insert_all (call_pto->values, ret_pto->values);
191 DBGPRINT (1, (stdout, "%s: after change args\n", __FUNCTION__));
192 DBGEXE (1, pto_print_pto (end_block));
193 DBGEXE (1, pto_print_pto (call));
200 /* Propagation of PTO values */
201 static pto_t *get_pto_proj (ir_node *proj, pto_env_t *env)
203 ir_node *proj_in = get_Proj_pred (proj);
204 const ir_opcode in_op = get_irn_opcode (proj_in);
205 pto_t *in_pto = NULL;
206 pto_t *proj_pto = NULL; /* get_node_pto (proj); */
208 ir_node *proj_in_in = NULL;
211 case (iro_Start): /* ProjT (Start) */
212 assert (0 && "pto from ProjT(Start) requested");
215 case (iro_Proj): { /* ProjT (Start), ProjT (Call) */
219 proj_in_in = get_Proj_pred (proj_in);
220 in_in_op = get_irn_opcode (proj_in_in);
221 proj_in_proj = get_Proj_proj (proj_in);
223 assert ((pn_Start_T_args == proj_in_proj) ||
224 (pn_Call_T_result == proj_in_proj));
227 case (iro_Start): /* ProjArg (ProjT (Start)) */
228 /* then the pto value must have been set to the node */
229 proj_pto = get_node_pto (proj);
233 case (iro_Call): /* ProjV (ProjT (Call)) */
234 if (NULL != proj_pto) {
237 in_pto = get_pto (proj_in, env);
238 set_node_pto (proj, in_pto);
244 default: assert (0 && "Proj(Proj(?))");
246 /* done with case (in_op == iro_Proj) */
249 case (iro_Load): /* ProjV (Load) */
250 assert (pn_Load_res == get_Proj_proj(proj));
252 case (iro_Call): /* ProjT (Call) */
254 case (iro_Alloc): /* ProjV (Alloc) */
255 if (NULL != proj_pto) {
258 in_pto = get_pto (proj_in, env);
261 set_node_pto (proj, in_pto);
265 fprintf (stderr, "get_pto_proj(/*todo*/): not handled: proj (%s[%li])\n",
266 get_op_name (get_irn_op (proj_in)),
267 get_irn_node_nr (proj_in));
268 assert (0 && "Proj(?)");
274 static pto_t *get_pto_phi (ir_node *phi, pto_env_t *env)
280 assert (mode_P == get_irn_mode (phi));
282 pto = get_node_pto (phi);
283 assert (pto); /* must be initialised */
285 n_ins = get_irn_arity (phi);
286 for (i = 0; i < n_ins; i ++) {
287 ir_node *in = get_irn_n (phi, i);
288 pto_t *in_pto = get_pto (in, env);
292 change |= qset_insert_all (pto->values, in_pto->values);
295 env->change |= change;
300 static pto_t *get_pto_sel (ir_node *sel, pto_env_t *env)
302 pto_t *pto = NULL; /* get_node_pto (sel); */
305 ir_node *in = get_Sel_ptr (sel);
307 pto = get_pto (in, env);
308 set_node_pto (sel, pto);
314 static pto_t *get_pto_ret (ir_node *ret, pto_env_t *env)
316 pto_t *pto = NULL; /* get_node_pto (ret); */
319 ir_node *in = get_Return_res (ret, 0);
321 pto = get_pto (in, env);
322 set_node_pto (ret, pto);
327 DBGPRINT (9, (stdout, "%s: ", __FUNCTION__));
328 DBGEXE (9, pto_print_pto (ret));
334 /* Dispatch to propagate PTO values */
335 static pto_t *get_pto (ir_node *node, pto_env_t *env)
337 const ir_opcode op = get_irn_opcode (node);
339 DBGPRINT (2, (stdout, "%s (%s[%li])\n",
341 OPNAME (node), OPNUM (node)));
344 case (iro_Cast): return (get_pto (get_Cast_op (node), env));
345 case (iro_Proj): return (get_pto_proj (node, env));
346 case (iro_Phi): return (get_pto_phi (node, env));
347 case (iro_Sel): return (get_pto_sel (node, env));
348 case (iro_Alloc): return (get_alloc_pto (node));
349 case (iro_Return): return (get_pto_ret (node, env));
351 case (iro_Call): /* FALLTHROUGH */
352 case (iro_Load): /* FALLTHROUGH */
353 case (iro_Const): /* FALLTHROUGH */
354 case (iro_SymConst):{
355 pto_t *pto = get_node_pto (node);
361 /* stopgap measure */
362 fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
364 get_irn_node_nr (node),
365 get_op_name (get_irn_op (node)));
366 assert (0 && "something not handled");
372 /* Actions for the nodes: */
373 static void pto_load (ir_node *load, pto_env_t *pto_env)
379 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
381 OPNAME (load), OPNUM (load), (int) get_node_pto (load)));
383 ptr = get_Load_ptr (load);
385 if (is_dummy_load_ptr (ptr)) {
389 ent = get_ptr_ent (ptr);
391 if (mode_P == get_type_mode (get_entity_type (ent))) {
392 pto_t *ptr_pto = get_pto (ptr, pto_env);
396 DBGPRINT (1, (stdout, "%s (%s[%li]): ptr = 0x%08x\n",
398 OPNAME (ptr), OPNUM (ptr), (int) ptr_pto));
400 pto_env->change |= mod_load (load, ent, ptr_pto);
404 static void pto_store (ir_node *store, pto_env_t *pto_env)
408 pto_t *ptr_pto, *val_pto;
411 DBGPRINT (2, (stdout, "%s (%s[%li]) (no pto)\n",
413 OPNAME (store), OPNUM (store)));
415 ptr = get_Store_ptr (store);
416 val = get_Store_value (store);
418 if (mode_P != get_irn_mode (val)) {
422 ent = get_ptr_ent (ptr);
424 ptr_pto = get_pto (ptr, pto_env);
425 val_pto = get_pto (val, pto_env);
430 DBGPRINT (2, (stdout, "%s (%s[%li]): ptr_pto = 0x%08x\n",
432 OPNAME (ptr), OPNUM (ptr), (int) ptr_pto));
433 DBGPRINT (2, (stdout, "%s (%s[%li]): val_pto = 0x%08x\n",
435 OPNAME (val), OPNUM (val), (int) val_pto));
437 pto_env->change |= mod_store (store, ent, ptr_pto, val_pto);
440 static void pto_method (ir_node *call, pto_env_t *pto_env)
443 callEd_info_t *callEd_info;
445 DBGPRINT (2, (stdout, "%s:%i (%s[%li]): pto = 0x%08x\n",
446 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call),
447 (int) get_node_pto (call)));
449 callEd_info = ecg_get_callEd_info (call);
451 if (NULL == callEd_info) {
452 DBGPRINT (2, (stdout, "%s:%i (%s[%li]), no graph\n",
453 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
457 while (NULL != callEd_info) {
458 DBGPRINT (2, (stdout, "%s:%i (%s[%li]), graph %i\n",
459 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call), i ++));
461 pto_call (callEd_info->callEd, call, pto_env);
463 callEd_info = callEd_info->prev;
467 /* Perform the appropriate action on the given node */
468 static void pto_node_node(ir_node *node, pto_env_t *pto_env)
470 ir_opcode op = get_irn_opcode (node);
472 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
473 __FUNCTION__, OPNAME (node), OPNUM (node)));
476 case (iro_Start): /* nothing */ break;
478 pto_load (node, pto_env);
482 pto_store (node, pto_env);
486 pto_method (node, pto_env);
490 pto_raise (node, pto_env);
502 pto_end_block (node, pto_env);
507 assert (mode_M == get_irn_mode (node));
511 /* uninteresting stuff: */
515 case (iro_DivMod): /* nothing to do */ break;
518 /* stopgap measure */
519 fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
521 get_irn_node_nr (node),
522 get_op_name (get_irn_op (node)));
523 assert (0 && "something not handled");
528 /* Callback function to execute in pre-order */
529 static void pto_node_pre (ir_node *node, void *env)
534 /* Callback function to execute in post-order */
535 static void pto_node_post (ir_node *node, void *env)
537 pto_env_t *pto_env = (pto_env_t*) env;
539 DBGPRINT (999, (stdout, "%s (%s[%li])\n",
541 OPNAME (node), OPNUM (node)));
543 pto_node_node (node, pto_env);
546 /* Perform a single pass over the given graph */
547 static void pto_graph_pass (ir_graph *graph, void *pto_env)
549 irg_walk_mem (graph, pto_node_pre, pto_node_post, pto_env);
552 /* Continue PTO for one of the graphs called at a Call */
553 static void pto_call (ir_graph *graph, ir_node *call, pto_env_t *pto_env)
557 /* only for debugging stuff: */
558 ir_entity *ent = get_irg_entity (graph);
559 const char *ent_name = (char*) get_entity_name (ent);
560 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
563 DBGPRINT (2, (stdout, "%s (%s[%li]) to \"%s.%s\"\n",
565 OPNAME (call), OPNUM (call),
566 own_name, ent_name));
568 if (! get_irg_is_mem_visited (graph)) {
569 /* handle direct call */
570 graph_info_t *ginfo = ecg_get_info (graph);
573 int ctx_idx = find_ctx_idx (call, ginfo, get_curr_ctx ());
574 ctx_info_t *call_ctx = get_ctx (ginfo, ctx_idx);
575 ctx_info_t *old_ctx = set_curr_ctx (call_ctx);
577 DBGPRINT (1, (stdout, "%s>CTX: ", -- spaces));
578 DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
580 /* Initialise Alloc Names and Node values */
581 pto_reset_graph_pto (graph, ctx_idx);
583 /* Compute Arguments */
584 set_graph_args (graph, call, pto_env);
586 /* Visit/Iterate Graph */
587 pto_graph (graph, ctx_idx, pto_env);
590 set_curr_ctx (old_ctx);
592 /* Get Return Value from Graph */
593 change |= set_graph_result (graph, call);
595 DBGPRINT (1, (stdout, "%s<CTX: ", spaces ++));
596 DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
598 /* Don't need to reset alloc names unless we handle recursion here */
603 /* handle recursion */
604 DBGPRINT (0, (stdout, "%s: recursion into \"%s.%s\"\n",
606 own_name, ent_name));
607 /* Find 'right' enclosing pto_env */
609 while (graph != enc_env->graph) {
610 enc_env = enc_env->enc_env; /* talk about naming issues here */
612 /* since we're in a recursion loop, we *must* find an env for the callEd here: */
613 assert (NULL != enc_env->enc_env);
616 /* Re-Set arguments */
617 rec_change = add_graph_args (graph, call, pto_env);
619 DBGPRINT (1, (stdout, "%s: return in:", __FUNCTION__));
620 DBGEXE (1, pto_print_pto (get_irg_end_block (graph)));
623 DBGPRINT (0, (stdout, "%s: change args\n", __FUNCTION__));
626 rec_change |= set_graph_result (graph, call);
629 DBGPRINT (1, (stdout, "%s: return out:", __FUNCTION__));
630 DBGEXE (1, pto_print_pto (get_irg_end_block (graph)));
634 /* appears that we don't need this: */
635 enc_env->change |= rec_change;
639 /* Todo: Set 'Unknown' Value as Return Value when the graph is not
642 pto_env->change |= change;
645 static void pto_raise (ir_node *raise, pto_env_t *pto_env)
648 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
650 OPNAME (raise), OPNUM (raise), (int) get_node_pto (raise)));
653 static void pto_end_block (ir_node *end_block, pto_env_t *pto_env)
655 /* perform end block */
656 ir_type *tp = get_entity_type (get_irg_entity (get_irn_irg (end_block)));
660 if (0 == get_method_n_ress (tp)) {
664 tp = get_method_res_type (tp, 0);
666 if (! mode_is_reference(get_type_mode (tp))) {
670 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
672 OPNAME (end_block), OPNUM (end_block),
673 (int) get_node_pto (end_block)));
675 end_pto = get_node_pto (end_block);
679 n_ins = get_irn_arity (end_block);
680 for (i = 0; i < n_ins; i ++) {
681 ir_node *in = get_irn_n (end_block, i);
683 if (iro_Return == get_irn_opcode (in)) {
684 pto_t *in_pto = get_pto (in, pto_env);
686 pto_env->change |= qset_insert_all (end_pto->values, in_pto->values);
691 /* ===================================================
692 Exported Implementation:
693 =================================================== */
694 /* Main loop: Initialise and iterate over the given graph */
695 void pto_graph (ir_graph *graph, int ctx_idx, pto_env_t *enc_env)
700 /* Also exported, since we need it in 'pto.c' */
701 pto_env = xmalloc (sizeof (pto_env_t));
702 pto_env->enc_env = enc_env;
703 pto_env->graph = graph;
704 pto_env->ctx_idx = ctx_idx;
705 pto_env->change = TRUE;
707 /* HERE ("start"); */
709 DBGPRINT (2, (stdout, "%s: start for ctx %i\n",
713 /* todo (here): iterate, obey 'changed' attribute */
715 while (0 != pto_env->change) {
717 pto_env->change = FALSE;
718 pto_graph_pass (graph, pto_env);
721 DBGPRINT (1, (stdout, "%s: %i runs on \"%s.%s\"\n",
724 get_type_name (get_entity_owner (get_irg_entity (graph))),
725 get_entity_name (get_irg_entity (graph))));
726 memset (pto_env, 0, sizeof (pto_env_t));
731 /* Set the PTO value for the given non-alloc node */
732 void set_node_pto (ir_node *node, pto_t *pto)
734 assert (op_Alloc != get_irn_op(node));
736 set_irn_link (node, (void*) pto);
739 /*Get the PTO value for the given non-alloc node */
740 pto_t *get_node_pto (ir_node *node)
742 assert (op_Alloc != get_irn_op(node));
744 return ((pto_t*) get_irn_link (node));
747 /* Set the PTO value for the given alloc node */
748 void set_alloc_pto (ir_node *alloc, alloc_pto_t *alloc_pto)
750 assert (op_Alloc == get_irn_op(alloc));
754 set_irn_link (alloc, (void*) alloc_pto);
757 /*Get the current PTO value for the given alloc node */
758 pto_t *get_alloc_pto (ir_node *alloc)
760 alloc_pto_t *alloc_pto = get_irn_link (alloc);
762 assert (op_Alloc == get_irn_op(alloc));
764 assert (alloc_pto -> curr_pto);
766 return (alloc_pto -> curr_pto);
772 Revision 1.21 2007/03/22 10:39:33 matze
773 a bunch of fixes to make firm work with NDEBUG and without DEBUG_libfirm
775 Revision 1.20 2007/01/16 15:45:42 beck
776 renamed type opcode to ir_opcode
778 Revision 1.19 2006/12/13 19:46:47 beck
779 rename type entity into ir_entity
781 Revision 1.18 2006/01/13 22:57:41 beck
782 renamed all types 'type' to 'ir_type'
783 used mode_is_reference instead of != mode_P test
785 Revision 1.17 2005/02/25 16:48:21 liekweg
788 Revision 1.16 2005/01/27 15:51:19 liekweg
791 Revision 1.15 2005/01/14 14:14:26 liekweg
792 fix gnu extension, fix fprintf's
794 Revision 1.14 2005/01/14 13:37:26 liekweg
795 fix allocation (size); don't cast malloc
797 Revision 1.13 2005/01/10 17:26:34 liekweg
798 fixup printfs, don't put environments on the stack
800 Revision 1.12 2004/12/23 15:46:19 beck
801 removed unneeded allocations
803 Revision 1.11 2004/12/21 14:50:59 beck
804 removed C)) and GNUC constructs, add default returns
806 Revision 1.10 2004/12/20 17:34:35 liekweg
807 fix recursion handling
809 Revision 1.9 2004/12/15 13:31:18 liekweg
810 remove debugging stuff
812 Revision 1.8 2004/12/15 09:18:18 liekweg
815 Revision 1.7 2004/12/06 12:55:06 liekweg
818 Revision 1.6 2004/12/02 16:17:51 beck
819 fixed config.h include
821 Revision 1.5 2004/11/30 14:47:54 liekweg
822 fix initialisation; do correct iteration
824 Revision 1.4 2004/11/26 15:59:40 liekweg
825 verify pto_{load,store}
827 Revision 1.3 2004/11/24 14:53:55 liekweg
830 Revision 1.2 2004/11/20 21:21:56 liekweg
831 Finalise initialisation
833 Revision 1.1 2004/11/18 16:37:34 liekweg