5 * File name: ir/ana2/pto.c
9 * Created: Mon 18 Oct 2004
11 * Copyright: (c) 1999-2004 Universität Karlsruhe
12 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
21 # include "pto_util.h"
22 # include "pto_init.h"
29 /* # include "eset.h" */
37 # include "typewalk.h"
38 # include "irmemwalk.h"
40 # define DBGPRINT(lvl, msg) if (get_pto_verbose () > lvl) { fprintf msg; }
45 static void pto_node (ir_node*, void*);
46 static void pto_node_pre (ir_node*, void*);
47 static void pto_node_post (ir_node*, void*);
50 Get the pto infos of a node
52 static pto_t *get_pto (ir_node *node)
56 return ((pto_t*) get_irn_link (node));
60 Propagate pto values up to the given node, and return the propagated
61 value. This recursion has to stop at important nodes, such as
62 loads and allocs, where pto is computed differently (albeit this may
63 involve more calls to this function for a different ptr value).
65 static pto_t *compute_pto (ir_node *node, void *env)
67 pto_t *node_pto = get_pto (node);
69 if ((NULL != node_pto) && (pto_is_dummy (node_pto))) {
70 /* weed out initialisation data as good as possible */
72 DBGPRINT (0, (stdout, "%s: dummy pto for (%s[%li])\n",
74 get_op_name (get_irn_op (node)),
75 get_irn_node_nr (node)));
77 pto_delete (node_pto);
81 if (NULL == node_pto) {
82 DBGPRINT (1, (stdout, "%s: must compute pto for %s[%li]\n",
84 get_op_name (get_irn_op (node)),
85 get_irn_node_nr (node)));
89 node_pto = get_pto (node);
98 Transfer the actual arguments to the given call's formal arguments
100 static void set_call_args (ir_node *call, ir_graph *graph, void *env)
102 ir_node **args = find_irg_args (graph);
105 const int n_call_args = get_irn_arity (call);
107 /* call: M x meth_ptr x Arg x Arg x ... x Arg */
108 /* projT(start): Arg x Arg x ... x Arg */
109 /* projM(start): M */
111 for (i = 2; i < n_call_args; i ++) {
112 if (NULL != args [i-2]) {
113 if (mode_P == get_irn_mode (args [i-2])) {
114 pto_t *arg_pto = compute_pto (get_irn_n (call, i), env);
115 /* off-by-two because of ProjT bd */
116 set_pto (args [i-2], arg_pto);
118 /* not a pointer value */
126 Transfer the return value of a call to the callR node
128 static void get_call_ret (ir_node *call, ir_graph *graph, void *env)
130 entity *ent = get_irg_ent (graph);
131 type *ent_tp = get_entity_type (ent);
133 if (NULL != get_pto (call)) {
134 pto_t *old = get_pto (call);
136 if (pto_is_dummy (old)) {
137 DBGPRINT (2, (stdout, "%s: dummy pto (0x%08x) from call[%li]\n",
138 __FUNCTION__, (int) old, get_irn_node_nr (call)));
144 if (0 != get_method_n_ress (ent_tp)) {
145 type *ent_ret_tp = get_method_res_type (ent_tp, 0);
147 if (mode_P == get_type_mode (ent_ret_tp)) {
148 pto_t *res_pto = get_pto (get_irg_end_block (graph));
150 set_pto (call, res_pto);
157 Take care of a single proj node. Basically a multiplex/dispatch for the
158 different node types that a proj can have as a predecessor.
160 static void pto_node_proj (ir_node *proj, void *env)
163 pto for proj({proj(start),load,call,alloc,raise?,...}) node
165 ir_node *in = get_Proj_pred (proj);
166 const opcode in_op = get_irn_opcode (in);
167 const long proj_proj = get_Proj_proj (proj);
169 DBGPRINT (3, (stdout, "%s: --> Proj[%li] (%s)\n",
171 get_irn_node_nr (proj),
172 get_op_name (get_irn_op (in))));
176 /* nothing (handled by proj(proj)) */
181 if (pn_Load_res == proj_proj) {
182 set_pto (proj, compute_pto (in, env));
184 /* ProjM(load) or ProjX(load) - do nothing */
189 /* ProjM (store) or ProjX (store) - nothing */
193 /* copy from alloc */
194 if (pn_Alloc_res == proj_proj) {
195 set_pto (proj, compute_pto (in, env));
197 /* ProjM(alloc) or ProjX (alloc) -- nothing */
202 /* ProjX (raise), ProjM (raise) -- nothing */
206 if (pn_Call_M_regular == proj_proj) {
207 /* ProjM(call) -- nothing */
208 } else if (pn_Call_T_result == proj_proj) {
209 /* copy return value of call */
210 pto_t *call_pto = get_pto (in); /* get result from call */
212 set_pto (proj, call_pto);
213 } else if (pn_Call_P_value_res_base == proj_proj) {
215 assert (0 && "what's with pn_Call_P_value_res_base?");
217 /* ProjX (call) or ProjM_exc (call) -- nothing */
223 const ir_node *in_in = get_Proj_pred (in);
224 const opcode in_in_op = get_irn_opcode (in_in);
228 /* projP (projT (call)) */
229 /* copy from projT to projP */
230 pto_t *in_pto = compute_pto (in, env);
231 set_pto (proj, in_pto);
234 /* proj(proj(start)) - make sure the arguments are initialised */
235 assert (get_pto (proj));
238 DBGPRINT (1, (stdout, "%s:%i: proj(proj(%s)) not handled\n",
239 __FILE__, __LINE__, get_op_name (get_irn_op (in_in))));
246 /* make sure the input has been analysed */
247 pto_t *cast_pto = compute_pto (in, env);
248 set_pto (proj, cast_pto);
253 fprintf (stderr, "%s: opcode %s of Node %ld not handled\n",
255 get_op_name (get_irn_op (in)),
256 get_irn_node_nr (in));
258 assert (0 && "something not handled");
262 DBGPRINT (2, (stdout, "%s: Proj (%s)\n",
264 get_op_name (get_irn_op (in))));
267 static void pto_node_obj_load (ir_node *load, ir_node *ptr,
268 entity *ent, void *env)
271 pto for obj load node
278 const char *ent_name = (char*) get_entity_name (ent);
279 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
281 DBGPRINT (1, (stdout, "%s for (%s[%li])\n",
283 get_op_name (get_irn_op (ptr)),
284 get_irn_node_nr (ptr)));
286 if (! is_pointer_type (get_entity_type (ent))) {
290 if (NULL != get_pto (load)) {
291 pto_t *old = get_pto (load);
293 if (pto_is_dummy (old)) {
294 DBGPRINT (0, (stdout, "%s: dummy pto (0x%08x) from load[%li]\n",
295 __FUNCTION__, (int) old, get_irn_node_nr (load)));
301 DBGPRINT (0, (stdout, "%s: obj load from ent (0x%08x) \"%s.%s\"\n",
307 pto_t *ptr_objs = compute_pto (ptr, env);
308 qset_t *objs = ptr_objs->objs;
309 pto_t *res = pto_new_empty (load);
310 obj_desc_t *obj_desc = (obj_desc_t*) qset_start (objs);
312 /* fprintf (stdout, "%s: load ptr = ", __FUNCTION__); */
313 /* qset_print (ptr_objs->objs, stdout); */
315 while (NULL != obj_desc) {
316 qset_t *cnts = pto_lookup (obj_desc, ent);
318 pto_add_all_names (res, cnts);
320 /* fprintf (stdout, "%s: load val = ", __FUNCTION__); */
321 /* qset_print (cnts, stdout); */
323 obj_desc = (obj_desc_t*) qset_next (objs);
326 /* fprintf (stdout, "%s: load res = ", __FUNCTION__); */
327 /* qset_print (res->objs, stdout); */
332 static void pto_node_arr_load (ir_node *load, ir_node *ptr,
333 entity *ent, void *env)
336 pto for array load node
339 load.ptr analysed or can be computed on-the-fly
343 const char *ent_name = (char*) get_entity_name (ent);
344 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
346 /* load from array */
347 DBGPRINT (1, (stdout, "%s for (%s[%li])\n",
349 get_op_name (get_irn_op (ptr)),
350 get_irn_node_nr (ptr)));
352 if (! is_pointer_type (get_entity_type (ent))) {
356 DBGPRINT (0, (stdout, "%s: array load from ent (0x%08x) \"%s.%s\"\n",
362 pto_t *ptr_objs = compute_pto (ptr, env);
363 qset_t *objs = ptr_objs->objs;
364 pto_t *res = pto_new_empty (load);
366 obj_desc_t *obj_desc = (obj_desc_t*) qset_start (objs);
368 while (NULL != obj_desc) {
369 qset_t *cnts = pto_lookup (obj_desc, NULL);
371 pto_add_all_names (res, cnts);
373 obj_desc = (obj_desc_t*) qset_next (objs);
379 static void pto_node_load (ir_node *load, void *env)
385 load.ptr analysed or can be computed on-the-fly
389 ir_node *ptr = get_Load_ptr (load);
390 const opcode op = get_irn_opcode (ptr);
393 /* check the funny cases */
394 if (iro_Proj == op) {
395 /* then it's an unused Load(this) (or whatever) and we don't need to look at it */
396 DBGPRINT (1, (stderr, "%s: %s[%li] ignored\n",
398 get_op_name (get_irn_op (ptr)),
399 get_irn_node_nr (ptr)));
401 } else if (iro_Cast == op) {
402 /* then it's (whatever) and we don't know where to look at */
403 DBGPRINT (1, (stderr, "%s: %s[%li] ignored\n",
405 get_op_name (get_irn_op (ptr)),
406 get_irn_node_nr (ptr)));
410 ent = get_ptr_ent (ptr);
414 /* array load or obj load? */
415 if ((iro_Sel == op) && (3 == get_irn_arity (ptr))) {
416 pto_node_arr_load (load, ptr, ent, env);
418 pto_node_obj_load (load, ptr, ent, env);
423 static void pto_node_obj_store (ir_node *store,
430 pto for obj store node
432 so far: ptr analysed or can be computed on-the-fly
438 const char *ent_name = (char*) get_entity_name (ent);
439 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
441 DBGPRINT (0, (stdout, "%s: obj store from ent (0x%08x) \"%s.%s\"\n",
443 (int) ent, own_name, ent_name));
445 pto_t *ptr_pto = compute_pto (ptr, env);
446 pto_t *val_pto = compute_pto (val, env);
447 qset_t *objs = ptr_pto->objs;
448 qset_t *vals = val_pto->objs;
450 obj_desc_t *obj_desc = (obj_desc_t*) qset_start (objs);
452 while (NULL != obj_desc) {
453 qset_t *cnts = pto_lookup (obj_desc, ent);
455 qset_insert_all (cnts, vals);
457 obj_desc = (obj_desc_t*) qset_next (objs);
461 static void pto_node_arr_store (ir_node *store,
468 pto for array store node
470 so far: ptr analysed or can be computed on-the-fly
475 const char *ent_name = (char*) get_entity_name (ent);
476 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
478 DBGPRINT (0, (stdout, "%s: array store from ent (0x%08x) \"%s.%s\"\n",
480 (int) ent, own_name, ent_name));
482 pto_t *ptr_pto = compute_pto (ptr, env);
483 pto_t *val_pto = compute_pto (val, env);
484 qset_t *objs = ptr_pto->objs;
485 qset_t *vals = val_pto->objs;
487 obj_desc_t *obj_desc = (obj_desc_t*) qset_start (objs);
489 while (NULL != obj_desc) {
490 qset_t *cnts = pto_lookup (obj_desc, NULL);
492 qset_insert_all (cnts, vals);
494 obj_desc = (obj_desc_t*) qset_next (objs);
498 static void pto_node_store (ir_node *store, void *env)
503 so far: ptr analysed or can be computed on-the-fly
508 ir_node *ptr = get_Store_ptr (store);
509 ir_node *val = get_Store_value (store);
510 const opcode op = get_irn_opcode (ptr);
511 entity *ent = get_ptr_ent (ptr);
513 if (mode_P != get_irn_mode (val)) {
517 /* array load or obj load? */
518 if ((iro_Sel == op) && (3 == get_irn_arity (ptr))) {
519 pto_node_arr_store (store, ptr, ent, val, env);
521 pto_node_obj_store (store, ptr, ent, val, env);
526 static void pto_node_alloc (ir_node *alloc, void *env)
531 so far: nothing to do
536 type *tp = get_Alloc_type (alloc);
538 pto_t *alloc_pto = pto_new_name (alloc, tp);
539 set_pto (alloc, alloc_pto);
542 static void pto_node_free (ir_node *free, void *env)
547 so far: ptr analysed or can be computed on-the-fly
551 /* still, copy somthing */
552 ir_node *ptr = get_Free_ptr (free);
554 pto_t *ptr_pto = compute_pto (ptr, env);
555 set_pto (free, ptr_pto);
558 static void pto_node_raise (ir_node *raise, void *env)
563 so far: ptr analysed or can be computed on-the-fly
568 /* right now, just copy something */
569 ir_node *ptr = get_Raise_exo_ptr (raise);
571 pto_t *ptr_pto = compute_pto (ptr, env);
573 set_pto (raise, ptr_pto);
576 static void pto_node_sel (ir_node *sel, void *env)
581 so far: input selected or can be computed on-the-fly
583 just copy (the selected entity is used in the load/store)
586 ir_node *sel_in = get_Sel_ptr (sel);
587 pto_t *sel_pto = compute_pto (sel_in, env);
589 if (NULL == sel_pto) {
590 fprintf (stdout, "%s:%i: sel.in = %s[%li]\n",
591 __FUNCTION__, __LINE__,
592 get_op_name (get_irn_op (sel_in)),
593 get_irn_node_nr (sel_in));
597 set_pto (sel, sel_pto);
600 static void pto_node_call (ir_node *call, void *env)
602 ir_graph *graph = NULL;
603 ir_node *ptr = get_Call_ptr (call);
604 entity *ent = get_ptr_ent (ptr);
606 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
608 get_op_name (get_irn_op (call)),
609 get_irn_node_nr (call)));
612 const char *ent_name = (char*) get_entity_name (ent);
613 const char *own_name = (char*) get_type_name (get_entity_owner (ent));
615 /* Todo: Iterate over all graphs in 'get_implementing_graphs' */
616 graph = get_entity_irg (ent);
618 if (! get_irg_is_mem_visited (graph)) {
619 DBGPRINT (1, (stdout, " -> visit graph (0x%08x) of \"%s.%s\"\n",
620 (int) graph, own_name, ent_name));
622 /* compute call arguments */
623 set_call_args (call, graph, env);
624 /* traverse callEd */
625 irg_walk_mem (graph, pto_node_pre, pto_node_post, NULL);
626 /* maybe get result from called graph */
627 get_call_ret (call, graph, env);
630 DBGPRINT (0, (stdout, "%s:%i: Warning: no graph for ent \"%s.%s\" in call[%li]\n",
631 __FILE__, __LINE__, own_name, ent_name, get_irn_node_nr (call)));
635 static void pto_node_ret (ir_node *ret, void *env)
641 input should be availlable
646 if ((0 != get_Return_n_ress (ret)) &&
647 (mode_P == get_irn_mode (get_Return_res (ret, 0)))) {
648 ir_node *ret_in = get_Return_res (ret, 0);
650 pto_t *ret_pto = compute_pto (ret_in, env);
652 DBGPRINT (4, (stdout, "--> Return Node (%ld) (%s)\n",
653 get_irn_node_nr (ret),
654 get_op_name (get_irn_op (ret))));
656 set_pto (ret, ret_pto);
662 static void pto_node_phi (ir_node *phi, void *env)
668 all ins present or can be computed on-the-fly
674 int n_ins = get_irn_arity (phi);
677 if (mode_P != get_irn_mode (phi)) {
681 assert (0 && "test phi");
683 pto_t *phi_pto = get_pto (phi);
685 if (NULL == phi_pto) {
686 phi_pto = pto_new_empty (phi);
687 set_pto (phi, phi_pto);
690 for (i = 0; i < n_ins; i ++) {
691 in = get_irn_n (phi, i);
693 pto_t *in_pto = compute_pto (in, env);
695 DBGPRINT (0, (stdout, "%s: IN PHI Node (%ld) (%s) (pto = 0x%08x)\n",
697 get_irn_node_nr (in),
698 get_op_name (get_irn_op (in)),
701 qset_insert_all (phi_pto->objs, in_pto->objs);
705 static void pto_node_cnst (ir_node *cnst, void *env)
712 if this represents something nameable, name it
714 type *tp = get_Const_type (cnst);
715 pto_t *cnst_pto = pto_new_name (cnst, tp);
718 set_pto (cnst, cnst_pto);
721 static void pto_node_sym_cnst (ir_node *sym_cnst, void *env)
728 if this represents something nameable, name it
730 type *tp = get_entity_type (get_SymConst_entity (sym_cnst));
732 if (is_class_type (tp)) {
733 pto_t *sym_cnst_pto = pto_new_name (sym_cnst, tp);
735 set_pto (sym_cnst, sym_cnst_pto);
741 static void pto_node_end_block (ir_node *end, void *env)
746 so far: all returns are set or can be computed on-the-fly
748 collect results, set to node.
750 type *tp = get_entity_type (get_irg_entity (get_irn_irg (end)));
752 DBGPRINT (2, (stdout, "%s: End Block (%ld) (%s)\n",
754 get_irn_node_nr (end),
755 get_op_name (get_irn_op (end))));
757 if (0 != get_method_n_ress (tp)) {
758 tp = get_method_res_type (tp, 0);
760 if (mode_P == get_type_mode (tp)) {
762 int n_ins = get_irn_arity (end);
763 pto_t *end_pto = pto_new_name (end, get_pointer_points_to_type (tp));
765 for (i = 0; i < n_ins; i ++) {
766 ir_node *ret = get_irn_n (end, i);
768 pto_t *ret_pto = get_pto (ret);
772 set_pto (end, end_pto);
778 Take care of a single node. Basically a multiplex/dispatch for the
779 different node types.
781 static void pto_node (ir_node *node, void *env)
783 const opcode op = get_irn_opcode (node);
785 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
787 get_op_name (get_irn_op (node)),
788 get_irn_node_nr (node)));
792 /* pto_node_start (node, env); */
797 pto_node_load (node, env);
801 pto_node_store (node, env);
805 pto_node_alloc (node, env);
809 pto_node_free (node, env);
813 pto_node_raise (node, env);
817 pto_node_sel (node, env);
821 /* assert (0 && "calls must be handled in main loop"); */
822 pto_node_call (node, env);
825 if (0 < get_Return_n_ress (node)) {
826 pto_node_ret (node, env);
830 pto_node_proj (node, env);
833 pto_node_phi (node, env);
836 pto_node_cnst (node, env);
838 case (iro_SymConst): {
839 pto_node_sym_cnst (node, env);
842 pto_t *cast_pto = compute_pto (get_Cast_op (node), env);
843 set_pto (node, cast_pto);
847 pto_node_end_block (node, env);
849 /* all the uninteresting stuff */
854 set_pto (node, NULL);
857 /* stopgap measure */
858 DBGPRINT (0, (stdout, "%s: not handled: node[%li].op = %s\n",
860 get_irn_node_nr (node),
861 get_op_name (get_irn_op (node))));
862 assert (0 && "something not handled");
866 static void pto_node_pre (ir_node *node, void *env)
868 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
870 get_op_name (get_irn_op (node)),
871 get_irn_node_nr (node)));
873 pto_init_node (node);
876 static void pto_node_post (ir_node *node, void *env)
878 DBGPRINT (1, (stdout, "%s (%s[%li])\n",
880 get_op_name (get_irn_op (node)),
881 get_irn_node_nr (node)));
883 pto_node (node, env);
886 static int pto_verbose = 0;
889 Helper to pto_init --- clear the link fields of class types
891 static void clear_type_link (type_or_ent *thing, void *__unused)
893 if (is_type (thing)) {
894 type *tp = (type*) thing;
896 if (is_class_type (tp)) {
897 DBGPRINT (4, (stdout, "%s (\"%s\")\n",
898 __FUNCTION__, get_type_name (tp)));
900 set_type_link (tp, NULL);
906 Helper to pto_cleanup --- deallocate the field closure lists and clear the link fields of class types
908 static void free_field_list (type_or_ent *thing, void *__unused)
911 type *tp = (type*) thing;
913 if (is_class_type (tp)) {
914 if (NULL != get_type_link (tp)) {
915 entity **fields = (entity**) get_type_link (tp);
920 set_type_link (tp, NULL);
926 void set_pto (ir_node *node, pto_t *pto)
930 set_irn_link (node, (void*) pto);
933 int get_pto_verbose ()
935 return (pto_verbose);
938 void set_pto_verbose (int verbose)
940 pto_verbose = verbose;
948 type_walk (clear_type_link, NULL, NULL);
955 void pto_run (int do_verbose)
958 set_pto_verbose (do_verbose);
960 DBGPRINT (0, (stdout, "START PTO\n"));
962 ir_graph *graph = get_irp_main_irg ();
964 DBGPRINT (0, (stdout, "START GRAPH (0x%08x) of \"%s.%s\"\n",
966 get_type_name (get_entity_owner (get_irg_entity (graph))),
967 get_entity_name (get_irg_entity (graph))));
969 /* Set args for main graph */
971 type *meth_tp = get_entity_type (get_irg_entity (graph));
972 type *param_tp = get_method_param_type (meth_tp, 1);
973 param_tp = get_pointer_points_to_type (param_tp);
975 const long n_args = /* wtf? */
976 get_method_n_params (meth_tp);
977 ir_node **args = find_irg_args (graph);
978 pto_t *main_pto = pto_new_name (args [1], param_tp);
981 for (i = 0; i < n_args; i ++) {
982 DBGPRINT (2, (stdout, "arg [%i] = %s[%ld]\n",
984 args [i] ? get_op_name (get_irn_op (args [i])) : "none",
985 args [i] ? get_irn_node_nr (args [i]) : -1));
987 set_pto (args [1], main_pto);
992 irg_walk_mem (graph, pto_node_pre, pto_node_post, NULL);
994 DBGPRINT (0, (stdout, "END GRAPH (0x%08x)\n", (int) graph));
995 DBGPRINT (0, (stdout, "END PTO\n"));
997 obj_desc_list_all (NULL);
1005 type_walk (free_field_list, NULL, NULL);
1012 * Revision 1.5 2004/11/08 12:33:06 liekweg
1013 * initialisation; sanitize print levels, misc fixes
1015 * Revision 1.4 2004/11/04 14:58:38 liekweg
1016 * expanded pto, added initialisation, added debugging printing
1018 * Revision 1.3 2004/10/25 11:59:45 liekweg
1021 * Revision 1.2 2004/10/21 11:09:37 liekweg
1022 * Moved memwalk stuf into irmemwalk
1023 * Moved lset stuff into lset
1024 * Moved typalise stuff into typalise
1026 * Revision 1.1 2004/10/20 14:59:42 liekweg
1027 * Added ana2, added ecg and pto