nsz Git - libfirm/blob - ir/ana/height.c

   1
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4
   5 #include "list.h"
   6
   7 #include "irdump.h"
   8 #include "irgwalk.h"
   9 #include "irtools.h"
  10 #include "irphase_t.h"
  11 #include "iredges_t.h"
  12
  13 typedef struct _heights_t heights_t;
  14
  15 struct _heights_t {
  16         phase_t ph;
  17         unsigned visited;
  18         void *dump_handle;
  19         struct list_head sink_head;
  20 };
  21
  22 typedef struct {
  23         unsigned height;
  24         unsigned visited;
  25         unsigned is_sink : 1;
  26         struct list_head sink_list;
  27 } irn_height_t;
  28
  29 static void irn_height_init(const phase_t *ph, const ir_node *irn, void *data)
  30 {
  31         irn_height_t *h = data;
  32         memset(h, 0, sizeof(h[0]));
  33         INIT_LIST_HEAD(&h->sink_list);
  34 }
  35
  36 static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
  37 {
  38         heights_t *heights = data;
  39         irn_height_t *h    = phase_get_irn_data(&heights->ph, irn);
  40
  41         if(h)
  42                 fprintf(f, "height: %u\n", h->height);
  43 }
  44
  45 /**
  46  * Check, if we can reach a target node from a given node inside one basic block.
  47  * @param h    The heights object.
  48  * @param curr The current node from which we tried to reach the other one.
  49  * @param tgt  The node we try to reach.
  50  * @return     1, one of tgt can be reached from curr, 0 else.
  51  */
  52 static int search(heights_t *h, const ir_node *curr, const ir_node *tgt)
  53 {
  54         irn_height_t *h_curr;
  55         irn_height_t *h_tgt;
  56         int i, n;
  57
  58         /* if the current node is the one we were looking for, we're done. */
  59         if(curr == tgt)
  60                 return 1;
  61
  62         /* If we are in another block we won't find our target. */
  63         if(get_nodes_block(curr) != get_nodes_block(tgt))
  64                 return 0;
  65
  66         /* Check, if we have already been here. Coming more often won't help :-) */
  67         h_curr = phase_get_irn_data(&h->ph, curr);
  68         if(h_curr->visited >= h->visited)
  69                 return 0;
  70
  71         /* If we are too deep into the DAG we won't find the target either. */
  72         h_tgt = phase_get_irn_data(&h->ph, tgt);
  73         if(h_curr->height > h_tgt->height)
  74                 return 0;
  75
  76         /* Mark this place as visited. */
  77         h_curr->visited = h->visited;
  78
  79         /* Start a search from this node. */
  80         for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
  81                 ir_node *op = get_irn_n(curr, i);
  82                 if(search(h, op, tgt))
  83                         return 1;
  84         }
  85
  86         return 0;
  87 }
  88
  89 /**
  90  * Check, if one node can be reached from another one, according to data dependence.
  91  */
  92 int heights_reachable_in_block(heights_t *h, const ir_node *n, const ir_node *m)
  93 {
  94         int res          = 0;
  95         irn_height_t *hn = phase_get_irn_data(&h->ph, n);
  96         irn_height_t *hm = phase_get_irn_data(&h->ph, m);
  97
  98         assert(get_nodes_block(n) == get_nodes_block(m));
  99         assert(hn != NULL && hm != NULL);
 100
 101         if(hn->height <= hm->height) {
 102                 h->visited++;
 103                 res = search(h, n, m);
 104         }
 105
 106         return res;
 107 }
 108
 109 /**
 110  * Compute the height of a node in a block.
 111  * @param h   The heights object.
 112  * @param irn The node.
 113  * @param bl  The block.
 114  */
 115 static unsigned compute_height(heights_t *h, const ir_node *irn, const ir_node *bl)
 116 {
 117         irn_height_t *ih = phase_get_or_set_irn_data(&h->ph, irn);
 118         int is_sink;
 119
 120         const ir_edge_t *edge;
 121
 122         /* bail out if we already visited that node. */
 123         if(ih->visited >= h->visited)
 124                 return ih->height;
 125
 126         ih->visited = h->visited;
 127         ih->height  = 0;
 128
 129         is_sink = 1;
 130
 131         foreach_out_edge(irn, edge) {
 132                 ir_node *dep = get_edge_src_irn(edge);
 133
 134                 if(!is_Block(dep) && get_nodes_block(dep) == bl) {
 135                         unsigned dep_height = compute_height(h, dep, bl);
 136                         ih->height          = MAX(ih->height, dep_height);
 137                         is_sink             = 0;
 138                 }
 139
 140                 ih->height++;
 141         }
 142
 143         ih->is_sink = is_sink;
 144         if(is_sink)
 145                 list_add(&ih->sink_list, &h->sink_head);
 146
 147         return ih->height;
 148 }
 149
 150 static void compute_heights_in_block(ir_node *bl, void *data)
 151 {
 152         heights_t *h = data;
 153         const ir_edge_t *edge;
 154
 155         h->visited++;
 156
 157         foreach_out_edge(bl, edge) {
 158                 ir_node *dep = get_edge_src_irn(edge);
 159                 compute_height(h, dep, bl);
 160         }
 161 }
 162
 163 unsigned get_irn_height(heights_t *heights, const ir_node *irn)
 164 {
 165         irn_height_t *h = phase_get_irn_data(&heights->ph, irn);
 166         assert(h && "No height information for node");
 167         return h->height;
 168 }
 169
 170 void heights_recompute(heights_t *h)
 171 {
 172         edges_assure(phase_get_irg(&h->ph));
 173         phase_reinit_irn_data(&h->ph);
 174         h->visited = 0;
 175         INIT_LIST_HEAD(&h->sink_head);
 176         irg_block_walk_graph(phase_get_irg(&h->ph), compute_heights_in_block, NULL, h);
 177 }
 178
 179 heights_t *heights_new(ir_graph *irg)
 180 {
 181         heights_t *res = xmalloc(sizeof(res[0]));
 182         phase_init(&res->ph, "heights", irg, sizeof(irn_height_t), PHASE_DEFAULT_GROWTH, irn_height_init);
 183         res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
 184         heights_recompute(res);
 185
 186         return res;
 187 }
 188
 189 void heights_free(heights_t *h)
 190 {
 191         phase_free(&h->ph);
 192         dump_remv_node_info_callback(h->dump_handle);
 193         xfree(h);
 194 }