2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Implementation of cdep
9 * @author Christoph Mallon
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. */
29 static cdep_info *cdep_data;
31 ir_node *(get_cdep_node)(const ir_cdep *cdep)
33 return _get_cdep_node(cdep);
36 ir_cdep *(get_cdep_next)(const ir_cdep *cdep)
38 return _get_cdep_next(cdep);
41 ir_cdep *find_cdep(const ir_node *block)
43 assert(is_Block(block));
44 return pmap_get(ir_cdep, cdep_data->cdep_map, block);
47 void exchange_cdep(ir_node *old, const ir_node *nw)
49 ir_cdep *cdep = find_cdep(nw);
50 assert(is_Block(old));
51 pmap_insert(cdep_data->cdep_map, old, cdep);
55 * Adds a control dependence from node to dep_on.
57 static void add_cdep(ir_node *node, ir_node *dep_on)
59 ir_cdep *dep = find_cdep(node);
61 assert(is_Block(dep_on));
63 ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
65 newdep->node = dep_on;
67 pmap_insert(cdep_data->cdep_map, node, newdep);
72 if (get_cdep_node(dep) == dep_on) return;
73 if (dep->next == NULL) break;
76 newdep = OALLOC(&cdep_data->obst, ir_cdep);
77 newdep->node = dep_on;
84 * Pre-block-walker: calculate the control dependence
86 static void cdep_pre(ir_node *node, void *ctx)
90 for (int i = get_Block_n_cfgpreds(node); i-- != 0;) {
91 ir_node *pred = get_Block_cfgpred_block(node, i);
95 if (is_Bad(pred)) continue;
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);
107 * A block edge hook: add all cdep edges of block.
109 static int cdep_edge_hook(FILE *F, ir_node *block)
113 for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
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)
125 void compute_cdep(ir_graph *irg)
128 cdep_data = XMALLOC(cdep_info);
129 obstack_init(&cdep_data->obst);
131 cdep_data->cdep_map = pmap_create();
133 assure_postdoms(irg);
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.
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);
144 irg_block_walk_graph(irg, cdep_pre, NULL, NULL);
146 (void) cdep_edge_hook;
148 /* restore the post dominator relation */
149 set_Block_ipostdom(start_block, rem);
152 void free_cdep(ir_graph *irg)
155 if (cdep_data != NULL) {
156 pmap_destroy(cdep_data->cdep_map);
157 obstack_free(&cdep_data->obst, NULL);
163 int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
167 for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
168 if (get_cdep_node(dep) == candidate) return 1;
173 ir_node *get_unique_cdep(const ir_node *block)
175 ir_cdep *cdep = find_cdep(block);
177 return cdep != NULL && cdep->next == NULL ? get_cdep_node(cdep) : NULL;
180 int has_multiple_cdep(const ir_node *block)
182 ir_cdep *cdep = find_cdep(block);
184 return cdep != NULL && cdep->next != NULL;