nsz Git - libfirm/blob - ir/ana2/typalise.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana2/pto.c
   6  * Purpose:     Pto
   7  * Author:      Florian
   8  * Modified by:
   9  * Created:     Mon 18 Oct 2004
  10  * CVS-ID:      $Id$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file is protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15
  16 # ifdef HAVE_CONFIG_H
  17 #  include <config.h>
  18 # endif
  19
  20 # include "typalise.h"
  21
  22 # ifndef TRUE
  23 #  define TRUE 1
  24 #  define FALSE 0
  25 # endif /* not defined TRUE */
  26
  27 # include <assert.h>
  28 # include <string.h>
  29
  30 # include "irnode.h"
  31 # include "irgwalk.h"
  32 # include "xmalloc.h"
  33
  34
  35 /*
  36   Local Globals
  37 */
  38
  39 static long ta_id = 0;
  40
  41 /*
  42   Local Protos
  43 */
  44 static typalise_t *typalise_proj (ir_node*);
  45
  46
  47 /*
  48   Ctors, Dtors for typalise_t-s
  49 */
  50 static typalise_t *ta_exact (type *tp)
  51 {
  52   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
  53   ta->kind = type_exact;
  54   ta->res.type = tp;
  55   ta->id = ta_id ++;
  56
  57   assert (is_class_type (tp));
  58
  59   return (ta);
  60 }
  61
  62 static typalise_t *ta_types (lset_t *set)
  63 {
  64   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
  65   ta->kind = type_types;
  66   ta->res.types = set;
  67   ta->id = ta_id ++;
  68
  69   return (ta);
  70 }
  71
  72 static typalise_t *ta_type (type *tp)
  73 {
  74   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
  75   ta->kind = type_type;
  76   ta->res.type = tp;
  77   ta->id = ta_id ++;
  78
  79   assert (is_class_type (tp));
  80
  81   return (ta);
  82 }
  83
  84 static void ta_delete (typalise_t *ta)
  85 {
  86   if (type_types == ta->kind) {
  87     lset_destroy (ta->res.types);
  88     ta->res.types = NULL;
  89   } else {
  90     ta->res.type = NULL;
  91   }
  92
  93   ta->kind = type_invalid;
  94
  95   free (ta);
  96 }
  97
  98 /*
  99   Helpers for inheritance, overwriting and stuff
 100 */
 101 /**
 102    Find out whether otype is a subtype of stype.
 103    Return non-zero iff otype is a subtype of stype.
 104 */
 105 static int is_subtype (type *otype, type *stype)
 106 {
 107   int n_sub = get_class_n_subtypes (stype);
 108   int is_sub = FALSE;
 109   int i;
 110
 111   if (otype == stype) {
 112     return (TRUE);
 113   }
 114
 115   for (i = 0; (!is_sub) && (i < n_sub); i ++) {
 116     type *sub = get_class_subtype (stype, i);
 117
 118     is_sub |= is_subtype (otype, sub);
 119   }
 120
 121
 122   return (is_sub);
 123 }
 124
 125
 126 /**
 127     Compute the closure of all subtypes of otype (including otype
 128     itself)
 129 */
 130 static void _collect_subtypes (type *otype, lset_t *set)
 131 {
 132   lset_insert (set, otype);
 133
 134   int n_sub = get_class_n_subtypes (otype);
 135   int i;
 136
 137   for (i = 0; i < n_sub; i ++) {
 138     type *sub = get_class_subtype (otype, i);
 139
 140     _collect_subtypes (sub, set);
 141   }
 142 }
 143
 144 static lset_t *subtype_closure (type *otype)
 145 {
 146   lset_t *set = lset_create ();
 147
 148   _collect_subtypes (otype, set);
 149
 150   return (set);
 151 }
 152
 153 /**
 154    Helper method for get_owner_types
 155 */
 156 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
 157 {
 158   /* search DOWNwards in clazz hierarchy */
 159
 160   if ((peculiarity_description == get_entity_peculiarity (method)) ||
 161       (peculiarity_inherited   == get_entity_peculiarity (method))) {
 162     lset_insert (tps, get_entity_owner (method));
 163   } else if (peculiarity_existent == get_entity_peculiarity (method)) {
 164     ir_graph *ex_graph = get_entity_irg (method);
 165
 166     if ((NULL == ex_graph) || (ex_graph == graph)) {
 167       /* wtf? they define the same graph again? well, whatever: */
 168       lset_insert (tps, get_entity_owner (method));
 169     } else {
 170       /* aha: they define a new graph. can't have that, so bail out */
 171       return;
 172     }
 173   }
 174
 175   int n_over = get_entity_n_overwrittenby (method);
 176   int i;
 177
 178   for (i = 0; i < n_over; i ++) {
 179     entity *ometh = get_entity_overwrittenby (method, i);
 180
 181     _collect_owner_types (ometh, graph, tps);
 182   }
 183 }
 184
 185
 186 /**
 187    Collect all classes that use the given implementation of a method.
 188 */
 189 static lset_t *get_owner_types (ir_graph *graph)
 190 {
 191   lset_t *tps = lset_create ();
 192   entity *meth = get_irg_entity (graph);
 193
 194   _collect_owner_types (meth, graph, tps);
 195
 196   return (tps);
 197 }
 198
 199 /**
 200    Return a list containing all types of 'set' which are a subtype of 'type'.
 201 */
 202 static lset_t *filter_for_type (lset_t *set, type *stype)
 203 {
 204   type *curs = (type*) lset_first (set);
 205   lset_t *lset = lset_create ();
 206
 207   while (NULL != curs) {
 208     if (is_subtype (curs, stype)) {
 209       lset_insert (lset, curs);
 210     }
 211
 212     curs = lset_next (set);
 213   }
 214
 215   return (lset);
 216 }
 217
 218 /*
 219  Handle typalise_t-s
 220 */
 221 /**
 222     Join 'one' and 'two'; both args are deallocated, result is freshly
 223     allocated.
 224 */
 225 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
 226 {
 227   typalise_t *res = NULL;
 228
 229   switch (one->kind) {
 230   case (type_invalid): { /* shut up, gcc */ }
 231   case (type_exact): {
 232     switch (two->kind) {
 233     case (type_invalid): { /* shut up, gcc */ }
 234     case (type_exact): {
 235       if (one->res.type == two->res.type) {
 236         res = one;
 237       } else {
 238         lset_t *set = lset_create ();
 239         lset_insert (set, one->res.type);
 240         lset_insert (set, two->res.type);
 241         res = ta_types (set);
 242
 243         ta_delete (one);
 244       }
 245
 246       ta_delete (two);
 247     } break;
 248     case (type_types): {
 249       lset_insert (two->res.types, one->res.type);
 250       ta_delete (one);
 251
 252       res = two;
 253     } break;
 254     case (type_type): {
 255       if (is_subtype (one->res.type, two->res.type)) {
 256         ta_delete (one);
 257         res = two;
 258       } else {
 259         lset_t *closure = subtype_closure (two->res.type);
 260         lset_insert (closure, one->res.type);
 261
 262         ta_delete (two);
 263
 264         res = one;
 265       }
 266     } break;
 267     }
 268   } break;
 269   case (type_types): {
 270     switch (two->kind) {
 271     case (type_invalid): { /* shut up, gcc */ }
 272     case (type_exact): {
 273       res = ta_join (two, one);
 274     } break;
 275     case (type_types): {
 276       lset_insert_all (one->res.types, two->res.types);
 277       ta_delete (two);
 278
 279       res = one;
 280     } break;
 281     case (type_type): {
 282       lset_t *closure = subtype_closure (two->res.type);
 283       lset_append (one->res.types, closure);
 284
 285       ta_delete (two);
 286
 287       res = one;
 288     } break;
 289     }
 290   } break;
 291   case (type_type): {
 292     switch (two->kind) {
 293     case (type_invalid): { /* shut up, gcc */ }
 294     case (type_exact): {
 295       res = ta_join (two, one);
 296     } break;
 297     case (type_types): {
 298       res = ta_join (two, one);
 299     } break;
 300     case (type_type): {
 301       type *one_type = one->res.type;
 302       type *two_type = two->res.type;
 303
 304       if (is_subtype (one_type, two_type)) {
 305         ta_delete (one);
 306         res = two;
 307       } else if (is_subtype (two_type, one_type)) {
 308         ta_delete (two);
 309         res = one;
 310       } else {
 311         lset_t *one_closure = subtype_closure (one->res.type);
 312         lset_t *two_closure = subtype_closure (two->res.type);
 313
 314         lset_append (one_closure, two_closure);
 315
 316         ta_delete (two);
 317         ta_delete (one);
 318
 319         res = ta_types (one_closure);
 320       }
 321     } break;
 322     }
 323   } break;
 324   }
 325
 326   assert (res && "no result");
 327
 328   return (res);
 329 }
 330
 331
 332 # ifdef SHUT_UP_GCC
 333 static const char *ta_name (typalise_t *ta)
 334 {
 335 # define BUF_SIZE 1024
 336   static char buf [BUF_SIZE];
 337
 338   int len = sprintf (buf, "[%d] ", ta->id);
 339
 340   switch (ta->kind) {
 341   case (type_invalid): { /* shut up, gcc */ }
 342   case (type_exact): {
 343     len += sprintf (buf+len, "only ");
 344     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 345   } break;
 346   case (type_types): {
 347     len += sprintf (buf+len, "one_of ");
 348
 349     type *iter = lset_first (ta->res.types);
 350
 351     int size = BUF_SIZE - len - 1;
 352     while ((NULL != iter) && (0 < size)) {
 353       char *dest = strncat (buf, get_type_name (iter), size);
 354       size = (dest - buf);
 355
 356       iter = lset_next (ta->res.types);
 357     }
 358   } break;
 359   case (type_type): {
 360     len += sprintf (buf+len, "poly ");
 361     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 362   } break;
 363   }
 364
 365   return (buf);
 366   /* # undef BUF_SIZE */
 367 }
 368 # endif /* SHUT_UP_GCC */
 369
 370 /**
 371    Find out whether the given clazz uses the given implementation of a
 372    method.  Presumably, this is because clazz inherits the graph as
 373    the implementation for a method.
 374 */
 375 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
 376 {
 377   type *g_clazz = get_entity_owner (meth);
 378
 379   if (g_clazz == clazz) {
 380     return (TRUE);
 381   }
 382
 383   if (peculiarity_existent == get_entity_peculiarity (meth)) {
 384     ir_graph *g_graph = get_entity_irg (meth);
 385
 386     if (g_graph != graph) {
 387       return (FALSE);
 388     }
 389   }
 390
 391   /* else inherited or description */
 392   int use = FALSE;
 393   int i;
 394   int n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
 395
 396   for (i = 0; (i < n_over) && (!use); i ++) {
 397     entity *over = get_entity_overwrittenby (meth, i);
 398
 399     use |= uses_graph (clazz, over, graph);
 400   }
 401
 402   return (use);
 403 }
 404
 405 /**
 406    Check whether the given typalise_t includes the given type.
 407 */
 408 static int ta_supports (typalise_t *ta, ir_graph *graph)
 409 {
 410   switch (ta->kind) {
 411   case (type_invalid): { /* shut up, gcc */ }
 412   case (type_exact): {
 413     int res = FALSE;
 414     lset_t *tps = get_owner_types (graph);
 415
 416     if (lset_contains (tps, ta->res.type)) {
 417       res = TRUE;
 418     }
 419
 420     lset_destroy (tps);
 421
 422     return (res);
 423   }
 424   case (type_type): {
 425     entity *meth = get_irg_entity (graph);
 426     type *tp = get_entity_owner (meth);
 427     int res = is_subtype (tp, ta->res.type);
 428
 429     if (res) {
 430       return (TRUE);
 431     } else {
 432       res = uses_graph (ta->res.type, meth, graph);
 433     }
 434
 435     return (res);
 436   }
 437   case (type_types): {
 438     type *tp = get_entity_owner (get_irg_entity (graph));
 439
 440     return (lset_contains (ta->res.types, tp));
 441   }
 442   }
 443
 444   assert (0 && "invalid ta");
 445 }
 446
 447
 448 /* =========== WHAT ELSE ? =========== */
 449
 450 /*
 451   Helper to typalise (ir_node*)
 452 */
 453 /**
 454     Find an approximation to the given proj node's value's types
 455 */
 456 static typalise_t *typalise_proj (ir_node *proj)
 457 {
 458   typalise_t *res = NULL;
 459   ir_node *proj_in = get_Proj_pred (proj);
 460
 461   if (iro_Proj  == get_irn_opcode (proj_in)) {
 462     /* fprintf (stdout, "\tProj (Proj)\n"); */
 463
 464     proj_in = get_Proj_pred (proj_in);
 465     if (iro_Start == get_irn_opcode (proj_in)) {
 466       ir_graph *graph = get_irn_irg (proj);
 467       entity   *meth  = get_irg_entity (graph);
 468
 469       long n = get_Proj_proj (proj);
 470
 471       if (1 == n) {
 472         /* yay proj this */
 473         type     *tp    = get_entity_owner (meth);
 474
 475         /* res = ta_exact (tp); */
 476         res = ta_type (tp);     /* TODO */
 477       } else {
 478         /* ugh proj arg */
 479         type *tp = get_method_param_type (get_entity_type (meth), n);
 480         if (is_pointer_type (tp)) {
 481           tp = get_pointer_points_to_type (tp);
 482         }
 483
 484         res = ta_type (tp);
 485       }
 486     } else if (iro_Call == get_irn_opcode (proj_in)) {
 487       /* call result ... 'whatever' */
 488       /* hey, this is redundant (or the check for iro_Call further down) */
 489       ir_node *call_ptr = get_Call_ptr (proj_in);
 490
 491       res = typalise (call_ptr);
 492     } else {
 493       fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
 494                get_op_name (get_irn_op (proj_in)));
 495       assert (0);
 496     }
 497   } else {
 498     opcode op = get_irn_opcode (proj_in);
 499     if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
 500       fprintf (stdout, "\n Proj (%s) not handled\n",
 501                get_op_name (get_irn_op (proj_in)));
 502       assert (0);
 503     }
 504     res = typalise (proj_in);      /* everything else */
 505     /* Proj (Load), Proj (New), Proj (Call) */
 506   }
 507
 508   return (res);
 509 }
 510
 511
 512
 513 /*
 514   Public Interface
 515 */
 516 /**
 517    Given a set of graphs and a typalise_t,  return the method (s) in
 518    the set that are supported by the typalise_t.  Also, deallocates
 519    the given set.
 520 */
 521 lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
 522 {
 523   lset_t *res = lset_create ();
 524   ir_graph *curs = (ir_graph*) lset_first (set);
 525
 526   while (NULL != curs) {
 527     if (ta_supports (ta, curs)) {
 528       lset_insert (res, curs);
 529     }
 530
 531     curs = lset_next (set);
 532   }
 533
 534   lset_destroy (set);
 535
 536   return (res);
 537 }
 538
 539 /**
 540    For the given ptr, do a quick check about what (class) types may be
 541    brought along on it.
 542 */
 543 typalise_t *typalise (ir_node *node)
 544 {
 545   opcode op = get_irn_opcode (node);
 546   typalise_t *res = NULL;
 547
 548   switch (op) {
 549   case (iro_Cast): {
 550     /* casts always succeed */
 551     typalise_t *ta = NULL;
 552     type *tp = get_Cast_type (node);
 553
 554     if (is_pointer_type (tp)) {
 555       tp = get_pointer_points_to_type (tp);
 556     }
 557     assert (is_class_type (tp));
 558
 559     ta = typalise (get_Cast_op (node));
 560
 561     if (NULL == ta) {           /* no type found */
 562       ta = ta_type (tp);
 563     } else if (type_exact == ta->kind) { /* one type found */
 564       /* nothing (maybe check cast? */
 565     } else if (type_type == ta->kind) { /* some types found */
 566       if (is_subtype (tp, ta->res.type)) {
 567         ta->res.type = tp;     /* assume cast is correct */
 568       } else {
 569         /* should assert (is_subtype (ta->res.type, tp)) */
 570       }
 571     } else if (type_types == ta->kind) {
 572       lset_t *ftp = filter_for_type (ta->res.types, tp);
 573       lset_destroy (ta->res.types);
 574       ta->res.types = ftp;
 575     }
 576
 577     res = ta;
 578   } break;
 579
 580   case (iro_Proj): {
 581     res = typalise_proj (node);
 582   } break;
 583
 584   case (iro_Load): {
 585     ir_node *load_ptr = get_Load_ptr (node);
 586
 587     res = typalise (load_ptr);
 588   } break;
 589
 590   case (iro_Sel): {
 591     /* FILTER */
 592     /* it's call (sel (ptr)) or load (sel (ptr)) */
 593     entity *ent = get_Sel_entity (node);
 594     type *tp = get_entity_type (ent);
 595
 596     if (is_method_type (tp)) {
 597       tp = get_entity_type (ent);
 598       tp = get_method_res_type (tp, 0);
 599
 600       if (is_pointer_type (tp)) {
 601         tp = get_pointer_points_to_type (tp);
 602       }
 603
 604       res = ta_type (tp);
 605     } else if (is_class_type (tp)) {
 606       tp = get_entity_type (ent);
 607
 608       if (is_pointer_type (tp)) {
 609         tp = get_pointer_points_to_type (tp);
 610       }
 611
 612       res = ta_type (tp);
 613     } else if (is_pointer_type (tp)) {
 614       tp = get_pointer_points_to_type (tp);
 615       res = ta_type (tp);
 616     } else {
 617       assert (0 && "select not handled");
 618     }
 619   } break;
 620
 621   case (iro_Phi): {
 622     int n_ins = get_irn_arity (node);
 623     int i;
 624     ir_node *phi_in = NULL;
 625     typalise_t *ta = NULL;
 626     /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
 627
 628     for (i = 0; i < n_ins; i ++) {
 629       phi_in = get_irn_n (node, i);
 630       ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
 631     }
 632
 633     res = ta;
 634   } break;
 635
 636   case (iro_Alloc): {
 637     type *type = get_Alloc_type (node);
 638     res = ta_exact (type);
 639   } break;
 640
 641   case (iro_Call): {
 642     /* presumably call (sel (proj (call))) */
 643     ir_node *ptr = get_Call_ptr (node);
 644     entity *meth = NULL;
 645     if (iro_Sel == get_irn_opcode (ptr)) {
 646       meth = get_Sel_entity (ptr);
 647     } else if (iro_SymConst == get_irn_opcode (ptr)) {
 648       if (get_SymConst_kind (ptr) == symconst_addr_ent) {
 649         meth = get_SymConst_entity (ptr);
 650       } else {
 651         meth = NULL;            /* WTF? */
 652       }
 653     }
 654
 655     if (NULL != meth) {
 656       type *tp = get_method_res_type ((type*) meth, 0);
 657       res = ta_type (tp);
 658     } else {
 659       /* could be anything */
 660       /* fprintf (stdout, "meth= (null)"); */
 661       res = NULL;
 662     }
 663
 664     fprintf (stdout, "]\n");
 665
 666   } break;
 667
 668   case (iro_SymConst): {
 669     if (get_SymConst_kind (node) == symconst_type_tag) {
 670       type *tp = get_SymConst_type (node);
 671
 672       res = ta_type (tp);
 673     } else if (get_SymConst_kind (node) == symconst_addr_ent) {
 674       entity *ent = get_SymConst_entity (node);
 675       type *tp = get_entity_type (ent);
 676       tp = get_pointer_points_to_type (tp);
 677       assert (is_class_type (tp));
 678
 679       res = ta_type (tp);       /* can't use ta_exact */
 680     } else {
 681       fprintf (stdout, "can't handle SymConst %s?\n",
 682                get_op_name (get_irn_op (node)));
 683       res = NULL;
 684     }
 685   } break;
 686
 687   /* template:
 688      case (iro_Cast): {}
 689      break;
 690   */
 691
 692   default: {
 693     fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
 694     assert (0);
 695   } break;
 696   }
 697
 698   return (res);
 699 }
 700
 701
 702
 703
 704 \f
 705 /*
 706   $Log$
 707   Revision 1.2  2004/10/22 09:53:10  liekweg
 708   Correctly handle proj_args
 709
 710   Revision 1.1  2004/10/21 11:09:37  liekweg
 711   Moved memwalk stuf into irmemwalk
 712   Moved lset stuff into lset
 713   Moved typalise stuff into typalise
 714
 715
 716  */