From c13d7d771c9b2a78ceaefa7b5ad6c6814fcec758 Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Thu, 28 Feb 2002 13:33:52 +0000 Subject: [PATCH] block walk in irouts. irdom implemented: dominator information. [r321] --- ir/ana/Makefile.in | 4 +- ir/ana/irdom.c | 448 ++++++++++++++++++++++++++++++++++++++++++ ir/ana/irdom.h | 58 ++++++ ir/ana/irdom_t.h | 23 +++ ir/ana/irouts.c | 97 ++++++++- ir/ana/irouts.h | 12 +- ir/common/Makefile.in | 3 +- ir/common/common.h | 1 + ir/ir/irdump.c | 30 ++- ir/ir/irdump.h | 22 ++- ir/ir/irgraph.c | 9 + ir/ir/irgraph.h | 17 +- ir/ir/irgraph_t.h | 1 + ir/ir/irnode.c | 7 + ir/ir/irnode.h | 2 + ir/ir/irnode_t.h | 7 + ir/ir/iropt.c | 28 ++- 17 files changed, 749 insertions(+), 20 deletions(-) create mode 100644 ir/ana/irdom.c create mode 100644 ir/ana/irdom.h create mode 100644 ir/ana/irdom_t.h diff --git a/ir/ana/Makefile.in b/ir/ana/Makefile.in index 73b28e394..89800f918 100644 --- a/ir/ana/Makefile.in +++ b/ir/ana/Makefile.in @@ -10,12 +10,12 @@ srcdir = @srcdir@ topdir = ../.. subdir := ir/ana -INSTALL_HEADERS = irouts.h +INSTALL_HEADERS = irouts.h irdom.h SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in \ - irouts.c + irouts.c irdom_t.h irdom.c include $(topdir)/MakeRules diff --git a/ir/ana/irdom.c b/ir/ana/irdom.c new file mode 100644 index 000000000..54ffcf59d --- /dev/null +++ b/ir/ana/irdom.c @@ -0,0 +1,448 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irdom.c --- Dominator tree. +** +*/ + +/* $Id$ */ + +#include "irouts.h" + +#include "irdom_t.h" +#include "irgraph_t.h" /* To access state field. */ +#include "irnode_t.h" + +/**********************************************************************/ +/** Accessing the dominator datastructures **/ +/**********************************************************************/ + +ir_node *get_Block_idom(ir_node *bl) { + assert(get_irn_op(bl) == op_Block); + return bl->attr.block.dom.idom; +} + +void set_Block_idom(ir_node *bl, ir_node *n) { + assert(get_irn_op(bl) == op_Block); + bl->attr.block.dom.idom = n; +} + +int get_Block_pre_num(ir_node *bl) { + assert(get_irn_op(bl) == op_Block); + return bl->attr.block.dom.pre_num; +} + +void set_Block_pre_num(ir_node *bl, int num) { + assert(get_irn_op(bl) == op_Block); + bl->attr.block.dom.pre_num = num; +} + +int get_Block_dom_depth(ir_node *bl) { + assert(get_irn_op(bl) == op_Block); + return bl->attr.block.dom.dom_depth; +} + +void set_Block_dom_depth(ir_node *bl, int depth) { + assert(get_irn_op(bl) == op_Block); + bl->attr.block.dom.dom_depth = depth; +} + + + +/**********************************************************************/ +/** Building and Removing the dominator datasturcture **/ +/** **/ +/** **/ +/** **/ +/** **/ +/** **/ +/** **/ +/** **/ +/** .**/ +/** **/ +/** **/ +/** **/ +/** **/ +/** **/ +/** **/ +/**********************************************************************/ + +void count_and_init_blocks(ir_node *bl, void *env) { + int *n_blocks = (int *) env; + (*n_blocks) ++; + + set_Block_idom(bl, NULL); + set_Block_pre_num(bl, -1); + set_Block_dom_depth(bl, -1); +} + +/* temporary type used while constructing the dominator tree. */ +typedef struct tmp_dom_info { + ir_node *block; /* backlink */ + + struct tmp_dom_info *semi; /* semidominator */ + struct tmp_dom_info *parent; + struct tmp_dom_info *label; /* used for LINK and EVAL */ + struct tmp_dom_info *ancestor;/* used for LINK and EVAL */ + struct tmp_dom_info *dom; /* After step 3, if the semidominator of w is + its immediate dominator, then w->dom is the + immediate dominator of w. Otherwise w->dom + is a vertex v whose number is smaller than + w and whose immediate dominator is also w's + immediate dominator. After step 4, w->dom + is the immediate dominator of w. */ + struct tmp_dom_info *bucket; /* set of vertices with same semidominator */ +} tmp_dom_info; + +/* Struct to pass info through walker. */ +typedef struct { + tmp_dom_info *d; + int used; + +} dom_env; + +void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent, tmp_dom_info *tdi_list, int* used) { + tmp_dom_info *tdi; + int i; + + assert(get_irn_op(bl) == op_Block); + if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl)) return; + mark_Block_block_visited(bl); + set_Block_pre_num(bl, *used); + + //printf(" used: %d ", *used); DDMN(bl); + + tdi = &tdi_list[*used]; + ++(*used); + + tdi->semi = tdi; + tdi->label = tdi; + tdi->ancestor = NULL; + tdi->bucket = NULL; + tdi->parent = parent; + tdi->block = bl; + + /* Iterate */ + for(i = 0; i < get_Block_n_cfg_outs(bl); i++) { + ir_node *pred = get_Block_cfg_out(bl, i); + assert(get_irn_opcode(pred) == iro_Block); + init_tmp_dom_info(pred, tdi, tdi_list, used); + } +} + + +static void +dom_compress (tmp_dom_info *v) +{ + assert (v->ancestor); + if (v->ancestor->ancestor) { + dom_compress (v->ancestor); + if (v->ancestor->label->semi < v->label->semi) { + v->label = v->ancestor->label; + } + v->ancestor = v->ancestor->ancestor; + } +} + +/* if V is a root, return v, else return the vertex u, not being the + root, with minimum u->semi on the path from v to its root. */ +inline static tmp_dom_info* +dom_eval (tmp_dom_info *v) +{ + if (!v->ancestor) return v; + dom_compress (v); + return v->label; +} + +/* make V W's ancestor */ +inline static void +dom_link (tmp_dom_info *v, tmp_dom_info *w) +{ + w->ancestor = v; +} + +/* Computes the dominator trees. Sets a flag in irg to "dom_consistent". + If the control flow of the graph is changed this flag must be set to + "dom_inconsistent". */ +void compute_doms(ir_graph *irg) { + ir_graph *rem = current_ir_graph; + int n_blocks, used, i, j; + tmp_dom_info *tdi_list; /* Ein Golf? */ + dom_env de; + + current_ir_graph = irg; + + /* Update graph state */ + assert(get_irg_phase_state(current_ir_graph) != phase_building); + current_ir_graph->dom_state = dom_consistent; + + /* Count the number of blocks in the graph. */ + n_blocks = 0; + irg_block_walk(get_irg_end(current_ir_graph), count_and_init_blocks, NULL, &n_blocks); + + //printf("n_blocks is %d\n", n_blocks); + + /* Memory for temporary information. */ + tdi_list = (tmp_dom_info *) calloc(n_blocks, sizeof(tmp_dom_info)); + + /* We need the out datastructure. */ + if (current_ir_graph->outs_state != outs_consistent) + compute_outs(current_ir_graph); + + /** Initialize the temporary information, add link to parent. We don't do + this with a standard walker as passing the parent to the sons isn't + simple. **/ + used = 0; + inc_irg_block_visited(current_ir_graph); + init_tmp_dom_info(get_irg_start_block(current_ir_graph), NULL, tdi_list, &used); + /* If not all blocks are reachable from Start by out edges this assertion + fails. */ + //assert(used == n_blocks && "Precondition for dom construction violated"); + n_blocks = used; + + //printf("used is %d\n", used); + + + for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */ + tmp_dom_info *w = &tdi_list[i]; + tmp_dom_info *v; + + //printf(" cfgpreds: %d ", get_Block_n_cfgpreds(w->block)); DDMN(w->block); + + /* Step 2 */ + for (j = 0; j < get_irn_arity(w->block); j++) { + ir_node *pred = get_nodes_Block(get_Block_cfgpred(w->block, j)); + tmp_dom_info *u; + + if ((is_Bad(pred)) || (get_Block_pre_num (pred) == -1)) + continue; /* control-dead */ + + u = dom_eval (&tdi_list[get_Block_pre_num(pred)]); + if (u->semi < w->semi) w->semi = u->semi; + } + /* Add w to w->semi's bucket. w is in exactly one bucket, so + buckets can ben implemented as linked lists. */ + w->bucket = w->semi->bucket; + w->semi->bucket = w; + + dom_link (w->parent, w); + + /* Step 3 */ + while (w->parent->bucket) { + tmp_dom_info *u; + v = w->parent->bucket; + /* remove v from w->parent->bucket */ + w->parent->bucket = v->bucket; + v->bucket = NULL; + + u = dom_eval (v); + if (u->semi < v->semi) + v->dom = u; + else + v->dom = w->parent; + } + } + /* Step 4 */ + tdi_list[0].dom = NULL; + set_Block_idom(tdi_list[0].block, NULL); + set_Block_dom_depth(tdi_list[0].block, 1); + for (i = 1; i < n_blocks; i++) { + tmp_dom_info *w = &tdi_list[i]; + + if (w->dom != w->semi) w->dom = w->dom->dom; + set_Block_idom(w->block, w->dom->block); + set_Block_dom_depth(w->block, get_Block_dom_depth(w->dom->block) + 1); + } + + /* clean up */ + free(tdi_list); + current_ir_graph = rem; +} + +void free_dom_and_peace(ir_graph *irg) { + /* Update graph state */ + assert(get_irg_phase_state(current_ir_graph) != phase_building); + current_ir_graph->dom_state = no_dom; + + /* @@@ free */ +} + + +#if 0 +/* Dominator Tree */ + +/* temporary type used while constructing the dominator tree. */ +typedef struct tmp_dom_info tmp_dom_info; +struct tmp_dom_info { + ir_node *region; + + tmp_dom_info *semi; /* semidominator */ + tmp_dom_info *parent; + tmp_dom_info *label; /* used for LINK and EVAL */ + tmp_dom_info *ancestor; /* used for LINK and EVAL */ + tmp_dom_info *dom; /* After step 3, if the semidominator + of w is its immediate dominator, then w->dom is the immediate + dominator of w. Otherwise w->dom is a vertex v whose number is + smaller than w and whose immediate dominator is also w's immediate + dominator. After step 4, w->dom is the immediate dominator of w. */ + tmp_dom_info *bucket; /* set of vertices with same semidominator */ +}; + +static int +dom_count_regions (ir_node *n) +{ + int i, count = 1; + + n->visit = ir_visited; + + for (i = IR_ARITY (n); i > 0; --i) { + ir_node *pr = prev_region (n, i); + if (pr && pr->visit != ir_visited) { + count += dom_count_regions (pr); + } + } + return count; +} + +struct dt_desc { tmp_dom_info *dt; int used;}; + +static void +dom_setup (ir_node *n, tmp_dom_info *parent, struct dt_desc *dt_desc) +{ + tmp_dom_info *dt = &dt_desc->dt[dt_desc->used]; + int i; + + if (n->visit == ir_visited) return; + n->visit = ir_visited; + + assert (IR_CFG_NODE (n)); + + n->data.r.pre_num = dt_desc->used; + dt->semi = dt; + dt->label = dt; + dt->ancestor = NULL; + dt->bucket = NULL; + dt->parent = parent; + dt->region = n; + ++(dt_desc->used); + + for (i = 0; i < n->data.r.cfg_outs; ++i) { + dom_setup (n->data.r.cfg_out[i], dt, dt_desc); + } +} + +static void +dom_compress (tmp_dom_info *v) +{ + assert (v->ancestor); + if (v->ancestor->ancestor) { + dom_compress (v->ancestor); + if (v->ancestor->label->semi < v->label->semi) { + v->label = v->ancestor->label; + } + v->ancestor = v->ancestor->ancestor; + } +} + +/* if V is a root, return v, else return the vertex u, not being the + root, with minimum u->semi on the path from v to its root. */ +static tmp_dom_info* +dom_eval (tmp_dom_info *v) +{ + if (!v->ancestor) return v; + dom_compress (v); + return v->label; +} + +/* make V W's ancestor */ +static void +dom_link (tmp_dom_info *v, tmp_dom_info *w) +{ + w->ancestor = v; +} + +void +irg_gen_idom (ir_graph *irg) +{ + int regions, i; + tmp_dom_info *dt; + struct dt_desc dt_desc; + + if (!(irg->state & irgs_has_CFG)) irg_gen_out (irg); + + ++ir_visited; + regions = 0; + /* walk all the artificially kept alive parts of the CFG instead of + the CFG beginning from the Start just for fun and safety */ + keep_alives_in_arr (irg); + for (i = ARR_LEN (irg->keep.alive) - 1; i >= 0; --i) + if ( IR_CFG_NODE (irg->keep.alive[i]) + && irg->keep.alive[i]->visit != ir_visited) + regions += dom_count_regions (irg->keep.alive[i]); + + dt = alloca ((regions+1) * sizeof (tmp_dom_info)); + memset (dt, 0, (regions+1) * sizeof (tmp_dom_info)); + + /* Step 1 */ + dt_desc.dt = dt; + dt_desc.used = 1; + ++ir_visited; + dom_setup (irg->start, NULL, &dt_desc); + + /* This assert will fail, if not all Regions are reachable by + walking the CFG starting from Start, that is when there is + [control] dead code, violating the single entry precondition of + this algorithm. */ + assert (dt_desc.used == regions + 1); + + for (i = regions; i > 1; --i) { + tmp_dom_info *w = &dt[i]; + tmp_dom_info *v; + int j, r_ins; + + /* Step 2 */ + r_ins = IR_ARITY (w->region); + for (j = 1; j <= r_ins; ++j) { + ir_node *prev = prev_region (w->region, j); + tmp_dom_info *u; + + if (!prev) continue; /* control-dead */ + + u = dom_eval (&dt[prev->data.r.pre_num]); + if (u->semi < w->semi) w->semi = u->semi; + } + /* Add w to w->semi's bucket. w is in exactly one bucket, so + buckets can ben implemented as linked lists. */ + w->bucket = w->semi->bucket; + w->semi->bucket = w; + + dom_link (w->parent, w); + + /* Step 3 */ + while ((v = w->parent->bucket)) { + tmp_dom_info *u; + /* remove v from w->parent->bucket */ + w->parent->bucket = v->bucket; + v->bucket = NULL; + + u = dom_eval (v); + v->dom = u->semi < v->semi ? u : w->parent; + } + } + /* Step 4 */ + dt[1].dom = NULL; + dt[1].region->data.r.idom = NULL; + dt[1].region->data.r.dom_depth = 1; + for (i = 2; i <= regions; ++i) { + tmp_dom_info *w = &dt[i]; + + if (w->dom != w->semi) w->dom = w->dom->dom; + w->region->data.r.idom = w->dom->region; + w->region->data.r.dom_depth = w->dom->region->data.r.dom_depth + 1; + } + current_ir_graph = sirg; +} + +#endif diff --git a/ir/ana/irdom.h b/ir/ana/irdom.h new file mode 100644 index 000000000..b4ff1f19f --- /dev/null +++ b/ir/ana/irdom.h @@ -0,0 +1,58 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irdom.h: This file contains routines to construct and access dominator +** information. +** The dominator information is stored in three fields of block nodes: +** idom: a reference to the block that is the immediate dominator of +** this block. +** dom_depth: a number giving the depth of the block in the dominator +** tree. +** pre_num: Number in preorder traversal. +*/ + +/* $Id$ */ + +# ifndef _IRDOM_H_ +# define _IRDOM_H_ + +# include "irgraph.h" +# include "irnode.h" + + +/**********************************************************************/ +/** Accessing the dopminator datastructure. **/ +/** These routines only work properly if the ir_graph is in state **/ +/** outs_consistent or outs_inconsistent. **/ +/**********************************************************************/ + +ir_node *get_Block_idom(ir_node *bl); +void set_Block_idom(ir_node *bl, ir_node *n); + +int get_Block_dom_depth(ir_node *bl); +void set_Block_dom_depth(ir_node *bl, int depth); + +int get_Block_pre_num(ir_node *bl); +void set_Block_pre_num(ir_node *bl, int num); + + +/**********************************************************************/ +/* Building and Removing the dominator datasturcture **/ +/**********************************************************************/ + +/* Computes the dominator trees. Sets a flag in irg to "dom_consistent". + If the control flow of the graph is changed this flag must be set to + "dom_inconsistent". + Does not compute dominator information for control dead code. Blocks + not reachable from Start contain the following information: + idom = NULL; + dom_depth = -1; + pre_num = -1; */ +void compute_doms(ir_graph *irg); + +/* Frees the dominator datastructures. Sets the flag in irg to "no_dom". */ +void free_dom_and_peace(ir_graph *irg); + +#endif /* _IRDOM_H_ */ diff --git a/ir/ana/irdom_t.h b/ir/ana/irdom_t.h new file mode 100644 index 000000000..28dfd4038 --- /dev/null +++ b/ir/ana/irdom_t.h @@ -0,0 +1,23 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** irdom_t.h: private datastructures +*/ + +/* $Id$ */ + +# ifndef _IRDOM_T_H_ +# define _IRDOM_T_H_ + +#include "irdom.h" + +/* For dominator information */ +typedef struct dom_info { + struct ir_node *idom; /* immediate CFG dominator */ + int pre_num; /* pre-order graph-walk number */ + int dom_depth; /* depth in dominator-tree */ +} dom_info; + +#endif /* _IRDOM_T_H_ */ diff --git a/ir/ana/irouts.c b/ir/ana/irouts.c index b99169a72..3ae97c8dc 100644 --- a/ir/ana/irouts.c +++ b/ir/ana/irouts.c @@ -20,23 +20,48 @@ /**********************************************************************/ /* returns the number of successors of the node: */ -inline int get_irn_n_outs (ir_node *node) { +inline int get_irn_n_outs (ir_node *node) { return (int)(node->out[0]); } /* Access successor n */ -inline ir_node *get_irn_out (ir_node *node, int pos) { +inline ir_node *get_irn_out (ir_node *node, int pos) { assert(node); assert(pos >= 0 && pos < get_irn_n_outs(node)); return node->out[pos+1]; } -inline void set_irn_out (ir_node *node, int pos, ir_node *out) { +inline void set_irn_out (ir_node *node, int pos, ir_node *out) { assert(node && out); assert(pos >= 0 && pos < get_irn_n_outs(node)); node->out[pos+1] = out; } + +inline int get_Block_n_cfg_outs (ir_node *bl) { + int i, n_cfg_outs = 0; + assert(bl && (get_irn_op(bl) == op_Block)); + for (i = 0; i < (int)bl->out[0]; i++) + if ((get_irn_mode(bl->out[i+1]) == mode_X) && + (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++; + return n_cfg_outs; +} + + +inline ir_node *get_Block_cfg_out (ir_node *bl, int pos) { + int i, out_pos = 0; + assert(bl && (get_irn_op(bl) == op_Block)); + for (i = 0; i < (int)bl->out[0]; i++) + if (get_irn_mode(bl->out[i+1]) == mode_X) + if (out_pos == pos) { + ir_node *cfop = bl->out[i+1]; + return cfop->out[0+1]; + } else { + out_pos++; + } + return NULL; +} + void irg_out_walk_2(ir_node *node, void (pre)(ir_node*, void*), void (post)(ir_node*, void*), void *env) { int i; @@ -74,11 +99,50 @@ void irg_out_walk(ir_node *node, return; } +void irg_out_block_walk2(ir_node *bl, + void (pre)(ir_node*, void*), void (post)(ir_node*, void*), + void *env) { + int i, out_pos; + + assert(get_irn_opcode(bl) == iro_Block); + + if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) { + set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph)); + + if(pre) + pre(bl, env); + + for(i = 0; i < get_Block_n_cfg_outs(bl); i++) { + /* find the corresponding predecessor block. */ + ir_node *pred = get_Block_cfg_out(bl, i); + assert(get_irn_opcode(pred) == iro_Block); + /* recursion */ + irg_out_block_walk2(pred, pre, post, env); + } + + if(post) + post(bl, env); + } + return; +} + /* Walks only over Block nodes in the graph. Has it's own visited flag, so that it can be interleaved with the other walker. */ void irg_out_block_walk(ir_node *node, void (pre)(ir_node*, void*), void (post)(ir_node*, void*), void *env) { + + assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X)); + + inc_irg_block_visited(current_ir_graph); + + if (get_irn_mode(node) == mode_X) node = node->out[1]; + assert(get_irn_opcode(node) == iro_Block); + + irg_out_block_walk2(node, pre, post, env); + + return; + } /**********************************************************************/ @@ -111,7 +175,9 @@ int count_outs(ir_node *n) { if ((get_irn_op(n) == op_Block)) start = 0; else start = -1; res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */ for (i = start; i < get_irn_arity(n); i++) { - succ = get_irn_n(n, i); + /* Optimize Tuples. They annoy if walking the cfg. */ + succ = skip_Tuple(get_irn_n(n, i)); + set_irn_n(n, i, succ); /* count outs for successors */ if (get_irn_visited(succ) < get_irg_visited(current_ir_graph)) res += count_outs(succ); @@ -149,6 +215,22 @@ ir_node **set_out_edges(ir_node *n, ir_node **free) { return free; } +inline void fix_start_proj(ir_graph *irg) { + ir_node *proj, *startbl; + int i; + if (get_Block_n_cfg_outs(get_irg_start_block(irg))) { + startbl = get_irg_start_block(irg); + for (i = 0; i < get_irn_n_outs(startbl); i++) + if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) + proj = get_irn_out(startbl, i); + if (get_irn_out(proj, 0) == startbl) { + assert(get_irn_n_outs(proj) == 2); + set_irn_out(proj, 0, get_irn_out(proj, 1)); + set_irn_out(proj, 1, startbl); + } + } +} + void compute_outs(ir_graph *irg) { ir_graph *rem = current_ir_graph; int n_out_edges = 0; @@ -172,13 +254,18 @@ void compute_outs(ir_graph *irg) { inc_irg_visited(irg); set_out_edges(get_irg_end(irg), irg->outs); + /* We want that the out of ProjX from Start contains the next block at + position 1, the Start block at position 2. This is necessary for + the out block walker. */ + fix_start_proj(irg); + current_ir_graph = rem; } void free_outs(ir_graph *irg) { /* Update graph state */ - // assert(get_irg_phase_state(current_ir_graph) != phase_building); + assert(get_irg_phase_state(current_ir_graph) != phase_building); current_ir_graph->outs_state = no_outs; if (irg->outs) free(irg->outs); diff --git a/ir/ana/irouts.h b/ir/ana/irouts.h index d48f64328..e1f648d35 100644 --- a/ir/ana/irouts.h +++ b/ir/ana/irouts.h @@ -7,7 +7,7 @@ ** @@@ eventually add reverse conrtol flow graph. (If needed.) */ -/* $ID$ */ +/* $Id$ */ # ifndef _IROUTS_H_ # define _IROUTS_H_ @@ -31,6 +31,12 @@ int get_irn_n_outs (ir_node *node); inline ir_node *get_irn_out (ir_node *node, int pos); inline void set_irn_out (ir_node *node, int pos, ir_node *out); +/* Methods to iterate through the control flow graph. Iterate from 0 to + i < get_Block_cfg_outs(block). No order of successors guaranteed. */ +int get_Block_n_cfg_outs (ir_node *node); +/* Access predecessor n. */ +inline ir_node *get_Block_cfg_out (ir_node *node, int pos); + /* Walks over the graph starting at node. Walks also if graph is in state "outs_inconsistent". Assumes current_ir_graph is set properly. */ @@ -40,7 +46,7 @@ void irg_out_walk(ir_node *node, /* Walks only over Block nodes in the graph. Has it's own visited flag, so that it can be interleaved with the other walker. - @@@ not yet implemented!! */ + node must be either op_Block or mode_X. */ void irg_out_block_walk(ir_node *node, void (pre)(ir_node*, void*), void (post)(ir_node*, void*), void *env); @@ -52,7 +58,7 @@ void irg_out_block_walk(ir_node *node, /* Computes the out edges. Sets a flag in irg to "outs_consistent". If the graph is changed this flag must be set to "outs_inconsistent". Computes out edges from block to floating nodes even if graph is in state - "floats". */ + "floats". Optimizes Tuple nodes. */ void compute_outs(ir_graph *irg); /* Frees the out datastructures. Sets the flag in irg to "no_outs". */ void free_outs(ir_graph *irg); diff --git a/ir/common/Makefile.in b/ir/common/Makefile.in index 36b924545..b73035335 100644 --- a/ir/common/Makefile.in +++ b/ir/common/Makefile.in @@ -20,7 +20,8 @@ SOURCES += Makefile.in panic.c tune.h xgprintf.c xp_help.h common.c firm.c \ include $(topdir)/MakeRules CPPFLAGS += -I$(top_srcdir)/ir/common -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr \ - -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/tv -I$(top_srcdir)/ir/ir + -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/tv -I$(top_srcdir)/ir/ir \ + -I$(top_srcdir)/ir/ana include $(top_srcdir)/MakeTargets diff --git a/ir/common/common.h b/ir/common/common.h index b77b3e6e6..fc95d23ee 100644 --- a/ir/common/common.h +++ b/ir/common/common.h @@ -33,6 +33,7 @@ as a stack! */ #define USE_EXPICIT_PHI_IN_STACK 1 +#define DEBUG_libfirm 1 /* If this is defined debuging aids are created, e.g. a field in ir_node uniquely numbering the nodes. Warum war das auskommentiert?? (--enable-debug hat das nicht gesetzt. diff --git a/ir/ir/irdump.c b/ir/ir/irdump.c index 1c9869d7e..abfd8c287 100644 --- a/ir/ir/irdump.c +++ b/ir/ir/irdump.c @@ -27,6 +27,7 @@ # include "irgwalk.h" # include "typewalk.h" # include "irouts.h" +#include "irdom.h" /* Attributes of nodes */ #define DEFAULT_NODE_ATTR "" @@ -36,6 +37,7 @@ #define BLOCK_EDGE_ATTR "class: 2 priority: 2 linestyle: dotted" #define CF_EDGE_ATTR "color: red" #define MEM_EDGE_ATTR "color: blue" +#define DOMINATOR_EDGE_ATTR "color: red" /* Attributes of edges between Firm nodes and type/entity nodes */ #define NODE2TYPE_EDGE_ATTR "class: 2 priority: 2 linestyle: dotted" @@ -76,7 +78,7 @@ int const_entities = 1; int dump_keepalive = 0; /* A compiler option to dump the out edges in dump_ir_graph */ int dump_out_edge_flag = 0; - +int dump_dominator_information_flag = 0; /* A global variable to record output of the Bad node. */ int Bad_dumped; @@ -1012,13 +1014,24 @@ dump_block_to_cfg (ir_node *block, void *env) { xfprintf (F, "\" label: \"%I ", block->op->name); PRINT_NODEID(block); xfprintf (F, "\"}\n"); /* Dump the edges */ - for ( i = 0; i < get_Block_n_cfgpreds(block); i++) { - pred = get_nodes_Block(skip_Proj(get_Block_cfgpred(block, i))); + for ( i = 0; i < get_Block_n_cfgpreds(block); i++) + if (get_irn_op(skip_Proj(get_Block_cfgpred(block, i))) != op_Bad) { + pred = get_nodes_Block(skip_Proj(get_Block_cfgpred(block, i))); + xfprintf (F, "edge: { sourcename: \""); + PRINT_NODEID(block); + fprintf (F, "\" targetname: \""); + PRINT_NODEID(pred); + fprintf (F, "\" }\n"); + } + + /* Dump dominator information */ + if (dump_dominator_information_flag && get_Block_idom(block)) { + pred = get_Block_idom(block); xfprintf (F, "edge: { sourcename: \""); PRINT_NODEID(block); fprintf (F, "\" targetname: \""); PRINT_NODEID(pred); - fprintf (F, "\" }\n"); + fprintf (F, "\" " DOMINATOR_EDGE_ATTR "}\n"); } } } @@ -1026,11 +1039,16 @@ dump_block_to_cfg (ir_node *block, void *env) { void dump_cfg (ir_graph *irg) { + int rem = dump_dominator_information_flag; vcg_open (irg, "-cfg"); + if (get_irg_dom_state(irg) != dom_consistent) + dump_dominator_information_flag = 0; + /* walk over the blocks in the graph */ irg_block_walk(irg->end, dump_block_to_cfg, NULL, NULL); + dump_dominator_information_flag = rem; vcg_close(); } @@ -1156,3 +1174,7 @@ void dump_keepalive_edges() { void dump_out_edges() { dump_out_edge_flag = 1; } + +void dump_dominator_information() { + dump_dominator_information_flag = 1; +} diff --git a/ir/ir/irdump.h b/ir/ir/irdump.h index 54a2d1924..1ad604cdc 100644 --- a/ir/ir/irdump.h +++ b/ir/ir/irdump.h @@ -276,7 +276,7 @@ void turn_off_constant_entity_values(); void dump_keepalive_edges(); -/****m* irdump/dump_constant_entity_values +/****m* irdump/dump_out_edges * * NAME * dump_out_edges @@ -293,4 +293,24 @@ void dump_keepalive_edges(); *** */ void dump_out_edges(); + + +/****m* irdump/dump_dominator_information + * + * NAME + * dump_dominator_information + * SYNOPSIS + * void dump_dominator_information() + * FUNCTION + * If this flag is set the dumper dumps edges to immediate dominator in cfg. + * INPUTS + * No inputs + * RESULT + * SEE ALSO + * + *** + */ +void dump_dominator_information(); + + # endif /* _IRDUMP_H_ */ diff --git a/ir/ir/irgraph.c b/ir/ir/irgraph.c index 527a3537d..a85400528 100644 --- a/ir/ir/irgraph.c +++ b/ir/ir/irgraph.c @@ -81,6 +81,7 @@ new_ir_graph (entity *ent, int n_loc) res->phase_state = phase_building; res->pinned = pinned; res->outs_state = no_outs; + res->dom_state = no_dom; /** Type inforamtion for the procedure of the graph **/ res->ent = ent; @@ -381,6 +382,14 @@ void set_irg_outs_inconsistent(ir_graph *irg) { irg->outs_state = outs_inconsistent; } +irg_dom_state get_irg_dom_state(ir_graph *irg) { + return irg->dom_state; +} + +void set_irg_dom_inconsistent(ir_graph *irg) { + irg->dom_state = dom_inconsistent; +} + inline void set_irg_pinned (ir_graph *irg, op_pinned p) { diff --git a/ir/ir/irgraph.h b/ir/ir/irgraph.h index 28bc6e468..1c5585bc2 100644 --- a/ir/ir/irgraph.h +++ b/ir/ir/irgraph.h @@ -182,7 +182,22 @@ typedef enum { irg_outs_state get_irg_outs_state(ir_graph *irg); void set_irg_outs_inconsistent(ir_graph *irg); - +/* state: dom_state + Signals the state of the dominator infomation. + Values: no_dom, dom_consistent, dom_inconsistent + no_dom: doms are not computed, no memory is allocated. The access routines + may not be used. + dom_consistent: dominator information is computed and correct, + dom_inconsistent: dominator information is computed, memory is still allocated, + but the graph has been changed since. Using the access routines is possible, + obtained information may be incorrect. */ +typedef enum { + no_dom, + dom_consistent, + dom_inconsistent +} irg_dom_state; +irg_dom_state get_irg_dom_state(ir_graph *irg); +void set_irg_dom_inconsistent(ir_graph *irg); /* increments visited by one */ void inc_irg_visited(ir_graph *irg); diff --git a/ir/ir/irgraph_t.h b/ir/ir/irgraph_t.h index 8f7848b4f..6e7fccf9d 100644 --- a/ir/ir/irgraph_t.h +++ b/ir/ir/irgraph_t.h @@ -43,6 +43,7 @@ struct ir_graph { irg_phase_state phase_state; /* compiler phase */ op_pinned pinned; /* Flag for status of nodes */ irg_outs_state outs_state; /* Out edges. */ + irg_dom_state dom_state; /* Dominator information */ /** Fields for construction **/ #if USE_EXPICIT_PHI_IN_STACK diff --git a/ir/ir/irnode.c b/ir/ir/irnode.c index 10294ec63..e5202016e 100644 --- a/ir/ir/irnode.c +++ b/ir/ir/irnode.c @@ -467,6 +467,13 @@ set_Block_block_visited (ir_node *node, unsigned long visit) { node->attr.block.block_visited = visit; } +/* For this current_ir_graph must be set. */ +inline void mark_Block_block_visited (ir_node *node) { + assert (node->op == op_Block); + node->attr.block.block_visited = get_irg_block_visited(current_ir_graph); +} + + inline ir_node * get_Block_graph_arr (ir_node *node, int pos) { assert (node->op == op_Block); diff --git a/ir/ir/irnode.h b/ir/ir/irnode.h index b52024b3b..665e1d1b3 100644 --- a/ir/ir/irnode.h +++ b/ir/ir/irnode.h @@ -147,6 +147,8 @@ inline bool get_Block_matured (ir_node *node); inline void set_Block_matured (ir_node *node, bool matured); inline unsigned long get_Block_block_visited (ir_node *node); inline void set_Block_block_visited (ir_node *node, unsigned long visit); +/* For this current_ir_graph must be set. */ +inline void mark_Block_block_visited(ir_node *node); inline ir_node *get_Block_graph_arr (ir_node *node, int pos); inline void set_Block_graph_arr (ir_node *node, int pos, ir_node *value); diff --git a/ir/ir/irnode_t.h b/ir/ir/irnode_t.h index 129380519..7214bbd10 100644 --- a/ir/ir/irnode_t.h +++ b/ir/ir/irnode_t.h @@ -15,13 +15,20 @@ # include "xprintf.h" # include "irop_t.h" +#include "irdom_t.h" /* For size of struct dom_info. */ + /** ir node attributes **/ + /* Block attributes */ typedef struct { unsigned long block_visited; /* for the walker that walks over all blocks. */ /* Attributes private to construction: */ bool matured; /* if set, all in-nodes of the block are fixed */ struct ir_node **graph_arr; /* array to store all parameters */ + struct dom_info dom; /* Datastructure that holds information about dominators. + @@@ Eventually overlay with graph_arr as only valid + in different phases. Eventually inline the whole + datastructure. */ } block_attr; /* Cond attributes */ diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c index 7ac9c5798..a4161d4b5 100644 --- a/ir/ir/iropt.c +++ b/ir/ir/iropt.c @@ -386,7 +386,7 @@ equivalent_node (ir_node *n) } break; /* GL: Why are they skipped? DivMod allocates new nodes --> it's - teated in transform node. + treated in transform node. case iro_Mod, Quot, DivMod */ case iro_And: @@ -589,6 +589,28 @@ transform_node (ir_node *n) tarval *ta, *tb; switch (get_irn_opcode(n)) { + case iro_Div: { + ta = computed_value(n); + if (ta) { + /* Turn Div into a tuple (mem, bad, value) */ + ir_node *mem = get_Div_mem(n); + turn_into_tuple(n, 3); + set_Tuple_pred(n, 0, mem); + set_Tuple_pred(n, 1, new_Bad()); + set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta)); + } + } break; + case iro_Mod: { + ta = computed_value(n); + if (ta) { + /* Turn Div into a tuple (mem, bad, value) */ + ir_node *mem = get_Mod_mem(n); + turn_into_tuple(n, 3); + set_Tuple_pred(n, 0, mem); + set_Tuple_pred(n, 1, new_Bad()); + set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta)); + } + } break; case iro_DivMod: { int evaluated = 0; @@ -598,8 +620,8 @@ transform_node (ir_node *n) b = get_DivMod_right(n); mode = get_irn_mode(a); - if (!( mode_is_int(get_irn_mode(a)) - && mode_is_int(get_irn_mode(b)))) + if (!(mode_is_int(get_irn_mode(a)) + && mode_is_int(get_irn_mode(b)))) break; if (a == b) { -- 2.20.1