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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Implementation of cdep
   9  * @author  Christoph Mallon
  10  */
  11 #include <assert.h>
  12 #include <stdlib.h>
  13 #include "irdom_t.h"
  14 #include "irgraph.h"
  15 #include "irgwalk.h"
  16 #include "irnode.h"
  17 #include "pmap.h"
  18 #include "obst.h"
  19 #include "xmalloc.h"
  20 #include "cdep_t.h"
  21 #include "irprintf.h"
  22 #include "irdump.h"
  23
  24 typedef struct cdep_info {
  25         pmap   *cdep_map;     /**< A map to find the list of all control dependence nodes for a block. */
  26         struct obstack obst;  /**< An obstack where all cdep data lives on. */
  27 } cdep_info;
  28
  29 static cdep_info *cdep_data;
  30
  31 ir_node *(get_cdep_node)(const ir_cdep *cdep)
  32 {
  33         return _get_cdep_node(cdep);
  34 }
  35
  36 ir_cdep *(get_cdep_next)(const ir_cdep *cdep)
  37 {
  38         return _get_cdep_next(cdep);
  39 }
  40
  41 ir_cdep *find_cdep(const ir_node *block)
  42 {
  43         assert(is_Block(block));
  44         return pmap_get(ir_cdep, cdep_data->cdep_map, block);
  45 }
  46
  47 void exchange_cdep(ir_node *old, const ir_node *nw)
  48 {
  49         ir_cdep *cdep = find_cdep(nw);
  50         assert(is_Block(old));
  51         pmap_insert(cdep_data->cdep_map, old, cdep);
  52 }
  53
  54 /**
  55  * Adds a control dependence from node to dep_on.
  56  */
  57 static void add_cdep(ir_node *node, ir_node *dep_on)
  58 {
  59         ir_cdep *dep = find_cdep(node);
  60
  61         assert(is_Block(dep_on));
  62         if (dep == NULL) {
  63                 ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
  64
  65                 newdep->node = dep_on;
  66                 newdep->next = NULL;
  67                 pmap_insert(cdep_data->cdep_map, node, newdep);
  68         } else {
  69                 ir_cdep *newdep;
  70
  71                 for (;;) {
  72                         if (get_cdep_node(dep) == dep_on) return;
  73                         if (dep->next == NULL) break;
  74                         dep = dep->next;
  75                 }
  76                 newdep = OALLOC(&cdep_data->obst, ir_cdep);
  77                 newdep->node = dep_on;
  78                 newdep->next = NULL;
  79                 dep->next = newdep;
  80         }
  81 }
  82
  83 /**
  84  * Pre-block-walker: calculate the control dependence
  85  */
  86 static void cdep_pre(ir_node *node, void *ctx)
  87 {
  88         (void)ctx;
  89
  90         for (int i = get_Block_n_cfgpreds(node); i-- != 0;) {
  91                 ir_node *pred = get_Block_cfgpred_block(node, i);
  92                 ir_node *pdom;
  93                 ir_node *dependee;
  94
  95                 if (is_Bad(pred)) continue;
  96
  97                 pdom = get_Block_ipostdom(pred);
  98                 for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
  99                         assert(!is_Bad(pdom));
 100                         add_cdep(dependee, pred);
 101                 }
 102         }
 103 }
 104
 105
 106 /**
 107  * A block edge hook: add all cdep edges of block.
 108  */
 109 static int cdep_edge_hook(FILE *F, ir_node *block)
 110 {
 111         ir_cdep *cd;
 112
 113         for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
 114                 fprintf(
 115                         F,
 116                         "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
 117                         "linestyle:dashed color:gold}\n",
 118                         get_irn_node_nr(block), get_irn_node_nr(cd->node)
 119                 );
 120         }
 121
 122         return 0;
 123 }
 124
 125 void compute_cdep(ir_graph *irg)
 126 {
 127         free_cdep(irg);
 128         cdep_data = XMALLOC(cdep_info);
 129         obstack_init(&cdep_data->obst);
 130
 131         cdep_data->cdep_map = pmap_create();
 132
 133         assure_postdoms(irg);
 134
 135         /* we must temporary change the post dominator relation:
 136            the ipdom of the startblock is the end block.
 137            Firm does NOT add the phantom edge from Start to End.
 138          */
 139         ir_node *const start_block = get_irg_start_block(irg);
 140         ir_node *const end_block   = get_irg_end_block(irg);
 141         ir_node *const rem         = get_Block_ipostdom(start_block);
 142         set_Block_ipostdom(start_block, end_block);
 143
 144         irg_block_walk_graph(irg, cdep_pre, NULL, NULL);
 145
 146         (void) cdep_edge_hook;
 147
 148         /* restore the post dominator relation */
 149         set_Block_ipostdom(start_block, rem);
 150 }
 151
 152 void free_cdep(ir_graph *irg)
 153 {
 154         (void) irg;
 155         if (cdep_data != NULL) {
 156                 pmap_destroy(cdep_data->cdep_map);
 157                 obstack_free(&cdep_data->obst, NULL);
 158                 xfree(cdep_data);
 159                 cdep_data = NULL;
 160         }
 161 }
 162
 163 int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
 164 {
 165         const ir_cdep *dep;
 166
 167         for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
 168                 if (get_cdep_node(dep) == candidate) return 1;
 169         }
 170         return 0;
 171 }
 172
 173 ir_node *get_unique_cdep(const ir_node *block)
 174 {
 175         ir_cdep *cdep = find_cdep(block);
 176
 177         return cdep != NULL && cdep->next == NULL ? get_cdep_node(cdep) : NULL;
 178 }
 179
 180 int has_multiple_cdep(const ir_node *block)
 181 {
 182         ir_cdep *cdep = find_cdep(block);
 183
 184         return cdep != NULL && cdep->next != NULL;
 185 }