nsz Git - libfirm/blob - ir/be/bephicongr.c

   1 /**
   2  * @author Daniel Grund
   3  * @date 09.12.2004
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 #include "config.h"
  11 #include "irgraph.h"
  12 #include "irnode.h"
  13 #include "irop.h"
  14 #include "irprog.h"
  15 #include "debug.h"
  16 #include "pset.h"
  17
  18 #include "bephicongr_t.h"
  19 #include "beutil.h"
  20
  21
  22 pset *all_phi_classes = NULL;
  23
  24 size_t phi_irn_data_offset = 0;
  25 static firm_dbg_module_t *dbgmod = NULL;
  26
  27 void be_phi_congr_class_init(void) {
  28         dbgmod = firm_dbg_register("Phi congruence classes");
  29         firm_dbg_set_mask(dbgmod, 1);
  30         phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t));
  31 }
  32
  33 #define get_phi(irn)            get_irn_phi_info(irn)->phi
  34 #define set_phi(irn, p)         get_irn_phi_info(irn)->phi = p
  35 #define set_phi_class(irn, cls) get_irn_phi_info(irn)->phi_class = cls
  36
  37 #define is_Const(n)       (get_irn_opcode(n) == iro_Const)
  38
  39
  40 /**
  41  * Insert a node to the phi class of a phi node
  42  * @param class The phi congruence class
  43  * @param phi The phi node holding the class
  44  * @param arg Node which gets assigned to the class
  45  */
  46 static INLINE void phi_class_insert(pset *class, ir_node *phi, ir_node *member) {
  47         DBG((dbgmod, 1, "\tinsert %n in %n\n", member, phi));
  48         if (!(is_Const(member) && CONSTS_SPLIT_PHI_CLASSES))
  49                 set_phi(member, phi);
  50         pset_insert_ptr(class, member);
  51 }
  52
  53
  54 /**
  55  * Unites two phi classes repesented by two phi nodes.
  56  * @param n Phi node representing phi class to reassign
  57  * @param new_tgt Phi node, which will hold the new bigger phi class
  58  */
  59 static void phi_class_union(ir_node *n, ir_node *new_tgt) {
  60         ir_node *p;
  61         pset *src, *tgt;
  62
  63     assert(is_Phi(n) && is_Phi(new_tgt) && "These must be phi nodes.");
  64         DBG((dbgmod, 1, "\tcorrect %n\n", n));
  65
  66         /* copy all class members from n to new_tgt. Duplicates eliminated by pset */
  67         src = get_phi_class(n);
  68         tgt = get_phi_class(new_tgt);
  69         for (p = (ir_node *)pset_first(src); p; p = (ir_node *)pset_next(src))
  70                 phi_class_insert(tgt, new_tgt, p);
  71
  72         /* phi class of n is no longer needed */
  73         del_pset(src);
  74         set_phi_class(n, NULL);
  75 }
  76
  77
  78 /**
  79  * Determines the phi congruence class of a phi node.
  80  * This will assign a phi class to all operands of this
  81  * phi node. Exceptions may be const nodes: See CONSTS_SPLIT_PHI_CLASSES
  82  */
  83 static void det_phi_congr_class(ir_node *curr_phi) {
  84         pset *pc;
  85     int i, n;
  86     assert(is_Phi(curr_phi) && "This must be a phi node.");
  87     DBG((dbgmod, 1, "Det. phi class of %n.\n", curr_phi));
  88
  89         pc = get_phi_class(curr_phi);
  90         if (!pc) {
  91                 pc = pset_new_ptr(2);
  92                 set_phi_class(curr_phi, pc);\
  93                 phi_class_insert(pc, curr_phi, curr_phi);
  94         }
  95
  96         for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) {
  97                 ir_node *arg, *phi;
  98
  99                 arg = get_irn_n(curr_phi, i);
 100                 DBG((dbgmod, 1, "    Arg %n\n", arg));
 101
 102                 phi = get_phi(arg);
 103                 if (phi == NULL) { /* Argument is not assigned to another phi class. */
 104                         phi_class_insert(pc, curr_phi, arg);
 105                 } else if (phi != curr_phi) {
 106                         assert(!(is_Const(arg) && CONSTS_SPLIT_PHI_CLASSES) && "Const nodes must not have a phi class assigned. See CONSTS_SPLIT_PHI_CLASSES");
 107                         phi_class_union(phi, curr_phi);
 108                 }
 109         }
 110         DBG((dbgmod, 1, "Size now: %d\n", pset_count(get_phi_class(curr_phi))));
 111 }
 112
 113
 114 /**
 115  * Determines the phi congruence classes of
 116  * all phi nodes in a given pset
 117  */
 118 void be_phi_congr_classes(pset *phis) {
 119         int i;
 120         ir_node *phi;
 121         pset *phi_class;
 122
 123         /* determine all phi classes */
 124         for (i = 0, phi = (ir_node *)pset_first(phis); phi; phi = (ir_node *)pset_next(phis))
 125                 det_phi_congr_class(phi);
 126
 127         /* store them in a pset for fast retrieval */
 128         all_phi_classes = pset_new_ptr(64);
 129         for (i = 0, phi = (ir_node *)pset_first(phis); phi; phi = (ir_node *)pset_next(phis)) {
 130                 phi_class = get_phi_class(phi);
 131                 if (phi_class)
 132                         pset_insert_ptr(all_phi_classes, phi_class);
 133         }
 134 }