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