5 File name: ir/ana2/pto_comp.c
6 Purpose: Main Implementation of PTO
9 Created: Sat Nov 13 19:35:27 CET 2004
11 Copyright: (c) 1999-2004 Universität Karlsruhe
12 Licence: This file is protected by the GPL - GNU GENERAL PUBLIC LICENSE.
20 pto_comp: Main Implementation of PTO
23 # include <string.h> /* for memset */
25 # include "pto_comp.h"
26 # include "pto_util.h"
27 # include "pto_name.h"
31 # include "irnode_t.h"
34 # include "irmemwalk.h"
36 # include "pto_debug.h"
37 # include "pto_init.h"
45 /* Local Data Types: */
46 typedef struct pto_env_str {
47 struct pto_env_str *enc_env;
54 /* Local Variables: */
59 /* Local Prototypes: */
60 static pto_t *get_pto (ir_node*, pto_env_t*);
61 static void pto_call (ir_graph*, ir_node*, pto_env_t*);
62 static void pto_raise (ir_node*, pto_env_t*);
63 static void pto_load (ir_node*, pto_env_t*);
64 static void pto_store (ir_node*, pto_env_t*);
65 static void pto_method (ir_node*, pto_env_t*);
66 static void pto_end_block (ir_node*, pto_env_t*);
68 /* ===================================================
70 =================================================== */
71 /* Add values of the actual arguments to the formal arguments */
72 static int add_graph_args (ir_graph *graph, ir_node *call, pto_env_t *env)
75 type *meth = get_entity_type (get_irg_entity (graph));
76 ir_node **args = get_irg_proj_args (graph);
79 assert(op_Call == get_irn_op(call));
81 n_args = get_Call_n_params (call);
83 DBGPRINT (1, (stdout, "%s: args of %s[%li] -> 0x%08x\n",
85 OPNAME (call), OPNUM (call), (int) graph));
87 for (i = 0; i < n_args; i ++) {
88 if (NULL != args [i]) {
89 if (mode_P == get_type_mode (get_method_param_type (meth, i))) {
90 ir_node *call_arg = get_Call_param (call, i);
91 pto_t *arg_pto = get_pto (call_arg, env);
92 pto_t *frm_pto = get_node_pto (args [i]);
97 change |= qset_insert_all (frm_pto->values, arg_pto->values);
99 DBGPRINT (2, (stdout, "%s: arg [%i]: -> %s[%li] (%i) -> %s[%li] (%i)\n",
102 OPNAME (call_arg), OPNUM (call_arg),
104 OPNAME (args [i]), OPNUM (args [i]),
105 frm_pto->values->id));
113 /* Transfer the actual arguments to the formal arguments */
114 static void set_graph_args (ir_graph *graph, ir_node *call, pto_env_t *env)
116 type *meth = get_entity_type (get_irg_entity (graph));
117 ir_node **args = get_irg_proj_args (graph);
120 assert (op_Call == get_irn_op(call));
122 n_args = get_Call_n_params (call);
124 for (i = 0; i < n_args; i ++) {
125 if (NULL != args [i]) {
126 if (mode_P == get_type_mode (get_method_param_type (meth, i))) {
127 ir_node *call_arg = get_Call_param (call, i);
128 pto_t *pto = get_pto (call_arg, env);
130 set_node_pto (args [i], pto);
132 DBGPRINT (1, (stdout, "%s: arg [%i]: %s[%li] -> %s[%li] (%i)\n",
135 OPNAME (call_arg), OPNUM (call_arg),
136 OPNAME (args [i]), OPNUM (args [i]),
143 /* Transfer the graph's result to the call */
144 static int set_graph_result (ir_graph *graph, ir_node *call)
146 type *tp = get_entity_type (get_irg_entity (graph));
148 pto_t *ret_pto, *call_pto;
151 if (0 == get_method_n_ress (tp)) {
155 tp = get_method_res_type (tp, 0);
157 if (mode_P != get_type_mode (tp)) {
158 set_node_pto (call, NULL);
163 end_block = get_irg_end_block (graph);
164 ret_pto = get_node_pto (end_block);
166 call_pto = get_node_pto (call);
170 DBGPRINT (1, (stdout, "%s: before change args\n", __FUNCTION__));
171 DBGEXE (1, pto_print_pto (end_block));
172 DBGEXE (1, pto_print_pto (call));
174 change = qset_insert_all (call_pto->values, ret_pto->values);
177 DBGPRINT (1, (stdout, "%s: after change args\n", __FUNCTION__));
178 DBGEXE (1, pto_print_pto (end_block));
179 DBGEXE (1, pto_print_pto (call));
186 /* Propagation of PTO values */
187 static pto_t *get_pto_proj (ir_node *proj, pto_env_t *env)
189 ir_node *proj_in = get_Proj_pred (proj);
190 const long proj_proj = get_Proj_proj (proj);
191 const opcode in_op = get_irn_opcode (proj_in);
192 pto_t *in_pto = NULL;
193 pto_t *proj_pto = NULL; /* get_node_pto (proj); */
195 ir_node *proj_in_in = NULL;
198 case (iro_Start): /* ProjT (Start) */
199 assert (0 && "pto from ProjT(Start) requested");
202 case (iro_Proj): { /* ProjT (Start), ProjT (Call) */
206 proj_in_in = get_Proj_pred (proj_in);
207 in_in_op = get_irn_opcode (proj_in_in);
208 proj_in_proj = get_Proj_proj (proj_in);
210 assert ((pn_Start_T_args == proj_in_proj) ||
211 (pn_Call_T_result == proj_in_proj));
214 case (iro_Start): /* ProjArg (ProjT (Start)) */
215 /* then the pto value must have been set to the node */
216 proj_pto = get_node_pto (proj);
220 case (iro_Call): /* ProjV (ProjT (Call)) */
221 if (NULL != proj_pto) {
224 in_pto = get_pto (proj_in, env);
225 set_node_pto (proj, in_pto);
231 default: assert (0 && "Proj(Proj(?))");
233 /* done with case (in_op == iro_Proj) */
236 case (iro_Load): /* ProjV (Load) */
237 assert (pn_Load_res == proj_proj);
239 case (iro_Call): /* ProjT (Call) */
241 case (iro_Alloc): /* ProjV (Alloc) */
242 if (NULL != proj_pto) {
245 in_pto = get_pto (proj_in, env);
248 set_node_pto (proj, in_pto);
252 fprintf (stderr, "get_pto_proj(/*todo*/): not handled: proj (%s[%li])\n",
253 get_op_name (get_irn_op (proj_in)),
254 get_irn_node_nr (proj_in));
255 assert (0 && "Proj(?)");
261 static pto_t *get_pto_phi (ir_node *phi, pto_env_t *env)
267 assert (mode_P == get_irn_mode (phi));
269 pto = get_node_pto (phi);
270 assert (pto); /* must be initialised */
272 n_ins = get_irn_arity (phi);
273 for (i = 0; i < n_ins; i ++) {
274 ir_node *in = get_irn_n (phi, i);
275 pto_t *in_pto = get_pto (in, env);
279 change |= qset_insert_all (pto->values, in_pto->values);
282 env->change |= change;
287 static pto_t *get_pto_sel (ir_node *sel, pto_env_t *env)
289 pto_t *pto = NULL; /* get_node_pto (sel); */
292 ir_node *in = get_Sel_ptr (sel);
294 pto = get_pto (in, env);
295 set_node_pto (sel, pto);
301 static pto_t *get_pto_ret (ir_node *ret, pto_env_t *env)
303 pto_t *pto = NULL; /* get_node_pto (ret); */
306 ir_node *in = get_Return_res (ret, 0);
308 pto = get_pto (in, env);
309 set_node_pto (ret, pto);
314 DBGPRINT (9, (stdout, "%s: ", __FUNCTION__));
315 DBGEXE (9, pto_print_pto (ret));
321 /* Dispatch to propagate PTO values */
322 static pto_t *get_pto (ir_node *node, pto_env_t *env)
324 const opcode op = get_irn_opcode (node);
326 DBGPRINT (2, (stdout, "%s (%s[%li])\n",
328 OPNAME (node), OPNUM (node)));
331 case (iro_Cast): return (get_pto (get_Cast_op (node), env));
332 case (iro_Proj): return (get_pto_proj (node, env));
333 case (iro_Phi): return (get_pto_phi (node, env));
334 case (iro_Sel): return (get_pto_sel (node, env));
335 case (iro_Alloc): return (get_alloc_pto (node));
336 case (iro_Return): return (get_pto_ret (node, env));
338 case (iro_Call): /* FALLTHROUGH */
339 case (iro_Load): /* FALLTHROUGH */
340 case (iro_Const): /* FALLTHROUGH */
341 case (iro_SymConst):{
342 pto_t *pto = get_node_pto (node);
348 /* stopgap measure */
349 fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
351 get_irn_node_nr (node),
352 get_op_name (get_irn_op (node)));
353 assert (0 && "something not handled");
359 /* Actions for the nodes: */
360 static void pto_load (ir_node *load, pto_env_t *pto_env)
366 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
368 OPNAME (load), OPNUM (load), (int) get_node_pto (load)));
370 ptr = get_Load_ptr (load);
372 if (is_dummy_load_ptr (ptr)) {
376 ent = get_ptr_ent (ptr);
378 if (mode_P == get_type_mode (get_entity_type (ent))) {
379 pto_t *ptr_pto = get_pto (ptr, pto_env);
383 DBGPRINT (1, (stdout, "%s (%s[%li]): ptr = 0x%08x\n",
385 OPNAME (ptr), OPNUM (ptr), (int) ptr_pto));
387 pto_env->change |= mod_load (load, ent, ptr_pto);
391 static void pto_store (ir_node *store, pto_env_t *pto_env)
395 pto_t *ptr_pto, *val_pto;
398 DBGPRINT (2, (stdout, "%s (%s[%li]) (no pto)\n",
400 OPNAME (store), OPNUM (store)));
402 ptr = get_Store_ptr (store);
403 val = get_Store_value (store);
405 if (mode_P != get_irn_mode (val)) {
409 ent = get_ptr_ent (ptr);
411 ptr_pto = get_pto (ptr, pto_env);
412 val_pto = get_pto (val, pto_env);
417 DBGPRINT (2, (stdout, "%s (%s[%li]): ptr_pto = 0x%08x\n",
419 OPNAME (ptr), OPNUM (ptr), (int) ptr_pto));
420 DBGPRINT (2, (stdout, "%s (%s[%li]): val_pto = 0x%08x\n",
422 OPNAME (val), OPNUM (val), (int) val_pto));
424 pto_env->change |= mod_store (store, ent, ptr_pto, val_pto);
427 static void pto_method (ir_node *call, pto_env_t *pto_env)
430 callEd_info_t *callEd_info;
432 DBGPRINT (2, (stdout, "%s:%i (%s[%li]): pto = 0x%08x\n",
433 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call),
434 (int) get_node_pto (call)));
436 callEd_info = ecg_get_callEd_info (call);
438 if (NULL == callEd_info) {
439 DBGPRINT (2, (stdout, "%s:%i (%s[%li]), no graph\n",
440 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
444 while (NULL != callEd_info) {
445 DBGPRINT (2, (stdout, "%s:%i (%s[%li]), graph %i\n",
446 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call), i ++));
448 pto_call (callEd_info->callEd, call, pto_env);
450 callEd_info = callEd_info->prev;
454 /* Perform the appropriate action on the given node */
455 static void pto_node_node(ir_node *node, pto_env_t *pto_env)
457 opcode op = get_irn_opcode (node);
459 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
460 __FUNCTION__, OPNAME (node), OPNUM (node)));
463 case (iro_Start): /* nothing */ break;
465 pto_load (node, pto_env);
469 pto_store (node, pto_env);
473 pto_method (node, pto_env);
477 pto_raise (node, pto_env);
489 pto_end_block (node, pto_env);
494 assert (mode_M == get_irn_mode (node));
498 /* uninteresting stuff: */
502 case (iro_DivMod): /* nothing to do */ break;
505 /* stopgap measure */
506 fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
508 get_irn_node_nr (node),
509 get_op_name (get_irn_op (node)));
510 assert (0 && "something not handled");
515 /* Callback function to execute in pre-order */
516 static void pto_node_pre (ir_node *node, void *env)
521 /* Callback function to execute in post-order */
522 static void pto_node_post (ir_node *node, void *env)
524 pto_env_t *pto_env = (pto_env_t*) env;
526 DBGPRINT (999, (stdout, "%s (%s[%li])\n",
528 OPNAME (node), OPNUM (node)));
530 pto_node_node (node, pto_env);
533 /* Perform a single pass over the given graph */
534 static void pto_graph_pass (ir_graph *graph, void *pto_env)
536 irg_walk_mem (graph, pto_node_pre, pto_node_post, pto_env);
539 /* Continue PTO for one of the graphs called at a Call */
540 static void pto_call (ir_graph *graph, ir_node *call, pto_env_t *pto_env)
544 /* only for debugging stuff: */
545 entity *ent = get_irg_entity (graph);
546 const char *ent_name = (char*) get_entity_name (ent);
547 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
550 DBGPRINT (2, (stdout, "%s (%s[%li]) to \"%s.%s\"\n",
552 OPNAME (call), OPNUM (call),
553 own_name, ent_name));
555 if (! get_irg_is_mem_visited (graph)) {
556 /* handle direct call */
557 graph_info_t *ginfo = ecg_get_info (graph);
560 int ctx_idx = find_ctx_idx (call, ginfo, get_curr_ctx ());
561 ctx_info_t *call_ctx = get_ctx (ginfo, ctx_idx);
562 ctx_info_t *old_ctx = set_curr_ctx (call_ctx);
564 DBGPRINT (1, (stdout, "%s>CTX: ", -- spaces));
565 DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
567 /* Initialise Alloc Names and Node values */
568 pto_reset_graph_pto (graph, ctx_idx);
570 /* Compute Arguments */
571 set_graph_args (graph, call, pto_env);
573 /* Visit/Iterate Graph */
574 pto_graph (graph, ctx_idx, pto_env);
577 set_curr_ctx (old_ctx);
579 /* Get Return Value from Graph */
580 change |= set_graph_result (graph, call);
582 DBGPRINT (1, (stdout, "%s<CTX: ", spaces ++));
583 DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
585 /* Don't need to reset alloc names unless we handle recursion here */
590 /* handle recursion */
591 DBGPRINT (0, (stdout, "%s: recursion into \"%s.%s\"\n",
593 own_name, ent_name));
594 /* Find 'right' enclosing pto_env */
596 while (graph != enc_env->graph) {
597 enc_env = enc_env->enc_env; /* talk about naming issues here */
599 /* since we're in a recursion loop, we *must* find an env for the callEd here: */
600 assert (NULL != enc_env->enc_env);
603 /* Re-Set arguments */
604 rec_change = add_graph_args (graph, call, pto_env);
606 DBGPRINT (1, (stdout, "%s: return in:", __FUNCTION__));
607 DBGEXE (1, pto_print_pto (get_irg_end_block (graph)));
610 DBGPRINT (0, (stdout, "%s: change args\n", __FUNCTION__));
613 rec_change |= set_graph_result (graph, call);
616 DBGPRINT (1, (stdout, "%s: return out:", __FUNCTION__));
617 DBGEXE (1, pto_print_pto (get_irg_end_block (graph)));
621 /* appears that we don't need this: */
622 enc_env->change |= rec_change;
626 /* Todo: Set 'Unknown' Value as Return Value when the graph is not
629 pto_env->change |= change;
632 static void pto_raise (ir_node *raise, pto_env_t *pto_env)
635 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
637 OPNAME (raise), OPNUM (raise), (int) get_node_pto (raise)));
640 static void pto_end_block (ir_node *end_block, pto_env_t *pto_env)
642 /* perform end block */
643 type *tp = get_entity_type (get_irg_entity (get_irn_irg (end_block)));
647 if (0 == get_method_n_ress (tp)) {
651 tp = get_method_res_type (tp, 0);
653 if (mode_P != get_type_mode (tp)) {
657 DBGPRINT (2, (stdout, "%s (%s[%li]): pto = 0x%08x\n",
659 OPNAME (end_block), OPNUM (end_block),
660 (int) get_node_pto (end_block)));
662 end_pto = get_node_pto (end_block);
666 n_ins = get_irn_arity (end_block);
667 for (i = 0; i < n_ins; i ++) {
668 ir_node *in = get_irn_n (end_block, i);
670 if (iro_Return == get_irn_opcode (in)) {
671 pto_t *in_pto = get_pto (in, pto_env);
673 pto_env->change |= qset_insert_all (end_pto->values, in_pto->values);
678 /* ===================================================
679 Exported Implementation:
680 =================================================== */
681 /* Main loop: Initialise and iterate over the given graph */
682 void pto_graph (ir_graph *graph, int ctx_idx, pto_env_t *enc_env)
687 /* Also exported, since we need it in 'pto.c' */
688 pto_env = xmalloc (sizeof (pto_env_t));
689 pto_env->enc_env = enc_env;
690 pto_env->graph = graph;
691 pto_env->ctx_idx = ctx_idx;
692 pto_env->change = TRUE;
694 /* HERE ("start"); */
696 DBGPRINT (2, (stdout, "%s: start for ctx %i\n",
700 /* todo (here): iterate, obey 'changed' attribute */
702 while (0 != pto_env->change) {
704 pto_env->change = FALSE;
705 pto_graph_pass (graph, pto_env);
708 DBGPRINT (1, (stdout, "%s: %i runs on \"%s.%s\"\n",
711 get_type_name (get_entity_owner (get_irg_entity (graph))),
712 get_entity_name (get_irg_entity (graph))));
713 memset (pto_env, 0, sizeof (pto_env_t));
718 /* Set the PTO value for the given non-alloc node */
719 void set_node_pto (ir_node *node, pto_t *pto)
721 assert (op_Alloc != get_irn_op(node));
723 set_irn_link (node, (void*) pto);
726 /*Get the PTO value for the given non-alloc node */
727 pto_t *get_node_pto (ir_node *node)
729 assert (op_Alloc != get_irn_op(node));
731 return ((pto_t*) get_irn_link (node));
734 /* Set the PTO value for the given alloc node */
735 void set_alloc_pto (ir_node *alloc, alloc_pto_t *alloc_pto)
737 assert (op_Alloc == get_irn_op(alloc));
741 set_irn_link (alloc, (void*) alloc_pto);
744 /*Get the current PTO value for the given alloc node */
745 pto_t *get_alloc_pto (ir_node *alloc)
747 alloc_pto_t *alloc_pto = get_irn_link (alloc);
749 assert (op_Alloc == get_irn_op(alloc));
751 assert (alloc_pto -> curr_pto);
753 return (alloc_pto -> curr_pto);
759 Revision 1.17 2005/02/25 16:48:21 liekweg
762 Revision 1.16 2005/01/27 15:51:19 liekweg
765 Revision 1.15 2005/01/14 14:14:26 liekweg
766 fix gnu extension, fix fprintf's
768 Revision 1.14 2005/01/14 13:37:26 liekweg
769 fix allocation (size); don't cast malloc
771 Revision 1.13 2005/01/10 17:26:34 liekweg
772 fixup printfs, don't put environments on the stack
774 Revision 1.12 2004/12/23 15:46:19 beck
775 removed unneeded allocations
777 Revision 1.11 2004/12/21 14:50:59 beck
778 removed C)) and GNUC constructs, add default returns
780 Revision 1.10 2004/12/20 17:34:35 liekweg
781 fix recursion handling
783 Revision 1.9 2004/12/15 13:31:18 liekweg
784 remove debugging stuff
786 Revision 1.8 2004/12/15 09:18:18 liekweg
789 Revision 1.7 2004/12/06 12:55:06 liekweg
792 Revision 1.6 2004/12/02 16:17:51 beck
793 fixed config.h include
795 Revision 1.5 2004/11/30 14:47:54 liekweg
796 fix initialisation; do correct iteration
798 Revision 1.4 2004/11/26 15:59:40 liekweg
799 verify pto_{load,store}
801 Revision 1.3 2004/11/24 14:53:55 liekweg
804 Revision 1.2 2004/11/20 21:21:56 liekweg
805 Finalise initialisation
807 Revision 1.1 2004/11/18 16:37:34 liekweg