From 328ae18da3e796f4f9fda2aba629cc34e2849ed7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Thu, 31 Jan 2002 08:05:05 +0000 Subject: [PATCH] New directory: ana for analyses. Adapted configure/makefiles implemented irout: backedges. Added one field to ir_graph, one to ir_node. Implemented state management for irgraphs: see irgraph.h. Must now call finalize_cons() after graph construction!!C [r304] --- ir/ir/Makefile.in | 2 +- ir/ir/ircons.c | 20 +- ir/ir/ircons.h | 6 +- ir/ir/irdump.c | 49 ++++- ir/ir/irdump.h | 17 ++ ir/ir/irflag.c | 30 ++- ir/ir/irflag.h | 17 +- ir/ir/irgopt.c | 29 ++- ir/ir/irgopt.h | 3 + ir/ir/irgraph.c | 35 +++- ir/ir/irgraph.h | 58 +++++- ir/ir/irgraph_t.h | 28 ++- ir/ir/irnode.c | 26 ++- ir/ir/irnode.h | 13 +- ir/ir/irnode_t.h | 7 +- ir/ir/irop.c | 123 +++++++----- ir/ir/irop.h | 16 +- ir/ir/irop_t.h | 4 +- ir/ir/iropt.c | 87 +++++--- ir/ir/iropt.h | 3 +- ir/ir/iropt_t.h | 1 + ir/ir/irprog.c | 1 - ir/tr/type.c | 18 +- testprograms/Makefile.in | 3 +- testprograms/array-heap_example.c | 2 + testprograms/array-stack_example.c | 3 +- testprograms/call_str_example.c | 2 + testprograms/cond_example.c | 2 + testprograms/const_ent_example.c | 3 +- testprograms/const_eval_example.c | 4 +- testprograms/dead_block_example.c | 2 + testprograms/empty.c | 1 + testprograms/endless_loop.c | 146 ++++++++++++++ testprograms/global_cse.c | 157 +++++++++++++++ testprograms/global_var_example.c | 2 + testprograms/if_else_example.c | 1 + testprograms/if_example.c | 1 + testprograms/if_while_example.c | 9 +- testprograms/irr_cf_example.c | 2 + testprograms/irr_loop_example.c | 2 + testprograms/memory_example.c | 2 + testprograms/oo_inline_example.c | 301 ++++++++++++++++++++++++++++ testprograms/oo_program_example.c | 3 + testprograms/three_cfpred_example.c | 7 +- testprograms/while_example.c | 2 + 45 files changed, 1102 insertions(+), 148 deletions(-) create mode 100644 testprograms/endless_loop.c create mode 100644 testprograms/global_cse.c create mode 100644 testprograms/oo_inline_example.c diff --git a/ir/ir/Makefile.in b/ir/ir/Makefile.in index baa473438..29c035323 100644 --- a/ir/ir/Makefile.in +++ b/ir/ir/Makefile.in @@ -27,7 +27,7 @@ include $(topdir)/MakeRules CPPFLAGS += -I$(top_srcdir)/ir/adt -I$(top_srcdir)/ir/ir -I$(top_srcdir)/ir/common \ -I$(top_srcdir)/ir/ident -I$(top_srcdir)/ir/tr -I$(top_srcdir)/ir/tv \ - -I$(top_srcdir)/ir/debug + -I$(top_srcdir)/ir/debug -I$(top_srcdir)/ir/ana include $(top_srcdir)/MakeTargets diff --git a/ir/ir/ircons.c b/ir/ir/ircons.c index 804a7865a..72c5a1fc8 100644 --- a/ir/ir/ircons.c +++ b/ir/ir/ircons.c @@ -22,7 +22,7 @@ # include "common.h" # include "irvrfy.h" # include "irop.h" -# include "iropt.h" +# include "iropt_t.h" # include "irgmod.h" # include "array.h" /* memset belongs to string.h */ @@ -636,10 +636,8 @@ ir_node * new_End (void) { ir_node *res; - res = new_ir_node (current_ir_graph, current_ir_graph->current_block, op_End, mode_X, -1, NULL); - res = optimize (res); irn_vrfy (res); @@ -1373,8 +1371,9 @@ mature_block (ir_node *block) we can not free the node on the obstack. Therefore we have to call optimize_in_place. Unfortunately the optimization does not change a lot, as all allocated - nodes refer to the unoptimized node. */ - block = optimize_in_place(block); + nodes refer to the unoptimized node. + We can call _2, as global cse has no effect on blocks. */ + block = optimize_in_place_2(block); irn_vrfy(block); } } @@ -1717,6 +1716,7 @@ new_Bad (void) ir_node *new_immBlock (void) { ir_node *res; + assert(get_irg_phase_state (current_ir_graph) == phase_building); /* creates a new dynamic in-array as length of in is -1 */ res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL); current_ir_graph->current_block = res; @@ -1761,6 +1761,7 @@ switch_block (ir_node *target) ir_node * get_value (int pos, ir_mode *mode) { + assert(get_irg_phase_state (current_ir_graph) == phase_building); inc_irg_visited(current_ir_graph); return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode); } @@ -1770,6 +1771,7 @@ get_value (int pos, ir_mode *mode) inline void set_value (int pos, ir_node *value) { + assert(get_irg_phase_state (current_ir_graph) == phase_building); current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value; } @@ -1777,6 +1779,7 @@ set_value (int pos, ir_node *value) inline ir_node * get_store (void) { + assert(get_irg_phase_state (current_ir_graph) == phase_building); /* GL: one could call get_value instead */ inc_irg_visited(current_ir_graph); return get_r_value_internal (current_ir_graph->current_block, 0, mode_M); @@ -1786,6 +1789,7 @@ get_store (void) inline void set_store (ir_node *store) { + assert(get_irg_phase_state (current_ir_graph) == phase_building); /* GL: one could call set_value instead */ current_ir_graph->current_block->attr.block.graph_arr[0] = store; } @@ -1817,3 +1821,9 @@ void init_cons (void) { } + +/* call for each graph */ +void +finalize_cons (ir_graph *irg) { + irg->phase_state = phase_high; +} diff --git a/ir/ir/ircons.h b/ir/ir/ircons.h index 51448e5c1..6561c3859 100644 --- a/ir/ir/ircons.h +++ b/ir/ir/ircons.h @@ -1267,9 +1267,11 @@ type *get_cur_frame_type(); /***********************************************************************/ -/* initialize ir construction */ +/* initialize and finalize ir construction */ /***********************************************************************/ -void init_cons (void); + +/* Puts the graph into state "phase_high" */ +void finalize_cons (ir_graph *irg); # endif /* _IRCONS_H_ */ diff --git a/ir/ir/irdump.c b/ir/ir/irdump.c index f5fbdd8fb..748b9062f 100644 --- a/ir/ir/irdump.c +++ b/ir/ir/irdump.c @@ -26,6 +26,7 @@ # include "type_or_entity.h" # include "irgwalk.h" # include "typewalk.h" +# include "irouts.h" /* Attributes of nodes */ #define DEFAULT_NODE_ATTR "" @@ -72,7 +73,10 @@ int edge_label = 1; /* A compiler option to turn off dumping values of constant entities */ int const_entities = 1; /* A compiler option to dump the keep alive edges */ -int dump_keepalive = 1; +int dump_keepalive = 0; +/* A compiler option to dump the out edges in dump_ir_graph */ +int dump_out_edge_flag = 0; + /* A global variable to record output of the Bad node. */ int Bad_dumped; @@ -479,6 +483,22 @@ dump_ir_data_edges(ir_node *n) { } } +/* dump out edges */ +void +dump_out_edge (ir_node *n, void* env) { + int i; + for (i = 0; i < get_irn_n_outs(n); i++) { + assert(get_irn_out(n, i)); + fprintf (F, "edge: {sourcename: \""); + PRINT_NODEID(n); + fprintf (F, "\" targetname: \""); + PRINT_NODEID(get_irn_out(n, i)); + fprintf (F, "\" color: red linestyle: dashed"); + fprintf (F, "}\n"); + } +} + + /* dumps the edges between nodes and their type or entity attributes. */ void dump_node2type_edges (ir_node *n, void *env) { @@ -851,7 +871,7 @@ vcg_close () { void dump_whole_node (ir_node *n, void* env) { dump_node(n); - dump_ir_block_edge(n); + if (!node_floats(n)) dump_ir_block_edge(n); dump_ir_data_edges(n); } @@ -867,6 +887,11 @@ dump_ir_graph (ir_graph *irg) /* walk over the graph */ irg_walk(irg->end, dump_whole_node, NULL, NULL); + /* dump the out edges in a separate walk */ + if ((dump_out_edge_flag) && (get_irg_outs_state(irg) != no_outs)) { + irg_out_walk(irg->start, dump_out_edge, NULL, NULL); + } + vcg_close(); current_ir_graph = rem; @@ -876,11 +901,16 @@ dump_ir_graph (ir_graph *irg) /* the following routines dump the nodes as attached to the blocks. */ /***********************************************************************/ +int node_floats(ir_node *n) { + return ((get_op_pinned(get_irn_op(n)) == floats) && + (get_irg_pinned(current_ir_graph) == floats)); +} + void dump_ir_blocks_nodes (ir_node *n, void *env) { ir_node *block = (ir_node *)env; - if (is_no_Block(n) && get_nodes_Block(n) == block) { + if (is_no_Block(n) && get_nodes_Block(n) == block && !node_floats(n)) { dump_node(n); dump_ir_data_edges(n); } @@ -920,9 +950,14 @@ dump_blockless_nodes (ir_node *n, void *env) { dump_node(n); dump_ir_data_edges(n); dump_ir_block_edge(n); + if (get_irn_op(n) == op_Bad) Bad_dumped = 1; + return; + } + if (node_floats(n)) { + dump_node(n); + dump_ir_data_edges(n); + if (get_irn_op(n) == op_Bad) Bad_dumped = 1; } - if (get_irn_op(n) == op_Bad) - Bad_dumped = 1; } void dump_ir_block_graph_2 (ir_graph *irg) @@ -1110,3 +1145,7 @@ void dump_constant_entity_values() { void dump_keepalive_edges() { dump_keepalive = 1; } + +void dump_out_edges() { + dump_out_edge_flag = 1; +} diff --git a/ir/ir/irdump.h b/ir/ir/irdump.h index 2e3be51e5..591a94849 100644 --- a/ir/ir/irdump.h +++ b/ir/ir/irdump.h @@ -276,4 +276,21 @@ void dump_constant_entity_values(); void dump_keepalive_edges(); +/****m* irdump/dump_constant_entity_values + * + * NAME + * dump_out_edges + * SYNOPSIS + * void dump_out_edges() + * FUNCTION + * Turns on dumping the out edges starting from the Start block in + * dump_ir_graph. To test the consistency of the out datastructure. + * INPUTS + * No inputs + * RESULT + * SEE ALSO + * + *** + */ +void dump_out_edges(); # endif /* _IRDUMP_H_ */ diff --git a/ir/ir/irflag.c b/ir/ir/irflag.c index 1e106958b..2bdd3198f 100644 --- a/ir/ir/irflag.c +++ b/ir/ir/irflag.c @@ -15,15 +15,18 @@ /* 0 - don't do this optimization 1 - lets see, if there is a better graph */ +int optimized = 1; /* Turn off all optimizations */ + int opt_cse = 1; /* Hash the nodes */ +int opt_global_cse = 0; /* Don't use block predecessor for comparison */ +/* @@@ 0 solage code placement fehlt */ int opt_constant_folding = 1; /* Evaluate operations */ int opt_unreachable_code = 1; /* Bad node propagation */ int opt_dead_node_elimination = 1; /* Reclaim memory */ -int optimized = 1; -int opt_inline = 1; +int opt_reassociation = 1; /* Reassociate nodes */ +int opt_inline = 1; /* Do inlining transformation */ /* set the flags with set_flagname, get the flag with get_flagname */ - inline void set_opt_cse (int value) { @@ -36,6 +39,16 @@ get_opt_cse (void) return opt_cse; } +void set_opt_global_cse (int value) +{ + opt_global_cse = value; +} + +int get_opt_global_cse (void) +{ + return opt_global_cse; +} + inline void set_opt_constant_folding (int value) { @@ -60,6 +73,17 @@ get_opt_unreachable_code(void) return opt_unreachable_code; } +inline void +set_opt_reassociation(int value) +{ + opt_reassociation = value; +} + +inline int +get_opt_reassociation(void) +{ + return opt_reassociation; +} inline void set_opt_dead_node_elimination (int value) diff --git a/ir/ir/irflag.h b/ir/ir/irflag.h index ffeddfd54..e962e7f0c 100644 --- a/ir/ir/irflag.h +++ b/ir/ir/irflag.h @@ -28,19 +28,30 @@ int get_optimize (void); void set_opt_constant_folding (int value); int get_opt_constant_folding (void); -/* If opt_cse == 1 perfor constant subexpression elimination - (and, if implemented, global code motion. @@@ Right now - cse only within blocks. +/* If opt_cse == 1 perform constant subexpression elimination. Default: opt_cse == 1. */ void set_opt_cse (int value); int get_opt_cse (void); +/* If opt_global_cse == 1 and opt_cse == 1 perform intra procedure + constant subexpression elimination for floating nodes. Intra + procedure cse gets the graph into state "floating". It is necessary + to run pre/code motion to get the graph back into state "pinned". + Default: opt_global_cse == 1. */ +void set_opt_global_cse (int value); +int get_opt_global_cse (void); + /* If opt_unreachable_code == 1 replace nodes (except Block, Phi and Tuple) with a Bad predecessor by the Bad node. Default: opt_unreachable_code == 1. */ inline void set_opt_unreachable_code(int value); inline int get_opt_unreachable_code(void); +/* If opt_reassociation == 1 reassociation is performed. + Default: opt_reassociation == 1. */ +inline void set_opt_reassociation(int value); +inline int get_opt_reassociation(void); + /* If opt_dead_node_elimination == 1 deallocate all dead nodes by copying the firm graph. Default: opt_dead_node_elimination == 0. @@@ as buggy, else 1. */ diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c index 1ad1d9aff..7b868acdf 100644 --- a/ir/ir/irgopt.c +++ b/ir/ir/irgopt.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe +/* Coyright (C) 1998 - 2000 by Universitaet Karlsruhe ** All rights reserved. ** ** Author: Christian Schaefer @@ -17,7 +17,7 @@ # include "irgopt.h" # include "irnode_t.h" # include "irgraph_t.h" -# include "iropt.h" +# include "iropt_t.h" # include "irgwalk.h" # include "ircons.h" # include "misc.h" @@ -55,7 +55,7 @@ optimize_in_place_wrapper (ir_node *n, void *env) { /* optimize all sons after recursion, i.e., the sons' sons are optimized already. */ for (i = -1; i < get_irn_arity(n); i++) { - optimized = optimize_in_place(get_irn_n(n, i)); + optimized = optimize_in_place_2(get_irn_n(n, i)); set_irn_n(n, i, optimized); } } @@ -65,7 +65,14 @@ local_optimize_graph (ir_graph *irg) { ir_graph *rem = current_ir_graph; current_ir_graph = irg; - /* Should we clean the value_table in irg for the cse? Better do so... */ + /* Handle graph state */ + assert(get_irg_phase_state(irg) != phase_building); + if (get_opt_global_cse()) + set_irg_pinned(current_ir_graph, floats); + if (get_irg_outs_state(current_ir_graph) == outs_consistent) + set_irg_outs_inconsistent(current_ir_graph); + + /* Clean the value_table in irg for the cse. */ del_identities(irg->value_table); irg->value_table = new_identities(); @@ -189,7 +196,7 @@ copy_preds (ir_node *n, void *env) { set_Block_block_visited(n, 0); /* Local optimization could not merge two subsequent blocks if in array contained Bads. Now it's possible. - @@@ I removed the call to optimize_in_place as it requires + We don't call optimize_in_place as it requires that the fields in ir_graph are set properly. */ if (get_Block_n_cfgpreds(nn) == 1 && get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp) @@ -292,6 +299,7 @@ copy_graph_env () { copy_graph(); /* fix the fields in current_ir_graph */ + free_End(get_irg_end(current_ir_graph)); set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph))); set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph))); if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) { @@ -337,6 +345,10 @@ dead_node_elimination(ir_graph *irg) { rem = current_ir_graph; current_ir_graph = irg; + /* Handle graph state */ + assert(get_irg_phase_state(current_ir_graph) != phase_building); + free_outs(current_ir_graph); + if (get_optimize() && get_opt_dead_node_elimination()) { /* A quiet place, where the old obstack can rest in peace, @@ -400,6 +412,11 @@ void inline_method(ir_node *call, ir_graph *called_graph) { if (!get_opt_inline()) return; + /* Handle graph state */ + assert(get_irg_phase_state(current_ir_graph) != phase_building); + if (get_irg_outs_state(current_ir_graph) == outs_consistent) + set_irg_outs_inconsistent(current_ir_graph); + /** Check preconditions **/ assert(get_irn_op(call) == op_Call); assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); @@ -505,6 +522,8 @@ void inline_method(ir_node *call, ir_graph *called_graph) { /** archive keepalives **/ for (i = 0; i < get_irn_arity(end); i++) add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i)); + /* The new end node will die, but the in array is not on the obstack ... */ + free_End(end); /** Collect control flow from Return blocks to post_calls block. Replace Return nodes by Jump nodes. **/ diff --git a/ir/ir/irgopt.h b/ir/ir/irgopt.h index e3710a290..494f2b063 100644 --- a/ir/ir/irgopt.h +++ b/ir/ir/irgopt.h @@ -19,6 +19,9 @@ void local_optimize_graph (ir_graph *irg); /* Performs dead node elimination by copying the ir graph to a new obstack. Further removes Bad predecesors from Blocks and the corresponding inputs to Phi nodes. + The graph may not be in state phase_building. The outs datasturcture + is freed, the outs state set to no_outs. (@@@ Change this? -> inconsistent.) + Removes old attributes of nodes. Attention: the numbers assigned to nodes if the library is compiled for development/debugging are not conserved by copying. */ void dead_node_elimination(ir_graph *irg); diff --git a/ir/ir/irgraph.c b/ir/ir/irgraph.c index e2a99c874..e03588e8f 100644 --- a/ir/ir/irgraph.c +++ b/ir/ir/irgraph.c @@ -76,6 +76,11 @@ new_ir_graph (entity *ent, int n_loc) res->value_table = new_identities (); /* value table for global value numbering for optimizing use in iropt.c */ + res->outs = NULL; + + res->phase_state = phase_building; + res->pinned = pinned; + res->outs_state = no_outs; /** Type inforamtion for the procedure of the graph **/ res->ent = ent; @@ -132,6 +137,7 @@ ir_graph *new_const_code_irg() { #endif res->obst = (struct obstack *) xmalloc (sizeof (struct obstack)); obstack_init (res->obst); + res->pinned = pinned; res->value_table = new_identities (); /* value table for global value numbering for optimizing use in iropt.c */ @@ -157,8 +163,6 @@ ir_graph *new_const_code_irg() { return res; } - - /* Frees the passed irgraph. Deallocates all nodes in this graph and the ir_graph structure. Sets the field irgraph in the corresponding entity to NULL. @@ -338,6 +342,33 @@ set_irg_n_loc (ir_graph *irg, int n_loc) irg->n_loc = n_loc; } +irg_phase_state get_irg_phase_state (ir_graph *irg) { + return irg->phase_state; +} + +void set_irg_phase_low(ir_graph *irg) { + irg->phase_state = phase_low; +} + +op_pinned +get_irg_pinned (ir_graph *irg) { + return irg->pinned; +} + +irg_outs_state get_irg_outs_state(ir_graph *irg) { + return irg->outs_state; +} + +void set_irg_outs_inconsistent(ir_graph *irg) { + irg->outs_state = outs_inconsistent; +} + +inline void +set_irg_pinned (ir_graph *irg, op_pinned p) +{ + irg->pinned = p; +} + unsigned long get_irg_visited (ir_graph *irg) { diff --git a/ir/ir/irgraph.h b/ir/ir/irgraph.h index 09f07487b..8a690e263 100644 --- a/ir/ir/irgraph.h +++ b/ir/ir/irgraph.h @@ -8,6 +8,8 @@ /* $Id$ */ +#include "irop.h" + # ifndef _IRGRAPH_H_ # define _IRGRAPH_H_ # include "tv.h" @@ -58,6 +60,10 @@ typedef struct ir_graph ir_graph; * datastructure is used to build the Phi nodes and removed after * completion of the graph. There is no path from end to start in the * graph after calling ir_graph. + * FIELDS + * pinned set to "pinned" if no global cse was performed on the graph. + * set to "floats" if global cse was performed (and during construction: + * did actually change something). Code placement is necessary. * SOURCE */ @@ -71,7 +77,8 @@ extern ir_graph *current_ir_graph; entity must be of a method type. The constructor automatically sets the field irg of the entity as well as current_ir_graph to the new ir graph. n_loc is the number of local variables in this procedure including - the procedure parameters. */ + the procedure parameters. + The state of the ir graph is: phase_building, pinned, no_outs. */ ir_graph *new_ir_graph (entity *ent, int n_loc); /* Frees the passed irgraph. @@ -125,6 +132,55 @@ void set_irg_frame_type (ir_graph *irg, type *ftp); int get_irg_n_loc (ir_graph *irg); void set_irg_n_loc (ir_graph *irg, int n_loc); + +/********************************************************************************/ +/* States of an ir_graph. */ +/********************************************************************************/ + +/* An ir_graph can have different states. These states represent the analysis + information associated with the graph. Optimizations invalidate these + states. */ + +/* state: phase + values: phase_building, phase_high, phase_low + The irg is in phase_building during construction of the irgraph. + It is in phase_high after construction. All nodes are allowed. + To get the irgraph into phase_low all Sel nodes must be removed + and replaced by explicit address computations. @@@ More conditions? */ +typedef enum { + phase_building, + phase_high, + phase_low +} irg_phase_state; +irg_phase_state get_irg_phase_state (ir_graph *irg); +void set_irg_phase_low(ir_graph *irg); + +/* state: pinned + The graph is "pinned" if all nodes are accosiated with a basic block. + It is in state "floats" if nodes are in arbitrary blocks. In state + "floats" the block predecessor is set in all nodes, but this can be an + invalid block, i.e., the block is not a dominator of all the uses of + the node. + The enum op_pinned is defined in irop.h. */ +op_pinned get_irg_pinned (ir_graph *irg); + +/* state: outs_state + Outs are the back edges or def-use edges. + Values: no_outs, outs_consistent, outs_inconsistent + no_outs: outs are not computed, no memory is allocated. + outs_consistent: outs are computed and correct, + outs_inconsistent: outs have been computed, memory is still allocated, + but the graph has been changed since. */ +typedef enum { + no_outs, + outs_consistent, + outs_inconsistent +} irg_outs_state; +irg_outs_state get_irg_outs_state(ir_graph *irg); +void set_irg_outs_inconsistent(ir_graph *irg); + + + /* increments visited by one */ void inc_irg_visited(ir_graph *irg); unsigned long get_irg_visited (ir_graph *irg); diff --git a/ir/ir/irgraph_t.h b/ir/ir/irgraph_t.h index b330c7332..ad99220cb 100644 --- a/ir/ir/irgraph_t.h +++ b/ir/ir/irgraph_t.h @@ -16,6 +16,7 @@ /* ir_graph holds all information for a procedure */ struct ir_graph { + /** Basics of the representation **/ struct entity *ent; /* The entity of this procedure, i.e., the type of the procedure and the class it belongs to. */ @@ -33,26 +34,39 @@ struct ir_graph { struct ir_node *bad; /* bad node of this ir_graph, the one and only in this graph */ struct obstack *obst; /* obstack where all of the ir_nodes live */ + struct ir_node *current_block; /* block for newly gen_*()-erated + ir_nodes */ + + /** Fields indicating different states of irgraph **/ + irg_phase_state phase_state; /* compiler phase */ + op_pinned pinned; /* Flag for status of nodes */ + irg_outs_state outs_state; /* Out edges. */ + + /** Fields for construction **/ #if USE_EXPICIT_PHI_IN_STACK struct Phi_in_stack *Phi_in_stack; /* needed for automatic Phi construction */ #endif - struct ir_node *current_block; /* block for newly gen_*()-erated - ir_nodes */ int n_loc; /* number of local variable in this procedure including procedure parameters. */ - pset *value_table; /* value table for global value numbering + + /** Fields for optimizations / analysis information **/ + pset *value_table; /* hash table for global value numbering (cse) for optimizing use in iropt.c */ + struct ir_node **outs; /* Space for the out arrays. */ + + /** Fields for Walking the graph **/ unsigned long visited; /* this flag is an identifier for - ir walk. it will be incremented, - every time, someone walk through + ir walk. it will be incremented + every time someone walks through the graph */ - unsigned long block_visited; /* same as visited, for a - complete block */ + unsigned long block_visited; /* same as visited, for a complete block */ }; /* Make a rudimentary ir graph for the constant code. Must look like a correct irg, spare everything else. */ ir_graph *new_const_code_irg(); +inline void +set_irg_pinned (ir_graph *irg, op_pinned p); # endif /* _IRGRAPH_T_H_ */ diff --git a/ir/ir/irnode.c b/ir/ir/irnode.c index f1a9a26c7..d0f32c052 100644 --- a/ir/ir/irnode.c +++ b/ir/ir/irnode.c @@ -96,6 +96,7 @@ new_ir_node (ir_graph *irg, ir_node *block, ir_op *op, ir_mode *mode, memcpy (&res->in[1], in, sizeof (ir_node *) * arity); } res->in[0] = block; + res->out = NULL; #ifdef DEBUG_libfirm res->node_nr = get_irp_new_node_nr(); @@ -208,9 +209,12 @@ set_irn_in (ir_node *node, int arity, ir_node **in) { inline ir_node * get_irn_n (ir_node *node, int n) { + ir_node *res; assert (node); - assert (get_irn_arity (node) > n); - return skip_nop(node->in[n+1]); + assert ((get_irn_arity (node) > n) && (-1 <= n)); + res = skip_nop(node->in[n+1]); + if (res != node->in[n+1]) node->in[n+1] = res; + return res; } inline void @@ -469,6 +473,12 @@ add_End_keepalive (ir_node *end, ir_node *ka) { ARR_APP1 (ir_node *, end->in, ka); } +inline void +free_End (ir_node *end) { + /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */ + end->in = NULL; /* @@@ make sure we get an error if we use the in array afterwards ... */ +} + /* > Implementing the case construct (which is where the constant Proj node is > important) involves far more than simply determining the constant values. @@ -1815,6 +1825,11 @@ skip_nop (ir_node *node) { } } +inline ir_node * +skip_Id (ir_node *node) { + return skip_nop(node); +} + inline int is_Bad (ir_node *node) { assert(node); @@ -1832,12 +1847,7 @@ is_no_Block (ir_node *node) { /* Returns true if the operation manipulates control flow. */ int is_cfop(ir_node *node) { - return ( (get_irn_opcode(node) == iro_Start) - || (get_irn_opcode(node) == iro_Jmp) - || (get_irn_opcode(node) == iro_Cond) - || (get_irn_opcode(node) == iro_Return) - || (get_irn_opcode(node) == iro_Raise) - || (get_irn_opcode(node) == iro_Bad)); + return is_cfopcode(get_irn_op(node)); } /* Returns true if the operation can change the control flow because diff --git a/ir/ir/irnode.h b/ir/ir/irnode.h index 954d97b90..b69ced1f4 100644 --- a/ir/ir/irnode.h +++ b/ir/ir/irnode.h @@ -60,7 +60,7 @@ inline ir_node **get_irn_in (ir_node *node); /* Replaces the old in array by a new one that will contain the ins given in the parameters. Conserves the block predecessor. It copies the array passed. This function is necessary to ajust in arrays of blocks, calls and phis. - Assumes the current_ir_graph is set to the graph containing "node". + Assumes that current_ir_graph is set to the graph containing "node". "in" must contain all predecessors except the block that are required for the nodes opcode. */ inline void set_irn_in (ir_node *node, int arity, @@ -71,6 +71,7 @@ inline void set_irn_in (ir_node *node, int arity, to iterate including the Block predecessor iterate from i = -1 to i < get_irn_arity. */ /* Access predecessor n */ +/* get_irn_n removes Id predecessors. */ inline ir_node *get_irn_n (ir_node *node, int n); inline void set_irn_n (ir_node *node, int n, ir_node *in); /* Get the mode struct. */ @@ -149,6 +150,10 @@ inline void set_Block_graph_arr (ir_node *node, int pos, ir_node *value); inline void add_End_keepalive (ir_node *end, ir_node *ka); +/* Some parts of the End node are allocated seperately -- their memory + is not recovered by dead_node_elimination if a End not is dead. + free_End frees these data structures. */ +inline void free_End (ir_node *end); /* We distinguish three kinds of Cond nodes. These can be distinguished by the mode of the selector operand and an internal flag of type cond_kind. @@ -463,6 +468,7 @@ inline void set_Id_pred (ir_node *node, ir_node *pred); inline ir_node *skip_Proj (ir_node *node); /* returns operand of node if node is a Id */ inline ir_node *skip_nop (ir_node *node); +inline ir_node *skip_Id (ir_node *node); /* Same as skip_nop. */ /* returns corresponding operand of Tuple if node is a Proj from a Tuple. */ inline ir_node *skip_Tuple (ir_node *node); @@ -471,7 +477,7 @@ inline int is_Bad (ir_node *node); /* returns true if the node is not a Block */ inline int is_no_Block (ir_node *node); /* Returns true if the operation manipulates control flow: - Start, End, Jmp, Cond, Return, Raise */ + Start, End, Jmp, Cond, Return, Raise, Bad */ int is_cfop(ir_node *node); /* Returns true if the operation can change the control flow because of an exception. */ @@ -495,6 +501,9 @@ ir_node *get_fragile_op_mem(ir_node *node); print_firm_kind(X), (X)) #define DDMSG4(X) printf("%s(l.%i) %s %s: %p\n", __FUNCTION__, __LINE__, \ get_type_tpop_name(X), get_type_name(X), (X)) +#define DDMSG5(X) printf("%s%s: %ld", \ + id_to_str(get_irn_opident(X)), id_to_str(get_irn_modeident(X)), \ + get_irn_node_nr(X)) #endif diff --git a/ir/ir/irnode_t.h b/ir/ir/irnode_t.h index ed2a840e3..129380519 100644 --- a/ir/ir/irnode_t.h +++ b/ir/ir/irnode_t.h @@ -74,7 +74,6 @@ typedef union { symconst_attr i; /* For SymConst. */ sel_attr s; /* For Sel. */ call_attr call; /* For Call: pointer to the type of the method to call */ - long proj; /* For Proj: contains the result position to project */ alloc_attr a; /* For Alloc. */ type *f; /* For Free. */ int phi0_pos; /* For Phi. Used to remember the value defined by @@ -83,11 +82,11 @@ typedef union { predecessors. If this attribute is set, the Phi node takes the role of the obsolete Phi0 node, therefore the name. */ + long proj; /* For Proj: contains the result position to project */ #if PRECISE_EXC_CONTEXT struct ir_node **frag_arr; /* For Phi node construction in case of exceptions for nodes Store, Load, Div, Mod, Quot, DivMod. */ #endif - } attr; @@ -95,6 +94,7 @@ typedef union { /* if the node has some attributes, they are stored in attr */ struct ir_node { + /** Basics of the representation **/ firm_kind kind; /* distinguishes this node from others */ ir_op *op; /* Opcode of this node. */ ir_mode *mode; /* Mode of this node. */ @@ -104,6 +104,9 @@ struct ir_node { used while construction to link Phi0 nodes and during optimization to link to nodes that shall replace a node. */ + /** Fields for optimizations / analysis information **/ + struct ir_node **out; /* array of out edges */ + /** For debugging **/ #ifdef DEBUG_libfirm int node_nr; /* a unique node number for each node to make output readable. */ diff --git a/ir/ir/irop.c b/ir/ir/irop.c index e0387db61..62af0ed0c 100644 --- a/ir/ir/irop.c +++ b/ir/ir/irop.c @@ -65,13 +65,14 @@ ir_op *op_Bad; ir_op * -new_ir_op (opcode code, ident *name, size_t attr_size, int labeled) +new_ir_op (opcode code, char *name, op_pinned p, int labeled, size_t attr_size) { ir_op *res; res = (ir_op *) xmalloc (sizeof (ir_op)); res->code = code; - res->name = name; + res->name = id_from_str(name, strlen(name)); + res->pinned = p; res->attr_size = attr_size; res->labeled = labeled; /* For vcg dumping. Set labeled = 1 if the edges should be @@ -84,54 +85,54 @@ new_ir_op (opcode code, ident *name, size_t attr_size, int labeled) void init_op(void) { - op_Block = new_ir_op (iro_Block, id_from_str ("Block", 5), sizeof (block_attr), 1); - - op_Start = new_ir_op (iro_Start, id_from_str ("Start", 5), sizeof (block_attr), 1); - op_End = new_ir_op (iro_End, id_from_str ("End", 3), sizeof (block_attr), 1); - op_Jmp = new_ir_op (iro_Jmp, id_from_str ("Jmp", 3), 0, 0); - op_Cond = new_ir_op (iro_Cond, id_from_str ("Cond", 4), sizeof(cond_attr), 1); - op_Return = new_ir_op (iro_Return, id_from_str ("Return", 6), 0, 1); - op_Raise = new_ir_op (iro_Raise, id_from_str ("Raise", 5), 0, 1); - - op_Const = new_ir_op (iro_Const, id_from_str ("Const", 5), sizeof (struct tarval *), 0); - op_SymConst = new_ir_op (iro_SymConst, id_from_str ("SymConst", 8), - sizeof (symconst_attr), 0); - - op_Sel = new_ir_op (iro_Sel, id_from_str ("Sel", 3), sizeof (sel_attr), 1); - - op_Call = new_ir_op (iro_Call, id_from_str ("Call", 4), sizeof (call_attr), 1); - op_Add = new_ir_op (iro_Add, id_from_str ("Add", 3), 0, 0); - op_Minus = new_ir_op (iro_Minus, id_from_str ("Minus", 5), 0, 0); - op_Sub = new_ir_op (iro_Sub, id_from_str ("Sub", 3), 0, 1); - op_Mul = new_ir_op (iro_Mul, id_from_str ("Mul", 3), 0, 0); - op_Quot = new_ir_op (iro_Quot, id_from_str ("Quot", 4), sizeof(struct irnode **), 1); - op_DivMod = new_ir_op (iro_DivMod, id_from_str ("DivMod", 6), sizeof(struct irnode **), 1); - op_Div = new_ir_op (iro_Div, id_from_str ("Div", 3), sizeof(struct irnode **), 1); - op_Mod = new_ir_op (iro_Mod, id_from_str ("Mod", 3), sizeof(struct irnode **), 1); - op_Abs = new_ir_op (iro_Abs, id_from_str ("Abs", 3), 0, 0); - op_And = new_ir_op (iro_And, id_from_str ("And", 3), 0, 0); - op_Or = new_ir_op (iro_Or, id_from_str ("Or", 2), 0, 0); - op_Eor = new_ir_op (iro_Eor, id_from_str ("Eor", 3), 0, 0); - op_Not = new_ir_op (iro_Not, id_from_str ("Not", 3), 0, 0); - op_Cmp = new_ir_op (iro_Cmp, id_from_str ("Cmp", 3), 0, 1); - op_Shl = new_ir_op (iro_Shl, id_from_str ("Shl", 3), 0, 1); - op_Shr = new_ir_op (iro_Shr, id_from_str ("Shr", 3), 0, 1); - op_Shrs = new_ir_op (iro_Shrs, id_from_str ("Shrs", 3), 0, 0); - op_Rot = new_ir_op (iro_Rot, id_from_str ("Rot", 3), 0, 0); - op_Conv = new_ir_op (iro_Conv, id_from_str ("Conv", 4), 0, 1); - - op_Phi = new_ir_op (iro_Phi, id_from_str ("Phi", 3), sizeof (int), 1); - - op_Load = new_ir_op (iro_Load, id_from_str ("Load", 4), sizeof(struct irnode **), 1); - op_Store = new_ir_op (iro_Store, id_from_str ("Store", 5), sizeof(struct irnode **), 1); - op_Alloc = new_ir_op (iro_Alloc, id_from_str ("Alloc", 5), sizeof (alloc_attr), 1); - op_Free = new_ir_op (iro_Free, id_from_str ("Free", 4), sizeof (type *), 1); - op_Sync = new_ir_op (iro_Sync, id_from_str ("Sync", 4), 0, 0); - - op_Proj = new_ir_op (iro_Proj, id_from_str ("Proj", 4), sizeof (long), 1); - op_Tuple = new_ir_op (iro_Tuple, id_from_str ("Tuple", 5), 0, 1); - op_Id = new_ir_op (iro_Id, id_from_str ("Id", 2), 0, 0); - op_Bad = new_ir_op (iro_Bad, id_from_str ("Bad", 3), 0, 0); + op_Block = new_ir_op (iro_Block, "Block", pinned, 1, sizeof (block_attr)); + + op_Start = new_ir_op (iro_Start, "Start", pinned, 0, 0); + op_End = new_ir_op (iro_End, "End", pinned, 0, 0); + op_Jmp = new_ir_op (iro_Jmp, "Jmp", pinned, 0, 0); + op_Cond = new_ir_op (iro_Cond, "Cond", pinned, 1, sizeof(cond_attr)); + op_Return= new_ir_op (iro_Return,"Return", pinned, 1, 0); + op_Raise = new_ir_op (iro_Raise, "Raise", pinned, 1, 0); + + op_Const = new_ir_op (iro_Const, "Const", floats, 0, sizeof (struct tarval *)); + op_SymConst = new_ir_op (iro_SymConst, "SymConst", + floats, 0, sizeof (symconst_attr)); + + op_Sel = new_ir_op (iro_Sel, "Sel", floats, 1, sizeof (sel_attr)); + + op_Call = new_ir_op (iro_Call, "Call", pinned, 1, sizeof (call_attr)); + op_Add = new_ir_op (iro_Add, "Add", floats, 0, 0); + op_Minus = new_ir_op (iro_Minus, "Minus", floats, 0, 0); + op_Sub = new_ir_op (iro_Sub, "Sub", floats, 1, 0); + op_Mul = new_ir_op (iro_Mul, "Mul", floats, 0, 0); + op_Quot = new_ir_op (iro_Quot, "Quot", pinned, 1, sizeof(struct irnode **)); + op_DivMod= new_ir_op (iro_DivMod,"DivMod", pinned, 1, sizeof(struct irnode **)); + op_Div = new_ir_op (iro_Div, "Div", pinned, 1, sizeof(struct irnode **)); + op_Mod = new_ir_op (iro_Mod, "Mod", pinned, 1, sizeof(struct irnode **)); + op_Abs = new_ir_op (iro_Abs, "Abs", floats, 0, 0); + op_And = new_ir_op (iro_And, "And", floats, 0, 0); + op_Or = new_ir_op (iro_Or, "Or", floats, 0, 0); + op_Eor = new_ir_op (iro_Eor, "Eor", floats, 0, 0); + op_Not = new_ir_op (iro_Not, "Not", floats, 0, 0); + op_Cmp = new_ir_op (iro_Cmp, "Cmp", floats, 1, 0); + op_Shl = new_ir_op (iro_Shl, "Shl", floats, 1, 0); + op_Shr = new_ir_op (iro_Shr, "Shr", floats, 1, 0); + op_Shrs = new_ir_op (iro_Shrs, "Shrs", floats, 1, 0); + op_Rot = new_ir_op (iro_Rot, "Rot", floats, 1, 0); + op_Conv = new_ir_op (iro_Conv, "Conv", floats, 0, 0); + + op_Phi = new_ir_op (iro_Phi, "Phi", pinned, 1, sizeof (int)); + + op_Load = new_ir_op (iro_Load, "Load", pinned, 1, sizeof(struct irnode **)); + op_Store = new_ir_op (iro_Store, "Store", pinned, 1, sizeof(struct irnode **)); + op_Alloc = new_ir_op (iro_Alloc, "Alloc", pinned, 1, sizeof (alloc_attr)); + op_Free = new_ir_op (iro_Free, "Free", pinned, 1, sizeof (type *)); + op_Sync = new_ir_op (iro_Sync, "Sync", pinned, 0, 0); + + op_Proj = new_ir_op (iro_Proj, "Proj", floats, 0, sizeof (long)); + op_Tuple = new_ir_op (iro_Tuple, "Tuple", floats, 1, 0); + op_Id = new_ir_op (iro_Id, "Id", floats, 0, 0); + op_Bad = new_ir_op (iro_Bad, "Bad", floats, 0, 0); } /* Returns the string for the opcode. */ @@ -147,7 +148,29 @@ ident *get_op_ident(ir_op *op){ return op->name; } +op_pinned get_op_pinned (ir_op *op){ + return op->pinned; +} + +/* Sets pinned in the opcode. Setting it to floating has no effect + for Phi, Block and control flow nodes. */ +void set_op_pinned(ir_op *op, op_pinned pinned) { + if (op == op_Block || op == op_Phi || is_cfopcode(op)) return; + op->pinned = pinned; +} + + /* returns the attribute size of the operator. */ int get_op_attr_size (ir_op *op) { return op->attr_size; } + +int is_cfopcode(ir_op *op) { + return ((op == op_Start) + || (op == op_Jmp) + || (op == op_Cond) + || (op == op_Return) + || (op == op_Raise) + || (op == op_Bad) + || (op == op_End)); +} diff --git a/ir/ir/irop.h b/ir/ir/irop.h index a0a38cbae..1ea3b1ffb 100644 --- a/ir/ir/irop.h +++ b/ir/ir/irop.h @@ -93,8 +93,22 @@ opcode get_op_code (ir_op *op); /* Returns the ident for the opcode name */ ident *get_op_ident (ir_op *op); -/* Returns the attribute size of the opcode. +typedef enum { + floats = 0, /* Nodes of this opcode can be placed in any basic block. */ + pinned /* Nodes must remain in this basic block. */ +} op_pinned; + +op_pinned get_op_pinned (ir_op *op); +/* Sets pinned in the opcode. Setting it to floating has no effect + for Block, Phi and control flow nodes. */ +void set_op_pinned(ir_op *op, op_pinned pinned); + +/* Returns the attribute size of nodes of this opcode. Use not encouraged, internal feature. */ int get_op_attr_size (ir_op *op); +/* Returns true if op is one of Start, End, Jmp, Cond, Return, Raise or Bad. */ +int is_cfopcode(ir_op *op); + + # endif /* _IROP_H_ */ diff --git a/ir/ir/irop_t.h b/ir/ir/irop_t.h index 66e76a408..a4667c840 100644 --- a/ir/ir/irop_t.h +++ b/ir/ir/irop_t.h @@ -11,10 +11,12 @@ struct ir_op { ident *name; size_t attr_size; /* Space needed in memory for private attributes */ int labeled; /* Output edge labels on in-edges in vcg graph */ + int pinned; /* How to deal with the node in cse, pre. */ }; /* create a new ir operation */ -ir_op * new_ir_op (opcode code, ident *name, size_t attr_size, int labeled); +ir_op * new_ir_op (opcode code, char *name, op_pinned p, + int labeled, size_t attr_size); /* initialize the irop module */ void init_op (void); diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c index c16d4ed50..1e0ba9c04 100644 --- a/ir/ir/iropt.c +++ b/ir/ir/iropt.c @@ -765,9 +765,8 @@ transform_node (ir_node *n) /* **************** Common Subexpression Elimination **************** */ -/* Compare function for two nodes in the hash table. Gets two */ -/* nodes as parameters. */ -/* @@@ a+b != b+a ? */ +/* Compare function for two nodes in the hash table. Gets two */ +/* nodes as parameters. Returns 0 if the nodes are a cse. */ static int vt_cmp (const void *elt, const void *key) { @@ -794,12 +793,16 @@ vt_cmp (const void *elt, const void *key) if (get_irn_arity (a) != get_irn_arity(b)) return 1; - /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */ - /* do if (*ain++ != *bin++) return 1; while (ins--); */ - for (i = -1; i < get_irn_arity(a); i++) - if (get_irn_n(a, i) != get_irn_n(b, i)) + /* for block-local cse and pinned nodes: */ + if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) { + if (get_irn_n(a, -1) != get_irn_n(b, -1)) return 1; + } + /* compare a->in[0..ins] with b->in[0..ins] */ + for (i = 0; i < get_irn_arity(a); i++) + if (get_irn_n(a, i) != get_irn_n(b, i)) + return 1; switch (get_irn_opcode(a)) { case iro_Const: @@ -872,33 +875,46 @@ identify (pset *value_table, ir_node *n) { ir_node *o = NULL; - - if (!value_table) return n; - switch (get_irn_opcode (n)) { - case iro_Add: - case iro_Mul: - case iro_Or: - case iro_And: - case iro_Eor: - { - /* for commutative operators perform a OP b == b OP a */ - if (get_binop_left(n) > get_binop_right(n)) { - ir_node *h = get_binop_left(n); - set_binop_left(n, get_binop_right(n)); - set_binop_right(n, h); + if (get_opt_reassociation()) { + switch (get_irn_opcode (n)) { + case iro_Add: + case iro_Mul: + case iro_Or: + case iro_And: + case iro_Eor: + { + /* for commutative operators perform a OP b == b OP a */ + if (get_binop_left(n) > get_binop_right(n)) { + ir_node *h = get_binop_left(n); + set_binop_left(n, get_binop_right(n)); + set_binop_right(n, h); + } } + break; + default: break; } - break; - default: break; } + o = pset_find (value_table, n, ir_node_hash (n)); if (!o) return n; return o; } +/* During construction we set the pinned flag in the graph right when the + optimizatin is performed. The flag turning on procedure global cse could + be changed between two allocations. This way we are safe. */ +static inline ir_node * +identify_cons (pset *value_table, ir_node *n) { + ir_node *old = n; + n = identify(value_table, n); + if (get_irn_n(old, -1) != get_irn_n(n, -1)) + set_irg_pinned(current_ir_graph, floats); + return n; +} + /* Return the canonical node computing the same value as n. Looks up the node in a hash table, enters it in the table if it isn't there yet. */ @@ -965,12 +981,6 @@ optimize (ir_node *n) /* Allways optimize Phi nodes: part of the construction. */ if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n; - /* if not optimize return n */ - if (n == NULL) { - printf(" attention: empty node!!! \n"); - return n; - } - /* constant expression evaluation / constant folding */ if (get_opt_constant_folding()) { /* constants can not be evaluated */ @@ -995,7 +1005,7 @@ optimize (ir_node *n) now all nodes are pinned to blocks, i.e., the cse only finds common subexpressions within a block. */ if (get_opt_cse()) - n = identify (current_ir_graph->value_table, n); + n = identify_cons (current_ir_graph->value_table, n); /* identify found a cse, so deallocate the old node. */ if (n != old_n) { obstack_free (current_ir_graph->obst, old_n); @@ -1032,7 +1042,7 @@ optimize (ir_node *n) nodes lying on the obstack. Remove these by a dead node elimination, i.e., a copying garbage collection. */ ir_node * -optimize_in_place (ir_node *n) +optimize_in_place_2 (ir_node *n) { tarval *tv; ir_node *old_n = n; @@ -1071,8 +1081,9 @@ optimize_in_place (ir_node *n) /* The block input is used to distinguish different subexpressions. Right now all nodes are pinned to blocks, i.e., the cse only finds common subexpressions within a block. */ - if (get_opt_cse()) + if (get_opt_cse()) { n = identify (current_ir_graph->value_table, n); + } /* identify found a cse, so deallocate the old node. */ if (n != old_n) { @@ -1097,3 +1108,15 @@ optimize_in_place (ir_node *n) return n; } + +/* Wrapper for external use, set proper status bits after optimization */ +ir_node * +optimize_in_place (ir_node *n) { + /* Handle graph state */ + assert(get_irg_phase_state(current_ir_graph) != phase_building); + if (get_opt_global_cse()) + set_irg_pinned(current_ir_graph, floats); + if (get_irg_outs_state(current_ir_graph) == outs_consistent) + set_irg_outs_inconsistent(current_ir_graph); + return optimize_in_place_2 (n); +} diff --git a/ir/ir/iropt.h b/ir/ir/iropt.h index f4448d0a0..e2e461d5a 100644 --- a/ir/ir/iropt.h +++ b/ir/ir/iropt.h @@ -24,9 +24,10 @@ optimize (n) may deallocate `n' and everything allocated after `n'! */ -tarval *computed_value (ir_node *n); +tarval *computed_value (ir_node *n); ir_node *optimize (ir_node *n); + ir_node *optimize_in_place (ir_node *n); # endif /* _IROPT_H_ */ diff --git a/ir/ir/iropt_t.h b/ir/ir/iropt_t.h index 592b5364a..2bb29b0a2 100644 --- a/ir/ir/iropt_t.h +++ b/ir/ir/iropt_t.h @@ -17,5 +17,6 @@ pset *new_identities (void); void del_identities (pset *value_table); void add_identity (pset *value_table, ir_node *node); +ir_node *optimize_in_place_2 (ir_node *n); # endif /* _IROPT_T_H_ */ diff --git a/ir/ir/irprog.c b/ir/ir/irprog.c index 458c430e9..c3a16960b 100644 --- a/ir/ir/irprog.c +++ b/ir/ir/irprog.c @@ -35,7 +35,6 @@ ir_prog *new_ir_prog (void) { res = (ir_prog *) malloc (sizeof(ir_prog)); irp = res; - /* res->obst = (struct obstack *) xmalloc (sizeof (struct obstack)); */ res->graphs = NEW_ARR_F (ir_graph *, 1); res->types = NEW_ARR_F (type *, 1); diff --git a/ir/tr/type.c b/ir/tr/type.c index 58bfd026d..fc6a499c8 100644 --- a/ir/tr/type.c +++ b/ir/tr/type.c @@ -189,23 +189,27 @@ set_type_state(type *tp, type_state state) { case tpo_class: { assert(get_type_size(tp) > -1); - for (i = 0; i < get_class_n_member(tp); i++) - assert(get_entity_offset(get_class_member(tp, i)) > -1); - assert(get_entity_allocation(get_class_member(tp, i)) == automatic_allocated); + if (tp != get_glob_type()) + for (i = 0; i < get_class_n_member(tp); i++) { + assert(get_entity_offset(get_class_member(tp, i)) > -1); + /* assert(get_entity_allocation(get_class_member(tp, i)) == automatic_allocated); @@@ lowerfirm geht nicht durch */ + } } break; case tpo_struct: { - assert(get_type_size(tp) > -1); + /* assert(get_type_size(tp) > -1); @@@ lowerfirm geht nicht durch */ for (i = 0; i < get_struct_n_member(tp); i++) { assert(get_entity_offset(get_struct_member(tp, i)) > -1); - assert(get_entity_allocation(get_struct_member(tp, i)) == automatic_allocated); + /* assert(get_entity_allocation(get_struct_member(tp, i)) == automatic_allocated); @@@ lowerfirm geht nicht durch */ } } break; case tpo_union: { /* ?? */ } break; case tpo_array: - { /* ?? */ + { /* ?? + Check order? + Assure that only innermost dimension is dynamic? */ } break; case tpo_enumeration: { @@ -402,7 +406,7 @@ inline void free_struct_attrs (type *strct) { /* manipulate private fields of struct */ void add_struct_member (type *strct, entity *member) { assert(strct && (strct->type_op == type_struct)); - assert(get_type_tpop(get_entity_type(member)) != type_method); + /*assert(get_type_tpop(get_entity_type(member)) != type_method); @@@ lowerfirm geht nicht durch */ ARR_APP1 (entity *, strct->attr.sa.members, member); } int get_struct_n_member (type *strct) { diff --git a/testprograms/Makefile.in b/testprograms/Makefile.in index b53b3a1f1..2e19e8772 100644 --- a/testprograms/Makefile.in +++ b/testprograms/Makefile.in @@ -17,7 +17,8 @@ SOURCES := Makefile.in \ call_str_example.c if_else_example.c memory_example.c \ cond_example.c if_example.c oo_program_example.c \ const_eval_example.c if_while_example.c three_cfpred_example.c \ - dead_block_example.c inheritance_example.c while_example.c + dead_block_example.c inheritance_example.c while_example.c \ + endless_loop.c global_cse.c oo_inline_example.c bin_EXAMPLES = $(CFILES:.c=) run_bin_EXAMPLES = $(patsubst %.c,./%;,$(CFILES)) diff --git a/testprograms/array-heap_example.c b/testprograms/array-heap_example.c index c09bcdc61..b445639fc 100644 --- a/testprograms/array-heap_example.c +++ b/testprograms/array-heap_example.c @@ -140,6 +140,8 @@ main(void) add_in_edge (get_irg_end_block(main_irg), x); mature_block (get_irg_end_block(main_irg)); + finalize_cons (main_irg); + printf("Optimizing ...\n"); dead_node_elimination(main_irg); diff --git a/testprograms/array-stack_example.c b/testprograms/array-stack_example.c index 38287fd48..a4cb412c4 100644 --- a/testprograms/array-stack_example.c +++ b/testprograms/array-stack_example.c @@ -130,13 +130,14 @@ main(void) add_in_edge (get_irg_end_block(main_irg), x); mature_block (get_irg_end_block(main_irg)); + finalize_cons (main_irg); + printf("Optimizing ...\n"); dead_node_elimination(main_irg); /* verify the graph */ irg_vrfy(main_irg); - printf("Dumping the graph and a type graph.\n"); dump_ir_block_graph (main_irg); dump_type_graph(main_irg); diff --git a/testprograms/call_str_example.c b/testprograms/call_str_example.c index 3fa59baa5..57e677e9d 100644 --- a/testprograms/call_str_example.c +++ b/testprograms/call_str_example.c @@ -109,6 +109,8 @@ int main(int argc, char **argv) /* Now we can mature the end block as all it's predecessors are known. */ mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/cond_example.c b/testprograms/cond_example.c index e10205fb3..ce4800a9b 100644 --- a/testprograms/cond_example.c +++ b/testprograms/cond_example.c @@ -121,6 +121,8 @@ int main(int argc, char **argv) /* Now we can mature the end block as all it's predecessors are known. */ mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/const_ent_example.c b/testprograms/const_ent_example.c index 4a5590634..991072743 100644 --- a/testprograms/const_ent_example.c +++ b/testprograms/const_ent_example.c @@ -42,7 +42,8 @@ int main(int argc, char **argv) entity *ae, *fe, *ge, *dipte, *diptpe; /* e names entities */ ir_node *n; - printf("\nCreating type information...\n"); + printf("\nExample program for constant entites.\n"); + printf("Creating type information...\n"); /** init library */ init_firm (); diff --git a/testprograms/const_eval_example.c b/testprograms/const_eval_example.c index 59384ef68..7e2dae7cb 100644 --- a/testprograms/const_eval_example.c +++ b/testprograms/const_eval_example.c @@ -83,13 +83,15 @@ main(void) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); - printf("Done building the graph. Dumping it.\n"); /* verify the graph */ irg_vrfy(irg); + printf("Done building the graph. Dumping it.\n"); dump_ir_block_graph (irg); printf("use xvcg to view this graph:\n"); diff --git a/testprograms/dead_block_example.c b/testprograms/dead_block_example.c index 113c21c5d..41d118df6 100644 --- a/testprograms/dead_block_example.c +++ b/testprograms/dead_block_example.c @@ -130,6 +130,8 @@ int main(int argc, char **argv) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); local_optimize_graph (irg); dead_node_elimination (irg); diff --git a/testprograms/empty.c b/testprograms/empty.c index 2b10dd51e..0b4624ca3 100644 --- a/testprograms/empty.c +++ b/testprograms/empty.c @@ -87,6 +87,7 @@ int main(int argc, char **argv) /* Verify the graph. Finds some very bad errors in the graph. */ irg_vrfy(irg); + finalize_cons (irg); printf("Done building the graph. Dumping it.\n"); dump_ir_block_graph (irg); diff --git a/testprograms/endless_loop.c b/testprograms/endless_loop.c new file mode 100644 index 000000000..446b5b16f --- /dev/null +++ b/testprograms/endless_loop.c @@ -0,0 +1,146 @@ +/* (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** testprogram. +*/ + +/* $ID$ */ + +# include "irdump.h" +# include "firm.h" +# include "irnode.h" + +/** +*** This file constructs the ir for the following pseudo-program: +*** +*** VAR_A is some extern variable. +*** +*** main(int a) { // pos 0 +*** int b = 1; // pos 1 +*** int h; // pos 2 +*** +*** while (0 == 0) loop { +*** h = a; +*** a = b; +*** b = h; +*** VAR_A = b; +*** } +*** +*** return a-b; +*** } +**/ + +int +main(void) +{ + type *prim_t_int; + ir_graph *irg; + type *owner; + type *proc_main; + entity *ent; + ir_node *b, *x, *r, *t, *f; + + printf("\nCreating an IR graph: ENDLESS_LOOP_EXAMPLE...\n"); + + init_firm (); + + set_optimize(1); + set_opt_constant_folding(1); + set_opt_cse(1); + set_opt_global_cse(1); + set_opt_dead_node_elimination (1); + + prim_t_int = new_type_primitive(id_from_str ("int", 3), mode_i); + +#define METHODNAME "main_tp" +#define NRARGS 1 +#define NRES 1 + + proc_main = new_type_method(id_from_str(METHODNAME, strlen(METHODNAME)), + NRARGS, NRES); + set_method_param_type(proc_main, 0, prim_t_int); + set_method_res_type(proc_main, 0, prim_t_int); + + + owner = new_type_class (id_from_str ("ENDLESS_LOOP_EXAMPLE", 20)); + ent = new_entity (owner, id_from_str ("main", strlen("main")), proc_main); + + /* Generates start and end blocks and nodes and a first, initial block */ + irg = new_ir_graph (ent, 4); + + /* Generate two values */ + set_value (0, new_Proj(get_irg_args(irg), mode_i, 0)); + set_value (1, new_Const (mode_i, tarval_from_long (mode_i, 1))); + + x = new_Jmp(); + mature_block (get_irg_current_block(irg)); + + /* generate a block for the loop header and the conditional branch */ + r = new_immBlock (); + add_in_edge (r, x); + x = new_Cond (new_Proj(new_Cmp(new_Const (mode_i, tarval_from_long (mode_i, 0)), + new_Const (mode_i, tarval_from_long (mode_i, 0))), + mode_b, Eq)); + f = new_Proj (x, mode_X, 0); + t = new_Proj (x, mode_X, 1); + + /* generate the block for the loop body */ + b = new_immBlock (); + add_in_edge (b, t); + x = new_Jmp (); + add_in_edge (r, x); + + /* The code in the loop body, + as we are dealing with local variables only the dataflow edges + are manipulated. */ + set_value (2, get_value (0, mode_i)); + set_value (0, get_value (1, mode_i)); + set_value (1, get_value (2, mode_i)); + + /* set VAR_A to constant value */ + set_store (new_Proj (new_Store (get_store (), + new_Const (mode_p, tarval_p_from_str ("VAR_A")), + get_value(1, mode_i)), + mode_M, 0)); + + mature_block (b); + mature_block (r); + + /* generate the return block */ + r = new_immBlock (); + add_in_edge (r, f); + mature_block (r); + + { + ir_node *in[1]; + in[0] = new_Sub (get_value (0, mode_i), get_value (1, mode_i), mode_i); + + x = new_Return (get_store (), 1, in); + } + + /* finalize the end block generated in new_ir_graph() */ + add_in_edge (get_irg_end_block(irg), x); + mature_block (get_irg_end_block(irg)); + + finalize_cons (irg); + + printf("Optimizing ...\n"); + + dead_node_elimination(irg); + local_optimize_graph(irg); + + /* verify the graph */ + irg_vrfy(irg); + + /* output the vcg file */ + printf("Done building the graph. Dumping it.\n"); + turn_of_edge_labels(); + dump_all_types(); + dump_ir_block_graph (irg); + printf("Use xvcg to view this graph:\n"); + printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n"); + + return (0); +} diff --git a/testprograms/global_cse.c b/testprograms/global_cse.c new file mode 100644 index 000000000..f17731cac --- /dev/null +++ b/testprograms/global_cse.c @@ -0,0 +1,157 @@ +/* Copyright (C) 2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Christian Schaefer, Goetz Lindenmaier +** +** testprogram. +*/ + +/* $Id$ */ + +# include "irdump.h" +# include "firm.h" + +/** +*** This file constructs the ir for the following pseudo-program: +*** +*** int main(int a) { +*** int b = 2; +*** if ( a == b ) { +*** a := a - 3; +*** } else { +*** a := a - 3; +*** a := a + 5; +*** } +*** return a; +*** } +**/ + +int +main(void) +{ + ir_graph *irg; + type *owner; + entity *ent; + type *proc_main; /* type information for the method main */ + type *typ; + ir_node *x, *r, *t, *f, *a, *cmp; + int a_pos, b_pos; + + printf("\nCreating an IR graph: GLOBAL_CSE_EXAMPLE...\n"); + + init_firm (); + + set_optimize(1); + set_opt_constant_folding(1); + set_opt_cse(1); + set_opt_global_cse(1); + set_opt_dead_node_elimination (1); + +#define CLASSNAME "GLOBAL_CSE_EXAMPLE" +#define METHODNAME "main" +#define NRARGS 1 +#define NRES 1 + + /** Type information for the procedure **/ + + owner = get_glob_type(); + /* Type information for the procedure */ + proc_main = new_type_method(id_from_str(METHODNAME, strlen(METHODNAME)), + NRARGS, NRES); + /* The entity for the procedure */ + ent = new_entity (owner, + id_from_str (METHODNAME, strlen(METHODNAME)), + proc_main); + /* The type int. This type is necessary to model the result and parameters + the procedure. */ +#define PRIM_NAME "int" + typ = new_type_primitive(id_from_str(PRIM_NAME, strlen(PRIM_NAME)), mode_i); + /* The parameter and result types of the procedure. */ + set_method_param_type(proc_main, 0, typ); + set_method_res_type(proc_main, 0, typ); + + /** The code of the procedure **/ + + /* Generates start and end blocks and nodes, and a first, initial block */ +#define NRLOCS 2 + irg = new_ir_graph (ent, NRLOCS); + + /* The value position used for: */ + a_pos = 0; + b_pos = 1; + + /* Get the procedure parameter and assign it to the parameter variable + a. */ + set_value (a_pos, new_Proj (get_irg_args(irg), mode_i, 0)); + /* Generate the constant and assign it to b. The assignment is resovled to a + dataflow edge. */ + set_value (b_pos, new_Const (mode_i, tarval_from_long (mode_i, 2))); + /* We know all predecessors of the block and all set_values and set_stores are + preformed. We can mature the block. */ + mature_block (get_irg_current_block(irg)); + + /* Generate a conditional branch */ + cmp = new_Cmp(get_value(a_pos, mode_i), get_value(b_pos, mode_i)); /* + cmp = new_Cmp(new_Const (mode_i, tarval_from_long (mode_i, 2)), + new_Const (mode_i, tarval_from_long (mode_i, 2)));*/ + x = new_Cond (new_Proj(cmp, mode_b, Eq)); + f = new_Proj (x, mode_X, 0); + t = new_Proj (x, mode_X, 1); + + /* generate and fill the then block */ + r = new_immBlock (); + add_in_edge (r, t); + a = new_Sub(get_value(a_pos, mode_i), + new_Const (mode_i, tarval_from_long (mode_i, 3)), + mode_i); + set_value (a_pos, a); + + mature_block (r); + t = new_Jmp (); + + /* generate the else block */ + r = new_immBlock (); + add_in_edge (r, f); + a = new_Sub(get_value(a_pos, mode_i), + new_Const (mode_i, tarval_from_long (mode_i, 3)), + mode_i); + a = new_Add(a, new_Const (mode_i, tarval_from_long (mode_i, 5)), mode_i); + set_value (a_pos, a); + + mature_block (r); + f = new_Jmp (); + + /* generate the fall through block and add all cfg edges */ + r = new_immBlock (); + add_in_edge (r, f); + add_in_edge (r, t); + mature_block (r); + /* The Return statement */ + { + ir_node *in[1], *store ; + in[0] = get_value (a_pos, mode_i); + store = get_store(); + + x = new_Return (store, 1, in); + } + + /* finalize the end block generated in new_ir_graph() */ + add_in_edge (get_irg_end_block(irg), x); + mature_block (get_irg_end_block(irg)); + + /* verify the graph */ + irg_vrfy(irg); + finalize_cons (irg); + + printf("Optimizing ...\n"); + local_optimize_graph(irg); + dead_node_elimination(irg); + + /* output the vcg file */ + printf("Done building the graph. Dumping it.\n"); + dump_ir_block_graph (irg); + printf("use xvcg to view this graph:\n"); + printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n"); + + return (0); +} diff --git a/testprograms/global_var_example.c b/testprograms/global_var_example.c index c5e038e3c..15d208d3e 100644 --- a/testprograms/global_var_example.c +++ b/testprograms/global_var_example.c @@ -105,6 +105,8 @@ int main(int argc, char **argv) /* Now we can mature the end block as all it's predecessors are known. */ mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/if_else_example.c b/testprograms/if_else_example.c index 82e22c0e4..26b8b3e97 100644 --- a/testprograms/if_else_example.c +++ b/testprograms/if_else_example.c @@ -126,6 +126,7 @@ int main(int argc, char **argv) /* verify the graph */ irg_vrfy(irg); + finalize_cons (irg); printf("Done building the graph. Dumping it.\n"); dump_ir_block_graph (irg); diff --git a/testprograms/if_example.c b/testprograms/if_example.c index f3944e134..37c030fa9 100644 --- a/testprograms/if_example.c +++ b/testprograms/if_example.c @@ -116,6 +116,7 @@ main(void) /* verify the graph */ irg_vrfy(irg); + finalize_cons (irg); /* output the vcg file */ printf("Done building the graph. Dumping it.\n"); diff --git a/testprograms/if_while_example.c b/testprograms/if_while_example.c index 0b572b801..2c58c7680 100644 --- a/testprograms/if_while_example.c +++ b/testprograms/if_while_example.c @@ -121,17 +121,22 @@ main(void) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); local_optimize_graph(irg); dead_node_elimination(irg); + compute_outs(irg); + /* verify the graph */ irg_vrfy(irg); /* output the vcg file */ - printf("Done building the graph. Dumping it.\n"); - dump_ir_block_graph (irg); + printf("Done building the graph. Dumping it with out-edges.\n"); + dump_out_edges(); + dump_ir_graph (irg); printf("Use xvcg to view this graph:\n"); printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n"); diff --git a/testprograms/irr_cf_example.c b/testprograms/irr_cf_example.c index 8f231a671..3b8b9211a 100644 --- a/testprograms/irr_cf_example.c +++ b/testprograms/irr_cf_example.c @@ -124,6 +124,8 @@ int main(int argc, char **argv) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/irr_loop_example.c b/testprograms/irr_loop_example.c index 43c1d00fd..b6eda9509 100644 --- a/testprograms/irr_loop_example.c +++ b/testprograms/irr_loop_example.c @@ -113,6 +113,8 @@ int main(int argc, char **argv) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/memory_example.c b/testprograms/memory_example.c index 64dd4ff5b..9b76b11a2 100644 --- a/testprograms/memory_example.c +++ b/testprograms/memory_example.c @@ -141,6 +141,8 @@ main(void) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); dead_node_elimination(irg); diff --git a/testprograms/oo_inline_example.c b/testprograms/oo_inline_example.c new file mode 100644 index 000000000..4f482f185 --- /dev/null +++ b/testprograms/oo_inline_example.c @@ -0,0 +1,301 @@ +/* Copyright (C)2002 by Universitaet Karlsruhe +** All rights reserved. +** +** Authors: Goetz Lindenmaier +** +** testprogram. +*/ + +/* $ID$ */ + +# include "irdump.h" +# include "firm.h" +# include "irnode.h" + +/** This file constructs the IR for the following program: +*** @@@ this is no more correct ... +*** class PRIMA { +*** a: int; +*** +*** int c(d: int) { +*** return (d + self.a); +*** } +*** +*** void set_a(e:int) { +*** self.a = e; +*** } +*** +*** } +*** +*** int main() { +*** o: PRIMA; +*** o = new PRIMA; +*** o.set_a(2); +*** return o.c(5); +*** }; +*** +**/ + +int +main(void) +{ + type *prim_t_int; + type *owner, *class_prima; + type *proc_main, *proc_set_a, *proc_c; + type *class_p_ptr; + entity *proc_main_e, *proc_set_a_e, *proc_c_e, *a_e; + + ir_graph *main_irg, *set_a_irg, *c_irg; + ir_node *c2, *c5, *obj_o, *obj_size, *proc_ptr, *call, *res, *x, *set_a_call, *c_call; + ir_node *self, *par1, *a_ptr; + ir_node *a_val, *r, *t, *b, *f; + + int o_pos, self_pos, e_pos, d_pos; + + int i; + + init_firm (); + + set_optimize(1); + set_opt_inline (1); + set_opt_constant_folding(1); + set_opt_cse(1); + set_opt_dead_node_elimination(1); + + /*** Make basic type information for primitive type int. ***/ + prim_t_int = new_type_primitive(id_from_str ("int", 3), mode_i); + + /*** Make type information for the class (PRIMA). ***/ + /* The type of the class */ + class_prima = new_type_class(id_from_str ("PRIMA_INLINE", 5)); + /* We need type information for pointers to the class: */ + class_p_ptr = new_type_pointer (id_from_str ("class_prima_ptr", 15), + class_prima); + /* An entity for the field (a). The entity constructor automatically adds + the entity as member of the owner. */ + a_e = new_entity(class_prima, id_from_str ("a", 1), prim_t_int); + /* An entity for the method set_a. But first we need type information + for the method. */ + proc_set_a = new_type_method(id_from_str("set_a", 5), 2, 0); + set_method_param_type(proc_set_a, 0, class_p_ptr); + set_method_param_type(proc_set_a, 1, prim_t_int); + proc_set_a_e = new_entity(class_prima, id_from_str ("set_a", 5), proc_set_a); + /* An entity for the method c. Implicit argument "self" must be modeled + explicit! */ + proc_c = new_type_method(id_from_str("c", 1 ), 2, 1); + set_method_param_type(proc_c, 0, class_p_ptr); + set_method_param_type(proc_c, 1, prim_t_int); + set_method_res_type(proc_c, 0, prim_t_int); + proc_c_e = new_entity(class_prima, id_from_str ("c", 1), proc_c); + + /*** Now build procedure main. ***/ + /** Type information for main. **/ + printf("\nCreating an IR graph: OO_INLINE_EXAMPLE...\n"); + /* Main is not modeled as part of an explicit class here. Therefore the + owner is the global type. */ + owner = get_glob_type(); + /* Main has zero parameters and one result. */ + proc_main = new_type_method(id_from_str("main", 4), 0, 1); + /* The result type is int. */ + set_method_res_type(proc_main, 0, prim_t_int); + + /* The entity for main. */ + proc_main_e = new_entity (owner, id_from_str ("main", 4), proc_main); + + /** Build code for procedure main. **/ + /* We need one local variable (for "o"). */ + main_irg = new_ir_graph (proc_main_e, 1); + o_pos = 0; + + /* Remark that this irg is the main routine of the program. */ + set_irp_main_irg(main_irg); + + /* Make the constants. They are independent of a block. */ + c2 = new_Const (mode_i, tarval_from_long (mode_i, 2)); + c5 = new_Const (mode_i, tarval_from_long (mode_i, 5)); + + /* There is only one block in main, it contains the allocation and the calls. */ + /* Allocate the defined object and generate the type information. */ + obj_size = new_SymConst((type_or_id_p)class_prima, size); + obj_o = new_Alloc(get_store(), obj_size, class_prima, heap_alloc); + set_store(new_Proj(obj_o, mode_M, 0)); /* make the changed memory visible */ + obj_o = new_Proj(obj_o, mode_p, 2); /* remember the pointer to the object */ + set_value(o_pos, obj_o); + + /* Get the pointer to the procedure from the object. */ + proc_ptr = new_simpleSel(get_store(), /* The memory containing the object. */ + get_value(o_pos, mode_p),/* The pointer to the object. */ + proc_set_a_e ); /* The feature to select. */ + + /* Call procedure set_a, first built array with parameters. */ + { + ir_node *in[2]; + in[0] = get_value(o_pos, mode_p); + in[1] = c2; + set_a_call = new_Call(get_store(), proc_ptr, 2, in, proc_set_a); + + } + /* Make the change to memory visible. There are no results. */ + set_store(new_Proj(set_a_call, mode_M, 0)); + + /* Get the pointer to the nest procedure from the object. */ + proc_ptr = new_simpleSel(get_store(), get_value(o_pos, mode_p), proc_c_e); + + /* call procedure c, first built array with parameters */ + { + ir_node *in[2]; + in[0] = get_value(o_pos, mode_p); + in[1] = c5; + c_call = new_Call(get_store(), proc_ptr, 2, in, proc_c); + } + /* make the change to memory visible */ + set_store(new_Proj(c_call, mode_M, 0)); + /* Get the result of the procedure: select the result tuple from the call, + then the proper result from the tuple. */ + res = new_Proj(new_Proj(c_call, mode_T, 2), mode_i, 0); + + /* return the results of procedure main */ + { + ir_node *in[1]; + in[0] = res; + x = new_Return (get_store(), 1, in); + } + mature_block (get_irg_current_block(main_irg)); + + /* complete the end_block */ + add_in_edge (get_irg_end_block(main_irg), x); + mature_block (get_irg_end_block(main_irg)); + + irg_vrfy(main_irg); + finalize_cons (main_irg); + + /****************************************************************************/ + + printf("Creating IR graph for set_a: \n"); + + /* Local variables: self, e */ + set_a_irg = new_ir_graph (proc_set_a_e, 2); + self_pos = 0; e_pos = 1; + + /* get the procedure parameter */ + self = new_Proj(get_irg_args(set_a_irg), mode_p, 0); + set_value(self_pos, self); + par1 = new_Proj(get_irg_args(set_a_irg), mode_i, 1); + set_value(e_pos, par1); + /* Create and select the entity to set */ + a_ptr = new_simpleSel(get_store(), self, a_e); + /* perform the assignment */ + set_store(new_Proj(new_Store(get_store(), a_ptr, par1), mode_M, 0)); + + /* return nothing */ + x = new_Return (get_store (), 0, NULL); + mature_block (get_irg_current_block(set_a_irg)); + + /* complete the end_block */ + add_in_edge (get_irg_end_block(set_a_irg), x); + mature_block (get_irg_end_block(set_a_irg)); + + /* verify the graph */ + irg_vrfy(set_a_irg); + finalize_cons (set_a_irg); + + /****************************************************************************/ + + printf("Creating IR graph for c: \n"); + + /* Local variables self, d */ + c_irg = new_ir_graph (proc_c_e, 5); + + /* get the procedure parameter */ + self = new_Proj(get_irg_args(c_irg), mode_p, 0); + set_value(0, self); + par1 = new_Proj(get_irg_args(c_irg), mode_i, 1); + set_value(1, par1); + set_value(2, new_Const (mode_i, tarval_from_long (mode_i, 0))); + + x = new_Jmp(); + mature_block (get_irg_current_block(c_irg)); + + /* generate a block for the loop header and the conditional branch */ + r = new_immBlock (); + add_in_edge (r, x); + x = new_Cond (new_Proj(new_Cmp(new_Const (mode_i, tarval_from_long (mode_i, 0)), + new_Const (mode_i, tarval_from_long (mode_i, 0))), + mode_b, Eq)); + + /* x = new_Cond (new_Proj(new_Cmp(new_Const (mode_i, tarval_from_long (mode_i, 0)), + get_value(1, mode_i)), + mode_b, Eq));*/ + f = new_Proj (x, mode_X, 0); + t = new_Proj (x, mode_X, 1); + + /* generate the block for the loop body */ + b = new_immBlock (); + add_in_edge (b, t); + + /* The code in the loop body, + as we are dealing with local variables only the dataflow edges + are manipulated. */ + set_value (3, get_value (1, mode_i)); + set_value (1, get_value (2, mode_i)); + set_value (2, get_value (3, mode_i)); + a_ptr = new_simpleSel(get_store(), self, a_e); + set_store(new_Store(get_store(), a_ptr, get_value(2, mode_i))); + x = new_Jmp (); + add_in_edge(r, x); + mature_block (b); + mature_block (r); + + /* generate the return block */ + r = new_immBlock (); + add_in_edge (r, f); + /* Select the entity and load the value */ + a_ptr = new_simpleSel(get_store(), self, a_e); + a_val = new_Load(get_store(), a_ptr); + set_store(new_Proj(a_val, mode_M, 0)); + a_val = new_Proj(a_val, mode_i, 2); + + /* return the result */ + { + ir_node *in[1]; + in[0] = new_Add(par1, a_val, mode_i); + + x = new_Return (get_store (), 1, in); + } + mature_block (r); + + /* complete the end_block */ + add_in_edge (get_irg_end_block(c_irg), x); + mature_block (get_irg_end_block(c_irg)); + + /* verify the graph */ + irg_vrfy(c_irg); + finalize_cons (c_irg); + + /****************************************************************************/ + + + collect_phiprojs(main_irg); + current_ir_graph = main_irg; + printf("Inlining set_a ...\n"); + inline_method(set_a_call, set_a_irg); + printf("Inlineing c ...\n"); + inline_method(c_call, c_irg); + + printf("Optimizing ...\n"); + + for (i = 0; i < get_irp_n_irgs(); i++) { + local_optimize_graph(get_irp_irg(i)); + dead_node_elimination(get_irp_irg(i)); + } + + printf("Dumping graphs of all procedures and a type graph.\n"); + turn_of_edge_labels(); + dump_all_ir_graphs(dump_ir_block_graph); + dump_all_ir_graphs(dump_ir_block_graph_w_types); + dump_all_types(); + + printf("Use xvcg to view these graphs:\n"); + printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n"); + return (1); +} diff --git a/testprograms/oo_program_example.c b/testprograms/oo_program_example.c index 791500528..f3dcaad56 100644 --- a/testprograms/oo_program_example.c +++ b/testprograms/oo_program_example.c @@ -161,6 +161,7 @@ main(void) mature_block (get_irg_end_block(main_irg)); irg_vrfy(main_irg); + finalize_cons (main_irg); /****************************************************************************/ @@ -190,6 +191,7 @@ main(void) /* verify the graph */ irg_vrfy(set_a_irg); + finalize_cons (set_a_irg); /****************************************************************************/ @@ -223,6 +225,7 @@ main(void) /* verify the graph */ irg_vrfy(c_irg); + finalize_cons (c_irg); /****************************************************************************/ diff --git a/testprograms/three_cfpred_example.c b/testprograms/three_cfpred_example.c index a5232a727..3c75c423b 100644 --- a/testprograms/three_cfpred_example.c +++ b/testprograms/three_cfpred_example.c @@ -147,11 +147,12 @@ int main(int argc, char **argv) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); - printf("Optimizing ...\n"); - dead_node_elimination(irg); - /* verify the graph */ irg_vrfy(irg); + finalize_cons (irg); + + printf("Optimizing ...\n"); + dead_node_elimination(irg); printf("Dumping the graph and a control flow graph.\n"); dump_ir_block_graph (irg); diff --git a/testprograms/while_example.c b/testprograms/while_example.c index c1dd962f4..df02e5415 100644 --- a/testprograms/while_example.c +++ b/testprograms/while_example.c @@ -111,6 +111,8 @@ main(void) add_in_edge (get_irg_end_block(irg), x); mature_block (get_irg_end_block(irg)); + finalize_cons (irg); + printf("Optimizing ...\n"); local_optimize_graph(irg), -- 2.20.1