nsz Git - libfirm/blob - ir/ana/phiclass.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 "debug.h"
  11 #include "irprog.h"
  12 #include "irgwalk.h"
  13 #include "irop.h"
  14 #include "phiclass_t.h"
  15
  16 #define DEBUG_LVL 0
  17
  18 size_t phi_irn_data_offset = 0;
  19 static firm_dbg_module_t *dbgphi = NULL;
  20
  21 #define _get_phi(irn)            get_irn_phi_info(irn)->phi
  22 #define _set_phi(irn,p)          get_irn_phi_info(irn)->phi = p
  23 #define _get_phi_class(irn)      get_irn_phi_info(irn)->phi_class
  24 #define _set_phi_class(irn,cls)  get_irn_phi_info(irn)->phi_class = cls
  25
  26 #define is_Const(n)       (get_irn_opcode(n) == iro_Const)
  27
  28
  29 /**
  30  * Insert a node to the phi class of a phi node
  31  * @param class The phi congruence class
  32  * @param phi The phi node holding the class
  33  * @param arg Node which gets assigned to the class
  34  */
  35 static INLINE void phi_class_insert(pset *class, ir_node *phi, ir_node *member) {
  36         DBG((dbgphi, 1, "\tinsert %n in %n\n", member, phi));
  37         if (!(is_Const(member) && CONSTS_SPLIT_PHI_CLASSES))
  38                 _set_phi(member, phi);
  39         pset_insert_ptr(class, member);
  40 }
  41
  42 /**
  43  * Unites two 'phi classes' represented by two phi nodes.
  44  * @param n Phi node representing phi class to reassign
  45  * @param new_tgt Phi node, which will hold the new bigger phi class
  46  */
  47 static void phi_class_union(ir_node *n, ir_node *new_tgt) {
  48         ir_node *p;
  49         pset *src, *tgt;
  50
  51         assert(is_Phi(n) && is_Phi(new_tgt) && "These must be phi nodes.");
  52         DBG((dbgphi, 1, "\tcorrect %n\n", n));
  53
  54         /* copy all class members from n to new_tgt. Duplicates eliminated by pset */
  55         src = _get_phi_class(n);
  56         tgt = _get_phi_class(new_tgt);
  57         for (p = (ir_node *)pset_first(src); p; p = (ir_node *)pset_next(src))
  58                 phi_class_insert(tgt, new_tgt, p);
  59
  60         /* phi class of n is no longer needed */
  61         del_pset(src);
  62         _set_phi_class(n, NULL);
  63 }
  64
  65 /**
  66  * Determines the phi congruence class of a phi node.
  67  * This will assign a phi class to all operands of this
  68  * phi node. Exceptions may be const nodes: See CONSTS_SPLIT_PHI_CLASSES
  69  */
  70 static void phi_class_det(ir_node *curr_phi) {
  71         pset *pc;
  72         int i, n;
  73         assert(is_Phi(curr_phi) && "This must be a phi node.");
  74         DBG((dbgphi, 1, "Det. phi class of %n.\n", curr_phi));
  75
  76         pc = _get_phi_class(curr_phi);
  77         if (!pc) {
  78                 pc = pset_new_ptr(2);
  79                 _set_phi_class(curr_phi, pc);
  80                 phi_class_insert(pc, curr_phi, curr_phi);
  81         }
  82
  83         for (i = 0, n = get_irn_arity(curr_phi); i < n; i++) {
  84                 ir_node *arg, *phi;
  85
  86                 arg = get_irn_n(curr_phi, i);
  87                 DBG((dbgphi, 1, "    Arg %n\n", arg));
  88
  89                 phi = _get_phi(arg);
  90                 if (phi == NULL) { /* Argument is not assigned to another phi class. */
  91                         phi_class_insert(pc, curr_phi, arg);
  92                 } else if (phi != curr_phi) {
  93                         assert(!(is_Const(arg) && CONSTS_SPLIT_PHI_CLASSES) && "Const nodes must not have a phi class assigned. See CONSTS_SPLIT_PHI_CLASSES");
  94                         phi_class_union(phi, curr_phi);
  95                 }
  96         }
  97         DBG((dbgphi, 1, "Size now: %d\n", pset_count(_get_phi_class(curr_phi))));
  98 }
  99
 100 pset *phi_class_compute_by_phis(pset *all_phi_nodes) {
 101         int i;
 102         ir_node *phi;
 103         pset *phi_class, *all_phi_classes;
 104
 105         /* determine all phi classes */
 106         for (i = 0, phi = (ir_node *)pset_first(all_phi_nodes); phi; phi = (ir_node *)pset_next(all_phi_nodes))
 107                 phi_class_det(phi);
 108
 109         /* store them in a pset for fast retrieval */
 110         all_phi_classes = pset_new_ptr(64);
 111         for (i = 0, phi = (ir_node *)pset_first(all_phi_nodes); phi; phi = (ir_node *)pset_next(all_phi_nodes)) {
 112                 phi_class = _get_phi_class(phi);
 113                 if (phi_class)
 114                         pset_insert_ptr(all_phi_classes, phi_class);
 115         }
 116
 117         return all_phi_classes;
 118 }
 119
 120 static void phi_class_construction_walker(ir_node *node, void *env) {
 121         if (is_Phi(node) && mode_is_datab(get_irn_mode(node)))
 122                 phi_class_det(node);
 123 }
 124
 125 void phi_class_compute(ir_graph *irg) {
 126         irg_walk_graph(irg, phi_class_construction_walker, NULL, NULL);
 127 }
 128
 129 static void phi_class_destruction_walker(ir_node *node, void *env) {
 130         if (is_Phi(node) && mode_is_datab(get_irn_mode(node))) {
 131                 pset *clss = _get_phi_class(node);
 132                 if (clss) {
 133                         del_pset(clss);
 134                         clss = NULL;
 135                 }
 136         }
 137 }
 138
 139 void phi_class_free(ir_graph *irg) {
 140         irg_walk_graph(irg, phi_class_destruction_walker, NULL, NULL);
 141 }
 142
 143 pset *get_phi_class(const ir_node *irn) {
 144         ir_node *phi;
 145         if (phi = _get_phi(irn), phi)
 146                 return _get_phi_class(phi);
 147         else
 148                 return NULL;
 149 }
 150
 151 void phi_class_init(void) {
 152         dbgphi = firm_dbg_register("ir.ana.phiclass");
 153         firm_dbg_set_mask(dbgphi, DEBUG_LVL);
 154         phi_irn_data_offset = register_additional_node_data(sizeof(phi_info_t));
 155 }